When run
	make -C tools DESTDIR=/my/nice/dir turbostat_install
get a message
	install: cannot create regular file '/usr/bin/turbostat': Permission denied

Allow user to alter DESTDIR and PREFIX variables.
Signed-off-by: NAndy Shevchenko <andriy.shevchenko@linux.intel.com>
Signed-off-by: NRafael J. Wysocki <rafael.j.wysocki@intel.com>

trivial fix to spelling mistake

Link: http://lkml.kernel.org/r/1466672144-831-1-git-send-email-colin.king@canonical.comSigned-off-by: NColin Ian King <colin.king@canonical.com>
Acked-by: NChristoph Lameter <cl@linux.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

The write at the end of the test to restore nr_hugepages to its previous
value is failing.  This is because it is trying to write the number of
bytes in the char array as opposed to the number of bytes in the string.

Link: http://lkml.kernel.org/r/1465331205-3284-1-git-send-email-mike.kravetz@oracle.comSigned-off-by: NMike Kravetz <mike.kravetz@oracle.com>
Cc: Shuah Khan <shuahkh@osg.samsung.com>
Cc: Sri Jayaramappa <sjayaram@akamai.com>
Cc: Eric B Munson <emunson@akamai.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

When histograms are not configured in the kernel, the ftracetest histogram
selftests should return "unsupported" and not "Failed". To detect this, the
test scripts have:

 FEATURE=`grep hist events/sched/sched_process_fork/trigger`
 if [ -z "$FEATURE" ]; then
     echo "hist trigger is not supported"
     exit_unsupported
 fi

The problem is that '-e' is in effect and any error will cause the program
to terminate. The grep for 'hist' fails, because it is not compiled it (thus
unsupported), but because grep has an error code for failing to find the
string, it causes the program to terminate, and is marked as a failed test.

Namhyung Kim recommended to test for the "hist" file located in
events/sched/sched_process_fork/hist instead, as it is more inline with the
other checks. As the hist file is only created if the histogram feature is
enabled, that is a valid check.

Link: http://lkml.kernel.org/r/20160523151538.4ea9ce0c@gandalf.local.homeSuggested-by: NNamhyung Kim <namhyung@kernel.org>
Acked-by: NNamhyung Kim <namhyung@kernel.org>
Acked-by: NMasami Hiramatsu <mhiramat@kernel.org>
Fixes: 76929ab5 ("kselftests/ftrace: Add hist trigger testcases")
Signed-off-by: NSteven Rostedt <rostedt@goodmis.org>

This fixes the following compiler warnings when compiling the
reuseport_bpf testcase on a 32 bit platform:

reuseport_bpf.c: In function ‘attach_ebpf’:
reuseport_bpf.c:114:15: warning: cast from pointer to integer of ifferent size [-Wpointer-to-int-cast]
Signed-off-by: NHelge Deller <deller@gmx.de>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

Useful to measure testing framework overhead.
Signed-off-by: NMichael S. Tsirkin <mst@redhat.com>

/dev/cpu is only available on x86 with certain modules (e.g. msr) enabled.
Using lscpu to get processors count is more portable.
Signed-off-by: NMike Rapoport <rppt@linux.vnet.ibm.com>
Signed-off-by: NMichael S. Tsirkin <mst@redhat.com>

Having typical usage example in the README file is more convinient than in
the git history...
Signed-off-by: NMike Rapoport <rppt@linux.vnet.ibm.com>
Signed-off-by: NMichael S. Tsirkin <mst@redhat.com>

We observed some crazy apps on Android set their comm to unprintable
string. For example:

  # cat /proc/10607/task/*/comm
  tencent.qqmusic
  ...
  Binder_2
  日志输出线  <-- Chinese word 'log output thread'
  WifiManager
  ...

'perf data convert' fails to convert perf.data with such string to CTF format.

