silo/masstree/kvtest.hh

   1 /* Masstree
   2  * Eddie Kohler, Yandong Mao, Robert Morris
   3  * Copyright (c) 2012-2013 President and Fellows of Harvard College
   4  * Copyright (c) 2012-2013 Massachusetts Institute of Technology
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the "Software"),
   8  * to deal in the Software without restriction, subject to the conditions
   9  * listed in the Masstree LICENSE file. These conditions include: you must
  10  * preserve this copyright notice, and you cannot mention the copyright
  11  * holders in advertising related to the Software without their permission.
  12  * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
  13  * notice is a summary of the Masstree LICENSE file; the license in that file
  14  * is legally binding.
  15  */
  16 #ifndef KVTEST_HH
  17 #define KVTEST_HH
  18 #include "json.hh"
  19 #include "misc.hh"
  20 #include "kvproto.hh"
  21 #include <vector>
  22 #include <fstream>
  23
  24 using lcdf::Str;
  25 using lcdf::String;
  26 using lcdf::Json;
  27 extern int kvtest_first_seed;
  28 // Templated KV tests, so we can run them either client/server or linked with
  29 // the kvd binary.
  30
  31 template <typename N>
  32 inline Json& kvtest_set_time(Json& result, const lcdf::String& base, N n, double delta_t)
  33 {
  34     result.set(base, n);
  35     if (delta_t > 0)
  36         result.set(base + "_per_sec", n / delta_t);
  37     return result;
  38 }
  39
  40 template <typename N>
  41 inline Json kvtest_set_time(const Json& result, const lcdf::String& base, N n, double delta_t) {
  42     Json x(result);
  43     kvtest_set_time(x, base, n, delta_t);
  44     return x;
  45 }
  46
  47 template <typename C>
  48 void kvtest_sync_rw1_seed(C &client, int seed)
  49 {
  50     client.rand.reset(seed);
  51     double tp0 = client.now();
  52     unsigned n;
  53     for (n = 0; !client.timeout(0) && n <= client.limit(); ++n) {
  54         int32_t x = (int32_t) client.rand.next();
  55         client.put_sync(x, x + 1);
  56     }
  57     client.wait_all();
  58     double tp1 = client.now();
  59
  60     client.puts_done();
  61     client.notice("now getting\n");
  62     int32_t *a = (int32_t *) malloc(sizeof(int32_t) * n);
  63     assert(a);
  64     client.rand.reset(seed);
  65     for (unsigned i = 0; i < n; ++i)
  66         a[i] = (int32_t) client.rand.next();
  67     for (unsigned i = 0; i < n; ++i)
  68         std::swap(a[i], a[client.rand.next() % n]);
  69
  70     double tg0 = client.now();
  71     unsigned g;
  72     for (g = 0; g < n && !client.timeout(1); ++g)
  73         client.get_check_sync(a[g], a[g] + 1);
  74     client.wait_all();
  75     double tg1 = client.now();
  76
  77     Json result = Json();
  78     kvtest_set_time(result, "puts", n, tp1 - tp0);
  79     kvtest_set_time(result, "gets", g, tg1 - tg0);
  80     kvtest_set_time(result, "ops", n + g, (tp1 - tp0) + (tg1 - tg0));
  81     client.report(result);
  82     free(a);
  83 }
  84
  85 template <typename C>
  86 void kvtest_sync_rw1(C &client)
  87 {
  88     kvtest_sync_rw1_seed(client, kvtest_first_seed + client.id() % 48);
  89 }
  90
  91 template <typename C>
  92 unsigned kvtest_rw1puts_seed(C& client, int seed) {
  93     client.rand.reset(seed);
  94     double tp0 = client.now();
  95     unsigned n;
  96     for (n = 0; !client.timeout(0) && n <= client.limit(); ++n) {
  97         int32_t x = (int32_t) client.rand.next();
  98         client.put(x, x + 1);
  99     }
 100     client.wait_all();
 101     double tp1 = client.now();
 102     client.puts_done();
 103
 104     client.report(kvtest_set_time(Json(), "puts", n, tp1 - tp0));
 105     return n;
 106 }
 107
 108 // do a bunch of inserts to distinct keys, then check that they all showed up.
 109 // sometimes overwrites, but only w/ same value.
 110 // different clients might use same key sometimes.
 111 template <typename C>
 112 void kvtest_rw1_seed(C &client, int seed)
 113 {
 114     unsigned n = kvtest_rw1puts_seed(client, seed);
 115
 116     client.notice("now getting\n");
 117     int32_t *a = (int32_t *) malloc(sizeof(int32_t) * n);
 118     assert(a);
 119     client.rand.reset(seed);
 120     for (unsigned i = 0; i < n; ++i)
 121         a[i] = (int32_t) client.rand.next();
 122     for (unsigned i = 0; i < n; ++i)
 123         std::swap(a[i], a[client.rand.next() % n]);
 124
 125     double tg0 = client.now();
 126     unsigned g;
 127 #if 0
 128 #define BATCH 8
 129     for(g = 0; g+BATCH < n && !client.timeout(1); g += BATCH){
 130       long key[BATCH], expected[BATCH];
 131       for(int i = 0; i < BATCH; i++){
 132         key[i] = a[g+i];
 133         expected[i] = a[g+i] + 1;
 134       }
 135       client.many_get_check(BATCH, key, expected);
 136     }
 137 #else
 138     for (g = 0; g < n && !client.timeout(1); ++g)
 139         client.get_check(a[g], a[g] + 1);
 140 #endif
 141     client.wait_all();
 142     double tg1 = client.now();
 143
 144     Json result = client.report(Json());
 145     kvtest_set_time(result, "gets", g, tg1 - tg0);
 146     double delta_puts = n / result["puts_per_sec"].as_d();
 147     kvtest_set_time(result, "ops", n + g, delta_puts + (tg1 - tg0));
 148     client.report(result);
 149     free(a);
 150 }
 151
 152 template <typename C>
 153 void kvtest_rw1puts(C &client)
 154 {
 155     kvtest_rw1puts_seed(client, kvtest_first_seed + client.id() % 48);
 156 }
 157
 158 template <typename C>
 159 void kvtest_rw1(C &client)
 160 {
 161     kvtest_rw1_seed(client, kvtest_first_seed + client.id() % 48);
 162 }
 163
 164 // do a bunch of inserts to distinct keys, then check that they all showed up.
 165 // sometimes overwrites, but only w/ same value.
 166 // different clients might use same key sometimes.
 167 template <typename C>
 168 void kvtest_rw1long_seed(C &client, int seed)
 169 {
 170     const char * const formats[] = {
 171         "user%u", "machine%u", "opening%u", "fartparade%u"
 172     };
 173     char buf[64];
 174
 175     client.rand.reset(seed);
 176     double tp0 = client.now();
 177     unsigned n;
 178     for (n = 0; !client.timeout(0) && n <= client.limit(); ++n) {
 179         unsigned fmt = client.rand.next();
 180         int32_t x = (int32_t) client.rand.next();
 181         client.put(Str::snprintf(buf, sizeof(buf), formats[fmt % 4], x), x + 1);
 182     }
 183     client.wait_all();
 184     double tp1 = client.now();
 185
 186     client.puts_done();
 187     client.notice("now getting\n");
 188     int32_t *a = (int32_t *) malloc(sizeof(int32_t) * n * 2);
 189     assert(a);
 190     client.rand.reset(seed);
 191     for (unsigned i = 0; i < n * 2; ++i)
 192         a[i] = (int32_t) client.rand.next();
 193     for (unsigned i = 0; i < n; ++i) {
 194         unsigned x = client.rand.next() % n;
 195         std::swap(a[2 * i], a[2 * x]);
 196         std::swap(a[2 * i + 1], a[2 * x + 1]);
 197     }
 198
 199     double tg0 = client.now();
 200     unsigned g;
 201     for (g = 0; g < n && !client.timeout(1); ++g) {
 202         unsigned fmt = a[2 * g];
 203         int32_t x = (int32_t) a[2 * g + 1];
 204         client.get_check(Str::snprintf(buf, sizeof(buf), formats[fmt % 4], x), x + 1);
 205     }
 206     client.wait_all();
 207     double tg1 = client.now();
 208
 209     Json result = Json();
 210     kvtest_set_time(result, "puts", n, tp1 - tp0);
 211     kvtest_set_time(result, "gets", g, tg1 - tg0);
 212     kvtest_set_time(result, "ops", n + g, (tp1 - tp0) + (tg1 - tg0));
 213     client.report(result);
 214     free(a);
 215 }
 216
 217 template <typename C>
 218 void kvtest_rw1long(C &client)
 219 {
 220     kvtest_rw1long_seed(client, kvtest_first_seed + client.id() % 48);
 221 }
 222
 223 // interleave inserts and gets for random keys.
 224 template <typename C>
 225 void kvtest_rw2_seed(C &client, int seed, double getfrac)
 226 {
 227     client.rand.reset(seed);
 228     const unsigned c = 2654435761U;
 229     const unsigned offset = client.rand.next();
 230
 231     double t0 = client.now();
 232     uint64_t puts = 0, gets = 0;
 233     int getfrac65536 = (int) (getfrac * 65536 + 0.5);
 234     while (!client.timeout(0) && (puts + gets) <= client.limit()) {
 235         if (puts == 0 || (client.rand.next() % 65536) >= getfrac65536) {
 236             // insert
 237             unsigned x = (offset + puts) * c;
 238             client.put(x, x + 1);
 239             ++puts;
 240         } else {
 241             // get
 242             unsigned x = (offset + (client.rand.next() % puts)) * c;
 243             client.get_check(x, x + 1);
 244             ++gets;
 245         }
 246     }
 247     client.wait_all();
 248     double t1 = client.now();
 249
 250     Json result = Json().set("puts", puts).set("gets", gets);
 251     kvtest_set_time(result, "ops", puts + gets, t1 - t0);
 252     client.report(result);
 253 }
 254
 255 template <typename C>
 256 void kvtest_rw2(C &client)
 257 {
 258     kvtest_rw2_seed(client, kvtest_first_seed + client.id() % 48, 0.5);
 259 }
 260
 261 template <typename C>
 262 void kvtest_rw2g90(C &client)
 263 {
 264     kvtest_rw2_seed(client, kvtest_first_seed + client.id() % 48, 0.9);
 265 }
 266
 267 template <typename C>
 268 void kvtest_rw2g98(C &client)
 269 {
 270     kvtest_rw2_seed(client, kvtest_first_seed + client.id() % 48, 0.98);
 271 }
 272
 273 // interleave inserts and gets for random keys.
 274 template <typename C>
 275 void kvtest_rw2fixed_seed(C &client, int seed, double getfrac)
 276 {
 277     client.rand.reset(seed);
 278     const unsigned c = 2654435761U;
 279     const unsigned offset = client.rand.next();
 280
 281     double t0 = client.now();
 282     uint64_t puts = 0, gets = 0;
 283     int getfrac65536 = (int) (getfrac * 65536 + 0.5);
 284     while (!client.timeout(0) && (puts + gets) <= client.limit()) {
 285         if (puts == 0 || (client.rand.next() % 65536) >= getfrac65536) {
 286             // insert
 287             unsigned x = (offset + puts) * c;
 288             x %= 100000000;
 289             client.put(x, x + 1);
 290             ++puts;
 291         } else {
 292             // get
 293             unsigned x = (offset + (client.rand.next() % puts)) * c;
 294             x %= 100000000;
 295             client.get_check(x, x + 1);
 296             ++gets;
 297         }
 298     }
 299     client.wait_all();
 300     double t1 = client.now();
 301
 302     Json result = Json().set("puts", puts).set("gets", gets);
 303     kvtest_set_time(result, "ops", puts + gets, t1 - t0);
 304     client.report(result);
 305 }
 306
 307 template <typename C>
 308 void kvtest_rw2fixed(C &client)
 309 {
 310     kvtest_rw2fixed_seed(client, kvtest_first_seed + client.id() % 48, 0.5);
 311 }
 312
 313 template <typename C>
 314 void kvtest_rw2fixedg90(C &client)
 315 {
 316     kvtest_rw2fixed_seed(client, kvtest_first_seed + client.id() % 48, 0.9);
 317 }
 318
 319 template <typename C>
 320 void kvtest_rw2fixedg98(C &client)
 321 {
 322     kvtest_rw2fixed_seed(client, kvtest_first_seed + client.id() % 48, 0.98);
 323 }
 324
 325 // do a bunch of inserts to sequentially increasing keys,
 326 // then check that they all showed up.
 327 // different clients might use same key sometimes.
 328 template <typename C>
 329 void kvtest_rw3(C &client)
 330 {
 331     double t0 = client.now();
 332     uint64_t n;
 333     for (n = 0; !client.timeout(0) && n <= client.limit(); ++n)
 334         client.put_key8(n, n + 1);
 335     client.wait_all();
 336
 337     client.puts_done();
 338     client.notice("now getting\n");
 339
 340     double t1 = client.now();
 341     for (unsigned i = 0; i < n; ++i)
 342         client.get_check_key8(i, i + 1);
 343     client.wait_all();
 344
 345     double t2 = client.now();
 346
 347     Json result = Json();
 348     kvtest_set_time(result, "puts", n, t1 - t0);
 349     kvtest_set_time(result, "gets", n, t2 - t1);
 350     kvtest_set_time(result, "ops", n + n, t2 - t0);
 351     client.report(result);
 352 }
 353
 354 // do a bunch of inserts to sequentially decreasing keys,
 355 // then check that they all showed up.
 356 // different clients might use same key sometimes.
 357 template <typename C>
 358 void kvtest_rw4(C &client)
 359 {
 360     const int top = 2147483647;
 361
 362     double t0 = client.now();
 363     unsigned n;
 364     for (n = 0; !client.timeout(0) && n <= client.limit(); ++n)
 365         client.put_key8(top - n, n + 1);
 366     client.wait_all();
 367
 368     client.puts_done();
 369     client.notice("now getting\n");
 370
 371     double t1 = client.now();
 372     for (unsigned i = 0; i < n; ++i)
 373         client.get_check_key8(top - i, i + 1);
 374     client.wait_all();
 375
 376     double t2 = client.now();
 377
 378     Json result = Json();
 379     kvtest_set_time(result, "puts", n, t1 - t0);
 380     kvtest_set_time(result, "gets", n, t2 - t1);
 381     kvtest_set_time(result, "ops", n + n, t2 - t0);
 382     client.report(result);
 383 }
 384
 385 // do a bunch of inserts to sequentially decreasing 8B keys,
 386 // then check that they all showed up.
 387 // different clients might use same key sometimes.
 388 template <typename C>
 389 void kvtest_rw4fixed(C &client)
 390 {
 391     const int top = 99999999;
 392
 393     double t0 = client.now();
 394     unsigned n;
 395     for (n = 0; !client.timeout(0) && n <= client.limit(); ++n)
 396         client.put_key8(top - n, n + 1);
 397     client.wait_all();
 398
 399     client.puts_done();
 400     client.notice("now getting\n");
 401
 402     double t1 = client.now();
 403     for (unsigned i = 0; i < n; ++i)
 404         client.get_check_key8(top - i, i + 1);
 405     client.wait_all();
 406
 407     double t2 = client.now();
 408
 409     Json result = Json();
 410     kvtest_set_time(result, "puts", n, t1 - t0);
 411     kvtest_set_time(result, "gets", n, t2 - t1);
 412     kvtest_set_time(result, "ops", n + n, t2 - t0);
 413     client.report(result);
 414 }
 415
 416 // update the same small set of keys over and over,
 417 // to uncover concurrent update bugs in the server.
 418 template <typename C>
 419 void kvtest_same_seed(C &client, int seed)
 420 {
 421     client.rand.reset(seed);
 422
 423     double t0 = client.now();
 424     unsigned n;
 425     for (n = 0; !client.timeout(0) && n <= client.limit(); ++n) {
 426         unsigned x = client.rand.next() % 10;
 427         client.put(x, x + 1);
 428     }
 429     client.wait_all();
 430     double t1 = client.now();
 431
 432     Json result = Json();
 433     kvtest_set_time(result, "puts", n, t1 - t0);
 434     client.report(result);
 435 }
 436
 437 template <typename C>
 438 void kvtest_same(C &client)
 439 {
 440     kvtest_same_seed(client, kvtest_first_seed + client.id() % 48);
 441 }
 442
 443 // update the same small set of keys over and over, with interspersed gets.
 444 template <typename C>
 445 void kvtest_rwsmall_seed(C &client, int nkeys, int seed)
 446 {
 447     client.rand.reset(seed);
 448
 449     double t0 = client.now();
 450     unsigned n;
 451     for (n = 0; !client.timeout(0) && n <= client.limit(); ++n) {
 452         unsigned x = client.rand.next() % (8 * nkeys);
 453         if (x & 7)
 454             client.get(x >> 3);
 455         else
 456             client.put(x >> 3, n);
 457     }
 458     client.wait_all();
 459     double t1 = client.now();
 460
 461     Json result = Json();
 462     kvtest_set_time(result, "ops", n, t1 - t0);
 463     client.report(result);
 464 }
 465
 466 template <typename C>
 467 void kvtest_rwsmall24(C &client)
 468 {
 469     kvtest_rwsmall_seed(client, 24, kvtest_first_seed + client.id() % 48);
 470 }
 471
 472 // update the same small set of keys over and over, with interspersed gets.
 473 // but ensure that the keys are all on different cache lines.
 474 template <typename C>
 475 void kvtest_rwsep_seed(C &client, int nkeys, int clientid, int seed)
 476 {
 477     for (int n = clientid * (32 + nkeys); n < (clientid + 1) * (32 + nkeys); ++n)
 478         client.put(1000000 + n, n);
 479
 480     client.rand.reset(seed);
 481
 482     double t0 = client.now();
 483     unsigned n;
 484     for (n = 0; !client.timeout(0) && n <= client.limit(); ++n) {
 485         unsigned x = client.rand.next() % (8 * nkeys);
 486         if (x & 7)
 487             client.get(1000000 + clientid * (32 + nkeys) + (x >> 3));
 488         else
 489             client.put(1000000 + clientid * (32 + nkeys) + (x >> 3), n);
 490     }
 491     client.wait_all();
 492     double t1 = client.now();
 493
 494     Json result = Json();
 495     kvtest_set_time(result, "ops", n, t1 - t0);
 496     client.report(result);
 497 }
 498
 499 template <typename C>
 500 void kvtest_rwsep24(C &client)
 501 {
 502     kvtest_rwsep_seed(client, 24, client.id(), kvtest_first_seed + client.id() % 48);
 503 }
 504
 505 // Same as rw1, except that the keys are no more than 8 bytes
 506 template <typename C>
 507 void kvtest_rw1fixed_seed(C &client, int seed)
 508 {
 509     client.rand.reset(seed);
 510     double tp0 = client.now();
 511     unsigned n;
 512     for (n = 0; !client.timeout(0) && n <= client.limit(); ++n) {
 513         int32_t x = (int32_t) client.rand.next();
 514         x %= 100000000;
 515         client.put(x, x + 1);
 516     }
 517     client.wait_all();
 518     double tp1 = client.now();
 519
 520     client.puts_done();
 521     client.notice("now getting\n");
 522     int32_t *a = (int32_t *) malloc(sizeof(int32_t) * n);
 523     assert(a);
 524     client.rand.reset(seed);
 525     for (unsigned i = 0; i < n; ++i) {
 526         a[i] = (int32_t) client.rand.next();
 527         a[i] %= 100000000;
 528     }
 529     for (unsigned i = 0; i < n; ++i)
 530         std::swap(a[i], a[client.rand.next() % n]);
 531
 532     double tg0 = client.now();
 533     unsigned g;
 534 #if 0
 535 #define BATCH 8
 536     for(g = 0; g+BATCH < n && !client.timeout(1); g += BATCH){
 537       long key[BATCH], expected[BATCH];
 538       for(int i = 0; i < BATCH; i++){
 539         key[i] = a[g+i];
 540         expected[i] = a[g+i] + 1;
 541       }
 542       client.many_get_check(BATCH, key, expected);
 543     }
 544 #else
 545     for (g = 0; g < n && !client.timeout(1); ++g)
 546         client.get_check(a[g], a[g] + 1);
 547 #endif
 548     client.wait_all();
 549     double tg1 = client.now();
 550
 551     Json result = Json();
 552     kvtest_set_time(result, "puts", n, tp1 - tp0);
 553     kvtest_set_time(result, "gets", g, tg1 - tg0);
 554     kvtest_set_time(result, "ops", n + g, (tp1 - tp0) + (tg1 - tg0));
 555     client.report(result);
 556     free(a);
 557 }
 558
 559 template <typename C>
 560 void kvtest_rw1fixed(C &client)
 561 {
 562     kvtest_rw1fixed_seed(client, kvtest_first_seed + client.id() % 48);
 563 }
 564
 565 // Same as rw1, except that keys are 16-bytes (prefixed with "0"s)
 566 template <typename C>
 567 void kvtest_rw16_seed(C &client, int seed)
 568 {
 569     client.rand.reset(seed);
 570     double tp0 = client.now();
 571     int n;
 572     char key[256];
 573     char val[256];
 574     for (n = 0; !client.timeout(0); ++n) {
 575         int32_t x = (int32_t) client.rand.next();
 576         sprintf(key, "%016d", x);
 577         sprintf(val, "%016d", x + 1);
 578         client.put(key, val);
 579     }
 580     client.wait_all();
 581     double tp1 = client.now();
 582
 583     client.puts_done();
 584     client.notice("now getting\n");
 585     int32_t *a = (int32_t *) malloc(sizeof(int32_t) * n);
 586     assert(a);
 587     client.rand.reset(seed);
 588     for (int i = 0; i < n; ++i)
 589         a[i] = (int32_t) client.rand.next();
 590     for (int i = 0; i < n; ++i)
 591         std::swap(a[i], a[client.rand.next() % n]);
 592
 593     double tg0 = client.now();
 594     int g;
 595     for (g = 0; g < n && !client.timeout(1); ++g) {
 596         sprintf(key, "%016d", a[g]);
 597         sprintf(val, "%016d", a[g] + 1);
 598         client.get_check(key, val);
 599     }
 600     client.wait_all();
 601     double tg1 = client.now();
 602
 603     Json result = Json();
 604     kvtest_set_time(result, "puts", n, tp1 - tp0);
 605     kvtest_set_time(result, "gets", g, tg1 - tg0);
 606     kvtest_set_time(result, "ops", n + g, (tp1 - tp0) + (tg1 - tg0));
 607     client.report(result);
 608     free(a);
 609 }
 610
 611 template <typename C>
 612 void kvtest_rw16(C &client)
 613 {
 614     kvtest_rw16_seed(client, kvtest_first_seed + client.id() % 48);
 615 }
 616
 617
 618 // A writer and a deleter; the deleter chases the writer
 619 template <typename C>
 620 void kvtest_wd1(unsigned initial_pos, int incr, C &client)
 621 {
 622     incr = std::max(incr, client.nthreads() / 2);
 623     unsigned pos = initial_pos + ((client.id() / 2) % incr);
 624     unsigned n = 0;
 625     Json result = Json();
 626
 627     double t0 = client.now();
 628     if (client.id() % 2) {
 629         while (!client.get_sync(pos + 16 * incr))
 630             /* spin */;
 631         while (!client.timeout(0)) {
 632             ++n;
 633             if (client.remove_sync(pos))
 634                 pos += incr;
 635             if ((n % (1 << 16)) == 0)
 636                 client.rcu_quiesce();
 637         }
 638         result.set("removepos", pos);
 639     } else {
 640         while (!client.timeout(0)) {
 641             ++n;
 642             client.put(pos, pos + 1);
 643             pos += incr;
 644             if ((n % (1 << 16)) == 0)
 645                 client.rcu_quiesce();
 646         }
 647         result.set("putpos", pos);
 648     }
 649     client.wait_all();
 650     double t1 = client.now();
 651
 652     kvtest_set_time(result, "ops", n, t1 - t0);
 653     client.report(result);
 654 }
 655
 656 template <typename C>
 657 void kvtest_wd1_check(unsigned initial_pos, int incr, C &client)
 658 {
 659     incr = std::max(incr, client.nthreads() / 2);
 660     unsigned pos = initial_pos + ((client.id() / 2) % incr);
 661     unsigned n = 0;
 662     Json result = Json();
 663
 664     double t0 = client.now();
 665     if (client.id() % 2 == 0) {
 666         unsigned max_remove = -1, min_post_remove = -1, max_post_remove = -1;
 667         unsigned bugs = 0;
 668         bool found_putpos = false;
 669         constexpr int nbatch = 20;
 670         Str gotten[nbatch];
 671         char gottenbuf[nbatch * 16];
 672         for (int i = 0; i < nbatch; ++i)
 673             gotten[i].s = &gottenbuf[i * 16];
 674
 675         while (!client.timeout(0)
 676                && (!found_putpos || pos < max_post_remove + 100000)) {
 677             for (int i = 0; i < nbatch; ++i) {
 678                 gotten[i].len = 16;
 679                 client.get(pos + i * incr, &gotten[i]);
 680             }
 681             client.wait_all();
 682             for (int i = 0; i < nbatch; ++i) {
 683                 if (gotten[i].len) {
 684                     if (min_post_remove == unsigned(-1))
 685                         min_post_remove = max_post_remove = pos;
 686                     else if (!found_putpos)
 687                         max_post_remove = pos;
 688                     else if (++bugs == 1)
 689                         fprintf(stderr, "%u: present unexpectedly\n", pos);
 690                 } else {
 691                     if (min_post_remove == unsigned(-1))
 692                         max_remove = pos;
 693                     else
 694                         found_putpos = true;
 695                 }
 696                 pos += incr;
 697             }
 698         }
 699
 700         result.set("removepos", max_remove + incr);
 701         result.set("putpos", max_post_remove + incr);
 702         if (bugs)
 703             result.set("buggykeys", bugs);
 704     }
 705     client.wait_all();
 706     double t1 = client.now();
 707
 708     kvtest_set_time(result, "ops", n, t1 - t0);
 709     client.report(result);
 710 }
 711
 712 template <typename C>
 713 void kvtest_wd2(C &client)
 714 {
 715     char sbuf[32], kbuf[32], next_kbuf[32];
 716     const int sep = 26;
 717     const int p_remove = 1000, p_put2 = 10000, p_remove2 = 20000;
 718     int x = 0;
 719     quick_istr xstr(0);
 720
 721     client.put(Str("n"), client.nthreads());
 722     always_assert(client.nthreads() > 1);
 723
 724     // set up status keys
 725     snprintf(sbuf, sizeof(sbuf), "s%03d", client.id());
 726     for (int i = 0; i < sep; ++i) {
 727         sbuf[4] = 'A' + i;
 728         client.put(Str(sbuf, 5), Str());
 729     }
 730     client.put(Str(sbuf, 4), xstr.string());
 731
 732     // set up main keys
 733     snprintf(kbuf, sizeof(kbuf), "k%03d", client.id());
 734     for (int i = 0; i < sep; ++i) {
 735         kbuf[4] = 'A' + i;
 736         client.put(Str(kbuf, 5), Str());
 737     }
 738     client.put(Str(kbuf, 4), Str());
 739
 740     snprintf(next_kbuf, sizeof(next_kbuf), "k%03d", (client.id() + 1) % client.nthreads());
 741
 742     // main loop
 743     double t0 = client.now();
 744     int put_status = 0;
 745     long nrounds = 0;
 746     while (!client.timeout(0)) {
 747         ++nrounds;
 748         client.put(Str(kbuf, 4), xstr.string(), &put_status);
 749         if ((client.rand.next() % 65536) < p_remove)
 750             client.remove(Str(next_kbuf, 4));
 751
 752         int rand = client.rand.next() % 65536;
 753         if (rand < p_put2) {
 754             for (int i = sep - 1; i >= 0; --i) {
 755                 next_kbuf[4] = 'A' + i;
 756                 client.put(Str(next_kbuf, 5), Str());
 757             }
 758         } else if (rand < p_remove2) {
 759             for (int i = sep - 1; i >= 0; --i) {
 760                 next_kbuf[4] = 'A' + i;
 761                 client.remove(Str(next_kbuf, 5));
 762             }
 763         } else {
 764             /* do nothing */
 765         }
 766
 767         client.wait_all();
 768
 769         if (put_status == Inserted) {
 770             ++x;
 771             xstr.set(x);
 772             client.put(Str(sbuf, 4), xstr.string());
 773         }
 774     }
 775     double t1 = client.now();
 776
 777     Json result;
 778     kvtest_set_time(result, "rounds", nrounds, t1 - t0);
 779     client.report(result);
 780 }
 781
 782 template <typename C>
 783 void kvtest_wd2_check(C &client)
 784 {
 785     if (client.id() != 0)
 786         return;
 787
 788     int n;
 789     client.get(Str("n"), &n);
 790     client.wait_all();
 791     always_assert(n > 1);
 792     Json result;
 793
 794     char buf[32];
 795     for (int i = 0; i < n; ++i) {
 796         int s, k;
 797         snprintf(buf, sizeof(buf), "k%03d", i);
 798         client.get(Str(buf, 4), &k);
 799         snprintf(buf, sizeof(buf), "s%03d", i);
 800         client.get(Str(buf, 4), &s);
 801         client.wait_all();
 802         if (!(s >= 0 && (s == k || s == k + 1 || k == -1)))
 803             fprintf(stderr, "problem: s%03d=%d vs. k%03d=%d\n",
 804                     i, s, i, k);
 805         result.set("thread" + String(i), Json().push_back(s).push_back(k));
 806     }
 807
 808     client.report(result);
 809 }
 810
 811 // Create a range of keys [initial_pos, initial_pos + n)
 812 // where key k == initial_pos + i has value (n - 1 - i).
 813 // Many overwrites.
 814 template <typename C>
 815 void kvtest_tri1(unsigned initial_pos, int incr, C &client)
 816 {
 817     incr = std::max(incr, client.nthreads());
 818     unsigned n = 0;
 819     Json result = Json();
 820
 821     double t0 = client.now();
 822     for (unsigned x = 0; x < client.limit(); ++x)
 823         for (unsigned y = 0, z = x; y <= x; ++y, --z, ++n)
 824             client.put(initial_pos + y * incr, z);
 825     client.wait_all();
 826     double t1 = client.now();
 827
 828     kvtest_set_time(result, "puts", n, t1 - t0);
 829     kvtest_set_time(result, "ops", n, t1 - t0);
 830     client.report(result);
 831 }
 832
 833 template <typename C>
 834 void kvtest_tri1_check(unsigned initial_pos, int incr, C &client)
 835 {
 836     incr = std::max(incr, client.nthreads());
 837     unsigned n = 0;
 838     Json result = Json();
 839
 840     double t0 = client.now();
 841     for (unsigned x = 0; x < client.limit(); ++x, ++n)
 842         client.get_check(initial_pos + x * incr, client.limit() - 1 - x);
 843     client.wait_all();
 844     double t1 = client.now();
 845
 846     kvtest_set_time(result, "gets", n, t1 - t0);
 847     kvtest_set_time(result, "ops", n, t1 - t0);
 848     client.report(result);
 849 }
 850
 851
 852 #define PALMN   128000000
 853 enum { PalmBatch = 8192 / 24 };
 854 #define PALM_DEBUG 1    // use get_check in palmb, which force palm::get
 855                         // to touch the cachline of the value
 856 template <typename C>
 857 void kvtest_palma(C &client)
 858 {
 859     Json result = Json();
 860     double t0 = client.now();
 861     for (int i = 0; i < PALMN; i++) {
 862         uint64_t v = i + 1;
 863         client.put(i, v);
 864     }
 865     client.wait_all();
 866     double t1 = client.now();
 867     kvtest_set_time(result, "ops", PALMN, t1 - t0);
 868     client.report(result);
 869 }
 870
 871 inline int compare_int(const void *a, const void *b)
 872 {
 873     return compare(*(uint64_t *)a, *(uint64_t *)b);
 874 }
 875
 876 template <typename C>
 877 void kvtest_palmb_seed(C &client, int seed)
 878 {
 879     Json result = Json();
 880     client.rand.reset(seed);
 881     double t0 = client.now();
 882     int n;
 883     int nquery = 0;
 884     uint64_t a[PalmBatch];
 885     for (n = 0; !client.timeout(0); ++n) {
 886         uint64_t x = (uint64_t) client.rand.next();
 887         x %= (PALMN / 10);
 888         a[nquery++] = x;
 889         if (nquery == PalmBatch) {
 890             qsort(a, PalmBatch, sizeof(a[0]), compare_int);
 891             for (int j = 0; j < PalmBatch && !client.timeout(0); j++) {
 892 #if PALM_DEBUG
 893                 uint64_t v = a[j] + 1;
 894                 client.get_check(a[j], v);
 895 #else
 896                 client.get(a[j]);
 897 #endif
 898             }
 899             nquery = 0;
 900         }
 901     }
 902     client.wait_all();
 903     double t1 = client.now();
 904     kvtest_set_time(result, "ops", n, t1 - t0);
 905     client.report(result);
 906 }
 907
 908 template <typename C>
 909 void kvtest_palmb(C &client)
 910 {
 911     kvtest_palmb_seed(client, kvtest_first_seed + client.id() % 48);
 912 }
 913
 914 template <typename C>
 915 void kvtest_ycsbk_seed(C &client, int seed)
 916 {
 917     client.rand.reset(seed);
 918     double tp0 = client.now();
 919     int n;
 920     char key[512], val[512];
 921     for (n = 0; !client.timeout(0) && n < 1000000; ++n) {
 922         strcpy(key, "user");
 923         int p = 4;
 924         for (int i = 0; i < 18; i++, p++)
 925             key[p] = '0' + (client.rand.next() % 10);
 926         key[p] = 0;
 927         int32_t v = (int32_t) client.rand.next();
 928         sprintf(val, "%d", v);
 929         client.put(Str(key, strlen(key)), Str(val, strlen(val)));
 930     }
 931     client.wait_all();
 932     double tp1 = client.now();
 933
 934     client.puts_done();
 935     client.notice("now getting\n");
 936     client.rand.reset(seed);
 937     double tg0 = client.now();
 938     int g;
 939     for (g = 0; g < n && !client.timeout(1); ++g) {
 940         strcpy(key, "user");
 941         int p = 4;
 942         for (int i = 0; i < 18; i++, p++)
 943             key[p] = '0' + (client.rand.next() % 10);
 944         key[p] = 0;
 945         int32_t v = (int32_t) client.rand.next();
 946         sprintf(val, "%d", v);
 947         client.get_check(Str(key, strlen(key)), Str(val, strlen(val)));
 948     }
 949     client.wait_all();
 950     double tg1 = client.now();
 951
 952     Json result = Json();
 953     kvtest_set_time(result, "puts", n, tp1 - tp0);
 954     kvtest_set_time(result, "gets", g, tg1 - tg0);
 955     kvtest_set_time(result, "ops", n + g, (tp1 - tp0) + (tg1 - tg0));
 956     client.report(result);
 957 }
 958
 959 template <typename C>
 960 void kvtest_ycsbk(C &client)
 961 {
 962     kvtest_ycsbk_seed(client, kvtest_first_seed + client.id() % 48);
 963 }
 964
 965 template <typename C>
 966 void
 967 kvtest_bdb(C &client)
 968 {
 969     enum { nrec = 500000, keylen = 8, datalen = 32 };
 970     char key[keylen + 1];
 971     char val[datalen + 1];
 972     memset(val, '^', sizeof(val));
 973     val[datalen] = 0;
 974     key[keylen] = 0;
 975     srandom(0);
 976     for (int n = 0; n < nrec; n++) {
 977         for (int i = 0; i < keylen; i++)
 978             key[i] = 'a' + random() % 26;
 979         client.put(key, val);
 980     }
 981     client.wait_all();
 982
 983     srandom(0);
 984     double t0 = now();
 985     unsigned long n;
 986     for (n = 0; n < 10000000; n++) {
 987         for (int i = 0; i < keylen; i++)
 988             key[i] = 'a' + random() % 26;
 989         client.get_check(key, val);
 990         if (n % nrec == 0)
 991             srandom(0);
 992     }
 993     double t1 = now();
 994     Json result = Json();
 995     kvtest_set_time(result, "ops", n, t1 - t0);
 996     client.report(result);
 997 }
 998
 999 enum { NLongParts = 16 };
