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:

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:

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:

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

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.

2.1 KiB Raw Permalink Blame History Unescape Escape