Skip to contentSkip to conversation

docs/bpf: document BPF ARRAY_OF_MAPS and HASH_OF_MAPS

PATCH Superseded Donald Hunter 2 participants 4 messages Nov 7, 2022 – Nov 8, 2022

Subsystems (2)

v3 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

PATCH v3 1/1 docs/bpf: document BPF ARRAY_OF_MAPS and HASH_OF_MAPS

Add documentation for the ARRAY_OF_MAPS and HASH_OF_MAPS map types, including usage and examples.

---
v2 -> v3:
- Update BPF example to show declarative initialisation, as suggested by Andrii Nakryiko
- Use LIBBPF_OPTS inline initialisation, as suggested by Andrii Nakryiko
- Fix duplicate label warning,

v1 -> v2:
- Fix formatting nits
- Tidy up code snippets as suggested by Maryam Tahhan

---
 Documentation/bpf/map_of_maps.rst | 126 ++++++++++++++++++++++++++++++
 1 file changed, 126 insertions(+)
 create mode 100644 Documentation/bpf/map_of_maps.rst
Documentation/bpf/map_of_maps.rst new file +126 -0
new file mode 100644
index 000000000000..63e41b06a91d
@@ -0,0 +1,126 @@
+.. SPDX-License-Identifier: GPL-2.0-only
+.. Copyright (C) 2022 Red Hat, Inc.
+
+========================================================
+BPF_MAP_TYPE_ARRAY_OF_MAPS and BPF_MAP_TYPE_HASH_OF_MAPS
+========================================================
+
+.. note::
+   - ``BPF_MAP_TYPE_ARRAY_OF_MAPS`` and ``BPF_MAP_TYPE_HASH_OF_MAPS`` were
+     introduced in kernel version 4.12
+
+``BPF_MAP_TYPE_ARRAY_OF_MAPS`` and ``BPF_MAP_TYPE_HASH_OF_MAPS`` provide general
+purpose support for map in map storage. One level of nesting is supported, where
+an outer map contains instances of a single type of inner map, for example
+``array_of_maps->sock_map``.
+
+When creating an outer map, an inner map instance is used to initialize the
+metadata that the outer map holds about its inner maps. This inner map has a
+separate lifetime from the outer map and can be deleted after the outer map has
+been created.
+
+The outer map supports element update and delete from user space using the
+syscall API. A BPF program is only allowed to do element lookup in the outer
+map.
+
+.. note::
+   - Multi-level nesting is not supported.
+   - Any BPF map type can be used as an inner map, except for
+     ``BPF_MAP_TYPE_PROG_ARRAY``.
+   - A BPF program cannot update or delete outer map entries.
+
+For ``BPF_MAP_TYPE_ARRAY_OF_MAPS`` the key is an unsigned 32-bit integer index
+into the array. The array is a fixed size with ``max_entries`` elements that are
+zero initialized when created.
+
+For ``BPF_MAP_TYPE_HASH_OF_MAPS`` the key type can be chosen when defining the
+map. The kernel is responsible for allocating and freeing key/value pairs, up to
+the max_entries limit that you specify. Hash maps use pre-allocation of hash
+table elements by default. The ``BPF_F_NO_PREALLOC`` flag can be used to disable
+pre-allocation when it is too memory expensive.
+
+Usage
+=====
+
+Kernel BPF Helper
+-----------------
+
+.. c:function::
+   void *bpf_map_lookup_elem(struct bpf_map *map, const void *key)
+
+Inner maps can be retrieved using the ``bpf_map_lookup_elem()`` helper. This
+helper returns a pointer to the inner map, or ``NULL`` if no entry was found.
+
+Examples
+========
+
+Kernel BPF Example
+------------------
+
+This snippet shows how to create and initialise an array of devmaps in a BPF
+program. Note that the outer array can only be modified from user space using
+the syscall API.
+
+.. code-block:: c
+
+    struct inner_map {
+            __uint(type, BPF_MAP_TYPE_DEVMAP);
+            __uint(max_entries, 10);
+            __type(key, __u32);
+            __type(value, __u32);
+    } inner_map1 SEC(".maps"), inner_map2 SEC(".maps");
+
+    struct {
+            __uint(type, BPF_MAP_TYPE_ARRAY_OF_MAPS);
+            __uint(max_entries, 2);
+            __type(key, __u32);
+            __array(values, struct inner_map);
+    } outer_map SEC(".maps") = {
+            .values = { &inner_map1,
+                        &inner_map2 }
+    };
+
+See ``progs/test_bpf_map_in_map.c`` in ``tools/testing/selftests/bpf`` for more
+examples of declarative initialisation of outer maps.
+
+User Space
+----------
+
+This snippet shows how to create an array based outer map:
+
+.. code-block:: c
+
+    int create_outer_array(int inner_fd) {
+            int fd;
+
+            LIBBPF_OPTS(bpf_map_create_opts, opts, .inner_map_fd = inner_fd);
+            fd = bpf_map_create(BPF_MAP_TYPE_ARRAY_OF_MAPS,
+                                "example_array",       /* name */
+                                sizeof(__u32),         /* key size */
+                                sizeof(__u32),         /* value size */
+                                256,                   /* max entries */
+                                &opts);                /* create opts */
+            return fd;
+    }
+
+
+This snippet shows how to add an inner map to an outer map:
+
+.. code-block:: c
+
+    int add_devmap(int outer_fd, int index, const char *name) {
+            int fd;
+
+            fd = bpf_map_create(BPF_MAP_TYPE_DEVMAP, name,
+                                sizeof(__u32), sizeof(__u32), 256, NULL);
+            if (fd < 0)
+                    return fd;
+
+            return bpf_map_update_elem(outer_fd, &index, &fd, BPF_ANY);
+    }
+
+References
+==========
+
+- https://lore.kernel.org/netdev/[email protected]/
+- https://lore.kernel.org/netdev/[email protected]/
Signature · 1 line
2.35.1
#1 lore raw
Quoted 41 lines · Donald Hunter

