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