vppinfra/vppinfra/test_vec.c

   1 /*
   2  * Copyright (c) 2015 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   Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
  17   Written by Fred Delley <fdelley@cisco.com> .
  18
  19   Permission is hereby granted, free of charge, to any person obtaining
  20   a copy of this software and associated documentation files (the
  21   "Software"), to deal in the Software without restriction, including
  22   without limitation the rights to use, copy, modify, merge, publish,
  23   distribute, sublicense, and/or sell copies of the Software, and to
  24   permit persons to whom the Software is furnished to do so, subject to
  25   the following conditions:
  26
  27   The above copyright notice and this permission notice shall be
  28   included in all copies or substantial portions of the Software.
  29
  30   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  31   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  32   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  33   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  34   LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  35   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  36   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  37 */
  38
  39 #ifdef CLIB_LINUX_KERNEL
  40 #include <linux/unistd.h>
  41 #endif
  42
  43 #ifdef CLIB_UNIX
  44 #include <unistd.h>
  45 #include <stdlib.h>
  46 #include <stdio.h>
  47 #endif
  48
  49 #include <vppinfra/clib.h>
  50 #include <vppinfra/mheap.h>
  51 #include <vppinfra/format.h>
  52 #include <vppinfra/error.h>
  53 #include <vppinfra/random.h>
  54 #include <vppinfra/time.h>
  55
  56 #include "test_vec.h"
  57
  58 static int verbose;
  59 #define if_verbose(format,args...) \
  60   if (verbose) { clib_warning(format, ## args); }
  61
  62 #define MAX_CHANGE 100
  63
  64
  65 typedef enum
  66 {
  67   /* Values have to be sequential and start with 0. */
  68   OP_IS_VEC_RESIZE = 0,
  69   OP_IS_VEC_ADD1,
  70   OP_IS_VEC_ADD2,
  71   OP_IS_VEC_ADD,
  72   OP_IS_VEC_INSERT,
  73   OP_IS_VEC_INSERT_ELTS,
  74   OP_IS_VEC_DELETE,
  75   OP_IS_VEC_DUP,
  76   OP_IS_VEC_IS_EQUAL,
  77   OP_IS_VEC_ZERO,
  78   OP_IS_VEC_SET,
  79   OP_IS_VEC_VALIDATE,
  80   OP_IS_VEC_FREE,
  81   OP_IS_VEC_INIT,
  82   OP_IS_VEC_CLONE,
  83   OP_IS_VEC_APPEND,
  84   OP_IS_VEC_PREPEND,
  85   /* Operations on vectors with custom headers. */
  86   OP_IS_VEC_INIT_H,
  87   OP_IS_VEC_RESIZE_H,
  88   OP_IS_VEC_FREE_H,
  89   OP_MAX,
  90 } op_t;
  91
  92 #define FIRST_VEC_OP            OP_IS_VEC_RESIZE
  93 #define LAST_VEC_OP             OP_IS_VEC_PREPEND
  94 #define FIRST_VEC_HDR_OP        OP_IS_VEC_INIT_H
  95 #define LAST_VEC_HDR_OP         OP_IS_VEC_FREE_H
  96
  97 uword g_prob_ratio[] = {
  98   [OP_IS_VEC_RESIZE] = 5,
  99   [OP_IS_VEC_ADD1] = 5,
 100   [OP_IS_VEC_ADD2] = 5,
 101   [OP_IS_VEC_ADD] = 5,
 102   [OP_IS_VEC_INSERT] = 5,
 103   [OP_IS_VEC_INSERT_ELTS] = 5,
 104   [OP_IS_VEC_DELETE] = 30,
 105   [OP_IS_VEC_DUP] = 5,
 106   [OP_IS_VEC_IS_EQUAL] = 5,
 107   [OP_IS_VEC_ZERO] = 2,
 108   [OP_IS_VEC_SET] = 3,
 109   [OP_IS_VEC_VALIDATE] = 5,
 110   [OP_IS_VEC_FREE] = 5,
 111   [OP_IS_VEC_INIT] = 5,
 112   [OP_IS_VEC_CLONE] = 5,
 113   [OP_IS_VEC_APPEND] = 5,
 114   [OP_IS_VEC_PREPEND] = 5,
 115   /* Operations on vectors with custom headers. */
 116   [OP_IS_VEC_INIT_H] = 5,
 117   [OP_IS_VEC_RESIZE_H] = 5,
 118   [OP_IS_VEC_FREE_H] = 5,
 119 };
 120
 121 op_t *g_prob;
 122 op_t *g_prob_wh;
 123
 124 uword g_call_stats[OP_MAX];
 125
 126
 127 /* A structure for both vector headers and vector elements might be useful to
 128    uncover potential alignement issues. */
 129
 130 typedef struct
 131 {
 132   u8 field1[4];
 133     CLIB_PACKED (u32 field2);
 134 } hdr_t;
 135
 136 typedef struct
 137 {
 138   u8 field1[3];
 139     CLIB_PACKED (u32 field2);
 140 } elt_t;
 141
 142 #ifdef CLIB_UNIX
 143 u32 g_seed = 0xdeadbabe;
 144 uword g_verbose = 1;
 145 #endif
 146
 147 op_t *g_op_prob;
 148 uword g_set_verbose_at = ~0;
 149 uword g_dump_period = ~0;
 150
 151
 152 static u8 *
 153 format_vec_op_type (u8 * s, va_list * args)
 154 {
 155   op_t op = va_arg (*args, int);
 156
 157   switch (op)
 158     {
 159 #define _(n)                                    \
 160       case OP_IS_##n:                           \
 161         s = format (s, "OP_IS_" #n);            \
 162         break;
 163
 164       _(VEC_RESIZE);
 165       _(VEC_ADD1);
 166       _(VEC_ADD2);
 167       _(VEC_ADD);
 168       _(VEC_INSERT);
 169       _(VEC_INSERT_ELTS);
 170       _(VEC_DELETE);
 171       _(VEC_DUP);
 172       _(VEC_IS_EQUAL);
 173       _(VEC_ZERO);
 174       _(VEC_SET);
 175       _(VEC_VALIDATE);
 176       _(VEC_FREE);
 177       _(VEC_INIT);
 178       _(VEC_CLONE);
 179       _(VEC_APPEND);
 180       _(VEC_PREPEND);
 181       _(VEC_INIT_H);
 182       _(VEC_RESIZE_H);
 183       _(VEC_FREE_H);
 184
 185     default:
 186       s = format (s, "Unknown vec op (%d)", op);
 187       break;
 188     }
 189
 190 #undef _
 191
 192   return s;
 193 }
 194
 195 static void
 196 dump_call_stats (uword * stats)
 197 {
 198   uword i;
 199
 200   fformat (stdout, "Call Stats\n----------\n");
 201
 202   for (i = 0; i < OP_MAX; i++)
 203     fformat (stdout, "%-8d %U\n", stats[i], format_vec_op_type, i);
 204 }
 205
 206
 207 /* XXX - Purposely low value for debugging the validator. Will be set it to a
 208    more sensible value later. */
 209 #define MAX_VEC_LEN 10
 210
 211 #define create_random_vec_wh(elt_type, len, hdr_bytes, seed)                    \
 212 ({                                                                              \
 213   elt_type * _v(v) = NULL;                                                      \
 214   uword _v(l) = (len);                                                          \
 215   uword _v(h) = (hdr_bytes);                                                    \
 216   u8 * _v(hdr);                                                                 \
 217                                                                                 \
 218   if (_v(l) == 0)                                                               \
 219     goto __done__;                                                              \
 220                                                                                 \
 221   /* ~0 means select random length between 0 and MAX_VEC_LEN. */                \
 222   if (_v(l) == ~0)                                                              \
 223     _v(l) = bounded_random_u32 (&(seed), 0, MAX_VEC_LEN);                       \
 224                                                                                 \
 225   _v(v) = _vec_resize (NULL, _v(l), _v(l) * sizeof (elt_type), _v(h), 0);       \
 226   fill_with_random_data (_v(v), vec_bytes (_v(v)), (seed));                     \
 227                                                                                 \
 228   /* Fill header with random data as well. */                                   \
 229   if (_v(h) > 0)                                                                \
 230     {                                                                           \
 231       _v(hdr) = vec_header (_v(v), _v(h));                                      \
 232       fill_with_random_data (_v(hdr), _v(h), (seed));                           \
 233     }                                                                           \
 234                                                                                 \
 235 __done__:                                                                       \
 236   _v(v);                                                                        \
 237 })
 238
 239 #define create_random_vec(elt_type, len, seed) \
 240 create_random_vec_wh (elt_type, len, 0, seed)
 241
 242 #define compute_vec_hash(hash, vec)                     \
 243 ({                                                      \
 244   u8 * _v(v) = (u8 *) (vec);                            \
 245   uword _v(n) = vec_len (vec) * sizeof ((vec)[0]);      \
 246   u8 _v(hh) = (u8) (hash);                              \
 247                                                         \
 248   compute_mem_hash (_v(hh), _v(v), _v(n));              \
 249 })
 250
 251 static elt_t *
 252 validate_vec_free (elt_t * vec)
 253 {
 254   vec_free (vec);
 255   ASSERT (vec == NULL);
 256   return vec;
 257 }
 258
 259 static elt_t *
 260 validate_vec_free_h (elt_t * vec, uword hdr_bytes)
 261 {
 262   vec_free_h (vec, hdr_bytes);
 263   ASSERT (vec == NULL);
 264   return vec;
 265 }
 266
 267 static void
 268 validate_vec_hdr (elt_t * vec, uword hdr_bytes)
 269 {
 270   u8 *hdr;
 271   u8 *hdr_end;
 272   vec_header_t *vh;
 273
 274   if (!vec)
 275     return;
 276
 277   vh = _vec_find (vec);
 278   hdr = vec_header (vec, hdr_bytes);
 279   hdr_end = vec_header_end (hdr, hdr_bytes);
 280
 281   ASSERT (hdr_end == (u8 *) vec);
 282   ASSERT ((u8 *) vh - (u8 *) hdr >= hdr_bytes);
 283 }
 284
 285 static void
 286 validate_vec_len (elt_t * vec)
 287 {
 288   u8 *ptr;
 289   u8 *end;
 290   uword len;
 291   uword bytes;
 292   uword i;
 293   elt_t *elt;
 294
 295   if (!vec)
 296     return;
 297
 298   ptr = (u8 *) vec;
 299   end = (u8 *) vec_end (vec);
 300   len = vec_len (vec);
 301   bytes = sizeof (vec[0]) * len;
 302
 303   ASSERT (bytes == vec_bytes (vec));
 304   ASSERT ((ptr + bytes) == end);
 305
 306   i = 0;
 307
 308   /* XXX - TODO: confirm that auto-incrementing in vec_is_member() would not
 309      have the expected result. */
 310   while (vec_is_member (vec, (__typeof__ (vec[0]) *) ptr))
 311     {
 312       ptr++;
 313       i++;
 314     }
 315
 316   ASSERT (ptr == end);
 317   ASSERT (i == bytes);
 318
 319   i = 0;
 320
 321   vec_foreach (elt, vec) i++;
 322
 323   ASSERT (i == len);
 324 }
 325
 326 static void
 327 validate_vec (elt_t * vec, uword hdr_bytes)
 328 {
 329   validate_vec_hdr (vec, hdr_bytes);
 330   validate_vec_len (vec);
 331
 332   if (!vec || vec_len (vec) == 0)
 333     {
 334       VERBOSE3 ("Vector at %p has zero elements.\n\n", vec);
 335     }
 336   else
 337     {
 338       if (hdr_bytes > 0)
 339         VERBOSE3 ("Header: %U\n",
 340                   format_hex_bytes, vec_header (vec, sizeof (vec[0])),
 341                   sizeof (vec[0]));
 342
 343       VERBOSE3 ("%U\n\n",
 344                 format_hex_bytes, vec, vec_len (vec) * sizeof (vec[0]));
 345     }
 346 }
 347
 348 static elt_t *
 349 validate_vec_resize (elt_t * vec, uword num_elts)
 350 {
 351   uword len1 = vec_len (vec);
 352   uword len2;
 353   u8 hash = compute_vec_hash (0, vec);
 354
 355   vec_resize (vec, num_elts);
 356   len2 = vec_len (vec);
 357
 358   ASSERT (len2 == len1 + num_elts);
 359   ASSERT (compute_vec_hash (hash, vec) == 0);
 360   validate_vec (vec, 0);
 361   return vec;
 362 }
 363
 364 static elt_t *
 365 validate_vec_resize_h (elt_t * vec, uword num_elts, uword hdr_bytes)
 366 {
 367   uword len1, len2;
 368   u8 *end1, *end2;
 369   u8 *hdr = NULL;
 370   u8 hash, hdr_hash;
 371
 372   len1 = vec_len (vec);
 373
 374   if (vec)
 375     hdr = vec_header (vec, hdr_bytes);
 376
 377   hash = compute_vec_hash (0, vec);
 378   hdr_hash = compute_mem_hash (0, hdr, hdr_bytes);
 379
 380   vec_resize_ha (vec, num_elts, hdr_bytes, 0);
 381   len2 = vec_len (vec);
 382
 383   ASSERT (len2 == len1 + num_elts);
 384
 385   end1 = (u8 *) (vec + len1);
 386   end2 = (u8 *) vec_end (vec);
 387
 388   while (end1 != end2)
 389     {
 390       ASSERT (*end1 == 0);
 391       end1++;
 392     }
 393
 394   if (vec)
 395     hdr = vec_header (vec, hdr_bytes);
 396
 397   ASSERT (compute_vec_hash (hash, vec) == 0);
 398   ASSERT (compute_mem_hash (hdr_hash, hdr, hdr_bytes) == 0);
 399   validate_vec (vec, 1);
 400   return vec;
 401 }
 402
 403 static elt_t *
 404 generic_validate_vec_add (elt_t * vec, uword num_elts, uword is_add2)
 405 {
 406   uword len1 = vec_len (vec);
 407   uword len2;
 408   u8 hash = compute_vec_hash (0, vec);
 409   elt_t *new;
 410
 411   if (is_add2)
 412     {
 413       vec_add2 (vec, new, num_elts);
 414     }
 415   else
 416     {
 417       new = create_random_vec (elt_t, num_elts, g_seed);
 418
 419       VERBOSE3 ("%U\n", format_hex_bytes, new,
 420                 vec_len (new) * sizeof (new[0]));
 421
 422       /* Add the hash value of the new elements to that of the old vector. */
 423       hash = compute_vec_hash (hash, new);
 424
 425       if (num_elts == 1)
 426         vec_add1 (vec, new[0]);
 427       else if (num_elts > 1)
 428         vec_add (vec, new, num_elts);
 429
 430       vec_free (new);
 431     }
 432
 433   len2 = vec_len (vec);
 434   ASSERT (len2 == len1 + num_elts);
 435
 436   ASSERT (compute_vec_hash (hash, vec) == 0);
 437   validate_vec (vec, 0);
 438   return vec;
 439 }
 440
 441 static elt_t *
 442 validate_vec_add1 (elt_t * vec)
 443 {
 444   return generic_validate_vec_add (vec, 1, 0);
 445 }
 446
 447 static elt_t *
 448 validate_vec_add2 (elt_t * vec, uword num_elts)
 449 {
 450   return generic_validate_vec_add (vec, num_elts, 1);
 451 }
 452
 453 static elt_t *
 454 validate_vec_add (elt_t * vec, uword num_elts)
 455 {
 456   return generic_validate_vec_add (vec, num_elts, 0);
 457 }
 458
 459 static elt_t *
 460 validate_vec_insert (elt_t * vec, uword num_elts, uword start_elt)
 461 {
 462   uword len1 = vec_len (vec);
 463   uword len2;
 464   u8 hash;
 465
 466   /* vec_insert() would not handle it properly. */
 467   if (start_elt > len1 || num_elts == 0)
 468     return vec;
 469
 470   hash = compute_vec_hash (0, vec);
 471   vec_insert (vec, num_elts, start_elt);
 472   len2 = vec_len (vec);
 473
 474   ASSERT (len2 == len1 + num_elts);
 475   ASSERT (compute_vec_hash (hash, vec) == 0);
 476   validate_vec (vec, 0);
 477   return vec;
 478 }
 479
 480 static elt_t *
 481 validate_vec_insert_elts (elt_t * vec, uword num_elts, uword start_elt)
 482 {
 483   uword len1 = vec_len (vec);
 484   uword len2;
 485   elt_t *new;
 486   u8 hash;
 487
 488   /* vec_insert_elts() would not handle it properly. */
 489   if (start_elt > len1 || num_elts == 0)
 490     return vec;
 491
 492   new = create_random_vec (elt_t, num_elts, g_seed);
 493
 494   VERBOSE3 ("%U\n", format_hex_bytes, new, vec_len (new) * sizeof (new[0]));
 495
 496   /* Add the hash value of the new elements to that of the old vector. */
 497   hash = compute_vec_hash (0, vec);
 498   hash = compute_vec_hash (hash, new);
 499
 500   vec_insert_elts (vec, new, num_elts, start_elt);
 501   len2 = vec_len (vec);
 502
 503   vec_free (new);
 504
 505   ASSERT (len2 == len1 + num_elts);
 506   ASSERT (compute_vec_hash (hash, vec) == 0);
 507   validate_vec (vec, 0);
 508   return vec;
 509 }
 510
 511 static elt_t *
 512 validate_vec_delete (elt_t * vec, uword num_elts, uword start_elt)
 513 {
 514   uword len1 = vec_len (vec);
 515   uword len2;
 516   u8 *start;
 517   u8 hash;
 518   u8 hash_del;
 519
 520   /* vec_delete() would not handle it properly. */
 521   if (start_elt + num_elts > len1)
 522     return vec;
 523
 524   start = (u8 *) vec + (start_elt * sizeof (vec[0]));
 525
 526   hash = compute_vec_hash (0, vec);
 527   hash_del = compute_mem_hash (0, start, num_elts * sizeof (vec[0]));
 528   hash ^= hash_del;
 529
 530   vec_delete (vec, num_elts, start_elt);
 531   len2 = vec_len (vec);
 532
 533   ASSERT (len2 == len1 - num_elts);
 534   ASSERT (compute_vec_hash (hash, vec) == 0);
 535   validate_vec (vec, 0);
 536   return vec;
 537 }
 538
 539 static elt_t *
 540 validate_vec_dup (elt_t * vec)
 541 {
 542   elt_t *new;
 543   u8 hash;
 544
 545   hash = compute_vec_hash (0, vec);
 546   new = vec_dup (vec);
 547
 548   ASSERT (compute_vec_hash (hash, new) == 0);
 549
 550   validate_vec (new, 0);
 551   return new;
 552 }
 553
 554 static elt_t *
 555 validate_vec_zero (elt_t * vec)
 556 {
 557   u8 *ptr;
 558   u8 *end;
 559
 560   vec_zero (vec);
 561
 562   ptr = (u8 *) vec;
 563   end = (u8 *) (vec + vec_len (vec));
 564
 565   while (ptr != end)
 566     {
 567       ASSERT (ptr < (u8 *) vec_end (vec));
 568       ASSERT (ptr[0] == 0);
 569       ptr++;
 570     }
 571
 572   validate_vec (vec, 0);
 573   return vec;
 574 }
 575
 576 static void
 577 validate_vec_is_equal (elt_t * vec)
 578 {
 579   elt_t *new = NULL;
 580
 581   if (vec_len (vec) <= 0)
 582     return;
 583
 584   new = vec_dup (vec);
 585   ASSERT (vec_is_equal (new, vec));
 586   vec_free (new);
 587 }
 588
 589 static elt_t *
 590 validate_vec_set (elt_t * vec)
 591 {
 592   uword i;
 593   uword len = vec_len (vec);
 594   elt_t *new;
 595
 596   if (!vec)
 597     return NULL;
 598
 599   new = create_random_vec (elt_t, 1, g_seed);
 600
 601   VERBOSE3 ("%U\n", format_hex_bytes, new, vec_len (new) * sizeof (new[0]));
 602
 603   vec_set (vec, new[0]);
 604
 605   for (i = 0; i < len; i++)
 606     ASSERT (memcmp (&vec[i], &new[0], sizeof (vec[0])) == 0);
 607
 608   vec_free (new);
 609   validate_vec (vec, 0);
 610   return vec;
 611 }
 612
 613 static elt_t *
 614 validate_vec_validate (elt_t * vec, uword index)
 615 {
 616   uword len = vec_len (vec);
 617   word num_new = index - len + 1;
 618   u8 *ptr;
 619   u8 *end;
 620   u8 hash = compute_vec_hash (0, vec);
 621
 622   if (num_new < 0)
 623     num_new = 0;
 624
 625   vec_validate (vec, index);
 626
 627   /* Old len but new vec pointer! */
 628   ptr = (u8 *) (vec + len);
 629   end = (u8 *) (vec + len + num_new);
 630
 631   ASSERT (len + num_new == vec_len (vec));
 632   ASSERT (compute_vec_hash (hash, vec) == 0);
 633
 634   while (ptr != end)
 635     {
 636       ASSERT (ptr < (u8 *) vec_end (vec));
 637       ASSERT (ptr[0] == 0);
 638       ptr++;
 639     }
 640
 641   validate_vec (vec, 0);
 642   return vec;
 643 }
 644
 645 static elt_t *
 646 validate_vec_init (uword num_elts)
 647 {
 648   u8 *ptr;
 649   u8 *end;
 650   uword len;
 651   elt_t *new;
 652
 653   new = vec_new (elt_t, num_elts);
 654   len = vec_len (new);
 655
 656   ASSERT (len == num_elts);
 657
 658   ptr = (u8 *) new;
 659   end = (u8 *) (new + len);
 660
 661   while (ptr != end)
 662     {
 663       ASSERT (ptr < (u8 *) vec_end (new));
 664       ASSERT (ptr[0] == 0);
 665       ptr++;
 666     }
 667
 668   validate_vec (new, 0);
 669   return new;
 670 }
 671
 672 static elt_t *
 673 validate_vec_init_h (uword num_elts, uword hdr_bytes)
 674 {
 675   uword i = 0;
 676   u8 *ptr;
 677   u8 *end;
 678   uword len;
 679   elt_t *new;
 680
 681   new = vec_new_ha (elt_t, num_elts, hdr_bytes, 0);
 682   len = vec_len (new);
 683
 684   ASSERT (len == num_elts);
 685
 686   /* We have 2 zero-regions to check: header & vec data (skip _VEC struct). */
 687   for (i = 0; i < 2; i++)
 688     {
 689       if (i == 0)
 690         {
 691           ptr = (u8 *) vec_header (new, hdr_bytes);
 692           end = ptr + hdr_bytes;
 693         }
 694       else
 695         {
 696           ptr = (u8 *) new;
 697           end = (u8 *) (new + len);
 698         }
 699
 700       while (ptr != end)
 701         {
 702           ASSERT (ptr < (u8 *) vec_end (new));
 703           ASSERT (ptr[0] == 0);
 704           ptr++;
 705         }
 706     }
 707
 708   validate_vec (new, 1);
 709   return new;
 710 }
 711
 712 /* XXX - I don't understand the purpose of the vec_clone() call. */
 713 static elt_t *
 714 validate_vec_clone (elt_t * vec)
 715 {
 716   elt_t *new;
 717
 718   vec_clone (new, vec);
 719
 720   ASSERT (vec_len (new) == vec_len (vec));
 721   ASSERT (compute_vec_hash (0, new) == 0);
 722   validate_vec (new, 0);
 723   return new;
 724 }
 725
 726 static elt_t *
 727 validate_vec_append (elt_t * vec)
 728 {
 729   elt_t *new;
 730   uword num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 731   uword len;
 732   u8 hash = 0;
 733
 734   new = create_random_vec (elt_t, num_elts, g_seed);
 735
 736   len = vec_len (vec) + vec_len (new);
 737   hash = compute_vec_hash (0, vec);
 738   hash = compute_vec_hash (hash, new);
 739
 740   vec_append (vec, new);
 741   vec_free (new);
 742
 743   ASSERT (vec_len (vec) == len);
 744   ASSERT (compute_vec_hash (hash, vec) == 0);
 745   validate_vec (vec, 0);
 746   return vec;
 747 }
 748
 749 static elt_t *
 750 validate_vec_prepend (elt_t * vec)
 751 {
 752   elt_t *new;
 753   uword num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 754   uword len;
 755   u8 hash = 0;
 756
 757   new = create_random_vec (elt_t, num_elts, g_seed);
 758
 759   len = vec_len (vec) + vec_len (new);
 760   hash = compute_vec_hash (0, vec);
 761   hash = compute_vec_hash (hash, new);
 762
 763   vec_prepend (vec, new);
 764   vec_free (new);
 765
 766   ASSERT (vec_len (vec) == len);
 767   ASSERT (compute_vec_hash (hash, vec) == 0);
 768   validate_vec (vec, 0);
 769   return vec;
 770 }
 771
 772 static void
 773 run_validator_wh (uword iter)
 774 {
 775   elt_t *vec;
 776   uword i;
 777   uword op;
 778   uword num_elts;
 779   uword len;
 780   uword dump_time;
 781   f64 time[3];                  /* [0]: start, [1]: last, [2]: current */
 782
 783   vec = create_random_vec_wh (elt_t, ~0, sizeof (hdr_t), g_seed);
 784   validate_vec (vec, 0);
 785   VERBOSE2 ("Start with len %d\n", vec_len (vec));
 786
 787   time[0] = unix_time_now ();
 788   time[1] = time[0];
 789   dump_time = g_dump_period;
 790
 791   for (i = 1; i <= iter; i++)
 792     {
 793       if (i >= g_set_verbose_at)
 794         g_verbose = 2;
 795
 796       op = bounded_random_u32 (&g_seed, 0, vec_len (g_prob_wh) - 1);
 797       op = g_prob_wh[op];
 798
 799       switch (op)
 800         {
 801         case OP_IS_VEC_INIT_H:
 802           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 803           vec_free_h (vec, sizeof (hdr_t));
 804           VERBOSE2 ("vec_init_h(), new elts %d\n", num_elts);
 805           vec = validate_vec_init_h (num_elts, sizeof (hdr_t));
 806           break;
 807
 808         case OP_IS_VEC_RESIZE_H:
 809           len = vec_len (vec);
 810           num_elts = bounded_random_u32 (&g_seed, len, len + MAX_CHANGE);
 811           VERBOSE2 ("vec_resize_h(), %d new elts.\n", num_elts);
 812           vec = validate_vec_resize_h (vec, num_elts, sizeof (hdr_t));
 813           break;
 814
 815         case OP_IS_VEC_FREE_H:
 816           VERBOSE2 ("vec_free_h()\n");
 817           vec = validate_vec_free_h (vec, sizeof (hdr_t));
 818           break;
 819
 820         default:
 821           ASSERT (0);
 822           break;
 823         }
 824
 825       g_call_stats[op]++;
 826
 827       if (i == dump_time)
 828         {
 829           time[2] = unix_time_now ();
 830           VERBOSE1 ("%d vec ops in %f secs. (last %d in %f secs.).\n",
 831                     i, time[2] - time[0], g_dump_period, time[2] - time[1]);
 832           time[1] = time[2];
 833           dump_time += g_dump_period;
 834
 835           VERBOSE1 ("vec len %d\n", vec_len (vec));
 836           VERBOSE2 ("%U\n\n",
 837                     format_hex_bytes, vec, vec_len (vec) * sizeof (vec[0]));
 838         }
 839
 840       VERBOSE2 ("len %d\n", vec_len (vec));
 841     }
 842
 843   validate_vec (vec, sizeof (hdr_t));
 844   vec_free_h (vec, sizeof (hdr_t));
 845 }
 846
 847 static void
 848 run_validator (uword iter)
 849 {
 850   elt_t *vec;
 851   elt_t *new;
 852   uword i;
 853   uword op;
 854   uword num_elts;
 855   uword index;
 856   uword len;
 857   uword dump_time;
 858   f64 time[3];                  /* [0]: start, [1]: last, [2]: current */
 859
 860   vec = create_random_vec (elt_t, ~0, g_seed);
 861   validate_vec (vec, 0);
 862   VERBOSE2 ("Start with len %d\n", vec_len (vec));
 863
 864   time[0] = unix_time_now ();
 865   time[1] = time[0];
 866   dump_time = g_dump_period;
 867
 868   for (i = 1; i <= iter; i++)
 869     {
 870       if (i >= g_set_verbose_at)
 871         g_verbose = 2;
 872
 873       op = bounded_random_u32 (&g_seed, 0, vec_len (g_prob) - 1);
 874       op = g_prob[op];
 875
 876       switch (op)
 877         {
 878         case OP_IS_VEC_RESIZE:
 879           len = vec_len (vec);
 880           num_elts = bounded_random_u32 (&g_seed, len, len + MAX_CHANGE);
 881           VERBOSE2 ("vec_resize(), %d new elts.\n", num_elts);
 882           vec = validate_vec_resize (vec, num_elts);
 883           break;
 884
 885         case OP_IS_VEC_ADD1:
 886           VERBOSE2 ("vec_add1()\n");
 887           vec = validate_vec_add1 (vec);
 888           break;
 889
 890         case OP_IS_VEC_ADD2:
 891           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 892           VERBOSE2 ("vec_add2(), %d new elts.\n", num_elts);
 893           vec = validate_vec_add2 (vec, num_elts);
 894           break;
 895
 896         case OP_IS_VEC_ADD:
 897           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 898           VERBOSE2 ("vec_add(), %d new elts.\n", num_elts);
 899           vec = validate_vec_add (vec, num_elts);
 900           break;
 901
 902         case OP_IS_VEC_INSERT:
 903           len = vec_len (vec);
 904           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 905           index = bounded_random_u32 (&g_seed, 0,
 906                                       (len > 0) ? (len - 1) : (0));
 907           VERBOSE2 ("vec_insert(), %d new elts, index %d.\n", num_elts,
 908                     index);
 909           vec = validate_vec_insert (vec, num_elts, index);
 910           break;
 911
 912         case OP_IS_VEC_INSERT_ELTS:
 913           len = vec_len (vec);
 914           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 915           index = bounded_random_u32 (&g_seed, 0,
 916                                       (len > 0) ? (len - 1) : (0));
 917           VERBOSE2 ("vec_insert_elts(), %d new elts, index %d.\n",
 918                     num_elts, index);
 919           vec = validate_vec_insert_elts (vec, num_elts, index);
 920           break;
 921
 922         case OP_IS_VEC_DELETE:
 923           len = vec_len (vec);
 924           index = bounded_random_u32 (&g_seed, 0, len - 1);
 925           num_elts = bounded_random_u32 (&g_seed, 0,
 926                                          (len > index) ? (len - index) : (0));
 927           VERBOSE2 ("vec_delete(), %d elts, index %d.\n", num_elts, index);
 928           vec = validate_vec_delete (vec, num_elts, index);
 929           break;
 930
 931         case OP_IS_VEC_DUP:
 932           VERBOSE2 ("vec_dup()\n");
 933           new = validate_vec_dup (vec);
 934           vec_free (new);
 935           break;
 936
 937         case OP_IS_VEC_IS_EQUAL:
 938           VERBOSE2 ("vec_is_equal()\n");
 939           validate_vec_is_equal (vec);
 940           break;
 941
 942         case OP_IS_VEC_ZERO:
 943           VERBOSE2 ("vec_zero()\n");
 944           vec = validate_vec_zero (vec);
 945           break;
 946
 947         case OP_IS_VEC_SET:
 948           VERBOSE2 ("vec_set()\n");
 949           vec = validate_vec_set (vec);
 950           break;
 951
 952         case OP_IS_VEC_VALIDATE:
 953           len = vec_len (vec);
 954           index = bounded_random_u32 (&g_seed, 0, len - 1 + MAX_CHANGE);
 955           VERBOSE2 ("vec_validate(), index %d\n", index);
 956           vec = validate_vec_validate (vec, index);
 957           break;
 958
 959         case OP_IS_VEC_FREE:
 960           VERBOSE2 ("vec_free()\n");
 961           vec = validate_vec_free (vec);
 962           break;
 963
 964         case OP_IS_VEC_INIT:
 965           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 966           vec_free (vec);
 967           VERBOSE2 ("vec_init(), new elts %d\n", num_elts);
 968           vec = validate_vec_init (num_elts);
 969           break;
 970
 971         case OP_IS_VEC_CLONE:
 972           VERBOSE2 ("vec_clone()\n");
 973           new = validate_vec_clone (vec);
 974           vec_free (new);
 975           break;
 976
 977         case OP_IS_VEC_APPEND:
 978           VERBOSE2 ("vec_append()\n");
 979           vec = validate_vec_append (vec);
 980           break;
 981
 982         case OP_IS_VEC_PREPEND:
 983           VERBOSE2 ("vec_prepend()\n");
 984           vec = validate_vec_prepend (vec);
 985           break;
 986
 987         default:
 988           ASSERT (0);
 989           break;
 990         }
 991
 992       g_call_stats[op]++;
 993
 994       if (i == dump_time)
 995         {
 996           time[2] = unix_time_now ();
 997           VERBOSE1 ("%d vec ops in %f secs. (last %d in %f secs.).\n",
 998                     i, time[2] - time[0], g_dump_period, time[2] - time[1]);
 999           time[1] = time[2];
1000           dump_time += g_dump_period;
1001
1002           VERBOSE1 ("vec len %d\n", vec_len (vec));
1003           VERBOSE2 ("%U\n\n",
1004                     format_hex_bytes, vec, vec_len (vec) * sizeof (vec[0]));
1005         }
1006
1007       VERBOSE2 ("len %d\n", vec_len (vec));
1008     }
1009
1010   validate_vec (vec, 0);
1011   vec_free (vec);
1012 }
1013
1014 static void
1015 prob_init (void)
1016 {
1017   uword i, j, ratio, len, index;
1018
1019   /* Create the vector to implement the statistical profile:
1020      vec [ op1 op1 op1 op2 op3 op3 op3 op4 op4 .... ] */
1021   for (i = FIRST_VEC_OP; i <= LAST_VEC_OP; i++)
1022     {
1023       ratio = g_prob_ratio[i];
1024       if (ratio <= 0)
1025         continue;
1026
1027       len = vec_len (g_prob);
1028       index = len - 1 + ratio;
1029       ASSERT (index >= 0);
1030
1031       /* Pre-allocate new elements. */
1032       vec_validate (g_prob, index);
1033
1034       for (j = len; j <= index; j++)
1035         g_prob[j] = i;
1036     }
1037
1038   /* Operations on vectors with headers. */
1039   for (i = FIRST_VEC_HDR_OP; i <= LAST_VEC_HDR_OP; i++)
1040     {
1041       ratio = g_prob_ratio[i];
1042       if (ratio <= 0)
1043         continue;
1044
1045       len = vec_len (g_prob_wh);
1046       index = len - 1 + ratio;
1047       ASSERT (index >= 0);
1048
1049       /* Pre-allocate new elements. */
1050       vec_validate (g_prob_wh, index);
1051
1052       for (j = len; j <= index; j++)
1053         g_prob_wh[j] = i;
1054     }
1055
1056   VERBOSE3 ("prob_vec, len %d\n%U\n", vec_len (g_prob),
1057             format_hex_bytes, g_prob, vec_len (g_prob) * sizeof (g_prob[0]));
1058   VERBOSE3 ("prob_vec_wh, len %d\n%U\n", vec_len (g_prob_wh),
1059             format_hex_bytes, g_prob_wh,
1060             vec_len (g_prob_wh) * sizeof (g_prob_wh[0]));
1061 }
1062
1063 static void
1064 prob_free (void)
1065 {
1066   vec_free (g_prob);
1067   vec_free (g_prob_wh);
1068 }
1069
1070 int
1071 test_vec_main (unformat_input_t * input)
1072 {
1073   uword iter = 1000;
1074   uword help = 0;
1075   uword big = 0;
1076
1077   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
1078     {
1079       if (0 == unformat (input, "iter %d", &iter)
1080           && 0 == unformat (input, "seed %d", &g_seed)
1081           && 0 == unformat (input, "verbose %d", &g_verbose)
1082           && 0 == unformat (input, "set %d", &g_set_verbose_at)
1083           && 0 == unformat (input, "dump %d", &g_dump_period)
1084           && 0 == unformat (input, "help %=", &help, 1)
1085           && 0 == unformat (input, "big %=", &big, 1))
1086         {
1087           clib_error ("unknown input `%U'", format_unformat_error, input);
1088           goto usage;
1089         }
1090     }
1091
1092   if (big)
1093     {
1094       u8 *bigboy = 0;
1095       u64 one_gig = (1 << 30);
1096       u64 size;
1097       u64 index;
1098
1099       fformat (stdout, "giant vector test...");
1100       size = 5ULL * one_gig;
1101
1102       vec_validate (bigboy, size);
1103
1104       for (index = size; index >= 0; index--)
1105         bigboy[index] = index & 0xff;
1106       return 0;
1107     }
1108
1109
1110   if (help)
1111     goto usage;
1112
1113   prob_init ();
1114   run_validator (iter);
1115   run_validator_wh (iter);
1116   if (verbose)
1117     dump_call_stats (g_call_stats);
1118   prob_free ();
1119
1120   if (verbose)
1121     {
1122       memory_snap ();
1123     }
1124   return 0;
1125
1126 usage:
1127   fformat (stdout, "Usage: test_vec iter <N> seed <N> verbose <N> "
1128            "set <N> dump <N>\n");
1129   if (help)
1130     return 0;
1131
1132   return -1;
1133 }
1134
1135 #ifdef CLIB_UNIX
1136 int
1137 main (int argc, char *argv[])
1138 {
1139   unformat_input_t i;
1140   int ret;
1141
1142   mheap_alloc (0, (uword) 10ULL << 30);
1143
1144   verbose = (argc > 1);
1145   unformat_init_command_line (&i, argv);
1146   ret = test_vec_main (&i);
1147   unformat_free (&i);
1148
1149   return ret;
1150 }
1151 #endif /* CLIB_UNIX */
1152
1153 /*
1154  * fd.io coding-style-patch-verification: ON
1155  *
1156  * Local Variables:
1157  * eval: (c-set-style "gnu")
1158  * End:
1159  */