ROSS
buddy.c
Go to the documentation of this file.
1#include <stdlib.h>
2#include <stdio.h>
3#include <assert.h>
4#include <string.h>
5#include <ross.h>
6#include "buddy.h"
7
8/**
9 * @file buddy.c
10 * @brief Buddy-system memory allocator implementation
11 */
12
13#define BUDDY_BLOCK_ORDER 6 /**< @brief Minimum block order */
14
15static void *buddy_base_address = 0;
16
17/**
18 * Finds the next power of 2 or, if v is a power of 2, return that.
19 * From http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
20 * @param v Find a power of 2 >= v.
21 */
22unsigned int
23next_power2(unsigned int v)
24{
25 // We're not allocating chunks smaller than 2^BUDDY_BLOCK_ORDER bytes
26 if (v < (1 << BUDDY_BLOCK_ORDER)) {
27 return (1 << BUDDY_BLOCK_ORDER);
28 }
29
30 v--;
31 v |= v >> 1;
32 v |= v >> 2;
33 v |= v >> 4;
34 v |= v >> 8;
35 v |= v >> 16;
36 v++;
37
38 return v;
39}
40
42{
43 buddy_list_t *blt;
44 buddy_list_bucket_t *blbt = buddy_master;
45
46 while (1) {
47 unsigned int counter = 0;
48
49 printf("BLBT %p:\n", (void*)blbt);
50 printf(" Count: %d\n", blbt->count);
51 printf(" Order: %d\n", blbt->order);
52 if (blbt->is_valid == VALID)
53 printf(" Valid: YES\n");
54 else
55 printf(" Valid: NO\n");
56
57 printf(" Pointer Use Size\n");
58 LIST_FOREACH(blt, &blbt->ptr, next_freelist) {
59 counter++;
60 if (blt->use == FREE)
61 printf(" %11p%8s%16d\n", (void*)blt, "FREE", blt->size);
62 else
63 printf(" %11p%8s%16d\n", (void*)blt, "USED", blt->size);
64 assert(next_power2(blt->size) == (unsigned int) (1 << blbt->order));
65 }
66 printf("\n");
67 assert(counter == blbt->count && "Count is incorrect!");
68
69 blbt++;
70 if (blbt->is_valid == INVALID)
71 break;
72 }
73
74 return 1;
75}
76
77/**
78 * See if we can merge. If we can, see if we can merge again.
79 */
81{
82 int merge_count = 0;
83
84 assert(sizeof(unsigned long) >= sizeof(buddy_list_t*));
85
86 while (1) {
87 unsigned long pointer_as_long = (unsigned long)blt;
88 unsigned int size = blt->size + sizeof(buddy_list_t);
90 // Find the bucket we need
91 while (size > (unsigned int)(1 << blbt->order)) {
92 blbt++;
93 }
94 // We need to normalize for the "buddy formula" to work
95 pointer_as_long -= (unsigned long)buddy_base_address;
96 pointer_as_long ^= size;
97 pointer_as_long += (unsigned long)buddy_base_address;
98
99 // Our buddy has to meet some criteria
100 buddy_list_t *possible_buddy = (buddy_list_t*)pointer_as_long;
101 if (possible_buddy->use == FREE &&
102 possible_buddy->size == (size - sizeof(buddy_list_t))) {
103
104 if (merge_count) {
105 // If we've already merged at least once, then it's already
106 // in its bucket and we must remove it
107 blbt->count--;
108 LIST_REMOVE(blt, next_freelist);
109 }
110
111 assert(blbt->count && "bucket containing buddy has zero elements");
112 blbt->count--;
113 LIST_REMOVE(possible_buddy, next_freelist);
114 blbt++;
115 blbt->count++;
116
117 buddy_list_t *smallest_address = (blt < possible_buddy) ? blt : possible_buddy;
118 smallest_address->size = 2 * size - sizeof(buddy_list_t);
119 smallest_address->use = FREE;
120 LIST_INSERT_HEAD(&blbt->ptr, smallest_address, next_freelist);
121 memset(smallest_address+1, 0, smallest_address->size);
122 blt = smallest_address;
123 merge_count++;
124 }
125 else {
126 break;
127 }
128 }
129
130 return merge_count;
131}
132
133/**
134 * Free the given pointer (and coalesce it with its buddy if possible).
135 * @param ptr The pointer to free.
136 */
137void buddy_free(void *ptr)
138{
139 buddy_list_t *blt = (buddy_list_t *)ptr;
140 blt--;
141
142 // Now blt is is pointing to the correct address
143 unsigned int size = blt->size + sizeof(buddy_list_t);
144
145 // Find the bucket we need
147 while (size > (unsigned int)(1 << blbt->order)) {
148 blbt++;
149 }
150
151 if (blt->use != USED) {
152 buddy_list_t *iter;
153 tw_printf(TW_LOC, "warning: double free buddy");
154 // If it's free, it should be in the correct bucket so let's see
155 LIST_FOREACH(iter, &blbt->ptr, next_freelist) {
156 if (blt == iter) {
157 // Found it, great.
158 return;
159 }
160 }
161 assert(0 && "buddy with FREE status not in freelist");
162 }
163
164 unsigned int initial_count = blbt->count;
165 (void) initial_count; // quiet compiler when building Release
166
167 // If there are no entries here, we can't have a buddy
168 if (blbt->count == 0) {
169 blt->size = size - sizeof(buddy_list_t);
170 blt->use = FREE;
171 blbt->count++;
172 LIST_INSERT_HEAD(&blbt->ptr, blt, next_freelist);
173 memset(blt+1, 0, blt->size);
174 assert(blbt->count == initial_count + 1);
175 return;
176 }
177
178 if (buddy_try_merge(blt)) {
179 assert(initial_count > blbt->count);
180 return;
181 }
182
183 // Otherwise, just add it to the list
184 blt->size = size - sizeof(buddy_list_t);
185 blt->use = FREE;
186 blbt->count++;
187 LIST_INSERT_HEAD(&blbt->ptr, blt, next_freelist);
188 memset(blt+1, 0, blt->size);
189 assert(blbt->count == initial_count + 1);
190}
191
192/**
193 * This function assumes that a block of the specified order exists.
194 * @param bucket The bucket containing a block we intend to split.
195 */
196static
198{
199 assert(bucket->count && "Bucket contains no entries!");
200
201 // Remove an entry from this bucket and adjust the count
202 buddy_list_t *blt = LIST_FIRST(&bucket->ptr);
203 assert(blt && "LIST_FIRST returned NULL");
204 bucket->count--;
205 LIST_REMOVE(blt, next_freelist);
206
207 // Add two to the lower order bucket
208 bucket--;
209 bucket->count += 2;
210
211 // Update the BLTs
212 blt->use = FREE;
213 blt->size = (1 << bucket->order) - sizeof(buddy_list_t);
214
215 void *address = ((char *)blt) + (1 << bucket->order);
216 buddy_list_t *new_blt = (buddy_list_t *)address;
217
218 // new_blt->next_freelist = NULL;
219 new_blt->use = FREE;
220 new_blt->size = (1 << bucket->order) - sizeof(buddy_list_t);
221
222 assert(blt != new_blt);
223
224 LIST_INSERT_HEAD(&bucket->ptr, new_blt, next_freelist);
225 LIST_INSERT_HEAD(&bucket->ptr, blt, next_freelist);
226}
227
228/**
229 * Find the smallest block that will contain size and return it.
230 * Note this returns the memory allocated and usable, not the entire buffer.
231 * This may involve breaking up larger blocks.
232 * @param size The size of the data this allocation must be able to hold.
233 */
234void *buddy_alloc(unsigned size)
235{
236 char *ret = 0; // Return value
237
238 // We'll prepend a BLT before each allocation so add that now
239 size += sizeof(buddy_list_t);
240 size = next_power2(size);
241
242 // Find the bucket we need
244 while (size > (unsigned int)(1 << blbt->order)) {
245 blbt++;
246 if (blbt->is_valid == INVALID) {
247 // Error: we're out of bound for valid BLBTs
248 tw_error(TW_LOC, "Increase buddy-size");
249 }
250 }
251
252 if (blbt->count == 0) {
253 unsigned split_count = 0;
254
255 // If there are none, keep moving up to larger sizes
256 while (blbt->count == 0) {
257 blbt++;
258 if (blbt->is_valid == INVALID) {
259 // Error: we're out of bound for valid BLBTs
260 tw_error(TW_LOC, "Increase buddy-size");
261 }
262 split_count++;
263 }
264
265 while (split_count--) {
266 buddy_split(blbt--);
267 }
268 }
269
270 if (LIST_EMPTY(&blbt->ptr)) {
271 // This is bad -- they should have allocated more memory
272 tw_error(TW_LOC, "Increase buddy-size");
273 }
274 buddy_list_t *blt = LIST_FIRST(&blbt->ptr);
275 assert(blt && "LIST_FIRST returned NULL");
276 LIST_REMOVE(blt, next_freelist);
277 blt->use = USED;
278 blbt->count--;
279 ret = (char *)blt;
280 ret += sizeof(buddy_list_t);
281 return ret;
282}
283
284/**
285 * Pass in the power of two e.g., passing 5 will yield 2^5 = 32.
286 * @param power_of_two The largest "order" this table will support.
287 */
288buddy_list_bucket_t * create_buddy_table(unsigned int power_of_two)
289{
290 int i;
291 int size;
292 int list_count;
293 // void *memory;
294 buddy_list_bucket_t *bsystem;
295
296 // Don't create anything smaller than this
297 if (power_of_two < BUDDY_BLOCK_ORDER) {
298 power_of_two = BUDDY_BLOCK_ORDER;
299 }
300
301 list_count = power_of_two - BUDDY_BLOCK_ORDER + 1;
302
303 bsystem = (buddy_list_bucket_t *)tw_calloc(TW_LOC, "buddy system", list_count + 1, sizeof(buddy_list_bucket_t));
304 if (bsystem == NULL) {
305 return NULL;
306 }
307
308 for (i = 0; i < list_count; i++) {
309 bsystem[i].count = 0;
310 bsystem[i].order = i + BUDDY_BLOCK_ORDER;
311 bsystem[i].is_valid = VALID;
312 LIST_INIT(&(bsystem[i].ptr));
313 }
314 bsystem[i].is_valid = INVALID;
315
316 // Allocate the memory
317 size = 1 << power_of_two;
318 buddy_base_address = tw_calloc(TW_LOC, "buddy system", 1, size);
319 if (buddy_base_address == NULL) {
320 free(bsystem);
321 return NULL;
322 }
323
324 // Set up the primordial buddy block (2^power_of_two)
326 primordial->use = FREE;
327 primordial->size = (1 << power_of_two) - sizeof(buddy_list_t);
328
329 bsystem[list_count - 1].count = 1;
330 LIST_INSERT_HEAD(&bsystem[list_count - 1].ptr, primordial, next_freelist);
331
332 return bsystem;
333}
void * buddy_alloc(unsigned size)
Definition buddy.c:234
void buddy_free(void *ptr)
Definition buddy.c:137
static void buddy_split(buddy_list_bucket_t *bucket)
Definition buddy.c:197
buddy_list_bucket_t * create_buddy_table(unsigned int power_of_two)
Definition buddy.c:288
int buddy_try_merge(buddy_list_t *blt)
Definition buddy.c:80
static void * buddy_base_address
Definition buddy.c:15
#define BUDDY_BLOCK_ORDER
Minimum block order.
Definition buddy.c:13
unsigned int next_power2(unsigned int v)
Definition buddy.c:23
int dump_buddy_table(buddy_list_bucket_t *buddy_master)
Definition buddy.c:41
struct buddy_list buddy_list_t
@ VALID
Definition buddy.h:31
@ INVALID
Definition buddy.h:31
struct buddy_list_bucket buddy_list_bucket_t
@ USED
Definition buddy.h:12
@ FREE
Definition buddy.h:12
void * tw_calloc(const char *file, int line, const char *for_who, size_t e_sz, size_t n)
Definition tw-util.c:206
buddy_list_bucket_t * g_tw_buddy_master
Definition ross-global.c:40
void tw_error(const char *file, int line, const char *fmt,...)
Definition tw-util.c:77
void tw_printf(const char *file, int line, const char *fmt,...)
Definition tw-util.c:64
#define TW_LOC
Buddy-system memory allocator.
unsigned int count
Definition buddy.h:39
valid_t is_valid
Definition buddy.h:41
unsigned int order
Definition buddy.h:40
purpose_t use
Definition buddy.h:27
uint32_t size
Definition buddy.h:26