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     if (*eflags & FIB_ENTRY_FLAG_DROP)
 535     {
 536         path->frp_flags |= FIB_ROUTE_PATH_DROP;
 537     }
 538     if (*eflags & FIB_ENTRY_FLAG_LOCAL)
 539     {
 540         path->frp_flags |= FIB_ROUTE_PATH_LOCAL;
 541     }
 542     if (*eflags & FIB_ENTRY_FLAG_EXCLUSIVE)
 543     {
 544         path->frp_flags |= FIB_ROUTE_PATH_EXCLUSIVE;
 545     }
 546     if (path->frp_flags & FIB_ROUTE_PATH_LOCAL)
 547     {
 548         *eflags |= FIB_ENTRY_FLAG_LOCAL;
 549
 550         if (path->frp_sw_if_index != ~0)
 551         {
 552             *eflags |= FIB_ENTRY_FLAG_CONNECTED;
 553         }
 554     }
 555 }
 556
 557 fib_node_index_t
 558 fib_table_entry_path_add (u32 fib_index,
 559                           const fib_prefix_t *prefix,
 560                           fib_source_t source,
 561                           fib_entry_flag_t flags,
 562                           dpo_proto_t next_hop_proto,
 563                           const ip46_address_t *next_hop,
 564                           u32 next_hop_sw_if_index,
 565                           u32 next_hop_fib_index,
 566                           u32 next_hop_weight,
 567                           fib_mpls_label_t *next_hop_labels,
 568                           fib_route_path_flags_t path_flags)
 569 {
 570     fib_route_path_t path = {
 571         .frp_proto = next_hop_proto,
 572         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 573         .frp_sw_if_index = next_hop_sw_if_index,
 574         .frp_fib_index = next_hop_fib_index,
 575         .frp_weight = next_hop_weight,
 576         .frp_flags = path_flags,
 577         .frp_rpf_id = INDEX_INVALID,
 578         .frp_label_stack = next_hop_labels,
 579     };
 580     fib_node_index_t fib_entry_index;
 581     fib_route_path_t *paths = NULL;
 582
 583     vec_add1(paths, path);
 584
 585     fib_entry_index = fib_table_entry_path_add2(fib_index, prefix,
 586                                                 source, flags, paths);
 587
 588     vec_free(paths);
 589     return (fib_entry_index);
 590 }
 591
 592 static int
 593 fib_route_path_cmp_for_sort (void * v1,
 594                              void * v2)
 595 {
 596     return (fib_route_path_cmp(v1, v2));
 597 }
 598
 599 fib_node_index_t
 600 fib_table_entry_path_add2 (u32 fib_index,
 601                            const fib_prefix_t *prefix,
 602                            fib_source_t source,
 603                            fib_entry_flag_t flags,
 604                            fib_route_path_t *rpaths)
 605 {
 606     fib_node_index_t fib_entry_index;
 607     fib_table_t *fib_table;
 608     u32 ii;
 609
 610     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 611     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 612
 613     for (ii = 0; ii < vec_len(rpaths); ii++)
 614     {
 615         fib_table_route_path_fixup(prefix, &flags, &rpaths[ii]);
 616     }
 617     /*
 618      * sort the paths provided by the control plane. this means
 619      * the paths and the extension on the entry will be sorted.
 620      */
 621     vec_sort_with_function(rpaths, fib_route_path_cmp_for_sort);
 622
 623     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 624     {
 625         fib_entry_index = fib_entry_create(fib_index, prefix,
 626                                            source, flags,
 627                                            rpaths);
 628
 629         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 630         fib_table_source_count_inc(fib_table, source);
 631     }
 632     else
 633     {
 634         int was_sourced;
 635
 636         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 637         fib_entry_path_add(fib_entry_index, source, flags, rpaths);;
 638
 639         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 640         {
 641             fib_table_source_count_inc(fib_table, source);
 642         }
 643     }
 644
 645     return (fib_entry_index);
 646 }
 647
 648 void
 649 fib_table_entry_path_remove2 (u32 fib_index,
 650                               const fib_prefix_t *prefix,
 651                               fib_source_t source,
 652                               fib_route_path_t *rpaths)
 653 {
 654     /*
 655      * 1 is it present
 656      *   yes => remove source
 657      *    2 - is it still sourced?
 658      *      no => cover walk
 659      */
 660     fib_node_index_t fib_entry_index;
 661     fib_route_path_t *rpath;
 662     fib_table_t *fib_table;
 663
 664     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 665     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 666
 667     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 668     {
 669         /*
 670          * removing an etry that does not exist. i'll allow it.
 671          */
 672     }
 673     else
 674     {
 675         fib_entry_src_flag_t src_flag;
 676         int was_sourced;
 677
 678         /*
 679          * if it's not sourced, then there's nowt to remove
 680          */
 681         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 682         if (!was_sourced)
 683         {
 684             return;
 685         }
 686
 687         /*
 688          * don't nobody go nowhere
 689          */
 690         fib_entry_lock(fib_entry_index);
 691
 692         vec_foreach(rpath, rpaths)
 693         {
 694             fib_entry_flag_t eflags;
 695
 696             eflags = fib_entry_get_flags_for_source(fib_entry_index,
 697                                                     source);
 698             fib_table_route_path_fixup(prefix, &eflags, rpath);
 699         }
 700
 701         src_flag = fib_entry_path_remove(fib_entry_index, source, rpaths);
 702
 703         if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 704         {
 705             /*
 706              * last source gone. remove from the table
 707              */
 708             fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 709
 710             /*
 711              * now the entry is no longer in the table, we can
 712              * inform the entries that it covers to re-calculate their cover
 713              */
 714             fib_entry_cover_change_notify(fib_entry_index,
 715                                           FIB_NODE_INDEX_INVALID);
 716         }
 717         /*
 718          * else
 719          *   still has sources, leave it be.
 720          */
 721         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 722         {
 723             fib_table_source_count_dec(fib_table, source);
 724         }
 725
 726         fib_entry_unlock(fib_entry_index);
 727     }
 728 }
 729
 730 void
 731 fib_table_entry_path_remove (u32 fib_index,
 732                              const fib_prefix_t *prefix,
 733                              fib_source_t source,
 734                              dpo_proto_t next_hop_proto,
 735                              const ip46_address_t *next_hop,
 736                              u32 next_hop_sw_if_index,
 737                              u32 next_hop_fib_index,
 738                              u32 next_hop_weight,
 739                              fib_route_path_flags_t path_flags)
 740 {
 741     /*
 742      * 1 is it present
 743      *   yes => remove source
 744      *    2 - is it still sourced?
 745      *      no => cover walk
 746      */
 747     fib_route_path_t path = {
 748         .frp_proto = next_hop_proto,
 749         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 750         .frp_sw_if_index = next_hop_sw_if_index,
 751         .frp_fib_index = next_hop_fib_index,
 752         .frp_weight = next_hop_weight,
 753         .frp_flags = path_flags,
 754     };
 755     fib_route_path_t *paths = NULL;
 756
 757     vec_add1(paths, path);
 758
 759     fib_table_entry_path_remove2(fib_index, prefix, source, paths);
 760
 761     vec_free(paths);
 762 }
 763
 764 fib_node_index_t
 765 fib_table_entry_update (u32 fib_index,
 766                         const fib_prefix_t *prefix,
 767                         fib_source_t source,
 768                         fib_entry_flag_t flags,
 769                         fib_route_path_t *paths)
 770 {
 771     fib_node_index_t fib_entry_index;
 772     fib_table_t *fib_table;
 773     u32 ii;
 774
 775     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 776     fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);
 777
 778     for (ii = 0; ii < vec_len(paths); ii++)
 779     {
 780         fib_table_route_path_fixup(prefix, &flags, &paths[ii]);
 781     }
 782     /*
 783      * sort the paths provided by the control plane. this means
 784      * the paths and the extension on the entry will be sorted.
 785      */
 786     vec_sort_with_function(paths, fib_route_path_cmp_for_sort);
 787
 788     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 789     {
 790         fib_entry_index = fib_entry_create(fib_index, prefix,
 791                                            source, flags,
 792                                            paths);
 793
 794         fib_table_entry_insert(fib_table, prefix, fib_entry_index);
 795         fib_table_source_count_inc(fib_table, source);
 796     }
 797     else
 798     {
 799         int was_sourced;
 800
 801         was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 802         fib_entry_update(fib_entry_index, source, flags, paths);
 803
 804         if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 805         {
 806             fib_table_source_count_inc(fib_table, source);
 807         }
 808     }
 809
 810     return (fib_entry_index);
 811 }
 812
 813 fib_node_index_t
 814 fib_table_entry_update_one_path (u32 fib_index,
 815                                  const fib_prefix_t *prefix,
 816                                  fib_source_t source,
 817                                  fib_entry_flag_t flags,
 818                                  dpo_proto_t next_hop_proto,
 819                                  const ip46_address_t *next_hop,
 820                                  u32 next_hop_sw_if_index,
 821                                  u32 next_hop_fib_index,
 822                                  u32 next_hop_weight,
 823                                  fib_mpls_label_t *next_hop_labels,
 824                                  fib_route_path_flags_t path_flags)
 825 {
 826     fib_node_index_t fib_entry_index;
 827     fib_route_path_t path = {
 828         .frp_proto = next_hop_proto,
 829         .frp_addr = (NULL == next_hop? zero_addr : *next_hop),
 830         .frp_sw_if_index = next_hop_sw_if_index,
 831         .frp_fib_index = next_hop_fib_index,
 832         .frp_weight = next_hop_weight,
 833         .frp_flags = path_flags,
 834         .frp_label_stack = next_hop_labels,
 835     };
 836     fib_route_path_t *paths = NULL;
 837
 838     vec_add1(paths, path);
 839
 840     fib_entry_index =
 841         fib_table_entry_update(fib_index, prefix, source, flags, paths);
 842
 843     vec_free(paths);
 844
 845     return (fib_entry_index);
 846 }
 847
 848 static void
 849 fib_table_entry_delete_i (u32 fib_index,
 850                           fib_node_index_t fib_entry_index,
 851                           const fib_prefix_t *prefix,
 852                           fib_source_t source)
 853 {
 854     fib_entry_src_flag_t src_flag;
 855     fib_table_t *fib_table;
 856     int was_sourced;
 857
 858     fib_table = fib_table_get(fib_index, prefix->fp_proto);
 859     was_sourced = fib_entry_is_sourced(fib_entry_index, source);
 860
 861     /*
 862      * don't nobody go nowhere
 863      */
 864     fib_entry_lock(fib_entry_index);
 865
 866     src_flag = fib_entry_delete(fib_entry_index, source);
 867
 868     if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
 869     {
 870         /*
 871          * last source gone. remove from the table
 872          */
 873         fib_table_entry_remove(fib_table, prefix, fib_entry_index);
 874
 875         /*
 876          * now the entry is no longer in the table, we can
 877          * inform the entries that it covers to re-calculate their cover
 878          */
 879         fib_entry_cover_change_notify(fib_entry_index,
 880                                       FIB_NODE_INDEX_INVALID);
 881     }
 882     /*
 883      * else
 884      *   still has sources, leave it be.
 885      */
 886     if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
 887     {
 888         fib_table_source_count_dec(fib_table, source);
 889     }
 890
 891     fib_entry_unlock(fib_entry_index);
 892 }
 893
 894 void
 895 fib_table_entry_delete (u32 fib_index,
 896                         const fib_prefix_t *prefix,
 897                         fib_source_t source)
 898 {
 899     fib_node_index_t fib_entry_index;
 900
 901     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 902
 903     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 904     {
 905         /*
 906          * removing an etry that does not exist.
 907          * i'll allow it, but i won't like it.
 908          */
 909         if (0)
 910             clib_warning("%U not in FIB", format_fib_prefix, prefix);
 911     }
 912     else
 913     {
 914         fib_table_entry_delete_i(fib_index, fib_entry_index, prefix, source);
 915     }
 916 }
 917
 918 void
 919 fib_table_entry_delete_index (fib_node_index_t fib_entry_index,
 920                               fib_source_t source)
 921 {
 922     const fib_prefix_t *prefix;
 923
 924     prefix = fib_entry_get_prefix(fib_entry_index);
 925
 926     fib_table_entry_delete_i(fib_entry_get_fib_index(fib_entry_index),
 927                              fib_entry_index, prefix, source);
 928 }
 929
 930 u32
 931 fib_table_entry_get_stats_index (u32 fib_index,
 932                                  const fib_prefix_t *prefix)
 933 {
 934     return (fib_entry_get_stats_index(
 935                 fib_table_lookup_exact_match(fib_index, prefix)));
 936 }
 937
 938 fib_node_index_t
 939 fib_table_entry_local_label_add (u32 fib_index,
 940                                  const fib_prefix_t *prefix,
 941                                  mpls_label_t label)
 942 {
 943     fib_node_index_t fib_entry_index;
 944
 945     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 946
 947     if (FIB_NODE_INDEX_INVALID == fib_entry_index ||
 948         !fib_entry_is_sourced(fib_entry_index, FIB_SOURCE_MPLS))
 949     {
 950         /*
 951          * only source the prefix once. this allows the label change
 952          * operation to work
 953          */
 954         fib_entry_index = fib_table_entry_special_dpo_add(fib_index, prefix,
 955                                                           FIB_SOURCE_MPLS,
 956                                                           FIB_ENTRY_FLAG_NONE,
 957                                                           NULL);
 958     }
 959
 960     fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &label);
 961
 962     return (fib_entry_index);
 963 }
 964
 965 void
 966 fib_table_entry_local_label_remove (u32 fib_index,
 967                                     const fib_prefix_t *prefix,
 968                                     mpls_label_t label)
 969 {
 970     fib_node_index_t fib_entry_index;
 971     const void *data;
 972     mpls_label_t pl;
 973
 974     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 975
 976     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 977         return;
 978
 979     data = fib_entry_get_source_data(fib_entry_index, FIB_SOURCE_MPLS);
 980
 981     if (NULL == data)
 982         return;
 983
 984     pl = *(mpls_label_t*)data;
 985
 986     if (pl != label)
 987         return;
 988
 989     pl = MPLS_LABEL_INVALID;
 990
 991     fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &pl);
 992     fib_table_entry_special_remove(fib_index,
 993                                    prefix,
 994                                    FIB_SOURCE_MPLS);
 995 }
 996
 997 u32
 998 fib_table_get_index_for_sw_if_index (fib_protocol_t proto,
 999                                      u32 sw_if_index)
