[PATCH 2/3] ida: Introduce ida_alloc_group_range()

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



Some drivers may require allocations of contiguous ranges of IDs,
while current IDA implementation allows only single ID allocation.

Extend implementation of ida_alloc_range() to allow allocation of
arbitrary number of contiguous IDs.  Allocated IDs can be released
individually with old ida_free() or can be released at once using
new ida_free_group() function.

Signed-off-by: Michal Wajdeczko <michal.wajdeczko@xxxxxxxxx>
Cc: Matthew Wilcox <willy@xxxxxxxxxxxxx>
---
 include/linux/idr.h |   3 +
 lib/idr.c           | 215 ++++++++++++++++++++++++++++++++++----------
 2 files changed, 172 insertions(+), 46 deletions(-)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index f477e35c9619..ecc403543d6a 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -253,7 +253,10 @@ struct ida {
 #define DEFINE_IDA(name)	struct ida name = IDA_INIT(name)
 
 int ida_alloc_range(struct ida *, unsigned int min, unsigned int max, gfp_t);
+int ida_alloc_group_range(struct ida *ida, unsigned int min, unsigned int max,
+			  unsigned int group, gfp_t gfp);
 void ida_free(struct ida *, unsigned int id);
+void ida_free_group(struct ida *ida, unsigned int id, unsigned int group);
 void ida_destroy(struct ida *ida);
 unsigned long ida_weight(struct ida *ida);
 
diff --git a/lib/idr.c b/lib/idr.c
index ed987a0fc25a..68ec837b67bc 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -362,34 +362,41 @@ EXPORT_SYMBOL(idr_replace);
  * bitmap, which is excessive.
  */
 
+static void __ida_free_group(struct ida *ida, unsigned int id, unsigned int group);
+
 /**
- * ida_alloc_range() - Allocate an unused ID.
+ * ida_alloc_group_range() - Allocate contiguous group of an unused IDs.
  * @ida: IDA handle.
  * @min: Lowest ID to allocate.
  * @max: Highest ID to allocate.
+ * @group: Number of extra IDs to allocate.
  * @gfp: Memory allocation flags.
  *
- * Allocate an ID between @min and @max, inclusive.  The allocated ID will
- * not exceed %INT_MAX, even if @max is larger.
+ * Allocate contiguous set of (1 + @group) IDs between @min and @max, inclusive.
+ * The allocated IDs will not exceed %INT_MAX, even if @max is larger.
  *
  * Context: Any context. It is safe to call this function without
  * locking in your code.
- * Return: The allocated ID, or %-ENOMEM if memory could not be allocated,
- * or %-ENOSPC if there are no free IDs.
+ * Return: The first allocated ID, or %-ENOMEM if memory could not be allocated,
+ * or %-ENOSPC if there are no free contiguous range of IDs.
  */
-int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max,
-			gfp_t gfp)
+int ida_alloc_group_range(struct ida *ida, unsigned int min, unsigned int max,
+			  unsigned int group, gfp_t gfp)
 {
 	XA_STATE(xas, &ida->xa, min / IDA_BITMAP_BITS);
 	unsigned bit = min % IDA_BITMAP_BITS;
 	unsigned long flags;
 	struct ida_bitmap *bitmap, *alloc = NULL;
+	unsigned int start, end, chunk, nbit;
+	unsigned int more = group;
 
 	if ((int)min < 0)
 		return -ENOSPC;
 
 	if ((int)max < 0)
 		max = INT_MAX;
+	end = max;
+	start = end + 1;
 
 retry:
 	xas_lock_irqsave(&xas, flags);
@@ -397,18 +404,21 @@ int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max,
 	bitmap = xas_find_marked(&xas, max / IDA_BITMAP_BITS, XA_FREE_MARK);
 	if (xas.xa_index > min / IDA_BITMAP_BITS)
 		bit = 0;
-	if (xas.xa_index * IDA_BITMAP_BITS + bit > max)
+	if (xas.xa_index * IDA_BITMAP_BITS + bit + more > max)
 		goto nospc;
 
 	if (xa_is_value(bitmap)) {
 		unsigned long tmp = xa_to_value(bitmap);
 
-		if (bit < BITS_PER_XA_VALUE) {
+		if (bit + more < BITS_PER_XA_VALUE) {
 			bit = find_next_zero_bit(&tmp, BITS_PER_XA_VALUE, bit);
-			if (xas.xa_index * IDA_BITMAP_BITS + bit > max)
+			if (xas.xa_index * IDA_BITMAP_BITS + bit + more > max)
 				goto nospc;
-			if (bit < BITS_PER_XA_VALUE) {
-				tmp |= 1UL << bit;
+			if (more == group)
+				start = xas.xa_index * IDA_BITMAP_BITS + bit;
+			if (bit + more < BITS_PER_XA_VALUE &&
+			    bit + more < find_next_bit(&tmp, bit + more + 1, bit)) {
+				tmp |= GENMASK(bit + more, bit);
 				xas_store(&xas, xa_mk_value(tmp));
 				goto out;
 			}
@@ -424,27 +434,41 @@ int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max,
 			bitmap->bitmap[0] = 0;
 			goto out;
 		}
+		alloc = NULL;
 	}
 
 	if (bitmap) {
 		bit = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, bit);
-		if (xas.xa_index * IDA_BITMAP_BITS + bit > max)
+		if (xas.xa_index * IDA_BITMAP_BITS + bit + more > max)
 			goto nospc;
 		if (bit == IDA_BITMAP_BITS)
 			goto next;
-
+		if (more == group)
+			start = xas.xa_index * IDA_BITMAP_BITS + bit;
+		if (more)
+			goto more;
 		__set_bit(bit, bitmap->bitmap);
 		if (bitmap_full(bitmap->bitmap, IDA_BITMAP_BITS))
 			xas_clear_mark(&xas, XA_FREE_MARK);
 	} else {
-		if (bit < BITS_PER_XA_VALUE) {
-			bitmap = xa_mk_value(1UL << bit);
+		if (more == group)
+			start = xas.xa_index * IDA_BITMAP_BITS + bit;
+
+		if (bit + more < BITS_PER_XA_VALUE) {
+			bitmap = xa_mk_value(GENMASK(bit + more, bit));
 		} else {
 			bitmap = alloc;
 			if (!bitmap)
 				bitmap = kzalloc(sizeof(*bitmap), GFP_NOWAIT);
 			if (!bitmap)
 				goto alloc;
+			if (more) {
+				xas_store(&xas, bitmap);
+				if (xas_error(&xas))
+					goto out;
+				alloc = NULL;
+				goto more;
+			}
 			__set_bit(bit, bitmap->bitmap);
 		}
 		xas_store(&xas, bitmap);
@@ -460,7 +484,7 @@ int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max,
 		kfree(alloc);
 	if (xas_error(&xas))
 		return xas_error(&xas);
-	return xas.xa_index * IDA_BITMAP_BITS + bit;
+	return WARN_ON_ONCE(start > end) ? -ENOSPC : start;
 alloc:
 	xas_unlock_irqrestore(&xas, flags);
 	alloc = kzalloc(sizeof(*bitmap), gfp);
@@ -469,60 +493,159 @@ int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max,
 	xas_set(&xas, min / IDA_BITMAP_BITS);
 	bit = min % IDA_BITMAP_BITS;
 	goto retry;
+restart:
+	max = end;
+	more = group;
+	start = end + 1;
+	goto next;
+more:
+	chunk = bit + more < IDA_BITMAP_BITS ?
+		1 + more : IDA_BITMAP_BITS - bit;
+	nbit = find_next_bit(bitmap->bitmap, bit + chunk, bit);
+	if (nbit < bit + chunk) {
+		min = xas.xa_index * IDA_BITMAP_BITS + nbit + 1;
+		bit = min % IDA_BITMAP_BITS;
+		xas_set(&xas, min / IDA_BITMAP_BITS);
+		if (group == more)
+			goto restart;
+		goto nospc;
+	}
+	bitmap_set(bitmap->bitmap, bit, chunk);
+	if (bitmap_full(bitmap->bitmap, IDA_BITMAP_BITS))
+		xas_clear_mark(&xas, XA_FREE_MARK);
+	if (chunk < 1 + more) {
+		more -= chunk;
+		min = (xas.xa_index + 1) * IDA_BITMAP_BITS;
+		max = min + more;
+		xas_set(&xas, min / IDA_BITMAP_BITS);
+		bit = 0;
+		goto next;
+	}
+	goto out;
 nospc:
+	if (more != group) {
+		__ida_free_group(ida, start, group - more - 1);
+		xas_reset(&xas);
+		goto restart;
+	}
 	xas_unlock_irqrestore(&xas, flags);
 	kfree(alloc);
 	return -ENOSPC;
 }
+EXPORT_SYMBOL(ida_alloc_group_range);
+
+/**
+ * ida_alloc_range() - Allocate an unused ID.
+ * @ida: IDA handle.
+ * @min: Lowest ID to allocate.
+ * @max: Highest ID to allocate.
+ * @gfp: Memory allocation flags.
+ *
+ * Allocate an ID between @min and @max, inclusive.  The allocated ID will
+ * not exceed %INT_MAX, even if @max is larger.
+ *
+ * Context: Any context. It is safe to call this function without
+ * locking in your code.
+ * Return: The allocated ID, or %-ENOMEM if memory could not be allocated,
+ * or %-ENOSPC if there are no free IDs.
+ */
+int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max,
+		    gfp_t gfp)
+{
+	return ida_alloc_group_range(ida, min, max, 0, gfp);
+}
 EXPORT_SYMBOL(ida_alloc_range);
 
-/**
- * ida_free() - Release an allocated ID.
- * @ida: IDA handle.
- * @id: Previously allocated ID.
- *
- * Context: Any context. It is safe to call this function without
- * locking in your code.
- */
-void ida_free(struct ida *ida, unsigned int id)
+static void __ida_free_group(struct ida *ida, unsigned int id, unsigned int group)
 {
 	XA_STATE(xas, &ida->xa, id / IDA_BITMAP_BITS);
 	unsigned bit = id % IDA_BITMAP_BITS;
+	unsigned int chunk, more = group;
 	struct ida_bitmap *bitmap;
-	unsigned long flags;
+	bool set = true;
 
 	if ((int)id < 0)
 		return;
 
-	xas_lock_irqsave(&xas, flags);
+next:
 	bitmap = xas_load(&xas);
 
+	chunk = bit + more < IDA_BITMAP_BITS ?
+		1 + more : IDA_BITMAP_BITS - bit;
+
 	if (xa_is_value(bitmap)) {
 		unsigned long v = xa_to_value(bitmap);
-		if (bit >= BITS_PER_XA_VALUE)
-			goto err;
-		if (!(v & (1UL << bit)))
-			goto err;
-		v &= ~(1UL << bit);
-		if (!v)
-			goto delete;
-		xas_store(&xas, xa_mk_value(v));
-	} else {
-		if (!test_bit(bit, bitmap->bitmap))
-			goto err;
-		__clear_bit(bit, bitmap->bitmap);
+		unsigned long m;
+
+		if (bit + more >= BITS_PER_XA_VALUE) {
+			m = GENMASK(BITS_PER_XA_VALUE - 1, bit);
+			set = false;
+		} else {
+			m = GENMASK(bit + more, bit);
+			set = set && !((v & m) ^ m);
+		}
+		v &= ~m;
+		xas_store(&xas, v ? xa_mk_value(v) : NULL);
+	} else if (bitmap) {
+		unsigned int nbit;
+
+		nbit = find_next_zero_bit(bitmap->bitmap, bit + chunk, bit);
+		if (nbit < bit + chunk)
+			set = false;
+		bitmap_clear(bitmap->bitmap, bit, chunk);
 		xas_set_mark(&xas, XA_FREE_MARK);
 		if (bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) {
 			kfree(bitmap);
-delete:
 			xas_store(&xas, NULL);
 		}
+	} else {
+		set = false;
 	}
-	xas_unlock_irqrestore(&xas, flags);
-	return;
- err:
-	xas_unlock_irqrestore(&xas, flags);
-	WARN(1, "ida_free called for id=%d which is not allocated.\n", id);
+
+	if (chunk < 1 + more) {
+		more -= chunk;
+		xas_set(&xas, xas.xa_index + 1);
+		bit = 0;
+		goto next;
+	}
+
+	WARN(!set, "IDA: trying to free non contiguous IDs %u..%u!\n", id, id + group);
+}
+
+/**
+ * ida_free_group() - Release contiguous group of an allocated IDs.
+ * @ida: IDA handle.
+ * @id: First ID of the group.
+ * @group: Number of extra IDs in group.
+ *
+ * Context: Any context. It is safe to call this function without
+ * locking in your code.
+ */
+void ida_free_group(struct ida *ida, unsigned int id, unsigned int group)
+{
+	unsigned long flags;
+
+	xa_lock_irqsave(&ida->xa, flags);
+	__ida_free_group(ida, id, group);
+	xa_unlock_irqrestore(&ida->xa, flags);
+}
+EXPORT_SYMBOL(ida_free_group);
+
+/**
+ * ida_free() - Release an allocated ID.
+ * @ida: IDA handle.
+ * @id: Previously allocated ID.
+ *
+ * Context: Any context. It is safe to call this function without
+ * locking in your code.
+ */
+void ida_free(struct ida *ida, unsigned int id)
+{
+	unsigned long flags;
+
+	xa_lock_irqsave(&ida->xa, flags);
+	__ida_free_group(ida, id, 0);
+	xa_unlock_irqrestore(&ida->xa, flags);
 }
 EXPORT_SYMBOL(ida_free);
 
-- 
2.25.1





[Index of Archives]     [Linux Ext4 Filesystem]     [Union Filesystem]     [Filesystem Testing]     [Ceph Users]     [Ecryptfs]     [NTFS 3]     [AutoFS]     [Kernel Newbies]     [Share Photos]     [Security]     [Netfilter]     [Bugtraq]     [Yosemite News]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux Cachefs]     [Reiser Filesystem]     [Linux RAID]     [NTFS 3]     [Samba]     [Device Mapper]     [CEPH Development]

  Powered by Linux