Faster implementation for circuit_get_by_rend_token_and_purpose()

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.

changed milestone to %Tor: 0.2.5.x-final

added 024-backport 025-triaged component::core tor/tor easy milestone::Tor: 0.2.5.x-final priority::medium resolution::fixed status::closed tor-hs tor-relay type::defect labels

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.

Trac:
Keywords: tor-relay tor-hs deleted, tor-relay tor-hs easy added
Status: new to needs_revision

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 (moved), which I'll close as a dup.

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.

Trac:
Status: needs_revision to needs_review

Trac:
Keywords: tor-relay tor-hs easy deleted, 025-triaged, tor-hs, easy, tor-relay added

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

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

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.

Trac:
Milestone: Tor: 0.2.5.x-final to Tor: 0.2.4.x-final
Keywords: 025-triaged deleted, 025-triaged 024-backport added

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

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

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

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

Trac:
Milestone: Tor: 0.2.4.x-final to Tor: 0.2.5.x-final
Status: needs_review to closed
Resolution: N/A to fixed

closed

mentioned in issue #11332 (moved)

moved to tpo/core/tor#9841 (closed)

mentioned in issue tpo/core/tor#11332 (closed)