ccan/ccan/antithread/alloc/tiny.c

/* Licensed under LGPLv2.1+ - see LICENSE file for details */
#include "tiny.h"
#include "bitops.h"
#include <assert.h>
#include <stdlib.h>
#include <string.h>

/* One byte header, one byte data. */
#define MIN_BLOCK_SIZE 2

/* Bit 7 (in any byte) == start or end. */
#define TERM_BIT 0x80
/* Bit 6 (first and last byte) == one byte long. */
#define SINGLE_BYTE 0x40
/* Bit 5 (of first byte) == "is this block free?" */
#define FREE_BIT 0x20

#define MAX_FREE_CACHED_SIZE 256

/* Val is usually offset by MIN_BLOCK_SIZE here. */
static unsigned encode_length(unsigned long val)
{
	unsigned int bits = afls(val);
	/* 5 bits in first byte. */
	if (bits <= 5)
		return 1;
	/* 6 bits in last byte, 7 bits in middle ones. */
	return 2 + (bits - 5) / 7;
}

/* Header is included in length, so we might need an extra byte. */
static unsigned encode_len_with_header(unsigned long len)
{
	unsigned int hdrlen = 1;

	assert(len);
	while (encode_length(len + hdrlen - MIN_BLOCK_SIZE) != hdrlen)
		hdrlen = encode_length(len + hdrlen - MIN_BLOCK_SIZE);

	return hdrlen;
}

/* Encoding can be read from front or back; 0 is invalid at either
 * start or end.  Returns bytes used for header. */
static unsigned encode(unsigned long len, bool free, unsigned char arr[])
{
	unsigned int hdrlen = 1;

	/* We can never have a length < MIN_BLOCK_SIZE. */
	assert(len >= MIN_BLOCK_SIZE);
	len -= MIN_BLOCK_SIZE;

	/* First byte always contains free bit. */
	arr[0] = TERM_BIT | (free ? FREE_BIT : 0);
	/* Also holds 5 bits of data (0 - 31) */
	arr[0] |= (len & 0x1F);
	len >>= 5;

	/* One byte only? */
	if (!len) {
		arr[0] |= SINGLE_BYTE;
		return hdrlen;
	}

	/* Middle bytes. */
	while (len >= (1 << 6)) {
		/* Next 7 data bits */
		arr[hdrlen++] = (len & 0x7F);
		len >>= 7;
	}
	arr[hdrlen++] = (len | TERM_BIT);
	return hdrlen;
}

/* Returns bytes used for header. */
static unsigned decode(unsigned long *len, bool *free, const unsigned char *arr)
{
	unsigned int hdrlen = 0, bits = 5;

	/* Free flag is in bit 5 */
	*free = (arr[hdrlen] & FREE_BIT);
	/* Bottom five bits are data. */
	*len = (arr[hdrlen] & 0x1f);
	if (!(arr[hdrlen++] & SINGLE_BYTE)) {
		/* Multi-byte encoding? */
		while (!(arr[hdrlen] & TERM_BIT)) {
			/* 7 more data bits. */
			*len |= (arr[hdrlen] & 0x7fUL) << bits;
			hdrlen++;
			bits += 7;
		}
		/* Final byte has 6 bits. */
		*len |= (arr[hdrlen] & 0x3fUL) << bits;
		hdrlen++;
	}

	*len += MIN_BLOCK_SIZE;
	return hdrlen;
}

/* We keep a helper array for freed mem, one byte per k. */
static unsigned long free_array_size(unsigned long poolsize)
{
	return poolsize / 1024;
}

/* We have series of 69 free sizes like so:
 * 1, 2, 3, 4.  6, 8, 10, 12, 14, 16. 20, 24, 28, 32... 252.
 */
static unsigned long free_array_off(unsigned long size)
{
	unsigned long off;

	if (size <= 4)
		off = size - 1;
	else if (size <= 16)
		off = size / 2 + 1;
	else
		off = size / 4 + 5;

	off *= 3;
	return off;
}

void tiny_alloc_init(void *pool, unsigned long poolsize)
{
	/* We start with free array, and then the rest is free. */
	unsigned long arrsize = free_array_size(poolsize);

	/* Do nothing with 1 byte or less! */
	if (poolsize < MIN_BLOCK_SIZE)
		return;

	memset(pool, 0, arrsize);
	encode(poolsize - arrsize, true, (unsigned char *)pool + arrsize);
}

