merging the classpath threadlocal changes

merging the classpath threadlocal changes

[Matthias Klose]

this is a pending patch for some files which are not used in libgcj, and the
files are shadowed except for one new file. Just merging the patch does result
in a build failure, because libgcj picks up this one new file. can makemake.tcl
blacklist this, or should libgcj just get an empty file/class?

  Matthias

Re: merging the classpath threadlocal changes

[Andrew John Hughes]

2008/9/24 Matthias Klose <doko@ubuntu.com>:
> this is a pending patch for some files which are not used in libgcj, and the
> files are shadowed except for one new file. Just merging the patch does result
> in a build failure, because libgcj picks up this one new file. can makemake.tcl
> blacklist this, or should libgcj just get an empty file/class?
>
>  Matthias
>

What is the build failure? I assume the new ThreadLocalMap (or
whatever it's called)
is referring back to ThreadLocal, though the map itself is unused.
Maybe gcj's version
could support the needed methods without using the map itself?
-- 
Andrew :-)

Support Free Java!
Contribute to GNU Classpath and the OpenJDK
http://www.gnu.org/software/classpath
http://openjdk.java.net

PGP Key: 94EFD9D8 (http://subkeys.pgp.net)
Fingerprint: F8EF F1EA 401E 2E60 15FA 7927 142C 2591 94EF D9D8

Re: merging the classpath threadlocal changes

[Matthias Klose]

Andrew John Hughes schrieb:
> 2008/9/24 Matthias Klose <doko@ubuntu.com>:
>> this is a pending patch for some files which are not used in libgcj, and the
>> files are shadowed except for one new file. Just merging the patch does result
>> in a build failure, because libgcj picks up this one new file. can makemake.tcl
>> blacklist this, or should libgcj just get an empty file/class?
>>
>>  Matthias
>>
> 
> What is the build failure? I assume the new ThreadLocalMap (or
> whatever it's called)
> is referring back to ThreadLocal, though the map itself is unused.
> Maybe gcj's version
> could support the needed methods without using the map itself?

Didn't save the build logs. Afaicr these were differences in return and
parameter types for some thread related classes.

Re: merging the classpath threadlocal changes

[Andrew John Hughes]

On 17:07 Sun 28 Sep     , Matthias Klose wrote:
> Andrew John Hughes schrieb:
> > 2008/9/24 Matthias Klose <doko@ubuntu.com>:
> >> this is a pending patch for some files which are not used in libgcj, and the
> >> files are shadowed except for one new file. Just merging the patch does result
> >> in a build failure, because libgcj picks up this one new file. can makemake.tcl
> >> blacklist this, or should libgcj just get an empty file/class?
> >>
> >>  Matthias
> >>
> > 
> > What is the build failure? I assume the new ThreadLocalMap (or
> > whatever it's called)
> > is referring back to ThreadLocal, though the map itself is unused.
> > Maybe gcj's version
> > could support the needed methods without using the map itself?
> 
> Didn't save the build logs. Afaicr these were differences in return and
> parameter types for some thread related classes.

Ok, I'll try a build.  This is probably the only thing I'd like to be
in before pushing back to trunk, as it means it is actually a merge
of Classpath to this point.  The other issues are all related to
gcj support which applies to a lot of stuff already on trunk anyway.
-- 
Andrew :)

Support Free Java!
Contribute to GNU Classpath and the OpenJDK
http://www.gnu.org/software/classpath
http://openjdk.java.net
PGP Key: 94EFD9D8 (http://subkeys.pgp.net)
Fingerprint = F8EF F1EA 401E 2E60 15FA  7927 142C 2591 94EF D9D8

Re: merging the classpath threadlocal changes

[Andrew John Hughes]

[-- Attachment #1: Type: text/plain, Size: 3416 bytes --]

On 17:07 Sun 28 Sep     , Matthias Klose wrote:
> Andrew John Hughes schrieb:
> > 2008/9/24 Matthias Klose <doko@ubuntu.com>:
> >> this is a pending patch for some files which are not used in libgcj, and the
> >> files are shadowed except for one new file. Just merging the patch does result
> >> in a build failure, because libgcj picks up this one new file. can makemake.tcl
> >> blacklist this, or should libgcj just get an empty file/class?
> >>
> >>  Matthias
> >>
> > 
> > What is the build failure? I assume the new ThreadLocalMap (or
> > whatever it's called)
> > is referring back to ThreadLocal, though the map itself is unused.
> > Maybe gcj's version
> > could support the needed methods without using the map itself?
> 
> Didn't save the build logs. Afaicr these were differences in return and
> parameter types for some thread related classes.

Here's the patches just committed (forgot to add the new files at first...).
The failures you were seeing were due to the ThreadLocalMap requiring a hash
value from java.lang.Thread.  Also InheritableThreadLocal is not shadowed,
so the changes in that were causing a build error due to a method that's
in ThreadLocalMap but not WeakIdentityHashMap (inherit).

Although in the best case scenario GCJ uses system thread-local storage
via POSIX threads, it still uses the Classpath map solution in a number of
situations.  First of all, it is always used for set (the native version
is stored first, followed by a call to internalSet(Object)). For get(),
it will only be used if POSIX threads are unavailable on build (the
working implementation is #ifdef on _POSIX_PTHREAD_SEMANTICS),
initialisation fails or the value can't be retrieved.  So although the map
is not usually used as much by gcj, the Classpath version still has a minor
effect (and is thus not as irrelevant as it may first have seemed).

With this patch, I ported the hash value changes to GCJ's java.lang.Thread
and updated internalGet, internalSet and internalRemove to use ThreadLocalMap
instead.  The latter can be dropped if necessary, but it seems sensible to
try and stay close to Classpath where possible.

2008-09-28  Andrew John Hughes  <gnu_andrew@member.fsf.org>

	* classpath/java/lang/ThreadLocalMap.java,
	* java/lang/ThreadLocalMap$Entry.h,
	* java/lang/ThreadLocalMap.h,
	* lib/java/lang/ThreadLocalMap.class,
	* lib/java/lang/ThreadLocalMap$Entry.class:
	Add the new files for the ThreadLocal patch.

2008-09-28  Andrew John Hughes  <gnu_andrew@member.fsf.org>

	* classpath/ChangeLog,
	* classpath/java/lang/InheritableThreadLocal.java,
	* classpath/java/lang/Thread.java,
	* classpath/java/lang/ThreadLocal.java:
	Merge Daniel Frampton's ThreadLocal patch.
	* gcj/javaprims.h: Updated.
	* java/lang/Thread.h: Regenerated.
	* java/lang/Thread.java:
	Replace WeakIdentityHashMap with ThreadLocalMap.
	(getThreadLocals()): Likewise.
	* java/lang/ThreadLocal.h: Regenerated.
	* java/lang/ThreadLocal.java:
	(computeNextHash()): New method.
	(ThreadLocal()): Initialise fastHash.
	(internalGet()): Updated to match Classpath's get().
	(internalSet(Object)): Likewise for set(Object).
	(internalRemove()): Likewise for remove().

-- 
Andrew :)

Support Free Java!
Contribute to GNU Classpath and the OpenJDK
http://www.gnu.org/software/classpath
http://openjdk.java.net
PGP Key: 94EFD9D8 (http://subkeys.pgp.net)
Fingerprint = F8EF F1EA 401E 2E60 15FA  7927 142C 2591 94EF D9D8

[-- Attachment #2: 0.98_merge-06.diff --]
[-- Type: text/plain, Size: 12853 bytes --]

Index: libjava/classpath/ChangeLog
===================================================================
--- libjava/classpath/ChangeLog	(revision 140746)
+++ libjava/classpath/ChangeLog	(working copy)
@@ -1,15 +1,15 @@
 2008-09-14  Andrew John Hughes  <gnu_andrew@member.fsf.org>
 
-        * examples/Makefile.am:
+	* examples/Makefile.am:
         Check lib directly as well as glibj.zip
         for boot classes.
-        * m4/acinclude.m4:
+	* m4/acinclude.m4:
         Only require the class files to be built
         to allow the tools and examples to be built,
         not the installation of glibj.zip.
-        * tools/Makefile.am:
-        Check lib directly as well as glibj.zip
-        for boot classes.
+	* tools/Makefile.am:
+	Check lib directly as well as glibj.zip
+	for boot classes.
 
 2008-09-13  Andrew John Hughes  <gnu_andrew@member.fsf.org>
 
@@ -26,6 +26,16 @@
 	* tools/Makefile.am:
 	Add GCJ rules.
 
+2007-08-23  Daniel Frampton  <zyridium@zyridium.net>
+
+	* AUTHORS: Added.
+	* java/lang/InheritableThreadLocal.java,
+	* java/lang/Thread.java,
+	* java/lang/ThreadLocal.java:
+	Modified to use java.lang.ThreadLocalMap.
+	* java/lang/ThreadLocalMap.java:
+	New cheaper ThreadLocal-specific WeakHashMap.
+
 2008-02-07  Ian Rogers  <ian.rogers@manchester.ac.uk>
 
 	* java/util/zip/ZipEntry.java:
Index: libjava/classpath/lib/java/lang/Thread.class
===================================================================
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream
Index: libjava/classpath/lib/java/lang/ThreadLocal.class
===================================================================
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream
Index: libjava/classpath/lib/java/lang/InheritableThreadLocal.class
===================================================================
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream
Index: libjava/classpath/java/lang/Thread.java
===================================================================
--- libjava/classpath/java/lang/Thread.java	(revision 140746)
+++ libjava/classpath/java/lang/Thread.java	(working copy)
@@ -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;
   }
 
   /** 
Index: libjava/classpath/java/lang/InheritableThreadLocal.java
===================================================================
--- libjava/classpath/java/lang/InheritableThreadLocal.java	(revision 140746)
+++ libjava/classpath/java/lang/InheritableThreadLocal.java	(working copy)
@@ -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);
   }
 }
Index: libjava/classpath/java/lang/ThreadLocal.java
===================================================================
--- libjava/classpath/java/lang/ThreadLocal.java	(revision 140746)
+++ libjava/classpath/java/lang/ThreadLocal.java	(working copy)
@@ -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);
   }
 }
Index: libjava/gcj/javaprims.h
===================================================================
--- libjava/gcj/javaprims.h	(revision 140746)
+++ libjava/gcj/javaprims.h	(working copy)
@@ -240,6 +240,8 @@
       class ThreadDeath;
       class ThreadGroup;
       class ThreadLocal;
+      class ThreadLocalMap;
+      class ThreadLocalMap$Entry;
       class Throwable;
       class Throwable$StaticData;
       class TypeNotPresentException;
Index: libjava/java/lang/Thread.h
===================================================================
--- libjava/java/lang/Thread.h	(revision 140746)
+++ libjava/java/lang/Thread.h	(working copy)
@@ -18,13 +18,6 @@
         class RawData;
         class RawDataManaged;
     }
-    namespace java
-    {
-      namespace util
-      {
-          class WeakIdentityHashMap;
-      }
-    }
   }
 }
 
@@ -100,7 +93,7 @@
   void initialize_native();
   static ::java::lang::String * gen_name();
 public: // actually package-private
-  static ::java::util::Map * getThreadLocals();
+  static ::java::lang::ThreadLocalMap * getThreadLocals();
 public:
   virtual void setUncaughtExceptionHandler(::java::lang::Thread$UncaughtExceptionHandler *);
   virtual ::java::lang::Thread$UncaughtExceptionHandler * getUncaughtExceptionHandler();
@@ -135,7 +128,7 @@
   static jlong totalThreadsCreated;
   static ::java::lang::Thread$UncaughtExceptionHandler * defaultHandler;
 public: // actually package-private
-  ::gnu::java::util::WeakIdentityHashMap * locals;
+  ::java::lang::ThreadLocalMap * locals;
   ::java::lang::Thread$UncaughtExceptionHandler * exceptionHandler;
 private:
   ::java::lang::Object * parkBlocker;
Index: libjava/java/lang/ThreadLocal.h
===================================================================
--- libjava/java/lang/ThreadLocal.h	(revision 140746)
+++ libjava/java/lang/ThreadLocal.h	(working copy)
@@ -21,6 +21,7 @@
 class java::lang::ThreadLocal : public ::java::lang::Object
 {
 
+  jint computeNextHash();
 public:
   ThreadLocal();
 public: // actually protected
@@ -44,7 +45,11 @@
 public: // actually package-private
   static ::java::lang::Object * sentinel;
 private:
-  ::gnu::gcj::RawData * __attribute__((aligned(__alignof__( ::java::lang::Object)))) TLSPointer;
+  static jint nextHashBase;
+public: // actually package-private
+  jint __attribute__((aligned(__alignof__( ::java::lang::Object)))) fastHash;
+private:
+  ::gnu::gcj::RawData * TLSPointer;
 public:
   static ::java::lang::Class class$;
 };
Index: libjava/java/lang/Thread.java
===================================================================
--- libjava/java/lang/Thread.java	(revision 140746)
+++ libjava/java/lang/Thread.java	(working copy)
@@ -160,7 +160,7 @@
   /** Thread local storage. Package accessible for use by
     * InheritableThreadLocal.
     */
-  WeakIdentityHashMap locals;
+  ThreadLocalMap locals;
 
   /** The uncaught exception handler.  */
   UncaughtExceptionHandler exceptionHandler;
@@ -1019,13 +1019,13 @@
   /**
    * 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;
+    ThreadLocalMap locals = thread.locals;
     if (locals == null)
       {
-        locals = thread.locals = new WeakIdentityHashMap();
+        locals = thread.locals = new ThreadLocalMap();
       }
     return locals;
   }
Index: libjava/java/lang/ThreadLocal.java
===================================================================
--- libjava/java/lang/ThreadLocal.java	(revision 140746)
+++ libjava/java/lang/ThreadLocal.java	(working copy)
@@ -96,11 +96,30 @@
   static final Object sentinel = 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()
   {
     constructNative();
+    fastHash = computeNextHash();
   }
 
   /**
@@ -128,16 +147,16 @@
 
   private final Object internalGet()
   {
-    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 == sentinel)
       {
         value = initialValue();
-        map.put(this, (T) (value == null ? sentinel : value));
+        map.set(this, value);
       }
-    return value == (T) sentinel ? null : value;
+    return value;
   }
 
   /**
@@ -152,10 +171,10 @@
 
   private final void internalSet(Object 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);
   }
 
   /**
@@ -167,7 +186,7 @@
 
   private final void internalRemove()
   {
-    Map map = Thread.getThreadLocals();
+    ThreadLocalMap map = Thread.getThreadLocals();
     map.remove(this);
   }
 

[-- Attachment #3: 0.98_merge-07.diff --]
[-- Type: text/plain, Size: 12651 bytes --]

Index: libjava/classpath/lib/java/lang/ThreadLocalMap$Entry.class
===================================================================
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

Property changes on: libjava/classpath/lib/java/lang/ThreadLocalMap$Entry.class
___________________________________________________________________
Added: svn:mime-type
   + application/octet-stream

Index: libjava/classpath/lib/java/lang/ThreadLocalMap.class
===================================================================
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream

Property changes on: libjava/classpath/lib/java/lang/ThreadLocalMap.class
___________________________________________________________________
Added: svn:mime-type
   + application/octet-stream

Index: libjava/classpath/java/lang/ThreadLocalMap.java
===================================================================
--- libjava/classpath/java/lang/ThreadLocalMap.java	(revision 0)
+++ libjava/classpath/java/lang/ThreadLocalMap.java	(revision 0)
@@ -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.sentinel;
+      }
+    }
+  }
+
+  /**
+   * 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));
+              }
+          }
+      }
+  }
+}
Index: libjava/java/lang/ThreadLocalMap$Entry.h
===================================================================
--- libjava/java/lang/ThreadLocalMap$Entry.h	(revision 0)
+++ libjava/java/lang/ThreadLocalMap$Entry.h	(revision 0)
@@ -0,0 +1,21 @@
+
+// DO NOT EDIT THIS FILE - it is machine generated -*- c++ -*-
+
+#ifndef __java_lang_ThreadLocalMap$Entry__
+#define __java_lang_ThreadLocalMap$Entry__
+
+#pragma interface
+
+#include <java/lang/ref/WeakReference.h>
+
+class java::lang::ThreadLocalMap$Entry : public ::java::lang::ref::WeakReference
+{
+
+public: // actually package-private
+  ThreadLocalMap$Entry(::java::lang::ThreadLocal *);
+  ::java::lang::Object * __attribute__((aligned(__alignof__( ::java::lang::ref::WeakReference)))) value;
+public:
+  static ::java::lang::Class class$;
+};
+
+#endif // __java_lang_ThreadLocalMap$Entry__
Index: libjava/java/lang/ThreadLocalMap.h
===================================================================
--- libjava/java/lang/ThreadLocalMap.h	(revision 0)
+++ libjava/java/lang/ThreadLocalMap.h	(revision 0)
@@ -0,0 +1,41 @@
+
+// DO NOT EDIT THIS FILE - it is machine generated -*- c++ -*-
+
+#ifndef __java_lang_ThreadLocalMap__
+#define __java_lang_ThreadLocalMap__
+
+#pragma interface
+
+#include <java/lang/Object.h>
+#include <gcj/array.h>
+
+
+class java::lang::ThreadLocalMap : public ::java::lang::Object
+{
+
+public: // actually package-private
+  ThreadLocalMap();
+private:
+  void newEntryArray(jint);
+  void overflow();
+public:
+  ::java::lang::Object * get(::java::lang::ThreadLocal *);
+  void set(::java::lang::ThreadLocal *, ::java::lang::Object *);
+  void remove(::java::lang::ThreadLocal *);
+public: // actually package-private
+  void clear();
+public:
+  void inherit(::java::lang::ThreadLocalMap *);
+private:
+  static const jint LOG_INITIAL_SIZE = 3;
+  static jfloat MAX_OCCUPANCY;
+  static jfloat TARGET_OCCUPANCY;
+  static ::java::lang::ThreadLocalMap$Entry * deletedEntry;
+  JArray< ::java::lang::ThreadLocalMap$Entry * > * __attribute__((aligned(__alignof__( ::java::lang::Object)))) entries;
+  jint hashMask;
+  jint count;
+public:
+  static ::java::lang::Class class$;
+};
+
+#endif // __java_lang_ThreadLocalMap__