xref: /linux/Documentation/bpf/map_hash.rst (revision 8a922b7728a93d837954315c98b84f6b78de0c4f) 
1.. SPDX-License-Identifier: GPL-2.0-only
2.. Copyright (C) 2022 Red Hat, Inc.
3
4===============================================
5BPF_MAP_TYPE_HASH, with PERCPU and LRU Variants
6===============================================
7
8.. note::
9   - ``BPF_MAP_TYPE_HASH`` was introduced in kernel version 3.19
10   - ``BPF_MAP_TYPE_PERCPU_HASH`` was introduced in version 4.6
11   - Both ``BPF_MAP_TYPE_LRU_HASH`` and ``BPF_MAP_TYPE_LRU_PERCPU_HASH``
12     were introduced in version 4.10
13
14``BPF_MAP_TYPE_HASH`` and ``BPF_MAP_TYPE_PERCPU_HASH`` provide general
15purpose hash map storage. Both the key and the value can be structs,
16allowing for composite keys and values.
17
18The kernel is responsible for allocating and freeing key/value pairs, up
19to the max_entries limit that you specify. Hash maps use pre-allocation
20of hash table elements by default. The ``BPF_F_NO_PREALLOC`` flag can be
21used to disable pre-allocation when it is too memory expensive.
22
23``BPF_MAP_TYPE_PERCPU_HASH`` provides a separate value slot per
24CPU. The per-cpu values are stored internally in an array.
25
26The ``BPF_MAP_TYPE_LRU_HASH`` and ``BPF_MAP_TYPE_LRU_PERCPU_HASH``
27variants add LRU semantics to their respective hash tables. An LRU hash
28will automatically evict the least recently used entries when the hash
29table reaches capacity. An LRU hash maintains an internal LRU list that
30is used to select elements for eviction. This internal LRU list is
31shared across CPUs but it is possible to request a per CPU LRU list with
32the ``BPF_F_NO_COMMON_LRU`` flag when calling ``bpf_map_create``.
33
34Usage
35=====
36
37Kernel BPF
38----------
39
40bpf_map_update_elem()
41~~~~~~~~~~~~~~~~~~~~~
42
43.. code-block:: c
44
45   long bpf_map_update_elem(struct bpf_map *map, const void *key, const void *value, u64 flags)
46
47Hash entries can be added or updated using the ``bpf_map_update_elem()``
48helper. This helper replaces existing elements atomically. The ``flags``
49parameter can be used to control the update behaviour:
50
51- ``BPF_ANY`` will create a new element or update an existing element
52- ``BPF_NOEXIST`` will create a new element only if one did not already
53  exist
54- ``BPF_EXIST`` will update an existing element
55
56``bpf_map_update_elem()`` returns 0 on success, or negative error in
57case of failure.
58
59bpf_map_lookup_elem()
60~~~~~~~~~~~~~~~~~~~~~
61
62.. code-block:: c
63
64   void *bpf_map_lookup_elem(struct bpf_map *map, const void *key)
65
66Hash entries can be retrieved using the ``bpf_map_lookup_elem()``
67helper. This helper returns a pointer to the value associated with
68``key``, or ``NULL`` if no entry was found.
69
70bpf_map_delete_elem()
71~~~~~~~~~~~~~~~~~~~~~
72
73.. code-block:: c
74
75   long bpf_map_delete_elem(struct bpf_map *map, const void *key)
76
77Hash entries can be deleted using the ``bpf_map_delete_elem()``
78helper. This helper will return 0 on success, or negative error in case
79of failure.
80
81Per CPU Hashes
82--------------
83
84For ``BPF_MAP_TYPE_PERCPU_HASH`` and ``BPF_MAP_TYPE_LRU_PERCPU_HASH``
85the ``bpf_map_update_elem()`` and ``bpf_map_lookup_elem()`` helpers
86automatically access the hash slot for the current CPU.
87
88bpf_map_lookup_percpu_elem()
89~~~~~~~~~~~~~~~~~~~~~~~~~~~~
90
91.. code-block:: c
92
93   void *bpf_map_lookup_percpu_elem(struct bpf_map *map, const void *key, u32 cpu)
94
95The ``bpf_map_lookup_percpu_elem()`` helper can be used to lookup the
96value in the hash slot for a specific CPU. Returns value associated with
97``key`` on ``cpu`` , or ``NULL`` if no entry was found or ``cpu`` is
98invalid.
99
100Concurrency
101-----------
102
103Values stored in ``BPF_MAP_TYPE_HASH`` can be accessed concurrently by
104programs running on different CPUs.  Since Kernel version 5.1, the BPF
105infrastructure provides ``struct bpf_spin_lock`` to synchronise access.
106See ``tools/testing/selftests/bpf/progs/test_spin_lock.c``.
107
108Userspace
109---------
110
111bpf_map_get_next_key()
112~~~~~~~~~~~~~~~~~~~~~~
113
114.. code-block:: c
115
116   int bpf_map_get_next_key(int fd, const void *cur_key, void *next_key)
117
118In userspace, it is possible to iterate through the keys of a hash using
119libbpf's ``bpf_map_get_next_key()`` function. The first key can be fetched by
120calling ``bpf_map_get_next_key()`` with ``cur_key`` set to
121``NULL``. Subsequent calls will fetch the next key that follows the
122current key. ``bpf_map_get_next_key()`` returns 0 on success, -ENOENT if
123cur_key is the last key in the hash, or negative error in case of
124failure.
125
126Note that if ``cur_key`` gets deleted then ``bpf_map_get_next_key()``
127will instead return the *first* key in the hash table which is
128undesirable. It is recommended to use batched lookup if there is going
129to be key deletion intermixed with ``bpf_map_get_next_key()``.
130
131Examples
132========
133
134Please see the ``tools/testing/selftests/bpf`` directory for functional
135examples.  The code snippets below demonstrates API usage.
136
137This example shows how to declare an LRU Hash with a struct key and a
138struct value.
139
140.. code-block:: c
141
142    #include <linux/bpf.h>
143    #include <bpf/bpf_helpers.h>
144
145    struct key {
146        __u32 srcip;
147    };
148
149    struct value {
150        __u64 packets;
151        __u64 bytes;
152    };
153
154    struct {
155            __uint(type, BPF_MAP_TYPE_LRU_HASH);
156            __uint(max_entries, 32);
157            __type(key, struct key);
158            __type(value, struct value);
159    } packet_stats SEC(".maps");
160
161This example shows how to create or update hash values using atomic
162instructions:
163
164.. code-block:: c
165
166    static void update_stats(__u32 srcip, int bytes)
167    {
168            struct key key = {
169                    .srcip = srcip,
170            };
171            struct value *value = bpf_map_lookup_elem(&packet_stats, &key);
172
173            if (value) {
174                    __sync_fetch_and_add(&value->packets, 1);
175                    __sync_fetch_and_add(&value->bytes, bytes);
176            } else {
177                    struct value newval = { 1, bytes };
178
179                    bpf_map_update_elem(&packet_stats, &key, &newval, BPF_NOEXIST);
180            }
181    }
182
183Userspace walking the map elements from the map declared above:
184
185.. code-block:: c
186
187    #include <bpf/libbpf.h>
188    #include <bpf/bpf.h>
189
190    static void walk_hash_elements(int map_fd)
191    {
192            struct key *cur_key = NULL;
193            struct key next_key;
194            struct value value;
195            int err;
196
197            for (;;) {
198                    err = bpf_map_get_next_key(map_fd, cur_key, &next_key);
199                    if (err)
200                            break;
201
202                    bpf_map_lookup_elem(map_fd, &next_key, &value);
203
204                    // Use key and value here
205
206                    cur_key = &next_key;
207            }
208    }
209