Your message dated Sat, 23 Feb 2013 14:33:14 +0100 with message-id <20130223133314.GQ5761@radis.cristau.org> and subject line Re: Bug#699900: unblock: nsd3/3.2.12-2 has caused the Debian Bug report #699900, regarding unblock: nsd3/3.2.12-2 to be marked as done. This means that you claim that the problem has been dealt with. If this is not the case it is now your responsibility to reopen the Bug report if necessary, and/or fix the problem forthwith. (NB: If you are a system administrator and have no idea what this message is talking about, this may indicate a serious mail system misconfiguration somewhere. Please contact owner@bugs.debian.org immediately.) -- 699900: http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=699900 Debian Bug Tracking System Contact owner@bugs.debian.org with problems
--- Begin Message ---
- To: Debian Bug Tracking System <submit@bugs.debian.org>
- Subject: unblock: nsd3/3.2.12-2
- From: Ondřej Surý <ondrej@debian.org>
- Date: Wed, 06 Feb 2013 14:32:02 +0100
- Message-id: <20130206133202.19885.99478.reportbug@localhost6.localdomain6>
Package: release.debian.org Severity: normal User: release.debian.org@packages.debian.org Usertags: unblock Please unblock package nsd3 Hi, please unblock nsd3 3.2.12-2 which includes Response Rate Limiting. Unfortunatelly the DDoSes on DNS infrastructure are very common right now and even though the patch is quite big I think it needs to go in. The patch has been provided directly by upstream, and although they have declared it's unsupported there have been so few changes between 3.2.12 and 3.2.15 (other than this diff) that I think it's quite safe to apply this patch. I will of course monitor new upstream versions and cherry-pick fixes if there's the need. Ondrej Here comes the debdiff explained: $ diffstat nsd3_3.2.12-2.debdiff .gitattributes | 1 # cruft changelog | 7 control | 3 # add autoconf, automake and autotools-dev patches/0005-Force-dbdir-to-be-var-lib-nsd3-by-patching-configure.patch | 4 # quilt refresh patches/0006-define_MAXHOSTNAMELEN_for_hurd_build.patch | 2 # quilt refresh patches/0009-nsd-3.2.12-rrl.patch | 2452 ++++++++++ # Response Rate Limiting patch provided by upstream patches/series | 1 rules | 4 # add autoreconf -fi and --enable-ratelimit 8 files changed, 2469 insertions(+), 5 deletions(-) unblock nsd3/3.2.12-2 -- System Information: Debian Release: 7.0 APT prefers testing APT policy: (500, 'testing') Architecture: amd64 (x86_64) Kernel: Linux 3.2.0-3-amd64 (SMP w/4 CPU cores) Locale: LANG=en_US.UTF-8, LC_CTYPE=en_US.UTF-8 (charmap=UTF-8) Shell: /bin/sh linked to /bin/dashdiff -Nru nsd3-3.2.12/debian/changelog nsd3-3.2.12/debian/changelog --- nsd3-3.2.12/debian/changelog 2012-07-19 15:07:28.000000000 +0200 +++ nsd3-3.2.12/debian/changelog 2013-02-06 14:16:06.000000000 +0100 @@ -1,3 +1,10 @@ +nsd3 (3.2.12-2) unstable; urgency=low + + * Add Response Rate Limiting patch (Courtesy of Matthijs Mekking of NLnet Labs) + * Regenerate configure due to RRL patch and ./configure with --enable-ratelimit + + -- Ondřej Surý <ondrej@debian.org> Wed, 06 Feb 2013 14:09:36 +0100 + nsd3 (3.2.12-1) unstable; urgency=low * Imported Upstream version 3.2.12 diff -Nru nsd3-3.2.12/debian/control nsd3-3.2.12/debian/control --- nsd3-3.2.12/debian/control 2012-07-19 15:07:28.000000000 +0200 +++ nsd3-3.2.12/debian/control 2013-02-06 14:16:06.000000000 +0100 @@ -4,6 +4,9 @@ Maintainer: Ondřej Surý <ondrej@debian.org> Build-Depends: debhelper (>= 7.0.50~), dpkg-dev (>= 1.16.1.1~), + autoconf, + automake, + autotools-dev, bison, flex, libssl-dev diff -Nru nsd3-3.2.12/debian/.gitattributes nsd3-3.2.12/debian/.gitattributes --- nsd3-3.2.12/debian/.gitattributes 2012-07-19 15:07:28.000000000 +0200 +++ nsd3-3.2.12/debian/.gitattributes 1970-01-01 01:00:00.000000000 +0100 @@ -1 +0,0 @@ -changelog merge=merge-debchangelog diff -Nru nsd3-3.2.12/debian/patches/0005-Force-dbdir-to-be-var-lib-nsd3-by-patching-configure.patch nsd3-3.2.12/debian/patches/0005-Force-dbdir-to-be-var-lib-nsd3-by-patching-configure.patch --- nsd3-3.2.12/debian/patches/0005-Force-dbdir-to-be-var-lib-nsd3-by-patching-configure.patch 2012-07-19 15:07:28.000000000 +0200 +++ nsd3-3.2.12/debian/patches/0005-Force-dbdir-to-be-var-lib-nsd3-by-patching-configure.patch 2013-02-06 14:16:06.000000000 +0100 @@ -13,7 +13,7 @@ --- a/configure +++ b/configure -@@ -3585,7 +3585,7 @@ logfile=${localstatedir}/log/nsd.log +@@ -3603,7 +3603,7 @@ logfile=${localstatedir}/log/nsd.log # # Database directory # @@ -24,7 +24,7 @@ # Determine the pidfile location. Check if /var/run exists, if so set pidfile --- a/configure.ac +++ b/configure.ac -@@ -69,7 +69,7 @@ logfile=${localstatedir}/log/nsd.log +@@ -70,7 +70,7 @@ AC_SUBST(logfile) # # Database directory # diff -Nru nsd3-3.2.12/debian/patches/0006-define_MAXHOSTNAMELEN_for_hurd_build.patch nsd3-3.2.12/debian/patches/0006-define_MAXHOSTNAMELEN_for_hurd_build.patch --- nsd3-3.2.12/debian/patches/0006-define_MAXHOSTNAMELEN_for_hurd_build.patch 2012-07-19 15:07:28.000000000 +0200 +++ nsd3-3.2.12/debian/patches/0006-define_MAXHOSTNAMELEN_for_hurd_build.patch 2013-02-06 14:16:06.000000000 +0100 @@ -5,7 +5,7 @@ --- a/nsd.c +++ b/nsd.c -@@ -44,6 +44,10 @@ +@@ -45,6 +45,10 @@ #include "options.h" #include "tsig.h" diff -Nru nsd3-3.2.12/debian/patches/0009-nsd-3.2.12-rrl.patch nsd3-3.2.12/debian/patches/0009-nsd-3.2.12-rrl.patch --- nsd3-3.2.12/debian/patches/0009-nsd-3.2.12-rrl.patch 1970-01-01 01:00:00.000000000 +0100 +++ nsd3-3.2.12/debian/patches/0009-nsd-3.2.12-rrl.patch 2013-02-06 14:16:06.000000000 +0100 @@ -0,0 +1,2452 @@ +--- a/doc/ChangeLog ++++ b/doc/ChangeLog +@@ -1,3 +1,27 @@ ++29 January 2013: Matthijs ++ - RRL documented in nsd.conf.sample ++ ++18 January 2013: Wouter ++ - Fix spurious assertion in RRL for block. ++ ++4 December 2012: Wouter ++ - NSD-RRL documented in manpage. ++ ++28 November 2012: Wouter ++ - RRL implements classification type RRSIG. ++ ++21 November 2012: Wouter ++ - Implement rrl log of unblock for collision. ++ ++9 November 2012: Wouter ++ - Log when NSD-RRL stops a stream from being blocked. ++ ++1 November 2012: Wouter ++ - Fix default settings for rrl. ++ ++30 October 2012: Wouter ++ - --enable-ratelimit enables RRL code (ported from NSD4). ++ + 19 July 2012: Willem + - Fix for VU#624931 CVE-2012-2978: NSD denial of service + vulnerability from non-standard DNS packet from any host +--- a/doc/RELNOTES ++++ b/doc/RELNOTES +@@ -1,5 +1,12 @@ + NSD RELEASE NOTES + ++3.2.12-PATCH ++================ ++ ++FEATURES: ++ - RRL, --enable-ratelimit at configure time and config options. ++ ++ + 3.2.12 + ================ + +--- a/doc/README ++++ b/doc/README +@@ -178,6 +178,10 @@ addition to standard configure options, + This option could lead to a reduced service level and increased + memory footprint. + ++ --enable-ratelimit ++ ++ Enables ratelimiting, based on query name, type and source. ++ + --with-configdir=dir + + Specified, NSD configuration directory, default /etc/nsd +--- /dev/null ++++ b/lookup3.c +@@ -0,0 +1,1011 @@ ++/* ++ January 2012(Wouter) added randomised initial value, fallout from 28c3. ++ March 2007(Wouter) adapted from lookup3.c original, add config.h include. ++ added #ifdef VALGRIND to remove 298,384,660 'unused variable k8' warnings. ++ added include of lookup3.h to check definitions match declarations. ++ removed include of stdint - config.h takes care of platform independence. ++ url http://burtleburtle.net/bob/hash/index.html. ++*/ ++/* ++------------------------------------------------------------------------------- ++lookup3.c, by Bob Jenkins, May 2006, Public Domain. ++ ++These are functions for producing 32-bit hashes for hash table lookup. ++hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() ++are externally useful functions. Routines to test the hash are included ++if SELF_TEST is defined. You can use this free for any purpose. It's in ++the public domain. It has no warranty. ++ ++You probably want to use hashlittle(). hashlittle() and hashbig() ++hash byte arrays. hashlittle() is is faster than hashbig() on ++little-endian machines. Intel and AMD are little-endian machines. ++On second thought, you probably want hashlittle2(), which is identical to ++hashlittle() except it returns two 32-bit hashes for the price of one. ++You could implement hashbig2() if you wanted but I haven't bothered here. ++ ++If you want to find a hash of, say, exactly 7 integers, do ++ a = i1; b = i2; c = i3; ++ mix(a,b,c); ++ a += i4; b += i5; c += i6; ++ mix(a,b,c); ++ a += i7; ++ final(a,b,c); ++then use c as the hash value. If you have a variable length array of ++4-byte integers to hash, use hashword(). If you have a byte array (like ++a character string), use hashlittle(). If you have several byte arrays, or ++a mix of things, see the comments above hashlittle(). ++ ++Why is this so big? I read 12 bytes at a time into 3 4-byte integers, ++then mix those integers. This is fast (you can do a lot more thorough ++mixing with 12*3 instructions on 3 integers than you can with 3 instructions ++on 1 byte), but shoehorning those bytes into integers efficiently is messy. ++------------------------------------------------------------------------------- ++*/ ++/*#define SELF_TEST 1*/ ++ ++#include "config.h" ++#include "lookup3.h" ++#include <stdio.h> /* defines printf for tests */ ++#include <time.h> /* defines time_t for timings in the test */ ++/*#include <stdint.h> defines uint32_t etc (from config.h) */ ++#include <sys/param.h> /* attempt to define endianness */ ++#ifdef linux ++# include <endian.h> /* attempt to define endianness */ ++#endif ++ ++/* random initial value */ ++static uint32_t raninit = 0xdeadbeef; ++ ++void ++hash_set_raninit(uint32_t v) ++{ ++ raninit = v; ++} ++ ++/* ++ * My best guess at if you are big-endian or little-endian. This may ++ * need adjustment. ++ */ ++#if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \ ++ __BYTE_ORDER == __LITTLE_ENDIAN) || \ ++ (defined(i386) || defined(__i386__) || defined(__i486__) || \ ++ defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL)) ++# define HASH_LITTLE_ENDIAN 1 ++# define HASH_BIG_ENDIAN 0 ++#elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \ ++ __BYTE_ORDER == __BIG_ENDIAN) || \ ++ (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel)) ++# define HASH_LITTLE_ENDIAN 0 ++# define HASH_BIG_ENDIAN 1 ++#else ++# define HASH_LITTLE_ENDIAN 0 ++# define HASH_BIG_ENDIAN 0 ++#endif ++ ++#define hashsize(n) ((uint32_t)1<<(n)) ++#define hashmask(n) (hashsize(n)-1) ++#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) ++ ++/* ++------------------------------------------------------------------------------- ++mix -- mix 3 32-bit values reversibly. ++ ++This is reversible, so any information in (a,b,c) before mix() is ++still in (a,b,c) after mix(). ++ ++If four pairs of (a,b,c) inputs are run through mix(), or through ++mix() in reverse, there are at least 32 bits of the output that ++are sometimes the same for one pair and different for another pair. ++This was tested for: ++* pairs that differed by one bit, by two bits, in any combination ++ of top bits of (a,b,c), or in any combination of bottom bits of ++ (a,b,c). ++* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed ++ the output delta to a Gray code (a^(a>>1)) so a string of 1's (as ++ is commonly produced by subtraction) look like a single 1-bit ++ difference. ++* the base values were pseudorandom, all zero but one bit set, or ++ all zero plus a counter that starts at zero. ++ ++Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that ++satisfy this are ++ 4 6 8 16 19 4 ++ 9 15 3 18 27 15 ++ 14 9 3 7 17 3 ++Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing ++for "differ" defined as + with a one-bit base and a two-bit delta. I ++used http://burtleburtle.net/bob/hash/avalanche.html to choose ++the operations, constants, and arrangements of the variables. ++ ++This does not achieve avalanche. There are input bits of (a,b,c) ++that fail to affect some output bits of (a,b,c), especially of a. The ++most thoroughly mixed value is c, but it doesn't really even achieve ++avalanche in c. ++ ++This allows some parallelism. Read-after-writes are good at doubling ++the number of bits affected, so the goal of mixing pulls in the opposite ++direction as the goal of parallelism. I did what I could. Rotates ++seem to cost as much as shifts on every machine I could lay my hands ++on, and rotates are much kinder to the top and bottom bits, so I used ++rotates. ++------------------------------------------------------------------------------- ++*/ ++#define mix(a,b,c) \ ++{ \ ++ a -= c; a ^= rot(c, 4); c += b; \ ++ b -= a; b ^= rot(a, 6); a += c; \ ++ c -= b; c ^= rot(b, 8); b += a; \ ++ a -= c; a ^= rot(c,16); c += b; \ ++ b -= a; b ^= rot(a,19); a += c; \ ++ c -= b; c ^= rot(b, 4); b += a; \ ++} ++ ++/* ++------------------------------------------------------------------------------- ++final -- final mixing of 3 32-bit values (a,b,c) into c ++ ++Pairs of (a,b,c) values differing in only a few bits will usually ++produce values of c that look totally different. This was tested for ++* pairs that differed by one bit, by two bits, in any combination ++ of top bits of (a,b,c), or in any combination of bottom bits of ++ (a,b,c). ++* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed ++ the output delta to a Gray code (a^(a>>1)) so a string of 1's (as ++ is commonly produced by subtraction) look like a single 1-bit ++ difference. ++* the base values were pseudorandom, all zero but one bit set, or ++ all zero plus a counter that starts at zero. ++ ++These constants passed: ++ 14 11 25 16 4 14 24 ++ 12 14 25 16 4 14 24 ++and these came close: ++ 4 8 15 26 3 22 24 ++ 10 8 15 26 3 22 24 ++ 11 8 15 26 3 22 24 ++------------------------------------------------------------------------------- ++*/ ++#define final(a,b,c) \ ++{ \ ++ c ^= b; c -= rot(b,14); \ ++ a ^= c; a -= rot(c,11); \ ++ b ^= a; b -= rot(a,25); \ ++ c ^= b; c -= rot(b,16); \ ++ a ^= c; a -= rot(c,4); \ ++ b ^= a; b -= rot(a,14); \ ++ c ^= b; c -= rot(b,24); \ ++} ++ ++/* ++-------------------------------------------------------------------- ++ This works on all machines. To be useful, it requires ++ -- that the key be an array of uint32_t's, and ++ -- that the length be the number of uint32_t's in the key ++ ++ The function hashword() is identical to hashlittle() on little-endian ++ machines, and identical to hashbig() on big-endian machines, ++ except that the length has to be measured in uint32_ts rather than in ++ bytes. hashlittle() is more complicated than hashword() only because ++ hashlittle() has to dance around fitting the key bytes into registers. ++-------------------------------------------------------------------- ++*/ ++uint32_t hashword( ++const uint32_t *k, /* the key, an array of uint32_t values */ ++size_t length, /* the length of the key, in uint32_ts */ ++uint32_t initval) /* the previous hash, or an arbitrary value */ ++{ ++ uint32_t a,b,c; ++ ++ /* Set up the internal state */ ++ a = b = c = raninit + (((uint32_t)length)<<2) + initval; ++ ++ /*------------------------------------------------- handle most of the key */ ++ while (length > 3) ++ { ++ a += k[0]; ++ b += k[1]; ++ c += k[2]; ++ mix(a,b,c); ++ length -= 3; ++ k += 3; ++ } ++ ++ /*------------------------------------------- handle the last 3 uint32_t's */ ++ switch(length) /* all the case statements fall through */ ++ { ++ case 3 : c+=k[2]; ++ case 2 : b+=k[1]; ++ case 1 : a+=k[0]; ++ final(a,b,c); ++ case 0: /* case 0: nothing left to add */ ++ break; ++ } ++ /*------------------------------------------------------ report the result */ ++ return c; ++} ++ ++ ++#ifdef SELF_TEST ++ ++/* ++-------------------------------------------------------------------- ++hashword2() -- same as hashword(), but take two seeds and return two ++32-bit values. pc and pb must both be nonnull, and *pc and *pb must ++both be initialized with seeds. If you pass in (*pb)==0, the output ++(*pc) will be the same as the return value from hashword(). ++-------------------------------------------------------------------- ++*/ ++void hashword2 ( ++const uint32_t *k, /* the key, an array of uint32_t values */ ++size_t length, /* the length of the key, in uint32_ts */ ++uint32_t *pc, /* IN: seed OUT: primary hash value */ ++uint32_t *pb) /* IN: more seed OUT: secondary hash value */ ++{ ++ uint32_t a,b,c; ++ ++ /* Set up the internal state */ ++ a = b = c = raninit + ((uint32_t)(length<<2)) + *pc; ++ c += *pb; ++ ++ /*------------------------------------------------- handle most of the key */ ++ while (length > 3) ++ { ++ a += k[0]; ++ b += k[1]; ++ c += k[2]; ++ mix(a,b,c); ++ length -= 3; ++ k += 3; ++ } ++ ++ /*------------------------------------------- handle the last 3 uint32_t's */ ++ switch(length) /* all the case statements fall through */ ++ { ++ case 3 : c+=k[2]; ++ case 2 : b+=k[1]; ++ case 1 : a+=k[0]; ++ final(a,b,c); ++ case 0: /* case 0: nothing left to add */ ++ break; ++ } ++ /*------------------------------------------------------ report the result */ ++ *pc=c; *pb=b; ++} ++ ++#endif /* SELF_TEST */ ++ ++/* ++------------------------------------------------------------------------------- ++hashlittle() -- hash a variable-length key into a 32-bit value ++ k : the key (the unaligned variable-length array of bytes) ++ length : the length of the key, counting by bytes ++ initval : can be any 4-byte value ++Returns a 32-bit value. Every bit of the key affects every bit of ++the return value. Two keys differing by one or two bits will have ++totally different hash values. ++ ++The best hash table sizes are powers of 2. There is no need to do ++mod a prime (mod is sooo slow!). If you need less than 32 bits, ++use a bitmask. For example, if you need only 10 bits, do ++ h = (h & hashmask(10)); ++In which case, the hash table should have hashsize(10) elements. ++ ++If you are hashing n strings (uint8_t **)k, do it like this: ++ for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h); ++ ++By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this ++code any way you wish, private, educational, or commercial. It's free. ++ ++Use for hash table lookup, or anything where one collision in 2^^32 is ++acceptable. Do NOT use for cryptographic purposes. ++------------------------------------------------------------------------------- ++*/ ++ ++uint32_t hashlittle( const void *key, size_t length, uint32_t initval) ++{ ++ uint32_t a,b,c; /* internal state */ ++ union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ ++ ++ /* Set up the internal state */ ++ a = b = c = raninit + ((uint32_t)length) + initval; ++ ++ u.ptr = key; ++ if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) { ++ const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ ++#ifdef VALGRIND ++ const uint8_t *k8; ++#endif ++ ++ /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ ++ while (length > 12) ++ { ++ a += k[0]; ++ b += k[1]; ++ c += k[2]; ++ mix(a,b,c); ++ length -= 12; ++ k += 3; ++ } ++ ++ /*----------------------------- handle the last (probably partial) block */ ++ /* ++ * "k[2]&0xffffff" actually reads beyond the end of the string, but ++ * then masks off the part it's not allowed to read. Because the ++ * string is aligned, the masked-off tail is in the same word as the ++ * rest of the string. Every machine with memory protection I've seen ++ * does it on word boundaries, so is OK with this. But VALGRIND will ++ * still catch it and complain. The masking trick does make the hash ++ * noticably faster for short strings (like English words). ++ */ ++#ifndef VALGRIND ++ ++ switch(length) ++ { ++ case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; ++ case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; ++ case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; ++ case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; ++ case 8 : b+=k[1]; a+=k[0]; break; ++ case 7 : b+=k[1]&0xffffff; a+=k[0]; break; ++ case 6 : b+=k[1]&0xffff; a+=k[0]; break; ++ case 5 : b+=k[1]&0xff; a+=k[0]; break; ++ case 4 : a+=k[0]; break; ++ case 3 : a+=k[0]&0xffffff; break; ++ case 2 : a+=k[0]&0xffff; break; ++ case 1 : a+=k[0]&0xff; break; ++ case 0 : return c; /* zero length strings require no mixing */ ++ } ++ ++#else /* make valgrind happy */ ++ ++ k8 = (const uint8_t *)k; ++ switch(length) ++ { ++ case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; ++ case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ ++ case 10: c+=((uint32_t)k8[9])<<8; /* fall through */ ++ case 9 : c+=k8[8]; /* fall through */ ++ case 8 : b+=k[1]; a+=k[0]; break; ++ case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ ++ case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */ ++ case 5 : b+=k8[4]; /* fall through */ ++ case 4 : a+=k[0]; break; ++ case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ ++ case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */ ++ case 1 : a+=k8[0]; break; ++ case 0 : return c; ++ } ++ ++#endif /* !valgrind */ ++ ++ } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) { ++ const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ ++ const uint8_t *k8; ++ ++ /*--------------- all but last block: aligned reads and different mixing */ ++ while (length > 12) ++ { ++ a += k[0] + (((uint32_t)k[1])<<16); ++ b += k[2] + (((uint32_t)k[3])<<16); ++ c += k[4] + (((uint32_t)k[5])<<16); ++ mix(a,b,c); ++ length -= 12; ++ k += 6; ++ } ++ ++ /*----------------------------- handle the last (probably partial) block */ ++ k8 = (const uint8_t *)k; ++ switch(length) ++ { ++ case 12: c+=k[4]+(((uint32_t)k[5])<<16); ++ b+=k[2]+(((uint32_t)k[3])<<16); ++ a+=k[0]+(((uint32_t)k[1])<<16); ++ break; ++ case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ ++ case 10: c+=k[4]; ++ b+=k[2]+(((uint32_t)k[3])<<16); ++ a+=k[0]+(((uint32_t)k[1])<<16); ++ break; ++ case 9 : c+=k8[8]; /* fall through */ ++ case 8 : b+=k[2]+(((uint32_t)k[3])<<16); ++ a+=k[0]+(((uint32_t)k[1])<<16); ++ break; ++ case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ ++ case 6 : b+=k[2]; ++ a+=k[0]+(((uint32_t)k[1])<<16); ++ break; ++ case 5 : b+=k8[4]; /* fall through */ ++ case 4 : a+=k[0]+(((uint32_t)k[1])<<16); ++ break; ++ case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ ++ case 2 : a+=k[0]; ++ break; ++ case 1 : a+=k8[0]; ++ break; ++ case 0 : return c; /* zero length requires no mixing */ ++ } ++ ++ } else { /* need to read the key one byte at a time */ ++ const uint8_t *k = (const uint8_t *)key; ++ ++ /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ ++ while (length > 12) ++ { ++ a += k[0]; ++ a += ((uint32_t)k[1])<<8; ++ a += ((uint32_t)k[2])<<16; ++ a += ((uint32_t)k[3])<<24; ++ b += k[4]; ++ b += ((uint32_t)k[5])<<8; ++ b += ((uint32_t)k[6])<<16; ++ b += ((uint32_t)k[7])<<24; ++ c += k[8]; ++ c += ((uint32_t)k[9])<<8; ++ c += ((uint32_t)k[10])<<16; ++ c += ((uint32_t)k[11])<<24; ++ mix(a,b,c); ++ length -= 12; ++ k += 12; ++ } ++ ++ /*-------------------------------- last block: affect all 32 bits of (c) */ ++ switch(length) /* all the case statements fall through */ ++ { ++ case 12: c+=((uint32_t)k[11])<<24; ++ case 11: c+=((uint32_t)k[10])<<16; ++ case 10: c+=((uint32_t)k[9])<<8; ++ case 9 : c+=k[8]; ++ case 8 : b+=((uint32_t)k[7])<<24; ++ case 7 : b+=((uint32_t)k[6])<<16; ++ case 6 : b+=((uint32_t)k[5])<<8; ++ case 5 : b+=k[4]; ++ case 4 : a+=((uint32_t)k[3])<<24; ++ case 3 : a+=((uint32_t)k[2])<<16; ++ case 2 : a+=((uint32_t)k[1])<<8; ++ case 1 : a+=k[0]; ++ break; ++ case 0 : return c; ++ } ++ } ++ ++ final(a,b,c); ++ return c; ++} ++ ++#ifdef SELF_TEST ++ ++/* ++ * hashlittle2: return 2 32-bit hash values ++ * ++ * This is identical to hashlittle(), except it returns two 32-bit hash ++ * values instead of just one. This is good enough for hash table ++ * lookup with 2^^64 buckets, or if you want a second hash if you're not ++ * happy with the first, or if you want a probably-unique 64-bit ID for ++ * the key. *pc is better mixed than *pb, so use *pc first. If you want ++ * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)". ++ */ ++void hashlittle2( ++ const void *key, /* the key to hash */ ++ size_t length, /* length of the key */ ++ uint32_t *pc, /* IN: primary initval, OUT: primary hash */ ++ uint32_t *pb) /* IN: secondary initval, OUT: secondary hash */ ++{ ++ uint32_t a,b,c; /* internal state */ ++ union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ ++ ++ /* Set up the internal state */ ++ a = b = c = raninit + ((uint32_t)length) + *pc; ++ c += *pb; ++ ++ u.ptr = key; ++ if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) { ++ const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ ++#ifdef VALGRIND ++ const uint8_t *k8; ++#endif ++ ++ /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ ++ while (length > 12) ++ { ++ a += k[0]; ++ b += k[1]; ++ c += k[2]; ++ mix(a,b,c); ++ length -= 12; ++ k += 3; ++ } ++ ++ /*----------------------------- handle the last (probably partial) block */ ++ /* ++ * "k[2]&0xffffff" actually reads beyond the end of the string, but ++ * then masks off the part it's not allowed to read. Because the ++ * string is aligned, the masked-off tail is in the same word as the ++ * rest of the string. Every machine with memory protection I've seen ++ * does it on word boundaries, so is OK with this. But VALGRIND will ++ * still catch it and complain. The masking trick does make the hash ++ * noticably faster for short strings (like English words). ++ */ ++#ifndef VALGRIND ++ ++ switch(length) ++ { ++ case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; ++ case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; ++ case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; ++ case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; ++ case 8 : b+=k[1]; a+=k[0]; break; ++ case 7 : b+=k[1]&0xffffff; a+=k[0]; break; ++ case 6 : b+=k[1]&0xffff; a+=k[0]; break; ++ case 5 : b+=k[1]&0xff; a+=k[0]; break; ++ case 4 : a+=k[0]; break; ++ case 3 : a+=k[0]&0xffffff; break; ++ case 2 : a+=k[0]&0xffff; break; ++ case 1 : a+=k[0]&0xff; break; ++ case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */ ++ } ++ ++#else /* make valgrind happy */ ++ ++ k8 = (const uint8_t *)k; ++ switch(length) ++ { ++ case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; ++ case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ ++ case 10: c+=((uint32_t)k8[9])<<8; /* fall through */ ++ case 9 : c+=k8[8]; /* fall through */ ++ case 8 : b+=k[1]; a+=k[0]; break; ++ case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ ++ case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */ ++ case 5 : b+=k8[4]; /* fall through */ ++ case 4 : a+=k[0]; break; ++ case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ ++ case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */ ++ case 1 : a+=k8[0]; break; ++ case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */ ++ } ++ ++#endif /* !valgrind */ ++ ++ } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) { ++ const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ ++ const uint8_t *k8; ++ ++ /*--------------- all but last block: aligned reads and different mixing */ ++ while (length > 12) ++ { ++ a += k[0] + (((uint32_t)k[1])<<16); ++ b += k[2] + (((uint32_t)k[3])<<16); ++ c += k[4] + (((uint32_t)k[5])<<16); ++ mix(a,b,c); ++ length -= 12; ++ k += 6; ++ } ++ ++ /*----------------------------- handle the last (probably partial) block */ ++ k8 = (const uint8_t *)k; ++ switch(length) ++ { ++ case 12: c+=k[4]+(((uint32_t)k[5])<<16); ++ b+=k[2]+(((uint32_t)k[3])<<16); ++ a+=k[0]+(((uint32_t)k[1])<<16); ++ break; ++ case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ ++ case 10: c+=k[4]; ++ b+=k[2]+(((uint32_t)k[3])<<16); ++ a+=k[0]+(((uint32_t)k[1])<<16); ++ break; ++ case 9 : c+=k8[8]; /* fall through */ ++ case 8 : b+=k[2]+(((uint32_t)k[3])<<16); ++ a+=k[0]+(((uint32_t)k[1])<<16); ++ break; ++ case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ ++ case 6 : b+=k[2]; ++ a+=k[0]+(((uint32_t)k[1])<<16); ++ break; ++ case 5 : b+=k8[4]; /* fall through */ ++ case 4 : a+=k[0]+(((uint32_t)k[1])<<16); ++ break; ++ case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ ++ case 2 : a+=k[0]; ++ break; ++ case 1 : a+=k8[0]; ++ break; ++ case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */ ++ } ++ ++ } else { /* need to read the key one byte at a time */ ++ const uint8_t *k = (const uint8_t *)key; ++ ++ /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ ++ while (length > 12) ++ { ++ a += k[0]; ++ a += ((uint32_t)k[1])<<8; ++ a += ((uint32_t)k[2])<<16; ++ a += ((uint32_t)k[3])<<24; ++ b += k[4]; ++ b += ((uint32_t)k[5])<<8; ++ b += ((uint32_t)k[6])<<16; ++ b += ((uint32_t)k[7])<<24; ++ c += k[8]; ++ c += ((uint32_t)k[9])<<8; ++ c += ((uint32_t)k[10])<<16; ++ c += ((uint32_t)k[11])<<24; ++ mix(a,b,c); ++ length -= 12; ++ k += 12; ++ } ++ ++ /*-------------------------------- last block: affect all 32 bits of (c) */ ++ switch(length) /* all the case statements fall through */ ++ { ++ case 12: c+=((uint32_t)k[11])<<24; ++ case 11: c+=((uint32_t)k[10])<<16; ++ case 10: c+=((uint32_t)k[9])<<8; ++ case 9 : c+=k[8]; ++ case 8 : b+=((uint32_t)k[7])<<24; ++ case 7 : b+=((uint32_t)k[6])<<16; ++ case 6 : b+=((uint32_t)k[5])<<8; ++ case 5 : b+=k[4]; ++ case 4 : a+=((uint32_t)k[3])<<24; ++ case 3 : a+=((uint32_t)k[2])<<16; ++ case 2 : a+=((uint32_t)k[1])<<8; ++ case 1 : a+=k[0]; ++ break; ++ case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */ ++ } ++ } ++ ++ final(a,b,c); ++ *pc=c; *pb=b; ++} ++ ++#endif /* SELF_TEST */ ++ ++#if 0 /* currently not used */ ++ ++/* ++ * hashbig(): ++ * This is the same as hashword() on big-endian machines. It is different ++ * from hashlittle() on all machines. hashbig() takes advantage of ++ * big-endian byte ordering. ++ */ ++uint32_t hashbig( const void *key, size_t length, uint32_t initval) ++{ ++ uint32_t a,b,c; ++ union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */ ++ ++ /* Set up the internal state */ ++ a = b = c = raninit + ((uint32_t)length) + initval; ++ ++ u.ptr = key; ++ if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) { ++ const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ ++#ifdef VALGRIND ++ const uint8_t *k8; ++#endif ++ ++ /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ ++ while (length > 12) ++ { ++ a += k[0]; ++ b += k[1]; ++ c += k[2]; ++ mix(a,b,c); ++ length -= 12; ++ k += 3; ++ } ++ ++ /*----------------------------- handle the last (probably partial) block */ ++ /* ++ * "k[2]<<8" actually reads beyond the end of the string, but ++ * then shifts out the part it's not allowed to read. Because the ++ * string is aligned, the illegal read is in the same word as the ++ * rest of the string. Every machine with memory protection I've seen ++ * does it on word boundaries, so is OK with this. But VALGRIND will ++ * still catch it and complain. The masking trick does make the hash ++ * noticably faster for short strings (like English words). ++ */ ++#ifndef VALGRIND ++ ++ switch(length) ++ { ++ case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; ++ case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break; ++ case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break; ++ case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break; ++ case 8 : b+=k[1]; a+=k[0]; break; ++ case 7 : b+=k[1]&0xffffff00; a+=k[0]; break; ++ case 6 : b+=k[1]&0xffff0000; a+=k[0]; break; ++ case 5 : b+=k[1]&0xff000000; a+=k[0]; break; ++ case 4 : a+=k[0]; break; ++ case 3 : a+=k[0]&0xffffff00; break; ++ case 2 : a+=k[0]&0xffff0000; break; ++ case 1 : a+=k[0]&0xff000000; break; ++ case 0 : return c; /* zero length strings require no mixing */ ++ } ++ ++#else /* make valgrind happy */ ++ ++ k8 = (const uint8_t *)k; ++ switch(length) /* all the case statements fall through */ ++ { ++ case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; ++ case 11: c+=((uint32_t)k8[10])<<8; /* fall through */ ++ case 10: c+=((uint32_t)k8[9])<<16; /* fall through */ ++ case 9 : c+=((uint32_t)k8[8])<<24; /* fall through */ ++ case 8 : b+=k[1]; a+=k[0]; break; ++ case 7 : b+=((uint32_t)k8[6])<<8; /* fall through */ ++ case 6 : b+=((uint32_t)k8[5])<<16; /* fall through */ ++ case 5 : b+=((uint32_t)k8[4])<<24; /* fall through */ ++ case 4 : a+=k[0]; break; ++ case 3 : a+=((uint32_t)k8[2])<<8; /* fall through */ ++ case 2 : a+=((uint32_t)k8[1])<<16; /* fall through */ ++ case 1 : a+=((uint32_t)k8[0])<<24; break; ++ case 0 : return c; ++ } ++ ++#endif /* !VALGRIND */ ++ ++ } else { /* need to read the key one byte at a time */ ++ const uint8_t *k = (const uint8_t *)key; ++ ++ /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ ++ while (length > 12) ++ { ++ a += ((uint32_t)k[0])<<24; ++ a += ((uint32_t)k[1])<<16; ++ a += ((uint32_t)k[2])<<8; ++ a += ((uint32_t)k[3]); ++ b += ((uint32_t)k[4])<<24; ++ b += ((uint32_t)k[5])<<16; ++ b += ((uint32_t)k[6])<<8; ++ b += ((uint32_t)k[7]); ++ c += ((uint32_t)k[8])<<24; ++ c += ((uint32_t)k[9])<<16; ++ c += ((uint32_t)k[10])<<8; ++ c += ((uint32_t)k[11]); ++ mix(a,b,c); ++ length -= 12; ++ k += 12; ++ } ++ ++ /*-------------------------------- last block: affect all 32 bits of (c) */ ++ switch(length) /* all the case statements fall through */ ++ { ++ case 12: c+=k[11]; ++ case 11: c+=((uint32_t)k[10])<<8; ++ case 10: c+=((uint32_t)k[9])<<16; ++ case 9 : c+=((uint32_t)k[8])<<24; ++ case 8 : b+=k[7]; ++ case 7 : b+=((uint32_t)k[6])<<8; ++ case 6 : b+=((uint32_t)k[5])<<16; ++ case 5 : b+=((uint32_t)k[4])<<24; ++ case 4 : a+=k[3]; ++ case 3 : a+=((uint32_t)k[2])<<8; ++ case 2 : a+=((uint32_t)k[1])<<16; ++ case 1 : a+=((uint32_t)k[0])<<24; ++ break; ++ case 0 : return c; ++ } ++ } ++ ++ final(a,b,c); ++ return c; ++} ++ ++#endif /* 0 == currently not used */ ++ ++#ifdef SELF_TEST ++ ++/* used for timings */ ++void driver1() ++{ ++ uint8_t buf[256]; ++ uint32_t i; ++ uint32_t h=0; ++ time_t a,z; ++ ++ time(&a); ++ for (i=0; i<256; ++i) buf[i] = 'x'; ++ for (i=0; i<1; ++i) ++ { ++ h = hashlittle(&buf[0],1,h); ++ } ++ time(&z); ++ if (z-a > 0) printf("time %d %.8x\n", z-a, h); ++} ++ ++/* check that every input bit changes every output bit half the time */ ++#define HASHSTATE 1 ++#define HASHLEN 1 ++#define MAXPAIR 60 ++#define MAXLEN 70 ++void driver2() ++{ ++ uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1]; ++ uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z; ++ uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE]; ++ uint32_t x[HASHSTATE],y[HASHSTATE]; ++ uint32_t hlen; ++ ++ printf("No more than %d trials should ever be needed \n",MAXPAIR/2); ++ for (hlen=0; hlen < MAXLEN; ++hlen) ++ { ++ z=0; ++ for (i=0; i<hlen; ++i) /*----------------------- for each input byte, */ ++ { ++ for (j=0; j<8; ++j) /*------------------------ for each input bit, */ ++ { ++ for (m=1; m<8; ++m) /*------------ for serveral possible initvals, */ ++ { ++ for (l=0; l<HASHSTATE; ++l) ++ e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0); ++ ++ /*---- check that every output bit is affected by that input bit */ ++ for (k=0; k<MAXPAIR; k+=2) ++ { ++ uint32_t finished=1; ++ /* keys have one bit different */ ++ for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;} ++ /* have a and b be two keys differing in only one bit */ ++ a[i] ^= (k<<j); ++ a[i] ^= (k>>(8-j)); ++ c[0] = hashlittle(a, hlen, m); ++ b[i] ^= ((k+1)<<j); ++ b[i] ^= ((k+1)>>(8-j)); ++ d[0] = hashlittle(b, hlen, m); ++ /* check every bit is 1, 0, set, and not set at least once */ ++ for (l=0; l<HASHSTATE; ++l) ++ { ++ e[l] &= (c[l]^d[l]); ++ f[l] &= ~(c[l]^d[l]); ++ g[l] &= c[l]; ++ h[l] &= ~c[l]; ++ x[l] &= d[l]; ++ y[l] &= ~d[l]; ++ if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0; ++ } ++ if (finished) break; ++ } ++ if (k>z) z=k; ++ if (k==MAXPAIR) ++ { ++ printf("Some bit didn't change: "); ++ printf("%.8x %.8x %.8x %.8x %.8x %.8x ", ++ e[0],f[0],g[0],h[0],x[0],y[0]); ++ printf("i %d j %d m %d len %d\n", i, j, m, hlen); ++ } ++ if (z==MAXPAIR) goto done; ++ } ++ } ++ } ++ done: ++ if (z < MAXPAIR) ++ { ++ printf("Mix success %2d bytes %2d initvals ",i,m); ++ printf("required %d trials\n", z/2); ++ } ++ } ++ printf("\n"); ++} ++ ++/* Check for reading beyond the end of the buffer and alignment problems */ ++void driver3() ++{ ++ uint8_t buf[MAXLEN+20], *b; ++ uint32_t len; ++ uint8_t q[] = "This is the time for all good men to come to the aid of their country..."; ++ uint32_t h; ++ uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country..."; ++ uint32_t i; ++ uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country..."; ++ uint32_t j; ++ uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country..."; ++ uint32_t ref,x,y; ++ uint8_t *p; ++ ++ printf("Endianness. These lines should all be the same (for values filled in):\n"); ++ printf("%.8x %.8x %.8x\n", ++ hashword((const uint32_t *)q, (sizeof(q)-1)/4, 13), ++ hashword((const uint32_t *)q, (sizeof(q)-5)/4, 13), ++ hashword((const uint32_t *)q, (sizeof(q)-9)/4, 13)); ++ p = q; ++ printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", ++ hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), ++ hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), ++ hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), ++ hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), ++ hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), ++ hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); ++ p = &qq[1]; ++ printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", ++ hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), ++ hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), ++ hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), ++ hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), ++ hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), ++ hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); ++ p = &qqq[2]; ++ printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", ++ hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), ++ hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), ++ hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), ++ hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), ++ hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), ++ hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); ++ p = &qqqq[3]; ++ printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", ++ hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), ++ hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), ++ hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), ++ hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), ++ hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), ++ hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); ++ printf("\n"); ++ ++ /* check that hashlittle2 and hashlittle produce the same results */ ++ i=47; j=0; ++ hashlittle2(q, sizeof(q), &i, &j); ++ if (hashlittle(q, sizeof(q), 47) != i) ++ printf("hashlittle2 and hashlittle mismatch\n"); ++ ++ /* check that hashword2 and hashword produce the same results */ ++ len = raninit; ++ i=47, j=0; ++ hashword2(&len, 1, &i, &j); ++ if (hashword(&len, 1, 47) != i) ++ printf("hashword2 and hashword mismatch %x %x\n", ++ i, hashword(&len, 1, 47)); ++ ++ /* check hashlittle doesn't read before or after the ends of the string */ ++ for (h=0, b=buf+1; h<8; ++h, ++b) ++ { ++ for (i=0; i<MAXLEN; ++i) ++ { ++ len = i; ++ for (j=0; j<i; ++j) *(b+j)=0; ++ ++ /* these should all be equal */ ++ ref = hashlittle(b, len, (uint32_t)1); ++ *(b+i)=(uint8_t)~0; ++ *(b-1)=(uint8_t)~0; ++ x = hashlittle(b, len, (uint32_t)1); ++ y = hashlittle(b, len, (uint32_t)1); ++ if ((ref != x) || (ref != y)) ++ { ++ printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y, ++ h, i); ++ } ++ } ++ } ++} ++ ++/* check for problems with nulls */ ++ void driver4() ++{ ++ uint8_t buf[1]; ++ uint32_t h,i,state[HASHSTATE]; ++ ++ ++ buf[0] = ~0; ++ for (i=0; i<HASHSTATE; ++i) state[i] = 1; ++ printf("These should all be different\n"); ++ for (i=0, h=0; i<8; ++i) ++ { ++ h = hashlittle(buf, 0, h); ++ printf("%2ld 0-byte strings, hash is %.8x\n", i, h); ++ } ++} ++ ++ ++int main() ++{ ++ driver1(); /* test that the key is hashed: used for timings */ ++ driver2(); /* test that whole key is hashed thoroughly */ ++ driver3(); /* test that nothing but the key is hashed */ ++ driver4(); /* test hashing multiple buffers (all buffers are null) */ ++ return 1; ++} ++ ++#endif /* SELF_TEST */ +--- /dev/null ++++ b/lookup3.h +@@ -0,0 +1,71 @@ ++/* ++ * util/storage/lookup3.h - header file for hashing functions. ++ * ++ * Copyright (c) 2007, NLnet Labs. All rights reserved. ++ * ++ * This software is open source. ++ * ++ * Redistribution and use in source and binary forms, with or without ++ * modification, are permitted provided that the following conditions ++ * are met: ++ * ++ * Redistributions of source code must retain the above copyright notice, ++ * this list of conditions and the following disclaimer. ++ * ++ * Redistributions in binary form must reproduce the above copyright notice, ++ * this list of conditions and the following disclaimer in the documentation ++ * and/or other materials provided with the distribution. ++ * ++ * Neither the name of the NLNET LABS nor the names of its contributors may ++ * be used to endorse or promote products derived from this software without ++ * specific prior written permission. ++ * ++ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ++ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED ++ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR ++ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE ++ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR ++ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF ++ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS ++ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN ++ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ++ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE ++ * POSSIBILITY OF SUCH DAMAGE. ++ */ ++ ++/** ++ * \file ++ * ++ * This file contains header definitions for the hash functions we use. ++ * The hash functions are public domain (see lookup3.c). ++ */ ++ ++#ifndef UTIL_STORAGE_LOOKUP3_H ++#define UTIL_STORAGE_LOOKUP3_H ++ ++/** ++ * Hash key made of 4byte chunks. ++ * @param k: the key, an array of uint32_t values ++ * @param length: the length of the key, in uint32_ts ++ * @param initval: the previous hash, or an arbitrary value ++ * @return: hash value. ++ */ ++uint32_t hashword(const uint32_t *k, size_t length, uint32_t initval); ++ ++/** ++ * Hash key data. ++ * @param k: the key, array of uint8_t ++ * @param length: the length of the key, in uint8_ts ++ * @param initval: the previous hash, or an arbitrary value ++ * @return: hash value. ++ */ ++uint32_t hashlittle(const void *k, size_t length, uint32_t initval); ++ ++/** ++ * Set the randomisation initial value, set this before threads start, ++ * and before hashing stuff (because it changes subsequent results). ++ * @param v: value ++ */ ++void hash_set_raninit(uint32_t v); ++ ++#endif /* UTIL_STORAGE_LOOKUP3_H */ +--- a/server.c ++++ b/server.c +@@ -41,6 +41,8 @@ + #include "difffile.h" + #include "nsec3.h" + #include "ipc.h" ++#include "lookup3.h" ++#include "rrl.h" + + /* + * Data for the UDP handlers. +@@ -524,6 +526,23 @@ server_init(struct nsd *nsd) + int + server_prepare(struct nsd *nsd) + { ++#ifdef RATELIMIT ++ /* set secret modifier for hashing (udb ptr buckets and rate limits) */ ++#ifdef HAVE_ARC4RANDOM ++ srandom(arc4random()); ++ hash_set_raninit(arc4random()); ++#else ++ uint32_t v = getpid() ^ time(NULL); ++ srandom((unsigned long)v); ++ if(RAND_status() && RAND_bytes((unsigned char*)&v, sizeof(v)) > 0) ++ hash_set_raninit(v); ++ else hash_set_raninit(random()); ++#endif ++ rrl_mmap_init(nsd->child_count, nsd->options->rrl_size, ++ nsd->options->rrl_ratelimit, ++ nsd->options->rrl_whitelist_ratelimit); ++#endif /* RATELIMIT */ ++ + /* Open the database... */ + if ((nsd->db = namedb_open(nsd->dbfile, nsd->options, nsd->child_count)) == NULL) { + log_msg(LOG_ERR, "unable to open the database %s: %s", +@@ -964,6 +983,10 @@ server_main(struct nsd *nsd) + pid_t xfrd_pid = -1; + sig_atomic_t mode; + ++#ifdef RATELIMIT ++ rrl_init((nsd->this_child - nsd->children)/sizeof(nsd->children[0])); ++#endif ++ + /* Ensure we are the main process */ + assert(nsd->server_kind == NSD_SERVER_MAIN); + +@@ -1369,6 +1392,20 @@ server_child(struct nsd *nsd) + server_shutdown(nsd); + } + ++static query_state_type ++server_process_query_udp(struct nsd *nsd, struct query *query) ++{ ++#ifdef RATELIMIT ++ if(query_process(query, nsd) != QUERY_DISCARDED) { ++ if(rrl_process_query(query)) ++ return rrl_slip(query); ++ else return QUERY_PROCESSED; ++ } ++ return QUERY_DISCARDED; ++#else ++ return query_process(query, nsd); ++#endif ++} + + static void + handle_udp(netio_type *ATTR_UNUSED(netio), +@@ -1413,7 +1450,7 @@ handle_udp(netio_type *ATTR_UNUSED(netio + buffer_flip(q->packet); + + /* Process and answer the query... */ +- if (server_process_query(data->nsd, q) != QUERY_DISCARDED) { ++ if (server_process_query_udp(data->nsd, q) != QUERY_DISCARDED) { + #ifdef BIND8_STATS + if (RCODE(q->packet) == RCODE_OK && !AA(q->packet)) { + STATUP(data->nsd, nona); +--- a/nsd.conf.5.in ++++ b/nsd.conf.5.in +@@ -235,6 +235,25 @@ zone transfers. 2 lists soft warnings th + .B hide\-version:\fR <yes or no> + Prevent NSD from replying with the version string on CHAOS class + queries. ++.\" rrlstart ++.TP ++.B rrl\-size:\fR <numbuckets> ++This option gives the size of the hashtable. Default 1000000. More buckets ++use more memory, and reduce the chance of hash collisions. ++.TP ++.B rrl\-ratelimit:\fR <qps> ++The max qps allowed (from one query source). Default 200 qps. If set to 0 ++then it is disabled (unlimited rate), also set the whilelist\-ratelimit ++to 0 to disable ratelimit processing. If you set verbosity to 2 the ++blocked and unblocked subnets are logged. Blocked queries are blocked ++and some receive TCP fallback replies. ++.TP ++.B rrl\-whitelist\-ratelimit:\fR <qps> ++The max qps for query sorts for a source, which have been ++whitelisted. Default 2000 qps. With the rrl\-whitelist option you can set ++specific queries to receive this qps limit instead of the normal limit. ++With the value 0 the rate is unlimited. ++.\" rrlend + .SS "Zone Options" + .LP + For every zone the options need to be specified in one +@@ -328,6 +347,18 @@ The ip\-address is a plain IP address (I + A port number can be added using a suffix of @number, for example + 1.2.3.4@5300. + .RE ++\" rrlstart ++.TP ++.B rrl\-whitelist:\fR <rrltype> ++This option causes queries of this rrltype to be whitelisted, for this ++zone. They receive the whitelist\-ratelimit. You can give multiple lines, ++each enables a new rrltype to be whitelisted for the zone. Default has ++none whitelisted. The rrltype is the query classification that the NSD RRL ++employs to make different types not interfere with one another. The types ++are logged in the loglines when a subnet is blocked (in verbosity 2). ++The RRL classification types are: nxdomain, error, referral, any, rrsig, ++wildcard, nodata, dnskey, positive, all. ++.\" rrlend + .SS "Key Declarations" + The + .B key: +--- a/configparser.y ++++ b/configparser.y +@@ -18,6 +18,7 @@ + + #include "options.h" + #include "util.h" ++#include "rrl.h" + #include "configyyrename.h" + int c_lex(void); + void c_error(const char *message); +@@ -58,6 +59,7 @@ static int server_settings_seen = 0; + %token VAR_ALGORITHM VAR_SECRET + %token VAR_AXFR VAR_UDP + %token VAR_VERBOSITY VAR_HIDE_VERSION ++%token VAR_RRL_SIZE VAR_RRL_RATELIMIT VAR_RRL_WHITELIST_RATELIMIT VAR_RRL_WHITELIST + + %% + toplevelvars: /* empty */ | toplevelvars toplevelvar ; +@@ -81,7 +83,8 @@ content_server: server_ip_address | serv + server_username | server_zonesdir | + server_difffile | server_xfrdfile | server_xfrd_reload_timeout | + server_tcp_query_count | server_tcp_timeout | server_ipv4_edns_size | +- server_ipv6_edns_size | server_verbosity | server_hide_version; ++ server_ipv6_edns_size | server_verbosity | server_hide_version | ++ server_rrl_size | server_rrl_ratelimit | server_rrl_whitelist_ratelimit; + server_ip_address: VAR_IP_ADDRESS STRING + { + OUTYY(("P(server_ip_address:%s)\n", $2)); +@@ -294,6 +297,32 @@ server_ipv6_edns_size: VAR_IPV6_EDNS_SIZ + cfg_parser->opt->ipv6_edns_size = atoi($2); + } + ; ++server_rrl_size: VAR_RRL_SIZE STRING ++ { ++ OUTYY(("P(server_rrl_size:%s)\n", $2)); ++#ifdef RATELIMIT ++ if(atoi($2) <= 0) ++ yyerror("number greater than zero expected"); ++ cfg_parser->opt->rrl_size = atoi($2); ++#endif ++ } ++ ; ++server_rrl_ratelimit: VAR_RRL_RATELIMIT STRING ++ { ++ OUTYY(("P(server_rrl_ratelimit:%s)\n", $2)); ++#ifdef RATELIMIT ++ cfg_parser->opt->rrl_ratelimit = atoi($2); ++#endif ++ } ++ ; ++server_rrl_whitelist_ratelimit: VAR_RRL_WHITELIST_RATELIMIT STRING ++ { ++ OUTYY(("P(server_rrl_whitelist_ratelimit:%s)\n", $2)); ++#ifdef RATELIMIT ++ cfg_parser->opt->rrl_whitelist_ratelimit = atoi($2); ++#endif ++ } ++ ; + + /* zone: declaration */ + zonestart: VAR_ZONE +@@ -321,7 +350,7 @@ zonestart: VAR_ZONE + contents_zone: contents_zone content_zone | content_zone; + content_zone: zone_name | zone_zonefile | zone_allow_notify | + zone_request_xfr | zone_notify | zone_notify_retry | zone_provide_xfr | +- zone_outgoing_interface | zone_allow_axfr_fallback; ++ zone_outgoing_interface | zone_allow_axfr_fallback | zone_rrl_whitelist; + zone_name: VAR_NAME STRING + { + OUTYY(("P(zone_name:%s)\n", $2)); +@@ -446,6 +475,14 @@ zone_allow_axfr_fallback: VAR_ALLOW_AXFR + else cfg_parser->current_zone->allow_axfr_fallback = (strcmp($2, "yes")==0); + } + ; ++zone_rrl_whitelist: VAR_RRL_WHITELIST STRING ++ { ++ OUTYY(("P(zone_rrl_whitelist:%s)\n", $2)); ++#ifdef RATELIMIT ++ cfg_parser->current_zone->rrl_whitelist |= rrlstr2type($2); ++#endif ++ } ++ ; + + /* key: declaration */ + keystart: VAR_KEY +--- a/nsd.conf.sample.in ++++ b/nsd.conf.sample.in +@@ -99,6 +99,20 @@ server: + # Verbosity level. + # verbosity: 0 + ++ # RRLconfig ++ # Response Rate Limiting, size of the hashtable. Default 1000000. ++ # rrl-size: 1000000 ++ ++ # Response Rate Limiting, maximum QPS allowed (from one query source). ++ # Default 200. If set to 0, ratelimiting is disabled. Also set ++ # rrl-whitelist-ratelimit to 0 to disable ratelimit processing. ++ # rrl-ratelimit: 200 ++ ++ # Response Rate Limiting, maximum QPS allowed (from one query source) ++ # for whitelisted types. Default 2000. ++ # rrl-whitelist-ratelimit: 2000 ++ # RRLend ++ + # key for zone 1 + key: + name: mskey +@@ -173,6 +187,21 @@ zone: + # set local interface for sending notifies + outgoing-interface: 10.0.0.15 + ++ # RRLconfig ++ # Response Rate Limiting, whitelist types ++ # rrl-whitelist: nxdomain ++ # rrl-whitelist: error ++ # rrl-whitelist: referral ++ # rrl-whitelist: any ++ # rrl-whitelist: rrsig ++ # rrl-whitelist: wildcard ++ # rrl-whitelist: nodata ++ # rrl-whitelist: dnskey ++ # rrl-whitelist: positive ++ # rrl-whitelist: all ++ # RRLend ++ ++ + # keys for zone 2 + key: + name: "sec1_key" +--- a/configure.ac ++++ b/configure.ac +@@ -598,6 +598,19 @@ case "$enable_checking" in + ;; + esac + ++AC_ARG_ENABLE(ratelimit, AC_HELP_STRING([--enable-ratelimit], [Enable rate limiting])) ++case "$enable_ratelimit" in ++ yes) ++ AC_DEFINE_UNQUOTED([RATELIMIT], [], [Define this to enable rate limiting.]) ++ dnl causes awk to not match the exclusion start marker. ++ ratelimit="xx" ++ ;; ++ no|*) ++ ratelimit="" ++ ;; ++esac ++AC_SUBST(ratelimit) ++ + # we need SSL for TSIG (and maybe also for NSEC3). + CHECK_SSL + +--- /dev/null ++++ b/rrl.c +@@ -0,0 +1,463 @@ ++ ++/* rrl.c - Response Rate Limiting for NSD. ++ * By W.C.A. Wijngaards ++ * Copyright 2012, NLnet Labs. ++ * BSD, see LICENSE. ++ */ ++#include "config.h" ++#include <errno.h> ++#include <ctype.h> ++#include "rrl.h" ++#include "util.h" ++#include "lookup3.h" ++#include "options.h" ++ ++#ifdef RATELIMIT ++ ++#ifdef HAVE_MMAP ++#include <sys/mman.h> ++#if defined(MAP_ANON) && !defined(MAP_ANONYMOUS) ++#define MAP_ANONYMOUS MAP_ANON ++#endif ++#endif /* HAVE_MMAP */ ++ ++ ++/** ++ * The rate limiting data structure bucket, this represents one rate of ++ * packets from a single source. ++ * Smoothed average rates. ++ */ ++struct rrl_bucket { ++ /* the source netmask */ ++ uint64_t source; ++ /* rate, in queries per second, which due to rate=r(t)+r(t-1)/2 is ++ * equal to double the queries per second */ ++ uint32_t rate; ++ /* counter for queries arrived in this second */ ++ uint32_t counter; ++ /* timestamp, which time is the time of the counter, the rate is from ++ * one timestep before that. */ ++ int32_t stamp; ++ /* flags for the source mask and type */ ++ uint16_t flags; ++}; ++ ++/* the (global) array of RRL buckets */ ++static struct rrl_bucket* rrl_array = NULL; ++static size_t rrl_array_size = RRL_BUCKETS; ++static uint32_t rrl_ratelimit = RRL_LIMIT; /* 2x qps */ ++static uint32_t rrl_whitelist_ratelimit = RRL_WLIST_LIMIT; /* 2x qps */ ++ ++/* the array of mmaps for the children (saved between reloads) */ ++static void** rrl_maps = NULL; ++static size_t rrl_maps_num = 0; ++ ++/* from NSD4 for RRL logs */ ++static char* wiredname2str(const uint8_t* dname) ++{ ++ static char buf[MAXDOMAINLEN*5+3]; ++ char* p = buf; ++ uint8_t lablen; ++ if(*dname == 0) { ++ strlcpy(buf, ".", sizeof(buf)); ++ return buf; ++ } ++ lablen = *dname++; ++ while(lablen) { ++ while(lablen--) { ++ uint8_t ch = *dname++; ++ if (isalnum(ch) || ch == '-' || ch == '_') { ++ *p++ = ch; ++ } else if (ch == '.' || ch == '\\') { ++ *p++ = '\\'; ++ *p++ = ch; ++ } else { ++ snprintf(p, 5, "\\%03u", (unsigned int)ch); ++ p += 4; ++ } ++ } ++ lablen = *dname++; ++ *p++ = '.'; ++ } ++ *p++ = 0; ++ return buf; ++} ++ ++void rrl_mmap_init(int numch, size_t numbuck, size_t lm, size_t wlm) ++{ ++#ifdef HAVE_MMAP ++ size_t i; ++#endif ++ if(numbuck != 0) ++ rrl_array_size = numbuck; ++ rrl_ratelimit = lm*2; ++ rrl_whitelist_ratelimit = wlm*2; ++#ifdef HAVE_MMAP ++ /* allocate the ratelimit hashtable in a memory map so it is ++ * preserved across reforks (every child its own table) */ ++ rrl_maps_num = (size_t)numch; ++ rrl_maps = (void**)xalloc(sizeof(void*)*rrl_maps_num); ++ for(i=0; i<rrl_maps_num; i++) { ++ rrl_maps[i] = mmap(NULL, ++ sizeof(struct rrl_bucket)*rrl_array_size, ++ PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0); ++ if(rrl_maps[i] == MAP_FAILED) { ++ log_msg(LOG_ERR, "rrl: mmap failed: %s", ++ strerror(errno)); ++ exit(1); ++ } ++ memset(rrl_maps[i], 0, ++ sizeof(struct rrl_bucket)*rrl_array_size); ++ } ++#else ++ (void)numch; ++ rrl_maps_num = 0; ++ rrl_maps = NULL; ++#endif ++} ++ ++void rrl_set_limit(size_t lm, size_t wlm) ++{ ++ rrl_ratelimit = lm*2; ++ rrl_whitelist_ratelimit = wlm*2; ++} ++ ++void rrl_init(size_t ch) ++{ ++ if(!rrl_maps || ch >= rrl_maps_num) ++ rrl_array = xalloc_zero(sizeof(struct rrl_bucket)*rrl_array_size); ++#ifdef HAVE_MMAP ++ else rrl_array = (struct rrl_bucket*)rrl_maps[ch]; ++#endif ++} ++ ++/** return the source netblock of the query, this is the genuine source ++ * for genuine queries and the target for reflected packets */ ++static uint64_t rrl_get_source(query_type* query, uint16_t* c2) ++{ ++ /* we take a /24 for IPv4 and /64 for IPv6 */ ++ /* note there is an IPv6 subnet, that maps ++ * to the same buckets as IPv4 space, but there is a flag in c2 ++ * that makes the hash different */ ++#ifdef INET6 ++ if( ((struct sockaddr_in*)&query->addr)->sin_family == AF_INET) { ++ *c2 = 0; ++ return ((struct sockaddr_in*)&query->addr)-> ++ sin_addr.s_addr & htonl(0xffffff00); ++ } else { ++ uint64_t s; ++ *c2 = rrl_ip6; ++ memmove(&s, &((struct sockaddr_in6*)&query->addr)->sin6_addr, ++ sizeof(s)); ++ return s; ++ } ++#else ++ *c2 = 0; ++ return query->addr.sin_addr.s_addr & htonl(0xffffff00); ++#endif ++} ++ ++/** debug source to string */ ++static const char* rrlsource2str(uint64_t s, uint16_t c2) ++{ ++ static char buf[64]; ++ struct in_addr a4; ++#ifdef INET6 ++ if(c2) { ++ /* IPv6 */ ++ struct in6_addr a6; ++ memset(&a6, 0, sizeof(a6)); ++ memmove(&a6, &s, sizeof(s)); ++ if(!inet_ntop(AF_INET6, &a6, buf, sizeof(buf))) ++ strlcpy(buf, "[ip6 ntop failed]", sizeof(buf)); ++ else strlcat(buf, "/64", sizeof(buf)); ++ return buf; ++ } ++#endif ++ /* ipv4 */ ++ a4.s_addr = (uint32_t)s; ++ if(!inet_ntop(AF_INET, &a4, buf, sizeof(buf))) ++ strlcpy(buf, "[ip4 ntop failed]", sizeof(buf)); ++ else strlcat(buf, "/24", sizeof(buf)); ++ return buf; ++} ++ ++enum rrl_type rrlstr2type(const char* s) ++{ ++ if(strcmp(s, "nxdomain")==0) return rrl_type_nxdomain; ++ else if(strcmp(s, "error")==0) return rrl_type_error; ++ else if(strcmp(s, "referral")==0) return rrl_type_referral; ++ else if(strcmp(s, "any")==0) return rrl_type_any; ++ else if(strcmp(s, "wildcard")==0) return rrl_type_wildcard; ++ else if(strcmp(s, "nodata")==0) return rrl_type_nodata; ++ else if(strcmp(s, "dnskey")==0) return rrl_type_dnskey; ++ else if(strcmp(s, "positive")==0) return rrl_type_positive; ++ else if(strcmp(s, "rrsig")==0) return rrl_type_rrsig; ++ else if(strcmp(s, "all")==0) return rrl_type_all; ++ return 0; /* unknown */ ++} ++ ++const char* rrltype2str(enum rrl_type c) ++{ ++ switch(c & 0x0fff) { ++ case rrl_type_nxdomain: return "nxdomain"; ++ case rrl_type_error: return "error"; ++ case rrl_type_referral: return "referral"; ++ case rrl_type_any: return "any"; ++ case rrl_type_wildcard: return "wildcard"; ++ case rrl_type_nodata: return "nodata"; ++ case rrl_type_dnskey: return "dnskey"; ++ case rrl_type_positive: return "positive"; ++ case rrl_type_rrsig: return "rrsig"; ++ case rrl_type_all: return "all"; ++ } ++ return "unknown"; ++} ++ ++/** classify the query in a number of different types, each has separate ++ * ratelimiting, so that positive queries are not impeded by others */ ++static uint16_t rrl_classify(query_type* query, const uint8_t** d, ++ size_t* d_len) ++{ ++ if(RCODE(query->packet) == RCODE_NXDOMAIN) { ++ if(query->zone && query->zone->apex) { ++ *d = dname_name(domain_dname(query->zone->apex)); ++ *d_len = domain_dname(query->zone->apex)->name_size; ++ } ++ return rrl_type_nxdomain; ++ } ++ if(RCODE(query->packet) != RCODE_OK) { ++ if(query->zone && query->zone->apex) { ++ *d = dname_name(domain_dname(query->zone->apex)); ++ *d_len = domain_dname(query->zone->apex)->name_size; ++ } ++ return rrl_type_error; ++ } ++ if(query->delegation_domain) { ++ *d = dname_name(domain_dname(query->delegation_domain)); ++ *d_len = domain_dname(query->delegation_domain)->name_size; ++ return rrl_type_referral; ++ } ++ if(query->qtype == TYPE_ANY) { ++ if(query->qname) { ++ *d = dname_name(query->qname); ++ *d_len = query->qname->name_size; ++ } ++ return rrl_type_any; ++ } ++ if(query->qtype == TYPE_RRSIG) { ++ if(query->qname) { ++ *d = dname_name(query->qname); ++ *d_len = query->qname->name_size; ++ } ++ return rrl_type_rrsig; ++ } ++ if(query->wildcard_domain) { ++ *d = dname_name(domain_dname(query->wildcard_domain)); ++ *d_len = domain_dname(query->wildcard_domain)->name_size; ++ return rrl_type_wildcard; ++ } ++ if(ANCOUNT(query->packet) == 0) { ++ if(query->zone && query->zone->apex) { ++ *d = dname_name(domain_dname(query->zone->apex)); ++ *d_len = domain_dname(query->zone->apex)->name_size; ++ } ++ return rrl_type_nodata; ++ } ++ if(query->qtype == TYPE_DNSKEY) { ++ if(query->qname) { ++ *d = dname_name(query->qname); ++ *d_len = query->qname->name_size; ++ } ++ return rrl_type_dnskey; ++ } ++ /* positive */ ++ if(query->qname) { ++ *d = dname_name(query->qname); ++ *d_len = query->qname->name_size; ++ } ++ return rrl_type_positive; ++} ++ ++/** Examine the query and return hash and source of netblock. */ ++static void examine_query(query_type* query, uint32_t* hash, uint64_t* source, ++ uint16_t* flags, uint32_t* lm) ++{ ++ /* compile a binary string representing the query */ ++ uint16_t c, c2; ++ /* size with 16 bytes to spare */ ++ uint8_t buf[MAXDOMAINLEN + sizeof(*source) + sizeof(c) + 16]; ++ const uint8_t* dname = NULL; size_t dname_len; ++ uint32_t r = 0x267fcd16; ++ ++ *source = rrl_get_source(query, &c2); ++ c = rrl_classify(query, &dname, &dname_len); ++ if(query->zone && query->zone->opts && ++ (query->zone->opts->rrl_whitelist & c)) ++ *lm = rrl_whitelist_ratelimit; ++ if(*lm == 0) return; ++ c |= c2; ++ *flags = c; ++ memmove(buf, source, sizeof(*source)); ++ memmove(buf+sizeof(*source), &c, sizeof(c)); ++ ++ DEBUG(DEBUG_QUERY, 1, (LOG_INFO, "rrl_examine type %s name %s", rrltype2str(c), dname?wiredname2str(dname):"NULL")); ++ ++ /* and hash it */ ++ if(dname && dname_len <= MAXDOMAINLEN) { ++ memmove(buf+sizeof(*source)+sizeof(c), dname, dname_len); ++ *hash = hashlittle(buf, sizeof(*source)+sizeof(c)+dname_len, r); ++ } else ++ *hash = hashlittle(buf, sizeof(*source)+sizeof(c), r); ++} ++ ++/* age the bucket because elapsed time steps have gone by */ ++static void rrl_attenuate_bucket(struct rrl_bucket* b, int32_t elapsed) ++{ ++ if(elapsed > 16) { ++ b->rate = 0; ++ } else { ++ /* divide rate /2 for every elapsed time step, because ++ * the counters in the inbetween steps were 0 */ ++ /* r(t) = 0 + 0/2 + 0/4 + .. + oldrate/2^dt */ ++ b->rate >>= elapsed; ++ /* we know that elapsed >= 2 */ ++ b->rate += (b->counter>>(elapsed-1)); ++ } ++} ++ ++/** log a message about ratelimits */ ++static void ++rrl_msg(query_type* query, const char* str) ++{ ++ uint16_t c, c2, wl = 0; ++ const uint8_t* d = NULL; ++ size_t d_len; ++ uint64_t s; ++ if(verbosity < 2) return; ++ s = rrl_get_source(query, &c2); ++ c = rrl_classify(query, &d, &d_len) | c2; ++ if(query->zone && query->zone->opts && ++ (query->zone->opts->rrl_whitelist & c)) ++ wl = 1; ++ log_msg(LOG_INFO, "ratelimit %s %s type %s%s target %s", ++ str, d?wiredname2str(d):"", rrltype2str(c), ++ wl?"(whitelisted)":"", rrlsource2str(s, c2)); ++} ++ ++/** true if the query used to be blocked by the ratelimit */ ++static int ++used_to_block(uint32_t rate, uint32_t counter, uint32_t lm) ++{ ++ return rate >= lm || counter+rate/2 >= lm; ++} ++ ++/** update the rate in a ratelimit bucket, return actual rate */ ++uint32_t rrl_update(query_type* query, uint32_t hash, uint64_t source, ++ uint16_t flags, int32_t now, uint32_t lm) ++{ ++ struct rrl_bucket* b = &rrl_array[hash % rrl_array_size]; ++ ++ DEBUG(DEBUG_QUERY, 1, (LOG_INFO, "source %llx hash %x oldrate %d oldcount %d stamp %d", ++ (long long unsigned)source, hash, b->rate, b->counter, b->stamp)); ++ ++ /* check if different source */ ++ if(b->source != source || b->flags != flags) { ++ /* initialise */ ++ /* potentially the wrong limit here, used lower nonwhitelim */ ++ if(verbosity >=2 && ++ used_to_block(b->rate, b->counter, rrl_ratelimit)) ++ log_msg(LOG_INFO, "ratelimit unblock ~ type %s target %s", ++ rrltype2str(b->flags), ++ rrlsource2str(b->source, b->flags)); ++ b->source = source; ++ b->flags = flags; ++ b->counter = 1; ++ b->rate = 0; ++ b->stamp = now; ++ return 1; ++ } ++ /* this is the same source */ ++ ++ /* check if old, zero or smooth it */ ++ /* circular arith for time */ ++ if(now - b->stamp == 1) { ++ /* very busy bucket and time just stepped one step */ ++ int oldblock = used_to_block(b->rate, b->counter, lm); ++ b->rate = b->rate/2 + b->counter; ++ if(oldblock && b->rate < lm) ++ rrl_msg(query, "unblock"); ++ b->counter = 1; ++ b->stamp = now; ++ } else if(now - b->stamp > 0) { ++ /* older bucket */ ++ int olderblock = used_to_block(b->rate, b->counter, lm); ++ rrl_attenuate_bucket(b, now - b->stamp); ++ if(olderblock && b->rate < lm) ++ rrl_msg(query, "unblock"); ++ b->counter = 1; ++ b->stamp = now; ++ } else if(now != b->stamp) { ++ /* robust, timestamp from the future */ ++ if(used_to_block(b->rate, b->counter, lm)) ++ rrl_msg(query, "unblock"); ++ b->rate = 0; ++ b->counter = 1; ++ b->stamp = now; ++ } else { ++ /* bucket is from the current timestep, update counter */ ++ b->counter ++; ++ ++ /* log what is blocked for operational debugging */ ++ if(b->counter + b->rate/2 == lm && b->rate < lm) ++ rrl_msg(query, "block"); ++ } ++ ++ /* return max from current rate and projected next-value for rate */ ++ /* so that if the rate increases suddenly very high, it is ++ * stopped halfway into the time step */ ++ if(b->counter > b->rate/2) ++ return b->counter + b->rate/2; ++ return b->rate; ++} ++ ++int rrl_process_query(query_type* query) ++{ ++ uint64_t source; ++ uint32_t hash; ++ int32_t now = (int32_t)time(NULL); ++ uint32_t lm = rrl_ratelimit; ++ uint16_t flags; ++ if(rrl_ratelimit == 0 && rrl_whitelist_ratelimit == 0) ++ return 0; ++ ++ /* examine query */ ++ examine_query(query, &hash, &source, &flags, &lm); ++ ++ if(lm == 0) ++ return 0; /* no limit for this */ ++ ++ /* update rate */ ++ return (rrl_update(query, hash, source, flags, now, lm) >= lm); ++} ++ ++query_state_type rrl_slip(query_type* query) ++{ ++ /* discard half the packets, randomly */ ++ if((random() & 0x1)) { ++ /* set TC on the rest */ ++ TC_SET(query->packet); ++ ANCOUNT_SET(query->packet, 0); ++ NSCOUNT_SET(query->packet, 0); ++ ARCOUNT_SET(query->packet, 0); ++ if(query->qname) ++ /* header, type, class, qname */ ++ buffer_set_position(query->packet, ++ QHEADERSZ+4+query->qname->name_size); ++ else buffer_set_position(query->packet, QHEADERSZ); ++ return QUERY_PROCESSED; ++ } ++ return QUERY_DISCARDED; ++} ++ ++#endif /* RATELIMIT */ +--- /dev/null ++++ b/rrl.h +@@ -0,0 +1,71 @@ ++/* rrl.h - Response Rate Limiting for NSD. ++ * By W.C.A. Wijngaards ++ * Copyright 2012, NLnet Labs. ++ * BSD, see LICENSE. ++ */ ++#ifndef RRL_H ++#define RRL_H ++#include "query.h" ++ ++/** the classification types for the rrl */ ++enum rrl_type { ++ /* classification types */ ++ rrl_type_nxdomain = 0x01, ++ rrl_type_error = 0x02, ++ rrl_type_referral = 0x04, ++ rrl_type_any = 0x08, ++ rrl_type_wildcard = 0x10, ++ rrl_type_nodata = 0x20, ++ rrl_type_dnskey = 0x40, ++ rrl_type_positive = 0x80, ++ rrl_type_rrsig = 0x100, ++ ++ /* all classification types */ ++ rrl_type_all = 0x1ff, ++ /* to distinguish between ip4 and ip6 netblocks, used in code */ ++ rrl_ip6 = 0x8000 ++}; ++ ++/** Number of buckets */ ++#define RRL_BUCKETS 1000000 ++/** default rrl limit, in 2x qps , the default is 200 qps */ ++#define RRL_LIMIT 400 ++/** default whitelist rrl limit, in 2x qps, default is thus 2000 qps */ ++#define RRL_WLIST_LIMIT 4000 ++ ++/** ++ * Initialize for n children (optional, otherwise no mmaps used) ++ * ratelimits lm and wlm are in qps (this routines x2s them for internal use). ++ */ ++void rrl_mmap_init(int numch, size_t numbuck, size_t lm, size_t wlm); ++ ++/** ++ * Initialize rate limiting (for this child server process) ++ */ ++void rrl_init(size_t ch); ++ ++/** ++ * Process query that happens, the query structure contains the ++ * information about the query and the answer. ++ * returns true if the query is ratelimited. ++ */ ++int rrl_process_query(query_type* query); ++ ++/** ++ * Deny the query, with slip. ++ * Returns DISCARD or PROCESSED(with TC flag). ++ */ ++query_state_type rrl_slip(query_type* query); ++ ++/** convert classification type to string */ ++const char* rrltype2str(enum rrl_type c); ++/** convert string to classification type */ ++enum rrl_type rrlstr2type(const char* s); ++ ++/** for unit test, update rrl bucket; return rate */ ++uint32_t rrl_update(query_type* query, uint32_t hash, uint64_t source, ++ uint16_t flags, int32_t now, uint32_t lm); ++/** set the rate limit counters, pass variables in qps */ ++void rrl_set_limit(size_t lm, size_t wlm); ++ ++#endif /* RRL_H */ +--- a/query.c ++++ b/query.c +@@ -226,6 +226,10 @@ query_reset(query_type *q, size_t maxlen + q->axfr_current_domain = NULL; + q->axfr_current_rrset = NULL; + q->axfr_current_rr = 0; ++ ++#ifdef RATELIMIT ++ q->wildcard_domain = NULL; ++#endif + } + + /* get a temporary domain number (or 0=failure) */ +@@ -1031,6 +1035,9 @@ answer_authoritative(struct nsd *nsd, + } else if (domain_wildcard_child(closest_encloser)) { + /* Generate the domain from the wildcard. */ + domain_type *wildcard_child = domain_wildcard_child(closest_encloser); ++#ifdef RATELIMIT ++ q->wildcard_domain = wildcard_child; ++#endif + + match = (domain_type *) region_alloc(q->region, + sizeof(domain_type)); +--- a/nsd-checkconf.c ++++ b/nsd-checkconf.c +@@ -16,6 +16,7 @@ + #include "options.h" + #include "util.h" + #include "dname.h" ++#include "rrl.h" + + extern char *optarg; + extern int optind; +@@ -45,6 +46,12 @@ extern int optind; + printf("%s\n", zone->NAME?"yes":"no"); \ + } + ++#define ZONE_GET_RRL(NAME, VAR, PATTERN) \ ++ if (strcasecmp(#NAME, (VAR)) == 0) { \ ++ zone_print_rrl_whitelist("", PATTERN->NAME); \ ++ return; \ ++ } ++ + #define SERV_GET_BIN(NAME, VAR) \ + if (strcasecmp(#NAME, (VAR)) == 0) { \ + printf("%s\n", opt->NAME?"yes":"no"); \ +@@ -71,6 +78,21 @@ extern int optind; + return; \ + } + ++#ifdef RATELIMIT ++static void zone_print_rrl_whitelist(const char* s, uint16_t w) ++{ ++ int i; ++ if(w==rrl_type_all) { ++ printf("%sall\n", s); ++ return; ++ } ++ for(i=0x01; i <= 0x80; i<<=1) { ++ if( (w&i) ) ++ printf("%s%s\n", s, rrltype2str(i)); ++ } ++} ++#endif /* RATELIMIT */ ++ + static char buf[BUFSIZ]; + + static char * +@@ -248,6 +270,9 @@ config_print_zone(nsd_options_t* opt, co + ZONE_GET_BIN(notify_retry, o); + ZONE_GET_OUTGOING(outgoing_interface, o); + ZONE_GET_BIN(allow_axfr_fallback, o); ++#ifdef RATELIMIT ++ ZONE_GET_RRL(rrl_whitelist, o, zone); ++#endif + printf("Zone option not handled: %s %s\n", z, o); + exit(1); + } +@@ -287,6 +312,11 @@ config_print_zone(nsd_options_t* opt, co + SERV_GET_INT(statistics, o); + SERV_GET_INT(xfrd_reload_timeout, o); + SERV_GET_INT(verbosity, o); ++#ifdef RATELIMIT ++ SERV_GET_INT(rrl_size, o); ++ SERV_GET_INT(rrl_ratelimit, o); ++ SERV_GET_INT(rrl_whitelist_ratelimit, o); ++#endif + + if(strcasecmp(o, "zones") == 0) { + RBTREE_FOR(zone, zone_options_t*, opt->zone_options) +@@ -334,6 +364,11 @@ config_test_print_server(nsd_options_t* + print_string_var("xfrdfile:", opt->xfrdfile); + printf("\txfrd_reload_timeout: %d\n", opt->xfrd_reload_timeout); + printf("\tverbosity: %d\n", opt->verbosity); ++#ifdef RATELIMIT ++ printf("\trrl-size: %d\n", (int)opt->rrl_size); ++ printf("\trrl-ratelimit: %d\n", (int)opt->rrl_ratelimit); ++ printf("\trrl-whitelist-ratelimit: %d\n", (int)opt->rrl_whitelist_ratelimit); ++#endif + + for(ip = opt->ip_addresses; ip; ip=ip->next) + { +@@ -351,6 +386,9 @@ config_test_print_server(nsd_options_t* + printf("\nzone:\n"); + print_string_var("name:", zone->name); + print_string_var("zonefile:", zone->zonefile); ++#ifdef RATELIMIT ++ zone_print_rrl_whitelist("\trrl-whitelist: ", zone->rrl_whitelist); ++#endif + print_acl("allow-notify:", zone->allow_notify); + print_acl("request-xfr:", zone->request_xfr); + printf("\tnotify-retry: %d\n", zone->notify_retry); +--- a/query.h ++++ b/query.h +@@ -119,6 +119,11 @@ struct query { + domain_type *axfr_current_domain; + rrset_type *axfr_current_rrset; + uint16_t axfr_current_rr; ++ ++#ifdef RATELIMIT ++ /* if we encountered a wildcard, its domain */ ++ domain_type *wildcard_domain; ++#endif + }; + + +--- a/configlexer.lex ++++ b/configlexer.lex +@@ -138,6 +138,10 @@ algorithm{COLON} { LEXOUT(("v(%s) ", yyt + secret{COLON} { LEXOUT(("v(%s) ", yytext)); return VAR_SECRET;} + AXFR { LEXOUT(("v(%s) ", yytext)); return VAR_AXFR;} + UDP { LEXOUT(("v(%s) ", yytext)); return VAR_UDP;} ++rrl-size{COLON} { LEXOUT(("v(%s) ", yytext)); return VAR_RRL_SIZE;} ++rrl-ratelimit{COLON} { LEXOUT(("v(%s) ", yytext)); return VAR_RRL_RATELIMIT;} ++rrl-whitelist-ratelimit{COLON} { LEXOUT(("v(%s) ", yytext)); return VAR_RRL_WHITELIST_RATELIMIT;} ++rrl-whitelist{COLON} { LEXOUT(("v(%s) ", yytext)); return VAR_RRL_WHITELIST;} + {NEWLINE} { LEXOUT(("NL\n")); cfg_parser->line++;} + + /* Quoted strings. Strip leading and ending quotes */ +--- a/options.c ++++ b/options.c +@@ -14,6 +14,7 @@ + #include "query.h" + #include "tsig.h" + #include "difffile.h" ++#include "rrl.h" + + #include "configyyrename.h" + #include "configparser.h" +@@ -65,6 +66,11 @@ nsd_options_t* nsd_options_create(region + opt->difffile = DIFFFILE; + opt->xfrdfile = XFRDFILE; + opt->xfrd_reload_timeout = 10; ++#ifdef RATELIMIT ++ opt->rrl_size = RRL_BUCKETS; ++ opt->rrl_ratelimit = RRL_LIMIT/2; ++ opt->rrl_whitelist_ratelimit = RRL_WLIST_LIMIT/2; ++#endif + nsd_options = opt; + return opt; + } +@@ -233,6 +239,9 @@ zone_options_t* zone_options_create(regi + zone->provide_xfr = 0; + zone->outgoing_interface = 0; + zone->allow_axfr_fallback = 1; ++#ifdef RATELIMIT ++ zone->rrl_whitelist = 0; ++#endif + return zone; + } + +--- a/options.h ++++ b/options.h +@@ -64,6 +64,15 @@ struct nsd_options { + const char* nsid; + int xfrd_reload_timeout; + ++#ifdef RATELIMIT ++ /** number of buckets in rrl hashtable */ ++ size_t rrl_size; ++ /** max qps for queries, 0 is nolimit */ ++ size_t rrl_ratelimit; ++ /** max qps for whitelisted queries, 0 is nolimit */ ++ size_t rrl_whitelist_ratelimit; ++#endif ++ + region_type* region; + }; + +@@ -87,6 +96,9 @@ struct zone_options { + acl_options_t* notify; + acl_options_t* provide_xfr; + acl_options_t* outgoing_interface; ++#ifdef RATELIMIT ++ uint16_t rrl_whitelist; /* bitmap with rrl types */ ++#endif + uint8_t allow_axfr_fallback; + uint8_t notify_retry; + }; +--- a/Makefile.in ++++ b/Makefile.in +@@ -81,6 +81,7 @@ ALL_OBJECTS = \ + edns.o \ + ipc.o \ + iterated_hash.o \ ++ lookup3.o \ + namedb.o \ + netio.o \ + nsd-checkconf.o \ +@@ -95,6 +96,7 @@ ALL_OBJECTS = \ + rbtree.o \ + rdata.o \ + region-allocator.o \ ++ rrl.o \ + server.o \ + tsig.o \ + tsig-openssl.o \ +@@ -121,6 +123,7 @@ NSD_OBJECTS = \ + edns.o \ + ipc.o \ + iterated_hash.o \ ++ lookup3.o \ + namedb.o \ + netio.o \ + nsd.o \ +@@ -130,6 +133,7 @@ NSD_OBJECTS = \ + rbtree.o \ + rdata.o \ + region-allocator.o \ ++ rrl.o \ + server.o \ + tsig.o \ + tsig-openssl.o \ +@@ -152,6 +156,7 @@ ZONEC_OBJECTS = \ + dns.o \ + edns.o \ + iterated_hash.o \ ++ lookup3.o \ + namedb.o \ + nsec3.o \ + options.o \ +@@ -160,6 +165,7 @@ ZONEC_OBJECTS = \ + rbtree.o \ + rdata.o \ + region-allocator.o \ ++ rrl.o \ + tsig.o \ + tsig-openssl.o \ + util.o \ +@@ -178,6 +184,7 @@ NSD_NOTIFY_OBJECTS = \ + dns.o \ + edns.o \ + iterated_hash.o \ ++ lookup3.o \ + namedb.o \ + nsd-notify.o \ + nsec3.o \ +@@ -187,6 +194,7 @@ NSD_NOTIFY_OBJECTS = \ + rbtree.o \ + rdata.o \ + region-allocator.o \ ++ rrl.o \ + tsig.o \ + tsig-openssl.o \ + util.o +@@ -202,6 +210,7 @@ NSD_XFER_OBJECTS = \ + dns.o \ + edns.o \ + iterated_hash.o \ ++ lookup3.o \ + namedb.o \ + nsd-xfer.o \ + nsec3.o \ +@@ -211,6 +220,7 @@ NSD_XFER_OBJECTS = \ + rbtree.o \ + rdata.o \ + region-allocator.o \ ++ rrl.o \ + tsig.o \ + tsig-openssl.o \ + util.o +@@ -226,6 +236,7 @@ NSD_CHECKCONF_OBJECTS = \ + dns.o \ + edns.o \ + iterated_hash.o \ ++ lookup3.o \ + namedb.o \ + nsd-checkconf.o \ + nsec3.o \ +@@ -235,6 +246,7 @@ NSD_CHECKCONF_OBJECTS = \ + rbtree.o \ + rdata.o \ + region-allocator.o \ ++ rrl.o \ + tsig.o \ + tsig-openssl.o \ + util.o +@@ -252,6 +264,7 @@ NSD_PATCH_OBJECTS = \ + dns.o \ + edns.o \ + iterated_hash.o \ ++ lookup3.o \ + namedb.o \ + nsd-patch.o \ + nsec3.o \ +@@ -261,6 +274,7 @@ NSD_PATCH_OBJECTS = \ + rbtree.o \ + rdata.o \ + region-allocator.o \ ++ rrl.o \ + tsig.o \ + tsig-openssl.o \ + util.o +@@ -280,6 +294,7 @@ CUTEST_OBJECTS = \ + edns.o \ + ipc.o \ + iterated_hash.o \ ++ lookup3.o \ + namedb.o \ + netio.o \ + nsec3.o \ +@@ -288,6 +303,7 @@ CUTEST_OBJECTS = \ + rbtree.o \ + rdata.o \ + region-allocator.o \ ++ rrl.o \ + server.o \ + tsig.o \ + tsig-openssl.o \ +@@ -303,6 +319,7 @@ CUTEST_OBJECTS = \ + cutest_rbtree.o \ + cutest_options.o \ + cutest_region.o \ ++ cutest_rrl.o \ + cutest_util.o \ + cutest.o + +@@ -318,11 +335,11 @@ nsdc.sh: $(srcdir)/nsdc.sh.in config.h + + nsd.conf.sample: $(srcdir)/nsd.conf.sample.in config.h + rm -f nsd.conf.sample +- $(EDIT) $(srcdir)/nsd.conf.sample.in > nsd.conf.sample ++ $(EDIT) $(srcdir)/nsd.conf.sample.in | awk '/RRLconfig'@ratelimit@'/ { while($$0 !~ /.*RRLend.*/) { getline; } getline; } {print} ' > nsd.conf.sample + + nsd.conf.5: $(srcdir)/nsd.conf.5.in config.h + rm -f nsd.conf.5 +- $(EDIT) $(srcdir)/nsd.conf.5.in > nsd.conf.5 ++ $(EDIT) $(srcdir)/nsd.conf.5.in | awk '/rrlstart'@ratelimit@'/ { while($$0 !~ /.*rrlend.*/) { getline; } getline; } {print} ' > nsd.conf.5 + + nsd.8: $(srcdir)/nsd.8.in config.h + rm -f nsd.8 +@@ -488,6 +505,9 @@ cutest_run.o: $(srcdir)/tpkg/cutest/cute + cutest_rbtree.o: $(srcdir)/tpkg/cutest/cutest_rbtree.c + $(COMPILE) -c $(srcdir)/tpkg/cutest/cutest_rbtree.c -o $@ + ++cutest_rrl.o: $(srcdir)/tpkg/cutest/cutest_rrl.c ++ $(COMPILE) -c $(srcdir)/tpkg/cutest/cutest_rrl.c -o $@ ++ + cutest_options.o: $(srcdir)/tpkg/cutest/cutest_options.c + $(COMPILE) -c $(srcdir)/tpkg/cutest/cutest_options.c -o $@ + +@@ -562,13 +582,15 @@ buffer.o: $(srcdir)/buffer.c config.h $( + configlexer.o: configlexer.c $(srcdir)/configyyrename.h config.h $(srcdir)/options.h \ + $(srcdir)/region-allocator.h $(srcdir)/rbtree.h configparser.h + configparser.o: configparser.c config.h $(srcdir)/options.h $(srcdir)/region-allocator.h \ +- $(srcdir)/rbtree.h $(srcdir)/util.h $(srcdir)/configyyrename.h ++ $(srcdir)/rbtree.h $(srcdir)/util.h $(srcdir)/rrl.h $(srcdir)/query.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h $(srcdir)/dns.h $(srcdir)/nsd.h \ ++ $(srcdir)/edns.h $(srcdir)/packet.h $(srcdir)/tsig.h $(srcdir)/configyyrename.h + dbaccess.o: $(srcdir)/dbaccess.c config.h $(srcdir)/dns.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h \ + $(srcdir)/region-allocator.h $(srcdir)/util.h $(srcdir)/rbtree.h $(srcdir)/options.h + dbcreate.o: $(srcdir)/dbcreate.c config.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h \ +- $(srcdir)/region-allocator.h $(srcdir)/util.h $(srcdir)/dns.h $(srcdir)/rbtree.h +-difffile.o: $(srcdir)/difffile.c config.h $(srcdir)/difffile.h $(srcdir)/rbtree.h $(srcdir)/region-allocator.h \ +- $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h $(srcdir)/util.h $(srcdir)/dns.h $(srcdir)/options.h $(srcdir)/packet.h $(srcdir)/rdata.h ++ $(srcdir)/region-allocator.h $(srcdir)/util.h config.h $(srcdir)/dns.h $(srcdir)/rbtree.h ++difffile.o: $(srcdir)/difffile.c config.h $(srcdir)/difffile.h $(srcdir)/rbtree.h \ ++ $(srcdir)/region-allocator.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h $(srcdir)/util.h $(srcdir)/dns.h $(srcdir)/options.h \ ++ $(srcdir)/packet.h $(srcdir)/rdata.h $(srcdir)/nsec3.h + dname.o: $(srcdir)/dname.c config.h $(srcdir)/dns.h $(srcdir)/dname.h $(srcdir)/buffer.h $(srcdir)/region-allocator.h \ + $(srcdir)/util.h $(srcdir)/query.h $(srcdir)/namedb.h $(srcdir)/rbtree.h $(srcdir)/nsd.h $(srcdir)/edns.h $(srcdir)/packet.h $(srcdir)/tsig.h + dns.o: $(srcdir)/dns.c config.h $(srcdir)/dns.h $(srcdir)/zonec.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h \ +@@ -578,41 +600,51 @@ ipc.o: $(srcdir)/ipc.c config.h $(srcdir + $(srcdir)/xfrd-tcp.h $(srcdir)/xfrd.h $(srcdir)/rbtree.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/dns.h $(srcdir)/options.h $(srcdir)/tsig.h $(srcdir)/nsd.h \ + $(srcdir)/edns.h $(srcdir)/xfrd-notify.h + iterated_hash.o: $(srcdir)/iterated_hash.c config.h $(srcdir)/iterated_hash.h ++lookup3.o: $(srcdir)/lookup3.c config.h $(srcdir)/lookup3.h + namedb.o: $(srcdir)/namedb.c config.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h $(srcdir)/region-allocator.h \ + $(srcdir)/util.h $(srcdir)/dns.h $(srcdir)/rbtree.h + netio.o: $(srcdir)/netio.c config.h $(srcdir)/netio.h $(srcdir)/region-allocator.h $(srcdir)/util.h + nsd.o: $(srcdir)/nsd.c config.h $(srcdir)/nsd.h $(srcdir)/dns.h $(srcdir)/edns.h $(srcdir)/buffer.h $(srcdir)/region-allocator.h \ +- $(srcdir)/util.h $(srcdir)/options.h $(srcdir)/rbtree.h $(srcdir)/tsig.h $(srcdir)/dname.h ++ $(srcdir)/util.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/rbtree.h $(srcdir)/options.h $(srcdir)/tsig.h + nsd-checkconf.o: $(srcdir)/nsd-checkconf.c config.h $(srcdir)/tsig.h $(srcdir)/buffer.h \ +- $(srcdir)/region-allocator.h $(srcdir)/util.h $(srcdir)/dname.h $(srcdir)/options.h $(srcdir)/rbtree.h ++ $(srcdir)/region-allocator.h $(srcdir)/util.h config.h $(srcdir)/dname.h $(srcdir)/options.h $(srcdir)/rbtree.h $(srcdir)/rrl.h \ ++ $(srcdir)/query.h $(srcdir)/namedb.h $(srcdir)/dns.h $(srcdir)/nsd.h $(srcdir)/edns.h $(srcdir)/packet.h + nsd-notify.o: $(srcdir)/nsd-notify.c config.h $(srcdir)/tsig.h $(srcdir)/buffer.h $(srcdir)/region-allocator.h \ +- $(srcdir)/util.h $(srcdir)/dname.h $(srcdir)/query.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/dns.h $(srcdir)/rbtree.h \ +- $(srcdir)/region-allocator.h $(srcdir)/nsd.h $(srcdir)/edns.h $(srcdir)/buffer.h $(srcdir)/packet.h $(srcdir)/tsig.h +-nsd-patch.o: $(srcdir)/nsd-patch.c config.h $(srcdir)/options.h $(srcdir)/region-allocator.h $(srcdir)/rbtree.h \ +- $(srcdir)/difffile.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h $(srcdir)/util.h $(srcdir)/dns.h ++ $(srcdir)/util.h config.h $(srcdir)/dname.h $(srcdir)/query.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/dns.h $(srcdir)/rbtree.h \ ++ $(srcdir)/region-allocator.h $(srcdir)/util.h $(srcdir)/nsd.h $(srcdir)/edns.h $(srcdir)/buffer.h $(srcdir)/packet.h $(srcdir)/tsig.h ++nsd-patch.o: $(srcdir)/nsd-patch.c config.h $(srcdir)/options.h $(srcdir)/region-allocator.h \ ++ $(srcdir)/rbtree.h $(srcdir)/difffile.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h $(srcdir)/util.h $(srcdir)/dns.h + nsd-xfer.o: $(srcdir)/nsd-xfer.c config.h $(srcdir)/dname.h $(srcdir)/buffer.h $(srcdir)/region-allocator.h \ +- $(srcdir)/util.h $(srcdir)/dns.h $(srcdir)/packet.h $(srcdir)/namedb.h $(srcdir)/rbtree.h $(srcdir)/query.h $(srcdir)/nsd.h $(srcdir)/edns.h $(srcdir)/tsig.h \ +- $(srcdir)/rdata.h $(srcdir)/tsig-openssl.h $(srcdir)/zonec.h +-nsec3.o: $(srcdir)/nsec3.c config.h $(srcdir)/nsec3.h $(srcdir)/iterated_hash.h $(srcdir)/namedb.h $(srcdir)/dname.h \ +- $(srcdir)/buffer.h $(srcdir)/region-allocator.h $(srcdir)/util.h $(srcdir)/dns.h $(srcdir)/rbtree.h $(srcdir)/nsd.h $(srcdir)/edns.h $(srcdir)/answer.h \ +- $(srcdir)/packet.h $(srcdir)/query.h $(srcdir)/tsig.h +-options.o: $(srcdir)/options.c config.h $(srcdir)/options.h $(srcdir)/region-allocator.h $(srcdir)/rbtree.h \ +- $(srcdir)/query.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h $(srcdir)/util.h $(srcdir)/dns.h $(srcdir)/nsd.h $(srcdir)/edns.h $(srcdir)/packet.h \ +- $(srcdir)/tsig.h $(srcdir)/difffile.h $(srcdir)/configyyrename.h configparser.h ++ $(srcdir)/util.h config.h $(srcdir)/dns.h $(srcdir)/packet.h $(srcdir)/namedb.h $(srcdir)/rbtree.h $(srcdir)/query.h $(srcdir)/nsd.h $(srcdir)/edns.h \ ++ $(srcdir)/tsig.h $(srcdir)/tsig-openssl.h ++nsec3.o: $(srcdir)/nsec3.c config.h $(srcdir)/nsec3.h $(srcdir)/iterated_hash.h $(srcdir)/namedb.h \ ++ $(srcdir)/dname.h $(srcdir)/buffer.h $(srcdir)/region-allocator.h $(srcdir)/util.h $(srcdir)/dns.h $(srcdir)/rbtree.h $(srcdir)/nsd.h $(srcdir)/edns.h \ ++ $(srcdir)/answer.h $(srcdir)/packet.h $(srcdir)/query.h $(srcdir)/tsig.h ++options.o: $(srcdir)/options.c config.h $(srcdir)/options.h $(srcdir)/region-allocator.h \ ++ $(srcdir)/rbtree.h $(srcdir)/query.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h $(srcdir)/util.h $(srcdir)/dns.h $(srcdir)/nsd.h $(srcdir)/edns.h \ ++ $(srcdir)/packet.h $(srcdir)/tsig.h $(srcdir)/rrl.h $(srcdir)/configyyrename.h + packet.o: $(srcdir)/packet.c config.h $(srcdir)/packet.h $(srcdir)/dns.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h \ +- $(srcdir)/region-allocator.h $(srcdir)/util.h $(srcdir)/rbtree.h $(srcdir)/query.h $(srcdir)/nsd.h $(srcdir)/edns.h $(srcdir)/tsig.h $(srcdir)/rdata.h ++ $(srcdir)/region-allocator.h $(srcdir)/util.h config.h $(srcdir)/rbtree.h $(srcdir)/query.h $(srcdir)/nsd.h $(srcdir)/edns.h $(srcdir)/tsig.h \ ++ $(srcdir)/rdata.h + query.o: $(srcdir)/query.c config.h $(srcdir)/answer.h $(srcdir)/dns.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h \ + $(srcdir)/region-allocator.h $(srcdir)/util.h $(srcdir)/rbtree.h $(srcdir)/packet.h $(srcdir)/query.h $(srcdir)/nsd.h $(srcdir)/edns.h $(srcdir)/tsig.h \ +- $(srcdir)/axfr.h $(srcdir)/options.h $(srcdir)/nsec3.h ++ $(srcdir)/axfr.h $(srcdir)/options.h $(srcdir)/nsec3.h config.h + rbtree.o: $(srcdir)/rbtree.c config.h $(srcdir)/rbtree.h $(srcdir)/region-allocator.h + rdata.o: $(srcdir)/rdata.c config.h $(srcdir)/rdata.h $(srcdir)/dns.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h \ + $(srcdir)/region-allocator.h $(srcdir)/util.h $(srcdir)/rbtree.h $(srcdir)/zonec.h + region-allocator.o: $(srcdir)/region-allocator.c config.h $(srcdir)/region-allocator.h $(srcdir)/util.h ++rrl.o: $(srcdir)/rrl.c config.h $(srcdir)/rrl.h $(srcdir)/query.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h \ ++ $(srcdir)/region-allocator.h $(srcdir)/util.h $(srcdir)/dns.h $(srcdir)/rbtree.h $(srcdir)/nsd.h $(srcdir)/edns.h $(srcdir)/packet.h $(srcdir)/tsig.h \ ++ $(srcdir)/lookup3.h $(srcdir)/options.h ++rrl-orig.o: $(srcdir)/rrl-orig.c config.h $(srcdir)/rrl.h $(srcdir)/query.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h \ ++ $(srcdir)/region-allocator.h $(srcdir)/util.h $(srcdir)/dns.h $(srcdir)/rbtree.h $(srcdir)/nsd.h $(srcdir)/edns.h $(srcdir)/packet.h $(srcdir)/tsig.h \ ++ $(srcdir)/lookup3.h $(srcdir)/options.h + server.o: $(srcdir)/server.c config.h $(srcdir)/axfr.h $(srcdir)/nsd.h $(srcdir)/dns.h $(srcdir)/edns.h $(srcdir)/buffer.h \ + $(srcdir)/region-allocator.h $(srcdir)/util.h $(srcdir)/query.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/rbtree.h $(srcdir)/packet.h \ +- $(srcdir)/tsig.h $(srcdir)/netio.h $(srcdir)/xfrd.h $(srcdir)/options.h $(srcdir)/xfrd-tcp.h $(srcdir)/difffile.h $(srcdir)/nsec3.h $(srcdir)/ipc.h ++ $(srcdir)/tsig.h $(srcdir)/netio.h $(srcdir)/xfrd.h $(srcdir)/options.h $(srcdir)/xfrd-tcp.h $(srcdir)/difffile.h $(srcdir)/nsec3.h config.h \ ++ $(srcdir)/ipc.h $(srcdir)/lookup3.h $(srcdir)/rrl.h + tsig.o: $(srcdir)/tsig.c config.h $(srcdir)/tsig.h $(srcdir)/buffer.h $(srcdir)/region-allocator.h $(srcdir)/util.h $(srcdir)/dname.h \ +- $(srcdir)/tsig-openssl.h $(srcdir)/dns.h $(srcdir)/packet.h $(srcdir)/namedb.h $(srcdir)/rbtree.h $(srcdir)/query.h $(srcdir)/nsd.h $(srcdir)/edns.h ++ $(srcdir)/tsig-openssl.h $(srcdir)/dns.h $(srcdir)/packet.h $(srcdir)/namedb.h $(srcdir)/rbtree.h + tsig-openssl.o: $(srcdir)/tsig-openssl.c config.h $(srcdir)/tsig-openssl.h $(srcdir)/region-allocator.h \ + $(srcdir)/tsig.h $(srcdir)/buffer.h $(srcdir)/util.h $(srcdir)/dname.h + util.o: $(srcdir)/util.c config.h $(srcdir)/util.h $(srcdir)/region-allocator.h $(srcdir)/dname.h $(srcdir)/buffer.h \ +@@ -632,7 +664,7 @@ xfrd-tcp.o: $(srcdir)/xfrd-tcp.c config. + zlexer.o: zlexer.c config.h $(srcdir)/zonec.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h \ + $(srcdir)/region-allocator.h $(srcdir)/util.h $(srcdir)/dns.h $(srcdir)/rbtree.h zparser.h + zonec.o: $(srcdir)/zonec.c config.h $(srcdir)/zonec.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h \ +- $(srcdir)/region-allocator.h $(srcdir)/util.h $(srcdir)/dns.h $(srcdir)/rbtree.h $(srcdir)/rdata.h zparser.h $(srcdir)/options.h \ ++ $(srcdir)/region-allocator.h $(srcdir)/util.h config.h $(srcdir)/dns.h $(srcdir)/rbtree.h $(srcdir)/rdata.h $(srcdir)/options.h \ + $(srcdir)/nsec3.h + zparser.o: zparser.c config.h $(srcdir)/dname.h $(srcdir)/buffer.h $(srcdir)/region-allocator.h $(srcdir)/util.h \ + $(srcdir)/namedb.h $(srcdir)/dns.h $(srcdir)/rbtree.h $(srcdir)/zonec.h +@@ -653,20 +685,23 @@ strlcpy.o: $(srcdir)/compat/strlcpy.c co + strptime.o: $(srcdir)/compat/strptime.c + cutest.o: $(srcdir)/tpkg/cutest/cutest.c $(srcdir)/tpkg/cutest/cutest.h + cutest_dname.o: $(srcdir)/tpkg/cutest/cutest_dname.c config.h $(srcdir)/tpkg/cutest/cutest.h \ +- $(srcdir)/region-allocator.h $(srcdir)/dname.h $(srcdir)/buffer.h $(srcdir)/region-allocator.h $(srcdir)/util.h ++ $(srcdir)/region-allocator.h $(srcdir)/dname.h $(srcdir)/buffer.h $(srcdir)/region-allocator.h $(srcdir)/util.h config.h + cutest_dns.o: $(srcdir)/tpkg/cutest/cutest_dns.c config.h $(srcdir)/tpkg/cutest/cutest.h \ + $(srcdir)/region-allocator.h $(srcdir)/dns.h + cutest_iterated_hash.o: $(srcdir)/tpkg/cutest/cutest_iterated_hash.c config.h \ +- $(srcdir)/tpkg/cutest/cutest.h $(srcdir)/region-allocator.h $(srcdir)/util.h $(srcdir)/iterated_hash.h $(srcdir)/dname.h \ +- $(srcdir)/buffer.h $(srcdir)/region-allocator.h $(srcdir)/util.h ++ $(srcdir)/tpkg/cutest/cutest.h $(srcdir)/region-allocator.h $(srcdir)/util.h config.h $(srcdir)/iterated_hash.h \ ++ $(srcdir)/dname.h $(srcdir)/buffer.h $(srcdir)/region-allocator.h $(srcdir)/util.h + cutest_options.o: $(srcdir)/tpkg/cutest/cutest_options.c config.h \ +- $(srcdir)/tpkg/cutest/cutest.h $(srcdir)/region-allocator.h $(srcdir)/options.h $(srcdir)/region-allocator.h \ +- $(srcdir)/rbtree.h $(srcdir)/util.h ++ $(srcdir)/tpkg/cutest/cutest.h $(srcdir)/region-allocator.h $(srcdir)/options.h config.h \ ++ $(srcdir)/region-allocator.h $(srcdir)/rbtree.h $(srcdir)/util.h + cutest_rbtree.o: $(srcdir)/tpkg/cutest/cutest_rbtree.c config.h \ + $(srcdir)/tpkg/cutest/cutest.h $(srcdir)/region-allocator.h $(srcdir)/rbtree.h $(srcdir)/region-allocator.h + cutest_region.o: $(srcdir)/tpkg/cutest/cutest_region.c config.h \ +- $(srcdir)/tpkg/cutest/cutest.h $(srcdir)/region-allocator.h $(srcdir)/util.h $(srcdir)/rbtree.h \ ++ $(srcdir)/tpkg/cutest/cutest.h $(srcdir)/region-allocator.h $(srcdir)/util.h config.h $(srcdir)/rbtree.h \ + $(srcdir)/region-allocator.h ++cutest_rrl.o: $(srcdir)/tpkg/cutest/cutest_rrl.c config.h $(srcdir)/tpkg/cutest/cutest.h \ ++ $(srcdir)/rrl.h $(srcdir)/query.h $(srcdir)/namedb.h $(srcdir)/dname.h $(srcdir)/buffer.h $(srcdir)/region-allocator.h $(srcdir)/util.h \ ++ config.h $(srcdir)/dns.h $(srcdir)/rbtree.h $(srcdir)/nsd.h $(srcdir)/edns.h $(srcdir)/packet.h $(srcdir)/tsig.h + cutest_run.o: $(srcdir)/tpkg/cutest/cutest_run.c config.h $(srcdir)/tpkg/cutest/cutest.h + cutest_util.o: $(srcdir)/tpkg/cutest/cutest_util.c config.h $(srcdir)/tpkg/cutest/cutest.h \ +- $(srcdir)/region-allocator.h $(srcdir)/util.h ++ $(srcdir)/region-allocator.h $(srcdir)/util.h config.h diff -Nru nsd3-3.2.12/debian/patches/series nsd3-3.2.12/debian/patches/series --- nsd3-3.2.12/debian/patches/series 2012-07-19 15:07:28.000000000 +0200 +++ nsd3-3.2.12/debian/patches/series 2013-02-06 14:16:06.000000000 +0100 @@ -5,3 +5,4 @@ 0005-Force-dbdir-to-be-var-lib-nsd3-by-patching-configure.patch 0006-define_MAXHOSTNAMELEN_for_hurd_build.patch 0008-NSEC3-wildcards.patch +0009-nsd-3.2.12-rrl.patch diff -Nru nsd3-3.2.12/debian/rules nsd3-3.2.12/debian/rules --- nsd3-3.2.12/debian/rules 2012-07-19 15:07:28.000000000 +0200 +++ nsd3-3.2.12/debian/rules 2013-02-06 14:16:06.000000000 +0100 @@ -26,6 +26,7 @@ dh $@ override_dh_auto_configure: + autoreconf -fi dh_auto_configure -- \ --with-configdir=/etc/nsd3 \ --with-nsd_conf_file=/etc/nsd3/nsd.conf \ @@ -36,7 +37,8 @@ --with-xfrdfile=/var/lib/nsd3/xfrd.state \ --disable-largefile \ --enable-root-server \ - --enable-mmap + --enable-mmap \ + --enable-ratelimit override_dh_auto_install: dh_auto_install -- DESTDIR=$(CURDIR)/debian/nsd3
--- End Message ---
--- Begin Message ---
- To: OndÅ?ej Surý <ondrej@debian.org>, 699900-done@bugs.debian.org
- Subject: Re: Bug#699900: unblock: nsd3/3.2.12-2
- From: Julien Cristau <jcristau@debian.org>
- Date: Sat, 23 Feb 2013 14:33:14 +0100
- Message-id: <20130223133314.GQ5761@radis.cristau.org>
- In-reply-to: <20130206133202.19885.99478.reportbug@localhost6.localdomain6>
- References: <20130206133202.19885.99478.reportbug@localhost6.localdomain6>
On Wed, Feb 6, 2013 at 14:32:02 +0100, Ondřej Surý wrote: > Package: release.debian.org > Severity: normal > User: release.debian.org@packages.debian.org > Usertags: unblock > > Please unblock package nsd3 > Unblocked. Cheers, JulienAttachment: signature.asc
Description: Digital signature
--- End Message ---