user/sven/linux.git/lib/xarray.c, branch v5.4.140

XArray: add xas_split

2021-06-10T11:37:14Z

commit 8fc75643c5e14574c8be59b69182452ece28315a upstream In order to use multi-index entries for huge pages in the page cache, we need to be able to split a multi-index entry (eg if a file is truncated in the middle of a huge page entry). This version does not support splitting more than one level of the tree at a time. This is an acceptable limitation for the page cache as we do not expect to support order-12 pages in the near future. [akpm@linux-foundation.org: export xas_split_alloc() to modules] [willy@infradead.org: fix xarray split] Link: https://lkml.kernel.org/r/20200910175450.GV6583@casper.infradead.org [willy@infradead.org: fix xarray] Link: https://lkml.kernel.org/r/20201001233943.GW20115@casper.infradead.org Signed-off-by: Matthew Wilcox (Oracle) Signed-off-by: Andrew Morton Cc: "Kirill A . Shutemov" Cc: Qian Cai Cc: Song Liu Link: https://lkml.kernel.org/r/20200903183029.14930-3-willy@infradead.org Signed-off-by: Linus Torvalds Signed-off-by: Greg Kroah-Hartman

XArray: add xa_get_order

2021-06-10T11:37:14Z

commit 57417cebc96b57122a2207fc84a6077d20c84b4b upstream Patch series "Fix read-only THP for non-tmpfs filesystems". As described more verbosely in the [3/3] changelog, we can inadvertently put an order-0 page in the page cache which occupies 512 consecutive entries. Users are running into this if they enable the READ_ONLY_THP_FOR_FS config option; see https://bugzilla.kernel.org/show_bug.cgi?id=206569 and Qian Cai has also reported it here: https://lore.kernel.org/lkml/20200616013309.GB815@lca.pw/ This is a rather intrusive way of fixing the problem, but has the advantage that I've actually been testing it with the THP patches, which means that it sees far more use than it does upstream -- indeed, Song has been entirely unable to reproduce it. It also has the advantage that it removes a few patches from my gargantuan backlog of THP patches. This patch (of 3): This function returns the order of the entry at the index. We need this because there isn't space in the shadow entry to encode its order. [akpm@linux-foundation.org: export xa_get_order to modules] Signed-off-by: Matthew Wilcox (Oracle) Signed-off-by: Andrew Morton Cc: "Kirill A . Shutemov" Cc: Qian Cai Cc: Song Liu Link: https://lkml.kernel.org/r/20200903183029.14930-1-willy@infradead.org Link: https://lkml.kernel.org/r/20200903183029.14930-2-willy@infradead.org Signed-off-by: Linus Torvalds Signed-off-by: Greg Kroah-Hartman

xarray: Fix early termination of xas_for_each_marked

2020-04-17T08:50:18Z

commit 7e934cf5ace1dceeb804f7493fa28bb697ed3c52 upstream. xas_for_each_marked() is using entry == NULL as a termination condition of the iteration. When xas_for_each_marked() is used protected only by RCU, this can however race with xas_store(xas, NULL) in the following way: TASK1 TASK2 page_cache_delete() find_get_pages_range_tag() xas_for_each_marked() xas_find_marked() off = xas_find_chunk() xas_store(&xas, NULL) xas_init_marks(&xas); ... rcu_assign_pointer(*slot, NULL); entry = xa_entry(off); And thus xas_for_each_marked() terminates prematurely possibly leading to missed entries in the iteration (translating to missing writeback of some pages or a similar problem). If we find a NULL entry that has been marked, skip it (unless we're trying to allocate an entry). Reported-by: Jan Kara CC: stable@vger.kernel.org Fixes: ef8e5717db01 ("page cache: Convert delete_batch to XArray") Signed-off-by: Matthew Wilcox (Oracle) Signed-off-by: Greg Kroah-Hartman

XArray: Fix xas_pause for large multi-index entries

2020-04-17T08:50:18Z

commit c36d451ad386b34f452fc3c8621ff14b9eaa31a6 upstream. Inspired by the recent Coverity report, I looked for other places where the offset wasn't being converted to an unsigned long before being shifted, and I found one in xas_pause() when the entry being paused is of order >32. Fixes: b803b42823d0 ("xarray: Add XArray iterators") Signed-off-by: Matthew Wilcox (Oracle) Cc: stable@vger.kernel.org Signed-off-by: Greg Kroah-Hartman

XArray: Fix xa_find_next for large multi-index entries

2020-04-08T07:08:40Z

[ Upstream commit bd40b17ca49d7d110adf456e647701ce74de2241 ] Coverity pointed out that xas_sibling() was shifting xa_offset without promoting it to an unsigned long first, so the shift could cause an overflow and we'd get the wrong answer. The fix is obvious, and the new test-case provokes UBSAN to report an error: runtime error: shift exponent 60 is too large for 32-bit type 'int' Fixes: 19c30f4dd092 ("XArray: Fix xa_find_after with multi-index entries") Reported-by: Bjorn Helgaas Reported-by: Kees Cook Signed-off-by: Matthew Wilcox (Oracle) Cc: stable@vger.kernel.org Signed-off-by: Sasha Levin

XArray: Fix xas_pause at ULONG_MAX

2020-02-05T21:22:47Z

[ Upstream commit 82a22311b7a68a78709699dc8c098953b70e4fd2 ] If we were unlucky enough to call xas_pause() when the index was at ULONG_MAX (or a multi-slot entry which ends at ULONG_MAX), we would wrap the index back around to 0 and restart the iteration from the beginning. Use the XAS_BOUNDS state to indicate that we should just stop the iteration. Signed-off-by: Matthew Wilcox (Oracle) Signed-off-by: Sasha Levin

XArray: Fix xas_find returning too many entries

2020-01-29T15:45:27Z

commit c44aa5e8ab58b5f4cf473970ec784c3333496a2e upstream. If you call xas_find() with the initial index > max, it should have returned NULL but was returning the entry at index. Signed-off-by: Matthew Wilcox (Oracle) Cc: stable@vger.kernel.org Signed-off-by: Greg Kroah-Hartman

XArray: Fix xa_find_after with multi-index entries

2020-01-29T15:45:26Z

commit 19c30f4dd0923ef191f35c652ee4058e91e89056 upstream. If the entry is of an order which is a multiple of XA_CHUNK_SIZE, the current detection of sibling entries does not work. Factor out an xas_sibling() function to make xa_find_after() a little more understandable, and write a new implementation that doesn't suffer from the same bug. Signed-off-by: Matthew Wilcox (Oracle) Cc: stable@vger.kernel.org Signed-off-by: Greg Kroah-Hartman

XArray: Fix infinite loop with entry at ULONG_MAX

2020-01-29T15:45:26Z

commit 430f24f94c8a174d411a550d7b5529301922e67a upstream. If there is an entry at ULONG_MAX, xa_for_each() will overflow the 'index + 1' in xa_find_after() and wrap around to 0. Catch this case and terminate the loop by returning NULL. Signed-off-by: Matthew Wilcox (Oracle) Cc: stable@vger.kernel.org Signed-off-by: Greg Kroah-Hartman

XArray: Fix xas_next() with a single entry at 0

2019-07-01T21:11:16Z

If there is only a single entry at 0, the first time we call xas_next(), we return the entry. Unfortunately, all subsequent times we call xas_next(), we also return the entry at 0 instead of noticing that the xa_index is now greater than zero. This broke find_get_pages_contig(). Fixes: 64d3e9a9e0cc ("xarray: Step through an XArray") Reported-by: Kent Overstreet Signed-off-by: Matthew Wilcox (Oracle)