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