[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>
#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;
	const struct rcu_flavor_struct *flavor;
	int ret;

	flavor = cds_lfht_rcu_flavor(ht);
	flavor->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:
	flavor->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 *new_node,
		struct rcu_ja_shadow_node *inherit_from)
{
	struct rcu_ja_shadow_node *shadow_node;
	struct cds_lfht_node *ret_node;
	const struct rcu_flavor_struct *flavor;

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

	shadow_node->node = new_node;
	/*
	 * Lock can be inherited from previous node at this position.
	 */
	if (inherit_from) {
		shadow_node->lock = inherit_from->lock;
	} else {
		shadow_node->lock = calloc(sizeof(*shadow_node->lock), 1);
		if (!shadow_node->lock) {
			free(shadow_node);
			return -ENOMEM;
		}
		pthread_mutex_init(shadow_node->lock, NULL);
	}

	flavor = cds_lfht_rcu_flavor(ht);
	flavor->read_lock();
	ret_node = cds_lfht_add_unique(ht,
			hash_pointer(new_node, hash_seed),
			match_pointer,
			new_node,
			&shadow_node->ht_node);
	flavor->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);
}

static
void free_shadow_node_and_node_and_lock(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->lock);
	free(shadow_node);
}

__attribute__((visibility("protected")))
int rcuja_shadow_clear(struct cds_lfht *ht,
		struct rcu_ja_node *node,
		unsigned int flags)
{
	struct cds_lfht_iter iter;
	struct cds_lfht_node *lookup_node;
	struct rcu_ja_shadow_node *shadow_node;
	const struct rcu_flavor_struct *flavor;
	int ret, lockret;

	flavor = cds_lfht_rcu_flavor(ht);
	flavor->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) {
		assert(flags & RCUJA_SHADOW_CLEAR_FREE_NODE);
		if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
			flavor->update_call_rcu(&shadow_node->head,
				free_shadow_node_and_node_and_lock);
		} else {
			flavor->update_call_rcu(&shadow_node->head,
				free_shadow_node_and_node);
		}
	}
	lockret = pthread_mutex_unlock(shadow_node->lock);
	assert(!lockret);
rcu_unlock:
	flavor->read_unlock();

	return ret;
}

