/* The ways of choosing a function, timed by harness.c.
   - Every kind has its own function (different constants, so they cannot be merged),
     and none may be inlined: what is measured is the choosing, not the work.
   - The one exception is the last way, which lets the compiler inline. */
#include "bench.h"

#define KIND(k, c)                                                              \
    [[gnu::noinline]] static uint64_t f##k(const struct obj *o)                 \
    { return o->x * (c) + (k); }                                                \
    static inline uint64_t g##k(const struct obj *o) { return o->x * (c) + (k); }
KIND(0, 3)  KIND(1, 5)  KIND(2, 7)  KIND(3, 11)
KIND(4, 13) KIND(5, 17) KIND(6, 19) KIND(7, 23)

[[gnu::noinline]] uint64_t other(const struct obj *o) { return o->x; }
const method fs[KMAX] = { f0, f1, f2, f3, f4, f5, f6, f7 };
const struct ops static_ops[KMAX] = {
    { f0, other }, { f1, other }, { f2, other }, { f3, other },
    { f4, other }, { f5, other }, { f6, other }, { f7, other },
};

#define EACH for (uint32_t r = 0; r < REPS; r++) for (uint32_t i = 0; i < N; i++)

uint64_t m_direct(void)          /* the baseline: one kind, a direct call */
{ uint64_t s = 0; EACH s += f0(&arena[i]); return s; }

uint64_t m_grouped(void)         /* grouped by kind (an index list per kind), direct */
{
    uint64_t s = 0;
    for (uint32_t r = 0; r < REPS; r++)
        for (uint32_t k = 0; k < kinds; k++) {
            const uint32_t *ix = by_kind[k];
            switch (k) {
#define GROUP(j) \
    case j: for (uint32_t i = 0; i < count[j]; i++) s += f##j(&arena[ix[i]]); break;
            GROUP(0) GROUP(1) GROUP(2) GROUP(3) GROUP(4) GROUP(5) GROUP(6) GROUP(7)
            }
        }
    return s;
}

uint64_t m_switch(void)          /* switch on the kind number */
{
    uint64_t s = 0;
    EACH {
        const struct obj *o = &arena[i];
        switch (o->kind) {
        case 0: s += f0(o); break; case 1: s += f1(o); break;
        case 2: s += f2(o); break; case 3: s += f3(o); break;
        case 4: s += f4(o); break; case 5: s += f5(o); break;
        case 6: s += f6(o); break; case 7: s += f7(o); break;
        }
    }
    return s;
}

uint64_t m_binary(void)          /* binary branches on the kind number, no table */
{
    uint64_t s = 0;
    EACH {
        const struct obj *o = &arena[i];
        uint32_t k = o->kind;
        if (k < 4) s += k < 2 ? (k < 1 ? f0(o) : f1(o)) : (k < 3 ? f2(o) : f3(o));
        else       s += k < 6 ? (k < 5 ? f4(o) : f5(o)) : (k < 7 ? f6(o) : f7(o));
    }
    return s;
}

uint64_t m_static(void)          /* a static const table */
{ uint64_t s = 0; EACH s += arena[i].sops->apply(&arena[i]); return s; }

uint64_t m_dynamic(void)         /* a table built at run time */
{ uint64_t s = 0; EACH s += arena[i].dops->apply(&arena[i]); return s; }

uint64_t m_fat(void)             /* a fat pointer */
{ uint64_t s = 0; EACH s += fats[i].ops->apply(fats[i].data); return s; }

/* ---- by selector: what Objective-C does, with and without caches ---- */
/* scan the list, then the parent's */
static method lookup_slow(const struct klass *c, uint32_t sel)
{
    for (; c; c = c->parent)
        for (uint32_t m = 0; m < c->n; m++)
            if (c->methods[m].sel == sel) return c->methods[m].fn;
    return nullptr;
}
/* the per-class cache first */
static method lookup_cached(struct klass *c, uint32_t sel)
{
    struct cache_entry *e = &c->cache[sel & 15];
    if (e->sel == sel) return e->fn;
    method m = lookup_slow(c, sel);
    *e = (struct cache_entry){ sel, m };
    return m;
}

uint64_t m_sel_slow(void)        /* by selector, no cache: scan the list to its end */
{ uint64_t s = 0; EACH s += lookup_slow(arena[i].cls, SEL_APPLY)(&arena[i]); return s; }

