Full explanation of ThreadLocal source code (threadlocalmap)

1. ThreadLocal Source code analysis

 

1.1 ThreadLocal principle

First of all, we have to start with Thread Class begins , stay Thread Class maintains two ThreadLocal.ThreadLocalMap object （ For the initial null, Only when calling ThreadLocal Class set or get Create them only when ）：threadLocals and inheritableThreadLocals. That is to say, each Thread Objects have two ThreadLocalMap object ,ThreadLocalMap yes ThreadLocal custom HashMap, yes ThreadLocal The inner class of , Its key Weakly quoted ThreadLocal object ,value Set for the corresponding Object object .

public class Thread implements Runnable {
    //......
    // Related to this thread ThreadLocal value . from ThreadLocal Class maintenance 
    ThreadLocal.ThreadLocalMap threadLocals = null;

    // Related to this thread InheritableThreadLocal value . from InheritableThreadLocal Class maintenance 
    ThreadLocal.ThreadLocalMap inheritableThreadLocals = null;
    //......
}

We want to set up ThreadLocal When the value of , By looking at the source code, we can find , Use ThreadLocal Of set() Method is actually called by the current thread ThreadLocalMap Of set() Method .ThreadLocal Of set() In the method , First use Thread.currentThread() Get current thread object t , Through the current thread object t Get threaded ThreadLocalMap object map , Then judge map Is it null—— by null Call creadMap() Method to pass in the current thread object t And the current set() The input of method value Create creates... For the current thread ThreadLocalMap Object and put value Add variables ; Not for null Call map.set(value) Set the ThreadLocal The value of the object .

// ThreadLocal.java
public void set(T value) {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null)
        map.set(this, value);
    else
        createMap(t, value);
}
ThreadLocalMap getMap(Thread t) {
    return t.threadLocals;
}

thus it can be seen , Variables are placed in the current thread ThreadLocalMap in , and ThreadLocal yes ThreadLocalMap Encapsulation , Passed variable value .

1.2 ThreadLocalMap principle

ThreadLocalMap The data structure of is actually an array , contrast HashMap It has only hash arrays and no linked lists .

1.2.1 ThreadLocalMap Four properties of

• Entry[] table
• INITIAL_CAPACITY
• size
• threshold

//  Source code 
static class ThreadLocalMap {
    
    static class Entry extends WeakReference<ThreadLocal<?>> {
        /** The value associated with this ThreadLocal. */
        Object value;

        Entry(ThreadLocal<?> k, Object v) {
            super(k);
            value = v;
        }
    }

    // The initial capacity defaults to 16, Must be 2 The power of 
    private static final int INITIAL_CAPACITY = 16;

    // table Every time resized, The capacity must be 2 The power of 
    private Entry[] table;

    //  At present table Number of elements stored in 
    private int size = 0;

    //  Expansion threshold 
    private int threshold; // Default to 0
	
    /**
     *  And then there's  set()、get()、 Expansion method 、expungeStaleEntry()、cleanSomeSlots() And other important methods will not post the source code 
	 * ......
     */
} 

1.2.2 Hash Algorithm

ThreadLocalMap Achieve your own hash Algorithm to resolve hash array conflicts .

int i = key.threadLocalHashCode & (len - 1);

 there `i`  Is the current  key  The corresponding array subscript position in the hash table .`len`  refer to `ThreadLocalMap`  Current capacity `capacity`.
 And the more important thing is that we must know `key.threadLocalHashCode`  How is this value calculated ？
 We can know through the source code `threadLocalHashCode`  yes `ThreadLocal`  A property of , Its value is to call `ThreadLocal`  Of `nextHahCode()`  Method of obtaining .
`nextHashCode()`： return `AtomicInteger nextHahCode`  Value , And will `AtomicInteger nextHahCode`   Self incrementing a constant value ——`HASH_INCREMENT(0x61c88647)`.
> __ Special reminder __： For every one created `ThreadLocal`  object （ Every time the object  hash  To  map  once ）,`ThreadLocal.nextHashCode`  Just grow `0x61c88647`.（`0x61c88647`  It's the Fibonacci number , Use this value as  hash  Increment can make  hash  More uniform distribution .）
 
 The code is as follows ：
