libhurd-slab/

2003-09-17  Johan Rydberg  <jrydberg@night.trouble.net>

	* slab.h: Add alignment argument.
	* slab.c: Rewrittten.

4 files changed, 258 insertions, 27 deletions

diff --git a/libhurd-slab/ChangeLog b/libhurd-slab/ChangeLog
index 59d4857..3f43903 100644
--- a/libhurd-slab/ChangeLog
+++ b/libhurd-slab/ChangeLog
@@ -1,3 +1,8 @@
+2003-09-17  Johan Rydberg  <jrydberg@night.trouble.net>
+
+	* slab.h: Add alignment argument.
+	* slab.c: Rewrittten.
+
 2003-08-17  Marcus Brinkmann  <marcus@gnu.org>
 
 	* Initial check-in.
diff --git a/libhurd-slab/README b/libhurd-slab/README
index 760a606..4d6e6d4 100644
--- a/libhurd-slab/README
+++ b/libhurd-slab/README
@@ -18,9 +18,8 @@ allocators:
 
 http://citeseer.nj.nec.com/bonwick94slab.html
 
-The current implementation in libhurd-slab is only a dummy
-implementation using malloc and free, though.
-
+The current implementation in libhurd-slab was written by Johan
+Rydberg, <jrydberg@night.trouble.net>.
 
 
 Copyright 2003 Free Software Foundation, Inc.
diff --git a/libhurd-slab/slab.c b/libhurd-slab/slab.c
index 106eb68..8fc9d33 100644
--- a/libhurd-slab/slab.c
+++ b/libhurd-slab/slab.c
@@ -1,5 +1,5 @@
 /* Copyright (C) 2003 Free Software Foundation, Inc.
-   Written by Marcus Brinkmann <marcus@gnu.org>
+   Written by Johan Rydberg.
 
    This file is part of the GNU Hurd.
 
@@ -18,47 +18,218 @@
    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
    02111-1307 USA.  */
 
+/* Known limitation: No memory is returned to the system.  As a
+   side-effect, the destructor will never be called.  */
+
 #if HAVE_CONFIG_H
 #include <config.h>
 #endif
 
 #include <stdlib.h>
 #include <errno.h>
+#include <sys/mman.h>
+#include <assert.h>
+#include <string.h>
+#include <unistd.h>
+#include <pthread.h>
 
-#include <hurd/slab.h>
+#include "slab.h"
 
 
+/* We do just want to initialize the allocator once.  */
+static pthread_once_t __hurd_slab_init = PTHREAD_ONCE_INIT;
+
+/* Number of pages the slab allocator has allocated.  */
+static int __hurd_slab_nr_pages;
+
+/* Internal slab used to allocate hurd_slab_space structures.  */
+static hurd_slab_space_t __hurd_slab_space;
+
+
+/* Buffer control structure.  Lives at the end of an object.  If the
+   buffer is allocated, SLAB points to the slab to which it belongs.
+   If the buffer is free, NEXT points to next buffer on free list.  */
+union hurd_bufctl
+{
+  union hurd_bufctl *next;
+  struct hurd_slab *slab;
+};
+
+
+/* When the allocator needs to grow a cache, it allocates a slab.  A
+   slab consists of one or more pages of memory, split up into equally
+   sized chunks.  */
+struct hurd_slab
+{
+  struct hurd_slab *next;
+  struct hurd_slab *prev;
+
+  /* The reference counter holds the number of allocated chunks in
+     the slab.  When the counter is zero, all chunks are free and
+     the slab can be reqlinquished.  */
+  int refcount;
+
+  /* Single linked list of free buffers in the slab.  */
+  union hurd_bufctl *free_list;
+};
+
+
 /* The type of a slab space.  */
 struct hurd_slab_space
 {
-  /* The size of one object.  */
+  struct hurd_slab *slab_first;
+  struct hurd_slab *slab_last;
+
+  /* In the double linked list of slabs, empty slabs come first,
+     after that there is the slabs that have some buffers allocated,
+     and finally the complete slabs (refcount == 0).  FIRST_FREE
+     points to the first non-empty slab.  */
+  struct hurd_slab *first_free;
+
+  /* For easy checking, this holds the value the reference counter
+     should have for an empty slab.  */
+  int full_refcount;
+
+  /* The size of one object.  Should include possible alignment as
+     well as the size of the bufctl structure.  */
   size_t size;
 
   /* The constructor.  */
   hurd_slab_constructor_t constructor;
 
+  /* Protects this structure, along with all the slabs.  */
+  pthread_mutex_t lock;
+
   /* The destructor.  */
   hurd_slab_destructor_t destructor;
 };
 