__attribute__((visibility("protected")))
struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor)
{
	return _cds_lfht_new(1, 1, 0,
		CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING,
		NULL, flavor, 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>
195e72d3 MD	27	#include <urcu/rcuja.h>
	28	#include <urcu/compiler.h>
	29	#include <urcu/arch.h>
	30	#include <assert.h>
	31	#include <urcu-pointer.h>
d22c185b MD	32	#include <stdlib.h>
d22c185b MD	33	#include <time.h>
195e72d3 MD	34
	35	#include "rcuja-internal.h"
	36	#include "bitfield.h"
	37
d22c185b MD	38	static unsigned long hash_seed;
	39
	40	/*
	41	* Hash function
	42	* Source: http://burtleburtle.net/bob/c/lookup3.c
	43	* Originally Public Domain
	44	*/
	45
	46	#define rot(x, k) (((x) << (k)) \| ((x) >> (32 - (k))))
	47
	48	#define mix(a, b, c) \
	49	do { \
	50	a -= c; a ^= rot(c, 4); c += b; \
	51	b -= a; b ^= rot(a, 6); a += c; \
	52	c -= b; c ^= rot(b, 8); b += a; \
	53	a -= c; a ^= rot(c, 16); c += b; \
	54	b -= a; b ^= rot(a, 19); a += c; \
	55	c -= b; c ^= rot(b, 4); b += a; \
	56	} while (0)
	57
	58	#define final(a, b, c) \
	59	{ \
	60	c ^= b; c -= rot(b, 14); \
	61	a ^= c; a -= rot(c, 11); \
	62	b ^= a; b -= rot(a, 25); \
	63	c ^= b; c -= rot(b, 16); \
	64	a ^= c; a -= rot(c, 4);\
	65	b ^= a; b -= rot(a, 14); \
	66	c ^= b; c -= rot(b, 24); \
	67	}
	68
	69	static inline __attribute__((unused))
	70	uint32_t hash_u32(
	71	const uint32_t k, / the key, an array of uint32_t values */
	72	size_t length, /* the length of the key, in uint32_ts */
	73	uint32_t initval) /* the previous hash, or an arbitrary value */
	74	{
	75	uint32_t a, b, c;
	76
	77	/* Set up the internal state */
	78	a = b = c = 0xdeadbeef + (((uint32_t) length) << 2) + initval;
	79
	80	/----------------------------------------- handle most of the key /
	81	while (length > 3) {
	82	a += k[0];
	83	b += k[1];
	84	c += k[2];
	85	mix(a, b, c);
	86	length -= 3;
	87	k += 3;
	88	}
	89
	90	/----------------------------------- handle the last 3 uint32_t's /
	91	switch (length) { /* all the case statements fall through */
	92	case 3: c += k[2];
	93	case 2: b += k[1];
	94	case 1: a += k[0];
	95	final(a, b, c);
	96	case 0: /* case 0: nothing left to add */
	97	break;
	98	}
	99	/---------------------------------------------- report the result /
	100	return c;
	101	}
102
103	static inline
104	void hashword2(
105	const uint32_t k, / the key, an array of uint32_t values */
106	size_t length, /* the length of the key, in uint32_ts */
107	uint32_t pc, / IN: seed OUT: primary hash value */
108	uint32_t pb) / IN: more seed OUT: secondary hash value */
109	{
110	uint32_t a, b, c;
111
112	/* Set up the internal state */
113	a = b = c = 0xdeadbeef + ((uint32_t) (length << 2)) + *pc;
114	c += *pb;
115
116	/----------------------------------------- handle most of the key /
117	while (length > 3) {
118	a += k[0];
119	b += k[1];
120	c += k[2];
121	mix(a, b, c);
122	length -= 3;
123	k += 3;
124	}
125
126	/----------------------------------- handle the last 3 uint32_t's /
127	switch (length) { /* all the case statements fall through */
128	case 3: c += k[2];
129	case 2: b += k[1];
130	case 1: a += k[0];
131	final(a, b, c);
132	case 0: /* case 0: nothing left to add */
133	break;
134	}
135	/---------------------------------------------- report the result /
136	*pc = c;
137	*pb = b;
138	}
139
140	#if (CAA_BITS_PER_LONG == 32)
141	static
142	unsigned long hash_pointer(const void *_key, unsigned long seed)
143	{
144	unsigned int key = (unsigned int) _key;
145
146	return hash_u32(&key, 1, seed);
147	}
148	#else
149	static
150	unsigned long hash_pointer(const void *_key, unsigned long seed)
151	{
152	union {
153	uint64_t v64;
154	uint32_t v32[2];
155	} v;
156	union {
157	uint64_t v64;
158	uint32_t v32[2];
159	} key;
160
161	v.v64 = (uint64_t) seed;
162	key.v64 = (uint64_t) _key;
163	hashword2(key.v32, 2, &v.v32[0], &v.v32[1]);
164	return v.v64;
165	}
166	#endif
167
168	static
169	int match_pointer(struct cds_lfht_node node, const void key)
170	{
171	struct rcu_ja_shadow_node *shadow =
172	caa_container_of(node, struct rcu_ja_shadow_node, ht_node);
173
174	return (key == shadow->node);
175	}
176
177	__attribute__((visibility("protected")))
178	struct rcu_ja_shadow_node rcuja_shadow_lookup_lock(struct cds_lfht ht,
179	struct rcu_ja_node *node)
180	{
181	struct cds_lfht_iter iter;
182	struct cds_lfht_node *lookup_node;
183	struct rcu_ja_shadow_node *shadow_node;
5eb692c0	184	const struct rcu_flavor_struct *flavor;
d22c185b MD	185	int ret;
d22c185b MD	186
5eb692c0 MD	187	flavor = cds_lfht_rcu_flavor(ht);
5eb692c0 MD	188	flavor->read_lock();
d22c185b MD	189	cds_lfht_lookup(ht, hash_pointer(node, hash_seed),
	190	match_pointer, node, &iter);
	191
	192	lookup_node = cds_lfht_iter_get_node(&iter);
	193	if (!lookup_node) {
	194	shadow_node = NULL;
	195	goto rcu_unlock;
	196	}
	197	shadow_node = caa_container_of(lookup_node,
	198	struct rcu_ja_shadow_node, ht_node);
e1db2db5	199	ret = pthread_mutex_lock(shadow_node->lock);
d22c185b MD	200	assert(!ret);
d22c185b MD	201	if (cds_lfht_is_node_deleted(lookup_node)) {
e1db2db5	202	ret = pthread_mutex_unlock(shadow_node->lock);
d22c185b MD	203	assert(!ret);
	204	shadow_node = NULL;
	205	}
	206	rcu_unlock:
5eb692c0	207	flavor->read_unlock();
d22c185b MD	208	return shadow_node;
	209	}
	210
25fde237	211	__attribute__((visibility("protected")))
d22c185b MD	212	void rcuja_shadow_unlock(struct rcu_ja_shadow_node *shadow_node)
	213	{
	214	int ret;
	215
e1db2db5	216	ret = pthread_mutex_unlock(shadow_node->lock);
d22c185b MD	217	assert(!ret);
	218	}
	219
	220	__attribute__((visibility("protected")))
	221	int rcuja_shadow_set(struct cds_lfht *ht,
e1db2db5 MD	222	struct rcu_ja_node *new_node,
e1db2db5 MD	223	struct rcu_ja_shadow_node *inherit_from)
d22c185b MD	224	{
	225	struct rcu_ja_shadow_node *shadow_node;
	226	struct cds_lfht_node *ret_node;
5eb692c0	227	const struct rcu_flavor_struct *flavor;
d22c185b MD	228
	229	shadow_node = calloc(sizeof(*shadow_node), 1);
	230	if (!shadow_node)
	231	return -ENOMEM;
	232
e1db2db5 MD	233	shadow_node->node = new_node;
	234	/*
	235	* Lock can be inherited from previous node at this position.
	236	*/
	237	if (inherit_from) {
	238	shadow_node->lock = inherit_from->lock;
	239	} else {
	240	shadow_node->lock = calloc(sizeof(*shadow_node->lock), 1);
	241	if (!shadow_node->lock) {
	242	free(shadow_node);
	243	return -ENOMEM;
	244	}
	245	pthread_mutex_init(shadow_node->lock, NULL);
	246	}
d22c185b	247
5eb692c0 MD	248	flavor = cds_lfht_rcu_flavor(ht);
5eb692c0 MD	249	flavor->read_lock();
d22c185b	250	ret_node = cds_lfht_add_unique(ht,
e1db2db5	251	hash_pointer(new_node, hash_seed),
d22c185b	252	match_pointer,
e1db2db5	253	new_node,
d22c185b	254	&shadow_node->ht_node);
5eb692c0	255	flavor->read_unlock();
d22c185b MD	256
	257	if (ret_node != &shadow_node->ht_node) {
	258	free(shadow_node);
	259	return -EEXIST;
	260	}
	261	return 0;
	262	}
	263
	264	static
25fde237	265	void free_shadow_node_and_node(struct rcu_head *head)
d22c185b MD	266	{
	267	struct rcu_ja_shadow_node *shadow_node =
	268	caa_container_of(head, struct rcu_ja_shadow_node, head);
25fde237	269	free(shadow_node->node);
d22c185b MD	270	free(shadow_node);
	271	}
	272
e1db2db5 MD	273	static
	274	void free_shadow_node_and_node_and_lock(struct rcu_head *head)
	275	{
	276	struct rcu_ja_shadow_node *shadow_node =
	277	caa_container_of(head, struct rcu_ja_shadow_node, head);
	278	free(shadow_node->node);
	279	free(shadow_node->lock);
	280	free(shadow_node);
	281	}
	282
d22c185b	283	__attribute__((visibility("protected")))
e1db2db5 MD	284	int rcuja_shadow_clear(struct cds_lfht *ht,
	285	struct rcu_ja_node *node,
	286	unsigned int flags)
d22c185b MD	287	{
	288	struct cds_lfht_iter iter;
	289	struct cds_lfht_node *lookup_node;
	290	struct rcu_ja_shadow_node *shadow_node;
5eb692c0	291	const struct rcu_flavor_struct *flavor;
d22c185b MD	292	int ret, lockret;
d22c185b MD	293
5eb692c0 MD	294	flavor = cds_lfht_rcu_flavor(ht);
5eb692c0 MD	295	flavor->read_lock();
d22c185b MD	296	cds_lfht_lookup(ht, hash_pointer(node, hash_seed),
	297	match_pointer, node, &iter);
	298	lookup_node = cds_lfht_iter_get_node(&iter);
	299	if (!lookup_node) {
	300	ret = -ENOENT;
	301	goto rcu_unlock;
	302	}
	303	shadow_node = caa_container_of(lookup_node,
	304	struct rcu_ja_shadow_node, ht_node);
e1db2db5	305	lockret = pthread_mutex_lock(shadow_node->lock);
d22c185b MD	306	assert(!lockret);
	307
	308	/*
	309	* Holding the mutex across deletion, and by also re-checking if
	310	* the node is deleted with mutex held at lookup ensure that we
	311	* don't let RCU JA use a node being removed.
	312	*/
	313	ret = cds_lfht_del(ht, lookup_node);
	314	if (!ret) {
e1db2db5 MD	315	assert(flags & RCUJA_SHADOW_CLEAR_FREE_NODE);
	316	if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
	317	flavor->update_call_rcu(&shadow_node->head,
	318	free_shadow_node_and_node_and_lock);
	319	} else {
	320	flavor->update_call_rcu(&shadow_node->head,
	321	free_shadow_node_and_node);
	322	}
d22c185b	323	}
e1db2db5	324	lockret = pthread_mutex_unlock(shadow_node->lock);
d22c185b MD	325	assert(!lockret);
d22c185b MD	326	rcu_unlock:
5eb692c0	327	flavor->read_unlock();
d22c185b MD	328
	329	return ret;
	330	}
	331
195e72d3	332	__attribute__((visibility("protected")))
5eb692c0	333	struct cds_lfht rcuja_create_ht(const struct rcu_flavor_struct flavor)
195e72d3	334	{
5eb692c0	335	return _cds_lfht_new(1, 1, 0,
195e72d3	336	CDS_LFHT_AUTO_RESIZE \| CDS_LFHT_ACCOUNTING,
5eb692c0	337	NULL, flavor, NULL);
195e72d3 MD	338	}
	339
	340	__attribute__((visibility("protected")))
	341	void rcuja_delete_ht(struct cds_lfht *ht)
	342	{
	343	int ret;
	344
	345	ret = cds_lfht_destroy(ht, NULL);
	346	assert(!ret);
	347	}
d22c185b MD	348
	349	__attribute__((constructor))
	350	void rcuja_ht_init(void)
	351	{
	352	hash_seed = (unsigned long) time(NULL);
	353	}