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