#5612

Committed 11 Jul 2026 03:47PM UTC coverage: 71.292% (-28.7%) from 100.0%

Build # #5612

Build Type

push

github

Committed by

ben-manes

Commit Message

Preserve timestamps on a raced same-instance refresh

The automatic refreshIfNeeded path checked for an equal-value reload
before the ABA/ownership check and returned without preserving the
timestamps, so a reload completing after a concurrent put(k,
sameInstance) did a full update — shifting the entry's expiration
forward by the reload's in-flight duration and stomping the write.
Mirror the explicit-refresh fix: check ownership first. An owned
reload installs the value (refreshing metadata even for a same
instance), while a raced reload preserves the write's timestamps and
only notifies REPLACED when the value differs.

Coverage Stats

2957 of 4134 branches covered (71.53%)

3 of 3 new or added lines in 1 file covered. (100.0%)

2408 existing lines in 53 files now uncovered.

5980 of 8388 relevant lines covered (71.29%)

0.71 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

97.7

/caffeine/src/main/java/com/github/benmanes/caffeine/cache/TimerWheel.java

/*
 * Copyright 2017 Ben Manes. All Rights Reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.github.benmanes.caffeine.cache;

import static com.github.benmanes.caffeine.cache.Caffeine.ceilingPowerOfTwo;
import static java.util.Objects.requireNonNull;

import java.lang.ref.ReferenceQueue;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.concurrent.TimeUnit;

import org.jspecify.annotations.Nullable;

import com.google.errorprone.annotations.CanIgnoreReturnValue;
import com.google.errorprone.annotations.Var;

/**
 * A hierarchical timer wheel to add, remove, and fire expiration events in amortized O(1) time. The
 * expiration events are deferred until the timer is advanced, which is performed as part of the
 * cache's maintenance cycle.
 *
 * @author ben.manes@gmail.com (Ben Manes)
 */
@SuppressWarnings("GuardedBy")
final class TimerWheel<K, V> implements Iterable<Node<K, V>> {

  /*
   * A timer wheel [1] stores timer events in buckets on a circular buffer. A bucket represents a
   * coarse time span, e.g. one minute, and holds a doubly-linked list of events. The wheels are
   * structured in a hierarchy (seconds, minutes, hours, days) so that events scheduled in the
   * distant future are cascaded to lower buckets when the wheels rotate. This allows for events
   * to be added, removed, and expired in O(1) time, where expiration occurs for the entire bucket,
   * and the penalty of cascading is amortized by the rotations.
   *
   * [1] Hashed and Hierarchical Timing Wheels
   * http://www.cs.columbia.edu/~nahum/w6998/papers/ton97-timing-wheels.pdf
   */

  static final int[] BUCKETS = { 64, 64, 32, 4, 1 };
  static final long[] SPANS = {
      ceilingPowerOfTwo(TimeUnit.SECONDS.toNanos(1)), // 1.07s
      ceilingPowerOfTwo(TimeUnit.MINUTES.toNanos(1)), // 1.14m
      ceilingPowerOfTwo(TimeUnit.HOURS.toNanos(1)),   // 1.22h
      ceilingPowerOfTwo(TimeUnit.DAYS.toNanos(1)),    // 1.63d
      BUCKETS[3] * ceilingPowerOfTwo(TimeUnit.DAYS.toNanos(1)), // 6.5d
      BUCKETS[3] * ceilingPowerOfTwo(TimeUnit.DAYS.toNanos(1)), // 6.5d
  };
  static final long[] SHIFT = {
      Long.numberOfTrailingZeros(SPANS[0]),
      Long.numberOfTrailingZeros(SPANS[1]),
      Long.numberOfTrailingZeros(SPANS[2]),
      Long.numberOfTrailingZeros(SPANS[3]),
      Long.numberOfTrailingZeros(SPANS[4]),
  };

  final Node<K, V>[][] wheel;

  long nanos;

  @SuppressWarnings({"rawtypes", "unchecked"})
  TimerWheel() {
    wheel = new Node[BUCKETS.length][];
    for (int i = 0; i < wheel.length; i++) {
      wheel[i] = new Node[BUCKETS[i]];
      for (int j = 0; j < wheel[i].length; j++) {
        wheel[i][j] = new Sentinel<>();
      }
    }
  }

