src/vnet/dpo/load_balance_map.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  * @brief
  17  */
  18 #include <vnet/fib/fib_path.h>
  19 #include <vnet/fib/fib_node_list.h>
  20 #include <vnet/dpo/load_balance_map.h>
  21 #include <vnet/dpo/load_balance.h>
  22
  23 /**
  24  * A hash-table of load-balance maps by path index.
  25  * this provides the fast lookup of the LB map when a path goes down
  26  */
  27 static uword *lb_maps_by_path_index;
  28
  29 /**
  30  * A hash-table of load-balance maps by set of paths.
  31  * This provides the LB map sharing.
  32  * LB maps do not necessarily use all the paths in the list, since
  33  * the entry that is requesting the map, may not have an out-going
  34  * label for each of the paths.
  35  */
  36 static uword *load_balance_map_db;
  37
  38 typedef enum load_balance_map_path_flags_t_
  39 {
  40     LOAD_BALANCE_MAP_PATH_UP     = (1 << 0),
  41     LOAD_BALANCE_MAP_PATH_USABLE = (1 << 1),
  42 } __attribute__ ((packed)) load_balance_map_path_flags_t;
  43
  44 typedef struct load_balance_map_path_t_ {
  45     /**
  46      * Index of the path
  47      */
  48     fib_node_index_t lbmp_index;
  49
  50     /**
  51      * Sibling Index in the list of all maps with this path index
  52      */
  53     fib_node_index_t lbmp_sibling;
  54
  55     /**
  56      * the normalised wegiht of the path
  57      */
  58     u32 lbmp_weight;
  59
  60     /**
  61      * The sate of the path
  62      */
  63     load_balance_map_path_flags_t lbmp_flags;
  64 } load_balance_map_path_t;
  65
  66 /**
  67  * The global pool of LB maps
  68  */
  69 load_balance_map_t *load_balance_map_pool;
  70
  71 /*
  72  * Debug macro
  73  */
  74 #ifdef FIB_DEBUG
  75 #define LOAD_BALANCE_MAP_DBG(_pl, _fmt, _args...)       \
  76     {                                                   \
  77         clib_warning("lbm: FIXME" _fmt,                 \
  78                      ##_args);                          \
  79     }
  80 #else
  81 #define LOAD_BALANCE_MAP_DBG(_pl, _fmt, _args...)
  82 #endif
  83
  84 static index_t
  85 load_balance_map_get_index (load_balance_map_t *lbm)
  86 {
  87     return (lbm - load_balance_map_pool);
  88 }
  89
  90 u8*
  91 format_load_balance_map (u8 *s, va_list * ap)
  92 {
  93     index_t lbmi = va_arg(*ap, index_t);
  94     u32 indent = va_arg(*ap, u32);
  95     load_balance_map_t *lbm;
  96     u32 n_buckets, ii;
  97
  98     lbm = load_balance_map_get(lbmi);
  99     n_buckets = vec_len(lbm->lbm_buckets);
 100
 101     s = format(s, "load-balance-map: index:%d buckets:%d", lbmi, n_buckets);
 102     s = format(s, "\n%U index:", format_white_space, indent+2);
 103     for (ii = 0; ii < n_buckets; ii++)
 104     {
 105         s = format(s, "%5d", ii);
 106     }
 107     s = format(s, "\n%U   map:", format_white_space, indent+2);
 108     for (ii = 0; ii < n_buckets; ii++)
 109     {
 110         s = format(s, "%5d", lbm->lbm_buckets[ii]);
 111     }
 112
 113     return (s);
 114 }
 115
 116
 117 static uword
 118 load_balance_map_hash (load_balance_map_t *lbm)
 119 {
 120     u32 old_lbm_hash, new_lbm_hash, hash;
 121     load_balance_map_path_t *lb_path;
 122
 123     new_lbm_hash = old_lbm_hash = vec_len(lbm->lbm_paths);
 124
 125     vec_foreach (lb_path, lbm->lbm_paths)
 126     {
 127         hash = lb_path->lbmp_index;
 128         hash_mix32(hash, old_lbm_hash, new_lbm_hash);
 129     }
 130
 131     return (new_lbm_hash);
 132 }
 133
 134 always_inline uword
 135 load_balance_map_db_hash_key_from_index (uword index)
 136 {
 137     return 1 + 2*index;
 138 }
 139
 140 always_inline uword
 141 load_balance_map_db_hash_key_is_index (uword key)
 142 {
 143     return key & 1;
 144 }
 145
 146 always_inline uword
 147 load_balance_map_db_hash_key_2_index (uword key)
 148 {
 149     ASSERT (load_balance_map_db_hash_key_is_index (key));
 150     return key / 2;
 151 }
 152
 153 static load_balance_map_t*
 154 load_balance_map_db_get_from_hash_key (uword key)
 155 {
 156     load_balance_map_t *lbm;
 157
 158     if (load_balance_map_db_hash_key_is_index (key))
 159     {
 160         index_t lbm_index;
 161
 162         lbm_index = load_balance_map_db_hash_key_2_index(key);
 163         lbm = load_balance_map_get(lbm_index);
 164     }
 165     else
 166     {
 167         lbm = uword_to_pointer (key, load_balance_map_t *);
 168     }
 169
 170     return (lbm);
 171 }
 172
 173 static uword
 174 load_balance_map_db_hash_key_sum (hash_t * h,
 175                                   uword key)
 176 {
 177     load_balance_map_t *lbm;
 178
 179     lbm = load_balance_map_db_get_from_hash_key(key);
 180
 181     return (load_balance_map_hash(lbm));
 182 }
 183
 184 static uword
 185 load_balance_map_db_hash_key_equal (hash_t * h,
 186                                     uword key1,
 187                                     uword key2)
 188 {
 189     load_balance_map_t *lbm1, *lbm2;
 190
 191     lbm1 = load_balance_map_db_get_from_hash_key(key1);
 192     lbm2 = load_balance_map_db_get_from_hash_key(key2);
 193
 194     return (load_balance_map_hash(lbm1) ==
 195             load_balance_map_hash(lbm2));
 196 }
 197
 198 static index_t
 199 load_balance_map_db_find (load_balance_map_t *lbm)
 200 {
 201     uword *p;
 202
 203     p = hash_get(load_balance_map_db, lbm);
 204
 205     if (NULL != p)
 206     {
 207         return p[0];
 208     }
 209
 210     return (FIB_NODE_INDEX_INVALID);
 211 }
 212
 213 static void
 214 load_balance_map_db_insert (load_balance_map_t *lbm)
 215 {
 216     load_balance_map_path_t *lbmp;
 217     fib_node_list_t list;
 218     uword *p;
 219
 220     ASSERT(FIB_NODE_INDEX_INVALID == load_balance_map_db_find(lbm));
 221
 222     /*
 223      * insert into the DB based on the set of paths.
 224      */
 225     hash_set (load_balance_map_db,
 226               load_balance_map_db_hash_key_from_index(
 227                   load_balance_map_get_index(lbm)),
 228               load_balance_map_get_index(lbm));
 229
 230     /*
 231      * insert into each per-path list.
 232      */
 233     vec_foreach(lbmp, lbm->lbm_paths)
 234     {
 235         p = hash_get(lb_maps_by_path_index, lbmp->lbmp_index);
 236
 237         if (NULL == p)
 238         {
 239             list = fib_node_list_create();
 240             hash_set(lb_maps_by_path_index, lbmp->lbmp_index, list);
 241         }
 242         else
 243         {
 244             list = p[0];
 245         }
 246
 247         lbmp->lbmp_sibling =
 248             fib_node_list_push_front(list,
 249                                      0, FIB_NODE_TYPE_FIRST,
 250                                      load_balance_map_get_index(lbm));
 251     }
 252
 253     LOAD_BALANCE_MAP_DBG(lbm, "DB-inserted");
 254 }
 255
 256 static void
 257 load_balance_map_db_remove (load_balance_map_t *lbm)
 258 {
 259     load_balance_map_path_t *lbmp;
 260     uword *p;
 261
 262     ASSERT(FIB_NODE_INDEX_INVALID != load_balance_map_db_find(lbm));
 263
 264     hash_unset(load_balance_map_db,
 265                load_balance_map_db_hash_key_from_index(
 266                    load_balance_map_get_index(lbm)));
 267
 268     /*
 269      * remove from each per-path list.
 270      */
 271     vec_foreach(lbmp, lbm->lbm_paths)
 272     {
 273         p = hash_get(lb_maps_by_path_index, lbmp->lbmp_index);
 274
 275         ASSERT(NULL != p);
 276
 277         fib_node_list_remove(p[0], lbmp->lbmp_sibling);
 278     }
 279
 280     LOAD_BALANCE_MAP_DBG(lbm, "DB-removed");
 281 }
 282
 283 /**
 284  * @brief from the paths that are usable, fill the Map.
 285  */
 286 static void
 287 load_balance_map_fill (load_balance_map_t *lbm)
 288 {
 289     load_balance_map_path_t *lbmp;
 290     u32 n_buckets, bucket, ii, jj;
 291     u16 *tmp_buckets;
 292
 293     tmp_buckets = NULL;
 294     n_buckets = vec_len(lbm->lbm_buckets);
 295
 296     /*
 297      * run throught the set of paths once, and build a vector of the
 298      * indices that are usable. we do this is a scratch space, since we
 299      * need to refer to it multiple times as we build the real buckets.
 300      */
 301     vec_validate(tmp_buckets, n_buckets-1);
 302
 303     bucket = jj = 0;
 304     vec_foreach (lbmp, lbm->lbm_paths)
 305     {
 306         if (fib_path_is_resolved(lbmp->lbmp_index))
 307         {
 308             for (ii = 0; ii < lbmp->lbmp_weight; ii++)
 309             {
 310                 tmp_buckets[jj++] = bucket++;
 311             }
 312         }
 313         else
 314         {
 315             bucket += lbmp->lbmp_weight;
 316         }
 317     }
 318     _vec_len(tmp_buckets) = jj;
 319
 320     /*
 321      * If the number of temporaries written is as many as we need, implying
 322      * all paths were up, then we can simply copy the scratch area over the
 323      * actual buckets' memory
 324      */
 325     if (jj == n_buckets)
 326     {
 327         memcpy(lbm->lbm_buckets,
 328                tmp_buckets,
 329                sizeof(lbm->lbm_buckets[0]) * n_buckets);
 330     }
 331     else
 332     {
 333         /*
 334          * one or more paths are down.
 335          */
 336         if (0 == vec_len(tmp_buckets))
 337         {
 338             /*
 339              * if the scratch area is empty, then no paths are usable.
 340              * they will all drop. so use them all, lest we account drops
 341              * against only one.
 342              */
 343             for (bucket = 0; bucket < n_buckets; bucket++)
 344             {
 345                 lbm->lbm_buckets[bucket] = bucket;
 346             }
 347         }
 348         else
 349         {
 350             bucket = jj = 0;
 351             vec_foreach (lbmp, lbm->lbm_paths)
 352             {
 353                 if (fib_path_is_resolved(lbmp->lbmp_index))
 354                 {
 355                     for (ii = 0; ii < lbmp->lbmp_weight; ii++)
 356                     {
 357                         lbm->lbm_buckets[bucket] = bucket;
 358                         bucket++;
 359                     }
 360                 }
 361                 else
 362                 {
 363                     /*
 364                      * path is unusable
 365                      * cycle through the scratch space selecting a index.
 366                      * this means we load balance, in the intended ratio,
 367                      * over the paths that are still usable.
 368                      */
 369                     for (ii = 0; ii < lbmp->lbmp_weight; ii++)
 370                     {
 371                         lbm->lbm_buckets[bucket] = tmp_buckets[jj];
 372                         jj = (jj + 1) % vec_len(tmp_buckets);
 373                         bucket++;
 374                     }
 375                 }
 376             }
 377        }
 378     }
 379
 380     vec_free(tmp_buckets);
 381 }
 382
 383 static load_balance_map_t*
 384 load_balance_map_alloc (const load_balance_path_t *paths)
 385 {
 386     load_balance_map_t *lbm;
 387     u32 ii;
 388
 389     pool_get_aligned(load_balance_map_pool, lbm, CLIB_CACHE_LINE_BYTES);
 390     memset(lbm, 0, sizeof(*lbm));
 391
 392     vec_validate(lbm->lbm_paths, vec_len(paths)-1);
 393
 394     vec_foreach_index(ii, paths)
 395     {
 396         lbm->lbm_paths[ii].lbmp_index  = paths[ii].path_index;
 397         lbm->lbm_paths[ii].lbmp_weight = paths[ii].path_weight;
 398     }
 399
 400     return (lbm);
 401 }
 402
 403 static load_balance_map_t *
 404 load_balance_map_init (load_balance_map_t *lbm,
 405                        u32 n_buckets,
 406                        u32 sum_of_weights)
 407 {
 408     lbm->lbm_sum_of_norm_weights = sum_of_weights;
 409     vec_validate(lbm->lbm_buckets, n_buckets-1);
 410
 411     load_balance_map_db_insert(lbm);
 412
 413     load_balance_map_fill(lbm);
 414
 415     return (lbm);
 416 }
 417
 418 static void
 419 load_balance_map_destroy (load_balance_map_t *lbm)
 420 {
 421     vec_free(lbm->lbm_paths);
 422     vec_free(lbm->lbm_buckets);
 423     pool_put(load_balance_map_pool, lbm);
 424 }
 425
 426 index_t
 427 load_balance_map_add_or_lock (u32 n_buckets,
 428                               u32 sum_of_weights,
 429                               const load_balance_path_t *paths)
 430 {
 431     load_balance_map_t *tmp, *lbm;
 432     index_t lbmi;
 433
 434     tmp = load_balance_map_alloc(paths);
 435
 436     lbmi = load_balance_map_db_find(tmp);
 437
 438     if (INDEX_INVALID == lbmi)
 439     {
 440         lbm = load_balance_map_init(tmp, n_buckets, sum_of_weights);
 441     }
 442     else
 443     {
 444         lbm = load_balance_map_get(lbmi);
 445         load_balance_map_destroy(tmp);
 446     }
 447
 448     lbm->lbm_locks++;
 449
 450     return (load_balance_map_get_index(lbm));
 451 }
 452
 453 void
 454 load_balance_map_lock (index_t lbmi)
 455 {
 456     load_balance_map_t *lbm;
 457
 458     lbm = load_balance_map_get(lbmi);
 459
 460     lbm->lbm_locks++;
 461 }
 462
 463 void
 464 load_balance_map_unlock (index_t lbmi)
 465 {
 466     load_balance_map_t *lbm;
 467
 468     if (INDEX_INVALID == lbmi)
 469     {
 470         return;
 471     }
 472
 473     lbm = load_balance_map_get(lbmi);
 474
 475     lbm->lbm_locks--;
 476
 477     if (0 == lbm->lbm_locks)
 478     {
 479         load_balance_map_db_remove(lbm);
 480         load_balance_map_destroy(lbm);
 481     }
 482 }
 483
 484 static int
 485 load_balance_map_path_state_change_walk (fib_node_ptr_t *fptr,
 486                                          void *ctx)
 487 {
 488     load_balance_map_t *lbm;
 489
 490     lbm = load_balance_map_get(fptr->fnp_index);
 491
 492     load_balance_map_fill(lbm);
 493
 494     return (!0);
 495 }
 496
 497 /**
 498  * @brief the state of a path has changed (it has no doubt gone down).
 499  * This is the trigger to perform a PIC edge cutover and update the maps
 500  * to exclude this path.
 501  */
 502 void
 503 load_balance_map_path_state_change (fib_node_index_t path_index)
 504 {
 505     uword *p;
 506
 507     /*
 508      * re-stripe the buckets for each affect MAP
 509      */
 510     p = hash_get(lb_maps_by_path_index, path_index);
 511
 512     if (NULL == p)
 513         return;
 514
 515     fib_node_list_walk(p[0], load_balance_map_path_state_change_walk, NULL);
 516 }
 517
 518 /**
 519  * @brief Make/add a new or lock an existing Load-balance map
 520  */
 521 void
 522 load_balance_map_module_init (void)
 523 {
 524     load_balance_map_db =
 525         hash_create2 (/* elts */ 0,
 526                       /* user */ 0,
 527                       /* value_bytes */ sizeof (index_t),
 528                       load_balance_map_db_hash_key_sum,
 529                       load_balance_map_db_hash_key_equal,
 530                       /* format pair/arg */
 531                       0, 0);
 532
 533     lb_maps_by_path_index = hash_create(0, sizeof(fib_node_list_t));
 534 }
 535
 536 void
 537 load_balance_map_show_mem (void)
 538 {
 539     fib_show_memory_usage("Load-Balance Map",
 540                           pool_elts(load_balance_map_pool),
 541                           pool_len(load_balance_map_pool),
 542                           sizeof(load_balance_map_t));
 543 }
 544
 545 static clib_error_t *
 546 load_balance_map_show (vlib_main_t * vm,
 547                        unformat_input_t * input,
 548                        vlib_cli_command_t * cmd)
 549 {
 550     index_t lbmi = INDEX_INVALID;
 551
 552     while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 553     {
 554         if (unformat (input, "%d", &lbmi))
 555             ;
 556         else
 557             break;
 558     }
 559
 560     if (INDEX_INVALID != lbmi)
 561     {
 562         vlib_cli_output (vm, "%U", format_load_balance_map, lbmi, 0);
 563     }
 564     else
 565     {
 566         load_balance_map_t *lbm;
 567
 568         pool_foreach(lbm, load_balance_map_pool,
 569         ({
 570             vlib_cli_output (vm, "%U", format_load_balance_map,
 571                              load_balance_map_get_index(lbm), 0);
 572         }));
 573     }
 574
 575     return 0;
 576 }
 577
 578 VLIB_CLI_COMMAND (load_balance_map_show_command, static) = {
 579     .path = "show load-balance-map",
 580     .short_help = "show load-balance-map [<index>]",
 581     .function = load_balance_map_show,
 582 };