qpb/linear_allocator.h

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * linear_allocator.h
   4  *
   5  * @copyright Copyright (C) 2016 Sproute Networks, Inc.
   6  *
   7  * @author Avneesh Sachdev <avneesh@sproute.com>
   8  */
   9
  10 /*
  11  * Header file for the linear allocator.
  12  *
  13  * An allocator that allocates memory by walking down towards the end
  14  * of a buffer. No attempt is made to reuse blocks that are freed
  15  * subsequently. The assumption is that the buffer is big enough to
  16  * cover allocations for a given purpose.
  17  */
  18 #include <assert.h>
  19 #include <string.h>
  20 #include <stdint.h>
  21 #include <stddef.h>
  22
  23 /*
  24  * Alignment for block allocated by the allocator. Must be a power of 2.
  25  */
  26 #define LINEAR_ALLOCATOR_ALIGNMENT        8
  27
  28 #define LINEAR_ALLOCATOR_ALIGN(value)                                          \
  29         (((value) + LINEAR_ALLOCATOR_ALIGNMENT - 1)                            \
  30          & ~(LINEAR_ALLOCATOR_ALIGNMENT - 1));
  31
  32 /*
  33  * linear_allocator_align_ptr
  34  */
  35 static inline char *linear_allocator_align_ptr(char *ptr)
  36 {
  37         return (char *)LINEAR_ALLOCATOR_ALIGN((intptr_t)ptr);
  38 }
  39
  40 typedef struct linear_allocator_t_ {
  41         char *buf;
  42
  43         /*
  44          * Current location in the buffer.
  45          */
  46         char *cur;
  47
  48         /*
  49          * End of buffer.
  50          */
  51         char *end;
  52
  53         /*
  54          * Version number of the allocator, this is bumped up when the allocator
  55          * is reset and helps identifies bad frees.
  56          */
  57         uint32_t version;
  58
  59         /*
  60          * The number of blocks that are currently allocated.
  61          */
  62         int num_allocated;
  63 } linear_allocator_t;
  64
  65 /*
  66  * linear_allocator_block_t
  67  *
  68  * Header structure at the begining of each block.
  69  */
  70 typedef struct linear_allocator_block_t_ {
  71         uint32_t flags;
  72
  73         /*
  74          * The version of the allocator when this block was allocated.
  75          */
  76         uint32_t version;
  77         char data[0];
  78 } linear_allocator_block_t;
  79
  80 #define LINEAR_ALLOCATOR_BLOCK_IN_USE 0x01
  81
  82 #define LINEAR_ALLOCATOR_HDR_SIZE (sizeof(linear_allocator_block_t))
  83
  84 /*
  85  * linear_allocator_block_size
  86  *
  87  * The total amount of space a block will take in the buffer,
  88  * including the size of the header.
  89  */
  90 static inline size_t linear_allocator_block_size(size_t user_size)
  91 {
  92         return LINEAR_ALLOCATOR_ALIGN(LINEAR_ALLOCATOR_HDR_SIZE + user_size);
  93 }
  94
  95 /*
  96  * linear_allocator_ptr_to_block
  97  */
  98 static inline linear_allocator_block_t *linear_allocator_ptr_to_block(void *ptr)
  99 {
 100         void *block_ptr;
 101         block_ptr = ((char *)ptr) - offsetof(linear_allocator_block_t, data);
 102         return block_ptr;
 103 }
 104
 105 /*
 106  * linear_allocator_init
 107  */
 108 static inline void linear_allocator_init(linear_allocator_t *allocator,
 109                                          char *buf, size_t buf_len)
 110 {
 111         memset(allocator, 0, sizeof(*allocator));
 112
 113         assert(linear_allocator_align_ptr(buf) == buf);
 114         allocator->buf = buf;
 115         allocator->cur = buf;
 116         allocator->end = buf + buf_len;
 117 }
 118
 119 /*
 120  * linear_allocator_reset
 121  *
 122  * Prepare an allocator for reuse.
 123  *
 124  * *** NOTE ** This implicitly frees all the blocks in the allocator.
 125  */
 126 static inline void linear_allocator_reset(linear_allocator_t *allocator)
 127 {
 128         allocator->num_allocated = 0;
 129         allocator->version++;
 130         allocator->cur = allocator->buf;
 131 }
 132
 133 /*
 134  * linear_allocator_alloc
 135  */
 136 static inline void *linear_allocator_alloc(linear_allocator_t *allocator,
 137                                            size_t user_size)
 138 {
 139         size_t block_size;
 140         linear_allocator_block_t *block;
 141
 142         block_size = linear_allocator_block_size(user_size);
 143
 144         if (allocator->cur + block_size > allocator->end) {
 145                 return NULL;
 146         }
 147
 148         block = (linear_allocator_block_t *)allocator->cur;
 149         allocator->cur += block_size;
 150
 151         block->flags = LINEAR_ALLOCATOR_BLOCK_IN_USE;
 152         block->version = allocator->version;
 153         allocator->num_allocated++;
 154         return block->data;
 155 }
 156
 157 /*
 158  * linear_allocator_free
 159  */
 160 static inline void linear_allocator_free(linear_allocator_t *allocator,
 161                                          void *ptr)
 162 {
 163         linear_allocator_block_t *block;
 164
 165         if (((char *)ptr) < allocator->buf || ((char *)ptr) >= allocator->end) {
 166                 assert(0);
 167                 return;
 168         }
 169
 170         block = linear_allocator_ptr_to_block(ptr);
 171         if (block->version != allocator->version) {
 172                 assert(0);
 173                 return;
 174         }
 175
 176         block->flags = block->flags & ~LINEAR_ALLOCATOR_BLOCK_IN_USE;
 177
 178         if (--allocator->num_allocated < 0) {
 179                 assert(0);
 180         }
 181 }