1 /* 2 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.lang; 27 import java.lang.ref.*; 28 import java.util.Objects; 29 import java.util.concurrent.atomic.AtomicInteger; 30 import java.util.function.Supplier; 31 import jdk.internal.misc.JdkThreadLocal; 32 33 /** 34 * This class provides thread-local variables. These variables differ from 35 * their normal counterparts in that each thread that accesses one (via its 36 * {@code get} or {@code set} method) has its own, independently initialized 37 * copy of the variable. {@code ThreadLocal} instances are typically private 38 * static fields in classes that wish to associate state with a thread (e.g., 39 * a user ID or Transaction ID). 40 * 41 * <p>For example, the class below generates unique identifiers local to each 42 * thread. 43 * A thread's id is assigned the first time it invokes {@code ThreadId.get()} 44 * and remains unchanged on subsequent calls. 45 * <pre> 46 * import java.util.concurrent.atomic.AtomicInteger; 47 * 48 * public class ThreadId { 49 * // Atomic integer containing the next thread ID to be assigned 50 * private static final AtomicInteger nextId = new AtomicInteger(0); 51 * 52 * // Thread local variable containing each thread's ID 53 * private static final ThreadLocal<Integer> threadId = 54 * new ThreadLocal<Integer>() { 55 * @Override protected Integer initialValue() { 56 * return nextId.getAndIncrement(); 57 * } 58 * }; 59 * 60 * // Returns the current thread's unique ID, assigning it if necessary 61 * public static int get() { 62 * return threadId.get(); 63 * } 64 * } 65 * </pre> 66 * <p>Each thread holds an implicit reference to its copy of a thread-local 67 * variable as long as the thread is alive and the {@code ThreadLocal} 68 * instance is accessible; after a thread goes away, all of its copies of 69 * thread-local instances are subject to garbage collection (unless other 70 * references to these copies exist). 71 * 72 * @author Josh Bloch and Doug Lea 73 * @since 1.2 74 */ 75 public class ThreadLocal<T> { 76 /** 77 * ThreadLocals rely on per-thread linear-probe hash maps attached 78 * to each thread (Thread.threadLocals and 79 * inheritableThreadLocals). The ThreadLocal objects act as keys, 80 * searched via threadLocalHashCode. This is a custom hash code 81 * (useful only within ThreadLocalMaps) that eliminates collisions 82 * in the common case where consecutively constructed ThreadLocals 83 * are used by the same threads, while remaining well-behaved in 84 * less common cases. 85 */ 86 private final int threadLocalHashCode = nextHashCode(); 87 88 static void callThreadTerminated(ThreadLocalMap map) { 89 if (map == null) { 90 return; 91 } 92 93 // We expect to have a very small number of hooks and 94 // potentially a lot of entries in the map. So, it should be 95 // faster to iterate over the hooks and do look-ups on the map 96 // instead of iterating over the map. 97 JdkThreadLocal.forEach(tl -> { 98 final ThreadLocalMap.Entry entry = map.getEntry(tl); 99 if (entry != null) { 100 tl.callThreadTerminated(entry.value); 101 } 102 }); 103 } 104 105 /** 106 * The next hash code to be given out. Updated atomically. Starts at 107 * zero. 108 */ 109 private static AtomicInteger nextHashCode = 110 new AtomicInteger(); 111 112 /** 113 * The difference between successively generated hash codes - turns 114 * implicit sequential thread-local IDs into near-optimally spread 115 * multiplicative hash values for power-of-two-sized tables. 116 */ 117 private static final int HASH_INCREMENT = 0x61c88647; 118 119 /** 120 * Returns the next hash code. 121 */ 122 private static int nextHashCode() { 123 return nextHashCode.getAndAdd(HASH_INCREMENT); 124 } 125 126 /** 127 * Returns the current thread's "initial value" for this 128 * thread-local variable. This method will be invoked the first 129 * time a thread accesses the variable with the {@link #get} 130 * method, unless the thread previously invoked the {@link #set} 131 * method, in which case the {@code initialValue} method will not 132 * be invoked for the thread. Normally, this method is invoked at 133 * most once per thread, but it may be invoked again in case of 134 * subsequent invocations of {@link #remove} followed by {@link #get}. 135 * 136 * <p>This implementation simply returns {@code null}; if the 137 * programmer desires thread-local variables to have an initial 138 * value other than {@code null}, {@code ThreadLocal} must be 139 * subclassed, and this method overridden. Typically, an 140 * anonymous inner class will be used. 141 * 142 * @return the initial value for this thread-local 143 */ 144 protected T initialValue() { 145 return null; 146 } 147 148 /** 149 * Creates a thread local variable. The initial value of the variable is 150 * determined by invoking the {@code get} method on the {@code Supplier}. 151 * 152 * @param <S> the type of the thread local's value 153 * @param supplier the supplier to be used to determine the initial value 154 * @return a new thread local variable 155 * @throws NullPointerException if the specified supplier is null 156 * @since 1.8 157 */ 158 public static <S> ThreadLocal<S> withInitial(Supplier<? extends S> supplier) { 159 return new SuppliedThreadLocal<>(supplier); 160 } 161 162 /** 163 * Creates a thread local variable. 164 * @see #withInitial(java.util.function.Supplier) 165 */ 166 public ThreadLocal() { 167 } 168 169 /** 170 * Returns the value in the current thread's copy of this 171 * thread-local variable. If the variable has no value for the 172 * current thread, it is first initialized to the value returned 173 * by an invocation of the {@link #initialValue} method. 174 * 175 * @return the current thread's value of this thread-local 176 */ 177 public T get() { 178 Thread t = Thread.currentThread(); 179 ThreadLocalMap map = getMap(t); 180 if (map != null) { 181 ThreadLocalMap.Entry e = map.getEntry(this); 182 if (e != null) { 183 @SuppressWarnings("unchecked") 184 T result = (T)e.value; 185 return result; 186 } 187 } 188 return setInitialValue(); 189 } 190 191 /** 192 * Variant of set() to establish initialValue. Used instead 193 * of set() in case user has overridden the set() method. 194 * 195 * @return the initial value 196 */ 197 private T setInitialValue() { 198 T value = initialValue(); 199 Thread t = Thread.currentThread(); 200 ThreadLocalMap map = getMap(t); 201 if (map != null) 202 map.set(this, value); 203 else 204 createMap(t, value); 205 return value; 206 } 207 208 /** 209 * Sets the current thread's copy of this thread-local variable 210 * to the specified value. Most subclasses will have no need to 211 * override this method, relying solely on the {@link #initialValue} 212 * method to set the values of thread-locals. 213 * 214 * @param value the value to be stored in the current thread's copy of 215 * this thread-local. 216 */ 217 public void set(T value) { 218 Thread t = Thread.currentThread(); 219 ThreadLocalMap map = getMap(t); 220 if (map != null) 221 map.set(this, value); 222 else 223 createMap(t, value); 224 } 225 226 /** 227 * Removes the current thread's value for this thread-local 228 * variable. If this thread-local variable is subsequently 229 * {@linkplain #get read} by the current thread, its value will be 230 * reinitialized by invoking its {@link #initialValue} method, 231 * unless its value is {@linkplain #set set} by the current thread 232 * in the interim. This may result in multiple invocations of the 233 * {@code initialValue} method in the current thread. 234 * 235 * @since 1.5 236 */ 237 public void remove() { 238 ThreadLocalMap m = getMap(Thread.currentThread()); 239 if (m != null) 240 m.remove(this); 241 } 242 243 /** 244 * Get the map associated with a ThreadLocal. Overridden in 245 * InheritableThreadLocal. 246 * 247 * @param t the current thread 248 * @return the map 249 */ 250 ThreadLocalMap getMap(Thread t) { 251 return t.threadLocals; 252 } 253 254 /** 255 * Create the map associated with a ThreadLocal. Overridden in 256 * InheritableThreadLocal. 257 * 258 * @param t the current thread 259 * @param firstValue value for the initial entry of the map 260 */ 261 void createMap(Thread t, T firstValue) { 262 t.threadLocals = new ThreadLocalMap(this, firstValue); 263 } 264 265 /** 266 * Factory method to create map of inherited thread locals. 267 * Designed to be called only from Thread constructor. 268 * 269 * @param parentMap the map associated with parent thread 270 * @return a map containing the parent's inheritable bindings 271 */ 272 static ThreadLocalMap createInheritedMap(ThreadLocalMap parentMap) { 273 return new ThreadLocalMap(parentMap); 274 } 275 276 /** 277 * Method childValue is visibly defined in subclass 278 * InheritableThreadLocal, but is internally defined here for the 279 * sake of providing createInheritedMap factory method without 280 * needing to subclass the map class in InheritableThreadLocal. 281 * This technique is preferable to the alternative of embedding 282 * instanceof tests in methods. 283 */ 284 T childValue(T parentValue) { 285 throw new UnsupportedOperationException(); 286 } 287 288 /** 289 * An extension of ThreadLocal that obtains its initial value from 290 * the specified {@code Supplier}. 291 */ 292 static final class SuppliedThreadLocal<T> extends ThreadLocal<T> { 293 294 private final Supplier<? extends T> supplier; 295 296 SuppliedThreadLocal(Supplier<? extends T> supplier) { 297 this.supplier = Objects.requireNonNull(supplier); 298 } 299 300 @Override 301 protected T initialValue() { 302 return supplier.get(); 303 } 304 } 305 306 /** 307 * ThreadLocalMap is a customized hash map suitable only for 308 * maintaining thread local values. No operations are exported 309 * outside of the ThreadLocal class. The class is package private to 310 * allow declaration of fields in class Thread. To help deal with 311 * very large and long-lived usages, the hash table entries use 312 * WeakReferences for keys. However, since reference queues are not 313 * used, stale entries are guaranteed to be removed only when 314 * the table starts running out of space. 315 */ 316 static class ThreadLocalMap { 317 318 /** 319 * The entries in this hash map extend WeakReference, using 320 * its main ref field as the key (which is always a 321 * ThreadLocal object). Note that null keys (i.e. entry.get() 322 * == null) mean that the key is no longer referenced, so the 323 * entry can be expunged from table. Such entries are referred to 324 * as "stale entries" in the code that follows. 325 */ 326 static class Entry extends WeakReference<ThreadLocal<?>> { 327 /** The value associated with this ThreadLocal. */ 328 Object value; 329 330 Entry(ThreadLocal<?> k, Object v) { 331 super(k); 332 value = v; 333 } 334 } 335 336 /** 337 * The initial capacity -- MUST be a power of two. 338 */ 339 private static final int INITIAL_CAPACITY = 16; 340 341 /** 342 * The table, resized as necessary. 343 * table.length MUST always be a power of two. 344 */ 345 private Entry[] table; 346 347 /** 348 * The number of entries in the table. 349 */ 350 private int size = 0; 351 352 /** 353 * The next size value at which to resize. 354 */ 355 private int threshold; // Default to 0 356 357 /** 358 * Set the resize threshold to maintain at worst a 2/3 load factor. 359 */ 360 private void setThreshold(int len) { 361 threshold = len * 2 / 3; 362 } 363 364 /** 365 * Increment i modulo len. 366 */ 367 private static int nextIndex(int i, int len) { 368 return ((i + 1 < len) ? i + 1 : 0); 369 } 370 371 /** 372 * Decrement i modulo len. 373 */ 374 private static int prevIndex(int i, int len) { 375 return ((i - 1 >= 0) ? i - 1 : len - 1); 376 } 377 378 /** 379 * Construct a new map initially containing (firstKey, firstValue). 380 * ThreadLocalMaps are constructed lazily, so we only create 381 * one when we have at least one entry to put in it. 382 */ 383 ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) { 384 table = new Entry[INITIAL_CAPACITY]; 385 int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1); 386 table[i] = new Entry(firstKey, firstValue); 387 size = 1; 388 setThreshold(INITIAL_CAPACITY); 389 } 390 391 /** 392 * Construct a new map including all Inheritable ThreadLocals 393 * from given parent map. Called only by createInheritedMap. 394 * 395 * @param parentMap the map associated with parent thread. 396 */ 397 private ThreadLocalMap(ThreadLocalMap parentMap) { 398 Entry[] parentTable = parentMap.table; 399 int len = parentTable.length; 400 setThreshold(len); 401 table = new Entry[len]; 402 403 for (Entry e : parentTable) { 404 if (e != null) { 405 @SuppressWarnings("unchecked") 406 ThreadLocal<Object> key = (ThreadLocal<Object>) e.get(); 407 if (key != null) { 408 Object value = key.childValue(e.value); 409 Entry c = new Entry(key, value); 410 int h = key.threadLocalHashCode & (len - 1); 411 while (table[h] != null) 412 h = nextIndex(h, len); 413 table[h] = c; 414 size++; 415 } 416 } 417 } 418 } 419 420 /** 421 * Get the entry associated with key. This method 422 * itself handles only the fast path: a direct hit of existing 423 * key. It otherwise relays to getEntryAfterMiss. This is 424 * designed to maximize performance for direct hits, in part 425 * by making this method readily inlinable. 426 * 427 * @param key the thread local object 428 * @return the entry associated with key, or null if no such 429 */ 430 private Entry getEntry(ThreadLocal<?> key) { 431 int i = key.threadLocalHashCode & (table.length - 1); 432 Entry e = table[i]; 433 if (e != null && e.get() == key) 434 return e; 435 else 436 return getEntryAfterMiss(key, i, e); 437 } 438 439 /** 440 * Version of getEntry method for use when key is not found in 441 * its direct hash slot. 442 * 443 * @param key the thread local object 444 * @param i the table index for key's hash code 445 * @param e the entry at table[i] 446 * @return the entry associated with key, or null if no such 447 */ 448 private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) { 449 Entry[] tab = table; 450 int len = tab.length; 451 452 while (e != null) { 453 ThreadLocal<?> k = e.get(); 454 if (k == key) 455 return e; 456 if (k == null) 457 expungeStaleEntry(i); 458 else 459 i = nextIndex(i, len); 460 e = tab[i]; 461 } 462 return null; 463 } 464 465 /** 466 * Set the value associated with key. 467 * 468 * @param key the thread local object 469 * @param value the value to be set 470 */ 471 private void set(ThreadLocal<?> key, Object value) { 472 473 // We don't use a fast path as with get() because it is at 474 // least as common to use set() to create new entries as 475 // it is to replace existing ones, in which case, a fast 476 // path would fail more often than not. 477 478 Entry[] tab = table; 479 int len = tab.length; 480 int i = key.threadLocalHashCode & (len-1); 481 482 for (Entry e = tab[i]; 483 e != null; 484 e = tab[i = nextIndex(i, len)]) { 485 ThreadLocal<?> k = e.get(); 486 487 if (k == key) { 488 e.value = value; 489 return; 490 } 491 492 if (k == null) { 493 replaceStaleEntry(key, value, i); 494 return; 495 } 496 } 497 498 tab[i] = new Entry(key, value); 499 int sz = ++size; 500 if (!cleanSomeSlots(i, sz) && sz >= threshold) 501 rehash(); 502 } 503 504 /** 505 * Remove the entry for key. 506 */ 507 private void remove(ThreadLocal<?> key) { 508 Entry[] tab = table; 509 int len = tab.length; 510 int i = key.threadLocalHashCode & (len-1); 511 for (Entry e = tab[i]; 512 e != null; 513 e = tab[i = nextIndex(i, len)]) { 514 if (e.get() == key) { 515 e.clear(); 516 expungeStaleEntry(i); 517 return; 518 } 519 } 520 } 521 522 /** 523 * Replace a stale entry encountered during a set operation 524 * with an entry for the specified key. The value passed in 525 * the value parameter is stored in the entry, whether or not 526 * an entry already exists for the specified key. 527 * 528 * As a side effect, this method expunges all stale entries in the 529 * "run" containing the stale entry. (A run is a sequence of entries 530 * between two null slots.) 531 * 532 * @param key the key 533 * @param value the value to be associated with key 534 * @param staleSlot index of the first stale entry encountered while 535 * searching for key. 536 */ 537 private void replaceStaleEntry(ThreadLocal<?> key, Object value, 538 int staleSlot) { 539 Entry[] tab = table; 540 int len = tab.length; 541 Entry e; 542 543 // Back up to check for prior stale entry in current run. 544 // We clean out whole runs at a time to avoid continual 545 // incremental rehashing due to garbage collector freeing 546 // up refs in bunches (i.e., whenever the collector runs). 547 int slotToExpunge = staleSlot; 548 for (int i = prevIndex(staleSlot, len); 549 (e = tab[i]) != null; 550 i = prevIndex(i, len)) 551 if (e.get() == null) 552 slotToExpunge = i; 553 554 // Find either the key or trailing null slot of run, whichever 555 // occurs first 556 for (int i = nextIndex(staleSlot, len); 557 (e = tab[i]) != null; 558 i = nextIndex(i, len)) { 559 ThreadLocal<?> k = e.get(); 560 561 // If we find key, then we need to swap it 562 // with the stale entry to maintain hash table order. 563 // The newly stale slot, or any other stale slot 564 // encountered above it, can then be sent to expungeStaleEntry 565 // to remove or rehash all of the other entries in run. 566 if (k == key) { 567 e.value = value; 568 569 tab[i] = tab[staleSlot]; 570 tab[staleSlot] = e; 571 572 // Start expunge at preceding stale entry if it exists 573 if (slotToExpunge == staleSlot) 574 slotToExpunge = i; 575 cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); 576 return; 577 } 578 579 // If we didn't find stale entry on backward scan, the 580 // first stale entry seen while scanning for key is the 581 // first still present in the run. 582 if (k == null && slotToExpunge == staleSlot) 583 slotToExpunge = i; 584 } 585 586 // If key not found, put new entry in stale slot 587 tab[staleSlot].value = null; 588 tab[staleSlot] = new Entry(key, value); 589 590 // If there are any other stale entries in run, expunge them 591 if (slotToExpunge != staleSlot) 592 cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); 593 } 594 595 /** 596 * Expunge a stale entry by rehashing any possibly colliding entries 597 * lying between staleSlot and the next null slot. This also expunges 598 * any other stale entries encountered before the trailing null. See 599 * Knuth, Section 6.4 600 * 601 * @param staleSlot index of slot known to have null key 602 * @return the index of the next null slot after staleSlot 603 * (all between staleSlot and this slot will have been checked 604 * for expunging). 605 */ 606 private int expungeStaleEntry(int staleSlot) { 607 Entry[] tab = table; 608 int len = tab.length; 609 610 // expunge entry at staleSlot 611 tab[staleSlot].value = null; 612 tab[staleSlot] = null; 613 size--; 614 615 // Rehash until we encounter null 616 Entry e; 617 int i; 618 for (i = nextIndex(staleSlot, len); 619 (e = tab[i]) != null; 620 i = nextIndex(i, len)) { 621 ThreadLocal<?> k = e.get(); 622 if (k == null) { 623 e.value = null; 624 tab[i] = null; 625 size--; 626 } else { 627 int h = k.threadLocalHashCode & (len - 1); 628 if (h != i) { 629 tab[i] = null; 630 631 // Unlike Knuth 6.4 Algorithm R, we must scan until 632 // null because multiple entries could have been stale. 633 while (tab[h] != null) 634 h = nextIndex(h, len); 635 tab[h] = e; 636 } 637 } 638 } 639 return i; 640 } 641 642 /** 643 * Heuristically scan some cells looking for stale entries. 644 * This is invoked when either a new element is added, or 645 * another stale one has been expunged. It performs a 646 * logarithmic number of scans, as a balance between no 647 * scanning (fast but retains garbage) and a number of scans 648 * proportional to number of elements, that would find all 649 * garbage but would cause some insertions to take O(n) time. 650 * 651 * @param i a position known NOT to hold a stale entry. The 652 * scan starts at the element after i. 653 * 654 * @param n scan control: {@code log2(n)} cells are scanned, 655 * unless a stale entry is found, in which case 656 * {@code log2(table.length)-1} additional cells are scanned. 657 * When called from insertions, this parameter is the number 658 * of elements, but when from replaceStaleEntry, it is the 659 * table length. (Note: all this could be changed to be either 660 * more or less aggressive by weighting n instead of just 661 * using straight log n. But this version is simple, fast, and 662 * seems to work well.) 663 * 664 * @return true if any stale entries have been removed. 665 */ 666 private boolean cleanSomeSlots(int i, int n) { 667 boolean removed = false; 668 Entry[] tab = table; 669 int len = tab.length; 670 do { 671 i = nextIndex(i, len); 672 Entry e = tab[i]; 673 if (e != null && e.get() == null) { 674 n = len; 675 removed = true; 676 i = expungeStaleEntry(i); 677 } 678 } while ( (n >>>= 1) != 0); 679 return removed; 680 } 681 682 /** 683 * Re-pack and/or re-size the table. First scan the entire 684 * table removing stale entries. If this doesn't sufficiently 685 * shrink the size of the table, double the table size. 686 */ 687 private void rehash() { 688 expungeStaleEntries(); 689 690 // Use lower threshold for doubling to avoid hysteresis 691 if (size >= threshold - threshold / 4) 692 resize(); 693 } 694 695 /** 696 * Double the capacity of the table. 697 */ 698 private void resize() { 699 Entry[] oldTab = table; 700 int oldLen = oldTab.length; 701 int newLen = oldLen * 2; 702 Entry[] newTab = new Entry[newLen]; 703 int count = 0; 704 705 for (Entry e : oldTab) { 706 if (e != null) { 707 ThreadLocal<?> k = e.get(); 708 if (k == null) { 709 e.value = null; // Help the GC 710 } else { 711 int h = k.threadLocalHashCode & (newLen - 1); 712 while (newTab[h] != null) 713 h = nextIndex(h, newLen); 714 newTab[h] = e; 715 count++; 716 } 717 } 718 } 719 720 setThreshold(newLen); 721 size = count; 722 table = newTab; 723 } 724 725 /** 726 * Expunge all stale entries in the table. 727 */ 728 private void expungeStaleEntries() { 729 Entry[] tab = table; 730 int len = tab.length; 731 for (int j = 0; j < len; j++) { 732 Entry e = tab[j]; 733 if (e != null && e.get() == null) 734 expungeStaleEntry(j); 735 } 736 } 737 } 738 }