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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
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>
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
27 static uword *lb_maps_by_path_index;
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.
36 static uword *load_balance_map_db;
38 typedef enum load_balance_map_path_flags_t_
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;
44 typedef struct load_balance_map_path_t_ {
48 fib_node_index_t lbmp_index;
51 * Sibling Index in the list of all maps with this path index
53 fib_node_index_t lbmp_sibling;
56 * the normalised wegiht of the path
61 * The sate of the path
63 load_balance_map_path_flags_t lbmp_flags;
64 } load_balance_map_path_t;
67 * The global pool of LB maps
69 load_balance_map_t *load_balance_map_pool;
74 vlib_log_class_t load_balance_map_logger;
79 #define LOAD_BALANCE_MAP_DBG(_pl, _fmt, _args...) \
81 vlib_log_debug(load_balance_map_logger, \
87 load_balance_map_get_index (load_balance_map_t *lbm)
89 return (lbm - load_balance_map_pool);
93 format_load_balance_map (u8 *s, va_list * ap)
95 index_t lbmi = va_arg(*ap, index_t);
96 u32 indent = va_arg(*ap, u32);
97 load_balance_map_t *lbm;
100 lbm = load_balance_map_get(lbmi);
101 n_buckets = vec_len(lbm->lbm_buckets);
103 s = format(s, "load-balance-map: index:%d buckets:%d", lbmi, n_buckets);
104 s = format(s, "\n%U index:", format_white_space, indent+2);
105 for (ii = 0; ii < n_buckets; ii++)
107 s = format(s, "%5d", ii);
109 s = format(s, "\n%U map:", format_white_space, indent+2);
110 for (ii = 0; ii < n_buckets; ii++)
112 s = format(s, "%5d", lbm->lbm_buckets[ii]);
120 load_balance_map_hash (load_balance_map_t *lbm)
122 u32 old_lbm_hash, new_lbm_hash, hash;
123 load_balance_map_path_t *lb_path;
125 new_lbm_hash = old_lbm_hash = vec_len(lbm->lbm_paths);
127 vec_foreach (lb_path, lbm->lbm_paths)
129 hash = lb_path->lbmp_index;
130 hash_mix32(hash, old_lbm_hash, new_lbm_hash);
133 return (new_lbm_hash);
137 load_balance_map_db_hash_key_from_index (uword index)
143 load_balance_map_db_hash_key_is_index (uword key)
149 load_balance_map_db_hash_key_2_index (uword key)
151 ASSERT (load_balance_map_db_hash_key_is_index (key));
155 static load_balance_map_t*
156 load_balance_map_db_get_from_hash_key (uword key)
158 load_balance_map_t *lbm;
160 if (load_balance_map_db_hash_key_is_index (key))
164 lbm_index = load_balance_map_db_hash_key_2_index(key);
165 lbm = load_balance_map_get(lbm_index);
169 lbm = uword_to_pointer (key, load_balance_map_t *);
176 load_balance_map_db_hash_key_sum (hash_t * h,
179 load_balance_map_t *lbm;
181 lbm = load_balance_map_db_get_from_hash_key(key);
183 return (load_balance_map_hash(lbm));
187 load_balance_map_db_hash_key_equal (hash_t * h,
191 load_balance_map_t *lbm1, *lbm2;
193 lbm1 = load_balance_map_db_get_from_hash_key(key1);
194 lbm2 = load_balance_map_db_get_from_hash_key(key2);
196 return (load_balance_map_hash(lbm1) ==
197 load_balance_map_hash(lbm2));
201 load_balance_map_db_find (load_balance_map_t *lbm)
205 p = hash_get(load_balance_map_db, lbm);
212 return (FIB_NODE_INDEX_INVALID);
216 load_balance_map_db_insert (load_balance_map_t *lbm)
218 load_balance_map_path_t *lbmp;
219 fib_node_list_t list;
222 ASSERT(FIB_NODE_INDEX_INVALID == load_balance_map_db_find(lbm));
225 * insert into the DB based on the set of paths.
227 hash_set (load_balance_map_db,
228 load_balance_map_db_hash_key_from_index(
229 load_balance_map_get_index(lbm)),
230 load_balance_map_get_index(lbm));
233 * insert into each per-path list.
235 vec_foreach(lbmp, lbm->lbm_paths)
237 p = hash_get(lb_maps_by_path_index, lbmp->lbmp_index);
241 list = fib_node_list_create();
242 hash_set(lb_maps_by_path_index, lbmp->lbmp_index, list);
250 fib_node_list_push_front(list,
251 0, FIB_NODE_TYPE_FIRST,
252 load_balance_map_get_index(lbm));
255 LOAD_BALANCE_MAP_DBG(lbm, "DB-inserted");
259 load_balance_map_db_remove (load_balance_map_t *lbm)
261 load_balance_map_path_t *lbmp;
264 ASSERT(FIB_NODE_INDEX_INVALID != load_balance_map_db_find(lbm));
266 hash_unset(load_balance_map_db,
267 load_balance_map_db_hash_key_from_index(
268 load_balance_map_get_index(lbm)));
271 * remove from each per-path list.
273 vec_foreach(lbmp, lbm->lbm_paths)
275 p = hash_get(lb_maps_by_path_index, lbmp->lbmp_index);
277 ALWAYS_ASSERT(NULL != p);
279 fib_node_list_remove(p[0], lbmp->lbmp_sibling);
282 LOAD_BALANCE_MAP_DBG(lbm, "DB-removed");
286 * @brief from the paths that are usable, fill the Map.
289 load_balance_map_fill (load_balance_map_t *lbm)
291 load_balance_map_path_t *lbmp;
292 u32 n_buckets, bucket, ii, jj;
296 n_buckets = vec_len(lbm->lbm_buckets);
299 * run throught the set of paths once, and build a vector of the
300 * indices that are usable. we do this is a scratch space, since we
301 * need to refer to it multiple times as we build the real buckets.
303 vec_validate(tmp_buckets, n_buckets-1);
306 vec_foreach (lbmp, lbm->lbm_paths)
308 if (fib_path_is_resolved(lbmp->lbmp_index))
310 for (ii = 0; ii < lbmp->lbmp_weight; ii++)
312 tmp_buckets[jj++] = bucket++;
317 bucket += lbmp->lbmp_weight;
320 vec_set_len (tmp_buckets, jj);
323 * If the number of temporaries written is as many as we need, implying
324 * all paths were up, then we can simply copy the scratch area over the
325 * actual buckets' memory
329 memcpy(lbm->lbm_buckets,
331 sizeof(lbm->lbm_buckets[0]) * n_buckets);
336 * one or more paths are down.
338 if (0 == vec_len(tmp_buckets))
341 * if the scratch area is empty, then no paths are usable.
342 * they will all drop. so use them all, lest we account drops
345 for (bucket = 0; bucket < n_buckets; bucket++)
347 lbm->lbm_buckets[bucket] = bucket;
353 vec_foreach (lbmp, lbm->lbm_paths)
355 if (fib_path_is_resolved(lbmp->lbmp_index))
357 for (ii = 0; ii < lbmp->lbmp_weight; ii++)
359 lbm->lbm_buckets[bucket] = bucket;
367 * cycle through the scratch space selecting a index.
368 * this means we load balance, in the intended ratio,
369 * over the paths that are still usable.
371 for (ii = 0; ii < lbmp->lbmp_weight; ii++)
373 lbm->lbm_buckets[bucket] = tmp_buckets[jj];
374 jj = (jj + 1) % vec_len(tmp_buckets);
382 vec_free(tmp_buckets);
385 static load_balance_map_t*
386 load_balance_map_alloc (const load_balance_path_t *paths)
388 load_balance_map_t *lbm;
393 dpo_pool_barrier_sync (vm, load_balance_map_pool, did_barrier_sync);
394 pool_get_aligned(load_balance_map_pool, lbm, CLIB_CACHE_LINE_BYTES);
395 dpo_pool_barrier_release (vm, did_barrier_sync);
397 clib_memset(lbm, 0, sizeof(*lbm));
399 vec_validate(lbm->lbm_paths, vec_len(paths)-1);
401 vec_foreach_index(ii, paths)
403 lbm->lbm_paths[ii].lbmp_index = paths[ii].path_index;
404 lbm->lbm_paths[ii].lbmp_weight = paths[ii].path_weight;
410 static load_balance_map_t *
411 load_balance_map_init (load_balance_map_t *lbm,
415 lbm->lbm_sum_of_norm_weights = sum_of_weights;
416 vec_validate(lbm->lbm_buckets, n_buckets-1);
418 load_balance_map_db_insert(lbm);
420 load_balance_map_fill(lbm);
422 load_balance_map_logger =
423 vlib_log_register_class ("dpo", "load-balance-map");
429 load_balance_map_destroy (load_balance_map_t *lbm)
431 vec_free(lbm->lbm_paths);
432 vec_free(lbm->lbm_buckets);
433 pool_put(load_balance_map_pool, lbm);
437 load_balance_map_add_or_lock (u32 n_buckets,
439 const load_balance_path_t *paths)
441 load_balance_map_t *tmp, *lbm;
444 tmp = load_balance_map_alloc(paths);
446 lbmi = load_balance_map_db_find(tmp);
448 if (INDEX_INVALID == lbmi)
450 lbm = load_balance_map_init(tmp, n_buckets, sum_of_weights);
454 lbm = load_balance_map_get(lbmi);
455 load_balance_map_destroy(tmp);
460 return (load_balance_map_get_index(lbm));
464 load_balance_map_lock (index_t lbmi)
466 load_balance_map_t *lbm;
468 lbm = load_balance_map_get(lbmi);
474 load_balance_map_unlock (index_t lbmi)
476 load_balance_map_t *lbm;
478 if (INDEX_INVALID == lbmi)
483 lbm = load_balance_map_get(lbmi);
487 if (0 == lbm->lbm_locks)
489 load_balance_map_db_remove(lbm);
490 load_balance_map_destroy(lbm);
495 load_balance_map_path_state_change_walk (fib_node_ptr_t *fptr,
498 load_balance_map_t *lbm;
500 lbm = load_balance_map_get(fptr->fnp_index);
502 load_balance_map_fill(lbm);
504 return (WALK_CONTINUE);
508 * @brief the state of a path has changed (it has no doubt gone down).
509 * This is the trigger to perform a PIC edge cutover and update the maps
510 * to exclude this path.
513 load_balance_map_path_state_change (fib_node_index_t path_index)
518 * re-stripe the buckets for each affect MAP
520 p = hash_get(lb_maps_by_path_index, path_index);
525 fib_node_list_walk(p[0], load_balance_map_path_state_change_walk, NULL);
529 * @brief Make/add a new or lock an existing Load-balance map
532 load_balance_map_module_init (void)
534 load_balance_map_db =
535 hash_create2 (/* elts */ 0,
537 /* value_bytes */ sizeof (index_t),
538 load_balance_map_db_hash_key_sum,
539 load_balance_map_db_hash_key_equal,
540 /* format pair/arg */
543 lb_maps_by_path_index = hash_create(0, sizeof(fib_node_list_t));
547 load_balance_map_show_mem (void)
549 fib_show_memory_usage("Load-Balance Map",
550 pool_elts(load_balance_map_pool),
551 pool_len(load_balance_map_pool),
552 sizeof(load_balance_map_t));
555 static clib_error_t *
556 load_balance_map_show (vlib_main_t * vm,
557 unformat_input_t * input,
558 vlib_cli_command_t * cmd)
560 index_t lbmi = INDEX_INVALID;
562 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
564 if (unformat (input, "%d", &lbmi))
570 if (INDEX_INVALID != lbmi)
572 vlib_cli_output (vm, "%U", format_load_balance_map, lbmi, 0);
576 load_balance_map_t *lbm;
578 pool_foreach (lbm, load_balance_map_pool)
580 vlib_cli_output (vm, "%U", format_load_balance_map,
581 load_balance_map_get_index(lbm), 0);
588 VLIB_CLI_COMMAND (load_balance_map_show_command, static) = {
589 .path = "show load-balance-map",
590 .short_help = "show load-balance-map [<index>]",
591 .function = load_balance_map_show,