Source code analysis of ThreadLocal and its core methods

Reference from JavaGuide
Outline:

1, Function

The ThreadLocal class implements that each thread has its own unique local variable.
If you create a ThreadLocal variable, each thread accessing this variable will have a local copy of this variable, which is also the origin of the ThreadLocal variable name. They can use the get () and set () methods to get the default value or change its value to the value of the copy stored by the current thread, thus avoiding thread safety problems.

2, Shortcomings

  1. Memory leak
    The key used in ThreadLocalMap is a weak reference to ThreadLocal, while value is a strong reference. Therefore, if ThreadLocal is not strongly referenced by the outside, during garbage collection, the key will be cleaned up, but the value will not be cleaned up. If we do not take any measures, value will never be recycled by GC, and memory leakage may occur at this time.
    This situation has been considered in the implementation of ThreadLocalMap. When calling the set(), get(), and remove() methods, the records with null key will be cleared. After calling the local thread() method, it is best to use the local thread() method manually.
  2. Parent child thread data cannot be shared

3, Principle

Start with the Thread class. First of all, there is a threadLocals and an inheritableThreadLocals variable in the Thread class. By default, these two variables are null. They are created only when the current Thread calls the set or get method of ThreadLocal class. They are variables of ThreadLocalMap type. ThreadLocalMap is the static internal class of ThreadLocal class. If a Thread accesses a variable of ThreadLocal type, there will be a key value pair with ThreadLocal Object as key and Object object as value in the ThreadLocalMap of the Thread.
The final variable is placed in the ThreadLocalMap of the current Thread, not on ThreadLocal. ThreadLocal can be understood as just the encapsulation of ThreadLocalMap, passing the variable value. In ThrealLocal class, you can use Thread After currentthread() obtains the current Thread Object, you can directly access the ThreadLocalMap Object of the Thread through getMap(Thread t). Each Thread has a ThreadLocalMap, which can store key value pairs with ThreadLocal as the key and Object object as the value.

4, Thread, ThreadLocalMap, ThreadLocal structure relationship

Each Thread has its own ThreadLocalMap. ThreadLocalMap is the static internal class of ThreadLocal class. ThreadLocalMap is an Entry array, which defines the Entry node class, and the key of the Entry is. ThreadLocal type inherited from WeakReference, that is, key is a weak reference type, value is a value put in the code, and it is a strong reference.

5, In ThreadLocal During get(), is the key null after GC?

Is not null. Because I'm doing ThreadLocal During the get () operation, it is proved that there is still a strong reference, so the key is not null. As shown in the figure below, the strong reference of ThreadLocal still exists.
If our strong reference does not exist, the key will be recycled, that is, our value will not be recycled and the key will be recycled, resulting in the permanent existence of value and memory leakage.

There are four reference types in Java:
Strong reference: the object we often new is a strong reference type. As long as the strong reference exists, the garbage collector will never recycle the referenced object, even when the memory is insufficient
Soft reference: the object decorated with SoftReference is called soft reference. The object pointed to by soft reference is recycled when memory is about to overflow
Weak reference: an object decorated with WeakReference is called a weak reference. As long as garbage collection occurs, if the object is only pointed to by a weak reference, it will be recycled
Virtual reference: virtual reference is the weakest reference, which is defined by phantom reference in Java. The only function of a virtual reference is to queue up to receive notification that an object is about to die

6, ThreadLocal Set() method

The source code is as follows:

/**
     * Sets the current thread's copy of this thread-local variable
     * to the specified value.  Most subclasses will have no need to
     * override this method, relying solely on the {@link #initialValue}
     * method to set the values of thread-locals.
     *
     * @param value the value to be stored in the current thread's copy of
     *        this thread-local.
     */
    public void set(T value) {
        Thread t = Thread.currentThread();
        ThreadLocalMap map = getMap(t);
        if (map != null)
            map.set(this, value);
        else
            createMap(t, value);
    }


The core logic is still in the set () method of ThreadLocalMap (later). ThreadLocal. The process of set() method is as follows:

  1. Gets the threadlocalmap of the current thread.
  2. If the map is not null, the map The set() method sets the value.
  3. If the map is null, the createMap method is called to create and set the value to be put in. The createMap() method is created through the construction method of ThreadLocalMap. The construction method mainly initializes the Entry[] table capacity 16, uses the hash algorithm to calculate the subscript corresponding to the value to be set, assigns the value of the table array through the subscript, initializes the number of stored elements, and initializes the minimum capacity expansion value of the array.

