vnet/vnet/ip/ip4_mtrie.h

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 /*
  16  * ip/ip4_fib.h: ip4 mtrie fib
  17  *
  18  * Copyright (c) 2012 Eliot Dresselhaus
  19  *
  20  * Permission is hereby granted, free of charge, to any person obtaining
  21  * a copy of this software and associated documentation files (the
  22  * "Software"), to deal in the Software without restriction, including
  23  * without limitation the rights to use, copy, modify, merge, publish,
  24  * distribute, sublicense, and/or sell copies of the Software, and to
  25  * permit persons to whom the Software is furnished to do so, subject to
  26  * the following conditions:
  27  *
  28  * The above copyright notice and this permission notice shall be
  29  * included in all copies or substantial portions of the Software.
  30  *
  31  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  32  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  33  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  34  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  35  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  36  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  37  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  38  */
  39
  40 #ifndef included_ip_ip4_fib_h
  41 #define included_ip_ip4_fib_h
  42
  43 #include <vppinfra/cache.h>
  44 #include <vppinfra/vector.h>
  45 #include <vnet/ip/lookup.h>
  46 #include <vnet/ip/ip4_packet.h> /* for ip4_address_t */
  47
  48 /* ip4 fib leafs: 4 ply 8-8-8-8 mtrie.
  49    1 + 2*adj_index for terminal leaves.
  50    0 + 2*next_ply_index for non-terminals.
  51    1 => empty (adjacency index of zero is special miss adjacency). */
  52 typedef u32 ip4_fib_mtrie_leaf_t;
  53
  54 #define IP4_FIB_MTRIE_LEAF_EMPTY (1 + 2*0)
  55 #define IP4_FIB_MTRIE_LEAF_ROOT  (0 + 2*0)
  56
  57 always_inline u32
  58 ip4_fib_mtrie_leaf_is_empty (ip4_fib_mtrie_leaf_t n)
  59 {
  60   return n == IP4_FIB_MTRIE_LEAF_EMPTY;
  61 }
  62
  63 always_inline u32
  64 ip4_fib_mtrie_leaf_is_non_empty (ip4_fib_mtrie_leaf_t n)
  65 {
  66   return n != IP4_FIB_MTRIE_LEAF_EMPTY;
  67 }
  68
  69 always_inline u32
  70 ip4_fib_mtrie_leaf_is_terminal (ip4_fib_mtrie_leaf_t n)
  71 {
  72   return n & 1;
  73 }
  74
  75 always_inline u32
  76 ip4_fib_mtrie_leaf_get_adj_index (ip4_fib_mtrie_leaf_t n)
  77 {
  78   ASSERT (ip4_fib_mtrie_leaf_is_terminal (n));
  79   return n >> 1;
  80 }
  81
  82 always_inline ip4_fib_mtrie_leaf_t
  83 ip4_fib_mtrie_leaf_set_adj_index (u32 adj_index)
  84 {
  85   ip4_fib_mtrie_leaf_t l;
  86   l = 1 + 2 * adj_index;
  87   ASSERT (ip4_fib_mtrie_leaf_get_adj_index (l) == adj_index);
  88   return l;
  89 }
  90
  91 always_inline u32
  92 ip4_fib_mtrie_leaf_is_next_ply (ip4_fib_mtrie_leaf_t n)
  93 {
  94   return (n & 1) == 0;
  95 }
  96
  97 always_inline u32
  98 ip4_fib_mtrie_leaf_get_next_ply_index (ip4_fib_mtrie_leaf_t n)
  99 {
 100   ASSERT (ip4_fib_mtrie_leaf_is_next_ply (n));
 101   return n >> 1;
 102 }
 103
 104 always_inline ip4_fib_mtrie_leaf_t
 105 ip4_fib_mtrie_leaf_set_next_ply_index (u32 i)
 106 {
 107   ip4_fib_mtrie_leaf_t l;
 108   l = 0 + 2 * i;
 109   ASSERT (ip4_fib_mtrie_leaf_get_next_ply_index (l) == i);
 110   return l;
 111 }
 112
 113 /* One ply of the 4 ply mtrie fib. */
 114 typedef struct
 115 {
 116   union
 117   {
 118     ip4_fib_mtrie_leaf_t leaves[256];
 119
 120 #ifdef CLIB_HAVE_VEC128
 121     u32x4 leaves_as_u32x4[256 / 4];
 122 #endif
 123   };
 124
 125   /* Prefix length for terminal leaves. */
 126   u8 dst_address_bits_of_leaves[256];
 127
 128   /* Number of non-empty leafs (whether terminal or not). */
 129   i32 n_non_empty_leafs;
 130
 131   /* Pad to cache line boundary. */
 132   u8 pad[CLIB_CACHE_LINE_BYTES - 1 * sizeof (i32)];
 133 }
 134 ip4_fib_mtrie_ply_t;
 135
 136 STATIC_ASSERT (0 == sizeof (ip4_fib_mtrie_ply_t) % CLIB_CACHE_LINE_BYTES,
 137                "IP4 Mtrie ply cache line");
 138
 139 typedef struct
 140 {
 141   /* Pool of plies.  Index zero is root ply. */
 142   ip4_fib_mtrie_ply_t *ply_pool;
 143
 144   /* Special case leaf for default route 0.0.0.0/0. */
 145   ip4_fib_mtrie_leaf_t default_leaf;
 146 } ip4_fib_mtrie_t;
 147
 148 void ip4_fib_mtrie_init (ip4_fib_mtrie_t * m);
 149
 150 struct ip4_fib_t;
 151
 152 void ip4_fib_mtrie_add_del_route (struct ip4_fib_t *f,
 153                                   ip4_address_t dst_address,
 154                                   u32 dst_address_length,
 155                                   u32 adj_index, u32 is_del);
 156
 157 /* Returns adjacency index. */
 158 u32 ip4_mtrie_lookup_address (ip4_fib_mtrie_t * m, ip4_address_t dst);
 159
 160 format_function_t format_ip4_fib_mtrie;
 161
 162 /* Lookup step.  Processes 1 byte of 4 byte ip4 address. */
 163 always_inline ip4_fib_mtrie_leaf_t
 164 ip4_fib_mtrie_lookup_step (ip4_fib_mtrie_t * m,
 165                            ip4_fib_mtrie_leaf_t current_leaf,
 166                            const ip4_address_t * dst_address,
 167                            u32 dst_address_byte_index)
 168 {
 169   ip4_fib_mtrie_leaf_t next_leaf;
 170   ip4_fib_mtrie_ply_t *ply;
 171   uword current_is_terminal = ip4_fib_mtrie_leaf_is_terminal (current_leaf);
 172
 173   ply = m->ply_pool + (current_is_terminal ? 0 : (current_leaf >> 1));
 174   next_leaf = ply->leaves[dst_address->as_u8[dst_address_byte_index]];
 175   next_leaf = current_is_terminal ? current_leaf : next_leaf;
 176
 177   return next_leaf;
 178 }
 179
 180 #endif /* included_ip_ip4_fib_h */
 181
 182 /*
 183  * fd.io coding-style-patch-verification: ON
 184  *
 185  * Local Variables:
 186  * eval: (c-set-style "gnu")
 187  * End:
 188  */