# UNDF: UNDF-2026-000000548
# systemd-0002: unit_file_get_list states filter O(U×S) — CWE-407

## Severity
MEDIUM

## Location
`src/shared/install.c` — `unit_file_get_list()`

## Root Cause
Inside `unit_file_get_list()`, the code iterates over all unit files found in
each directory of the unit search path. For each unit file, it calls
`strv_contains(states, unit_file_state_to_string(state))` to check if the
unit's state matches the caller's filter list.

`strv_contains` = `strv_find()` = O(S) linear scan (S = number of states in the
filter). This check is performed once per unit file U, giving O(U × S) total.

In practice, `systemctl list-units --state=STATE1,STATE2,...` can pass S states.
With thousands of units (common on a large system) and S > 1, this degrades
noticeably compared to an O(1) hash lookup.

## Defective Code

```c
// src/shared/install.c  unit_file_get_list()
STRV_FOREACH(dirname, lp.search_path) {
        ...
        FOREACH_DIRENT(de, d, return -errno) {
                ...
                UnitFileState state;
                r = unit_file_lookup_state(scope, &lp, de->d_name, &state);
                if (r < 0)
                        state = UNIT_FILE_BAD;

                if (!strv_isempty(states) &&
                    !strv_contains(states, unit_file_state_to_string(state)))  // O(S) per unit
                        continue;
                ...
        }
}
```

## Call Chain
- `unit_file_get_list(scope, root_dir, states, patterns, ret)`
- Called by `systemctl list-unit-files` with the `--state=` filter

## Complexity
- Before: O(U × S) — U unit files × S state strings scanned per file
- After:  O(U)     — one O(1) hash lookup per unit file

## Fix

```c
int unit_file_get_list(
                RuntimeScope scope,
                const char *root_dir,
                char * const *states,
                char * const *patterns,
                Hashmap **ret) {

        _cleanup_(lookup_paths_done) LookupPaths lp = {};
        _cleanup_hashmap_free_ Hashmap *h = NULL;
+       _cleanup_set_free_ Set *states_set = NULL;
        int r;

        ...

+       /* Build O(1) lookup set for states filter */
+       if (!strv_isempty(states)) {
+               STRV_FOREACH(s, states) {
+                       r = set_put_strdup(&states_set, *s);
+                       if (r < 0)
+                               return r;
+               }
+       }

        STRV_FOREACH(dirname, lp.search_path) {
                ...
                FOREACH_DIRENT(de, d, return -errno) {
                        ...
                        if (!strv_isempty(states) &&
-                           !strv_contains(states, unit_file_state_to_string(state)))
+                           !set_contains(states_set, unit_file_state_to_string(state)))
                                continue;
                        ...
                }
        }
        ...
}
```

## Speedup
At U=5000 units, S=5 states:
- Before: ~25,000 string comparisons
- After:  ~5,000 hash lookups
- Ratio: ~5x (grows linearly with S)

The ratio is modest because S is bounded by the number of valid UnitFileState
values (~10), but the fix is trivially correct and eliminates the linear scan.

## References
- CWE-407: Inefficient Algorithmic Complexity
- `src/basic/set.h` — systemd Set with O(1) lookup
