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