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 #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 }