[userspace-rcu.git] / rcuja / rcuja-range.c

/*
 * rcuja/rcuja-range.c
 *
 * Userspace RCU library - RCU Judy Array Range Support
 *
 * 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 <string.h>
#include <assert.h>
#include <pthread.h>
#include <urcu/rcuja.h>
#include <urcu/compiler.h>
#include <urcu/arch.h>
#include <urcu-pointer.h>
#include <urcu/uatomic.h>
#include <urcu/rcuja-range.h>
#include <urcu-flavor.h>

#include "rcuja-internal.h"

/*
 * Discussion about order of lookup/lock vs allocated node deletion.
 *
 * - If node deletion returns before call to
 *   cds_ja_range_lookup(), the node will not be found by lookup.
 * - If node deletion is called after cds_ja_range_lock() returns a
 *   non-NULL range, the deletion will wait until the lock is released
 *   before it takes place.
 * - If node deletion call/return overlaps with the call to
 *   cds_ja_range_lookup() and return from cds_ja_range_lock(), the node
 *   may or may not be found by each of cds_ja_range_lookup() and
 *   cds_ja_range_lock().
 */

/*
 * Discussion about order of lookup/lock vs allocated node add. Assuming
 * no concurrent delete.
 *
 * - If node add returns before call to
 *   cds_ja_range_lookup(), the node will be found by lookup.
 * - If node add is called after cds_ja_range_lookup returns, the node
 *   will not be found by lookup.
 * - If node add call/return overlaps with the call to and return from
 *   cds_ja_range_lookup(), the node may or may not be found.
 * - If node add call/return overlaps with call to cds_ja_range_lookup()
 *   and return from cds_ja_range_lock(), in the specific case where
 *   cds_ja_range_lookup() _does_ succeed, then cds_ja_range_lock() will
 *   succeed (still assuming no concurrent deletion).
 */

/*
 * Discussion: concurrent deletion of contiguous allocated ranges.
 *
 * Ensuring that merge of contiguous free ranges is always performed, we
 * need to ensure locking of concurrent removal of contiguous allocated
 * ranges one with respect to another. This is done by locking the
 * ranges prior to and after the range to remove, even if that range is
 * allocated. This serializes removal of contiguous ranges. The only
 * cases for which there is no range to lock is when removing an
 * allocated range starting at 0, and/or ending at the end of the key
 * space.
 */

/*
 * Discussion of the type state transitions.
 *
 * State transitions of "type" always go from either:
 *
 * CDS_JA_RANGE_FREE -> CDS_JA_RANGE_REMOVED
 * or
 * CDS_JA_RANGE_ALLOCATED -> CDS_JA_RANGE_REMOVED
 *
 * A range type never changes otherwise.
 */

#define CDS_JA_RANGE_KEY_BITS	64

struct cds_ja_range *cds_ja_range_lookup(struct cds_ja *ja, uint64_t key)
{
	struct cds_ja_node *node, *last_node;
	struct cds_ja_range *range;

	node = cds_ja_lookup_below_equal(ja, key, NULL);
	assert(node);
	/*
	 * Get the last of duplicate chain. Adding a node to Judy array
	 * duplicates inserts them at the end of the chain.
	 */
	cds_ja_for_each_duplicate_rcu(node)
		last_node = node;
	range = caa_container_of(last_node, struct cds_ja_range, ja_node);
	/*
	 * If last node in the duplicates is removed or free, we can
	 * consider that either a removal or add operation is in
	 * progress, or removal is the last completed operation to
	 * update this range. We can therefore consider that this area
	 * is not allocated.
	 */
	if (range->type != CDS_JA_RANGE_ALLOCATED)
		return NULL;
	/*
	 * We found an allocated range. We can return it for use with
	 * RCU read-side protection for existence. However, we have no
	 * mutual exclusion against removal at this point.
	 */
	return range;
}

/*
 * Provide mutual exclusion against removal.
 */
struct cds_ja_range *cds_ja_range_lock(struct cds_ja_range *range)
{
	pthread_mutex_lock(&range->lock);

	if (range->type == CDS_JA_RANGE_REMOVED)
		goto removed;
	return range;

removed:
	pthread_mutex_unlock(&range->lock);
	return NULL;
}

