1 /*
  2  * Copyright (c) 2020, 2022, Oracle and/or its affiliates. All rights reserved.
  3  * Copyright (c) 2020, 2021, 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 java.lang;
 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 
 35 import jdk.internal.javac.PreviewFeature;
 36 import jdk.internal.vm.ScopeLocalContainer;
 37 import jdk.internal.vm.annotation.ForceInline;
 38 import jdk.internal.vm.annotation.Stable;
 39 import sun.security.action.GetPropertyAction;
 40 
 41 import static jdk.internal.javac.PreviewFeature.Feature.SCOPE_LOCALS;
 42 
 43 /**
 44  * Represents a scoped value.
 45  *
 46  * <p> A scope-local value (hereinafter called a scope local) differs from a normal variable in that it is dynamically
 47  * scoped and intended for cases where context needs to be passed from a caller
 48  * to a transitive callee without using an explicit parameter. A scope-local value
 49  * does not have a default/initial value: it is bound, meaning it gets a value,
 50  * when executing an operation specified to {@link #where(ScopeLocal, Object)}.
 51  * Code executed by the operation
 52  * uses the {@link #get()} method to get the value of the scope local. The scope local reverts
 53  * to being unbound (or its previous value) when the operation completes.
 54  *
 55  * <p> Access to the value of a scope local is controlled by the accessibility
 56  * of the {@code ScopeLocal} object. A {@code ScopeLocal} object  will typically be declared
 57  * in a private static field so that it can only be accessed by code in that class
 58  * (or other classes within its nest).
 59  *
 60  * <p> Scope locals  support nested bindings. If a scope local has a value
 61  * then the {@code runWithBinding} or {@code callWithBinding} can be invoked to run
 62  * another operation with a new value. Code executed by this methods "sees" the new
 63  * value of the scope local. The scope local reverts to its previous value when the
 64  * operation completes.
 65  *
 66  * <p> Unless otherwise specified, passing a {@code null} argument to a constructor
 67  * or method in this class will cause a {@link NullPointerException} to be thrown.
 68  *
 69  * @apiNote
 70  * The following example uses a scope local to make credentials available to callees.
 71  *
 72  * <pre>{@code
 73  *   private static final ScopeLocal<Credentials> CREDENTIALS = ScopeLocal.newInstance();
 74  *
 75  *   Credentials creds = ...
 76  *   ScopeLocal.where(CREDENTIALS, creds).run(() -> {
 77  *       :
 78  *       Connection connection = connectDatabase();
 79  *       :
 80  *   });
 81  *
 82  *   Connection connectDatabase() {
 83  *       Credentials credentials = CREDENTIALS.get();
 84  *       :
 85  *   }
 86  * }</pre>
 87  *
 88  * As an alternative to the lambda expression form used above, {@link ScopeLocal} also supports
 89  * a <i>try-with-resources</i> form, which looks like this:
 90  * <pre>{@code}
 91  *   try (var unused = ScopeLocal.where(CREDENTIALS, creds).bind()) {
 92  *       :
 93  *       Connection connection = connectDatabase();
 94  *       :
 95  *    }
 96  * }</pre>
 97  *
 98  * Note, however, that this version is <i>insecure</i>: it is up to the application programmer
 99  * to make sure that bindings are closed at the right time. While a <i>try-with-resources</i>
100  * statement is enough to guarantee this, there is no way to enforce the requirement that this form
101  * is only used in a <i>try-with-resources</i> statement.
102  * <p>Also, it is not possible to re-bind an already-bound {@link ScopeLocal} with this <i>try-with-resources</i> binding.</p>
103  * @param <T> the scope local's type
104  * @since 99
105  */
106 @PreviewFeature(feature=SCOPE_LOCALS)
107 public final class ScopeLocal<T> {
108     private final @Stable int hash;
109 
110     public final int hashCode() { return hash; }
111 
112     static final boolean PRESERVE_SCOPE_LOCAL_CACHE;
113     static {
114         // maybe rename to preserveScopeLocalCache to be consistent with other props
115         String value = GetPropertyAction.privilegedGetProperty("java.lang.ScopeLocal.preserveScopeLocalCache");
116         PRESERVE_SCOPE_LOCAL_CACHE = (value == null) || Boolean.parseBoolean(value);
117     }
118 
119     /**
120      * The interface for a ScopeLocal try-with-resources binding.
121      */
122     @PreviewFeature(feature = SCOPE_LOCALS)
123     public sealed interface Binder extends AutoCloseable permits BinderImpl {
124 
125         /**
126          * Closes this {@link ScopeLocal} binding. If this binding was not the most recent binding
127          * created by {@code Carrier.bind()}, throws a {@link StructureViolationException}.
128          * This method is invoked automatically on objects managed by the try-with-resources statement.
129          *
130          * @throws StructureViolationException if the bindings were not closed in the correct order.
131          */
132         public void close();
133     }
134     /**
135      * An immutable map from {@code ScopeLocal} to values.
136      *
137      * <p> Unless otherwise specified, passing a {@code null} argument to a constructor
138      * or method in this class will cause a {@link NullPointerException} to be thrown.
139      *
140      * @since 99
141      */
142     static sealed class Snapshot permits EmptySnapshot {
143         final Snapshot prev;
144         final Carrier bindings;
145         final int bitmask;
146 
147         private static final Object NIL = new Object();
148 
149         Snapshot(Carrier bindings, Snapshot prev) {
150             this.prev = prev;
151             this.bindings = bindings;
152             this.bitmask = bindings.bitmask | prev.bitmask;
153         }
154 
155         protected Snapshot() {
156             this.prev = null;
157             this.bindings = null;
158             this.bitmask = 0;
159         }
160 
161         Object find(ScopeLocal<?> key) {
162             int bits = key.bitmask();
163             for (Snapshot snapshot = this;
164                  containsAll(snapshot.bitmask, bits);
165                  snapshot = snapshot.prev) {
166                 for (Carrier carrier = snapshot.bindings;
167                      carrier != null && containsAll(carrier.bitmask, bits);
168                      carrier = carrier.prev) {
169                     if (carrier.getKey() == key) {
170                         Object value = carrier.get();
171                         return value;
172                     }
173                 }
174             }
175             return NIL;
176         }
177     }
178 
179     static final class EmptySnapshot extends Snapshot {
180 
181         private EmptySnapshot() {
182             super();
183         }
184 
185         private static final Snapshot SINGLETON = new EmptySnapshot();
186 
187         static final Snapshot getInstance() {
188             return SINGLETON;
189         }
190     }
191 
192     /**
193      * An immutable map from a set of ScopeLocals to their bound values.
194      * When map() or call() is invoked, the ScopeLocals bound in this set
195      * are bound, such that calling the get() method returns the associated
196      * value.
197      */
198     @PreviewFeature(feature=SCOPE_LOCALS)
199     public static final class Carrier {
200         // Bit masks: a 1 in postion n indicates that this set of bound values
201         // hits that slot in the cache.
202         final int bitmask;
203         final ScopeLocal<?> key;
204         final Object value;
205         final Carrier prev;
206 
207         Carrier(ScopeLocal<?> key, Object value, Carrier prev) {
208             this.key = key;
209             this.value = value;
210             this.prev = prev;
211             int bits = key.bitmask();
212             if (prev != null) {
213                 bits |= prev.bitmask;
214             }
215             this.bitmask = bits;
216         }
217 
218         /**
219          * Add a binding to this map, returning a new Carrier instance.
220          */
221         private static final <T> Carrier where(ScopeLocal<T> key, T value,
222                                                Carrier prev) {
223             return new Carrier(key, value, prev);
224         }
225 
226         /**
227          * Return a new map, which consists of the contents of this map plus a
228          * new binding of key and value.
229          * @param key   The ScopeLocal to bind a value to
230          * @param value The new value
231          * @param <T>   The type of the ScopeLocal
232          * @return A new map, consisting of {@code this}. plus a new binding. {@code this} is unchanged.
233          */
234         public final <T> Carrier where(ScopeLocal<T> key, T value) {
235             return where(key, value, this);
236         }
237 
238         /*
239          * Return a new set consisting of a single binding.
240          */
241         static final <T> Carrier of(ScopeLocal<T> key, T value) {
242             return where(key, value, null);
243         }
244 
245         final Object get() {
246             return value;
247         }
248 
249         final ScopeLocal<?> getKey() {
250             return key;
251         }
252 
253         /**
254          * Search for the value of a binding in this set
255          * @param key the ScopeLocal to find
256          * @param <T> the type of the ScopeLocal
257          * @return the value
258          * @throws NoSuchElementException if key is not bound to any value
259          *
260          */
261         @SuppressWarnings("unchecked")
262         public final <T> T get(ScopeLocal<T> key) {
263             var bits = key.bitmask();
264             for (Carrier carrier = this;
265                  carrier != null && containsAll(carrier.bitmask, bits);
266                  carrier = carrier.prev) {
267                 if (carrier.getKey() == key) {
268                     Object value = carrier.get();
269                     return (T)value;
270                 }
271             }
272             throw new NoSuchElementException();
273         }
274 
275         /**
276          * Run a value-returning operation with this some ScopeLocals bound to values.
277          * Code executed by the operation can use the {@link #get()} method to
278          * get the value of the scope local. The scope locals revert to their previous values or
279          * become {@linkplain #isBound() unbound} when the operation completes.
280          *
281          * <p> Scope locals are intended to be used in a <em>structured manner</em>. If the
282          * operation creates {@link java.util.concurrent.StructuredTaskScope StructuredTaskScope}s
283          * but does not close them, then exiting the operation causes the underlying construct
284          * of each executor to be closed (in the reverse order that they were created in), and
285          * {@link StructureViolationException} to be thrown.
286          *
287          * @param op    the operation to run
288          * @param <R>   the type of the result of the function
289          * @return the result
290          * @throws Exception if the operation completes with an exception
291          */
292         public final <R> R call(Callable<R> op) throws Exception {
293             Objects.requireNonNull(op);
294             Cache.invalidate(bitmask);
295             var prevBindings = addScopeLocalBindings(this);
296             try {
297                 return ScopeLocalContainer.call(op);
298             } catch (Throwable t) {
299                 Cache.invalidate();
300                 throw t;
301             } finally {
302                 Thread.currentThread().scopeLocalBindings = prevBindings;
303                 Cache.invalidate(bitmask);
304             }
305         }
306 
307         /**
308          * Run a value-returning operation with this set of ScopeLocals bound to values,
309          * in the same way as {@code call()}.<p>
310          *     If the operation throws an exception, pass it as a single argument to the {@link Function}
311          *     {@code handler}. {@code handler} must return a value compatible with the type returned by {@code op}.
312          * </p>
313          * @param op    the operation to run
314          * @param <R>   the type of the result of the function
315          * @param handler the handler to be applied if {code op} threw an exception
316          * @return the result.
317           */
318         public final <R> R callOrElse(Callable<R> op,
319                                       Function<? super Exception, ? extends R> handler) {
320             try {
321                 return call(op);
322             } catch (Exception e) {
323                 return handler.apply(e);
324             }
325         }
326 
327         /**
328          * Runs an operation with some ScopeLocals bound to our values.
329          * Code executed by the operation can use the {@link #get()} method to
330          * get the value of the scope local. The scope locals revert to their previous values or
331          * becomes {@linkplain #isBound() unbound} when the operation completes.
332          *
333          * <p> Scope locals are intended to be used in a <em>structured manner</em>. If the
334          * operation creates {@link java.util.concurrent.StructuredTaskScope StructuredTaskScope}s
335          * but does not close them, then exiting the operation causes the underlying construct
336          * of each executor to be closed (in the reverse order that they were created in), and
337          * {@link StructureViolationException} to be thrown.
338          *
339          * @param op    the operation to run
340          */
341         public final void run(Runnable op) {
342             Objects.requireNonNull(op);
343             Cache.invalidate(bitmask);
344             var prevBindings = addScopeLocalBindings(this);
345             try {
346                 ScopeLocalContainer.run(op);
347             } catch (Throwable t) {
348                 Cache.invalidate();
349                 throw t;
350             } finally {
351                 Thread.currentThread().scopeLocalBindings = prevBindings;
352                 Cache.invalidate(bitmask);
353             }
354         }
355 
356         /*
357          * Add a list of bindings to the current Thread's set of bound values.
358          */
359         private static final Snapshot addScopeLocalBindings(Carrier bindings) {
360             Snapshot prev = getScopeLocalBindings();
361             var b = new Snapshot(bindings, prev);
362             ScopeLocal.setScopeLocalBindings(b);
363             return prev;
364         }
365 
366         /*
367          * Ensure that none of these bindings is already bound.
368          */
369         void checkNotBound() {
370             for (Carrier c = this; c != null; c = c.prev) {
371                 if (c.key.isBound()) {
372                     throw new RuntimeException("Scope Local already bound");
373                 }
374             }
375         }
376 
377         /**
378          * Create a try-with-resources ScopeLocal binding to be used within
379          * a try-with-resources block.
380          * <p>If any of the {@link ScopeLocal}s bound in this {@link Carrier} are already bound in an outer context,
381          * throw a {@link RuntimeException}.</p>
382          * @return a {@link ScopeLocal.Binder}.
383          */
384         public ScopeLocal.Binder bind() {
385             checkNotBound();
386             return (Binder)new BinderImpl(this).push();
387         }
388     }
389 
390     /**
391      * An @AutoCloseable that's used to bind a {@code ScopeLocal} in a try-with-resources construct.
392      */
393     static final class BinderImpl
394             extends ScopeLocalContainer implements ScopeLocal.Binder {
395         final Carrier bindings;
396         final int bitmask;
397         final BinderImpl prevBinder;
398         private boolean closed;
399 
400         BinderImpl(Carrier bindings) {
401             super();
402             this.bindings = bindings;
403             this.prevBinder = innermostBinder();
404             this.bitmask = bindings.bitmask
405                     | (prevBinder == null ? 0 : prevBinder.bitmask);
406         }
407 
408         static BinderImpl innermostBinder() {
409             var container = ScopeLocalContainer.latest(BinderImpl.class);
410             if (container instanceof BinderImpl binder) {
411                 return binder;
412             } else {
413                 return null;
414             }
415         }
416 
417         /**
418          * Close a scope local binding context.
419          *
420          * @throws StructureViolationException if {@code this} isn't the current top binding
421          * @throws WrongThreadException if the current thread is not the owner
422          */
423         public void close() throws RuntimeException {
424             if (Thread.currentThread() != owner())
425                 throw new WrongThreadException();
426             if (!closed) {
427                 closed = true;
428                 Cache.invalidate(bindings.bitmask);
429                 if (!popForcefully()) {
430                     Cache.invalidate();
431                     throw new StructureViolationException();
432                 }
433             }
434         }
435 
436         protected boolean tryClose() {
437             assert Thread.currentThread() == owner();
438             if (!closed) {
439                 closed = true;
440                 Cache.invalidate(bindings.bitmask);
441                 return true;
442             } else {
443                 assert false : "Should not get there";
444                 return false;
445             }
446         }
447 
448         static Object find(ScopeLocal<?> key) {
449             int bits = key.bitmask();
450             for (BinderImpl b = innermostBinder();
451                  b != null && containsAll(b.bitmask, bits);
452                  b = b.prevBinder) {
453                 for (Carrier carrier = b.bindings;
454                      carrier != null && containsAll(carrier.bitmask, bits);
455                      carrier = carrier.prev) {
456                     if (carrier.getKey() == key) {
457                         Object value = carrier.get();
458                         return value;
459                     }
460                 }
461             }
462             return Snapshot.NIL;
463         }
464     }
465 
466     /**
467      * Create a binding for a ScopeLocal instance.
468      * That {@link Carrier} may be used later to invoke a {@link Callable} or
469      * {@link Runnable} instance. More bindings may be added to the {@link Carrier}
470      * by the {@link Carrier#where(ScopeLocal, Object)} method.
471      *
472      * @param key the ScopeLocal to bind
473      * @param value The value to bind it to
474      * @param <T> the type of the ScopeLocal
475      * @return A Carrier instance that contains one binding, that of key and value
476      */
477     public static <T> Carrier where(ScopeLocal<T> key, T value) {
478         return Carrier.of(key, value);
479     }
480 
481 
482     /**
483      * Create a try-with-resources ScopeLocal binding to be used within
484      * a try-with-resources block.
485      * <p>If this {@link ScopeLocal} is already bound in an outer context,
486      * throw a {@link RuntimeException}.</p>
487      * @param t The value to bind this to
488      * @return a {@link ScopeLocal.Binder}.
489      */
490     public ScopeLocal.Binder bind(T t) {
491         return where(this, t).bind();
492     }
493 
494     /**
495      * Creates a binding for a ScopeLocal instance and runs a value-returning
496      * operation with that bound ScopeLocal.
497      * @param key the ScopeLocal to bind
498      * @param value The value to bind it to
499      * @param <T> the type of the ScopeLocal
500      * @param <U> the type of the Result
501      * @param op the operation to call
502      * @return the result
503      * @throws Exception if the operation completes with an exception
504      */
505     public static <T, U> U where(ScopeLocal<T> key, T value, Callable<U> op) throws Exception {
506         return where(key, value).call(op);
507     }
508 
509     /**
510      * Creates a binding for a ScopeLocal instance and runs an
511      * operation with that bound ScopeLocal.
512      * @param key the ScopeLocal to bind
513      * @param value The value to bind it to
514      * @param <T> the type of the ScopeLocal
515      * @param op the operation to run
516      */
517     public static <T> void where(ScopeLocal<T> key, T value, Runnable op) {
518         where(key, value).run(op);
519     }
520 
521     private ScopeLocal() {
522         this.hash = generateKey();
523     }
524 
525     /**
526      * Creates a scope-local handle to refer to a value of type T.
527      *
528      * @param <T> the type of the scope local's value.
529      * @return a scope-local handle
530      */
531     public static <T> ScopeLocal<T> newInstance() {
532         return new ScopeLocal<T>();
533     }
534 
535     /**
536      * Returns the value of the scope local.
537      * @return the value of the scope local
538      * @throws NoSuchElementException if the scope local is not bound (exception is TBD)
539      */
540     @ForceInline
541     @SuppressWarnings("unchecked")
542     public T get() {
543         Object[] objects;
544         if ((objects = Thread.scopeLocalCache()) != null) {
545             // This code should perhaps be in class Cache. We do it
546             // here because the generated code is small and fast and
547             // we really want it to be inlined in the caller.
548             int n = (hash & Cache.TABLE_MASK) * 2;
549             if (objects[n] == this) {
550                 return (T)objects[n + 1];
551             }
552             n = ((hash >>> Cache.INDEX_BITS) & Cache.TABLE_MASK) * 2;
553             if (objects[n] == this) {
554                 return (T)objects[n + 1];
555             }
556         }
557         return slowGet();
558     }
559 
560     @SuppressWarnings("unchecked")
561     private T slowGet() {
562         var value = findBinding();
563         if (value == Snapshot.NIL) {
564             throw new NoSuchElementException();
565         }
566         Cache.put(this, value);
567         return (T)value;
568     }
569 
570     /**
571      * Returns {@code true} if the scope local is bound to a value.
572      *
573      * @return {@code true} if the scope local is bound to a value, otherwise {@code false}
574      */
575     @SuppressWarnings("unchecked")
576     public boolean isBound() {
577         // ??? Do we want to search cache for this? In most cases we don't expect
578         // this {@link ScopeLocal} to be bound, so it's not worth it. But I may
579         // be wrong about that.
580 /*
581         if (Cache.find(this) != Snapshot.NIL) {
582             return true;
583         }
584  */
585         return findBinding() != Snapshot.NIL;
586     }
587 
588     /**
589      * Return the value of the scope local or NIL if not bound.
590      */
591     private Object findBinding() {
592         Object value = scopeLocalBindings().find(this);
593         if (value != Snapshot.NIL) {
594             return value;
595         }
596         return BinderImpl.find(this);
597     }
598 
599     /**
600      * Return the value of the scope local if bound, otherwise returns {@code other}.
601      * @param other the value to return if not bound, can be {@code null}
602      * @return the value of the scope local if bound, otherwise {@code other}
603      */
604     public T orElse(T other) {
605         Object obj = findBinding();
606         if (obj != Snapshot.NIL) {
607             @SuppressWarnings("unchecked")
608             T value = (T) obj;
609             return value;
610         } else {
611             return other;
612         }
613     }
614 
615     /**
616      * Return the value of the scope local if bound, otherwise throw an exception
617      * produced by the exception supplying function.
618      * @param <X> Type of the exception to be thrown
619      * @param exceptionSupplier the supplying function that produces an
620      *        exception to be thrown
621      * @return the value of the scope local if bound
622      * @throws X if the scope local is unbound
623      */
624     public <X extends Throwable> T orElseThrow(Supplier<? extends X> exceptionSupplier) throws X {
625         Objects.requireNonNull(exceptionSupplier);
626         Object obj = findBinding();
627         if (obj != Snapshot.NIL) {
628             @SuppressWarnings("unchecked")
629             T value = (T) obj;
630             return value;
631         } else {
632             throw exceptionSupplier.get();
633         }
634     }
635 
636     private static Snapshot getScopeLocalBindings() {
637         return Thread.currentThread().scopeLocalBindings;
638     }
639 
640     private static void setScopeLocalBindings(Snapshot bindings) {
641         Thread currentThread = Thread.currentThread();
642         currentThread.scopeLocalBindings = bindings;
643     }
644 
645     private Snapshot scopeLocalBindings() {
646         return getScopeLocalBindings();
647     }
648 
649     private static int nextKey = 0xf0f0_f0f0;
650 
651     // A Marsaglia xor-shift generator used to generate hashes. This one has full period, so
652     // it generates 2**32 - 1 hashes before it repeats. We're going to use the lowest n bits
653     // and the next n bits as cache indexes, so we make sure that those indexes are
654     // different.
655     private static synchronized int generateKey() {
656         int x = nextKey;
657         do {
658             x ^= x >>> 12;
659             x ^= x << 9;
660             x ^= x >>> 23;
661         } while ((x & Cache.TABLE_MASK)
662                 == ((x >>> Cache.INDEX_BITS) & Cache.TABLE_MASK));
663         return (nextKey = x);
664     }
665 
666     /**
667      * Return a bit mask that may be used to determine if this ScopeLocal is
668      * bound in the current context. Each Carrier holds a bit mask which is
669      * the OR of all the bit masks of the bound ScopeLocals.
670      * @return the bitmask
671      */
672     int bitmask() {
673         return (1 << Cache.primaryIndex(this)) | (1 << (Cache.secondaryIndex(this) + Cache.TABLE_SIZE));
674     }
675 
676     // Return true iff bitmask, considered as a set of bits, contains all
677     // of the bits in targetBits.
678     static boolean containsAll(int bitmask, int targetBits) {
679         return (bitmask & targetBits) == targetBits;
680     }
681 
682     // A small fixed-size key-value cache. When a scope scope local's get() method
683     // is invoked, we record the result of the lookup in this per-thread cache
684     // for fast access in future.
685     private static class Cache {
686         static final int INDEX_BITS = 4;  // Must be a power of 2
687         static final int TABLE_SIZE = 1 << INDEX_BITS;
688         static final int TABLE_MASK = TABLE_SIZE - 1;
689         static final int PRIMARY_MASK = (1 << TABLE_SIZE) - 1;
690 
691         static final int primaryIndex(ScopeLocal<?> key) {
692             return key.hash & TABLE_MASK;
693         }
694 
695         static final int secondaryIndex(ScopeLocal<?> key) {
696             return (key.hash >> INDEX_BITS) & TABLE_MASK;
697         }
698 
699         static void put(ScopeLocal<?> key, Object value) {
700             Object[] theCache = Thread.scopeLocalCache();
701             if (theCache == null) {
702                 theCache = new Object[TABLE_SIZE * 2];
703                 Thread.setScopeLocalCache(theCache);
704             }
705             // Update the cache to replace one entry with the value we just looked up.
706             // Each value can be in one of two possible places in the cache.
707             // Pick a victim at (pseudo-)random.
708             Thread thread = Thread.currentThread();
709             int k1 = primaryIndex(key);
710             int k2 = secondaryIndex(key);
711             var usePrimaryIndex = chooseVictim(thread);
712             int victim = usePrimaryIndex ? k1 : k2;
713             int other = usePrimaryIndex ? k2 : k1;
714             setKeyAndObjectAt(victim, key, value);
715             if (getKey(theCache, other) == key) {
716                 setKey(theCache, other, null);
717             }
718         }
719 
720         private static final void update(Object key, Object value) {
721             Object[] objects;
722             if ((objects = Thread.scopeLocalCache()) != null) {
723                 int k1 = key.hashCode() & TABLE_MASK;
724                 if (getKey(objects, k1) == key) {
725                     setKeyAndObjectAt(k1, key, value);
726                 }
727                 int k2 = (key.hashCode() >> INDEX_BITS) & TABLE_MASK;
728                 if (getKey(objects, k2) == key) {
729                     setKeyAndObjectAt(k2, key, value);
730                 }
731             }
732         }
733 
734         private static final void remove(Object key) {
735             Object[] objects;
736             if ((objects = Thread.scopeLocalCache()) != null) {
737                 int k1 = key.hashCode() & TABLE_MASK;
738                 if (getKey(objects, k1) == key) {
739                     setKeyAndObjectAt(k1, null, null);
740                 }
741                 int k2 = (key.hashCode() >> INDEX_BITS) & TABLE_MASK;
742                 if (getKey(objects, k2) == key) {
743                     setKeyAndObjectAt(k2, null, null);
744                 }
745             }
746         }
747 
748 
749 /*
750         static Object find(ScopeLocal<?> key) {
751             Object[] objects;
752             var hash = key.hashCode();
753             if ((objects = Thread.scopeLocalCache()) != null) {
754                 // This code should perhaps be in class Cache. We do it
755                 // here because the generated code is small and fast and
756                 // we really want it to be inlined in the caller.
757                 int n = (hash & Cache.TABLE_MASK) * 2;
758                 if (objects[n] == key) {
759                     return objects[n + 1];
760                 }
761                 n = ((hash >>> Cache.INDEX_BITS) & Cache.TABLE_MASK) * 2;
762                 if (objects[n] == key) {
763                     return objects[n + 1];
764                 }
765             }
766             return Snapshot.NIL;
767         }
768 */
769 
770         private static void setKeyAndObjectAt(int n, Object key, Object value) {
771             Thread.scopeLocalCache()[n * 2] = key;
772             Thread.scopeLocalCache()[n * 2 + 1] = value;
773         }
774 
775         private static Object getKey(Object[] objs, int n) {
776             return objs[n * 2];
777         }
778 
779         private static void setKey(Object[] objs, int n, Object key) {
780             objs[n * 2] = key;
781         }
782 
783         // Return either true or false, at pseudo-random, with a bias towards true.
784         // This chooses either the primary or secondary cache slot, but the
785         // primary slot is approximately twice as likely to be chosen as the
786         // secondary one.
787         private static boolean chooseVictim(Thread thread) {
788             int tmp = thread.victims;
789             tmp ^= tmp << 13;
790             tmp ^= tmp >>> 17;
791             tmp ^= tmp << 5;
792             thread.victims = tmp;
793             return (tmp & 15) >= 5;
794         }
795 
796         public static void invalidate() {
797             Thread.setScopeLocalCache(null);
798         }
799 
800         // Null a set of cache entries, indicated by the 1-bits given
801         static void invalidate(int toClearBits) {
802             toClearBits = (toClearBits >>> TABLE_SIZE) | (toClearBits & PRIMARY_MASK);
803             Object[] objects;
804             if ((objects = Thread.scopeLocalCache()) != null) {
805                 for (int bits = toClearBits; bits != 0; ) {
806                     int index = Integer.numberOfTrailingZeros(bits);
807                     setKeyAndObjectAt(index, null, null);
808                     bits &= ~1 << index;
809                 }
810             }
811         }
812     }
813 }