[PATCH rdma-core 04/27] util: Add interval_set support

[Yishai Hadas <yishaih@nvidia.com>]

From: Mark Zhang <markzhang@nvidia.com>

Add interval_set functionality to support range management.

This functionality enables to insert/get valid ranges of values and
maintains the contiguity of them internally.

This will be used in down stream patches from this series to set/get
valid iova ranges from this data structure.

Signed-off-by: Mark Zhang <markzhang@nvidia.com>
Signed-off-by: Yishai Hadas <yishaih@nvidia.com>
---
 util/CMakeLists.txt |   2 +
 util/interval_set.c | 208 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 util/interval_set.h |  77 +++++++++++++++++++
 3 files changed, 287 insertions(+)
 create mode 100644 util/interval_set.c
 create mode 100644 util/interval_set.h

diff --git a/util/CMakeLists.txt b/util/CMakeLists.txt
index e8646bf..d8a66be 100644
--- a/util/CMakeLists.txt
+++ b/util/CMakeLists.txt
@@ -1,6 +1,7 @@
 publish_internal_headers(util
   cl_qmap.h
   compiler.h
+  interval_set.h
   node_name_map.h
   rdma_nl.h
   symver.h
@@ -9,6 +10,7 @@ publish_internal_headers(util
 
 set(C_FILES
   cl_map.c
+  interval_set.c
   node_name_map.c
   open_cdev.c
   rdma_nl.c
diff --git a/util/interval_set.c b/util/interval_set.c
new file mode 100644
index 0000000..9fb9bde
--- /dev/null
+++ b/util/interval_set.c
@@ -0,0 +1,208 @@
+/* GPLv2 or OpenIB.org BSD (MIT) See COPYING file */
+
+#include <errno.h>
+#include <pthread.h>
+#include <stdlib.h>
+
+#include <ccan/list.h>
+#include <util/interval_set.h>
+#include <util/util.h>
+
+struct iset {
+	struct list_head head;
+	pthread_mutex_t lock;
+};
+
+struct iset_range {
+	struct list_node entry;
+	uint64_t start;
+	uint64_t length;
+};
+
+struct iset *iset_create(void)
+{
+	struct iset *iset;
+
+	iset = calloc(1, sizeof(*iset));
+	if (!iset) {
+		errno = ENOMEM;
+		return NULL;
+	}
+
+	pthread_mutex_init(&iset->lock, NULL);
+	list_head_init(&iset->head);
+	return iset;
+}
+
+void iset_destroy(struct iset *iset)
+{
+	struct iset_range *range, *tmp;
+
+	list_for_each_safe(&iset->head, range, tmp, entry)
+		free(range);
+
+	free(iset);
+}
+
+static int
+range_overlap(uint64_t s1, uint64_t len1, uint64_t s2, uint64_t len2)
+{
+	if (((s1 < s2) && (s1 + len1 - 1 < s2)) ||
+	    ((s1 > s2) && (s1 > s2 + len2 - 1)))
+		return 0;
+
+	return 1;
+}
+
+static struct iset_range *create_range(uint64_t start, uint64_t length)
+{
+	struct iset_range *range;
+
+	range = calloc(1, sizeof(*range));
+	if (!range) {
+		errno = ENOMEM;
+		return NULL;
+	}
+
+	range->start = start;
+	range->length = length;
+	return range;
+}
+
+static void delete_range(struct iset_range *r)
+{
+	list_del(&r->entry);
+	free(r);
+}
+
+static bool check_do_combine(struct iset *iset,
+			     struct iset_range *p, struct iset_range *n,
+			     uint64_t start, uint64_t length)
+{
+	bool combined2prev = false, combined2next = false;
+
+	if (p && (p->start + p->length == start)) {
+		p->length += length;
+		combined2prev = true;
+	}
+
+	if (n && (start + length == n->start)) {
+		if (combined2prev) {
+			p->length += n->length;
+			delete_range(n);
+		} else {
+			n->start = start;
+			n->length += length;
+		}
+		combined2next = true;
+	}
+
+	return combined2prev || combined2next;
+}
+
+int iset_insert_range(struct iset *iset, uint64_t start, uint64_t length)
+{
+	struct iset_range *prev = NULL, *r, *rnew;
+	bool found = false, combined;
+	int ret = 0;
+
+	if (!length || (start + length - 1 < start)) {
+		errno = EINVAL;
+		return errno;
+	}
+
+	pthread_mutex_lock(&iset->lock);
+	list_for_each(&iset->head, r, entry) {
+		if (range_overlap(r->start, r->length, start, length)) {
+			errno = EINVAL;
+			ret = errno;
+			goto out;
+		}
+
+		if (r->start > start) {
+			found = true;
+			break;
+		}
+
+		prev = r;
+	}
+
+	combined = check_do_combine(iset, prev, found ? r : NULL,
+				    start, length);
+	if (!combined) {
+		rnew = create_range(start, length);
+		if (!rnew) {
+			ret = errno;
+			goto out;
+		}
+
+		if (!found)
+			list_add_tail(&iset->head, &rnew->entry);
+		else
+			list_add_before(&iset->head, &r->entry, &rnew->entry);
+	}
+
+out:
+	pthread_mutex_unlock(&iset->lock);
+	return ret;
+}
+
+static int power_of_two(uint64_t x)
+{
+	return ((x != 0) && !(x & (x - 1)));
+}
+
+int iset_alloc_range(struct iset *iset, uint64_t length, uint64_t *start)
+{
+	struct iset_range *r, *rnew;
+	uint64_t astart, rend;
+	bool found = false;
+	int ret = 0;
+
+	if (!power_of_two(length)) {
+		errno = EINVAL;
+		return errno;
+	}
+
+	pthread_mutex_lock(&iset->lock);
+	list_for_each(&iset->head, r, entry) {
+		astart = align(r->start, length);
+		/* Check for wrap around */
+		if ((astart + length - 1 >= astart) &&
+		    (astart + length - 1 <= r->start + r->length - 1)) {
+			found = true;
+			break;
+		}
+	}
+	if (!found) {
+		errno = ENOSPC;
+		ret = errno;
+		goto out;
+	}
+
+	if (r->start == astart) {
+		if (r->length == length) { /* Case #1 */
+			delete_range(r);
+		} else {	/* Case #2 */
+			r->start += length;
+			r->length -= length;
+		}
+	} else {
+		rend = r->start + r->length;
+		if (astart + length != rend) { /* Case #4 */
+			rnew = create_range(astart + length,
+					    rend - astart - length);
+			if (!rnew) {
+				ret = errno;
+				goto out;
+			}
+			list_add_after(&iset->head, &r->entry, &rnew->entry);
+		}
+		r->length = astart - r->start; /* Case #3 & #4 */
+	}
+
+	*start = astart;
+out:
+	pthread_mutex_unlock(&iset->lock);
+	return ret;
+}
diff --git a/util/interval_set.h b/util/interval_set.h
new file mode 100644
index 0000000..d5b1f56
--- /dev/null
+++ b/util/interval_set.h
@@ -0,0 +1,77 @@
+/* GPLv2 or OpenIB.org BSD (MIT) See COPYING file */
+
+#include <stdint.h>
+
+struct iset;
+
+/**
+ * iset_create - Create an interval set
+ *
+ * Return the created iset if succeeded, NULL otherwise, with errno set
+ */
+struct iset *iset_create(void);
+
+/**
+ * iset_destroy - Destroy an interval set
+ * @iset: The set to be destroyed
+ */
+void iset_destroy(struct iset *iset);
+
+/**
+ * iset_insert_range - Insert a range to the set
+ * @iset: The set to be operated
+ * @start: The start address of the range
+ * @length: The length of the range
+ *
+ * If this range is continuous to the adjacent ranges (before and/or after),
+ * then they will be combined to a larger one.
+ *
+ * Return 0 if succeeded, errno otherwise
+ */
+int iset_insert_range(struct iset *iset, uint64_t start, uint64_t length);
+
+/**
+ * iset_alloc_range - Allocate a range from the set
+ *
+ * @iset: The set to be operated
+ * @length: The length of the range, must be power of two
+ * @start: The start address of the allocated range, aligned with @length
+ *
+ * Return 0 if succeeded, errno otherwise
+ *
+ * Note: There are these cases:
+ *
+Case 1: Original range is fully taken
++------------------+
+|XXXXXXXXXXXXXXXXXX|
++------------------+
+=>  (NULL)
+
+Case 2: Original range shrunk
++------------------+
+|XXXXX             |
++------------------+
+=>
+      +------------+
+      |            |
+      +------------+
+
+Case 3: Original range shrunk
++------------------+
+|             XXXXX|
++------------------+
+=>
++------------+
+|            |
++------------+
+
+Case 4: Original range splited
++------------------+
+|      XXXXX       |
++------------------+
+=>
++-----+     +------+
+|     |     |      |
++-----+     +------+
+*/
+int iset_alloc_range(struct iset *iset, uint64_t length, uint64_t *start);
-- 
1.8.3.1