[PATCH] Huge changes in mm.c

[Vincent Pelletier]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi.

In my attempt to port grub 2 to usparc, I had big problems with all the
memory allocation things, so I decided to rewrite the functions after
reading them (I wasn't able to understand at all 20% of the code).

Some comments :
It *seems* that before the alloc'ed chunks weren't linked any more with
other chunks. Now all the chunks of a region are part of the same ring.
Chunks were allocated from the end of the memory to the beginning, I
kept this behaviour.
It *seems* that the chunk headers were "forgotten" in the malloc
process, which led to my problems on usparc : a chunk was overwriting
the header of the previous one. It's now fixed.

A little schema to explain how it works :
First, we have a full free region, with the region header & chunk header:
(  free  )
[H_CHUNK ] (free, "next" points to self)
[H_REGION] ("head" always points to first chunk header)

We allocate a chunk that fit in the free space :
(alloc'ed)
[H_CHUNK ] (alloc, "next" points to free chunk)
(  free  )
[H_CHUNK ] (free, "next" points to alloc'ed chunk)
[H_REGION] (no change)

And so on.
Each chunk is 32 or 64 bits aligned (depends on arch) and his length is
a multiple of this alignment by giving some extra bytes to the alloc'ed
chunk if needed (its end is then also aligned, no byte loss).

I've added a defrag function that merges consecutive free chunks. It's
pretty fast (O(N), N=number of chunks) but I only call it when needed...
Maybe could it be interesting to call it on each grub_free().

I've added lots of dprintf calls triggered by "mm". They slows
everything down a lot...

I'm not sure where to put the 3 new prototypes, and I'm not even sure
about the name they should have. Please correct if it is wrong.

2005-07-11  Vincent Pelletier  <address@hidden>

        * kern/mm.c (GRUB_MM_ALIGN): Removed macro.  Renamed
        GRUB_MM_ALIGN_LOG2 into GRUB_MM_ALIGN.
        (grub_defragment, align_before, align_after): New functions
        and their prototypes.
        (get_header_from_pointer): Check alignment correctly.  Add
        grub_dprintf call.  Cast pointers so additions give the correct
        result.
        (grub_mm_init_region): Add dprintf calls.  Compute size before
        testing it.  Only keep regions which can contain 1 or more
        bytes.
        (grub_real_malloc): Add grub_dprintf calls.  Do some extra
        sanity checks.  Add grub_mm_dump calls.  Change "for" loop into
        "do..while".  Don't change *first value.  Keep alloc'ed headers
        in the ring.  Align beginning and end of alloc'ed chunks.
        (grub_memalign): Add grub_dprintf calls.  Add grub_mm_dump call.
        Always align.  Give the real wanted size to grub_real_malloc.
        Use grub_defragment if needed.
        (grub_free): Add grub_dprintf calls.  Do some extra sanity
        checks.  Handle GRUB_MM_ALLOC_MAGIC in the ring correctly.
        Call grub_fatal if the chunk to be freed isn't found.
        (grub_realloc): Remove useless alignment things, since they
        are handled in grub_real_malloc.  Add (disabled) experimental
        code to call grub_defragment if needed.
        (grub_mm_dump): Follow the ring to be faster.
        * include/grub/mm.h (MM_DEBUG): Changed default value to 0.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFC0mRSFEQoKRQyjtURApn4AJ9qUXY0b7w3pEZq8ctVl3dM3Sr2UgCgj2sj
MTPU8nMkchdxhf+fA1JzPVE=
=oPFJ
-----END PGP SIGNATURE-----

Index: kern/mm.c
===================================================================
RCS file: /cvsroot/grub/grub2/kern/mm.c,v
retrieving revision 1.10
diff -u -p -r1.10 mm.c
--- kern/mm.c   23 Jun 2005 08:12:19 -0000      1.10
+++ kern/mm.c   11 Jul 2005 12:19:12 -0000
@@ -46,13 +46,11 @@ typedef struct grub_mm_header
 *grub_mm_header_t;
 
 #if GRUB_CPU_SIZEOF_VOID_P == 4
-# define GRUB_MM_ALIGN_LOG2    4
+# define GRUB_MM_ALIGN 4
 #elif GRUB_CPU_SIZEOF_VOID_P == 8
-# define GRUB_MM_ALIGN_LOG2    8
+# define GRUB_MM_ALIGN 8
 #endif
 
-#define GRUB_MM_ALIGN  (1 << GRUB_MM_ALIGN_LOG2)
-
 typedef struct grub_mm_region
 {
   struct grub_mm_header *first;
@@ -64,21 +62,45 @@ typedef struct grub_mm_region
 
 
 
+void grub_defragment (grub_mm_region_t r);
+grub_addr_t align_before (grub_addr_t addr, grub_size_t align);
+grub_addr_t align_after (grub_addr_t addr, grub_size_t align);
+
 static grub_mm_region_t base;
 
+/* Align given memory address to the first valid position after addr.
+   If addr is already aligned, don't touch it.   */
+grub_addr_t align_after (grub_addr_t addr, grub_size_t align)
+{
+  if (addr % align)
+    return addr + align - ( addr % align );
+  return addr;
+}
+
+/* Align given memory address to the first valid position before addr.
+ *    If addr is already aligned, don't touch it.   */
+grub_addr_t align_before (grub_addr_t addr, grub_size_t align)
+{
+  return addr - addr % align;
+} 
+
 /* Get a header from the pointer PTR, and set *P and *R to a pointer
    to the header and a pointer to its region, respectively. PTR must
    be allocated.  */
 static void
 get_header_from_pointer (void *ptr, grub_mm_header_t *p, grub_mm_region_t *r)
 {
-  if ((grub_addr_t) ptr & (GRUB_MM_ALIGN - 1))
+  if ((grub_addr_t) ptr % GRUB_MM_ALIGN)
     grub_fatal ("unaligned pointer %p", ptr);
 
   for (*r = base; *r; *r = (*r)->next)
-    if ((grub_addr_t) ptr > (*r)->addr
-       && (grub_addr_t) ptr <= (*r)->addr + (*r)->size)
-      break;
+    {
+      grub_dprintf ("mm", "[%p..%p]\n", ((*r)->addr),
+                    ((grub_addr_t) (*r)->addr) + (*r)->size);
+      if ((grub_addr_t) ptr >= ((grub_addr_t) (*r)->addr)
+          && (grub_addr_t) ptr <= ((grub_addr_t) (*r)->addr) + (*r)->size)
+        break;
+    }
 
   if (! *r)
     grub_fatal ("out of range pointer %p", ptr);
@@ -96,27 +118,28 @@ grub_mm_init_region (void *addr, grub_si
   grub_mm_header_t h;
   grub_mm_region_t r, *p, q;
 
-#if 0
-  grub_printf ("%s:%d: addr=%p, size=%u\n", __FILE__, __LINE__, addr, size);
-#endif
-  
+  grub_dprintf ("mm", "New region (before) : %p:%x\n", addr, size);
+  r = (grub_mm_region_t) align_after ((grub_addr_t) addr, GRUB_MM_ALIGN);
+
+  size = align_before (size - sizeof (*r) -
+                       ((grub_addr_t) r - (grub_addr_t) addr),
+                     GRUB_MM_ALIGN);
+
   /* If this region is too small, ignore it.  */
-  if (size < GRUB_MM_ALIGN * 2)
+  if (size < sizeof (grub_mm_header_t) + 1)
     return;
 
-  /* Allocate a region from the head.  */
-  r = (grub_mm_region_t) (((grub_addr_t) addr + GRUB_MM_ALIGN - 1)
-                         & (~(GRUB_MM_ALIGN - 1)));
-  size -= (char *) r - (char *) addr + sizeof (*r);
-  
-  h = (grub_mm_header_t) ((char *) r + GRUB_MM_ALIGN);
+  h = (grub_mm_header_t) (r + 1);
   h->next = h;
   h->magic = GRUB_MM_FREE_MAGIC;
-  h->size = (size >> GRUB_MM_ALIGN_LOG2);
+  h->size = size - sizeof (*h);
 
   r->first = h;
   r->addr = (grub_addr_t) h;
-  r->size = (h->size << GRUB_MM_ALIGN_LOG2);
+  r->size = size;
+
+  grub_dprintf ("mm", "First header in new region : h=%p, size=%x\n",
+      h, h->size);
 
   /* Find where to insert this region. Put a smaller one before bigger ones,
      to prevent fragmentations.  */
@@ -126,6 +149,7 @@ grub_mm_init_region (void *addr, grub_si
   
   *p = r;
   r->next = q;
+  grub_dprintf ("mm", "New region (after) : %p:%x:%p\n", r, size, r->next);
 }
 
 /* Allocate the number of units N with the alignment ALIGN from the ring
@@ -134,63 +158,87 @@ grub_mm_init_region (void *addr, grub_si
 static void *
 grub_real_malloc (grub_mm_header_t *first, grub_size_t n, grub_size_t align)
 {
-  grub_mm_header_t p, q;
+  grub_mm_header_t p, q, r;
+  grub_off_t extra = align_after (n, align) - n;
 
-  if ((*first)->magic == GRUB_MM_ALLOC_MAGIC)
-    return 0;
-
-  for (q = *first, p = q->next; ; q = p, p = p->next)
+  if (! first)
+    grub_fatal ("null in the ring (at start)");
+  
+  p = *first;
+  
+  switch (p->magic)
     {
-      grub_off_t extra;
+    case GRUB_MM_ALLOC_MAGIC:
+    case GRUB_MM_FREE_MAGIC:
+      break;
+    default:
+#if MM_DEBUG
+      grub_mm_dump (__LINE__);
+#endif
+      grub_fatal ("magic is broken (at start) %p: 0x%x", p, p->magic);
+    }
 
-      extra = ((grub_addr_t) (p + 1) >> GRUB_MM_ALIGN_LOG2) % align;
-      if (extra)
-       extra = align - extra;
+  do
+    {
+      q = p;
+      p = p->next;
 
       if (! p)
        grub_fatal ("null in the ring");
 
-      if (p->magic != GRUB_MM_FREE_MAGIC)
-       grub_fatal ("free magic is broken at %p: 0x%x", p, p->magic);
-
-      if (p->size >= n + extra)
-       {
-         if (extra == 0 && p->size == n)
+      switch (p->magic)
+        {
+        case GRUB_MM_ALLOC_MAGIC:
+          break;
+        case GRUB_MM_FREE_MAGIC:
+          grub_dprintf ("mm", "Before: p %p:%x:%p\n",
+             p, p->size, p->next);
+          grub_dprintf ("mm", "Before: q %p:%x:%p\n",
+              q, q->size, q->next);
+         grub_dprintf ("mm", "Align = 0x%x Size = 0x%x Extra = 0x%x\n",
+              align, n, extra);
+         if (p->size == n + extra)
            {
-             q->next = p->next;
              p->magic = GRUB_MM_ALLOC_MAGIC;
+              grub_dprintf ("mm", "After : p %p:%x:%p\n",
+                  p, p->size, p->next);
+              grub_dprintf ("mm", "After : q %p:%x:%p\n",
+                  q, q->size, q->next);
+             return p + 1;
            }
-         else if (extra == 0 || p->size == n + extra)
+         if (p->size >= n + extra + sizeof (*r))
            {
-             p->size -= n;
-             p += p->size;
-             p->size = n;
-             p->magic = GRUB_MM_ALLOC_MAGIC;
-           }
-         else
-           {
-             grub_mm_header_t r;
-
-             r = p + extra + n;
-             r->magic = GRUB_MM_FREE_MAGIC;
-             r->size = p->size - extra - n;
-             r->next = p->next;
-             
-             p->size = extra;
-             p->next = r;
-             p += extra;
-             p->size = n;
-             p->magic = GRUB_MM_ALLOC_MAGIC;
-           }
+#if 0
+               r = (grub_mm_header_t) align_before (
+                   ((grub_addr_t) p) + p->size - (extra + n),
+                    align);
+#else
+                /* XXX: Is it safe to assume we are aligned ?  */
+                r = ((grub_addr_t) p) + p->size - (extra + n);
+#endif
+              r->magic = GRUB_MM_ALLOC_MAGIC;
+              r->size = n + extra;
+              r->next = p;
+              p->size = p->size - r->size - sizeof (*r);
+              q->next = r;
+
+              grub_dprintf ("mm", "After : p %p:%x:%p\n",
+                  p, p->size, p->next);
+              grub_dprintf ("mm", "After : q %p:%x:%p\n",
+                  q, q->size, q->next);
+              grub_dprintf ("mm", "After : r %p:%x:%p\n",
+                  r, r->size, r->next);
+              return r + 1;
+            }
+            break;
+        default:
+#if MM_DEBUG
+          grub_mm_dump (__LINE__);
+#endif
+          grub_fatal ("magic is broken at %p: 0x%x", p, p->magic);
+        }
 
-         *first = q;
-         
-         return p + 1;
-       }
-
-      if (p == *first)
-       break;
-    }
+    } while ( p != *first );
 
   return 0;
 }