7, ThreadLocal Get() method

The source code is as follows:

/**
     * Returns the value in the current thread's copy of this
     * thread-local variable.  If the variable has no value for the
     * current thread, it is first initialized to the value returned
     * by an invocation of the {@link #initialValue} method.
     *
     * @return the current thread's value of this thread-local
     */
    public T get() {
        Thread t = Thread.currentThread();
        ThreadLocalMap map = getMap(t);
        if (map != null) {
            ThreadLocalMap.Entry e = map.getEntry(this);
            if (e != null) {
                @SuppressWarnings("unchecked")
                T result = (T)e.value;
                return result;
            }
        }
        return setInitialValue();
    }

**The core logic is still in the getEntry() method of ThreadLocalMap** ThreadLocal. The process of get() method is as follows:

  1. Gets the threadlocalmap of the current thread.
  2. If the map is not null, call map The getentry () method obtains the Entry corresponding to the thread.
  3. If the map is empty, create a new map and initialize the value of the thread to null.

8, ThreadLocalMap

8.1 Hash algorithm

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

Here i is the corresponding array subscript position of the current key in the hash table. The key is the calculation of threadLocalHashCode value: every time a ThreadLocal object is created, the value will increase by 0x61c88647. This value is very special. It is Fibonacci number, also known as golden section number. The hash increment is this number, which brings the advantage that the hash distribution is very uniform.

8.2 Hash conflict

Calculate the subscript through hash. If the subscript slot has data, if the key is the same, update the data. Otherwise, it will find the slot with null entry and insert the data. If the entry is not null but the key is null, start cleaning up the expired data.

8.3 principle of set () method

8.3.1 simplified set method flow

First, calculate the subscript corresponding to the data through the hash algorithm. After calculation, perform different operations according to the current Entry position. There are four main situations:

  1. Case 1: if the Entry corresponding to the subscript is null, the data can be directly put into the slot.
  2. Case 2: if the Entry corresponding to the subscript is not null, but the key is the same, the value value is updated.
  3. Case 3: if the Entry corresponding to the subscript is not null and the key is not the same, traverse the array backward. Before finding the slot with null Entry, if no Entry with null key is encountered, put the data into the slot with null Entry; Or if you encounter data with equal key values during subsequent traversal, you can update it directly.
  4. Case 4: if the Entry corresponding to the subscript is not null and the key is not the same, traverse the array backward. Before finding the slot where the Entry is null, an Entry with null key is encountered, indicating that the key of this data has been garbage collected. At this time, the replacestateentry() method will be executed. This method is mainly used to set data and clean up expired data at the same time.

Finally, a heuristic will be conducted to clean up expired data and judge whether capacity expansion is needed.

8.3.2 set() method source code and specific version process

/**
         * Set the value associated with key.
         *
         * @param key the thread local object
         * @param value the value to be set
         */
        private void set(ThreadLocal<?> key, Object value) {

            // We don't use a fast path as with get() because it is at
            // least as common to use set() to create new entries as
            // it is to replace existing ones, in which case, a fast
            // path would fail more often than not.

            Entry[] tab = table;
            int len = tab.length;
            int i = key.threadLocalHashCode & (len-1);

            for (Entry e = tab[i];
                 e != null;
                 e = tab[i = nextIndex(i, len)]) {
                ThreadLocal<?> k = e.get();

                if (k == key) {
                    e.value = value;
                    return;
                }

                if (k == null) {
                    replaceStaleEntry(key, value, i);
                    return;
                }
            }

            tab[i] = new Entry(key, value);
            int sz = ++size;
            if (!cleanSomeSlots(i, sz) && sz >= threshold)
                rehash();
        }

The code flow is mainly as follows:
First, calculate the corresponding position in the hash table through the key, and then look back with the position of the bucket corresponding to the current key.
Logic in the for loop:

  1. The Entry data in the bucket corresponding to the current key value is empty, which indicates that there is no data conflict in the hash array. Jump out of the for loop and directly set the data into the corresponding bucket
  2. If the Entry data in the bucket corresponding to the key value is not empty
    2.1 if k = key, it indicates that the current set operation is a replacement operation. Do the replacement logic and return directly
    2.2 if key = null, it means that the Entry of the current bucket position is expired data. Execute the replacestateentry() method. This method is mainly used to clean up the expired data (core method) while set ting the data, and then return
  3. After the execution of the for loop, continue to execute. It indicates that the entry is null in the process of backward iteration
    3.1 create a new Entry object in the bucket with null Entry 3.2 execute + + size operation
  4. Call cleanSomeSlots() to do a heuristic cleanup to clean up the expired data of the Entry key in the hash array
    4.1 if no data is cleaned up after cleaning, and the size exceeds the threshold (2 / 3 of the array length), rehash() operation is performed
    4.2 rehash() will first conduct a round of probing cleaning to clean up expired key s. After cleaning, if size > = threshold - threshold / 4, the real expansion logic will be executed (the expansion logic will look back)

