1 .. SPDX-License-Identifier: GPL-2.0-only 1 .. SPDX-License-Identifier: GPL-2.0-only
2 .. Copyright (C) 2022 Red Hat, Inc. 2 .. Copyright (C) 2022 Red Hat, Inc.
3 .. Copyright (C) 2022-2023 Isovalent, Inc. <<
4 3
5 ============================================== 4 ===============================================
6 BPF_MAP_TYPE_HASH, with PERCPU and LRU Variant 5 BPF_MAP_TYPE_HASH, with PERCPU and LRU Variants
7 ============================================== 6 ===============================================
8 7
9 .. note:: 8 .. note::
10 - ``BPF_MAP_TYPE_HASH`` was introduced in k 9 - ``BPF_MAP_TYPE_HASH`` was introduced in kernel version 3.19
11 - ``BPF_MAP_TYPE_PERCPU_HASH`` was introduc 10 - ``BPF_MAP_TYPE_PERCPU_HASH`` was introduced in version 4.6
12 - Both ``BPF_MAP_TYPE_LRU_HASH`` and ``BPF_ 11 - Both ``BPF_MAP_TYPE_LRU_HASH`` and ``BPF_MAP_TYPE_LRU_PERCPU_HASH``
13 were introduced in version 4.10 12 were introduced in version 4.10
14 13
15 ``BPF_MAP_TYPE_HASH`` and ``BPF_MAP_TYPE_PERCP 14 ``BPF_MAP_TYPE_HASH`` and ``BPF_MAP_TYPE_PERCPU_HASH`` provide general
16 purpose hash map storage. Both the key and the 15 purpose hash map storage. Both the key and the value can be structs,
17 allowing for composite keys and values. 16 allowing for composite keys and values.
18 17
19 The kernel is responsible for allocating and f 18 The kernel is responsible for allocating and freeing key/value pairs, up
20 to the max_entries limit that you specify. Has 19 to the max_entries limit that you specify. Hash maps use pre-allocation
21 of hash table elements by default. The ``BPF_F 20 of hash table elements by default. The ``BPF_F_NO_PREALLOC`` flag can be
22 used to disable pre-allocation when it is too 21 used to disable pre-allocation when it is too memory expensive.
23 22
24 ``BPF_MAP_TYPE_PERCPU_HASH`` provides a separa 23 ``BPF_MAP_TYPE_PERCPU_HASH`` provides a separate value slot per
25 CPU. The per-cpu values are stored internally 24 CPU. The per-cpu values are stored internally in an array.
26 25
27 The ``BPF_MAP_TYPE_LRU_HASH`` and ``BPF_MAP_TY 26 The ``BPF_MAP_TYPE_LRU_HASH`` and ``BPF_MAP_TYPE_LRU_PERCPU_HASH``
28 variants add LRU semantics to their respective 27 variants add LRU semantics to their respective hash tables. An LRU hash
29 will automatically evict the least recently us 28 will automatically evict the least recently used entries when the hash
30 table reaches capacity. An LRU hash maintains 29 table reaches capacity. An LRU hash maintains an internal LRU list that
31 is used to select elements for eviction. This 30 is used to select elements for eviction. This internal LRU list is
32 shared across CPUs but it is possible to reque 31 shared across CPUs but it is possible to request a per CPU LRU list with
33 the ``BPF_F_NO_COMMON_LRU`` flag when calling !! 32 the ``BPF_F_NO_COMMON_LRU`` flag when calling ``bpf_map_create``.
34 following table outlines the properties of LRU <<
35 map type and the flags used to create the map. <<
36 <<
37 ======================== ===================== <<
38 Flag ``BPF_MAP_TYPE_LRU_HA <<
39 ======================== ===================== <<
40 **BPF_F_NO_COMMON_LRU** Per-CPU LRU, global m <<
41 **!BPF_F_NO_COMMON_LRU** Global LRU, global ma <<
42 ======================== ===================== <<
43 33
44 Usage 34 Usage
45 ===== 35 =====
46 36
47 Kernel BPF 37 Kernel BPF
48 ---------- 38 ----------
49 39
50 bpf_map_update_elem() 40 bpf_map_update_elem()
51 ~~~~~~~~~~~~~~~~~~~~~ 41 ~~~~~~~~~~~~~~~~~~~~~
52 42
53 .. code-block:: c 43 .. code-block:: c
54 44
55 long bpf_map_update_elem(struct bpf_map *ma 45 long bpf_map_update_elem(struct bpf_map *map, const void *key, const void *value, u64 flags)
56 46
57 Hash entries can be added or updated using the 47 Hash entries can be added or updated using the ``bpf_map_update_elem()``
58 helper. This helper replaces existing elements 48 helper. This helper replaces existing elements atomically. The ``flags``
59 parameter can be used to control the update be 49 parameter can be used to control the update behaviour:
60 50
61 - ``BPF_ANY`` will create a new element or upd 51 - ``BPF_ANY`` will create a new element or update an existing element
62 - ``BPF_NOEXIST`` will create a new element on 52 - ``BPF_NOEXIST`` will create a new element only if one did not already
63 exist 53 exist
64 - ``BPF_EXIST`` will update an existing elemen 54 - ``BPF_EXIST`` will update an existing element
65 55
66 ``bpf_map_update_elem()`` returns 0 on success 56 ``bpf_map_update_elem()`` returns 0 on success, or negative error in
67 case of failure. 57 case of failure.
68 58
69 bpf_map_lookup_elem() 59 bpf_map_lookup_elem()
70 ~~~~~~~~~~~~~~~~~~~~~ 60 ~~~~~~~~~~~~~~~~~~~~~
71 61
72 .. code-block:: c 62 .. code-block:: c
73 63
74 void *bpf_map_lookup_elem(struct bpf_map *m 64 void *bpf_map_lookup_elem(struct bpf_map *map, const void *key)
75 65
76 Hash entries can be retrieved using the ``bpf_ 66 Hash entries can be retrieved using the ``bpf_map_lookup_elem()``
77 helper. This helper returns a pointer to the v 67 helper. This helper returns a pointer to the value associated with
78 ``key``, or ``NULL`` if no entry was found. 68 ``key``, or ``NULL`` if no entry was found.
79 69
80 bpf_map_delete_elem() 70 bpf_map_delete_elem()
81 ~~~~~~~~~~~~~~~~~~~~~ 71 ~~~~~~~~~~~~~~~~~~~~~
82 72
83 .. code-block:: c 73 .. code-block:: c
84 74
85 long bpf_map_delete_elem(struct bpf_map *ma 75 long bpf_map_delete_elem(struct bpf_map *map, const void *key)
86 76
87 Hash entries can be deleted using the ``bpf_ma 77 Hash entries can be deleted using the ``bpf_map_delete_elem()``
88 helper. This helper will return 0 on success, 78 helper. This helper will return 0 on success, or negative error in case
89 of failure. 79 of failure.
90 80
91 Per CPU Hashes 81 Per CPU Hashes
92 -------------- 82 --------------
93 83
94 For ``BPF_MAP_TYPE_PERCPU_HASH`` and ``BPF_MAP 84 For ``BPF_MAP_TYPE_PERCPU_HASH`` and ``BPF_MAP_TYPE_LRU_PERCPU_HASH``
95 the ``bpf_map_update_elem()`` and ``bpf_map_lo 85 the ``bpf_map_update_elem()`` and ``bpf_map_lookup_elem()`` helpers
96 automatically access the hash slot for the cur 86 automatically access the hash slot for the current CPU.
97 87
98 bpf_map_lookup_percpu_elem() 88 bpf_map_lookup_percpu_elem()
99 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 89 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
100 90
101 .. code-block:: c 91 .. code-block:: c
102 92
103 void *bpf_map_lookup_percpu_elem(struct bpf 93 void *bpf_map_lookup_percpu_elem(struct bpf_map *map, const void *key, u32 cpu)
104 94
105 The ``bpf_map_lookup_percpu_elem()`` helper ca 95 The ``bpf_map_lookup_percpu_elem()`` helper can be used to lookup the
106 value in the hash slot for a specific CPU. Ret 96 value in the hash slot for a specific CPU. Returns value associated with
107 ``key`` on ``cpu`` , or ``NULL`` if no entry w 97 ``key`` on ``cpu`` , or ``NULL`` if no entry was found or ``cpu`` is
108 invalid. 98 invalid.
109 99
110 Concurrency 100 Concurrency
111 ----------- 101 -----------
112 102
113 Values stored in ``BPF_MAP_TYPE_HASH`` can be 103 Values stored in ``BPF_MAP_TYPE_HASH`` can be accessed concurrently by
114 programs running on different CPUs. Since Ker 104 programs running on different CPUs. Since Kernel version 5.1, the BPF
115 infrastructure provides ``struct bpf_spin_lock 105 infrastructure provides ``struct bpf_spin_lock`` to synchronise access.
116 See ``tools/testing/selftests/bpf/progs/test_s 106 See ``tools/testing/selftests/bpf/progs/test_spin_lock.c``.
117 107
118 Userspace 108 Userspace
119 --------- 109 ---------
120 110
121 bpf_map_get_next_key() 111 bpf_map_get_next_key()
122 ~~~~~~~~~~~~~~~~~~~~~~ 112 ~~~~~~~~~~~~~~~~~~~~~~
123 113
124 .. code-block:: c 114 .. code-block:: c
125 115
126 int bpf_map_get_next_key(int fd, const void 116 int bpf_map_get_next_key(int fd, const void *cur_key, void *next_key)
127 117
128 In userspace, it is possible to iterate throug 118 In userspace, it is possible to iterate through the keys of a hash using
129 libbpf's ``bpf_map_get_next_key()`` function. 119 libbpf's ``bpf_map_get_next_key()`` function. The first key can be fetched by
130 calling ``bpf_map_get_next_key()`` with ``cur_ 120 calling ``bpf_map_get_next_key()`` with ``cur_key`` set to
131 ``NULL``. Subsequent calls will fetch the next 121 ``NULL``. Subsequent calls will fetch the next key that follows the
132 current key. ``bpf_map_get_next_key()`` return 122 current key. ``bpf_map_get_next_key()`` returns 0 on success, -ENOENT if
133 cur_key is the last key in the hash, or negati 123 cur_key is the last key in the hash, or negative error in case of
134 failure. 124 failure.
135 125
136 Note that if ``cur_key`` gets deleted then ``b 126 Note that if ``cur_key`` gets deleted then ``bpf_map_get_next_key()``
137 will instead return the *first* key in the has 127 will instead return the *first* key in the hash table which is
138 undesirable. It is recommended to use batched 128 undesirable. It is recommended to use batched lookup if there is going
139 to be key deletion intermixed with ``bpf_map_g 129 to be key deletion intermixed with ``bpf_map_get_next_key()``.
140 130
141 Examples 131 Examples
142 ======== 132 ========
143 133
144 Please see the ``tools/testing/selftests/bpf`` 134 Please see the ``tools/testing/selftests/bpf`` directory for functional
145 examples. The code snippets below demonstrate 135 examples. The code snippets below demonstrates API usage.
146 136
147 This example shows how to declare an LRU Hash 137 This example shows how to declare an LRU Hash with a struct key and a
148 struct value. 138 struct value.
149 139
150 .. code-block:: c 140 .. code-block:: c
151 141
152 #include <linux/bpf.h> 142 #include <linux/bpf.h>
153 #include <bpf/bpf_helpers.h> 143 #include <bpf/bpf_helpers.h>
154 144
155 struct key { 145 struct key {
156 __u32 srcip; 146 __u32 srcip;
157 }; 147 };
158 148
159 struct value { 149 struct value {
160 __u64 packets; 150 __u64 packets;
161 __u64 bytes; 151 __u64 bytes;
162 }; 152 };
163 153
164 struct { 154 struct {
165 __uint(type, BPF_MAP_TYPE_LRU_HASH 155 __uint(type, BPF_MAP_TYPE_LRU_HASH);
166 __uint(max_entries, 32); 156 __uint(max_entries, 32);
167 __type(key, struct key); 157 __type(key, struct key);
168 __type(value, struct value); 158 __type(value, struct value);
169 } packet_stats SEC(".maps"); 159 } packet_stats SEC(".maps");
170 160
171 This example shows how to create or update has 161 This example shows how to create or update hash values using atomic
172 instructions: 162 instructions:
173 163
174 .. code-block:: c 164 .. code-block:: c
175 165
176 static void update_stats(__u32 srcip, int 166 static void update_stats(__u32 srcip, int bytes)
177 { 167 {
178 struct key key = { 168 struct key key = {
179 .srcip = srcip, 169 .srcip = srcip,
180 }; 170 };
181 struct value *value = bpf_map_look 171 struct value *value = bpf_map_lookup_elem(&packet_stats, &key);
182 172
183 if (value) { 173 if (value) {
184 __sync_fetch_and_add(&valu 174 __sync_fetch_and_add(&value->packets, 1);
185 __sync_fetch_and_add(&valu 175 __sync_fetch_and_add(&value->bytes, bytes);
186 } else { 176 } else {
187 struct value newval = { 1, 177 struct value newval = { 1, bytes };
188 178
189 bpf_map_update_elem(&packe 179 bpf_map_update_elem(&packet_stats, &key, &newval, BPF_NOEXIST);
190 } 180 }
191 } 181 }
192 182
193 Userspace walking the map elements from the ma 183 Userspace walking the map elements from the map declared above:
194 184
195 .. code-block:: c 185 .. code-block:: c
196 186
197 #include <bpf/libbpf.h> 187 #include <bpf/libbpf.h>
198 #include <bpf/bpf.h> 188 #include <bpf/bpf.h>
199 189
200 static void walk_hash_elements(int map_fd) 190 static void walk_hash_elements(int map_fd)
201 { 191 {
202 struct key *cur_key = NULL; 192 struct key *cur_key = NULL;
203 struct key next_key; 193 struct key next_key;
204 struct value value; 194 struct value value;
205 int err; 195 int err;
206 196
207 for (;;) { 197 for (;;) {
208 err = bpf_map_get_next_key 198 err = bpf_map_get_next_key(map_fd, cur_key, &next_key);
209 if (err) 199 if (err)
210 break; 200 break;
211 201
212 bpf_map_lookup_elem(map_fd 202 bpf_map_lookup_elem(map_fd, &next_key, &value);
213 203
214 // Use key and value here 204 // Use key and value here
215 205
216 cur_key = &next_key; 206 cur_key = &next_key;
217 } 207 }
218 } 208 }
219 <<
220 Internals <<
221 ========= <<
222 <<
223 This section of the document is targeted at Li <<
224 aspects of the map implementations that are no <<
225 following details are subject to change in fut <<
226 <<
227 ``BPF_MAP_TYPE_LRU_HASH`` and variants <<
228 -------------------------------------- <<
229 <<
230 Updating elements in LRU maps may trigger evic <<
231 of the map is reached. There are various steps <<
232 attempts in order to enforce the LRU property <<
233 other CPUs involved in the following operation <<
234 <<
235 - Attempt to use CPU-local state to batch oper <<
236 - Attempt to fetch free nodes from global list <<
237 - Attempt to pull any node from a global list <<
238 - Attempt to pull any node from any CPU's list <<
239 <<
240 This algorithm is described visually in the fo <<
241 description in commit 3a08c2fd7634 ("bpf: LRU <<
242 the corresponding operations: <<
243 <<
244 .. kernel-figure:: map_lru_hash_update.dot <<
245 :alt: Diagram outlining the LRU eviction <<
246 <<
247 LRU hash eviction during map update for ``B <<
248 variants. See the dot file source for kerne <<
249 <<
250 Map updates start from the oval in the top rig <<
251 and progress through the graph towards the bot <<
252 either a successful update or a failure with v <<
253 the top right provides indicators for which lo <<
254 operations. This is intended as a visual hint <<
255 contention may impact update operations, thoug <<
256 impact the actual contention on those locks, b <<
257 the table above. For instance, if the map is c <<
258 ``BPF_MAP_TYPE_LRU_PERCPU_HASH`` and flags ``B <<
259 properties would be per-cpu. <<
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.