java-topology/defects/ovs/unit/OvsOffloadProviderTest.java

package unit;

/**
 * CWE-407 unit test: OVS dpif-offload dpif_offload_port_add() linear provider scan
 * Defect: strtok priority loop × LIST_FOR_EACH(collection->list) with strcmp per port-add
 * Fix:    shash (string hash map) keyed by provider type — O(1) lookup
 *
 * slow(): ArrayList-backed provider list, scanned with O(P) strcmp per priority token
 * fast(): HashMap-backed lookup — O(1) per type
 * Assert: slowOps > fastOps * 5   (P=20 providers, T=10 tokens, N=200 ports → ~40000 vs ~2000 ops)
 */
public class OvsOffloadProviderTest {

    static long slowCmpCount;
    static long fastCmpCount;

    /** Slow: linear scan through provider list for each priority name token. */
    static long slow(int providers, int tokens, int ports) {
        // Build provider list
        java.util.List<String> providerTypes = new java.util.ArrayList<>();
        for (int i = 0; i < providers; i++) {
            providerTypes.add("provider-" + i);
        }
        // Build priority token list (search for last half of providers — worst case)
        java.util.List<String> priorityTokens = new java.util.ArrayList<>();
        for (int t = 0; t < tokens; t++) {
            priorityTokens.add("provider-" + (providers - 1 - (t % (providers / 2))));
        }

        slowCmpCount = 0;
        for (int port = 0; port < ports; port++) {
            for (String token : priorityTokens) {
                boolean found = false;
                for (String pType : providerTypes) {
                    slowCmpCount++;
                    if (pType.equals(token)) {
                        found = true;
                        break;
                    }
                }
                if (found) break;
            }
        }
        return slowCmpCount;
    }

    /** Fast: HashMap lookup — O(1) per type per port. */
    static long fast(int providers, int tokens, int ports) {
        java.util.Map<String, String> providerMap = new java.util.HashMap<>();
        for (int i = 0; i < providers; i++) {
            providerMap.put("provider-" + i, "provider-" + i);
        }
        java.util.List<String> priorityTokens = new java.util.ArrayList<>();
        for (int t = 0; t < tokens; t++) {
            priorityTokens.add("provider-" + (providers - 1 - (t % (providers / 2))));
        }

        fastCmpCount = 0;
        for (int port = 0; port < ports; port++) {
            for (String token : priorityTokens) {
                // HashMap.get() is O(1) — no strcmp loop
                fastCmpCount++;   // count the single hashCode+equals call
                if (providerMap.containsKey(token)) {
                    break;
                }
            }
        }
        return fastCmpCount;
    }

    public static void main(String[] args) {
        int P = 20;   // offload providers
        int T = 10;   // priority tokens
        int N = 200;  // ports
        int MULTIPLIER = 5;

        long sOps = slow(P, T, N);
        long fOps = fast(P, T, N);

        System.out.println("P=" + P + " providers, T=" + T + " tokens, N=" + N + " ports");
        System.out.println("slow (list strcmp scan): " + sOps + " comparisons");
        System.out.println("fast (hash map lookup):  " + fOps + " comparisons");

        if (sOps > fOps * MULTIPLIER) {
            System.out.println("1/1 PASS (slow=" + sOps + " > fast*" + MULTIPLIER + "=" + (fOps * MULTIPLIER) + ")");
        } else {
            System.out.println("1/1 FAIL (slow=" + sOps + " not > fast*" + MULTIPLIER + "=" + (fOps * MULTIPLIER) + ")");
            System.exit(1);
        }
    }
}