Index: glib/gmem.c
===================================================================
RCS file: /cvs/gnome/glib/glib/gmem.c,v
retrieving revision 1.47
diff -u -r1.47 gmem.c
--- glib/gmem.c	22 Mar 2005 04:09:16 -0000	1.47
+++ glib/gmem.c	27 Sep 2005 17:25:31 -0000
@@ -127,6 +127,7 @@
 
 
 /* --- functions --- */
+
 gpointer
 g_malloc (gulong n_bytes)
 {
@@ -602,621 +603,608 @@
 
 #endif	/* !G_DISABLE_CHECKS */
 
+/* Chunk allocator.
+ *
+ * Memory is allocated in reasonably large blocks (1k currently), chopped into
+ * equal-sized chunks, and put on a global freelist. The freelist is actually 
+ * a list of "magazines", which hold a fixed number of chunks. Each thread has 
+ * its own local freelist which is limited in size to two magazines. 
+ * Transferring memory between the global and local freelists is always done in 
+ * full magazines (except for thread termination, which is handled separately 
+ * using a "rest" list).
+ *
+ * Each thread allocates and frees chunks out of its local freelist, as long
+ * as thats possible. As an extra twist, the 2 magazines of the local freelist
+ * can be swapped, which can sometimes avoid exchanging memory with the global 
+ * freelist.
+ *
+ * For O(1) list freeing, we give up the idea that the members of a magazines 
+ * are individual chunks. Instead, they can be lists themselves, and the code 
+ * handles that when allocating a chunk.
+ */
 
-/* --- MemChunks --- */
-typedef struct _GFreeAtom      GFreeAtom;
-typedef struct _GMemArea       GMemArea;
+#define AREA_SIZE 1024
+#define NUM_DEPOTS 16
+#define MIN_CHUNK_SIZE (((sizeof (Chunk) + G_MEM_ALIGN - 1) / G_MEM_ALIGN) * G_MEM_ALIGN)
 
-struct _GFreeAtom
-{
-  GFreeAtom *next;
-};
 
-struct _GMemArea
+typedef struct _Chunk Chunk;
+typedef struct _Magazine Magazine;
+typedef struct _Depot Depot;
+
+/*  
+ * We require chunks to hold at least 2 pointers. @next_chunk is used to link
+ * the chunks in a magazine together. @next is the next pointer used in data 
+ * structures like GList or GSList; it is also used internally to link the 
+ * magazines on the global freelist together.
+ */
+struct _Chunk 
 {
-  GMemArea *next;            /* the next mem area */
-  GMemArea *prev;            /* the previous mem area */
-  gulong index;              /* the current index into the "mem" array */
-  gulong free;               /* the number of free bytes in this mem area */
-  gulong allocated;          /* the number of atoms allocated from this area */
-  gulong mark;               /* is this mem area marked for deletion */
-  gchar mem[MEM_AREA_SIZE];  /* the mem array from which atoms get allocated
-			      * the actual size of this array is determined by
-			      *  the mem chunk "area_size". ANSI says that it
-			      *  must be declared to be the maximum size it
-			      *  can possibly be (even though the actual size
-			      *  may be less).
-			      */
+  Chunk *next_chunk;
+  Chunk *next;
 };
 
-struct _GMemChunk
+/*
+ * The thread-local freelist for a given chunk size, holding two 
+ * magazines of chunks.
+ */
+struct _Magazine
 {
-  const gchar *name;         /* name of this MemChunk...used for debugging output */
-  gint type;                 /* the type of MemChunk: ALLOC_ONLY or ALLOC_AND_FREE */
-  gint num_mem_areas;        /* the number of memory areas */
-  gint num_marked_areas;     /* the number of areas marked for deletion */
-  guint atom_size;           /* the size of an atom */
-  gulong area_size;          /* the size of a memory area */
-  GMemArea *mem_area;        /* the current memory area */
-  GMemArea *mem_areas;       /* a list of all the mem areas owned by this chunk */
-  GMemArea *free_mem_area;   /* the free area...which is about to be destroyed */
-  GFreeAtom *free_atoms;     /* the free atoms list */
-  GTree *mem_tree;           /* tree of mem areas sorted by memory address */
-  GMemChunk *next;           /* pointer to the next chunk */
-  GMemChunk *prev;           /* pointer to the previous chunk */
+  Chunk *chunk[2];
+  gint   count[2];
 };
 
-
-#ifndef DISABLE_MEM_POOLS
-static gulong g_mem_chunk_compute_size (gulong    size,
-					gulong    min_size) G_GNUC_CONST;
-static gint   g_mem_chunk_area_compare (GMemArea *a,
-					GMemArea *b);
-static gint   g_mem_chunk_area_search  (GMemArea *a,
-					gchar    *addr);
-
-/* here we can't use StaticMutexes, as they depend upon a working
- * g_malloc, the same holds true for StaticPrivate
+/*
+ * The global freelist for a given chunk size. @depot holds a 
+ * @rest is a list of leftover chunks
  */
-static GMutex        *mem_chunks_lock = NULL;
-static GMemChunk     *mem_chunks = NULL;
-
-GMemChunk*
-g_mem_chunk_new (const gchar  *name,
-		 gint          atom_size,
-		 gulong        area_size,
-		 gint          type)
+struct _Depot
 {
-  GMemChunk *mem_chunk;
-  gulong rarea_size;
+  Chunk *depot; /* list of magazines which are ready to be handed out,
+                 * linked together using the @next pointer in the first chunk.
+		 */
 
-  g_return_val_if_fail (atom_size > 0, NULL);
-  g_return_val_if_fail (area_size >= atom_size, NULL);
+  Chunk *rest;     /* leftover chunks from terminated threads */
+  gint rest_count; /* length of the @rest list */
 
-  ENTER_MEM_CHUNK_ROUTINE ();
+  guint chunk_size;
+  guint magazine_size;  /* how many chunks fit into a magazine */
 
-  area_size = (area_size + atom_size - 1) / atom_size;
-  area_size *= atom_size;
-
-  mem_chunk = g_new (GMemChunk, 1);
-  mem_chunk->name = name;
-  mem_chunk->type = type;
-  mem_chunk->num_mem_areas = 0;
-  mem_chunk->num_marked_areas = 0;
-  mem_chunk->mem_area = NULL;
-  mem_chunk->free_mem_area = NULL;
-  mem_chunk->free_atoms = NULL;
-  mem_chunk->mem_tree = NULL;
-  mem_chunk->mem_areas = NULL;
-  mem_chunk->atom_size = atom_size;
+  guint n_areas;   /* number of areas which have been malloced for chunks
+                    * of this size; used only for diagnostic purposes
+		    */
   
-  if (mem_chunk->type == G_ALLOC_AND_FREE)
-    mem_chunk->mem_tree = g_tree_new ((GCompareFunc) g_mem_chunk_area_compare);
-  
-  if (mem_chunk->atom_size % G_MEM_ALIGN)
-    mem_chunk->atom_size += G_MEM_ALIGN - (mem_chunk->atom_size % G_MEM_ALIGN);
+  GStaticMutex lock;
+};
 
-  rarea_size = area_size + sizeof (GMemArea) - MEM_AREA_SIZE;
-  rarea_size = g_mem_chunk_compute_size (rarea_size, atom_size + sizeof (GMemArea) - MEM_AREA_SIZE);
-  mem_chunk->area_size = rarea_size - (sizeof (GMemArea) - MEM_AREA_SIZE);
-
-  g_mutex_lock (mem_chunks_lock);
-  mem_chunk->next = mem_chunks;
-  mem_chunk->prev = NULL;
-  if (mem_chunks)
-    mem_chunks->prev = mem_chunk;
-  mem_chunks = mem_chunk;
-  g_mutex_unlock (mem_chunks_lock);
+static Depot depots[NUM_DEPOTS];
 
-  LEAVE_MEM_CHUNK_ROUTINE ();
+/* 
+ * Sets up the global freelists. 
+ */
+static inline void
+initialize_depots (void)
+{
+  static gboolean initialized = FALSE;
 
-  return mem_chunk;
-}
+  if (G_UNLIKELY (!initialized))
+    {
+      gint i;
 
-void
-g_mem_chunk_destroy (GMemChunk *mem_chunk)
-{
-  GMemArea *mem_areas;
-  GMemArea *temp_area;
-  
-  g_return_if_fail (mem_chunk != NULL);
+      initialized = TRUE;
 
-  ENTER_MEM_CHUNK_ROUTINE ();
+      for (i = 0; i < NUM_DEPOTS; i++)
+	{
+	  depots[i].depot = NULL;
+	  depots[i].rest = NULL;
+	  depots[i].rest_count = 0;
+	  depots[i].chunk_size = MIN_CHUNK_SIZE + i * G_MEM_ALIGN;
+	  depots[i].magazine_size = AREA_SIZE / depots[i].chunk_size;
+	  depots[i].n_areas = 0;
 
-  mem_areas = mem_chunk->mem_areas;
-  while (mem_areas)
-    {
-      temp_area = mem_areas;
-      mem_areas = mem_areas->next;
-      g_free (temp_area);
+	  g_static_mutex_init (&depots[i].lock);
+	}
     }
-  
-  g_mutex_lock (mem_chunks_lock);
-  if (mem_chunk->next)
-    mem_chunk->next->prev = mem_chunk->prev;
-  if (mem_chunk->prev)
-    mem_chunk->prev->next = mem_chunk->next;
-  
-  if (mem_chunk == mem_chunks)
-    mem_chunks = mem_chunks->next;
-  g_mutex_unlock (mem_chunks_lock);
-  
-  if (mem_chunk->type == G_ALLOC_AND_FREE)
-    g_tree_destroy (mem_chunk->mem_tree);  
-
-  g_free (mem_chunk);
+}
 
-  LEAVE_MEM_CHUNK_ROUTINE ();
+static inline gint
+get_index (gint chunk_size)
+{
+  return (MAX (chunk_size - MIN_CHUNK_SIZE, 0) + G_MEM_ALIGN - 1) / G_MEM_ALIGN;
 }
 
-gpointer
-g_mem_chunk_alloc (GMemChunk *mem_chunk)
+static inline Magazine *
+get_magazine (gint idx)
 {
-  GMemArea *temp_area;
-  gpointer mem;
+  GThread *self;
+  Magazine *mag;
 
-  ENTER_MEM_CHUNK_ROUTINE ();
+  self = g_thread_self ();
 
-  g_return_val_if_fail (mem_chunk != NULL, NULL);
-  
-  while (mem_chunk->free_atoms)
+  mag = (Magazine *)_g_thread_mem_private_get (self);
+
+  if (G_UNLIKELY (!mag))
     {
-      /* Get the first piece of memory on the "free_atoms" list.
-       * We can go ahead and destroy the list node we used to keep
-       *  track of it with and to update the "free_atoms" list to
-       *  point to its next element.
-       */
-      mem = mem_chunk->free_atoms;
-      mem_chunk->free_atoms = mem_chunk->free_atoms->next;
-      
-      /* Determine which area this piece of memory is allocated from */
-      temp_area = g_tree_search (mem_chunk->mem_tree,
-				 (GCompareFunc) g_mem_chunk_area_search,
-				 mem);
+      mag = g_new0 (Magazine, NUM_DEPOTS);
       
-      /* If the area has been marked, then it is being destroyed.
-       *  (ie marked to be destroyed).
-       * We check to see if all of the segments on the free list that
-       *  reference this area have been removed. This occurs when
-       *  the ammount of free memory is less than the allocatable size.
-       * If the chunk should be freed, then we place it in the "free_mem_area".
-       * This is so we make sure not to free the mem area here and then
-       *  allocate it again a few lines down.
-       * If we don't allocate a chunk a few lines down then the "free_mem_area"
-       *  will be freed.
-       * If there is already a "free_mem_area" then we'll just free this mem area.
-       */
-      if (temp_area->mark)
-        {
-          /* Update the "free" memory available in that area */
-          temp_area->free += mem_chunk->atom_size;
-	  
-          if (temp_area->free == mem_chunk->area_size)
-            {
-              if (temp_area == mem_chunk->mem_area)
-                mem_chunk->mem_area = NULL;
-	      
-              if (mem_chunk->free_mem_area)
-                {
-                  mem_chunk->num_mem_areas -= 1;
-		  
-                  if (temp_area->next)
-                    temp_area->next->prev = temp_area->prev;
-                  if (temp_area->prev)
-                    temp_area->prev->next = temp_area->next;
-                  if (temp_area == mem_chunk->mem_areas)
-                    mem_chunk->mem_areas = mem_chunk->mem_areas->next;
-		  
-		  if (mem_chunk->type == G_ALLOC_AND_FREE)
-		    g_tree_remove (mem_chunk->mem_tree, temp_area);
-                  g_free (temp_area);
-                }
-              else
-                mem_chunk->free_mem_area = temp_area;
-	      
-	      mem_chunk->num_marked_areas -= 1;
-	    }
-	}
-      else
-        {
-          /* Update the number of allocated atoms count.
-	   */
-          temp_area->allocated += 1;
-	  
-          /* The area wasn't marked...return the memory
-	   */
-	  goto outa_here;
-        }
-    }
-  
-  /* If there isn't a current mem area or the current mem area is out of space
-   *  then allocate a new mem area. We'll first check and see if we can use
-   *  the "free_mem_area". Otherwise we'll just malloc the mem area.
-   */
-  if ((!mem_chunk->mem_area) ||
-      ((mem_chunk->mem_area->index + mem_chunk->atom_size) > mem_chunk->area_size))
-    {
-      if (mem_chunk->free_mem_area)
-        {
-          mem_chunk->mem_area = mem_chunk->free_mem_area;
-	  mem_chunk->free_mem_area = NULL;
-        }
-      else
-        {
-#ifdef ENABLE_GC_FRIENDLY
-	  mem_chunk->mem_area = (GMemArea*) g_malloc0 (sizeof (GMemArea) -
-						       MEM_AREA_SIZE +
-						       mem_chunk->area_size); 
-#else /* !ENABLE_GC_FRIENDLY */
-	  mem_chunk->mem_area = (GMemArea*) g_malloc (sizeof (GMemArea) -
-						      MEM_AREA_SIZE +
-						      mem_chunk->area_size);
-#endif /* ENABLE_GC_FRIENDLY */
-	  
-	  mem_chunk->num_mem_areas += 1;
-	  mem_chunk->mem_area->next = mem_chunk->mem_areas;
-	  mem_chunk->mem_area->prev = NULL;
-	  
-	  if (mem_chunk->mem_areas)
-	    mem_chunk->mem_areas->prev = mem_chunk->mem_area;
-	  mem_chunk->mem_areas = mem_chunk->mem_area;
-	  
-	  if (mem_chunk->type == G_ALLOC_AND_FREE)
-	    g_tree_insert (mem_chunk->mem_tree, mem_chunk->mem_area, mem_chunk->mem_area);
-        }
-      
-      mem_chunk->mem_area->index = 0;
-      mem_chunk->mem_area->free = mem_chunk->area_size;
-      mem_chunk->mem_area->allocated = 0;
-      mem_chunk->mem_area->mark = 0;
+      _g_thread_mem_private_set (self, mag);
     }
-  
-  /* Get the memory and modify the state variables appropriately.
-   */
-  mem = (gpointer) &mem_chunk->mem_area->mem[mem_chunk->mem_area->index];
-  mem_chunk->mem_area->index += mem_chunk->atom_size;
-  mem_chunk->mem_area->free -= mem_chunk->atom_size;
-  mem_chunk->mem_area->allocated += 1;
-
-outa_here:
-
-  LEAVE_MEM_CHUNK_ROUTINE ();
 
-  return mem;
+  return &mag[idx];
 }
 
-gpointer
-g_mem_chunk_alloc0 (GMemChunk *mem_chunk)
+/* 
+ * Adds a full magazine to the global freelist.
+ * If necessary, rotate the first chunk out of
+ * the @next list into the @next_chunk list, so
+ * that its @next pointer can be used. This may
+ * make the magazine larger than depot->magazine_size,
+ * but that is not a problem, since magazine_size
+ * is only used to limit the growth of the 
+ * thread-local freelists.
+ *
+ * The caller must hold depot->lock.
+ */
+static inline void
+add_magazine_to_depot (Depot *depot,
+		       Chunk *chunk)
 {
-  gpointer mem;
-
-  mem = g_mem_chunk_alloc (mem_chunk);
-  if (mem)
+  if (chunk->next)
     {
-      memset (mem, 0, mem_chunk->atom_size);
+      chunk->next->next_chunk = chunk->next_chunk;
+      chunk->next_chunk = chunk->next;
     }
-
-  return mem;
+  
+  chunk->next = depot->depot;
+  depot->depot = chunk;
 }
 
-void
-g_mem_chunk_free (GMemChunk *mem_chunk,
-		  gpointer   mem)
+/*
+ * Puts chunks back onto the global freelist.
+ * The chunks are not required to form a full
+ * magazine.
+ */
+static inline void
+unload_chunks (gint   idx,
+	       Chunk *chunk)
 {
-  GMemArea *temp_area;
-  GFreeAtom *free_atom;
-  
-  g_return_if_fail (mem_chunk != NULL);
-  g_return_if_fail (mem != NULL);
+  Depot *depot;
+  Chunk *next;
+
+  if (!chunk)
+    return;
 
-  ENTER_MEM_CHUNK_ROUTINE ();
+  depot = &depots[idx];
 
-#ifdef ENABLE_GC_FRIENDLY
-  memset (mem, 0, mem_chunk->atom_size);
-#endif /* ENABLE_GC_FRIENDLY */
+  g_static_mutex_lock (&depot->lock);
 
-  /* Don't do anything if this is an ALLOC_ONLY chunk
-   */
-  if (mem_chunk->type == G_ALLOC_AND_FREE)
+  while (chunk)
     {
-      /* Place the memory on the "free_atoms" list
-       */
-      free_atom = (GFreeAtom*) mem;
-      free_atom->next = mem_chunk->free_atoms;
-      mem_chunk->free_atoms = free_atom;
+      next = chunk->next_chunk;
+      chunk->next_chunk = depot->rest;
+      depot->rest = chunk;
+      depot->rest_count++;
+      chunk = next;
       
-      temp_area = g_tree_search (mem_chunk->mem_tree,
-				 (GCompareFunc) g_mem_chunk_area_search,
-				 mem);
-      
-      temp_area->allocated -= 1;
-      
-      if (temp_area->allocated == 0)
+      if (depot->rest_count == depot->magazine_size)
 	{
-	  temp_area->mark = 1;
-	  mem_chunk->num_marked_areas += 1;
+	  add_magazine_to_depot (depot, depot->rest);
+
+	  depot->rest = NULL;
+	  depot->rest_count = 0;   
 	}
-    }
+    } 
 
-  LEAVE_MEM_CHUNK_ROUTINE ();
+  g_static_mutex_unlock (&depot->lock);   
 }
 
-/* This doesn't free the free_area if there is one */
+/* 
+ * This function is called from gthread.c upon
+ * thread termination. It puts the chunks from
+ * the thread-local freelist back onto the global
+ * freelist, after collecting it in magazines.
+ */
 void
-g_mem_chunk_clean (GMemChunk *mem_chunk)
-{
-  GMemArea *mem_area;
-  GFreeAtom *prev_free_atom;
-  GFreeAtom *temp_free_atom;
-  gpointer mem;
-  
-  g_return_if_fail (mem_chunk != NULL);
-  
-  ENTER_MEM_CHUNK_ROUTINE ();
+_g_mem_thread_cleanup (void)
+{ 
+  gint idx;
+  Magazine *mag;
 
-  if (mem_chunk->type == G_ALLOC_AND_FREE)
+  mag = _g_thread_mem_private_get (g_thread_self ());
+  for (idx = 0; idx < NUM_DEPOTS; idx++)
     {
-      prev_free_atom = NULL;
-      temp_free_atom = mem_chunk->free_atoms;
-      
-      while (temp_free_atom)
-	{
-	  mem = (gpointer) temp_free_atom;
-	  
-	  mem_area = g_tree_search (mem_chunk->mem_tree,
-				    (GCompareFunc) g_mem_chunk_area_search,
-				    mem);
-	  
-          /* If this mem area is marked for destruction then delete the
-	   *  area and list node and decrement the free mem.
-           */
-	  if (mem_area->mark)
-	    {
-	      if (prev_free_atom)
-		prev_free_atom->next = temp_free_atom->next;
-	      else
-		mem_chunk->free_atoms = temp_free_atom->next;
-	      temp_free_atom = temp_free_atom->next;
-	      
-	      mem_area->free += mem_chunk->atom_size;
-	      if (mem_area->free == mem_chunk->area_size)
-		{
-		  mem_chunk->num_mem_areas -= 1;
-		  mem_chunk->num_marked_areas -= 1;
-		  
-		  if (mem_area->next)
-		    mem_area->next->prev = mem_area->prev;
-		  if (mem_area->prev)
-		    mem_area->prev->next = mem_area->next;
-		  if (mem_area == mem_chunk->mem_areas)
-		    mem_chunk->mem_areas = mem_chunk->mem_areas->next;
-		  if (mem_area == mem_chunk->mem_area)
-		    mem_chunk->mem_area = NULL;
-		  
-		  if (mem_chunk->type == G_ALLOC_AND_FREE)
-		    g_tree_remove (mem_chunk->mem_tree, mem_area);
-		  g_free (mem_area);
-		}
-	    }
-	  else
-	    {
-	      prev_free_atom = temp_free_atom;
-	      temp_free_atom = temp_free_atom->next;
-	    }
-	}
+      unload_chunks (idx, mag[idx].chunk[0]);
+      unload_chunks (idx, mag[idx].chunk[1]);
     }
-  LEAVE_MEM_CHUNK_ROUTINE ();
+  g_free (mag);
+
+  _g_thread_mem_private_set (g_thread_self (), NULL);
 }
 
-void
-g_mem_chunk_reset (GMemChunk *mem_chunk)
+/* 
+ * Obtains a full magazine from the global freelist.
+ * If necessary, a new area is allocated and chopped
+ * in chunks.
+ */
+static inline Chunk *
+reload (gint idx)
 {
-  GMemArea *mem_areas;
-  GMemArea *temp_area;
-  
-  g_return_if_fail (mem_chunk != NULL);
-  
-  ENTER_MEM_CHUNK_ROUTINE ();
+  gchar *mem;
+  Depot *depot;
+  Chunk *chunk, *next;
+  gint i;
 
-  mem_areas = mem_chunk->mem_areas;
-  mem_chunk->num_mem_areas = 0;
-  mem_chunk->mem_areas = NULL;
-  mem_chunk->mem_area = NULL;
+  initialize_depots ();
   
-  while (mem_areas)
-    {
-      temp_area = mem_areas;
-      mem_areas = mem_areas->next;
-      g_free (temp_area);
-    }
-  
-  mem_chunk->free_atoms = NULL;
+  depot = &depots[idx];
+
+  g_static_mutex_lock (&depot->lock);
   
-  if (mem_chunk->mem_tree)
+  if (G_UNLIKELY (!depot->depot))
     {
-      g_tree_destroy (mem_chunk->mem_tree);
-      mem_chunk->mem_tree = g_tree_new ((GCompareFunc) g_mem_chunk_area_compare);
+      mem = g_malloc (AREA_SIZE);
+      depot->n_areas++;
+
+      chunk = next = NULL;
+      for (i = 0; i < depot->magazine_size; i++)
+	{
+	  chunk = (Chunk *) (mem + i * depot->chunk_size);
+          chunk->next = NULL;
+	  chunk->next_chunk = next;
+	  next = chunk;
+	}
+
+      depot->depot = chunk;
     }
 
-  LEAVE_MEM_CHUNK_ROUTINE ();
+  chunk = depot->depot;
+  depot->depot = chunk->next;
+  chunk->next = NULL;
+ 
+  g_static_mutex_unlock (&depot->lock);
+
+  return chunk;
 }
 
-void
-g_mem_chunk_print (GMemChunk *mem_chunk)
+/* 
+ * Returns a full magazine to the global
+ * freelist.
+ */
+static inline void
+unload (gint   idx,
+	Chunk *chunk)
 {
-  GMemArea *mem_areas;
-  gulong mem;
-  
-  g_return_if_fail (mem_chunk != NULL);
-  
-  mem_areas = mem_chunk->mem_areas;
-  mem = 0;
-  
-  while (mem_areas)
-    {
-      mem += mem_chunk->area_size - mem_areas->free;
-      mem_areas = mem_areas->next;
-    }
+  Depot *depot;
 
-  g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO,
-	 "%s: %ld bytes using %d mem areas",
-	 mem_chunk->name, mem, mem_chunk->num_mem_areas);
+  depot = &depots[idx];
+
+  g_static_mutex_lock (&depot->lock);
+
+  add_magazine_to_depot (depot, chunk);
+
+  g_static_mutex_unlock (&depot->lock);
 }
 
-void
-g_mem_chunk_info (void)
+static inline void
+swap_magazine (Magazine *magazine)
 {
-  GMemChunk *mem_chunk;
+  Chunk *chunk;
   gint count;
+
+  chunk = magazine->chunk[0];
+  count = magazine->count[0];
+  magazine->chunk[0] = magazine->chunk[1];
+  magazine->count[0] = magazine->count[1];
+  magazine->chunk[1] = chunk;
+  magazine->count[1] = count;
+}
+
+/*
+ * g_alloc_chunk:
+ * @chunk_size: the number of bytes to allocate
+ *
+ * Allocates @n_bytes of memory. The memory
+ * must be freed with g_free_chunk() or 
+ * g_free_chunk_list() when it is no longer needed.
+ *
+ * g_alloc_chunk() avoids the space overhead of
+ * malloc() and thus can be more efficient than
+ * g_malloc() when allocating many small, equal-sized
+ * pieces of memory.
+ * 
+ * Returns: a pointer to the allocated memory
+ */
+gpointer
+g_alloc_chunk (gint chunk_size)
+{
+  gint idx;
+  Magazine *magazine;
+  Chunk *chunk;
   
-  count = 0;
-  g_mutex_lock (mem_chunks_lock);
-  mem_chunk = mem_chunks;
-  while (mem_chunk)
+  idx = get_index (chunk_size);
+
+  if (G_UNLIKELY (idx >= NUM_DEPOTS))
+    return g_malloc (chunk_size);
+
+  magazine = get_magazine (idx);
+
+  if (G_UNLIKELY (!magazine->chunk[0]))
+    {
+      if (G_UNLIKELY (!magazine->chunk[1]))
+	{
+	  magazine->chunk[0] = reload (idx);
+	  magazine->count[0] = depots[idx].magazine_size;
+	}
+      else
+	{
+          swap_magazine (magazine);
+	}
+    }
+
+  chunk = magazine->chunk[0];
+  if (chunk->next)
     {
-      count += 1;
-      mem_chunk = mem_chunk->next;
+      chunk->next->next_chunk = chunk->next_chunk;
+      magazine->chunk[0] = chunk->next;
+    }
+  else
+    {
+      magazine->chunk[0] = chunk->next_chunk;
+      magazine->count[0]--;
     }
-  g_mutex_unlock (mem_chunks_lock);
-  
-  g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "%d mem chunks", count);
   
-  g_mutex_lock (mem_chunks_lock);
-  mem_chunk = mem_chunks;
-  g_mutex_unlock (mem_chunks_lock);
-
-  while (mem_chunk)
-    {
-      g_mem_chunk_print ((GMemChunk*) mem_chunk);
-      mem_chunk = mem_chunk->next;
-    }  
+  return chunk;
 }
 
