silo/masstree/mttest.cc

   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 // -*- mode: c++ -*-
  17 // mttest: key/value tester
  18 //
  19
  20 #include <stdio.h>
  21 #include <stdarg.h>
  22 #include <ctype.h>
  23 #include <stdlib.h>
  24 #include <unistd.h>
  25 #include <sys/socket.h>
  26 #include <netinet/in.h>
  27 #include <netinet/tcp.h>
  28 #include <sys/select.h>
  29 #include <sys/mman.h>
  30 #include <sys/stat.h>
  31 #include <sys/wait.h>
  32 #include <sys/utsname.h>
  33 #include <limits.h>
  34 #if HAVE_NUMA_H
  35 #include <numa.h>
  36 #endif
  37 #if HAVE_SYS_EPOLL_H
  38 #include <sys/epoll.h>
  39 #endif
  40 #if HAVE_EXECINFO_H
  41 #include <execinfo.h>
  42 #endif
  43 #if __linux__
  44 #include <asm-generic/mman.h>
  45 #endif
  46 #include <fcntl.h>
  47 #include <assert.h>
  48 #include <string.h>
  49 #include <pthread.h>
  50 #include <math.h>
  51 #include <signal.h>
  52 #include <errno.h>
  53 #ifdef __linux__
  54 #include <malloc.h>
  55 #endif
  56 #include "nodeversion.hh"
  57 #include "kvstats.hh"
  58 #include "query_masstree.hh"
  59 #include "masstree_tcursor.hh"
  60 #include "masstree_insert.hh"
  61 #include "masstree_remove.hh"
  62 #include "masstree_scan.hh"
  63 #include "timestamp.hh"
  64 #include "json.hh"
  65 #include "kvtest.hh"
  66 #include "kvrandom.hh"
  67 #include "kvrow.hh"
  68 #include "kvio.hh"
  69 #include "clp.h"
  70 #include <algorithm>
  71 #include <numeric>
  72
  73 static std::vector<int> cores;
  74 volatile bool timeout[2] = {false, false};
  75 double duration[2] = {10, 0};
  76 // Do not start timer until asked
  77 static bool lazy_timer = false;
  78 int kvtest_first_seed = 31949;
  79 uint64_t test_limit = ~uint64_t(0);
  80 static Json test_param;
  81
  82 bool quiet = false;
  83 bool print_table = false;
  84 static const char *gid = NULL;
  85
  86 // all default to the number of cores
  87 static int udpthreads = 0;
  88 static int tcpthreads = 0;
  89
  90 static bool tree_stats = false;
  91 static bool json_stats = false;
  92 static bool pinthreads = false;
  93 volatile uint64_t globalepoch = 1;     // global epoch, updated by main thread regularly
  94 kvepoch_t global_log_epoch = 0;
  95 static int port = 2117;
  96 static int rscale_ncores = 0;
  97
  98 #if MEMSTATS && HAVE_NUMA_H && HAVE_LIBNUMA
  99 struct mttest_numainfo {
 100     long long free;
 101     long long size;
 102 };
 103 std::vector<mttest_numainfo> numa;
 104 #endif
 105
 106 volatile bool recovering = false; // so don't add log entries, and free old value immediately
 107 kvtimestamp_t initial_timestamp;
 108
 109 static const char *threadcounter_names[(int) tc_max];
 110
 111 /* running local tests */
 112 void test_timeout(int) {
 113     size_t n;
 114     for (n = 0; n < arraysize(timeout) && timeout[n]; ++n)
 115         /* do nothing */;
 116     if (n < arraysize(timeout)) {
 117         timeout[n] = true;
 118         if (n + 1 < arraysize(timeout) && duration[n + 1])
 119             xalarm(duration[n + 1]);
 120     }
 121 }
 122
 123 template <typename T>
 124 struct kvtest_client {
 125     kvtest_client()
 126         : limit_(test_limit), ncores_(udpthreads), kvo_() {
 127     }
 128     ~kvtest_client() {
 129         if (kvo_)
 130             free_kvout(kvo_);
 131     }
 132
 133     int nthreads() const {
 134         return udpthreads;
 135     }
 136     int id() const {
 137         return ti_->index();
 138     }
 139     void set_table(T *table, threadinfo *ti) {
 140         table_ = table;
 141         ti_ = ti;
 142     }
 143     void reset(const String &test, int trial) {
 144         report_ = Json().set("table", T().name())
 145             .set("test", test).set("trial", trial)
 146             .set("thread", ti_->index());
 147     }
 148     static void start_timer() {
 149         always_assert(lazy_timer && "Cannot start timer without lazy_timer option");
 150         always_assert(duration[0] && "Must specify timeout[0]");
 151         xalarm(duration[0]);
 152     }
 153
 154     bool timeout(int which) const {
 155         return ::timeout[which];
 156     }
 157     uint64_t limit() const {
 158         return limit_;
 159     }
 160     Json param(const String& name) const {
 161         return test_param[name];
 162     }
 163
 164     int ncores() const {
 165         return ncores_;
 166     }
 167     double now() const {
 168         return ::now();
 169     }
 170     int ruscale_partsz() const {
 171         return (140 * 1000000) / 16;
 172     }
 173     int ruscale_init_part_no() const {
 174         return ti_->index();
 175     }
 176     long nseqkeys() const {
 177         return 16 * ruscale_partsz();
 178     }
 179
 180     void get(long ikey);
 181     bool get_sync(const Str &key);
 182     bool get_sync(const Str &key, Str &value);
 183     bool get_sync(long ikey) {
 184         quick_istr key(ikey);
 185         return get_sync(key.string());
 186     }
 187     bool get_sync_key16(long ikey) {
 188         quick_istr key(ikey, 16);
 189         return get_sync(key.string());
 190     }
 191     void get_check(const Str &key, const Str &expected);
 192     void get_check(const char *key, const char *expected) {
 193         get_check(Str(key), Str(expected));
 194     }
 195     void get_check(long ikey, long iexpected) {
 196         quick_istr key(ikey), expected(iexpected);
 197         get_check(key.string(), expected.string());
 198     }
 199     void get_check(const Str &key, long iexpected) {
 200         quick_istr expected(iexpected);
 201         get_check(key, expected.string());
 202     }
 203     void get_check_key8(long ikey, long iexpected) {
 204         quick_istr key(ikey, 8), expected(iexpected);
 205         get_check(key.string(), expected.string());
 206     }
 207     void get_col_check(const Str &key, int col, const Str &value);
 208     void get_col_check(long ikey, int col, long ivalue) {
 209         quick_istr key(ikey), value(ivalue);
 210         get_col_check(key.string(), col, value.string());
 211     }
 212     void get_col_check_key10(long ikey, int col, long ivalue) {
 213         quick_istr key(ikey, 10), value(ivalue);
 214         get_col_check(key.string(), col, value.string());
 215     }
 216     //void many_get_check(int nk, long ikey[], long iexpected[]);
 217
 218     void scan_sync(const Str &firstkey, int n,
 219                    std::vector<Str> &keys, std::vector<Str> &values);
 220     void rscan_sync(const Str &firstkey, int n,
 221                     std::vector<Str> &keys, std::vector<Str> &values);
 222
 223     void put(const Str &key, const Str &value);
 224     void put(const char *key, const char *value) {
 225         put(Str(key), Str(value));
 226     }
 227     void put(long ikey, long ivalue) {
 228         quick_istr key(ikey), value(ivalue);
 229         put(key.string(), value.string());
 230     }
 231     void put(const Str &key, long ivalue) {
 232         quick_istr value(ivalue);
 233         put(key, value.string());
 234     }
 235     void put_key8(long ikey, long ivalue) {
 236         quick_istr key(ikey, 8), value(ivalue);
 237         put(key.string(), value.string());
 238     }
 239     void put_key16(long ikey, long ivalue) {
 240         quick_istr key(ikey, 16), value(ivalue);
 241         put(key.string(), value.string());
 242     }
 243     void put_col(const Str &key, int col, const Str &value);
 244     void put_col(long ikey, int col, long ivalue) {
 245         quick_istr key(ikey), value(ivalue);
 246         put_col(key.string(), col, value.string());
 247     }
 248     void put_col_key10(long ikey, int col, long ivalue) {
 249         quick_istr key(ikey, 10), value(ivalue);
 250         put_col(key.string(), col, value.string());
 251     }
 252
 253     void remove(const Str &key);
 254     void remove(long ikey) {
 255         quick_istr key(ikey);
 256         remove(key.string());
 257     }
 258     void remove_key8(long ikey) {
 259         quick_istr key(ikey, 8);
 260         remove(key.string());
 261     }
 262     void remove_key16(long ikey) {
 263         quick_istr key(ikey, 16);
 264         remove(key.string());
 265     }
 266     bool remove_sync(const Str &key);
 267     bool remove_sync(long ikey) {
 268         quick_istr key(ikey);
 269         return remove_sync(key.string());
 270     }
 271
 272     void puts_done() {
 273     }
 274     void wait_all() {
 275     }
 276     void rcu_quiesce() {
 277         uint64_t e = timestamp() >> 16;
 278         if (e != globalepoch)
 279             globalepoch = e;
 280         ti_->rcu_quiesce();
 281     }
 282     String make_message(lcdf::StringAccum &sa) const;
 283     void notice(const char *fmt, ...);
 284     void fail(const char *fmt, ...);
 285     const Json& report(const Json& x) {
 286         return report_.merge(x);
 287     }
 288     void finish() {
 289         Json counters;
 290         for (int i = 0; i < tc_max; ++i)
 291             if (uint64_t c = ti_->counter(threadcounter(i)))
 292                 counters.set(threadcounter_names[i], c);
 293         if (counters)
 294             report_.set("counters", counters);
 295         if (!quiet)
 296             fprintf(stderr, "%d: %s\n", ti_->index(), report_.unparse().c_str());
 297     }
 298
 299     T *table_;
 300     threadinfo *ti_;
 301     query<row_type> q_[1];
 302     kvrandom_lcg_nr rand;
 303     uint64_t limit_;
 304     Json report_;
 305     int ncores_;
 306     kvout *kvo_;
 307
 308   private:
 309     void output_scan(const Json& req, std::vector<Str>& keys, std::vector<Str>& values) const;
 310 };
 311
 312 static volatile int kvtest_printing;
 313
 314 template <typename T> inline void kvtest_print(const T &table, FILE *f, int indent, threadinfo *ti) {
 315     // only print out the tree from the first failure
 316     while (!bool_cmpxchg((int *) &kvtest_printing, 0, ti->index() + 1))
 317         /* spin */;
 318     table.print(f, indent);
 319 }
 320
 321 template <typename T> inline void kvtest_json_stats(T& table, Json& j, threadinfo& ti) {
 322     table.json_stats(j, ti);
 323 }
 324
 325 template <typename T>
 326 void kvtest_client<T>::get(long ikey) {
 327     quick_istr key(ikey);
 328     Str val;
 329     (void) q_[0].run_get1(table_->table(), key.string(), 0, val, *ti_);
 330 }
 331
 332 template <typename T>
 333 bool kvtest_client<T>::get_sync(const Str& key) {
 334     Str val;
 335     return q_[0].run_get1(table_->table(), key, 0, val, *ti_);
 336 }
 337
 338 template <typename T>
 339 bool kvtest_client<T>::get_sync(const Str &key, Str &value) {
 340     return q_[0].run_get1(table_->table(), key, 0, value, *ti_);
 341 }
 342
 343 template <typename T>
 344 void kvtest_client<T>::get_check(const Str &key, const Str &expected) {
 345     Str val;
 346     if (!q_[0].run_get1(table_->table(), key, 0, val, *ti_))
 347         fail("get(%.*s) failed (expected %.*s)\n", key.len, key.s,
 348              expected.len, expected.s);
 349     else if (expected != val)
 350         fail("get(%.*s) returned unexpected value %.*s (expected %.*s)\n",
 351              key.len, key.s, std::min(val.len, 40), val.s,
 352              expected.len, expected.s);
 353 }
 354
 355 template <typename T>
 356 void kvtest_client<T>::get_col_check(const Str &key, int col,
 357                                      const Str &expected) {
 358     Str val;
 359     if (!q_[0].run_get1(table_->table(), key, col, val, *ti_))
 360         fail("get.%d(%.*s) failed (expected %.*s)\n",
 361              col, key.len, key.s, expected.len, expected.s);
 362     else if (expected != val)
 363         fail("get.%d(%.*s) returned unexpected value %.*s (expected %.*s)\n",
 364              col, key.len, key.s, std::min(val.len, 40), val.s,
 365              expected.len, expected.s);
 366 }
 367
 368 /*template <typename T>
 369 void kvtest_client<T>::many_get_check(int nk, long ikey[], long iexpected[]) {
 370     std::vector<quick_istr> ka(2*nk, quick_istr());
 371     for(int i = 0; i < nk; i++){
 372       ka[i].set(ikey[i]);
 373       ka[i+nk].set(iexpected[i]);
 374       q_[i].begin_get1(ka[i].string());
 375     }
 376     table_->many_get(q_, nk, *ti_);
 377     for(int i = 0; i < nk; i++){
 378       Str val = q_[i].get1_value();
 379       if (ka[i+nk] != val){
 380         printf("get(%ld) returned unexpected value %.*s (expected %ld)\n",
 381              ikey[i], std::min(val.len, 40), val.s, iexpected[i]);
 382         exit(1);
 383       }
 384     }
 385 }*/
 386
 387 template <typename T>
 388 void kvtest_client<T>::scan_sync(const Str &firstkey, int n,
 389                                  std::vector<Str> &keys,
 390                                  std::vector<Str> &values) {
 391     Json req = Json::array(0, 0, firstkey, n);
 392     q_[0].run_scan(table_->table(), req, *ti_);
 393     output_scan(req, keys, values);
 394 }
 395
 396 template <typename T>
 397 void kvtest_client<T>::rscan_sync(const Str &firstkey, int n,
 398                                   std::vector<Str> &keys,
 399                                   std::vector<Str> &values) {
 400     Json req = Json::array(0, 0, firstkey, n);
 401     q_[0].run_rscan(table_->table(), req, *ti_);
 402     output_scan(req, keys, values);
 403 }
 404
 405 template <typename T>
 406 void kvtest_client<T>::output_scan(const Json& req, std::vector<Str>& keys,
 407                                    std::vector<Str>& values) const {
 408     keys.clear();
 409     values.clear();
 410     for (int i = 2; i != req.size(); i += 2) {
 411         keys.push_back(req[i].as_s());
 412         values.push_back(req[i + 1].as_s());
 413     }
 414 }
 415
 416 template <typename T>
 417 void kvtest_client<T>::put(const Str &key, const Str &value) {
 418     q_[0].run_replace(table_->table(), key, value, *ti_);
 419 }
 420
 421 template <typename T>
 422 void kvtest_client<T>::put_col(const Str &key, int col, const Str &value) {
 423 #if !MASSTREE_ROW_TYPE_STR
 424     if (!kvo_)
 425         kvo_ = new_kvout(-1, 2048);
 426     Json x[2] = {Json(col), Json(String::make_stable(value))};
 427     q_[0].run_put(table_->table(), key, &x[0], &x[2], *ti_);
 428 #else
 429     (void) key, (void) col, (void) value;
 430     assert(0);
 431 #endif
 432 }
 433
 434 template <typename T> inline bool kvtest_remove(kvtest_client<T> &client, const Str &key) {
 435     return client.q_[0].run_remove(client.table_->table(), key, *client.ti_);
 436 }
 437
 438 template <typename T>
 439 void kvtest_client<T>::remove(const Str &key) {
 440     (void) kvtest_remove(*this, key);
 441 }
 442
 443 template <typename T>
 444 bool kvtest_client<T>::remove_sync(const Str &key) {
 445     return kvtest_remove(*this, key);
 446 }
 447
 448 template <typename T>
 449 String kvtest_client<T>::make_message(lcdf::StringAccum &sa) const {
 450     const char *begin = sa.begin();
 451     while (begin != sa.end() && isspace((unsigned char) *begin))
 452         ++begin;
 453     String s = String(begin, sa.end());
 454     if (!s.empty() && s.back() != '\n')
 455         s += '\n';
 456     return s;
 457 }
 458
 459 template <typename T>
 460 void kvtest_client<T>::notice(const char *fmt, ...) {
 461     va_list val;
 462     va_start(val, fmt);
 463     String m = make_message(lcdf::StringAccum().vsnprintf(500, fmt, val));
 464     va_end(val);
 465     if (m && !quiet)
 466         fprintf(stderr, "%d: %s", ti_->index(), m.c_str());
 467 }
 468
 469 template <typename T>
 470 void kvtest_client<T>::fail(const char *fmt, ...) {
 471     static nodeversion failing_lock(false);
 472     static nodeversion fail_message_lock(false);
 473     static String fail_message;
 474
 475     va_list val;
 476     va_start(val, fmt);
 477     String m = make_message(lcdf::StringAccum().vsnprintf(500, fmt, val));
 478     va_end(val);
 479     if (!m)
 480         m = "unknown failure";
 481
 482     fail_message_lock.lock();
 483     if (fail_message != m) {
 484         fail_message = m;
 485         fprintf(stderr, "%d: %s", ti_->index(), m.c_str());
 486     }
 487     fail_message_lock.unlock();
 488
 489     failing_lock.lock();
 490     fprintf(stdout, "%d: %s", ti_->index(), m.c_str());
 491     kvtest_print(*table_, stdout, 0, ti_);
 492
 493     always_assert(0);
 494 }
 495
 496
 497 static const char *current_test_name;
 498 static int current_trial;
 499 static FILE *test_output_file;
 500 static pthread_mutex_t subtest_mutex;
 501 static pthread_cond_t subtest_cond;
 502
 503 #define TESTRUNNER_CLIENT_TYPE kvtest_client<Masstree::default_table>&
 504 #include "testrunner.hh"
 505
 506 MAKE_TESTRUNNER(rw1, kvtest_rw1(client));
 507 // MAKE_TESTRUNNER(palma, kvtest_palma(client));
 508 // MAKE_TESTRUNNER(palmb, kvtest_palmb(client));
 509 MAKE_TESTRUNNER(rw1fixed, kvtest_rw1fixed(client));
 510 MAKE_TESTRUNNER(rw1long, kvtest_rw1long(client));
 511 MAKE_TESTRUNNER(rw1puts, kvtest_rw1puts(client));
 512 MAKE_TESTRUNNER(rw2, kvtest_rw2(client));
 513 MAKE_TESTRUNNER(rw2fixed, kvtest_rw2fixed(client));
 514 MAKE_TESTRUNNER(rw2g90, kvtest_rw2g90(client));
 515 MAKE_TESTRUNNER(rw2fixedg90, kvtest_rw2fixedg90(client));
 516 MAKE_TESTRUNNER(rw2g98, kvtest_rw2g98(client));
 517 MAKE_TESTRUNNER(rw2fixedg98, kvtest_rw2fixedg98(client));
 518 MAKE_TESTRUNNER(rw3, kvtest_rw3(client));
 519 MAKE_TESTRUNNER(rw4, kvtest_rw4(client));
 520 MAKE_TESTRUNNER(rw4fixed, kvtest_rw4fixed(client));
 521 MAKE_TESTRUNNER(wd1, kvtest_wd1(10000000, 1, client));
 522 MAKE_TESTRUNNER(wd1m1, kvtest_wd1(100000000, 1, client));
 523 MAKE_TESTRUNNER(wd1m2, kvtest_wd1(1000000000, 4, client));
 524 MAKE_TESTRUNNER(same, kvtest_same(client));
 525 MAKE_TESTRUNNER(rwsmall24, kvtest_rwsmall24(client));
 526 MAKE_TESTRUNNER(rwsep24, kvtest_rwsep24(client));
 527 MAKE_TESTRUNNER(wscale, kvtest_wscale(client));
 528 MAKE_TESTRUNNER(ruscale_init, kvtest_ruscale_init(client));
 529 MAKE_TESTRUNNER(rscale, if (client.ti_->index() < ::rscale_ncores) kvtest_rscale(client));
 530 MAKE_TESTRUNNER(uscale, kvtest_uscale(client));
 531 MAKE_TESTRUNNER(bdb, kvtest_bdb(client));
 532 MAKE_TESTRUNNER(wcol1, kvtest_wcol1at(client, client.id() % 24, kvtest_first_seed + client.id() % 48, 5000000));
 533 MAKE_TESTRUNNER(rcol1, kvtest_rcol1at(client, client.id() % 24, kvtest_first_seed + client.id() % 48, 5000000));
 534 MAKE_TESTRUNNER(wcol1o1, kvtest_wcol1at(client, (client.id() + 1) % 24, kvtest_first_seed + client.id() % 48, 5000000));
 535 MAKE_TESTRUNNER(rcol1o1, kvtest_rcol1at(client, (client.id() + 1) % 24, kvtest_first_seed + client.id() % 48, 5000000));
 536 MAKE_TESTRUNNER(wcol1o2, kvtest_wcol1at(client, (client.id() + 2) % 24, kvtest_first_seed + client.id() % 48, 5000000));
 537 MAKE_TESTRUNNER(rcol1o2, kvtest_rcol1at(client, (client.id() + 2) % 24, kvtest_first_seed + client.id() % 48, 5000000));
 538 MAKE_TESTRUNNER(scan1, kvtest_scan1(client, 0));
 539 MAKE_TESTRUNNER(scan1q80, kvtest_scan1(client, 0.8));
 540 MAKE_TESTRUNNER(rscan1, kvtest_rscan1(client, 0));
 541 MAKE_TESTRUNNER(rscan1q80, kvtest_rscan1(client, 0.8));
 542 MAKE_TESTRUNNER(splitremove1, kvtest_splitremove1(client));
 543 MAKE_TESTRUNNER(url, kvtest_url(client));
 544
 545
 546 enum {
 547     test_thread_initialize = 1,
 548     test_thread_destroy = 2,
 549     test_thread_stats = 3
 550 };
 551
 552 template <typename T>
 553 struct test_thread {
 554     test_thread(threadinfo* ti) {
 555         client_.set_table(table_, ti);
 556         client_.ti_->rcu_start();
 557     }
 558     ~test_thread() {
 559         client_.ti_->rcu_stop();
 560     }
 561     static void setup(threadinfo* ti, int action) {
 562         if (action == test_thread_initialize) {
 563             assert(!table_);
 564             table_ = new T;
 565             table_->initialize(*ti);
 566         } else if (action == test_thread_destroy) {
 567             assert(table_);
 568             delete table_;
 569             table_ = 0;
 570         } else if (action == test_thread_stats) {
 571             assert(table_);
 572             table_->stats(test_output_file);
 573         }
 574     }
 575     static void* go(threadinfo* ti) {
 576         assert(table_);
 577 #if __linux__
 578         if (pinthreads) {
 579             cpu_set_t cs;
 580             CPU_ZERO(&cs);
 581             CPU_SET(cores[ti->index()], &cs);
 582             int r = sched_setaffinity(0, sizeof(cs), &cs);
 583             always_assert(r == 0);
 584         }
 585 #else
 586         always_assert(!pinthreads && "pinthreads not supported\n");
 587 #endif
 588
 589         test_thread<T> tt(ti);
 590         if (fetch_and_add(&active_threads_, 1) == 0)
 591             tt.ready_timeouts();
 592         String test = ::current_test_name;
 593         int subtestno = 0;
 594         for (int pos = 0; pos < test.length(); ) {
 595             int comma = test.find_left(',', pos);
 596             comma = (comma < 0 ? test.length() : comma);
 597             String subtest = test.substr(pos, comma - pos), tname;
 598             testrunner* tr = testrunner::find(subtest);
 599             tname = (subtest == test ? subtest : test + String("@") + String(subtestno));
 600             tt.client_.reset(tname, ::current_trial);
 601             if (tr)
 602                 tr->run(tt.client_);
 603             else
 604                 tt.client_.fail("unknown test %s", subtest.c_str());
 605             if (comma == test.length())
 606                 break;
 607             pthread_mutex_lock(&subtest_mutex);
 608             if (fetch_and_add(&active_threads_, -1) == 1) {
 609                 pthread_cond_broadcast(&subtest_cond);
 610                 tt.ready_timeouts();
 611             } else
 612                 pthread_cond_wait(&subtest_cond, &subtest_mutex);
 613             fprintf(test_output_file, "%s\n", tt.client_.report_.unparse().c_str());
 614             pthread_mutex_unlock(&subtest_mutex);
 615             fetch_and_add(&active_threads_, 1);
 616             pos = comma + 1;
 617             ++subtestno;
 618         }
 619         int at = fetch_and_add(&active_threads_, -1);
 620         if (at == 1 && print_table)
 621             kvtest_print(*table_, stdout, 0, tt.client_.ti_);
 622         if (at == 1 && json_stats) {
 623             Json j;
 624             kvtest_json_stats(*table_, j, *tt.client_.ti_);
 625             if (j) {
 626                 fprintf(stderr, "%s\n", j.unparse(Json::indent_depth(1).tab_width(2).newline_terminator(true)).c_str());
 627                 tt.client_.report_.merge(j);
 628             }
 629         }
 630         fprintf(test_output_file, "%s\n", tt.client_.report_.unparse().c_str());
 631         return 0;
 632     }
 633     void ready_timeouts() {
 634         for (size_t i = 0; i < arraysize(timeout); ++i)
 635             timeout[i] = false;
 636         if (!lazy_timer && duration[0])
 637             xalarm(duration[0]);
 638     }
 639     static T *table_;
 640     static unsigned active_threads_;
 641     kvtest_client<T> client_;
 642 };
 643 template <typename T> T *test_thread<T>::table_;
 644 template <typename T> unsigned test_thread<T>::active_threads_;
 645
 646 typedef test_thread<Masstree::default_table> masstree_test_thread;
 647
 648 static struct {
 649     const char *treetype;
 650     void* (*go_func)(threadinfo*);
 651     void (*setup_func)(threadinfo*, int);
 652 } test_thread_map[] = {
 653     { "masstree", masstree_test_thread::go, masstree_test_thread::setup },
 654     { "mass", masstree_test_thread::go, masstree_test_thread::setup },
 655     { "mbtree", masstree_test_thread::go, masstree_test_thread::setup },
 656     { "mb", masstree_test_thread::go, masstree_test_thread::setup },
 657     { "m", masstree_test_thread::go, masstree_test_thread::setup }
 658 };
 659
 660
 661 void runtest(int nthreads, void* (*func)(threadinfo*)) {
 662     std::vector<threadinfo *> tis;
 663     for (int i = 0; i < nthreads; ++i)
 664         tis.push_back(threadinfo::make(threadinfo::TI_PROCESS, i));
 665     signal(SIGALRM, test_timeout);
 666     for (int i = 0; i < nthreads; ++i) {
 667         int r = tis[i]->run(func);
 668         always_assert(r == 0);
 669     }
 670     for (int i = 0; i < nthreads; ++i)
 671         pthread_join(tis[i]->threadid(), 0);
 672 }
 673
 674
 675 static const char * const kvstats_name[] = {
 676     "ops_per_sec", "puts_per_sec", "gets_per_sec", "scans_per_sec"
 677 };
 678
 679 static Json experiment_stats;
 680
 681 void *stat_collector(void *arg) {
 682     int p = (int) (intptr_t) arg;
 683     FILE *f = fdopen(p, "r");
 684     char buf[8192];
 685     while (fgets(buf, sizeof(buf), f)) {
 686         Json result = Json::parse(buf);
 687         if (result && result["table"] && result["test"]) {
 688             String key = result["test"].to_s() + "/" + result["table"].to_s()
 689                 + "/" + result["trial"].to_s();
 690             Json &thisex = experiment_stats.get_insert(key);
 691             thisex[result["thread"].to_i()] = result;
 692         } else
 693             fprintf(stderr, "%s\n", buf);
 694     }
 695     fclose(f);
 696     return 0;
 697 }
 698
 699
 700 /* main loop */
 701
 702 enum { clp_val_normalize = Clp_ValFirstUser, clp_val_suffixdouble };
 703 enum { opt_pin = 1, opt_port, opt_duration,
 704        opt_test, opt_test_name, opt_threads, opt_trials, opt_quiet, opt_print,
 705        opt_normalize, opt_limit, opt_notebook, opt_compare, opt_no_run,
 706        opt_lazy_timer, opt_gid, opt_tree_stats, opt_rscale_ncores, opt_cores,
 707        opt_stats, opt_help };
 708 static const Clp_Option options[] = {
 709     { "pin", 'p', opt_pin, 0, Clp_Negate },
 710     { "port", 0, opt_port, Clp_ValInt, 0 },
 711     { "duration", 'd', opt_duration, Clp_ValDouble, 0 },
 712     { "lazy-timer", 0, opt_lazy_timer, 0, 0 },
 713     { "limit", 'l', opt_limit, clp_val_suffixdouble, 0 },
 714     { "normalize", 0, opt_normalize, clp_val_normalize, Clp_Negate },
 715     { "test", 0, opt_test, Clp_ValString, 0 },
 716     { "rscale_ncores", 'r', opt_rscale_ncores, Clp_ValInt, 0 },
 717     { "test-rw1", 0, opt_test_name, 0, 0 },
 718     { "test-rw2", 0, opt_test_name, 0, 0 },
 719     { "test-rw3", 0, opt_test_name, 0, 0 },
 720     { "test-rw4", 0, opt_test_name, 0, 0 },
 721     { "test-rd1", 0, opt_test_name, 0, 0 },
 722     { "threads", 'j', opt_threads, Clp_ValInt, 0 },
 723     { "trials", 'T', opt_trials, Clp_ValInt, 0 },
 724     { "quiet", 'q', opt_quiet, 0, Clp_Negate },
 725     { "print", 0, opt_print, 0, Clp_Negate },
 726     { "notebook", 'b', opt_notebook, Clp_ValString, Clp_Negate },
 727     { "gid", 'g', opt_gid, Clp_ValString, 0 },
 728     { "tree-stats", 0, opt_tree_stats, 0, 0 },
 729     { "stats", 0, opt_stats, 0, 0 },
 730     { "compare", 'c', opt_compare, Clp_ValString, 0 },
 731     { "cores", 0, opt_cores, Clp_ValString, 0 },
 732     { "no-run", 'n', opt_no_run, 0, 0 },
 733     { "help", 0, opt_help, 0, 0 }
 734 };
 735
 736 static void help() {
 737     printf("Masstree-beta mttest\n\
 738 Usage: mttest [-jTHREADS] [OPTIONS] [PARAM=VALUE...] TEST...\n\
 739        mttest -n -c TESTNAME...\n\
 740 \n\
 741 Options:\n\
 742   -j, --threads=THREADS    Run with THREADS threads (default %d).\n\
 743   -p, --pin                Pin each thread to its own core.\n\
 744   -T, --trials=TRIALS      Run each test TRIALS times.\n\
 745   -q, --quiet              Do not generate verbose and Gnuplot output.\n\
 746   -l, --limit=LIMIT        Limit relevant tests to LIMIT operations.\n\
 747   -d, --duration=TIME      Limit relevant tests to TIME seconds.\n\
 748   -b, --notebook=FILE      Record JSON results in FILE (notebook-mttest.json).\n\
 749       --no-notebook        Do not record JSON results.\n\
 750 \n\
 751   -n, --no-run             Do not run new tests.\n\
 752   -c, --compare=EXPERIMENT Generated plot compares to EXPERIMENT.\n\
 753 \n\
 754 Known TESTs:\n",
 755            (int) sysconf(_SC_NPROCESSORS_ONLN));
 756     testrunner_base::print_names(stdout, 5);
 757     printf("Or say TEST1,TEST2,... to run several tests in sequence\n\
 758 on the same tree.\n");
 759     exit(0);
 760 }
 761
 762 static void run_one_test(int trial, const char *treetype, const char *test,
 763                          const int *collectorpipe, int nruns);
 764 enum { normtype_none, normtype_pertest, normtype_firsttest };
 765 static void print_gnuplot(FILE *f, const char * const *types_begin, const char * const *types_end, std::vector<String> &comparisons, int normalizetype);
 766 static void update_labnotebook(String notebook);
 767
 768 #if HAVE_EXECINFO_H
 769 static const int abortable_signals[] = {
 770     SIGSEGV, SIGBUS, SIGILL, SIGABRT, SIGFPE
 771 };
 772
 773 static void abortable_signal_handler(int) {
 774     // reset signals so if a signal recurs, we exit
 775     for (const int* it = abortable_signals;
 776          it != abortable_signals + arraysize(abortable_signals); ++it)
 777         signal(*it, SIG_DFL);
 778     // dump backtrace to standard error
 779     void* return_addrs[50];
 780     int n = backtrace(return_addrs, arraysize(return_addrs));
 781     backtrace_symbols_fd(return_addrs, n, STDERR_FILENO);
 782     // re-abort
 783     abort();
 784 }
 785 #endif
 786
 787 int
 788 main(int argc, char *argv[])
 789 {
 790     threadcounter_names[(int) tc_root_retry] = "root_retry";
 791     threadcounter_names[(int) tc_internode_retry] = "internode_retry";
 792     threadcounter_names[(int) tc_leaf_retry] = "leaf_retry";
 793     threadcounter_names[(int) tc_leaf_walk] = "leaf_walk";
 794     threadcounter_names[(int) tc_stable_internode_insert] = "stable_internode_insert";
 795     threadcounter_names[(int) tc_stable_internode_split] = "stable_internode_split";
 796     threadcounter_names[(int) tc_stable_leaf_insert] = "stable_leaf_insert";
 797     threadcounter_names[(int) tc_stable_leaf_split] = "stable_leaf_split";
 798     threadcounter_names[(int) tc_internode_lock] = "internode_lock_retry";
 799     threadcounter_names[(int) tc_leaf_lock] = "leaf_lock_retry";
 800
 801     int ret, ntrials = 1, normtype = normtype_pertest, firstcore = -1, corestride = 1;
 802     std::vector<const char *> tests, treetypes;
 803     std::vector<String> comparisons;
 804     const char *notebook = "notebook-mttest.json";
 805     tcpthreads = udpthreads = sysconf(_SC_NPROCESSORS_ONLN);
 806
 807     Clp_Parser *clp = Clp_NewParser(argc, argv, (int) arraysize(options), options);
 808     Clp_AddStringListType(clp, clp_val_normalize, 0,
 809                           "none", (int) normtype_none,
 810                           "pertest", (int) normtype_pertest,
 811                           "test", (int) normtype_pertest,
 812                           "firsttest", (int) normtype_firsttest,
 813                           (const char *) 0);
 814     Clp_AddType(clp, clp_val_suffixdouble, Clp_DisallowOptions, clp_parse_suffixdouble, 0);
 815     int opt;
 816     while ((opt = Clp_Next(clp)) != Clp_Done) {
 817         switch (opt) {
 818         case opt_pin:
 819             pinthreads = !clp->negated;
 820             break;
 821         case opt_threads:
 822             tcpthreads = udpthreads = clp->val.i;
 823             break;
 824         case opt_trials:
 825             ntrials = clp->val.i;
 826             break;
 827         case opt_quiet:
 828             quiet = !clp->negated;
 829             break;
 830         case opt_print:
 831             print_table = !clp->negated;
 832             break;
 833         case opt_rscale_ncores:
 834             rscale_ncores = clp->val.i;
 835             break;
 836         case opt_port:
 837             port = clp->val.i;
 838             break;
 839         case opt_duration:
 840             duration[0] = clp->val.d;
 841             break;
 842         case opt_lazy_timer:
 843             lazy_timer = true;
 844             break;
 845         case opt_limit:
 846             test_limit = uint64_t(clp->val.d);
 847             break;
 848         case opt_test:
 849             tests.push_back(clp->vstr);
 850             break;
 851         case opt_test_name:
 852             tests.push_back(clp->option->long_name + 5);
 853             break;
 854         case opt_normalize:
 855             normtype = clp->negated ? normtype_none : clp->val.i;
 856             break;
 857         case opt_gid:
 858             gid = clp->vstr;
 859             break;
 860         case opt_tree_stats:
 861             tree_stats = true;
 862             break;
 863         case opt_stats:
 864             json_stats = true;
 865             break;
 866         case opt_notebook:
 867             if (clp->negated)
 868                 notebook = 0;
 869             else if (clp->have_val)
 870                 notebook = clp->vstr;
 871             else
 872                 notebook = "notebook-mttest.json";
 873             break;
 874         case opt_compare:
 875             comparisons.push_back(clp->vstr);
 876             break;
 877         case opt_no_run:
 878             ntrials = 0;
 879             break;
 880       case opt_cores:
 881           if (firstcore >= 0 || cores.size() > 0) {
 882               Clp_OptionError(clp, "%<%O%> already given");
 883               exit(EXIT_FAILURE);
 884           } else {
 885               const char *plus = strchr(clp->vstr, '+');
 886               Json ij = Json::parse(clp->vstr),
 887                   aj = Json::parse(String("[") + String(clp->vstr) + String("]")),
 888                   pj1 = Json::parse(plus ? String(clp->vstr, plus) : "x"),
 889                   pj2 = Json::parse(plus ? String(plus + 1) : "x");
 890               for (int i = 0; aj && i < aj.size(); ++i)
 891                   if (!aj[i].is_int() || aj[i].to_i() < 0)
 892                       aj = Json();
 893               if (ij && ij.is_int() && ij.to_i() >= 0)
 894                   firstcore = ij.to_i(), corestride = 1;
 895               else if (pj1 && pj2 && pj1.is_int() && pj1.to_i() >= 0 && pj2.is_int())
 896                   firstcore = pj1.to_i(), corestride = pj2.to_i();
 897               else if (aj) {
 898                   for (int i = 0; i < aj.size(); ++i)
 899                       cores.push_back(aj[i].to_i());
 900               } else {
 901                   Clp_OptionError(clp, "bad %<%O%>, expected %<CORE1%>, %<CORE1+STRIDE%>, or %<CORE1,CORE2,...%>");
 902                   exit(EXIT_FAILURE);
 903               }
 904           }
 905           break;
 906         case opt_help:
 907             help();
 908             break;
 909         case Clp_NotOption:
 910             // check for parameter setting
 911             if (const char* eqchr = strchr(clp->vstr, '=')) {
 912                 Json& param = test_param[String(clp->vstr, eqchr)];
 913                 const char* end_vstr = clp->vstr + strlen(clp->vstr);
 914                 if (param.assign_parse(eqchr + 1, end_vstr))
 915                     /* OK, param was valid JSON */;
 916                 else if (eqchr[1] != 0)
 917                     param = String(eqchr + 1, end_vstr);
 918                 else
 919                     param = Json();
 920             } else {
 921                 // otherwise, tree or test
 922                 bool is_treetype = false;
 923                 for (int i = 0; i < (int) arraysize(test_thread_map) && !is_treetype; ++i)
 924                     is_treetype = (strcmp(test_thread_map[i].treetype, clp->vstr) == 0);
 925                 (is_treetype ? treetypes.push_back(clp->vstr) : tests.push_back(clp->vstr));
 926             }
 927             break;
 928         default:
 929             fprintf(stderr, "Usage: mttest [-jN] TESTS...\n\
 930 Try 'mttest --help' for options.\n");
 931             exit(EXIT_FAILURE);
 932         }
 933     }
 934     Clp_DeleteParser(clp);
 935     if (firstcore < 0)
 936         firstcore = cores.size() ? cores.back() + 1 : 0;
 937     for (; (int) cores.size() < udpthreads; firstcore += corestride)
 938         cores.push_back(firstcore);
 939
 940 #if PMC_ENABLED
 941     always_assert(pinthreads && "Using performance counter requires pinning threads to cores!");
 942 #endif
 943 #if MEMSTATS && HAVE_NUMA_H && HAVE_LIBNUMA
 944     if (numa_available() != -1)
 945         for (int i = 0; i <= numa_max_node(); i++) {
 946             numa.push_back(mttest_numainfo());
 947             numa.back().size = numa_node_size64(i, &numa.back().free);
 948         }
 949 #endif
 950 #if HAVE_EXECINFO_H
 951     for (const int* it = abortable_signals;
 952          it != abortable_signals + arraysize(abortable_signals); ++it)
 953         signal(*it, abortable_signal_handler);
 954 #endif
 955
 956     if (treetypes.empty())
 957         treetypes.push_back("m");
 958     if (tests.empty())
 959         tests.push_back("rw1");
 960
 961     // arrange for a per-thread threadinfo pointer
 962     ret = pthread_key_create(&threadinfo::key, 0);
 963     always_assert(ret == 0);
 964     pthread_mutex_init(&subtest_mutex, 0);
 965     pthread_cond_init(&subtest_cond, 0);
 966
 967     // pipe for them to write back to us
 968     int p[2];
 969     ret = pipe(p);
 970     always_assert(ret == 0);
 971     test_output_file = fdopen(p[1], "w");
 972
 973     pthread_t collector;
 974     ret = pthread_create(&collector, 0, stat_collector, (void *) (intptr_t) p[0]);
 975     always_assert(ret == 0);
 976     initial_timestamp = timestamp();
 977
 978     // run tests
 979     int nruns = ntrials * (int) tests.size() * (int) treetypes.size();
 980     std::vector<int> runlist(nruns, 0);
 981     for (int i = 0; i < nruns; ++i)
 982         runlist[i] = i;
 983
 984     for (int counter = 0; counter < nruns; ++counter) {
 985         int x = random() % runlist.size();
 986         int run = runlist[x];
 987         runlist[x] = runlist.back();
 988         runlist.pop_back();
 989
 990         int trial = run % ntrials;
 991         run /= ntrials;
 992         int t = run % tests.size();
 993         run /= tests.size();
 994         int tt = run;
 995
 996         fprintf(stderr, "%d/%u %s/%s%s", counter + 1, (int) (ntrials * tests.size() * treetypes.size()),
 997                 tests[t], treetypes[tt], quiet ? "      " : "\n");
 998
 999         run_one_test(trial, treetypes[tt], tests[t], p, nruns);
1000         struct timeval delay;
1001         delay.tv_sec = 0;
1002         delay.tv_usec = 250000;
1003         (void) select(0, 0, 0, 0, &delay);
1004
1005         if (quiet)
1006             fprintf(stderr, "\r%60s\r", "");
1007     }
1008
1009     fclose(test_output_file);
1010     pthread_join(collector, 0);
1011
1012     // update lab notebook
1013     if (notebook)
1014         update_labnotebook(notebook);
1015
1016     // print Gnuplot
1017     if (ntrials != 0)
1018         comparisons.insert(comparisons.begin(), "");
1019     if (!isatty(STDOUT_FILENO))
1020         print_gnuplot(stdout, kvstats_name, kvstats_name + arraysize(kvstats_name),
1021                       comparisons, normtype);
1022
1023     return 0;
1024 }
1025
1026 static void run_one_test_body(int trial, const char *treetype, const char *test) {
1027     threadinfo *main_ti = threadinfo::make(threadinfo::TI_MAIN, -1);
1028     main_ti->run();
1029     globalepoch = timestamp() >> 16;
1030     for (int i = 0; i < (int) arraysize(test_thread_map); ++i)
1031         if (strcmp(test_thread_map[i].treetype, treetype) == 0) {
1032             current_test_name = test;
1033             current_trial = trial;
1034             test_thread_map[i].setup_func(main_ti, test_thread_initialize);
1035             runtest(tcpthreads, test_thread_map[i].go_func);
1036             if (tree_stats)
1037                 test_thread_map[i].setup_func(main_ti, test_thread_stats);
1038             test_thread_map[i].setup_func(main_ti, test_thread_destroy);
1039             break;
1040         }
1041 }
1042
1043 static void run_one_test(int trial, const char *treetype, const char *test,
1044                          const int *collectorpipe, int nruns) {
1045     if (nruns == 1)
1046         run_one_test_body(trial, treetype, test);
1047     else {
1048         pid_t c = fork();
1049         if (c == 0) {
1050             close(collectorpipe[0]);
1051             run_one_test_body(trial, treetype, test);
1052             exit(0);
1053         } else
1054             while (waitpid(c, 0, 0) == -1 && errno == EINTR)
1055                 /* loop */;
1056     }
1057 }
1058
1059 static double level(const std::vector<double> &v, double frac) {
1060     frac *= v.size() - 1;
1061     int base = (int) frac;
1062     if (base == frac)
1063         return v[base];
1064     else
1065         return v[base] * (1 - (frac - base)) + v[base + 1] * (frac - base);
1066 }
1067
1068 static String experiment_test_table_trial(const String &key) {
1069     const char *l = key.begin(), *r = key.end();
1070     if (l + 2 < r && l[0] == 'x' && isdigit((unsigned char) l[1])) {
1071         for (const char *s = l; s != r; ++s)
1072             if (*s == '/') {
1073                 l = s + 1;
1074                 break;
1075             }
1076     }
1077     return key.substring(l, r);
1078 }
1079
1080 static String experiment_run_test_table(const String &key) {
1081     const char *l = key.begin(), *r = key.end();
1082     for (const char *s = r; s != l; --s)
1083         if (s[-1] == '/') {
1084             r = s - 1;
1085             break;
1086         } else if (!isdigit((unsigned char) s[-1]))
1087             break;
1088     return key.substring(l, r);
1089 }
1090
1091 static String experiment_test_table(const String &key) {
1092     return experiment_run_test_table(experiment_test_table_trial(key));
1093 }
1094
1095 namespace {
1096 struct gnuplot_info {
1097     static constexpr double trialdelta = 0.015, treetypedelta = 0.04,
1098         testdelta = 0.08, typedelta = 0.2;
1099     double pos;
1100     double nextdelta;
1101     double normalization;
1102     String last_test;
1103     int normalizetype;
1104
1105     std::vector<lcdf::StringAccum> candlesticks;
1106     std::vector<lcdf::StringAccum> medians;
1107     lcdf::StringAccum xtics;
1108
1109     gnuplot_info(int nt)
1110         : pos(1 - trialdelta), nextdelta(trialdelta), normalization(-1),
1111           normalizetype(nt) {
1112     }
1113     void one(const String &xname, int ti, const String &datatype_name);
1114     void print(FILE *f, const char * const *types_begin);
1115 };
1116 constexpr double gnuplot_info::trialdelta, gnuplot_info::treetypedelta, gnuplot_info::testdelta, gnuplot_info::typedelta;
1117
1118 void gnuplot_info::one(const String &xname, int ti, const String &datatype_name)
1119 {
1120     String current_test = experiment_test_table(xname);
1121     if (current_test != last_test) {
1122         last_test = current_test;
1123         if (normalizetype == normtype_pertest)
1124             normalization = -1;
1125         if (nextdelta == treetypedelta)
1126             nextdelta = testdelta;
1127     }
1128     double beginpos = pos, firstpos = pos + nextdelta;
1129
1130     std::vector<int> trials;
1131     for (Json::object_iterator it = experiment_stats.obegin();
1132          it != experiment_stats.oend(); ++it) {
1133         String key = it.key();
1134         if (experiment_run_test_table(key) == xname)
1135             trials.push_back(strtol(key.c_str() + xname.length() + 1, 0, 0));
1136     }
1137     std::sort(trials.begin(), trials.end());
1138
1139     for (std::vector<int>::iterator tit = trials.begin();
1140          tit != trials.end(); ++tit) {
1141         Json &this_trial = experiment_stats[xname + "/" + String(*tit)];
1142         std::vector<double> values;
1143         for (int jn = 0; jn < this_trial.size(); ++jn)
1144             if (this_trial[jn].get(datatype_name).is_number())
1145                 values.push_back(this_trial[jn].get(datatype_name).to_d());
1146         if (values.size()) {
1147             pos += nextdelta;
1148             std::sort(values.begin(), values.end());
1149             if (normalization < 0)
1150                 normalization = normalizetype == normtype_none ? 1 : level(values, 0.5);
1151             if (int(candlesticks.size()) <= ti) {
1152                 candlesticks.resize(ti + 1);
1153                 medians.resize(ti + 1);
1154             }
1155             candlesticks[ti] << pos << " " << level(values, 0)
1156                              << " " << level(values, 0.25)
1157                              << " " << level(values, 0.75)
1158                              << " " << level(values, 1)
1159                              << " " << normalization << "\n";
1160             medians[ti] << pos << " " << level(values, 0.5) << " " << normalization << "\n";
1161             nextdelta = trialdelta;
1162         }
1163     }
1164
1165     if (pos > beginpos) {
1166         double middle = (firstpos + pos) / 2;
1167         xtics << (xtics ? ", " : "") << "\"" << xname << "\" " << middle;
1168         nextdelta = treetypedelta;
1169     }
1170 }
1171
1172 void gnuplot_info::print(FILE *f, const char * const *types_begin) {
1173     std::vector<int> linetypes(medians.size(), 0);
1174     int next_linetype = 1;
1175     for (int i = 0; i < int(medians.size()); ++i)
1176         if (medians[i])
1177             linetypes[i] = next_linetype++;
1178     struct utsname name;
1179     fprintf(f, "set title \"%s (%d cores)\"\n",
1180             (uname(&name) == 0 ? name.nodename : "unknown"),
1181             udpthreads);
1182     fprintf(f, "set terminal png\n");
1183     fprintf(f, "set xrange [%g:%g]\n", 1 - treetypedelta, pos + treetypedelta);
1184     fprintf(f, "set xtics rotate by 45 right (%s) font \"Verdana,9\"\n", xtics.c_str());
1185     fprintf(f, "set key top left Left reverse\n");
1186     if (normalizetype == normtype_none)
1187         fprintf(f, "set ylabel \"count\"\n");
1188     else if (normalizetype == normtype_pertest)
1189         fprintf(f, "set ylabel \"count, normalized per test\"\n");
1190     else
1191         fprintf(f, "set ylabel \"normalized count (1=%f)\"\n", normalization);
1192     const char *sep = "plot ";
1193     for (int i = 0; i < int(medians.size()); ++i)
1194         if (medians[i]) {
1195             fprintf(f, "%s '-' using 1:($3/$6):($2/$6):($5/$6):($4/$6) with candlesticks lt %d title '%s', \\\n",
1196                     sep, linetypes[i], types_begin[i]);
1197             fprintf(f, " '-' using 1:($2/$3):($2/$3):($2/$3):($2/$3) with candlesticks lt %d notitle", linetypes[i]);
1198             sep = ", \\\n";
1199         }
1200     fprintf(f, "\n");
1201     for (int i = 0; i < int(medians.size()); ++i)
1202         if (medians[i]) {
1203             fwrite(candlesticks[i].begin(), 1, candlesticks[i].length(), f);
1204             fprintf(f, "e\n");
1205             fwrite(medians[i].begin(), 1, medians[i].length(), f);
1206             fprintf(f, "e\n");
1207         }
1208 }
1209
1210 }
1211
1212 static void print_gnuplot(FILE *f, const char * const *types_begin, const char * const *types_end,
1213                           std::vector<String> &comparisons, int normalizetype) {
1214     for (std::vector<String>::iterator cit = comparisons.begin();
1215          cit != comparisons.end(); ++cit) {
1216         if (!*cit)
1217             *cit = "[^x]*";
1218         else if (cit->length() >= 2 && (*cit)[0] == 'x' && isdigit((unsigned char) (*cit)[1]))
1219             *cit += String(cit->find_left('/') < 0 ? "/*" : "*");
1220         else
1221             *cit = String("x*") + *cit + String("*");
1222     }
1223
1224     std::vector<String> all_versions, all_experiments;
1225     for (Json::object_iterator it = experiment_stats.obegin();
1226          it != experiment_stats.oend(); ++it)
1227         for (std::vector<String>::const_iterator cit = comparisons.begin();
1228              cit != comparisons.end(); ++cit)
1229             if (it.key().glob_match(*cit)) {
1230                 all_experiments.push_back(experiment_run_test_table(it.key()));
1231                 all_versions.push_back(experiment_test_table(it.key()));
1232                 break;
1233             }
1234     std::sort(all_experiments.begin(), all_experiments.end());
1235     all_experiments.erase(std::unique(all_experiments.begin(), all_experiments.end()),
1236                           all_experiments.end());
1237     std::sort(all_versions.begin(), all_versions.end());
1238     all_versions.erase(std::unique(all_versions.begin(), all_versions.end()),
1239                        all_versions.end());
1240
1241     int ntypes = (int) (types_end - types_begin);
1242     gnuplot_info gpinfo(normalizetype);
1243
1244     for (int ti = 0; ti < ntypes; ++ti) {
1245         double typepos = gpinfo.pos;
1246         for (std::vector<String>::iterator vit = all_versions.begin();
1247              vit != all_versions.end(); ++vit) {
1248             for (std::vector<String>::iterator xit = all_experiments.begin();
1249                  xit != all_experiments.end(); ++xit)
1250                 if (experiment_test_table(*xit) == *vit)
1251                     gpinfo.one(*xit, ti, types_begin[ti]);
1252         }
1253         if (gpinfo.pos > typepos)
1254             gpinfo.nextdelta = gpinfo.typedelta;
1255         gpinfo.last_test = "";
1256     }
1257
1258     if (gpinfo.xtics)
1259         gpinfo.print(f, types_begin);
1260 }
1261
1262 static String
1263 read_file(FILE *f, const char *name)
1264 {
1265     lcdf::StringAccum sa;
1266     while (1) {
1267         size_t x = fread(sa.reserve(4096), 1, 4096, f);
1268         if (x != 0)
1269             sa.adjust_length(x);
1270         else if (ferror(f)) {
1271             fprintf(stderr, "%s: %s\n", name, strerror(errno));
1272             return String::make_stable("???", 3);
1273         } else
1274             return sa.take_string();
1275     }
1276 }
1277
1278 static void
1279 update_labnotebook(String notebook)
1280 {
1281     FILE *f = (notebook == "-" ? stdin : fopen(notebook.c_str(), "r"));
1282     String previous_text = (f ? read_file(f, notebook.c_str()) : String());
1283     if (previous_text.out_of_memory())
1284         return;
1285     if (f && f != stdin)
1286         fclose(f);
1287
1288     Json nb = Json::parse(previous_text);
1289     if (previous_text && (!nb.is_object() || !nb["experiments"])) {
1290         fprintf(stderr, "%s: unexpected contents, not writing new data\n", notebook.c_str());
1291         return;
1292     }
1293
1294     if (!nb)
1295         nb = Json::make_object();
1296     if (!nb.get("experiments"))
1297         nb.set("experiments", Json::make_object());
1298     if (!nb.get("data"))
1299         nb.set("data", Json::make_object());
1300
1301     Json old_data = nb["data"];
1302     if (!experiment_stats) {
1303         experiment_stats = old_data;
1304         return;
1305     }
1306
1307     Json xjson;
1308
1309     FILE *git_info_p = popen("git rev-parse HEAD | tr -d '\n'; git --no-pager diff --exit-code --shortstat HEAD >/dev/null 2>&1 || echo M", "r");
1310     String git_info = read_file(git_info_p, "<git output>");
1311     pclose(git_info_p);
1312     if (git_info)
1313         xjson.set("git-revision", git_info.trim());
1314
1315     time_t now = time(0);
1316     xjson.set("time", String(ctime(&now)).trim());
1317     if (gid)
1318         xjson.set("gid", String(gid));
1319
1320     struct utsname name;
1321     if (uname(&name) == 0)
1322         xjson.set("machine", name.nodename);
1323
1324     xjson.set("cores", udpthreads);
1325
1326     Json &runs = xjson.get_insert("runs");
1327     String xname = "x" + String(nb["experiments"].size());
1328     for (Json::const_iterator it = experiment_stats.begin();
1329          it != experiment_stats.end(); ++it) {
1330         String xkey = xname + "/" + it.key();
1331         runs.push_back(xkey);
1332         nb["data"][xkey] = it.value();
1333     }
1334     xjson.set("runs", runs);
1335
1336     nb["experiments"][xname] = xjson;
1337
1338     String new_text = nb.unparse(Json::indent_depth(4).tab_width(2).newline_terminator(true));
1339     f = (notebook == "-" ? stdout : fopen((notebook + "~").c_str(), "w"));
1340     if (!f) {
1341         fprintf(stderr, "%s~: %s\n", notebook.c_str(), strerror(errno));
1342         return;
1343     }
1344     size_t written = fwrite(new_text.data(), 1, new_text.length(), f);
1345     if (written != size_t(new_text.length())) {
1346         fprintf(stderr, "%s~: %s\n", notebook.c_str(), strerror(errno));
1347         fclose(f);
1348         return;
1349     }
1350     if (f != stdout) {
1351         fclose(f);
1352         if (rename((notebook + "~").c_str(), notebook.c_str()) != 0)
1353             fprintf(stderr, "%s: %s\n", notebook.c_str(), strerror(errno));
1354     }
1355
1356     fprintf(stderr, "EXPERIMENT %s\n", xname.c_str());
1357     experiment_stats.merge(old_data);
1358 }