void cds_ja_range_unlock(struct cds_ja_range *range)
{
	pthread_mutex_unlock(&range->lock);
}

static
struct cds_ja_range *range_create(
		uint64_t start,		/* inclusive */
		uint64_t end,		/* inclusive */
		enum cds_ja_range_type type)
{
	struct cds_ja_range *range;

	range = calloc(sizeof(*range), 1);
	if (!range)
		return NULL;
	range->start = start;
	range->end = end;
	range->type = type;
	pthread_mutex_init(&range->lock, NULL);
	return range;
}

static
void free_range_cb(struct rcu_head *head)
{
	struct cds_ja_range *range =
		caa_container_of(head, struct cds_ja_range, head);
	free(range);
}

static
void free_range(struct cds_ja_range *range)
{
	free(range);
}

static
void rcu_free_range(struct cds_ja *ja, struct cds_ja_range *range)
{
	cds_lfht_rcu_flavor(ja->ht)->update_call_rcu(&range->head,
			free_range_cb);
}

struct cds_ja_range *cds_ja_range_add(struct cds_ja *ja,
		uint64_t start,		/* inclusive */
		uint64_t end)		/* inclusive */
{
	struct cds_ja_node *old_node, *old_node_end;
	struct cds_ja_range *old_range, *old_range_end, *new_range, *ranges[3];
	unsigned int nr_ranges, i;
	int ret;

retry:
	/*
	 * Find if requested range is entirely contained within a single
	 * free range.
	 */
	old_node = cds_ja_lookup_below_equal(ja, start, NULL);
	assert(old_node);

	old_range = caa_container_of(old_node, struct cds_ja_range, ja_node);
	switch (CMM_LOAD_SHARED(old_range->type)) {
	case CDS_JA_RANGE_ALLOCATED:
		return NULL;
	case CDS_JA_RANGE_FREE:
		break;
	case CDS_JA_RANGE_REMOVED:
		goto retry;
	}

	old_node_end = cds_ja_lookup_below_equal(ja, end, NULL);
	assert(old_node_end);
	old_range_end = caa_container_of(old_node_end,
			struct cds_ja_range, ja_node);
	if (old_range_end != old_range) {
		switch (CMM_LOAD_SHARED(old_range->type)) {
		case CDS_JA_RANGE_ALLOCATED:
		case CDS_JA_RANGE_FREE:		/* fall-through */
			return NULL;
		case CDS_JA_RANGE_REMOVED:
			goto retry;
		}
	}

	pthread_mutex_lock(&old_range->lock);

	if (old_range->type == CDS_JA_RANGE_REMOVED) {
		pthread_mutex_unlock(&old_range->lock);
		goto retry;
	}

	/* Create replacement ranges: at most 2 free and 1 allocated */
	if (start == old_range->start) {
		if (end == old_range->end) {
			/* 1 range */
			ranges[0] = new_range = range_create(start, end,
				CDS_JA_RANGE_ALLOCATED);
			nr_ranges = 1;
		} else {
			/* 2 ranges */
			ranges[0] = new_range = range_create(start, end,
				CDS_JA_RANGE_ALLOCATED);
			ranges[1] = range_create(end + 1, old_range->end,
				CDS_JA_RANGE_FREE);
			nr_ranges = 2;
		}
	} else {
		if (end == old_range->end) {
			/* 2 ranges */
			ranges[0] = range_create(old_range->start, start - 1,
				CDS_JA_RANGE_FREE);
			ranges[1] = new_range = range_create(start, end,
				CDS_JA_RANGE_ALLOCATED);
			nr_ranges = 2;
		} else {
			/* 3 ranges */
			ranges[0] = range_create(old_range->start, start - 1,
				CDS_JA_RANGE_FREE);
			ranges[1] = new_range = range_create(start, end,
				CDS_JA_RANGE_ALLOCATED);
			ranges[2] = range_create(end + 1, old_range->end,
				CDS_JA_RANGE_FREE);
			nr_ranges = 3;
		}
	}

	/* Add replacement ranges to Judy array */
	for (i = 0; i < nr_ranges; i++) {
		ret = cds_ja_add(ja, ranges[i]->start, &ranges[i]->ja_node);
		assert(!ret);
	}

	/*
	 * We add replacement ranges _before_ removing old ranges, so
	 * concurrent traversals will always see one or the other. This
	 * is OK because we temporarily have a duplicate key, and Judy
	 * arrays provide key existence guarantee for lookups performed
	 * concurrently with add followed by del of duplicate keys.
	 */

	/* Remove old free range */
	ret = cds_ja_del(ja, old_range->start, &old_range->ja_node);
	assert(!ret);
	old_range->type = CDS_JA_RANGE_REMOVED;
	pthread_mutex_unlock(&old_range->lock);

	rcu_free_range(ja, old_range);

	return new_range;
}

