ffd17c65734f881f1ca355ed9e1a5b705dd3ff46
[ccan] / ccan / alloc / tiny.c
1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
2 #include "tiny.h"
3 #include "bitops.h"
4 #include <assert.h>
5 #include <stdlib.h>
6 #include <string.h>
7
8 /* One byte header, one byte data. */
9 #define MIN_BLOCK_SIZE 2
10
11 /* Bit 7 (in any byte) == start or end. */
12 #define TERM_BIT 0x80
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?" */
16 #define FREE_BIT 0x20
17
18 #define MAX_FREE_CACHED_SIZE 256
19
20 /* Val is usually offset by MIN_BLOCK_SIZE here. */
21 static unsigned encode_length(unsigned long val)
22 {
23         unsigned int bits = afls(val);
24         /* 5 bits in first byte. */
25         if (bits <= 5)
26                 return 1;
27         /* 6 bits in last byte, 7 bits in middle ones. */
28         return 2 + (bits - 5) / 7;
29 }
30
31 /* Header is included in length, so we might need an extra byte. */
32 static unsigned encode_len_with_header(unsigned long len)
33 {
34         unsigned int hdrlen = 1;
35
36         assert(len);
37         while (encode_length(len + hdrlen - MIN_BLOCK_SIZE) != hdrlen)
38                 hdrlen = encode_length(len + hdrlen - MIN_BLOCK_SIZE);
39
40         return hdrlen;
41 }
42
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[])
46 {
47         unsigned int hdrlen = 1;
48
49         /* We can never have a length < MIN_BLOCK_SIZE. */
50         assert(len >= MIN_BLOCK_SIZE);
51         len -= MIN_BLOCK_SIZE;
52
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);
57         len >>= 5;
58
59         /* One byte only? */
60         if (!len) {
61                 arr[0] |= SINGLE_BYTE;
62                 return hdrlen;
63         }
64
65         /* Middle bytes. */
66         while (len >= (1 << 6)) {
67                 /* Next 7 data bits */
68                 arr[hdrlen++] = (len & 0x7F);
69                 len >>= 7;
70         }
71         arr[hdrlen++] = (len | TERM_BIT);
72         return hdrlen;
73 }
74
75 /* Returns bytes used for header. */
76 static unsigned decode(unsigned long *len, bool *free, const unsigned char *arr)
77 {
78         unsigned int hdrlen = 0, bits = 5;
79
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;
89                         hdrlen++;
90                         bits += 7;
91                 }
92                 /* Final byte has 6 bits. */
93                 *len |= (arr[hdrlen] & 0x3fUL) << bits;
94                 hdrlen++;
95         }
96
97         *len += MIN_BLOCK_SIZE;
98         return hdrlen;
99 }
100
101 /* We keep a helper array for freed mem, one byte per k. */
102 static unsigned long free_array_size(unsigned long poolsize)
103 {
104         return poolsize / 1024;
105 }
106
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.
109  */
110 static unsigned long free_array_off(unsigned long size)
111 {
112         unsigned long off;
113
114         if (size <= 4)
115                 off = size - 1;
116         else if (size <= 16)
117                 off = size / 2 + 1;
118         else
119                 off = size / 4 + 5;
120
121         off *= 3;
122         return off;
123 }
124
125 void tiny_alloc_init(void *pool, unsigned long poolsize)
126 {
127         /* We start with free array, and then the rest is free. */
128         unsigned long arrsize = free_array_size(poolsize);
129
130         /* Do nothing with 1 byte or less! */
131         if (poolsize < MIN_BLOCK_SIZE)
132                 return;
133
134         memset(pool, 0, arrsize);
135         encode(poolsize - arrsize, true, (unsigned char *)pool + arrsize);
136 }
137
138 /* Walk through and try to coalesce */
139 static bool try_coalesce(unsigned char *pool, unsigned long poolsize)
140 {
141         unsigned long len, prev_off = 0, prev_len = 0, off;
142         bool free, prev_free = false, coalesced = false;
143
144         off = free_array_size(poolsize);
145         do {
146                 decode(&len, &free, pool + off);
147                 if (free && prev_free) {
148                         prev_len += len;
149                         encode(prev_len, true, pool + prev_off);
150                         coalesced = true;
151                 } else {
152                         prev_free = free;
153                         prev_off = off;
154                         prev_len = len;
155                 }
156                 off += len;
157         } while (off < poolsize);
158
159         /* Clear the free array. */
160         if (coalesced)
161                 memset(pool, 0, free_array_size(poolsize));
162
163         return coalesced;
164 }
165
166 static bool long_enough(unsigned long offset, unsigned long len,
167                         unsigned long size, unsigned long align)
168 {
169         unsigned long end = offset + len;
170
171         offset += encode_len_with_header(len);
172         offset = align_up(offset, align);
173         return offset + size <= end;
174 }
175
176 static void add_to_free_array(unsigned char *arr,
177                               unsigned long poolsize,
178                               unsigned long size,
179                               unsigned long off)
180 {
181         unsigned long fa_off;
182
183         if (size >= MAX_FREE_CACHED_SIZE)
184                 return;
185
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);
192                         arr[fa_off+2] = off;
193                         break;
194                 }
195         }
196 }
197
198 void *tiny_alloc_get(void *pool, unsigned long poolsize,
199                      unsigned long size, unsigned long align)
200 {
201         unsigned long arrsize = free_array_size(poolsize);
202         unsigned long len, off, actual, hdr, free_bucket;
203         long fa_off;
204         unsigned char *arr = pool;
205         bool free, coalesced = false;
206
207         /* We can't do anything with tiny pools. */
208         if (poolsize < MIN_BLOCK_SIZE)
209                 return NULL;
210
211         /* We don't do zero-allocs; allows 1 more offset in encoding. */
212         if (!size)
213                 size = 1;
214
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);
218              free_bucket += 3) {
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]);
225                         if (!off)
226                                 continue;
227
228                         decode(&len, &free, arr + off);
229                         if (long_enough(off, len, size, align)) {
230                                 /* Remove it. */
231                                 memset(&arr[fa_off], 0, 3);
232                                 goto found;
233                         }
234                 }
235         }
236
237 again:
238         off = arrsize;
239
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);
245
246                 off += len;
247                 /* Hit end? */
248                 if (off == poolsize) {
249                         if (!coalesced && try_coalesce(pool, poolsize)) {
250                                 coalesced = true;
251                                 goto again;
252                         }
253                         return NULL;
254                 }
255                 decode(&len, &free, arr + off);
256         }
257
258 found:
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);
262
263
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);
268         } else {
269                 hdr = off;
270         }
271
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);
275
276         /* Create header for allocated block. */
277         encode(off + len - hdr, false, arr + hdr);
278
279         return arr + actual;
280 }
281
282 static unsigned char *to_hdr(void *p)
283 {
284         unsigned char *hdr = p;
285
286         /* Walk back to find end of header. */
287         while (!*(--hdr));
288         assert(*hdr & TERM_BIT);
289
290         /* Now walk back to find start of header. */
291         if (!(*hdr & SINGLE_BYTE)) {
292                 while (!(*(--hdr) & TERM_BIT));
293         }
294         return hdr;
295 }
296
297 void tiny_alloc_free(void *pool, unsigned long poolsize, void *freep)
298 {
299         unsigned long len;
300         unsigned char *arr = pool;
301         unsigned char *hdr;
302         bool free;
303
304         /* Too small to do anything. */
305         if (poolsize < MIN_BLOCK_SIZE)
306                 return;
307
308         hdr = to_hdr(freep);
309
310         decode(&len, &free, hdr);
311         assert(!free);
312         hdr[0] |= FREE_BIT;
313
314         /* If an empty slot, put this in free array. */
315         add_to_free_array(pool, poolsize, len, hdr - arr);
316 }
317
318 unsigned long tiny_alloc_size(void *pool, unsigned long poolsize, void *p)
319 {
320         unsigned char *hdr = to_hdr(p);
321         unsigned long len, hdrlen;
322         bool free;
323
324         hdrlen = decode(&len, &free, hdr);
325         return len - hdrlen;
326 }
327
328 /* Useful for gdb breakpoints. */
329 static bool tiny_check_fail(void)
330 {
331         return false;
332 }
333
334 static bool check_decode(const unsigned char *arr, unsigned long len)
335 {
336         unsigned int i;
337
338         if (len == 0)
339                 return tiny_check_fail();
340         if (!(arr[0] & TERM_BIT))
341                 return tiny_check_fail();
342         if (arr[0] & SINGLE_BYTE)
343                 return true;
344         for (i = 1; i < len; i++) {
345                 if (arr[i] & TERM_BIT)
346                         return true;
347         }
348         return tiny_check_fail();
349 }
350
351 bool tiny_alloc_check(void *pool, unsigned long poolsize)
352 {
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;
357         bool free;
358
359         if (poolsize < MIN_BLOCK_SIZE)
360                 return true;
361
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]);
366                 if (!off)
367                         continue;
368
369                 if (off >= poolsize)
370                         return tiny_check_fail();
371                 freearr[num_freearr++] = off;
372         }
373
374         for (off = arrsize; off < poolsize; off += len) {
375                 /* We should have a valid header. */
376                 if (!check_decode(arr + off, poolsize - off))
377                         return false;
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) {
385                                 if (!free)
386                                         return tiny_check_fail();
387                                 memmove(&freearr[i], &freearr[i+1],
388                                         (num_freearr-- - (i + 1))
389                                         * sizeof(freearr[i]));
390                                 break;
391                         }
392                 }
393         }
394
395         /* Now we should have found everything in freearr. */
396         if (num_freearr)
397                 return tiny_check_fail();
398
399         /* Now check that sizes are correct. */
400         for (i = 0; i + 3 < free_array_size(poolsize); i += 3) {
401                 unsigned long fa_off;
402
403                 off = ((unsigned long)arr[i]) << 16
404                         | ((unsigned long)arr[i+1]) << 8
405                         | ((unsigned long)arr[i+2]);
406                 if (!off)
407                         continue;
408
409                 decode(&len, &free, arr + off);
410
411                 /* Would we expect to find this length in this bucket? */
412                 if (len >= MAX_FREE_CACHED_SIZE)
413                         return tiny_check_fail();
414
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)) {
418                         if (fa_off == i)
419                                 break;
420                 }
421                 if (fa_off != i)
422                         return tiny_check_fail();
423         }
424
425         return true;
426 }
427
428 /* FIXME: Implement. */
429 void tiny_alloc_visualize(FILE *out, void *pool, unsigned long poolsize)
430 {
431 }