Make AutomapHostsOnResolve work with IPv6
Since IPv6 addresses are infinite[*], it'd be a good idea to support automapping to them. In fact, we should automap to them by default when possible.
This is orthogonal to actual client use of IPv6 addresses.
[*] For very small values of infinity.
Activity
changed milestone to %Tor: 0.2.4.x-final
Please review branch prop205-simplified_automap in my public repository. It is based on prop205-simplified, the branch for #7570 (moved), since they touch a lot of similar code. I've also fixed some other automaphostsonresolve annoyances there: the resulting addresses are now randomized to avoid collisions between Tor runs, and the maximum attempts is clipped down to a more plausible value than UINT32_MAX.
Trac:
Status: new to needs_reviewOther concern: letting 'attempts' be UINT32_MAX for picking random IPv6 addresses. Assuming almost all addresses are free is plausible given the huge address space of IPv6, but to be sure the expectation value of the number of attempts needed is small (i.e., O(log(n)) in the address space size at worst), you also need to assume the random number generator is well behaved, especially in terms of correlations between successive bytes. With a linear congruential generator in particular, this can fail horribly due to Marsaglia's Theorem, making the effective reachable address space much smaller and hence much more densely occupied.
Now, I know lots and lots of other things would break if crypto_rand() were that bad and I sure as hell hope it's never an LCG, but is crypto_rand() actually under our control? I think if for some horrible, messed-up reason it turns out to be a really terrible not-at-all-crypto-grade PRNG, the manifestation of this probably should not be addressmap_get_virtual_address() inexplicably hanging after an apparently-small number of addresses have been mapped or something bizarre like that.
Further thought on the random numbers issue: there's a deterministic O(log(n)) way to do this that doesn't depend strongly on the properties of the PRNG. We keep track of all the addresses we've already assigned already (we have to, to be able to test whether one we've picked is available), and for that to be an acceptably efficient algorithm the test better take O(log(n)), so we already have some data structure complexity there. Why not just select some data structure that lets us efficiently skip over the already assigned addresses? Then pick uniformly distributed random numbers x in the range 0 <= x < max_address - assigned_addresses, and, at a conceptual level, we want to (efficiently) compute the following:
1.) Let S_i for i from 0 to max_address - assigned_addresses - 1 be the set of all unassigned addresses in numerical order. 2.) Pick S_x
Then this is clearly a uniformly distributed random selection of an unallocated address, which we can always choose with only one attempt. It remains only to show that we can efficiently compute S_x.
Now, we have N assigned addresses S_0 through S_(N-1), and N+1 (possibly empty) intervals I_0 through I_N, with I_i = {x in Z | S_(i-1) <= x < S_i}, mutatis mutandis for I_0 and I_N - that is, implicitly S_(-1) = 0 and S_N = max_addr. The problem is then to determine which of the intervals I_i that S_x falls in, and the offset within that interval corresponding to the chosen address.
The offset is easy enough: let C_j be the count of unassigned addresses in I_j (that is, C_j = S_j - 1 - S_(j-1), mutatis mutandis for C_0 and C_N), and then the offset of S_x in I_i is just x adjusted by the C_j of all preceding intervals:
S_x = S_(i-1) + (x - sum(C_j for 0 <= j < i))
By assumption that S_x falls in I_i, we must have 0 <= (x - sum(C_j for 0 <= j < i)) < S_i - S_(i-1). If we picked too large a value of i this will be negative and for too small a value it will be past S_i - S_(i-1). Thus, if nothing else, we could learn i efficiently by binary search given an efficient way of computing sum(C_j for 0 <= j < i). Fortunately, this is easy: keep the assigned addresses in a balanced tree (we need a data structure of some sort to test for assignedness anyway), and in addition to the assigned address S_i used as the sort key at each node, keep the count of assigned nodes in the subtree below that node (which will be easy to update on tree rotations when rebalancing). Then, the number of assigned addresses <= S_i is just 1 + count(left subtree at S_i) and so the number of unassigned addresses <= S_i (that is, sum(C_j for 0 <= j < i)) is just S_i - (1 + count(left subtree at S_i)).
This could be done by binary search in O(log(N)) queries on the tree of cost O(log(N)), for a total time complexity of O(log^2(N)), but we can just as easily walk down the tree evaluating x - sum(C_j for 0 <= j < i) and comparing to 0 and S_i - S_(i-1) as long as we can get S_(i-1) in constant time (that is, each node must have a prev pointer as well as left/right subtrees), use that to decide whether to pick this interval or move to the left or right subtree, and thus determine the correct I_i in O(log(N)).
It's kind of a lot of implementation complexity and I'd be satisfied with just "we're really confident the expected number of attempts for the existing algorithm is at worst O(log(N))", but just pointing out that it can be done in deterministic O(log(N)) with only one random number per address selection and without strong assumptions about the properties of the PRNG.
Replying to andrea:
Hmmm - I have two concerns here. Simpler one first:
- Why the loopback by default for IPv4 but link-local for IPv6? Is assuming we can use a whole /8 on the loopback portable? I had a vague impression that the loopback device acting like that is a Linuxism.
As I understand it, IPv6 has exactly one loopback address, not a whole loopback netblock like IPv4.
As for the data structure,
addressmapis astrmap_t, which is a hash table.See [http://www.chiark.greenend.org.uk/~sgtatham/algorithms/] for implementations of some relevant data structures (either Cumulative frequency tables for an extra data structure to maintain alongside the hash table or Counted B-trees for a data structure to replace the hash table).
Alternatively, someone could implement a crit-bit tree.
See also [http://code.dogmap.org./kart/] for some ways to use crit-bit trees.
-
Why the loopback by default for IPv4 but link-local for IPv6?
rransom is right -- there's only one loopback address for IPv6.
Other concern: letting 'attempts' be UINT32_MAX for picking random IPv6 addresses.
I believe that later in the branch (c50bb9e3), I reduced it to 1000.
Is crypto_rand() actually under our control?
The crypto_rand() function uses OpenSSL's cryptographic PRNG. If that's broken (like when Debian broke theirs), or replaced with an LCG or something, all OpenSSL users on that platform will be almost totally insecure, and an infinite loop in addressmap_get_virtual_address() would be the least of our worries ;)
My inner perfectionist likes the idea of using crit-bit trees, but I'm having a hard time constructing a reasonable scenario where 1000 isn't a big enough number here. If that turns out to be wrong, though, we shouldn't forget this stuff: maybe we should add a comment or another ticket about it.
-
There's now a combined "ticket7570_7571" branch that has a squashed and rebased version of this code plus the code in #7570 (moved). I'm going to merge that if there are no objections.
-
I've merged the branch, and added a ticket (#7749 (moved)) for the "use a better algorithm" issue.
Trac:
Status: needs_review to closed
Resolution: N/A to implemented mentioned in issue #7749 (moved)
moved to tpo/core/tor#7571 (closed)
mentioned in issue tpo/core/tor#7749 (closed)