@@ -200,12 +248,16 @@ void *
 grub_memalign (grub_size_t align, grub_size_t size)
 {
   grub_mm_region_t r;
-  grub_size_t n = ((size + GRUB_MM_ALIGN - 1) >> GRUB_MM_ALIGN_LOG2) + 1;
   int count = 0;
   
-  align = (align >> GRUB_MM_ALIGN_LOG2);
+#if 0
+  align = (align >> GRUB_MM_ALIGN);
   if (align == 0)
     align = 1;
+#else
+  /* XXX: Is it right to always align ?  */
+  align = GRUB_MM_ALIGN;
+#endif
 
  again:
   
@@ -213,9 +265,18 @@ grub_memalign (grub_size_t align, grub_s
     {
       void *p;
       
-      p = grub_real_malloc (&(r->first), n, align);
+      p = grub_real_malloc (&(r->first), size, align);
       if (p)
-       return p;
+        {
+         grub_dprintf("mm","%p=malloc(0x%x)\n",p,size);
+#if MM_DEBUG
+         grub_size_t a;
+         for(a = 0; a < size; a++)
+            ((char *) p)[a] = 'X'; /* To test overlapping.  */
+          grub_mm_dump (__LINE__);
+#endif
+         return p;
+        }
     }
 
   /* If failed, increase free memory somehow.  */
@@ -228,6 +289,13 @@ grub_memalign (grub_size_t align, grub_s
       goto again;
       
     case 1:
+      /* Defragment memory.  */
+      for (r = base; r; r = r->next)
+        grub_defragment (r);
+      count++;
+      goto again;
+      
+    case 2:
       /* Unload unneeded modules.  */
       grub_dl_unload_unneeded ();
       count++;
@@ -248,6 +316,43 @@ grub_malloc (grub_size_t size)
   return grub_memalign (0, size);
 }
 
+/* Aggregates consecutive free segments.  */
+void
+grub_defragment (grub_mm_region_t r)
+{
+  grub_mm_header_t p, first_free = 0;
+
+  grub_dprintf ("mm", "Defrag running...\n");
+  
+  p = r->first;
+
+  do
+    {
+      p = p->next;
+      switch (p->magic)
+        {
+        case GRUB_MM_ALLOC_MAGIC:
+          first_free = 0;
+          break;
+        case GRUB_MM_FREE_MAGIC:
+          if (first_free)
+          {
+            first_free->next = p->next;
+            first_free->size += p->size + sizeof (*p);
+          }
+          else
+            first_free = p;
+          break;
+        default:
+#if MM_DEBUG
+          grub_mm_dump (__LINE__);
+#endif
+          grub_fatal ("magic is broken at %p: 0x%x", p, p->magic);
+        }
+    } while ( p != r->first );
+  grub_dprintf ("mm", "Done.\n");
+}
+
 /* Deallocate the pointer PTR.  */
 void
 grub_free (void *ptr)
@@ -258,60 +363,44 @@ grub_free (void *ptr)
   if (! ptr)
     return;
 
+  grub_dprintf ("mm", "free(%p)\n", ptr);
+  
   get_header_from_pointer (ptr, &p, &r);
 
-  if (r->first->magic == GRUB_MM_ALLOC_MAGIC)
-    {
-      p->magic = GRUB_MM_FREE_MAGIC;
-      r->first = p->next = p;
-    }
-  else
+  p = r->first;
+
+  do
     {
-      grub_mm_header_t q;
+      p = p->next;
 
-#if 0
-      q = r->first;
-      do
-       {
-         grub_printf ("%s:%d: q=%p, q->size=0x%x, q->magic=0x%x\n",
-                      __FILE__, __LINE__, q, q->size, q->magic);
-         q = q->next;
-       }
-      while (q != r->first);
+      if (! p)
+       grub_fatal ("null in the ring");
+
+      switch (p->magic)
+        {
+        case GRUB_MM_ALLOC_MAGIC:
+          if (p + 1 != ptr)
+            continue;
+          else
+            {
+              p->magic = GRUB_MM_FREE_MAGIC;
+#if MM_DEBUG
+              grub_mm_dump (__LINE__);
+#endif     
+              return;
+            }
+        case GRUB_MM_FREE_MAGIC:
+          continue;
+        default:
+#if MM_DEBUG
+          grub_mm_dump (__LINE__);
 #endif
-      
-      for (q = r->first; q >= p || q->next <= p; q = q->next)
-       {
-         if (q->magic != GRUB_MM_FREE_MAGIC)
-           grub_fatal ("free magic is broken at %p: 0x%x", q, q->magic);
-         
-         if (q >= q->next && (q < p || q->next > p))
-           break;
-       }
-
-      p->magic = GRUB_MM_FREE_MAGIC;
-      p->next = q->next;
-      q->next = p;
-      
-      if (p + p->size == p->next)
-       {
-         if (p->next == q)
-           q = p;
+          grub_fatal ("magic is broken at %p: 0x%x", p, p->magic);
+        }
+    } while ( p != r->first );
 
-         p->next->magic = 0;
-         p->size += p->next->size;
-         p->next = p->next->next;
-       }
-      
-      if (q + q->size == p)
-       {
-         p->magic = 0;
-         q->size += p->size;
-         q->next = p->next;
-       }
+  grub_fatal ("alloc'ed chunk not found");
 
-      r->first = q;
-    }
 }
 
 /* Reallocate SIZE bytes and return the pointer. The contents will be
@@ -322,7 +411,6 @@ grub_realloc (void *ptr, grub_size_t siz
   grub_mm_header_t p;
   grub_mm_region_t r;
   void *q;
-  grub_size_t n;
   
   if (! ptr)
     return grub_malloc (size);
@@ -334,18 +422,33 @@ grub_realloc (void *ptr, grub_size_t siz
     }
 
   /* FIXME: Not optimal.  */
