java-topology/docs/tickets/netbsd-0004.md

netbsd-0004 — CWE-407: pci_resource_is_reserved / setup_iowins / setup_memwins — O(N×R) + O(N²) PCI enumeration

Severity: LOW File: sys/dev/pci/pciconf.c Functions: pci_resource_is_reserved, setup_iowins, setup_memwins CWE: CWE-407 Algorithmic Complexity

Defect

pci_resource_is_reserved() does LIST_FOREACH over pciconf_resource_reservations (O(R)) called per window in setup_iowins/setup_memwins. Plus insertion-sort in get_io_desc/get_mem_desc. O(N×R) + O(N²) for sort during PCI enumeration.

/* per-window reservation check — O(R) each */
int pci_resource_is_reserved(tag, res) {
    LIST_FOREACH(r, &pciconf_resource_reservations, pr_list) {
        if (resource_overlaps(r, res))  // O(R) per call
            return 1;
    }
    return 0;
}

/* called per window during setup_iowins — O(N×R) total */
for (i = 0; i < nwins; i++) {
    if (!pci_resource_is_reserved(tag, &wins[i]))
        assign_window(...);
}

/* insertion sort in get_io_desc — O(N²) */
for (i = 1; i < n; i++) {
    key = descs[i];
    j = i - 1;
    while (j >= 0 && descs[j].base > key.base) { descs[j+1] = descs[j]; j--; }
    descs[j+1] = key;
}

Complexity: O(N×R) for reservation checks + O(N²) for insertion sort during PCI bus enumeration at boot.

Scale

On a system with 64 PCI windows and 32 reservations: 2,048 reservation checks. Insertion sort on 64 descriptors = 4,096 comparisons worst case. Compounds with multiple PCI buses.

Fix

Sorted array + bsearch for O(log R) reservation lookup; qsort once at end instead of insertion sort. Reservation list is built before enumeration and read-only during scan.