1 /*
  2  * Copyright (c) 2020, 2023, 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.Callable;
 33 import java.util.concurrent.StructuredTaskScope;
 34 import java.util.concurrent.StructureViolationException;
 35 import java.util.function.Supplier;
 36 import jdk.internal.access.JavaUtilConcurrentTLRAccess;
 37 import jdk.internal.access.SharedSecrets;
 38 import jdk.internal.javac.PreviewFeature;
 39 import jdk.internal.vm.annotation.ForceInline;
 40 import jdk.internal.vm.annotation.Hidden;
 41 import jdk.internal.vm.ScopedValueContainer;
 42 import sun.security.action.GetPropertyAction;
 43 
 44 /**
 45  * A value that may be safely and efficiently shared to methods without using method
 46  * parameters.
 47  *
 48  * <p> In the Java programming language, data is usually passed to a method by means of a
 49  * method parameter. The data may need to be passed through a sequence of many methods to
 50  * get to the method that makes use of the data. Every method in the sequence of calls
 51  * needs to declare the parameter and every method has access to the data.
 52  * {@code ScopedValue} provides a means to pass data to a faraway method (typically a
 53  * <em>callback</em>) without using method parameters. In effect, a {@code ScopedValue}
 54  * is an <em>implicit method parameter</em>. It is "as if" every method in a sequence of
 55  * calls has an additional parameter. None of the methods declare the parameter and only
 56  * the methods that have access to the {@code ScopedValue} object can access its value
 57  * (the data). {@code ScopedValue} makes it possible to securely pass data from a
 58  * <em>caller</em> to a faraway <em>callee</em> through a sequence of intermediate methods
 59  * that do not declare a parameter for the data and have no access to the data.
 60  *
 61  * <p> The {@code ScopedValue} API works by executing a method with a {@code ScopedValue}
 62  * object <em>bound</em> to some value for the bounded period of execution of a method.
 63  * The method may invoke another method, which in turn may invoke another. The unfolding
 64  * execution of the methods define a <em>dynamic scope</em>. Code in these methods with
 65  * access to the {@code ScopedValue} object may read its value. The {@code ScopedValue}
 66  * object reverts to being <em>unbound</em> when the original method completes normally or
 67  * with an exception. The {@code ScopedValue} API supports executing a {@link Runnable#run()
 68  * Runnable.run}, {@link Callable#call() Callable.call}, or {@link Supplier#get() Supplier.get}
 69  * method with a {@code ScopedValue} bound to a value.
 70  *
 71  * <p> Consider the following example with a scoped value "{@code NAME}" bound to the value
 72  * "{@code duke}" for the execution of a {@code run} method. The {@code run} method, in
 73  * turn, invokes {@code doSomething}.
 74  * {@snippet lang=java :
 75  *     // @link substring="newInstance" target="#newInstance" :
 76  *     private static final ScopedValue<String> NAME = ScopedValue.newInstance();
 77  *
 78  *     // @link substring="runWhere" target="#runWhere" :
 79  *     ScopedValue.runWhere(NAME, "duke", () -> 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 runWhere} invokes a method that does not return a result.
 87  * The {@link #callWhere(ScopedValue, Object, Callable) callWhere} and {@link
 88  * #getWhere(ScopedValue, Object, Supplier) getWhere} can be used to invoke a method that
 89  * returns a result.
 90  * In addition, {@code ScopedValue} defines the {@link #where(ScopedValue, Object)} method
 91  * for cases where multiple mappings of ({@code ScopedValue} to value) are accumulated
 92  * in advance of calling a method with all {@code ScopedValue}s bound to their value.
 93  *
 94  * <h2>Bindings are per-thread</h2>
 95  *
 96  * A {@code ScopedValue} binding to a value is per-thread. Invoking {@code xxxWhere}
 97  * executes a method with a {@code ScopedValue} bound to a value for the current thread.
 98  * The {@link #get() get} method returns the value bound for the current thread.
 99  *
100  * <p> In the example, if code executed by one thread invokes this:
101  * {@snippet lang=java :
102  *     ScopedValue.runWhere(NAME, "duke1", () -> doSomething());
103  * }
104  * and code executed by another thread invokes:
105  * {@snippet lang=java :
106  *     ScopedValue.runWhere(NAME, "duke2", () -> doSomething());
107  * }
108  * then code in {@code doSomething} (or any method that it calls) invoking {@code NAME.get()}
109  * will read the value "{@code duke1}" or "{@code duke2}", depending on which thread is
110  * executing.
111  *
112  * <h2>Scoped values as capabilities</h2>
113  *
114  * A {@code ScopedValue} object should be treated as a <em>capability</em> or a key to
115  * access its value when the {@code ScopedValue} is bound. Secure usage depends on access
116  * control (see <cite>The Java Virtual Machine Specification</cite>, Section {@jvms 5.4.4})
117  * and taking care to not share the {@code ScopedValue} object. In many cases, a {@code
118  * ScopedValue} will be declared in a {@code final} and {@code static} field so that it
119  * is only accessible to code in a single class (or nest).
120  *
121  * <h2><a id="rebind">Rebinding</a></h2>
122  *
123  * The {@code ScopedValue} API allows a new binding to be established for <em>nested
124  * dynamic scopes</em>. This is known as <em>rebinding</em>. A {@code ScopedValue} that
125  * is bound to a value may be bound to a new value for the bounded execution of a new
126  * method. The unfolding execution of code executed by that method defines the nested
127  * dynamic scope. When the method completes, the value of the {@code ScopedValue} reverts
128  * to its previous value.
129  *
130  * <p> In the above example, suppose that code executed by {@code doSomething} binds
131  * {@code NAME} to a new value with:
132  * {@snippet lang=java :
133  *     ScopedValue.runWhere(NAME, "duchess", () -> doMore());
134  * }
135  * Code executed directly or indirectly by {@code doMore()} that invokes {@code
136  * NAME.get()} will read the value "{@code duchess}". When {@code doMore()} completes
137  * then the value of {@code NAME} reverts to "{@code duke}".
138  *
139  * <h2><a id="inheritance">Inheritance</a></h2>
140  *
141  * {@code ScopedValue} supports sharing across threads. This sharing is limited to
142  * structured cases where child threads are started and terminate within the bounded
143  * period of execution by a parent thread. When using a {@link StructuredTaskScope},
144  * scoped value bindings are <em>captured</em> when creating a {@code StructuredTaskScope}
145  * and inherited by all threads started in that task scope with the
146  * {@link StructuredTaskScope#fork(Callable) fork} method.
147  *
148  * <p> A {@code ScopedValue} that is shared across threads requires that the value be an
149  * immutable object or for all access to the value to be appropriately synchronized.
150  *
151  * <p> In the following example, the {@code ScopedValue} {@code NAME} is bound to the
152  * value "{@code duke}" for the execution of a runnable operation. The code in the {@code
153  * run} method creates a {@code StructuredTaskScope} that forks three tasks. Code executed
154  * directly or indirectly by these threads running {@code childTask1()}, {@code childTask2()},
155  * and {@code childTask3()} that invokes {@code NAME.get()} will read the value
156  * "{@code duke}".
157  *
158  * {@snippet lang=java :
159  *     private static final ScopedValue<String> NAME = ScopedValue.newInstance();
160 
161  *     ScopedValue.runWhere(NAME, "duke", () -> {
162  *         try (var scope = new StructuredTaskScope<String>()) {
163  *
164  *             scope.fork(() -> childTask1());
165  *             scope.fork(() -> childTask2());
166  *             scope.fork(() -> childTask3());
167  *
168  *             ...
169  *          }
170  *     });
171  * }
172  *
173  * <p> Unless otherwise specified, passing a {@code null} argument to a method in this
174  * class will cause a {@link NullPointerException} to be thrown.
175  *
176  * @apiNote
177  * A {@code ScopedValue} should be preferred over a {@link ThreadLocal} for cases where
178  * the goal is "one-way transmission" of data without using method parameters.  While a
179  * {@code ThreadLocal} can be used to pass data to a method without using method parameters,
180  * it does suffer from a number of issues:
181  * <ol>
182  *   <li> {@code ThreadLocal} does not prevent code in a faraway callee from {@linkplain
183  *   ThreadLocal#set(Object) setting} a new value.
184  *   <li> A {@code ThreadLocal} has an unbounded lifetime and thus continues to have a value
185  *   after a method completes, unless explicitly {@linkplain ThreadLocal#remove() removed}.
186  *   <li> {@linkplain InheritableThreadLocal Inheritance} is expensive - the map of
187  *   thread-locals to values must be copied when creating each child thread.
188  * </ol>
189  *
190  * @implNote
191  * Scoped values are designed to be used in fairly small
192  * numbers. {@link #get} initially performs a search through enclosing
193  * scopes to find a scoped value's innermost binding. It
194  * then caches the result of the search in a small thread-local
195  * cache. Subsequent invocations of {@link #get} for that scoped value
196  * will almost always be very fast. However, if a program has many
197  * scoped values that it uses cyclically, the cache hit rate
198  * will be low and performance will be poor. This design allows
199  * scoped-value inheritance by {@link StructuredTaskScope} threads to
200  * be very fast: in essence, no more than copying a pointer, and
201  * leaving a scoped-value binding also requires little more than
202  * updating a pointer.
203  *
204  * <p>Because the scoped-value per-thread cache is small, clients
205  * should minimize the number of bound scoped values in use. For
206  * example, if it is necessary to pass a number of values in this way,
207  * it makes sense to create a record class to hold those values, and
208  * then bind a single {@code ScopedValue} to an instance of that record.
209  *
210  * <p>For this release, the reference implementation
211  * provides some system properties to tune the performance of scoped
212  * values.
213  *
214  * <p>The system property {@code java.lang.ScopedValue.cacheSize}
215  * controls the size of the (per-thread) scoped-value cache. This cache is crucial
216  * for the performance of scoped values. If it is too small,
217  * the runtime library will repeatedly need to scan for each
218  * {@link #get}. If it is too large, memory will be unnecessarily
219  * consumed. The default scoped-value cache size is 16 entries. It may
220  * be varied from 2 to 16 entries in size. {@code ScopedValue.cacheSize}
221  * must be an integer power of 2.
222  *
223  * <p>For example, you could use {@code -Djava.lang.ScopedValue.cacheSize=8}.
224  *
225  * <p>The other system property is {@code jdk.preserveScopedValueCache}.
226  * This property determines whether the per-thread scoped-value
227  * cache is preserved when a virtual thread is blocked. By default
228  * this property is set to {@code true}, meaning that every virtual
229  * thread preserves its scoped-value cache when blocked. Like {@code
230  * ScopedValue.cacheSize}, this is a space versus speed trade-off: in
231  * situations where many virtual threads are blocked most of the time,
232  * setting this property to {@code false} might result in a useful
233  * memory saving, but each virtual thread's scoped-value cache would
234  * have to be regenerated after a blocking operation.
235  *
236  * @param <T> the type of the value
237  * @since 21
238  */
239 @PreviewFeature(feature = PreviewFeature.Feature.SCOPED_VALUES)
240 public final class ScopedValue<T> {
241     private final int hash;
242 
243     @Override
244     public int hashCode() { return hash; }
245 
246     /**
247      * An immutable map from {@code ScopedValue} to values.
248      *
249      * <p> Unless otherwise specified, passing a {@code null} argument to a constructor
250      * or method in this class will cause a {@link NullPointerException} to be thrown.
251      */
252     static final class Snapshot {
253         final Snapshot prev;
254         final Carrier bindings;
255         final int bitmask;
256 
257         private static final Object NIL = new Object();
258 
259         static final Snapshot EMPTY_SNAPSHOT = new Snapshot();
260 
261         Snapshot(Carrier bindings, Snapshot prev) {
262             this.prev = prev;
263             this.bindings = bindings;
264             this.bitmask = bindings.bitmask | prev.bitmask;
265         }
266 
267         protected Snapshot() {
268             this.prev = null;
269             this.bindings = null;
270             this.bitmask = 0;
271         }
272 
273         Object find(ScopedValue<?> key) {
274             int bits = key.bitmask();
275             for (Snapshot snapshot = this;
276                  containsAll(snapshot.bitmask, bits);
277                  snapshot = snapshot.prev) {
278                 for (Carrier carrier = snapshot.bindings;
279                      carrier != null && containsAll(carrier.bitmask, bits);
280                      carrier = carrier.prev) {
281                     if (carrier.getKey() == key) {
282                         Object value = carrier.get();
283                         return value;
284                     }
285                 }
286             }
287             return NIL;
288         }
289     }
290 
291     /**
292      * A mapping of scoped values, as <em>keys</em>, to values.
293      *
294      * <p> A {@code Carrier} is used to accumulate mappings so that an operation (a
295      * {@link Runnable} or {@link Callable}) can be executed with all scoped values in the
296      * mapping bound to values. The following example runs an operation with {@code k1}
297      * bound (or rebound) to {@code v1}, and {@code k2} bound (or rebound) to {@code v2}.
298      * {@snippet lang=java :
299      *     // @link substring="where" target="#where(ScopedValue, Object)" :
300      *     ScopedValue.where(k1, v1).where(k2, v2).run(() -> ... );
301      * }
302      *
303      * <p> A {@code Carrier} is immutable and thread-safe. The {@link
304      * #where(ScopedValue, Object) where} method returns a new {@code Carrier} object,
305      * it does not mutate an existing mapping.
306      *
307      * <p> Unless otherwise specified, passing a {@code null} argument to a method in
308      * this class will cause a {@link NullPointerException} to be thrown.
309      *
310      * @since 21
311      */
312     @PreviewFeature(feature = PreviewFeature.Feature.SCOPED_VALUES)
313     public static final class Carrier {
314         // Bit masks: a 1 in postion n indicates that this set of bound values
315         // hits that slot in the cache.
316         final int bitmask;
317         final ScopedValue<?> key;
318         final Object value;
319         final Carrier prev;
320 
321         Carrier(ScopedValue<?> key, Object value, Carrier prev) {
322             this.key = key;
323             this.value = value;
324             this.prev = prev;
325             int bits = key.bitmask();
326             if (prev != null) {
327                 bits |= prev.bitmask;
328             }
329             this.bitmask = bits;
330         }
331 
332         /**
333          * Add a binding to this map, returning a new Carrier instance.
334          */
335         private static <T> Carrier where(ScopedValue<T> key, T value, Carrier prev) {
336             return new Carrier(key, value, prev);
337         }
338 
339         /**
340          * Returns a new {@code Carrier} with the mappings from this carrier plus a
341          * new mapping from {@code key} to {@code value}. If this carrier already has a
342          * mapping for the scoped value {@code key} then it will map to the new
343          * {@code value}. The current carrier is immutable, so it is not changed by this
344          * method.
345          *
346          * @param key the {@code ScopedValue} key
347          * @param value the value, can be {@code null}
348          * @param <T> the type of the value
349          * @return a new {@code Carrier} with the mappings from this carrier plus the new mapping
350          */
351         public <T> Carrier where(ScopedValue<T> key, T value) {
352             return where(key, value, this);
353         }
354 
355         /*
356          * Return a new set consisting of a single binding.
357          */
358         static <T> Carrier of(ScopedValue<T> key, T value) {
359             return where(key, value, null);
360         }
361 
362         Object get() {
363             return value;
364         }
365 
366         ScopedValue<?> getKey() {
367             return key;
368         }
369 
370         /**
371          * Returns the value of a {@link ScopedValue} in this mapping.
372          *
373          * @param key the {@code ScopedValue} key
374          * @param <T> the type of the value
375          * @return the value
376          * @throws NoSuchElementException if the key is not present in this mapping
377          */
378         @SuppressWarnings("unchecked")
379         public <T> T get(ScopedValue<T> key) {
380             var bits = key.bitmask();
381             for (Carrier carrier = this;
382                  carrier != null && containsAll(carrier.bitmask, bits);
383                  carrier = carrier.prev) {
384                 if (carrier.getKey() == key) {
385                     Object value = carrier.get();
386                     return (T)value;
387                 }
388             }
389             throw new NoSuchElementException();
390         }
391 
392         /**
393          * Calls a value-returning operation with each scoped value in this mapping bound
394          * to its value in the current thread.
395          * When the operation completes (normally or with an exception), each scoped value
396          * in the mapping will revert to being unbound, or revert to its previous value
397          * when previously bound, in the current thread.
398          *
399          * <p> Scoped values are intended to be used in a <em>structured manner</em>.
400          * If {@code op} creates a {@link StructuredTaskScope} but does not {@linkplain
401          * StructuredTaskScope#close() close} it, then exiting {@code op} causes the
402          * underlying construct of each {@code StructuredTaskScope} created in the
403          * dynamic scope to be closed. This may require blocking until all child threads
404          * have completed their sub-tasks. The closing is done in the reverse order that
405          * they were created. Once closed, {@link StructureViolationException} is thrown.
406          *
407          * @param op the operation to run
408          * @param <R> the type of the result of the operation
409          * @return the result
410          * @throws Exception if {@code op} completes with an exception
411          * @see ScopedValue#callWhere(ScopedValue, Object, Callable)
412          */
413         public <R> R call(Callable<? extends R> op) throws Exception {
414             Objects.requireNonNull(op);
415             Cache.invalidate(bitmask);
416             var prevSnapshot = scopedValueBindings();
417             var newSnapshot = new Snapshot(this, prevSnapshot);
418             return runWith(newSnapshot, op);
419         }
420 
421         /**
422          * Invokes a supplier of results with each scoped value in this mapping bound
423          * to its value in the current thread.
424          * When the operation completes (normally or with an exception), each scoped value
425          * in the mapping will revert to being unbound, or revert to its previous value
426          * when previously bound, in the current thread.
427          *
428          * <p> Scoped values are intended to be used in a <em>structured manner</em>.
429          * If {@code op} creates a {@link StructuredTaskScope} but does not {@linkplain
430          * StructuredTaskScope#close() close} it, then exiting {@code op} causes the
431          * underlying construct of each {@code StructuredTaskScope} created in the
432          * dynamic scope to be closed. This may require blocking until all child threads
433          * have completed their sub-tasks. The closing is done in the reverse order that
434          * they were created. Once closed, {@link StructureViolationException} is thrown.
435          *
436          * @param op the operation to run
437          * @param <R> the type of the result of the operation
438          * @return the result
439          * @see ScopedValue#getWhere(ScopedValue, Object, Supplier)
440          */
441         public <R> R get(Supplier<? extends R> op) {
442             Objects.requireNonNull(op);
443             Cache.invalidate(bitmask);
444             var prevSnapshot = scopedValueBindings();
445             var newSnapshot = new Snapshot(this, prevSnapshot);
446             return runWith(newSnapshot, new CallableAdapter<R>(op));
447         }
448 
449         // A lightweight adapter from Supplier to Callable. This is
450         // used here to create the Callable which is passed to
451         // Carrier#call() in this thread because it needs neither
452         // runtime bytecode generation nor any release fencing.
453         private static final class CallableAdapter<V> implements Callable<V> {
454             private /*non-final*/ Supplier<? extends V> s;
455             CallableAdapter(Supplier<? extends V> s) {
456                 this.s = s;
457             }
458             public V call() {
459                 return s.get();
460             }
461         }
462 
463         /**
464          * Execute the action with a set of ScopedValue bindings.
465          *
466          * The VM recognizes this method as special, so any changes to the
467          * name or signature require corresponding changes in
468          * JVM_FindScopedValueBindings().
469          */
470         @Hidden
471         @ForceInline
472         private <R> R runWith(Snapshot newSnapshot, Callable<R> op) {
473             try {
474                 Thread.setScopedValueBindings(newSnapshot);
475                 Thread.ensureMaterializedForStackWalk(newSnapshot);
476                 return ScopedValueContainer.call(op);
477             } finally {
478                 Reference.reachabilityFence(newSnapshot);
479                 Thread.setScopedValueBindings(newSnapshot.prev);
480                 Cache.invalidate(bitmask);
481             }
482         }
483 
484         /**
485          * Runs an operation with each scoped value in this mapping bound to its value
486          * in the current thread.
487          * When the operation completes (normally or with an exception), each scoped value
488          * in the mapping will revert to being unbound, or revert to its previous value
489          * when previously bound, in the current thread.
490          *
491          * <p> Scoped values are intended to be used in a <em>structured manner</em>.
492          * If {@code op} creates a {@link StructuredTaskScope} but does not {@linkplain
493          * StructuredTaskScope#close() close} it, then exiting {@code op} causes the
494          * underlying construct of each {@code StructuredTaskScope} created in the
495          * dynamic scope to be closed. This may require blocking until all child threads
496          * have completed their sub-tasks. The closing is done in the reverse order that
497          * they were created. Once closed, {@link StructureViolationException} is thrown.
498          *
499          * @param op the operation to run
500          * @see ScopedValue#runWhere(ScopedValue, Object, Runnable)
501          */
502         public void run(Runnable op) {
503             Objects.requireNonNull(op);
504             Cache.invalidate(bitmask);
505             var prevSnapshot = scopedValueBindings();
506             var newSnapshot = new Snapshot(this, prevSnapshot);
507             runWith(newSnapshot, op);
508         }
509 
510         /**
511          * Execute the action with a set of {@code ScopedValue} bindings.
512          *
513          * The VM recognizes this method as special, so any changes to the
514          * name or signature require corresponding changes in
515          * JVM_FindScopedValueBindings().
516          */
517         @Hidden
518         @ForceInline
519         private void runWith(Snapshot newSnapshot, Runnable op) {
520             try {
521                 Thread.setScopedValueBindings(newSnapshot);
522                 Thread.ensureMaterializedForStackWalk(newSnapshot);
523                 ScopedValueContainer.run(op);
524             } finally {
525                 Reference.reachabilityFence(newSnapshot);
526                 Thread.setScopedValueBindings(newSnapshot.prev);
527                 Cache.invalidate(bitmask);
528             }
529         }
530     }
531 
532     /**
533      * Creates a new {@code Carrier} with a single mapping of a {@code ScopedValue}
534      * <em>key</em> to a value. The {@code Carrier} can be used to accumlate mappings so
535      * that an operation can be executed with all scoped values in the mapping bound to
536      * values. The following example runs an operation with {@code k1} bound (or rebound)
537      * to {@code v1}, and {@code k2} bound (or rebound) to {@code v2}.
538      * {@snippet lang=java :
539      *     // @link substring="run" target="Carrier#run(Runnable)" :
540      *     ScopedValue.where(k1, v1).where(k2, v2).run(() -> ... );
541      * }
542      *
543      * @param key the {@code ScopedValue} key
544      * @param value the value, can be {@code null}
545      * @param <T> the type of the value
546      * @return a new {@code Carrier} with a single mapping
547      */
548     public static <T> Carrier where(ScopedValue<T> key, T value) {
549         return Carrier.of(key, value);
550     }
551 
552     /**
553      * Calls a value-returning operation with a {@code ScopedValue} bound to a value
554      * in the current thread. When the operation completes (normally or with an
555      * exception), the {@code ScopedValue} will revert to being unbound, or revert to
556      * its previous value when previously bound, in the current thread.
557      *
558      * <p> Scoped values are intended to be used in a <em>structured manner</em>.
559      * If {@code op} creates a {@link StructuredTaskScope} but does not {@linkplain
560      * StructuredTaskScope#close() close} it, then exiting {@code op} causes the
561      * underlying construct of each {@code StructuredTaskScope} created in the
562      * dynamic scope to be closed. This may require blocking until all child threads
563      * have completed their sub-tasks. The closing is done in the reverse order that
564      * they were created. Once closed, {@link StructureViolationException} is thrown.
565      *
566      * @implNote
567      * This method is implemented to be equivalent to:
568      * {@snippet lang=java :
569      *     // @link substring="call" target="Carrier#call(Callable)" :
570      *     ScopedValue.where(key, value).call(op);
571      * }
572      *
573      * @param key the {@code ScopedValue} key
574      * @param value the value, can be {@code null}
575      * @param <T> the type of the value
576      * @param <R> the result type
577      * @param op the operation to call
578      * @return the result
579      * @throws Exception if the operation completes with an exception
580      */
581     public static <T, R> R callWhere(ScopedValue<T> key,
582                                      T value,
583                                      Callable<? extends R> op) throws Exception {
584         return where(key, value).call(op);
585     }
586 
587     /**
588      * Invokes a supplier of results with a {@code ScopedValue} bound to a value
589      * in the current thread. When the operation completes (normally or with an
590      * exception), the {@code ScopedValue} will revert to being unbound, or revert to
591      * its previous value when previously bound, in the current thread.
592      *
593      * <p> Scoped values are intended to be used in a <em>structured manner</em>.
594      * If {@code op} creates a {@link StructuredTaskScope} but does not {@linkplain
595      * StructuredTaskScope#close() close} it, then exiting {@code op} causes the
596      * underlying construct of each {@code StructuredTaskScope} created in the
597      * dynamic scope to be closed. This may require blocking until all child threads
598      * have completed their sub-tasks. The closing is done in the reverse order that
599      * they were created. Once closed, {@link StructureViolationException} is thrown.
600      *
601      * @implNote
602      * This method is implemented to be equivalent to:
603      * {@snippet lang=java :
604      *     // @link substring="get" target="Carrier#get(Supplier)" :
605      *     ScopedValue.where(key, value).get(op);
606      * }
607      *
608      * @param key the {@code ScopedValue} key
609      * @param value the value, can be {@code null}
610      * @param <T> the type of the value
611      * @param <R> the result type
612      * @param op the operation to call
613      * @return the result
614      */
615     public static <T, R> R getWhere(ScopedValue<T> key,
616                                     T value,
617                                     Supplier<? extends R> op) {
618         return where(key, value).get(op);
619     }
620 
621     /**
622      * Run an operation with a {@code ScopedValue} bound to a value in the current
623      * thread. When the operation completes (normally or with an exception), the
624      * {@code ScopedValue} will revert to being unbound, or revert to its previous value
625      * when previously bound, in the current thread.
626      *
627      * <p> Scoped values are intended to be used in a <em>structured manner</em>.
628      * If {@code op} creates a {@link StructuredTaskScope} but does not {@linkplain
629      * StructuredTaskScope#close() close} it, then exiting {@code op} causes the
630      * underlying construct of each {@code StructuredTaskScope} created in the
631      * dynamic scope to be closed. This may require blocking until all child threads
632      * have completed their sub-tasks. The closing is done in the reverse order that
633      * they were created. Once closed, {@link StructureViolationException} is thrown.
634      *
635      * @implNote
636      * This method is implemented to be equivalent to:
637      * {@snippet lang=java :
638      *     // @link substring="run" target="Carrier#run(Runnable)" :
639      *     ScopedValue.where(key, value).run(op);
640      * }
641      *
642      * @param key the {@code ScopedValue} key
643      * @param value the value, can be {@code null}
644      * @param <T> the type of the value
645      * @param op the operation to call
646      */
647     public static <T> void runWhere(ScopedValue<T> key, T value, Runnable op) {
648         where(key, value).run(op);
649     }
650 
651     private ScopedValue() {
652         this.hash = generateKey();
653     }
654 
655     /**
656      * Creates a scoped value that is initially unbound for all threads.
657      *
658      * @param <T> the type of the value
659      * @return a new {@code ScopedValue}
660      */
661     public static <T> ScopedValue<T> newInstance() {
662         return new ScopedValue<T>();
663     }
664 
665     /**
666      * {@return the value of the scoped value if bound in the current thread}
667      *
668      * @throws NoSuchElementException if the scoped value is not bound
669      */
670     @ForceInline
671     @SuppressWarnings("unchecked")
672     public T get() {
673         Object[] objects;
674         if ((objects = scopedValueCache()) != null) {
675             // This code should perhaps be in class Cache. We do it
676             // here because the generated code is small and fast and
677             // we really want it to be inlined in the caller.
678             int n = (hash & Cache.SLOT_MASK) * 2;
679             if (objects[n] == this) {
680                 return (T)objects[n + 1];
681             }
682             n = ((hash >>> Cache.INDEX_BITS) & Cache.SLOT_MASK) * 2;
683             if (objects[n] == this) {
684                 return (T)objects[n + 1];
685             }
686         }
687         return slowGet();
688     }
689 
690     @SuppressWarnings("unchecked")
691     private T slowGet() {
692         var value = findBinding();
693         if (value == Snapshot.NIL) {
694             throw new NoSuchElementException();
695         }
696         Cache.put(this, value);
697         return (T)value;
698     }
699 
700     /**
701      * {@return {@code true} if this scoped value is bound in the current thread}
702      */
703     public boolean isBound() {
704         Object[] objects = scopedValueCache();
705         if (objects != null) {
706             int n = (hash & Cache.SLOT_MASK) * 2;
707             if (objects[n] == this) {
708                 return true;
709             }
710             n = ((hash >>> Cache.INDEX_BITS) & Cache.SLOT_MASK) * 2;
711             if (objects[n] == this) {
712                 return true;
713             }
714         }
715         var value = findBinding();
716         boolean result = (value != Snapshot.NIL);
717         if (result)  Cache.put(this, value);
718         return result;
719     }
720 
721     /**
722      * Return the value of the scoped value or NIL if not bound.
723      */
724     private Object findBinding() {
725         Object value = scopedValueBindings().find(this);
726         return value;
727     }
728 
729     /**
730      * Returns the value of this scoped value if bound in the current thread, otherwise
731      * returns {@code other}.
732      *
733      * @param other the value to return if not bound, can be {@code null}
734      * @return the value of the scoped value if bound, otherwise {@code other}
735      */
736     public T orElse(T other) {
737         Object obj = findBinding();
738         if (obj != Snapshot.NIL) {
739             @SuppressWarnings("unchecked")
740             T value = (T) obj;
741             return value;
742         } else {
743             return other;
744         }
745     }
746 
747     /**
748      * Returns the value of this scoped value if bound in the current thread, otherwise
749      * throws an exception produced by the exception supplying function.
750      *
751      * @param <X> the type of the exception that may be thrown
752      * @param exceptionSupplier the supplying function that produces the exception to throw
753      * @return the value of the scoped value if bound in the current thread
754      * @throws X if the scoped value is not bound in the current thread
755      */
756     public <X extends Throwable> T orElseThrow(Supplier<? extends X> exceptionSupplier) throws X {
757         Objects.requireNonNull(exceptionSupplier);
758         Object obj = findBinding();
759         if (obj != Snapshot.NIL) {
760             @SuppressWarnings("unchecked")
761             T value = (T) obj;
762             return value;
763         } else {
764             throw exceptionSupplier.get();
765         }
766     }
767 
768     private static Object[] scopedValueCache() {
769         return Thread.scopedValueCache();
770     }
771 
772     private static void setScopedValueCache(Object[] cache) {
773         Thread.setScopedValueCache(cache);
774     }
775 
776     // Special value to indicate this is a newly-created Thread
777     // Note that his must match the declaration in j.l.Thread.
778     private static final Object NEW_THREAD_BINDINGS = Thread.class;
779 
780     private static Snapshot scopedValueBindings() {
781         // Bindings can be in one of four states:
782         //
783         // 1: class Thread: this is a new Thread instance, and no
784         // scoped values have ever been bound in this Thread.
785         // 2: EmptySnapshot.SINGLETON: This is effectively an empty binding.
786         // 3: A Snapshot instance: this contains one or more scoped value
787         // bindings.
788         // 4: null: there may be some bindings in this Thread, but we don't know
789         // where they are. We must invoke Thread.findScopedValueBindings() to walk
790         // the stack to find them.
791 
792         Object bindings = Thread.scopedValueBindings();
793         if (bindings == NEW_THREAD_BINDINGS) {
794             // This must be a new thread
795            return Snapshot.EMPTY_SNAPSHOT;
796         }
797         if (bindings == null) {
798             // Search the stack
799             bindings = Thread.findScopedValueBindings();
800             if (bindings == null) {
801                 // Nothing on the stack.
802                 bindings = Snapshot.EMPTY_SNAPSHOT;
803             }
804         }
805         assert (bindings != null);
806         Thread.setScopedValueBindings(bindings);
807         return (Snapshot) bindings;
808     }
809 
810     private static int nextKey = 0xf0f0_f0f0;
811 
812     // A Marsaglia xor-shift generator used to generate hashes. This one has full period, so
813     // it generates 2**32 - 1 hashes before it repeats. We're going to use the lowest n bits
814     // and the next n bits as cache indexes, so we make sure that those indexes map
815     // to different slots in the cache.
816     private static synchronized int generateKey() {
817         int x = nextKey;
818         do {
819             x ^= x >>> 12;
820             x ^= x << 9;
821             x ^= x >>> 23;
822         } while (Cache.primarySlot(x) == Cache.secondarySlot(x));
823         return (nextKey = x);
824     }
825 
826     /**
827      * Return a bit mask that may be used to determine if this ScopedValue is
828      * bound in the current context. Each Carrier holds a bit mask which is
829      * the OR of all the bit masks of the bound ScopedValues.
830      * @return the bitmask
831      */
832     int bitmask() {
833         return (1 << Cache.primaryIndex(this)) | (1 << (Cache.secondaryIndex(this) + Cache.TABLE_SIZE));
834     }
835 
836     // Return true iff bitmask, considered as a set of bits, contains all
837     // of the bits in targetBits.
838     static boolean containsAll(int bitmask, int targetBits) {
839         return (bitmask & targetBits) == targetBits;
840     }
841 
842     // A small fixed-size key-value cache. When a scoped value's get() method
843     // is invoked, we record the result of the lookup in this per-thread cache
844     // for fast access in future.
845     private static final class Cache {
846         static final int INDEX_BITS = 4;  // Must be a power of 2
847         static final int TABLE_SIZE = 1 << INDEX_BITS;
848         static final int TABLE_MASK = TABLE_SIZE - 1;
849         static final int PRIMARY_MASK = (1 << TABLE_SIZE) - 1;
850 
851         // The number of elements in the cache array, and a bit mask used to
852         // select elements from it.
853         private static final int CACHE_TABLE_SIZE, SLOT_MASK;
854         // The largest cache we allow. Must be a power of 2 and greater than
855         // or equal to 2.
856         private static final int MAX_CACHE_SIZE = 16;
857 
858         static {
859             final String propertyName = "java.lang.ScopedValue.cacheSize";
860             var sizeString = GetPropertyAction.privilegedGetProperty(propertyName, "16");
861             var cacheSize = Integer.valueOf(sizeString);
862             if (cacheSize < 2 || cacheSize > MAX_CACHE_SIZE) {
863                 cacheSize = MAX_CACHE_SIZE;
864                 System.err.println(propertyName + " is out of range: is " + sizeString);
865             }
866             if ((cacheSize & (cacheSize - 1)) != 0) {  // a power of 2
867                 cacheSize = MAX_CACHE_SIZE;
868                 System.err.println(propertyName + " must be an integer power of 2: is " + sizeString);
869             }
870             CACHE_TABLE_SIZE = cacheSize;
871             SLOT_MASK = cacheSize - 1;
872         }
873 
874         static int primaryIndex(ScopedValue<?> key) {
875             return key.hash & TABLE_MASK;
876         }
877 
878         static int secondaryIndex(ScopedValue<?> key) {
879             return (key.hash >> INDEX_BITS) & TABLE_MASK;
880         }
881 
882         private static int primarySlot(ScopedValue<?> key) {
883             return key.hashCode() & SLOT_MASK;
884         }
885 
886         private static int secondarySlot(ScopedValue<?> key) {
887             return (key.hash >> INDEX_BITS) & SLOT_MASK;
888         }
889 
890         static int primarySlot(int hash) {
891             return hash & SLOT_MASK;
892         }
893 
894         static int secondarySlot(int hash) {
895             return (hash >> INDEX_BITS) & SLOT_MASK;
896         }
897 
898         static void put(ScopedValue<?> key, Object value) {
899             Object[] theCache = scopedValueCache();
900             if (theCache == null) {
901                 theCache = new Object[CACHE_TABLE_SIZE * 2];
902                 setScopedValueCache(theCache);
903             }
904             // Update the cache to replace one entry with the value we just looked up.
905             // Each value can be in one of two possible places in the cache.
906             // Pick a victim at (pseudo-)random.
907             int k1 = primarySlot(key);
908             int k2 = secondarySlot(key);
909             var usePrimaryIndex = chooseVictim();
910             int victim = usePrimaryIndex ? k1 : k2;
911             int other = usePrimaryIndex ? k2 : k1;
912             setKeyAndObjectAt(victim, key, value);
913             if (getKey(theCache, other) == key) {
914                 setKeyAndObjectAt(other, key, value);
915             }
916         }
917 
918         private static void setKeyAndObjectAt(int n, Object key, Object value) {
919             var cache = scopedValueCache();
920             cache[n * 2] = key;
921             cache[n * 2 + 1] = value;
922         }
923 
924         private static void setKeyAndObjectAt(Object[] cache, int n, Object key, Object value) {
925             cache[n * 2] = key;
926             cache[n * 2 + 1] = value;
927         }
928 
929         private static Object getKey(Object[] objs, int n) {
930             return objs[n * 2];
931         }
932 
933         private static void setKey(Object[] objs, int n, Object key) {
934             objs[n * 2] = key;
935         }
936 
937         private static final JavaUtilConcurrentTLRAccess THREAD_LOCAL_RANDOM_ACCESS
938                 = SharedSecrets.getJavaUtilConcurrentTLRAccess();
939 
940         // Return either true or false, at pseudo-random, with a bias towards true.
941         // This chooses either the primary or secondary cache slot, but the
942         // primary slot is approximately twice as likely to be chosen as the
943         // secondary one.
944         private static boolean chooseVictim() {
945             int r = THREAD_LOCAL_RANDOM_ACCESS.nextSecondaryThreadLocalRandomSeed();
946             return (r & 15) >= 5;
947         }
948 
949         // Null a set of cache entries, indicated by the 1-bits given
950         static void invalidate(int toClearBits) {
951             toClearBits = (toClearBits >>> TABLE_SIZE) | (toClearBits & PRIMARY_MASK);
952             Object[] objects;
953             if ((objects = scopedValueCache()) != null) {
954                 for (int bits = toClearBits; bits != 0; ) {
955                     int index = Integer.numberOfTrailingZeros(bits);
956                     setKeyAndObjectAt(objects, index & SLOT_MASK, null, null);
957                     bits &= ~1 << index;
958                 }
959             }
960         }
961     }
962 }