# UNDF: UNDF-2026-000000592
# libvirt-0002: x86ModelFromCPU() x86FeatureFind O(C×F) linear scan per feature per VM start

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

## Location
`src/cpu/cpu_x86.c`, function `x86ModelFromCPU()`, lines 1407–1424

```c
for (i = 0; i < cpu->nfeatures; i++) {         /* outer: all CPU features in def (~50–200) */
    ...
    if (!(feature = x86FeatureFind(map, cpu->features[i].name))) {  /* O(F) linear scan */
        virReportError(...);
        return NULL;
    }
    ...
}
```

`x86FeatureFind()` at line 416:
```c
for (i = 0; i < map->nfeatures; i++) {         /* scans ALL ~500 global features */
    if (STREQ(map->features[i]->name, name))
        return map->features[i];
}
```

## Pattern

`x86ModelFromCPU()` is called during VM start, CPU capability check, and live
migration to build a CPU model from a `virCPUDef`.  For each of the C explicit
CPU features in the domain definition it calls `x86FeatureFind()` which does a
full linear scan of the global feature map (F entries).

Total: O(C × F) ≈ 100 × 500 = 50,000 string comparisons per call.
`x86ModelFromCPU()` is called multiple times per VM start (at minimum twice from
`virCPUx86UpdateLive()` via `x86ModelFromCPU(cpu, map, -1)` and
`x86ModelFromCPU(cpu, map, VIR_CPU_FEATURE_DISABLE)`).

A parallel O(M) linear scan exists in `x86ModelFind()` (line 1355–1364) which
scans all M CPU model definitions by name.

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

```
qemuProcessStart()
  qemuProcessFetchGuestCPU()
  virCPUx86UpdateLive()
    x86ModelFromCPU(cpu, map, -1)           # O(C×F)
    x86ModelFromCPU(cpu, map, DISABLE)      # O(C×F) again
      for (i < cpu->nfeatures)
        x86FeatureFind(map, name)           # O(F) linear scan each call
```

## Speedup

At C=100, F=500: 50,000 comparisons → 100 hash lookups (500× op-count reduction).
Per VM start, with two calls: 100,000 → 200 (500× overall).

## Patch

Index `map->features` in a `GHashTable` keyed by feature name, built once when
the map is loaded.  `x86ModelFind()` similarly benefits from a model-name hash.

```diff
--- a/src/cpu/cpu_x86.c
+++ b/src/cpu/cpu_x86.c
@@ -200,6 +200,8 @@ struct _virCPUx86Map {
     virCPUx86Model **models;
     size_t nmodels;
+    GHashTable *featureByName;   /* char* → virCPUx86Feature*, built at load */
+    GHashTable *modelByName;     /* char* → virCPUx86Model*, built at load */
 };

@@ -416,7 +416,10 @@ x86FeatureFind(virCPUx86Map *map, const char *name)
-    for (i = 0; i < map->nfeatures; i++) {
-        if (STREQ(map->features[i]->name, name))
-            return map->features[i];
-    }
-    return NULL;
+    if (!map->featureByName)
+        return NULL;
+    return g_hash_table_lookup(map->featureByName, name);
 }

@@ -1211,6 +1211,9 @@ x86MapAddFeature(...)
     VIR_APPEND_ELEMENT(map->features, map->nfeatures, feature);
+    if (!map->featureByName)
+        map->featureByName = g_hash_table_new(g_str_hash, g_str_equal);
+    g_hash_table_insert(map->featureByName, feature->name, feature);
 }

@@ -1355,7 +1355,10 @@ x86ModelFind(virCPUx86Map *map, const char *name)
-    for (i = 0; i < map->nmodels; i++) {
-        if (STREQ(map->models[i]->name, name))
-            return map->models[i];
-    }
-    return NULL;
+    if (!map->modelByName)
+        return NULL;
+    return g_hash_table_lookup(map->modelByName, name);
 }

@@ -1769,6 +1769,9 @@ x86MapAddModel(...)
     VIR_APPEND_ELEMENT(map->models, map->nmodels, model);
+    if (!map->modelByName)
+        map->modelByName = g_hash_table_new(g_str_hash, g_str_equal);
+    g_hash_table_insert(map->modelByName, model->name, model);
 }
```

## Complexity
- Before: O(C × F) per `x86ModelFromCPU()` call; O(M) per `x86ModelFind()` call
- After: O(C) per `x86ModelFromCPU()` (hash lookup per feature); O(1) per `x86ModelFind()`
