branch predictor eval

branch-predictor-eval.cpp

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>

extern "C" {
void make_guesses(bool *, size_t);
void dummy();
};

void __attribute__((noinline)) run_guesses(bool *guesses, size_t n, decltype(make_guesses) func) {
    func(guesses, n);
    asm volatile("");
}

int main(int argc, const char **argv) {
    if (argc < 2) {
        printf("Usage: %s <filename>\n", argv[0]);
        return 1;
    }

    // load guesses from guesses.bin
    FILE *f = fopen(argv[1], "rb");

    // get file size
    fseek(f, 0, SEEK_END);
    size_t file_size = ftell(f);
    fseek(f, 0, SEEK_SET);

    // file layout:
    // first 4 bytes are # of guess buffers
    // then for each buffer: 4 bytes for size, then that many bytes of bools

    size_t n_buffers;
    fread(&n_buffers, sizeof(size_t), 1, f);

    for (size_t i = 0; i < n_buffers; i++) {
        size_t buffer_size;
        fread(&buffer_size, sizeof(size_t), 1, f);
        bool *guesses = new bool[buffer_size];
        fread(guesses, sizeof(bool), buffer_size, f);

        // funky bit: to reset the CPU's branch predictor state, copy
        // make_guesses into new executable buffer note we're on mac, so use
        // MAP_JIT
        void *exec_buffer =
            mmap(nullptr, 4096, PROT_READ | PROT_WRITE | PROT_EXEC,
                 MAP_ANONYMOUS | MAP_PRIVATE | MAP_JIT, -1, 0);

        pthread_jit_write_protect_np(0);
        memcpy(exec_buffer, (void *)make_guesses, 4096);
        pthread_jit_write_protect_np(1);

        auto func = (void (*)(bool *, size_t))exec_buffer;
        run_guesses(guesses, buffer_size, func);

        delete[] guesses;

        // purposefully leak the exec_buffer to make sure it isn't reused and
        // somehow messes with our measurements
    }
}

branch-predictor-eval.s

.global _make_guesses
_make_guesses:
    ;; iterate over the x1 guesses in x0 with dummy branches to see how the predictor responds
    ;; x0 = pointer to array of guesses (1-byte each)
    ;; x1 = number of guesses
    mov x2, #0 ;; index
.loop:
    cmp x2, x1
    b.ge .done
    ldrb w3, [x0, x2] ;; load guess
    ;; make a dummy branch based on the guess (e.g. if guess is 0, branch to .taken, else branch to .not_taken)
    cbz w3, .taken
.not_taken:
    add x2, x2, #1
    b .loop
.taken:
    add x2, x2, #1
    b .loop
.done:
    ret

;; dummy for positionality
.global _dummy
_dummy:
    ret