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
|
#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 pool_size = 1024 * 1024 * 1024;
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 buddy;
uint8_t magic[MAGIC_COOKIE_BYTES];
get_random(magic, MAGIC_COOKIE_BYTES);
init_buddy(pool, pool_size, magic, &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++) {
// 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), &buddy);
p = next;
} else if (action == n_size_options + 1) {
// do a free, but with reallocate
struct ll *next = p->next;
p = reallocate(p, p->data_size + sizeof(struct ll), 0, &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, old_size, new_size, &buddy);
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), &buddy);
if (!ll) continue;
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);
}
}
|
