123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207 |
- /*
- * linear_allocator.h
- *
- * @copyright Copyright (C) 2016 Sproute Networks, Inc.
- *
- * @author Avneesh Sachdev <avneesh@sproute.com>
- *
- * This file is part of Quagga.
- *
- * Quagga is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; either version 2, or (at your option) any
- * later version.
- *
- * Quagga is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with Quagga; see the file COPYING. If not, write to the Free
- * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
- * 02111-1307, USA.
- */
- /*
- * Header file for the linear allocator.
- *
- * An allocator that allocates memory by walking down towards the end
- * of a buffer. No attempt is made to reuse blocks that are freed
- * subsequently. The assumption is that the buffer is big enough to
- * cover allocations for a given purpose.
- */
- #include <assert.h>
- #include <string.h>
- #include <stdint.h>
- #include <stddef.h>
- /*
- * Alignment for block allocated by the allocator. Must be a power of 2.
- */
- #define LINEAR_ALLOCATOR_ALIGNMENT 8
- #define LINEAR_ALLOCATOR_ALIGN(value) \
- (((value) + LINEAR_ALLOCATOR_ALIGNMENT - 1) & ~(LINEAR_ALLOCATOR_ALIGNMENT - 1));
- /*
- * linear_allocator_align_ptr
- */
- static inline char *
- linear_allocator_align_ptr (char *ptr)
- {
- return (char *) LINEAR_ALLOCATOR_ALIGN ((intptr_t) ptr);
- }
- typedef struct linear_allocator_t_
- {
- char *buf;
- /*
- * Current location in the buffer.
- */
- char *cur;
- /*
- * End of buffer.
- */
- char *end;
- /*
- * Version number of the allocator, this is bumped up when the allocator
- * is reset and helps identifies bad frees.
- */
- uint32_t version;
- /*
- * The number of blocks that are currently allocated.
- */
- int num_allocated;
- } linear_allocator_t;
- /*
- * linear_allocator_block_t
- *
- * Header structure at the begining of each block.
- */
- typedef struct linear_allocator_block_t_
- {
- uint32_t flags;
- /*
- * The version of the allocator when this block was allocated.
- */
- uint32_t version;
- char data[0];
- } linear_allocator_block_t;
- #define LINEAR_ALLOCATOR_BLOCK_IN_USE 0x01
- #define LINEAR_ALLOCATOR_HDR_SIZE (sizeof(linear_allocator_block_t))
- /*
- * linear_allocator_block_size
- *
- * The total amount of space a block will take in the buffer,
- * including the size of the header.
- */
- static inline size_t
- linear_allocator_block_size (size_t user_size)
- {
- return LINEAR_ALLOCATOR_ALIGN (LINEAR_ALLOCATOR_HDR_SIZE + user_size);
- }
- /*
- * linear_allocator_ptr_to_block
- */
- static inline linear_allocator_block_t *
- linear_allocator_ptr_to_block (void *ptr)
- {
- void *block_ptr;
- block_ptr = ((char *) ptr) - offsetof (linear_allocator_block_t, data);
- return block_ptr;
- }
- /*
- * linear_allocator_init
- */
- static inline void
- linear_allocator_init (linear_allocator_t * allocator, char *buf,
- size_t buf_len)
- {
- memset (allocator, 0, sizeof (*allocator));
- assert (linear_allocator_align_ptr (buf) == buf);
- allocator->buf = buf;
- allocator->cur = buf;
- allocator->end = buf + buf_len;
- }
- /*
- * linear_allocator_reset
- *
- * Prepare an allocator for reuse.
- *
- * *** NOTE ** This implicitly frees all the blocks in the allocator.
- */
- static inline void
- linear_allocator_reset (linear_allocator_t *allocator)
- {
- allocator->num_allocated = 0;
- allocator->version++;
- allocator->cur = allocator->buf;
- }
- /*
- * linear_allocator_alloc
- */
- static inline void *
- linear_allocator_alloc (linear_allocator_t *allocator, size_t user_size)
- {
- size_t block_size;
- linear_allocator_block_t *block;
- block_size = linear_allocator_block_size (user_size);
- if (allocator->cur + block_size > allocator->end)
- {
- return NULL;
- }
- block = (linear_allocator_block_t *) allocator->cur;
- allocator->cur += block_size;
- block->flags = LINEAR_ALLOCATOR_BLOCK_IN_USE;
- block->version = allocator->version;
- allocator->num_allocated++;
- return block->data;
- }
- /*
- * linear_allocator_free
- */
- static inline void
- linear_allocator_free (linear_allocator_t *allocator, void *ptr)
- {
- linear_allocator_block_t *block;
- if (((char *) ptr) < allocator->buf || ((char *) ptr) >= allocator->end)
- {
- assert (0);
- return;
- }
- block = linear_allocator_ptr_to_block (ptr);
- if (block->version != allocator->version)
- {
- assert (0);
- return;
- }
- block->flags = block->flags & ~LINEAR_ALLOCATOR_BLOCK_IN_USE;
- if (--allocator->num_allocated < 0)
- {
- assert (0);
- }
- }
|