uint64_t m_sel_cache(void)       /* by selector, per-class cache */
{ uint64_t s = 0; EACH s += lookup_cached(arena[i].cls, SEL_APPLY)(&arena[i]); return s; }

uint64_t m_sel_ic(void)          /* by selector, one-entry inline cache at the call */
{
    uint64_t s = 0;
    struct { const struct klass *cls; method fn; } ic = {};
    EACH {
        struct klass *c = arena[i].cls;
        if (c != ic.cls) { ic.cls = c; ic.fn = lookup_slow(c, SEL_APPLY); }   /* miss */
        s += ic.fn(&arena[i]);
    }
    return s;
}

uint64_t m_sel_pic(void)         /* by selector, a four-entry polymorphic inline cache */
{
    uint64_t s = 0;
    struct { const struct klass *cls; method fn; } pic[4] = {};
    uint32_t next = 0;
    EACH {
        struct klass *c = arena[i].cls;
        method m;
        if      (pic[0].cls == c) m = pic[0].fn;
        else if (pic[1].cls == c) m = pic[1].fn;
        else if (pic[2].cls == c) m = pic[2].fn;
        else if (pic[3].cls == c) m = pic[3].fn;
        else {                                       /* miss: look up, replace one */
            m = lookup_slow(c, SEL_APPLY);
            pic[next].cls = c;
            pic[next].fn = m;
            next = (next + 1) & 3;
        }
        s += m(&arena[i]);
    }
    return s;
}

uint64_t m_inlined(void)         /* switch again, but the bodies may be inlined */
{
    uint64_t s = 0;
    EACH {
        const struct obj *o = &arena[i];
        switch (o->kind) {
        case 0: s += g0(o); break; case 1: s += g1(o); break;
        case 2: s += g2(o); break; case 3: s += g3(o); break;
        case 4: s += g4(o); break; case 5: s += g5(o); break;
        case 6: s += g6(o); break; case 7: s += g7(o); break;
        }
    }
    return s;
}

/* When the compiler knows the table, and when it does not --- the same shape_area,
   called from five places. run.sh checks each function's machine code for an
   indirect call. */
#include <stdlib.h>

struct shape;
struct shape_ops { double (*area)(const struct shape *); };
struct shape { const struct shape_ops *ops; double r; };

static double circle_area(const struct shape *s) { return 3.0 * s->r * s->r; }
static inline double shape_area(const struct shape *s) { return s->ops->area(s); }

static const struct shape_ops circle_ops = { circle_area };  /* a static const table */
static struct shape_ops quiet_ops = { circle_area };   /* no const, nobody changes it */
struct shape_ops open_ops = { circle_area };           /* visible to other files */
const struct shape_ops *built_ops;                     /* built at run time */

double known_object(double r)          /* object and table both visible here */
{
    struct shape s = { &circle_ops, r };
    return shape_area(&s);
}
double never_written(double r)         /* no const, yet nothing in this file writes it */
{
    struct shape s = { &quiet_ops, r };
    return shape_area(&s);
}
double visible_outside(double r)       /* another file may change it */
{
    struct shape s = { &open_ops, r };
    return shape_area(&s);
}
double built_at_run_time(double r)     /* the table is decided at run time */
{
    struct shape s = { built_ops, r };
    return shape_area(&s);
}
/* one static const table, but the object comes from outside */
double from_caller(const struct shape *s)
{
    return shape_area(s);
}

void build(void)
{
    struct shape_ops *t = malloc(sizeof *t);
    if (t) { *t = circle_ops; built_ops = t; }
}

/* Inline caches and polymorphic inline caches --- a cache at each call site.
   Smalltalk and JIT runtimes rewrite the calling machine code itself. C cannot
   rewrite its own code, so the cache is a static variable beside the call and
   only that call uses it.
   - One entry (IC): one "last class -> function".
   - Four entries (PIC): four of them. A miss replaces the entries in turn.
   - Megamorphic: once a full PIC misses, the site stops comparing and goes to
     the per-class cache.
   Each entry records the generation number, for the same reason as lookup.c in
   chapter 72: a method changed at run time must not stay in the cache. */
#include <stdio.h>

struct object;
typedef double (*imp)(const struct object *self);

struct method { unsigned sel; imp fn; };
struct entry { const struct class *cls; imp fn; unsigned epoch; };
struct class {
    const struct class *parent;
    struct method methods[2];
    unsigned n_methods;
    double factor;
    struct entry cache;                  /* per-class cache, one selector here */
};
struct object { struct class *isa; double size; };

