3ec6952c82c8b6d20187ea722d56a907d518548f
[ccan] / 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 }