netdev - Re: [PATCH bpf-next 3/6] bpf: allow for map-in-map with dynamic inner array map entries

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <6137b220-3678-af3c-8cee-c1b5d2a6e4e1@fb.com>
Date:   Thu, 8 Oct 2020 20:19:47 -0700
From:   Yonghong Song <yhs@...com>
To:     Daniel Borkmann <daniel@...earbox.net>, <ast@...nel.org>
CC:     <john.fastabend@...il.com>, <netdev@...r.kernel.org>,
        <bpf@...r.kernel.org>
Subject: Re: [PATCH bpf-next 3/6] bpf: allow for map-in-map with dynamic inner
 array map entries



On 10/8/20 2:31 PM, Daniel Borkmann 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@...earbox.net>

Acked-by: Yonghong Song <yhs@...com>