[PATCH bpf-next 0/2] bpf, docs: Document BPF_MAP_TYPE_ARRAY

[PATCH bpf-next 0/2] bpf, docs: Document BPF_MAP_TYPE_ARRAY

[Dave Tucker]

This series is the beginning of my attempt to improve the BPF map and
program type documentation. It expands the template from
map_cgroup_storage to include the kernel version it was introduced.
I then used this template to document BPF_MAP_TYPE_ARRAY and 
BPF_MAP_TYPE_PERCPU_ARRAY

Dave Tucker (2):
  bpf, docs: add kernel version to map_cgroup_storage
  bpf, docs: document BPF_MAP_TYPE_ARRAY

 Documentation/bpf/map_array.rst          | 150 +++++++++++++++++++++++
 Documentation/bpf/map_cgroup_storage.rst |   2 +
 2 files changed, 152 insertions(+)
 create mode 100644 Documentation/bpf/map_array.rst

-- 
2.33.1

[PATCH bpf-next 1/2] bpf, docs: add kernel version to map_cgroup_storage

[Dave Tucker]

This adds the version at which this map became available to use in the
documentation

Signed-off-by: Dave Tucker <dave@dtucker.co.uk>
---
 Documentation/bpf/map_cgroup_storage.rst | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/Documentation/bpf/map_cgroup_storage.rst b/Documentation/bpf/map_cgroup_storage.rst
index cab9543017bf..b626cb068846 100644
--- a/Documentation/bpf/map_cgroup_storage.rst
+++ b/Documentation/bpf/map_cgroup_storage.rst
@@ -5,6 +5,8 @@
 BPF_MAP_TYPE_CGROUP_STORAGE
 ===========================
 
+.. note:: Introduced in Kernel version 4.19
+
 The ``BPF_MAP_TYPE_CGROUP_STORAGE`` map type represents a local fix-sized
 storage. It is only available with ``CONFIG_CGROUP_BPF``, and to programs that
 attach to cgroups; the programs are made available by the same Kconfig. The
-- 
2.33.1

[PATCH bpf-next 2/2] bpf, docs: document BPF_MAP_TYPE_ARRAY

[Dave Tucker]

This commit adds documentation for the BPF_MAP_TYPE_ARRAY including
kernel version introduced, usage and examples.
It also documents BPF_MAP_TYPE_PERCPU_ARRAY since this is similar.

Signed-off-by: Dave Tucker <dave@dtucker.co.uk>
---
 Documentation/bpf/map_array.rst | 150 ++++++++++++++++++++++++++++++++
 1 file changed, 150 insertions(+)
 create mode 100644 Documentation/bpf/map_array.rst

