Opened 5 years ago

Closed 5 years ago

#9841 closed defect (fixed)

Faster implementation for circuit_get_by_rend_token_and_purpose()

Reported by: nickm Owned by:
Priority: Medium Milestone: Tor: 0.2.5.x-final
Component: Core Tor/Tor Version:
Severity: Keywords: tor-relay, tor-hs, easy, 025-triaged 024-backport
Cc: Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

According to https://lists.torproject.org/pipermail/tor-relays/2013-September/002715.html , https://lists.torproject.org/pipermail/tor-relays/2013-September/002715.html can be 6% of a relay's runtime.

This is another function that does a linear search when a hashtable lookup would be more appropriate.

We'll need to be a little careful, since there's nothing preventing collisions here: An intro circuit and a rendezvous circuit can have the same "token" pretty easily.

Child Tickets

Change History (11)

comment:1 Changed 5 years ago by nickm

Keywords: easy added
Status: newneeds_revision

There's an untested branch "bug9841_024" in my public repository that uses a digestmap of linked lists to organize circuits. It needs testing and documentation, however.

Also, I'm not convinced that the approach is a very good one. We could instead just do two digestmaps: one for intro circuits and one for rendezvous circuits. We'd need to forbid there to be two simultaneous open circuits with the same intropoint pk digest, or two simultaneous open circuits with the same rendezvous cookie, but that's probably a fine thing to forbid.

comment:2 Changed 5 years ago by nickm

Looks like I did this once before, in a branch called "rend_token_map". So probably both are worth reviewing to see which is more advanced. That one needed tests; it was for #7764, which I'll close as a dup.

comment:3 Changed 5 years ago by nickm

Status: needs_revisionneeds_review

Okay, I revised it. The branches to consider are "bug9841_024_v2" and "bug9841_025". The latter contains the former merged to 0.2.5, plus a unit test.

I changed it to stop using a linked list, and instead use two maps as discussed above. We should merge this into 0.2.5 at least; I'm ambivalent about an 0.2.4 backport.

comment:4 Changed 5 years ago by nickm

Keywords: 025-triaged added

comment:5 Changed 5 years ago by nickm

IIUC Andrea told me this is good to merge according to her, but it should maybe have a warning on rendezvous cookie collision.

comment:6 Changed 5 years ago by nickm

I've been stress-testing it a little and found an assertion-failure bug. Both branches are updated. More tests to follow.

comment:7 Changed 5 years ago by nickm

Keywords: 024-backport added
Milestone: Tor: 0.2.5.x-finalTor: 0.2.4.x-final

okay, I think we shook all the bugs out. Merging to master.

I did the original branch here against 0.2.4, but now I am not so sure that a backport is appropriate. Nonetheless, putting it in the 0.2.4 milestone for consideration.

comment:8 Changed 5 years ago by nickm

The unit tests had a bug in them; see #11460.

comment:9 Changed 5 years ago by nickm

Recommendation: no backport; is a speedup. (But is helping all hidden services everywhere go faster not worth it?)

comment:10 Changed 5 years ago by arma

No backport. I look forward to the grand future when 0.2.5 relays are faster. (The future is now.)

comment:11 Changed 5 years ago by nickm

Milestone: Tor: 0.2.4.x-finalTor: 0.2.5.x-final
Resolution: fixed
Status: needs_reviewclosed

Okay, no backport to 0.2.4 for these, for stability reasons.

Note: See TracTickets for help on using tickets.