For example:

  # cat << EOF > ./badguy.c
  #include <sys/prctl.h>
  int main(int argc, char *argv[])
  {
         prctl(PR_SET_NAME, "\xe6\x97\xa5\xe5\xbf\x97\xe8\xbe\x93\xe5\x87\xba\xe7\xba\xbf");
         while(1)
                 sleep(1);
         return 0;
  }
  EOF
  # gcc ./badguy.c
  # perf record -e sched:* ./a.out
  # perf data convert --to-ctf ./bad.ctf
  CTF stream 4 flush failed
  [ perf data convert: Converted 'perf.data' into CTF data './bad.ctf' ]
  [ perf data convert: Converted and wrote 0.008 MB (78 samples)  ]
  # babeltrace ./bad.ctf/
  [error] Packet size (18446744073709551615 bits) is larger than remaining file size (262144 bits).
  [error] Stream index creation error.
  [error] Open file stream error.
  [warning] [Context] Cannot open_trace of format ctf at path ./bad.ctf.
  [warning] [Context] cannot open trace "./bad.ctf" from ./bad.ctf/ for reading.
  [error] Cannot open any trace for reading.

  [error] opening trace "./bad.ctf/" for reading.

  [error] none of the specified trace paths could be opened.

This patch converts unprintable characters to hexadecimal word.

After applying this patch the above test works correctly:

  # ~/perf data convert --to-ctf ./good.ctf
  [ perf data convert: Converted 'perf.data' into CTF data './good.ctf' ]
  [ perf data convert: Converted and wrote 0.008 MB (78 samples) ]
  # babeltrace ./good.ctf
  ..
  [23:14:35.491665268] (+0.000001100) sched:sched_wakeup: { cpu_id = 4 }, { perf_ip = 0xFFFFFFFF810AEF33, perf_tid = 0, perf_pid = 0, perf_id = 5123, perf_period = 1, common_type = 270, common_flags = 45, common_preempt_count = 4, common_pid = 0, comm = "\xe6\x97\xa5\xe5\xbf\x97\xe8\xbe\x93\xe5\x87\xba\xe7\xba\xbf", pid = 1057, prio = 120, success = 1, target_cpu = 4 }
  [23:14:35.491666230] (+0.000000962) sched:sched_wakeup: { cpu_id = 4 }, { perf_ip = 0xFFFFFFFF810AEF33, perf_tid = 0, perf_pid = 0, perf_id = 5122, perf_period = 1, common_type = 270, common_flags = 45, common_preempt_count = 4, common_pid = 0, comm = "\xe6\x97\xa5\xe5\xbf\x97\xe8\xbe\x93\xe5\x87\xba\xe7\xba\xbf", pid = 1057, prio = 120, success = 1, target_cpu = 4 }
  ..

Committer note:

To build perf with libabeltrace, use:

  $ mkdir -p /tmp/build/perf
  $ make LIBBABELTRACE=1 LIBBABELTRACE_DIR=/usr/local O=/tmp/build/perf -C tools/perf install-bin

Or equivalent (no O=, fixup LIBBABELTRACE_DIR, etc).
Signed-off-by: NWang Nan <wangnan0@huawei.com>
Tested-by: NArnaldo Carvalho de Melo <acme@redhat.com>
Cc: Jiri Olsa <jolsa@redhat.com>
Cc: pi3orama@163.com
Link: http://lkml.kernel.org/r/1464348951-179595-1-git-send-email-wangnan0@huawei.comSigned-off-by: NArnaldo Carvalho de Melo <acme@redhat.com>

Before this patch, a simple 'perf record' could fail if kptr_restrict is
set to 1 (for normal user) or 2 (for root):

  # perf record ls
  WARNING: Kernel address maps (/proc/{kallsyms,modules}) are restricted,
  check /proc/sys/kernel/kptr_restrict.

  Samples in kernel functions may not be resolved if a suitable vmlinux
  file is not found in the buildid cache or in the vmlinux path.

  Samples in kernel modules won't be resolved at all.

  If some relocation was applied (e.g. kexec) symbols may be misresolved
  even with a suitable vmlinux or kallsyms file.

  Segmentation fault (core dumped)

