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) & ~(LINEAR_ALLOCATOR_ALIGNMENT - 1));
  45
  46 /*
  47  * linear_allocator_align_ptr
  48  */
  49 static inline char *
  50 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 {
  57   char *buf;
  58
  59   /*
  60    * Current location in the buffer.
  61    */
  62   char *cur;
  63
  64   /*
  65    * End of buffer.
  66    */
  67   char *end;
  68
  69   /*
  70    * Version number of the allocator, this is bumped up when the allocator
  71    * is reset and helps identifies bad frees.
  72    */
  73   uint32_t version;
  74
  75   /*
  76    * The number of blocks that are currently allocated.
  77    */
  78   int num_allocated;
  79 } linear_allocator_t;
  80
  81 /*
  82  * linear_allocator_block_t
  83  *
  84  * Header structure at the begining of each block.
  85  */
  86 typedef struct linear_allocator_block_t_
  87 {
  88   uint32_t flags;
  89
  90   /*
  91    * The version of the allocator when this block was allocated.
  92    */
  93   uint32_t version;
  94   char data[0];
  95 } linear_allocator_block_t;
  96
  97 #define LINEAR_ALLOCATOR_BLOCK_IN_USE 0x01
  98
  99 #define LINEAR_ALLOCATOR_HDR_SIZE (sizeof(linear_allocator_block_t))
 100
 101 /*
 102  * linear_allocator_block_size
 103  *
 104  * The total amount of space a block will take in the buffer,
 105  * including the size of the header.
 106  */
 107 static inline size_t
 108 linear_allocator_block_size (size_t user_size)
 109 {
 110   return LINEAR_ALLOCATOR_ALIGN (LINEAR_ALLOCATOR_HDR_SIZE + user_size);
 111 }
 112
 113 /*
 114  * linear_allocator_ptr_to_block
 115  */
 116 static inline linear_allocator_block_t *
 117 linear_allocator_ptr_to_block (void *ptr)
 118 {
 119   void *block_ptr;
 120   block_ptr = ((char *) ptr) - offsetof (linear_allocator_block_t, data);
 121   return block_ptr;
 122 }
 123
 124 /*
 125  * linear_allocator_init
 126  */
 127 static inline void
 128 linear_allocator_init (linear_allocator_t * allocator, char *buf,
 129                        size_t buf_len)
 130 {
 131   memset (allocator, 0, sizeof (*allocator));
 132
 133   assert (linear_allocator_align_ptr (buf) == buf);
 134   allocator->buf = buf;
 135   allocator->cur = buf;
 136   allocator->end = buf + buf_len;
 137 }
 138
 139 /*
 140  * linear_allocator_reset
 141  *
 142  * Prepare an allocator for reuse.
 143  *
 144  * *** NOTE ** This implicitly frees all the blocks in the allocator.
 145  */
 146 static inline void
 147 linear_allocator_reset (linear_allocator_t *allocator)
 148 {
 149   allocator->num_allocated = 0;
 150   allocator->version++;
 151   allocator->cur = allocator->buf;
 152 }
 153
 154 /*
 155  * linear_allocator_alloc
 156  */
 157 static inline void *
 158 linear_allocator_alloc (linear_allocator_t *allocator, size_t user_size)
 159 {
 160   size_t block_size;
 161   linear_allocator_block_t *block;
 162
 163   block_size = linear_allocator_block_size (user_size);
 164
 165   if (allocator->cur + block_size > allocator->end)
 166     {
 167       return NULL;
 168     }
 169
 170   block = (linear_allocator_block_t *) allocator->cur;
 171   allocator->cur += block_size;
 172
 173   block->flags = LINEAR_ALLOCATOR_BLOCK_IN_USE;
 174   block->version = allocator->version;
 175   allocator->num_allocated++;
 176   return block->data;
 177 }
 178
 179 /*
 180  * linear_allocator_free
 181  */
 182 static inline void
 183 linear_allocator_free (linear_allocator_t *allocator, void *ptr)
 184 {
 185   linear_allocator_block_t *block;
 186
 187   if (((char *) ptr) < allocator->buf || ((char *) ptr) >= allocator->end)
 188     {
 189       assert (0);
 190       return;
 191     }
 192
 193   block = linear_allocator_ptr_to_block (ptr);
 194   if (block->version != allocator->version)
 195     {
 196       assert (0);
 197       return;
 198     }
 199
 200   block->flags = block->flags & ~LINEAR_ALLOCATOR_BLOCK_IN_USE;
 201
 202   if (--allocator->num_allocated < 0)
 203     {
 204       assert (0);
 205     }
 206 }