xref: /linux/Documentation/bpf/map_hash.rst (revision 2da68a77) 
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
37.. c:function::
38   long bpf_map_update_elem(struct bpf_map *map, const void *key, const void *value, u64 flags)
39
40Hash entries can be added or updated using the ``bpf_map_update_elem()``
41helper. This helper replaces existing elements atomically. The ``flags``
42parameter can be used to control the update behaviour:
43
44- ``BPF_ANY`` will create a new element or update an existing element
45- ``BPF_NOEXIST`` will create a new element only if one did not already
46  exist
47- ``BPF_EXIST`` will update an existing element
48
49``bpf_map_update_elem()`` returns 0 on success, or negative error in
50case of failure.
51
52.. c:function::
53   void *bpf_map_lookup_elem(struct bpf_map *map, const void *key)
54
55Hash entries can be retrieved using the ``bpf_map_lookup_elem()``
56helper. This helper returns a pointer to the value associated with
57``key``, or ``NULL`` if no entry was found.
58
59.. c:function::
60   long bpf_map_delete_elem(struct bpf_map *map, const void *key)
61
62Hash entries can be deleted using the ``bpf_map_delete_elem()``
63helper. This helper will return 0 on success, or negative error in case
64of failure.
65
66Per CPU Hashes
67--------------
68
69For ``BPF_MAP_TYPE_PERCPU_HASH`` and ``BPF_MAP_TYPE_LRU_PERCPU_HASH``
70the ``bpf_map_update_elem()`` and ``bpf_map_lookup_elem()`` helpers
71automatically access the hash slot for the current CPU.
72
73.. c:function::
74   void *bpf_map_lookup_percpu_elem(struct bpf_map *map, const void *key, u32 cpu)
75
76The ``bpf_map_lookup_percpu_elem()`` helper can be used to lookup the
77value in the hash slot for a specific CPU. Returns value associated with
78``key`` on ``cpu`` , or ``NULL`` if no entry was found or ``cpu`` is
79invalid.
80
81Concurrency
82-----------
83
84Values stored in ``BPF_MAP_TYPE_HASH`` can be accessed concurrently by
85programs running on different CPUs.  Since Kernel version 5.1, the BPF
86infrastructure provides ``struct bpf_spin_lock`` to synchronise access.
87See ``tools/testing/selftests/bpf/progs/test_spin_lock.c``.
88
89Userspace
90---------
91
92.. c:function::
93   int bpf_map_get_next_key(int fd, const void *cur_key, void *next_key)
94
95In userspace, it is possible to iterate through the keys of a hash using
96libbpf's ``bpf_map_get_next_key()`` function. The first key can be fetched by
97calling ``bpf_map_get_next_key()`` with ``cur_key`` set to
98``NULL``. Subsequent calls will fetch the next key that follows the
99current key. ``bpf_map_get_next_key()`` returns 0 on success, -ENOENT if
100cur_key is the last key in the hash, or negative error in case of
101failure.
102
103Note that if ``cur_key`` gets deleted then ``bpf_map_get_next_key()``
104will instead return the *first* key in the hash table which is
105undesirable. It is recommended to use batched lookup if there is going
106to be key deletion intermixed with ``bpf_map_get_next_key()``.
107
108Examples
109========
110
111Please see the ``tools/testing/selftests/bpf`` directory for functional
112examples.  The code snippets below demonstrates API usage.
113
114This example shows how to declare an LRU Hash with a struct key and a
115struct value.
116
117.. code-block:: c
118
119    #include <linux/bpf.h>
120    #include <bpf/bpf_helpers.h>
121
122    struct key {
123        __u32 srcip;
124    };
125
126    struct value {
127        __u64 packets;
128        __u64 bytes;
129    };
130
131    struct {
132            __uint(type, BPF_MAP_TYPE_LRU_HASH);
133            __uint(max_entries, 32);
134            __type(key, struct key);
135            __type(value, struct value);
136    } packet_stats SEC(".maps");
137
138This example shows how to create or update hash values using atomic
139instructions:
140
141.. code-block:: c
142
143    static void update_stats(__u32 srcip, int bytes)
144    {
145            struct key key = {
146                    .srcip = srcip,
147            };
148            struct value *value = bpf_map_lookup_elem(&packet_stats, &key);
149
150            if (value) {
151                    __sync_fetch_and_add(&value->packets, 1);
152                    __sync_fetch_and_add(&value->bytes, bytes);
153            } else {
154                    struct value newval = { 1, bytes };
155
156                    bpf_map_update_elem(&packet_stats, &key, &newval, BPF_NOEXIST);
157            }
158    }
159
160Userspace walking the map elements from the map declared above:
161
162.. code-block:: c
163
164    #include <bpf/libbpf.h>
165    #include <bpf/bpf.h>
166
167    static void walk_hash_elements(int map_fd)
168    {
169            struct key *cur_key = NULL;
170            struct key next_key;
171            struct value value;
172            int err;
173
174            for (;;) {
175                    err = bpf_map_get_next_key(map_fd, cur_key, &next_key);
176                    if (err)
177                            break;
178
179                    bpf_map_lookup_elem(map_fd, &next_key, &value);
180
181                    // Use key and value here
182
183                    cur_key = &next_key;
184            }
185    }
186