From 8229706e03e4147f3e22d1de0d30630cde6d18a9 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Thu, 1 Nov 2018 16:55:19 -0400 Subject: XArray: Fix xa_for_each with a single element at 0 The following sequence of calls would result in an infinite loop in xa_find_after(): xa_store(xa, 0, x, GFP_KERNEL); index = 0; xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) { } xa_find_after() was confusing the situation where we found no entry in the tree with finding a multiorder entry, so it would look for the successor entry forever. Just check for this case explicitly. Includes a few new checks in the test suite to be sure this doesn't reappear. Signed-off-by: Matthew Wilcox --- lib/test_xarray.c | 30 +++++++++++++++++++++++++++++- 1 file changed, 29 insertions(+), 1 deletion(-) (limited to 'lib/test_xarray.c') diff --git a/lib/test_xarray.c b/lib/test_xarray.c index aa47754150ce..126127658b49 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -702,7 +702,7 @@ static noinline void check_multi_find_2(struct xarray *xa) } } -static noinline void check_find(struct xarray *xa) +static noinline void check_find_1(struct xarray *xa) { unsigned long i, j, k; @@ -748,6 +748,34 @@ static noinline void check_find(struct xarray *xa) XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_0)); } XA_BUG_ON(xa, !xa_empty(xa)); +} + +static noinline void check_find_2(struct xarray *xa) +{ + void *entry; + unsigned long i, j, index = 0; + + xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) { + 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_BUG_ON(xa, xa_mk_value(index) != entry); + XA_BUG_ON(xa, index != j++); + } + } + + xa_destroy(xa); +} + +static noinline void check_find(struct xarray *xa) +{ + check_find_1(xa); + check_find_2(xa); check_multi_find(xa); check_multi_find_2(xa); } -- cgit From 4c0608f4a0e76dfb82d3accd20081f4bf47ed143 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Tue, 30 Oct 2018 09:45:55 -0400 Subject: XArray: Regularise xa_reserve The xa_reserve() function was a little unusual in that it attempted to be callable for all kinds of locking scenarios. Make it look like the other APIs with __xa_reserve, xa_reserve_bh and xa_reserve_irq variants. Signed-off-by: Matthew Wilcox --- Documentation/core-api/xarray.rst | 13 +++++++ include/linux/xarray.h | 80 ++++++++++++++++++++++++++++++++++++++- lib/test_xarray.c | 6 +++ lib/xarray.c | 18 ++++----- 4 files changed, 105 insertions(+), 12 deletions(-) (limited to 'lib/test_xarray.c') diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst index a4e705108f42..65c77a81b689 100644 --- a/Documentation/core-api/xarray.rst +++ b/Documentation/core-api/xarray.rst @@ -105,6 +105,15 @@ may result in the entry being marked at some, but not all of the other indices. Storing into one index may result in the entry retrieved by 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`. + Finally, you can remove all entries from an XArray by calling :c:func:`xa_destroy`. If the XArray entries are pointers, you may wish to free the entries first. You can do this by iterating over all present @@ -167,6 +176,9 @@ Takes xa_lock internally: * :c:func:`xa_alloc` * :c:func:`xa_alloc_bh` * :c:func:`xa_alloc_irq` + * :c:func:`xa_reserve` + * :c:func:`xa_reserve_bh` + * :c:func:`xa_reserve_irq` * :c:func:`xa_destroy` * :c:func:`xa_set_mark` * :c:func:`xa_clear_mark` @@ -177,6 +189,7 @@ Assumes xa_lock held on entry: * :c:func:`__xa_erase` * :c:func:`__xa_cmpxchg` * :c:func:`__xa_alloc` + * :c:func:`__xa_reserve` * :c:func:`__xa_set_mark` * :c:func:`__xa_clear_mark` diff --git a/include/linux/xarray.h b/include/linux/xarray.h index d9514928ddac..c2cb0426c60c 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -291,7 +291,6 @@ void *xa_load(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_reserve(struct xarray *, unsigned long index, gfp_t); void *xa_store_range(struct xarray *, unsigned long first, unsigned long last, void *entry, gfp_t); bool xa_get_mark(struct xarray *, unsigned long index, xa_mark_t); @@ -455,6 +454,7 @@ 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_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); @@ -621,6 +621,84 @@ static inline int xa_alloc_irq(struct xarray *xa, u32 *id, u32 max, void *entry, return err; } +/** + * xa_reserve() - Reserve this index in the XArray. + * @xa: XArray. + * @index: Index into array. + * @gfp: Memory allocation flags. + * + * Ensures there is somewhere to store an entry at @index in the array. + * If there is already something stored at @index, this function does + * nothing. If there was nothing there, the entry is marked as reserved. + * Loading from a reserved entry returns a %NULL pointer. + * + * If you do not use the entry that you have reserved, call xa_release() + * or xa_erase() to free any unnecessary memory. + * + * Context: Any context. Takes and releases the xa_lock. + * May sleep if the @gfp flags permit. + * Return: 0 if the reservation succeeded or -ENOMEM if it failed. + */ +static inline +int xa_reserve(struct xarray *xa, unsigned long index, gfp_t gfp) +{ + int ret; + + xa_lock(xa); + ret = __xa_reserve(xa, index, gfp); + xa_unlock(xa); + + return ret; +} + +/** + * xa_reserve_bh() - Reserve this index in the XArray. + * @xa: XArray. + * @index: Index into array. + * @gfp: Memory allocation flags. + * + * A softirq-disabling version of xa_reserve(). + * + * Context: Any context. Takes and releases the xa_lock while + * disabling softirqs. + * Return: 0 if the reservation succeeded or -ENOMEM if it failed. + */ +static inline +int xa_reserve_bh(struct xarray *xa, unsigned long index, gfp_t gfp) +{ + int ret; + + xa_lock_bh(xa); + ret = __xa_reserve(xa, index, gfp); + xa_unlock_bh(xa); + + return ret; +} + +/** + * xa_reserve_irq() - Reserve this index in the XArray. + * @xa: XArray. + * @index: Index into array. + * @gfp: Memory allocation flags. + * + * An interrupt-disabling version of xa_reserve(). + * + * Context: Process context. Takes and releases the xa_lock while + * disabling interrupts. + * Return: 0 if the reservation succeeded or -ENOMEM if it failed. + */ +static inline +int xa_reserve_irq(struct xarray *xa, unsigned long index, gfp_t gfp) +{ + int ret; + + xa_lock_irq(xa); + ret = __xa_reserve(xa, index, gfp); + xa_unlock_irq(xa); + + return ret; +} + /* Everything below here is the Advanced API. Proceed with caution. */ /* diff --git a/lib/test_xarray.c b/lib/test_xarray.c index 126127658b49..e5294b20b52f 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -373,6 +373,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 */ + 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_empty(xa)); + /* Can iterate through a reserved entry */ xa_store_index(xa, 5, GFP_KERNEL); xa_reserve(xa, 6, GFP_KERNEL); diff --git a/lib/xarray.c b/lib/xarray.c index e7be4e47c6a9..9cab8cfef8a8 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -1488,7 +1488,7 @@ void *__xa_cmpxchg(struct xarray *xa, unsigned long index, EXPORT_SYMBOL(__xa_cmpxchg); /** - * xa_reserve() - Reserve this index in the XArray. + * __xa_reserve() - Reserve this index in the XArray. * @xa: XArray. * @index: Index into array. * @gfp: Memory allocation flags. @@ -1496,33 +1496,29 @@ EXPORT_SYMBOL(__xa_cmpxchg); * Ensures there is somewhere to store an entry at @index in the array. * If there is already something stored at @index, this function does * nothing. If there was nothing there, the entry is marked as reserved. - * Loads from @index will continue to see a %NULL pointer until a - * subsequent store to @index. + * Loading from a reserved entry returns a %NULL pointer. * * If you do not use the entry that you have reserved, call xa_release() * or xa_erase() to free any unnecessary memory. * - * Context: Process context. Takes and releases the xa_lock, IRQ or BH safe - * if specified in XArray flags. May sleep if the @gfp flags permit. + * Context: Any context. Expects the xa_lock to be held on entry. May + * release the lock, sleep and reacquire the lock if the @gfp flags permit. * Return: 0 if the reservation succeeded or -ENOMEM if it failed. */ -int xa_reserve(struct xarray *xa, unsigned long index, gfp_t gfp) +int __xa_reserve(struct xarray *xa, unsigned long index, gfp_t gfp) { XA_STATE(xas, xa, index); - unsigned int lock_type = xa_lock_type(xa); void *curr; do { - xas_lock_type(&xas, lock_type); curr = xas_load(&xas); if (!curr) xas_store(&xas, XA_ZERO_ENTRY); - xas_unlock_type(&xas, lock_type); - } while (xas_nomem(&xas, gfp)); + } while (__xas_nomem(&xas, gfp)); return xas_error(&xas); } -EXPORT_SYMBOL(xa_reserve); +EXPORT_SYMBOL(__xa_reserve); #ifdef CONFIG_XARRAY_MULTI static void xas_set_range(struct xa_state *xas, unsigned long first, -- cgit From 5404a7f1c21cfda061712bedf2d06cc0f6c755e9 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Mon, 5 Nov 2018 09:34:04 -0500 Subject: XArray tests: Correct some 64-bit assumptions The test-suite caught these two mistakes when compiled for 32-bit. I had only been running the test-suite in 64-bit mode. Signed-off-by: Matthew Wilcox --- lib/test_xarray.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/test_xarray.c') diff --git a/lib/test_xarray.c b/lib/test_xarray.c index e5294b20b52f..5f9c14e975a4 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -504,7 +504,7 @@ static noinline void check_multi_store(struct xarray *xa) rcu_read_unlock(); /* We can erase multiple values with a single store */ - xa_store_order(xa, 0, 63, NULL, GFP_KERNEL); + xa_store_order(xa, 0, BITS_PER_LONG - 1, NULL, GFP_KERNEL); XA_BUG_ON(xa, !xa_empty(xa)); /* Even when the first slot is empty but the others aren't */ @@ -1101,7 +1101,7 @@ static noinline void check_store_range(struct xarray *xa) __check_store_range(xa, 4095 + i, 4095 + j); __check_store_range(xa, 4096 + i, 4096 + j); __check_store_range(xa, 123456 + i, 123456 + j); - __check_store_range(xa, UINT_MAX + i, UINT_MAX + j); + __check_store_range(xa, (1 << 24) + i, (1 << 24) + j); } } } -- cgit From fffc9a260e38acec3187515738122a3ecb24ac90 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Mon, 19 Nov 2018 09:36:29 -0500 Subject: XArray tests: Add missing locking Lockdep caught me being sloppy in the test suite and failing to lock the XArray appropriately. Reported-by: kernel test robot Signed-off-by: Matthew Wilcox --- lib/test_xarray.c | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'lib/test_xarray.c') diff --git a/lib/test_xarray.c b/lib/test_xarray.c index 5f9c14e975a4..0598e86af8fc 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -208,15 +208,19 @@ static noinline void check_xa_mark_1(struct xarray *xa, unsigned long index) XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_2)); /* We should see two elements in the array */ + rcu_read_lock(); xas_for_each(&xas, entry, ULONG_MAX) seen++; + rcu_read_unlock(); XA_BUG_ON(xa, seen != 2); /* One of which is marked */ xas_set(&xas, 0); seen = 0; + rcu_read_lock(); xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0) seen++; + rcu_read_unlock(); XA_BUG_ON(xa, seen != 1); } XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_0)); @@ -442,7 +446,9 @@ static noinline void check_multi_store_1(struct xarray *xa, unsigned long index, XA_BUG_ON(xa, xa_load(xa, max) != NULL); XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL); + xas_lock(&xas); XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(min)) != xa_mk_value(index)); + xas_unlock(&xas); XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_value(min)); XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_value(min)); XA_BUG_ON(xa, xa_load(xa, max) != NULL); @@ -458,9 +464,11 @@ static noinline void check_multi_store_2(struct xarray *xa, unsigned long index, XA_STATE(xas, xa, index); xa_store_order(xa, index, order, xa_mk_value(0), GFP_KERNEL); + xas_lock(&xas); XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(1)) != xa_mk_value(0)); XA_BUG_ON(xa, xas.xa_index != index); XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1)); + xas_unlock(&xas); XA_BUG_ON(xa, !xa_empty(xa)); } #endif @@ -1180,10 +1188,12 @@ static noinline void check_account(struct xarray *xa) XA_STATE(xas, xa, 1 << order); xa_store_order(xa, 0, order, xa, GFP_KERNEL); + rcu_read_lock(); xas_load(&xas); XA_BUG_ON(xa, xas.xa_node->count == 0); XA_BUG_ON(xa, xas.xa_node->count > (1 << order)); XA_BUG_ON(xa, xas.xa_node->nr_values != 0); + rcu_read_unlock(); xa_store_order(xa, 1 << order, order, xa_mk_value(1 << order), GFP_KERNEL); -- cgit