1000
1001 template <typename C>
1002 void
1003 kvtest_long_init(C &client)
1004 {
1005     assert(client.id() < NLongParts);
1006     int seed = kvtest_first_seed + client.id();
1007     client.rand.reset(seed);
1008     const int keylen = client.keylen();
1009     const int prefixLen = client.prefixLen();
1010     const char minkltr = client.minkeyletter();
1011     const char maxkltr = client.maxkeyletter();
1012     assert(prefixLen < keylen);
1013     const uint32_t nkeysPerPart = client.nkeys() / NLongParts;
1014     char key[512], val[512];
1015     val[8] = 0;
1016     memset(key, '^', prefixLen);
1017     double t0 = now();
1018     unsigned long n;
1019     for(n = 0; n < nkeysPerPart; ++n){
1020         for (int i = prefixLen; i < keylen; i++)
1021             key[i] = minkltr + client.rand.next() % (maxkltr - minkltr + 1);
1022         key[keylen] = 0;
1023         memcpy(val, key + keylen - 8, 8);
1024         client.put(key, val);
1025         client.rand.next();
1026     }
1027     client.wait_all();
1028     double t1 = now();
1029
1030     Json result = Json();
1031     kvtest_set_time(result, "puts", n, t1 - t0);
1032     client.report(result);
1033 }
1034
1035 template <typename C>
1036 void
1037 kvtest_long_go(C &client)
1038 {
1039     const int keylen = client.keylen();
1040     const int prefixLen = client.prefixLen();
1041     assert(prefixLen < keylen);
1042     const uint32_t nKeysPerPart = client.nkeys() / NLongParts;
1043     const char minkltr = client.minkeyletter();
1044     const char maxkltr = client.maxkeyletter();
1045     char key[512], val[512];
1046     memset(key, '^', prefixLen);
1047     val[8] = 0;
1048     double t0 = now();
1049     long n = 0;
1050     int cur_cid = client.id() % NLongParts;
1051     while (!client.timeout(0)) {
1052         client.rand.reset(kvtest_first_seed + cur_cid);
1053         uint32_t op;
1054         for(op = 0; !client.timeout(0) && op < nKeysPerPart; op++){
1055             for (int i = prefixLen; i < keylen; i++)
1056                 key[i] = minkltr + client.rand.next() % (maxkltr - minkltr + 1);
1057             memcpy(val, key + keylen - 8, 8);
1058             key[keylen] = 0;
1059             if (client.rand.next() % 100 < client.getratio())
1060                 client.get_check(key, val);
1061             else
1062                 client.put(key, val);
1063         }
1064         cur_cid = (cur_cid + 1) % NLongParts;
1065         n += op;
1066     }
1067     client.wait_all();
1068     double t1 = now();
1069
1070     Json result = Json();
1071     kvtest_set_time(result, "ops", n, t1 - t0);
1072     client.report(result);
1073 }
1074
1075 template <typename C>
1076 void
1077 kvtest_wscale(C &client)
1078 {
1079     double t0 = now();
1080     client.rand.reset(kvtest_first_seed + client.id() % 48);
1081     long n;
1082     for(n = 0; !client.timeout(0); n++){
1083         long x = client.rand.next();
1084         client.put(x, x + 1);
1085     }
1086     client.wait_all();
1087     double t1 = now();
1088     Json result = Json();
1089     kvtest_set_time(result, "puts", n, t1 -t0);
1090     client.report(result);
1091 }
1092
1093 template <typename C>
1094 void
1095 kvtest_ruscale_init(C &client)
1096 {
1097     double t0 = now();
1098     client.rand.reset(kvtest_first_seed + client.id() % 48);
1099     const int ruscale_partsz = client.ruscale_partsz();
1100     const int firstkey = ruscale_partsz * client.ruscale_init_part_no();
1101     // Insert in random order
1102     int *keys = (int *) malloc(sizeof(int) * ruscale_partsz);
1103     always_assert(keys);
1104     for(int i = 0; i < ruscale_partsz; i++)
1105         keys[i] = i + firstkey;
1106     for(int i = 0; i < ruscale_partsz; i++)
1107         std::swap(keys[i], keys[client.rand.next() % ruscale_partsz]);
1108     for(int i = 0; i < ruscale_partsz; i++){
1109         long x = keys[i];
1110         client.put(x, x + 1);
1111     }
1112     client.wait_all();
1113     double t1 = now();
1114     Json result = Json();
1115     kvtest_set_time(result, "puts", ruscale_partsz, t1 - t0);
1116     client.report(result);
1117     free(keys);
1118 }
1119
1120 template <typename C>
1121 void
1122 kvtest_rscale(C &client)
1123 {
1124     client.rand.reset(kvtest_first_seed + client.id() % 48);
1125     const long nseqkeys = client.nseqkeys();
1126     double t0 = now();
1127     long n;
1128     for(n = 0; !client.timeout(0); n++){
1129         long x = client.rand.next() % nseqkeys;
1130         client.get_check(x, x + 1);
1131     }
1132     client.wait_all();
1133     double t1 = now();
1134     Json result = Json();
1135     kvtest_set_time(result, "gets", n, t1 - t0);
1136     client.report(result);
1137 }
1138
1139 template <typename C>
1140 void
1141 kvtest_uscale(C &client)
1142 {
1143     client.rand.reset(kvtest_first_seed + client.id());
1144     const long nseqkeys = client.nseqkeys();
1145     double t0 = now();
1146     long n;
1147     for(n = 0; !client.timeout(0); n++){
1148         long x = client.rand.next() % nseqkeys;
1149         client.put(x, x + 1);
1150     }
1151     client.wait_all();
1152     double t1 = now();
1153     Json result = Json();
1154     kvtest_set_time(result, "puts", n, t1 - t0);
1155     client.report(result);
1156 }
1157
1158 template <typename C>
1159 void kvtest_udp1_seed(C &client, int seed)
1160 {
1161     client.rand.reset(seed);
1162     double tp0 = client.now();
1163     unsigned n;
1164     for (n = 0; !client.timeout(0); ++n)
1165         client.put(0, 1);
1166     client.wait_all();
1167     double tp1 = client.now();
1168
1169     client.puts_done();
1170     client.notice("now getting\n");
1171     int32_t *a = (int32_t *) malloc(sizeof(int32_t) * n);
1172     assert(a);
1173     client.rand.reset(seed);
1174     for (unsigned i = 0; i < n; ++i)
1175         a[i] = (int32_t) client.rand.next();
1176     for (unsigned i = 0; i < n; ++i)
1177         std::swap(a[i], a[client.rand.next() % n]);
1178
1179     double tg0 = client.now();
1180     unsigned g;
1181     for (g = 0; !client.timeout(1); ++g)
1182         client.get_check(0, 1);
1183     client.wait_all();
1184     double tg1 = client.now();
1185
1186     Json result = Json();
1187     kvtest_set_time(result, "puts", n, tp1 - tp0);
1188     kvtest_set_time(result, "gets", g, tg1 - tg0);
1189     kvtest_set_time(result, "ops", n + g, (tp1 - tp0) + (tg1 - tg0));
1190     client.report(result);
1191     free(a);
1192 }
1193
1194 template <typename C>
1195 void kvtest_udp1(C &client)
1196 {
1197     kvtest_udp1_seed(client, kvtest_first_seed + client.id() % 48);
1198 }
1199
1200 // do four million of inserts to distinct keys.
1201 // sometimes overwrites, but only w/ same value.
1202 // different clients might use same key sometimes.
1203 template <typename C>
1204 void kvtest_w1_seed(C &client, int seed)
1205 {
1206     int n;
1207     if (client.limit() == ~(uint64_t) 0)
1208         n = 4000000;
1209     else
1210         n = std::min(client.limit(), (uint64_t) INT_MAX);
1211     client.rand.reset(seed);
1212
1213     double t0 = now();
1214     for (int i = 0; i < n; i++) {
1215         long x = client.rand.next();
1216         client.put_key10(x, x + 1);
1217     }
1218     client.wait_all();
1219     double t1 = now();
1220
1221     Json result = Json().set("total", (long) (n / (t1 - t0)))
1222         .set("puts", n)
1223         .set("puts_per_sec", n / (t1 - t0));
1224     client.report(result);
1225 }
1226
1227 // do four million gets.
1228 // in a random order.
1229 // if we get in the same order that w1 put, performance is
1230 // about 15% better for b-tree.
1231 template <typename C>
1232 void kvtest_r1_seed(C &client, int seed)
1233 {
1234     int n;
1235     if (client.limit() == ~(uint64_t) 0)
1236         n = 4000000;
1237     else
1238         n = std::min(client.limit(), (uint64_t) INT_MAX);
1239     long *a = (long *) malloc(sizeof(long) * n);
1240     always_assert(a);
1241
1242     client.rand.reset(seed);
1243     for (int i = 0; i < n; i++)
1244         a[i] = client.rand.next();
1245     for (int i = 0; i < n; i++) {
1246         int i1 = client.rand.next() % n;
1247         long tmp = a[i];
1248         a[i] = a[i1];
1249         a[i1] = tmp;
1250     }
1251
1252     double t0 = now();
1253     for (int i = 0; i < n; i++)
1254         client.get_check_key10(a[i], a[i] + 1);
1255     client.wait_all();
1256     double t1 = now();
1257
1258     Json result = Json().set("total", (long) (n / (t1 - t0)))
1259         .set("gets", n)
1260         .set("gets_per_sec", n / (t1 - t0));
1261     client.report(result);
1262 }
1263
1264 // do four million of inserts to distinct keys.
1265 // sometimes overwrites, but only w/ same value.
1266 // different clients might use same key sometimes.
1267 template <typename C>
1268 void kvtest_wcol1at(C &client, int col, int seed, long maxkeys)
1269 {
1270     int n;
1271     if (client.limit() == ~(uint64_t) 0)
1272         n = 4000000;
1273     else
1274         n = std::min(client.limit(), (uint64_t) INT_MAX);
1275     client.rand.reset(seed);
1276
1277     double t0 = now();
1278     for (int i = 0; i < n; i++) {
1279         long x = client.rand.next() % maxkeys;
1280         client.put_col_key10(x, col, x + 1);
1281     }
1282     client.wait_all();
1283     double t1 = now();
1284
1285     Json result = Json().set("total", (long) (n / (t1 - t0)))
1286         .set("puts", n)
1287         .set("puts_per_sec", n / (t1 - t0));
1288     client.report(result);
1289 }
1290
1291 // do four million gets.
1292 // in a random order.
1293 // if we get in the same order that w1 put, performance is
1294 // about 15% better for b-tree.
1295 template <typename C>
1296 void kvtest_rcol1at(C &client, int col, int seed, long maxkeys)
1297 {
1298     int n;
1299     if (client.limit() == ~(uint64_t) 0)
1300         n = 4000000;
1301     else
1302         n = std::min(client.limit(), (uint64_t) INT_MAX);
1303     long *a = (long *) malloc(sizeof(long) * n);
1304     always_assert(a);
1305
1306     client.rand.reset(seed);
1307     for (int i = 0; i < n; i++)
1308         a[i] = client.rand.next() % maxkeys;
1309     for (int i = 0; i < n && 0; i++) {
1310         int i1 = client.rand.next() % n;
1311         long tmp = a[i];
1312         a[i] = a[i1];
1313         a[i1] = tmp;
1314     }
1315
1316     double t0 = now();
1317     for (int i = 0; i < n; i++)
1318         client.get_col_check_key10(a[i], col, a[i] + 1);
1319     client.wait_all();
1320     double t1 = now();
1321
1322     Json result = Json().set("total", (long) (n / (t1 - t0)))
1323         .set("gets", n)
1324         .set("gets_per_sec", n / (t1 - t0));
1325     client.report(result);
1326 }
1327
1328 // test scans with parallel inserts
1329 template <typename C>
1330 void kvtest_scan1(C &client, double writer_quiet)
1331 {
1332     int n, wq65536 = int(writer_quiet * 65536);
1333     if (client.limit() == ~(uint64_t) 0)
1334         n = 10000;
1335     else
1336         n = std::min(client.limit(), (uint64_t) 97655);
1337     Json result;
1338
1339     if (client.id() % 24 == 0) {
1340         for (int i = 0; i < n; ++i)
1341             client.put_key8(i * 1024, i);
1342         client.wait_all();
1343
1344         int pos = 0, mypos = 0, scansteps = 0;
1345         quick_istr key;
1346         std::vector<Str> keys, values;
1347         Json errj;
1348         while (!client.timeout(0) && errj.size() < 1000) {
1349             key.set(pos, 8);
1350             client.scan_sync(key.string(), 100, keys, values);
1351             if (keys.size() == 0) {
1352                 if (mypos < n * 1024)
1353                     errj.push_back("missing " + String(mypos) + " through " + String((n - 1) * 1024));
1354                 pos = mypos = 0;
1355             } else {
1356                 for (size_t i = 0; i < keys.size(); ++i) {
1357                     int val = keys[i].to_i();
1358                     if (val < 0) {
1359                         errj.push_back("unexpected key " + String(keys[i].s, keys[i].len));
1360                         continue;
1361                     }
1362                     if (val < pos)
1363                         errj.push_back("got " + String(keys[i].s, keys[i].len) + ", expected " + String(pos) + " or later");
1364                     pos = val + 1;
1365                     while (val > mypos) {
1366                         errj.push_back("got " + String(keys[i].s, keys[i].len) + ", missing " + String(mypos) + " @" + String(scansteps) + "+" + String(i));
1367                         mypos += 1024;
1368                     }
1369                     if (val == mypos) {
1370                         mypos = val + 1024;
1371                         ++scansteps;
1372                     }
1373                 }
1374             }
1375             client.rcu_quiesce();
1376         }
1377         if (errj.size() >= 1000)
1378             errj.push_back("too many errors, giving up");
1379         result.set("ok", errj.empty()).set("scansteps", scansteps);
1380         if (errj)
1381             result.set("errors", errj);
1382
1383     } else {
1384         int delta = 1 + (client.id() % 30) * 32, rounds = 0;
1385         while (!client.timeout(0)) {
1386             int first = (client.rand.next() % n) * 1024 + delta;
1387             int rand = client.rand.next() % 65536;
1388             if (rand < wq65536) {
1389                 for (int d = 0; d < 31; ++d)
1390                     relax_fence();
1391             } else if (rounds > 100 && (rand % 2) == 1) {
1392                 for (int d = 0; d < 31; ++d)
1393                     client.remove_key8(d + first);
1394             } else {
1395                 for (int d = 0; d < 31; ++d)
1396                     client.put_key8(d + first, d + first);
1397             }
1398             ++rounds;
1399             client.rcu_quiesce();
1400         }
1401     }
1402
1403     client.report(result);
1404 }
1405
1406 // test reverse scans with parallel inserts
1407 template <typename C>
1408 void kvtest_rscan1(C &client, double writer_quiet)
1409 {
1410     int n, wq65536 = int(writer_quiet * 65536);
1411     if (client.limit() == ~(uint64_t) 0)
1412         n = 10000;
1413     else
1414         n = std::min(client.limit(), (uint64_t) 97655);
1415     Json result;
1416
1417     if (client.id() % 24 == 0) {
1418         for (int i = 1; i <= n; ++i)
1419             client.put_key8(i * 1024, i);
1420         client.wait_all();
1421
1422         int pos = (n + 1) * 1024, mypos = n * 1024, scansteps = 0;
1423         quick_istr key;
1424         std::vector<Str> keys, values;
1425         Json errj;
1426         while (!client.timeout(0) && errj.size() < 1000) {
1427             key.set(pos, 8);
1428             client.rscan_sync(key.string(), 100, keys, values);
1429             if (keys.size() == 0) {
1430                 if (mypos > 0)
1431                     errj.push_back("missing 1024 through " + String(mypos) + " @" + String(scansteps));
1432                 pos = (n + 1) * 1024, mypos = n * 1024;
1433             } else {
1434                 for (size_t i = 0; i < keys.size(); ++i) {
1435                     int val = keys[i].to_i();
1436                     if (val < 0) {
1437                         errj.push_back("unexpected key " + String(keys[i].s, keys[i].len));
1438                         continue;
1439                     }
1440                     if (val > pos)
1441                         errj.push_back("got " + String(keys[i].s, keys[i].len) + ", expected " + String(pos) + " or less");
1442                     pos = val - 1;
1443                     while (val < mypos) {
1444                         String last;
1445                         if (i)
1446                             last = String(keys[i-1].s, keys[i-1].len);
1447                         else
1448                             last = String(key.string().s, key.string().len);
1449                         errj.push_back("got " + String(keys[i].s, keys[i].len) + ", missing " + String(mypos) + " @" + String(scansteps) + "+" + String(i) + ", last " + last);
1450                         mypos -= 1024;
1451                     }
1452                     if (val == mypos) {
1453                         mypos = val - 1024;
1454                         ++scansteps;
1455                     }
1456                 }
1457             }
1458             client.rcu_quiesce();
1459         }
1460         if (errj.size() >= 1000)
1461             errj.push_back("too many errors, giving up");
1462         result.set("ok", errj.empty()).set("scansteps", scansteps);
1463         if (errj)
1464             result.set("errors", errj);
1465
1466     } else {
1467         int delta = 1 + (client.id() % 30) * 32, rounds = 0;
1468         while (!client.timeout(0)) {
1469             int first = (client.rand.next() % n + 1) * 1024 + delta;
1470             int rand = client.rand.next() % 65536;
1471             if (rand < wq65536) {
1472                 for (int d = 0; d < 31; ++d)
1473                     relax_fence();
1474             } else if (rounds > 100 && (rand % 2) == 1) {
1475                 for (int d = 0; d < 31; ++d)
1476                     client.remove_key8(d + first);
1477             } else {
1478                 for (int d = 0; d < 31; ++d)
1479                     client.put_key8(d + first, d + first);
1480             }
1481             ++rounds;
1482             client.rcu_quiesce();
1483         }
1484     }
1485
1486     client.report(result);
1487 }
1488
1489 // test concurrent splits with removes in lower layers
1490 template <typename C>
1491 void kvtest_splitremove1(C &client)
1492 {
1493     // XXX these parameters depend on masstree constants...
1494     int leaf_width = 15, internode_width = 15;
1495     int num_keys = leaf_width * (internode_width + 1) + 1;
1496     int trigger_key = num_keys - 15;
1497     int rounds = 0;
1498     Json result, errj;
1499
1500     if (client.id() == 0) {
1501         while (1) {
1502             for (int i = 0; i < num_keys; ++i)
1503                 client.put_key16(i + 100, i + 101);
1504             client.rcu_quiesce();
1505             for (int i = trigger_key + 1; i < num_keys + 10; ++i)
1506                 client.remove_key16(i + 100);
1507             client.rcu_quiesce();
1508             for (int i = 0; i < leaf_width * internode_width; ++i)
1509                 client.put_key16(i, i + 1);
1510
1511             client.put(client.nthreads(), client.nthreads() + 1);
1512             for (int i = 1; i < client.nthreads(); ++i)
1513                 client.put(i, i + 1);
1514             for (int i = 1; i < client.nthreads(); ++i) {
1515                 while (!client.timeout(0) && client.get_sync(i))
1516                     /* do nothing */;
1517             }
1518             client.remove_key16(trigger_key);
1519             client.remove(client.nthreads());
1520             if (client.timeout(0))
1521                 break;
1522
1523             for (int i = 0; i < num_keys; ++i) {
1524                 client.remove_key16(i);
1525                 client.remove_key16(i + 100);
1526             }
1527             for (int i = 0; i < 10; ++i)
1528                 client.rcu_quiesce();
1529             ++rounds;
1530         }
1531
1532     } else {
1533         quick_istr me(client.id()), trigger(trigger_key, 16);
1534         while (1) {
1535             while (!client.timeout(0) && !client.get_sync_key16(trigger_key))
1536                 client.rcu_quiesce();
1537             if (client.timeout(0))
1538                 break;
1539
1540             for (int i = 0; !client.get_sync(me.string()); ++i) {
1541                 if (!client.get_sync(trigger.string()) && !client.timeout(0)) {
1542                     if (errj.size() == 100)
1543                         errj.push_back("more errors");
1544                     else if (errj.size() < 100)
1545                         errj.push_back("key " + String(trigger.string()) + " missing after " + String(rounds) + " rounds, counter " + String(i));
1546                     break;
1547                 }
1548                 client.rcu_quiesce();
1549             }
1550
1551             while (!client.timeout(0) && !client.get_sync(me.string()))
1552                 client.rcu_quiesce();
1553             client.remove(me.string());
1554             while (!client.timeout(0) && client.get_sync(client.nthreads()))
1555                 client.rcu_quiesce();
1556             if (client.timeout(0))
1557                 break;
1558
1559             for (int i = 0; i < 10; ++i)
1560                 client.rcu_quiesce();
1561             ++rounds;
1562         }
1563     }
1564
1565     result.set("ok", errj.empty()).set("rounds", rounds);
1566     if (errj)
1567         result.set("errors", errj);
1568     client.report(result);
1569 }
1570
1571 template <typename C>
1572 void kvtest_url_seed(C &client)
1573 {
1574     if (!client.param("file").is_s()) {
1575         client.report(Json::object("ok", false, "error", "need 'file=URLFILE' parameter"));
1576         return;
1577     }
1578
1579     std::ifstream infile_url_init(client.param("file").to_s());
1580     std::ifstream infile_url_del_get(client.param("file").to_s());
1581     std::string ops;
1582     std::string url;
1583     unsigned count_i = 0;
1584     unsigned count_d = 0;
1585     unsigned count_g = 0;
1586
1587     double t0 = client.now();
1588     while (count_i < client.limit() && infile_url_init.good()) {
1589         //do the following alternately:
1590         //insert 10 urls, then delete 5 inserted urls
1591         for (int i = 0; i != 10 && infile_url_init >> ops >> url; ++i, ++count_i)
1592             client.put(url, 2014);
1593         for (int i = 0; i != 5 && infile_url_del_get >> ops >> url; ++i, ++count_d)
1594             client.remove(url);
1595     }
1596     client.wait_all();
1597     client.puts_done();
1598     double t1 = client.now();
1599     infile_url_init.close();
1600     client.notice("\ninsert done\n");
1601
1602     //query all the inserted urls
1603     double t2 = client.now();
1604     while (count_d + count_g != count_i && infile_url_del_get >> ops >> url) {
1605         client.get_check(Str(url), 2014);
1606         ++count_g;
1607     }
1608     client.wait_all();
1609     double t3 = client.now();
1610
1611     // client.notice("Total pool memory: %d\n", client.ti_->poolmem);
1612     // client.notice("Total general memory: %d\n", client.ti_->genmem);
1613     // client.notice("Total MEMORY: %d\n", client.ti_->poolmem + client.ti_->genmem);
1614
1615     Json result = Json::object("puts", count_i, "removes", count_d);
1616     kvtest_set_time(result, "gets", count_g, t3 - t2);
1617     kvtest_set_time(result, "ops", count_i + count_d, t1 - t0);
1618     client.report(result);
1619 }
1620
1621 template <typename C>
1622 void kvtest_url(C &client)
1623 {
1624   kvtest_url_seed(client);
1625 }
1626
1627 #endif