From 9c160941403ba833c8e67981806ccae73ff7aca7 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Tue, 28 Nov 2017 09:48:43 -0500 Subject: idr: Delete idr_remove_ext function Simply changing idr_remove's 'id' argument to 'unsigned long' suffices for all callers. Signed-off-by: Matthew Wilcox --- include/linux/idr.h | 7 +------ 1 file changed, 1 insertion(+), 6 deletions(-) (limited to 'include/linux') diff --git a/include/linux/idr.h b/include/linux/idr.h index fa14f834e4ed..118987a17ada 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -140,16 +140,11 @@ void *idr_replace(struct idr *, void *, int id); void *idr_replace_ext(struct idr *idr, void *ptr, unsigned long id); void idr_destroy(struct idr *); -static inline void *idr_remove_ext(struct idr *idr, unsigned long id) +static inline void *idr_remove(struct idr *idr, unsigned long id) { return radix_tree_delete_item(&idr->idr_rt, id, NULL); } -static inline void *idr_remove(struct idr *idr, int id) -{ - return idr_remove_ext(idr, id); -} - static inline void idr_init(struct idr *idr) { INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER); -- cgit v1.2.3 From 234a4624efe5629a777b4c00dbdf41dd8b7332db Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Tue, 28 Nov 2017 09:56:36 -0500 Subject: idr: Delete idr_replace_ext function Changing idr_replace's 'id' argument to 'unsigned long' works for all callers. Callers which passed a negative ID now get -ENOENT instead of -EINVAL. No callers relied on this error value. Signed-off-by: Matthew Wilcox --- include/linux/idr.h | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'include/linux') diff --git a/include/linux/idr.h b/include/linux/idr.h index 118987a17ada..f1299c4dc45f 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -136,8 +136,7 @@ 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); void *idr_get_next_ext(struct idr *idr, unsigned long *nextid); -void *idr_replace(struct idr *, void *, int id); -void *idr_replace_ext(struct idr *idr, void *ptr, unsigned long id); +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) -- cgit v1.2.3 From 322d884ba731e05ca79ae58e9dee1ef7dc4de504 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Tue, 28 Nov 2017 10:01:24 -0500 Subject: idr: Delete idr_find_ext function Simply changing idr_remove's 'id' argument to 'unsigned long' works for all callers. Signed-off-by: Matthew Wilcox --- include/linux/idr.h | 7 +------ 1 file changed, 1 insertion(+), 6 deletions(-) (limited to 'include/linux') diff --git a/include/linux/idr.h b/include/linux/idr.h index f1299c4dc45f..7867d6117535 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -179,16 +179,11 @@ static inline void idr_preload_end(void) * This function can be called under rcu_read_lock(), given that the leaf * pointers lifetimes are correctly managed. */ -static inline void *idr_find_ext(const struct idr *idr, unsigned long id) +static inline void *idr_find(const struct idr *idr, unsigned long id) { return radix_tree_lookup(&idr->idr_rt, id); } -static inline void *idr_find(const struct idr *idr, int id) -{ - return idr_find_ext(idr, id); -} - /** * idr_for_each_entry - iterate over an idr's elements of a given type * @idr: idr handle -- cgit v1.2.3 From e096f6a762bc54d0e5d44ba8b196e70b58e04367 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Tue, 28 Nov 2017 10:14:27 -0500 Subject: idr: Add idr_alloc_u32 helper All current users of idr_alloc_ext() actually want to allocate a u32 and idr_alloc_u32() fits their needs better. Like idr_get_next(), it uses a 'nextid' argument which serves as both a pointer to the start ID and the assigned ID (instead of a separate minimum and pointer-to-assigned-ID argument). It uses a 'max' argument rather than 'end' because the semantics that idr_alloc has for 'end' don't work well for unsigned types. Since idr_alloc_u32() returns an errno instead of the allocated ID, mark it as __must_check to help callers use it correctly. Include copious kernel-doc. Chris Mi has promised to contribute test-cases for idr_alloc_u32. Signed-off-by: Matthew Wilcox --- include/linux/idr.h | 2 ++ 1 file changed, 2 insertions(+) (limited to 'include/linux') diff --git a/include/linux/idr.h b/include/linux/idr.h index 7867d6117535..561a4cbabca6 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -131,6 +131,8 @@ static inline int idr_alloc_ext(struct idr *idr, void *ptr, return idr_alloc_cmn(idr, ptr, index, start, end, gfp, true); } +int __must_check idr_alloc_u32(struct idr *, void *ptr, u32 *nextid, + unsigned long max, gfp_t); int idr_alloc_cyclic(struct idr *, void *entry, int start, int end, gfp_t); int idr_for_each(const struct idr *, int (*fn)(int id, void *p, void *data), void *data); -- cgit v1.2.3 From 460488c58ca8b9167463ac22ec9a2e33db351962 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Tue, 28 Nov 2017 15:16:24 -0500 Subject: idr: Remove idr_alloc_ext It has no more users, so remove it. Move idr_alloc() back into idr.c, move the guts of idr_alloc_cmn() into idr_alloc_u32(), remove the wrappers around idr_get_free_cmn() and rename it to idr_get_free(). While there is now no interface to allocate IDs larger than a u32, the IDR internals remain ready to handle a larger ID should a need arise. These changes make it possible to provide the guarantee that, if the nextid pointer points into the object, the object's ID will be initialised before a concurrent lookup can find the object. Signed-off-by: Matthew Wilcox --- include/linux/idr.h | 51 +--------------------------------------------- include/linux/radix-tree.h | 17 +--------------- 2 files changed, 2 insertions(+), 66 deletions(-) (limited to 'include/linux') diff --git a/include/linux/idr.h b/include/linux/idr.h index 561a4cbabca6..fa2a04b984df 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -15,7 +15,6 @@ #include #include #include -#include struct idr { struct radix_tree_root idr_rt; @@ -82,55 +81,7 @@ static inline void idr_set_cursor(struct idr *idr, unsigned int val) void idr_preload(gfp_t gfp_mask); -int idr_alloc_cmn(struct idr *idr, void *ptr, unsigned long *index, - unsigned long start, unsigned long end, gfp_t gfp, - bool ext); - -/** - * idr_alloc - allocate an id - * @idr: idr handle - * @ptr: pointer to be associated with the new id - * @start: the minimum id (inclusive) - * @end: the maximum id (exclusive) - * @gfp: memory allocation flags - * - * Allocates an unused ID in the range [start, end). Returns -ENOSPC - * if there are no unused IDs in that range. - * - * Note that @end is treated as max when <= 0. This is to always allow - * using @start + N as @end as long as N is inside integer range. - * - * Simultaneous modifications to the @idr are not allowed and should be - * prevented by the user, usually with a lock. idr_alloc() may be called - * concurrently with read-only accesses to the @idr, such as idr_find() and - * idr_for_each_entry(). - */ -static inline int idr_alloc(struct idr *idr, void *ptr, - int start, int end, gfp_t gfp) -{ - unsigned long id; - int ret; - - if (WARN_ON_ONCE(start < 0)) - return -EINVAL; - - ret = idr_alloc_cmn(idr, ptr, &id, start, end, gfp, false); - - if (ret) - return ret; - - return id; -} - -static inline int idr_alloc_ext(struct idr *idr, void *ptr, - unsigned long *index, - unsigned long start, - unsigned long end, - gfp_t gfp) -{ - return idr_alloc_cmn(idr, ptr, index, start, end, gfp, true); -} - +int idr_alloc(struct idr *, void *, int start, int end, gfp_t); int __must_check idr_alloc_u32(struct idr *, void *ptr, u32 *nextid, unsigned long max, gfp_t); int idr_alloc_cyclic(struct idr *, void *entry, int start, int end, gfp_t); diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index 23a9c89c7ad9..fc55ff31eca7 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -356,24 +356,9 @@ int radix_tree_split(struct radix_tree_root *, unsigned long index, int radix_tree_join(struct radix_tree_root *, unsigned long index, unsigned new_order, void *); -void __rcu **idr_get_free_cmn(struct radix_tree_root *root, +void __rcu **idr_get_free(struct radix_tree_root *root, struct radix_tree_iter *iter, gfp_t gfp, unsigned long max); -static inline void __rcu **idr_get_free(struct radix_tree_root *root, - struct radix_tree_iter *iter, - gfp_t gfp, - int end) -{ - return idr_get_free_cmn(root, iter, gfp, end > 0 ? end - 1 : INT_MAX); -} - -static inline void __rcu **idr_get_free_ext(struct radix_tree_root *root, - struct radix_tree_iter *iter, - gfp_t gfp, - unsigned long end) -{ - return idr_get_free_cmn(root, iter, gfp, end - 1); -} enum { RADIX_TREE_ITER_TAG_MASK = 0x0f, /* tag index in lower nybble */ -- cgit v1.2.3 From 7a4575778f4db109b8b78e6dba03271096793f88 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Tue, 28 Nov 2017 15:39:51 -0500 Subject: idr: Rename idr_for_each_entry_ext Most places in the kernel that we need to distinguish functions by the type of their arguments, we use '_ul' as a suffix for the unsigned long variant, not '_ext'. Also add kernel-doc. Signed-off-by: Matthew Wilcox --- include/linux/idr.h | 52 ++++++++++++++++++++++++++++++++-------------------- 1 file changed, 32 insertions(+), 20 deletions(-) (limited to 'include/linux') diff --git a/include/linux/idr.h b/include/linux/idr.h index fa2a04b984df..95a82cf2ed02 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -88,7 +88,7 @@ int idr_alloc_cyclic(struct idr *, void *entry, int start, int end, gfp_t); 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); -void *idr_get_next_ext(struct idr *idr, unsigned long *nextid); +void *idr_get_next_ul(struct idr *, unsigned long *nextid); void *idr_replace(struct idr *, void *, unsigned long id); void idr_destroy(struct idr *); @@ -121,16 +121,18 @@ static inline void idr_preload_end(void) } /** - * idr_find - return pointer for given id - * @idr: idr handle - * @id: lookup key + * idr_find() - Return pointer for given ID. + * @idr: IDR handle. + * @id: Pointer ID. * - * Return the pointer given the id it has been registered with. A %NULL - * return indicates that @id is not valid or you passed %NULL in - * idr_get_new(). + * 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) { @@ -138,28 +140,38 @@ static inline void *idr_find(const struct idr *idr, unsigned long 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 - * @id: id entry's key + * idr_for_each_entry() - Iterate over an IDR's elements of a given type. + * @idr: IDR handle. + * @entry: The type * to use as cursor + * @id: Entry ID. * * @entry and @id do not need to be initialized before the loop, and - * after normal terminatinon @entry is left with the value NULL. This + * after normal termination @entry is left with the value NULL. This * is convenient for a "not found" value. */ #define idr_for_each_entry(idr, entry, id) \ for (id = 0; ((entry) = idr_get_next(idr, &(id))) != NULL; ++id) -#define idr_for_each_entry_ext(idr, entry, id) \ - for (id = 0; ((entry) = idr_get_next_ext(idr, &(id))) != NULL; ++id) /** - * idr_for_each_entry_continue - continue iteration over an idr's elements of a given type - * @idr: idr handle - * @entry: the type * to use as cursor - * @id: id entry's key + * idr_for_each_entry_ul() - Iterate over an IDR's elements of a given type. + * @idr: IDR handle. + * @entry: The type * to use as cursor. + * @id: Entry ID. + * + * @entry and @id do not need to be initialized before the loop, and + * after normal termination @entry is left with the value NULL. This + * is convenient for a "not found" value. + */ +#define idr_for_each_entry_ul(idr, entry, id) \ + for (id = 0; ((entry) = idr_get_next_ul(idr, &(id))) != NULL; ++id) + +/** + * idr_for_each_entry_continue() - Continue iteration over an IDR's elements of a given type + * @idr: IDR handle. + * @entry: The type * to use as a cursor. + * @id: Entry ID. * - * Continue to iterate over list of given type, continuing after - * the current position. + * Continue to iterate over entries, continuing after the current position. */ #define idr_for_each_entry_continue(idr, entry, id) \ for ((entry) = idr_get_next((idr), &(id)); \ -- cgit v1.2.3 From 6ce711f2750031d12cec91384ac5cfa0a485b60a Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Thu, 30 Nov 2017 13:45:11 -0500 Subject: idr: Make 1-based IDRs more efficient About 20% of the IDR users in the kernel want the allocated IDs to start at 1. The implementation currently searches all the way down the left hand side of the tree, finds no free ID other than ID 0, walks all the way back up, and then all the way down again. This patch 'rebases' the ID so we fill the entire radix tree, rather than leave a gap at 0. Chris Wilson says: "I did the quick hack of allocating index 0 of the idr and that eradicated idr_get_free() from being at the top of the profiles for the many-object stress tests. This improvement will be much appreciated." Signed-off-by: Matthew Wilcox --- include/linux/idr.h | 66 ++++++++++++++++++++++++++++++----------------------- 1 file changed, 37 insertions(+), 29 deletions(-) (limited to 'include/linux') 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,12 +31,20 @@ 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) @@ -120,25 +147,6 @@ static inline void idr_preload_end(void) preempt_enable(); } -/** - * 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. -- cgit v1.2.3 From ac665d9423474e64e64b34b0e2cea43601b50d7d Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Tue, 6 Feb 2018 15:05:49 -0500 Subject: idr: Add documentation Move the idr kernel-doc to its own idr.rst file and add a few paragraphs about how to use it. Also add some more kernel-doc. Signed-off-by: Matthew Wilcox --- include/linux/idr.h | 16 +++++++++++++++- 1 file changed, 15 insertions(+), 1 deletion(-) (limited to 'include/linux') diff --git a/include/linux/idr.h b/include/linux/idr.h index 86b38df6e121..7d6a6313f0ab 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -36,7 +36,6 @@ struct idr { .idr_base = (base), \ .idr_next = 0, \ } -#define DEFINE_IDR(name) struct idr name = IDR_INIT /** * IDR_INIT() - Initialise an IDR. @@ -45,6 +44,15 @@ struct idr { */ #define IDR_INIT IDR_INIT_BASE(0) +/** + * DEFINE_IDR() - Define a statically-allocated IDR + * @name: Name of IDR + * + * An IDR defined using this macro is ready for use with no additional + * initialisation required. It contains no IDs. + */ +#define DEFINE_IDR(name) struct idr name = IDR_INIT + /** * idr_get_cursor - Return the current position of the cyclic allocator * @idr: idr handle @@ -130,6 +138,12 @@ static inline void idr_init(struct idr *idr) idr_init_base(idr, 0); } +/** + * idr_is_empty() - Are there any IDs allocated? + * @idr: IDR handle. + * + * Return: %true if any IDs have been allocated from this IDR. + */ static inline bool idr_is_empty(const struct idr *idr) { return radix_tree_empty(&idr->idr_rt) && -- cgit v1.2.3