Top domains API returns an incomplete result set — v6.7 regression

[Atesca]

Versions

• Pi-hole: v6.4.3
• Web: v6.6
• FTL: v6.7 (fa65a88)

Platform

• OS and version: Raspberry Pi OS 13.5 (trixie), aarch64
• Platform: Raspberry Pi (bare metal)

Expected behavior

GET /api/stats/top_domains (default count=10) should return the top 10
domains -- the first 10 of the ?count=100 list.

Actual behavior / bug

The default request returns only 2 domains; all lower-count ones are
dropped. ?count=100 on the same instance, same moment, returns the full,
correctly sorted list. So the data is fine -- a small count just discards most
of it.

$ curl -s '.../api/stats/top_domains'            # 2 domains (counts 44, 42)
$ curl -s '.../api/stats/top_domains?count=100'  # full ~100-domain list

Steps to reproduce

Reproduction depends on SHM state, so I isolated the exact selection/output
logic from src/api/stats.c into a standalone C program (inlined below) -- no
running instance needed:

$ cc -Wall -Wextra -O2 -o repro repro.c && ./repro
count= 10  -> [44 42]  (2 visible)
count=100  -> [44 42 35 32 31 24 ...]  (100 visible)

Standalone reproducer (repro.c)

/*
 * Reproducer for a top-K selection bug in Pi-hole FTL v6.7
 * (GET /api/stats/top_domains, src/api/stats.c :: get_top_domains()).
 *
 * Introduced by commit 8f8fd45b ("API: heap-based top-K selection for
 * domains and clients"), which replaced "allocate an array for ALL
 * domains + qsort" with a bounded min-heap of capacity (count * 4).
 *
 * The bug
 * -------
 * The scan loop admits a domain into the heap when its name is not the
 * privacy sentinel and its count is >= 1. It does NOT skip "phantom"
 * slots whose name offset is 0 (domainpos == 0 -> getstr() returns "",
 * which is the uninitialized/recycled sentinel; real names live at
 * offset >= 1 because shmSettings->next_str_pos starts at 1).
 *
 * Those phantom slots are only discarded LATER, in the output loop:
 *
 *     // Skip e.g. recycled domains          (stats.c)
 *     if(top_domains[i].namepos == 0)
 *         continue;
 *
 * With the old unbounded array this was harmless: every domain fit, so
 * skipping a phantom at output time never reduced the visible result.
 * With the bounded heap (default count=10 -> capacity 40), phantom slots
 * with count >= 1 CONSUME heap capacity and evict real domains, which are
 * then never printed. The endpoint returns far fewer than `count` rows.
 *
 * This mirrors a real report: with the default request the endpoint
 * returned only 2 domains (each > 40 queries) while ?count=100 returned
 * the full, correct list of ~100 domains.
 *
 * This file isolates the exact heap/output logic from stats.c (no shared
 * memory, no locks, no cJSON) and feeds it a synthetic domain table.
 *
 * Build & run:
 *     cc -Wall -Wextra -O2 -o repro repro.c && ./repro
 *
 * Expected output (demonstrating the bug):
 *     count= 10  -> 2 visible domains: [44 42]
 *     count=100  -> 100 visible domains: [44 42 35 32 ...]
 * A correct implementation would return 10 visible domains for count=10.
 */

#include <stdio.h>
#include <stdlib.h>

/* Mirrors "struct top_entries" in src/api/stats.c (relevant fields only).
 * namepos == 0 marks a recycled / uninitialized slot (getstr(0) == ""). */
struct top_entries {
    int count;
    unsigned int namepos;
};

/* Verbatim from src/api/stats.c: min-heap sift-down keeping the smallest
 * element at the root so it can be replaced when a larger one is found. */
static void heap_sift_down(struct top_entries *heap, const unsigned int size, unsigned int i)
{
    for(;;)
    {
        unsigned int min = i;
        const unsigned int l = 2*i + 1, r = 2*i + 2;
        if(l < size && heap[l].count < heap[min].count)
            min = l;
        if(r < size && heap[r].count < heap[min].count)
            min = r;
        if(min == i)
            break;
        const struct top_entries tmp = heap[i];
        heap[i] = heap[min];
        heap[min] = tmp;
        i = min;
    }
}

