1 /* mm.c - functions for memory manager */
3 * GRUB -- GRand Unified Bootloader
4 * Copyright (C) 2002,2005,2007,2008,2009 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 3 of the License, or
9 * (at your option) any later version.
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.
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/>.
21 The design of this memory manager.
23 This is a simple implementation of malloc with a few extensions. These are
26 - memalign is implemented efficiently.
28 - multiple regions may be used as free space. They may not be
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.
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
43 There are two types of blocks: allocated blocks and free blocks.
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
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.
56 For safety, both allocated blocks and free ones are marked by magic
57 numbers. Whenever anything unexpected is detected, GRUB aborts the
63 #include <grub/misc.h>
65 #include <grub/types.h>
66 #include <grub/disk.h>
68 #include <grub/i18n.h>
69 #include <grub/mm_private.h>
81 grub_mm_region_t grub_mm_base
;
83 /* Get a header from the pointer PTR, and set *P and *R to a pointer
84 to the header and a pointer to its region, respectively. PTR must
87 get_header_from_pointer (void *ptr
, grub_mm_header_t
*p
, grub_mm_region_t
*r
)
89 if ((grub_addr_t
) ptr
& (GRUB_MM_ALIGN
- 1))
90 grub_fatal ("unaligned pointer %p", ptr
);
92 for (*r
= grub_mm_base
; *r
; *r
= (*r
)->next
)
93 if ((grub_addr_t
) ptr
> (grub_addr_t
) ((*r
) + 1)
94 && (grub_addr_t
) ptr
<= (grub_addr_t
) ((*r
) + 1) + (*r
)->size
)
98 grub_fatal ("out of range pointer %p", ptr
);
100 *p
= (grub_mm_header_t
) ptr
- 1;
101 if ((*p
)->magic
== GRUB_MM_FREE_MAGIC
)
102 grub_fatal ("double free at %p", *p
);
103 if ((*p
)->magic
!= GRUB_MM_ALLOC_MAGIC
)
104 grub_fatal ("alloc magic is broken at %p: %lx", *p
,
105 (unsigned long) (*p
)->magic
);
108 /* Initialize a region starting from ADDR and whose size is SIZE,
109 to use it as free space. */
111 grub_mm_init_region (void *addr
, grub_size_t size
)
114 grub_mm_region_t r
, *p
, q
;
117 grub_printf ("Using memory for heap: start=%p, end=%p\n", addr
, addr
+ (unsigned int) size
);
120 /* Allocate a region from the head. */
121 r
= (grub_mm_region_t
) ALIGN_UP ((grub_addr_t
) addr
, GRUB_MM_ALIGN
);
122 size
-= (char *) r
- (char *) addr
+ sizeof (*r
);
124 /* If this region is too small, ignore it. */
125 if (size
< GRUB_MM_ALIGN
)
128 h
= (grub_mm_header_t
) (r
+ 1);
130 h
->magic
= GRUB_MM_FREE_MAGIC
;
131 h
->size
= (size
>> GRUB_MM_ALIGN_LOG2
);
134 r
->pre_size
= (grub_addr_t
) r
- (grub_addr_t
) addr
;
135 r
->size
= (h
->size
<< GRUB_MM_ALIGN_LOG2
);
137 /* Find where to insert this region. Put a smaller one before bigger ones,
138 to prevent fragmentation. */
139 for (p
= &grub_mm_base
, q
= *p
; q
; p
= &(q
->next
), q
= *p
)
140 if (q
->size
> r
->size
)
147 /* Allocate the number of units N with the alignment ALIGN from the ring
148 buffer starting from *FIRST. ALIGN must be a power of two. Both N and
149 ALIGN are in units of GRUB_MM_ALIGN. Return a non-NULL if successful,
150 otherwise return NULL. */
152 grub_real_malloc (grub_mm_header_t
*first
, grub_size_t n
, grub_size_t align
)
154 grub_mm_header_t p
, q
;
156 /* When everything is allocated side effect is that *first will have alloc
157 magic marked, meaning that there is no room in this region. */
158 if ((*first
)->magic
== GRUB_MM_ALLOC_MAGIC
)
161 /* Try to search free slot for allocation in this memory region. */
162 for (q
= *first
, p
= q
->next
; ; q
= p
, p
= p
->next
)
166 extra
= ((grub_addr_t
) (p
+ 1) >> GRUB_MM_ALIGN_LOG2
) % align
;
168 extra
= align
- extra
;
171 grub_fatal ("null in the ring");
173 if (p
->magic
!= GRUB_MM_FREE_MAGIC
)
174 grub_fatal ("free magic is broken at %p: 0x%x", p
, p
->magic
);
176 if (p
->size
>= n
+ extra
)
178 extra
+= (p
->size
- extra
- n
) & (~(align
- 1));
179 if (extra
== 0 && p
->size
== n
)
181 /* There is no special alignment requirement and memory block
184 1. Just mark memory block as allocated and remove it from
188 +---------------+ previous block's next
194 else if (align
== 1 || p
->size
== n
+ extra
)
196 /* There might be alignment requirement, when taking it into
197 account memory block fits in.
199 1. Allocate new area at end of memory block.
200 2. Reduce size of available blocks from original node.
201 3. Mark new area as allocated and "remove" it from free
206 | free, size-=n | next --+
220 r
->magic
= GRUB_MM_FREE_MAGIC
;
221 r
->size
= p
->size
- extra
- n
;
233 /* There is alignment requirement and there is room in memory
234 block. Split memory block to three pieces.
236 1. Create new memory block right after section being
237 allocated. Mark it as free.
238 2. Add new memory block to free chain.
239 3. Mark current memory block having only extra blocks.
240 4. Advance to aligned block and mark that as allocated and
241 "remove" it from free list.
244 +------------------------------+
245 | free, size=extra | next --+
246 +------------------------------+ |
248 +------------------------------+ |
249 | free, size=orig.size-extra-n | <------+, next --+
250 +------------------------------+ v
255 r
->magic
= GRUB_MM_FREE_MAGIC
;
256 r
->size
= p
->size
- extra
- n
;
264 p
->magic
= GRUB_MM_ALLOC_MAGIC
;
267 /* Mark find as a start marker for next allocation to fasten it.
268 This will have side effect of fragmenting memory as small
269 pieces before this will be un-used. */
275 /* Search was completed without result. */
283 /* Allocate SIZE bytes with the alignment ALIGN and return the pointer. */
285 grub_memalign (grub_size_t align
, grub_size_t size
)
288 grub_size_t n
= ((size
+ GRUB_MM_ALIGN
- 1) >> GRUB_MM_ALIGN_LOG2
) + 1;
294 align
= (align
>> GRUB_MM_ALIGN_LOG2
);
300 for (r
= grub_mm_base
; r
; r
= r
->next
)
304 p
= grub_real_malloc (&(r
->first
), n
, align
);
309 /* If failed, increase free memory somehow. */
313 /* Invalidate disk caches. */
314 grub_disk_cache_invalidate_all ();
320 /* Unload unneeded modules. */
321 grub_dl_unload_unneeded ();
331 grub_error (GRUB_ERR_OUT_OF_MEMORY
, N_("out of memory"));
335 /* Allocate SIZE bytes and return the pointer. */
337 grub_malloc (grub_size_t size
)
339 return grub_memalign (0, size
);
342 /* Allocate SIZE bytes, clear them and return the pointer. */
344 grub_zalloc (grub_size_t size
)
348 ret
= grub_memalign (0, size
);
350 grub_memset (ret
, 0, size
);
355 /* Deallocate the pointer PTR. */
357 grub_free (void *ptr
)
365 get_header_from_pointer (ptr
, &p
, &r
);
367 if (r
->first
->magic
== GRUB_MM_ALLOC_MAGIC
)
369 p
->magic
= GRUB_MM_FREE_MAGIC
;
370 r
->first
= p
->next
= p
;
374 grub_mm_header_t q
, s
;
380 grub_printf ("%s:%d: q=%p, q->size=0x%x, q->magic=0x%x\n",
381 GRUB_FILE
, __LINE__
, q
, q
->size
, q
->magic
);
384 while (q
!= r
->first
);
387 for (s
= r
->first
, q
= s
->next
; q
<= p
|| q
->next
>= p
; s
= q
, q
= s
->next
)
389 if (q
->magic
!= GRUB_MM_FREE_MAGIC
)
390 grub_fatal ("free magic is broken at %p: 0x%x", q
, q
->magic
);
392 if (q
<= q
->next
&& (q
> p
|| q
->next
< p
))
396 p
->magic
= GRUB_MM_FREE_MAGIC
;
400 if (p
->next
+ p
->next
->size
== p
)
404 p
->next
->size
+= p
->size
;
411 if (q
== p
+ p
->size
)
425 /* Reallocate SIZE bytes and return the pointer. The contents will be
426 the same as that of PTR. */
428 grub_realloc (void *ptr
, grub_size_t size
)
436 return grub_malloc (size
);
444 /* FIXME: Not optimal. */
445 n
= ((size
+ GRUB_MM_ALIGN
- 1) >> GRUB_MM_ALIGN_LOG2
) + 1;
446 get_header_from_pointer (ptr
, &p
, &r
);
451 q
= grub_malloc (size
);
455 grub_memcpy (q
, ptr
, size
);
461 int grub_mm_debug
= 0;
464 grub_mm_dump_free (void)
468 for (r
= grub_mm_base
; r
; r
= r
->next
)
472 /* Follow the free list. */
476 if (p
->magic
!= GRUB_MM_FREE_MAGIC
)
477 grub_fatal ("free magic is broken at %p: 0x%x", p
, p
->magic
);
479 grub_printf ("F:%p:%u:%p\n",
480 p
, (unsigned int) p
->size
<< GRUB_MM_ALIGN_LOG2
, p
->next
);
483 while (p
!= r
->first
);
490 grub_mm_dump (unsigned lineno
)
494 grub_printf ("called at line %u\n", lineno
);
495 for (r
= grub_mm_base
; r
; r
= r
->next
)
499 for (p
= (grub_mm_header_t
) ALIGN_UP ((grub_addr_t
) (r
+ 1),
501 (grub_addr_t
) p
< (grub_addr_t
) (r
+1) + r
->size
;
506 case GRUB_MM_FREE_MAGIC
:
507 grub_printf ("F:%p:%u:%p\n",
508 p
, (unsigned int) p
->size
<< GRUB_MM_ALIGN_LOG2
, p
->next
);
510 case GRUB_MM_ALLOC_MAGIC
:
511 grub_printf ("A:%p:%u\n", p
, (unsigned int) p
->size
<< GRUB_MM_ALIGN_LOG2
);
521 grub_debug_malloc (const char *file
, int line
, grub_size_t size
)
526 grub_printf ("%s:%d: malloc (0x%" PRIxGRUB_SIZE
") = ", file
, line
, size
);
527 ptr
= grub_malloc (size
);
529 grub_printf ("%p\n", ptr
);
534 grub_debug_zalloc (const char *file
, int line
, grub_size_t size
)
539 grub_printf ("%s:%d: zalloc (0x%" PRIxGRUB_SIZE
") = ", file
, line
, size
);
540 ptr
= grub_zalloc (size
);
542 grub_printf ("%p\n", ptr
);
547 grub_debug_free (const char *file
, int line
, void *ptr
)
550 grub_printf ("%s:%d: free (%p)\n", file
, line
, ptr
);
555 grub_debug_realloc (const char *file
, int line
, void *ptr
, grub_size_t size
)
558 grub_printf ("%s:%d: realloc (%p, 0x%" PRIxGRUB_SIZE
") = ", file
, line
, ptr
, size
);
559 ptr
= grub_realloc (ptr
, size
);
561 grub_printf ("%p\n", ptr
);
566 grub_debug_memalign (const char *file
, int line
, grub_size_t align
,
572 grub_printf ("%s:%d: memalign (0x%" PRIxGRUB_SIZE
", 0x%" PRIxGRUB_SIZE
573 ") = ", file
, line
, align
, size
);
574 ptr
= grub_memalign (align
, size
);
576 grub_printf ("%p\n", ptr
);
580 #endif /* MM_DEBUG */