eBPF Validation error when trying to hash a string (process name)

Question

Hi I am trying to generate a 32bit hash for the full process name in ebpf. These process names can be long and will not fit on the stack hence the "heap" per cpu array. I am currently using libbpf bootstrap as a prototype from here: https://github.com/libbpf/libbpf-bootstrap.git I am having an issue with the verifier not validating the hash function. What is the problem here? I am stumped.

The meat of the code is:

  uint32_t map_id = 0;
  char *map_val = bpf_map_lookup_elem(&heap, &map_id);
  if (!map_val)
    return 0;

  int bytes_read = bpf_probe_read_str(map_val, sizeof(e->filename), (void *)ctx + fname_off);
  if (bytes_read > 0) {
      map_val[ (bytes_read - 1) & (4096 -1) ] = 0;

      uint32_t key = hash( (unsigned char*)map_val);
      bpf_printk("process_exec count: %u, hash: %lu, full path: %s\n", bytes_read -1, key, map_val); 
  }

The hash function is:

uint32_t hash(unsigned char *str)
{
    int c;
    uint32_t hash = 5381;
    while ( c = *str++ )
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

I get a validator error:

; hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
91: (27) r4 *= 33
; hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
92: (0f) r4 += r1
; while ( c = *str++ )
93: (71) r1 = *(u8 *)(r2 +0)
 R0=inv(id=6,smin_value=-4096,smax_value=4095) R1_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R2_w=map_value(id=0,off=4096,ks=4,vs=4096,imm=0) R4_w=inv(id=0) R6=ctx(id=0,off=0,umax_value=65535,var_off=(0x0; 0xffff)) R7=map_value(id=0,off=0,ks=4,vs=4096,imm=0) R8=invP0 R10=fp0 fp-8=mmmm???? fp-16=mmmmmmmm fp-24=mmmm???? fp-32=mmmmmmmm
invalid access to map value, value_size=4096 off=4096 size=1
R2 min value is outside of the allowed memory range
processed 32861 insns (limit 1000000) max_states_per_insn 4 total_states 337 peak_states 337 mark_read 4
-- END PROG LOAD LOG --
libbpf: prog 'handle_exec': failed to load: -13
libbpf: failed to load object 'bootstrap_bpf'
libbpf: failed to load BPF skeleton 'bootstrap_bpf': -13
Failed to load and verify BPF skeleton

Here is the complete diff for my use case:

diff --git a/examples/c/bootstrap.bpf.c b/examples/c/bootstrap.bpf.c
index d0860c0..c93ed58 100644
--- a/examples/c/bootstrap.bpf.c
+++ b/examples/c/bootstrap.bpf.c
@@ -20,6 +20,13 @@ struct {
        __uint(max_entries, 256 * 1024);
 } rb SEC(".maps");

+struct {
+       __uint(type, BPF_MAP_TYPE_PERCPU_ARRAY);
+       __uint(key_size, sizeof(u32));
+       __uint(max_entries, 1);
+       __uint(value_size, 4096);
+} heap SEC(".maps");
+
 const volatile unsigned long long min_duration_ns = 0;

 SEC("tp/sched/sched_process_exec")
@@ -58,6 +65,22 @@ int handle_exec(struct trace_event_raw_sched_process_exec *ctx)

        /* successfully submit it to user-space for post-processing */
        bpf_ringbuf_submit(e, 0);
+
+
+  uint32_t map_id = 0;
+  char *map_val = bpf_map_lookup_elem(&heap, &map_id);
+  if (!map_val)
+    return 0;
+
+  int bytes_read = bpf_probe_read_str(map_val, sizeof(e->filename), (void *)ctx + fname_off);
+  if (bytes_read > 0) {
+      // tell the validator bytes ready is between 0 and 4095
+      map_val[ (bytes_read - 1) & (4096 -1) ] = 0;
+
+      uint32_t key = hash( (unsigned char*)map_val);
+      bpf_printk("process_exec count: %u, hash: %u, full path: %s\n", bytes_read -1, key, map_val);
+  }
+
        return 0;
 }

@@ -109,4 +132,3 @@ int handle_exit(struct trace_event_raw_sched_process_template* ctx)
        bpf_ringbuf_submit(e, 0);
        return 0;
 }
-
diff --git a/examples/c/bootstrap.h b/examples/c/bootstrap.h
index b49e022..d268e56 100644
--- a/examples/c/bootstrap.h
+++ b/examples/c/bootstrap.h
@@ -4,7 +4,7 @@
 #define __BOOTSTRAP_H

 #define TASK_COMM_LEN 16
-#define MAX_FILENAME_LEN 127
+#define MAX_FILENAME_LEN 4096

 struct event {
        int pid;
@@ -16,4 +16,15 @@ struct event {
        bool exit_event;
 };

+static inline
+uint32_t hash(unsigned char *str)
+{
+    int c;
+    uint32_t hash = 5381;
+    while ( c = *str++ )
+        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
+
+    return hash;
+}
+
 #endif /* __BOOTSTRAP_H */

Answer 1

TL;DR. You need to ensure that you are not reading past the end of the map value. So you need to check str never goes past the initial str value + 4095.

---

Verifier error explanation.

; while ( c = *str++ )
93: (71) r1 = *(u8 *)(r2 +0)
 R0=inv(id=6,smin_value=-4096,smax_value=4095) R1_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R2_w=map_value(id=0,off=4096,ks=4,vs=4096,imm=0) R4_w=inv(id=0) R6=ctx(id=0,off=0,umax_value=65535,var_off=(0x0; 0xffff)) R7=map_value(id=0,off=0,ks=4,vs=4096,imm=0) R8=invP0 R10=fp0 fp-8=mmmm???? fp-16=mmmmmmmm fp-24=mmmm???? fp-32=mmmmmmmm
invalid access to map value, value_size=4096 off=4096 size=1
R2 min value is outside of the allowed memory range

The verifier here is telling you that your code may attempt to read one byte (size=1) from the map value, at offset 4096 (off=4096). Since the map value has a size of 4096 (value_size=4096), that would end up reading after the end of the map value, leading to an unbounded memory access. Hence, the verifier rejects it.