debianpkg: Add debian9 backport to distribution tar

[mirror_frr.git] / qpb / linear_allocator.h

/*
 * 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);
	}
}