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

/*
 * rcuja/rcuja-hashtable.c
 *
 * Userspace RCU library - RCU Judy Array Shadow Node Hash Table
 *
 * Copyright 2012-2013 - 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 <assert.h>
#include <stdlib.h>
#include <time.h>
#include <urcu/rcuja.h>
#include <urcu/compiler.h>
#include <urcu/arch.h>
#include <urcu-pointer.h>

#include "rcuja-internal.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 cds_ja_shadow_node *shadow =
		caa_container_of(node, struct cds_ja_shadow_node, ht_node);

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

__attribute__((visibility("protected")))
struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht,
		struct cds_ja_inode_flag *node_flag)
{
	struct cds_lfht_iter iter;
	struct cds_lfht_node *lookup_node;
	struct cds_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_flag, hash_seed),
			match_pointer, node_flag, &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 cds_ja_shadow_node, ht_node);
	dbg_printf("Lock %p\n", shadow_node->lock);
	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 cds_ja_shadow_node *shadow_node)
{
	int ret;

	dbg_printf("Unlock %p\n", shadow_node->lock);
	ret = pthread_mutex_unlock(shadow_node->lock);
	assert(!ret);
}

__attribute__((visibility("protected")))
struct cds_ja_shadow_node *rcuja_shadow_set(struct cds_lfht *ht,
		struct cds_ja_inode_flag *new_node_flag,
		struct cds_ja_shadow_node *inherit_from,
		struct cds_ja *ja, int level)
{
	struct cds_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 NULL;

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

	flavor = cds_lfht_rcu_flavor(ht);
	flavor->read_lock();
	ret_node = cds_lfht_add_unique(ht,
			hash_pointer(new_node_flag, hash_seed),
			match_pointer,
			new_node_flag,
			&shadow_node->ht_node);
	flavor->read_unlock();

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

static
void free_shadow_node(struct rcu_head *head)
{
	struct cds_ja_shadow_node *shadow_node =
		caa_container_of(head, struct cds_ja_shadow_node, head);
	free(shadow_node);
}

static
void free_shadow_node_and_node(struct rcu_head *head)
{
	struct cds_ja_shadow_node *shadow_node =
		caa_container_of(head, struct cds_ja_shadow_node, head);
	free_cds_ja_node(shadow_node->ja, ja_node_ptr(shadow_node->node_flag));
	free(shadow_node);
}

static
void free_shadow_node_and_lock(struct rcu_head *head)
{
	struct cds_ja_shadow_node *shadow_node =
		caa_container_of(head, struct cds_ja_shadow_node, head);
	free(shadow_node->lock);
	free(shadow_node);
}

static
void free_shadow_node_and_node_and_lock(struct rcu_head *head)
{
	struct cds_ja_shadow_node *shadow_node =
		caa_container_of(head, struct cds_ja_shadow_node, head);
	assert(shadow_node->level);
	free_cds_ja_node(shadow_node->ja, ja_node_ptr(shadow_node->node_flag));
	free(shadow_node->lock);
	free(shadow_node);
}

__attribute__((visibility("protected")))
int rcuja_shadow_clear(struct cds_lfht *ht,
		struct cds_ja_inode_flag *node_flag,
		struct cds_ja_shadow_node *shadow_node,
		unsigned int flags)
{
	struct cds_lfht_iter iter;
	struct cds_lfht_node *lookup_node;
	const struct rcu_flavor_struct *flavor;
	int ret, lockret;
	int lookup_shadow = 0;

	flavor = cds_lfht_rcu_flavor(ht);
	flavor->read_lock();

	cds_lfht_lookup(ht, hash_pointer(node_flag, hash_seed),
			match_pointer, node_flag, &iter);
	lookup_node = cds_lfht_iter_get_node(&iter);
	if (!lookup_node) {
		ret = -ENOENT;
		goto rcu_unlock;
	}

	if (!shadow_node) {
		shadow_node = caa_container_of(lookup_node,
				struct cds_ja_shadow_node, ht_node);
		lockret = pthread_mutex_lock(shadow_node->lock);
		assert(!lockret);
		lookup_shadow = 1;
	}

	/*
	 * 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)
		goto unlock;
	if ((flags & RCUJA_SHADOW_CLEAR_FREE_NODE)
			&& shadow_node->level) {
		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);
		}
	} else {
		if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
			flavor->update_call_rcu(&shadow_node->head,
				free_shadow_node_and_lock);
		} else {
			flavor->update_call_rcu(&shadow_node->head,
				free_shadow_node);
		}
	}
unlock:
	if (lookup_shadow) {
		lockret = pthread_mutex_unlock(shadow_node->lock);
		assert(!lockret);
	}
rcu_unlock:
	flavor->read_unlock();

	return ret;
}

/*
 * Delete all shadow nodes and nodes from hash table, along with their
 * associated lock.
 */
