Allow static initialization for BPF_MAP_TYPE_HASH_OF_MAPS map with integer as key_size

[shpalani]

Describe the bug

Request: Allow static initialization for BPF_MAP_TYPE_HASH_OF_MAPS map value with integer as key_size.

Reason: BPF_MAP_TYPE_HASH_OF_MAPS style maps have no implicit key value but if the key type is defined as an integer, it can be statically initialized.

Reference:

1. https://docs.kernel.org/bpf/map_of_maps.html
   "For BPF_MAP_TYPE_HASH_OF_MAPS the key type can be chosen when defining the map. "
2. https://github.com/libbpf/libbpf/blob/e26b84dc330c9644c07428c271ab491b0f01f4e1/src/libbpf.c#L6779C1-L6784C5

Map structure:

struct {
		__uint(type, **BPF_MAP_TYPE_ARRAY)**;
		__uint(key_size, sizeof(__u32));
		__uint(value_size, sizeof(__u32) * LB_MAGLEV_LUT_SIZE);
		__uint(max_entries, 1);
} LB6_MAGLEV_MAP_INNER  __section_maps_btf;

struct {
	__uint(type, **BPF_MAP_TYPE_HASH_OF_MAPS**);
	__type(key, __u16);
	__type(value, __u32);
	__uint(pinning, LIBBPF_PIN_BY_NAME);
	__uint(max_entries, CILIUM_LB_MAGLEV_MAP_MAX_ENTRIES);
	__uint(map_flags, CONDITIONAL_PREALLOC);
	/* Maglev inner map definition */
	__array(values, LB6_MAGLEV_MAP_INNER);
} LB6_MAGLEV_MAP_OUTER __section_maps_btf = {
    .values = {&LB6_MAGLEV_MAP_INNER},
};

OS information

Windows 10 and above

Steps taken to reproduce bug

Please see #2882.

Expected behavior

Hash-of-maps should be statically initialized if the key is an integer.

Actual outcome

Please see #2882 for analysis.

Additional details

No response

[shankarseal]

I think this issue stemmed from the fact that the native program loader failed to load Cilium XDP program with the following map definition.

struct {
    __uint(type, BPF_MAP_TYPE_HASH_OF_MAPS);
    __type(key, __u16);
    __type(value, __u32);
    __uint(pinning, LIBBPF_PIN_BY_NAME);
    __uint(max_entries, CILIUM_LB_MAGLEV_MAP_MAX_ENTRIES);
    __uint(map_flags, CONDITIONAL_PREALLOC);
    /* Maglev inner map definition */
    __array(values, struct {
        __uint(type, BPF_MAP_TYPE_ARRAY);
        __uint(key_size, sizeof(__u32));
        __uint(value_size, sizeof(__u32) * LB_MAGLEV_LUT_SIZE);
        __uint(max_entries, 1);
    });

This is tracked by: Issue #2854

While trying to work around this, I inadvertently made an incorrect suggestion that on Windows we could represent the above as:

struct
{
    __uint(type, BPF_MAP_TYPE_HASH);
    __type(key, uint32_t);
    __type(value, uint32_t);
    __uint(max_entries, 1);
} inner_map SEC(".maps");

 
struct
{
    __uint(type, BPF_MAP_TYPE_HASH_OF_MAPS);
    __type(key, uint32_t);
    __type(value, uint32_t);
    __uint(max_entries, 1);
    __array(values, inner_map);
} outer_map SEC(".maps") = {
    .values = {&inner_map},
};

The static initialization part at the end is not needed at all. And it created further issues with loading the program as static initializing a hashmap was not supported.

Later @Alan-Jowett found out this super corner case in Linux where this is actually supported. Here is the slack channel conversation:

Why create a hashmap if “use it exactly the same way as array” ? Also, I don’t buy that key-size of 4 bytes implies the key is actually an integer and can be used as an array index. Instead the key type should be an integer type.

Pull Request #2952 attempts to replicate the Linux behavior. But I am not sure if it actually does as what the slack conversation above suggests.

The _ebpf_native_set_initial_map_values function was originally meant for arraymaps and prog_arrays only. It treats the outer map as an array and adds the inner map instances to it with the array index as key here:

        // For each value in the map, find the map or program to insert.
        for (size_t j = 0; j < map_initial_values[i].count; j++) {
            . . .
            uint32_t key = (uint32_t)j;
            result = ebpf_core_update_map_with_handle(
                native_map_to_update->handle,
                (uint8_t*)&key,
                native_map_to_update->entry->definition.key_size,
                handle_to_insert);
            if (result != EBPF_SUCCESS) {
                break;
            }
        }

See how the inner maps are inserted using ebpf_core_update_map_with_handle. Since the outer map is defined as a hashmap; the update function will eventually invoke ebpf_hash_table_update which would compute a hash of the key by invoking _ebpf_murmur3_32. So unlike array, there is no “order” in the entries. Not sure if this is a big deal.

Also, I have doubts about if this should work for keys of size 1 byte and 2 bytes which the above PR allows.

And most importantly the Cilium program does not static initialize the hashmaps. For example, the maglev map (hashmap); even though has a key of type uint16_t; its not really an array index – it’s the service ID. So static intitilization does not make any sense for the maglev map.

[shankarseal]

We should also consider putting a more robust initialization method where both {key, values} are specified.

[dahavey]

Fixed by #3211