ben-manes / caffeine / #5462

100%

push

github

Restore paper-faithful semantics in GDWheelPolicy

Three remaining gaps versus Algorithm 2 of the GD-Wheel paper:

1. evict() never assigned the next-non-empty index back to clockHand[0]
   (== C[1]). The level-1 hand never advanced and the "C[1] wrapped a
   whole round → migration(2)" trigger fired only when wheel[0] became
   completely empty. Net effect: high-cost items in wheel[1+] rarely
   migrated down, and evictions were biased toward whatever queue
   index happened to scan first.

2. migrate() drained at most NQ entries per call because its inner
   loop was bounded by wheel[level].length rather than running to
   queue-empty. Concentrated cost classes left entries stranded in the
   upper wheel until the next full rotation.

3. migrate()'s destination queue index used the source level's hand
   instead of clockHand[level-1] (the destination wheel's hand), and
   reduced modulo the source wheel's length instead of the destination
   wheel's. Observationally equivalent today (all wheels share NQ) but
   wrong per the paper.

With all four corrections (this commit + 7ce1c9b65), GDWheel becomes
competitive again on Systor-style workloads with varying miss
penalties — within ~5pp of Gdsf at 1M cache, beating Camp at every
size on the LUNs I checked. Uniform-penalty traces are unchanged.

Bug 1 was identified by an internal audit; bugs 2 and 3 were
identified by walking the paper's Algorithm 2 against the current
code after the audit's add() fix exposed the regression.

4007 of 4016 branches covered (99.78%)

8206 of 8206 relevant lines covered (100.0%)

1.0 hits per line