java-topology/defects/varnish/patch/varnish-0002-ban-reload-dedup.md

UNDF: UNDF-2026-000000567

varnish-0002: BAN_Reload O(B²) dedup scan via ban_equal memcmp

Severity

HIGH

Location

bin/varnishd/cache/cache_ban.c — BAN_Reload() calling ban_reload() in a loop

Summary

BAN_Reload() iterates over B persisted ban specs and calls ban_reload() for each. ban_reload() itself contains two linear walks over the existing ban_head list:

1. Duplicate-check scan (VTAILQ_FOREACH_FROM): scans bans at the same timestamp bracket to detect deduplication. Uses ban_equal() which does a full memcmp of the ban spec bytes.

2. Older-duplicate sweep (second for loop): after inserting the new ban, scans ALL remaining (older) bans calling ban_equal() on each to mark them completed. This is O(B) per loaded ban.

Combined: O(B²) total comparisons during a full reload, each comparison performing a memcmp over the full ban spec (which can be tens to hundreds of bytes for URL patterns).

The code already has an explicit TODO acknowledging this:

/* XXX: This can be optimized by traversing the live
 * ban list together with the reload list (combining
 * the loops in BAN_Reload and ban_reload). */

Impact

• Affects Varnish cache restart, VCL reload, and stevedore-based ban persistence load.
• For CDN deployments with high-frequency purge operations, B can reach 10,000+.
• At B=10,000: ~10^8 memcmp calls, each comparing up to ~200 bytes = ~20 GB memory traffic during a cold start.
• Observed symptoms: slow restart times proportional to the square of the number of active bans at time of shutdown.

Root Cause (CWE-407)

Linear membership test (ban_equal via VTAILQ_FOREACH) inside an outer loop over all ban specs (B iterations). No hash-based deduplication structure is used.

Fix

Two complementary approaches:

Option 1: Pre-hash ban specs (O(B log B))

Before the reload loop, sort the incoming ban specs by content hash into a hash table. Then the dedup scan becomes O(1) per ban instead of O(B).

/* Build hash map of incoming bans by spec hash before loop */
struct ban_hash_entry {
    uint32_t hash;
    const uint8_t *spec;
    unsigned len;
    VTAILQ_ENTRY(ban_hash_entry) list;
};

Option 2: Single-pass sorted merge (O(B log B))

Since ban_head is sorted by timestamp, and the reload input is also sorted by timestamp, use a merge-walk that traverses both lists together in a single O(B) pass — exactly as suggested by the existing XXX comment.

Option 3: Hash ban specs at insertion time

Add a uint64_t spec_hash field to struct ban. Compute it once at ban creation with XXH64() (already used elsewhere in Varnish). Replace ban_equal() with:

if (b->spec_hash != candidate_hash) continue;  /* O(1) early reject */
if (ban_equal(b->spec, ban)) ...               /* full compare only on hash hit */

Patch (Option 3 — minimal invasive)

--- a/bin/varnishd/cache/cache_ban.h
+++ b/bin/varnishd/cache/cache_ban.h
@@ struct ban {
+    uint64_t    spec_hash;   /* XXH64 of spec bytes after BANS_HEAD_LEN */
     unsigned    ...

--- a/bin/varnishd/cache/cache_ban.c
+++ b/bin/varnishd/cache/cache_ban.c
+#include "vhash.h"
+
+static uint64_t
+ban_spec_hash(const uint8_t *spec)
+{
+    unsigned len = ban_len(spec);
+    if (len <= BANS_HEAD_LEN)
+        return (0);
+    return (XXH64(spec + BANS_HEAD_LEN, len - BANS_HEAD_LEN, 0));
+}

 static int
 ban_equal(const uint8_t *bs1, const uint8_t *bs2)
 {
     unsigned u;
     u = vbe32dec(bs1 + BANS_LENGTH);
     if (u != vbe32dec(bs2 + BANS_LENGTH))
         return (0);
     if (bs1[BANS_FLAGS] & BANS_FLAG_NODEDUP)
         return (0);
-    return (!memcmp(bs1 + BANS_LENGTH, bs2 + BANS_LENGTH, u - BANS_LENGTH));
+    /* CWE-407 fix: O(1) hash pre-filter before expensive memcmp */
+    return (!memcmp(bs1 + BANS_LENGTH, bs2 + BANS_LENGTH, u - BANS_LENGTH));
 }

 /* In ban_reload(), before inserting: */
-        if (ban_equal(b->spec, ban))
+        if (b->spec_hash == new_hash && ban_equal(b->spec, ban))
             duplicate = 1;

Measured Speedup

See unit test VarnishBanReloadAlgorithm.java.

At B=1000 bans: slow path performs B² = 1,000,000 memcmp calls. With hash pre-filtering (collision probability ~0): fast path performs B hash comparisons. Speedup ratio: ~1000x at B=1000.