159 lines
4.7 KiB
Python
159 lines
4.7 KiB
Python
"""
|
|
evince-0001: CWE-407 — ev-page-accessible children O(N^2) pointer scan
|
|
|
|
ev_page_accessible_get_children() merges links, images, and fields into a
|
|
children list, then classifies each element by calling ev_mapping_list_find()
|
|
(linear GList scan) up to 3 times per element. Cost: O(N * (L+I+F)) = O(N^2).
|
|
|
|
Fix: build GHashTable pointer->mapping before the loop; O(1) per lookup.
|
|
|
|
This test simulates our defect and fix in Python, benchmarks at N=100 and
|
|
N=1000, asserts speedup > 3x.
|
|
"""
|
|
|
|
import time
|
|
import sys
|
|
|
|
PASS = True
|
|
|
|
def simulate_ev_mapping_list_find(mapping_list, data_ptr):
|
|
"""Simulate ev_mapping_list_find: O(N) GList pointer scan."""
|
|
for mapping in mapping_list:
|
|
if mapping["data"] is data_ptr:
|
|
return mapping
|
|
return None
|
|
|
|
|
|
def get_children_defective(links, images, fields):
|
|
"""
|
|
Simulate defective ev_page_accessible_get_children.
|
|
For each child in our merged list, calls linear find 1-3 times.
|
|
O(N^2) where N = len(links) + len(images) + len(fields).
|
|
"""
|
|
children = links + images + fields
|
|
result = []
|
|
ops = 0
|
|
|
|
for mapping in children:
|
|
data = mapping["data"]
|
|
|
|
# Simulate ev_mapping_list_find for links — O(L) scan
|
|
found = None
|
|
for m in links:
|
|
ops += 1
|
|
if m["data"] is data:
|
|
found = m
|
|
break
|
|
|
|
if found is None:
|
|
# Simulate ev_mapping_list_find for images — O(I) scan
|
|
for m in images:
|
|
ops += 1
|
|
if m["data"] is data:
|
|
found = m
|
|
break
|
|
|
|
if found is None:
|
|
# Simulate ev_mapping_list_find for fields — O(F) scan
|
|
for m in fields:
|
|
ops += 1
|
|
if m["data"] is data:
|
|
found = m
|
|
break
|
|
|
|
if found:
|
|
result.append(found)
|
|
|
|
return result, ops
|
|
|
|
|
|
def get_children_fixed(links, images, fields):
|
|
"""
|
|
Simulate fixed ev_page_accessible_get_children.
|
|
Build GHashTable (dict) pointer->mapping before the loop; O(1) lookup.
|
|
O(N) total.
|
|
"""
|
|
# Build hash tables — O(L + I + F)
|
|
link_set = {id(m["data"]): m for m in links}
|
|
image_set = {id(m["data"]): m for m in images}
|
|
field_set = {id(m["data"]): m for m in fields}
|
|
|
|
children = links + images + fields
|
|
result = []
|
|
ops = 0
|
|
|
|
for mapping in children:
|
|
data_id = id(mapping["data"])
|
|
ops += 1 # O(1) hash lookup
|
|
|
|
if data_id in link_set:
|
|
result.append(link_set[data_id])
|
|
elif data_id in image_set:
|
|
result.append(image_set[data_id])
|
|
elif data_id in field_set:
|
|
result.append(field_set[data_id])
|
|
|
|
return result, ops
|
|
|
|
|
|
def make_mappings(n, prefix):
|
|
"""Create n mapping structs with unique data pointers."""
|
|
objects = [object() for _ in range(n)]
|
|
return [{"data": obj, "area": (0, 0, 10, 10), "type": prefix} for obj in objects]
|
|
|
|
|
|
def bench(n_links, n_images, n_fields, label):
|
|
links = make_mappings(n_links, "link")
|
|
images = make_mappings(n_images, "image")
|
|
fields = make_mappings(n_fields, "field")
|
|
|
|
# Correctness check
|
|
result_d, ops_d = get_children_defective(links, images, fields)
|
|
result_f, ops_f = get_children_fixed(links, images, fields)
|
|
assert len(result_d) == len(result_f), f"length mismatch: {len(result_d)} vs {len(result_f)}"
|
|
|
|
# Timing benchmark
|
|
iterations = 200
|
|
|
|
t0 = time.perf_counter()
|
|
for _ in range(iterations):
|
|
get_children_defective(links, images, fields)
|
|
t_defect = time.perf_counter() - t0
|
|
|
|
t0 = time.perf_counter()
|
|
for _ in range(iterations):
|
|
get_children_fixed(links, images, fields)
|
|
t_fixed = time.perf_counter() - t0
|
|
|
|
speedup = t_defect / t_fixed if t_fixed > 0 else float("inf")
|
|
op_ratio = ops_d / ops_f if ops_f > 0 else float("inf")
|
|
|
|
status = "PASS" if speedup > 3.0 else "FAIL"
|
|
print(
|
|
f" [{label}] N={n_links+n_images+n_fields} "
|
|
f"defect_ops={ops_d} fixed_ops={ops_f} "
|
|
f"op_ratio={op_ratio:.1f}x "
|
|
f"time_speedup={speedup:.1f}x {status}"
|
|
)
|
|
return speedup > 3.0
|
|
|
|
|
|
def main():
|
|
global PASS
|
|
print("evince-0001: CWE-407 ev-page-accessible children O(N^2) scan")
|
|
print("=" * 65)
|
|
|
|
ok1 = bench(60, 20, 20, "N=100 (60L+20I+20F)")
|
|
ok2 = bench(600, 200, 200, "N=1000 (600L+200I+200F)")
|
|
ok3 = bench(100, 100, 100, "N=300 equal split")
|
|
# N=20 is dominated by Python function-call overhead; skip timing assertion
|
|
bench(10, 5, 5, "N=20 small (informational)")
|
|
|
|
all_pass = all([ok1, ok2, ok3])
|
|
print()
|
|
print("PASS" if all_pass else "FAIL")
|
|
sys.exit(0 if all_pass else 1)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|