183177c0dSDonald Hunter.. SPDX-License-Identifier: GPL-2.0-only 283177c0dSDonald Hunter.. Copyright (C) 2022 Red Hat, Inc. 383177c0dSDonald Hunter 483177c0dSDonald Hunter===================== 583177c0dSDonald HunterBPF_MAP_TYPE_LPM_TRIE 683177c0dSDonald Hunter===================== 783177c0dSDonald Hunter 883177c0dSDonald Hunter.. note:: 983177c0dSDonald Hunter - ``BPF_MAP_TYPE_LPM_TRIE`` was introduced in kernel version 4.11 1083177c0dSDonald Hunter 1183177c0dSDonald Hunter``BPF_MAP_TYPE_LPM_TRIE`` provides a longest prefix match algorithm that 1283177c0dSDonald Huntercan be used to match IP addresses to a stored set of prefixes. 1383177c0dSDonald HunterInternally, data is stored in an unbalanced trie of nodes that uses 1483177c0dSDonald Hunter``prefixlen,data`` pairs as its keys. The ``data`` is interpreted in 1583177c0dSDonald Hunternetwork byte order, i.e. big endian, so ``data[0]`` stores the most 1683177c0dSDonald Huntersignificant byte. 1783177c0dSDonald Hunter 1883177c0dSDonald HunterLPM tries may be created with a maximum prefix length that is a multiple 1983177c0dSDonald Hunterof 8, in the range from 8 to 2048. The key used for lookup and update 20*896880ffSKees Cookoperations is a ``struct bpf_lpm_trie_key_u8``, extended by 2183177c0dSDonald Hunter``max_prefixlen/8`` bytes. 2283177c0dSDonald Hunter 2383177c0dSDonald Hunter- For IPv4 addresses the data length is 4 bytes 2483177c0dSDonald Hunter- For IPv6 addresses the data length is 16 bytes 2583177c0dSDonald Hunter 2683177c0dSDonald HunterThe value type stored in the LPM trie can be any user defined type. 2783177c0dSDonald Hunter 2883177c0dSDonald Hunter.. note:: 2983177c0dSDonald Hunter When creating a map of type ``BPF_MAP_TYPE_LPM_TRIE`` you must set the 3083177c0dSDonald Hunter ``BPF_F_NO_PREALLOC`` flag. 3183177c0dSDonald Hunter 3283177c0dSDonald HunterUsage 3383177c0dSDonald Hunter===== 3483177c0dSDonald Hunter 3583177c0dSDonald HunterKernel BPF 3683177c0dSDonald Hunter---------- 3783177c0dSDonald Hunter 38539886a3SDonald Hunterbpf_map_lookup_elem() 39539886a3SDonald Hunter~~~~~~~~~~~~~~~~~~~~~ 40539886a3SDonald Hunter 41539886a3SDonald Hunter.. code-block:: c 42539886a3SDonald Hunter 4383177c0dSDonald Hunter void *bpf_map_lookup_elem(struct bpf_map *map, const void *key) 4483177c0dSDonald Hunter 4583177c0dSDonald HunterThe longest prefix entry for a given data value can be found using the 4683177c0dSDonald Hunter``bpf_map_lookup_elem()`` helper. This helper returns a pointer to the 4783177c0dSDonald Huntervalue associated with the longest matching ``key``, or ``NULL`` if no 4883177c0dSDonald Hunterentry was found. 4983177c0dSDonald Hunter 5083177c0dSDonald HunterThe ``key`` should have ``prefixlen`` set to ``max_prefixlen`` when 5183177c0dSDonald Hunterperforming longest prefix lookups. For example, when searching for the 5283177c0dSDonald Hunterlongest prefix match for an IPv4 address, ``prefixlen`` should be set to 5383177c0dSDonald Hunter``32``. 5483177c0dSDonald Hunter 55539886a3SDonald Hunterbpf_map_update_elem() 56539886a3SDonald Hunter~~~~~~~~~~~~~~~~~~~~~ 57539886a3SDonald Hunter 58539886a3SDonald Hunter.. code-block:: c 59539886a3SDonald Hunter 6083177c0dSDonald Hunter long bpf_map_update_elem(struct bpf_map *map, const void *key, const void *value, u64 flags) 6183177c0dSDonald Hunter 6283177c0dSDonald HunterPrefix entries can be added or updated using the ``bpf_map_update_elem()`` 6383177c0dSDonald Hunterhelper. This helper replaces existing elements atomically. 6483177c0dSDonald Hunter 6583177c0dSDonald Hunter``bpf_map_update_elem()`` returns ``0`` on success, or negative error in 6683177c0dSDonald Huntercase of failure. 6783177c0dSDonald Hunter 6883177c0dSDonald Hunter .. note:: 6983177c0dSDonald Hunter The flags parameter must be one of BPF_ANY, BPF_NOEXIST or BPF_EXIST, 7083177c0dSDonald Hunter but the value is ignored, giving BPF_ANY semantics. 7183177c0dSDonald Hunter 72539886a3SDonald Hunterbpf_map_delete_elem() 73539886a3SDonald Hunter~~~~~~~~~~~~~~~~~~~~~ 74539886a3SDonald Hunter 75539886a3SDonald Hunter.. code-block:: c 76539886a3SDonald Hunter 7783177c0dSDonald Hunter long bpf_map_delete_elem(struct bpf_map *map, const void *key) 7883177c0dSDonald Hunter 7983177c0dSDonald HunterPrefix entries can be deleted using the ``bpf_map_delete_elem()`` 8083177c0dSDonald Hunterhelper. This helper will return 0 on success, or negative error in case 8183177c0dSDonald Hunterof failure. 8283177c0dSDonald Hunter 8383177c0dSDonald HunterUserspace 8483177c0dSDonald Hunter--------- 8583177c0dSDonald Hunter 8683177c0dSDonald HunterAccess from userspace uses libbpf APIs with the same names as above, with 8783177c0dSDonald Hunterthe map identified by ``fd``. 8883177c0dSDonald Hunter 89539886a3SDonald Hunterbpf_map_get_next_key() 90539886a3SDonald Hunter~~~~~~~~~~~~~~~~~~~~~~ 91539886a3SDonald Hunter 92539886a3SDonald Hunter.. code-block:: c 93539886a3SDonald Hunter 9483177c0dSDonald Hunter int bpf_map_get_next_key (int fd, const void *cur_key, void *next_key) 9583177c0dSDonald Hunter 9683177c0dSDonald HunterA userspace program can iterate through the entries in an LPM trie using 9783177c0dSDonald Hunterlibbpf's ``bpf_map_get_next_key()`` function. The first key can be 9883177c0dSDonald Hunterfetched by calling ``bpf_map_get_next_key()`` with ``cur_key`` set to 9983177c0dSDonald Hunter``NULL``. Subsequent calls will fetch the next key that follows the 10083177c0dSDonald Huntercurrent key. ``bpf_map_get_next_key()`` returns ``0`` on success, 10183177c0dSDonald Hunter``-ENOENT`` if ``cur_key`` is the last key in the trie, or negative 10283177c0dSDonald Huntererror in case of failure. 10383177c0dSDonald Hunter 10483177c0dSDonald Hunter``bpf_map_get_next_key()`` will iterate through the LPM trie elements 10583177c0dSDonald Hunterfrom leftmost leaf first. This means that iteration will return more 10683177c0dSDonald Hunterspecific keys before less specific ones. 10783177c0dSDonald Hunter 10883177c0dSDonald HunterExamples 10983177c0dSDonald Hunter======== 11083177c0dSDonald Hunter 11183177c0dSDonald HunterPlease see ``tools/testing/selftests/bpf/test_lpm_map.c`` for examples 11283177c0dSDonald Hunterof LPM trie usage from userspace. The code snippets below demonstrate 11383177c0dSDonald HunterAPI usage. 11483177c0dSDonald Hunter 11583177c0dSDonald HunterKernel BPF 11683177c0dSDonald Hunter---------- 11783177c0dSDonald Hunter 11883177c0dSDonald HunterThe following BPF code snippet shows how to declare a new LPM trie for IPv4 11983177c0dSDonald Hunteraddress prefixes: 12083177c0dSDonald Hunter 12183177c0dSDonald Hunter.. code-block:: c 12283177c0dSDonald Hunter 12383177c0dSDonald Hunter #include <linux/bpf.h> 12483177c0dSDonald Hunter #include <bpf/bpf_helpers.h> 12583177c0dSDonald Hunter 12683177c0dSDonald Hunter struct ipv4_lpm_key { 12783177c0dSDonald Hunter __u32 prefixlen; 12883177c0dSDonald Hunter __u32 data; 12983177c0dSDonald Hunter }; 13083177c0dSDonald Hunter 13183177c0dSDonald Hunter struct { 13283177c0dSDonald Hunter __uint(type, BPF_MAP_TYPE_LPM_TRIE); 13383177c0dSDonald Hunter __type(key, struct ipv4_lpm_key); 13483177c0dSDonald Hunter __type(value, __u32); 13583177c0dSDonald Hunter __uint(map_flags, BPF_F_NO_PREALLOC); 13683177c0dSDonald Hunter __uint(max_entries, 255); 13783177c0dSDonald Hunter } ipv4_lpm_map SEC(".maps"); 13883177c0dSDonald Hunter 13983177c0dSDonald HunterThe following BPF code snippet shows how to lookup by IPv4 address: 14083177c0dSDonald Hunter 14183177c0dSDonald Hunter.. code-block:: c 14283177c0dSDonald Hunter 14383177c0dSDonald Hunter void *lookup(__u32 ipaddr) 14483177c0dSDonald Hunter { 14583177c0dSDonald Hunter struct ipv4_lpm_key key = { 14683177c0dSDonald Hunter .prefixlen = 32, 14783177c0dSDonald Hunter .data = ipaddr 14883177c0dSDonald Hunter }; 14983177c0dSDonald Hunter 15083177c0dSDonald Hunter return bpf_map_lookup_elem(&ipv4_lpm_map, &key); 15183177c0dSDonald Hunter } 15283177c0dSDonald Hunter 15383177c0dSDonald HunterUserspace 15483177c0dSDonald Hunter--------- 15583177c0dSDonald Hunter 15683177c0dSDonald HunterThe following snippet shows how to insert an IPv4 prefix entry into an 15783177c0dSDonald HunterLPM trie: 15883177c0dSDonald Hunter 15983177c0dSDonald Hunter.. code-block:: c 16083177c0dSDonald Hunter 16183177c0dSDonald Hunter int add_prefix_entry(int lpm_fd, __u32 addr, __u32 prefixlen, struct value *value) 16283177c0dSDonald Hunter { 16383177c0dSDonald Hunter struct ipv4_lpm_key ipv4_key = { 16483177c0dSDonald Hunter .prefixlen = prefixlen, 16583177c0dSDonald Hunter .data = addr 16683177c0dSDonald Hunter }; 16783177c0dSDonald Hunter return bpf_map_update_elem(lpm_fd, &ipv4_key, value, BPF_ANY); 16883177c0dSDonald Hunter } 16983177c0dSDonald Hunter 17083177c0dSDonald HunterThe following snippet shows a userspace program walking through the entries 17183177c0dSDonald Hunterof an LPM trie: 17283177c0dSDonald Hunter 17383177c0dSDonald Hunter 17483177c0dSDonald Hunter.. code-block:: c 17583177c0dSDonald Hunter 17683177c0dSDonald Hunter #include <bpf/libbpf.h> 17783177c0dSDonald Hunter #include <bpf/bpf.h> 17883177c0dSDonald Hunter 17983177c0dSDonald Hunter void iterate_lpm_trie(int map_fd) 18083177c0dSDonald Hunter { 18183177c0dSDonald Hunter struct ipv4_lpm_key *cur_key = NULL; 18283177c0dSDonald Hunter struct ipv4_lpm_key next_key; 18383177c0dSDonald Hunter struct value value; 18483177c0dSDonald Hunter int err; 18583177c0dSDonald Hunter 18683177c0dSDonald Hunter for (;;) { 18783177c0dSDonald Hunter err = bpf_map_get_next_key(map_fd, cur_key, &next_key); 18883177c0dSDonald Hunter if (err) 18983177c0dSDonald Hunter break; 19083177c0dSDonald Hunter 19183177c0dSDonald Hunter bpf_map_lookup_elem(map_fd, &next_key, &value); 19283177c0dSDonald Hunter 19383177c0dSDonald Hunter /* Use key and value here */ 19483177c0dSDonald Hunter 19583177c0dSDonald Hunter cur_key = &next_key; 19683177c0dSDonald Hunter } 19783177c0dSDonald Hunter } 198