kern/mm.c

   1 /* mm.c - functions for memory manager */
   2 /*
   3  *  GRUB  --  GRand Unified Bootloader
   4  *  Copyright (C) 2002,2005,2007  Free Software Foundation, Inc.
   5  *
   6  *  GRUB is free software: you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation, either version 3 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  GRUB is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
  18  */
  19
  20 /*
  21   The design of this memory manager.
  22
  23   This is a simple implementation of malloc with a few extensions. These are
  24   the extensions:
  25
  26   - memalign is implemented efficiently.
  27
  28   - multiple regions may be used as free space. They may not be
  29   contiguous.
  30
  31   Regions are managed by a singly linked list, and the meta information is
  32   stored in the beginning of each region. Space after the meta information
  33   is used to allocate memory.
  34
  35   The memory space is used as cells instead of bytes for simplicity. This
  36   is important for some CPUs which may not access multiple bytes at a time
  37   when the first byte is not aligned at a certain boundary (typically,
  38   4-byte or 8-byte). The size of each cell is equal to the size of struct
  39   grub_mm_header, so the header of each allocated/free block fits into one
  40   cell precisely. One cell is 16 bytes on 32-bit platforms and 32 bytes
  41   on 64-bit platforms.
  42
  43   There are two types of blocks: allocated blocks and free blocks.
  44
  45   In allocated blocks, the header of each block has only its size. Note that
  46   this size is based on cells but not on bytes. The header is located right
  47   before the returned pointer, that is, the header resides at the previous
  48   cell.
  49
  50   Free blocks constitutes a ring, using a singly linked list. The first free
  51   block is pointed to by the meta information of a region. The allocator
  52   attempts to pick up the second block instead of the first one. This is
  53   a typical optimization against defragmentation, and makes the
  54   implementation a bit easier.
  55
  56   For safety, both allocated blocks and free ones are marked by magic
  57   numbers. Whenever anything unexpected is detected, GRUB aborts the
  58   operation.
  59  */
  60
  61 #include <config.h>
  62 #include <grub/mm.h>
  63 #include <grub/misc.h>
  64 #include <grub/err.h>
  65 #include <grub/types.h>
  66 #include <grub/disk.h>
  67 #include <grub/dl.h>
  68
  69 #ifdef MM_DEBUG
  70 # undef grub_malloc
  71 # undef grub_realloc
  72 # undef grub_free
  73 # undef grub_memalign
  74 #endif
  75
  76 /* Magic words.  */
  77 #define GRUB_MM_FREE_MAGIC      0x2d3c2808
  78 #define GRUB_MM_ALLOC_MAGIC     0x6db08fa4
  79
  80 typedef struct grub_mm_header
  81 {
  82   struct grub_mm_header *next;
  83   grub_size_t size;
  84   grub_size_t magic;
  85 #if GRUB_CPU_SIZEOF_VOID_P == 4
  86   char padding[4];
  87 #elif GRUB_CPU_SIZEOF_VOID_P == 8
  88   char padding[8];
  89 #else
  90 # error "unknown word size"
  91 #endif
  92 }
  93 *grub_mm_header_t;
  94
  95 #if GRUB_CPU_SIZEOF_VOID_P == 4
  96 # define GRUB_MM_ALIGN_LOG2     4
  97 #elif GRUB_CPU_SIZEOF_VOID_P == 8
  98 # define GRUB_MM_ALIGN_LOG2     5
  99 #endif
 100
 101 #define GRUB_MM_ALIGN   (1 << GRUB_MM_ALIGN_LOG2)
 102
 103 typedef struct grub_mm_region
 104 {
 105   struct grub_mm_header *first;
 106   struct grub_mm_region *next;
 107   grub_addr_t addr;
 108   grub_size_t size;
 109 }
 110 *grub_mm_region_t;
 111
 112 \f
 113
 114 static grub_mm_region_t base;
 115
 116 /* Get a header from the pointer PTR, and set *P and *R to a pointer
 117    to the header and a pointer to its region, respectively. PTR must
 118    be allocated.  */
 119 static void
 120 get_header_from_pointer (void *ptr, grub_mm_header_t *p, grub_mm_region_t *r)
 121 {
 122   if ((grub_addr_t) ptr & (GRUB_MM_ALIGN - 1))
 123     grub_fatal ("unaligned pointer %p", ptr);
 124
 125   for (*r = base; *r; *r = (*r)->next)
 126     if ((grub_addr_t) ptr > (*r)->addr
 127         && (grub_addr_t) ptr <= (*r)->addr + (*r)->size)
 128       break;
 129
 130   if (! *r)
 131     grub_fatal ("out of range pointer %p", ptr);
 132
 133   *p = (grub_mm_header_t) ptr - 1;
 134   if ((*p)->magic != GRUB_MM_ALLOC_MAGIC)
 135     grub_fatal ("alloc magic is broken at %p", *p);
 136 }
 137
 138 /* Initialize a region starting from ADDR and whose size is SIZE,
 139    to use it as free space.  */
 140 void
 141 grub_mm_init_region (void *addr, grub_size_t size)
 142 {
 143   grub_mm_header_t h;
 144   grub_mm_region_t r, *p, q;
 145
 146 #if 0
 147   grub_printf ("Using memory for heap: start=%p, end=%p\n", addr, addr + (unsigned int) size);
 148 #endif
 149
 150   /* If this region is too small, ignore it.  */
 151   if (size < GRUB_MM_ALIGN * 2)
 152     return;
 153
 154   /* Allocate a region from the head.  */
 155   r = (grub_mm_region_t) (((grub_addr_t) addr + GRUB_MM_ALIGN - 1)
 156                           & (~(GRUB_MM_ALIGN - 1)));
 157   size -= (char *) r - (char *) addr + sizeof (*r);
 158
 159   h = (grub_mm_header_t) ((char *) r + GRUB_MM_ALIGN);
 160   h->next = h;
 161   h->magic = GRUB_MM_FREE_MAGIC;
 162   h->size = (size >> GRUB_MM_ALIGN_LOG2);
 163
 164   r->first = h;
 165   r->addr = (grub_addr_t) h;
 166   r->size = (h->size << GRUB_MM_ALIGN_LOG2);
 167
 168   /* Find where to insert this region. Put a smaller one before bigger ones,
 169      to prevent fragmentation.  */
 170   for (p = &base, q = *p; q; p = &(q->next), q = *p)
 171     if (q->size > r->size)
 172       break;
 173
 174   *p = r;
 175   r->next = q;
 176 }
 177
 178 /* Allocate the number of units N with the alignment ALIGN from the ring
 179    buffer starting from *FIRST. ALIGN must be a power of two. Return a
 180    non-NULL if successful, otherwise return NULL.  */
 181 static void *
 182 grub_real_malloc (grub_mm_header_t *first, grub_size_t n, grub_size_t align)
 183 {
 184   grub_mm_header_t p, q;
 185
 186   if ((*first)->magic == GRUB_MM_ALLOC_MAGIC)
 187     return 0;
 188
 189   for (q = *first, p = q->next; ; q = p, p = p->next)
 190     {
 191       grub_off_t extra;
 192
 193       extra = ((grub_addr_t) (p + 1) >> GRUB_MM_ALIGN_LOG2) % align;
 194       if (extra)
 195         extra = align - extra;
 196
 197       if (! p)
 198         grub_fatal ("null in the ring");
 199
 200       if (p->magic != GRUB_MM_FREE_MAGIC)
 201         grub_fatal ("free magic is broken at %p: 0x%x", p, p->magic);
 202
 203       if (p->size >= n + extra)
 204         {
 205           if (extra == 0 && p->size == n)
 206             {
 207               q->next = p->next;
 208               p->magic = GRUB_MM_ALLOC_MAGIC;
 209             }
 210           else if (extra == 0 || p->size == n + extra)
 211             {
 212               p->size -= n;
 213               p += p->size;
 214               p->size = n;
 215               p->magic = GRUB_MM_ALLOC_MAGIC;
 216             }
 217           else
 218             {
 219               grub_mm_header_t r;
 220
 221               r = p + extra + n;
 222               r->magic = GRUB_MM_FREE_MAGIC;
 223               r->size = p->size - extra - n;
 224               r->next = p->next;
 225
 226               p->size = extra;
 227               p->next = r;
 228               p += extra;
 229               p->size = n;
 230               p->magic = GRUB_MM_ALLOC_MAGIC;
 231             }
 232
 233           *first = q;
 234
 235           return p + 1;
 236         }
 237
 238       if (p == *first)
 239         break;
 240     }
 241
 242   return 0;
 243 }
 244
 245 /* Allocate SIZE bytes with the alignment ALIGN and return the pointer.  */
 246 void *
 247 grub_memalign (grub_size_t align, grub_size_t size)
 248 {
 249   grub_mm_region_t r;
 250   grub_size_t n = ((size + GRUB_MM_ALIGN - 1) >> GRUB_MM_ALIGN_LOG2) + 1;
 251   int count = 0;
 252
 253   align = (align >> GRUB_MM_ALIGN_LOG2);
 254   if (align == 0)
 255     align = 1;
 256
 257  again:
 258
 259   for (r = base; r; r = r->next)
 260     {
 261       void *p;
 262
 263       p = grub_real_malloc (&(r->first), n, align);
 264       if (p)
 265         return p;
 266     }
 267
 268   /* If failed, increase free memory somehow.  */
 269   switch (count)
 270     {
 271     case 0:
 272       /* Invalidate disk caches.  */
 273       grub_disk_cache_invalidate_all ();
 274       count++;
 275       goto again;
 276
 277     case 1:
 278       /* Unload unneeded modules.  */
 279       grub_dl_unload_unneeded ();
 280       count++;
 281       goto again;
 282
 283     default:
 284       break;
 285     }
 286
 287   grub_error (GRUB_ERR_OUT_OF_MEMORY, "out of memory");
 288   return 0;
 289 }
 290
 291 /* Allocate SIZE bytes and return the pointer.  */
 292 void *
 293 grub_malloc (grub_size_t size)
 294 {
 295   return grub_memalign (0, size);
 296 }
 297
 298 /* Deallocate the pointer PTR.  */
 299 void
 300 grub_free (void *ptr)
 301 {
 302   grub_mm_header_t p;
 303   grub_mm_region_t r;
 304
 305   if (! ptr)
 306     return;
 307
 308   get_header_from_pointer (ptr, &p, &r);
 309
 310   if (r->first->magic == GRUB_MM_ALLOC_MAGIC)
 311     {
 312       p->magic = GRUB_MM_FREE_MAGIC;
 313       r->first = p->next = p;
 314     }
 315   else
 316     {
 317       grub_mm_header_t q;
 318
 319 #if 0
 320       q = r->first;
 321       do
 322         {
 323           grub_printf ("%s:%d: q=%p, q->size=0x%x, q->magic=0x%x\n",
 324                        __FILE__, __LINE__, q, q->size, q->magic);
 325           q = q->next;
 326         }
 327       while (q != r->first);
 328 #endif
 329
 330       for (q = r->first; q >= p || q->next <= p; q = q->next)
 331         {
 332           if (q->magic != GRUB_MM_FREE_MAGIC)
 333             grub_fatal ("free magic is broken at %p: 0x%x", q, q->magic);
 334
 335           if (q >= q->next && (q < p || q->next > p))
 336             break;
 337         }
 338
 339       p->magic = GRUB_MM_FREE_MAGIC;
 340       p->next = q->next;
 341       q->next = p;
 342
 343       if (p + p->size == p->next)
 344         {
 345           if (p->next == q)
 346             q = p;
 347
 348           p->next->magic = 0;
 349           p->size += p->next->size;
 350           p->next = p->next->next;
 351         }
 352
 353       if (q + q->size == p)
 354         {
 355           p->magic = 0;
 356           q->size += p->size;
 357           q->next = p->next;
 358         }
 359
 360       r->first = q;
 361     }
 362 }
 363
 364 /* Reallocate SIZE bytes and return the pointer. The contents will be
 365    the same as that of PTR.  */
 366 void *
 367 grub_realloc (void *ptr, grub_size_t size)
 368 {
 369   grub_mm_header_t p;
 370   grub_mm_region_t r;
 371   void *q;
 372   grub_size_t n;
 373
 374   if (! ptr)
 375     return grub_malloc (size);
 376
 377   if (! size)
 378     {
 379       grub_free (ptr);
 380       return 0;
 381     }
 382
 383   /* FIXME: Not optimal.  */
 384   n = ((size + GRUB_MM_ALIGN - 1) >> GRUB_MM_ALIGN_LOG2) + 1;
 385   get_header_from_pointer (ptr, &p, &r);
 386
 387   if (p->size >= n)
 388     return ptr;
 389
 390   q = grub_malloc (size);
 391   if (! q)
 392     return q;
 393
 394   grub_memcpy (q, ptr, size);
 395   grub_free (ptr);
 396   return q;
 397 }
 398
 399 #ifdef MM_DEBUG
 400 int grub_mm_debug = 0;
 401
 402 void
 403 grub_mm_dump_free (void)
 404 {
 405   grub_mm_region_t r;
 406
 407   for (r = base; r; r = r->next)
 408     {
 409       grub_mm_header_t p;
 410
 411       /* Follow the free list.  */
 412       p = r->first;
 413       do
 414         {
 415           if (p->magic != GRUB_MM_FREE_MAGIC)
 416             grub_fatal ("free magic is broken at %p: 0x%x", p, p->magic);
 417
 418           grub_printf ("F:%p:%u:%p\n",
 419                        p, (unsigned int) p->size << GRUB_MM_ALIGN_LOG2, p->next);
 420           p = p->next;
 421         }
 422       while (p != r->first);
 423     }
 424
 425   grub_printf ("\n");
 426 }
 427
 428 void
 429 grub_mm_dump (unsigned lineno)
 430 {
 431   grub_mm_region_t r;
 432
 433   grub_printf ("called at line %u\n", lineno);
 434   for (r = base; r; r = r->next)
 435     {
 436       grub_mm_header_t p;
 437
 438       for (p = (grub_mm_header_t) ((r->addr + GRUB_MM_ALIGN - 1)
 439                                    & (~(GRUB_MM_ALIGN - 1)));
 440            (grub_addr_t) p < r->addr + r->size;
 441            p++)
 442         {
 443           switch (p->magic)
 444             {
 445             case GRUB_MM_FREE_MAGIC:
 446               grub_printf ("F:%p:%u:%p\n",
 447                            p, (unsigned int) p->size << GRUB_MM_ALIGN_LOG2, p->next);
 448               break;
 449             case GRUB_MM_ALLOC_MAGIC:
 450               grub_printf ("A:%p:%u\n", p, (unsigned int) p->size << GRUB_MM_ALIGN_LOG2);
 451               break;
 452             }
 453         }
 454     }
 455
 456   grub_printf ("\n");
 457 }
 458
 459 void *
 460 grub_debug_malloc (const char *file, int line, grub_size_t size)
 461 {
 462   void *ptr;
 463
 464   if (grub_mm_debug)
 465     grub_printf ("%s:%d: malloc (0x%x) = ", file, line, size);
 466   ptr = grub_malloc (size);
 467   if (grub_mm_debug)
 468     grub_printf ("%p\n", ptr);
 469   return ptr;
 470 }
 471
 472 void
 473 grub_debug_free (const char *file, int line, void *ptr)
 474 {
 475   if (grub_mm_debug)
 476     grub_printf ("%s:%d: free (%p)\n", file, line, ptr);
 477   grub_free (ptr);
 478 }
 479
 480 void *
 481 grub_debug_realloc (const char *file, int line, void *ptr, grub_size_t size)
 482 {
 483   if (grub_mm_debug)
 484     grub_printf ("%s:%d: realloc (%p, 0x%x) = ", file, line, ptr, size);
 485   ptr = grub_realloc (ptr, size);
 486   if (grub_mm_debug)
 487     grub_printf ("%p\n", ptr);
 488   return ptr;
 489 }
 490
 491 void *
 492 grub_debug_memalign (const char *file, int line, grub_size_t align,
 493                     grub_size_t size)
 494 {
 495   void *ptr;
 496
 497   if (grub_mm_debug)
 498     grub_printf ("%s:%d: memalign (0x%x, 0x%x) = ",
 499                  file, line, align, size);
 500   ptr = grub_memalign (align, size);
 501   if (grub_mm_debug)
 502     grub_printf ("%p\n", ptr);
 503   return ptr;
 504 }
 505
 506 #endif /* MM_DEBUG */