ccan/ccan/alloc/tiny.c

#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

/* Val is usually offset by MIN_BLOCK_SIZE here. */
static unsigned encode_length(unsigned long val)
{
	unsigned int bits = fls(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, or 0 if won't fit. */
static unsigned encode(unsigned long len, bool free, unsigned char arr[],
		       size_t limit)
{
	unsigned int hdrlen = 1;

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

	if (encode_length(len) > limit)
		return 0;

	/* 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 recently-freed array, one byte per k. */
static unsigned long free_array_size(unsigned long poolsize)
{
	return poolsize / 1024;
}

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, poolsize - arrsize);
}

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

	off = free_array_size(poolsize);
	do {
		hdrlen = decode(&len, &free, pool + off);
		if (free && prev_free) {
			encode(prev_len + len, true, pool + prev_off,
			       poolsize - prev_off);
			coalesced = true;
		}
		prev_free = free;
		prev_off = off;
		prev_len = len;
		off += len;
	} while (off < 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;
}

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, hdrlen;
	bool free;

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

	/* FIXME: Look through free array. */

again:
	off = arrsize;

	hdrlen = decode(&len, &free, (unsigned char *)pool + off);
	while (!free || !long_enough(off, len, size, align)) {
		/* FIXME: Refill free array if this block is free. */

		/* Hit end? */
		off += len;
		if (off == poolsize) {
			if (try_coalesce(pool, poolsize))
				goto again;
			return NULL;
		}
		hdrlen = decode(&len, &free, (unsigned char *)pool + off);
	}

	/* 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, (unsigned char *)pool + off, poolsize);
	} else {
		hdr = off;
	}

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

	/* Create header for allocated block. */
	encode(off + len - hdr, false, (unsigned char *)pool + hdr, poolsize);

	return (unsigned char *)pool + 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 char *hdr;

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

	hdr = to_hdr(freep);

	/* FIXME: Put in free array. */
	hdr[0] |= FREE_BIT;
}

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;
}

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;
	bool free;

	if (poolsize < MIN_BLOCK_SIZE)
		return true;

	/* For the moment, free array is all zeroes. */
	for (off = 0; off < arrsize; off++) {
		if (arr[off] != 0)
			return tiny_check_fail();
	}

	for (off = arrsize; off < poolsize; off += len) {
		/* We should have a valid header. */
		if (!(arr[off] & TERM_BIT))
			return tiny_check_fail();
		if (!(arr[off] & SINGLE_BYTE)) {
			unsigned long off2;
			for (off2 = off+1; off2 < poolsize; off2++) {
				if (arr[off2] & TERM_BIT)
					break;
			}
			if (off2 == poolsize)
				return tiny_check_fail();
		}
		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();
	}
	return true;
}

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