russell@unturf.com 9934133dcf whitepaper: 312 sites / 151 ecosystems — wave2+3 defect tables and PDF rebuild

Add 88 new defect entries to HIGH and MEDIUM tables:
  HIGH: mysql-0001/0002, mariadb-0001, redis-0001/0002, valkey-0001/0002, openvpn-0001,
        vlc-0001, prometheus-0001, otel-collector-0001, cockroachdb-0001..0004,
        tidb-0001..0008, kubernetes-0001/0002, go-0001, kotlin-0002, scala-0001,
        allegro5-0001, sdl2-0001, grafana-0001, clickhouse-0001, duckdb-0001,
        mongodb-0001, envoy-0001, istio-0001, cilium-0001, linkerd2-0001,
        linux-0001/0002/0003, tor-0002/0003, curl-0001, julia-0001, lua-0001,
        perl5-0001, nats-0001, spring-0003/0004, tomcat-0001, onos-0002, odl-0002

  MEDIUM: helm-0001, mariadb-0002, openssl-0001/0002, memcached-0001,
          cassandra-0001..0004, flink-0001, storm-0001/0002, zookeeper-0001..0003,
          pip-0001, gradle-0001, nginx-0001, haproxy-0001, caddy-0001, varnish-0001,
          ffmpeg-0001, gstreamer-0001, raylib-0001, love2d-0001, php-0001/0002,
          r-source-0001, cpython-0002, ruby-0001, rabbitmq-0003/0004, activemq-0001,
          ovs-0001, onos-0003, odl-0002, jetty-0001

PDF: 976K

2026-03-27 15:23:43 -04:00

2 KiB

Raw Permalink Blame History

redis-0002: getUpcomingChannelList O(S×C²) quadratic channel membership

Target: redis/redis Severity: MEDIUM CWE: CWE-407 (Inefficient Algorithmic Complexity) File: src/acl.c:1952 (getUpcomingChannelList) Status: PATCHED

Description

getUpcomingChannelList(user *new, user *original) builds a flat linked list (upcoming) of all channel patterns from new's selectors, then for each channel pattern in original's selectors calls listSearchKey(upcoming, ...).

listSearchKey is an O(n) walk of the upcoming list. With S selectors and C channel patterns per selector the upcoming list grows to S×C entries. The outer loop also iterates S×C patterns.

Result: O((S×C)²) in the worst case — quadratic in total channel-pattern count.

In practice, heavily compartmentalized users (many selectors, many channel ACL rules) hit this during ACL SETUSER and at any SUBSCRIBE/PSUBSCRIBE event that triggers client-kill evaluation.

Hot paths

ACL SETUSER — triggers killPubsubClientsIfNeeded, which calls getUpcomingChannelList for each affected client.
SUBSCRIBE / PSUBSCRIBE evaluation when ACL rules restrict channels.

Root cause

src/acl.c:1935–1960:

list *upcoming = listCreate();   // O(S×C) entries
...
while((lpn = listNext(&lpi)) && match) {
    if (!listSearchKey(upcoming, listNodeValue(lpn))) {   // O(S×C) per call
        match = 0;

Fix

Replace the upcoming linked list with a hash table (dictCreate with dictTypeSds or a simple rax). Build the set from new's selectors, then check each of original's channel patterns with O(1) lookup. Total cost becomes O(S×C) instead of O((S×C)²).

See patch: defects/redis/patch/0002-acl-upcoming-channels-dict.patch

Also affects

valkey/valkey — identical getUpcomingChannelList code path.

Ops ratio (unit test)

S=4 selectors, C=50 channels each (200 total):

slow ops: 200 × 200 = 40,000
fast ops: 200 (one pass build) + 200 (O(1) lookups) = 400
speedup: 100×

2 KiB Raw Permalink Blame History Unescape Escape