[tor-bugs] #11595 [Tor]: Use smarter data structures for keeping track of circuit IDs per channel

[Tor Bug Tracker & Wiki]

#11595: Use smarter data structures for keeping track of circuit IDs per channel
-------------------------+------------------------------------
 Reporter:  andrea       |          Owner:
     Type:  enhancement  |         Status:  new
 Priority:  normal       |      Milestone:  Tor: 0.2.6.x-final
Component:  Tor          |        Version:  Tor: 0.2.5.3-alpha
 Keywords:               |  Actual Points:
Parent ID:               |         Points:
-------------------------+------------------------------------
 In 0.2.4 and 0.2.5, we use a hash table mapping (channel_t *, circid_t)
 pairs to circuit_t * to look up circuits; see
 circuit_get_by_circid_channel_impl() in circuitlist.c.  Prior to 0.2.4, we
 did something similar but with orconns rather than channels.  In #11553,
 we introduced a random circuit ID selection which can fail if the space of
 circuit IDs is nearly full; this is preferable to the old linear-time
 search, but still not as good as a deterministic solution without false
 positive exhaustion detection would be.

 If we used a balanced tree (AVL tree, red/black tree, anything along those
 lines) augmented at each node with a count of the total nodes in the
 subtree rooted at that node, we could still do all the operations we
 currently use the hash table for in deterministic log time, but we could
 also easily pick a uniformly distributed random unused circuit id in
 deterministic log time by picking a random integer x in the range [0,
 max_circ_id - n_circ_ids_used), and then walk down the tree to where the
 node for that newly allocated circuit id should be, using the node counts
 to add the number of used circuit ids less than x at each step.

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