git.ozlabs.org Git - ccan/blob - 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         long i;
 156
 157         for (i = arrsize-1; i >= 0; i--) {
 158                 if (arr[i])
 159                         return i + 1;
 160         }
 161         return 0;
 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_off + 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 }