This patch skips perf_event__synthesize_kernel_mmap() when kptr is not
available.
Signed-off-by: NWang Nan <wangnan0@huawei.com>
Tested-by: NArnaldo Carvalho de Melo <acme@redhat.com>
Fixes: 45e90056 ("perf machine: Do not bail out if not managing to read ref reloc symbol")
Cc: Zefan Li <lizefan@huawei.com>
Cc: pi3orama@163.com
Link: http://lkml.kernel.org/r/1464081688-167940-2-git-send-email-wangnan0@huawei.comSigned-off-by: NArnaldo Carvalho de Melo <acme@redhat.com>

If kptr_restrict is set to 2, even root is not allowed to see pointers.
This patch checks kptr_restrict even if euid == 0. For root, report
error if kptr_restrict is 2.
Signed-off-by: NWang Nan <wangnan0@huawei.com>
Tested-by: NArnaldo Carvalho de Melo <acme@redhat.com>
Cc: Zefan Li <lizefan@huawei.com>
Cc: pi3orama@163.com
Link: http://lkml.kernel.org/r/1464081688-167940-1-git-send-email-wangnan0@huawei.comSigned-off-by: NArnaldo Carvalho de Melo <acme@redhat.com>

A lot of the code works with the perf events about which only sparse
documentation was available until 2012. Having that information now,
we can clarify what is done in the code.
Signed-off-by: NJanosch Frank <frankja@linux.vnet.ibm.com>
Signed-off-by: NPaolo Bonzini <pbonzini@redhat.com>

Having stats for single VMs can help to determine the problem of a VM
without the need of running other tools like perf.

The tracepoints already allowed pid level monitoring, but kvm_stat
didn't have support for it till now. Support for the newly implemented
debugfs vm monitoring was also implemented.
Signed-off-by: NJanosch Frank <frankja@linux.vnet.ibm.com>
Signed-off-by: NPaolo Bonzini <pbonzini@redhat.com>

kvm_stat script is failing to execute on powerpc :
 # ./kvm_stat
Traceback (most recent call last):
  File "./kvm_stat", line 825, in <module>
    main()
  File "./kvm_stat", line 813, in main
    providers = get_providers(options)
  File "./kvm_stat", line 778, in get_providers
    providers.append(TracepointProvider())
  File "./kvm_stat", line 416, in __init__
    self.filters = get_filters()
  File "./kvm_stat", line 315, in get_filters
    if ARCH.exit_reasons:
AttributeError: 'ArchPPC' object has no attribute 'exit_reasons'

This is because, its trying to access a non-defined attribute.

Also, the IOCTL number of RESET is incorrect for powerpc. The correct
number has been added.
Signed-off-by: NHemant Kumar <hemant@linux.vnet.ibm.com>
Signed-off-by: NPaolo Bonzini <pbonzini@redhat.com>

Converted from the Texinfo source in QEMU to asciidoc.  The a2x
incantation was provided by Janosch Frank.
Signed-off-by: NPaolo Bonzini <pbonzini@redhat.com>

This tool displays kvm vm exit statistics to ease vm monitoring. It
takes its data from the kvm debugfs files or the vm tracepoints and
outputs them as a curses ui or simple text.

It was moved from qemu, as it is dependent on the kernel whereas qemu
works with a large number of kernel versions, some of which may break
the script.
Signed-off-by: NJanosch Frank <frankja@linux.vnet.ibm.com>
Signed-off-by: NPaolo Bonzini <pbonzini@redhat.com>

Introduce rb_find_range() to find start and end position from a backward
ring buffer.
Signed-off-by: NWang Nan <wangnan0@huawei.com>
Cc: Jiri Olsa <jolsa@kernel.org>
Cc: Masami Hiramatsu <masami.hiramatsu.pt@hitachi.com>
Cc: Namhyung Kim <namhyung@kernel.org>
Cc: Zefan Li <lizefan@huawei.com>
Cc: pi3orama@163.com
Link: http://lkml.kernel.org/r/1463987628-163563-5-git-send-email-wangnan0@huawei.comSigned-off-by: NHe Kuang <hekuang@huawei.com>
Signed-off-by: NArnaldo Carvalho de Melo <acme@redhat.com>

record__mmap_read() writes data from ring buffer into perf.data.  'head'
is maintained by the kernel, points to the last written record.
'old' is maintained by perf, points to the record read in previous
round. record__mmap_read() saves data from 'old' to 'head' to
perf.data.

