[userspace-rcu.git] / tests / benchmark / test_urcu_hash.h

// SPDX-FileCopyrightText: 2009-2012 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
//
// SPDX-License-Identifier: GPL-2.0-or-later

#ifndef _TEST_URCU_HASH_H
#define _TEST_URCU_HASH_H

/*
 * Userspace RCU library - test program
 */

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
#include <stdio.h>
#include <errno.h>
#include <signal.h>

#include <urcu/assert.h>
#include <urcu/tls-compat.h>
#include <compat-rand.h>
#include "thread-id.h"
#include "../common/debug-yield.h"

#define DEFAULT_HASH_SIZE	32
#define DEFAULT_MIN_ALLOC_SIZE	1
#define DEFAULT_RAND_POOL	1000000

/*
 * Note: the hash seed should be a random value for hash tables
 * targeting production environments to provide protection against
 * denial of service attacks. We keep it a static value within this test
 * program to compare identical benchmark runs.
 */
#define TEST_HASH_SEED	0x42UL

/* hardcoded number of CPUs */
#define NR_CPUS 16384

#ifdef POISON_FREE
#define poison_free(ptr)				\
	do {						\
		memset(ptr, 0x42, sizeof(*(ptr)));	\
		free(ptr);				\
	} while (0)
#else
#define poison_free(ptr)	free(ptr)
#endif

#ifndef DYNAMIC_LINK_TEST
#define _LGPL_SOURCE
#else
#define debug_yield_read()
#endif
#include <urcu-qsbr.h>
#include <urcu/rculfhash.h>
#include <urcu-call-rcu.h>

struct wr_count {
	unsigned long update_ops;
	unsigned long add;
	unsigned long add_exist;
	unsigned long remove;
};

extern DECLARE_URCU_TLS(unsigned int, rand_lookup);
extern DECLARE_URCU_TLS(unsigned long, nr_add);
extern DECLARE_URCU_TLS(unsigned long, nr_addexist);
extern DECLARE_URCU_TLS(unsigned long, nr_del);
extern DECLARE_URCU_TLS(unsigned long, nr_delnoent);
extern DECLARE_URCU_TLS(unsigned long, lookup_fail);
extern DECLARE_URCU_TLS(unsigned long, lookup_ok);

extern struct cds_lfht *test_ht;

struct test_data {
	int a;
	int b;
};

struct lfht_test_node {
	struct cds_lfht_node node;
	void *key;
	unsigned int key_len;
	/* cache-cold for iteration */
	struct rcu_head head;
};

static inline struct lfht_test_node *
to_test_node(struct cds_lfht_node *node)
{
	return caa_container_of(node, struct lfht_test_node, node);
}

static inline
void lfht_test_node_init(struct lfht_test_node *node, void *key,
			size_t key_len)
{
	cds_lfht_node_init(&node->node);
	node->key = key;
	node->key_len = key_len;
}

static inline struct lfht_test_node *
cds_lfht_iter_get_test_node(struct cds_lfht_iter *iter)
{
	return to_test_node(cds_lfht_iter_get_node(iter));
}

extern unsigned long wdelay;

extern unsigned long duration;

/* read-side C.S. duration, in loops */
extern unsigned long rduration;

extern unsigned long init_hash_size;
extern unsigned long min_hash_alloc_size;
extern unsigned long max_hash_buckets_size;
extern unsigned long init_populate;
extern int opt_auto_resize;
extern int add_only, add_unique, add_replace;
extern const struct cds_lfht_mm_type *memory_backend;

extern unsigned long init_pool_offset, lookup_pool_offset, write_pool_offset;
extern unsigned long init_pool_size,
	lookup_pool_size,
	write_pool_size;
extern int validate_lookup;

extern unsigned long nr_hash_chains;

extern int count_pipe[2];

static inline void loop_sleep(unsigned long loops)
{
	while (loops-- != 0)
		caa_cpu_relax();
}

extern int verbose_mode;

