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)                            \
  46          & ~(LINEAR_ALLOCATOR_ALIGNMENT - 1));
  47
  48 /*
  49  * linear_allocator_align_ptr
  50  */
  51 static inline char *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         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         uint32_t flags;
  88
  89         /*
  90          * The version of the allocator when this block was allocated.
  91          */
  92         uint32_t version;
  93         char data[0];
  94 } linear_allocator_block_t;
  95
  96 #define LINEAR_ALLOCATOR_BLOCK_IN_USE 0x01
  97
  98 #define LINEAR_ALLOCATOR_HDR_SIZE (sizeof(linear_allocator_block_t))
  99
 100 /*
 101  * linear_allocator_block_size
 102  *
 103  * The total amount of space a block will take in the buffer,
 104  * including the size of the header.
 105  */
 106 static inline size_t linear_allocator_block_size(size_t user_size)
 107 {
 108         return LINEAR_ALLOCATOR_ALIGN(LINEAR_ALLOCATOR_HDR_SIZE + user_size);
 109 }
 110
 111 /*
 112  * linear_allocator_ptr_to_block
 113  */
 114 static inline linear_allocator_block_t *linear_allocator_ptr_to_block(void *ptr)
 115 {
 116         void *block_ptr;
 117         block_ptr = ((char *)ptr) - offsetof(linear_allocator_block_t, data);
 118         return block_ptr;
 119 }
 120
 121 /*
 122  * linear_allocator_init
 123  */
 124 static inline void linear_allocator_init(linear_allocator_t *allocator,
 125                                          char *buf, size_t buf_len)
 126 {
 127         memset(allocator, 0, sizeof(*allocator));
 128
 129         assert(linear_allocator_align_ptr(buf) == buf);
 130         allocator->buf = buf;
 131         allocator->cur = buf;
 132         allocator->end = buf + buf_len;
 133 }
 134
 135 /*
 136  * linear_allocator_reset
 137  *
 138  * Prepare an allocator for reuse.
 139  *
 140  * *** NOTE ** This implicitly frees all the blocks in the allocator.
 141  */
 142 static inline void linear_allocator_reset(linear_allocator_t *allocator)
 143 {
 144         allocator->num_allocated = 0;
 145         allocator->version++;
 146         allocator->cur = allocator->buf;
 147 }
 148
 149 /*
 150  * linear_allocator_alloc
 151  */
 152 static inline void *linear_allocator_alloc(linear_allocator_t *allocator,
 153                                            size_t user_size)
 154 {
 155         size_t block_size;
 156         linear_allocator_block_t *block;
 157
 158         block_size = linear_allocator_block_size(user_size);
 159
 160         if (allocator->cur + block_size > allocator->end) {
 161                 return NULL;
 162         }
 163
 164         block = (linear_allocator_block_t *)allocator->cur;
 165         allocator->cur += block_size;
 166
 167         block->flags = LINEAR_ALLOCATOR_BLOCK_IN_USE;
 168         block->version = allocator->version;
 169         allocator->num_allocated++;
 170         return block->data;
 171 }
 172
 173 /*
 174  * linear_allocator_free
 175  */
 176 static inline void linear_allocator_free(linear_allocator_t *allocator,
 177                                          void *ptr)
 178 {
 179         linear_allocator_block_t *block;
 180
 181         if (((char *)ptr) < allocator->buf || ((char *)ptr) >= allocator->end) {
 182                 assert(0);
 183                 return;
 184         }
 185
 186         block = linear_allocator_ptr_to_block(ptr);
 187         if (block->version != allocator->version) {
 188                 assert(0);
 189                 return;
 190         }
 191
 192         block->flags = block->flags & ~LINEAR_ALLOCATOR_BLOCK_IN_USE;
 193
 194         if (--allocator->num_allocated < 0) {
 195                 assert(0);
 196         }
 197 }