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     u32 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                                                      mfib_entry_flags_t entry_flags,
 214                                                      const fib_route_path_t *rpath);
 215 extern fib_node_index_t mfib_table_entry_paths_update(u32 fib_index,
 216                                                       const mfib_prefix_t *prefix,
 217                                                       mfib_source_t source,
 218                                                       mfib_entry_flags_t entry_flags,
 219                                                       const fib_route_path_t *rpath);
 220
 221 /**
 222  * @brief
 223  * Remove n paths to an entry (aka route) in the FIB. If this is the entry's
 224  * last path, then the entry will be removed, unless it has other sources.
 225  * See the documentation for fib_route_path_t for more descirptions of
 226  * the path parameters.
 227  *
 228  * @param fib_index
 229  *  The index of the FIB
 230  *
 231  * @param prefix
 232  *  The prefix for the entry to add
 233  *
 234  * @param source
 235  *  The ID of the client/source adding the entry.
 236  *
 237  * @param rpaths
 238  *  A vector of paths.
 239  */
 240 extern void mfib_table_entry_path_remove(u32 fib_index,
 241                                          const mfib_prefix_t *prefix,
 242                                          mfib_source_t source,
 243                                          const fib_route_path_t *paths);
 244 extern void mfib_table_entry_paths_remove(u32 fib_index,
 245                                           const mfib_prefix_t *prefix,
 246                                           mfib_source_t source,
 247                                           const fib_route_path_t *paths);
 248
 249
 250
 251 /**
 252  * @brief
 253  *  Delete a FIB entry. If the entry has no more sources, then it is
 254  * removed from the table.
 255  *
 256  * @param fib_index
 257  *  The index of the FIB
 258  *
 259  * @param prefix
 260  *  The prefix for the entry to remove
 261  *
 262  * @param source
 263  *  The ID of the client/source adding the entry.
 264  */
 265 extern void mfib_table_entry_delete(u32 fib_index,
 266                                     const mfib_prefix_t *prefix,
 267                                     mfib_source_t source);
 268
 269 /**
 270  * @brief
 271  *  Delete a FIB entry. If the entry has no more sources, then it is
 272  * removed from the table.
 273  *
 274  * @param entry_index
 275  *  The index of the FIB entry
 276  *
 277  * @param source
 278  *  The ID of the client/source adding the entry.
 279  */
 280 extern void mfib_table_entry_delete_index(fib_node_index_t entry_index,
 281                                           mfib_source_t source);
 282
 283 /**
 284  * @brief
 285  *  Add a 'special' entry to the mFIB that links to the DPO passed
 286  *  A special entry is an entry that the FIB is not expect to resolve
 287  *  via the usual mechanisms (i.e. recurisve or neighbour adj DB lookup).
 288  *  Instead the client/source provides the index of a replicate DPO to link to.
 289  *
 290   * @param fib_index
 291  *  The index of the FIB
 292  *
 293  * @param prefix
 294  *  The prefix to add
 295  *
 296  * @param source
 297  *  The ID of the client/source adding the entry.
 298  *
 299  * @param flags
 300  *  Flags for the entry.
 301  *
 302  * @param rep_dpo
 303  *  The replicate DPO index to link to.
 304  *
 305  * @return
 306  *  the index of the fib_entry_t that is created (or existed already).
 307  */
 308 extern fib_node_index_t mfib_table_entry_special_add(u32 fib_index,
 309                                                      const mfib_prefix_t *prefix,
 310                                                      mfib_source_t source,
 311                                                      mfib_entry_flags_t flags,
 312                                                      index_t rep_dpo);
 313
 314 /**
 315  * @brief
 316  *  Flush all entries from a table for the source
 317  *
 318  * @param fib_index
 319  *  The index of the FIB
 320  *
 321  * @paran proto
 322  *  The protocol of the entries in the table
 323  *
 324  * @param source
 325  *  the source to flush
 326  */
 327 extern void mfib_table_flush(u32 fib_index,
 328                              fib_protocol_t proto,
 329                              mfib_source_t source);
 330
 331 /**
 332  * @brief
 333  *  Resync all entries from a table for the source
 334  *  this is the mark part of the mark and sweep algorithm.
 335  *  All entries in this FIB that are sourced by 'source' are marked
 336  *  as stale.
 337  *
 338  * @param fib_index
 339  *  The index of the FIB
 340  *
 341  * @paran proto
 342  *  The protocol of the entries in the table
 343  *
 344  * @param source
 345  *  the source to flush
 346  */
 347 extern void mfib_table_mark(u32 fib_index,
 348                             fib_protocol_t proto,
 349                             mfib_source_t source);
 350
 351 /**
 352  * @brief
 353  *  Signal that the table has converged, i.e. all updates are complete.
 354  *  this is the sweep part of the mark and sweep algorithm.
 355  *  All entries in this FIB that are sourced by 'source' and marked
 356  *  as stale are flushed.
 357  *
 358  * @param fib_index
 359  *  The index of the FIB
 360  *
 361  * @paran proto
 362  *  The protocol of the entries in the table
 363  *
 364  * @param source
 365  *  the source to flush
 366  */
 367 extern void mfib_table_sweep(u32 fib_index,
 368                              fib_protocol_t proto,
 369                              mfib_source_t source);
 370
 371 /**
 372  * @brief
 373  *  Get the index of the FIB bound to the interface
 374  *
 375  * @paran proto
 376  *  The protocol of the FIB (and thus the entries therein)
 377  *
 378  * @param sw_if_index
 379  *  The interface index
 380  *
 381  * @return fib_index
 382  *  The index of the FIB
 383  */
 384 extern u32 mfib_table_get_index_for_sw_if_index(fib_protocol_t proto,
 385                                                 u32 sw_if_index);
 386
 387 /**
 388  * @brief
 389  *  Get the Table-ID of the FIB from protocol and index
 390  *
 391  * @param fib_index
 392  *  The FIB index
 393  *
 394  * @paran proto
 395  *  The protocol of the FIB (and thus the entries therein)
 396  *
 397  * @return fib_index
 398  *  The tableID of the FIB
 399  */
 400 extern u32 mfib_table_get_table_id(u32 fib_index, fib_protocol_t proto);
 401
 402 /**
 403  * @brief
 404  *  Get the index of the FIB for a Table-ID. This DOES NOT create the
 405  * FIB if it does not exist.
 406  *
 407  * @paran proto
 408  *  The protocol of the FIB (and thus the entries therein)
 409  *
 410  * @param table-id
 411  *  The Table-ID
 412  *
 413  * @return fib_index
 414  *  The index of the FIB, which may be INVALID.
 415  */
 416 extern u32 mfib_table_find(fib_protocol_t proto, u32 table_id);
 417
 418 /**
 419  * @brief
 420  *  Get the Table-ID of the FIB from protocol and index
 421  *
 422  * @param fib_index
 423  *  The FIB index
 424  *
 425  * @paran proto
 426  *  The protocol of the FIB (and thus the entries therein)
 427  *
 428  * @return fib_index
 429  *  The tableID of the FIB
 430  */
 431 extern u32 mfib_table_get_table_id(u32 fib_index, fib_protocol_t proto);
 432
 433 /**
 434  * @brief
 435  *  Get the index of the FIB for a Table-ID. This DOES create the
 436  * FIB if it does not exist.
 437  *
 438  * @paran proto
 439  *  The protocol of the FIB (and thus the entries therein)
 440  *
 441  * @param table-id
 442  *  The Table-ID
 443  *
 444  * @return fib_index
 445  *  The index of the FIB
 446  *
 447  * @param source
 448  *  The ID of the client/source.
 449  */
 450 extern u32 mfib_table_find_or_create_and_lock(fib_protocol_t proto,
 451                                               u32 table_id,
 452                                               mfib_source_t source);
 453
 454 /**
 455  * @brief
 456  *  Get the index of the FIB for a Table-ID. This DOES create the
 457  * FIB if it does not exist.
 458  *
 459  * @paran proto
 460  *  The protocol of the FIB (and thus the entries therein)
 461  *
 462  * @param table-id
 463  *  The Table-ID
 464  *
 465  * @return fib_index
 466  *  The index of the FIB
 467  *
 468  * @param source
 469  *  The ID of the client/source.
 470  *
 471  * @param name
 472  *  The client is choosing the name they want the table to have
 473  */
 474 extern u32 mfib_table_find_or_create_and_lock_w_name(fib_protocol_t proto,
 475                                                      u32 table_id,
 476                                                      mfib_source_t source,
 477                                                      const u8 *name);
 478
 479
 480 /**
 481  * @brief
 482  * Take a reference counting lock on the table
 483  *
 484  * @param fib_index
 485  *  The index of the FIB
 486  *
 487  * @paran proto
 488  *  The protocol of the FIB (and thus the entries therein)
 489  *
 490  * @param source
 491  *  The ID of the client/source.
 492  */
 493 extern void mfib_table_unlock(u32 fib_index,
 494                               fib_protocol_t proto,
 495                               mfib_source_t source);
 496
 497 /**
 498  * @brief
 499  * Release a reference counting lock on the table. When the last lock
 500  * has gone. the FIB is deleted.
 501  *
 502  * @param fib_index
 503  *  The index of the FIB
 504  *
 505  * @paran proto
 506  *  The protocol of the FIB (and thus the entries therein)
 507  *
 508  * @param source
 509  *  The ID of the client/source.
 510  */
 511 extern void mfib_table_lock(u32 fib_index,
 512                             fib_protocol_t proto,
 513                             mfib_source_t source);
 514
 515 /**
 516  * @brief
 517  * Return the number of entries in the FIB added by a given source.
 518  *
 519  * @param fib_index
 520  *  The index of the FIB
 521  *
 522  * @paran proto
 523  *  The protocol of the FIB (and thus the entries therein)
 524  *
 525  * @return number of sourced entries.
 526  */
 527 extern u32 mfib_table_get_num_entries(u32 fib_index,
 528                                       fib_protocol_t proto);
 529
 530 /**
 531  * @brief
 532  *  Get the less specific (covering) prefix
 533  *
 534  * @param fib_index
 535  *  The index of the FIB
 536  *
 537  * @param prefix
 538  *  The prefix to lookup
 539  *
 540  * @return
 541  *  The index of the less specific fib_entry_t.
 542  */
 543 extern fib_node_index_t mfib_table_get_less_specific(u32 fib_index,
 544                                                     const mfib_prefix_t *prefix);
 545
 546 /**
 547  * @brief
 548  * Get a pointer to a FIB table
 549  */
 550 extern mfib_table_t *mfib_table_get(fib_node_index_t index,
 551                                     fib_protocol_t proto);
 552
 553 /**
 554  * @brief Call back function when walking entries in a FIB table
 555  */
 556 typedef walk_rc_t (*mfib_table_walk_fn_t)(fib_node_index_t fei,
 557                                           void *ctx);
 558
 559 /**
 560  * @brief Walk all entries in a FIB table
 561  * N.B: This is NOT safe to deletes. If you need to delete, walk the whole
 562  * table and store elements in a vector, then delete the elements
 563  */
 564 extern void mfib_table_walk(u32 fib_index,
 565                             fib_protocol_t proto,
 566                             mfib_table_walk_fn_t fn,
 567                             void *ctx);
 568 /**
 569  * @brief format (display) the memory usage for mfibs
 570  */
 571 extern u8 * format_mfib_table_memory(u8 * s, va_list * args);
 572
 573 /**
 574  * To assit UT
 575  */
 576 extern u32 mfib_table_get_n_routes(fib_node_index_t index,
 577                                    fib_protocol_t proto);
 578
 579
 580 #endif