lib: radix-tree: check accounting of existing slot replacement users
authorJohannes Weiner <hannes@cmpxchg.org>
Tue, 13 Dec 2016 00:43:43 +0000 (16:43 -0800)
committerLinus Torvalds <torvalds@linux-foundation.org>
Tue, 13 Dec 2016 02:55:08 +0000 (18:55 -0800)
commit6d75f366b9242f9b17ed7d0b0604d7460f818f21
treed2225813a4c3f435e79273780eac7b1f7b2ecf67
parentf7942430e40f14c6d2ca48a1875add509938c07d
lib: radix-tree: check accounting of existing slot replacement users

The bug in khugepaged fixed earlier in this series shows that radix tree
slot replacement is fragile; and it will become more so when not only
NULL<->!NULL transitions need to be caught but transitions from and to
exceptional entries as well.  We need checks.

Re-implement radix_tree_replace_slot() on top of the sanity-checked
__radix_tree_replace().  This requires existing callers to also pass the
radix tree root, but it'll warn us when somebody replaces slots with
contents that need proper accounting (transitions between NULL entries,
real entries, exceptional entries) and where a replacement through the
slot pointer would corrupt the radix tree node counts.

Link: http://lkml.kernel.org/r/20161117193021.GB23430@cmpxchg.org
Signed-off-by: Johannes Weiner <hannes@cmpxchg.org>
Suggested-by: Jan Kara <jack@suse.cz>
Reviewed-by: Jan Kara <jack@suse.cz>
Cc: Kirill A. Shutemov <kirill.shutemov@linux.intel.com>
Cc: Hugh Dickins <hughd@google.com>
Cc: Matthew Wilcox <mawilcox@linuxonhyperv.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
arch/s390/mm/gmap.c
drivers/sh/intc/virq.c
fs/dax.c
include/linux/radix-tree.h
lib/radix-tree.c
mm/filemap.c
mm/khugepaged.c
mm/migrate.c
mm/truncate.c
tools/testing/radix-tree/multiorder.c