[urcu.git] / urcu-ht.c


/*
 * TODO: keys are currently assumed <= sizeof(void *). Key target never freed.
 */

#define _LGPL_SOURCE
#include <stdlib.h>
#include <errno.h>
#include <assert.h>
#include <stdio.h>

#include <urcu.h>
#include <urcu-defer.h>
#include <arch.h>
#include <arch_atomic.h>
#include <compiler.h>
#include <urcu/jhash.h>
#include <urcu-ht.h>

struct rcu_ht_node;

struct rcu_ht_node {
	struct rcu_ht_node *next;
	void *key;
	void *data;
	int stolen;
};

struct rcu_ht {
	struct rcu_ht_node **tbl;
	ht_hash_fct hash_fct;
	void (*free_fct)(void *data);	/* fct to free data */
	uint32_t keylen;
	uint32_t hashseed;
	struct ht_size {
		unsigned long add;
		unsigned long lookup;
	} size;
};

struct rcu_ht *ht_new(ht_hash_fct hash_fct, void (*free_fct)(void *data),
		      unsigned long init_size, uint32_t keylen,
		      uint32_t hashseed)
{
	struct rcu_ht *ht;

	ht = calloc(1, sizeof(struct rcu_ht));
	ht->hash_fct = hash_fct;
	ht->free_fct = free_fct;
	ht->size.add = init_size;
	ht->size.lookup = init_size;
	ht->keylen = keylen;
	ht->hashseed = hashseed;
	ht->tbl = calloc(init_size, sizeof(struct rcu_ht_node *));
	return ht;
}

void *ht_lookup(struct rcu_ht *ht, void *key)
{
	unsigned long hash;
	struct rcu_ht_node *node;
	void *ret;

	hash = ht->hash_fct(key, ht->keylen, ht->hashseed) % ht->size.lookup;

	rcu_read_lock();
	node = rcu_dereference(ht->tbl[hash]);
	for (;;) {
		if (likely(!node)) {
			ret = NULL;
			break;
		}
		if (node->key == key) {
			ret = node->data;
			break;
		}
		node = rcu_dereference(node->next);
	}
	rcu_read_unlock();

	return ret;
}

/*
 * Will re-try until either:
 * - The key is already there (-EEXIST)
 * - We successfully add the key at the head of a table bucket.
 */
int ht_add(struct rcu_ht *ht, void *key, void *data)
{
	struct rcu_ht_node *node, *old_head, *new_head;
	unsigned long hash;
	int ret = 0;

	new_head = calloc(1, sizeof(struct rcu_ht_node));
	new_head->key = key;
	new_head->data = data;
	new_head->stolen = 0;
	/* here comes the fun and tricky part.
	 * Add at the beginning with a cmpxchg.
	 * Hold a read lock between the moment the first element is read
	 * and the nodes traversal (to find duplicates). This ensures
	 * the head pointer has not been reclaimed when cmpxchg is done.
	 * Always adding at the head ensures that we would have to
	 * re-try if a new item has been added concurrently. So we ensure that
	 * we never add duplicates. */
retry:
	rcu_read_lock();

	hash = ht->hash_fct(key, ht->keylen, ht->hashseed) % ht->size.add;

	old_head = node = rcu_dereference(ht->tbl[hash]);
	for (;;) {
		if (likely(!node)) {
			break;
		}
		if (node->key == key) {
			ret = -EEXIST;
			goto end;
		}
		node = rcu_dereference(node->next);
	}
	new_head->next = old_head;
	if (rcu_cmpxchg_pointer(&ht->tbl[hash], old_head, new_head) != old_head)
		goto restart;
end:
	rcu_read_unlock();

	return ret;

	/* restart loop, release and re-take the read lock to be kind to GP */
restart:
	rcu_read_unlock();
	goto retry;
}

/*
 * Restart until we successfully remove the entry, or no entry is left
 * ((void *)(unsigned long)-ENOENT).
 * Deal with concurrent stealers by doing an extra verification pass to check
 * that no element in the list are still pointing to the element stolen.
 * This could happen if two concurrent steal for consecutive objects are
 * executed. A pointer to an object being stolen could be saved by the
 * concurrent stealer for the previous object.
 * Also, given that in this precise scenario, another stealer can also want to
 * delete the doubly-referenced object; use a "stolen" flag to let only one
 * stealer delete the object.
 */
