summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/linux/idr.h66
-rw-r--r--lib/idr.c70
-rw-r--r--tools/testing/radix-tree/idr-test.c7
3 files changed, 103 insertions, 40 deletions
diff --git a/include/linux/idr.h b/include/linux/idr.h
index 95a82cf2ed02..86b38df6e121 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -18,6 +18,7 @@
struct idr {
struct radix_tree_root idr_rt;
+ unsigned int idr_base;
unsigned int idr_next;
};
@@ -30,13 +31,21 @@ struct idr {
/* Set the IDR flag and the IDR_FREE tag */
#define IDR_RT_MARKER ((__force gfp_t)(3 << __GFP_BITS_SHIFT))
-#define IDR_INIT \
-{ \
- .idr_rt = RADIX_TREE_INIT(IDR_RT_MARKER) \
+#define IDR_INIT_BASE(base) { \
+ .idr_rt = RADIX_TREE_INIT(IDR_RT_MARKER), \
+ .idr_base = (base), \
+ .idr_next = 0, \
}
#define DEFINE_IDR(name) struct idr name = IDR_INIT
/**
+ * IDR_INIT() - Initialise an IDR.
+ *
+ * A freshly-initialised IDR contains no IDs.
+ */
+#define IDR_INIT IDR_INIT_BASE(0)
+
+/**
* idr_get_cursor - Return the current position of the cyclic allocator
* @idr: idr handle
*
@@ -81,10 +90,12 @@ static inline void idr_set_cursor(struct idr *idr, unsigned int val)
void idr_preload(gfp_t gfp_mask);
-int idr_alloc(struct idr *, void *, int start, int end, gfp_t);
-int __must_check idr_alloc_u32(struct idr *, void *ptr, u32 *nextid,
+int idr_alloc(struct idr *, void *ptr, int start, int end, gfp_t);
+int __must_check idr_alloc_u32(struct idr *, void *ptr, u32 *id,
unsigned long max, gfp_t);
-int idr_alloc_cyclic(struct idr *, void *entry, int start, int end, gfp_t);
+int idr_alloc_cyclic(struct idr *, void *ptr, int start, int end, gfp_t);
+void *idr_remove(struct idr *, unsigned long id);
+void *idr_find(const struct idr *, unsigned long id);
int idr_for_each(const struct idr *,
int (*fn)(int id, void *p, void *data), void *data);
void *idr_get_next(struct idr *, int *nextid);
@@ -92,15 +103,31 @@ void *idr_get_next_ul(struct idr *, unsigned long *nextid);
void *idr_replace(struct idr *, void *, unsigned long id);
void idr_destroy(struct idr *);
-static inline void *idr_remove(struct idr *idr, unsigned long id)
+/**
+ * idr_init_base() - Initialise an IDR.
+ * @idr: IDR handle.
+ * @base: The base value for the IDR.
+ *
+ * This variation of idr_init() creates an IDR which will allocate IDs
+ * starting at %base.
+ */
+static inline void idr_init_base(struct idr *idr, int base)
{
- return radix_tree_delete_item(&idr->idr_rt, id, NULL);
+ INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER);
+ idr->idr_base = base;
+ idr->idr_next = 0;
}
+/**
+ * idr_init() - Initialise an IDR.
+ * @idr: IDR handle.
+ *
+ * Initialise a dynamically allocated IDR. To initialise a
+ * statically allocated IDR, use DEFINE_IDR().
+ */
static inline void idr_init(struct idr *idr)
{
- INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER);
- idr->idr_next = 0;
+ idr_init_base(idr, 0);
}
static inline bool idr_is_empty(const struct idr *idr)
@@ -121,25 +148,6 @@ static inline void idr_preload_end(void)
}
/**
- * idr_find() - Return pointer for given ID.
- * @idr: IDR handle.
- * @id: Pointer ID.
- *
- * Looks up the pointer associated with this ID. A %NULL pointer may
- * indicate that @id is not allocated or that the %NULL pointer was
- * associated with this ID.
- *
- * This function can be called under rcu_read_lock(), given that the leaf
- * pointers lifetimes are correctly managed.
- *
- * Return: The pointer associated with this ID.
- */
-static inline void *idr_find(const struct idr *idr, unsigned long id)
-{
- return radix_tree_lookup(&idr->idr_rt, id);
-}
-
-/**
* idr_for_each_entry() - Iterate over an IDR's elements of a given type.
* @idr: IDR handle.
* @entry: The type * to use as cursor
diff --git a/lib/idr.c b/lib/idr.c
index b47055efceb0..c98d77fcf393 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -36,18 +36,21 @@ int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid,
{
struct radix_tree_iter iter;
void __rcu **slot;
+ int base = idr->idr_base;
+ int id = *nextid;
if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
return -EINVAL;
if (WARN_ON_ONCE(!(idr->idr_rt.gfp_mask & ROOT_IS_IDR)))
idr->idr_rt.gfp_mask |= IDR_RT_MARKER;
- radix_tree_iter_init(&iter, *nextid);
- slot = idr_get_free(&idr->idr_rt, &iter, gfp, max);
+ id = (id < base) ? 0 : id - base;
+ radix_tree_iter_init(&iter, id);
+ slot = idr_get_free(&idr->idr_rt, &iter, gfp, max - base);
if (IS_ERR(slot))
return PTR_ERR(slot);
- *nextid = iter.index;
+ *nextid = iter.index + base;
/* there is a memory barrier inside radix_tree_iter_replace() */
radix_tree_iter_replace(&idr->idr_rt, &iter, slot, ptr);
radix_tree_iter_tag_clear(&idr->idr_rt, &iter, IDR_FREE);
@@ -136,6 +139,46 @@ int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)
EXPORT_SYMBOL(idr_alloc_cyclic);
/**
+ * idr_remove() - Remove an ID from the IDR.
+ * @idr: IDR handle.
+ * @id: Pointer ID.
+ *
+ * Removes this ID from the IDR. If the ID was not previously in the IDR,
+ * this function returns %NULL.
+ *
+ * Since this function modifies the IDR, the caller should provide their
+ * own locking to ensure that concurrent modification of the same IDR is
+ * not possible.
+ *
+ * Return: The pointer formerly associated with this ID.
+ */
+void *idr_remove(struct idr *idr, unsigned long id)
+{
+ return radix_tree_delete_item(&idr->idr_rt, id - idr->idr_base, NULL);
+}
+EXPORT_SYMBOL_GPL(idr_remove);
+
+/**
+ * idr_find() - Return pointer for given ID.
+ * @idr: IDR handle.
+ * @id: Pointer ID.
+ *
+ * Looks up the pointer associated with this ID. A %NULL pointer may
+ * indicate that @id is not allocated or that the %NULL pointer was
+ * associated with this ID.
+ *
+ * This function can be called under rcu_read_lock(), given that the leaf
+ * pointers lifetimes are correctly managed.
+ *
+ * Return: The pointer associated with this ID.
+ */
+void *idr_find(const struct idr *idr, unsigned long id)
+{
+ return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base);
+}
+EXPORT_SYMBOL_GPL(idr_find);
+
+/**
* idr_for_each() - Iterate through all stored pointers.
* @idr: IDR handle.
* @fn: Function to be called for each pointer.
@@ -157,13 +200,14 @@ int idr_for_each(const struct idr *idr,
{
struct radix_tree_iter iter;
void __rcu **slot;
+ int base = idr->idr_base;
radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, 0) {
int ret;
if (WARN_ON_ONCE(iter.index > INT_MAX))
break;
- ret = fn(iter.index, rcu_dereference_raw(*slot), data);
+ ret = fn(iter.index + base, rcu_dereference_raw(*slot), data);
if (ret)
return ret;
}
@@ -186,15 +230,19 @@ void *idr_get_next(struct idr *idr, int *nextid)
{
struct radix_tree_iter iter;
void __rcu **slot;
+ int base = idr->idr_base;
+ int id = *nextid;
- slot = radix_tree_iter_find(&idr->idr_rt, &iter, *nextid);
+ id = (id < base) ? 0 : id - base;
+ slot = radix_tree_iter_find(&idr->idr_rt, &iter, id);
if (!slot)
return NULL;
+ id = iter.index + base;
- if (WARN_ON_ONCE(iter.index > INT_MAX))
+ if (WARN_ON_ONCE(id > INT_MAX))
return NULL;
- *nextid = iter.index;
+ *nextid = id;
return rcu_dereference_raw(*slot);
}
EXPORT_SYMBOL(idr_get_next);
@@ -213,12 +261,15 @@ void *idr_get_next_ul(struct idr *idr, unsigned long *nextid)
{
struct radix_tree_iter iter;
void __rcu **slot;
+ unsigned long base = idr->idr_base;
+ unsigned long id = *nextid;
- slot = radix_tree_iter_find(&idr->idr_rt, &iter, *nextid);
+ id = (id < base) ? 0 : id - base;
+ slot = radix_tree_iter_find(&idr->idr_rt, &iter, id);
if (!slot)
return NULL;
- *nextid = iter.index;
+ *nextid = iter.index + base;
return rcu_dereference_raw(*slot);
}
EXPORT_SYMBOL(idr_get_next_ul);
@@ -245,6 +296,7 @@ void *idr_replace(struct idr *idr, void *ptr, unsigned long id)
if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
return ERR_PTR(-EINVAL);
+ id -= idr->idr_base;
entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot);
if (!slot || radix_tree_tag_get(&idr->idr_rt, id, IDR_FREE))
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 36437ade429c..44ef9eba5a7a 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -153,11 +153,12 @@ void idr_nowait_test(void)
idr_destroy(&idr);
}
-void idr_get_next_test(void)
+void idr_get_next_test(int base)
{
unsigned long i;
int nextid;
DEFINE_IDR(idr);
+ idr_init_base(&idr, base);
int indices[] = {4, 7, 9, 15, 65, 128, 1000, 99999, 0};
@@ -244,7 +245,9 @@ void idr_checks(void)
idr_alloc_test();
idr_null_test();
idr_nowait_test();
- idr_get_next_test();
+ idr_get_next_test(0);
+ idr_get_next_test(1);
+ idr_get_next_test(4);
}
/*
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-04 06:09:13 +0000