git.ozlabs.org Git - ccan/blob - 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 }