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