+/**
+ * g_alloc0_chunk:
+ * @chunk_size: the number of bytes to allocate
+ *
+ * Allocates @n_bytes of zeroed memory. The memory
+ * must be freed with g_free_chunk() or 
+ * g_free_chunk_list() when it is no longer needed.
+ *
+ * See g_alloc_chunk().
+ *
+ * Returns: a pointer to the allocated memory
+ */
+gpointer
+g_alloc0_chunk (gint chunk_size)
+{
+  gpointer mem;
+
+  mem = g_alloc_chunk (chunk_size);
+
+  if (mem)
+    memset (mem, 0, chunk_size);
+
+  return mem;
+}
+
+/**
+ * g_free_chunk_list: 
+ * @mem: the memory to free
+ * @chunk_size: the size of @mem
+ *
+ * Frees a list of chunks that have been
+ * allocated by g_alloc_chunk(). The lists
+ * must be linked together by pointers stored
+ * in the second word of each chunk. This 
+ * function is intended for list structures
+ * which allow O(1) freeing of entire lists,
+ * like #GList.
+ * 
+ * See g_free_chunk() for freeing chunks
+ * which are not part of a list.
+ */
 void
-g_blow_chunks (void)
+g_free_chunk_list (gpointer mem,
+                   gint     chunk_size)
 {
-  GMemChunk *mem_chunk;
+  gint idx;
+  Magazine *magazine;
+  Chunk *chunk;
   
-  g_mutex_lock (mem_chunks_lock);
-  mem_chunk = mem_chunks;
-  g_mutex_unlock (mem_chunks_lock);
-  while (mem_chunk)
+  if (!mem)
+    return;
+ 
+  idx = get_index (chunk_size);
+  if (G_UNLIKELY (idx >= NUM_DEPOTS))
     {
-      g_mem_chunk_clean ((GMemChunk*) mem_chunk);
-      mem_chunk = mem_chunk->next;
+      g_free (mem);
+      return;
+    }
+
+  magazine = get_magazine (idx);
+
+  if (G_UNLIKELY (magazine->count[1] == depots[idx].magazine_size))
+    {
+      if (G_UNLIKELY (magazine->count[0] == depots[idx].magazine_size))
+	{
+	  unload (idx, magazine->chunk[1]);
+	  magazine->chunk[1] = NULL;
+	  magazine->count[1] = 0;
+	}
+      else
+	{
+          swap_magazine (magazine);
+	}
     }
+
+  chunk = (Chunk *)mem;
+  chunk->next_chunk = magazine->chunk[1];
+  magazine->chunk[1] = chunk;
+  magazine->count[1]++;
 }
 