Add documentation for the ARRAY_OF_MAPS and HASH_OF_MAPS map types, including usage and examples.

---
v2 -> v3:
- Update BPF example to show declarative initialisation, as suggested by Andrii Nakryiko
- Use LIBBPF_OPTS inline initialisation, as suggested by Andrii Nakryiko
- Fix duplicate label warning,

v1 -> v2:
- Fix formatting nits
- Tidy up code snippets as suggested by Maryam Tahhan

---
  Documentation/bpf/map_of_maps.rst | 126 ++++++++++++++++++++++++++++++
  1 file changed, 126 insertions(+)

create mode 100644 Documentation/bpf/map_of_maps.rst

Documentation/bpf/map_of_maps.rst new file +14 -0
new file mode 100644
index 000000000000..63e41b06a91d
@@ -0,0 +1,126 @@
+.. SPDX-License-Identifier: GPL-2.0-only
+.. Copyright (C) 2022 Red Hat, Inc.
+
+========================================================
+BPF_MAP_TYPE_ARRAY_OF_MAPS and BPF_MAP_TYPE_HASH_OF_MAPS
+========================================================
+
+.. note::
+   - ``BPF_MAP_TYPE_ARRAY_OF_MAPS`` and ``BPF_MAP_TYPE_HASH_OF_MAPS`` were
+     introduced in kernel version 4.12
+
+``BPF_MAP_TYPE_ARRAY_OF_MAPS`` and ``BPF_MAP_TYPE_HASH_OF_MAPS`` provide general
+purpose support for map in map storage. One level of nesting is supported, where
+an outer map contains instances of a single type of inner map, for example

Documentation/bpf/map_of_maps.rst line 24

Quoted 10 lines
Documentation/bpf/map_of_maps.rst new file +10 -0
+``array_of_maps->sock_map``.
+
+When creating an outer map, an inner map instance is used to initialize the
+metadata that the outer map holds about its inner maps. This inner map has a
+separate lifetime from the outer map and can be deleted after the outer map has
+been created.
+
+The outer map supports element update and delete from user space using the
+syscall API. A BPF program is only allowed to do element lookup in the outer
+map.

The outer map supports element lookup, update and delete from user space using the syscall API.

A BPF program can do element delete for array/hash_of_maps. Please double check.

Documentation/bpf/map_of_maps.rst line 30

Quoted 6 lines
Documentation/bpf/map_of_maps.rst new file +6 -0
+
+.. note::
+   - Multi-level nesting is not supported.
+   - Any BPF map type can be used as an inner map, except for
+     ``BPF_MAP_TYPE_PROG_ARRAY``.
+   - A BPF program cannot update or delete outer map entries.

A BPF program cannot update outer map entries.