int cds_ja_range_del(struct cds_ja *ja, struct cds_ja_range *range)
{
	struct cds_ja_node *prev_node, *next_node;
	struct cds_ja_range *new_range;
	struct cds_ja_range *merge_ranges[3], *lock_ranges[3];
	unsigned int nr_merge, nr_lock, i;
	uint64_t start, end;
	int ret;

retry:
	nr_merge = 0;
	nr_lock = 0;
	prev_node = cds_ja_lookup_below_equal(ja, range->start - 1, NULL);
	if (prev_node) {
		struct cds_ja_range *prev_range;

		prev_range = caa_container_of(prev_node,
			struct cds_ja_range, ja_node);
		lock_ranges[nr_lock++] = prev_range;
		if (prev_range->type != CDS_JA_RANGE_ALLOCATED)
			merge_ranges[nr_merge++] = prev_range;
	}

	lock_ranges[nr_lock++] = range;
	merge_ranges[nr_merge++] = range;

	next_node = cds_ja_lookup_above_equal(ja, range->end + 1, NULL);
	if (next_node) {
		struct cds_ja_range *next_range;

		next_range = caa_container_of(next_node,
			struct cds_ja_range, ja_node);
		lock_ranges[nr_lock++] = next_range;
		if (next_range->type != CDS_JA_RANGE_ALLOCATED)
			merge_ranges[nr_merge++] = next_range;
	}

	/* Acquire locks in increasing key order for range merge */
	for (i = 0; i < nr_lock; i++)
		pthread_mutex_lock(&lock_ranges[i]->lock);
	/* Ensure they are valid */
	for (i = 0; i < nr_lock; i++) {
		if (lock_ranges[i]->type == CDS_JA_RANGE_REMOVED)
			goto unlock_retry;
	}

	/* Create new free range */
	start = merge_ranges[0]->start;
	end = merge_ranges[nr_merge - 1]->end;
	new_range = range_create(start, end, CDS_JA_RANGE_FREE);
	ret = cds_ja_add(ja, start, &new_range->ja_node);
	assert(!ret);

	/* Remove old ranges */
	for (i = 0; i < nr_merge; i++) {
		ret = cds_ja_del(ja, merge_ranges[i]->start,
				&merge_ranges[i]->ja_node);
		assert(!ret);
		merge_ranges[i]->type = CDS_JA_RANGE_REMOVED;
	}
	for (i = 0; i < nr_lock; i++)
		pthread_mutex_unlock(&lock_ranges[i]->lock);
	/* Free old merged ranges */
	for (i = 0; i < nr_merge; i++)
		rcu_free_range(ja, merge_ranges[i]);

	return 0;

	/* retry paths */
unlock_retry:
	for (i = 0; i < nr_lock; i++)
		pthread_mutex_unlock(&lock_ranges[i]->lock);
	goto retry;
}

struct cds_ja *_cds_ja_range_new(const struct rcu_flavor_struct *flavor)
{
	struct cds_ja_range *range;
	struct cds_ja *ja;
	int ret;

	ja = _cds_ja_new(CDS_JA_RANGE_KEY_BITS, flavor);
	if (!ja)
		return NULL;
	range = range_create(0, UINT64_MAX, CDS_JA_RANGE_FREE);
	if (!range)
		goto free_ja;
	ret = cds_ja_add(ja, 0, &range->ja_node);
	if (ret)
		goto free_range;
	return ja;

free_range:
	free_range(range);
free_ja:
	ret = cds_ja_destroy(ja);
	assert(!ret);
	return NULL;
}