/* qsort subroutine, sort DESC (verbatim from src/api/stats.c). */
static int cmpdesc_te(const void *a, const void *b)
{
    const struct top_entries *elem1 = (const struct top_entries*)a;
    const struct top_entries *elem2 = (const struct top_entries*)b;

    if (elem1->count > elem2->count)
        return -1;
    else if (elem1->count < elem2->count)
        return 1;
    else
        return 0;
}

/* Faithful extraction of get_top_domains()'s selection + output.
 * counts[]  : entry_count per domain slot (blocked ? blockedcount : count-blockedcount)
 * nameposs[]: domainpos per slot; 0 == phantom/recycled (skipped only at output)
 * domains   : number of slots scanned (counters->domains)
 * count     : requested top-K (the ?count= query parameter; default 10)
 * Returns the number of VISIBLE domains emitted. */
static int get_top_domains_sim(const int *counts, const unsigned int *nameposs,
                               unsigned int domains, int count)
{
    /* --- allocation (stats.c) --- */
    const unsigned int k = count > 0 ? (unsigned int)count : 1u;
    const unsigned int heap_cap = (k <= domains / 4) ? k * 4 : domains;
    struct top_entries *top_domains =
        heap_cap > 0 ? calloc(heap_cap, sizeof(struct top_entries)) : NULL;
    if(heap_cap > 0 && top_domains == NULL)
        return -1;

    /* --- scan loop (stats.c): fill / evict the bounded min-heap --- */
    unsigned int heap_size = 0;
    int heap_ready = 0;
    for(unsigned int domainID = 0; domainID < domains; domainID++)
    {
        const int entry_count = counts[domainID];

        /* NOTE: the real code skips only the HIDDEN_DOMAIN privacy
         * sentinel here. A phantom slot (namepos == 0) has getstr() == ""
         * which is NOT HIDDEN_DOMAIN, so it is *not* skipped and is
         * admitted to the heap below. This is the defect. */
        if(entry_count < 1)
            continue;

        if(heap_size < heap_cap)
        {
            top_domains[heap_size].count = entry_count;
            top_domains[heap_size].namepos = nameposs[domainID];
            heap_size++;
        }
        else
        {
            if(!heap_ready)
            {
                for(int j = (int)(heap_size / 2) - 1; j >= 0; j--)
                    heap_sift_down(top_domains, heap_size, (unsigned int)j);
                heap_ready = 1;
            }
            if(entry_count > top_domains[0].count)
            {
                top_domains[0].count = entry_count;
                top_domains[0].namepos = nameposs[domainID];
                heap_sift_down(top_domains, heap_size, 0);
            }
        }
    }

    if(heap_size > 1)
        qsort(top_domains, heap_size, sizeof(*top_domains), cmpdesc_te);

    /* --- output loop (stats.c): phantom slots are discarded only here --- */
    int n = 0;
    printf("count=%3d  -> ", count);
    for(unsigned int i = 0; i < heap_size; i++)
    {
        if(top_domains[i].namepos == 0)   /* "Skip e.g. recycled domains" */
            continue;
        if(top_domains[i].count < 1)
            continue;
        printf("%s%d", n == 0 ? "[" : " ", top_domains[i].count);
        if(++n >= count)
            break;
    }
    printf("%s  (%d visible)\n", n == 0 ? "[" : "]", n);

    free(top_domains);
    return n;
}

int main(void)
{
    /*
     * Synthetic domain table matching the reported instance:
     *   - 38 phantom slots (namepos == 0) with a leftover count of 43,
     *     i.e. counted domains whose name offset is 0.
     *   - the real top domains: 44, 42, 35, 32, 31, ...
     *   - a long tail of low-count real domains.
     *
     * At count=10 the heap capacity is 40. The 38 phantoms plus the two
     * largest real domains (44, 42) fill the heap; every other real domain
     * is evicted. The 38 phantoms are then skipped at output -> only 2 rows.
     */
    int counts[512];
    unsigned int nameposs[512];
    unsigned int m = 0;

    for(int i = 0; i < 38; i++) { counts[m] = 43; nameposs[m] = 0; m++; }

    const int real[] = { 44, 42, 35, 32, 31, 24, 24, 24, 21, 21,
                         14, 13, 12, 11, 10,  9,  8,  7,  6,  5, 4, 3 };
    for(unsigned int i = 0; i < sizeof(real)/sizeof(real[0]); i++)
    { counts[m] = real[i]; nameposs[m] = 1000 + i; m++; }

    for(int i = 0; i < 150; i++) { counts[m] = (i % 2) + 1; nameposs[m] = 5000 + i; m++; }

    printf("domain slots scanned: %u (38 phantom namepos==0 + %zu real + 150 tail)\n\n",
           m, sizeof(real)/sizeof(real[0]));

    get_top_domains_sim(counts, nameposs, m, 10);
    get_top_domains_sim(counts, nameposs, m, 100);

    printf("\nBUG: count=10 returns 2 rows although >=10 real domains exist.\n");
    printf("count=100 works only because heap_cap >= slot count disables eviction.\n");
    return 0;
}

