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
|
#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);
}
}
}
|