__attribute__((visibility("protected")))
void rcuja_shadow_prune(struct cds_lfht *ht,
		unsigned int flags)
{
	const struct rcu_flavor_struct *flavor;
	struct cds_ja_shadow_node *shadow_node;
	struct cds_lfht_iter iter;
	int ret, lockret;

	flavor = cds_lfht_rcu_flavor(ht);
	/*
	 * Read-side lock is needed to ensure hash table node existence
	 * vs concurrent resize.
	 */
	flavor->read_lock();
	cds_lfht_for_each_entry(ht, &iter, shadow_node, ht_node) {
		lockret = pthread_mutex_lock(shadow_node->lock);
		assert(!lockret);
	
		ret = cds_lfht_del(ht, &shadow_node->ht_node);
		if (ret)
			goto unlock;
		if ((flags & RCUJA_SHADOW_CLEAR_FREE_NODE)
				&& shadow_node->level) {
			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);
			}
		} else {
			if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
				flavor->update_call_rcu(&shadow_node->head,
					free_shadow_node_and_lock);
			} else {
				flavor->update_call_rcu(&shadow_node->head,
					free_shadow_node);
			}
		}
	unlock:
		lockret = pthread_mutex_unlock(shadow_node->lock);
		assert(!lockret);
	}
	flavor->read_unlock();
}

__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")))
int rcuja_delete_ht(struct cds_lfht *ht)
{
	return cds_lfht_destroy(ht, NULL);
}

__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	*
170e1186	6	* Copyright 2012-2013 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
195e72d3 MD	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>
41b52c29 MD	27	#include <assert.h>
	28	#include <stdlib.h>
	29	#include <time.h>
195e72d3 MD	30	#include <urcu/rcuja.h>
	31	#include <urcu/compiler.h>
	32	#include <urcu/arch.h>
195e72d3 MD	33	#include <urcu-pointer.h>
	34
	35	#include "rcuja-internal.h"
