无锁栈：Treiber 栈与指数退避

typedef struct Node {
    int val;
    struct Node *next;
} Node;

typedef struct {
    Node *top;
    pthread_mutex_t lock;
} LockedStack;

void locked_push(LockedStack *s, int val) {
    Node *n = malloc(sizeof(Node));
    n->val = val;
    pthread_mutex_lock(&s->lock);
    n->next = s->top;
    s->top = n;
    pthread_mutex_unlock(&s->lock);
}

int locked_pop(LockedStack *s, int *out) {
    pthread_mutex_lock(&s->lock);
    if (s->top == NULL) {
        pthread_mutex_unlock(&s->lock);
        return 0;
    }
    Node *old = s->top;
    s->top = old->next;
    *out = old->val;
    pthread_mutex_unlock(&s->lock);
    free(old);
    return 1;
}

// 伪代码：以下操作由硬件原子完成
bool CAS(T *ptr, T *expected, T desired) {
    if (*ptr == *expected) {
        *ptr = desired;
        return true;
    } else {
        *expected = *ptr;  // 更新 expected 为当前值
        return false;
    }
}

#include <stdint.h>
#include <stdatomic.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

typedef struct Node {
    int val;
    struct Node *next;
} Node;

typedef struct {
    _Atomic(Node *) top;
} TreiberStack;

void treiber_init(TreiberStack *s) {
    atomic_store(&s->top, NULL);
}

void treiber_push(TreiberStack *s, int val) {
    Node *n = malloc(sizeof(Node));
    n->val = val;

    Node *old_top = atomic_load_explicit(&s->top, memory_order_relaxed);
    do {
        n->next = old_top;
    } while (!atomic_compare_exchange_weak_explicit(
        &s->top, &old_top, n,
        memory_order_release,
        memory_order_relaxed));
}

int treiber_pop(TreiberStack *s, int *val) {
    Node *old_top = atomic_load_explicit(&s->top, memory_order_acquire);
    Node *new_top;

    do {
        if (old_top == NULL) return 0;
        new_top = old_top->next;
    } while (!atomic_compare_exchange_weak_explicit(
        &s->top, &old_top, new_top,
        memory_order_acquire,
        memory_order_relaxed));

    *val = old_top->val;
    // 注意：这里不能直接 free(old_top)！
    // 其他线程可能还在读 old_top->next
    // 需要安全内存回收（Hazard Pointers 或 Epoch-Based）
    return 1;
}

typedef struct {
    Node *ptr;
    uint64_t tag;
} __attribute__((aligned(16))) TaggedPtr;

// 确保 16 字节对齐
typedef struct {
    _Alignas(16) Node *ptr;
    uint64_t tag;
} TaggedPtr;

// GCC 内建方式
typedef unsigned __int128 uint128_t;

static inline bool dwcas(TaggedPtr *target,
                         TaggedPtr *expected,
                         TaggedPtr desired) {
    return __sync_bool_compare_and_swap(
        (uint128_t *)target,
        *(uint128_t *)expected,
        *(uint128_t *)&desired);
}

static inline void backoff_delay(int us) {
    if (us < 4) {
        // 短退避：自旋，用 PAUSE 指令减少功耗
        for (int i = 0; i < us * 100; i++) {
            __builtin_ia32_pause();
        }
    } else {
        struct timespec ts = {0, us * 1000L};
        nanosleep(&ts, NULL);
    }
}

do {
    if (old_top == NULL) return 0;
    new_top = old_top->next;         // ← 这里解引用 old_top
} while (!atomic_compare_exchange_weak(...));

// CAS 成功后，old_top 被弹出
free(old_top);  // ← 危险！

#include <stdint.h>
#include <stdatomic.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/* ── 节点定义 ── */
typedef struct Node {
    int val;
    struct Node *next;
} Node;

/* ── Tagged Pointer：指针 + 版本号 ── */
typedef struct {
    Node *ptr;
    uint64_t tag;
} __attribute__((aligned(16))) TaggedPtr;

/* 128-bit CAS 封装（x86-64: CMPXCHG16B，需要 -mcx16） */
typedef unsigned __int128 uint128_t;

static inline bool tagged_cas(TaggedPtr *target,
                              TaggedPtr *expected,
                              TaggedPtr desired) {
    uint128_t exp_val, des_val;
    memcpy(&exp_val, expected, sizeof(uint128_t));
    memcpy(&des_val, &desired, sizeof(uint128_t));

    bool ok = __sync_bool_compare_and_swap(
        (volatile uint128_t *)target, exp_val, des_val);
    if (!ok) {
        uint128_t cur = __atomic_load_n(
            (volatile uint128_t *)target, __ATOMIC_RELAXED);
        memcpy(expected, &cur, sizeof(uint128_t));
    }
    return ok;
}

