diff options
| author | Gabriel Schneider <[email protected]> | 2026-11-10 11:32:21 -0300 |
|---|---|---|
| committer | Gabriel Schneider <[email protected]> | 2026-11-10 12:08:27 -0300 |
| commit | b426a8a99bcad81ecbb41d1f2a2e83738c29d8e1 (patch) | |
| tree | 06e303f1f33ce53cfc2d8a2043e24f032877f9ad | |
| parent | 7f363779cb99b0820cce69c433bcfab87bb3d709 (diff) | |
| download | computeranim-b426a8a99bcad81ecbb41d1f2a2e83738c29d8e1.tar.gz computeranim-b426a8a99bcad81ecbb41d1f2a2e83738c29d8e1.zip | |
llvm: a pass that instruments for animation, its runtime, ztrace cc
llvm/pass.cpp is an LLVM pass plugin: lines, stores, loads, calls and
variables, each call into the runtime carrying names and type descriptions,
selected by globs (-ztrace-only, -ztrace-mem), before the optimizer by
default. src/instr/rt.zig is the runtime (libztrace-rt.a), which also
answers clang's own coverage and -finstrument-functions hooks;
src/instr/types.zig the grammar of the type descriptions and its parser.
ztrace cc adds all of it to a compiler command.
test-llvm compiles fib, two sorts, a linked list and a BFS through ztrace
cc and asserts on their recordings; bench-llvm measures what each selection
costs.
Co-Authored-By: Claude Fable 5.2 <[email protected]>
| -rw-r--r-- | build/llvm.zig | 95 | ||||
| -rw-r--r-- | llvm/bench.sh | 57 | ||||
| -rw-r--r-- | llvm/pass.cpp | 469 | ||||
| -rw-r--r-- | src/cli/cc.zig | 116 | ||||
| -rw-r--r-- | src/cli/main.zig | 2 | ||||
| -rw-r--r-- | src/instr/bench.zig | 70 | ||||
| -rw-r--r-- | src/instr/rt.zig | 227 | ||||
| -rw-r--r-- | src/instr/test.zig | 464 | ||||
| -rw-r--r-- | src/instr/types.zig | 215 | ||||
| -rw-r--r-- | targets/instr_bfs.c | 39 | ||||
| -rw-r--r-- | targets/instr_big.c | 11 | ||||
| -rw-r--r-- | targets/instr_fib.c | 12 | ||||
| -rw-r--r-- | targets/instr_list.c | 46 | ||||
| -rw-r--r-- | targets/instr_own.c | 27 | ||||
| -rw-r--r-- | targets/instr_sort.c | 44 |
15 files changed, 1893 insertions, 1 deletions
diff --git a/build/llvm.zig b/build/llvm.zig index d3c7eb3..a3e93cc 100644 --- a/build/llvm.zig +++ b/build/llvm.zig @@ -1,5 +1,98 @@ +//! Compiler instrumentation: the pass plugin (C++, built with the system +//! clang++ against the LLVM that will load it), the runtime instrumented +//! programs link, and tests on targets compiled through `ztrace cc`. +const std = @import("std"); const Ctx = @import("../build.zig").Ctx; pub fn add(ctx: Ctx) void { - _ = ctx; + const b = ctx.b; + + // The runtime runs inside the target at every event: optimized whatever + // mode the rest is built in. + const fast = b.createModule(.{ .root_source_file = b.path("src/trace/root.zig"), .target = ctx.target, .optimize = .ReleaseFast, .pic = true }); + const rt = b.addLibrary(.{ .name = "ztrace-rt", .root_module = b.createModule(.{ + .root_source_file = b.path("src/instr/rt.zig"), + .target = ctx.target, + .optimize = .ReleaseFast, + .pic = true, + .imports = &.{.{ .name = "ztrace", .module = fast }}, + }) }); + b.installArtifact(rt); + + const cxx = b.addSystemCommand(&.{ "sh", "-c", "exec clang++ -shared -fPIC -O2 -fno-rtti $(llvm-config --cxxflags) \"$0\" -o \"$1\"" }); + cxx.addFileArg(b.path("llvm/pass.cpp")); + const plugin = cxx.addOutputFileArg("ztrace-pass.so"); + b.getInstallStep().dependOn(&b.addInstallLibFile(plugin, "ztrace-pass.so").step); + + // For whoever draws values: the parser of type descriptions. + const types = b.addModule("ztrace-types", .{ .root_source_file = b.path("src/instr/types.zig"), .target = ctx.target, .optimize = ctx.optimize }); + + // The tests read recordings of the targets, each compiled by `ztrace cc` + // and run by `ztrace run`. + const options = b.addOptions(); + // A recording by name: its source, how clang optimizes it (-O2 is the + // optimizer going over what the pass put in), what `ztrace cc` is told. + const Target = struct { []const u8, []const u8, []const u8, []const []const u8 }; + for ([_]Target{ + .{ "fib", "fib", "-O0", &.{} }, + .{ "sort", "sort", "-O0", &.{} }, + .{ "sort_O2", "sort", "-O2", &.{} }, + .{ "sort_only", "sort", "-O0", &.{ "--only", "bub*" } }, + .{ "sort_mem", "sort", "-O0", &.{ "--only", "instr_sort.c", "--mem", "insertion" } }, + .{ "list", "list", "-O0", &.{} }, + .{ "bfs", "bfs", "-O0", &.{} }, + .{ "own", "own", "-O0", &.{} }, + .{ "big", "big", "-O0", &.{} }, + }) |target| { + const name, const source, const opt, const selection = target; + const cc = b.addRunArtifact(ctx.exe); + cc.addArg("cc"); + cc.addArgs(selection); + cc.addArg("--plugin"); + cc.addFileArg(plugin); + cc.addArg("--rt"); + cc.addArtifactArg(rt); + cc.addArgs(&.{ "--", "clang", opt }); + cc.addFileArg(b.path(b.fmt("targets/instr_{s}.c", .{source}))); + cc.addArg("-o"); + const program = cc.addOutputFileArg(b.fmt("instr_{s}", .{name})); + options.addOptionPath(b.fmt("{s}_program", .{name}), program); + + const run = b.addRunArtifact(ctx.exe); + run.addArgs(&.{ "run", "-o" }); + options.addOptionPath(name, run.addOutputFileArg(b.fmt("{s}.ztrace", .{name}))); + run.addArg("--"); + run.addFileArg(program); + run.expectStdErrMatch("(0 dropped)"); + } + + const step = ctx.areaTest("test-llvm", "Compiler instrumentation: the pass, the runtime, ztrace cc"); + const tests = b.addTest(.{ .root_module = b.createModule(.{ + .root_source_file = b.path("src/instr/test.zig"), + .target = ctx.target, + .optimize = ctx.optimize, + .imports = &.{ + .{ .name = "ztrace", .module = ctx.ztrace }, + .{ .name = "types", .module = types }, + .{ .name = "recordings", .module = options.createModule() }, + }, + }) }); + step.dependOn(&b.addRunArtifact(tests).step); + step.dependOn(&b.addRunArtifact(b.addTest(.{ .root_module = types })).step); + + // zig build bench-llvm -Doptimize=ReleaseFast: what each kind of + // instrumentation costs each target (llvm/bench.sh). + const bench = b.addSystemCommand(&.{"sh"}); + bench.addFileArg(b.path("llvm/bench.sh")); + bench.addArtifactArg(ctx.exe); + bench.addArtifactArg(b.addExecutable(.{ .name = "bench", .root_module = b.createModule(.{ + .root_source_file = b.path("src/instr/bench.zig"), + .target = ctx.target, + .optimize = .ReleaseFast, + .imports = &.{.{ .name = "ztrace", .module = fast }}, + }) })); + bench.addFileArg(plugin); + bench.addArtifactArg(rt); + bench.addDirectoryArg(b.path("targets")); + b.step("bench-llvm", "Measure the cost of compiler instrumentation").dependOn(&bench.step); } diff --git a/llvm/bench.sh b/llvm/bench.sh new file mode 100644 index 0000000..00edc88 --- /dev/null +++ b/llvm/bench.sh @@ -0,0 +1,57 @@ +#!/bin/sh +# What compiler instrumentation costs: zig build bench-llvm -Doptimize=ReleaseFast. +# Arguments: ztrace, the bench tool (src/instr/bench.zig), the plugin, the +# runtime, the targets directory. +set -eu +ztrace=$1 bench=$2 plugin=$3 rt=$4 targets=$5 +tmp=$(mktemp -d) +trap 'rm -rf "$tmp"' EXIT + +# target : argument when traced : argument when not : how many times more +# work the second is. With no tracer a target runs too briefly to time at +# the first. +workloads="fib:24:35:199.006 sort:2000:400000:200 list:5000:1000000:200 bfs:3000:600000:200" +selections="lines stores loads calls vars lines,calls,vars lines,calls,vars,stores edges cmps cyg" + +# The best of three runs: milliseconds, then whatever else the tool printed. +best() { + for _ in 1 2 3; do "$bench" "$@"; done | sort -n | head -1 +} + +cat <<'EOF2' +Per selection of `ztrace cc --instr`: + events emitted at the traced workload + idle time against the uninstrumented program, with no tracer + ring the same into a ring drained and thrown away + ns nanoseconds an event, into that ring + B/event bytes of recording an event (`ztrace run`, a moment a line) + B/line bytes of recording a source line executed + rec/s events a second into the recording +EOF2 +for opt in -O0 -O2; do + for w in $workloads; do + IFS=: read -r name arg long scale <<EOF2 +$w +EOF2 + clang $opt "$targets/instr_$name.c" -o "$tmp/plain" + start=$(best --untraced "$tmp/plain" 0 | cut -d' ' -f1) + alone=$(best --untraced "$tmp/plain" "$long" | awk -v start="$start" '{ print $1 - start }') + printf '\n%s %s: uninstrumented, %.1f ms at %s; traced at %s\n' "$name" "$opt" "$alone" "$long" "$arg" + printf ' %-24s %9s %7s %9s %6s %8s %7s %9s\n' selection events idle ring ns B/event B/line rec/s + for s in $selections; do + "$ztrace" cc --instr "$s" --plugin "$plugin" --rt "$rt" -- clang $opt "$targets/instr_$name.c" -o "$tmp/instr" + idle=$(best --untraced "$tmp/instr" "$long" | cut -d' ' -f1) + traced=$(best "$tmp/instr" "$arg") + # The lines the workload executes, whatever is selected: counted once. + [ "$s" = lines ] && lines=$(echo "$traced" | sed 's/.* line=\([0-9]*\).*/\1/') + recorded=$("$ztrace" run -o "$tmp/r.ztrace" -- "$tmp/instr" "$arg" 2>&1 | sed 's/.* \([0-9]*\) bytes.* \([0-9]*\) events\/s.*/\1 \2/') + echo "$traced $recorded" | awk -v s="$s" -v start="$start" -v alone="$alone" -v scale="$scale" -v idle="$idle" -v lines="$lines" \ + '{ printf " %-24s %9d %6.1fx %8.1fx %6.1f %8.1f %7.1f %9d\n", s, $2, (idle - start) / alone, ($1 - start) * scale / alone, ($1 - start - alone / scale) * 1e6 / $2, $(NF - 1) / $2, $(NF - 1) / lines, $NF }' + done + done +done + +"$ztrace" cc --plugin "$plugin" --rt "$rt" -- clang -O0 "$targets/instr_sort.c" -o "$tmp/sort" +echo +echo "sort 2000 -O0, held at each line by the stop mask and resumed at once:" +best --step "$tmp/sort" 2000 | awk '{ ms = $1; sub(/.* line=/, ""); printf " %d stops in %.0f ms: %.0f a second\n", $1, ms, $1 / ms * 1000 }' diff --git a/llvm/pass.cpp b/llvm/pass.cpp new file mode 100644 index 0000000..2872a98 --- /dev/null +++ b/llvm/pass.cpp @@ -0,0 +1,469 @@ +// ztrace-pass.so: an LLVM pass plugin that instruments a program for +// animation. Each inserted call hands the runtime (src/instr/rt.zig) what a +// viewer needs, so nothing parses DWARF at view time: +// +// lines __zt_line(file, line, column) before each new source line of a block +// stores __zt_store(addr, size) after each store, memset, memcpy +// loads __zt_load(addr, size) after each load; neither for the +// compiler's own temporaries +// calls __zt_enter(name, type, sp, site) at function entry +// __zt_exit(name, value, size) before each return +// vars __zt_var(addr, size, name, type, arg) per named local, after __zt_enter; +// a record in section ztrace_vars per global +// +// file, name and type are texts: pointers to records in section ztrace_strs +// (id, length, text), one per text in the program, the linker folding the +// copies of other translation units. The runtime numbers them from 1 and +// emits each as a `string` before the first event: an id is a byte or two +// in a recording. Type descriptions follow the grammar in +// src/instr/types.zig; the description of a named type has its id fixed +// here, a hash of the name, so a viewer finds it from the name. +// +// clang -g -fpass-plugin=ztrace-pass.so -Xclang -load -Xclang ztrace-pass.so \ +// -mllvm -ztrace-instr=lines,calls,vars,stores \ +// -mllvm -ztrace-only='sqlite3Btree*,*/pager.c' -mllvm -ztrace-mem='*Insert*' +// opt -load-pass-plugin=ztrace-pass.so -passes=ztrace +// +// It runs before optimization by default: every local still has an address +// and a debug record that says so, every source store exists, lines come in +// source order; the optimizer then keeps what the calls made observable. +// -ztrace-late runs it after: the stores, loads and lines of the code that +// really runs, and only the variables the optimizer left in memory. +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/BinaryFormat/Dwarf.h" +#include "llvm/IR/DebugInfoMetadata.h" +#include "llvm/IR/DebugProgramInstruction.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Module.h" +#include "llvm/Passes/PassBuilder.h" +#include "llvm/Plugins/PassPlugin.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/GlobPattern.h" +#include "llvm/Support/Path.h" +#include "llvm/Transforms/Utils/ModuleUtils.h" + +using namespace llvm; + +static cl::opt<std::string> Instr("ztrace-instr", cl::init("lines,calls,vars,stores"), + cl::desc("What to instrument: lines,stores,loads,calls,vars")); +static cl::opt<std::string> Only("ztrace-only", + cl::desc("Globs: instrument only the functions and globals whose name, " + "source path or source file name matches one")); +static cl::opt<std::string> MemOnly("ztrace-mem", cl::desc("Globs: of those, the functions whose stores and loads are instrumented")); +static cl::opt<bool> Late("ztrace-late", cl::desc("Instrument after optimization")); + +namespace { + +uint64_t hash(StringRef S) { + uint64_t H = 0xcbf29ce484222325; + for (unsigned char C : S) + H = (H ^ C) * 0x100000001b3; + return H; +} + +struct Instrumenter { + Module &M; + LLVMContext &Ctx = M.getContext(); + const DataLayout &DL = M.getDataLayout(); + Type *Void = Type::getVoidTy(Ctx), *Ptr = PointerType::getUnqual(Ctx); + IntegerType *I32 = Type::getInt32Ty(Ctx), *I64 = Type::getInt64Ty(Ctx); + bool Lines = false, Stores = false, Loads = false, Calls = false, Vars = false; + std::vector<GlobPattern> Where, Memory; + std::vector<GlobalValue *> Used; + DenseSet<const DIType *> Defined; + DenseMap<const DIFile *, Constant *> Files; + + FunctionCallee callee(const char *Name, std::initializer_list<Type *> Params) { + return M.getOrInsertFunction(Name, FunctionType::get(Void, Params, false)); + } + ConstantInt *i64(uint64_t V) { return ConstantInt::get(I64, V); } + + Instrumenter(Module &M) : M(M) { + SmallVector<StringRef> Words; + StringRef(Instr).split(Words, ',', -1, false); + for (StringRef W : Words) { + bool *Flag = StringSwitch<bool *>(W).Case("lines", &Lines).Case("stores", &Stores).Case("loads", &Loads).Case("calls", &Calls).Case("vars", &Vars).Default(nullptr); + if (!Flag) + reportFatalUsageError(Twine("-ztrace-instr: '") + W + "' is none of lines,stores,loads,calls,vars"); + *Flag = true; + } + for (auto [Text, Globs] : {std::pair(StringRef(Only), &Where), std::pair(StringRef(MemOnly), &Memory)}) { + Words.clear(); + Text.split(Words, ',', -1, false); + for (StringRef W : Words) { + auto G = GlobPattern::create(W); + if (!G) + reportFatalUsageError(Twine("ztrace: glob '") + W + "': " + toString(G.takeError())); + Globs->push_back(*G); + } + } + } + + // Names. + + // The record the runtime turns into a `string` event: id, length, text, + // padded to 8 bytes. One per name in the program: the linker folds the + // rest. Id 0 is the runtime's to number. + Constant *record(const Twine &Name, uint64_t Id, StringRef Text) { + if (GlobalVariable *G = M.getNamedGlobal(Name.str())) + return G; + std::string Bytes(16 + alignTo(Text.size(), 8), '\0'); + uint64_t Len = Text.size(); + memcpy(&Bytes[0], &Id, 8); + memcpy(&Bytes[8], &Len, 8); + memcpy(&Bytes[16], Text.data(), Len); + Constant *Init = ConstantDataArray::getString(Ctx, Bytes, false); + auto *G = new GlobalVariable(M, Init->getType(), false, GlobalValue::LinkOnceODRLinkage, Init, Name); + G->setSection("ztrace_strs"); + G->setAlignment(Align(8)); + G->setVisibility(GlobalValue::HiddenVisibility); + G->setComdat(M.getOrInsertComdat(G->getName())); + Used.push_back(G); + return G; + } + Constant *str(StringRef Text) { return record("__zt_s_" + utohexstr(hash(Text)), 0, Text); } + + static std::string path(const DIFile *F) { + SmallString<256> P(F->getFilename()); + if (!sys::path::is_absolute(P)) { + P = F->getDirectory(); + sys::path::append(P, F->getFilename()); + } + sys::path::remove_dots(P, true); + return std::string(P); + } + + // C++: the namespaces and classes a name sits in. + static std::string qualified(const DIScope *S, StringRef Name) { + std::string Out(Name); + for (; S && (isa<DINamespace>(S) || isa<DICompositeType>(S)); S = S->getScope()) + Out = (S->getName().empty() ? "(anonymous)" : S->getName().str()) + "::" + Out; + return Out; + } + + // No list selects everything; a list, what has a name (as written, or as + // linked) or a source file (its path, or its last part) matching one glob. + static bool selected(std::vector<GlobPattern> &Globs, StringRef Name, StringRef Linked, const DIFile *File) { + std::string Path = File ? path(File) : ""; + for (GlobPattern &G : Globs) + if (G.match(Name) || G.match(Linked) || G.match(Path) || G.match(sys::path::filename(Path))) + return true; + return Globs.empty(); + } + + // Type descriptions: the grammar of src/instr/types.zig. + + static std::string opaque(const DIType *T) { return "x" + utostr(T->getSizeInBits()); } + + static char letter(const DIType *T) { + while (auto *D = dyn_cast_or_null<DIDerivedType>(T)) + T = D->getBaseType(); + if (auto *C = dyn_cast_or_null<DICompositeType>(T)) + T = C->getBaseType(); // an enum's integer + auto *B = dyn_cast_or_null<DIBasicType>(T); + switch (B ? B->getEncoding() : 0) { + case dwarf::DW_ATE_boolean: + return 'b'; + case dwarf::DW_ATE_float: + return 'f'; + case dwarf::DW_ATE_signed: + return 'i'; + case dwarf::DW_ATE_unsigned: + return 'u'; + case dwarf::DW_ATE_signed_char: + return B->getName() == "char" ? 'c' : 'i'; + case dwarf::DW_ATE_unsigned_char: + return B->getName() == "char" ? 'c' : 'u'; + case dwarf::DW_ATE_UTF: + case dwarf::DW_ATE_ASCII: + return 'c'; + default: + return 'x'; + } + } + + // A named type is written as its name. Its description is a text of its + // own, under an id no numbered text has (the top bit) that follows from + // the name: `defId` in types.zig. It is marked defined before its body is + // described, so a struct that points to itself ends. + std::string named(const DIType *T, std::string Name, bool HasBody, function_ref<std::string()> Body) { + if (HasBody && Defined.insert(T).second) { + uint64_t Id = hash("=" + Name) | 1ull << 63; + record("__zt_d_" + utohexstr(Id), Id, Body()); + } + return "`" + Name + "`"; + } + + std::string record(const DICompositeType *C) { + if (C->getTag() == dwarf::DW_TAG_enumeration_type) { + std::string Out = "enum(" + (C->getBaseType() ? type(C->getBaseType()) : "u" + utostr(C->getSizeInBits())) + "){"; + for (DINode *E : C->getElements()) + if (auto *V = dyn_cast<DIEnumerator>(E)) + Out += V->getName().str() + "=" + toString(V->getValue(), 10, !V->isUnsigned()) + ";"; + return Out + "}"; + } + std::string Out = (C->getTag() == dwarf::DW_TAG_union_type ? "union(" : "struct(") + utostr(C->getSizeInBits() / 8) + "){"; + for (DINode *E : C->getElements()) { + auto *F = dyn_cast<DIDerivedType>(E); + if (!F || F->isStaticMember() || (F->getTag() != dwarf::DW_TAG_member && F->getTag() != dwarf::DW_TAG_inheritance)) + continue; + for (char Ch : F->getName()) + Out += isAlnum(Ch) || Ch == '$' ? Ch : '_'; + uint64_t At = F->getOffsetInBits(); + Out += "@" + utostr(At / 8); + if (F->isBitField()) + Out += "." + utostr(At % 8) + ":" + letter(F->getBaseType()) + utostr(F->getSizeInBits()); + else + Out += ":" + type(F->getBaseType()); + Out += ";"; + } + return Out + "}"; + } + + std::string type(const DIType *T) { + if (!T) + return "void"; + if (auto *B = dyn_cast<DIBasicType>(T)) + return letter(B) + utostr(B->getSizeInBits()); + if (auto *S = dyn_cast<DISubroutineType>(T)) { + DITypeArray Types = S->getTypeArray(); + std::string Out = "fn("; + for (unsigned I = 1; I < Types.size(); ++I) + Out += (I > 1 ? "," : "") + (Types[I] ? type(Types[I]) : "..."); + return Out + ")" + type(Types.size() ? Types[0] : nullptr); + } + if (auto *D = dyn_cast<DIDerivedType>(T)) { + switch (D->getTag()) { + case dwarf::DW_TAG_pointer_type: + case dwarf::DW_TAG_reference_type: + case dwarf::DW_TAG_rvalue_reference_type: + return "*" + type(D->getBaseType()); + case dwarf::DW_TAG_typedef: + return named(D, qualified(D->getScope(), D->getName()), true, [&] { return type(D->getBaseType()); }); + case dwarf::DW_TAG_ptr_to_member_type: + return opaque(D); + default: // const, volatile, restrict, atomic + return type(D->getBaseType()); + } + } + if (auto *C = dyn_cast<DICompositeType>(T)) { + unsigned Tag = C->getTag(); + if (Tag == dwarf::DW_TAG_array_type && !C->isVector()) { + std::string Out; + for (DINode *E : C->getElements()) + if (auto *R = dyn_cast<DISubrange>(E)) { + // A flexible or variable-length array has no constant count: 0. + auto *N = dyn_cast_if_present<ConstantInt *>(R->getCount()); + Out += "[" + utostr(N && N->getSExtValue() > 0 ? N->getZExtValue() : 0) + "]"; + } + return Out + type(C->getBaseType()); + } + bool Struct = Tag == dwarf::DW_TAG_structure_type || Tag == dwarf::DW_TAG_class_type; + if (Struct || Tag == dwarf::DW_TAG_union_type || Tag == dwarf::DW_TAG_enumeration_type) { + if (C->getName().empty()) + return record(C); + // shortcut: two different types with one name (file-local structs in + // two C files) share a definition; add the declaring file to the name + // when a target has them. + return named(C, (Struct ? "struct " : Tag == dwarf::DW_TAG_union_type ? "union " : "enum ") + qualified(C->getScope(), C->getName()), + !C->isForwardDecl(), [&] { return record(C); }); + } + } + return opaque(T); + } + + // Code. + + void instrument(Function &F) { + DISubprogram *SP = F.getSubprogram(); + BasicBlock &Entry = F.getEntryBlock(); + std::string FName = qualified(SP->getScope(), SP->getName()); + bool Mem = selected(Memory, FName, F.getName(), SP->getFile()); + + // The named locals that live in memory: the first debug record that + // gives a static alloca or a by-value argument as a variable's address. + // That is #dbg_declare at -O0, and #dbg_assign from -O1 on, where clang + // turns the one into the other before any plugin runs. + struct Local { + Value *Addr; + uint64_t Size; + DILocalVariable *Var; + }; + std::vector<Local> Locals; + SmallPtrSet<Value *, 8> Named; + for (BasicBlock &BB : F) + for (Instruction &I : BB) + for (DbgVariableRecord &R : filterDbgVars(I.getDbgRecordRange())) { + if (!R.isDbgDeclare() && !R.isDbgAssign()) + continue; + Value *V = R.getAddress(); + if (!V || !Named.insert(V).second || !Vars || (R.isDbgAssign() ? R.getAddressExpression() : R.getExpression())->getNumElements()) + continue; + if (auto *A = dyn_cast<AllocaInst>(V); A && A->isStaticAlloca()) { + if (auto Size = A->getAllocationSize(DL)) + Locals.push_back({A, Size->getFixedValue(), R.getVariable()}); + } else if (auto *Arg = dyn_cast<Argument>(V); Arg && Arg->hasByValAttr()) { + Locals.push_back({Arg, DL.getTypeAllocSize(Arg->getParamByValType()).getFixedValue(), R.getVariable()}); + } + } + // Declared for the whole call, so two of them must not share a stack + // slot: without its lifetime markers a slot is never reused. + for (Local &L : Locals) + for (User *U : make_early_inc_range(L.Addr->users())) + if (auto *Life = dyn_cast<LifetimeIntrinsic>(U)) + Life->eraseFromParent(); + + // What was there before anything is inserted. + std::vector<Instruction *> Body; + for (BasicBlock &BB : F) + for (Instruction &I : BB) + Body.push_back(&I); + + IRBuilder<> B(&Entry, Entry.getFirstNonPHIOrDbgOrAlloca()); + B.SetCurrentDebugLocation(DILocation::get(Ctx, SP->getScopeLine(), 0, SP)); + Constant *Name = Calls ? str(FName) : nullptr; + if (Calls) { + Value *Sp = B.CreateIntrinsic(Intrinsic::addressofreturnaddress, {Ptr}, {}); + Value *Site = B.CreateIntrinsic(Intrinsic::returnaddress, {Ptr}, {ConstantInt::get(I32, 0)}); + B.CreateCall(callee("__zt_enter", {Ptr, Ptr, Ptr, Ptr}), {Name, str(type(SP->getType())), Sp, Site}); + } + for (Local &L : Locals) + B.CreateCall(callee("__zt_var", {Ptr, I64, Ptr, Ptr, I32}), + {L.Addr, i64(L.Size), str(L.Var->getName()), str(type(L.Var->getType())), ConstantInt::get(I32, L.Var->getArg())}); + + const BasicBlock *Block = nullptr; + const DIFile *File = nullptr; + unsigned Line = 0; + for (Instruction *I : Body) { + // Nothing may come between a musttail call and its return: the call + // is where this function ends. + CallInst *Tail = I->getParent()->getTerminatingMustTailCall(); + if (Tail && I != Tail && Tail->comesBefore(I)) + continue; + B.SetInsertPoint(I); + + // A line event where a block reaches a line it was not on. A block + // always says where it is: a loop comes back to the same line. Jumps + // do no work of their own (the closing brace of a loop body). + if (I->getParent() != Block) { + Block = I->getParent(); + Line = 0; + } + const DebugLoc &Loc = I->getDebugLoc(); + if (Lines && Loc && Loc.getLine() && !isa<PHINode>(I) && !isa<AllocaInst>(I) && !I->isEHPad() && !I->isLifetimeStartOrEnd() && !isa<UncondBrInst>(I) && + (Loc.getLine() != Line || Loc->getFile() != File)) { + Line = Loc.getLine(); + File = Loc->getFile(); + auto [At, New] = Files.try_emplace(File); + if (New) + At->second = str(path(File)); + B.CreateCall(callee("__zt_line", {Ptr, I32, I32}), {At->second, ConstantInt::get(I32, Line), ConstantInt::get(I32, Loc.getCol())}); + } + + if (Calls && (isa<ReturnInst>(I) || I == Tail)) { + Value *V = I == Tail ? nullptr : cast<ReturnInst>(I)->getReturnValue(); + Type *T = V ? V->getType() : Void; + unsigned Bits = T->isPointerTy() ? 64 : T->isIntegerTy() || T->isFloatTy() || T->isDoubleTy() ? T->getPrimitiveSizeInBits().getFixedValue() : 0; + if (Bits == 0 || Bits > 64) + V = i64(0), Bits = 0; // void, or an aggregate: no value + else if (T->isPointerTy()) + V = B.CreatePtrToInt(V, I64); + else + V = B.CreateZExt(B.CreateBitCast(V, IntegerType::get(Ctx, Bits)), I64); + B.CreateCall(callee("__zt_exit", {Ptr, I64, I32}), {Name, V, ConstantInt::get(I32, (Bits + 7) / 8)}); + } + + Value *Addr = nullptr, *Size = nullptr; + const char *Hook = "__zt_store"; + if (auto *S = dyn_cast<StoreInst>(I); S && Stores) + Addr = S->getPointerOperand(), Size = i64(DL.getTypeStoreSize(S->getValueOperand()->getType())); + else if (auto *A = dyn_cast<AtomicRMWInst>(I); A && Stores) + Addr = A->getPointerOperand(), Size = i64(DL.getTypeStoreSize(A->getValOperand()->getType())); + else if (auto *X = dyn_cast<AtomicCmpXchgInst>(I); X && Stores) + Addr = X->getPointerOperand(), Size = i64(DL.getTypeStoreSize(X->getNewValOperand()->getType())); + else if (auto *Set = dyn_cast<MemIntrinsic>(I); Set && Stores) + Addr = Set->getRawDest(), Size = Set->getLength(); + else if (auto *L = dyn_cast<LoadInst>(I); L && Loads) + Addr = L->getPointerOperand(), Size = i64(DL.getTypeStoreSize(L->getType())), Hook = "__zt_load"; + // Not the stack slots the compiler made for itself (a return value on + // its way out, a temporary): nothing names them, so nothing draws them. + Value *Object = Addr ? getUnderlyingObject(Addr) : nullptr; + if (Addr && Mem && (!isa<AllocaInst>(Object) || Named.count(Object))) { + // After it: the runtime reads the bytes the store left. + B.SetInsertPoint(I->getNextNode()); + B.SetCurrentDebugLocation(Loc); + B.CreateCall(callee(Hook, {Ptr, I64}), {Addr, B.CreateZExtOrTrunc(Size, I64)}); + } + } + } + + bool run() { + std::vector<Function *> Functions; + for (Function &F : M) { + DISubprogram *SP = F.getSubprogram(); + if (!F.isDeclaration() && SP && !F.hasAvailableExternallyLinkage() && !F.hasFnAttribute(Attribute::Naked) && + !F.hasFnAttribute(Attribute::DisableSanitizerInstrumentation) && + selected(Where, qualified(SP->getScope(), SP->getName()), F.getName(), SP->getFile())) + Functions.push_back(&F); + } + // The globals with debug info: {address, size, name, type} each, for the + // runtime to declare and snapshot at startup. + std::vector<Constant *> Globals; + if (Vars) + for (GlobalVariable &G : M.globals()) { + SmallVector<DIGlobalVariableExpression *, 1> Info; + G.getDebugInfo(Info); + if (G.isDeclaration() || G.hasAvailableExternallyLinkage() || G.isThreadLocal() || Info.empty()) + continue; + DIGlobalVariable *V = Info[0]->getVariable(); + std::string Name = qualified(V->getScope(), V->getName()); + if (selected(Where, Name, G.getName(), V->getFile())) + Globals.push_back(ConstantStruct::getAnon({&G, i64(DL.getTypeAllocSize(G.getValueType())), str(Name), str(type(V->getType()))})); + } + for (Function *F : Functions) + instrument(*F); + for (Constant *Init : Globals) { + auto *G = new GlobalVariable(M, Init->getType(), true, GlobalValue::PrivateLinkage, Init, "__zt_v"); + G->setSection("ztrace_vars"); + G->setAlignment(Align(8)); + Used.push_back(G); + } + // Used: nothing refers to these records but the section's bounds. + appendToUsed(M, Used); + return !Used.empty() || !Functions.empty(); + } +}; + +struct ZtracePass : PassInfoMixin<ZtracePass> { + PreservedAnalyses run(Module &M, ModuleAnalysisManager &) { + return Instrumenter(M).run() ? PreservedAnalyses::none() : PreservedAnalyses::all(); + } + // Also for the optnone functions of -O0. + static bool isRequired() { return true; } +}; + +} // namespace + +extern "C" LLVM_ATTRIBUTE_WEAK PassPluginLibraryInfo llvmGetPassPluginInfo() { + return {LLVM_PLUGIN_API_VERSION, "ztrace", "0.1", [](PassBuilder &PB) { + PB.registerPipelineStartEPCallback([](ModulePassManager &MPM, OptimizationLevel) { + if (!Late) + MPM.addPass(ZtracePass()); + }); + PB.registerOptimizerLastEPCallback([](ModulePassManager &MPM, OptimizationLevel, ThinOrFullLTOPhase) { + if (Late) + MPM.addPass(ZtracePass()); + }); + PB.registerPipelineParsingCallback([](StringRef Name, ModulePassManager &MPM, ArrayRef<PassBuilder::PipelineElement>) { + if (Name != "ztrace") + return false; + MPM.addPass(ZtracePass()); + return true; + }); + }}; +} diff --git a/src/cli/cc.zig b/src/cli/cc.zig new file mode 100644 index 0000000..1d08b51 --- /dev/null +++ b/src/cli/cc.zig @@ -0,0 +1,116 @@ +//! ztrace cc: a compiler command with the instrumentation added, so a +//! program compiled from source records itself under `ztrace run`. +const std = @import("std"); +const util = @import("util.zig"); +const fail = util.fail; + +pub const usage = + \\usage: ztrace cc [--instr LIST] [--only GLOBS] [--mem GLOBS] [--late] [--plugin SO] [--rt A] -- CLANG ARGS + \\ + \\Runs CLANG (clang, clang++) with ARGS and -g, the pass plugin and its + \\options, and when the command links, the runtime: + \\ + \\ ztrace cc -- clang sort.c -o sort && ztrace run -- ./sort + \\ + \\ --instr LIST comma separated, default lines,calls,vars,stores + \\ lines `line` at each source line reached + \\ stores `mem_write`, with the bytes, after each store to a + \\ variable or through a pointer; a memset or + \\ memcpy is one, of its first 64 KiB at most + \\ loads `mem_read` after each load + \\ calls `call` at function entry, `ret` with the value at exit + \\ vars `variable` for each named local and global: + \\ address, size, name, type description + \\ from stock clang, no plugin and no names: + \\ edges `edge` (-fsanitize-coverage=trace-pc-guard) + \\ cmps `cmp`, and `edge`: clang compares only along with edges + \\ (-fsanitize-coverage=trace-pc-guard,trace-cmp) + \\ cyg `call`, `ret` (-finstrument-functions) + \\ --only GLOBS comma separated; the plugin instruments only the functions + \\ and globals whose name, source path or source file name + \\ matches one: 'sort*,*/vdbe.c' + \\ --mem GLOBS of those, the functions whose stores and loads are recorded + \\ (default: all of them). Stores are most of a recording: + \\ in a large program, name where memory matters. + \\ --late instrument after optimization: the stores and lines of the + \\ code that runs, not of the source + \\ --plugin SO the pass (default: ../lib/ztrace-pass.so from this program) + \\ --rt A the runtime (default: ../lib/libztrace-rt.a) + \\ +; + +pub fn run(init: std.process.Init, args: []const [:0]const u8) !void { + const arena = init.arena.allocator(); + var instr: []const u8 = "lines,calls,vars,stores"; + var only: ?[]const u8 = null; + var mem: ?[]const u8 = null; + var late = false; + var plugin: ?[]const u8 = null; + var rt: ?[]const u8 = null; + var i: usize = 0; + while (i < args.len) : (i += 1) { + const arg = args[i]; + if (std.mem.eql(u8, arg, "--")) { + i += 1; + break; + } else if (std.mem.eql(u8, arg, "--late")) { + late = true; + } else if (i + 1 < args.len and std.mem.eql(u8, arg, "--instr")) { + i += 1; + instr = args[i]; + } else if (i + 1 < args.len and std.mem.eql(u8, arg, "--only")) { + i += 1; + only = args[i]; + } else if (i + 1 < args.len and std.mem.eql(u8, arg, "--mem")) { + i += 1; + mem = args[i]; + } else if (i + 1 < args.len and std.mem.eql(u8, arg, "--plugin")) { + i += 1; + plugin = args[i]; + } else if (i + 1 < args.len and std.mem.eql(u8, arg, "--rt")) { + i += 1; + rt = args[i]; + } else fail(usage, .{}); + } + if (i >= args.len) fail(usage, .{}); + const lib = try std.fs.path.join(arena, &.{ try std.process.executableDirPathAlloc(init.io, arena), "..", "lib" }); + + var argv: std.ArrayList([]const u8) = .empty; + for (args[i..]) |arg| try argv.append(arena, arg); + // What a command that only links does not use is no warning. + try argv.appendSlice(arena, &.{ "--start-no-unused-arguments", "-g" }); + // The plugin's own words, which it checks; the rest are clang's flags. + var pass: std.ArrayList(u8) = .empty; + var words = std.mem.tokenizeScalar(u8, instr, ','); + while (words.next()) |word| { + if (std.mem.eql(u8, word, "edges")) { + try argv.append(arena, "-fsanitize-coverage=trace-pc-guard"); + } else if (std.mem.eql(u8, word, "cmps")) { + try argv.append(arena, "-fsanitize-coverage=trace-pc-guard,trace-cmp"); + } else if (std.mem.eql(u8, word, "cyg")) { + try argv.append(arena, "-finstrument-functions"); + } else try pass.print(arena, "{s}{s}", .{ if (pass.items.len > 0) "," else "", word }); + } + if (pass.items.len > 0) { + const so = plugin orelse try std.fs.path.join(arena, &.{ lib, "ztrace-pass.so" }); + // -load as well: the plugin's options must exist when -mllvm is read, + // which is before -fpass-plugin loads it. + try argv.appendSlice(arena, &.{ try std.fmt.allocPrint(arena, "-fpass-plugin={s}", .{so}), "-Xclang", "-load", "-Xclang", so }); + try argv.appendSlice(arena, &.{ "-mllvm", try std.fmt.allocPrint(arena, "-ztrace-instr={s}", .{pass.items}) }); + if (only) |globs| try argv.appendSlice(arena, &.{ "-mllvm", try std.fmt.allocPrint(arena, "-ztrace-only={s}", .{globs}) }); + if (mem) |globs| try argv.appendSlice(arena, &.{ "-mllvm", try std.fmt.allocPrint(arena, "-ztrace-mem={s}", .{globs}) }); + if (late) try argv.appendSlice(arena, &.{ "-mllvm", "-ztrace-late" }); + } + try argv.append(arena, "--end-no-unused-arguments"); + // The command links unless it says where to stop. The whole archive: with + // -fsanitize-coverage clang links weak callbacks of its own first, and + // only a runtime already in the link replaces them. -x none: after an + // -x c the archive would be read as source. + const links = for (args[i..]) |arg| { + if (std.mem.eql(u8, arg, "-c") or std.mem.eql(u8, arg, "-S") or std.mem.eql(u8, arg, "-E") or std.mem.eql(u8, arg, "-fsyntax-only")) break false; + } else true; + if (links) try argv.appendSlice(arena, &.{ "-x", "none", "-Wl,--whole-archive", rt orelse try std.fs.path.join(arena, &.{ lib, "libztrace-rt.a" }), "-Wl,--no-whole-archive" }); + + const err = std.process.replace(init.io, .{ .argv = argv.items }); + fail("{s}: {t}\n", .{ argv.items[0], err }); +} diff --git a/src/cli/main.zig b/src/cli/main.zig index 72b894a..1ac019f 100644 --- a/src/cli/main.zig +++ b/src/cli/main.zig @@ -9,6 +9,7 @@ const commands = .{ .run = @import("run.zig"), .dump = @import("dump.zig"), .show = @import("show.zig"), + .cc = @import("cc.zig"), }; const usage = @@ -19,6 +20,7 @@ const usage = \\ run record a program that carries a ring producer (agent, instrumentation) \\ dump print a recording's events \\ show print a recording's summary, or the program's state at a moment + \\ cc compile a program with instrumentation that records it \\ \\`ztrace COMMAND --help` for each. \\ diff --git a/src/instr/bench.zig b/src/instr/bench.zig new file mode 100644 index 0000000..38ad1a3 --- /dev/null +++ b/src/instr/bench.zig @@ -0,0 +1,70 @@ +//! What instrumentation costs, measured on a target: runs PROGRAM and prints +//! one line, its wall time in milliseconds and the events it emitted by kind. +//! +//! bench PROGRAM ARGS with a ring, drained and counted, nothing recorded +//! bench --untraced PROGRAM ARGS with no ring: the calls return at once +//! bench --step PROGRAM ARGS held at each `line` by the ring's stop mask, resumed at once +//! +//! llvm/bench.sh makes the tables from it. +const std = @import("std"); +const linux = std.os.linux; +const zt = @import("ztrace"); + +var counts: [64]u64 = @splat(0); + +pub fn main(init: std.process.Init) !void { + const arena = init.arena.allocator(); + const args = try init.minimal.args.toSlice(arena); + const mode: enum { ring, untraced, step } = if (args.len > 1 and std.mem.eql(u8, args[1], "--untraced")) .untraced else if (args.len > 1 and std.mem.eql(u8, args[1], "--step")) .step else .ring; + const rest = args[@as(usize, 1) + @intFromBool(mode != .ring) ..]; + if (rest.len == 0) return error.Usage; + const argv = try arena.allocSentinel(?[*:0]const u8, rest.len, null); + for (argv, rest) |*dst, s| dst.* = s.ptr; + const env = init.minimal.environ.block.slice; + + const start = zt.event.now(); + if (mode == .untraced) { + const pid = linux.fork(); + if (pid == 0) { + _ = linux.execve(argv[0].?, argv.ptr, env.ptr); + linux.exit_group(127); + } + var status: u32 = 0; + _ = linux.waitpid(@intCast(pid), @ptrCast(&status), 0); + } else { + var session = try zt.host.Session.spawn(arena, argv[0].?, argv.ptr, env, .{ .stop_mask = if (mode == .step) zt.Kind.line.bit() else 0 }); + defer session.close(); + const ring = &session.ring; + // Step mode answers each stop at once. Otherwise the consumer drains + // what there is and sleeps a moment, never on the ring's futex: so + // the producer pays neither a wake nor for a cache line the consumer + // keeps taking, and the time is the cost of producing. + while (true) { + const rec = ring.peek() orelse { + if (session.exit_code != null) break; + var status: u32 = 0; + if (linux.waitpid(session.pid, @ptrCast(&status), linux.W.NOHANG) != 0) { + session.exit_code = 0; + } else if (mode == .step) std.atomic.spinLoopHint() else _ = linux.nanosleep(&.{ .sec = 0, .nsec = 200_000 }, null); + continue; + }; + const kind = rec.ev.kind; + counts[@intFromEnum(kind)] += 1; + ring.advance(rec); + if (mode == .step and kind == .line) ring.resumeAll(); + } + } + const ms = @as(f64, @floatFromInt(zt.event.now() - start)) / 1e6; + + var buf: [1024]u8 = undefined; + var out = std.Io.File.stdout().writer(init.io, &buf); + const w = &out.interface; + var total: u64 = 0; + for (counts) |n| total += n; + try w.print("{d:.2} {d}", .{ ms, total }); + for (counts, 0..) |n, kind| { + if (n > 0) try w.print(" {t}={d}", .{ @as(zt.Kind, @enumFromInt(kind)), n }); + } + try w.print("\n", .{}); + try w.flush(); +} diff --git a/src/instr/rt.zig b/src/instr/rt.zig new file mode 100644 index 0000000..3719409 --- /dev/null +++ b/src/instr/rt.zig @@ -0,0 +1,227 @@ +//! libztrace-rt.a: what compiler-instrumented code calls, linked into the +//! target; every call becomes an event in the ring the tracer handed over, +//! or returns at once when there is none. Two faces: +//! +//! Our pass (llvm/pass.cpp): +//! __zt_line(file, line, column) line a0=file a1=line a2=column +//! __zt_store(addr, size) mem_write a0=addr a1=len, the bytes (see `wrote`) +//! __zt_load(addr, size) mem_read a0=addr a1=len +//! __zt_enter(name, type, sp, site) call a0=function name a1=call site a2=sp a3=function type +//! __zt_exit(name, value, size) ret a0=function name a1=value, aux=bytes of value (0: none) +//! __zt_var(addr, size, name, type, arg) variable a0=addr a1=size a2=name a3=type, aux=N for the Nth parameter +//! file, name and type arrive as pointers to text records and leave as +//! string ids. The records, and the program's globals, sit in two sections +//! the pass filled: before the first event the runtime numbers the texts +//! and emits each as a `string` (from thread 0: no thread), and each global +//! as a `variable` with one `mem_write` of what it holds, from the thread +//! that got there first, which is inside no call yet. A local is declared, +//! never dumped: what it holds arrives with the stores. +//! +//! No pc in `line`, `mem_write` and `mem_read`, though event.zig has a +//! place for one: the source line is the place, and seven bytes would be a +//! third of each of them in a recording. +//! +//! Stock clang, no plugin: +//! -fsanitize-coverage=trace-pc-guard edge a0=pc +//! -fsanitize-coverage=trace-cmp cmp aux=operand bytes a0=pc a1=lhs a2=rhs +//! -finstrument-functions call a0=function address a1=call site a2=frame +//! ret a0=function address +//! +//! Raw syscalls only, no allocation: a store may be anywhere. +// shortcut: one program, one runtime: the texts of a shared library loaded later are never numbered; walk its sections on dlopen when a target needs it. +const std = @import("std"); +const linux = std.os.linux; +const zt = @import("ztrace"); + +/// 0 untried, 1 starting, 2 tracing, 3 not traced. +var state: std.atomic.Value(u8) = .init(0); +var ring: *zt.Ring = undefined; + +fn start(tid: u32) bool { + @branchHint(.cold); + while (true) switch (state.load(.acquire)) { + 2 => return true, + 3 => return false, + // Another thread is emitting the names: nothing may get ahead of them. + 1 => _ = linux.sched_yield(), + else => if (state.cmpxchgStrong(0, 1, .acquire, .monotonic) == null) { + const found = zt.client.get(); + if (found) |r| { + ring = r; + names(); + globals(tid); + } + state.store(if (found != null) 2 else 3, .release); + }, + }; +} + +fn put(tid: u32, kind: zt.Kind, aux: u16, a: [6]u64, payload: []const u8) void { + ring.emit(.{ .ts = zt.event.now(), .tid = tid, .kind = kind, .aux = aux, .a = a }, payload); +} + +const Thread = struct { + /// A gettid a thread, not an event: the syscall would be half the cost + /// of an event. + // shortcut: a forked child keeps its parent's tid; reset it in a fork hook once a target forks. + tid: u32 = 0, + inside: bool = false, +}; +threadlocal var thread: Thread = .{}; + +/// The calling thread, for one event; `inside` is the caller's to clear. +/// Null when nobody listens, or when the thread is already in here: what the +/// runtime calls (memcpy and strlen, in a libc compiled with the pass) must +/// not trace itself. +fn enter() ?*Thread { + const s = state.load(.monotonic); + if (s == 3) return null; + const t = &thread; + if (t.inside) return null; + t.inside = true; + if (t.tid == 0) t.tid = @intCast(linux.gettid()); + if (s == 2 or start(t.tid)) return t; + t.inside = false; + return null; +} + +/// An event with no text in it: a text's id is read after `enter`, which +/// may be what numbers it. +fn emit(kind: zt.Kind, aux: u16, a: [6]u64, payload: []const u8) void { + const t = enter() orelse return; + defer t.inside = false; + put(t.tid, kind, aux, a, payload); +} + +/// The `mem_write`s of one write (a store, a memset, a memcpy, a global's +/// first contents), in pieces that fit the smallest ring. a1 is how much was +/// written from a0 on, so the first piece says the whole length; a payload +/// shorter than a1 is all that is recorded of it. A write is recorded up to +/// `most`: a megabyte cleared is not a megabyte in the recording. +const most = 64 << 10; + +fn wrote(tid: u32, addr: usize, len: usize) void { + var at: usize = 0; + while (at < @min(len, most)) : (at += 2048) { + const bytes: [*]const u8 = @ptrFromInt(addr + at); + put(tid, .mem_write, 0, .{ addr + at, len - at, 0, 0, 0, 0 }, bytes[0..@min(len - at, 2048)]); + } +} + +/// The bounds the linker gives a section named like a C identifier; both 0 +/// when no object has the section. +fn section(comptime name: []const u8) [2]usize { + return .{ + @intFromPtr(@extern(?*const u8, .{ .name = "__start_" ++ name, .linkage = .weak })), + @intFromPtr(@extern(?*const u8, .{ .name = "__stop_" ++ name, .linkage = .weak })), + }; +} + +/// A text of the program, in section ztrace_strs: this, then the text, +/// padded to 8 bytes. +const Text = extern struct { + /// The string id. The pass leaves 0, to be numbered here from 1: ids + /// small enough to cost a recording a byte or two each. It fixes only + /// the ids nothing but a viewer looks up (`types.defId`). + id: u64, + len: u64, +}; + +fn names() void { + var at, const end = section("ztrace_strs"); + var next: u64 = 0; + while (at < end) { + const text: *Text = @ptrFromInt(at); + if (text.id == 0) { + next += 1; + text.id = next; + } + const bytes: [*]const u8 = @ptrFromInt(at + @sizeOf(Text)); + // A text the ring cannot hold is cut: better than none of it. + put(0, .string, 0, .{ text.id, 0, 0, 0, 0, 0 }, bytes[0..@min(text.len, ring.hdr.capacity / 2)]); + at += @sizeOf(Text) + std.mem.alignForward(usize, text.len, 8); + } +} + +/// ztrace_vars: (address, size, name, type)*. +fn globals(tid: u32) void { + var at, const end = section("ztrace_vars"); + while (at < end) : (at += 32) { + const g: *const extern struct { addr: u64, size: u64, name: *const Text, type: *const Text } = @ptrFromInt(at); + put(tid, .variable, 0, .{ g.addr, g.size, g.name.id, g.type.id, 0, 0 }, ""); + wrote(tid, g.addr, g.size); + } +} + +// The pass. + +export fn __zt_line(file: *const Text, line: u32, column: u32) void { + const t = enter() orelse return; + defer t.inside = false; + put(t.tid, .line, 0, .{ file.id, line, column, 0, 0, 0 }, ""); +} + +export fn __zt_store(addr: usize, size: u64) void { + const t = enter() orelse return; + defer t.inside = false; + wrote(t.tid, addr, size); +} + +export fn __zt_load(addr: usize, size: u64) void { + emit(.mem_read, 0, .{ addr, size, 0, 0, 0, 0 }, ""); +} + +export fn __zt_enter(name: *const Text, type_text: *const Text, sp: usize, site: usize) void { + const t = enter() orelse return; + defer t.inside = false; + put(t.tid, .call, 0, .{ name.id, site, sp, type_text.id, 0, 0 }, ""); +} + +export fn __zt_exit(name: *const Text, value: u64, size: u32) void { + const t = enter() orelse return; + defer t.inside = false; + put(t.tid, .ret, @intCast(size), .{ name.id, value, 0, 0, 0, 0 }, ""); +} + +export fn __zt_var(addr: usize, size: u64, name: *const Text, type_text: *const Text, arg: u32) void { + const t = enter() orelse return; + defer t.inside = false; + put(t.tid, .variable, @truncate(arg), .{ addr, size, name.id, type_text.id, 0, 0 }, ""); +} + +// Stock clang. + +export fn __sanitizer_cov_trace_pc_guard_init(_: *u32, _: *u32) void {} + +export fn __sanitizer_cov_trace_pc_guard(_: *u32) void { + emit(.edge, 0, .{ @returnAddress(), 0, 0, 0, 0, 0 }, ""); +} + +comptime { + for (.{ u8, u16, u32, u64 }) |T| { + const f = struct { + fn cmp(lhs: T, rhs: T) callconv(.c) void { + emit(.cmp, @sizeOf(T), .{ @returnAddress(), lhs, rhs, 0, 0, 0 }, ""); + } + }.cmp; + for (.{ "", "const_" }) |c| @export(&f, .{ .name = std.fmt.comptimePrint("__sanitizer_cov_trace_{s}cmp{d}", .{ c, @sizeOf(T) }) }); + } +} + +/// `cases` is (count, bits, values...). One event a switch, not one a case: +/// rhs is the case taken, or the first when it is the default. +export fn __sanitizer_cov_trace_switch(value: u64, cases: [*]const u64) void { + var rhs = cases[2]; + for (cases[2..][0..cases[0]]) |c| { + if (c == value) rhs = c; + } + emit(.cmp, @intCast(cases[1] / 8), .{ @returnAddress(), value, rhs, 0, 0, 0 }, ""); +} + +export fn __cyg_profile_func_enter(function: usize, site: usize) void { + emit(.call, 0, .{ function, site, @frameAddress(), 0, 0, 0 }, ""); +} + +export fn __cyg_profile_func_exit(function: usize, _: usize) void { + emit(.ret, 0, .{ function, 0, 0, 0, 0, 0 }, ""); +} diff --git a/src/instr/test.zig b/src/instr/test.zig new file mode 100644 index 0000000..3b67c62 --- /dev/null +++ b/src/instr/test.zig @@ -0,0 +1,464 @@ +//! The pass and the runtime on real programs: each test reads the recording +//! of a target the build compiled with `ztrace cc` and ran under `ztrace +//! run` (their paths come from build/llvm.zig), as a viewer would: names +//! and types from the recording alone. +const std = @import("std"); +const linux = std.os.linux; +const zt = @import("ztrace"); +const types = @import("types"); +const recordings = @import("recordings"); + +const gpa = std.testing.allocator; +const io = std.testing.io; +const expect = std.testing.expect; +const expectEqual = std.testing.expectEqual; +const expectEqualSlices = std.testing.expectEqualSlices; +const expectEqualStrings = std.testing.expectEqualStrings; + +const Item = struct { moment: u64, ev: zt.Event, payload: []const u8 }; + +/// A recording, its events in order with the moment each is in, and the id +/// the runtime gave each text. +const Recording = struct { + arena: std.heap.ArenaAllocator, + trace: zt.Trace, + items: []Item, + ids: std.StringHashMapUnmanaged(u64) = .empty, + + fn open(path: []const u8) !Recording { + var r: Recording = .{ .arena = .init(gpa), .trace = try zt.Trace.open(gpa, io, path), .items = &.{} }; + errdefer r.close(); + const arena = r.arena.allocator(); + var items: std.ArrayList(Item) = .empty; + for (0..r.trace.len) |m| { + var events = try (try r.trace.moment(m)).events(arena); + while (events.next()) |item| { + try items.append(arena, .{ .moment = m, .ev = item.ev, .payload = item.payload }); + if (item.ev.kind == .string) try r.ids.put(arena, item.payload, item.ev.a[0]); + } + } + r.items = items.items; + return r; + } + + /// The id of a text; 0, which nothing has, for one the program lacks. + fn id(r: *const Recording, text: []const u8) u64 { + return r.ids.get(text) orelse 0; + } + + fn close(r: *Recording) void { + r.trace.close(); + r.arena.deinit(); + } + + fn last(r: *const Recording) !zt.store.Moment { + return r.trace.moment(r.trace.len - 1); + } + + fn string(r: *Recording, of: u64) ![]const u8 { + const buf = try r.arena.allocator().alloc(u8, 4096); + return (try (try r.last()).string(of, buf)) orelse error.NoSuchString; + } + + /// The first `variable` event of that name and type. + fn variable(r: *Recording, name: []const u8, type_text: []const u8) !zt.Event { + for (r.items) |item| { + if (item.ev.kind == .variable and item.ev.a[2] == r.id(name) and item.ev.a[3] == r.id(type_text)) return item.ev; + } + return error.NoSuchVariable; + } + + fn count(r: *const Recording, kind: zt.Kind, a0: u64) usize { + var n: usize = 0; + for (r.items) |item| n += @intFromBool(item.ev.kind == kind and item.ev.a[0] == a0); + return n; + } + + /// `T` from the memory recorded as of a moment; every byte must be known. + fn read(moment: zt.store.Moment, comptime T: type, addr: u64) !T { + var out: T = undefined; + var known: [@sizeOf(T)]bool = undefined; + try moment.read(addr, std.mem.asBytes(&out), &known); + try expect(std.mem.allEqual(bool, &known, true)); + return out; + } +}; + +/// The calls of fib(n) from `at` on must be the tree of the source: each +/// declares its parameter and stores n in it (the recorder keeps the bytes +/// of a store only where they changed memory: the value is read there), +/// calls fib(n-1) then fib(n-2), and returns their sum from the frame it +/// entered. Returns the sum. +fn fibTree(r: *const Recording, at: *usize, calls: *usize, n: u32) !u32 { + const items = r.items; + const fib = r.id("fib"); + while (!((items[at.*].ev.kind == .call or items[at.*].ev.kind == .ret) and items[at.*].ev.a[0] == fib)) at.* += 1; + const call, const param, const store = .{ items[at.*].ev, items[at.* + 1].ev, items[at.* + 2] }; + at.* += 3; + calls.* += 1; + try expectEqual(zt.Kind.call, call.kind); + try expectEqual(r.id("fn(u32)u32"), call.a[3]); + try expectEqual(zt.Kind.variable, param.kind); + try expectEqual(@as(u16, 1), param.aux); + try expectEqual(r.id("n"), param.a[2]); + try expectEqual(zt.Kind.mem_write, store.ev.kind); + try expectEqual(param.a[0], store.ev.a[0]); + try expectEqual(n, try Recording.read(try r.trace.moment(store.moment), u32, param.a[0])); + + const result = if (n < 2) n else try fibTree(r, at, calls, n - 1) + try fibTree(r, at, calls, n - 2); + while (items[at.*].ev.kind != .ret) at.* += 1; + const ret = items[at.*].ev; + at.* += 1; + try expectEqual(fib, ret.a[0]); + try expectEqual(@as(u64, result), ret.a[1]); + try expectEqual(@as(u16, 4), ret.aux); + return result; +} + +test "fib: the call tree, arguments and results" { + var r = try Recording.open(recordings.fib); + defer r.close(); + var at: usize = 0; + var calls: usize = 0; + try expectEqual(@as(u32, 8), try fibTree(&r, &at, &calls, 6)); + try expectEqual(@as(usize, 25), calls); + try expectEqual(@as(usize, 25), r.count(.call, r.id("fib"))); + try expectEqual(@as(usize, 25), r.count(.ret, r.id("fib"))); + try expectEqualStrings("fib", try r.string(r.id("fib"))); + // Numbered from 1: a name costs a recording a byte or two each time. + try expect(r.id("fib") != 0 and r.id("fib") <= r.ids.count()); + + // The recorder's stack at the first fib(1): main, then fib six deep. + var seen: usize = 0; + const deepest = for (r.items) |item| { + if (item.ev.kind == .call and item.ev.a[0] == r.id("fib")) seen += 1; + if (seen == 6) break item; + } else unreachable; + const stack = try (try r.trace.moment(deepest.moment)).stack(gpa, deepest.ev.tid); + defer gpa.free(stack); + try expectEqual(@as(usize, 7), stack.len); + try expectEqual(r.id("main"), stack[0].function); + for (stack[1..], stack[0 .. stack.len - 1]) |frame, outer| { + try expectEqual(r.id("fib"), frame.function); + try expect(frame.sp < outer.sp); + } +} + +test "sort: both arrays end sorted, and the lines run as often as the source says" { + try sortChecks(recordings.sort); +} + +test "sort -O2: the optimizer keeps what the pass put in before it" { + try sortChecks(recordings.sort_O2); +} + +fn sortChecks(recording: []const u8) !void { + var r = try Recording.open(recording); + defer r.close(); + const unsorted = [8]i32{ 5, 2, 9, 1, 7, 3, 8, 4 }; + const sorted = [8]i32{ 1, 2, 3, 4, 5, 7, 8, 9 }; + for ([_][]const u8{ "bubbled", "inserted" }) |name| { + const v = try r.variable(name, "[8]i32"); + try expectEqual(@as(u64, 32), v.a[1]); + try expectEqual(sorted, try Recording.read(try r.last(), [8]i32, v.a[0])); + } + // The constant they are copied from is a global: known from the start. + const source = try r.variable("unsorted", "[8]i32"); + try expectEqual(unsorted, try Recording.read(try r.trace.moment(0), [8]i32, source.a[0])); + + // Inside bubble the recorder knows its locals, and the array as it then was. + const in_bubble = for (r.items) |item| { + if (item.ev.kind == .line and item.ev.tid != 0 and (try (try r.trace.moment(item.moment)).stack(r.arena.allocator(), item.ev.tid)).len == 2) break item; + } else unreachable; + const then = try r.trace.moment(in_bubble.moment); + try expectEqual(unsorted, try Recording.read(then, [8]i32, (try r.variable("bubbled", "[8]i32")).a[0])); + var depth_of_a: u32 = 0; + for (try then.variables(r.arena.allocator())) |v| { + if (v.name == r.id("a")) depth_of_a = v.depth; + } + try expectEqual(@as(u32, 2), depth_of_a); + // After main returned only the global is left. + const left = try (try r.last()).variables(r.arena.allocator()); + try expectEqual(@as(usize, 1), left.len); + try expectEqual(r.id("unsorted"), left[0].name); + + // Every line event is a line of the one source file, which the recording names. + var file: u64 = 0; + var hits: [64]u32 = @splat(0); + for (r.items) |item| { + if (item.ev.kind != .line) continue; + if (file == 0) file = item.ev.a[0]; + try expectEqual(file, item.ev.a[0]); + hits[item.ev.a[1]] += 1; + } + const path = try r.string(file); + try expect(std.mem.endsWith(u8, path, "targets/instr_sort.c")); + const text = try std.Io.Dir.cwd().readFileAlloc(io, path, r.arena.allocator(), .limited(1 << 20)); + // The array has 13 inversions: bubble sort swaps that often, insertion + // sort shifts that often. Bubble sort compares 8*7/2 times. + const expected = [_]struct { []const u8, u32 }{ + .{ "if (a[j] > a[j + 1]) {", 28 }, + .{ "a[j + 1] = t;", 13 }, + .{ "a[j + 1] = a[j];", 13 }, + .{ "int key = a[i];", 7 }, + .{ "bubble(bubbled, N);", 1 }, + }; + var found: usize = 0; + var lines = std.mem.splitScalar(u8, text, '\n'); + var number: usize = 1; + while (lines.next()) |line| : (number += 1) { + const code = std.mem.trim(u8, line, " "); + // No event on a line with no code. + if (code.len == 0 or std.mem.startsWith(u8, code, "//") or std.mem.startsWith(u8, code, "#")) try expectEqual(@as(u32, 0), hits[number]); + for (expected) |e| { + if (!std.mem.eql(u8, code, e[0])) continue; + try expectEqual(e[1], hits[number]); + found += 1; + } + } + try expectEqual(expected.len, found); +} + +/// The values of a list from `head` on, following `next` through the memory +/// recorded as of `moment`, by the offsets of the node's description. +fn listValues(moment: zt.store.Moment, node: types.Type, head: u64, out: []i32) ![]i32 { + var at = head; + var n: usize = 0; + while (at != 0) : (n += 1) { + out[n] = try Recording.read(moment, i32, at + node.field("value").?.offset); + at = try Recording.read(moment, u64, at + node.field("next").?.offset); + } + return out[0..n]; +} + +test "list: the recorded stores are the list, at every push and at the end" { + var r = try Recording.open(recordings.list); + defer r.close(); + const arena = r.arena.allocator(); + + // From the variable to the shape of a node, through the type descriptions. + const list = try r.variable("list", "*`struct node`"); + const pointer = try types.parse(arena, try r.string(list.a[3])); + const node = try types.parse(arena, try r.string(types.defId(pointer.pointer.named))); + try expectEqual(@as(?u64, 16), node.size()); + try expectEqualStrings("struct node", node.field("next").?.type.pointer.named); + + // Each push returns a list one longer: its squares, newest first. + var buf: [8]i32 = undefined; + var pushes: usize = 0; + for (r.items) |item| { + if (item.ev.kind != .ret or item.ev.a[0] != r.id("push")) continue; + pushes += 1; + const values = try listValues(try r.trace.moment(item.moment), node, item.ev.a[1], &buf); + try expectEqual(pushes, values.len); + for (values, 0..) |v, i| try expectEqual(@as(i32, @intCast((pushes - i) * (pushes - i))), v); + } + try expectEqual(@as(usize, 5), pushes); + + // Reversed in place, and left in the global. + const end = try r.last(); + const head = try Recording.read(end, u64, list.a[0]); + try expectEqualSlices(i32, &.{ 1, 4, 9, 16, 25 }, try listValues(end, node, head, &buf)); + const globals = try end.variables(arena); + try expectEqual(@as(usize, 1), globals.len); + try expectEqual(@as(u32, 0), globals[0].depth); +} + +test "bfs: distances and visiting order, the graph known from the start" { + var r = try Recording.open(recordings.bfs); + defer r.close(); + const end = try r.last(); + + const distance = try r.variable("distance", "[7]i32"); + try expectEqual([7]i32{ 0, 1, 1, 2, 3, 4, -1 }, try Recording.read(end, [7]i32, distance.a[0])); + const order = try r.variable("order", "[7]i32"); + try expectEqual([7]i32{ 0, 1, 2, 3, 4, 5, 0 }, try Recording.read(end, [7]i32, order.a[0])); + + // The edge list is constant: in the first moment already. The matrix + // main builds from it is symmetric and has each edge twice. + const edges = try Recording.read(try r.trace.moment(0), [6][2]i32, (try r.variable("edges", "[6][2]i32")).a[0]); + const adjacent = try Recording.read(end, [7][7]i32, (try r.variable("adjacent", "[7][7]i32")).a[0]); + var ones: usize = 0; + for (adjacent) |row| { + for (row) |cell| ones += @intCast(cell); + } + try expectEqual(2 * edges.len, ones); + for (edges) |e| try expectEqual(@as(i32, 1), adjacent[@intCast(e[1])][@intCast(e[0])]); + + // bfs returns how many it reached; its queue lived only during the call. + const queue = try r.variable("queue", "[7]i32"); + for (r.items) |item| { + if (item.ev.kind != .ret or item.ev.a[0] != r.id("bfs")) continue; + try expectEqual(@as(u64, 6), item.ev.a[1]); + try expectEqual([6]i32{ 0, 1, 2, 3, 4, 5 }, try Recording.read(try r.trace.moment(item.moment), [6]i32, queue.a[0])); + } + try expectEqual(@as(usize, 1), r.count(.ret, r.id("bfs"))); + for (try end.variables(r.arena.allocator())) |v| try expect(v.name != r.id("queue")); +} + +test "only: nothing outside the selection, by function name" { + var r = try Recording.open(recordings.sort_only); + defer r.close(); + // Of three functions and a global, bubble alone: its call, its five locals. + var calls: usize = 0; + var variables: usize = 0; + var writes: usize = 0; + for (r.items) |item| switch (item.ev.kind) { + .call => { + try expectEqual(r.id("bubble"), item.ev.a[0]); + calls += 1; + }, + .variable => variables += 1, + .mem_write => writes += 1, + .line => try expect(item.ev.a[1] >= 11 and item.ev.a[1] <= 21), + else => {}, + }; + try expectEqual(@as(usize, 1), calls); + try expectEqual(@as(usize, 5), variables); + try expect(writes > 13); + try expect(r.ids.get("bubble") != null and r.ids.get("insertion") == null and r.ids.get("unsorted") == null); +} + +test "mem: lines and calls in the whole file, stores in one function" { + var r = try Recording.open(recordings.sort_mem); + defer r.close(); + var full = try Recording.open(recordings.sort); + defer full.close(); + // The file's name selects all of it: every line and call of the full recording. + for ([_]zt.Kind{ .line, .call, .ret, .variable }) |kind| { + var here: usize = 0; + var there: usize = 0; + for (r.items) |item| here += @intFromBool(item.ev.kind == kind); + for (full.items) |item| there += @intFromBool(item.ev.kind == kind); + try expectEqual(there, here); + } + // Stores only while insertion runs; the one before is the global's contents. + var inside = false; + var writes: usize = 0; + for (r.items) |item| switch (item.ev.kind) { + .call, .ret => inside = item.ev.kind == .call and item.ev.a[0] == r.id("insertion"), + .mem_write => { + try expect(inside or item.ev.a[0] == (try r.variable("unsorted", "[8]i32")).a[0]); + writes += @intFromBool(inside); + }, + else => {}, + }; + try expect(writes > 13); +} + +test "big: a megabyte written is 64 KiB recorded" { + var r = try Recording.open(recordings.big); + defer r.close(); + const end = try r.last(); + for ([_][]const u8{ "from", "to" }) |name| { + const v = try r.variable(name, "[1048576]c8"); + var bytes: [(64 << 10) + 1]u8 = undefined; + var known: [bytes.len]bool = undefined; + try end.read(v.a[0], &bytes, &known); + try expect(std.mem.allEqual(u8, bytes[0 .. 64 << 10], 7)); + try expect(std.mem.allEqual(bool, known[0 .. 64 << 10], true)); + try expect(!known[64 << 10]); + } + // Four megabytes of globals and writes: four times 64 KiB, and the keyframe. + try expect((try std.Io.Dir.cwd().statFile(io, recordings.big, .{})).size < 1 << 20); + + // As the runtime emits them, before the recorder: pieces, each saying how + // much was written from its address on. + const arena = r.arena.allocator(); + const path = try arena.dupeSentinel(u8, recordings.big_program, 0); + var session = try zt.host.Session.spawn(arena, path, &.{ path, null }, &.{}, .{}); + defer session.close(); + const Pieces = struct { + name: u64 = 0, + from: u64 = 0, + bytes: u64 = 0, + first: u64 = 0, + last: u64 = 0, + + fn emit(ctx: *anyopaque, ev: *const zt.Event, payload: []const u8) anyerror!void { + const p: *@This() = @ptrCast(@alignCast(ctx)); + if (ev.kind == .string and std.mem.eql(u8, payload, "from")) p.name = ev.a[0]; + if (ev.kind == .variable and ev.a[2] == p.name) p.from = ev.a[0]; + // The memset, not the global's first contents. + if (ev.kind != .mem_write or ev.a[0] -% p.from >= 1 << 20 or payload[0] != 7) return; + try expect(payload.len <= 2048 and ev.a[1] >= payload.len); + if (p.bytes == 0) p.first = ev.a[1]; + p.bytes += payload.len; + p.last = ev.a[1]; + } + }; + var pieces: Pieces = .{}; + while (try session.pump(.{ .ctx = &pieces, .emitFn = Pieces.emit }, std.time.ns_per_ms)) {} + try expectEqual(@as(u64, 64 << 10), pieces.bytes); + try expectEqual(@as(u64, 1 << 20), pieces.first); + try expectEqual(@as(u64, (1 << 20) - (64 << 10) + 2048), pieces.last); +} + +test "own: a program's own memcpy is traced when the program calls it, not when the runtime does" { + var r = try Recording.open(recordings.own); + defer r.close(); + // Every mem_write the runtime emits it copies with this memcpy. + try expect(r.count(.mem_write, (try r.variable("to", "[8]c8")).a[0]) > 0); + try expectEqual(@as(usize, 1), r.count(.call, r.id("memcpy"))); + try expectEqual(@as(usize, 1), r.count(.call, r.id("strlen"))); + for (r.items) |item| { + if (item.ev.kind == .ret and item.ev.a[0] == r.id("strlen")) try expectEqual(@as(u64, 7), item.ev.a[1]); + } + try expectEqualStrings("abcdefg", std.mem.sliceTo(&try Recording.read(try r.last(), [8]u8, (try r.variable("to", "[8]c8")).a[0]), 0)); +} + +test "step: the ring holds the target at every line, its memory there to read" { + var r = try Recording.open(recordings.sort); + defer r.close(); + const arena = r.arena.allocator(); + var lines: usize = 0; + for (r.items) |item| lines += @intFromBool(item.ev.kind == .line); + + const path = try arena.dupeSentinel(u8, recordings.sort_program, 0); + var session = try zt.host.Session.spawn(arena, path, &.{ path, null }, &.{}, .{ .stop_mask = zt.Kind.line.bit() }); + defer session.close(); + const ring = &session.ring; + + // The array as the events so far say it is, against the target's own. + var name: u64 = 0; + var addr: u64 = 0; + var told: [32]u8 = @splat(0); + var compared: usize = 0; + var stops: usize = 0; + while (true) { + const rec = ring.peek() orelse { + if (session.exit_code != null) break; + var status: u32 = 0; + if (linux.waitpid(session.pid, @ptrCast(&status), linux.W.NOHANG) != 0) session.exit_code = linux.W.EXITSTATUS(status) else ring.wait(std.time.ns_per_ms); + continue; + }; + const ev = rec.ev.*; + if (ev.kind == .string and std.mem.eql(u8, rec.payload, "bubbled")) name = ev.a[0]; + if (ev.kind == .variable and ev.a[2] == name) addr = ev.a[0]; + if (ev.kind == .mem_write and ev.a[0] >= addr and ev.a[0] + ev.a[1] <= addr + told.len) { + @memcpy(told[ev.a[0] - addr ..][0..rec.payload.len], rec.payload); + // From the first copy into it on; before, it is whatever the stack held. + compared += @intFromBool(compared == 0 and rec.payload.len == told.len); + } + ring.advance(rec); + if (ev.kind != .line) continue; + + // Held: it emits nothing more until resumed. + while (ring.hdr.stopped.load(.acquire) == 0) std.atomic.spinLoopHint(); + try expect(ring.peek() == null); + var live: [32]u8 = undefined; + const local = [_]std.posix.iovec{.{ .base = &live, .len = live.len }}; + const remote = [_]std.posix.iovec_const{.{ .base = @ptrFromInt(addr), .len = live.len }}; + try expectEqual(live.len, linux.process_vm_readv(session.pid, &local, &remote, 0)); + if (compared > 0) { + try expectEqualSlices(u8, &told, &live); + compared += 1; + } + stops += 1; + ring.resumeAll(); + } + try expectEqual(lines, stops); + try expect(compared > lines - 16); + try expectEqual(@as(?u8, 10), session.exit_code); + try expectEqualSlices(i32, &.{ 1, 2, 3, 4, 5, 7, 8, 9 }, &std.mem.bytesToValue([8]i32, &told)); +} diff --git a/src/instr/types.zig b/src/instr/types.zig new file mode 100644 index 0000000..1f6615a --- /dev/null +++ b/src/instr/types.zig @@ -0,0 +1,215 @@ +//! The type descriptions the pass (llvm/pass.cpp) attaches to variables and +//! functions: what a viewer needs to draw a value from its bytes, with no +//! DWARF. A `variable` event's a3 and a `call` event's a3 are the string ids +//! of one: +//! +//! type := 'void' +//! | KIND BITS i32 u64 f64, c8 a character, b8 a boolean, x128 opaque bits +//! | '*' type a pointer or a reference: 8 bytes +//! | '[' COUNT ']' type an array; [3][4]i32 is three rows of four +//! | 'fn(' (type (',' type)*)? ')' type a function: its parameters ('...' when variadic), its result +//! | ('struct' | 'union') '(' BYTES '){' field* '}' +//! | 'enum(' type '){' (NAME '=' VALUE ';')* '}' +//! | '`' NAME '`' a named type, described elsewhere +//! field := NAME '@' BYTE ('.' BIT)? ':' type ';' +//! +//! A field sits at a byte offset. A bit-field adds the bit it starts at +//! within that byte, counted from the least significant, and is as wide as +//! its type: `[email protected]:u1`. An anonymous member or a C++ base has an empty +//! NAME. A flexible or variable-length array has COUNT 0. +//! +//! A named type is `struct NAME`, `union NAME`, `enum NAME`, or a typedef's +//! bare name (in C++ qualified: `struct v8::internal::Isolate`). What it is +//! is one more string, with the id `defId(NAME)`: of all the pass's string +//! ids (small numbers, given when the program starts) the only ones that +//! follow from a text. A type the program only declares has none. So a +//! struct is described once however many variables have it, and one that +//! points to itself ends: +//! +//! struct node { int value; struct node *next; } *head; +//! size_t n; +//! +//! type of head *`struct node` +//! defId("struct node") struct(16){value@0:i32;next@8:*`struct node`;} +//! type of n `size_t` +//! defId("size_t") u64 +const std = @import("std"); + +pub const Type = union(enum) { + void, + scalar: Scalar, + pointer: *const Type, + array: struct { len: u64, elem: *const Type }, + function: struct { params: []const Type, variadic: bool, result: *const Type }, + record: struct { kind: enum { @"struct", @"union" }, size: u64, fields: []const Field }, + @"enum": struct { base: *const Type, items: []const Item }, + /// Look its description up at `defId`. + named: []const u8, + + /// Bytes a value takes. Null for void, a function, and a named type: + /// resolve the name first. + pub fn size(t: Type) ?u64 { + return switch (t) { + .void, .function, .named => null, + .scalar => |s| (s.bits + 7) / 8, + .pointer => 8, + .array => |a| a.len * (a.elem.size() orelse return null), + .record => |r| r.size, + .@"enum" => |e| e.base.size(), + }; + } + + /// The field of a struct or union by name. + pub fn field(t: Type, name: []const u8) ?Field { + if (t != .record) return null; + for (t.record.fields) |f| { + if (std.mem.eql(u8, f.name, name)) return f; + } + return null; + } +}; + +pub const Scalar = struct { + kind: enum(u8) { int = 'i', uint = 'u', float = 'f', char = 'c', bool = 'b', @"opaque" = 'x' }, + bits: u16, +}; + +pub const Field = struct { name: []const u8, offset: u64, bit: u3 = 0, type: Type }; +pub const Item = struct { name: []const u8, value: i128 }; + +/// The string id of the description of the named type `name`: FNV-1a of +/// "=" and the name, with the top bit, which no numbered id has. +pub fn defId(name: []const u8) u64 { + var h = std.hash.Fnv1a_64.init(); + h.update("="); + h.update(name); + return h.final() | 1 << 63; +} + +pub const Error = error{ BadType, OutOfMemory }; + +/// A description as a tree, allocated in `arena`; its names point into `text`. +pub fn parse(arena: std.mem.Allocator, text: []const u8) Error!Type { + var p: Parser = .{ .arena = arena, .text = text }; + const t = try p.type(); + return if (p.at == text.len) t else error.BadType; +} + +const Parser = struct { + arena: std.mem.Allocator, + text: []const u8, + at: usize = 0, + + fn eat(p: *Parser, word: []const u8) bool { + if (!std.mem.startsWith(u8, p.text[p.at..], word)) return false; + p.at += word.len; + return true; + } + + /// The text up to `end`, which is consumed. + fn until(p: *Parser, end: u8) ![]const u8 { + const len = std.mem.indexOfScalar(u8, p.text[p.at..], end) orelse return error.BadType; + defer p.at += len + 1; + return p.text[p.at..][0..len]; + } + + fn number(p: *Parser, comptime T: type, end: u8) !T { + return std.fmt.parseInt(T, try p.until(end), 10) catch error.BadType; + } + + fn box(p: *Parser, t: Type) !*const Type { + const out = try p.arena.create(Type); + out.* = t; + return out; + } + + fn @"type"(p: *Parser) Error!Type { + if (p.eat("void")) return .void; + if (p.eat("*")) return .{ .pointer = try p.box(try p.type()) }; + if (p.eat("`")) return .{ .named = try p.until('`') }; + if (p.eat("[")) { + const len = try p.number(u64, ']'); + return .{ .array = .{ .len = len, .elem = try p.box(try p.type()) } }; + } + if (p.eat("fn(")) { + var params: std.ArrayList(Type) = .empty; + var variadic = false; + while (!p.eat(")")) { + if (p.eat("...")) variadic = true else try params.append(p.arena, try p.type()); + _ = p.eat(","); + } + return .{ .function = .{ .params = params.items, .variadic = variadic, .result = try p.box(try p.type()) } }; + } + if (p.eat("enum(")) { + const base = try p.box(try p.type()); + if (!p.eat("){")) return error.BadType; + var items: std.ArrayList(Item) = .empty; + while (!p.eat("}")) try items.append(p.arena, .{ .name = try p.until('='), .value = try p.number(i128, ';') }); + return .{ .@"enum" = .{ .base = base, .items = items.items } }; + } + const is_union = p.eat("union("); + if (is_union or p.eat("struct(")) { + const bytes = try p.number(u64, ')'); + if (!p.eat("{")) return error.BadType; + var fields: std.ArrayList(Field) = .empty; + while (!p.eat("}")) { + var f: Field = .{ .name = try p.until('@'), .offset = 0, .type = .void }; + var place = std.mem.splitScalar(u8, try p.until(':'), '.'); + f.offset = std.fmt.parseInt(u64, place.first(), 10) catch return error.BadType; + if (place.next()) |bit| f.bit = std.fmt.parseInt(u3, bit, 10) catch return error.BadType; + f.type = try p.type(); + if (!p.eat(";")) return error.BadType; + try fields.append(p.arena, f); + } + return .{ .record = .{ .kind = if (is_union) .@"union" else .@"struct", .size = bytes, .fields = fields.items } }; + } + if (p.at < p.text.len and std.mem.indexOfScalar(u8, "iufcbx", p.text[p.at]) != null) { + const start = p.at + 1; + p.at = start; + while (p.at < p.text.len and std.ascii.isDigit(p.text[p.at])) p.at += 1; + return .{ .scalar = .{ .kind = @enumFromInt(p.text[start - 1]), .bits = std.fmt.parseInt(u16, p.text[start..p.at], 10) catch return error.BadType } }; + } + return error.BadType; + } +}; + +test "descriptions parse to what the pass meant" { + var arena_state: std.heap.ArenaAllocator = .init(std.testing.allocator); + defer arena_state.deinit(); + const arena = arena_state.allocator(); + + const node = try parse(arena, "struct(16){value@0:i32;next@8:*`struct node`;}"); + try std.testing.expectEqual(@as(?u64, 16), node.size()); + try std.testing.expectEqual(Scalar{ .kind = .int, .bits = 32 }, node.field("value").?.type.scalar); + const next = node.field("next").?; + try std.testing.expectEqual(@as(u64, 8), next.offset); + try std.testing.expectEqualStrings("struct node", next.type.pointer.named); + try std.testing.expect(node.field("prev") == null); + + // Bit-fields, an anonymous union member, an array of arrays. + const bits = try parse(arena, "struct(24){[email protected]:u3;[email protected]:i5;@8:union(8){d@0:f64;p@0:*void;};m@16:[2][3]c8;}"); + try std.testing.expectEqual(@as(u3, 3), bits.field("b").?.bit); + try std.testing.expectEqual(Scalar{ .kind = .int, .bits = 5 }, bits.field("b").?.type.scalar); + try std.testing.expectEqual(@as(usize, 2), bits.field("").?.type.record.fields.len); + try std.testing.expectEqual(@as(?u64, 6), bits.field("m").?.type.size()); + try std.testing.expectEqual(@as(u64, 3), bits.field("m").?.type.array.elem.array.len); + + const f = (try parse(arena, "fn(*`struct node`,i32,...)*c8")).function; + try std.testing.expectEqual(@as(usize, 2), f.params.len); + try std.testing.expect(f.variadic); + try std.testing.expectEqual(Scalar{ .kind = .char, .bits = 8 }, f.result.pointer.scalar); + try std.testing.expectEqual(Type.void, (try parse(arena, "fn()void")).function.result.*); + + const e = (try parse(arena, "enum(i32){LOW=-1;HIGH=5;}")).@"enum"; + try std.testing.expectEqualStrings("HIGH", e.items[1].name); + try std.testing.expectEqual(@as(i128, -1), e.items[0].value); + // A name may hold anything but a backquote. + try std.testing.expectEqualStrings("struct std::pair<int, char *>", (try parse(arena, "[4]`struct std::pair<int, char *>`")).array.elem.named); + + for ([_][]const u8{ "", "i", "i32x", "struct(8){a@0:i32}", "[x]i32", "*", "`open", "fn(i32" }) |bad| try std.testing.expectError(error.BadType, parse(arena, bad)); + + // FNV-1a of "=", worked out by hand. That the pass agrees is the list + // test of src/instr/test.zig, on a real program. + try std.testing.expectEqual(@as(u64, 0xaf63b04c8601a1c8), defId("")); + try std.testing.expectEqual(@as(u64, 1), defId("size_t") >> 63); +} diff --git a/targets/instr_bfs.c b/targets/instr_bfs.c new file mode 100644 index 0000000..a7b176e --- /dev/null +++ b/targets/instr_bfs.c @@ -0,0 +1,39 @@ +// Breadth-first search from vertex 0 of a seven-vertex graph, one vertex +// out of reach, argv[1] times (by default once). Exits with the number of +// vertices reached. +#include <stdlib.h> + +#define N 7 +static const int edges[][2] = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}}; +static int adjacent[N][N]; +static int distance[N]; +static int order[N]; + +static int bfs(int from) { + int queue[N], head = 0, tail = 0; + for (int v = 0; v < N; v++) distance[v] = -1; + distance[from] = 0; + queue[tail++] = from; + while (head < tail) { + int v = queue[head]; + order[head++] = v; + for (int w = 0; w < N; w++) { + if (adjacent[v][w] && distance[w] < 0) { + distance[w] = distance[v] + 1; + queue[tail++] = w; + } + } + } + return tail; +} + +int main(int argc, char **argv) { + int rounds = argc > 1 ? atoi(argv[1]) : 1; + int reached = 0; + for (unsigned i = 0; i < sizeof edges / sizeof *edges; i++) { + adjacent[edges[i][0]][edges[i][1]] = 1; + adjacent[edges[i][1]][edges[i][0]] = 1; + } + while (rounds-- > 0) reached = bfs(0); + return reached; +} diff --git a/targets/instr_big.c b/targets/instr_big.c new file mode 100644 index 0000000..ce89947 --- /dev/null +++ b/targets/instr_big.c @@ -0,0 +1,11 @@ +// A megabyte set, then copied: a recording keeps the first 64 KiB of each +// write. Exits with the last byte copied. +#include <string.h> + +static char from[1 << 20], to[1 << 20]; + +int main(void) { + memset(from, 7, sizeof from); + memcpy(to, from, sizeof to); + return to[sizeof to - 1]; +} diff --git a/targets/instr_fib.c b/targets/instr_fib.c new file mode 100644 index 0000000..9da9306 --- /dev/null +++ b/targets/instr_fib.c @@ -0,0 +1,12 @@ +// fib(n) the slow way: a call tree to draw. Exits with fib(argv[1]), by +// default fib(6). +#include <stdlib.h> + +static unsigned fib(unsigned n) { + if (n < 2) return n; + return fib(n - 1) + fib(n - 2); +} + +int main(int argc, char **argv) { + return (int)fib(argc > 1 ? (unsigned)atoi(argv[1]) : 6); +} diff --git a/targets/instr_list.c b/targets/instr_list.c new file mode 100644 index 0000000..aaa6c8a --- /dev/null +++ b/targets/instr_list.c @@ -0,0 +1,46 @@ +// A linked list of five squares, built at its head and then reversed in +// place, argv[1] times (by default once). The last list is left standing. +// Exits with the sum of its values. +#include <stdlib.h> + +struct node { + int value; + struct node *next; +}; + +static struct node *list; + +static struct node *push(struct node *head, int value) { + struct node *n = malloc(sizeof *n); + n->value = value; + n->next = head; + return n; +} + +static struct node *reverse(struct node *head) { + struct node *prev = NULL; + while (head) { + struct node *next = head->next; + head->next = prev; + prev = head; + head = next; + } + return prev; +} + +int main(int argc, char **argv) { + int rounds = argc > 1 ? atoi(argv[1]) : 1; + int sum = 0; + while (rounds-- > 0) { + while (list) { + struct node *next = list->next; + free(list); + list = next; + } + for (int i = 1; i <= 5; i++) list = push(list, i * i); + list = reverse(list); + sum = 0; + for (struct node *n = list; n; n = n->next) sum += n->value; + } + return sum; +} diff --git a/targets/instr_own.c b/targets/instr_own.c new file mode 100644 index 0000000..5c30141 --- /dev/null +++ b/targets/instr_own.c @@ -0,0 +1,27 @@ +// A program with its own memcpy and strlen, as one linked with a libc +// compiled by the pass has: the runtime calls them too, and must not trace +// itself. Exits with the length of the string it copied. +#include <stddef.h> + +void *memcpy(void *to, const void *from, size_t n) { + char *d = to; + const char *s = from; + for (size_t i = 0; i < n; i++) d[i] = s[i]; + return to; +} + +size_t strlen(const char *s) { + size_t n = 0; + while (s[n]) n++; + return n; +} + +// Through pointers: the compiler would do a known memcpy inline. +void *(*volatile copy)(void *, const void *, size_t) = memcpy; +size_t (*volatile length)(const char *) = strlen; + +int main(void) { + char to[8], from[8] = "abcdefg"; + copy(to, from, sizeof from); + return (int)length(to); +} diff --git a/targets/instr_sort.c b/targets/instr_sort.c new file mode 100644 index 0000000..411b348 --- /dev/null +++ b/targets/instr_sort.c @@ -0,0 +1,44 @@ +// Bubble sort and insertion sort of the same eight numbers, argv[1] times +// (by default once). Exits with the smallest plus the largest. +#include <stdlib.h> +#include <string.h> + +#define N 8 +// Not const, not static: -O2 must sort at run time, not when compiling. +int unsorted[N] = {5, 2, 9, 1, 7, 3, 8, 4}; + +static void bubble(int *a, int n) { + for (int i = 0; i < n - 1; i++) { + for (int j = 0; j < n - 1 - i; j++) { + if (a[j] > a[j + 1]) { + int t = a[j]; + a[j] = a[j + 1]; + a[j + 1] = t; + } + } + } +} + +static void insertion(int *a, int n) { + for (int i = 1; i < n; i++) { + int key = a[i]; + int j = i - 1; + while (j >= 0 && a[j] > key) { + a[j + 1] = a[j]; + j--; + } + a[j + 1] = key; + } +} + +int main(int argc, char **argv) { + int rounds = argc > 1 ? atoi(argv[1]) : 1; + int bubbled[N], inserted[N]; + while (rounds-- > 0) { + memcpy(bubbled, unsorted, sizeof unsorted); + memcpy(inserted, unsorted, sizeof unsorted); + bubble(bubbled, N); + insertion(inserted, N); + } + return bubbled[0] + inserted[N - 1]; +} |
