diff --git a/sysdeps/htl/pt-destroy-specific.c b/sysdeps/htl/pt-destroy-specific.c
index 7c1acb5068..6d1ad6baed 100644
--- a/sysdeps/htl/pt-destroy-specific.c
+++ b/sysdeps/htl/pt-destroy-specific.c
@@ -29,7 +29,16 @@ __pthread_destroy_specific (struct __pthread *thread)
 
   /* Check if there is any thread specific data.  */
   if (thread->thread_specifics == NULL)
-    return;
+    {
+      for (i = 0; i < PTHREAD_STATIC_KEYS; i++)
+	{
+	  if (thread->static_thread_specifics[i] != NULL)
+	    break;
+	}
+
+      if (i == PTHREAD_STATIC_KEYS)
+	return;
+    }
 
   __pthread_key_lock_ready ();
 
@@ -40,18 +49,32 @@ __pthread_destroy_specific (struct __pthread *thread)
 
       __pthread_mutex_lock (&__pthread_key_lock);
 
-      for (i = 0; i < __pthread_key_count && i < thread->thread_specifics_size;
-	   i++)
+      for (i = 0; i < __pthread_key_count; i++)
 	{
 	  void *value;
 
 	  if (__pthread_key_destructors[i] == PTHREAD_KEY_INVALID)
 	    continue;
 
-	  value = thread->thread_specifics[i];
+	  if (thread->thread_specifics == NULL)
+	    {
+	      if (i >= PTHREAD_STATIC_KEYS)
+		break;
+	      value = thread->static_thread_specifics[i];
+	    }
+	  else
+	    {
+	      if (i >= thread->thread_specifics_size)
+		break;
+	      value = thread->thread_specifics[i];
+	    }
+
 	  if (value != NULL)
 	    {
-	      thread->thread_specifics[i] = 0;
+	      if (thread->thread_specifics == NULL)
+		thread->static_thread_specifics[i] = 0;
+	      else
+		thread->thread_specifics[i] = 0;
 
 	      if (__pthread_key_destructors[i])
 		{
@@ -74,4 +97,6 @@ __pthread_destroy_specific (struct __pthread *thread)
   free (thread->thread_specifics);
   thread->thread_specifics = 0;
   thread->thread_specifics_size = 0;
+  memset (&thread->static_thread_specifics, 0,
+	  sizeof (thread->static_thread_specifics));
 }
diff --git a/sysdeps/htl/pt-getspecific.c b/sysdeps/htl/pt-getspecific.c
index 68a2503563..4d42cba93d 100644
--- a/sysdeps/htl/pt-getspecific.c
+++ b/sysdeps/htl/pt-getspecific.c
@@ -29,6 +29,14 @@ __pthread_getspecific (pthread_key_t key)
     return NULL;
 
   self = _pthread_self ();
+
+  if (self->thread_specifics == NULL)
+    {
+      if (key >= PTHREAD_STATIC_KEYS)
+	return NULL;
+      return self->static_thread_specifics[key];
+    }
+
   if (key >= self->thread_specifics_size)
     return 0;
 
diff --git a/sysdeps/htl/pt-init-specific.c b/sysdeps/htl/pt-init-specific.c
index 8c4d23cb13..ed6c6f2d0c 100644
--- a/sysdeps/htl/pt-init-specific.c
+++ b/sysdeps/htl/pt-init-specific.c
@@ -26,5 +26,7 @@ __pthread_init_specific (struct __pthread *thread)
 {
   thread->thread_specifics = 0;
   thread->thread_specifics_size = 0;
+  memset (&thread->static_thread_specifics, 0,
+	  sizeof (thread->static_thread_specifics));
   return 0;
 }
diff --git a/sysdeps/htl/pt-key-create.c b/sysdeps/htl/pt-key-create.c
index 51c0ef72b8..b7057434e3 100644
--- a/sysdeps/htl/pt-key-create.c
+++ b/sysdeps/htl/pt-key-create.c
@@ -26,10 +26,11 @@
 pthread_mutex_t __pthread_key_lock;
 pthread_once_t __pthread_key_once = PTHREAD_ONCE_INIT;
 
-void (**__pthread_key_destructors) (void *arg);
-int __pthread_key_size;
+void (*__pthread_static_key_destructors [PTHREAD_STATIC_KEYS]) (void *arg);
+void (**__pthread_key_destructors) (void *arg) = __pthread_static_key_destructors;
+int __pthread_key_size = PTHREAD_STATIC_KEYS;
 int __pthread_key_count;
-int __pthread_key_invalid_count;
+int __pthread_key_invalid_count = PTHREAD_STATIC_KEYS;
 
 int
 __pthread_key_create (pthread_key_t *key, void (*destructor) (void *))
@@ -80,13 +81,21 @@ do_search:
 	void *t;
 	int newsize;
 
-	if (__pthread_key_size == 0)
-	  newsize = 8;
+	newsize = __pthread_key_size * 2;
+
+	if (__pthread_key_destructors == __pthread_static_key_destructors)
+	  {
+	    /* We were still using the static array.  Switch to dynamic.  */
+	    t = malloc (newsize * sizeof (*__pthread_key_destructors));
+
+	    if (t != NULL)
+	      memcpy (t, __pthread_key_destructors,
+		      __pthread_key_size * sizeof (*__pthread_key_destructors));
+	  }
 	else
-	  newsize = __pthread_key_size * 2;
+	  t = realloc (__pthread_key_destructors,
+		       newsize * sizeof (*__pthread_key_destructors));
 
-	t = realloc (__pthread_key_destructors,
-		     newsize * sizeof (*__pthread_key_destructors));
 	if (t == NULL)
 	  {
 	    __pthread_mutex_unlock (&__pthread_key_lock);
diff --git a/sysdeps/htl/pt-key-delete.c b/sysdeps/htl/pt-key-delete.c
index ce77a573c2..6d128d2aaf 100644
--- a/sysdeps/htl/pt-key-delete.c
+++ b/sysdeps/htl/pt-key-delete.c
@@ -51,8 +51,16 @@ __pthread_key_delete (pthread_key_t key)
 
 	  /* Just remove the key, no need to care whether it was
 	     already there. */
-	  if (key < t->thread_specifics_size)
-	    t->thread_specifics[key] = 0;
+	  if (t->thread_specifics == NULL)
+	    {
+	      if (key < PTHREAD_STATIC_KEYS)
+		t->static_thread_specifics[key] = 0;
+	    }
+	  else
+	    {
+	      if (key < t->thread_specifics_size)
+		t->thread_specifics[key] = 0;
+	    }
 	}
       __libc_rwlock_unlock (GL (dl_pthread_threads_lock));
     }
diff --git a/sysdeps/htl/pt-key.h b/sysdeps/htl/pt-key.h
index 262006de9f..047b7e24ba 100644
--- a/sysdeps/htl/pt-key.h
+++ b/sysdeps/htl/pt-key.h
@@ -20,9 +20,14 @@
 #include <libc-lockP.h>
 #include <pthreadP.h>
 
+/* When using e.g. jemalloc, we need to be able to create and use keys before
+   being able to allocate.  */
+#define PTHREAD_STATIC_KEYS 4
+
 #define PTHREAD_KEY_MEMBERS \
   void **thread_specifics;		/* This is only resized by the thread, and always growing */ \
-  unsigned thread_specifics_size;	/* Number of entries in thread_specifics */
+  unsigned thread_specifics_size;	/* Number of entries in thread_specifics */ \
+  void *static_thread_specifics[PTHREAD_STATIC_KEYS];	/* Static storage for a few entries */
 
 #define PTHREAD_KEY_INVALID (void *) (-1)
 
diff --git a/sysdeps/htl/pt-setspecific.c b/sysdeps/htl/pt-setspecific.c
index 2b9a89dc70..30550e09c7 100644
--- a/sysdeps/htl/pt-setspecific.c
+++ b/sysdeps/htl/pt-setspecific.c
@@ -28,12 +28,34 @@ __pthread_setspecific (pthread_key_t key, const void *value)
   if (key < 0 || key >= __pthread_key_count)
     return EINVAL;
 
+  if (self->thread_specifics == NULL)
+    {
+      if (key < PTHREAD_STATIC_KEYS)
+	{
+	  self->static_thread_specifics[key] = (void *) value;
+	  return 0;
+	}
+    }
+
   if (key >= self->thread_specifics_size)
     {
       /* Amortize reallocation cost.  */
       int newsize = 2 * key + 1;
-      void **new = realloc (self->thread_specifics,
-			    newsize * sizeof (new[0]));
+      void **new;
+
+      if (self->thread_specifics == NULL)
+	{
+	  self->thread_specifics_size = PTHREAD_STATIC_KEYS;
+	  new = malloc (newsize * sizeof (new[0]));
+	  if (new != NULL)
+	    memcpy (new, self->static_thread_specifics,
+		    PTHREAD_STATIC_KEYS * sizeof (new[0]));
+	}
+      else
+	{
+	  new = realloc (self->thread_specifics,
+			 newsize * sizeof (new[0]));
+	}
       if (new == NULL)
 	return ENOMEM;
 