  /**
   * Advances the timer and evicts entries that have expired, up to the {@code limit} number of
   * evictions, and returns the unused budget. When the limit is reached the timer is rewound so
   * that the next advance processes the remaining backlog.
   *
   * @param cache the instance that the entries belong to
   * @param currentTimeNanos the current time, in nanoseconds
   * @param limit the maximum number of entries to evict
   * @return the unused portion of the eviction budget; zero if the limit was reached
   */
  @CanIgnoreReturnValue
  @SuppressWarnings("PMD.UnusedAssignment")
  public int advance(BoundedLocalCache<K, V> cache, long currentTimeNanos, @Var int limit) {
    long previousTimeNanos = nanos;
    nanos = currentTimeNanos;

    // If wrapping from negative to non-negative then shift for the delta computation so that
    // the unsigned tick difference is correct. The raw previousTicks is used for the bucket
    // start to stay consistent with how schedule() places timers.
    @Var long previousDelta = previousTimeNanos;
    @Var long currentDelta = currentTimeNanos;
    if ((previousTimeNanos < 0) && (currentTimeNanos >= 0)) {
      previousDelta += Long.MAX_VALUE;
      currentDelta += Long.MAX_VALUE;
    }

    try {
      for (int i = 0; i < SHIFT.length; i++) {
        long delta = ((currentDelta >>> SHIFT[i]) - (previousDelta >>> SHIFT[i]));
        if (delta <= 0L) {
          break;
        }
        long previousTicks = (previousTimeNanos >>> SHIFT[i]);
        limit = expire(cache, i, previousTicks, delta, limit);
        if (limit == 0) {
          // The backlog was not fully drained, so rewind to process it on the next advance
          nanos = previousTimeNanos;
          break;
        }
      }
    } catch (Throwable t) {
      nanos = previousTimeNanos;
      throw t;
    }
    return limit;
  }

  /**
   * Expires entries or reschedules into the proper bucket if still active.
   *
   * @param cache the instance that the entries belong to
   * @param index the timing wheel being operated on
   * @param previousTicks the previous number of ticks
   * @param delta the number of additional ticks
   */
  @SuppressWarnings("Varifier")
  int expire(BoundedLocalCache<K, V> cache, int index,
      long previousTicks, long delta, @Var int limit) {
    Node<K, V>[] timerWheel = wheel[index];
    int mask = timerWheel.length - 1;

    int steps = (int) Math.min(1 + delta, timerWheel.length);
    int start = (int) (previousTicks & mask);
    int end = start + steps;

    for (int i = start; i < end; i++) {
      Node<K, V> sentinel = timerWheel[i & mask];
      Node<K, V> prev = sentinel.getPreviousInVariableOrder();
      @Var Node<K, V> node = sentinel.getNextInVariableOrder();
      sentinel.setPreviousInVariableOrder(sentinel);
      sentinel.setNextInVariableOrder(sentinel);

      while (node != sentinel) {
        Node<K, V> next = node.getNextInVariableOrder();
        node.setPreviousInVariableOrder(null);
        node.setNextInVariableOrder(null);

        try {
          if ((node.getVariableTime() - nanos) > 0) {
            schedule(node);
          } else if (cache.evictEntry(node, RemovalCause.EXPIRED, nanos)) {
            if (--limit == 0) {
              // Leave the unprocessed remainder in the bucket for the next advance to process
              if (next != sentinel) {
                next.setPreviousInVariableOrder(sentinel.getPreviousInVariableOrder());
                sentinel.getPreviousInVariableOrder().setNextInVariableOrder(next);
                sentinel.setPreviousInVariableOrder(prev);
              }
              return 0;
            }
          } else {
            schedule(node);
          }
          node = next;
        } catch (Throwable t) {
          node.setPreviousInVariableOrder(sentinel.getPreviousInVariableOrder());
          node.setNextInVariableOrder(next);
          sentinel.getPreviousInVariableOrder().setNextInVariableOrder(node);
          sentinel.setPreviousInVariableOrder(prev);
          throw t;
        }
      }
    }
    return limit;
  }

  /**
   * Schedules a timer event for the node.
   *
   * @param node the entry in the cache
   */
  public void schedule(Node<K, V> node) {
    Node<K, V> sentinel = findBucket(node.getVariableTime());
    link(sentinel, node);
  }

  /**
   * Reschedules an active timer event for the node.
   *
   * @param node the entry in the cache
   */
  public void reschedule(Node<K, V> node) {
    if (node.getNextInVariableOrder() != null) {
      unlink(node);
      schedule(node);
    }
  }

  /**
   * Removes a timer event for this entry if present.
   *
   * @param node the entry in the cache
   */
  public void deschedule(Node<K, V> node) {
    unlink(node);
    node.setNextInVariableOrder(null);
    node.setPreviousInVariableOrder(null);
  }

  /**
   * Determines the bucket that the timer event should be added to.
   *
   * @param time the time when the event fires
   * @return the sentinel at the head of the bucket
   */
  @SuppressWarnings("Varifier")
  Node<K, V> findBucket(@Var long time) {
    long duration = Math.max(0L, time - nanos);
    if (duration == 0L) {
      time = nanos;
    }

    int length = wheel.length - 1;
    for (int i = 0; i < length; i++) {
      if (duration < SPANS[i + 1]) {
        long ticks = (time >>> SHIFT[i]);
        int index = (int) (ticks & (wheel[i].length - 1));
        return wheel[i][index];
      }
    }
    return wheel[length][0];
  }

  /** Adds the entry at the tail of the bucket's list. */
  void link(Node<K, V> sentinel, Node<K, V> node) {
    node.setPreviousInVariableOrder(sentinel.getPreviousInVariableOrder());
    node.setNextInVariableOrder(sentinel);

    sentinel.getPreviousInVariableOrder().setNextInVariableOrder(node);
    sentinel.setPreviousInVariableOrder(node);
  }

