/* 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)
{
}
/* 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)
+ * start or end. Returns bytes used for header. */
+static unsigned encode(unsigned long len, bool free, unsigned char arr[])
{
unsigned int hdrlen = 1;
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) */
return hdrlen;
}
-/* We keep a recently-freed array, one byte per k. */
+/* 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. */
return;
memset(pool, 0, arrsize);
- encode(poolsize - arrsize, true,
- (unsigned char *)pool + arrsize, poolsize - arrsize);
+ encode(poolsize - arrsize, true, (unsigned char *)pool + arrsize);
}
/* Walk through and try to coalesce */
do {
hdrlen = decode(&len, &free, pool + off);
if (free && prev_free) {
- encode(prev_len + len, true, pool + prev_off,
- poolsize - prev_off);
+ prev_len += len;
+ encode(prev_len, true, pool + prev_off);
coalesced = true;
+ } else {
+ prev_free = free;
+ prev_off = off;
+ prev_len = len;
}
- 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;
}
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, hdrlen;
- bool free;
+ unsigned long len, off, actual, hdr, hdrlen, 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)
if (!size)
size = 1;
- /* FIXME: Look through free array. */
+ /* 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;
+
+ hdrlen = 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;
- hdrlen = decode(&len, &free, (unsigned char *)pool + off);
+ hdrlen = decode(&len, &free, arr + off);
while (!free || !long_enough(off, len, size, align)) {
- /* FIXME: Refill free array if this block is free. */
+ /* Refill free array as we go. */
+ if (free && coalesced)
+ add_to_free_array(arr, poolsize, len, off);
- /* Hit end? */
off += len;
+ /* Hit end? */
if (off == poolsize) {
- if (try_coalesce(pool, poolsize))
+ if (!coalesced && try_coalesce(pool, poolsize)) {
+ coalesced = true;
goto again;
+ }
return NULL;
}
- hdrlen = decode(&len, &free, (unsigned char *)pool + off);
+ hdrlen = 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, (unsigned char *)pool + off, poolsize);
+ 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((unsigned char *)pool + hdr, 0, actual - hdr);
+ memset(arr + hdr, 0, actual - hdr);
/* Create header for allocated block. */
- encode(off + len - hdr, false, (unsigned char *)pool + hdr, poolsize);
+ encode(off + len - hdr, false, arr + hdr);
- return (unsigned char *)pool + actual;
+ return arr + actual;
}
static unsigned char *to_hdr(void *p)
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)
hdr = to_hdr(freep);
- /* FIXME: Put in free array. */
+ 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)
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 the moment, free array is all zeroes. */
- for (off = 0; off < arrsize; off++) {
- if (arr[off] != 0)
+ 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 (!(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();
- }
+ 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;
}
projects / ccan / blobdiff