How to design eBPF map for large data structures without exceeding jump complexity?

Question

I have been working with eBPF for the past few months.

I have been working on a solution that, for one reason or the other, requires me to make a BPF map where one u32 maps to a structure containing hundreds of entries (ACLs), let me demonstrate:

struct array_of_elements
{
    /*some data, around 9 members, all necessary to perform a scan on TC ingress*/
};

struct data_structure
{
    struct array_of_elements arr[600];
};

struct
{
    __uint(type, BPF_MAP_TYPE_HASH);
    __uint(max_entries, 10000);
    __type(key, u32);
    __type(value, struct data_structure);
} internal_map SEC(".maps");

The issue comes when I'm processing the data inside arr. I have a few loops that look like this:

for (int i = 0; i < 600; i++)
{
    if (lookup_result->arr[i].present) { /* some processing */ }
}

Increasing the number of elements beyond 600 triggers a "jump complexity too high" error. The array simulates ACLs, requiring iteration for processing. I attempted using nested BPF maps, but the limitation seems to be the loop through the array, not the array itself.

I have tried implementing inner-outer BPF maps setups, with BPF maps mapping to BPF arrays, but have not had any success, as the issue here is NOT the fact that I have an array, but that I have to iterate through it.

A cumbersome workaround has been to use the array elements as keys in a hashmap, but this approach is neither scalable nor maintainable. Is there a more elegant solution to this problem that avoids excessive looping while complying with the verifier's restrictions?

Answer 1

I would recommend looking into a map type such as LPM or some other methods of indexing your ACL. Even if you can fix the verifier limitation your program will be slow which might effect packet processing speed and throughput.

If that is not possible, you should look into using the bpf_loop helper. It is designed to allow large loops without the verifier getting in the way. The only downside is that it requires a kernel of at least v5.17.