static inline TaggedPtr tagged_load(const TaggedPtr *src) {
    uint128_t raw = __atomic_load_n(
        (const volatile uint128_t *)src, __ATOMIC_ACQUIRE);
    TaggedPtr tp;
    memcpy(&tp, &raw, sizeof(TaggedPtr));
    return tp;
}

/* ── 退避策略 ── */
#define BACKOFF_MIN_US  1
#define BACKOFF_MAX_US  1024

static inline void do_backoff(int *backoff_us) {
    int delay = *backoff_us + (rand() % (*backoff_us + 1));
    if (delay < 4) {
        for (int i = 0; i < delay * 80; i++)
            __builtin_ia32_pause();
    } else {
        struct timespec ts = {0, (long)delay * 1000};
        nanosleep(&ts, NULL);
    }
    int next = *backoff_us * 2;
    *backoff_us = next < BACKOFF_MAX_US ? next : BACKOFF_MAX_US;
}

/* ── Treiber 栈（带 tagged pointer + 指数退避） ── */
typedef struct {
    TaggedPtr top __attribute__((aligned(16)));
} TreiberStackTP;

void treiber_tp_init(TreiberStackTP *s) {
    s->top.ptr = NULL;
    s->top.tag = 0;
}

void treiber_tp_push(TreiberStackTP *s, int val) {
    Node *n = malloc(sizeof(Node));
    n->val = val;

    int backoff = BACKOFF_MIN_US;
    TaggedPtr old_top = tagged_load(&s->top);
    TaggedPtr new_top;

    for (;;) {
        n->next = old_top.ptr;
        new_top.ptr = n;
        new_top.tag = old_top.tag + 1;

        if (tagged_cas(&s->top, &old_top, new_top))
            return;

        do_backoff(&backoff);
    }
}

int treiber_tp_pop(TreiberStackTP *s, int *out) {
    int backoff = BACKOFF_MIN_US;
    TaggedPtr old_top = tagged_load(&s->top);
    TaggedPtr new_top;

    for (;;) {
        if (old_top.ptr == NULL) return 0;

        new_top.ptr = old_top.ptr->next;
        new_top.tag = old_top.tag + 1;

        if (tagged_cas(&s->top, &old_top, new_top)) {
            *out = old_top.ptr->val;
            /* 注意：不直接 free(old_top.ptr)
             * 生产代码需用 Hazard Pointer 或 Epoch-Based 回收
             * 此处为演示省略 */
            return 1;
        }

        do_backoff(&backoff);
    }
}

/* ── 简易测试 ── */
#ifdef TREIBER_TP_MAIN
#include <stdio.h>
#include <pthread.h>

static TreiberStackTP g_stack;
#define OPS_PER_THREAD 100000

void *worker(void *arg) {
    (void)arg;
    unsigned int seed = (unsigned int)pthread_self();
    for (int i = 0; i < OPS_PER_THREAD; i++) {
        if (rand_r(&seed) % 2 == 0) {
            treiber_tp_push(&g_stack, i);
        } else {
            int v;
            treiber_tp_pop(&g_stack, &v);
        }
    }
    return NULL;
}

int main(void) {
    treiber_tp_init(&g_stack);
    int nthreads = 8;
    pthread_t threads[64];
    for (int i = 0; i < nthreads; i++)
        pthread_create(&threads[i], NULL, worker, NULL);
    for (int i = 0; i < nthreads; i++)
        pthread_join(threads[i], NULL);
    printf("Done. Draining stack...\n");
    int v, count = 0;
    while (treiber_tp_pop(&g_stack, &v)) count++;
    printf("Remaining elements: %d\n", count);
    return 0;
}
#endif

gcc -DTREIBER_TP_MAIN -O2 -mcx16 -lpthread -o treiber_tp treiber_tp.c

#include <stdint.h>
#include <stdatomic.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <limits.h>

/* ── 节点 ── */
typedef struct ENode {
    int val;
    struct ENode *next;
} ENode;

/* ── 主栈（简化版 Treiber，使用普通指针 CAS） ── */
typedef struct {
    _Atomic(ENode *) top;
} EStack;

/* ── Elimination 槽位 ── */
/* 状态编码到指针中：
 *   NULL          → EMPTY（无人等待）
 *   SENTINEL      → POP 正在等待
 *   其他 Node*    → PUSH 正在等待（节点地址即数据）
 */
#define ELIM_EMPTY  ((ENode *)0)
#define ELIM_POP    ((ENode *)1)  /* 哨兵值，表示 pop 在等待 */

