#20124

Committed 22 Dec 2025 07:28PM UTC coverage: 88.72% (+0.001%) from 88.719%

Build # #20124

Build Type

push

github

Committed by

ejona86

Commit Message

core: Improve DEADLINE_EXCEEDED message for CallCreds delays

DelayedStream is used both by DelayedClientTransport and
CallCredentialsApplyingTransport, but it wasn't clear from the error
which of the two was the cause of the delay. Now the two will have
different messages.

b/462499883

Run Details

35450 of 39957 relevant lines covered (88.72%)

0.89 hits per line

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

87.6

/../rls/src/main/java/io/grpc/rls/LinkedHashLruCache.java

/*
 * Copyright 2020 The gRPC Authors
 *
 * 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 io.grpc.rls;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkState;

import com.google.common.base.MoreObjects;
import com.google.common.base.Ticker;
import com.google.errorprone.annotations.CheckReturnValue;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import javax.annotation.Nullable;

/**
 * A LinkedHashLruCache implements least recently used caching where it supports access order lru
 * cache eviction while allowing entry level expiration time. When the cache reaches max capacity,
 * LruCache try to remove up to one already expired entries. If it doesn't find any expired entries,
 * it will remove based on access order of entry. To proactively clean up expired entries, call
 * {@link #cleanupExpiredEntries()} (e.g., via a recurring timer).
 */
abstract class LinkedHashLruCache<K, V> implements LruCache<K, V> {

  private final LinkedHashMap<K, SizedValue> delegate;
  private final Ticker ticker;
  @Nullable
  private final EvictionListener<K, V> evictionListener;
  private long estimatedSizeBytes;
  private long estimatedMaxSizeBytes;

  LinkedHashLruCache(
      final long estimatedMaxSizeBytes,
      @Nullable final EvictionListener<K, V> evictionListener,
      final Ticker ticker) {
    checkState(estimatedMaxSizeBytes > 0, "max estimated cache size should be positive");
    this.estimatedMaxSizeBytes = estimatedMaxSizeBytes;
    this.evictionListener = evictionListener;
    this.ticker = checkNotNull(ticker, "ticker");
    delegate = new LinkedHashMap<K, SizedValue>(
        // rough estimate or minimum hashmap default
        Math.max((int) (estimatedMaxSizeBytes / 1000), 16),
        /* loadFactor= */ 0.75f,
        /* accessOrder= */ true) {
      @Override
      protected boolean removeEldestEntry(Map.Entry<K, SizedValue> eldest) {
        if (estimatedSizeBytes <= LinkedHashLruCache.this.estimatedMaxSizeBytes) {
          return false;
        }

        // first, remove at most 1 expired entry
        boolean removed = cleanupExpiredEntries(1, ticker.read());
        // handles size based eviction if necessary no expired entry
        boolean shouldRemove = !removed
            && shouldInvalidateEldestEntry(eldest.getKey(), eldest.getValue().value, ticker.read());
        if (shouldRemove) {
          // remove entry by us to make sure lruIterator and cache is in sync
          LinkedHashLruCache.this.invalidate(eldest.getKey(), EvictionType.SIZE);
        }
        return false;
      }
    };
  }

  /**
   * Determines if the eldest entry should be kept or not when the cache size limit is reached. Note
   * that LruCache is access level and the eldest is determined by access pattern.
   */
  @SuppressWarnings("unused")
  protected boolean shouldInvalidateEldestEntry(K eldestKey, V eldestValue, long now) {
    return true;
  }

  /** Determines if the entry is already expired or not. */
  protected abstract boolean isExpired(K key, V value, long nowNanos);

  /**
   * Returns estimated size of entry to keep track. If it always returns 1, the max size bytes
   * behaves like max number of entry (default behavior).
   */
  @SuppressWarnings("unused")
  protected int estimateSizeOf(K key, V value) {
    return 1;
  }

