[userspace-rcu.git] / rcuja / rcuja-shadow-nodes.c

/*
 * rcuja/rcuja-hashtable.c
 *
 * Userspace RCU library - RCU Judy Array Shadow Node Hash Table
 *
 * Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

#define _LGPL_SOURCE
#include <stdint.h>
#include <errno.h>
#include <limits.h>

/*
 * The hash table used by judy array updates only for the shadow node
 * mapping rely on standard urcu_mb flavor. It does not put any
 * requirement on the RCU flavor used by applications using the judy
 * array.
 */
#include <urcu.h>

#include <urcu/rcuja.h>
#include <urcu/compiler.h>
#include <urcu/arch.h>
#include <assert.h>
#include <urcu-pointer.h>
#include <stdlib.h>
#include <time.h>

#include "rcuja-internal.h"
#include "bitfield.h"

static unsigned long hash_seed;

/*
 * 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];
	case 2: b += k[1];
	case 1: a += k[0];
		final(a, b, c);
	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];
	case 2: b += k[1];
	case 1: a += k[0];
		final(a, b, c);
	case 0:			/* case 0: nothing left to add */
		break;
	}
	/*---------------------------------------------- report the result */
	*pc = c;
	*pb = b;
}

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

	return hash_u32(&key, 1, seed);
}
#else
static
unsigned long hash_pointer(const void *_key, unsigned long seed)
{
	union {
		uint64_t v64;
		uint32_t v32[2];
	} v;
	union {
		uint64_t v64;
		uint32_t v32[2];
	} key;

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

static
int match_pointer(struct cds_lfht_node *node, const void *key)
{
	struct rcu_ja_shadow_node *shadow =
		caa_container_of(node, struct rcu_ja_shadow_node, ht_node);

	return (key == shadow->node);
}

__attribute__((visibility("protected")))
struct rcu_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht,
		struct rcu_ja_node *node)
{
	struct cds_lfht_iter iter;
	struct cds_lfht_node *lookup_node;
	struct rcu_ja_shadow_node *shadow_node;
	int ret;

	rcu_read_lock();
	cds_lfht_lookup(ht, hash_pointer(node, hash_seed),
			match_pointer, node, &iter);

	lookup_node = cds_lfht_iter_get_node(&iter);
	if (!lookup_node) {
		shadow_node = NULL;
		goto rcu_unlock;
	}
	shadow_node = caa_container_of(lookup_node,
			struct rcu_ja_shadow_node, ht_node);
	ret = pthread_mutex_lock(&shadow_node->lock);
	assert(!ret);
	if (cds_lfht_is_node_deleted(lookup_node)) {
		ret = pthread_mutex_unlock(&shadow_node->lock);
		assert(!ret);
		shadow_node = NULL;
	}
rcu_unlock:
	rcu_read_unlock();
	return shadow_node;
}

__attribute__((visibility("protected")))
void rcuja_shadow_unlock(struct rcu_ja_shadow_node *shadow_node)
{
	int ret;

	ret = pthread_mutex_unlock(&shadow_node->lock);
	assert(!ret);
}

__attribute__((visibility("protected")))
int rcuja_shadow_set(struct cds_lfht *ht,
		struct rcu_ja_node *node)
{
	struct rcu_ja_shadow_node *shadow_node;
	struct cds_lfht_node *ret_node;

	shadow_node = calloc(sizeof(*shadow_node), 1);
	if (!shadow_node)
		return -ENOMEM;

	shadow_node->node = node;
	pthread_mutex_init(&shadow_node->lock, NULL);

	rcu_read_lock();
	ret_node = cds_lfht_add_unique(ht,
			hash_pointer(node, hash_seed),
			match_pointer,
			node,
			&shadow_node->ht_node);
	rcu_read_unlock();

	if (ret_node != &shadow_node->ht_node) {
		free(shadow_node);
		return -EEXIST;
	}
	return 0;
}

static
void free_shadow_node_and_node(struct rcu_head *head)
{
	struct rcu_ja_shadow_node *shadow_node =
		caa_container_of(head, struct rcu_ja_shadow_node, head);
	free(shadow_node->node);
	free(shadow_node);
}

__attribute__((visibility("protected")))
int rcuja_shadow_clear_and_free_node(struct cds_lfht *ht,
		struct rcu_ja_node *node)
{
	struct cds_lfht_iter iter;
	struct cds_lfht_node *lookup_node;
	struct rcu_ja_shadow_node *shadow_node;
	int ret, lockret;

