ThreadLocal


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