-static gulong
-g_mem_chunk_compute_size (gulong size,
-			  gulong min_size)
+/**
+ * g_free_chunk:
+ * @mem: the memory to free
+ * @chunk_size: the size of @mem
+ *
+ * Frees a chunk of memory that has been
+ * allocated with g_alloc_chunk(). 
+ *
+ * See g_free_chunk_list() for freeing lists
+ * of chunks in one go.
+ */
+void
+g_free_chunk (gpointer mem,
+              gint     chunk_size)
 {
-  gulong power_of_2;
-  gulong lower, upper;
-  
-  power_of_2 = 16;
-  while (power_of_2 < size)
-    power_of_2 <<= 1;
-  
-  lower = power_of_2 >> 1;
-  upper = power_of_2;
-  
-  if (size - lower < upper - size && lower >= min_size)
-    return lower;
-  else
-    return upper;
+  Chunk *chunk;
+
+  if (!mem)
+    return;
+
+  chunk = (Chunk *)mem;
+  chunk->next = NULL;
+
+  g_free_chunk_list (mem, chunk_size);
 }
 
-static gint
-g_mem_chunk_area_compare (GMemArea *a,
-			  GMemArea *b)
+static void
+collect_stats (gpointer data, 
+	       gpointer user_data)
 {
-  if (a->mem > b->mem)
-    return 1;
-  else if (a->mem < b->mem)
-    return -1;
-  return 0;
+  GThread *thread = (GThread *)data;
+  gint *stats = (gint *)user_data;
+  Magazine *mag;
+  gint i;
+
+  mag = (Magazine *)_g_thread_mem_private_get (thread);
+      
+  if (mag)
+    for (i = 0; i < NUM_DEPOTS; i++)
+      {
+	stats[i] += mag[i].count[0];
+	stats[i] += mag[i].count[1];
+      }
+
+  stats[16]++;
 }
 
