[bpf-next,v3] docs/bpf: Document BPF map types QUEUE and STACK

Commit Message

Donald Hunter Nov. 8, 2022, 9:33 a.m. UTC

Add documentation for BPF_MAP_TYPE_QUEUE and BPF_MAP_TYPE_STACK,
including usage and examples.

Signed-off-by: Donald Hunter <[e-mail]>
---
v2 -> v3:
- Add BPF_EXIST to valid flags as reported by Yonghong Song
- Clarify valid flags for bpf_map_push_elem

v1 -> v2:
- Mention "libbpf's low-level API", as reported by Andrii Nakryiko
- Replace 0 with NULL in code snippet, as reported by Andrii Nakryiko
---
 Documentation/bpf/map_queue_stack.rst | 122 ++++++++++++++++++++++++++
 1 file changed, 122 insertions(+)
 create mode 100644 Documentation/bpf/map_queue_stack.rst

Comments

Bagas Sanjaya Nov. 8, 2022, 12:57 p.m. UTC | #1

On Tue, Nov 08, 2022 at 09:33:14AM +0000, Donald Hunter wrote:
> diff --git a/Documentation/bpf/map_queue_stack.rst b/Documentation/bpf/map_queue_stack.rst
> new file mode 100644
> index 000000000000..f20e31a647b9
> --- /dev/null
> +++ b/Documentation/bpf/map_queue_stack.rst
> @@ -0,0 +1,122 @@
> +.. SPDX-License-Identifier: GPL-2.0-only
> +.. Copyright (C) 2022 Red Hat, Inc.
> +
> +=========================================
> +BPF_MAP_TYPE_QUEUE and BPF_MAP_TYPE_STACK
> +=========================================
> +
> +.. note::
> +   - ``BPF_MAP_TYPE_QUEUE`` and ``BPF_MAP_TYPE_STACK`` were introduced
> +     in kernel version 4.20
> +
> +``BPF_MAP_TYPE_QUEUE`` provides FIFO storage and ``BPF_MAP_TYPE_STACK``
> +provides LIFO storage for BPF programs. These maps support peek, pop and
> +push operations that are exposed to BPF programs through the respective
> +helpers. These operations are exposed to userspace applications using
> +the existing ``bpf`` syscall in the following way:
> +
> +- ``BPF_MAP_LOOKUP_ELEM`` -> peek
> +- ``BPF_MAP_LOOKUP_AND_DELETE_ELEM`` -> pop
> +- ``BPF_MAP_UPDATE_ELEM`` -> push
> +
> +``BPF_MAP_TYPE_QUEUE`` and ``BPF_MAP_TYPE_STACK`` do not support
> +``BPF_F_NO_PREALLOC``.
> +
> +Usage
> +=====
> +
> +Kernel BPF
> +----------
> +
> +.. c:function::
> +   long bpf_map_push_elem(struct bpf_map *map, const void *value, u64 flags)
> +
> +An element ``value`` can be added to a queue or stack using the
> +``bpf_map_push_elem`` helper. The ``flags`` parameter must be set to
> +``BPF_ANY`` or ``BPF_EXIST``. If ``flags`` is set to ``BPF_EXIST`` then,
> +when the queue or stack is full, the oldest element will be removed to
> +make room for ``value`` to be added. Returns ``0`` on success, or
> +negative error in case of failure.
> +
> +.. c:function::
> +   long bpf_map_peek_elem(struct bpf_map *map, void *value)
> +
> +This helper fetches an element ``value`` from a queue or stack without
> +removing it. Returns ``0`` on success, or negative error in case of
> +failure.
> +
> +.. c:function::
> +   long bpf_map_pop_elem(struct bpf_map *map, void *value)
> +
> +This helper removes an element into ``value`` from a queue or
> +stack. Returns ``0`` on success, or negative error in case of failure.
> +
> +
> +Userspace
> +---------
> +
> +.. c:function::
> +   int bpf_map_update_elem (int fd, const void *key, const void *value, __u64 flags)
> +
> +A userspace program can push ``value`` onto a queue or stack using libbpf's
> +``bpf_map_update_elem`` function. The ``key`` parameter must be set to
> +``NULL`` and ``flags`` must be set to ``BPF_ANY`` or ``BPF_EXIST``, with the
> +same semantics as the ``bpf_map_push_elem`` kernel helper. Returns ``0`` on
> +success, or negative error in case of failure.
> +
> +.. c:function::
> +   int bpf_map_lookup_elem (int fd, const void *key, void *value)
> +
> +A userspace program can peek at the ``value`` at the head of a queue or stack
> +using the libbpf ``bpf_map_lookup_elem`` function. The ``key`` parameter must be
> +set to ``NULL``.  Returns ``0`` on success, or negative error in case of
> +failure.
> +
> +.. c:function::
> +   int bpf_map_lookup_and_delete_elem (int fd, const void *key, void *value)
> +
> +A userspace program can pop a ``value`` from the head of a queue or stack using
> +the libbpf ``bpf_map_lookup_and_delete_elem`` function. The ``key`` parameter
> +must be set to ``NULL``. Returns ``0`` on success, or negative error in case of
> +failure.
> +
> +Examples
> +========
> +
> +Kernel BPF
> +----------
> +
> +This snippet shows how to declare a queue in a BPF program:
> +
> +.. code-block:: c
> +
> +    struct {
> +            __uint(type, BPF_MAP_TYPE_QUEUE);
> +            __type(value, __u32);
> +            __uint(max_entries, 10);
> +    } queue SEC(".maps");
> +
> +
> +Userspace
> +---------
> +
> +This snippet shows how to use libbpf's low-level API to create a queue from
> +userspace:
> +
> +.. code-block:: c
> +
> +    int create_queue()
> +    {
> +            return bpf_map_create(BPF_MAP_TYPE_QUEUE,
> +                                  "sample_queue", /* name */
> +                                  0,              /* key size, must be zero */
> +                                  sizeof(__u32),  /* value size */
> +                                  10,             /* max entries */
> +                                  NULL);          /* create options */
> +    }
> +
> +
> +References
> +==========
> +
> +https://lwn.net/ml/netdev/153986858555.9127.14517764371945179514.stgit@kernel/

