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, or 0 if won't fit. */
42 static unsigned encode(unsigned long len, bool free, unsigned char arr[],
45 unsigned int hdrlen = 1;
47 /* We can never have a length < MIN_BLOCK_SIZE. */
48 assert(len >= MIN_BLOCK_SIZE);
49 len -= MIN_BLOCK_SIZE;
51 if (encode_length(len) > limit)
54 /* First byte always contains free bit. */
55 arr[0] = TERM_BIT | (free ? FREE_BIT : 0);
56 /* Also holds 5 bits of data (0 - 31) */
57 arr[0] |= (len & 0x1F);
62 arr[0] |= SINGLE_BYTE;
67 while (len >= (1 << 6)) {
68 /* Next 7 data bits */
69 arr[hdrlen++] = (len & 0x7F);
72 arr[hdrlen++] = (len | TERM_BIT);
76 /* Returns bytes used for header. */
77 static unsigned decode(unsigned long *len, bool *free, const unsigned char *arr)
79 unsigned int hdrlen = 0, bits = 5;
81 /* Free flag is in bit 5 */
82 *free = (arr[hdrlen] & FREE_BIT);
83 /* Bottom five bits are data. */
84 *len = (arr[hdrlen] & 0x1f);
85 if (!(arr[hdrlen++] & SINGLE_BYTE)) {
86 /* Multi-byte encoding? */
87 while (!(arr[hdrlen] & TERM_BIT)) {
88 /* 7 more data bits. */
89 *len |= (arr[hdrlen] & 0x7fUL) << bits;
93 /* Final byte has 6 bits. */
94 *len |= (arr[hdrlen] & 0x3fUL) << bits;
98 *len += MIN_BLOCK_SIZE;
102 /* We keep a recently-freed array, one byte per k. */
103 static unsigned long free_array_size(unsigned long poolsize)
105 return poolsize / 1024;
108 void tiny_alloc_init(void *pool, unsigned long poolsize)
110 /* We start with free array, and then the rest is free. */
111 unsigned long arrsize = free_array_size(poolsize);
113 /* Do nothing with 1 byte or less! */
114 if (poolsize < MIN_BLOCK_SIZE)
117 memset(pool, 0, arrsize);
118 encode(poolsize - arrsize, true,
119 (unsigned char *)pool + arrsize, poolsize - arrsize);
122 /* Walk through and try to coalesce */
123 static bool try_coalesce(unsigned char *pool, unsigned long poolsize)
125 unsigned long len, hdrlen, prev_off = 0, prev_len = 0, off;
126 bool free, prev_free = false, coalesced = false;
128 off = free_array_size(poolsize);
130 hdrlen = decode(&len, &free, pool + off);
131 if (free && prev_free) {
132 encode(prev_len + len, true, pool + prev_off,
133 poolsize - prev_off);
140 } while (off < poolsize);
145 static bool long_enough(unsigned long offset, unsigned long len,
146 unsigned long size, unsigned long align)
148 unsigned long end = offset + len;
150 offset += encode_len_with_header(len);
151 offset = align_up(offset, align);
152 return offset + size <= end;
155 void *tiny_alloc_get(void *pool, unsigned long poolsize,
156 unsigned long size, unsigned long align)
158 unsigned long arrsize = free_array_size(poolsize);
159 unsigned long len, off, actual, hdr, hdrlen;
162 /* We can't do anything with tiny pools. */
163 if (poolsize < MIN_BLOCK_SIZE)
166 /* We don't do zero-allocs; allows 1 more offset in encoding. */
170 /* FIXME: Look through free array. */
175 hdrlen = decode(&len, &free, (unsigned char *)pool + off);
176 while (!free || !long_enough(off, len, size, align)) {
177 /* FIXME: Refill free array if this block is free. */
181 if (off == poolsize) {
182 if (try_coalesce(pool, poolsize))
186 hdrlen = decode(&len, &free, (unsigned char *)pool + off);
189 /* We have a free block. Since we walk from front, take far end. */
190 actual = ((off + len - size) & ~(align - 1));
191 hdr = actual - encode_len_with_header(off + len - actual);
193 /* Do we have enough room to split? */
194 if (hdr - off >= MIN_BLOCK_SIZE) {
195 encode(hdr - off, true, (unsigned char *)pool + off, poolsize);
200 /* Make sure that we are all-zero up to actual, so we can walk back
201 * and find header. */
202 memset((unsigned char *)pool + hdr, 0, actual - hdr);
204 /* Create header for allocated block. */
205 encode(off + len - hdr, false, (unsigned char *)pool + hdr, poolsize);
207 return (unsigned char *)pool + actual;
210 static unsigned char *to_hdr(void *p)
212 unsigned char *hdr = p;
214 /* Walk back to find end of header. */
216 assert(*hdr & TERM_BIT);
218 /* Now walk back to find start of header. */
219 if (!(*hdr & SINGLE_BYTE)) {
220 while (!(*(--hdr) & TERM_BIT));
225 void tiny_alloc_free(void *pool, unsigned long poolsize, void *freep)
229 /* Too small to do anything. */
230 if (poolsize < MIN_BLOCK_SIZE)
235 /* FIXME: Put in free array. */
239 unsigned long tiny_alloc_size(void *pool, unsigned long poolsize, void *p)
241 unsigned char *hdr = to_hdr(p);
242 unsigned long len, hdrlen;
245 hdrlen = decode(&len, &free, hdr);
249 /* Useful for gdb breakpoints. */
250 static bool tiny_check_fail(void)
255 bool tiny_alloc_check(void *pool, unsigned long poolsize)
257 unsigned long arrsize = free_array_size(poolsize);
258 unsigned char *arr = pool;
259 unsigned long len, off, hdrlen;
262 if (poolsize < MIN_BLOCK_SIZE)
265 /* For the moment, free array is all zeroes. */
266 for (off = 0; off < arrsize; off++) {
268 return tiny_check_fail();
271 for (off = arrsize; off < poolsize; off += len) {
272 /* We should have a valid header. */
273 if (!(arr[off] & TERM_BIT))
274 return tiny_check_fail();
275 if (!(arr[off] & SINGLE_BYTE)) {
277 for (off2 = off+1; off2 < poolsize; off2++) {
278 if (arr[off2] & TERM_BIT)
281 if (off2 == poolsize)
282 return tiny_check_fail();
284 hdrlen = decode(&len, &free, arr + off);
285 if (off + len > poolsize)
286 return tiny_check_fail();
287 if (hdrlen != encode_length(len - MIN_BLOCK_SIZE))
288 return tiny_check_fail();
293 /* FIXME: Implement. */
294 void tiny_alloc_visualize(FILE *out, void *pool, unsigned long poolsize)