[urcu.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 volatile int test_go, test_stop;

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);

/*
 * returns 0 if test should end.
 */
static inline int test_duration_write(void)
{
	return !test_stop;
}

static inline int test_duration_read(void)
{
	return !test_stop;
}

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
	114	extern volatile int test_go, test_stop;
	115
	116	extern unsigned long wdelay;
	117
	118	extern unsigned long duration;
	119
	120	/* read-side C.S. duration, in loops */
	121	extern unsigned long rduration;
	122
	123	extern unsigned long init_hash_size;
	124	extern unsigned long min_hash_alloc_size;
	125	extern unsigned long max_hash_buckets_size;
	126	extern unsigned long init_populate;
	127	extern int opt_auto_resize;
	128	extern int add_only, add_unique, add_replace;
	129	extern const struct cds_lfht_mm_type *memory_backend;
	130
	131	extern unsigned long init_pool_offset, lookup_pool_offset, write_pool_offset;
	132	extern unsigned long init_pool_size,
	133	lookup_pool_size,
	134	write_pool_size;
	135	extern int validate_lookup;
	136
495913bf MD	137	extern unsigned long nr_hash_chains;
495913bf MD	138
18ca7a5b MD	139	extern int count_pipe[2];
18ca7a5b MD	140
ab0aacbe	141	static inline void loop_sleep(unsigned long loops)
18ca7a5b	142	{
ab0aacbe	143	while (loops-- != 0)
18ca7a5b MD	144	caa_cpu_relax();
	145	}
	146
	147	extern int verbose_mode;
	148
	149	#define printf_verbose(fmt, args...) \
	150	do { \
	151	if (verbose_mode) \
	152	printf(fmt, ## args); \
	153	} while (0)
	154
	155	extern unsigned int cpu_affinities[NR_CPUS];
	156	extern unsigned int next_aff;
	157	extern int use_affinity;
	158
	159	extern pthread_mutex_t affinity_mutex;
	160
18ca7a5b MD	161	void set_affinity(void);
18ca7a5b MD	162
18ca7a5b MD	163	/*
	164	* returns 0 if test should end.
	165	*/
	166	static inline int test_duration_write(void)
	167	{
	168	return !test_stop;
	169	}
	170
	171	static inline int test_duration_read(void)
	172	{
	173	return !test_stop;
	174	}
	175
bd252a04 MD	176	extern DECLARE_URCU_TLS(unsigned long long, nr_writes);
bd252a04 MD	177	extern DECLARE_URCU_TLS(unsigned long long, nr_reads);
18ca7a5b MD	178
	179	extern unsigned int nr_readers;
	180	extern unsigned int nr_writers;
	181
	182	void rcu_copy_mutex_lock(void);
	183	void rcu_copy_mutex_unlock(void);
	184
	185	/*
	186	* Hash function
	187	* Source: http://burtleburtle.net/bob/c/lookup3.c
	188	* Originally Public Domain
	189	*/
	190
	191	#define rot(x, k) (((x) << (k)) \| ((x) >> (32 - (k))))
	192
	193	#define mix(a, b, c) \
	194	do { \
	195	a -= c; a ^= rot(c, 4); c += b; \
	196	b -= a; b ^= rot(a, 6); a += c; \
	197	c -= b; c ^= rot(b, 8); b += a; \
	198	a -= c; a ^= rot(c, 16); c += b; \
	199	b -= a; b ^= rot(a, 19); a += c; \
	200	c -= b; c ^= rot(b, 4); b += a; \
	201	} while (0)
	202
	203	#define final(a, b, c) \
	204	{ \
	205	c ^= b; c -= rot(b, 14); \
	206	a ^= c; a -= rot(c, 11); \
	207	b ^= a; b -= rot(a, 25); \
	208	c ^= b; c -= rot(b, 16); \
	209	a ^= c; a -= rot(c, 4);\
	210	b ^= a; b -= rot(a, 14); \
	211	c ^= b; c -= rot(b, 24); \
	212	}
	213
	214	static inline __attribute__((unused))
	215	uint32_t hash_u32(
	216	const uint32_t k, / the key, an array of uint32_t values */
	217	size_t length, /* the length of the key, in uint32_ts */
	218	uint32_t initval) /* the previous hash, or an arbitrary value */
	219	{
	220	uint32_t a, b, c;
	221
	222	/* Set up the internal state */
	223	a = b = c = 0xdeadbeef + (((uint32_t) length) << 2) + initval;
	224
	225	/----------------------------------------- handle most of the key /
	226	while (length > 3) {
	227	a += k[0];
	228	b += k[1];
	229	c += k[2];
	230	mix(a, b, c);
	231	length -= 3;
	232	k += 3;
	233	}
	234
	235	/----------------------------------- handle the last 3 uint32_t's /
	236	switch (length) { /* all the case statements fall through */
8771d88d MJ	237	case 3: c += k[2]; /* fall through */
8771d88d MJ	238	case 2: b += k[1]; /* fall through */
18ca7a5b MD	239	case 1: a += k[0];
18ca7a5b MD	240	final(a, b, c);
8771d88d	241	/* fall through */
18ca7a5b MD	242	case 0: /* case 0: nothing left to add */
	243	break;
	244	}
	245	/---------------------------------------------- report the result /
	246	return c;
	247	}
	248
	249	static inline
	250	void hashword2(
	251	const uint32_t k, / the key, an array of uint32_t values */
	252	size_t length, /* the length of the key, in uint32_ts */
	253	uint32_t pc, / IN: seed OUT: primary hash value */
	254	uint32_t pb) / IN: more seed OUT: secondary hash value */
	255	{
	256	uint32_t a, b, c;
	257
	258	/* Set up the internal state */
	259	a = b = c = 0xdeadbeef + ((uint32_t) (length << 2)) + *pc;
	260	c += *pb;
	261
	262	/----------------------------------------- handle most of the key /
	263	while (length > 3) {
	264	a += k[0];
	265	b += k[1];
	266	c += k[2];
	267	mix(a, b, c);
	268	length -= 3;
	269	k += 3;
	270	}
	271
	272	/----------------------------------- handle the last 3 uint32_t's /
	273	switch (length) { /* all the case statements fall through */
447c9339 MJ	274	case 3: c += k[2]; /* fall through */
447c9339 MJ	275	case 2: b += k[1]; /* fall through */
18ca7a5b MD	276	case 1: a += k[0];
18ca7a5b MD	277	final(a, b, c);
447c9339	278	/* fall through */
18ca7a5b MD	279	case 0: /* case 0: nothing left to add */
	280	break;
	281	}
	282	/---------------------------------------------- report the result /
	283	*pc = c;
	284	*pb = b;
	285	}
	286
	287	#if (CAA_BITS_PER_LONG == 32)
	288	static inline
495913bf	289	unsigned long test_hash_mix(const void *_key, size_t length, unsigned long seed)
18ca7a5b MD	290	{
	291	unsigned int key = (unsigned int) _key;
	292
01477510	293	urcu_posix_assert(length == sizeof(unsigned int));
18ca7a5b MD	294	return hash_u32(&key, 1, seed);
	295	}
	296	#else
	297	static inline
495913bf	298	unsigned long test_hash_mix(const void *_key, size_t length, unsigned long seed)
18ca7a5b MD	299	{
	300	union {
	301	uint64_t v64;
	302	uint32_t v32[2];
	303	} v;
	304	union {
	305	uint64_t v64;
	306	uint32_t v32[2];
	307	} key;
	308
01477510	309	urcu_posix_assert(length == sizeof(unsigned long));
18ca7a5b MD	310	v.v64 = (uint64_t) seed;
	311	key.v64 = (uint64_t) _key;
	312	hashword2(key.v32, 2, &v.v32[0], &v.v32[1]);
	313	return v.v64;
	314	}
	315	#endif
	316
495913bf MD	317	/*
	318	* Hash function with nr_hash_chains != 0 for testing purpose only!
	319	* Creates very long hash chains, deteriorating the hash table into a
	320	* few linked lists, depending on the nr_hash_chains value. The purpose
	321	* of this test is to check how the hash table behaves with hash chains
	322	* containing different values, which is a rare case in a normal hash
	323	* table.
	324	*/
	325	static inline
	326	unsigned long test_hash(const void *_key, size_t length,
	327	unsigned long seed)
	328	{
	329	if (nr_hash_chains == 0) {
	330	return test_hash_mix(_key, length, seed);
	331	} else {
	332	unsigned long v;
	333
01477510	334	urcu_posix_assert(length == sizeof(unsigned long));
495913bf MD	335	v = (unsigned long) _key;
	336	return v % nr_hash_chains;
	337	}
	338	}
	339
18ca7a5b MD	340	unsigned long test_compare(const void *key1, size_t key1_len,
	341	const void *key2, size_t key2_len);
	342
	343	static inline
	344	int test_match(struct cds_lfht_node node, const void key)
	345	{
	346	struct lfht_test_node *test_node = to_test_node(node);
	347
	348	return !test_compare(test_node->key, test_node->key_len,
	349	key, sizeof(unsigned long));
	350	}
	351
	352	static inline
	353	void cds_lfht_test_lookup(struct cds_lfht ht, void key, size_t key_len,
	354	struct cds_lfht_iter *iter)
	355	{
01477510	356	urcu_posix_assert(key_len == sizeof(unsigned long));
18ca7a5b MD	357
	358	cds_lfht_lookup(ht, test_hash(key, key_len, TEST_HASH_SEED),
	359	test_match, key, iter);
	360	}
	361
	362	void free_node_cb(struct rcu_head *head);
	363
f52c1ef7 MD	364	/* rw test */
	365	void test_hash_rw_sigusr1_handler(int signo);
	366	void test_hash_rw_sigusr2_handler(int signo);
	367	void test_hash_rw_thr_reader(void _count);
	368	void test_hash_rw_thr_writer(void _count);
	369	int test_hash_rw_populate_hash(void);
	370
20adf780 MD	371	/* unique test */
	372	void test_hash_unique_sigusr1_handler(int signo);
	373	void test_hash_unique_sigusr2_handler(int signo);
	374	void test_hash_unique_thr_reader(void _count);
	375	void test_hash_unique_thr_writer(void _count);
	376	int test_hash_unique_populate_hash(void);
	377
18ca7a5b	378	#endif /* _TEST_URCU_HASH_H */