	rcu_read_lock();
	cds_lfht_lookup(ht, hash_pointer(node, hash_seed),
			match_pointer, node, &iter);
	lookup_node = cds_lfht_iter_get_node(&iter);
	if (!lookup_node) {
		ret = -ENOENT;
		goto rcu_unlock;
	}
	shadow_node = caa_container_of(lookup_node,
			struct rcu_ja_shadow_node, ht_node);
	lockret = pthread_mutex_lock(&shadow_node->lock);
	assert(!lockret);

	/*
	 * Holding the mutex across deletion, and by also re-checking if
	 * the node is deleted with mutex held at lookup ensure that we
	 * don't let RCU JA use a node being removed.
	 */
	ret = cds_lfht_del(ht, lookup_node);
	if (!ret) {
		call_rcu(&shadow_node->head, free_shadow_node_and_node);
	}
	lockret = pthread_mutex_unlock(&shadow_node->lock);
	assert(!lockret);
rcu_unlock:
	rcu_read_unlock();

	return ret;
}

__attribute__((visibility("protected")))
struct cds_lfht *rcuja_create_ht(void)
{
	return cds_lfht_new(1, 1, 0,
		CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING,
		NULL);
}

__attribute__((visibility("protected")))
void rcuja_delete_ht(struct cds_lfht *ht)
{
	int ret;

	ret = cds_lfht_destroy(ht, NULL);
	assert(!ret);
}

__attribute__((constructor))
void rcuja_ht_init(void)
{
	hash_seed = (unsigned long) time(NULL);
}
Commit	Line	Data
195e72d3 MD	1	/*
	2	* rcuja/rcuja-hashtable.c
	3	*
	4	* Userspace RCU library - RCU Judy Array Shadow Node Hash Table
	5	*
	6	* Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
	7	*
	8	* This library is free software; you can redistribute it and/or
	9	* modify it under the terms of the GNU Lesser General Public
	10	* License as published by the Free Software Foundation; either
	11	* version 2.1 of the License, or (at your option) any later version.
	12	*
	13	* This library is distributed in the hope that it will be useful,
	14	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	15	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	16	* Lesser General Public License for more details.
	17	*
	18	* You should have received a copy of the GNU Lesser General Public
	19	* License along with this library; if not, write to the Free Software
	20	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
	21	*/
	22
	23	#define _LGPL_SOURCE
	24	#include <stdint.h>
	25	#include <errno.h>
	26	#include <limits.h>
	27
	28	/*
	29	* The hash table used by judy array updates only for the shadow node
	30	* mapping rely on standard urcu_mb flavor. It does not put any
	31	* requirement on the RCU flavor used by applications using the judy
	32	* array.
	33	*/
	34	#include <urcu.h>
	35
	36	#include <urcu/rcuja.h>
	37	#include <urcu/compiler.h>
	38	#include <urcu/arch.h>
	39	#include <assert.h>
	40	#include <urcu-pointer.h>
d22c185b MD	41	#include <stdlib.h>
d22c185b MD	42	#include <time.h>
195e72d3 MD	43
	44	#include "rcuja-internal.h"
	45	#include "bitfield.h"
	46
