Add config option "SHIFT=<value>" to Makefile for building test suite
with any value of RADIX_TREE_MAP_SHIFT between 3 and 7 inclusive.
Signed-off-by: Rehas Sachdeva <aquannie@gmail.com>
[mawilcox@microsoft.com: .gitignore, quieten grep, remove on clean]
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

Where we use the radix tree iteration macros, we need to annotate 'slot'
with __rcu.  Make sure we don't forget any new places in the future with
the same CFLAGS check used for radix-tree.c.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

Many places were missing __rcu annotations.  A few places needed a few
lines of explanation about why it was safe to not use RCU accessors.
Add a custom CFLAGS setting to the Makefile to ensure that new patches
don't miss RCU annotations.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

Some of these have been missing for many years.  Others were recently
introduced by me.  Fortunately, we have tools that help us find such
things.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

If the -l flag is set, run the tests for 100 seconds each instead of
the normal 10 seconds.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
Reviewed-by: Rehas Sachdeva <aquannie@gmail.com>

The last of the memory leaks in the test suite was a couple of places in
the split/join testing where I forgot to free the element being removed
from the tree.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
Reviewed-by: Rehas Sachdeva <aquannie@gmail.com>

None of the malloc'ed data structures were ever being freed.  Found with
-fsanitize=address.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
Reviewed-by: Rehas Sachdeva <aquannie@gmail.com>

If item_insert() or item_insert_order() failed to insert an item, they
would leak the item they had just created.  This was causing runaway
memory consumption while running the iteration_check testcase, which
proves that Ross has too much memory in his workstation ;-)

Make sure to free the item on error.  Found with -fsanitize=address.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
Reviewed-by: Rehas Sachdeva <aquannie@gmail.com>

I was looking for a memory scribble and instead found a pile of memory
leaks.  Ensure no more occur in future.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
Reviewed-by: Rehas Sachdeva <aquannie@gmail.com>

The address sanitizer occasionally finds an out of bounds error while
running the test-suite.  It turned out to be a read of the pointer
immediately next to the tree root, but this out of bounds error could
have occurred elsewhere.  This happens because radix_tree_iter_resume()
dereferences 'slot' before checking whether we've come to the end of
the chunk.  We can just delete this line; the value was never used.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

Instead of having this mysterious private_data in each radix_tree_node,
store a pointer to the root, which can be useful for debugging.  This also
relieves the mm code from the duty of updating it.
Acked-by: Johannes Weiner <hannes@cmpxchg.org>
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

Chaining through the ->private_data member means we have to zero
->private_data after removing preallocated nodes from the list.
We're about to initialise ->parent anyway, so we can avoid zeroing it.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

Make the output of radix tree test suite less verbose by default and add
-v and -vv command line options for increasing level of verbosity.
Signed-off-by: Rehas Sachdeva <aquannie@gmail.com>
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

To help track down where memory leaks may be, add the ability to turn
on/off printing allocations, frees and delayed frees.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

It is a relatively common idiom (8 instances) to first look up an IDR
entry, and then remove it from the tree if it is found, possibly doing
further operations upon the entry afterwards.  If we change idr_remove()
to return the removed object, all of these users can save themselves a
walk of the IDR tree.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

To allow developers to run a subset of tests, build separate multiorder
and idr-test binaries which will run just the tests in those files.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
Reviewed-by: Rehas Sachdeva <aquannie@gmail.com>

We can use the root entry as a bitmap and save allocating a 128 byte
bitmap for an IDA that contains only a few entries (30 on a 32-bit
machine, 62 on a 64-bit machine).  This costs about 300 bytes of kernel
text on x86-64, so as long as 3 IDAs fall into this category, this
is a net win for memory consumption.

Thanks to Rasmus Villemoes for his work documenting the problem and
collecting statistics on IDAs.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

When we preload the IDA, we allocate an IDA bitmap.  Instead of storing
that preallocated bitmap in the IDA, we store it in a percpu variable.
Generally there are more IDAs in the system than CPUs, so this cuts down
on the number of preallocated bitmaps that are unused, and about half
of the IDA users did not call ida_destroy() so they were leaking IDA
bitmaps.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

