src/vnet/mfib/mfib_table.h

   1 /*
   2  * Copyright (c) 2016 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 #ifndef __MFIB_TABLE_H__
  17 #define __MFIB_TABLE_H__
  18
  19 #include <vnet/ip/ip.h>
  20 #include <vnet/adj/adj.h>
  21 #include <vnet/dpo/replicate_dpo.h>
  22
  23 #include <vnet/mfib/mfib_types.h>
  24
  25 /**
  26  * Keep a lock per-source and a total
  27  */
  28 #define MFIB_TABLE_N_LOCKS (MFIB_N_SOURCES+1)
  29 #define MFIB_TABLE_TOTAL_LOCKS MFIB_N_SOURCES
  30
  31 /**
  32  * Flags for the source data
  33  */
  34 typedef enum mfib_table_attribute_t_ {
  35     /**
  36      * Marker. Add new values after this one.
  37      */
  38     MFIB_TABLE_ATTRIBUTE_FIRST,
  39     /**
  40      * the table is currently resync-ing
  41      */
  42     MFIB_TABLE_ATTRIBUTE_RESYNC = MFIB_TABLE_ATTRIBUTE_FIRST,
  43     /**
  44      * Marker. add new entries before this one.
  45      */
  46     MFIB_TABLE_ATTRIBUTE_LAST = MFIB_TABLE_ATTRIBUTE_RESYNC,
  47 } mfib_table_attribute_t;
  48
  49 #define MFIB_TABLE_ATTRIBUTE_MAX (MFIB_TABLE_ATTRIBUTE_LAST+1)
  50
  51 #define MFIB_TABLE_ATTRIBUTES {                  \
  52     [MFIB_TABLE_ATTRIBUTE_RESYNC]  = "resync",    \
  53 }
  54
  55 #define FOR_EACH_MFIB_TABLE_ATTRIBUTE(_item)            \
  56     for (_item = MFIB_TABLE_ATTRIBUTE_FIRST;            \
  57          _item < MFIB_TABLE_ATTRIBUTE_MAX;              \
  58          _item++)
  59
  60 typedef enum mfib_table_flags_t_ {
  61     MFIB_TABLE_FLAG_NONE   = 0,
  62     MFIB_TABLE_FLAG_RESYNC  = (1 << MFIB_TABLE_ATTRIBUTE_RESYNC),
  63 } __attribute__ ((packed)) mfib_table_flags_t;
  64
  65 extern u8* format_mfib_table_flags(u8 *s, va_list *args);
  66
  67 /**
  68  * @brief
  69  *   A protocol Independent IP multicast FIB table
  70  */
  71 typedef struct mfib_table_t_
  72 {
  73     /**
  74      * Required for pool_get_aligned
  75      */
  76     CLIB_CACHE_LINE_ALIGN_MARK(cacheline0);
  77
  78     /**
  79      * A union of the protocol specific FIBs that provide the
  80      * underlying LPM mechanism.
  81      * This element is first in the struct so that it is in the
  82      * first cache line.
  83      */
  84     union {
  85         ip4_mfib_t v4;
  86         ip6_mfib_t v6;
  87     };
  88
  89     /**
  90      * Which protocol this table serves. Used to switch on the union above.
  91      */
  92     fib_protocol_t mft_proto;
  93
  94     /**
  95      * table falgs
  96      */
  97     mfib_table_flags_t mft_flags;
  98
  99     /**
 100      * number of locks on the table
 101      */
 102     u16 mft_locks[MFIB_TABLE_N_LOCKS];
 103
 104     /**
 105      * Table ID (hash key) for this FIB.
 106      */
 107     u32 mft_table_id;
 108
 109     /**
 110      * resync epoch
 111      */
 112     u32 mft_epoch;
 113
 114     /**
 115      * Index into FIB vector.
 116      */
 117     fib_node_index_t mft_index;
 118
 119     /**
 120      * Total route counters
 121      */
 122     u32 mft_total_route_counts;
 123
 124     /**
 125      * Table description
 126      */
 127     u8* mft_desc;
 128 } mfib_table_t;
 129
 130 /**
 131  * @brief
 132  *  Format the description/name of the table
 133  */
 134 extern u8* format_mfib_table_name(u8* s, va_list *ap);
 135
 136 /**
 137  * @brief
 138  *  Perfom a longest prefix match in the non-forwarding table
 139  *
 140  * @param fib_index
 141  *  The index of the FIB
 142  *
 143  * @param prefix
 144  *  The prefix to lookup
 145  *
 146  * @return
 147  *  The index of the fib_entry_t for the best match, which may be the default route
 148  */
 149 extern fib_node_index_t mfib_table_lookup(u32 fib_index,
 150                                          const mfib_prefix_t *prefix);
 151
 152 /**
 153  * @brief
 154  *  Perfom an exact match in the non-forwarding table
 155  *
 156  * @param fib_index
 157  *  The index of the FIB
 158  *
 159  * @param prefix
 160  *  The prefix to lookup
 161  *
 162  * @return
 163  *  The index of the fib_entry_t for the exact match, or INVALID
 164  *  is there is no match.
 165  */
 166 extern fib_node_index_t mfib_table_lookup_exact_match(u32 fib_index,
 167                                                       const mfib_prefix_t *prefix);
 168
 169 /**
 170  * @brief
 171  * Add a new (with no replication) or lock an existing entry
 172  *
 173  * @param prefix
 174  *  The prefix for the entry to add
 175  *
 176  * @return
 177  *  the index of the fib_entry_t that is created (or existed already).
 178  */
 179 extern fib_node_index_t mfib_table_entry_update(u32 fib_index,
 180                                                 const mfib_prefix_t *prefix,
 181                                                 mfib_source_t source,
 182                                                 fib_rpf_id_t rpf_id,
 183                                                 mfib_entry_flags_t flags);
 184
 185 /**
 186  * @brief
 187  *  Add n paths to an entry (aka route) in the FIB. If the entry does not
 188  *  exist, it will be created.
 189  * See the documentation for fib_route_path_t for more descirptions of
 190  * the path parameters.
 191  *
 192  * @param fib_index
 193  *  The index of the FIB
 194  *
 195  * @param prefix
 196  *  The prefix for the entry to add
 197  *
 198  * @param source
 199  *  The ID of the client/source adding the entry.
 200  *
 201  * @param flags
 202  *  Flags for the entry.
 203  *
 204  * @param rpaths
 205  *  A vector of paths.
 206  *
 207  * @return
 208  *  the index of the fib_entry_t that is created (or existed already).
 209  */
 210 extern fib_node_index_t mfib_table_entry_path_update(u32 fib_index,
 211                                                      const mfib_prefix_t *prefix,
 212                                                      mfib_source_t source,
 213                                                      const fib_route_path_t *rpath);
 214 extern fib_node_index_t mfib_table_entry_paths_update(u32 fib_index,
 215                                                       const mfib_prefix_t *prefix,
 216                                                       mfib_source_t source,
 217                                                       const fib_route_path_t *rpath);
 218
 219 /**
 220  * @brief
 221  * Remove n paths to an entry (aka route) in the FIB. If this is the entry's
 222  * last path, then the entry will be removed, unless it has other sources.
 223  * See the documentation for fib_route_path_t for more descirptions of
 224  * the path parameters.
 225  *
 226  * @param fib_index
 227  *  The index of the FIB
 228  *
 229  * @param prefix
 230  *  The prefix for the entry to add
 231  *
 232  * @param source
 233  *  The ID of the client/source adding the entry.
 234  *
 235  * @param rpaths
 236  *  A vector of paths.
 237  */
 238 extern void mfib_table_entry_path_remove(u32 fib_index,
 239                                          const mfib_prefix_t *prefix,
 240                                          mfib_source_t source,
 241                                          const fib_route_path_t *paths);
 242 extern void mfib_table_entry_paths_remove(u32 fib_index,
 243                                           const mfib_prefix_t *prefix,
 244                                           mfib_source_t source,
 245                                           const fib_route_path_t *paths);
 246
 247
 248
 249 /**
 250  * @brief
 251  *  Delete a FIB entry. If the entry has no more sources, then it is
 252  * removed from the table.
 253  *
 254  * @param fib_index
 255  *  The index of the FIB
 256  *
 257  * @param prefix
 258  *  The prefix for the entry to remove
 259  *
 260  * @param source
 261  *  The ID of the client/source adding the entry.
 262  */
 263 extern void mfib_table_entry_delete(u32 fib_index,
 264                                     const mfib_prefix_t *prefix,
 265                                     mfib_source_t source);
 266
 267 /**
 268  * @brief
 269  *  Delete a FIB entry. If the entry has no more sources, then it is
 270  * removed from the table.
 271  *
 272  * @param entry_index
 273  *  The index of the FIB entry
 274  *
 275  * @param source
 276  *  The ID of the client/source adding the entry.
 277  */
 278 extern void mfib_table_entry_delete_index(fib_node_index_t entry_index,
 279                                           mfib_source_t source);
 280
 281 /**
 282  * @brief
 283  *  Add a 'special' entry to the mFIB that links to the DPO passed
 284  *  A special entry is an entry that the FIB is not expect to resolve
 285  *  via the usual mechanisms (i.e. recurisve or neighbour adj DB lookup).
 286  *  Instead the client/source provides the index of a replicate DPO to link to.
 287  *
 288   * @param fib_index
 289  *  The index of the FIB
 290  *
 291  * @param prefix
 292  *  The prefix to add
 293  *
 294  * @param source
 295  *  The ID of the client/source adding the entry.
 296  *
 297  * @param flags
 298  *  Flags for the entry.
 299  *
 300  * @param rep_dpo
 301  *  The replicate DPO index to link to.
 302  *
 303  * @return
 304  *  the index of the fib_entry_t that is created (or existed already).
 305  */
 306 extern fib_node_index_t mfib_table_entry_special_add(u32 fib_index,
 307                                                      const mfib_prefix_t *prefix,
 308                                                      mfib_source_t source,
 309                                                      mfib_entry_flags_t flags,
 310                                                      index_t rep_dpo);
 311
 312 /**
 313  * @brief
 314  *  Flush all entries from a table for the source
 315  *
 316  * @param fib_index
 317  *  The index of the FIB
 318  *
 319  * @paran proto
 320  *  The protocol of the entries in the table
 321  *
 322  * @param source
 323  *  the source to flush
 324  */
 325 extern void mfib_table_flush(u32 fib_index,
 326                              fib_protocol_t proto,
 327                              mfib_source_t source);
 328
 329 /**
 330  * @brief
 331  *  Resync all entries from a table for the source
 332  *  this is the mark part of the mark and sweep algorithm.
 333  *  All entries in this FIB that are sourced by 'source' are marked
 334  *  as stale.
 335  *
 336  * @param fib_index
 337  *  The index of the FIB
 338  *
 339  * @paran proto
 340  *  The protocol of the entries in the table
 341  *
 342  * @param source
 343  *  the source to flush
 344  */
 345 extern void mfib_table_mark(u32 fib_index,
 346                             fib_protocol_t proto,
 347                             mfib_source_t source);
 348
 349 /**
 350  * @brief
 351  *  Signal that the table has converged, i.e. all updates are complete.
 352  *  this is the sweep part of the mark and sweep algorithm.
 353  *  All entries in this FIB that are sourced by 'source' and marked
 354  *  as stale are flushed.
 355  *
 356  * @param fib_index
 357  *  The index of the FIB
 358  *
 359  * @paran proto
 360  *  The protocol of the entries in the table
 361  *
 362  * @param source
 363  *  the source to flush
 364  */
 365 extern void mfib_table_sweep(u32 fib_index,
 366                              fib_protocol_t proto,
 367                              mfib_source_t source);
 368
 369 /**
 370  * @brief
 371  *  Get the index of the FIB bound to the interface
 372  *
 373  * @paran proto
 374  *  The protocol of the FIB (and thus the entries therein)
 375  *
 376  * @param sw_if_index
 377  *  The interface index
 378  *
 379  * @return fib_index
 380  *  The index of the FIB
 381  */
 382 extern u32 mfib_table_get_index_for_sw_if_index(fib_protocol_t proto,
 383                                                 u32 sw_if_index);
 384
 385 /**
 386  * @brief
 387  *  Get the Table-ID of the FIB from protocol and index
 388  *
 389  * @param fib_index
 390  *  The FIB index
 391  *
 392  * @paran proto
 393  *  The protocol of the FIB (and thus the entries therein)
 394  *
 395  * @return fib_index
 396  *  The tableID of the FIB
 397  */
 398 extern u32 mfib_table_get_table_id(u32 fib_index, fib_protocol_t proto);
 399
 400 /**
 401  * @brief
 402  *  Get the index of the FIB for a Table-ID. This DOES NOT create the
 403  * FIB if it does not exist.
 404  *
 405  * @paran proto
 406  *  The protocol of the FIB (and thus the entries therein)
 407  *
 408  * @param table-id
 409  *  The Table-ID
 410  *
 411  * @return fib_index
 412  *  The index of the FIB, which may be INVALID.
 413  */
 414 extern u32 mfib_table_find(fib_protocol_t proto, u32 table_id);
 415
 416 /**
 417  * @brief
 418  *  Get the Table-ID of the FIB from protocol and index
 419  *
 420  * @param fib_index
 421  *  The FIB index
 422  *
 423  * @paran proto
 424  *  The protocol of the FIB (and thus the entries therein)
 425  *
 426  * @return fib_index
 427  *  The tableID of the FIB
 428  */
 429 extern u32 mfib_table_get_table_id(u32 fib_index, fib_protocol_t proto);
 430
 431 /**
 432  * @brief
 433  *  Get the index of the FIB for a Table-ID. This DOES create the
 434  * FIB if it does not exist.
 435  *
 436  * @paran proto
 437  *  The protocol of the FIB (and thus the entries therein)
 438  *
 439  * @param table-id
 440  *  The Table-ID
 441  *
 442  * @return fib_index
 443  *  The index of the FIB
 444  *
 445  * @param source
 446  *  The ID of the client/source.
 447  */
 448 extern u32 mfib_table_find_or_create_and_lock(fib_protocol_t proto,
 449                                               u32 table_id,
 450                                               mfib_source_t source);
 451
 452 /**
 453  * @brief
 454  *  Get the index of the FIB for a Table-ID. This DOES create the
 455  * FIB if it does not exist.
 456  *
 457  * @paran proto
 458  *  The protocol of the FIB (and thus the entries therein)
 459  *
 460  * @param table-id
 461  *  The Table-ID
 462  *
 463  * @return fib_index
 464  *  The index of the FIB
 465  *
 466  * @param source
 467  *  The ID of the client/source.
 468  *
 469  * @param name
 470  *  The client is choosing the name they want the table to have
 471  */
 472 extern u32 mfib_table_find_or_create_and_lock_w_name(fib_protocol_t proto,
 473                                                      u32 table_id,
 474                                                      mfib_source_t source,
 475                                                      const u8 *name);
 476
 477
 478 /**
 479  * @brief
 480  * Take a reference counting lock on the table
 481  *
 482  * @param fib_index
 483  *  The index of the FIB
 484  *
 485  * @paran proto
 486  *  The protocol of the FIB (and thus the entries therein)
 487  *
 488  * @param source
 489  *  The ID of the client/source.
 490  */
 491 extern void mfib_table_unlock(u32 fib_index,
 492                               fib_protocol_t proto,
 493                               mfib_source_t source);
 494
 495 /**
 496  * @brief
 497  * Release a reference counting lock on the table. When the last lock
 498  * has gone. the FIB is deleted.
 499  *
 500  * @param fib_index
 501  *  The index of the FIB
 502  *
 503  * @paran proto
 504  *  The protocol of the FIB (and thus the entries therein)
 505  *
 506  * @param source
 507  *  The ID of the client/source.
 508  */
 509 extern void mfib_table_lock(u32 fib_index,
 510                             fib_protocol_t proto,
 511                             mfib_source_t source);
 512
 513 /**
 514  * @brief
 515  * Return the number of entries in the FIB added by a given source.
 516  *
 517  * @param fib_index
 518  *  The index of the FIB
 519  *
 520  * @paran proto
 521  *  The protocol of the FIB (and thus the entries therein)
 522  *
 523  * @return number of sourced entries.
 524  */
 525 extern u32 mfib_table_get_num_entries(u32 fib_index,
 526                                       fib_protocol_t proto);
 527
 528 /**
 529  * @brief
 530  *  Get the less specific (covering) prefix
 531  *
 532  * @param fib_index
 533  *  The index of the FIB
 534  *
 535  * @param prefix
 536  *  The prefix to lookup
 537  *
 538  * @return
 539  *  The index of the less specific fib_entry_t.
 540  */
 541 extern fib_node_index_t mfib_table_get_less_specific(u32 fib_index,
 542                                                     const mfib_prefix_t *prefix);
 543
 544 /**
 545  * @brief
 546  * Get a pointer to a FIB table
 547  */
 548 extern mfib_table_t *mfib_table_get(fib_node_index_t index,
 549                                     fib_protocol_t proto);
 550
 551 /**
 552  * @brief Call back function when walking entries in a FIB table
 553  */
 554 typedef walk_rc_t (*mfib_table_walk_fn_t)(fib_node_index_t fei,
 555                                           void *ctx);
 556
 557 /**
 558  * @brief Walk all entries in a FIB table
 559  * N.B: This is NOT safe to deletes. If you need to delete, walk the whole
 560  * table and store elements in a vector, then delete the elements
 561  */
 562 extern void mfib_table_walk(u32 fib_index,
 563                             fib_protocol_t proto,
 564                             mfib_table_walk_fn_t fn,
 565                             void *ctx);
 566 /**
 567  * @brief format (display) the memory usage for mfibs
 568  */
 569 extern u8 * format_mfib_table_memory(u8 * s, va_list * args);
 570
 571 /**
 572  * To assit UT
 573  */
 574 extern u32 mfib_table_get_n_routes(fib_node_index_t index,
 575                                    fib_protocol_t proto);
 576
 577
 578 #endif