```java

public class ThreadLocal<T> {
    private final int threadLocalHashCode = nextHashCode();

    private static AtomicInteger nextHashCode = new AtomicInteger();

    private static final int HASH_INCREMENT = 0x61c88647;

    private static int nextHashCode() {
        return nextHashCode.getAndAdd(HASH_INCREMENT);
    }

    static class ThreadLocalMap {
        ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) {
            table = new Entry[INITIAL_CAPACITY];
            int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);

            table[i] = new Entry(firstKey, firstValue);
            size = 1;
            setThreshold(INITIAL_CAPACITY);
        }
    } 
}

summary ：ThreadLocalMap Of hash The algorithm is very simple , Is to use the multiple of Fibonacci number and (len -1) Bitwise AND （ This result is actually a multiple of Fibonacci number Yes capacity modulus ） As a result of the current key Array subscript in hash table .

1.2.3 Hash Conflict

HashMap How to solve hash Conflict ：HashMap The solution to the conflict is to use the chain address method , Construct a linked list structure on an array , Put the conflicting data on the linked list , And when the length of each array element, that is, the linked list exceeds a certain number, the linked list will be converted into a red black tree .

ThreadLocalMap The open address method of linear detection is used to solve hash Conflict . When the present key There is hash Conflict , Will probe back linearly until it is found to be null The location of is stored in the object , Or find key Update the original object by overwriting the same location . During this process, if it is found that it is not empty but key by null The barrel （key overdue Entry data ） Then start the probe cleaning operation .

4.1.2.4 ThreadLocal.set() Source details

ThreadLocal in set() The principle of the method ： Get the current thread object first , Pass in the thread object to getMap() Methods to get ThreadLocalMap object , Judge whether it exists , To be is to use map Of set() Method for data processing , Otherwise, call createMap() Method to pass in the current thread object and value establish map. The code is as follows ：

// ThreadLocal  Of  set()  Method source code 
public void set(T value){
  Thread t = Thread.currentThread();
  ThreadLocalMap map=getMap(t);
  if(map != null)
	  map.set(this, value);
  else
	  createMap(t, value);
}
void create(Thread t, T firstValue){
	t.threadLocals = new ThreadLocalMap(this, firstValue);
}

set() The main core logic of the method is still ThreadLocalMap .

1.2.5 ThreadLocalMap.set() The principle,

adopt ThreadLocalMap Medium set() Method can add or update data , This can be divided into four cases ：

• One ： adopt hash The calculated position corresponds to Entry Data is empty ： Directly store the data in this location .
• Two ： The data corresponding to the position is not empty , but key Value and current ThreadLocal hash Calculated key Same value ： Directly overwrite the data updates to this location .
• 3、 ... and ：hash The location to is not empty ,key Value and current hash To the key The value is different , Traverse backwards and find Entry by null Or key Before the same position , Not encountered Entry not null but key by null The situation of ： Directly store data or update data .
• Four ：hash The location to is not empty , Encountered while traversing backwards Entry not null but key by null （ Suppose the subscript of this position is x ） The situation of ：
• Execute at this time replaceStaleEntry() Method （ Replace expired data ）, From the subscript x Traverse forward for the starting point , Initialize the start position of probe cleaning ：slotToExpunge = staleSlot = x, Perform exploratory data cleansing .
• from staleSlot Start traversing forward to find other expired data , And update the starting subscript for cleaning up expired data slotToExpunge（ encounter key by null The location of is updated slotToExpu nge = The subscript ）, Until I met Entry = null Stop traversing forward .
• from staleSlot Start traversing backwards , Until I met Entry = null perhaps key = hash Later obtained key.
• * `Entry = null`： Replace the data coverage with `staleSlot` In position `Entry` .
  • key = hash Later obtained key： Update data , Then with staleSlot Of Entry In exchange for .
• before 3 If two or more key = null Call cleanSomeSlots(expungeStaleEntry(slotToExpunge), len) Method to clean up expired elements .（ from slotToExpunge Start checking backwards and cleaning up expired elements , At this time, it is mainly through expungeStaleEntry() and cleanSomeSlots() Two methods work .）

1.2.6 ThreadLocalMap.set() Source details

set() The code of the method is as follows ：

// ThreadLocal.ThreadLocalMap.set() Method 
private void set(ThreadLocal<?> key, Object value) {
    //  adopt  key  Calculate the current  key  In the corresponding position of the hash table ——i
    Entry[] tab = table;
    int len = tab.length;
    int i = key.threadLocalHashCode & (len-1);
    
    //  from  i  Start traversing backwards , Find the empty location （ Which is to get  tab[i]）, Be careful ： adopt nextIndex() Method , After traversing the last position of the hash array , The next position to traverse is  index=0
    /** 
     * private static int nextIndex(int i, int len) {
     *     return ((i + 1 < len) ? i + 1 : 0);
     * }
	*/
    for (Entry e = tab[i];
         e != null;
         e = tab[i = nextIndex(i, len)]) {
        ThreadLocal<?> k = e.get();
		//  encounter key identical , Direct update overrides , return 
        if (k == key) {
            e.value = value;
            return;
        }
		//  Traverse to key=null（ Expired elements ）, perform replaceStaleEntry(), return 
        if (k == null) {
            replaceStaleEntry(key, value, i);
            return;
        }
    }

    //  stay   Empty position   Storing data 
    tab[i] = new Entry(key, value);
    // size++
    int sz = ++size;
    //  call boolean cleanSomeSlots() Perform heuristic cleanup of expired elements 
    //  If no data is cleaned up and size Threshold exceeded threshold（len*2/3） be rehash(),rehash() Will first probe to clean up expired elements , If at this time size>=len/2(threshold-threshold/4) Then expand the capacity 
    if (!cleanSomeSlots(i, sz) && sz >= threshold)
        rehash();
}

Through the above code and comments, you can clearly understand the use of set() The processing logic of the first three cases of method , The main processing logic of the fourth case is replaceStaleEntry() In the method .

ThreadLocal.ThreadLocalMap.replaceStaleEntry() The method code is as follows ：

// ThreadLocal.ThreadLocalMap.replaceStaleEntry()
private void replaceStaleEntry(ThreadLocal<?> key, Object value,
                                       int staleSlot) {
    Entry[] tab = table;
    int len = tab.length;
    Entry e;
	//  from staleSlot Traverse forward until you encounter Entry=null, Encountered during key=null When the update slotToExpunge
    int slotToExpunge = staleSlot;
    for (int i = prevIndex(staleSlot, len);
         (e = tab[i]) != null;
         i = prevIndex(i, len))
        if (e.get() == null)
            slotToExpunge = i;
	//  from staleSlot Traverse backward , until Entry=null stop it 
    for (int i = nextIndex(staleSlot, len);
         (e = tab[i]) != null;
         i = nextIndex(i, len)) {

        ThreadLocal<?> k = e.get();
		//  encounter key=key
        if (k == key) {
            //  Update the location Entry And match this position with staleSlot Of Entry In exchange for 
            e.value = value;
			
            tab[i] = tab[staleSlot];
            tab[staleSlot] = e;
			//  If at this time slotToExpunge=staleSlot, It indicates that no expired elements are found during forward traversal and no expired elements are found during backward traversal , At this point, modify the initial subscript of the expired element of the probe cleanup to i（ That is from i Start probe cleanup as the starting subscript ）
            if (slotToExpunge == staleSlot)
                slotToExpunge = i;
            // cleanSomeSlots() Clean up for heuristics ,expungeStaleEntry() It is a probe type cleaning 
            cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
            return;
        }
		//  If key=null  And  slotToExpunge=staleSlot, Description: the forward traversal did not encounter expired elements, but the backward traversal encountered expired elements , At this point, modify the initial subscript of the expired element of the probe cleanup to i
        if (k == null && slotToExpunge == staleSlot)
            slotToExpunge = i;
    }
	//  from staleSlot Encountered during backward traversal Entry=null, At this point, the data is directly updated to staleSlot Location 
    tab[staleSlot].value = null;
    tab[staleSlot] = new Entry(key, value);
	//  if slotToExpunge!=staleSlot, It indicates that there are expired elements encountered during forward traversal or backward traversal , here slotToExpunge Is traversing forward “ furthest ” Or encountered in backward traversal “ furthest ” Of key by null The subscript , Start heuristic cleanup after probe cleanup .
    if (slotToExpunge != staleSlot)
        cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
}

1.2.7 Probe cleaning details

Probe cleaning , That is to say expungeStaleEntry() Method .

Traverse backwards from the start position , Clear expired elements , Of the expired data that will be traversed Entry Set to null , The unexpired data encountered along the way will be rehash And then again in table Middle positioning , If there is data at the location, you can go back and find the first one Entry=null Store in the location of . Then continue to check the expired data later , The detection is not terminated until an empty bucket is encountered .

The code is as follows ：

private int expungeStaleEntry(int staleSlot) {
    Entry[] tab = table;
    int len = tab.length;
	//  Incoming staleSlot The data on the location must be out of date , take staleSlot Empty position 
    tab[staleSlot].value = null;
    tab[staleSlot] = null;
    size--;
	// for A loop is a backward traversal , Until I met  Entry=null
    Entry e;
    int i;
    for (i = nextIndex(staleSlot, len);
         (e = tab[i]) != null;
         i = nextIndex(i, len)) {
        ThreadLocal<?> k = e.get();
        //  If the current traversal  key  by  null Will  Entry empty 
        if (k == null) {
            e.value = null;
            tab[i] = null;
            size--;
        // If the current traversal  key  Not for null, Put it rehash And will key The original location of Entry empty , then key Of Entry Put in rehash The position of the back and the first of its back positions are null The location of 
        } else {
            int h = k.threadLocalHashCode & (len - 1);
            if (h != i) {
                tab[i] = null;

                while (tab[h] != null)
                    h = nextIndex(h, len);
                tab[h] = e;
            }
        }
    }
    //  return i, That is, the first one encountered in the backward traversal of the probe cleanup is null The location of 
    return i;
}

This can make rehash After the data distance from the correct position （i= key.hashCode & (tab.len - 1)） Closer . It can improve the query performance of the whole hash table .

1.2.8 Heuristic cleanup details

Heuristic cleanup ,cleanSomeSlots(int i, int n) ：

Traverse backward ⌊log2n⌋\lfloor log_2 n \rfloor⌊log2​n⌋ A place , Subscript i As the first position of traversal . Encountered in traversal at position key=null when （ Suppose the location is i ）, A synchronous invocation expungeStaleEntry(i) Method .

The code is as follows ：

private boolean cleanSomeSlots(int i, int n) {
    boolean removed = false;
    Entry[] tab = table;
    int len = tab.length;
    do {
        i = nextIndex(i, len);
        Entry e = tab[i];
        if (e != null && e.get() == null) {
            n = len;
            removed = true;
            i = expungeStaleEntry(i);
        }
    } while ( (n >>>= 1) != 0);
    return removed;
}

Be careful ： stay ThreadLocalMap.set() Method call method ThreadLocalMap.replaceStaleEntry() , This is usually called —— cleanSomeSlots(expungeStaleEntry(slotToExpunge), len) .

1.2.9 Expansion mechanism

ThreadLocalMap The expansion of is in set() Method before it can be executed . stay set() At the end of the method , If in set() No data is cleaned up and size Exceeds or equals the threshold threshold（ That is to say len*2/3） be rehash().rehash() Will first probe to clean up expired elements , If in rehash() After clearing size>=len/2（ That is to say threshold-threshold/4） Call resize() Capacity expansion .

Be careful ： The threshold is len*2/3 .

rehash() The code for is as follows ：

private void rehash() {
    //  The method is subscript 0 set out , Find the first  key=null  The location of j, With j Start probe cleanup for start 
    expungeStaleEntries();
    //  threshold  threshold=len*2/3
	//  At present size Exceeding or equal to the threshold 3/4 Execute extension when 
    if (size >= threshold - threshold / 4)
        resize();
}

private void expungeStaleEntries() {
    Entry[] tab = table;
    int len = tab.length;
    for (int j = 0; j < len; j++) {
        Entry e = tab[j];
        if (e != null && e.get() == null)
            expungeStaleEntry(j);
    }
}

The specific implementation of capacity expansion is resize() . First , Capacity expansion is tab Directly expand the capacity to the original 2 Times , Then traverse the old hash table , Recalculate... For each element hash Place in the new tab Array , encounter hash Conflict is looking for the nearest entry=null To store in . Finally, recalculate tab The threshold for performing capacity expansion .

resize() The code for is as follows ：

private void resize() {
    Entry[] oldTab = table;
    int oldLen = oldTab.length;
    int newLen = oldLen * 2;
    Entry[] newTab = new Entry[newLen];
    int count = 0;

    for (int j = 0; j < oldLen; ++j) {
        Entry e = oldTab[j];
        if (e != null) {
            ThreadLocal<?> k = e.get();
            if (k == null) {
                e.value = null;
            } else {
                int h = k.threadLocalHashCode & (newLen - 1);
                while (newTab[h] != null)
                    h = nextIndex(h, newLen);
                newTab[h] = e;
                count++;
            }
        }
    }

    setThreshold(newLen);
    size = count;
    table = newTab;
}

1.2.10 ThreadLocalMap.get() Detailed explanation

Use get() Operation to obtain data has 2 In this case ：

• ** One ：** Through the introduction of key Calculated position , position Entry!=null && k==key , Go straight back to .
• ** Two ：** In position Entry Of key and Incoming key It's not equal , Then traverse backwards from this position , encounter key=null Just start the probe cleanup and continue to traverse , Until traversal to key= Incoming key The location of , Finally, place the Entry return ; Or in position Entry It's empty , return null.

ThreadLocalMap.get() The code for is as follows ：

private Entry getEntry(ThreadLocal<?> key) {
    int i = key.threadLocalHashCode & (table.length - 1);
    Entry e = table[i];
    if (e != null && e.get() == key)
        //  Case one 
        return e;
    else
        //  The second case 
        return getEntryAfterMiss(key, i, e);
}

private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
    Entry[] tab = table;
    int len = tab.length;

    while (e != null) {
        ThreadLocal<?> k = e.get();
        //  Traversing key= Incoming key, Return to the Entry
        if (k == key)
            return e;
        if (k == null)
            //  Encountered in traversal  key=null, Start probe cleaning 
            expungeStaleEntry(i);
        else
            i = nextIndex(i, len);
        e = tab[i];
    }
    //  Encountered in traversal null
    return null;
}

2. ThreadLocal The problem of

2.1 ThreadLocal Memory leak problem

WeakReference Weak reference ： The references we usually use are basically weak references , Weak quotation can be understood as an indispensable item in life , When an object is only weakly referenced , stay GC Once the object is scanned , The object will be cleaned up .

stay ThreadLocalMap Medium Entry Of key It's right ThreadLocal Of WeakReference Weak reference , and value Is a strong quote . When ThreadLocalMap Of ThreadLocal Objects are only weakly referenced ,GC The object will be cleaned up when it occurs , here key by null, but value For strong references will not be cleaned up . here value Not being accessed or cleaned up may lead to memory leakage .

So we used up ThreadLocal It's best to call... Manually after remove() Method . But in fact ThreadLocalMap And considering this situation , So in the call set()、get()、remove() When the method is used , Will clean up key by null The record of .

2.2 ThreadLocal Cannot share thread copy data of parent thread to child thread

In an asynchronous scenario, the child thread cannot share the thread copy data of the parent thread , Can pass InheritableThreadLocal Class solves this problem .

Its principle is that the child thread is called in the parent thread new Thread() Created , stay Thread Called in the construction method Thread Of init Method , stay init The parent thread data in the method will be copied to the child thread （ThreadLocal.createInheritedMap(parent.inheritableThreadLocals);）.

But we use thread pool for asynchronous processing , The thread pool will reuse threads, which will cause problems . In this case, we need to solve it by ourselves .

author ： The advancing sea
link ：https://juejin.cn/post/7113023112655929358