[tor-bugs] #30291 [Core Tor/Tor]: Optimize our path selection code

[Tor Bug Tracker & Wiki]

#30291: Optimize our path selection code
-------------------------------------------------+-------------------------
 Reporter:  dgoulet                              |          Owner:  (none)
     Type:  enhancement                          |         Status:  new
 Priority:  Medium                               |      Milestone:  Tor:
                                                 |  unspecified
Component:  Core Tor/Tor                         |        Version:
 Severity:  Normal                               |     Resolution:
 Keywords:  tor-performance tor-hs path-         |  Actual Points:
  selection refactoring tor-dos                  |
Parent ID:  #30221                               |         Points:  10
 Reviewer:                                       |        Sponsor:
                                                 |  Sponsor27-can
-------------------------------------------------+-------------------------

Comment (by dgoulet):

 Performance Update! Now that both child tickets have been merged, here is
 the new profile offenders:

 {{{
 -   12.54%  tor      tor                    [.] tor_addr_is_null
    - tor_addr_is_null
       - 8.59% tor_addr_is_valid
          - 7.80% node_get_pref_ipv6_orport
             + 7.80% nodelist_add_node_and_family
          + 0.79% bridge_exists_with_ipv6_addr_and_port
       - 3.94% addrs_in_same_network_family
          - 3.94% nodelist_add_node_and_family
               build_middle_exclude_list
               choose_good_middle_server
               onion_extend_cpath
               onion_populate_cpath
               circuit_establish_circuit
             + circuit_launch_by_extend_info
 +    8.43%  tor      tor                    [.] curve25519_donna
 -    6.20%  tor      tor                    [.]
 microdesc_has_curve25519_onion_key
      microdesc_has_curve25519_onion_key
    - node_get_curve25519_onion_key
       - 6.20% node_has_curve25519_onion_key
          - 3.11% router_add_running_nodes_to_smartlist
             - router_choose_random_node
                + 3.10% choose_good_middle_server
          - 3.09% count_acceptable_nodes.isra.2
               new_route_len
               onion_pick_cpath_exit
               circuit_establish_circuit
             + circuit_launch_by_extend_info
 +    5.13%  tor      libc-2.24.so           [.] 0x0000000000145533
 -    4.04%  tor      tor                    [.] node_get_prim_orport
    - node_get_prim_orport
       - 4.04% node_get_addr
          - 4.04% nodelist_add_node_and_family
               build_middle_exclude_list
               choose_good_middle_server
               onion_extend_cpath
               onion_populate_cpath
               circuit_establish_circuit
             + circuit_launch_by_extend_info
 }}}

 To summarize the above, it appears that we spend a lot of times in
 `nodelist_add_node_and_family()` doing some address validation during our
 path selection.

 Then we do check a lot of memories with `tor_mem_is_zero()` within the
 `node_get_curve25519_onion_key()` that basically use it to figure out if
 the key is set or not.

 Overall, to give an idea of the rest of the profile, majority is spent
 looking at IP addresses... It appears we basically only do that during
 path selection with a bit of "getting the bw weight" ;):

 {{{
 +    3.80%  tor      tor                    [.] tor_addr_family.isra.1
 +    3.44%  tor      tor                    [.] tor_addr_compare_masked
 +    3.02%  tor      tor                    [.]
 addrs_in_same_network_family
 +    2.57%  tor      tor                    [.] node_get_pref_ipv6_orport
 +    2.42%  tor      tor                    [.] tor_addr_copy
 +    2.27%  tor      tor                    [.] tor_addr_is_valid
 +    2.10%  tor      tor                    [.] tor_addr_to_ipv4n.isra.0
 +    1.93%  tor      tor                    [.]
 node_is_a_configured_bridge
 +    1.86%  tor      tor                    [.]
 compute_weighted_bandwidths
 +    1.71%  tor      tor                    [.] tor_mem_is_zero
 +    1.71%  tor      tor                    [.] tor_port_is_valid
 +    1.46%  tor      tor                    [.] tor_addr_is_valid_ipv4n
 +    1.30%  tor      tor                    [.]
 bridge_exists_with_ipv4h_addr_and_port
 +    1.25%  tor      tor                    [.] tor_addr_from_ipv4n
 +    1.13%  tor      tor                    [.]
 node_has_preferred_descriptor
 +    1.13%  tor      tor                    [.] tor_addr_to_in6_assert
 +    1.10%  tor      tor                    [.] __bswap_32
 +    1.09%  tor      tor                    [.] tor_addr_to_ipv4h
 +    1.07%  tor      tor                    [.]
 get_configured_bridge_by_addr_port_digest
 ...
 }}}

 These almost all comes from within `nodelist_add_node_and_family()`.

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/30291#comment:5>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online