1 /* mm.c - functions for memory manager */
3 * GRUB -- GRand Unified Bootloader
4 * Copyright (C) 2002,2005,2007,2008 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>
77 #define GRUB_MM_FREE_MAGIC 0x2d3c2808
78 #define GRUB_MM_ALLOC_MAGIC 0x6db08fa4
80 typedef struct grub_mm_header
82 struct grub_mm_header
*next
;
85 #if GRUB_CPU_SIZEOF_VOID_P == 4
87 #elif GRUB_CPU_SIZEOF_VOID_P == 8
90 # error "unknown word size"
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
101 #define GRUB_MM_ALIGN (1 << GRUB_MM_ALIGN_LOG2)
103 typedef struct grub_mm_region
105 struct grub_mm_header
*first
;
106 struct grub_mm_region
*next
;
114 static grub_mm_region_t base
;
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
120 get_header_from_pointer (void *ptr
, grub_mm_header_t
*p
, grub_mm_region_t
*r
)
122 if ((grub_addr_t
) ptr
& (GRUB_MM_ALIGN
- 1))
123 grub_fatal ("unaligned pointer %p", ptr
);
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
)
131 grub_fatal ("out of range pointer %p", ptr
);
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
);
138 /* Initialize a region starting from ADDR and whose size is SIZE,
139 to use it as free space. */
141 grub_mm_init_region (void *addr
, grub_size_t size
)
144 grub_mm_region_t r
, *p
, q
;
147 grub_printf ("Using memory for heap: start=%p, end=%p\n", addr
, addr
+ (unsigned int) size
);
150 /* If this region is too small, ignore it. */
151 if (size
< GRUB_MM_ALIGN
* 2)
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
);
159 h
= (grub_mm_header_t
) ((char *) r
+ GRUB_MM_ALIGN
);
161 h
->magic
= GRUB_MM_FREE_MAGIC
;
162 h
->size
= (size
>> GRUB_MM_ALIGN_LOG2
);
165 r
->addr
= (grub_addr_t
) h
;
166 r
->size
= (h
->size
<< GRUB_MM_ALIGN_LOG2
);
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
)
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. */
183 grub_real_malloc (grub_mm_header_t
*first
, grub_size_t n
, grub_size_t align
)
185 grub_mm_header_t p
, q
;
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
)
192 /* Try to search free slot for allocation in this memory region. */
193 for (q
= *first
, p
= q
->next
; ; q
= p
, p
= p
->next
)
197 extra
= ((grub_addr_t
) (p
+ 1) >> GRUB_MM_ALIGN_LOG2
) % align
;
199 extra
= align
- extra
;
202 grub_fatal ("null in the ring");
204 if (p
->magic
!= GRUB_MM_FREE_MAGIC
)
205 grub_fatal ("free magic is broken at %p: 0x%x", p
, p
->magic
);
207 if (p
->size
>= n
+ extra
)
209 if (extra
== 0 && p
->size
== n
)
211 /* There is no special alignment requirement and memory block
214 1. Just mark memory block as allocated and remove it from
218 +---------------+ previous block's next
223 p
->magic
= GRUB_MM_ALLOC_MAGIC
;
225 else if (extra
== 0 || p
->size
== n
+ extra
)
227 /* There might be alignment requirement, when taking it into
228 account memory block fits in.
230 1. Allocate new area at end of memory block.
231 2. Reduce size of available blocks from original node.
232 3. Mark new area as allocated and "remove" it from free
237 | free, size-=n | next --+
245 p
->magic
= GRUB_MM_ALLOC_MAGIC
;
249 /* There is alignment requirement and there is room in memory
250 block. Split memory block to three pieces.
252 1. Create new memory block right after section being
253 allocated. Mark it as free.
254 2. Add new memory block to free chain.
255 3. Mark current memory block having only extra blocks.
256 4. Advance to aligned block and mark that as allocated and
257 "remove" it from free list.
260 +------------------------------+
261 | free, size=extra | next --+
262 +------------------------------+ |
264 +------------------------------+ |
265 | free, size=orig.size-extra-n | <------+, next --+
266 +------------------------------+ v
271 r
->magic
= GRUB_MM_FREE_MAGIC
;
272 r
->size
= p
->size
- extra
- n
;
279 p
->magic
= GRUB_MM_ALLOC_MAGIC
;
282 /* Mark find as a start marker for next allocation to fasten it.
283 This will have side effect of fragmenting memory as small
284 pieces before this will be un-used. */
290 /* Search was completed without result. */
298 /* Allocate SIZE bytes with the alignment ALIGN and return the pointer. */
300 grub_memalign (grub_size_t align
, grub_size_t size
)
303 grub_size_t n
= ((size
+ GRUB_MM_ALIGN
- 1) >> GRUB_MM_ALIGN_LOG2
) + 1;
306 align
= (align
>> GRUB_MM_ALIGN_LOG2
);
312 for (r
= base
; r
; r
= r
->next
)
316 p
= grub_real_malloc (&(r
->first
), n
, align
);
321 /* If failed, increase free memory somehow. */
325 /* Invalidate disk caches. */
326 grub_disk_cache_invalidate_all ();
331 /* Unload unneeded modules. */
332 grub_dl_unload_unneeded ();
340 grub_error (GRUB_ERR_OUT_OF_MEMORY
, "out of memory");
344 /* Allocate SIZE bytes and return the pointer. */
346 grub_malloc (grub_size_t size
)
348 return grub_memalign (0, size
);
351 /* Deallocate the pointer PTR. */
353 grub_free (void *ptr
)
361 get_header_from_pointer (ptr
, &p
, &r
);
363 if (r
->first
->magic
== GRUB_MM_ALLOC_MAGIC
)
365 p
->magic
= GRUB_MM_FREE_MAGIC
;
366 r
->first
= p
->next
= p
;
376 grub_printf ("%s:%d: q=%p, q->size=0x%x, q->magic=0x%x\n",
377 __FILE__
, __LINE__
, q
, q
->size
, q
->magic
);
380 while (q
!= r
->first
);
383 for (q
= r
->first
; q
>= p
|| q
->next
<= p
; q
= q
->next
)
385 if (q
->magic
!= GRUB_MM_FREE_MAGIC
)
386 grub_fatal ("free magic is broken at %p: 0x%x", q
, q
->magic
);
388 if (q
>= q
->next
&& (q
< p
|| q
->next
> p
))
392 p
->magic
= GRUB_MM_FREE_MAGIC
;
396 if (p
+ p
->size
== p
->next
)
402 p
->size
+= p
->next
->size
;
403 p
->next
= p
->next
->next
;
406 if (q
+ q
->size
== p
)
417 /* Reallocate SIZE bytes and return the pointer. The contents will be
418 the same as that of PTR. */
420 grub_realloc (void *ptr
, grub_size_t size
)
428 return grub_malloc (size
);
436 /* FIXME: Not optimal. */
437 n
= ((size
+ GRUB_MM_ALIGN
- 1) >> GRUB_MM_ALIGN_LOG2
) + 1;
438 get_header_from_pointer (ptr
, &p
, &r
);
443 q
= grub_malloc (size
);
447 grub_memcpy (q
, ptr
, size
);
453 int grub_mm_debug
= 0;
456 grub_mm_dump_free (void)
460 for (r
= base
; r
; r
= r
->next
)
464 /* Follow the free list. */
468 if (p
->magic
!= GRUB_MM_FREE_MAGIC
)
469 grub_fatal ("free magic is broken at %p: 0x%x", p
, p
->magic
);
471 grub_printf ("F:%p:%u:%p\n",
472 p
, (unsigned int) p
->size
<< GRUB_MM_ALIGN_LOG2
, p
->next
);
475 while (p
!= r
->first
);
482 grub_mm_dump (unsigned lineno
)
486 grub_printf ("called at line %u\n", lineno
);
487 for (r
= base
; r
; r
= r
->next
)
491 for (p
= (grub_mm_header_t
) ((r
->addr
+ GRUB_MM_ALIGN
- 1)
492 & (~(GRUB_MM_ALIGN
- 1)));
493 (grub_addr_t
) p
< r
->addr
+ r
->size
;
498 case GRUB_MM_FREE_MAGIC
:
499 grub_printf ("F:%p:%u:%p\n",
500 p
, (unsigned int) p
->size
<< GRUB_MM_ALIGN_LOG2
, p
->next
);
502 case GRUB_MM_ALLOC_MAGIC
:
503 grub_printf ("A:%p:%u\n", p
, (unsigned int) p
->size
<< GRUB_MM_ALIGN_LOG2
);
513 grub_debug_malloc (const char *file
, int line
, grub_size_t size
)
518 grub_printf ("%s:%d: malloc (0x%x) = ", file
, line
, size
);
519 ptr
= grub_malloc (size
);
521 grub_printf ("%p\n", ptr
);
526 grub_debug_free (const char *file
, int line
, void *ptr
)
529 grub_printf ("%s:%d: free (%p)\n", file
, line
, ptr
);
534 grub_debug_realloc (const char *file
, int line
, void *ptr
, grub_size_t size
)
537 grub_printf ("%s:%d: realloc (%p, 0x%x) = ", file
, line
, ptr
, size
);
538 ptr
= grub_realloc (ptr
, size
);
540 grub_printf ("%p\n", ptr
);
545 grub_debug_memalign (const char *file
, int line
, grub_size_t align
,
551 grub_printf ("%s:%d: memalign (0x%x, 0x%x) = ",
552 file
, line
, align
, size
);
553 ptr
= grub_memalign (align
, size
);
555 grub_printf ("%p\n", ptr
);
559 #endif /* MM_DEBUG */