linux-toradex.git/include/linux/xarray.h, branch v5.10-rc3

Merge tag 'xarray-5.9' of git://git.infradead.org/users/willy/xarray

2020-10-20T21:39:37+00:00

Pull XArray updates from Matthew Wilcox:

 - Fix the test suite after introduction of the local_lock

 - Fix a bug in the IDA spotted by Coverity

 - Change the API that allows the workingset code to delete a node

 - Fix xas_reload() when dealing with entries that occupy multiple
   indices

 - Add a few more tests to the test suite

 - Fix an unsigned int being shifted into an unsigned long

* tag 'xarray-5.9' of git://git.infradead.org/users/willy/xarray:
  XArray: Fix xas_create_range for ranges above 4 billion
  radix-tree: fix the comment of radix_tree_next_slot()
  XArray: Fix xas_reload for multi-index entries
  XArray: Add private interface for workingset node deletion
  XArray: Fix xas_for_each_conflict documentation
  XArray: Test marked multiorder iterations
  XArray: Test two more things about xa_cmpxchg
  ida: Free allocated bitmap in error path
  radix tree test suite: Fix compilation

XArray: add xas_split

2020-10-16T18:11:15+00:00

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

XArray: add xa_get_order

2020-10-16T18:11:15+00:00

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

XArray: Fix xas_reload for multi-index entries

2020-10-13T12:41:26+00:00

xas_reload() was only checking that the head entry was still at the
head index.  If the entry has been split, that's not enough as there
may be a different entry at the specified index now.

Solve this by checking the slot for the requested index instead of the
head index.

Signed-off-by: Matthew Wilcox (Oracle)

XArray: Add private interface for workingset node deletion

2020-10-13T12:41:26+00:00

Move the tricky bits of dealing with the XArray from the workingset
code to the XArray.  Make it clear in the documentation that this is a
private interface, and only export it for the benefit of the test suite.

Signed-off-by: Matthew Wilcox (Oracle)

XArray: Fix xas_for_each_conflict documentation

2020-10-08T14:07:48+00:00

At one point, xas_for_each_conflict() was going to work this way,
and I forgot to update the documentation when I changed my mind.

Signed-off-by: Matthew Wilcox (Oracle)

xarray.h: correct return code documentation for xa_store_{bh,irq}()

2020-06-08T18:05:56+00:00

__xa_store() and xa_store() document that the functions can fail, and
that the return code can be an xa_err() encoded error code.

xa_store_bh() and xa_store_irq() do not document that the functions can
fail and that they can also return xa_err() encoded error codes.

Thus: Update the documentation.

Signed-off-by: Manfred Spraul 
Signed-off-by: Andrew Morton 
Cc: Matthew Wilcox 
Link: http://lkml.kernel.org/r/20200430111424.16634-1-manfred@colorfullife.com
Signed-off-by: Linus Torvalds

xarray: Fix early termination of xas_for_each_marked

2020-03-12T21:42:08+00:00

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)

XArray: Fix incorrect comment in header file

2020-01-31T20:09:49+00:00

256 means Retry entry and 257 means Zero entry,
so fix it.

Signed-off-by: Chengguang Xu 
Signed-off-by: Matthew Wilcox (Oracle)

XArray: Add xa_for_each_range

2020-01-18T03:33:37+00:00

This function supports iterating over a range of an array.  Also add
documentation links for xa_for_each_start().

Signed-off-by: Matthew Wilcox (Oracle)