A flow chart:

8.3.3 replacestateentry() source code + text flow (the core method in set method)

The source code is as follows:

/**
         * Replace a stale entry encountered during a set operation
         * with an entry for the specified key.  The value passed in
         * the value parameter is stored in the entry, whether or not
         * an entry already exists for the specified key.
         *
         * As a side effect, this method expunges all stale entries in the
         * "run" containing the stale entry.  (A run is a sequence of entries
         * between two null slots.)
         *
         * @param  key the key
         * @param  value the value to be associated with key
         * @param  staleSlot index of the first stale entry encountered while
         *         searching for key.
         */
        private void replaceStaleEntry(ThreadLocal<?> key, Object value,
                                       int staleSlot) {
            Entry[] tab = table;
            int len = tab.length;
            Entry e;

            // Back up to check for prior stale entry in current run.
            // We clean out whole runs at a time to avoid continual
            // incremental rehashing due to garbage collector freeing
            // up refs in bunches (i.e., whenever the collector runs).
            int slotToExpunge = staleSlot;
            for (int i = prevIndex(staleSlot, len);
                 (e = tab[i]) != null;
                 i = prevIndex(i, len))
                if (e.get() == null)
                    slotToExpunge = i;

            // Find either the key or trailing null slot of run, whichever
            // occurs first
            for (int i = nextIndex(staleSlot, len);
                 (e = tab[i]) != null;
                 i = nextIndex(i, len)) {
                ThreadLocal<?> k = e.get();

                // If we find key, then we need to swap it
                // with the stale entry to maintain hash table order.
                // The newly stale slot, or any other stale slot
                // encountered above it, can then be sent to expungeStaleEntry
                // to remove or rehash all of the other entries in run.
                if (k == key) {
                    e.value = value;

                    tab[i] = tab[staleSlot];
                    tab[staleSlot] = e;

                    // Start expunge at preceding stale entry if it exists
                    if (slotToExpunge == staleSlot)
                        slotToExpunge = i;
                    cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
                    return;
                }

                // If we didn't find stale entry on backward scan, the
                // first stale entry seen while scanning for key is the
                // first still present in the run.
                if (k == null && slotToExpunge == staleSlot)
                    slotToExpunge = i;
            }

            // If key not found, put new entry in stale slot
            tab[staleSlot].value = null;
            tab[staleSlot] = new Entry(key, value);

            // If there are any other stale entries in run, expunge them
            if (slotToExpunge != staleSlot)
                cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
        }

**I think the main function of this method is to clean up expired data while set ting data** There are two for loops in this method. There are two important variables: staleSlot: the location of the first expired bucket encountered when looking for the key. slotToExpunge: the starting position to start probe cleaning of expired data.

  • The first for loop is to determine the starting position of the snooping cleanup of expired data, slotToExpunge. The specific process is:
    The current staleSlot (expired bucket position) starts and iterates forward to find. If the expired data is found forward, the start subscript of the update probe cleaning up the expired data is the current position subscript, and the for loop will end when the Entry is null.
  • **Next is the second for loop. The second for loop is to set data and clean up expired data at the same time** The specific process is:
    Search backward from the staleSlot and end the loop when encountering data with null Entry.
    During the iteration,
    (1) If the key in the bucket is the same as the key to be inserted, i.e. k=key, the data is updated and the position is exchanged with the element of the current staleSlot position. If slotToExpunge=staleSlot, it means that the expired Entry data is not found when looking forward for the expired data, and then the expired data is not found during the backward search, then the slottoexpunge is updated to the current position, which is used as the starting point for probing to clean up the expired data. Finally, call cleanSomeSlots(expungeStaleEntry(slotToExpunge), len). Base note: Perform probing cleanup and heuristic cleanup, and then return;
    (2) If you encounter expired data (k==null) and slotToExpunge == staleSlot, it means that you can't find the expired Entry by looking forward to the data, update the slotToExpunge, and the current position is the starting point of probing to clean up the expired data.
    The data with null Entry ends the second cycle, which is to add new data to the previously marked expired bucket position staleSlot.
    Finally, judge whether there are other expired data (slotttoexpunge! = staleSlot) in addition to the staleSlot. If so, turn on the logic of data cleaning, first conduct a probe cleaning (explungestaleentry method) and then a heuristic cleaning (cleanSomeSlots method).

