Opened 4 years ago

Last modified 2 years ago

#16764 new enhancement

Simplify Tor's control flow graph to the extent we can.

Reported by: nickm Owned by:
Priority: High Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: blob, tor-modularity, callgraph, technical-debt
Cc: Actual Points:
Parent ID: Points: parent
Reviewer: Sponsor: SponsorS-can

Description

For background, see http://archives.seul.org/tor/dev/Mar-2015/msg00197.html .

As of this writing, the largest strongly-connected component in Tor's callgraph has 407 functions in it. Nobody can actually understand a program that's so complex. Let's simplify it!

(This is a parent ticket.)

Child Tickets

TicketTypeStatusOwnerSummary
#16695defectclosedDecouple generating controller events from sending them to controllers
#16762enhancementclosedMove most of directory_all_unreachable into a backend callback
#16763defectclosedExtract client-only parts of init_keys()
#16766enhancementclosedDon't call process_signal directly from control.c
#16788enhancementclosedDon't call tor_cleanup() directly from lost_owning_controller()
#16789enhancementclosedDon't launch downloads directly from routerlist_retry_directory_downloads()
#16826defectnewAdd a mechanism to allow callgraph generator to find vtbl-like constructions
#17218enhancementclosedMove most of "circuit_mark_for_close" into "circuit_free" or "circuit_close_all_marked".
#19328defectclosedTry not to log from inside functions called from inside log functions
#19329defectassignedIntegrate callgraph complexity measures into our regular process

Change History (20)

comment:1 Changed 4 years ago by nickm

Updated to include all branches written so far. With these, we're at 93 items in the blob, down from ~450 in March.

The remaining functions in the blob will be:

['append_cell_to_circuit_queue',
 'authority_certs_fetch_missing',
 'cell_queues_check_size',
 'channel_connect',
 'channel_connect_for_circuit',
 'channel_tls_connect',
 'circuit_build_failed',
 'circuit_deliver_create_cell',
 'circuit_discard_optional_exit_enclaves',
 'circuit_establish_circuit',
 'circuit_extend_to_new_exit',
 'circuit_get_open_circ_or_launch',
 'circuit_handle_first_hop',
 'circuit_has_opened',
 'circuit_launch_by_extend_info',
 'circuit_mark_for_close_',
 'circuit_package_relay_cell',
 'circuit_send_next_onion_skin',
 'circuit_testing_opened',
 'circuit_try_attaching_streams',
 'circuits_handle_oom',
 'connection_ap_attach_pending',
 'connection_ap_fail_onehop',
 'connection_ap_handshake_attach_chosen_circuit',
 'connection_ap_handshake_attach_circuit',
 'connection_ap_handshake_send_begin',
 'connection_ap_handshake_send_resolve',
 'connection_ap_handshake_socks_reply',
 'connection_ap_handshake_socks_resolved',
 'connection_ap_make_link',
 'connection_control_closed',
 'connection_dir_bridge_routerdesc_failed',
 'connection_dir_download_cert_failed',
 'connection_dir_request_failed',
 'connection_dir_retry_bridges',
 'connection_edge_destroy',
 'connection_edge_package_raw_inbuf',
 'connection_edge_send_command',
 'connection_free',
 'connection_mark_unattached_ap_',
 'connection_or_connect',
 'connection_or_finished_connecting',
 'connection_or_launch_v3_or_handshake',
 'connection_or_send_versions',
 'connection_or_write_var_cell_to_buf',
 'connection_proxy_connect',
 'connection_tls_continue_handshake',
 'connection_tls_finish_handshake',
 'connection_tls_start_handshake',
 'connection_write_to_buf',
 'connection_write_to_buf_impl_',
 'consider_plaintext_ports',
 'consider_testing_reachability',
 'directory_get_from_dirserver',
 'directory_get_from_hs_dir',
 'directory_initiate_command',
 'directory_initiate_command_rend',
 'directory_initiate_command_routerstatus',
 'directory_initiate_command_routerstatus_rend',
 'directory_send_command',
 'fetch_v2_desc_by_addr',
 'fetch_v2_desc_by_descid',
 'initiate_descriptor_downloads',
 'launch_descriptor_downloads',
 'launch_direct_bridge_descriptor_fetch',
 'launch_dummy_descriptor_download_as_needed',
 'networkstatus_consensus_download_failed',
 'pathbias_check_close',
 'pathbias_send_usable_probe',
 'relay_send_command_from_edge_',
 'rend_client_desc_trynow',
 'rend_client_fetch_v2_desc',
 'rend_client_introcirc_has_opened',
 'rend_client_reextend_intro_circuit',
 'rend_client_refetch_v2_renddesc',
 'rend_client_rendcirc_has_opened',
 'rend_client_report_intro_point_failure',
 'rend_client_send_establish_rendezvous',
 'rend_client_send_introduction',
 'rend_service_del_ephemeral',
 'rend_service_intro_has_opened',
 'rend_service_relaunch_rendezvous',
 'rend_service_rendezvous_has_opened',
 'retry_bridge_descriptor_fetch_directly',
 'router_perform_bandwidth_test',
 'routerlist_retry_directory_downloads',
 'update_all_descriptor_downloads',
 'update_certificate_downloads',
 'update_consensus_networkstatus_downloads',
 'update_consensus_router_descriptor_downloads',
 'update_microdesc_downloads',
 'update_networkstatus_downloads',
 'update_router_descriptor_downloads']

In addition to the tickets currently open, these seem like promising areas to try removing a single call dependency on. Each of them would remove the stated number of functions from the largest SCC:

