#20108

Committed 05 Dec 2025 10:43PM UTC coverage: 88.709% (+0.06%) from 88.652%

Build # #20108

Build Type

push

github

Committed by

web-flow

Commit Message

Introduce io.grpc.Uri. (#12535)

`io.grpc.Uri` is an implementation of RFC 3986 tailored for grpc-java's
needs. It lifts some of the limitations of `java.net.URI` that currently
prevent us from resolving target URIs like `intent:#Intent;...` See
#12244 for more.

Marked `@Internal` for now but the plan is to eventually use this to
replace `java.net.URI` in our public APIs such as NameResolver.Factory.

Run Details

35458 of 39971 relevant lines covered (88.71%)

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 / #20108

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