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 fib_node_index_t
 889 fib_table_entry_local_label_add (u32 fib_index,
 890                                  const fib_prefix_t *prefix,
 891                                  mpls_label_t label)
 892 {
 893     fib_node_index_t fib_entry_index;
 894
 895     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 896
 897     if (FIB_NODE_INDEX_INVALID == fib_entry_index ||
 898         !fib_entry_is_sourced(fib_entry_index, FIB_SOURCE_MPLS))
 899     {
 900         /*
 901          * only source the prefix once. this allows the label change
 902          * operation to work
 903          */
 904         fib_entry_index = fib_table_entry_special_dpo_add(fib_index, prefix,
 905                                                           FIB_SOURCE_MPLS,
 906                                                           FIB_ENTRY_FLAG_NONE,
 907                                                           NULL);
 908     }
 909
 910     fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &label);
 911
 912     return (fib_entry_index);
 913 }
 914
 915 void
 916 fib_table_entry_local_label_remove (u32 fib_index,
 917                                     const fib_prefix_t *prefix,
 918                                     mpls_label_t label)
 919 {
 920     fib_node_index_t fib_entry_index;
 921     const void *data;
 922     mpls_label_t pl;
 923
 924     fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);
 925
 926     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
 927         return;
 928
 929     data = fib_entry_get_source_data(fib_entry_index, FIB_SOURCE_MPLS);
 930
 931     if (NULL == data)
 932         return;
 933
 934     pl = *(mpls_label_t*)data;
 935
 936     if (pl != label)
 937         return;
 938
 939     pl = MPLS_LABEL_INVALID;
 940
 941     fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &pl);
 942     fib_table_entry_special_remove(fib_index,
 943                                    prefix,
 944                                    FIB_SOURCE_MPLS);
 945 }
 946
 947 u32
 948 fib_table_get_index_for_sw_if_index (fib_protocol_t proto,
 949                                      u32 sw_if_index)
 950 {
 951     switch (proto)
 952     {
 953     case FIB_PROTOCOL_IP4:
 954         return (ip4_fib_table_get_index_for_sw_if_index(sw_if_index));
 955     case FIB_PROTOCOL_IP6:
 956         return (ip6_fib_table_get_index_for_sw_if_index(sw_if_index));
 957     case FIB_PROTOCOL_MPLS:
 958         return (mpls_fib_table_get_index_for_sw_if_index(sw_if_index));
 959     }
 960     return (~0);
 961 }
 962
 963 flow_hash_config_t
 964 fib_table_get_flow_hash_config (u32 fib_index,
 965                                 fib_protocol_t proto)
 966 {
 967     fib_table_t *fib;
 968
 969     fib = fib_table_get(fib_index, proto);
 970
 971     return (fib->ft_flow_hash_config);
 972 }
 973
 974 flow_hash_config_t
 975 fib_table_get_default_flow_hash_config (fib_protocol_t proto)
 976 {
 977     switch (proto)
 978     {
 979     case FIB_PROTOCOL_IP4:
 980     case FIB_PROTOCOL_IP6:
 981         return (IP_FLOW_HASH_DEFAULT);
 982
 983     case FIB_PROTOCOL_MPLS:
 984         return (MPLS_FLOW_HASH_DEFAULT);
 985     }
 986
 987     ASSERT(0);
 988     return (IP_FLOW_HASH_DEFAULT);
 989 }
 990
 991 /**
 992  * @brief Table set flow hash config context.
 993  */
 994 typedef struct fib_table_set_flow_hash_config_ctx_t_
 995 {
 996     /**
 997      * the flow hash config to set
 998      */
 999     flow_hash_config_t hash_config;
1000 } fib_table_set_flow_hash_config_ctx_t;
1001
1002 static fib_table_walk_rc_t
1003 fib_table_set_flow_hash_config_cb (fib_node_index_t fib_entry_index,
1004                                    void *arg)
1005 {
1006     fib_table_set_flow_hash_config_ctx_t *ctx = arg;
1007
1008     fib_entry_set_flow_hash_config(fib_entry_index, ctx->hash_config);
1009
1010     return (FIB_TABLE_WALK_CONTINUE);
1011 }
1012
1013 void
1014 fib_table_set_flow_hash_config (u32 fib_index,
1015                                 fib_protocol_t proto,
1016                                 flow_hash_config_t hash_config)
1017 {
1018     fib_table_set_flow_hash_config_ctx_t ctx = {
1019         .hash_config = hash_config,
1020     };
1021     fib_table_t *fib;
1022
1023     fib = fib_table_get(fib_index, proto);
1024     fib->ft_flow_hash_config = hash_config;
1025
1026     fib_table_walk(fib_index, proto,
1027                    fib_table_set_flow_hash_config_cb,
1028                    &ctx);
1029 }
1030
1031 u32
1032 fib_table_get_table_id_for_sw_if_index (fib_protocol_t proto,
1033                                         u32 sw_if_index)
1034 {
1035     fib_table_t *fib_table;
1036
1037     fib_table = fib_table_get(fib_table_get_index_for_sw_if_index(
1038                                   proto, sw_if_index),
1039                               proto);
1040
1041     return ((NULL != fib_table ? fib_table->ft_table_id : ~0));
1042 }
1043
1044 u32
1045 fib_table_get_table_id (u32 fib_index,
1046                         fib_protocol_t proto)
1047 {
1048     fib_table_t *fib_table;
1049
1050     fib_table = fib_table_get(fib_index, proto);
1051
1052     return ((NULL != fib_table ? fib_table->ft_table_id : ~0));
1053 }
1054
1055 u32
1056 fib_table_find (fib_protocol_t proto,
1057                 u32 table_id)
1058 {
1059     switch (proto)
1060     {
1061     case FIB_PROTOCOL_IP4:
1062         return (ip4_fib_index_from_table_id(table_id));
1063     case FIB_PROTOCOL_IP6:
1064         return (ip6_fib_index_from_table_id(table_id));
1065     case FIB_PROTOCOL_MPLS:
1066         return (mpls_fib_index_from_table_id(table_id));
1067     }
1068     return (~0);
1069 }
1070
1071 static u32
1072 fib_table_find_or_create_and_lock_i (fib_protocol_t proto,
1073                                      u32 table_id,
1074                                      fib_source_t src,
1075                                      const u8 *name)
1076 {
1077     fib_table_t *fib_table;
1078     fib_node_index_t fi;
1079
1080     switch (proto)
1081     {
1082     case FIB_PROTOCOL_IP4:
1083         fi = ip4_fib_table_find_or_create_and_lock(table_id, src);
1084         break;
1085     case FIB_PROTOCOL_IP6:
1086         fi = ip6_fib_table_find_or_create_and_lock(table_id, src);
1087         break;
1088     case FIB_PROTOCOL_MPLS:
1089         fi = mpls_fib_table_find_or_create_and_lock(table_id, src);
1090         break;
1091     default:
1092         return (~0);
1093     }
1094
1095     fib_table = fib_table_get(fi, proto);
1096
1097     if (NULL == fib_table->ft_desc)
1098     {
1099         if (name && name[0])
1100         {
1101             fib_table->ft_desc = format(NULL, "%s", name);
1102         }
1103         else
1104         {
1105             fib_table->ft_desc = format(NULL, "%U-VRF:%d",
1106                                         format_fib_protocol, proto,
1107                                         table_id);
1108         }
1109     }
1110
1111     return (fi);
1112 }
1113
1114 u32
1115 fib_table_find_or_create_and_lock (fib_protocol_t proto,
1116                                    u32 table_id,
1117                                    fib_source_t src)
1118 {
1119     return (fib_table_find_or_create_and_lock_i(proto, table_id,
1120                                                 src, NULL));
1121 }
1122
1123 u32
1124 fib_table_find_or_create_and_lock_w_name (fib_protocol_t proto,
1125                                           u32 table_id,
1126                                           fib_source_t src,
1127                                           const u8 *name)
1128 {
1129     return (fib_table_find_or_create_and_lock_i(proto, table_id,
1130                                                 src, name));
1131 }
1132
1133 u32
1134 fib_table_create_and_lock (fib_protocol_t proto,
1135                            fib_source_t src,
1136                            const char *const fmt,
1137                            ...)
1138 {
1139     fib_table_t *fib_table;
1140     fib_node_index_t fi;
1141     va_list ap;
1142
1143     va_start(ap, fmt);
1144
1145     switch (proto)
1146     {
1147     case FIB_PROTOCOL_IP4:
1148         fi = ip4_fib_table_create_and_lock(src);
1149         break;
1150     case FIB_PROTOCOL_IP6:
1151         fi = ip6_fib_table_create_and_lock(src, FIB_TABLE_FLAG_NONE, NULL);
1152         break;
1153      case FIB_PROTOCOL_MPLS:
1154         fi = mpls_fib_table_create_and_lock(src);
1155         break;
1156    default:
1157         return (~0);
1158     }
1159
1160     fib_table = fib_table_get(fi, proto);
1161
1162     fib_table->ft_desc = va_format(fib_table->ft_desc, fmt, &ap);
1163
1164     va_end(ap);
1165     return (fi);
1166 }
1167
1168 static void
1169 fib_table_destroy (fib_table_t *fib_table)
1170 {
1171     vec_free(fib_table->ft_desc);
1172
1173     switch (fib_table->ft_proto)
1174     {
1175     case FIB_PROTOCOL_IP4:
1176         ip4_fib_table_destroy(fib_table->ft_index);
1177         break;
1178     case FIB_PROTOCOL_IP6:
1179         ip6_fib_table_destroy(fib_table->ft_index);
1180         break;
1181     case FIB_PROTOCOL_MPLS:
1182         mpls_fib_table_destroy(fib_table->ft_index);
1183         break;
1184     }
1185 }
1186
1187 void
1188 fib_table_walk (u32 fib_index,
1189                 fib_protocol_t proto,
1190                 fib_table_walk_fn_t fn,
1191                 void *ctx)
1192 {
1193     switch (proto)
1194     {
1195     case FIB_PROTOCOL_IP4:
1196         ip4_fib_table_walk(ip4_fib_get(fib_index), fn, ctx);
1197         break;
1198     case FIB_PROTOCOL_IP6:
1199         ip6_fib_table_walk(fib_index, fn, ctx);
1200         break;
1201     case FIB_PROTOCOL_MPLS:
1202         mpls_fib_table_walk(mpls_fib_get(fib_index), fn, ctx);
1203         break;
1204     }
1205 }
1206
1207 void
1208 fib_table_sub_tree_walk (u32 fib_index,
1209                          fib_protocol_t proto,
1210                          const fib_prefix_t *root,
1211                          fib_table_walk_fn_t fn,
1212                          void *ctx)
1213 {
1214     switch (proto)
1215     {
1216     case FIB_PROTOCOL_IP4:
1217         ip4_fib_table_sub_tree_walk(ip4_fib_get(fib_index), root, fn, ctx);
1218         break;
1219     case FIB_PROTOCOL_IP6:
1220         ip6_fib_table_sub_tree_walk(fib_index, root, fn, ctx);
1221         break;
1222     case FIB_PROTOCOL_MPLS:
1223         break;
1224     }
1225 }
1226
1227 void
1228 fib_table_unlock (u32 fib_index,
1229                   fib_protocol_t proto,
1230                   fib_source_t source)
1231 {
1232     fib_table_t *fib_table;
1233
1234     fib_table = fib_table_get(fib_index, proto);
1235     fib_table->ft_locks[source]--;
1236     fib_table->ft_locks[FIB_TABLE_TOTAL_LOCKS]--;
1237
1238     if (0 == fib_table->ft_locks[source])
1239     {
1240         /*
1241          * The source no longer needs the table. flush any routes
1242          * from it just in case
1243          */
1244         fib_table_flush(fib_index, proto, source);
1245     }
1246
1247     if (0 == fib_table->ft_locks[FIB_TABLE_TOTAL_LOCKS])
1248     {
1249         /*
1250          * no more locak from any source - kill it
1251          */
1252         fib_table_destroy(fib_table);
1253     }
1254 }
1255
1256 void
1257 fib_table_lock (u32 fib_index,
1258                 fib_protocol_t proto,
1259                 fib_source_t source)
1260 {
1261     fib_table_t *fib_table;
1262
1263     fib_table = fib_table_get(fib_index, proto);
1264     fib_table->ft_locks[source]++;
1265     fib_table->ft_locks[FIB_TABLE_TOTAL_LOCKS]++;
1266 }
1267
1268 u32
1269 fib_table_get_num_entries (u32 fib_index,
1270                            fib_protocol_t proto,
1271                            fib_source_t source)
1272 {
1273     fib_table_t *fib_table;
1274
1275     fib_table = fib_table_get(fib_index, proto);
1276
1277     return (fib_table->ft_src_route_counts[source]);
1278 }
1279
1280 u8*
1281 format_fib_table_name (u8* s, va_list* ap)
1282 {
1283     fib_node_index_t fib_index = va_arg(*ap, fib_node_index_t);
1284     fib_protocol_t proto = va_arg(*ap, int); // int promotion
1285     fib_table_t *fib_table;
1286
1287     fib_table = fib_table_get(fib_index, proto);
1288
1289     s = format(s, "%v", fib_table->ft_desc);
1290
1291     return (s);
1292 }
1293
1294 /**
1295  * @brief Table flush context. Store the indicies of matching FIB entries
1296  * that need to be removed.
1297  */
1298 typedef struct fib_table_flush_ctx_t_
1299 {
1300     /**
1301      * The list of entries to flush
1302      */
1303     fib_node_index_t *ftf_entries;
1304
1305     /**
1306      * The source we are flushing
1307      */
1308     fib_source_t ftf_source;
1309 } fib_table_flush_ctx_t;
1310
1311 static fib_table_walk_rc_t
1312 fib_table_flush_cb (fib_node_index_t fib_entry_index,
1313                     void *arg)
1314 {
1315     fib_table_flush_ctx_t *ctx = arg;
1316
1317     if (fib_entry_is_sourced(fib_entry_index, ctx->ftf_source))
1318     {
1319         vec_add1(ctx->ftf_entries, fib_entry_index);
1320     }
1321     return (FIB_TABLE_WALK_CONTINUE);
1322 }
1323
1324
1325 void
1326 fib_table_flush (u32 fib_index,
1327                  fib_protocol_t proto,
1328                  fib_source_t source)
1329 {
1330     fib_node_index_t *fib_entry_index;
1331     fib_table_flush_ctx_t ctx = {
1332         .ftf_entries = NULL,
1333         .ftf_source = source,
1334     };
1335
1336     fib_table_walk(fib_index, proto,
1337                    fib_table_flush_cb,
1338                    &ctx);
1339
1340     vec_foreach(fib_entry_index, ctx.ftf_entries)
1341     {
1342         fib_table_entry_delete_index(*fib_entry_index, source);
1343     }
1344
1345     vec_free(ctx.ftf_entries);
1346 }
1347
1348 u8 *
1349 format_fib_table_memory (u8 *s, va_list *args)
1350 {
1351     s = format(s, "%U", format_ip4_fib_table_memory);
1352     s = format(s, "%U", format_ip6_fib_table_memory);
1353     s = format(s, "%U", format_mpls_fib_table_memory);
1354
1355     return (s);
1356 }