Quoted 12 lines
Documentation/bpf/map_of_maps.rst new file +12 -0
+
+For ``BPF_MAP_TYPE_ARRAY_OF_MAPS`` the key is an unsigned 32-bit integer index
+into the array. The array is a fixed size with ``max_entries`` elements that are
+zero initialized when created.
+
+For ``BPF_MAP_TYPE_HASH_OF_MAPS`` the key type can be chosen when defining the
+map. The kernel is responsible for allocating and freeing key/value pairs, up to
+the max_entries limit that you specify. Hash maps use pre-allocation of hash
+table elements by default. The ``BPF_F_NO_PREALLOC`` flag can be used to disable
+pre-allocation when it is too memory expensive.
+
+Usage

Documentation/bpf/map_of_maps.rst line 52

Quoted 10 lines
Documentation/bpf/map_of_maps.rst new file +10 -0
+=====
+
+Kernel BPF Helper
+-----------------
+
+.. c:function::
+   void *bpf_map_lookup_elem(struct bpf_map *map, const void *key)
+
+Inner maps can be retrieved using the ``bpf_map_lookup_elem()`` helper. This
+helper returns a pointer to the inner map, or ``NULL`` if no entry was found.

bpf_map_delete_elem?

Quoted 21 lines
Documentation/bpf/map_of_maps.rst new file +21 -0
+
+Examples
+========
+
+Kernel BPF Example
+------------------
+
+This snippet shows how to create and initialise an array of devmaps in a BPF
+program. Note that the outer array can only be modified from user space using
+the syscall API.
+
+.. code-block:: c
+
+    struct inner_map {
+            __uint(type, BPF_MAP_TYPE_DEVMAP);
+            __uint(max_entries, 10);
+            __type(key, __u32);
+            __type(value, __u32);
+    } inner_map1 SEC(".maps"), inner_map2 SEC(".maps");
+
+    struct {

Documentation/bpf/map_of_maps.rst line 83

Quoted 10 lines
Documentation/bpf/map_of_maps.rst new file +10 -0
+            __uint(type, BPF_MAP_TYPE_ARRAY_OF_MAPS);
+            __uint(max_entries, 2);
+            __type(key, __u32);
+            __array(values, struct inner_map);
+    } outer_map SEC(".maps") = {
+            .values = { &inner_map1,
+                        &inner_map2 }
+    };
+
+See ``progs/test_bpf_map_in_map.c`` in ``tools/testing/selftests/bpf`` for more

