src/vnet/fib/fib_attached_export.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 <vnet/fib/fib_entry.h>
  17 #include <vnet/fib/fib_table.h>
  18
  19 #include <vnet/fib/fib_attached_export.h>
  20 #include <vnet/fib/fib_entry_cover.h>
  21 #include <vnet/fib/fib_entry_src.h>
  22 #include <vnet/fib/fib_entry_delegate.h>
  23
  24 /**
  25  * A description of the need to import routes from the export table
  26  */
  27 typedef struct fib_ae_import_t_
  28 {
  29     /**
  30      * The entry in the epxort table that this importer
  31      * is importing covereds from
  32      */
  33     fib_node_index_t faei_export_entry;
  34
  35     /**
  36      * The attached entry in the import table
  37      */
  38     fib_node_index_t faei_import_entry;
  39     /**
  40      * the sibling index on the cover
  41      */
  42     u32 faei_export_sibling;
  43
  44     /**
  45      * The index of the exporter tracker. Not set if the
  46      * export entry is not valid for export
  47      */
  48     fib_node_index_t faei_exporter;
  49
  50     /**
  51      * A vector/list of imported entry indicies
  52      */
  53     fib_node_index_t *faei_importeds;
  54
  55     /**
  56      * The FIB index and prefix we are tracking
  57      */
  58     fib_node_index_t faei_export_fib;
  59     fib_prefix_t faei_prefix;
  60
  61     /**
  62      * The FIB index we are importing into
  63      */
  64     fib_node_index_t faei_import_fib;
  65 } fib_ae_import_t;
  66
  67 /**
  68  * A description of the need to export routes to one or more export tables
  69  */
  70 typedef struct fib_ae_export_t_ {
  71     /**
  72      * The vector/list of import tracker indicies
  73      */
  74     fib_node_index_t *faee_importers;
  75
  76     /**
  77      * THe connected entry this export is acting on behalf of
  78      */
  79     fib_node_index_t faee_ei;
  80
  81     /**
  82      * Reference counting locks
  83      */
  84     u32 faee_locks;
  85 } fib_ae_export_t;
  86
  87 /*
  88  * memory pools for the importers and exportes
  89  */
  90 static fib_ae_import_t *fib_ae_import_pool;
  91 static fib_ae_export_t *fib_ae_export_pool;
  92
  93 static fib_ae_export_t *
  94 fib_entry_ae_add_or_lock (fib_node_index_t connected)
  95 {
  96     fib_entry_delegate_t *fed;
  97     fib_ae_export_t *export;
  98     fib_entry_t *entry;
  99
 100     entry = fib_entry_get(connected);
 101     fed = fib_entry_delegate_get(entry,
 102                                  FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 103
 104     if (NULL == fed)
 105     {
 106         fed = fib_entry_delegate_find_or_add(entry,
 107                                              FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 108         pool_get(fib_ae_export_pool, export);
 109         memset(export, 0, sizeof(*export));
 110
 111         fed->fd_index = (export - fib_ae_export_pool);
 112         export->faee_ei = connected;
 113     }
 114     else
 115     {
 116         export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
 117     }
 118
 119     export->faee_locks++;
 120
 121     return (export);
 122 }
 123
 124 static void
 125 fib_entry_import_remove (fib_ae_import_t *import,
 126                          fib_node_index_t entry_index)
 127 {
 128     fib_prefix_t prefix;
 129     u32 index;
 130
 131     /*
 132      * find the index in the vector of the entry we are removing
 133      */
 134     index = vec_search(import->faei_importeds, entry_index);
 135
 136     if (index < vec_len(import->faei_importeds))
 137     {
 138         /*
 139          * this is an entry that was previsouly imported
 140          */
 141         fib_entry_get_prefix(entry_index, &prefix);
 142
 143         fib_table_entry_special_remove(import->faei_import_fib,
 144                                        &prefix,
 145                                        FIB_SOURCE_AE);
 146
 147         fib_entry_unlock(entry_index);
 148         vec_del1(import->faei_importeds, index);
 149     }
 150 }
 151
 152 static void
 153 fib_entry_import_add (fib_ae_import_t *import,
 154                       fib_node_index_t entry_index)
 155 {
 156     fib_node_index_t *existing;
 157     fib_prefix_t prefix;
 158
 159     /*
 160      * ensure we only add the exported entry once, since
 161      * sourcing prefixes in the table is reference counted
 162      */
 163     vec_foreach(existing, import->faei_importeds)
 164     {
 165         if (*existing == entry_index)
 166         {
 167             return;
 168         }
 169     }
 170
 171     /*
 172      * this is the first time this export entry has been imported
 173      * Add it to the import FIB and to the list of importeds
 174      */
 175     fib_entry_get_prefix(entry_index, &prefix);
 176
 177     /*
 178      * don't import entries that have the same prefix the import entry
 179      */
 180     if (0 != fib_prefix_cmp(&prefix,
 181                             &import->faei_prefix))
 182     {
 183         const dpo_id_t *dpo;
 184
 185         dpo = fib_entry_contribute_ip_forwarding(entry_index);
 186
 187         if (dpo_id_is_valid(dpo))
 188         {
 189             fib_table_entry_special_dpo_add(import->faei_import_fib,
 190                                             &prefix,
 191                                             FIB_SOURCE_AE,
 192                                             (fib_entry_get_flags(entry_index) |
 193                                              FIB_ENTRY_FLAG_EXCLUSIVE),
 194                                             load_balance_get_bucket(dpo->dpoi_index, 0));
 195
 196             fib_entry_lock(entry_index);
 197             vec_add1(import->faei_importeds, entry_index);
 198         }
 199         /*
 200          * else
 201          *   the entry currently has no valid forwarding. when it
 202          * does it will export itself
 203          */
 204     }
 205 }
 206
 207 /**
 208  * Call back when walking a connected prefix's covered prefixes for import
 209  */
 210 static int
 211 fib_entry_covered_walk_import (fib_entry_t *cover,
 212                                fib_node_index_t covered,
 213                                void *ctx)
 214 {
 215     fib_ae_import_t *import = ctx;
 216
 217     fib_entry_import_add(import, covered);
 218
 219     return (0);
 220 }
 221
 222 /*
 223  * fib_entry_ae_import_add
 224  *
 225  * Add an importer to a connected entry
 226  */
 227 static void
 228 fib_ae_export_import_add (fib_ae_export_t *export,
 229                           fib_ae_import_t *import)
 230 {
 231     fib_entry_t *entry;
 232
 233     import->faei_exporter = (export - fib_ae_export_pool);
 234     entry = fib_entry_get(export->faee_ei);
 235
 236     fib_entry_cover_walk(entry,
 237                          fib_entry_covered_walk_import,
 238                          import);
 239 }
 240
 241 void
 242 fib_attached_export_import (fib_entry_t *fib_entry,
 243                             fib_node_index_t export_fib)
 244 {
 245     fib_entry_delegate_t *fed;
 246     fib_ae_import_t *import;
 247     fib_node_index_t fei;
 248
 249     /*
 250      * save index for later post-realloc retreival
 251      */
 252     fei = fib_entry_get_index(fib_entry);
 253
 254     pool_get(fib_ae_import_pool, import);
 255
 256     import->faei_import_fib = fib_entry->fe_fib_index;
 257     import->faei_export_fib = export_fib;
 258     import->faei_prefix = fib_entry->fe_prefix;
 259     import->faei_import_entry = fib_entry_get_index(fib_entry);
 260     import->faei_export_sibling = ~0;
 261
 262     /*
 263      * do an exact match in the export table
 264      */
 265     import->faei_export_entry =
 266         fib_table_lookup_exact_match(import->faei_export_fib,
 267                                      &import->faei_prefix);
 268
 269     if (FIB_NODE_INDEX_INVALID == import->faei_export_entry)
 270     {
 271         /*
 272          * no exact matching entry in the export table. can't be good.
 273          * track the next best thing
 274          */
 275         import->faei_export_entry =
 276             fib_table_lookup(import->faei_export_fib,
 277                              &import->faei_prefix);
 278         import->faei_exporter = FIB_NODE_INDEX_INVALID;
 279     }
 280     else
 281     {
 282         /*
 283          * found the entry in the export table. import the
 284          * the prefixes that it covers.
 285          * only if the prefix found in the export FIB really is
 286          * attached do we want to import its covered
 287          */
 288         if (FIB_ENTRY_FLAG_ATTACHED &
 289             fib_entry_get_flags_i(fib_entry_get(import->faei_export_entry)))
 290         {
 291             fib_ae_export_t *export;
 292
 293             export = fib_entry_ae_add_or_lock(import->faei_export_entry);
 294             vec_add1(export->faee_importers, (import - fib_ae_import_pool));
 295             fib_ae_export_import_add(export, import);
 296         }
 297     }
 298
 299     /*
 300      * track the entry in the export table so we can update appropriately
 301      * when it changes.
 302      * Exporting prefixes will have allocated new fib_entry_t objects, so the pool
 303      * may have realloc'd.
 304      */
 305     fib_entry = fib_entry_get(fei);
 306     import->faei_export_sibling =
 307         fib_entry_cover_track(fib_entry_get(import->faei_export_entry), fei);
 308
 309     fed = fib_entry_delegate_find_or_add(fib_entry,
 310                                          FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 311     fed->fd_index = (import - fib_ae_import_pool);
 312 }
 313
 314 /**
 315  * \brief All the imported entries need to be pruged
 316  */
 317 void
 318 fib_attached_export_purge (fib_entry_t *fib_entry)
 319 {
 320     fib_entry_delegate_t *fed;
 321
 322     fed = fib_entry_delegate_get(fib_entry,
 323                                  FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 324
 325     if (NULL != fed)
 326     {
 327         fib_node_index_t *import_index;
 328         fib_entry_t *export_entry;
 329         fib_ae_import_t *import;
 330         fib_ae_export_t *export;
 331
 332         import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
 333
 334         /*
 335          * remove each imported entry
 336          */
 337         vec_foreach(import_index, import->faei_importeds)
 338         {
 339             fib_prefix_t prefix;
 340
 341             fib_entry_get_prefix(*import_index, &prefix);
 342
 343             fib_table_entry_delete(import->faei_import_fib,
 344                                    &prefix,
 345                                    FIB_SOURCE_AE);
 346             fib_entry_unlock(*import_index);
 347         }
 348         vec_free(import->faei_importeds);
 349
 350         /*
 351          * stop tracking the export entry
 352          */
 353         if (~0 != import->faei_export_sibling)
 354         {
 355             fib_entry_cover_untrack(fib_entry_get(import->faei_export_entry),
 356                                     import->faei_export_sibling);
 357         }
 358         import->faei_export_sibling = ~0;
 359
 360         /*
 361          * remove this import tracker from the export's list,
 362          * if it is attached to one. It won't be in the case the tracked
 363          * export entry is not an attached exact match.
 364          */
 365         if (FIB_NODE_INDEX_INVALID != import->faei_exporter)
 366         {
 367             fib_entry_delegate_t *fed;
 368
 369             export_entry = fib_entry_get(import->faei_export_entry);
 370
 371             fed = fib_entry_delegate_get(export_entry,
 372                                          FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 373             ASSERT(NULL != fed);
 374
 375             export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
 376
 377             u32 index = vec_search(export->faee_importers,
 378                                    (import - fib_ae_import_pool));
 379
 380             ASSERT(index < vec_len(export->faee_importers));
 381             vec_del1(export->faee_importers, index);
 382
 383             /*
 384              * free the exporter if there are no longer importers
 385              */
 386             if (0 == --export->faee_locks)
 387             {
 388                 pool_put(fib_ae_export_pool, export);
 389                 fib_entry_delegate_remove(export_entry,
 390                                           FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 391             }
 392         }
 393
 394         /*
 395          * free the import tracker
 396          */
 397         pool_put(fib_ae_import_pool, import);
 398         fib_entry_delegate_remove(fib_entry,
 399                                   FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 400     }
 401 }
 402
 403 void
 404 fib_attached_export_covered_added (fib_entry_t *cover,
 405                                    fib_node_index_t covered)
 406 {
 407     fib_entry_delegate_t *fed;
 408
 409     fed = fib_entry_delegate_get(cover,
 410                                  FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 411
 412     if (NULL != fed)
 413     {
 414         /*
 415          * the covering prefix is exporting to other tables
 416          */
 417         fib_node_index_t *import_index;
 418         fib_ae_import_t *import;
 419         fib_ae_export_t *export;
 420
 421         export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
 422
 423         /*
 424          * export the covered entry to each of the importers
 425          */
 426         vec_foreach(import_index, export->faee_importers)
 427         {
 428             import = pool_elt_at_index(fib_ae_import_pool, *import_index);
 429
 430             fib_entry_import_add(import, covered);
 431         }
 432     }
 433 }
 434
 435 void
 436 fib_attached_export_covered_removed (fib_entry_t *cover,
 437                                      fib_node_index_t covered)
 438 {
 439     fib_entry_delegate_t *fed;
 440
 441     fed = fib_entry_delegate_get(cover,
 442                                  FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 443
 444     if (NULL != fed)
 445     {
 446         /*
 447          * the covering prefix is exporting to other tables
 448          */
 449         fib_node_index_t *import_index;
 450         fib_ae_import_t *import;
 451         fib_ae_export_t *export;
 452
 453         export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
 454
 455         /*
 456          * remove the covered entry from each of the importers
 457          */
 458         vec_foreach(import_index, export->faee_importers)
 459         {
 460             import = pool_elt_at_index(fib_ae_import_pool, *import_index);
 461
 462             fib_entry_import_remove(import, covered);
 463         }
 464     }
 465 }
 466
 467 static void
 468 fib_attached_export_cover_modified_i (fib_entry_t *fib_entry)
 469 {
 470     fib_entry_delegate_t *fed;
 471
 472     fed = fib_entry_delegate_get(fib_entry,
 473                                  FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 474
 475     if (NULL != fed)
 476     {
 477         fib_ae_import_t *import;
 478         u32 export_fib;
 479
 480         /*
 481          * safe the temporaries we need from the existing import
 482          * since it will be toast after the purge.
 483          */
 484         import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
 485         export_fib = import->faei_export_fib;
 486
 487         /*
 488          * keep it simple. purge anything that was previously imported.
 489          * then re-evaluate the need to import.
 490          */
 491         fib_attached_export_purge(fib_entry);
 492         fib_attached_export_import(fib_entry, export_fib);
 493     }
 494 }
 495
 496 /**
 497  * \brief If this entry is tracking a cover (in another table)
 498  *        then that cover has changed. re-evaluate import.
 499  */
 500 void
 501 fib_attached_export_cover_change (fib_entry_t *fib_entry)
 502 {
 503     fib_attached_export_cover_modified_i(fib_entry);
 504 }
 505
 506 /**
 507  * \brief If this entry is tracking a cover (in another table)
 508  *        then that cover has been updated. re-evaluate import.
 509  */
 510 void
 511 fib_attached_export_cover_update (fib_entry_t *fib_entry)
 512 {
 513     fib_attached_export_cover_modified_i(fib_entry);
 514 }
 515
 516 u8*
 517 fib_ae_import_format (fib_entry_t *fib_entry,
 518                       u8* s)
 519 {
 520     fib_entry_delegate_t *fed;
 521
 522     fed = fib_entry_delegate_get(fib_entry,
 523                                  FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 524
 525     if (NULL != fed)
 526     {
 527         fib_node_index_t *index;
 528         fib_ae_import_t *import;
 529
 530         import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
 531
 532         s = format(s, "\n  Attached-Import:%d:[", (import - fib_ae_import_pool));
 533         s = format(s, "export-prefix:%U ", format_fib_prefix, &import->faei_prefix);
 534         s = format(s, "export-entry:%d ", import->faei_export_entry);
 535         s = format(s, "export-sibling:%d ", import->faei_export_sibling);
 536         s = format(s, "exporter:%d ", import->faei_exporter);
 537         s = format(s, "export-fib:%d ", import->faei_export_fib);
 538
 539         s = format(s, "import-entry:%d ", import->faei_import_entry);
 540         s = format(s, "import-fib:%d ", import->faei_import_fib);
 541
 542         s = format(s, "importeds:[");
 543         vec_foreach(index, import->faei_importeds)
 544         {
 545             s = format(s, "%d, ", *index);
 546         }
 547         s = format(s, "]]");
 548     }
 549
 550     return (s);
 551 }
 552
 553 u8*
 554 fib_ae_export_format (fib_entry_t *fib_entry,
 555                       u8* s)
 556 {
 557     fib_entry_delegate_t *fed;
 558
 559     fed = fib_entry_delegate_get(fib_entry,
 560                                  FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 561
 562     if (NULL != fed)
 563     {
 564         fib_node_index_t *index;
 565         fib_ae_export_t *export;
 566
 567         export = pool_elt_at_index(fib_ae_export_pool, fed->fd_list);
 568
 569         s = format(s, "\n  Attached-Export:%d:[", (export - fib_ae_export_pool));
 570         s = format(s, "export-entry:%d ", export->faee_ei);
 571
 572         s = format(s, "importers:[");
 573         vec_foreach(index, export->faee_importers)
 574         {
 575             s = format(s, "%d, ", *index);
 576         }
 577         s = format(s, "]]");
 578     }
 579     return (s);
 580 }