russell@unturf.com
59ae52c7b4
nova-0001: scheduler/manager.py selected_hosts list → set (273x, CRITICAL) nova-0002: scheduler/host_manager.py lowered_hosts_to_force list → set (43x, HIGH) keystone-0001: api/users.py token_roles list → set (32x, HIGH) crystal-0001: syntax/parser.cr type_vars Array#includes? → Set (25x, CRITICAL) crystal-0002: semantic/restrictions.cr discarded Array#includes? → Set (5x, CRITICAL) dovecot-0001: mail-storage-hooks.c array_lsearch → sort+bsearch (4x, HIGH) wireshark-0001: proto_data.c GSList → wmem_map_t (8x, HIGH) 7 unit tests: 9/9 PASS
120 lines
3.9 KiB
Python
120 lines
3.9 KiB
Python
"""
|
||
CWE-407 unit tests for nova scheduler defects.
|
||
|
||
nova-0001: selected_hosts list → set in manager.py _schedule_alt
|
||
nova-0002: lowered_hosts_to_force list → set in host_manager.py
|
||
"""
|
||
import time
|
||
|
||
|
||
# ---------------------------------------------------------------------------
|
||
# nova-0001: selected_hosts set membership test
|
||
# Simulates the _schedule_alt inner loop pattern:
|
||
# for host in hosts:
|
||
# if host not in selected_hosts: # was list, now set
|
||
# ---------------------------------------------------------------------------
|
||
|
||
def schedule_alt_list(all_hosts, selected):
|
||
"""O(H × S) — selected_hosts is a list (defect)."""
|
||
alts = []
|
||
for host in all_hosts:
|
||
if host not in selected: # O(S) list scan
|
||
alts.append(host)
|
||
return alts
|
||
|
||
|
||
def schedule_alt_set(all_hosts, selected_set):
|
||
"""O(H) — selected_hosts_set is a set (fixed)."""
|
||
alts = []
|
||
for host in all_hosts:
|
||
if host not in selected_set: # O(1) hash probe
|
||
alts.append(host)
|
||
return alts
|
||
|
||
|
||
def test_nova_0001_selected_hosts_set():
|
||
N = 2000
|
||
all_hosts = [f"host-{i}" for i in range(N)]
|
||
selected = all_hosts[:N // 2] # half selected
|
||
selected_set = set(selected)
|
||
|
||
# correctness
|
||
r_list = schedule_alt_list(all_hosts, selected)
|
||
r_set = schedule_alt_set(all_hosts, selected_set)
|
||
assert r_list == r_set, "list and set paths must return identical results"
|
||
|
||
# performance: set must be at least 10× faster
|
||
t0 = time.perf_counter()
|
||
for _ in range(50):
|
||
schedule_alt_list(all_hosts, selected)
|
||
t_list = time.perf_counter() - t0
|
||
|
||
t0 = time.perf_counter()
|
||
for _ in range(50):
|
||
schedule_alt_set(all_hosts, selected_set)
|
||
t_set = time.perf_counter() - t0
|
||
|
||
ratio = t_list / t_set
|
||
print(f"nova-0001: list={t_list:.3f}s set={t_set:.3f}s ratio={ratio:.1f}×")
|
||
assert ratio > 10, f"Expected >10× speedup, got {ratio:.1f}×"
|
||
print("PASS nova-0001")
|
||
|
||
|
||
# ---------------------------------------------------------------------------
|
||
# nova-0002: lowered_hosts_to_force set membership test
|
||
# Simulates _match_forced_hosts inner loop:
|
||
# lowered = [h.lower() for h in hosts_to_force] # list (defect)
|
||
# for (hostname, _) in host_map:
|
||
# if hostname.lower() not in lowered: # O(F) scan
|
||
# ---------------------------------------------------------------------------
|
||
|
||
def match_forced_list(host_map_keys, hosts_to_force):
|
||
"""O(H × F) — list (defect)."""
|
||
lowered = [h.lower() for h in hosts_to_force]
|
||
result = []
|
||
for (hostname, nodename) in host_map_keys:
|
||
if hostname.lower() not in lowered:
|
||
result.append((hostname, nodename))
|
||
return result
|
||
|
||
|
||
def match_forced_set(host_map_keys, hosts_to_force):
|
||
"""O(H) — set (fixed)."""
|
||
lowered = {h.lower() for h in hosts_to_force}
|
||
result = []
|
||
for (hostname, nodename) in host_map_keys:
|
||
if hostname.lower() not in lowered:
|
||
result.append((hostname, nodename))
|
||
return result
|
||
|
||
|
||
def test_nova_0002_forced_hosts_set():
|
||
F = 500
|
||
H = 2000
|
||
hosts_to_force = [f"forced-{i}" for i in range(F)]
|
||
host_map_keys = [(f"host-{i}", f"node-{i}") for i in range(H)]
|
||
|
||
r_list = match_forced_list(host_map_keys, hosts_to_force)
|
||
r_set = match_forced_set(host_map_keys, hosts_to_force)
|
||
assert r_list == r_set
|
||
|
||
t0 = time.perf_counter()
|
||
for _ in range(20):
|
||
match_forced_list(host_map_keys, hosts_to_force)
|
||
t_list = time.perf_counter() - t0
|
||
|
||
t0 = time.perf_counter()
|
||
for _ in range(20):
|
||
match_forced_set(host_map_keys, hosts_to_force)
|
||
t_set = time.perf_counter() - t0
|
||
|
||
ratio = t_list / t_set
|
||
print(f"nova-0002: list={t_list:.3f}s set={t_set:.3f}s ratio={ratio:.1f}×")
|
||
assert ratio > 20, f"Expected >20× speedup, got {ratio:.1f}×"
|
||
print("PASS nova-0002")
|
||
|
||
|
||
if __name__ == "__main__":
|
||
test_nova_0001_selected_hosts_set()
|
||
test_nova_0002_forced_hosts_set()
|
||
print("ALL PASS")
|