[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

[or-cvs] r15137: Implement code to force handing out a minimum number of ORs (in bridgedb/trunk: . lib/bridgedb)



Author: nickm
Date: 2008-06-11 16:07:48 -0400 (Wed, 11 Jun 2008)
New Revision: 15137

Modified:
   bridgedb/trunk/bridgedb.conf
   bridgedb/trunk/lib/bridgedb/Bridges.py
   bridgedb/trunk/lib/bridgedb/Dist.py
   bridgedb/trunk/lib/bridgedb/Main.py
   bridgedb/trunk/lib/bridgedb/Tests.py
Log:
Implement code to force handing out a minimum number of ORs with a given ORPort from a given ring, if possible (will not give good results until the number of such bridges is over the number of rings).  Also, initial support for IP categories, usable for proxy selection.

Modified: bridgedb/trunk/bridgedb.conf
===================================================================
--- bridgedb/trunk/bridgedb.conf	2008-06-11 19:59:01 UTC (rev 15136)
+++ bridgedb/trunk/bridgedb.conf	2008-06-11 20:07:48 UTC (rev 15137)
@@ -33,6 +33,10 @@
 # How many clusters do we group IPs in when distributing bridges based on IP?
 N_IP_CLUSTERS = 4
 
+# If possible, always give a certain number of answers with a given ORPort.
+# This is a list of (port,minimum) tuples.
+FORCE_PORTS = [ (443, 1) ]
+
 #==========
 # Options related to HTTPS
 

Modified: bridgedb/trunk/lib/bridgedb/Bridges.py
===================================================================
--- bridgedb/trunk/lib/bridgedb/Bridges.py	2008-06-11 19:59:01 UTC (rev 15136)
+++ bridgedb/trunk/lib/bridgedb/Bridges.py	2008-06-11 20:07:48 UTC (rev 15137)
@@ -204,6 +204,18 @@
     def assignmentsArePersistent(self):
         return True
 
+class BridgeRingParameters:
+    """DOCDOC"""
+    def __init__(self, needPorts=()):
+        """DOCDOC takes list of port, count"""
+        for port,count in needPorts:
+            if not (1 <= port <= 65535):
+                raise TypeError("Port %s out of range."%port)
+            if count <= 0:
+                raise TypeError("Count %s out of range."%count)
+
+        self.needPorts = needPorts[:]
+
 class BridgeRing(BridgeHolder):
     """Arranges bridges in a ring based on an hmac function."""
     ## Fields:
@@ -212,28 +224,48 @@
     ##   isSorted: true iff sortedKeys is currently sorted.
     ##   sortedKeys: a list of all the hmacs, in order.
     ##   name: a string to represent this ring in the logs.
-    def __init__(self, key):
+    def __init__(self, key, answerParameters=None):
         """Create a new BridgeRing, using key as its hmac key."""
         self.bridges = {}
         self.bridgesByID = {}
         self.hmac = get_hmac_fn(key, hex=False)
         self.isSorted = False
         self.sortedKeys = []
-        self.name = "Ring"
+        if answerParameters is None:
+            answerParameters = BridgeRingParameters()
+        self.answerParameters = answerParameters
 
+        self.portSubrings = [] #DOCDOC
+        for port,count in self.answerParameters.needPorts:
+            #note that we really need to use the same key here, so that
+            # the mapping is in the same order for all subrings.
+            self.portSubrings.append( (port,count,BridgeRing(key,None)) )
+
+        self.setName("Ring")
+
+    def setName(self, name):
+        """DOCDOC"""
+        self.name = name
+        for port,_,subring in self.portSubrings:
+            subring.setName("%s (port-%s subring)"%(name, port))
+
     def __len__(self):
         return len(self.bridges)
 
     def insert(self, bridge):
         """Add a bridge to the ring.  If the bridge is already there,
            replace the old one."""
+        for port,_,subring in self.portSubrings:
+            if port == bridge.orport:
+                subring.insert(bridge)
+
         ident = bridge.getID()
         pos = self.hmac(ident)
         if not self.bridges.has_key(pos):
             self.sortedKeys.append(pos)
             self.isSorted = False
         self.bridges[pos] = bridge
-        self.bridgesByID[id] = bridge
+        self.bridgesByID[ident] = bridge
         logging.debug("Adding %s to %s", bridge.getConfigLine(), self.name)
 
     def _sort(self):
@@ -260,16 +292,30 @@
 
     def getBridges(self, pos, N=1):
         """Return the N bridges appearing in the ring after position pos"""
-        keys = self._getBridgeKeysAt(pos, N)
+        forced = []
+        for _,count,subring in self.portSubrings:
+            if len(subring) < count:
+                count = len.subring
+            forced.extend(subring._getBridgeKeysAt(pos, count))
+
+        keys = forced[:]
+        for k in self._getBridgeKeysAt(pos, N):
+            if k not in forced:
+                keys.append(k)
+        keys = keys[:N]
         keys.sort()
         return [ self.bridges[k] for k in keys ]
 
     def getBridgeByID(self, fp):
         """Return the bridge whose identity digest is fp, or None if no such
            bridge exists."""
+        for _,_,subring in self.portSubrings:
+            b = subring.getBridgeByID(fp)
+            if b is not None:
+                return b
+
         return self.bridgesByID.get(fp)
 
-
 class LogDB:
     """Wraps a database object and records all modifications to a
        human-readable logfile."""

Modified: bridgedb/trunk/lib/bridgedb/Dist.py
===================================================================
--- bridgedb/trunk/lib/bridgedb/Dist.py	2008-06-11 19:59:01 UTC (rev 15136)
+++ bridgedb/trunk/lib/bridgedb/Dist.py	2008-06-11 20:07:48 UTC (rev 15137)
@@ -33,17 +33,31 @@
     ##        rings of this distributor.
     ##    areaOrderHmac -- an hmac function used to order areas within rings.
     ##    areaClusterHmac -- an hmac function used to assign areas to rings.
-    def __init__(self, areaMapper, nClusters, key):
+    def __init__(self, areaMapper, nClusters, key, ipCategories=(),
+                 answerParameters=None):
         self.areaMapper = areaMapper
 
         self.rings = []
+        self.categoryRings = [] #DOCDDOC
+        self.categories = [] #DOCDOC
         for n in xrange(nClusters):
             key1 = bridgedb.Bridges.get_hmac(key, "Order-Bridges-In-Ring-%d"%n)
-            self.rings.append( bridgedb.Bridges.BridgeRing(key1) )
-            self.rings[-1].name = "IP ring %s"%len(self.rings)
+            self.rings.append( bridgedb.Bridges.BridgeRing(key1,
+                                                           answerParameters) )
+            self.rings[-1].setName("IP ring %s"%len(self.rings))
+        n = nClusters
+        for c in ipCategories:
+            key1 = bridgedb.Bridges.get_hmac(key, "Order-Bridges-In-Ring-%d"%n)
+            ring = bridgedb.Bridges.BridgeRing(key1, answerParameters)
+            self.categoryRings.append( ring )
+            self.categoryRings[-1].setName(
+                "IP category ring %s"%len(self.categoryRings))
+            self.categories.append( (c, ring) )
+            n += 1
 
         key2 = bridgedb.Bridges.get_hmac(key, "Assign-Bridges-To-Rings")
-        self.splitter = bridgedb.Bridges.FixedBridgeSplitter(key2, self.rings)
+        self.splitter = bridgedb.Bridges.FixedBridgeSplitter(key2,
+                                       self.rings+self.categoryRings)
 
         key3 = bridgedb.Bridges.get_hmac(key, "Order-Areas-In-Rings")
         self.areaOrderHmac = bridgedb.Bridges.get_hmac_fn(key3, hex=False)
@@ -67,6 +81,11 @@
 
         area = self.areaMapper(ip)
 
+        for category, ring in self.categories:
+            if category.contains(ip):
+                pos = self.areaOrderHmac("category<%s>%s"%(epoch,area))
+                return ring.getBridges(pos, N)
+
         # Which bridge cluster should we look at?
         h = int( self.areaClusterHmac(area)[:8], 16)
         clusterNum = h % len(self.rings)
@@ -183,12 +202,13 @@
     ##   store -- a database object to remember what we've given to whom.
     ##   domainmap -- a map from lowercase domains that we support mail from
     ##       to their canonical forms.
-    def __init__(self, key, store, domainmap, domainrules):
+    def __init__(self, key, store, domainmap, domainrules,
+                 answerParameters=None):
         key1 = bridgedb.Bridges.get_hmac(key, "Map-Addresses-To-Ring")
         self.emailHmac = bridgedb.Bridges.get_hmac_fn(key1, hex=False)
 
         key2 = bridgedb.Bridges.get_hmac(key, "Order-Bridges-In-Ring")
-        self.ring = bridgedb.Bridges.BridgeRing(key2)
+        self.ring = bridgedb.Bridges.BridgeRing(key2, answerParameters)
         self.ring.name = "email ring"
         # XXXX clear the store when the period rolls over!
         self.store = store
@@ -199,7 +219,7 @@
         """Assign a bridge to this distributor."""
         self.ring.insert(bridge)
 
-    def getBridgesForEmail(self, emailaddress, epoch, N=1):
+    def getBridgesForEmail(self, emailaddress, epoch, N=1, parameters=None):
         """Return a list of bridges to give to a user.
            emailaddress -- the user's email address, as given in a from line.
            epoch -- the time period when we got this request.  This can
@@ -226,7 +246,7 @@
             return result
 
         pos = self.emailHmac("<%s>%s" % (epoch, emailaddress))
-        result = self.ring.getBridges(pos, N)
+        result = self.ring.getBridges(pos, N, parameters)
         memo = "".join(b.getID() for b in result)
         self.store[emailaddress] = memo
         return result

Modified: bridgedb/trunk/lib/bridgedb/Main.py
===================================================================
--- bridgedb/trunk/lib/bridgedb/Main.py	2008-06-11 19:59:01 UTC (rev 15136)
+++ bridgedb/trunk/lib/bridgedb/Main.py	2008-06-11 20:07:48 UTC (rev 15137)
@@ -43,6 +43,8 @@
     N_IP_CLUSTERS = 4,
     MASTER_KEY_FILE = "./secret_key",
 
+    REQUIRE_ORPORTS = [(443, 1)],
+
     HTTPS_DIST = True,
     HTTPS_SHARE=10,
     HTTPS_BIND_IP=None,
@@ -181,13 +183,18 @@
     splitter = Bridges.BridgeSplitter(Bridges.get_hmac(key, "Splitter-Key"),
                                       Bridges.PrefixStore(store, "sp|"))
 
+    # Create ring parameters.
+    forcePorts = getattr(cfg, "FORCE_PORTS")
+    ringParams=Bridges.BridgeRingParameters(forcePorts=forcePorts)
+
     emailDistributor = ipDistributor = None
     # As appropriate, create an IP-based distributor.
     if cfg.HTTPS_DIST and cfg.HTTPS_SHARE:
         ipDistributor = Dist.IPBasedDistributor(
             Dist.uniformMap,
             cfg.N_IP_CLUSTERS,
-            Bridges.get_hmac(key, "HTTPS-IP-Dist-Key"))
+            Bridges.get_hmac(key, "HTTPS-IP-Dist-Key"),
+            answerParameters=ringParams)
         splitter.addRing(ipDistributor, "https", cfg.HTTPS_SHARE)
         webSchedule = Time.IntervalSchedule("day", 2)
 
@@ -199,7 +206,8 @@
             Bridges.get_hmac(key, "Email-Dist-Key"),
             Bridges.PrefixStore(store, "em|"),
             cfg.EMAIL_DOMAIN_MAP.copy(),
-            cfg.EMAIL_DOMAIN_RULES.copy())
+            cfg.EMAIL_DOMAIN_RULES.copy(),
+            answerParameters=ringParams)
         splitter.addRing(emailDistributor, "email", cfg.EMAIL_SHARE)
         emailSchedule = Time.IntervalSchedule("day", 1)
 

Modified: bridgedb/trunk/lib/bridgedb/Tests.py
===================================================================
--- bridgedb/trunk/lib/bridgedb/Tests.py	2008-06-11 19:59:01 UTC (rev 15136)
+++ bridgedb/trunk/lib/bridgedb/Tests.py	2008-06-11 20:07:48 UTC (rev 15137)
@@ -5,6 +5,7 @@
 import doctest
 import unittest
 import warnings
+import random
 
 import bridgedb.Bridges
 import bridgedb.Main
@@ -18,11 +19,70 @@
     def testFooIsFooish(self):
         self.assert_(True)
 
+def randomIP():
+    return ".".join([str(random.randrange(1,256)) for _ in xrange(4)])
+
+def fakeBridge(orport=8080):
+    nn = "bridge-%s"%random.randrange(0,1000000)
+    ip = randomIP()
+    fp = "".join([random.choice("0123456789ABCDEF") for _ in xrange(40)])
+    return bridgedb.Bridges.Bridge(nn,ip,orport,fingerprint=fp)
+
+class RhymesWith255Category:
+    def contains(self, ip):
+        return ip.endswith(".255")
+
+class IPBridgeDistTests(unittest.TestCase):
+    def dumbAreaMapper(self, ip):
+        return ip
+    def testBasicDist(self):
+        d = bridgedb.Dist.IPBasedDistributor(self.dumbAreaMapper, 3, "Foo")
+        for _ in xrange(256):
+            d.insert(fakeBridge())
+        n = d.getBridgesForIP("1.2.3.4", "x", 2)
+        n2 = d.getBridgesForIP("1.2.3.4", "x", 2)
+        self.assertEquals(n, n2)
+
+    def testDistWithCategories(self):
+        d = bridgedb.Dist.IPBasedDistributor(self.dumbAreaMapper, 3, "Foo",
+                                             [RhymesWith255Category()])
+        assert len(d.categoryRings) == 1
+        rhymesWith255Ring = d.categoryRings[0]
+        for _ in xrange(256):
+            d.insert(fakeBridge())
+        # Make sure this IP doesn't get any rhymes-with-255 bridges
+        n = d.getBridgesForIP("1.2.3.4", "x", 10)
+        for b in n:
+            self.assertFalse(b.getID() in rhymesWith255Ring.bridgesByID)
+
+        # Make sure these IPs all get rhymes-with-255 bridges
+        for ip in ("6.7.8.255", "10.10.10.255"):
+            n = d.getBridgesForIP("1.2.3.255", "xyz", 10)
+            for b in n:
+                self.assertTrue(b.getID() in rhymesWith255Ring.bridgesByID)
+
+    def testDistWithPortRestrictions(self):
+        param = bridgedb.Bridges.BridgeRingParameters(needPorts=[(443, 1)])
+        d = bridgedb.Dist.IPBasedDistributor(self.dumbAreaMapper, 3, "Baz",
+                                             answerParameters=param)
+        for _ in xrange(32):
+            d.insert(fakeBridge(443))
+        for _ in range(256):
+            d.insert(fakeBridge())
+        for _ in xrange(16):
+            i = randomIP()
+            n = d.getBridgesForIP(i, "x", 2)
+            count = 0
+            for b in n:
+                if b.orport == 443:
+                    count += 1
+            self.assertTrue(count >= 1)
+
 def testSuite():
     suite = unittest.TestSuite()
     loader = unittest.TestLoader()
 
-    for klass in [ TestCase0 ]:
+    for klass in [ TestCase0, IPBridgeDistTests ]:
         suite.addTest(loader.loadTestsFromTestCase(klass))
 
     for module in [ bridgedb.Bridges,