← Back to branch summary

~ubuntu-branches/ubuntu/trusty/grub2/trusty-updates

« back to all changes in this revision

Viewing changes to kern/mm.c

  • Committer: Bazaar Package Importer
  • Author(s): Colin Watson
  • Date: 2011-02-08 11:39:26 UTC
  • mfrom: (17.6.26 experimental)
  • mto: (17.6.27 experimental)
  • mto: This revision was merged to the branch mainline in revision 104.
  • Revision ID: james.westby@ubuntu.com-20110208113926-clfs90haboyk9zip
Tags: 1.99~rc1-2
https://launchpad.net/bugs/712029
https://launchpad.net/bugs/712029
* Merge 1.98+20100804-13 and 1.98+20100804-14, updating translations:
  - Kazakh (Baurzhan Muftakhidinov / Timur Birsh).
* mkconfig_skip_dmcrypt.patch: Refer to GRUB_PRELOAD_MODULES rather than
  suggesting people write a /etc/grub.d/01_modules script (thanks, Jordan
  Uggla).
* Handle empty dir passed to grub_find_root_device_from_mountinfo; fixes
  grub-mkrelpath on btrfs subvolumes (LP: #712029).
* Add rootflags=subvol=<name> if / is on a btrfs subvolume (LP: #712029).
* Upload to unstable.

Show diffs side-by-side

added added

removed removed

Lines of Context:
kern/mm.c
1
 
/* mm.c - functions for memory manager */
2
 
/*
3
 
 *  GRUB  --  GRand Unified Bootloader
4
 
 *  Copyright (C) 2002,2005,2007,2008,2009  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_zalloc
72
 
# undef grub_realloc
73
 
# undef grub_free
74
 
# undef grub_memalign
75
 
#endif
76
 
 
77
 
/* Magic words.  */
78
 
#define GRUB_MM_FREE_MAGIC      0x2d3c2808
79
 
#define GRUB_MM_ALLOC_MAGIC     0x6db08fa4
80
 
 
81
 
typedef struct grub_mm_header
82
 
{
83
 
  struct grub_mm_header *next;
84
 
  grub_size_t size;
85
 
  grub_size_t magic;
86
 
#if GRUB_CPU_SIZEOF_VOID_P == 4
87
 
  char padding[4];
88
 
#elif GRUB_CPU_SIZEOF_VOID_P == 8
89
 
  char padding[8];
90
 
#else
91
 
# error "unknown word size"
92
 
#endif
93
 
}
94
 
*grub_mm_header_t;
95
 
 
96
 
#if GRUB_CPU_SIZEOF_VOID_P == 4
97
 
# define GRUB_MM_ALIGN_LOG2     4
98
 
#elif GRUB_CPU_SIZEOF_VOID_P == 8
99
 
# define GRUB_MM_ALIGN_LOG2     5
100
 
#endif
101
 
 
102
 
#define GRUB_MM_ALIGN   (1 << GRUB_MM_ALIGN_LOG2)
103
 
 
104
 
typedef struct grub_mm_region
105
 
{
106
 
  struct grub_mm_header *first;
107
 
  struct grub_mm_region *next;
108
 
  grub_addr_t addr;
109
 
  grub_size_t size;
110
 
}
111
 
*grub_mm_region_t;
112
 
 
113
 
 
114
 
 
115
 
static grub_mm_region_t base;
116
 
 
117
 
/* Get a header from the pointer PTR, and set *P and *R to a pointer
118
 
   to the header and a pointer to its region, respectively. PTR must
119
 
   be allocated.  */
120
 
static void
121
 
get_header_from_pointer (void *ptr, grub_mm_header_t *p, grub_mm_region_t *r)
122
 
{
123
 
  if ((grub_addr_t) ptr & (GRUB_MM_ALIGN - 1))
124
 
    grub_fatal ("unaligned pointer %p", ptr);
125
 
 
126
 
  for (*r = base; *r; *r = (*r)->next)
127
 
    if ((grub_addr_t) ptr > (*r)->addr
128
 
        && (grub_addr_t) ptr <= (*r)->addr + (*r)->size)
129
 
      break;
130
 
 
131
 
  if (! *r)
132
 
    grub_fatal ("out of range pointer %p", ptr);
133
 
 
134
 
  *p = (grub_mm_header_t) ptr - 1;
135
 
  if ((*p)->magic != GRUB_MM_ALLOC_MAGIC)
136
 
    grub_fatal ("alloc magic is broken at %p", *p);
137
 
}
138
 
 
139
 
/* Initialize a region starting from ADDR and whose size is SIZE,
140
 
   to use it as free space.  */
141
 
void
142
 
grub_mm_init_region (void *addr, grub_size_t size)
143
 
{
144
 
  grub_mm_header_t h;
145
 
  grub_mm_region_t r, *p, q;
146
 
 
147
 
#if 0
148
 
  grub_printf ("Using memory for heap: start=%p, end=%p\n", addr, addr + (unsigned int) size);
149
 
#endif
150
 
 
151
 
  /* Allocate a region from the head.  */
152
 
  r = (grub_mm_region_t) ALIGN_UP ((grub_addr_t) addr, GRUB_MM_ALIGN);
153
 
  size -= (char *) r - (char *) addr + sizeof (*r);
154
 
 
155
 
  /* If this region is too small, ignore it.  */
156
 
  if (size < GRUB_MM_ALIGN)
157
 
    return;
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. Both N and
180
 
   ALIGN are in units of GRUB_MM_ALIGN.  Return a non-NULL if successful,
181
 
   otherwise return NULL.  */
182
 
static void *
183
 
grub_real_malloc (grub_mm_header_t *first, grub_size_t n, grub_size_t align)
184
 
{
185
 
  grub_mm_header_t p, q;
186
 
 
187
 
  /* When everything is allocated side effect is that *first will have alloc
188
 
     magic marked, meaning that there is no room in this region.  */
189
 
  if ((*first)->magic == GRUB_MM_ALLOC_MAGIC)
190
 
    return 0;
191
 
 
192
 
  /* Try to search free slot for allocation in this memory region.  */
193
 
  for (q = *first, p = q->next; ; q = p, p = p->next)
194
 
    {
195
 
      grub_off_t extra;
196
 
 
197
 
      extra = ((grub_addr_t) (p + 1) >> GRUB_MM_ALIGN_LOG2) % align;
198
 
      if (extra)
199
 
        extra = align - extra;
200
 
 
201
 
      if (! p)
202
 
        grub_fatal ("null in the ring");
203
 
 
204
 
      if (p->magic != GRUB_MM_FREE_MAGIC)
205
 
        grub_fatal ("free magic is broken at %p: 0x%x", p, p->magic);
206
 
 
207
 
      if (p->size >= n + extra)
208
 
        {
209
 
          if (extra == 0 && p->size == n)
210
 
            {
211
 
              /* There is no special alignment requirement and memory block
212
 
                 is complete match.
213
 
 
214
 
                 1. Just mark memory block as allocated and remove it from
215
 
                    free list.
216
 
 
217
 
                 Result:
218
 
                 +---------------+ previous block's next
219
 
                 | alloc, size=n |          |
220
 
                 +---------------+          v
221
 
               */
222
 
              q->next = p->next;
223
 
            }
224
 
          else if (align == 1 || p->size == n + extra)
225
 
            {
226
 
              /* There might be alignment requirement, when taking it into
227
 
                 account memory block fits in.
228
 
 
229
 
                 1. Allocate new area at end of memory block.
230
 
                 2. Reduce size of available blocks from original node.
231
 
                 3. Mark new area as allocated and "remove" it from free
232
 
                    list.
233
 
 
234
 
                 Result:
235
 
                 +---------------+
236
 
                 | free, size-=n | next --+
237
 
                 +---------------+        |
238
 
                 | alloc, size=n |        |
239
 
                 +---------------+        v
240
 
               */
241
 
 
242
 
              p->size -= n;
243
 
              p += p->size;
244
 
            }
245
 
          else if (extra == 0)
246
 
            {
247
 
              grub_mm_header_t r;
248
 
              
249
 
              r = p + extra + n;
250
 
              r->magic = GRUB_MM_FREE_MAGIC;
251
 
              r->size = p->size - extra - n;
252
 
              r->next = p->next;
253
 
              q->next = r;
254
 
 
255
 
              if (q == p)
256
 
                {
257
 
                  q = r;
258
 
                  r->next = r;
259
 
                }
260
 
            }
261
 
          else
262
 
            {
263
 
              /* There is alignment requirement and there is room in memory
264
 
                 block.  Split memory block to three pieces.
265
 
 
266
 
                 1. Create new memory block right after section being
267
 
                    allocated.  Mark it as free.
268
 
                 2. Add new memory block to free chain.
269
 
                 3. Mark current memory block having only extra blocks.
270
 
                 4. Advance to aligned block and mark that as allocated and
271
 
                    "remove" it from free list.
272
 
 
273
 
                 Result:
274
 
                 +------------------------------+
275
 
                 | free, size=extra             | next --+
276
 
                 +------------------------------+        |
277
 
                 | alloc, size=n                |        |
278
 
                 +------------------------------+        |
279
 
                 | free, size=orig.size-extra-n | <------+, next --+
280
 
                 +------------------------------+                  v
281
 
               */
282
 
              grub_mm_header_t r;
283
 
 
284
 
              r = p + extra + n;
285
 
              r->magic = GRUB_MM_FREE_MAGIC;
286
 
              r->size = p->size - extra - n;
287
 
              r->next = p->next;
288
 
 
289
 
              p->size = extra;
290
 
              p->next = r;
291
 
              p += extra;
292
 
            }
293
 
 
294
 
          p->magic = GRUB_MM_ALLOC_MAGIC;
295
 
          p->size = n;
296
 
 
297
 
          /* Mark find as a start marker for next allocation to fasten it.
298
 
             This will have side effect of fragmenting memory as small
299
 
             pieces before this will be un-used.  */
300
 
          *first = q;
301
 
 
302
 
          return p + 1;
303
 
        }
304
 
 
305
 
      /* Search was completed without result.  */
306
 
      if (p == *first)
307
 
        break;
308
 
    }
309
 
 
310
 
  return 0;
311
 
}
312
 
 
313
 
/* Allocate SIZE bytes with the alignment ALIGN and return the pointer.  */
314
 
void *
315
 
grub_memalign (grub_size_t align, grub_size_t size)
316
 
{
317
 
  grub_mm_region_t r;
318
 
  grub_size_t n = ((size + GRUB_MM_ALIGN - 1) >> GRUB_MM_ALIGN_LOG2) + 1;
319
 
  int count = 0;
320
 
 
321
 
  align = (align >> GRUB_MM_ALIGN_LOG2);
322
 
  if (align == 0)
323
 
    align = 1;
324
 
 
325
 
 again:
326
 
 
327
 
  for (r = base; r; r = r->next)
328
 
    {
329
 
      void *p;
330
 
 
331
 
      p = grub_real_malloc (&(r->first), n, align);
332
 
      if (p)
333
 
        return p;
334
 
    }
335
 
 
336
 
  /* If failed, increase free memory somehow.  */
337
 
  switch (count)
338
 
    {
339
 
    case 0:
340
 
      /* Invalidate disk caches.  */
341
 
      grub_disk_cache_invalidate_all ();
342
 
      count++;
343
 
      goto again;
344
 
 
345
 
    case 1:
346
 
      /* Unload unneeded modules.  */
347
 
      grub_dl_unload_unneeded ();
348
 
      count++;
349
 
      goto again;
350
 
 
351
 
    default:
352
 
      break;
353
 
    }
354
 
 
355
 
  grub_error (GRUB_ERR_OUT_OF_MEMORY, "out of memory");
356
 
  return 0;
357
 
}
358
 
 
359
 
/* Allocate SIZE bytes and return the pointer.  */
360
 
void *
361
 
grub_malloc (grub_size_t size)
362
 
{
363
 
  return grub_memalign (0, size);
364
 
}
365
 
 
366
 
/* Allocate SIZE bytes, clear them and return the pointer.  */
367
 
void *
368
 
grub_zalloc (grub_size_t size)
369
 
{
370
 
  void *ret;
371
 
 
372
 
  ret = grub_memalign (0, size);
373
 
  if (ret)
374
 
    grub_memset (ret, 0, size);
375
 
 
376
 
  return ret;
377
 
}
378
 
 
379
 
/* Deallocate the pointer PTR.  */
380
 
void
381
 
grub_free (void *ptr)
382
 
{
383
 
  grub_mm_header_t p;
384
 
  grub_mm_region_t r;
385
 
 
386
 
  if (! ptr)
387
 
    return;
388
 
 
389
 
  get_header_from_pointer (ptr, &p, &r);
390
 
 
391
 
  if (r->first->magic == GRUB_MM_ALLOC_MAGIC)
392
 
    {
393
 
      p->magic = GRUB_MM_FREE_MAGIC;
394
 
      r->first = p->next = p;
395
 
    }
396
 
  else
397
 
    {
398
 
      grub_mm_header_t q;
399
 
 
400
 
#if 0
401
 
      q = r->first;
402
 
      do
403
 
        {
404
 
          grub_printf ("%s:%d: q=%p, q->size=0x%x, q->magic=0x%x\n",
405
 
                       GRUB_FILE, __LINE__, q, q->size, q->magic);
406
 
          q = q->next;
407
 
        }
408
 
      while (q != r->first);
409
 
#endif
410
 
 
411
 
      for (q = r->first; q >= p || q->next <= p; q = q->next)
412
 
        {
413
 
          if (q->magic != GRUB_MM_FREE_MAGIC)
414
 
            grub_fatal ("free magic is broken at %p: 0x%x", q, q->magic);
415
 
 
416
 
          if (q >= q->next && (q < p || q->next > p))
417
 
            break;
418
 
        }
419
 
 
420
 
      p->magic = GRUB_MM_FREE_MAGIC;
421
 
      p->next = q->next;
422
 
      q->next = p;
423
 
 
424
 
      if (p + p->size == p->next)
425
 
        {
426
 
          if (p->next == q)
427
 
            q = p;
428
 
 
429
 
          p->next->magic = 0;
430
 
          p->size += p->next->size;
431
 
          p->next = p->next->next;
432
 
        }
433
 
 
434
 
      if (q + q->size == p)
435
 
        {
436
 
          p->magic = 0;
437
 
          q->size += p->size;
438
 
          q->next = p->next;
439
 
        }
440
 
 
441
 
      r->first = q;
442
 
    }
443
 
}
444
 
 
445
 
/* Reallocate SIZE bytes and return the pointer. The contents will be
446
 
   the same as that of PTR.  */
447
 
void *
448
 
grub_realloc (void *ptr, grub_size_t size)
449
 
{
450
 
  grub_mm_header_t p;
451
 
  grub_mm_region_t r;
452
 
  void *q;
453
 
  grub_size_t n;
454
 
 
455
 
  if (! ptr)
456
 
    return grub_malloc (size);
457
 
 
458
 
  if (! size)
459
 
    {
460
 
      grub_free (ptr);
461
 
      return 0;
462
 
    }
463
 
 
464
 
  /* FIXME: Not optimal.  */
465
 
  n = ((size + GRUB_MM_ALIGN - 1) >> GRUB_MM_ALIGN_LOG2) + 1;
466
 
  get_header_from_pointer (ptr, &p, &r);
467
 
 
468
 
  if (p->size >= n)
469
 
    return ptr;
470
 
 
471
 
  q = grub_malloc (size);
472
 
  if (! q)
473
 
    return q;
474
 
 
475
 
  grub_memcpy (q, ptr, size);
476
 
  grub_free (ptr);
477
 
  return q;
478
 
}
479
 
 
480
 
#ifdef MM_DEBUG
481
 
int grub_mm_debug = 0;
482
 
 
483
 
void
484
 
grub_mm_dump_free (void)
485
 
{
486
 
  grub_mm_region_t r;
487
 
 
488
 
  for (r = base; r; r = r->next)
489
 
    {
490
 
      grub_mm_header_t p;
491
 
 
492
 
      /* Follow the free list.  */
493
 
      p = r->first;
494
 
      do
495
 
        {
496
 
          if (p->magic != GRUB_MM_FREE_MAGIC)
497
 
            grub_fatal ("free magic is broken at %p: 0x%x", p, p->magic);
498
 
 
499
 
          grub_printf ("F:%p:%u:%p\n",
500
 
                       p, (unsigned int) p->size << GRUB_MM_ALIGN_LOG2, p->next);
501
 
          p = p->next;
502
 
        }
503
 
      while (p != r->first);
504
 
    }
505
 
 
506
 
  grub_printf ("\n");
507
 
}
508
 
 
509
 
void
510
 
grub_mm_dump (unsigned lineno)
511
 
{
512
 
  grub_mm_region_t r;
513
 
 
514
 
  grub_printf ("called at line %u\n", lineno);
515
 
  for (r = base; r; r = r->next)
516
 
    {
517
 
      grub_mm_header_t p;
518
 
 
519
 
      for (p = (grub_mm_header_t) ((r->addr + GRUB_MM_ALIGN - 1)
520
 
                                   & (~(GRUB_MM_ALIGN - 1)));
521
 
           (grub_addr_t) p < r->addr + r->size;
522
 
           p++)
523
 
        {
524
 
          switch (p->magic)
525
 
            {
526
 
            case GRUB_MM_FREE_MAGIC:
527
 
              grub_printf ("F:%p:%u:%p\n",
528
 
                           p, (unsigned int) p->size << GRUB_MM_ALIGN_LOG2, p->next);
529
 
              break;
530
 
            case GRUB_MM_ALLOC_MAGIC:
531
 
              grub_printf ("A:%p:%u\n", p, (unsigned int) p->size << GRUB_MM_ALIGN_LOG2);
532
 
              break;
533
 
            }
534
 
        }
535
 
    }
536
 
 
537
 
  grub_printf ("\n");
538
 
}
539
 
 
540
 
void *
541
 
grub_debug_malloc (const char *file, int line, grub_size_t size)
542
 
{
543
 
  void *ptr;
544
 
 
545
 
  if (grub_mm_debug)
546
 
    grub_printf ("%s:%d: malloc (0x%zx) = ", file, line, size);
547
 
  ptr = grub_malloc (size);
548
 
  if (grub_mm_debug)
549
 
    grub_printf ("%p\n", ptr);
550
 
  return ptr;
551
 
}
552
 
 
553
 
void *
554
 
grub_debug_zalloc (const char *file, int line, grub_size_t size)
555
 
{
556
 
  void *ptr;
557
 
 
558
 
  if (grub_mm_debug)
559
 
    grub_printf ("%s:%d: zalloc (0x%zx) = ", file, line, size);
560
 
  ptr = grub_zalloc (size);
561
 
  if (grub_mm_debug)
562
 
    grub_printf ("%p\n", ptr);
563
 
  return ptr;
564
 
}
565
 
 
566
 
void
567
 
grub_debug_free (const char *file, int line, void *ptr)
568
 
{
569
 
  if (grub_mm_debug)
570
 
    grub_printf ("%s:%d: free (%p)\n", file, line, ptr);
571
 
  grub_free (ptr);
572
 
}
573
 
 
574
 
void *
575
 
grub_debug_realloc (const char *file, int line, void *ptr, grub_size_t size)
576
 
{
577
 
  if (grub_mm_debug)
578
 
    grub_printf ("%s:%d: realloc (%p, 0x%zx) = ", file, line, ptr, size);
579
 
  ptr = grub_realloc (ptr, size);
580
 
  if (grub_mm_debug)
581
 
    grub_printf ("%p\n", ptr);
582
 
  return ptr;
583
 
}
584
 
 
585
 
void *
586
 
grub_debug_memalign (const char *file, int line, grub_size_t align,
587
 
                    grub_size_t size)
588
 
{
589
 
  void *ptr;
590
 
 
591
 
  if (grub_mm_debug)
592
 
    grub_printf ("%s:%d: memalign (0x%zx, 0x%zx) = ",
593
 
                 file, line, align, size);
594
 
  ptr = grub_memalign (align, size);
595
 
  if (grub_mm_debug)
596
 
    grub_printf ("%p\n", ptr);
597
 
  return ptr;
598
 
}
599
 
 
600
 
#endif /* MM_DEBUG */