Merge branch 'ronnie'
[ccan] / ccan / alloc / tiny.c
old mode 100755 (executable)
new mode 100644 (file)
index 678ca52..563c761
@@ -14,6 +14,8 @@
 /* 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)
 {
@@ -38,9 +40,8 @@ static unsigned encode_len_with_header(unsigned long len)
 }
 
 /* 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;
 
@@ -48,9 +49,6 @@ static unsigned encode(unsigned long len, bool free, unsigned char arr[],
        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) */
@@ -99,12 +97,30 @@ static unsigned decode(unsigned long *len, bool *free, const unsigned char *arr)
        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. */
@@ -115,8 +131,7 @@ void tiny_alloc_init(void *pool, unsigned long poolsize)
                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 */
@@ -129,16 +144,21 @@ static bool try_coalesce(unsigned char *pool, unsigned long poolsize)
        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;
 }
 
@@ -152,12 +172,36 @@ static bool long_enough(unsigned long offset, unsigned long len,
        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)
@@ -167,44 +211,71 @@ void *tiny_alloc_get(void *pool, unsigned long poolsize,
        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)
@@ -224,7 +295,10 @@ 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)
@@ -232,8 +306,12 @@ void tiny_alloc_free(void *pool, unsigned long poolsize, void *freep)
 
        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)
@@ -252,41 +330,97 @@ 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 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;
 }