From 38b4406b046fb794322e948fd77cc1cbf28baa25 Mon Sep 17 00:00:00 2001 From: David Blacka Date: Wed, 11 Jun 2008 01:36:06 -0400 Subject: [PATCH] Allow netblocks to be used in CIDR indexes. Netblocks can now be used as CIDR indexes. Also, CidrMemIndex.find_subnets() now uses a set to avoid returning duplicate objects. Update the README and setup.py in preparation for the next release. --- README | 13 ++-- rwhoisd/MemDB.py | 2 +- rwhoisd/MemIndex.py | 153 +++++++++++++++++++++++++++------------ sample_data/example_data | 12 +++ setup.py | 3 +- 5 files changed, 130 insertions(+), 53 deletions(-) diff --git a/README b/README index bc781a4..e5bd075 100644 --- a/README +++ b/README @@ -15,12 +15,12 @@ Ending a IP or CIDR query with a single "*" will result in a REQUIREMENTS -python 2.2 or later +python 2.4 or later INSTALL -This can be run from it's source directory, which is the preferable -way to do it. +This can be run from it's source directory, which is a fine way to do +it. However, if you wish to install it, as root: @@ -38,9 +38,9 @@ RUNNING IT This is assuming that you are running it from the distribution directory. -% tar zxvf python-rwhoisd-0.1.tar.gz +% tar zxvf python-rwhoisd-0.4.tar.gz -% cd python-rwhoisd-0.1 +% cd python-rwhoisd-0.4 % ./bin/pyrwhoisd sample_data/example_schema \ sample_data/example_data & @@ -76,6 +76,9 @@ following differences, however: * This server does not support attribute "aliases". +* It doesn't quite support indexing network blocks (i.e., values like + "10.1.42.0 - 10.1.42.255"). + It should be noted that this server in small ways violates the description put forth by RFC 2167. In particular, it does not establish independent schemas for each authority area. There may be diff --git a/rwhoisd/MemDB.py b/rwhoisd/MemDB.py index e1da0c1..1cde736 100644 --- a/rwhoisd/MemDB.py +++ b/rwhoisd/MemDB.py @@ -157,7 +157,7 @@ class MemDB: def index_data(self): """Prepare the indexes for searching. Currently, this isn't strictly necessary (the indexes will prepare themselves when - necessary), but it should elminate a penalty on initial + necessary), but it should eliminate a penalty on initial searches""" for i in self.indexes.values(): diff --git a/rwhoisd/MemIndex.py b/rwhoisd/MemIndex.py index 996ef42..88a6cf0 100644 --- a/rwhoisd/MemIndex.py +++ b/rwhoisd/MemIndex.py @@ -36,7 +36,7 @@ class MemIndex: # use of objects (like Cidr) as keys in favor of a primitive type. # In the Cidr case, we would either have to use longs or strings, # as Python doesn't seem to have an unsigned 32-bit integer type. - + def __init__(self): self.index = [] self.sorted = False @@ -100,7 +100,7 @@ class MemIndex: def _find(self, key): """Return the (search_element, index) tuple. Used internally only.""" - + self.prepare() search_el = element(key, None) i = bisect.bisect_left(self.index, search_el) @@ -131,32 +131,70 @@ class CidrMemIndex(MemIndex): # NOTE: this structure lends to fairly efficient exact searches # (O[log2N]), efficient subnet searches (also O[log2N]), but not - # terribly efficient supernet searches (O[32 * log2N]), because we - # have to potentially do 32 exact matches. If we want efficient - # supernet searches, we will probably have to use some sort of - # general (i.e., not binary) search tree datastructure, as there - # is no sorted ordering that will efficiently give supernets that - # I can think of. + # terribly efficient supernet searches (O[32 * log2N] or O[128 * + # log2N] for IPv6), because we have to potentially do 32 (or 128!) + # exact matches. If we want efficient supernet searches, we will + # probably have to use some sort of general (i.e., not binary) + # search tree datastructure, as there is no sorted ordering that + # will efficiently give supernets that I can think of. + + # convert a key, value pair into a list of (cidr, value) tuples. + # It can be a list with more than one element if key is actually a + # netblock. + def _conv_key_value(self, key, value): + res = [] + if isinstance(key, Cidr.Cidr): + res.append((key, value)) + return res + if self.is_netblock(key): + cidrs = self.parse_netblock(key) + for c in cidrs: + res.append((c, value)) + else: + c = Cidr.valid_cidr(key) + res.append((c, value)) + return res + + # convert a (key, value) tuple into a list of (cidr, value) + # tuples. + def _conv_tuple(self, tuple): + return self._conv_key_value(tuple[0], tuple[1]) def add(self, key, value=None): if isinstance(key, types.TupleType): - MemIndex.add(self, (Cidr.valid_cidr(key[0]), key[1]), value) + l = self._conv_tuple(key) else: - MemIndex.add(self, Cidr.valid_cidr(key), value) + l = self._conv_key_value(key, value) + + for k, v in l: + MemIndex.add(self, k, v) return def addlist(self, list): + res_list = [] # make sure the keys are Cidr objects for i in list: if isinstance(i, types.TupleType): - i = (Cidr.valid_cidr(el[0]), el[1]) + l = self._conv_tuple(i) elif isinstance(el, element): - i.key = Cidr.valid_cidr(i.key) - - MemIndex.addlist(self, list) + l = self._conv_key_value(i.key, i.value) + res_list.append(l) + + MemIndex.addlist(self, res_list) return - + + def is_netblock(self, key): + if "-" in key: return True + return False + + def parse_netblock(self, key): + start, end = key.split("-", 1); + start = start.strip() + end = end.strip() + + return Cidr.netblock_to_cidr(start, end) + def find_exact(self, key, max = 0): key = Cidr.valid_cidr(key) @@ -167,7 +205,7 @@ class CidrMemIndex(MemIndex): if max and len(res) == max: break i += 1 return res - + def find_subnets(self, key, max = 0): """Return all values that are subnets of 'key', including any that match 'key' itself.""" @@ -175,12 +213,12 @@ class CidrMemIndex(MemIndex): key = Cidr.valid_cidr(key) search_el, i = self._find(key) - res = [] + res = set() while i < len(self.index) and self.index[i].key.is_subnet(key): if max and len(res) == max: break - res.append(self.index[i].value) + res.add(self.index[i].value) i += 1 - return res + return list(res) def find_supernets(self, key, max = 0): """Return all values that are supernets of 'key', including @@ -196,7 +234,7 @@ class CidrMemIndex(MemIndex): return res[:max] k.netlen -= 1 - + return res def find(self, key, prefix_match=0, max=0): @@ -207,7 +245,7 @@ class CidrMemIndex(MemIndex): key = Cidr.valid_cidr(key) if prefix_match == 0: res = self.find_exact(key, max) - + if not res: # now do a modified supernet search that stops after # the first proper supernet, but gets all values @@ -219,7 +257,7 @@ class CidrMemIndex(MemIndex): res = self.find_exact(k, max) k.netlen -= 1 return res - + # for now, a prefix match means all supernets return self.find_supernets(key, max) @@ -228,7 +266,7 @@ class ComboMemIndex: index and a CIDR index. Valid CIDR values we be applied against the CIDR index. Other values will be applied against the normal index.""" - + def __init__(self): self.normal_index = MemIndex() self.cidr_index = CidrMemIndex() @@ -236,7 +274,7 @@ class ComboMemIndex: def add(self, key, value = None): """Add a key,value pair to the correct map. See MemIndex for the behavior of this method""" - + if isinstance(key, types.TupleType): k = key[0] else: @@ -251,16 +289,16 @@ class ComboMemIndex: def addlist(self, list): """Add a list of elements or key, value tuples to the appropriate maps.""" - + cidr_list = [] normal_list = [] - + for i in list: if isinstance(i, element): k, v = i.key, i.value elif isinstance(i, types.TupleType): k, v = i[:2] - + c = Cidr.valid_cidr(k) if c: cidr_list.append((c, v)) @@ -300,7 +338,7 @@ class ComboMemIndex: """If 'key' is a CIDR value (either a Cidr object or a valid CIDR string representation, do a find_subnets on the internal CidrMemIndex, otherwise return None.""" - + c = Cidr.valid_cidr(key) if c: return self.cidr_index.find_subnets(key, max) return None @@ -313,11 +351,11 @@ class ComboMemIndex: c = Cidr.valid_cidr(key) if c: return self.cidr_index.find_supernets(key, max) return None - + class element: """This is the base element class. It basically exists to simplify sorting.""" - + def __init__(self, key, value): self.key = key self.value = value @@ -338,7 +376,7 @@ class element: def __repr__(self): return "element" + str(self) - + def __hash__(self): return self.key.__hash__() @@ -381,38 +419,61 @@ if __name__ == "__main__": ci = CidrMemIndex() - ci.add(Cidr.Cidr("127.0.0.1/24"), "net-local-1"); - ci.add(Cidr.Cidr("127.0.0.1/32"), "net-local-2"); - ci.add(Cidr.Cidr("216.168.224.0", 22), "net-vrsn-1") - ci.add(Cidr.Cidr("216.168.252.1", 32), "net-vrsn-2") - ci.add(Cidr.Cidr("24.36.191.0/24"), "net-foo-c") - ci.add(Cidr.Cidr("24.36.191.32/27"), "net-foo-sub-c") - ci.add(Cidr.Cidr("24.36/16"), "net-foo-b") + ci.add("127.0.0.1/24", "net-local-1"); + ci.add("127.0.0.1/32", "net-local-2"); + ci.add(Cidr.Cidr.create("216.168.224.0", 22), "net-vrsn-1") + ci.add(Cidr.Cidr.create("216.168.252.1", 32), "net-vrsn-2") + ci.add("24.36.191.0/24", "net-foo-c") + ci.add("24.36.191.32/27", "net-foo-sub-c") + ci.add("24.36/16", "net-foo-b") + ci.add("3ffe:4:5::0/48", "net-foo-d6") + ci.add("3ffe:4:5:6::0/64", "net-foo-e6") + ci.add("48.12.6.0 - 48.12.6.95", "net-bar-1") print "finding exactly 127.0.0.0/24" - res = ci.find(Cidr.Cidr("127.0.0.0/24")) + res = ci.find(Cidr.Cidr.create("127.0.0.0/24")) print res print "finding exactly 127.0.0.16/32" - res = ci.find(Cidr.Cidr("127.0.0.16/32")) + res = ci.find(Cidr.Cidr.create("127.0.0.16/32")) + print res + + print "finding exactly 3ffe:4:5:6::0/64" + res = ci.find(Cidr.valid_cidr("3ffe:4:5:6::/64")) print res print "finding supernets of 127.0.0.16/32" - res = ci.find_supernets(Cidr.Cidr("127.0.0.16/32")) + res = ci.find_supernets(Cidr.Cidr.create("127.0.0.16/32")) print res - + print "finding supernets of 24.36.191.32/27" - res = ci.find(Cidr.Cidr("24.36.191.32/27"), 1) + res = ci.find(Cidr.Cidr.create("24.36.191.32/27"), 1) print res print "finding supernets of 24.36.191.33/27" - res = ci.find_supernets(Cidr.Cidr("24.36.191.33/27")) + res = ci.find_supernets(Cidr.Cidr.create("24.36.191.33/27")) print res print "finding supernets of 24.36.191.64/27" - res = ci.find_supernets(Cidr.Cidr("24.36.191.64/27")) + res = ci.find_supernets(Cidr.Cidr.create("24.36.191.64/27")) + print res + + print "finding supernets of 3ffe:4:5:6:7::0/80" + res = ci.find_supernets(Cidr.valid_cidr("3ffe:4:5:6:7::0/80")) + print res + + print "finding supernets of 48.12.6.90" + res = ci.find_supernets(Cidr.valid_cidr("48.12.6.90")) print res print "finding subnets of 127.0/16" - res = ci.find_subnets(Cidr.Cidr("127.0/16")) + res = ci.find_subnets(Cidr.Cidr.create("127.0/16")) + print res + + print "finding subnets of 3ffe:4::0/32" + res = ci.find_subnets(Cidr.valid_cidr("3ffe:4::0/32")) + print res + + print "finding subnets of 48.12.0.0/16" + res = ci.find_subnets(Cidr.valid_cidr("48.12.0.0/16")) print res diff --git a/sample_data/example_data b/sample_data/example_data index 79667e9..2b49200 100644 --- a/sample_data/example_data +++ b/sample_data/example_data @@ -22,6 +22,18 @@ Created: 19961022 Updated: 19961023 Updated-By: hostmaster@a.com +ID: VRSN-BLOCK-7-V6.a.com +Class-Name: network +Auth-Area: a.com +IP-Network: 2001:503:a83e::0/48 +Network-Name: VRSN-BLOCK-7-V6 +Organization: 777.a.com +Tech-Contact: 222.a.com +Admin-Contact: 222.a.com +Created: 20040315 +Updated: 20050704 +Updated-By: hostmaster@a.com + ID:333.a.com Auth-Area:a.com Class-Name: domain diff --git a/setup.py b/setup.py index 39cf03a..7f98e10 100644 --- a/setup.py +++ b/setup.py @@ -4,10 +4,11 @@ from distutils.core import setup import os setup(name="python-rwhoisd", - version="0.2", + version="0.4", description="A lightweight RWhois server written in Python", author="David Blacka", author_email="david@blacka.com", + url="http://blacka.com/software/python-rwhoisd", packages=['rwhoisd'], scripts=['bin/'+x for x in os.listdir('bin') if os.path.isfile('bin/'+x)], -- 2.36.6