Finally, the entire replacestateentry method ends.

JavaGuide has a detailed example flow chart for reference.

8.4 probe cleaning of expired key s (expungeStaleEntry method process)

The source code is as follows:

/**
         * Expunge a stale entry by rehashing any possibly colliding entries
         * lying between staleSlot and the next null slot.  This also expunges
         * any other stale entries encountered before the trailing null.  See
         * Knuth, Section 6.4
         *
         * @param staleSlot index of slot known to have null key
         * @return the index of the next null slot after staleSlot
         * (all between staleSlot and this slot will have been checked
         * for expunging).
         */
        private int expungeStaleEntry(int staleSlot) {
            Entry[] tab = table;
            int len = tab.length;

            // expunge entry at staleSlot
            tab[staleSlot].value = null;
            tab[staleSlot] = null;
            size--;

            // Rehash until we encounter null
            Entry e;
            int i;
            for (i = nextIndex(staleSlot, len);
                 (e = tab[i]) != null;
                 i = nextIndex(i, len)) {
                ThreadLocal<?> k = e.get();
                if (k == null) {
                    e.value = null;
                    tab[i] = null;
                    size--;
                } else {
                    int h = k.threadLocalHashCode & (len - 1);
                    if (h != i) {
                        tab[i] = null;

                        // Unlike Knuth 6.4 Algorithm R, we must scan until
                        // null because multiple entries could have been stale.
                        while (tab[h] != null)
                            h = nextIndex(h, len);
                        tab[h] = e;
                    }
                }
            }
            return i;
        }

Probe cleanup is to clean up the current Entry later. If the value is null, the cleanup will end. It belongs to linear probe cleanup. The main process is as follows:

  1. Starting from the starting position of probing cleaning expired data, clear the data at the starting position first.
  2. Then continue to traverse the array backward,
    (1) If you encounter expired data (key is null), clear the location data and size -.
    (2) If normal data is encountered, recalculate the position of the data in the array. If the calculated position is different from the current position, clear the position data and start from the calculated position to find the slot where the data can be put. The purpose is to store the normal data in the correct position or closer to the correct position as much as possible.
  3. When an empty slot is encountered in the process of subsequent iterations, terminate the detection. In this way, a round of detection cleaning is completed. return the index at the time of termination.

Conclusion: while cleaning up the expired data, this method allows the normal data to be stored in the correct position or closer to the normal position as far as possible.

8.5 heuristic cleanup process for expired key s (cleanSomeSlots method process)

The source code is as follows:

/**
         * Heuristically scan some cells looking for stale entries.
         * This is invoked when either a new element is added, or
         * another stale one has been expunged. It performs a
         * logarithmic number of scans, as a balance between no
         * scanning (fast but retains garbage) and a number of scans
         * proportional to number of elements, that would find all
         * garbage but would cause some insertions to take O(n) time.
         *
         * @param i a position known NOT to hold a stale entry. The
         * scan starts at the element after i.
         *
         * @param n scan control: {@code log2(n)} cells are scanned,
         * unless a stale entry is found, in which case
         * {@code log2(table.length)-1} additional cells are scanned.
         * When called from insertions, this parameter is the number
         * of elements, but when from replaceStaleEntry, it is the
         * table length. (Note: all this could be changed to be either
         * more or less aggressive by weighting n instead of just
         * using straight log n. But this version is simple, fast, and
         * seems to work well.)
         *
         * @return true if any stale entries have been removed.
         */
        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;
        }

This method searches for expired data by tentatively scanning some elements in the array. Calculate the number of attempts according to the passed in parameter n (cycle condition (n > > > = 1)= 0), the parameter i passed in from the initial probe position will iterate backward. If an expired element is just probed, a probe cleaning will be carried out, and the next probe will start from the index returned by the probe cleaning. Returns true if there are expired elements cleaned up, and false if there are none.

8.6 capacity expansion mechanism

The source code is as follows: rehash():

/**
         * Re-pack and/or re-size the table. First scan the entire
         * table removing stale entries. If this doesn't sufficiently
         * shrink the size of the table, double the table size.
         */
        private void rehash() {
            expungeStaleEntries();

            // Use lower threshold for doubling to avoid hysteresis
            if (size >= threshold - threshold / 4)
                resize();
        }

