[Dnsmasq-discuss] [PATCH 0/3] Efficient adblocking via hashing and Bloom filters

[Roman Valls Guimera]

Hello Simon,

First submission ever on dnsmasq, here goes nothing :)

These three patches add --blocklist, which blocks the domains listed in a
file such as the published ad- and malware-filtering domain lists
(i.e HaGeZi Ultimate). No pre-processing nor sorting is needed and takes
around 0,4 seconds to load (for >180.000 entries) because it doesn't 
just mmap() the domain names themselves. Instead, it keeps eight bytes 
per domain name and uses hashing and a bloom filter.

Patch 1 keeps only a sorted array of 64-bit keyed hashes of the names.

Patch 2 (optionally) puts a small Bloom filter in front of it, behind
HAVE_BLOCKLIST_BLOOM... I previously wrote software using Bloom filters
to de-contaminate DNA sequences, hence my bias towards this beautiful
probabilistic data structure over, say, Cuckoo filters, MPH or others.

I tested/benchmarked those other hashes too previously before 
submitting this, I reckon this is the simplest solution I could attain.

Patch 3 also blocks answers which reach a listed name through a CNAME.
Without it, such an answer is cached and a query for the listed name 
is then answered from the cache. AFAIK, --address has the same 
gap today if I'm not mistaken?:

https://lists.thekelleys.org.uk/pipermail/dnsmasq-discuss/2025q3/018320.html

Other relevant threads I went through and relatively on topic:

https://lists.thekelleys.org.uk/pipermail/dnsmasq-discuss/2024q3/017627.html
https://lists.thekelleys.org.uk/pipermail/dnsmasq-discuss/2026q2/018480.html
https://lists.thekelleys.org.uk/pipermail/dnsmasq-discuss/2021q2/014994.html

Here's some informal benchmarks I've run on my OpenWrt BananaPi BPI-R3
router (apologies for the slightly different list name counts between
tests, I fell into benchmarking fatigue after so many tests):

  memory for a 189,000 name list (x86_64):
    address=/name/ lines                    13.9 MB
    --blocklist                              1.5 MB
    --blocklist with the Bloom filter        2.0 MB

  CPU per query, same list, against address= lines (x86_64):
    name not listed                         10.6 us vs 30.2 us
    name listed                              4.5 us vs  5.3 us

  lookup on my router (Cortex-A53, 231,175 names):
                                   name not listed    name listed
    --blocklist                         1198 ns          1108 ns
    --blocklist with the Bloom filter    460 ns          1227 ns

CPU per query is dnsmasq's own, against a stub upstream with the cache
disabled. I can share the benchmarking code too if there's interest.

Future improvements if I see this catching steam: multi-platform SIMD
speedups with https://github.com/simd-everywhere/simde ?

Thanks to Manel for code review pre-submission and Lars for the 
Bloom filter lessons!

Roman Valls Guimera (3):
  Add --blocklist to block the names listed in a file.
  Add an optional Bloom filter in front of the --blocklist search.
  Block answers which go through a CNAME to a --blocklist name.

 Makefile           |   2 +-
 man/dnsmasq.8      |  25 +++-
 src/blocklist.c    | 329 +++++++++++++++++++++++++++++++++++++++++++++
 src/config.h       |  18 ++-
 src/dnsmasq.c      |  16 +++
 src/dnsmasq.h      |  15 ++-
 src/domain-match.c |   7 +-
 src/forward.c      |  60 ++++++++-
 src/option.c       |  11 ++
 9 files changed, 475 insertions(+), 8 deletions(-)
 create mode 100644 src/blocklist.c


base-commit: 03fd0c19efbc68710bf96784adcbb402deef9726
-- 
2.53.0