ck_rhs_t robinhood probing issue reproducer

ck_rhs_probe_bound_reproducer.c

/*
 * Standalone reproducer for a ck_rhs probe-bound corruption. It expects the
 * usual ck_rhs configuration where an 8-bit atomic stores the probe bound.
 *
 * Build from a configured ck checkout with:
 *   cc -std=c99 -O2 -Iinclude ck_rhs_probe_bound_reproducer.c \
 *       src/ck_rhs.c -o ck_rhs_probe_bound_reproducer
 * Or just:
 *   cc -O2 -g3 ck_rhs_probe_bound_reproducer.c -lck -o ck_rhs_probe_reproducer
 */

#include <ck_rhs.h>

#include <assert.h>
#include <ck_malloc.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

#if !defined(CK_F_PR_LOAD_8) || !defined(CK_F_PR_STORE_8)
#error "This reproducer expects 8-bit ck_rhs probe bounds."
#endif

#define CAPACITY 16384
#define N_KEYS 256

struct key {
	unsigned long hash;
};

static struct key keys[N_KEYS];

static void *
repro_malloc(size_t size)
{

	return malloc(size);
}

static void
repro_free(void *pointer, size_t size, bool defer)
{

	(void)size;
	(void)defer;
	free(pointer);
}

static struct ck_malloc allocator = {
	.malloc = repro_malloc,
	.free = repro_free
};

static unsigned long
key_hash(const void *object, unsigned long seed)
{
	const struct key *key = object;

	(void)seed;
	return key->hash;
}

int
main(void)
{
	ck_rhs_t rhs;
	struct key *k, *d;
	unsigned int i;

	assert(ck_rhs_init(&rhs, CK_RHS_MODE_SPMC | CK_RHS_MODE_OBJECT,
	    key_hash, NULL, &allocator, CAPACITY, 0));

	for (i = 0; i < N_KEYS; i++) {
		keys[i].hash = 0;
		assert(ck_rhs_put(&rhs, keys[i].hash, &keys[i]));
	}

	/* Save the last collision while the saturated bound is still correct. */
	k = ck_rhs_get(&rhs, keys[N_KEYS - 1].hash, &keys[N_KEYS - 1]);
	assert(k == &keys[N_KEYS - 1]);

	/* On affected ck, this deletion incorrectly lowers the bound to one. */
	assert(ck_rhs_remove(&rhs, keys[0].hash, &keys[0]) == &keys[0]);

	d = ck_rhs_remove(&rhs, k->hash, k);
	fprintf(stderr, "remove returned %p; expected %p\n", d, k);
	assert(d == k);

	ck_rhs_destroy(&rhs);
	return 0;
}