diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | Makefile | 9 | ||||
| -rw-r--r-- | README | 18 | ||||
| -rw-r--r-- | examples/main.c | 2 | ||||
| -rw-r--r-- | imc/checker.c | 81 | ||||
| -rw-r--r-- | imc/libimc/README | 1 | ||||
| -rw-r--r-- | imc/libimc/_libimc.h | 94 | ||||
| -rw-r--r-- | imc/libimc/libimc.h | 18 | ||||
| -rw-r--r-- | imc/libimc/master.c | 180 | ||||
| -rw-r--r-- | imc/libimc/worker.c | 286 | ||||
| -rw-r--r-- | magic_buddy/magic_buddy.c | 2 | ||||
| -rw-r--r-- | magic_buddy/magic_buddy.h (renamed from magic_buddy/buddy.h) | 0 |
12 files changed, 689 insertions, 3 deletions
@@ -1,3 +1,4 @@ .*.sw* .sw* build +perf.* @@ -5,11 +5,18 @@ CFLAGS += -O3 CFLAGS += -I./magic_buddy # CFLAGS += -fsanitize=address -all: build/examples/main +all: build/examples/main build/imc/checker build/examples/%: examples/%.c magic_buddy/magic_buddy.c @ mkdir -p $(dir $@) $(CC) $(CFLAGS) $^ -o $@ +IMCFLAGS += -I./imc/libimc +IMCFLAGS += -DN_WORKERS=32 +IMCFLAGS += -DREPORT_FREQ=5 +build/imc/%: imc/%.c magic_buddy/magic_buddy.c imc/libimc/master.c imc/libimc/worker.c + @ mkdir -p $(dir $@) + $(CC) $(CFLAGS) $(IMCFLAGS) $^ -o $@ + clean: rm -rf build @@ -15,6 +15,9 @@ Benefits are: 4. Support for realloc and reserving subregions (e.g., device MMIO addresses). + 5. Core functionality is reasonably well-tested with an exhaustive + implementation model checker. + Caveats are: 1. The minimum allocation size is nontrivial, approximately 64 bytes @@ -52,6 +55,21 @@ The only sources of memory overhead are: But it retains the nice property of buddy allocators that liberation is linear in the computer's address size. +### Model Checking +The imc/ directory includes code to "exhaustively fuzz" the allocator. The +basic approach is based on the EXPLODE paper by Yang, Sar, and Engler. + +Current status of the test harness(es): + + - [X] init_buddy + - [X] allocate + - [X] liberate + - [ ] reallocate + - [ ] reserve + - [ ] grow_buddy + - [ ] shrink_buddy + - [ ] move_buddy + ### Usage Usage example in main.c. diff --git a/examples/main.c b/examples/main.c index a288f1c..bdc5c24 100644 --- a/examples/main.c +++ b/examples/main.c @@ -1,4 +1,4 @@ -#include "buddy.h" +#include "magic_buddy.h" #include <stdlib.h> #include <string.h> #include <fcntl.h> diff --git a/imc/checker.c b/imc/checker.c new file mode 100644 index 0000000..d3f09cc --- /dev/null +++ b/imc/checker.c @@ -0,0 +1,81 @@ +#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); + } + struct ll *next = p->next; + liberate(p, p->data_size + sizeof(struct ll), &buddy); + 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); + } +} diff --git a/imc/libimc/README b/imc/libimc/README new file mode 100644 index 0000000..a2eb083 --- /dev/null +++ b/imc/libimc/README @@ -0,0 +1 @@ +See parent README. diff --git a/imc/libimc/_libimc.h b/imc/libimc/_libimc.h new file mode 100644 index 0000000..3cf4dd2 --- /dev/null +++ b/imc/libimc/_libimc.h @@ -0,0 +1,94 @@ +#pragma once + +#define _GNU_SOURCE +#include <fcntl.h> +#include <unistd.h> +#include <errno.h> +#include "libimc.h" + +// #define verbose(...) printf(__VA_ARGS__) +#define verbose(...) + +extern int MASTER2WORKER_RD[N_WORKERS]; +extern int MASTER2WORKER_WR[N_WORKERS]; +extern int WORKER2MASTER_RD[N_WORKERS]; +extern int WORKER2MASTER_WR[N_WORKERS]; + +extern void launch_worker(unsigned int i); +extern void worker_replay(char *path); + +enum message_type { + MSG_NONE, + + // Worker -> Master + MSG_CAN_I_DIE, + MSG_DID_SPLIT, + MSG_NO_SPLIT, + MSG_PROGRESS, + + // Master -> Worker + MSG_PLEASE_SPLIT, + MSG_OK_DIE, + MSG_NO_DIE, +}; + +struct message { + enum message_type message_type; + int new_id; + int pid; + + size_t n_branches; + size_t n_bugs; +}; + +static void tell_pipe(int fd, uint8_t *ptr, size_t n) { + while (n) { + ssize_t n_sent = write(fd, ptr, n); + if (n_sent == -1 && (errno == EAGAIN || errno == EWOULDBLOCK)) + n_sent = 0; + assert(n_sent >= 0); + ptr += n_sent; + n -= n_sent; + } +} + +static void hear_pipe(int fd, uint8_t *ptr, size_t n) { + int any = 0; + while (n) { + ssize_t n_read = read(fd, ptr, n); + if (n_read == -1 && (errno == EAGAIN || errno == EWOULDBLOCK)) + n_read = 0; + assert(n_read >= 0); + ptr += n_read; + n -= n_read; + if (!any && !n_read) return; + any = 1; + } +} + +static void clear_pipe(int fd) { + uint8_t byte; + while (read(fd, &byte, 1) == 1); +} + +static void tell_worker(struct message message, int idx) { + tell_pipe(MASTER2WORKER_WR[idx], (uint8_t*)&message, sizeof(message)); +} + +static void tell_master(struct message message, int idx) { + struct message *msg = calloc(1, sizeof(message)); + *msg = message; + tell_pipe(WORKER2MASTER_WR[idx], (uint8_t*)msg, sizeof(message)); +} + +static struct message hear_worker(int idx) { + struct message message = {0}; + hear_pipe(WORKER2MASTER_RD[idx], (uint8_t*)&message, sizeof(message)); + return message; +} + +static struct message hear_master(int idx) { + struct message message = {0}; + hear_pipe(MASTER2WORKER_RD[idx], (uint8_t*)&message, sizeof(message)); + return message; +} diff --git a/imc/libimc/libimc.h b/imc/libimc/libimc.h new file mode 100644 index 0000000..8777883 --- /dev/null +++ b/imc/libimc/libimc.h @@ -0,0 +1,18 @@ +#pragma once + +#include <stdint.h> +#include <stdio.h> +#include <assert.h> +#include <string.h> +#include <stdlib.h> +#include <stddef.h> + +typedef uint64_t choice_t; +typedef uint64_t hash_t; + +choice_t choose(choice_t n, hash_t hash); +void report_error(); +void check_exit_normal(); +extern void check_main(); + +void register_resetter(void (*resetter)(void)); diff --git a/imc/libimc/master.c b/imc/libimc/master.c new file mode 100644 index 0000000..6d48b28 --- /dev/null +++ b/imc/libimc/master.c @@ -0,0 +1,180 @@ +#include "_libimc.h" +#include <stdio.h> +#include <time.h> +#include <assert.h> +#include <string.h> +#include <stdlib.h> +#include <stddef.h> +#include <unistd.h> +#include <signal.h> +#include <sys/wait.h> +#include <sys/prctl.h> + +int MASTER2WORKER_RD[N_WORKERS]; +int MASTER2WORKER_WR[N_WORKERS]; +int WORKER2MASTER_RD[N_WORKERS]; +int WORKER2MASTER_WR[N_WORKERS]; + +static size_t N_BRANCHES[N_WORKERS]; +static size_t N_BUGS[N_WORKERS]; +void handle_progress(struct message message, int worker_id) { + N_BRANCHES[worker_id] += message.n_branches; + N_BUGS[worker_id] += message.n_bugs; +} + +void print_progress(void) { + size_t total_branches = 0, total_bugs = 0; + printf("# branches:"); + for (int i = 0; i < N_WORKERS; i++) { + printf(" %lu", N_BRANCHES[i]); + total_branches += N_BRANCHES[i]; + } + printf("\n"); + printf("# bugs:"); + for (int i = 0; i < N_WORKERS; i++) { + printf(" %lu", N_BUGS[i]); + total_bugs += N_BUGS[i]; + } + printf("\n"); + printf("TOTAL branches: %lu; bugs: %lu\n", total_branches, total_bugs); +} + +void launch_master() { + // make a bugs directory + system("mkdir -p bugs"); + system("rm bugs/*"); + + assert(!prctl(PR_SET_CHILD_SUBREAPER, 1, 0, 0, 0)); + + // set up the control pipes + for (int i = 0; i < N_WORKERS; i++) { + int ends[2]; + pipe2(ends, O_NONBLOCK); + MASTER2WORKER_RD[i] = ends[0]; + MASTER2WORKER_WR[i] = ends[1]; + pipe2(ends, O_NONBLOCK); + WORKER2MASTER_RD[i] = ends[0]; + WORKER2MASTER_WR[i] = ends[1]; + } + + // 0 -> dead, 1 -> alive, -1 -> waiting on it to die + int worker_alive[N_WORKERS] = {0}; + // only guaranteed to be up-to-date for workers with worker_alive[i] == -1 + int worker_pid[N_WORKERS] = {0}; + size_t dead_count = 0; + + // launch an initial worker + if (!fork()) { + launch_worker(0); + exit(0); + } + + worker_alive[0] = 1; + while (1) { + static time_t last_time = 0; + if ((time(0) - last_time) > 1) { + last_time = time(0); + print_progress(); + } + + // First: handle any workers that want to die + for (int i = 0; i < N_WORKERS; i++) { + if (!worker_alive[i]) continue; + if (worker_alive[i] == -1) { + if (waitpid(worker_pid[i], NULL, WNOHANG)) { + worker_alive[i] = 0; + clear_pipe(MASTER2WORKER_RD[i]); + clear_pipe(WORKER2MASTER_RD[i]); + } + continue; + } + + struct message message = hear_worker(i); + switch (message.message_type) { + case MSG_CAN_I_DIE: + worker_alive[i] = -1; + worker_pid[i] = message.pid; + verbose("Telling worker %d (%d) they can die\n", i, message.pid); + tell_worker((struct message){MSG_OK_DIE, 0}, i); + break; + + case MSG_PROGRESS: + handle_progress(message, i); + break; + + case MSG_NONE: + break; + + default: + assert(!"Bad message!"); + break; + } + } + + // Second: if we have empty slots, ask a worker to split. + int n_alive = 0, fill_slot = 0; + for (int i = 0; i < N_WORKERS; i++) { + n_alive += (worker_alive[i] != 0); + if (!worker_alive[i]) fill_slot = i; + } + if (n_alive == 0) break; + if (n_alive == N_WORKERS) continue; + + int which = rand() % n_alive; + for (int i = 0; i < N_WORKERS; i++) { + if (!worker_alive[i]) continue; + if (which--) continue; + if (worker_alive[i] == -1) continue; + + verbose("Requesting a split of %d -> %d\n", i, fill_slot); + tell_worker((struct message){ + .message_type = MSG_PLEASE_SPLIT, + .new_id = fill_slot + }, i); + + while (1) { + struct message reply = hear_worker(i); + switch (reply.message_type) { + case MSG_CAN_I_DIE: + verbose("Telling worker %d not to die, because we want to split\n"); + tell_worker((struct message){MSG_NO_DIE}, i); + break; + + case MSG_DID_SPLIT: + worker_alive[fill_slot] = 1; + waitpid(reply.pid, NULL, 0); + goto finish_split; + + case MSG_NO_SPLIT: + goto finish_split; + + case MSG_PROGRESS: + handle_progress(reply, i); + break; + + case MSG_NONE: + break; + + default: + printf("Unknown message %d!\n", reply.message_type); + break; + } + } + +finish_split: break; + } + } + + printf("Done with exhaustive search.\n"); + print_progress(); +} + +int main(int argc, char **argv) { + if (argc > 1) { + assert(argc == 2); + worker_replay(argv[1]); + } else { + launch_master(); + } + return 0; +} diff --git a/imc/libimc/worker.c b/imc/libimc/worker.c new file mode 100644 index 0000000..d4d57b7 --- /dev/null +++ b/imc/libimc/worker.c @@ -0,0 +1,286 @@ +#include "_libimc.h" +#include <stdio.h> +#include <assert.h> +#include <string.h> +#include <stdlib.h> +#include <stddef.h> +#include <unistd.h> +#include <setjmp.h> +#include <signal.h> +#include <time.h> + +static int IS_REPLAY; +static size_t WORKER_I; +static size_t N_BRANCHES, N_BUGS; +static void send_progress(void) { + tell_master((struct message){ + .message_type = MSG_PROGRESS, + .n_branches = N_BRANCHES, + .n_bugs = N_BUGS + }, WORKER_I); + N_BRANCHES = N_BUGS = 0; +} + +struct resetter { + void (*fn)(void); + struct resetter *next; +}; +static struct resetter *RESETTERS; +void register_resetter(void (*fn)(void)) { + for (struct resetter *r = RESETTERS; r; r = r->next) + if (r->fn == fn) + return; + struct resetter *resetter = malloc(sizeof(struct resetter)); + resetter->fn = fn; + resetter->next = RESETTERS; + RESETTERS = resetter; +} + +// The worker keeps track of a search tree. Each node in the tree contains: +// +// (0) The specific option that was chosen at that node +// (1) An array of the choices we have explored there so far, each one +// associated with a specific child node. +// (2) The choice argument, i.e., how many children it has +// +// The search itself is a simple depth-first search. Once we explore all +// children of a node, we can free it. + +// at each 'choose', we look at the current node's 'pos'. +struct tree_node { + choice_t choice; + // @n_children == 0 means this node hasn't been explored yet. + // note we auto-handle choose(1), so n_children > 2 if it's > 0. + choice_t n_children; + + // if @n_children > 0, @pos should always point to a proper child in + // @children. + choice_t pos; + struct tree_node *children; + struct tree_node *parent; +}; + +struct tree_node *ROOT, *NODE; + +choice_t choose(choice_t n, hash_t hash) { + if (n == 1) return 0; + + if (!NODE) { + // this is the first choice; give it a node + ROOT = NODE = calloc(1, sizeof(struct tree_node)); + } + assert(ROOT); + + if (NODE->n_children) { + NODE = NODE->children + NODE->pos; + return NODE->choice; + } + + // this node is unexplored + NODE->n_children = n; + NODE->children = calloc(n, sizeof(NODE->children[0])); + + choice_t *options = calloc(n, sizeof(options)); + + for (choice_t i = 0; i < n; i++) options[i] = i; + for (choice_t i = 0; i < n; i++) { + size_t swap_with = i + (rand() % (n - i)); + choice_t tmp = options[i]; + options[i] = options[swap_with]; + options[swap_with] = tmp; + } + + for (int i = 0; i < n; i++) { + NODE->children[i].choice = options[i]; + NODE->children[i].parent = NODE; + } + + NODE->pos = 0; + + return choose(n, hash); +} + +static void search_increment(void) { + // finish off this branch + while (1) { + struct tree_node *parent = NODE->parent; + if (!parent) { + send_progress(); + + struct message death_msg = (struct message){ + .message_type = MSG_CAN_I_DIE, + .pid = getpid(), + }; + verbose("%d (%d) trying to die.\n", WORKER_I, getpid()); + tell_master(death_msg, WORKER_I); + while (1) { + struct message message = hear_master(WORKER_I); + switch (message.message_type) { + case MSG_NONE: break; + case MSG_PLEASE_SPLIT: + verbose("%d was asked to split\n", WORKER_I); + tell_master((struct message){MSG_NO_SPLIT}, WORKER_I); + tell_master(death_msg, WORKER_I); + break; + case MSG_OK_DIE: + verbose("%d gets to die.\n", WORKER_I); + exit(0); + break; + case MSG_NO_DIE: + verbose("%d can't die yet.\n", WORKER_I); + break; + default: + printf("While trying to die, %d got unknown message type %d\n", + WORKER_I, message.message_type); + break; + } + } + assert(!"Shouldn't reach here\n"); + } + + parent->pos++; + if (parent->pos < parent->n_children) break; + + free(parent->children); + NODE = parent; + } + NODE = ROOT; +} + +static void try_split(struct message message) { + struct tree_node *node = ROOT; + while (node) { + if (!node->n_children || node->pos == (node->n_children - 1)) { + node = node->children + node->pos; + continue; + } + + send_progress(); + int pid = getpid(); + if (fork()) { // parent + if (fork()) { + // let the parent reap me + exit(0); + } else { + node->n_children--; + tell_master((struct message){ + .message_type = MSG_DID_SPLIT, + .pid = pid, + }, WORKER_I); + } + } else { // child + WORKER_I = message.new_id; + node->pos = node->n_children - 1; + assert(node->pos < node->n_children); + } + return; + } + tell_master((struct message){MSG_NO_SPLIT}, WORKER_I); +} + +static jmp_buf RESET_JMP; + +void report_error() { + if (IS_REPLAY) { + fprintf(stderr, "Done with replay!\n"); + siglongjmp(RESET_JMP, 1); + } + + N_BUGS++; + + char tmpname[128]; + strcpy(tmpname, "bugs/XXXXXX"); + mkstemp(tmpname); + FILE *f = fopen(tmpname, "w"); + + struct tree_node *node = ROOT; + while (node) { + fprintf(f, "%lu\n", node->choice); + node = node->children + node->pos; + } + + fclose(f); + + fprintf(stderr, "Error written to %s\n", tmpname); + + check_exit_normal(); +} + +void check_exit_normal() { + if (IS_REPLAY) { + fprintf(stderr, "Replay finished with normal exit.\n"); + siglongjmp(RESET_JMP, 1); + } + + N_BRANCHES++; + if ((N_BRANCHES + 1) % REPORT_FREQ == 0) + send_progress(); + siglongjmp(RESET_JMP, 1); +} + +static void sighandler(int which) { + printf("Got signal: %d\n", which); + report_error(); +} + +void launch_worker(unsigned int i) { + WORKER_I = i; + srand(i + 24); + + // (0) set up signal handlers + struct sigaction action; + action.sa_handler = sighandler; + sigemptyset(&(action.sa_mask)); + action.sa_flags = 0; + assert(!sigaction(SIGABRT, &action, 0)); + assert(!sigaction(SIGSEGV, &action, 0)); + + // (1) set a setjmp for resetting the search + if (sigsetjmp(RESET_JMP, 1)) search_increment(); + for (struct resetter *r = RESETTERS; r; r = r->next) + r->fn(); + + // (1b) check for commands + struct message message = hear_master(WORKER_I); + switch (message.message_type) { + case MSG_NONE: + break; + + case MSG_PLEASE_SPLIT: + try_split(message); + break; + + default: + printf("!!!!!!!!!!!!!!! In the main loop, %d (%d) got unknown message type %d\n", WORKER_I, getpid(), message.message_type); + break; + } + + // (2) start the program + check_main(); + + // (3) trigger a reset + check_exit_normal(); +} + +void worker_replay(char *path) { + if (sigsetjmp(RESET_JMP, 1)) return; + IS_REPLAY = 1; + + FILE *f = fopen(path, "r"); + assert(f); + NODE = ROOT = calloc(1, sizeof(*ROOT)); + while (1) { + size_t choice = 0; + if (fscanf(f, " %lu", &choice) != 1) break; + + NODE->n_children = 2; + NODE->children = calloc(2, sizeof(NODE->children[0])); + NODE->children[0].choice = choice; + NODE->children[0].parent = NODE; + + NODE = NODE->children; + } + NODE = ROOT->children; + check_main(); + check_exit_normal(); +} diff --git a/magic_buddy/magic_buddy.c b/magic_buddy/magic_buddy.c index 80bc069..c6283d8 100644 --- a/magic_buddy/magic_buddy.c +++ b/magic_buddy/magic_buddy.c @@ -1,7 +1,7 @@ #include <stdio.h> #include <string.h> #include <assert.h> -#include "buddy.h" +#include "magic_buddy.h" struct free_block { struct free_block *next; diff --git a/magic_buddy/buddy.h b/magic_buddy/magic_buddy.h index c8778d6..c8778d6 100644 --- a/magic_buddy/buddy.h +++ b/magic_buddy/magic_buddy.h |