Bugzilla bug 97485: added the zone allocator (implemented by Nelson

Bolyard).
Modified files: primpl.h prmem.c prinit.c ptthread.c

4 files changed, 378 insertions, 0 deletions

diff --git a/pr/include/private/primpl.h b/pr/include/private/primpl.h
index 30ddf5c5..8501c0e0 100644
--- a/pr/include/private/primpl.h
+++ b/pr/include/private/primpl.h
@@ -1792,6 +1792,23 @@ extern PRFileDesc *_pr_stdin;
 extern PRFileDesc *_pr_stdout;
 extern PRFileDesc *_pr_stderr;
 
+/* Zone allocator */
+/*
+** The zone allocator code has hardcoded pthread types and
+** functions, so it can only be used in the pthreads version.
+** This can be fixed by replacing the hardcoded pthread types
+** and functions with macros that expand to the native thread
+** types and functions on each platform.
+*/
+#if defined(_PR_PTHREADS)
+#define _PR_ZONE_ALLOCATOR
+#endif
+
+#ifdef _PR_ZONE_ALLOCATOR
+extern void _PR_InitZones(void);
+extern void _PR_DestroyZones(void);
+#endif
+
 /* Overriding malloc, free, etc. */
 #if !defined(_PR_NO_PREEMPT) && defined(XP_UNIX) \
         && !defined(_PR_PTHREADS) && !defined(_PR_GLOBAL_THREADS_ONLY) \
diff --git a/pr/src/malloc/prmem.c b/pr/src/malloc/prmem.c
index e5e1cedd..0a70b439 100644
--- a/pr/src/malloc/prmem.c
+++ b/pr/src/malloc/prmem.c
@@ -38,6 +38,358 @@
 
 #include "primpl.h"
 
