1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
8 /* One byte header, one byte data. */
9 #define MIN_BLOCK_SIZE 2
11 /* Bit 7 (in any byte) == start or end. */
13 /* Bit 6 (first and last byte) == one byte long. */
14 #define SINGLE_BYTE 0x40
15 /* Bit 5 (of first byte) == "is this block free?" */
18 #define MAX_FREE_CACHED_SIZE 256
20 /* Val is usually offset by MIN_BLOCK_SIZE here. */
21 static unsigned encode_length(unsigned long val)
23 unsigned int bits = afls(val);
24 /* 5 bits in first byte. */
27 /* 6 bits in last byte, 7 bits in middle ones. */
28 return 2 + (bits - 5) / 7;
31 /* Header is included in length, so we might need an extra byte. */
32 static unsigned encode_len_with_header(unsigned long len)
34 unsigned int hdrlen = 1;
37 while (encode_length(len + hdrlen - MIN_BLOCK_SIZE) != hdrlen)
38 hdrlen = encode_length(len + hdrlen - MIN_BLOCK_SIZE);
43 /* Encoding can be read from front or back; 0 is invalid at either
44 * start or end. Returns bytes used for header. */
45 static unsigned encode(unsigned long len, bool free, unsigned char arr[])
47 unsigned int hdrlen = 1;
49 /* We can never have a length < MIN_BLOCK_SIZE. */
50 assert(len >= MIN_BLOCK_SIZE);
51 len -= MIN_BLOCK_SIZE;
53 /* First byte always contains free bit. */
54 arr[0] = TERM_BIT | (free ? FREE_BIT : 0);
55 /* Also holds 5 bits of data (0 - 31) */
56 arr[0] |= (len & 0x1F);
61 arr[0] |= SINGLE_BYTE;
66 while (len >= (1 << 6)) {
67 /* Next 7 data bits */
68 arr[hdrlen++] = (len & 0x7F);
71 arr[hdrlen++] = (len | TERM_BIT);
75 /* Returns bytes used for header. */
76 static unsigned decode(unsigned long *len, bool *free, const unsigned char *arr)
78 unsigned int hdrlen = 0, bits = 5;
80 /* Free flag is in bit 5 */
81 *free = (arr[hdrlen] & FREE_BIT);
82 /* Bottom five bits are data. */
83 *len = (arr[hdrlen] & 0x1f);
84 if (!(arr[hdrlen++] & SINGLE_BYTE)) {
85 /* Multi-byte encoding? */
86 while (!(arr[hdrlen] & TERM_BIT)) {
87 /* 7 more data bits. */
88 *len |= (arr[hdrlen] & 0x7fUL) << bits;
92 /* Final byte has 6 bits. */
93 *len |= (arr[hdrlen] & 0x3fUL) << bits;
97 *len += MIN_BLOCK_SIZE;
101 /* We keep a helper array for freed mem, one byte per k. */
102 static unsigned long free_array_size(unsigned long poolsize)
104 return poolsize / 1024;
107 /* We have series of 69 free sizes like so:
108 * 1, 2, 3, 4. 6, 8, 10, 12, 14, 16. 20, 24, 28, 32... 252.
110 static unsigned long free_array_off(unsigned long size)
125 void tiny_alloc_init(void *pool, unsigned long poolsize)
127 /* We start with free array, and then the rest is free. */
128 unsigned long arrsize = free_array_size(poolsize);
130 /* Do nothing with 1 byte or less! */
131 if (poolsize < MIN_BLOCK_SIZE)
134 memset(pool, 0, arrsize);
135 encode(poolsize - arrsize, true, (unsigned char *)pool + arrsize);
138 /* Walk through and try to coalesce */
139 static bool try_coalesce(unsigned char *pool, unsigned long poolsize)
141 unsigned long len, prev_off = 0, prev_len = 0, off;
142 bool free, prev_free = false, coalesced = false;
144 off = free_array_size(poolsize);
146 decode(&len, &free, pool + off);
147 if (free && prev_free) {
149 encode(prev_len, true, pool + prev_off);
157 } while (off < poolsize);
159 /* Clear the free array. */
161 memset(pool, 0, free_array_size(poolsize));
166 static bool long_enough(unsigned long offset, unsigned long len,
167 unsigned long size, unsigned long align)
169 unsigned long end = offset + len;
171 offset += encode_len_with_header(len);
172 offset = align_up(offset, align);
173 return offset + size <= end;
176 static void add_to_free_array(unsigned char *arr,
177 unsigned long poolsize,
181 unsigned long fa_off;
183 if (size >= MAX_FREE_CACHED_SIZE)
186 for (fa_off = free_array_off(size);
187 fa_off + 3 < free_array_size(poolsize);
188 fa_off += free_array_off(MAX_FREE_CACHED_SIZE)) {
189 if (!arr[fa_off] && !arr[fa_off+1] && !arr[fa_off+2]) {
190 arr[fa_off] = (off >> 16);
191 arr[fa_off+1] = (off >> 8);
198 void *tiny_alloc_get(void *pool, unsigned long poolsize,
199 unsigned long size, unsigned long align)
201 unsigned long arrsize = free_array_size(poolsize);
202 unsigned long len, off, actual, hdr, free_bucket;
204 unsigned char *arr = pool;
205 bool free, coalesced = false;
207 /* We can't do anything with tiny pools. */
208 if (poolsize < MIN_BLOCK_SIZE)
211 /* We don't do zero-allocs; allows 1 more offset in encoding. */
215 /* Look for entries in free array, starting from right size up. */
216 for (free_bucket = free_array_off(size);
217 free_bucket < free_array_off(MAX_FREE_CACHED_SIZE);
219 for (fa_off = free_bucket;
220 fa_off + 3 < free_array_size(poolsize);
221 fa_off += free_array_off(MAX_FREE_CACHED_SIZE)) {
222 off = ((unsigned long)arr[fa_off]) << 16
223 | ((unsigned long)arr[fa_off+1]) << 8
224 | ((unsigned long)arr[fa_off+2]);
228 decode(&len, &free, arr + off);
229 if (long_enough(off, len, size, align)) {
231 memset(&arr[fa_off], 0, 3);
240 decode(&len, &free, arr + off);
241 while (!free || !long_enough(off, len, size, align)) {
242 /* Refill free array as we go. */
243 if (free && coalesced)
244 add_to_free_array(arr, poolsize, len, off);
248 if (off == poolsize) {
249 if (!coalesced && try_coalesce(pool, poolsize)) {
255 decode(&len, &free, arr + off);
259 /* We have a free block. Since we walk from front, take far end. */
260 actual = ((off + len - size) & ~(align - 1));
261 hdr = actual - encode_len_with_header(off + len - actual);
264 /* Do we have enough room to split? */
265 if (hdr - off >= MIN_BLOCK_SIZE) {
266 encode(hdr - off, true, arr + off);
267 add_to_free_array(arr, poolsize, hdr - off, off);
272 /* Make sure that we are all-zero up to actual, so we can walk back
273 * and find header. */
274 memset(arr + hdr, 0, actual - hdr);
276 /* Create header for allocated block. */
277 encode(off + len - hdr, false, arr + hdr);
282 static unsigned char *to_hdr(void *p)
284 unsigned char *hdr = p;
286 /* Walk back to find end of header. */
288 assert(*hdr & TERM_BIT);
290 /* Now walk back to find start of header. */
291 if (!(*hdr & SINGLE_BYTE)) {
292 while (!(*(--hdr) & TERM_BIT));
297 void tiny_alloc_free(void *pool, unsigned long poolsize, void *freep)
300 unsigned char *arr = pool;
304 /* Too small to do anything. */
305 if (poolsize < MIN_BLOCK_SIZE)
310 decode(&len, &free, hdr);
314 /* If an empty slot, put this in free array. */
315 add_to_free_array(pool, poolsize, len, hdr - arr);
318 unsigned long tiny_alloc_size(void *pool, unsigned long poolsize, void *p)
320 unsigned char *hdr = to_hdr(p);
321 unsigned long len, hdrlen;
324 hdrlen = decode(&len, &free, hdr);
328 /* Useful for gdb breakpoints. */
329 static bool tiny_check_fail(void)
334 static bool check_decode(const unsigned char *arr, unsigned long len)
339 return tiny_check_fail();
340 if (!(arr[0] & TERM_BIT))
341 return tiny_check_fail();
342 if (arr[0] & SINGLE_BYTE)
344 for (i = 1; i < len; i++) {
345 if (arr[i] & TERM_BIT)
348 return tiny_check_fail();
351 bool tiny_alloc_check(void *pool, unsigned long poolsize)
353 unsigned long arrsize = free_array_size(poolsize);
354 unsigned char *arr = pool;
355 unsigned long len, off, hdrlen;
356 unsigned long i, freearr[arrsize], num_freearr = 0;
359 if (poolsize < MIN_BLOCK_SIZE)
362 for (i = 0; i + 3 < free_array_size(poolsize); i += 3) {
363 off = ((unsigned long)arr[i]) << 16
364 | ((unsigned long)arr[i+1]) << 8
365 | ((unsigned long)arr[i+2]);
370 return tiny_check_fail();
371 freearr[num_freearr++] = off;
374 for (off = arrsize; off < poolsize; off += len) {
375 /* We should have a valid header. */
376 if (!check_decode(arr + off, poolsize - off))
378 hdrlen = decode(&len, &free, arr + off);
379 if (off + len > poolsize)
380 return tiny_check_fail();
381 if (hdrlen != encode_length(len - MIN_BLOCK_SIZE))
382 return tiny_check_fail();
383 for (i = 0; i < num_freearr; i++) {
384 if (freearr[i] == off) {
386 return tiny_check_fail();
387 memmove(&freearr[i], &freearr[i+1],
388 (num_freearr-- - (i + 1))
389 * sizeof(freearr[i]));
395 /* Now we should have found everything in freearr. */
397 return tiny_check_fail();
399 /* Now check that sizes are correct. */
400 for (i = 0; i + 3 < free_array_size(poolsize); i += 3) {
401 unsigned long fa_off;
403 off = ((unsigned long)arr[i]) << 16
404 | ((unsigned long)arr[i+1]) << 8
405 | ((unsigned long)arr[i+2]);
409 decode(&len, &free, arr + off);
411 /* Would we expect to find this length in this bucket? */
412 if (len >= MAX_FREE_CACHED_SIZE)
413 return tiny_check_fail();
415 for (fa_off = free_array_off(len);
416 fa_off + 3 < free_array_size(poolsize);
417 fa_off += free_array_off(MAX_FREE_CACHED_SIZE)) {
422 return tiny_check_fail();
428 /* FIXME: Implement. */
429 void tiny_alloc_visualize(FILE *out, void *pool, unsigned long poolsize)