195e72d3	36
d22c185b MD	37	static unsigned long hash_seed;
	38
	39	/*
	40	* Hash function
	41	* Source: http://burtleburtle.net/bob/c/lookup3.c
	42	* Originally Public Domain
	43	*/
	44
	45	#define rot(x, k) (((x) << (k)) \| ((x) >> (32 - (k))))
	46
	47	#define mix(a, b, c) \
	48	do { \
	49	a -= c; a ^= rot(c, 4); c += b; \
	50	b -= a; b ^= rot(a, 6); a += c; \
	51	c -= b; c ^= rot(b, 8); b += a; \
	52	a -= c; a ^= rot(c, 16); c += b; \
	53	b -= a; b ^= rot(a, 19); a += c; \
	54	c -= b; c ^= rot(b, 4); b += a; \
	55	} while (0)
	56
	57	#define final(a, b, c) \
	58	{ \
	59	c ^= b; c -= rot(b, 14); \
	60	a ^= c; a -= rot(c, 11); \
	61	b ^= a; b -= rot(a, 25); \
	62	c ^= b; c -= rot(b, 16); \
	63	a ^= c; a -= rot(c, 4);\
	64	b ^= a; b -= rot(a, 14); \
	65	c ^= b; c -= rot(b, 24); \
	66	}
	67
	68	static inline __attribute__((unused))
	69	uint32_t hash_u32(
	70	const uint32_t k, / the key, an array of uint32_t values */
	71	size_t length, /* the length of the key, in uint32_ts */
	72	uint32_t initval) /* the previous hash, or an arbitrary value */
	73	{
	74	uint32_t a, b, c;
	75
	76	/* Set up the internal state */
	77	a = b = c = 0xdeadbeef + (((uint32_t) length) << 2) + initval;
	78
	79	/----------------------------------------- handle most of the key /
	80	while (length > 3) {
	81	a += k[0];
	82	b += k[1];
	83	c += k[2];
	84	mix(a, b, c);
	85	length -= 3;
	86	k += 3;
	87	}
	88
	89	/----------------------------------- handle the last 3 uint32_t's /
	90	switch (length) { /* all the case statements fall through */
	91	case 3: c += k[2];
	92	case 2: b += k[1];
	93	case 1: a += k[0];
	94	final(a, b, c);
	95	case 0: /* case 0: nothing left to add */
	96	break;
	97	}
	98	/---------------------------------------------- report the result /
	99	return c;
	100	}
101
102	static inline
103	void hashword2(
104	const uint32_t k, / the key, an array of uint32_t values */
105	size_t length, /* the length of the key, in uint32_ts */
106	uint32_t pc, / IN: seed OUT: primary hash value */
107	uint32_t pb) / IN: more seed OUT: secondary hash value */
108	{
109	uint32_t a, b, c;
110
111	/* Set up the internal state */
112	a = b = c = 0xdeadbeef + ((uint32_t) (length << 2)) + *pc;
113	c += *pb;
114
115	/----------------------------------------- handle most of the key /
116	while (length > 3) {
117	a += k[0];
118	b += k[1];
119	c += k[2];
120	mix(a, b, c);
121	length -= 3;
122	k += 3;
123	}
124
125	/----------------------------------- handle the last 3 uint32_t's /
126	switch (length) { /* all the case statements fall through */
127	case 3: c += k[2];
128	case 2: b += k[1];
129	case 1: a += k[0];
130	final(a, b, c);
131	case 0: /* case 0: nothing left to add */
132	break;
133	}
134	/---------------------------------------------- report the result /
135	*pc = c;
136	*pb = b;
137	}
138
139	#if (CAA_BITS_PER_LONG == 32)
140	static
141	unsigned long hash_pointer(const void *_key, unsigned long seed)
142	{
143	unsigned int key = (unsigned int) _key;
144
145	return hash_u32(&key, 1, seed);
146	}
147	#else
148	static
149	unsigned long hash_pointer(const void *_key, unsigned long seed)
150	{
151	union {
152	uint64_t v64;
153	uint32_t v32[2];
154	} v;
155	union {
156	uint64_t v64;
157	uint32_t v32[2];
158	} key;
159
160	v.v64 = (uint64_t) seed;
161	key.v64 = (uint64_t) _key;
162	hashword2(key.v32, 2, &v.v32[0], &v.v32[1]);
163	return v.v64;
164	}
165	#endif
166
167	static
168	int match_pointer(struct cds_lfht_node node, const void key)
169	{
d96bfb0d MD	170	struct cds_ja_shadow_node *shadow =
d96bfb0d MD	171	caa_container_of(node, struct cds_ja_shadow_node, ht_node);
d22c185b	172
3d8fe307	173	return (key == shadow->node_flag);
d22c185b MD	174	}
	175
	176	__attribute__((visibility("protected")))
