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
|
#include <unistd.h>
#include <sys/fcntl.h>
#include "libimc.h"
#include "magic_buddy.h"
// #define verbose(...) printf(__VA_ARGS__)
#define verbose(...)
void get_random(uint8_t *dst, size_t count) {
int fd = open("/dev/urandom", O_RDONLY);
assert(count == read(fd, dst, count));
close(fd);
}
struct ll {
size_t data_size;
struct ll *next;
uint8_t data[];
};
// basically the simulation described by Knuth on pg 445
void check_main() {
size_t n_timesteps = 10;
size_t real_pool_size = 1024 * 1024 * 1024;
size_t pool_size = real_pool_size;
static void *raw_pool = 0;
static struct ll **time_to_dielist = 0;
if (!raw_pool)
raw_pool = malloc(pool_size + 55);
if (!time_to_dielist)
time_to_dielist = calloc(n_timesteps + 1, sizeof(struct ll *));
else
memset(time_to_dielist, 0, (n_timesteps + 1) * sizeof(struct ll *));
void *pool = raw_pool;
if (choose(2, 0)) pool_size += 11;
if (choose(2, 0)) pool = (void*)((uint8_t*)pool + 11);
struct buddy buddy1;
struct buddy buddy2;
struct buddy *curr_buddy = &buddy1;
uint8_t magic[MAGIC_COOKIE_BYTES];
get_random(magic, MAGIC_COOKIE_BYTES);
init_buddy(pool, pool_size, magic, curr_buddy);
void *redzone_start = 0;
void *redzone_end = 0;
if (choose(2, 0)) {
redzone_start = (uint8_t*)pool + 1365;
redzone_end = (uint8_t*)redzone_start + (1024 * 2);
verbose("Reserving %p -- %p\n", redzone_start, redzone_end);
assert(reserve(redzone_start,
(uint8_t*)redzone_end - (uint8_t*)redzone_start,
0, 0, curr_buddy));
}
size_t size_options[] = {1, 128, 1024, 5, 167, 10500};
const size_t n_size_options = sizeof(size_options) / sizeof(size_options[0]);
for (int t = 0; t < n_timesteps; t++) {
int which_buddy = choose(3, 0);
if (which_buddy == 1) {
move_buddy(&buddy1, curr_buddy);
curr_buddy = &buddy1;
} else if (which_buddy == 2) {
move_buddy(&buddy2, curr_buddy);
curr_buddy = &buddy2;
}
int shrink_grow_nop = choose(3, 0);
if (shrink_grow_nop == 0) {
if (shrink_buddy(pool_size / 2, curr_buddy))
pool_size = pool_size / 2;
assert(pool_size);
} else if (shrink_grow_nop == 1) {
if ((2 * pool_size) <= real_pool_size) {
pool_size *= 2;
grow_buddy(pool, pool_size, curr_buddy);
}
}
// free the regions at this timestep, and ensure its contents are good
for (struct ll *p = time_to_dielist[t]; p;) {
for (size_t i = 0; i < p->data_size; i++) {
verbose("Checking %p->data[%d] = %u versus %u\n",
p, i, (unsigned)p->data[i],
(unsigned)(uint8_t)p->data_size);
assert(p->data[i] == (uint8_t)p->data_size);
}
size_t action = choose(n_size_options + 2, 0);
if (action == n_size_options) {
// do a free!
struct ll *next = p->next;
liberate(p, p->data_size + sizeof(struct ll), curr_buddy);
p = next;
} else if (action == n_size_options + 1) {
// do a free, but with reallocate
struct ll *next = p->next;
p = reallocate(p, 0, p->data_size + sizeof(struct ll), curr_buddy);
assert(!p);
p = next;
} else {
// do a reallocate
struct ll *next = p->next;
size_t old_size = p->data_size + sizeof(struct ll);
p->data_size = size_options[action];
size_t new_size = p->data_size + sizeof(struct ll);
p = reallocate(p, new_size, old_size, curr_buddy);
assert(!(redzone_start <= (void*)p && (void*)p < redzone_end));
for (size_t i = 0; i < p->data_size; i++)
p->data[i] = (uint8_t)p->data_size;
int lifetime = choose(n_timesteps - t, 0) + 1;
p->next = time_to_dielist[t + lifetime];
time_to_dielist[t + lifetime] = p;
verbose("Reallocated %p, which should die at time %lu\n",
ll, t + lifetime);
p = next;
}
}
// try allocating a region
size_t size = size_options[choose(n_size_options, 0)];
struct ll *ll = allocate(size + sizeof(struct ll), curr_buddy);
if (!ll) continue;
verbose("Got allocation: %p\n", ll);
assert(!(redzone_start <= (void*)ll && (void*)ll < redzone_end));
assert((void*)ll >= pool);
assert((uint8_t*)ll + size + sizeof(struct ll)
<= (uint8_t*)pool + pool_size);
ll->data_size = size;
for (size_t i = 0; i < ll->data_size; i++) {
verbose("Writing %p->data[%d] = %u\n",
ll, i, (unsigned)(uint8_t)size);
ll->data[i] = (uint8_t)size;
}
// pick a death time
int lifetime = choose(n_timesteps - t, 0) + 1;
ll->next = time_to_dielist[t + lifetime];
time_to_dielist[t + lifetime] = ll;
verbose("Allocated %p, which should die at time %lu\n",
ll, t + lifetime);
}
}
|
