1 /* Copyright 2016 IBM Corp.
2 *
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
12 * implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 #include <assert.h>
17 #include <stdlib.h>
18 #include <string.h>
19 #include <stdio.h>
20
21 #include "buddy.h"
22
23 #define BUDDY_DEBUG
24 #undef BUDDY_VERBOSE
25
26 #ifdef BUDDY_VERBOSE
27 #define BUDDY_NOISE(fmt...) printf(fmt)
28 #else
29 #define BUDDY_NOISE(fmt...) do { } while(0)
30 #endif
31
buddy_map_size(struct buddy * b)32 static inline unsigned int buddy_map_size(struct buddy *b)
33 {
34 return 1u << (b->max_order + 1);
35 }
36
buddy_order_start(struct buddy * b,unsigned int order)37 static inline unsigned int buddy_order_start(struct buddy *b,
38 unsigned int order)
39 {
40 unsigned int level = b->max_order - order;
41
42 /* Starting bit of index for order */
43 return 1u << level;
44 }
45
buddy_index_to_node(struct buddy * b,unsigned int index,unsigned int order)46 static inline unsigned int buddy_index_to_node(struct buddy *b,
47 unsigned int index,
48 unsigned int order)
49 {
50 /* Ensure the index is a multiple of the order */
51 assert((index & ((1u << order) - 1)) == 0);
52
53 return buddy_order_start(b, order) + (index >> order);
54 }
55
buddy_node_to_index(struct buddy * b,unsigned int node,unsigned int order)56 static inline unsigned int buddy_node_to_index(struct buddy *b,
57 unsigned int node,
58 unsigned int order)
59 {
60 unsigned int start = buddy_order_start(b, order);
61
62 return (node - start) << order;
63 }
64
65 #ifdef BUDDY_DEBUG
buddy_check_alloc(struct buddy * b,unsigned int node)66 static void buddy_check_alloc(struct buddy *b, unsigned int node)
67 {
68 assert(bitmap_tst_bit(b->map, node));
69 }
70
buddy_check_alloc_down(struct buddy * b,unsigned int node)71 static void buddy_check_alloc_down(struct buddy *b, unsigned int node)
72 {
73 unsigned int i, count = 1;
74
75 while (node < buddy_map_size(b)) {
76 for (i = 0; i < count; i++)
77 buddy_check_alloc(b, node + i);
78
79 /* Down one level */
80 node <<= 1;
81 count <<= 1;
82 }
83 }
84 #else
buddy_check_alloc(struct buddy * b,unsigned int node)85 static inline void buddy_check_alloc(struct buddy *b, unsigned int node) {}
buddy_check_alloc_down(struct buddy * b,unsigned int node)86 static inline void buddy_check_alloc_down(struct buddy *b, unsigned int node) {}
87 #endif
88
buddy_alloc(struct buddy * b,unsigned int order)89 int buddy_alloc(struct buddy *b, unsigned int order)
90 {
91 unsigned int o;
92 int node, index;
93
94 BUDDY_NOISE("buddy_alloc(%d)\n", order);
95 /*
96 * Find the first order up the tree from our requested order that
97 * has at least one free node.
98 */
99 for (o = order; o <= b->max_order; o++) {
100 if (b->freecounts[o] > 0)
101 break;
102 }
103
104 /* Nothing found ? fail */
105 if (o > b->max_order) {
106 BUDDY_NOISE(" no free nodes !\n");
107 return -1;
108 }
109
110 BUDDY_NOISE(" %d free node(s) at order %d, bits %d(%d)\n",
111 b->freecounts[o], o,
112 buddy_order_start(b, o),
113 1u << (b->max_order - o));
114
115 /* Now find a free node */
116 node = bitmap_find_zero_bit(b->map, buddy_order_start(b, o),
117 1u << (b->max_order - o));
118
119 /* There should always be one */
120 assert(node >= 0);
121
122 /* Mark it allocated and decrease free count */
123 bitmap_set_bit(b->map, node);
124 b->freecounts[o]--;
125
126 /* We know that node was free which means all its children must have
127 * been marked "allocated". Double check.
128 */
129 buddy_check_alloc_down(b, node);
130
131 /* We have a node, we've marked it allocated, now we need to go down
132 * the tree until we reach "order" which is the order we need. For
133 * each level along the way, we mark the buddy free and leave the
134 * first child allocated.
135 */
136 while (o > order) {
137 /* Next level down */
138 o--;
139 node <<= 1;
140
141 BUDDY_NOISE(" order %d, using %d marking %d free\n",
142 o, node, node ^ 1);
143 bitmap_clr_bit(b->map, node ^ 1);
144 b->freecounts[o]++;
145 assert(bitmap_tst_bit(b->map, node));
146 }
147
148 index = buddy_node_to_index(b, node, order);
149
150 BUDDY_NOISE(" result is index %d (node %d)\n", index, node);
151
152 /* We have a node, convert it to an element number */
153 return index;
154 }
155
buddy_reserve(struct buddy * b,unsigned int index,unsigned int order)156 bool buddy_reserve(struct buddy *b, unsigned int index, unsigned int order)
157 {
158 unsigned int node, freenode, o;
159
160 assert(index < (1u << b->max_order));
161
162 BUDDY_NOISE("buddy_reserve(%d,%d)\n", index, order);
163
164 /* Get bit number for node */
165 node = buddy_index_to_node(b, index, order);
166
167 BUDDY_NOISE(" node=%d\n", node);
168
169 /* Find something free */
170 for (freenode = node, o = order; freenode > 0; freenode >>= 1, o++)
171 if (!bitmap_tst_bit(b->map, freenode))
172 break;
173
174 BUDDY_NOISE(" freenode=%d order %d\n", freenode, o);
175
176 /* Nothing free, error out */
177 if (!freenode)
178 return false;
179
180 /* We sit on a free node, mark it busy */
181 bitmap_set_bit(b->map, freenode);
182 assert(b->freecounts[o]);
183 b->freecounts[o]--;
184
185 /* We know that node was free which means all its children must have
186 * been marked "allocated". Double check.
187 */
188 buddy_check_alloc_down(b, freenode);
189
190 /* Reverse-walk the path and break down nodes */
191 while (o > order) {
192 /* Next level down */
193 o--;
194 freenode <<= 1;
195
196 /* Find the right one on the path to node */
197 if (node & (1u << (o - order)))
198 freenode++;
199
200 BUDDY_NOISE(" order %d, using %d marking %d free\n",
201 o, freenode, freenode ^ 1);
202 bitmap_clr_bit(b->map, freenode ^ 1);
203 b->freecounts[o]++;
204 assert(bitmap_tst_bit(b->map, node));
205 }
206 assert(node == freenode);
207
208 return true;
209 }
210
buddy_free(struct buddy * b,unsigned int index,unsigned int order)211 void buddy_free(struct buddy *b, unsigned int index, unsigned int order)
212 {
213 unsigned int node;
214
215 assert(index < (1u << b->max_order));
216
217 BUDDY_NOISE("buddy_free(%d,%d)\n", index, order);
218
219 /* Get bit number for node */
220 node = buddy_index_to_node(b, index, order);
221
222 BUDDY_NOISE(" node=%d\n", node);
223
224 /* We assume that anything freed was fully allocated, ie,
225 * there is no child node of that allocation index/order
226 * that is already free.
227 *
228 * BUDDY_DEBUG will verify it at the cost of performances
229 */
230 buddy_check_alloc_down(b, node);
231
232 /* Propagate if buddy is free */
233 while (order < b->max_order && !bitmap_tst_bit(b->map, node ^ 1)) {
234 BUDDY_NOISE(" order %d node %d buddy %d free, propagating\n",
235 order, node, node ^ 1);
236
237 /* Mark buddy busy (we are already marked busy) */
238 bitmap_set_bit(b->map, node ^ 1);
239
240 /* Reduce free count */
241 assert(b->freecounts[order] > 0);
242 b->freecounts[order]--;
243
244 /* Get parent */
245 node >>= 1;
246 order++;
247
248 /* It must be busy already ! */
249 buddy_check_alloc(b, node);
250
251 BUDDY_NOISE(" testing order %d node %d\n", order, node ^ 1);
252 }
253
254 /* No more coalescing, mark it free */
255 bitmap_clr_bit(b->map, node);
256
257 /* Increase the freelist count for that level */
258 b->freecounts[order]++;
259
260 BUDDY_NOISE(" free count at order %d is %d\n",
261 order, b->freecounts[order]);
262 }
263
buddy_reset(struct buddy * b)264 void buddy_reset(struct buddy *b)
265 {
266 unsigned int bsize = BITMAP_BYTES(1u << (b->max_order + 1));
267
268 BUDDY_NOISE("buddy_reset()\n");
269 /* We fill the bitmap with 1's to make it completely "busy" */
270 memset(b->map, 0xff, bsize);
271 memset(b->freecounts, 0, sizeof(b->freecounts));
272
273 /* We mark the root of the tree free, this is entry 1 as entry 0
274 * is unused.
275 */
276 buddy_free(b, 0, b->max_order);
277 }
278
buddy_create(unsigned int max_order)279 struct buddy *buddy_create(unsigned int max_order)
280 {
281 struct buddy *b;
282 unsigned int bsize;
283
284 assert(max_order <= BUDDY_MAX_ORDER);
285
286 bsize = BITMAP_BYTES(1u << (max_order + 1));
287
288 b = zalloc(sizeof(struct buddy) + bsize);
289 if (!b)
290 return NULL;
291 b->max_order = max_order;
292
293 BUDDY_NOISE("Map @%p, size: %d bytes\n", b->map, bsize);
294
295 buddy_reset(b);
296
297 return b;
298 }
299
buddy_destroy(struct buddy * b)300 void buddy_destroy(struct buddy *b)
301 {
302 free(b);
303 }
304
305