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
   8 /* FIXME: Doesn't handle non-page-aligned poolsize. */
   9 /* FIXME: Doesn't handle sub-page allocations. */
  10
  11 #define MIN_SIZE (getpagesize() * 2)
  12
  13 enum page_state
  14 {
  15         FREE,
  16         TAKEN,
  17         TAKEN_START,
  18 };
  19
  20 void alloc_init(void *pool, unsigned long poolsize)
  21 {
  22         uint8_t *bits = pool;
  23         unsigned int pages = poolsize / getpagesize();
  24
  25         if (poolsize < MIN_SIZE)
  26                 return;
  27
  28         memset(bits, 0, (pages * 2 + CHAR_BIT - 1)/ CHAR_BIT);
  29 }
  30
  31 static enum page_state get_page_state(const uint8_t *bits, unsigned long page)
  32 {
  33         return bits[page * 2 / CHAR_BIT] >> (page * 2 % CHAR_BIT) & 3;
  34 }
  35
  36 static void set_page_state(uint8_t *bits, unsigned long page, enum page_state s)
  37 {
  38         bits[page * 2 / CHAR_BIT] &= ~(3 << (page * 2 % CHAR_BIT));
  39         bits[page * 2 / CHAR_BIT] |= ((uint8_t)s << (page * 2 % CHAR_BIT));
  40 }
  41
  42 static unsigned long metadata_length(void *pool, unsigned long poolsize)
  43 {
  44         return ((poolsize / getpagesize() * 2 / CHAR_BIT) + getpagesize() - 1)
  45                 & ~(getpagesize() - 1);
  46 }
  47
  48 void *alloc_get(void *pool, unsigned long poolsize,
  49                 unsigned long size, unsigned long align)
  50 {
  51         long i;
  52         unsigned long free, want, metalen;
  53
  54         if (poolsize < MIN_SIZE)
  55                 return NULL;
  56
  57         /* FIXME: Necessary for this. */
  58         if (size == 0)
  59                 size = 1;
  60
  61         want = (size + getpagesize() - 1) / getpagesize();
  62         metalen = metadata_length(pool, poolsize);
  63
  64         free = 0;
  65         /* We allocate from far end, to increase ability to expand metadata. */
  66         for (i = (poolsize - metalen) / getpagesize() - 1; i >= 0; i--) {
  67                 switch (get_page_state(pool, i)) {
  68                 case FREE:
  69                         if (++free >= want) {
  70                                 unsigned long j;
  71                                 char *ret = (char *)pool + metalen
  72                                         + i * getpagesize();
  73
  74                                 /* They might ask for multi-page alignment. */
  75                                 if ((unsigned long)ret % align)
  76                                         continue;
  77
  78                                 for (j = i+1; j < i + want; j++)
  79                                         set_page_state(pool, j, TAKEN);
  80                                 set_page_state(pool, i, TAKEN_START);
  81                                 return ret;
  82                         }
  83                         break;
  84                 case TAKEN_START:
  85                 case TAKEN:
  86                         free = 0;
  87                         break;
  88                 }
  89         }
  90
  91         return NULL;
  92 }
  93
  94 void alloc_free(void *pool, unsigned long poolsize, void *free)
  95 {
  96         unsigned long pagenum, metalen;
  97
  98         if (poolsize < MIN_SIZE)
  99                 return;
 100
 101         if (!free)
 102                 return;
 103
 104         metalen = metadata_length(pool, poolsize);
 105
 106         assert(free > pool && (char *)pool + poolsize > (char *)free);
 107         assert((unsigned long)free % getpagesize() == 0);
 108
 109         pagenum = ((char *)free - (char *)pool - metalen) / getpagesize();
 110
 111         assert(get_page_state(pool, pagenum) == TAKEN_START);
 112         set_page_state(pool, pagenum, FREE);
 113         while (get_page_state(pool, ++pagenum) == TAKEN)
 114                 set_page_state(pool, pagenum, FREE);
 115 }
 116
 117 bool alloc_check(void *pool, unsigned long poolsize)
 118 {
 119         unsigned int i, metalen;
 120         enum page_state last_state = FREE;
 121
 122         if (poolsize < MIN_SIZE)
 123                 return true;
 124
 125         metalen = metadata_length(pool, poolsize);
 126         for (i = 0; i < (poolsize - metalen) / getpagesize(); i++) {
 127                 enum page_state state = get_page_state(pool, i);
 128                 switch (state) {
 129                 case FREE:
 130                 case TAKEN_START:
 131                         break;
 132                 case TAKEN:
 133                         if (last_state == FREE)
 134                                 return false;
 135                         break;
 136                 default:
 137                         return false;
 138                 }
 139                 last_state = state;
 140         }
 141         return true;
 142 }