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