^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0-only
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * Longest prefix match list implementation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * Copyright (c) 2016,2017 Daniel Mack
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * Copyright (c) 2016 David Herrmann
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) #include <linux/bpf.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) #include <linux/btf.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) #include <linux/err.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) #include <linux/slab.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) #include <linux/spinlock.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) #include <linux/vmalloc.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) #include <net/ipv6.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) #include <uapi/linux/btf.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) /* Intermediate node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) #define LPM_TREE_NODE_FLAG_IM BIT(0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) struct lpm_trie_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) struct lpm_trie_node {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) struct rcu_head rcu;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) struct lpm_trie_node __rcu *child[2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) u32 prefixlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) u32 flags;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) u8 data[];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) struct lpm_trie {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) struct bpf_map map;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) struct lpm_trie_node __rcu *root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) size_t n_entries;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) size_t max_prefixlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) size_t data_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) spinlock_t lock;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) /* This trie implements a longest prefix match algorithm that can be used to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) * match IP addresses to a stored set of ranges.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) * Data stored in @data of struct bpf_lpm_key and struct lpm_trie_node is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) * interpreted as big endian, so data[0] stores the most significant byte.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) * Match ranges are internally stored in instances of struct lpm_trie_node
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) * which each contain their prefix length as well as two pointers that may
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) * lead to more nodes containing more specific matches. Each node also stores
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) * a value that is defined by and returned to userspace via the update_elem
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) * and lookup functions.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) * For instance, let's start with a trie that was created with a prefix length
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) * of 32, so it can be used for IPv4 addresses, and one single element that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) * matches 192.168.0.0/16. The data array would hence contain
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) * [0xc0, 0xa8, 0x00, 0x00] in big-endian notation. This documentation will
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) * stick to IP-address notation for readability though.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) * As the trie is empty initially, the new node (1) will be places as root
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) * node, denoted as (R) in the example below. As there are no other node, both
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) * child pointers are %NULL.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) * +----------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) * | (1) (R) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) * | 192.168.0.0/16 |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) * | value: 1 |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) * | [0] [1] |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) * +----------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) * Next, let's add a new node (2) matching 192.168.0.0/24. As there is already
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) * a node with the same data and a smaller prefix (ie, a less specific one),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) * node (2) will become a child of (1). In child index depends on the next bit
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) * that is outside of what (1) matches, and that bit is 0, so (2) will be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) * child[0] of (1):
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) * +----------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) * | (1) (R) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) * | 192.168.0.0/16 |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) * | value: 1 |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) * | [0] [1] |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) * +----------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) * |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) * +----------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) * | (2) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) * | 192.168.0.0/24 |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) * | value: 2 |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) * | [0] [1] |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) * +----------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) * The child[1] slot of (1) could be filled with another node which has bit #17
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) * (the next bit after the ones that (1) matches on) set to 1. For instance,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) * 192.168.128.0/24:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) * +----------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) * | (1) (R) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) * | 192.168.0.0/16 |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) * | value: 1 |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) * | [0] [1] |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) * +----------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) * | |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) * +----------------+ +------------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) * | (2) | | (3) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) * | 192.168.0.0/24 | | 192.168.128.0/24 |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) * | value: 2 | | value: 3 |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) * | [0] [1] | | [0] [1] |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) * +----------------+ +------------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) * Let's add another node (4) to the game for 192.168.1.0/24. In order to place
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) * it, node (1) is looked at first, and because (4) of the semantics laid out
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) * above (bit #17 is 0), it would normally be attached to (1) as child[0].
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) * However, that slot is already allocated, so a new node is needed in between.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) * That node does not have a value attached to it and it will never be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) * returned to users as result of a lookup. It is only there to differentiate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) * the traversal further. It will get a prefix as wide as necessary to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) * distinguish its two children:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) * +----------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) * | (1) (R) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) * | 192.168.0.0/16 |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) * | value: 1 |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) * | [0] [1] |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) * +----------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) * | |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) * +----------------+ +------------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) * | (4) (I) | | (3) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) * | 192.168.0.0/23 | | 192.168.128.0/24 |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) * | value: --- | | value: 3 |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) * | [0] [1] | | [0] [1] |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) * +----------------+ +------------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) * | |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) * +----------------+ +----------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) * | (2) | | (5) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) * | 192.168.0.0/24 | | 192.168.1.0/24 |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) * | value: 2 | | value: 5 |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) * | [0] [1] | | [0] [1] |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) * +----------------+ +----------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) * 192.168.1.1/32 would be a child of (5) etc.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) * An intermediate node will be turned into a 'real' node on demand. In the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) * example above, (4) would be re-used if 192.168.0.0/23 is added to the trie.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) * A fully populated trie would have a height of 32 nodes, as the trie was
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) * created with a prefix length of 32.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) * The lookup starts at the root node. If the current node matches and if there
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) * is a child that can be used to become more specific, the trie is traversed
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) * downwards. The last node in the traversal that is a non-intermediate one is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) * returned.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) static inline int extract_bit(const u8 *data, size_t index)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) return !!(data[index / 8] & (1 << (7 - (index % 8))));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) * longest_prefix_match() - determine the longest prefix
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) * @trie: The trie to get internal sizes from
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) * @node: The node to operate on
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) * @key: The key to compare to @node
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) * Determine the longest prefix of @node that matches the bits in @key.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) static size_t longest_prefix_match(const struct lpm_trie *trie,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) const struct lpm_trie_node *node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) const struct bpf_lpm_trie_key *key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) u32 limit = min(node->prefixlen, key->prefixlen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) u32 prefixlen = 0, i = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) BUILD_BUG_ON(offsetof(struct lpm_trie_node, data) % sizeof(u32));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) BUILD_BUG_ON(offsetof(struct bpf_lpm_trie_key, data) % sizeof(u32));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) && defined(CONFIG_64BIT)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) /* data_size >= 16 has very small probability.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) * We do not use a loop for optimal code generation.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) if (trie->data_size >= 8) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) u64 diff = be64_to_cpu(*(__be64 *)node->data ^
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) *(__be64 *)key->data);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) prefixlen = 64 - fls64(diff);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) if (prefixlen >= limit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) return limit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) if (diff)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) return prefixlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) i = 8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) while (trie->data_size >= i + 4) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) u32 diff = be32_to_cpu(*(__be32 *)&node->data[i] ^
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) *(__be32 *)&key->data[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) prefixlen += 32 - fls(diff);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) if (prefixlen >= limit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) return limit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) if (diff)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) return prefixlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) i += 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) if (trie->data_size >= i + 2) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) u16 diff = be16_to_cpu(*(__be16 *)&node->data[i] ^
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) *(__be16 *)&key->data[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) prefixlen += 16 - fls(diff);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) if (prefixlen >= limit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) return limit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) if (diff)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) return prefixlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) i += 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) if (trie->data_size >= i + 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) prefixlen += 8 - fls(node->data[i] ^ key->data[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) if (prefixlen >= limit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) return limit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) return prefixlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) /* Called from syscall or from eBPF program */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) static void *trie_lookup_elem(struct bpf_map *map, void *_key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) struct lpm_trie *trie = container_of(map, struct lpm_trie, map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) struct lpm_trie_node *node, *found = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) struct bpf_lpm_trie_key *key = _key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) /* Start walking the trie from the root node ... */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) for (node = rcu_dereference(trie->root); node;) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) unsigned int next_bit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) size_t matchlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) /* Determine the longest prefix of @node that matches @key.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) * If it's the maximum possible prefix for this trie, we have
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) * an exact match and can return it directly.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) matchlen = longest_prefix_match(trie, node, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) if (matchlen == trie->max_prefixlen) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) found = node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) /* If the number of bits that match is smaller than the prefix
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) * length of @node, bail out and return the node we have seen
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) * last in the traversal (ie, the parent).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) if (matchlen < node->prefixlen)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) /* Consider this node as return candidate unless it is an
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) * artificially added intermediate one.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) if (!(node->flags & LPM_TREE_NODE_FLAG_IM))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) found = node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) /* If the node match is fully satisfied, let's see if we can
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) * become more specific. Determine the next bit in the key and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) * traverse down.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) next_bit = extract_bit(key->data, node->prefixlen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) node = rcu_dereference(node->child[next_bit]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) if (!found)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) return found->data + trie->data_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) static struct lpm_trie_node *lpm_trie_node_alloc(const struct lpm_trie *trie,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) const void *value)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) struct lpm_trie_node *node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) size_t size = sizeof(struct lpm_trie_node) + trie->data_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) if (value)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) size += trie->map.value_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) node = kmalloc_node(size, GFP_ATOMIC | __GFP_NOWARN,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) trie->map.numa_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) if (!node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) node->flags = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) if (value)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) memcpy(node->data + trie->data_size, value,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) trie->map.value_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) return node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) /* Called from syscall or from eBPF program */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) static int trie_update_elem(struct bpf_map *map,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) void *_key, void *value, u64 flags)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) struct lpm_trie *trie = container_of(map, struct lpm_trie, map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) struct lpm_trie_node *node, *im_node = NULL, *new_node = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) struct lpm_trie_node __rcu **slot;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) struct bpf_lpm_trie_key *key = _key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) unsigned long irq_flags;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) unsigned int next_bit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) size_t matchlen = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) int ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) if (unlikely(flags > BPF_EXIST))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) if (key->prefixlen > trie->max_prefixlen)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) spin_lock_irqsave(&trie->lock, irq_flags);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) /* Allocate and fill a new node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) if (trie->n_entries == trie->map.max_entries) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) ret = -ENOSPC;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) new_node = lpm_trie_node_alloc(trie, value);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) if (!new_node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) ret = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) trie->n_entries++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335) new_node->prefixlen = key->prefixlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) RCU_INIT_POINTER(new_node->child[0], NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) RCU_INIT_POINTER(new_node->child[1], NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) memcpy(new_node->data, key->data, trie->data_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) /* Now find a slot to attach the new node. To do that, walk the tree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) * from the root and match as many bits as possible for each node until
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) * we either find an empty slot or a slot that needs to be replaced by
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343) * an intermediate node.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) slot = &trie->root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) while ((node = rcu_dereference_protected(*slot,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) lockdep_is_held(&trie->lock)))) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) matchlen = longest_prefix_match(trie, node, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) if (node->prefixlen != matchlen ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) node->prefixlen == key->prefixlen ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) node->prefixlen == trie->max_prefixlen)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) next_bit = extract_bit(key->data, node->prefixlen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) slot = &node->child[next_bit];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) /* If the slot is empty (a free child pointer or an empty root),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) * simply assign the @new_node to that slot and be done.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) if (!node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) rcu_assign_pointer(*slot, new_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) /* If the slot we picked already exists, replace it with @new_node
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) * which already has the correct data array set.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) if (node->prefixlen == matchlen) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) new_node->child[0] = node->child[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) new_node->child[1] = node->child[1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) if (!(node->flags & LPM_TREE_NODE_FLAG_IM))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) trie->n_entries--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) rcu_assign_pointer(*slot, new_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) kfree_rcu(node, rcu);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384) /* If the new node matches the prefix completely, it must be inserted
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) * as an ancestor. Simply insert it between @node and *@slot.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) if (matchlen == key->prefixlen) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388) next_bit = extract_bit(node->data, matchlen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389) rcu_assign_pointer(new_node->child[next_bit], node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) rcu_assign_pointer(*slot, new_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) im_node = lpm_trie_node_alloc(trie, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) if (!im_node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) ret = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) im_node->prefixlen = matchlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) im_node->flags |= LPM_TREE_NODE_FLAG_IM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) memcpy(im_node->data, node->data, trie->data_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) /* Now determine which child to install in which slot */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) if (extract_bit(key->data, matchlen)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) rcu_assign_pointer(im_node->child[0], node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) rcu_assign_pointer(im_node->child[1], new_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) rcu_assign_pointer(im_node->child[0], new_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) rcu_assign_pointer(im_node->child[1], node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413) /* Finally, assign the intermediate node to the determined spot */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) rcu_assign_pointer(*slot, im_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) if (ret) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) if (new_node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419) trie->n_entries--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421) kfree(new_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) kfree(im_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425) spin_unlock_irqrestore(&trie->lock, irq_flags);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) /* Called from syscall or from eBPF program */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431) static int trie_delete_elem(struct bpf_map *map, void *_key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) struct lpm_trie *trie = container_of(map, struct lpm_trie, map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434) struct bpf_lpm_trie_key *key = _key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) struct lpm_trie_node __rcu **trim, **trim2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436) struct lpm_trie_node *node, *parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437) unsigned long irq_flags;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438) unsigned int next_bit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439) size_t matchlen = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440) int ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) if (key->prefixlen > trie->max_prefixlen)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445) spin_lock_irqsave(&trie->lock, irq_flags);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447) /* Walk the tree looking for an exact key/length match and keeping
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448) * track of the path we traverse. We will need to know the node
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449) * we wish to delete, and the slot that points to the node we want
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) * to delete. We may also need to know the nodes parent and the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451) * slot that contains it.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453) trim = &trie->root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454) trim2 = trim;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) parent = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456) while ((node = rcu_dereference_protected(
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457) *trim, lockdep_is_held(&trie->lock)))) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458) matchlen = longest_prefix_match(trie, node, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460) if (node->prefixlen != matchlen ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461) node->prefixlen == key->prefixlen)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464) parent = node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465) trim2 = trim;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466) next_bit = extract_bit(key->data, node->prefixlen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467) trim = &node->child[next_bit];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470) if (!node || node->prefixlen != key->prefixlen ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471) node->prefixlen != matchlen ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472) (node->flags & LPM_TREE_NODE_FLAG_IM)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473) ret = -ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477) trie->n_entries--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479) /* If the node we are removing has two children, simply mark it
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) * as intermediate and we are done.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482) if (rcu_access_pointer(node->child[0]) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483) rcu_access_pointer(node->child[1])) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484) node->flags |= LPM_TREE_NODE_FLAG_IM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) /* If the parent of the node we are about to delete is an intermediate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489) * node, and the deleted node doesn't have any children, we can delete
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490) * the intermediate parent as well and promote its other child
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491) * up the tree. Doing this maintains the invariant that all
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492) * intermediate nodes have exactly 2 children and that there are no
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) * unnecessary intermediate nodes in the tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495) if (parent && (parent->flags & LPM_TREE_NODE_FLAG_IM) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) !node->child[0] && !node->child[1]) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497) if (node == rcu_access_pointer(parent->child[0]))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498) rcu_assign_pointer(
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499) *trim2, rcu_access_pointer(parent->child[1]));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501) rcu_assign_pointer(
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502) *trim2, rcu_access_pointer(parent->child[0]));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503) kfree_rcu(parent, rcu);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504) kfree_rcu(node, rcu);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508) /* The node we are removing has either zero or one child. If there
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509) * is a child, move it into the removed node's slot then delete
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510) * the node. Otherwise just clear the slot and delete the node.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512) if (node->child[0])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513) rcu_assign_pointer(*trim, rcu_access_pointer(node->child[0]));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514) else if (node->child[1])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515) rcu_assign_pointer(*trim, rcu_access_pointer(node->child[1]));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517) RCU_INIT_POINTER(*trim, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518) kfree_rcu(node, rcu);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521) spin_unlock_irqrestore(&trie->lock, irq_flags);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526) #define LPM_DATA_SIZE_MAX 256
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527) #define LPM_DATA_SIZE_MIN 1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529) #define LPM_VAL_SIZE_MAX (KMALLOC_MAX_SIZE - LPM_DATA_SIZE_MAX - \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 530) sizeof(struct lpm_trie_node))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 531) #define LPM_VAL_SIZE_MIN 1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 532)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 533) #define LPM_KEY_SIZE(X) (sizeof(struct bpf_lpm_trie_key) + (X))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 534) #define LPM_KEY_SIZE_MAX LPM_KEY_SIZE(LPM_DATA_SIZE_MAX)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 535) #define LPM_KEY_SIZE_MIN LPM_KEY_SIZE(LPM_DATA_SIZE_MIN)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 536)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 537) #define LPM_CREATE_FLAG_MASK (BPF_F_NO_PREALLOC | BPF_F_NUMA_NODE | \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 538) BPF_F_ACCESS_MASK)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 539)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 540) static struct bpf_map *trie_alloc(union bpf_attr *attr)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 541) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 542) struct lpm_trie *trie;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 543) u64 cost = sizeof(*trie), cost_per_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 544) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 545)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 546) if (!bpf_capable())
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 547) return ERR_PTR(-EPERM);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 548)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 549) /* check sanity of attributes */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 550) if (attr->max_entries == 0 ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 551) !(attr->map_flags & BPF_F_NO_PREALLOC) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 552) attr->map_flags & ~LPM_CREATE_FLAG_MASK ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 553) !bpf_map_flags_access_ok(attr->map_flags) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 554) attr->key_size < LPM_KEY_SIZE_MIN ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 555) attr->key_size > LPM_KEY_SIZE_MAX ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 556) attr->value_size < LPM_VAL_SIZE_MIN ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 557) attr->value_size > LPM_VAL_SIZE_MAX)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 558) return ERR_PTR(-EINVAL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 559)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 560) trie = kzalloc(sizeof(*trie), GFP_USER | __GFP_NOWARN);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 561) if (!trie)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 562) return ERR_PTR(-ENOMEM);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 563)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 564) /* copy mandatory map attributes */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 565) bpf_map_init_from_attr(&trie->map, attr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 566) trie->data_size = attr->key_size -
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 567) offsetof(struct bpf_lpm_trie_key, data);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 568) trie->max_prefixlen = trie->data_size * 8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 569)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 570) cost_per_node = sizeof(struct lpm_trie_node) +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 571) attr->value_size + trie->data_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 572) cost += (u64) attr->max_entries * cost_per_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 573)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 574) ret = bpf_map_charge_init(&trie->map.memory, cost);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 575) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 576) goto out_err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 577)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 578) spin_lock_init(&trie->lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 579)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 580) return &trie->map;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 581) out_err:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 582) kfree(trie);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 583) return ERR_PTR(ret);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 584) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 585)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 586) static void trie_free(struct bpf_map *map)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 587) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 588) struct lpm_trie *trie = container_of(map, struct lpm_trie, map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 589) struct lpm_trie_node __rcu **slot;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 590) struct lpm_trie_node *node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 591)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 592) /* Always start at the root and walk down to a node that has no
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 593) * children. Then free that node, nullify its reference in the parent
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 594) * and start over.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 595) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 596)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 597) for (;;) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 598) slot = &trie->root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 599)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 600) for (;;) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 601) node = rcu_dereference_protected(*slot, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 602) if (!node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 603) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 604)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 605) if (rcu_access_pointer(node->child[0])) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 606) slot = &node->child[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 607) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 608) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 609)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 610) if (rcu_access_pointer(node->child[1])) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 611) slot = &node->child[1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 612) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 613) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 614)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 615) kfree(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 616) RCU_INIT_POINTER(*slot, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 617) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 618) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 619) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 620)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 621) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 622) kfree(trie);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 623) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 624)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 625) static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 626) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 627) struct lpm_trie_node *node, *next_node = NULL, *parent, *search_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 628) struct lpm_trie *trie = container_of(map, struct lpm_trie, map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 629) struct bpf_lpm_trie_key *key = _key, *next_key = _next_key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 630) struct lpm_trie_node **node_stack = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 631) int err = 0, stack_ptr = -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 632) unsigned int next_bit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 633) size_t matchlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 634)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 635) /* The get_next_key follows postorder. For the 4 node example in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 636) * the top of this file, the trie_get_next_key() returns the following
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 637) * one after another:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 638) * 192.168.0.0/24
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 639) * 192.168.1.0/24
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 640) * 192.168.128.0/24
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 641) * 192.168.0.0/16
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 642) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 643) * The idea is to return more specific keys before less specific ones.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 644) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 645)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 646) /* Empty trie */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 647) search_root = rcu_dereference(trie->root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 648) if (!search_root)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 649) return -ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 650)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 651) /* For invalid key, find the leftmost node in the trie */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 652) if (!key || key->prefixlen > trie->max_prefixlen)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 653) goto find_leftmost;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 654)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 655) node_stack = kmalloc_array(trie->max_prefixlen,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 656) sizeof(struct lpm_trie_node *),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 657) GFP_ATOMIC | __GFP_NOWARN);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 658) if (!node_stack)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 659) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 660)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 661) /* Try to find the exact node for the given key */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 662) for (node = search_root; node;) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 663) node_stack[++stack_ptr] = node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 664) matchlen = longest_prefix_match(trie, node, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 665) if (node->prefixlen != matchlen ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 666) node->prefixlen == key->prefixlen)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 667) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 668)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 669) next_bit = extract_bit(key->data, node->prefixlen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 670) node = rcu_dereference(node->child[next_bit]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 671) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 672) if (!node || node->prefixlen != key->prefixlen ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 673) (node->flags & LPM_TREE_NODE_FLAG_IM))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 674) goto find_leftmost;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 675)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 676) /* The node with the exactly-matching key has been found,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 677) * find the first node in postorder after the matched node.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 678) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 679) node = node_stack[stack_ptr];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 680) while (stack_ptr > 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 681) parent = node_stack[stack_ptr - 1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 682) if (rcu_dereference(parent->child[0]) == node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 683) search_root = rcu_dereference(parent->child[1]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 684) if (search_root)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 685) goto find_leftmost;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 686) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 687) if (!(parent->flags & LPM_TREE_NODE_FLAG_IM)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 688) next_node = parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 689) goto do_copy;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 690) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 691)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 692) node = parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 693) stack_ptr--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 694) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 695)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 696) /* did not find anything */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 697) err = -ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 698) goto free_stack;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 699)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 700) find_leftmost:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 701) /* Find the leftmost non-intermediate node, all intermediate nodes
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 702) * have exact two children, so this function will never return NULL.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 703) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 704) for (node = search_root; node;) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 705) if (node->flags & LPM_TREE_NODE_FLAG_IM) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 706) node = rcu_dereference(node->child[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 707) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 708) next_node = node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 709) node = rcu_dereference(node->child[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 710) if (!node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 711) node = rcu_dereference(next_node->child[1]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 712) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 713) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 714) do_copy:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 715) next_key->prefixlen = next_node->prefixlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 716) memcpy((void *)next_key + offsetof(struct bpf_lpm_trie_key, data),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 717) next_node->data, trie->data_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 718) free_stack:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 719) kfree(node_stack);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 720) return err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 721) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 722)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 723) static int trie_check_btf(const struct bpf_map *map,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 724) const struct btf *btf,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 725) const struct btf_type *key_type,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 726) const struct btf_type *value_type)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 727) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 728) /* Keys must have struct bpf_lpm_trie_key embedded. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 729) return BTF_INFO_KIND(key_type->info) != BTF_KIND_STRUCT ?
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 730) -EINVAL : 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 731) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 732)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 733) static int trie_map_btf_id;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 734) const struct bpf_map_ops trie_map_ops = {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 735) .map_meta_equal = bpf_map_meta_equal,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 736) .map_alloc = trie_alloc,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 737) .map_free = trie_free,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 738) .map_get_next_key = trie_get_next_key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 739) .map_lookup_elem = trie_lookup_elem,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 740) .map_update_elem = trie_update_elem,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 741) .map_delete_elem = trie_delete_elem,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 742) .map_check_btf = trie_check_btf,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 743) .map_btf_name = "lpm_trie",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 744) .map_btf_id = &trie_map_btf_id,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 745) };
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags