"Program too large" threshold greater than actual instruction count

Question

I've written a couple production BPF agents, but my approach is very iterative until I please the verifier and can move on. I've reached my limit again.

Here's a program that works if I have one fewer && condition -- and breaks otherwise. The confusing part is that the warning implies that 103 insns is greater-than at most 4096 insns. There's obviously something I'm misunderstanding about how this is all strung together.

My ultimate goal is to do logging based on a process' environment -- so alternative approaches are welcome. :)

Error:

$ sudo python foo.py
bpf: Argument list too long. Program  too large (103 insns), at most 4096 insns

Failed to load BPF program b'tracepoint__sched__sched_process_exec': Argument list too long

BPF Source:

#include <linux/mm_types.h>
#include <linux/sched.h>
#include <linux/version.h>

int tracepoint__sched__sched_process_exec(
  struct tracepoint__sched__sched_process_exec* args
) {
  struct task_struct* task = (typeof(task))bpf_get_current_task();

  const struct mm_struct* mm = task->mm;

  unsigned long env_start = mm->env_start;
  unsigned long env_end = mm->env_end;

  // Read up to 512 environment variables -- only way I could find to "limit"
  // the loop to satisfy the verifier.
  char var[12];
  for (int n = 0; n < 512; n++) {
    int result = bpf_probe_read_str(&var, sizeof var, (void*)env_start);
    if (result <= 0) {
      break;
    }
    env_start += result;
    if (
      var[0] == 'H' &&
      var[1] == 'I' &&
      var[2] == 'S' &&
      var[3] == 'T' &&
      var[4] == 'S' &&
      var[5] == 'I' &&
      var[6] == 'Z' &&
      var[7] == 'E'
    ) {
      bpf_trace_printk("Got it: %s\n", var);
      break;
    }
  }

  return 0;
}

Basic loader program for reproducing:

#!/usr/bin/env python3

import sys

from bcc import BPF


if __name__ == '__main__':
    source = open("./foo.c").read()
    try:
        BPF(text=source.encode("utf-8")).trace_print()
    except Exception as e:
        error = str(e)
        sys.exit(error)

isatty() would be preferred, but I'm not sure how to use those functions inside a BPF program. `#include unistd.h` doesn't seem possible. — coxley, Nov 28 '21 at 21:37
That error message looks a bit weird. This is likely a matter of complexity vs. program size, but the error message is very misleading. What kernel are you running on? — pchaigno, Nov 28 '21 at 22:03
@pchaigno Whoops -- 5.15 on Fedora 34 right now: 5.15.4-101.fc34.x86_64 — coxley, Nov 29 '21 at 03:11
Looks like `#pragma unroll` helps by showing an "accurate" portrayal of instructions? It works with that pragma + changing `n < 128`. — coxley, Nov 29 '21 at 03:12
I've answered below, with an explanation for the weird error message. Reducing the number of loop iterations is probably the easiest way to work around this. Reducing the number of conditions inside the loop would also help. In particular, you should be able to compare the four first characters of `var` in one instruction. Alternatively, you could use Cilium's optimized `memcmp` function for BPF: https://github.com/cilium/cilium/blob/v1.10.4/bpf/include/bpf/builtins.h#L267. — pchaigno, Nov 29 '21 at 09:52

pchaigno · Accepted Answer · 2021-11-29T09:48:20.533

bpf: Argument list too long. Program too large (103 insns), at most 4096 insns

Looking at the error message, my guess would be that your program has 103 instructions and it's rejected because it's too complex. That is, the verifier gave up before analyzing all instructions on all paths.

On Linux 5.15 with a privileged user, the verifier gives up after reading 1 million instructions (the complexity limit). Since it has to analyze all paths through the program, a program with a small number of instructions can have a very high complexity. That's particularly the case when you have loops and many conditions, as is your case.

Why is the error message confusing? This error message is coming from libbpf.c:

if (ret < 0 && errno == E2BIG) {
  fprintf(stderr,
          "bpf: %s. Program %s too large (%u insns), at most %d insns\n\n",
          strerror(errno), attr->name, insns_cnt, BPF_MAXINSNS);
  return -1;
}

Since the bpf(2) syscall returns E2BIG both when the program is too large and when its complexity is too high, libbpf prints the same error message for both cases, always with at most 4096 instructions. I'm confident upstream would accept a patch to improve that error message.

"Program too large" threshold greater than actual instruction count

1 Answers1

Linked