- 21 Oct, 2018 32 commits
-
-
Matthew Wilcox authored
Instead of calling find_get_pages_range() and putting any reference, use xas_find() to iterate over any entries in the range, skipping the shadow/swap entries. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
Rename the function from page_cache_tree_delete_batch to just page_cache_delete_batch. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
Now the page cache lookup is using the XArray, let's convert this regression test from the radix tree API to the XArray so it's testing roughly the same thing it was testing before. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
Slight change of strategy here; if we have trouble getting hold of a page for whatever reason (eg a compound page is split underneath us), don't spin to stabilise the page, just continue the iteration, like we would if we failed to trylock the page. Since this is a speculative optimisation, it feels like we should allow the process to take an extra fault if it turns out to need this page instead of spending time to pin down a page it may not need. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
Slightly shorter and simpler code. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
The 'end' parameter of the xas_for_each iterator avoids a useless iteration at the end of the range. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
There's no direct replacement for radix_tree_for_each_contig() in the XArray API as it's an unusual thing to do. Instead, open-code a loop using xas_next(). This removes the only user of radix_tree_for_each_contig() so delete the iterator from the API and the test suite code for it. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
The 'end' parameter of the xas_for_each iterator avoids a useless iteration at the end of the range. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
Slightly shorter and simpler code. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
Slightly shorter and simpler code. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
The code is slightly shorter and simpler. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
Use the XArray APIs to add and replace pages in the page cache. This removes two uses of the radix tree preload API and is significantly shorter code. It also removes the last user of __radix_tree_create() outside radix-tree.c itself, so make it static. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
The page cache offers the ability to search for a miss in the previous or next N locations. Rather than teach the XArray about the page cache's definition of a miss, use xas_prev() and xas_next() to search the page array. This should be more efficient as it does not have to start the lookup from the top for each index. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
Change i_pages from a radix_tree_root to an xarray, convert the documentation into kernel-doc format and change the order of the elements to pack them better on 64-bit systems. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
Use the XA_TRACK_FREE ability to track which entries have a free bit, similarly to how it uses the radix tree's IDR_FREE tag. This eliminates the per-cpu ida_bitmap preload, and fixes the memory consumption regression I introduced when making the IDR able to store any pointer. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
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>
-
Matthew Wilcox authored
Add myself as XArray and IDR maintainer. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
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>
-
Matthew Wilcox authored
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>
-
Matthew Wilcox authored
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>
-
Matthew Wilcox authored
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>
-
Matthew Wilcox authored
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>
-
Matthew Wilcox authored
The xa_extract function combines the functionality of radix_tree_gang_lookup() and radix_tree_gang_lookup_tagged(). It extracts entries matching the specified filter into a normal array. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
Matthew Wilcox authored
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>
-
Matthew Wilcox authored
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>
-
Matthew Wilcox authored
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>
-
Matthew Wilcox authored
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>
-
Matthew Wilcox authored
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>
-
Matthew Wilcox authored
This is documentation on how to use the XArray, not details about its internal implementation. Signed-off-by: Matthew Wilcox <willy@infradead.org> Acked-by: Josef Bacik <jbacik@fb.com>
-
Matthew Wilcox authored
This is a direct replacement for struct radix_tree_node. A couple of struct members have changed name, so convert those. Use a #define so that radix tree users continue to work without change. Signed-off-by: Matthew Wilcox <willy@infradead.org> Reviewed-by: Josef Bacik <jbacik@fb.com>
-
Matthew Wilcox authored
This is a direct replacement for struct radix_tree_root. Some of the struct members have changed name; convert those, and use a #define so that radix_tree users continue to work without change. Signed-off-by: Matthew Wilcox <willy@infradead.org> Reviewed-by: Josef Bacik <jbacik@fb.com>
-
- 30 Sep, 2018 4 commits
-
-
Matthew Wilcox authored
Instead of storing a pointer to the slot containing the canonical entry, store the offset of the slot. Produces slightly more efficient code (~300 bytes) and simplifies the implementation. Signed-off-by: Matthew Wilcox <willy@infradead.org> Reviewed-by: Josef Bacik <jbacik@fb.com>
-
Matthew Wilcox authored
Introduce xarray value entries and tagged pointers to replace radix tree exceptional entries. This is a slight change in encoding to allow the use of an extra bit (we can now store BITS_PER_LONG - 1 bits in a value entry). It is also a change in emphasis; exceptional entries are intimidating and different. As the comment explains, you can choose to store values or pointers in the xarray and they are both first-class citizens. Signed-off-by: Matthew Wilcox <willy@infradead.org> Reviewed-by: Josef Bacik <jbacik@fb.com>
-
Matthew Wilcox authored
An upcoming change to the encoding of internal entries will set the bottom two bits to 0b10. Unfortunately, m68k only aligns some data structures to 2 bytes, so the IDR will interpret them as internal entries and things will go badly wrong. Change the radix tree so that it stops either when the node indicates that it's the bottom of the tree (shift == 0) or when the entry is not an internal entry. This means we cannot insert an arbitrary kernel pointer as a multiorder entry, but the IDR does not permit multiorder entries. Annoyingly, this means the IDR can no longer take advantage of the radix tree's ability to store a single entry at offset 0 without allocating memory. A pointer which is 2-byte aligned cannot be stored directly in the root as it would be indistinguishable from a node, so we must allocate a node in order to store a 2-byte pointer at index 0. The idr_replace() function does not take a GFP flags argument, so cannot allocate memory. If a user inserts a 4-byte aligned pointer at index 0 and then replaces it with a 2-byte aligned pointer, we must be able to store it. Arbitrary pointer values are still not permitted; pointers of the form 2 + (i * 4) for values of i between 0 and 1023 are reserved for the implementation. These are not valid kernel pointers as they would point into the zero page. This change does cause a runtime memory consumption regression for the IDA. I will recover that later. Signed-off-by: Matthew Wilcox <willy@infradead.org> Tested-by: Guenter Roeck <linux@roeck-us.net>
-
Matthew Wilcox authored
Redirect some older email addresses that are in the git logs. Signed-off-by: Matthew Wilcox <willy@infradead.org>
-
- 29 Sep, 2018 4 commits
-
-
git://git.kernel.dk/linux-blockGreg Kroah-Hartman authored
Jens writes: "Block fixes for 4.19-rc6 A set of fixes that should go into this release. This pull request contains: - A fix (hopefully) for the persistent grants for xen-blkfront. A previous fix from this series wasn't complete, hence reverted, and this one should hopefully be it. (Boris Ostrovsky) - Fix for an elevator drain warning with SMR devices, which is triggered when you switch schedulers (Damien) - bcache deadlock fix (Guoju Fang) - Fix for the block unplug tracepoint, which has had the timer/explicit flag reverted since 4.11 (Ilya) - Fix a regression in this series where the blk-mq timeout hook is invoked with the RCU read lock held, hence preventing it from blocking (Keith) - NVMe pull from Christoph, with a single multipath fix (Susobhan Dey)" * tag 'for-linus-20180929' of git://git.kernel.dk/linux-block: xen/blkfront: correct purging of persistent grants Revert "xen/blkfront: When purging persistent grants, keep them in the buffer" blk-mq: I/O and timer unplugs are inverted in blktrace bcache: add separate workqueue for journal_write to avoid deadlock xen/blkfront: When purging persistent grants, keep them in the buffer block: fix deadline elevator drain for zoned block devices blk-mq: Allow blocking queue tag iter callbacks nvme: properly propagate errors in nvme_mpath_init
-
git://git.kernel.org/pub/scm/linux/kernel/git/tip/tipGreg Kroah-Hartman authored
Thomas writes: "A single fix for the AMD memory encryption boot code so it does not read random garbage instead of the cached encryption bit when a kexec kernel is allocated above the 32bit address limit." * 'x86-urgent-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip: x86/boot: Fix kexec booting failure in the SEV bit detection code
-
git://git.kernel.org/pub/scm/linux/kernel/git/tip/tipGreg Kroah-Hartman authored
Thomas writes: "Three small fixes for clocksource drivers: - Proper error handling in the Atmel PIT driver - Add CLOCK_SOURCE_SUSPEND_NONSTOP for TI SoCs so suspend works again - Fix the next event function for Facebook Backpack-CMM BMC chips so usleep(100) doesnt sleep several milliseconds" * 'timers-urgent-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip: clocksource/drivers/timer-atmel-pit: Properly handle error cases clocksource/drivers/fttmr010: Fix set_next_event handler clocksource/drivers/ti-32k: Add CLOCK_SOURCE_SUSPEND_NONSTOP flag for non-am43 SoCs
-
git://git.kernel.org/pub/scm/linux/kernel/git/tip/tipGreg Kroah-Hartman authored
Thomas writes: "A single fix for a missing sanity check when a pinned event is tried to be read on the wrong CPU due to a legit event scheduling failure." * 'perf-urgent-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip: perf/core: Add sanity check to deal with pinned event failure
-