Okay, get ready to pick those nits! Attached is a patch for a new
memory allocator. Please review and tear it apart. If you hate what
I have done, then please propose something different (preferably with
patches!). Read on for my motivation and description of whats
going on here.
What was wrong with the old allocator you say? Glad you asked.
The old memory allocator worked on a static region of memory set
aside by the linker - in the case of libpayload it was 16k sightly
above the .data segment of the payload. This was so that we didn't
need to concern ourselves with figuring out how much system memory we
had and other such concerns.
Well, 16k goes quickly. We are outgrowing our little sandbox. As
an example, I wanted to change the menu system in coreinfo to allow
for more items. This would have involved a "popup" window that the
user could navigate to select the next area to examine. Unfortunately,
the current implementation uses a static allocation for windows, which
limited us to 3 total windows, and guess what - we're already using them.
If I allocate them dynamically, then that will reduce the amount of memory
usable for other components, and like I said - 16k goes fast.
So, this new allocator reads the memory tables, and sets up a block of
allocateable memory at the top of system RAM. Right now we are hardcoding
8Mb of memory, but that will eventually be configurable through both
Kconfig and at runtime.
So here is how the allocator works - right below the allocated memory is
room for an array of slots - each slot has an entry for an offset into
memory and a size. It also has prev and next pointers for linked list
purposes. The number of slots is currently hardcoded to 1024.
There are three lists - the unallocated list contains all of the unused
slots. At init time, there would are 1023 unused slots. The free list
contains slots describing all of the free areas in the memory. At init
time, this list contains a single entry with offset 0, and size of 8Mb.
The final list is actually a hash of linked lists - this will contain
the allocated pointers as they are created.
So, we're set up - and the user calls malloc(). The free blocks are
searched for a free block large enough for the allocation.
The slot containing the former free block is re-adjusted for the allocated
size, and a new slot is allocated on the free list containing the remainder
of the previous free block. Put simply, if the original free block is
8Mb, and you allocate 1Mb, then a new 7Mb slot is put on to the free block
list. And the 1Mb allocated slot is added to the allocated hash table.
When the entry is free()d, it is added to the free list. We also
run a consolidate function that merges consecutive free blocks and and
returns the unused slots to the unallocated list.
The advantage of this implementation is that it is pretty simple,
easy to code, and interestingly enough, it allows us to maintain multiple
chunks of dynamic memory. Why is this useful? One of the problems with
reentrant payloads such as bayou is that if they need their memory to
stick around, then they need to exclude it from the tables they pass to
their children payloads. This is cool if you are running coreinfo, but
not so cool if you are calling FILO and then the kernel, because the kernel
won't return, and you've wasted memory. One of the solutions for this would
be to use both the original static memory block _and_ the extended memory
block, and then restrict bayou so that it only uses the static memory.
This implementation lets us do that, and it will just work (TM).
--
Jordan Crouse
Systems Software Development Engineer
Advanced Micro Devices, Inc.
[PATCH] libpayload: New dynamic memory allocator
This adds a new dynamic memory allocator that can take advantage
of more memory then the static chunk defined in the previous
implementation.
Signed-off-by: Jordan Crouse <[EMAIL PROTECTED]>
Index: libpayload/libc/Makefile.inc
===================================================================
--- libpayload.orig/libc/Makefile.inc 2008-09-26 10:57:24.000000000 -0600
+++ libpayload/libc/Makefile.inc 2008-09-26 10:57:25.000000000 -0600
@@ -28,7 +28,7 @@
## SUCH DAMAGE.
##
-TARGETS-$(CONFIG_LIBC) += libc/malloc.o libc/printf.o libc/console.o libc/string.o
+TARGETS-$(CONFIG_LIBC) += libc/alloc.o libc/printf.o libc/console.o libc/string.o
TARGETS-$(CONFIG_LIBC) += libc/memory.o libc/ctype.o libc/ipchecksum.o libc/lib.o
TARGETS-$(CONFIG_LIBC) += libc/rand.o libc/time.o libc/lar.o libc/exec.o
TARGETS-$(CONFIG_LIBC) += libc/readline.o libc/sysinfo.o
Index: libpayload/libc/alloc.c
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ libpayload/libc/alloc.c 2008-09-26 15:48:41.000000000 -0600
@@ -0,0 +1,584 @@
+/*
+ * This file is part of the libpayload project.
+ *
+ * Copyright (C) 2008 Advanced Micro Devices, Inc.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. The name of the author may not be used to endorse or promote products
+ * derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <libpayload.h>
+
+/* Amount of dynamic memory to allow */
+/* FIXME: This should be configurable */
+
+#define MEMORY_SIZE (8 * 1024 * 1024)
+
+#define ALIGN(_o, _a) (((_o) + ((_a) - 1)) & ~((_a) - 1))
+
+/* The number of available slots - the number of allocations
+ in the system cannot exceed this */
+
+#define MAX_SLOT_COUNT 1024
+
+/* A marker used to indicate the end of a list */
+#define SLOT_EMPTY (MAX_SLOT_COUNT)
+
+struct mslot {
+ u16 next;
+ u16 prev;
+ u32 offset;
+ u32 size;
+} __attribute__ ((packed));
+
+static struct mslot *slots;
+
+/* Given a slot number, return a pointer to its structure */
+
+#define SLOTPTR(_s) (&slots[(_s)])
+
+/* Pointer to the head of the list unallocated slots */
+static u16 unalloc_list = SLOT_EMPTY;
+
+/* Pointer to the head of the list of free slots (available memory) */
+static u16 free_list;
+
+/* A hash table containing pointers to allocated slots */
+
+#define HASH_SIZE 512
+#define HASH(_p) (((_p) >> 10) % HASH_SIZE)
+
+static u16 alloc_hash[HASH_SIZE];
+
+/* Pointer to the start of allocatable memory */
+static void *memstart;
+
+/* The amount of memory allocated to the slot list aligned to 4096 bytes */
+#define SLOT_SIZE (ALIGN(MAX_SLOT_COUNT * sizeof(struct mslot), 0x1000))
+
+/**
+ * Assign a slot from the unallocated list
+ */
+
+static u16 alloc_slot(void)
+{
+ u16 ret = unalloc_list;
+
+ if (unalloc_list != SLOT_EMPTY) {
+ unalloc_list = slots[ret].next;
+
+ if (unalloc_list != SLOT_EMPTY)
+ slots[unalloc_list].prev = SLOT_EMPTY;
+ }
+
+ return ret;
+}
+
+/**
+ * Return a slot to the beginning of the unallocated list
+ */
+
+static void free_slot(u16 slot)
+{
+ slots[slot].prev = SLOT_EMPTY;
+ slots[slot].next = unalloc_list;
+
+ if (unalloc_list != SLOT_EMPTY)
+ slots[unalloc_list].prev = slot;
+
+ unalloc_list = slot;
+}
+
+/**
+ * Attach a slot to the free list
+ */
+
+static void freelist_attach(int slot)
+{
+ struct mslot *new = SLOTPTR(slot);
+ u16 p = free_list;
+
+ if (free_list == SLOT_EMPTY) {
+ new->prev = new->next = SLOT_EMPTY;
+ free_list = slot;
+
+ return;
+ }
+
+ /* Sort the slots in the free list according to offset */
+
+ while (1) {
+ struct mslot *ptr = SLOTPTR(p);
+
+ if (ptr->offset > new->offset) {
+
+ new->prev = ptr->prev;
+ new->next = p;
+
+ if (ptr->prev != SLOT_EMPTY)
+ slots[ptr->prev].next = slot;
+
+ ptr->prev = slot;
+
+ if (p == free_list)
+ free_list = slot;
+
+ return;
+ }
+
+ if (ptr->next == SLOT_EMPTY) {
+ new->next = ptr->next;
+ ptr->next = slot;
+ new->prev = p;
+
+ return;
+ }
+
+ p = ptr->next;
+ }
+}
+
+/**
+ * Detach a slot from the free list
+ */
+
+static void freelist_detach(slot)
+{
+ if (slots[slot].next != SLOT_EMPTY)
+ slots[slots[slot].next].prev = slots[slot].prev;
+
+ if (slots[slot].prev != SLOT_EMPTY)
+ slots[slots[slot].prev].next = slots[slot].next;
+
+ if (free_list == slot)
+ free_list = slots[slot].next;
+}
+
+/**
+ * Allocate a new slot and add it to the free list
+ */
+
+static void freelist_add(u32 offset, u32 size)
+{
+ u16 slot = alloc_slot();
+
+ if (slot == SLOT_EMPTY)
+ fatal
+ ("Unable to add a free slot - too many allocations\n");
+
+ slots[slot].offset = offset;
+ slots[slot].size = size;
+
+ freelist_attach(slot);
+}
+
+/**
+ * Consolidate the free list to recover as many slots as possible
+ */
+
+static void freelist_consolidate(void)
+{
+ u16 slot = free_list;
+
+ while (slot != SLOT_EMPTY) {
+ struct mslot *cur = SLOTPTR(slot);
+ struct mslot *next;
+
+ if (cur->next == SLOT_EMPTY)
+ return;
+
+ next = SLOTPTR(slots[slot].next);
+
+ if (cur->offset + cur->size == next->offset) {
+ u16 n = cur->next;
+
+ cur->size += next->size;
+ cur->next = next->next;
+
+ if (next->next != SLOT_EMPTY)
+ slots[next->next].prev = slot;
+
+ free_slot(n);
+ } else
+ slot = cur->next;
+ }
+}
+
+/**
+ * Attach a slot to the allocated list
+ */
+
+static void alloclist_attach(int slot)
+{
+ int hash = HASH(slots[slot].offset);
+
+ slots[slot].prev = SLOT_EMPTY;
+ slots[slot].next = alloc_hash[hash];
+
+ slots[alloc_hash[hash]].prev = slot;
+ alloc_hash[hash] = slot;
+}
+
+/**
+ * Find the allocated slot attached to the offset
+ */
+
+static u16 alloclist_find(u32 offset)
+{
+ u16 slot = alloc_hash[HASH(offset)];
+
+ while (slot != SLOT_EMPTY) {
+ if (slots[slot].offset == offset)
+ return slot;
+
+ slot = slots[slot].next;
+ }
+
+ return SLOT_EMPTY;
+}
+
+/**
+ * Detach a slot from the allocated list
+ */
+
+static u16 alloclist_detach(u32 offset)
+{
+ int hash = HASH(offset);
+ u16 slot = alloclist_find(offset);
+
+ if (slot == SLOT_EMPTY)
+ return SLOT_EMPTY;
+
+ if (slots[slot].next != SLOT_EMPTY)
+ slots[slots[slot].next].prev = slots[slot].prev;
+
+ if (slots[slot].prev != SLOT_EMPTY)
+ slots[slots[slot].prev].next = slots[slot].next;
+
+ if (slot == alloc_hash[hash])
+ alloc_hash[hash] = slots[slot].next;
+
+ return slot;
+}
+
+static u64 getmemptr(void)
+{
+ struct sysinfo_memmap *mmap;
+ int i, tom = -1;
+ int mmap_count;
+
+ /* Get the memory map information */
+ mmap_count = sysinfo_get_memmap(&mmap);
+
+ if (mmap_count == 0)
+ fatal("There isn't any system memory available!\n");
+
+ /* Find the entry describing the highest area of memory */
+
+ for (i = 0; i < mmap_count; i++) {
+
+ if (mmap[i].size < (MEMORY_SIZE + SLOT_SIZE))
+ continue;
+
+ if (tom == -1 ||
+ (mmap[i].base + mmap[i].size >
+ mmap[tom].base + mmap[tom].size))
+ tom = i;
+ }
+
+ if (tom == -1)
+ fatal("There isn't enough system memory to run\n");
+
+ return mmap[tom].base + mmap[tom].size - (MEMORY_SIZE + SLOT_SIZE);
+}
+
+/**
+ * Initialize the memory area and lists
+ */
+
+static void initmem(void)
+{
+ int i;
+ void *memptr = phys_to_virt(getmemptr());
+
+ /* Allocate MEMORY_SIZE megs at the top of memory */
+
+ slots = (struct mslot *)memptr;
+ memstart = (void *)memptr + SLOT_SIZE;
+
+ for (i = 0; i < HASH_SIZE; i++)
+ alloc_hash[i] = SLOT_EMPTY;
+
+ for (i = 1; i < MAX_SLOT_COUNT; i++) {
+ slots[i].prev = i - 1;
+ slots[i].next = i + 1;
+ }
+
+ slots[1].prev = SLOT_EMPTY;
+ slots[MAX_SLOT_COUNT - 1].next = SLOT_EMPTY;
+
+ unalloc_list = 1;
+
+ /* Allocate slot 0 as the first free item */
+ slots[0].offset = 0;
+ slots[0].size = MEMORY_SIZE;
+ slots[0].prev = slots[0].next = SLOT_EMPTY;
+
+ free_list = 0;
+}
+
+/**
+ * Allocate dynamic memory
+ * @param size Size of the block to allocation
+ * @align align Byte boundary to align the new allocation on
+ * @return Pointer to the new memory block
+ */
+
+void *alloc(int size, int align)
+{
+ u32 noffset, nsize, psize;
+ u32 boffset;
+ u16 fslot;
+
+ if (size == 0)
+ return NULL;
+
+ /* Allocate the memory infrastructure the first time we need it */
+
+ if (unalloc_list == SLOT_EMPTY)
+ initmem();
+
+ /* Find a free slot big enough for our needs */
+
+ for (fslot = free_list; fslot != SLOT_EMPTY; fslot = slots[fslot].next) {
+
+ u32 bsize = ALIGN(slots[fslot].offset, align) + size;
+
+ if (slots[fslot].size >= bsize)
+ break;
+ }
+
+ if (fslot == SLOT_EMPTY)
+ return NULL;
+
+ /* Remove the slot from the free list */
+ freelist_detach(fslot);
+
+ /* Get the aligned offset of the new block */
+
+ boffset = ALIGN(slots[fslot].offset, align);
+
+ /* Leave no byte behind - if the aligned offset is greater then
+ the block offset, add the bits at the begining back into the
+ free pool
+ */
+
+ psize = boffset - slots[fslot].offset;
+
+ if (boffset > slots[fslot].offset)
+ freelist_add(slots[fslot].offset, psize);
+
+ /* If there is a remainder left in the block, then put it on the
+ list
+ */
+
+ nsize = slots[fslot].size - size - psize;
+ noffset = boffset + size;
+
+ if (nsize)
+ freelist_add(noffset, nsize);
+
+ /* Adjust the slot size and offset for the allocated block */
+
+ slots[fslot].offset = boffset;
+ slots[fslot].size = size;
+
+ /* Add the allocated slot */
+ alloclist_attach(fslot);
+
+ /* Return the memory pointer */
+ return (void *)(memstart + slots[fslot].offset);
+}
+
+/**
+ * Free a previously allocated memory pointer
+ * @param ptr The pointer to free
+ */
+
+void free(void *ptr)
+{
+ u32 offset = (u32) ((u64) (ptr - memstart));
+ u16 slot;
+
+ if (ptr < memstart || ptr == NULL)
+ return;
+
+ /* Detact the slot from the allocated set */
+ slot = alloclist_detach(offset);
+
+ if (slot == SLOT_EMPTY)
+ return;
+
+ /* Attach the slot to the free list */
+ freelist_attach(slot);
+
+ /* Consolidate the blocks in the free list */
+ freelist_consolidate();
+}
+
+/**
+ * Allocate dynamic memory
+ * @param size Size of the memory block (in bytes)
+ * @return A pointer to the allocated memory block or
+ * NULL on failure
+ */
+
+void *malloc(size_t size)
+{
+ return alloc(size, 1);
+}
+
+/**
+ * Allocate zeroed dynamic memory
+ * @param size Size of the memory block (in bytes)
+ * @return A pointer to the allocated memory block or
+ * NULL on failure
+ */
+
+void *calloc(size_t nmemb, size_t size)
+{
+ size_t total = nmemb * size;
+ void *ptr = alloc(total, 1);
+
+ if (ptr)
+ memset(ptr, 0, total);
+
+ return ptr;
+}
+
+/**
+ * Reallocate dynamic memory
+ * @param size Size of the memory block (in bytes)
+ * @return A pointer to the allocated memory block or
+ * NULL on failure
+ */
+
+void *realloc(void *ptr, size_t size)
+{
+ void *new;
+ u16 slot = alloclist_find(slot);
+
+ if (slot == SLOT_EMPTY)
+ return NULL;
+
+ /* Allocate a new block for the memory */
+ new = alloc(size, 1);
+
+ if (new == NULL)
+ return NULL;
+
+ /* Copy the contents */
+ memcpy(new, ptr, size < slots[slot].size ? size : slots[slot].size);
+
+ /* Free the old pointer */
+ free(ptr);
+ return new;
+}
+
+/**
+ * Allocate an aligned chunk of memory
+ *
+ * @param align alignment, must be power of two
+ * @param size size of chunk in bytes
+ * @return Return the address of such a memory region or NULL
+ */
+void *memalign(size_t align, size_t size)
+{
+ return alloc(size, align);
+}
+
+/* Return the amount of free memory available */
+
+/**
+ * Return the amount of free memory available
+ * @return Return the amount of free memory left in the system
+ */
+
+u32 sys_memavail(void)
+{
+ int u = free_list;
+ u32 count = 0;
+
+ for (; u != SLOT_EMPTY; u = slots[u].next)
+ count += slots[u].size;
+
+ return count;
+}
+
+static u32 _count(int head)
+{
+ int count = 0;
+
+ while (head != SLOT_EMPTY) {
+ count++;
+ head = slots[head].next;
+ }
+
+ return count;
+}
+
+/**
+ * Return the number of unallocated slots
+ * @return The number of unallocated memory slots
+ */
+
+u32 sys_unalloc_count(void)
+{
+ return _count(unalloc_list);
+}
+
+/**
+ * Return the number of free slots
+ * @return The number of slots describing free memory
+ */
+
+u32 sys_free_count(void)
+{
+ return _count(free_list);
+}
+
+/**
+ * Return the number of allocated slots
+ * @return The number of slots describing allocated memory
+ */
+
+u32 sys_alloc_count(void)
+{
+ int count = 0;
+ int i;
+
+ for (i = 0; i < HASH_SIZE; i++)
+ count += _count(alloc_hash[i]);
+
+ return count;
+}
Index: libpayload/include/libpayload.h
===================================================================
--- libpayload.orig/include/libpayload.h 2008-09-26 10:57:24.000000000 -0600
+++ libpayload/include/libpayload.h 2008-09-26 10:57:25.000000000 -0600
@@ -261,6 +261,11 @@
int sysinfo_get_memmap(struct sysinfo_memmap **ptr);
unsigned long sysinfo_get_multiboot(void);
+u32 sys_alloc_count(void);
+u32 sys_free_count(void);
+u32 sys_unalloc_count(void);
+u32 sys_memavail(void);
+
/** @} */
/**
* @defgroup memory Memory manipulation functions
--
coreboot mailing list: [email protected]
http://www.coreboot.org/mailman/listinfo/coreboot