+
+/* Insert SLAB into the list of slabs in SPACE.  SLAB is expected to
+   be complete (so it will be inserted at the end).  */
+static void
+insert_slab (struct hurd_slab_space *space, struct hurd_slab *slab)
+{
+  assert (slab->refcount == 0);
+  if (space->slab_first == 0)
+    space->slab_first = space->slab_last = slab;
+  else
+    {
+      space->slab_last->next = slab;
+      slab->prev = space->slab_last;
+      space->slab_last = slab;
+    }
+}
+
+
+/* SPACE has no more memory.  Allocate new slab and insert it into the
+   list, repoint free_list and return possible error.  */
+static error_t
+grow (struct hurd_slab_space *space)
+{
+  struct hurd_slab *new_slab;
+  union hurd_bufctl *bufctl;
+  int nr_objs, i;
+  void *p;
+
+  p = mmap (NULL, getpagesize (), PROT_READ|PROT_WRITE,
+	    MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
+  if (p == MAP_FAILED)
+    return errno;
+  __hurd_slab_nr_pages++;
+
+  new_slab = (p + getpagesize () - sizeof (struct hurd_slab));
+  memset (new_slab, 0, sizeof (struct hurd_slab));
+
+  /* Calculate the number of objects that the page can hold.
+     SPACE->size should be adjusted to handle alignment.  */
+  nr_objs = ((getpagesize () - sizeof (struct hurd_slab))
+	     / space->size);
+  
+  for (i = 0; i < nr_objs; i++, p += space->size)
+    {
+      /* Invoke constructor at object creation time, not when it is
+	 really allocated (for faster allocation).  */
+      if (space->constructor)
+	(*space->constructor) (p);
+
+      /* The most activity is in front of the object, so it is most
+	 likely to be overwritten if a freed buffer gets accessed.
+	 Therefor, put the bufctl structure at the end of the
+	 object.  */
+      bufctl = (p + space->size - sizeof *bufctl);
+      bufctl->next = new_slab->free_list;
+      new_slab->free_list = bufctl;
+    }
+
+  /* Insert slab into the list of available slabs for this cache.  The
+     only time a slab should be allocated is when there is no more
+     buffers, so it is safe to repoint first_free.  */  
+  insert_slab (space, new_slab);
+  space->first_free = new_slab;
+  return 0;
+}
+
+
+/* Initialize the internal slab space used for allocating other slab
+   spaces.  The usual chicken and the egg problem.  */
+static void
+init_allocator (void)
+{
+  __hurd_slab_space = malloc (sizeof (struct hurd_slab_space));
+  __hurd_slab_space->size = (sizeof (struct hurd_slab_space)
+			     + sizeof (union hurd_bufctl));
+  __hurd_slab_space->full_refcount = ((getpagesize () 
+				       - sizeof (struct hurd_slab))
+				      / __hurd_slab_space->size);
+  pthread_mutex_init (&__hurd_slab_space->lock, NULL);
+}
+
 
-/* Create a new slab space with the given object size, constructor and
-   destructor.  */
+/* Create a new slab space with the given object size, alignment,
+   constructor and destructor.  ALIGNMENT can be zero.  */
 error_t
-hurd_slab_create (size_t size,
+hurd_slab_create (size_t size, size_t alignment,
 		  hurd_slab_constructor_t constructor,
 		  hurd_slab_destructor_t destructor,
 		  hurd_slab_space_t *space)
 {
-  *space = malloc (sizeof (struct hurd_slab_space));
+  error_t err;
 
-  if (!*space)
-    return errno;
+  /* If SIZE is so big that one object can not fit into a page, return
+     EINVAL.  FIXME: this doesn't take ALIGNMENT into account.  */
+  if (size > (getpagesize () - sizeof (struct hurd_slab)
+	      - sizeof (union hurd_bufctl)))
+    return EINVAL;
+
+  pthread_once (&__hurd_slab_init, init_allocator);
+
+  if ((err = hurd_slab_alloc (__hurd_slab_space, (void **) space)))
+    return err;
+  memset (*space, 0, sizeof (struct hurd_slab_space));
+
+  err = pthread_mutex_init (&(*space)->lock, NULL);
+  if (err)
+    {
+      hurd_slab_dealloc (__hurd_slab_space, *space);
+      return err;
+    }
 
-  (*space)->size = size;
-  (*space)->constructor;
-  (*space)->destructor;
+  /* The size should include the size of the buffer control
+     structure.  */
+  (*space)->size = size + sizeof (union hurd_bufctl);
 
+  /* If the user has specified any alignment demand, simply round up
+     the size of the buffer to the alignment.  */
+  if (alignment)
+    (*space)->size = (((*space)->size + alignment - 1) & ~(alignment - 1));
+
+  (*space)->constructor = constructor;
+  (*space)->destructor = destructor;
+
+  /* Calculate the number of objects that fit in a slab.  */
+  (*space)->full_refcount 
+    = ((getpagesize () - sizeof (struct hurd_slab)) / (*space)->size);
   return 0;
 }
 
@@ -68,26 +239,82 @@ error_t
 hurd_slab_alloc (hurd_slab_space_t space, void **buffer)
 {
   error_t err;
+  union hurd_bufctl *bufctl;
 
-  *buffer = malloc (space->size);
-  if (!*buffer)
-    return errno;
+  pthread_mutex_lock (&space->lock);
 
-  err = (*space->constructor) (*buffer);
-  if (err)
+  /* If there is no slabs with free buffer, the cache has to be
+     expanded with another slab.  */
+  if (!space->first_free)
     {
-      free (*buffer);
-      return err;
+      err = grow (space);
+      if (err)
+	{
+	  pthread_mutex_unlock (&space->lock);
+	  return err;
+	}
     }
 
+  /* Remove buffer from the free list and update the reference
+     counter.  If the reference counter will hit the top, it is
+     handled at the time of the next allocation.  */
+  bufctl = space->first_free->free_list;
+  space->first_free->free_list = bufctl->next;
+  space->first_free->refcount++;
+  bufctl->slab = space->first_free;
+
+  /* If the reference counter hits the top it means that there has
+     been an allocation boost, otherwise dealloc would have updated
+     the first_free pointer.  Find a slab with free objects.  */
+  if (space->first_free->refcount == space->full_refcount)
+    {
+      struct hurd_slab *new_first = space->slab_first;
+      while (new_first)
+	{
+	  if (new_first->refcount != space->full_refcount)
+	    break;
+	  new_first = new_first->next;
+	}
+      /* If first_free is set to NULL here it means that there are
+	 only empty slabs.  The next call to alloc will allocate a new
+	 slab if there was no call to dealloc in the meantime.  */
+      space->first_free = new_first;
+    }
+  *buffer = ((void *) bufctl) - (space->size - sizeof *bufctl);
+  pthread_mutex_unlock (&space->lock);
   return 0;
 }
 
 
+static inline void
+put_on_slab_list (struct hurd_slab *slab, union hurd_bufctl *bufctl)
+{
+  bufctl->next = slab->free_list;
+  slab->free_list = bufctl;
+  slab->refcount--;
+  assert (slab->refcount >= 0);
+}
+
+
 /* Deallocate the object BUFFER from the slab space SPACE.  */
 void
 hurd_slab_dealloc (hurd_slab_space_t space, void *buffer)
 {
-  (*space->destructor) (buffer);
-  free (buffer);
+  struct hurd_slab *slab;
+  union hurd_bufctl *bufctl;
+
+  pthread_mutex_lock (&space->lock);
+
+  bufctl = (buffer + (space->size - sizeof *bufctl));
+  put_on_slab_list (slab = bufctl->slab, bufctl);
+
+  /* Try to have first_free always pointing at the slab that has the
+     most number of free objects.  So after this deallocation, update
+     the first_free pointer if reference counter drops below the
+     current reference counter of first_free.  */
+  if (!space->first_free 
+      || slab->refcount < space->first_free->refcount)
+    space->first_free = slab;
+
+  pthread_mutex_unlock (&space->lock);
 }
diff --git a/libhurd-slab/slab.h b/libhurd-slab/slab.h
index 2a481e5..aaa35f7 100644
--- a/libhurd-slab/slab.h
+++ b/libhurd-slab/slab.h
@@ -34,9 +34,9 @@ struct hurd_slab_space;
 typedef struct hurd_slab_space *hurd_slab_space_t;
 
 
-/* Create a new slab space with the given object size, constructor and
-   destructor.  */
-error_t hurd_slab_create (size_t size,
+/* Create a new slab space with the given object size, alignment, 
+   constructor and destructor.  ALIGNMENT can be zero.  */
+error_t hurd_slab_create (size_t size, size_t alignment,
 			  hurd_slab_constructor_t constructor,
 			  hurd_slab_destructor_t destructor,
 			  hurd_slab_space_t *space);