tools: add tool to detect potential deadlocks in running programs

`deadlock_detector` is a new tool to detect potential deadlocks (lock order
inversions) in a running process. The program attaches uprobes on
`pthread_mutex_lock` and `pthread_mutex_unlock` to build a mutex wait directed
graph, and then looks for a cycle in this graph. This graph has the following
properties:

- Nodes in the graph represent mutexes.
- Edge (A, B) exists if there exists some thread T where lock(A) was called
  and lock(B) was called before unlock(A) was called.

If there is a cycle in this graph, this indicates that there is a lock order
inversion (potential deadlock). If the program finds a lock order inversion, the
program will dump the cycle of mutexes, dump the stack traces where each mutex
was acquired, and then exit.

The format of the output uses a similar output as ThreadSanitizer (See example:
https://github.com/google/sanitizers/wiki/ThreadSanitizerDeadlockDetector)

This program can only find potential deadlocks that occur while the program is
tracing the process. It cannot find deadlocks that may have occurred before the
program was attached to the process.

If the traced process has many mutexes and threads, this program will add a
very large overhead because every mutex lock/unlock and clone call will be
traced. This tool is meant for debugging only, and you should run this tool
only on programs where the slowdown is acceptable.

Note: This tool adds a dependency on `networkx` for the graph libraries
(building a directed graph and cycle detection).

Note: This tool does not work for shared mutexes or recursive mutexes.

For shared (read-write) mutexes, a deadlock requires a cycle in the wait
graph where at least one of the mutexes in the cycle is acquiring exclusive
(write) ownership.

For recursive mutexes, lock() is called multiple times on the same mutex.
However, there is no way to determine if a mutex is a recursive mutex
after the mutex has been created. As a result, this tool will not find
potential deadlocks that involve only one mutex.

Merge pull request #928 from goldshtn/tp-data-loc

Support for __data_loc tracepoint fields

tplist: Don't ignore __data_loc fields

tests: Add test for TP_DATA_LOC_READ_CONST

cc: Support for __data_loc tracepoint fields

`__data_loc` fields are dynamically sized by the kernel at
runtime. The field data follows the tracepoint structure entry,
and needs to be extracted in a special way. The `__data_loc` field
itself is a 32-bit value that consists of two 16-bit parts: the
high 16 bits are the length of the data, and the low 16 bits are
the offset of the data from the beginning of the tracepoint
structure. From a cursory look, there are >200 tracepoints in
recent kernels that have this kind of field.

This patch fixes `tp_frontend_action.cc` to recognize and emit
`__data_loc` fields correctly, as 32-bit opaque fields. Then, it
introduces two helper macros:

`TP_DATA_LOC_READ(dst, field)` reads from `args->field` by finding
the right offset and length and emitting the `bpf_probe_read`
required to fetch the data. This will only work with new kernels.

`TP_DATA_LOC_READ_CONST(dst, field, length)` takes a user-specified
length rather than finding it from `args->field`. This will work
on older kernels, where the BPF verifier doesn't allow non-constant
sizes to be passed to `bpf_probe_read`.

Merge pull request #918 from derek0883/mybcc

Handling multiple concurrent probe users.

enum bpf_probe_attach_type to CAPITAL

undo rebase

Merge pull request #927 from rnav/powerpc-fixes

powerpc: update the build triplet

powerpc: update the build triplet

The more commonly used triplet on ppc64le happens to be
powerpc64le-unknown-linux-gnu. The existing one causes problems in
certain build environments. Change this.

While at it, also include support for building on big endian.

Reported-by: Anton Blanchard <anton@samba.org>
Signed-off-by: Naveen N. Rao <naveen.n.rao@linux.vnet.ibm.com>

Merge branch 'mybcc' of https://github.com/derek0883/bcc into mybcc

keep 'enum bpf_attach_type' inside libbpf.h, renamed it to bpf_probe_attach_type
using static buf size in libbpf.c. for uprobe, set buf size to PATH_MAX

Fixed test case test_trace4.py error

Handling multiple concurrent probe users.
    remove event_desc from front-end, handle it inside libbpf
    Event naming pattern changed to $(eventname)_bcc_$(pid)

rename event_name for lua

rename event name in detach_uprobe/detach_uretprobe

rename event name in detach_kprobe/detach_kretprobe

Handling multiple concurrent probe users.
Event naming pattern changed to $(eventname)_bcc_$(pid)
Detect /sys/kernel/debug/tracing/instances in bpf_attach_probe,
if it exist, then will per-instance event, if failed the make global
event instance as same as before.

Merge pull request #926 from goldshtn/argdist-pid-fix

argdist: Fix -p behavior to filter tgid and not pid

Merge pull request #925 from goldshtn/cpudist-import-fix

cpudist: remove unused Tracepoint import

argdist: Fix -p behavior to filter tgid and not pid

argdist remained one of the last holdouts to use the `-p` switch
inconsistently with other tools, filtering for kernel pid (thread
id from user space perspective) and not kernel tgid (process id
from user space perspective). This is now fixed.

Additionally, minor nits around generating pid filters were fixed,
and a potential collision with user-provided argument names was
fixed too (in general, script-generated arguments/locals should
probably stick to reserved identifiers, such as `__whatever` rather
than `whatever`).

cpudist: remove unused Tracepoint import

Fixed test case test_trace4.py error

Handling multiple concurrent probe users.
    remove event_desc from front-end, handle it inside libbpf
    Event naming pattern changed to $(eventname)_bcc_$(pid)

rename event_name for lua

rename event name in detach_uprobe/detach_uretprobe

rename event name in detach_kprobe/detach_kretprobe

Handling multiple concurrent probe users.
Event naming pattern changed to $(eventname)_bcc_$(pid)
Detect /sys/kernel/debug/tracing/instances in bpf_attach_probe,
if it exist, then will per-instance event, if failed the make global
event instance as same as before.

Merge pull request #913 from iovisor/python23_percpu

Fix python2/3 incompatible percpu helpers

Skip percpu testing on unsupported kernels

Signed-off-by: Brenden Blanco <bblanco@gmail.com>

Support for hotplug cpu cases in percpu array sizing

The kernel uses number of possible cpus to size the leaf, not the num of
online cpus. Fixup the python side appropriately.
Update: use num_possible_cpus() helper instead

Signed-off-by: Brenden Blanco <bblanco@gmail.com>

Fix python2/3 incompatible percpu helpers

The python3 version of the percpu helpers (average, sum, etc.) were
using a python2 function that has since moved to functools (reduce).

Worse, the test case for percpu functionality was not enabled in the
cmake file. Better turn that on and make it work.

Signed-off-by: Brenden Blanco <bblanco@gmail.com>

Merge pull request #914 from mkacik/master

[tools][memleak.py] add parameter for specifying object to load malloc/free from

[memleak] add parameter for specifying object to load malloc/free from

Merge pull request #911 from goldshtn/trace-params-signature

trace: Allow function signatures in uprobes and kprobes

Merge pull request #909 from goldshtn/tp-str-fixes

trace, tplist, argdist: UDST probe miscellaneous fixes

trace: Allow function signatures in uprobes and kprobes

§`trace` now allows uprobes and kprobes to have function signatures,
which means function parameters can be named and typed, rather than
relying on the positional arg1, arg2, etc. arguments. This also
enables structure field access, which is impossible with the unnamed
arguments due to rewriter limitations.

The example requested by @brendangregg, which now works, is the
following:

§Â```
PID    TID    COMM         FUNC             -
777    785    automount    SyS_nanosleep    sleep for 500000000 ns
777    785    automount    SyS_nanosleep    sleep for 500000000 ns
777    785    automount    SyS_nanosleep    sleep for 500000000 ns
777    785    automount    SyS_nanosleep    sleep for 500000000 ns
^C
```

trace, argdist: Fix code formatting nits

trace: Use correct argument index and tgid for filters

`trace` would use the incorrect argument index for USDT probes when
filtering specifically, e.g. `trace u:lib:tp (arg1 != 0) ...` would
actually use the type of the 2nd argument, and not the 1st argument
for the type of the filter variable in the generated program. This
could cause compilation errors or subtle bugs where the data would
be either extended or contracted to fit the wrong argument's type.

Additionally, `trace` would use the pid (thread id, `-L`) filter
with the `attach_uprobe` API, which expects a tgid (process id).
As a result, incorrect filtering would happen.

trace: Generated streq-helper to ignore null terminator

argdist: Generated streq-helper to ignore null terminator

Oftentimes we want to use the STRCMP helper to compare strings that
are not null-terminated, e.g. in USDT probes this often happens.
Ignore the null terminator (i.e. loop until the last character
excluding the null terminator).

tplist: Print one-based location and argument indices

The `trace` and `argdist` tools expect location and argument indices
to start at 1 -- the first argument is arg1, and so on. The `tplist`
tool now prints UDST argument indices (and location indices, for
consistency) as 1-based as well.

Merge pull request #875 from pchaigno/target-process-library

Use targeted process to resolve library names

Merge pull request #908 from Catalysts/cpu-iteration

fix iteration over CPUs

fix iteration over CPUs

Since kernel version 4.9.0 BPF stopped working in a KVM guest.
The problem are calls to perf_event_open with CPU identifiers which do
not exist (ENODEV). The root cause for this is that the current code
assumes ascending numbered CPUs. However, this is not always the case
(e.g. CPU hotplugging).

This patch introduces the get_online_cpus() and get_possible_cpus()
helper functions and uses the appropriate function for iterations over
CPUs. The BPF_MAP_TYPE_PERF_EVENT_ARRAY map contains now an entry for
each possible CPU instead of for each online CPU.

Fixes: #893
Signed-off-by: Andreas Gerstmayr <andreas.gerstmayr@catalysts.cc>

Merge pull request #906 from goldshtn/valid-idents

argdist, trace: Support non-C identifier names

cc: Dynamically allocate memory for library path

cc: Use PID to detach uprobes

We need the PID when detaching uprobes to resolve library names
to the same path as when attaching

cc: Resolve library names using loaded libraries

To resolve library names, bcc_procutils_which_so leverages mapped
libraries of the targeted process, if one is given. Uses the kernel's
/proc/$pid/maps

argdist, trace: Support non-C identifier names

When argdist or trace face a function that has characters
in its name that are not valid in C identifier, they now
replace these characters with an underscore (`_`) when
generating function names and structure names to include
in the BPF program. As a result, it is now possible to
trace functions that have these identifiers in their names,
such as Golang functions like `fmt.Println`.

Merge pull request #904 from brendangregg/master

add some error hints

add some error hints

Merge pull request #899 from brendangregg/tool2

profile: increase unique stack default to 10k

Merge pull request #896 from brendangregg/tool1

trace: allow tracing of functions containing a dot (golang)

Merge pull request #897 from brendangregg/master

statsnoop: refactor

profile: increase unique stack default to 10k

statsnoop: refactor

Merge pull request #895 from brendangregg/master

gethostlatency: remove unused code

trace: allow tracing of functions containing a dot (golang)

gethostlatency: remove unused code

Merge pull request #894 from brendangregg/master

add a few funccount examples

add a few funccount examples

Merge pull request #883 from ColinIanKing/master

snapcraft: add cpuunclaimed to snapcraft wrapper rules

Merge pull request #890 from mvbpolito/add_helpers

Add missing helper prototypes

Merge pull request #889 from totally/preprocess_4.10

Fixes bio{snoop,top} on 4.10

Add missing helpers prototypes in helpers.h

Signed-off-by: Mauricio Vasquez B <mauricio.vasquez@polito.it>

Fixes bio{snoop,top} on 4.10.

This commit fixes #888.  The 2 scripts run the same check, and now run
basically the same code to do it.

Tested on 4.10-rc2.

Merge pull request #887 from rneugeba/cflags

Add -fno-stack-protector to CFLAGS

Add -fno-stack-protector to CFLAGS

When compiling ebpf programs on Alpine Linux the compiler throws the following
error:

LLVM ERROR: Cannot select: 0x56049b79dcb0: ch,glue = BPFISD::CALL 0x56049a93ad60, TargetExternalSymbol:i64'__stack_chk_fail'
  0x56049b391500: i64 = TargetExternalSymbol'__stack_chk_fail'
    In function: waker

Disabling the stack protector explicitly with '-fno-stack-protector'
fixes this error.

clang version 3.8.1 (tags/RELEASE_381/final)
Target: x86_64-alpine-linux-musl
Thread model: posix
InstalledDir: /usr/bin

Signed-off-by: Rolf Neugebauer <rolf.neugebauer@docker.com>

Merge pull request #882 from mvbpolito/master

add missing inclusion guards in bcc/proto.h

Merge branch 'master' into master

Merge pull request #886 from iovisor/llvm_40_fixes

Fixes for LLVM 4.0 and python3

Fixes for LLVM 4.0 and python3

Avoid conflicting [no]inline attributes in function annotation. This was
probably always there but now 4.0 is treating this as an error.
Also, explicitly inline several functions in helpers.h.

Turn off unwind tables in the flags passed to clang. This was generating
calls to the elf relocator, which doesn't work for the BPF target. It is
unclear which change in LLVM 4.0 altered this behavior.

On python3, handle byte strings in the usual way for supporting
backwards compatibility.

Signed-off-by: Brenden Blanco <bblanco@gmail.com>

snapcraft.yaml: fix typo in ttysnoop wrapper

fix stupid typo in wrapper: ttysnop -> ttysnoop

Signed-off-by: Colin Ian King <colin.king@canonical.com>

snapcraft: add cpuunclaimed to snapcraft wrapper rules

Signed-off-by: Colin Ian King <colin.king@canonical.com>

Merge pull request #878 from iovisor/compat-4.10-update

Update [virtual_]bpf.h to 4.10

add missing inclusion guards in bcc/proto.h

Signed-off-by: Mauricio Vasquez B <mauricio.vasquez@polito.it>

Use compat bpf_common.h for local clang build

Only the virtual_bpf.h should point to the installed kernel headers.

Signed-off-by: Brenden Blanco <bblanco@gmail.com>

Update [virtual_]bpf.h to 4.10

As is occassionally necessary, we need to update the compat header
files for new kernels. This picks up the bpf.h from 4.10rc1.

Fixes: #877
Signed-off-by: Brenden Blanco <bblanco@gmail.com>

Merge pull request #874 from pchaigno/fix-var

Fix variable names in exceptions

Fix variable name

Merge pull request #870 from brendangregg/master

add cpuunclaimed

fix comment in runqlen

add cpuunclaimed

Merge pull request #835 from ColinIanKing/master

Add snapcraft script to package up bcc as a snap

Merge pull request #867 from shodoco/extern

Don't close extern table when a module destructs

fix company copyright

Merge pull request #868 from shodoco/pin

add bpf_obj_pin/bpf_obj_get to pin/get bpf objects

add bpf_obj_pin/bpf_obj_get to pin/get bpf objects

do not close extern table when a module destructs

add table type to shared tables

Merge pull request #863 from shodoco/master

support macro in call arguments

Merge branch 'master' into master

Merge pull request #865 from goldshtn/trace-timestamp

trace: -L, -t, -T switches

Merge pull request #774 from goldshtn/usdt-tools

USDT tools for higher level languages

trace: -L, -t, -T switches

The `-t` switch for specifying a thread id has been renamed
to `-L`. The `-T` switch specifies that a time column should
be provided, whereas the `-t` switch requests a relative
timestamp (from the beginning of the trace). This is more
consistent with other tools, and lets the user choose the
desired format for the time column, if any.

uobjnew: Remove -l switch from examples

uobjnew: Attach uprobe only to the requested process

When C allocations are traced, attach the `malloc`
uprobe only to the requested process -- otherwise, we
get allocation information from the entire system.

README: Add u* tools based on USDT probes

uflow: Add man page and companion examples file