kernel/linux
0
Fork 0
mirror of https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/ synced 2026-10-01 18:21:29 +00:00
Code Issues Releases Packages Activity
linux/lib/test_xarray.c

1598 lines
41 KiB
Raw Permalink Normal View History

xarray: Add XArray load operation The xa_load function brings with it a lot of infrastructure; xa_empty(), xa_is_err(), and large chunks of the XArray advanced API that are used to implement xa_load. As the test-suite demonstrates, it is possible to use the XArray functions on a radix tree. The radix tree functions depend on the GFP flags being stored in the root of the tree, so it's not possible to use the radix tree functions on an XArray. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-07 14:57:46 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add XArray load operation The xa_load function brings with it a lot of infrastructure; xa_empty(), xa_is_err(), and large chunks of the XArray advanced API that are used to implement xa_load. As the test-suite demonstrates, it is possible to use the XArray functions on a radix tree. The radix tree functions depend on the GFP flags being stored in the root of the tree, so it's not possible to use the radix tree functions on an XArray. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-07 14:57:46 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add XArray load operation The xa_load function brings with it a lot of infrastructure; xa_empty(), xa_is_err(), and large chunks of the XArray advanced API that are used to implement xa_load. As the test-suite demonstrates, it is possible to use the XArray functions on a radix tree. The radix tree functions depend on the GFP flags being stored in the root of the tree, so it's not possible to use the radix tree functions on an XArray. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-07 14:57:46 -05:00
XArray tests: Add check_insert A simple test which just checks that inserting an entry into an empty array succeeds. Try various different interesting indices. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-03-09 22:25:27 -05:00
xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-07-04 10:50:12 -04:00
XArray: Redesign xa_alloc API It was too easy to forget to initialise the start index. Add an xa_limit data structure which can be used to pass min & max, and define a couple of special values for common cases. Also add some more tests cribbed from the IDR test suite. Change the return value from -ENOSPC to -EBUSY to match xa_insert(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-12-31 10:41:01 -05:00
xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-07-04 10:50:12 -04:00
XArray: Redesign xa_alloc API It was too easy to forget to initialise the start index. Add an xa_limit data structure which can be used to pass min & max, and define a couple of special values for common cases. Also add some more tests cribbed from the IDR test suite. Change the return value from -ENOSPC to -EBUSY to match xa_insert(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-12-31 10:41:01 -05:00
xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-07-04 10:50:12 -04:00
xarray: Add XArray load operation The xa_load function brings with it a lot of infrastructure; xa_empty(), xa_is_err(), and large chunks of the XArray advanced API that are used to implement xa_load. As the test-suite demonstrates, it is possible to use the XArray functions on a radix tree. The radix tree functions depend on the GFP flags being stored in the root of the tree, so it's not possible to use the radix tree functions on an XArray. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-07 14:57:46 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
xarray: Add XArray load operation The xa_load function brings with it a lot of infrastructure; xa_empty(), xa_is_err(), and large chunks of the XArray advanced API that are used to implement xa_load. As the test-suite demonstrates, it is possible to use the XArray functions on a radix tree. The radix tree functions depend on the GFP flags being stored in the root of the tree, so it's not possible to use the radix tree functions on an XArray. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-07 14:57:46 -05:00
xarray: Add XArray iterators The xa_for_each iterator allows the user to efficiently walk a range of the array, executing the loop body once for each entry in that range that matches the filter. This commit also includes xa_find() and xa_find_after() which are helper functions for xa_for_each() but may also be useful in their own right. In the xas family of functions, we have xas_for_each(), xas_find(), xas_next_entry(), xas_for_each_tagged(), xas_find_tagged(), xas_next_tagged() and xas_pause(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-14 08:30:11 -05:00
XArray tests: RCU lock prohibits GFP_KERNEL Drop and reacquire the RCU read lock while using GFP_KERNEL. Reported-by: Li RongQing <lirongqing@baidu.com> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-04 23:12:08 -05:00
xarray: Add XArray iterators The xa_for_each iterator allows the user to efficiently walk a range of the array, executing the loop body once for each entry in that range that matches the filter. This commit also includes xa_find() and xa_find_after() which are helper functions for xa_for_each() but may also be useful in their own right. In the xas family of functions, we have xas_for_each(), xas_find(), xas_next_entry(), xas_for_each_tagged(), xas_find_tagged(), xas_next_tagged() and xas_pause(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-14 08:30:11 -05:00
XArray tests: RCU lock prohibits GFP_KERNEL Drop and reacquire the RCU read lock while using GFP_KERNEL. Reported-by: Li RongQing <lirongqing@baidu.com> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-04 23:12:08 -05:00
xarray: Add XArray iterators The xa_for_each iterator allows the user to efficiently walk a range of the array, executing the loop body once for each entry in that range that matches the filter. This commit also includes xa_find() and xa_find_after() which are helper functions for xa_for_each() but may also be useful in their own right. In the xas family of functions, we have xas_for_each(), xas_find(), xas_next_entry(), xas_for_each_tagged(), xas_find_tagged(), xas_next_tagged() and xas_pause(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-14 08:30:11 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add XArray iterators The xa_for_each iterator allows the user to efficiently walk a range of the array, executing the loop body once for each entry in that range that matches the filter. This commit also includes xa_find() and xa_find_after() which are helper functions for xa_for_each() but may also be useful in their own right. In the xas family of functions, we have xas_for_each(), xas_find(), xas_next_entry(), xas_for_each_tagged(), xas_find_tagged(), xas_next_tagged() and xas_pause(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-14 08:30:11 -05:00
xarray: Add XArray load operation The xa_load function brings with it a lot of infrastructure; xa_empty(), xa_is_err(), and large chunks of the XArray advanced API that are used to implement xa_load. As the test-suite demonstrates, it is possible to use the XArray functions on a radix tree. The radix tree functions depend on the GFP flags being stored in the root of the tree, so it's not possible to use the radix tree functions on an XArray. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-07 14:57:46 -05:00
xarray: Add XArray marks XArray marks are like the radix tree tags, only slightly more strongly typed. They are renamed in order to distinguish them from tagged pointers. This commit adds the basic get/set/clear operations. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 09:34:31 -05:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
xarray: Add XArray marks XArray marks are like the radix tree tags, only slightly more strongly typed. They are renamed in order to distinguish them from tagged pointers. This commit adds the basic get/set/clear operations. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 09:34:31 -05:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
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 <gorcunov@gmail.com> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-01-14 13:57:31 -05:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
xarray: Move multiorder_shrink to kernel tests Test this functionality inside the kernel as well as in userspace. Also remove insert_bug() as there's no comparable thing to test in the XArray code. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-09-08 12:09:52 -04:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
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 <gorcunov@gmail.com> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-01-14 13:57:31 -05:00
xarray: Move multiorder_shrink to kernel tests Test this functionality inside the kernel as well as in userspace. Also remove insert_bug() as there's no comparable thing to test in the XArray code. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-09-08 12:09:52 -04:00
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 <rong.a.chen@intel.com> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-19 09:36:29 -05:00
xarray: Move multiorder_shrink to kernel tests Test this functionality inside the kernel as well as in userspace. Also remove insert_bug() as there's no comparable thing to test in the XArray code. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-09-08 12:09:52 -04:00
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 <rong.a.chen@intel.com> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-19 09:36:29 -05:00
xarray: Move multiorder_shrink to kernel tests Test this functionality inside the kernel as well as in userspace. Also remove insert_bug() as there's no comparable thing to test in the XArray code. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-09-08 12:09:52 -04:00
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 <rong.a.chen@intel.com> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-19 09:36:29 -05:00
xarray: Move multiorder_shrink to kernel tests Test this functionality inside the kernel as well as in userspace. Also remove insert_bug() as there's no comparable thing to test in the XArray code. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-09-08 12:09:52 -04:00
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 <rong.a.chen@intel.com> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-19 09:36:29 -05:00
xarray: Move multiorder_shrink to kernel tests Test this functionality inside the kernel as well as in userspace. Also remove insert_bug() as there's no comparable thing to test in the XArray code. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-09-08 12:09:52 -04:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
xarray: Add XArray marks XArray marks are like the radix tree tags, only slightly more strongly typed. They are renamed in order to distinguish them from tagged pointers. This commit adds the basic get/set/clear operations. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 09:34:31 -05:00
radix tree: Remove radix_tree_clear_tags The page cache was the only user of this interface and it has now been converted to the XArray. Transform the test into a test of xas_init_marks(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-04-09 16:52:21 -04:00
xarray: Add XArray marks XArray marks are like the radix tree tags, only slightly more strongly typed. They are renamed in order to distinguish them from tagged pointers. This commit adds the basic get/set/clear operations. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 09:34:31 -05:00
radix tree: Remove radix_tree_clear_tags The page cache was the only user of this interface and it has now been converted to the XArray. Transform the test into a test of xas_init_marks(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-04-09 16:52:21 -04:00
xarray: Add XArray marks XArray marks are like the radix tree tags, only slightly more strongly typed. They are renamed in order to distinguish them from tagged pointers. This commit adds the basic get/set/clear operations. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 09:34:31 -05:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
xarray: Move multiorder_shrink to kernel tests Test this functionality inside the kernel as well as in userspace. Also remove insert_bug() as there's no comparable thing to test in the XArray code. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-09-08 12:09:52 -04:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
xarray: Move multiorder_shrink to kernel tests Test this functionality inside the kernel as well as in userspace. Also remove insert_bug() as there's no comparable thing to test in the XArray code. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-09-08 12:09:52 -04:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
XArray tests: Add check_insert A simple test which just checks that inserting an entry into an empty array succeeds. Try various different interesting indices. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-03-09 22:25:27 -05:00
xarray: Add XArray conditional store operations Like cmpxchg(), xa_cmpxchg will only store to the index if the current entry matches the old entry. It returns the current entry, which is usually more useful than the errno returned by radix_tree_insert(). For the users who really only want the errno, the xa_insert() wrapper provides a more convenient calling convention. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:34:55 -05:00
XArray: Change xa_insert to return -EBUSY Userspace translates EEXIST to "File exists" which isn't a very good error message for the problem. "Device or resource busy" is a better indication of what went wrong. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-06 13:07:11 -05:00
xarray: Add XArray conditional store operations Like cmpxchg(), xa_cmpxchg will only store to the index if the current entry matches the old entry. It returns the current entry, which is usually more useful than the errno returned by radix_tree_insert(). For the users who really only want the errno, the xa_insert() wrapper provides a more convenient calling convention. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:34:55 -05:00
xarray: Add xa_reserve and xa_release This function reserves a slot in the XArray for users which need to acquire multiple locks before storing their entry in the tree and so cannot use a plain xa_store(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-01 14:54:59 -04:00
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 <willy@infradead.org>
2018-12-17 14:45:36 -05:00
XArray: Fix xa_release in allocating arrays xa_cmpxchg() was a little too magic in turning ZERO entries into NULL, and would leave the entry set to the ZERO entry instead of releasing it for future use. After careful review of existing users of xa_cmpxchg(), change the semantics so that it does not translate either incoming argument from NULL into ZERO entries. Add several tests to the test-suite to make sure this problem doesn't come back. Reported-by: Jason Gunthorpe <jgg@ziepe.ca> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-20 11:30:49 -05:00
xarray: Add xa_reserve and xa_release This function reserves a slot in the XArray for users which need to acquire multiple locks before storing their entry in the tree and so cannot use a plain xa_store(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-01 14:54:59 -04:00
XArray: Mark xa_insert and xa_reserve as must_check If the user doesn't care about the return value from xa_insert(), then they should be using xa_store() instead. The point of xa_reserve() is to get the return value early before taking another lock, so this should also be __must_check. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-08 14:02:45 -05:00
xarray: Add xa_reserve and xa_release This function reserves a slot in the XArray for users which need to acquire multiple locks before storing their entry in the tree and so cannot use a plain xa_store(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-01 14:54:59 -04:00
XArray: Mark xa_insert and xa_reserve as must_check If the user doesn't care about the return value from xa_insert(), then they should be using xa_store() instead. The point of xa_reserve() is to get the return value early before taking another lock, so this should also be __must_check. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-08 14:02:45 -05:00
xarray: Add xa_reserve and xa_release This function reserves a slot in the XArray for users which need to acquire multiple locks before storing their entry in the tree and so cannot use a plain xa_store(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-01 14:54:59 -04:00
XArray: Fix xa_release in allocating arrays xa_cmpxchg() was a little too magic in turning ZERO entries into NULL, and would leave the entry set to the ZERO entry instead of releasing it for future use. After careful review of existing users of xa_cmpxchg(), change the semantics so that it does not translate either incoming argument from NULL into ZERO entries. Add several tests to the test-suite to make sure this problem doesn't come back. Reported-by: Jason Gunthorpe <jgg@ziepe.ca> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-20 11:30:49 -05:00
XArray: Mark xa_insert and xa_reserve as must_check If the user doesn't care about the return value from xa_insert(), then they should be using xa_store() instead. The point of xa_reserve() is to get the return value early before taking another lock, so this should also be __must_check. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-08 14:02:45 -05:00
XArray: Fix xa_release in allocating arrays xa_cmpxchg() was a little too magic in turning ZERO entries into NULL, and would leave the entry set to the ZERO entry instead of releasing it for future use. After careful review of existing users of xa_cmpxchg(), change the semantics so that it does not translate either incoming argument from NULL into ZERO entries. Add several tests to the test-suite to make sure this problem doesn't come back. Reported-by: Jason Gunthorpe <jgg@ziepe.ca> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-20 11:30:49 -05:00
xarray: Add xa_reserve and xa_release This function reserves a slot in the XArray for users which need to acquire multiple locks before storing their entry in the tree and so cannot use a plain xa_store(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-01 14:54:59 -04:00
XArray: Fix xa_release in allocating arrays xa_cmpxchg() was a little too magic in turning ZERO entries into NULL, and would leave the entry set to the ZERO entry instead of releasing it for future use. After careful review of existing users of xa_cmpxchg(), change the semantics so that it does not translate either incoming argument from NULL into ZERO entries. Add several tests to the test-suite to make sure this problem doesn't come back. Reported-by: Jason Gunthorpe <jgg@ziepe.ca> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-20 11:30:49 -05:00
XArray: Mark xa_insert and xa_reserve as must_check If the user doesn't care about the return value from xa_insert(), then they should be using xa_store() instead. The point of xa_reserve() is to get the return value early before taking another lock, so this should also be __must_check. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-08 14:02:45 -05:00
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 <willy@infradead.org>
2019-01-02 13:57:03 -05:00
XArray: Change xa_insert to return -EBUSY Userspace translates EEXIST to "File exists" which isn't a very good error message for the problem. "Device or resource busy" is a better indication of what went wrong. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-06 13:07:11 -05:00
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 <willy@infradead.org>
2019-01-02 13:57:03 -05:00
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 <willy@infradead.org>
2018-10-30 09:45:55 -04:00
xarray: Add xa_reserve and xa_release This function reserves a slot in the XArray for users which need to acquire multiple locks before storing their entry in the tree and so cannot use a plain xa_store(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-01 14:54:59 -04:00
XArray: Mark xa_insert and xa_reserve as must_check If the user doesn't care about the return value from xa_insert(), then they should be using xa_store() instead. The point of xa_reserve() is to get the return value early before taking another lock, so this should also be __must_check. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-08 14:02:45 -05:00
xarray: Add xa_reserve and xa_release This function reserves a slot in the XArray for users which need to acquire multiple locks before storing their entry in the tree and so cannot use a plain xa_store(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-01 14:54:59 -04:00
XArray: Fix xa_release in allocating arrays xa_cmpxchg() was a little too magic in turning ZERO entries into NULL, and would leave the entry set to the ZERO entry instead of releasing it for future use. After careful review of existing users of xa_cmpxchg(), change the semantics so that it does not translate either incoming argument from NULL into ZERO entries. Add several tests to the test-suite to make sure this problem doesn't come back. Reported-by: Jason Gunthorpe <jgg@ziepe.ca> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-20 11:30:49 -05:00
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 <willy@infradead.org>
2018-12-17 14:45:36 -05:00
xarray: Add xa_reserve and xa_release This function reserves a slot in the XArray for users which need to acquire multiple locks before storing their entry in the tree and so cannot use a plain xa_store(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-01 14:54:59 -04:00
XArray: Fix xa_release in allocating arrays xa_cmpxchg() was a little too magic in turning ZERO entries into NULL, and would leave the entry set to the ZERO entry instead of releasing it for future use. After careful review of existing users of xa_cmpxchg(), change the semantics so that it does not translate either incoming argument from NULL into ZERO entries. Add several tests to the test-suite to make sure this problem doesn't come back. Reported-by: Jason Gunthorpe <jgg@ziepe.ca> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-20 11:30:49 -05:00
xarray: Add xa_reserve and xa_release This function reserves a slot in the XArray for users which need to acquire multiple locks before storing their entry in the tree and so cannot use a plain xa_store(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-01 14:54:59 -04:00
XArray: Fix xa_release in allocating arrays xa_cmpxchg() was a little too magic in turning ZERO entries into NULL, and would leave the entry set to the ZERO entry instead of releasing it for future use. After careful review of existing users of xa_cmpxchg(), change the semantics so that it does not translate either incoming argument from NULL into ZERO entries. Add several tests to the test-suite to make sure this problem doesn't come back. Reported-by: Jason Gunthorpe <jgg@ziepe.ca> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-20 11:30:49 -05:00
xarray: Add xa_reserve and xa_release This function reserves a slot in the XArray for users which need to acquire multiple locks before storing their entry in the tree and so cannot use a plain xa_store(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-01 14:54:59 -04:00
xarray: Add XArray iterators The xa_for_each iterator allows the user to efficiently walk a range of the array, executing the loop body once for each entry in that range that matches the filter. This commit also includes xa_find() and xa_find_after() which are helper functions for xa_for_each() but may also be useful in their own right. In the xas family of functions, we have xas_for_each(), xas_find(), xas_next_entry(), xas_for_each_tagged(), xas_find_tagged(), xas_next_tagged() and xas_pause(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-14 08:30:11 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add XArray iterators The xa_for_each iterator allows the user to efficiently walk a range of the array, executing the loop body once for each entry in that range that matches the filter. This commit also includes xa_find() and xa_find_after() which are helper functions for xa_for_each() but may also be useful in their own right. In the xas family of functions, we have xas_for_each(), xas_find(), xas_next_entry(), xas_for_each_tagged(), xas_find_tagged(), xas_next_tagged() and xas_pause(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-14 08:30:11 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add XArray iterators The xa_for_each iterator allows the user to efficiently walk a range of the array, executing the loop body once for each entry in that range that matches the filter. This commit also includes xa_find() and xa_find_after() which are helper functions for xa_for_each() but may also be useful in their own right. In the xas family of functions, we have xas_for_each(), xas_find(), xas_next_entry(), xas_for_each_tagged(), xas_find_tagged(), xas_next_tagged() and xas_pause(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-14 08:30:11 -05:00
xarray: Move multiorder_check to in-kernel tests This version is a little less thorough in order to be a little quicker, but tests the important edge cases. Also test adding a multiorder entry at a non-canonical index, and erasing it. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-09-09 01:52:17 -04:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Move multiorder_check to in-kernel tests This version is a little less thorough in order to be a little quicker, but tests the important edge cases. Also test adding a multiorder entry at a non-canonical index, and erasing it. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-09-09 01:52:17 -04:00
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 <rong.a.chen@intel.com> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-19 09:36:29 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
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 <rong.a.chen@intel.com> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-19 09:36:29 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Move multiorder_check to in-kernel tests This version is a little less thorough in order to be a little quicker, but tests the important edge cases. Also test adding a multiorder entry at a non-canonical index, and erasing it. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-09-09 01:52:17 -04:00
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 <rong.a.chen@intel.com> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-19 09:36:29 -05:00
xarray: Move multiorder_check to in-kernel tests This version is a little less thorough in order to be a little quicker, but tests the important edge cases. Also test adding a multiorder entry at a non-canonical index, and erasing it. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-09-09 01:52:17 -04:00
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 <rong.a.chen@intel.com> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-19 09:36:29 -05:00
xarray: Move multiorder_check to in-kernel tests This version is a little less thorough in order to be a little quicker, but tests the important edge cases. Also test adding a multiorder entry at a non-canonical index, and erasing it. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-09-09 01:52:17 -04:00
XArray tests: Check iterating over multiorder entries There was no bug here, but there was no test coverage for this scenario. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-29 16:04:35 -05:00
xarray: Move multiorder_check to in-kernel tests This version is a little less thorough in order to be a little quicker, but tests the important edge cases. Also test adding a multiorder entry at a non-canonical index, and erasing it. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-09-09 01:52:17 -04:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
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 <willy@infradead.org>
2018-11-05 09:34:04 -05:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
xarray: Move multiorder_check to in-kernel tests This version is a little less thorough in order to be a little quicker, but tests the important edge cases. Also test adding a multiorder entry at a non-canonical index, and erasing it. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-09-09 01:52:17 -04:00
XArray tests: Check iterating over multiorder entries There was no bug here, but there was no test coverage for this scenario. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-29 16:04:35 -05:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
XArray: Add support for 1s-based allocation A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-26 14:43:22 -04:00
xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-07-04 10:50:12 -04:00
XArray: Add support for 1s-based allocation A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-26 14:43:22 -04:00
xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-07-04 10:50:12 -04:00
XArray: Add support for 1s-based allocation A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-26 14:43:22 -04:00
xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-07-04 10:50:12 -04:00
XArray: Add support for 1s-based allocation A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-26 14:43:22 -04:00
xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-07-04 10:50:12 -04:00
XArray: Add support for 1s-based allocation A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-26 14:43:22 -04:00
xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-07-04 10:50:12 -04:00
XArray: Add support for 1s-based allocation A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-26 14:43:22 -04:00
xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-07-04 10:50:12 -04:00
XArray: Add support for 1s-based allocation A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-26 14:43:22 -04:00
xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-07-04 10:50:12 -04:00
XArray: Add support for 1s-based allocation A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-26 14:43:22 -04:00
xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-07-04 10:50:12 -04:00
XArray: Add support for 1s-based allocation A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-26 14:43:22 -04:00
xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-07-04 10:50:12 -04:00
XArray: Add support for 1s-based allocation A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-26 14:43:22 -04:00
xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-07-04 10:50:12 -04:00
XArray: Add support for 1s-based allocation A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-26 14:43:22 -04:00
XArray: Redesign xa_alloc API It was too easy to forget to initialise the start index. Add an xa_limit data structure which can be used to pass min & max, and define a couple of special values for common cases. Also add some more tests cribbed from the IDR test suite. Change the return value from -ENOSPC to -EBUSY to match xa_insert(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-12-31 10:41:01 -05:00
xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-07-04 10:50:12 -04:00
XArray: Add support for 1s-based allocation A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-26 14:43:22 -04:00
XArray: Redesign xa_alloc API It was too easy to forget to initialise the start index. Add an xa_limit data structure which can be used to pass min & max, and define a couple of special values for common cases. Also add some more tests cribbed from the IDR test suite. Change the return value from -ENOSPC to -EBUSY to match xa_insert(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-12-31 10:41:01 -05:00
xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-07-04 10:50:12 -04:00
XArray: Add support for 1s-based allocation A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-26 14:43:22 -04:00
XArray: Redesign xa_alloc API It was too easy to forget to initialise the start index. Add an xa_limit data structure which can be used to pass min & max, and define a couple of special values for common cases. Also add some more tests cribbed from the IDR test suite. Change the return value from -ENOSPC to -EBUSY to match xa_insert(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-12-31 10:41:01 -05:00
XArray: Add support for 1s-based allocation A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-26 14:43:22 -04:00
XArray: Fix xa_alloc when id exceeds max Specifying a starting ID greater than the maximum ID isn't something attempted very often, but it should fail. It was succeeding due to xas_find_marked() returning the wrong error state, so add tests for both xa_alloc() and xas_find_marked(). Fixes: b803b42823d0 ("xarray: Add XArray iterators") Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-12-13 13:57:42 -05:00
XArray: Redesign xa_alloc API It was too easy to forget to initialise the start index. Add an xa_limit data structure which can be used to pass min & max, and define a couple of special values for common cases. Also add some more tests cribbed from the IDR test suite. Change the return value from -ENOSPC to -EBUSY to match xa_insert(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-12-31 10:41:01 -05:00
XArray: Add support for 1s-based allocation A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-26 14:43:22 -04:00
XArray: Redesign xa_alloc API It was too easy to forget to initialise the start index. Add an xa_limit data structure which can be used to pass min & max, and define a couple of special values for common cases. Also add some more tests cribbed from the IDR test suite. Change the return value from -ENOSPC to -EBUSY to match xa_insert(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-12-31 10:41:01 -05:00
XArray: Add support for 1s-based allocation A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-26 14:43:22 -04:00
XArray: Redesign xa_alloc API It was too easy to forget to initialise the start index. Add an xa_limit data structure which can be used to pass min & max, and define a couple of special values for common cases. Also add some more tests cribbed from the IDR test suite. Change the return value from -ENOSPC to -EBUSY to match xa_insert(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-12-31 10:41:01 -05:00
XArray: Add cyclic allocation This differs slightly from the IDR equivalent in five ways. 1. It can allocate up to UINT_MAX instead of being limited to INT_MAX, like xa_alloc(). Also like xa_alloc(), it will write to the 'id' pointer before placing the entry in the XArray. 2. The 'next' cursor is allocated separately from the XArray instead of being part of the IDR. This saves memory for all the users which do not use the cyclic allocation API and suits some users better. 3. It returns -EBUSY instead of -ENOSPC. 4. It will attempt to wrap back to the minimum value on memory allocation failure as well as on an -EBUSY error, assuming that a user would rather allocate a small ID than suffer an ID allocation failure. 5. It reports whether it has wrapped, which is important to some users. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-06 14:13:35 -05:00
XArray: Add support for 1s-based allocation A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-26 14:43:22 -04:00
XArray: Redesign xa_alloc API It was too easy to forget to initialise the start index. Add an xa_limit data structure which can be used to pass min & max, and define a couple of special values for common cases. Also add some more tests cribbed from the IDR test suite. Change the return value from -ENOSPC to -EBUSY to match xa_insert(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-12-31 10:41:01 -05:00
XArray: Add cyclic allocation This differs slightly from the IDR equivalent in five ways. 1. It can allocate up to UINT_MAX instead of being limited to INT_MAX, like xa_alloc(). Also like xa_alloc(), it will write to the 'id' pointer before placing the entry in the XArray. 2. The 'next' cursor is allocated separately from the XArray instead of being part of the IDR. This saves memory for all the users which do not use the cyclic allocation API and suits some users better. 3. It returns -EBUSY instead of -ENOSPC. 4. It will attempt to wrap back to the minimum value on memory allocation failure as well as on an -EBUSY error, assuming that a user would rather allocate a small ID than suffer an ID allocation failure. 5. It reports whether it has wrapped, which is important to some users. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-06 14:13:35 -05:00
xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-07-04 10:50:12 -04:00
xarray: Add xas_for_each_conflict This iterator iterates over each entry that is stored in the index or indices specified by the xa_state. This is intended for use for a conditional store of a multiindex entry, or to allow entries which are about to be removed from the xarray to be disposed of properly. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-06-01 22:46:02 -04:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add xas_for_each_conflict This iterator iterates over each entry that is stored in the index or indices specified by the xa_state. This is intended for use for a conditional store of a multiindex entry, or to allow entries which are about to be removed from the xarray to be disposed of properly. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-06-01 22:46:02 -04:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add xas_for_each_conflict This iterator iterates over each entry that is stored in the index or indices specified by the xa_state. This is intended for use for a conditional store of a multiindex entry, or to allow entries which are about to be removed from the xarray to be disposed of properly. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-06-01 22:46:02 -04:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add xas_for_each_conflict This iterator iterates over each entry that is stored in the index or indices specified by the xa_state. This is intended for use for a conditional store of a multiindex entry, or to allow entries which are about to be removed from the xarray to be disposed of properly. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-06-01 22:46:02 -04:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add xas_for_each_conflict This iterator iterates over each entry that is stored in the index or indices specified by the xa_state. This is intended for use for a conditional store of a multiindex entry, or to allow entries which are about to be removed from the xarray to be disposed of properly. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-06-01 22:46:02 -04:00
xarray: Add XArray iterators The xa_for_each iterator allows the user to efficiently walk a range of the array, executing the loop body once for each entry in that range that matches the filter. This commit also includes xa_find() and xa_find_after() which are helper functions for xa_for_each() but may also be useful in their own right. In the xas family of functions, we have xas_for_each(), xas_find(), xas_next_entry(), xas_for_each_tagged(), xas_find_tagged(), xas_next_tagged() and xas_pause(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-14 08:30:11 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add XArray iterators The xa_for_each iterator allows the user to efficiently walk a range of the array, executing the loop body once for each entry in that range that matches the filter. This commit also includes xa_find() and xa_find_after() which are helper functions for xa_for_each() but may also be useful in their own right. In the xas family of functions, we have xas_for_each(), xas_find(), xas_next_entry(), xas_for_each_tagged(), xas_find_tagged(), xas_next_tagged() and xas_pause(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-14 08:30:11 -05:00
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 <willy@infradead.org>
2018-11-01 16:55:19 -04:00
xarray: Add XArray iterators The xa_for_each iterator allows the user to efficiently walk a range of the array, executing the loop body once for each entry in that range that matches the filter. This commit also includes xa_find() and xa_find_after() which are helper functions for xa_for_each() but may also be useful in their own right. In the xas family of functions, we have xas_for_each(), xas_find(), xas_next_entry(), xas_for_each_tagged(), xas_find_tagged(), xas_next_tagged() and xas_pause(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-14 08:30:11 -05:00
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 <willy@infradead.org>
2018-11-01 16:55:19 -04:00
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 <willy@infradead.org>
2018-12-17 14:45:36 -05:00
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 <willy@infradead.org>
2018-11-01 16:55:19 -04:00
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 <willy@infradead.org>
2018-12-17 14:45:36 -05:00
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 <willy@infradead.org>
2018-11-01 16:55:19 -04:00
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 <willy@infradead.org>
2018-12-17 14:45:36 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
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 <willy@infradead.org>
2018-11-01 16:55:19 -04:00
XArray: Fix xa_alloc when id exceeds max Specifying a starting ID greater than the maximum ID isn't something attempted very often, but it should fail. It was succeeding due to xas_find_marked() returning the wrong error state, so add tests for both xa_alloc() and xas_find_marked(). Fixes: b803b42823d0 ("xarray: Add XArray iterators") Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-12-13 13:57:42 -05:00
XArray tests: Add RCU locking 0day picked up that I'd forgotten to add locking to this new test. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-12-17 17:37:25 -05:00
XArray: Fix xa_alloc when id exceeds max Specifying a starting ID greater than the maximum ID isn't something attempted very often, but it should fail. It was succeeding due to xas_find_marked() returning the wrong error state, so add tests for both xa_alloc() and xas_find_marked(). Fixes: b803b42823d0 ("xarray: Add XArray iterators") Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-12-13 13:57:42 -05:00
XArray tests: Add RCU locking 0day picked up that I'd forgotten to add locking to this new test. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-12-17 17:37:25 -05:00
XArray: Fix xa_alloc when id exceeds max Specifying a starting ID greater than the maximum ID isn't something attempted very often, but it should fail. It was succeeding due to xas_find_marked() returning the wrong error state, so add tests for both xa_alloc() and xas_find_marked(). Fixes: b803b42823d0 ("xarray: Add XArray iterators") Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-12-13 13:57:42 -05:00
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 <willy@infradead.org>
2018-11-01 16:55:19 -04:00
XArray: Fix xa_alloc when id exceeds max Specifying a starting ID greater than the maximum ID isn't something attempted very often, but it should fail. It was succeeding due to xas_find_marked() returning the wrong error state, so add tests for both xa_alloc() and xas_find_marked(). Fixes: b803b42823d0 ("xarray: Add XArray iterators") Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-12-13 13:57:42 -05:00
xarray: Add XArray iterators The xa_for_each iterator allows the user to efficiently walk a range of the array, executing the loop body once for each entry in that range that matches the filter. This commit also includes xa_find() and xa_find_after() which are helper functions for xa_for_each() but may also be useful in their own right. In the xas family of functions, we have xas_for_each(), xas_find(), xas_next_entry(), xas_for_each_tagged(), xas_find_tagged(), xas_next_tagged() and xas_pause(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-14 08:30:11 -05:00
shmem: Convert find_swap_entry to XArray This is a 1:1 conversion. The major part of this patch is converting the test framework from userspace to kernel space and mirroring the algorithm now used in find_swap_entry(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-22 08:36:00 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
shmem: Convert find_swap_entry to XArray This is a 1:1 conversion. The major part of this patch is converting the test framework from userspace to kernel space and mirroring the algorithm now used in find_swap_entry(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-22 08:36:00 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
shmem: Convert find_swap_entry to XArray This is a 1:1 conversion. The major part of this patch is converting the test framework from userspace to kernel space and mirroring the algorithm now used in find_swap_entry(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-22 08:36:00 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
shmem: Convert find_swap_entry to XArray This is a 1:1 conversion. The major part of this patch is converting the test framework from userspace to kernel space and mirroring the algorithm now used in find_swap_entry(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-22 08:36:00 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
shmem: Convert find_swap_entry to XArray This is a 1:1 conversion. The major part of this patch is converting the test framework from userspace to kernel space and mirroring the algorithm now used in find_swap_entry(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-22 08:36:00 -05:00
xarray: Step through an XArray The xas_next and xas_prev functions move the xas index by one position, and adjust the rest of the iterator state to match it. This is more efficient than calling xas_set() as it keeps the iterator at the leaves of the tree instead of walking the iterator from the root each time. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-12-01 00:06:52 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Step through an XArray The xas_next and xas_prev functions move the xas index by one position, and adjust the rest of the iterator state to match it. This is more efficient than calling xas_set() as it keeps the iterator at the leaves of the tree instead of walking the iterator from the root each time. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-12-01 00:06:52 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Step through an XArray The xas_next and xas_prev functions move the xas index by one position, and adjust the rest of the iterator state to match it. This is more efficient than calling xas_set() as it keeps the iterator at the leaves of the tree instead of walking the iterator from the root each time. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-12-01 00:06:52 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Step through an XArray The xas_next and xas_prev functions move the xas index by one position, and adjust the rest of the iterator state to match it. This is more efficient than calling xas_set() as it keeps the iterator at the leaves of the tree instead of walking the iterator from the root each time. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-12-01 00:06:52 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Step through an XArray The xas_next and xas_prev functions move the xas index by one position, and adjust the rest of the iterator state to match it. This is more efficient than calling xas_set() as it keeps the iterator at the leaves of the tree instead of walking the iterator from the root each time. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-12-01 00:06:52 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Step through an XArray The xas_next and xas_prev functions move the xas index by one position, and adjust the rest of the iterator state to match it. This is more efficient than calling xas_set() as it keeps the iterator at the leaves of the tree instead of walking the iterator from the root each time. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-12-01 00:06:52 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Step through an XArray The xas_next and xas_prev functions move the xas index by one position, and adjust the rest of the iterator state to match it. This is more efficient than calling xas_set() as it keeps the iterator at the leaves of the tree instead of walking the iterator from the root each time. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-12-01 00:06:52 -05:00
xarray: Add xas_create_range This hopefully temporary function is useful for users who have not yet been converted to multi-index entries. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-12-04 00:11:48 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add xas_create_range This hopefully temporary function is useful for users who have not yet been converted to multi-index entries. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-12-04 00:11:48 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add xas_create_range This hopefully temporary function is useful for users who have not yet been converted to multi-index entries. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-12-04 00:11:48 -05:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add xas_create_range This hopefully temporary function is useful for users who have not yet been converted to multi-index entries. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-12-04 00:11:48 -05:00
xarray: Add range store functionality This version of xa_store_range() really only supports load and store. Our only user only needs basic load and store functionality, so there's no need to do the extra work to support marking and overlapping stores correctly yet. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-08-15 14:13:29 -04:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add range store functionality This version of xa_store_range() really only supports load and store. Our only user only needs basic load and store functionality, so there's no need to do the extra work to support marking and overlapping stores correctly yet. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-08-15 14:13:29 -04:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Add range store functionality This version of xa_store_range() really only supports load and store. Our only user only needs basic load and store functionality, so there's no need to do the extra work to support marking and overlapping stores correctly yet. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-08-15 14:13:29 -04:00
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 <willy@infradead.org>
2018-11-05 09:34:04 -05:00
xarray: Add range store functionality This version of xa_store_range() really only supports load and store. Our only user only needs basic load and store functionality, so there's no need to do the extra work to support marking and overlapping stores correctly yet. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-08-15 14:13:29 -04:00
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 <willy@infradead.org>
2018-12-28 23:20:44 -05:00
XArray: Redesign xa_alloc API It was too easy to forget to initialise the start index. Add an xa_limit data structure which can be used to pass min & max, and define a couple of special values for common cases. Also add some more tests cribbed from the IDR test suite. Change the return value from -ENOSPC to -EBUSY to match xa_insert(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-12-31 10:41:01 -05:00
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 <willy@infradead.org>
2018-12-28 23:20:44 -05:00
XArray: Fix xa_reserve for 2-byte aligned entries If we reserve index 0, the next entry to be stored there might be 2-byte aligned. That means we have to create the root xa_node at the time of reserving the initial entry. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-21 17:54:44 -05:00
XArray: Fix xa_erase of 2-byte aligned entries xas_store() was interpreting the entry it found in the array as a node entry if the bottom two bits had value 2. That's only true if either the entry is in the root node or in a non-leaf node. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-21 17:36:45 -05:00
XArray: Fix xa_reserve for 2-byte aligned entries If we reserve index 0, the next entry to be stored there might be 2-byte aligned. That means we have to create the root xa_node at the time of reserving the initial entry. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-21 17:54:44 -05:00
XArray: Fix xa_erase of 2-byte aligned entries xas_store() was interpreting the entry it found in the array as a node entry if the bottom two bits had value 2. That's only true if either the entry is in the root node or in a non-leaf node. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-21 17:36:45 -05:00
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 <willy@infradead.org>
2018-12-28 23:20:44 -05:00
XArray: Fix xa_erase of 2-byte aligned entries xas_store() was interpreting the entry it found in the array as a node entry if the bottom two bits had value 2. That's only true if either the entry is in the root node or in a non-leaf node. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-21 17:36:45 -05:00
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 <willy@infradead.org>
2018-12-28 23:20:44 -05:00
mm: Convert workingset to XArray We construct an XA_STATE and use it to delete the node with xas_store() rather than adding a special function for this unique use case. Includes a test that simulates this usage for the test suite. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-24 14:24:59 -05:00
xarray: Move multiorder account test in-kernel Move this test to the in-kernel test suite, and enhance it to test several different orders. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-08-28 16:13:16 -04:00
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 <rong.a.chen@intel.com> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-19 09:36:29 -05:00
xarray: Move multiorder account test in-kernel Move this test to the in-kernel test suite, and enhance it to test several different orders. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-08-28 16:13:16 -04:00
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 <rong.a.chen@intel.com> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-19 09:36:29 -05:00
xarray: Move multiorder account test in-kernel Move this test to the in-kernel test suite, and enhance it to test several different orders. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-08-28 16:13:16 -04:00
XArray tests: Handle larger indices more elegantly xa_mk_value() only handles values up to LONG_MAX. I successfully hid that inside xa_store_index() and xa_erase_index(), but it turned out I also needed it for testing xa_alloc() on 32-bit machines. So extract xa_mk_index() from the above two functions, and convert the non-constant users of xa_mk_value() to xa_mk_index(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-11-05 13:19:54 -05:00
xarray: Move multiorder account test in-kernel Move this test to the in-kernel test suite, and enhance it to test several different orders. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-08-28 16:13:16 -04:00
xarray: Destroy an XArray This function frees all the internal memory allocated to the xarray and reinitialises it to be empty. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-17 08:16:34 -05:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
xarray: Add XArray load operation The xa_load function brings with it a lot of infrastructure; xa_empty(), xa_is_err(), and large chunks of the XArray advanced API that are used to implement xa_load. As the test-suite demonstrates, it is possible to use the XArray functions on a radix tree. The radix tree functions depend on the GFP flags being stored in the root of the tree, so it's not possible to use the radix tree functions on an XArray. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-07 14:57:46 -05:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
xarray: Add XArray iterators The xa_for_each iterator allows the user to efficiently walk a range of the array, executing the loop body once for each entry in that range that matches the filter. This commit also includes xa_find() and xa_find_after() which are helper functions for xa_for_each() but may also be useful in their own right. In the xas family of functions, we have xas_for_each(), xas_find(), xas_next_entry(), xas_for_each_tagged(), xas_find_tagged(), xas_next_tagged() and xas_pause(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-14 08:30:11 -05:00
xarray: Add XArray load operation The xa_load function brings with it a lot of infrastructure; xa_empty(), xa_is_err(), and large chunks of the XArray advanced API that are used to implement xa_load. As the test-suite demonstrates, it is possible to use the XArray functions on a radix tree. The radix tree functions depend on the GFP flags being stored in the root of the tree, so it's not possible to use the radix tree functions on an XArray. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-07 14:57:46 -05:00
xarray: Add XArray marks XArray marks are like the radix tree tags, only slightly more strongly typed. They are renamed in order to distinguish them from tagged pointers. This commit adds the basic get/set/clear operations. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 09:34:31 -05:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
xarray: Add XArray iterators The xa_for_each iterator allows the user to efficiently walk a range of the array, executing the loop body once for each entry in that range that matches the filter. This commit also includes xa_find() and xa_find_after() which are helper functions for xa_for_each() but may also be useful in their own right. In the xas family of functions, we have xas_for_each(), xas_find(), xas_next_entry(), xas_for_each_tagged(), xas_find_tagged(), xas_next_tagged() and xas_pause(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-14 08:30:11 -05:00
XArray tests: Add check_insert A simple test which just checks that inserting an entry into an empty array succeeds. Try various different interesting indices. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-03-09 22:25:27 -05:00
xarray: Add XArray conditional store operations Like cmpxchg(), xa_cmpxchg will only store to the index if the current entry matches the old entry. It returns the current entry, which is usually more useful than the errno returned by radix_tree_insert(). For the users who really only want the errno, the xa_insert() wrapper provides a more convenient calling convention. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:34:55 -05:00
xarray: Add xa_reserve and xa_release This function reserves a slot in the XArray for users which need to acquire multiple locks before storing their entry in the tree and so cannot use a plain xa_store(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-10-01 14:54:59 -04:00
XArray: Fix xa_release in allocating arrays xa_cmpxchg() was a little too magic in turning ZERO entries into NULL, and would leave the entry set to the ZERO entry instead of releasing it for future use. After careful review of existing users of xa_cmpxchg(), change the semantics so that it does not translate either incoming argument from NULL into ZERO entries. Add several tests to the test-suite to make sure this problem doesn't come back. Reported-by: Jason Gunthorpe <jgg@ziepe.ca> Signed-off-by: Matthew Wilcox <willy@infradead.org>
2019-02-20 11:30:49 -05:00
xarray: Add XArray unconditional store operations xa_store() differs from radix_tree_insert() in that it will overwrite an existing element in the array rather than returning an error. This is the behaviour which most users want, and those that want more complex behaviour generally want to use the xas family of routines anyway. For memory allocation, xa_store() will first attempt to request memory from the slab allocator; if memory is not immediately available, it will drop the xa_lock and allocate memory, keeping a pointer in the xa_state. It does not use the per-CPU cache, although those will continue to exist until all radix tree users are converted to the xarray. This patch also includes xa_erase() and __xa_erase() for a streamlined way to store NULL. Since there is no need to allocate memory in order to store a NULL in the XArray, we do not need to trouble the user with deciding what memory allocation flags to use. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-10 15:15:08 -05:00
xarray: Track free entries in an XArray Add the optional ability to track which entries in an XArray are free and provide xa_alloc() to replace most of the functionality of the IDR. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-07-04 10:50:12 -04:00
xarray: Add XArray iterators The xa_for_each iterator allows the user to efficiently walk a range of the array, executing the loop body once for each entry in that range that matches the filter. This commit also includes xa_find() and xa_find_after() which are helper functions for xa_for_each() but may also be useful in their own right. In the xas family of functions, we have xas_for_each(), xas_find(), xas_next_entry(), xas_for_each_tagged(), xas_find_tagged(), xas_next_tagged() and xas_pause(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-14 08:30:11 -05:00
shmem: Convert find_swap_entry to XArray This is a 1:1 conversion. The major part of this patch is converting the test framework from userspace to kernel space and mirroring the algorithm now used in find_swap_entry(). Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-22 08:36:00 -05:00
xarray: Move multiorder account test in-kernel Move this test to the in-kernel test suite, and enhance it to test several different orders. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-08-28 16:13:16 -04:00
xarray: Destroy an XArray This function frees all the internal memory allocated to the xarray and reinitialises it to be empty. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-17 08:16:34 -05:00
xarray: Step through an XArray The xas_next and xas_prev functions move the xas index by one position, and adjust the rest of the iterator state to match it. This is more efficient than calling xas_set() as it keeps the iterator at the leaves of the tree instead of walking the iterator from the root each time. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-12-01 00:06:52 -05:00
xarray: Add xas_create_range This hopefully temporary function is useful for users who have not yet been converted to multi-index entries. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-12-04 00:11:48 -05:00
xarray: Add range store functionality This version of xa_store_range() really only supports load and store. Our only user only needs basic load and store functionality, so there's no need to do the extra work to support marking and overlapping stores correctly yet. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-08-15 14:13:29 -04:00
xarray: Add xas_for_each_conflict This iterator iterates over each entry that is stored in the index or indices specified by the xa_state. This is intended for use for a conditional store of a multiindex entry, or to allow entries which are about to be removed from the xarray to be disposed of properly. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-06-01 22:46:02 -04:00
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 <willy@infradead.org>
2018-12-28 23:20:44 -05:00
xarray: Add XArray load operation The xa_load function brings with it a lot of infrastructure; xa_empty(), xa_is_err(), and large chunks of the XArray advanced API that are used to implement xa_load. As the test-suite demonstrates, it is possible to use the XArray functions on a radix tree. The radix tree functions depend on the GFP flags being stored in the root of the tree, so it's not possible to use the radix tree functions on an XArray. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-07 14:57:46 -05:00
mm: Convert workingset to XArray We construct an XA_STATE and use it to delete the node with xas_store() rather than adding a special function for this unique use case. Includes a test that simulates this usage for the test suite. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-24 14:24:59 -05:00
xarray: Add XArray load operation The xa_load function brings with it a lot of infrastructure; xa_empty(), xa_is_err(), and large chunks of the XArray advanced API that are used to implement xa_load. As the test-suite demonstrates, it is possible to use the XArray functions on a radix tree. The radix tree functions depend on the GFP flags being stored in the root of the tree, so it's not possible to use the radix tree functions on an XArray. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2017-11-07 14:57:46 -05:00