enum { SEL_AREA = 1 };

static unsigned epoch = 1;               /* rises whenever a method changes */
static unsigned slow_lookups;

static imp lookup_slow(const struct class *c, unsigned sel)
{
    slow_lookups++;
    for (; c; c = c->parent)
        for (unsigned i = 0; i < c->n_methods; i++)
            if (c->methods[i].sel == sel) return c->methods[i].fn;
    return nullptr;
}
static imp lookup_class_cache(struct class *c, unsigned sel)
{
    if (c->cache.epoch != epoch)
        c->cache = (struct entry){ c, lookup_slow(c, sel), epoch };
    return c->cache.fn;
}

/* ---- the cache of one call site ---- */
/* No selector is stored: the message sent from one site is always the same. */
struct site {
    struct entry e[4];
    unsigned ways, next;                 /* entries in use (1 or 4), next to replace */
    bool megamorphic;
    unsigned sends, misses;
};

static double send_at(struct site *s, struct object *o, unsigned sel)
{
    s->sends++;
    if (s->megamorphic)                  /* stopped comparing: per-class cache */
        return lookup_class_cache(o->isa, sel)(o);
    for (unsigned i = 0; i < s->ways; i++)
        if (s->e[i].cls == o->isa && s->e[i].epoch == epoch)
            return s->e[i].fn(o);        /* hit: one comparison per entry, no lookup */
    s->misses++;
    if (s->ways > 1 && s->e[s->next].cls && s->e[s->next].epoch == epoch) {
        s->megamorphic = true;           /* full and missed: give up comparing */
        return lookup_class_cache(o->isa, sel)(o);
    }
    imp fn = lookup_slow(o->isa, sel);
    s->e[s->next] = (struct entry){ o->isa, fn, epoch };
    s->next = (s->next + 1) % s->ways;
    return fn(o);
}

static const char *state(const struct site *s)
{
    if (s->megamorphic) return "megamorphic";
    unsigned used = 0;
    for (unsigned i = 0; i < s->ways; i++) used += s->e[i].epoch == epoch;
    return used == 0 ? "empty" : used == 1 ? "monomorphic" : "polymorphic";
}
static void report(const char *label, struct site *s, double sum)
{
    printf("  %-12s sum %5g, %2u sends, %2u misses, %-11s (slow lookups %u)\n",
           label, sum, s->sends, s->misses, state(s), slow_lookups);
    s->sends = s->misses = 0;
    slow_lookups = 0;
}

/* Two call sites. Each block-scope static is the cache of the one call below it. */
static void total_area_ic(struct object *xs, size_t n)
{
    static struct site here = { .ways = 1 };   /* this call site's own cache */
    double sum = 0;
    for (size_t i = 0; i < n; i++) sum += send_at(&here, &xs[i], SEL_AREA);
    report("1-entry IC", &here, sum);
}
static void total_area_pic(struct object *xs, size_t n)
{
    static struct site here = { .ways = 4 };   /* and this one's */
    double sum = 0;
    for (size_t i = 0; i < n; i++) sum += send_at(&here, &xs[i], SEL_AREA);
    report("4-entry PIC", &here, sum);
}

/* ---- classes: every shape's area is factor x size x size ---- */
static double scaled_area(const struct object *self)
{ return self->isa->factor * self->size * self->size; }
static double circle_area(const struct object *self)
{ return 3 * self->size * self->size; }
static double circle_area_2(const struct object *self)      /* added at run time */
{ return 3.14 * self->size * self->size; }

static struct class shape = {
    .methods = { { SEL_AREA, scaled_area } }, .n_methods = 1, .factor = 1 };
static struct class circle = {
    .parent = &shape, .methods = { { SEL_AREA, circle_area } }, .n_methods = 1 };
#define KIND(var, f) static struct class var = { .parent = &shape, .factor = f }
KIND(square, 1); KIND(triangle, 0.5); KIND(hexagon, 2.5);
KIND(kite, 0.5); KIND(star, 4);

static void scene(const char *title, struct object *xs, size_t n)
{
    puts(title);
    total_area_ic(xs, n);
    total_area_pic(xs, n);
}