#define ELIM_ARRAY_SIZE   16
#define ELIM_ROUNDS       32     /* 自旋轮次 */
#define BACKOFF_MIN       1
#define BACKOFF_MAX       512

typedef struct {
    /* 每个槽位独占一个 cache line */
    _Atomic(ENode *) slot __attribute__((aligned(64)));
} __attribute__((aligned(64))) ElimSlot;

typedef struct {
    EStack stack;
    ElimSlot elim[ELIM_ARRAY_SIZE];
} EliminationBackoffStack;

/* ── 工具函数 ── */
static inline unsigned int fast_rand(unsigned int *seed) {
    *seed = *seed * 1103515245 + 12345;
    return (*seed >> 16) & 0x7fff;
}

static inline void spin_wait(int rounds) {
    for (int i = 0; i < rounds; i++)
        __builtin_ia32_pause();
}

/* ── 初始化 ── */
void ebs_init(EliminationBackoffStack *ebs) {
    atomic_store(&ebs->stack.top, NULL);
    for (int i = 0; i < ELIM_ARRAY_SIZE; i++)
        atomic_store(&ebs->elim[i].slot, ELIM_EMPTY);
}

/* ── 尝试通过 elimination 完成 push ── */
static bool elim_try_push(EliminationBackoffStack *ebs,
                          ENode *node, unsigned int *seed) {
    int idx = fast_rand(seed) % ELIM_ARRAY_SIZE;
    _Atomic(ENode *) *slot = &ebs->elim[idx].slot;

    ENode *expected = ELIM_EMPTY;
    if (!atomic_compare_exchange_strong_explicit(
            slot, &expected, node,
            memory_order_release, memory_order_relaxed)) {
        /* 槽位非空——如果是 pop 在等待，直接配对 */
        if (expected == ELIM_POP) {
            if (atomic_compare_exchange_strong_explicit(
                    slot, &expected, node,
                    memory_order_release, memory_order_relaxed)) {
                /* pop 会看到 node 并取走 */
                return false; /* 让 pop 侧完成语义 */
            }
        }
        return false;
    }

    /* 成功写入，等待 pop 来取 */
    for (int r = 0; r < ELIM_ROUNDS; r++) {
        ENode *cur = atomic_load_explicit(slot, memory_order_acquire);
        if (cur != node) {
            /* pop 取走了我们的节点（替换为 ELIM_EMPTY 或其他）*/
            return true;
        }
        spin_wait(4);
    }

    /* 超时，尝试收回 */
    expected = node;
    if (atomic_compare_exchange_strong_explicit(
            slot, &expected, ELIM_EMPTY,
            memory_order_relaxed, memory_order_relaxed))
        return false;  /* 成功收回，elimination 未完成 */

    /* CAS 失败说明 pop 已取走 */
    return true;
}

/* ── 尝试通过 elimination 完成 pop ── */
static bool elim_try_pop(EliminationBackoffStack *ebs,
                         int *out, unsigned int *seed) {
    int idx = fast_rand(seed) % ELIM_ARRAY_SIZE;
    _Atomic(ENode *) *slot = &ebs->elim[idx].slot;

    ENode *cur = atomic_load_explicit(slot, memory_order_acquire);

    if (cur != ELIM_EMPTY && cur != ELIM_POP) {
        /* push 在等待，尝试取走 */
        if (atomic_compare_exchange_strong_explicit(
                slot, &cur, ELIM_EMPTY,
                memory_order_acquire, memory_order_relaxed)) {
            *out = cur->val;
            /* 不 free(cur)——由调用者或回收机制处理 */
            return true;
        }
    }
    return false;
}

/* ── Push（主栈 + elimination 退避） ── */
void ebs_push(EliminationBackoffStack *ebs, int val) {
    ENode *n = malloc(sizeof(ENode));
    n->val = val;

    unsigned int seed = (unsigned int)(uintptr_t)n;
    int backoff = BACKOFF_MIN;

    for (;;) {
        /* 尝试主栈 */
        ENode *old = atomic_load_explicit(
            &ebs->stack.top, memory_order_relaxed);
        n->next = old;
        if (atomic_compare_exchange_weak_explicit(
                &ebs->stack.top, &old, n,
                memory_order_release, memory_order_relaxed))
            return;

        /* CAS 失败，尝试 elimination */
        if (elim_try_push(ebs, n, &seed))
            return;

        /* 退避 */
        spin_wait(backoff);
        backoff = backoff * 2 < BACKOFF_MAX ? backoff * 2 : BACKOFF_MAX;
    }
}