int cds_ja_range_destroy(struct cds_ja *ja)
{
	uint64_t key;
	struct cds_ja_node *ja_node;
	int ret = 0;

	cds_ja_for_each_key_rcu(ja, key, ja_node) {
		struct cds_ja_node *tmp_node;

		cds_ja_for_each_duplicate_safe_rcu(ja_node, tmp_node) {
			struct cds_ja_range *range;

			range = caa_container_of(ja_node,
					struct cds_ja_range, ja_node);
			ret = cds_ja_del(ja, key, &range->ja_node);
			if (ret)
				goto error;
			/* Alone using Judy array, OK to free now */
			free_range(range);
		}
	}
	return cds_ja_destroy(ja);

error:
	return ret;
}
Commit	Line	Data
b45a45b9 MD	1	/*
	2	* rcuja/rcuja-range.c
	3	*
	4	* Userspace RCU library - RCU Judy Array Range Support
	5	*
	6	* Copyright 2012-2013 - 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	#include <string.h>
	28	#include <assert.h>
	29	#include <pthread.h>
	30	#include <urcu/rcuja.h>
	31	#include <urcu/compiler.h>
	32	#include <urcu/arch.h>
	33	#include <urcu-pointer.h>
	34	#include <urcu/uatomic.h>
	35	#include <urcu/rcuja-range.h>
	36	#include <urcu-flavor.h>
	37
	38	#include "rcuja-internal.h"
	39
	40	/*
	41	* Discussion about order of lookup/lock vs allocated node deletion.
	42	*
	43	* - If node deletion returns before call to
	44	* cds_ja_range_lookup(), the node will not be found by lookup.
	45	* - If node deletion is called after cds_ja_range_lock() returns a
	46	* non-NULL range, the deletion will wait until the lock is released
	47	* before it takes place.
	48	* - If node deletion call/return overlaps with the call to
	49	* cds_ja_range_lookup() and return from cds_ja_range_lock(), the node
	50	* may or may not be found by each of cds_ja_range_lookup() and
	51	* cds_ja_range_lock().
	52	*/
	53
	54	/*
	55	* Discussion about order of lookup/lock vs allocated node add. Assuming
	56	* no concurrent delete.
	57	*
	58	* - If node add returns before call to
	59	* cds_ja_range_lookup(), the node will be found by lookup.
	60	* - If node add is called after cds_ja_range_lookup returns, the node
	61	* will not be found by lookup.
	62	* - If node add call/return overlaps with the call to and return from
	63	* cds_ja_range_lookup(), the node may or may not be found.
	64	* - If node add call/return overlaps with call to cds_ja_range_lookup()
65	* and return from cds_ja_range_lock(), in the specific case where
66	* cds_ja_range_lookup() _does_ succeed, then cds_ja_range_lock() will
67	* succeed (still assuming no concurrent deletion).
68	*/
69
c34bfad2 MD	70	/*
	71	* Discussion: concurrent deletion of contiguous allocated ranges.
	72	*
	73	* Ensuring that merge of contiguous free ranges is always performed, we
	74	* need to ensure locking of concurrent removal of contiguous allocated
	75	* ranges one with respect to another. This is done by locking the
	76	* ranges prior to and after the range to remove, even if that range is
	77	* allocated. This serializes removal of contiguous ranges. The only
	78	* cases for which there is no range to lock is when removing an
	79	* allocated range starting at 0, and/or ending at the end of the key
	80	* space.
	81	*/
	82
b45a45b9 MD	83	/*
	84	* Discussion of the type state transitions.
	85	*
	86	* State transitions of "type" always go from either:
	87	*
	88	* CDS_JA_RANGE_FREE -> CDS_JA_RANGE_REMOVED
	89	* or
	90	* CDS_JA_RANGE_ALLOCATED -> CDS_JA_RANGE_REMOVED
	91	*
	92	* A range type never changes otherwise.
	93	*/
	94
