From: Anton Protopopov int f(struct file *file, int mode) { int ret = -EINVAL; if (mode & ~MASK) goto out; ret = g(file); out: return ret; } Which constants does f() return? A compiler loads a constant into any register. Copies, sign extensions and selects carry it to the return value register. Run a data flow analysis on the instructions of one function. It is backward and "may", like liveness. The fact at a point is the set of registers whose value may become the return value: fact before the instruction mov $0xffffffea,%ebx {} -22 is returned test $0xfffffff8,%esi {rbx} jne 1f {rbx} join: {} + {rbx} call g {} a call writes rax mov %eax,%ebx {rax} 1: mov %ebx,%eax {rbx} ret {rax} transfer functions and join return { return value register } dst = src src takes the place of dst another write the register leaves the set call the caller-saved registers leave the set join union An instruction that loads a constant into dst is a definition that reaches the return value, if dst is in the fact after it. One run answers the question for all constants of the function. It is a may analysis. Branches are not evaluated: a constant counts if a path of the control flow graph carries it. Memory is not tracked: a constant that is spilled to the stack is not found. "mov $-22,%eax" makes 0xffffffea. That is an error for a function that returns int. For a function that returns long it is a large number, unless cltq follows. So there are three sets: returned as it is, zero extended, sign extended. Nothing in the analysis depends on the arch. Signed-off-by: Anton Protopopov Co-developed-by: Alexei Starovoitov Signed-off-by: Alexei Starovoitov --- tools/bpf/resolve_btfids/Build | 4 + tools/bpf/resolve_btfids/text_flow.c | 145 +++++++++++++++++++++++++++ tools/bpf/resolve_btfids/text_flow.h | 44 ++++++++ 3 files changed, 193 insertions(+) create mode 100644 tools/bpf/resolve_btfids/text_flow.c create mode 100644 tools/bpf/resolve_btfids/text_flow.h diff --git a/tools/bpf/resolve_btfids/Build b/tools/bpf/resolve_btfids/Build index b9e5bf21439f..cd42283bb929 100644 --- a/tools/bpf/resolve_btfids/Build +++ b/tools/bpf/resolve_btfids/Build @@ -3,6 +3,7 @@ hostprogs := resolve_btfids resolve_btfids-y += main.o resolve_btfids-y += btf_colors.o resolve_btfids-y += image.o +resolve_btfids-y += text_flow.o resolve_btfids-$(LLVM_MC) += text_mc.o resolve_btfids-$(LLVM_MC) += text_mc_$(SRCARCH).o resolve_btfids-y += rbtree.o @@ -11,6 +12,9 @@ resolve_btfids-y += string.o resolve_btfids-y += ctype.o resolve_btfids-y += str_error_r.o +# The inner loops of --fmodret_scan +HOSTCFLAGS_text_flow.o += -O2 + # LLVM's C++ API may have moved on, see Makefile $(OUTPUT)text_mc.o: cmd_cxx_o_c += $(or_llvm_mc_help) diff --git a/tools/bpf/resolve_btfids/text_flow.c b/tools/bpf/resolve_btfids/text_flow.c new file mode 100644 index 000000000000..2d58ffb2e939 --- /dev/null +++ b/tools/bpf/resolve_btfids/text_flow.c @@ -0,0 +1,145 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* Which values does a function return? See text_flow.h */ + +#include +#include + +#include "text_flow.h" + +/* Return the index of the instruction which runs after I if I does not branch */ +static u32 next_insn(const struct text_flow *flow, u32 i) +{ + const struct text_insn *insn = &flow->insns[i]; + + /* A function and its cold subfunctions are not adjacent */ + return i + 1 < flow->nr_insns && insn[1].addr == insn->addr + insn->len ? + i + 1 : TEXT_NO_INSN; +} + +static u32 insn_at(const struct text_flow *flow, u64 addr) +{ + u32 lo = 0, hi = flow->nr_insns; + + while (lo < hi) { + u32 mid = lo + (hi - lo) / 2; + + if (flow->insns[mid].addr < addr) + lo = mid + 1; + else + hi = mid; + } + return lo < flow->nr_insns && flow->insns[lo].addr == addr ? lo : TEXT_NO_INSN; +} + +static void join(struct text_facts *facts, const struct text_flow *flow, u32 i) +{ + if (i == TEXT_NO_INSN) + return; + facts->same |= flow->facts[i].same; + facts->zext |= flow->facts[i].zext; + facts->sext |= flow->facts[i].sext; +} + +static void kill(struct text_facts *facts, u32 regs) +{ + facts->same &= ~regs; + facts->zext &= ~regs; + facts->sext &= ~regs; +} + +enum cast { SAME, ZEXT, SEXT }; + +/* The facts of DST behind "dst = cast(src)" are those of SRC before it */ +static void copy(struct text_facts *in, const struct text_facts *out, u8 dst, u8 src, + enum cast cast) +{ + bool same = out->same & BIT(dst), zext = out->zext & BIT(dst), sext = out->sext & BIT(dst); + + if (same && cast == SAME) + in->same |= BIT(src); + if (zext || (same && cast == ZEXT)) + in->zext |= BIT(src); + if (sext || (same && cast == SEXT)) + in->sext |= BIT(src); +} + +/* Return the facts before instruction I */ +static struct text_facts transfer(const struct text_flow *flow, u32 i) +{ + const struct text_insn *insn = &flow->insns[i]; + struct text_facts out = {}, in; + enum cast cast; + + switch (insn->kind) { + case TEXT_RETURN: + out.same = BIT(flow->arch->retval); + return out; + case TEXT_BRANCH: + join(&out, flow, insn->target); + return out; + case TEXT_COND_BRANCH: + join(&out, flow, insn->target); + break; + } + join(&out, flow, next_insn(flow, i)); + + in = out; + kill(&in, insn->defs); + switch (insn->kind) { + case TEXT_CALL: + kill(&in, flow->arch->caller_saved); + break; + case TEXT_MOV_IMM: + kill(&in, BIT(insn->dst)); + break; + case TEXT_MOV: + case TEXT_SEXT32: + case TEXT_SELECT: + case TEXT_SELECT_IMM: + cast = insn->kind == TEXT_SEXT32 ? SEXT : insn->is32 ? ZEXT : SAME; + kill(&in, BIT(insn->dst)); + copy(&in, &out, insn->dst, insn->src, cast); + if (insn->kind == TEXT_SELECT) + copy(&in, &out, insn->dst, insn->src2, cast); + break; + } + return in; +} + +/* + * Sweep from the last instruction to the first one until nothing changes. The + * sets only grow, and one more sweep is needed only for what goes around a loop. + */ +void text_flow_solve(struct text_flow *flow) +{ + bool changed; + u32 i; + + for (i = 0; i < flow->nr_insns; i++) { + struct text_insn *insn = &flow->insns[i]; + + flow->facts[i] = (struct text_facts){}; + insn->target = TEXT_NO_INSN; + if ((insn->kind == TEXT_BRANCH || insn->kind == TEXT_COND_BRANCH) && insn->imm) + insn->target = insn_at(flow, insn->imm); + } + do { + changed = false; + for (i = flow->nr_insns; i--; ) { + struct text_facts *old = &flow->facts[i], new = transfer(flow, i); + + if (new.same == old->same && new.zext == old->zext && new.sext == old->sext) + continue; + *old = new; + changed = true; + } + } while (changed); +} + +struct text_facts text_flow_out(const struct text_flow *flow, u32 i) +{ + struct text_facts out = {}; + + join(&out, flow, next_insn(flow, i)); + return out; +} diff --git a/tools/bpf/resolve_btfids/text_flow.h b/tools/bpf/resolve_btfids/text_flow.h new file mode 100644 index 000000000000..b307c08fd163 --- /dev/null +++ b/tools/bpf/resolve_btfids/text_flow.h @@ -0,0 +1,44 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +#ifndef __TEXT_FLOW_H +#define __TEXT_FLOW_H + +#include "text_insn.h" + +/* + * Which values does a function return? A backward may data flow analysis of + * the machine code of one function. + * + * The fact at a point of the code is the set of registers whose value at that + * point may become the return value: the return value register at a return, + * and before "dst = src" the register src if dst is in the set behind it. The + * join is the union. Branches are not evaluated, calls write what the ABI lets + * them write, memory is not tracked. + * + * A copy may convert the value, and only the last conversion counts. So there + * are three sets. + */ +struct text_facts { + u32 same; /* returned as it is */ + u32 zext; /* the low 32 bits are returned, zero extended */ + u32 sext; /* the low 32 bits are returned, sign extended */ +}; + +struct text_flow { + const struct text_arch *arch; + /* + * All instructions of the function in the order of their addresses, + * whether they can be reached or not: the way to a block may be a jump + * which is patched in at run time, or an exception. + */ + struct text_insn *insns; + u32 nr_insns; + /* The result: the facts before each instruction */ + struct text_facts *facts; +}; + +/* Compute the facts */ +void text_flow_solve(struct text_flow *flow); +/* Return the facts behind instruction I, which is not a branch */ +struct text_facts text_flow_out(const struct text_flow *flow, u32 i); + +#endif -- 2.55.0