  /** Removes the entry from its bucket, if scheduled. */
  void unlink(Node<K, V> node) {
    Node<K, V> next = node.getNextInVariableOrder();
    if (next != null) {
      Node<K, V> prev = node.getPreviousInVariableOrder();
      next.setPreviousInVariableOrder(prev);
      prev.setNextInVariableOrder(next);
    }
  }

  /** Returns the duration until the next bucket expires, or {@link Long#MAX_VALUE} if none. */
  @SuppressWarnings({"IntLongMath", "Varifier"})
  public long getExpirationDelay() {
    for (int i = 0; i < SHIFT.length; i++) {
      Node<K, V>[] timerWheel = wheel[i];
      long ticks = (nanos >>> SHIFT[i]);

      long spanMask = SPANS[i] - 1;
      int mask = timerWheel.length - 1;
      int start = (int) (ticks & mask);
      int end = start + timerWheel.length;
      for (int j = start; j < end; j++) {
        Node<K, V> sentinel = timerWheel[(j & mask)];
        Node<K, V> next = sentinel.getNextInVariableOrder();
        if (next == sentinel) {
          continue;
        }
        long buckets = (j - start);
        @Var long delay = (buckets << SHIFT[i]) - (nanos & spanMask);
        delay = (delay > 0) ? delay : SPANS[i];

        for (int k = i + 1; k < SHIFT.length; k++) {
          long nextDelay = peekAhead(k);
          delay = Math.min(delay, nextDelay);
        }

        return delay;
      }
    }
    return Long.MAX_VALUE;
  }

  /**
   * Returns the duration when the wheel's next bucket expires, or {@link Long#MAX_VALUE} if empty.
   *
   * @param index the timing wheel being operated on
   */
  @SuppressWarnings("Varifier")
  long peekAhead(int index) {
    long ticks = (nanos >>> SHIFT[index]);
    Node<K, V>[] timerWheel = wheel[index];

    long spanMask = SPANS[index] - 1;
    int mask = timerWheel.length - 1;
    int probe = (int) ((ticks + 1) & mask);
    Node<K, V> sentinel = timerWheel[probe];
    Node<K, V> next = sentinel.getNextInVariableOrder();
    return (next == sentinel) ? Long.MAX_VALUE : (SPANS[index] - (nanos & spanMask));
  }

  /**
   * Returns an iterator roughly ordered by the expiration time from the entries most likely to
   * expire (oldest) to the entries least likely to expire (youngest). The wheels are evaluated in
   * order, but the timers that fall within the bucket's range are not sorted.
   */
  @Override
  public Iterator<Node<K, V>> iterator() {
    return new AscendingIterator();
  }

  /**
   * Returns an iterator roughly ordered by the expiration time from the entries least likely to
   * expire (youngest) to the entries most likely to expire (oldest). The wheels are evaluated in
   * order, but the timers that fall within the bucket's range are not sorted.
   */
  public Iterator<Node<K, V>> descendingIterator() {
    return new DescendingIterator();
  }

  /** An iterator with rough ordering that can be specialized for either direction. */
  abstract class Traverser implements Iterator<Node<K, V>> {
    final long expectedNanos;

    @Nullable Node<K, V> current;
    @Nullable Node<K, V> next;

    Traverser() {
      expectedNanos = nanos;
    }

    @Override
    public boolean hasNext() {
      if (nanos != expectedNanos) {
        throw new ConcurrentModificationException();
      } else if (next != null) {
        return true;
      } else if (isDone()) {
        return false;
      }
      next = computeNext();
      return (next != null);
    }

    @Override
    public Node<K, V> next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      current = next;
      next = null;
      return requireNonNull(current);
    }

    @Nullable Node<K, V> computeNext() {
      @Var var node = (current == null) ? sentinel() : current;
      for (;;) {
        node = traverse(node);
        if (node != sentinel()) {
          return node;
        } else if ((node = goToNextBucket()) != null) {
          continue;
        } else if ((node = goToNextWheel()) != null) {
          continue;
        }
        return null;
      }
    }

    /** Returns if the iteration has completed. */
    abstract boolean isDone();

    /** Returns the sentinel at the current wheel and bucket position. */
    abstract Node<K, V> sentinel();

    /** Returns the node's successor, or the bucket's sentinel if at the end. */
    abstract Node<K, V> traverse(Node<K, V> node);

    /** Returns the sentinel for the wheel's next bucket, or null if the wheel is exhausted. */
    abstract @Nullable Node<K, V> goToNextBucket();

