FD.io VPP  v17.07-30-g839fa73
Vector Packet Processing
load_balance_map.c
Go to the documentation of this file.
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>
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  */
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  */
37 
39 {
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  */
49 
50  /**
51  * Sibling Index in the list of all maps with this path index
52  */
54 
55  /**
56  * the normalised wegiht of the path
57  */
59 
60  /**
61  * The sate of the path
62  */
63  load_balance_map_path_flags_t lbmp_flags;
65 
66 /**
67  * The global pool of LB maps
68  */
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
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
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 
136 {
137  return 1 + 2*index;
138 }
139 
142 {
143  return key & 1;
144 }
145 
148 {
150  return key / 2;
151 }
152 
153 static load_balance_map_t*
155 {
156  load_balance_map_t *lbm;
157 
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
175  uword key)
176 {
177  load_balance_map_t *lbm;
178 
180 
181  return (load_balance_map_hash(lbm));
182 }
183 
184 static uword
186  uword key1,
187  uword key2)
188 {
189  load_balance_map_t *lbm1, *lbm2;
190 
193 
194  return (load_balance_map_hash(lbm1) ==
195  load_balance_map_hash(lbm2));
196 }
197 
198 static index_t
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
215 {
217  fib_node_list_t list;
218  uword *p;
219 
221 
222  /*
223  * insert into the DB based on the set of paths.
224  */
225  hash_set (load_balance_map_db,
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 =
251  }
252 
253  LOAD_BALANCE_MAP_DBG(lbm, "DB-inserted");
254 }
255 
256 static void
258 {
260  uword *p;
261 
263 
264  hash_unset(load_balance_map_db,
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
288 {
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*
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 *
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 
412 
414 
415  return (lbm);
416 }
417 
418 static void
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
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);
446  }
447 
448  lbm->lbm_locks++;
449 
450  return (load_balance_map_get_index(lbm));
451 }
452 
453 void
455 {
456  load_balance_map_t *lbm;
457 
458  lbm = load_balance_map_get(lbmi);
459 
460  lbm->lbm_locks++;
461 }
462 
463 void
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  {
481  }
482 }
483 
484 static int
486  void *ctx)
487 {
488  load_balance_map_t *lbm;
489 
490  lbm = load_balance_map_get(fptr->fnp_index);
491 
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
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 
516 }
517 
518 /**
519  * @brief Make/add a new or lock an existing Load-balance map
520  */
521 void
523 {
524  load_balance_map_db =
525  hash_create2 (/* elts */ 0,
526  /* user */ 0,
527  /* value_bytes */ sizeof (index_t),
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
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 *
547  unformat_input_t * input,
548  vlib_cli_command_t * cmd)
549 {
550  index_t lbmi = INDEX_INVALID;
551 
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  ({
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 };
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:436
int fib_path_is_resolved(fib_node_index_t path_index)
Definition: fib_path.c:2083
void load_balance_map_unlock(index_t lbmi)
#define vec_foreach_index(var, v)
Iterate over vector indices.
struct load_balance_map_path_t_ * lbm_paths
the vector of paths this MAP represents
index_t load_balance_map_add_or_lock(u32 n_buckets, u32 sum_of_weights, const load_balance_path_t *paths)
#define hash_set(h, key, value)
Definition: hash.h:254
fib_node_index_t path_index
The index of the FIB path.
Definition: load_balance.h:71
static index_t load_balance_map_get_index(load_balance_map_t *lbm)
static uword load_balance_map_db_hash_key_2_index(uword key)
#define hash_unset(h, key)
Definition: hash.h:260
#define NULL
Definition: clib.h:55
void load_balance_map_path_state_change(fib_node_index_t path_index)
the state of a path has changed (it has no doubt gone down).
u32 index_t
A Data-Path Object is an object that represents actions that are applied to packets are they are swit...
Definition: dpo.h:41
enum load_balance_map_path_flags_t_ load_balance_map_path_flags_t
static int load_balance_map_path_state_change_walk(fib_node_ptr_t *fptr, void *ctx)
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:419
void fib_node_list_walk(fib_node_list_t list, fib_node_list_walk_cb_t fn, void *args)
Walk the list of node.
#define pool_len(p)
Number of elements in pool vector.
Definition: pool.h:121
static load_balance_map_t * load_balance_map_get(index_t lbmi)
static index_t load_balance_map_db_find(load_balance_map_t *lbm)
fib_node_index_t fnp_index
node&#39;s index
Definition: fib_node.h:181
void fib_node_list_remove(fib_node_list_t list, u32 sibling)
#define pool_foreach(VAR, POOL, BODY)
Iterate through pool.
Definition: pool.h:376
void load_balance_map_module_init(void)
Make/add a new or lock an existing Load-balance map.
#define always_inline
Definition: clib.h:84
static uword load_balance_map_db_hash_key_is_index(uword key)
u8 * format_white_space(u8 *s, va_list *va)
Definition: std-formats.c:113
static uword load_balance_map_db_hash_key_sum(hash_t *h, uword key)
u32 lbm_sum_of_norm_weights
the sum of the normalised weights.
fib_node_index_t lbmp_index
Index of the path.
void fib_show_memory_usage(const char *name, u32 in_use_elts, u32 allocd_elts, size_t size_elt)
Show the memory usage for a type.
Definition: fib_node.c:221
static uword load_balance_map_db_hash_key_from_index(uword index)
A representation of one pointer to another node.
Definition: fib_node.h:173
load_balance_map_t * load_balance_map_pool
The global pool of LB maps.
#define hash_get(h, key)
Definition: hash.h:248
struct _unformat_input_t unformat_input_t
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:241
static clib_error_t * load_balance_map_show(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
#define LOAD_BALANCE_MAP_DBG(_pl, _fmt, _args...)
u32 fib_node_list_push_front(fib_node_list_t list, int owner_id, fib_node_type_t type, fib_node_index_t index)
Insert an element at the from of the list.
struct load_balance_map_path_t_ load_balance_map_path_t
load_balance_map_path_flags_t lbmp_flags
The sate of the path.
#define uword_to_pointer(u, type)
Definition: types.h:136
void load_balance_map_lock(index_t lbmi)
#define pool_get_aligned(P, E, A)
Allocate an object E from a pool P (general version).
Definition: pool.h:169
static load_balance_map_t * load_balance_map_db_get_from_hash_key(uword key)
#define UNFORMAT_END_OF_INPUT
Definition: format.h:143
load_balance_map_path_flags_t_
static uword load_balance_map_db_hash_key_equal(hash_t *h, uword key1, uword key2)
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:340
void load_balance_map_show_mem(void)
static uword * lb_maps_by_path_index
A hash-table of load-balance maps by path index.
#define hash_mix32(a0, b0, c0)
Definition: hash.h:515
static void load_balance_map_db_insert(load_balance_map_t *lbm)
static load_balance_map_t * load_balance_map_alloc(const load_balance_path_t *paths)
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:28
static void load_balance_map_destroy(load_balance_map_t *lbm)
#define hash_create2(_elts, _user, _value_bytes,_key_sum, _key_equal,_format_pair, _format_pair_arg)
Definition: hash.h:470
#define VLIB_CLI_COMMAND(x,...)
Definition: cli.h:154
#define hash_create(elts, value_bytes)
Definition: hash.h:658
#define ASSERT(truth)
fib_node_list_t fib_node_list_create(void)
Create a new node list.
unsigned int u32
Definition: types.h:88
u16 * lbm_buckets
The buckets of the map that provide the index to index translation.
static void load_balance_map_db_remove(load_balance_map_t *lbm)
static load_balance_map_t * load_balance_map_init(load_balance_map_t *lbm, u32 n_buckets, u32 sum_of_weights)
u64 uword
Definition: types.h:112
u32 lbmp_weight
the normalised wegiht of the path
unsigned short u16
Definition: types.h:57
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:29
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
unsigned char u8
Definition: types.h:56
u32 path_weight
weight for the path.
Definition: load_balance.h:76
#define INDEX_INVALID
Invalid index - used when no index is known blazoned capitals INVALID speak volumes where ~0 does not...
Definition: dpo.h:47
fib_node_index_t lbmp_sibling
Sibling Index in the list of all maps with this path index.
One path from an [EU]CMP set that the client wants to add to a load-balance object.
Definition: load_balance.h:62
u32 fib_node_list_t
A list of FIB nodes.
Definition: fib_node.h:187
static uword load_balance_map_hash(load_balance_map_t *lbm)
#define vec_foreach(var, vec)
Vector iterator.
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:67
u8 * format_load_balance_map(u8 *s, va_list ap)
static uword * load_balance_map_db
A hash-table of load-balance maps by set of paths.
void vlib_cli_output(vlib_main_t *vm, char *fmt,...)
Definition: cli.c:680
u32 lbm_locks
Number of locks.
uword unformat(unformat_input_t *i, const char *fmt,...)
Definition: unformat.c:972
static uword unformat_check_input(unformat_input_t *i)
Definition: format.h:169
static void load_balance_map_fill(load_balance_map_t *lbm)
from the paths that are usable, fill the Map.
static uword pool_elts(void *v)
Number of active elements in a pool.
Definition: pool.h:109