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