lpm_trie.c 21 KB

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