vnet/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_FLAG_EXCLUSIVE,
 193                                             load_balance_get_bucket(dpo->dpoi_index, 0));
 194
 195             fib_entry_lock(entry_index);
 196             vec_add1(import->faei_importeds, entry_index);
 197         }
 198         /*
 199          * else
 200          *   the entry currently has no valid forwarding. when it
 201          * does it will export itself
 202          */
 203     }
 204 }
 205
 206 /**
 207  * Call back when walking a connected prefix's covered prefixes for import
 208  */
 209 static int
 210 fib_entry_covered_walk_import (fib_entry_t *cover,
 211                                fib_node_index_t covered,
 212                                void *ctx)
 213 {
 214     fib_ae_import_t *import = ctx;
 215
 216     fib_entry_import_add(import, covered);
 217
 218     return (0);
 219 }
 220
 221 /*
 222  * fib_entry_ae_import_add
 223  *
 224  * Add an importer to a connected entry
 225  */
 226 static void
 227 fib_ae_export_import_add (fib_ae_export_t *export,
 228                           fib_ae_import_t *import)
 229 {
 230     fib_entry_t *entry;
 231
 232     import->faei_exporter = (export - fib_ae_export_pool);
 233     entry = fib_entry_get(export->faee_ei);
 234
 235     fib_entry_cover_walk(entry,
 236                          fib_entry_covered_walk_import,
 237                          import);
 238 }
 239
 240 void
 241 fib_attached_export_import (fib_entry_t *fib_entry,
 242                             fib_node_index_t export_fib)
 243 {
 244     fib_entry_delegate_t *fed;
 245     fib_ae_import_t *import;
 246
 247     pool_get(fib_ae_import_pool, import);
 248
 249     import->faei_import_fib = fib_entry->fe_fib_index;
 250     import->faei_export_fib = export_fib;
 251     import->faei_prefix = fib_entry->fe_prefix;
 252     import->faei_import_entry = fib_entry_get_index(fib_entry);
 253     import->faei_export_sibling = ~0;
 254
 255     /*
 256      * do an exact match in the export table
 257      */
 258     import->faei_export_entry =
 259         fib_table_lookup_exact_match(import->faei_export_fib,
 260                                      &import->faei_prefix);
 261
 262     if (FIB_NODE_INDEX_INVALID == import->faei_export_entry)
 263     {
 264         /*
 265          * no exact matching entry in the export table. can't be good.
 266          * track the next best thing
 267          */
 268         import->faei_export_entry =
 269             fib_table_lookup(import->faei_export_fib,
 270                              &import->faei_prefix);
 271         import->faei_exporter = FIB_NODE_INDEX_INVALID;
 272     }
 273     else
 274     {
 275         /*
 276          * found the entry in the export table. import the
 277          * the prefixes that it covers.
 278          * only if the prefix found in the export FIB really is
 279          * attached do we want to import its covered
 280          */
 281         if (FIB_ENTRY_FLAG_ATTACHED &
 282             fib_entry_get_flags_i(fib_entry_get(import->faei_export_entry)))
 283         {
 284             fib_ae_export_t *export;
 285
 286             export = fib_entry_ae_add_or_lock(import->faei_export_entry);
 287             vec_add1(export->faee_importers, (import - fib_ae_import_pool));
 288             fib_ae_export_import_add(export, import);
 289         }
 290     }
 291
 292     /*
 293      * track the entry in the export table so we can update appropriately
 294      * when it changes
 295      */
 296     import->faei_export_sibling =
 297         fib_entry_cover_track(fib_entry_get(import->faei_export_entry),
 298                               fib_entry_get_index(fib_entry));
 299
 300     fed = fib_entry_delegate_find_or_add(fib_entry,
 301                                          FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 302     fed->fd_index = (import - fib_ae_import_pool);
 303 }
 304
 305 /**
 306  * \brief All the imported entries need to be pruged
 307  */
 308 void
 309 fib_attached_export_purge (fib_entry_t *fib_entry)
 310 {
 311     fib_entry_delegate_t *fed;
 312
 313     fed = fib_entry_delegate_get(fib_entry,
 314                                  FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 315
 316     if (NULL != fed)
 317     {
 318         fib_node_index_t *import_index;
 319         fib_entry_t *export_entry;
 320         fib_ae_import_t *import;
 321         fib_ae_export_t *export;
 322
 323         import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
 324
 325         /*
 326          * remove each imported entry
 327          */
 328         vec_foreach(import_index, import->faei_importeds)
 329         {
 330             fib_prefix_t prefix;
 331
 332             fib_entry_get_prefix(*import_index, &prefix);
 333
 334             fib_table_entry_delete(import->faei_import_fib,
 335                                    &prefix,
 336                                    FIB_SOURCE_AE);
 337             fib_entry_unlock(*import_index);
 338         }
 339         vec_free(import->faei_importeds);
 340
 341         /*
 342          * stop tracking the export entry
 343          */
 344         if (~0 != import->faei_export_sibling)
 345         {
 346             fib_entry_cover_untrack(fib_entry_get(import->faei_export_entry),
 347                                     import->faei_export_sibling);
 348         }
 349         import->faei_export_sibling = ~0;
 350
 351         /*
 352          * remove this import tracker from the export's list,
 353          * if it is attached to one. It won't be in the case the tracked
 354          * export entry is not an attached exact match.
 355          */
 356         if (FIB_NODE_INDEX_INVALID != import->faei_exporter)
 357         {
 358             fib_entry_delegate_t *fed;
 359
 360             export_entry = fib_entry_get(import->faei_export_entry);
 361
 362             fed = fib_entry_delegate_get(export_entry,
 363                                          FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 364             ASSERT(NULL != fed);
 365
 366             export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
 367
 368             u32 index = vec_search(export->faee_importers,
 369                                    (import - fib_ae_import_pool));
 370
 371             ASSERT(index < vec_len(export->faee_importers));
 372             vec_del1(export->faee_importers, index);
 373
 374             /*
 375              * free the exporter if there are no longer importers
 376              */
 377             if (0 == --export->faee_locks)
 378             {
 379                 pool_put(fib_ae_export_pool, export);
 380                 fib_entry_delegate_remove(export_entry,
 381                                           FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 382             }
 383         }
 384
 385         /*
 386          * free the import tracker
 387          */
 388         pool_put(fib_ae_import_pool, import);
 389         fib_entry_delegate_remove(fib_entry,
 390                                   FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 391     }
 392 }
 393
 394 void
 395 fib_attached_export_covered_added (fib_entry_t *cover,
 396                                    fib_node_index_t covered)
 397 {
 398     fib_entry_delegate_t *fed;
 399
 400     fed = fib_entry_delegate_get(cover,
 401                                  FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 402
 403     if (NULL != fed)
 404     {
 405         /*
 406          * the covering prefix is exporting to other tables
 407          */
 408         fib_node_index_t *import_index;
 409         fib_ae_import_t *import;
 410         fib_ae_export_t *export;
 411
 412         export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
 413
 414         /*
 415          * export the covered entry to each of the importers
 416          */
 417         vec_foreach(import_index, export->faee_importers)
 418         {
 419             import = pool_elt_at_index(fib_ae_import_pool, *import_index);
 420
 421             fib_entry_import_add(import, covered);
 422         }
 423     }
 424 }
 425
 426 void
 427 fib_attached_export_covered_removed (fib_entry_t *cover,
 428                                      fib_node_index_t covered)
 429 {
 430     fib_entry_delegate_t *fed;
 431
 432     fed = fib_entry_delegate_get(cover,
 433                                  FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 434
 435     if (NULL != fed)
 436     {
 437         /*
 438          * the covering prefix is exporting to other tables
 439          */
 440         fib_node_index_t *import_index;
 441         fib_ae_import_t *import;
 442         fib_ae_export_t *export;
 443
 444         export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
 445
 446         /*
 447          * remove the covered entry from each of the importers
 448          */
 449         vec_foreach(import_index, export->faee_importers)
 450         {
 451             import = pool_elt_at_index(fib_ae_import_pool, *import_index);
 452
 453             fib_entry_import_remove(import, covered);
 454         }
 455     }
 456 }
 457
 458 static void
 459 fib_attached_export_cover_modified_i (fib_entry_t *fib_entry)
 460 {
 461     fib_entry_delegate_t *fed;
 462
 463     fed = fib_entry_delegate_get(fib_entry,
 464                                  FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 465
 466     if (NULL != fed)
 467     {
 468         fib_ae_import_t *import;
 469         u32 export_fib;
 470
 471         /*
 472          * safe the temporaries we need from the existing import
 473          * since it will be toast after the purge.
 474          */
 475         import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
 476         export_fib = import->faei_export_fib;
 477
 478         /*
 479          * keep it simple. purge anything that was previously imported.
 480          * then re-evaluate the need to import.
 481          */
 482         fib_attached_export_purge(fib_entry);
 483         fib_attached_export_import(fib_entry, export_fib);
 484     }
 485 }
 486
 487 /**
 488  * \brief If this entry is tracking a cover (in another table)
 489  *        then that cover has changed. re-evaluate import.
 490  */
 491 void
 492 fib_attached_export_cover_change (fib_entry_t *fib_entry)
 493 {
 494     fib_attached_export_cover_modified_i(fib_entry);
 495 }
 496
 497 /**
 498  * \brief If this entry is tracking a cover (in another table)
 499  *        then that cover has been updated. re-evaluate import.
 500  */
 501 void
 502 fib_attached_export_cover_update (fib_entry_t *fib_entry)
 503 {
 504     fib_attached_export_cover_modified_i(fib_entry);
 505 }
 506
 507 u8*
 508 fib_ae_import_format (fib_entry_t *fib_entry,
 509                       u8* s)
 510 {
 511     fib_entry_delegate_t *fed;
 512
 513     fed = fib_entry_delegate_get(fib_entry,
 514                                  FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 515
 516     if (NULL != fed)
 517     {
 518         fib_node_index_t *index;
 519         fib_ae_import_t *import;
 520
 521         import = pool_elt_at_index(fib_ae_import_pool, fed->fd_index);
 522
 523         s = format(s, "\n  Attached-Import:%d:[", (import - fib_ae_import_pool));
 524         s = format(s, "export-prefix:%U ", format_fib_prefix, &import->faei_prefix);
 525         s = format(s, "export-entry:%d ", import->faei_export_entry);
 526         s = format(s, "export-sibling:%d ", import->faei_export_sibling);
 527         s = format(s, "exporter:%d ", import->faei_exporter);
 528         s = format(s, "export-fib:%d ", import->faei_export_fib);
 529
 530         s = format(s, "import-entry:%d ", import->faei_import_entry);
 531         s = format(s, "import-fib:%d ", import->faei_import_fib);
 532
 533         s = format(s, "importeds:[");
 534         vec_foreach(index, import->faei_importeds)
 535         {
 536             s = format(s, "%d, ", *index);
 537         }
 538             s = format(s, "]]");
 539     }
 540
 541     return (s);
 542 }
 543
 544 u8*
 545 fib_ae_export_format (fib_entry_t *fib_entry,
 546                       u8* s)
 547 {
 548     fib_entry_delegate_t *fed;
 549
 550     fed = fib_entry_delegate_get(fib_entry,
 551                                  FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 552
 553     if (NULL != fed)
 554     {
 555         fib_node_index_t *index;
 556         fib_ae_export_t *export;
 557
 558         export = pool_elt_at_index(fib_ae_export_pool, fed->fd_list);
 559
 560         s = format(s, "\n  Attached-Export:%d:[", (export - fib_ae_export_pool));
 561         s = format(s, "export-entry:%d ", export->faee_ei);
 562
 563         s = format(s, "importers:[");
 564         vec_foreach(index, export->faee_importers)
 565         {
 566             s = format(s, "%d, ", *index);
 567         }
 568         s = format(s, "]]");
 569     }
 570     return (s);
 571 }