HASH_OF_MAPS inner map allocation from BPF

HASH_OF_MAPS inner map allocation from BPF

[Borna Cafuk]

Hello everyone,

Judging by [0], the inner maps in BPF_MAP_TYPE_HASH_OF_MAPS can only be created
from the userspace. This seems quite limiting in regard to what can be done
with them.

Are there any plans to allow for creating the inner maps from BPF programs?

[0] https://stackoverflow.com/a/63391528

Best regards,
Borna Cafuk

Re: HASH_OF_MAPS inner map allocation from BPF

[Alexei Starovoitov]

On Fri, Sep 4, 2020 at 7:57 AM Borna Cafuk <borna.cafuk@sartura.hr> wrote:
>
> Hello everyone,
>
> Judging by [0], the inner maps in BPF_MAP_TYPE_HASH_OF_MAPS can only be created
> from the userspace. This seems quite limiting in regard to what can be done
> with them.
>
> Are there any plans to allow for creating the inner maps from BPF programs?
>
> [0] https://stackoverflow.com/a/63391528

Did you ask that question or your use case is different?
Creating a new map for map_in_map from bpf prog can be implemented.
bpf_map_update_elem() is doing memory allocation for map elements.
In such a case calling this helper on map_in_map can, in theory, create a new
inner map and insert it into the outer map.

But if your use case it what stackoverflow says:
"
SEC("lsm/sb_alloc_security")
int BPF_PROG(sb_alloc_security, struct super_block *sb) {
    uuid_t key = sb->s_uuid; // use super block UUID as key to the outer_map
    // If key does not exist in outer_map,
    // create a new inner map and insert it
    // into the outer_map with the key
}
"
Then it would be more efficient, faster, easier to use if you could
extend the kernel with per-sb local storage.
We already have socket- and inode- local storage.
Other kernel data structures will fit the same infra.
You wouldn't need to hook into sb_alloc_security either.
From other lsm hooks you'll ask for super_block-local_stoarge and scratch
memory will be allocated on demand and automatically freed with sb.

Re: HASH_OF_MAPS inner map allocation from BPF

[KP Singh]

[+lists, format=plain text]

On Sat, Sep 5, 2020 at 4:48 PM KP Singh <kpsingh@google.com> wrote:
>
>
>
> On Sat, Sep 5, 2020 at 12:47 AM Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote:
>>
>> On Fri, Sep 4, 2020 at 7:57 AM Borna Cafuk <borna.cafuk@sartura.hr> wrote:
>> >
>> > Hello everyone,
>> >
>> > Judging by [0], the inner maps in BPF_MAP_TYPE_HASH_OF_MAPS can only be created
>> > from the userspace. This seems quite limiting in regard to what can be done
>> > with them.
>> >
>> > Are there any plans to allow for creating the inner maps from BPF programs?
>> >
>> > [0] https://stackoverflow.com/a/63391528
>>
>> Did you ask that question or your use case is different?
>> Creating a new map for map_in_map from bpf prog can be implemented.
>> bpf_map_update_elem() is doing memory allocation for map elements.
>> In such a case calling this helper on map_in_map can, in theory, create a new
>> inner map and insert it into the outer map.
>>
>> But if your use case it what stackoverflow says:
>> "
>> SEC("lsm/sb_alloc_security")
>> int BPF_PROG(sb_alloc_security, struct super_block *sb) {
>>     uuid_t key = sb->s_uuid; // use super block UUID as key to the outer_map
>>     // If key does not exist in outer_map,
>>     // create a new inner map and insert it
>>     // into the outer_map with the key
>> }
>> "
>
>
> Indeed, if you want to associate some information with super_block objects
> in LSM programs, local storage fits better.
>
> It would help if you can shed some more light on your use case.
>
>> Then it would be more efficient, faster, easier to use if you could
>> extend the kernel with per-sb local storage.
>
>
> Now that we have generalized local storage, this should not be much work.
>
> Please have a look at
> https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/kernel/bpf/bpf_inode_storage.c
>
> and the example in:
>
> https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/tools/testing/selftests/bpf/progs/local_storage.c#n121
>
> We will need something similar for super_block as well.
>
> - KP
>
>> We already have socket- and inode- local storage.
>> Other kernel data structures will fit the same infra.
>> You wouldn't need to hook into sb_alloc_security either.
>> From other lsm hooks you'll ask for super_block-local_stoarge and scratch
>> memory will be allocated on demand and automatically freed with sb.

Re: HASH_OF_MAPS inner map allocation from BPF

