[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;
}

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(struct rcu_head *head)
{
	struct rcu_ja_shadow_node *shadow_node =
		caa_container_of(head, struct rcu_ja_shadow_node, head);
	free(shadow_node);
}

__attribute__((visibility("protected")))
int rcuja_shadow_clear(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);
	}
	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
218	void rcuja_shadow_unlock(struct rcu_ja_shadow_node *shadow_node)
219	{
220	int ret;
221
222	ret = pthread_mutex_unlock(&shadow_node->lock);
223	assert(!ret);
224	}
225
226	__attribute__((visibility("protected")))
227	int rcuja_shadow_set(struct cds_lfht *ht,
228	struct rcu_ja_node *node)
229	{
230	struct rcu_ja_shadow_node *shadow_node;
231	struct cds_lfht_node *ret_node;
232
233	shadow_node = calloc(sizeof(*shadow_node), 1);
234	if (!shadow_node)
235	return -ENOMEM;
236
237	shadow_node->node = node;
238	pthread_mutex_init(&shadow_node->lock, NULL);
239
240	rcu_read_lock();
241	ret_node = cds_lfht_add_unique(ht,
242	hash_pointer(node, hash_seed),
243	match_pointer,
244	node,
245	&shadow_node->ht_node);
246	rcu_read_unlock();
247
248	if (ret_node != &shadow_node->ht_node) {
249	free(shadow_node);
250	return -EEXIST;
251	}
252	return 0;
253	}
254
255	static
256	void free_shadow_node(struct rcu_head *head)
257	{
258	struct rcu_ja_shadow_node *shadow_node =
259	caa_container_of(head, struct rcu_ja_shadow_node, head);
260	free(shadow_node);
261	}
262
263	__attribute__((visibility("protected")))
264	int rcuja_shadow_clear(struct cds_lfht *ht,
265	struct rcu_ja_node *node)
266	{
267	struct cds_lfht_iter iter;
268	struct cds_lfht_node *lookup_node;
269	struct rcu_ja_shadow_node *shadow_node;
270	int ret, lockret;
271
272	rcu_read_lock();
273	cds_lfht_lookup(ht, hash_pointer(node, hash_seed),
274	match_pointer, node, &iter);
275	lookup_node = cds_lfht_iter_get_node(&iter);
276	if (!lookup_node) {
277	ret = -ENOENT;
278	goto rcu_unlock;
279	}
280	shadow_node = caa_container_of(lookup_node,
281	struct rcu_ja_shadow_node, ht_node);
282	lockret = pthread_mutex_lock(&shadow_node->lock);
283	assert(!lockret);
284
285	/*
286	* Holding the mutex across deletion, and by also re-checking if
287	* the node is deleted with mutex held at lookup ensure that we
288	* don't let RCU JA use a node being removed.
289	*/
290	ret = cds_lfht_del(ht, lookup_node);
291	if (!ret) {
292	call_rcu(&shadow_node->head, free_shadow_node);
293	}
294	lockret = pthread_mutex_unlock(&shadow_node->lock);
295	assert(!lockret);
296	rcu_unlock:
297	rcu_read_unlock();
298
299	return ret;
300	}
301
195e72d3 MD	302	__attribute__((visibility("protected")))
	303	struct cds_lfht *rcuja_create_ht(void)
	304	{
	305	return cds_lfht_new(1, 1, 0,
	306	CDS_LFHT_AUTO_RESIZE \| CDS_LFHT_ACCOUNTING,
	307	NULL);
	308	}
	309
	310	__attribute__((visibility("protected")))
	311	void rcuja_delete_ht(struct cds_lfht *ht)
	312	{
	313	int ret;
	314
	315	ret = cds_lfht_destroy(ht, NULL);
	316	assert(!ret);
	317	}
d22c185b MD	318
	319	__attribute__((constructor))
	320	void rcuja_ht_init(void)
	321	{
	322	hash_seed = (unsigned long) time(NULL);
	323	}