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 }