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     uword _v (h) = (hdr_bytes);                                               \
 215     u8 *_v (hdr);                                                             \
 216                                                                               \
 217     if (_v (l) == 0)                                                          \
 218       goto __done__;                                                          \
 219                                                                               \
 220     /* ~0 means select random length between 0 and MAX_VEC_LEN. */            \
 221     if (_v (l) == ~0)                                                         \
 222       _v (l) = bounded_random_u32 (&(seed), 0, MAX_VEC_LEN);                  \
 223                                                                               \
 224     _v (v) = _vec_realloc (NULL, _v (l), sizeof (elt_type), _v (h), 0, 0);    \
 225     fill_with_random_data (_v (v), vec_bytes (_v (v)), (seed));               \
 226                                                                               \
 227     /* Fill header with random data as well. */                               \
 228     if (_v (h) > 0)                                                           \
 229       {                                                                       \
 230         _v (hdr) = vec_header (_v (v));                                       \
 231         fill_with_random_data (_v (hdr), _v (h), (seed));                     \
 232       }                                                                       \
 233                                                                               \
 234   __done__:                                                                   \
 235     _v (v);                                                                   \
 236   })
 237
 238 #define create_random_vec(elt_type, len, seed) \
 239 create_random_vec_wh (elt_type, len, 0, seed)
 240
 241 #define compute_vec_hash(hash, vec)                     \
 242 ({                                                      \
 243   u8 * _v(v) = (u8 *) (vec);                            \
 244   uword _v(n) = vec_len (vec) * sizeof ((vec)[0]);      \
 245   u8 _v(hh) = (u8) (hash);                              \
 246                                                         \
 247   compute_mem_hash (_v(hh), _v(v), _v(n));              \
 248 })
 249
 250 static elt_t *
 251 validate_vec_free (elt_t * vec)
 252 {
 253   vec_free (vec);
 254   ASSERT (vec == NULL);
 255   return vec;
 256 }
 257
 258 static elt_t *
 259 validate_vec_free_h (elt_t * vec, uword hdr_bytes)
 260 {
 261   vec_free (vec);
 262   ASSERT (vec == NULL);
 263   return vec;
 264 }
 265
 266 static void
 267 validate_vec_hdr (elt_t * vec, uword hdr_bytes)
 268 {
 269   u8 *hdr;
 270   u8 *hdr_end;
 271   vec_header_t *vh;
 272
 273   if (!vec)
 274     return;
 275
 276   vh = _vec_find (vec);
 277   hdr = vec_header (vec);
 278   hdr_end = vec_header_end (hdr);
 279
 280   ASSERT (hdr_end == (u8 *) vec);
 281   ASSERT ((u8 *) vh - (u8 *) hdr >= hdr_bytes);
 282 }
 283
 284 static void
 285 validate_vec_len (elt_t * vec)
 286 {
 287   u8 *ptr;
 288   u8 *end;
 289   uword len;
 290   uword bytes;
 291   uword i;
 292   elt_t *elt;
 293
 294   if (!vec)
 295     return;
 296
 297   ptr = (u8 *) vec;
 298   end = (u8 *) vec_end (vec);
 299   len = vec_len (vec);
 300   bytes = sizeof (vec[0]) * len;
 301
 302   ASSERT (bytes == vec_bytes (vec));
 303   ASSERT ((ptr + bytes) == end);
 304
 305   i = 0;
 306
 307   /* XXX - TODO: confirm that auto-incrementing in vec_is_member() would not
 308      have the expected result. */
 309   while (vec_is_member (vec, (__typeof__ (vec[0]) *) ptr))
 310     {
 311       ptr++;
 312       i++;
 313     }
 314
 315   ASSERT (ptr == end);
 316   ASSERT (i == bytes);
 317
 318   i = 0;
 319
 320   vec_foreach (elt, vec) i++;
 321
 322   ASSERT (i == len);
 323 }
 324
 325 static void
 326 validate_vec (elt_t * vec, uword hdr_bytes)
 327 {
 328   validate_vec_hdr (vec, hdr_bytes);
 329   validate_vec_len (vec);
 330
 331   if (!vec || vec_len (vec) == 0)
 332     {
 333       VERBOSE3 ("Vector at %p has zero elements.\n\n", vec);
 334     }
 335   else
 336     {
 337       if (hdr_bytes > 0)
 338         VERBOSE3 ("Header: %U\n", format_hex_bytes, vec_header (vec),
 339                   sizeof (vec[0]));
 340
 341       VERBOSE3 ("%U\n\n",
 342                 format_hex_bytes, vec, vec_len (vec) * sizeof (vec[0]));
 343     }
 344 }
 345
 346 static elt_t *
 347 validate_vec_resize (elt_t * vec, uword num_elts)
 348 {
 349   uword len1 = vec_len (vec);
 350   uword len2;
 351   u8 hash = compute_vec_hash (0, vec);
 352
 353   vec_resize (vec, num_elts);
 354   len2 = vec_len (vec);
 355
 356   ASSERT (len2 == len1 + num_elts);
 357   ASSERT (compute_vec_hash (hash, vec) == 0);
 358   validate_vec (vec, 0);
 359   return vec;
 360 }
 361
 362 static elt_t *
 363 validate_vec_resize_h (elt_t * vec, uword num_elts, uword hdr_bytes)
 364 {
 365   uword len1, len2;
 366   u8 *end1, *end2;
 367   u8 *hdr = NULL;
 368   u8 hash, hdr_hash;
 369
 370   len1 = vec_len (vec);
 371
 372   if (vec)
 373     hdr = vec_header (vec);
 374
 375   hash = compute_vec_hash (0, vec);
 376   hdr_hash = compute_mem_hash (0, hdr, hdr_bytes);
 377
 378   vec_resize_ha (vec, num_elts, hdr_bytes, 0);
 379   len2 = vec_len (vec);
 380
 381   ASSERT (len2 == len1 + num_elts);
 382
 383   end1 = (u8 *) (vec + len1);
 384   end2 = (u8 *) vec_end (vec);
 385
 386   while (end1 != end2)
 387     {
 388       ASSERT (*end1 == 0);
 389       end1++;
 390     }
 391
 392   if (vec)
 393     hdr = vec_header (vec);
 394
 395   ASSERT (compute_vec_hash (hash, vec) == 0);
 396   ASSERT (compute_mem_hash (hdr_hash, hdr, hdr_bytes) == 0);
 397   validate_vec (vec, 1);
 398   return vec;
 399 }
 400
 401 static elt_t *
 402 generic_validate_vec_add (elt_t * vec, uword num_elts, uword is_add2)
 403 {
 404   uword len1 = vec_len (vec);
 405   uword len2;
 406   u8 hash = compute_vec_hash (0, vec);
 407   elt_t *new;
 408
 409   if (is_add2)
 410     {
 411       vec_add2 (vec, new, num_elts);
 412     }
 413   else
 414     {
 415       new = create_random_vec (elt_t, num_elts, g_seed);
 416
 417       VERBOSE3 ("%U\n", format_hex_bytes, new,
 418                 vec_len (new) * sizeof (new[0]));
 419
 420       /* Add the hash value of the new elements to that of the old vector. */
 421       hash = compute_vec_hash (hash, new);
 422
 423       if (num_elts == 1)
 424         vec_add1 (vec, new[0]);
 425       else if (num_elts > 1)
 426         vec_add (vec, new, num_elts);
 427
 428       vec_free (new);
 429     }
 430
 431   len2 = vec_len (vec);
 432   ASSERT (len2 == len1 + num_elts);
 433
 434   ASSERT (compute_vec_hash (hash, vec) == 0);
 435   validate_vec (vec, 0);
 436   return vec;
 437 }
 438
 439 static elt_t *
 440 validate_vec_add1 (elt_t * vec)
 441 {
 442   return generic_validate_vec_add (vec, 1, 0);
 443 }
 444
 445 static elt_t *
 446 validate_vec_add2 (elt_t * vec, uword num_elts)
 447 {
 448   return generic_validate_vec_add (vec, num_elts, 1);
 449 }
 450
 451 static elt_t *
 452 validate_vec_add (elt_t * vec, uword num_elts)
 453 {
 454   return generic_validate_vec_add (vec, num_elts, 0);
 455 }
 456
 457 static elt_t *
 458 validate_vec_insert (elt_t * vec, uword num_elts, uword start_elt)
 459 {
 460   uword len1 = vec_len (vec);
 461   uword len2;
 462   u8 hash;
 463
 464   /* vec_insert() would not handle it properly. */
 465   if (start_elt > len1 || num_elts == 0)
 466     return vec;
 467
 468   hash = compute_vec_hash (0, vec);
 469   vec_insert (vec, num_elts, start_elt);
 470   len2 = vec_len (vec);
 471
 472   ASSERT (len2 == len1 + num_elts);
 473   ASSERT (compute_vec_hash (hash, vec) == 0);
 474   validate_vec (vec, 0);
 475   return vec;
 476 }
 477
 478 static elt_t *
 479 validate_vec_insert_elts (elt_t * vec, uword num_elts, uword start_elt)
 480 {
 481   uword len1 = vec_len (vec);
 482   uword len2;
 483   elt_t *new;
 484   u8 hash;
 485
 486   /* vec_insert_elts() would not handle it properly. */
 487   if (start_elt > len1 || num_elts == 0)
 488     return vec;
 489
 490   new = create_random_vec (elt_t, num_elts, g_seed);
 491
 492   VERBOSE3 ("%U\n", format_hex_bytes, new, vec_len (new) * sizeof (new[0]));
 493
 494   /* Add the hash value of the new elements to that of the old vector. */
 495   hash = compute_vec_hash (0, vec);
 496   hash = compute_vec_hash (hash, new);
 497
 498   vec_insert_elts (vec, new, num_elts, start_elt);
 499   len2 = vec_len (vec);
 500
 501   vec_free (new);
 502
 503   ASSERT (len2 == len1 + num_elts);
 504   ASSERT (compute_vec_hash (hash, vec) == 0);
 505   validate_vec (vec, 0);
 506   return vec;
 507 }
 508
 509 static elt_t *
 510 validate_vec_delete (elt_t * vec, uword num_elts, uword start_elt)
 511 {
 512   uword len1 = vec_len (vec);
 513   uword len2;
 514   u8 *start;
 515   u8 hash;
 516   u8 hash_del;
 517
 518   /* vec_delete() would not handle it properly. */
 519   if (start_elt + num_elts > len1)
 520     return vec;
 521
 522   start = (u8 *) vec + (start_elt * sizeof (vec[0]));
 523
 524   hash = compute_vec_hash (0, vec);
 525   hash_del = compute_mem_hash (0, start, num_elts * sizeof (vec[0]));
 526   hash ^= hash_del;
 527
 528   vec_delete (vec, num_elts, start_elt);
 529   len2 = vec_len (vec);
 530
 531   ASSERT (len2 == len1 - num_elts);
 532   ASSERT (compute_vec_hash (hash, vec) == 0);
 533   validate_vec (vec, 0);
 534   return vec;
 535 }
 536
 537 static elt_t *
 538 validate_vec_dup (elt_t * vec)
 539 {
 540   elt_t *new;
 541   u8 hash;
 542
 543   hash = compute_vec_hash (0, vec);
 544   new = vec_dup (vec);
 545
 546   ASSERT (compute_vec_hash (hash, new) == 0);
 547
 548   validate_vec (new, 0);
 549   return new;
 550 }
 551
 552 static elt_t *
 553 validate_vec_zero (elt_t * vec)
 554 {
 555   u8 *ptr;
 556   u8 *end;
 557
 558   vec_zero (vec);
 559
 560   ptr = (u8 *) vec;
 561   end = (u8 *) (vec + vec_len (vec));
 562
 563   while (ptr != end)
 564     {
 565       ASSERT (ptr < (u8 *) vec_end (vec));
 566       ASSERT (ptr[0] == 0);
 567       ptr++;
 568     }
 569
 570   validate_vec (vec, 0);
 571   return vec;
 572 }
 573
 574 static void
 575 validate_vec_is_equal (elt_t * vec)
 576 {
 577   elt_t *new = NULL;
 578
 579   if (vec_len (vec) <= 0)
 580     return;
 581
 582   new = vec_dup (vec);
 583   ASSERT (vec_is_equal (new, vec));
 584   vec_free (new);
 585 }
 586
 587 static elt_t *
 588 validate_vec_set (elt_t * vec)
 589 {
 590   uword i;
 591   uword len = vec_len (vec);
 592   elt_t *new;
 593
 594   if (!vec)
 595     return NULL;
 596
 597   new = create_random_vec (elt_t, 1, g_seed);
 598
 599   VERBOSE3 ("%U\n", format_hex_bytes, new, vec_len (new) * sizeof (new[0]));
 600
 601   vec_set (vec, new[0]);
 602
 603   for (i = 0; i < len; i++)
 604     ASSERT (memcmp (&vec[i], &new[0], sizeof (vec[0])) == 0);
 605
 606   vec_free (new);
 607   validate_vec (vec, 0);
 608   return vec;
 609 }
 610
 611 static elt_t *
 612 validate_vec_validate (elt_t * vec, uword index)
 613 {
 614   uword len = vec_len (vec);
 615   word num_new = index - len + 1;
 616   u8 *ptr;
 617   u8 *end;
 618   u8 hash = compute_vec_hash (0, vec);
 619
 620   if (num_new < 0)
 621     num_new = 0;
 622
 623   vec_validate (vec, index);
 624
 625   /* Old len but new vec pointer! */
 626   ptr = (u8 *) (vec + len);
 627   end = (u8 *) (vec + len + num_new);
 628
 629   ASSERT (len + num_new == vec_len (vec));
 630   ASSERT (compute_vec_hash (hash, vec) == 0);
 631
 632   while (ptr != end)
 633     {
 634       ASSERT (ptr < (u8 *) vec_end (vec));
 635       ASSERT (ptr[0] == 0);
 636       ptr++;
 637     }
 638
 639   validate_vec (vec, 0);
 640   return vec;
 641 }
 642
 643 static elt_t *
 644 validate_vec_init (uword num_elts)
 645 {
 646   u8 *ptr;
 647   u8 *end;
 648   uword len;
 649   elt_t *new;
 650
 651   new = vec_new (elt_t, num_elts);
 652   len = vec_len (new);
 653
 654   ASSERT (len == num_elts);
 655
 656   ptr = (u8 *) new;
 657   end = (u8 *) (new + len);
 658
 659   while (ptr != end)
 660     {
 661       ASSERT (ptr < (u8 *) vec_end (new));
 662       ASSERT (ptr[0] == 0);
 663       ptr++;
 664     }
 665
 666   validate_vec (new, 0);
 667   return new;
 668 }
 669
 670 static elt_t *
 671 validate_vec_init_h (uword num_elts, uword hdr_bytes)
 672 {
 673   uword i = 0;
 674   u8 *ptr;
 675   u8 *end;
 676   uword len;
 677   elt_t *new;
 678
 679   new = vec_new_generic (elt_t, num_elts, hdr_bytes, 0, 0);
 680   len = vec_len (new);
 681
 682   ASSERT (len == num_elts);
 683
 684   /* We have 2 zero-regions to check: header & vec data (skip _VEC struct). */
 685   for (i = 0; i < 2; i++)
 686     {
 687       if (i == 0)
 688         {
 689           ptr = (u8 *) vec_header (new);
 690           end = ptr + hdr_bytes;
 691         }
 692       else
 693         {
 694           ptr = (u8 *) new;
 695           end = (u8 *) (new + len);
 696         }
 697
 698       while (ptr != end)
 699         {
 700           ASSERT (ptr < (u8 *) vec_end (new));
 701           ASSERT (ptr[0] == 0);
 702           ptr++;
 703         }
 704     }
 705
 706   validate_vec (new, 1);
 707   return new;
 708 }
 709
 710 /* XXX - I don't understand the purpose of the vec_clone() call. */
 711 static elt_t *
 712 validate_vec_clone (elt_t * vec)
 713 {
 714   elt_t *new;
 715
 716   vec_clone (new, vec);
 717
 718   ASSERT (vec_len (new) == vec_len (vec));
 719   ASSERT (compute_vec_hash (0, new) == 0);
 720   validate_vec (new, 0);
 721   return new;
 722 }
 723
 724 static elt_t *
 725 validate_vec_append (elt_t * vec)
 726 {
 727   elt_t *new;
 728   uword num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 729   uword len;
 730   u8 hash = 0;
 731
 732   new = create_random_vec (elt_t, num_elts, g_seed);
 733
 734   len = vec_len (vec) + vec_len (new);
 735   hash = compute_vec_hash (0, vec);
 736   hash = compute_vec_hash (hash, new);
 737
 738   vec_append (vec, new);
 739   vec_free (new);
 740
 741   ASSERT (vec_len (vec) == len);
 742   ASSERT (compute_vec_hash (hash, vec) == 0);
 743   validate_vec (vec, 0);
 744   return vec;
 745 }
 746
 747 static elt_t *
 748 validate_vec_prepend (elt_t * vec)
 749 {
 750   elt_t *new;
 751   uword num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 752   uword len;
 753   u8 hash = 0;
 754
 755   new = create_random_vec (elt_t, num_elts, g_seed);
 756
 757   len = vec_len (vec) + vec_len (new);
 758   hash = compute_vec_hash (0, vec);
 759   hash = compute_vec_hash (hash, new);
 760
 761   vec_prepend (vec, new);
 762   vec_free (new);
 763
 764   ASSERT (vec_len (vec) == len);
 765   ASSERT (compute_vec_hash (hash, vec) == 0);
 766   validate_vec (vec, 0);
 767   return vec;
 768 }
 769
 770 static void
 771 run_validator_wh (uword iter)
 772 {
 773   elt_t *vec;
 774   uword i;
 775   uword op;
 776   uword num_elts;
 777   uword len;
 778   uword dump_time;
 779   f64 time[3];                  /* [0]: start, [1]: last, [2]: current */
 780
 781   vec = create_random_vec_wh (elt_t, ~0, sizeof (hdr_t), g_seed);
 782   validate_vec (vec, 0);
 783   VERBOSE2 ("Start with len %d\n", vec_len (vec));
 784
 785   time[0] = unix_time_now ();
 786   time[1] = time[0];
 787   dump_time = g_dump_period;
 788
 789   for (i = 1; i <= iter; i++)
 790     {
 791       if (i >= g_set_verbose_at)
 792         g_verbose = 2;
 793
 794       op = bounded_random_u32 (&g_seed, 0, vec_len (g_prob_wh) - 1);
 795       op = g_prob_wh[op];
 796
 797       switch (op)
 798         {
 799         case OP_IS_VEC_INIT_H:
 800           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 801           vec_free (vec);
 802           VERBOSE2 ("vec_init_h(), new elts %d\n", num_elts);
 803           vec = validate_vec_init_h (num_elts, sizeof (hdr_t));
 804           break;
 805
 806         case OP_IS_VEC_RESIZE_H:
 807           len = vec_len (vec);
 808           num_elts = bounded_random_u32 (&g_seed, len, len + MAX_CHANGE);
 809           VERBOSE2 ("vec_resize_h(), %d new elts.\n", num_elts);
 810           vec = validate_vec_resize_h (vec, num_elts, sizeof (hdr_t));
 811           break;
 812
 813         case OP_IS_VEC_FREE_H:
 814           VERBOSE2 ("vec_free_h()\n");
 815           vec = validate_vec_free_h (vec, sizeof (hdr_t));
 816           break;
 817
 818         default:
 819           ASSERT (0);
 820           break;
 821         }
 822
 823       g_call_stats[op]++;
 824
 825       if (i == dump_time)
 826         {
 827           time[2] = unix_time_now ();
 828           VERBOSE1 ("%d vec ops in %f secs. (last %d in %f secs.).\n",
 829                     i, time[2] - time[0], g_dump_period, time[2] - time[1]);
 830           time[1] = time[2];
 831           dump_time += g_dump_period;
 832
 833           VERBOSE1 ("vec len %d\n", vec_len (vec));
 834           VERBOSE2 ("%U\n\n",
 835                     format_hex_bytes, vec, vec_len (vec) * sizeof (vec[0]));
 836         }
 837
 838       VERBOSE2 ("len %d\n", vec_len (vec));
 839     }
 840
 841   validate_vec (vec, sizeof (hdr_t));
 842   vec_free (vec);
 843 }
 844
 845 static void
 846 run_validator (uword iter)
 847 {
 848   elt_t *vec;
 849   elt_t *new;
 850   uword i;
 851   uword op;
 852   uword num_elts;
 853   uword index;
 854   uword len;
 855   uword dump_time;
 856   f64 time[3];                  /* [0]: start, [1]: last, [2]: current */
 857
 858   vec = create_random_vec (elt_t, ~0, g_seed);
 859   validate_vec (vec, 0);
 860   VERBOSE2 ("Start with len %d\n", vec_len (vec));
 861
 862   time[0] = unix_time_now ();
 863   time[1] = time[0];
 864   dump_time = g_dump_period;
 865
 866   for (i = 1; i <= iter; i++)
 867     {
 868       if (i >= g_set_verbose_at)
 869         g_verbose = 2;
 870
 871       op = bounded_random_u32 (&g_seed, 0, vec_len (g_prob) - 1);
 872       op = g_prob[op];
 873
 874       switch (op)
 875         {
 876         case OP_IS_VEC_RESIZE:
 877           len = vec_len (vec);
 878           num_elts = bounded_random_u32 (&g_seed, len, len + MAX_CHANGE);
 879           VERBOSE2 ("vec_resize(), %d new elts.\n", num_elts);
 880           vec = validate_vec_resize (vec, num_elts);
 881           break;
 882
 883         case OP_IS_VEC_ADD1:
 884           VERBOSE2 ("vec_add1()\n");
 885           vec = validate_vec_add1 (vec);
 886           break;
 887
 888         case OP_IS_VEC_ADD2:
 889           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 890           VERBOSE2 ("vec_add2(), %d new elts.\n", num_elts);
 891           vec = validate_vec_add2 (vec, num_elts);
 892           break;
 893
 894         case OP_IS_VEC_ADD:
 895           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 896           VERBOSE2 ("vec_add(), %d new elts.\n", num_elts);
 897           vec = validate_vec_add (vec, num_elts);
 898           break;
 899
 900         case OP_IS_VEC_INSERT:
 901           len = vec_len (vec);
 902           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 903           index = bounded_random_u32 (&g_seed, 0,
 904                                       (len > 0) ? (len - 1) : (0));
 905           VERBOSE2 ("vec_insert(), %d new elts, index %d.\n", num_elts,
 906                     index);
 907           vec = validate_vec_insert (vec, num_elts, index);
 908           break;
 909
 910         case OP_IS_VEC_INSERT_ELTS:
 911           len = vec_len (vec);
 912           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 913           index = bounded_random_u32 (&g_seed, 0,
 914                                       (len > 0) ? (len - 1) : (0));
 915           VERBOSE2 ("vec_insert_elts(), %d new elts, index %d.\n",
 916                     num_elts, index);
 917           vec = validate_vec_insert_elts (vec, num_elts, index);
 918           break;
 919
 920         case OP_IS_VEC_DELETE:
 921           len = vec_len (vec);
 922           index = bounded_random_u32 (&g_seed, 0, len - 1);
 923           num_elts = bounded_random_u32 (&g_seed, 0,
 924                                          (len > index) ? (len - index) : (0));
 925           VERBOSE2 ("vec_delete(), %d elts, index %d.\n", num_elts, index);
 926           vec = validate_vec_delete (vec, num_elts, index);
 927           break;
 928
 929         case OP_IS_VEC_DUP:
 930           VERBOSE2 ("vec_dup()\n");
 931           new = validate_vec_dup (vec);
 932           vec_free (new);
 933           break;
 934
 935         case OP_IS_VEC_IS_EQUAL:
 936           VERBOSE2 ("vec_is_equal()\n");
 937           validate_vec_is_equal (vec);
 938           break;
 939
 940         case OP_IS_VEC_ZERO:
 941           VERBOSE2 ("vec_zero()\n");
 942           vec = validate_vec_zero (vec);
 943           break;
 944
 945         case OP_IS_VEC_SET:
 946           VERBOSE2 ("vec_set()\n");
 947           vec = validate_vec_set (vec);
 948           break;
 949
 950         case OP_IS_VEC_VALIDATE:
 951           len = vec_len (vec);
 952           index = bounded_random_u32 (&g_seed, 0, len - 1 + MAX_CHANGE);
 953           VERBOSE2 ("vec_validate(), index %d\n", index);
 954           vec = validate_vec_validate (vec, index);
 955           break;
 956
 957         case OP_IS_VEC_FREE:
 958           VERBOSE2 ("vec_free()\n");
 959           vec = validate_vec_free (vec);
 960           break;
 961
 962         case OP_IS_VEC_INIT:
 963           num_elts = bounded_random_u32 (&g_seed, 0, MAX_CHANGE);
 964           vec_free (vec);
 965           VERBOSE2 ("vec_init(), new elts %d\n", num_elts);
 966           vec = validate_vec_init (num_elts);
 967           break;
 968
 969         case OP_IS_VEC_CLONE:
 970           VERBOSE2 ("vec_clone()\n");
 971           new = validate_vec_clone (vec);
 972           vec_free (new);
 973           break;
 974
 975         case OP_IS_VEC_APPEND:
 976           VERBOSE2 ("vec_append()\n");
 977           vec = validate_vec_append (vec);
 978           break;
 979
 980         case OP_IS_VEC_PREPEND:
 981           VERBOSE2 ("vec_prepend()\n");
 982           vec = validate_vec_prepend (vec);
 983           break;
 984
 985         default:
 986           ASSERT (0);
 987           break;
 988         }
 989
 990       g_call_stats[op]++;
 991
 992       if (i == dump_time)
 993         {
 994           time[2] = unix_time_now ();
 995           VERBOSE1 ("%d vec ops in %f secs. (last %d in %f secs.).\n",
 996                     i, time[2] - time[0], g_dump_period, time[2] - time[1]);
 997           time[1] = time[2];
 998           dump_time += g_dump_period;
 999
1000           VERBOSE1 ("vec len %d\n", vec_len (vec));
1001           VERBOSE2 ("%U\n\n",
1002                     format_hex_bytes, vec, vec_len (vec) * sizeof (vec[0]));
1003         }
1004
1005       VERBOSE2 ("len %d\n", vec_len (vec));
1006     }
1007
1008   validate_vec (vec, 0);
1009   vec_free (vec);
1010 }
1011
1012 static void
1013 prob_init (void)
1014 {
1015   uword i, j, ratio, len, index;
1016
1017   /* Create the vector to implement the statistical profile:
1018      vec [ op1 op1 op1 op2 op3 op3 op3 op4 op4 .... ] */
1019   for (i = FIRST_VEC_OP; i <= LAST_VEC_OP; i++)
1020     {
1021       ratio = g_prob_ratio[i];
1022       if (ratio <= 0)
1023         continue;
1024
1025       len = vec_len (g_prob);
1026       index = len - 1 + ratio;
1027       ASSERT (index >= 0);
1028
1029       /* Pre-allocate new elements. */
1030       vec_validate (g_prob, index);
1031
1032       for (j = len; j <= index; j++)
1033         g_prob[j] = i;
1034     }
1035
1036   /* Operations on vectors with headers. */
1037   for (i = FIRST_VEC_HDR_OP; i <= LAST_VEC_HDR_OP; i++)
1038     {
1039       ratio = g_prob_ratio[i];
1040       if (ratio <= 0)
1041         continue;
1042
1043       len = vec_len (g_prob_wh);
1044       index = len - 1 + ratio;
1045       ASSERT (index >= 0);
1046
1047       /* Pre-allocate new elements. */
1048       vec_validate (g_prob_wh, index);
1049
1050       for (j = len; j <= index; j++)
1051         g_prob_wh[j] = i;
1052     }
1053
1054   VERBOSE3 ("prob_vec, len %d\n%U\n", vec_len (g_prob),
1055             format_hex_bytes, g_prob, vec_len (g_prob) * sizeof (g_prob[0]));
1056   VERBOSE3 ("prob_vec_wh, len %d\n%U\n", vec_len (g_prob_wh),
1057             format_hex_bytes, g_prob_wh,
1058             vec_len (g_prob_wh) * sizeof (g_prob_wh[0]));
1059 }
1060
1061 static void
1062 prob_free (void)
1063 {
1064   vec_free (g_prob);
1065   vec_free (g_prob_wh);
1066 }
1067
1068 int
1069 vl (void *v)
1070 {
1071   return vec_len (v);
1072 }
1073
1074 int
1075 test_vec_main (unformat_input_t * input)
1076 {
1077   uword iter = 1000;
1078   uword help = 0;
1079   uword big = 0;
1080   uword align = 0;
1081   uword ugly = 0;
1082
1083   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
1084     {
1085       if (0 == unformat (input, "iter %d", &iter)
1086           && 0 == unformat (input, "seed %d", &g_seed)
1087           && 0 == unformat (input, "verbose %d", &g_verbose)
1088           && 0 == unformat (input, "set %d", &g_set_verbose_at)
1089           && 0 == unformat (input, "dump %d", &g_dump_period)
1090           && 0 == unformat (input, "help %=", &help, 1)
1091           && 0 == unformat (input, "big %=", &big, 1)
1092           && 0 == unformat (input, "ugly %d", &ugly)
1093           && 0 == unformat (input, "align %=", &align, 1))
1094         {
1095           clib_error ("unknown input `%U'", format_unformat_error, input);
1096           goto usage;
1097         }
1098     }
1099
1100   /* Cause a deliberate heap botch */
1101   if (ugly)
1102     {
1103       u8 *overrun_me = 0;
1104       int i;
1105
1106       vec_validate (overrun_me, 31);
1107       for (i = 0; i < vec_len (overrun_me) + ugly; i++)
1108         overrun_me[i] = i;
1109
1110       vec_free (overrun_me);
1111     }
1112
1113   if (big)
1114     {
1115       u8 *bigboy = 0;
1116       u64 one_gig = (1 << 30);
1117       u64 size;
1118       u64 index;
1119
1120       fformat (stdout, "giant vector test...");
1121       size = 5ULL * one_gig;
1122
1123       vec_validate (bigboy, size);
1124
1125       for (index = size; index >= 0; index--)
1126         bigboy[index] = index & 0xff;
1127       return 0;
1128     }
1129
1130   if (align)
1131     {
1132       u8 *v = 0;
1133
1134       vec_validate_aligned (v, 9, CLIB_CACHE_LINE_BYTES);
1135       fformat (stdout, "v = 0x%llx, aligned %llx\n",
1136                v, ((uword) v) & ~(CLIB_CACHE_LINE_BYTES - 1));
1137       vec_free (v);
1138     }
1139
1140
1141   if (help)
1142     goto usage;
1143
1144   prob_init ();
1145   run_validator (iter);
1146   run_validator_wh (iter);
1147   if (verbose)
1148     dump_call_stats (g_call_stats);
1149   prob_free ();
1150
1151   return 0;
1152
1153 usage:
1154   fformat (stdout, "Usage: test_vec iter <N> seed <N> verbose <N> "
1155            "set <N> dump <N>\n");
1156   if (help)
1157     return 0;
1158
1159   return -1;
1160 }
1161
1162 #ifdef CLIB_UNIX
1163 int
1164 main (int argc, char *argv[])
1165 {
1166   unformat_input_t i;
1167   int ret;
1168
1169   clib_mem_init (0, 3ULL << 30);
1170
1171   verbose = (argc > 1);
1172   unformat_init_command_line (&i, argv);
1173   ret = test_vec_main (&i);
1174   unformat_free (&i);
1175
1176   return ret;
1177 }
1178 #endif /* CLIB_UNIX */
1179
1180 /*
1181  * fd.io coding-style-patch-verification: ON
1182  *
1183  * Local Variables:
1184  * eval: (c-set-style "gnu")
1185  * End:
1186  */