+#ifdef _PR_ZONE_ALLOCATOR
+
+/*
+** The zone allocator code must use native mutexes and cannot
+** use PRLocks because PR_NewLock calls PR_Calloc, resulting
+** in cyclic dependency of initialization.
+*/
+
+#include <string.h>	
+
+union memBlkHdrUn;
+
+typedef struct MemoryZoneStr {
+    union memBlkHdrUn    *head;         /* free list */
+    pthread_mutex_t       lock;
+    size_t                blockSize;    /* size of blocks on this free list */
+    PRUint32              locked;       /* current state of lock */
+    PRUint32              contention;   /* counter: had to wait for lock */
+    PRUint32              hits;         /* allocated from free list */
+    PRUint32              misses;       /* had to call malloc */
+    PRUint32              elements;     /* on free list */
+} MemoryZone;
+
+typedef union memBlkHdrUn {
+    unsigned char filler[48];  /* fix the size of this beast */
+    struct memBlkHdrStr {
+        union memBlkHdrUn    *next;
+        MemoryZone           *zone;
+        size_t                blockSize;
+        size_t                requestedSize;
+        PRUint32              magic;
+    } s;
+} MemBlockHdr;
+
+#define MEM_ZONES     7
+#define THREAD_POOLS 11  /* prime number for modulus */
+#define ZONE_MAGIC  0x0BADC0DE
+
+static MemoryZone zones[MEM_ZONES][THREAD_POOLS];
+
+static PRBool use_zone_allocator = PR_FALSE;
+
+static void pr_ZoneFree(void *ptr);
+
+void
+_PR_DestroyZones(void)
+{   
+    int i, j;
+
+    if (!use_zone_allocator)
+        return;
+    
+    for (j = 0; j < THREAD_POOLS; j++) {
+        for (i = 0; i < MEM_ZONES; i++) {
+            MemoryZone *mz = &zones[i][j];
+            pthread_mutex_destroy(&mz->lock);
+            while (mz->head) {
+                MemBlockHdr *hdr = mz->head;
+                mz->head = hdr->s.next;  /* unlink it */
+                pr_ZoneFree(hdr);
+                mz->elements--;
+            }
+        }
+    } 
+} 
+
+void
+_PR_InitZones(void)
+{
+    int i, j;
+    char *envp;
+
+    if (envp = getenv("NSPR_USE_ZONE_ALLOCATOR")) {
+        use_zone_allocator = (atoi(envp) == 1);
+    }
+
+    if (!use_zone_allocator)
+        return;
+
+    for (j = 0; j < THREAD_POOLS; j++) { 
+        for (i = 0; i < MEM_ZONES; i++) {
+            MemoryZone *mz = &zones[i][j];
+            int rv = pthread_mutex_init(&mz->lock, NULL);
+            PR_ASSERT(0 == rv);
+            if (rv != 0) {
+                goto loser;
+            } 
+            mz->blockSize = 16 << ( 2 * i);
+        }
+    }
+    return;
+
+loser:
+    _PR_DestroyZones();
+    return;
+}
+
+PR_IMPLEMENT(void)
+PR_FPrintZoneStats(PRFileDesc *debug_out)
+{
+    int i, j;
+
+    for (j = 0; j < THREAD_POOLS; j++) {
+        for (i = 0; i < MEM_ZONES; i++) {
+            MemoryZone   *mz   = &zones[i][j];
+            MemoryZone    zone = *mz;
+            if (zone.elements || zone.misses || zone.hits) {
+                PR_fprintf(debug_out,
+"pool: %d, zone: %d, size: %d, free: %d, hit: %d, miss: %d, contend: %d\n",
+                    j, i, zone.blockSize, zone.elements,
+                    zone.hits, zone.misses, zone.contention);
+            }
+	}
+    }
+}
+
+static void *
+pr_ZoneMalloc(PRUint32 size)
+{
+    void         *rv;
+    unsigned int  zone;
+    size_t        blockSize;
+    MemBlockHdr  *mb, *mt;
+    MemoryZone   *mz;
+
+    /* Always allocate a non-zero amount of bytes */
+    if (size < 1) {
+        size = 1;
+    }
+    for (zone = 0, blockSize = 16; zone < MEM_ZONES; ++zone, blockSize <<= 2) {
+        if (size <= blockSize) {
+            break;
+        }
+    }
+    if (zone < MEM_ZONES) {
+        pthread_t me = pthread_self();
+        unsigned int pool = (ptrdiff_t)me % THREAD_POOLS;
+        PRUint32     wasLocked;
+        mz = &zones[zone][pool];
+        wasLocked = mz->locked;
+        pthread_mutex_lock(&mz->lock);
+        mz->locked = 1;
+        if (wasLocked)
+            mz->contention++;
+        if (mz->head) {
+            mb = mz->head;
+            PR_ASSERT(mb->s.magic == ZONE_MAGIC);
+            PR_ASSERT(mb->s.zone  == mz);
+            PR_ASSERT(mb->s.blockSize == blockSize);
+            PR_ASSERT(mz->blockSize == blockSize);
+
+            mt = (MemBlockHdr *)(((char *)(mb + 1)) + blockSize);
+            PR_ASSERT(mt->s.magic == ZONE_MAGIC);
+            PR_ASSERT(mt->s.zone  == mz);
+            PR_ASSERT(mt->s.blockSize == blockSize);
+
+            mz->hits++;
+            mz->elements--;
+            mz->head = mb->s.next;    /* take off free list */
+            mz->locked = 0;
+            pthread_mutex_unlock(&mz->lock);
+
+            mt->s.next          = mb->s.next          = NULL;
+            mt->s.requestedSize = mb->s.requestedSize = size;
+
+            rv = (void *)(mb + 1);
+            return rv;
+        }
+
+        mz->misses++;
+        mz->locked = 0;
+        pthread_mutex_unlock(&mz->lock);
+
+        mb = (MemBlockHdr *)malloc(blockSize + 2 * (sizeof *mb));
+        if (!mb) {
+            PR_SetError(PR_OUT_OF_MEMORY_ERROR, 0);
+            return NULL;
+        }
+        mb->s.next          = NULL;
+        mb->s.zone          = mz;
+        mb->s.magic         = ZONE_MAGIC;
+        mb->s.blockSize     = blockSize;
+        mb->s.requestedSize = size;
+
+        mt = (MemBlockHdr *)(((char *)(mb + 1)) + blockSize);
+        memcpy(mt, mb, sizeof *mb);
+
+        rv = (void *)(mb + 1);
+        return rv;
+    }
+
+    /* size was too big.  Create a block with no zone */
+    blockSize = (size & 15) ? size + 16 - (size & 15) : size;
+    mb = (MemBlockHdr *)malloc(blockSize + 2 * (sizeof *mb));
+    if (!mb) {
+        PR_SetError(PR_OUT_OF_MEMORY_ERROR, 0);
+        return NULL;
+    }
+    mb->s.next          = NULL;
+    mb->s.zone          = NULL;
+    mb->s.magic         = ZONE_MAGIC;
+    mb->s.blockSize     = blockSize;
+    mb->s.requestedSize = size;
+
+    mt = (MemBlockHdr *)(((char *)(mb + 1)) + blockSize);
+    memcpy(mt, mb, sizeof *mb);
+
+    rv = (void *)(mb + 1);
+    return rv;
+}
+
+
+static void *
+pr_ZoneCalloc(PRUint32 nelem, PRUint32 elsize)
+{
+    PRUint32 size = nelem * elsize;
+    void *p = pr_ZoneMalloc(size);
+    if (p) {
+        memset(p, 0, size);
+    }
+    return p;
+}
+
+static void *
+pr_ZoneRealloc(void *oldptr, PRUint32 bytes)
+{
+    void         *rv;
+    MemBlockHdr  *mb;
+    int           ours;
+    MemBlockHdr   phony;
+
+    if (!oldptr)
+        return pr_ZoneMalloc(bytes);
+    mb = (MemBlockHdr *)((char *)oldptr - (sizeof *mb));
+    PR_ASSERT(mb->s.magic == ZONE_MAGIC);
+    if (mb->s.magic != ZONE_MAGIC) {
+        /* Maybe this just came from ordinary malloc */
+        /* We don't know how big it is.  But we can fix that. */
+        oldptr = realloc(oldptr, bytes);
+        if (!oldptr) {
+            if (bytes) {
+                PR_SetError(PR_OUT_OF_MEMORY_ERROR, 0);
+                return oldptr;
+            }
+        }
+        phony.s.requestedSize = bytes;
+        mb = &phony;
+        ours = 0;
+    } else {
+        size_t blockSize = mb->s.blockSize;
+        MemBlockHdr *mt = (MemBlockHdr *)(((char *)(mb + 1)) + blockSize);
+
+        PR_ASSERT(mt->s.magic == ZONE_MAGIC);
+        PR_ASSERT(mt->s.zone  == mb->s.zone);
+        PR_ASSERT(mt->s.blockSize == blockSize);
+	
+        if (bytes <= blockSize) {
+            /* The block is already big enough. */
+            mt->s.requestedSize = mb->s.requestedSize = bytes;
+            return oldptr;
+        }
+        ours = 1;
+    }
+    
+    rv = pr_ZoneMalloc(bytes);
+    if (rv) {
+        if (oldptr && mb->s.requestedSize)
+            memcpy(rv, oldptr, mb->s.requestedSize);
+        if (ours)
+            pr_ZoneFree(oldptr);
+        else if (oldptr)
+            free(oldptr);
+    }
+    return rv;
+}
+
+static void
+pr_ZoneFree(void *ptr)
+{
+    MemBlockHdr  *mb, *mt;
+    MemoryZone   *mz;
+    size_t        blockSize;
+    PRUint32      wasLocked;
+
+    if (!ptr)
+        return;
+
+    mb = (MemBlockHdr *)((char *)ptr - (sizeof *mb));
+
+    if (mb->s.magic != ZONE_MAGIC) {
+        /* maybe this came from ordinary malloc */
+        free(ptr);
+        return;
+    }
+
+    blockSize = mb->s.blockSize;
+    mz        = mb->s.zone;
+    mt = (MemBlockHdr *)(((char *)(mb + 1)) + blockSize);
+    PR_ASSERT(mt->s.magic == ZONE_MAGIC);
+    PR_ASSERT(mt->s.zone  == mz);
+    PR_ASSERT(mt->s.blockSize == blockSize);
+    if (!mz) {
+        PR_ASSERT(blockSize > 65536);
+        /* This block was not in any zone.  Just free it. */
+        free(ptr);
+        return;
+    }
+    PR_ASSERT(mz->blockSize == blockSize);
+    wasLocked = mz->locked;
+    pthread_mutex_lock(&mz->lock);
+    mz->locked = 1;
+    if (wasLocked)
+        mz->contention++;
+    mt->s.next = mb->s.next = mz->head;        /* put on head of list */
+    mz->head = mb;
+    mz->elements++;
+    mz->locked = 0;
+    pthread_mutex_unlock(&mz->lock);
+}
+
+PR_IMPLEMENT(void *) PR_Malloc(PRUint32 size)
+{
+    if (!_pr_initialized) _PR_ImplicitInitialization();
+
+    return use_zone_allocator ? pr_ZoneMalloc(size) : malloc(size);
+}
+
+PR_IMPLEMENT(void *) PR_Calloc(PRUint32 nelem, PRUint32 elsize)
+{
+    if (!_pr_initialized) _PR_ImplicitInitialization();
+
+    return use_zone_allocator ?
+        pr_ZoneCalloc(nelem, elsize) : calloc(nelem, elsize);
+}
+
+PR_IMPLEMENT(void *) PR_Realloc(void *ptr, PRUint32 size)
+{
+    if (!_pr_initialized) _PR_ImplicitInitialization();
+
+    return use_zone_allocator ? pr_ZoneRealloc(ptr, size) : realloc(ptr, size);
+}
+
+PR_IMPLEMENT(void) PR_Free(void *ptr)
+{
+    if (use_zone_allocator)
+        pr_ZoneFree(ptr);
+    else
+        free(ptr);
+}
+
+#else /* !defined(_PR_ZONE_ALLOCATOR) */
+
 /*
 ** The PR_Malloc, PR_Calloc, PR_Realloc, and PR_Free functions simply
 ** call their libc equivalents now.  This may seem redundant, but it
@@ -83,6 +435,8 @@ PR_IMPLEMENT(void) PR_Free(void *ptr)
 #endif
 }
 
+#endif /* _PR_ZONE_ALLOCATOR */
+
 /*
 ** Complexity alert!
 **
diff --git a/pr/src/misc/prinit.c b/pr/src/misc/prinit.c
index c7471367..6da27fa0 100644
--- a/pr/src/misc/prinit.c
+++ b/pr/src/misc/prinit.c
@@ -220,6 +220,10 @@ static void _PR_InitStuff(void)
 	_PR_InitCPUs();
 #endif
 
+#ifdef _PR_ZONE_ALLOCATOR
+    _PR_InitZones();
+#endif
+
 /*
  * XXX: call _PR_InitMem only on those platforms for which nspr implements
  *	malloc, for now.
diff --git a/pr/src/pthreads/ptthread.c b/pr/src/pthreads/ptthread.c
index 1072df2d..d23b2dd1 100644
--- a/pr/src/pthreads/ptthread.c
+++ b/pr/src/pthreads/ptthread.c
@@ -940,6 +940,9 @@ PR_IMPLEMENT(PRStatus) PR_Cleanup()
         _pr_sleeplock = NULL;
         _PR_CleanupLayerCache();
         _PR_CleanupEnv();
+#ifdef _PR_ZONE_ALLOCATOR
+        _PR_DestroyZones();
+#endif
         _pr_initialized = PR_FALSE;
         return PR_SUCCESS;
     }