/* Walk through and try to coalesce */
static bool try_coalesce(unsigned char *pool, unsigned long poolsize)
{
	unsigned long len, prev_off = 0, prev_len = 0, off;
	bool free, prev_free = false, coalesced = false;

	off = free_array_size(poolsize);
	do {
		decode(&len, &free, pool + off);
		if (free && prev_free) {
			prev_len += len;
			encode(prev_len, true, pool + prev_off);
			coalesced = true;
		} else {
			prev_free = free;
			prev_off = off;
			prev_len = len;
		}
		off += len;
	} while (off < poolsize);

	/* Clear the free array. */
	if (coalesced)
		memset(pool, 0, free_array_size(poolsize));

	return coalesced;
}

static bool long_enough(unsigned long offset, unsigned long len,
			unsigned long size, unsigned long align)
{
	unsigned long end = offset + len;

	offset += encode_len_with_header(len);
	offset = align_up(offset, align);
	return offset + size <= end;
}

static void add_to_free_array(unsigned char *arr,
			      unsigned long poolsize,
			      unsigned long size,
			      unsigned long off)
{
	unsigned long fa_off;

	if (size >= MAX_FREE_CACHED_SIZE)
		return;

	for (fa_off = free_array_off(size);
	     fa_off + 3 < free_array_size(poolsize);
	     fa_off += free_array_off(MAX_FREE_CACHED_SIZE)) {
		if (!arr[fa_off] && !arr[fa_off+1] && !arr[fa_off+2]) {
			arr[fa_off] = (off >> 16);
			arr[fa_off+1] = (off >> 8);
			arr[fa_off+2] = off;
			break;
		}
	}
}

void *tiny_alloc_get(void *pool, unsigned long poolsize,
		     unsigned long size, unsigned long align)
{
	unsigned long arrsize = free_array_size(poolsize);
	unsigned long len, off, actual, hdr, free_bucket;
	long fa_off;
	unsigned char *arr = pool;
	bool free, coalesced = false;

	/* We can't do anything with tiny pools. */
	if (poolsize < MIN_BLOCK_SIZE)
		return NULL;

	/* We don't do zero-allocs; allows 1 more offset in encoding. */
	if (!size)
		size = 1;

	/* Look for entries in free array, starting from right size up. */
	for (free_bucket = free_array_off(size);
	     free_bucket < free_array_off(MAX_FREE_CACHED_SIZE);
	     free_bucket += 3) {
		for (fa_off = free_bucket;
		     fa_off + 3 < free_array_size(poolsize);
		     fa_off += free_array_off(MAX_FREE_CACHED_SIZE)) {
			off = ((unsigned long)arr[fa_off]) << 16
				| ((unsigned long)arr[fa_off+1]) << 8
				| ((unsigned long)arr[fa_off+2]);
			if (!off)
				continue;

			decode(&len, &free, arr + off);
			if (long_enough(off, len, size, align)) {
				/* Remove it. */
				memset(&arr[fa_off], 0, 3);
				goto found;
			}
		}
	}

again:
	off = arrsize;

	decode(&len, &free, arr + off);
	while (!free || !long_enough(off, len, size, align)) {
		/* Refill free array as we go. */
		if (free && coalesced)
			add_to_free_array(arr, poolsize, len, off);

		off += len;
		/* Hit end? */
		if (off == poolsize) {
			if (!coalesced && try_coalesce(pool, poolsize)) {
				coalesced = true;
				goto again;
			}
			return NULL;
		}
		decode(&len, &free, arr + off);
	}

found:
	/* We have a free block.  Since we walk from front, take far end. */
	actual = ((off + len - size) & ~(align - 1));
	hdr = actual - encode_len_with_header(off + len - actual);


	/* Do we have enough room to split? */
	if (hdr - off >= MIN_BLOCK_SIZE) {
		encode(hdr - off, true, arr + off);
		add_to_free_array(arr, poolsize, hdr - off, off);
	} else {
		hdr = off;
	}

	/* Make sure that we are all-zero up to actual, so we can walk back
	 * and find header. */
	memset(arr + hdr, 0, actual - hdr);

	/* Create header for allocated block. */
	encode(off + len - hdr, false, arr + hdr);

	return arr + actual;
}