d22c185b MD	47	static unsigned long hash_seed;
	48
	49	/*
	50	* Hash function
	51	* Source: http://burtleburtle.net/bob/c/lookup3.c
	52	* Originally Public Domain
	53	*/
	54
	55	#define rot(x, k) (((x) << (k)) \| ((x) >> (32 - (k))))
	56
	57	#define mix(a, b, c) \
	58	do { \
	59	a -= c; a ^= rot(c, 4); c += b; \
	60	b -= a; b ^= rot(a, 6); a += c; \
	61	c -= b; c ^= rot(b, 8); b += a; \
	62	a -= c; a ^= rot(c, 16); c += b; \
	63	b -= a; b ^= rot(a, 19); a += c; \
	64	c -= b; c ^= rot(b, 4); b += a; \
	65	} while (0)
	66
	67	#define final(a, b, c) \
	68	{ \
	69	c ^= b; c -= rot(b, 14); \
	70	a ^= c; a -= rot(c, 11); \
	71	b ^= a; b -= rot(a, 25); \
	72	c ^= b; c -= rot(b, 16); \
	73	a ^= c; a -= rot(c, 4);\
	74	b ^= a; b -= rot(a, 14); \
	75	c ^= b; c -= rot(b, 24); \
	76	}
	77
	78	static inline __attribute__((unused))
	79	uint32_t hash_u32(
	80	const uint32_t k, / the key, an array of uint32_t values */
	81	size_t length, /* the length of the key, in uint32_ts */
	82	uint32_t initval) /* the previous hash, or an arbitrary value */
	83	{
	84	uint32_t a, b, c;
	85
	86	/* Set up the internal state */
	87	a = b = c = 0xdeadbeef + (((uint32_t) length) << 2) + initval;
	88
	89	/----------------------------------------- handle most of the key /
	90	while (length > 3) {
	91	a += k[0];
	92	b += k[1];
	93	c += k[2];
	94	mix(a, b, c);
	95	length -= 3;
	96	k += 3;
	97	}
	98
	99	/----------------------------------- handle the last 3 uint32_t's /
	100	switch (length) { /* all the case statements fall through */
	101	case 3: c += k[2];
	102	case 2: b += k[1];
	103	case 1: a += k[0];
	104	final(a, b, c);
	105	case 0: /* case 0: nothing left to add */
	106	break;
	107	}
	108	/---------------------------------------------- report the result /
	109	return c;
	110	}
111
112	static inline
113	void hashword2(
114	const uint32_t k, / the key, an array of uint32_t values */
115	size_t length, /* the length of the key, in uint32_ts */
116	uint32_t pc, / IN: seed OUT: primary hash value */
117	uint32_t pb) / IN: more seed OUT: secondary hash value */
118	{
119	uint32_t a, b, c;
120
121	/* Set up the internal state */
122	a = b = c = 0xdeadbeef + ((uint32_t) (length << 2)) + *pc;
123	c += *pb;
124
125	/----------------------------------------- handle most of the key /
126	while (length > 3) {
127	a += k[0];
128	b += k[1];
129	c += k[2];
130	mix(a, b, c);
131	length -= 3;
132	k += 3;
133	}
134
135	/----------------------------------- handle the last 3 uint32_t's /
136	switch (length) { /* all the case statements fall through */
137	case 3: c += k[2];
138	case 2: b += k[1];
139	case 1: a += k[0];
140	final(a, b, c);
141	case 0: /* case 0: nothing left to add */
142	break;
143	}
144	/---------------------------------------------- report the result /
145	*pc = c;
146	*pb = b;
147	}
148
149	#if (CAA_BITS_PER_LONG == 32)
150	static
151	unsigned long hash_pointer(const void *_key, unsigned long seed)
152	{
153	unsigned int key = (unsigned int) _key;
154
155	return hash_u32(&key, 1, seed);
156	}
157	#else
158	static
159	unsigned long hash_pointer(const void *_key, unsigned long seed)
160	{
161	union {
162	uint64_t v64;
163	uint32_t v32[2];
164	} v;
165	union {
166	uint64_t v64;
167	uint32_t v32[2];
168	} key;
169
170	v.v64 = (uint64_t) seed;
171	key.v64 = (uint64_t) _key;
172	hashword2(key.v32, 2, &v.v32[0], &v.v32[1]);
173	return v.v64;
174	}
175	#endif
176
177	static
178	int match_pointer(struct cds_lfht_node node, const void key)
179	{
180	struct rcu_ja_shadow_node *shadow =
181	caa_container_of(node, struct rcu_ja_shadow_node, ht_node);
182
183	return (key == shadow->node);
184	}
185
186	__attribute__((visibility("protected")))
187	struct rcu_ja_shadow_node rcuja_shadow_lookup_lock(struct cds_lfht ht,
188	struct rcu_ja_node *node)
189	{
190	struct cds_lfht_iter iter;
191	struct cds_lfht_node *lookup_node;
192	struct rcu_ja_shadow_node *shadow_node;
193	int ret;
194
195	rcu_read_lock();
196	cds_lfht_lookup(ht, hash_pointer(node, hash_seed),
197	match_pointer, node, &iter);
198
199	lookup_node = cds_lfht_iter_get_node(&iter);
200	if (!lookup_node) {
201	shadow_node = NULL;
202	goto rcu_unlock;
203	}
204	shadow_node = caa_container_of(lookup_node,
205	struct rcu_ja_shadow_node, ht_node);
206	ret = pthread_mutex_lock(&shadow_node->lock);
207	assert(!ret);
208	if (cds_lfht_is_node_deleted(lookup_node)) {
209	ret = pthread_mutex_unlock(&shadow_node->lock);
210	assert(!ret);
211	shadow_node = NULL;
212	}
213	rcu_unlock:
214	rcu_read_unlock();
215	return shadow_node;
216	}
217
25fde237	218	__attribute__((visibility("protected")))
d22c185b MD	219	void rcuja_shadow_unlock(struct rcu_ja_shadow_node *shadow_node)
	220	{
	221	int ret;
	222
	223	ret = pthread_mutex_unlock(&shadow_node->lock);
	224	assert(!ret);
	225	}
	226
	227	__attribute__((visibility("protected")))
	228	int rcuja_shadow_set(struct cds_lfht *ht,
	229	struct rcu_ja_node *node)
	230	{
	231	struct rcu_ja_shadow_node *shadow_node;
	232	struct cds_lfht_node *ret_node;
	233
	234	shadow_node = calloc(sizeof(*shadow_node), 1);
	235	if (!shadow_node)
	236	return -ENOMEM;
	237
	238	shadow_node->node = node;
	239	pthread_mutex_init(&shadow_node->lock, NULL);
	240
	241	rcu_read_lock();
	242	ret_node = cds_lfht_add_unique(ht,
	243	hash_pointer(node, hash_seed),
	244	match_pointer,
	245	node,
	246	&shadow_node->ht_node);
	247	rcu_read_unlock();
	248
	249	if (ret_node != &shadow_node->ht_node) {
	250	free(shadow_node);
	251	return -EEXIST;
	252	}
	253	return 0;
	254	}
	255
	256	static
