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, or 0 if won't fit. */
  42 static unsigned encode(unsigned long len, bool free, unsigned char arr[],
  43                        size_t limit)
  44 {
  45         unsigned int hdrlen = 1;
  46
  47         /* We can never have a length < MIN_BLOCK_SIZE. */
  48         assert(len >= MIN_BLOCK_SIZE);
  49         len -= MIN_BLOCK_SIZE;
  50
  51         if (encode_length(len) > limit)
  52                 return 0;
  53
  54         /* First byte always contains free bit. */
  55         arr[0] = TERM_BIT | (free ? FREE_BIT : 0);
  56         /* Also holds 5 bits of data (0 - 31) */
  57         arr[0] |= (len & 0x1F);
  58         len >>= 5;
  59
  60         /* One byte only? */
  61         if (!len) {
  62                 arr[0] |= SINGLE_BYTE;
  63                 return hdrlen;
  64         }
  65
  66         /* Middle bytes. */
  67         while (len >= (1 << 6)) {
  68                 /* Next 7 data bits */
  69                 arr[hdrlen++] = (len & 0x7F);
  70                 len >>= 7;
  71         }
  72         arr[hdrlen++] = (len | TERM_BIT);
  73         return hdrlen;
  74 }
  75
  76 /* Returns bytes used for header. */
  77 static unsigned decode(unsigned long *len, bool *free, const unsigned char *arr)
  78 {
  79         unsigned int hdrlen = 0, bits = 5;
  80
  81         /* Free flag is in bit 5 */
  82         *free = (arr[hdrlen] & FREE_BIT);
  83         /* Bottom five bits are data. */
  84         *len = (arr[hdrlen] & 0x1f);
  85         if (!(arr[hdrlen++] & SINGLE_BYTE)) {
  86                 /* Multi-byte encoding? */
  87                 while (!(arr[hdrlen] & TERM_BIT)) {
  88                         /* 7 more data bits. */
  89                         *len |= (arr[hdrlen] & 0x7fUL) << bits;
  90                         hdrlen++;
  91                         bits += 7;
  92                 }
  93                 /* Final byte has 6 bits. */
  94                 *len |= (arr[hdrlen] & 0x3fUL) << bits;
  95                 hdrlen++;
  96         }
  97
  98         *len += MIN_BLOCK_SIZE;
  99         return hdrlen;
 100 }
 101
 102 /* We keep a recently-freed array, one byte per k. */
 103 static unsigned long free_array_size(unsigned long poolsize)
 104 {
 105         return poolsize / 1024;
 106 }
 107
 108 void tiny_alloc_init(void *pool, unsigned long poolsize)
 109 {
 110         /* We start with free array, and then the rest is free. */
 111         unsigned long arrsize = free_array_size(poolsize);
 112
 113         /* Do nothing with 1 byte or less! */
 114         if (poolsize < MIN_BLOCK_SIZE)
 115                 return;
 116
 117         memset(pool, 0, arrsize);
 118         encode(poolsize - arrsize, true,
 119                (unsigned char *)pool + arrsize, poolsize - arrsize);
 120 }
 121
 122 /* Walk through and try to coalesce */
 123 static bool try_coalesce(unsigned char *pool, unsigned long poolsize)
 124 {
 125         unsigned long len, hdrlen, prev_off = 0, prev_len = 0, off;
 126         bool free, prev_free = false, coalesced = false;
 127
 128         off = free_array_size(poolsize);
 129         do {
 130                 hdrlen = decode(&len, &free, pool + off);
 131                 if (free && prev_free) {
 132                         encode(prev_len + len, true, pool + prev_off,
 133                                poolsize - prev_off);
 134                         coalesced = true;
 135                 }
 136                 prev_free = free;
 137                 prev_off = off;
 138                 prev_len = len;
 139                 off += len;
 140         } while (off < poolsize);
 141
 142         return coalesced;
 143 }
 144
 145 static bool long_enough(unsigned long offset, unsigned long len,
 146                         unsigned long size, unsigned long align)
 147 {
 148         unsigned long end = offset + len;
 149
 150         offset += encode_len_with_header(len);
 151         offset = align_up(offset, align);
 152         return offset + size <= end;
 153 }
 154
 155 void *tiny_alloc_get(void *pool, unsigned long poolsize,
 156                      unsigned long size, unsigned long align)
 157 {
 158         unsigned long arrsize = free_array_size(poolsize);
 159         unsigned long len, off, actual, hdr, hdrlen;
 160         bool free;
 161
 162         /* We can't do anything with tiny pools. */
 163         if (poolsize < MIN_BLOCK_SIZE)
 164                 return NULL;
 165
 166         /* We don't do zero-allocs; allows 1 more offset in encoding. */
 167         if (!size)
 168                 size = 1;
 169
 170         /* FIXME: Look through free array. */
 171
 172 again:
 173         off = arrsize;
 174
 175         hdrlen = decode(&len, &free, (unsigned char *)pool + off);
 176         while (!free || !long_enough(off, len, size, align)) {
 177                 /* FIXME: Refill free array if this block is free. */
 178
 179                 /* Hit end? */
 180                 off += len;
 181                 if (off == poolsize) {
 182                         if (try_coalesce(pool, poolsize))
 183                                 goto again;
 184                         return NULL;
 185                 }
 186                 hdrlen = decode(&len, &free, (unsigned char *)pool + off);
 187         }
 188
 189         /* We have a free block.  Since we walk from front, take far end. */
 190         actual = ((off + len - size) & ~(align - 1));
 191         hdr = actual - encode_len_with_header(off + len - actual);
 192
 193         /* Do we have enough room to split? */
 194         if (hdr - off >= MIN_BLOCK_SIZE) {
 195                 encode(hdr - off, true, (unsigned char *)pool + off, poolsize);
 196         } else {
 197                 hdr = off;
 198         }
 199
 200         /* Make sure that we are all-zero up to actual, so we can walk back
 201          * and find header. */
 202         memset((unsigned char *)pool + hdr, 0, actual - hdr);
 203
 204         /* Create header for allocated block. */
 205         encode(off + len - hdr, false, (unsigned char *)pool + hdr, poolsize);
 206
 207         return (unsigned char *)pool + actual;
 208 }
 209
 210 static unsigned char *to_hdr(void *p)
 211 {
 212         unsigned char *hdr = p;
 213
 214         /* Walk back to find end of header. */
 215         while (!*(--hdr));
 216         assert(*hdr & TERM_BIT);
 217
 218         /* Now walk back to find start of header. */
 219         if (!(*hdr & SINGLE_BYTE)) {
 220                 while (!(*(--hdr) & TERM_BIT));
 221         }
 222         return hdr;
 223 }
 224
 225 void tiny_alloc_free(void *pool, unsigned long poolsize, void *freep)
 226 {
 227         unsigned char *hdr;
 228
 229         /* Too small to do anything. */
 230         if (poolsize < MIN_BLOCK_SIZE)
 231                 return;
 232
 233         hdr = to_hdr(freep);
 234
 235         /* FIXME: Put in free array. */
 236         hdr[0] |= FREE_BIT;
 237 }
 238
 239 unsigned long tiny_alloc_size(void *pool, unsigned long poolsize, void *p)
 240 {
 241         unsigned char *hdr = to_hdr(p);
 242         unsigned long len, hdrlen;
 243         bool free;
 244
 245         hdrlen = decode(&len, &free, hdr);
 246         return len - hdrlen;
 247 }
 248
 249 /* Useful for gdb breakpoints. */
 250 static bool tiny_check_fail(void)
 251 {
 252         return false;
 253 }
 254
 255 bool tiny_alloc_check(void *pool, unsigned long poolsize)
 256 {
 257         unsigned long arrsize = free_array_size(poolsize);
 258         unsigned char *arr = pool;
 259         unsigned long len, off, hdrlen;
 260         bool free;
 261
 262         if (poolsize < MIN_BLOCK_SIZE)
 263                 return true;
 264
 265         /* For the moment, free array is all zeroes. */
 266         for (off = 0; off < arrsize; off++) {
 267                 if (arr[off] != 0)
 268                         return tiny_check_fail();
 269         }
 270
 271         for (off = arrsize; off < poolsize; off += len) {
 272                 /* We should have a valid header. */
 273                 if (!(arr[off] & TERM_BIT))
 274                         return tiny_check_fail();
 275                 if (!(arr[off] & SINGLE_BYTE)) {
 276                         unsigned long off2;
 277                         for (off2 = off+1; off2 < poolsize; off2++) {
 278                                 if (arr[off2] & TERM_BIT)
 279                                         break;
 280                         }
 281                         if (off2 == poolsize)
 282                                 return tiny_check_fail();
 283                 }
 284                 hdrlen = decode(&len, &free, arr + off);
 285                 if (off + len > poolsize)
 286                         return tiny_check_fail();
 287                 if (hdrlen != encode_length(len - MIN_BLOCK_SIZE))
 288                         return tiny_check_fail();
 289         }
 290         return true;
 291 }
 292
 293 /* FIXME: Implement. */
 294 void tiny_alloc_visualize(FILE *out, void *pool, unsigned long poolsize)
 295 {
 296 }