int main(void)
{
    struct object same[8], two[8], six[12];
    struct class *six_kinds[] = { &circle, &square, &triangle, &hexagon, &kite, &star };
    for (size_t i = 0; i < 8; i++) {
        same[i] = (struct object){ &circle, 1 };
        two[i] = (struct object){ i % 2 ? &square : &circle, 1 };
    }
    for (size_t i = 0; i < 12; i++) six[i] = (struct object){ six_kinds[i % 6], 1 };

    scene("one class only (8 circles):", same, 8);
    scene("two classes taking turns (circle, square, ...):", two, 8);
    scene("two classes again, after the first round:", two, 8);
    scene("six classes taking turns:", six, 12);

    puts("change Circle's area at run time (generation rises), then two classes:");
    circle.methods[0].fn = circle_area_2;
    epoch++;
    total_area_ic(two, 8);
    total_area_pic(two, 8);
    return 0;
}

#!/bin/sh
# The same benchmark (../bench) under two mitigations, each beside the build it
# should be compared with:
#   retpoline  GCC -mindirect-branch=thunk, Clang -mretpoline
#              (against plain -O2, which is ../bench)
#   CFI        Clang -flto -fvisibility=hidden -fsanitize=cfi-icall
#              (against the same LTO build without CFI, printed first)
# All four are compiler options, not C. A build the toolchain refuses is reported,
# not run.
set -u
cd "$(dirname "$0")"
tmp=$(mktemp -d)
trap 'rm -rf "$tmp"' EXIT INT TERM
pin=""
if command -v taskset >/dev/null 2>&1 && [ "$(nproc 2>/dev/null || echo 1)" -gt 2 ]; then
    pin="taskset -c 2"
fi
src="../bench/ways.c ../bench/harness.c"
w="-std=c23 -Wall -Wextra -Werror -O2"
lto="-flto -fvisibility=hidden -fuse-ld=lld"
shape() {   # did the compiler turn m_switch into a jump table (an indirect jump)?
    command -v objdump >/dev/null 2>&1 || return 0
    objdump -d --no-show-raw-insn "$1" |
        awk '/<m_switch>:/ { p = 1; next } /^$/ { p = 0 } p' > "$tmp/s.s"
    [ -s "$tmp/s.s" ] || return 0
    if grep -Eq 'jmp[a-z]* +\*|thunk|retpoline|[[:space:]]br[[:space:]]' "$tmp/s.s"; then
        echo "switch compiled to: a jump table (one indirect jump)"
    else
        echo "switch compiled to: a chain of compares (no indirect jump)"
    fi
}
run() {   # label, compiler, options...
    label=$1; cc=$2; shift 2
    echo "== $label"
    # shellcheck disable=SC2086
    if command -v "$cc" >/dev/null 2>&1 && $cc $w "$@" $src -o "$tmp/b" 2>/dev/null; then
        $pin "$tmp/b" short
        case $label in *retpoline*) shape "$tmp/b" ;; esac
    else
        echo "this toolchain cannot build it, skipped"
    fi
}
run "gcc -O2 -mindirect-branch=thunk (retpoline)" gcc -mindirect-branch=thunk
run "clang -O2 -mretpoline" clang -mretpoline
# shellcheck disable=SC2086
run "clang -O2 -flto (the control for CFI)" clang $lto
# shellcheck disable=SC2086
run "clang -O2 -flto -fsanitize=cfi-icall" clang $lto -fsanitize=cfi-icall

/* A table slot holds a function of the wrong type. In C that is undefined behaviour
   (6.3.2.3p8). An ordinary build just calls it; a Clang CFI build stops first. */
#include <stdio.h>

struct shape;
struct shape_ops { double (*area)(const struct shape *); };
struct shape { const struct shape_ops *ops; double r; };

static double circle_area(const struct shape *s) { return 3.0 * s->r * s->r; }
static long   count_lines(const char *text)          /* a function of another type */
{
    long n = 0;
    for (; text && *text; text++) n += *text == '\n';
    return n;
}

/* the cast through void (*)(void) avoids -Wcast-function-type --- it imitates
   the mistake no compiler catches */
static struct shape_ops ops = { circle_area };

int main(void)
{
    struct shape s = { &ops, 2.0 };
    printf("right slot: %.1f\n", s.ops->area(&s));
    fflush(stdout);
    ops.area = (double (*)(const struct shape *))(void (*)(void))count_lines;
    printf("wrong slot: ");
    fflush(stdout);
    double a = s.ops->area(&s);     /* what comes back is garbage --- not printed */
    (void)a;
    puts("the call went through --- nothing stopped it");
    return 0;
}