  protected long estimatedMaxSizeBytes() {
    return estimatedMaxSizeBytes;
  }

  /** Updates size for given key if entry exists. It is useful if the cache value is mutated. */
  public void updateEntrySize(K key) {
    SizedValue entry = readInternal(key);
    if (entry == null) {
      return;
    }
    int prevSize = entry.size;
    int newSize = estimateSizeOf(key, entry.value);
    entry.size = newSize;
    estimatedSizeBytes += newSize - prevSize;
  }

  /**
   * Returns estimated cache size bytes. Each entry size is calculated by {@link
   * #estimateSizeOf(java.lang.Object, java.lang.Object)}.
   */
  public long estimatedSizeBytes() {
    return estimatedSizeBytes;
  }

  @Override
  @Nullable
  public final V cache(K key, V value) {
    checkNotNull(key, "key");
    checkNotNull(value, "value");
    SizedValue existing;
    int size = estimateSizeOf(key, value);
    estimatedSizeBytes += size;
    existing = delegate.put(key, new SizedValue(size, value));
    if (existing != null) {
      fireOnEviction(key, existing, EvictionType.REPLACED);
    }
    return existing == null ? null : existing.value;
  }

  @Override
  @Nullable
  @CheckReturnValue
  public final V read(K key) {
    SizedValue entry = readInternal(key);
    if (entry != null) {
      return entry.value;
    }
    return null;
  }

  @Nullable
  @CheckReturnValue
  private SizedValue readInternal(K key) {
    checkNotNull(key, "key");
    SizedValue existing = delegate.get(key);
    if (existing != null && isExpired(key, existing.value, ticker.read())) {
      return null;
    }
    return existing;
  }

  @Override
  @Nullable
  public final V invalidate(K key) {
    return invalidate(key, EvictionType.EXPLICIT);
  }

  @Nullable
  private V invalidate(K key, EvictionType cause) {
    checkNotNull(key, "key");
    checkNotNull(cause, "cause");
    SizedValue existing = delegate.remove(key);
    if (existing != null) {
      fireOnEviction(key, existing, cause);
    }
    return existing == null ? null : existing.value;
  }

  @Override
  public final void invalidateAll() {
    Iterator<Map.Entry<K, SizedValue>> iterator = delegate.entrySet().iterator();
    while (iterator.hasNext()) {
      Map.Entry<K, SizedValue> entry = iterator.next();
      if (entry.getValue() != null) {
        fireOnEviction(entry.getKey(), entry.getValue(), EvictionType.EXPLICIT);
      }
      iterator.remove();
    }
  }

  @Override
  @CheckReturnValue
  public final boolean hasCacheEntry(K key) {
    // call readInternal to filter already expired entry in the cache
    return readInternal(key) != null;
  }

  /** Returns shallow copied values in the cache. */
  public final List<V> values() {
    List<V> list = new ArrayList<>(delegate.size());
    for (SizedValue value : delegate.values()) {
      list.add(value.value);
    }
    return Collections.unmodifiableList(list);
  }

  /**
   * Cleans up cache if needed to fit into max size bytes by
   * removing expired entries and removing oldest entries by LRU order.
   * Returns TRUE if any unexpired entries were removed
   */
  protected final boolean fitToLimit() {
    boolean removedAnyUnexpired = false;
    if (estimatedSizeBytes <= estimatedMaxSizeBytes) {
      return false;
    }
    // cleanup expired entries
    long now = ticker.read();
    cleanupExpiredEntries(now);

    // cleanup eldest entry until the size of all entries fits within the limit
    Iterator<Map.Entry<K, SizedValue>> lruIter = delegate.entrySet().iterator();
    while (lruIter.hasNext() && estimatedMaxSizeBytes < this.estimatedSizeBytes) {
      Map.Entry<K, SizedValue> entry = lruIter.next();
      if (!shouldInvalidateEldestEntry(entry.getKey(), entry.getValue().value, now)) {
        break; // Violates some constraint like minimum age so stop our cleanup
      }
      lruIter.remove();
      // fireOnEviction will update the estimatedSizeBytes
      fireOnEviction(entry.getKey(), entry.getValue(), EvictionType.SIZE);
      removedAnyUnexpired = true;
    }
    return removedAnyUnexpired;
  }