The IDR is very similar to the radix tree.  It has some functionality that
the radix tree did not have (alloc next free, cyclic allocation, a
callback-based for_each, destroy tree), which is readily implementable on
top of the radix tree.  A few small changes were needed in order to use a
tag to represent nodes with free space below them.  More extensive
changes were needed to support storing NULL as a valid entry in an IDR.
Plain radix trees still interpret NULL as a not-present entry.

The IDA is reimplemented as a client of the newly enhanced radix tree.  As
in the current implementation, it uses a bitmap at the last level of the
tree.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
Tested-by: Kirill A. Shutemov <kirill.shutemov@linux.intel.com>
Cc: Konstantin Khlebnikov <koct9i@gmail.com>
Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
Cc: Tejun Heo <tj@kernel.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>

Factor the deletion code out into __radix_tree_delete() and provide a
nice iterator-based wrapper around it.  If we free the node, advance
the iterator to avoid reading from freed memory.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

The counterpart to radix_tree_iter_tag_set(), used by the IDR code
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
Reviewed-by: Rehas Sachdeva <aquannie@gmail.com>

radix-tree.c doesn't use these CONFIG options any more.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
Reviewed-by: Rehas Sachdeva <aquannie@gmail.com>

Instead of specifying how to build find_bit.o from lib/find_bit.o,
use vpath to tell make where to find find_bit.c.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
Reviewed-by: Rehas Sachdeva <aquannie@gmail.com>

Many of the definitions in the radix-tree kernel.h are redundant with
others in tools/include, or are no longer used, such as panic().
Move the definition of __init to init.h and in_interrupt() to preempt.h
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

The tools/include export.h contains everything we need.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

Move the pieces we still need to tools/include and update a few implicit
includes.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

The radix tree hasn't used a mempool since the beginning of git history.
Remove the userspace mempool implementation.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
Reviewed-by: Rehas Sachdeva <aquannie@gmail.com>

Changing tools/include/asm/bug.h showed a missing dependency in the
Makefile.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
Reviewed-by: Rehas Sachdeva <aquannie@gmail.com>

The definition of WARN_ON being used by the radix tree test suite was
deficient in two ways: it did not provide a return value, and it stopped
execution instead of continuing.  This version of WARN_ON tells you
which file & line the assertion was triggered in.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

By adding __set_bit and __clear_bit to the tools include directory, we
can share the bitops code.  This reveals an include loop between kernel.h,
log2.h, bitmap.h and bitops.h.  Break it the same way as the kernel does;
by moving the kernel.h include from bitops.h to bitmap.h.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

If we're just getting the value of a tag, or looking up an entry,
we won't modify the radix tree, so we can declare these functions as
taking a const pointer.  Mostly for documentation purposes, though it
might help code generation.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

We were using spinlock_t and INIT_LIST_HEAD without including spinlock.h
or list.h.  They were being implicitly included through some other header
file, but that's fragile.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

Pull networking fixes from David Miller:

 1) GTP fixes from Andreas Schultz (missing genl module alias, clear IP
    DF on transmit).

 2) Netfilter needs to reflect the fwmark when sending resets, from Pau
    Espin Pedrol.

 3) nftable dump OOPS fix from Liping Zhang.

 4) Fix erroneous setting of VIRTIO_NET_HDR_F_DATA_VALID on transmit,
    from Rolf Neugebauer.

 5) Fix build error of ipt_CLUSTERIP when procfs is disabled, from Arnd
    Bergmann.

 6) Fix regression in handling of NETIF_F_SG in harmonize_features(),
    from Eric Dumazet.

 7) Fix RTNL deadlock wrt. lwtunnel module loading, from David Ahern.

 8) tcp_fastopen_create_child() needs to setup tp->max_window, from
    Alexey Kodanev.

 9) Missing kmemdup() failure check in ipv6 segment routing code, from
    Eric Dumazet.

10) Don't execute unix_bind() under the bindlock, otherwise we deadlock
    with splice. From WANG Cong.

