Opened 3 years ago

Last modified 8 months ago

#25152 needs_information defect

Try to call less circuitmux_find_map_entry()

Reported by: dgoulet Owned by:
Priority: Medium Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: performance, tor-relay, 034-triage-20180328, 034-removed-20180328, 035-deferred-20180930, 040-deferred-201915
Cc: neel@… Actual Points:
Parent ID: Points:
Reviewer: Sponsor:


The circuitmux_find_map_entry() function is currently taking more than 3% of the CPU on a busy relay. It is literally the second highest after curv25519 crypto stuff (which is expected to be high).

We can't really optimize that function so much but we can try to call it less! For instance, at every single cell we append to a circuit in append_cell_to_circuit_queue() we call update_circuit_on_cmux() which calls *4* functions in succession that calls circuitmux_find_map_entry():

  • circuitmux_is_circuit_attached()
  • circuitmux_attached_circuit_direction()
  • circuitmux_set_num_cells() and this function can call it again with circuitmux_make_circuit_inactive() or circuitmux_make_circuit_active().

This is quite a lot of CPU at _each_ cell especially when we do have many many circuits.

Child Tickets

Change History (16)

comment:1 Changed 3 years ago by nickm

Keywords: 034-triage-20180328 added; removed

comment:2 Changed 3 years ago by nickm

Keywords: 034-removed-20180328 added

Per our triage process, these tickets are pending removal from 0.3.4.

comment:3 Changed 3 years ago by nickm

Milestone: Tor: 0.3.4.x-finalTor: unspecified

These tickets, tagged with 034-removed-*, are no longer in-scope for 0.3.4. We can reconsider any of them, if time permits.

comment:4 Changed 2 years ago by neel

Owner: set to neel
Status: newassigned

comment:5 Changed 2 years ago by neel

Cc: neel@… added

comment:7 Changed 2 years ago by nickm

Milestone: Tor: unspecifiedTor: 0.3.5.x-final
Status: assignedneeds_review

comment:8 Changed 2 years ago by asn

Reviewer: mikeperry

comment:9 Changed 2 years ago by nickm

I've left a review on the PR; Mike is planning to do so as well.

In general, I think that the approach is a good start, but that a more thorough approach might be called for in order to keep the code clean. I'm not sure it's a good idea to proliferate these "hashent" usages throughout our codebase, I'd like to take a step back.

Before we optimize too much we should ask ourselves, "Is this hashtable really necessary?" After all, there are at most two of these hash entries for each circuit, and we are looking them up _from_ the circuit. Perhaps a better solution would be to give each circuit a couple of pointers to this information, to make lookup into an O(1) operation. Maybe after we were done, we might find that the hashtable wasn't necessary at all.

Of course, we would need to manage lifetime issues carefully here.

I am not taking a position about whether the change I suggest above should be done instead of or after this change; I would like a second opinion from mike about that -- and ideally from dgoulet too, once he is back online.

comment:10 Changed 2 years ago by dgoulet

Status: needs_reviewneeds_information

I 100% agree with nickm...

A while back, when I was working on KIST with pastly, we realized that much of the cmux subsystem is quite complex and could be simplify drastically. I even did Dia diagram to try to make sense of it all and came up with a design to address the complexities.

So there is an argument to be made to try to revive all my notes in a Ticket and address the overall issue instead of patching things here and there.

We have no sponsor or roadmap slots for this afaict but if it is out there, great volunteers like neel can go at it :). I'll try to find an evening soon and sum up it all up in a ticket. In the meantime, I recommend we keep that ticket on hold until we decide if overhauling is what should be done or if we should merge this as a temporary band aid before bigger work.

comment:11 Changed 2 years ago by nickm

Keywords: 035-deferred-20180930 added
Milestone: Tor: 0.3.5.x-finalTor: 0.3.6.x-final

Deferring several items from 0.3.5. I think these are features, not bugfixes, and therefore no longer great for 0.3.5. Please let me know if I'm wrong.

comment:12 Changed 2 years ago by nickm

Milestone: Tor: 0.3.6.x-finalTor: 0.4.0.x-final

Tor 0.3.6.x has been renamed to 0.4.0.x.

comment:13 Changed 22 months ago by nickm

Keywords: 040-deferred-201915 added
Milestone: Tor: 0.4.0.x-finalTor: unspecified

Deferring some tickets from 0.4.0 without proposing them for later. Please tag with 041-proposed if you want to do them.

comment:14 Changed 18 months ago by neel

Owner: neel deleted
Status: needs_informationassigned

comment:15 Changed 18 months ago by neel

Status: assignedneeds_information

comment:16 Changed 8 months ago by gaba

Reviewer: mikeperry

Remove MikePerry from reviewer from all this old tickets.

Note: See TracTickets for help on using tickets.