[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[tor-bugs] #11595 [Tor]: Use smarter data structures for keeping track of circuit IDs per channel
#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
_______________________________________________
tor-bugs mailing list
tor-bugs@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs