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