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.8 KiB

Raw Permalink Blame History

onos-0002: PipelineTraceableHitChain addDataPlaneEntity — O(n²) ArrayList membership test

Status

PATCHED

Target

opennetworkinglab/onos

File

core/api/src/main/java/org/onosproject/net/PipelineTraceableHitChain.java

Symptom

addDataPlaneEntity() calls hitChain.contains() on an ArrayList<DataPlaneEntity> before every insert — O(n) linear scan. The method is called inside O(n) loops in OfdpaPipelineTraceable (lines 267 and 683), producing O(n²) total work during pipeline trace chain copying. With deep group-bucket trees (typical in OpenFlow 1.3 table-miss chains), hitChain can contain dozens to hundreds of entries. Each forEach → addDataPlaneEntity copy costs O(n) per element → O(n²) total.

Root cause

// PipelineTraceableHitChain.java:94
public void addDataPlaneEntity(DataPlaneEntity dataPlaneEntity) {
    if (!hitChain.contains(dataPlaneEntity)) {   // O(n) ArrayList scan
        hitChain.add(dataPlaneEntity);
    }
}

hitChain is declared as List<DataPlaneEntity> backed by ArrayList. The dedup check is O(n) per call. Callers iterate over the existing chain and call this method once per element — making every chain copy O(n²).

Call site example (OfdpaPipelineTraceable.java:683):

currentHitChain.hitChain().forEach(newHitChain::addDataPlaneEntity);

With a 50-entry hit chain this issues 50 × 50 = 2500 equality comparisons for a single packet trace.

Fix

Replace ArrayList with LinkedHashSet (insertion-ordered set). contains() becomes O(1); iteration order is preserved; add/remove semantics are unchanged for the callers.

Complexity

Before	After
O(n²) chain copy	O(n) chain copy

Patch

defects/onos/patch/onos-0002-pipeline-hitchain-arraylist-quadratic.patch

Unit test

defects/onos/unit/OnosPipelineHitChainTest.java

1.8 KiB Raw Permalink Blame History Unescape Escape