25fde237	257	void free_shadow_node_and_node(struct rcu_head *head)
d22c185b MD	258	{
	259	struct rcu_ja_shadow_node *shadow_node =
	260	caa_container_of(head, struct rcu_ja_shadow_node, head);
25fde237	261	free(shadow_node->node);
d22c185b MD	262	free(shadow_node);
	263	}
	264
	265	__attribute__((visibility("protected")))
25fde237	266	int rcuja_shadow_clear_and_free_node(struct cds_lfht *ht,
d22c185b MD	267	struct rcu_ja_node *node)
	268	{
	269	struct cds_lfht_iter iter;
	270	struct cds_lfht_node *lookup_node;
	271	struct rcu_ja_shadow_node *shadow_node;
	272	int ret, lockret;
	273
	274	rcu_read_lock();
	275	cds_lfht_lookup(ht, hash_pointer(node, hash_seed),
	276	match_pointer, node, &iter);
	277	lookup_node = cds_lfht_iter_get_node(&iter);
	278	if (!lookup_node) {
	279	ret = -ENOENT;
	280	goto rcu_unlock;
	281	}
	282	shadow_node = caa_container_of(lookup_node,
	283	struct rcu_ja_shadow_node, ht_node);
	284	lockret = pthread_mutex_lock(&shadow_node->lock);
	285	assert(!lockret);
	286
	287	/*
	288	* Holding the mutex across deletion, and by also re-checking if
	289	* the node is deleted with mutex held at lookup ensure that we
	290	* don't let RCU JA use a node being removed.
	291	*/
	292	ret = cds_lfht_del(ht, lookup_node);
	293	if (!ret) {
25fde237	294	call_rcu(&shadow_node->head, free_shadow_node_and_node);
d22c185b MD	295	}
	296	lockret = pthread_mutex_unlock(&shadow_node->lock);
	297	assert(!lockret);
	298	rcu_unlock:
	299	rcu_read_unlock();
	300
	301	return ret;
	302	}
	303
195e72d3 MD	304	__attribute__((visibility("protected")))
	305	struct cds_lfht *rcuja_create_ht(void)
	306	{
	307	return cds_lfht_new(1, 1, 0,
	308	CDS_LFHT_AUTO_RESIZE \| CDS_LFHT_ACCOUNTING,
	309	NULL);
	310	}
	311
	312	__attribute__((visibility("protected")))
	313	void rcuja_delete_ht(struct cds_lfht *ht)
	314	{
	315	int ret;
	316
	317	ret = cds_lfht_destroy(ht, NULL);
	318	assert(!ret);
	319	}
d22c185b MD	320
	321	__attribute__((constructor))
	322	void rcuja_ht_init(void)
	323	{
	324	hash_seed = (unsigned long) time(NULL);
	325	}