Assuming that most queries are for names which are not listed (non-evil
internet), and without a filter, each query costs a full binary search
at every step of the parent walk.
With HAVE_BLOCKLIST_BLOOM defined, each listed name also sets two
bits, one picked by each half of its 64-bit hash, in a bitmap of at
least 16 bits per name built with the list. A name with either bit clear
is not listed, so most unlisted names are answered without a search;
about 1% get through to it anyway.
This costs 2 to 4 bytes per name, depending on where the bitmap size
rounds up to a power of two.
---
One lookup, on a Bananapi BPI-R3 (Cortex-A53) with HaGeZi Ultimate,
231,175 names, best of 8 rounds, medians of 3 runs:
name not listed name listed
without the filter 1198 ns 1108 ns
with it 460 ns 1227 ns
For 189,000 names the filter adds 0.5 MB to the 1.5 MB the hashes take.
False positives measured against the same list: 1.08%, against 1.09%
predicted for two bits at 18 bits a name.
Calibration of the bitmap size (m) and bits per name (k), same router
and list, in a separate run: medians of 3 launches, ns per lookup, false
positives counted over 1,000,000 names not on the list. Bit i of a name
is a + i*b from the two hash halves, so k = 2 is this patch's filter.
bitmap bits/name k false pos. not listed listed
none 1195 1100
256 KiB 9.1 1 10.4% 545 1109
256 KiB 9.1 2 3.9% 462 1161
256 KiB 9.1 3 2.2% 442 1195
256 KiB 9.1 4 1.6% 439 1219
512 KiB 18.1 1 5.4% 542 1133
512 KiB 18.1 2 1.1% 473 1237 this patch
512 KiB 18.1 3 0.36% 460 1328
512 KiB 18.1 4 0.15% 461 1409
1 MiB 36.3 1 2.7% 556 1149
1 MiB 36.3 2 0.29% 520 1280
1 MiB 36.3 3 0.05% 516 1406
1 MiB 36.3 4 0.01% 520 1523
The textbook k = (m/n) ln 2, 12.6 here, gives the fewest false positives
for the memory, but each extra bit is another memory access, and a false
positive costs only one search of about 600 ns.
Past k = 2 or 3 (# of hashes for the bloom filter) the extra probes
"cost more" (cache line locality, etc...) than they save, and
every listed name pays for all k of them.
The bitmap size matters through the cache: on my Cortex-A53 router,
a random bit costs about 14 ns while the bitmap is 256 KiB or
less.
Then, 29 ns at 512 KiB and over 75 ns from 1 MiB, which is why 1 MiB is
slower than 512 KiB despite fewer false positives.
So this patch keeps 16 bits per name and k = 2... I think it's a good
sweet spot for this usecase, please let me know if I'm wrong.
src/blocklist.c | 60 +++++++++++++++++++++++++++++++++++++++++++++++--
src/config.h | 6 +++++
2 files changed, 64 insertions(+), 2 deletions(-)
diff --git a/src/blocklist.c b/src/blocklist.c
index 0d4b98c..22cc4ba 100644
--- a/src/blocklist.c
+++ b/src/blocklist.c
@@ -118,6 +118,40 @@ static int cmp_hash(const void *a, const void *b)
return (x > y) - (x < y);
}
+#ifdef HAVE_BLOCKLIST_BLOOM
+/* A Bloom filter in front of the search. Each name sets two bits of a
+ bitmap with at least 16 bits per name, one picked by each half of its
+ hash. If either bit is clear the name is not listed, which settles
+ most unlisted names without a search. About 1% get through anyway,
+ and those only cost the search. */
+static unsigned char *bloom;
+static u64 bloom_mask;
+
+static void bloom_add(u64 h)
+{
+ u64 a = h & bloom_mask, b = (h >> 32) & bloom_mask;
+
+ bloom[a / 8] |= 1 << (a % 8);
+ bloom[b / 8] |= 1 << (b % 8);
+}
+
+static int bloom_test(u64 h)
+{
+ u64 a = h & bloom_mask, b = (h >> 32) & bloom_mask;
+
+ return (bloom[a / 8] & (1 << (a % 8))) && (bloom[b / 8] & (1 << (b % 8)));
+}
+#endif
+
+static int listed(u64 h)
+{
+#ifdef HAVE_BLOCKLIST_BLOOM
+ if (!bloom_test(h))
+ return 0;
+#endif
+ return bsearch(&h, daemon->blocklist, daemon->blocklist_count, sizeof(u64),
cmp_hash) != NULL;
+}
+
/* Read the --blocklist file: one name per line, ignoring blank lines
and anything after a '#', which is the format of the domain lists
published for ad-blocking. Only a sorted array of 64 bit hashes is
@@ -181,8 +215,31 @@ void blocklist_init(int reload)
goto fail;
fclose(f);
+ f = NULL;
qsort(list, n, sizeof(u64), cmp_hash);
+
+#ifdef HAVE_BLOCKLIST_BLOOM
+ {
+ u64 bits = 64;
+ unsigned char *map;
+ size_t i;
+
+ while (bits < 16 * (u64)n)
+ bits *= 2;
+
+ if (!(map = whine_malloc(bits / 8)))
+ goto fail;
+
+ free(bloom);
+ bloom = map;
+ bloom_mask = bits - 1;
+
+ for (i = 0; i < n; i++)
+ bloom_add(list[i]);
+ }
+#endif
+
free(daemon->blocklist);
daemon->blocklist = list;
daemon->blocklist_count = n;
@@ -224,8 +281,7 @@ int blocklist_match(char *name)
h = hash_label(h, label, p - label);
- if ((++labels > 1 || label == name) &&
- bsearch(&h, daemon->blocklist, daemon->blocklist_count, sizeof(u64),
cmp_hash))
+ if ((++labels > 1 || label == name) && listed(h))
return 1;
p = label > name ? label - 1 : name;
diff --git a/src/config.h b/src/config.h
index c8a2a38..c79060e 100644
--- a/src/config.h
+++ b/src/config.h
@@ -144,6 +144,11 @@ HAVE_BLOCKLIST
--blocklist, using much less memory than the same names as
--address lines.
+HAVE_BLOCKLIST_BLOOM
+ put a Bloom filter in front of the --blocklist search, which makes
+ lookups of names which are not listed about three times faster for
+ two more bytes of memory per name. Needs HAVE_BLOCKLIST.
+
HAVE_LOOP
include functionality to probe for and remove DNS forwarding loops.
@@ -211,6 +216,7 @@ RESOLVFILE
/* #define HAVE_DNSSEC */
/* #define HAVE_NFTSET */
/* #define HAVE_BLOCKLIST */
+/* #define HAVE_BLOCKLIST_BLOOM */
/* Default locations for important system files. */
--
2.53.0
_______________________________________________
Dnsmasq-discuss mailing list
[email protected]
https://lists.thekelleys.org.uk/cgi-bin/mailman/listinfo/dnsmasq-discuss
