UNDF: UNDF-2026-000000547

systemd-0001: strv_extend_strv filter_duplicates O(N²) — CWE-407

Severity

HIGH

Location

src/basic/strv.c — strv_extend_strv() and strv_extend_strv_consume()

Root Cause

strv_contains(t, *s) is called inside a loop that iterates over every element of b. strv_contains expands to strv_find(), which is an O(N) linear scan of the entire target array t. As entries are appended to t, each successive membership check scans a longer array. Total cost: O(|b| × |t|) = O(N²).

Defective Code

// src/basic/strv.c  strv_extend_strv()
STRV_FOREACH(s, b) {
        if (filter_duplicates && strv_contains(t, *s))  // O(|t|) per iteration
                continue;
        t[p+i] = strdup(*s);
        ...
}

// src/basic/strv.c  strv_extend_strv_consume()
STRV_FOREACH(s, b) {
        if (strv_contains(t, *s)) {                      // O(|t|) per iteration
                free(*s);
                continue;
        }
        t[p+i] = *s;
        ...
}

strv_contains is defined in src/basic/strv.h as:

#define strv_contains(l, s) (!!strv_find((l), (s)))

and strv_find is a plain linear scan:

char* strv_find(char * const *l, const char *name) {
        STRV_FOREACH(i, l)
                if (streq(*i, name))
                        return *i;
        return NULL;
}

Call Chain

strv_extend_strv(a, b, /*filter_duplicates=*/true) — direct callers throughout codebase
strv_split_and_extend_full() → strv_extend_strv_consume(t, l, filter_duplicates) → O(N²) when filter=true
strv_split_and_extend() is a common wrapper used in config parsing

Complexity

Before: O(N²) — each of N elements checks against growing array of size ~N
After: O(N) — track seen strings in a Set* (systemd's set.h) keyed by string hash

Fix

int strv_extend_strv(char ***a, char * const *b, bool filter_duplicates) {
        size_t p, q, i = 0;

        assert(a);

        q = strv_length(b);
        if (q == 0)
                return 0;

        p = strv_length(*a);
        if (p >= SIZE_MAX - q)
                return -ENOMEM;

        char **t = reallocarray(*a, GREEDY_ALLOC_ROUND_UP(p + q + 1), sizeof(char *));
        if (!t)
                return -ENOMEM;

        t[p] = NULL;
        *a = t;

+       _cleanup_set_free_ Set *seen = NULL;
+       if (filter_duplicates) {
+               /* Pre-populate seen with existing entries */
+               STRV_FOREACH(e, t)
+                       if (set_put_strdup(&seen, *e) < 0)
+                               goto rollback;
+       }

        STRV_FOREACH(s, b) {
-               if (filter_duplicates && strv_contains(t, *s))
+               if (filter_duplicates && set_contains(seen, *s))
                        continue;
+               if (filter_duplicates && set_put_strdup(&seen, *s) < 0)
+                       goto rollback;

                t[p+i] = strdup(*s);
                if (!t[p+i])
                        goto rollback;

                i++;
                t[p+i] = NULL;
        }
        ...
}

The same pattern applies to strv_extend_strv_consume().

Speedup

At N=1000 strings with filter_duplicates=true:

Before: ~500,000 string comparisons
After: ~1,000 hash lookups
Ratio: ~500x

References

CWE-407: Inefficient Algorithmic Complexity
systemd src/basic/set.h — Set* uses Hashmap internally, O(1) average lookup

3.4 KiB Raw Permalink Blame History Unescape Escape