# UNDF: UNDF-2026-000000096
# hadoop-0001: PendingReconstructionBlocks — ArrayList.contains() O(n²) in incrementReplicas()

## Severity
MEDIUM — called on block reconstruction events (not every request), but can degrade under heavy re-replication storms (datanode failures, decommission)

## File
`hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/blockmanagement/PendingReconstructionBlocks.java`

## Lines
227–235 (`PendingBlockInfo.incrementReplicas`)

## Pattern
CWE-407: O(n) List.contains() inside a for loop over newTargets.

```java
// DEFECTIVE
private final List<DatanodeStorageInfo> targets; // ArrayList

void incrementReplicas(DatanodeStorageInfo... newTargets) {
    if (newTargets != null) {
        for (DatanodeStorageInfo newTarget : newTargets) {  // outer O(m)
            if (!targets.contains(newTarget)) {             // inner O(n) scan
                targets.add(newTarget);
            }
        }
    }
}
```

`targets` is declared as `ArrayList` (line 215). Each `contains()` is O(n). For m newTargets
and n existing targets, total cost is O(m*n). Under re-replication storms with many blocks
being simultaneously reconstructed, this becomes a hot path.

## Fix
Change `targets` from `ArrayList` to `LinkedHashSet` (preserves insertion order, O(1) add/contains).
Return as list via `new ArrayList<>(targets)` where needed.

## Speedup
~50x at n=1000 (theoretical); measured in unit test at n=500: see hadoop-0001 test.
