+++ /dev/null
-/* 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)
-{
-}
projects / ccan / blobdiff