The file name test_bpf_map_in_map.c` does not exist.

Documentation/bpf/map_of_maps.rst line 96

Quoted 13 lines
Documentation/bpf/map_of_maps.rst new file +13 -0
+examples of declarative initialisation of outer maps.
+
+User Space
+----------
+
+This snippet shows how to create an array based outer map:
+
+.. code-block:: c
+
+    int create_outer_array(int inner_fd) {
+            int fd;
+
+            LIBBPF_OPTS(bpf_map_create_opts, opts, .inner_map_fd = inner_fd);

This is declaration. Please put it adjacent to 'int fd'.

Quoted 30 lines
Documentation/bpf/map_of_maps.rst new file +30 -0
+            fd = bpf_map_create(BPF_MAP_TYPE_ARRAY_OF_MAPS,
+                                "example_array",       /* name */
+                                sizeof(__u32),         /* key size */
+                                sizeof(__u32),         /* value size */
+                                256,                   /* max entries */
+                                &opts);                /* create opts */
+            return fd;
+    }
+
+
+This snippet shows how to add an inner map to an outer map:
+
+.. code-block:: c
+
+    int add_devmap(int outer_fd, int index, const char *name) {
+            int fd;
+
+            fd = bpf_map_create(BPF_MAP_TYPE_DEVMAP, name,
+                                sizeof(__u32), sizeof(__u32), 256, NULL);
+            if (fd < 0)
+                    return fd;
+
+            return bpf_map_update_elem(outer_fd, &index, &fd, BPF_ANY);
+    }
+
+References
+==========
+
+- https://lore.kernel.org/netdev/[email protected]/
+- https://lore.kernel.org/netdev/[email protected]/
#2 lore raw
Quoted 66 lines · Yonghong Song
Quoted 56 lines · Donald Hunter

Add documentation for the ARRAY_OF_MAPS and HASH_OF_MAPS map types, including usage and examples.

---
v2 -> v3:
- Update BPF example to show declarative initialisation, as suggested by Andrii Nakryiko
- Use LIBBPF_OPTS inline initialisation, as suggested by Andrii Nakryiko
- Fix duplicate label warning,

v1 -> v2:
- Fix formatting nits
- Tidy up code snippets as suggested by Maryam Tahhan
---
  Documentation/bpf/map_of_maps.rst | 126 ++++++++++++++++++++++++++++++

  1 file changed, 126 insertions(+)

  create mode 100644 Documentation/bpf/map_of_maps.rst

Documentation/bpf/map_of_maps.rst new file +9 -0
new file mode 100644
index 000000000000..63e41b06a91d
@@ -0,0 +1,126 @@
+.. SPDX-License-Identifier: GPL-2.0-only
+.. Copyright (C) 2022 Red Hat, Inc.
+
+========================================================
+BPF_MAP_TYPE_ARRAY_OF_MAPS and BPF_MAP_TYPE_HASH_OF_MAPS
+========================================================
+
+.. note::
+   - ``BPF_MAP_TYPE_ARRAY_OF_MAPS`` and ``BPF_MAP_TYPE_HASH_OF_MAPS`` 

were
+     introduced in kernel version 4.12
+
+``BPF_MAP_TYPE_ARRAY_OF_MAPS`` and ``BPF_MAP_TYPE_HASH_OF_MAPS`` provide general
+purpose support for map in map storage. One level of nesting is supported, where
+an outer map contains instances of a single type of inner map, for example
+``array_of_maps->sock_map``.

Documentation/bpf/map_of_maps.rst new file +2 -0
+
+When creating an outer map, an inner map instance is used to 

initialize the
+metadata that the outer map holds about its inner maps. This inner map has a
+separate lifetime from the outer map and can be deleted after the outer map has

Documentation/bpf/map_of_maps.rst new file +3 -0
+been created.
+
+The outer map supports element update and delete from user space 
Quoted 4 lines

using the
+syscall API. A BPF program is only allowed to do element lookup in the outer
+map.

The outer map supports element lookup, update and delete from user space using the syscall API.

Quoted 1 line

A BPF program can do element delete for array/hash_of_maps. Please double check.

Okay, I double checked with verifier.c. You are right, only lookup is supported for bpf programs.

Quoted 9 lines
Quoted 7 lines

+
+.. note::
+   - Multi-level nesting is not supported.
+   - Any BPF map type can be used as an inner map, except for +     ``BPF_MAP_TYPE_PROG_ARRAY``.
+   - A BPF program cannot update or delete outer map entries.

A BPF program cannot update outer map entries.

Yes, only lookup is allowed for bpf programs.

Quoted 25 lines
Quoted 25 lines
Documentation/bpf/map_of_maps.rst new file +2 -0
+
+For ``BPF_MAP_TYPE_ARRAY_OF_MAPS`` the key is an unsigned 32-bit 

integer index
+into the array. The array is a fixed size with ``max_entries`` elements that are

Documentation/bpf/map_of_maps.rst new file +3 -0
+zero initialized when created.
+
+For ``BPF_MAP_TYPE_HASH_OF_MAPS`` the key type can be chosen when 

defining the
+map. The kernel is responsible for allocating and freeing key/value pairs, up to
+the max_entries limit that you specify. Hash maps use pre-allocation of hash
+table elements by default. The ``BPF_F_NO_PREALLOC`` flag can be used to disable

Documentation/bpf/map_of_maps.rst new file +9 -0
+pre-allocation when it is too memory expensive.
+
+Usage
+=====
+
+Kernel BPF Helper
+-----------------
+
+.. c:function::
Quoted 8 lines
Quoted 6 lines

+   void *bpf_map_lookup_elem(struct bpf_map *map, const void *key)

Documentation/bpf/map_of_maps.rst new file +2 -0
+
+Inner maps can be retrieved using the ``bpf_map_lookup_elem()`` 

helper. This
+helper returns a pointer to the inner map, or ``NULL`` if no entry was found.

bpf_map_delete_elem?

same here. bpf_map_delete_elem is not available for bpf programs.

Quoted 86 lines
Quoted 34 lines
Documentation/bpf/map_of_maps.rst new file +8 -0
+
+Examples
+========
+
+Kernel BPF Example
+------------------
+
+This snippet shows how to create and initialise an array of devmaps 

in a BPF
+program. Note that the outer array can only be modified from user space using

Documentation/bpf/map_of_maps.rst new file +22 -0
+the syscall API.
+
+.. code-block:: c
+
+    struct inner_map {
+            __uint(type, BPF_MAP_TYPE_DEVMAP);
+            __uint(max_entries, 10);
+            __type(key, __u32);
+            __type(value, __u32);
+    } inner_map1 SEC(".maps"), inner_map2 SEC(".maps");
+
+    struct {
+            __uint(type, BPF_MAP_TYPE_ARRAY_OF_MAPS);
+            __uint(max_entries, 2);
+            __type(key, __u32);
+            __array(values, struct inner_map);
+    } outer_map SEC(".maps") = {
+            .values = { &inner_map1,
+                        &inner_map2 }
+    };
+
+See ``progs/test_bpf_map_in_map.c`` in 
Quoted 1 line

``tools/testing/selftests/bpf`` for more

The file name test_bpf_map_in_map.c` does not exist.

