# UNDF: UNDF-2026-000000591
# libvirt-0001: virCPUx86UpdateLive() addedFeatures g_strv_contains O(F×A) per VM start/migration

## Classification
- **Severity**: MEDIUM
- **CWE**: CWE-407 (Algorithmic Complexity — Inefficient Algorithmic Complexity)
- **Component**: `src/cpu/cpu_x86.c`

## Location
`src/cpu/cpu_x86.c`, function `virCPUx86UpdateLive()`, lines 3189–3222

```c
for (i = 0; i < map->nfeatures; i++) {           /* outer: ALL x86 features (~500) */
    virCPUx86Feature *feature = map->features[i];
    ...
    if (!explicit &&
        model->addedFeatures &&
        g_strv_contains((const char **) model->addedFeatures, feature->name))  /* O(A) */
        ignore = true;
    ...
}
```

## Pattern

`virCPUx86UpdateLive()` is called from `qemuProcessUpdateLiveGuestCPU()` on
every QEMU VM start and live migration.  It iterates all x86 CPU features in
the global CPU map (`map->nfeatures` ≈ 500–800 on a modern host) and for each
feature calls `g_strv_contains()` to test membership in
`model->addedFeatures` — a `NULL`-terminated string array.

`g_strv_contains()` is a GLib O(A) linear string scan.  `A` = number of
features added to the CPU model definition (e.g. Icelake-Server has ~20–50
`addedFeatures`).  Total: O(F × A) ≈ 500 × 50 = 25,000 string comparisons
per VM start, per VM — with the virtio/KVM call chain holding libvirt
driver-level locks.

A secondary O(F×A) pattern exists in `qemuDomainDropAddedCPUFeatures()`
called via `virCPUDefFilterFeatures()` during migration XML serialization
(file `src/qemu/qemu_domain.c`, lines 5367–5371).

## Call Path (semi-hot: every VM start + every live migration)

```
qemuProcessStart()
  qemuProcessFetchGuestCPU()
  qemuProcessUpdateLiveGuestCPU()
    virCPUUpdateLive()
      virCPUx86UpdateLive()          # O(F×A) here
        for (i < map->nfeatures)
          g_strv_contains(model->addedFeatures, ...)   # O(A)
```

## Speedup

At F=500, A=50: 25,000 comparisons → 500 hash lookups (50× reduction).
At F=800, A=100: 80,000 comparisons → 800 hash lookups (100× reduction).

## Patch

Convert `model->addedFeatures` from a `GStrv` (NULL-terminated `char**`) to
a `GHashTable*` keyed by feature name for O(1) membership tests.

```diff
--- a/src/cpu/cpu_x86.c
+++ b/src/cpu/cpu_x86.c
@@ -187,7 +187,7 @@ struct _virCPUx86Model {
     char *name;
     virCPUx86Vendor *vendor;
-    GStrv addedFeatures;
+    GHashTable *addedFeaturesSet;  /* feature name → TRUE, for O(1) lookup */
+    GStrv addedFeatures;           /* kept for serialisation/API compat */
     virCPUx86Data data;
     char **blockers;
 };
@@ -1745,6 +1745,8 @@ x86ModelParseCPUID(...)
         model->addedFeatures[nadded++] = g_strdup(ftname);
+        if (!model->addedFeaturesSet)
+            model->addedFeaturesSet = g_hash_table_new(g_str_hash, g_str_equal);
+        g_hash_table_add(model->addedFeaturesSet, model->addedFeatures[nadded-1]);
     }
@@ -1331,6 +1331,7 @@ x86ModelFree(virCPUx86Model *model)
+    g_clear_pointer(&model->addedFeaturesSet, g_hash_table_unref);
     g_strfreev(model->addedFeatures);
@@ -3219,7 +3219,7 @@ virCPUx86UpdateLive(...)
     if (!explicit &&
-        model->addedFeatures &&
-        g_strv_contains((const char **) model->addedFeatures, feature->name))
+        model->addedFeaturesSet &&
+        g_hash_table_contains(model->addedFeaturesSet, feature->name))
         ignore = true;
```

## Complexity
- Before: O(F × A) — F = map->nfeatures (~500–800), A = addedFeatures count (~20–100)
- After: O(F) — g_hash_table_contains is O(1) average
