BPF verifier fails when using a map with an array of struct as a field of the value

[mlavacca]

In the context of writing a PR for blixt, I encountered the following eBPF verifier error:

    Finished dev [optimized] target(s) in 0.21s
    Finished dev [unoptimized + debuginfo] target(s) in 0.18s
[2023-01-27T12:38:51Z INFO  loader] loading ebpf programs
[2023-01-27T12:38:51Z INFO  loader] attaching tc_ingress program to lo
Error: the BPF_PROG_LOAD syscall failed. Verifier output: func#0 @0
func#1 @3948
0: R1=ctx(off=0,imm=0) R10=fp0
...
...
3952: (73) *(u8 *)(r5 +0) = r2
invalid size of register spill
verification time 3475 usec
stack depth 232+0
processed 2208 insns (limit 1000000) max_states_per_insn 1 total_states 20 peak_states 20 mark_read 7


Caused by:
    Permission denied (os error 13)

Here is the full eBPF verifier error: eBPF_verifier_error.log

After a few trials, I figured out that the root cause of the error is the update of a hashmap shared between the user and kernel space:

// update the entry in BACKENDS
match unsafe { BACKENDS.insert(&key, &new_backends, 0) } {
    Ok(_) => {
        info!(&ctx, "index updated for vip/port {}/{}", key.ip, key.port);
    }
    Err(err) => {
        error!(&ctx, "error {} inserting index update for vip/port {}/{}", err, key.ip, key.port);
    }
}

Such a map is allocated with:

#[map(name = "BACKENDS")]
static mut BACKENDS: HashMap<BackendKey, BackendsList> =
    HashMap::<BackendKey, BackendsList>::with_max_entries(128, 0);

and the map value is structured as follows:

pub const BACKENDS_ARRAY_LENGTH: usize = 16;

#[derive(Copy, Clone, Debug)]
#[repr(C)]
pub struct Backend {
    pub daddr: u32,
    pub dport: u32,
    pub ifindex: u16,
}

#[derive(Copy, Clone, Debug)]
#[repr(C)]
pub struct BackendsList {
    pub backends: [Backend; BACKENDS_ARRAY_LENGTH],
    pub index: usize,
    pub n_elements: usize,
}

#[cfg(feature = "user")]
unsafe impl aya::Pod for BackendsList {}

The following are my attempts to figure out the root cause of the problem, along with the discoveries:

• simplifying the insert statement to unsafe { BACKENDS.insert(&key, &new_backends, 0) }; does not solve the issue.
• changing the backends array length to 1,2,4, whatever, does not solve the issue.
• removing all the Backend fields but one (so that the struct only contains a u16 field) does not solve the issue.
• changing the backends field of the BackendList to an array of u16 solves the issue.

After my attempts, I wondered: is it possible to have an array of structs as a field of hashmap value? If yes, most likely, I'm missing something.

[alessandrod]

After my attempts, I wondered: is it possible to have an array of structs as a field of hashmap value? If yes, most likely, I'm missing something.

As I mentioned on discord, this is not the root cause. I know it can seem like it's the root cause, because if you remove the array then things work, but the actual problem is something else.

The error you get is about a register spill, which means that because your code is complex, LLVM runs out of available registers, tries to spill some on the stack, and in particular it tries to do a 1-byte spill which is not allowed by the verifier (only 8-bytes spills are allowed).

[alessandrod]

pub const BACKENDS_ARRAY_LENGTH: usize = 16;

#[derive(Copy, Clone, Debug)]
#[repr(C)]
pub struct Backend {
    pub daddr: u32,
    pub dport: u32,
    pub ifindex: u16,
}

This structure will have 2 bytes of padding at the end, which is a problem. Try making ifindex u32.

#[derive(Copy, Clone, Debug)]
#[repr(C)]
pub struct BackendsList {
pub backends: [Backend; BACKENDS_ARRAY_LENGTH],
pub index: usize,
pub n_elements: usize,
}

#[cfg(feature = "user")]
unsafe impl aya::Pod for BackendsList {}

The following are my attempts to figure out the root cause of the problem, along with the discoveries:

    * simplifying the insert statement to `unsafe { BACKENDS.insert(&key, &new_backends, 0) };` does not solve the issue.