-  n = ((size + GRUB_MM_ALIGN - 1) >> GRUB_MM_ALIGN_LOG2) + 1;
   get_header_from_pointer (ptr, &p, &r);
   
-  if (p->size >= n)
+  if (p->size >= size)
     return ptr;
+
+#if 0 /* XXX: Experimental.  */
+  if(p->next->magic == GRUB_MM_FREE_MAGIC)
+    {
+      if (p->size + p->next->size < size)
+        grub_defragment (r); /* Try to increase the free space.  */
+      
+      if (p->size + p->next->size >= size)
+        {
+          grub_size_t delta = size - p->size;
+          p->next->size -= delta;
+          p->size += delta;
+          grub_memcpy (p->next, p->next + delta, sizeof(*p));
+        }
+    }
+#endif
   
   q = grub_malloc (size);
-  if (! q)
-    return q;
-  
-  grub_memcpy (q, ptr, size);
-  grub_free (ptr);
+  if (q)
+    {
+      grub_memcpy (q, ptr, size);
+      grub_free (ptr);
+    }
   return q;
 }
 
@@ -354,28 +457,29 @@ void
 grub_mm_dump (unsigned lineno)
 {
   grub_mm_region_t r;
+  grub_mm_header_t p;
 
-  grub_printf ("called at line %u\n", lineno);
+  grub_printf ("Dump called at line %u\n", lineno);
   for (r = base; r; r = r->next)
     {
-      grub_mm_header_t p;
-      
-      for (p = (grub_mm_header_t) ((r->addr + GRUB_MM_ALIGN - 1)
-                                  & (~(GRUB_MM_ALIGN - 1)));
-          (grub_addr_t) p < r->addr + r->size;
-          p++)
+      p = r->first;
+      do
        {
          switch (p->magic)
            {
            case GRUB_MM_FREE_MAGIC:
-             grub_printf ("F:%p:%u:%p\n",
-                          p, p->size << GRUB_MM_ALIGN_LOG2, p->next);
+             grub_printf ("F:%p:%x:%p\n",
+                          p, (grub_uintn_t) p->size, p->next);
              break;
            case GRUB_MM_ALLOC_MAGIC:
-             grub_printf ("A:%p:%u\n", p, p->size << GRUB_MM_ALIGN_LOG2);
+             grub_printf ("A:%p:%x:%p\n", p, (grub_uintn_t) p->size, p->next);
              break;
+            default:
+              grub_printf ("magic broken at %p\n", p);
+              return; /* XXX: A little rough.  */
            }
-       }
+          p = p->next;
+       } while (p != r->first);
     }
 
   grub_printf ("\n");
Index: include/grub/mm.h
===================================================================
RCS file: /cvsroot/grub/grub2/include/grub/mm.h,v
retrieving revision 1.4
diff -u -p -r1.4 mm.h
--- include/grub/mm.h   20 Jan 2005 17:25:39 -0000      1.4
+++ include/grub/mm.h   11 Jul 2005 12:19:12 -0000
@@ -31,7 +31,7 @@ void *EXPORT_FUNC(grub_realloc) (void *p
 void *EXPORT_FUNC(grub_memalign) (grub_size_t align, grub_size_t size);
 
 /* For debugging.  */
-#define MM_DEBUG       1
+#define MM_DEBUG       0
 #if MM_DEBUG
 void grub_mm_dump (unsigned lineno);
 #endif