Patrick Georgi (pgeorgi@google.com) just uploaded a new patch set to gerrit, which you can find at http://review.coreboot.org/8729
-gerrit
commit e065631ba28bf906e923d61b7580842782236923 Author: Aaron Durbin adurbin@chromium.org Date: Thu Jan 22 08:59:03 2015 -0600
libpayload: special case large memalign() requests
For memalign() requests the current allocator keeps metadata about each chunk of aligned memory that copmrises the size requested. For large allocations relative to the alignment this can cause significant metadata overhead. Instead, consider all memalign() requests whose size meets or exceeds 1KiB or alignment that meets or exceeds 1KiB are considered large requests. These requests are handled specially to only allocate the amount of memory required for the size and alignment constraints by not allocating any metadata as the whole region would be consumed by the request.
BUG=None BRANCH=None TEST=Built and tested various scenarios. Noted the ability to free() and properly coalesce the heap as expected.
Change-Id: Ia9cf5529ca859e490617af296cffd2705c2c6fd8 Signed-off-by: Patrick Georgi pgeorgi@chromium.org Original-Commit-Id: 4e32fc57626dac6194c9fd0141df680b4a5417e8 Original-Change-Id: Icdf022831b733e3bb84a2d2f3b499f4e25d89128 Original-Signed-off-by: Aaron Durbin adurbin@chromium.org Original-Reviewed-on: https://chromium-review.googlesource.com/242456 Original-Reviewed-by: Julius Werner jwerner@chromium.org --- payloads/libpayload/libc/malloc.c | 140 +++++++++++++++++++++++++++++--------- 1 file changed, 109 insertions(+), 31 deletions(-)
diff --git a/payloads/libpayload/libc/malloc.c b/payloads/libpayload/libc/malloc.c index edda0b4..493dd62 100644 --- a/payloads/libpayload/libc/malloc.c +++ b/payloads/libpayload/libc/malloc.c @@ -318,6 +318,8 @@ void *realloc(void *ptr, size_t size)
struct align_region_t { + /* If alignment is 0 then the region reqpresents a large region which + * has no metadata for tracking subelements. */ int alignment; /* start in memory, and size in bytes */ void* start; @@ -336,58 +338,126 @@ struct align_region_t struct align_region_t *next; };
-static struct align_region_t *allocate_region(int alignment, int num_elements, struct memory_type *type) +static inline int region_is_large(const struct align_region_t *r) { - struct align_region_t *new_region; + return r->alignment == 0; +} + +static inline int addr_in_region(const struct align_region_t *r, void *addr) +{ + return ((addr >= r->start_data) && (addr < r->start_data + r->size)); +} + +/* num_elements == 0 indicates are large aligned region instead of a smaller + * region comprised of alignment-sized chunks. */ +static struct align_region_t *allocate_region(int alignment, int num_elements, + size_t size, struct memory_type *type) +{ + struct align_region_t *r; + size_t extra_space; + #ifdef CONFIG_LP_DEBUG_MALLOC - printf("%s(old align_regions=%p, alignment=%u, num_elements=%u)\n", - __func__, type->align_regions, alignment, num_elements); + printf("%s(old align_regions=%p, alignment=%u, num_elements=%u, size=%zu)\n", + __func__, type->align_regions, alignment, num_elements, size); #endif
- new_region = malloc(sizeof(struct align_region_t)); + r = malloc(sizeof(*r));
- if (!new_region) + if (r == NULL) return NULL; - new_region->alignment = alignment; - new_region->start = alloc((num_elements+1) * alignment + num_elements, type); - if (!new_region->start) { - free(new_region); + + memset(r, 0, sizeof(r)); + + if (num_elements != 0) { + r->alignment = alignment; + r->size = num_elements * alignment; + r->free = num_elements; + /* Allocate enough memory for alignment requirements and + * metadata for each chunk. */ + extra_space = num_elements; + } else { + /* Large aligned allocation. Set alignment = 0. */ + r->alignment = 0; + r->size = size; + extra_space = 0; + } + + r->start = alloc(r->size + alignment + extra_space, type); + + if (r->start == NULL) { + free(r); return NULL; } - new_region->start_data = (void*)((uintptr_t)(new_region->start + num_elements + alignment - 1) & (~(alignment-1))); - new_region->size = num_elements * alignment; - new_region->free = num_elements; - new_region->next = type->align_regions; - memset(new_region->start, 0, num_elements); - type->align_regions = new_region; - return new_region; + + r->start_data = (void *)ALIGN_UP((uintptr_t)r->start + extra_space, + alignment); + + /* Clear any (if requested) metadata. */ + memset(r->start, 0, extra_space); + + /* Link the region with the rest. */ + r->next = type->align_regions; + type->align_regions = r; + + return r; }
+static void try_free_region(struct align_region_t **prev_link) +{ + struct align_region_t *r = *prev_link; + + /* All large regions are immediately free-able. Non-large regions + * need to be checked for the fully freed state. */ + if (!region_is_large(r)) { + if (r->free != r->size / r->alignment) + return; + } + + /* Unlink region from link list. */ + *prev_link = r->next; + + /* Free the data and metadata. */ + free(r->start); + free(r); +}
static int free_aligned(void* addr, struct memory_type *type) { - struct align_region_t *reg = type->align_regions; - while (reg != 0) + struct align_region_t **prev_link = &type->align_regions; + + while (*prev_link != NULL) { - if ((addr >= reg->start_data) && (addr < reg->start_data + reg->size)) - { - int i = (addr-reg->start_data)/reg->alignment; - while (((u8*)reg->start)[i]==2) - { - ((u8*)reg->start)[i++]=0; - reg->free++; - } - ((u8*)reg->start)[i]=0; - reg->free++; + if (!addr_in_region(*prev_link, addr)) { + prev_link = &((*prev_link)->next); + continue; + } + + if (region_is_large(*prev_link)) { + try_free_region(prev_link); return 1; } - reg = reg->next; + + int i = (addr-(*prev_link)->start_data)/(*prev_link)->alignment; + u8 *meta = (*prev_link)->start; + while (meta[i]==2) + { + meta[i++]=0; + (*prev_link)->free++; + } + meta[i]=0; + (*prev_link)->free++; + try_free_region(prev_link); + return 1; } return 0; }
static void *alloc_aligned(size_t align, size_t size, struct memory_type *type) { + /* Define a large request to be 1024 bytes for either alignment or + * size of allocation. */ + const size_t large_request = 1024; + if (size == 0) return 0; if (type->align_regions == 0) { type->align_regions = malloc(sizeof(struct align_region_t)); @@ -396,6 +466,14 @@ static void *alloc_aligned(size_t align, size_t size, struct memory_type *type) memset(type->align_regions, 0, sizeof(struct align_region_t)); } struct align_region_t *reg = type->align_regions; + + if (size >= large_request || align >= large_request) { + reg = allocate_region(align, 0, size, type); + if (reg == NULL) + return NULL; + return reg->start_data; + } + look_further: while (reg != 0) { @@ -414,7 +492,7 @@ look_further: printf(" need to allocate a new memalign region\n"); #endif /* get align regions */ - reg = allocate_region(align, (size<1024)?(1024/align):(((size-1)/align)+1), type); + reg = allocate_region(align, large_request/align, size, type); #ifdef CONFIG_LP_DEBUG_MALLOC printf(" ... returned %p\n", reg); #endif