Re: [patch] mem_node shrink #2

[Dmitry Antipov]

Richard Stallman wrote:
> It looks good to me, except that here
>
>     +  /* Size of allocated region.  */
>     +  unsigned size : MEM_NODE_SIZE_WIDTH;
>
> The comment should explain WHY it is defined that way.

OK. BTW, is there a (supported) system where gmalloc.c is still used ?

Dmitry

Index: alloc.c
===================================================================
RCS file: /sources/emacs/emacs/src/alloc.c,v
retrieving revision 1.432
diff -u -r1.432 alloc.c
--- alloc.c     16 Nov 2007 21:24:59 -0000      1.432
+++ alloc.c     29 Nov 2007 15:39:56 -0000
@@ -430,6 +430,19 @@
    description of red-black trees.  Any book worth its salt should
    describe them.  */
 
+#ifdef GC_MALLOC_CHECK
+/* If this is defined, xmalloc and xrealloc calls mem_insert.  On 64-bit
+   system, if neither USE_MMAP_FOR_BUFFERS nor REL_ALLOC are used, xmalloc
+   or xrealloc may allocate buffer text which size fits into integer, but
+   not into BITS_PER_INT - 4 bits wide bit field.  */
+#define MEM_NODE_SIZE_WIDTH (BITS_PER_EMACS_INT - 4)
+#else
+/* Otherwise, every region which is passed to mem_insert is never larger
+   than 256M, so it's size fits into BITS_PER_INT - 4 bits wide bit field.  */
+#define MEM_NODE_SIZE_WIDTH (BITS_PER_INT - 4)
+#endif
+#define MEM_NODE_SIZE_MAX ((1 << MEM_NODE_SIZE_WIDTH) - 1)
+
 struct mem_node
 {
   /* Children of this node.  These pointers are never NULL.  When there
@@ -439,14 +452,20 @@
   /* The parent of this node.  In the root node, this is NULL.  */
   struct mem_node *parent;
 
-  /* Start and end of allocated region.  */
-  void *start, *end;
+  /* Start of allocated region.  */
+  void *start;
+
+  /* Size of allocated region.  It's defined in such a way to pack the
+     rest of mem_node data within single integer, but still provide
+     the space enough to hold any acceptable size value.  */
+  unsigned size : MEM_NODE_SIZE_WIDTH;
 
   /* Node color.  */
-  enum {MEM_BLACK, MEM_RED} color;
+  enum {MEM_BLACK, MEM_RED} color : 1;
 
-  /* Memory type.  */
-  enum mem_type type;
+  /* Memory type.  The width of this bitfield should be
+     enough to hold any possible mem_type value.  */
+  enum mem_type type : 3;
 };
 
 /* Base address of stack.  Set in main.  */
@@ -480,7 +499,7 @@
 static void mark_maybe_object P_ ((Lisp_Object));
 static void mark_memory P_ ((void *, void *, int));
 static void mem_init P_ ((void));
-static struct mem_node *mem_insert P_ ((void *, void *, enum mem_type));
+static struct mem_node *mem_insert P_ ((void *, size_t, enum mem_type));
 static void mem_insert_fixup P_ ((struct mem_node *));
 static void mem_rotate_left P_ ((struct mem_node *));
 static void mem_rotate_right P_ ((struct mem_node *));
@@ -781,9 +800,16 @@
   register POINTER_TYPE *val;
 
   MALLOC_BLOCK_INPUT;
+  /* Some mallocs returns valid pointer even if SIZE is 0.
+     We're just doing free (PTR) here.  */
+  if (size == 0)
+    {
+      free (block);
+      val = NULL;
+    }
   /* We must call malloc explicitly when BLOCK is 0, since some
      reallocs don't do this.  */
-  if (! block)
+  else if (! block)
     val = (POINTER_TYPE *) malloc (size);
   else
     val = (POINTER_TYPE *) realloc (block, size);
@@ -880,7 +906,7 @@
 
 #if GC_MARK_STACK && !defined GC_MALLOC_CHECK
   if (val && type != MEM_TYPE_NON_LISP)
