Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#15236 closed task (implemented)

Identify functions most in need of testing, and hardest to test

Reported by: nickm Owned by:
Priority: Medium Milestone: Tor: 0.2.7.x-final
Component: Core Tor/Tor Version: Tor: 0.2.7
Severity: Keywords: SponsorS
Cc: Actual Points:
Parent ID: Points: medium
Reviewer: Sponsor:

Description

In addition to our opportunistic write-tests-as-you-go approach, we should also direct our testing efforts on the functions that most *need* to be tested. This includes (possibly)

  • Big functions
  • Volatile functions (ones that have changed many times)
  • Functions that have had lots of bugs in them in the past
  • Functions nobody understands
  • Functions with high complexity
  • Functions with high complexity-to-line ratio
  • Functions with high code-to-comments ratio

We should also look at what's hardest to test, including possibly

  • Anything that hits the OS directly
  • Anything that's windows only.
  • Anything that calls many other functions
  • Anything that calls many other modules
  • Anything that indirectly calls most of the rest of Tor.

Child Tickets

Change History (6)

comment:1 Changed 4 years ago by nickm

I have a script that looks for functions with certain properties using git-blame. It can count:

  • Lines
  • Number of distinct months of commits
  • Number of distinct commits
  • Number of distinct commits with the string "bug" in them

Get the branch findvolatile from my public repository and play around with it. It's a bit addictive. Edit the 'badness' function. Sort the results on different columns. Omit the "scariness" calculation if you aren't using it; it's slow!

I pregenerated some git-blame output with touch blame_all; for fn in src/common/*.c src/or/*.c src/tools/*.c src/tools/*/*.c ; do echo $fn;; git blame -wMC $fn >> blame_all; done, and I've been piping it to lots of variants of this.

So far, the different ways to calculate are pretty samey, and give similar results. Big functions appear extra-high on the list. But there are ones that are "bad for their size" that get ranked a little higher than others.

Top-10 longest functions (all lists by ascending badness):

circuit_expire_building
parse_port_config
run_scheduled_events
connection_ap_handshake_rewrite_and_attach
options_act
networkstatus_parse_vote_from_string
connection_dir_client_reached_eof
directory_handle_command_get
networkstatus_compute_consensus
options_validate

Top-10 most scary functions (commits plus "bug" in log messages):

networkstatus_compute_consensus
init_keys
connection_edge_process_relay_cell
connection_ap_handshake_rewrite_and_attach
router_rebuild_descriptor
directory_handle_command_get
connection_dir_client_reached_eof
run_scheduled_events
options_act
options_validate

Top 10 most modified functions (number of distinct commits):

circuit_expire_building
parse_port_config
run_scheduled_events
connection_ap_handshake_rewrite_and_attach
options_act
networkstatus_parse_vote_from_string
connection_dir_client_reached_eof
directory_handle_command_get
networkstatus_compute_consensus
options_validate

Top 10 most high-scoring functions (sqrt(scariness times distinct months) divided by lines.):

router_dump_router_to_string
connection_dir_client_reached_eof
router_add_to_routerlist
init_keys
connection_exit_begin_conn
connection_handle_write_impl
router_rebuild_descriptor
options_validate
options_act
run_scheduled_events

And now for something completely different: as above, but somewhat de-weighted for length:

consider_testing_reachability
connection_connect_sockaddr
connection_close_immediate
add_callback_log
tor_free_all
router_rebuild_descriptor
add_stream_log_impl
run_scheduled_events
connection_edge_destroy
directory_info_has_arrived

comment:2 Changed 4 years ago by nickm

In order to try to figure out the "hardest-to-test" functions, I've been looking through the Tor callgraph.

(How do you get a callgraph? Make sure you have "clang" and "opt" installed, then run:

for f in src/common/*.c src/or/*.c ; do clang -S -emit-llvm $f -std=gnu99 -DHAVE_CONFIG_H -I.  -I./src/ext -Isrc/ext -I./src/ext/trunnel -I./src/trunnel -I./src/common -Isrc/common -I./src/ext/trunnel -I./src/trunnel -I./src/or -Isrc/or -DSHARE_DATADIR="\"/usr/local/share\"" -DLOCALSTATEDIR="\"/usr/local/var\"" -DBINDIR="\"/usr/local/bin\"" -I./src/common | opt -analyze -print-callgraph 2>$f.callgraph ; done

Then post-process the data with a little python script, and then you're set.)

If you want to see the callgraph data I got for approximately-current master, head over to https://people.torproject.org/~nickm/volatile/call-graph-stuff/ .

Anyway, it looks as though our call-graph breaks down so that about 85% of our functions are nice sensible functions from which only a smaller number of functions are reachable... but the rest of our functions can reach *nearly any other function in or called by Tor*. These are likely to be among the hardest to debug, given how complex their potential behavior is.

Here is the list of the top 25 offenders, and the number of other functions reachable from them:

3157 command_process_created_cell
3157 connection_about_to_close_connection
3158 dns_resolve
3158 evdns_callback
3159 connection_exit_begin_resolve
3161 connection_unlink
3161 dirserv_generate_networkstatus_vote_obj
3164 conn_close_if_marked
3165 close_closeable_connections
3165 dirvote_compute_consensuses
3166 conn_read_callback
3166 conn_write_callback
3167 dirvote_perform_vote
3169 connection_exit_begin_conn
3170 command_process_create_cell
3172 rend_process_relay_cell
3200 dirvote_act
3201 tor_main
3202 main
3266 connection_edge_process_relay_cell
3274 circuit_receive_relay_cell
3276 command_process_relay_cell
3306 command_process_cell
3355 run_scheduled_events
3367 second_elapsed_callback

comment:3 Changed 4 years ago by nickm

And here's a pure-volatility measure. Use Git and Perl to find out which functions have been changed the most:

git log -p |perl -ne 'if (/\@\@[^\@]*\@\@ .* ([A-Za-z0-9_]+)\(/) { print "$1\n";}' | sort |uniq -c >change_counts

The top 25 offenders are:

  60 router_rebuild_descriptor
  61 onion_extend_cpath
  62 directory_handle_command
  63 dns_resolve
  65 assert_connection_ok
  66 connection_handle_write
  68 connection_handle_listener_read
  71 dns_found_answer
  73 circuit_extend
  73 main
  79 connection_edge_process_inbuf
  83 connection_ap_handshake_attach_circuit
  86 config_assign
  88 init_keys
  94 circuit_send_next_onion_skin
  94 connection_dir_process_inbuf
  94 prepare_for_poll
  95 connection_exit_begin_conn
 124 connection_ap_handshake_process_socks
 124 router_dump_router_to_string
 142 fetch_from_buf_socks
 144 getconfig
 149 run_scheduled_events
 158 connection_edge_process_relay_cell
 178 do_main_loop

Complete list at https://people.torproject.org/~nickm/volatile/sorted_change_counts.bz2

comment:4 Changed 4 years ago by nickm

Status: newassigned

comment:5 Changed 4 years ago by nickm

Resolution: implemented
Status: assignedclosed

I've summarized my results here in this email:

https://lists.torproject.org/pipermail/tor-dev/2015-March/008545.html

comment:6 Changed 4 years ago by isabela

Points: medium
Version: Tor: 0.2.7
Note: See TracTickets for help on using tickets.