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