You forgot to add the documentation to BPF toctree:

---- >8 ----

diff --git a/Documentation/bpf/index.rst b/Documentation/bpf/index.rst
index 1b50de1983ee2c..113872fa0193d7 100644
--- a/Documentation/bpf/index.rst
+++ b/Documentation/bpf/index.rst
@@ -22,6 +22,7 @@ that goes into great technical depth about the BPF Architecture.
    kfuncs
    programs
    maps
+   map_queue_stack
    bpf_prog_run
    classic_vs_extended.rst
    bpf_licensing

Thanks.

Yonghong Song Nov. 8, 2022, 2:39 p.m. UTC | #2

On 11/8/22 1:33 AM, Donald Hunter wrote:
> Add documentation for BPF_MAP_TYPE_QUEUE and BPF_MAP_TYPE_STACK,
> including usage and examples.
> 
> Signed-off-by: Donald Hunter <[e-mail]>

Acked-by: Yonghong Song <[e-mail]>

Yonghong Song Nov. 8, 2022, 2:50 p.m. UTC | #3

On 11/8/22 4:57 AM, Bagas Sanjaya wrote:
> On Tue, Nov 08, 2022 at 09:33:14AM +0000, Donald Hunter wrote:
>> diff --git a/Documentation/bpf/map_queue_stack.rst b/Documentation/bpf/map_queue_stack.rst
>> new file mode 100644
>> index 000000000000..f20e31a647b9
>> --- /dev/null
>> +++ b/Documentation/bpf/map_queue_stack.rst
>> @@ -0,0 +1,122 @@
>> +.. SPDX-License-Identifier: GPL-2.0-only
>> +.. Copyright (C) 2022 Red Hat, Inc.
>> +
>> +=========================================
>> +BPF_MAP_TYPE_QUEUE and BPF_MAP_TYPE_STACK
>> +=========================================
>> +
>> +.. note::
>> +   - ``BPF_MAP_TYPE_QUEUE`` and ``BPF_MAP_TYPE_STACK`` were introduced
>> +     in kernel version 4.20
>> +
>> +``BPF_MAP_TYPE_QUEUE`` provides FIFO storage and ``BPF_MAP_TYPE_STACK``
>> +provides LIFO storage for BPF programs. These maps support peek, pop and
>> +push operations that are exposed to BPF programs through the respective
>> +helpers. These operations are exposed to userspace applications using
>> +the existing ``bpf`` syscall in the following way:
>> +
>> +- ``BPF_MAP_LOOKUP_ELEM`` -> peek
>> +- ``BPF_MAP_LOOKUP_AND_DELETE_ELEM`` -> pop
>> +- ``BPF_MAP_UPDATE_ELEM`` -> push
>> +
>> +``BPF_MAP_TYPE_QUEUE`` and ``BPF_MAP_TYPE_STACK`` do not support
>> +``BPF_F_NO_PREALLOC``.
>> +
>> +Usage
>> +=====
>> +
>> +Kernel BPF
>> +----------
>> +
>> +.. c:function::
>> +   long bpf_map_push_elem(struct bpf_map *map, const void *value, u64 flags)
>> +
>> +An element ``value`` can be added to a queue or stack using the
>> +``bpf_map_push_elem`` helper. The ``flags`` parameter must be set to
>> +``BPF_ANY`` or ``BPF_EXIST``. If ``flags`` is set to ``BPF_EXIST`` then,
>> +when the queue or stack is full, the oldest element will be removed to
>> +make room for ``value`` to be added. Returns ``0`` on success, or
>> +negative error in case of failure.
>> +
>> +.. c:function::
>> +   long bpf_map_peek_elem(struct bpf_map *map, void *value)
>> +
>> +This helper fetches an element ``value`` from a queue or stack without
>> +removing it. Returns ``0`` on success, or negative error in case of
>> +failure.
>> +
>> +.. c:function::
>> +   long bpf_map_pop_elem(struct bpf_map *map, void *value)
>> +
>> +This helper removes an element into ``value`` from a queue or
>> +stack. Returns ``0`` on success, or negative error in case of failure.
>> +
>> +
>> +Userspace
>> +---------
>> +
>> +.. c:function::
>> +   int bpf_map_update_elem (int fd, const void *key, const void *value, __u64 flags)
>> +
>> +A userspace program can push ``value`` onto a queue or stack using libbpf's
>> +``bpf_map_update_elem`` function. The ``key`` parameter must be set to
>> +``NULL`` and ``flags`` must be set to ``BPF_ANY`` or ``BPF_EXIST``, with the
>> +same semantics as the ``bpf_map_push_elem`` kernel helper. Returns ``0`` on
>> +success, or negative error in case of failure.
>> +
>> +.. c:function::
>> +   int bpf_map_lookup_elem (int fd, const void *key, void *value)
>> +
>> +A userspace program can peek at the ``value`` at the head of a queue or stack
>> +using the libbpf ``bpf_map_lookup_elem`` function. The ``key`` parameter must be
>> +set to ``NULL``.  Returns ``0`` on success, or negative error in case of
>> +failure.
>> +
>> +.. c:function::
>> +   int bpf_map_lookup_and_delete_elem (int fd, const void *key, void *value)
>> +
>> +A userspace program can pop a ``value`` from the head of a queue or stack using
>> +the libbpf ``bpf_map_lookup_and_delete_elem`` function. The ``key`` parameter
>> +must be set to ``NULL``. Returns ``0`` on success, or negative error in case of
>> +failure.
>> +
>> +Examples
>> +========
>> +
>> +Kernel BPF
>> +----------
>> +
>> +This snippet shows how to declare a queue in a BPF program:
>> +
>> +.. code-block:: c
>> +
>> +    struct {
>> +            __uint(type, BPF_MAP_TYPE_QUEUE);
>> +            __type(value, __u32);
>> +            __uint(max_entries, 10);
>> +    } queue SEC(".maps");
>> +
>> +
>> +Userspace
>> +---------
>> +
>> +This snippet shows how to use libbpf's low-level API to create a queue from
>> +userspace:
>> +
>> +.. code-block:: c
>> +
>> +    int create_queue()
>> +    {
>> +            return bpf_map_create(BPF_MAP_TYPE_QUEUE,
>> +                                  "sample_queue", /* name */
>> +                                  0,              /* key size, must be zero */
>> +                                  sizeof(__u32),  /* value size */
>> +                                  10,             /* max entries */
>> +                                  NULL);          /* create options */
>> +    }
>> +
>> +
>> +References
>> +==========
>> +
>> +https://lwn.net/ml/netdev/153986858555.9127.14517764371945179514.stgit@kernel/
> 
> You forgot to add the documentation to BPF toctree:
> 
> ---- >8 ----
> 
> diff --git a/Documentation/bpf/index.rst b/Documentation/bpf/index.rst
> index 1b50de1983ee2c..113872fa0193d7 100644
> --- a/Documentation/bpf/index.rst
> +++ b/Documentation/bpf/index.rst
> @@ -22,6 +22,7 @@ that goes into great technical depth about the BPF Architecture.
>      kfuncs
>      programs
>      maps
> +   map_queue_stack
>      bpf_prog_run
>      classic_vs_extended.rst
>      bpf_licensing

