← Back to branch summary

~hamo/ubuntu/precise/grub2/grub2.hi_res

« back to all changes in this revision

Viewing changes to grub-core/kern/mm.c

  • Committer: Bazaar Package Importer
  • Author(s): Colin Watson, Colin Watson, Robert Millan, Updated translations
  • Date: 2010-11-22 12:24:56 UTC
  • mfrom: (1.26.4 upstream) (17.3.36 sid)
  • mto: (17.3.43 sid)
  • mto: This revision was merged to the branch mainline in revision 89.
  • Revision ID: james.westby@ubuntu.com-20101122122456-y82z3sfb7k4zfdcc
Tags: 1.99~20101122-1
http://bugs.debian.org/550658
http://bugs.debian.org/550702
http://bugs.debian.org/591416
http://bugs.debian.org/593347
http://bugs.debian.org/551627
http://bugs.debian.org/589325
http://bugs.debian.org/543924
http://bugs.debian.org/603354
http://bugs.debian.org/604003
http://bugs.debian.org/604102
[ Colin Watson ]
* New Bazaar snapshot.  Too many changes to list in full, but some of the
  more user-visible ones are as follows:
  - GRUB script:
    + Function parameters, "break", "continue", "shift", "setparams",
      "return", and "!".
    + "export" command supports multiple variable names.
    + Multi-line quoted strings support.
    + Wildcard expansion.
  - sendkey support.
  - USB hotunplugging and USB serial support.
  - Rename CD-ROM to cd on BIOS.
  - Add new --boot-directory option to grub-install, grub-reboot, and
    grub-set-default; the old --root-directory option is still accepted
    but was often confusing.
  - Basic btrfs detection/UUID support (but no file reading yet).
  - bash-completion for utilities.
  - If a device is listed in device.map, always assume that it is
    BIOS-visible rather than using extra layers such as LVM or RAID.
  - Add grub-mknetdir script (closes: #550658).
  - Remove deprecated "root" command.
  - Handle RAID devices containing virtio components.
  - GRUB Legacy configuration file support (via grub-menulst2cfg).
  - Keyboard layout support (via grub-mklayout and grub-kbdcomp).
  - Check generated grub.cfg for syntax errors before saving.
  - Pause execution for at most ten seconds if any errors are displayed,
    so that the user has a chance to see them.
  - Support submenus.
  - Write embedding zone using Reed-Solomon, so that it's robust against
    being partially overwritten (closes: #550702, #591416, #593347).
  - GRUB_DISABLE_LINUX_RECOVERY and GRUB_DISABLE_NETBSD_RECOVERY merged
    into a single GRUB_DISABLE_RECOVERY variable.
  - Fix loader memory allocation failure (closes: #551627).
  - Don't call savedefault on recovery entries (closes: #589325).
  - Support triple-indirect blocks on ext2 (closes: #543924).
  - Recognise DDF1 fake RAID (closes: #603354).

[ Robert Millan ]
* Use dpkg architecture wildcards.

[ Updated translations ]
* Slovenian (Vanja Cvelbar).  Closes: #604003
* Dzongkha (dawa pemo via Tenzin Dendup).  Closes: #604102

Show diffs side-by-side

added added

removed removed

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