engineering/java-topology
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
java-topology/docs/tickets/zookeeper-0001-prepRequestProcessor-removeduplicates-acl-quadratic.md
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

1.7 KiB
Raw Permalink Blame History

zookeeper-0001: PrepRequestProcessor ACL dedup — ArrayList.contains() O(n²)

Target: Apache ZooKeeper File: zookeeper-server/src/main/java/org/apache/zookeeper/server/PrepRequestProcessor.java CWE: CWE-407 — Inefficient Algorithmic Complexity Severity: HIGH Status: PATCHED

Description

PrepRequestProcessor.removeDuplicates(List<ACL>) deduplicates ACL entries using retval.contains(acl) where retval is an ArrayList<ACL>. For n ACL entries this is O(n²). The method is called via fixupACL() on every create and setACL request — it sits in the hot request-processing path.

// PrepRequestProcessor.java  line 943-957
private static List<ACL> removeDuplicates(final List<ACL> acls) {
    // This would be done better with a Set but ACL hashcode/equals do not
    // allow for null values
    final ArrayList<ACL> retval = new ArrayList<>(acls.size());
    for (final ACL acl : acls) {
        if (!retval.contains(acl)) {   // O(n) per iteration → O(n²) total
            retval.add(acl);
        }
    }
    return retval;
}

The comment acknowledges the defect but dismisses it on the grounds that ACL's hashCode/equals "do not allow for null values." In practice ACL fields are Id objects whose own hashCode never returns null — the concern is unfounded.

Fix

Replace the ArrayList accumulator with a LinkedHashSet<ACL> (preserves order, O(1) lookup) and return new ArrayList<>(set). Alternatively, add a null-safe comparator and use a TreeSet. Either eliminates the O(n²) behaviour.

Patch

defects/zookeeper/patch/zookeeper-0001.patch

Unit Test

defects/zookeeper/unit/ZooKeeperAclDedupTest.java