[Borna Cafuk]

On Sat, Sep 5, 2020 at 12:47 AM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Fri, Sep 4, 2020 at 7:57 AM Borna Cafuk <borna.cafuk@sartura.hr> wrote:
> >
> > Hello everyone,
> >
> > Judging by [0], the inner maps in BPF_MAP_TYPE_HASH_OF_MAPS can only be created
> > from the userspace. This seems quite limiting in regard to what can be done
> > with them.
> >
> > Are there any plans to allow for creating the inner maps from BPF programs?
> >
> > [0] https://stackoverflow.com/a/63391528
>
> Did you ask that question or your use case is different?
> Creating a new map for map_in_map from bpf prog can be implemented.
> bpf_map_update_elem() is doing memory allocation for map elements.
> In such a case calling this helper on map_in_map can, in theory, create a new
> inner map and insert it into the outer map.

No, it wasn't me who asked that question, but it seemed close enough to
my issue. My use case calls for modifying the syscount example from BCC[1].

The idea is to have an outer map where the keys are PIDs, and inner maps where
the keys are system call numbers. This would enable tracking the number of
syscalls made by each process and the makeup of those calls for all processes
simultaneously.

[1] https://github.com/iovisor/bcc/blob/master/libbpf-tools/syscount.bpf.c


>
> But if your use case it what stackoverflow says:
> "
> SEC("lsm/sb_alloc_security")
> int BPF_PROG(sb_alloc_security, struct super_block *sb) {
>     uuid_t key = sb->s_uuid; // use super block UUID as key to the outer_map
>     // If key does not exist in outer_map,
>     // create a new inner map and insert it
>     // into the outer_map with the key
> }
> "
> Then it would be more efficient, faster, easier to use if you could
> extend the kernel with per-sb local storage.
> We already have socket- and inode- local storage.
> Other kernel data structures will fit the same infra.
> You wouldn't need to hook into sb_alloc_security either.
> From other lsm hooks you'll ask for super_block-local_stoarge and scratch
> memory will be allocated on demand and automatically freed with sb.

Re: HASH_OF_MAPS inner map allocation from BPF

[Toke Høiland-Jørgensen]

Borna Cafuk <borna.cafuk@sartura.hr> writes:

> On Sat, Sep 5, 2020 at 12:47 AM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
>>
>> On Fri, Sep 4, 2020 at 7:57 AM Borna Cafuk <borna.cafuk@sartura.hr> wrote:
>> >
>> > Hello everyone,
>> >
>> > Judging by [0], the inner maps in BPF_MAP_TYPE_HASH_OF_MAPS can only be created
>> > from the userspace. This seems quite limiting in regard to what can be done
>> > with them.
>> >
>> > Are there any plans to allow for creating the inner maps from BPF programs?
>> >
>> > [0] https://stackoverflow.com/a/63391528
>>
>> Did you ask that question or your use case is different?
>> Creating a new map for map_in_map from bpf prog can be implemented.
>> bpf_map_update_elem() is doing memory allocation for map elements.
>> In such a case calling this helper on map_in_map can, in theory, create a new
>> inner map and insert it into the outer map.
>
> No, it wasn't me who asked that question, but it seemed close enough to
> my issue. My use case calls for modifying the syscount example from BCC[1].
>
> The idea is to have an outer map where the keys are PIDs, and inner maps where
> the keys are system call numbers. This would enable tracking the number of
> syscalls made by each process and the makeup of those calls for all processes
> simultaneously.
>
> [1] https://github.com/iovisor/bcc/blob/master/libbpf-tools/syscount.bpf.c

Well, if you just want to count, map-in-map seems a bit overkill? You
could just do:

struct {
  u32 pid;
  u32 syscall;
} map_key;

and use that?

-Toke

Re: HASH_OF_MAPS inner map allocation from BPF

[Borna Cafuk]

