1 /*
  2  * Copyright (c) 2020, 2022, Oracle and/or its affiliates. All rights reserved.
  3  * Copyright (c) 2020, 2022, Red Hat Inc.
  4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  5  *
  6  * This code is free software; you can redistribute it and/or modify it
  7  * under the terms of the GNU General Public License version 2 only, as
  8  * published by the Free Software Foundation.  Oracle designates this
  9  * particular file as subject to the "Classpath" exception as provided
 10  * by Oracle in the LICENSE file that accompanied this code.
 11  *
 12  * This code is distributed in the hope that it will be useful, but WITHOUT
 13  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 14  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 15  * version 2 for more details (a copy is included in the LICENSE file that
 16  * accompanied this code).
 17  *
 18  * You should have received a copy of the GNU General Public License version
 19  * 2 along with this work; if not, write to the Free Software Foundation,
 20  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 21  *
 22  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 23  * or visit www.oracle.com if you need additional information or have any
 24  * questions.
 25  */
 26 
 27 package jdk.incubator.concurrent;
 28 
 29 import java.util.NoSuchElementException;
 30 import java.util.Objects;
 31 import java.util.concurrent.Callable;
 32 import java.util.function.Function;
 33 import java.util.function.Supplier;
 34 import jdk.internal.access.JavaLangAccess;
 35 import jdk.internal.access.JavaUtilConcurrentTLRAccess;
 36 import jdk.internal.access.SharedSecrets;
 37 import jdk.internal.vm.ExtentLocalContainer;
 38 import jdk.internal.vm.annotation.DontInline;
 39 import jdk.internal.vm.annotation.ForceInline;
 40 import jdk.internal.vm.annotation.ReservedStackAccess;
 41 import jdk.internal.vm.annotation.Stable;
 42 import sun.security.action.GetPropertyAction;
 43 
 44 /**
 45  * Represents a variable that is local to an <em>extent</em>. It is a per-thread variable
 46  * that allows context to be set in a caller and read by callees. The <em>extent</em> is
 47  * the set of methods that the caller directly invokes, and any methods invoked
 48  * transitively. Extent-local variables also provide a way to share immutable data across
 49  * threads.
 50  *
 51  * <p> An extent-local variable is bound, meaning it gets a value, when invoking an
 52  * operation with the {@link Carrier#run(Runnable) Carrier.run} or {@link
 53  * Carrier#call(Callable) Carrier.call} methods. {@link Carrier Carrier} instances are
 54  * created by the static method {@link #where(ExtentLocal, Object)}. The operations
 55  * executed by the {@code run} and {@code call} methods use the {@link #get()} method to
 56  * read the value of a bound extent local. An extent-local variable reverts to being
 57  * unbound (or its previous value) when the operation completes.
 58  *
 59  * <p> An {@code ExtentLocal} object will typically be declared in a {@code private
 60  * static final} field so that it can only be accessed by code in that class (or other
 61  * classes within its nest).
 62  *
 63  * <p> {@link ExtentLocal} bindings are immutable: there is no "{@code set}" method.
 64  * There may be cases when an operation might need to use the same extent-local variable
 65  * to communicate a different value to the methods that it calls. The requirement is not
 66  * to change the original binding but to establish a new binding for nested calls. If an
 67  * extent local already has a value, then {@code run} or {@code call} methods may be
 68  * invoked to run another operation with a newly-bound value. Code executed by the
 69  * operation will read the new value of the extent local. The extent local reverts to its
 70  * previous value when the operation completes.
 71  *
 72  * <h2> Sharing extent-local variables across threads </h2>
 73  *
 74  * Extent-local variables can be shared across threads when used in conjunction with
 75  * {@link StructuredTaskScope}. Creating a {@code StructuredTaskScope} captures the
 76  * current thread's extent-local bindings for inheritance by threads {@link
 77  * StructuredTaskScope#fork(Callable) forked} in the task scope. This means that a thread
 78  * may bind an extent-local variable and share its value in a structured concurrency
 79  * context. Threads forked in the task scope that read the extent-local variable will read
 80  * the value bound by the thread that created the task scope.
 81  *
 82  * <p> Unless otherwise specified, passing a {@code null} argument to a constructor
 83  * or method in this class will cause a {@link NullPointerException} to be thrown.
 84  *
 85  * @apiNote
 86  * The following example uses an extent local to make credentials available to callees.
 87  *
 88  * {@snippet lang=java :
 89  *   // @link substring="newInstance" target="ExtentLocal#newInstance" :
 90  *   private static final ExtentLocal<Credentials> CREDENTIALS = ExtentLocal.newInstance();
 91  *
 92  *   Credentials creds = ...
 93  *   ExtentLocal.where(CREDENTIALS, creds).run(() -> {
 94  *       ...
 95  *       Connection connection = connectDatabase();
 96  *       ...
 97  *   });
 98  *
 99  *   ...
100  *
101  *   Connection connectDatabase() {
102  *       // @link substring="get" target="ExtentLocal#get" :
103  *       Credentials credentials = CREDENTIALS.get();
104  *       ...
105  *   }
106  * }
107  *
108  * @implNote
109  * Extent-local variables are designed to be used in fairly small
110  * numbers. {@link #get} initially performs a search through enclosing
111  * scopes to find an extent-local variable's innermost binding. It
112  * then caches the result of the search in a small thread-local
113  * cache. Subsequent invocations of {@link #get} for that extent local
114  * will almost always be very fast. However, if a program has many
115  * extent-local variables that it uses cyclically, the cache hit rate
116  * will be low and performance will be poor. This design allows
117  * extent-local inheritance by {@link StructuredTaskScope} threads to
118  * be very fast: in essence, no more than copying a pointer, and
119  * leaving an extent-local binding also requires little more than
120  * updating a pointer.
121  *
122  * <p>Because the extent-local per-thread cache is small, you should
123  * try to minimize the number of bound extent-local variables in
124  * use. For example, if you need to pass a number of values in this
125  * way, it makes sense to create a record class to hold those values,
126  * and then bind a single extent-local variable to an instance of that
127  * record.
128  *
129  * <p>For this incubator release, we have provided some system properties
130  * to tune the performance of extent-local variables.
131  *
132  * <p>The system property {@code jdk.incubator.concurrent.ExtentLocal.cacheSize}
133  * controls the size of the (per-thread) extent-local cache. This cache is crucial
134  * for the performance of extent-local variables. If it is too small,
135  * the runtime library will repeatedly need to scan for each
136  * {@link #get}. If it is too large, memory will be unnecessarily
137  * consumed. The default extent-local cache size is 16 entries. It may
138  * be varied from 2 to 16 entries in size. {@code ExtentLocal.cacheSize}
139  * must be an integer power of 2.
140  *
141  * <p>For example, you could use {@code -Djdk.incubator.concurrent.ExtentLocal.cacheSize=8}.
142  *
143  * <p>The other system property is {@code jdk.preserveExtentLocalCache}.
144  * This property determines whether the per-thread extent-local
145  * cache is preserved when a virtual thread is blocked. By default
146  * this property is set to {@code true}, meaning that every virtual
147  * thread preserves its extent-local cache when blocked. Like {@code
148  * ExtentLocal.cacheSize}, this is a space versus speed trade-off: if
149  * you have a great many virtual threads that are blocked most of the
150  * time, setting this property to {@code false} might result in a
151  * useful memory saving, but each virtual thread's extent-local cache
152  * would have to be regenerated after a blocking operation.
153  *
154  * @param <T> the extent local's type
155  * @since 19
156  */
157 public final class ExtentLocal<T> {
158     private static final JavaLangAccess JLA = SharedSecrets.getJavaLangAccess();
159 
160     private final @Stable int hash;
161 
162     @Override
163     public int hashCode() { return hash; }
164 
165     /**
166      * An immutable map from {@code ExtentLocal} to values.
167      *
168      * <p> Unless otherwise specified, passing a {@code null} argument to a constructor
169      * or method in this class will cause a {@link NullPointerException} to be thrown.
170      */
171     static sealed class Snapshot permits EmptySnapshot {
172         final Snapshot prev;
173         final Carrier bindings;
174         final int bitmask;
175 
176         private static final Object NIL = new Object();
177 
178         Snapshot(Carrier bindings, Snapshot prev) {
179             this.prev = prev;
180             this.bindings = bindings;
181             this.bitmask = bindings.bitmask | prev.bitmask;
182         }
183 
184         protected Snapshot() {
185             this.prev = null;
186             this.bindings = null;
187             this.bitmask = 0;
188         }
189 
190         Object find(ExtentLocal<?> key) {
191             int bits = key.bitmask();
192             for (Snapshot snapshot = this;
193                  containsAll(snapshot.bitmask, bits);
194                  snapshot = snapshot.prev) {
195                 for (Carrier carrier = snapshot.bindings;
196                      carrier != null && containsAll(carrier.bitmask, bits);
197                      carrier = carrier.prev) {
198                     if (carrier.getKey() == key) {
199                         Object value = carrier.get();
200                         return value;
201                     }
202                 }
203             }
204             return NIL;
205         }
206     }
207 
208     static final class EmptySnapshot extends Snapshot {
209 
210         private EmptySnapshot() {
211             super();
212         }
213 
214         private static final Snapshot SINGLETON = new EmptySnapshot();
215 
216         static final Snapshot getInstance() {
217             return SINGLETON;
218         }
219     }
220 
221     /**
222      * An immutable map of extent-local variables to values.
223      * It define the {@link #run(Runnable) run} and {@link #call(Callable) call} methods
224      * to invoke an operation with the extent-local variable mappings bound to the thread
225      * that invokes {@code run} or {@code call}.
226      *
227      * @since 19
228      */
229     public static final class Carrier {
230         // Bit masks: a 1 in postion n indicates that this set of bound values
231         // hits that slot in the cache.
232         final int bitmask;
233         final ExtentLocal<?> key;
234         final Object value;
235         final Carrier prev;
236 
237         Carrier(ExtentLocal<?> key, Object value, Carrier prev) {
238             this.key = key;
239             this.value = value;
240             this.prev = prev;
241             int bits = key.bitmask();
242             if (prev != null) {
243                 bits |= prev.bitmask;
244             }
245             this.bitmask = bits;
246         }
247 
248         /**
249          * Add a binding to this map, returning a new Carrier instance.
250          */
251         private static final <T> Carrier where(ExtentLocal<T> key, T value,
252                                                Carrier prev) {
253             return new Carrier(key, value, prev);
254         }
255 
256         /**
257          * Returns a new {@link Carrier Carrier}, which consists of the contents of this
258          * carrier plus a new mapping from {@code key} to {@code value}. If this carrier
259          * already has a mapping for the extent-local variable {@code key} then the new
260          * value added by this method overrides the previous mapping. That is to say, if
261          * there is a list of {@code where(...)} clauses, the rightmost clause wins.
262          * @param key   the ExtentLocal to bind a value to
263          * @param value the new value, can be {@code null}
264          * @param <T>   the type of the ExtentLocal
265          * @return a new carrier, consisting of {@code this} plus a new binding
266          * ({@code this} is unchanged)
267          */
268         public <T> Carrier where(ExtentLocal<T> key, T value) {
269             return where(key, value, this);
270         }
271 
272         /*
273          * Return a new set consisting of a single binding.
274          */
275         static <T> Carrier of(ExtentLocal<T> key, T value) {
276             return where(key, value, null);
277         }
278 
279         final Object get() {
280             return value;
281         }
282 
283         final ExtentLocal<?> getKey() {
284             return key;
285         }
286 
287         /**
288          * Returns the value of a variable in this map of extent-local variables.
289          * @param key the ExtentLocal variable
290          * @param <T> the type of the ExtentLocal
291          * @return the value
292          * @throws NoSuchElementException if key is not bound to any value
293          */
294         @SuppressWarnings("unchecked")
295         public <T> T get(ExtentLocal<T> key) {
296             var bits = key.bitmask();
297             for (Carrier carrier = this;
298                  carrier != null && containsAll(carrier.bitmask, bits);
299                  carrier = carrier.prev) {
300                 if (carrier.getKey() == key) {
301                     Object value = carrier.get();
302                     return (T)value;
303                 }
304             }
305             throw new NoSuchElementException();
306         }
307 
308         /**
309          * Runs a value-returning operation with this map of extent-local variables bound
310          * to values. Code invoked by {@code op} can use the {@link ExtentLocal#get()
311          * get} method to get the value of the extent local. The extent-local variables
312          * revert to their previous values or become {@linkplain #isBound() unbound} when
313          * the operation completes.
314          *
315          * <p> Extent-local variables are intended to be used in a <em>structured
316          * manner</em>. If {@code op} creates any {@link StructuredTaskScope}s but does
317          * not close them, then exiting {@code op} causes the underlying construct of each
318          * {@link StructuredTaskScope} to be closed (in the reverse order that they were
319          * created in), and {@link StructureViolationException} to be thrown.
320          *
321          * @param op    the operation to run
322          * @param <R>   the type of the result of the function
323          * @return the result
324          * @throws Exception if {@code op} completes with an exception
325          */
326         public <R> R call(Callable<R> op) throws Exception {
327             Objects.requireNonNull(op);
328             Cache.invalidate(bitmask);
329             var prevBindings = addExtentLocalBindings(this);
330             try {
331                 return ExtentLocalContainer.call(op);
332             } catch (Throwable t) {
333                 setExtentLocalCache(null); // Cache.invalidate();
334                 throw t;
335             } finally {
336                 setExtentLocalBindings(prevBindings);
337                 Cache.invalidate(bitmask);
338             }
339         }
340 
341         /**
342          * Runs an operation with this map of ExtentLocals bound to values. Code executed
343          * by the operation can use the {@link ExtentLocal#get() get()} method to get the
344          * value of the extent local. The extent-local variables revert to their previous
345          * values or becomes {@linkplain #isBound() unbound} when the operation completes.
346          *
347          * <p> Extent-local variables are intended to be used in a <em>structured
348          * manner</em>. If {@code op} creates any {@link StructuredTaskScope}s but does
349          * not close them, then exiting {@code op} causes the underlying construct of each
350          * {@link StructuredTaskScope} to be closed (in the reverse order that they were
351          * created in), and {@link StructureViolationException} to be thrown.
352          *
353          * @param op    the operation to run
354          */
355         public void run(Runnable op) {
356             Objects.requireNonNull(op);
357             Cache.invalidate(bitmask);
358             var prevBindings = addExtentLocalBindings(this);
359             try {
360                 ExtentLocalContainer.run(op);
361             } catch (Throwable t) {
362                 setExtentLocalCache(null); // Cache.invalidate();
363                 throw t;
364             } finally {
365                 setExtentLocalBindings(prevBindings);
366                 Cache.invalidate(bitmask);
367             }
368         }
369 
370         /*
371          * Add a list of bindings to the current Thread's set of bound values.
372          */
373         private static final Snapshot addExtentLocalBindings(Carrier bindings) {
374             Snapshot prev = extentLocalBindings();
375             var b = new Snapshot(bindings, prev);
376             ExtentLocal.setExtentLocalBindings(b);
377             return prev;
378         }
379     }
380 
381     /**
382      * Creates a binding for an extent-local variable.
383      * The {@link Carrier Carrier} may be used later to invoke a {@link Callable} or
384      * {@link Runnable} instance. More bindings may be added to the {@link Carrier Carrier}
385      * by further calls to this method.
386      *
387      * @param key the ExtentLocal to bind
388      * @param value the value to bind it to, can be {@code null}
389      * @param <T> the type of the ExtentLocal
390      * @return A Carrier instance that contains one binding, that of key and value
391      */
392     public static <T> Carrier where(ExtentLocal<T> key, T value) {
393         return Carrier.of(key, value);
394     }
395 
396     /**
397      * Creates a binding for an extent-local variable and runs a
398      * value-returning operation with that {@link ExtentLocal} bound to the value.
399      * @param key the ExtentLocal to bind
400      * @param value the value to bind it to, can be {@code null}
401      * @param <T> the type of the ExtentLocal
402      * @param <U> the type of the Result
403      * @param op the operation to call
404      * @return the result
405      * @throws Exception if the operation completes with an exception
406      */
407     public static <T, U> U where(ExtentLocal<T> key, T value, Callable<U> op) throws Exception {
408         return where(key, value).call(op);
409     }
410 
411     /**
412      * Creates a binding for extent-local variable and runs an
413      * operation with that  {@link ExtentLocal} bound to the value.
414      * @param key the ExtentLocal to bind
415      * @param value the value to bind it to, can be {@code null}
416      * @param <T> the type of the ExtentLocal
417      * @param op the operation to run
418      */
419     public static <T> void where(ExtentLocal<T> key, T value, Runnable op) {
420         where(key, value).run(op);
421     }
422 
423     private ExtentLocal() {
424         this.hash = generateKey();
425     }
426 
427     /**
428      * Creates an extent-local variable to refer to a value of type T.
429      *
430      * @param <T> the type of the extent local's value.
431      * @return an extent-local variable
432      */
433     public static <T> ExtentLocal<T> newInstance() {
434         return new ExtentLocal<T>();
435     }
436 
437     /**
438      * Returns the current thread's bound value for this extent-local variable.
439      * @return the value of the extent local
440      * @throws NoSuchElementException if the extent local is not bound
441      */
442     @ForceInline
443     @SuppressWarnings("unchecked")
444     public T get() {
445         Object[] objects;
446         if ((objects = extentLocalCache()) != null) {
447             // This code should perhaps be in class Cache. We do it
448             // here because the generated code is small and fast and
449             // we really want it to be inlined in the caller.
450             int n = (hash & Cache.SLOT_MASK) * 2;
451             if (objects[n] == this) {
452                 return (T)objects[n + 1];
453             }
454             n = ((hash >>> Cache.INDEX_BITS) & Cache.SLOT_MASK) * 2;
455             if (objects[n] == this) {
456                 return (T)objects[n + 1];
457             }
458         }
459         return slowGet();
460     }
461 
462     @SuppressWarnings("unchecked")
463     private T slowGet() {
464         var value = findBinding();
465         if (value == Snapshot.NIL) {
466             throw new NoSuchElementException();
467         }
468         Cache.put(this, value);
469         return (T)value;
470     }
471 
472     /**
473      * {@return {@code true} if the extent local is bound to a value}
474      */
475     public boolean isBound() {
476         // ??? Do we want to search cache for this? In most cases we don't expect
477         // this {@link ExtentLocal} to be bound, so it's not worth it. But I may
478         // be wrong about that.
479 /*
480         if (Cache.find(this) != Snapshot.NIL) {
481             return true;
482         }
483  */
484         return findBinding() != Snapshot.NIL;
485     }
486 
487     /**
488      * Return the value of the extent local or NIL if not bound.
489      */
490     private Object findBinding() {
491         Object value = extentLocalBindings().find(this);
492         return value;
493     }
494 
495     /**
496      * Returns the value of the extent local if bound, otherwise returns {@code other}.
497      * @param other the value to return if not bound, can be {@code null}
498      * @return the value of the extent local if bound, otherwise {@code other}
499      */
500     public T orElse(T other) {
501         Object obj = findBinding();
502         if (obj != Snapshot.NIL) {
503             @SuppressWarnings("unchecked")
504             T value = (T) obj;
505             return value;
506         } else {
507             return other;
508         }
509     }
510 
511     /**
512      * Returns the value of the extent local if bound, otherwise throws the exception
513      * produced by the exception supplying function.
514      * @param <X> Type of the exception to be thrown
515      * @param exceptionSupplier the supplying function that produces the exception to throw
516      * @return the value of the extent local if bound
517      * @throws X prodouced by the exception suppying function if the extent local is unbound
518      */
519     public <X extends Throwable> T orElseThrow(Supplier<? extends X> exceptionSupplier) throws X {
520         Objects.requireNonNull(exceptionSupplier);
521         Object obj = findBinding();
522         if (obj != Snapshot.NIL) {
523             @SuppressWarnings("unchecked")
524             T value = (T) obj;
525             return value;
526         } else {
527             throw exceptionSupplier.get();
528         }
529     }
530 
531     private static Object[] extentLocalCache() {
532         return JLA.extentLocalCache();
533     }
534 
535     private static void setExtentLocalCache(Object[] cache) {
536         JLA.setExtentLocalCache(cache);
537     }
538 
539     private static Snapshot extentLocalBindings() {
540         Object bindings = JLA.extentLocalBindings();
541         if (bindings != null) {
542             return (Snapshot) bindings;
543         } else {
544             return EmptySnapshot.getInstance();
545         }
546     }
547 
548     private static void setExtentLocalBindings(Snapshot bindings) {
549         JLA.setExtentLocalBindings(bindings);
550     }
551 
552     private static int nextKey = 0xf0f0_f0f0;
553 
554     // A Marsaglia xor-shift generator used to generate hashes. This one has full period, so
555     // it generates 2**32 - 1 hashes before it repeats. We're going to use the lowest n bits
556     // and the next n bits as cache indexes, so we make sure that those indexes map
557     // to different slots in the cache.
558     private static synchronized int generateKey() {
559         int x = nextKey;
560         do {
561             x ^= x >>> 12;
562             x ^= x << 9;
563             x ^= x >>> 23;
564         } while (Cache.primarySlot(x) == Cache.secondarySlot(x));
565         return (nextKey = x);
566     }
567 
568     /**
569      * Return a bit mask that may be used to determine if this ExtentLocal is
570      * bound in the current context. Each Carrier holds a bit mask which is
571      * the OR of all the bit masks of the bound ExtentLocals.
572      * @return the bitmask
573      */
574     int bitmask() {
575         return (1 << Cache.primaryIndex(this)) | (1 << (Cache.secondaryIndex(this) + Cache.TABLE_SIZE));
576     }
577 
578     // Return true iff bitmask, considered as a set of bits, contains all
579     // of the bits in targetBits.
580     static boolean containsAll(int bitmask, int targetBits) {
581         return (bitmask & targetBits) == targetBits;
582     }
583 
584     // A small fixed-size key-value cache. When an extent local's get() method
585     // is invoked, we record the result of the lookup in this per-thread cache
586     // for fast access in future.
587     private static class Cache {
588         static final int INDEX_BITS = 4;  // Must be a power of 2
589         static final int TABLE_SIZE = 1 << INDEX_BITS;
590         static final int TABLE_MASK = TABLE_SIZE - 1;
591         static final int PRIMARY_MASK = (1 << TABLE_SIZE) - 1;
592 
593         // The number of elements in the cache array, and a bit mask used to
594         // select elements from it.
595         private static final int CACHE_TABLE_SIZE, SLOT_MASK;
596         // The largest cache we allow. Must be a power of 2 and greater than
597         // or equal to 2.
598         private static final int MAX_CACHE_SIZE = 16;
599 
600         static {
601             final String propertyName = "jdk.incubator.concurrent.ExtentLocal.cacheSize";
602             var sizeString = GetPropertyAction.privilegedGetProperty(propertyName, "16");
603             var cacheSize = Integer.valueOf(sizeString);
604             if (cacheSize < 2 || cacheSize > MAX_CACHE_SIZE) {
605                 cacheSize = MAX_CACHE_SIZE;
606                 System.err.println(propertyName + " is out of range: is " + sizeString);
607             }
608             if ((cacheSize & (cacheSize - 1)) != 0) {  // a power of 2
609                 cacheSize = MAX_CACHE_SIZE;
610                 System.err.println(propertyName + " must be an integer power of 2: is " + sizeString);
611             }
612             CACHE_TABLE_SIZE = cacheSize;
613             SLOT_MASK = cacheSize - 1;
614         }
615 
616         static final int primaryIndex(ExtentLocal<?> key) {
617             return key.hash & TABLE_MASK;
618         }
619 
620         static final int secondaryIndex(ExtentLocal<?> key) {
621             return (key.hash >> INDEX_BITS) & TABLE_MASK;
622         }
623 
624         private static final int primarySlot(ExtentLocal<?> key) {
625             return key.hashCode() & SLOT_MASK;
626         }
627 
628         private static final int secondarySlot(ExtentLocal<?> key) {
629             return (key.hash >> INDEX_BITS) & SLOT_MASK;
630         }
631 
632         static final int primarySlot(int hash) {
633             return hash & SLOT_MASK;
634         }
635 
636         static final int secondarySlot(int hash) {
637             return (hash >> INDEX_BITS) & SLOT_MASK;
638         }
639 
640         static void put(ExtentLocal<?> key, Object value) {
641             Object[] theCache = extentLocalCache();
642             if (theCache == null) {
643                 theCache = new Object[CACHE_TABLE_SIZE * 2];
644                 setExtentLocalCache(theCache);
645             }
646             // Update the cache to replace one entry with the value we just looked up.
647             // Each value can be in one of two possible places in the cache.
648             // Pick a victim at (pseudo-)random.
649             int k1 = primarySlot(key);
650             int k2 = secondarySlot(key);
651             var usePrimaryIndex = chooseVictim();
652             int victim = usePrimaryIndex ? k1 : k2;
653             int other = usePrimaryIndex ? k2 : k1;
654             setKeyAndObjectAt(victim, key, value);
655             if (getKey(theCache, other) == key) {
656                 setKeyAndObjectAt(other, key, value);
657             }
658         }
659 
660         private static void setKeyAndObjectAt(int n, Object key, Object value) {
661             var cache = extentLocalCache();
662             cache[n * 2] = key;
663             cache[n * 2 + 1] = value;
664         }
665 
666         private static Object getKey(Object[] objs, int n) {
667             return objs[n * 2];
668         }
669 
670         private static void setKey(Object[] objs, int n, Object key) {
671             objs[n * 2] = key;
672         }
673 
674         private static final JavaUtilConcurrentTLRAccess THREAD_LOCAL_RANDOM_ACCESS
675                 = SharedSecrets.getJavaUtilConcurrentTLRAccess();
676 
677         // Return either true or false, at pseudo-random, with a bias towards true.
678         // This chooses either the primary or secondary cache slot, but the
679         // primary slot is approximately twice as likely to be chosen as the
680         // secondary one.
681         private static boolean chooseVictim() {
682             int r = THREAD_LOCAL_RANDOM_ACCESS.nextSecondaryThreadLocalRandomSeed();
683             return (r & 15) >= 5;
684         }
685 
686         @ReservedStackAccess @DontInline
687         public static void invalidate() {
688             setExtentLocalCache(null);
689         }
690 
691         // Null a set of cache entries, indicated by the 1-bits given
692         @ReservedStackAccess @DontInline
693         static void invalidate(int toClearBits) {
694             toClearBits = (toClearBits >>> TABLE_SIZE) | (toClearBits & PRIMARY_MASK);
695             Object[] objects;
696             if ((objects = extentLocalCache()) != null) {
697                 for (int bits = toClearBits; bits != 0; ) {
698                     int index = Integer.numberOfTrailingZeros(bits);
699                     setKeyAndObjectAt(index & SLOT_MASK, null, null);
700                     bits &= ~1 << index;
701                 }
702             }
703         }
704     }
705 }