  /**
   * Resizes cache. If new size is smaller than current estimated size, it will free up space by
   * removing expired entries and removing oldest entries by LRU order.
   */
  public final void resize(long newSizeBytes) {
    this.estimatedMaxSizeBytes = newSizeBytes;
    fitToLimit();
  }

  @Override
  @CheckReturnValue
  public final int estimatedSize() {
    return delegate.size();
  }

  /** Returns {@code true} if any entries were removed. */
  public final boolean cleanupExpiredEntries() {
    return cleanupExpiredEntries(ticker.read());
  }

  private boolean cleanupExpiredEntries(long now) {
    return cleanupExpiredEntries(Integer.MAX_VALUE, now);
  }

  // maxExpiredEntries is by number of entries
  private boolean cleanupExpiredEntries(int maxExpiredEntries, long now) {
    checkArgument(maxExpiredEntries > 0, "maxExpiredEntries must be positive");
    boolean removedAny = false;
    Iterator<Map.Entry<K, SizedValue>> lruIter = delegate.entrySet().iterator();
    while (lruIter.hasNext() && maxExpiredEntries > 0) {
      Map.Entry<K, SizedValue> entry = lruIter.next();
      if (isExpired(entry.getKey(), entry.getValue().value, now)) {
        lruIter.remove();
        fireOnEviction(entry.getKey(), entry.getValue(), EvictionType.EXPIRED);
        removedAny = true;
        maxExpiredEntries--;
      }
    }
    return removedAny;
  }

  @Override
  public final void close() {
    invalidateAll();
  }

  private void fireOnEviction(K key, SizedValue value, EvictionType cause) {
    estimatedSizeBytes -= value.size;
    if (evictionListener != null) {
      evictionListener.onEviction(key, value.value, cause);
    }
  }

  private final class SizedValue {
    volatile int size;
    final V value;

    SizedValue(int size, V value) {
      this.size = size;
      this.value = value;
    }

    @Override
    public boolean equals(Object o) {
      // NOTE: the size doesn't affect equality
      if (this == o) {
        return true;
      }
      if (o == null || getClass() != o.getClass()) {
        return false;
      }
      LinkedHashLruCache<?, ?>.SizedValue that = (LinkedHashLruCache<?, ?>.SizedValue) o;
      return Objects.equals(value, that.value);
    }

    @Override
    public int hashCode() {
      // NOTE: the size doesn't affect hashCode
      return Objects.hash(value);
    }

    @Override
    public String toString() {
      return MoreObjects.toStringHelper(this)
          .add("size", size)
          .add("value", value)
          .toString();
    }
  }
}