Quoted 13 lines
Documentation/bpf/map_of_maps.rst new file +13 -0
+examples of declarative initialisation of outer maps.
+
+User Space
+----------
+
+This snippet shows how to create an array based outer map:
+
+.. code-block:: c
+
+    int create_outer_array(int inner_fd) {
+            int fd;
+
+            LIBBPF_OPTS(bpf_map_create_opts, opts, .inner_map_fd = 
Quoted 1 line

inner_fd);

This is declaration. Please put it adjacent to 'int fd'.

Quoted 31 lines

+            fd = bpf_map_create(BPF_MAP_TYPE_ARRAY_OF_MAPS, +                                "example_array",       /* name */ +                                sizeof(__u32),         /* key size */ +                                sizeof(__u32),         /* value size */ +                                256,                   /* max entries */ +                                &opts);                /* create opts */ +            return fd;
+    }

Documentation/bpf/map_of_maps.rst new file +11 -0
+
+
+This snippet shows how to add an inner map to an outer map:
+
+.. code-block:: c
+
+    int add_devmap(int outer_fd, int index, const char *name) {
+            int fd;
+
+            fd = bpf_map_create(BPF_MAP_TYPE_DEVMAP, name,
+                                sizeof(__u32), sizeof(__u32), 256, 

NULL);
+            if (fd < 0)
+                    return fd;

Documentation/bpf/map_of_maps.rst new file +9 -0
+
+            return bpf_map_update_elem(outer_fd, &index, &fd, BPF_ANY);
+    }
+
+References
+==========
+
+- https://lore.kernel.org/netdev/[email protected]/
+- https://lore.kernel.org/netdev/[email protected]/
#3 lore raw
Quoted 10 lines · Yonghong Song
Quoted 8 lines · Yonghong Song

Documentation/bpf/map_of_maps.rst line 24

Quoted 4 lines · Donald Hunter
Documentation/bpf/map_of_maps.rst new file +4 -0
+
+The outer map supports element update and delete from user space using the
+syscall API. A BPF program is only allowed to do element lookup in the outer
+map.

The outer map supports element lookup, update and delete from user space using the syscall API.
A BPF program can do element delete for array/hash_of_maps. Please double check.

Quoted 2 lines

Okay, I double checked with verifier.c. You are right, only lookup is supported for bpf programs.

Thanks for checking. I do refer to verifier.c to see what helpers are supported. I will add lookup for userspace.

Quoted 3 lines
Quoted 3 lines

Review

Quoted 2 lines
(quoted diff) +2 -0
+
+See ``progs/test_bpf_map_in_map.c`` in ``tools/testing/selftests/bpf`` for more

The file name test_bpf_map_in_map.c` does not exist.

Good catch, that's an unfortunate typo. It should be test_btf_map_in_map.c

Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
Documentation/bpf/map_of_maps.rst new file +6 -0
+examples of declarative initialisation of outer maps.
+
+User Space
+----------
+
+This snippet shows how to create an array based outer map:
Quoted 8 lines
Quoted 8 lines

Documentation/bpf/map_of_maps.rst line 96

Quoted 7 lines
Documentation/bpf/map_of_maps.rst new file +7 -0
+
+.. code-block:: c
+
+    int create_outer_array(int inner_fd) {
+            int fd;
+
+            LIBBPF_OPTS(bpf_map_create_opts, opts, .inner_map_fd = inner_fd);

This is declaration. Please put it adjacent to 'int fd'.

Will do. Looking at code in testing/selftests/bpf it seems the preferred style is to put it above 'int fd;' ?