java-topology/docs/tickets/tomcat-0001-replicationvalve-crosscontext-arraylist-contains.md

tomcat-0001: ReplicationValve cross-context session dedup — ArrayList.contains() O(n²)

Target: Apache Tomcat File: java/org/apache/catalina/ha/tcp/ReplicationValve.java CWE: CWE-407 — Inefficient Algorithmic Complexity Severity: MEDIUM Status: PATCHED

Description

ReplicationValve.registerReplicationSession() accumulates cross-context DeltaSession objects in a ThreadLocal<ArrayList<DeltaSession>>. For each incoming session it checks membership with sessions.contains(session) before adding, where sessions is ArrayList<DeltaSession>.

In Portlet-style deployments the comment in the code explicitly notes that "the Portlet API can include a lot of fragments from same or different applications with session changes." Each call to registerReplicationSession() does a full linear scan of the growing list — O(n) per call — producing O(n²) total work when n sessions are registered for a single request.

// ReplicationValve.java  line 80, 265-275
protected final ThreadLocal<ArrayList<DeltaSession>> crossContextSessions = new ThreadLocal<>();

public void registerReplicationSession(DeltaSession session) {
    List<DeltaSession> sessions = crossContextSessions.get();
    if (sessions != null) {
        if (!sessions.contains(session)) {   // O(n) scan per call → O(n²) total
            sessions.add(session);
        }
    }
}

Fix

Replace ArrayList<DeltaSession> with LinkedHashSet<DeltaSession> in the ThreadLocal initialiser. Set.add() is idempotent so the contains() guard is unnecessary and can be removed entirely.

protected final ThreadLocal<LinkedHashSet<DeltaSession>> crossContextSessions = new ThreadLocal<>();

public void registerReplicationSession(DeltaSession session) {
    LinkedHashSet<DeltaSession> sessions = crossContextSessions.get();
    if (sessions != null) {
        sessions.add(session);   // O(1) — Set deduplicates automatically
    }
}

Callers that iterate sessions (lines 394, 422) are unaffected — LinkedHashSet is Iterable and preserves insertion order.

Patch

defects/tomcat/patch/tomcat-0001.patch

Unit Test

defects/tomcat/unit/TomcatReplicationValveTest.java