src/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/format.h>
  51 #include <vppinfra/error.h>
  52 #include <vppinfra/random.h>
  53 #include <vppinfra/time.h>
  54
  55 #include "test_vec.h"
  56
  57 static int verbose;
  58 #define if_verbose(format,args...) \
  59   if (verbose) { clib_warning(format, ## args); }
  60
  61 #define MAX_CHANGE 100
  62
  63
  64 typedef enum
  65 {
  66   /* Values have to be sequential and start with 0. */
  67   OP_IS_VEC_RESIZE = 0,
  68   OP_IS_VEC_ADD1,
  69   OP_IS_VEC_ADD2,
  70   OP_IS_VEC_ADD,
  71   OP_IS_VEC_INSERT,
  72   OP_IS_VEC_INSERT_ELTS,
  73   OP_IS_VEC_DELETE,
  74   OP_IS_VEC_DUP,
  75   OP_IS_VEC_IS_EQUAL,
  76   OP_IS_VEC_ZERO,
  77   OP_IS_VEC_SET,
  78   OP_IS_VEC_VALIDATE,
  79   OP_IS_VEC_FREE,
  80   OP_IS_VEC_INIT,
  81   OP_IS_VEC_CLONE,
  82   OP_IS_VEC_APPEND,
  83   OP_IS_VEC_PREPEND,
  84   /* Operations on vectors with custom headers. */
  85   OP_IS_VEC_INIT_H,
  86   OP_IS_VEC_RESIZE_H,
  87   OP_IS_VEC_FREE_H,
  88   OP_MAX,
  89 } op_t;
  90
  91 #define FIRST_VEC_OP            OP_IS_VEC_RESIZE
  92 #define LAST_VEC_OP             OP_IS_VEC_PREPEND
  93 #define FIRST_VEC_HDR_OP        OP_IS_VEC_INIT_H
  94 #define LAST_VEC_HDR_OP         OP_IS_VEC_FREE_H
  95
  96 uword g_prob_ratio[] = {
  97   [OP_IS_VEC_RESIZE] = 5,
  98   [OP_IS_VEC_ADD1] = 5,
  99   [OP_IS_VEC_ADD2] = 5,
 100   [OP_IS_VEC_ADD] = 5,
 101   [OP_IS_VEC_INSERT] = 5,
 102   [OP_IS_VEC_INSERT_ELTS] = 5,
 103   [OP_IS_VEC_DELETE] = 30,
 104   [OP_IS_VEC_DUP] = 5,
 105   [OP_IS_VEC_IS_EQUAL] = 5,
 106   [OP_IS_VEC_ZERO] = 2,
 107   [OP_IS_VEC_SET] = 3,
 108   [OP_IS_VEC_VALIDATE] = 5,
 109   [OP_IS_VEC_FREE] = 5,
 110   [OP_IS_VEC_INIT] = 5,
 111   [OP_IS_VEC_CLONE] = 5,
 112   [OP_IS_VEC_APPEND] = 5,
 113   [OP_IS_VEC_PREPEND] = 5,
 114   /* Operations on vectors with custom headers. */
 115   [OP_IS_VEC_INIT_H] = 5,
 116   [OP_IS_VEC_RESIZE_H] = 5,
 117   [OP_IS_VEC_FREE_H] = 5,
 118 };
 119
 120 op_t *g_prob;
 121 op_t *g_prob_wh;
 122
 123 uword g_call_stats[OP_MAX];
 124
 125
 126 /* A structure for both vector headers and vector elements might be useful to
 127    uncover potential alignment issues. */
 128
 129 typedef struct
 130 {
 131   u8 field1[4];
 132     CLIB_PACKED (u32 field2);
 133 } hdr_t;
 134
 135 typedef struct
 136 {
 137   u8 field1[3];
 138     CLIB_PACKED (u32 field2);
 139 } elt_t;
 140
 141 #ifdef CLIB_UNIX
 142 u32 g_seed = 0xdeadbabe;
 143 uword g_verbose = 1;
 144 #endif
 145
 146 op_t *g_op_prob;
 147 uword g_set_verbose_at = ~0;
 148 uword g_dump_period = ~0;
 149
 150
 151 static u8 *
 152 format_vec_op_type (u8 * s, va_list * args)
 153 {
 154   op_t op = va_arg (*args, int);
 155
 156   switch (op)
 157     {
 158 #define _(n)                                    \
 159       case OP_IS_##n:                           \
 160         s = format (s, "OP_IS_" #n);            \
 161         break;
 162
 163       _(VEC_RESIZE);
 164       _(VEC_ADD1);
 165       _(VEC_ADD2);
 166       _(VEC_ADD);
 167       _(VEC_INSERT);
 168       _(VEC_INSERT_ELTS);
 169       _(VEC_DELETE);
 170       _(VEC_DUP);
 171       _(VEC_IS_EQUAL);
 172       _(VEC_ZERO);
 173       _(VEC_SET);
 174       _(VEC_VALIDATE);
 175       _(VEC_FREE);
 176       _(VEC_INIT);
 177       _(VEC_CLONE);
 178       _(VEC_APPEND);
 179       _(VEC_PREPEND);
 180       _(VEC_INIT_H);
 181       _(VEC_RESIZE_H);
 182       _(VEC_FREE_H);
 183
 184     default:
 185       s = format (s, "Unknown vec op (%d)", op);
 186       break;
 187     }
 188
 189 #undef _
 190
 191   return s;
 192 }
 193
 194 static void
 195 dump_call_stats (uword * stats)
 196 {
 197   uword i;
 198
 199   fformat (stdout, "Call Stats\n----------\n");
 200
 201   for (i = 0; i < OP_MAX; i++)
 202     fformat (stdout, "%-8d %U\n", stats[i], format_vec_op_type, i);
 203 }
 204
 205
 206 /* XXX - Purposely low value for debugging the validator. Will be set it to a
 207    more sensible value later. */
 208 #define MAX_VEC_LEN 10
 209
 210 #define create_random_vec_wh(elt_type, len, hdr_bytes, seed)                  \
 211   ({                                                                          \
 212     elt_type *_v (v) = NULL;                                                  \
 213     uword _v (l) = (len);                                                     \
 214     vec_attr_t _v (attr) = { .hdr_sz = (hdr_bytes),                           \
 215                              .elt_sz = sizeof (elt_type) };                   \
 216     uword _v (h) = (hdr_bytes);                                               \
 217     u8 *_v (hdr);                                                             \
 218                                                                               \
 219     if (_v (l) == 0)                                                          \
 220       goto __done__;                                                          \
 221                                                                               \
 222     /* ~0 means select random length between 0 and MAX_VEC_LEN. */            \
 223     if (_v (l) == ~0)                                                         \
 224       _v (l) = bounded_random_u32 (&(seed), 0, MAX_VEC_LEN);                  \
 225                                                                               \
 226     _v (v) = _vec_alloc_internal (_v (l), &_v (attr));                        \
 227     fill_with_random_data (_v (v), vec_bytes (_v (v)), (seed));               \
 228                                                                               \
 229     /* Fill header with random data as well. */                               \
 230     if (_v (h) > 0)                                                           \
 231       {                                                                       \
 232         _v (hdr) = vec_header (_v (v));                                       \
 233         fill_with_random_data (_v (hdr), _v (h), (seed));                     \
 234       }                                                                       \
 235                                                                               \
 236   __done__:                                                                   \
 237     _v (v);                                                                   \
 238   })
 239
 240 #define create_random_vec(elt_type, len, seed) \
 241 create_random_vec_wh (elt_type, len, 0, seed)
 242
 243 #define compute_vec_hash(hash, vec)                     \
 244 ({                                                      \
 245   u8 * _v(v) = (u8 *) (vec);                            \
 246   uword _v(n) = vec_len (vec) * sizeof ((vec)[0]);      \
 247   u8 _v(hh) = (u8) (hash);                              \
 248                                                         \
 249   compute_mem_hash (_v(hh), _v(v), _v(n));              \
 250 })
 251
 252 static elt_t *
 253 validate_vec_free (elt_t * vec)
 254 {
 255   vec_free (vec);
 256   ASSERT (vec == NULL);
 257   return vec;
 258 }
 259
 260 static elt_t *
 261 validate_vec_free_h (elt_t * vec, uword hdr_bytes)
 262 {
 263   vec_free (vec);
 264   ASSERT (vec == NULL);
 265   return vec;
 266 }
 267
 268 static void
 269 validate_vec_hdr (elt_t * vec, uword hdr_bytes)
 270 {
 271   u8 *hdr;
 272   u8 *hdr_end;
 273   vec_header_t *vh;
 274
 275   if (!vec)
 276     return;
 277
 278   vh = _vec_find (vec);
 279   hdr = vec_header (vec);
 280   hdr_end = vec_header_end (hdr);
 281
 282   ASSERT (hdr_end == (u8 *) vec);
 283   ASSERT ((u8 *) vh - (u8 *) hdr >= hdr_bytes);
 284 }
 285
 286 static void
 287 validate_vec_len (elt_t * vec)
 288 {
 289   u8 *ptr;
 290   u8 *end;
 291   uword len;
 292   uword bytes;
 293   uword i;
 294   elt_t *elt;
 295
 296   if (!vec)
 297     return;
 298
 299   ptr = (u8 *) vec;
 300   end = (u8 *) vec_end (vec);
 301   len = vec_len (vec);
 302   bytes = sizeof (vec[0]) * len;
 303
 304   ASSERT (bytes == vec_bytes (vec));
 305   ASSERT ((ptr + bytes) == end);
 306
 307   i = 0;
 308
 309   /* XXX - TODO: confirm that auto-incrementing in vec_is_member() would not
 310      have the expected result. */
 311   while (vec_is_member (vec, (__typeof__ (vec[0]) *) ptr))
 312     {
 313       ptr++;
 314       i++;
 315     }
 316
 317   ASSERT (ptr == end);
 318   ASSERT (i == bytes);
 319
 320   i = 0;
 321
 322   vec_foreach (elt, vec) i++;
 323
 324   ASSERT (i == len);
 325 }
 326
 327 static void
 328 validate_vec (elt_t * vec, uword hdr_bytes)
 329 {
 330   validate_vec_hdr (vec, hdr_bytes);
 331   validate_vec_len (vec);
 332
 333   if (!vec || vec_len (vec) == 0)
 334     {
 335       VERBOSE3 ("Vector at %p has zero elements.\n\n", vec);
 336     }
 337   else
 338     {
 339       if (hdr_bytes > 0)
 340         VERBOSE3 ("Header: %U\n", format_hex_bytes, vec_header (vec),
 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);
 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);
 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_generic (elt_t, num_elts, hdr_bytes, 0, 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);
 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 (vec);
 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 (vec);
 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 vl (void *v)
1072 {
1073   return vec_len (v);
1074 }
1075
1076 int
1077 test_vec_main (unformat_input_t * input)
1078 {
1079   uword iter = 1000;
1080   uword help = 0;
1081   uword big = 0;
1082   uword align = 0;
1083   uword ugly = 0;
1084
1085   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
1086     {
1087       if (0 == unformat (input, "iter %d", &iter)
1088           && 0 == unformat (input, "seed %d", &g_seed)
1089           && 0 == unformat (input, "verbose %d", &g_verbose)
1090           && 0 == unformat (input, "set %d", &g_set_verbose_at)
1091           && 0 == unformat (input, "dump %d", &g_dump_period)
1092           && 0 == unformat (input, "help %=", &help, 1)
1093           && 0 == unformat (input, "big %=", &big, 1)
1094           && 0 == unformat (input, "ugly %d", &ugly)
1095           && 0 == unformat (input, "align %=", &align, 1))
1096         {
1097           clib_error ("unknown input `%U'", format_unformat_error, input);
1098           goto usage;
1099         }
1100     }
1101
1102   /* Cause a deliberate heap botch */
1103   if (ugly)
1104     {
1105       u8 *overrun_me = 0;
1106       int i;
1107
1108       vec_validate (overrun_me, 31);
1109       for (i = 0; i < vec_len (overrun_me) + ugly; i++)
1110         overrun_me[i] = i;
1111
1112       vec_free (overrun_me);
1113     }
1114
1115   if (big)
1116     {
1117       u8 *bigboy = 0;
1118       u64 one_gig = (1 << 30);
1119       u64 size;
1120       u64 index;
1121
1122       fformat (stdout, "giant vector test...");
1123       size = 5ULL * one_gig;
1124
1125       vec_validate (bigboy, size);
1126
1127       for (index = size; index >= 0; index--)
1128         bigboy[index] = index & 0xff;
1129       return 0;
1130     }
1131
1132   if (align)
1133     {
1134       u8 *v = 0;
1135
1136       vec_validate_aligned (v, 9, CLIB_CACHE_LINE_BYTES);
1137       fformat (stdout, "v = 0x%llx, aligned %llx\n",
1138                v, ((uword) v) & ~(CLIB_CACHE_LINE_BYTES - 1));
1139       vec_free (v);
1140     }
1141
1142
1143   if (help)
1144     goto usage;
1145
1146   prob_init ();
1147   run_validator (iter);
1148   run_validator_wh (iter);
1149   if (verbose)
1150     dump_call_stats (g_call_stats);
1151   prob_free ();
1152
1153   return 0;
1154
1155 usage:
1156   fformat (stdout, "Usage: test_vec iter <N> seed <N> verbose <N> "
1157            "set <N> dump <N>\n");
1158   if (help)
1159     return 0;
1160
1161   return -1;
1162 }
1163
1164 #ifdef CLIB_UNIX
1165 int
1166 main (int argc, char *argv[])
1167 {
1168   unformat_input_t i;
1169   int ret;
1170
1171   clib_mem_init (0, 3ULL << 30);
1172
1173   verbose = (argc > 1);
1174   unformat_init_command_line (&i, argv);
1175   ret = test_vec_main (&i);
1176   unformat_free (&i);
1177
1178   return ret;
1179 }
1180 #endif /* CLIB_UNIX */
1181
1182 /*
1183  * fd.io coding-style-patch-verification: ON
1184  *
1185  * Local Variables:
1186  * eval: (c-set-style "gnu")
1187  * End:
1188  */