git.ozlabs.org Git - ccan/blob - alloc/alloc.c

   1 #include <unistd.h>
   2 #include <stdint.h>
   3 #include <string.h>
   4 #include <limits.h>
   5 #include <assert.h>
   6 #include "alloc.h"
   7 #include "build_assert/build_assert.h"
   8 #include "config.h"
   9
  10 #if HAVE_ALIGNOF
  11 #define ALIGNOF(t) __alignof__(t)
  12 #else
  13 /* Alignment by measuring structure padding. */
  14 #define ALIGNOF(t) (sizeof(struct { char c; t _h; }) - 1 - sizeof(t))
  15 #endif
  16
  17 /* FIXME: Doesn't handle non-page-aligned poolsize. */
  18
  19 /* FIXME: Reduce. */
  20 #define MIN_SIZE (getpagesize() * 2)
  21
  22 /* Metadata looks like this:
  23  * <unsigned long metalen> <page states> <align-pad> [<1-byte-len> <free|bit|uniform> bits...]* [unsigned long next].
  24  */
  25
  26 #define BITS_PER_PAGE 2
  27 enum page_state
  28 {
  29         FREE,
  30         TAKEN,
  31         TAKEN_START,
  32 };
  33
  34 static enum page_state get_page_state(const uint8_t *bits, unsigned long page)
  35 {
  36         bits += sizeof(unsigned long);
  37         return bits[page * 2 / CHAR_BIT] >> (page * 2 % CHAR_BIT) & 3;
  38 }
  39
  40 static void set_page_state(uint8_t *bits, unsigned long page, enum page_state s)
  41 {
  42         bits += sizeof(unsigned long);
  43         bits[page * 2 / CHAR_BIT] &= ~(3 << (page * 2 % CHAR_BIT));
  44         bits[page * 2 / CHAR_BIT] |= ((uint8_t)s << (page * 2 % CHAR_BIT));
  45 }
  46
  47 /* Assumes a is a power of two. */
  48 static unsigned long align_up(unsigned long x, unsigned long a)
  49 {
  50         return (x + a - 1) & ~(a - 1);
  51 }
  52
  53 static unsigned long div_up(unsigned long x, unsigned long a)
  54 {
  55         return (x + a - 1) / a;
  56 }
  57
  58 static unsigned long metadata_length(void *pool, unsigned long poolsize)
  59 {
  60         return *(unsigned long *)pool;
  61 }
  62
  63 void alloc_init(void *pool, unsigned long poolsize)
  64 {
  65         /* FIXME: Alignment assumptions about pool. */
  66         unsigned long *metalen = pool, pages, pagestatebytes, i;
  67
  68         if (poolsize < MIN_SIZE)
  69                 return;
  70
  71         pages = poolsize / getpagesize();
  72
  73         /* First comes the metadata length, then 2 bits per page, then
  74          * the next pointer. */
  75         pagestatebytes = div_up(pages * BITS_PER_PAGE, CHAR_BIT);
  76         *metalen = sizeof(*metalen)
  77                 + align_up(pagestatebytes, ALIGNOF(unsigned long))
  78                 + sizeof(unsigned long);
  79
  80         /* Mark all the bits FREE to start, and zero the next pointer. */
  81         BUILD_ASSERT(FREE == 0);
  82         memset(metalen + 1, 0, *metalen - sizeof(*metalen));
  83
  84         /* Mark the metadata page(s) allocated. */
  85         set_page_state(pool, 0, TAKEN_START);
  86         for (i = 1; i < div_up(*metalen, getpagesize()); i++)
  87                 set_page_state(pool, i, TAKEN);
  88 }
  89
  90 static void *alloc_get_pages(void *pool, unsigned long poolsize,
  91                              unsigned long pages, unsigned long align)
  92 {
  93         long i;
  94         unsigned long free;
  95
  96         free = 0;
  97         /* We allocate from far end, to increase ability to expand metadata. */
  98         for (i = poolsize / getpagesize() - 1; i >= 0; i--) {
  99                 switch (get_page_state(pool, i)) {
 100                 case FREE:
 101                         if (++free >= pages) {
 102                                 unsigned long j;
 103                                 char *ret = (char *)pool + i * getpagesize();
 104
 105                                 /* They might ask for multi-page alignment. */
 106                                 if ((unsigned long)ret % align)
 107                                         continue;
 108
 109                                 for (j = i+1; j < i + pages; j++)
 110                                         set_page_state(pool, j, TAKEN);
 111                                 set_page_state(pool, i, TAKEN_START);
 112                                 return ret;
 113                         }
 114                         break;
 115                 case TAKEN_START:
 116                 case TAKEN:
 117                         free = 0;
 118                         break;
 119                 }
 120         }
 121
 122         return NULL;
 123 }
 124
 125 void *alloc_get(void *pool, unsigned long poolsize,
 126                 unsigned long size, unsigned long align)
 127 {
 128         if (poolsize < MIN_SIZE)
 129                 return NULL;
 130
 131         if (size >= getpagesize() || align > getpagesize()) {
 132                 unsigned long pages = (size + getpagesize()-1) / getpagesize();
 133                 return alloc_get_pages(pool, poolsize, pages, align);
 134         }
 135
 136         /* FIXME: Sub-page allocations. */
 137         return alloc_get_pages(pool, poolsize, 1, align);
 138 }
 139
 140 void alloc_free(void *pool, unsigned long poolsize, void *free)
 141 {
 142         unsigned long pagenum, metalen;
 143
 144         if (!free)
 145                 return;
 146
 147         assert(poolsize >= MIN_SIZE);
 148
 149         metalen = metadata_length(pool, poolsize);
 150
 151         assert((char *)free >= (char *)pool + metalen);
 152         assert((char *)pool + poolsize > (char *)free);
 153         assert((unsigned long)free % getpagesize() == 0);
 154
 155         pagenum = ((char *)free - (char *)pool) / getpagesize();
 156
 157         assert(get_page_state(pool, pagenum) == TAKEN_START);
 158         set_page_state(pool, pagenum, FREE);
 159         while (get_page_state(pool, ++pagenum) == TAKEN)
 160                 set_page_state(pool, pagenum, FREE);
 161 }
 162
 163 bool alloc_check(void *pool, unsigned long poolsize)
 164 {
 165         unsigned long i, metalen, pagestatebytes;
 166         enum page_state last_state = FREE;
 167
 168         if (poolsize < MIN_SIZE)
 169                 return true;
 170
 171         metalen = metadata_length(pool, poolsize);
 172         if (get_page_state(pool, 0) != TAKEN_START)
 173                 return false;
 174
 175         pagestatebytes = div_up(poolsize / getpagesize() * BITS_PER_PAGE,
 176                                 CHAR_BIT);
 177         if (metalen < (sizeof(unsigned long)
 178                        + align_up(pagestatebytes, ALIGNOF(unsigned long))
 179                        + sizeof(unsigned long)))
 180                 return false;
 181
 182         for (i = 1; i < poolsize / getpagesize(); i++) {
 183                 enum page_state state = get_page_state(pool, i);
 184
 185                 /* Metadata pages will be marked TAKEN. */
 186                 if (i < div_up(metalen, getpagesize())) {
 187                         if (get_page_state(pool, 0) != TAKEN)
 188                                 return false;
 189                         continue;
 190                 }
 191
 192                 switch (state) {
 193                 case FREE:
 194                 case TAKEN_START:
 195                         break;
 196                 case TAKEN:
 197                         if (last_state == FREE)
 198                                 return false;
 199                         break;
 200                 default:
 201                         return false;
 202                 }
 203                 last_state = state;
 204         }
 205         return true;
 206 }