src/vnet/fib/fib_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 __FIB_TABLE_H__
  17 #define __FIB_TABLE_H__
  18
  19 #include <vnet/ip/ip.h>
  20 #include <vnet/adj/adj.h>
  21 #include <vnet/fib/fib_entry.h>
  22 #include <vnet/mpls/mpls.h>
  23 #include <vnet/mpls/packet.h>
  24
  25 /**
  26  * @brief
  27  *   A protocol Independent FIB table
  28  */
  29 typedef struct fib_table_t_
  30 {
  31     /**
  32      * Which protocol this table serves. Used to switch on the union above.
  33      */
  34     fib_protocol_t ft_proto;
  35
  36     /**
  37      * number of locks on the table
  38      */
  39     u16 ft_locks;
  40
  41     /**
  42      * Table ID (hash key) for this FIB.
  43      */
  44     u32 ft_table_id;
  45
  46     /**
  47      * Index into FIB vector.
  48      */
  49     fib_node_index_t ft_index;
  50
  51     /**
  52      * flow hash configuration
  53      */
  54     u32 ft_flow_hash_config;
  55
  56     /**
  57      * Per-source route counters
  58      */
  59     u32 ft_src_route_counts[FIB_SOURCE_MAX];
  60
  61     /**
  62      * Total route counters
  63      */
  64     u32 ft_total_route_counts;
  65
  66     /**
  67      * Table description
  68      */
  69     u8* ft_desc;
  70 } fib_table_t;
  71
  72 /**
  73  * @brief
  74  *  Format the description/name of the table
  75  */
  76 extern u8* format_fib_table_name(u8* s, va_list ap);
  77
  78 /**
  79  * @brief
  80  *  Perfom a longest prefix match in the non-forwarding table
  81  *
  82  * @param fib_index
  83  *  The index of the FIB
  84  *
  85  * @param prefix
  86  *  The prefix to lookup
  87  *
  88  * @return
  89  *  The index of the fib_entry_t for the best match, which may be the default route
  90  */
  91 extern fib_node_index_t fib_table_lookup(u32 fib_index,
  92                                          const fib_prefix_t *prefix);
  93
  94 /**
  95  * @brief
  96  *  Perfom an exact match in the non-forwarding table
  97  *
  98  * @param fib_index
  99  *  The index of the FIB
 100  *
 101  * @param prefix
 102  *  The prefix to lookup
 103  *
 104  * @return
 105  *  The index of the fib_entry_t for the exact match, or INVALID
 106  *  is there is no match.
 107  */
 108 extern fib_node_index_t fib_table_lookup_exact_match(u32 fib_index,
 109                                                      const fib_prefix_t *prefix);
 110
 111 /**
 112  * @brief
 113  *  Get the less specific (covering) prefix
 114  *
 115  * @param fib_index
 116  *  The index of the FIB
 117  *
 118  * @param prefix
 119  *  The prefix to lookup
 120  *
 121  * @return
 122  *  The index of the less specific fib_entry_t.
 123  */
 124 extern fib_node_index_t fib_table_get_less_specific(u32 fib_index,
 125                                                     const fib_prefix_t *prefix);
 126
 127 /**
 128  * @brief
 129  *  Add a 'special' entry to the FIB that links to the adj passed
 130  *  A special entry is an entry that the FIB is not expect to resolve
 131  *  via the usual mechanisms (i.e. recurisve or neighbour adj DB lookup).
 132  *  Instead the client/source provides the adj to link to.
 133  *  This add is reference counting per-source. So n 'removes' are required
 134  *  for n 'adds', if the entry is no longer required.
 135  *
 136   * @param fib_index
 137  *  The index of the FIB
 138  *
 139  * @param prefix
 140  *  The prefix to add
 141  *
 142  * @param source
 143  *  The ID of the client/source adding the entry.
 144  *
 145  * @param flags
 146  *  Flags for the entry.
 147  *
 148  * @param adj_index
 149  *  The adjacency to link to.
 150  *
 151  * @return
 152  *  the index of the fib_entry_t that is created (or exists already).
 153  */
 154 extern fib_node_index_t fib_table_entry_special_add(u32 fib_index,
 155                                                     const fib_prefix_t *prefix,
 156                                                     fib_source_t source,
 157                                                     fib_entry_flag_t flags,
 158                                                     adj_index_t adj_index);
 159
 160 /**
 161  * @brief
 162  *  Add a 'special' entry to the FIB that links to the DPO passed
 163  *  A special entry is an entry that the FIB is not expect to resolve
 164  *  via the usual mechanisms (i.e. recurisve or neighbour adj DB lookup).
 165  *  Instead the client/source provides the DPO to link to.
 166  *  This add is reference counting per-source. So n 'removes' are required
 167  *  for n 'adds', if the entry is no longer required.
 168  *
 169   * @param fib_index
 170  *  The index of the FIB
 171  *
 172  * @param prefix
 173  *  The prefix to add
 174  *
 175  * @param source
 176  *  The ID of the client/source adding the entry.
 177  *
 178  * @param flags
 179  *  Flags for the entry.
 180  *
 181  * @param dpo
 182  *  The DPO to link to.
 183  *
 184  * @return
 185  *  the index of the fib_entry_t that is created (or existed already).
 186  */
 187 extern fib_node_index_t fib_table_entry_special_dpo_add(u32 fib_index,
 188                                                         const fib_prefix_t *prefix,
 189                                                         fib_source_t source,
 190                                                         fib_entry_flag_t stype,
 191                                                         const dpo_id_t *dpo);
 192
 193 /**
 194  * @brief
 195  *  Update a 'special' entry to the FIB that links to the DPO passed
 196  *  A special entry is an entry that the FIB is not expect to resolve
 197  *  via the usual mechanisms (i.e. recurisve or neighbour adj DB lookup).
 198  *  Instead the client/source provides the DPO to link to.
 199  *  Special entries are add/remove reference counted per-source. So n
 200  * 'removes' are required for n 'adds', if the entry is no longer required.
 201  *  An 'update' is an 'add' if no 'add' has already been called, otherwise an 'add'
 202  * is therefore assumed to act on the reference instance of that add.
 203  *
 204  * @param fib_entry_index
 205  *  The index of the FIB entry to update
 206  *
 207  * @param source
 208  *  The ID of the client/source adding the entry.
 209  *
 210  * @param flags
 211  *  Flags for the entry.
 212  *
 213  * @param dpo
 214  *  The DPO to link to.
 215  *
 216  * @return
 217  *  the index of the fib_entry_t that is created (or existed already).
 218  */
 219 extern fib_node_index_t fib_table_entry_special_dpo_update (u32 fib_index,
 220                                                             const fib_prefix_t *prefix,
 221                                                             fib_source_t source,
 222                                                             fib_entry_flag_t stype,
 223                                                             const dpo_id_t *dpo);
 224
 225 /**
 226  * @brief
 227  *  Remove a 'special' entry from the FIB.
 228  *  This add is reference counting per-source. So n 'removes' are required
 229  *  for n 'adds', if the entry is no longer required.
 230  *
 231  * @param fib_index
 232  *  The index of the FIB
 233  *
 234  * @param prefix
 235  *  The prefix to remove
 236  *
 237  * @param source
 238  *  The ID of the client/source adding the entry.
 239  *
 240  */
 241 extern void fib_table_entry_special_remove(u32 fib_index,
 242                                            const fib_prefix_t *prefix,
 243                                            fib_source_t source);
 244
 245 /**
 246  * @brief
 247  *  Add one path to an entry (aka route) in the FIB. If the entry does not
 248  *  exist, it will be created.
 249  * See the documentation for fib_route_path_t for more descirptions of
 250  * the path parameters.
 251  *
 252  * @param fib_index
 253  *  The index of the FIB
 254  *
 255  * @param prefix
 256  *  The prefix for the entry to add
 257  *
 258  * @param source
 259  *  The ID of the client/source adding the entry.
 260  *
 261  * @param flags
 262  *  Flags for the entry.
 263  *
 264  * @paran next_hop_proto
 265  *  The protocol of the next hop. This cannot be derived in the event that
 266  * the next hop is all zeros.
 267  *
 268  * @param next_hop
 269  *  The address of the next-hop.
 270  *
 271  * @param sw_if_index
 272  *  The index of the interface.
 273  *
 274  * @param next_hop_fib_index,
 275  *  The fib index of the next-hop for recursive resolution
 276  *
 277  * @param next_hop_weight
 278  *  [un]equal cost path weight
 279  *
 280  * @param  next_hop_label_stack
 281  *  The path's out-going label stack. NULL is there is none.
 282  *
 283  * @param  pf
 284  *  Flags for the path
 285  *
 286  * @return
 287  *  the index of the fib_entry_t that is created (or existed already).
 288  */
 289 extern fib_node_index_t fib_table_entry_path_add(u32 fib_index,
 290                                                  const fib_prefix_t *prefix,
 291                                                  fib_source_t source,
 292                                                  fib_entry_flag_t flags,
 293                                                  fib_protocol_t next_hop_proto,
 294                                                  const ip46_address_t *next_hop,
 295                                                  u32 next_hop_sw_if_index,
 296                                                  u32 next_hop_fib_index,
 297                                                  u32 next_hop_weight,
 298                                                  mpls_label_t *next_hop_label_stack,
 299                                                  fib_route_path_flags_t pf);
 300 /**
 301  * @brief
 302  *  Add n paths to an entry (aka route) in the FIB. If the entry does not
 303  *  exist, it will be created.
 304  * See the documentation for fib_route_path_t for more descirptions of
 305  * the path parameters.
 306  *
 307  * @param fib_index
 308  *  The index of the FIB
 309  *
 310  * @param prefix
 311  *  The prefix for the entry to add
 312  *
 313  * @param source
 314  *  The ID of the client/source adding the entry.
 315  *
 316  * @param flags
 317  *  Flags for the entry.
 318  *
 319  * @param rpaths
 320  *  A vector of paths. Not const since they may be modified.
 321  *
 322  * @return
 323  *  the index of the fib_entry_t that is created (or existed already).
 324  */
 325 extern fib_node_index_t fib_table_entry_path_add2(u32 fib_index,
 326                                                   const fib_prefix_t *prefix,
 327                                                   fib_source_t source,
 328                                                   fib_entry_flag_t flags,
 329                                                   fib_route_path_t *rpath);
 330
 331 /**
 332  * @brief
 333  * remove one path to an entry (aka route) in the FIB. If this is the entry's
 334  * last path, then the entry will be removed, unless it has other sources.
 335  * See the documentation for fib_route_path_t for more descirptions of
 336  * the path parameters.
 337  *
 338  * @param fib_index
 339  *  The index of the FIB
 340  *
 341  * @param prefix
 342  *  The prefix for the entry to add
 343  *
 344  * @param source
 345  *  The ID of the client/source adding the entry.
 346  *
 347  * @paran next_hop_proto
 348  *  The protocol of the next hop. This cannot be derived in the event that
 349  * the next hop is all zeros.
 350  *
 351  * @param next_hop
 352  *  The address of the next-hop.
 353  *
 354  * @param sw_if_index
 355  *  The index of the interface.
 356  *
 357  * @param next_hop_fib_index,
 358  *  The fib index of the next-hop for recursive resolution
 359  *
 360  * @param next_hop_weight
 361  *  [un]equal cost path weight
 362  *
 363  * @param  pf
 364  *  Flags for the path
 365  */
 366 extern void fib_table_entry_path_remove(u32 fib_index,
 367                                         const fib_prefix_t *prefix,
 368                                         fib_source_t source,
 369                                         fib_protocol_t next_hop_proto,
 370                                         const ip46_address_t *next_hop,
 371                                         u32 next_hop_sw_if_index,
 372                                         u32 next_hop_fib_index,
 373                                         u32 next_hop_weight,
 374                                         fib_route_path_flags_t pf);
 375
 376 /**
 377  * @brief
 378  * Remove n paths to an entry (aka route) in the FIB. If this is the entry's
 379  * last path, then the entry will be removed, unless it has other sources.
 380  * See the documentation for fib_route_path_t for more descirptions of
 381  * the path parameters.
 382  *
 383  * @param fib_index
 384  *  The index of the FIB
 385  *
 386  * @param prefix
 387  *  The prefix for the entry to add
 388  *
 389  * @param source
 390  *  The ID of the client/source adding the entry.
 391  *
 392  * @param rpaths
 393  *  A vector of paths.
 394  */
 395 extern void fib_table_entry_path_remove2(u32 fib_index,
 396                                          const fib_prefix_t *prefix,
 397                                          fib_source_t source,
 398                                          fib_route_path_t *paths);
 399
 400 /**
 401  * @brief
 402  *  Update an entry to have a new set of paths. If the entry does not
 403  *  exist, it will be created.
 404  * The difference between an 'path-add' and an update, is that path-add is
 405  * an incremental addition of paths, whereas an update is a wholesale swap.
 406  *
 407  * @param fib_index
 408  *  The index of the FIB
 409  *
 410  * @param prefix
 411  *  The prefix for the entry to add
 412  *
 413  * @param source
 414  *  The ID of the client/source adding the entry.
 415  *
 416  * @param rpaths
 417  *  A vector of paths. Not const since they may be modified.
 418  *
 419  * @return
 420  *  the index of the fib_entry_t that is created (or existed already).
 421  */
 422 extern fib_node_index_t fib_table_entry_update(u32 fib_index,
 423                                                const fib_prefix_t *prefix,
 424                                                fib_source_t source,
 425                                                fib_entry_flag_t flags,
 426                                                fib_route_path_t *paths);
 427
 428 /**
 429  * @brief
 430  *  Update the entry to have just one path. If the entry does not
 431  *  exist, it will be created.
 432  * See the documentation for fib_route_path_t for more descirptions of
 433  * the path parameters.
 434  *
 435  * @param fib_index
 436  *  The index of the FIB
 437  *
 438  * @param prefix
 439  *  The prefix for the entry to add
 440  *
 441  * @param source
 442  *  The ID of the client/source adding the entry.
 443  *
 444  * @param flags
 445  *  Flags for the entry.
 446  *
 447  * @paran next_hop_proto
 448  *  The protocol of the next hop. This cannot be derived in the event that
 449  * the next hop is all zeros.
 450  *
 451  * @param next_hop
 452  *  The address of the next-hop.
 453  *
 454  * @param sw_if_index
 455  *  The index of the interface.
 456  *
 457  * @param next_hop_fib_index,
 458  *  The fib index of the next-hop for recursive resolution
 459  *
 460  * @param next_hop_weight
 461  *  [un]equal cost path weight
 462  *
 463  * @param  next_hop_label_stack
 464  *  The path's out-going label stack. NULL is there is none.
 465  *
 466  * @param  pf
 467  *  Flags for the path
 468  *
 469  * @return
 470  *  the index of the fib_entry_t that is created (or existed already).
 471  */
 472 extern fib_node_index_t fib_table_entry_update_one_path(u32 fib_index,
 473                                                         const fib_prefix_t *prefix,
 474                                                         fib_source_t source,
 475                                                         fib_entry_flag_t flags,
 476                                                         fib_protocol_t next_hop_proto,
 477                                                         const ip46_address_t *next_hop,
 478                                                         u32 next_hop_sw_if_index,
 479                                                         u32 next_hop_fib_index,
 480                                                         u32 next_hop_weight,
 481                                                         mpls_label_t *next_hop_label_stack,
 482                                                         fib_route_path_flags_t pf);
 483
 484 /**
 485  * @brief
 486  *  Add a MPLS local label for the prefix/route. If the entry does not
 487  *  exist, it will be created. In theory more than one local label can be
 488  *  added, but this is not yet supported.
 489  *
 490  * @param fib_index
 491  *  The index of the FIB
 492  *
 493  * @param prefix
 494  *  The prefix for the entry to which to add the label
 495  *
 496  * @param label
 497  *  The MPLS label to add
 498  *
 499  * @return
 500  *  the index of the fib_entry_t that is created (or existed already).
 501  */
 502 extern fib_node_index_t fib_table_entry_local_label_add(u32 fib_index,
 503                                                         const fib_prefix_t *prefix,
 504                                                         mpls_label_t label);
 505 /**
 506  * @brief
 507  *  remove a MPLS local label for the prefix/route.
 508  *
 509  * @param fib_index
 510  *  The index of the FIB
 511  *
 512  * @param prefix
 513  *  The prefix for the entry to which to add the label
 514  *
 515  * @param label
 516  *  The MPLS label to add
 517  */
 518 extern void fib_table_entry_local_label_remove(u32 fib_index,
 519                                                const fib_prefix_t *prefix,
 520                                                mpls_label_t label);
 521
 522 /**
 523  * @brief
 524  *  Delete a FIB entry. If the entry has no more sources, then it is
 525  * removed from the table.
 526  *
 527  * @param fib_index
 528  *  The index of the FIB
 529  *
 530  * @param prefix
 531  *  The prefix for the entry to remove
 532  *
 533  * @param source
 534  *  The ID of the client/source adding the entry.
 535  */
 536 extern void fib_table_entry_delete(u32 fib_index,
 537                                    const fib_prefix_t *prefix,
 538                                    fib_source_t source);
 539
 540 /**
 541  * @brief
 542  *  Delete a FIB entry. If the entry has no more sources, then it is
 543  * removed from the table.
 544  *
 545  * @param entry_index
 546  *  The index of the FIB entry
 547  *
 548  * @param source
 549  *  The ID of the client/source adding the entry.
 550  */
 551 extern void fib_table_entry_delete_index(fib_node_index_t entry_index,
 552                                          fib_source_t source);
 553
 554 /**
 555  * @brief
 556  *  Flush all entries from a table for the source
 557  *
 558  * @param fib_index
 559  *  The index of the FIB
 560  *
 561  * @paran proto
 562  *  The protocol of the entries in the table
 563  *
 564  * @param source
 565  *  the source to flush
 566  */
 567 extern void fib_table_flush(u32 fib_index,
 568                             fib_protocol_t proto,
 569                             fib_source_t source);
 570
 571 /**
 572  * @brief
 573  *  Get the index of the FIB bound to the interface
 574  *
 575  * @paran proto
 576  *  The protocol of the FIB (and thus the entries therein)
 577  *
 578  * @param sw_if_index
 579  *  The interface index
 580  *
 581  * @return fib_index
 582  *  The index of the FIB
 583  */
 584 extern u32 fib_table_get_index_for_sw_if_index(fib_protocol_t proto,
 585                                                u32 sw_if_index);
 586
 587 /**
 588  * @brief
 589  *  Get the Table-ID of the FIB bound to the interface
 590  *
 591  * @paran proto
 592  *  The protocol of the FIB (and thus the entries therein)
 593  *
 594  * @param sw_if_index
 595  *  The interface index
 596  *
 597  * @return fib_index
 598  *  The tableID of the FIB
 599  */
 600 extern u32 fib_table_get_table_id_for_sw_if_index(fib_protocol_t proto,
 601                                                   u32 sw_if_index);
 602
 603 /**
 604  * @brief
 605  *  Get the index of the FIB for a Table-ID. This DOES NOT create the
 606  * FIB if it does not exist.
 607  *
 608  * @paran proto
 609  *  The protocol of the FIB (and thus the entries therein)
 610  *
 611  * @param table-id
 612  *  The Table-ID
 613  *
 614  * @return fib_index
 615  *  The index of the FIB, which may be INVALID.
 616  */
 617 extern u32 fib_table_find(fib_protocol_t proto, u32 table_id);
 618
 619
 620 /**
 621  * @brief
 622  *  Get the index of the FIB for a Table-ID. This DOES create the
 623  * FIB if it does not exist.
 624  *
 625  * @paran proto
 626  *  The protocol of the FIB (and thus the entries therein)
 627  *
 628  * @param table-id
 629  *  The Table-ID
 630  *
 631  * @return fib_index
 632  *  The index of the FIB
 633  */
 634 extern u32 fib_table_find_or_create_and_lock(fib_protocol_t proto,
 635                                              u32 table_id);
 636
 637 /**
 638  * @brief
 639  *  Create a new table with no table ID. This means it does not get
 640  * added to the hash-table and so can only be found by using the index returned.
 641  *
 642  * @paran proto
 643  *  The protocol of the FIB (and thus the entries therein)
 644  *
 645  * @param fmt
 646  *  A string to describe the table
 647  *
 648  * @return fib_index
 649  *  The index of the FIB
 650  */
 651 extern u32 fib_table_create_and_lock(fib_protocol_t proto,
 652                                      const char *const fmt,
 653                                      ...);
 654
 655 /**
 656  * @brief
 657  *  Get the flow hash configured used by the table
 658  *
 659  * @param fib_index
 660  *  The index of the FIB
 661  *
 662  * @paran proto
 663  *  The protocol of the FIB (and thus the entries therein)
 664  *
 665  * @return The flow hash config
 666  */
 667 extern flow_hash_config_t fib_table_get_flow_hash_config(u32 fib_index,
 668                                                          fib_protocol_t proto);
 669
 670 /**
 671  * @brief
 672  * Take a reference counting lock on the table
 673  *
 674  * @param fib_index
 675  *  The index of the FIB
 676  *
 677  * @paran proto
 678  *  The protocol of the FIB (and thus the entries therein)
 679  */
 680 extern void fib_table_unlock(u32 fib_index,
 681                              fib_protocol_t proto);
 682
 683 /**
 684  * @brief
 685  * Release a reference counting lock on the table. When the last lock
 686  * has gone. the FIB is deleted.
 687  *
 688  * @param fib_index
 689  *  The index of the FIB
 690  *
 691  * @paran proto
 692  *  The protocol of the FIB (and thus the entries therein)
 693  */
 694 extern void fib_table_lock(u32 fib_index,
 695                            fib_protocol_t proto);
 696
 697 /**
 698  * @brief
 699  * Return the number of entries in the FIB added by a given source.
 700  *
 701  * @param fib_index
 702  *  The index of the FIB
 703  *
 704  * @paran proto
 705  *  The protocol of the FIB (and thus the entries therein)
 706  *
 707  * @return number of sourced entries.
 708  */
 709 extern u32 fib_table_get_num_entries(u32 fib_index,
 710                                      fib_protocol_t proto,
 711                                      fib_source_t source);
 712
 713 /**
 714  * @brief
 715  * Get a pointer to a FIB table
 716  */
 717 extern fib_table_t *fib_table_get(fib_node_index_t index,
 718                                   fib_protocol_t proto);
 719
 720 /**
 721  * @brief Call back function when walking entries in a FIB table
 722  */
 723 typedef int (*fib_table_walk_fn_t)(fib_node_index_t fei,
 724                                    void *ctx);
 725
 726 /**
 727  * @brief Walk all entries in a FIB table
 728  * N.B: This is NOT safe to deletes. If you need to delete walk the whole
 729  * table and store elements in a vector, then delete the elements
 730  */
 731 extern void fib_table_walk(u32 fib_index,
 732                            fib_protocol_t proto,
 733                            fib_table_walk_fn_t fn,
 734                            void *ctx);
 735
 736 #endif