Libimc dumpHEADmaster

1 files changed, 286 insertions, 0 deletions

diff --git a/libimc/worker.c b/libimc/worker.c
new file mode 100644
index 0000000..d4d57b7
--- /dev/null
+++ b/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();
+}