static unsigned char *to_hdr(void *p)
{
	unsigned char *hdr = p;

	/* Walk back to find end of header. */
	while (!*(--hdr));
	assert(*hdr & TERM_BIT);

	/* Now walk back to find start of header. */
	if (!(*hdr & SINGLE_BYTE)) {
		while (!(*(--hdr) & TERM_BIT));
	}
	return hdr;
}

void tiny_alloc_free(void *pool, unsigned long poolsize, void *freep)
{
	unsigned long len;
	unsigned char *arr = pool;
	unsigned char *hdr;
	bool free;

	/* Too small to do anything. */
	if (poolsize < MIN_BLOCK_SIZE)
		return;

	hdr = to_hdr(freep);

	decode(&len, &free, hdr);
	assert(!free);
	hdr[0] |= FREE_BIT;

	/* If an empty slot, put this in free array. */
	add_to_free_array(pool, poolsize, len, hdr - arr);
}

unsigned long tiny_alloc_size(void *pool, unsigned long poolsize, void *p)
{
	unsigned char *hdr = to_hdr(p);
	unsigned long len, hdrlen;
	bool free;

	hdrlen = decode(&len, &free, hdr);
	return len - hdrlen;
}

/* Useful for gdb breakpoints. */
static bool tiny_check_fail(void)
{
	return false;
}

static bool check_decode(const unsigned char *arr, unsigned long len)
{
	unsigned int i;

	if (len == 0)
		return tiny_check_fail();
	if (!(arr[0] & TERM_BIT))
		return tiny_check_fail();
	if (arr[0] & SINGLE_BYTE)
		return true;
	for (i = 1; i < len; i++) {
		if (arr[i] & TERM_BIT)
			return true;
	}
	return tiny_check_fail();
}

bool tiny_alloc_check(void *pool, unsigned long poolsize)
{
	unsigned long arrsize = free_array_size(poolsize);
	unsigned char *arr = pool;
	unsigned long len, off, hdrlen;
	unsigned long i, freearr[arrsize], num_freearr = 0;
	bool free;

	if (poolsize < MIN_BLOCK_SIZE)
		return true;

	for (i = 0; i + 3 < free_array_size(poolsize); i += 3) {
		off = ((unsigned long)arr[i]) << 16
			| ((unsigned long)arr[i+1]) << 8
			| ((unsigned long)arr[i+2]);
		if (!off)
			continue;

		if (off >= poolsize)
			return tiny_check_fail();
		freearr[num_freearr++] = off;
	}

	for (off = arrsize; off < poolsize; off += len) {
		/* We should have a valid header. */
		if (!check_decode(arr + off, poolsize - off))
			return false;
		hdrlen = decode(&len, &free, arr + off);
		if (off + len > poolsize)
			return tiny_check_fail();
		if (hdrlen != encode_length(len - MIN_BLOCK_SIZE))
			return tiny_check_fail();
		for (i = 0; i < num_freearr; i++) {
			if (freearr[i] == off) {
				if (!free)
					return tiny_check_fail();
				memmove(&freearr[i], &freearr[i+1],
					(num_freearr-- - (i + 1))
					* sizeof(freearr[i]));
				break;
			}
		}
	}

	/* Now we should have found everything in freearr. */
	if (num_freearr)
		return tiny_check_fail();

	/* Now check that sizes are correct. */
	for (i = 0; i + 3 < free_array_size(poolsize); i += 3) {
		unsigned long fa_off;

		off = ((unsigned long)arr[i]) << 16
			| ((unsigned long)arr[i+1]) << 8
			| ((unsigned long)arr[i+2]);
		if (!off)
			continue;

		decode(&len, &free, arr + off);

		/* Would we expect to find this length in this bucket? */
		if (len >= MAX_FREE_CACHED_SIZE)
			return tiny_check_fail();

		for (fa_off = free_array_off(len);
		     fa_off + 3 < free_array_size(poolsize);
		     fa_off += free_array_off(MAX_FREE_CACHED_SIZE)) {
			if (fa_off == i)
				break;
		}
		if (fa_off != i)
			return tiny_check_fail();
	}

	return true;
}

/* FIXME: Implement. */
void tiny_alloc_visualize(FILE *out, void *pool, unsigned long poolsize)
{
}