Reproducer illustrating losing a key with `ck_rhs_fas`

ck_rhs_fas_grow_reproducer.c

/*
 * Reproduce a stale map pointer in ck_rhs_fas after Robin Hood relocation
 * grows the table.
 *
 * There are three useful outcomes:
 *
 *  1. Unpatched master loses a key before ck_rhs_fas can reach the growth
 *     path, demonstrating the pre-existing Robin Hood probe-depth bug.
 *  2. With only the probe-depth fix, ck_rhs_fas reaches the growth path and
 *     loses the replacement by restarting with a pointer to the retired map.
 *  3. With both fixes, the program reports successful ck_rhs_fas growth.
 *
 * Build with:
 *   cc -std=c99 -O2 -Iinclude ck_rhs_fas_grow_reproducer.c \
 *       src/ck_rhs.c -o ck_rhs_fas_grow_reproducer
 */

#include <ck_malloc.h>
#include <ck_rhs.h>

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

#define MAX_KEYS 1024
#define MAX_RETIRED 64

struct key {
	unsigned long hash;
	unsigned long id;
};

static struct key keys[MAX_KEYS][2];
static struct key *active[MAX_KEYS];
static void *retired[MAX_RETIRED];
static unsigned int n_retired;
static bool in_fas;
static bool fas_grew;

static void *
repro_malloc(size_t size)
{

	return malloc(size);
}

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

	(void)size;
	if (defer) {
		if (n_retired == MAX_RETIRED) {
			fprintf(stderr, "too many retired maps\n");
			exit(EXIT_FAILURE);
		}
		retired[n_retired++] = pointer;
		if (in_fas)
			fas_grew = true;
		return;
	}
	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;
}

static bool
key_compare(const void *left, const void *right)
{
	const struct key *a = left;
	const struct key *b = right;

	return a->id == b->id;
}

int
main(void)
{
	ck_rhs_t rhs;
	unsigned int i, j = 0, version, grown_key = 0;
	void *previous;

	if (ck_rhs_init(&rhs, CK_RHS_MODE_SPMC | CK_RHS_MODE_OBJECT,
	    key_hash, key_compare, &allocator, 8, 0) == false) {
		fprintf(stderr, "ck_rhs_init failed\n");
		return EXIT_FAILURE;
	}

	for (i = 0; i < MAX_KEYS && fas_grew == false; i++) {
		keys[i][0].hash = keys[i][1].hash = i & 7;
		keys[i][0].id = keys[i][1].id = i;
		active[i] = &keys[i][0];
		if (ck_rhs_put(&rhs, active[i]->hash, active[i]) == false) {
			fprintf(stderr, "put failed at key %u\n", i);
			return EXIT_FAILURE;
		}

		for (j = 0; j <= i && fas_grew == false; j++) {
			version = active[j] == &keys[j][0];
			if (ck_rhs_get(&rhs, active[j]->hash,
			    active[j]) != active[j]) {
				fprintf(stderr, "key %u became unreachable before "
				    "ck_rhs_fas after inserting key %u\n", j, i);
				return EXIT_FAILURE;
			}
			in_fas = true;
			if (ck_rhs_fas(&rhs, keys[j][version].hash,
			    &keys[j][version], &previous) == false) {
				in_fas = false;
				fprintf(stderr, "ck_rhs_fas failed for reachable key %u "
				    "after inserting key %u\n", j, i);
				return EXIT_FAILURE;
			}
			in_fas = false;
			if (previous != active[j]) {
				fprintf(stderr, "fas returned the wrong previous key\n");
				return EXIT_FAILURE;
			}
			active[j] = &keys[j][version];
			if (fas_grew)
				grown_key = j;
			if (fas_grew && ck_rhs_get(&rhs, active[j]->hash,
			    active[j]) != active[j]) {
				fprintf(stderr, "replacement key %u was lost after growth\n", j);
				return EXIT_FAILURE;
			}
		}
	}

	if (fas_grew == false) {
		fprintf(stderr, "no ck_rhs_fas growth after %u keys\n", i);
		return EXIT_FAILURE;
	}

	printf("ck_rhs_fas grew after inserting key %u while replacing key %u\n",
	    i - 1, grown_key);
	ck_rhs_destroy(&rhs);
	for (i = 0; i < n_retired; i++)
		free(retired[i]);
	return EXIT_SUCCESS;
}