[(4,
  'rend_client_fetch_v2_desc',
  'called by',
  'rend_client_refetch_v2_renddesc'),
 (4,
  'retry_bridge_descriptor_fetch_directly',
  'called by',
  'connection_dir_retry_bridges'),
 (5, 'cell_queues_check_size', 'called by', 'append_cell_to_circuit_queue'),
 (5, 'circuit_build_failed', 'called by', 'circuit_mark_for_close_'),
 (5, 'circuits_handle_oom', 'called by', 'cell_queues_check_size'),
 (5,
  'initiate_descriptor_downloads',
  'called by',
  'launch_descriptor_downloads'),
 (6,
  'connection_or_write_var_cell_to_buf',
  'called by',
  'connection_or_send_versions'),
 (6,
  'connection_tls_continue_handshake',
  'called by',
  'connection_tls_start_handshake'),
 (6,
  'connection_tls_start_handshake',
  'called by',
  'connection_or_finished_connecting'),
 (7,
  'connection_dir_request_failed',
  'called by',
  'directory_initiate_command_rend'),
 (7,
  'update_all_descriptor_downloads',
  'called by',
  'routerlist_retry_directory_downloads'),
 (8,
  'connection_or_finished_connecting',
  'called by',
  'connection_or_connect'),
 (9,
  'routerlist_retry_directory_downloads',
  'called by',
  'circuit_get_open_circ_or_launch'),
 (12, 'channel_connect', 'called by', 'channel_connect_for_circuit'),
 (12, 'channel_connect_for_circuit', 'called by', 'circuit_handle_first_hop'),
 (12, 'channel_tls_connect', 'called by', 'channel_connect'),
 (12, 'connection_or_connect', 'called by', 'channel_tls_connect'),
 (13, 'circuit_handle_first_hop', 'called by', 'circuit_establish_circuit'),
 (14,
  'circuit_establish_circuit',
  'called by',
  'circuit_launch_by_extend_info'),
 (18, 'connection_write_to_buf_impl_', 'called by', 'connection_write_to_buf')]

And these are the functions which (after the currently open tickets are applied) which pull the most other functions into the largest SCC.

 (7, 'rend_client_refetch_v2_renddesc'),
 (7, 'update_all_descriptor_downloads'),
 (8, 'connection_or_finished_connecting'),
 (8, 'directory_get_from_dirserver'),
 (9, 'routerlist_retry_directory_downloads'),
 (10, 'circuit_get_open_circ_or_launch'),
 (10, 'circuit_has_opened'),
 (12, 'channel_connect'),
 (12, 'channel_connect_for_circuit'),
 (12, 'channel_tls_connect'),
 (12, 'connection_or_connect'),
 (13, 'circuit_handle_first_hop'),
 (14, 'circuit_establish_circuit'),
 (16, 'circuit_launch_by_extend_info'),
 (18, 'connection_ap_handshake_attach_circuit'),
 (18, 'connection_write_to_buf'),
 (18, 'connection_write_to_buf_impl_'),
 (30, 'directory_initiate_command_rend'),
 (46, 'circuit_mark_for_close_')]
Last edited 4 years ago by nickm (previous) (diff)

comment:2 Changed 4 years ago by nickm

Milestone: Tor: 0.2.7.x-finalTor: 0.2.8.x-final

comment:3 Changed 4 years ago by nickm

Keywords: 028-triage added

comment:4 Changed 4 years ago by nickm

Keywords: SponsorS removed
Sponsor: SponsorS

Bulk-replace SponsorS keyword with SponsorS sponsor field in Tor component.

comment:5 Changed 4 years ago by nickm

Points: medium/large

comment:6 Changed 4 years ago by nickm

Milestone: Tor: 0.2.8.x-finalTor: 0.2.9.x-final

Deferring these two to 0.2.9; we have already made big progress in simplifying the Blob.

comment:7 Changed 3 years ago by isabela

Sponsor: SponsorSSponsorS-can

comment:8 Changed 3 years ago by nickm

Priority: MediumHigh

comment:9 Changed 3 years ago by nickm

Owner: set to nickm
Status: newaccepted

comment:10 Changed 3 years ago by nickm

Keywords: tor-modularity added

comment:11 Changed 3 years ago by isabela

Points: medium/large4.5

comment:12 Changed 3 years ago by nickm

Points: 4.5parent
Severity: Normal

comment:13 Changed 3 years ago by nickm

Owner: nickm deleted
Status: acceptedassigned

comment:14 Changed 3 years ago by nickm

Status: assignednew

Put all unowned "assigned" tickets back into "new".

comment:15 Changed 3 years ago by nickm

Milestone: Tor: 0.2.9.x-finalTor: 0.2.???

This is very largely done. The blob is tiny now. Dropping this from 0.2.9.

comment:16 Changed 3 years ago by teor

Milestone: Tor: 0.2.???Tor: 0.3.???

Milestone renamed

comment:17 Changed 3 years ago by nickm

Keywords: tor-03-unspecified-201612 added
Milestone: Tor: 0.3.???Tor: unspecified

Finally admitting that 0.3.??? was a euphemism for Tor: unspecified all along.

comment:18 Changed 2 years ago by nickm

Keywords: tor-03-unspecified-201612 removed

Remove an old triaging keyword.

comment:19 Changed 2 years ago by nickm

Keywords: 028-triage removed

comment:20 Changed 2 years ago by nickm

Keywords: callgraph technical-debt added
Note: See TracTickets for help on using tickets.