678624e7	95	#define CDS_JA_RANGE_KEY_BITS 64
b45a45b9 MD	96
	97	struct cds_ja_range cds_ja_range_lookup(struct cds_ja ja, uint64_t key)
	98	{
	99	struct cds_ja_node node, last_node;
	100	struct cds_ja_range *range;
	101
	102	node = cds_ja_lookup_below_equal(ja, key, NULL);
	103	assert(node);
	104	/*
	105	* Get the last of duplicate chain. Adding a node to Judy array
	106	* duplicates inserts them at the end of the chain.
	107	*/
	108	cds_ja_for_each_duplicate_rcu(node)
	109	last_node = node;
	110	range = caa_container_of(last_node, struct cds_ja_range, ja_node);
	111	/*
	112	* If last node in the duplicates is removed or free, we can
	113	* consider that either a removal or add operation is in
	114	* progress, or removal is the last completed operation to
	115	* update this range. We can therefore consider that this area
	116	* is not allocated.
	117	*/
	118	if (range->type != CDS_JA_RANGE_ALLOCATED)
	119	return NULL;
	120	/*
	121	* We found an allocated range. We can return it for use with
7c74dcc7	122	* RCU read-side protection for existence. However, we have no
b45a45b9 MD	123	* mutual exclusion against removal at this point.
	124	*/
	125	return range;
	126	}
	127
	128	/*
	129	* Provide mutual exclusion against removal.
	130	*/
	131	struct cds_ja_range cds_ja_range_lock(struct cds_ja_range range)
	132	{
	133	pthread_mutex_lock(&range->lock);
	134
	135	if (range->type == CDS_JA_RANGE_REMOVED)
	136	goto removed;
	137	return range;
	138
	139	removed:
	140	pthread_mutex_unlock(&range->lock);
	141	return NULL;
	142	}
	143
	144	void cds_ja_range_unlock(struct cds_ja_range *range)
	145	{
	146	pthread_mutex_unlock(&range->lock);
	147	}
	148
	149	static
	150	struct cds_ja_range *range_create(
	151	uint64_t start, /* inclusive */
	152	uint64_t end, /* inclusive */
	153	enum cds_ja_range_type type)
	154	{
	155	struct cds_ja_range *range;
	156
	157	range = calloc(sizeof(*range), 1);
	158	if (!range)
	159	return NULL;
	160	range->start = start;
	161	range->end = end;
	162	range->type = type;
	163	pthread_mutex_init(&range->lock, NULL);
	164	return range;
	165	}
	166
	167	static
	168	void free_range_cb(struct rcu_head *head)
	169	{
	170	struct cds_ja_range *range =
	171	caa_container_of(head, struct cds_ja_range, head);
	172	free(range);
	173	}
	174
	175	static
	176	void free_range(struct cds_ja_range *range)
	177	{
	178	free(range);
	179	}
	180
	181	static
	182	void rcu_free_range(struct cds_ja ja, struct cds_ja_range range)
	183	{
	184	cds_lfht_rcu_flavor(ja->ht)->update_call_rcu(&range->head,
	185	free_range_cb);
	186	}