void *ht_steal(struct rcu_ht *ht, void *key)
{
	struct rcu_ht_node **prev, *node, *del_node = NULL;
	unsigned long hash;
	void *data;

retry:
	rcu_read_lock();

	hash = ht->hash_fct(key, ht->keylen, ht->hashseed) % ht->size.lookup;

	prev = &ht->tbl[hash];
	node = rcu_dereference(*prev);
	for (;;) {
		if (likely(!node)) {
			if (del_node) {
				goto end;
			} else {
				goto error;
			}
		}
		if (node->key == key) {
			break;
		}
		prev = &node->next;
		node = rcu_dereference(*prev);
	}

	if (!del_node) {
		/*
		 * Another concurrent thread stole it ? If so, let it deal with
		 * this.
		 */
		if (cmpxchg(&node->stolen, 0, 1) != 0)
			goto error;
	}

	/* Found it ! pointer to object is in "prev" */
	if (rcu_cmpxchg_pointer(prev, node, node->next) == node)
		del_node = node;
	goto restart;

end:
	/*
	 * From that point, we own node. Note that there can still be concurrent
	 * RCU readers using it. We can free it outside of read lock after a GP.
	 */
	rcu_read_unlock();

	data = del_node->data;
	call_rcu(free, del_node);
	return data;

error:
	data = (void *)(unsigned long)-ENOENT;
	rcu_read_unlock();
	return data;

	/* restart loop, release and re-take the read lock to be kind to GP */
restart:
	rcu_read_unlock();
	goto retry;
}

int ht_delete(struct rcu_ht *ht, void *key)
{
	void *data;

	data = ht_steal(ht, key);
	if (data && data != (void *)(unsigned long)-ENOENT) {
		if (ht->free_fct)
			call_rcu(ht->free_fct, data);
		return 0;
	} else {
		return -ENOENT;
	}
}

/* Delete all old elements. Allow concurrent writer accesses. */
int ht_delete_all(struct rcu_ht *ht)
{
	unsigned long i;
	struct rcu_ht_node **prev, *node, *inext;
	int cnt = 0;

	for (i = 0; i < ht->size.lookup; i++) {
		rcu_read_lock();
		prev = &ht->tbl[i];
		/*
		 * Cut the head. After that, we own the first element.
		 */
		node = rcu_xchg_pointer(prev, NULL);
		if (!node) {
			rcu_read_unlock();
			continue;
		}
		/*
		 * We manage a list shared with concurrent writers and readers.
		 * Note that a concurrent add may or may not be deleted by us,
		 * depending if it arrives before or after the head is cut.
		 * "node" points to our first node. Remove first elements
		 * iteratively.
		 */
		for (;;) {
			inext = NULL;
			prev = &node->next;
			if (prev)
				inext = rcu_xchg_pointer(prev, NULL);
			/*
			 * "node" is the first element of the list we have cut.
			 * We therefore own it, no concurrent writer may delete
			 * it. There can only be concurrent lookups. Concurrent
			 * add can only be done on a bucket head, but we've cut
			 * it already. inext is also owned by us, because we
			 * have exchanged it for "NULL". It will therefore be
			 * safe to use it after a G.P.
			 */
			rcu_read_unlock();
			if (node->data)
				call_rcu(ht->free_fct, node->data);
			call_rcu(free, node);
			cnt++;
			if (likely(!inext))
				break;
			rcu_read_lock();
			node = inext;
		}
	}
	return cnt;
}

/*
 * Should only be called when no more concurrent readers nor writers can
 * possibly access the table.
 */
int ht_destroy(struct rcu_ht *ht)
{
	int ret;

	ret = ht_delete_all(ht);
	free(ht->tbl);
	free(ht);
	return ret;
}

/*
 * Expects keys <= than pointer size to be encoded in the pointer itself.
 */