The names of these variables are not very intutive. In addition,
when dealing with backward writing ring buffer, the md->prev pointer
should point to 'head' instead of the last byte it got.

Add 'start' and 'end' pointer to make code clear and set md->prev to
'head' instead of the moved 'old' pointer. This patch doesn't change
behavior since:

    buf = &data[old & md->mask];
    size = head - old;
    old += size;     <--- Here, old == head
Signed-off-by: NWang Nan <wangnan0@huawei.com>
Cc: Jiri Olsa <jolsa@kernel.org>
Cc: Masami Hiramatsu <masami.hiramatsu.pt@hitachi.com>
Cc: Namhyung Kim <namhyung@kernel.org>
Cc: Zefan Li <lizefan@huawei.com>
Cc: pi3orama@163.com
Link: http://lkml.kernel.org/r/1463987628-163563-4-git-send-email-wangnan0@huawei.comSigned-off-by: NHe Kuang <hekuang@huawei.com>
Signed-off-by: NArnaldo Carvalho de Melo <acme@redhat.com>

When record__mmap_read() requires data more than the size of ring
buffer, drop those data to avoid accessing invalid memory.

This can happen when reading from overwritable ring buffer, which
should be avoided. However, check this for robustness.
Signed-off-by: NWang Nan <wangnan0@huawei.com>
Cc: Jiri Olsa <jolsa@kernel.org>
Cc: Masami Hiramatsu <masami.hiramatsu.pt@hitachi.com>
Cc: Namhyung Kim <namhyung@kernel.org>
Cc: Zefan Li <lizefan@huawei.com>
Cc: pi3orama@163.com
Link: http://lkml.kernel.org/r/1463987628-163563-3-git-send-email-wangnan0@huawei.comSigned-off-by: NHe Kuang <hekuang@huawei.com>
Signed-off-by: NArnaldo Carvalho de Melo <acme@redhat.com>

perf_evlist__toggle_{pause,resume}() are introduced to pause/resume
events in an evlist. Utilize PERF_EVENT_IOC_PAUSE_OUTPUT ioctl.

Following commits use them to ensure overwrite ring buffer is paused
before reading.
Signed-off-by: NWang Nan <wangnan0@huawei.com>
Cc: Jiri Olsa <jolsa@kernel.org>
Cc: Masami Hiramatsu <masami.hiramatsu.pt@hitachi.com>
Cc: Namhyung Kim <namhyung@kernel.org>
Cc: Zefan Li <lizefan@huawei.com>
Cc: pi3orama@163.com
Link: http://lkml.kernel.org/r/1463987628-163563-2-git-send-email-wangnan0@huawei.comSigned-off-by: NHe Kuang <hekuang@huawei.com>
[ Return -1, like all other ioctl() usage in evlist.c, rename 'pause'
  arg to avoid breaking the build on ubuntu 12.04 and other old systems ]
Signed-off-by: NArnaldo Carvalho de Melo <acme@redhat.com>

Auto-attach the ptr->name beautifier to syscall args "filename", "path"
and "pathname" if they are of type "const char *".

Cc: Adrian Hunter <adrian.hunter@intel.com>
Cc: David Ahern <dsahern@gmail.com>
Cc: Jiri Olsa <jolsa@kernel.org>
Cc: Milian Wolff <milian.wolff@kdab.com>
Cc: Namhyung Kim <namhyung@kernel.org>
Cc: Wang Nan <wangnan0@huawei.com>
Link: http://lkml.kernel.org/n/tip-jxii4qmcgoppftv0zdvml9d7@git.kernel.orgSigned-off-by: NArnaldo Carvalho de Melo <acme@redhat.com>

Noticed when the 'setsockopt' 'fd' arg wasn't being formatted via
the SCA_FD beautifier, so just remove the setting of "fd" args to
SCA_FD and do it when reading the syscall info, like we do for
args of type "pid_t", i.e. "fd" as the name should be enough as
the decision to use the SFA_FD beautifier. For odd cases we can
just do it explicitely.

