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 {
 376     fib_node_index_t fib_entry_index;
 377     dpo_id_t tmp_dpo = DPO_INVALID;
 378
 379     dpo_copy(&tmp_dpo, drop_dpo_get(fib_proto_to_dpo(prefix->fp_proto)));
 380
 381     fib_entry_index = fib_table_entry_special_dpo_add(fib_index, prefix, source,
 382                                                       flags, &tmp_dpo);
 383
 384     dpo_unlock(&tmp_dpo);
 385
 386     return (fib_entry_index);
 387 }
 388
 389 void
 390 fib_table_entry_special_remove (u32 fib_index,
 391                                 const fib_prefix_t *prefix,
 392                                 fib_source_t source)
 393 {
 394     /*
 395      * 1 is it present
 396      *   yes => remove source
 397      *    2 - is it still sourced?
 398      *      no => cover walk
 399      */
 400     fib_node_index_t fib_entry_index;
 401     fib_table_t *fib_table;
 402
 403     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 404     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 405
 406     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 407     {
 408         /*
 409          * removing an etry that does not exist. i'll allow it.
 410          */
 411     }
 412     else
 413     {
 414         fib_entry_src_flag_t src_flag;
 415         int was_sourced;
 416
 417         /*
 418          * don't nobody go nowhere
 419          */
 420         fib_entry_lock(fib_entry_index);
 421         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 422
 423         src_flag = fib_entry_special_remove(fib_entry_index, source);
 424
 425         if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 426         {
 427             /*
 428              * last source gone. remove from the table
 429              */
 430             fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 431
 432             /*
 433              * now the entry is no longer in the table, we can
 434              * inform the entries that it covers to re-calculate their cover
 435              */
 436             fib_entry_cover_change_notify(fib_entry_index,
 437                                           FIB_NODE_INDEX_INVALID);
 438         }
 439         /*
 440          * else
 441          *   still has sources, leave it be.
 442          */
 443         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 444         {
 445             fib_table->ft_src_route_counts[source]--;
 446         }
 447
 448         fib_entry_unlock(fib_entry_index);
 449     }
 450 }
 451
 452 /**
 453  * fib_table_route_path_fixup
 454  *
 455  * Convert attached hosts to attached next-hops.
 456  *
 457  * This special case is required because an attached path will link to a
 458  * glean, and the FIB entry will have the interface or API/CLI source. When
 459  * the ARP/ND process is completes then that source (which will provide a
 460  * complete adjacency) will be lower priority and so the FIB entry will
 461  * remain linked to a glean and traffic will never reach the hosts. For
 462  * an ATTAHCED_HOST path we can link the path directly to the [incomplete]
 463  * adjacency.
 464  */
 465 static void
 466 fib_table_route_path_fixup (const fib_prefix_t *prefix,
 467                             fib_entry_flag_t eflags,
 468                             fib_route_path_t *path)
 469 {
 470     /*
 471      * not all zeros next hop &&
 472      * is recursive path &&
 473      * nexthop is same as the route's address
 474      */
 475     if ((!ip46_address_is_zero(&path->frp_addr)) &&
 476         (~0 == path->frp_sw_if_index) &&
 477         (0 == ip46_address_cmp(&path->frp_addr, &prefix->fp_addr)))
 478     {
 479         /* Prefix recurses via itse;f */
 480         path->frp_flags |= FIB_ROUTE_PATH_DROP;
 481     }
 482     if (fib_prefix_is_host(prefix) &&
 483         ip46_address_is_zero(&path->frp_addr) &&
 484         path->frp_sw_if_index != ~0 &&
 485         path->frp_proto != DPO_PROTO_ETHERNET)
 486     {
 487         path->frp_addr = prefix->fp_addr;
 488         path->frp_flags |= FIB_ROUTE_PATH_ATTACHED;
 489     }
 490     if (eflags & FIB_ENTRY_FLAG_DROP)
 491     {
 492         path->frp_flags |= FIB_ROUTE_PATH_DROP;
 493     }
 494     if (eflags & FIB_ENTRY_FLAG_LOCAL)
 495     {
 496         path->frp_flags |= FIB_ROUTE_PATH_LOCAL;
 497     }
 498     if (eflags & FIB_ENTRY_FLAG_EXCLUSIVE)
 499     {
 500         path->frp_flags |= FIB_ROUTE_PATH_EXCLUSIVE;
 501     }
 502 }
 503
 504 fib_node_index_t
 505 fib_table_entry_path_add (u32 fib_index,
 506                           const fib_prefix_t *prefix,
 507                           fib_source_t source,
 508                           fib_entry_flag_t flags,
 509                           dpo_proto_t next_hop_proto,
 510                           const ip46_address_t *next_hop,
 511                           u32 next_hop_sw_if_index,
 512                           u32 next_hop_fib_index,
 513                           u32 next_hop_weight,
 514                           mpls_label_t *next_hop_labels,
 515                           fib_route_path_flags_t path_flags)
 516 {
 517     fib_route_path_t path = {
 518         .frp_proto = next_hop_proto,
 519         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 520         .frp_sw_if_index = next_hop_sw_if_index,
 521         .frp_fib_index = next_hop_fib_index,
 522         .frp_weight = next_hop_weight,
 523         .frp_flags = path_flags,
 524         .frp_label_stack = next_hop_labels,
 525     };
 526     fib_node_index_t fib_entry_index;
 527     fib_route_path_t *paths = NULL;
 528
 529     vec_add1(paths, path);
 530
 531     fib_entry_index = fib_table_entry_path_add2(fib_index, prefix,
 532                                                 source, flags, paths);
 533
 534     vec_free(paths);
 535     return (fib_entry_index);
 536 }
 537
 538 fib_node_index_t
 539 fib_table_entry_path_add2 (u32 fib_index,
 540                            const fib_prefix_t *prefix,
 541                            fib_source_t source,
 542                            fib_entry_flag_t flags,
 543                            fib_route_path_t *rpath)
 544 {
 545     fib_node_index_t fib_entry_index;
 546     fib_table_t *fib_table;
 547     u32 ii;
 548
 549     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 550     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 551
 552     for (ii = 0; ii < vec_len(rpath); ii++)
 553     {
 554         fib_table_route_path_fixup(prefix, flags, &rpath[ii]);
 555     }
 556
 557     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 558     {
 559         fib_entry_index = fib_entry_create(fib_index, prefix,
 560                                            source, flags,
 561                                            rpath);
 562
 563         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 564         fib_table->ft_src_route_counts[source]++;
 565     }
 566     else
 567     {
 568         int was_sourced;
 569
 570         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 571         fib_entry_path_add(fib_entry_index, source, flags, rpath);;
 572
 573         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 574         {
 575             fib_table->ft_src_route_counts[source]++;
 576         }
 577     }
 578
 579     return (fib_entry_index);
 580 }
 581
 582 void
 583 fib_table_entry_path_remove2 (u32 fib_index,
 584                               const fib_prefix_t *prefix,
 585                               fib_source_t source,
 586                               fib_route_path_t *rpath)
 587 {
 588     /*
 589      * 1 is it present
 590      *   yes => remove source
 591      *    2 - is it still sourced?
 592      *      no => cover walk
 593      */
 594     fib_node_index_t fib_entry_index;
 595     fib_table_t *fib_table;
 596     u32 ii;
 597
 598     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 599     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 600
 601     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 602     {
 603         /*
 604          * removing an etry that does not exist. i'll allow it.
 605          */
 606     }
 607     else
 608     {
 609         fib_entry_src_flag_t src_flag;
 610         int was_sourced;
 611
 612         /*
 613          * if it's not sourced, then there's nowt to remove
 614          */
 615         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 616         if (!was_sourced)
 617         {
 618             return;
 619         }
 620
 621         /*
 622          * don't nobody go nowhere
 623          */
 624         fib_entry_lock(fib_entry_index);
 625
 626         for (ii = 0; ii < vec_len(rpath); ii++)
 627         {
 628             fib_table_route_path_fixup(
 629                 prefix,
 630                 fib_entry_get_flags_for_source(fib_entry_index,
 631                                                source),
 632                 &rpath[ii]);
 633         }
 634
 635         src_flag = fib_entry_path_remove(fib_entry_index, source, rpath);
 636
 637         if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 638         {
 639             /*
 640              * last source gone. remove from the table
 641              */
 642             fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 643
 644             /*
 645              * now the entry is no longer in the table, we can
 646              * inform the entries that it covers to re-calculate their cover
 647              */
 648             fib_entry_cover_change_notify(fib_entry_index,
 649                                           FIB_NODE_INDEX_INVALID);
 650         }
 651         /*
 652          * else
 653          *   still has sources, leave it be.
 654          */
 655         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 656         {
 657             fib_table->ft_src_route_counts[source]--;
 658         }
 659
 660         fib_entry_unlock(fib_entry_index);
 661     }
 662 }
 663
 664 void
 665 fib_table_entry_path_remove (u32 fib_index,
 666                              const fib_prefix_t *prefix,
 667                              fib_source_t source,
 668                              dpo_proto_t next_hop_proto,
 669                              const ip46_address_t *next_hop,
 670                              u32 next_hop_sw_if_index,
 671                              u32 next_hop_fib_index,
 672                              u32 next_hop_weight,
 673                              fib_route_path_flags_t path_flags)
 674 {
 675     /*
 676      * 1 is it present
 677      *   yes => remove source
 678      *    2 - is it still sourced?
 679      *      no => cover walk
 680      */
 681     fib_route_path_t path = {
 682         .frp_proto = next_hop_proto,
 683         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 684         .frp_sw_if_index = next_hop_sw_if_index,
 685         .frp_fib_index = next_hop_fib_index,
 686         .frp_weight = next_hop_weight,
 687         .frp_flags = path_flags,
 688     };
 689     fib_route_path_t *paths = NULL;
 690
 691     vec_add1(paths, path);
 692
 693     fib_table_entry_path_remove2(fib_index, prefix, source, paths);
 694
 695     vec_free(paths);
 696 }
 697
 698 static int
 699 fib_route_path_cmp_for_sort (void * v1,
 700                              void * v2)
 701 {
 702     return (fib_route_path_cmp(v1, v2));
 703 }
 704
 705 fib_node_index_t
 706 fib_table_entry_update (u32 fib_index,
 707                         const fib_prefix_t *prefix,
 708                         fib_source_t source,
 709                         fib_entry_flag_t flags,
 710                         fib_route_path_t *paths)
 711 {
 712     fib_node_index_t fib_entry_index;
 713     fib_table_t *fib_table;
 714     u32 ii;
 715
 716     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 717     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 718
 719     for (ii = 0; ii < vec_len(paths); ii++)
 720     {
 721         fib_table_route_path_fixup(prefix, flags, &paths[ii]);
 722     }
 723     /*
 724      * sort the paths provided by the control plane. this means
 725      * the paths and the extension on the entry will be sorted.
 726      */
 727     vec_sort_with_function(paths, fib_route_path_cmp_for_sort);
 728
 729     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 730     {
 731         fib_entry_index = fib_entry_create(fib_index, prefix,
 732                                            source, flags,
 733                                            paths);
 734
 735         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 736         fib_table->ft_src_route_counts[source]++;
 737     }
 738     else
 739     {
 740         int was_sourced;
 741
 742         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 743         fib_entry_update(fib_entry_index, source, flags, paths);
 744
 745         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 746         {
 747             fib_table->ft_src_route_counts[source]++;
 748         }
 749     }
 750
 751     return (fib_entry_index);
 752 }
 753
 754 fib_node_index_t
 755 fib_table_entry_update_one_path (u32 fib_index,
 756                                  const fib_prefix_t *prefix,
 757                                  fib_source_t source,
 758                                  fib_entry_flag_t flags,
 759                                  dpo_proto_t next_hop_proto,
 760                                  const ip46_address_t *next_hop,
 761                                  u32 next_hop_sw_if_index,
 762                                  u32 next_hop_fib_index,
 763                                  u32 next_hop_weight,
 764                                  mpls_label_t *next_hop_labels,
 765                                  fib_route_path_flags_t path_flags)
 766 {
 767     fib_node_index_t fib_entry_index;
 768     fib_route_path_t path = {
 769         .frp_proto = next_hop_proto,
 770         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 771         .frp_sw_if_index = next_hop_sw_if_index,
 772         .frp_fib_index = next_hop_fib_index,
 773         .frp_weight = next_hop_weight,
 774         .frp_flags = path_flags,
 775         .frp_label_stack = next_hop_labels,
 776     };
 777     fib_route_path_t *paths = NULL;
 778
 779     vec_add1(paths, path);
 780
 781     fib_entry_index =
 782         fib_table_entry_update(fib_index, prefix, source, flags, paths);
 783
 784     vec_free(paths);
 785
 786     return (fib_entry_index);
 787 }
 788
 789 static void
 790 fib_table_entry_delete_i (u32 fib_index,
 791                           fib_node_index_t fib_entry_index,
 792                           const fib_prefix_t *prefix,
 793                           fib_source_t source)
 794 {
 795     fib_entry_src_flag_t src_flag;
 796     fib_table_t *fib_table;
 797     int was_sourced;
 798
 799     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 800     was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 801
 802     /*
 803      * don't nobody go nowhere
 804      */
 805     fib_entry_lock(fib_entry_index);
 806
 807     src_flag = fib_entry_delete(fib_entry_index, source);
 808
 809     if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 810     {
 811         /*
 812          * last source gone. remove from the table
 813          */
 814         fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 815
 816         /*
 817          * now the entry is no longer in the table, we can
 818          * inform the entries that it covers to re-calculate their cover
 819          */
 820         fib_entry_cover_change_notify(fib_entry_index,
 821                                       FIB_NODE_INDEX_INVALID);
 822     }
 823     /*
 824      * else
 825      *   still has sources, leave it be.
 826      */
 827     if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 828     {
 829         fib_table->ft_src_route_counts[source]--;
 830     }
 831
 832     fib_entry_unlock(fib_entry_index);
 833 }
 834
 835 void
 836 fib_table_entry_delete (u32 fib_index,
 837                         const fib_prefix_t *prefix,
 838                         fib_source_t source)
 839 {
 840     fib_node_index_t fib_entry_index;
 841
 842     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 843
 844     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 845     {
 846         /*
 847          * removing an etry that does not exist.
 848          * i'll allow it, but i won't like it.
 849          */
 850         if (0)
 851             clib_warning("%U not in FIB", format_fib_prefix, prefix);
 852     }
 853     else
 854     {
 855         fib_table_entry_delete_i(fib_index, fib_entry_index, prefix, source);
 856     }
 857 }
 858
 859 void
 860 fib_table_entry_delete_index (fib_node_index_t fib_entry_index,
 861                               fib_source_t source)
 862 {
 863     fib_prefix_t prefix;
 864
 865     fib_entry_get_prefix(fib_entry_index, &prefix);
 866
 867     fib_table_entry_delete_i(fib_entry_get_fib_index(fib_entry_index),
 868                              fib_entry_index, &prefix, source);
 869 }
 870
 871 fib_node_index_t
 872 fib_table_entry_local_label_add (u32 fib_index,
 873                                  const fib_prefix_t *prefix,
 874                                  mpls_label_t label)
 875 {
 876     fib_node_index_t fib_entry_index;
 877
 878     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 879
 880     if (FIB_NODE_INDEX_INVALID == fib_entry_index ||
 881         !fib_entry_is_sourced(fib_entry_index, FIB_SOURCE_MPLS))
 882     {
 883         /*
 884          * only source the prefix once. this allows the label change
 885          * operation to work
 886          */
 887         fib_entry_index = fib_table_entry_special_dpo_add(fib_index, prefix,
 888                                                           FIB_SOURCE_MPLS,
 889                                                           FIB_ENTRY_FLAG_NONE,
 890                                                           NULL);
 891     }
 892
 893     fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &label);
 894
 895     return (fib_entry_index);
 896 }
 897
 898 void
 899 fib_table_entry_local_label_remove (u32 fib_index,
 900                                     const fib_prefix_t *prefix,
 901                                     mpls_label_t label)
 902 {
 903     fib_node_index_t fib_entry_index;
 904     const void *data;
 905     mpls_label_t pl;
 906
 907     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 908
 909     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 910         return;
 911
 912     data = fib_entry_get_source_data(fib_entry_index, FIB_SOURCE_MPLS);
 913
 914     if (NULL == data)
 915         return;
 916
 917     pl = *(mpls_label_t*)data;
 918
 919     if (pl != label)
 920         return;
 921
 922     pl = MPLS_LABEL_INVALID;
 923
 924     fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &pl);
 925     fib_table_entry_special_remove(fib_index,
 926                                    prefix,
 927                                    FIB_SOURCE_MPLS);
 928 }
 929
 930 u32
 931 fib_table_get_index_for_sw_if_index (fib_protocol_t proto,
 932                                      u32 sw_if_index)
 933 {
 934     switch (proto)
 935     {
 936     case FIB_PROTOCOL_IP4:
 937         return (ip4_fib_table_get_index_for_sw_if_index(sw_if_index));
 938     case FIB_PROTOCOL_IP6:
 939         return (ip6_fib_table_get_index_for_sw_if_index(sw_if_index));
 940     case FIB_PROTOCOL_MPLS:
 941         return (mpls_fib_table_get_index_for_sw_if_index(sw_if_index));
 942     }
 943     return (~0);
 944 }
 945
 946 flow_hash_config_t
 947 fib_table_get_flow_hash_config (u32 fib_index,
 948                                 fib_protocol_t proto)
 949 {
 950     fib_table_t *fib;
 951
 952     fib = fib_table_get(fib_index, proto);
 953
 954     return (fib->ft_flow_hash_config);
 955 }
 956 flow_hash_config_t
 957 fib_table_get_default_flow_hash_config (fib_protocol_t proto)
 958 {
 959     switch (proto)
 960     {
 961     case FIB_PROTOCOL_IP4:
 962     case FIB_PROTOCOL_IP6:
 963         return (IP_FLOW_HASH_DEFAULT);
 964
 965     case FIB_PROTOCOL_MPLS:
 966         return (MPLS_FLOW_HASH_DEFAULT);
 967     }
 968
 969     ASSERT(0);
 970     return (IP_FLOW_HASH_DEFAULT);
 971 }
 972
 973 /**
 974  * @brief Table set flow hash config context.
 975  */
 976 typedef struct fib_table_set_flow_hash_config_ctx_t_
 977 {
 978     /**
 979      * the flow hash config to set
 980      */
 981     flow_hash_config_t hash_config;
 982 } fib_table_set_flow_hash_config_ctx_t;
 983
 984 static int
 985 fib_table_set_flow_hash_config_cb (fib_node_index_t fib_entry_index,
 986                                    void *arg)
 987 {
 988     fib_table_set_flow_hash_config_ctx_t *ctx = arg;
 989
 990     fib_entry_set_flow_hash_config(fib_entry_index, ctx->hash_config);
 991
 992     return (1);
 993 }
 994
 995 void
 996 fib_table_set_flow_hash_config (u32 fib_index,
 997                                 fib_protocol_t proto,
 998                                 flow_hash_config_t hash_config)
 999 {
1000     fib_table_set_flow_hash_config_ctx_t ctx = {
1001         .hash_config = hash_config,
1002     };
1003     fib_table_t *fib;
1004
1005     fib = fib_table_get(fib_index, proto);
1006     fib->ft_flow_hash_config = hash_config;
1007
1008     fib_table_walk(fib_index, proto,
1009                    fib_table_set_flow_hash_config_cb,
1010                    &ctx);
1011 }
1012
1013 u32
1014 fib_table_get_table_id_for_sw_if_index (fib_protocol_t proto,
1015                                         u32 sw_if_index)
1016 {
1017     fib_table_t *fib_table;
1018
1019     fib_table = fib_table_get(fib_table_get_index_for_sw_if_index(
1020                                   proto, sw_if_index),
1021                               proto);
1022
1023     return ((NULL != fib_table ? fib_table->ft_table_id : ~0));
1024 }
1025
1026 u32
1027 fib_table_find (fib_protocol_t proto,
1028                 u32 table_id)
1029 {
1030     switch (proto)
1031     {
1032     case FIB_PROTOCOL_IP4:
1033         return (ip4_fib_index_from_table_id(table_id));
1034     case FIB_PROTOCOL_IP6:
1035         return (ip6_fib_index_from_table_id(table_id));
1036     case FIB_PROTOCOL_MPLS:
1037         return (mpls_fib_index_from_table_id(table_id));
1038     }
1039     return (~0);
1040 }
1041
1042 static u32
1043 fib_table_find_or_create_and_lock_i (fib_protocol_t proto,
1044                                      u32 table_id,
1045                                      fib_source_t src,
1046                                      const u8 *name)
1047 {
1048     fib_table_t *fib_table;
1049     fib_node_index_t fi;
1050
1051     switch (proto)
1052     {
1053     case FIB_PROTOCOL_IP4:
1054         fi = ip4_fib_table_find_or_create_and_lock(table_id, src);
1055         break;
1056     case FIB_PROTOCOL_IP6:
1057         fi = ip6_fib_table_find_or_create_and_lock(table_id, src);
1058         break;
1059     case FIB_PROTOCOL_MPLS:
1060         fi = mpls_fib_table_find_or_create_and_lock(table_id, src);
1061         break;
1062     default:
1063         return (~0);
1064     }
1065
1066     fib_table = fib_table_get(fi, proto);
1067
1068     if (NULL == fib_table->ft_desc)
1069     {
1070         if (name && name[0])
1071         {
1072             fib_table->ft_desc = format(NULL, "%s", name);
1073         }
1074         else
1075         {
1076             fib_table->ft_desc = format(NULL, "%U-VRF:%d",
1077                                         format_fib_protocol, proto,
1078                                         table_id);
1079         }
1080     }
1081
1082     return (fi);
1083 }
1084
1085 u32
1086 fib_table_find_or_create_and_lock (fib_protocol_t proto,
1087                                    u32 table_id,
1088                                    fib_source_t src)
1089 {
1090     return (fib_table_find_or_create_and_lock_i(proto, table_id,
1091                                                 src, NULL));
1092 }
1093
1094 u32
1095 fib_table_find_or_create_and_lock_w_name (fib_protocol_t proto,
1096                                           u32 table_id,
1097                                           fib_source_t src,
1098                                           const u8 *name)
1099 {
1100     return (fib_table_find_or_create_and_lock_i(proto, table_id,
1101                                                 src, name));
1102 }
1103
1104 u32
1105 fib_table_create_and_lock (fib_protocol_t proto,
1106                            fib_source_t src,
1107                            const char *const fmt,
1108                            ...)
1109 {
1110     fib_table_t *fib_table;
1111     fib_node_index_t fi;
1112     va_list ap;
1113
1114     va_start(ap, fmt);
1115
1116     switch (proto)
1117     {
1118     case FIB_PROTOCOL_IP4:
1119         fi = ip4_fib_table_create_and_lock(src);
1120         break;
1121     case FIB_PROTOCOL_IP6:
1122         fi = ip6_fib_table_create_and_lock(src);
1123         break;
1124      case FIB_PROTOCOL_MPLS:
1125         fi = mpls_fib_table_create_and_lock(src);
1126         break;
1127    default:
1128         return (~0);
1129     }
1130
1131     fib_table = fib_table_get(fi, proto);
1132
1133     fib_table->ft_desc = va_format(fib_table->ft_desc, fmt, &ap);
1134
1135     va_end(ap);
1136     return (fi);
1137 }
1138
1139 static void
1140 fib_table_destroy (fib_table_t *fib_table)
1141 {
1142     vec_free(fib_table->ft_desc);
1143
1144     switch (fib_table->ft_proto)
1145     {
1146     case FIB_PROTOCOL_IP4:
1147         ip4_fib_table_destroy(fib_table->ft_index);
1148         break;
1149     case FIB_PROTOCOL_IP6:
1150         ip6_fib_table_destroy(fib_table->ft_index);
1151         break;
1152     case FIB_PROTOCOL_MPLS:
1153         mpls_fib_table_destroy(fib_table->ft_index);
1154         break;
1155     }
1156 }
1157
1158 void
1159 fib_table_walk (u32 fib_index,
1160                 fib_protocol_t proto,
1161                 fib_table_walk_fn_t fn,
1162                 void *ctx)
1163 {
1164     switch (proto)
1165     {
1166     case FIB_PROTOCOL_IP4:
1167         ip4_fib_table_walk(ip4_fib_get(fib_index), fn, ctx);
1168         break;
1169     case FIB_PROTOCOL_IP6:
1170         ip6_fib_table_walk(fib_index, fn, ctx);
1171         break;
1172     case FIB_PROTOCOL_MPLS:
1173         mpls_fib_table_walk(mpls_fib_get(fib_index), fn, ctx);
1174         break;
1175     }
1176 }
1177
1178 void
1179 fib_table_unlock (u32 fib_index,
1180                   fib_protocol_t proto,
1181                   fib_source_t source)
1182 {
1183     fib_table_t *fib_table;
1184
1185     fib_table = fib_table_get(fib_index, proto);
1186     fib_table->ft_locks[source]--;
1187     fib_table->ft_locks[FIB_TABLE_TOTAL_LOCKS]--;
1188
1189     if (0 == fib_table->ft_locks[source])
1190     {
1191         /*
1192          * The source no longer needs the table. flush any routes
1193          * from it just in case
1194          */
1195         fib_table_flush(fib_index, proto, source);
1196     }
1197
1198     if (0 == fib_table->ft_locks[FIB_TABLE_TOTAL_LOCKS])
1199     {
1200         /*
1201          * no more locak from any source - kill it
1202          */
1203         fib_table_destroy(fib_table);
1204     }
1205 }
1206
1207 void
1208 fib_table_lock (u32 fib_index,
1209                 fib_protocol_t proto,
1210                 fib_source_t source)
1211 {
1212     fib_table_t *fib_table;
1213
1214     fib_table = fib_table_get(fib_index, proto);
1215     fib_table->ft_locks[source]++;
1216     fib_table->ft_locks[FIB_TABLE_TOTAL_LOCKS]++;
1217 }
1218
1219 u32
1220 fib_table_get_num_entries (u32 fib_index,
1221                            fib_protocol_t proto,
1222                            fib_source_t source)
1223 {
1224     fib_table_t *fib_table;
1225
1226     fib_table = fib_table_get(fib_index, proto);
1227
1228     return (fib_table->ft_src_route_counts[source]);
1229 }
1230
1231 u8*
1232 format_fib_table_name (u8* s, va_list* ap)
1233 {
1234     fib_node_index_t fib_index = va_arg(*ap, fib_node_index_t);
1235     fib_protocol_t proto = va_arg(*ap, int); // int promotion
1236     fib_table_t *fib_table;
1237
1238     fib_table = fib_table_get(fib_index, proto);
1239
1240     s = format(s, "%v", fib_table->ft_desc);
1241
1242     return (s);
1243 }
1244
1245 /**
1246  * @brief Table flush context. Store the indicies of matching FIB entries
1247  * that need to be removed.
1248  */
1249 typedef struct fib_table_flush_ctx_t_
1250 {
1251     /**
1252      * The list of entries to flush
1253      */
1254     fib_node_index_t *ftf_entries;
1255
1256     /**
1257      * The source we are flushing
1258      */
1259     fib_source_t ftf_source;
1260 } fib_table_flush_ctx_t;
1261
1262 static int
1263 fib_table_flush_cb (fib_node_index_t fib_entry_index,
1264                     void *arg)
1265 {
1266     fib_table_flush_ctx_t *ctx = arg;
1267
1268     if (fib_entry_is_sourced(fib_entry_index, ctx->ftf_source))
1269     {
1270         vec_add1(ctx->ftf_entries, fib_entry_index);
1271     }
1272     return (1);
1273 }
1274
1275
1276 void
1277 fib_table_flush (u32 fib_index,
1278                  fib_protocol_t proto,
1279                  fib_source_t source)
1280 {
1281     fib_node_index_t *fib_entry_index;
1282     fib_table_flush_ctx_t ctx = {
1283         .ftf_entries = NULL,
1284         .ftf_source = source,
1285     };
1286
1287     fib_table_walk(fib_index, proto,
1288                    fib_table_flush_cb,
1289                    &ctx);
1290
1291     vec_foreach(fib_entry_index, ctx.ftf_entries)
1292     {
1293         fib_table_entry_delete_index(*fib_entry_index, source);
1294     }
1295
1296     vec_free(ctx.ftf_entries);
1297 }