uint32_t ht_jhash(void *key, uint32_t length, uint32_t initval)
{
	uint32_t ret;
	void *vkey;

	if (length <= sizeof(void *))
		vkey = &key;
	else
		vkey = key;
	ret = jhash(vkey, length, initval);
	return ret;
}
Commit	Line	Data
2ed95849	1
5e28c532 MD	2	/*
	3	* TODO: keys are currently assumed <= sizeof(void *). Key target never freed.
	4	*/
	5
2ed95849 MD	6	#define _LGPL_SOURCE
2ed95849 MD	7	#include <stdlib.h>
e0ba718a MD	8	#include <errno.h>
	9	#include <assert.h>
	10	#include <stdio.h>
	11
2ed95849	12	#include <urcu.h>
e0ba718a	13	#include <urcu-defer.h>
2ed95849 MD	14	#include <arch.h>
2ed95849 MD	15	#include <arch_atomic.h>
2ed95849	16	#include <compiler.h>
674f7a69	17	#include <urcu/jhash.h>
e0ba718a	18	#include <urcu-ht.h>
2ed95849 MD	19
	20	struct rcu_ht_node;
	21
	22	struct rcu_ht_node {
	23	struct rcu_ht_node *next;
	24	void *key;
	25	void *data;
e0ba718a	26	int stolen;
2ed95849 MD	27	};
	28
	29	struct rcu_ht {
674f7a69	30	struct rcu_ht_node **tbl;
2ed95849 MD	31	ht_hash_fct hash_fct;
2ed95849 MD	32	void (free_fct)(void data); /* fct to free data */
5e28c532 MD	33	uint32_t keylen;
5e28c532 MD	34	uint32_t hashseed;
674f7a69 MD	35	struct ht_size {
	36	unsigned long add;
	37	unsigned long lookup;
	38	} size;
2ed95849 MD	39	};
2ed95849 MD	40
674f7a69	41	struct rcu_ht ht_new(ht_hash_fct hash_fct, void (free_fct)(void *data),
5e28c532 MD	42	unsigned long init_size, uint32_t keylen,
5e28c532 MD	43	uint32_t hashseed)
2ed95849 MD	44	{
	45	struct rcu_ht *ht;
	46
	47	ht = calloc(1, sizeof(struct rcu_ht));
	48	ht->hash_fct = hash_fct;
	49	ht->free_fct = free_fct;
674f7a69 MD	50	ht->size.add = init_size;
674f7a69 MD	51	ht->size.lookup = init_size;
5e28c532 MD	52	ht->keylen = keylen;
5e28c532 MD	53	ht->hashseed = hashseed;
674f7a69	54	ht->tbl = calloc(init_size, sizeof(struct rcu_ht_node *));
ab7d5fc6	55	return ht;
2ed95849 MD	56	}
2ed95849 MD	57
2ed95849 MD	58	void ht_lookup(struct rcu_ht ht, void *key)
	59	{
	60	unsigned long hash;
	61	struct rcu_ht_node *node;
	62	void *ret;
	63
5e28c532	64	hash = ht->hash_fct(key, ht->keylen, ht->hashseed) % ht->size.lookup;
2ed95849 MD	65
2ed95849 MD	66	rcu_read_lock();
5e28c532	67	node = rcu_dereference(ht->tbl[hash]);
2ed95849 MD	68	for (;;) {
	69	if (likely(!node)) {
	70	ret = NULL;
	71	break;
	72	}
	73	if (node->key == key) {
	74	ret = node->data;
	75	break;
	76	}
	77	node = rcu_dereference(node->next);
	78	}
	79	rcu_read_unlock();
ab7d5fc6 MD	80
ab7d5fc6 MD	81	return ret;
2ed95849 MD	82	}
	83
	84	/*
	85	* Will re-try until either:
	86	* - The key is already there (-EEXIST)
	87	* - We successfully add the key at the head of a table bucket.
	88	*/
	89	int ht_add(struct rcu_ht ht, void key, void *data)
	90	{
	91	struct rcu_ht_node node, old_head, *new_head;
	92	unsigned long hash;
	93	int ret = 0;
	94
	95	new_head = calloc(1, sizeof(struct rcu_ht_node));
	96	new_head->key = key;
	97	new_head->data = data;
e0ba718a	98	new_head->stolen = 0;
2ed95849 MD	99	/* here comes the fun and tricky part.
	100	* Add at the beginning with a cmpxchg.
	101	* Hold a read lock between the moment the first element is read
	102	* and the nodes traversal (to find duplicates). This ensures
	103	* the head pointer has not been reclaimed when cmpxchg is done.
	104	* Always adding at the head ensures that we would have to
	105	* re-try if a new item has been added concurrently. So we ensure that
	106	* we never add duplicates. */
	107	retry:
	108	rcu_read_lock();
	109
5e28c532 MD	110	hash = ht->hash_fct(key, ht->keylen, ht->hashseed) % ht->size.add;
	111
	112	old_head = node = rcu_dereference(ht->tbl[hash]);
2ed95849 MD	113	for (;;) {
	114	if (likely(!node)) {
	115	break;
	116	}
	117	if (node->key == key) {
	118	ret = -EEXIST;
	119	goto end;
	120	}
	121	node = rcu_dereference(node->next);
	122	}
5e28c532 MD	123	new_head->next = old_head;
5e28c532 MD	124	if (rcu_cmpxchg_pointer(&ht->tbl[hash], old_head, new_head) != old_head)
2ed95849 MD	125	goto restart;
	126	end:
	127	rcu_read_unlock();
	128
	129	return ret;
	130
	131	/* restart loop, release and re-take the read lock to be kind to GP */
	132	restart:
	133	rcu_read_unlock();
	134	goto retry;
	135	}
	136
	137	/*
	138	* Restart until we successfully remove the entry, or no entry is left
	139	* ((void *)(unsigned long)-ENOENT).
e0ba718a MD	140	* Deal with concurrent stealers by doing an extra verification pass to check
	141	* that no element in the list are still pointing to the element stolen.
	142	* This could happen if two concurrent steal for consecutive objects are
	143	* executed. A pointer to an object being stolen could be saved by the
	144	* concurrent stealer for the previous object.
	145	* Also, given that in this precise scenario, another stealer can also want to
	146	* delete the doubly-referenced object; use a "stolen" flag to let only one
	147	* stealer delete the object.
2ed95849	148	*/
ab7d5fc6	149	void ht_steal(struct rcu_ht ht, void *key)
2ed95849	150	{
2e6070d0	151	struct rcu_ht_node *prev, node, *del_node = NULL;
2ed95849	152	unsigned long hash;
ab7d5fc6	153	void *data;
2ed95849	154
2ed95849 MD	155	retry:
	156	rcu_read_lock();
	157
5e28c532 MD	158	hash = ht->hash_fct(key, ht->keylen, ht->hashseed) % ht->size.lookup;
	159
	160	prev = &ht->tbl[hash];
2ed95849 MD	161	node = rcu_dereference(*prev);
	162	for (;;) {
	163	if (likely(!node)) {
2e6070d0 MD	164	if (del_node) {
	165	goto end;
	166	} else {
2e6070d0 MD	167	goto error;
2e6070d0 MD	168	}
2ed95849 MD	169	}
	170	if (node->key == key) {
	171	break;
	172	}
	173	prev = &node->next;
	174	node = rcu_dereference(*prev);
	175	}
e0ba718a	176
85f6ba5f MD	177	if (!del_node) {
	178	/*
	179	* Another concurrent thread stole it ? If so, let it deal with
	180	* this.
	181	*/
	182	if (cmpxchg(&node->stolen, 0, 1) != 0)
	183	goto error;
	184	}
e0ba718a	185
2ed95849	186	/* Found it ! pointer to object is in "prev" */
7ce4eb38	187	if (rcu_cmpxchg_pointer(prev, node, node->next) == node)
2e6070d0 MD	188	del_node = node;
2e6070d0 MD	189	goto restart;
5e28c532	190
2e6070d0 MD	191	end:
	192	/*
	193	* From that point, we own node. Note that there can still be concurrent
	194	* RCU readers using it. We can free it outside of read lock after a GP.
	195	*/
2ed95849 MD	196	rcu_read_unlock();
2ed95849 MD	197
567d7550 MD	198	data = del_node->data;
567d7550 MD	199	call_rcu(free, del_node);
5e28c532	200	return data;
ab7d5fc6	201
5e28c532	202	error:
e0ba718a	203	data = (void *)(unsigned long)-ENOENT;
5e28c532	204	rcu_read_unlock();
ab7d5fc6	205	return data;
2ed95849 MD	206
	207	/* restart loop, release and re-take the read lock to be kind to GP */
	208	restart:
	209	rcu_read_unlock();
	210	goto retry;
	211	}
	212
	213	int ht_delete(struct rcu_ht ht, void key)
	214	{
ab7d5fc6	215	void *data;
2ed95849	216
ab7d5fc6	217	data = ht_steal(ht, key);
5e28c532 MD	218	if (data && data != (void *)(unsigned long)-ENOENT) {
5e28c532 MD	219	if (ht->free_fct)
ab7d5fc6	220	call_rcu(ht->free_fct, data);
2ed95849 MD	221	return 0;
	222	} else {
	223	return -ENOENT;
	224	}
	225	}
