src/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, i.e. PLYs
  51    1 => empty (adjacency index of zero is special miss adjacency). */
  52 typedef u32 ip4_mtrie_leaf_t;
  53
  54 #define IP4_MTRIE_LEAF_EMPTY (1 + 2 * 0)
  55
  56 /**
  57  * @brief the 16 way stride that is the top PLY of the mtrie
  58  * We do not maintain the count of 'real' leaves in this PLY, since
  59  * it is never removed. The FIB will destroy the mtrie and the ply once
  60  * the FIB is destroyed.
  61  */
  62 #define PLY_16_SIZE (1<<16)
  63 typedef struct ip4_mtrie_16_ply_t_
  64 {
  65   /**
  66    * The leaves/slots/buckets to be filed with leafs
  67    */
  68   union
  69   {
  70     ip4_mtrie_leaf_t leaves[PLY_16_SIZE];
  71
  72 #ifdef CLIB_HAVE_VEC128
  73     u32x4 leaves_as_u32x4[PLY_16_SIZE / 4];
  74 #endif
  75   };
  76
  77   /**
  78    * Prefix length for terminal leaves.
  79    */
  80   u8 dst_address_bits_of_leaves[PLY_16_SIZE];
  81 } ip4_mtrie_16_ply_t;
  82
  83 /**
  84  * @brief One ply of the 4 ply mtrie fib.
  85  */
  86 typedef struct ip4_mtrie_8_ply_t_
  87 {
  88   /**
  89    * The leaves/slots/buckets to be filed with leafs
  90    */
  91   union
  92   {
  93     ip4_mtrie_leaf_t leaves[256];
  94
  95 #ifdef CLIB_HAVE_VEC128
  96     u32x4 leaves_as_u32x4[256 / 4];
  97 #endif
  98   };
  99
 100   /**
 101    * Prefix length for leaves/ply.
 102    */
 103   u8 dst_address_bits_of_leaves[256];
 104
 105   /**
 106    * Number of non-empty leafs (whether terminal or not).
 107    */
 108   i32 n_non_empty_leafs;
 109
 110   /**
 111    * The length of the ply's covering prefix. Also a measure of its depth
 112    * If a leaf in a slot has a mask length longer than this then it is
 113    * 'non-empty'. Otherwise it is the value of the cover.
 114    */
 115   i32 dst_address_bits_base;
 116
 117   /* Pad to cache line boundary. */
 118   u8 pad[CLIB_CACHE_LINE_BYTES - 2 * sizeof (i32)];
 119 } ip4_mtrie_8_ply_t;
 120
 121 STATIC_ASSERT (0 == sizeof (ip4_mtrie_8_ply_t) % CLIB_CACHE_LINE_BYTES,
 122                "IP4 Mtrie ply cache line");
 123
 124 /**
 125  * @brief The mutiway-TRIE with a 16-8-8 stride.
 126  * There is no data associated with the mtrie apart from the top PLY
 127  */
 128 typedef struct
 129 {
 130   /**
 131    * Embed the PLY with the mtrie struct. This means that the Data-plane
 132    * 'get me the mtrie' returns the first ply, and not an indirect 'pointer'
 133    * to it. therefore no cacheline misses in the data-path.
 134    */
 135   ip4_mtrie_16_ply_t root_ply;
 136 } ip4_mtrie_16_t;
 137
 138 /**
 139  * @brief The mutiway-TRIE with a 8-8-8-8 stride.
 140  * There is no data associated with the mtrie apart from the top PLY
 141  */
 142 typedef struct
 143 {
 144   /* pool index of the root ply */
 145   u32 root_ply;
 146 } ip4_mtrie_8_t;
 147
 148 /**
 149  * @brief Initialise an mtrie
 150  */
 151 void ip4_mtrie_16_init (ip4_mtrie_16_t *m);
 152 void ip4_mtrie_8_init (ip4_mtrie_8_t *m);
 153
 154 /**
 155  * @brief Free an mtrie, It must be empty when free'd
 156  */
 157 void ip4_mtrie_16_free (ip4_mtrie_16_t *m);
 158 void ip4_mtrie_8_free (ip4_mtrie_8_t *m);
 159
 160 /**
 161  * @brief Add a route/entry to the mtrie
 162  */
 163 void ip4_mtrie_16_route_add (ip4_mtrie_16_t *m,
 164                              const ip4_address_t *dst_address,
 165                              u32 dst_address_length, u32 adj_index);
 166 void ip4_mtrie_8_route_add (ip4_mtrie_8_t *m, const ip4_address_t *dst_address,
 167                             u32 dst_address_length, u32 adj_index);
 168
 169 /**
 170  * @brief remove a route/entry to the mtrie
 171  */
 172 void ip4_mtrie_16_route_del (ip4_mtrie_16_t *m,
 173                              const ip4_address_t *dst_address,
 174                              u32 dst_address_length, u32 adj_index,
 175                              u32 cover_address_length, u32 cover_adj_index);
 176 void ip4_mtrie_8_route_del (ip4_mtrie_8_t *m, const ip4_address_t *dst_address,
 177                             u32 dst_address_length, u32 adj_index,
 178                             u32 cover_address_length, u32 cover_adj_index);
 179
 180 /**
 181  * @brief return the memory used by the table
 182  */
 183 uword ip4_mtrie_16_memory_usage (ip4_mtrie_16_t *m);
 184 uword ip4_mtrie_8_memory_usage (ip4_mtrie_8_t *m);
 185
 186 /**
 187  * @brief Format/display the contents of the mtrie
 188  */
 189 format_function_t format_ip4_mtrie_16;
 190 format_function_t format_ip4_mtrie_8;
 191
 192 /**
 193  * @brief A global pool of 8bit stride plys
 194  */
 195 extern ip4_mtrie_8_ply_t *ip4_ply_pool;
 196
 197 /**
 198  * Is the leaf terminal (i.e. an LB index) or non-terminal (i.e. a PLY index)
 199  */
 200 always_inline u32
 201 ip4_mtrie_leaf_is_terminal (ip4_mtrie_leaf_t n)
 202 {
 203   return n & 1;
 204 }
 205
 206 /**
 207  * From the stored slot value extract the LB index value
 208  */
 209 always_inline u32
 210 ip4_mtrie_leaf_get_adj_index (ip4_mtrie_leaf_t n)
 211 {
 212   ASSERT (ip4_mtrie_leaf_is_terminal (n));
 213   return n >> 1;
 214 }
 215
 216 /**
 217  * @brief Lookup step.  Processes 1 byte of 4 byte ip4 address.
 218  */
 219 always_inline ip4_mtrie_leaf_t
 220 ip4_mtrie_16_lookup_step (ip4_mtrie_leaf_t current_leaf,
 221                           const ip4_address_t *dst_address,
 222                           u32 dst_address_byte_index)
 223 {
 224   ip4_mtrie_8_ply_t *ply;
 225
 226   uword current_is_terminal = ip4_mtrie_leaf_is_terminal (current_leaf);
 227
 228   if (!current_is_terminal)
 229     {
 230       ply = ip4_ply_pool + (current_leaf >> 1);
 231       return (ply->leaves[dst_address->as_u8[dst_address_byte_index]]);
 232     }
 233
 234   return current_leaf;
 235 }
 236
 237 /**
 238  * @brief Lookup step number 1.  Processes 2 bytes of 4 byte ip4 address.
 239  */
 240 always_inline ip4_mtrie_leaf_t
 241 ip4_mtrie_16_lookup_step_one (const ip4_mtrie_16_t *m,
 242                               const ip4_address_t *dst_address)
 243 {
 244   ip4_mtrie_leaf_t next_leaf;
 245
 246   next_leaf = m->root_ply.leaves[dst_address->as_u16[0]];
 247
 248   return next_leaf;
 249 }
 250
 251 always_inline ip4_mtrie_leaf_t
 252 ip4_mtrie_8_lookup_step (ip4_mtrie_leaf_t current_leaf,
 253                          const ip4_address_t *dst_address,
 254                          u32 dst_address_byte_index)
 255 {
 256   ip4_mtrie_8_ply_t *ply;
 257
 258   uword current_is_terminal = ip4_mtrie_leaf_is_terminal (current_leaf);
 259
 260   if (!current_is_terminal)
 261     {
 262       ply = ip4_ply_pool + (current_leaf >> 1);
 263       return (ply->leaves[dst_address->as_u8[dst_address_byte_index]]);
 264     }
 265
 266   return current_leaf;
 267 }
 268
 269 always_inline ip4_mtrie_leaf_t
 270 ip4_mtrie_8_lookup_step_one (const ip4_mtrie_8_t *m,
 271                              const ip4_address_t *dst_address)
 272 {
 273   ip4_mtrie_leaf_t next_leaf;
 274   ip4_mtrie_8_ply_t *ply;
 275
 276   ply = pool_elt_at_index (ip4_ply_pool, m->root_ply);
 277   next_leaf = ply->leaves[dst_address->as_u8[0]];
 278
 279   return next_leaf;
 280 }
 281
 282 #endif /* included_ip_ip4_fib_h */
 283
 284 /*
 285  * fd.io coding-style-patch-verification: ON
 286  *
 287  * Local Variables:
 288  * eval: (c-set-style "gnu")
 289  * End:
 290  */