187
188	struct cds_ja_range cds_ja_range_add(struct cds_ja ja,
189	uint64_t start, /* inclusive */
190	uint64_t end) /* inclusive */
191	{
192	struct cds_ja_node old_node, old_node_end;
193	struct cds_ja_range old_range, old_range_end, new_range, ranges[3];
194	unsigned int nr_ranges, i;
195	int ret;
196
197	retry:
198	/*
199	* Find if requested range is entirely contained within a single
200	* free range.
201	*/
202	old_node = cds_ja_lookup_below_equal(ja, start, NULL);
203	assert(old_node);
204
205	old_range = caa_container_of(old_node, struct cds_ja_range, ja_node);
206	switch (CMM_LOAD_SHARED(old_range->type)) {
207	case CDS_JA_RANGE_ALLOCATED:
208	return NULL;
209	case CDS_JA_RANGE_FREE:
210	break;
211	case CDS_JA_RANGE_REMOVED:
212	goto retry;
213	}
214
215	old_node_end = cds_ja_lookup_below_equal(ja, end, NULL);
216	assert(old_node_end);
217	old_range_end = caa_container_of(old_node_end,
218	struct cds_ja_range, ja_node);
219	if (old_range_end != old_range) {
220	switch (CMM_LOAD_SHARED(old_range->type)) {
221	case CDS_JA_RANGE_ALLOCATED:
222	case CDS_JA_RANGE_FREE: /* fall-through */
b45a45b9 MD	223	return NULL;
	224	case CDS_JA_RANGE_REMOVED:
	225	goto retry;
	226	}
	227	}
	228
	229	pthread_mutex_lock(&old_range->lock);
	230
	231	if (old_range->type == CDS_JA_RANGE_REMOVED) {
	232	pthread_mutex_unlock(&old_range->lock);
	233	goto retry;
	234	}
	235
	236	/* Create replacement ranges: at most 2 free and 1 allocated */
	237	if (start == old_range->start) {
	238	if (end == old_range->end) {
	239	/* 1 range */
	240	ranges[0] = new_range = range_create(start, end,
	241	CDS_JA_RANGE_ALLOCATED);
	242	nr_ranges = 1;
	243	} else {
	244	/* 2 ranges */
	245	ranges[0] = new_range = range_create(start, end,
	246	CDS_JA_RANGE_ALLOCATED);
	247	ranges[1] = range_create(end + 1, old_range->end,
	248	CDS_JA_RANGE_FREE);
	249	nr_ranges = 2;
	250	}
	251	} else {
	252	if (end == old_range->end) {
	253	/* 2 ranges */
	254	ranges[0] = range_create(old_range->start, start - 1,
	255	CDS_JA_RANGE_FREE);
	256	ranges[1] = new_range = range_create(start, end,
	257	CDS_JA_RANGE_ALLOCATED);
	258	nr_ranges = 2;
	259	} else {
	260	/* 3 ranges */
	261	ranges[0] = range_create(old_range->start, start - 1,
	262	CDS_JA_RANGE_FREE);
	263	ranges[1] = new_range = range_create(start, end,
	264	CDS_JA_RANGE_ALLOCATED);
	265	ranges[2] = range_create(end + 1, old_range->end,
	266	CDS_JA_RANGE_FREE);
	267	nr_ranges = 3;
	268	}
	269	}
	270
	271	/* Add replacement ranges to Judy array */
	272	for (i = 0; i < nr_ranges; i++) {
	273	ret = cds_ja_add(ja, ranges[i]->start, &ranges[i]->ja_node);
	274	assert(!ret);
	275	}
	276
	277	/*
	278	* We add replacement ranges _before_ removing old ranges, so
	279	* concurrent traversals will always see one or the other. This
	280	* is OK because we temporarily have a duplicate key, and Judy
	281	* arrays provide key existence guarantee for lookups performed
	282	* concurrently with add followed by del of duplicate keys.
	283	*/
	284
	285	/* Remove old free range */
	286	ret = cds_ja_del(ja, old_range->start, &old_range->ja_node);
287	assert(!ret);
288	old_range->type = CDS_JA_RANGE_REMOVED;
289	pthread_mutex_unlock(&old_range->lock);
290
291	rcu_free_range(ja, old_range);
292
293	return new_range;
294	}
295
296	int cds_ja_range_del(struct cds_ja ja, struct cds_ja_range range)
297	{
298	struct cds_ja_node prev_node, next_node;
c34bfad2 MD	299	struct cds_ja_range *new_range;
	300	struct cds_ja_range merge_ranges[3], lock_ranges[3];
	301	unsigned int nr_merge, nr_lock, i;
b45a45b9 MD	302	uint64_t start, end;
	303	int ret;
	304
	305	retry:
	306	nr_merge = 0;
c34bfad2	307	nr_lock = 0;
b45a45b9	308	prev_node = cds_ja_lookup_below_equal(ja, range->start - 1, NULL);
c34bfad2 MD	309	if (prev_node) {
c34bfad2 MD	310	struct cds_ja_range *prev_range;
b45a45b9	311
c34bfad2 MD	312	prev_range = caa_container_of(prev_node,
	313	struct cds_ja_range, ja_node);
	314	lock_ranges[nr_lock++] = prev_range;
	315	if (prev_range->type != CDS_JA_RANGE_ALLOCATED)
	316	merge_ranges[nr_merge++] = prev_range;
	317	}
	318
	319	lock_ranges[nr_lock++] = range;
b45a45b9 MD	320	merge_ranges[nr_merge++] = range;
	321
	322	next_node = cds_ja_lookup_above_equal(ja, range->end + 1, NULL);
c34bfad2 MD	323	if (next_node) {
	324	struct cds_ja_range *next_range;
	325
	326	next_range = caa_container_of(next_node,
	327	struct cds_ja_range, ja_node);
	328	lock_ranges[nr_lock++] = next_range;
	329	if (next_range->type != CDS_JA_RANGE_ALLOCATED)
	330	merge_ranges[nr_merge++] = next_range;
	331	}
b45a45b9 MD	332
b45a45b9 MD	333	/* Acquire locks in increasing key order for range merge */
c34bfad2 MD	334	for (i = 0; i < nr_lock; i++)
c34bfad2 MD	335	pthread_mutex_lock(&lock_ranges[i]->lock);
b45a45b9	336	/* Ensure they are valid */
c34bfad2 MD	337	for (i = 0; i < nr_lock; i++) {
c34bfad2 MD	338	if (lock_ranges[i]->type == CDS_JA_RANGE_REMOVED)
b45a45b9 MD	339	goto unlock_retry;
	340	}
	341
	342	/* Create new free range */
	343	start = merge_ranges[0]->start;
	344	end = merge_ranges[nr_merge - 1]->end;
	345	new_range = range_create(start, end, CDS_JA_RANGE_FREE);
	346	ret = cds_ja_add(ja, start, &new_range->ja_node);
	347	assert(!ret);
	348
	349	/* Remove old ranges */
	350	for (i = 0; i < nr_merge; i++) {
	351	ret = cds_ja_del(ja, merge_ranges[i]->start,
	352	&merge_ranges[i]->ja_node);
	353	assert(!ret);
	354	merge_ranges[i]->type = CDS_JA_RANGE_REMOVED;
b45a45b9	355	}
c34bfad2 MD	356	for (i = 0; i < nr_lock; i++)
	357	pthread_mutex_unlock(&lock_ranges[i]->lock);
	358	/* Free old merged ranges */
	359	for (i = 0; i < nr_merge; i++)
	360	rcu_free_range(ja, merge_ranges[i]);
b45a45b9 MD	361
	362	return 0;
	363
	364	/* retry paths */
	365	unlock_retry:
c34bfad2 MD	366	for (i = 0; i < nr_lock; i++)
c34bfad2 MD	367	pthread_mutex_unlock(&lock_ranges[i]->lock);
b45a45b9 MD	368	goto retry;
	369	}
	370
