On Fri, Oct 9, 2020 at 7:13 AM Daniel Borkmann <daniel@xxxxxxxxxxxxx> wrote:
>
> Recent work in f4d05259213f ("bpf: Add map_meta_equal map ops") and 134fede4eecf
> ("bpf: Relax max_entries check for most of the inner map types") added support
> for dynamic inner max elements for most map-in-map types. Exceptions were maps
> like array or prog array where the map_gen_lookup() callback uses the maps'
> max_entries field as a constant when emitting instructions.
>
> We recently implemented Maglev consistent hashing into Cilium's load balancer
> which uses map-in-map with an outer map being hash and inner being array holding
> the Maglev backend table for each service. This has been designed this way in
> order to reduce overall memory consumption given the outer hash map allows to
> avoid preallocating a large, flat memory area for all services. Also, the
> number of service mappings is not always known a-priori.
>
> The use case for dynamic inner array map entries is to further reduce memory
> overhead, for example, some services might just have a small number of back
> ends while others could have a large number. Right now the Maglev backend table
> for small and large number of backends would need to have the same inner array
> map entries which adds a lot of unneeded overhead.
>
> Dynamic inner array map entries can be realized by avoiding the inlined code
> generation for their lookup. The lookup will still be efficient since it will
> be calling into array_map_lookup_elem() directly and thus avoiding retpoline.
> The patch adds a BPF_F_NO_INLINE flag to map creation which internally swaps
> out map ops with a variant that does not have map_gen_lookup() callback and
> a relaxed map_meta_equal() that calls bpf_map_meta_equal() directly.
>
> Example code generation where inner map is dynamic sized array:
>
> # bpftool p d x i 125
> int handle__sys_enter(void * ctx):
> ; int handle__sys_enter(void *ctx)
> 0: (b4) w1 = 0
> ; int key = 0;
> 1: (63) *(u32 *)(r10 -4) = r1
> 2: (bf) r2 = r10
> ;
> 3: (07) r2 += -4
> ; inner_map = bpf_map_lookup_elem(&outer_arr_dyn, &key);
> 4: (18) r1 = map[id:468]
> 6: (07) r1 += 272
> 7: (61) r0 = *(u32 *)(r2 +0)
> 8: (35) if r0 >= 0x3 goto pc+5
> 9: (67) r0 <<= 3
> 10: (0f) r0 += r1
> 11: (79) r0 = *(u64 *)(r0 +0)
> 12: (15) if r0 == 0x0 goto pc+1
> 13: (05) goto pc+1
> 14: (b7) r0 = 0
> 15: (b4) w6 = -1
> ; if (!inner_map)
> 16: (15) if r0 == 0x0 goto pc+6
> 17: (bf) r2 = r10
> ;
> 18: (07) r2 += -4
> ; val = bpf_map_lookup_elem(inner_map, &key);
> 19: (bf) r1 = r0 | No inlining but instead
> 20: (85) call array_map_lookup_elem#149280 | call to array_map_lookup_elem()
> ; return val ? *val : -1; | for inner array lookup.
> 21: (15) if r0 == 0x0 goto pc+1
> ; return val ? *val : -1;
> 22: (61) r6 = *(u32 *)(r0 +0)
> ; }
> 23: (bc) w0 = w6
> 24: (95) exit
>
> Signed-off-by: Daniel Borkmann <daniel@xxxxxxxxxxxxx>
> Acked-by: Yonghong Song <yhs@xxxxxx>
> ---
> include/linux/bpf.h | 1 +
> include/uapi/linux/bpf.h | 5 +++++
> kernel/bpf/arraymap.c | 40 ++++++++++++++++++++++++++++++++--
> kernel/bpf/syscall.c | 3 ++-
> tools/include/uapi/linux/bpf.h | 5 +++++
> 5 files changed, 51 insertions(+), 3 deletions(-)
>
[...]
>
> +/* Variant which does not have map_gen_lookup() implementation, but
> + * therefore can relax map_meta_equal() check to allow for dynamic
> + * max_entries for inner maps.
> + */
> +const struct bpf_map_ops array_map_no_inline_ops = {
> + .map_meta_equal = bpf_map_meta_equal,
> + .map_alloc_check = array_map_alloc_check,
> + .map_alloc = array_map_alloc,
> + .map_free = array_map_free,
> + .map_get_next_key = array_map_get_next_key,
> + .map_lookup_elem = array_map_lookup_elem,
> + .map_update_elem = array_map_update_elem,
> + .map_delete_elem = array_map_delete_elem,
> + .map_direct_value_addr = array_map_direct_value_addr,
> + .map_direct_value_meta = array_map_direct_value_meta,
> + .map_mmap = array_map_mmap,
> + .map_seq_show_elem = array_map_seq_show_elem,
> + .map_check_btf = array_map_check_btf,
> + .map_lookup_batch = generic_map_lookup_batch,
> + .map_update_batch = generic_map_update_batch,
> + .map_btf_name = "bpf_array",
> + .map_btf_id = &array_map_btf_id,
> + .iter_seq_info = &iter_seq_info,
> +};
> +
> static int percpu_array_map_btf_id;
> const struct bpf_map_ops percpu_array_map_ops = {
> .map_meta_equal = bpf_map_meta_equal,
> diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
> index 1110ecd7d1f3..519bf867f065 100644
> --- a/kernel/bpf/syscall.c
> +++ b/kernel/bpf/syscall.c
> @@ -111,7 +111,8 @@ static struct bpf_map *find_and_alloc_map(union bpf_attr *attr)
> ops = bpf_map_types[type];
> if (!ops)
> return ERR_PTR(-EINVAL);
> -
> + if (ops->map_swap_ops)
> + ops = ops->map_swap_ops(attr);
I'm afraid that this can cause quite a lot of confusion down the road.
Wouldn't designating -EOPNOTSUPP return code from map_gen_lookup() and
not inlining in that case as if map_gen_lookup() wasn't even defined
be a much smaller and more local (semantically) change that achieves
exactly the same thing? Doesn't seem like switching from u32 to int
for return value would be a big inconvenience for existing
implementations of inlining callbacks, right?
> if (ops->map_alloc_check) {
> err = ops->map_alloc_check(attr);
> if (err)
> diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
> index ea8dfbe62c7a..eb384264f906 100644
> --- a/tools/include/uapi/linux/bpf.h
> +++ b/tools/include/uapi/linux/bpf.h
> @@ -435,6 +435,11 @@ enum {
>
> /* Share perf_event among processes */
> BPF_F_PRESERVE_ELEMS = (1U << 11),
> +
> +/* Do not inline (array) map lookups so the array map can be used for
> + * map in map with dynamic max entries.
> + */
> + BPF_F_NO_INLINE = (1U << 12),
> };
>
> /* Flags for BPF_PROG_QUERY. */
> --
> 2.21.0
>