1	/*
2	* Copyright 2020 The gRPC Authors
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
17	package io.grpc.rls;
18
19	import static com.google.common.base.Preconditions.checkArgument;
20	import static com.google.common.base.Preconditions.checkNotNull;
21	import static com.google.common.base.Preconditions.checkState;
22
23	import com.google.common.base.MoreObjects;
24	import com.google.common.base.Ticker;
25	import com.google.errorprone.annotations.CheckReturnValue;
26	import java.util.ArrayList;
27	import java.util.Collections;
28	import java.util.Iterator;
29	import java.util.LinkedHashMap;
30	import java.util.List;
31	import java.util.Map;
32	import java.util.Objects;
33	import javax.annotation.Nullable;
34
35	/**
36	* A LinkedHashLruCache implements least recently used caching where it supports access order lru
37	* cache eviction while allowing entry level expiration time. When the cache reaches max capacity,
38	* LruCache try to remove up to one already expired entries. If it doesn't find any expired entries,
39	* it will remove based on access order of entry. To proactively clean up expired entries, call
40	* {@link #cleanupExpiredEntries()} (e.g., via a recurring timer).
41	*/
42	abstract class LinkedHashLruCache<K, V> implements LruCache<K, V> {
43
44	private final LinkedHashMap<K, SizedValue> delegate;
45	private final Ticker ticker;
46	@Nullable
47	private final EvictionListener<K, V> evictionListener;
48	private long estimatedSizeBytes;
49	private long estimatedMaxSizeBytes;
50
51	LinkedHashLruCache(
52	final long estimatedMaxSizeBytes,
53	@Nullable final EvictionListener<K, V> evictionListener,
54	final Ticker ticker) {	1✔
55	checkState(estimatedMaxSizeBytes > 0, "max estimated cache size should be positive");	1✔
56	this.estimatedMaxSizeBytes = estimatedMaxSizeBytes;	1✔
57	this.evictionListener = evictionListener;	1✔
58	this.ticker = checkNotNull(ticker, "ticker");	1✔
59	delegate = new LinkedHashMap<K, SizedValue>(	1✔
60	// rough estimate or minimum hashmap default
61	Math.max((int) (estimatedMaxSizeBytes / 1000), 16),	1✔
62	/* loadFactor= */ 0.75f,
63	/* accessOrder= */ true) {	1✔
64	@Override
65	protected boolean removeEldestEntry(Map.Entry<K, SizedValue> eldest) {
66	if (estimatedSizeBytes <= LinkedHashLruCache.this.estimatedMaxSizeBytes) {	1✔
67	return false;	1✔
68	}
69
70	// first, remove at most 1 expired entry
71	boolean removed = cleanupExpiredEntries(1, ticker.read());	1✔
72	// handles size based eviction if necessary no expired entry
73	boolean shouldRemove = !removed	1✔
74	&& shouldInvalidateEldestEntry(eldest.getKey(), eldest.getValue().value, ticker.read());	1✔
75	if (shouldRemove) {	1✔
76	// remove entry by us to make sure lruIterator and cache is in sync
77	LinkedHashLruCache.this.invalidate(eldest.getKey(), EvictionType.SIZE);	1✔
78	}
79	return false;	1✔
80	}
81	};
82	}	1✔
83
84	/**
85	* Determines if the eldest entry should be kept or not when the cache size limit is reached. Note
86	* that LruCache is access level and the eldest is determined by access pattern.
87	*/
88	@SuppressWarnings("unused")
89	protected boolean shouldInvalidateEldestEntry(K eldestKey, V eldestValue, long now) {
90	return true;	1✔
91	}
92
93	/** Determines if the entry is already expired or not. */
94	protected abstract boolean isExpired(K key, V value, long nowNanos);
95
96	/**
97	* Returns estimated size of entry to keep track. If it always returns 1, the max size bytes
98	* behaves like max number of entry (default behavior).
99	*/
100	@SuppressWarnings("unused")
101	protected int estimateSizeOf(K key, V value) {
102	return 1;	×
103	}
104
105	protected long estimatedMaxSizeBytes() {
106	return estimatedMaxSizeBytes;	1✔
107	}
108
109	/** Updates size for given key if entry exists. It is useful if the cache value is mutated. */
110	public void updateEntrySize(K key) {
111	SizedValue entry = readInternal(key);	1✔
112	if (entry == null) {	1✔
113	return;	×
114	}
115	int prevSize = entry.size;	1✔
116	int newSize = estimateSizeOf(key, entry.value);	1✔
117	entry.size = newSize;	1✔
118	estimatedSizeBytes += newSize - prevSize;	1✔
119	}	1✔
120
121	/**
122	* Returns estimated cache size bytes. Each entry size is calculated by {@link
123	* #estimateSizeOf(java.lang.Object, java.lang.Object)}.
124	*/
125	public long estimatedSizeBytes() {
126	return estimatedSizeBytes;	1✔
127	}
128
129	@Override
130	@Nullable
131	public final V cache(K key, V value) {
132	checkNotNull(key, "key");	1✔
133	checkNotNull(value, "value");	1✔
134	SizedValue existing;
135	int size = estimateSizeOf(key, value);	1✔
136	estimatedSizeBytes += size;	1✔
137	existing = delegate.put(key, new SizedValue(size, value));	1✔
138	if (existing != null) {	1✔
139	fireOnEviction(key, existing, EvictionType.REPLACED);	1✔
140	}
141	return existing == null ? null : existing.value;	1✔
142	}
143
144	@Override
145	@Nullable
146	@CheckReturnValue
147	public final V read(K key) {
148	SizedValue entry = readInternal(key);	1✔
149	if (entry != null) {	1✔
150	return entry.value;	1✔
151	}
152	return null;	1✔
153	}
154
155	@Nullable
156	@CheckReturnValue
157	private SizedValue readInternal(K key) {
158	checkNotNull(key, "key");	1✔
159	SizedValue existing = delegate.get(key);	1✔
160	if (existing != null && isExpired(key, existing.value, ticker.read())) {	1✔
161	return null;	×
162	}
163	return existing;	1✔
164	}
165
166	@Override
167	@Nullable
168	public final V invalidate(K key) {
169	return invalidate(key, EvictionType.EXPLICIT);	1✔
170	}
171
172	@Nullable
173	private V invalidate(K key, EvictionType cause) {
174	checkNotNull(key, "key");	1✔
175	checkNotNull(cause, "cause");	1✔
176	SizedValue existing = delegate.remove(key);	1✔
177	if (existing != null) {	1✔
178	fireOnEviction(key, existing, cause);	1✔
179	}
180	return existing == null ? null : existing.value;	1✔
181	}
182
183	@Override
184	public final void invalidateAll() {
185	Iterator<Map.Entry<K, SizedValue>> iterator = delegate.entrySet().iterator();	1✔
186	while (iterator.hasNext()) {	1✔
187	Map.Entry<K, SizedValue> entry = iterator.next();	1✔
188	if (entry.getValue() != null) {	1✔
189	fireOnEviction(entry.getKey(), entry.getValue(), EvictionType.EXPLICIT);	1✔
190	}
191	iterator.remove();	1✔
192	}	1✔
193	}	1✔
194
195	@Override
196	@CheckReturnValue
197	public final boolean hasCacheEntry(K key) {
198	// call readInternal to filter already expired entry in the cache
199	return readInternal(key) != null;	1✔
200	}
201
202	/** Returns shallow copied values in the cache. */
203	public final List<V> values() {
204	List<V> list = new ArrayList<>(delegate.size());	1✔
205	for (SizedValue value : delegate.values()) {	1✔
206	list.add(value.value);	1✔
207	}	1✔
208	return Collections.unmodifiableList(list);	1✔
209	}
210
211	/**
212	* Cleans up cache if needed to fit into max size bytes by
213	* removing expired entries and removing oldest entries by LRU order.
214	* Returns TRUE if any unexpired entries were removed
215	*/
216	protected final boolean fitToLimit() {
217	boolean removedAnyUnexpired = false;	1✔
218	if (estimatedSizeBytes <= estimatedMaxSizeBytes) {	1✔
219	return false;	1✔
220	}
221	// cleanup expired entries
222	long now = ticker.read();	1✔
223	cleanupExpiredEntries(now);	1✔
224
225	// cleanup eldest entry until the size of all entries fits within the limit
226	Iterator<Map.Entry<K, SizedValue>> lruIter = delegate.entrySet().iterator();	1✔
227	while (lruIter.hasNext() && estimatedMaxSizeBytes < this.estimatedSizeBytes) {	1✔
228	Map.Entry<K, SizedValue> entry = lruIter.next();	1✔
229	if (!shouldInvalidateEldestEntry(entry.getKey(), entry.getValue().value, now)) {	1✔
230	break; // Violates some constraint like minimum age so stop our cleanup	×
231	}
232	lruIter.remove();	1✔
233	// fireOnEviction will update the estimatedSizeBytes
234	fireOnEviction(entry.getKey(), entry.getValue(), EvictionType.SIZE);	1✔
235	removedAnyUnexpired = true;	1✔
236	}	1✔
237	return removedAnyUnexpired;	1✔
238	}
239
240	/**
241	* Resizes cache. If new size is smaller than current estimated size, it will free up space by
242	* removing expired entries and removing oldest entries by LRU order.
243	*/
244	public final void resize(long newSizeBytes) {
245	this.estimatedMaxSizeBytes = newSizeBytes;	1✔
246	fitToLimit();	1✔
247	}	1✔
248
249	@Override
250	@CheckReturnValue
251	public final int estimatedSize() {
252	return delegate.size();	1✔
253	}
254
255	/** Returns {@code true} if any entries were removed. */
256	public final boolean cleanupExpiredEntries() {
257	return cleanupExpiredEntries(ticker.read());	1✔
258	}
259
260	private boolean cleanupExpiredEntries(long now) {
261	return cleanupExpiredEntries(Integer.MAX_VALUE, now);	1✔
262	}
263
264	// maxExpiredEntries is by number of entries
265	private boolean cleanupExpiredEntries(int maxExpiredEntries, long now) {
266	checkArgument(maxExpiredEntries > 0, "maxExpiredEntries must be positive");	1✔
267	boolean removedAny = false;	1✔
268	Iterator<Map.Entry<K, SizedValue>> lruIter = delegate.entrySet().iterator();	1✔
269	while (lruIter.hasNext() && maxExpiredEntries > 0) {	1✔
270	Map.Entry<K, SizedValue> entry = lruIter.next();	1✔
271	if (isExpired(entry.getKey(), entry.getValue().value, now)) {	1✔
272	lruIter.remove();	1✔
273	fireOnEviction(entry.getKey(), entry.getValue(), EvictionType.EXPIRED);	1✔
274	removedAny = true;	1✔
275	maxExpiredEntries--;	1✔
276	}
277	}	1✔
278	return removedAny;	1✔
279	}
280
281	@Override
282	public final void close() {
283	invalidateAll();	1✔
284	}	1✔
285
286	private void fireOnEviction(K key, SizedValue value, EvictionType cause) {
287	estimatedSizeBytes -= value.size;	1✔
288	if (evictionListener != null) {	1✔
289	evictionListener.onEviction(key, value.value, cause);	1✔
290	}
291	}	1✔
292
293	private final class SizedValue {
294	volatile int size;
295	final V value;
296
297	SizedValue(int size, V value) {	1✔
298	this.size = size;	1✔
299	this.value = value;	1✔
300	}	1✔
301
302	@Override
303	public boolean equals(Object o) {
304	// NOTE: the size doesn't affect equality
305	if (this == o) {	×
306	return true;	×
307	}
308	if (o == null \|\| getClass() != o.getClass()) {	×
309	return false;	×
310	}
311	LinkedHashLruCache<?, ?>.SizedValue that = (LinkedHashLruCache<?, ?>.SizedValue) o;	×
312	return Objects.equals(value, that.value);	×
313	}
314
315	@Override
316	public int hashCode() {
317	// NOTE: the size doesn't affect hashCode
318	return Objects.hash(value);	×
319	}
320
321	@Override
322	public String toString() {
323	return MoreObjects.toStringHelper(this)	×
324	.add("size", size)	×
325	.add("value", value)	×
326	.toString();	×
327	}
328	}
329	}

grpc / grpc-java / #20124

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