graphrecord.sh

#!/usr/bin/env bash
#
# Script to record a callgraph with perf. The script generates the following
# files:
#
#  - Always:
#     perf.data: Recording of the specified events.
#  - if -r:
#     OUT_FILE.report: ASCII values from perf record with specified fields
#
# Perf sampling mode
# ------------------
#
# Perf_events is based on event-based sampling. The period is expressed as
# the number of occurrences of an event, not the number of timer ticks. A
# sample is recorded when the sampling counter overflows, i.e., wraps
# from 2^64 back to 0. No PMU implements 64-bit hardware counters, but
# perf_events emulates such counters in software. [6]
#
# Interrupt-based sampling introduces skids on modern processors. That means
# that the instruction pointer stored in each sample designates the place
# where the program was interrupted to process the PMU interrupt, not the
# place where the counter actually overflows, i.e., where it was at the end
# of the sampling period. In some case, the distance between those two points
# may be several dozen instructions or more if there were taken branches.
# When the program cannot make forward progress, those two locations are
# indeed identical. For this reason, care must be taken when interpreting
# profiles. [6]
#
# In addition, the number of reported samples is only an estimate. It does
# not reflect the actual number of samples collected. The estimate is based
# on the number of bytes written to the perf.data file and the minimal
# sample size. But the size of each sample depends on the type of measurement.
# Some samples are generated by the counters themselves but others are
# recorded to support symbol correlation during post-processing,
# e.g., mmap() information. [6]
#
# Callgraph Method
# ----------------
# The used default value for the --call-graph flag is dwarf with the maximum
# allowed stack-size.
#
# Another options would be LBR (Last Branch Recording) which uses special
# registers to record the caller and callee information from which a callgraph
# or control flow can be build. [2] In additon it provides the perf
# functionality to filter for specific branches. [4]
#
# However, lbr is a) generating more information but doesn't provide as deep
# a callgraph as the dwarf format and b) it can only be used for userspace
# call chains and doesnt work with branch stack sampling (see
# [1, 5.4.3 Collecting Call Stacks]; `man perf-record`, under --call-graph).
#
# Another method is to use the Intel PT functionality [5].
#
# More information about capturing callgraphs can be found in [1] in chapter
# 6.2.2 Capture call graph and 6.2.3 Identify hot branches
#
# Frequency Sampling
# ------------------
# "The choice of 99 Hertz, instead of 100 Hertz, is to avoid accidentally
# sampling in lockstep with some periodic activity, which would produce
# skewed results. This is also coarse: you may want to increase that to
# higher rates (eg, up to 997 Hertz) for finer resolution, especially if
# you are sampling short bursts of activity and you'd still like enough
# resolution to be useful. Bear in mind that higher frequencies means
# higher overhead" [2]
#
# perf report columns
# --------------------
#
# There are many columns which one can choosen from to customize the
# generation of the report. A lot of explainations can be found in [7].
# A basic information in the report is the fourth column, which indicates the
# privilege level at which the sample was taken, i.e. when the program was
# running when it was interrupted. It goes as follows:
#
# > [.] : user level
# > [k]: kernel level
# > [g]: guest kernel level (virtualization)
# > [u]: guest os user space
# > [H]: hypervisor
#
# Event Profiling wit PEBS
# ------------------------
#
# Apart from sampling at a timed interval (with a defined --freq value),
# taking samples triggered by CPU hardware counters (with --event) is another
# form of CPU profiling. [8, 6.3 Event profiling]
#
# However, there is a problem with that: There can be a a) jitter between
# and Performance Monitor Counter overflow and capturing the Instruction Pointer
# and b) wrong Instruction Pointer addresses with Out-of-order execution, etc.
# [8, Skew and PEBS]
#
# Intels solution for that is Precise Event-Based Sampling (PEBS). These use
# CPU hardware support to capture the real state of the CPU at the time of the
# event. perf can use precise sampling by adding a :p modifier. [8, Skew and PEBS]
#
# From `man perf-list`
#
# > The 'p' modifier can be used for specifying how precise the instruction
# > address should be. The 'p' modifier can be specified multiple times:
# >
# > 0 - SAMPLE_IP can have arbitrary skid
# > 1 - SAMPLE_IP must have constant skid
# > 2 - SAMPLE_IP requested to have 0 skid
# > 3 - SAMPLE_IP must have 0 skid
#
# Frequency (-F) vs Counter (-c)
# ------------------------------
# Count and frequency are two fundamental switches that tune the rate of
# sampling when using perf record:
#
# Count specifies the sample period which is expressed as the number of
# occurrences of an event, not the number of timer ticks. A sample is
# recorded when the sampling counter overflows, i.e., wraps from 2^64
# back to 0. [6, Event-based sampling overview]
#
# Frequency specifies the sample frequency which is the average rate of
# samples/sec. For event based sampling the sample will be generated when the
# corresponding counter overflows. The kernel dynamiclly adjusts the sampling
# period to adhere to the sampling frequency. [6, Period and rate]
#
# "Sampling reads values at a specific sampling frequency. This frequency is
# usually static and given in Hz, so you have for example 4000 events per
# second and a sampling frequency of 4000 Hz and a sampling rate of 250
# microseconds. With the sampling event, the concept of a static sampling
# frequency in time is somewhat redefined. Instead of a constant factor in
# time (sampling rate) you define a constant factor in events. So instead
# of a sampling rate of 250 microseconds, you have a sampling rate of
# 10,000 floating point operations." [7]
#
# Sampling event - instructions vs cycles
# ---------------------------------------
#
# llvm-project/bolt recommends to use "cycle events and not
# BR_INST_RETIRED.*. Empirically we found it to produce better results." [10]
#
# References
# ----------
#
# [1] Bakhvalov, Denis. Performance analysis and tuning modern CPUs. 2020.
# [2] Gregg, Brendon. Systems Performance: Enterprise and the Cloud,
#     2nd Edition. Addison-Wesley. 2020.
# [3] An introduction to last branch records https://lwn.net/Articles/680985/
# [4] Advanced usage of last branch records https://lwn.net/Articles/680996/
# [5] https://perf.wiki.kernel.org/index.php/Perf_tools_support_for_Intel%C2%AE_Processor_Trace#Example:_Tracing_your_own_code_:_Hello_World
# [6] https://perf.wiki.kernel.org/index.php/Tutorial
# [7] https://perf.wiki.kernel.org/index.php/Tutorial#Sampling_with_perf_record
# [8] https://www.brendangregg.com/perf.html
# [9] https://doc.zih.tu-dresden.de/software/perf_tools/
# [10] https://github.com/llvm/llvm-project/tree/main/bolt
#
source "$PWD/common.src"

