# nova-0001 — CWE-407: O(H×G) group_hosts list membership in ServerGroupAffinityFilter

**Severity:** HIGH
**File:** `nova/scheduler/filters/affinity_filter.py`
**Lines:** 150–156
**Status:** PATCHED

## Description

`_GroupAffinityFilter.host_passes()` is called once per candidate host
during VM scheduling.  For each call it does:

```python
group_hosts = (spec_obj.instance_group.hosts    # list of strings
               if spec_obj.instance_group else [])
if group_hosts:
    return host_state.host in group_hosts       # O(G) list scan
```

`spec_obj.instance_group.hosts` is built by `InstanceGroup.get_hosts()`
which returns `list(set(...))`.  For a group of G members and H candidate
hosts evaluated during a single scheduling pass, cost is O(H × G).

With H=500 hosts and G=200 group members this is 100 000 string
comparisons per scheduling request.

Additionally in the same filter class:

```python
policies = (spec_obj.instance_group.policies    # ListOfStringsField
            if spec_obj.instance_group else [])
if self.policy_name not in policies:            # O(P) per host
```

`policies` is a `ListOfStringsField` (a list), so `not in` is O(P) per
call.  With H hosts this is O(H × P).

## Complexity

| Check | Defective | Fixed |
|-------|-----------|-------|
| `host in group_hosts` | O(G) per host | O(1) per host |
| `policy not in policies` | O(P) per host | O(1) per host |

## Fix

Convert `group_hosts` and `policies` to sets before the loop-per-host
check.  Since `host_passes` is called per host, the set should be built
once per scheduling request and cached.  The simplest local fix:

```python
group_hosts = set(spec_obj.instance_group.hosts
                  if spec_obj.instance_group else [])
return host_state.host in group_hosts   # O(1)
```

```python
policies = set(spec_obj.instance_group.policies
               if spec_obj.instance_group else [])
if self.policy_name not in policies:    # O(1)
```

## Patch

See `patch/nova-0001.patch`

## Test

See `unit/NovaAffinityFilterAlgorithm.java`

## Speedup

At H=500 hosts, G=200 group members: ~200× fewer string comparisons.