/* ── Pop（主栈 + elimination 退避） ── */
int ebs_pop(EliminationBackoffStack *ebs, int *out) {
    unsigned int seed = (unsigned int)time(NULL);
    int backoff = BACKOFF_MIN;

    for (;;) {
        /* 尝试主栈 */
        ENode *old = atomic_load_explicit(
            &ebs->stack.top, memory_order_acquire);
        if (old == NULL) {
            /* 栈可能为空，但 elimination 中可能有数据 */
            if (elim_try_pop(ebs, out, &seed))
                return 1;
            return 0;  /* 真正为空 */
        }
        ENode *nx = old->next;
        if (atomic_compare_exchange_weak_explicit(
                &ebs->stack.top, &old, nx,
                memory_order_acquire, memory_order_relaxed)) {
            *out = old->val;
            return 1;
        }

        /* CAS 失败，尝试 elimination */
        if (elim_try_pop(ebs, out, &seed))
            return 1;

        /* 退避 */
        spin_wait(backoff);
        backoff = backoff * 2 < BACKOFF_MAX ? backoff * 2 : BACKOFF_MAX;
    }
}

/* ── 销毁 ── */
void ebs_destroy(EliminationBackoffStack *ebs) {
    ENode *cur = atomic_load(&ebs->stack.top);
    while (cur) {
        ENode *next = cur->next;
        free(cur);
        cur = next;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <time.h>
#include <string.h>

#define OPS_PER_THREAD  500000
#define MAX_THREADS     64

typedef struct {
    const char *name;
    void *ctx;
    void (*push_fn)(void *ctx, int val);
    int  (*pop_fn)(void *ctx, int *val);
} BenchTarget;

typedef struct {
    BenchTarget *target;
    int thread_id;
} WorkerArg;

static void *bench_worker(void *arg) {
    WorkerArg *wa = (WorkerArg *)arg;
    unsigned int seed = (unsigned int)wa->thread_id;
    for (int i = 0; i < OPS_PER_THREAD; i++) {
        if (rand_r(&seed) % 2 == 0)
            wa->target->push_fn(wa->target->ctx, i);
        else {
            int v;
            wa->target->pop_fn(wa->target->ctx, &v);
        }
    }
    return NULL;
}

static double run_bench(BenchTarget *target, int nthreads) {
    pthread_t threads[MAX_THREADS];
    WorkerArg args[MAX_THREADS];

    struct timespec start, end;
    clock_gettime(CLOCK_MONOTONIC, &start);

    for (int i = 0; i < nthreads; i++) {
        args[i] = (WorkerArg){target, i};
        pthread_create(&threads[i], NULL, bench_worker, &args[i]);
    }
    for (int i = 0; i < nthreads; i++)
        pthread_join(threads[i], NULL);

    clock_gettime(CLOCK_MONOTONIC, &end);
    double elapsed = (end.tv_sec - start.tv_sec) +
                     (end.tv_nsec - start.tv_nsec) / 1e9;
    double mops = (double)(nthreads * OPS_PER_THREAD) / elapsed / 1e6;
    return mops;
}

void run_all_benchmarks(BenchTarget targets[], int ntargets) {
    int thread_counts[] = {1, 2, 4, 8, 16, 32, 64};
    int ncounts = sizeof(thread_counts) / sizeof(thread_counts[0]);

    printf("%-25s", "Threads");
    for (int t = 0; t < ntargets; t++)
        printf("  %-18s", targets[t].name);
    printf("\n");

    for (int c = 0; c < ncounts; c++) {
        int nt = thread_counts[c];
        printf("%-25d", nt);
        for (int t = 0; t < ntargets; t++) {
            double mops = run_bench(&targets[t], nt);
            printf("  %-18.1f", mops);
        }
        printf("\n");
    }
}

/* 错误：top 和 elim[0] 可能在同一 cache line */
typedef struct {
    _Atomic(Node *) top;       // 8 字节
    _Atomic(Node *) elim[16];  // 紧接 top 之后
} BadStack;

/* 正确：padding 确保不同变量在不同 cache line */
typedef struct {
    _Atomic(Node *) top;
    char _pad[56];                          // 填充到 64 字节
    _Atomic(Node *) elim[16] __attribute__((aligned(64)));
} GoodStack;

/* 方法 1：手动 padding */
typedef struct {
    _Atomic(Node *) top;
    char _pad[64 - sizeof(_Atomic(Node *))];
} PaddedTop;

/* 方法 2：GCC aligned 属性 */
typedef struct {
    _Atomic(Node *) top __attribute__((aligned(64)));
} AlignedTop;

/* 方法 3：C11 _Alignas */
typedef struct {
    _Alignas(64) _Atomic(Node *) top;
} C11AlignedTop;

int slot_index = (numa_node_id * SLOTS_PER_NODE) +
                 (fast_rand(&seed) % SLOTS_PER_NODE);