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

[Roman Valls]

"No pre-processing nor sorting is needed"

Correction: (post-)sorting at program start (qsort) does happen. I just
wanted to express that no pre-sorting before loading the input file was
needed (manually or automated outside dnsmasq).

On Sat, 10 Oct 2026 at 21:39, Roman Valls Guimera <brainstorm at nopcode.org>
wrote:

> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.thekelleys.org.uk/pipermail/dnsmasq-discuss/attachments/20261011/3ea1860c/attachment.htm>