Debug Token

• URL: n/a -- deterministic logic bug, reproducible standalone (see reproducer below).

Screenshots

N/A

Additional context

Regression from commit 8f8fd45b (v6.7), which made get_top_domains() use a
bounded min-heap of capacity count*4 (40 by default) instead of an array over
all domains.

The scan loop admits recycled/uninitialized slots (domainpos == 0, whose
getstr() is "", not HIDDEN_DOMAIN) as long as count-blockedcount >= 1.
These are only skipped later, at output (if(top_domains[i].namepos == 0)).
With the old full-size array that was harmless; with the small heap they consume
capacity and evict real domains, so the response has far fewer than count
rows. Large count grows the heap past the slot count, disabling eviction --
hence ?count=100 works.

Fix: skip these slots in the scan loop, before heap insertion:

if(domain->domainpos == 0)
    continue;

This is exactly what the sibling get_top_clients() already does -- its scan
loop skips recycled slots up front (if(client->ippos == 0) continue;), so it
is not affected. get_top_domains() looks like it simply missed the equivalent
guard and only filters namepos == 0 at output.

Investigation and write-up were AI-assisted, then reviewed and verified.

[DL6ER]

Thanks for the detailed write-up. We have added the missing guard in #2951: get_top_domains() now skips recycled slots in the scan loop, matching what get_top_clients() already does, so both paths handle recycled entries symmetrically again.

One correction on the root cause, though: a domain is only recycled once its count has already dropped to zero, at which point gc.c wipes the whole slot. Such an entry is caught by the existing entry_count < 1 check and never reaches the heap, so it cannot evict the populated slots your reproducer relies on. The only slot that can carry domainpos == 0 together with a positive count is a single empty-name domain (deduplicated to one entry). The change is therefore a robustness/parity fix rather than an explanation for the 10 -> 2 result you saw.

If you can still reproduce the shortfall on a live instance, could you share the real /api/stats/top_domains output for count=10 vs count=100, plus the domain count from /api/info/metrics? That would let us find what is actually being dropped.

[Atesca]

You're right that the recycled-slot path can't be the cause — a domain is only recycled once its count is already 0, and name-dedup leaves at most one empty-name slot, so #2951 is a good parity fix but not what I was hitting. I ran a controlled test, and the actual trigger is the excludeDomains filter.

Same instant, numbers only:

	65 excludeDomains	excludeDomains = []
count=10	n=3, [61, 54, 39]	n=10, [157, 144, 144, 144, 109, 108, 108, 78, 77, 75]
count=100	n=100	n=100

(unique_domains = 2727.)

Clearing the 65-entry list makes count=10 return a full 10 again. The excluded entries are the high-traffic domains (counts 157…75 above); because the filter is compiled before the scan but only applied in the output loop, they still occupy the count*4 = 40-slot heap at count=10 and evict the genuine lower-count domains, which are then dropped at output → 3 visible. At count=100 the 400-slot heap has room, so it looks correct.

[DL6ER]

Confirmed - and reproduced in code review. You have it exactly right: both get_top_domains() and get_top_clients() compile the exclude filter but only apply it in the output loop, after the bounded top-K heap has already truncated the candidates to count*4. A high-count excluded entry therefore occupies a heap slot and evicts a genuine one, which is then never emitted, while the excluded slot itself is dropped at output - so the response ends up shorter than count. A large count grows the heap past the slot count and disables eviction, which is why ?count=100 looked fine.

The fix moves the filter into the scan loop, before heap insertion, so excluded domains and clients never consume heap capacity. That also makes the output-time guard redundant. It is now on #2951 (which therefore fixes the actual under-count, not just the recycled-slot parity), together with a regression test that excludes the top four domains and checks that count=1 still returns a full result.

Thanks for the controlled test - clearing the 65-entry list to bisect it was exactly what pinned this down.