11) ip6_tnl_parse_tlv_enc_lim() potentially reallocates the skb buffer,
    therefore callers must reload cached header pointers into that skb.
    Fix from Eric Dumazet.

12) Fix various bugs in legacy IRQ fallback handling in alx driver, from
    Tobias Regnery.

13) Do not allow lwtunnel drivers to be unloaded while they are
    referenced by active instances, from Robert Shearman.

14) Fix truncated PHY LED trigger names, from Geert Uytterhoeven.

15) Fix a few regressions from virtio_net XDP support, from John
    Fastabend and Jakub Kicinski.

* git://git.kernel.org/pub/scm/linux/kernel/git/davem/net: (102 commits)
  ISDN: eicon: silence misleading array-bounds warning
  net: phy: micrel: add support for KSZ8795
  gtp: fix cross netns recv on gtp socket
  gtp: clear DF bit on GTP packet tx
  gtp: add genl family modules alias
  tcp: don't annotate mark on control socket from tcp_v6_send_response()
  ravb: unmap descriptors when freeing rings
  virtio_net: reject XDP programs using header adjustment
  virtio_net: use dev_kfree_skb for small buffer XDP receive
  r8152: check rx after napi is enabled
  r8152: re-schedule napi for tx
  r8152: avoid start_xmit to schedule napi when napi is disabled
  r8152: avoid start_xmit to call napi_schedule during autosuspend
  net: dsa: Bring back device detaching in dsa_slave_suspend()
  net: phy: leds: Fix truncated LED trigger names
  net: phy: leds: Break dependency of phy.h on phy_led_triggers.h
  net: phy: leds: Clear phy_num_led_triggers on failure to avoid crash
  net-next: ethernet: mediatek: change the compatible string
  Documentation: devicetree: change the mediatek ethernet compatible string
  bnxt_en: Fix RTNL lock usage on bnxt_get_port_module_status().
  ...

Pull xfs uodates from Darrick Wong:
 "I have some more fixes this week: better input validation, corruption
  avoidance, build fixes, memory leak fixes, and a couple from Christoph
  to avoid an ENOSPC failure.

  Summary:
   - Fix race conditions in the CoW code
   - Fix some incorrect input validation checks
   - Avoid crashing fs by running out of space when freeing inodes
   - Fix toctou race wrt whether or not an inode has an attr
   - Fix build error on arm
   - Fix page refcount corruption when readahead fails
   - Don't corrupt userspace in the bmap ioctl"

* tag 'xfs-for-linus-4.10-rc6-5' of git://git.kernel.org/pub/scm/fs/xfs/xfs-linux:
  xfs: prevent quotacheck from overloading inode lru
  xfs: fix bmv_count confusion w/ shared extents
  xfs: clear _XBF_PAGES from buffers when readahead page
  xfs: extsize hints are not unlikely in xfs_bmap_btalloc
  xfs: remove racy hasattr check from attr ops
  xfs: use per-AG reservations for the finobt
  xfs: only update mount/resv fields on success in __xfs_ag_resv_init
  xfs: verify dirblocklog correctly
  xfs: fix COW writeback race

Pull btrfs updates from Chris Mason:
 "Some fixes that we've collected from the list.

  We still have one more pending to nail down a regression in lzo
  compression, but I wanted to get this batch out the door"

* 'for-linus-4.10' of git://git.kernel.org/pub/scm/linux/kernel/git/mason/linux-btrfs:
  Btrfs: remove ->{get, set}_acl() from btrfs_dir_ro_inode_operations
  Btrfs: disable xattr operations on subvolume directories
  Btrfs: remove old tree_root case in btrfs_read_locked_inode()
  Btrfs: fix truncate down when no_holes feature is enabled
  Btrfs: Fix deadlock between direct IO and fast fsync
  btrfs: fix false enospc error when truncating heavily reflinked file

Pull block fixes from Jens Axboe:
 "A set of fixes for this series. This contains:

   - Set of fixes for the nvme target code

   - A revert of patch from this merge window, causing a regression with
     WRITE_SAME on iSCSI targets at least.

   - A fix for a use-after-free in the new O_DIRECT bdev code.

   - Two fixes for the xen-blkfront driver"

