From 490fd30f859572ac97a51faa31860869744ba97b Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Mon, 17 Dec 2018 17:37:25 -0500 Subject: XArray tests: Add RCU locking 0day picked up that I'd forgotten to add locking to this new test. Signed-off-by: Matthew Wilcox --- lib/test_xarray.c | 2 ++ 1 file changed, 2 insertions(+) (limited to 'lib') diff --git a/lib/test_xarray.c b/lib/test_xarray.c index 4676c0a1eeca..a885afde0aef 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -839,6 +839,7 @@ static noinline void check_find_3(struct xarray *xa) for (i = 0; i < 100; i++) { for (j = 0; j < 100; j++) { + rcu_read_lock(); for (k = 0; k < 100; k++) { xas_set(&xas, j); xas_for_each_marked(&xas, entry, k, XA_MARK_0) @@ -847,6 +848,7 @@ static noinline void check_find_3(struct xarray *xa) XA_BUG_ON(xa, xas.xa_node != XAS_RESTART); } + rcu_read_unlock(); } xa_store_index(xa, i, GFP_KERNEL); xa_set_mark(xa, i, XA_MARK_0); -- cgit v1.2.3 From 02669b17a433c242a40f01f14b691c9c9d1f8a13 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Wed, 5 Dec 2018 16:37:03 -0500 Subject: XArray: Turn xa_init_flags into a static inline A regular xa_init_flags() put all dynamically-initialised XArrays into the same locking class. That leads to lockdep believing that taking one XArray lock while holding another is a deadlock. It's possible to work around some of these situations with separate locking classes for irq/bh/regular XArrays, and SINGLE_DEPTH_NESTING, but that's ugly, and it doesn't work for all situations (where we have completely unrelated XArrays). Signed-off-by: Matthew Wilcox --- include/linux/xarray.h | 19 ++++++++++++++++++- lib/xarray.c | 29 ----------------------------- 2 files changed, 18 insertions(+), 30 deletions(-) (limited to 'lib') diff --git a/include/linux/xarray.h b/include/linux/xarray.h index f492e21c4aa2..4cf3cd128689 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -286,7 +286,6 @@ struct xarray { */ #define DEFINE_XARRAY_ALLOC(name) DEFINE_XARRAY_FLAGS(name, XA_FLAGS_ALLOC) -void xa_init_flags(struct xarray *, gfp_t flags); void *xa_load(struct xarray *, unsigned long index); void *xa_store(struct xarray *, unsigned long index, void *entry, gfp_t); void *xa_erase(struct xarray *, unsigned long index); @@ -303,6 +302,24 @@ unsigned int xa_extract(struct xarray *, void **dst, unsigned long start, unsigned long max, unsigned int n, xa_mark_t); void xa_destroy(struct xarray *); +/** + * xa_init_flags() - Initialise an empty XArray with flags. + * @xa: XArray. + * @flags: XA_FLAG values. + * + * If you need to initialise an XArray with special flags (eg you need + * to take the lock from interrupt context), use this function instead + * of xa_init(). + * + * Context: Any context. + */ +static inline void xa_init_flags(struct xarray *xa, gfp_t flags) +{ + spin_lock_init(&xa->xa_lock); + xa->xa_flags = flags; + xa->xa_head = NULL; +} + /** * xa_init() - Initialise an empty XArray. * @xa: XArray. diff --git a/lib/xarray.c b/lib/xarray.c index 5f3f9311de89..dda6026d202e 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -1250,35 +1250,6 @@ void *xas_find_conflict(struct xa_state *xas) } EXPORT_SYMBOL_GPL(xas_find_conflict); -/** - * xa_init_flags() - Initialise an empty XArray with flags. - * @xa: XArray. - * @flags: XA_FLAG values. - * - * If you need to initialise an XArray with special flags (eg you need - * to take the lock from interrupt context), use this function instead - * of xa_init(). - * - * Context: Any context. - */ -void xa_init_flags(struct xarray *xa, gfp_t flags) -{ - unsigned int lock_type; - static struct lock_class_key xa_lock_irq; - static struct lock_class_key xa_lock_bh; - - spin_lock_init(&xa->xa_lock); - xa->xa_flags = flags; - xa->xa_head = NULL; - - lock_type = xa_lock_type(xa); - if (lock_type == XA_LOCK_IRQ) - lockdep_set_class(&xa->xa_lock, &xa_lock_irq); - else if (lock_type == XA_LOCK_BH) - lockdep_set_class(&xa->xa_lock, &xa_lock_bh); -} -EXPORT_SYMBOL(xa_init_flags); - /** * xa_load() - Load an entry from an XArray. * @xa: XArray. -- cgit v1.2.3 From 4a31896c5b5a2715ecf4033426aa0a35066d92d6 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Mon, 17 Dec 2018 14:45:36 -0500 Subject: XArray: Change xa_for_each iterator There were three problems with this API: 1. It took too many arguments; almost all users wanted to iterate over every element in the array rather than a subset. 2. It required that 'index' be initialised before use, and there's no realistic way to make GCC catch that. 3. 'index' and 'entry' were the opposite way round from every other member of the XArray APIs. So split it into three different APIs: xa_for_each(xa, index, entry) xa_for_each_start(xa, index, entry, start) xa_for_each_marked(xa, index, entry, filter) Signed-off-by: Matthew Wilcox --- include/linux/xarray.h | 78 +++++++++++++++++++++++++++++++++++++++++--------- lib/test_xarray.c | 11 ++++--- 2 files changed, 70 insertions(+), 19 deletions(-) (limited to 'lib') diff --git a/include/linux/xarray.h b/include/linux/xarray.h index 4cf3cd128689..3d0ce8b267e3 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -359,20 +359,45 @@ static inline bool xa_marked(const struct xarray *xa, xa_mark_t mark) } /** - * xa_for_each() - Iterate over a portion of an XArray. + * xa_for_each_start() - Iterate over a portion of an XArray. * @xa: XArray. + * @index: Index of @entry. * @entry: Entry retrieved from array. + * @start: First index to retrieve from array. + * + * During the iteration, @entry will have the value of the entry stored + * in @xa at @index. You may modify @index during the iteration if you + * want to skip or reprocess indices. It is safe to modify the array + * during the iteration. At the end of the iteration, @entry will be set + * to NULL and @index will have a value less than or equal to max. + * + * xa_for_each_start() is O(n.log(n)) while xas_for_each() is O(n). You have + * to handle your own locking with xas_for_each(), and if you have to unlock + * after each iteration, it will also end up being O(n.log(n)). + * xa_for_each_start() will spin if it hits a retry entry; if you intend to + * see retry entries, you should use the xas_for_each() iterator instead. + * The xas_for_each() iterator will expand into more inline code than + * xa_for_each_start(). + * + * Context: Any context. Takes and releases the RCU lock. + */ +#define xa_for_each_start(xa, index, entry, start) \ + for (index = start, \ + entry = xa_find(xa, &index, ULONG_MAX, XA_PRESENT); \ + entry; \ + entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT)) + +/** + * xa_for_each() - Iterate over present entries in an XArray. + * @xa: XArray. * @index: Index of @entry. - * @max: Maximum index to retrieve from array. - * @filter: Selection criterion. + * @entry: Entry retrieved from array. * - * Initialise @index to the lowest index you want to retrieve from the - * array. During the iteration, @entry will have the value of the entry - * stored in @xa at @index. The iteration will skip all entries in the - * array which do not match @filter. You may modify @index during the - * iteration if you want to skip or reprocess indices. It is safe to modify - * the array during the iteration. At the end of the iteration, @entry will - * be set to NULL and @index will have a value less than or equal to max. + * During the iteration, @entry will have the value of the entry stored + * in @xa at @index. You may modify @index during the iteration if you want + * to skip or reprocess indices. It is safe to modify the array during the + * iteration. At the end of the iteration, @entry will be set to NULL and + * @index will have a value less than or equal to max. * * xa_for_each() is O(n.log(n)) while xas_for_each() is O(n). You have * to handle your own locking with xas_for_each(), and if you have to unlock @@ -383,9 +408,36 @@ static inline bool xa_marked(const struct xarray *xa, xa_mark_t mark) * * Context: Any context. Takes and releases the RCU lock. */ -#define xa_for_each(xa, entry, index, max, filter) \ - for (entry = xa_find(xa, &index, max, filter); entry; \ - entry = xa_find_after(xa, &index, max, filter)) +#define xa_for_each(xa, index, entry) \ + xa_for_each_start(xa, index, entry, 0) + +/** + * xa_for_each_marked() - Iterate over marked entries in an XArray. + * @xa: XArray. + * @index: Index of @entry. + * @entry: Entry retrieved from array. + * @filter: Selection criterion. + * + * During the iteration, @entry will have the value of the entry stored + * in @xa at @index. The iteration will skip all entries in the array + * which do not match @filter. You may modify @index during the iteration + * if you want to skip or reprocess indices. It is safe to modify the array + * during the iteration. At the end of the iteration, @entry will be set to + * NULL and @index will have a value less than or equal to max. + * + * xa_for_each_marked() is O(n.log(n)) while xas_for_each_marked() is O(n). + * You have to handle your own locking with xas_for_each(), and if you have + * to unlock after each iteration, it will also end up being O(n.log(n)). + * xa_for_each_marked() will spin if it hits a retry entry; if you intend to + * see retry entries, you should use the xas_for_each_marked() iterator + * instead. The xas_for_each_marked() iterator will expand into more inline + * code than xa_for_each_marked(). + * + * Context: Any context. Takes and releases the RCU lock. + */ +#define xa_for_each_marked(xa, index, entry, filter) \ + for (index = 0, entry = xa_find(xa, &index, ULONG_MAX, filter); \ + entry; entry = xa_find_after(xa, &index, ULONG_MAX, filter)) #define xa_trylock(xa) spin_trylock(&(xa)->xa_lock) #define xa_lock(xa) spin_lock(&(xa)->xa_lock) diff --git a/lib/test_xarray.c b/lib/test_xarray.c index a885afde0aef..dc02eff562b8 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -357,7 +357,7 @@ static noinline void check_cmpxchg(struct xarray *xa) static noinline void check_reserve(struct xarray *xa) { void *entry; - unsigned long index = 0; + unsigned long index; /* An array with a reserved entry is not empty */ XA_BUG_ON(xa, !xa_empty(xa)); @@ -393,7 +393,7 @@ static noinline void check_reserve(struct xarray *xa) xa_reserve(xa, 6, GFP_KERNEL); xa_store_index(xa, 7, GFP_KERNEL); - xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) { + xa_for_each(xa, index, entry) { XA_BUG_ON(xa, index != 5 && index != 7); } xa_destroy(xa); @@ -812,17 +812,16 @@ static noinline void check_find_1(struct xarray *xa) static noinline void check_find_2(struct xarray *xa) { void *entry; - unsigned long i, j, index = 0; + unsigned long i, j, index; - xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) { + xa_for_each(xa, index, entry) { XA_BUG_ON(xa, true); } for (i = 0; i < 1024; i++) { xa_store_index(xa, index, GFP_KERNEL); j = 0; - index = 0; - xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) { + xa_for_each(xa, index, entry) { XA_BUG_ON(xa, xa_mk_index(index) != entry); XA_BUG_ON(xa, index != j++); } -- cgit v1.2.3 From 76b4e52995654af260f14558e0e07b5b039ae202 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Fri, 28 Dec 2018 23:20:44 -0500 Subject: XArray: Permit storing 2-byte-aligned pointers On m68k, statically allocated pointers may only be two-byte aligned. This clashes with the XArray's method for tagging internal pointers. Permit storing these pointers in single slots (ie not in multislots). Signed-off-by: Matthew Wilcox --- include/linux/xarray.h | 18 +++++++++++++++--- lib/test_xarray.c | 30 ++++++++++++++++++++++++++++++ lib/xarray.c | 22 +++++++++++++--------- 3 files changed, 58 insertions(+), 12 deletions(-) (limited to 'lib') diff --git a/include/linux/xarray.h b/include/linux/xarray.h index 3d0ce8b267e3..435c25b29079 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -176,7 +176,8 @@ static inline bool xa_is_internal(const void *entry) */ static inline bool xa_is_err(const void *entry) { - return unlikely(xa_is_internal(entry)); + return unlikely(xa_is_internal(entry) && + (unsigned long)entry >= -((MAX_ERRNO << 2) + 2)); } /** @@ -1039,8 +1040,8 @@ static inline bool xa_is_sibling(const void *entry) (entry < xa_mk_sibling(XA_CHUNK_SIZE - 1)); } -#define XA_ZERO_ENTRY xa_mk_internal(256) -#define XA_RETRY_ENTRY xa_mk_internal(257) +#define XA_RETRY_ENTRY xa_mk_internal(256) +#define XA_ZERO_ENTRY xa_mk_internal(257) /** * xa_is_zero() - Is the entry a zero entry? @@ -1064,6 +1065,17 @@ static inline bool xa_is_retry(const void *entry) return unlikely(entry == XA_RETRY_ENTRY); } +/** + * xa_is_advanced() - Is the entry only permitted for the advanced API? + * @entry: Entry to be stored in the XArray. + * + * Return: %true if the entry cannot be stored by the normal API. + */ +static inline bool xa_is_advanced(const void *entry) +{ + return xa_is_internal(entry) && (entry <= XA_RETRY_ENTRY); +} + /** * typedef xa_update_node_t - A callback function from the XArray. * @node: The node which is being processed diff --git a/lib/test_xarray.c b/lib/test_xarray.c index dc02eff562b8..6e0212a60b08 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -1184,6 +1184,35 @@ static noinline void check_store_range(struct xarray *xa) } } +static void check_align_1(struct xarray *xa, char *name) +{ + int i; + unsigned int id; + unsigned long index; + void *entry; + + for (i = 0; i < 8; i++) { + id = 0; + XA_BUG_ON(xa, xa_alloc(xa, &id, UINT_MAX, name + i, GFP_KERNEL) + != 0); + XA_BUG_ON(xa, id != i); + } + xa_for_each(xa, index, entry) + XA_BUG_ON(xa, xa_is_err(entry)); + xa_destroy(xa); +} + +static noinline void check_align(struct xarray *xa) +{ + char name[] = "Motorola 68000"; + + check_align_1(xa, name); + check_align_1(xa, name + 1); + check_align_1(xa, name + 2); + check_align_1(xa, name + 3); +// check_align_2(xa, name); +} + static LIST_HEAD(shadow_nodes); static void test_update_node(struct xa_node *node) @@ -1333,6 +1362,7 @@ static int xarray_checks(void) check_create_range(&array); check_store_range(&array); check_store_iter(&array); + check_align(&xa0); check_workingset(&array, 0); check_workingset(&array, 64); diff --git a/lib/xarray.c b/lib/xarray.c index dda6026d202e..bffa26b1f0d6 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -232,6 +232,8 @@ void *xas_load(struct xa_state *xas) if (xas->xa_shift > node->shift) break; entry = xas_descend(xas, node); + if (node->shift == 0) + break; } return entry; } @@ -506,7 +508,7 @@ static void xas_free_nodes(struct xa_state *xas, struct xa_node *top) for (;;) { void *entry = xa_entry_locked(xas->xa, node, offset); - if (xa_is_node(entry)) { + if (node->shift && xa_is_node(entry)) { node = xa_to_node(entry); offset = 0; continue; @@ -604,6 +606,7 @@ static int xas_expand(struct xa_state *xas, void *head) /* * xas_create() - Create a slot to store an entry in. * @xas: XArray operation state. + * @allow_root: %true if we can store the entry in the root directly * * Most users will not need to call this function directly, as it is called * by xas_store(). It is useful for doing conditional store operations @@ -613,7 +616,7 @@ static int xas_expand(struct xa_state *xas, void *head) * If the slot was newly created, returns %NULL. If it failed to create the * slot, returns %NULL and indicates the error in @xas. */ -static void *xas_create(struct xa_state *xas) +static void *xas_create(struct xa_state *xas, bool allow_root) { struct xarray *xa = xas->xa; void *entry; @@ -628,6 +631,8 @@ static void *xas_create(struct xa_state *xas) shift = xas_expand(xas, entry); if (shift < 0) return NULL; + if (!shift && !allow_root) + shift = XA_CHUNK_SHIFT; entry = xa_head_locked(xa); slot = &xa->xa_head; } else if (xas_error(xas)) { @@ -687,7 +692,7 @@ void xas_create_range(struct xa_state *xas) xas->xa_sibs = 0; for (;;) { - xas_create(xas); + xas_create(xas, true); if (xas_error(xas)) goto restore; if (xas->xa_index <= (index | XA_CHUNK_MASK)) @@ -754,7 +759,7 @@ void *xas_store(struct xa_state *xas, void *entry) bool value = xa_is_value(entry); if (entry) - first = xas_create(xas); + first = xas_create(xas, !xa_is_node(entry)); else first = xas_load(xas); @@ -1279,7 +1284,6 @@ static void *xas_result(struct xa_state *xas, void *curr) { if (xa_is_zero(curr)) return NULL; - XA_NODE_BUG_ON(xas->xa_node, xa_is_internal(curr)); if (xas_error(xas)) curr = xas->xa_node; return curr; @@ -1349,7 +1353,7 @@ void *__xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp) XA_STATE(xas, xa, index); void *curr; - if (WARN_ON_ONCE(xa_is_internal(entry))) + if (WARN_ON_ONCE(xa_is_advanced(entry))) return XA_ERROR(-EINVAL); if (xa_track_free(xa) && !entry) entry = XA_ZERO_ENTRY; @@ -1415,7 +1419,7 @@ void *__xa_cmpxchg(struct xarray *xa, unsigned long index, XA_STATE(xas, xa, index); void *curr; - if (WARN_ON_ONCE(xa_is_internal(entry))) + if (WARN_ON_ONCE(xa_is_advanced(entry))) return XA_ERROR(-EINVAL); if (xa_track_free(xa) && !entry) entry = XA_ZERO_ENTRY; @@ -1538,7 +1542,7 @@ void *xa_store_range(struct xarray *xa, unsigned long first, if (last + 1) order = __ffs(last + 1); xas_set_order(&xas, last, order); - xas_create(&xas); + xas_create(&xas, true); if (xas_error(&xas)) goto unlock; } @@ -1580,7 +1584,7 @@ int __xa_alloc(struct xarray *xa, u32 *id, u32 max, void *entry, gfp_t gfp) XA_STATE(xas, xa, 0); int err; - if (WARN_ON_ONCE(xa_is_internal(entry))) + if (WARN_ON_ONCE(xa_is_advanced(entry))) return -EINVAL; if (WARN_ON_ONCE(!xa_track_free(xa))) return -EINVAL; -- cgit v1.2.3 From b0606fed6eece16a421034eca0bbea9a08b90e91 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Wed, 2 Jan 2019 13:57:03 -0500 Subject: XArray: Honour reserved entries in xa_insert xa_insert() should treat reserved entries as occupied, not as available. Also, it should treat requests to insert a NULL pointer as a request to reserve the slot. Add xa_insert_bh() and xa_insert_irq() for completeness. Signed-off-by: Matthew Wilcox --- Documentation/core-api/xarray.rst | 15 +++--- include/linux/xarray.h | 110 ++++++++++++++++++++++++-------------- lib/test_xarray.c | 8 +-- lib/xarray.c | 41 ++++++++++++++ 4 files changed, 126 insertions(+), 48 deletions(-) (limited to 'lib') diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst index 6a6d67acaf69..5d54b27c6eba 100644 --- a/Documentation/core-api/xarray.rst +++ b/Documentation/core-api/xarray.rst @@ -108,12 +108,13 @@ some, but not all of the other indices changing. Sometimes you need to ensure that a subsequent call to :c:func:`xa_store` will not need to allocate memory. The :c:func:`xa_reserve` function -will store a reserved entry at the indicated index. Users of the normal -API will see this entry as containing ``NULL``. If you do not need to -use the reserved entry, you can call :c:func:`xa_release` to remove the -unused entry. If another user has stored to the entry in the meantime, -:c:func:`xa_release` will do nothing; if instead you want the entry to -become ``NULL``, you should use :c:func:`xa_erase`. +will store a reserved entry at the indicated index. Users of the +normal API will see this entry as containing ``NULL``. If you do +not need to use the reserved entry, you can call :c:func:`xa_release` +to remove the unused entry. If another user has stored to the entry +in the meantime, :c:func:`xa_release` will do nothing; if instead you +want the entry to become ``NULL``, you should use :c:func:`xa_erase`. +Using :c:func:`xa_insert` on a reserved entry will fail. If all entries in the array are ``NULL``, the :c:func:`xa_empty` function will return ``true``. @@ -183,6 +184,8 @@ Takes xa_lock internally: * :c:func:`xa_store_bh` * :c:func:`xa_store_irq` * :c:func:`xa_insert` + * :c:func:`xa_insert_bh` + * :c:func:`xa_insert_irq` * :c:func:`xa_erase` * :c:func:`xa_erase_bh` * :c:func:`xa_erase_irq` diff --git a/include/linux/xarray.h b/include/linux/xarray.h index 435c25b29079..12244aa98a69 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -463,39 +463,12 @@ void *__xa_erase(struct xarray *, unsigned long index); void *__xa_store(struct xarray *, unsigned long index, void *entry, gfp_t); void *__xa_cmpxchg(struct xarray *, unsigned long index, void *old, void *entry, gfp_t); +int __xa_insert(struct xarray *, unsigned long index, void *entry, gfp_t); int __xa_alloc(struct xarray *, u32 *id, u32 max, void *entry, gfp_t); int __xa_reserve(struct xarray *, unsigned long index, gfp_t); void __xa_set_mark(struct xarray *, unsigned long index, xa_mark_t); void __xa_clear_mark(struct xarray *, unsigned long index, xa_mark_t); -/** - * __xa_insert() - Store this entry in the XArray unless another entry is - * already present. - * @xa: XArray. - * @index: Index into array. - * @entry: New entry. - * @gfp: Memory allocation flags. - * - * If you would rather see the existing entry in the array, use __xa_cmpxchg(). - * This function is for users who don't care what the entry is, only that - * one is present. - * - * Context: Any context. Expects xa_lock to be held on entry. May - * release and reacquire xa_lock if the @gfp flags permit. - * Return: 0 if the store succeeded. -EEXIST if another entry was present. - * -ENOMEM if memory could not be allocated. - */ -static inline int __xa_insert(struct xarray *xa, unsigned long index, - void *entry, gfp_t gfp) -{ - void *curr = __xa_cmpxchg(xa, index, NULL, entry, gfp); - if (!curr) - return 0; - if (xa_is_err(curr)) - return xa_err(curr); - return -EEXIST; -} - /** * xa_store_bh() - Store this entry in the XArray. * @xa: XArray. @@ -685,24 +658,83 @@ static inline void *xa_cmpxchg_irq(struct xarray *xa, unsigned long index, * @entry: New entry. * @gfp: Memory allocation flags. * - * If you would rather see the existing entry in the array, use xa_cmpxchg(). - * This function is for users who don't care what the entry is, only that - * one is present. + * Inserting a NULL entry will store a reserved entry (like xa_reserve()) + * if no entry is present. Inserting will fail if a reserved entry is + * present, even though loading from this index will return NULL. * - * Context: Process context. Takes and releases the xa_lock. - * May sleep if the @gfp flags permit. + * Context: Any context. Takes and releases the xa_lock. May sleep if + * the @gfp flags permit. * Return: 0 if the store succeeded. -EEXIST if another entry was present. * -ENOMEM if memory could not be allocated. */ static inline int xa_insert(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp) { - void *curr = xa_cmpxchg(xa, index, NULL, entry, gfp); - if (!curr) - return 0; - if (xa_is_err(curr)) - return xa_err(curr); - return -EEXIST; + int err; + + xa_lock(xa); + err = __xa_insert(xa, index, entry, gfp); + xa_unlock(xa); + + return err; +} + +/** + * xa_insert_bh() - Store this entry in the XArray unless another entry is + * already present. + * @xa: XArray. + * @index: Index into array. + * @entry: New entry. + * @gfp: Memory allocation flags. + * + * Inserting a NULL entry will store a reserved entry (like xa_reserve()) + * if no entry is present. Inserting will fail if a reserved entry is + * present, even though loading from this index will return NULL. + * + * Context: Any context. Takes and releases the xa_lock while + * disabling softirqs. May sleep if the @gfp flags permit. + * Return: 0 if the store succeeded. -EEXIST if another entry was present. + * -ENOMEM if memory could not be allocated. + */ +static inline int xa_insert_bh(struct xarray *xa, unsigned long index, + void *entry, gfp_t gfp) +{ + int err; + + xa_lock_bh(xa); + err = __xa_insert(xa, index, entry, gfp); + xa_unlock_bh(xa); + + return err; +} + +/** + * xa_insert_irq() - Store this entry in the XArray unless another entry is + * already present. + * @xa: XArray. + * @index: Index into array. + * @entry: New entry. + * @gfp: Memory allocation flags. + * + * Inserting a NULL entry will store a reserved entry (like xa_reserve()) + * if no entry is present. Inserting will fail if a reserved entry is + * present, even though loading from this index will return NULL. + * + * Context: Process context. Takes and releases the xa_lock while + * disabling interrupts. May sleep if the @gfp flags permit. + * Return: 0 if the store succeeded. -EEXIST if another entry was present. + * -ENOMEM if memory could not be allocated. + */ +static inline int xa_insert_irq(struct xarray *xa, unsigned long index, + void *entry, gfp_t gfp) +{ + int err; + + xa_lock_irq(xa); + err = __xa_insert(xa, index, entry, gfp); + xa_unlock_irq(xa); + + return err; } /** diff --git a/lib/test_xarray.c b/lib/test_xarray.c index 6e0212a60b08..3cf17338b0a4 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -382,10 +382,12 @@ static noinline void check_reserve(struct xarray *xa) xa_erase_index(xa, 12345678); XA_BUG_ON(xa, !xa_empty(xa)); - /* And so does xa_insert */ + /* But xa_insert does not */ xa_reserve(xa, 12345678, GFP_KERNEL); - XA_BUG_ON(xa, xa_insert(xa, 12345678, xa_mk_value(12345678), 0) != 0); - xa_erase_index(xa, 12345678); + XA_BUG_ON(xa, xa_insert(xa, 12345678, xa_mk_value(12345678), 0) != + -EEXIST); + XA_BUG_ON(xa, xa_empty(xa)); + XA_BUG_ON(xa, xa_erase(xa, 12345678) != NULL); XA_BUG_ON(xa, !xa_empty(xa)); /* Can iterate through a reserved entry */ diff --git a/lib/xarray.c b/lib/xarray.c index bffa26b1f0d6..81c3171ddde9 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -1439,6 +1439,47 @@ void *__xa_cmpxchg(struct xarray *xa, unsigned long index, } EXPORT_SYMBOL(__xa_cmpxchg); +/** + * __xa_insert() - Store this entry in the XArray if no entry is present. + * @xa: XArray. + * @index: Index into array. + * @entry: New entry. + * @gfp: Memory allocation flags. + * + * Inserting a NULL entry will store a reserved entry (like xa_reserve()) + * if no entry is present. Inserting will fail if a reserved entry is + * present, even though loading from this index will return NULL. + * + * Context: Any context. Expects xa_lock to be held on entry. May + * release and reacquire xa_lock if @gfp flags permit. + * Return: 0 if the store succeeded. -EEXIST if another entry was present. + * -ENOMEM if memory could not be allocated. + */ +int __xa_insert(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp) +{ + XA_STATE(xas, xa, index); + void *curr; + + if (WARN_ON_ONCE(xa_is_advanced(entry))) + return -EINVAL; + if (!entry) + entry = XA_ZERO_ENTRY; + + do { + curr = xas_load(&xas); + if (!curr) { + xas_store(&xas, entry); + if (xa_track_free(xa)) + xas_clear_mark(&xas, XA_FREE_MARK); + } else { + xas_set_err(&xas, -EEXIST); + } + } while (__xas_nomem(&xas, gfp)); + + return xas_error(&xas); +} +EXPORT_SYMBOL(__xa_insert); + /** * __xa_reserve() - Reserve this index in the XArray. * @xa: XArray. -- cgit v1.2.3 From 3719876809e745b9db5293d418600c194bbf5c23 Mon Sep 17 00:00:00 2001 From: "Steven Rostedt (VMware)" Date: Mon, 14 Jan 2019 12:25:40 -0500 Subject: sbitmap: Protect swap_lock from softirqs The swap_lock used by sbitmap has a chain with locks taken from softirq, but the swap_lock is not protected from being preempted by softirqs. A chain exists of: sbq->ws[i].wait -> dispatch_wait_lock -> swap_lock Where the sbq->ws[i].wait lock can be taken from softirq context, which means all locks below it in the chain must also be protected from softirqs. Reported-by: Clark Williams Fixes: 58ab5e32e6fd ("sbitmap: silence bogus lockdep IRQ warning") Fixes: ea86ea2cdced ("sbitmap: amortize cost of clearing bits") Cc: Jens Axboe Cc: Ming Lei Cc: Guenter Roeck Signed-off-by: Steven Rostedt (VMware) Signed-off-by: Linus Torvalds --- lib/sbitmap.c | 12 ++---------- 1 file changed, 2 insertions(+), 10 deletions(-) (limited to 'lib') diff --git a/lib/sbitmap.c b/lib/sbitmap.c index 65c2d06250a6..864354000e04 100644 --- a/lib/sbitmap.c +++ b/lib/sbitmap.c @@ -26,14 +26,9 @@ static inline bool sbitmap_deferred_clear(struct sbitmap *sb, int index) { unsigned long mask, val; - unsigned long __maybe_unused flags; bool ret = false; - /* Silence bogus lockdep warning */ -#if defined(CONFIG_LOCKDEP) - local_irq_save(flags); -#endif - spin_lock(&sb->map[index].swap_lock); + spin_lock_bh(&sb->map[index].swap_lock); if (!sb->map[index].cleared) goto out_unlock; @@ -54,10 +49,7 @@ static inline bool sbitmap_deferred_clear(struct sbitmap *sb, int index) ret = true; out_unlock: - spin_unlock(&sb->map[index].swap_lock); -#if defined(CONFIG_LOCKDEP) - local_irq_restore(flags); -#endif + spin_unlock_bh(&sb->map[index].swap_lock); return ret; } -- cgit v1.2.3 From d69d287a9002b70bdbe2975660b97241ccefc071 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Mon, 14 Jan 2019 13:57:31 -0500 Subject: XArray tests: Check mark 2 gets squashed We do not currently check that the loop in xas_squash_marks() doesn't have an off-by-one error in it. It didn't, but a patch which introduced an off-by-one error wasn't caught by any existing test. Switch the roles of XA_MARK_1 and XA_MARK_2 to catch that bug. Reported-by: Cyrill Gorcunov Signed-off-by: Matthew Wilcox --- lib/test_xarray.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/test_xarray.c b/lib/test_xarray.c index 3cf17338b0a4..c596a957f764 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -199,7 +199,7 @@ static noinline void check_xa_mark_1(struct xarray *xa, unsigned long index) XA_BUG_ON(xa, xa_store_index(xa, index + 1, GFP_KERNEL)); xa_set_mark(xa, index + 1, XA_MARK_0); XA_BUG_ON(xa, xa_store_index(xa, index + 2, GFP_KERNEL)); - xa_set_mark(xa, index + 2, XA_MARK_1); + xa_set_mark(xa, index + 2, XA_MARK_2); XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL)); xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL); @@ -209,8 +209,8 @@ static noinline void check_xa_mark_1(struct xarray *xa, unsigned long index) void *entry; XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0)); - XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_1)); - XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_2)); + XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_1)); + XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_2)); /* We should see two elements in the array */ rcu_read_lock(); -- cgit v1.2.3 From fe76fc6aaf538df27708ffa3e5d549a6c8e16142 Mon Sep 17 00:00:00 2001 From: Ming Lei Date: Tue, 15 Jan 2019 11:59:52 +0800 Subject: sbitmap: Protect swap_lock from hardirq Because we may call blk_mq_get_driver_tag() directly from blk_mq_dispatch_rq_list() without holding any lock, then HARDIRQ may come and the above DEADLOCK is triggered. Commit ab53dcfb3e7b ("sbitmap: Protect swap_lock from hardirq") tries to fix this issue by using 'spin_lock_bh', which isn't enough because we complete request from hardirq context direclty in case of multiqueue. Cc: Clark Williams Fixes: ab53dcfb3e7b ("sbitmap: Protect swap_lock from hardirq") Cc: Jens Axboe Cc: Ming Lei Cc: Guenter Roeck Cc: Steven Rostedt (VMware) Signed-off-by: Ming Lei Signed-off-by: Linus Torvalds --- lib/sbitmap.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/sbitmap.c b/lib/sbitmap.c index 864354000e04..5b382c1244ed 100644 --- a/lib/sbitmap.c +++ b/lib/sbitmap.c @@ -27,8 +27,9 @@ static inline bool sbitmap_deferred_clear(struct sbitmap *sb, int index) { unsigned long mask, val; bool ret = false; + unsigned long flags; - spin_lock_bh(&sb->map[index].swap_lock); + spin_lock_irqsave(&sb->map[index].swap_lock, flags); if (!sb->map[index].cleared) goto out_unlock; @@ -49,7 +50,7 @@ static inline bool sbitmap_deferred_clear(struct sbitmap *sb, int index) ret = true; out_unlock: - spin_unlock_bh(&sb->map[index].swap_lock); + spin_unlock_irqrestore(&sb->map[index].swap_lock, flags); return ret; } -- cgit v1.2.3 From fbfaf851902cd9293f392f3a1735e0543016d530 Mon Sep 17 00:00:00 2001 From: Florian La Roche Date: Sat, 19 Jan 2019 16:14:50 +0100 Subject: fix int_sqrt64() for very large numbers If an input number x for int_sqrt64() has the highest bit set, then fls64(x) is 64. (1UL << 64) is an overflow and breaks the algorithm. Subtracting 1 is a better guess for the initial value of m anyway and that's what also done in int_sqrt() implicitly [*]. [*] Note how int_sqrt() uses __fls() with two underscores, which already returns the proper raw bit number. In contrast, int_sqrt64() used fls64(), and that returns bit numbers illogically starting at 1, because of error handling for the "no bits set" case. Will points out that he bug probably is due to a copy-and-paste error from the regular int_sqrt() case. Signed-off-by: Florian La Roche Acked-by: Will Deacon Signed-off-by: Linus Torvalds --- lib/int_sqrt.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c index 14436f4ca6bd..30e0f9770f88 100644 --- a/lib/int_sqrt.c +++ b/lib/int_sqrt.c @@ -52,7 +52,7 @@ u32 int_sqrt64(u64 x) if (x <= ULONG_MAX) return int_sqrt((unsigned long) x); - m = 1ULL << (fls64(x) & ~1ULL); + m = 1ULL << ((fls64(x) - 1) & ~1ULL); while (m != 0) { b = y + m; y >>= 1; -- cgit v1.2.3 From fc42a689c4c097859e5bd37b5ea11b60dc426df6 Mon Sep 17 00:00:00 2001 From: Bart Van Assche Date: Wed, 30 Jan 2019 10:42:30 -0800 Subject: lib/test_rhashtable: Make test_insert_dup() allocate its hash table dynamically The test_insert_dup() function from lib/test_rhashtable.c passes a pointer to a stack object to rhltable_init(). Allocate the hash table dynamically to avoid that the following is reported with object debugging enabled: ODEBUG: object (ptrval) is on stack (ptrval), but NOT annotated. WARNING: CPU: 0 PID: 1 at lib/debugobjects.c:368 __debug_object_init+0x312/0x480 Modules linked in: EIP: __debug_object_init+0x312/0x480 Call Trace: ? debug_object_init+0x1a/0x20 ? __init_work+0x16/0x30 ? rhashtable_init+0x1e1/0x460 ? sched_clock_cpu+0x57/0xe0 ? rhltable_init+0xb/0x20 ? test_insert_dup+0x32/0x20f ? trace_hardirqs_on+0x38/0xf0 ? ida_dump+0x10/0x10 ? jhash+0x130/0x130 ? my_hashfn+0x30/0x30 ? test_rht_init+0x6aa/0xab4 ? ida_dump+0x10/0x10 ? test_rhltable+0xc5c/0xc5c ? do_one_initcall+0x67/0x28e ? trace_hardirqs_off+0x22/0xe0 ? restore_all_kernel+0xf/0x70 ? trace_hardirqs_on_thunk+0xc/0x10 ? restore_all_kernel+0xf/0x70 ? kernel_init_freeable+0x142/0x213 ? rest_init+0x230/0x230 ? kernel_init+0x10/0x110 ? schedule_tail_wrapper+0x9/0xc ? ret_from_fork+0x19/0x24 Cc: Thomas Graf Cc: Herbert Xu Cc: netdev@vger.kernel.org Cc: linux-kernel@vger.kernel.org Signed-off-by: Bart Van Assche Acked-by: Herbert Xu Signed-off-by: David S. Miller --- lib/test_rhashtable.c | 23 +++++++++++++++-------- 1 file changed, 15 insertions(+), 8 deletions(-) (limited to 'lib') diff --git a/lib/test_rhashtable.c b/lib/test_rhashtable.c index 6a8ac7626797..e52f8cafe227 100644 --- a/lib/test_rhashtable.c +++ b/lib/test_rhashtable.c @@ -541,38 +541,45 @@ static unsigned int __init print_ht(struct rhltable *rhlt) static int __init test_insert_dup(struct test_obj_rhl *rhl_test_objects, int cnt, bool slow) { - struct rhltable rhlt; + struct rhltable *rhlt; unsigned int i, ret; const char *key; int err = 0; - err = rhltable_init(&rhlt, &test_rht_params_dup); - if (WARN_ON(err)) + rhlt = kmalloc(sizeof(*rhlt), GFP_KERNEL); + if (WARN_ON(!rhlt)) + return -EINVAL; + + err = rhltable_init(rhlt, &test_rht_params_dup); + if (WARN_ON(err)) { + kfree(rhlt); return err; + } for (i = 0; i < cnt; i++) { rhl_test_objects[i].value.tid = i; - key = rht_obj(&rhlt.ht, &rhl_test_objects[i].list_node.rhead); + key = rht_obj(&rhlt->ht, &rhl_test_objects[i].list_node.rhead); key += test_rht_params_dup.key_offset; if (slow) { - err = PTR_ERR(rhashtable_insert_slow(&rhlt.ht, key, + err = PTR_ERR(rhashtable_insert_slow(&rhlt->ht, key, &rhl_test_objects[i].list_node.rhead)); if (err == -EAGAIN) err = 0; } else - err = rhltable_insert(&rhlt, + err = rhltable_insert(rhlt, &rhl_test_objects[i].list_node, test_rht_params_dup); if (WARN(err, "error %d on element %d/%d (%s)\n", err, i, cnt, slow? "slow" : "fast")) goto skip_print; } - ret = print_ht(&rhlt); + ret = print_ht(rhlt); WARN(ret != cnt, "missing rhltable elements (%d != %d, %s)\n", ret, cnt, slow? "slow" : "fast"); skip_print: - rhltable_destroy(&rhlt); + rhltable_destroy(rhlt); + kfree(rhlt); return 0; } -- cgit v1.2.3 From db7ddeab3ce5d64c9696e70d61f45ea9909cd196 Mon Sep 17 00:00:00 2001 From: Dan Carpenter Date: Fri, 1 Feb 2019 14:20:58 -0800 Subject: lib/test_kmod.c: potential double free in error handling There is a copy and paste bug so we set "config->test_driver" to NULL twice instead of setting "config->test_fs". Smatch complains that it leads to a double free: lib/test_kmod.c:840 __kmod_config_init() warn: 'config->test_fs' double freed Link: http://lkml.kernel.org/r/20190121140011.GA14283@kadam Fixes: d9c6a72d6fa2 ("kmod: add test driver to stress test the module loader") Signed-off-by: Dan Carpenter Acked-by: Luis Chamberlain Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/test_kmod.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/test_kmod.c b/lib/test_kmod.c index d82d022111e0..9cf77628fc91 100644 --- a/lib/test_kmod.c +++ b/lib/test_kmod.c @@ -632,7 +632,7 @@ static void __kmod_config_free(struct test_config *config) config->test_driver = NULL; kfree_const(config->test_fs); - config->test_driver = NULL; + config->test_fs = NULL; } static void kmod_config_free(struct kmod_test_device *test_dev) -- cgit v1.2.3