-static gint
-g_mem_chunk_area_search (GMemArea *a,
-			 gchar    *addr)
+static void 
+print_depot_info (Depot *depot)
 {
-  if (a->mem <= addr)
-    {
-      if (addr < &a->mem[a->index])
-	return 0;
-      return 1;
-    }
-  return -1;
-}
+  Chunk *head; 
+  gint free_chunks;
+  gint stats[NUM_DEPOTS + 1] = { 0, };
+  gint idx;
+  
+  free_chunks = depot->rest_count;
+  for (head = depot->depot; head; head = head->next_chunk)
+    free_chunks += depot->magazine_size;
 
-#else /* DISABLE_MEM_POOLS */
+  _g_thread_foreach (collect_stats, stats);
 
-typedef struct {
-  guint alloc_size;           /* the size of an atom */
-}  GMinimalMemChunk;
+  idx = get_index (depot->chunk_size);
+
+  g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO,
+	 "Depot (%d / %d): mem areas %d (%d bytes), global free %d (%d bytes), local free %d (%d bytes) in %d threads",
+	 depot->chunk_size, 
+	 depot->magazine_size,
+	 depot->n_areas,
+	 AREA_SIZE * depot->n_areas, 
+	 free_chunks,
+	 free_chunks * depot->chunk_size,
+	 stats[idx],
+	 stats[idx] * depot->chunk_size,
+	 stats[NUM_DEPOTS]);
+}
+
+/*  
+ * Below is a minimalistic memchunk implementation based 
+ * on g_chunk_alloc(). It ignores the @area_size and @type.
+ * We should probably deprecate memchunks in favor of 
+ * g_chunk_alloc().
+ */
+struct _GMemChunk
+{
+  Depot *depot;
+  gchar *name;
+  guint chunk_size;
+};
 
