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 /* Val is usually offset by MIN_BLOCK_SIZE here. */
18 static unsigned encode_length(unsigned long val)
20 unsigned int bits = fls(val);
21 /* 5 bits in first byte. */
24 /* 6 bits in last byte, 7 bits in middle ones. */
25 return 2 + (bits - 5) / 7;
28 /* Header is included in length, so we might need an extra byte. */
29 static unsigned encode_len_with_header(unsigned long len)
31 unsigned int hdrlen = 1;
34 while (encode_length(len + hdrlen - MIN_BLOCK_SIZE) != hdrlen)
35 hdrlen = encode_length(len + hdrlen - MIN_BLOCK_SIZE);
40 /* Encoding can be read from front or back; 0 is invalid at either
41 * start or end. Returns bytes used for header. */
42 static unsigned encode(unsigned long len, bool free, unsigned char arr[])
44 unsigned int hdrlen = 1;
46 /* We can never have a length < MIN_BLOCK_SIZE. */
47 assert(len >= MIN_BLOCK_SIZE);
48 len -= MIN_BLOCK_SIZE;
50 /* First byte always contains free bit. */
51 arr[0] = TERM_BIT | (free ? FREE_BIT : 0);
52 /* Also holds 5 bits of data (0 - 31) */
53 arr[0] |= (len & 0x1F);
58 arr[0] |= SINGLE_BYTE;
63 while (len >= (1 << 6)) {
64 /* Next 7 data bits */
65 arr[hdrlen++] = (len & 0x7F);
68 arr[hdrlen++] = (len | TERM_BIT);
72 /* Returns bytes used for header. */
73 static unsigned decode(unsigned long *len, bool *free, const unsigned char *arr)
75 unsigned int hdrlen = 0, bits = 5;
77 /* Free flag is in bit 5 */
78 *free = (arr[hdrlen] & FREE_BIT);
79 /* Bottom five bits are data. */
80 *len = (arr[hdrlen] & 0x1f);
81 if (!(arr[hdrlen++] & SINGLE_BYTE)) {
82 /* Multi-byte encoding? */
83 while (!(arr[hdrlen] & TERM_BIT)) {
84 /* 7 more data bits. */
85 *len |= (arr[hdrlen] & 0x7fUL) << bits;
89 /* Final byte has 6 bits. */
90 *len |= (arr[hdrlen] & 0x3fUL) << bits;
94 *len += MIN_BLOCK_SIZE;
98 /* We keep a recently-freed array, one byte per k. */
99 static unsigned long free_array_size(unsigned long poolsize)
101 return poolsize / 1024;
104 void tiny_alloc_init(void *pool, unsigned long poolsize)
106 /* We start with free array, and then the rest is free. */
107 unsigned long arrsize = free_array_size(poolsize);
109 /* Do nothing with 1 byte or less! */
110 if (poolsize < MIN_BLOCK_SIZE)
113 memset(pool, 0, arrsize);
114 encode(poolsize - arrsize, true, (unsigned char *)pool + arrsize);
117 /* Walk through and try to coalesce */
118 static bool try_coalesce(unsigned char *pool, unsigned long poolsize)
120 unsigned long len, hdrlen, prev_off = 0, prev_len = 0, off;
121 bool free, prev_free = false, coalesced = false;
123 off = free_array_size(poolsize);
125 hdrlen = decode(&len, &free, pool + off);
126 if (free && prev_free) {
127 encode(prev_len + len, true, pool + prev_off);
134 } while (off < poolsize);
136 /* FIXME: Refill free_array here. */
138 memset(pool, 0, free_array_size(poolsize));
143 static bool long_enough(unsigned long offset, unsigned long len,
144 unsigned long size, unsigned long align)
146 unsigned long end = offset + len;
148 offset += encode_len_with_header(len);
149 offset = align_up(offset, align);
150 return offset + size <= end;
153 static unsigned long find_free_end(unsigned char *arr, unsigned long arrsize)
157 for (i = arrsize-1; i >= 0; i--) {
164 void *tiny_alloc_get(void *pool, unsigned long poolsize,
165 unsigned long size, unsigned long align)
167 unsigned long arrsize = free_array_size(poolsize);
168 unsigned long len, off, fa_off, fa_hdrlen, actual, hdr, hdrlen, freelen;
169 unsigned char *arr = pool;
172 /* We can't do anything with tiny pools. */
173 if (poolsize < MIN_BLOCK_SIZE)
176 /* We don't do zero-allocs; allows 1 more offset in encoding. */
180 /* Look for entries in free array. */
181 freelen = find_free_end(pool, arrsize);
182 for (fa_off = 0; fa_off < freelen; fa_off += fa_hdrlen) {
183 fa_hdrlen = decode(&off, &free, arr + fa_off);
184 off -= MIN_BLOCK_SIZE;
185 hdrlen = decode(&len, &free, arr + off);
186 if (long_enough(off, len, size, align)) {
187 /* Move every successive entry down. */
188 memmove(arr + fa_off, arr + fa_off + fa_hdrlen,
189 freelen - (fa_off + fa_hdrlen));
190 memset(arr + freelen - fa_hdrlen, 0, fa_hdrlen);
198 hdrlen = decode(&len, &free, arr + off);
199 while (!free || !long_enough(off, len, size, align)) {
200 /* FIXME: Refill free array if this block is free. */
204 if (off == poolsize) {
205 if (try_coalesce(pool, poolsize))
209 hdrlen = decode(&len, &free, arr + off);
213 /* We have a free block. Since we walk from front, take far end. */
214 actual = ((off + len - size) & ~(align - 1));
215 hdr = actual - encode_len_with_header(off + len - actual);
217 /* Do we have enough room to split? */
218 if (hdr - off >= MIN_BLOCK_SIZE) {
219 encode(hdr - off, true, arr + off);
224 /* Make sure that we are all-zero up to actual, so we can walk back
225 * and find header. */
226 memset(arr + hdr, 0, actual - hdr);
228 /* Create header for allocated block. */
229 encode(off + len - hdr, false, arr + hdr);
234 static unsigned char *to_hdr(void *p)
236 unsigned char *hdr = p;
238 /* Walk back to find end of header. */
240 assert(*hdr & TERM_BIT);
242 /* Now walk back to find start of header. */
243 if (!(*hdr & SINGLE_BYTE)) {
244 while (!(*(--hdr) & TERM_BIT));
249 void tiny_alloc_free(void *pool, unsigned long poolsize, void *freep)
251 unsigned long len, end, arrsize = free_array_size(poolsize);
252 unsigned char *arr = pool;
255 /* Too small to do anything. */
256 if (poolsize < MIN_BLOCK_SIZE)
262 end = find_free_end(pool, arrsize);
264 /* If we can fit this block, encode it. */
265 len = encode_length(hdr - arr);
266 if (end + len <= arrsize)
267 encode(hdr - arr + MIN_BLOCK_SIZE, true, arr + end);
270 unsigned long tiny_alloc_size(void *pool, unsigned long poolsize, void *p)
272 unsigned char *hdr = to_hdr(p);
273 unsigned long len, hdrlen;
276 hdrlen = decode(&len, &free, hdr);
280 /* Useful for gdb breakpoints. */
281 static bool tiny_check_fail(void)
286 static bool check_decode(const unsigned char *arr, unsigned long len)
291 return tiny_check_fail();
292 if (!(arr[0] & TERM_BIT))
293 return tiny_check_fail();
294 if (arr[0] & SINGLE_BYTE)
296 for (i = 1; i < len; i++) {
297 if (arr[i] & TERM_BIT)
300 return tiny_check_fail();
303 bool tiny_alloc_check(void *pool, unsigned long poolsize)
305 unsigned long arrsize = free_array_size(poolsize);
306 unsigned char *arr = pool;
307 unsigned long len, off, off2, hdrlen, end;
308 unsigned long i, freearr[arrsize], num_freearr = 0;
311 if (poolsize < MIN_BLOCK_SIZE)
314 end = find_free_end(pool, arrsize);
315 for (off = 0; off < end; off += hdrlen) {
316 if (!check_decode(arr + off, end - off))
318 hdrlen = decode(&off2, &free, arr + off);
319 off2 -= MIN_BLOCK_SIZE;
320 if (off2 >= poolsize)
321 return tiny_check_fail();
323 return tiny_check_fail();
324 freearr[num_freearr++] = off2;
326 /* Rest of free array should be all zeroes. */
327 for (off = end; off < arrsize; off++) {
329 return tiny_check_fail();
332 for (off = arrsize; off < poolsize; off += len) {
333 /* We should have a valid header. */
334 if (!check_decode(arr + off, poolsize - off))
336 hdrlen = decode(&len, &free, arr + off);
337 if (off + len > poolsize)
338 return tiny_check_fail();
339 if (hdrlen != encode_length(len - MIN_BLOCK_SIZE))
340 return tiny_check_fail();
341 for (i = 0; i < num_freearr; i++) {
342 if (freearr[i] == off) {
344 return tiny_check_fail();
345 memmove(&freearr[i], &freearr[i+1],
346 (num_freearr-- - (i + 1))
347 * sizeof(freearr[i]));
353 /* Now we should have found everything in freearr. */
355 return tiny_check_fail();
360 /* FIXME: Implement. */
361 void tiny_alloc_visualize(FILE *out, void *pool, unsigned long poolsize)