diff --git a/Documentation/bpf/map_array.rst b/Documentation/bpf/map_array.rst
new file mode 100644
index 000000000000..f9eb5473a240
--- /dev/null
+++ b/Documentation/bpf/map_array.rst
@@ -0,0 +1,150 @@
+.. SPDX-License-Identifier: GPL-2.0-only
+.. Copyright (C) 2021 Red Hat, Inc.
+
+================================================
+BPF_MAP_TYPE_ARRAY and BPF_MAP_TYPE_PERCPU_ARRAY
+================================================
+
+.. note:: ``BPF_MAP_TYPE_ARRAY`` was introduced in Kernel version 3.19 and ``BPF_MAP_TYPE_PERCPU_ARRAY`` in version 4.6
+
+``BPF_MAP_TYPE_ARRAY`` and ``BPF_MAP_TYPE_PERCPU_ARRAY`` provide generic array storage.
+The key type is an unsigned 32-bit integer (4 bytes) and the map is of constant size.
+All array elements are pre-allocated and zero initialized when created.
+``BPF_MAP_TYPE_PERCPU_ARRAY`` uses a different memory region for each CPU whereas
+``BPF_MAP_TYPE_ARRAY`` uses the same memory region.
+The maximum size of an array, defined in max_entries, is limited to 2^32.
+The value stored can be of any size, however, small values will be rounded up to 8 bytes.
+
+Usage
+=====
+
+Array elements can be retrieved using the ``bpf_map_lookup_elem()`` helper.
+This helper returns a pointer into the array element, so to avoid data races with userspace reading the value,
+the user must use primitives like ``__sync_fetch_and_add()`` when updating the value in-place.
+Access from userspace uses the libbpf API of the same name.
+
+Array elements can also be added using the ``bpf_map_update_elem()`` helper or libbpf API.
+
+Since the array is of constant size, ``bpf_map_delete_elem()`` is not supported.
+To clear an array element, you may use ``bpf_map_update_eleme()`` to insert a zero value to that index.
+
+Values stored in ``BPF_MAP_TYPE_ARRAY`` can be accessed by multiple programs across different CPUs.
+To restrict storage to a single CPU, you may use a ``BPF_MAP_TYPE_PERCPU_ARRAY``.
+Since Kernel version 5.1, the BPF infrastructure provides ``struct bpf_spin_lock`` to synchronize access.
+
+```bpf_map_get_next_key()`` can be used to iterate over array values.
+
+Examples
+========
+
+Please see the `bpf/samples`_ directory for functional examples.
+This sample code simply demonstrates the API.
+
+.. section links
+.. _bpf/samples:
+    https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/samples/bpf/
+
+Kernel
+------
+
+.. code-block:: c
+
+    struct {
+        __uint(type, BPF_MAP_TYPE_ARRAY);
+        __type(key, u32);
+        __type(value, long);
+        __uint(max_entries, 256);
+    } my_map SEC(".maps");
+
+    int bpf_prog(struct __sk_buff *skb)
+    {
+        int index = load_byte(skb, ETH_HLEN + offsetof(struct iphdr, protocol));
+        long *value;
+
+        if (skb->pkt_type != PACKET_OUTGOING)
+            return 0;
+
+        value = bpf_map_lookup_elem(&my_map, &index);
+        if (value)
+            __sync_fetch_and_add(value, skb->len);
+
+        return 0;
+    }
+
+Userspace
+---------
+
+BPF_MAP_TYPE_ARRAY
+~~~~~~~~~~~~~~~~~~
+
+.. code-block:: c
+
+    #include <assert.h>
+    #include <bpf/libbpf.h>
+    #include <bpf/bpf.h>
+
+    int main(int argc, char **argv)
+        {
+
+            int fd = bpf_create_map(BPF_MAP_TYPE_ARRAY, sizeof(__u32), sizeof(long), 256, 0);
+            if (fd < 0)
+            return -1;
+
+            // fill the map with values from 0-255
+            for(__u32 i=0; i < 256 ; i++) {
+                long v = i;
+                bpf_map_update_elem(fd, &i, &v, BPF_ANY);
+            }
+
+            __u32 index = 42;
+            long value;
+            bpf_map_lookup_elem(fd, &index, &value);
+            assert(value == 42);
+            return 0;
+    }
+
+
+BPF_MAP_TYPE_PERCPU_ARRAY
+~~~~~~~~~~~~~~~~~~~~~~~~~
+
+.. code-block:: c
+
+    #include <assert.h>
+    #include <bpf/libbpf.h>
+    #include <bpf/bpf.h>
+
+    int main(int argc, char **argv)
+        {
+            int ncpus = libbpf_num_possible_cpus();
+
+            int fd = bpf_create_map(BPF_MAP_TYPE_PERCPU_ARRAY, sizeof(__u32), sizeof(long), 256, 0);
+            if (fd < 0)
+            return -1;
+
+            // fill the map with values from 0-255 for each cpu
+            for(__u32 i=0; i < 256 ; i++) {
+                long v[ncpus];
+                for (int j=0; j < ncpus; j++ ) {
+                    v[j] = i;
+                }
+                bpf_map_update_elem(fd, &i, &v, BPF_ANY);
+            }
+
+            sleep(60);
+
+            __u32 index = 42;
+            long value[ncpus];
+            bpf_map_lookup_elem(fd, &index, &value);
+            for (int j=0; j < ncpus; j++ ) {
+                assert(value[j] == 42);
+            }
+            return 0;
+    }
+
+Semantics
+=========
+
+As illustrated in the example above, when using a ``BPF_MAP_TYPE_PERCPU_ARRAY`` in userspace, the
+values are an array with ``ncpus`` elements.
+
+When calling ``bpf_map_update_elem()`` the flags `BPF_NOEXIST` can not be used for these maps.
\ No newline at end of file
-- 
2.33.1

Re: [PATCH bpf-next 2/2] bpf, docs: document BPF_MAP_TYPE_ARRAY

[Jonathan Corbet]

Dave Tucker <dave@dtucker.co.uk> writes:

> This commit adds documentation for the BPF_MAP_TYPE_ARRAY including
> kernel version introduced, usage and examples.
> It also documents BPF_MAP_TYPE_PERCPU_ARRAY since this is similar.
>
> Signed-off-by: Dave Tucker <dave@dtucker.co.uk>
> ---
>  Documentation/bpf/map_array.rst | 150 ++++++++++++++++++++++++++++++++
>  1 file changed, 150 insertions(+)
>  create mode 100644 Documentation/bpf/map_array.rst

When you add a new BPF file, you need to add it to the corresponding
index.rst file as well.  Otherwise it won't be part of the docs build
and will, instead, generate the warning you surely saw when you tested
the build...:)

Thanks,

jon

Re: [PATCH bpf-next 2/2] bpf, docs: document BPF_MAP_TYPE_ARRAY

[Dave Tucker]

On Mon, 22 Nov 2021, at 19:15, Jonathan Corbet wrote:
> Dave Tucker <dave@dtucker.co.uk> writes:
>
> When you add a new BPF file, you need to add it to the corresponding
> index.rst file as well.  Otherwise it won't be part of the docs build
> and will, instead, generate the warning you surely saw when you tested
> the build...:)

I did test the build and I don't think I introduced any new warnings :)

This file is included in the docs build via the glob pattern that I added to 
the toctree in Documentation/bpf/maps.rst, which was recently applied to
bpf-next [1].

- Dave

[1]: https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/commit/?id=5931d9a3d0529dc803c792a10e52f0de1d0b9991

Re: [PATCH bpf-next 2/2] bpf, docs: document BPF_MAP_TYPE_ARRAY

[Jonathan Corbet]

"Dave Tucker" <dave@dtucker.co.uk> writes:

> On Mon, 22 Nov 2021, at 19:15, Jonathan Corbet wrote:
>> Dave Tucker <dave@dtucker.co.uk> writes:
>>
>> When you add a new BPF file, you need to add it to the corresponding
>> index.rst file as well.  Otherwise it won't be part of the docs build
>> and will, instead, generate the warning you surely saw when you tested
>> the build...:)
>
> I did test the build and I don't think I introduced any new warnings :)
>
> This file is included in the docs build via the glob pattern that I added to 
> the toctree in Documentation/bpf/maps.rst, which was recently applied to
> bpf-next [1].

Interesting, I didn't know about :glob: - thanks for teaching me
something and apologies for the noise :)

Thanks,

jon

Re: [PATCH bpf-next 2/2] bpf, docs: document BPF_MAP_TYPE_ARRAY

[Andrii Nakryiko]

On Mon, Nov 22, 2021 at 9:19 AM Dave Tucker <dave@dtucker.co.uk> wrote:
>
> This commit adds documentation for the BPF_MAP_TYPE_ARRAY including
> kernel version introduced, usage and examples.
> It also documents BPF_MAP_TYPE_PERCPU_ARRAY since this is similar.
>
> Signed-off-by: Dave Tucker <dave@dtucker.co.uk>
> ---
>  Documentation/bpf/map_array.rst | 150 ++++++++++++++++++++++++++++++++
>  1 file changed, 150 insertions(+)
>  create mode 100644 Documentation/bpf/map_array.rst
>
> diff --git a/Documentation/bpf/map_array.rst b/Documentation/bpf/map_array.rst
> new file mode 100644
> index 000000000000..f9eb5473a240
> --- /dev/null
> +++ b/Documentation/bpf/map_array.rst
> @@ -0,0 +1,150 @@
> +.. SPDX-License-Identifier: GPL-2.0-only
> +.. Copyright (C) 2021 Red Hat, Inc.
> +
> +================================================
> +BPF_MAP_TYPE_ARRAY and BPF_MAP_TYPE_PERCPU_ARRAY
> +================================================
> +
> +.. note:: ``BPF_MAP_TYPE_ARRAY`` was introduced in Kernel version 3.19 and ``BPF_MAP_TYPE_PERCPU_ARRAY`` in version 4.6
> +
> +``BPF_MAP_TYPE_ARRAY`` and ``BPF_MAP_TYPE_PERCPU_ARRAY`` provide generic array storage.
> +The key type is an unsigned 32-bit integer (4 bytes) and the map is of constant size.
> +All array elements are pre-allocated and zero initialized when created.
> +``BPF_MAP_TYPE_PERCPU_ARRAY`` uses a different memory region for each CPU whereas
> +``BPF_MAP_TYPE_ARRAY`` uses the same memory region.
> +The maximum size of an array, defined in max_entries, is limited to 2^32.
> +The value stored can be of any size, however, small values will be rounded up to 8 bytes.
> +
> +Usage
> +=====
> +
> +Array elements can be retrieved using the ``bpf_map_lookup_elem()`` helper.
> +This helper returns a pointer into the array element, so to avoid data races with userspace reading the value,
> +the user must use primitives like ``__sync_fetch_and_add()`` when updating the value in-place.
> +Access from userspace uses the libbpf API of the same name.
> +
> +Array elements can also be added using the ``bpf_map_update_elem()`` helper or libbpf API.
> +
> +Since the array is of constant size, ``bpf_map_delete_elem()`` is not supported.
> +To clear an array element, you may use ``bpf_map_update_eleme()`` to insert a zero value to that index.
> +
> +Values stored in ``BPF_MAP_TYPE_ARRAY`` can be accessed by multiple programs across different CPUs.
> +To restrict storage to a single CPU, you may use a ``BPF_MAP_TYPE_PERCPU_ARRAY``.
> +Since Kernel version 5.1, the BPF infrastructure provides ``struct bpf_spin_lock`` to synchronize access.
> +

It would be good to also mention BPF_F_MMAPABLE flag and ability to
mmap() contents of BPF_MAP_TYPE_ARRAY created with such a flag. We
need to double-check, but there might be also a restriction to have
value_size be a multiple of page size in such case, we need to consult
the code.


> +```bpf_map_get_next_key()`` can be used to iterate over array values.
> +
> +Examples
> +========
> +
> +Please see the `bpf/samples`_ directory for functional examples.

