1 /*
  2  * Copyright (c) 2020, 2024, 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 java.lang;
 28 
 29 import java.util.NoSuchElementException;
 30 import java.util.Objects;
 31 import java.lang.ref.Reference;
 32 import java.util.concurrent.StructuredTaskScope;
 33 import java.util.concurrent.StructureViolationException;
 34 import java.util.function.Supplier;
 35 import jdk.internal.access.JavaUtilConcurrentTLRAccess;
 36 import jdk.internal.access.SharedSecrets;
 37 import jdk.internal.javac.PreviewFeature;
 38 import jdk.internal.vm.annotation.ForceInline;
 39 import jdk.internal.vm.annotation.Hidden;
 40 import jdk.internal.vm.ScopedValueContainer;
 41 import sun.security.action.GetPropertyAction;
 42 
 43 /**
 44  * A value that may be safely and efficiently shared to methods without using method
 45  * parameters.
 46  *
 47  * <p> In the Java programming language, data is usually passed to a method by means of a
 48  * method parameter. The data may need to be passed through a sequence of many methods to
 49  * get to the method that makes use of the data. Every method in the sequence of calls
 50  * needs to declare the parameter and every method has access to the data.
 51  * {@code ScopedValue} provides a means to pass data to a faraway method (typically a
 52  * <em>callback</em>) without using method parameters. In effect, a {@code ScopedValue}
 53  * is an <em>implicit method parameter</em>. It is "as if" every method in a sequence of
 54  * calls has an additional parameter. None of the methods declare the parameter and only
 55  * the methods that have access to the {@code ScopedValue} object can access its value
 56  * (the data). {@code ScopedValue} makes it possible to securely pass data from a
 57  * <em>caller</em> to a faraway <em>callee</em> through a sequence of intermediate methods
 58  * that do not declare a parameter for the data and have no access to the data.
 59  *
 60  * <p> The {@code ScopedValue} API works by executing a method with a {@code ScopedValue}
 61  * object <em>bound</em> to some value for the bounded period of execution of a method.
 62  * The method may invoke another method, which in turn may invoke another. The unfolding
 63  * execution of the methods define a <em>dynamic scope</em>. Code in these methods with
 64  * access to the {@code ScopedValue} object may read its value. The {@code ScopedValue}
 65  * object reverts to being <em>unbound</em> when the original method completes normally or
 66  * with an exception. The {@code ScopedValue} API supports executing a {@link Runnable},
 67  * or {@link CallableOp} with a {@code ScopedValue} bound to a value.
 68  *
 69  * <p> Consider the following example with a scoped value "{@code NAME}" bound to the value
 70  * "{@code duke}" for the execution of a {@code Runnable}'s {@code run} method.
 71  * The {@code run} method, in turn, invokes a method {@code doSomething}.
 72  *
 73  *
 74  * {@snippet lang=java :
 75  *     // @link substring="newInstance" target="#newInstance" :
 76  *     private static final ScopedValue<String> NAME = ScopedValue.newInstance();
 77  *
 78  *     // @link substring="run" target="Carrier#run(Runnable)" :
 79  *     ScopedValue.where(NAME, "duke").run(() -> doSomething());
 80  * }
 81  * Code executed directly or indirectly by {@code doSomething}, with access to the field
 82  * {@code NAME}, can invoke {@code NAME.get()} to read the value "{@code duke}". {@code
 83  * NAME} is bound while executing the {@code run} method. It reverts to being unbound when
 84  * the {@code run} method completes.
 85  *
 86  * <p> The example using {@code run} invokes a method that does not return a result.
 87  * The {@link Carrier#call(CallableOp) call} method can be used
 88  * to invoke a method that returns a result.
 89  * {@code ScopedValue} defines the {@link #where(ScopedValue, Object)} method
 90  * for cases where multiple mappings (of {@code ScopedValue} to value) are accumulated
 91  * in advance of calling a method with all {@code ScopedValue}s bound to their value.
 92  *
 93  * <h2>Bindings are per-thread</h2>
 94  *
 95  * A {@code ScopedValue} binding to a value is per-thread. Invoking {@code run}
 96  * executes a method with a {@code ScopedValue} bound to a value for the current thread.
 97  * The {@link #get() get} method returns the value bound for the current thread.
 98  *
 99  * <p> In the example, if code executed by one thread invokes this:
100  * {@snippet lang=java :
101  *     ScopedValue.where(NAME, "duke1").run(() -> doSomething());
102  * }
103  * and code executed by another thread invokes:
104  * {@snippet lang=java :
105  *     ScopedValue.where(NAME, "duke2").run(() -> doSomething());
106  * }
107  * then code in {@code doSomething} (or any method that it calls) invoking {@code NAME.get()}
108  * will read the value "{@code duke1}" or "{@code duke2}", depending on which thread is
109  * executing.
110  *
111  * <h2>Scoped values as capabilities</h2>
112  *
113  * A {@code ScopedValue} object should be treated as a <em>capability</em> or a key to
114  * access its value when the {@code ScopedValue} is bound. Secure usage depends on access
115  * control (see <cite>The Java Virtual Machine Specification</cite>, Section {@jvms 5.4.4})
116  * and taking care to not share the {@code ScopedValue} object. In many cases, a {@code
117  * ScopedValue} will be declared in a {@code final} and {@code static} field so that it
118  * is only accessible to code in a single class (or nest).
119  *
120  * <h2><a id="rebind">Rebinding</a></h2>
121  *
122  * The {@code ScopedValue} API allows a new binding to be established for <em>nested
123  * dynamic scopes</em>. This is known as <em>rebinding</em>. A {@code ScopedValue} that
124  * is bound to a value may be bound to a new value for the bounded execution of a new
125  * method. The unfolding execution of code executed by that method defines the nested
126  * dynamic scope. When the method completes, the value of the {@code ScopedValue} reverts
127  * to its previous value.
128  *
129  * <p> In the above example, suppose that code executed by {@code doSomething} binds
130  * {@code NAME} to a new value with:
131  * {@snippet lang=java :
132  *     ScopedValue.where(NAME, "duchess").run(() -> doMore());
133  * }
134  * Code executed directly or indirectly by {@code doMore()} that invokes {@code
135  * NAME.get()} will read the value "{@code duchess}". When {@code doMore()} completes
136  * then the value of {@code NAME} reverts to "{@code duke}".
137  *
138  * <h2><a id="inheritance">Inheritance</a></h2>
139  *
140  * {@code ScopedValue} supports sharing across threads. This sharing is limited to
141  * structured cases where child threads are started and terminate within the bounded
142  * period of execution by a parent thread. When using a {@link StructuredTaskScope},
143  * scoped value bindings are <em>captured</em> when creating a {@code StructuredTaskScope}
144  * and inherited by all threads started in that task scope with the
145  * {@link StructuredTaskScope#fork(java.util.concurrent.Callable) fork} method.
146  *
147  * <p> A {@code ScopedValue} that is shared across threads requires that the value be an
148  * immutable object or for all access to the value to be appropriately synchronized.
149  *
150  * <p> In the following example, the {@code ScopedValue} {@code NAME} is bound to the
151  * value "{@code duke}" for the execution of a runnable operation. The code in the {@code
152  * run} method creates a {@code StructuredTaskScope} that forks three tasks. Code executed
153  * directly or indirectly by these threads running {@code childTask1()}, {@code childTask2()},
154  * and {@code childTask3()} that invokes {@code NAME.get()} will read the value
155  * "{@code duke}".
156  *
157  * {@snippet lang=java :
158  *     private static final ScopedValue<String> NAME = ScopedValue.newInstance();
159 
160  *     ScopedValue.where(NAME, "duke").run(() -> {
161  *         // @link substring="open" target="StructuredTaskScope#open()" :
162  *         try (var scope = StructuredTaskScope.open()) {
163  *
164  *              // @link substring="fork" target="StructuredTaskScope#fork(java.util.concurrent.Callable)" :
165  *              scope.fork(() -> childTask1());
166  *              scope.fork(() -> childTask2());
167  *              scope.fork(() -> childTask3());
168  *
169  *              // @link substring="join" target="StructuredTaskScope#join()" :
170  *              scope.join();
171  *
172  *              ..
173  *          }
174  *     });
175  * }
176  *
177  * <p> Unless otherwise specified, passing a {@code null} argument to a method in this
178  * class will cause a {@link NullPointerException} to be thrown.
179  *
180  * @apiNote
181  * A {@code ScopedValue} should be preferred over a {@link ThreadLocal} for cases where
182  * the goal is "one-way transmission" of data without using method parameters.  While a
183  * {@code ThreadLocal} can be used to pass data to a method without using method parameters,
184  * it does suffer from a number of issues:
185  * <ol>
186  *   <li> {@code ThreadLocal} does not prevent code in a faraway callee from {@linkplain
187  *   ThreadLocal#set(Object) setting} a new value.
188  *   <li> A {@code ThreadLocal} has an unbounded lifetime and thus continues to have a value
189  *   after a method completes, unless explicitly {@linkplain ThreadLocal#remove() removed}.
190  *   <li> {@linkplain InheritableThreadLocal Inheritance} is expensive - the map of
191  *   thread-locals to values must be copied when creating each child thread.
192  * </ol>
193  *
194  * @implNote
195  * Scoped values are designed to be used in fairly small
196  * numbers. {@link #get} initially performs a search through enclosing
197  * scopes to find a scoped value's innermost binding. It
198  * then caches the result of the search in a small thread-local
199  * cache. Subsequent invocations of {@link #get} for that scoped value
200  * will almost always be very fast. However, if a program has many
201  * scoped values that it uses cyclically, the cache hit rate
202  * will be low and performance will be poor. This design allows
203  * scoped-value inheritance by {@link StructuredTaskScope} threads to
204  * be very fast: in essence, no more than copying a pointer, and
205  * leaving a scoped-value binding also requires little more than
206  * updating a pointer.
207  *
208  * <p>Because the scoped-value per-thread cache is small, clients
209  * should minimize the number of bound scoped values in use. For
210  * example, if it is necessary to pass a number of values in this way,
211  * it makes sense to create a record class to hold those values, and
212  * then bind a single {@code ScopedValue} to an instance of that record.
213  *
214  * <p>For this release, the reference implementation
215  * provides some system properties to tune the performance of scoped
216  * values.
217  *
218  * <p>The system property {@code java.lang.ScopedValue.cacheSize}
219  * controls the size of the (per-thread) scoped-value cache. This cache is crucial
220  * for the performance of scoped values. If it is too small,
221  * the runtime library will repeatedly need to scan for each
222  * {@link #get}. If it is too large, memory will be unnecessarily
223  * consumed. The default scoped-value cache size is 16 entries. It may
224  * be varied from 2 to 16 entries in size. {@code ScopedValue.cacheSize}
225  * must be an integer power of 2.
226  *
227  * <p>For example, you could use {@code -Djava.lang.ScopedValue.cacheSize=8}.
228  *
229  * <p>The other system property is {@code jdk.preserveScopedValueCache}.
230  * This property determines whether the per-thread scoped-value
231  * cache is preserved when a virtual thread is blocked. By default
232  * this property is set to {@code true}, meaning that every virtual
233  * thread preserves its scoped-value cache when blocked. Like {@code
234  * ScopedValue.cacheSize}, this is a space versus speed trade-off: in
235  * situations where many virtual threads are blocked most of the time,
236  * setting this property to {@code false} might result in a useful
237  * memory saving, but each virtual thread's scoped-value cache would
238  * have to be regenerated after a blocking operation.
239  *
240  * @param <T> the type of the value
241  * @since 21
242  */
243 @PreviewFeature(feature = PreviewFeature.Feature.SCOPED_VALUES)
244 public final class ScopedValue<T> {
245     private final int hash;
246 
247     @Override
248     public int hashCode() { return hash; }
249 
250     /**
251      * An immutable map from {@code ScopedValue} to values.
252      *
253      * <p> Unless otherwise specified, passing a {@code null} argument to a constructor
254      * or method in this class will cause a {@link NullPointerException} to be thrown.
255      */
256     static final class Snapshot {
257         final Snapshot prev;
258         final Carrier bindings;
259         final int bitmask;
260 
261         private static final Object NIL = new Object();
262 
263         static final Snapshot EMPTY_SNAPSHOT = new Snapshot();
264 
265         Snapshot(Carrier bindings, Snapshot prev) {
266             this.prev = prev;
267             this.bindings = bindings;
268             this.bitmask = bindings.bitmask | prev.bitmask;
269         }
270 
271         protected Snapshot() {
272             this.prev = null;
273             this.bindings = null;
274             this.bitmask = 0;
275         }
276 
277         Object find(ScopedValue<?> key) {
278             int bits = key.bitmask();
279             for (Snapshot snapshot = this;
280                  containsAll(snapshot.bitmask, bits);
281                  snapshot = snapshot.prev) {
282                 for (Carrier carrier = snapshot.bindings;
283                      carrier != null && containsAll(carrier.bitmask, bits);
284                      carrier = carrier.prev) {
285                     if (carrier.getKey() == key) {
286                         Object value = carrier.get();
287                         return value;
288                     }
289                 }
290             }
291             return NIL;
292         }
293     }
294 
295     /**
296      * A mapping of scoped values, as <em>keys</em>, to values.
297      *
298      * <p> A {@code Carrier} is used to accumulate mappings so that an operation (a {@link
299      * Runnable} or {@link CallableOp}) can be executed with all scoped values in the
300      * mapping bound to values. The following example runs an operation with {@code k1}
301      * bound (or rebound) to {@code v1}, and {@code k2} bound (or rebound) to {@code v2}.
302      * {@snippet lang=java :
303      *     // @link substring="where" target="#where(ScopedValue, Object)" :
304      *     ScopedValue.where(k1, v1).where(k2, v2).run(() -> ... );
305      * }
306      *
307      * <p> A {@code Carrier} is immutable and thread-safe. The {@link
308      * #where(ScopedValue, Object) where} method returns a new {@code Carrier} object,
309      * it does not mutate an existing mapping.
310      *
311      * <p> Unless otherwise specified, passing a {@code null} argument to a method in
312      * this class will cause a {@link NullPointerException} to be thrown.
313      *
314      * @since 21
315      */
316     @PreviewFeature(feature = PreviewFeature.Feature.SCOPED_VALUES)
317     public static final class Carrier {
318         // Bit masks: a 1 in postion n indicates that this set of bound values
319         // hits that slot in the cache.
320         final int bitmask;
321         final ScopedValue<?> key;
322         final Object value;
323         final Carrier prev;
324 
325         Carrier(ScopedValue<?> key, Object value, Carrier prev) {
326             this.key = key;
327             this.value = value;
328             this.prev = prev;
329             int bits = key.bitmask();
330             if (prev != null) {
331                 bits |= prev.bitmask;
332             }
333             this.bitmask = bits;
334         }
335 
336         /**
337          * Add a binding to this map, returning a new Carrier instance.
338          */
339         private static <T> Carrier where(ScopedValue<T> key, T value, Carrier prev) {
340             return new Carrier(key, value, prev);
341         }
342 
343         /**
344          * Returns a new {@code Carrier} with the mappings from this carrier plus a
345          * new mapping from {@code key} to {@code value}. If this carrier already has a
346          * mapping for the scoped value {@code key} then it will map to the new
347          * {@code value}. The current carrier is immutable, so it is not changed by this
348          * method.
349          *
350          * @param key the {@code ScopedValue} key
351          * @param value the value, can be {@code null}
352          * @param <T> the type of the value
353          * @return a new {@code Carrier} with the mappings from this carrier plus the new mapping
354          */
355         public <T> Carrier where(ScopedValue<T> key, T value) {
356             return where(key, value, this);
357         }
358 
359         /*
360          * Return a new set consisting of a single binding.
361          */
362         static <T> Carrier of(ScopedValue<T> key, T value) {
363             return where(key, value, null);
364         }
365 
366         Object get() {
367             return value;
368         }
369 
370         ScopedValue<?> getKey() {
371             return key;
372         }
373 
374         /**
375          * Returns the value of a {@link ScopedValue} in this mapping.
376          *
377          * @param key the {@code ScopedValue} key
378          * @param <T> the type of the value
379          * @return the value
380          * @throws NoSuchElementException if the key is not present in this mapping
381          */
382         @SuppressWarnings("unchecked")
383         public <T> T get(ScopedValue<T> key) {
384             var bits = key.bitmask();
385             for (Carrier carrier = this;
386                  carrier != null && containsAll(carrier.bitmask, bits);
387                  carrier = carrier.prev) {
388                 if (carrier.getKey() == key) {
389                     Object value = carrier.get();
390                     return (T) value;
391                 }
392             }
393             throw new NoSuchElementException("No mapping present");
394         }
395 
396         /**
397          * Calls a value-returning operation with each scoped value in this mapping bound
398          * to its value in the current thread.
399          * When the operation completes (normally or with an exception), each scoped value
400          * in the mapping will revert to being unbound, or revert to its previous value
401          * when previously bound, in the current thread. If {@code op} completes with an
402          * exception then it propagated by this method.
403          *
404          * <p> Scoped values are intended to be used in a <em>structured manner</em>. If code
405          * invoked directly or indirectly by the operation creates a {@link StructuredTaskScope}
406          * but does not {@linkplain StructuredTaskScope#close() close} it, then it is detected
407          * as a <em>structure violation</em> when the operation completes (normally or with an
408          * exception). In that case, the underlying construct of the {@code StructuredTaskScope}
409          * is closed and {@link StructureViolationException} is thrown.
410          *
411          * @param op the operation to run
412          * @param <R> the type of the result of the operation
413          * @param <X> type of the exception thrown by the operation
414          * @return the result
415          * @throws StructureViolationException if a structure violation is detected
416          * @throws X if {@code op} completes with an exception

417          * @since 23
418          */
419         public <R, X extends Throwable> R call(CallableOp<? extends R, X> op) throws X {
420             Objects.requireNonNull(op);
421             Cache.invalidate(bitmask);
422             var prevSnapshot = scopedValueBindings();
423             var newSnapshot = new Snapshot(this, prevSnapshot);
424             return runWith(newSnapshot, op);
425         }
426 
427         /**
428          * Execute the action with a set of ScopedValue bindings.
429          *
430          * The VM recognizes this method as special, so any changes to the
431          * name or signature require corresponding changes in
432          * JVM_FindScopedValueBindings().
433          */
434         @Hidden
435         @ForceInline
436         private <R, X extends Throwable> R runWith(Snapshot newSnapshot, CallableOp<R, X> op) {
437             try {
438                 Thread.setScopedValueBindings(newSnapshot);
439                 Thread.ensureMaterializedForStackWalk(newSnapshot);
440                 return ScopedValueContainer.call(op);
441             } finally {
442                 Reference.reachabilityFence(newSnapshot);
443                 Thread.setScopedValueBindings(newSnapshot.prev);
444                 Cache.invalidate(bitmask);
445             }
446         }
447 
448         /**
449          * Runs an operation with each scoped value in this mapping bound to its value
450          * in the current thread.
451          * When the operation completes (normally or with an exception), each scoped value
452          * in the mapping will revert to being unbound, or revert to its previous value
453          * when previously bound, in the current thread. If {@code op} completes with an
454          * exception then it propagated by this method.
455          *
456          * <p> Scoped values are intended to be used in a <em>structured manner</em>. If code
457          * invoked directly or indirectly by the operation creates a {@link StructuredTaskScope}
458          * but does not {@linkplain StructuredTaskScope#close() close} it, then it is detected
459          * as a <em>structure violation</em> when the operation completes (normally or with an
460          * exception). In that case, the underlying construct of the {@code StructuredTaskScope}
461          * is closed and {@link StructureViolationException} is thrown.
462          *
463          * @param op the operation to run
464          * @throws StructureViolationException if a structure violation is detected

465          */
466         public void run(Runnable op) {
467             Objects.requireNonNull(op);
468             Cache.invalidate(bitmask);
469             var prevSnapshot = scopedValueBindings();
470             var newSnapshot = new Snapshot(this, prevSnapshot);
471             runWith(newSnapshot, op);
472         }
473 
474         /**
475          * Execute the action with a set of {@code ScopedValue} bindings.
476          *
477          * The VM recognizes this method as special, so any changes to the
478          * name or signature require corresponding changes in
479          * JVM_FindScopedValueBindings().
480          */
481         @Hidden
482         @ForceInline
483         private void runWith(Snapshot newSnapshot, Runnable op) {
484             try {
485                 Thread.setScopedValueBindings(newSnapshot);
486                 Thread.ensureMaterializedForStackWalk(newSnapshot);
487                 ScopedValueContainer.run(op);
488             } finally {
489                 Reference.reachabilityFence(newSnapshot);
490                 Thread.setScopedValueBindings(newSnapshot.prev);
491                 Cache.invalidate(bitmask);
492             }
493         }
494     }
495 
496     /**
497      * An operation that returns a result and may throw an exception.
498      *
499      * @param <T> result type of the operation
500      * @param <X> type of the exception thrown by the operation
501      * @since 23
502      */
503     @PreviewFeature(feature = PreviewFeature.Feature.SCOPED_VALUES)
504     @FunctionalInterface
505     public interface CallableOp<T, X extends Throwable> {
506         /**
507          * Executes this operation.
508          * @return the result, can be null
509          * @throws X if the operation completes with an exception
510          */
511         T call() throws X;
512     }
513 
514     /**
515      * Creates a new {@code Carrier} with a single mapping of a {@code ScopedValue}
516      * <em>key</em> to a value. The {@code Carrier} can be used to accumulate mappings so
517      * that an operation can be executed with all scoped values in the mapping bound to
518      * values. The following example runs an operation with {@code k1} bound (or rebound)
519      * to {@code v1}, and {@code k2} bound (or rebound) to {@code v2}.
520      * {@snippet lang=java :
521      *     // @link substring="run" target="Carrier#run(Runnable)" :
522      *     ScopedValue.where(k1, v1).where(k2, v2).run(() -> ... );
523      * }
524      *
525      * @param key the {@code ScopedValue} key
526      * @param value the value, can be {@code null}
527      * @param <T> the type of the value
528      * @return a new {@code Carrier} with a single mapping
529      */
530     public static <T> Carrier where(ScopedValue<T> key, T value) {
531         return Carrier.of(key, value);
532     }
533 







































































534     private ScopedValue() {
535         this.hash = generateKey();
536     }
537 
538     /**
539      * Creates a scoped value that is initially unbound for all threads.
540      *
541      * @param <T> the type of the value
542      * @return a new {@code ScopedValue}
543      */
544     public static <T> ScopedValue<T> newInstance() {
545         return new ScopedValue<T>();
546     }
547 
548     /**
549      * {@return the value of the scoped value if bound in the current thread}
550      *
551      * @throws NoSuchElementException if the scoped value is not bound
552      */
553     @ForceInline
554     @SuppressWarnings("unchecked")
555     public T get() {
556         Object[] objects;
557         if ((objects = scopedValueCache()) != null) {
558             // This code should perhaps be in class Cache. We do it
559             // here because the generated code is small and fast and
560             // we really want it to be inlined in the caller.
561             int n = (hash & Cache.SLOT_MASK) * 2;
562             if (objects[n] == this) {
563                 return (T)objects[n + 1];
564             }
565             n = ((hash >>> Cache.INDEX_BITS) & Cache.SLOT_MASK) * 2;
566             if (objects[n] == this) {
567                 return (T)objects[n + 1];
568             }
569         }
570         return slowGet();
571     }
572 
573     @SuppressWarnings("unchecked")
574     private T slowGet() {
575         var value = findBinding();
576         if (value == Snapshot.NIL) {
577             throw new NoSuchElementException("ScopedValue not bound");
578         }
579         Cache.put(this, value);
580         return (T)value;
581     }
582 
583     /**
584      * {@return {@code true} if this scoped value is bound in the current thread}
585      */
586     public boolean isBound() {
587         Object[] objects = scopedValueCache();
588         if (objects != null) {
589             int n = (hash & Cache.SLOT_MASK) * 2;
590             if (objects[n] == this) {
591                 return true;
592             }
593             n = ((hash >>> Cache.INDEX_BITS) & Cache.SLOT_MASK) * 2;
594             if (objects[n] == this) {
595                 return true;
596             }
597         }
598         var value = findBinding();
599         boolean result = (value != Snapshot.NIL);
600         if (result)  Cache.put(this, value);
601         return result;
602     }
603 
604     /**
605      * Return the value of the scoped value or NIL if not bound.
606      */
607     private Object findBinding() {
608         Object value = scopedValueBindings().find(this);
609         return value;
610     }
611 
612     /**
613      * Returns the value of this scoped value if bound in the current thread, otherwise
614      * returns {@code other}.
615      *
616      * @param other the value to return if not bound, can be {@code null}
617      * @return the value of the scoped value if bound, otherwise {@code other}
618      */
619     public T orElse(T other) {
620         Object obj = findBinding();
621         if (obj != Snapshot.NIL) {
622             @SuppressWarnings("unchecked")
623             T value = (T) obj;
624             return value;
625         } else {
626             return other;
627         }
628     }
629 
630     /**
631      * Returns the value of this scoped value if bound in the current thread, otherwise
632      * throws an exception produced by the exception supplying function.
633      *
634      * @param <X> the type of the exception that may be thrown
635      * @param exceptionSupplier the supplying function that produces the exception to throw
636      * @return the value of the scoped value if bound in the current thread
637      * @throws X if the scoped value is not bound in the current thread
638      */
639     public <X extends Throwable> T orElseThrow(Supplier<? extends X> exceptionSupplier) throws X {
640         Objects.requireNonNull(exceptionSupplier);
641         Object obj = findBinding();
642         if (obj != Snapshot.NIL) {
643             @SuppressWarnings("unchecked")
644             T value = (T) obj;
645             return value;
646         } else {
647             throw exceptionSupplier.get();
648         }
649     }
650 
651     private static Object[] scopedValueCache() {
652         return Thread.scopedValueCache();
653     }
654 
655     private static void setScopedValueCache(Object[] cache) {
656         Thread.setScopedValueCache(cache);
657     }
658 
659     // Special value to indicate this is a newly-created Thread
660     // Note that his must match the declaration in j.l.Thread.
661     private static final Object NEW_THREAD_BINDINGS = Thread.class;
662 
663     private static Snapshot scopedValueBindings() {
664         // Bindings can be in one of four states:
665         //
666         // 1: class Thread: this is a new Thread instance, and no
667         // scoped values have ever been bound in this Thread, and neither
668         // have any scoped value bindings been inherited from a parent.
669         // 2: EmptySnapshot.SINGLETON: This is effectively an empty binding.
670         // 3: A Snapshot instance: this contains one or more scoped value
671         // bindings.
672         // 4: null: there may be some bindings in this Thread, but we don't know
673         // where they are. We must invoke Thread.findScopedValueBindings() to walk
674         // the stack to find them.
675 
676         Object bindings = Thread.scopedValueBindings();
677         if (bindings == NEW_THREAD_BINDINGS) {
678             // This must be a new thread
679             return Snapshot.EMPTY_SNAPSHOT;
680         }
681         if (bindings == null) {
682             // Search the stack
683             bindings = Thread.findScopedValueBindings();
684             if (bindings == NEW_THREAD_BINDINGS || bindings == null) {
685                 // We've walked the stack without finding anything.
686                 bindings = Snapshot.EMPTY_SNAPSHOT;
687             }
688             Thread.setScopedValueBindings(bindings);
689         }
690         assert (bindings != null);
691         return (Snapshot) bindings;
692     }
693 
694     private static int nextKey = 0xf0f0_f0f0;
695 
696     // A Marsaglia xor-shift generator used to generate hashes. This one has full period, so
697     // it generates 2**32 - 1 hashes before it repeats. We're going to use the lowest n bits
698     // and the next n bits as cache indexes, so we make sure that those indexes map
699     // to different slots in the cache.
700     private static synchronized int generateKey() {
701         int x = nextKey;
702         do {
703             x ^= x >>> 12;
704             x ^= x << 9;
705             x ^= x >>> 23;
706         } while (Cache.primarySlot(x) == Cache.secondarySlot(x));
707         return (nextKey = x);
708     }
709 
710     /**
711      * Return a bit mask that may be used to determine if this ScopedValue is
712      * bound in the current context. Each Carrier holds a bit mask which is
713      * the OR of all the bit masks of the bound ScopedValues.
714      * @return the bitmask
715      */
716     int bitmask() {
717         return (1 << Cache.primaryIndex(this)) | (1 << (Cache.secondaryIndex(this) + Cache.TABLE_SIZE));
718     }
719 
720     // Return true iff bitmask, considered as a set of bits, contains all
721     // of the bits in targetBits.
722     static boolean containsAll(int bitmask, int targetBits) {
723         return (bitmask & targetBits) == targetBits;
724     }
725 
726     // A small fixed-size key-value cache. When a scoped value's get() method
727     // is invoked, we record the result of the lookup in this per-thread cache
728     // for fast access in future.
729     private static final class Cache {
730         static final int INDEX_BITS = 4;  // Must be a power of 2
731         static final int TABLE_SIZE = 1 << INDEX_BITS;
732         static final int TABLE_MASK = TABLE_SIZE - 1;
733         static final int PRIMARY_MASK = (1 << TABLE_SIZE) - 1;
734 
735         // The number of elements in the cache array, and a bit mask used to
736         // select elements from it.
737         private static final int CACHE_TABLE_SIZE, SLOT_MASK;
738         // The largest cache we allow. Must be a power of 2 and greater than
739         // or equal to 2.
740         private static final int MAX_CACHE_SIZE = 16;
741 
742         static {
743             final String propertyName = "java.lang.ScopedValue.cacheSize";
744             var sizeString = GetPropertyAction.privilegedGetProperty(propertyName, "16");
745             var cacheSize = Integer.valueOf(sizeString);
746             if (cacheSize < 2 || cacheSize > MAX_CACHE_SIZE) {
747                 cacheSize = MAX_CACHE_SIZE;
748                 System.err.println(propertyName + " is out of range: is " + sizeString);
749             }
750             if ((cacheSize & (cacheSize - 1)) != 0) {  // a power of 2
751                 cacheSize = MAX_CACHE_SIZE;
752                 System.err.println(propertyName + " must be an integer power of 2: is " + sizeString);
753             }
754             CACHE_TABLE_SIZE = cacheSize;
755             SLOT_MASK = cacheSize - 1;
756         }
757 
758         static int primaryIndex(ScopedValue<?> key) {
759             return key.hash & TABLE_MASK;
760         }
761 
762         static int secondaryIndex(ScopedValue<?> key) {
763             return (key.hash >> INDEX_BITS) & TABLE_MASK;
764         }
765 
766         private static int primarySlot(ScopedValue<?> key) {
767             return key.hashCode() & SLOT_MASK;
768         }
769 
770         private static int secondarySlot(ScopedValue<?> key) {
771             return (key.hash >> INDEX_BITS) & SLOT_MASK;
772         }
773 
774         static int primarySlot(int hash) {
775             return hash & SLOT_MASK;
776         }
777 
778         static int secondarySlot(int hash) {
779             return (hash >> INDEX_BITS) & SLOT_MASK;
780         }
781 
782         static void put(ScopedValue<?> key, Object value) {
783             Object[] theCache = scopedValueCache();
784             if (theCache == null) {
785                 theCache = new Object[CACHE_TABLE_SIZE * 2];
786                 setScopedValueCache(theCache);
787             }
788             // Update the cache to replace one entry with the value we just looked up.
789             // Each value can be in one of two possible places in the cache.
790             // Pick a victim at (pseudo-)random.
791             int k1 = primarySlot(key);
792             int k2 = secondarySlot(key);
793             var usePrimaryIndex = chooseVictim();
794             int victim = usePrimaryIndex ? k1 : k2;
795             int other = usePrimaryIndex ? k2 : k1;
796             setKeyAndObjectAt(victim, key, value);
797             if (getKey(theCache, other) == key) {
798                 setKeyAndObjectAt(other, key, value);
799             }
800         }
801 
802         private static void setKeyAndObjectAt(int n, Object key, Object value) {
803             var cache = scopedValueCache();
804             cache[n * 2] = key;
805             cache[n * 2 + 1] = value;
806         }
807 
808         private static void setKeyAndObjectAt(Object[] cache, int n, Object key, Object value) {
809             cache[n * 2] = key;
810             cache[n * 2 + 1] = value;
811         }
812 
813         private static Object getKey(Object[] objs, int n) {
814             return objs[n * 2];
815         }
816 
817         private static void setKey(Object[] objs, int n, Object key) {
818             objs[n * 2] = key;
819         }
820 
821         private static final JavaUtilConcurrentTLRAccess THREAD_LOCAL_RANDOM_ACCESS
822                 = SharedSecrets.getJavaUtilConcurrentTLRAccess();
823 
824         // Return either true or false, at pseudo-random, with a bias towards true.
825         // This chooses either the primary or secondary cache slot, but the
826         // primary slot is approximately twice as likely to be chosen as the
827         // secondary one.
828         private static boolean chooseVictim() {
829             int r = THREAD_LOCAL_RANDOM_ACCESS.nextSecondaryThreadLocalRandomSeed();
830             return (r & 15) >= 5;
831         }
832 
833         // Null a set of cache entries, indicated by the 1-bits given
834         static void invalidate(int toClearBits) {
835             toClearBits = (toClearBits >>> TABLE_SIZE) | (toClearBits & PRIMARY_MASK);
836             Object[] objects;
837             if ((objects = scopedValueCache()) != null) {
838                 for (int bits = toClearBits; bits != 0; ) {
839                     int index = Integer.numberOfTrailingZeros(bits);
840                     setKeyAndObjectAt(objects, index & SLOT_MASK, null, null);
841                     bits &= ~1 << index;
842                 }
843             }
844         }
845     }
846 }
--- EOF ---