qpb/linear_allocator.h

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