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