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