Cc: Adrian Hunter <adrian.hunter@intel.com>
Cc: David Ahern <dsahern@gmail.com>
Cc: Jiri Olsa <jolsa@kernel.org>
Cc: Milian Wolff <milian.wolff@kdab.com>
Cc: Namhyung Kim <namhyung@kernel.org>
Cc: Wang Nan <wangnan0@huawei.com>
Link: http://lkml.kernel.org/n/tip-0qissgetiuqmqyj4b6ancmpn@git.kernel.orgSigned-off-by: NArnaldo Carvalho de Melo <acme@redhat.com>

Add "srcline_from" and "srcline_to" branch sort keys that allow to show
the source lines of a branch.

That makes it much easier to track down where particular branches happen
in the program, for example to examine branch mispredictions, or to
associate it with cycle counts:

  % perf record -b -e cycles:p ./tcall
  % perf report --sort srcline_from,srcline_to,mispredict
  ...
    15.10%  tcall.c:18       tcall.c:10       N
    14.83%  tcall.c:11       tcall.c:5        N
    14.12%  tcall.c:7        tcall.c:12       N
    14.04%  tcall.c:12       tcall.c:5        N
    12.42%  tcall.c:17       tcall.c:18       N
    12.39%  tcall.c:7        tcall.c:13       N
    12.27%  tcall.c:13       tcall.c:17       N
  ...

  % perf report --sort srcline_from,srcline_to,cycles
  ...
    17.12%  tcall.c:18       tcall.c:11       1
    17.01%  tcall.c:12       tcall.c:6        1
    16.98%  tcall.c:11       tcall.c:6        1
    15.91%  tcall.c:17       tcall.c:18       1
     6.38%  tcall.c:7        tcall.c:17       7
     4.80%  tcall.c:7        tcall.c:12       8
     4.21%  tcall.c:7        tcall.c:17       8
     2.67%  tcall.c:7        tcall.c:12       7
     2.62%  tcall.c:7        tcall.c:12       10
     2.10%  tcall.c:7        tcall.c:17       9
     1.58%  tcall.c:7        tcall.c:12       6
     1.44%  tcall.c:7        tcall.c:12       5
     1.38%  tcall.c:7        tcall.c:12       9
     1.06%  tcall.c:7        tcall.c:17       13
     1.05%  tcall.c:7        tcall.c:12       4
     1.01%  tcall.c:7        tcall.c:17       6

Open issues:

- Some kernel symbols get misresolved.
Signed-off-by: NAndi Kleen <ak@linux.intel.com>
Acked-by: NJiri Olsa <jolsa@kernel.org>
Tested-by: NArnaldo Carvalho de Melo <acme@redhat.com>
Link: http://lkml.kernel.org/r/1463775308-32748-1-git-send-email-andi@firstfloor.orgSigned-off-by: NArnaldo Carvalho de Melo <acme@redhat.com>

Half of the test in instance-event.tc was updated to use $! to find the PID
of the previous background process that was launched, but the second part of
the test still used the parsing of "jobs", which does not work on all shells
like $! does.
Signed-off-by: NSteven Rostedt <rostedt@goodmis.org>

Do not hardcode MAP_HUGETLB to 0x40000, since quite some architectures
use a different value.

Tested with a parisc architecture 64bit kernel.
Signed-off-by: NHelge Deller <deller@gmx.de>

By adding TRACEHOOK support we now get a clean user interface to access
registers via PTRACE_GETREGS, PTRACE_SETREGS, PTRACE_GETFPREGS and
PTRACE_SETFPREGS.

The user-visible regset struct user_regs_struct and user_fp_struct are
modelled similiar to x86 and can be accessed via PTRACE_GETREGSET.
Signed-off-by: NHelge Deller <deller@gmx.de>

just a stub pointer for now.
Signed-off-by: NMichael S. Tsirkin <mst@redhat.com>

skips ring accesses but drops out of order support
Signed-off-by: NMichael S. Tsirkin <mst@redhat.com>

Device DAX is the device-centric analogue of Filesystem DAX
(CONFIG_FS_DAX).  It allows memory ranges to be allocated and mapped
without need of an intervening file system.  Device DAX is strict,
precise and predictable.  Specifically this interface:

