7 /* One byte header, one byte data. */
8 #define MIN_BLOCK_SIZE 2
10 /* Bit 7 (in any byte) == start or end. */
12 /* Bit 6 (first and last byte) == one byte long. */
13 #define SINGLE_BYTE 0x40
14 /* Bit 5 (of first byte) == "is this block free?" */
17 #define MAX_FREE_CACHED_SIZE 256
19 /* Val is usually offset by MIN_BLOCK_SIZE here. */
20 static unsigned encode_length(unsigned long val)
22 unsigned int bits = fls(val);
23 /* 5 bits in first byte. */
26 /* 6 bits in last byte, 7 bits in middle ones. */
27 return 2 + (bits - 5) / 7;
30 /* Header is included in length, so we might need an extra byte. */
31 static unsigned encode_len_with_header(unsigned long len)
33 unsigned int hdrlen = 1;
36 while (encode_length(len + hdrlen - MIN_BLOCK_SIZE) != hdrlen)
37 hdrlen = encode_length(len + hdrlen - MIN_BLOCK_SIZE);
42 /* Encoding can be read from front or back; 0 is invalid at either
43 * start or end. Returns bytes used for header. */
44 static unsigned encode(unsigned long len, bool free, unsigned char arr[])
46 unsigned int hdrlen = 1;
48 /* We can never have a length < MIN_BLOCK_SIZE. */
49 assert(len >= MIN_BLOCK_SIZE);
50 len -= MIN_BLOCK_SIZE;
52 /* First byte always contains free bit. */
53 arr[0] = TERM_BIT | (free ? FREE_BIT : 0);
54 /* Also holds 5 bits of data (0 - 31) */
55 arr[0] |= (len & 0x1F);
60 arr[0] |= SINGLE_BYTE;
65 while (len >= (1 << 6)) {
66 /* Next 7 data bits */
67 arr[hdrlen++] = (len & 0x7F);
70 arr[hdrlen++] = (len | TERM_BIT);
74 /* Returns bytes used for header. */
75 static unsigned decode(unsigned long *len, bool *free, const unsigned char *arr)
77 unsigned int hdrlen = 0, bits = 5;
79 /* Free flag is in bit 5 */
80 *free = (arr[hdrlen] & FREE_BIT);
81 /* Bottom five bits are data. */
82 *len = (arr[hdrlen] & 0x1f);
83 if (!(arr[hdrlen++] & SINGLE_BYTE)) {
84 /* Multi-byte encoding? */
85 while (!(arr[hdrlen] & TERM_BIT)) {
86 /* 7 more data bits. */
87 *len |= (arr[hdrlen] & 0x7fUL) << bits;
91 /* Final byte has 6 bits. */
92 *len |= (arr[hdrlen] & 0x3fUL) << bits;
96 *len += MIN_BLOCK_SIZE;
100 /* We keep a helper array for freed mem, one byte per k. */
101 static unsigned long free_array_size(unsigned long poolsize)
103 return poolsize / 1024;
106 /* We have series of 69 free sizes like so:
107 * 1, 2, 3, 4. 6, 8, 10, 12, 14, 16. 20, 24, 28, 32... 252.
109 static unsigned long free_array_off(unsigned long size)
124 void tiny_alloc_init(void *pool, unsigned long poolsize)
126 /* We start with free array, and then the rest is free. */
127 unsigned long arrsize = free_array_size(poolsize);
129 /* Do nothing with 1 byte or less! */
130 if (poolsize < MIN_BLOCK_SIZE)
133 memset(pool, 0, arrsize);
134 encode(poolsize - arrsize, true, (unsigned char *)pool + arrsize);
137 /* Walk through and try to coalesce */
138 static bool try_coalesce(unsigned char *pool, unsigned long poolsize)
140 unsigned long len, hdrlen, prev_off = 0, prev_len = 0, off;
141 bool free, prev_free = false, coalesced = false;
143 off = free_array_size(poolsize);
145 hdrlen = decode(&len, &free, pool + off);
146 if (free && prev_free) {
148 encode(prev_len, true, pool + prev_off);
156 } while (off < poolsize);
158 /* Clear the free array. */
160 memset(pool, 0, free_array_size(poolsize));
165 static bool long_enough(unsigned long offset, unsigned long len,
166 unsigned long size, unsigned long align)
168 unsigned long end = offset + len;
170 offset += encode_len_with_header(len);
171 offset = align_up(offset, align);
172 return offset + size <= end;
175 static void add_to_free_array(unsigned char *arr,
176 unsigned long poolsize,
180 unsigned long fa_off;
182 if (size >= MAX_FREE_CACHED_SIZE)
185 for (fa_off = free_array_off(size);
186 fa_off + 3 < free_array_size(poolsize);
187 fa_off += free_array_off(MAX_FREE_CACHED_SIZE)) {
188 if (!arr[fa_off] && !arr[fa_off+1] && !arr[fa_off+2]) {
189 arr[fa_off] = (off >> 16);
190 arr[fa_off+1] = (off >> 8);
197 void *tiny_alloc_get(void *pool, unsigned long poolsize,
198 unsigned long size, unsigned long align)
200 unsigned long arrsize = free_array_size(poolsize);
201 unsigned long len, off, actual, hdr, hdrlen, free_bucket;
203 unsigned char *arr = pool;
204 bool free, coalesced = false;
206 /* We can't do anything with tiny pools. */
207 if (poolsize < MIN_BLOCK_SIZE)
210 /* We don't do zero-allocs; allows 1 more offset in encoding. */
214 /* Look for entries in free array, starting from right size up. */
215 for (free_bucket = free_array_off(size);
216 free_bucket < free_array_off(MAX_FREE_CACHED_SIZE);
218 for (fa_off = free_bucket;
219 fa_off + 3 < free_array_size(poolsize);
220 fa_off += free_array_off(MAX_FREE_CACHED_SIZE)) {
221 off = ((unsigned long)arr[fa_off]) << 16
222 | ((unsigned long)arr[fa_off+1]) << 8
223 | ((unsigned long)arr[fa_off+2]);
227 hdrlen = decode(&len, &free, arr + off);
228 if (long_enough(off, len, size, align)) {
230 memset(&arr[fa_off], 0, 3);
239 hdrlen = decode(&len, &free, arr + off);
240 while (!free || !long_enough(off, len, size, align)) {
241 /* Refill free array as we go. */
242 if (free && coalesced)
243 add_to_free_array(arr, poolsize, len, off);
247 if (off == poolsize) {
248 if (!coalesced && try_coalesce(pool, poolsize)) {
254 hdrlen = decode(&len, &free, arr + off);
258 /* We have a free block. Since we walk from front, take far end. */
259 actual = ((off + len - size) & ~(align - 1));
260 hdr = actual - encode_len_with_header(off + len - actual);
263 /* Do we have enough room to split? */
264 if (hdr - off >= MIN_BLOCK_SIZE) {
265 encode(hdr - off, true, arr + off);
266 add_to_free_array(arr, poolsize, hdr - off, off);
271 /* Make sure that we are all-zero up to actual, so we can walk back
272 * and find header. */
273 memset(arr + hdr, 0, actual - hdr);
275 /* Create header for allocated block. */
276 encode(off + len - hdr, false, arr + hdr);
281 static unsigned char *to_hdr(void *p)
283 unsigned char *hdr = p;
285 /* Walk back to find end of header. */
287 assert(*hdr & TERM_BIT);
289 /* Now walk back to find start of header. */
290 if (!(*hdr & SINGLE_BYTE)) {
291 while (!(*(--hdr) & TERM_BIT));
296 void tiny_alloc_free(void *pool, unsigned long poolsize, void *freep)
299 unsigned char *arr = pool;
303 /* Too small to do anything. */
304 if (poolsize < MIN_BLOCK_SIZE)
309 decode(&len, &free, hdr);
313 /* If an empty slot, put this in free array. */
314 add_to_free_array(pool, poolsize, len, hdr - arr);
317 unsigned long tiny_alloc_size(void *pool, unsigned long poolsize, void *p)
319 unsigned char *hdr = to_hdr(p);
320 unsigned long len, hdrlen;
323 hdrlen = decode(&len, &free, hdr);
327 /* Useful for gdb breakpoints. */
328 static bool tiny_check_fail(void)
333 static bool check_decode(const unsigned char *arr, unsigned long len)
338 return tiny_check_fail();
339 if (!(arr[0] & TERM_BIT))
340 return tiny_check_fail();
341 if (arr[0] & SINGLE_BYTE)
343 for (i = 1; i < len; i++) {
344 if (arr[i] & TERM_BIT)
347 return tiny_check_fail();
350 bool tiny_alloc_check(void *pool, unsigned long poolsize)
352 unsigned long arrsize = free_array_size(poolsize);
353 unsigned char *arr = pool;
354 unsigned long len, off, hdrlen;
355 unsigned long i, freearr[arrsize], num_freearr = 0;
358 if (poolsize < MIN_BLOCK_SIZE)
361 for (i = 0; i + 3 < free_array_size(poolsize); i += 3) {
362 off = ((unsigned long)arr[i]) << 16
363 | ((unsigned long)arr[i+1]) << 8
364 | ((unsigned long)arr[i+2]);
369 return tiny_check_fail();
370 freearr[num_freearr++] = off;
373 for (off = arrsize; off < poolsize; off += len) {
374 /* We should have a valid header. */
375 if (!check_decode(arr + off, poolsize - off))
377 hdrlen = decode(&len, &free, arr + off);
378 if (off + len > poolsize)
379 return tiny_check_fail();
380 if (hdrlen != encode_length(len - MIN_BLOCK_SIZE))
381 return tiny_check_fail();
382 for (i = 0; i < num_freearr; i++) {
383 if (freearr[i] == off) {
385 return tiny_check_fail();
386 memmove(&freearr[i], &freearr[i+1],
387 (num_freearr-- - (i + 1))
388 * sizeof(freearr[i]));
394 /* Now we should have found everything in freearr. */
396 return tiny_check_fail();
398 /* Now check that sizes are correct. */
399 for (i = 0; i + 3 < free_array_size(poolsize); i += 3) {
400 unsigned long fa_off;
402 off = ((unsigned long)arr[i]) << 16
403 | ((unsigned long)arr[i+1]) << 8
404 | ((unsigned long)arr[i+2]);
408 decode(&len, &free, arr + off);
410 /* Would we expect to find this length in this bucket? */
411 if (len >= MAX_FREE_CACHED_SIZE)
412 return tiny_check_fail();
414 for (fa_off = free_array_off(len);
415 fa_off + 3 < free_array_size(poolsize);
416 fa_off += free_array_off(MAX_FREE_CACHED_SIZE)) {
421 return tiny_check_fail();
427 /* FIXME: Implement. */
428 void tiny_alloc_visualize(FILE *out, void *pool, unsigned long poolsize)