Let's point to tools/testing/selftests/bpf for functional examples.
It's much more complete and more actively maintained and tested.

> +This sample code simply demonstrates the API.
> +
> +.. section links
> +.. _bpf/samples:
> +    https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/samples/bpf/
> +
> +Kernel
> +------
> +
> +.. code-block:: c
> +
> +    struct {
> +        __uint(type, BPF_MAP_TYPE_ARRAY);
> +        __type(key, u32);
> +        __type(value, long);
> +        __uint(max_entries, 256);
> +    } my_map SEC(".maps");
> +
> +    int bpf_prog(struct __sk_buff *skb)
> +    {
> +        int index = load_byte(skb, ETH_HLEN + offsetof(struct iphdr, protocol));
> +        long *value;
> +
> +        if (skb->pkt_type != PACKET_OUTGOING)
> +            return 0;
> +
> +        value = bpf_map_lookup_elem(&my_map, &index);
> +        if (value)
> +            __sync_fetch_and_add(value, skb->len);
> +
> +        return 0;
> +    }
> +
> +Userspace
> +---------
> +
> +BPF_MAP_TYPE_ARRAY
> +~~~~~~~~~~~~~~~~~~
> +
> +.. code-block:: c
> +
> +    #include <assert.h>
> +    #include <bpf/libbpf.h>
> +    #include <bpf/bpf.h>
> +
> +    int main(int argc, char **argv)
> +        {

something is off with this curly brace

> +
> +            int fd = bpf_create_map(BPF_MAP_TYPE_ARRAY, sizeof(__u32), sizeof(long), 256, 0);
> +            if (fd < 0)
> +            return -1;

return not indented

and the example itself doesn't follow kernel style guide with
C89-style variable block separate from the rest of the code. Would be
good to stick to that in kernel documentation.

> +
> +            // fill the map with values from 0-255
> +            for(__u32 i=0; i < 256 ; i++) {

__u32 inside the for isn't C89-compatible either. Also C++-style
comment above isn't allowed.

> +                long v = i;
> +                bpf_map_update_elem(fd, &i, &v, BPF_ANY);

makes sense to do error checking for update and lookup

> +            }
> +
> +            __u32 index = 42;
> +            long value;
> +            bpf_map_lookup_elem(fd, &index, &value);
> +            assert(value == 42);
> +            return 0;
> +    }
> +
> +

[...]