src/plugins/cnat/cnat_maglev.c

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