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