# UNDF: UNDF-2026-000000516
# qemu-0001: savevm find_se O(N²) during VM migration load

## Classification
- **Severity:** MEDIUM
- **CWE:** CWE-407 (Inefficient Algorithmic Complexity)
- **Component:** `migration/savevm.c`
- **Function:** `find_se()`, `qemu_loadvm_state_main()`

## Description

`find_se()` performs a linear scan over the `savevm_state.handlers` QTAILQ
list to look up a `SaveStateEntry` by `(idstr, instance_id)`:

```c
static SaveStateEntry *find_se(const char *idstr, uint32_t instance_id)
{
    SaveStateEntry *se;
    QTAILQ_FOREACH(se, &savevm_state.handlers, entry) {
        if (!strcmp(se->idstr, idstr) &&
            (instance_id == se->instance_id || instance_id == se->alias_id))
            return se;
        ...
    }
    return NULL;
}
```

`find_se()` is called from `qemu_loadvm_section_start_full()`, which is called
once per section in the migration stream inside `qemu_loadvm_state_main()`'s
`while (true)` loop. Since each registered handler writes one section, if there
are N registered vmstate handlers the load path calls `find_se()` N times,
each costing O(N) → **O(N²) total**.

`calculate_new_instance_id()` has the same pattern: it scans all handlers
to find the maximum instance_id for a given idstr, called once per
`VMSTATE_INSTANCE_ID_ANY` registration.

With large guest configurations (hundreds of virtio devices, PCIe VFs,
CPUs, RAM regions), N can easily reach 500+, giving ~250,000 unnecessary
strcmp calls on every live migration or snapshot restore.

## Root Cause

`savevm_state.handlers` is a QTAILQ (linked list). No hash index exists for
`(idstr, instance_id)` lookup. Every load-time lookup is O(N).

## Fix

Maintain a `GHashTable *handler_map` keyed by a compound key of
`(idstr, instance_id)` → `SaveStateEntry *`. Insert on
`savevm_state_handler_insert()`, remove on `savevm_state_handler_remove()`.
`find_se()` becomes an O(1) hash lookup.

```c
// In SaveStateEntry registry struct, add:
GHashTable *handler_map;  // key: "<idstr>:instance_id", value: SaveStateEntry*

// find_se becomes:
static SaveStateEntry *find_se(const char *idstr, uint32_t instance_id)
{
    char key[280];
    snprintf(key, sizeof(key), "%s:%u", idstr, instance_id);
    return g_hash_table_lookup(savevm_state.handler_map, key);
}
```

## Overhead Measured

See unit test `QemuSavevmFindSeAlgorithm.java`. At N=500 handlers:
- SLOW (linear scan): ~250,000 strcmp operations
- FAST (hash lookup): ~500 hash operations
- Ratio: ~500x

## Files

- `migration/savevm.c` — `find_se()`, `calculate_new_instance_id()`,
  `savevm_state_handler_insert()`, `savevm_state_handler_remove()`