-GMemChunk*
-g_mem_chunk_new (const gchar  *name,
-		 gint          atom_size,
-		 gulong        area_size,
-		 gint          type)
+GMemChunk *
+g_mem_chunk_new (const gchar *name,
+		 gint         atom_size, 
+		 gulong       area_size,
+		 gint         type)
 {
-  GMinimalMemChunk *mem_chunk;
+  GMemChunk *mem_chunk;
 
-  g_return_val_if_fail (atom_size > 0, NULL);
+  mem_chunk = g_malloc (sizeof (GMemChunk));
 
-  mem_chunk = g_new (GMinimalMemChunk, 1);
-  mem_chunk->alloc_size = atom_size;
+  mem_chunk->name = g_strdup (name);
+  atom_size = ((atom_size + G_MEM_ALIGN - 1) / G_MEM_ALIGN) * G_MEM_ALIGN;
+  if (atom_size < sizeof (Chunk))
+    atom_size = sizeof (Chunk);
+
+  mem_chunk->chunk_size = atom_size;
+
+  if (mem_chunk->chunk_size > sizeof (Chunk) + 15 * G_MEM_ALIGN)
+    mem_chunk->depot = NULL;
+  else
+    {
+      initialize_depots ();
+      
+      mem_chunk->depot = &depots[(mem_chunk->chunk_size - sizeof (Chunk)) / G_MEM_ALIGN];
+    }
 
-  return ((GMemChunk*) mem_chunk);
+  return mem_chunk;
 }
 
 void
 g_mem_chunk_destroy (GMemChunk *mem_chunk)
 {
-  g_return_if_fail (mem_chunk != NULL);
-  
+  g_free (mem_chunk->name);
   g_free (mem_chunk);
 }
 
 gpointer
 g_mem_chunk_alloc (GMemChunk *mem_chunk)
 {
-  GMinimalMemChunk *minimal = (GMinimalMemChunk *)mem_chunk;
-  
-  g_return_val_if_fail (mem_chunk != NULL, NULL);
-  
-  return g_malloc (minimal->alloc_size);
+  return g_alloc_chunk (mem_chunk->chunk_size);
 }
 
 gpointer
 g_mem_chunk_alloc0 (GMemChunk *mem_chunk)
 {
-  GMinimalMemChunk *minimal = (GMinimalMemChunk *)mem_chunk;
-  
-  g_return_val_if_fail (mem_chunk != NULL, NULL);
-  
-  return g_malloc0 (minimal->alloc_size);
+  return g_alloc0_chunk (mem_chunk->chunk_size);
 }
 
 void
 g_mem_chunk_free (GMemChunk *mem_chunk,
-		  gpointer   mem)
+                  gpointer   mem)
 {
-  g_return_if_fail (mem_chunk != NULL);
-  
-  g_free (mem);
+  g_free_chunk (mem, mem_chunk->chunk_size);
 }
 
 void	g_mem_chunk_clean	(GMemChunk *mem_chunk)	{}
 void	g_mem_chunk_reset	(GMemChunk *mem_chunk)	{}