678624e7	371	struct cds_ja _cds_ja_range_new(const struct rcu_flavor_struct flavor)
b45a45b9	372	{
b45a45b9	373	struct cds_ja_range *range;
678624e7	374	struct cds_ja *ja;
b45a45b9 MD	375	int ret;
b45a45b9 MD	376
678624e7 MD	377	ja = _cds_ja_new(CDS_JA_RANGE_KEY_BITS, flavor);
	378	if (!ja)
	379	return NULL;
b45a45b9 MD	380	range = range_create(0, UINT64_MAX, CDS_JA_RANGE_FREE);
b45a45b9 MD	381	if (!range)
678624e7	382	goto free_ja;
b45a45b9	383	ret = cds_ja_add(ja, 0, &range->ja_node);
678624e7 MD	384	if (ret)
	385	goto free_range;
	386	return ja;
	387
	388	free_range:
	389	free_range(range);
	390	free_ja:
	391	ret = cds_ja_destroy(ja);
	392	assert(!ret);
	393	return NULL;
b45a45b9 MD	394	}
b45a45b9 MD	395
678624e7	396	int cds_ja_range_destroy(struct cds_ja *ja)
b45a45b9 MD	397	{
	398	uint64_t key;
	399	struct cds_ja_node *ja_node;
	400	int ret = 0;
	401
	402	cds_ja_for_each_key_rcu(ja, key, ja_node) {
	403	struct cds_ja_node *tmp_node;
	404
	405	cds_ja_for_each_duplicate_safe_rcu(ja_node, tmp_node) {
	406	struct cds_ja_range *range;
	407
	408	range = caa_container_of(ja_node,
	409	struct cds_ja_range, ja_node);
	410	ret = cds_ja_del(ja, key, &range->ja_node);
678624e7 MD	411	if (ret)
678624e7 MD	412	goto error;
b45a45b9 MD	413	/* Alone using Judy array, OK to free now */
	414	free_range(range);
	415	}
	416	}
678624e7 MD	417	return cds_ja_destroy(ja);
	418
	419	error:
b45a45b9 MD	420	return ret;
b45a45b9 MD	421	}