java-topology/defects/valkey/unit/ValkeyTest.java

import java.util.*;

/**
 * CWE-407 unit tests for Valkey acl.c defects.
 *
 * valkey-0001: src/acl.c ACLSelectorCheckKey()
 *   selector->patterns is a linked list — O(P) stringmatchlen scan per key per selector.
 *   O(S × K × P) total per command (same architecture as redis-0001).
 *   Fix: index exact patterns (no glob chars) in a dict for O(1) lookup.
 *
 * valkey-0002: src/acl.c ACLCheckChannelAgainstList()
 *   selector->channels is a linked list — O(C) scan per channel arg per SUBSCRIBE.
 *   Fix: exact channels indexed in channels_dict for O(1) lookup.
 */
public class ValkeyTest {

    // --- valkey-0001 ---

    static boolean aclCheckKey_list(List<String> patterns, String key) {
        for (String p : patterns) {    // O(P) — defect
            if (key.equals(p)) return true;  // simplified: no glob
        }
        return false;
    }

    static boolean aclCheckKey_dict(Map<String, Boolean> patternDict,
                                    List<String> globPatterns, String key) {
        if (patternDict.containsKey(key)) return true;  // O(1) — fix
        for (String p : globPatterns) if (key.equals(p)) return true;
        return false;
    }

    static void testValkey0001() throws Exception {
        int S = 3;     // selectors per user
        int K = 500;   // keys in MSET
        int P = 50;    // key patterns per selector

        List<String> patterns = new ArrayList<>(P);
        Map<String, Boolean> patternDict = new HashMap<>(P);
        for (int i = 0; i < P; i++) {
            String pat = "keyspace:" + i;
            patterns.add(pat);
            patternDict.put(pat, Boolean.TRUE);
        }

        String[] keys = new String[K];
        for (int i = 0; i < K; i++) keys[i] = "keyspace:" + (P - 1);

        // correctness
        assert aclCheckKey_list(patterns, keys[0]) == aclCheckKey_dict(patternDict, Collections.emptyList(), keys[0]);

        // simulate S selectors × K keys per command
        int REPS = 500;
        long t0 = System.nanoTime();
        for (int r = 0; r < REPS; r++) {
            for (int s = 0; s < S; s++) {
                for (String k : keys) aclCheckKey_list(patterns, k);
            }
        }
        long tList = System.nanoTime() - t0;

        t0 = System.nanoTime();
        for (int r = 0; r < REPS; r++) {
            for (int s = 0; s < S; s++) {
                for (String k : keys) aclCheckKey_dict(patternDict, Collections.emptyList(), k);
            }
        }
        long tDict = System.nanoTime() - t0;

        double ratio = (double) tList / tDict;
        System.out.printf("valkey-0001: list=%.3fs dict=%.3fs ratio=%.1f×%n",
                tList / 1e9, tDict / 1e9, ratio);
        assert ratio > 8 : "Expected >8× speedup, got " + ratio;
        System.out.println("PASS valkey-0001");
    }

    // --- valkey-0002 ---

    static boolean aclCheckChannel_list(List<String> channels, String ch) {
        for (String c : channels) if (ch.equals(c)) return true;  // O(C) — defect
        return false;
    }

    static boolean aclCheckChannel_dict(Map<String, Boolean> dict,
                                        List<String> globs, String ch) {
        if (dict.containsKey(ch)) return true;  // O(1) — fix
        for (String g : globs) if (ch.equals(g)) return true;
        return false;
    }

    static void testValkey0002() throws Exception {
        int S = 3;
        int A = 100;   // channel args in SUBSCRIBE
        int C = 50;    // ACL channel patterns per selector

        List<String> channels = new ArrayList<>(C);
        Map<String, Boolean> chanDict = new HashMap<>(C);
        for (int i = 0; i < C; i++) {
            String ch = "topic:" + i;
            channels.add(ch);
            chanDict.put(ch, Boolean.TRUE);
        }

        String[] args = new String[A];
        for (int i = 0; i < A; i++) args[i] = "topic:" + (C - 1);

        assert aclCheckChannel_list(channels, args[0]) == aclCheckChannel_dict(chanDict, Collections.emptyList(), args[0]);

        int REPS = 2000;
        long t0 = System.nanoTime();
        for (int r = 0; r < REPS; r++) {
            for (int s = 0; s < S; s++) {
                for (String a : args) aclCheckChannel_list(channels, a);
            }
        }
        long tList = System.nanoTime() - t0;

        t0 = System.nanoTime();
        for (int r = 0; r < REPS; r++) {
            for (int s = 0; s < S; s++) {
                for (String a : args) aclCheckChannel_dict(chanDict, Collections.emptyList(), a);
            }
        }
        long tDict = System.nanoTime() - t0;

        double ratio = (double) tList / tDict;
        System.out.printf("valkey-0002: list=%.3fs dict=%.3fs ratio=%.1f×%n",
                tList / 1e9, tDict / 1e9, ratio);
        assert ratio > 4 : "Expected >4× speedup, got " + ratio;
        System.out.println("PASS valkey-0002");
    }

    public static void main(String[] args) throws Exception {
        testValkey0001();
        testValkey0002();
        System.out.println("ALL PASS");
    }
}