-void	g_mem_chunk_print	(GMemChunk *mem_chunk)	{}
-void	g_mem_chunk_info	(void)			{}
-void	g_blow_chunks		(void)			{}
 
-#endif /* DISABLE_MEM_POOLS */
+void
+g_mem_chunk_print (GMemChunk *mem_chunk)
+{
+  if (mem_chunk->depot)
+    g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO,
+	   "%s: using depot %d", mem_chunk->name, mem_chunk->chunk_size);
+  else
+    g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO,
+	   "%s: using malloc", mem_chunk->name);
+}
+
+void
+g_mem_chunk_info (void)			
+{
+  gint i;
+  
+  for (i = 0; i < 16; i++)
+    print_depot_info (&depots[i]);
+}
+ 
+void g_blow_chunks (void) {}
 
 
 /* generic allocators
@@ -1268,12 +1256,10 @@
 void
 _g_mem_thread_init (void)
 {
-#ifndef DISABLE_MEM_POOLS
-  mem_chunks_lock = g_mutex_new ();
-#endif
 #ifndef G_DISABLE_CHECKS
   g_profile_mutex = g_mutex_new ();
 #endif
+  initialize_depots ();
 }
 
 void
Index: glib/gmem.h
===================================================================
RCS file: /cvs/gnome/glib/glib/gmem.h,v
retrieving revision 1.12
diff -u -r1.12 gmem.h
--- glib/gmem.h	22 Mar 2005 04:09:16 -0000	1.12
+++ glib/gmem.h	27 Sep 2005 17:25:31 -0000
@@ -55,6 +55,13 @@
 gpointer g_try_realloc    (gpointer	 mem,
 			   gulong	 n_bytes);
 
+gpointer g_alloc_chunk     (gint     chunk_size);
+gpointer g_alloc0_chunk    (gint     chunk_size);
+void     g_free_chunk      (gpointer mem,
+	                    gint     chunk_size);
+void     g_free_chunk_list (gpointer mem,
+	                    gint     chunk_size);
+
 
 /* Convenience memory allocators
  */
