X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Falloc%2Ftiny.c;h=ffd17c65734f881f1ca355ed9e1a5b705dd3ff46;hp=678ca52d16d021ae4ce74d9ff826e77f81b2b331;hb=f725bbb1987284933e0f21dfb8f2ce7a1f0806e5;hpb=7f9d956574d30f70d2260f4b7694f481e3765173

diff --git a/ccan/alloc/tiny.c b/ccan/alloc/tiny.c
old mode 100755
new mode 100644
index 678ca52d..ffd17c65
--- a/ccan/alloc/tiny.c
+++ b/ccan/alloc/tiny.c
@@ -1,3 +1,4 @@
+/* Licensed under LGPLv2.1+ - see LICENSE file for details */
 #include "tiny.h"
 #include "bitops.h"
 #include <assert.h>
@@ -14,10 +15,12 @@
 /* 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 = fls(val);
+	unsigned int bits = afls(val);
 	/* 5 bits in first byte. */
 	if (bits <= 5)
 		return 1;
@@ -38,9 +41,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 +50,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 +98,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,30 +132,34 @@ 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 */
 static bool try_coalesce(unsigned char *pool, unsigned long poolsize)
 {
-	unsigned long len, hdrlen, prev_off = 0, prev_len = 0, off;
+	unsigned long len, 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);
+		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 +173,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, 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 +212,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;
+
+			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);
+	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);
+		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 +296,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 +307,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 +331,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;
 }