-    mem_insert (val, (char *) val + nbytes, type);
+    mem_insert (val, nbytes, type);
 #endif
 
   MALLOC_UNBLOCK_INPUT;
@@ -1090,7 +1116,7 @@
 
 #if GC_MARK_STACK && !defined GC_MALLOC_CHECK
   if (val && type != MEM_TYPE_NON_LISP)
-    mem_insert (val, (char *) val + nbytes, type);
+    mem_insert (val, nbytes, type);
 #endif
 
   MALLOC_UNBLOCK_INPUT;
@@ -1263,14 +1289,13 @@
        fprintf (stderr, "Malloc returned %p which is already in use\n",
                 value);
        fprintf (stderr, "Region in use is %p...%p, %u bytes, type %d\n",
-                m->start, m->end, (char *) m->end - (char *) m->start,
-                m->type);
+                m->start, m->start + m->size, m->size, m->type);
        abort ();
       }
 
     if (!dont_register_blocks)
       {
-       mem_insert (value, (char *) value + max (1, size), allocated_mem_type);
+       mem_insert (value, size, allocated_mem_type);
        allocated_mem_type = MEM_TYPE_NON_LISP;
       }
   }
@@ -1330,9 +1355,7 @@
        fprintf (stderr, "Realloc returns memory that is already in use\n");
        abort ();
       }
-
-    /* Can't handle zero size regions in the red-black tree.  */
-    mem_insert (value, (char *) value + max (size, 1), MEM_TYPE_NON_LISP);
+    mem_insert (value, size, MEM_TYPE_NON_LISP);
   }
 
   /* fprintf (stderr, "%p <- realloc\n", value); */
@@ -3543,7 +3566,8 @@
   mem_z.left = mem_z.right = MEM_NIL;
   mem_z.parent = NULL;
   mem_z.color = MEM_BLACK;
-  mem_z.start = mem_z.end = NULL;
+  mem_z.start = NULL;
+  mem_z.size = 0;
   mem_root = MEM_NIL;
 }
 
@@ -3562,10 +3586,10 @@
 
   /* Make the search always successful to speed up the loop below.  */
   mem_z.start = start;
-  mem_z.end = (char *) start + 1;
+  mem_z.size = 1;
 
   p = mem_root;
-  while (start < p->start || start >= p->end)
+  while (start < p->start || start >= p->start + p->size)
     p = start < p->start ? p->left : p->right;
   return p;
 }
@@ -3576,16 +3600,20 @@
    pointer to the node that was inserted.  */
 
 static struct mem_node *
-mem_insert (start, end, type)
-     void *start, *end;
+mem_insert (start, size, type)
+     void *start;
+     size_t size;
      enum mem_type type;
 {
   struct mem_node *c, *parent, *x;
 
+  if (size == 0 || size > MEM_NODE_SIZE_MAX)
+    abort ();
+
   if (min_heap_address == NULL || start < min_heap_address)
     min_heap_address = start;
-  if (max_heap_address == NULL || end > max_heap_address)
-    max_heap_address = end;
+  if (max_heap_address == NULL || start + size > max_heap_address)
+    max_heap_address = start + size;
 
   /* See where in the tree a node for START belongs.  In this
      particular application, it shouldn't happen that a node is already
@@ -3597,7 +3625,7 @@
 
   while (c != MEM_NIL)
     {
-      if (start >= c->start && start < c->end)
+      if (start >= c->start && start < c->start + c->size)
        abort ();
       parent = c;
       c = start < c->start ? c->left : c->right;
@@ -3622,7 +3650,7 @@
   x = (struct mem_node *) xmalloc (sizeof *x);
 #endif
   x->start = start;
-  x->end = end;
+  x->size = size;
   x->type = type;
   x->parent = parent;
   x->left = x->right = MEM_NIL;
@@ -3835,7 +3863,7 @@
   if (y != z)
     {
       z->start = y->start;
-      z->end = y->end;
+      z->size = y->size;
       z->type = y->type;
     }