* 'for-linus' of git://git.kernel.dk/linux-block:
  Revert "sd: remove __data_len hack for WRITE SAME"
  nvme-fc: use blk_rq_nr_phys_segments
  nvmet-rdma: Fix missing dma sync to nvme data structures
  nvmet: Call fatal_error from keep-alive timout expiration
  nvmet: cancel fatal error and flush async work before free controller
  nvmet: delete controllers deletion upon subsystem release
  nvmet_fc: correct logic in disconnect queue LS handling
  block: fix use after free in __blkdev_direct_IO
  xen-blkfront: correct maximum segment accounting
  xen-blkfront: feature flags handling adjustments

Pull rdma fixes from Doug Ledford:
 "Second round of -rc fixes for 4.10.

  This -rc cycle has been slow for the rdma subsystem. I had already
  sent you the first batch before the Holiday break. After that, we kept
  only getting a few here or there. Up until this week, when I got a
  drop of 13 to one driver (qedr). So, here's the -rc patches I have. I
  currently have none held in reserve, so unless something new comes in,
  this is it until the next merge window opens.

  Summary:

   - series of iw_cxgb4 fixes to make it work with the drain cq API

   - one or two patches each to: srp, iser, cxgb3, vmw_pvrdma, umem,
     rxe, and ipoib

   - one big series (13 patches) for the new qedr driver"

* tag 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/dledford/rdma: (27 commits)
  RDMA/cma: Fix unknown symbol when CONFIG_IPV6 is not enabled
  IB/rxe: Prevent from completer to operate on non valid QP
  IB/rxe: Fix rxe dev insertion to rxe_dev_list
  IB/umem: Release pid in error and ODP flow
  RDMA/qedr: Dispatch port active event from qedr_add
  RDMA/qedr: Fix and simplify memory leak in PD alloc
  RDMA/qedr: Fix RDMA CM loopback
  RDMA/qedr: Fix formatting
  RDMA/qedr: Mark three functions as static
  RDMA/qedr: Don't reset QP when queues aren't flushed
  RDMA/qedr: Don't spam dmesg if QP is in error state
  RDMA/qedr: Remove CQ spinlock from CM completion handlers
  RDMA/qedr: Return max inline data in QP query result
  RDMA/qedr: Return success when not changing QP state
  RDMA/qedr: Add uapi header qedr-abi.h
  RDMA/qedr: Fix MTU returned from QP query
  RDMA/core: Add the function ib_mtu_int_to_enum
  IB/vmw_pvrdma: Fix incorrect cleanup on pvrdma_pci_probe error path
  IB/vmw_pvrdma: Don't leak info from alloc_ucontext
  IB/cxgb3: fix misspelling in header guard
  ...

Pull s390 fixes from Martin Schwidefsky:
 "Another two bug fixes:

   - ptrace partial write information leak

   - a guest page hinting regression introduced with v4.6"

* 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/s390/linux:
  s390/mm: Fix cmma unused transfer from pgste into pte
  s390/ptrace: Preserve previous registers for short regset write

Merge branch 'stable/for-linus-4.10' of git://git.kernel.org/pub/scm/linux/kernel/git/konrad/swiotlb

Pull swiotlb fix from Konrad Rzeszutek Wilk:
 "An ARM fix in the Xen SWIOTLB - mainly the translation of physical to
  bus addresses was done just a tad too late"

* 'stable/for-linus-4.10' of git://git.kernel.org/pub/scm/linux/kernel/git/konrad/swiotlb:
  swiotlb-xen: update dev_addr after swapping pages

Pull VFIO fix from Alex Williamson:
 "mdev IOMMU groups are not yet compatible with the powerpc SPAPR IOMMU
  backend, detect and fail group attach (Greg Kurz)"

* tag 'vfio-v4.10-rc6' of git://github.com/awilliam/linux-vfio:
  vfio/spapr: fail tce_iommu_attach_group() when iommu_data is null