diff options
author | Daniel Axtens <dja@axtens.net> | 2021-11-25 02:22:48 +1100 |
---|---|---|
committer | Daniel Kiper <daniel.kiper@oracle.com> | 2021-12-23 03:08:27 +0100 |
commit | 1f8d0b01738e49767d662d6426af3570a64565f0 (patch) | |
tree | a501d130529805223275a8e6ba23d93677cfb351 | |
parent | a847895a8d000bdf27ad4d4326f883a0eed769ca (diff) | |
download | grub-1f8d0b01738e49767d662d6426af3570a64565f0.tar.gz |
mm: Document grub_free()
The grub_free() possesses a surprising number of quirks, and also
uses single-letter variable names confusingly to iterate through
the free list.
Document what's going on.
Use prev and cur to iterate over the free list.
Signed-off-by: Daniel Axtens <dja@axtens.net>
Reviewed-by: Daniel Kiper <daniel.kiper@oracle.com>
-rw-r--r-- | grub-core/kern/mm.c | 63 |
1 files changed, 41 insertions, 22 deletions
diff --git a/grub-core/kern/mm.c b/grub-core/kern/mm.c index ac41cf4aa..bec960c18 100644 --- a/grub-core/kern/mm.c +++ b/grub-core/kern/mm.c @@ -446,54 +446,73 @@ grub_free (void *ptr) } else { - grub_mm_header_t q, s; + grub_mm_header_t cur, prev; #if 0 - q = r->first; + cur = r->first; do { grub_printf ("%s:%d: q=%p, q->size=0x%x, q->magic=0x%x\n", - GRUB_FILE, __LINE__, q, q->size, q->magic); - q = q->next; + GRUB_FILE, __LINE__, cur, cur->size, cur->magic); + cur = cur->next; } - while (q != r->first); + while (cur != r->first); #endif - - for (s = r->first, q = s->next; q <= p || q->next >= p; s = q, q = s->next) + /* Iterate over all blocks in the free ring. + * + * The free ring is arranged from high addresses to low + * addresses, modulo wraparound. + * + * We are looking for a block with a higher address than p or + * whose next address is lower than p. + */ + for (prev = r->first, cur = prev->next; cur <= p || cur->next >= p; + prev = cur, cur = prev->next) { - if (q->magic != GRUB_MM_FREE_MAGIC) - grub_fatal ("free magic is broken at %p: 0x%x", q, q->magic); + if (cur->magic != GRUB_MM_FREE_MAGIC) + grub_fatal ("free magic is broken at %p: 0x%x", cur, cur->magic); - if (q <= q->next && (q > p || q->next < p)) + /* Deal with wrap-around */ + if (cur <= cur->next && (cur > p || cur->next < p)) break; } + /* mark p as free and insert it between cur and cur->next */ p->magic = GRUB_MM_FREE_MAGIC; - p->next = q->next; - q->next = p; + p->next = cur->next; + cur->next = p; + /* + * If the block we are freeing can be merged with the next + * free block, do that. + */ if (p->next + p->next->size == p) { p->magic = 0; p->next->size += p->size; - q->next = p->next; + cur->next = p->next; p = p->next; } - r->first = q; + r->first = cur; - if (q == p + p->size) + /* Likewise if can be merged with the preceeding free block */ + if (cur == p + p->size) { - q->magic = 0; - p->size += q->size; - if (q == s) - s = p; - s->next = p; - q = s; + cur->magic = 0; + p->size += cur->size; + if (cur == prev) + prev = p; + prev->next = p; + cur = prev; } - r->first = q; + /* + * Set r->first such that the just free()d block is tried first. + * (An allocation is tried from *first->next, and cur->next == p.) + */ + r->first = cur; } } |