Line data Source code
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 : * the logger
73 : */
74 : vlib_log_class_t load_balance_map_logger;
75 :
76 : /*
77 : * Debug macro
78 : */
79 : #define LOAD_BALANCE_MAP_DBG(_pl, _fmt, _args...) \
80 : { \
81 : vlib_log_debug(load_balance_map_logger, \
82 : "lbm:" _fmt, \
83 : ##_args); \
84 : }
85 :
86 : static index_t
87 1998 : load_balance_map_get_index (load_balance_map_t *lbm)
88 : {
89 1998 : return (lbm - load_balance_map_pool);
90 : }
91 :
92 : u8*
93 4 : format_load_balance_map (u8 *s, va_list * ap)
94 : {
95 4 : index_t lbmi = va_arg(*ap, index_t);
96 4 : u32 indent = va_arg(*ap, u32);
97 : load_balance_map_t *lbm;
98 : u32 n_buckets, ii;
99 :
100 4 : lbm = load_balance_map_get(lbmi);
101 4 : n_buckets = vec_len(lbm->lbm_buckets);
102 :
103 4 : s = format(s, "load-balance-map: index:%d buckets:%d", lbmi, n_buckets);
104 4 : s = format(s, "\n%U index:", format_white_space, indent+2);
105 12 : for (ii = 0; ii < n_buckets; ii++)
106 : {
107 8 : s = format(s, "%5d", ii);
108 : }
109 4 : s = format(s, "\n%U map:", format_white_space, indent+2);
110 12 : for (ii = 0; ii < n_buckets; ii++)
111 : {
112 8 : s = format(s, "%5d", lbm->lbm_buckets[ii]);
113 : }
114 :
115 4 : return (s);
116 : }
117 :
118 :
119 : static uword
120 5861 : load_balance_map_hash (load_balance_map_t *lbm)
121 : {
122 : u32 old_lbm_hash, new_lbm_hash, hash;
123 : load_balance_map_path_t *lb_path;
124 :
125 5861 : new_lbm_hash = old_lbm_hash = vec_len(lbm->lbm_paths);
126 :
127 16746 : vec_foreach (lb_path, lbm->lbm_paths)
128 : {
129 10885 : hash = lb_path->lbmp_index;
130 10885 : hash_mix32(hash, old_lbm_hash, new_lbm_hash);
131 : }
132 :
133 5861 : return (new_lbm_hash);
134 : }
135 :
136 : always_inline uword
137 28 : load_balance_map_db_hash_key_from_index (uword index)
138 : {
139 28 : return 1 + 2*index;
140 : }
141 :
142 : always_inline uword
143 7848 : load_balance_map_db_hash_key_is_index (uword key)
144 : {
145 7848 : return key & 1;
146 : }
147 :
148 : always_inline uword
149 1987 : load_balance_map_db_hash_key_2_index (uword key)
150 : {
151 1987 : ASSERT (load_balance_map_db_hash_key_is_index (key));
152 1987 : return key / 2;
153 : }
154 :
155 : static load_balance_map_t*
156 5861 : load_balance_map_db_get_from_hash_key (uword key)
157 : {
158 : load_balance_map_t *lbm;
159 :
160 5861 : if (load_balance_map_db_hash_key_is_index (key))
161 : {
162 : index_t lbm_index;
163 :
164 1987 : lbm_index = load_balance_map_db_hash_key_2_index(key);
165 1987 : lbm = load_balance_map_get(lbm_index);
166 : }
167 : else
168 : {
169 3874 : lbm = uword_to_pointer (key, load_balance_map_t *);
170 : }
171 :
172 5861 : return (lbm);
173 : }
174 :
175 : static uword
176 1971 : load_balance_map_db_hash_key_sum (hash_t * h,
177 : uword key)
178 : {
179 : load_balance_map_t *lbm;
180 :
181 1971 : lbm = load_balance_map_db_get_from_hash_key(key);
182 :
183 1971 : return (load_balance_map_hash(lbm));
184 : }
185 :
186 : static uword
187 1945 : load_balance_map_db_hash_key_equal (hash_t * h,
188 : uword key1,
189 : uword key2)
190 : {
191 : load_balance_map_t *lbm1, *lbm2;
192 :
193 1945 : lbm1 = load_balance_map_db_get_from_hash_key(key1);
194 1945 : lbm2 = load_balance_map_db_get_from_hash_key(key2);
195 :
196 3890 : return (load_balance_map_hash(lbm1) ==
197 1945 : load_balance_map_hash(lbm2));
198 : }
199 :
200 : static index_t
201 1959 : load_balance_map_db_find (load_balance_map_t *lbm)
202 : {
203 : uword *p;
204 :
205 1959 : p = hash_get(load_balance_map_db, lbm);
206 :
207 1959 : if (NULL != p)
208 : {
209 1931 : return p[0];
210 : }
211 :
212 28 : return (FIB_NODE_INDEX_INVALID);
213 : }
214 :
215 : static void
216 14 : load_balance_map_db_insert (load_balance_map_t *lbm)
217 : {
218 : load_balance_map_path_t *lbmp;
219 : fib_node_list_t list;
220 : uword *p;
221 :
222 14 : ASSERT(FIB_NODE_INDEX_INVALID == load_balance_map_db_find(lbm));
223 :
224 : /*
225 : * insert into the DB based on the set of paths.
226 : */
227 14 : 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));
231 :
232 : /*
233 : * insert into each per-path list.
234 : */
235 39 : vec_foreach(lbmp, lbm->lbm_paths)
236 : {
237 25 : p = hash_get(lb_maps_by_path_index, lbmp->lbmp_index);
238 :
239 25 : if (NULL == p)
240 : {
241 12 : list = fib_node_list_create();
242 12 : hash_set(lb_maps_by_path_index, lbmp->lbmp_index, list);
243 : }
244 : else
245 : {
246 13 : list = p[0];
247 : }
248 :
249 25 : lbmp->lbmp_sibling =
250 25 : fib_node_list_push_front(list,
251 : 0, FIB_NODE_TYPE_FIRST,
252 : load_balance_map_get_index(lbm));
253 : }
254 :
255 14 : LOAD_BALANCE_MAP_DBG(lbm, "DB-inserted");
256 14 : }
257 :
258 : static void
259 14 : load_balance_map_db_remove (load_balance_map_t *lbm)
260 : {
261 : load_balance_map_path_t *lbmp;
262 : uword *p;
263 :
264 14 : ASSERT(FIB_NODE_INDEX_INVALID != load_balance_map_db_find(lbm));
265 :
266 14 : hash_unset(load_balance_map_db,
267 : load_balance_map_db_hash_key_from_index(
268 : load_balance_map_get_index(lbm)));
269 :
270 : /*
271 : * remove from each per-path list.
272 : */
273 39 : vec_foreach(lbmp, lbm->lbm_paths)
274 : {
275 25 : p = hash_get(lb_maps_by_path_index, lbmp->lbmp_index);
276 :
277 25 : ALWAYS_ASSERT(NULL != p);
278 :
279 25 : fib_node_list_remove(p[0], lbmp->lbmp_sibling);
280 : }
281 :
282 14 : LOAD_BALANCE_MAP_DBG(lbm, "DB-removed");
283 14 : }
284 :
285 : /**
286 : * @brief from the paths that are usable, fill the Map.
287 : */
288 : static void
289 21 : load_balance_map_fill (load_balance_map_t *lbm)
290 : {
291 : load_balance_map_path_t *lbmp;
292 : u32 n_buckets, bucket, ii, jj;
293 : u16 *tmp_buckets;
294 :
295 21 : tmp_buckets = NULL;
296 21 : n_buckets = vec_len(lbm->lbm_buckets);
297 :
298 : /*
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.
302 : */
303 21 : vec_validate(tmp_buckets, n_buckets-1);
304 :
305 21 : bucket = jj = 0;
306 61 : vec_foreach (lbmp, lbm->lbm_paths)
307 : {
308 40 : if (fib_path_is_resolved(lbmp->lbmp_index))
309 : {
310 79 : for (ii = 0; ii < lbmp->lbmp_weight; ii++)
311 : {
312 50 : tmp_buckets[jj++] = bucket++;
313 : }
314 : }
315 : else
316 : {
317 11 : bucket += lbmp->lbmp_weight;
318 : }
319 : }
320 21 : vec_set_len (tmp_buckets, jj);
321 :
322 : /*
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
326 : */
327 21 : if (jj == n_buckets)
328 : {
329 10 : memcpy(lbm->lbm_buckets,
330 : tmp_buckets,
331 : sizeof(lbm->lbm_buckets[0]) * n_buckets);
332 : }
333 : else
334 : {
335 : /*
336 : * one or more paths are down.
337 : */
338 11 : if (0 == vec_len(tmp_buckets))
339 : {
340 : /*
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
343 : * against only one.
344 : */
345 8 : for (bucket = 0; bucket < n_buckets; bucket++)
346 : {
347 4 : lbm->lbm_buckets[bucket] = bucket;
348 : }
349 : }
350 : else
351 : {
352 7 : bucket = jj = 0;
353 22 : vec_foreach (lbmp, lbm->lbm_paths)
354 : {
355 15 : if (fib_path_is_resolved(lbmp->lbmp_index))
356 : {
357 24 : for (ii = 0; ii < lbmp->lbmp_weight; ii++)
358 : {
359 16 : lbm->lbm_buckets[bucket] = bucket;
360 16 : bucket++;
361 : }
362 : }
363 : else
364 : {
365 : /*
366 : * path is unusable
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.
370 : */
371 19 : for (ii = 0; ii < lbmp->lbmp_weight; ii++)
372 : {
373 12 : lbm->lbm_buckets[bucket] = tmp_buckets[jj];
374 12 : jj = (jj + 1) % vec_len(tmp_buckets);
375 12 : bucket++;
376 : }
377 : }
378 : }
379 : }
380 : }
381 :
382 21 : vec_free(tmp_buckets);
383 21 : }
384 :
385 : static load_balance_map_t*
386 1931 : load_balance_map_alloc (const load_balance_path_t *paths)
387 : {
388 : load_balance_map_t *lbm;
389 : u32 ii;
390 : vlib_main_t *vm;
391 : u8 did_barrier_sync;
392 :
393 1931 : dpo_pool_barrier_sync (vm, load_balance_map_pool, did_barrier_sync);
394 1931 : pool_get_aligned(load_balance_map_pool, lbm, CLIB_CACHE_LINE_BYTES);
395 1931 : dpo_pool_barrier_release (vm, did_barrier_sync);
396 :
397 1931 : clib_memset(lbm, 0, sizeof(*lbm));
398 :
399 1931 : vec_validate(lbm->lbm_paths, vec_len(paths)-1);
400 :
401 5520 : vec_foreach_index(ii, paths)
402 : {
403 3589 : lbm->lbm_paths[ii].lbmp_index = paths[ii].path_index;
404 3589 : lbm->lbm_paths[ii].lbmp_weight = paths[ii].path_weight;
405 : }
406 :
407 1931 : return (lbm);
408 : }
409 :
410 : static load_balance_map_t *
411 14 : load_balance_map_init (load_balance_map_t *lbm,
412 : u32 n_buckets,
413 : u32 sum_of_weights)
414 : {
415 14 : lbm->lbm_sum_of_norm_weights = sum_of_weights;
416 14 : vec_validate(lbm->lbm_buckets, n_buckets-1);
417 :
418 14 : load_balance_map_db_insert(lbm);
419 :
420 14 : load_balance_map_fill(lbm);
421 :
422 14 : load_balance_map_logger =
423 14 : vlib_log_register_class ("dpo", "load-balance-map");
424 :
425 14 : return (lbm);
426 : }
427 :
428 : static void
429 1931 : load_balance_map_destroy (load_balance_map_t *lbm)
430 : {
431 1931 : vec_free(lbm->lbm_paths);
432 1931 : vec_free(lbm->lbm_buckets);
433 1931 : pool_put(load_balance_map_pool, lbm);
434 1931 : }
435 :
436 : index_t
437 1931 : load_balance_map_add_or_lock (u32 n_buckets,
438 : u32 sum_of_weights,
439 : const load_balance_path_t *paths)
440 : {
441 : load_balance_map_t *tmp, *lbm;
442 : index_t lbmi;
443 :
444 1931 : tmp = load_balance_map_alloc(paths);
445 :
446 1931 : lbmi = load_balance_map_db_find(tmp);
447 :
448 1931 : if (INDEX_INVALID == lbmi)
449 : {
450 14 : lbm = load_balance_map_init(tmp, n_buckets, sum_of_weights);
451 : }
452 : else
453 : {
454 1917 : lbm = load_balance_map_get(lbmi);
455 1917 : load_balance_map_destroy(tmp);
456 : }
457 :
458 1931 : lbm->lbm_locks++;
459 :
460 1931 : return (load_balance_map_get_index(lbm));
461 : }
462 :
463 : void
464 2 : load_balance_map_lock (index_t lbmi)
465 : {
466 : load_balance_map_t *lbm;
467 :
468 2 : lbm = load_balance_map_get(lbmi);
469 :
470 2 : lbm->lbm_locks++;
471 2 : }
472 :
473 : void
474 117563 : load_balance_map_unlock (index_t lbmi)
475 : {
476 : load_balance_map_t *lbm;
477 :
478 117563 : if (INDEX_INVALID == lbmi)
479 : {
480 115630 : return;
481 : }
482 :
483 1933 : lbm = load_balance_map_get(lbmi);
484 :
485 1933 : lbm->lbm_locks--;
486 :
487 1933 : if (0 == lbm->lbm_locks)
488 : {
489 14 : load_balance_map_db_remove(lbm);
490 14 : load_balance_map_destroy(lbm);
491 : }
492 : }
493 :
494 : static walk_rc_t
495 7 : load_balance_map_path_state_change_walk (fib_node_ptr_t *fptr,
496 : void *ctx)
497 : {
498 : load_balance_map_t *lbm;
499 :
500 7 : lbm = load_balance_map_get(fptr->fnp_index);
501 :
502 7 : load_balance_map_fill(lbm);
503 :
504 7 : return (WALK_CONTINUE);
505 : }
506 :
507 : /**
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.
511 : */
512 : void
513 80 : load_balance_map_path_state_change (fib_node_index_t path_index)
514 : {
515 : uword *p;
516 :
517 : /*
518 : * re-stripe the buckets for each affect MAP
519 : */
520 80 : p = hash_get(lb_maps_by_path_index, path_index);
521 :
522 80 : if (NULL == p)
523 69 : return;
524 :
525 11 : fib_node_list_walk(p[0], load_balance_map_path_state_change_walk, NULL);
526 : }
527 :
528 : /**
529 : * @brief Make/add a new or lock an existing Load-balance map
530 : */
531 : void
532 575 : load_balance_map_module_init (void)
533 : {
534 575 : load_balance_map_db =
535 575 : hash_create2 (/* elts */ 0,
536 : /* user */ 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 */
541 : 0, 0);
542 :
543 575 : lb_maps_by_path_index = hash_create(0, sizeof(fib_node_list_t));
544 575 : }
545 :
546 : void
547 0 : load_balance_map_show_mem (void)
548 : {
549 0 : fib_show_memory_usage("Load-Balance Map",
550 0 : pool_elts(load_balance_map_pool),
551 0 : pool_len(load_balance_map_pool),
552 : sizeof(load_balance_map_t));
553 0 : }
554 :
555 : static clib_error_t *
556 0 : load_balance_map_show (vlib_main_t * vm,
557 : unformat_input_t * input,
558 : vlib_cli_command_t * cmd)
559 : {
560 0 : index_t lbmi = INDEX_INVALID;
561 :
562 0 : while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
563 : {
564 0 : if (unformat (input, "%d", &lbmi))
565 : ;
566 : else
567 0 : break;
568 : }
569 :
570 0 : if (INDEX_INVALID != lbmi)
571 : {
572 0 : vlib_cli_output (vm, "%U", format_load_balance_map, lbmi, 0);
573 : }
574 : else
575 : {
576 : load_balance_map_t *lbm;
577 :
578 0 : pool_foreach (lbm, load_balance_map_pool)
579 : {
580 0 : vlib_cli_output (vm, "%U", format_load_balance_map,
581 : load_balance_map_get_index(lbm), 0);
582 : }
583 : }
584 :
585 0 : return 0;
586 : }
587 :
588 285289 : 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,
592 : };
|