function usage {
    cat <<EOM >&2
Usage: $(basename "$0") [-a] [-r] [-c CALLGRAPH_METHOD] [-t TIME_TO_SLEEP]
		        [-f FREQUNCY] [-m SIZE] [-o OUTFILE] [-i PROGRAM]

OPTIONS
	-h                 Print usage and exit.
	-a                 Record a system-wide collection from all CPUs.
	-r		   Create a callgraph.report from perf.data.
	-g		   Name the callgraph method to use.
			   [Default: dwarf,8192]
	-t                 If no executable specified collect data for t seconds.
			   [Default: 1]
	-f		   Change the default event overflow frequency of 4000.
	-o                 Name the output file.
			   [Default: callgraph]
	-m		   Number of mmap data pages (must be a power of two)
			   or size specification with appended unit character
			   /B/K/M/G) perf writes data to. The size is rounded
			   up to have nearest pages power of two value.
	-i 	           Specify a program to record.
	-A		   Append custom flags to *perf record*.

EOM
    exit 1
}

PROG=""
OUT_FILE="callgraph"
PERF_RECORD_FLAGS=""
PERF_CALLGRAPH_METHOD="dwarf,8192"
ADDITIONAL=""
FREQUENCY=""
MMAP=""
REPORT=0
TIME=0

while getopts "ht:g:i:o:f:m:A:avr" arg; do
  case $arg in
    h)
      usage
      ;;
    a)
      PERF_RECORD_FLAGS="${PERF_RECORD_FLAGS} --all-cpus"
      ;;
    t)
      PROG="-- sleep ${OPTARG}"
      ;;
    g)
      PERF_CALLGRAPH_METHOD="${OPTARG}"
      ;;
    i)
      PROG="${OPTARG}"
      ;;
    o)
      OUT_FILE="${OPTARG}"
      ;;
    f)
      FREQUENCY="--freq ${OPTARG}"
      ;;
    m)
      MMAP="--mmap-pages ${OPTARG}"
      ;;
    r)
      REPORT=1;;
    A)
      ADDITIONAL="${OPTARG}"
      ;;
    *)
      printf 'WARN: Unknown option (ignored): %s\n' "${arg}" >&2
      usage
      die ""
      ;;
  esac
done

if [ "${TIME}" -eq 0 ] && [ -z "${PROG}" ]; then
	# if no time value was defined and no executable was defined
	# set the default sleep value to 1 sec
	PROG="-- sleep 1"
fi


set -o xtrace

#
# The event modifier and branch-filter can't be used with LBR. Use dwarf
# instead.
#

perf record ${PERF_RECORD_FLAGS} \
	--event cycles:k \
	${FREQUENCY} \
	--call-graph ${PERF_CALLGRAPH_METHOD} \
	--branch-filter any,k \
	${MMAP} \
	${ADDITIONAL} \
	${PROG}

#
# Normally, perf-report shows the path through the program in reversed order
# (last function called on the top, first function called at the bottom)
#
# *--all-kernel --kernel-chains* can't be used in combination with
# *--branch-stack* in perf-report.
#

(( REPORT )) &&\
perf report --header --show-info --show-nr-samples --branch-stack \
--sort sample \
--fields +symbol_from,symbol_to,symbol_size \
--percent-limit 0 \
--field-separator '$' \
--stdio > "${OUT_FILE}.report" && exit 0 || exit 1