# 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

```c
// 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:
```c
#define strv_contains(l, s) (!!strv_find((l), (s)))
```
and `strv_find` is a plain linear scan:
```c
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

```c
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