1/ Guarantees fault granularity with respect to a given page size (pte,
pmd, or pud) set at configuration time.

2/ Enforces deterministic behavior by being strict about what fault
scenarios are supported.

For example, by forcing MADV_DONTFORK semantics and omitting MAP_PRIVATE
support device-dax guarantees that a mapping always behaves/performs the
same once established.  It is the "what you see is what you get" access
mechanism to differentiated memory vs filesystem DAX which has
filesystem specific implementation semantics.

Persistent memory is the first target, but the mechanism is also
targeted for exclusive allocations of performance differentiated memory
ranges.

This commit is limited to the base device driver infrastructure to
associate a dax device with pmem range.

Cc: Jeff Moyer <jmoyer@redhat.com>
Cc: Christoph Hellwig <hch@lst.de>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Dave Hansen <dave.hansen@linux.intel.com>
Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
Reviewed-by: NJohannes Thumshirn <jthumshirn@suse.de>
Signed-off-by: NDan Williams <dan.j.williams@intel.com>

Convert radix_tree_next_chunk to use 'child' instead of 'slot' as the
name of the child node.  Also use node_maxindex() where it makes sense.

The 'rnode' variable was unnecessary; it doesn't overlap in usage with
'node', so we can just use 'node' the whole way through the function.

Improve the testcase to start the walk from every index in the carefully
constructed tree, and to accept any index within the range covered by
the entry.
Signed-off-by: NMatthew Wilcox <willy@linux.intel.com>
Cc: Konstantin Khlebnikov <koct9i@gmail.com>
Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
Cc: Jan Kara <jack@suse.com>
Cc: Neil Brown <neilb@suse.de>
Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

As with indirect_to_ptr(), ptr_to_indirect() and
RADIX_TREE_INDIRECT_PTR, change radix_tree_is_indirect_ptr() to
radix_tree_is_internal_node().
Signed-off-by: NMatthew Wilcox <willy@linux.intel.com>
Cc: Konstantin Khlebnikov <koct9i@gmail.com>
Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
Cc: Jan Kara <jack@suse.com>
Cc: Neil Brown <neilb@suse.de>
Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

Mirrors the earlier commit introducing node_to_entry().

Also change the type returned to be a struct radix_tree_node pointer.
That lets us simplify a couple of places in the radix tree shrink &
extend paths where we could convert an entry into a pointer, modify the
node, then convert the pointer back into an entry.
Signed-off-by: NMatthew Wilcox <willy@linux.intel.com>
Cc: Konstantin Khlebnikov <koct9i@gmail.com>
Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
Cc: Jan Kara <jack@suse.com>
Cc: Neil Brown <neilb@suse.de>
Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

verify_node() can use node->shift instead of the height.

tree_verify_min_height() can be converted over to using node_maxindex()
and shift_maxindex() instead of radix_tree_maxindex().
Signed-off-by: NMatthew Wilcox <willy@linux.intel.com>
Cc: Konstantin Khlebnikov <koct9i@gmail.com>
Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
Cc: Jan Kara <jack@suse.com>
Cc: Neil Brown <neilb@suse.de>
Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

 - Print which indices are covered by every leaf entry
 - Print sibling entries
 - Print the node pointer instead of the slot entry
 - Build by default in userspace, and make it accessible to the test-suite
Signed-off-by: NRoss Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: NMatthew Wilcox <willy@linux.intel.com>
Cc: Konstantin Khlebnikov <koct9i@gmail.com>
Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
Cc: Jan Kara <jack@suse.com>
Cc: Neil Brown <neilb@suse.de>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

I had previously decided that tagging a single multiorder entry would
count as tagging 2^order entries for the purposes of 'nr_to_tag'.  I now
believe that decision to be a mistake, and it should count as a single
entry.  That's more likely to be what callers expect.

When walking back up the tree from a newly-tagged entry, the current
code assumed we were starting from the lowest level of the tree; if we
have a multiorder entry with an order at least RADIX_TREE_MAP_SHIFT in
size then we need to shift the index by 'shift' before we start walking
back up the tree, or we will end up not setting tags on higher entries,
and then mistakenly thinking that entries below a certain point in the
tree are not tagged.

