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
  21  * along with Quagga; see the file COPYING.  If not, write to the Free
  22  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  23  * 02111-1307, USA.
  24  */
  25
  26 /*
  27  * Header file for the linear allocator.
  28  *
  29  * An allocator that allocates memory by walking down towards the end
  30  * of a buffer. No attempt is made to reuse blocks that are freed
  31  * subsequently. The assumption is that the buffer is big enough to
  32  * cover allocations for a given purpose.
  33  */
  34 #include <assert.h>
  35 #include <string.h>
  36 #include <stdint.h>
  37 #include <stddef.h>
  38
  39 /*
  40  * Alignment for block allocated by the allocator. Must be a power of 2.
  41  */
  42 #define LINEAR_ALLOCATOR_ALIGNMENT        8
  43
  44 #define LINEAR_ALLOCATOR_ALIGN(value)                                   \
  45   (((value) + LINEAR_ALLOCATOR_ALIGNMENT - 1) & ~(LINEAR_ALLOCATOR_ALIGNMENT - 1));
  46
  47 /*
  48  * linear_allocator_align_ptr
  49  */
  50 static inline char *
  51 linear_allocator_align_ptr (char *ptr)
  52 {
  53   return (char *) LINEAR_ALLOCATOR_ALIGN ((intptr_t) ptr);
  54 }
  55
  56 typedef struct linear_allocator_t_
  57 {
  58   char *buf;
  59
  60   /*
  61    * Current location in the buffer.
  62    */
  63   char *cur;
  64
  65   /*
  66    * End of buffer.
  67    */
  68   char *end;
  69
  70   /*
  71    * Version number of the allocator, this is bumped up when the allocator
  72    * is reset and helps identifies bad frees.
  73    */
  74   uint32_t version;
  75
  76   /*
  77    * The number of blocks that are currently allocated.
  78    */
  79   int num_allocated;
  80 } linear_allocator_t;
  81
  82 /*
  83  * linear_allocator_block_t
  84  *
  85  * Header structure at the begining of each block.
  86  */
  87 typedef struct linear_allocator_block_t_
  88 {
  89   uint32_t flags;
  90
  91   /*
  92    * The version of the allocator when this block was allocated.
  93    */
  94   uint32_t version;
  95   char data[0];
  96 } linear_allocator_block_t;
  97
  98 #define LINEAR_ALLOCATOR_BLOCK_IN_USE 0x01
  99
 100 #define LINEAR_ALLOCATOR_HDR_SIZE (sizeof(linear_allocator_block_t))
 101
 102 /*
 103  * linear_allocator_block_size
 104  *
 105  * The total amount of space a block will take in the buffer,
 106  * including the size of the header.
 107  */
 108 static inline size_t
 109 linear_allocator_block_size (size_t user_size)
 110 {
 111   return LINEAR_ALLOCATOR_ALIGN (LINEAR_ALLOCATOR_HDR_SIZE + user_size);
 112 }
 113
 114 /*
 115  * linear_allocator_ptr_to_block
 116  */
 117 static inline linear_allocator_block_t *
 118 linear_allocator_ptr_to_block (void *ptr)
 119 {
 120   void *block_ptr;
 121   block_ptr = ((char *) ptr) - offsetof (linear_allocator_block_t, data);
 122   return block_ptr;
 123 }
 124
 125 /*
 126  * linear_allocator_init
 127  */
 128 static inline void
 129 linear_allocator_init (linear_allocator_t * allocator, char *buf,
 130                        size_t buf_len)
 131 {
 132   memset (allocator, 0, sizeof (*allocator));
 133
 134   assert (linear_allocator_align_ptr (buf) == buf);
 135   allocator->buf = buf;
 136   allocator->cur = buf;
 137   allocator->end = buf + buf_len;
 138 }
 139
 140 /*
 141  * linear_allocator_reset
 142  *
 143  * Prepare an allocator for reuse.
 144  *
 145  * *** NOTE ** This implicitly frees all the blocks in the allocator.
 146  */
 147 static inline void
 148 linear_allocator_reset (linear_allocator_t *allocator)
 149 {
 150   allocator->num_allocated = 0;
 151   allocator->version++;
 152   allocator->cur = allocator->buf;
 153 }
 154
 155 /*
 156  * linear_allocator_alloc
 157  */
 158 static inline void *
 159 linear_allocator_alloc (linear_allocator_t *allocator, size_t user_size)
 160 {
 161   size_t block_size;
 162   linear_allocator_block_t *block;
 163
 164   block_size = linear_allocator_block_size (user_size);
 165
 166   if (allocator->cur + block_size > allocator->end)
 167     {
 168       return NULL;
 169     }
 170
 171   block = (linear_allocator_block_t *) allocator->cur;
 172   allocator->cur += block_size;
 173
 174   block->flags = LINEAR_ALLOCATOR_BLOCK_IN_USE;
 175   block->version = allocator->version;
 176   allocator->num_allocated++;
 177   return block->data;
 178 }
 179
 180 /*
 181  * linear_allocator_free
 182  */
 183 static inline void
 184 linear_allocator_free (linear_allocator_t *allocator, void *ptr)
 185 {
 186   linear_allocator_block_t *block;
 187
 188   if (((char *) ptr) < allocator->buf || ((char *) ptr) >= allocator->end)
 189     {
 190       assert (0);
 191       return;
 192     }
 193
 194   block = linear_allocator_ptr_to_block (ptr);
 195   if (block->version != allocator->version)
 196     {
 197       assert (0);
 198       return;
 199     }
 200
 201   block->flags = block->flags & ~LINEAR_ALLOCATOR_BLOCK_IN_USE;
 202
 203   if (--allocator->num_allocated < 0)
 204     {
 205       assert (0);
 206     }
 207 }