d96bfb0d	177	struct cds_ja_shadow_node rcuja_shadow_lookup_lock(struct cds_lfht ht,
3d8fe307	178	struct cds_ja_inode_flag *node_flag)
d22c185b MD	179	{
	180	struct cds_lfht_iter iter;
	181	struct cds_lfht_node *lookup_node;
d96bfb0d	182	struct cds_ja_shadow_node *shadow_node;
5eb692c0	183	const struct rcu_flavor_struct *flavor;
d22c185b MD	184	int ret;
d22c185b MD	185
5eb692c0 MD	186	flavor = cds_lfht_rcu_flavor(ht);
5eb692c0 MD	187	flavor->read_lock();
3d8fe307 MD	188	cds_lfht_lookup(ht, hash_pointer(node_flag, hash_seed),
3d8fe307 MD	189	match_pointer, node_flag, &iter);
d22c185b MD	190
	191	lookup_node = cds_lfht_iter_get_node(&iter);
	192	if (!lookup_node) {
	193	shadow_node = NULL;
	194	goto rcu_unlock;
	195	}
	196	shadow_node = caa_container_of(lookup_node,
d96bfb0d	197	struct cds_ja_shadow_node, ht_node);
a2a7ff59	198	dbg_printf("Lock %p\n", shadow_node->lock);
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")))
d96bfb0d	212	void rcuja_shadow_unlock(struct cds_ja_shadow_node *shadow_node)
d22c185b MD	213	{
	214	int ret;
	215
a2a7ff59	216	dbg_printf("Unlock %p\n", shadow_node->lock);
e1db2db5	217	ret = pthread_mutex_unlock(shadow_node->lock);
d22c185b MD	218	assert(!ret);
	219	}
	220
	221	__attribute__((visibility("protected")))
f07b240f	222	struct cds_ja_shadow_node rcuja_shadow_set(struct cds_lfht ht,
3d8fe307 MD	223	struct cds_ja_inode_flag *new_node_flag,
3d8fe307 MD	224	struct cds_ja_shadow_node *inherit_from,
48cbe001	225	struct cds_ja *ja, int level)
d22c185b	226	{
d96bfb0d	227	struct cds_ja_shadow_node *shadow_node;
d22c185b	228	struct cds_lfht_node *ret_node;
5eb692c0	229	const struct rcu_flavor_struct *flavor;
d22c185b MD	230
	231	shadow_node = calloc(sizeof(*shadow_node), 1);
	232	if (!shadow_node)
f07b240f	233	return NULL;
d22c185b	234
3d8fe307 MD	235	shadow_node->node_flag = new_node_flag;
3d8fe307 MD	236	shadow_node->ja = ja;
e1db2db5 MD	237	/*
	238	* Lock can be inherited from previous node at this position.
	239	*/
	240	if (inherit_from) {
	241	shadow_node->lock = inherit_from->lock;
48cbe001	242	shadow_node->level = inherit_from->level;
e1db2db5 MD	243	} else {
	244	shadow_node->lock = calloc(sizeof(*shadow_node->lock), 1);
	245	if (!shadow_node->lock) {
	246	free(shadow_node);
f07b240f	247	return NULL;
e1db2db5 MD	248	}
e1db2db5 MD	249	pthread_mutex_init(shadow_node->lock, NULL);
48cbe001	250	shadow_node->level = level;
e1db2db5	251	}
d22c185b	252
5eb692c0 MD	253	flavor = cds_lfht_rcu_flavor(ht);
5eb692c0 MD	254	flavor->read_lock();
d22c185b	255	ret_node = cds_lfht_add_unique(ht,
3d8fe307	256	hash_pointer(new_node_flag, hash_seed),
d22c185b	257	match_pointer,
3d8fe307	258	new_node_flag,
d22c185b	259	&shadow_node->ht_node);
5eb692c0	260	flavor->read_unlock();
d22c185b MD	261
	262	if (ret_node != &shadow_node->ht_node) {
	263	free(shadow_node);
f07b240f	264	return NULL;
d22c185b	265	}
f07b240f	266	return shadow_node;
d22c185b MD	267	}
d22c185b MD	268
a2a7ff59 MD	269	static
	270	void free_shadow_node(struct rcu_head *head)
	271	{
	272	struct cds_ja_shadow_node *shadow_node =
	273	caa_container_of(head, struct cds_ja_shadow_node, head);
	274	free(shadow_node);
	275	}
	276
d22c185b	277	static
25fde237	278	void free_shadow_node_and_node(struct rcu_head *head)
d22c185b	279	{
d96bfb0d MD	280	struct cds_ja_shadow_node *shadow_node =
d96bfb0d MD	281	caa_container_of(head, struct cds_ja_shadow_node, head);
354981c2	282	free_cds_ja_node(shadow_node->ja, ja_node_ptr(shadow_node->node_flag));
d22c185b MD	283	free(shadow_node);
	284	}
	285
a2a7ff59 MD	286	static
	287	void free_shadow_node_and_lock(struct rcu_head *head)
	288	{
	289	struct cds_ja_shadow_node *shadow_node =
	290	caa_container_of(head, struct cds_ja_shadow_node, head);
	291	free(shadow_node->lock);
	292	free(shadow_node);
	293	}
	294
e1db2db5 MD	295	static
	296	void free_shadow_node_and_node_and_lock(struct rcu_head *head)
	297	{
d96bfb0d MD	298	struct cds_ja_shadow_node *shadow_node =
d96bfb0d MD	299	caa_container_of(head, struct cds_ja_shadow_node, head);
3d8fe307	300	assert(shadow_node->level);
354981c2	301	free_cds_ja_node(shadow_node->ja, ja_node_ptr(shadow_node->node_flag));
e1db2db5 MD	302	free(shadow_node->lock);
	303	free(shadow_node);
	304	}
	305
d22c185b	306	__attribute__((visibility("protected")))
e1db2db5	307	int rcuja_shadow_clear(struct cds_lfht *ht,
3d8fe307	308	struct cds_ja_inode_flag *node_flag,
a2a7ff59	309	struct cds_ja_shadow_node *shadow_node,
e1db2db5	310	unsigned int flags)
d22c185b MD	311	{
	312	struct cds_lfht_iter iter;
	313	struct cds_lfht_node *lookup_node;
5eb692c0	314	const struct rcu_flavor_struct *flavor;
d22c185b	315	int ret, lockret;
a2a7ff59	316	int lookup_shadow = 0;
d22c185b	317
5eb692c0 MD	318	flavor = cds_lfht_rcu_flavor(ht);
5eb692c0 MD	319	flavor->read_lock();
a2a7ff59	320
3d8fe307 MD	321	cds_lfht_lookup(ht, hash_pointer(node_flag, hash_seed),
3d8fe307 MD	322	match_pointer, node_flag, &iter);
d22c185b MD	323	lookup_node = cds_lfht_iter_get_node(&iter);
	324	if (!lookup_node) {
	325	ret = -ENOENT;
	326	goto rcu_unlock;
	327	}
a2a7ff59 MD	328
	329	if (!shadow_node) {
	330	shadow_node = caa_container_of(lookup_node,
	331	struct cds_ja_shadow_node, ht_node);
	332	lockret = pthread_mutex_lock(shadow_node->lock);
	333	assert(!lockret);
	334	lookup_shadow = 1;
	335	}
d22c185b MD	336
	337	/*
	338	* Holding the mutex across deletion, and by also re-checking if
	339	* the node is deleted with mutex held at lookup ensure that we
	340	* don't let RCU JA use a node being removed.
	341	*/
	342	ret = cds_lfht_del(ht, lookup_node);
dc0e9798 MD	343	if (ret)
	344	goto unlock;
	345	if ((flags & RCUJA_SHADOW_CLEAR_FREE_NODE)
	346	&& shadow_node->level) {
	347	if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
	348	flavor->update_call_rcu(&shadow_node->head,
	349	free_shadow_node_and_node_and_lock);
e1db2db5	350	} else {
dc0e9798 MD	351	flavor->update_call_rcu(&shadow_node->head,
	352	free_shadow_node_and_node);
	353	}
	354	} else {
	355	if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
	356	flavor->update_call_rcu(&shadow_node->head,
	357	free_shadow_node_and_lock);
	358	} else {
	359	flavor->update_call_rcu(&shadow_node->head,
	360	free_shadow_node);
e1db2db5	361	}
d22c185b	362	}
dc0e9798	363	unlock:
a2a7ff59 MD	364	if (lookup_shadow) {
	365	lockret = pthread_mutex_unlock(shadow_node->lock);
	366	assert(!lockret);
	367	}
