Store family lists more efficiently

Looking at the analysis, our storage for family lists accounted for 1.3MB out of 24.9MB total allocation. That's around 5% of our total allocation, not counting malloc overhead.

Fortunately, this will be pretty easy to fix.

changed milestone to %Tor: 0.4.0.x-final in legacy/trac

added 035-roadmap-master in Legacy / Trac 035-triaged-in-20180711 in Legacy / Trac actualpoints::3 in Legacy / Trac component::core tor/tor in Legacy / Trac milestone::Tor: 0.4.0.x-final in Legacy / Trac owner::nickm in Legacy / Trac parent::27243 in Legacy / Trac priority::medium in Legacy / Trac resolution::implemented in Legacy / Trac reviewer::teor in Legacy / Trac severity::normal in Legacy / Trac sponsor::8-can in Legacy / Trac status::closed in Legacy / Trac type::defect in Legacy / Trac labels

I've got an untested, undocumented, unintegrated sketch design in a branch called ticket27359. It needs to get tested, documented, and integrated with microdesc. (maybe someday it could get integrated with routerdesc -- but that wouldn't work for authorities yet.)

Trac:
Milestone: Tor: 0.3.5.x-final to Tor: 0.3.6.x-final

Trac:
Sponsor: N/A to Sponsor8-can

Trac:
Status: new to accepted
Owner: N/A to nickm

So the idea of the scheme here is to encode families in a more compact representation: roughly, as a sorted array of 21-byte elements, where each element is a one byte tag, and 20 bytes of either a sha1 ID or a nickname. These objects are reference-counted, so that they can be shared by relays with the same family members.

To optimize the number of family objects that are shared by multiple relays, I want to add each relay's hex ID to its own family -- doing this will make all the relays in the same family have the same encoded family. (It's harmless to consider a relay a member of its own family.)

I've run into a few issues with this, and I'm not sure which of them need to be solved pre-merge, and how.

1. A small number of relays specify invalid hex IDs in their family lines -- typically, with the wrong number of hex digits.

2. A small number of relays use the $hexid=nickname syntax, which can't be encoded in the manner above, and which is probably not what they want anyway.

3. Authorities need to process family lines exactly as they are received, and rely on a lossless encoding of their inputs.

4. When parsing a microdescriptor, we do not know which relay it is associated with, so we can't easily add its own ID to its family when parsing it. (Further, it is in theory possible for two misconfigured relays to wind up with the same microdescriptor, I think.)

I'm not sure quite what to do about each of these issues.

After conversation with teor, here's what we're thinking:

1. Ignore any malformed family entries
2. Treat $hexid=nickname as if it just said $hexid.
3. Don't use this trick outside of parsed microdescriptors, since that's what clients need.
4. Add a new consensus method to canonicalize family lists by adding each node's own identity and sorting the entries.

For future work (TODO, make tickets)

1. Also do the same canonicalization in ns consensus documents
2. Deprecate $foo=bar and $foo~bar
3. Relays should warn if they are about to publish an invalid hexid in their family line.
4. Relays should canonicalize their own family lines

Replying to nickm:

... 4. Add a new consensus method to canonicalize family lists by adding each node's own identity and sorting the entries.

Looking at the available microdescs, we should also:

• uppercase the hex ids

It's also worth noting;:

• chutney doesn't set MyFamily, so we'll need to test carefully
• this change likely causes:
  • a slight increase in the size of descriptors on disk (from the extra ids), offset by removing =nick and malformed hex id, and
  • a slight decrease of compressed descriptor size, because the sorted lines are identical

1. Also do the same canonicalization in ns consensus documents

fwiw, I don't think ns consensus documents include family lines?

See branch ticket27359_v2, with PR at https://github.com/torproject/tor/pull/463

Trac:
Actualpoints: N/A to 2
Status: accepted to needs_review

Replying to nickm:

1. Also do the same canonicalization in ns consensus documents

fwiw, I don't think ns consensus documents include family lines?

Yes, you're right, family only appears in descriptors.

Trac:
Reviewer: N/A to teor

I did a review, looks good, except for a case-comparison bug.

Trac:
Status: needs_review to needs_revision

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

Trac:
Milestone: Tor: 0.3.6.x-final to Tor: 0.4.0.x-final

I've resolved the bug, and added a bunch of tests. Do you like the test coverage now?

Trac:
Status: needs_revision to needs_review

Looks good to me.

Let's defer the routerinfo / microdesc decision until later.

Trac:
Status: needs_review to merge_ready

Thanks! Squashed and merged!

Trac:
Status: merge_ready to closed
Resolution: N/A to implemented
Actualpoints: 2 to 3