ab7d5fc6	226
674f7a69	227	/* Delete all old elements. Allow concurrent writer accesses. */
5e28c532	228	int ht_delete_all(struct rcu_ht *ht)
674f7a69 MD	229	{
	230	unsigned long i;
	231	struct rcu_ht_node *prev, node, *inext;
5e28c532	232	int cnt = 0;
674f7a69 MD	233
	234	for (i = 0; i < ht->size.lookup; i++) {
	235	rcu_read_lock();
5e28c532 MD	236	prev = &ht->tbl[i];
	237	/*
	238	* Cut the head. After that, we own the first element.
	239	*/
	240	node = rcu_xchg_pointer(prev, NULL);
	241	if (!node) {
674f7a69 MD	242	rcu_read_unlock();
	243	continue;
	244	}
	245	/*
	246	* We manage a list shared with concurrent writers and readers.
	247	* Note that a concurrent add may or may not be deleted by us,
	248	* depending if it arrives before or after the head is cut.
	249	* "node" points to our first node. Remove first elements
	250	* iteratively.
	251	*/
	252	for (;;) {
5e28c532	253	inext = NULL;
674f7a69	254	prev = &node->next;
5e28c532 MD	255	if (prev)
5e28c532 MD	256	inext = rcu_xchg_pointer(prev, NULL);
674f7a69 MD	257	/*
	258	* "node" is the first element of the list we have cut.
	259	* We therefore own it, no concurrent writer may delete
	260	* it. There can only be concurrent lookups. Concurrent
	261	* add can only be done on a bucket head, but we've cut
	262	* it already. inext is also owned by us, because we
	263	* have exchanged it for "NULL". It will therefore be
	264	* safe to use it after a G.P.
	265	*/
	266	rcu_read_unlock();
	267	if (node->data)
	268	call_rcu(ht->free_fct, node->data);
	269	call_rcu(free, node);
5e28c532	270	cnt++;
674f7a69 MD	271	if (likely(!inext))
	272	break;
	273	rcu_read_lock();
	274	node = inext;
	275	}
	276	}
5e28c532	277	return cnt;
674f7a69 MD	278	}
	279
	280	/*
	281	* Should only be called when no more concurrent readers nor writers can
	282	* possibly access the table.
	283	*/
5e28c532	284	int ht_destroy(struct rcu_ht *ht)
674f7a69	285	{
5e28c532 MD	286	int ret;
	287
	288	ret = ht_delete_all(ht);
674f7a69 MD	289	free(ht->tbl);
674f7a69 MD	290	free(ht);
5e28c532	291	return ret;
674f7a69 MD	292	}
674f7a69 MD	293
5e28c532 MD	294	/*
	295	* Expects keys <= than pointer size to be encoded in the pointer itself.
	296	*/
674f7a69	297	uint32_t ht_jhash(void *key, uint32_t length, uint32_t initval)
ab7d5fc6	298	{
5e28c532 MD	299	uint32_t ret;
	300	void *vkey;
	301
0eb566f4	302	if (length <= sizeof(void *))
5e28c532 MD	303	vkey = &key;
	304	else
	305	vkey = key;
	306	ret = jhash(vkey, length, initval);
	307	return ret;
ab7d5fc6	308	}