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 const static char * fib_table_flags_strings[] = FIB_TABLE_ATTRIBUTES;
  27
  28 fib_table_t *
  29 fib_table_get (fib_node_index_t index,
  30                fib_protocol_t proto)
  31 {
  32     switch (proto)
  33     {
  34     case FIB_PROTOCOL_IP4:
  35         return (pool_elt_at_index(ip4_main.fibs, index));
  36     case FIB_PROTOCOL_IP6:
  37         return (pool_elt_at_index(ip6_main.fibs, index));
  38     case FIB_PROTOCOL_MPLS:
  39         return (pool_elt_at_index(mpls_main.fibs, index));
  40     }
  41     ASSERT(0);
  42     return (NULL);
  43 }
  44
  45 static inline fib_node_index_t
  46 fib_table_lookup_i (fib_table_t *fib_table,
  47                     const fib_prefix_t *prefix)
  48 {
  49     switch (prefix->fp_proto)
  50     {
  51     case FIB_PROTOCOL_IP4:
  52         return (ip4_fib_table_lookup(ip4_fib_get(fib_table->ft_index),
  53                                      &prefix->fp_addr.ip4,
  54                                      prefix->fp_len));
  55     case FIB_PROTOCOL_IP6:
  56         return (ip6_fib_table_lookup(fib_table->ft_index,
  57                                      &prefix->fp_addr.ip6,
  58                                      prefix->fp_len));
  59     case FIB_PROTOCOL_MPLS:
  60         return (mpls_fib_table_lookup(mpls_fib_get(fib_table->ft_index),
  61                                       prefix->fp_label,
  62                                       prefix->fp_eos));
  63     }
  64     return (FIB_NODE_INDEX_INVALID);
  65 }
  66
  67 fib_node_index_t
  68 fib_table_lookup (u32 fib_index,
  69                   const fib_prefix_t *prefix)
  70 {
  71     return (fib_table_lookup_i(fib_table_get(fib_index, prefix->fp_proto), prefix));
  72 }
  73
  74 static inline fib_node_index_t
  75 fib_table_lookup_exact_match_i (const fib_table_t *fib_table,
  76                                 const fib_prefix_t *prefix)
  77 {
  78     switch (prefix->fp_proto)
  79     {
  80     case FIB_PROTOCOL_IP4:
  81         return (ip4_fib_table_lookup_exact_match(ip4_fib_get(fib_table->ft_index),
  82                                                  &prefix->fp_addr.ip4,
  83                                                  prefix->fp_len));
  84     case FIB_PROTOCOL_IP6:
  85         return (ip6_fib_table_lookup_exact_match(fib_table->ft_index,
  86                                                  &prefix->fp_addr.ip6,
  87                                                  prefix->fp_len));
  88     case FIB_PROTOCOL_MPLS:
  89         return (mpls_fib_table_lookup(mpls_fib_get(fib_table->ft_index),
  90                                       prefix->fp_label,
  91                                       prefix->fp_eos));
  92     }
  93     return (FIB_NODE_INDEX_INVALID);
  94 }
  95
  96 fib_node_index_t
  97 fib_table_lookup_exact_match (u32 fib_index,
  98                               const fib_prefix_t *prefix)
  99 {
 100     return (fib_table_lookup_exact_match_i(fib_table_get(fib_index,
 101                                                          prefix->fp_proto),
 102                                            prefix));
 103 }
 104
 105 static fib_node_index_t
 106 fib_table_get_less_specific_i (fib_table_t *fib_table,
 107                                const fib_prefix_t *prefix)
 108 {
 109     fib_prefix_t pfx;
 110
 111     pfx = *prefix;
 112
 113     if (FIB_PROTOCOL_MPLS == pfx.fp_proto)
 114     {
 115         return (FIB_NODE_INDEX_INVALID);
 116     }
 117
 118     /*
 119      * in the absence of a tree structure for the table that allows for an O(1)
 120      * parent get, a cheeky way to find the cover is to LPM for the prefix with
 121      * mask-1.
 122      * there should always be a cover, though it may be the default route. the
 123      * default route's cover is the default route.
 124      */
 125     if (pfx.fp_len != 0) {
 126         pfx.fp_len -= 1;
 127     }
 128
 129     return (fib_table_lookup_i(fib_table, &pfx));
 130 }
 131
 132 fib_node_index_t
 133 fib_table_get_less_specific (u32 fib_index,
 134                              const fib_prefix_t *prefix)
 135 {
 136     return (fib_table_get_less_specific_i(fib_table_get(fib_index,
 137                                                         prefix->fp_proto),
 138                                           prefix));
 139 }
 140
 141 static void
 142 fib_table_entry_remove (fib_table_t *fib_table,
 143                         const fib_prefix_t *prefix,
 144                         fib_node_index_t fib_entry_index)
 145 {
 146     vlib_smp_unsafe_warning();
 147
 148     fib_table->ft_total_route_counts--;
 149
 150     switch (prefix->fp_proto)
 151     {
 152     case FIB_PROTOCOL_IP4:
 153         ip4_fib_table_entry_remove(ip4_fib_get(fib_table->ft_index),
 154                                    &prefix->fp_addr.ip4,
 155                                    prefix->fp_len);
 156         break;
 157     case FIB_PROTOCOL_IP6:
 158         ip6_fib_table_entry_remove(fib_table->ft_index,
 159                                    &prefix->fp_addr.ip6,
 160                                    prefix->fp_len);
 161         break;
 162     case FIB_PROTOCOL_MPLS:
 163         mpls_fib_table_entry_remove(mpls_fib_get(fib_table->ft_index),
 164                                     prefix->fp_label,
 165                                     prefix->fp_eos);
 166         break;
 167     }
 168
 169     fib_entry_unlock(fib_entry_index);
 170 }
 171
 172 static void
 173 fib_table_post_insert_actions (fib_table_t *fib_table,
 174                                const fib_prefix_t *prefix,
 175                                fib_node_index_t fib_entry_index)
 176 {
 177     fib_node_index_t fib_entry_cover_index;
 178
 179     /*
 180      * no cover relationships in the MPLS FIB
 181      */
 182     if (FIB_PROTOCOL_MPLS == prefix->fp_proto)
 183         return;
 184
 185     /*
 186      * find  the covering entry
 187      */
 188     fib_entry_cover_index = fib_table_get_less_specific_i(fib_table, prefix);
 189     /*
 190      * the indicies are the same when the default route is first added
 191      */
 192     if (fib_entry_cover_index != fib_entry_index)
 193     {
 194         /*
 195          * push any inherting sources from the cover onto the covered
 196          */
 197         fib_entry_inherit(fib_entry_cover_index,
 198                           fib_entry_index);
 199
 200         /*
 201          * inform the covering entry that a new more specific
 202          * has been inserted beneath it.
 203          * If the prefix that has been inserted is a host route
 204          * then it is not possible that it will be the cover for any
 205          * other entry, so we can elide the walk. This is particularly
 206          * beneficial since there are often many host entries sharing the
 207          * same cover (i.e. ADJ or RR sourced entries).
 208          */
 209         if (!fib_entry_is_host(fib_entry_index))
 210         {
 211             fib_entry_cover_change_notify(fib_entry_cover_index,
 212                                           fib_entry_index);
 213         }
 214     }
 215 }
 216
 217 static void
 218 fib_table_entry_insert (fib_table_t *fib_table,
 219                         const fib_prefix_t *prefix,
 220                         fib_node_index_t fib_entry_index)
 221 {
 222     vlib_smp_unsafe_warning();
 223
 224     fib_entry_lock(fib_entry_index);
 225     fib_table->ft_total_route_counts++;
 226
 227     switch (prefix->fp_proto)
 228     {
 229     case FIB_PROTOCOL_IP4:
 230         ip4_fib_table_entry_insert(ip4_fib_get(fib_table->ft_index),
 231                                    &prefix->fp_addr.ip4,
 232                                    prefix->fp_len,
 233                                    fib_entry_index);
 234         break;
 235     case FIB_PROTOCOL_IP6:
 236         ip6_fib_table_entry_insert(fib_table->ft_index,
 237                                    &prefix->fp_addr.ip6,
 238                                    prefix->fp_len,
 239                                    fib_entry_index);
 240         break;
 241     case FIB_PROTOCOL_MPLS:
 242         mpls_fib_table_entry_insert(mpls_fib_get(fib_table->ft_index),
 243                                     prefix->fp_label,
 244                                     prefix->fp_eos,
 245                                     fib_entry_index);
 246         break;
 247     }
 248
 249     fib_table_post_insert_actions(fib_table, prefix, fib_entry_index);
 250 }
 251
 252 void
 253 fib_table_fwding_dpo_update (u32 fib_index,
 254                              const fib_prefix_t *prefix,
 255                              const dpo_id_t *dpo)
 256 {
 257     vlib_smp_unsafe_warning();
 258
 259     switch (prefix->fp_proto)
 260     {
 261     case FIB_PROTOCOL_IP4:
 262         return (ip4_fib_table_fwding_dpo_update(ip4_fib_get(fib_index),
 263                                                 &prefix->fp_addr.ip4,
 264                                                 prefix->fp_len,
 265                                                 dpo));
 266     case FIB_PROTOCOL_IP6:
 267         return (ip6_fib_table_fwding_dpo_update(fib_index,
 268                                                 &prefix->fp_addr.ip6,
 269                                                 prefix->fp_len,
 270                                                 dpo));
 271     case FIB_PROTOCOL_MPLS:
 272         return (mpls_fib_forwarding_table_update(mpls_fib_get(fib_index),
 273                                                  prefix->fp_label,
 274                                                  prefix->fp_eos,
 275                                                  dpo));
 276     }
 277 }
 278
 279 void
 280 fib_table_fwding_dpo_remove (u32 fib_index,
 281                              const fib_prefix_t *prefix,
 282                              const dpo_id_t *dpo)
 283 {
 284     vlib_smp_unsafe_warning();
 285
 286     switch (prefix->fp_proto)
 287     {
 288     case FIB_PROTOCOL_IP4:
 289         return (ip4_fib_table_fwding_dpo_remove(ip4_fib_get(fib_index),
 290                                                 &prefix->fp_addr.ip4,
 291                                                 prefix->fp_len,
 292                                                 dpo,
 293                                                 fib_table_get_less_specific(fib_index,
 294                                                                             prefix)));
 295     case FIB_PROTOCOL_IP6:
 296         return (ip6_fib_table_fwding_dpo_remove(fib_index,
 297                                                 &prefix->fp_addr.ip6,
 298                                                 prefix->fp_len,
 299                                                 dpo));
 300     case FIB_PROTOCOL_MPLS:
 301         return (mpls_fib_forwarding_table_reset(mpls_fib_get(fib_index),
 302                                                 prefix->fp_label,
 303                                                 prefix->fp_eos));
 304     }
 305 }
 306
 307 static void
 308 fib_table_source_count_inc (fib_table_t *fib_table,
 309                             fib_source_t source)
 310 {
 311     vec_validate (fib_table->ft_src_route_counts, source);
 312     fib_table->ft_src_route_counts[source]++;
 313 }
 314
 315 static void
 316 fib_table_source_count_dec (fib_table_t *fib_table,
 317                             fib_source_t source)
 318 {
 319     vec_validate (fib_table->ft_src_route_counts, source);
 320     fib_table->ft_src_route_counts[source]--;
 321 }
 322
 323 fib_node_index_t
 324 fib_table_entry_special_dpo_add (u32 fib_index,
 325                                  const fib_prefix_t *prefix,
 326                                  fib_source_t source,
 327                                  fib_entry_flag_t flags,
 328                                  const dpo_id_t *dpo)
 329 {
 330     fib_node_index_t fib_entry_index;
 331     fib_table_t *fib_table;
 332
 333     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 334     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 335
 336     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 337     {
 338         fib_entry_index = fib_entry_create_special(fib_index, prefix,
 339                                                    source, flags,
 340                                                    dpo);
 341
 342         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 343         fib_table_source_count_inc(fib_table, source);
 344     }
 345     else
 346     {
 347         int was_sourced;
 348
 349         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 350         fib_entry_special_add(fib_entry_index, source, flags, dpo);
 351
 352         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 353         {
 354         fib_table_source_count_inc(fib_table, source);
 355         }
 356     }
 357
 358
 359     return (fib_entry_index);
 360 }
 361
 362 fib_node_index_t
 363 fib_table_entry_special_dpo_update (u32 fib_index,
 364                                     const fib_prefix_t *prefix,
 365                                     fib_source_t source,
 366                                     fib_entry_flag_t flags,
 367                                     const dpo_id_t *dpo)
 368 {
 369     fib_node_index_t fib_entry_index;
 370     fib_table_t *fib_table;
 371
 372     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 373     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 374
 375     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 376     {
 377         fib_entry_index = fib_entry_create_special(fib_index, prefix,
 378                                                    source, flags,
 379                                                    dpo);
 380
 381         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 382         fib_table_source_count_inc(fib_table, source);
 383     }
 384     else
 385     {
 386         int was_sourced;
 387
 388         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 389
 390         if (was_sourced)
 391             fib_entry_special_update(fib_entry_index, source, flags, dpo);
 392         else
 393             fib_entry_special_add(fib_entry_index, source, flags, dpo);
 394
 395         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 396         {
 397             fib_table_source_count_inc(fib_table, source);
 398         }
 399     }
 400
 401     return (fib_entry_index);
 402 }
 403
 404 fib_node_index_t
 405 fib_table_entry_special_add (u32 fib_index,
 406                              const fib_prefix_t *prefix,
 407                              fib_source_t source,
 408                              fib_entry_flag_t flags)
 409 {
 410     fib_node_index_t fib_entry_index;
 411     dpo_id_t tmp_dpo = DPO_INVALID;
 412
 413     dpo_copy(&tmp_dpo, drop_dpo_get(fib_proto_to_dpo(prefix->fp_proto)));
 414
 415     fib_entry_index = fib_table_entry_special_dpo_add(fib_index, prefix, source,
 416                                                       flags, &tmp_dpo);
 417
 418     dpo_unlock(&tmp_dpo);
 419
 420     return (fib_entry_index);
 421 }
 422
 423 void
 424 fib_table_entry_special_remove (u32 fib_index,
 425                                 const fib_prefix_t *prefix,
 426                                 fib_source_t source)
 427 {
 428     /*
 429      * 1 is it present
 430      *   yes => remove source
 431      *    2 - is it still sourced?
 432      *      no => cover walk
 433      */
 434     fib_node_index_t fib_entry_index;
 435     fib_table_t *fib_table;
 436
 437     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 438     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 439
 440     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 441     {
 442         /*
 443          * removing an etry that does not exist. i'll allow it.
 444          */
 445     }
 446     else
 447     {
 448         fib_entry_src_flag_t src_flag;
 449         int was_sourced;
 450
 451         /*
 452          * don't nobody go nowhere
 453          */
 454         fib_entry_lock(fib_entry_index);
 455         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 456
 457         src_flag = fib_entry_special_remove(fib_entry_index, source);
 458
 459         if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 460         {
 461             /*
 462              * last source gone. remove from the table
 463              */
 464             fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 465
 466             /*
 467              * now the entry is no longer in the table, we can
 468              * inform the entries that it covers to re-calculate their cover
 469              */
 470             fib_entry_cover_change_notify(fib_entry_index,
 471                                           FIB_NODE_INDEX_INVALID);
 472         }
 473         /*
 474          * else
 475          *   still has sources, leave it be.
 476          */
 477         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 478         {
 479             fib_table_source_count_dec(fib_table, source);
 480         }
 481
 482         fib_entry_unlock(fib_entry_index);
 483     }
 484 }
 485
 486 /**
 487  * fib_table_route_path_fixup
 488  *
 489  * Convert attached hosts to attached next-hops.
 490  *
 491  * This special case is required because an attached path will link to a
 492  * glean, and the FIB entry will have the interface or API/CLI source. When
 493  * the ARP/ND process is completes then that source (which will provide a
 494  * complete adjacency) will be lower priority and so the FIB entry will
 495  * remain linked to a glean and traffic will never reach the hosts. For
 496  * an ATTAHCED_HOST path we can link the path directly to the [incomplete]
 497  * adjacency.
 498  */
 499 static void
 500 fib_table_route_path_fixup (const fib_prefix_t *prefix,
 501                             fib_entry_flag_t *eflags,
 502                             fib_route_path_t *path)
 503 {
 504     /*
 505      * not all zeros next hop &&
 506      * is recursive path &&
 507      * nexthop is same as the route's address
 508      */
 509     if ((!ip46_address_is_zero(&path->frp_addr)) &&
 510         (~0 == path->frp_sw_if_index) &&
 511         (0 == ip46_address_cmp(&path->frp_addr, &prefix->fp_addr)))
 512     {
 513         /* Prefix recurses via itself */
 514         path->frp_flags |= FIB_ROUTE_PATH_DROP;
 515     }
 516     if (!(path->frp_flags & FIB_ROUTE_PATH_LOCAL) &&
 517         fib_prefix_is_host(prefix) &&
 518         ip46_address_is_zero(&path->frp_addr) &&
 519         path->frp_sw_if_index != ~0 &&
 520         path->frp_proto != DPO_PROTO_ETHERNET)
 521     {
 522         path->frp_addr = prefix->fp_addr;
 523         path->frp_flags |= FIB_ROUTE_PATH_ATTACHED;
 524     }
 525     else if ((*eflags & FIB_ENTRY_FLAG_CONNECTED) &&
 526              !(*eflags & FIB_ENTRY_FLAG_LOCAL))
 527     {
 528         if (ip46_address_is_zero(&path->frp_addr))
 529         {
 530             path->frp_flags |= FIB_ROUTE_PATH_GLEAN;
 531             fib_prefix_normalize(prefix, &path->frp_connected);
 532         }
 533     }
 534     else if (fib_route_path_is_attached(path))
 535     {
 536         path->frp_flags |= FIB_ROUTE_PATH_GLEAN;
 537         /*
 538          * attached prefixes are not suitable as the source of ARP requests
 539          * so don't save the prefix in the glean adj
 540          */
 541         clib_memset(&path->frp_connected, 0, sizeof(path->frp_connected));
 542     }
 543     if (*eflags & FIB_ENTRY_FLAG_DROP)
 544     {
 545         path->frp_flags |= FIB_ROUTE_PATH_DROP;
 546     }
 547     if (*eflags & FIB_ENTRY_FLAG_LOCAL)
 548     {
 549         path->frp_flags |= FIB_ROUTE_PATH_LOCAL;
 550     }
 551     if (*eflags & FIB_ENTRY_FLAG_EXCLUSIVE)
 552     {
 553         path->frp_flags |= FIB_ROUTE_PATH_EXCLUSIVE;
 554     }
 555     if (path->frp_flags & FIB_ROUTE_PATH_LOCAL)
 556     {
 557         *eflags |= FIB_ENTRY_FLAG_LOCAL;
 558
 559         if (path->frp_sw_if_index != ~0)
 560         {
 561             *eflags |= FIB_ENTRY_FLAG_CONNECTED;
 562         }
 563     }
 564 }
 565
 566 fib_node_index_t
 567 fib_table_entry_path_add (u32 fib_index,
 568                           const fib_prefix_t *prefix,
 569                           fib_source_t source,
 570                           fib_entry_flag_t flags,
 571                           dpo_proto_t next_hop_proto,
 572                           const ip46_address_t *next_hop,
 573                           u32 next_hop_sw_if_index,
 574                           u32 next_hop_fib_index,
 575                           u32 next_hop_weight,
 576                           fib_mpls_label_t *next_hop_labels,
 577                           fib_route_path_flags_t path_flags)
 578 {
 579     fib_route_path_t path = {
 580         .frp_proto = next_hop_proto,
 581         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 582         .frp_sw_if_index = next_hop_sw_if_index,
 583         .frp_fib_index = next_hop_fib_index,
 584         .frp_weight = next_hop_weight,
 585         .frp_flags = path_flags,
 586         .frp_rpf_id = INDEX_INVALID,
 587         .frp_label_stack = next_hop_labels,
 588     };
 589     fib_node_index_t fib_entry_index;
 590     fib_route_path_t *paths = NULL;
 591
 592     vec_add1(paths, path);
 593
 594     fib_entry_index = fib_table_entry_path_add2(fib_index, prefix,
 595                                                 source, flags, paths);
 596
 597     vec_free(paths);
 598     return (fib_entry_index);
 599 }
 600
 601 static int
 602 fib_route_path_cmp_for_sort (void * v1,
 603                              void * v2)
 604 {
 605     return (fib_route_path_cmp(v1, v2));
 606 }
 607
 608 fib_node_index_t
 609 fib_table_entry_path_add2 (u32 fib_index,
 610                            const fib_prefix_t *prefix,
 611                            fib_source_t source,
 612                            fib_entry_flag_t flags,
 613                            fib_route_path_t *rpaths)
 614 {
 615     fib_node_index_t fib_entry_index;
 616     fib_table_t *fib_table;
 617     u32 ii;
 618
 619     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 620     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 621
 622     for (ii = 0; ii < vec_len(rpaths); ii++)
 623     {
 624         fib_table_route_path_fixup(prefix, &flags, &rpaths[ii]);
 625     }
 626     /*
 627      * sort the paths provided by the control plane. this means
 628      * the paths and the extension on the entry will be sorted.
 629      */
 630     vec_sort_with_function(rpaths, fib_route_path_cmp_for_sort);
 631
 632     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 633     {
 634         fib_entry_index = fib_entry_create(fib_index, prefix,
 635                                            source, flags,
 636                                            rpaths);
 637
 638         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 639         fib_table_source_count_inc(fib_table, source);
 640     }
 641     else
 642     {
 643         int was_sourced;
 644
 645         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 646         fib_entry_path_add(fib_entry_index, source, flags, rpaths);;
 647
 648         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 649         {
 650             fib_table_source_count_inc(fib_table, source);
 651         }
 652     }
 653
 654     return (fib_entry_index);
 655 }
 656
 657 void
 658 fib_table_entry_path_remove2 (u32 fib_index,
 659                               const fib_prefix_t *prefix,
 660                               fib_source_t source,
 661                               fib_route_path_t *rpaths)
 662 {
 663     /*
 664      * 1 is it present
 665      *   yes => remove source
 666      *    2 - is it still sourced?
 667      *      no => cover walk
 668      */
 669     fib_node_index_t fib_entry_index;
 670     fib_route_path_t *rpath;
 671     fib_table_t *fib_table;
 672
 673     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 674     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 675
 676     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 677     {
 678         /*
 679          * removing an etry that does not exist. i'll allow it.
 680          */
 681     }
 682     else
 683     {
 684         fib_entry_src_flag_t src_flag;
 685         int was_sourced;
 686
 687         /*
 688          * if it's not sourced, then there's nowt to remove
 689          */
 690         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 691         if (!was_sourced)
 692         {
 693             return;
 694         }
 695
 696         /*
 697          * don't nobody go nowhere
 698          */
 699         fib_entry_lock(fib_entry_index);
 700
 701         vec_foreach(rpath, rpaths)
 702         {
 703             fib_entry_flag_t eflags;
 704
 705             eflags = fib_entry_get_flags_for_source(fib_entry_index,
 706                                                     source);
 707             fib_table_route_path_fixup(prefix, &eflags, rpath);
 708         }
 709
 710         src_flag = fib_entry_path_remove(fib_entry_index, source, rpaths);
 711
 712         if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 713         {
 714             /*
 715              * last source gone. remove from the table
 716              */
 717             fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 718
 719             /*
 720              * now the entry is no longer in the table, we can
 721              * inform the entries that it covers to re-calculate their cover
 722              */
 723             fib_entry_cover_change_notify(fib_entry_index,
 724                                           FIB_NODE_INDEX_INVALID);
 725         }
 726         /*
 727          * else
 728          *   still has sources, leave it be.
 729          */
 730         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 731         {
 732             fib_table_source_count_dec(fib_table, source);
 733         }
 734
 735         fib_entry_unlock(fib_entry_index);
 736     }
 737 }
 738
 739 void
 740 fib_table_entry_path_remove (u32 fib_index,
 741                              const fib_prefix_t *prefix,
 742                              fib_source_t source,
 743                              dpo_proto_t next_hop_proto,
 744                              const ip46_address_t *next_hop,
 745                              u32 next_hop_sw_if_index,
 746                              u32 next_hop_fib_index,
 747                              u32 next_hop_weight,
 748                              fib_route_path_flags_t path_flags)
 749 {
 750     /*
 751      * 1 is it present
 752      *   yes => remove source
 753      *    2 - is it still sourced?
 754      *      no => cover walk
 755      */
 756     fib_route_path_t path = {
 757         .frp_proto = next_hop_proto,
 758         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 759         .frp_sw_if_index = next_hop_sw_if_index,
 760         .frp_fib_index = next_hop_fib_index,
 761         .frp_weight = next_hop_weight,
 762         .frp_flags = path_flags,
 763     };
 764     fib_route_path_t *paths = NULL;
 765
 766     vec_add1(paths, path);
 767
 768     fib_table_entry_path_remove2(fib_index, prefix, source, paths);
 769
 770     vec_free(paths);
 771 }
 772
 773 fib_node_index_t
 774 fib_table_entry_update (u32 fib_index,
 775                         const fib_prefix_t *prefix,
 776                         fib_source_t source,
 777                         fib_entry_flag_t flags,
 778                         fib_route_path_t *paths)
 779 {
 780     fib_node_index_t fib_entry_index;
 781     fib_table_t *fib_table;
 782     u32 ii;
 783
 784     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 785     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 786
 787     for (ii = 0; ii < vec_len(paths); ii++)
 788     {
 789         fib_table_route_path_fixup(prefix, &flags, &paths[ii]);
 790     }
 791     /*
 792      * sort the paths provided by the control plane. this means
 793      * the paths and the extension on the entry will be sorted.
 794      */
 795     vec_sort_with_function(paths, fib_route_path_cmp_for_sort);
 796
 797     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 798     {
 799         fib_entry_index = fib_entry_create(fib_index, prefix,
 800                                            source, flags,
 801                                            paths);
 802
 803         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 804         fib_table_source_count_inc(fib_table, source);
 805     }
 806     else
 807     {
 808         int was_sourced;
 809
 810         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 811         fib_entry_update(fib_entry_index, source, flags, paths);
 812
 813         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 814         {
 815             fib_table_source_count_inc(fib_table, source);
 816         }
 817     }
 818
 819     return (fib_entry_index);
 820 }
 821
 822 fib_node_index_t
 823 fib_table_entry_update_one_path (u32 fib_index,
 824                                  const fib_prefix_t *prefix,
 825                                  fib_source_t source,
 826                                  fib_entry_flag_t flags,
 827                                  dpo_proto_t next_hop_proto,
 828                                  const ip46_address_t *next_hop,
 829                                  u32 next_hop_sw_if_index,
 830                                  u32 next_hop_fib_index,
 831                                  u32 next_hop_weight,
 832                                  fib_mpls_label_t *next_hop_labels,
 833                                  fib_route_path_flags_t path_flags)
 834 {
 835     fib_node_index_t fib_entry_index;
 836     fib_route_path_t path = {
 837         .frp_proto = next_hop_proto,
 838         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 839         .frp_sw_if_index = next_hop_sw_if_index,
 840         .frp_fib_index = next_hop_fib_index,
 841         .frp_weight = next_hop_weight,
 842         .frp_flags = path_flags,
 843         .frp_label_stack = next_hop_labels,
 844     };
 845     fib_route_path_t *paths = NULL;
 846
 847     vec_add1(paths, path);
 848
 849     fib_entry_index =
 850         fib_table_entry_update(fib_index, prefix, source, flags, paths);
 851
 852     vec_free(paths);
 853
 854     return (fib_entry_index);
 855 }
 856
 857 static void
 858 fib_table_entry_delete_i (u32 fib_index,
 859                           fib_node_index_t fib_entry_index,
 860                           const fib_prefix_t *prefix,
 861                           fib_source_t source)
 862 {
 863     fib_entry_src_flag_t src_flag;
 864     fib_table_t *fib_table;
 865     int was_sourced;
 866
 867     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 868     was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 869
 870     /*
 871      * don't nobody go nowhere
 872      */
 873     fib_entry_lock(fib_entry_index);
 874
 875     src_flag = fib_entry_delete(fib_entry_index, source);
 876
 877     if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 878     {
 879         /*
 880          * last source gone. remove from the table
 881          */
 882         fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 883
 884         /*
 885          * now the entry is no longer in the table, we can
 886          * inform the entries that it covers to re-calculate their cover
 887          */
 888         fib_entry_cover_change_notify(fib_entry_index,
 889                                       FIB_NODE_INDEX_INVALID);
 890     }
 891     /*
 892      * else
 893      *   still has sources, leave it be.
 894      */
 895     if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 896     {
 897         fib_table_source_count_dec(fib_table, source);
 898     }
 899
 900     fib_entry_unlock(fib_entry_index);
 901 }
 902
 903 void
 904 fib_table_entry_delete (u32 fib_index,
 905                         const fib_prefix_t *prefix,
 906                         fib_source_t source)
 907 {
 908     fib_node_index_t fib_entry_index;
 909
 910     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 911
 912     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 913     {
 914         /*
 915          * removing an etry that does not exist.
 916          * i'll allow it, but i won't like it.
 917          */
 918         if (0)
 919             clib_warning("%U not in FIB", format_fib_prefix, prefix);
 920     }
 921     else
 922     {
 923         fib_table_entry_delete_i(fib_index, fib_entry_index, prefix, source);
 924     }
 925 }
 926
 927 void
 928 fib_table_entry_delete_index (fib_node_index_t fib_entry_index,
 929                               fib_source_t source)
 930 {
 931     const fib_prefix_t *prefix;
 932
 933     prefix = fib_entry_get_prefix(fib_entry_index);
 934
 935     fib_table_entry_delete_i(fib_entry_get_fib_index(fib_entry_index),
 936                              fib_entry_index, prefix, source);
 937 }
 938
 939 u32
 940 fib_table_entry_get_stats_index (u32 fib_index,
 941                                  const fib_prefix_t *prefix)
 942 {
 943     return (fib_entry_get_stats_index(
 944                 fib_table_lookup_exact_match(fib_index, prefix)));
 945 }
 946
 947 fib_node_index_t
 948 fib_table_entry_local_label_add (u32 fib_index,
 949                                  const fib_prefix_t *prefix,
 950                                  mpls_label_t label)
 951 {
 952     fib_node_index_t fib_entry_index;
 953
 954     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 955
 956     if (FIB_NODE_INDEX_INVALID == fib_entry_index ||
 957         !fib_entry_is_sourced(fib_entry_index, FIB_SOURCE_MPLS))
 958     {
 959         /*
 960          * only source the prefix once. this allows the label change
 961          * operation to work
 962          */
 963         fib_entry_index = fib_table_entry_special_dpo_add(fib_index, prefix,
 964                                                           FIB_SOURCE_MPLS,
 965                                                           FIB_ENTRY_FLAG_NONE,
 966                                                           NULL);
 967     }
 968
 969     fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &label);
 970
 971     return (fib_entry_index);
 972 }
 973
 974 void
 975 fib_table_entry_local_label_remove (u32 fib_index,
 976                                     const fib_prefix_t *prefix,
 977                                     mpls_label_t label)
 978 {
 979     fib_node_index_t fib_entry_index;
 980     const void *data;
 981     mpls_label_t pl;
 982
 983     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 984
 985     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 986         return;
 987
 988     data = fib_entry_get_source_data(fib_entry_index, FIB_SOURCE_MPLS);
 989
 990     if (NULL == data)
 991         return;
 992
 993     pl = *(mpls_label_t*)data;
 994
 995     if (pl != label)
 996         return;
 997
 998     pl = MPLS_LABEL_INVALID;
 999
1000     fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &pl);
1001     fib_table_entry_special_remove(fib_index,
1002                                    prefix,
1003                                    FIB_SOURCE_MPLS);
1004 }
1005
1006 u32
1007 fib_table_get_index_for_sw_if_index (fib_protocol_t proto,
1008                                      u32 sw_if_index)
1009 {
1010     switch (proto)
1011     {
1012     case FIB_PROTOCOL_IP4:
1013         return (ip4_fib_table_get_index_for_sw_if_index(sw_if_index));
1014     case FIB_PROTOCOL_IP6:
1015         return (ip6_fib_table_get_index_for_sw_if_index(sw_if_index));
1016     case FIB_PROTOCOL_MPLS:
1017         return (mpls_fib_table_get_index_for_sw_if_index(sw_if_index));
1018     }
1019     return (~0);
1020 }
1021
1022 flow_hash_config_t
1023 fib_table_get_flow_hash_config (u32 fib_index,
1024                                 fib_protocol_t proto)
1025 {
1026     fib_table_t *fib;
1027
1028     fib = fib_table_get(fib_index, proto);
1029
1030     return (fib->ft_flow_hash_config);
1031 }
1032
1033 flow_hash_config_t
1034 fib_table_get_default_flow_hash_config (fib_protocol_t proto)
1035 {
1036     switch (proto)
1037     {
1038     case FIB_PROTOCOL_IP4:
1039     case FIB_PROTOCOL_IP6:
1040         return (IP_FLOW_HASH_DEFAULT);
1041
1042     case FIB_PROTOCOL_MPLS:
1043         return (MPLS_FLOW_HASH_DEFAULT);
1044     }
1045
1046     ASSERT(0);
1047     return (IP_FLOW_HASH_DEFAULT);
1048 }
1049
1050 /**
1051  * @brief Table set flow hash config context.
1052  */
1053 typedef struct fib_table_set_flow_hash_config_ctx_t_
1054 {
1055     /**
1056      * the flow hash config to set
1057      */
1058     flow_hash_config_t hash_config;
1059 } fib_table_set_flow_hash_config_ctx_t;
1060
1061 static fib_table_walk_rc_t
1062 fib_table_set_flow_hash_config_cb (fib_node_index_t fib_entry_index,
1063                                    void *arg)
1064 {
1065     fib_table_set_flow_hash_config_ctx_t *ctx = arg;
1066
1067     fib_entry_set_flow_hash_config(fib_entry_index, ctx->hash_config);
1068
1069     return (FIB_TABLE_WALK_CONTINUE);
1070 }
1071
1072 void
1073 fib_table_set_flow_hash_config (u32 fib_index,
1074                                 fib_protocol_t proto,
1075                                 flow_hash_config_t hash_config)
1076 {
1077     fib_table_set_flow_hash_config_ctx_t ctx = {
1078         .hash_config = hash_config,
1079     };
1080     fib_table_t *fib;
1081
1082     fib = fib_table_get(fib_index, proto);
1083     fib->ft_flow_hash_config = hash_config;
1084
1085     fib_table_walk(fib_index, proto,
1086                    fib_table_set_flow_hash_config_cb,
1087                    &ctx);
1088 }
1089
1090 u32
1091 fib_table_get_table_id_for_sw_if_index (fib_protocol_t proto,
1092                                         u32 sw_if_index)
1093 {
1094     fib_table_t *fib_table;
1095
1096     fib_table = fib_table_get(fib_table_get_index_for_sw_if_index(
1097                                   proto, sw_if_index),
1098                               proto);
1099
1100     return ((NULL != fib_table ? fib_table->ft_table_id : ~0));
1101 }
1102
1103 u32
1104 fib_table_get_table_id (u32 fib_index,
1105                         fib_protocol_t proto)
1106 {
1107     fib_table_t *fib_table;
1108
1109     fib_table = fib_table_get(fib_index, proto);
1110
1111     return ((NULL != fib_table ? fib_table->ft_table_id : ~0));
1112 }
1113
1114 u32
1115 fib_table_find (fib_protocol_t proto,
1116                 u32 table_id)
1117 {
1118     switch (proto)
1119     {
1120     case FIB_PROTOCOL_IP4:
1121         return (ip4_fib_index_from_table_id(table_id));
1122     case FIB_PROTOCOL_IP6:
1123         return (ip6_fib_index_from_table_id(table_id));
1124     case FIB_PROTOCOL_MPLS:
1125         return (mpls_fib_index_from_table_id(table_id));
1126     }
1127     return (~0);
1128 }
1129
1130 static u32
1131 fib_table_find_or_create_and_lock_i (fib_protocol_t proto,
1132                                      u32 table_id,
1133                                      fib_source_t src,
1134                                      const u8 *name)
1135 {
1136     fib_table_t *fib_table;
1137     fib_node_index_t fi;
1138
1139     switch (proto)
1140     {
1141     case FIB_PROTOCOL_IP4:
1142         fi = ip4_fib_table_find_or_create_and_lock(table_id, src);
1143         break;
1144     case FIB_PROTOCOL_IP6:
1145         fi = ip6_fib_table_find_or_create_and_lock(table_id, src);
1146         break;
1147     case FIB_PROTOCOL_MPLS:
1148         fi = mpls_fib_table_find_or_create_and_lock(table_id, src);
1149         break;
1150     default:
1151         return (~0);
1152     }
1153
1154     fib_table = fib_table_get(fi, proto);
1155
1156     if (NULL == fib_table->ft_desc)
1157     {
1158         if (name && name[0])
1159         {
1160             fib_table->ft_desc = format(NULL, "%s", name);
1161         }
1162         else
1163         {
1164             fib_table->ft_desc = format(NULL, "%U-VRF:%d",
1165                                         format_fib_protocol, proto,
1166                                         table_id);
1167         }
1168     }
1169
1170     return (fi);
1171 }
1172
1173 u32
1174 fib_table_find_or_create_and_lock (fib_protocol_t proto,
1175                                    u32 table_id,
1176                                    fib_source_t src)
1177 {
1178     return (fib_table_find_or_create_and_lock_i(proto, table_id,
1179                                                 src, NULL));
1180 }
1181
1182 u32
1183 fib_table_find_or_create_and_lock_w_name (fib_protocol_t proto,
1184                                           u32 table_id,
1185                                           fib_source_t src,
1186                                           const u8 *name)
1187 {
1188     return (fib_table_find_or_create_and_lock_i(proto, table_id,
1189                                                 src, name));
1190 }
1191
1192 u32
1193 fib_table_create_and_lock (fib_protocol_t proto,
1194                            fib_source_t src,
1195                            const char *const fmt,
1196                            ...)
1197 {
1198     fib_table_t *fib_table;
1199     fib_node_index_t fi;
1200     va_list ap;
1201
1202
1203     switch (proto)
1204     {
1205     case FIB_PROTOCOL_IP4:
1206         fi = ip4_fib_table_create_and_lock(src);
1207         break;
1208     case FIB_PROTOCOL_IP6:
1209         fi = ip6_fib_table_create_and_lock(src, FIB_TABLE_FLAG_NONE, NULL);
1210         break;
1211      case FIB_PROTOCOL_MPLS:
1212         fi = mpls_fib_table_create_and_lock(src);
1213         break;
1214    default:
1215         return (~0);
1216     }
1217
1218     fib_table = fib_table_get(fi, proto);
1219
1220     va_start(ap, fmt);
1221
1222     fib_table->ft_desc = va_format(fib_table->ft_desc, fmt, &ap);
1223
1224     va_end(ap);
1225     return (fi);
1226 }
1227
1228 static void
1229 fib_table_destroy (fib_table_t *fib_table)
1230 {
1231     vec_free(fib_table->ft_desc);
1232
1233     switch (fib_table->ft_proto)
1234     {
1235     case FIB_PROTOCOL_IP4:
1236         ip4_fib_table_destroy(fib_table->ft_index);
1237         break;
1238     case FIB_PROTOCOL_IP6:
1239         ip6_fib_table_destroy(fib_table->ft_index);
1240         break;
1241     case FIB_PROTOCOL_MPLS:
1242         mpls_fib_table_destroy(fib_table->ft_index);
1243         break;
1244     }
1245 }
1246
1247 void
1248 fib_table_walk (u32 fib_index,
1249                 fib_protocol_t proto,
1250                 fib_table_walk_fn_t fn,
1251                 void *ctx)
1252 {
1253     switch (proto)
1254     {
1255     case FIB_PROTOCOL_IP4:
1256         ip4_fib_table_walk(ip4_fib_get(fib_index), fn, ctx);
1257         break;
1258     case FIB_PROTOCOL_IP6:
1259         ip6_fib_table_walk(fib_index, fn, ctx);
1260         break;
1261     case FIB_PROTOCOL_MPLS:
1262         mpls_fib_table_walk(mpls_fib_get(fib_index), fn, ctx);
1263         break;
1264     }
1265 }
1266
1267 typedef struct fib_table_walk_w_src_ctx_t_
1268 {
1269     fib_table_walk_fn_t fn;
1270     void *data;
1271     fib_source_t src;
1272 } fib_table_walk_w_src_cxt_t;
1273
1274 static fib_table_walk_rc_t
1275 fib_table_walk_w_src_cb (fib_node_index_t fei,
1276                          void *arg)
1277 {
1278     fib_table_walk_w_src_cxt_t *ctx = arg;
1279
1280     if (ctx->src == fib_entry_get_best_source(fei))
1281     {
1282         return (ctx->fn(fei, ctx->data));
1283     }
1284     return (FIB_TABLE_WALK_CONTINUE);
1285 }
1286
1287 void
1288 fib_table_walk_w_src (u32 fib_index,
1289                       fib_protocol_t proto,
1290                       fib_source_t src,
1291                       fib_table_walk_fn_t fn,
1292                       void *data)
1293 {
1294     fib_table_walk_w_src_cxt_t ctx = {
1295         .fn = fn,
1296         .src = src,
1297         .data = data,
1298     };
1299
1300     fib_table_walk(fib_index, proto, fib_table_walk_w_src_cb, &ctx);
1301 }
1302
1303 void
1304 fib_table_sub_tree_walk (u32 fib_index,
1305                          fib_protocol_t proto,
1306                          const fib_prefix_t *root,
1307                          fib_table_walk_fn_t fn,
1308                          void *ctx)
1309 {
1310     switch (proto)
1311     {
1312     case FIB_PROTOCOL_IP4:
1313         ip4_fib_table_sub_tree_walk(ip4_fib_get(fib_index), root, fn, ctx);
1314         break;
1315     case FIB_PROTOCOL_IP6:
1316         ip6_fib_table_sub_tree_walk(fib_index, root, fn, ctx);
1317         break;
1318     case FIB_PROTOCOL_MPLS:
1319         break;
1320     }
1321 }
1322
1323 static void
1324 fib_table_lock_dec (fib_table_t *fib_table,
1325                     fib_source_t source)
1326 {
1327     vec_validate(fib_table->ft_locks, source);
1328
1329     ASSERT(fib_table->ft_locks[source] > 0);
1330     fib_table->ft_locks[source]--;
1331     fib_table->ft_total_locks--;
1332 }
1333
1334 static void
1335 fib_table_lock_inc (fib_table_t *fib_table,
1336                     fib_source_t source)
1337 {
1338     vec_validate(fib_table->ft_locks, source);
1339
1340     ASSERT(fib_table->ft_total_locks < (0xffffffff - 1));
1341     fib_table->ft_locks[source]++;
1342     fib_table->ft_total_locks++;
1343 }
1344
1345
1346 static void
1347 fib_table_lock_clear (fib_table_t *fib_table,
1348                       fib_source_t source)
1349 {
1350     vec_validate(fib_table->ft_locks, source);
1351
1352     ASSERT(fib_table->ft_locks[source] <= 1);
1353     if (fib_table->ft_locks[source])
1354     {
1355         fib_table->ft_locks[source]--;
1356         fib_table->ft_total_locks--;
1357     }
1358 }
1359
1360 static void
1361 fib_table_lock_set (fib_table_t *fib_table,
1362                     fib_source_t source)
1363 {
1364     vec_validate(fib_table->ft_locks, source);
1365
1366     ASSERT(fib_table->ft_locks[source] <= 1);
1367     ASSERT(fib_table->ft_total_locks < (0xffffffff - 1));
1368     if (!fib_table->ft_locks[source])
1369     {
1370         fib_table->ft_locks[source]++;
1371         fib_table->ft_total_locks++;
1372     }
1373 }
1374
1375 void
1376 fib_table_unlock (u32 fib_index,
1377                   fib_protocol_t proto,
1378                   fib_source_t source)
1379 {
1380     fib_table_t *fib_table;
1381
1382     fib_table = fib_table_get(fib_index, proto);
1383
1384     if (source == FIB_SOURCE_API || source == FIB_SOURCE_CLI)
1385         fib_table_lock_clear(fib_table, source);
1386     else
1387         fib_table_lock_dec(fib_table, source);
1388
1389     if (0 == fib_table->ft_total_locks)
1390     {
1391         /*
1392          * no more lock from any source - kill it
1393          */
1394         fib_table_destroy(fib_table);
1395     }
1396 }
1397
1398 void
1399 fib_table_lock (u32 fib_index,
1400                 fib_protocol_t proto,
1401                 fib_source_t source)
1402 {
1403     fib_table_t *fib_table;
1404
1405     fib_table = fib_table_get(fib_index, proto);
1406
1407     if (source == FIB_SOURCE_API || source == FIB_SOURCE_CLI)
1408         fib_table_lock_set(fib_table, source);
1409     else
1410         fib_table_lock_inc(fib_table, source);
1411 }
1412
1413 u32
1414 fib_table_get_num_entries (u32 fib_index,
1415                            fib_protocol_t proto,
1416                            fib_source_t source)
1417 {
1418     fib_table_t *fib_table;
1419
1420     fib_table = fib_table_get(fib_index, proto);
1421
1422     return (fib_table->ft_src_route_counts[source]);
1423 }
1424
1425 u8*
1426 format_fib_table_name (u8* s, va_list* ap)
1427 {
1428     fib_node_index_t fib_index = va_arg(*ap, fib_node_index_t);
1429     fib_protocol_t proto = va_arg(*ap, int); // int promotion
1430     fib_table_t *fib_table;
1431
1432     fib_table = fib_table_get(fib_index, proto);
1433
1434     s = format(s, "%v", fib_table->ft_desc);
1435
1436     return (s);
1437 }
1438
1439 u8*
1440 format_fib_table_flags (u8 *s, va_list *args)
1441 {
1442     fib_table_flags_t flags = va_arg(*args, int);
1443     fib_table_attribute_t attr;
1444
1445     if (!flags)
1446     {
1447         return format(s, "none");
1448     }
1449
1450     FOR_EACH_FIB_TABLE_ATTRIBUTE(attr) {
1451         if (1 << attr & flags) {
1452             s = format(s, "%s", fib_table_flags_strings[attr]);
1453         }
1454     }
1455
1456     return (s);
1457 }
1458
1459 /**
1460  * @brief Table flush context. Store the indicies of matching FIB entries
1461  * that need to be removed.
1462  */
1463 typedef struct fib_table_flush_ctx_t_
1464 {
1465     /**
1466      * The list of entries to flush
1467      */
1468     fib_node_index_t *ftf_entries;
1469
1470     /**
1471      * The source we are flushing
1472      */
1473     fib_source_t ftf_source;
1474 } fib_table_flush_ctx_t;
1475
1476 static fib_table_walk_rc_t
1477 fib_table_flush_cb (fib_node_index_t fib_entry_index,
1478                     void *arg)
1479 {
1480     fib_table_flush_ctx_t *ctx = arg;
1481
1482     if (fib_entry_is_sourced(fib_entry_index, ctx->ftf_source))
1483     {
1484         vec_add1(ctx->ftf_entries, fib_entry_index);
1485     }
1486     return (FIB_TABLE_WALK_CONTINUE);
1487 }
1488
1489 void
1490 fib_table_flush (u32 fib_index,
1491                  fib_protocol_t proto,
1492                  fib_source_t source)
1493 {
1494     fib_node_index_t *fib_entry_index;
1495     fib_table_flush_ctx_t ctx = {
1496         .ftf_entries = NULL,
1497         .ftf_source = source,
1498     };
1499
1500     fib_table_walk(fib_index, proto,
1501                    fib_table_flush_cb,
1502                    &ctx);
1503
1504     vec_foreach(fib_entry_index, ctx.ftf_entries)
1505     {
1506         fib_table_entry_delete_index(*fib_entry_index, source);
1507     }
1508
1509     vec_free(ctx.ftf_entries);
1510 }
1511
1512 static fib_table_walk_rc_t
1513 fib_table_mark_cb (fib_node_index_t fib_entry_index,
1514                    void *arg)
1515 {
1516     fib_table_flush_ctx_t *ctx = arg;
1517
1518     if (fib_entry_is_sourced(fib_entry_index, ctx->ftf_source))
1519     {
1520         fib_entry_mark(fib_entry_index, ctx->ftf_source);
1521     }
1522     return (FIB_TABLE_WALK_CONTINUE);
1523 }
1524
1525 void
1526 fib_table_mark (u32 fib_index,
1527                 fib_protocol_t proto,
1528                 fib_source_t source)
1529 {
1530     fib_table_flush_ctx_t ctx = {
1531         .ftf_source = source,
1532     };
1533     fib_table_t *fib_table;
1534
1535     fib_table = fib_table_get(fib_index, proto);
1536
1537     fib_table->ft_epoch++;
1538     fib_table->ft_flags |= FIB_TABLE_FLAG_RESYNC;
1539
1540     fib_table_walk(fib_index, proto,
1541                    fib_table_mark_cb,
1542                    &ctx);
1543 }
1544
1545 static fib_table_walk_rc_t
1546 fib_table_sweep_cb (fib_node_index_t fib_entry_index,
1547                     void *arg)
1548 {
1549     fib_table_flush_ctx_t *ctx = arg;
1550
1551     if (fib_entry_is_marked(fib_entry_index, ctx->ftf_source))
1552     {
1553         vec_add1(ctx->ftf_entries, fib_entry_index);
1554     }
1555     return (FIB_TABLE_WALK_CONTINUE);
1556 }
1557
1558 void
1559 fib_table_sweep (u32 fib_index,
1560                  fib_protocol_t proto,
1561                  fib_source_t source)
1562 {
1563     fib_table_flush_ctx_t ctx = {
1564         .ftf_source = source,
1565     };
1566     fib_node_index_t *fib_entry_index;
1567     fib_table_t *fib_table;
1568
1569     fib_table = fib_table_get(fib_index, proto);
1570
1571     fib_table->ft_flags &= ~FIB_TABLE_FLAG_RESYNC;
1572
1573     fib_table_walk(fib_index, proto,
1574                    fib_table_sweep_cb,
1575                    &ctx);
1576
1577     vec_foreach(fib_entry_index, ctx.ftf_entries)
1578     {
1579         fib_table_entry_delete_index(*fib_entry_index, source);
1580     }
1581
1582     vec_free(ctx.ftf_entries);
1583 }
1584
1585 u8 *
1586 format_fib_table_memory (u8 *s, va_list *args)
1587 {
1588     s = format(s, "%U", format_ip4_fib_table_memory);
1589     s = format(s, "%U", format_ip6_fib_table_memory);
1590     s = format(s, "%U", format_mpls_fib_table_memory);
1591
1592     return (s);
1593 }