#include <linux/bpf_verifier.h>
#include <linux/btf.h>
#include <linux/hashtable.h>
#include <linux/jhash.h>
#include <linux/slab.h>
#include <linux/sort.h>
#define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args)
#define FRAME_HALF_SPIS (MAX_BPF_STACK_JIT / BPF_HALF_REG_SIZE)
#define FRAME_MAX_WORDS BITS_TO_LONGS(FRAME_HALF_SPIS)
enum {
FM_MAY_READ,
FM_MUST_WRITE,
FM_LIVE_BEFORE,
FM_MAY_WRITE,
FM_MASK_CNT,
};
struct frame_masks {
u32 words;
unsigned long bits[];
};
struct func_instance {
struct hlist_node hl_node;
u32 callsite;
u32 depth;
u32 subprog;
u32 subprog_start;
u32 insn_cnt;
struct frame_masks *frames[MAX_CALL_FRAMES];
bool must_write_initialized;
};
struct live_stack_query {
struct func_instance *instances[MAX_CALL_FRAMES];
u32 callsites[MAX_CALL_FRAMES];
u32 curframe;
u32 insn_idx;
};
struct bpf_liveness {
DECLARE_HASHTABLE(func_instances, 8);
struct live_stack_query live_stack_query;
u32 subprog_calls;
};
static u32 instance_hash(u32 callsite, u32 depth)
{
u32 key[2] = { depth, callsite };
return jhash2(key, 2, 0);
}
static struct func_instance *find_instance(struct bpf_verifier_env *env,
u32 callsite, u32 depth)
{
struct bpf_liveness *liveness = env->liveness;
struct func_instance *f;
u32 key = instance_hash(callsite, depth);
hash_for_each_possible(liveness->func_instances, f, hl_node, key)
if (f->depth == depth && f->callsite == callsite)
return f;
return NULL;
}
static struct func_instance *call_instance(struct bpf_verifier_env *env,
struct func_instance *caller,
u32 callsite, int subprog)
{
u32 depth = caller ? caller->depth + 1 : 0;
u32 subprog_start = env->subprog_info[subprog].start;
u32 lookup_key = depth > 0 ? callsite : subprog_start;
struct func_instance *f;
u32 hash;
f = find_instance(env, lookup_key, depth);
if (f)
return f;
f = kvzalloc_obj(*f, GFP_KERNEL_ACCOUNT);
if (!f)
return ERR_PTR(-ENOMEM);
f->callsite = lookup_key;
f->depth = depth;
f->subprog = subprog;
f->subprog_start = subprog_start;
f->insn_cnt = (env->subprog_info + subprog + 1)->start - subprog_start;
hash = instance_hash(lookup_key, depth);
hash_add(env->liveness->func_instances, &f->hl_node, hash);
return f;
}
static struct func_instance *lookup_instance(struct bpf_verifier_env *env,
struct bpf_verifier_state *st,
u32 frameno)
{
u32 callsite, subprog_start;
struct func_instance *f;
u32 key, depth;
subprog_start = env->subprog_info[st->frame[frameno]->subprogno].start;
callsite = frameno > 0 ? st->frame[frameno]->callsite : subprog_start;
for (depth = frameno; ; depth--) {
key = depth > 0 ? callsite : subprog_start;
f = find_instance(env, key, depth);
if (f || depth == 0)
return f;
}
}
int bpf_stack_liveness_init(struct bpf_verifier_env *env)
{
env->liveness = kvzalloc_obj(*env->liveness, GFP_KERNEL_ACCOUNT);
if (!env->liveness)
return -ENOMEM;
hash_init(env->liveness->func_instances);
return 0;
}
void bpf_stack_liveness_free(struct bpf_verifier_env *env)
{
struct func_instance *instance;
struct hlist_node *tmp;
int bkt, i;
if (!env->liveness)
return;
hash_for_each_safe(env->liveness->func_instances, bkt, tmp, instance, hl_node) {
for (i = 0; i <= instance->depth; i++)
kvfree(instance->frames[i]);
kvfree(instance);
}
kvfree(env->liveness);
}
static int relative_idx(struct func_instance *instance, u32 insn_idx)
{
return insn_idx - instance->subprog_start;
}
static u32 frame_mask_bits(struct frame_masks *fm)
{
return fm->words * BITS_PER_LONG;
}
static size_t frame_mask_words(struct func_instance *instance, u32 words)
{
return (size_t)instance->insn_cnt * FM_MASK_CNT * words;
}
static unsigned long *rel_mask(struct frame_masks *fm, u32 rel, u32 kind)
{
return fm->bits + ((size_t)rel * FM_MASK_CNT + kind) * fm->words;
}
static struct frame_masks *widen_frame_masks(struct func_instance *instance,
u32 frame, u32 words)
{
struct frame_masks *old = instance->frames[frame], *new;
u32 i, kind;
if (old && old->words >= words)
return old;
new = kvzalloc_flex(*new, bits, frame_mask_words(instance, words), GFP_KERNEL_ACCOUNT);
if (!new)
return NULL;
new->words = words;
if (old) {
for (i = 0; i < instance->insn_cnt; i++)
for (kind = 0; kind < FM_MASK_CNT; kind++)
memcpy(rel_mask(new, i, kind), rel_mask(old, i, kind),
old->words * sizeof(*old->bits));
kvfree(old);
}
instance->frames[frame] = new;
return new;
}
static int mark_stack_range(struct func_instance *instance, u32 frame, u32 insn_idx,
u32 kind, s32 lo, s32 hi)
{
struct frame_masks *fm;
hi = min_t(s32, hi, FRAME_HALF_SPIS - 1);
if (lo > hi)
return 0;
fm = widen_frame_masks(instance, frame, BITS_TO_LONGS(hi + 1));
if (!fm)
return -ENOMEM;
bitmap_set(rel_mask(fm, relative_idx(instance, insn_idx), kind), lo, hi - lo + 1);
return 0;
}
static int mark_stack_read(struct func_instance *instance, u32 frame, u32 insn_idx,
s32 lo, s32 hi)
{
return mark_stack_range(instance, frame, insn_idx, FM_MAY_READ, lo, hi);
}
static int mark_stack_write(struct func_instance *instance, u32 frame, u32 insn_idx,
s32 lo, s32 hi)
{
return mark_stack_range(instance, frame, insn_idx, FM_MUST_WRITE, lo, hi);
}
static int mark_stack_may_write(struct func_instance *instance, u32 frame, u32 insn_idx,
s32 lo, s32 hi)
{
return mark_stack_range(instance, frame, insn_idx, FM_MAY_WRITE, lo, hi);
}
static int mark_stack_read_all(struct bpf_verifier_env *env, struct func_instance *instance,
u32 frame, u32 insn_idx)
{
return mark_stack_read(instance, frame, insn_idx, 0,
env->stack_limit / BPF_HALF_REG_SIZE - 1);
}
static int mark_stack_may_write_all(struct bpf_verifier_env *env, struct func_instance *instance,
u32 frame, u32 insn_idx)
{
return mark_stack_may_write(instance, frame, insn_idx, 0,
env->stack_limit / BPF_HALF_REG_SIZE - 1);
}
static int mark_stack_mask(struct func_instance *instance, u32 frame, u32 insn_idx, u32 kind,
const unsigned long *src, u32 src_words)
{
u32 nbits = src_words * BITS_PER_LONG;
struct frame_masks *fm;
unsigned long *dst;
u32 last, w;
last = find_last_bit(src, nbits);
if (last == nbits)
return 0;
fm = widen_frame_masks(instance, frame, BITS_TO_LONGS(last + 1));
if (!fm)
return -ENOMEM;
dst = rel_mask(fm, relative_idx(instance, insn_idx), kind);
src_words = min(src_words, fm->words);
for (w = 0; w < src_words; w++)
dst[w] |= src[w];
return 0;
}
static int mark_stack_read_mask(struct func_instance *instance, u32 frame, u32 insn_idx,
const unsigned long *src, u32 src_words)
{
return mark_stack_mask(instance, frame, insn_idx, FM_MAY_READ, src, src_words);
}
int bpf_jmp_offset(struct bpf_insn *insn)
{
u8 code = insn->code;
if (code == (BPF_JMP32 | BPF_JA))
return insn->imm;
return insn->off;
}
__diag_push();
__diag_ignore_all("-Woverride-init", "Allow field initialization overrides for opcode_info_tbl");
inline struct bpf_iarray *
bpf_insn_successors(struct bpf_verifier_env *env, u32 idx)
{
static const struct opcode_info {
bool can_jump;
bool can_fallthrough;
} opcode_info_tbl[256] = {
[0 ... 255] = {.can_jump = false, .can_fallthrough = true},
#define _J(code, ...) \
[BPF_JMP | code] = __VA_ARGS__, \
[BPF_JMP32 | code] = __VA_ARGS__
_J(BPF_EXIT, {.can_jump = false, .can_fallthrough = false}),
_J(BPF_JA, {.can_jump = true, .can_fallthrough = false}),
_J(BPF_JEQ, {.can_jump = true, .can_fallthrough = true}),
_J(BPF_JNE, {.can_jump = true, .can_fallthrough = true}),
_J(BPF_JLT, {.can_jump = true, .can_fallthrough = true}),
_J(BPF_JLE, {.can_jump = true, .can_fallthrough = true}),
_J(BPF_JGT, {.can_jump = true, .can_fallthrough = true}),
_J(BPF_JGE, {.can_jump = true, .can_fallthrough = true}),
_J(BPF_JSGT, {.can_jump = true, .can_fallthrough = true}),
_J(BPF_JSGE, {.can_jump = true, .can_fallthrough = true}),
_J(BPF_JSLT, {.can_jump = true, .can_fallthrough = true}),
_J(BPF_JSLE, {.can_jump = true, .can_fallthrough = true}),
_J(BPF_JCOND, {.can_jump = true, .can_fallthrough = true}),
_J(BPF_JSET, {.can_jump = true, .can_fallthrough = true}),
#undef _J
};
struct bpf_prog *prog = env->prog;
struct bpf_insn *insn = &prog->insnsi[idx];
const struct opcode_info *opcode_info;
struct bpf_iarray *succ, *jt;
int insn_sz;
succ = env->succ;
succ->cnt = 0;
if (unlikely(insn_is_gotox(insn))) {
jt = bpf_find_containing_subprog(env, idx)->jt;
if (verifier_bug_if(!jt, env, "no jump table for gotox insn %u", idx))
return succ;
return jt;
}
opcode_info = &opcode_info_tbl[BPF_CLASS(insn->code) | BPF_OP(insn->code)];
insn_sz = bpf_is_ldimm64(insn) ? 2 : 1;
if (opcode_info->can_fallthrough)
succ->items[succ->cnt++] = idx + insn_sz;
if (opcode_info->can_jump)
succ->items[succ->cnt++] = idx + bpf_jmp_offset(insn) + 1;
if (unlikely((bpf_helper_call(insn) && insn->imm == BPF_FUNC_tail_call) ||
(BPF_CLASS(insn->code) == BPF_LD &&
(BPF_MODE(insn->code) == BPF_ABS || BPF_MODE(insn->code) == BPF_IND)))) {
u32 exit_idx = bpf_find_containing_subprog(env, idx)->exit_idx;
if (exit_idx != U32_MAX)
succ->items[succ->cnt++] = exit_idx;
}
return succ;
}
__diag_pop();
static inline bool update_insn(struct bpf_verifier_env *env,
struct func_instance *instance, u32 frame, u32 insn_idx)
{
unsigned long new_after[FRAME_MAX_WORDS] = {};
unsigned long *may_read, *must_write, *live_before;
struct frame_masks *fm = instance->frames[frame];
u32 rel = relative_idx(instance, insn_idx);
struct bpf_iarray *succ;
bool changed = false;
u32 s, w;
succ = bpf_insn_successors(env, insn_idx);
if (succ->cnt == 0)
return false;
for (s = 0; s < succ->cnt; ++s) {
unsigned long *succ_live;
succ_live = rel_mask(fm, relative_idx(instance, succ->items[s]), FM_LIVE_BEFORE);
for (w = 0; w < fm->words; w++)
new_after[w] |= succ_live[w];
}
may_read = rel_mask(fm, rel, FM_MAY_READ);
must_write = rel_mask(fm, rel, FM_MUST_WRITE);
live_before = rel_mask(fm, rel, FM_LIVE_BEFORE);
for (w = 0; w < fm->words; w++) {
unsigned long new_before = (new_after[w] & ~must_write[w]) | may_read[w];
if (new_before != live_before[w]) {
live_before[w] = new_before;
changed = true;
}
}
return changed;
}
static void update_instance(struct bpf_verifier_env *env, struct func_instance *instance)
{
u32 i, frame, po_start, po_end;
int *insn_postorder = env->cfg.insn_postorder;
struct bpf_subprog_info *subprog;
bool changed;
instance->must_write_initialized = true;
subprog = &env->subprog_info[instance->subprog];
po_start = subprog->postorder_start;
po_end = (subprog + 1)->postorder_start;
do {
changed = false;
for (frame = 0; frame <= instance->depth; frame++) {
if (!instance->frames[frame])
continue;
for (i = po_start; i < po_end; i++)
changed |= update_insn(env, instance, frame, insn_postorder[i]);
}
} while (changed);
}
static bool is_live_before(struct func_instance *instance, u32 insn_idx, u32 frameno, u32 half_spi)
{
struct frame_masks *fm = instance->frames[frameno];
if (!fm || half_spi >= frame_mask_bits(fm))
return false;
return test_bit(half_spi, rel_mask(fm, relative_idx(instance, insn_idx), FM_LIVE_BEFORE));
}
int bpf_live_stack_query_init(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
{
struct live_stack_query *q = &env->liveness->live_stack_query;
struct func_instance *instance;
u32 frame;
memset(q, 0, sizeof(*q));
for (frame = 0; frame <= st->curframe; frame++) {
instance = lookup_instance(env, st, frame);
if (IS_ERR_OR_NULL(instance))
q->instances[frame] = NULL;
else
q->instances[frame] = instance;
if (frame < st->curframe)
q->callsites[frame] = st->frame[frame + 1]->callsite;
}
q->curframe = st->curframe;
q->insn_idx = st->insn_idx;
return 0;
}
static bool callee_stack_access_at_callsite(struct bpf_verifier_env *env, u32 callsite)
{
return bpf_calls_callback(env, callsite) ||
bpf_is_callx(&env->prog->insnsi[callsite]);
}
bool bpf_stack_slot_alive(struct bpf_verifier_env *env, u32 frameno, u32 half_spi)
{
struct live_stack_query *q = &env->liveness->live_stack_query;
struct func_instance *instance, *curframe_instance;
u32 i, callsite, rel;
int cur_delta, delta;
bool alive = false;
curframe_instance = q->instances[q->curframe];
if (!curframe_instance)
return true;
cur_delta = (int)curframe_instance->depth - (int)q->curframe;
rel = frameno + cur_delta;
if (rel <= curframe_instance->depth)
alive = is_live_before(curframe_instance, q->insn_idx, rel, half_spi);
if (alive)
return true;
for (i = frameno; i < q->curframe; i++) {
instance = q->instances[i];
if (!instance)
return true;
delta = (int)instance->depth - (int)i;
rel = frameno + delta;
if (rel > instance->depth)
return true;
callsite = q->callsites[i];
alive = callee_stack_access_at_callsite(env, callsite)
? is_live_before(instance, callsite, rel, half_spi)
: is_live_before(instance, callsite + 1, rel, half_spi);
if (alive)
return true;
}
return false;
}
static char *fmt_subprog(struct bpf_verifier_env *env, int subprog)
{
const char *name = env->subprog_info[subprog].name;
snprintf(env->tmp_str_buf, sizeof(env->tmp_str_buf),
"subprog#%d%s%s", subprog, name ? " " : "", name ? name : "");
return env->tmp_str_buf;
}
static char *fmt_instance(struct bpf_verifier_env *env, struct func_instance *instance)
{
snprintf(env->tmp_str_buf, sizeof(env->tmp_str_buf),
"(d%d,cs%d)", instance->depth, instance->callsite);
return env->tmp_str_buf;
}
static int spi_off(int spi)
{
return -(spi + 1) * BPF_REG_SIZE;
}
static char *fmt_spis_mask(struct bpf_verifier_env *env, int frame, bool first,
const unsigned long *spis, u32 words)
{
int buf_sz = sizeof(env->tmp_str_buf);
int spi_cnt = words * BITS_PER_LONG / 2;
char *buf = env->tmp_str_buf;
int spi, n, run_start;
buf[0] = '\0';
for (spi = 0; spi < spi_cnt && buf_sz > 0; spi++) {
bool lo = test_bit(spi * 2, spis);
bool hi = test_bit(spi * 2 + 1, spis);
const char *space = first ? "" : " ";
if (!lo && !hi)
continue;
if (!lo || !hi) {
n = scnprintf(buf, buf_sz, "%sfp%d%d%s",
space, frame, spi_off(spi) + (lo ? STACK_SLOT_SZ : 0), "h");
} else if (spi + 2 < spi_cnt &&
test_bit(spi * 2 + 2, spis) &&
test_bit(spi * 2 + 3, spis) &&
test_bit(spi * 2 + 4, spis) &&
test_bit(spi * 2 + 5, spis)) {
run_start = spi;
while (spi + 1 < spi_cnt &&
test_bit((spi + 1) * 2, spis) &&
test_bit((spi + 1) * 2 + 1, spis))
spi++;
n = scnprintf(buf, buf_sz, "%sfp%d%d..%d",
space, frame, spi_off(run_start), spi_off(spi));
} else {
n = scnprintf(buf, buf_sz, "%sfp%d%d", space, frame, spi_off(spi));
}
first = false;
buf += n;
buf_sz -= n;
}
return env->tmp_str_buf;
}
static bool print_mask(struct bpf_verifier_env *env, struct func_instance *instance, int i,
const char *name, u32 kind)
{
struct frame_masks *fm;
bool printed = false;
unsigned long *mask;
int frame;
u64 pos;
pos = env->log.end_pos;
verbose(env, "%s", name);
for (frame = instance->depth; frame >= 0; --frame) {
fm = instance->frames[frame];
if (!fm)
continue;
mask = rel_mask(fm, i, kind);
if (bitmap_empty(mask, frame_mask_bits(fm)))
continue;
verbose(env, "%s", fmt_spis_mask(env, frame, !printed, mask, fm->words));
printed = true;
}
if (!printed)
bpf_vlog_reset(&env->log, pos);
return printed;
}
static void print_instance(struct bpf_verifier_env *env, struct func_instance *instance)
{
int start = env->subprog_info[instance->subprog].start;
struct bpf_insn *insns = env->prog->insnsi;
int len = instance->insn_cnt;
u64 pos, insn_pos;
int insn_idx, i;
bool printed;
if (!(env->log.level & BPF_LOG_LEVEL2))
return;
verbose(env, "stack use/def %s ", fmt_subprog(env, instance->subprog));
verbose(env, "%s:\n", fmt_instance(env, instance));
for (i = 0; i < len; i++) {
insn_idx = start + i;
pos = env->log.end_pos;
verbose(env, "%3d: ", insn_idx);
bpf_verbose_insn(env, &insns[insn_idx]);
insn_pos = env->log.end_pos;
verbose(env, "%*c;", bpf_vlog_alignment(insn_pos - pos), ' ');
printed = false;
printed |= print_mask(env, instance, i, " use: ", FM_MAY_READ);
printed |= print_mask(env, instance, i, " def: ", FM_MUST_WRITE);
printed |= print_mask(env, instance, i, " may_def: ", FM_MAY_WRITE);
if (!printed)
bpf_vlog_reset(&env->log, insn_pos);
verbose(env, "\n");
if (bpf_is_ldimm64(&insns[insn_idx]))
i++;
}
}
static int cmp_instances(const void *pa, const void *pb)
{
struct func_instance *a = *(struct func_instance **)pa;
struct func_instance *b = *(struct func_instance **)pb;
int dcallsite = (int)a->callsite - b->callsite;
int ddepth = (int)a->depth - b->depth;
if (dcallsite)
return dcallsite;
if (ddepth)
return ddepth;
return 0;
}
static void half_spis_to_slots(unsigned long *slots, const unsigned long *mask, u32 nbits)
{
u32 slot;
for (slot = 0; slot < MAX_BPF_STACK_SLOTS && slot * 2 + 1 < nbits; slot++)
if (test_bit(slot * 2, mask) || test_bit(slot * 2 + 1, mask))
__set_bit(slot, slots);
}
static void compute_may_write_masks(struct bpf_verifier_env *env)
{
struct bpf_insn_aux_data *aux = env->insn_aux_data;
struct bpf_liveness *liveness = env->liveness;
struct func_instance *instance;
struct frame_masks *fm;
u32 nbits;
int bkt, i;
hash_for_each(liveness->func_instances, bkt, instance, hl_node) {
fm = instance->frames[instance->depth];
if (!fm)
continue;
nbits = frame_mask_bits(fm);
for (i = 0; i < instance->insn_cnt; i++) {
half_spis_to_slots(aux[instance->subprog_start + i].may_write_mask,
rel_mask(fm, i, FM_MAY_WRITE), nbits);
half_spis_to_slots(aux[instance->subprog_start + i].live_stack_before,
rel_mask(fm, i, FM_LIVE_BEFORE), nbits);
}
}
}
const unsigned long *bpf_may_write_mask(struct bpf_verifier_env *env, u32 insn_idx)
{
return env->insn_aux_data[insn_idx].may_write_mask;
}
static int print_instances(struct bpf_verifier_env *env)
{
struct func_instance *instance, **sorted_instances;
struct bpf_liveness *liveness = env->liveness;
int i, bkt, cnt;
cnt = 0;
hash_for_each(liveness->func_instances, bkt, instance, hl_node)
cnt++;
sorted_instances = kvmalloc_objs(*sorted_instances, cnt, GFP_KERNEL_ACCOUNT);
if (!sorted_instances)
return -ENOMEM;
cnt = 0;
hash_for_each(liveness->func_instances, bkt, instance, hl_node)
sorted_instances[cnt++] = instance;
sort(sorted_instances, cnt, sizeof(*sorted_instances), cmp_instances, NULL);
for (i = 0; i < cnt; i++)
print_instance(env, sorted_instances[i]);
kvfree(sorted_instances);
return 0;
}
#define MAX_ARG_OFFSETS 4
struct arg_track {
union {
s16 off[MAX_ARG_OFFSETS];
u16 mask;
};
s8 frame;
s8 off_cnt;
};
enum arg_track_state {
ARG_NONE = -1,
ARG_UNVISITED = -2,
ARG_IMPRECISE = -3,
};
struct spill_snapshot {
u32 slots;
struct arg_track at[];
};
#define MAX_AT_TRACK_REGS (MAX_BPF_REG + MAX_STACK_ARG_SLOTS)
static int stack_arg_off_to_slot(s16 off)
{
int aoff = off < 0 ? -off : off;
if (aoff / 8 > MAX_STACK_ARG_SLOTS)
return -1;
return aoff / 8 - 1;
}
static bool arg_is_visited(const struct arg_track *at)
{
return at->frame != ARG_UNVISITED;
}
static bool arg_is_fp(const struct arg_track *at)
{
return at->frame >= 0 || at->frame == ARG_IMPRECISE;
}
static void verbose_arg_track(struct bpf_verifier_env *env, struct arg_track *at)
{
int i;
switch (at->frame) {
case ARG_NONE: verbose(env, "_"); break;
case ARG_UNVISITED: verbose(env, "?"); break;
case ARG_IMPRECISE: verbose(env, "IMP%x", at->mask); break;
default:
if (at->off_cnt == 0) {
verbose(env, "fp%d ?", at->frame);
} else {
for (i = 0; i < at->off_cnt; i++) {
if (i)
verbose(env, "|");
verbose(env, "fp%d%+d", at->frame, at->off[i]);
}
}
break;
}
}
static bool arg_track_eq(const struct arg_track *a, const struct arg_track *b)
{
int i;
if (a->frame != b->frame)
return false;
if (a->frame == ARG_IMPRECISE)
return a->mask == b->mask;
if (a->frame < 0)
return true;
if (a->off_cnt != b->off_cnt)
return false;
for (i = 0; i < a->off_cnt; i++)
if (a->off[i] != b->off[i])
return false;
return true;
}
static struct arg_track arg_single(s8 arg, s16 off)
{
struct arg_track at = {};
at.frame = arg;
at.off[0] = off;
at.off_cnt = 1;
return at;
}
static struct arg_track arg_merge_offsets(struct arg_track a, struct arg_track b)
{
struct arg_track result = { .frame = a.frame };
struct arg_track imp = { .frame = a.frame };
int i = 0, j = 0, k = 0;
while (i < a.off_cnt && j < b.off_cnt) {
s16 v;
if (a.off[i] <= b.off[j]) {
v = a.off[i++];
if (v == b.off[j])
j++;
} else {
v = b.off[j++];
}
if (k > 0 && result.off[k - 1] == v)
continue;
if (k >= MAX_ARG_OFFSETS)
return imp;
result.off[k++] = v;
}
while (i < a.off_cnt) {
if (k >= MAX_ARG_OFFSETS)
return imp;
result.off[k++] = a.off[i++];
}
while (j < b.off_cnt) {
if (k >= MAX_ARG_OFFSETS)
return imp;
result.off[k++] = b.off[j++];
}
result.off_cnt = k;
return result;
}
static struct arg_track arg_join_imprecise(struct arg_track a, struct arg_track b)
{
u32 m = 0;
if (a.frame >= 0)
m |= BIT(a.frame);
else if (a.frame == ARG_IMPRECISE)
m |= a.mask;
if (b.frame >= 0)
m |= BIT(b.frame);
else if (b.frame == ARG_IMPRECISE)
m |= b.mask;
return (struct arg_track){ .mask = m, .frame = ARG_IMPRECISE };
}
static struct arg_track arg_or_none(struct arg_track a)
{
if (a.off_cnt != 1)
return a;
if (!a.off[0])
return (struct arg_track){ .frame = a.frame };
return arg_merge_offsets(a, arg_single(a.frame, 0));
}
static struct arg_track __arg_track_join(struct arg_track a, struct arg_track b)
{
if (!arg_is_visited(&b))
return a;
if (!arg_is_visited(&a))
return b;
if (a.frame == b.frame && a.frame >= 0) {
if (a.off_cnt == 0 || b.off_cnt == 0)
return (struct arg_track){ .frame = a.frame };
return arg_merge_offsets(a, b);
}
if (a.frame == ARG_NONE && b.frame == ARG_NONE)
return a;
if (a.frame >= 0 && b.frame == ARG_NONE)
return arg_or_none(a);
if (b.frame >= 0 && a.frame == ARG_NONE)
return arg_or_none(b);
return arg_join_imprecise(a, b);
}
static bool arg_track_join(struct bpf_verifier_env *env, int idx, int target, int r,
struct arg_track *in, struct arg_track out)
{
struct arg_track old = *in;
struct arg_track new_val = __arg_track_join(old, out);
if (arg_track_eq(&new_val, &old))
return false;
*in = new_val;
if (!(env->log.level & BPF_LOG_LEVEL2) || !arg_is_visited(&old))
return true;
verbose(env, "arg JOIN insn %d -> %d ", idx, target);
if (r >= MAX_BPF_REG)
verbose(env, "sa%d: ", r - MAX_BPF_REG);
else if (r >= 0)
verbose(env, "r%d: ", r);
else
verbose(env, "fp%+d: ", r * 8);
verbose_arg_track(env, &old);
verbose(env, " + ");
verbose_arg_track(env, &out);
verbose(env, " => ");
verbose_arg_track(env, &new_val);
verbose(env, "\n");
return true;
}
static void arg_track_alu64(struct arg_track *dst, const struct arg_track *src)
{
WARN_ON_ONCE(!arg_is_visited(dst));
WARN_ON_ONCE(!arg_is_visited(src));
if (dst->frame >= 0 && (src->frame == ARG_NONE || src->frame == dst->frame)) {
dst->off_cnt = 0;
return;
}
if (src->frame >= 0 && dst->frame == ARG_NONE) {
dst->off_cnt = 0;
dst->frame = src->frame;
return;
}
if (dst->frame == ARG_NONE && src->frame == ARG_NONE)
return;
*dst = arg_join_imprecise(*dst, *src);
}
static bool arg_add(s16 off, s64 delta, s16 *out)
{
s16 d = delta;
if (d != delta)
return true;
return check_add_overflow(off, d, out);
}
static void arg_padd(struct arg_track *at, s64 delta)
{
int i;
if (at->off_cnt == 0)
return;
for (i = 0; i < at->off_cnt; i++) {
s16 new_off;
if (arg_add(at->off[i], delta, &new_off)) {
at->off_cnt = 0;
return;
}
at->off[i] = new_off;
}
}
static u32 spill_slots_affordable(int len)
{
u32 base = MAX_BPF_STACK / BPF_REG_SIZE;
return max_t(u32, base, base * BPF_COMPLEXITY_LIMIT_INSNS / len);
}
static u32 subprog_spill_slots(struct bpf_verifier_env *env, int start, int end)
{
struct bpf_insn *insns = env->prog->insnsi;
int deepest = 0;
for (int i = start; i < end; i++) {
struct bpf_insn *insn = &insns[i];
u8 class = BPF_CLASS(insn->code);
u8 base;
if (BPF_SIZE(insn->code) != BPF_DW)
continue;
if (class == BPF_LDX)
base = insn->src_reg;
else if (class == BPF_STX || class == BPF_ST)
base = insn->dst_reg;
else
continue;
if (base == BPF_REG_FP && insn->off < 0)
deepest = max(deepest, -insn->off);
}
return clamp_t(u32, DIV_ROUND_UP(deepest, 8), MAX_BPF_STACK / BPF_REG_SIZE,
env->stack_limit / BPF_REG_SIZE);
}
static int fp_off_to_slot(s16 off, u32 nslots)
{
if (off >= 0 || off < -(int)(nslots * 8))
return -1;
if (off % 8)
return -1;
return (-off) / 8 - 1;
}
static struct arg_track fill_from_stack(struct bpf_insn *insn,
struct arg_track *at_out, int reg,
struct arg_track *at_stack_out, u32 nslots,
int depth)
{
struct arg_track imp = {
.mask = (1u << (depth + 1)) - 1,
.frame = ARG_IMPRECISE
};
struct arg_track result = { .frame = ARG_NONE };
int cnt, i;
if (reg == BPF_REG_FP) {
int slot = fp_off_to_slot(insn->off, nslots);
return slot >= 0 ? at_stack_out[slot] : imp;
}
cnt = at_out[reg].off_cnt;
if (cnt == 0)
return imp;
for (i = 0; i < cnt; i++) {
s16 fp_off, slot;
if (arg_add(at_out[reg].off[i], insn->off, &fp_off))
return imp;
slot = fp_off_to_slot(fp_off, nslots);
if (slot < 0)
return imp;
result = __arg_track_join(result, at_stack_out[slot]);
}
return result;
}
static void spill_to_stack(struct bpf_insn *insn, struct arg_track *at_out,
int reg, struct arg_track *at_stack_out, u32 nslots,
struct arg_track *val, u32 sz)
{
struct arg_track none = { .frame = ARG_NONE };
struct arg_track new_val = sz == 8 ? *val : none;
int cnt, i;
if (reg == BPF_REG_FP) {
int slot = fp_off_to_slot(insn->off, nslots);
if (slot >= 0)
at_stack_out[slot] = new_val;
return;
}
cnt = at_out[reg].off_cnt;
if (cnt == 0) {
for (int slot = 0; slot < nslots; slot++)
at_stack_out[slot] = __arg_track_join(at_stack_out[slot], new_val);
return;
}
for (i = 0; i < cnt; i++) {
s16 fp_off;
int slot;
if (arg_add(at_out[reg].off[i], insn->off, &fp_off))
continue;
slot = fp_off_to_slot(fp_off, nslots);
if (slot < 0)
continue;
if (cnt == 1)
at_stack_out[slot] = new_val;
else
at_stack_out[slot] = __arg_track_join(at_stack_out[slot], new_val);
}
}
static void clear_overlapping_stack_slots(struct arg_track *at_stack, u32 nslots, s16 off,
u32 sz, int cnt)
{
struct arg_track none = { .frame = ARG_NONE };
if (cnt == 0) {
for (int i = 0; i < nslots; i++)
at_stack[i] = __arg_track_join(at_stack[i], none);
return;
}
for (int i = 0; i < nslots; i++) {
int slot_start = -((i + 1) * 8);
int slot_end = slot_start + 8;
if (slot_start < off + (int)sz && slot_end > off) {
if (cnt == 1)
at_stack[i] = none;
else
at_stack[i] = __arg_track_join(at_stack[i], none);
}
}
}
static void clear_stack_for_all_offs(struct bpf_insn *insn,
struct arg_track *at_out, int reg,
struct arg_track *at_stack_out, u32 nslots, u32 sz)
{
int cnt, i;
if (reg == BPF_REG_FP) {
clear_overlapping_stack_slots(at_stack_out, nslots, insn->off, sz, 1);
return;
}
cnt = at_out[reg].off_cnt;
if (cnt == 0) {
clear_overlapping_stack_slots(at_stack_out, nslots, 0, sz, cnt);
return;
}
for (i = 0; i < cnt; i++) {
s16 fp_off;
if (arg_add(at_out[reg].off[i], insn->off, &fp_off)) {
clear_overlapping_stack_slots(at_stack_out, nslots, 0, sz, 0);
break;
}
clear_overlapping_stack_slots(at_stack_out, nslots, fp_off, sz, cnt);
}
}
static void arg_track_log(struct bpf_verifier_env *env, struct bpf_insn *insn, int idx,
struct arg_track *at_in, struct arg_track *at_stack_in,
struct arg_track *at_out, struct arg_track *at_stack_out, u32 nslots)
{
bool printed = false;
int i;
if (!(env->log.level & BPF_LOG_LEVEL2))
return;
for (i = 0; i < MAX_BPF_REG; i++) {
if (arg_track_eq(&at_out[i], &at_in[i]))
continue;
if (!printed) {
verbose(env, "%3d: ", idx);
bpf_verbose_insn(env, insn);
printed = true;
}
verbose(env, "\tr%d: ", i); verbose_arg_track(env, &at_in[i]);
verbose(env, " -> "); verbose_arg_track(env, &at_out[i]);
}
for (i = 0; i < MAX_STACK_ARG_SLOTS; i++) {
int ai = MAX_BPF_REG + i;
if (arg_track_eq(&at_out[ai], &at_in[ai]))
continue;
if (!printed) {
verbose(env, "%3d: ", idx);
bpf_verbose_insn(env, insn);
printed = true;
}
verbose(env, "\tsa%d: ", i); verbose_arg_track(env, &at_in[ai]);
verbose(env, " -> "); verbose_arg_track(env, &at_out[ai]);
}
for (i = 0; i < nslots; i++) {
if (arg_track_eq(&at_stack_out[i], &at_stack_in[i]))
continue;
if (!printed) {
verbose(env, "%3d: ", idx);
bpf_verbose_insn(env, insn);
printed = true;
}
verbose(env, "\tfp%+d: ", -(i + 1) * 8); verbose_arg_track(env, &at_stack_in[i]);
verbose(env, " -> "); verbose_arg_track(env, &at_stack_out[i]);
}
if (printed)
verbose(env, "\n");
}
static bool can_be_local_fp(int depth, int regno, struct arg_track *at)
{
return regno == BPF_REG_FP || at->frame == depth ||
(at->frame == ARG_IMPRECISE && (at->mask & BIT(depth)));
}
static struct arg_track arg_track_deref(struct bpf_verifier_env *env, struct bpf_insn *insn,
struct arg_track *at_out, int reg,
struct arg_track *at_stack_out, u32 nslots,
int depth, u32 *callsites)
{
struct arg_track *ptr = &at_out[reg];
if (can_be_local_fp(depth, reg, ptr))
return fill_from_stack(insn, at_out, reg, at_stack_out, nslots, depth);
if (ptr->frame >= 0 && ptr->frame < depth) {
struct spill_snapshot *parent = env->callsite_at_stack[callsites[ptr->frame]];
return fill_from_stack(insn, at_out, reg, parent->at, parent->slots, ptr->frame);
}
if (ptr->frame == ARG_IMPRECISE && !(ptr->mask & BIT(depth)) && ptr->mask)
return *ptr;
return (struct arg_track){ .frame = ARG_NONE };
}
static bool subprog_gets_local_fp(struct bpf_verifier_env *env, struct bpf_insn *insn, int insn_idx,
struct arg_track *at, int depth)
{
int r;
if (bpf_pseudo_call(insn)) {
r = bpf_find_subprog(env, insn_idx + insn->imm + 1);
if (r >= 0 && bpf_subprog_is_global(env, r))
return false;
} else if (!bpf_is_callx(insn) && !bpf_calls_callback(env, insn_idx)) {
return false;
}
for (r = BPF_REG_1; r < MAX_AT_TRACK_REGS; r++)
if ((r <= BPF_REG_5 || r >= MAX_BPF_REG) && can_be_local_fp(depth, r, &at[r]))
return true;
return false;
}
static void arg_track_xfer(struct bpf_verifier_env *env, struct bpf_insn *insn,
int insn_idx,
struct arg_track *at_out, struct arg_track *at_stack_out, u32 nslots,
const struct arg_track *at_stack_arg_entry,
struct func_instance *instance,
u32 *callsites)
{
int depth = instance->depth;
u8 class = BPF_CLASS(insn->code);
u8 code = BPF_OP(insn->code);
struct arg_track *dst = &at_out[insn->dst_reg];
struct arg_track *src = &at_out[insn->src_reg];
struct arg_track none = { .frame = ARG_NONE };
int r, slot;
if (is_stack_arg_st(insn) || is_stack_arg_stx(insn)) {
slot = stack_arg_off_to_slot(insn->off);
if (slot >= 0) {
if (is_stack_arg_stx(insn))
at_out[MAX_BPF_REG + slot] = at_out[insn->src_reg];
else
at_out[MAX_BPF_REG + slot] = none;
}
} else if (is_stack_arg_ldx(insn)) {
slot = stack_arg_off_to_slot(insn->off);
at_out[insn->dst_reg] = (slot >= 0) ? at_stack_arg_entry[slot] : none;
} else if (class == BPF_ALU64 && BPF_SRC(insn->code) == BPF_K) {
if (code == BPF_MOV) {
*dst = none;
} else if (dst->frame >= 0) {
if (code == BPF_ADD)
arg_padd(dst, insn->imm);
else if (code == BPF_SUB)
arg_padd(dst, -(s64)insn->imm);
else
dst->off_cnt = 0;
}
} else if (class == BPF_ALU64 && BPF_SRC(insn->code) == BPF_X) {
if (code == BPF_MOV) {
if (insn->off == 0) {
*dst = *src;
} else {
*dst = none;
}
} else {
arg_track_alu64(dst, src);
}
} else if (class == BPF_ALU) {
*dst = none;
} else if (class == BPF_JMP && code == BPF_CALL) {
if (subprog_gets_local_fp(env, insn, insn_idx, at_out, depth))
for (slot = 0; slot < nslots; slot++)
at_stack_out[slot] = __arg_track_join(at_stack_out[slot], none);
for (r = BPF_REG_0; r <= BPF_REG_5; r++)
at_out[r] = none;
} else if (class == BPF_LDX) {
if (BPF_MODE(insn->code) == BPF_MEM && BPF_SIZE(insn->code) == BPF_DW)
*dst = arg_track_deref(env, insn, at_out, insn->src_reg,
at_stack_out, nslots, depth, callsites);
else
*dst = none;
} else if (class == BPF_LD && BPF_MODE(insn->code) == BPF_IMM) {
*dst = none;
} else if (class == BPF_STX) {
u32 sz = bpf_size_to_bytes(BPF_SIZE(insn->code));
bool dst_is_local_fp = can_be_local_fp(depth, insn->dst_reg, dst);
u8 mode = BPF_MODE(insn->code);
if (mode == BPF_MEM || (mode == BPF_ATOMIC && insn->imm == BPF_STORE_REL)) {
if (dst_is_local_fp)
spill_to_stack(insn, at_out, insn->dst_reg,
at_stack_out, nslots, src, sz);
} else if (mode == BPF_ATOMIC && insn->imm == BPF_LOAD_ACQ) {
if (sz == 8)
*dst = arg_track_deref(env, insn, at_out, insn->src_reg,
at_stack_out, nslots, depth, callsites);
else
*dst = none;
} else if (mode == BPF_ATOMIC) {
struct arg_track old = none;
r = bpf_atomic_load_reg(insn);
if (r >= 0 && sz == 8)
old = arg_track_deref(env, insn, at_out, insn->dst_reg,
at_stack_out, nslots, depth, callsites);
if (dst_is_local_fp)
clear_stack_for_all_offs(insn, at_out, insn->dst_reg,
at_stack_out, nslots, sz);
if (r >= 0)
at_out[r] = old;
}
} else if (class == BPF_ST && BPF_MODE(insn->code) == BPF_MEM) {
u32 sz = bpf_size_to_bytes(BPF_SIZE(insn->code));
bool dst_is_local_fp = can_be_local_fp(depth, insn->dst_reg, dst);
if (dst_is_local_fp)
clear_stack_for_all_offs(insn, at_out, insn->dst_reg,
at_stack_out, nslots, sz);
}
}
static int record_stack_access_off(struct func_instance *instance, const struct arg_track *arg,
s64 off_idx, struct arg_access_info info,
u32 frame, u32 insn_idx)
{
s64 fp_off = arg->off[off_idx];
s32 slot_hi, slot_lo;
int err;
if (fp_off >= 0)
return 0;
slot_hi = (-fp_off - 1) / STACK_SLOT_SZ;
slot_lo = info.size == U32_MAX
? 0
: max_t(s32, (-fp_off - info.size) / STACK_SLOT_SZ, 0);
if (info.may_read) {
err = mark_stack_read(instance, frame, insn_idx, slot_lo, slot_hi);
if (err)
return err;
}
if (info.may_write) {
err = mark_stack_may_write(instance, frame, insn_idx, slot_lo, slot_hi);
if (err)
return err;
}
if (info.must_write && info.size != U32_MAX && arg->off_cnt == 1) {
slot_hi = (-fp_off) / STACK_SLOT_SZ - 1;
slot_lo = max_t(s32, (-fp_off - info.size + STACK_SLOT_SZ - 1) / STACK_SLOT_SZ, 0);
return mark_stack_write(instance, frame, insn_idx, slot_lo, slot_hi);
}
return 0;
}
static int record_stack_access(struct bpf_verifier_env *env,
struct func_instance *instance,
const struct arg_track *arg,
struct arg_access_info info, u32 frame, u32 insn_idx)
{
int i, err;
if (!info.size)
return 0;
if (arg->off_cnt == 0) {
if (info.may_read) {
err = mark_stack_read_all(env, instance, frame, insn_idx);
if (err)
return err;
}
if (info.may_write) {
err = mark_stack_may_write_all(env, instance, frame, insn_idx);
if (err)
return err;
}
return 0;
}
for (i = 0; i < arg->off_cnt; i++) {
err = record_stack_access_off(instance, arg, i, info, frame, insn_idx);
if (err)
return err;
}
return 0;
}
static int record_imprecise(struct bpf_verifier_env *env, struct func_instance *instance,
struct arg_access_info info, u32 mask, u32 insn_idx)
{
int depth = instance->depth;
int f, err;
for (f = 0; mask; f++, mask >>= 1) {
if (!(mask & 1))
continue;
if (f <= depth) {
if (info.may_read) {
err = mark_stack_read_all(env, instance, f, insn_idx);
if (err)
return err;
}
if (info.may_write) {
err = mark_stack_may_write_all(env, instance, f, insn_idx);
if (err)
return err;
}
}
}
return 0;
}
static int record_load_store_access(struct bpf_verifier_env *env,
struct func_instance *instance,
struct arg_track *at, int insn_idx)
{
struct bpf_insn *insn = &env->prog->insnsi[insn_idx];
struct arg_access_info info = {};
int depth = instance->depth;
u8 class = BPF_CLASS(insn->code);
bool read = false, write = false;
struct arg_track resolved, *ptr;
int oi;
if (is_stack_arg_stx(insn) || is_stack_arg_st(insn) || is_stack_arg_ldx(insn))
return 0;
switch (class) {
case BPF_LDX:
ptr = &at[insn->src_reg];
read = true;
break;
case BPF_STX:
if (BPF_MODE(insn->code) == BPF_ATOMIC) {
switch (insn->imm) {
case BPF_LOAD_ACQ:
ptr = &at[insn->src_reg];
read = true;
break;
case BPF_STORE_REL:
ptr = &at[insn->dst_reg];
write = true;
break;
default:
ptr = &at[insn->dst_reg];
read = true;
write = true;
break;
}
} else {
ptr = &at[insn->dst_reg];
write = true;
}
break;
case BPF_ST:
ptr = &at[insn->dst_reg];
write = true;
break;
default:
return 0;
}
if (ptr->off_cnt > 0) {
resolved.off_cnt = ptr->off_cnt;
resolved.frame = ptr->frame;
for (oi = 0; oi < ptr->off_cnt; oi++) {
if (arg_add(ptr->off[oi], insn->off, &resolved.off[oi])) {
resolved.off_cnt = 0;
break;
}
}
ptr = &resolved;
}
info.may_read = read;
info.may_write = write;
info.must_write = write;
info.size = bpf_size_to_bytes(BPF_SIZE(insn->code));
if (ptr->frame >= 0 && ptr->frame <= depth)
return record_stack_access(env, instance, ptr, info, ptr->frame, insn_idx);
if (ptr->frame == ARG_IMPRECISE)
return record_imprecise(env, instance, info, ptr->mask, insn_idx);
return 0;
}
static int record_arg_access(struct bpf_verifier_env *env,
struct func_instance *instance,
struct bpf_insn *insn,
struct arg_track *at, int arg_idx,
int insn_idx)
{
struct arg_access_info info;
int depth = instance->depth;
int frame = at->frame;
int err = 0;
if (!arg_is_fp(at))
return 0;
if (bpf_helper_call(insn)) {
info = bpf_helper_stack_access_bytes(env, insn, arg_idx, insn_idx);
} else if (bpf_pseudo_kfunc_call(insn)) {
info = bpf_kfunc_stack_access_bytes(env, insn, arg_idx, insn_idx);
} else if (bpf_pseudo_call(insn)) {
info = bpf_global_subprog_stack_access_bytes(env, insn, arg_idx, insn_idx);
} else {
for (int f = 0; f <= depth; f++) {
err = mark_stack_read_all(env, instance, f, insn_idx);
if (err)
return err;
err = mark_stack_may_write_all(env, instance, f, insn_idx);
if (err)
return err;
}
return 0;
}
if (!info.size)
return 0;
if (frame >= 0 && frame <= depth)
err = record_stack_access(env, instance, at, info, frame, insn_idx);
else if (frame == ARG_IMPRECISE)
err = record_imprecise(env, instance, info, at->mask, insn_idx);
return err;
}
static int record_call_access(struct bpf_verifier_env *env,
struct func_instance *instance,
struct arg_track *at,
int insn_idx)
{
struct bpf_insn *insn = &env->prog->insnsi[insn_idx];
struct bpf_call_summary cs;
int r, err, callee, arg_slot_cnt = 5;
if (bpf_pseudo_call(insn)) {
callee = bpf_find_subprog(env, insn_idx + insn->imm + 1);
if (callee < 0 || !bpf_subprog_is_global(env, callee))
return 0;
arg_slot_cnt = MAX_BPF_FUNC_ARGS;
} else if (bpf_is_callx(insn))
arg_slot_cnt = MAX_BPF_FUNC_REG_ARGS + MAX_STACK_ARG_SLOTS;
else if (bpf_get_call_summary(env, insn, &cs))
arg_slot_cnt = cs.arg_slot_cnt;
for (r = BPF_REG_1; r < BPF_REG_1 + min(arg_slot_cnt, MAX_BPF_FUNC_REG_ARGS); r++) {
err = record_arg_access(env, instance, insn, &at[r], r - 1, insn_idx);
if (err)
return err;
}
for (r = 0; r < MAX_STACK_ARG_SLOTS && r < arg_slot_cnt - MAX_BPF_FUNC_REG_ARGS; r++) {
err = record_arg_access(env, instance, insn, &at[MAX_BPF_REG + r],
r + MAX_BPF_FUNC_REG_ARGS, insn_idx);
if (err)
return err;
}
return 0;
}
static int find_callback_subprog(struct bpf_verifier_env *env,
struct bpf_insn *insn, int insn_idx,
int *caller_reg, int *callee_reg)
{
struct bpf_insn_aux_data *aux = &env->insn_aux_data[insn_idx];
int cb_reg = -1;
*caller_reg = -1;
*callee_reg = -1;
if (!bpf_helper_call(insn))
return -1;
switch (insn->imm) {
case BPF_FUNC_loop:
cb_reg = BPF_REG_2;
*caller_reg = BPF_REG_3;
*callee_reg = BPF_REG_2;
break;
case BPF_FUNC_for_each_map_elem:
cb_reg = BPF_REG_2;
*caller_reg = BPF_REG_3;
*callee_reg = BPF_REG_4;
break;
case BPF_FUNC_find_vma:
cb_reg = BPF_REG_3;
*caller_reg = BPF_REG_4;
*callee_reg = BPF_REG_3;
break;
case BPF_FUNC_user_ringbuf_drain:
cb_reg = BPF_REG_2;
*caller_reg = BPF_REG_3;
*callee_reg = BPF_REG_2;
break;
default:
return -1;
}
if (!(aux->const_reg_subprog_mask & BIT(cb_reg)))
return -2;
return aux->const_reg_vals[cb_reg];
}
struct subprog_at_info {
struct arg_track (*at_in)[MAX_AT_TRACK_REGS];
int len;
};
static void print_subprog_arg_access(struct bpf_verifier_env *env,
int subprog,
struct subprog_at_info *info,
struct arg_track *at_stack_in, u32 nslots)
{
struct bpf_insn *insns = env->prog->insnsi;
int start = env->subprog_info[subprog].start;
int len = info->len;
int i, r;
if (!(env->log.level & BPF_LOG_LEVEL2))
return;
verbose(env, "%s:\n", fmt_subprog(env, subprog));
for (i = 0; i < len; i++) {
int idx = start + i;
bool has_extra = false;
u8 cls = BPF_CLASS(insns[idx].code);
bool is_ldx_stx_call = cls == BPF_LDX || cls == BPF_STX ||
(cls == BPF_JMP && BPF_OP(insns[idx].code) == BPF_CALL);
verbose(env, "%3d: ", idx);
bpf_verbose_insn(env, &insns[idx]);
verbose(env, "\n");
if (is_ldx_stx_call &&
arg_is_visited(&info->at_in[i][0])) {
for (r = 0; r < MAX_BPF_REG - 1; r++)
if (arg_is_fp(&info->at_in[i][r]))
has_extra = true;
for (r = 0; r < MAX_STACK_ARG_SLOTS; r++)
if (arg_is_fp(&info->at_in[i][MAX_BPF_REG + r]))
has_extra = true;
}
if (is_ldx_stx_call) {
for (r = 0; r < nslots; r++)
if (arg_is_fp(&at_stack_in[(size_t)i * nslots + r]))
has_extra = true;
}
if (!has_extra) {
if (bpf_is_ldimm64(&insns[idx]))
i++;
continue;
}
bpf_vlog_reset(&env->log, env->log.end_pos - 1);
verbose(env, " //");
if (is_ldx_stx_call && info->at_in &&
arg_is_visited(&info->at_in[i][0])) {
for (r = 0; r < MAX_BPF_REG - 1; r++) {
if (!arg_is_fp(&info->at_in[i][r]))
continue;
verbose(env, " r%d=", r);
verbose_arg_track(env, &info->at_in[i][r]);
}
for (r = 0; r < MAX_STACK_ARG_SLOTS; r++) {
if (!arg_is_fp(&info->at_in[i][MAX_BPF_REG + r]))
continue;
verbose(env, " sa%d=", r);
verbose_arg_track(env, &info->at_in[i][MAX_BPF_REG + r]);
}
}
if (is_ldx_stx_call) {
for (r = 0; r < nslots; r++) {
if (!arg_is_fp(&at_stack_in[(size_t)i * nslots + r]))
continue;
verbose(env, " fp%+d=", -(r + 1) * 8);
verbose_arg_track(env, &at_stack_in[(size_t)i * nslots + r]);
}
}
verbose(env, "\n");
if (bpf_is_ldimm64(&insns[idx]))
i++;
}
}
static void record_stack_ptrs(struct bpf_verifier_env *env, int idx, struct arg_track *at_in)
{
u16 r, mask = 0;
for (r = 0; r < MAX_BPF_REG; r++)
if (arg_is_fp(&at_in[r]))
mask |= BIT(r);
env->insn_aux_data[idx].stack_ptrs |= mask;
}
static int compute_subprog_args(struct bpf_verifier_env *env,
struct subprog_at_info *info,
struct arg_track *callee_entry,
struct func_instance *instance,
u32 *callsites)
{
int subprog = instance->subprog;
struct bpf_insn *insns = env->prog->insnsi;
int depth = instance->depth;
int start = env->subprog_info[subprog].start;
int po_start = env->subprog_info[subprog].postorder_start;
int end = env->subprog_info[subprog + 1].start;
int po_end = env->subprog_info[subprog + 1].postorder_start;
int len = end - start;
u32 nslots = min(subprog_spill_slots(env, start, end), spill_slots_affordable(len));
struct arg_track (*at_in)[MAX_AT_TRACK_REGS] = NULL;
struct arg_track at_out[MAX_AT_TRACK_REGS];
struct arg_track *at_stack_in = NULL;
struct arg_track *at_stack_out = NULL;
struct arg_track at_stack_arg_entry[MAX_STACK_ARG_SLOTS];
struct arg_track unvisited = { .frame = ARG_UNVISITED };
struct arg_track none = { .frame = ARG_NONE };
bool changed;
int i, p, r, err = -ENOMEM;
at_in = kvmalloc_objs(*at_in, len, GFP_KERNEL_ACCOUNT);
if (!at_in)
goto err_free;
at_stack_in = kvmalloc_objs(*at_stack_in, (size_t)len * nslots, GFP_KERNEL_ACCOUNT);
if (!at_stack_in)
goto err_free;
at_stack_out = kvmalloc_objs(*at_stack_out, nslots, GFP_KERNEL_ACCOUNT);
if (!at_stack_out)
goto err_free;
for (i = 0; i < len; i++) {
for (r = 0; r < MAX_AT_TRACK_REGS; r++)
at_in[i][r] = unvisited;
for (r = 0; r < nslots; r++)
at_stack_in[(size_t)i * nslots + r] = unvisited;
}
for (r = 0; r < MAX_AT_TRACK_REGS; r++)
at_in[0][r] = none;
at_in[0][BPF_REG_FP] = arg_single(depth, 0);
if (callee_entry) {
for (r = BPF_REG_1; r <= BPF_REG_5; r++)
at_in[0][r] = callee_entry[r];
}
for (r = 0; r < nslots; r++)
at_stack_in[r] = none;
for (r = 0; r < MAX_STACK_ARG_SLOTS; r++)
at_stack_arg_entry[r] = callee_entry ? callee_entry[MAX_BPF_REG + r] : none;
if (env->log.level & BPF_LOG_LEVEL2)
verbose(env, "subprog#%d: analyzing (depth %d)...\n", subprog, depth);
redo:
changed = false;
for (p = po_end - 1; p >= po_start; p--) {
int idx = env->cfg.insn_postorder[p];
int i = idx - start;
struct bpf_insn *insn = &insns[idx];
struct bpf_iarray *succ;
if (!arg_is_visited(&at_in[i][0]) && !arg_is_visited(&at_in[i][1]))
continue;
memcpy(at_out, at_in[i], sizeof(at_out));
memcpy(at_stack_out, &at_stack_in[(size_t)i * nslots], nslots * sizeof(*at_stack_out));
arg_track_xfer(env, insn, idx, at_out, at_stack_out, nslots,
at_stack_arg_entry, instance, callsites);
arg_track_log(env, insn, idx, at_in[i], &at_stack_in[(size_t)i * nslots], at_out,
at_stack_out, nslots);
succ = bpf_insn_successors(env, idx);
for (int s = 0; s < succ->cnt; s++) {
int target = succ->items[s];
int ti;
if (target < start || target >= end)
continue;
ti = target - start;
for (r = 0; r < MAX_AT_TRACK_REGS; r++)
changed |= arg_track_join(env, idx, target, r,
&at_in[ti][r], at_out[r]);
for (r = 0; r < nslots; r++)
changed |= arg_track_join(env, idx, target, -r - 1,
&at_stack_in[(size_t)ti * nslots + r],
at_stack_out[r]);
}
}
if (changed)
goto redo;
for (p = po_end - 1; p >= po_start; p--) {
int idx = env->cfg.insn_postorder[p];
int i = idx - start;
struct bpf_insn *insn = &insns[idx];
err = record_load_store_access(env, instance, at_in[i], idx);
if (err)
goto err_free;
if (BPF_CLASS(insn->code) == BPF_JMP && BPF_OP(insn->code) == BPF_CALL) {
err = record_call_access(env, instance, at_in[i], idx);
if (err)
goto err_free;
}
if (bpf_pseudo_call(insn) || bpf_calls_callback(env, idx)) {
struct spill_snapshot *snap;
kvfree(env->callsite_at_stack[idx]);
env->callsite_at_stack[idx] = kvmalloc_flex(*snap, at, nslots, GFP_KERNEL_ACCOUNT);
snap = env->callsite_at_stack[idx];
if (!snap) {
err = -ENOMEM;
goto err_free;
}
snap->slots = nslots;
memcpy(snap->at, &at_stack_in[(size_t)i * nslots], nslots * sizeof(*snap->at));
}
record_stack_ptrs(env, idx, at_in[i]);
}
info->at_in = at_in;
at_in = NULL;
info->len = len;
print_subprog_arg_access(env, subprog, info, at_stack_in, nslots);
err = 0;
err_free:
kvfree(at_stack_out);
kvfree(at_stack_in);
kvfree(at_in);
return err;
}
static bool has_fp_args(struct arg_track *args)
{
for (int r = BPF_REG_1; r <= BPF_REG_5; r++)
if (arg_is_fp(&args[r]))
return true;
for (int r = 0; r < MAX_STACK_ARG_SLOTS; r++)
if (arg_is_fp(&args[MAX_BPF_REG + r]))
return true;
return false;
}
static int merge_instances(struct func_instance *dst, struct func_instance *src)
{
struct frame_masks *d, *s;
u32 f, i, w;
for (f = 0; f <= dst->depth; f++) {
s = src->frames[f];
d = dst->frames[f];
if (!s) {
if (d)
for (i = 0; i < dst->insn_cnt; i++)
bitmap_zero(rel_mask(d, i, FM_MUST_WRITE),
frame_mask_bits(d));
continue;
}
if (!d) {
dst->frames[f] = s;
src->frames[f] = NULL;
for (i = 0; i < dst->insn_cnt; i++)
bitmap_zero(rel_mask(s, i, FM_MUST_WRITE), frame_mask_bits(s));
continue;
}
d = widen_frame_masks(dst, f, s->words);
if (!d)
return -ENOMEM;
for (i = 0; i < dst->insn_cnt; i++) {
unsigned long *dst_read = rel_mask(d, i, FM_MAY_READ);
unsigned long *dst_write = rel_mask(d, i, FM_MUST_WRITE);
unsigned long *dst_may_write = rel_mask(d, i, FM_MAY_WRITE);
unsigned long *src_read = rel_mask(s, i, FM_MAY_READ);
unsigned long *src_write = rel_mask(s, i, FM_MUST_WRITE);
unsigned long *src_may_write = rel_mask(s, i, FM_MAY_WRITE);
for (w = 0; w < d->words; w++) {
dst_read[w] |= w < s->words ? src_read[w] : 0;
dst_write[w] &= w < s->words ? src_write[w] : 0;
dst_may_write[w] |= w < s->words ? src_may_write[w] : 0;
}
}
}
return 0;
}
static int merge_may_write(struct func_instance *caller, struct func_instance *callee)
{
DECLARE_BITMAP(acc, FRAME_HALF_SPIS);
u32 call_idx = callee->callsite;
struct frame_masks *fm;
u32 f, i, nbits;
int err;
for (f = 0; f < callee->depth; f++) {
fm = callee->frames[f];
if (!fm)
continue;
nbits = frame_mask_bits(fm);
bitmap_zero(acc, nbits);
for (i = 0; i < callee->insn_cnt; i++)
bitmap_or(acc, acc, rel_mask(fm, i, FM_MAY_WRITE), nbits);
if (bitmap_empty(acc, nbits))
continue;
err = mark_stack_mask(caller, f, call_idx, FM_MAY_WRITE, acc, fm->words);
if (err)
return err;
}
return 0;
}
static struct func_instance *fresh_instance(struct func_instance *src)
{
struct func_instance *f;
f = kvzalloc_obj(*f, GFP_KERNEL_ACCOUNT);
if (!f)
return ERR_PTR(-ENOMEM);
f->callsite = src->callsite;
f->depth = src->depth;
f->subprog = src->subprog;
f->subprog_start = src->subprog_start;
f->insn_cnt = src->insn_cnt;
return f;
}
static void free_instance(struct func_instance *instance)
{
int i;
for (i = 0; i <= instance->depth; i++)
kvfree(instance->frames[i]);
kvfree(instance);
}
static int analyze_subprog(struct bpf_verifier_env *env,
struct arg_track *entry_args,
struct subprog_at_info *info,
struct func_instance *instance,
u32 *callsites)
{
int subprog = instance->subprog;
int depth = instance->depth;
struct bpf_insn *insns = env->prog->insnsi;
int start = env->subprog_info[subprog].start;
int po_start = env->subprog_info[subprog].postorder_start;
int po_end = env->subprog_info[subprog + 1].postorder_start;
struct func_instance *prev_instance = NULL;
int j, err;
if (++env->liveness->subprog_calls > 10000) {
verbose(env, "liveness analysis exceeded complexity limit (%d calls)\n",
env->liveness->subprog_calls);
return -E2BIG;
}
if (need_resched())
cond_resched();
if (instance->must_write_initialized) {
struct func_instance *fresh = fresh_instance(instance);
if (IS_ERR(fresh))
return PTR_ERR(fresh);
prev_instance = instance;
instance = fresh;
}
kvfree(info[subprog].at_in);
info[subprog].at_in = NULL;
err = compute_subprog_args(env, &info[subprog], entry_args, instance, callsites);
if (err)
goto out_free;
for (int p = po_start; p < po_end; p++) {
int idx = env->cfg.insn_postorder[p];
struct arg_track callee_args[MAX_AT_TRACK_REGS] = {};
struct arg_track none = { .frame = ARG_NONE };
struct bpf_insn *insn = &insns[idx];
struct func_instance *callee_instance;
int callee, target;
int caller_reg, cb_callee_reg;
j = idx - start;
if (bpf_pseudo_call(insn)) {
target = idx + insn->imm + 1;
callee = bpf_find_subprog(env, target);
if (callee < 0 || bpf_subprog_is_global(env, callee))
continue;
for (int r = BPF_REG_1; r <= BPF_REG_5; r++)
callee_args[r] = info[subprog].at_in[j][r];
for (int r = 0; r < MAX_STACK_ARG_SLOTS; r++)
callee_args[MAX_BPF_REG + r] = info[subprog].at_in[j][MAX_BPF_REG + r];
} else if (bpf_calls_callback(env, idx)) {
callee = find_callback_subprog(env, insn, idx, &caller_reg, &cb_callee_reg);
if (callee == -2) {
if (info[subprog].at_in[j][caller_reg].frame == ARG_NONE)
continue;
for (int f = 0; f <= depth; f++) {
err = mark_stack_read_all(env, instance, f, idx);
if (err)
goto out_free;
err = mark_stack_may_write_all(env, instance, f, idx);
if (err)
goto out_free;
}
continue;
}
if (callee < 0)
continue;
for (int r = BPF_REG_1; r <= BPF_REG_5; r++)
callee_args[r] = none;
for (int r = 0; r < MAX_STACK_ARG_SLOTS; r++)
callee_args[MAX_BPF_REG + r] = none;
callee_args[cb_callee_reg] = info[subprog].at_in[j][caller_reg];
} else {
continue;
}
if (!has_fp_args(callee_args))
continue;
if (depth == MAX_CALL_FRAMES - 1) {
err = -EINVAL;
goto out_free;
}
callee_instance = call_instance(env, instance, idx, callee);
if (IS_ERR(callee_instance)) {
err = PTR_ERR(callee_instance);
goto out_free;
}
callsites[depth] = idx;
err = analyze_subprog(env, callee_args, info, callee_instance, callsites);
if (err)
goto out_free;
{
u32 callee_start = callee_instance->subprog_start;
struct frame_masks *callee_fm;
for (int f = 0; f < callee_instance->depth; f++) {
callee_fm = callee_instance->frames[f];
if (!callee_fm)
continue;
err = mark_stack_read_mask(instance, f, idx,
rel_mask(callee_fm,
relative_idx(callee_instance,
callee_start),
FM_LIVE_BEFORE),
callee_fm->words);
if (err)
goto out_free;
}
}
err = merge_may_write(instance, callee_instance);
if (err)
goto out_free;
}
if (prev_instance) {
err = merge_instances(prev_instance, instance);
free_instance(instance);
instance = prev_instance;
if (err)
return err;
}
update_instance(env, instance);
return 0;
out_free:
if (prev_instance)
free_instance(instance);
return err;
}
int bpf_compute_subprog_arg_access(struct bpf_verifier_env *env)
{
u32 callsites[MAX_CALL_FRAMES] = {};
int insn_cnt = env->prog->len;
struct func_instance *instance;
struct subprog_at_info *info;
int k, err = 0;
info = kvzalloc_objs(*info, env->subprog_cnt, GFP_KERNEL_ACCOUNT);
if (!info)
return -ENOMEM;
env->callsite_at_stack = kvzalloc_objs(*env->callsite_at_stack, insn_cnt,
GFP_KERNEL_ACCOUNT);
if (!env->callsite_at_stack) {
kvfree(info);
return -ENOMEM;
}
for (k = env->subprog_cnt - 1; k >= 0; k--) {
int sub = env->subprog_topo_order[k];
if (info[sub].at_in && !bpf_subprog_is_global(env, sub))
continue;
instance = call_instance(env, NULL, 0, sub);
if (IS_ERR(instance)) {
err = PTR_ERR(instance);
goto out;
}
err = analyze_subprog(env, NULL, info, instance, callsites);
if (err)
goto out;
}
compute_may_write_masks(env);
if (env->log.level & BPF_LOG_LEVEL2)
err = print_instances(env);
out:
for (k = 0; k < insn_cnt; k++)
kvfree(env->callsite_at_stack[k]);
kvfree(env->callsite_at_stack);
env->callsite_at_stack = NULL;
for (k = 0; k < env->subprog_cnt; k++)
kvfree(info[k].at_in);
kvfree(info);
return err;
}
struct insn_live_regs {
u32 use;
u32 def;
u32 in;
u32 out;
};
#define ALL_CALLER_SAVED_REGS ((1u << CALLER_SAVED_REGS) - 1)
static inline u32 reg32_mask(u32 n) { return BIT(n); }
static inline u32 reg64_mask(u32 n) { return BIT(n) | BIT(n + 16); }
static inline u32 mask_widen(u32 m) { return m | (m << 16); }
static inline u16 mask_lo(u32 m) { return (u16)m; }
static inline u16 mask_hi(u32 m) { return (u16)(m >> 16); }
static int callee_subprog(struct bpf_verifier_env *env, const struct bpf_insn *insn)
{
return bpf_find_subprog(env, insn - env->prog->insnsi + insn->imm + 1);
}
static void compute_insn_live_regs(struct bpf_verifier_env *env,
struct bpf_insn *insn,
struct insn_live_regs *info,
bool ret_reg_pair)
{
struct bpf_call_summary cs;
const u8 class = BPF_CLASS(insn->code);
const u8 code = BPF_OP(insn->code);
const u8 mode = BPF_MODE(insn->code);
const u8 size = BPF_SIZE(insn->code);
const u32 src = reg64_mask(insn->src_reg);
const u32 dst = reg64_mask(insn->dst_reg);
const u32 src32 = mask_lo(src);
const u32 dst32 = mask_lo(dst);
const u32 r0 = reg64_mask(0);
const u32 r2 = reg64_mask(BPF_REG_2);
int subprog, reg_args;
u32 def = 0;
u32 use = U32_MAX;
switch (class) {
case BPF_LD:
switch (mode) {
case BPF_IMM:
if (BPF_SIZE(insn->code) == BPF_DW) {
def = dst;
use = 0;
}
break;
case BPF_ABS:
case BPF_IND:
break;
}
break;
case BPF_LDX:
switch (mode) {
case BPF_MEM:
def = dst;
use = src;
break;
case BPF_MEMSX:
def = dst;
use = src;
break;
}
break;
case BPF_ST:
switch (mode) {
case BPF_MEM:
def = 0;
use = dst;
break;
}
break;
case BPF_STX:
switch (mode) {
case BPF_MEM:
def = 0;
use = dst | (size == BPF_DW ? src : src32);
break;
case BPF_ATOMIC: {
u32 srcv = size == BPF_DW ? src : src32;
u32 r0v = size == BPF_DW ? r0 : mask_lo(r0);
switch (insn->imm) {
case BPF_CMPXCHG:
use = r0v | dst | srcv;
def = r0;
break;
case BPF_LOAD_ACQ:
def = dst;
use = src;
break;
case BPF_STORE_REL:
def = 0;
use = dst | srcv;
break;
default:
use = dst | srcv;
if (insn->imm & BPF_FETCH)
def = src;
else
def = 0;
}
break;
}
}
break;
case BPF_ALU:
case BPF_ALU64:
switch (code) {
case BPF_END:
use = dst;
def = dst;
break;
case BPF_MOV:
def = dst;
if (BPF_SRC(insn->code) == BPF_K)
use = 0;
else
use = class == BPF_ALU64 ? src : src32;
break;
default:
def = dst;
if (BPF_SRC(insn->code) == BPF_K)
use = class == BPF_ALU64 ? dst : dst32;
else
use = class == BPF_ALU64 ? (dst | src) : (dst32 | src32);
}
break;
case BPF_JMP:
case BPF_JMP32:
switch (code) {
case BPF_JA:
def = 0;
if (BPF_SRC(insn->code) == BPF_X)
use = dst;
else
use = 0;
break;
case BPF_JCOND:
def = 0;
use = 0;
break;
case BPF_EXIT:
def = 0;
use = ret_reg_pair ? (r0 | r2) : r0;
break;
case BPF_CALL:
def = ALL_CALLER_SAVED_REGS;
use = def & ~BIT(BPF_REG_0);
if (bpf_get_call_summary(env, insn, &cs)) {
use = GENMASK(min_t(u8, cs.arg_slot_cnt, MAX_BPF_FUNC_REG_ARGS), 1);
} else if (bpf_pseudo_call(insn)) {
subprog = callee_subprog(env, insn);
if (bpf_subprog_is_global(env, subprog)) {
reg_args = min_t(u8, env->subprog_info[subprog].arg_slot_cnt, MAX_BPF_FUNC_REG_ARGS);
use = GENMASK(reg_args, 1);
} else {
use = 0;
}
}
def = mask_widen(def);
use = mask_widen(use);
if (bpf_is_callx(insn))
use |= dst;
break;
default:
def = 0;
use = class == BPF_JMP ? dst : dst32;
if (BPF_SRC(insn->code) == BPF_X)
use |= class == BPF_JMP ? src : src32;
}
break;
}
info->def = def;
info->use = use;
}
int bpf_compute_live_registers(struct bpf_verifier_env *env)
{
struct bpf_insn_aux_data *insn_aux = env->insn_aux_data;
struct bpf_insn *insns = env->prog->insnsi;
struct insn_live_regs *state;
int insn_cnt = env->prog->len;
int err = 0, i, subprog, start, end;
bool changed, ret_reg_pair;
state = kvzalloc_objs(*state, insn_cnt, GFP_KERNEL_ACCOUNT);
if (!state) {
err = -ENOMEM;
goto out;
}
for (subprog = 0; subprog < env->subprog_cnt; subprog++) {
start = env->subprog_info[subprog].start;
end = env->subprog_info[subprog + 1].start;
ret_reg_pair = bpf_ret_reg_pair(env, subprog);
for (i = start; i < end; ++i)
compute_insn_live_regs(env, &insns[i], &state[i], ret_reg_pair);
}
err = bpf_compute_subprog_arg_access(env);
if (err)
goto out;
changed = true;
while (changed) {
changed = false;
for (i = 0; i < env->cfg.cur_postorder; ++i) {
int insn_idx = env->cfg.insn_postorder[i];
struct insn_live_regs *live = &state[insn_idx];
struct bpf_iarray *succ;
u32 new_out = 0;
u32 new_in = 0;
u32 use;
succ = bpf_insn_successors(env, insn_idx);
for (int s = 0; s < succ->cnt; ++s)
new_out |= state[succ->items[s]].in;
use = live->use;
if (bpf_pseudo_call(&insns[insn_idx]) &&
!bpf_subprog_is_global(env, callee_subprog(env, &insns[insn_idx])))
use |= state[insn_idx + insns[insn_idx].imm + 1].in &
mask_widen(GENMASK(BPF_REG_5, BPF_REG_1));
new_in = (new_out & ~live->def) | use;
if (new_out != live->out || new_in != live->in) {
live->in = new_in;
live->out = new_out;
changed = true;
}
}
}
for (i = 0; i < insn_cnt; ++i) {
int def32 = bpf_insn_def32(env->prog, &insns[i]);
u32 out = state[i].out;
u32 in = state[i].in;
insn_aux[i].live_regs_before = mask_lo(in) | mask_hi(in);
insn_aux[i].zext_dst = def32 >= 0 && (mask_hi(out) & BIT(def32));
}
out:
kvfree(state);
return err;
}