[1981] 2009-02-08 Vesa J?\195?\164?\195?\164skel?\195?\164inen <chaac@nic .fi>
Vesa J??skel?inen <[email protected]>
| Newsgroups | gmane.comp.boot-loaders.grub.cvs |
|---|---|
| Message-ID | <[email protected]> |
Revision: 1981
http://svn.sv.gnu.org/viewvc/?view=rev&root=grub&revision=1981
Author: chaac
Date: 2009-02-08 10:52:03 +0000 (Sun, 08 Feb 2009)
Log Message:
-----------
2009-02-08 Vesa J?\195?\164?\195?\164skel?\195?\164inen <[email protected]>
* kern/mm.c: Add more comments.
Modified Paths:
--------------
trunk/grub2/ChangeLog
trunk/grub2/kern/mm.c
Modified: trunk/grub2/ChangeLog
===================================================================
--- trunk/grub2/ChangeLog 2009-02-08 00:51:22 UTC (rev 1980)
+++ trunk/grub2/ChangeLog 2009-02-08 10:52:03 UTC (rev 1981)
@@ -1,3 +1,7 @@
+2009-02-08 Vesa Jääskeläinen <[email protected]>
+
+ * kern/mm.c: Add more comments.
+
2009-02-08 Robert Millan <[email protected]>
Patch from Javier Martín.
Modified: trunk/grub2/kern/mm.c
===================================================================
--- trunk/grub2/kern/mm.c 2009-02-08 00:51:22 UTC (rev 1980)
+++ trunk/grub2/kern/mm.c 2009-02-08 10:52:03 UTC (rev 1981)
@@ -129,7 +129,7 @@
if (! *r)
grub_fatal ("out of range pointer %p", ptr);
-
+
*p = (grub_mm_header_t) ptr - 1;
if ((*p)->magic != GRUB_MM_ALLOC_MAGIC)
grub_fatal ("alloc magic is broken at %p", *p);
@@ -155,7 +155,7 @@
r = (grub_mm_region_t) (((grub_addr_t) addr + GRUB_MM_ALIGN - 1)
& (~(GRUB_MM_ALIGN - 1)));
size -= (char *) r - (char *) addr + sizeof (*r);
-
+
h = (grub_mm_header_t) ((char *) r + GRUB_MM_ALIGN);
h->next = h;
h->magic = GRUB_MM_FREE_MAGIC;
@@ -170,22 +170,26 @@
for (p = &base, q = *p; q; p = &(q->next), q = *p)
if (q->size > r->size)
break;
-
+
*p = r;
r->next = q;
}
/* Allocate the number of units N with the alignment ALIGN from the ring
- buffer starting from *FIRST. ALIGN must be a power of two. Return a
- non-NULL if successful, otherwise return NULL. */
+ buffer starting from *FIRST. ALIGN must be a power of two. Both N and
+ ALIGN are in units of GRUB_MM_ALIGN. Return a non-NULL if successful,
+ otherwise return NULL. */
static void *
grub_real_malloc (grub_mm_header_t *first, grub_size_t n, grub_size_t align)
{
grub_mm_header_t p, q;
+ /* When everything is allocated side effect is that *first will have alloc
+ magic marked, meaning that there is no room in this region. */
if ((*first)->magic == GRUB_MM_ALLOC_MAGIC)
return 0;
+ /* Try to search free slot for allocation in this memory region. */
for (q = *first, p = q->next; ; q = p, p = p->next)
{
grub_off_t extra;
@@ -204,11 +208,37 @@
{
if (extra == 0 && p->size == n)
{
+ /* There is no special alignment requirement and memory block
+ is complete match.
+
+ 1. Just mark memory block as allocated and remove it from
+ free list.
+
+ Result:
+ +---------------+ previous block's next
+ | alloc, size=n | |
+ +---------------+ v
+ */
q->next = p->next;
p->magic = GRUB_MM_ALLOC_MAGIC;
}
else if (extra == 0 || p->size == n + extra)
{
+ /* There might be alignment requirement, when taking it into
+ account memory block fits in.
+
+ 1. Allocate new area at end of memory block.
+ 2. Reduce size of available blocks from original node.
+ 3. Mark new area as allocated and "remove" it from free
+ list.
+
+ Result:
+ +---------------+
+ | free, size-=n | next --+
+ +---------------+ |
+ | alloc, size=n | |
+ +---------------+ v
+ */
p->size -= n;
p += p->size;
p->size = n;
@@ -216,13 +246,32 @@
}
else
{
+ /* There is alignment requirement and there is room in memory
+ block. Split memory block to three pieces.
+
+ 1. Create new memory block right after section being
+ allocated. Mark it as free.
+ 2. Add new memory block to free chain.
+ 3. Mark current memory block having only extra blocks.
+ 4. Advance to aligned block and mark that as allocated and
+ "remove" it from free list.
+
+ Result:
+ +------------------------------+
+ | free, size=extra | next --+
+ +------------------------------+ |
+ | alloc, size=n | |
+ +------------------------------+ |
+ | free, size=orig.size-extra-n | <------+, next --+
+ +------------------------------+ v
+ */
grub_mm_header_t r;
r = p + extra + n;
r->magic = GRUB_MM_FREE_MAGIC;
r->size = p->size - extra - n;
r->next = p->next;
-
+
p->size = extra;
p->next = r;
p += extra;
@@ -230,11 +279,15 @@
p->magic = GRUB_MM_ALLOC_MAGIC;
}
+ /* Mark find as a start marker for next allocation to fasten it.
+ This will have side effect of fragmenting memory as small
+ pieces before this will be un-used. */
*first = q;
-
+
return p + 1;
}
+ /* Search was completed without result. */
if (p == *first)
break;
}
@@ -249,17 +302,17 @@
grub_mm_region_t r;
grub_size_t n = ((size + GRUB_MM_ALIGN - 1) >> GRUB_MM_ALIGN_LOG2) + 1;
int count = 0;
-
+
align = (align >> GRUB_MM_ALIGN_LOG2);
if (align == 0)
align = 1;
again:
-
+
for (r = base; r; r = r->next)
{
void *p;
-
+
p = grub_real_malloc (&(r->first), n, align);
if (p)
return p;
@@ -273,7 +326,7 @@
grub_disk_cache_invalidate_all ();
count++;
goto again;
-
+
case 1:
/* Unload unneeded modules. */
grub_dl_unload_unneeded ();
@@ -283,7 +336,7 @@
default:
break;
}
-
+
grub_error (GRUB_ERR_OUT_OF_MEMORY, "out of memory");
return 0;
}
@@ -326,12 +379,12 @@
}
while (q != r->first);
#endif
-
+
for (q = r->first; q >= p || q->next <= p; q = q->next)
{
if (q->magic != GRUB_MM_FREE_MAGIC)
grub_fatal ("free magic is broken at %p: 0x%x", q, q->magic);
-
+
if (q >= q->next && (q < p || q->next > p))
break;
}
@@ -339,7 +392,7 @@
p->magic = GRUB_MM_FREE_MAGIC;
p->next = q->next;
q->next = p;
-
+
if (p + p->size == p->next)
{
if (p->next == q)
@@ -349,7 +402,7 @@
p->size += p->next->size;
p->next = p->next->next;
}
-
+
if (q + q->size == p)
{
p->magic = 0;
@@ -370,7 +423,7 @@
grub_mm_region_t r;
void *q;
grub_size_t n;
-
+
if (! ptr)
return grub_malloc (size);
@@ -383,14 +436,14 @@
/* FIXME: Not optimal. */
n = ((size + GRUB_MM_ALIGN - 1) >> GRUB_MM_ALIGN_LOG2) + 1;
get_header_from_pointer (ptr, &p, &r);
-
+
if (p->size >= n)
return ptr;
-
+
q = grub_malloc (size);
if (! q)
return q;
-
+
grub_memcpy (q, ptr, size);
grub_free (ptr);
return q;
@@ -434,7 +487,7 @@
for (r = base; r; r = r->next)
{
grub_mm_header_t p;
-
+
for (p = (grub_mm_header_t) ((r->addr + GRUB_MM_ALIGN - 1)
& (~(GRUB_MM_ALIGN - 1)));
(grub_addr_t) p < r->addr + r->size;
@@ -493,7 +546,7 @@
grub_size_t size)
{
void *ptr;
-
+
if (grub_mm_debug)
grub_printf ("%s:%d: memalign (0x%x, 0x%x) = ",
file, line, align, size);