linux.git/include/linux/maple_tree.h, branch v6.6-rc2

maple_tree: shrink struct maple_tree

2023-08-24T23:20:32+00:00

Pack the members of struct maple_tree to avoid holes on 64-bit.  The size
shrinks from 24 to 16 bytes which will save eight bytes in every structure
which embeds it.

[willy@infradead.org: changelog alterations]
Link: https://lkml.kernel.org/r/20230821225145.2169848-1-mjguzik@gmail.com
Signed-off-by: Mateusz Guzik 
Reviewed-by: Liam R. Howlett 
Reviewed-by: Matthew Wilcox (Oracle) 
Signed-off-by: Andrew Morton

maple_tree: re-introduce entry to mas_preallocate() arguments

2023-08-18T17:12:48+00:00

The current preallocation strategy is to preallocate the absolute
worst-case allocation for a tree modification.  The entry (or NULL) is
needed to know how many nodes are needed to write to the tree.  Start by
adding the argument to the mas_preallocate() definition.

Link: https://lkml.kernel.org/r/20230724183157.3939892-8-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: Peng Zhang 
Cc: Suren Baghdasaryan 
Signed-off-by: Andrew Morton

maple_tree: introduce __mas_set_range()

2023-08-18T17:12:48+00:00

mas_set_range() resets the node to MAS_START, which will cause a re-walk
of the tree to the range.  This is unnecessary when the maple state is
already at the correct location of the write.  Add a function that only
sets the range to avoid unnecessary re-walking of the tree.

Link: https://lkml.kernel.org/r/20230724183157.3939892-6-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: Peng Zhang 
Cc: Suren Baghdasaryan 
Signed-off-by: Andrew Morton

maple_tree: Be more strict about locking

2023-08-18T17:12:40+00:00

Use lockdep to check the write path in the maple tree holds the lock in
write mode.

Introduce mt_write_lock_is_held() to check if the lock is held for
writing.  Update the necessary checks for rcu_dereference_protected() to
use the new write lock check.

Link: https://lkml.kernel.org/r/20230714195551.894800-5-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: Linus Torvalds 
Cc: Oliver Sang 
Signed-off-by: Andrew Morton

mm/mmap: change detached vma locking scheme

2023-08-18T17:12:40+00:00

Don't set the lock to the mm lock so that the detached VMA tree does not
complain about being unlocked when the mmap_lock is dropped prior to
freeing the tree.

Introduce mt_on_stack() for setting the external lock to NULL only when
LOCKDEP is used.

Move the destroying of the detached tree outside the mmap lock all
together.

Link: https://lkml.kernel.org/r/20230719183142.ktgcmuj2pnlr3h3s@revolver
Signed-off-by: Liam R. Howlett 
Cc: Linus Torvalds 
Cc: Oliver Sang 
Signed-off-by: Andrew Morton

maple_tree: relax lockdep checks for on-stack trees

2023-08-18T17:12:39+00:00

To support early release of the maple tree locks, do not lockdep check the
lock if it is set to NULL.  This is intended for the special case on-stack
use of tracking entries and not for general use.

Link: https://lkml.kernel.org/r/20230714195551.894800-3-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: Linus Torvalds 
Cc: Oliver Sang 
Signed-off-by: Andrew Morton

maple_tree: don't use MAPLE_ARANGE64_META_MAX to indicate no gap

2023-08-18T17:12:21+00:00

Patch series "Improve the validation for maple tree and some cleanup", v2.


This patch (of 7):

Do not use a special offset to indicate that there is no gap.  When there
is no gap, offset can point to any valid slots because its gap is 0.

Link: https://lkml.kernel.org/r/20230711035444.526-1-zhangpeng.00@bytedance.com
Link: https://lkml.kernel.org/r/20230711035444.526-3-zhangpeng.00@bytedance.com
Signed-off-by: Peng Zhang 
Reviewed-by: Liam R. Howlett 
Tested-by: Geert Uytterhoeven 
Signed-off-by: Andrew Morton

maple_tree: fix a few documentation issues

2023-08-18T17:12:00+00:00

The documentation of mt_next() claims that it starts the search at the
provided index.  That's incorrect as it starts the search after the
provided index.

The documentation of mt_find() is slightly confusing.  "Handles locking"
is not really helpful as it does not explain how the "locking" works. 
Also the documentation of index talks about a range, while in reality the
index is updated on a succesful search to the index of the found entry
plus one.

Fix similar issues for mt_find_after() and mt_prev().

Reword the confusing "Note: Will not return the zero entry." comment on
mt_for_each() and document @__index correctly.

Link: https://lkml.kernel.org/r/87ttw2n556.ffs@tglx
Signed-off-by: Thomas Gleixner 
Reviewed-by: Liam R. Howlett 
Cc: Matthew Wilcox 
Cc: Shanker Donthineni 
Signed-off-by: Andrew Morton

maple_tree: relocate the declaration of mas_empty_area_rev().

2023-06-09T23:25:46+00:00

Relocate the declaration of mas_empty_area_rev() so that mas_empty_area()
and mas_empty_area_rev() are together.

Link: https://lkml.kernel.org/r/20230524031247.65949-11-zhangpeng.00@bytedance.com
Signed-off-by: Peng Zhang 
Reviewed-by: Liam R. Howlett 
Signed-off-by: Andrew Morton

maple_tree: add mas_prev_range() and mas_find_range_rev interface

2023-06-09T23:25:34+00:00

Some users of the maple tree may want to move to the previous range
regardless of the value stored there.  Add this interface as well as the
'find' variant to support walking to the first value, then iterating over
the previous ranges.

Link: https://lkml.kernel.org/r/20230518145544.1722059-32-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: Vernon Yang 
Cc: David Binderman 
Cc: Peng Zhang 
Cc: Sergey Senozhatsky 
Cc: Wei Yang 
Signed-off-by: Andrew Morton