Opened 6 years ago

Last modified 3 years ago

#11595 new enhancement

Use smarter data structures for keeping track of circuit IDs per channel

Reported by: andrea Owned by:
Priority: Low Milestone: Tor: unspecified
Component: Core Tor/Tor Version: Tor: 0.2.5.3-alpha
Severity: Normal Keywords: tor-relay data-structure maybe-not-good-idea
Cc: Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

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.

Child Tickets

Change History (6)

comment:1 Changed 6 years ago by nickm

See also #7749, which suggests (in a vague single-sentence form) a similar approach for keeping track of unused virtual addresses.

comment:2 Changed 5 years ago by nickm

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

comment:3 Changed 3 years ago by teor

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

Milestone renamed

comment:4 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:5 Changed 3 years ago by nickm

Keywords: tor-03-unspecified-201612 removed

Remove an old triaging keyword.

comment:6 Changed 3 years ago by nickm

Keywords: tor-relay data-structure maybe-not-good-idea added
Priority: MediumLow
Severity: Normal

It's not 100% clear to me that this solves a problem which it's important to solve. If we can make circuit lookup _faster_, though, that would rule.

Note: See TracTickets for help on using tickets.