It will be automatically indexed in maps.rst:

...
Map Types
=========

.. toctree::
    :maxdepth: 1
    :glob:

    map_*

Usage Notes
===========
...

The visualized example:
   https://docs.kernel.org/bpf/maps.html

> 
> Thanks.
>

[e-mail] Nov. 11, 2022, 7:40 p.m. UTC | #4

Hello:

This patch was applied to bpf/bpf-next.git (master)
by Andrii Nakryiko <[e-mail]>:

On Tue,  8 Nov 2022 09:33:14 +0000 you wrote:
> Add documentation for BPF_MAP_TYPE_QUEUE and BPF_MAP_TYPE_STACK,
> including usage and examples.
> 
> Signed-off-by: Donald Hunter <[e-mail]>
> ---
> v2 -> v3:
> - Add BPF_EXIST to valid flags as reported by Yonghong Song
> - Clarify valid flags for bpf_map_push_elem
> 
> [...]

Here is the summary with links:
  - [bpf-next,v3] docs/bpf: Document BPF map types QUEUE and STACK
    https://git.kernel.org/bpf/bpf-next/c/64488ca57ab8

You are awesome, thank you!

Patch

diff --git a/Documentation/bpf/map_queue_stack.rst b/Documentation/bpf/map_queue_stack.rst
new file mode 100644
index 000000000000..f20e31a647b9
--- /dev/null
+++ b/Documentation/bpf/map_queue_stack.rst
@@ -0,0 +1,122 @@ 
+.. SPDX-License-Identifier: GPL-2.0-only
+.. Copyright (C) 2022 Red Hat, Inc.
+
+=========================================
+BPF_MAP_TYPE_QUEUE and BPF_MAP_TYPE_STACK
+=========================================
+
+.. note::
+   - ``BPF_MAP_TYPE_QUEUE`` and ``BPF_MAP_TYPE_STACK`` were introduced
+     in kernel version 4.20
+
+``BPF_MAP_TYPE_QUEUE`` provides FIFO storage and ``BPF_MAP_TYPE_STACK``
+provides LIFO storage for BPF programs. These maps support peek, pop and
+push operations that are exposed to BPF programs through the respective
+helpers. These operations are exposed to userspace applications using
+the existing ``bpf`` syscall in the following way:
+
+- ``BPF_MAP_LOOKUP_ELEM`` -> peek
+- ``BPF_MAP_LOOKUP_AND_DELETE_ELEM`` -> pop
+- ``BPF_MAP_UPDATE_ELEM`` -> push
+
+``BPF_MAP_TYPE_QUEUE`` and ``BPF_MAP_TYPE_STACK`` do not support
+``BPF_F_NO_PREALLOC``.
+
+Usage
+=====
+
+Kernel BPF
+----------
+
+.. c:function::
+   long bpf_map_push_elem(struct bpf_map *map, const void *value, u64 flags)
+
+An element ``value`` can be added to a queue or stack using the
+``bpf_map_push_elem`` helper. The ``flags`` parameter must be set to
+``BPF_ANY`` or ``BPF_EXIST``. If ``flags`` is set to ``BPF_EXIST`` then,
+when the queue or stack is full, the oldest element will be removed to
+make room for ``value`` to be added. Returns ``0`` on success, or
+negative error in case of failure.
+
+.. c:function::
+   long bpf_map_peek_elem(struct bpf_map *map, void *value)
+
+This helper fetches an element ``value`` from a queue or stack without
+removing it. Returns ``0`` on success, or negative error in case of
+failure.
+
+.. c:function::
+   long bpf_map_pop_elem(struct bpf_map *map, void *value)
+
+This helper removes an element into ``value`` from a queue or
+stack. Returns ``0`` on success, or negative error in case of failure.
+
+
+Userspace
+---------
+
+.. c:function::
+   int bpf_map_update_elem (int fd, const void *key, const void *value, __u64 flags)
+
+A userspace program can push ``value`` onto a queue or stack using libbpf's
+``bpf_map_update_elem`` function. The ``key`` parameter must be set to
+``NULL`` and ``flags`` must be set to ``BPF_ANY`` or ``BPF_EXIST``, with the
+same semantics as the ``bpf_map_push_elem`` kernel helper. Returns ``0`` on
+success, or negative error in case of failure.
+
+.. c:function::
+   int bpf_map_lookup_elem (int fd, const void *key, void *value)
+
+A userspace program can peek at the ``value`` at the head of a queue or stack
+using the libbpf ``bpf_map_lookup_elem`` function. The ``key`` parameter must be
+set to ``NULL``.  Returns ``0`` on success, or negative error in case of
+failure.
+
+.. c:function::
+   int bpf_map_lookup_and_delete_elem (int fd, const void *key, void *value)
+
+A userspace program can pop a ``value`` from the head of a queue or stack using
+the libbpf ``bpf_map_lookup_and_delete_elem`` function. The ``key`` parameter
+must be set to ``NULL``. Returns ``0`` on success, or negative error in case of
+failure.
+
+Examples
+========
+
+Kernel BPF
+----------
+
+This snippet shows how to declare a queue in a BPF program:
+
+.. code-block:: c
+
+    struct {
+            __uint(type, BPF_MAP_TYPE_QUEUE);
+            __type(value, __u32);
+            __uint(max_entries, 10);
+    } queue SEC(".maps");
+
+
+Userspace
+---------
+
+This snippet shows how to use libbpf's low-level API to create a queue from
+userspace:
+
+.. code-block:: c
+
+    int create_queue()
+    {
+            return bpf_map_create(BPF_MAP_TYPE_QUEUE,
+                                  "sample_queue", /* name */
+                                  0,              /* key size, must be zero */
+                                  sizeof(__u32),  /* value size */
+                                  10,             /* max entries */
+                                  NULL);          /* create options */
+    }
+
+
+References
+==========
+
+https://lwn.net/ml/netdev/153986858555.9127.14517764371945179514.stgit@kernel/