    /** Returns the sentinel for the next wheel's bucket position, or null if no more wheels. */
    abstract @Nullable Node<K, V> goToNextWheel();
  }

  final class AscendingIterator extends Traverser {
    int wheelIndex;
    int steps;

    @Override boolean isDone() {
      return (wheelIndex == wheel.length);
    }
    @Override Node<K, V> sentinel() {
      return wheel[wheelIndex][bucketIndex()];
    }
    @Override Node<K, V> traverse(Node<K, V> node) {
      return node.getNextInVariableOrder();
    }
    @Override @Nullable Node<K, V> goToNextBucket() {
      return (++steps < wheel[wheelIndex].length)
          ? wheel[wheelIndex][bucketIndex()]
          : null;
    }
    @Override @Nullable Node<K, V> goToNextWheel() {
      if (++wheelIndex == wheel.length) {
        return null;
      }
      steps = 0;
      return wheel[wheelIndex][bucketIndex()];
    }
    int bucketIndex() {
      @SuppressWarnings("Varifier")
      int ticks = (int) (nanos >>> SHIFT[wheelIndex]);
      int bucketMask = wheel[wheelIndex].length - 1;
      int bucketOffset = (ticks & bucketMask) + 1;
      return (bucketOffset + steps) & bucketMask;
    }
  }

  final class DescendingIterator extends Traverser {
    int wheelIndex;
    int steps;

    DescendingIterator() {
      wheelIndex = wheel.length - 1;
    }
    @Override boolean isDone() {
      return (wheelIndex == -1);
    }
    @Override Node<K, V> sentinel() {
      return wheel[wheelIndex][bucketIndex()];
    }
    @Override @Nullable Node<K, V> goToNextBucket() {
      return (++steps < wheel[wheelIndex].length)
          ? wheel[wheelIndex][bucketIndex()]
          : null;
    }
    @Override @Nullable Node<K, V> goToNextWheel() {
      if (--wheelIndex < 0) {
        return null;
      }
      steps = 0;
      return wheel[wheelIndex][bucketIndex()];
    }
    @Override Node<K, V> traverse(Node<K, V> node) {
      return node.getPreviousInVariableOrder();
    }
    int bucketIndex() {
      @SuppressWarnings("Varifier")
      int ticks = (int) (nanos >>> SHIFT[wheelIndex]);
      int bucketMask = wheel[wheelIndex].length - 1;
      int bucketOffset = (ticks & bucketMask);
      return (bucketOffset - steps) & bucketMask;
    }
  }

  /** A sentinel for the doubly-linked list in the bucket. */
  static final class Sentinel<K, V> extends Node<K, V> {
    Node<K, V> prev;
    Node<K, V> next;

    Sentinel() {
      prev = next = this;
    }

    @Override public Node<K, V> getPreviousInVariableOrder() {
      return prev;
    }
    @SuppressWarnings({"DataFlowIssue", "NullAway"})
    @Override public void setPreviousInVariableOrder(@Nullable Node<K, V> prev) {
      this.prev = prev;
    }
    @Override public Node<K, V> getNextInVariableOrder() {
      return next;
    }
    @SuppressWarnings({"DataFlowIssue", "NullAway"})
    @Override public void setNextInVariableOrder(@Nullable Node<K, V> next) {
      this.next = next;
    }

    @Override public @Nullable K getKey() { return null; }
    @Override public Object getKeyReference() { throw new UnsupportedOperationException(); }
    @Override public Object getKeyReferenceOrNull() { throw new UnsupportedOperationException(); }
    @Override public @Nullable V getValue() { return null; }
    @Override public Object getValueReference() { throw new UnsupportedOperationException(); }
    @Override public void setValue(V value, @Nullable ReferenceQueue<V> referenceQueue) {}
    @Override public boolean containsValue(Object value) { return false; }
    @Override public boolean isAlive() { return false; }
    @Override public boolean isRetired() { return false; }
    @Override public boolean isDead() { return false; }
    @Override public void retire() {}
    @Override public void die() {}
  }
}

