7ec026ec39ffff9a7246c00c019eed5d585d8df4
[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_slot(struct single_slot_allocator *sca, cslot_t slot, struct thread_mutex *mutex)
59 {
60     thread_mutex_lock(mutex);
61
62     errval_t err = SYS_ERR_OK;
63
64     struct cnode_meta *walk = sca->head;
65     struct cnode_meta *prev = NULL;
66
67     // Entire cnode was allocated
68     if (!sca->head) {
69         sca->head = slab_alloc(&sca->slab);
70         sca->head->slot = slot;
71         sca->head->space = 1;
72         sca->head->next = NULL;
73         goto finish;
74     }
75
76     // Freeing one before head
77     if (slot + 1 == sca->head->slot) {
78         sca->head->slot = slot;
79         sca->head->space++;
80         goto finish;
81     }
82
83     // Freeing before head
84     if (slot < sca->head->slot) {
85         struct cnode_meta *new = slab_alloc(&sca->slab);
86         new->slot  = slot;
87         new->space = 1;
88         new->next  = sca->head;
89         sca->head  = new;
90         goto finish;
91     }
92
93     while (walk != NULL) {
94         // Freeing at the edge of walk
95         if (slot == walk->slot + walk->space) {
96             walk->space++;
97
98             // check if we can merge walk to next
99             struct cnode_meta *next = walk->next;
100             if (next && next->slot == walk->slot + walk->space) {
101                 walk->space += next->space;
102                 walk->next = next->next;
103                 slab_free(&sca->slab, next);
104             }
105
106             goto finish;
107         }
108         else if (slot < walk->slot + walk->space) {
109             err = LIB_ERR_SLOT_UNALLOCATED;
110             goto unlock;
111         }
112
113         // Freing just before walk->next
114         if (walk->next && slot + 1 == walk->next->slot) {
115             walk->next->slot = slot;
116             walk->next->space++;
117             goto finish;
118         }
119
120         // Freeing after walk and before walk->next
121         if (walk->next && slot < walk->next->slot) {
122             struct cnode_meta *new = walk->next;
123             walk->next = slab_alloc(&sca->slab);
124             walk->next->slot = slot;
125             walk->next->space = 1;
126             walk->next->next = new;
127             goto finish;
128         }
129         prev = walk;
130         walk = walk->next;
131     }
132
133     // Freeing after the list
134     prev->next = slab_alloc(&sca->slab);
135     prev->next->slot = slot;
136     prev->next->space = 1;
137     prev->next->next = NULL;
138
139  finish:
140     sca->a.space++;
141
142  unlock:
143     thread_mutex_unlock(mutex);
144     return err;
145 }
146
147 static errval_t sfree(struct slot_allocator *ca, struct capref cap)
148 {
149     struct single_slot_allocator *sca = (struct single_slot_allocator*)ca;
150     if (!cnodecmp(cap.cnode, sca->cnode)) {
151         return LIB_ERR_SLOT_ALLOC_WRONG_CNODE;
152     }
153
154     return free_slot(sca, cap.slot, &ca->mutex);
155 }
156
157 errval_t single_slot_alloc_init_raw(struct single_slot_allocator *ret,
158                                     struct capref cap, struct cnoderef cnode,
159                                     cslot_t nslots, void *buf, size_t buflen)
160 {
161     /* Generic part */
162     ret->a.alloc = salloc;
163     ret->a.free  = sfree;
164     ret->a.space = nslots;
165     ret->a.nslots = nslots;
166     thread_mutex_init(&ret->a.mutex);
167
168     /* Specific part */
169     ret->cap   = cap;
170     ret->cnode = cnode;
171
172     slab_init(&ret->slab, sizeof(struct cnode_meta), NULL);
173     if (buflen > 0) {
174         // check for callers that do not provide enough buffer space
175         #if !defined(NDEBUG)
176         //on arm, __builtin_return_address does not take arguments !=0
177         #if !defined(__arm__) && !defined(__aarch64__) 
178         size_t buflen_proper = SINGLE_SLOT_ALLOC_BUFLEN(nslots);
179         if (buflen != buflen_proper) {
180             debug_printf("******* FIXME: %s buflen=%zu != buflen_proper=%zu"
181                          "call stack: %p %p\n",
182                          __FUNCTION__, buflen, buflen_proper,
183                          __builtin_return_address(0),
184                          __builtin_return_address(1));
185         }
186         #endif
187         #endif
188         slab_grow(&ret->slab, buf, buflen);
189     }
190
191     ret->head = slab_alloc(&ret->slab);
192     assert(ret->head != NULL);
193     ret->head->slot = 0;
194     ret->head->space = nslots;
195     ret->head->next = NULL;
196
197     return SYS_ERR_OK;
198 }
199
200 errval_t single_slot_alloc_init(struct single_slot_allocator *ret,
201                                  cslot_t nslots, cslot_t *retslots)
202 {
203     errval_t err;
204
205     struct capref cap;
206     struct cnoderef cnode;
207     err = cnode_create(&cap, &cnode, nslots, &nslots);
208     if (err_is_fail(err)) {
209         return err_push(err, LIB_ERR_CNODE_CREATE);
210     }
211     size_t buflen = SINGLE_SLOT_ALLOC_BUFLEN(nslots);
212     void *buf = malloc(buflen);
213     if (!buf) {
214         return LIB_ERR_MALLOC_FAIL;
215     }
216
217     err = single_slot_alloc_init_raw(ret, cap, cnode, nslots, buf, buflen);
218     if (err_is_fail(err)) {
219         return err_push(err, LIB_ERR_SINGLE_SLOT_ALLOC_INIT_RAW);
220     }
221
222     if (retslots) {
223         *retslots = nslots;
224     }
225     return SYS_ERR_OK;
226 }