Index: glib/gthread.c
===================================================================
RCS file: /cvs/gnome/glib/glib/gthread.c,v
retrieving revision 1.45
diff -u -r1.45 gthread.c
--- glib/gthread.c	12 Jul 2005 16:56:51 -0000	1.45
+++ glib/gthread.c	27 Sep 2005 17:25:31 -0000
@@ -76,6 +76,8 @@
 {
   GThread thread;
   gpointer private_data;
+  gpointer mem_private;
+  GRealThread *next;
   gpointer retval;
   GSystemThread system_thread;
 };
@@ -126,7 +128,7 @@
 static GMutex   *g_once_mutex = NULL;
 static GCond    *g_once_cond = NULL;
 static GPrivate *g_thread_specific_private = NULL;
-static GSList   *g_thread_all_threads = NULL;
+static GRealThread *g_thread_all_threads = NULL;
 static GSList   *g_thread_free_indeces = NULL;
 
 G_LOCK_DEFINE_STATIC (g_thread);
@@ -465,7 +467,7 @@
 g_static_private_free (GStaticPrivate *private_key)
 {
   guint index = private_key->index;
-  GSList *list;
+  GRealThread *thread;
 
   if (!index)
     return;
@@ -473,12 +475,12 @@
   private_key->index = 0;
 
   G_LOCK (g_thread);
-  list =  g_thread_all_threads;
-  while (list)
+  
+  thread = g_thread_all_threads;
+  while (thread)
     {
-      GRealThread *thread = list->data;
       GArray *array = thread->private_data;
-      list = list->next;
+      thread = thread->next;
 
       if (array && index <= array->len)
 	{
@@ -529,8 +531,20 @@
          it is, the structure is freed in g_thread_join */
       if (!thread->thread.joinable)
 	{
+	  GRealThread *t, *p;
+
 	  G_LOCK (g_thread);
-	  g_thread_all_threads = g_slist_remove (g_thread_all_threads, data);
+	  for (t = g_thread_all_threads, p = NULL; t; p = t, t = t->next)
+	    {
+	      if (t == thread)
+		{
+		  if (p)
+		    p->next = t->next;
+		  else
+		    g_thread_all_threads = t->next;
+		  break;
+		}
+	    }
 	  G_UNLOCK (g_thread);
 	  
 	  /* Just to make sure, this isn't used any more */
@@ -581,7 +595,7 @@
   g_return_val_if_fail (priority >= G_THREAD_PRIORITY_LOW, NULL);
   g_return_val_if_fail (priority <= G_THREAD_PRIORITY_URGENT, NULL);
   
-  result = g_new (GRealThread, 1);
+  result = g_new0 (GRealThread, 1);
 
   result->thread.joinable = joinable;
   result->thread.priority = priority;
@@ -592,7 +606,8 @@
   G_THREAD_UF (thread_create, (g_thread_create_proxy, result, 
 			       stack_size, joinable, bound, priority,
 			       &result->system_thread, &local_error));
-  g_thread_all_threads = g_slist_prepend (g_thread_all_threads, result);
+  result->next = g_thread_all_threads;
+  g_thread_all_threads = result;
   G_UNLOCK (g_thread);
 
   if (local_error)
@@ -617,6 +632,7 @@
 g_thread_join (GThread* thread)
 {
   GRealThread* real = (GRealThread*) thread;
+  GRealThread *t, *p;
   gpointer retval;
 
   g_return_val_if_fail (thread, NULL);
@@ -629,7 +645,17 @@
   retval = real->retval;
 
   G_LOCK (g_thread);
-  g_thread_all_threads = g_slist_remove (g_thread_all_threads, thread);
+  for (t = g_thread_all_threads, p = NULL; t; p = t, t = t->next)
+    {
+      if (t == thread)
+	{
+	  if (p)
+	    p->next = t->next;
+	  else
+	    g_thread_all_threads = t->next;
+	  break;
+	}
+    }
   G_UNLOCK (g_thread);
 
   /* Just to make sure, this isn't used any more */
@@ -672,7 +698,7 @@
       /* If no thread data is available, provide and set one.  This
          can happen for the main thread and for threads, that are not
          created by GLib. */
-      thread = g_new (GRealThread, 1);
+      thread = g_new0 (GRealThread, 1);
       thread->thread.joinable = FALSE; /* This is a save guess */
       thread->thread.priority = G_THREAD_PRIORITY_NORMAL; /* This is
 							     just a guess */
@@ -686,7 +712,8 @@
       g_private_set (g_thread_specific_private, thread); 
       
       G_LOCK (g_thread);
-      g_thread_all_threads = g_slist_prepend (g_thread_all_threads, thread);
+      thread->next = g_thread_all_threads;
+      g_thread_all_threads = thread;
       G_UNLOCK (g_thread);
     }
   
@@ -839,6 +866,44 @@
       lock->write_cond = NULL;
     }
   g_static_mutex_free (&lock->mutex);
+}
+
+/*
+ * Memory allocation can't use the regular GPrivate 
+ * API, since that relies on GArray, which uses
+ * chunked memory. 
+ */
+gpointer
+_g_thread_mem_private_get (GThread *thread)
+{
+  GRealThread *real_thread = (GRealThread*) thread;
+
+  return real_thread->mem_private;
+}
+
+void
+_g_thread_mem_private_set (GThread *thread,
+			   gpointer data)
+{
+  GRealThread *real_thread = (GRealThread*) thread;
+
+  real_thread->mem_private = data;
+}
+
+/*
+ * This function is only used for diagnostic output
+ * in gmem.c
+ */
+void
+_g_thread_foreach (GFunc    func, 
+		   gpointer data)
+{
+  GRealThread *thread;
+
+  for (thread = g_thread_all_threads; thread; thread = thread->next)
+    {
+      (*func) (thread, data);
+    }
 }
 
 #define __G_THREAD_C__
