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
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
17 // mttest: key/value tester
25 #include <sys/socket.h>
26 #include <netinet/in.h>
27 #include <netinet/tcp.h>
28 #include <sys/select.h>
32 #include <sys/utsname.h>
38 #include <sys/epoll.h>
44 #include <asm-generic/mman.h>
56 #include "nodeversion.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"
66 #include "kvrandom.hh"
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;
83 bool print_table = false;
84 static const char *gid = NULL;
86 // all default to the number of cores
87 static int udpthreads = 0;
88 static int tcpthreads = 0;
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;
98 #if MEMSTATS && HAVE_NUMA_H && HAVE_LIBNUMA
99 struct mttest_numainfo {
103 std::vector<mttest_numainfo> numa;
106 volatile bool recovering = false; // so don't add log entries, and free old value immediately
107 kvtimestamp_t initial_timestamp;
109 static const char *threadcounter_names[(int) tc_max];
111 /* running local tests */
112 void test_timeout(int) {
114 for (n = 0; n < arraysize(timeout) && timeout[n]; ++n)
116 if (n < arraysize(timeout)) {
118 if (n + 1 < arraysize(timeout) && duration[n + 1])
119 xalarm(duration[n + 1]);
123 template <typename T>
124 struct kvtest_client {
126 : limit_(test_limit), ncores_(udpthreads), kvo_() {
133 int nthreads() const {
139 void set_table(T *table, threadinfo *ti) {
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());
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]");
154 bool timeout(int which) const {
155 return ::timeout[which];
157 uint64_t limit() const {
160 Json param(const String& name) const {
161 return test_param[name];
170 int ruscale_partsz() const {
171 return (140 * 1000000) / 16;
173 int ruscale_init_part_no() const {
176 long nseqkeys() const {
177 return 16 * ruscale_partsz();
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());
187 bool get_sync_key16(long ikey) {
188 quick_istr key(ikey, 16);
189 return get_sync(key.string());
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));
195 void get_check(long ikey, long iexpected) {
196 quick_istr key(ikey), expected(iexpected);
197 get_check(key.string(), expected.string());
199 void get_check(const Str &key, long iexpected) {
200 quick_istr expected(iexpected);
201 get_check(key, expected.string());
203 void get_check_key8(long ikey, long iexpected) {
204 quick_istr key(ikey, 8), expected(iexpected);
205 get_check(key.string(), expected.string());
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());
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());
216 //void many_get_check(int nk, long ikey[], long iexpected[]);
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);
223 void put(const Str &key, const Str &value);
224 void put(const char *key, const char *value) {
225 put(Str(key), Str(value));
227 void put(long ikey, long ivalue) {
228 quick_istr key(ikey), value(ivalue);
229 put(key.string(), value.string());
231 void put(const Str &key, long ivalue) {
232 quick_istr value(ivalue);
233 put(key, value.string());
235 void put_key8(long ikey, long ivalue) {
236 quick_istr key(ikey, 8), value(ivalue);
237 put(key.string(), value.string());
239 void put_key16(long ikey, long ivalue) {
240 quick_istr key(ikey, 16), value(ivalue);
241 put(key.string(), value.string());
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());
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());
253 void remove(const Str &key);
254 void remove(long ikey) {
255 quick_istr key(ikey);
256 remove(key.string());
258 void remove_key8(long ikey) {
259 quick_istr key(ikey, 8);
260 remove(key.string());
262 void remove_key16(long ikey) {
263 quick_istr key(ikey, 16);
264 remove(key.string());
266 bool remove_sync(const Str &key);
267 bool remove_sync(long ikey) {
268 quick_istr key(ikey);
269 return remove_sync(key.string());
277 uint64_t e = timestamp() >> 16;
278 if (e != globalepoch)
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);
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);
294 report_.set("counters", counters);
296 fprintf(stderr, "%d: %s\n", ti_->index(), report_.unparse().c_str());
301 query<row_type> q_[1];
302 kvrandom_lcg_nr rand;
309 void output_scan(const Json& req, std::vector<Str>& keys, std::vector<Str>& values) const;
312 static volatile int kvtest_printing;
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))
318 table.print(f, indent);
321 template <typename T> inline void kvtest_json_stats(T& table, Json& j, threadinfo& ti) {
322 table.json_stats(j, ti);
325 template <typename T>
326 void kvtest_client<T>::get(long ikey) {
327 quick_istr key(ikey);
329 (void) q_[0].run_get1(table_->table(), key.string(), 0, val, *ti_);
332 template <typename T>
333 bool kvtest_client<T>::get_sync(const Str& key) {
335 return q_[0].run_get1(table_->table(), key, 0, val, *ti_);
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_);
343 template <typename T>
344 void kvtest_client<T>::get_check(const Str &key, const Str &expected) {
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);
355 template <typename T>
356 void kvtest_client<T>::get_col_check(const Str &key, int col,
357 const Str &expected) {
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);
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++){
373 ka[i+nk].set(iexpected[i]);
374 q_[i].begin_get1(ka[i].string());
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]);
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);
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);
405 template <typename T>
406 void kvtest_client<T>::output_scan(const Json& req, std::vector<Str>& keys,
407 std::vector<Str>& values) const {
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());
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_);
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
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_);
429 (void) key, (void) col, (void) value;
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_);
438 template <typename T>
439 void kvtest_client<T>::remove(const Str &key) {
440 (void) kvtest_remove(*this, key);
443 template <typename T>
444 bool kvtest_client<T>::remove_sync(const Str &key) {
445 return kvtest_remove(*this, key);
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))
453 String s = String(begin, sa.end());
454 if (!s.empty() && s.back() != '\n')
459 template <typename T>
460 void kvtest_client<T>::notice(const char *fmt, ...) {
463 String m = make_message(lcdf::StringAccum().vsnprintf(500, fmt, val));
466 fprintf(stderr, "%d: %s", ti_->index(), m.c_str());
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;
477 String m = make_message(lcdf::StringAccum().vsnprintf(500, fmt, val));
480 m = "unknown failure";
482 fail_message_lock.lock();
483 if (fail_message != m) {
485 fprintf(stderr, "%d: %s", ti_->index(), m.c_str());
487 fail_message_lock.unlock();
490 fprintf(stdout, "%d: %s", ti_->index(), m.c_str());
491 kvtest_print(*table_, stdout, 0, ti_);
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;
503 #define TESTRUNNER_CLIENT_TYPE kvtest_client<Masstree::default_table>&
504 #include "testrunner.hh"
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));
547 test_thread_initialize = 1,
548 test_thread_destroy = 2,
549 test_thread_stats = 3
552 template <typename T>
554 test_thread(threadinfo* ti) {
555 client_.set_table(table_, ti);
556 client_.ti_->rcu_start();
559 client_.ti_->rcu_stop();
561 static void setup(threadinfo* ti, int action) {
562 if (action == test_thread_initialize) {
565 table_->initialize(*ti);
566 } else if (action == test_thread_destroy) {
570 } else if (action == test_thread_stats) {
572 table_->stats(test_output_file);
575 static void* go(threadinfo* ti) {
581 CPU_SET(cores[ti->index()], &cs);
582 int r = sched_setaffinity(0, sizeof(cs), &cs);
583 always_assert(r == 0);
586 always_assert(!pinthreads && "pinthreads not supported\n");
589 test_thread<T> tt(ti);
590 if (fetch_and_add(&active_threads_, 1) == 0)
592 String test = ::current_test_name;
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);
604 tt.client_.fail("unknown test %s", subtest.c_str());
605 if (comma == test.length())
607 pthread_mutex_lock(&subtest_mutex);
608 if (fetch_and_add(&active_threads_, -1) == 1) {
609 pthread_cond_broadcast(&subtest_cond);
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);
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) {
624 kvtest_json_stats(*table_, j, *tt.client_.ti_);
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);
630 fprintf(test_output_file, "%s\n", tt.client_.report_.unparse().c_str());
633 void ready_timeouts() {
634 for (size_t i = 0; i < arraysize(timeout); ++i)
636 if (!lazy_timer && duration[0])
640 static unsigned active_threads_;
641 kvtest_client<T> client_;
643 template <typename T> T *test_thread<T>::table_;
644 template <typename T> unsigned test_thread<T>::active_threads_;
646 typedef test_thread<Masstree::default_table> masstree_test_thread;
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 }
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);
670 for (int i = 0; i < nthreads; ++i)
671 pthread_join(tis[i]->threadid(), 0);
675 static const char * const kvstats_name[] = {
676 "ops_per_sec", "puts_per_sec", "gets_per_sec", "scans_per_sec"
679 static Json experiment_stats;
681 void *stat_collector(void *arg) {
682 int p = (int) (intptr_t) arg;
683 FILE *f = fdopen(p, "r");
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;
693 fprintf(stderr, "%s\n", buf);
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 }
737 printf("Masstree-beta mttest\n\
738 Usage: mttest [-jTHREADS] [OPTIONS] [PARAM=VALUE...] TEST...\n\
739 mttest -n -c TESTNAME...\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\
751 -n, --no-run Do not run new tests.\n\
752 -c, --compare=EXPERIMENT Generated plot compares to EXPERIMENT.\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");
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);
769 static const int abortable_signals[] = {
770 SIGSEGV, SIGBUS, SIGILL, SIGABRT, SIGFPE
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);
788 main(int argc, char *argv[])
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";
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);
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,
814 Clp_AddType(clp, clp_val_suffixdouble, Clp_DisallowOptions, clp_parse_suffixdouble, 0);
816 while ((opt = Clp_Next(clp)) != Clp_Done) {
819 pinthreads = !clp->negated;
822 tcpthreads = udpthreads = clp->val.i;
825 ntrials = clp->val.i;
828 quiet = !clp->negated;
831 print_table = !clp->negated;
833 case opt_rscale_ncores:
834 rscale_ncores = clp->val.i;
840 duration[0] = clp->val.d;
846 test_limit = uint64_t(clp->val.d);
849 tests.push_back(clp->vstr);
852 tests.push_back(clp->option->long_name + 5);
855 normtype = clp->negated ? normtype_none : clp->val.i;
869 else if (clp->have_val)
870 notebook = clp->vstr;
872 notebook = "notebook-mttest.json";
875 comparisons.push_back(clp->vstr);
881 if (firstcore >= 0 || cores.size() > 0) {
882 Clp_OptionError(clp, "%<%O%> already given");
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)
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();
898 for (int i = 0; i < aj.size(); ++i)
899 cores.push_back(aj[i].to_i());
901 Clp_OptionError(clp, "bad %<%O%>, expected %<CORE1%>, %<CORE1+STRIDE%>, or %<CORE1,CORE2,...%>");
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);
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));
929 fprintf(stderr, "Usage: mttest [-jN] TESTS...\n\
930 Try 'mttest --help' for options.\n");
934 Clp_DeleteParser(clp);
936 firstcore = cores.size() ? cores.back() + 1 : 0;
937 for (; (int) cores.size() < udpthreads; firstcore += corestride)
938 cores.push_back(firstcore);
941 always_assert(pinthreads && "Using performance counter requires pinning threads to cores!");
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);
951 for (const int* it = abortable_signals;
952 it != abortable_signals + arraysize(abortable_signals); ++it)
953 signal(*it, abortable_signal_handler);
956 if (treetypes.empty())
957 treetypes.push_back("m");
959 tests.push_back("rw1");
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);
967 // pipe for them to write back to us
970 always_assert(ret == 0);
971 test_output_file = fdopen(p[1], "w");
974 ret = pthread_create(&collector, 0, stat_collector, (void *) (intptr_t) p[0]);
975 always_assert(ret == 0);
976 initial_timestamp = timestamp();
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)
984 for (int counter = 0; counter < nruns; ++counter) {
985 int x = random() % runlist.size();
986 int run = runlist[x];
987 runlist[x] = runlist.back();
990 int trial = run % ntrials;
992 int t = run % tests.size();
996 fprintf(stderr, "%d/%u %s/%s%s", counter + 1, (int) (ntrials * tests.size() * treetypes.size()),
997 tests[t], treetypes[tt], quiet ? " " : "\n");
999 run_one_test(trial, treetypes[tt], tests[t], p, nruns);
1000 struct timeval delay;
1002 delay.tv_usec = 250000;
1003 (void) select(0, 0, 0, 0, &delay);
1006 fprintf(stderr, "\r%60s\r", "");
1009 fclose(test_output_file);
1010 pthread_join(collector, 0);
1012 // update lab notebook
1014 update_labnotebook(notebook);
1018 comparisons.insert(comparisons.begin(), "");
1019 if (!isatty(STDOUT_FILENO))
1020 print_gnuplot(stdout, kvstats_name, kvstats_name + arraysize(kvstats_name),
1021 comparisons, normtype);
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);
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);
1037 test_thread_map[i].setup_func(main_ti, test_thread_stats);
1038 test_thread_map[i].setup_func(main_ti, test_thread_destroy);
1043 static void run_one_test(int trial, const char *treetype, const char *test,
1044 const int *collectorpipe, int nruns) {
1046 run_one_test_body(trial, treetype, test);
1050 close(collectorpipe[0]);
1051 run_one_test_body(trial, treetype, test);
1054 while (waitpid(c, 0, 0) == -1 && errno == EINTR)
1059 static double level(const std::vector<double> &v, double frac) {
1060 frac *= v.size() - 1;
1061 int base = (int) frac;
1065 return v[base] * (1 - (frac - base)) + v[base + 1] * (frac - base);
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)
1077 return key.substring(l, r);
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)
1086 } else if (!isdigit((unsigned char) s[-1]))
1088 return key.substring(l, r);
1091 static String experiment_test_table(const String &key) {
1092 return experiment_run_test_table(experiment_test_table_trial(key));
1096 struct gnuplot_info {
1097 static constexpr double trialdelta = 0.015, treetypedelta = 0.04,
1098 testdelta = 0.08, typedelta = 0.2;
1101 double normalization;
1105 std::vector<lcdf::StringAccum> candlesticks;
1106 std::vector<lcdf::StringAccum> medians;
1107 lcdf::StringAccum xtics;
1109 gnuplot_info(int nt)
1110 : pos(1 - trialdelta), nextdelta(trialdelta), normalization(-1),
1113 void one(const String &xname, int ti, const String &datatype_name);
1114 void print(FILE *f, const char * const *types_begin);
1116 constexpr double gnuplot_info::trialdelta, gnuplot_info::treetypedelta, gnuplot_info::testdelta, gnuplot_info::typedelta;
1118 void gnuplot_info::one(const String &xname, int ti, const String &datatype_name)
1120 String current_test = experiment_test_table(xname);
1121 if (current_test != last_test) {
1122 last_test = current_test;
1123 if (normalizetype == normtype_pertest)
1125 if (nextdelta == treetypedelta)
1126 nextdelta = testdelta;
1128 double beginpos = pos, firstpos = pos + nextdelta;
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));
1137 std::sort(trials.begin(), trials.end());
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()) {
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);
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;
1165 if (pos > beginpos) {
1166 double middle = (firstpos + pos) / 2;
1167 xtics << (xtics ? ", " : "") << "\"" << xname << "\" " << middle;
1168 nextdelta = treetypedelta;
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)
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"),
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");
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)
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]);
1201 for (int i = 0; i < int(medians.size()); ++i)
1203 fwrite(candlesticks[i].begin(), 1, candlesticks[i].length(), f);
1205 fwrite(medians[i].begin(), 1, medians[i].length(), f);
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) {
1218 else if (cit->length() >= 2 && (*cit)[0] == 'x' && isdigit((unsigned char) (*cit)[1]))
1219 *cit += String(cit->find_left('/') < 0 ? "/*" : "*");
1221 *cit = String("x*") + *cit + String("*");
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()));
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());
1241 int ntypes = (int) (types_end - types_begin);
1242 gnuplot_info gpinfo(normalizetype);
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]);
1253 if (gpinfo.pos > typepos)
1254 gpinfo.nextdelta = gpinfo.typedelta;
1255 gpinfo.last_test = "";
1259 gpinfo.print(f, types_begin);
1263 read_file(FILE *f, const char *name)
1265 lcdf::StringAccum sa;
1267 size_t x = fread(sa.reserve(4096), 1, 4096, f);
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);
1274 return sa.take_string();
1279 update_labnotebook(String notebook)
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())
1285 if (f && f != stdin)
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());
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());
1301 Json old_data = nb["data"];
1302 if (!experiment_stats) {
1303 experiment_stats = old_data;
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>");
1313 xjson.set("git-revision", git_info.trim());
1315 time_t now = time(0);
1316 xjson.set("time", String(ctime(&now)).trim());
1318 xjson.set("gid", String(gid));
1320 struct utsname name;
1321 if (uname(&name) == 0)
1322 xjson.set("machine", name.nodename);
1324 xjson.set("cores", udpthreads);
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();
1334 xjson.set("runs", runs);
1336 nb["experiments"][xname] = xjson;
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"));
1341 fprintf(stderr, "%s~: %s\n", notebook.c_str(), strerror(errno));
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));
1352 if (rename((notebook + "~").c_str(), notebook.c_str()) != 0)
1353 fprintf(stderr, "%s: %s\n", notebook.c_str(), strerror(errno));
1356 fprintf(stderr, "EXPERIMENT %s\n", xname.c_str());
1357 experiment_stats.merge(old_data);