1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
|
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include "buddy.h"
static uint8_t MAGIC[MAGIC_COOKIE_BYTES];
struct free_list {
uint8_t magic[MAGIC_COOKIE_BYTES];
struct free_list *next;
struct free_list **pprev;
};
static struct free_list *(AVAIL[ADDRESS_BITS]);
static size_t ROOT_LOGSIZE;
static void *BASE;
// log2 of size rounded up (ceil) or down (!ceil) to the nearest power of 2
static size_t size2log(size_t size, int ceil) {
int bitcnt = 0;
for (int i = 0; size; i++) {
bitcnt += size & 1;
size >>= 1;
if (size) continue;
if (ceil) return (bitcnt > 1) ? (i + 1) : i;
return i;
}
return ceil ? 1 : 0;
}
void init_buddy(uint8_t *base, size_t size,
uint8_t magic[MAGIC_COOKIE_BYTES]) {
BASE = base;
size_t logsize = size2log(size, 0);
ROOT_LOGSIZE = logsize;
AVAIL[logsize] = (struct free_list *)base;
AVAIL[logsize]->next = 0;
AVAIL[logsize]->pprev = &(AVAIL[logsize]);
memcpy(MAGIC, magic, sizeof(MAGIC));
}
static struct free_list *buddy_of(struct free_list *block, size_t logsize) {
size_t virt_block = (size_t)block - (size_t)BASE;
size_t virt_buddy = virt_block ^ (1 << logsize);
return (void*)((uint8_t*)BASE + virt_buddy);
}
static int isfree(struct free_list *block) {
return !memcmp(block->magic, MAGIC, sizeof(MAGIC));
}
static void makefree(struct free_list *block) {
memcpy(block->magic, MAGIC, sizeof(MAGIC));
}
static struct free_list *pop(struct free_list *block) {
*(block->pprev) = block->next;
if (block->next) block->next->pprev = block->pprev;
return block;
}
static void push(struct free_list *block, size_t logsize) {
block->next = AVAIL[logsize];
if (block->next) block->next->pprev = &(block->next);
AVAIL[logsize] = block;
block->pprev = &(AVAIL[logsize]);
}
static void *_allocate(size_t logsize) {
if (logsize > ROOT_LOGSIZE) return 0;
if (AVAIL[logsize]) {
struct free_list *block = pop(AVAIL[logsize]);
memset(block, 0, sizeof(struct free_list));
return block;
}
struct free_list *parent = _allocate(logsize + 1);
struct free_list *buddy = buddy_of(parent, logsize);
// split @parent in half and place the buddy on the avail list.
memcpy(buddy->magic, MAGIC, sizeof(MAGIC));
push(buddy, logsize);
return parent;
}
void *allocate(size_t size) {
size = (size < sizeof(struct free_list)) ? sizeof(struct free_list) : size;
return _allocate(size2log(size, 1));
}
static void _liberate(struct free_list *block, size_t logsize) {
push(block, logsize);
if (logsize == ROOT_LOGSIZE) return;
struct free_list *buddy = buddy_of(block, logsize);
if (!isfree(buddy)) return;
// coalesce up!
struct free_list *smaller = (buddy < block) ? buddy : block;
struct free_list *bigger = (buddy < block) ? block : buddy;
pop(bigger);
memset(bigger, 0, sizeof(*bigger));
pop(smaller);
_liberate(smaller, logsize + 1);
}
void liberate(void *base, size_t size) {
struct free_list *block = base;
memset(block, 0, sizeof(*block));
makefree(block);
_liberate(block, size2log(size, 1));
}
void debug_buddy(void) {
for (size_t i = 0; i <= ROOT_LOGSIZE; i++) {
printf("Free blocks at size 2^%lu = %lu:\n", i, 1ul << i);
for (struct free_list *block = AVAIL[i]; block; block = block->next) {
printf("\t%p\n", block);
}
}
}
///////// "advanced features"
static struct free_list *rhs_child_of(struct free_list *block, size_t logsize) {
size_t virt_block = (size_t)block - (size_t)BASE;
size_t virt_child = virt_block | (1 << (logsize - 1));
return (void*)((uint8_t*)BASE + virt_buddy);
}
// NOTE: this method is perhaps more complicated than it needs to be because we
// take great pains to avoid writing to the region that is being preallocated
// (e.g., in case it is device MMIO).
int preallocate(void *start, size_t size) {
assert(size);
void *end = (void*)((uint8_t*)start + size);
// (1) check if BASE itself is a free node
struct free_list *parent = (void*)BASE;
size_t parent_logsize = ROOT_LOGSIZE;
while (!isfree(parent)) {
// pick the proper child and recurse
struct free_list *rhs_child = rhs_child_of(parent, parent_logsize);
if (rhs_child <= start) parent = rhs_child;
if (!parent_logsize--) return 0;
}
// parent is free!
void *parent_end = (void*)((uint8_t*)parent + (1 << parent_logsize));
// if the size has no chance of fitting, return 0.
if (parent_end < end) return 0;
// otherwise, split this parent
pop(parent, parent_logsize);
while (1) {
// check whether the child could fit it.
struct free_list *rhs_child = rhs_child_of(parent, parent_logsize);
struct free_list *next_child = (rhs_child <= start) parent : rhs_child;
void *child_end = (void*)((uint8_t*)next_child + (1 << (parent_logsize - 1)));
if (child_end < end) {
// the child *cannot* fit it, so allocate this parent.
return 1;
} else {
// the child *can* fit it, so split this parent into two children.
struct free_list *lhs_child = parent;
if (rhs_child <= start) {
// the lhs child will be free
makefree(lhs_child);
push(lhs_child, parent_logsize - 1);
parent = rhs_child;
} else {
// the rhs child will be free
makefree(rhs_child);
push(rhs_child, parent_logsize - 1);
parent = lhs_child;
}
}
parent_logsize--;
}
return 0;
}
void *reallocate(void *old, size_t old_size, size_t new_size) {
// if new_size < old_size, repeatedly split ourself. TODO: does this mess
// with fragmentation?
// otherwise, basically identical to preallocate, except what we want to
// allocate is roughly @old + old_size (with proper rounding to
// boundaries).
}
|