d22c185b	368	rcu_unlock:
5eb692c0	369	flavor->read_unlock();
d22c185b MD	370
	371	return ret;
	372	}
	373
be9a7474 MD	374	/*
	375	* Delete all shadow nodes and nodes from hash table, along with their
	376	* associated lock.
	377	*/
	378	__attribute__((visibility("protected")))
	379	void rcuja_shadow_prune(struct cds_lfht *ht,
99e6e3dc	380	unsigned int flags)
be9a7474 MD	381	{
	382	const struct rcu_flavor_struct *flavor;
	383	struct cds_ja_shadow_node *shadow_node;
	384	struct cds_lfht_iter iter;
	385	int ret, lockret;
	386
	387	flavor = cds_lfht_rcu_flavor(ht);
dc0e9798 MD	388	/*
	389	* Read-side lock is needed to ensure hash table node existence
	390	* vs concurrent resize.
	391	*/
be9a7474 MD	392	flavor->read_lock();
	393	cds_lfht_for_each_entry(ht, &iter, shadow_node, ht_node) {
	394	lockret = pthread_mutex_lock(shadow_node->lock);
	395	assert(!lockret);
	396
	397	ret = cds_lfht_del(ht, &shadow_node->ht_node);
dc0e9798 MD	398	if (ret)
	399	goto unlock;
	400	if ((flags & RCUJA_SHADOW_CLEAR_FREE_NODE)
	401	&& shadow_node->level) {
dc0e9798 MD	402	if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
	403	flavor->update_call_rcu(&shadow_node->head,
	404	free_shadow_node_and_node_and_lock);
	405	} else {
	406	flavor->update_call_rcu(&shadow_node->head,
	407	free_shadow_node_and_node);
	408	}
	409	} else {
	410	if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
	411	flavor->update_call_rcu(&shadow_node->head,
	412	free_shadow_node_and_lock);
582a6ade	413	} else {
dc0e9798 MD	414	flavor->update_call_rcu(&shadow_node->head,
dc0e9798 MD	415	free_shadow_node);
582a6ade	416	}
be9a7474	417	}
dc0e9798	418	unlock:
be9a7474 MD	419	lockret = pthread_mutex_unlock(shadow_node->lock);
	420	assert(!lockret);
	421	}
	422	flavor->read_unlock();
	423	}
	424
195e72d3	425	__attribute__((visibility("protected")))
5eb692c0	426	struct cds_lfht rcuja_create_ht(const struct rcu_flavor_struct flavor)
195e72d3	427	{
5eb692c0	428	return _cds_lfht_new(1, 1, 0,
195e72d3	429	CDS_LFHT_AUTO_RESIZE \| CDS_LFHT_ACCOUNTING,
5eb692c0	430	NULL, flavor, NULL);
195e72d3 MD	431	}
	432
	433	__attribute__((visibility("protected")))
be9a7474	434	int rcuja_delete_ht(struct cds_lfht *ht)
195e72d3	435	{
be9a7474	436	return cds_lfht_destroy(ht, NULL);
195e72d3	437	}
d22c185b MD	438
	439	__attribute__((constructor))
	440	void rcuja_ht_init(void)
	441	{
	442	hash_seed = (unsigned long) time(NULL);
	443	}