On Mon, Sep 7, 2020 at 3:33 PM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>
> Borna Cafuk <borna.cafuk@sartura.hr> writes:
>
> > On Sat, Sep 5, 2020 at 12:47 AM Alexei Starovoitov
> > <alexei.starovoitov@gmail.com> wrote:
> >>
> >> On Fri, Sep 4, 2020 at 7:57 AM Borna Cafuk <borna.cafuk@sartura.hr> wrote:
> >> >
> >> > Hello everyone,
> >> >
> >> > Judging by [0], the inner maps in BPF_MAP_TYPE_HASH_OF_MAPS can only be created
> >> > from the userspace. This seems quite limiting in regard to what can be done
> >> > with them.
> >> >
> >> > Are there any plans to allow for creating the inner maps from BPF programs?
> >> >
> >> > [0] https://stackoverflow.com/a/63391528
> >>
> >> Did you ask that question or your use case is different?
> >> Creating a new map for map_in_map from bpf prog can be implemented.
> >> bpf_map_update_elem() is doing memory allocation for map elements.
> >> In such a case calling this helper on map_in_map can, in theory, create a new
> >> inner map and insert it into the outer map.
> >
> > No, it wasn't me who asked that question, but it seemed close enough to
> > my issue. My use case calls for modifying the syscount example from BCC[1].
> >
> > The idea is to have an outer map where the keys are PIDs, and inner maps where
> > the keys are system call numbers. This would enable tracking the number of
> > syscalls made by each process and the makeup of those calls for all processes
> > simultaneously.
> >
> > [1] https://github.com/iovisor/bcc/blob/master/libbpf-tools/syscount.bpf.c
>
> Well, if you just want to count, map-in-map seems a bit overkill? You
> could just do:
>
> struct {
>   u32 pid;
>   u32 syscall;
> } map_key;
>
> and use that?
>
> -Toke
>

I have considered that, but maps in maps seem better for when I need to get the
data about a single process's syscalls: It requires reading only one of the
inner maps in its entirety. If I have a composite key like that, I don't see
any way, other than:
 * either iterating through all the possible keys for a process
   (i.e. over all syscalls) and looking them up in the map, or
 * iterating over all entries in the map and filtering them.

Looking at it again, the first option does not seem _that_ bad, but just
iterating over one (inner) map would be easier to fit into our use-case.

Re: HASH_OF_MAPS inner map allocation from BPF

[Toke Høiland-Jørgensen]

Borna Cafuk <borna.cafuk@sartura.hr> writes:

> On Mon, Sep 7, 2020 at 3:33 PM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>>
>> Borna Cafuk <borna.cafuk@sartura.hr> writes:
>>
>> > On Sat, Sep 5, 2020 at 12:47 AM Alexei Starovoitov
>> > <alexei.starovoitov@gmail.com> wrote:
>> >>
>> >> On Fri, Sep 4, 2020 at 7:57 AM Borna Cafuk <borna.cafuk@sartura.hr> wrote:
>> >> >
>> >> > Hello everyone,
>> >> >
>> >> > Judging by [0], the inner maps in BPF_MAP_TYPE_HASH_OF_MAPS can only be created
>> >> > from the userspace. This seems quite limiting in regard to what can be done
>> >> > with them.
>> >> >
>> >> > Are there any plans to allow for creating the inner maps from BPF programs?
>> >> >
>> >> > [0] https://stackoverflow.com/a/63391528
>> >>
>> >> Did you ask that question or your use case is different?
>> >> Creating a new map for map_in_map from bpf prog can be implemented.
>> >> bpf_map_update_elem() is doing memory allocation for map elements.
>> >> In such a case calling this helper on map_in_map can, in theory, create a new
>> >> inner map and insert it into the outer map.
>> >
>> > No, it wasn't me who asked that question, but it seemed close enough to
>> > my issue. My use case calls for modifying the syscount example from BCC[1].
>> >
>> > The idea is to have an outer map where the keys are PIDs, and inner maps where
>> > the keys are system call numbers. This would enable tracking the number of
>> > syscalls made by each process and the makeup of those calls for all processes
>> > simultaneously.
>> >
>> > [1] https://github.com/iovisor/bcc/blob/master/libbpf-tools/syscount.bpf.c
>>
>> Well, if you just want to count, map-in-map seems a bit overkill? You
>> could just do:
>>
>> struct {
>>   u32 pid;
>>   u32 syscall;
>> } map_key;
>>
>> and use that?
>>
>> -Toke
>>
>
> I have considered that, but maps in maps seem better for when I need to get the
> data about a single process's syscalls: It requires reading only one of the
> inner maps in its entirety. If I have a composite key like that, I don't see
> any way, other than:
>  * either iterating through all the possible keys for a process
>    (i.e. over all syscalls) and looking them up in the map, or
>  * iterating over all entries in the map and filtering them.
>
> Looking at it again, the first option does not seem _that_ bad,

You could even use BPF_MAP_LOOKUP_BATCH to do this in one operation, I
suppose...

> but just iterating over one (inner) map would be easier to fit into
> our use-case.

...but yeah, I see what you mean. Well, maybe BPF local storage per
process would also be a nice fit here?

-Toke

