1
/* mm.c - functions for memory manager */
3
* GRUB -- GRand Unified Bootloader
4
* Copyright (C) 2002,2005 Free Software Foundation, Inc.
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 2 of the License, or
9
* (at your option) any later version.
11
* This program 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.
16
* You should have received a copy of the GNU General Public License
17
* along with GRUB; if not, write to the Free Software
18
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22
The design of this memory manager.
24
This is a simple implementation of malloc with a few extensions. These are
27
- memalign is implemented efficiently.
29
- multiple regions may be used as free space. They may not be
32
Regions are managed by a singly linked list, and the meta information is
33
stored in the beginning of each region. Space after the meta information
34
is used to allocate memory.
36
The memory space is used as cells instead of bytes for simplicity. This
37
is important for some CPUs which may not access multiple bytes at a time
38
when the first byte is not aligned at a certain boundary (typically,
39
4-byte or 8-byte). The size of each cell is equal to the size of struct
40
grub_mm_header, so the header of each allocated/free block fits into one
41
cell precisely. One cell is 16 bytes on 32-bit platforms and 32 bytes
44
There are two types of blocks: allocated blocks and free blocks.
46
In allocated blocks, the header of each block has only its size. Note that
47
this size is based on cells but not on bytes. The header is located right
48
before the returned pointer, that is, the header resides at the previous
51
Free blocks constitutes a ring, using a singly linked list. The first free
52
block is pointed to by the meta information of a region. The allocator
53
attempts to pick up the second block instead of the first one. This is
54
a typical optimization against defragmentation, and makes the
55
implementation a bit easier.
57
For safety, both allocated blocks and free ones are marked by magic
58
numbers. Whenever anything unexpected is detected, GRUB aborts the
64
#include <grub/misc.h>
66
#include <grub/types.h>
67
#include <grub/disk.h>
71
#define GRUB_MM_FREE_MAGIC 0x2d3c2808
72
#define GRUB_MM_ALLOC_MAGIC 0x6db08fa4
74
typedef struct grub_mm_header
76
struct grub_mm_header *next;
79
#if GRUB_CPU_SIZEOF_VOID_P == 4
81
#elif GRUB_CPU_SIZEOF_VOID_P == 8
84
# error "unknown word size"
89
#if GRUB_CPU_SIZEOF_VOID_P == 4
90
# define GRUB_MM_ALIGN_LOG2 4
91
#elif GRUB_CPU_SIZEOF_VOID_P == 8
92
# define GRUB_MM_ALIGN_LOG2 5
95
#define GRUB_MM_ALIGN (1 << GRUB_MM_ALIGN_LOG2)
97
typedef struct grub_mm_region
99
struct grub_mm_header *first;
100
struct grub_mm_region *next;
108
static grub_mm_region_t base;
110
/* Get a header from the pointer PTR, and set *P and *R to a pointer
111
to the header and a pointer to its region, respectively. PTR must
114
get_header_from_pointer (void *ptr, grub_mm_header_t *p, grub_mm_region_t *r)
116
if ((grub_addr_t) ptr & (GRUB_MM_ALIGN - 1))
117
grub_fatal ("unaligned pointer %p", ptr);
119
for (*r = base; *r; *r = (*r)->next)
120
if ((grub_addr_t) ptr > (*r)->addr
121
&& (grub_addr_t) ptr <= (*r)->addr + (*r)->size)
125
grub_fatal ("out of range pointer %p", ptr);
127
*p = (grub_mm_header_t) ptr - 1;
128
if ((*p)->magic != GRUB_MM_ALLOC_MAGIC)
129
grub_fatal ("alloc magic is broken at %p", *p);
132
/* Initialize a region starting from ADDR and whose size is SIZE,
133
to use it as free space. */
135
grub_mm_init_region (void *addr, grub_size_t size)
138
grub_mm_region_t r, *p, q;
140
grub_dprintf ("mem", "Using memory for heap: addr=%p, size=%u\n", addr, (unsigned int) size);
142
/* If this region is too small, ignore it. */
143
if (size < GRUB_MM_ALIGN * 2)
146
/* Allocate a region from the head. */
147
r = (grub_mm_region_t) (((grub_addr_t) addr + GRUB_MM_ALIGN - 1)
148
& (~(GRUB_MM_ALIGN - 1)));
149
size -= (char *) r - (char *) addr + sizeof (*r);
151
h = (grub_mm_header_t) ((char *) r + GRUB_MM_ALIGN);
153
h->magic = GRUB_MM_FREE_MAGIC;
154
h->size = (size >> GRUB_MM_ALIGN_LOG2);
157
r->addr = (grub_addr_t) h;
158
r->size = (h->size << GRUB_MM_ALIGN_LOG2);
160
/* Find where to insert this region. Put a smaller one before bigger ones,
161
to prevent fragmentations. */
162
for (p = &base, q = *p; q; p = &(q->next), q = *p)
163
if (q->size > r->size)
170
/* Allocate the number of units N with the alignment ALIGN from the ring
171
buffer starting from *FIRST. ALIGN must be a power of two. Return a
172
non-NULL if successful, otherwise return NULL. */
174
grub_real_malloc (grub_mm_header_t *first, grub_size_t n, grub_size_t align)
176
grub_mm_header_t p, q;
178
if ((*first)->magic == GRUB_MM_ALLOC_MAGIC)
181
for (q = *first, p = q->next; ; q = p, p = p->next)
185
extra = ((grub_addr_t) (p + 1) >> GRUB_MM_ALIGN_LOG2) % align;
187
extra = align - extra;
190
grub_fatal ("null in the ring");
192
if (p->magic != GRUB_MM_FREE_MAGIC)
193
grub_fatal ("free magic is broken at %p: 0x%x", p, p->magic);
195
if (p->size >= n + extra)
197
if (extra == 0 && p->size == n)
200
p->magic = GRUB_MM_ALLOC_MAGIC;
202
else if (extra == 0 || p->size == n + extra)
207
p->magic = GRUB_MM_ALLOC_MAGIC;
214
r->magic = GRUB_MM_FREE_MAGIC;
215
r->size = p->size - extra - n;
222
p->magic = GRUB_MM_ALLOC_MAGIC;
237
/* Allocate SIZE bytes with the alignment ALIGN and return the pointer. */
239
grub_memalign (grub_size_t align, grub_size_t size)
242
grub_size_t n = ((size + GRUB_MM_ALIGN - 1) >> GRUB_MM_ALIGN_LOG2) + 1;
245
align = (align >> GRUB_MM_ALIGN_LOG2);
251
for (r = base; r; r = r->next)
255
p = grub_real_malloc (&(r->first), n, align);
260
/* If failed, increase free memory somehow. */
264
/* Invalidate disk caches. */
265
grub_disk_cache_invalidate_all ();
270
/* Unload unneeded modules. */
271
grub_dl_unload_unneeded ();
279
grub_error (GRUB_ERR_OUT_OF_MEMORY, "out of memory");
283
/* Allocate SIZE bytes and return the pointer. */
285
grub_malloc (grub_size_t size)
287
return grub_memalign (0, size);
290
/* Deallocate the pointer PTR. */
292
grub_free (void *ptr)
300
get_header_from_pointer (ptr, &p, &r);
302
if (r->first->magic == GRUB_MM_ALLOC_MAGIC)
304
p->magic = GRUB_MM_FREE_MAGIC;
305
r->first = p->next = p;
315
grub_printf ("%s:%d: q=%p, q->size=0x%x, q->magic=0x%x\n",
316
__FILE__, __LINE__, q, q->size, q->magic);
319
while (q != r->first);
322
for (q = r->first; q >= p || q->next <= p; q = q->next)
324
if (q->magic != GRUB_MM_FREE_MAGIC)
325
grub_fatal ("free magic is broken at %p: 0x%x", q, q->magic);
327
if (q >= q->next && (q < p || q->next > p))
331
p->magic = GRUB_MM_FREE_MAGIC;
335
if (p + p->size == p->next)
341
p->size += p->next->size;
342
p->next = p->next->next;
345
if (q + q->size == p)
356
/* Reallocate SIZE bytes and return the pointer. The contents will be
357
the same as that of PTR. */
359
grub_realloc (void *ptr, grub_size_t size)
367
return grub_malloc (size);
375
/* FIXME: Not optimal. */
376
n = ((size + GRUB_MM_ALIGN - 1) >> GRUB_MM_ALIGN_LOG2) + 1;
377
get_header_from_pointer (ptr, &p, &r);
382
q = grub_malloc (size);
386
grub_memcpy (q, ptr, size);
393
grub_mm_dump (unsigned lineno)
397
grub_printf ("called at line %u\n", lineno);
398
for (r = base; r; r = r->next)
402
for (p = (grub_mm_header_t) ((r->addr + GRUB_MM_ALIGN - 1)
403
& (~(GRUB_MM_ALIGN - 1)));
404
(grub_addr_t) p < r->addr + r->size;
409
case GRUB_MM_FREE_MAGIC:
410
grub_printf ("F:%p:%u:%p\n",
411
p, (unsigned int) p->size << GRUB_MM_ALIGN_LOG2, p->next);
413
case GRUB_MM_ALLOC_MAGIC:
414
grub_printf ("A:%p:%u\n", p, (unsigned int) p->size << GRUB_MM_ALIGN_LOG2);
422
#endif /* MM_DEBUG */
added
removed
kern/mm.c
