src/vnet/fib/fib_table.c

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