channel_rsa_id_group_set_badness spends a lot of time in malloc/free

[Hello71]

in particular, a very large proportion (~25%) of allocations made seem to be "temporary", i.e. an allocation is made and then freed before any other allocations are made. possibly a portion of these are due to the second loop, but I was wondering if it is possible that the function is called with an empty list, and if that is a problem.

regardless, I have written a patch to use ht instead of only smartlists, which should very slightly increase the memory usage and moderately decrease the CPU usage in this function.

[Hello71]

hm... annoyingly, this patch only seems to reduce the allocations from 30% to 25%, and that's probably noise. I will investigate whether this API can be changed to be more efficient.

[Hello71]

fixed patch to actually add the first element to the set. still wondering if this function truly needs to be called every single second.

[Hello71]

I think this patch finally actually does the same work as the other one, just faster.

[Hello71]

I think this one is even better, but given that the first one took me about six tries, this one is probably wrong too.

[Hello71]

so I realised that we can just avoid all allocations in the vastly more common case that there is only one ed25519 identity for an rsa id group. 0001-Add-fast-paths-to-channel_rsa_id_group_set_badness.patch does this first step. 0002-Simplify-channel_rsa_id_group_set_badness-24119.patch​ applied on top additionally rewrites the nested loop into a sort and a single loop. performance is probably better with huge n, but with the small numbers we are likely to have here, it's really between which one is simpler. I think mine is, but that might just be because I've spent several days staring at it.

tl;dr pls review and apply 0001-Add-fast-paths-to-channel_rsa_id_group_set_badness.patch, 0002-Simplify-channel_rsa_id_group_set_badness-24119.patch​ is probably nice to have but not needed

[nickm]

setting owner. (We'll take a look at this once review-group-24 is done and review-group-25 is open.)

[nickm]

On the first patch: I think connection_or_expire_ should probably have a name more like connection_or_mark_bad_if_too_old or connection_or_set_singleton_badness or something ? The current name makes it sound like it always expires the connection.

On the second patch: First, please don't use memcmp() directly. Use one of the aliases or function in di_ops.h instead.

I think there's a bug on the loop in your second patch: connection_or_group_set_badness_ will get called on every Ed25519 ID except for the last one.

[Hello71]

​https://cgit.alxu.ca/tor.git/log/?h=bug24119 resolves the problems. I don't know if you agree about fast_memcmp here, but there seem to be similar uses in other sorting helpers. also I dunno about the underscore here, because this part seems to already be back and forth between connections and channels.

[isis]

Calling this a Sponsor8 because resource consumption effects mobile; feel free to change if there's a better sponsor.

[nickm]

Creating review-group-26.

[nickm]

Hi, and sorry about the delay!

I've fixed a few things I noticed in a new branch, bug24119, in my public repository (​https://git.torproject.org/nickm/tor.git). How does this look to you?

[nickm]

I think this is ready to merge, if you agree with the changes.

[Hello71]

lgtm. (I wonder if ed25519_pubkey_eq could safely use fast_memcmp... although it doesn't really matter here)

[Hello71]

I think that would be correct if all callers ensure that either side channels are (effectively) unobservable, such as in these background tasks, or that the foreign party has proved that it owns the private key for this public key. the former doesn't apply everywhere, and the latter sounds nearly impossible to ensure.

tl;dr lgtm, ignore part about ed25519_pubkey_eq in previous comment

[Hello71]

https://trac.torproject.org/projects/tor/wiki/org/sponsors/Sponsor8 says it is Android, but this change affects only nodes with many channels open, mainly participating nodes (relays, directories, etc). clients are unlikely to have this type of load, and mobile clients especially so.

[nickm]

Okay; squashed and merged to master!