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