LCOV - code coverage report
Current view: top level - kernel/bpf - lpm_trie.c (source / functions) Hit Total Coverage
Test: Real Lines: 55 197 27.9 %
Date: 2020-10-17 15:46:16 Functions: 0 9 0.0 %
Legend: Neither, QEMU, Real, Both Branches: 0 0 -

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

Generated by: LCOV version 1.14