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