alloc: first cut of tiny allocator (down to 2 bytes!)
[ccan] / ccan / alloc / tiny.c
1 #include "tiny.h"
2 #include "bitops.h"
3 #include <assert.h>
4 #include <stdlib.h>
5 #include <string.h>
6
7 /* One byte header, one byte data. */
8 #define MIN_BLOCK_SIZE 2
9
10 /* Bit 7 (in any byte) == start or end. */
11 #define TERM_BIT 0x80
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?" */
15 #define FREE_BIT 0x20
16
17 /* Val is usually offset by MIN_BLOCK_SIZE here. */
18 static unsigned encode_length(unsigned long val)
19 {
20         unsigned int bits = fls(val);
21         /* 5 bits in first byte. */
22         if (bits <= 5)
23                 return 1;
24         /* 6 bits in last byte, 7 bits in middle ones. */
25         return 2 + (bits - 5) / 7;
26 }
27
28 /* Header is included in length, so we might need an extra byte. */
29 static unsigned encode_len_with_header(unsigned long len)
30 {
31         unsigned int hdrlen = 1;
32
33         assert(len);
34         while (encode_length(len + hdrlen - MIN_BLOCK_SIZE) != hdrlen)
35                 hdrlen = encode_length(len + hdrlen - MIN_BLOCK_SIZE);
36
37         return hdrlen;
38 }
39
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[],
43                        size_t limit)
44 {
45         unsigned int hdrlen = 1;
46
47         /* We can never have a length < MIN_BLOCK_SIZE. */
48         assert(len >= MIN_BLOCK_SIZE);
49         len -= MIN_BLOCK_SIZE;
50
51         if (encode_length(len) > limit)
52                 return 0;
53
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);
58         len >>= 5;
59
60         /* One byte only? */
61         if (!len) {
62                 arr[0] |= SINGLE_BYTE;
63                 return hdrlen;
64         }
65
66         /* Middle bytes. */
67         while (len >= (1 << 6)) {
68                 /* Next 7 data bits */
69                 arr[hdrlen++] = (len & 0x7F);
70                 len >>= 7;
71         }
72         arr[hdrlen++] = (len | TERM_BIT);
73         return hdrlen;
74 }
75
76 /* Returns bytes used for header. */
77 static unsigned decode(unsigned long *len, bool *free, const unsigned char *arr)
78 {
79         unsigned int hdrlen = 0, bits = 5;
80
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;
90                         hdrlen++;
91                         bits += 7;
92                 }
93                 /* Final byte has 6 bits. */
94                 *len |= (arr[hdrlen] & 0x3fUL) << bits;
95                 hdrlen++;
96         }
97
98         *len += MIN_BLOCK_SIZE;
99         return hdrlen;
100 }
101
102 /* We keep a recently-freed array, one byte per k. */
103 static unsigned long free_array_size(unsigned long poolsize)
104 {
105         return poolsize / 1024;
106 }
107
108 void tiny_alloc_init(void *pool, unsigned long poolsize)
109 {
110         /* We start with free array, and then the rest is free. */
111         unsigned long arrsize = free_array_size(poolsize);
112
113         /* Do nothing with 1 byte or less! */
114         if (poolsize < MIN_BLOCK_SIZE)
115                 return;
116
117         memset(pool, 0, arrsize);
118         encode(poolsize - arrsize, true,
119                (unsigned char *)pool + arrsize, poolsize - arrsize);
120 }
121
122 /* Walk through and try to coalesce */
123 static bool try_coalesce(unsigned char *pool, unsigned long poolsize)
124 {
125         unsigned long len, hdrlen, prev_off = 0, prev_len = 0, off;
126         bool free, prev_free = false, coalesced = false;
127
128         off = free_array_size(poolsize);
129         do {
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);
134                         coalesced = true;
135                 }
136                 prev_free = free;
137                 prev_off = off;
138                 prev_len = len;
139                 off += len;
140         } while (off < poolsize);
141
142         return coalesced;
143 }
144
145 static bool long_enough(unsigned long offset, unsigned long len,
146                         unsigned long size, unsigned long align)
147 {
148         unsigned long end = offset + len;
149
150         offset += encode_len_with_header(len);
151         offset = align_up(offset, align);
152         return offset + size <= end;
153 }
154
155 void *tiny_alloc_get(void *pool, unsigned long poolsize,
156                      unsigned long size, unsigned long align)
157 {
158         unsigned long arrsize = free_array_size(poolsize);
159         unsigned long len, off, actual, hdr, hdrlen;
160         bool free;
161
162         /* We can't do anything with tiny pools. */
163         if (poolsize < MIN_BLOCK_SIZE)
164                 return NULL;
165
166         /* We don't do zero-allocs; allows 1 more offset in encoding. */
167         if (!size)
168                 size = 1;
169
170         /* FIXME: Look through free array. */
171
172 again:
173         off = arrsize;
174
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. */
178
179                 /* Hit end? */
180                 off += len;
181                 if (off == poolsize) {
182                         if (try_coalesce(pool, poolsize))
183                                 goto again;
184                         return NULL;
185                 }
186                 hdrlen = decode(&len, &free, (unsigned char *)pool + off);
187         }
188
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);
192
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);
196         } else {
197                 hdr = off;
198         }
199
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);
203
204         /* Create header for allocated block. */
205         encode(off + len - hdr, false, (unsigned char *)pool + hdr, poolsize);
206
207         return (unsigned char *)pool + actual;
208 }
209
210 static unsigned char *to_hdr(void *p)
211 {
212         unsigned char *hdr = p;
213
214         /* Walk back to find end of header. */
215         while (!*(--hdr));
216         assert(*hdr & TERM_BIT);
217
218         /* Now walk back to find start of header. */
219         if (!(*hdr & SINGLE_BYTE)) {
220                 while (!(*(--hdr) & TERM_BIT));
221         }
222         return hdr;
223 }
224
225 void tiny_alloc_free(void *pool, unsigned long poolsize, void *freep)
226 {
227         unsigned char *hdr;
228
229         /* Too small to do anything. */
230         if (poolsize < MIN_BLOCK_SIZE)
231                 return;
232
233         hdr = to_hdr(freep);
234
235         /* FIXME: Put in free array. */
236         hdr[0] |= FREE_BIT;
237 }
238
239 unsigned long tiny_alloc_size(void *pool, unsigned long poolsize, void *p)
240 {
241         unsigned char *hdr = to_hdr(p);
242         unsigned long len, hdrlen;
243         bool free;
244
245         hdrlen = decode(&len, &free, hdr);
246         return len - hdrlen;
247 }
248
249 /* Useful for gdb breakpoints. */
250 static bool tiny_check_fail(void)
251 {
252         return false;
253 }
254
255 bool tiny_alloc_check(void *pool, unsigned long poolsize)
256 {
257         unsigned long arrsize = free_array_size(poolsize);
258         unsigned char *arr = pool;
259         unsigned long len, off, hdrlen;
260         bool free;
261
262         if (poolsize < MIN_BLOCK_SIZE)
263                 return true;
264
265         /* For the moment, free array is all zeroes. */
266         for (off = 0; off < arrsize; off++) {
267                 if (arr[off] != 0)
268                         return tiny_check_fail();
269         }
270
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)) {
276                         unsigned long off2;
277                         for (off2 = off+1; off2 < poolsize; off2++) {
278                                 if (arr[off2] & TERM_BIT)
279                                         break;
280                         }
281                         if (off2 == poolsize)
282                                 return tiny_check_fail();
283                 }
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();
289         }
290         return true;
291 }
292
293 /* FIXME: Implement. */
294 void tiny_alloc_visualize(FILE *out, void *pool, unsigned long poolsize)
295 {
296 }