[Fwd: [drlvm]several performance optimizaion can improve situation on Dacapo.jython bench]
|
View:
New views
18 Messages
—
Rating Filter:
Alert me
|
| < Prev | 1 - 2 | Next > |
 |
Re: Jython performance
by Peter Donald-2
::
Rate this Message:
On 8/20/07, Ian Rogers <ian.rogers@...> wrote:
> Eliot Moss wrote: > > Of course the problem with NOT using weak references is that you'll never > > be able to reclaim the String objects in question .... > > > > Yep, we could say that we currently don't care, as we do for class > unloading. I would prefer not to do that. We *should* be caring about class unloading. -- Cheers, Peter Donald ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Jikesrvm-core mailing list Jikesrvm-core@... https://lists.sourceforge.net/lists/listinfo/jikesrvm-core |
|
|
|
|
|
Changes to ThreadLocal
by Ian Rogers (nabble)
::
Rate this Message:
Hi,
the attached patch modifies ThreadLocal to use an array of Objects hung off Thread rather than a weak hash map hung off Thread. On DaCapo's Jython benchmark this can improve the performance of the Jikes RVM by more than 10%. It also improves other DaCapo benchmark performance. GCJ already has a similar mechanism to use pthread thread locals. Regards, Ian diff -u java/lang/InheritableThreadLocal.java java/lang/InheritableThreadLocal.java --- java/lang/InheritableThreadLocal.java 2006-12-10 20:25:44.000000000 +0000 +++ java/lang/InheritableThreadLocal.java 2007-08-20 16:41:23.000000000 +0100 @@ -37,9 +37,7 @@ package java.lang; -import gnu.java.util.WeakIdentityHashMap; - -import java.util.Iterator; +import java.util.Arrays; /** * A ThreadLocal whose value is inherited by child Threads. The value of the @@ -56,6 +54,7 @@ * @author Eric Blake (ebb9@...) * @author Tom Tromey (tromey@...) * @author Andrew John Hughes (gnu_andrew@...) + * @author Ian Rogers (ian.rogers@...) * @see ThreadLocal * @since 1.2 * @status updated to 1.4 @@ -93,29 +92,28 @@ * @param childThread the newly created thread, to inherit from this thread * @see Thread#Thread(ThreadGroup, Runnable, String) */ - static void newChildThread(Thread childThread) + static <T> void newChildThread(Thread childThread) { // The currentThread is the parent of the new thread. Thread parentThread = Thread.currentThread(); - if (parentThread.locals != null) - { - Iterator keys = parentThread.locals.keySet().iterator(); - while (keys.hasNext()) - { - Object key = keys.next(); - if (key instanceof InheritableThreadLocal) - { - InheritableThreadLocal local = (InheritableThreadLocal)key; - Object parentValue = parentThread.locals.get(key); - Object childValue = local.childValue(parentValue == sentinel - ? null : parentValue); - if (childThread.locals == null) - childThread.locals = new WeakIdentityHashMap(); - childThread.locals.put(key, (childValue == null - ? sentinel : childValue)); - } + if (parentThread.locals != null) { + childThread.locals = new Object[parentThread.locals.length]; + Arrays.fill(childThread.locals, sentinel); + for (int i=0; i < parentThread.locals.length; i++) { + ThreadLocal<?> tl = owners.get(i).get(); + if (tl != null && tl instanceof InheritableThreadLocal) { + InheritableThreadLocal local = (InheritableThreadLocal)tl; + Object parentValue = parentThread.locals[i]; + Object childValue; + if (parentValue == sentinel) { + childValue = sentinel; + } else { + childValue = local.childValue(parentValue); } + childThread.locals[i] = childValue; + } } + } } } diff -u java/lang/Thread.java java/lang/Thread.java --- java/lang/Thread.java 2006-12-10 23:06:55.000000000 +0000 +++ java/lang/Thread.java 2007-08-20 16:59:52.000000000 +0100 @@ -39,14 +39,11 @@ package java.lang; import gnu.classpath.VMStackWalker; -import gnu.java.util.WeakIdentityHashMap; import java.lang.management.ManagementFactory; import java.lang.management.ThreadInfo; import java.lang.management.ThreadMXBean; - import java.security.Permission; - import java.util.HashMap; import java.util.Map; @@ -90,6 +87,7 @@ * @author John Keiser * @author Eric Blake (ebb9@...) * @author Andrew John Hughes (gnu_andrew@...) + * @author Ian Rogers (ian.rogers@...) * @see Runnable * @see Runtime#exit(int) * @see #run() @@ -156,10 +154,11 @@ /** The default exception handler. */ private static UncaughtExceptionHandler defaultHandler; - /** Thread local storage. Package accessible for use by - * InheritableThreadLocal. - */ - WeakIdentityHashMap locals; + /** Default value for a thread with no locals. */ + private static final Object[] noLocals = new Object[0]; + + /** Where thread local storage is hung by ThreadLocal. */ + Object[] locals = noLocals; /** The uncaught exception handler. */ UncaughtExceptionHandler exceptionHandler; @@ -1066,20 +1065,6 @@ locals = null; } - /** - * Returns the map used by ThreadLocal to store the thread local values. - */ - static Map getThreadLocals() - { - Thread thread = currentThread(); - Map locals = thread.locals; - if (locals == null) - { - locals = thread.locals = new WeakIdentityHashMap(); - } - return locals; - } - /** * Assigns the given <code>UncaughtExceptionHandler</code> to this * thread. This will then be called if the thread terminates due diff -u java/lang/ThreadLocal.java java/lang/ThreadLocal.java --- java/lang/ThreadLocal.java 2006-12-10 20:25:44.000000000 +0000 +++ java/lang/ThreadLocal.java 2007-08-20 17:19:18.000000000 +0100 @@ -37,8 +37,9 @@ package java.lang; -import java.util.Map; - +import java.lang.ref.WeakReference; +import java.util.ArrayList; +import java.util.Arrays; /** * ThreadLocal objects have a different state associated with every @@ -83,6 +84,7 @@ * * @author Mark Wielaard (mark@...) * @author Eric Blake (ebb9@...) + * @author Ian Rogers (ian.rogers@...) * @since 1.2 * @status updated to 1.5 */ @@ -94,12 +96,46 @@ * InheritableThreadLocal */ static final Object sentinel = new Object(); - + + /** + * List of owners of thread local variables. Weak references allow thread + * locals to be collected when no longer in use. Package visible for use by + * InheritableThreadLocal + */ + static final ArrayList<WeakReference<ThreadLocal<?>>> owners = + new ArrayList<WeakReference<ThreadLocal<?>>>(); + + /** + * Index of thread local within Thread's pool + */ + private final int localIndex; + + /** + * Allocate space within the owners for this thread local. + * @param the thread local we're allocating space for + * @return the slot to hold the thread local + */ + private static int allocateThreadLocal(ThreadLocal<?> tl) { + synchronized(owners) { + int size = owners.size(); + // Look if any slot is now available + for (int i=0; i < size; i++) { + if(owners.get(i).get() == null) { + return i; + } + } + // Add slot at end of array + owners.add(new WeakReference<ThreadLocal<?>>(tl)); + return size; + } + } + /** * Creates a ThreadLocal object without associating any value to it yet. */ public ThreadLocal() { + localIndex = allocateThreadLocal(this); } /** @@ -125,16 +161,21 @@ */ public T get() { - Map<ThreadLocal<T>,T> map = (Map<ThreadLocal<T>,T>) Thread.getThreadLocals(); - // Note that we don't have to synchronize, as only this thread will - // ever modify the map. - T value = map.get(this); - if (value == null) - { - value = initialValue(); - map.put(this, (T) (value == null ? sentinel : value)); - } - return value == (T) sentinel ? null : value; + Thread thread = Thread.currentThread(); + T value; + try { + value = (T)thread.locals[localIndex]; + } catch (ArrayIndexOutOfBoundsException e) { + final int oldLength = thread.locals.length; + thread.locals = Arrays.copyOf(thread.locals, owners.size()); + Arrays.fill(thread.locals, oldLength, thread.locals.length, sentinel); + value = (T)sentinel; + } + if (value == sentinel) { + value = initialValue(); + thread.locals[localIndex] = value; + } + return value; } /** @@ -147,10 +188,17 @@ */ public void set(T value) { - Map map = Thread.getThreadLocals(); // Note that we don't have to synchronize, as only this thread will // ever modify the map. - map.put(this, value == null ? sentinel : value); + Thread thread = Thread.currentThread(); + try { + thread.locals[localIndex] = value; + } catch (ArrayIndexOutOfBoundsException e) { + final int oldLength = thread.locals.length; + thread.locals = Arrays.copyOf(thread.locals, owners.size()); + Arrays.fill(thread.locals, oldLength, thread.locals.length, sentinel); + thread.locals[localIndex] = value; + } } /** @@ -160,7 +208,6 @@ */ public void remove() { - Map map = Thread.getThreadLocals(); - map.remove(this); + set((T)sentinel); } } ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Jikesrvm-core mailing list Jikesrvm-core@... https://lists.sourceforge.net/lists/listinfo/jikesrvm-core |
|
|
Re: [cp-patches] Changes to ThreadLocal
by Jeroen Frijters
::
Rate this Message:
Ian Rogers wrote:
> the attached patch modifies ThreadLocal to use an array of Objects hung > off Thread rather than a weak hash map hung off Thread. On DaCapo's > Jython benchmark this can improve the performance of the Jikes RVM by > more than 10%. It also improves other DaCapo benchmark performance. GCJ > already has a similar mechanism to use pthread thread locals. This patch looks wrong to me: 1) Values are strongly reachable, which means they potentially won't be garbage collected. 2) Value slots are reused without clearing them, which means potential security hole. Regards, Jeroen ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Jikesrvm-core mailing list Jikesrvm-core@... https://lists.sourceforge.net/lists/listinfo/jikesrvm-core |
|
|
Re: [cp-patches] Changes to ThreadLocal
by Ian Rogers (nabble)
::
Rate this Message:
Jeroen Frijters wrote:
> Ian Rogers wrote: > >> the attached patch modifies ThreadLocal to use an array of Objects hung >> off Thread rather than a weak hash map hung off Thread. On DaCapo's >> Jython benchmark this can improve the performance of the Jikes RVM by >> more than 10%. It also improves other DaCapo benchmark performance. GCJ >> already has a similar mechanism to use pthread thread locals. >> > > This patch looks wrong to me: > > 1) Values are strongly reachable, which means they potentially won't be garbage collected. > 2) Value slots are reused without clearing them, which means potential security hole. > > Regards, > Jeroen > > you're of course right. Without reinventing extra indirections in the locals it strikes me that the easiest way to solve these problems is with a finalizer (groan) in the thread local that iterates over every thread reverting the slot location to the sentinel value. I'll test and revise the patch. Regards, Ian ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Jikesrvm-core mailing list Jikesrvm-core@... https://lists.sourceforge.net/lists/listinfo/jikesrvm-core |
|
|
Re: [cp-patches] Changes to ThreadLocal
by Andrew Haley-5
::
Rate this Message:
Ian Rogers writes:
> Jeroen Frijters wrote: > > Ian Rogers wrote: > > > >> the attached patch modifies ThreadLocal to use an array of Objects hung > >> off Thread rather than a weak hash map hung off Thread. On DaCapo's > >> Jython benchmark this can improve the performance of the Jikes RVM by > >> more than 10%. It also improves other DaCapo benchmark performance. GCJ > >> already has a similar mechanism to use pthread thread locals. > >> > > > > This patch looks wrong to me: > > > > 1) Values are strongly reachable, which means they potentially won't be garbage collected. > > 2) Value slots are reused without clearing them, which means potential security hole. > > you're of course right. Without reinventing extra indirections in the > locals it strikes me that the easiest way to solve these problems is > with a finalizer (groan) in the thread local that iterates over every > thread reverting the slot location to the sentinel value. I'll test and > revise the patch. In the gcj pthreads version I keep the WeakIdentityHashMap but I have a look-aside cache that's used by get(). set() is slow by get() is fast. Like this: java::lang::ThreadLocal::get (void) { if (TLSPointer == NULL) return internalGet (); // Slow version, creates the ThreadLocal and updates the HashMap tls_t* tls = (tls_t*)TLSPointer; void *obj = pthread_getspecific(tls->key); // A fast lookup in an area of memory the garbage collector doesn't scan. if (obj) return (::java::lang::Object *)obj; ::java::lang::Object *value = internalGet (); // Slow version again. Garbage collection isn't affected because the use of the HashMap is exactly the same as in the previous Classpath version, and the gc doesn't scan the pthreads memory area used for thread locals. This gets the fast path (the usual case) down to a few instructions. I suppose it's only really an advantage on VMs with very low overhead native calls. Andrew. ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Jikesrvm-core mailing list Jikesrvm-core@... https://lists.sourceforge.net/lists/listinfo/jikesrvm-core |
|
|
Re: [cp-patches] Changes to ThreadLocal
by Ian Rogers (nabble)
::
Rate this Message:
Andrew Haley wrote:
> Ian Rogers writes: > > Jeroen Frijters wrote: > > > Ian Rogers wrote: > > > > > >> the attached patch modifies ThreadLocal to use an array of Objects hung > > >> off Thread rather than a weak hash map hung off Thread. On DaCapo's > > >> Jython benchmark this can improve the performance of the Jikes RVM by > > >> more than 10%. It also improves other DaCapo benchmark performance. GCJ > > >> already has a similar mechanism to use pthread thread locals. > > >> > > > > > > This patch looks wrong to me: > > > > > > 1) Values are strongly reachable, which means they potentially won't be garbage collected. > > > 2) Value slots are reused without clearing them, which means potential security hole. > > > > you're of course right. Without reinventing extra indirections in the > > locals it strikes me that the easiest way to solve these problems is > > with a finalizer (groan) in the thread local that iterates over every > > thread reverting the slot location to the sentinel value. I'll test and > > revise the patch. > > In the gcj pthreads version I keep the WeakIdentityHashMap but I have > a look-aside cache that's used by get(). set() is slow by get() is > fast. Like this: > > java::lang::ThreadLocal::get (void) > { > if (TLSPointer == NULL) > return internalGet (); // Slow version, creates the ThreadLocal and updates the HashMap > > tls_t* tls = (tls_t*)TLSPointer; > void *obj = pthread_getspecific(tls->key); // A fast lookup in an area of memory the garbage collector doesn't scan. > > if (obj) > return (::java::lang::Object *)obj; > > ::java::lang::Object *value = internalGet (); // Slow version again. > > Garbage collection isn't affected because the use of the HashMap is > exactly the same as in the previous Classpath version, and the gc > doesn't scan the pthreads memory area used for thread locals. This > gets the fast path (the usual case) down to a few instructions. I > suppose it's only really an advantage on VMs with very low overhead > native calls. > > Andrew. > here is the revised patch. The get and set methods are deliberately about as short as they can be, they are very very hot in benchmarks and need to be tight, ie read/write the variable and catch cases where the thread local data structure isn't set up yet via a bound check failure. When a thread local is garbage collected a finalizer object runs over every thread making sure we free up the thread local storage and then mark the local as being available again. The use of weak references that must be atomically nulled and not sharing locals avoids a lot of synchronization. I believe the only inefficiency of this code compared to the old code is that the amount of local storage can't shrink as thread locals become unreachable in memory unless new threads are created, and there's a possible issue of fragmentation (similar as to would exist in the hash maps backing store). I think the patch makes a sensible compromise in ignoring this to boost the performance of get and set. For the Jikes RVM on DaCapo's Jython benchmark (large size for 3 iterations) the time taken changes from ~62 seconds to just under 51 seconds. The use of a finalizer object is due to not wanting to over ride the finalize method on thread local, because of potential complications. One bug in the current implementation is that if the thread local overrides hashcode and/or equal it can be made to collide with other thread locals. I think the revised code would also make a good revision for GCJ. It's possible that avoiding the use of pthread calls will boost efficiency, but if not it would provide a more efficient place to look on cache misses. Thanks, Ian diff -u java/lang/InheritableThreadLocal.java java/lang/InheritableThreadLocal.java --- java/lang/InheritableThreadLocal.java 2007-08-21 12:01:24.000000000 +0100 +++ java/lang/InheritableThreadLocal.java 2007-08-21 11:55:49.000000000 +0100 @@ -37,9 +37,9 @@ package java.lang; -import gnu.java.util.WeakIdentityHashMap; - -import java.util.Iterator; +import java.lang.ref.WeakReference; +import java.util.HashMap; +import java.util.Arrays; /** * A ThreadLocal whose value is inherited by child Threads. The value of the @@ -56,12 +56,22 @@ * @author Eric Blake (ebb9@...) * @author Tom Tromey (tromey@...) * @author Andrew John Hughes (gnu_andrew@...) + * @author Ian Rogers (ian.rogers@...) * @see ThreadLocal * @since 1.2 * @status updated to 1.4 */ public class InheritableThreadLocal<T> extends ThreadLocal<T> { + + + /** + * Map of owners of local index to inheritable thread local. Weak references + * allow thread locals to be collected when no longer in use. + */ + private static final HashMap<Integer,WeakReference<InheritableThreadLocal<?>>> + owners = new HashMap<Integer,WeakReference<InheritableThreadLocal<?>>>(); + /** * Creates a new InheritableThreadLocal that has no values associated @@ -69,6 +79,8 @@ */ public InheritableThreadLocal() { + super(); + owners.put(localIndex, new WeakReference<InheritableThreadLocal<?>>(this)); } /** @@ -97,24 +109,25 @@ { // The currentThread is the parent of the new thread. Thread parentThread = Thread.currentThread(); - if (parentThread.locals != null) - { - Iterator keys = parentThread.locals.keySet().iterator(); - while (keys.hasNext()) - { - Object key = keys.next(); - if (key instanceof InheritableThreadLocal) - { - InheritableThreadLocal local = (InheritableThreadLocal)key; - Object parentValue = parentThread.locals.get(key); - Object childValue = local.childValue(parentValue == sentinel - ? null : parentValue); - if (childThread.locals == null) - childThread.locals = new WeakIdentityHashMap(); - childThread.locals.put(key, (childValue == null - ? sentinel : childValue)); - } + if (parentThread.locals != null) { + childThread.locals = new Object[parentThread.locals.length]; + Arrays.fill(childThread.locals, sentinel); + for (int i=0; i < parentThread.locals.length; i++) { + WeakReference ref = owners.get(i); + if (ref != null) { + InheritableThreadLocal local = (InheritableThreadLocal)ref.get(); + if (local != null) { + Object parentValue = parentThread.locals[i]; + Object childValue; + if (parentValue == sentinel) { + childValue = sentinel; + } else { + childValue = local.childValue(parentValue); + } + childThread.locals[i] = childValue; } + } } + } } } diff -u java/lang/Thread.java java/lang/Thread.java --- java/lang/Thread.java 2007-08-21 12:01:24.000000000 +0100 +++ java/lang/Thread.java 2007-08-21 11:55:14.000000000 +0100 @@ -39,14 +39,11 @@ package java.lang; import gnu.classpath.VMStackWalker; -import gnu.java.util.WeakIdentityHashMap; import java.lang.management.ManagementFactory; import java.lang.management.ThreadInfo; import java.lang.management.ThreadMXBean; - import java.security.Permission; - import java.util.HashMap; import java.util.Map; @@ -90,6 +87,7 @@ * @author John Keiser * @author Eric Blake (ebb9@...) * @author Andrew John Hughes (gnu_andrew@...) + * @author Ian Rogers (ian.rogers@...) * @see Runnable * @see Runtime#exit(int) * @see #run() @@ -156,10 +154,11 @@ /** The default exception handler. */ private static UncaughtExceptionHandler defaultHandler; - /** Thread local storage. Package accessible for use by - * InheritableThreadLocal. - */ - WeakIdentityHashMap locals; + /** Default value for a thread with no locals. */ + private static final Object[] noLocals = new Object[0]; + + /** Where thread local storage is hung by ThreadLocal. */ + Object[] locals = noLocals; /** The uncaught exception handler. */ UncaughtExceptionHandler exceptionHandler; @@ -1066,20 +1065,6 @@ locals = null; } - /** - * Returns the map used by ThreadLocal to store the thread local values. - */ - static Map getThreadLocals() - { - Thread thread = currentThread(); - Map locals = thread.locals; - if (locals == null) - { - locals = thread.locals = new WeakIdentityHashMap(); - } - return locals; - } - /** * Assigns the given <code>UncaughtExceptionHandler</code> to this * thread. This will then be called if the thread terminates due diff -u java/lang/ThreadLocal.java java/lang/ThreadLocal.java --- java/lang/ThreadLocal.java 2007-08-21 12:01:24.000000000 +0100 +++ java/lang/ThreadLocal.java 2007-08-21 11:55:30.000000000 +0100 @@ -37,8 +37,8 @@ package java.lang; -import java.util.Map; - +import java.util.Arrays; +import java.util.BitSet; /** * ThreadLocal objects have a different state associated with every @@ -83,6 +83,7 @@ * * @author Mark Wielaard (mark@...) * @author Eric Blake (ebb9@...) + * @author Ian Rogers (ian.rogers@...) * @since 1.2 * @status updated to 1.5 */ @@ -94,12 +95,92 @@ * InheritableThreadLocal */ static final Object sentinel = new Object(); - + + /** + * List of slots owned by thread locals, cleared when the thread local is + * finalized + */ + private static final BitSet ownedSlots = new BitSet(); + + /** + * Index of thread local within Thread's pool. Package visible for use by + * InheritableThreadLocal + */ + final int localIndex; + + /** + * When the thread local gets collected make sure that no local slots have + * live references to values and that the slot is marked as available + */ + private static class FinalizeThreadLocal { + /** Index to free */ + private final int localIndex; + + /** Create class for finalizing the use of a thread local slot */ + FinalizeThreadLocal(int slot) { + localIndex = slot; + } + + /** + * Drop references to locals visible from this slot and free slot for + * reuse + */ + protected void finalize() { + // Create list of threads + ThreadGroup group = Thread.currentThread().group; + while (group.getParent() != null) + group = group.getParent(); + int arraySize = group.activeCount(); + Thread[] threadList = new Thread[arraySize]; + int filled = group.enumerate(threadList); + while (filled == arraySize) + { + arraySize *= 2; + threadList = new Thread[arraySize]; + filled = group.enumerate(threadList); + } + // Iterate over all threads re-initializing slot + for (Thread thread : threadList) { + if (thread.locals.length > localIndex) { + thread.locals[localIndex] = sentinel; + } + } + // Mark slot as available for reuse + synchronized(ownedSlots) { + ownedSlots.clear(localIndex); + } + } + } + + /** + * Sole reference to object whose sole purpose is to make the ownedSlot + * available following collection of a thread local. We don't override + * finalize directly as this would mean sub-classes calling this finalizer. + */ + private final FinalizeThreadLocal finalizer; + + + /** + * Allocate space within the owned slots for this thread local. Once + * allocated a thread local slot will only ever be reused, not reclaimed. + * @param the thread local we're allocating space for + * @return the slot to hold the thread local + */ + private static int allocateThreadLocal(ThreadLocal<?> tl) { + synchronized(ownedSlots) { + int freeSlot = ownedSlots.nextClearBit(0); + ownedSlots.set(freeSlot); + return freeSlot; + } + } + /** * Creates a ThreadLocal object without associating any value to it yet. */ public ThreadLocal() { + localIndex = allocateThreadLocal(this); + finalizer = new FinalizeThreadLocal(localIndex); } /** @@ -125,16 +206,24 @@ */ public T get() { - Map<ThreadLocal<T>,T> map = (Map<ThreadLocal<T>,T>) Thread.getThreadLocals(); - // Note that we don't have to synchronize, as only this thread will - // ever modify the map. - T value = map.get(this); - if (value == null) - { - value = initialValue(); - map.put(this, (T) (value == null ? sentinel : value)); - } - return value == (T) sentinel ? null : value; + Thread thread = Thread.currentThread(); + T value; + try { + // Get value + value = (T)thread.locals[localIndex]; + } catch (ArrayIndexOutOfBoundsException e) { + // Uncommon case: first access to local in this thread. Grow array. + final int oldLength = thread.locals.length; + thread.locals = Arrays.copyOf(thread.locals, ownedSlots.length()); + Arrays.fill(thread.locals, oldLength, thread.locals.length, sentinel); + value = (T)sentinel; + } + // Initialize on first use + if (value == sentinel) { + value = initialValue(); + thread.locals[localIndex] = value; + } + return value; } /** @@ -147,10 +236,19 @@ */ public void set(T value) { - Map map = Thread.getThreadLocals(); // Note that we don't have to synchronize, as only this thread will // ever modify the map. - map.put(this, value == null ? sentinel : value); + Thread thread = Thread.currentThread(); + try { + // Set the value + thread.locals[localIndex] = value; + } catch (ArrayIndexOutOfBoundsException e) { + // Uncommon case: first access to local in this thread. Grow array. + final int oldLength = thread.locals.length; + thread.locals = Arrays.copyOf(thread.locals, ownedSlots.length()); + Arrays.fill(thread.locals, oldLength, thread.locals.length, sentinel); + thread.locals[localIndex] = value; + } } /** @@ -160,7 +258,6 @@ */ public void remove() { - Map map = Thread.getThreadLocals(); - map.remove(this); + set((T)sentinel); } } ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Jikesrvm-core mailing list Jikesrvm-core@... https://lists.sourceforge.net/lists/listinfo/jikesrvm-core |
|
|
Re: [cp-patches] Changes to ThreadLocal
by Jeroen Frijters
::
Rate this Message:
Ian Rogers wrote:
> One bug in the current implementation is that if the thread local > overrides hashcode and/or equal it can be made to collide with other > thread locals. No, it uses an Weak*Identity*HashMap. Regards, Jeroen ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Jikesrvm-core mailing list Jikesrvm-core@... https://lists.sourceforge.net/lists/listinfo/jikesrvm-core |
|
|
Re: [cp-patches] Changes to ThreadLocal
by Jeroen Frijters
::
Rate this Message:
Ian Rogers wrote:
> here is the revised patch. + int arraySize = group.activeCount(); + Thread[] threadList = new Thread[arraySize]; + int filled = group.enumerate(threadList); + while (filled == arraySize) + { + arraySize *= 2; + threadList = new Thread[arraySize]; + filled = group.enumerate(threadList); + } Shouldn't the initial array be arraySize + 1, to avoid always having to enumerate twice? A bigger problem is that the ThreadLocal can be resurrected after the finalizer has run, so you need to either make localIndex in ThreadLocal volatile and set it to -1 in the finalizer, or use a PhantomReference and a ReferenceQueue to do the clean up. Regards, Jeroen ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Jikesrvm-core mailing list Jikesrvm-core@... https://lists.sourceforge.net/lists/listinfo/jikesrvm-core |
|
|
Re: [cp-patches] Changes to ThreadLocal
by Ian Rogers (nabble)
::
Rate this Message:
Jeroen Frijters wrote:
> Ian Rogers wrote: > >> here is the revised patch. >> > > + int arraySize = group.activeCount(); > + Thread[] threadList = new Thread[arraySize]; > + int filled = group.enumerate(threadList); > + while (filled == arraySize) > + { > + arraySize *= 2; > + threadList = new Thread[arraySize]; > + filled = group.enumerate(threadList); > + } > > Shouldn't the initial array be arraySize + 1, to avoid always having to enumerate twice? > This code is taken from Thread.getAllStackTraces so the problem should effect both. > A bigger problem is that the ThreadLocal can be resurrected after the finalizer has run, so you need to either make localIndex in ThreadLocal volatile and set it to -1 in the finalizer, or use a PhantomReference and a ReferenceQueue to do the clean up. > How can then the thread local be resurrected after the finalizer is run? All the references in ThreadLocal and InheritableThreadLocal are weak and will be atomically cleared prior to the finalizer being run. All other references must be dead for the finalizer to have been run. The finalizer doesn't use the ThreadLocal it just clears all references to the slot it used to reference prior to saying that slot can be reused. Given that thread locals normally only die when the VM shuts down or by class unloading, its quite tempting just to ignore the situation of reclaiming their storage - its certainly a much smaller problem than the performance of get and set. Thanks, Ian ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Jikesrvm-core mailing list Jikesrvm-core@... https://lists.sourceforge.net/lists/listinfo/jikesrvm-core |
|
|
Re: [cp-patches] Changes to ThreadLocal
by Jeroen Frijters
::
Rate this Message:
Ian Rogers wrote:
> How can then the thread local be resurrected after the finalizer is > run? > > All the references in ThreadLocal and InheritableThreadLocal are weak > and will be atomically cleared prior to the finalizer being run. All > other references must be dead for the finalizer to have been run. This is not true. Once an object becomes "finalizer reachable" the finalizer can run, but that doesn't mean all references are gone. Any object with a finalizer can still have references to objects that have already been finalized. In its finalizer it will be able to resurrect these objects. This is a well known attack vector and the reason that PhantomReferences were introduced to do post-mortem cleanup. Regards, Jeroen ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Jikesrvm-core mailing list Jikesrvm-core@... https://lists.sourceforge.net/lists/listinfo/jikesrvm-core |
|
|
Re: [cp-patches] Changes to ThreadLocal
by Ian Rogers (nabble)
::
Rate this Message:
Jeroen Frijters wrote:
> This is not true. Once an object becomes "finalizer reachable" the finalizer can run, but that doesn't mean all references are gone. Any object with a finalizer can still have references to objects that have already been finalized. In its finalizer it will be able to resurrect these objects. This is a well known attack vector and the reason that PhantomReferences were introduced to do post-mortem cleanup. > In normal use it would be so hard to do this, but you're right that in theory someone could try to use a thread local after its been finalized in their own finalizer using the finalizer I wrote. I've changed the patch as you suggested to make the localIndex an invalid value after finalization to prevent this attack. It's unfortunate as the change stops localIndex being a prime candidate for final field chasing or caching in a register. This seems better than using a phantom reference and polling a queue though. Thanks, Ian diff -u java/lang/InheritableThreadLocal.java java/lang/InheritableThreadLocal.java --- java/lang/InheritableThreadLocal.java 2007-08-21 12:01:24.000000000 +0100 +++ java/lang/InheritableThreadLocal.java 2007-08-21 11:55:49.000000000 +0100 @@ -37,9 +37,9 @@ package java.lang; -import gnu.java.util.WeakIdentityHashMap; - -import java.util.Iterator; +import java.lang.ref.WeakReference; +import java.util.HashMap; +import java.util.Arrays; /** * A ThreadLocal whose value is inherited by child Threads. The value of the @@ -56,12 +56,22 @@ * @author Eric Blake (ebb9@...) * @author Tom Tromey (tromey@...) * @author Andrew John Hughes (gnu_andrew@...) + * @author Ian Rogers (ian.rogers@...) * @see ThreadLocal * @since 1.2 * @status updated to 1.4 */ public class InheritableThreadLocal<T> extends ThreadLocal<T> { + + + /** + * Map of owners of local index to inheritable thread local. Weak references + * allow thread locals to be collected when no longer in use. + */ + private static final HashMap<Integer,WeakReference<InheritableThreadLocal<?>>> + owners = new HashMap<Integer,WeakReference<InheritableThreadLocal<?>>>(); + /** * Creates a new InheritableThreadLocal that has no values associated @@ -69,6 +79,8 @@ */ public InheritableThreadLocal() { + super(); + owners.put(localIndex, new WeakReference<InheritableThreadLocal<?>>(this)); } /** @@ -97,24 +109,25 @@ { // The currentThread is the parent of the new thread. Thread parentThread = Thread.currentThread(); - if (parentThread.locals != null) - { - Iterator keys = parentThread.locals.keySet().iterator(); - while (keys.hasNext()) - { - Object key = keys.next(); - if (key instanceof InheritableThreadLocal) - { - InheritableThreadLocal local = (InheritableThreadLocal)key; - Object parentValue = parentThread.locals.get(key); - Object childValue = local.childValue(parentValue == sentinel - ? null : parentValue); - if (childThread.locals == null) - childThread.locals = new WeakIdentityHashMap(); - childThread.locals.put(key, (childValue == null - ? sentinel : childValue)); - } + if (parentThread.locals != null) { + childThread.locals = new Object[parentThread.locals.length]; + Arrays.fill(childThread.locals, sentinel); + for (int i=0; i < parentThread.locals.length; i++) { + WeakReference ref = owners.get(i); + if (ref != null) { + InheritableThreadLocal local = (InheritableThreadLocal)ref.get(); + if (local != null) { + Object parentValue = parentThread.locals[i]; + Object childValue; + if (parentValue == sentinel) { + childValue = sentinel; + } else { + childValue = local.childValue(parentValue); + } + childThread.locals[i] = childValue; } + } } + } } } diff -u java/lang/Thread.java java/lang/Thread.java --- java/lang/Thread.java 2007-08-21 12:01:24.000000000 +0100 +++ java/lang/Thread.java 2007-08-21 11:55:14.000000000 +0100 @@ -39,14 +39,11 @@ package java.lang; import gnu.classpath.VMStackWalker; -import gnu.java.util.WeakIdentityHashMap; import java.lang.management.ManagementFactory; import java.lang.management.ThreadInfo; import java.lang.management.ThreadMXBean; - import java.security.Permission; - import java.util.HashMap; import java.util.Map; @@ -90,6 +87,7 @@ * @author John Keiser * @author Eric Blake (ebb9@...) * @author Andrew John Hughes (gnu_andrew@...) + * @author Ian Rogers (ian.rogers@...) * @see Runnable * @see Runtime#exit(int) * @see #run() @@ -156,10 +154,11 @@ /** The default exception handler. */ private static UncaughtExceptionHandler defaultHandler; - /** Thread local storage. Package accessible for use by - * InheritableThreadLocal. - */ - WeakIdentityHashMap locals; + /** Default value for a thread with no locals. */ + private static final Object[] noLocals = new Object[0]; + + /** Where thread local storage is hung by ThreadLocal. */ + Object[] locals = noLocals; /** The uncaught exception handler. */ UncaughtExceptionHandler exceptionHandler; @@ -1066,20 +1065,6 @@ locals = null; } - /** - * Returns the map used by ThreadLocal to store the thread local values. - */ - static Map getThreadLocals() - { - Thread thread = currentThread(); - Map locals = thread.locals; - if (locals == null) - { - locals = thread.locals = new WeakIdentityHashMap(); - } - return locals; - } - /** * Assigns the given <code>UncaughtExceptionHandler</code> to this * thread. This will then be called if the thread terminates due diff -u java/lang/ThreadLocal.java java/lang/ThreadLocal.java --- java/lang/ThreadLocal.java 2006-12-10 20:25:44.000000000 +0000 +++ java/lang/ThreadLocal.java 2007-08-21 14:42:16.000000000 +0100 @@ -37,8 +37,8 @@ package java.lang; -import java.util.Map; - +import java.util.Arrays; +import java.util.BitSet; /** * ThreadLocal objects have a different state associated with every @@ -83,6 +83,7 @@ * * @author Mark Wielaard (mark@...) * @author Eric Blake (ebb9@...) + * @author Ian Rogers (ian.rogers@...) * @since 1.2 * @status updated to 1.5 */ @@ -94,12 +95,79 @@ * InheritableThreadLocal */ static final Object sentinel = new Object(); - + + /** + * List of slots owned by thread locals, cleared when the thread local is + * finalized + */ + private static final BitSet ownedSlots = new BitSet(); + + /** + * Index of thread local within Thread's pool. Package visible for use by + * InheritableThreadLocal + */ + volatile int localIndex; + + /** + * Sole reference to object whose sole purpose is to make the ownedSlot + * available following collection of a thread local. We don't override + * finalize directly as this would mean sub-classes calling this finalizer. + */ + private final Object finalizer = new Object() { + /** + * Drop references to locals visible from this slot and free slot for + * reuse + */ + protected void finalize() { + // Create list of threads + ThreadGroup group = Thread.currentThread().group; + while (group.getParent() != null) + group = group.getParent(); + int arraySize = group.activeCount(); + Thread[] threadList = new Thread[arraySize]; + int filled = group.enumerate(threadList); + while (filled == arraySize) + { + arraySize *= 2; + threadList = new Thread[arraySize]; + filled = group.enumerate(threadList); + } + // Iterate over all threads re-initializing slot + for (Thread thread : threadList) { + if (thread.locals.length > localIndex) { + thread.locals[localIndex] = sentinel; + } + } + // Mark slot as available for reuse + synchronized(ownedSlots) { + ownedSlots.clear(localIndex); + } + // Make local index nonsensical to avoid possible finalizer attack + localIndex = -1; + } + }; + + /** + * Allocate space within the owned slots for this thread local. Once + * allocated a thread local slot will only ever be reused, not reclaimed. + * @param the thread local we're allocating space for + * @return the slot to hold the thread local + */ + private static int allocateThreadLocal(ThreadLocal<?> tl) { + synchronized(ownedSlots) { + int freeSlot = ownedSlots.nextClearBit(0); + ownedSlots.set(freeSlot); + return freeSlot; + } + } + /** * Creates a ThreadLocal object without associating any value to it yet. */ public ThreadLocal() { + localIndex = allocateThreadLocal(this); } /** @@ -125,16 +193,24 @@ */ public T get() { - Map<ThreadLocal<T>,T> map = (Map<ThreadLocal<T>,T>) Thread.getThreadLocals(); - // Note that we don't have to synchronize, as only this thread will - // ever modify the map. - T value = map.get(this); - if (value == null) - { - value = initialValue(); - map.put(this, (T) (value == null ? sentinel : value)); - } - return value == (T) sentinel ? null : value; + Thread thread = Thread.currentThread(); + T value; + try { + // Get value + value = (T)thread.locals[localIndex]; + } catch (ArrayIndexOutOfBoundsException e) { + // Uncommon case: first access to local in this thread. Grow array. + final int oldLength = thread.locals.length; + thread.locals = Arrays.copyOf(thread.locals, ownedSlots.length()); + Arrays.fill(thread.locals, oldLength, thread.locals.length, sentinel); + value = (T)sentinel; + } + // Initialize on first use + if (value == sentinel) { + value = initialValue(); + thread.locals[localIndex] = value; + } + return value; } /** @@ -147,10 +223,19 @@ */ public void set(T value) { - Map map = Thread.getThreadLocals(); // Note that we don't have to synchronize, as only this thread will // ever modify the map. - map.put(this, value == null ? sentinel : value); + Thread thread = Thread.currentThread(); + try { + // Set the value + thread.locals[localIndex] = value; + } catch (ArrayIndexOutOfBoundsException e) { + // Uncommon case: first access to local in this thread. Grow array. + final int oldLength = thread.locals.length; + thread.locals = Arrays.copyOf(thread.locals, ownedSlots.length()); + Arrays.fill(thread.locals, oldLength, thread.locals.length, sentinel); + thread.locals[localIndex] = value; + } } /** @@ -160,7 +245,6 @@ */ public void remove() { - Map map = Thread.getThreadLocals(); - map.remove(this); + set((T)sentinel); } } ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Jikesrvm-core mailing list Jikesrvm-core@... https://lists.sourceforge.net/lists/listinfo/jikesrvm-core |
|
|
Re: [cp-patches] Changes to ThreadLocal
by Ian Rogers (nabble)
::
Rate this Message:
Ian Rogers wrote:
> Jeroen Frijters wrote: >> This is not true. Once an object becomes "finalizer reachable" the >> finalizer can run, but that doesn't mean all references are gone. Any >> object with a finalizer can still have references to objects that >> have already been finalized. In its finalizer it will be able to >> resurrect these objects. This is a well known attack vector and the >> reason that PhantomReferences were introduced to do post-mortem cleanup. >> > > In normal use it would be so hard to do this, but you're right that in > theory someone could try to use a thread local after its been > finalized in their own finalizer using the finalizer I wrote. I've > changed the patch as you suggested to make the localIndex an invalid > value after finalization to prevent this attack. It's unfortunate as > the change stops localIndex being a prime candidate for final field > chasing or caching in a register. This seems better than using a > phantom reference and polling a queue though. The more I think about this the less happy I am about the solution to not make the local index final. What my hope had been was that the locals would be something amenable to caching in a register for a thread. The local index as a final would also be amenable to constant propagation and access to a thread local would, in the best case, be an indexed register load away. The problem with escaping references, in this situation, doesn't effect the Jikes RVM. This is because all weak references that become finalizable are queued onto the finalizer thread. A thread local queued on the finalizer thread would only be able to look at the thread local variables of the finalizer thread. So the scenario of a "secret" thread running then an "untrusted" thread running and stealing data from the "secret" via the thread local can't occur. The "secret" thread would have to put data into the finalizer thread's thread local for the "untrusted" thread then to steal; I can't see how this can occur without the "secret" thread being complicit in trying to leak data to the "untrusted" thread - if the "secret" thread is being complicit with the "untrusted" thread then aren't all bets off? Anyway, this design decision seems to hang off how weak references are finalized. If they are finalized on their own finalizer thread then the final local index design is fine and preferable imo to the volatile design or a weak identity hash map (however cached or stream lined) - I think an indexed register load is the shortest bit of code you could produce for this. If finalizable objects are finalized as part of tearing down threads then a leak is possible and for correctness the volatile should be used. So this comes down to a question of how Classpath using VMs are finalizing objects? One simple idea is to palm off the implementation decision to the VMThread and make the reference implementation use a volatile - this way the Jikes RVM, I believe, can get its optimal code sequence. Currently the whole issue of caching these values in registers for the Jikes RVM is a mute one as optimizations to reduce redundant loads are disabled. Thanks, Ian ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Jikesrvm-core mailing list Jikesrvm-core@... https://lists.sourceforge.net/lists/listinfo/jikesrvm-core |
|
|
Re: [cp-patches] Changes to ThreadLocal
by Jeroen Frijters
::
Rate this Message:
Ian Rogers wrote:
> Anyway, this design decision seems to hang off how weak references are > finalized. If they are finalized on their own finalizer thread then the > final local index design is fine and preferable imo to the volatile > design or a weak identity hash map (however cached or stream lined) - I > think an indexed register load is the shortest bit of code you could > produce for this. If finalizable objects are finalized as part of > tearing down threads then a leak is possible and for correctness the > volatile should be used. So this comes down to a question of how > Classpath using VMs are finalizing objects? No, any VM that implements the spec is vulnerable. Here's an example of a possible attack: class Attacker { static ArrayList<ThreadLocal> resurrected; ArrayList<ThreadLocal> list = new ArrayList<ThreadLocal>(); Attacker() { for (int i = 0; i < 1000; i++) { list.add(new ThreadLocal()); } } protected void finalize() { resurrected = list; } static void attack() { new Attacker(); System.gc(); System.runFinalization(); runSomeHighTrustCodeThatWillAllocateThreadLocal(); for (ThreadLocal t : resurrected) { if (t.get() != null) { System.out.println("We've stolen the object:" + t.get()); } } } } I hope this clarifies the problem with finalizers. A PhantomReference doesn't suffer from this problem, because it only gets enqueued after the object *really* is gone. For another example of this bug in GNU Classpath see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29499 Regards, Jeroen ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Jikesrvm-core mailing list Jikesrvm-core@... https://lists.sourceforge.net/lists/listinfo/jikesrvm-core |
|
|
Re: [cp-patches] Changes to ThreadLocal
by Ian Rogers (nabble)
::
Rate this Message:
Jeroen Frijters wrote:
> No, any VM that implements the spec is vulnerable. Here's an example of a possible attack: > > class Attacker > { > static ArrayList<ThreadLocal> resurrected; > ArrayList<ThreadLocal> list = new ArrayList<ThreadLocal>(); > > Attacker() > { > for (int i = 0; i < 1000; i++) > { > list.add(new ThreadLocal()); > } > } > > protected void finalize() > { > resurrected = list; > } > > static void attack() > { > new Attacker(); > System.gc(); > System.runFinalization(); > runSomeHighTrustCodeThatWillAllocateThreadLocal(); > for (ThreadLocal t : resurrected) > { > if (t.get() != null) > { > System.out.println("We've stolen the object:" + t.get()); > } > } > } > } > > I hope this clarifies the problem with finalizers. A PhantomReference doesn't suffer from this problem, because it only gets enqueued after the object *really* is gone. For another example of this bug in GNU Classpath see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29499 > Thanks Jeroen, it's clear now. The problem with a phantom reference is that when we collect the thread local we should also really make collectable all of the values set to thread locals. A phantom reference won't do this and so introduces a memory leak until something can run over the queue of phantom references freeing all the allocated thread local slots. As you say, we can use phantom references, wouldn't another way be to implement say our own system weak reference, with a guarantee there are no references and weak references to the object? Having a thread that polls a normally empty queue seems undesirable both for this and Classpath bug 29499. Thanks again, Ian ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Jikesrvm-core mailing list Jikesrvm-core@... https://lists.sourceforge.net/lists/listinfo/jikesrvm-core |
|
|
Re: [cp-patches] Changes to ThreadLocal
by Jeroen Frijters
::
Rate this Message:
Ian Rogers wrote:
> Thanks Jeroen, it's clear now. The problem with a phantom reference is > that when we collect the thread local we should also really make > collectable all of the values set to thread locals. A phantom reference > won't do this and so introduces a memory leak until something can run > over the queue of phantom references freeing all the allocated thread > local slots. As you say, we can use phantom references, wouldn't > another way be to implement say our own system weak reference, with a > guarantee there are no references and weak references to the object? > Having a thread that polls a normally empty queue seems undesirable > both for this and Classpath bug 29499. The thread doesn't actually need to poll (ReferenceQueue.remove() is a blocking operation), but burning a thread on this does suck. OTOH, there are a lot of other areas in the class lib that create background threads. I think the best thing would be to have a VM interface that handles the clean up and provide a default implementation that uses PhantomReference and allows VMs to provide a more efficient clean up mechanism. Ideally the mechanism would be flexible enough to also be used for #29499. OpenJDK has the sun.misc.Cleaner class for this. It extends PhantomReference, but it is treated specially by the finalizer thread, so that these aren't actually enqueued but processed by the finalizer thread itself. Regards, Jeroen ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Jikesrvm-core mailing list Jikesrvm-core@... https://lists.sourceforge.net/lists/listinfo/jikesrvm-core |
|
|
|
|
|
Re: [cp-patches] Changes to ThreadLocal
by Ian Rogers (nabble)
::
Rate this Message:
Hi,
here is a revision of Daniel's patch, from Daniel, that revises a bug with InheritableThreadLocals not calling childValue. This bug was found through the JSR 166 TCK, which now passes its thread local tests. Thanks, Ian Daniel Frampton wrote: > In order to tease out where the performance differences were coming > from, I implemented a map specialized for thread locals > (ThreadLocalMap.java) and found that the performance is essentially the > same as the version Ian posted earlier that stores ThreadLocal data in a > per-thread direct indexed array. > > Steve ran the numbers for first and third iteration performance (-1 and > -3). > > http://cs.anu.edu.au/people/Steve.Blackburn/jikesrvm/vole-2007-08-22-Wed > -213259-1.txt > http://cs.anu.edu.au/people/Steve.Blackburn/jikesrvm/vole-2007-08-22-Wed > -213259-3.txt > > All numbers are from JikesRVM and listed from left to right are the > original (WeakIdentityHashMap) the array version suggested by Ian, and > the ThreadLocalMap version. > > The implementation is essentially a map of weak references to values > that are lazily cleaned up as the map is manipulated. I think this is a > good balance of performance and design, but I am open to suggestions. To > allow other VMs to benefit from this I have made all these changes > within classpath (patch attached). > > The job still remains to improve the WeakIdentityHashMap so it does not > perform allocation as it searches the buckets in the fast case for a > simple get(), but I believe that optimizing the ThreadLocal case is > worthwhile regardless as in some benchmarks they are performance > critical. > > Thanks & Regards, > Daniel Frampton. > > --- java/lang/Thread.java 2006-12-11 10:06:55.000000000 +1100 +++ java/lang/Thread.java 2007-08-22 19:20:32.000000000 +1000 @@ -159,7 +159,7 @@ /** Thread local storage. Package accessible for use by * InheritableThreadLocal. */ - WeakIdentityHashMap locals; + final ThreadLocalMap locals; /** The uncaught exception handler. */ UncaughtExceptionHandler exceptionHandler; @@ -367,6 +367,7 @@ this.name = name.toString(); this.runnable = target; this.stacksize = size; + this.locals = new ThreadLocalMap(); synchronized (Thread.class) { @@ -398,6 +399,7 @@ */ Thread(VMThread vmThread, String name, int priority, boolean daemon) { + this.locals = new ThreadLocalMap(); this.vmThread = vmThread; this.runnable = null; if (name == null) @@ -1063,21 +1065,15 @@ { group.removeThread(this); vmThread = null; - locals = null; + locals.clear(); } /** * Returns the map used by ThreadLocal to store the thread local values. */ - static Map getThreadLocals() + static ThreadLocalMap getThreadLocals() { - Thread thread = currentThread(); - Map locals = thread.locals; - if (locals == null) - { - locals = thread.locals = new WeakIdentityHashMap(); - } - return locals; + return currentThread().locals; } /** --- java/lang/ThreadLocal.java 2006-12-11 07:25:44.000000000 +1100 +++ java/lang/ThreadLocal.java 2007-08-22 18:45:24.000000000 +1000 @@ -37,9 +37,6 @@ package java.lang; -import java.util.Map; - - /** * ThreadLocal objects have a different state associated with every * Thread that accesses them. Every access to the ThreadLocal object @@ -93,13 +90,31 @@ * user. Do not expose this to the public. Package visible for use by * InheritableThreadLocal */ - static final Object sentinel = new Object(); + static final Object notFound = new Object(); + + /** + * The base for the computation of the next hash for a thread local. + */ + private static int nextHashBase = 1; + + /** + * Allocate a new hash. + */ + private synchronized int computeNextHash() { + return nextHashBase++ * 6709; + } + + /** + * Hash code computed for ThreadLocalMap + */ + final int fastHash; /** * Creates a ThreadLocal object without associating any value to it yet. */ public ThreadLocal() { + fastHash = computeNextHash(); } /** @@ -125,16 +140,16 @@ */ public T get() { - Map<ThreadLocal<T>,T> map = (Map<ThreadLocal<T>,T>) Thread.getThreadLocals(); + ThreadLocalMap map = Thread.getThreadLocals(); // Note that we don't have to synchronize, as only this thread will // ever modify the map. - T value = map.get(this); - if (value == null) + T value = (T) map.get(this); + if (value == notFound) { value = initialValue(); - map.put(this, (T) (value == null ? sentinel : value)); + map.set(this, value); } - return value == (T) sentinel ? null : value; + return value; } /** @@ -147,10 +162,10 @@ */ public void set(T value) { - Map map = Thread.getThreadLocals(); + ThreadLocalMap map = Thread.getThreadLocals(); // Note that we don't have to synchronize, as only this thread will // ever modify the map. - map.put(this, value == null ? sentinel : value); + map.set(this, value); } /** @@ -160,7 +175,7 @@ */ public void remove() { - Map map = Thread.getThreadLocals(); + ThreadLocalMap map = Thread.getThreadLocals(); map.remove(this); } } --- java/lang/InheritableThreadLocal.java 2006-12-11 07:25:44.000000000 +1100 +++ java/lang/InheritableThreadLocal.java 2007-08-22 19:05:57.000000000 +1000 @@ -37,10 +37,6 @@ package java.lang; -import gnu.java.util.WeakIdentityHashMap; - -import java.util.Iterator; - /** * A ThreadLocal whose value is inherited by child Threads. The value of the * InheritableThreadLocal associated with the (parent) Thread is copied to @@ -97,24 +93,6 @@ { // The currentThread is the parent of the new thread. Thread parentThread = Thread.currentThread(); - if (parentThread.locals != null) - { - Iterator keys = parentThread.locals.keySet().iterator(); - while (keys.hasNext()) - { - Object key = keys.next(); - if (key instanceof InheritableThreadLocal) - { - InheritableThreadLocal local = (InheritableThreadLocal)key; - Object parentValue = parentThread.locals.get(key); - Object childValue = local.childValue(parentValue == sentinel - ? null : parentValue); - if (childThread.locals == null) - childThread.locals = new WeakIdentityHashMap(); - childThread.locals.put(key, (childValue == null - ? sentinel : childValue)); - } - } - } + childThread.locals.inherit(parentThread.locals); } } --- java/lang/ThreadLocalMap.java 2007-04-15 21:49:35.000000000 +1000 +++ java/lang/ThreadLocalMap.java 2007-08-22 19:31:21.000000000 +1000 @@ -0,0 +1,325 @@ +/* ThreadLocal -- a variable with a unique value per thread + Copyright (C) 2000, 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc. + +This file is part of GNU Classpath. + +GNU Classpath is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU Classpath is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Classpath; see the file COPYING. If not, write to the +Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301 USA. + +Linking this library statically or dynamically with other modules is +making a combined work based on this library. Thus, the terms and +conditions of the GNU General Public License cover the whole +combination. + +As a special exception, the copyright holders of this library give you +permission to link this library with independent modules to produce an +executable, regardless of the license terms of these independent +modules, and to copy and distribute the resulting executable under +terms of your choice, provided that you also meet, for each linked +independent module, the terms and conditions of the license of that +module. An independent module is a module which is not derived from +or based on this library. If you modify this library, you may extend +this exception to your version of the library, but you are not +obligated to do so. If you do not wish to do so, delete this +exception statement from your version. */ + +package java.lang; + +import java.lang.ref.WeakReference; + +/** + * ThreadLocalMap is the basic storage for the map of ThreadLocal instance + * to a thread's current value. + * + * Some applications really work out ThreadLocals, leading to this + * optimized implementation. + */ +final class ThreadLocalMap +{ + /** + * The log (base 2) of the initial size of the map + */ + private static final int LOG_INITIAL_SIZE = 3; + + /** + * The maximum occupancy rate (after which we grow) + */ + private static final float MAX_OCCUPANCY = 0.7f; + + /** + * The target occupancy rate. + */ + private static final float TARGET_OCCUPANCY = 0.5f; + + /** + * The deleted entry sentinel value. + */ + private static final Entry deletedEntry = new Entry(null); + + /** + * Constructor + */ + ThreadLocalMap() + { + /* Dummy value to ensure fast path can be optimized */ + entries = new Entry[1]; + hashMask = 0; + count = 0; + } + + /** + * The map entries + */ + private Entry[] entries; + + /** + * Used for start index computation + */ + private int hashMask; + + /** + * The number of entries currently in the map + */ + private int count; + + /** + * Create or grow the table to the specified size. The size must be a + * power of two for the efficient mask/hash computation. + * + * @param newSize The new table size. + */ + private void newEntryArray(int newSize) + { + int mask = newSize - 1; + Entry[] oldEntries = this.entries; + this.entries = new Entry[newSize]; + this.hashMask = mask; + + /* Copy old entries to new table */ + count = 0; + if (oldEntries != null) + { + for(Entry e: oldEntries) + { + if (e != null) + { + ThreadLocal<?> key = e.get(); + if (e != deletedEntry && key != null) + { + for(int i = key.fastHash & mask;; i = (i + 1) & mask) + { + if (entries[i] == null) + { + entries[i] = e; + count++; + break; + } + } + } + } + } + } + } + + /** + * We have run out of space in our locals. We use this as the + * trigger to attempt to find unused slots as ThreadLocals have + * died. If we recover any slots this way then we do not grow. + */ + private void overflow() + { + /* First 'actual' use */ + if (entries.length == 1) + { + newEntryArray(1 << LOG_INITIAL_SIZE); + return; + } + + /* Attempt to recover unused slots */ + int deleted = 0; + for(int i=0; i < entries.length; i++) + { + Entry e = entries[i]; + if (e != null) + { + if (e == deletedEntry) + { + deleted++; + } + else if (e.get() == null) + { + entries[i] = deletedEntry; + deleted++; + } + } + } + + if ((count-deleted) <= (TARGET_OCCUPANCY * entries.length)) + { + /* We currently rehash by simple reallocating into a same-sized table. + * An alternative would be to implement a clever hashing algorithm but + * as this happens infrequently this seems preferred */ + newEntryArray(entries.length); + return; + } + + /* Double the size */ + newEntryArray(entries.length << 1); + } + + /** + * This is the class that is used to refer to a thread local weakly. + * + * As we want to minimize indirections we extend WeakReference. + */ + static final class Entry extends WeakReference<ThreadLocal<?>> { + /** + * The value stored in this slot + */ + Object value; + + /** + * Constructor + */ + Entry(ThreadLocal<?> threadLocal) { + super(threadLocal); + } + } + + /** + * Gets the value associated with the ThreadLocal object for the currently + * executing Thread. If this is the first time the current thread has called + * get(), and it has not already called set(), the sentinel value is returned. + * + * @return the value of the variable in this thread, or sentinel if not present. + */ + public Object get(ThreadLocal<?> key) + { + int mask = this.hashMask; + for(int i = key.fastHash & mask;; i = (i + 1) & mask) { + Entry e = entries[i]; + if (e != null) { + if (e.get() == key) { + return e.value; + } + } else { + return ThreadLocal.notFound; + } + } + } + + /** + * Sets the value associated with the ThreadLocal object for the currently + * executing Thread. This overrides any existing value associated with the + * current Thread and prevents <code>initialValue()</code> from being + * called if this is the first access to this ThreadLocal in this Thread. + * + * @param value the value to set this thread's view of the variable to + */ + public void set(ThreadLocal<?> key, Object value) + { + /* Overflow ? */ + if ((count+1) >= (MAX_OCCUPANCY * entries.length)) + { + overflow(); + } + + /* Set the entry */ + int mask = this.hashMask; + for(int i = key.fastHash & mask;; i = (i + 1) & mask) + { + Entry e = entries[i]; + if (e == null || e == deletedEntry) + { + /* Create entry */ + if (e == null) count++; + entries[i] = e = new Entry(key); + e.value = value; + return; + } + else + { + ThreadLocal<?> entryKey = e.get(); + if (entryKey == null) + { + entries[i] = deletedEntry; + } + else if (entryKey == key) + { + /* Update entry */ + e.value = value; + return; + } + } + } + } + + /** + * Removes the value associated with the ThreadLocal object for the + * currently executing Thread. + * @since 1.5 + */ + public void remove(ThreadLocal<?> key) + { + int mask = this.hashMask; + for(int i = key.fastHash & mask;; i = (i + 1) & mask) + { + Entry e = entries[i]; + if (e != null) + { + ThreadLocal<?> entryKey = e.get(); + if (entryKey != key) + { + if (entryKey == null) { + entries[i] = deletedEntry; + } + continue; + } + else + { + /* Remove from the table */ + entries[i] = deletedEntry; + } + } + return; + } + } + + /** + * Clear out the map. Done once during thread death. + */ + void clear() { + entries = null; + } + + /** + * Inherit all the InheritableThreadLocal instances from the given parent. + * + * @param parentMap The map to inherit from. + */ + public void inherit(ThreadLocalMap parentMap) { + for(Entry e: parentMap.entries) + { + if (e != null && e != deletedEntry) + { + ThreadLocal<?> key = e.get(); + if (key instanceof InheritableThreadLocal) + { + set(key, ((InheritableThreadLocal)key).childValue(e.value)); + } + } + } + } +} ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Jikesrvm-core mailing list Jikesrvm-core@... https://lists.sourceforge.net/lists/listinfo/jikesrvm-core |
classpath95-ThreadLocalMap.patch (19K) | < Prev | 1 - 2 | Next > |
| Free embeddable forum powered by Nabble | Forum Help |