#define printf_verbose(fmt, args...)		\
	do {					\
		if (verbose_mode)		\
			printf(fmt, ## args);	\
	} while (0)

extern unsigned int cpu_affinities[NR_CPUS];
extern unsigned int next_aff;
extern int use_affinity;

extern pthread_mutex_t affinity_mutex;

void set_affinity(void);

extern DECLARE_URCU_TLS(unsigned long long, nr_writes);
extern DECLARE_URCU_TLS(unsigned long long, nr_reads);

extern unsigned int nr_readers;
extern unsigned int nr_writers;

void rcu_copy_mutex_lock(void);
void rcu_copy_mutex_unlock(void);

/*
 * Hash function
 * Source: http://burtleburtle.net/bob/c/lookup3.c
 * Originally Public Domain
 */

#define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k))))

#define mix(a, b, c) \
do { \
	a -= c; a ^= rot(c,  4); c += b; \
	b -= a; b ^= rot(a,  6); a += c; \
	c -= b; c ^= rot(b,  8); b += a; \
	a -= c; a ^= rot(c, 16); c += b; \
	b -= a; b ^= rot(a, 19); a += c; \
	c -= b; c ^= rot(b,  4); b += a; \
} while (0)

#define final(a, b, c) \
{ \
	c ^= b; c -= rot(b, 14); \
	a ^= c; a -= rot(c, 11); \
	b ^= a; b -= rot(a, 25); \
	c ^= b; c -= rot(b, 16); \
	a ^= c; a -= rot(c,  4);\
	b ^= a; b -= rot(a, 14); \
	c ^= b; c -= rot(b, 24); \
}

static inline __attribute__((unused))
uint32_t hash_u32(
	const uint32_t *k,	/* the key, an array of uint32_t values */
	size_t length,		/* the length of the key, in uint32_ts */
	uint32_t initval)	/* the previous hash, or an arbitrary value */
{
	uint32_t a, b, c;

	/* Set up the internal state */
	a = b = c = 0xdeadbeef + (((uint32_t) length) << 2) + initval;

	/*----------------------------------------- handle most of the key */
	while (length > 3) {
		a += k[0];
		b += k[1];
		c += k[2];
		mix(a, b, c);
		length -= 3;
		k += 3;
	}

	/*----------------------------------- handle the last 3 uint32_t's */
	switch (length) {	/* all the case statements fall through */
	case 3: c += k[2]; /* fall through */
	case 2: b += k[1]; /* fall through */
	case 1: a += k[0];
		final(a, b, c);
		/* fall through */
	case 0:			/* case 0: nothing left to add */
		break;
	}
	/*---------------------------------------------- report the result */
	return c;
}

static inline
void hashword2(
	const uint32_t *k,	/* the key, an array of uint32_t values */
	size_t length,		/* the length of the key, in uint32_ts */
	uint32_t *pc,		/* IN: seed OUT: primary hash value */
	uint32_t *pb)		/* IN: more seed OUT: secondary hash value */
{
	uint32_t a, b, c;

	/* Set up the internal state */
	a = b = c = 0xdeadbeef + ((uint32_t) (length << 2)) + *pc;
	c += *pb;

	/*----------------------------------------- handle most of the key */
	while (length > 3) {
		a += k[0];
		b += k[1];
		c += k[2];
		mix(a, b, c);
		length -= 3;
		k += 3;
	}

	/*----------------------------------- handle the last 3 uint32_t's */
	switch (length) {	/* all the case statements fall through */
	case 3: c += k[2]; /* fall through */
	case 2: b += k[1]; /* fall through */
	case 1: a += k[0];
		final(a, b, c);
		/* fall through */
	case 0:			/* case 0: nothing left to add */
		break;
	}
	/*---------------------------------------------- report the result */
	*pc = c;
	*pb = b;
}

#if (CAA_BITS_PER_LONG == 32)
static inline
unsigned long test_hash_mix(const void *_key, size_t length, unsigned long seed)
{
	unsigned int key = (unsigned int) _key;

	urcu_posix_assert(length == sizeof(unsigned int));
	return hash_u32(&key, 1, seed);
}
#else
static inline
unsigned long test_hash_mix(const void *_key, size_t length, unsigned long seed)
{
	union {
		uint64_t v64;
		uint32_t v32[2];
	} v;
	union {
		uint64_t v64;
		uint32_t v32[2];
	} key;

	urcu_posix_assert(length == sizeof(unsigned long));
	v.v64 = (uint64_t) seed;
	key.v64 = (uint64_t) _key;
	hashword2(key.v32, 2, &v.v32[0], &v.v32[1]);
	return v.v64;
}
#endif

/*
 * Hash function with nr_hash_chains != 0 for testing purpose only!
 * Creates very long hash chains, deteriorating the hash table into a
 * few linked lists, depending on the nr_hash_chains value. The purpose
 * of this test is to check how the hash table behaves with hash chains
 * containing different values, which is a rare case in a normal hash
 * table.
 */
static inline
unsigned long test_hash(const void *_key, size_t length,
			unsigned long seed)
{
	if (nr_hash_chains == 0) {
		return test_hash_mix(_key, length, seed);
	} else {
		unsigned long v;

		urcu_posix_assert(length == sizeof(unsigned long));
		v = (unsigned long) _key;
		return v % nr_hash_chains;
	}
}

unsigned long test_compare(const void *key1, size_t key1_len,
                           const void *key2, size_t key2_len);

static inline
int test_match(struct cds_lfht_node *node, const void *key)
{
	struct lfht_test_node *test_node = to_test_node(node);

	return !test_compare(test_node->key, test_node->key_len,
			key, sizeof(unsigned long));
}

static inline
void cds_lfht_test_lookup(struct cds_lfht *ht, void *key, size_t key_len,
		struct cds_lfht_iter *iter)
{
	urcu_posix_assert(key_len == sizeof(unsigned long));

	cds_lfht_lookup(ht, test_hash(key, key_len, TEST_HASH_SEED),
			test_match, key, iter);
}

void free_node_cb(struct rcu_head *head);

/* rw test */
void test_hash_rw_sigusr1_handler(int signo);
void test_hash_rw_sigusr2_handler(int signo);
void *test_hash_rw_thr_reader(void *_count);
void *test_hash_rw_thr_writer(void *_count);
int test_hash_rw_populate_hash(void);

/* unique test */
void test_hash_unique_sigusr1_handler(int signo);
void test_hash_unique_sigusr2_handler(int signo);
void *test_hash_unique_thr_reader(void *_count);
void *test_hash_unique_thr_writer(void *_count);
int test_hash_unique_populate_hash(void);

#endif /* _TEST_URCU_HASH_H */
Commit	Line	Data
ce29b371 MJ	1	// SPDX-FileCopyrightText: 2009-2012 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
	2	//
	3	// SPDX-License-Identifier: GPL-2.0-or-later
	4
18ca7a5b MD	5	#ifndef _TEST_URCU_HASH_H
	6	#define _TEST_URCU_HASH_H
	7
	8	/*
18ca7a5b	9	* Userspace RCU library - test program
18ca7a5b MD	10	*/
18ca7a5b MD	11
18ca7a5b MD	12	#include <stdio.h>
	13	#include <pthread.h>
	14	#include <stdlib.h>
	15	#include <string.h>
	16	#include <sys/types.h>
	17	#include <sys/wait.h>
	18	#include <unistd.h>
	19	#include <stdio.h>
18ca7a5b MD	20	#include <errno.h>
	21	#include <signal.h>
	22
01477510	23	#include <urcu/assert.h>
bd252a04	24	#include <urcu/tls-compat.h>
094c8c59	25	#include <compat-rand.h>
94df6318	26	#include "thread-id.h"
2650042a	27	#include "../common/debug-yield.h"
18ca7a5b MD	28
	29	#define DEFAULT_HASH_SIZE 32
	30	#define DEFAULT_MIN_ALLOC_SIZE 1
	31	#define DEFAULT_RAND_POOL 1000000
	32
	33	/*
	34	* Note: the hash seed should be a random value for hash tables
	35	* targeting production environments to provide protection against
	36	* denial of service attacks. We keep it a static value within this test
	37	* program to compare identical benchmark runs.
	38	*/
	39	#define TEST_HASH_SEED 0x42UL
	40
18ca7a5b MD	41	/* hardcoded number of CPUs */
	42	#define NR_CPUS 16384
	43
	44	#ifdef POISON_FREE
	45	#define poison_free(ptr) \
	46	do { \
	47	memset(ptr, 0x42, sizeof(*(ptr))); \
	48	free(ptr); \
	49	} while (0)
	50	#else
	51	#define poison_free(ptr) free(ptr)
	52	#endif
	53
18ca7a5b MD	54	#ifndef DYNAMIC_LINK_TEST
	55	#define _LGPL_SOURCE
	56	#else
	57	#define debug_yield_read()
	58	#endif
	59	#include <urcu-qsbr.h>
	60	#include <urcu/rculfhash.h>
	61	#include <urcu-call-rcu.h>
	62
	63	struct wr_count {
	64	unsigned long update_ops;
	65	unsigned long add;
	66	unsigned long add_exist;
	67	unsigned long remove;
	68	};
	69
bd252a04 MD	70	extern DECLARE_URCU_TLS(unsigned int, rand_lookup);
	71	extern DECLARE_URCU_TLS(unsigned long, nr_add);
	72	extern DECLARE_URCU_TLS(unsigned long, nr_addexist);
	73	extern DECLARE_URCU_TLS(unsigned long, nr_del);
	74	extern DECLARE_URCU_TLS(unsigned long, nr_delnoent);
	75	extern DECLARE_URCU_TLS(unsigned long, lookup_fail);
	76	extern DECLARE_URCU_TLS(unsigned long, lookup_ok);
18ca7a5b MD	77
	78	extern struct cds_lfht *test_ht;
	79
	80	struct test_data {
	81	int a;
	82	int b;
	83	};
	84
	85	struct lfht_test_node {
	86	struct cds_lfht_node node;
	87	void *key;
	88	unsigned int key_len;
	89	/* cache-cold for iteration */
	90	struct rcu_head head;
	91	};
	92
	93	static inline struct lfht_test_node *
	94	to_test_node(struct cds_lfht_node *node)
	95	{
	96	return caa_container_of(node, struct lfht_test_node, node);
	97	}
	98
	99	static inline
	100	void lfht_test_node_init(struct lfht_test_node node, void key,
	101	size_t key_len)
	102	{
	103	cds_lfht_node_init(&node->node);
	104	node->key = key;
	105	node->key_len = key_len;
	106	}
	107
	108	static inline struct lfht_test_node *
	109	cds_lfht_iter_get_test_node(struct cds_lfht_iter *iter)
	110	{
	111	return to_test_node(cds_lfht_iter_get_node(iter));
	112	}
	113
18ca7a5b MD	114	extern unsigned long wdelay;
	115
	116	extern unsigned long duration;
	117
	118	/* read-side C.S. duration, in loops */
	119	extern unsigned long rduration;
	120
	121	extern unsigned long init_hash_size;
	122	extern unsigned long min_hash_alloc_size;
	123	extern unsigned long max_hash_buckets_size;
	124	extern unsigned long init_populate;
	125	extern int opt_auto_resize;
	126	extern int add_only, add_unique, add_replace;
	127	extern const struct cds_lfht_mm_type *memory_backend;
	128
	129	extern unsigned long init_pool_offset, lookup_pool_offset, write_pool_offset;
	130	extern unsigned long init_pool_size,
	131	lookup_pool_size,
	132	write_pool_size;
	133	extern int validate_lookup;
	134
495913bf MD	135	extern unsigned long nr_hash_chains;
495913bf MD	136
18ca7a5b MD	137	extern int count_pipe[2];
18ca7a5b MD	138
ab0aacbe	139	static inline void loop_sleep(unsigned long loops)
18ca7a5b	140	{
ab0aacbe	141	while (loops-- != 0)
18ca7a5b MD	142	caa_cpu_relax();
	143	}
	144
	145	extern int verbose_mode;
	146
	147	#define printf_verbose(fmt, args...) \
	148	do { \
	149	if (verbose_mode) \
	150	printf(fmt, ## args); \
	151	} while (0)
	152
	153	extern unsigned int cpu_affinities[NR_CPUS];
	154	extern unsigned int next_aff;
	155	extern int use_affinity;
	156
	157	extern pthread_mutex_t affinity_mutex;
	158
18ca7a5b MD	159	void set_affinity(void);
18ca7a5b MD	160
bd252a04 MD	161	extern DECLARE_URCU_TLS(unsigned long long, nr_writes);
bd252a04 MD	162	extern DECLARE_URCU_TLS(unsigned long long, nr_reads);
18ca7a5b MD	163
	164	extern unsigned int nr_readers;
	165	extern unsigned int nr_writers;
	166
	167	void rcu_copy_mutex_lock(void);
	168	void rcu_copy_mutex_unlock(void);
	169
	170	/*
	171	* Hash function
	172	* Source: http://burtleburtle.net/bob/c/lookup3.c
	173	* Originally Public Domain
	174	*/
	175
	176	#define rot(x, k) (((x) << (k)) \| ((x) >> (32 - (k))))
	177
	178	#define mix(a, b, c) \
	179	do { \
	180	a -= c; a ^= rot(c, 4); c += b; \
	181	b -= a; b ^= rot(a, 6); a += c; \
	182	c -= b; c ^= rot(b, 8); b += a; \
	183	a -= c; a ^= rot(c, 16); c += b; \
	184	b -= a; b ^= rot(a, 19); a += c; \
	185	c -= b; c ^= rot(b, 4); b += a; \
	186	} while (0)
	187
	188	#define final(a, b, c) \
	189	{ \
	190	c ^= b; c -= rot(b, 14); \
	191	a ^= c; a -= rot(c, 11); \
	192	b ^= a; b -= rot(a, 25); \
	193	c ^= b; c -= rot(b, 16); \
	194	a ^= c; a -= rot(c, 4);\
	195	b ^= a; b -= rot(a, 14); \
	196	c ^= b; c -= rot(b, 24); \
	197	}
	198
	199	static inline __attribute__((unused))
	200	uint32_t hash_u32(
	201	const uint32_t k, / the key, an array of uint32_t values */
	202	size_t length, /* the length of the key, in uint32_ts */
	203	uint32_t initval) /* the previous hash, or an arbitrary value */
	204	{
	205	uint32_t a, b, c;
	206
	207	/* Set up the internal state */
	208	a = b = c = 0xdeadbeef + (((uint32_t) length) << 2) + initval;
	209
	210	/----------------------------------------- handle most of the key /
	211	while (length > 3) {
	212	a += k[0];
	213	b += k[1];
	214	c += k[2];
	215	mix(a, b, c);
	216	length -= 3;
	217	k += 3;
	218	}
	219
	220	/----------------------------------- handle the last 3 uint32_t's /
	221	switch (length) { /* all the case statements fall through */
8771d88d MJ	222	case 3: c += k[2]; /* fall through */
8771d88d MJ	223	case 2: b += k[1]; /* fall through */
18ca7a5b MD	224	case 1: a += k[0];
18ca7a5b MD	225	final(a, b, c);
8771d88d	226	/* fall through */
18ca7a5b MD	227	case 0: /* case 0: nothing left to add */
	228	break;
	229	}
	230	/---------------------------------------------- report the result /
	231	return c;
	232	}
	233
	234	static inline
	235	void hashword2(
	236	const uint32_t k, / the key, an array of uint32_t values */
	237	size_t length, /* the length of the key, in uint32_ts */
	238	uint32_t pc, / IN: seed OUT: primary hash value */
	239	uint32_t pb) / IN: more seed OUT: secondary hash value */
	240	{
	241	uint32_t a, b, c;
	242
	243	/* Set up the internal state */
	244	a = b = c = 0xdeadbeef + ((uint32_t) (length << 2)) + *pc;
	245	c += *pb;
	246
	247	/----------------------------------------- handle most of the key /
	248	while (length > 3) {
	249	a += k[0];
	250	b += k[1];
	251	c += k[2];
	252	mix(a, b, c);
	253	length -= 3;
	254	k += 3;
	255	}
	256
	257	/----------------------------------- handle the last 3 uint32_t's /
	258	switch (length) { /* all the case statements fall through */
447c9339 MJ	259	case 3: c += k[2]; /* fall through */
447c9339 MJ	260	case 2: b += k[1]; /* fall through */
18ca7a5b MD	261	case 1: a += k[0];
18ca7a5b MD	262	final(a, b, c);
447c9339	263	/* fall through */
18ca7a5b MD	264	case 0: /* case 0: nothing left to add */
	265	break;
	266	}
	267	/---------------------------------------------- report the result /
	268	*pc = c;
	269	*pb = b;
	270	}
	271
	272	#if (CAA_BITS_PER_LONG == 32)
	273	static inline
495913bf	274	unsigned long test_hash_mix(const void *_key, size_t length, unsigned long seed)
18ca7a5b MD	275	{
	276	unsigned int key = (unsigned int) _key;
	277
01477510	278	urcu_posix_assert(length == sizeof(unsigned int));
18ca7a5b MD	279	return hash_u32(&key, 1, seed);
	280	}
	281	#else
	282	static inline
495913bf	283	unsigned long test_hash_mix(const void *_key, size_t length, unsigned long seed)
18ca7a5b MD	284	{
	285	union {
	286	uint64_t v64;
	287	uint32_t v32[2];
	288	} v;
	289	union {
	290	uint64_t v64;
	291	uint32_t v32[2];
	292	} key;
	293
01477510	294	urcu_posix_assert(length == sizeof(unsigned long));
18ca7a5b MD	295	v.v64 = (uint64_t) seed;
	296	key.v64 = (uint64_t) _key;
	297	hashword2(key.v32, 2, &v.v32[0], &v.v32[1]);
	298	return v.v64;
	299	}
	300	#endif
	301
495913bf MD	302	/*
	303	* Hash function with nr_hash_chains != 0 for testing purpose only!
	304	* Creates very long hash chains, deteriorating the hash table into a
	305	* few linked lists, depending on the nr_hash_chains value. The purpose
	306	* of this test is to check how the hash table behaves with hash chains
	307	* containing different values, which is a rare case in a normal hash
	308	* table.
	309	*/
	310	static inline
	311	unsigned long test_hash(const void *_key, size_t length,
	312	unsigned long seed)
	313	{
	314	if (nr_hash_chains == 0) {
	315	return test_hash_mix(_key, length, seed);
	316	} else {
	317	unsigned long v;
	318
01477510	319	urcu_posix_assert(length == sizeof(unsigned long));
495913bf MD	320	v = (unsigned long) _key;
	321	return v % nr_hash_chains;
	322	}
	323	}
	324
18ca7a5b MD	325	unsigned long test_compare(const void *key1, size_t key1_len,
	326	const void *key2, size_t key2_len);
	327
	328	static inline
	329	int test_match(struct cds_lfht_node node, const void key)
	330	{
	331	struct lfht_test_node *test_node = to_test_node(node);
	332
	333	return !test_compare(test_node->key, test_node->key_len,
	334	key, sizeof(unsigned long));
	335	}
	336
	337	static inline
	338	void cds_lfht_test_lookup(struct cds_lfht ht, void key, size_t key_len,
	339	struct cds_lfht_iter *iter)
	340	{
01477510	341	urcu_posix_assert(key_len == sizeof(unsigned long));
18ca7a5b MD	342
	343	cds_lfht_lookup(ht, test_hash(key, key_len, TEST_HASH_SEED),
	344	test_match, key, iter);
	345	}
	346
	347	void free_node_cb(struct rcu_head *head);
	348
f52c1ef7 MD	349	/* rw test */
	350	void test_hash_rw_sigusr1_handler(int signo);
	351	void test_hash_rw_sigusr2_handler(int signo);
	352	void test_hash_rw_thr_reader(void _count);
	353	void test_hash_rw_thr_writer(void _count);
	354	int test_hash_rw_populate_hash(void);
	355
20adf780 MD	356	/* unique test */
	357	void test_hash_unique_sigusr1_handler(int signo);
	358	void test_hash_unique_sigusr2_handler(int signo);
	359	void test_hash_unique_thr_reader(void _count);
	360	void test_hash_unique_thr_writer(void _count);
	361	int test_hash_unique_populate_hash(void);
	362
18ca7a5b	363	#endif /* _TEST_URCU_HASH_H */