1000 {
1001     switch (proto)
1002     {
1003     case FIB_PROTOCOL_IP4:
1004         return (ip4_fib_table_get_index_for_sw_if_index(sw_if_index));
1005     case FIB_PROTOCOL_IP6:
1006         return (ip6_fib_table_get_index_for_sw_if_index(sw_if_index));
1007     case FIB_PROTOCOL_MPLS:
1008         return (mpls_fib_table_get_index_for_sw_if_index(sw_if_index));
1009     }
1010     return (~0);
1011 }
1012
1013 flow_hash_config_t
1014 fib_table_get_flow_hash_config (u32 fib_index,
1015                                 fib_protocol_t proto)
1016 {
1017     fib_table_t *fib;
1018
1019     fib = fib_table_get(fib_index, proto);
1020
1021     return (fib->ft_flow_hash_config);
1022 }
1023
1024 flow_hash_config_t
1025 fib_table_get_default_flow_hash_config (fib_protocol_t proto)
1026 {
1027     switch (proto)
1028     {
1029     case FIB_PROTOCOL_IP4:
1030     case FIB_PROTOCOL_IP6:
1031         return (IP_FLOW_HASH_DEFAULT);
1032
1033     case FIB_PROTOCOL_MPLS:
1034         return (MPLS_FLOW_HASH_DEFAULT);
1035     }
1036
1037     ASSERT(0);
1038     return (IP_FLOW_HASH_DEFAULT);
1039 }
1040
1041 /**
1042  * @brief Table set flow hash config context.
1043  */
1044 typedef struct fib_table_set_flow_hash_config_ctx_t_
1045 {
1046     /**
1047      * the flow hash config to set
1048      */
1049     flow_hash_config_t hash_config;
1050 } fib_table_set_flow_hash_config_ctx_t;
1051
1052 static fib_table_walk_rc_t
1053 fib_table_set_flow_hash_config_cb (fib_node_index_t fib_entry_index,
1054                                    void *arg)
1055 {
1056     fib_table_set_flow_hash_config_ctx_t *ctx = arg;
1057
1058     fib_entry_set_flow_hash_config(fib_entry_index, ctx->hash_config);
1059
1060     return (FIB_TABLE_WALK_CONTINUE);
1061 }
1062
1063 void
1064 fib_table_set_flow_hash_config (u32 fib_index,
1065                                 fib_protocol_t proto,
1066                                 flow_hash_config_t hash_config)
1067 {
1068     fib_table_set_flow_hash_config_ctx_t ctx = {
1069         .hash_config = hash_config,
1070     };
1071     fib_table_t *fib;
1072
1073     fib = fib_table_get(fib_index, proto);
1074     fib->ft_flow_hash_config = hash_config;
1075
1076     fib_table_walk(fib_index, proto,
1077                    fib_table_set_flow_hash_config_cb,
1078                    &ctx);
1079 }
1080
1081 u32
1082 fib_table_get_table_id_for_sw_if_index (fib_protocol_t proto,
1083                                         u32 sw_if_index)
1084 {
1085     fib_table_t *fib_table;
1086
1087     fib_table = fib_table_get(fib_table_get_index_for_sw_if_index(
1088                                   proto, sw_if_index),
1089                               proto);
1090
1091     return ((NULL != fib_table ? fib_table->ft_table_id : ~0));
1092 }
1093
1094 u32
1095 fib_table_get_table_id (u32 fib_index,
1096                         fib_protocol_t proto)
1097 {
1098     fib_table_t *fib_table;
1099
1100     fib_table = fib_table_get(fib_index, proto);
1101
1102     return ((NULL != fib_table ? fib_table->ft_table_id : ~0));
1103 }
1104
1105 u32
1106 fib_table_find (fib_protocol_t proto,
1107                 u32 table_id)
1108 {
1109     switch (proto)
1110     {
1111     case FIB_PROTOCOL_IP4:
1112         return (ip4_fib_index_from_table_id(table_id));
1113     case FIB_PROTOCOL_IP6:
1114         return (ip6_fib_index_from_table_id(table_id));
1115     case FIB_PROTOCOL_MPLS:
1116         return (mpls_fib_index_from_table_id(table_id));
1117     }
1118     return (~0);
1119 }
1120
1121 static u32
1122 fib_table_find_or_create_and_lock_i (fib_protocol_t proto,
1123                                      u32 table_id,
1124                                      fib_source_t src,
1125                                      const u8 *name)
1126 {
1127     fib_table_t *fib_table;
1128     fib_node_index_t fi;
1129
1130     switch (proto)
1131     {
1132     case FIB_PROTOCOL_IP4:
1133         fi = ip4_fib_table_find_or_create_and_lock(table_id, src);
1134         break;
1135     case FIB_PROTOCOL_IP6:
1136         fi = ip6_fib_table_find_or_create_and_lock(table_id, src);
1137         break;
1138     case FIB_PROTOCOL_MPLS:
1139         fi = mpls_fib_table_find_or_create_and_lock(table_id, src);
1140         break;
1141     default:
1142         return (~0);
1143     }
1144
1145     fib_table = fib_table_get(fi, proto);
1146
1147     if (NULL == fib_table->ft_desc)
1148     {
1149         if (name && name[0])
1150         {
1151             fib_table->ft_desc = format(NULL, "%s", name);
1152         }
1153         else
1154         {
1155             fib_table->ft_desc = format(NULL, "%U-VRF:%d",
1156                                         format_fib_protocol, proto,
1157                                         table_id);
1158         }
1159     }
1160
1161     return (fi);
1162 }
1163
1164 u32
1165 fib_table_find_or_create_and_lock (fib_protocol_t proto,
1166                                    u32 table_id,
1167                                    fib_source_t src)
1168 {
1169     return (fib_table_find_or_create_and_lock_i(proto, table_id,
1170                                                 src, NULL));
1171 }
1172
1173 u32
1174 fib_table_find_or_create_and_lock_w_name (fib_protocol_t proto,
1175                                           u32 table_id,
1176                                           fib_source_t src,
1177                                           const u8 *name)
1178 {
1179     return (fib_table_find_or_create_and_lock_i(proto, table_id,
1180                                                 src, name));
1181 }
1182
1183 u32
1184 fib_table_create_and_lock (fib_protocol_t proto,
1185                            fib_source_t src,
1186                            const char *const fmt,
1187                            ...)
1188 {
1189     fib_table_t *fib_table;
1190     fib_node_index_t fi;
1191     va_list ap;
1192
1193
1194     switch (proto)
1195     {
1196     case FIB_PROTOCOL_IP4:
1197         fi = ip4_fib_table_create_and_lock(src);
1198         break;
1199     case FIB_PROTOCOL_IP6:
1200         fi = ip6_fib_table_create_and_lock(src, FIB_TABLE_FLAG_NONE, NULL);
1201         break;
1202      case FIB_PROTOCOL_MPLS:
1203         fi = mpls_fib_table_create_and_lock(src);
1204         break;
1205    default:
1206         return (~0);
1207     }
1208
1209     fib_table = fib_table_get(fi, proto);
1210
1211     va_start(ap, fmt);
1212
1213     fib_table->ft_desc = va_format(fib_table->ft_desc, fmt, &ap);
1214
1215     va_end(ap);
1216     return (fi);
1217 }
1218
1219 static void
1220 fib_table_destroy (fib_table_t *fib_table)
1221 {
1222     vec_free(fib_table->ft_desc);
1223
1224     switch (fib_table->ft_proto)
1225     {
1226     case FIB_PROTOCOL_IP4:
1227         ip4_fib_table_destroy(fib_table->ft_index);
1228         break;
1229     case FIB_PROTOCOL_IP6:
1230         ip6_fib_table_destroy(fib_table->ft_index);
1231         break;
1232     case FIB_PROTOCOL_MPLS:
1233         mpls_fib_table_destroy(fib_table->ft_index);
1234         break;
1235     }
1236 }
1237
1238 void
1239 fib_table_walk (u32 fib_index,
1240                 fib_protocol_t proto,
1241                 fib_table_walk_fn_t fn,
1242                 void *ctx)
1243 {
1244     switch (proto)
1245     {
1246     case FIB_PROTOCOL_IP4:
1247         ip4_fib_table_walk(ip4_fib_get(fib_index), fn, ctx);
1248         break;
1249     case FIB_PROTOCOL_IP6:
1250         ip6_fib_table_walk(fib_index, fn, ctx);
1251         break;
1252     case FIB_PROTOCOL_MPLS:
1253         mpls_fib_table_walk(mpls_fib_get(fib_index), fn, ctx);
1254         break;
1255     }
1256 }
1257
1258 void
1259 fib_table_sub_tree_walk (u32 fib_index,
1260                          fib_protocol_t proto,
1261                          const fib_prefix_t *root,
1262                          fib_table_walk_fn_t fn,
1263                          void *ctx)
1264 {
1265     switch (proto)
1266     {
1267     case FIB_PROTOCOL_IP4:
1268         ip4_fib_table_sub_tree_walk(ip4_fib_get(fib_index), root, fn, ctx);
1269         break;
1270     case FIB_PROTOCOL_IP6:
1271         ip6_fib_table_sub_tree_walk(fib_index, root, fn, ctx);
1272         break;
1273     case FIB_PROTOCOL_MPLS:
1274         break;
1275     }
1276 }
1277
1278 static void
1279 fib_table_lock_dec (fib_table_t *fib_table,
1280                     fib_source_t source)
1281 {
1282     vec_validate(fib_table->ft_locks, source);
1283
1284     fib_table->ft_locks[source]--;
1285     fib_table->ft_total_locks--;
1286 }
1287
1288 static void
1289 fib_table_lock_inc (fib_table_t *fib_table,
1290                     fib_source_t source)
1291 {
1292     vec_validate(fib_table->ft_locks, source);
1293
1294     ASSERT(fib_table->ft_total_locks < (0xffffffff - 1));
1295     fib_table->ft_locks[source]++;
1296     fib_table->ft_total_locks++;
1297 }
1298
1299 void
1300 fib_table_unlock (u32 fib_index,
1301                   fib_protocol_t proto,
1302                   fib_source_t source)
1303 {
1304     fib_table_t *fib_table;
1305
1306     fib_table = fib_table_get(fib_index, proto);
1307     fib_table_lock_dec(fib_table, source);
1308
1309     if (0 == fib_table->ft_total_locks)
1310     {
1311         /*
1312          * no more locak from any source - kill it
1313          */
1314         fib_table_destroy(fib_table);
1315     }
1316 }
1317
1318 void
1319 fib_table_lock (u32 fib_index,
1320                 fib_protocol_t proto,
1321                 fib_source_t source)
1322 {
1323     fib_table_t *fib_table;
1324
1325     fib_table = fib_table_get(fib_index, proto);
1326
1327     fib_table_lock_inc(fib_table, source);
1328 }
1329
1330 u32
1331 fib_table_get_num_entries (u32 fib_index,
1332                            fib_protocol_t proto,
1333                            fib_source_t source)
1334 {
1335     fib_table_t *fib_table;
1336
1337     fib_table = fib_table_get(fib_index, proto);
1338
1339     return (fib_table->ft_src_route_counts[source]);
1340 }
1341
1342 u8*
1343 format_fib_table_name (u8* s, va_list* ap)
1344 {
1345     fib_node_index_t fib_index = va_arg(*ap, fib_node_index_t);
1346     fib_protocol_t proto = va_arg(*ap, int); // int promotion
1347     fib_table_t *fib_table;
1348
1349     fib_table = fib_table_get(fib_index, proto);
1350
1351     s = format(s, "%v", fib_table->ft_desc);
1352
1353     return (s);
1354 }
1355
1356 u8*
1357 format_fib_table_flags (u8 *s, va_list *args)
1358 {
1359     fib_table_flags_t flags = va_arg(*args, int);
1360     fib_table_attribute_t attr;
1361
1362     if (!flags)
1363     {
1364         return format(s, "none");
1365     }
1366
1367     FOR_EACH_FIB_TABLE_ATTRIBUTE(attr) {
1368         if (1 << attr & flags) {
1369             s = format(s, "%s", fib_table_flags_strings[attr]);
1370         }
1371     }
1372
1373     return (s);
1374 }
1375
1376 /**
1377  * @brief Table flush context. Store the indicies of matching FIB entries
1378  * that need to be removed.
1379  */
1380 typedef struct fib_table_flush_ctx_t_
1381 {
1382     /**
1383      * The list of entries to flush
1384      */
1385     fib_node_index_t *ftf_entries;
1386
1387     /**
1388      * The source we are flushing
1389      */
1390     fib_source_t ftf_source;
1391 } fib_table_flush_ctx_t;
1392
1393 static fib_table_walk_rc_t
1394 fib_table_flush_cb (fib_node_index_t fib_entry_index,
1395                     void *arg)
1396 {
1397     fib_table_flush_ctx_t *ctx = arg;
1398
1399     if (fib_entry_is_sourced(fib_entry_index, ctx->ftf_source))
1400     {
1401         vec_add1(ctx->ftf_entries, fib_entry_index);
1402     }
1403     return (FIB_TABLE_WALK_CONTINUE);
1404 }
1405
1406 void
1407 fib_table_flush (u32 fib_index,
1408                  fib_protocol_t proto,
1409                  fib_source_t source)
1410 {
1411     fib_node_index_t *fib_entry_index;
1412     fib_table_flush_ctx_t ctx = {
1413         .ftf_entries = NULL,
1414         .ftf_source = source,
1415     };
1416
1417     fib_table_walk(fib_index, proto,
1418                    fib_table_flush_cb,
1419                    &ctx);
1420
1421     vec_foreach(fib_entry_index, ctx.ftf_entries)
1422     {
1423         fib_table_entry_delete_index(*fib_entry_index, source);
1424     }
1425
1426     vec_free(ctx.ftf_entries);
1427 }
1428
1429 static fib_table_walk_rc_t
1430 fib_table_mark_cb (fib_node_index_t fib_entry_index,
1431                    void *arg)
1432 {
1433     fib_table_flush_ctx_t *ctx = arg;
1434
1435     if (fib_entry_is_sourced(fib_entry_index, ctx->ftf_source))
1436     {
1437         fib_entry_mark(fib_entry_index, ctx->ftf_source);
1438     }
1439     return (FIB_TABLE_WALK_CONTINUE);
1440 }
1441
1442 void
1443 fib_table_mark (u32 fib_index,
1444                 fib_protocol_t proto,
1445                 fib_source_t source)
1446 {
1447     fib_table_flush_ctx_t ctx = {
1448         .ftf_source = source,
1449     };
1450     fib_table_t *fib_table;
1451
1452     fib_table = fib_table_get(fib_index, proto);
1453
1454     fib_table->ft_epoch++;
1455     fib_table->ft_flags |= FIB_TABLE_FLAG_RESYNC;
1456
1457     fib_table_walk(fib_index, proto,
1458                    fib_table_mark_cb,
1459                    &ctx);
1460 }
1461
1462 static fib_table_walk_rc_t
1463 fib_table_sweep_cb (fib_node_index_t fib_entry_index,
1464                     void *arg)
1465 {
1466     fib_table_flush_ctx_t *ctx = arg;
1467
1468     if (fib_entry_is_marked(fib_entry_index, ctx->ftf_source))
1469     {
1470         vec_add1(ctx->ftf_entries, fib_entry_index);
1471     }
1472     return (FIB_TABLE_WALK_CONTINUE);
1473 }
1474
1475 void
1476 fib_table_sweep (u32 fib_index,
1477                  fib_protocol_t proto,
1478                  fib_source_t source)
1479 {
1480     fib_table_flush_ctx_t ctx = {
1481         .ftf_source = source,
1482     };
1483     fib_node_index_t *fib_entry_index;
1484     fib_table_t *fib_table;
1485
1486     fib_table = fib_table_get(fib_index, proto);
1487
1488     fib_table->ft_flags &= ~FIB_TABLE_FLAG_RESYNC;
1489
1490     fib_table_walk(fib_index, proto,
1491                    fib_table_sweep_cb,
1492                    &ctx);
1493
1494     vec_foreach(fib_entry_index, ctx.ftf_entries)
1495     {
1496         fib_table_entry_delete_index(*fib_entry_index, source);
1497     }
1498
1499     vec_free(ctx.ftf_entries);
1500 }
1501
1502 u8 *
1503 format_fib_table_memory (u8 *s, va_list *args)
1504 {
1505     s = format(s, "%U", format_ip4_fib_table_memory);
1506     s = format(s, "%U", format_ip6_fib_table_memory);
1507     s = format(s, "%U", format_mpls_fib_table_memory);
1508
1509     return (s);
1510 }