hurd-l4 ./TODO doc/ipc.tex libhurd-cap/cap.c li...

[Marcus Brinkmann]

CVSROOT:        /cvsroot/hurd
Module name:    hurd-l4
Branch:         
Changes by:     Marcus Brinkmann <address@hidden>       03/09/17 11:12:22

Modified files:
        .              : TODO 
        doc            : ipc.tex 
        libhurd-cap    : cap.c 
        libhurd-slab   : ChangeLog README slab.c slab.h 

Log message:
        libhurd-slab/
        2003-09-17  Johan Rydberg  <address@hidden>
        
        * slab.h: Add alignment argument.
        * slab.c: Rewrittten.

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/hurd/hurd-l4/TODO.diff?tr1=1.6&tr2=1.7&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/hurd/hurd-l4/doc/ipc.tex.diff?tr1=1.2&tr2=1.3&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/hurd/hurd-l4/libhurd-cap/cap.c.diff?tr1=1.4&tr2=1.5&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/hurd/hurd-l4/libhurd-slab/ChangeLog.diff?tr1=1.2&tr2=1.3&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/hurd/hurd-l4/libhurd-slab/README.diff?tr1=1.2&tr2=1.3&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/hurd/hurd-l4/libhurd-slab/slab.c.diff?tr1=1.4&tr2=1.5&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/hurd/hurd-l4/libhurd-slab/slab.h.diff?tr1=1.2&tr2=1.3&r1=text&r2=text

Patches:
Index: hurd-l4/TODO
diff -u hurd-l4/TODO:1.6 hurd-l4/TODO:1.7
--- hurd-l4/TODO:1.6    Tue Sep 16 21:23:22 2003
+++ hurd-l4/TODO        Wed Sep 17 11:12:21 2003
@@ -27,8 +27,7 @@
 
 
 * libhurd-slab
-** This is only a dummy implementation (Johan Rydberg is working on a
-   real one).
+** Provide a way to release resources.
 ** Ideally this would be a feature in glibc.
 
 
Index: hurd-l4/doc/ipc.tex
diff -u hurd-l4/doc/ipc.tex:1.2 hurd-l4/doc/ipc.tex:1.3
--- hurd-l4/doc/ipc.tex:1.2     Sun Sep  7 18:24:06 2003
+++ hurd-l4/doc/ipc.tex Wed Sep 17 11:12:22 2003
@@ -1,7 +1,7 @@
 \chapter{Inter-process communication (IPC)}
 \label{ipc}
 
-The Hurd requires a capability system.  Capabilities are used to proof
+The Hurd requires a capability system.  Capabilities are used to prove
 your identity to other servers (authentication), and access
 server-side implemented objects like devices, files, directories,
 terminals, and other things.  The server can use a capability for
Index: hurd-l4/libhurd-cap/cap.c
diff -u hurd-l4/libhurd-cap/cap.c:1.4 hurd-l4/libhurd-cap/cap.c:1.5
--- hurd-l4/libhurd-cap/cap.c:1.4       Mon Sep 15 14:09:45 2003
+++ hurd-l4/libhurd-cap/cap.c   Wed Sep 17 11:12:22 2003
@@ -75,7 +75,7 @@
 error_t
 hurd_cap_init (void)
 {
-  return hurd_slab_create (sizeof (struct hurd_cap),
+  return hurd_slab_create (sizeof (struct hurd_cap), 0,
                           cap_constructor, cap_destructor, &cap_space);
 }
 
Index: hurd-l4/libhurd-slab/ChangeLog
diff -u hurd-l4/libhurd-slab/ChangeLog:1.2 hurd-l4/libhurd-slab/ChangeLog:1.3
--- hurd-l4/libhurd-slab/ChangeLog:1.2  Sun Aug 17 01:25:12 2003
+++ hurd-l4/libhurd-slab/ChangeLog      Wed Sep 17 11:12:22 2003
@@ -1,3 +1,8 @@
+2003-09-17  Johan Rydberg  <address@hidden>
+
+       * slab.h: Add alignment argument.
+       * slab.c: Rewrittten.
+
 2003-08-17  Marcus Brinkmann  <address@hidden>
 
        * Initial check-in.
Index: hurd-l4/libhurd-slab/README
diff -u hurd-l4/libhurd-slab/README:1.2 hurd-l4/libhurd-slab/README:1.3
--- hurd-l4/libhurd-slab/README:1.2     Sun Aug 17 01:25:12 2003
+++ hurd-l4/libhurd-slab/README Wed Sep 17 11:12:22 2003
@@ -18,9 +18,8 @@
 
 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, <address@hidden>.
 
 
 Copyright 2003 Free Software Foundation, Inc.
Index: hurd-l4/libhurd-slab/slab.c
diff -u hurd-l4/libhurd-slab/slab.c:1.4 hurd-l4/libhurd-slab/slab.c:1.5
--- hurd-l4/libhurd-slab/slab.c:1.4     Mon Sep  8 17:07:51 2003
+++ hurd-l4/libhurd-slab/slab.c Wed Sep 17 11:12:22 2003
@@ -1,5 +1,5 @@
 /* Copyright (C) 2003 Free Software Foundation, Inc.
-   Written by Marcus Brinkmann <address@hidden>
+   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));
 
-  (*space)->size = size;
-  (*space)->constructor;
-  (*space)->destructor;
+  err = pthread_mutex_init (&(*space)->lock, NULL);
+  if (err)
+    {
+      hurd_slab_dealloc (__hurd_slab_space, *space);
+      return err;
+    }
 
+  /* 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 @@
 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);
 }
Index: hurd-l4/libhurd-slab/slab.h
diff -u hurd-l4/libhurd-slab/slab.h:1.2 hurd-l4/libhurd-slab/slab.h:1.3
--- hurd-l4/libhurd-slab/slab.h:1.2     Sat Aug 16 17:11:00 2003
+++ hurd-l4/libhurd-slab/slab.h Wed Sep 17 11:12:22 2003
@@ -34,9 +34,9 @@
 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);