Line data Source code
1 : /* SPDX-License-Identifier: Apache-2.0
2 : * Copyright(c) 2022 Cisco Systems, Inc.
3 : */
4 :
5 : #include <cnat/cnat_maglev.h>
6 :
7 : static int
8 0 : cnat_maglev_perm_compare (void *_a, void *_b)
9 : {
10 0 : return *(u64 *) _b - *(u64 *) _a;
11 : }
12 :
13 : /**
14 : * Maglev algorithm implementation. This takes permutation as input,
15 : * with the values of offset & skip for the backends.
16 : * It fills buckets matching the permuntations, provided buckets is
17 : * already of length at least M
18 : */
19 : static void
20 0 : cnat_maglev_shuffle (cnat_maglev_perm_t *permutation, u32 *buckets)
21 : {
22 0 : u32 N, M, i, done = 0;
23 0 : u32 *next = 0;
24 :
25 0 : N = vec_len (permutation);
26 0 : if (N == 0)
27 0 : return;
28 :
29 0 : M = vec_len (buckets);
30 0 : if (M == 0)
31 0 : return;
32 0 : vec_set (buckets, -1);
33 :
34 0 : vec_validate (next, N - 1);
35 0 : vec_zero (next);
36 :
37 : while (1)
38 : {
39 0 : for (i = 0; i < N; i++)
40 : {
41 0 : u32 c = (permutation[i].offset + next[i] * permutation[i].skip) % M;
42 0 : while (buckets[c] != (u32) -1)
43 : {
44 0 : next[i]++;
45 0 : c = (permutation[i].offset + next[i] * permutation[i].skip) % M;
46 : }
47 :
48 0 : buckets[c] = permutation[i].index;
49 0 : next[i]++;
50 0 : done++;
51 :
52 0 : if (done == M)
53 : {
54 0 : vec_free (next);
55 0 : return;
56 : }
57 : }
58 : }
59 : }
60 :
61 : void
62 0 : cnat_translation_init_maglev (cnat_translation_t *ct)
63 : {
64 0 : cnat_maglev_perm_t *permutations = NULL;
65 0 : cnat_main_t *cm = &cnat_main;
66 : cnat_ep_trk_t *trk;
67 0 : u32 backend_index = 0;
68 :
69 0 : if (vec_len (ct->ct_active_paths) == 0)
70 0 : return;
71 :
72 0 : vec_foreach (trk, ct->ct_active_paths)
73 : {
74 : cnat_maglev_perm_t permutation;
75 : u32 h1, h2;
76 :
77 0 : if (AF_IP4 == ip_addr_version (&trk->ct_ep[VLIB_TX].ce_ip))
78 : {
79 : u32 a, b, c;
80 0 : a = ip_addr_v4 (&trk->ct_ep[VLIB_TX].ce_ip).data_u32;
81 0 : b = (u64) trk->ct_ep[VLIB_TX].ce_port;
82 0 : c = 0;
83 0 : hash_v3_mix32 (a, b, c);
84 0 : hash_v3_finalize32 (a, b, c);
85 0 : h1 = c;
86 0 : h2 = b;
87 : }
88 : else
89 : {
90 : u64 a, b, c;
91 0 : a = ip_addr_v6 (&trk->ct_ep[VLIB_TX].ce_ip).as_u64[0];
92 0 : b = ip_addr_v6 (&trk->ct_ep[VLIB_TX].ce_ip).as_u64[1];
93 0 : c = (u64) trk->ct_ep[VLIB_TX].ce_port;
94 0 : hash_mix64 (a, b, c);
95 0 : h1 = c;
96 0 : h2 = b;
97 : }
98 :
99 0 : permutation.offset = h1 % cm->maglev_len;
100 0 : permutation.skip = h2 % (cm->maglev_len - 1) + 1;
101 0 : permutation.index = backend_index++;
102 :
103 0 : if (trk->ct_flags & CNAT_TRK_FLAG_TEST_DISABLED)
104 0 : continue;
105 :
106 0 : vec_add1 (permutations, permutation);
107 : }
108 :
109 0 : vec_sort_with_function (permutations, cnat_maglev_perm_compare);
110 :
111 0 : vec_validate (ct->lb_maglev, cm->maglev_len - 1);
112 :
113 0 : cnat_maglev_shuffle (permutations, ct->lb_maglev);
114 :
115 0 : vec_free (permutations);
116 : }
117 :
118 : static int
119 0 : cnat_u32_vec_contains (u32 *v, u32 e)
120 : {
121 : int i;
122 :
123 0 : vec_foreach_index (i, v)
124 0 : if (v[i] == e)
125 0 : return 1;
126 :
127 0 : return 0;
128 : }
129 :
130 : static void
131 0 : cnat_maglev_print_changes (vlib_main_t *vm, u32 *changed_bk_indices,
132 : u32 *old_maglev_lb, u32 *new_maglev_lb)
133 : {
134 0 : u32 good_flow_buckets = 0, reset_flow_buckets = 0, stable_to_reset = 0;
135 0 : u32 reset_to_stable = 0, switched_stable = 0;
136 0 : if (vec_len (new_maglev_lb) == 0)
137 0 : return;
138 0 : for (u32 i = 0; i < vec_len (new_maglev_lb); i++)
139 : {
140 0 : u8 is_new_changed =
141 0 : cnat_u32_vec_contains (changed_bk_indices, new_maglev_lb[i]);
142 0 : u8 is_old_changed =
143 0 : cnat_u32_vec_contains (changed_bk_indices, old_maglev_lb[i]);
144 0 : if (new_maglev_lb[i] == old_maglev_lb[i])
145 : {
146 0 : if (is_new_changed)
147 0 : reset_flow_buckets++;
148 : else
149 0 : good_flow_buckets++;
150 : }
151 : else
152 : {
153 0 : if (is_new_changed)
154 0 : stable_to_reset++;
155 0 : else if (is_old_changed)
156 0 : reset_to_stable++;
157 : else
158 0 : switched_stable++;
159 : }
160 : }
161 0 : vlib_cli_output (vm,
162 : "good B->B:%d | lost A->A':%d A->B:%d ~%0.2f%% | bad "
163 : "B->A':%d B->C:%d ~%0.2f%%",
164 : good_flow_buckets, reset_flow_buckets, reset_to_stable,
165 0 : (f64) (reset_flow_buckets + reset_to_stable) /
166 0 : vec_len (new_maglev_lb) * 100.0,
167 : stable_to_reset, switched_stable,
168 0 : (f64) (stable_to_reset + switched_stable) /
169 0 : vec_len (new_maglev_lb) * 100.0);
170 : }
171 :
172 : static u8 *
173 0 : format_cnat_maglev_buckets (u8 *s, va_list *args)
174 : {
175 0 : u32 *buckets = va_arg (*args, u32 *);
176 0 : u32 backend_idx = va_arg (*args, u32);
177 0 : u32 count = va_arg (*args, u32);
178 :
179 0 : for (u32 ii = 0; ii < vec_len (buckets); ii++)
180 0 : if (buckets[ii] == backend_idx)
181 : {
182 0 : s = format (s, "%d,", ii);
183 0 : if (--count == 0)
184 0 : return (s);
185 : }
186 0 : return (s);
187 : }
188 :
189 : static clib_error_t *
190 0 : cnat_translation_test_init_maglev (vlib_main_t *vm, unformat_input_t *input,
191 : vlib_cli_command_t *cmd)
192 : {
193 0 : cnat_translation_t *trs = 0, *ct;
194 0 : u64 num_backends = 0, n_tests = 0;
195 0 : cnat_main_t *cm = &cnat_main;
196 : cnat_ep_trk_t *trk;
197 : u32 rnd;
198 0 : u32 n_changes = 0, n_remove = 0, verbose = 0;
199 :
200 0 : while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
201 : {
202 0 : if (unformat (input, "tests %d", &n_tests))
203 : ;
204 0 : else if (unformat (input, "backends %d", &num_backends))
205 : ;
206 0 : else if (unformat (input, "len %d", &cm->maglev_len))
207 : ;
208 0 : else if (unformat (input, "change %d", &n_changes))
209 : ;
210 0 : else if (unformat (input, "rm %d", &n_remove))
211 : ;
212 0 : else if (unformat (input, "verbose %d", &verbose))
213 : ;
214 : else
215 0 : return (clib_error_return (0, "unknown input '%U'",
216 : format_unformat_error, input));
217 : }
218 :
219 0 : if (num_backends == 0 || n_tests == 0)
220 0 : return (clib_error_return (0, "No backends / tests to run"));
221 : ;
222 :
223 0 : vlib_cli_output (vm, "generating random backends...");
224 0 : rnd = random_default_seed ();
225 :
226 0 : vec_validate (trs, n_tests - 1);
227 0 : vec_foreach (ct, trs)
228 : {
229 0 : vec_validate (ct->ct_active_paths, num_backends - 1);
230 0 : vec_foreach (trk, ct->ct_active_paths)
231 : {
232 0 : trk->ct_flags = 0;
233 0 : ip_addr_version (&trk->ct_ep[VLIB_TX].ce_ip) = AF_IP4;
234 0 : ip_addr_v4 (&trk->ct_ep[VLIB_TX].ce_ip).data_u32 = random_u32 (&rnd);
235 0 : trk->ct_ep[VLIB_TX].ce_port = random_u32 (&rnd);
236 : }
237 : }
238 :
239 0 : vlib_cli_output (vm, "testing...");
240 0 : f64 start_time = vlib_time_now (vm);
241 0 : vec_foreach (ct, trs)
242 0 : cnat_translation_init_maglev (ct);
243 0 : f64 d = vlib_time_now (vm) - start_time;
244 :
245 0 : vlib_cli_output (vm, "Test took : %U", format_duration, d);
246 0 : vlib_cli_output (vm, "Per pool : %U", format_duration, d / n_tests);
247 :
248 : /* sanity checking of the output */
249 0 : u32 *backend_freqs = 0;
250 0 : vec_validate (backend_freqs, num_backends - 1);
251 0 : vec_foreach (ct, trs)
252 : {
253 0 : if (vec_len (ct->lb_maglev) != cm->maglev_len)
254 0 : vlib_cli_output (vm, "Unexpected bucket length %d",
255 0 : vec_len (ct->lb_maglev));
256 :
257 0 : vec_zero (backend_freqs);
258 0 : for (u32 i = 0; i < vec_len (ct->lb_maglev); i++)
259 : {
260 0 : if (ct->lb_maglev[i] >= num_backends)
261 0 : clib_warning ("out of bound backend");
262 0 : backend_freqs[ct->lb_maglev[i]]++;
263 : }
264 0 : u32 fmin = ~0, fmax = 0;
265 0 : for (u32 i = 0; i < num_backends; i++)
266 : {
267 0 : if (backend_freqs[i] > fmax)
268 0 : fmax = backend_freqs[i];
269 0 : if (backend_freqs[i] < fmin)
270 0 : fmin = backend_freqs[i];
271 : }
272 0 : f64 fdiff = (fmax - fmin);
273 0 : if (fdiff / vec_len (ct->lb_maglev) - 1 > 0.02)
274 0 : vlib_cli_output (vm, "More than 2%% frequency diff (min %d max %d)",
275 : fmin, fmax);
276 : }
277 0 : vec_free (backend_freqs);
278 :
279 0 : int i = 0;
280 0 : if (verbose)
281 0 : vec_foreach (ct, trs)
282 : {
283 0 : vlib_cli_output (vm, "Translation %d", i++);
284 0 : for (u32 i = 0; i < verbose; i++)
285 : {
286 0 : u32 j = random_u32 (&rnd) % vec_len (ct->ct_active_paths);
287 0 : trk = &ct->ct_active_paths[j];
288 0 : vlib_cli_output (
289 : vm, "[%03d] %U:%d buckets:%U", j, format_ip_address,
290 0 : &trk->ct_ep[VLIB_TX].ce_ip, trk->ct_ep[VLIB_TX].ce_port,
291 : format_cnat_maglev_buckets, ct->lb_maglev, j, verbose);
292 : }
293 : }
294 :
295 0 : if (n_remove != 0)
296 : {
297 0 : vlib_cli_output (
298 : vm, "Removing %d entries (refered to as A), others (B,C) stay same",
299 : n_remove);
300 0 : vec_foreach (ct, trs)
301 : {
302 0 : u32 *old_maglev_lb = 0;
303 0 : u32 *changed_bk_indices = 0;
304 0 : if (vec_len (ct->lb_maglev) != cm->maglev_len)
305 0 : vlib_cli_output (vm, "Unexpected bucket length %d",
306 0 : vec_len (ct->lb_maglev));
307 :
308 0 : vec_validate (changed_bk_indices, n_remove - 1);
309 0 : for (u32 i = 0; i < n_remove; i++)
310 : {
311 : /* remove n_remove backends from the LB set */
312 0 : changed_bk_indices[i] =
313 0 : random_u32 (&rnd) % vec_len (ct->ct_active_paths);
314 0 : trk = &ct->ct_active_paths[changed_bk_indices[i]];
315 0 : trk->ct_flags |= CNAT_TRK_FLAG_TEST_DISABLED;
316 : }
317 :
318 0 : old_maglev_lb = vec_dup (ct->lb_maglev);
319 0 : cnat_translation_init_maglev (ct);
320 :
321 0 : cnat_maglev_print_changes (vm, changed_bk_indices, old_maglev_lb,
322 : ct->lb_maglev);
323 :
324 0 : vec_free (changed_bk_indices);
325 0 : vec_free (old_maglev_lb);
326 : }
327 : }
328 :
329 : /* Reshuffle and check changes */
330 0 : if (n_changes != 0)
331 : {
332 0 : vlib_cli_output (
333 : vm,
334 : "Changing %d entries (refered to as A->A'), others (B,C) stay same",
335 : n_changes);
336 0 : vec_foreach (ct, trs)
337 : {
338 0 : if (vec_len (ct->lb_maglev) != cm->maglev_len)
339 0 : vlib_cli_output (vm, "Unexpected bucket length %d",
340 0 : vec_len (ct->lb_maglev));
341 :
342 0 : u32 *old_maglev_lb = 0;
343 0 : u32 *changed_bk_indices = 0;
344 :
345 0 : vec_validate (changed_bk_indices, n_changes - 1);
346 0 : for (u32 i = 0; i < n_changes; i++)
347 : {
348 : /* Change n_changes backends in the LB set */
349 0 : changed_bk_indices[i] =
350 0 : random_u32 (&rnd) % vec_len (ct->ct_active_paths);
351 0 : trk = &ct->ct_active_paths[changed_bk_indices[i]];
352 0 : ip_addr_v4 (&trk->ct_ep[VLIB_TX].ce_ip).data_u32 =
353 0 : random_u32 (&rnd);
354 0 : trk->ct_ep[VLIB_TX].ce_port = random_u32 (&rnd) & 0xffff;
355 : }
356 0 : old_maglev_lb = vec_dup (ct->lb_maglev);
357 :
358 0 : cnat_translation_init_maglev (ct);
359 0 : cnat_maglev_print_changes (vm, changed_bk_indices, old_maglev_lb,
360 : ct->lb_maglev);
361 :
362 0 : vec_free (changed_bk_indices);
363 0 : vec_free (old_maglev_lb);
364 : }
365 : }
366 :
367 0 : vec_foreach (ct, trs)
368 0 : vec_free (ct->ct_active_paths);
369 0 : vec_free (trs);
370 :
371 0 : return (NULL);
372 : }
373 :
374 257065 : VLIB_CLI_COMMAND (cnat_translation_test_init_maglev_cmd, static) = {
375 : .path = "test cnat maglev",
376 : .short_help = "test cnat maglev tests [n_tests] backends [num_backends] len "
377 : "[maglev_len]",
378 : .function = cnat_translation_test_init_maglev,
379 : };
|
