LCOV - code coverage report
Current view: top level - net/ipv4 - fib_trie.c (source / functions) Hit Total Coverage
Test: gcov_data_raspi2_real_modules_combined.info Lines: 363 969 37.5 %
Date: 2020-09-30 20:25:40 Functions: 24 61 39.3 %
Branches: 248 846 29.3 %

           Branch data     Line data    Source code
       1                 :            : // SPDX-License-Identifier: GPL-2.0-or-later
       2                 :            : /*
       3                 :            :  *
       4                 :            :  *   Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
       5                 :            :  *     & Swedish University of Agricultural Sciences.
       6                 :            :  *
       7                 :            :  *   Jens Laas <jens.laas@data.slu.se> Swedish University of
       8                 :            :  *     Agricultural Sciences.
       9                 :            :  *
      10                 :            :  *   Hans Liss <hans.liss@its.uu.se>  Uppsala Universitet
      11                 :            :  *
      12                 :            :  * This work is based on the LPC-trie which is originally described in:
      13                 :            :  *
      14                 :            :  * An experimental study of compression methods for dynamic tries
      15                 :            :  * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
      16                 :            :  * http://www.csc.kth.se/~snilsson/software/dyntrie2/
      17                 :            :  *
      18                 :            :  * IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
      19                 :            :  * IEEE Journal on Selected Areas in Communications, 17(6):1083-1092, June 1999
      20                 :            :  *
      21                 :            :  * Code from fib_hash has been reused which includes the following header:
      22                 :            :  *
      23                 :            :  * INET         An implementation of the TCP/IP protocol suite for the LINUX
      24                 :            :  *              operating system.  INET is implemented using the  BSD Socket
      25                 :            :  *              interface as the means of communication with the user level.
      26                 :            :  *
      27                 :            :  *              IPv4 FIB: lookup engine and maintenance routines.
      28                 :            :  *
      29                 :            :  * Authors:     Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
      30                 :            :  *
      31                 :            :  * Substantial contributions to this work comes from:
      32                 :            :  *
      33                 :            :  *              David S. Miller, <davem@davemloft.net>
      34                 :            :  *              Stephen Hemminger <shemminger@osdl.org>
      35                 :            :  *              Paul E. McKenney <paulmck@us.ibm.com>
      36                 :            :  *              Patrick McHardy <kaber@trash.net>
      37                 :            :  */
      38                 :            : 
      39                 :            : #define VERSION "0.409"
      40                 :            : 
      41                 :            : #include <linux/cache.h>
      42                 :            : #include <linux/uaccess.h>
      43                 :            : #include <linux/bitops.h>
      44                 :            : #include <linux/types.h>
      45                 :            : #include <linux/kernel.h>
      46                 :            : #include <linux/mm.h>
      47                 :            : #include <linux/string.h>
      48                 :            : #include <linux/socket.h>
      49                 :            : #include <linux/sockios.h>
      50                 :            : #include <linux/errno.h>
      51                 :            : #include <linux/in.h>
      52                 :            : #include <linux/inet.h>
      53                 :            : #include <linux/inetdevice.h>
      54                 :            : #include <linux/netdevice.h>
      55                 :            : #include <linux/if_arp.h>
      56                 :            : #include <linux/proc_fs.h>
      57                 :            : #include <linux/rcupdate.h>
      58                 :            : #include <linux/skbuff.h>
      59                 :            : #include <linux/netlink.h>
      60                 :            : #include <linux/init.h>
      61                 :            : #include <linux/list.h>
      62                 :            : #include <linux/slab.h>
      63                 :            : #include <linux/export.h>
      64                 :            : #include <linux/vmalloc.h>
      65                 :            : #include <linux/notifier.h>
      66                 :            : #include <net/net_namespace.h>
      67                 :            : #include <net/ip.h>
      68                 :            : #include <net/protocol.h>
      69                 :            : #include <net/route.h>
      70                 :            : #include <net/tcp.h>
      71                 :            : #include <net/sock.h>
      72                 :            : #include <net/ip_fib.h>
      73                 :            : #include <net/fib_notifier.h>
      74                 :            : #include <trace/events/fib.h>
      75                 :            : #include "fib_lookup.h"
      76                 :            : 
      77                 :          0 : static int call_fib_entry_notifier(struct notifier_block *nb, struct net *net,
      78                 :            :                                    enum fib_event_type event_type, u32 dst,
      79                 :            :                                    int dst_len, struct fib_alias *fa)
      80                 :            : {
      81                 :          0 :         struct fib_entry_notifier_info info = {
      82                 :            :                 .dst = dst,
      83                 :            :                 .dst_len = dst_len,
      84                 :          0 :                 .fi = fa->fa_info,
      85                 :          0 :                 .tos = fa->fa_tos,
      86                 :          0 :                 .type = fa->fa_type,
      87                 :          0 :                 .tb_id = fa->tb_id,
      88                 :            :         };
      89                 :          0 :         return call_fib4_notifier(nb, net, event_type, &info.info);
      90                 :            : }
      91                 :            : 
      92                 :       1863 : static int call_fib_entry_notifiers(struct net *net,
      93                 :            :                                     enum fib_event_type event_type, u32 dst,
      94                 :            :                                     int dst_len, struct fib_alias *fa,
      95                 :            :                                     struct netlink_ext_ack *extack)
      96                 :            : {
      97                 :       9315 :         struct fib_entry_notifier_info info = {
      98                 :            :                 .info.extack = extack,
      99                 :            :                 .dst = dst,
     100                 :            :                 .dst_len = dst_len,
     101                 :       1863 :                 .fi = fa->fa_info,
     102                 :       1863 :                 .tos = fa->fa_tos,
     103                 :       1863 :                 .type = fa->fa_type,
     104                 :       1863 :                 .tb_id = fa->tb_id,
     105                 :            :         };
     106                 :       1863 :         return call_fib4_notifiers(net, event_type, &info.info);
     107                 :            : }
     108                 :            : 
     109                 :            : #define MAX_STAT_DEPTH 32
     110                 :            : 
     111                 :            : #define KEYLENGTH       (8*sizeof(t_key))
     112                 :            : #define KEY_MAX         ((t_key)~0)
     113                 :            : 
     114                 :            : typedef unsigned int t_key;
     115                 :            : 
     116                 :            : #define IS_TRIE(n)      ((n)->pos >= KEYLENGTH)
     117                 :            : #define IS_TNODE(n)     ((n)->bits)
     118                 :            : #define IS_LEAF(n)      (!(n)->bits)
     119                 :            : 
     120                 :            : struct key_vector {
     121                 :            :         t_key key;
     122                 :            :         unsigned char pos;              /* 2log(KEYLENGTH) bits needed */
     123                 :            :         unsigned char bits;             /* 2log(KEYLENGTH) bits needed */
     124                 :            :         unsigned char slen;
     125                 :            :         union {
     126                 :            :                 /* This list pointer if valid if (pos | bits) == 0 (LEAF) */
     127                 :            :                 struct hlist_head leaf;
     128                 :            :                 /* This array is valid if (pos | bits) > 0 (TNODE) */
     129                 :            :                 struct key_vector __rcu *tnode[0];
     130                 :            :         };
     131                 :            : };
     132                 :            : 
     133                 :            : struct tnode {
     134                 :            :         struct rcu_head rcu;
     135                 :            :         t_key empty_children;           /* KEYLENGTH bits needed */
     136                 :            :         t_key full_children;            /* KEYLENGTH bits needed */
     137                 :            :         struct key_vector __rcu *parent;
     138                 :            :         struct key_vector kv[1];
     139                 :            : #define tn_bits kv[0].bits
     140                 :            : };
     141                 :            : 
     142                 :            : #define TNODE_SIZE(n)   offsetof(struct tnode, kv[0].tnode[n])
     143                 :            : #define LEAF_SIZE       TNODE_SIZE(1)
     144                 :            : 
     145                 :            : #ifdef CONFIG_IP_FIB_TRIE_STATS
     146                 :            : struct trie_use_stats {
     147                 :            :         unsigned int gets;
     148                 :            :         unsigned int backtrack;
     149                 :            :         unsigned int semantic_match_passed;
     150                 :            :         unsigned int semantic_match_miss;
     151                 :            :         unsigned int null_node_hit;
     152                 :            :         unsigned int resize_node_skipped;
     153                 :            : };
     154                 :            : #endif
     155                 :            : 
     156                 :            : struct trie_stat {
     157                 :            :         unsigned int totdepth;
     158                 :            :         unsigned int maxdepth;
     159                 :            :         unsigned int tnodes;
     160                 :            :         unsigned int leaves;
     161                 :            :         unsigned int nullpointers;
     162                 :            :         unsigned int prefixes;
     163                 :            :         unsigned int nodesizes[MAX_STAT_DEPTH];
     164                 :            : };
     165                 :            : 
     166                 :            : struct trie {
     167                 :            :         struct key_vector kv[1];
     168                 :            : #ifdef CONFIG_IP_FIB_TRIE_STATS
     169                 :            :         struct trie_use_stats __percpu *stats;
     170                 :            : #endif
     171                 :            : };
     172                 :            : 
     173                 :            : static struct key_vector *resize(struct trie *t, struct key_vector *tn);
     174                 :            : static unsigned int tnode_free_size;
     175                 :            : 
     176                 :            : /*
     177                 :            :  * synchronize_rcu after call_rcu for outstanding dirty memory; it should be
     178                 :            :  * especially useful before resizing the root node with PREEMPT_NONE configs;
     179                 :            :  * the value was obtained experimentally, aiming to avoid visible slowdown.
     180                 :            :  */
     181                 :            : unsigned int sysctl_fib_sync_mem = 512 * 1024;
     182                 :            : unsigned int sysctl_fib_sync_mem_min = 64 * 1024;
     183                 :            : unsigned int sysctl_fib_sync_mem_max = 64 * 1024 * 1024;
     184                 :            : 
     185                 :            : static struct kmem_cache *fn_alias_kmem __ro_after_init;
     186                 :            : static struct kmem_cache *trie_leaf_kmem __ro_after_init;
     187                 :            : 
     188                 :            : static inline struct tnode *tn_info(struct key_vector *kv)
     189                 :            : {
     190                 :            :         return container_of(kv, struct tnode, kv[0]);
     191                 :            : }
     192                 :            : 
     193                 :            : /* caller must hold RTNL */
     194                 :            : #define node_parent(tn) rtnl_dereference(tn_info(tn)->parent)
     195                 :            : #define get_child(tn, i) rtnl_dereference((tn)->tnode[i])
     196                 :            : 
     197                 :            : /* caller must hold RCU read lock or RTNL */
     198                 :            : #define node_parent_rcu(tn) rcu_dereference_rtnl(tn_info(tn)->parent)
     199                 :            : #define get_child_rcu(tn, i) rcu_dereference_rtnl((tn)->tnode[i])
     200                 :            : 
     201                 :            : /* wrapper for rcu_assign_pointer */
     202                 :            : static inline void node_set_parent(struct key_vector *n, struct key_vector *tp)
     203                 :            : {
     204   [ +  -  #  #  :       2691 :         if (n)
                   +  - ]
     205                 :       2691 :                 rcu_assign_pointer(tn_info(n)->parent, tp);
     206                 :            : }
     207                 :            : 
     208                 :            : #define NODE_INIT_PARENT(n, p) RCU_INIT_POINTER(tn_info(n)->parent, p)
     209                 :            : 
     210                 :            : /* This provides us with the number of children in this node, in the case of a
     211                 :            :  * leaf this will return 0 meaning none of the children are accessible.
     212                 :            :  */
     213                 :            : static inline unsigned long child_length(const struct key_vector *tn)
     214                 :            : {
     215                 :      10971 :         return (1ul << tn->bits) & ~(1ul);
     216                 :            : }
     217                 :            : 
     218                 :            : #define get_cindex(key, kv) (((key) ^ (kv)->key) >> (kv)->pos)
     219                 :            : 
     220                 :            : static inline unsigned long get_index(t_key key, struct key_vector *kv)
     221                 :            : {
     222                 :      11592 :         unsigned long index = key ^ kv->key;
     223                 :            : 
     224   [ #  #  #  #  :      11592 :         if ((BITS_PER_LONG <= KEYLENGTH) && (KEYLENGTH == kv->pos))
          #  #  #  #  #  
          #  +  -  +  +  
          #  #  +  +  +  
          -  +  +  +  -  
                   +  - ]
     225                 :            :                 return 0;
     226                 :            : 
     227                 :       9108 :         return index >> kv->pos;
     228                 :            : }
     229                 :            : 
     230                 :            : /* To understand this stuff, an understanding of keys and all their bits is
     231                 :            :  * necessary. Every node in the trie has a key associated with it, but not
     232                 :            :  * all of the bits in that key are significant.
     233                 :            :  *
     234                 :            :  * Consider a node 'n' and its parent 'tp'.
     235                 :            :  *
     236                 :            :  * If n is a leaf, every bit in its key is significant. Its presence is
     237                 :            :  * necessitated by path compression, since during a tree traversal (when
     238                 :            :  * searching for a leaf - unless we are doing an insertion) we will completely
     239                 :            :  * ignore all skipped bits we encounter. Thus we need to verify, at the end of
     240                 :            :  * a potentially successful search, that we have indeed been walking the
     241                 :            :  * correct key path.
     242                 :            :  *
     243                 :            :  * Note that we can never "miss" the correct key in the tree if present by
     244                 :            :  * following the wrong path. Path compression ensures that segments of the key
     245                 :            :  * that are the same for all keys with a given prefix are skipped, but the
     246                 :            :  * skipped part *is* identical for each node in the subtrie below the skipped
     247                 :            :  * bit! trie_insert() in this implementation takes care of that.
     248                 :            :  *
     249                 :            :  * if n is an internal node - a 'tnode' here, the various parts of its key
     250                 :            :  * have many different meanings.
     251                 :            :  *
     252                 :            :  * Example:
     253                 :            :  * _________________________________________________________________
     254                 :            :  * | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
     255                 :            :  * -----------------------------------------------------------------
     256                 :            :  *  31  30  29  28  27  26  25  24  23  22  21  20  19  18  17  16
     257                 :            :  *
     258                 :            :  * _________________________________________________________________
     259                 :            :  * | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
     260                 :            :  * -----------------------------------------------------------------
     261                 :            :  *  15  14  13  12  11  10   9   8   7   6   5   4   3   2   1   0
     262                 :            :  *
     263                 :            :  * tp->pos = 22
     264                 :            :  * tp->bits = 3
     265                 :            :  * n->pos = 13
     266                 :            :  * n->bits = 4
     267                 :            :  *
     268                 :            :  * First, let's just ignore the bits that come before the parent tp, that is
     269                 :            :  * the bits from (tp->pos + tp->bits) to 31. They are *known* but at this
     270                 :            :  * point we do not use them for anything.
     271                 :            :  *
     272                 :            :  * The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
     273                 :            :  * index into the parent's child array. That is, they will be used to find
     274                 :            :  * 'n' among tp's children.
     275                 :            :  *
     276                 :            :  * The bits from (n->pos + n->bits) to (tp->pos - 1) - "S" - are skipped bits
     277                 :            :  * for the node n.
     278                 :            :  *
     279                 :            :  * All the bits we have seen so far are significant to the node n. The rest
     280                 :            :  * of the bits are really not needed or indeed known in n->key.
     281                 :            :  *
     282                 :            :  * The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
     283                 :            :  * n's child array, and will of course be different for each child.
     284                 :            :  *
     285                 :            :  * The rest of the bits, from 0 to (n->pos -1) - "u" - are completely unknown
     286                 :            :  * at this point.
     287                 :            :  */
     288                 :            : 
     289                 :            : static const int halve_threshold = 25;
     290                 :            : static const int inflate_threshold = 50;
     291                 :            : static const int halve_threshold_root = 15;
     292                 :            : static const int inflate_threshold_root = 30;
     293                 :            : 
     294                 :          0 : static void __alias_free_mem(struct rcu_head *head)
     295                 :            : {
     296                 :          0 :         struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
     297                 :          0 :         kmem_cache_free(fn_alias_kmem, fa);
     298                 :          0 : }
     299                 :            : 
     300                 :            : static inline void alias_free_mem_rcu(struct fib_alias *fa)
     301                 :            : {
     302                 :          0 :         call_rcu(&fa->rcu, __alias_free_mem);
     303                 :            : }
     304                 :            : 
     305                 :            : #define TNODE_KMALLOC_MAX \
     306                 :            :         ilog2((PAGE_SIZE - TNODE_SIZE(0)) / sizeof(struct key_vector *))
     307                 :            : #define TNODE_VMALLOC_MAX \
     308                 :            :         ilog2((SIZE_MAX - TNODE_SIZE(0)) / sizeof(struct key_vector *))
     309                 :            : 
     310                 :        828 : static void __node_free_rcu(struct rcu_head *head)
     311                 :            : {
     312                 :            :         struct tnode *n = container_of(head, struct tnode, rcu);
     313                 :            : 
     314         [ -  + ]:        828 :         if (!n->tn_bits)
     315                 :          0 :                 kmem_cache_free(trie_leaf_kmem, n);
     316                 :            :         else
     317                 :        828 :                 kvfree(n);
     318                 :        828 : }
     319                 :            : 
     320                 :            : #define node_free(n) call_rcu(&tn_info(n)->rcu, __node_free_rcu)
     321                 :            : 
     322                 :       1656 : static struct tnode *tnode_alloc(int bits)
     323                 :            : {
     324                 :            :         size_t size;
     325                 :            : 
     326                 :            :         /* verify bits is within bounds */
     327         [ +  - ]:       1656 :         if (bits > TNODE_VMALLOC_MAX)
     328                 :            :                 return NULL;
     329                 :            : 
     330                 :            :         /* determine size and verify it is non-zero and didn't overflow */
     331                 :       1656 :         size = TNODE_SIZE(1ul << bits);
     332                 :            : 
     333         [ +  - ]:       1656 :         if (size <= PAGE_SIZE)
     334                 :       1656 :                 return kzalloc(size, GFP_KERNEL);
     335                 :            :         else
     336                 :          0 :                 return vzalloc(size);
     337                 :            : }
     338                 :            : 
     339                 :            : static inline void empty_child_inc(struct key_vector *n)
     340                 :            : {
     341                 :          0 :         tn_info(n)->empty_children++;
     342                 :            : 
     343         [ #  # ]:          0 :         if (!tn_info(n)->empty_children)
     344                 :          0 :                 tn_info(n)->full_children++;
     345                 :            : }
     346                 :            : 
     347                 :            : static inline void empty_child_dec(struct key_vector *n)
     348                 :            : {
     349         [ -  + ]:       3933 :         if (!tn_info(n)->empty_children)
     350                 :          0 :                 tn_info(n)->full_children--;
     351                 :            : 
     352                 :       3933 :         tn_info(n)->empty_children--;
     353                 :            : }
     354                 :            : 
     355                 :       1449 : static struct key_vector *leaf_new(t_key key, struct fib_alias *fa)
     356                 :            : {
     357                 :            :         struct key_vector *l;
     358                 :            :         struct tnode *kv;
     359                 :            : 
     360                 :       1449 :         kv = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
     361         [ +  - ]:       1449 :         if (!kv)
     362                 :            :                 return NULL;
     363                 :            : 
     364                 :            :         /* initialize key vector */
     365                 :       1449 :         l = kv->kv;
     366                 :       1449 :         l->key = key;
     367                 :       1449 :         l->pos = 0;
     368                 :       1449 :         l->bits = 0;
     369                 :       1449 :         l->slen = fa->fa_slen;
     370                 :            : 
     371                 :            :         /* link leaf to fib alias */
     372                 :       1449 :         INIT_HLIST_HEAD(&l->leaf);
     373                 :       1449 :         hlist_add_head(&fa->fa_list, &l->leaf);
     374                 :            : 
     375                 :       1449 :         return l;
     376                 :            : }
     377                 :            : 
     378                 :       1656 : static struct key_vector *tnode_new(t_key key, int pos, int bits)
     379                 :            : {
     380                 :       1656 :         unsigned int shift = pos + bits;
     381                 :            :         struct key_vector *tn;
     382                 :            :         struct tnode *tnode;
     383                 :            : 
     384                 :            :         /* verify bits and pos their msb bits clear and values are valid */
     385         [ -  + ]:       1656 :         BUG_ON(!bits || (shift > KEYLENGTH));
     386                 :            : 
     387                 :       1656 :         tnode = tnode_alloc(bits);
     388         [ +  - ]:       1656 :         if (!tnode)
     389                 :            :                 return NULL;
     390                 :            : 
     391                 :            :         pr_debug("AT %p s=%zu %zu\n", tnode, TNODE_SIZE(0),
     392                 :            :                  sizeof(struct key_vector *) << bits);
     393                 :            : 
     394         [ -  + ]:       1656 :         if (bits == KEYLENGTH)
     395                 :          0 :                 tnode->full_children = 1;
     396                 :            :         else
     397                 :       1656 :                 tnode->empty_children = 1ul << bits;
     398                 :            : 
     399                 :       1656 :         tn = tnode->kv;
     400         [ +  + ]:       1656 :         tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;
     401                 :       1656 :         tn->pos = pos;
     402                 :       1656 :         tn->bits = bits;
     403                 :       1656 :         tn->slen = pos;
     404                 :            : 
     405                 :       1656 :         return tn;
     406                 :            : }
     407                 :            : 
     408                 :            : /* Check whether a tnode 'n' is "full", i.e. it is an internal node
     409                 :            :  * and no bits are skipped. See discussion in dyntree paper p. 6
     410                 :            :  */
     411                 :            : static inline int tnode_full(struct key_vector *tn, struct key_vector *n)
     412                 :            : {
     413   [ +  -  -  +  :      10350 :         return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);
          #  #  +  +  -  
          +  #  #  +  +  
          -  +  #  #  +  
             -  +  +  +  
                      - ]
     414                 :            : }
     415                 :            : 
     416                 :            : /* Add a child at position i overwriting the old value.
     417                 :            :  * Update the value of full_children and empty_children.
     418                 :            :  */
     419                 :       4347 : static void put_child(struct key_vector *tn, unsigned long i,
     420                 :            :                       struct key_vector *n)
     421                 :            : {
     422                 :       4347 :         struct key_vector *chi = get_child(tn, i);
     423                 :            :         int isfull, wasfull;
     424                 :            : 
     425         [ -  + ]:       4347 :         BUG_ON(i >= child_length(tn));
     426                 :            : 
     427                 :            :         /* update emptyChildren, overflow into fullChildren */
     428         [ -  + ]:       4347 :         if (!n && chi)
     429                 :            :                 empty_child_inc(tn);
     430         [ +  + ]:       4347 :         if (n && !chi)
     431                 :            :                 empty_child_dec(tn);
     432                 :            : 
     433                 :            :         /* update fullChildren */
     434                 :            :         wasfull = tnode_full(tn, chi);
     435                 :            :         isfull = tnode_full(tn, n);
     436                 :            : 
     437         [ -  + ]:       4347 :         if (wasfull && !isfull)
     438                 :          0 :                 tn_info(tn)->full_children--;
     439         [ -  + ]:       4347 :         else if (!wasfull && isfull)
     440                 :          0 :                 tn_info(tn)->full_children++;
     441                 :            : 
     442   [ +  -  +  + ]:       4347 :         if (n && (tn->slen < n->slen))
     443                 :        621 :                 tn->slen = n->slen;
     444                 :            : 
     445                 :       4347 :         rcu_assign_pointer(tn->tnode[i], n);
     446                 :       4347 : }
     447                 :            : 
     448                 :        828 : static void update_children(struct key_vector *tn)
     449                 :            : {
     450                 :            :         unsigned long i;
     451                 :            : 
     452                 :            :         /* update all of the child parent pointers */
     453         [ +  + ]:       5796 :         for (i = child_length(tn); i;) {
     454                 :       4140 :                 struct key_vector *inode = get_child(tn, --i);
     455                 :            : 
     456         [ +  + ]:       4140 :                 if (!inode)
     457                 :       2277 :                         continue;
     458                 :            : 
     459                 :            :                 /* Either update the children of a tnode that
     460                 :            :                  * already belongs to us or update the child
     461                 :            :                  * to point to ourselves.
     462                 :            :                  */
     463         [ -  + ]:       1863 :                 if (node_parent(inode) == tn)
     464                 :          0 :                         update_children(inode);
     465                 :            :                 else
     466                 :            :                         node_set_parent(inode, tn);
     467                 :            :         }
     468                 :        828 : }
     469                 :            : 
     470                 :       3105 : static inline void put_child_root(struct key_vector *tp, t_key key,
     471                 :            :                                   struct key_vector *n)
     472                 :            : {
     473         [ +  + ]:       3105 :         if (IS_TRIE(tp))
     474                 :       1449 :                 rcu_assign_pointer(tp->tnode[0], n);
     475                 :            :         else
     476                 :       1656 :                 put_child(tp, get_index(key, tp), n);
     477                 :       3105 : }
     478                 :            : 
     479                 :            : static inline void tnode_free_init(struct key_vector *tn)
     480                 :            : {
     481                 :        828 :         tn_info(tn)->rcu.next = NULL;
     482                 :            : }
     483                 :            : 
     484                 :            : static inline void tnode_free_append(struct key_vector *tn,
     485                 :            :                                      struct key_vector *n)
     486                 :            : {
     487                 :          0 :         tn_info(n)->rcu.next = tn_info(tn)->rcu.next;
     488                 :          0 :         tn_info(tn)->rcu.next = &tn_info(n)->rcu;
     489                 :            : }
     490                 :            : 
     491                 :        828 : static void tnode_free(struct key_vector *tn)
     492                 :            : {
     493                 :        828 :         struct callback_head *head = &tn_info(tn)->rcu;
     494                 :            : 
     495         [ +  + ]:       2484 :         while (head) {
     496                 :        828 :                 head = head->next;
     497                 :        828 :                 tnode_free_size += TNODE_SIZE(1ul << tn->bits);
     498                 :        828 :                 node_free(tn);
     499                 :            : 
     500                 :        828 :                 tn = container_of(head, struct tnode, rcu)->kv;
     501                 :            :         }
     502                 :            : 
     503         [ -  + ]:        828 :         if (tnode_free_size >= sysctl_fib_sync_mem) {
     504                 :          0 :                 tnode_free_size = 0;
     505                 :          0 :                 synchronize_rcu();
     506                 :            :         }
     507                 :        828 : }
     508                 :            : 
     509                 :        828 : static struct key_vector *replace(struct trie *t,
     510                 :            :                                   struct key_vector *oldtnode,
     511                 :            :                                   struct key_vector *tn)
     512                 :            : {
     513                 :        828 :         struct key_vector *tp = node_parent(oldtnode);
     514                 :            :         unsigned long i;
     515                 :            : 
     516                 :            :         /* setup the parent pointer out of and back into this node */
     517                 :        828 :         NODE_INIT_PARENT(tn, tp);
     518                 :        828 :         put_child_root(tp, tn->key, tn);
     519                 :            : 
     520                 :            :         /* update all of the child parent pointers */
     521                 :        828 :         update_children(tn);
     522                 :            : 
     523                 :            :         /* all pointers should be clean so we are done */
     524                 :        828 :         tnode_free(oldtnode);
     525                 :            : 
     526                 :            :         /* resize children now that oldtnode is freed */
     527         [ +  + ]:       5796 :         for (i = child_length(tn); i;) {
     528                 :       4140 :                 struct key_vector *inode = get_child(tn, --i);
     529                 :            : 
     530                 :            :                 /* resize child node */
     531         [ -  + ]:       4140 :                 if (tnode_full(tn, inode))
     532                 :          0 :                         tn = resize(t, inode);
     533                 :            :         }
     534                 :            : 
     535                 :        828 :         return tp;
     536                 :            : }
     537                 :            : 
     538                 :        828 : static struct key_vector *inflate(struct trie *t,
     539                 :            :                                   struct key_vector *oldtnode)
     540                 :            : {
     541                 :            :         struct key_vector *tn;
     542                 :            :         unsigned long i;
     543                 :            :         t_key m;
     544                 :            : 
     545                 :            :         pr_debug("In inflate\n");
     546                 :            : 
     547                 :        828 :         tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1);
     548         [ +  - ]:        828 :         if (!tn)
     549                 :            :                 goto notnode;
     550                 :            : 
     551                 :            :         /* prepare oldtnode to be freed */
     552                 :            :         tnode_free_init(oldtnode);
     553                 :            : 
     554                 :            :         /* Assemble all of the pointers in our cluster, in this case that
     555                 :            :          * represents all of the pointers out of our allocated nodes that
     556                 :            :          * point to existing tnodes and the links between our allocated
     557                 :            :          * nodes.
     558                 :            :          */
     559         [ +  + ]:       3726 :         for (i = child_length(oldtnode), m = 1u << tn->pos; i;) {
     560                 :       2070 :                 struct key_vector *inode = get_child(oldtnode, --i);
     561                 :            :                 struct key_vector *node0, *node1;
     562                 :            :                 unsigned long j, k;
     563                 :            : 
     564                 :            :                 /* An empty child */
     565         [ +  + ]:       2070 :                 if (!inode)
     566                 :        207 :                         continue;
     567                 :            : 
     568                 :            :                 /* A leaf or an internal node with skipped bits */
     569         [ +  - ]:       1863 :                 if (!tnode_full(oldtnode, inode)) {
     570                 :       3726 :                         put_child(tn, get_index(inode->key, tn), inode);
     571                 :       1863 :                         continue;
     572                 :            :                 }
     573                 :            : 
     574                 :            :                 /* drop the node in the old tnode free list */
     575                 :            :                 tnode_free_append(oldtnode, inode);
     576                 :            : 
     577                 :            :                 /* An internal node with two children */
     578         [ #  # ]:          0 :                 if (inode->bits == 1) {
     579                 :          0 :                         put_child(tn, 2 * i + 1, get_child(inode, 1));
     580                 :          0 :                         put_child(tn, 2 * i, get_child(inode, 0));
     581                 :          0 :                         continue;
     582                 :            :                 }
     583                 :            : 
     584                 :            :                 /* We will replace this node 'inode' with two new
     585                 :            :                  * ones, 'node0' and 'node1', each with half of the
     586                 :            :                  * original children. The two new nodes will have
     587                 :            :                  * a position one bit further down the key and this
     588                 :            :                  * means that the "significant" part of their keys
     589                 :            :                  * (see the discussion near the top of this file)
     590                 :            :                  * will differ by one bit, which will be "0" in
     591                 :            :                  * node0's key and "1" in node1's key. Since we are
     592                 :            :                  * moving the key position by one step, the bit that
     593                 :            :                  * we are moving away from - the bit at position
     594                 :            :                  * (tn->pos) - is the one that will differ between
     595                 :            :                  * node0 and node1. So... we synthesize that bit in the
     596                 :            :                  * two new keys.
     597                 :            :                  */
     598                 :          0 :                 node1 = tnode_new(inode->key | m, inode->pos, inode->bits - 1);
     599         [ #  # ]:          0 :                 if (!node1)
     600                 :            :                         goto nomem;
     601                 :          0 :                 node0 = tnode_new(inode->key, inode->pos, inode->bits - 1);
     602                 :            : 
     603                 :            :                 tnode_free_append(tn, node1);
     604         [ #  # ]:          0 :                 if (!node0)
     605                 :            :                         goto nomem;
     606                 :            :                 tnode_free_append(tn, node0);
     607                 :            : 
     608                 :            :                 /* populate child pointers in new nodes */
     609         [ #  # ]:          0 :                 for (k = child_length(inode), j = k / 2; j;) {
     610                 :          0 :                         put_child(node1, --j, get_child(inode, --k));
     611                 :          0 :                         put_child(node0, j, get_child(inode, j));
     612                 :          0 :                         put_child(node1, --j, get_child(inode, --k));
     613                 :          0 :                         put_child(node0, j, get_child(inode, j));
     614                 :            :                 }
     615                 :            : 
     616                 :            :                 /* link new nodes to parent */
     617                 :          0 :                 NODE_INIT_PARENT(node1, tn);
     618                 :            :                 NODE_INIT_PARENT(node0, tn);
     619                 :            : 
     620                 :            :                 /* link parent to nodes */
     621                 :          0 :                 put_child(tn, 2 * i + 1, node1);
     622                 :          0 :                 put_child(tn, 2 * i, node0);
     623                 :            :         }
     624                 :            : 
     625                 :            :         /* setup the parent pointers into and out of this node */
     626                 :        828 :         return replace(t, oldtnode, tn);
     627                 :            : nomem:
     628                 :            :         /* all pointers should be clean so we are done */
     629                 :          0 :         tnode_free(tn);
     630                 :            : notnode:
     631                 :            :         return NULL;
     632                 :            : }
     633                 :            : 
     634                 :          0 : static struct key_vector *halve(struct trie *t,
     635                 :            :                                 struct key_vector *oldtnode)
     636                 :            : {
     637                 :            :         struct key_vector *tn;
     638                 :            :         unsigned long i;
     639                 :            : 
     640                 :            :         pr_debug("In halve\n");
     641                 :            : 
     642                 :          0 :         tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1);
     643         [ #  # ]:          0 :         if (!tn)
     644                 :            :                 goto notnode;
     645                 :            : 
     646                 :            :         /* prepare oldtnode to be freed */
     647                 :            :         tnode_free_init(oldtnode);
     648                 :            : 
     649                 :            :         /* Assemble all of the pointers in our cluster, in this case that
     650                 :            :          * represents all of the pointers out of our allocated nodes that
     651                 :            :          * point to existing tnodes and the links between our allocated
     652                 :            :          * nodes.
     653                 :            :          */
     654         [ #  # ]:          0 :         for (i = child_length(oldtnode); i;) {
     655                 :          0 :                 struct key_vector *node1 = get_child(oldtnode, --i);
     656                 :          0 :                 struct key_vector *node0 = get_child(oldtnode, --i);
     657                 :            :                 struct key_vector *inode;
     658                 :            : 
     659                 :            :                 /* At least one of the children is empty */
     660         [ #  # ]:          0 :                 if (!node1 || !node0) {
     661         [ #  # ]:          0 :                         put_child(tn, i / 2, node1 ? : node0);
     662                 :          0 :                         continue;
     663                 :            :                 }
     664                 :            : 
     665                 :            :                 /* Two nonempty children */
     666                 :          0 :                 inode = tnode_new(node0->key, oldtnode->pos, 1);
     667         [ #  # ]:          0 :                 if (!inode)
     668                 :            :                         goto nomem;
     669                 :            :                 tnode_free_append(tn, inode);
     670                 :            : 
     671                 :            :                 /* initialize pointers out of node */
     672                 :          0 :                 put_child(inode, 1, node1);
     673                 :          0 :                 put_child(inode, 0, node0);
     674                 :          0 :                 NODE_INIT_PARENT(inode, tn);
     675                 :            : 
     676                 :            :                 /* link parent to node */
     677                 :          0 :                 put_child(tn, i / 2, inode);
     678                 :            :         }
     679                 :            : 
     680                 :            :         /* setup the parent pointers into and out of this node */
     681                 :          0 :         return replace(t, oldtnode, tn);
     682                 :            : nomem:
     683                 :            :         /* all pointers should be clean so we are done */
     684                 :          0 :         tnode_free(tn);
     685                 :            : notnode:
     686                 :            :         return NULL;
     687                 :            : }
     688                 :            : 
     689                 :          0 : static struct key_vector *collapse(struct trie *t,
     690                 :            :                                    struct key_vector *oldtnode)
     691                 :            : {
     692                 :            :         struct key_vector *n, *tp;
     693                 :            :         unsigned long i;
     694                 :            : 
     695                 :            :         /* scan the tnode looking for that one child that might still exist */
     696         [ #  # ]:          0 :         for (n = NULL, i = child_length(oldtnode); !n && i;)
     697                 :          0 :                 n = get_child(oldtnode, --i);
     698                 :            : 
     699                 :            :         /* compress one level */
     700                 :          0 :         tp = node_parent(oldtnode);
     701                 :          0 :         put_child_root(tp, oldtnode->key, n);
     702                 :            :         node_set_parent(n, tp);
     703                 :            : 
     704                 :            :         /* drop dead node */
     705                 :          0 :         node_free(oldtnode);
     706                 :            : 
     707                 :          0 :         return tp;
     708                 :            : }
     709                 :            : 
     710                 :          0 : static unsigned char update_suffix(struct key_vector *tn)
     711                 :            : {
     712                 :          0 :         unsigned char slen = tn->pos;
     713                 :            :         unsigned long stride, i;
     714                 :            :         unsigned char slen_max;
     715                 :            : 
     716                 :            :         /* only vector 0 can have a suffix length greater than or equal to
     717                 :            :          * tn->pos + tn->bits, the second highest node will have a suffix
     718                 :            :          * length at most of tn->pos + tn->bits - 1
     719                 :            :          */
     720         [ #  # ]:          0 :         slen_max = min_t(unsigned char, tn->pos + tn->bits - 1, tn->slen);
     721                 :            : 
     722                 :            :         /* search though the list of children looking for nodes that might
     723                 :            :          * have a suffix greater than the one we currently have.  This is
     724                 :            :          * why we start with a stride of 2 since a stride of 1 would
     725                 :            :          * represent the nodes with suffix length equal to tn->pos
     726                 :            :          */
     727         [ #  # ]:          0 :         for (i = 0, stride = 0x2ul ; i < child_length(tn); i += stride) {
     728                 :          0 :                 struct key_vector *n = get_child(tn, i);
     729                 :            : 
     730   [ #  #  #  # ]:          0 :                 if (!n || (n->slen <= slen))
     731                 :          0 :                         continue;
     732                 :            : 
     733                 :            :                 /* update stride and slen based on new value */
     734                 :          0 :                 stride <<= (n->slen - slen);
     735                 :            :                 slen = n->slen;
     736                 :          0 :                 i &= ~(stride - 1);
     737                 :            : 
     738                 :            :                 /* stop searching if we have hit the maximum possible value */
     739         [ #  # ]:          0 :                 if (slen >= slen_max)
     740                 :            :                         break;
     741                 :            :         }
     742                 :            : 
     743                 :          0 :         tn->slen = slen;
     744                 :            : 
     745                 :          0 :         return slen;
     746                 :            : }
     747                 :            : 
     748                 :            : /* From "Implementing a dynamic compressed trie" by Stefan Nilsson of
     749                 :            :  * the Helsinki University of Technology and Matti Tikkanen of Nokia
     750                 :            :  * Telecommunications, page 6:
     751                 :            :  * "A node is doubled if the ratio of non-empty children to all
     752                 :            :  * children in the *doubled* node is at least 'high'."
     753                 :            :  *
     754                 :            :  * 'high' in this instance is the variable 'inflate_threshold'. It
     755                 :            :  * is expressed as a percentage, so we multiply it with
     756                 :            :  * child_length() and instead of multiplying by 2 (since the
     757                 :            :  * child array will be doubled by inflate()) and multiplying
     758                 :            :  * the left-hand side by 100 (to handle the percentage thing) we
     759                 :            :  * multiply the left-hand side by 50.
     760                 :            :  *
     761                 :            :  * The left-hand side may look a bit weird: child_length(tn)
     762                 :            :  * - tn->empty_children is of course the number of non-null children
     763                 :            :  * in the current node. tn->full_children is the number of "full"
     764                 :            :  * children, that is non-null tnodes with a skip value of 0.
     765                 :            :  * All of those will be doubled in the resulting inflated tnode, so
     766                 :            :  * we just count them one extra time here.
     767                 :            :  *
     768                 :            :  * A clearer way to write this would be:
     769                 :            :  *
     770                 :            :  * to_be_doubled = tn->full_children;
     771                 :            :  * not_to_be_doubled = child_length(tn) - tn->empty_children -
     772                 :            :  *     tn->full_children;
     773                 :            :  *
     774                 :            :  * new_child_length = child_length(tn) * 2;
     775                 :            :  *
     776                 :            :  * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
     777                 :            :  *      new_child_length;
     778                 :            :  * if (new_fill_factor >= inflate_threshold)
     779                 :            :  *
     780                 :            :  * ...and so on, tho it would mess up the while () loop.
     781                 :            :  *
     782                 :            :  * anyway,
     783                 :            :  * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
     784                 :            :  *      inflate_threshold
     785                 :            :  *
     786                 :            :  * avoid a division:
     787                 :            :  * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
     788                 :            :  *      inflate_threshold * new_child_length
     789                 :            :  *
     790                 :            :  * expand not_to_be_doubled and to_be_doubled, and shorten:
     791                 :            :  * 100 * (child_length(tn) - tn->empty_children +
     792                 :            :  *    tn->full_children) >= inflate_threshold * new_child_length
     793                 :            :  *
     794                 :            :  * expand new_child_length:
     795                 :            :  * 100 * (child_length(tn) - tn->empty_children +
     796                 :            :  *    tn->full_children) >=
     797                 :            :  *      inflate_threshold * child_length(tn) * 2
     798                 :            :  *
     799                 :            :  * shorten again:
     800                 :            :  * 50 * (tn->full_children + child_length(tn) -
     801                 :            :  *    tn->empty_children) >= inflate_threshold *
     802                 :            :  *    child_length(tn)
     803                 :            :  *
     804                 :            :  */
     805                 :       2484 : static inline bool should_inflate(struct key_vector *tp, struct key_vector *tn)
     806                 :            : {
     807                 :            :         unsigned long used = child_length(tn);
     808                 :            :         unsigned long threshold = used;
     809                 :            : 
     810                 :            :         /* Keep root node larger */
     811         [ +  + ]:       2484 :         threshold *= IS_TRIE(tp) ? inflate_threshold_root : inflate_threshold;
     812                 :       2484 :         used -= tn_info(tn)->empty_children;
     813                 :       2484 :         used += tn_info(tn)->full_children;
     814                 :            : 
     815                 :            :         /* if bits == KEYLENGTH then pos = 0, and will fail below */
     816                 :            : 
     817   [ +  -  +  +  :       2484 :         return (used > 1) && tn->pos && ((50 * used) >= threshold);
                   +  + ]
     818                 :            : }
     819                 :            : 
     820                 :            : static inline bool should_halve(struct key_vector *tp, struct key_vector *tn)
     821                 :            : {
     822                 :            :         unsigned long used = child_length(tn);
     823                 :            :         unsigned long threshold = used;
     824                 :            : 
     825                 :            :         /* Keep root node larger */
     826         [ +  + ]:        828 :         threshold *= IS_TRIE(tp) ? halve_threshold_root : halve_threshold;
     827                 :        828 :         used -= tn_info(tn)->empty_children;
     828                 :            : 
     829                 :            :         /* if bits == KEYLENGTH then used = 100% on wrap, and will fail below */
     830                 :            : 
     831   [ +  -  +  +  :        828 :         return (used > 1) && (tn->bits > 1) && ((100 * used) < threshold);
                   +  - ]
     832                 :            : }
     833                 :            : 
     834                 :            : static inline bool should_collapse(struct key_vector *tn)
     835                 :            : {
     836                 :            :         unsigned long used = child_length(tn);
     837                 :            : 
     838                 :        828 :         used -= tn_info(tn)->empty_children;
     839                 :            : 
     840                 :            :         /* account for bits == KEYLENGTH case */
     841   [ -  +  #  # ]:        828 :         if ((tn->bits == KEYLENGTH) && tn_info(tn)->full_children)
     842                 :          0 :                 used -= KEY_MAX;
     843                 :            : 
     844                 :            :         /* One child or none, time to drop us from the trie */
     845                 :            :         return used < 2;
     846                 :            : }
     847                 :            : 
     848                 :            : #define MAX_WORK 10
     849                 :       1656 : static struct key_vector *resize(struct trie *t, struct key_vector *tn)
     850                 :            : {
     851                 :            : #ifdef CONFIG_IP_FIB_TRIE_STATS
     852                 :            :         struct trie_use_stats __percpu *stats = t->stats;
     853                 :            : #endif
     854                 :       1656 :         struct key_vector *tp = node_parent(tn);
     855                 :       1656 :         unsigned long cindex = get_index(tn->key, tp);
     856                 :            :         int max_work = MAX_WORK;
     857                 :            : 
     858                 :            :         pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
     859                 :            :                  tn, inflate_threshold, halve_threshold);
     860                 :            : 
     861                 :            :         /* track the tnode via the pointer from the parent instead of
     862                 :            :          * doing it ourselves.  This way we can let RCU fully do its
     863                 :            :          * thing without us interfering
     864                 :            :          */
     865         [ +  - ]:       1656 :         BUG_ON(tn != get_child(tp, cindex));
     866                 :            : 
     867                 :            :         /* Double as long as the resulting node has a number of
     868                 :            :          * nonempty nodes that are above the threshold.
     869                 :            :          */
     870   [ +  +  +  - ]:       2484 :         while (should_inflate(tp, tn) && max_work) {
     871                 :        828 :                 tp = inflate(t, tn);
     872         [ +  - ]:        828 :                 if (!tp) {
     873                 :            : #ifdef CONFIG_IP_FIB_TRIE_STATS
     874                 :            :                         this_cpu_inc(stats->resize_node_skipped);
     875                 :            : #endif
     876                 :            :                         break;
     877                 :            :                 }
     878                 :            : 
     879                 :        828 :                 max_work--;
     880                 :        828 :                 tn = get_child(tp, cindex);
     881                 :            :         }
     882                 :            : 
     883                 :            :         /* update parent in case inflate failed */
     884                 :       1656 :         tp = node_parent(tn);
     885                 :            : 
     886                 :            :         /* Return if at least one inflate is run */
     887         [ +  + ]:       1656 :         if (max_work != MAX_WORK)
     888                 :            :                 return tp;
     889                 :            : 
     890                 :            :         /* Halve as long as the number of empty children in this
     891                 :            :          * node is above threshold.
     892                 :            :          */
     893   [ -  +  #  # ]:        828 :         while (should_halve(tp, tn) && max_work) {
     894                 :          0 :                 tp = halve(t, tn);
     895         [ #  # ]:          0 :                 if (!tp) {
     896                 :            : #ifdef CONFIG_IP_FIB_TRIE_STATS
     897                 :            :                         this_cpu_inc(stats->resize_node_skipped);
     898                 :            : #endif
     899                 :            :                         break;
     900                 :            :                 }
     901                 :            : 
     902                 :          0 :                 max_work--;
     903                 :          0 :                 tn = get_child(tp, cindex);
     904                 :            :         }
     905                 :            : 
     906                 :            :         /* Only one child remains */
     907         [ -  + ]:        828 :         if (should_collapse(tn))
     908                 :          0 :                 return collapse(t, tn);
     909                 :            : 
     910                 :            :         /* update parent in case halve failed */
     911                 :        828 :         return node_parent(tn);
     912                 :            : }
     913                 :            : 
     914                 :          0 : static void node_pull_suffix(struct key_vector *tn, unsigned char slen)
     915                 :            : {
     916                 :          0 :         unsigned char node_slen = tn->slen;
     917                 :            : 
     918   [ #  #  #  # ]:          0 :         while ((node_slen > tn->pos) && (node_slen > slen)) {
     919                 :          0 :                 slen = update_suffix(tn);
     920         [ #  # ]:          0 :                 if (node_slen == slen)
     921                 :            :                         break;
     922                 :            : 
     923                 :          0 :                 tn = node_parent(tn);
     924                 :          0 :                 node_slen = tn->slen;
     925                 :            :         }
     926                 :          0 : }
     927                 :            : 
     928                 :            : static void node_push_suffix(struct key_vector *tn, unsigned char slen)
     929                 :            : {
     930   [ +  +  +  + ]:       2277 :         while (tn->slen < slen) {
     931                 :        621 :                 tn->slen = slen;
     932                 :        621 :                 tn = node_parent(tn);
     933                 :            :         }
     934                 :            : }
     935                 :            : 
     936                 :            : /* rcu_read_lock needs to be hold by caller from readside */
     937                 :            : static struct key_vector *fib_find_node(struct trie *t,
     938                 :            :                                         struct key_vector **tp, u32 key)
     939                 :            : {
     940                 :       2277 :         struct key_vector *pn, *n = t->kv;
     941                 :            :         unsigned long index = 0;
     942                 :            : 
     943                 :            :         do {
     944                 :            :                 pn = n;
     945                 :       8280 :                 n = get_child_rcu(n, index);
     946                 :            : 
     947   [ #  #  #  #  :       4140 :                 if (!n)
                   +  + ]
     948                 :            :                         break;
     949                 :            : 
     950                 :       3519 :                 index = get_cindex(key, n);
     951                 :            : 
     952                 :            :                 /* This bit of code is a bit tricky but it combines multiple
     953                 :            :                  * checks into a single check.  The prefix consists of the
     954                 :            :                  * prefix plus zeros for the bits in the cindex. The index
     955                 :            :                  * is the difference between the key and this value.  From
     956                 :            :                  * this we can actually derive several pieces of data.
     957                 :            :                  *   if (index >= (1ul << bits))
     958                 :            :                  *     we have a mismatch in skip bits and failed
     959                 :            :                  *   else
     960                 :            :                  *     we know the value is cindex
     961                 :            :                  *
     962                 :            :                  * This check is safe even if bits == KEYLENGTH due to the
     963                 :            :                  * fact that we can only allocate a node with 32 bits if a
     964                 :            :                  * long is greater than 32 bits.
     965                 :            :                  */
     966   [ #  #  #  #  :       3519 :                 if (index >= (1ul << n->bits)) {
                   +  + ]
     967                 :            :                         n = NULL;
     968                 :            :                         break;
     969                 :            :                 }
     970                 :            : 
     971                 :            :                 /* keep searching until we find a perfect match leaf or NULL */
     972   [ #  #  #  #  :       2691 :         } while (IS_TNODE(n));
                   +  + ]
     973                 :            : 
     974                 :       2277 :         *tp = pn;
     975                 :            : 
     976                 :            :         return n;
     977                 :            : }
     978                 :            : 
     979                 :            : /* Return the first fib alias matching TOS with
     980                 :            :  * priority less than or equal to PRIO.
     981                 :            :  */
     982                 :        828 : static struct fib_alias *fib_find_alias(struct hlist_head *fah, u8 slen,
     983                 :            :                                         u8 tos, u32 prio, u32 tb_id)
     984                 :            : {
     985                 :            :         struct fib_alias *fa;
     986                 :            : 
     987         [ +  - ]:        828 :         if (!fah)
     988                 :            :                 return NULL;
     989                 :            : 
     990   [ +  -  -  +  :       1035 :         hlist_for_each_entry(fa, fah, fa_list) {
                   +  + ]
     991         [ +  + ]:        828 :                 if (fa->fa_slen < slen)
     992                 :        207 :                         continue;
     993         [ +  + ]:        621 :                 if (fa->fa_slen != slen)
     994                 :            :                         break;
     995         [ -  + ]:        414 :                 if (fa->tb_id > tb_id)
     996                 :          0 :                         continue;
     997         [ +  - ]:        414 :                 if (fa->tb_id != tb_id)
     998                 :            :                         break;
     999         [ -  + ]:        414 :                 if (fa->fa_tos > tos)
    1000                 :          0 :                         continue;
    1001   [ -  +  #  # ]:        414 :                 if (fa->fa_info->fib_priority >= prio || fa->fa_tos < tos)
    1002                 :        414 :                         return fa;
    1003                 :            :         }
    1004                 :            : 
    1005                 :            :         return NULL;
    1006                 :            : }
    1007                 :            : 
    1008                 :            : static void trie_rebalance(struct trie *t, struct key_vector *tn)
    1009                 :            : {
    1010   [ #  #  +  + ]:       3105 :         while (!IS_TRIE(tn))
    1011                 :       1656 :                 tn = resize(t, tn);
    1012                 :            : }
    1013                 :            : 
    1014                 :       1449 : static int fib_insert_node(struct trie *t, struct key_vector *tp,
    1015                 :            :                            struct fib_alias *new, t_key key)
    1016                 :            : {
    1017                 :            :         struct key_vector *n, *l;
    1018                 :            : 
    1019                 :       1449 :         l = leaf_new(key, new);
    1020         [ +  - ]:       1449 :         if (!l)
    1021                 :            :                 goto noleaf;
    1022                 :            : 
    1023                 :            :         /* retrieve child from parent node */
    1024                 :       1449 :         n = get_child(tp, get_index(key, tp));
    1025                 :            : 
    1026                 :            :         /* Case 2: n is a LEAF or a TNODE and the key doesn't match.
    1027                 :            :          *
    1028                 :            :          *  Add a new tnode here
    1029                 :            :          *  first tnode need some special handling
    1030                 :            :          *  leaves us in position for handling as case 3
    1031                 :            :          */
    1032         [ +  + ]:       1449 :         if (n) {
    1033                 :            :                 struct key_vector *tn;
    1034                 :            : 
    1035                 :       1656 :                 tn = tnode_new(key, __fls(key ^ n->key), 1);
    1036         [ +  - ]:        828 :                 if (!tn)
    1037                 :            :                         goto notnode;
    1038                 :            : 
    1039                 :            :                 /* initialize routes out of node */
    1040                 :        828 :                 NODE_INIT_PARENT(tn, tp);
    1041                 :        828 :                 put_child(tn, get_index(key, tn) ^ 1, n);
    1042                 :            : 
    1043                 :            :                 /* start adding routes into the node */
    1044                 :        828 :                 put_child_root(tp, key, tn);
    1045                 :            :                 node_set_parent(n, tn);
    1046                 :            : 
    1047                 :            :                 /* parent now has a NULL spot where the leaf can go */
    1048                 :            :                 tp = tn;
    1049                 :            :         }
    1050                 :            : 
    1051                 :            :         /* Case 3: n is NULL, and will just insert a new leaf */
    1052                 :       1449 :         node_push_suffix(tp, new->fa_slen);
    1053                 :       1449 :         NODE_INIT_PARENT(l, tp);
    1054                 :       1449 :         put_child_root(tp, key, l);
    1055                 :            :         trie_rebalance(t, tp);
    1056                 :            : 
    1057                 :            :         return 0;
    1058                 :            : notnode:
    1059                 :          0 :         node_free(l);
    1060                 :            : noleaf:
    1061                 :            :         return -ENOMEM;
    1062                 :            : }
    1063                 :            : 
    1064                 :            : /* fib notifier for ADD is sent before calling fib_insert_alias with
    1065                 :            :  * the expectation that the only possible failure ENOMEM
    1066                 :            :  */
    1067                 :       1863 : static int fib_insert_alias(struct trie *t, struct key_vector *tp,
    1068                 :            :                             struct key_vector *l, struct fib_alias *new,
    1069                 :            :                             struct fib_alias *fa, t_key key)
    1070                 :            : {
    1071         [ +  + ]:       1863 :         if (!l)
    1072                 :       1449 :                 return fib_insert_node(t, tp, new, key);
    1073                 :            : 
    1074         [ -  + ]:        414 :         if (fa) {
    1075                 :          0 :                 hlist_add_before_rcu(&new->fa_list, &fa->fa_list);
    1076                 :            :         } else {
    1077                 :            :                 struct fib_alias *last;
    1078                 :            : 
    1079   [ +  -  -  +  :        621 :                 hlist_for_each_entry(last, &l->leaf, fa_list) {
                   +  + ]
    1080         [ +  + ]:        414 :                         if (new->fa_slen < last->fa_slen)
    1081                 :            :                                 break;
    1082   [ -  +  #  # ]:        207 :                         if ((new->fa_slen == last->fa_slen) &&
    1083                 :          0 :                             (new->tb_id > last->tb_id))
    1084                 :            :                                 break;
    1085                 :            :                         fa = last;
    1086                 :            :                 }
    1087                 :            : 
    1088         [ +  + ]:        414 :                 if (fa)
    1089                 :        207 :                         hlist_add_behind_rcu(&new->fa_list, &fa->fa_list);
    1090                 :            :                 else
    1091                 :        207 :                         hlist_add_head_rcu(&new->fa_list, &l->leaf);
    1092                 :            :         }
    1093                 :            : 
    1094                 :            :         /* if we added to the tail node then we need to update slen */
    1095         [ +  + ]:        414 :         if (l->slen < new->fa_slen) {
    1096                 :        207 :                 l->slen = new->fa_slen;
    1097                 :        207 :                 node_push_suffix(tp, new->fa_slen);
    1098                 :            :         }
    1099                 :            : 
    1100                 :            :         return 0;
    1101                 :            : }
    1102                 :            : 
    1103                 :            : static bool fib_valid_key_len(u32 key, u8 plen, struct netlink_ext_ack *extack)
    1104                 :            : {
    1105   [ #  #  -  + ]:       2277 :         if (plen > KEYLENGTH) {
    1106   [ #  #  #  # ]:          0 :                 NL_SET_ERR_MSG(extack, "Invalid prefix length");
    1107                 :            :                 return false;
    1108                 :            :         }
    1109                 :            : 
    1110   [ #  #  #  #  :       2277 :         if ((plen < KEYLENGTH) && (key << plen)) {
             +  +  -  + ]
    1111   [ #  #  #  # ]:          0 :                 NL_SET_ERR_MSG(extack,
    1112                 :            :                                "Invalid prefix for given prefix length");
    1113                 :            :                 return false;
    1114                 :            :         }
    1115                 :            : 
    1116                 :            :         return true;
    1117                 :            : }
    1118                 :            : 
    1119                 :            : /* Caller must hold RTNL. */
    1120                 :       2277 : int fib_table_insert(struct net *net, struct fib_table *tb,
    1121                 :            :                      struct fib_config *cfg, struct netlink_ext_ack *extack)
    1122                 :            : {
    1123                 :            :         enum fib_event_type event = FIB_EVENT_ENTRY_ADD;
    1124                 :       2277 :         struct trie *t = (struct trie *)tb->tb_data;
    1125                 :            :         struct fib_alias *fa, *new_fa;
    1126                 :            :         struct key_vector *l, *tp;
    1127                 :            :         u16 nlflags = NLM_F_EXCL;
    1128                 :            :         struct fib_info *fi;
    1129                 :       2277 :         u8 plen = cfg->fc_dst_len;
    1130                 :       2277 :         u8 slen = KEYLENGTH - plen;
    1131                 :       2277 :         u8 tos = cfg->fc_tos;
    1132                 :            :         u32 key;
    1133                 :            :         int err;
    1134                 :            : 
    1135                 :       2277 :         key = ntohl(cfg->fc_dst);
    1136                 :            : 
    1137         [ +  - ]:       2277 :         if (!fib_valid_key_len(key, plen, extack))
    1138                 :            :                 return -EINVAL;
    1139                 :            : 
    1140                 :            :         pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
    1141                 :            : 
    1142                 :       2277 :         fi = fib_create_info(cfg, extack);
    1143         [ -  + ]:       2277 :         if (IS_ERR(fi)) {
    1144                 :            :                 err = PTR_ERR(fi);
    1145                 :          0 :                 goto err;
    1146                 :            :         }
    1147                 :            : 
    1148                 :            :         l = fib_find_node(t, &tp, key);
    1149                 :        828 :         fa = l ? fib_find_alias(&l->leaf, slen, tos, fi->fib_priority,
    1150         [ +  + ]:       3105 :                                 tb->tb_id) : NULL;
    1151                 :            : 
    1152                 :            :         /* Now fa, if non-NULL, points to the first fib alias
    1153                 :            :          * with the same keys [prefix,tos,priority], if such key already
    1154                 :            :          * exists or to the node before which we will insert new one.
    1155                 :            :          *
    1156                 :            :          * If fa is NULL, we will need to allocate a new one and
    1157                 :            :          * insert to the tail of the section matching the suffix length
    1158                 :            :          * of the new alias.
    1159                 :            :          */
    1160                 :            : 
    1161   [ +  +  +  -  :       2691 :         if (fa && fa->fa_tos == tos &&
                   +  - ]
    1162                 :        414 :             fa->fa_info->fib_priority == fi->fib_priority) {
    1163                 :            :                 struct fib_alias *fa_first, *fa_match;
    1164                 :            : 
    1165                 :            :                 err = -EEXIST;
    1166         [ +  - ]:        414 :                 if (cfg->fc_nlflags & NLM_F_EXCL)
    1167                 :            :                         goto out;
    1168                 :            : 
    1169                 :            :                 nlflags &= ~NLM_F_EXCL;
    1170                 :            : 
    1171                 :            :                 /* We have 2 goals:
    1172                 :            :                  * 1. Find exact match for type, scope, fib_info to avoid
    1173                 :            :                  * duplicate routes
    1174                 :            :                  * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
    1175                 :            :                  */
    1176                 :            :                 fa_match = NULL;
    1177                 :            :                 fa_first = fa;
    1178   [ #  #  +  - ]:          0 :                 hlist_for_each_entry_from(fa, fa_list) {
    1179   [ +  -  +  - ]:        828 :                         if ((fa->fa_slen != slen) ||
    1180         [ +  - ]:        828 :                             (fa->tb_id != tb->tb_id) ||
    1181                 :        414 :                             (fa->fa_tos != tos))
    1182                 :            :                                 break;
    1183         [ +  - ]:        414 :                         if (fa->fa_info->fib_priority != fi->fib_priority)
    1184                 :            :                                 break;
    1185   [ +  -  +  - ]:        414 :                         if (fa->fa_type == cfg->fc_type &&
    1186                 :            :                             fa->fa_info == fi) {
    1187                 :        414 :                                 fa_match = fa;
    1188                 :        414 :                                 break;
    1189                 :            :                         }
    1190                 :            :                 }
    1191                 :            : 
    1192         [ -  + ]:        414 :                 if (cfg->fc_nlflags & NLM_F_REPLACE) {
    1193                 :            :                         struct fib_info *fi_drop;
    1194                 :            :                         u8 state;
    1195                 :            : 
    1196                 :            :                         nlflags |= NLM_F_REPLACE;
    1197                 :            :                         fa = fa_first;
    1198         [ #  # ]:          0 :                         if (fa_match) {
    1199         [ #  # ]:          0 :                                 if (fa == fa_match)
    1200                 :            :                                         err = 0;
    1201                 :            :                                 goto out;
    1202                 :            :                         }
    1203                 :            :                         err = -ENOBUFS;
    1204                 :          0 :                         new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
    1205         [ #  # ]:          0 :                         if (!new_fa)
    1206                 :            :                                 goto out;
    1207                 :            : 
    1208                 :          0 :                         fi_drop = fa->fa_info;
    1209                 :          0 :                         new_fa->fa_tos = fa->fa_tos;
    1210                 :          0 :                         new_fa->fa_info = fi;
    1211                 :          0 :                         new_fa->fa_type = cfg->fc_type;
    1212                 :          0 :                         state = fa->fa_state;
    1213                 :          0 :                         new_fa->fa_state = state & ~FA_S_ACCESSED;
    1214                 :          0 :                         new_fa->fa_slen = fa->fa_slen;
    1215                 :          0 :                         new_fa->tb_id = tb->tb_id;
    1216                 :          0 :                         new_fa->fa_default = -1;
    1217                 :            : 
    1218                 :          0 :                         err = call_fib_entry_notifiers(net,
    1219                 :            :                                                        FIB_EVENT_ENTRY_REPLACE,
    1220                 :            :                                                        key, plen, new_fa,
    1221                 :            :                                                        extack);
    1222         [ #  # ]:          0 :                         if (err)
    1223                 :            :                                 goto out_free_new_fa;
    1224                 :            : 
    1225                 :          0 :                         rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
    1226                 :          0 :                                   tb->tb_id, &cfg->fc_nlinfo, nlflags);
    1227                 :            : 
    1228                 :          0 :                         hlist_replace_rcu(&fa->fa_list, &new_fa->fa_list);
    1229                 :            : 
    1230                 :            :                         alias_free_mem_rcu(fa);
    1231                 :            : 
    1232                 :          0 :                         fib_release_info(fi_drop);
    1233         [ #  # ]:          0 :                         if (state & FA_S_ACCESSED)
    1234                 :          0 :                                 rt_cache_flush(cfg->fc_nlinfo.nl_net);
    1235                 :            : 
    1236                 :            :                         goto succeeded;
    1237                 :            :                 }
    1238                 :            :                 /* Error if we find a perfect match which
    1239                 :            :                  * uses the same scope, type, and nexthop
    1240                 :            :                  * information.
    1241                 :            :                  */
    1242         [ -  + ]:        414 :                 if (fa_match)
    1243                 :            :                         goto out;
    1244                 :            : 
    1245         [ #  # ]:          0 :                 if (cfg->fc_nlflags & NLM_F_APPEND) {
    1246                 :            :                         event = FIB_EVENT_ENTRY_APPEND;
    1247                 :            :                         nlflags |= NLM_F_APPEND;
    1248                 :            :                 } else {
    1249                 :            :                         fa = fa_first;
    1250                 :            :                 }
    1251                 :            :         }
    1252                 :            :         err = -ENOENT;
    1253         [ +  - ]:       1863 :         if (!(cfg->fc_nlflags & NLM_F_CREATE))
    1254                 :            :                 goto out;
    1255                 :            : 
    1256                 :       1863 :         nlflags |= NLM_F_CREATE;
    1257                 :            :         err = -ENOBUFS;
    1258                 :       1863 :         new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
    1259         [ +  - ]:       1863 :         if (!new_fa)
    1260                 :            :                 goto out;
    1261                 :            : 
    1262                 :       1863 :         new_fa->fa_info = fi;
    1263                 :       1863 :         new_fa->fa_tos = tos;
    1264                 :       1863 :         new_fa->fa_type = cfg->fc_type;
    1265                 :       1863 :         new_fa->fa_state = 0;
    1266                 :       1863 :         new_fa->fa_slen = slen;
    1267                 :       1863 :         new_fa->tb_id = tb->tb_id;
    1268                 :       1863 :         new_fa->fa_default = -1;
    1269                 :            : 
    1270                 :       1863 :         err = call_fib_entry_notifiers(net, event, key, plen, new_fa, extack);
    1271         [ +  - ]:       1863 :         if (err)
    1272                 :            :                 goto out_free_new_fa;
    1273                 :            : 
    1274                 :            :         /* Insert new entry to the list. */
    1275                 :       1863 :         err = fib_insert_alias(t, tp, l, new_fa, fa, key);
    1276         [ +  - ]:       1863 :         if (err)
    1277                 :            :                 goto out_fib_notif;
    1278                 :            : 
    1279         [ +  + ]:       1863 :         if (!plen)
    1280                 :        207 :                 tb->tb_num_default++;
    1281                 :            : 
    1282                 :       1863 :         rt_cache_flush(cfg->fc_nlinfo.nl_net);
    1283                 :       3726 :         rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, new_fa->tb_id,
    1284                 :       1863 :                   &cfg->fc_nlinfo, nlflags);
    1285                 :            : succeeded:
    1286                 :            :         return 0;
    1287                 :            : 
    1288                 :            : out_fib_notif:
    1289                 :            :         /* notifier was sent that entry would be added to trie, but
    1290                 :            :          * the add failed and need to recover. Only failure for
    1291                 :            :          * fib_insert_alias is ENOMEM.
    1292                 :            :          */
    1293         [ #  # ]:          0 :         NL_SET_ERR_MSG(extack, "Failed to insert route into trie");
    1294                 :          0 :         call_fib_entry_notifiers(net, FIB_EVENT_ENTRY_DEL, key,
    1295                 :            :                                  plen, new_fa, NULL);
    1296                 :            : out_free_new_fa:
    1297                 :          0 :         kmem_cache_free(fn_alias_kmem, new_fa);
    1298                 :            : out:
    1299                 :        414 :         fib_release_info(fi);
    1300                 :            : err:
    1301                 :        414 :         return err;
    1302                 :            : }
    1303                 :            : 
    1304                 :            : static inline t_key prefix_mismatch(t_key key, struct key_vector *n)
    1305                 :            : {
    1306                 :      11787 :         t_key prefix = n->key;
    1307                 :            : 
    1308                 :      11787 :         return (key ^ prefix) & (prefix | -prefix);
    1309                 :            : }
    1310                 :            : 
    1311                 :            : /* should be called with rcu_read_lock */
    1312                 :      18639 : int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
    1313                 :            :                      struct fib_result *res, int fib_flags)
    1314                 :            : {
    1315                 :      18639 :         struct trie *t = (struct trie *) tb->tb_data;
    1316                 :            : #ifdef CONFIG_IP_FIB_TRIE_STATS
    1317                 :            :         struct trie_use_stats __percpu *stats = t->stats;
    1318                 :            : #endif
    1319                 :      18639 :         const t_key key = ntohl(flp->daddr);
    1320                 :            :         struct key_vector *n, *pn;
    1321                 :            :         struct fib_alias *fa;
    1322                 :            :         unsigned long index;
    1323                 :            :         t_key cindex;
    1324                 :            : 
    1325                 :      18639 :         pn = t->kv;
    1326                 :            :         cindex = 0;
    1327                 :            : 
    1328                 :      18639 :         n = get_child_rcu(pn, cindex);
    1329         [ -  + ]:      18639 :         if (!n) {
    1330                 :          0 :                 trace_fib_table_lookup(tb->tb_id, flp, NULL, -EAGAIN);
    1331                 :          0 :                 return -EAGAIN;
    1332                 :            :         }
    1333                 :            : 
    1334                 :            : #ifdef CONFIG_IP_FIB_TRIE_STATS
    1335                 :            :         this_cpu_inc(stats->gets);
    1336                 :            : #endif
    1337                 :            : 
    1338                 :            :         /* Step 1: Travel to the longest prefix match in the trie */
    1339                 :            :         for (;;) {
    1340                 :      41430 :                 index = get_cindex(key, n);
    1341                 :            : 
    1342                 :            :                 /* This bit of code is a bit tricky but it combines multiple
    1343                 :            :                  * checks into a single check.  The prefix consists of the
    1344                 :            :                  * prefix plus zeros for the "bits" in the prefix. The index
    1345                 :            :                  * is the difference between the key and this value.  From
    1346                 :            :                  * this we can actually derive several pieces of data.
    1347                 :            :                  *   if (index >= (1ul << bits))
    1348                 :            :                  *     we have a mismatch in skip bits and failed
    1349                 :            :                  *   else
    1350                 :            :                  *     we know the value is cindex
    1351                 :            :                  *
    1352                 :            :                  * This check is safe even if bits == KEYLENGTH due to the
    1353                 :            :                  * fact that we can only allocate a node with 32 bits if a
    1354                 :            :                  * long is greater than 32 bits.
    1355                 :            :                  */
    1356         [ +  + ]:      41430 :                 if (index >= (1ul << n->bits))
    1357                 :            :                         break;
    1358                 :            : 
    1359                 :            :                 /* we have found a leaf. Prefixes have already been compared */
    1360         [ +  + ]:      32890 :                 if (IS_LEAF(n))
    1361                 :            :                         goto found;
    1362                 :            : 
    1363                 :            :                 /* only record pn and cindex if we are going to be chopping
    1364                 :            :                  * bits later.  Otherwise we are just wasting cycles.
    1365                 :            :                  */
    1366         [ +  + ]:      24774 :                 if (n->slen > n->pos) {
    1367                 :            :                         pn = n;
    1368                 :            :                         cindex = index;
    1369                 :            :                 }
    1370                 :            : 
    1371                 :      49548 :                 n = get_child_rcu(n, index);
    1372         [ +  + ]:      24774 :                 if (unlikely(!n))
    1373                 :            :                         goto backtrace;
    1374                 :            :         }
    1375                 :            : 
    1376                 :            :         /* Step 2: Sort out leaves and begin backtracing for longest prefix */
    1377                 :            :         for (;;) {
    1378                 :            :                 /* record the pointer where our next node pointer is stored */
    1379                 :      11787 :                 struct key_vector __rcu **cptr = n->tnode;
    1380                 :            : 
    1381                 :            :                 /* This test verifies that none of the bits that differ
    1382                 :            :                  * between the key and the prefix exist in the region of
    1383                 :            :                  * the lsb and higher in the prefix.
    1384                 :            :                  */
    1385   [ +  +  +  + ]:      11787 :                 if (unlikely(prefix_mismatch(key, n)) || (n->slen == n->pos))
    1386                 :            :                         goto backtrace;
    1387                 :            : 
    1388                 :            :                 /* exit out and process leaf */
    1389         [ -  + ]:       5826 :                 if (unlikely(IS_LEAF(n)))
    1390                 :            :                         break;
    1391                 :            : 
    1392                 :            :                 /* Don't bother recording parent info.  Since we are in
    1393                 :            :                  * prefix match mode we will have to come back to wherever
    1394                 :            :                  * we started this traversal anyway
    1395                 :            :                  */
    1396                 :            : 
    1397         [ +  + ]:       4415 :                 while ((n = rcu_dereference(*cptr)) == NULL) {
    1398                 :            : backtrace:
    1399                 :            : #ifdef CONFIG_IP_FIB_TRIE_STATS
    1400                 :            :                         if (!n)
    1401                 :            :                                 this_cpu_inc(stats->null_node_hit);
    1402                 :            : #endif
    1403                 :            :                         /* If we are at cindex 0 there are no more bits for
    1404                 :            :                          * us to strip at this level so we must ascend back
    1405                 :            :                          * up one level to see if there are any more bits to
    1406                 :            :                          * be stripped there.
    1407                 :            :                          */
    1408         [ +  + ]:       9112 :                         while (!cindex) {
    1409                 :       4697 :                                 t_key pkey = pn->key;
    1410                 :            : 
    1411                 :            :                                 /* If we don't have a parent then there is
    1412                 :            :                                  * nothing for us to do as we do not have any
    1413                 :            :                                  * further nodes to parse.
    1414                 :            :                                  */
    1415         [ +  - ]:       4697 :                                 if (IS_TRIE(pn)) {
    1416                 :       4697 :                                         trace_fib_table_lookup(tb->tb_id, flp,
    1417                 :            :                                                                NULL, -EAGAIN);
    1418                 :       4697 :                                         return -EAGAIN;
    1419                 :            :                                 }
    1420                 :            : #ifdef CONFIG_IP_FIB_TRIE_STATS
    1421                 :            :                                 this_cpu_inc(stats->backtrack);
    1422                 :            : #endif
    1423                 :            :                                 /* Get Child's index */
    1424                 :          0 :                                 pn = node_parent_rcu(pn);
    1425                 :            :                                 cindex = get_index(pkey, pn);
    1426                 :            :                         }
    1427                 :            : 
    1428                 :            :                         /* strip the least significant bit from the cindex */
    1429                 :       4415 :                         cindex &= cindex - 1;
    1430                 :            : 
    1431                 :            :                         /* grab pointer for next child node */
    1432                 :       4415 :                         cptr = &pn->tnode[cindex];
    1433                 :            :                 }
    1434                 :            :         }
    1435                 :            : 
    1436                 :            : found:
    1437                 :            :         /* this line carries forward the xor from earlier in the function */
    1438                 :      13942 :         index = key ^ n->key;
    1439                 :            : 
    1440                 :            :         /* Step 3: Process the leaf, if that fails fall back to backtracing */
    1441   [ +  -  +  -  :      17691 :         hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) {
                   -  + ]
    1442                 :      17691 :                 struct fib_info *fi = fa->fa_info;
    1443                 :            :                 int nhsel, err;
    1444                 :            : 
    1445         [ +  + ]:      17691 :                 if ((BITS_PER_LONG > KEYLENGTH) || (fa->fa_slen < KEYLENGTH)) {
    1446         [ +  + ]:      15614 :                         if (index >= (1ul << fa->fa_slen))
    1447                 :       3749 :                                 continue;
    1448                 :            :                 }
    1449   [ -  +  #  # ]:      13942 :                 if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
    1450                 :          0 :                         continue;
    1451         [ -  + ]:      13942 :                 if (fi->fib_dead)
    1452                 :          0 :                         continue;
    1453         [ -  + ]:      13942 :                 if (fa->fa_info->fib_scope < flp->flowi4_scope)
    1454                 :          0 :                         continue;
    1455                 :            :                 fib_alias_accessed(fa);
    1456                 :      13942 :                 err = fib_props[fa->fa_type].error;
    1457         [ -  + ]:      13942 :                 if (unlikely(err < 0)) {
    1458                 :            : out_reject:
    1459                 :            : #ifdef CONFIG_IP_FIB_TRIE_STATS
    1460                 :            :                         this_cpu_inc(stats->semantic_match_passed);
    1461                 :            : #endif
    1462                 :          0 :                         trace_fib_table_lookup(tb->tb_id, flp, NULL, err);
    1463                 :          0 :                         return err;
    1464                 :            :                 }
    1465         [ -  + ]:      13942 :                 if (fi->fib_flags & RTNH_F_DEAD)
    1466                 :          0 :                         continue;
    1467                 :            : 
    1468   [ -  +  #  # ]:      13942 :                 if (unlikely(fi->nh && nexthop_is_blackhole(fi->nh))) {
    1469                 :          0 :                         err = fib_props[RTN_BLACKHOLE].error;
    1470                 :          0 :                         goto out_reject;
    1471                 :            :                 }
    1472                 :            : 
    1473         [ +  - ]:      13942 :                 for (nhsel = 0; nhsel < fib_info_num_path(fi); nhsel++) {
    1474                 :      13942 :                         struct fib_nh_common *nhc = fib_info_nhc(fi, nhsel);
    1475                 :            : 
    1476         [ -  + ]:      13942 :                         if (nhc->nhc_flags & RTNH_F_DEAD)
    1477                 :          0 :                                 continue;
    1478   [ -  +  #  # ]:      27884 :                         if (ip_ignore_linkdown(nhc->nhc_dev) &&
    1479         [ #  # ]:          0 :                             nhc->nhc_flags & RTNH_F_LINKDOWN &&
    1480                 :          0 :                             !(fib_flags & FIB_LOOKUP_IGNORE_LINKSTATE))
    1481                 :          0 :                                 continue;
    1482         [ +  - ]:      13942 :                         if (!(flp->flowi4_flags & FLOWI_FLAG_SKIP_NH_OIF)) {
    1483   [ +  +  -  + ]:      14977 :                                 if (flp->flowi4_oif &&
    1484                 :       1035 :                                     flp->flowi4_oif != nhc->nhc_oif)
    1485                 :          0 :                                         continue;
    1486                 :            :                         }
    1487                 :            : 
    1488         [ -  + ]:      13942 :                         if (!(fib_flags & FIB_LOOKUP_NOREF))
    1489                 :          0 :                                 refcount_inc(&fi->fib_clntref);
    1490                 :            : 
    1491                 :      13942 :                         res->prefix = htonl(n->key);
    1492                 :      13942 :                         res->prefixlen = KEYLENGTH - fa->fa_slen;
    1493                 :      13942 :                         res->nh_sel = nhsel;
    1494                 :      13942 :                         res->nhc = nhc;
    1495                 :      13942 :                         res->type = fa->fa_type;
    1496                 :      13942 :                         res->scope = fi->fib_scope;
    1497                 :      13942 :                         res->fi = fi;
    1498                 :      13942 :                         res->table = tb;
    1499                 :      13942 :                         res->fa_head = &n->leaf;
    1500                 :            : #ifdef CONFIG_IP_FIB_TRIE_STATS
    1501                 :            :                         this_cpu_inc(stats->semantic_match_passed);
    1502                 :            : #endif
    1503                 :      13942 :                         trace_fib_table_lookup(tb->tb_id, flp, nhc, err);
    1504                 :            : 
    1505                 :      13942 :                         return err;
    1506                 :            :                 }
    1507                 :            :         }
    1508                 :            : #ifdef CONFIG_IP_FIB_TRIE_STATS
    1509                 :            :         this_cpu_inc(stats->semantic_match_miss);
    1510                 :            : #endif
    1511                 :            :         goto backtrace;
    1512                 :            : }
    1513                 :            : EXPORT_SYMBOL_GPL(fib_table_lookup);
    1514                 :            : 
    1515                 :          0 : static void fib_remove_alias(struct trie *t, struct key_vector *tp,
    1516                 :            :                              struct key_vector *l, struct fib_alias *old)
    1517                 :            : {
    1518                 :            :         /* record the location of the previous list_info entry */
    1519                 :          0 :         struct hlist_node **pprev = old->fa_list.pprev;
    1520                 :            :         struct fib_alias *fa = hlist_entry(pprev, typeof(*fa), fa_list.next);
    1521                 :            : 
    1522                 :            :         /* remove the fib_alias from the list */
    1523                 :            :         hlist_del_rcu(&old->fa_list);
    1524                 :            : 
    1525                 :            :         /* if we emptied the list this leaf will be freed and we can sort
    1526                 :            :          * out parent suffix lengths as a part of trie_rebalance
    1527                 :            :          */
    1528         [ #  # ]:          0 :         if (hlist_empty(&l->leaf)) {
    1529         [ #  # ]:          0 :                 if (tp->slen == l->slen)
    1530                 :          0 :                         node_pull_suffix(tp, tp->pos);
    1531                 :          0 :                 put_child_root(tp, l->key, NULL);
    1532                 :          0 :                 node_free(l);
    1533                 :            :                 trie_rebalance(t, tp);
    1534                 :            :                 return;
    1535                 :            :         }
    1536                 :            : 
    1537                 :            :         /* only access fa if it is pointing at the last valid hlist_node */
    1538         [ #  # ]:          0 :         if (*pprev)
    1539                 :            :                 return;
    1540                 :            : 
    1541                 :            :         /* update the trie with the latest suffix length */
    1542                 :          0 :         l->slen = fa->fa_slen;
    1543                 :          0 :         node_pull_suffix(tp, fa->fa_slen);
    1544                 :            : }
    1545                 :            : 
    1546                 :            : /* Caller must hold RTNL. */
    1547                 :          0 : int fib_table_delete(struct net *net, struct fib_table *tb,
    1548                 :            :                      struct fib_config *cfg, struct netlink_ext_ack *extack)
    1549                 :            : {
    1550                 :          0 :         struct trie *t = (struct trie *) tb->tb_data;
    1551                 :            :         struct fib_alias *fa, *fa_to_delete;
    1552                 :            :         struct key_vector *l, *tp;
    1553                 :          0 :         u8 plen = cfg->fc_dst_len;
    1554                 :          0 :         u8 slen = KEYLENGTH - plen;
    1555                 :          0 :         u8 tos = cfg->fc_tos;
    1556                 :            :         u32 key;
    1557                 :            : 
    1558                 :          0 :         key = ntohl(cfg->fc_dst);
    1559                 :            : 
    1560         [ #  # ]:          0 :         if (!fib_valid_key_len(key, plen, extack))
    1561                 :            :                 return -EINVAL;
    1562                 :            : 
    1563                 :            :         l = fib_find_node(t, &tp, key);
    1564         [ #  # ]:          0 :         if (!l)
    1565                 :            :                 return -ESRCH;
    1566                 :            : 
    1567                 :          0 :         fa = fib_find_alias(&l->leaf, slen, tos, 0, tb->tb_id);
    1568         [ #  # ]:          0 :         if (!fa)
    1569                 :            :                 return -ESRCH;
    1570                 :            : 
    1571                 :            :         pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
    1572                 :            : 
    1573                 :            :         fa_to_delete = NULL;
    1574   [ #  #  #  # ]:          0 :         hlist_for_each_entry_from(fa, fa_list) {
    1575                 :          0 :                 struct fib_info *fi = fa->fa_info;
    1576                 :            : 
    1577   [ #  #  #  # ]:          0 :                 if ((fa->fa_slen != slen) ||
    1578         [ #  # ]:          0 :                     (fa->tb_id != tb->tb_id) ||
    1579                 :          0 :                     (fa->fa_tos != tos))
    1580                 :            :                         break;
    1581                 :            : 
    1582   [ #  #  #  #  :          0 :                 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
                   #  # ]
    1583         [ #  # ]:          0 :                     (cfg->fc_scope == RT_SCOPE_NOWHERE ||
    1584         [ #  # ]:          0 :                      fa->fa_info->fib_scope == cfg->fc_scope) &&
    1585         [ #  # ]:          0 :                     (!cfg->fc_prefsrc ||
    1586         [ #  # ]:          0 :                      fi->fib_prefsrc == cfg->fc_prefsrc) &&
    1587         [ #  # ]:          0 :                     (!cfg->fc_protocol ||
    1588         [ #  # ]:          0 :                      fi->fib_protocol == cfg->fc_protocol) &&
    1589         [ #  # ]:          0 :                     fib_nh_match(cfg, fi, extack) == 0 &&
    1590                 :          0 :                     fib_metrics_match(cfg, fi)) {
    1591                 :          0 :                         fa_to_delete = fa;
    1592                 :          0 :                         break;
    1593                 :            :                 }
    1594                 :            :         }
    1595                 :            : 
    1596         [ #  # ]:          0 :         if (!fa_to_delete)
    1597                 :            :                 return -ESRCH;
    1598                 :            : 
    1599                 :          0 :         call_fib_entry_notifiers(net, FIB_EVENT_ENTRY_DEL, key, plen,
    1600                 :            :                                  fa_to_delete, extack);
    1601                 :          0 :         rtmsg_fib(RTM_DELROUTE, htonl(key), fa_to_delete, plen, tb->tb_id,
    1602                 :          0 :                   &cfg->fc_nlinfo, 0);
    1603                 :            : 
    1604         [ #  # ]:          0 :         if (!plen)
    1605                 :          0 :                 tb->tb_num_default--;
    1606                 :            : 
    1607                 :          0 :         fib_remove_alias(t, tp, l, fa_to_delete);
    1608                 :            : 
    1609         [ #  # ]:          0 :         if (fa_to_delete->fa_state & FA_S_ACCESSED)
    1610                 :          0 :                 rt_cache_flush(cfg->fc_nlinfo.nl_net);
    1611                 :            : 
    1612                 :          0 :         fib_release_info(fa_to_delete->fa_info);
    1613                 :            :         alias_free_mem_rcu(fa_to_delete);
    1614                 :          0 :         return 0;
    1615                 :            : }
    1616                 :            : 
    1617                 :            : /* Scan for the next leaf starting at the provided key value */
    1618                 :       2898 : static struct key_vector *leaf_walk_rcu(struct key_vector **tn, t_key key)
    1619                 :            : {
    1620                 :       2898 :         struct key_vector *pn, *n = *tn;
    1621                 :            :         unsigned long cindex;
    1622                 :            : 
    1623                 :            :         /* this loop is meant to try and find the key in the trie */
    1624                 :            :         do {
    1625                 :            :                 /* record parent and next child index */
    1626                 :            :                 pn = n;
    1627         [ +  + ]:       3312 :                 cindex = (key > pn->key) ? get_index(key, pn) : 0;
    1628                 :            : 
    1629         [ +  + ]:       3312 :                 if (cindex >> pn->bits)
    1630                 :            :                         break;
    1631                 :            : 
    1632                 :            :                 /* descend into the next child */
    1633                 :       4140 :                 n = get_child_rcu(pn, cindex++);
    1634         [ +  + ]:       2070 :                 if (!n)
    1635                 :            :                         break;
    1636                 :            : 
    1637                 :            :                 /* guarantee forward progress on the keys */
    1638   [ +  +  +  + ]:       1656 :                 if (IS_LEAF(n) && (n->key >= key))
    1639                 :            :                         goto found;
    1640         [ +  + ]:       1242 :         } while (IS_TNODE(n));
    1641                 :            : 
    1642                 :            :         /* this loop will search for the next leaf with a greater key */
    1643         [ +  + ]:       7038 :         while (!IS_TRIE(pn)) {
    1644                 :            :                 /* if we exhausted the parent node we will need to climb */
    1645         [ +  + ]:       6624 :                 if (cindex >= (1ul << pn->bits)) {
    1646                 :       1656 :                         t_key pkey = pn->key;
    1647                 :            : 
    1648                 :       1656 :                         pn = node_parent_rcu(pn);
    1649                 :       1656 :                         cindex = get_index(pkey, pn) + 1;
    1650                 :       1656 :                         continue;
    1651                 :            :                 }
    1652                 :            : 
    1653                 :            :                 /* grab the next available node */
    1654                 :       9936 :                 n = get_child_rcu(pn, cindex++);
    1655         [ +  + ]:       4968 :                 if (!n)
    1656                 :       1656 :                         continue;
    1657                 :            : 
    1658                 :            :                 /* no need to compare keys since we bumped the index */
    1659         [ +  + ]:       3312 :                 if (IS_LEAF(n))
    1660                 :            :                         goto found;
    1661                 :            : 
    1662                 :            :                 /* Rescan start scanning in new node */
    1663                 :            :                 pn = n;
    1664                 :            :                 cindex = 0;
    1665                 :            :         }
    1666                 :            : 
    1667                 :        414 :         *tn = pn;
    1668                 :        414 :         return NULL; /* Root of trie */
    1669                 :            : found:
    1670                 :            :         /* if we are at the limit for keys just return NULL for the tnode */
    1671                 :       2484 :         *tn = pn;
    1672                 :       2484 :         return n;
    1673                 :            : }
    1674                 :            : 
    1675                 :          0 : static void fib_trie_free(struct fib_table *tb)
    1676                 :            : {
    1677                 :          0 :         struct trie *t = (struct trie *)tb->tb_data;
    1678                 :          0 :         struct key_vector *pn = t->kv;
    1679                 :            :         unsigned long cindex = 1;
    1680                 :            :         struct hlist_node *tmp;
    1681                 :            :         struct fib_alias *fa;
    1682                 :            : 
    1683                 :            :         /* walk trie in reverse order and free everything */
    1684                 :            :         for (;;) {
    1685                 :            :                 struct key_vector *n;
    1686                 :            : 
    1687         [ #  # ]:          0 :                 if (!(cindex--)) {
    1688                 :          0 :                         t_key pkey = pn->key;
    1689                 :            : 
    1690         [ #  # ]:          0 :                         if (IS_TRIE(pn))
    1691                 :            :                                 break;
    1692                 :            : 
    1693                 :            :                         n = pn;
    1694                 :          0 :                         pn = node_parent(pn);
    1695                 :            : 
    1696                 :            :                         /* drop emptied tnode */
    1697                 :          0 :                         put_child_root(pn, n->key, NULL);
    1698                 :          0 :                         node_free(n);
    1699                 :            : 
    1700                 :            :                         cindex = get_index(pkey, pn);
    1701                 :            : 
    1702                 :          0 :                         continue;
    1703                 :            :                 }
    1704                 :            : 
    1705                 :            :                 /* grab the next available node */
    1706                 :          0 :                 n = get_child(pn, cindex);
    1707         [ #  # ]:          0 :                 if (!n)
    1708                 :          0 :                         continue;
    1709                 :            : 
    1710         [ #  # ]:          0 :                 if (IS_TNODE(n)) {
    1711                 :            :                         /* record pn and cindex for leaf walking */
    1712                 :            :                         pn = n;
    1713                 :          0 :                         cindex = 1ul << n->bits;
    1714                 :            : 
    1715                 :          0 :                         continue;
    1716                 :            :                 }
    1717                 :            : 
    1718   [ #  #  #  #  :          0 :                 hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {
                   #  # ]
    1719                 :            :                         hlist_del_rcu(&fa->fa_list);
    1720                 :            :                         alias_free_mem_rcu(fa);
    1721                 :            :                 }
    1722                 :            : 
    1723                 :          0 :                 put_child_root(pn, n->key, NULL);
    1724                 :          0 :                 node_free(n);
    1725                 :            :         }
    1726                 :            : 
    1727                 :            : #ifdef CONFIG_IP_FIB_TRIE_STATS
    1728                 :            :         free_percpu(t->stats);
    1729                 :            : #endif
    1730                 :          0 :         kfree(tb);
    1731                 :          0 : }
    1732                 :            : 
    1733                 :          0 : struct fib_table *fib_trie_unmerge(struct fib_table *oldtb)
    1734                 :            : {
    1735                 :          0 :         struct trie *ot = (struct trie *)oldtb->tb_data;
    1736                 :          0 :         struct key_vector *l, *tp = ot->kv;
    1737                 :            :         struct fib_table *local_tb;
    1738                 :            :         struct fib_alias *fa;
    1739                 :            :         struct trie *lt;
    1740                 :            :         t_key key = 0;
    1741                 :            : 
    1742         [ #  # ]:          0 :         if (oldtb->tb_data == oldtb->__data)
    1743                 :            :                 return oldtb;
    1744                 :            : 
    1745                 :          0 :         local_tb = fib_trie_table(RT_TABLE_LOCAL, NULL);
    1746         [ #  # ]:          0 :         if (!local_tb)
    1747                 :            :                 return NULL;
    1748                 :            : 
    1749                 :          0 :         lt = (struct trie *)local_tb->tb_data;
    1750                 :            : 
    1751         [ #  # ]:          0 :         while ((l = leaf_walk_rcu(&tp, key)) != NULL) {
    1752                 :            :                 struct key_vector *local_l = NULL, *local_tp;
    1753                 :            : 
    1754   [ #  #  #  #  :          0 :                 hlist_for_each_entry(fa, &l->leaf, fa_list) {
                   #  # ]
    1755                 :            :                         struct fib_alias *new_fa;
    1756                 :            : 
    1757         [ #  # ]:          0 :                         if (local_tb->tb_id != fa->tb_id)
    1758                 :          0 :                                 continue;
    1759                 :            : 
    1760                 :            :                         /* clone fa for new local table */
    1761                 :          0 :                         new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
    1762         [ #  # ]:          0 :                         if (!new_fa)
    1763                 :            :                                 goto out;
    1764                 :            : 
    1765                 :          0 :                         memcpy(new_fa, fa, sizeof(*fa));
    1766                 :            : 
    1767                 :            :                         /* insert clone into table */
    1768         [ #  # ]:          0 :                         if (!local_l)
    1769                 :          0 :                                 local_l = fib_find_node(lt, &local_tp, l->key);
    1770                 :            : 
    1771         [ #  # ]:          0 :                         if (fib_insert_alias(lt, local_tp, local_l, new_fa,
    1772                 :            :                                              NULL, l->key)) {
    1773                 :          0 :                                 kmem_cache_free(fn_alias_kmem, new_fa);
    1774                 :          0 :                                 goto out;
    1775                 :            :                         }
    1776                 :            :                 }
    1777                 :            : 
    1778                 :            :                 /* stop loop if key wrapped back to 0 */
    1779                 :          0 :                 key = l->key + 1;
    1780         [ #  # ]:          0 :                 if (key < l->key)
    1781                 :            :                         break;
    1782                 :            :         }
    1783                 :            : 
    1784                 :          0 :         return local_tb;
    1785                 :            : out:
    1786                 :          0 :         fib_trie_free(local_tb);
    1787                 :            : 
    1788                 :          0 :         return NULL;
    1789                 :            : }
    1790                 :            : 
    1791                 :            : /* Caller must hold RTNL */
    1792                 :          0 : void fib_table_flush_external(struct fib_table *tb)
    1793                 :            : {
    1794                 :          0 :         struct trie *t = (struct trie *)tb->tb_data;
    1795                 :          0 :         struct key_vector *pn = t->kv;
    1796                 :            :         unsigned long cindex = 1;
    1797                 :            :         struct hlist_node *tmp;
    1798                 :            :         struct fib_alias *fa;
    1799                 :            : 
    1800                 :            :         /* walk trie in reverse order */
    1801                 :            :         for (;;) {
    1802                 :            :                 unsigned char slen = 0;
    1803                 :            :                 struct key_vector *n;
    1804                 :            : 
    1805         [ #  # ]:          0 :                 if (!(cindex--)) {
    1806                 :          0 :                         t_key pkey = pn->key;
    1807                 :            : 
    1808                 :            :                         /* cannot resize the trie vector */
    1809         [ #  # ]:          0 :                         if (IS_TRIE(pn))
    1810                 :            :                                 break;
    1811                 :            : 
    1812                 :            :                         /* update the suffix to address pulled leaves */
    1813         [ #  # ]:          0 :                         if (pn->slen > pn->pos)
    1814                 :          0 :                                 update_suffix(pn);
    1815                 :            : 
    1816                 :            :                         /* resize completed node */
    1817                 :          0 :                         pn = resize(t, pn);
    1818                 :            :                         cindex = get_index(pkey, pn);
    1819                 :            : 
    1820                 :          0 :                         continue;
    1821                 :            :                 }
    1822                 :            : 
    1823                 :            :                 /* grab the next available node */
    1824                 :          0 :                 n = get_child(pn, cindex);
    1825         [ #  # ]:          0 :                 if (!n)
    1826                 :          0 :                         continue;
    1827                 :            : 
    1828         [ #  # ]:          0 :                 if (IS_TNODE(n)) {
    1829                 :            :                         /* record pn and cindex for leaf walking */
    1830                 :            :                         pn = n;
    1831                 :          0 :                         cindex = 1ul << n->bits;
    1832                 :            : 
    1833                 :          0 :                         continue;
    1834                 :            :                 }
    1835                 :            : 
    1836   [ #  #  #  #  :          0 :                 hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {
                   #  # ]
    1837                 :            :                         /* if alias was cloned to local then we just
    1838                 :            :                          * need to remove the local copy from main
    1839                 :            :                          */
    1840         [ #  # ]:          0 :                         if (tb->tb_id != fa->tb_id) {
    1841                 :            :                                 hlist_del_rcu(&fa->fa_list);
    1842                 :            :                                 alias_free_mem_rcu(fa);
    1843                 :          0 :                                 continue;
    1844                 :            :                         }
    1845                 :            : 
    1846                 :            :                         /* record local slen */
    1847                 :          0 :                         slen = fa->fa_slen;
    1848                 :            :                 }
    1849                 :            : 
    1850                 :            :                 /* update leaf slen */
    1851                 :          0 :                 n->slen = slen;
    1852                 :            : 
    1853         [ #  # ]:          0 :                 if (hlist_empty(&n->leaf)) {
    1854                 :          0 :                         put_child_root(pn, n->key, NULL);
    1855                 :          0 :                         node_free(n);
    1856                 :            :                 }
    1857                 :            :         }
    1858                 :          0 : }
    1859                 :            : 
    1860                 :            : /* Caller must hold RTNL. */
    1861                 :          0 : int fib_table_flush(struct net *net, struct fib_table *tb, bool flush_all)
    1862                 :            : {
    1863                 :          0 :         struct trie *t = (struct trie *)tb->tb_data;
    1864                 :          0 :         struct key_vector *pn = t->kv;
    1865                 :            :         unsigned long cindex = 1;
    1866                 :            :         struct hlist_node *tmp;
    1867                 :            :         struct fib_alias *fa;
    1868                 :            :         int found = 0;
    1869                 :            : 
    1870                 :            :         /* walk trie in reverse order */
    1871                 :            :         for (;;) {
    1872                 :            :                 unsigned char slen = 0;
    1873                 :            :                 struct key_vector *n;
    1874                 :            : 
    1875         [ #  # ]:          0 :                 if (!(cindex--)) {
    1876                 :          0 :                         t_key pkey = pn->key;
    1877                 :            : 
    1878                 :            :                         /* cannot resize the trie vector */
    1879         [ #  # ]:          0 :                         if (IS_TRIE(pn))
    1880                 :            :                                 break;
    1881                 :            : 
    1882                 :            :                         /* update the suffix to address pulled leaves */
    1883         [ #  # ]:          0 :                         if (pn->slen > pn->pos)
    1884                 :          0 :                                 update_suffix(pn);
    1885                 :            : 
    1886                 :            :                         /* resize completed node */
    1887                 :          0 :                         pn = resize(t, pn);
    1888                 :            :                         cindex = get_index(pkey, pn);
    1889                 :            : 
    1890                 :          0 :                         continue;
    1891                 :            :                 }
    1892                 :            : 
    1893                 :            :                 /* grab the next available node */
    1894                 :          0 :                 n = get_child(pn, cindex);
    1895         [ #  # ]:          0 :                 if (!n)
    1896                 :          0 :                         continue;
    1897                 :            : 
    1898         [ #  # ]:          0 :                 if (IS_TNODE(n)) {
    1899                 :            :                         /* record pn and cindex for leaf walking */
    1900                 :            :                         pn = n;
    1901                 :          0 :                         cindex = 1ul << n->bits;
    1902                 :            : 
    1903                 :          0 :                         continue;
    1904                 :            :                 }
    1905                 :            : 
    1906   [ #  #  #  #  :          0 :                 hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {
                   #  # ]
    1907                 :          0 :                         struct fib_info *fi = fa->fa_info;
    1908                 :            : 
    1909   [ #  #  #  #  :          0 :                         if (!fi || tb->tb_id != fa->tb_id ||
                   #  # ]
    1910         [ #  # ]:          0 :                             (!(fi->fib_flags & RTNH_F_DEAD) &&
    1911                 :          0 :                              !fib_props[fa->fa_type].error)) {
    1912                 :          0 :                                 slen = fa->fa_slen;
    1913                 :          0 :                                 continue;
    1914                 :            :                         }
    1915                 :            : 
    1916                 :            :                         /* Do not flush error routes if network namespace is
    1917                 :            :                          * not being dismantled
    1918                 :            :                          */
    1919   [ #  #  #  # ]:          0 :                         if (!flush_all && fib_props[fa->fa_type].error) {
    1920                 :          0 :                                 slen = fa->fa_slen;
    1921                 :          0 :                                 continue;
    1922                 :            :                         }
    1923                 :            : 
    1924                 :          0 :                         call_fib_entry_notifiers(net, FIB_EVENT_ENTRY_DEL,
    1925                 :            :                                                  n->key,
    1926                 :          0 :                                                  KEYLENGTH - fa->fa_slen, fa,
    1927                 :            :                                                  NULL);
    1928                 :            :                         hlist_del_rcu(&fa->fa_list);
    1929                 :          0 :                         fib_release_info(fa->fa_info);
    1930                 :            :                         alias_free_mem_rcu(fa);
    1931                 :          0 :                         found++;
    1932                 :            :                 }
    1933                 :            : 
    1934                 :            :                 /* update leaf slen */
    1935                 :          0 :                 n->slen = slen;
    1936                 :            : 
    1937         [ #  # ]:          0 :                 if (hlist_empty(&n->leaf)) {
    1938                 :          0 :                         put_child_root(pn, n->key, NULL);
    1939                 :          0 :                         node_free(n);
    1940                 :            :                 }
    1941                 :            :         }
    1942                 :            : 
    1943                 :            :         pr_debug("trie_flush found=%d\n", found);
    1944                 :          0 :         return found;
    1945                 :            : }
    1946                 :            : 
    1947                 :            : /* derived from fib_trie_free */
    1948                 :          0 : static void __fib_info_notify_update(struct net *net, struct fib_table *tb,
    1949                 :            :                                      struct nl_info *info)
    1950                 :            : {
    1951                 :          0 :         struct trie *t = (struct trie *)tb->tb_data;
    1952                 :          0 :         struct key_vector *pn = t->kv;
    1953                 :            :         unsigned long cindex = 1;
    1954                 :            :         struct fib_alias *fa;
    1955                 :            : 
    1956                 :            :         for (;;) {
    1957                 :            :                 struct key_vector *n;
    1958                 :            : 
    1959         [ #  # ]:          0 :                 if (!(cindex--)) {
    1960                 :          0 :                         t_key pkey = pn->key;
    1961                 :            : 
    1962         [ #  # ]:          0 :                         if (IS_TRIE(pn))
    1963                 :            :                                 break;
    1964                 :            : 
    1965                 :          0 :                         pn = node_parent(pn);
    1966                 :            :                         cindex = get_index(pkey, pn);
    1967                 :          0 :                         continue;
    1968                 :            :                 }
    1969                 :            : 
    1970                 :            :                 /* grab the next available node */
    1971                 :          0 :                 n = get_child(pn, cindex);
    1972         [ #  # ]:          0 :                 if (!n)
    1973                 :          0 :                         continue;
    1974                 :            : 
    1975         [ #  # ]:          0 :                 if (IS_TNODE(n)) {
    1976                 :            :                         /* record pn and cindex for leaf walking */
    1977                 :            :                         pn = n;
    1978                 :          0 :                         cindex = 1ul << n->bits;
    1979                 :            : 
    1980                 :          0 :                         continue;
    1981                 :            :                 }
    1982                 :            : 
    1983   [ #  #  #  #  :          0 :                 hlist_for_each_entry(fa, &n->leaf, fa_list) {
                   #  # ]
    1984                 :          0 :                         struct fib_info *fi = fa->fa_info;
    1985                 :            : 
    1986   [ #  #  #  #  :          0 :                         if (!fi || !fi->nh_updated || fa->tb_id != tb->tb_id)
                   #  # ]
    1987                 :          0 :                                 continue;
    1988                 :            : 
    1989                 :          0 :                         rtmsg_fib(RTM_NEWROUTE, htonl(n->key), fa,
    1990                 :          0 :                                   KEYLENGTH - fa->fa_slen, tb->tb_id,
    1991                 :            :                                   info, NLM_F_REPLACE);
    1992                 :            : 
    1993                 :            :                         /* call_fib_entry_notifiers will be removed when
    1994                 :            :                          * in-kernel notifier is implemented and supported
    1995                 :            :                          * for nexthop objects
    1996                 :            :                          */
    1997                 :          0 :                         call_fib_entry_notifiers(net, FIB_EVENT_ENTRY_REPLACE,
    1998                 :            :                                                  n->key,
    1999                 :          0 :                                                  KEYLENGTH - fa->fa_slen, fa,
    2000                 :            :                                                  NULL);
    2001                 :            :                 }
    2002                 :            :         }
    2003                 :          0 : }
    2004                 :            : 
    2005                 :          0 : void fib_info_notify_update(struct net *net, struct nl_info *info)
    2006                 :            : {
    2007                 :            :         unsigned int h;
    2008                 :            : 
    2009         [ #  # ]:          0 :         for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
    2010                 :          0 :                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
    2011                 :            :                 struct fib_table *tb;
    2012                 :            : 
    2013   [ #  #  #  #  :          0 :                 hlist_for_each_entry_rcu(tb, head, tb_hlist)
                   #  # ]
    2014                 :          0 :                         __fib_info_notify_update(net, tb, info);
    2015                 :            :         }
    2016                 :          0 : }
    2017                 :            : 
    2018                 :          0 : static void fib_leaf_notify(struct net *net, struct key_vector *l,
    2019                 :            :                             struct fib_table *tb, struct notifier_block *nb)
    2020                 :            : {
    2021                 :            :         struct fib_alias *fa;
    2022                 :            : 
    2023   [ #  #  #  #  :          0 :         hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) {
                   #  # ]
    2024                 :          0 :                 struct fib_info *fi = fa->fa_info;
    2025                 :            : 
    2026         [ #  # ]:          0 :                 if (!fi)
    2027                 :          0 :                         continue;
    2028                 :            : 
    2029                 :            :                 /* local and main table can share the same trie,
    2030                 :            :                  * so don't notify twice for the same entry.
    2031                 :            :                  */
    2032         [ #  # ]:          0 :                 if (tb->tb_id != fa->tb_id)
    2033                 :          0 :                         continue;
    2034                 :            : 
    2035                 :          0 :                 call_fib_entry_notifier(nb, net, FIB_EVENT_ENTRY_ADD, l->key,
    2036                 :          0 :                                         KEYLENGTH - fa->fa_slen, fa);
    2037                 :            :         }
    2038                 :          0 : }
    2039                 :            : 
    2040                 :          0 : static void fib_table_notify(struct net *net, struct fib_table *tb,
    2041                 :            :                              struct notifier_block *nb)
    2042                 :            : {
    2043                 :          0 :         struct trie *t = (struct trie *)tb->tb_data;
    2044                 :          0 :         struct key_vector *l, *tp = t->kv;
    2045                 :            :         t_key key = 0;
    2046                 :            : 
    2047         [ #  # ]:          0 :         while ((l = leaf_walk_rcu(&tp, key)) != NULL) {
    2048                 :          0 :                 fib_leaf_notify(net, l, tb, nb);
    2049                 :            : 
    2050                 :          0 :                 key = l->key + 1;
    2051                 :            :                 /* stop in case of wrap around */
    2052         [ #  # ]:          0 :                 if (key < l->key)
    2053                 :            :                         break;
    2054                 :            :         }
    2055                 :          0 : }
    2056                 :            : 
    2057                 :          0 : void fib_notify(struct net *net, struct notifier_block *nb)
    2058                 :            : {
    2059                 :            :         unsigned int h;
    2060                 :            : 
    2061         [ #  # ]:          0 :         for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
    2062                 :          0 :                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
    2063                 :            :                 struct fib_table *tb;
    2064                 :            : 
    2065   [ #  #  #  #  :          0 :                 hlist_for_each_entry_rcu(tb, head, tb_hlist)
                   #  # ]
    2066                 :          0 :                         fib_table_notify(net, tb, nb);
    2067                 :            :         }
    2068                 :          0 : }
    2069                 :            : 
    2070                 :          0 : static void __trie_free_rcu(struct rcu_head *head)
    2071                 :            : {
    2072                 :          0 :         struct fib_table *tb = container_of(head, struct fib_table, rcu);
    2073                 :            : #ifdef CONFIG_IP_FIB_TRIE_STATS
    2074                 :            :         struct trie *t = (struct trie *)tb->tb_data;
    2075                 :            : 
    2076                 :            :         if (tb->tb_data == tb->__data)
    2077                 :            :                 free_percpu(t->stats);
    2078                 :            : #endif /* CONFIG_IP_FIB_TRIE_STATS */
    2079                 :          0 :         kfree(tb);
    2080                 :          0 : }
    2081                 :            : 
    2082                 :          0 : void fib_free_table(struct fib_table *tb)
    2083                 :            : {
    2084                 :          0 :         call_rcu(&tb->rcu, __trie_free_rcu);
    2085                 :          0 : }
    2086                 :            : 
    2087                 :       2484 : static int fn_trie_dump_leaf(struct key_vector *l, struct fib_table *tb,
    2088                 :            :                              struct sk_buff *skb, struct netlink_callback *cb,
    2089                 :            :                              struct fib_dump_filter *filter)
    2090                 :            : {
    2091                 :            :         unsigned int flags = NLM_F_MULTI;
    2092                 :       2484 :         __be32 xkey = htonl(l->key);
    2093                 :            :         int i, s_i, i_fa, s_fa, err;
    2094                 :            :         struct fib_alias *fa;
    2095                 :            : 
    2096   [ +  -  +  - ]:       4968 :         if (filter->filter_set ||
    2097         [ -  + ]:       4968 :             !filter->dump_exceptions || !filter->dump_routes)
    2098                 :            :                 flags |= NLM_F_DUMP_FILTERED;
    2099                 :            : 
    2100                 :       2484 :         s_i = cb->args[4];
    2101                 :       2484 :         s_fa = cb->args[5];
    2102                 :            :         i = 0;
    2103                 :            : 
    2104                 :            :         /* rcu_read_lock is hold by caller */
    2105   [ +  -  +  +  :       5382 :         hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) {
                   +  + ]
    2106                 :       2898 :                 struct fib_info *fi = fa->fa_info;
    2107                 :            : 
    2108         [ +  - ]:       2898 :                 if (i < s_i)
    2109                 :            :                         goto next;
    2110                 :            : 
    2111                 :       2898 :                 i_fa = 0;
    2112                 :            : 
    2113         [ +  + ]:       2898 :                 if (tb->tb_id != fa->tb_id)
    2114                 :            :                         goto next;
    2115                 :            : 
    2116         [ -  + ]:       1449 :                 if (filter->filter_set) {
    2117   [ #  #  #  # ]:          0 :                         if (filter->rt_type && fa->fa_type != filter->rt_type)
    2118                 :            :                                 goto next;
    2119                 :            : 
    2120   [ #  #  #  # ]:          0 :                         if ((filter->protocol &&
    2121                 :          0 :                              fi->fib_protocol != filter->protocol))
    2122                 :            :                                 goto next;
    2123                 :            : 
    2124   [ #  #  #  # ]:          0 :                         if (filter->dev &&
    2125                 :          0 :                             !fib_info_nh_uses_dev(fi, filter->dev))
    2126                 :            :                                 goto next;
    2127                 :            :                 }
    2128                 :            : 
    2129         [ +  - ]:       1449 :                 if (filter->dump_routes) {
    2130         [ +  - ]:       1449 :                         if (!s_fa) {
    2131                 :       4347 :                                 err = fib_dump_info(skb,
    2132                 :       1449 :                                                     NETLINK_CB(cb->skb).portid,
    2133                 :       1449 :                                                     cb->nlh->nlmsg_seq,
    2134                 :            :                                                     RTM_NEWROUTE,
    2135                 :            :                                                     tb->tb_id, fa->fa_type,
    2136                 :            :                                                     xkey,
    2137                 :       1449 :                                                     KEYLENGTH - fa->fa_slen,
    2138                 :            :                                                     fa->fa_tos, fi, flags);
    2139         [ +  - ]:       1449 :                                 if (err < 0)
    2140                 :            :                                         goto stop;
    2141                 :            :                         }
    2142                 :            : 
    2143                 :       1449 :                         i_fa++;
    2144                 :            :                 }
    2145                 :            : 
    2146         [ +  - ]:       1449 :                 if (filter->dump_exceptions) {
    2147                 :       1449 :                         err = fib_dump_info_fnhe(skb, cb, tb->tb_id, fi,
    2148                 :            :                                                  &i_fa, s_fa, flags);
    2149         [ +  - ]:       1449 :                         if (err < 0)
    2150                 :            :                                 goto stop;
    2151                 :            :                 }
    2152                 :            : 
    2153                 :            : next:
    2154                 :       2898 :                 i++;
    2155                 :            :         }
    2156                 :            : 
    2157                 :       2484 :         cb->args[4] = i;
    2158                 :       2484 :         return skb->len;
    2159                 :            : 
    2160                 :            : stop:
    2161                 :          0 :         cb->args[4] = i;
    2162                 :          0 :         cb->args[5] = i_fa;
    2163                 :          0 :         return err;
    2164                 :            : }
    2165                 :            : 
    2166                 :            : /* rcu_read_lock needs to be hold by caller from readside */
    2167                 :        414 : int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
    2168                 :            :                    struct netlink_callback *cb, struct fib_dump_filter *filter)
    2169                 :            : {
    2170                 :        414 :         struct trie *t = (struct trie *)tb->tb_data;
    2171                 :        414 :         struct key_vector *l, *tp = t->kv;
    2172                 :            :         /* Dump starting at last key.
    2173                 :            :          * Note: 0.0.0.0/0 (ie default) is first key.
    2174                 :            :          */
    2175                 :        414 :         int count = cb->args[2];
    2176                 :        414 :         t_key key = cb->args[3];
    2177                 :            : 
    2178                 :            :         /* First time here, count and key are both always 0. Count > 0
    2179                 :            :          * and key == 0 means the dump has wrapped around and we are done.
    2180                 :            :          */
    2181         [ -  + ]:        414 :         if (count && !key)
    2182                 :          0 :                 return skb->len;
    2183                 :            : 
    2184         [ +  + ]:       2898 :         while ((l = leaf_walk_rcu(&tp, key)) != NULL) {
    2185                 :            :                 int err;
    2186                 :            : 
    2187                 :       2484 :                 err = fn_trie_dump_leaf(l, tb, skb, cb, filter);
    2188         [ -  + ]:       2484 :                 if (err < 0) {
    2189                 :          0 :                         cb->args[3] = key;
    2190                 :          0 :                         cb->args[2] = count;
    2191                 :          0 :                         return err;
    2192                 :            :                 }
    2193                 :            : 
    2194                 :       2484 :                 ++count;
    2195                 :       2484 :                 key = l->key + 1;
    2196                 :            : 
    2197                 :       2484 :                 memset(&cb->args[4], 0,
    2198                 :            :                        sizeof(cb->args) - 4*sizeof(cb->args[0]));
    2199                 :            : 
    2200                 :            :                 /* stop loop if key wrapped back to 0 */
    2201         [ +  - ]:       2484 :                 if (key < l->key)
    2202                 :            :                         break;
    2203                 :            :         }
    2204                 :            : 
    2205                 :        414 :         cb->args[3] = key;
    2206                 :        414 :         cb->args[2] = count;
    2207                 :            : 
    2208                 :        414 :         return skb->len;
    2209                 :            : }
    2210                 :            : 
    2211                 :        207 : void __init fib_trie_init(void)
    2212                 :            : {
    2213                 :        207 :         fn_alias_kmem = kmem_cache_create("ip_fib_alias",
    2214                 :            :                                           sizeof(struct fib_alias),
    2215                 :            :                                           0, SLAB_PANIC, NULL);
    2216                 :            : 
    2217                 :        207 :         trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
    2218                 :            :                                            LEAF_SIZE,
    2219                 :            :                                            0, SLAB_PANIC, NULL);
    2220                 :        207 : }
    2221                 :            : 
    2222                 :        414 : struct fib_table *fib_trie_table(u32 id, struct fib_table *alias)
    2223                 :            : {
    2224                 :            :         struct fib_table *tb;
    2225                 :            :         struct trie *t;
    2226                 :            :         size_t sz = sizeof(*tb);
    2227                 :            : 
    2228         [ +  + ]:        414 :         if (!alias)
    2229                 :            :                 sz += sizeof(struct trie);
    2230                 :            : 
    2231                 :        414 :         tb = kzalloc(sz, GFP_KERNEL);
    2232         [ +  - ]:        414 :         if (!tb)
    2233                 :            :                 return NULL;
    2234                 :            : 
    2235                 :        414 :         tb->tb_id = id;
    2236                 :        414 :         tb->tb_num_default = 0;
    2237         [ +  + ]:        414 :         tb->tb_data = (alias ? alias->__data : tb->__data);
    2238                 :            : 
    2239         [ +  + ]:        414 :         if (alias)
    2240                 :            :                 return tb;
    2241                 :            : 
    2242                 :            :         t = (struct trie *) tb->tb_data;
    2243                 :        207 :         t->kv[0].pos = KEYLENGTH;
    2244                 :        207 :         t->kv[0].slen = KEYLENGTH;
    2245                 :            : #ifdef CONFIG_IP_FIB_TRIE_STATS
    2246                 :            :         t->stats = alloc_percpu(struct trie_use_stats);
    2247                 :            :         if (!t->stats) {
    2248                 :            :                 kfree(tb);
    2249                 :            :                 tb = NULL;
    2250                 :            :         }
    2251                 :            : #endif
    2252                 :            : 
    2253                 :        207 :         return tb;
    2254                 :            : }
    2255                 :            : 
    2256                 :            : #ifdef CONFIG_PROC_FS
    2257                 :            : /* Depth first Trie walk iterator */
    2258                 :            : struct fib_trie_iter {
    2259                 :            :         struct seq_net_private p;
    2260                 :            :         struct fib_table *tb;
    2261                 :            :         struct key_vector *tnode;
    2262                 :            :         unsigned int index;
    2263                 :            :         unsigned int depth;
    2264                 :            : };
    2265                 :            : 
    2266                 :          0 : static struct key_vector *fib_trie_get_next(struct fib_trie_iter *iter)
    2267                 :            : {
    2268                 :          0 :         unsigned long cindex = iter->index;
    2269                 :          0 :         struct key_vector *pn = iter->tnode;
    2270                 :            :         t_key pkey;
    2271                 :            : 
    2272                 :            :         pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
    2273                 :            :                  iter->tnode, iter->index, iter->depth);
    2274                 :            : 
    2275         [ #  # ]:          0 :         while (!IS_TRIE(pn)) {
    2276         [ #  # ]:          0 :                 while (cindex < child_length(pn)) {
    2277                 :          0 :                         struct key_vector *n = get_child_rcu(pn, cindex++);
    2278                 :            : 
    2279         [ #  # ]:          0 :                         if (!n)
    2280                 :          0 :                                 continue;
    2281                 :            : 
    2282         [ #  # ]:          0 :                         if (IS_LEAF(n)) {
    2283                 :          0 :                                 iter->tnode = pn;
    2284                 :          0 :                                 iter->index = cindex;
    2285                 :            :                         } else {
    2286                 :            :                                 /* push down one level */
    2287                 :          0 :                                 iter->tnode = n;
    2288                 :          0 :                                 iter->index = 0;
    2289                 :          0 :                                 ++iter->depth;
    2290                 :            :                         }
    2291                 :            : 
    2292                 :          0 :                         return n;
    2293                 :            :                 }
    2294                 :            : 
    2295                 :            :                 /* Current node exhausted, pop back up */
    2296                 :          0 :                 pkey = pn->key;
    2297                 :          0 :                 pn = node_parent_rcu(pn);
    2298                 :          0 :                 cindex = get_index(pkey, pn) + 1;
    2299                 :          0 :                 --iter->depth;
    2300                 :            :         }
    2301                 :            : 
    2302                 :            :         /* record root node so further searches know we are done */
    2303                 :          0 :         iter->tnode = pn;
    2304                 :          0 :         iter->index = 0;
    2305                 :            : 
    2306                 :          0 :         return NULL;
    2307                 :            : }
    2308                 :            : 
    2309                 :            : static struct key_vector *fib_trie_get_first(struct fib_trie_iter *iter,
    2310                 :            :                                              struct trie *t)
    2311                 :            : {
    2312                 :            :         struct key_vector *n, *pn;
    2313                 :            : 
    2314   [ #  #  #  #  :          0 :         if (!t)
             #  #  #  # ]
    2315                 :            :                 return NULL;
    2316                 :            : 
    2317                 :          0 :         pn = t->kv;
    2318                 :          0 :         n = rcu_dereference(pn->tnode[0]);
    2319   [ #  #  #  #  :          0 :         if (!n)
             #  #  #  # ]
    2320                 :            :                 return NULL;
    2321                 :            : 
    2322   [ #  #  #  #  :          0 :         if (IS_TNODE(n)) {
             #  #  #  # ]
    2323                 :          0 :                 iter->tnode = n;
    2324                 :          0 :                 iter->index = 0;
    2325                 :          0 :                 iter->depth = 1;
    2326                 :            :         } else {
    2327                 :          0 :                 iter->tnode = pn;
    2328                 :          0 :                 iter->index = 0;
    2329                 :          0 :                 iter->depth = 0;
    2330                 :            :         }
    2331                 :            : 
    2332                 :            :         return n;
    2333                 :            : }
    2334                 :            : 
    2335                 :          0 : static void trie_collect_stats(struct trie *t, struct trie_stat *s)
    2336                 :            : {
    2337                 :            :         struct key_vector *n;
    2338                 :            :         struct fib_trie_iter iter;
    2339                 :            : 
    2340                 :          0 :         memset(s, 0, sizeof(*s));
    2341                 :            : 
    2342                 :            :         rcu_read_lock();
    2343         [ #  # ]:          0 :         for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
    2344         [ #  # ]:          0 :                 if (IS_LEAF(n)) {
    2345                 :            :                         struct fib_alias *fa;
    2346                 :            : 
    2347                 :          0 :                         s->leaves++;
    2348                 :          0 :                         s->totdepth += iter.depth;
    2349         [ #  # ]:          0 :                         if (iter.depth > s->maxdepth)
    2350                 :          0 :                                 s->maxdepth = iter.depth;
    2351                 :            : 
    2352   [ #  #  #  #  :          0 :                         hlist_for_each_entry_rcu(fa, &n->leaf, fa_list)
                   #  # ]
    2353                 :          0 :                                 ++s->prefixes;
    2354                 :            :                 } else {
    2355                 :          0 :                         s->tnodes++;
    2356         [ #  # ]:          0 :                         if (n->bits < MAX_STAT_DEPTH)
    2357                 :          0 :                                 s->nodesizes[n->bits]++;
    2358                 :          0 :                         s->nullpointers += tn_info(n)->empty_children;
    2359                 :            :                 }
    2360                 :            :         }
    2361                 :            :         rcu_read_unlock();
    2362                 :          0 : }
    2363                 :            : 
    2364                 :            : /*
    2365                 :            :  *      This outputs /proc/net/fib_triestats
    2366                 :            :  */
    2367                 :          0 : static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
    2368                 :            : {
    2369                 :            :         unsigned int i, max, pointers, bytes, avdepth;
    2370                 :            : 
    2371         [ #  # ]:          0 :         if (stat->leaves)
    2372                 :          0 :                 avdepth = stat->totdepth*100 / stat->leaves;
    2373                 :            :         else
    2374                 :            :                 avdepth = 0;
    2375                 :            : 
    2376                 :          0 :         seq_printf(seq, "\tAver depth:     %u.%02d\n",
    2377                 :            :                    avdepth / 100, avdepth % 100);
    2378                 :          0 :         seq_printf(seq, "\tMax depth:      %u\n", stat->maxdepth);
    2379                 :            : 
    2380                 :          0 :         seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
    2381                 :          0 :         bytes = LEAF_SIZE * stat->leaves;
    2382                 :            : 
    2383                 :          0 :         seq_printf(seq, "\tPrefixes:       %u\n", stat->prefixes);
    2384                 :          0 :         bytes += sizeof(struct fib_alias) * stat->prefixes;
    2385                 :            : 
    2386                 :          0 :         seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
    2387                 :          0 :         bytes += TNODE_SIZE(0) * stat->tnodes;
    2388                 :            : 
    2389                 :            :         max = MAX_STAT_DEPTH;
    2390   [ #  #  #  # ]:          0 :         while (max > 0 && stat->nodesizes[max-1] == 0)
    2391                 :            :                 max--;
    2392                 :            : 
    2393                 :            :         pointers = 0;
    2394         [ #  # ]:          0 :         for (i = 1; i < max; i++)
    2395         [ #  # ]:          0 :                 if (stat->nodesizes[i] != 0) {
    2396                 :          0 :                         seq_printf(seq, "  %u: %u",  i, stat->nodesizes[i]);
    2397                 :          0 :                         pointers += (1<<i) * stat->nodesizes[i];
    2398                 :            :                 }
    2399                 :          0 :         seq_putc(seq, '\n');
    2400                 :          0 :         seq_printf(seq, "\tPointers: %u\n", pointers);
    2401                 :            : 
    2402                 :          0 :         bytes += sizeof(struct key_vector *) * pointers;
    2403                 :          0 :         seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
    2404                 :          0 :         seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
    2405                 :          0 : }
    2406                 :            : 
    2407                 :            : #ifdef CONFIG_IP_FIB_TRIE_STATS
    2408                 :            : static void trie_show_usage(struct seq_file *seq,
    2409                 :            :                             const struct trie_use_stats __percpu *stats)
    2410                 :            : {
    2411                 :            :         struct trie_use_stats s = { 0 };
    2412                 :            :         int cpu;
    2413                 :            : 
    2414                 :            :         /* loop through all of the CPUs and gather up the stats */
    2415                 :            :         for_each_possible_cpu(cpu) {
    2416                 :            :                 const struct trie_use_stats *pcpu = per_cpu_ptr(stats, cpu);
    2417                 :            : 
    2418                 :            :                 s.gets += pcpu->gets;
    2419                 :            :                 s.backtrack += pcpu->backtrack;
    2420                 :            :                 s.semantic_match_passed += pcpu->semantic_match_passed;
    2421                 :            :                 s.semantic_match_miss += pcpu->semantic_match_miss;
    2422                 :            :                 s.null_node_hit += pcpu->null_node_hit;
    2423                 :            :                 s.resize_node_skipped += pcpu->resize_node_skipped;
    2424                 :            :         }
    2425                 :            : 
    2426                 :            :         seq_printf(seq, "\nCounters:\n---------\n");
    2427                 :            :         seq_printf(seq, "gets = %u\n", s.gets);
    2428                 :            :         seq_printf(seq, "backtracks = %u\n", s.backtrack);
    2429                 :            :         seq_printf(seq, "semantic match passed = %u\n",
    2430                 :            :                    s.semantic_match_passed);
    2431                 :            :         seq_printf(seq, "semantic match miss = %u\n", s.semantic_match_miss);
    2432                 :            :         seq_printf(seq, "null node hit= %u\n", s.null_node_hit);
    2433                 :            :         seq_printf(seq, "skipped node resize = %u\n\n", s.resize_node_skipped);
    2434                 :            : }
    2435                 :            : #endif /*  CONFIG_IP_FIB_TRIE_STATS */
    2436                 :            : 
    2437                 :          0 : static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
    2438                 :            : {
    2439         [ #  # ]:          0 :         if (tb->tb_id == RT_TABLE_LOCAL)
    2440                 :          0 :                 seq_puts(seq, "Local:\n");
    2441         [ #  # ]:          0 :         else if (tb->tb_id == RT_TABLE_MAIN)
    2442                 :          0 :                 seq_puts(seq, "Main:\n");
    2443                 :            :         else
    2444                 :          0 :                 seq_printf(seq, "Id %d:\n", tb->tb_id);
    2445                 :          0 : }
    2446                 :            : 
    2447                 :            : 
    2448                 :          0 : static int fib_triestat_seq_show(struct seq_file *seq, void *v)
    2449                 :            : {
    2450                 :          0 :         struct net *net = (struct net *)seq->private;
    2451                 :            :         unsigned int h;
    2452                 :            : 
    2453                 :          0 :         seq_printf(seq,
    2454                 :            :                    "Basic info: size of leaf:"
    2455                 :            :                    " %zd bytes, size of tnode: %zd bytes.\n",
    2456                 :            :                    LEAF_SIZE, TNODE_SIZE(0));
    2457                 :            : 
    2458                 :            :         rcu_read_lock();
    2459         [ #  # ]:          0 :         for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
    2460                 :          0 :                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
    2461                 :            :                 struct fib_table *tb;
    2462                 :            : 
    2463   [ #  #  #  #  :          0 :                 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
                   #  # ]
    2464                 :          0 :                         struct trie *t = (struct trie *) tb->tb_data;
    2465                 :            :                         struct trie_stat stat;
    2466                 :            : 
    2467         [ #  # ]:          0 :                         if (!t)
    2468                 :          0 :                                 continue;
    2469                 :            : 
    2470                 :          0 :                         fib_table_print(seq, tb);
    2471                 :            : 
    2472                 :          0 :                         trie_collect_stats(t, &stat);
    2473                 :          0 :                         trie_show_stats(seq, &stat);
    2474                 :            : #ifdef CONFIG_IP_FIB_TRIE_STATS
    2475                 :            :                         trie_show_usage(seq, t->stats);
    2476                 :            : #endif
    2477                 :            :                 }
    2478                 :            :                 cond_resched_rcu();
    2479                 :            :         }
    2480                 :            :         rcu_read_unlock();
    2481                 :            : 
    2482                 :          0 :         return 0;
    2483                 :            : }
    2484                 :            : 
    2485                 :          0 : static struct key_vector *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
    2486                 :            : {
    2487                 :          0 :         struct fib_trie_iter *iter = seq->private;
    2488                 :            :         struct net *net = seq_file_net(seq);
    2489                 :            :         loff_t idx = 0;
    2490                 :            :         unsigned int h;
    2491                 :            : 
    2492         [ #  # ]:          0 :         for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
    2493                 :          0 :                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
    2494                 :            :                 struct fib_table *tb;
    2495                 :            : 
    2496   [ #  #  #  #  :          0 :                 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
                   #  # ]
    2497                 :            :                         struct key_vector *n;
    2498                 :            : 
    2499         [ #  # ]:          0 :                         for (n = fib_trie_get_first(iter,
    2500                 :          0 :                                                     (struct trie *) tb->tb_data);
    2501                 :          0 :                              n; n = fib_trie_get_next(iter))
    2502         [ #  # ]:          0 :                                 if (pos == idx++) {
    2503                 :          0 :                                         iter->tb = tb;
    2504                 :          0 :                                         return n;
    2505                 :            :                                 }
    2506                 :            :                 }
    2507                 :            :         }
    2508                 :            : 
    2509                 :            :         return NULL;
    2510                 :            : }
    2511                 :            : 
    2512                 :          0 : static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
    2513                 :            :         __acquires(RCU)
    2514                 :            : {
    2515                 :            :         rcu_read_lock();
    2516                 :          0 :         return fib_trie_get_idx(seq, *pos);
    2517                 :            : }
    2518                 :            : 
    2519                 :          0 : static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
    2520                 :            : {
    2521                 :          0 :         struct fib_trie_iter *iter = seq->private;
    2522                 :            :         struct net *net = seq_file_net(seq);
    2523                 :          0 :         struct fib_table *tb = iter->tb;
    2524                 :            :         struct hlist_node *tb_node;
    2525                 :            :         unsigned int h;
    2526                 :            :         struct key_vector *n;
    2527                 :            : 
    2528                 :          0 :         ++*pos;
    2529                 :            :         /* next node in same table */
    2530                 :          0 :         n = fib_trie_get_next(iter);
    2531         [ #  # ]:          0 :         if (n)
    2532                 :            :                 return n;
    2533                 :            : 
    2534                 :            :         /* walk rest of this hash chain */
    2535                 :          0 :         h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
    2536         [ #  # ]:          0 :         while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
    2537                 :            :                 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
    2538                 :          0 :                 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
    2539         [ #  # ]:          0 :                 if (n)
    2540                 :            :                         goto found;
    2541                 :            :         }
    2542                 :            : 
    2543                 :            :         /* new hash chain */
    2544         [ #  # ]:          0 :         while (++h < FIB_TABLE_HASHSZ) {
    2545                 :          0 :                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
    2546   [ #  #  #  #  :          0 :                 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
                   #  # ]
    2547                 :          0 :                         n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
    2548         [ #  # ]:          0 :                         if (n)
    2549                 :            :                                 goto found;
    2550                 :            :                 }
    2551                 :            :         }
    2552                 :            :         return NULL;
    2553                 :            : 
    2554                 :            : found:
    2555                 :          0 :         iter->tb = tb;
    2556                 :          0 :         return n;
    2557                 :            : }
    2558                 :            : 
    2559                 :          0 : static void fib_trie_seq_stop(struct seq_file *seq, void *v)
    2560                 :            :         __releases(RCU)
    2561                 :            : {
    2562                 :            :         rcu_read_unlock();
    2563                 :          0 : }
    2564                 :            : 
    2565                 :            : static void seq_indent(struct seq_file *seq, int n)
    2566                 :            : {
    2567   [ #  #  #  #  :          0 :         while (n-- > 0)
                   #  # ]
    2568                 :          0 :                 seq_puts(seq, "   ");
    2569                 :            : }
    2570                 :            : 
    2571                 :          0 : static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
    2572                 :            : {
    2573   [ #  #  #  #  :          0 :         switch (s) {
                   #  # ]
    2574                 :            :         case RT_SCOPE_UNIVERSE: return "universe";
    2575                 :          0 :         case RT_SCOPE_SITE:     return "site";
    2576                 :          0 :         case RT_SCOPE_LINK:     return "link";
    2577                 :          0 :         case RT_SCOPE_HOST:     return "host";
    2578                 :          0 :         case RT_SCOPE_NOWHERE:  return "nowhere";
    2579                 :            :         default:
    2580                 :          0 :                 snprintf(buf, len, "scope=%d", s);
    2581                 :          0 :                 return buf;
    2582                 :            :         }
    2583                 :            : }
    2584                 :            : 
    2585                 :            : static const char *const rtn_type_names[__RTN_MAX] = {
    2586                 :            :         [RTN_UNSPEC] = "UNSPEC",
    2587                 :            :         [RTN_UNICAST] = "UNICAST",
    2588                 :            :         [RTN_LOCAL] = "LOCAL",
    2589                 :            :         [RTN_BROADCAST] = "BROADCAST",
    2590                 :            :         [RTN_ANYCAST] = "ANYCAST",
    2591                 :            :         [RTN_MULTICAST] = "MULTICAST",
    2592                 :            :         [RTN_BLACKHOLE] = "BLACKHOLE",
    2593                 :            :         [RTN_UNREACHABLE] = "UNREACHABLE",
    2594                 :            :         [RTN_PROHIBIT] = "PROHIBIT",
    2595                 :            :         [RTN_THROW] = "THROW",
    2596                 :            :         [RTN_NAT] = "NAT",
    2597                 :            :         [RTN_XRESOLVE] = "XRESOLVE",
    2598                 :            : };
    2599                 :            : 
    2600                 :            : static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
    2601                 :            : {
    2602   [ #  #  #  # ]:          0 :         if (t < __RTN_MAX && rtn_type_names[t])
    2603                 :            :                 return rtn_type_names[t];
    2604                 :          0 :         snprintf(buf, len, "type %u", t);
    2605                 :            :         return buf;
    2606                 :            : }
    2607                 :            : 
    2608                 :            : /* Pretty print the trie */
    2609                 :          0 : static int fib_trie_seq_show(struct seq_file *seq, void *v)
    2610                 :            : {
    2611                 :          0 :         const struct fib_trie_iter *iter = seq->private;
    2612                 :            :         struct key_vector *n = v;
    2613                 :            : 
    2614         [ #  # ]:          0 :         if (IS_TRIE(node_parent_rcu(n)))
    2615                 :          0 :                 fib_table_print(seq, iter->tb);
    2616                 :            : 
    2617         [ #  # ]:          0 :         if (IS_TNODE(n)) {
    2618                 :          0 :                 __be32 prf = htonl(n->key);
    2619                 :            : 
    2620                 :          0 :                 seq_indent(seq, iter->depth-1);
    2621                 :          0 :                 seq_printf(seq, "  +-- %pI4/%zu %u %u %u\n",
    2622                 :          0 :                            &prf, KEYLENGTH - n->pos - n->bits, n->bits,
    2623                 :            :                            tn_info(n)->full_children,
    2624                 :            :                            tn_info(n)->empty_children);
    2625                 :            :         } else {
    2626                 :          0 :                 __be32 val = htonl(n->key);
    2627                 :            :                 struct fib_alias *fa;
    2628                 :            : 
    2629                 :          0 :                 seq_indent(seq, iter->depth);
    2630                 :          0 :                 seq_printf(seq, "  |-- %pI4\n", &val);
    2631                 :            : 
    2632   [ #  #  #  #  :          0 :                 hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) {
                   #  # ]
    2633                 :            :                         char buf1[32], buf2[32];
    2634                 :            : 
    2635                 :          0 :                         seq_indent(seq, iter->depth + 1);
    2636                 :          0 :                         seq_printf(seq, "  /%zu %s %s",
    2637                 :          0 :                                    KEYLENGTH - fa->fa_slen,
    2638                 :            :                                    rtn_scope(buf1, sizeof(buf1),
    2639                 :          0 :                                              fa->fa_info->fib_scope),
    2640                 :            :                                    rtn_type(buf2, sizeof(buf2),
    2641                 :          0 :                                             fa->fa_type));
    2642         [ #  # ]:          0 :                         if (fa->fa_tos)
    2643                 :          0 :                                 seq_printf(seq, " tos=%d", fa->fa_tos);
    2644                 :          0 :                         seq_putc(seq, '\n');
    2645                 :            :                 }
    2646                 :            :         }
    2647                 :            : 
    2648                 :          0 :         return 0;
    2649                 :            : }
    2650                 :            : 
    2651                 :            : static const struct seq_operations fib_trie_seq_ops = {
    2652                 :            :         .start  = fib_trie_seq_start,
    2653                 :            :         .next   = fib_trie_seq_next,
    2654                 :            :         .stop   = fib_trie_seq_stop,
    2655                 :            :         .show   = fib_trie_seq_show,
    2656                 :            : };
    2657                 :            : 
    2658                 :            : struct fib_route_iter {
    2659                 :            :         struct seq_net_private p;
    2660                 :            :         struct fib_table *main_tb;
    2661                 :            :         struct key_vector *tnode;
    2662                 :            :         loff_t  pos;
    2663                 :            :         t_key   key;
    2664                 :            : };
    2665                 :            : 
    2666                 :          0 : static struct key_vector *fib_route_get_idx(struct fib_route_iter *iter,
    2667                 :            :                                             loff_t pos)
    2668                 :            : {
    2669                 :          0 :         struct key_vector *l, **tp = &iter->tnode;
    2670                 :            :         t_key key;
    2671                 :            : 
    2672                 :            :         /* use cached location of previously found key */
    2673   [ #  #  #  # ]:          0 :         if (iter->pos > 0 && pos >= iter->pos) {
    2674                 :          0 :                 key = iter->key;
    2675                 :            :         } else {
    2676                 :          0 :                 iter->pos = 1;
    2677                 :            :                 key = 0;
    2678                 :            :         }
    2679                 :            : 
    2680                 :          0 :         pos -= iter->pos;
    2681                 :            : 
    2682   [ #  #  #  # ]:          0 :         while ((l = leaf_walk_rcu(tp, key)) && (pos-- > 0)) {
    2683                 :          0 :                 key = l->key + 1;
    2684                 :          0 :                 iter->pos++;
    2685                 :            :                 l = NULL;
    2686                 :            : 
    2687                 :            :                 /* handle unlikely case of a key wrap */
    2688         [ #  # ]:          0 :                 if (!key)
    2689                 :            :                         break;
    2690                 :            :         }
    2691                 :            : 
    2692         [ #  # ]:          0 :         if (l)
    2693                 :          0 :                 iter->key = l->key;       /* remember it */
    2694                 :            :         else
    2695                 :          0 :                 iter->pos = 0;               /* forget it */
    2696                 :            : 
    2697                 :          0 :         return l;
    2698                 :            : }
    2699                 :            : 
    2700                 :          0 : static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
    2701                 :            :         __acquires(RCU)
    2702                 :            : {
    2703                 :          0 :         struct fib_route_iter *iter = seq->private;
    2704                 :            :         struct fib_table *tb;
    2705                 :            :         struct trie *t;
    2706                 :            : 
    2707                 :            :         rcu_read_lock();
    2708                 :            : 
    2709                 :          0 :         tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
    2710         [ #  # ]:          0 :         if (!tb)
    2711                 :            :                 return NULL;
    2712                 :            : 
    2713                 :          0 :         iter->main_tb = tb;
    2714                 :          0 :         t = (struct trie *)tb->tb_data;
    2715                 :          0 :         iter->tnode = t->kv;
    2716                 :            : 
    2717         [ #  # ]:          0 :         if (*pos != 0)
    2718                 :          0 :                 return fib_route_get_idx(iter, *pos);
    2719                 :            : 
    2720                 :          0 :         iter->pos = 0;
    2721                 :          0 :         iter->key = KEY_MAX;
    2722                 :            : 
    2723                 :          0 :         return SEQ_START_TOKEN;
    2724                 :            : }
    2725                 :            : 
    2726                 :          0 : static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
    2727                 :            : {
    2728                 :          0 :         struct fib_route_iter *iter = seq->private;
    2729                 :            :         struct key_vector *l = NULL;
    2730                 :          0 :         t_key key = iter->key + 1;
    2731                 :            : 
    2732                 :          0 :         ++*pos;
    2733                 :            : 
    2734                 :            :         /* only allow key of 0 for start of sequence */
    2735         [ #  # ]:          0 :         if ((v == SEQ_START_TOKEN) || key)
    2736                 :          0 :                 l = leaf_walk_rcu(&iter->tnode, key);
    2737                 :            : 
    2738         [ #  # ]:          0 :         if (l) {
    2739                 :          0 :                 iter->key = l->key;
    2740                 :          0 :                 iter->pos++;
    2741                 :            :         } else {
    2742                 :          0 :                 iter->pos = 0;
    2743                 :            :         }
    2744                 :            : 
    2745                 :          0 :         return l;
    2746                 :            : }
    2747                 :            : 
    2748                 :          0 : static void fib_route_seq_stop(struct seq_file *seq, void *v)
    2749                 :            :         __releases(RCU)
    2750                 :            : {
    2751                 :            :         rcu_read_unlock();
    2752                 :          0 : }
    2753                 :            : 
    2754                 :          0 : static unsigned int fib_flag_trans(int type, __be32 mask, struct fib_info *fi)
    2755                 :            : {
    2756                 :            :         unsigned int flags = 0;
    2757                 :            : 
    2758         [ #  # ]:          0 :         if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
    2759                 :            :                 flags = RTF_REJECT;
    2760         [ #  # ]:          0 :         if (fi) {
    2761                 :          0 :                 const struct fib_nh_common *nhc = fib_info_nhc(fi, 0);
    2762                 :            : 
    2763         [ #  # ]:          0 :                 if (nhc->nhc_gw.ipv4)
    2764                 :          0 :                         flags |= RTF_GATEWAY;
    2765                 :            :         }
    2766         [ #  # ]:          0 :         if (mask == htonl(0xFFFFFFFF))
    2767                 :          0 :                 flags |= RTF_HOST;
    2768                 :          0 :         flags |= RTF_UP;
    2769                 :          0 :         return flags;
    2770                 :            : }
    2771                 :            : 
    2772                 :            : /*
    2773                 :            :  *      This outputs /proc/net/route.
    2774                 :            :  *      The format of the file is not supposed to be changed
    2775                 :            :  *      and needs to be same as fib_hash output to avoid breaking
    2776                 :            :  *      legacy utilities
    2777                 :            :  */
    2778                 :          0 : static int fib_route_seq_show(struct seq_file *seq, void *v)
    2779                 :            : {
    2780                 :          0 :         struct fib_route_iter *iter = seq->private;
    2781                 :          0 :         struct fib_table *tb = iter->main_tb;
    2782                 :            :         struct fib_alias *fa;
    2783                 :            :         struct key_vector *l = v;
    2784                 :            :         __be32 prefix;
    2785                 :            : 
    2786         [ #  # ]:          0 :         if (v == SEQ_START_TOKEN) {
    2787                 :          0 :                 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
    2788                 :            :                            "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
    2789                 :            :                            "\tWindow\tIRTT");
    2790                 :          0 :                 return 0;
    2791                 :            :         }
    2792                 :            : 
    2793                 :          0 :         prefix = htonl(l->key);
    2794                 :            : 
    2795   [ #  #  #  #  :          0 :         hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) {
                   #  # ]
    2796                 :          0 :                 struct fib_info *fi = fa->fa_info;
    2797                 :          0 :                 __be32 mask = inet_make_mask(KEYLENGTH - fa->fa_slen);
    2798                 :          0 :                 unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
    2799                 :            : 
    2800         [ #  # ]:          0 :                 if ((fa->fa_type == RTN_BROADCAST) ||
    2801                 :            :                     (fa->fa_type == RTN_MULTICAST))
    2802                 :          0 :                         continue;
    2803                 :            : 
    2804         [ #  # ]:          0 :                 if (fa->tb_id != tb->tb_id)
    2805                 :          0 :                         continue;
    2806                 :            : 
    2807                 :            :                 seq_setwidth(seq, 127);
    2808                 :            : 
    2809         [ #  # ]:          0 :                 if (fi) {
    2810                 :          0 :                         struct fib_nh_common *nhc = fib_info_nhc(fi, 0);
    2811                 :            :                         __be32 gw = 0;
    2812                 :            : 
    2813         [ #  # ]:          0 :                         if (nhc->nhc_gw_family == AF_INET)
    2814                 :          0 :                                 gw = nhc->nhc_gw.ipv4;
    2815                 :            : 
    2816   [ #  #  #  # ]:          0 :                         seq_printf(seq,
    2817                 :            :                                    "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
    2818                 :            :                                    "%d\t%08X\t%d\t%u\t%u",
    2819                 :          0 :                                    nhc->nhc_dev ? nhc->nhc_dev->name : "*",
    2820                 :            :                                    prefix, gw, flags, 0, 0,
    2821                 :            :                                    fi->fib_priority,
    2822                 :            :                                    mask,
    2823                 :          0 :                                    (fi->fib_advmss ?
    2824                 :            :                                     fi->fib_advmss + 40 : 0),
    2825                 :            :                                    fi->fib_window,
    2826                 :          0 :                                    fi->fib_rtt >> 3);
    2827                 :            :                 } else {
    2828                 :          0 :                         seq_printf(seq,
    2829                 :            :                                    "*\t%08X\t%08X\t%04X\t%d\t%u\t"
    2830                 :            :                                    "%d\t%08X\t%d\t%u\t%u",
    2831                 :            :                                    prefix, 0, flags, 0, 0, 0,
    2832                 :            :                                    mask, 0, 0, 0);
    2833                 :            :                 }
    2834                 :          0 :                 seq_pad(seq, '\n');
    2835                 :            :         }
    2836                 :            : 
    2837                 :            :         return 0;
    2838                 :            : }
    2839                 :            : 
    2840                 :            : static const struct seq_operations fib_route_seq_ops = {
    2841                 :            :         .start  = fib_route_seq_start,
    2842                 :            :         .next   = fib_route_seq_next,
    2843                 :            :         .stop   = fib_route_seq_stop,
    2844                 :            :         .show   = fib_route_seq_show,
    2845                 :            : };
    2846                 :            : 
    2847                 :        207 : int __net_init fib_proc_init(struct net *net)
    2848                 :            : {
    2849         [ +  - ]:        207 :         if (!proc_create_net("fib_trie", 0444, net->proc_net, &fib_trie_seq_ops,
    2850                 :            :                         sizeof(struct fib_trie_iter)))
    2851                 :            :                 goto out1;
    2852                 :            : 
    2853         [ +  - ]:        207 :         if (!proc_create_net_single("fib_triestat", 0444, net->proc_net,
    2854                 :            :                         fib_triestat_seq_show, NULL))
    2855                 :            :                 goto out2;
    2856                 :            : 
    2857         [ -  + ]:        207 :         if (!proc_create_net("route", 0444, net->proc_net, &fib_route_seq_ops,
    2858                 :            :                         sizeof(struct fib_route_iter)))
    2859                 :            :                 goto out3;
    2860                 :            : 
    2861                 :            :         return 0;
    2862                 :            : 
    2863                 :            : out3:
    2864                 :          0 :         remove_proc_entry("fib_triestat", net->proc_net);
    2865                 :            : out2:
    2866                 :          0 :         remove_proc_entry("fib_trie", net->proc_net);
    2867                 :            : out1:
    2868                 :            :         return -ENOMEM;
    2869                 :            : }
    2870                 :            : 
    2871                 :          0 : void __net_exit fib_proc_exit(struct net *net)
    2872                 :            : {
    2873                 :          0 :         remove_proc_entry("fib_trie", net->proc_net);
    2874                 :          0 :         remove_proc_entry("fib_triestat", net->proc_net);
    2875                 :          0 :         remove_proc_entry("route", net->proc_net);
    2876                 :          0 : }
    2877                 :            : 
    2878                 :            : #endif /* CONFIG_PROC_FS */

Generated by: LCOV version 1.14