alloc: remove encode limit arg, and implement free array cache.
[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. */
42 static unsigned encode(unsigned long len, bool free, unsigned char arr[])
43 {
44         unsigned int hdrlen = 1;
45
46         /* We can never have a length < MIN_BLOCK_SIZE. */
47         assert(len >= MIN_BLOCK_SIZE);
48         len -= MIN_BLOCK_SIZE;
49
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);
54         len >>= 5;
55
56         /* One byte only? */
57         if (!len) {
58                 arr[0] |= SINGLE_BYTE;
59                 return hdrlen;
60         }
61
62         /* Middle bytes. */
63         while (len >= (1 << 6)) {
64                 /* Next 7 data bits */
65                 arr[hdrlen++] = (len & 0x7F);
66                 len >>= 7;
67         }
68         arr[hdrlen++] = (len | TERM_BIT);
69         return hdrlen;
70 }
71
72 /* Returns bytes used for header. */
73 static unsigned decode(unsigned long *len, bool *free, const unsigned char *arr)
74 {
75         unsigned int hdrlen = 0, bits = 5;
76
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;
86                         hdrlen++;
87                         bits += 7;
88                 }
89                 /* Final byte has 6 bits. */
90                 *len |= (arr[hdrlen] & 0x3fUL) << bits;
91                 hdrlen++;
92         }
93
94         *len += MIN_BLOCK_SIZE;
95         return hdrlen;
96 }
97
98 /* We keep a recently-freed array, one byte per k. */
99 static unsigned long free_array_size(unsigned long poolsize)
100 {
101         return poolsize / 1024;
102 }
103
104 void tiny_alloc_init(void *pool, unsigned long poolsize)
105 {
106         /* We start with free array, and then the rest is free. */
107         unsigned long arrsize = free_array_size(poolsize);
108
109         /* Do nothing with 1 byte or less! */
110         if (poolsize < MIN_BLOCK_SIZE)
111                 return;
112
113         memset(pool, 0, arrsize);
114         encode(poolsize - arrsize, true, (unsigned char *)pool + arrsize);
115 }
116
117 /* Walk through and try to coalesce */
118 static bool try_coalesce(unsigned char *pool, unsigned long poolsize)
119 {
120         unsigned long len, hdrlen, prev_off = 0, prev_len = 0, off;
121         bool free, prev_free = false, coalesced = false;
122
123         off = free_array_size(poolsize);
124         do {
125                 hdrlen = decode(&len, &free, pool + off);
126                 if (free && prev_free) {
127                         encode(prev_len + len, true, pool + prev_off);
128                         coalesced = true;
129                 }
130                 prev_free = free;
131                 prev_off = off;
132                 prev_len = len;
133                 off += len;
134         } while (off < poolsize);
135
136         /* FIXME: Refill free_array here. */
137         if (coalesced)
138                 memset(pool, 0, free_array_size(poolsize));
139
140         return coalesced;
141 }
142
143 static bool long_enough(unsigned long offset, unsigned long len,
144                         unsigned long size, unsigned long align)
145 {
146         unsigned long end = offset + len;
147
148         offset += encode_len_with_header(len);
149         offset = align_up(offset, align);
150         return offset + size <= end;
151 }
152
153 static unsigned long find_free_end(unsigned char *arr, unsigned long arrsize)
154 {
155         unsigned long end;
156
157         for (end = 0; end < arrsize; end++) {
158                 if (!arr[end])
159                         break;
160         }
161         return end;
162 }
163
164 void *tiny_alloc_get(void *pool, unsigned long poolsize,
165                      unsigned long size, unsigned long align)
166 {
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;
170         bool free;
171
172         /* We can't do anything with tiny pools. */
173         if (poolsize < MIN_BLOCK_SIZE)
174                 return NULL;
175
176         /* We don't do zero-allocs; allows 1 more offset in encoding. */
177         if (!size)
178                 size = 1;
179
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_hdrlen);
190                         memset(arr + freelen - fa_hdrlen, 0, fa_hdrlen);
191                         goto found;
192                 }
193         }
194
195 again:
196         off = arrsize;
197
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. */
201
202                 /* Hit end? */
203                 off += len;
204                 if (off == poolsize) {
205                         if (try_coalesce(pool, poolsize))
206                                 goto again;
207                         return NULL;
208                 }
209                 hdrlen = decode(&len, &free, arr + off);
210         }
211
212 found:
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);
216
217         /* Do we have enough room to split? */
218         if (hdr - off >= MIN_BLOCK_SIZE) {
219                 encode(hdr - off, true, arr + off);
220         } else {
221                 hdr = off;
222         }
223
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);
227
228         /* Create header for allocated block. */
229         encode(off + len - hdr, false, arr + hdr);
230
231         return arr + actual;
232 }
233
234 static unsigned char *to_hdr(void *p)
235 {
236         unsigned char *hdr = p;
237
238         /* Walk back to find end of header. */
239         while (!*(--hdr));
240         assert(*hdr & TERM_BIT);
241
242         /* Now walk back to find start of header. */
243         if (!(*hdr & SINGLE_BYTE)) {
244                 while (!(*(--hdr) & TERM_BIT));
245         }
246         return hdr;
247 }
248
249 void tiny_alloc_free(void *pool, unsigned long poolsize, void *freep)
250 {
251         unsigned long len, end, arrsize = free_array_size(poolsize);
252         unsigned char *arr = pool;
253         unsigned char *hdr;
254
255         /* Too small to do anything. */
256         if (poolsize < MIN_BLOCK_SIZE)
257                 return;
258
259         hdr = to_hdr(freep);
260         hdr[0] |= FREE_BIT;
261
262         end = find_free_end(pool, arrsize);
263
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);
268 }
269
270 unsigned long tiny_alloc_size(void *pool, unsigned long poolsize, void *p)
271 {
272         unsigned char *hdr = to_hdr(p);
273         unsigned long len, hdrlen;
274         bool free;
275
276         hdrlen = decode(&len, &free, hdr);
277         return len - hdrlen;
278 }
279
280 /* Useful for gdb breakpoints. */
281 static bool tiny_check_fail(void)
282 {
283         return false;
284 }
285
286 static bool check_decode(const unsigned char *arr, unsigned long len)
287 {
288         unsigned int i;
289
290         if (len == 0)
291                 return tiny_check_fail();
292         if (!(arr[0] & TERM_BIT))
293                 return tiny_check_fail();
294         if (arr[0] & SINGLE_BYTE)
295                 return true;
296         for (i = 1; i < len; i++) {
297                 if (arr[i] & TERM_BIT)
298                         return true;
299         }
300         return tiny_check_fail();
301 }
302
303 bool tiny_alloc_check(void *pool, unsigned long poolsize)
304 {
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;
309         bool free;
310
311         if (poolsize < MIN_BLOCK_SIZE)
312                 return true;
313
314         end = find_free_end(pool, arrsize);
315         for (off = 0; off < end; off += hdrlen) {
316                 if (!check_decode(arr + off, end - off))
317                         return false;
318                 hdrlen = decode(&off2, &free, arr + off);
319                 off2 -= MIN_BLOCK_SIZE;
320                 if (off2 >= poolsize)
321                         return tiny_check_fail();
322                 if (!free)
323                         return tiny_check_fail();
324                 freearr[num_freearr++] = off2;
325         }
326         /* Rest of free array should be all zeroes. */
327         for (off = end; off < arrsize; off++) {
328                 if (arr[off] != 0)
329                         return tiny_check_fail();
330         }
331
332         for (off = arrsize; off < poolsize; off += len) {
333                 /* We should have a valid header. */
334                 if (!check_decode(arr + off, poolsize - off))
335                         return false;
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) {
343                                 if (!free)
344                                         return tiny_check_fail();
345                                 memmove(&freearr[i], &freearr[i+1],
346                                         (num_freearr-- - (i + 1))
347                                         * sizeof(freearr[i]));
348                                 break;
349                         }
350                 }
351         }
352
353         /* Now we should have found everything in freearr. */
354         if (num_freearr)
355                 return tiny_check_fail();
356                 
357         return true;
358 }
359
360 /* FIXME: Implement. */
361 void tiny_alloc_visualize(FILE *out, void *pool, unsigned long poolsize)
362 {
363 }