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