Re: HASH_OF_MAPS inner map allocation from BPF

[KP Singh]

On Wed, Sep 9, 2020 at 12:24 PM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>
> Borna Cafuk <borna.cafuk@sartura.hr> writes:
>
> > On Mon, Sep 7, 2020 at 3:33 PM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
> >>
> >> Borna Cafuk <borna.cafuk@sartura.hr> writes:
> >>
> >> > On Sat, Sep 5, 2020 at 12:47 AM Alexei Starovoitov
> >> > <alexei.starovoitov@gmail.com> wrote:

[...]

> >> >
> >> > The idea is to have an outer map where the keys are PIDs, and inner maps where
> >> > the keys are system call numbers. This would enable tracking the number of
> >> > syscalls made by each process and the makeup of those calls for all processes
> >> > simultaneously.
> >> >
> >> > [1] https://github.com/iovisor/bcc/blob/master/libbpf-tools/syscount.bpf.c
> >>
> >> Well, if you just want to count, map-in-map seems a bit overkill? You
> >> could just do:
> >>
> >> struct {
> >>   u32 pid;
> >>   u32 syscall;
> >> } map_key;
> >>
> >> and use that?
> >>
> >> -Toke
> >>
> >
> > I have considered that, but maps in maps seem better for when I need to get the
> > data about a single process's syscalls: It requires reading only one of the
> > inner maps in its entirety. If I have a composite key like that, I don't see
> > any way, other than:
> >  * either iterating through all the possible keys for a process
> >    (i.e. over all syscalls) and looking them up in the map, or
> >  * iterating over all entries in the map and filtering them.
> >
> > Looking at it again, the first option does not seem _that_ bad,
>
> You could even use BPF_MAP_LOOKUP_BATCH to do this in one operation, I
> suppose...
>
> > but just iterating over one (inner) map would be easier to fit into
> > our use-case.
>
> ...but yeah, I see what you mean. Well, maybe BPF local storage per
> process would also be a nice fit here?

Yes, task local storage does seem like a good fit and is the next one I was
thinking of implementing.

- KP

>
> -Toke
>

Re: HASH_OF_MAPS inner map allocation from BPF

[Borna Cafuk]

On Wed, Sep 9, 2020 at 12:36 PM KP Singh <kpsingh@google.com> wrote:
>
> On Wed, Sep 9, 2020 at 12:24 PM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
> >
> > Borna Cafuk <borna.cafuk@sartura.hr> writes:
> >
> > > On Mon, Sep 7, 2020 at 3:33 PM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
> > >>
> > >> Borna Cafuk <borna.cafuk@sartura.hr> writes:
> > >>
> > >> > On Sat, Sep 5, 2020 at 12:47 AM Alexei Starovoitov
> > >> > <alexei.starovoitov@gmail.com> wrote:
>
> [...]
>
> > >> >
> > >> > The idea is to have an outer map where the keys are PIDs, and inner maps where
> > >> > the keys are system call numbers. This would enable tracking the number of
> > >> > syscalls made by each process and the makeup of those calls for all processes
> > >> > simultaneously.
> > >> >
> > >> > [1] https://github.com/iovisor/bcc/blob/master/libbpf-tools/syscount.bpf.c
> > >>
> > >> Well, if you just want to count, map-in-map seems a bit overkill? You
> > >> could just do:
> > >>
> > >> struct {
> > >>   u32 pid;
> > >>   u32 syscall;
> > >> } map_key;
> > >>
> > >> and use that?
> > >>
> > >> -Toke
> > >>
> > >
> > > I have considered that, but maps in maps seem better for when I need to get the
> > > data about a single process's syscalls: It requires reading only one of the
> > > inner maps in its entirety. If I have a composite key like that, I don't see
> > > any way, other than:
> > >  * either iterating through all the possible keys for a process
> > >    (i.e. over all syscalls) and looking them up in the map, or
> > >  * iterating over all entries in the map and filtering them.
> > >
> > > Looking at it again, the first option does not seem _that_ bad,
> >
> > You could even use BPF_MAP_LOOKUP_BATCH to do this in one operation, I
> > suppose...
> >
> > > but just iterating over one (inner) map would be easier to fit into
> > > our use-case.
> >
> > ...but yeah, I see what you mean. Well, maybe BPF local storage per
> > process would also be a nice fit here?

Thank you for the insight.

>
> Yes, task local storage does seem like a good fit and is the next one I was
> thinking of implementing.
>
> - KP

I'm looking forward to the patches.

>
> >
> > -Toke
> >