From 6608dbf540c3724f8cc20619ef3ffb23257dc721 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Marek=20Ol=C5=A1=C3=A1k?= Date: Fri, 7 Oct 2016 04:44:05 +0200 Subject: [PATCH] ralloc: add a linear allocator as a child node of ralloc MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit v2: remove goto, cosmetic changes Tested-by: Edmondo Tommasina (v1) Reviewed-by: Nicolai Hähnle --- src/util/ralloc.c | 353 ++++++++++++++++++++++++++++++++++++++++++++++ src/util/ralloc.h | 84 ++++++++++- 2 files changed, 433 insertions(+), 4 deletions(-) diff --git a/src/util/ralloc.c b/src/util/ralloc.c index b202753e15f..980e4e4f138 100644 --- a/src/util/ralloc.c +++ b/src/util/ralloc.c @@ -528,3 +528,356 @@ ralloc_vasprintf_rewrite_tail(char **str, size_t *start, const char *fmt, *start += new_length; return true; } + +/*************************************************************************** + * Linear allocator for short-lived allocations. + *************************************************************************** + * + * The allocator consists of a parent node (2K buffer), which requires + * a ralloc parent, and child nodes (allocations). Child nodes can't be freed + * directly, because the parent doesn't track them. You have to release + * the parent node in order to release all its children. + * + * The allocator uses a fixed-sized buffer with a monotonically increasing + * offset after each allocation. If the buffer is all used, another buffer + * is allocated, sharing the same ralloc parent, so all buffers are at + * the same level in the ralloc hierarchy. + * + * The linear parent node is always the first buffer and keeps track of all + * other buffers. + */ + +#define ALIGN_POT(x, y) (((x) + (y) - 1) & ~((y) - 1)) + +#define MIN_LINEAR_BUFSIZE 2048 +#define SUBALLOC_ALIGNMENT sizeof(uintptr_t) +#define LMAGIC 0x87b9c7d3 + +struct linear_header { +#ifdef DEBUG + unsigned magic; /* for debugging */ +#endif + unsigned offset; /* points to the first unused byte in the buffer */ + unsigned size; /* size of the buffer */ + void *ralloc_parent; /* new buffers will use this */ + struct linear_header *next; /* next buffer if we have more */ + struct linear_header *latest; /* the only buffer that has free space */ + + /* After this structure, the buffer begins. + * Each suballocation consists of linear_size_chunk as its header followed + * by the suballocation, so it goes: + * + * - linear_size_chunk + * - allocated space + * - linear_size_chunk + * - allocated space + * etc. + * + * linear_size_chunk is only needed by linear_realloc. + */ +}; + +struct linear_size_chunk { + unsigned size; /* for realloc */ + unsigned _padding; +}; + +typedef struct linear_header linear_header; +typedef struct linear_size_chunk linear_size_chunk; + +#define LINEAR_PARENT_TO_HEADER(parent) \ + (linear_header*) \ + ((char*)(parent) - sizeof(linear_size_chunk) - sizeof(linear_header)) + +/* Allocate the linear buffer with its header. */ +static linear_header * +create_linear_node(void *ralloc_ctx, unsigned min_size) +{ + linear_header *node; + + min_size += sizeof(linear_size_chunk); + + if (likely(min_size < MIN_LINEAR_BUFSIZE)) + min_size = MIN_LINEAR_BUFSIZE; + + node = ralloc_size(ralloc_ctx, sizeof(linear_header) + min_size); + if (unlikely(!node)) + return NULL; + +#ifdef DEBUG + node->magic = LMAGIC; +#endif + node->offset = 0; + node->size = min_size; + node->ralloc_parent = ralloc_ctx; + node->next = NULL; + node->latest = node; + return node; +} + +void * +linear_alloc_child(void *parent, unsigned size) +{ + linear_header *first = LINEAR_PARENT_TO_HEADER(parent); + linear_header *latest = first->latest; + linear_header *new_node; + linear_size_chunk *ptr; + unsigned full_size; + + assert(first->magic == LMAGIC); + assert(!latest->next); + + size = ALIGN_POT(size, SUBALLOC_ALIGNMENT); + full_size = sizeof(linear_size_chunk) + size; + + if (unlikely(latest->offset + full_size > latest->size)) { + /* allocate a new node */ + new_node = create_linear_node(latest->ralloc_parent, size); + if (unlikely(!new_node)) + return NULL; + + first->latest = new_node; + latest->latest = new_node; + latest->next = new_node; + latest = new_node; + } + + ptr = (linear_size_chunk *)((char*)&latest[1] + latest->offset); + ptr->size = size; + latest->offset += full_size; + return &ptr[1]; +} + +void * +linear_alloc_parent(void *ralloc_ctx, unsigned size) +{ + linear_header *node; + + if (unlikely(!ralloc_ctx)) + return NULL; + + size = ALIGN_POT(size, SUBALLOC_ALIGNMENT); + + node = create_linear_node(ralloc_ctx, size); + if (unlikely(!node)) + return NULL; + + return linear_alloc_child((char*)node + + sizeof(linear_header) + + sizeof(linear_size_chunk), size); +} + +void * +linear_zalloc_child(void *parent, unsigned size) +{ + void *ptr = linear_alloc_child(parent, size); + + if (likely(ptr)) + memset(ptr, 0, size); + return ptr; +} + +void * +linear_zalloc_parent(void *parent, unsigned size) +{ + void *ptr = linear_alloc_parent(parent, size); + + if (likely(ptr)) + memset(ptr, 0, size); + return ptr; +} + +void +linear_free_parent(void *ptr) +{ + linear_header *node; + + if (unlikely(!ptr)) + return; + + node = LINEAR_PARENT_TO_HEADER(ptr); + assert(node->magic == LMAGIC); + + while (node) { + void *ptr = node; + + node = node->next; + ralloc_free(ptr); + } +} + +void +ralloc_steal_linear_parent(void *new_ralloc_ctx, void *ptr) +{ + linear_header *node; + + if (unlikely(!ptr)) + return; + + node = LINEAR_PARENT_TO_HEADER(ptr); + assert(node->magic == LMAGIC); + + while (node) { + ralloc_steal(new_ralloc_ctx, node); + node->ralloc_parent = new_ralloc_ctx; + node = node->next; + } +} + +void * +ralloc_parent_of_linear_parent(void *ptr) +{ + linear_header *node = LINEAR_PARENT_TO_HEADER(ptr); + assert(node->magic == LMAGIC); + return node->ralloc_parent; +} + +void * +linear_realloc(void *parent, void *old, unsigned new_size) +{ + unsigned old_size = 0; + ralloc_header *new_ptr; + + new_ptr = linear_alloc_child(parent, new_size); + + if (unlikely(!old)) + return new_ptr; + + old_size = ((linear_size_chunk*)old)[-1].size; + + if (likely(new_ptr && old_size)) + memcpy(new_ptr, old, MIN2(old_size, new_size)); + + return new_ptr; +} + +/* All code below is pretty much copied from ralloc and only the alloc + * calls are different. + */ + +char * +linear_strdup(void *parent, const char *str) +{ + unsigned n; + char *ptr; + + if (unlikely(!str)) + return NULL; + + n = strlen(str); + ptr = linear_alloc_child(parent, n + 1); + if (unlikely(!ptr)) + return NULL; + + memcpy(ptr, str, n); + ptr[n] = '\0'; + return ptr; +} + +char * +linear_asprintf(void *parent, const char *fmt, ...) +{ + char *ptr; + va_list args; + va_start(args, fmt); + ptr = linear_vasprintf(parent, fmt, args); + va_end(args); + return ptr; +} + +char * +linear_vasprintf(void *parent, const char *fmt, va_list args) +{ + unsigned size = printf_length(fmt, args) + 1; + + char *ptr = linear_alloc_child(parent, size); + if (ptr != NULL) + vsnprintf(ptr, size, fmt, args); + + return ptr; +} + +bool +linear_asprintf_append(void *parent, char **str, const char *fmt, ...) +{ + bool success; + va_list args; + va_start(args, fmt); + success = linear_vasprintf_append(parent, str, fmt, args); + va_end(args); + return success; +} + +bool +linear_vasprintf_append(void *parent, char **str, const char *fmt, va_list args) +{ + size_t existing_length; + assert(str != NULL); + existing_length = *str ? strlen(*str) : 0; + return linear_vasprintf_rewrite_tail(parent, str, &existing_length, fmt, args); +} + +bool +linear_asprintf_rewrite_tail(void *parent, char **str, size_t *start, + const char *fmt, ...) +{ + bool success; + va_list args; + va_start(args, fmt); + success = linear_vasprintf_rewrite_tail(parent, str, start, fmt, args); + va_end(args); + return success; +} + +bool +linear_vasprintf_rewrite_tail(void *parent, char **str, size_t *start, + const char *fmt, va_list args) +{ + size_t new_length; + char *ptr; + + assert(str != NULL); + + if (unlikely(*str == NULL)) { + *str = linear_vasprintf(parent, fmt, args); + *start = strlen(*str); + return true; + } + + new_length = printf_length(fmt, args); + + ptr = linear_realloc(parent, *str, *start + new_length + 1); + if (unlikely(ptr == NULL)) + return false; + + vsnprintf(ptr + *start, new_length + 1, fmt, args); + *str = ptr; + *start += new_length; + return true; +} + +/* helper routine for strcat/strncat - n is the exact amount to copy */ +static bool +linear_cat(void *parent, char **dest, const char *str, unsigned n) +{ + char *both; + unsigned existing_length; + assert(dest != NULL && *dest != NULL); + + existing_length = strlen(*dest); + both = linear_realloc(parent, *dest, existing_length + n + 1); + if (unlikely(both == NULL)) + return false; + + memcpy(both + existing_length, str, n); + both[existing_length + n] = '\0'; + + *dest = both; + return true; +} + +bool +linear_strcat(void *parent, char **dest, const char *str) +{ + return linear_cat(parent, dest, str, strlen(str)); +} diff --git a/src/util/ralloc.h b/src/util/ralloc.h index d74a39875c1..3e2d342b45e 100644 --- a/src/util/ralloc.h +++ b/src/util/ralloc.h @@ -407,10 +407,6 @@ bool ralloc_asprintf_append (char **str, const char *fmt, ...) bool ralloc_vasprintf_append(char **str, const char *fmt, va_list args); /// @} -#ifdef __cplusplus -} /* end of extern "C" */ -#endif - /** * Declare C++ new and delete operators which use ralloc. * @@ -454,4 +450,84 @@ public: \ #define DECLARE_RZALLOC_CXX_OPERATORS(type) \ DECLARE_ALLOC_CXX_OPERATORS_TEMPLATE(type, rzalloc_size) +#define DECLARE_LINEAR_ALLOC_CXX_OPERATORS(type) \ + DECLARE_ALLOC_CXX_OPERATORS_TEMPLATE(type, linear_alloc_child) + +#define DECLARE_LINEAR_ZALLOC_CXX_OPERATORS(type) \ + DECLARE_ALLOC_CXX_OPERATORS_TEMPLATE(type, linear_zalloc_child) + + +/** + * Do a fast allocation from the linear buffer, also known as the child node + * from the allocator's point of view. It can't be freed directly. You have + * to free the parent or the ralloc parent. + * + * \param parent parent node of the linear allocator + * \param size size to allocate (max 32 bits) + */ +void *linear_alloc_child(void *parent, unsigned size); + +/** + * Allocate a parent node that will hold linear buffers. The returned + * allocation is actually the first child node, but it's also the handle + * of the parent node. Use it for all child node allocations. + * + * \param ralloc_ctx ralloc context, must not be NULL + * \param size size to allocate (max 32 bits) + */ +void *linear_alloc_parent(void *ralloc_ctx, unsigned size); + +/** + * Same as linear_alloc_child, but also clears memory. + */ +void *linear_zalloc_child(void *parent, unsigned size); + +/** + * Same as linear_alloc_parent, but also clears memory. + */ +void *linear_zalloc_parent(void *ralloc_ctx, unsigned size); + +/** + * Free the linear parent node. This will free all child nodes too. + * Freeing the ralloc parent will also free this. + */ +void linear_free_parent(void *ptr); + +/** + * Same as ralloc_steal, but steals the linear parent node. + */ +void ralloc_steal_linear_parent(void *new_ralloc_ctx, void *ptr); + +/** + * Return the ralloc parent of the linear parent node. + */ +void *ralloc_parent_of_linear_parent(void *ptr); + +/** + * Same as realloc except that the linear allocator doesn't free child nodes, + * so it's reduced to memory duplication. It's used in places where + * reallocation is required. Don't use it often. It's much slower than + * realloc. + */ +void *linear_realloc(void *parent, void *old, unsigned new_size); + +/* The functions below have the same semantics as their ralloc counterparts, + * except that they always allocate a linear child node. + */ +char *linear_strdup(void *parent, const char *str); +char *linear_asprintf(void *parent, const char *fmt, ...); +char *linear_vasprintf(void *parent, const char *fmt, va_list args); +bool linear_asprintf_append(void *parent, char **str, const char *fmt, ...); +bool linear_vasprintf_append(void *parent, char **str, const char *fmt, + va_list args); +bool linear_asprintf_rewrite_tail(void *parent, char **str, size_t *start, + const char *fmt, ...); +bool linear_vasprintf_rewrite_tail(void *parent, char **str, size_t *start, + const char *fmt, va_list args); +bool linear_strcat(void *parent, char **dest, const char *str); + +#ifdef __cplusplus +} /* end of extern "C" */ +#endif + #endif -- 2.30.2