T266: Resizing root cnode enabled for libmm slot allocator
[barrelfish] / lib / barrelfish / slot_alloc / single_slot_alloc.c
1 /**
2  * \file
3  * \brief Slot allocator for a single cnode
4  *
5  * Allocators should be created with worst case slab requirement.
6  * The worst case requirement is the number of slots in the cnode / 2.
7  */
8
9 /*
10  * Copyright (c) 2010, ETH Zurich.
11  * Copyright (c) 2015, Hewlett Packard Enterprise Development LP.
12  * All rights reserved.
13  *
14  * This file is distributed under the terms in the attached LICENSE file.
15  * If you do not find this file, copies can be found by writing to:
16  * ETH Zurich D-INFK, Universitaetstr. 6, CH-8092 Zurich. Attn: Systems Group.
17  */
18
19 #include <barrelfish/barrelfish.h>
20 #include <barrelfish/caddr.h>
21
22 static errval_t salloc(struct slot_allocator *ca, struct capref *ret)
23 {
24     struct single_slot_allocator *sca = (struct single_slot_allocator*)ca;
25
26     if (sca->a.space == 0) {
27         return LIB_ERR_SLOT_ALLOC_NO_SPACE;
28     }
29
30     thread_mutex_lock(&ca->mutex);
31
32     // Slot to return
33     ret->cnode = sca->cnode;
34     ret->slot  = sca->head->slot;
35
36 #if 0
37     char buf[256];
38     debug_print_capref(buf, 256, *ret);
39     debug_printf("%p->salloc: ret = %.*s\n", ca, 256, buf);
40 #endif
41
42     // Decrement space
43     sca->head->space--;
44     sca->head->slot++;
45     sca->a.space--;
46
47     // Check to free head
48     if (sca->head->space == 0) {
49         struct cnode_meta *walk = sca->head;
50         sca->head = walk->next;
51         slab_free(&sca->slab, walk);
52     }
53
54     thread_mutex_unlock(&ca->mutex);
55     return SYS_ERR_OK;
56 }
57
58 static errval_t free_slots(struct single_slot_allocator *sca, cslot_t slot,
59                            cslot_t count, struct thread_mutex *mutex)
60 {
61     thread_mutex_lock(mutex);
62
63     errval_t err = SYS_ERR_OK;
64
65     struct cnode_meta *walk = sca->head;
66     struct cnode_meta *prev = NULL;
67
68     // Entire cnode was allocated
69     if (!sca->head) {
70         sca->head = slab_alloc(&sca->slab);
71         sca->head->slot = slot;
72         sca->head->space = count;
73         sca->head->next = NULL;
74         goto finish;
75     }
76
77     // Freeing one before head
78     if (slot + count == sca->head->slot) {
79         sca->head->slot = slot;
80         sca->head->space += count;
81         goto finish;
82     }
83
84     // Freeing before head
85     if (slot < sca->head->slot) {
86         struct cnode_meta *new = slab_alloc(&sca->slab);
87         new->slot  = slot;
88         new->space = count;
89         new->next  = sca->head;
90         sca->head  = new;
91         goto finish;
92     }
93
94     while (walk != NULL) {
95         // Freeing at the edge of walk
96         if (slot == walk->slot + walk->space) {
97             walk->space += count;
98
99             // check if we can merge walk to next
100             struct cnode_meta *next = walk->next;
101             if (next && next->slot == walk->slot + walk->space) {
102                 walk->space += next->space;
103                 walk->next = next->next;
104                 slab_free(&sca->slab, next);
105             }
106
107             goto finish;
108         }
109         else if (slot < walk->slot + walk->space) {
110             err = LIB_ERR_SLOT_UNALLOCATED;
111             goto unlock;
112         }
113
114         // Freing just before walk->next
115         if (walk->next && slot + count == walk->next->slot) {
116             walk->next->slot = slot;
117             walk->next->space += count;
118             goto finish;
119         }
120
121         // Freeing after walk and before walk->next
122         if (walk->next && slot < walk->next->slot) {
123             struct cnode_meta *new = walk->next;
124             walk->next = slab_alloc(&sca->slab);
125             walk->next->slot = slot;
126             walk->next->space = count;
127             walk->next->next = new;
128             goto finish;
129         }
130         prev = walk;
131         walk = walk->next;
132     }
133
134     // Freeing after the list
135     prev->next = slab_alloc(&sca->slab);
136     prev->next->slot = slot;
137     prev->next->space = count;
138     prev->next->next = NULL;
139
140  finish:
141     sca->a.space += count;
142
143  unlock:
144     thread_mutex_unlock(mutex);
145     return err;
146 }
147
148 static errval_t sfree(struct slot_allocator *ca, struct capref cap)
149 {
150     struct single_slot_allocator *sca = (struct single_slot_allocator*)ca;
151     if (!cnodecmp(cap.cnode, sca->cnode)) {
152         return LIB_ERR_SLOT_ALLOC_WRONG_CNODE;
153     }
154
155     return free_slots(sca, cap.slot, 1, &ca->mutex);
156 }
157
158 cslot_t single_slot_alloc_freecount(struct single_slot_allocator *this)
159 {
160     cslot_t free = 0;
161     for (struct cnode_meta *walk = this->head; walk; walk = walk->next) {
162         free += walk->space;
163     }
164     return free;
165 }
166
167 errval_t single_slot_alloc_resize(struct single_slot_allocator *this,
168                                   cslot_t newslotcount)
169 {
170     errval_t err;
171
172     cslot_t grow = newslotcount - this->a.nslots;
173
174     // Refill slab allocator
175     size_t bufgrow = SINGLE_SLOT_ALLOC_BUFLEN(grow);
176     void *buf = malloc(bufgrow);
177     if (!buf) {
178         return LIB_ERR_MALLOC_FAIL;
179     }
180     slab_grow(&this->slab, buf, bufgrow);
181
182     // Update free slot metadata
183     err = free_slots(this, this->a.nslots, grow, &this->a.mutex);
184     if (err_is_fail(err)) {
185         return err;
186     }
187
188     // Update generic metadata
189     this->a.nslots = newslotcount;
190
191     return SYS_ERR_OK;
192 }
193
194 errval_t single_slot_alloc_init_raw(struct single_slot_allocator *ret,
195                                     struct capref cap, struct cnoderef cnode,
196                                     cslot_t nslots, void *buf, size_t buflen)
197 {
198     /* Generic part */
199     ret->a.alloc = salloc;
200     ret->a.free  = sfree;
201     ret->a.space = nslots;
202     ret->a.nslots = nslots;
203     thread_mutex_init(&ret->a.mutex);
204
205     /* Specific part */
206     ret->cap   = cap;
207     ret->cnode = cnode;
208
209     slab_init(&ret->slab, sizeof(struct cnode_meta), NULL);
210     if (buflen > 0) {
211         // check for callers that do not provide enough buffer space
212         #if !defined(NDEBUG)
213         //on arm, __builtin_return_address does not take arguments !=0
214         #if !defined(__arm__) && !defined(__aarch64__) 
215         size_t buflen_proper = SINGLE_SLOT_ALLOC_BUFLEN(nslots);
216         if (buflen != buflen_proper) {
217             debug_printf("******* FIXME: %s buflen=%zu != buflen_proper=%zu"
218                          "call stack: %p %p\n",
219                          __FUNCTION__, buflen, buflen_proper,
220                          __builtin_return_address(0),
221                          __builtin_return_address(1));
222         }
223         #endif
224         #endif
225         slab_grow(&ret->slab, buf, buflen);
226     }
227
228     ret->head = slab_alloc(&ret->slab);
229     assert(ret->head != NULL);
230     ret->head->slot = 0;
231     ret->head->space = nslots;
232     ret->head->next = NULL;
233
234     return SYS_ERR_OK;
235 }
236
237 errval_t single_slot_alloc_init(struct single_slot_allocator *ret,
238                                  cslot_t nslots, cslot_t *retslots)
239 {
240     errval_t err;
241
242     struct capref cap;
243     struct cnoderef cnode;
244     err = cnode_create(&cap, &cnode, nslots, &nslots);
245     if (err_is_fail(err)) {
246         return err_push(err, LIB_ERR_CNODE_CREATE);
247     }
248     size_t buflen = SINGLE_SLOT_ALLOC_BUFLEN(nslots);
249     void *buf = malloc(buflen);
250     if (!buf) {
251         return LIB_ERR_MALLOC_FAIL;
252     }
253
254     err = single_slot_alloc_init_raw(ret, cap, cnode, nslots, buf, buflen);
255     if (err_is_fail(err)) {
256         return err_push(err, LIB_ERR_SINGLE_SLOT_ALLOC_INIT_RAW);
257     }
258
259     if (retslots) {
260         *retslots = nslots;
261     }
262     return SYS_ERR_OK;
263 }