resize():

/**
         * Double the capacity of the table.
         */
        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; // Help the GC
                    } 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;
        }

In threadlocalmap At the end of the set() method, if no data is cleaned up after the heuristic cleaning, and the number of entries in the current hash array has reached the capacity expansion threshold of the list (len*2/3), start the execution:

  1. rehash() logic (no capacity expansion yet): first, probe cleaning will be carried out from the starting position of the table. After cleaning, some Entry data with null key in the table may be cleaned up. Therefore, at this time, determine whether to expand and resize() by judging size > = threshold - threshold / 4, that is, size > = threshold * 3 / 4.
  2. The logic of resize() is (capacity expansion): expand the size of the array to twice the original size, that is, the size of the expanded tab is oldLen * 2, then traverse the old hash table, recalculate the hash position, and then put it into the new tab array. In case of hash conflict, look for the nearest slot with null entry. After traversal, all entry data in oldTab has been put into the new tab. Finally, recalculate the threshold of the next expansion of tab.

8.7 principle of getentry() method

The source code is as follows: getEntry():

/**
         * Get the entry associated with key.  This method
         * itself handles only the fast path: a direct hit of existing
         * key. It otherwise relays to getEntryAfterMiss.  This is
         * designed to maximize performance for direct hits, in part
         * by making this method readily inlinable.
         *
         * @param  key the thread local object
         * @return the entry associated with key, or null if no such
         */
        private Entry getEntry(ThreadLocal<?> key) {
            int i = key.threadLocalHashCode & (table.length - 1);
            Entry e = table[i];
            if (e != null && e.get() == key)
                return e;
            else
                return getEntryAfterMiss(key, i, e);
        }

getEntryAfterMiss():

/**
         * Version of getEntry method for use when key is not found in
         * its direct hash slot.
         *
         * @param  key the thread local object
         * @param  i the table index for key's hash code
         * @param  e the entry at table[i]
         * @return the entry associated with key, or null if no such
         */
        private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
            Entry[] tab = table;
            int len = tab.length;

            while (e != null) {
                ThreadLocal<?> k = e.get();
                if (k == key)
                    return e;
                if (k == null)
                    expungeStaleEntry(i);
                else
                    i = nextIndex(i, len);
                e = tab[i];
            }
            return null;
        }

Calculate the slot position in the hash table by looking up the key value,

  1. If the Entry in the slot is If the key is consistent with the searched key, the value of the Entry will be returned directly; If the location Entry=null, null is returned, indicating that the value corresponding to this key is not found.
  2. If the Entry in the slot position If the key is inconsistent with the key to be found, you need to continue to search iteratively in the future. If you encounter expired data with key=null, conduct a probe type overdue data cleaning. If you encounter an Entry with the same key, you will return it, or if the Entry is null, you will return null, indicating that the value corresponding to this key is not found.

IX InheritableThreadLocal

When we use ThreadLocal, we cannot share the thread copy data created in the parent thread with the child thread in the asynchronous scenario. InheritableThreadLocal can solve this problem.
However, InheritableThreadLocal still has defects. Generally, we use thread pool for asynchronous processing, and InheritableThreadLocal is assigned by init() method in new Thread, and thread pool is the logic of thread reuse, so there will be problems here. Of course, if there is a problem, there will be a solution. Alibaba can solve this problem by opening a TransmittableThreadLocal component, which will not be extended here.

Example code:

public class InheritableThreadLocalDemo {
    public static void main(String[] args) {
        ThreadLocal<String> ThreadLocal = new ThreadLocal<>();
        ThreadLocal<String> inheritableThreadLocal = new InheritableThreadLocal<>();
        inheritableThreadLocal.set("Parent data:inheritableThreadLocal");
        ThreadLocal.set("Parent data:threadLocal");

        //Create a new child thread
        new Thread(new Runnable() {
            @Override
            public void run() {
                //print: the child thread gets the parent ThreadLocal data: null
                System.out.println("Get parent class from child thread ThreadLocal Data:" + ThreadLocal.get());
                //The child thread shares the thread copy data created in the parent thread
                //print: the child thread obtains the parent class inheritableThreadLocal data: parent class data: inheritableThreadLocal
                System.out.println("Get parent class from child thread inheritableThreadLocal Data:" + inheritableThreadLocal.get());
            }
        }).start();
    }
}

Tags: Java Back-end

Posted by manalnor on Fri, 22 Apr 2022 15:54:53 +0300