[tor-bugs] #7571 [Tor]: Make AutomapHostsOnResolve work with IPv6

[Tor Bug Tracker & Wiki]

#7571: Make AutomapHostsOnResolve work with IPv6
-------------------------+--------------------------------------------------
 Reporter:  nickm        |          Owner:                    
     Type:  enhancement  |         Status:  needs_review      
 Priority:  normal       |      Milestone:  Tor: 0.2.4.x-final
Component:  Tor          |        Version:                    
 Keywords:               |         Parent:                    
   Points:               |   Actualpoints:                    
-------------------------+--------------------------------------------------

Comment(by andrea):

 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.

-- 
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/7571#comment:4>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online