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         unsigned long i, free, want, metalen;
  52
  53         if (poolsize < MIN_SIZE)
  54                 return NULL;
  55
  56         /* FIXME: Necessary for this. */
  57         if (size == 0)
  58                 size = 1;
  59
  60         want = (size + getpagesize() - 1) / getpagesize();
  61         metalen = metadata_length(pool, poolsize);
  62
  63         free = 0;
  64         for (i = 0; i < (poolsize - metalen) / getpagesize(); i++) {
  65                 switch (get_page_state(pool, i)) {
  66                 case FREE:
  67                         if (++free >= want) {
  68                                 unsigned int j;
  69                                 char *ret = (char *)pool + metalen
  70                                         + (i - want + 1) * getpagesize();
  71
  72                                 if ((unsigned long)ret % align)
  73                                         continue;
  74
  75                                 for (j = i; j > i - want + 1; j--)
  76                                         set_page_state(pool, j, TAKEN);
  77                                 set_page_state(pool, i - want + 1, TAKEN_START);
  78                                 return ret;
  79                         }
  80                         break;
  81                 case TAKEN_START:
  82                 case TAKEN:
  83                         free = 0;
  84                         break;
  85                 }
  86         }
  87
  88         return NULL;
  89 }
  90
  91 void alloc_free(void *pool, unsigned long poolsize, void *free)
  92 {
  93         unsigned long pagenum, metalen;
  94
  95         if (poolsize < MIN_SIZE)
  96                 return;
  97
  98         if (!free)
  99                 return;
 100
 101         metalen = metadata_length(pool, poolsize);
 102
 103         assert(free > pool && (char *)pool + poolsize > (char *)free);
 104         assert((unsigned long)free % getpagesize() == 0);
 105
 106         pagenum = ((char *)free - (char *)pool - metalen) / getpagesize();
 107
 108         assert(get_page_state(pool, pagenum) == TAKEN_START);
 109         set_page_state(pool, pagenum, FREE);
 110         while (get_page_state(pool, ++pagenum) == TAKEN)
 111                 set_page_state(pool, pagenum, FREE);
 112 }
 113
 114 bool alloc_check(void *pool, unsigned long poolsize)
 115 {
 116         unsigned int i, metalen;
 117         enum page_state last_state = FREE;
 118
 119         if (poolsize < MIN_SIZE)
 120                 return true;
 121
 122         metalen = metadata_length(pool, poolsize);
 123         for (i = 0; i < (poolsize - metalen) / getpagesize(); i++) {
 124                 enum page_state state = get_page_state(pool, i);
 125                 switch (state) {
 126                 case FREE:
 127                 case TAKEN_START:
 128                         break;
 129                 case TAKEN:
 130                         if (last_state == FREE)
 131                                 return false;
 132                         break;
 133                 default:
 134                         return false;
 135                 }
 136                 last_state = state;
 137         }
 138         return true;
 139 }