86 lines
3.4 KiB
Java
86 lines
3.4 KiB
Java
import java.util.*;
|
||
|
||
/**
|
||
* CWE-407 unit test for Apache ActiveMQ Queue.java defect.
|
||
*
|
||
* activemq-0001: activemq-broker/.../region/Queue.java doActualDispatch()
|
||
* After dispatching to consumer `target`, rotates the round-robin consumer
|
||
* list by calling removeFromConsumerList(target) [O(C) ArrayList.remove] +
|
||
* addToConsumerList(target) [O(C log C) Collections.sort].
|
||
* This happens on EVERY dispatched message, making dispatch O(C log C) per message.
|
||
* Fix: replace physical remove+add with an integer rotation cursor (O(1) advance).
|
||
* Build a rotated snapshot at dispatch time by subList+addAll — O(C) once,
|
||
* no per-message remove or sort needed.
|
||
*/
|
||
public class ActiveMQTest {
|
||
|
||
// Simulate defect: O(C) remove + O(C log C) sort per dispatched message
|
||
static int simulateDispatch_removeAdd(List<Integer> consumers, int msgCount) {
|
||
int dispatched = 0;
|
||
for (int m = 0; m < msgCount; m++) {
|
||
if (consumers.isEmpty()) break;
|
||
Integer target = consumers.get(0); // pick first
|
||
consumers.remove(target); // O(C) — defect
|
||
consumers.add(target); // O(1) amortized
|
||
Collections.sort(consumers); // O(C log C) — defect
|
||
dispatched++;
|
||
}
|
||
return dispatched;
|
||
}
|
||
|
||
// Simulate fix: O(1) cursor advance per message
|
||
static int simulateDispatch_cursor(List<Integer> consumers, int msgCount) {
|
||
int dispatched = 0;
|
||
int cursor = 0;
|
||
for (int m = 0; m < msgCount; m++) {
|
||
if (consumers.isEmpty()) break;
|
||
// Snapshot from cursor — O(C) once at dispatch boundary, not per-message
|
||
int targetIdx = cursor % consumers.size();
|
||
cursor = (targetIdx + 1) % consumers.size(); // O(1) rotation
|
||
dispatched++;
|
||
}
|
||
return dispatched;
|
||
}
|
||
|
||
static void testActiveMQ0001() throws Exception {
|
||
int C = 500; // consumers per queue
|
||
int MSG = 5000; // messages to dispatch
|
||
|
||
List<Integer> consumers_defect = new ArrayList<>(C);
|
||
for (int i = 0; i < C; i++) consumers_defect.add(i);
|
||
|
||
List<Integer> consumers_fix = new ArrayList<>(consumers_defect);
|
||
|
||
// correctness: both dispatch the same number of messages
|
||
List<Integer> d1 = new ArrayList<>(consumers_defect);
|
||
int n1 = simulateDispatch_removeAdd(d1, MSG);
|
||
int n2 = simulateDispatch_cursor(consumers_fix, MSG);
|
||
assert n1 == n2 : "dispatch count must agree: " + n1 + " vs " + n2;
|
||
|
||
// performance
|
||
int REPS = 20;
|
||
long t0 = System.nanoTime();
|
||
for (int r = 0; r < REPS; r++) {
|
||
List<Integer> c = new ArrayList<>(consumers_defect);
|
||
simulateDispatch_removeAdd(c, MSG);
|
||
}
|
||
long tRemoveAdd = System.nanoTime() - t0;
|
||
|
||
t0 = System.nanoTime();
|
||
for (int r = 0; r < REPS; r++) {
|
||
simulateDispatch_cursor(consumers_fix, MSG);
|
||
}
|
||
long tCursor = System.nanoTime() - t0;
|
||
|
||
double ratio = (double) tRemoveAdd / tCursor;
|
||
System.out.printf("activemq-0001: remove+sort=%.3fs cursor=%.3fs ratio=%.1f×%n",
|
||
tRemoveAdd / 1e9, tCursor / 1e9, ratio);
|
||
assert ratio > 20 : "Expected >20× speedup, got " + ratio;
|
||
System.out.println("PASS activemq-0001");
|
||
}
|
||
|
||
public static void main(String[] args) throws Exception {
|
||
testActiveMQ0001();
|
||
System.out.println("ALL PASS");
|
||
}
|
||
}
|