[Mesa-dev] [PATCH 06/15] ralloc: add a linear allocator as a child node of ralloc

[Nicolai Hähnle]

On 08.10.2016 12:58, Marek Olšák wrote:
> From: Marek Olšák <marek.olsak at amd.com>

It would be useful to hook this up with Valgrind and address sanitizer. 
Some drivers already do that; basically, there are macros 
VALGRIND_MAKE_MEM_{NOACCESS, UNDEFINED, DEFINED} in valgrind/memcheck.h, 
and similarly address sanitizer has 
__asan_{poison,unpoison}_memory_region intrinsics.

The linear_size_chunks can serve as red zones helping to catch array 
overflows.

This doesn't necessarily have to be in the same commit, but it would be 
good to do it soon.


>
> ---
>  src/util/ralloc.c | 355 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  src/util/ralloc.h |  84 ++++++++++++-
>  2 files changed, 435 insertions(+), 4 deletions(-)
>
> diff --git a/src/util/ralloc.c b/src/util/ralloc.c
> index bf21ac3..a8e660f 100644
> --- a/src/util/ralloc.c
> +++ b/src/util/ralloc.c
> @@ -522,10 +522,365 @@ ralloc_vasprintf_rewrite_tail(char **str, size_t *start, const char *fmt,
>
>     ptr = resize(*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;
>  }
> +
> +/***************************************************************************
> + * 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(x, y) (((x) + (y) - 1) & ~((y) - 1))

Please rename this to ALIGN_POT or similar.


> +#define MIN_LINEAR_BUFSIZE 2048
> +#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(size, 8);

sizeof(size_t) instead of 8? In a similar vein, you could use size_t in 
linear_size_chunk.


> +   full_size = sizeof(linear_size_chunk) + size;
> +
> +   if (likely(latest->offset + full_size <= latest->size)) {
> +alloc:

Please avoid the goto by inverting the logic here.


> +      ptr = (linear_size_chunk *)((char*)&latest[1] + latest->offset);
> +      ptr->size = size;
> +      latest->offset += full_size;
> +      return &ptr[1];
> +   }
> +
> +   /* 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;
> +
> +   goto alloc;
> +}
> +
> +void *
> +linear_alloc_parent(void *ralloc_ctx, unsigned size)
> +{
> +   linear_header *node;
> +
> +   if (unlikely(!ralloc_ctx))
> +      return NULL;
> +
> +   size = ALIGN(size, 8);
> +
> +   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)
> +{
> +   size_t 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, old_size > new_size ? new_size : old_size);

Use MIN2.

Nicolai