src/vnet/fib/fib_table.c

   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 #include <vlib/vlib.h>
  17 #include <vnet/dpo/drop_dpo.h>
  18
  19 #include <vnet/fib/fib_table.h>
  20 #include <vnet/fib/fib_entry_cover.h>
  21 #include <vnet/fib/fib_internal.h>
  22 #include <vnet/fib/ip4_fib.h>
  23 #include <vnet/fib/ip6_fib.h>
  24 #include <vnet/fib/mpls_fib.h>
  25
  26 fib_table_t *
  27 fib_table_get (fib_node_index_t index,
  28                fib_protocol_t proto)
  29 {
  30     switch (proto)
  31     {
  32     case FIB_PROTOCOL_IP4:
  33         return (pool_elt_at_index(ip4_main.fibs, index));
  34     case FIB_PROTOCOL_IP6:
  35         return (pool_elt_at_index(ip6_main.fibs, index));
  36     case FIB_PROTOCOL_MPLS:
  37         return (pool_elt_at_index(mpls_main.fibs, index));
  38     }
  39     ASSERT(0);
  40     return (NULL);
  41 }
  42
  43 static inline fib_node_index_t
  44 fib_table_lookup_i (fib_table_t *fib_table,
  45                     const fib_prefix_t *prefix)
  46 {
  47     switch (prefix->fp_proto)
  48     {
  49     case FIB_PROTOCOL_IP4:
  50         return (ip4_fib_table_lookup(ip4_fib_get(fib_table->ft_index),
  51                                      &prefix->fp_addr.ip4,
  52                                      prefix->fp_len));
  53     case FIB_PROTOCOL_IP6:
  54         return (ip6_fib_table_lookup(fib_table->ft_index,
  55                                      &prefix->fp_addr.ip6,
  56                                      prefix->fp_len));
  57     case FIB_PROTOCOL_MPLS:
  58         return (mpls_fib_table_lookup(mpls_fib_get(fib_table->ft_index),
  59                                       prefix->fp_label,
  60                                       prefix->fp_eos));
  61     }
  62     return (FIB_NODE_INDEX_INVALID);
  63 }
  64
  65 fib_node_index_t
  66 fib_table_lookup (u32 fib_index,
  67                   const fib_prefix_t *prefix)
  68 {
  69     return (fib_table_lookup_i(fib_table_get(fib_index, prefix->fp_proto), prefix));
  70 }
  71
  72 static inline fib_node_index_t
  73 fib_table_lookup_exact_match_i (const fib_table_t *fib_table,
  74                                 const fib_prefix_t *prefix)
  75 {
  76     switch (prefix->fp_proto)
  77     {
  78     case FIB_PROTOCOL_IP4:
  79         return (ip4_fib_table_lookup_exact_match(ip4_fib_get(fib_table->ft_index),
  80                                                  &prefix->fp_addr.ip4,
  81                                                  prefix->fp_len));
  82     case FIB_PROTOCOL_IP6:
  83         return (ip6_fib_table_lookup_exact_match(fib_table->ft_index,
  84                                                  &prefix->fp_addr.ip6,
  85                                                  prefix->fp_len));
  86     case FIB_PROTOCOL_MPLS:
  87         return (mpls_fib_table_lookup(mpls_fib_get(fib_table->ft_index),
  88                                       prefix->fp_label,
  89                                       prefix->fp_eos));
  90     }
  91     return (FIB_NODE_INDEX_INVALID);
  92 }
  93
  94 fib_node_index_t
  95 fib_table_lookup_exact_match (u32 fib_index,
  96                               const fib_prefix_t *prefix)
  97 {
  98     return (fib_table_lookup_exact_match_i(fib_table_get(fib_index,
  99                                                          prefix->fp_proto),
 100                                            prefix));
 101 }
 102
 103 static fib_node_index_t
 104 fib_table_get_less_specific_i (fib_table_t *fib_table,
 105                                const fib_prefix_t *prefix)
 106 {
 107     fib_prefix_t pfx;
 108
 109     pfx = *prefix;
 110
 111     if (FIB_PROTOCOL_MPLS == pfx.fp_proto)
 112     {
 113         return (FIB_NODE_INDEX_INVALID);
 114     }
 115
 116     /*
 117      * in the absence of a tree structure for the table that allows for an O(1)
 118      * parent get, a cheeky way to find the cover is to LPM for the prefix with
 119      * mask-1.
 120      * there should always be a cover, though it may be the default route. the
 121      * default route's cover is the default route.
 122      */
 123     if (pfx.fp_len != 0) {
 124         pfx.fp_len -= 1;
 125     }
 126
 127     return (fib_table_lookup_i(fib_table, &pfx));
 128 }
 129
 130 fib_node_index_t
 131 fib_table_get_less_specific (u32 fib_index,
 132                              const fib_prefix_t *prefix)
 133 {
 134     return (fib_table_get_less_specific_i(fib_table_get(fib_index,
 135                                                         prefix->fp_proto),
 136                                           prefix));
 137 }
 138
 139 static void
 140 fib_table_entry_remove (fib_table_t *fib_table,
 141                         const fib_prefix_t *prefix,
 142                         fib_node_index_t fib_entry_index)
 143 {
 144     vlib_smp_unsafe_warning();
 145
 146     fib_table->ft_total_route_counts--;
 147
 148     switch (prefix->fp_proto)
 149     {
 150     case FIB_PROTOCOL_IP4:
 151         ip4_fib_table_entry_remove(ip4_fib_get(fib_table->ft_index),
 152                                    &prefix->fp_addr.ip4,
 153                                    prefix->fp_len);
 154         break;
 155     case FIB_PROTOCOL_IP6:
 156         ip6_fib_table_entry_remove(fib_table->ft_index,
 157                                    &prefix->fp_addr.ip6,
 158                                    prefix->fp_len);
 159         break;
 160     case FIB_PROTOCOL_MPLS:
 161         mpls_fib_table_entry_remove(mpls_fib_get(fib_table->ft_index),
 162                                     prefix->fp_label,
 163                                     prefix->fp_eos);
 164         break;
 165     }
 166
 167     fib_entry_unlock(fib_entry_index);
 168 }
 169
 170 static void
 171 fib_table_post_insert_actions (fib_table_t *fib_table,
 172                                const fib_prefix_t *prefix,
 173                                fib_node_index_t fib_entry_index)
 174 {
 175     fib_node_index_t fib_entry_cover_index;
 176
 177     /*
 178      * no cover relationships in the MPLS FIB
 179      */
 180     if (FIB_PROTOCOL_MPLS == prefix->fp_proto)
 181         return;
 182
 183     /*
 184      * find and inform the covering entry that a new more specific
 185      * has been inserted beneath it
 186      */
 187     fib_entry_cover_index = fib_table_get_less_specific_i(fib_table, prefix);
 188     /*
 189      * the indicies are the same when the default route is first added
 190      */
 191     if (fib_entry_cover_index != fib_entry_index)
 192     {
 193         fib_entry_cover_change_notify(fib_entry_cover_index,
 194                                       fib_entry_index);
 195     }
 196 }
 197
 198 static void
 199 fib_table_entry_insert (fib_table_t *fib_table,
 200                         const fib_prefix_t *prefix,
 201                         fib_node_index_t fib_entry_index)
 202 {
 203     vlib_smp_unsafe_warning();
 204
 205     fib_entry_lock(fib_entry_index);
 206     fib_table->ft_total_route_counts++;
 207
 208     switch (prefix->fp_proto)
 209     {
 210     case FIB_PROTOCOL_IP4:
 211         ip4_fib_table_entry_insert(ip4_fib_get(fib_table->ft_index),
 212                                    &prefix->fp_addr.ip4,
 213                                    prefix->fp_len,
 214                                    fib_entry_index);
 215         break;
 216     case FIB_PROTOCOL_IP6:
 217         ip6_fib_table_entry_insert(fib_table->ft_index,
 218                                    &prefix->fp_addr.ip6,
 219                                    prefix->fp_len,
 220                                    fib_entry_index);
 221         break;
 222     case FIB_PROTOCOL_MPLS:
 223         mpls_fib_table_entry_insert(mpls_fib_get(fib_table->ft_index),
 224                                     prefix->fp_label,
 225                                     prefix->fp_eos,
 226                                     fib_entry_index);
 227         break;
 228     }
 229
 230     fib_table_post_insert_actions(fib_table, prefix, fib_entry_index);
 231 }
 232
 233 void
 234 fib_table_fwding_dpo_update (u32 fib_index,
 235                              const fib_prefix_t *prefix,
 236                              const dpo_id_t *dpo)
 237 {
 238     vlib_smp_unsafe_warning();
 239
 240     switch (prefix->fp_proto)
 241     {
 242     case FIB_PROTOCOL_IP4:
 243         return (ip4_fib_table_fwding_dpo_update(ip4_fib_get(fib_index),
 244                                                 &prefix->fp_addr.ip4,
 245                                                 prefix->fp_len,
 246                                                 dpo));
 247     case FIB_PROTOCOL_IP6:
 248         return (ip6_fib_table_fwding_dpo_update(fib_index,
 249                                                 &prefix->fp_addr.ip6,
 250                                                 prefix->fp_len,
 251                                                 dpo));
 252     case FIB_PROTOCOL_MPLS:
 253         return (mpls_fib_forwarding_table_update(mpls_fib_get(fib_index),
 254                                                  prefix->fp_label,
 255                                                  prefix->fp_eos,
 256                                                  dpo));
 257     }
 258 }
 259
 260 void
 261 fib_table_fwding_dpo_remove (u32 fib_index,
 262                              const fib_prefix_t *prefix,
 263                              const dpo_id_t *dpo)
 264 {
 265     vlib_smp_unsafe_warning();
 266
 267     switch (prefix->fp_proto)
 268     {
 269     case FIB_PROTOCOL_IP4:
 270         return (ip4_fib_table_fwding_dpo_remove(ip4_fib_get(fib_index),
 271                                                 &prefix->fp_addr.ip4,
 272                                                 prefix->fp_len,
 273                                                 dpo,
 274                                                 fib_table_get_less_specific(fib_index,
 275                                                                             prefix)));
 276     case FIB_PROTOCOL_IP6:
 277         return (ip6_fib_table_fwding_dpo_remove(fib_index,
 278                                                 &prefix->fp_addr.ip6,
 279                                                 prefix->fp_len,
 280                                                 dpo));
 281     case FIB_PROTOCOL_MPLS:
 282         return (mpls_fib_forwarding_table_reset(mpls_fib_get(fib_index),
 283                                                 prefix->fp_label,
 284                                                 prefix->fp_eos));
 285     }
 286 }
 287
 288
 289 fib_node_index_t
 290 fib_table_entry_special_dpo_add (u32 fib_index,
 291                                  const fib_prefix_t *prefix,
 292                                  fib_source_t source,
 293                                  fib_entry_flag_t flags,
 294                                  const dpo_id_t *dpo)
 295 {
 296     fib_node_index_t fib_entry_index;
 297     fib_table_t *fib_table;
 298
 299     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 300     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 301
 302     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 303     {
 304         fib_entry_index = fib_entry_create_special(fib_index, prefix,
 305                                                    source, flags,
 306                                                    dpo);
 307
 308         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 309         fib_table->ft_src_route_counts[source]++;
 310     }
 311     else
 312     {
 313         int was_sourced;
 314
 315         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 316         fib_entry_special_add(fib_entry_index, source, flags, dpo);
 317
 318         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 319         {
 320             fib_table->ft_src_route_counts[source]++;
 321         }
 322     }
 323
 324
 325     return (fib_entry_index);
 326 }
 327
 328 fib_node_index_t
 329 fib_table_entry_special_dpo_update (u32 fib_index,
 330                                     const fib_prefix_t *prefix,
 331                                     fib_source_t source,
 332                                     fib_entry_flag_t flags,
 333                                     const dpo_id_t *dpo)
 334 {
 335     fib_node_index_t fib_entry_index;
 336     fib_table_t *fib_table;
 337
 338     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 339     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 340
 341     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 342     {
 343         fib_entry_index = fib_entry_create_special(fib_index, prefix,
 344                                                    source, flags,
 345                                                    dpo);
 346
 347         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 348         fib_table->ft_src_route_counts[source]++;
 349     }
 350     else
 351     {
 352         int was_sourced;
 353
 354         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 355
 356         if (was_sourced)
 357             fib_entry_special_update(fib_entry_index, source, flags, dpo);
 358         else
 359             fib_entry_special_add(fib_entry_index, source, flags, dpo);
 360
 361         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 362         {
 363             fib_table->ft_src_route_counts[source]++;
 364         }
 365     }
 366
 367     return (fib_entry_index);
 368 }
 369
 370 fib_node_index_t
 371 fib_table_entry_special_add (u32 fib_index,
 372                              const fib_prefix_t *prefix,
 373                              fib_source_t source,
 374                              fib_entry_flag_t flags,
 375                              adj_index_t adj_index)
 376 {
 377     fib_node_index_t fib_entry_index;
 378     dpo_id_t tmp_dpo = DPO_INVALID;
 379
 380     if (ADJ_INDEX_INVALID != adj_index)
 381     {
 382         dpo_set(&tmp_dpo,
 383                 DPO_ADJACENCY,
 384                 FIB_PROTOCOL_MAX,
 385                 adj_index);
 386     }
 387     else
 388     {
 389         dpo_copy(&tmp_dpo, drop_dpo_get(fib_proto_to_dpo(prefix->fp_proto)));
 390     }
 391
 392     fib_entry_index = fib_table_entry_special_dpo_add(fib_index, prefix, source,
 393                                                       flags, &tmp_dpo);
 394
 395     dpo_unlock(&tmp_dpo);
 396
 397     return (fib_entry_index);
 398 }
 399
 400 void
 401 fib_table_entry_special_remove (u32 fib_index,
 402                                 const fib_prefix_t *prefix,
 403                                 fib_source_t source)
 404 {
 405     /*
 406      * 1 is it present
 407      *   yes => remove source
 408      *    2 - is it still sourced?
 409      *      no => cover walk
 410      */
 411     fib_node_index_t fib_entry_index;
 412     fib_table_t *fib_table;
 413
 414     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 415     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 416
 417     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 418     {
 419         /*
 420          * removing an etry that does not exist. i'll allow it.
 421          */
 422     }
 423     else
 424     {
 425         fib_entry_src_flag_t src_flag;
 426         int was_sourced;
 427
 428         /*
 429          * don't nobody go nowhere
 430          */
 431         fib_entry_lock(fib_entry_index);
 432         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 433
 434         src_flag = fib_entry_special_remove(fib_entry_index, source);
 435
 436         if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 437         {
 438             /*
 439              * last source gone. remove from the table
 440              */
 441             fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 442
 443             /*
 444              * now the entry is no longer in the table, we can
 445              * inform the entries that it covers to re-calculate their cover
 446              */
 447             fib_entry_cover_change_notify(fib_entry_index,
 448                                           FIB_NODE_INDEX_INVALID);
 449         }
 450         /*
 451          * else
 452          *   still has sources, leave it be.
 453          */
 454         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 455         {
 456             fib_table->ft_src_route_counts[source]--;
 457         }
 458
 459         fib_entry_unlock(fib_entry_index);
 460     }
 461 }
 462
 463 /**
 464  * fib_table_route_path_fixup
 465  *
 466  * Convert attached hosts to attached next-hops.
 467  *
 468  * This special case is required because an attached path will link to a
 469  * glean, and the FIB entry will have the interface or API/CLI source. When
 470  * the ARP/ND process is completes then that source (which will provide a
 471  * complete adjacency) will be lower priority and so the FIB entry will
 472  * remain linked to a glean and traffic will never reach the hosts. For
 473  * an ATTAHCED_HOST path we can link the path directly to the [incomplete]
 474  * adjacency.
 475  */
 476 static void
 477 fib_table_route_path_fixup (const fib_prefix_t *prefix,
 478                             fib_entry_flag_t eflags,
 479                             fib_route_path_t *path)
 480 {
 481     /*
 482      * not all zeros next hop &&
 483      * is recursive path &&
 484      * nexthop is same as the route's address
 485      */
 486     if ((!ip46_address_is_zero(&path->frp_addr)) &&
 487         (~0 == path->frp_sw_if_index) &&
 488         (0 == ip46_address_cmp(&path->frp_addr, &prefix->fp_addr)))
 489     {
 490         /* Prefix recurses via itse;f */
 491         path->frp_flags |= FIB_ROUTE_PATH_DROP;
 492     }
 493     if (fib_prefix_is_host(prefix) &&
 494         ip46_address_is_zero(&path->frp_addr) &&
 495         path->frp_sw_if_index != ~0)
 496     {
 497         path->frp_addr = prefix->fp_addr;
 498         path->frp_flags |= FIB_ROUTE_PATH_ATTACHED;
 499     }
 500     if (eflags & FIB_ENTRY_FLAG_DROP)
 501     {
 502         path->frp_flags |= FIB_ROUTE_PATH_DROP;
 503     }
 504     if (eflags & FIB_ENTRY_FLAG_LOCAL)
 505     {
 506         path->frp_flags |= FIB_ROUTE_PATH_LOCAL;
 507     }
 508     if (eflags & FIB_ENTRY_FLAG_EXCLUSIVE)
 509     {
 510         path->frp_flags |= FIB_ROUTE_PATH_EXCLUSIVE;
 511     }
 512 }
 513
 514 fib_node_index_t
 515 fib_table_entry_path_add (u32 fib_index,
 516                           const fib_prefix_t *prefix,
 517                           fib_source_t source,
 518                           fib_entry_flag_t flags,
 519                           fib_protocol_t next_hop_proto,
 520                           const ip46_address_t *next_hop,
 521                           u32 next_hop_sw_if_index,
 522                           u32 next_hop_fib_index,
 523                           u32 next_hop_weight,
 524                           mpls_label_t *next_hop_labels,
 525                           fib_route_path_flags_t path_flags)
 526 {
 527     fib_route_path_t path = {
 528         .frp_proto = next_hop_proto,
 529         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 530         .frp_sw_if_index = next_hop_sw_if_index,
 531         .frp_fib_index = next_hop_fib_index,
 532         .frp_weight = next_hop_weight,
 533         .frp_flags = path_flags,
 534         .frp_label_stack = next_hop_labels,
 535     };
 536     fib_node_index_t fib_entry_index;
 537     fib_route_path_t *paths = NULL;
 538
 539     vec_add1(paths, path);
 540
 541     fib_entry_index = fib_table_entry_path_add2(fib_index, prefix,
 542                                                 source, flags, paths);
 543
 544     vec_free(paths);
 545     return (fib_entry_index);
 546 }
 547
 548 fib_node_index_t
 549 fib_table_entry_path_add2 (u32 fib_index,
 550                            const fib_prefix_t *prefix,
 551                            fib_source_t source,
 552                            fib_entry_flag_t flags,
 553                            fib_route_path_t *rpath)
 554 {
 555     fib_node_index_t fib_entry_index;
 556     fib_table_t *fib_table;
 557     u32 ii;
 558
 559     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 560     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 561
 562     for (ii = 0; ii < vec_len(rpath); ii++)
 563     {
 564         fib_table_route_path_fixup(prefix, flags, &rpath[ii]);
 565     }
 566
 567     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 568     {
 569         fib_entry_index = fib_entry_create(fib_index, prefix,
 570                                            source, flags,
 571                                            rpath);
 572
 573         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 574         fib_table->ft_src_route_counts[source]++;
 575     }
 576     else
 577     {
 578         int was_sourced;
 579
 580         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 581         fib_entry_path_add(fib_entry_index, source, flags, rpath);;
 582
 583         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 584         {
 585             fib_table->ft_src_route_counts[source]++;
 586         }
 587     }
 588
 589     return (fib_entry_index);
 590 }
 591
 592 void
 593 fib_table_entry_path_remove2 (u32 fib_index,
 594                               const fib_prefix_t *prefix,
 595                               fib_source_t source,
 596                               fib_route_path_t *rpath)
 597 {
 598     /*
 599      * 1 is it present
 600      *   yes => remove source
 601      *    2 - is it still sourced?
 602      *      no => cover walk
 603      */
 604     fib_node_index_t fib_entry_index;
 605     fib_table_t *fib_table;
 606     u32 ii;
 607
 608     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 609     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 610
 611     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 612     {
 613         /*
 614          * removing an etry that does not exist. i'll allow it.
 615          */
 616     }
 617     else
 618     {
 619         fib_entry_src_flag_t src_flag;
 620         int was_sourced;
 621
 622         /*
 623          * don't nobody go nowhere
 624          */
 625         fib_entry_lock(fib_entry_index);
 626         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 627
 628         for (ii = 0; ii < vec_len(rpath); ii++)
 629         {
 630             fib_table_route_path_fixup(
 631                 prefix,
 632                 fib_entry_get_flags_for_source(fib_entry_index,
 633                                                source),
 634                 &rpath[ii]);
 635         }
 636
 637         src_flag = fib_entry_path_remove(fib_entry_index, source, rpath);
 638
 639         if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 640         {
 641             /*
 642              * last source gone. remove from the table
 643              */
 644             fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 645
 646             /*
 647              * now the entry is no longer in the table, we can
 648              * inform the entries that it covers to re-calculate their cover
 649              */
 650             fib_entry_cover_change_notify(fib_entry_index,
 651                                           FIB_NODE_INDEX_INVALID);
 652         }
 653         /*
 654          * else
 655          *   still has sources, leave it be.
 656          */
 657         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 658         {
 659             fib_table->ft_src_route_counts[source]--;
 660         }
 661
 662         fib_entry_unlock(fib_entry_index);
 663     }
 664 }
 665
 666 void
 667 fib_table_entry_path_remove (u32 fib_index,
 668                              const fib_prefix_t *prefix,
 669                              fib_source_t source,
 670                              fib_protocol_t next_hop_proto,
 671                              const ip46_address_t *next_hop,
 672                              u32 next_hop_sw_if_index,
 673                              u32 next_hop_fib_index,
 674                              u32 next_hop_weight,
 675                              fib_route_path_flags_t path_flags)
 676 {
 677     /*
 678      * 1 is it present
 679      *   yes => remove source
 680      *    2 - is it still sourced?
 681      *      no => cover walk
 682      */
 683     fib_route_path_t path = {
 684         .frp_proto = next_hop_proto,
 685         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 686         .frp_sw_if_index = next_hop_sw_if_index,
 687         .frp_fib_index = next_hop_fib_index,
 688         .frp_weight = next_hop_weight,
 689         .frp_flags = path_flags,
 690     };
 691     fib_route_path_t *paths = NULL;
 692
 693     vec_add1(paths, path);
 694
 695     fib_table_entry_path_remove2(fib_index, prefix, source, paths);
 696
 697     vec_free(paths);
 698 }
 699
 700 static int
 701 fib_route_path_cmp_for_sort (void * v1,
 702                              void * v2)
 703 {
 704     return (fib_route_path_cmp(v1, v2));
 705 }
 706
 707 fib_node_index_t
 708 fib_table_entry_update (u32 fib_index,
 709                         const fib_prefix_t *prefix,
 710                         fib_source_t source,
 711                         fib_entry_flag_t flags,
 712                         fib_route_path_t *paths)
 713 {
 714     fib_node_index_t fib_entry_index;
 715     fib_table_t *fib_table;
 716     u32 ii;
 717
 718     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 719     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 720
 721     for (ii = 0; ii < vec_len(paths); ii++)
 722     {
 723         fib_table_route_path_fixup(prefix, flags, &paths[ii]);
 724     }
 725     /*
 726      * sort the paths provided by the control plane. this means
 727      * the paths and the extension on the entry will be sorted.
 728      */
 729     vec_sort_with_function(paths, fib_route_path_cmp_for_sort);
 730
 731     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 732     {
 733         fib_entry_index = fib_entry_create(fib_index, prefix,
 734                                            source, flags,
 735                                            paths);
 736
 737         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 738         fib_table->ft_src_route_counts[source]++;
 739     }
 740     else
 741     {
 742         int was_sourced;
 743
 744         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 745         fib_entry_update(fib_entry_index, source, flags, paths);
 746
 747         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 748         {
 749             fib_table->ft_src_route_counts[source]++;
 750         }
 751     }
 752
 753     return (fib_entry_index);
 754 }
 755
 756 fib_node_index_t
 757 fib_table_entry_update_one_path (u32 fib_index,
 758                                  const fib_prefix_t *prefix,
 759                                  fib_source_t source,
 760                                  fib_entry_flag_t flags,
 761                                  fib_protocol_t next_hop_proto,
 762                                  const ip46_address_t *next_hop,
 763                                  u32 next_hop_sw_if_index,
 764                                  u32 next_hop_fib_index,
 765                                  u32 next_hop_weight,
 766                                  mpls_label_t *next_hop_labels,
 767                                  fib_route_path_flags_t path_flags)
 768 {
 769     fib_node_index_t fib_entry_index;
 770     fib_route_path_t path = {
 771         .frp_proto = next_hop_proto,
 772         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 773         .frp_sw_if_index = next_hop_sw_if_index,
 774         .frp_fib_index = next_hop_fib_index,
 775         .frp_weight = next_hop_weight,
 776         .frp_flags = path_flags,
 777         .frp_label_stack = next_hop_labels,
 778     };
 779     fib_route_path_t *paths = NULL;
 780
 781     vec_add1(paths, path);
 782
 783     fib_entry_index =
 784         fib_table_entry_update(fib_index, prefix, source, flags, paths);
 785
 786     vec_free(paths);
 787
 788     return (fib_entry_index);
 789 }
 790
 791 static void
 792 fib_table_entry_delete_i (u32 fib_index,
 793                           fib_node_index_t fib_entry_index,
 794                           const fib_prefix_t *prefix,
 795                           fib_source_t source)
 796 {
 797     fib_entry_src_flag_t src_flag;
 798     fib_table_t *fib_table;
 799     int was_sourced;
 800
 801     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 802     was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 803
 804     /*
 805      * don't nobody go nowhere
 806      */
 807     fib_entry_lock(fib_entry_index);
 808
 809     src_flag = fib_entry_delete(fib_entry_index, source);
 810
 811     if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 812     {
 813         /*
 814          * last source gone. remove from the table
 815          */
 816         fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 817
 818         /*
 819          * now the entry is no longer in the table, we can
 820          * inform the entries that it covers to re-calculate their cover
 821          */
 822         fib_entry_cover_change_notify(fib_entry_index,
 823                                       FIB_NODE_INDEX_INVALID);
 824     }
 825     /*
 826      * else
 827      *   still has sources, leave it be.
 828      */
 829     if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 830     {
 831         fib_table->ft_src_route_counts[source]--;
 832     }
 833
 834     fib_entry_unlock(fib_entry_index);
 835 }
 836
 837 void
 838 fib_table_entry_delete (u32 fib_index,
 839                         const fib_prefix_t *prefix,
 840                         fib_source_t source)
 841 {
 842     fib_node_index_t fib_entry_index;
 843
 844     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 845
 846     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 847     {
 848         /*
 849          * removing an etry that does not exist.
 850          * i'll allow it, but i won't like it.
 851          */
 852         clib_warning("%U not in FIB", format_fib_prefix, prefix);
 853     }
 854     else
 855     {
 856         fib_table_entry_delete_i(fib_index, fib_entry_index, prefix, source);
 857     }
 858 }
 859
 860 void
 861 fib_table_entry_delete_index (fib_node_index_t fib_entry_index,
 862                               fib_source_t source)
 863 {
 864     fib_prefix_t prefix;
 865
 866     fib_entry_get_prefix(fib_entry_index, &prefix);
 867
 868     fib_table_entry_delete_i(fib_entry_get_fib_index(fib_entry_index),
 869                              fib_entry_index, &prefix, source);
 870 }
 871
 872 fib_node_index_t
 873 fib_table_entry_local_label_add (u32 fib_index,
 874                                  const fib_prefix_t *prefix,
 875                                  mpls_label_t label)
 876 {
 877     fib_node_index_t fib_entry_index;
 878
 879     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 880
 881     if (FIB_NODE_INDEX_INVALID == fib_entry_index ||
 882         !fib_entry_is_sourced(fib_entry_index, FIB_SOURCE_MPLS))
 883     {
 884         /*
 885          * only source the prefix once. this allows the label change
 886          * operation to work
 887          */
 888         fib_entry_index = fib_table_entry_special_dpo_add(fib_index, prefix,
 889                                                           FIB_SOURCE_MPLS,
 890                                                           FIB_ENTRY_FLAG_NONE,
 891                                                           NULL);
 892     }
 893
 894     fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &label);
 895
 896     return (fib_entry_index);
 897 }
 898
 899 void
 900 fib_table_entry_local_label_remove (u32 fib_index,
 901                                     const fib_prefix_t *prefix,
 902                                     mpls_label_t label)
 903 {
 904     fib_node_index_t fib_entry_index;
 905     const void *data;
 906     mpls_label_t pl;
 907
 908     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 909
 910     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 911         return;
 912
 913     data = fib_entry_get_source_data(fib_entry_index, FIB_SOURCE_MPLS);
 914
 915     if (NULL == data)
 916         return;
 917
 918     pl = *(mpls_label_t*)data;
 919
 920     if (pl != label)
 921         return;
 922
 923     pl = MPLS_LABEL_INVALID;
 924
 925     fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &pl);
 926     fib_table_entry_special_remove(fib_index,
 927                                    prefix,
 928                                    FIB_SOURCE_MPLS);
 929 }
 930
 931 u32
 932 fib_table_get_index_for_sw_if_index (fib_protocol_t proto,
 933                                      u32 sw_if_index)
 934 {
 935     switch (proto)
 936     {
 937     case FIB_PROTOCOL_IP4:
 938         return (ip4_fib_table_get_index_for_sw_if_index(sw_if_index));
 939     case FIB_PROTOCOL_IP6:
 940         return (ip6_fib_table_get_index_for_sw_if_index(sw_if_index));
 941     case FIB_PROTOCOL_MPLS:
 942         return (mpls_fib_table_get_index_for_sw_if_index(sw_if_index));
 943     }
 944     return (~0);
 945 }
 946
 947 flow_hash_config_t
 948 fib_table_get_flow_hash_config (u32 fib_index,
 949                                 fib_protocol_t proto)
 950 {
 951     switch (proto)
 952     {
 953     case FIB_PROTOCOL_IP4:
 954         return (ip4_fib_table_get_flow_hash_config(fib_index));
 955     case FIB_PROTOCOL_IP6:
 956         return (ip6_fib_table_get_flow_hash_config(fib_index));
 957     case FIB_PROTOCOL_MPLS:
 958         return (mpls_fib_table_get_flow_hash_config(fib_index));
 959     }
 960     return (0);
 961 }
 962
 963
 964 u32
 965 fib_table_get_table_id_for_sw_if_index (fib_protocol_t proto,
 966                                         u32 sw_if_index)
 967 {
 968     fib_table_t *fib_table;
 969
 970     fib_table = fib_table_get(fib_table_get_index_for_sw_if_index(
 971                                   proto, sw_if_index),
 972                               proto);
 973
 974     return ((NULL != fib_table ? fib_table->ft_table_id : ~0));
 975 }
 976
 977 u32
 978 fib_table_find (fib_protocol_t proto,
 979                 u32 table_id)
 980 {
 981     switch (proto)
 982     {
 983     case FIB_PROTOCOL_IP4:
 984         return (ip4_fib_index_from_table_id(table_id));
 985     case FIB_PROTOCOL_IP6:
 986         return (ip6_fib_index_from_table_id(table_id));
 987     case FIB_PROTOCOL_MPLS:
 988         return (mpls_fib_index_from_table_id(table_id));
 989     }
 990     return (~0);
 991 }
 992
 993 u32
 994 fib_table_find_or_create_and_lock (fib_protocol_t proto,
 995                                    u32 table_id)
 996 {
 997     fib_table_t *fib_table;
 998     fib_node_index_t fi;
 999
1000     switch (proto)
1001     {
1002     case FIB_PROTOCOL_IP4:
1003         fi = ip4_fib_table_find_or_create_and_lock(table_id);
1004         break;
1005     case FIB_PROTOCOL_IP6:
1006         fi = ip6_fib_table_find_or_create_and_lock(table_id);
1007         break;
1008     case FIB_PROTOCOL_MPLS:
1009         fi = mpls_fib_table_find_or_create_and_lock(table_id);
1010         break;
1011     default:
1012         return (~0);
1013     }
1014
1015     fib_table = fib_table_get(fi, proto);
1016
1017     fib_table->ft_desc = format(NULL, "%U-VRF:%d",
1018                                 format_fib_protocol, proto,
1019                                 table_id);
1020
1021     return (fi);
1022 }
1023
1024 u32
1025 fib_table_create_and_lock (fib_protocol_t proto,
1026                            const char *const fmt,
1027                            ...)
1028 {
1029     fib_table_t *fib_table;
1030     fib_node_index_t fi;
1031     va_list ap;
1032
1033     va_start(ap, fmt);
1034
1035     switch (proto)
1036     {
1037     case FIB_PROTOCOL_IP4:
1038         fi = ip4_fib_table_create_and_lock();
1039         break;
1040     case FIB_PROTOCOL_IP6:
1041         fi = ip6_fib_table_create_and_lock();
1042         break;
1043      case FIB_PROTOCOL_MPLS:
1044         fi = mpls_fib_table_create_and_lock();
1045         break;
1046    default:
1047         return (~0);
1048     }
1049
1050     fib_table = fib_table_get(fi, proto);
1051
1052     fib_table->ft_desc = va_format(fib_table->ft_desc, fmt, &ap);
1053
1054     va_end(ap);
1055     return (fi);
1056 }
1057
1058 static void
1059 fib_table_destroy (fib_table_t *fib_table)
1060 {
1061     vec_free(fib_table->ft_desc);
1062
1063     switch (fib_table->ft_proto)
1064     {
1065     case FIB_PROTOCOL_IP4:
1066         ip4_fib_table_destroy(fib_table->ft_index);
1067         break;
1068     case FIB_PROTOCOL_IP6:
1069         ip6_fib_table_destroy(fib_table->ft_index);
1070         break;
1071     case FIB_PROTOCOL_MPLS:
1072         mpls_fib_table_destroy(fib_table->ft_index);
1073         break;
1074     }
1075 }
1076
1077 void
1078 fib_table_walk (u32 fib_index,
1079                 fib_protocol_t proto,
1080                 fib_table_walk_fn_t fn,
1081                 void *ctx)
1082 {
1083     switch (proto)
1084     {
1085     case FIB_PROTOCOL_IP4:
1086         ip4_fib_table_walk(ip4_fib_get(fib_index), fn, ctx);
1087         break;
1088     case FIB_PROTOCOL_IP6:
1089         ip6_fib_table_walk(fib_index, fn, ctx);
1090         break;
1091     case FIB_PROTOCOL_MPLS:
1092         mpls_fib_table_walk(mpls_fib_get(fib_index), fn, ctx);
1093         break;
1094     }
1095 }
1096
1097 void
1098 fib_table_unlock (u32 fib_index,
1099                   fib_protocol_t proto)
1100 {
1101     fib_table_t *fib_table;
1102
1103     fib_table = fib_table_get(fib_index, proto);
1104     fib_table->ft_locks--;
1105
1106     if (0 == fib_table->ft_locks)
1107     {
1108         fib_table_destroy(fib_table);
1109     }
1110 }
1111 void
1112 fib_table_lock (u32 fib_index,
1113                 fib_protocol_t proto)
1114 {
1115     fib_table_t *fib_table;
1116
1117     fib_table = fib_table_get(fib_index, proto);
1118     fib_table->ft_locks++;
1119 }
1120
1121 u32
1122 fib_table_get_num_entries (u32 fib_index,
1123                            fib_protocol_t proto,
1124                            fib_source_t source)
1125 {
1126     fib_table_t *fib_table;
1127
1128     fib_table = fib_table_get(fib_index, proto);
1129
1130     return (fib_table->ft_src_route_counts[source]);
1131 }
1132
1133 u8*
1134 format_fib_table_name (u8* s, va_list ap)
1135 {
1136     fib_node_index_t fib_index = va_arg(ap, fib_node_index_t);
1137     fib_protocol_t proto = va_arg(ap, int); // int promotion
1138     fib_table_t *fib_table;
1139
1140     fib_table = fib_table_get(fib_index, proto);
1141
1142     s = format(s, "%v", fib_table->ft_desc);
1143
1144     return (s);
1145 }
1146
1147 /**
1148  * @brief Table flush context. Store the indicies of matching FIB entries
1149  * that need to be removed.
1150  */
1151 typedef struct fib_table_flush_ctx_t_
1152 {
1153     /**
1154      * The list of entries to flush
1155      */
1156     fib_node_index_t *ftf_entries;
1157
1158     /**
1159      * The source we are flushing
1160      */
1161     fib_source_t ftf_source;
1162 } fib_table_flush_ctx_t;
1163
1164 static int
1165 fib_table_flush_cb (fib_node_index_t fib_entry_index,
1166                     void *arg)
1167 {
1168     fib_table_flush_ctx_t *ctx = arg;
1169
1170     if (fib_entry_is_sourced(fib_entry_index, ctx->ftf_source))
1171     {
1172         vec_add1(ctx->ftf_entries, fib_entry_index);
1173     }
1174     return (1);
1175 }
1176
1177
1178 void
1179 fib_table_flush (u32 fib_index,
1180                  fib_protocol_t proto,
1181                  fib_source_t source)
1182 {
1183     fib_node_index_t *fib_entry_index;
1184     fib_table_flush_ctx_t ctx = {
1185         .ftf_entries = NULL,
1186         .ftf_source = source,
1187     };
1188
1189     fib_table_walk(fib_index, proto,
1190                    fib_table_flush_cb,
1191                    &ctx);
1192
1193     vec_foreach(fib_entry_index, ctx.ftf_entries)
1194     {
1195         fib_table_entry_delete_index(*fib_entry_index, source);
1196     }
1197
1198     vec_free(ctx.ftf_entries);
1199 }