1	/*
2	* Copyright 2017 Ben Manes. All Rights Reserved.
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16	package com.github.benmanes.caffeine.cache;
17
18	import static com.github.benmanes.caffeine.cache.Caffeine.ceilingPowerOfTwo;
19	import static java.util.Objects.requireNonNull;
20
21	import java.lang.ref.ReferenceQueue;
22	import java.util.ConcurrentModificationException;
23	import java.util.Iterator;
24	import java.util.NoSuchElementException;
25	import java.util.concurrent.TimeUnit;
26
27	import org.jspecify.annotations.Nullable;
28
29	import com.google.errorprone.annotations.CanIgnoreReturnValue;
30	import com.google.errorprone.annotations.Var;
31
32	/**
33	* A hierarchical timer wheel to add, remove, and fire expiration events in amortized O(1) time. The
34	* expiration events are deferred until the timer is advanced, which is performed as part of the
35	* cache's maintenance cycle.
36	*
37	* @author ben.manes@gmail.com (Ben Manes)
38	*/
39	@SuppressWarnings("GuardedBy")
40	final class TimerWheel<K, V> implements Iterable<Node<K, V>> {
41
42	/*
43	* A timer wheel [1] stores timer events in buckets on a circular buffer. A bucket represents a
44	* coarse time span, e.g. one minute, and holds a doubly-linked list of events. The wheels are
45	* structured in a hierarchy (seconds, minutes, hours, days) so that events scheduled in the
46	* distant future are cascaded to lower buckets when the wheels rotate. This allows for events
47	* to be added, removed, and expired in O(1) time, where expiration occurs for the entire bucket,
48	* and the penalty of cascading is amortized by the rotations.
49	*
50	* [1] Hashed and Hierarchical Timing Wheels
51	* http://www.cs.columbia.edu/~nahum/w6998/papers/ton97-timing-wheels.pdf
52	*/
53
54	static final int[] BUCKETS = { 64, 64, 32, 4, 1 };	1✔
55	static final long[] SPANS = {	1✔
56	ceilingPowerOfTwo(TimeUnit.SECONDS.toNanos(1)), // 1.07s	1✔
57	ceilingPowerOfTwo(TimeUnit.MINUTES.toNanos(1)), // 1.14m	1✔
58	ceilingPowerOfTwo(TimeUnit.HOURS.toNanos(1)), // 1.22h	1✔
59	ceilingPowerOfTwo(TimeUnit.DAYS.toNanos(1)), // 1.63d	1✔
60	BUCKETS[3] * ceilingPowerOfTwo(TimeUnit.DAYS.toNanos(1)), // 6.5d	1✔
61	BUCKETS[3] * ceilingPowerOfTwo(TimeUnit.DAYS.toNanos(1)), // 6.5d	1✔
62	};
63	static final long[] SHIFT = {	1✔
64	Long.numberOfTrailingZeros(SPANS[0]),	1✔
65	Long.numberOfTrailingZeros(SPANS[1]),	1✔
66	Long.numberOfTrailingZeros(SPANS[2]),	1✔
67	Long.numberOfTrailingZeros(SPANS[3]),	1✔
68	Long.numberOfTrailingZeros(SPANS[4]),	1✔
69	};
70
71	final Node<K, V>[][] wheel;
72
73	long nanos;
74
75	@SuppressWarnings({"rawtypes", "unchecked"})
76	TimerWheel() {	1✔
77	wheel = new Node[BUCKETS.length][];	1✔
78	for (int i = 0; i < wheel.length; i++) {	1✔
79	wheel[i] = new Node[BUCKETS[i]];	1✔
80	for (int j = 0; j < wheel[i].length; j++) {	1✔
81	wheel[i][j] = new Sentinel<>();	1✔
82	}
83	}
84	}	1✔
85
86	/**
87	* Advances the timer and evicts entries that have expired, up to the {@code limit} number of
88	* evictions, and returns the unused budget. When the limit is reached the timer is rewound so
89	* that the next advance processes the remaining backlog.
90	*
91	* @param cache the instance that the entries belong to
92	* @param currentTimeNanos the current time, in nanoseconds
93	* @param limit the maximum number of entries to evict
94	* @return the unused portion of the eviction budget; zero if the limit was reached
95	*/
96	@CanIgnoreReturnValue
97	@SuppressWarnings("PMD.UnusedAssignment")
98	public int advance(BoundedLocalCache<K, V> cache, long currentTimeNanos, @Var int limit) {
99	long previousTimeNanos = nanos;	1✔
100	nanos = currentTimeNanos;	1✔
101
102	// If wrapping from negative to non-negative then shift for the delta computation so that
103	// the unsigned tick difference is correct. The raw previousTicks is used for the bucket
104	// start to stay consistent with how schedule() places timers.
105	@Var long previousDelta = previousTimeNanos;	1✔
106	@Var long currentDelta = currentTimeNanos;	1✔
107	if ((previousTimeNanos < 0) && (currentTimeNanos >= 0)) {	1✔
108	previousDelta += Long.MAX_VALUE;	1✔
109	currentDelta += Long.MAX_VALUE;	1✔
110	}
111
112	try {
113	for (int i = 0; i < SHIFT.length; i++) {	1✔
114	long delta = ((currentDelta >>> SHIFT[i]) - (previousDelta >>> SHIFT[i]));	1✔
115	if (delta <= 0L) {	1✔
116	break;	1✔
117	}
118	long previousTicks = (previousTimeNanos >>> SHIFT[i]);	1✔
119	limit = expire(cache, i, previousTicks, delta, limit);	1✔
120	if (limit == 0) {	1✔
121	// The backlog was not fully drained, so rewind to process it on the next advance
122	nanos = previousTimeNanos;	1✔
123	break;	1✔
124	}
125	}
126	} catch (Throwable t) {	1✔
127	nanos = previousTimeNanos;	1✔
128	throw t;	1✔
129	}	1✔
130	return limit;	1✔
131	}
132
133	/**
134	* Expires entries or reschedules into the proper bucket if still active.
135	*
136	* @param cache the instance that the entries belong to
137	* @param index the timing wheel being operated on
138	* @param previousTicks the previous number of ticks
139	* @param delta the number of additional ticks
140	*/
141	@SuppressWarnings("Varifier")
142	int expire(BoundedLocalCache<K, V> cache, int index,
143	long previousTicks, long delta, @Var int limit) {
144	Node<K, V>[] timerWheel = wheel[index];	1✔
145	int mask = timerWheel.length - 1;	1✔
146
147	int steps = (int) Math.min(1 + delta, timerWheel.length);	1✔
148	int start = (int) (previousTicks & mask);	1✔
149	int end = start + steps;	1✔
150
151	for (int i = start; i < end; i++) {	1✔
152	Node<K, V> sentinel = timerWheel[i & mask];	1✔
153	Node<K, V> prev = sentinel.getPreviousInVariableOrder();	1✔
154	@Var Node<K, V> node = sentinel.getNextInVariableOrder();	1✔
155	sentinel.setPreviousInVariableOrder(sentinel);	1✔
156	sentinel.setNextInVariableOrder(sentinel);	1✔
157
158	while (node != sentinel) {	1✔
159	Node<K, V> next = node.getNextInVariableOrder();	1✔
160	node.setPreviousInVariableOrder(null);	1✔
161	node.setNextInVariableOrder(null);	1✔
162
163	try {
164	if ((node.getVariableTime() - nanos) > 0) {	1✔
165	schedule(node);	1✔
166	} else if (cache.evictEntry(node, RemovalCause.EXPIRED, nanos)) {	1!
167	if (--limit == 0) {	1✔
168	// Leave the unprocessed remainder in the bucket for the next advance to process
169	if (next != sentinel) {	1!
UNCOV 170	next.setPreviousInVariableOrder(sentinel.getPreviousInVariableOrder());	×
UNCOV 171	sentinel.getPreviousInVariableOrder().setNextInVariableOrder(next);	×
UNCOV 172	sentinel.setPreviousInVariableOrder(prev);	×
173	}
174	return 0;	1✔
175	}
176	} else {
UNCOV 177	schedule(node);	×
178	}
179	node = next;	1✔
180	} catch (Throwable t) {	1✔
181	node.setPreviousInVariableOrder(sentinel.getPreviousInVariableOrder());	1✔
182	node.setNextInVariableOrder(next);	1✔
183	sentinel.getPreviousInVariableOrder().setNextInVariableOrder(node);	1✔
184	sentinel.setPreviousInVariableOrder(prev);	1✔
185	throw t;	1✔
186	}	1✔
187	}	1✔
188	}
189	return limit;	1✔
190	}
191
192	/**
193	* Schedules a timer event for the node.
194	*
195	* @param node the entry in the cache
196	*/
197	public void schedule(Node<K, V> node) {
198	Node<K, V> sentinel = findBucket(node.getVariableTime());	1✔
199	link(sentinel, node);	1✔
200	}	1✔
201
202	/**
203	* Reschedules an active timer event for the node.
204	*
205	* @param node the entry in the cache
206	*/
207	public void reschedule(Node<K, V> node) {
208	if (node.getNextInVariableOrder() != null) {	1✔
209	unlink(node);	1✔
210	schedule(node);	1✔
211	}
212	}	1✔
213
214	/**
215	* Removes a timer event for this entry if present.
216	*
217	* @param node the entry in the cache
218	*/
219	public void deschedule(Node<K, V> node) {
220	unlink(node);	1✔
221	node.setNextInVariableOrder(null);	1✔
222	node.setPreviousInVariableOrder(null);	1✔
223	}	1✔
224
225	/**
226	* Determines the bucket that the timer event should be added to.
227	*
228	* @param time the time when the event fires
229	* @return the sentinel at the head of the bucket
230	*/
231	@SuppressWarnings("Varifier")
232	Node<K, V> findBucket(@Var long time) {
233	long duration = Math.max(0L, time - nanos);	1✔
234	if (duration == 0L) {	1✔
235	time = nanos;	1✔
236	}
237
238	int length = wheel.length - 1;	1✔
239	for (int i = 0; i < length; i++) {	1✔
240	if (duration < SPANS[i + 1]) {	1✔
241	long ticks = (time >>> SHIFT[i]);	1✔
242	int index = (int) (ticks & (wheel[i].length - 1));	1✔
243	return wheel[i][index];	1✔
244	}
245	}
246	return wheel[length][0];	1✔
247	}
248
249	/** Adds the entry at the tail of the bucket's list. */
250	void link(Node<K, V> sentinel, Node<K, V> node) {
251	node.setPreviousInVariableOrder(sentinel.getPreviousInVariableOrder());	1✔
252	node.setNextInVariableOrder(sentinel);	1✔
253
254	sentinel.getPreviousInVariableOrder().setNextInVariableOrder(node);	1✔
255	sentinel.setPreviousInVariableOrder(node);	1✔
256	}	1✔
257
258	/** Removes the entry from its bucket, if scheduled. */
259	void unlink(Node<K, V> node) {
260	Node<K, V> next = node.getNextInVariableOrder();	1✔
261	if (next != null) {	1✔
262	Node<K, V> prev = node.getPreviousInVariableOrder();	1✔
263	next.setPreviousInVariableOrder(prev);	1✔
264	prev.setNextInVariableOrder(next);	1✔
265	}
266	}	1✔
267
268	/** Returns the duration until the next bucket expires, or {@link Long#MAX_VALUE} if none. */
269	@SuppressWarnings({"IntLongMath", "Varifier"})
270	public long getExpirationDelay() {
271	for (int i = 0; i < SHIFT.length; i++) {	1✔
272	Node<K, V>[] timerWheel = wheel[i];	1✔
273	long ticks = (nanos >>> SHIFT[i]);	1✔
274
275	long spanMask = SPANS[i] - 1;	1✔
276	int mask = timerWheel.length - 1;	1✔
277	int start = (int) (ticks & mask);	1✔
278	int end = start + timerWheel.length;	1✔
279	for (int j = start; j < end; j++) {	1✔
280	Node<K, V> sentinel = timerWheel[(j & mask)];	1✔
281	Node<K, V> next = sentinel.getNextInVariableOrder();	1✔
282	if (next == sentinel) {	1✔
283	continue;	1✔
284	}
285	long buckets = (j - start);	1✔
286	@Var long delay = (buckets << SHIFT[i]) - (nanos & spanMask);	1✔
287	delay = (delay > 0) ? delay : SPANS[i];	1✔
288
289	for (int k = i + 1; k < SHIFT.length; k++) {	1✔
290	long nextDelay = peekAhead(k);	1✔
291	delay = Math.min(delay, nextDelay);	1✔
292	}
293
294	return delay;	1✔
295	}
296	}
297	return Long.MAX_VALUE;	1✔
298	}
299
300	/**
301	* Returns the duration when the wheel's next bucket expires, or {@link Long#MAX_VALUE} if empty.
302	*
303	* @param index the timing wheel being operated on
304	*/
305	@SuppressWarnings("Varifier")
306	long peekAhead(int index) {
307	long ticks = (nanos >>> SHIFT[index]);	1✔
308	Node<K, V>[] timerWheel = wheel[index];	1✔
309
310	long spanMask = SPANS[index] - 1;	1✔
311	int mask = timerWheel.length - 1;	1✔
312	int probe = (int) ((ticks + 1) & mask);	1✔
313	Node<K, V> sentinel = timerWheel[probe];	1✔
314	Node<K, V> next = sentinel.getNextInVariableOrder();	1✔
315	return (next == sentinel) ? Long.MAX_VALUE : (SPANS[index] - (nanos & spanMask));	1✔
316	}
317
318	/**
319	* Returns an iterator roughly ordered by the expiration time from the entries most likely to
320	* expire (oldest) to the entries least likely to expire (youngest). The wheels are evaluated in
321	* order, but the timers that fall within the bucket's range are not sorted.
322	*/
323	@Override
324	public Iterator<Node<K, V>> iterator() {
325	return new AscendingIterator();	1✔
326	}
327
328	/**
329	* Returns an iterator roughly ordered by the expiration time from the entries least likely to
330	* expire (youngest) to the entries most likely to expire (oldest). The wheels are evaluated in
331	* order, but the timers that fall within the bucket's range are not sorted.
332	*/
333	public Iterator<Node<K, V>> descendingIterator() {
334	return new DescendingIterator();	1✔
335	}
336
337	/** An iterator with rough ordering that can be specialized for either direction. */
338	abstract class Traverser implements Iterator<Node<K, V>> {
339	final long expectedNanos;
340
341	@Nullable Node<K, V> current;
342	@Nullable Node<K, V> next;
343
344	Traverser() {	1✔
345	expectedNanos = nanos;	1✔
346	}	1✔
347
348	@Override
349	public boolean hasNext() {
350	if (nanos != expectedNanos) {	1!
UNCOV 351	throw new ConcurrentModificationException();	×
352	} else if (next != null) {	1✔
353	return true;	1✔
354	} else if (isDone()) {	1✔
355	return false;	1✔
356	}
357	next = computeNext();	1✔
358	return (next != null);	1✔
359	}
360
361	@Override
362	public Node<K, V> next() {
363	if (!hasNext()) {	1✔
364	throw new NoSuchElementException();	1✔
365	}
366	current = next;	1✔
367	next = null;	1✔
368	return requireNonNull(current);	1✔
369	}
370
371	@Nullable Node<K, V> computeNext() {
372	@Var var node = (current == null) ? sentinel() : current;	1✔
373	for (;;) {
374	node = traverse(node);	1✔
375	if (node != sentinel()) {	1✔
376	return node;	1✔
377	} else if ((node = goToNextBucket()) != null) {	1✔
378	continue;	1✔
379	} else if ((node = goToNextWheel()) != null) {	1✔
380	continue;	1✔
381	}
382	return null;	1✔
383	}
384	}
385
386	/** Returns if the iteration has completed. */
387	abstract boolean isDone();
388
389	/** Returns the sentinel at the current wheel and bucket position. */
390	abstract Node<K, V> sentinel();
391
392	/** Returns the node's successor, or the bucket's sentinel if at the end. */
393	abstract Node<K, V> traverse(Node<K, V> node);
394
395	/** Returns the sentinel for the wheel's next bucket, or null if the wheel is exhausted. */
396	abstract @Nullable Node<K, V> goToNextBucket();
397
398	/** Returns the sentinel for the next wheel's bucket position, or null if no more wheels. */
399	abstract @Nullable Node<K, V> goToNextWheel();
400	}
401
402	final class AscendingIterator extends Traverser {	1✔
403	int wheelIndex;
404	int steps;
405
406	@Override boolean isDone() {
407	return (wheelIndex == wheel.length);	1✔
408	}
409	@Override Node<K, V> sentinel() {
410	return wheel[wheelIndex][bucketIndex()];	1✔
411	}
412	@Override Node<K, V> traverse(Node<K, V> node) {
413	return node.getNextInVariableOrder();	1✔
414	}
415	@Override @Nullable Node<K, V> goToNextBucket() {
416	return (++steps < wheel[wheelIndex].length)	1✔
417	? wheel[wheelIndex][bucketIndex()]	1✔
418	: null;	1✔
419	}
420	@Override @Nullable Node<K, V> goToNextWheel() {
421	if (++wheelIndex == wheel.length) {	1✔
422	return null;	1✔
423	}
424	steps = 0;	1✔
425	return wheel[wheelIndex][bucketIndex()];	1✔
426	}
427	int bucketIndex() {
428	@SuppressWarnings("Varifier")
429	int ticks = (int) (nanos >>> SHIFT[wheelIndex]);	1✔
430	int bucketMask = wheel[wheelIndex].length - 1;	1✔
431	int bucketOffset = (ticks & bucketMask) + 1;	1✔
432	return (bucketOffset + steps) & bucketMask;	1✔
433	}
434	}
435
436	final class DescendingIterator extends Traverser {
437	int wheelIndex;
438	int steps;
439
440	DescendingIterator() {	1✔
441	wheelIndex = wheel.length - 1;	1✔
442	}	1✔
443	@Override boolean isDone() {
444	return (wheelIndex == -1);	1✔
445	}
446	@Override Node<K, V> sentinel() {
447	return wheel[wheelIndex][bucketIndex()];	1✔
448	}
449	@Override @Nullable Node<K, V> goToNextBucket() {
450	return (++steps < wheel[wheelIndex].length)	1✔
451	? wheel[wheelIndex][bucketIndex()]	1✔
452	: null;	1✔
453	}
454	@Override @Nullable Node<K, V> goToNextWheel() {
455	if (--wheelIndex < 0) {	1✔
456	return null;	1✔
457	}
458	steps = 0;	1✔
459	return wheel[wheelIndex][bucketIndex()];	1✔
460	}
461	@Override Node<K, V> traverse(Node<K, V> node) {
462	return node.getPreviousInVariableOrder();	1✔
463	}
464	int bucketIndex() {
465	@SuppressWarnings("Varifier")
466	int ticks = (int) (nanos >>> SHIFT[wheelIndex]);	1✔
467	int bucketMask = wheel[wheelIndex].length - 1;	1✔
468	int bucketOffset = (ticks & bucketMask);	1✔
469	return (bucketOffset - steps) & bucketMask;	1✔
470	}
471	}
472
473	/** A sentinel for the doubly-linked list in the bucket. */
474	static final class Sentinel<K, V> extends Node<K, V> {
475	Node<K, V> prev;
476	Node<K, V> next;
477
478	Sentinel() {	1✔
479	prev = next = this;	1✔
480	}	1✔
481
482	@Override public Node<K, V> getPreviousInVariableOrder() {
483	return prev;	1✔
484	}
485	@SuppressWarnings({"DataFlowIssue", "NullAway"})
486	@Override public void setPreviousInVariableOrder(@Nullable Node<K, V> prev) {
487	this.prev = prev;	1✔
488	}	1✔
489	@Override public Node<K, V> getNextInVariableOrder() {
490	return next;	1✔
491	}
492	@SuppressWarnings({"DataFlowIssue", "NullAway"})
493	@Override public void setNextInVariableOrder(@Nullable Node<K, V> next) {
494	this.next = next;	1✔
495	}	1✔
496
497	@Override public @Nullable K getKey() { return null; }	1✔
498	@Override public Object getKeyReference() { throw new UnsupportedOperationException(); }	1✔
499	@Override public Object getKeyReferenceOrNull() { throw new UnsupportedOperationException(); }	1✔
500	@Override public @Nullable V getValue() { return null; }	1✔
501	@Override public Object getValueReference() { throw new UnsupportedOperationException(); }	1✔
502	@Override public void setValue(V value, @Nullable ReferenceQueue<V> referenceQueue) {}	1✔
503	@Override public boolean containsValue(Object value) { return false; }	1✔
504	@Override public boolean isAlive() { return false; }	1✔
505	@Override public boolean isRetired() { return false; }	1✔
506	@Override public boolean isDead() { return false; }	1✔
507	@Override public void retire() {}	1✔
508	@Override public void die() {}	1✔
509	}
510	}

ben-manes / caffeine / #5612

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous