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  the covering entry
 185      */
 186     fib_entry_cover_index = fib_table_get_less_specific_i(fib_table, prefix);
 187     /*
 188      * the indicies are the same when the default route is first added
 189      */
 190     if (fib_entry_cover_index != fib_entry_index)
 191     {
 192         /*
 193          * push any inherting sources from the cover onto the covered
 194          */
 195         fib_entry_inherit(fib_entry_cover_index,
 196                           fib_entry_index);
 197
 198         /*
 199          * inform the covering entry that a new more specific
 200          * has been inserted beneath it.
 201          * If the prefix that has been inserted is a host route
 202          * then it is not possible that it will be the cover for any
 203          * other entry, so we can elide the walk. This is particularly
 204          * beneficial since there are often many host entries sharing the
 205          * same cover (i.e. ADJ or RR sourced entries).
 206          */
 207         if (!fib_entry_is_host(fib_entry_index))
 208         {
 209             fib_entry_cover_change_notify(fib_entry_cover_index,
 210                                           fib_entry_index);
 211         }
 212     }
 213 }
 214
 215 static void
 216 fib_table_entry_insert (fib_table_t *fib_table,
 217                         const fib_prefix_t *prefix,
 218                         fib_node_index_t fib_entry_index)
 219 {
 220     vlib_smp_unsafe_warning();
 221
 222     fib_entry_lock(fib_entry_index);
 223     fib_table->ft_total_route_counts++;
 224
 225     switch (prefix->fp_proto)
 226     {
 227     case FIB_PROTOCOL_IP4:
 228         ip4_fib_table_entry_insert(ip4_fib_get(fib_table->ft_index),
 229                                    &prefix->fp_addr.ip4,
 230                                    prefix->fp_len,
 231                                    fib_entry_index);
 232         break;
 233     case FIB_PROTOCOL_IP6:
 234         ip6_fib_table_entry_insert(fib_table->ft_index,
 235                                    &prefix->fp_addr.ip6,
 236                                    prefix->fp_len,
 237                                    fib_entry_index);
 238         break;
 239     case FIB_PROTOCOL_MPLS:
 240         mpls_fib_table_entry_insert(mpls_fib_get(fib_table->ft_index),
 241                                     prefix->fp_label,
 242                                     prefix->fp_eos,
 243                                     fib_entry_index);
 244         break;
 245     }
 246
 247     fib_table_post_insert_actions(fib_table, prefix, fib_entry_index);
 248 }
 249
 250 void
 251 fib_table_fwding_dpo_update (u32 fib_index,
 252                              const fib_prefix_t *prefix,
 253                              const dpo_id_t *dpo)
 254 {
 255     vlib_smp_unsafe_warning();
 256
 257     switch (prefix->fp_proto)
 258     {
 259     case FIB_PROTOCOL_IP4:
 260         return (ip4_fib_table_fwding_dpo_update(ip4_fib_get(fib_index),
 261                                                 &prefix->fp_addr.ip4,
 262                                                 prefix->fp_len,
 263                                                 dpo));
 264     case FIB_PROTOCOL_IP6:
 265         return (ip6_fib_table_fwding_dpo_update(fib_index,
 266                                                 &prefix->fp_addr.ip6,
 267                                                 prefix->fp_len,
 268                                                 dpo));
 269     case FIB_PROTOCOL_MPLS:
 270         return (mpls_fib_forwarding_table_update(mpls_fib_get(fib_index),
 271                                                  prefix->fp_label,
 272                                                  prefix->fp_eos,
 273                                                  dpo));
 274     }
 275 }
 276
 277 void
 278 fib_table_fwding_dpo_remove (u32 fib_index,
 279                              const fib_prefix_t *prefix,
 280                              const dpo_id_t *dpo)
 281 {
 282     vlib_smp_unsafe_warning();
 283
 284     switch (prefix->fp_proto)
 285     {
 286     case FIB_PROTOCOL_IP4:
 287         return (ip4_fib_table_fwding_dpo_remove(ip4_fib_get(fib_index),
 288                                                 &prefix->fp_addr.ip4,
 289                                                 prefix->fp_len,
 290                                                 dpo,
 291                                                 fib_table_get_less_specific(fib_index,
 292                                                                             prefix)));
 293     case FIB_PROTOCOL_IP6:
 294         return (ip6_fib_table_fwding_dpo_remove(fib_index,
 295                                                 &prefix->fp_addr.ip6,
 296                                                 prefix->fp_len,
 297                                                 dpo));
 298     case FIB_PROTOCOL_MPLS:
 299         return (mpls_fib_forwarding_table_reset(mpls_fib_get(fib_index),
 300                                                 prefix->fp_label,
 301                                                 prefix->fp_eos));
 302     }
 303 }
 304
 305
 306 fib_node_index_t
 307 fib_table_entry_special_dpo_add (u32 fib_index,
 308                                  const fib_prefix_t *prefix,
 309                                  fib_source_t source,
 310                                  fib_entry_flag_t flags,
 311                                  const dpo_id_t *dpo)
 312 {
 313     fib_node_index_t fib_entry_index;
 314     fib_table_t *fib_table;
 315
 316     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 317     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 318
 319     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 320     {
 321         fib_entry_index = fib_entry_create_special(fib_index, prefix,
 322                                                    source, flags,
 323                                                    dpo);
 324
 325         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 326         fib_table->ft_src_route_counts[source]++;
 327     }
 328     else
 329     {
 330         int was_sourced;
 331
 332         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 333         fib_entry_special_add(fib_entry_index, source, flags, dpo);
 334
 335         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 336         {
 337             fib_table->ft_src_route_counts[source]++;
 338         }
 339     }
 340
 341
 342     return (fib_entry_index);
 343 }
 344
 345 fib_node_index_t
 346 fib_table_entry_special_dpo_update (u32 fib_index,
 347                                     const fib_prefix_t *prefix,
 348                                     fib_source_t source,
 349                                     fib_entry_flag_t flags,
 350                                     const dpo_id_t *dpo)
 351 {
 352     fib_node_index_t fib_entry_index;
 353     fib_table_t *fib_table;
 354
 355     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 356     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 357
 358     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 359     {
 360         fib_entry_index = fib_entry_create_special(fib_index, prefix,
 361                                                    source, flags,
 362                                                    dpo);
 363
 364         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 365         fib_table->ft_src_route_counts[source]++;
 366     }
 367     else
 368     {
 369         int was_sourced;
 370
 371         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 372
 373         if (was_sourced)
 374             fib_entry_special_update(fib_entry_index, source, flags, dpo);
 375         else
 376             fib_entry_special_add(fib_entry_index, source, flags, dpo);
 377
 378         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 379         {
 380             fib_table->ft_src_route_counts[source]++;
 381         }
 382     }
 383
 384     return (fib_entry_index);
 385 }
 386
 387 fib_node_index_t
 388 fib_table_entry_special_add (u32 fib_index,
 389                              const fib_prefix_t *prefix,
 390                              fib_source_t source,
 391                              fib_entry_flag_t flags)
 392 {
 393     fib_node_index_t fib_entry_index;
 394     dpo_id_t tmp_dpo = DPO_INVALID;
 395
 396     dpo_copy(&tmp_dpo, drop_dpo_get(fib_proto_to_dpo(prefix->fp_proto)));
 397
 398     fib_entry_index = fib_table_entry_special_dpo_add(fib_index, prefix, source,
 399                                                       flags, &tmp_dpo);
 400
 401     dpo_unlock(&tmp_dpo);
 402
 403     return (fib_entry_index);
 404 }
 405
 406 void
 407 fib_table_entry_special_remove (u32 fib_index,
 408                                 const fib_prefix_t *prefix,
 409                                 fib_source_t source)
 410 {
 411     /*
 412      * 1 is it present
 413      *   yes => remove source
 414      *    2 - is it still sourced?
 415      *      no => cover walk
 416      */
 417     fib_node_index_t fib_entry_index;
 418     fib_table_t *fib_table;
 419
 420     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 421     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 422
 423     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 424     {
 425         /*
 426          * removing an etry that does not exist. i'll allow it.
 427          */
 428     }
 429     else
 430     {
 431         fib_entry_src_flag_t src_flag;
 432         int was_sourced;
 433
 434         /*
 435          * don't nobody go nowhere
 436          */
 437         fib_entry_lock(fib_entry_index);
 438         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 439
 440         src_flag = fib_entry_special_remove(fib_entry_index, source);
 441
 442         if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 443         {
 444             /*
 445              * last source gone. remove from the table
 446              */
 447             fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 448
 449             /*
 450              * now the entry is no longer in the table, we can
 451              * inform the entries that it covers to re-calculate their cover
 452              */
 453             fib_entry_cover_change_notify(fib_entry_index,
 454                                           FIB_NODE_INDEX_INVALID);
 455         }
 456         /*
 457          * else
 458          *   still has sources, leave it be.
 459          */
 460         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 461         {
 462             fib_table->ft_src_route_counts[source]--;
 463         }
 464
 465         fib_entry_unlock(fib_entry_index);
 466     }
 467 }
 468
 469 /**
 470  * fib_table_route_path_fixup
 471  *
 472  * Convert attached hosts to attached next-hops.
 473  *
 474  * This special case is required because an attached path will link to a
 475  * glean, and the FIB entry will have the interface or API/CLI source. When
 476  * the ARP/ND process is completes then that source (which will provide a
 477  * complete adjacency) will be lower priority and so the FIB entry will
 478  * remain linked to a glean and traffic will never reach the hosts. For
 479  * an ATTAHCED_HOST path we can link the path directly to the [incomplete]
 480  * adjacency.
 481  */
 482 static void
 483 fib_table_route_path_fixup (const fib_prefix_t *prefix,
 484                             fib_entry_flag_t *eflags,
 485                             fib_route_path_t *path)
 486 {
 487     /*
 488      * not all zeros next hop &&
 489      * is recursive path &&
 490      * nexthop is same as the route's address
 491      */
 492     if ((!ip46_address_is_zero(&path->frp_addr)) &&
 493         (~0 == path->frp_sw_if_index) &&
 494         (0 == ip46_address_cmp(&path->frp_addr, &prefix->fp_addr)))
 495     {
 496         /* Prefix recurses via itse;f */
 497         path->frp_flags |= FIB_ROUTE_PATH_DROP;
 498     }
 499     if (!(path->frp_flags & FIB_ROUTE_PATH_LOCAL) &&
 500         fib_prefix_is_host(prefix) &&
 501         ip46_address_is_zero(&path->frp_addr) &&
 502         path->frp_sw_if_index != ~0 &&
 503         path->frp_proto != DPO_PROTO_ETHERNET)
 504     {
 505         path->frp_addr = prefix->fp_addr;
 506         path->frp_flags |= FIB_ROUTE_PATH_ATTACHED;
 507     }
 508     if (*eflags & FIB_ENTRY_FLAG_DROP)
 509     {
 510         path->frp_flags |= FIB_ROUTE_PATH_DROP;
 511     }
 512     if (*eflags & FIB_ENTRY_FLAG_LOCAL)
 513     {
 514         path->frp_flags |= FIB_ROUTE_PATH_LOCAL;
 515     }
 516     if (*eflags & FIB_ENTRY_FLAG_EXCLUSIVE)
 517     {
 518         path->frp_flags |= FIB_ROUTE_PATH_EXCLUSIVE;
 519     }
 520     if (path->frp_flags & FIB_ROUTE_PATH_LOCAL)
 521     {
 522         *eflags |= FIB_ENTRY_FLAG_LOCAL;
 523
 524         if (path->frp_sw_if_index != ~0)
 525         {
 526             *eflags |= FIB_ENTRY_FLAG_CONNECTED;
 527         }
 528     }
 529 }
 530
 531 fib_node_index_t
 532 fib_table_entry_path_add (u32 fib_index,
 533                           const fib_prefix_t *prefix,
 534                           fib_source_t source,
 535                           fib_entry_flag_t flags,
 536                           dpo_proto_t next_hop_proto,
 537                           const ip46_address_t *next_hop,
 538                           u32 next_hop_sw_if_index,
 539                           u32 next_hop_fib_index,
 540                           u32 next_hop_weight,
 541                           fib_mpls_label_t *next_hop_labels,
 542                           fib_route_path_flags_t path_flags)
 543 {
 544     fib_route_path_t path = {
 545         .frp_proto = next_hop_proto,
 546         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 547         .frp_sw_if_index = next_hop_sw_if_index,
 548         .frp_fib_index = next_hop_fib_index,
 549         .frp_weight = next_hop_weight,
 550         .frp_flags = path_flags,
 551         .frp_rpf_id = INDEX_INVALID,
 552         .frp_label_stack = next_hop_labels,
 553     };
 554     fib_node_index_t fib_entry_index;
 555     fib_route_path_t *paths = NULL;
 556
 557     vec_add1(paths, path);
 558
 559     fib_entry_index = fib_table_entry_path_add2(fib_index, prefix,
 560                                                 source, flags, paths);
 561
 562     vec_free(paths);
 563     return (fib_entry_index);
 564 }
 565
 566 fib_node_index_t
 567 fib_table_entry_path_add2 (u32 fib_index,
 568                            const fib_prefix_t *prefix,
 569                            fib_source_t source,
 570                            fib_entry_flag_t flags,
 571                            fib_route_path_t *rpaths)
 572 {
 573     fib_node_index_t fib_entry_index;
 574     fib_table_t *fib_table;
 575     u32 ii;
 576
 577     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 578     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 579
 580     for (ii = 0; ii < vec_len(rpaths); ii++)
 581     {
 582         fib_table_route_path_fixup(prefix, &flags, &rpaths[ii]);
 583     }
 584
 585     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 586     {
 587         fib_entry_index = fib_entry_create(fib_index, prefix,
 588                                            source, flags,
 589                                            rpaths);
 590
 591         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 592         fib_table->ft_src_route_counts[source]++;
 593     }
 594     else
 595     {
 596         int was_sourced;
 597
 598         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 599         fib_entry_path_add(fib_entry_index, source, flags, rpaths);;
 600
 601         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 602         {
 603             fib_table->ft_src_route_counts[source]++;
 604         }
 605     }
 606
 607     return (fib_entry_index);
 608 }
 609
 610 void
 611 fib_table_entry_path_remove2 (u32 fib_index,
 612                               const fib_prefix_t *prefix,
 613                               fib_source_t source,
 614                               fib_route_path_t *rpaths)
 615 {
 616     /*
 617      * 1 is it present
 618      *   yes => remove source
 619      *    2 - is it still sourced?
 620      *      no => cover walk
 621      */
 622     fib_node_index_t fib_entry_index;
 623     fib_route_path_t *rpath;
 624     fib_table_t *fib_table;
 625
 626     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 627     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 628
 629     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 630     {
 631         /*
 632          * removing an etry that does not exist. i'll allow it.
 633          */
 634     }
 635     else
 636     {
 637         fib_entry_src_flag_t src_flag;
 638         int was_sourced;
 639
 640         /*
 641          * if it's not sourced, then there's nowt to remove
 642          */
 643         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 644         if (!was_sourced)
 645         {
 646             return;
 647         }
 648
 649         /*
 650          * don't nobody go nowhere
 651          */
 652         fib_entry_lock(fib_entry_index);
 653
 654         vec_foreach(rpath, rpaths)
 655         {
 656             fib_entry_flag_t eflags;
 657
 658             eflags = fib_entry_get_flags_for_source(fib_entry_index,
 659                                                     source);
 660             fib_table_route_path_fixup(prefix, &eflags, rpath);
 661         }
 662
 663         src_flag = fib_entry_path_remove(fib_entry_index, source, rpaths);
 664
 665         if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 666         {
 667             /*
 668              * last source gone. remove from the table
 669              */
 670             fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 671
 672             /*
 673              * now the entry is no longer in the table, we can
 674              * inform the entries that it covers to re-calculate their cover
 675              */
 676             fib_entry_cover_change_notify(fib_entry_index,
 677                                           FIB_NODE_INDEX_INVALID);
 678         }
 679         /*
 680          * else
 681          *   still has sources, leave it be.
 682          */
 683         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 684         {
 685             fib_table->ft_src_route_counts[source]--;
 686         }
 687
 688         fib_entry_unlock(fib_entry_index);
 689     }
 690 }
 691
 692 void
 693 fib_table_entry_path_remove (u32 fib_index,
 694                              const fib_prefix_t *prefix,
 695                              fib_source_t source,
 696                              dpo_proto_t next_hop_proto,
 697                              const ip46_address_t *next_hop,
 698                              u32 next_hop_sw_if_index,
 699                              u32 next_hop_fib_index,
 700                              u32 next_hop_weight,
 701                              fib_route_path_flags_t path_flags)
 702 {
 703     /*
 704      * 1 is it present
 705      *   yes => remove source
 706      *    2 - is it still sourced?
 707      *      no => cover walk
 708      */
 709     fib_route_path_t path = {
 710         .frp_proto = next_hop_proto,
 711         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 712         .frp_sw_if_index = next_hop_sw_if_index,
 713         .frp_fib_index = next_hop_fib_index,
 714         .frp_weight = next_hop_weight,
 715         .frp_flags = path_flags,
 716     };
 717     fib_route_path_t *paths = NULL;
 718
 719     vec_add1(paths, path);
 720
 721     fib_table_entry_path_remove2(fib_index, prefix, source, paths);
 722
 723     vec_free(paths);
 724 }
 725
 726 static int
 727 fib_route_path_cmp_for_sort (void * v1,
 728                              void * v2)
 729 {
 730     return (fib_route_path_cmp(v1, v2));
 731 }
 732
 733 fib_node_index_t
 734 fib_table_entry_update (u32 fib_index,
 735                         const fib_prefix_t *prefix,
 736                         fib_source_t source,
 737                         fib_entry_flag_t flags,
 738                         fib_route_path_t *paths)
 739 {
 740     fib_node_index_t fib_entry_index;
 741     fib_table_t *fib_table;
 742     u32 ii;
 743
 744     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 745     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 746
 747     for (ii = 0; ii < vec_len(paths); ii++)
 748     {
 749         fib_table_route_path_fixup(prefix, &flags, &paths[ii]);
 750     }
 751     /*
 752      * sort the paths provided by the control plane. this means
 753      * the paths and the extension on the entry will be sorted.
 754      */
 755     vec_sort_with_function(paths, fib_route_path_cmp_for_sort);
 756
 757     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 758     {
 759         fib_entry_index = fib_entry_create(fib_index, prefix,
 760                                            source, flags,
 761                                            paths);
 762
 763         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 764         fib_table->ft_src_route_counts[source]++;
 765     }
 766     else
 767     {
 768         int was_sourced;
 769
 770         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 771         fib_entry_update(fib_entry_index, source, flags, paths);
 772
 773         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 774         {
 775             fib_table->ft_src_route_counts[source]++;
 776         }
 777     }
 778
 779     return (fib_entry_index);
 780 }
 781
 782 fib_node_index_t
 783 fib_table_entry_update_one_path (u32 fib_index,
 784                                  const fib_prefix_t *prefix,
 785                                  fib_source_t source,
 786                                  fib_entry_flag_t flags,
 787                                  dpo_proto_t next_hop_proto,
 788                                  const ip46_address_t *next_hop,
 789                                  u32 next_hop_sw_if_index,
 790                                  u32 next_hop_fib_index,
 791                                  u32 next_hop_weight,
 792                                  fib_mpls_label_t *next_hop_labels,
 793                                  fib_route_path_flags_t path_flags)
 794 {
 795     fib_node_index_t fib_entry_index;
 796     fib_route_path_t path = {
 797         .frp_proto = next_hop_proto,
 798         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 799         .frp_sw_if_index = next_hop_sw_if_index,
 800         .frp_fib_index = next_hop_fib_index,
 801         .frp_weight = next_hop_weight,
 802         .frp_flags = path_flags,
 803         .frp_label_stack = next_hop_labels,
 804     };
 805     fib_route_path_t *paths = NULL;
 806
 807     vec_add1(paths, path);
 808
 809     fib_entry_index =
 810         fib_table_entry_update(fib_index, prefix, source, flags, paths);
 811
 812     vec_free(paths);
 813
 814     return (fib_entry_index);
 815 }
 816
 817 static void
 818 fib_table_entry_delete_i (u32 fib_index,
 819                           fib_node_index_t fib_entry_index,
 820                           const fib_prefix_t *prefix,
 821                           fib_source_t source)
 822 {
 823     fib_entry_src_flag_t src_flag;
 824     fib_table_t *fib_table;
 825     int was_sourced;
 826
 827     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 828     was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 829
 830     /*
 831      * don't nobody go nowhere
 832      */
 833     fib_entry_lock(fib_entry_index);
 834
 835     src_flag = fib_entry_delete(fib_entry_index, source);
 836
 837     if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 838     {
 839         /*
 840          * last source gone. remove from the table
 841          */
 842         fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 843
 844         /*
 845          * now the entry is no longer in the table, we can
 846          * inform the entries that it covers to re-calculate their cover
 847          */
 848         fib_entry_cover_change_notify(fib_entry_index,
 849                                       FIB_NODE_INDEX_INVALID);
 850     }
 851     /*
 852      * else
 853      *   still has sources, leave it be.
 854      */
 855     if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 856     {
 857         fib_table->ft_src_route_counts[source]--;
 858     }
 859
 860     fib_entry_unlock(fib_entry_index);
 861 }
 862
 863 void
 864 fib_table_entry_delete (u32 fib_index,
 865                         const fib_prefix_t *prefix,
 866                         fib_source_t source)
 867 {
 868     fib_node_index_t fib_entry_index;
 869
 870     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 871
 872     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 873     {
 874         /*
 875          * removing an etry that does not exist.
 876          * i'll allow it, but i won't like it.
 877          */
 878         if (0)
 879             clib_warning("%U not in FIB", format_fib_prefix, prefix);
 880     }
 881     else
 882     {
 883         fib_table_entry_delete_i(fib_index, fib_entry_index, prefix, source);
 884     }
 885 }
 886
 887 void
 888 fib_table_entry_delete_index (fib_node_index_t fib_entry_index,
 889                               fib_source_t source)
 890 {
 891     const fib_prefix_t *prefix;
 892
 893     prefix = fib_entry_get_prefix(fib_entry_index);
 894
 895     fib_table_entry_delete_i(fib_entry_get_fib_index(fib_entry_index),
 896                              fib_entry_index, prefix, source);
 897 }
 898
 899 u32
 900 fib_table_entry_get_stats_index (u32 fib_index,
 901                                  const fib_prefix_t *prefix)
 902 {
 903     return (fib_entry_get_stats_index(
 904                 fib_table_lookup_exact_match(fib_index, prefix)));
 905 }
 906
 907 fib_node_index_t
 908 fib_table_entry_local_label_add (u32 fib_index,
 909                                  const fib_prefix_t *prefix,
 910                                  mpls_label_t label)
 911 {
 912     fib_node_index_t fib_entry_index;
 913
 914     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 915
 916     if (FIB_NODE_INDEX_INVALID == fib_entry_index ||
 917         !fib_entry_is_sourced(fib_entry_index, FIB_SOURCE_MPLS))
 918     {
 919         /*
 920          * only source the prefix once. this allows the label change
 921          * operation to work
 922          */
 923         fib_entry_index = fib_table_entry_special_dpo_add(fib_index, prefix,
 924                                                           FIB_SOURCE_MPLS,
 925                                                           FIB_ENTRY_FLAG_NONE,
 926                                                           NULL);
 927     }
 928
 929     fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &label);
 930
 931     return (fib_entry_index);
 932 }
 933
 934 void
 935 fib_table_entry_local_label_remove (u32 fib_index,
 936                                     const fib_prefix_t *prefix,
 937                                     mpls_label_t label)
 938 {
 939     fib_node_index_t fib_entry_index;
 940     const void *data;
 941     mpls_label_t pl;
 942
 943     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 944
 945     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 946         return;
 947
 948     data = fib_entry_get_source_data(fib_entry_index, FIB_SOURCE_MPLS);
 949
 950     if (NULL == data)
 951         return;
 952
 953     pl = *(mpls_label_t*)data;
 954
 955     if (pl != label)
 956         return;
 957
 958     pl = MPLS_LABEL_INVALID;
 959
 960     fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &pl);
 961     fib_table_entry_special_remove(fib_index,
 962                                    prefix,
 963                                    FIB_SOURCE_MPLS);
 964 }
 965
 966 u32
 967 fib_table_get_index_for_sw_if_index (fib_protocol_t proto,
 968                                      u32 sw_if_index)
 969 {
 970     switch (proto)
 971     {
 972     case FIB_PROTOCOL_IP4:
 973         return (ip4_fib_table_get_index_for_sw_if_index(sw_if_index));
 974     case FIB_PROTOCOL_IP6:
 975         return (ip6_fib_table_get_index_for_sw_if_index(sw_if_index));
 976     case FIB_PROTOCOL_MPLS:
 977         return (mpls_fib_table_get_index_for_sw_if_index(sw_if_index));
 978     }
 979     return (~0);
 980 }
 981
 982 flow_hash_config_t
 983 fib_table_get_flow_hash_config (u32 fib_index,
 984                                 fib_protocol_t proto)
 985 {
 986     fib_table_t *fib;
 987
 988     fib = fib_table_get(fib_index, proto);
 989
 990     return (fib->ft_flow_hash_config);
 991 }
 992
 993 flow_hash_config_t
 994 fib_table_get_default_flow_hash_config (fib_protocol_t proto)
 995 {
 996     switch (proto)
 997     {
 998     case FIB_PROTOCOL_IP4:
 999     case FIB_PROTOCOL_IP6:
1000         return (IP_FLOW_HASH_DEFAULT);
1001
1002     case FIB_PROTOCOL_MPLS:
1003         return (MPLS_FLOW_HASH_DEFAULT);
1004     }
1005
1006     ASSERT(0);
1007     return (IP_FLOW_HASH_DEFAULT);
1008 }
1009
1010 /**
1011  * @brief Table set flow hash config context.
1012  */
1013 typedef struct fib_table_set_flow_hash_config_ctx_t_
1014 {
1015     /**
1016      * the flow hash config to set
1017      */
1018     flow_hash_config_t hash_config;
1019 } fib_table_set_flow_hash_config_ctx_t;
1020
1021 static fib_table_walk_rc_t
1022 fib_table_set_flow_hash_config_cb (fib_node_index_t fib_entry_index,
1023                                    void *arg)
1024 {
1025     fib_table_set_flow_hash_config_ctx_t *ctx = arg;
1026
1027     fib_entry_set_flow_hash_config(fib_entry_index, ctx->hash_config);
1028
1029     return (FIB_TABLE_WALK_CONTINUE);
1030 }
1031
1032 void
1033 fib_table_set_flow_hash_config (u32 fib_index,
1034                                 fib_protocol_t proto,
1035                                 flow_hash_config_t hash_config)
1036 {
1037     fib_table_set_flow_hash_config_ctx_t ctx = {
1038         .hash_config = hash_config,
1039     };
1040     fib_table_t *fib;
1041
1042     fib = fib_table_get(fib_index, proto);
1043     fib->ft_flow_hash_config = hash_config;
1044
1045     fib_table_walk(fib_index, proto,
1046                    fib_table_set_flow_hash_config_cb,
1047                    &ctx);
1048 }
1049
1050 u32
1051 fib_table_get_table_id_for_sw_if_index (fib_protocol_t proto,
1052                                         u32 sw_if_index)
1053 {
1054     fib_table_t *fib_table;
1055
1056     fib_table = fib_table_get(fib_table_get_index_for_sw_if_index(
1057                                   proto, sw_if_index),
1058                               proto);
1059
1060     return ((NULL != fib_table ? fib_table->ft_table_id : ~0));
1061 }
1062
1063 u32
1064 fib_table_get_table_id (u32 fib_index,
1065                         fib_protocol_t proto)
1066 {
1067     fib_table_t *fib_table;
1068
1069     fib_table = fib_table_get(fib_index, proto);
1070
1071     return ((NULL != fib_table ? fib_table->ft_table_id : ~0));
1072 }
1073
1074 u32
1075 fib_table_find (fib_protocol_t proto,
1076                 u32 table_id)
1077 {
1078     switch (proto)
1079     {
1080     case FIB_PROTOCOL_IP4:
1081         return (ip4_fib_index_from_table_id(table_id));
1082     case FIB_PROTOCOL_IP6:
1083         return (ip6_fib_index_from_table_id(table_id));
1084     case FIB_PROTOCOL_MPLS:
1085         return (mpls_fib_index_from_table_id(table_id));
1086     }
1087     return (~0);
1088 }
1089
1090 static u32
1091 fib_table_find_or_create_and_lock_i (fib_protocol_t proto,
1092                                      u32 table_id,
1093                                      fib_source_t src,
1094                                      const u8 *name)
1095 {
1096     fib_table_t *fib_table;
1097     fib_node_index_t fi;
1098
1099     switch (proto)
1100     {
1101     case FIB_PROTOCOL_IP4:
1102         fi = ip4_fib_table_find_or_create_and_lock(table_id, src);
1103         break;
1104     case FIB_PROTOCOL_IP6:
1105         fi = ip6_fib_table_find_or_create_and_lock(table_id, src);
1106         break;
1107     case FIB_PROTOCOL_MPLS:
1108         fi = mpls_fib_table_find_or_create_and_lock(table_id, src);
1109         break;
1110     default:
1111         return (~0);
1112     }
1113
1114     fib_table = fib_table_get(fi, proto);
1115
1116     if (NULL == fib_table->ft_desc)
1117     {
1118         if (name && name[0])
1119         {
1120             fib_table->ft_desc = format(NULL, "%s", name);
1121         }
1122         else
1123         {
1124             fib_table->ft_desc = format(NULL, "%U-VRF:%d",
1125                                         format_fib_protocol, proto,
1126                                         table_id);
1127         }
1128     }
1129
1130     return (fi);
1131 }
1132
1133 u32
1134 fib_table_find_or_create_and_lock (fib_protocol_t proto,
1135                                    u32 table_id,
1136                                    fib_source_t src)
1137 {
1138     return (fib_table_find_or_create_and_lock_i(proto, table_id,
1139                                                 src, NULL));
1140 }
1141
1142 u32
1143 fib_table_find_or_create_and_lock_w_name (fib_protocol_t proto,
1144                                           u32 table_id,
1145                                           fib_source_t src,
1146                                           const u8 *name)
1147 {
1148     return (fib_table_find_or_create_and_lock_i(proto, table_id,
1149                                                 src, name));
1150 }
1151
1152 u32
1153 fib_table_create_and_lock (fib_protocol_t proto,
1154                            fib_source_t src,
1155                            const char *const fmt,
1156                            ...)
1157 {
1158     fib_table_t *fib_table;
1159     fib_node_index_t fi;
1160     va_list ap;
1161
1162
1163     switch (proto)
1164     {
1165     case FIB_PROTOCOL_IP4:
1166         fi = ip4_fib_table_create_and_lock(src);
1167         break;
1168     case FIB_PROTOCOL_IP6:
1169         fi = ip6_fib_table_create_and_lock(src, FIB_TABLE_FLAG_NONE, NULL);
1170         break;
1171      case FIB_PROTOCOL_MPLS:
1172         fi = mpls_fib_table_create_and_lock(src);
1173         break;
1174    default:
1175         return (~0);
1176     }
1177
1178     fib_table = fib_table_get(fi, proto);
1179
1180     va_start(ap, fmt);
1181
1182     fib_table->ft_desc = va_format(fib_table->ft_desc, fmt, &ap);
1183
1184     va_end(ap);
1185     return (fi);
1186 }
1187
1188 static void
1189 fib_table_destroy (fib_table_t *fib_table)
1190 {
1191     vec_free(fib_table->ft_desc);
1192
1193     switch (fib_table->ft_proto)
1194     {
1195     case FIB_PROTOCOL_IP4:
1196         ip4_fib_table_destroy(fib_table->ft_index);
1197         break;
1198     case FIB_PROTOCOL_IP6:
1199         ip6_fib_table_destroy(fib_table->ft_index);
1200         break;
1201     case FIB_PROTOCOL_MPLS:
1202         mpls_fib_table_destroy(fib_table->ft_index);
1203         break;
1204     }
1205 }
1206
1207 void
1208 fib_table_walk (u32 fib_index,
1209                 fib_protocol_t proto,
1210                 fib_table_walk_fn_t fn,
1211                 void *ctx)
1212 {
1213     switch (proto)
1214     {
1215     case FIB_PROTOCOL_IP4:
1216         ip4_fib_table_walk(ip4_fib_get(fib_index), fn, ctx);
1217         break;
1218     case FIB_PROTOCOL_IP6:
1219         ip6_fib_table_walk(fib_index, fn, ctx);
1220         break;
1221     case FIB_PROTOCOL_MPLS:
1222         mpls_fib_table_walk(mpls_fib_get(fib_index), fn, ctx);
1223         break;
1224     }
1225 }
1226
1227 void
1228 fib_table_sub_tree_walk (u32 fib_index,
1229                          fib_protocol_t proto,
1230                          const fib_prefix_t *root,
1231                          fib_table_walk_fn_t fn,
1232                          void *ctx)
1233 {
1234     switch (proto)
1235     {
1236     case FIB_PROTOCOL_IP4:
1237         ip4_fib_table_sub_tree_walk(ip4_fib_get(fib_index), root, fn, ctx);
1238         break;
1239     case FIB_PROTOCOL_IP6:
1240         ip6_fib_table_sub_tree_walk(fib_index, root, fn, ctx);
1241         break;
1242     case FIB_PROTOCOL_MPLS:
1243         break;
1244     }
1245 }
1246
1247 void
1248 fib_table_unlock (u32 fib_index,
1249                   fib_protocol_t proto,
1250                   fib_source_t source)
1251 {
1252     fib_table_t *fib_table;
1253
1254     fib_table = fib_table_get(fib_index, proto);
1255     fib_table->ft_locks[source]--;
1256     fib_table->ft_locks[FIB_TABLE_TOTAL_LOCKS]--;
1257
1258     if (0 == fib_table->ft_locks[FIB_TABLE_TOTAL_LOCKS])
1259     {
1260         /*
1261          * no more locak from any source - kill it
1262          */
1263         fib_table_destroy(fib_table);
1264     }
1265 }
1266
1267 void
1268 fib_table_lock (u32 fib_index,
1269                 fib_protocol_t proto,
1270                 fib_source_t source)
1271 {
1272     fib_table_t *fib_table;
1273
1274     fib_table = fib_table_get(fib_index, proto);
1275
1276     ASSERT(fib_table->ft_locks[source] < (0xffff - 1));
1277
1278     fib_table->ft_locks[source]++;
1279     fib_table->ft_locks[FIB_TABLE_TOTAL_LOCKS]++;
1280 }
1281
1282 u32
1283 fib_table_get_num_entries (u32 fib_index,
1284                            fib_protocol_t proto,
1285                            fib_source_t source)
1286 {
1287     fib_table_t *fib_table;
1288
1289     fib_table = fib_table_get(fib_index, proto);
1290
1291     return (fib_table->ft_src_route_counts[source]);
1292 }
1293
1294 u8*
1295 format_fib_table_name (u8* s, va_list* ap)
1296 {
1297     fib_node_index_t fib_index = va_arg(*ap, fib_node_index_t);
1298     fib_protocol_t proto = va_arg(*ap, int); // int promotion
1299     fib_table_t *fib_table;
1300
1301     fib_table = fib_table_get(fib_index, proto);
1302
1303     s = format(s, "%v", fib_table->ft_desc);
1304
1305     return (s);
1306 }
1307
1308 /**
1309  * @brief Table flush context. Store the indicies of matching FIB entries
1310  * that need to be removed.
1311  */
1312 typedef struct fib_table_flush_ctx_t_
1313 {
1314     /**
1315      * The list of entries to flush
1316      */
1317     fib_node_index_t *ftf_entries;
1318
1319     /**
1320      * The source we are flushing
1321      */
1322     fib_source_t ftf_source;
1323 } fib_table_flush_ctx_t;
1324
1325 static fib_table_walk_rc_t
1326 fib_table_flush_cb (fib_node_index_t fib_entry_index,
1327                     void *arg)
1328 {
1329     fib_table_flush_ctx_t *ctx = arg;
1330
1331     if (fib_entry_is_sourced(fib_entry_index, ctx->ftf_source))
1332     {
1333         vec_add1(ctx->ftf_entries, fib_entry_index);
1334     }
1335     return (FIB_TABLE_WALK_CONTINUE);
1336 }
1337
1338
1339 void
1340 fib_table_flush (u32 fib_index,
1341                  fib_protocol_t proto,
1342                  fib_source_t source)
1343 {
1344     fib_node_index_t *fib_entry_index;
1345     fib_table_flush_ctx_t ctx = {
1346         .ftf_entries = NULL,
1347         .ftf_source = source,
1348     };
1349
1350     fib_table_walk(fib_index, proto,
1351                    fib_table_flush_cb,
1352                    &ctx);
1353
1354     vec_foreach(fib_entry_index, ctx.ftf_entries)
1355     {
1356         fib_table_entry_delete_index(*fib_entry_index, source);
1357     }
1358
1359     vec_free(ctx.ftf_entries);
1360 }
1361
1362 u8 *
1363 format_fib_table_memory (u8 *s, va_list *args)
1364 {
1365     s = format(s, "%U", format_ip4_fib_table_memory);
1366     s = format(s, "%U", format_ip6_fib_table_memory);
1367     s = format(s, "%U", format_mpls_fib_table_memory);
1368
1369     return (s);
1370 }