If the first index we examine is a sibling entry of a tagged multiorder
entry, we were not tagging it.  We need to examine the canonical entry,
and the easiest way to do that is to use radix_tree_descend().  We then
have to skip over sibling slots when looking for the next entry in the
tree or we will end up walking back to the canonical entry.

Add several tests for radix_tree_range_tag_if_tagged().
Signed-off-by: NMatthew Wilcox <willy@linux.intel.com>
Reviewed-by: NRoss Zwisler <ross.zwisler@linux.intel.com>
Cc: Konstantin Khlebnikov <koct9i@gmail.com>
Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
Cc: Jan Kara <jack@suse.com>
Cc: Neil Brown <neilb@suse.de>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

Add a unit test that provides coverage for the bug fixed in the commit
entitled "radix-tree: rewrite radix_tree_locate_item fix" from Hugh
Dickins.  I've verified that this test fails before his patch due to
miscalculated 'index' values in __locate() in lib/radix-tree.c, and
passes with his fix.

Link: http://lkml.kernel.org/r/1462307263-20623-1-git-send-email-ross.zwisler@linux.intel.comSigned-off-by: NRoss Zwisler <ross.zwisler@linux.intel.com>
Cc: Hugh Dickins <hughd@google.com>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

Use the new multi-order support functions to rewrite
radix_tree_locate_item().  Modify the locate tests to test multiorder
entries too.

[hughd@google.com: radix_tree_locate_item() is often returning the wrong index]
  Link: http://lkml.kernel.org/r/alpine.LSU.2.11.1605012108490.1166@eggly.anvilsSigned-off-by: NMatthew Wilcox <willy@linux.intel.com>
Reviewed-by: NRoss Zwisler <ross.zwisler@linux.intel.com>
Cc: Konstantin Khlebnikov <koct9i@gmail.com>
Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
Cc: Jan Kara <jack@suse.com>
Cc: Neil Brown <neilb@suse.de>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

If the radix tree user attempted to insert a colliding entry with an
existing multiorder entry, then radix_tree_create() could encounter a
sibling entry when walking down the tree to look for a slot.  Use
radix_tree_descend() to fix the problem, and add a test-case to make
sure the problem doesn't come back in future.
Signed-off-by: NMatthew Wilcox <willy@linux.intel.com>
Reviewed-by: NRoss Zwisler <ross.zwisler@linux.intel.com>
Cc: Konstantin Khlebnikov <koct9i@gmail.com>
Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
Cc: Jan Kara <jack@suse.com>
Cc: Neil Brown <neilb@suse.de>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

Add a generic test for multi-order tag verification, and call it using
several different configurations.

This test creates a multi-order radix tree using the given index and
order, and then sets, checks and clears tags using the indices covered
by the single multi-order radix tree entry.

With the various calls done by this test we verify root multi-order
entries without siblings, multi-order entries without siblings in a
radix tree node, as well as multi-order entries with siblings of various
sizes.
Signed-off-by: NRoss Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: NMatthew Wilcox <willy@linux.intel.com>
Cc: Konstantin Khlebnikov <koct9i@gmail.com>
Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
Cc: Jan Kara <jack@suse.com>
Cc: Neil Brown <neilb@suse.de>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

Add a unit test to verify that we can iterate over multi-order entries
properly via a radix_tree_for_each_slot() loop.

This was done with a single, somewhat complicated configuration that was
meant to test many of the various corner cases having to do with
multi-order entries:

- An iteration could begin at a sibling entry, and we need to return the
  canonical entry.
- We could have entries of various orders in the same slots[] array.
- We could have multi-order entries at a nonzero height, followed by
  indirect pointers to more radix tree nodes later in that same slots[]
  array.
Signed-off-by: NRoss Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: NMatthew Wilcox <willy@linux.intel.com>
Cc: Konstantin Khlebnikov <koct9i@gmail.com>
Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
Cc: Jan Kara <jack@suse.com>
Cc: Neil Brown <neilb@suse.de>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>