How are you creating new_backends before inserting?

[mlavacca]

Hi @alessandrod, thanks for your reply!

This structure will have 2 bytes of padding at the end, which is a problem. Try making ifindex u32.

I tried making ifindex a u32, but the error is still here.

How are you creating new_backends before inserting?

// get the backends available for the combination vip/port
let backends_list = unsafe { BACKENDS.get(&key) }.ok_or(TC_ACT_OK)?;

let mut new_backends: BackendsList = BackendsList {
    backends: backends_list.backends,
    index: backends_list.index + 1,
    n_elements: backends_list.n_elements
};

if new_backends.index > new_backends.backends.len() - 1 {
        new_backends.index = 0;
}

[alessandrod]

How are you creating new_backends before inserting?

// get the backends available for the combination vip/port
let backends_list = unsafe { BACKENDS.get(&key) }.ok_or(TC_ACT_OK)?;

let mut new_backends: BackendsList = BackendsList {
    backends: backends_list.backends,
    index: backends_list.index + 1,
    n_elements: backends_list.n_elements
};

if new_backends.index > new_backends.backends.len() - 1 {
        new_backends.index = 0;
}

From what I understand the backends are configured from userspace, and you're doing this from ebpf to advance index right? But that code does a lot of stuff, including a mem::size_of::<Backend>() * BACKENDS_ARRAY_LENGTH memcpy. Why not have a separate map just for the index, indexed by the key, and you just bump the index?

[shaneutt]

From what I understand the backends are configured from userspace, and you're doing this from ebpf to advance index right?

Correct. (I also work on Blixt)

Why not have a separate map just for the index, indexed by the key, and you just bump the index?

If I'm not mistaken this approach is kinda what Cilium does, it sounds reasonable to me .

I am also left wondering if there's ways we can help users avoid or at least understand these issues better. Based on the suggestions here so far, it would seem there's a fair amount of conceptual work needed to avoid or resolve these: there needs to be a certain amount of intuition about how things will actually compile to bytecode and foresight into how they will be executed.

Perhaps @alessandrod we could add some documentation to the book talking about how code complexity can lead to these kinds of issues, perhaps with some concrete examples of programs that will trigger similar problems and a guided dive into exactly what goes wrong, and then examples of how to fix it? Or maybe there's ways to improve the tooling around this? I suppose the tooling notion almost suggests we're talking about improving the verifier itself which I know is no small task for any goal. Just curious to hear your thoughts on how we could help preempt these kinds of things for Aya developers 🤔

[mlavacca]

Why not have a separate map just for the index, indexed by the key, and you just bump the index?

yeah, it makes sense. I'll try this way 👍

[alessandrod]

Just curious to hear your thoughts on how we could help preempt these kinds of things for Aya developers 🤔

My thoughts are: yes!

Perhaps @alessandrod we could add some documentation to the book talking about how code complexity can lead to these kinds of issues, perhaps with some concrete examples of programs that will trigger similar problems and a guided dive into exactly what goes wrong, and then examples of how to fix it?

So many things we should add to the book, this is one of them. In general I think it'd be good to document idiomatic ways to do things, and things to avoid.

Or maybe there's ways to improve the tooling around this? I suppose the tooling notion almost suggests we're talking about improving the verifier itself which I know is no small task for any goal

Only regarding this specific issue, there are so many things that can be improved:

• aya-log currently generates too much code, which contributes to running out of registers, someone needs to look into optimizing it
• The memory intrinsics (memset/memcpy/memmove etc) can likely be optimized too to generate more efficient and smaller code
• Some rustc/LLVM optimizations are not required for eBPF, and actually end up generating code that is too complex for the verifier. Those optimizations should be disabled.
• The verifier output has been improved recently but it's still very much a thing by hackers, for hackers. The error messages can definitely be improved.

[shaneutt]

Sounds great. I've created some relevant issues (I searched for existing issues first and didn't see relevant ones, let me know if I missed something):

• Guide on code complexity and register spill book#97
• General improvements to aya-log efficiency #509
• Optimize memory instrinsics #510
• Disable some rustc/LLVM optimizations for build efficiency #511

Please feel free to update those issues with any changes in language you deem necessary.