From 19b84c667216ff74f1b747e18b5542444dc54716 Mon Sep 17 00:00:00 2001 From: ahmad Date: Thu, 7 Feb 2019 15:22:50 -0800 Subject: [PATCH] benchmark silo added --- README.md | 6 + silo/AUTHORS | 8 + silo/BUILD | 18 + silo/LICENSE | 21 + silo/Makefile | 279 + silo/README.md | 58 + silo/allocator.cc | 376 + silo/allocator.h | 145 + silo/amd64.h | 21 + silo/base_txn_btree.h | 495 ++ silo/benchmarks/abstract_db.h | 137 + silo/benchmarks/abstract_ordered_index.h | 150 + silo/benchmarks/bdb_wrapper.cc | 101 + silo/benchmarks/bdb_wrapper.h | 95 + silo/benchmarks/bench.cc | 428 + silo/benchmarks/bench.h | 338 + silo/benchmarks/bid.cc | 266 + silo/benchmarks/dbtest.cc | 407 + silo/benchmarks/encstress.cc | 180 + silo/benchmarks/gc_runner.sh | 31 + silo/benchmarks/kvdb_wrapper.h | 98 + silo/benchmarks/kvdb_wrapper_impl.h | 558 ++ silo/benchmarks/masstree/README | 3 + silo/benchmarks/masstree/kvrandom.cc | 38 + silo/benchmarks/masstree/kvrandom.hh | 100 + silo/benchmarks/masstree/kvtest.cc | 179 + silo/benchmarks/mysql_wrapper.cc | 255 + silo/benchmarks/mysql_wrapper.h | 97 + silo/benchmarks/ndb_wrapper.h | 164 + silo/benchmarks/ndb_wrapper_impl.h | 600 ++ silo/benchmarks/plotter.py | 16 + silo/benchmarks/queue.cc | 296 + silo/benchmarks/results/NOTES.txt | 19 + silo/benchmarks/results/ben-3-8-13.py | 1 + silo/benchmarks/results/ben-4-10-13.py | 1 + silo/benchmarks/results/istc11-3-13-13.py | 1 + silo/benchmarks/results/istc11-3-14-13.py | 1 + silo/benchmarks/results/istc11-3-16-13.py | 1 + silo/benchmarks/results/istc11-3-18-13.py | 1 + silo/benchmarks/results/istc11-3-21-13.py | 1 + silo/benchmarks/results/istc11-3-22-13.py | 1 + silo/benchmarks/results/istc11-3-23-13.py | 1 + silo/benchmarks/results/istc11-3-26-13.py | 4 + silo/benchmarks/results/istc11-4-10-13.py | 1 + .../results/istc11-5-18-13-tpcc-chains.txt | 108 + .../results/istc11-5-18-13-ycsb-chains.txt | 9 + silo/benchmarks/results/istc11-5-18-13.py | 1 + .../results/istc11-8-28-13_cameraready.py | 1 + .../results/istc12-8-30-13_cameraready.py | 1 + silo/benchmarks/results/istc3-10-23-13.py | 1 + silo/benchmarks/results/istc3-7-27-13.py | 1 + silo/benchmarks/results/istc3-7-31-13.py | 1 + silo/benchmarks/results/istc3-8-1-13.py | 1 + .../results/istc3-8-1-13_compress.py | 1 + .../results/istc3-8-1-13_fake_compress.py | 1 + .../results/istc3-8-1-13_fake_writes.py | 1 + .../istc3-8-1-13_fake_writes_stride.py | 1 + .../istc3-8-1-13_fake_writes_stride1.py | 1 + .../results/istc3-8-1-13_log_reduce_size.py | 1 + .../results/istc3-8-1-13_log_reduce_size_1.py | 1 + .../istc3-8-1-13_log_reduce_size_nofsync.py | 1 + .../results/istc3-8-1-13_newbench.py | 1 + silo/benchmarks/results/istc3-8-12-13.py | 1 + .../results/istc3-8-16-13_multipart_skew.py | 1 + .../results/istc3-8-19-13_cameraready.py | 1 + .../results/istc3-8-21-13_cameraready-1.py | 1 + .../results/istc3-8-21-13_cameraready.py | 1 + .../results/istc3-8-22-13_cameraready.py | 1 + .../results/istc3-8-22-13_cameraready_2.py | 1 + .../results/istc3-8-23-13_cameraready.py | 1 + .../results/istc3-8-24-13_cameraready.py | 1 + silo/benchmarks/results/istc3-9-6-13.py | 1 + silo/benchmarks/results/istc3-9-8-13.py | 1 + silo/benchmarks/results/make_graphs-2.py | 38 + silo/benchmarks/results/make_graphs-3.py | 226 + silo/benchmarks/results/make_graphs-4.py | 137 + silo/benchmarks/results/make_graphs-5.py | 148 + silo/benchmarks/results/make_graphs-6.py | 701 ++ silo/benchmarks/results/make_graphs.py | 26 + silo/benchmarks/results/tom-1-22-13.py | 4 + silo/benchmarks/results/tom-2-13-13.py | 1 + silo/benchmarks/results/tom-2-6-13.py | 6 + silo/benchmarks/runner.py | 759 ++ silo/benchmarks/stats_runner.py | 34 + silo/benchmarks/tpcc.cc | 2214 +++++ silo/benchmarks/tpcc.h | 162 + silo/benchmarks/ycsb.cc | 519 ++ silo/btree.cc | 2010 +++++ silo/btree.h | 1794 ++++ silo/btree_choice.h | 8 + silo/btree_impl.h | 2042 +++++ silo/circbuf.h | 112 + silo/compile.sh | 4 + silo/config/config-backoff.h | 3 + silo/config/config-factor-fake-compression.h | 3 + silo/config/config-factor-gc-nowriteinplace.h | 5 + silo/config/config-factor-gc.h | 4 + silo/config/config-perf.h | 1 + silo/config/config-sandbox.h | 6 + silo/core.cc | 35 + silo/core.h | 206 + silo/counter.cc | 119 + silo/counter.h | 163 + silo/fileutils.h | 40 + silo/imstring.h | 125 + silo/lockguard.h | 37 + silo/log2.hh | 42 + silo/macros.h | 132 + silo/marked_ptr.h | 170 + silo/masstree/AUTHORS | 8 + silo/masstree/GNUmakefile | 95 + silo/masstree/GNUmakefile.in | 95 + silo/masstree/LICENSE | 34 + silo/masstree/README.md | 160 + silo/masstree/_masstree_config.d | 1 + silo/masstree/autom4te.cache/output.0 | 7594 +++++++++++++++++ silo/masstree/autom4te.cache/output.1 | 7594 +++++++++++++++++ silo/masstree/autom4te.cache/requests | 107 + silo/masstree/autom4te.cache/traces.0 | 211 + silo/masstree/autom4te.cache/traces.1 | 619 ++ silo/masstree/btree_leaflink.hh | 124 + silo/masstree/checkpoint.cc | 30 + silo/masstree/checkpoint.hh | 56 + silo/masstree/circular_int.hh | 146 + silo/masstree/clp.c | 2506 ++++++ silo/masstree/clp.h | 348 + silo/masstree/compiler.cc | 51 + silo/masstree/compiler.hh | 1178 +++ silo/masstree/config.h | 326 + silo/masstree/config.h.in | 325 + silo/masstree/config.log | 1511 ++++ silo/masstree/config.status | 1053 +++ silo/masstree/configure | 7594 +++++++++++++++++ silo/masstree/configure.ac | 438 + silo/masstree/doc/.gitignore | 11 + silo/masstree/doc/GNUmakefile | 87 + silo/masstree/doc/elements.mp | 520 ++ silo/masstree/doc/elemfig.sty | 88 + silo/masstree/doc/examples.mp | 53 + silo/masstree/doc/insert1.mp | 179 + silo/masstree/doc/masstree.mp | 200 + silo/masstree/doc/patches.mp | 44 + silo/masstree/doc/remove1.mp | 327 + silo/masstree/doc/remove2.mp | 408 + silo/masstree/doc/spec.tex | 1395 +++ silo/masstree/file.cc | 92 + silo/masstree/file.hh | 82 + silo/masstree/hashcode.hh | 119 + silo/masstree/json.cc | 1226 +++ silo/masstree/json.hh | 3180 +++++++ silo/masstree/jsontest.cc | 603 ++ silo/masstree/kpermuter.hh | 325 + silo/masstree/ksearch.hh | 173 + silo/masstree/kvio.cc | 112 + silo/masstree/kvio.hh | 67 + silo/masstree/kvproto.hh | 57 + silo/masstree/kvrandom.cc | 38 + silo/masstree/kvrandom.hh | 99 + silo/masstree/kvrow.hh | 321 + silo/masstree/kvstats.hh | 53 + silo/masstree/kvtest.hh | 1627 ++++ silo/masstree/kvthread.cc | 315 + silo/masstree/kvthread.hh | 477 ++ silo/masstree/local_vector.hh | 337 + silo/masstree/log.cc | 864 ++ silo/masstree/log.hh | 233 + silo/masstree/masstree.hh | 97 + silo/masstree/masstree_get.hh | 120 + silo/masstree/masstree_insert.hh | 181 + silo/masstree/masstree_key.hh | 240 + silo/masstree/masstree_print.hh | 160 + silo/masstree/masstree_remove.hh | 357 + silo/masstree/masstree_scan.hh | 399 + silo/masstree/masstree_split.hh | 274 + silo/masstree/masstree_struct.hh | 773 ++ silo/masstree/masstree_tcursor.hh | 228 + silo/masstree/misc.cc | 40 + silo/masstree/misc.hh | 86 + silo/masstree/msgpack.cc | 240 + silo/masstree/msgpack.hh | 692 ++ silo/masstree/msgpacktest.cc | 209 + silo/masstree/mtclient.cc | 1702 ++++ silo/masstree/mtclient.hh | 219 + silo/masstree/mtcounters.hh | 55 + silo/masstree/mtd.cc | 1704 ++++ silo/masstree/mttest.cc | 1358 +++ silo/masstree/nodeversion.hh | 343 + silo/masstree/perfstat.cc | 216 + silo/masstree/perfstat.hh | 38 + silo/masstree/query_masstree.cc | 424 + silo/masstree/query_masstree.hh | 82 + silo/masstree/str.cc | 53 + silo/masstree/str.hh | 165 + silo/masstree/straccum.cc | 398 + silo/masstree/straccum.hh | 736 ++ silo/masstree/string.cc | 1381 +++ silo/masstree/string.hh | 880 ++ silo/masstree/string_base.hh | 628 ++ silo/masstree/string_slice.cc | 16 + silo/masstree/string_slice.hh | 166 + silo/masstree/stringbag.hh | 162 + silo/masstree/test_atomics.cc | 468 + silo/masstree/test_string.cc | 89 + silo/masstree/testrunner.cc | 54 + silo/masstree/testrunner.hh | 60 + silo/masstree/timestamp.hh | 63 + silo/masstree/value_array.cc | 66 + silo/masstree/value_array.hh | 156 + silo/masstree/value_bag.hh | 285 + silo/masstree/value_string.cc | 18 + silo/masstree/value_string.hh | 193 + silo/masstree/value_versioned_array.cc | 97 + silo/masstree/value_versioned_array.hh | 205 + silo/masstree_btree.h | 812 ++ silo/memory.cc | 82 + silo/ndb_type_traits.h | 50 + silo/new-benchmarks/abstract_db.h | 111 + silo/new-benchmarks/abstract_ordered_index.h | 75 + silo/new-benchmarks/bench.cc | 406 + silo/new-benchmarks/bench.h | 422 + silo/new-benchmarks/dbtest.cc | 340 + silo/new-benchmarks/kvdb_database.h | 800 ++ silo/new-benchmarks/ndb_database.h | 237 + silo/new-benchmarks/tpcc.cc | 2276 +++++ silo/new-benchmarks/tpcc.h | 208 + silo/ownership_checker.h | 48 + silo/persist_test.cc | 1221 +++ silo/prefetch.h | 54 + silo/pxqueue.h | 354 + silo/rcu.cc | 390 + silo/rcu.h | 333 + silo/record/cursor.h | 174 + silo/record/encoder.h | 625 ++ silo/record/inline_str.h | 352 + silo/record/serializer.h | 246 + silo/run.sh | 4 + silo/scopedperf.hh | 794 ++ silo/scripts/tester.py | 110 + silo/scripts/tester.sh | 14 + silo/small_unordered_map.h | 511 ++ silo/small_vector.h | 648 ++ silo/spinbarrier.h | 53 + silo/spinlock.h | 55 + silo/static_unordered_map.h | 345 + silo/static_vector.h | 407 + silo/stats_client.cc | 90 + silo/stats_common.h | 63 + silo/stats_server.cc | 94 + silo/stats_server.h | 15 + silo/str_arena.h | 133 + silo/test.cc | 1016 +++ silo/third-party/lz4/LZ4 Streaming Format.odt | Bin 0 -> 92660 bytes silo/third-party/lz4/Makefile | 40 + silo/third-party/lz4/bench.c | 434 + silo/third-party/lz4/bench.h | 41 + silo/third-party/lz4/cmake/CMakeLists.txt | 106 + .../third-party/lz4/cmake/pack/CMakeLists.txt | 82 + .../lz4/cmake/pack/release_COPYING.txt | 21 + silo/third-party/lz4/fullbench.c | 638 ++ silo/third-party/lz4/fuzzer.c | 259 + silo/third-party/lz4/liblz4.so | Bin 0 -> 29984 bytes silo/third-party/lz4/lz4.c | 703 ++ silo/third-party/lz4/lz4.h | 200 + silo/third-party/lz4/lz4.o | Bin 0 -> 22768 bytes silo/third-party/lz4/lz4_encoder.h | 262 + .../lz4/lz4_format_description.txt | 120 + silo/third-party/lz4/lz4c.c | 1066 +++ silo/third-party/lz4/lz4hc.c | 584 ++ silo/third-party/lz4/lz4hc.h | 111 + silo/third-party/lz4/lz4hc_encoder.h | 349 + silo/third-party/lz4/xxhash.c | 477 ++ silo/third-party/lz4/xxhash.h | 164 + silo/third-party/lz4/xxhash.o | Bin 0 -> 3456 bytes silo/thread.cc | 31 + silo/thread.h | 55 + silo/ticker.cc | 3 + silo/ticker.h | 241 + silo/tuple.cc | 105 + silo/tuple.h | 1099 +++ silo/txn.cc | 67 + silo/txn.h | 865 ++ silo/txn_btree.cc | 1906 +++++ silo/txn_btree.h | 483 ++ silo/txn_impl.h | 643 ++ silo/txn_proto2_impl.cc | 716 ++ silo/txn_proto2_impl.h | 1265 +++ silo/typed_txn_btree.h | 593 ++ silo/util.h | 712 ++ silo/varint.cc | 32 + silo/varint.h | 164 + silo/varkey.h | 222 + 291 files changed, 109496 insertions(+) create mode 100644 silo/AUTHORS create mode 100644 silo/BUILD create mode 100644 silo/LICENSE create mode 100644 silo/Makefile create mode 100644 silo/README.md create mode 100644 silo/allocator.cc create mode 100644 silo/allocator.h create mode 100644 silo/amd64.h create mode 100644 silo/base_txn_btree.h create mode 100644 silo/benchmarks/abstract_db.h create mode 100644 silo/benchmarks/abstract_ordered_index.h create mode 100644 silo/benchmarks/bdb_wrapper.cc create mode 100644 silo/benchmarks/bdb_wrapper.h create mode 100644 silo/benchmarks/bench.cc create mode 100644 silo/benchmarks/bench.h create mode 100644 silo/benchmarks/bid.cc create mode 100644 silo/benchmarks/dbtest.cc create mode 100644 silo/benchmarks/encstress.cc create mode 100755 silo/benchmarks/gc_runner.sh create mode 100644 silo/benchmarks/kvdb_wrapper.h create mode 100644 silo/benchmarks/kvdb_wrapper_impl.h create mode 100644 silo/benchmarks/masstree/README create mode 100644 silo/benchmarks/masstree/kvrandom.cc create mode 100644 silo/benchmarks/masstree/kvrandom.hh create mode 100644 silo/benchmarks/masstree/kvtest.cc create mode 100644 silo/benchmarks/mysql_wrapper.cc create mode 100644 silo/benchmarks/mysql_wrapper.h create mode 100644 silo/benchmarks/ndb_wrapper.h create mode 100644 silo/benchmarks/ndb_wrapper_impl.h create mode 100644 silo/benchmarks/plotter.py create mode 100644 silo/benchmarks/queue.cc create mode 100644 silo/benchmarks/results/NOTES.txt create mode 100644 silo/benchmarks/results/ben-3-8-13.py create mode 100644 silo/benchmarks/results/ben-4-10-13.py create mode 100644 silo/benchmarks/results/istc11-3-13-13.py create mode 100644 silo/benchmarks/results/istc11-3-14-13.py create mode 100644 silo/benchmarks/results/istc11-3-16-13.py create mode 100644 silo/benchmarks/results/istc11-3-18-13.py create mode 100644 silo/benchmarks/results/istc11-3-21-13.py create mode 100644 silo/benchmarks/results/istc11-3-22-13.py create mode 100644 silo/benchmarks/results/istc11-3-23-13.py create mode 100644 silo/benchmarks/results/istc11-3-26-13.py create mode 100644 silo/benchmarks/results/istc11-4-10-13.py create mode 100644 silo/benchmarks/results/istc11-5-18-13-tpcc-chains.txt create mode 100644 silo/benchmarks/results/istc11-5-18-13-ycsb-chains.txt create mode 100644 silo/benchmarks/results/istc11-5-18-13.py create mode 100644 silo/benchmarks/results/istc11-8-28-13_cameraready.py create mode 100644 silo/benchmarks/results/istc12-8-30-13_cameraready.py create mode 100644 silo/benchmarks/results/istc3-10-23-13.py create mode 100644 silo/benchmarks/results/istc3-7-27-13.py create mode 100644 silo/benchmarks/results/istc3-7-31-13.py create mode 100644 silo/benchmarks/results/istc3-8-1-13.py create mode 100644 silo/benchmarks/results/istc3-8-1-13_compress.py create mode 100644 silo/benchmarks/results/istc3-8-1-13_fake_compress.py create mode 100644 silo/benchmarks/results/istc3-8-1-13_fake_writes.py create mode 100644 silo/benchmarks/results/istc3-8-1-13_fake_writes_stride.py create mode 100644 silo/benchmarks/results/istc3-8-1-13_fake_writes_stride1.py create mode 100644 silo/benchmarks/results/istc3-8-1-13_log_reduce_size.py create mode 100644 silo/benchmarks/results/istc3-8-1-13_log_reduce_size_1.py create mode 100644 silo/benchmarks/results/istc3-8-1-13_log_reduce_size_nofsync.py create mode 100644 silo/benchmarks/results/istc3-8-1-13_newbench.py create mode 100644 silo/benchmarks/results/istc3-8-12-13.py create mode 100644 silo/benchmarks/results/istc3-8-16-13_multipart_skew.py create mode 100644 silo/benchmarks/results/istc3-8-19-13_cameraready.py create mode 100644 silo/benchmarks/results/istc3-8-21-13_cameraready-1.py create mode 100644 silo/benchmarks/results/istc3-8-21-13_cameraready.py create mode 100644 silo/benchmarks/results/istc3-8-22-13_cameraready.py create mode 100644 silo/benchmarks/results/istc3-8-22-13_cameraready_2.py create mode 100644 silo/benchmarks/results/istc3-8-23-13_cameraready.py create mode 100644 silo/benchmarks/results/istc3-8-24-13_cameraready.py create mode 100644 silo/benchmarks/results/istc3-9-6-13.py create mode 100644 silo/benchmarks/results/istc3-9-8-13.py create mode 100755 silo/benchmarks/results/make_graphs-2.py create mode 100755 silo/benchmarks/results/make_graphs-3.py create mode 100644 silo/benchmarks/results/make_graphs-4.py create mode 100644 silo/benchmarks/results/make_graphs-5.py create mode 100644 silo/benchmarks/results/make_graphs-6.py create mode 100755 silo/benchmarks/results/make_graphs.py create mode 100644 silo/benchmarks/results/tom-1-22-13.py create mode 100644 silo/benchmarks/results/tom-2-13-13.py create mode 100644 silo/benchmarks/results/tom-2-6-13.py create mode 100644 silo/benchmarks/runner.py create mode 100644 silo/benchmarks/stats_runner.py create mode 100644 silo/benchmarks/tpcc.cc create mode 100644 silo/benchmarks/tpcc.h create mode 100644 silo/benchmarks/ycsb.cc create mode 100644 silo/btree.cc create mode 100644 silo/btree.h create mode 100644 silo/btree_choice.h create mode 100644 silo/btree_impl.h create mode 100644 silo/circbuf.h create mode 100755 silo/compile.sh create mode 100644 silo/config/config-backoff.h create mode 100644 silo/config/config-factor-fake-compression.h create mode 100644 silo/config/config-factor-gc-nowriteinplace.h create mode 100644 silo/config/config-factor-gc.h create mode 100644 silo/config/config-perf.h create mode 100644 silo/config/config-sandbox.h create mode 100644 silo/core.cc create mode 100644 silo/core.h create mode 100644 silo/counter.cc create mode 100644 silo/counter.h create mode 100644 silo/fileutils.h create mode 100644 silo/imstring.h create mode 100644 silo/lockguard.h create mode 100644 silo/log2.hh create mode 100644 silo/macros.h create mode 100644 silo/marked_ptr.h create mode 100644 silo/masstree/AUTHORS create mode 100644 silo/masstree/GNUmakefile create mode 100644 silo/masstree/GNUmakefile.in create mode 100644 silo/masstree/LICENSE create mode 100644 silo/masstree/README.md create mode 100644 silo/masstree/_masstree_config.d create mode 100644 silo/masstree/autom4te.cache/output.0 create mode 100644 silo/masstree/autom4te.cache/output.1 create mode 100644 silo/masstree/autom4te.cache/requests create mode 100644 silo/masstree/autom4te.cache/traces.0 create mode 100644 silo/masstree/autom4te.cache/traces.1 create mode 100644 silo/masstree/btree_leaflink.hh create mode 100644 silo/masstree/checkpoint.cc create mode 100644 silo/masstree/checkpoint.hh create mode 100644 silo/masstree/circular_int.hh create mode 100644 silo/masstree/clp.c create mode 100644 silo/masstree/clp.h create mode 100644 silo/masstree/compiler.cc create mode 100644 silo/masstree/compiler.hh create mode 100644 silo/masstree/config.h create mode 100644 silo/masstree/config.h.in create mode 100644 silo/masstree/config.log create mode 100755 silo/masstree/config.status create mode 100755 silo/masstree/configure create mode 100644 silo/masstree/configure.ac create mode 100644 silo/masstree/doc/.gitignore create mode 100644 silo/masstree/doc/GNUmakefile create mode 100644 silo/masstree/doc/elements.mp create mode 100644 silo/masstree/doc/elemfig.sty create mode 100644 silo/masstree/doc/examples.mp create mode 100644 silo/masstree/doc/insert1.mp create mode 100644 silo/masstree/doc/masstree.mp create mode 100644 silo/masstree/doc/patches.mp create mode 100644 silo/masstree/doc/remove1.mp create mode 100644 silo/masstree/doc/remove2.mp create mode 100644 silo/masstree/doc/spec.tex create mode 100644 silo/masstree/file.cc create mode 100644 silo/masstree/file.hh create mode 100644 silo/masstree/hashcode.hh create mode 100644 silo/masstree/json.cc create mode 100644 silo/masstree/json.hh create mode 100644 silo/masstree/jsontest.cc create mode 100644 silo/masstree/kpermuter.hh create mode 100644 silo/masstree/ksearch.hh create mode 100644 silo/masstree/kvio.cc create mode 100644 silo/masstree/kvio.hh create mode 100644 silo/masstree/kvproto.hh create mode 100644 silo/masstree/kvrandom.cc create mode 100644 silo/masstree/kvrandom.hh create mode 100644 silo/masstree/kvrow.hh create mode 100644 silo/masstree/kvstats.hh create mode 100644 silo/masstree/kvtest.hh create mode 100644 silo/masstree/kvthread.cc create mode 100644 silo/masstree/kvthread.hh create mode 100644 silo/masstree/local_vector.hh create mode 100644 silo/masstree/log.cc create mode 100644 silo/masstree/log.hh create mode 100644 silo/masstree/masstree.hh create mode 100644 silo/masstree/masstree_get.hh create mode 100644 silo/masstree/masstree_insert.hh create mode 100644 silo/masstree/masstree_key.hh create mode 100644 silo/masstree/masstree_print.hh create mode 100644 silo/masstree/masstree_remove.hh create mode 100644 silo/masstree/masstree_scan.hh create mode 100644 silo/masstree/masstree_split.hh create mode 100644 silo/masstree/masstree_struct.hh create mode 100644 silo/masstree/masstree_tcursor.hh create mode 100644 silo/masstree/misc.cc create mode 100644 silo/masstree/misc.hh create mode 100644 silo/masstree/msgpack.cc create mode 100644 silo/masstree/msgpack.hh create mode 100644 silo/masstree/msgpacktest.cc create mode 100644 silo/masstree/mtclient.cc create mode 100644 silo/masstree/mtclient.hh create mode 100644 silo/masstree/mtcounters.hh create mode 100644 silo/masstree/mtd.cc create mode 100644 silo/masstree/mttest.cc create mode 100644 silo/masstree/nodeversion.hh create mode 100644 silo/masstree/perfstat.cc create mode 100644 silo/masstree/perfstat.hh create mode 100644 silo/masstree/query_masstree.cc create mode 100644 silo/masstree/query_masstree.hh create mode 100644 silo/masstree/str.cc create mode 100644 silo/masstree/str.hh create mode 100644 silo/masstree/straccum.cc create mode 100644 silo/masstree/straccum.hh create mode 100644 silo/masstree/string.cc create mode 100644 silo/masstree/string.hh create mode 100644 silo/masstree/string_base.hh create mode 100644 silo/masstree/string_slice.cc create mode 100644 silo/masstree/string_slice.hh create mode 100644 silo/masstree/stringbag.hh create mode 100644 silo/masstree/test_atomics.cc create mode 100644 silo/masstree/test_string.cc create mode 100644 silo/masstree/testrunner.cc create mode 100644 silo/masstree/testrunner.hh create mode 100644 silo/masstree/timestamp.hh create mode 100644 silo/masstree/value_array.cc create mode 100644 silo/masstree/value_array.hh create mode 100644 silo/masstree/value_bag.hh create mode 100644 silo/masstree/value_string.cc create mode 100644 silo/masstree/value_string.hh create mode 100644 silo/masstree/value_versioned_array.cc create mode 100644 silo/masstree/value_versioned_array.hh create mode 100644 silo/masstree_btree.h create mode 100644 silo/memory.cc create mode 100644 silo/ndb_type_traits.h create mode 100644 silo/new-benchmarks/abstract_db.h create mode 100644 silo/new-benchmarks/abstract_ordered_index.h create mode 100644 silo/new-benchmarks/bench.cc create mode 100644 silo/new-benchmarks/bench.h create mode 100644 silo/new-benchmarks/dbtest.cc create mode 100644 silo/new-benchmarks/kvdb_database.h create mode 100644 silo/new-benchmarks/ndb_database.h create mode 100644 silo/new-benchmarks/tpcc.cc create mode 100644 silo/new-benchmarks/tpcc.h create mode 100644 silo/ownership_checker.h create mode 100644 silo/persist_test.cc create mode 100644 silo/prefetch.h create mode 100644 silo/pxqueue.h create mode 100644 silo/rcu.cc create mode 100644 silo/rcu.h create mode 100644 silo/record/cursor.h create mode 100644 silo/record/encoder.h create mode 100644 silo/record/inline_str.h create mode 100644 silo/record/serializer.h create mode 100755 silo/run.sh create mode 100644 silo/scopedperf.hh create mode 100755 silo/scripts/tester.py create mode 100755 silo/scripts/tester.sh create mode 100644 silo/small_unordered_map.h create mode 100644 silo/small_vector.h create mode 100644 silo/spinbarrier.h create mode 100644 silo/spinlock.h create mode 100644 silo/static_unordered_map.h create mode 100644 silo/static_vector.h create mode 100644 silo/stats_client.cc create mode 100644 silo/stats_common.h create mode 100644 silo/stats_server.cc create mode 100644 silo/stats_server.h create mode 100644 silo/str_arena.h create mode 100644 silo/test.cc create mode 100644 silo/third-party/lz4/LZ4 Streaming Format.odt create mode 100644 silo/third-party/lz4/Makefile create mode 100644 silo/third-party/lz4/bench.c create mode 100644 silo/third-party/lz4/bench.h create mode 100644 silo/third-party/lz4/cmake/CMakeLists.txt create mode 100644 silo/third-party/lz4/cmake/pack/CMakeLists.txt create mode 100644 silo/third-party/lz4/cmake/pack/release_COPYING.txt create mode 100644 silo/third-party/lz4/fullbench.c create mode 100644 silo/third-party/lz4/fuzzer.c create mode 100755 silo/third-party/lz4/liblz4.so create mode 100644 silo/third-party/lz4/lz4.c create mode 100644 silo/third-party/lz4/lz4.h create mode 100644 silo/third-party/lz4/lz4.o create mode 100644 silo/third-party/lz4/lz4_encoder.h create mode 100644 silo/third-party/lz4/lz4_format_description.txt create mode 100644 silo/third-party/lz4/lz4c.c create mode 100644 silo/third-party/lz4/lz4hc.c create mode 100644 silo/third-party/lz4/lz4hc.h create mode 100644 silo/third-party/lz4/lz4hc_encoder.h create mode 100644 silo/third-party/lz4/xxhash.c create mode 100644 silo/third-party/lz4/xxhash.h create mode 100644 silo/third-party/lz4/xxhash.o create mode 100644 silo/thread.cc create mode 100644 silo/thread.h create mode 100644 silo/ticker.cc create mode 100644 silo/ticker.h create mode 100644 silo/tuple.cc create mode 100644 silo/tuple.h create mode 100644 silo/txn.cc create mode 100644 silo/txn.h create mode 100644 silo/txn_btree.cc create mode 100644 silo/txn_btree.h create mode 100644 silo/txn_impl.h create mode 100644 silo/txn_proto2_impl.cc create mode 100644 silo/txn_proto2_impl.h create mode 100644 silo/typed_txn_btree.h create mode 100644 silo/util.h create mode 100644 silo/varint.cc create mode 100644 silo/varint.h create mode 100644 silo/varkey.h diff --git a/README.md b/README.md index f06a376..15958b3 100644 --- a/README.md +++ b/README.md @@ -12,3 +12,9 @@ Corresponding command for Ubuntu is included for convenience. 4. g++ Compiler that supports C++11 -- sudo apt-get install g++ + +5. packages for Silo + +sudo apt-get install libdb++-dev +sudo apt-get install libaio-dev +sudo apt-get install libjemalloc-dev diff --git a/silo/AUTHORS b/silo/AUTHORS new file mode 100644 index 0000000..e04ebfa --- /dev/null +++ b/silo/AUTHORS @@ -0,0 +1,8 @@ +Stephen Tu +stephentu@csail.mit.edu + +Wenting Zheng +wzheng@mit.edu + +Eddie Kohler +kohler@seas.harvard.edu diff --git a/silo/BUILD b/silo/BUILD new file mode 100644 index 0000000..719a9d0 --- /dev/null +++ b/silo/BUILD @@ -0,0 +1,18 @@ +Baseline: + +$ sudo apt-get install libnuma-dev + +To use with jemalloc: + +$ sudo apt-get install libjemalloc-dev + +Note that jemalloc2 has a bug which shows up in tests- make sure +to use jemalloc3 + +To use with tcmalloc: + +$ sudo apt-get install libgoogle-perftools-dev + +For benchmarks: + +$ sudo apt-get install libdb5.3++-dev libmysqld-dev libaio-dev diff --git a/silo/LICENSE b/silo/LICENSE new file mode 100644 index 0000000..dc1d496 --- /dev/null +++ b/silo/LICENSE @@ -0,0 +1,21 @@ +The MIT License (MIT) + +Copyright (C) 2013 Stephen Tu and other contributors + +Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal in +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies +of the Software, and to permit persons to whom the Software is furnished to do +so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/silo/Makefile b/silo/Makefile new file mode 100644 index 0000000..682b4cb --- /dev/null +++ b/silo/Makefile @@ -0,0 +1,279 @@ +-include config.mk + +### Options ### + +DEBUG ?= 0 +CHECK_INVARIANTS ?= 0 + +# 0 = libc malloc +# 1 = jemalloc +# 2 = tcmalloc +# 3 = flow +USE_MALLOC_MODE ?= 1 + +MYSQL ?= 1 +MYSQL_SHARE_DIR ?= /x/stephentu/mysql-5.5.29/build/sql/share + +# Available modes +# * perf +# * backoff +# * factor-gc +# * factor-gc-nowriteinplace +# * factor-fake-compression +# * sandbox +MODE ?= perf + +# run with 'MASSTREE=0' to turn off masstree +MASSTREE ?= 1 + +############### + +DEBUG_S=$(strip $(DEBUG)) +CHECK_INVARIANTS_S=$(strip $(CHECK_INVARIANTS)) +EVENT_COUNTERS_S=$(strip $(EVENT_COUNTERS)) +USE_MALLOC_MODE_S=$(strip $(USE_MALLOC_MODE)) +MODE_S=$(strip $(MODE)) +MASSTREE_S=$(strip $(MASSTREE)) +MASSTREE_CONFIG:=--enable-max-key-len=1024 + +ifeq ($(DEBUG_S),1) + OSUFFIX_D=.debug + MASSTREE_CONFIG+=--enable-assertions +else + MASSTREE_CONFIG+=--disable-assertions +endif +ifeq ($(CHECK_INVARIANTS_S),1) + OSUFFIX_S=.check + MASSTREE_CONFIG+=--enable-invariants --enable-preconditions +else + MASSTREE_CONFIG+=--disable-invariants --disable-preconditions +endif +ifeq ($(EVENT_COUNTERS_S),1) + OSUFFIX_E=.ectrs +endif +OSUFFIX=$(OSUFFIX_D)$(OSUFFIX_S)$(OSUFFIX_E) + +ifeq ($(MODE_S),perf) + O := out-perf$(OSUFFIX) + CONFIG_H = config/config-perf.h +else ifeq ($(MODE_S),backoff) + O := out-backoff$(OSUFFIX) + CONFIG_H = config/config-backoff.h +else ifeq ($(MODE_S),factor-gc) + O := out-factor-gc$(OSUFFIX) + CONFIG_H = config/config-factor-gc.h +else ifeq ($(MODE_S),factor-gc-nowriteinplace) + O := out-factor-gc-nowriteinplace$(OSUFFIX) + CONFIG_H = config/config-factor-gc-nowriteinplace.h +else ifeq ($(MODE_S),factor-fake-compression) + O := out-factor-fake-compression$(OSUFFIX) + CONFIG_H = config/config-factor-fake-compression.h +else ifeq ($(MODE_S),sandbox) + O := out-sandbox$(OSUFFIX) + CONFIG_H = config/config-sandbox.h +else + $(error invalid mode) +endif + +CXXFLAGS := -g -Wall -std=c++0x +CXXFLAGS += -MD -Ithird-party/lz4 -DCONFIG_H=\"$(CONFIG_H)\" +ifeq ($(DEBUG_S),1) + CXXFLAGS += -fno-omit-frame-pointer -DDEBUG +else + CXXFLAGS += -Werror -O2 -funroll-loops -fno-omit-frame-pointer +endif +ifeq ($(CHECK_INVARIANTS_S),1) + CXXFLAGS += -DCHECK_INVARIANTS +endif +ifeq ($(EVENT_COUNTERS_S),1) + CXXFLAGS += -DENABLE_EVENT_COUNTERS +endif +ifeq ($(MASSTREE_S),1) + CXXFLAGS += -DNDB_MASSTREE -include masstree/config.h + OBJDEP += masstree/config.h + O := $(O).masstree +else + O := $(O).silotree +endif + +TOP := $(shell echo $${PWD-`pwd`}) +LDFLAGS := -lpthread -lnuma -lrt + +LZ4LDFLAGS := -Lthird-party/lz4 -llz4 -Wl,-rpath,$(TOP)/third-party/lz4 + +ifeq ($(USE_MALLOC_MODE_S),1) + CXXFLAGS+=-DUSE_JEMALLOC + LDFLAGS+=-ljemalloc + MASSTREE_CONFIG+=--with-malloc=jemalloc +else ifeq ($(USE_MALLOC_MODE_S),2) + CXXFLAGS+=-DUSE_TCMALLOC + LDFLAGS+=-ltcmalloc + MASSTREE_CONFIG+=--with-malloc=tcmalloc +else ifeq ($(USE_MALLOC_MODE_S),3) + CXXFLAGS+=-DUSE_FLOW + LDFLAGS+=-lflow + MASSTREE_CONFIG+=--with-malloc=flow +else + MASSTREE_CONFIG+=--with-malloc=malloc +endif + +ifneq ($(strip $(CUSTOM_LDPATH)), ) + LDFLAGS+=$(CUSTOM_LDPATH) +endif + +SRCFILES = allocator.cc \ + btree.cc \ + core.cc \ + counter.cc \ + memory.cc \ + rcu.cc \ + stats_server.cc \ + thread.cc \ + ticker.cc \ + tuple.cc \ + txn_btree.cc \ + txn.cc \ + txn_proto2_impl.cc \ + varint.cc + +ifeq ($(MASSTREE_S),1) +MASSTREE_SRCFILES = masstree/compiler.cc \ + masstree/str.cc \ + masstree/string.cc \ + masstree/straccum.cc \ + masstree/json.cc +endif + +OBJFILES := $(patsubst %.cc, $(O)/%.o, $(SRCFILES)) + +MASSTREE_OBJFILES := $(patsubst masstree/%.cc, $(O)/%.o, $(MASSTREE_SRCFILES)) + +BENCH_CXXFLAGS := $(CXXFLAGS) +BENCH_LDFLAGS := $(LDFLAGS) -ldb_cxx -lz -lrt -lcrypt -laio -ldl -lssl -lcrypto + +BENCH_SRCFILES = benchmarks/bdb_wrapper.cc \ + benchmarks/bench.cc \ + benchmarks/encstress.cc \ + benchmarks/bid.cc \ + benchmarks/masstree/kvrandom.cc \ + benchmarks/queue.cc \ + benchmarks/tpcc.cc \ + benchmarks/ycsb.cc + +ifeq ($(MYSQL_S),1) +BENCH_CXXFLAGS += -DMYSQL_SHARE_DIR=\"$(MYSQL_SHARE_DIR)\" +BENCH_LDFLAGS := -L/usr/lib/mysql -lmysqld $(BENCH_LDFLAGS) +BENCH_SRCFILES += benchmarks/mysql_wrapper.cc +else +BENCH_CXXFLAGS += -DNO_MYSQL +endif + +BENCH_OBJFILES := $(patsubst %.cc, $(O)/%.o, $(BENCH_SRCFILES)) + +NEWBENCH_SRCFILES = new-benchmarks/bench.cc \ + new-benchmarks/tpcc.cc + +NEWBENCH_OBJFILES := $(patsubst %.cc, $(O)/%.o, $(NEWBENCH_SRCFILES)) + +all: $(O)/test + +$(O)/benchmarks/%.o: benchmarks/%.cc $(O)/buildstamp $(O)/buildstamp.bench $(OBJDEP) + @mkdir -p $(@D) + $(CXX) $(BENCH_CXXFLAGS) -c $< -o $@ + +$(O)/benchmarks/masstree/%.o: benchmarks/masstree/%.cc $(O)/buildstamp $(O)/buildstamp.bench $(OBJDEP) + @mkdir -p $(@D) + $(CXX) $(BENCH_CXXFLAGS) -c $< -o $@ + +$(O)/new-benchmarks/%.o: new-benchmarks/%.cc $(O)/buildstamp $(O)/buildstamp.bench $(OBJDEP) + @mkdir -p $(@D) + $(CXX) $(CXXFLAGS) -c $< -o $@ + +$(O)/%.o: %.cc $(O)/buildstamp $(OBJDEP) + @mkdir -p $(@D) + $(CXX) $(CXXFLAGS) -c $< -o $@ + +$(MASSTREE_OBJFILES) : $(O)/%.o: masstree/%.cc masstree/config.h + @mkdir -p $(@D) + $(CXX) $(CXXFLAGS) -include masstree/config.h -c $< -o $@ + +third-party/lz4/liblz4.so: + make -C third-party/lz4 library + +.PHONY: test +test: $(O)/test + +$(O)/test: $(O)/test.o $(OBJFILES) $(MASSTREE_OBJFILES) third-party/lz4/liblz4.so + $(CXX) -o $(O)/test $^ $(LDFLAGS) $(LZ4LDFLAGS) + +.PHONY: persist_test +persist_test: $(O)/persist_test + +$(O)/persist_test: $(O)/persist_test.o third-party/lz4/liblz4.so + $(CXX) -o $(O)/persist_test $(O)/persist_test.o $(LDFLAGS) $(LZ4LDFLAGS) + +.PHONY: stats_client +stats_client: $(O)/stats_client + +$(O)/stats_client: $(O)/stats_client.o + $(CXX) -o $(O)/stats_client $(O)/stats_client.o $(LDFLAGS) + +masstree/config.h: $(O)/buildstamp.masstree masstree/configure masstree/config.h.in + rm -f $@ + cd masstree; ./configure $(MASSTREE_CONFIG) + if test -f $@; then touch $@; fi + +masstree/configure masstree/config.h.in: masstree/configure.ac + cd masstree && autoreconf -i && touch configure config.h.in + +.PHONY: dbtest +dbtest: $(O)/benchmarks/dbtest + +$(O)/benchmarks/dbtest: $(O)/benchmarks/dbtest.o $(OBJFILES) $(MASSTREE_OBJFILES) $(BENCH_OBJFILES) third-party/lz4/liblz4.so + $(CXX) -o $(O)/benchmarks/dbtest $^ $(BENCH_LDFLAGS) $(LZ4LDFLAGS) + +.PHONY: kvtest +kvtest: $(O)/benchmarks/masstree/kvtest + +$(O)/benchmarks/masstree/kvtest: $(O)/benchmarks/masstree/kvtest.o $(OBJFILES) $(BENCH_OBJFILES) + $(CXX) -o $(O)/benchmarks/masstree/kvtest $^ $(BENCH_LDFLAGS) + +.PHONY: newdbtest +newdbtest: $(O)/new-benchmarks/dbtest + +$(O)/new-benchmarks/dbtest: $(O)/new-benchmarks/dbtest.o $(OBJFILES) $(MASSTREE_OBJFILES) $(NEWBENCH_OBJFILES) third-party/lz4/liblz4.so + $(CXX) -o $(O)/new-benchmarks/dbtest $^ $(LDFLAGS) $(LZ4LDFLAGS) + +DEPFILES := $(wildcard $(O)/*.d $(O)/*/*.d $(O)/*/*/*.d masstree/_masstree_config.d) +ifneq ($(DEPFILES),) +-include $(DEPFILES) +endif + +ifeq ($(wildcard masstree/GNUmakefile.in),) +INSTALL_MASSTREE := $(shell git submodule init; git submodule update) +endif + +ifeq ($(MASSTREE_S),1) +UPDATE_MASSTREE := $(shell cd ./`git rev-parse --show-cdup` && cur=`git submodule status --cached masstree | head -c 41 | tail -c +2` && if test -z `cd masstree; git rev-list -n1 $$cur^..HEAD 2>/dev/null`; then (echo Updating masstree... 1>&2; cd masstree; git checkout -f master >/dev/null; git pull; cd ..; git submodule update masstree); fi) +endif + +ifneq ($(strip $(DEBUG_S).$(CHECK_INVARIANTS_S).$(EVENT_COUNTERS_S)),$(strip $(DEP_MAIN_CONFIG))) +DEP_MAIN_CONFIG := $(shell mkdir -p $(O); echo >$(O)/buildstamp; echo "DEP_MAIN_CONFIG:=$(DEBUG_S).$(CHECK_INVARIANTS_S).$(EVENT_COUNTERS_S)" >$(O)/_main_config.d) +endif + +ifneq ($(strip $(MYSQL_S)),$(strip $(DEP_BENCH_CONFIG))) +DEP_BENCH_CONFIG := $(shell mkdir -p $(O); echo >$(O)/buildstamp.bench; echo "DEP_BENCH_CONFIG:=$(MYSQL_S)" >$(O)/_bench_config.d) +endif + +ifneq ($(strip $(MASSTREE_CONFIG)),$(strip $(DEP_MASSTREE_CONFIG))) +DEP_MASSTREE_CONFIG := $(shell mkdir -p $(O); echo >$(O)/buildstamp.masstree; echo "DEP_MASSTREE_CONFIG:=$(MASSTREE_CONFIG)" >masstree/_masstree_config.d) +endif + +$(O)/buildstamp $(O)/buildstamp.bench $(O)/buildstamp.masstree: + @mkdir -p $(@D) + @echo >$@ + +.PHONY: clean +clean: + rm -rf out-* + make -C third-party/lz4 clean diff --git a/silo/README.md b/silo/README.md new file mode 100644 index 0000000..04a68c9 --- /dev/null +++ b/silo/README.md @@ -0,0 +1,58 @@ +Silo +===== + +This project contains the prototype of the database system described in + + Speedy Transactions in Multicore In-Memory Databases + Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, Samuel Madden + SOSP 2013. + http://people.csail.mit.edu/stephentu/papers/silo.pdf + +This code is an ongoing work in progress. + +Build +----- + +There are several options to build. `MODE` is an important variable +governing the type of build. The default is `MODE=perf`, see the +Makefile for more options. `DEBUG=1` triggers a debug build (off by +default). `CHECK_INVARIANTS=1` enables invariant checking. There are +two targets: the default target which builds the test suite, and +`dbtest` which builds the benchmark suite. Examples: + + MODE=perf DEBUG=1 CHECK_INVARIANTS=1 make -j + MODE=perf make -j dbtest + +Each different combination of `MODE`, `DEBUG`, and `CHECK_INVARIANTS` triggers +a unique output directory; for example, the first command above builds to +`out-perf.debug.check.masstree`. + +Silo now uses [Masstree](https://github.com/kohler/masstree-beta) by default as +the default index tree. To use the old tree, set `MASSTREE=0`. + +Running +------- + +To run the tests, simply invoke `/test` with no arguments. To run the +benchmark suite, invoke `/benchmarks/dbtest`. For now, look in +`benchmarks/dbtest.cc` for documentation on the command line arguments. An +example invocation for TPC-C is: + + /benchmarks/dbtest \ + --verbose \ + --bench tpcc \ + --num-threads 28 \ + --scale-factor 28 \ + --runtime 30 \ + --numa-memory 112G + +Benchmarks +---------- + +To reproduce the graphs from the paper: + + $ cd benchmarks + $ python runner.py /unused-dir + +If you set `DRYRUN=True` in `runner.py`, then you get to see all the +commands that would be issued by the benchmark script. diff --git a/silo/allocator.cc b/silo/allocator.cc new file mode 100644 index 0000000..6c3067a --- /dev/null +++ b/silo/allocator.cc @@ -0,0 +1,376 @@ +#include +#include +#include +#include +#include +#include + +#include "allocator.h" +#include "spinlock.h" +#include "lockguard.h" +#include "static_vector.h" +#include "counter.h" + +using namespace util; + +static event_counter evt_allocator_total_region_usage( + "allocator_total_region_usage_bytes"); + +// page+alloc routines taken from masstree + +#ifdef MEMCHECK_MAGIC +const allocator::pgmetadata * +allocator::PointerToPgMetadata(const void *p) +{ + static const size_t hugepgsize = GetHugepageSize(); + if (unlikely(!ManagesPointer(p))) + return nullptr; + const size_t cpu = PointerToCpu(p); + const regionctx &pc = g_regions[cpu]; + if (p >= pc.region_begin) + return nullptr; + // round pg down to page + p = (const void *) ((uintptr_t)p & ~(hugepgsize-1)); + const pgmetadata *pmd = (const pgmetadata *) p; + ALWAYS_ASSERT((pmd->unit_ % AllocAlignment) == 0); + ALWAYS_ASSERT((MAX_ARENAS * AllocAlignment) >= pmd->unit_); + return pmd; +} +#endif + +size_t +allocator::GetHugepageSizeImpl() +{ + FILE *f = fopen("/proc/meminfo", "r"); + assert(f); + char *linep = NULL; + size_t n = 0; + static const char *key = "Hugepagesize:"; + static const int keylen = strlen(key); + size_t size = 0; + while (getline(&linep, &n, f) > 0) { + if (strstr(linep, key) != linep) + continue; + size = atol(linep + keylen) * 1024; + break; + } + fclose(f); + assert(size); + return size; +} + +size_t +allocator::GetPageSizeImpl() +{ + return sysconf(_SC_PAGESIZE); +} + +bool +allocator::UseMAdvWillNeed() +{ + static const char *px = getenv("DISABLE_MADV_WILLNEED"); + static const std::string s = px ? to_lower(px) : ""; + static const bool use_madv = !(s == "1" || s == "true"); + return use_madv; +} + +void +allocator::Initialize(size_t ncpus, size_t maxpercore) +{ + static spinlock s_lock; + static bool s_init = false; + if (likely(s_init)) + return; + lock_guard l(s_lock); + if (s_init) + return; + ALWAYS_ASSERT(!g_memstart); + ALWAYS_ASSERT(!g_memend); + ALWAYS_ASSERT(!g_ncpus); + ALWAYS_ASSERT(!g_maxpercore); + + static const size_t hugepgsize = GetHugepageSize(); + + // round maxpercore to the nearest hugepagesize + maxpercore = slow_round_up(maxpercore, hugepgsize); + + g_ncpus = ncpus; + g_maxpercore = maxpercore; + + // mmap() the entire region for now, but just as a marker + // (this does not actually cause physical pages to be allocated) + // note: we allocate an extra hugepgsize so we can guarantee alignment + // of g_memstart to a huge page boundary + + void * const x = mmap(nullptr, g_ncpus * g_maxpercore + hugepgsize, + PROT_NONE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); + if (x == MAP_FAILED) { + perror("mmap"); + ALWAYS_ASSERT(false); + } + + void * const endpx = (void *) ((uintptr_t)x + g_ncpus * g_maxpercore + hugepgsize); + std::cerr << "allocator::Initialize()" << std::endl + << " hugepgsize: " << hugepgsize << std::endl + << " use MADV_WILLNEED: " << UseMAdvWillNeed() << std::endl + << " mmap() region [" << x << ", " << endpx << ")" << std::endl; + + g_memstart = reinterpret_cast(util::iceil(uintptr_t(x), hugepgsize)); + g_memend = reinterpret_cast(g_memstart) + (g_ncpus * g_maxpercore); + + ALWAYS_ASSERT(!(reinterpret_cast(g_memstart) % hugepgsize)); + ALWAYS_ASSERT(reinterpret_cast(g_memend) <= + (reinterpret_cast(x) + (g_ncpus * g_maxpercore + hugepgsize))); + + for (size_t i = 0; i < g_ncpus; i++) { + g_regions[i].region_begin = + reinterpret_cast(g_memstart) + (i * g_maxpercore); + g_regions[i].region_end = + reinterpret_cast(g_memstart) + ((i + 1) * g_maxpercore); + std::cerr << "cpu" << i << " owns [" << g_regions[i].region_begin + << ", " << g_regions[i].region_end << ")" << std::endl; + ALWAYS_ASSERT(g_regions[i].region_begin < g_regions[i].region_end); + ALWAYS_ASSERT(g_regions[i].region_begin >= x); + ALWAYS_ASSERT(g_regions[i].region_end <= endpx); + } + + s_init = true; +} + +void +allocator::DumpStats() +{ + std::cerr << "[allocator] ncpus=" << g_ncpus << std::endl; + for (size_t i = 0; i < g_ncpus; i++) { + const bool f = g_regions[i].region_faulted; + const size_t remaining = + intptr_t(g_regions[i].region_end) - + intptr_t(g_regions[i].region_begin); + std::cerr << "[allocator] cpu=" << i << " fully_faulted?=" << f + << " remaining=" << remaining << " bytes" << std::endl; + } +} + +static void * +initialize_page(void *page, const size_t pagesize, const size_t unit) +{ + INVARIANT(((uintptr_t)page % pagesize) == 0); + +#ifdef MEMCHECK_MAGIC + ::allocator::pgmetadata *pmd = (::allocator::pgmetadata *) page; + pmd->unit_ = unit; + page = (void *) ((uintptr_t)page + sizeof(*pmd)); +#endif + + void *first = (void *)util::iceil((uintptr_t)page, (uintptr_t)unit); + INVARIANT((uintptr_t)first + unit <= (uintptr_t)page + pagesize); + void **p = (void **)first; + void *next = (void *)((uintptr_t)p + unit); + while ((uintptr_t)next + unit <= (uintptr_t)page + pagesize) { + INVARIANT(((uintptr_t)p % unit) == 0); + *p = next; +#ifdef MEMCHECK_MAGIC + NDB_MEMSET( + (char *) p + sizeof(void **), + MEMCHECK_MAGIC, unit - sizeof(void **)); +#endif + p = (void **)next; + next = (void *)((uintptr_t)next + unit); + } + INVARIANT(((uintptr_t)p % unit) == 0); + *p = NULL; +#ifdef MEMCHECK_MAGIC + NDB_MEMSET( + (char *) p + sizeof(void **), + MEMCHECK_MAGIC, unit - sizeof(void **)); +#endif + return first; +} + +void * +allocator::AllocateArenas(size_t cpu, size_t arena) +{ + INVARIANT(cpu < g_ncpus); + INVARIANT(arena < MAX_ARENAS); + INVARIANT(g_memstart); + INVARIANT(g_maxpercore); + static const size_t hugepgsize = GetHugepageSize(); + + regionctx &pc = g_regions[cpu]; + pc.lock.lock(); + if (likely(pc.arenas[arena])) { + // claim + void *ret = pc.arenas[arena]; + pc.arenas[arena] = nullptr; + pc.lock.unlock(); + return ret; + } + + void * const mypx = AllocateUnmanagedWithLock(pc, 1); // releases lock + return initialize_page(mypx, hugepgsize, (arena + 1) * AllocAlignment); +} + +void * +allocator::AllocateUnmanaged(size_t cpu, size_t nhugepgs) +{ + regionctx &pc = g_regions[cpu]; + pc.lock.lock(); + return AllocateUnmanagedWithLock(pc, nhugepgs); // releases lock +} + +void * +allocator::AllocateUnmanagedWithLock(regionctx &pc, size_t nhugepgs) +{ + static const size_t hugepgsize = GetHugepageSize(); + + void * const mypx = pc.region_begin; + + // check alignment + if (reinterpret_cast(mypx) % hugepgsize) + ALWAYS_ASSERT(false); + + void * const mynewpx = + reinterpret_cast(mypx) + nhugepgs * hugepgsize; + + if (unlikely(mynewpx > pc.region_end)) { + std::cerr << "allocator::AllocateUnmanagedWithLock():" << std::endl + << " region ending at " << pc.region_end << " OOM" << std::endl; + ALWAYS_ASSERT(false); // out of memory otherwise + } + + const bool needs_mmap = !pc.region_faulted; + pc.region_begin = mynewpx; + pc.lock.unlock(); + + evt_allocator_total_region_usage.inc(nhugepgs * hugepgsize); + + if (needs_mmap) { + void * const x = mmap(mypx, hugepgsize, PROT_READ | PROT_WRITE, + MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1, 0); + if (unlikely(x == MAP_FAILED)) { + perror("mmap"); + ALWAYS_ASSERT(false); + } + INVARIANT(x == mypx); + const int advice = + UseMAdvWillNeed() ? MADV_HUGEPAGE | MADV_WILLNEED : MADV_HUGEPAGE; + if (madvise(x, hugepgsize, advice)) { + perror("madvise"); + ALWAYS_ASSERT(false); + } + } + + return mypx; +} + +void +allocator::ReleaseArenas(void **arenas) +{ + // cpu -> [(head, tail)] + // XXX: use a small_map here? + std::map, MAX_ARENAS>> m; + for (size_t arena = 0; arena < MAX_ARENAS; arena++) { + void *p = arenas[arena]; + while (p) { + void * const pnext = *reinterpret_cast(p); + const size_t cpu = PointerToCpu(p); + auto it = m.find(cpu); + if (it == m.end()) { + auto &v = m[cpu]; + v.resize(MAX_ARENAS); + *reinterpret_cast(p) = nullptr; + v[arena].first = v[arena].second = p; + } else { + auto &v = it->second; + if (!v[arena].second) { + *reinterpret_cast(p) = nullptr; + v[arena].first = v[arena].second = p; + } else { + *reinterpret_cast(p) = v[arena].first; + v[arena].first = p; + } + } + p = pnext; + } + } + for (auto &p : m) { + INVARIANT(!p.second.empty()); + regionctx &pc = g_regions[p.first]; + lock_guard l(pc.lock); + for (size_t arena = 0; arena < MAX_ARENAS; arena++) { + INVARIANT(bool(p.second[arena].first) == bool(p.second[arena].second)); + if (!p.second[arena].first) + continue; + *reinterpret_cast(p.second[arena].second) = pc.arenas[arena]; + pc.arenas[arena] = p.second[arena].first; + } + } +} + +static void +numa_hint_memory_placement(void *px, size_t sz, unsigned node) +{ + struct bitmask *bm = numa_allocate_nodemask(); + numa_bitmask_setbit(bm, node); + numa_interleave_memory(px, sz, bm); + numa_free_nodemask(bm); +} + +void +allocator::FaultRegion(size_t cpu) +{ + static const size_t hugepgsize = GetHugepageSize(); + ALWAYS_ASSERT(cpu < g_ncpus); + regionctx &pc = g_regions[cpu]; + if (pc.region_faulted) + return; + lock_guard l1(pc.fault_lock); + lock_guard l(pc.lock); // exclude other users of the allocator + if (pc.region_faulted) + return; + // mmap the entire region + memset it for faulting + if (reinterpret_cast(pc.region_begin) % hugepgsize) + ALWAYS_ASSERT(false); + const size_t sz = + reinterpret_cast(pc.region_end) - + reinterpret_cast(pc.region_begin); + void * const x = mmap(pc.region_begin, sz, PROT_READ | PROT_WRITE, + MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1, 0); + if (unlikely(x == MAP_FAILED)) { + perror("mmap"); + std::cerr << " cpu" << cpu + << " [" << pc.region_begin << ", " << pc.region_end << ")" + << std::endl; + ALWAYS_ASSERT(false); + } + ALWAYS_ASSERT(x == pc.region_begin); + const int advice = + UseMAdvWillNeed() ? MADV_HUGEPAGE | MADV_WILLNEED : MADV_HUGEPAGE; + if (madvise(x, sz, advice)) { + perror("madvise"); + ALWAYS_ASSERT(false); + } + numa_hint_memory_placement( + pc.region_begin, + (uintptr_t)pc.region_end - (uintptr_t)pc.region_begin, + numa_node_of_cpu(cpu)); + const size_t nfaults = + ((uintptr_t)pc.region_end - (uintptr_t)pc.region_begin) / hugepgsize; + std::cerr << "cpu" << cpu << " starting faulting region (" + << intptr_t(pc.region_end) - intptr_t(pc.region_begin) + << " bytes / " << nfaults << " hugepgs)" << std::endl; + timer t; + for (char *px = (char *) pc.region_begin; + px < (char *) pc.region_end; + px += CACHELINE_SIZE) + *px = 0xDE; + std::cerr << "cpu" << cpu << " finished faulting region in " + << t.lap_ms() << " ms" << std::endl; + pc.region_faulted = true; +} + +void *allocator::g_memstart = nullptr; +void *allocator::g_memend = nullptr; +size_t allocator::g_ncpus = 0; +size_t allocator::g_maxpercore = 0; +percore allocator::g_regions; diff --git a/silo/allocator.h b/silo/allocator.h new file mode 100644 index 0000000..266e686 --- /dev/null +++ b/silo/allocator.h @@ -0,0 +1,145 @@ +#ifndef _NDB_ALLOCATOR_H_ +#define _NDB_ALLOCATOR_H_ + +#include +#include +#include + +#include "util.h" +#include "core.h" +#include "macros.h" +#include "spinlock.h" + +class allocator { +public: + + // our allocator doesn't let allocations exceed maxpercore over a single core + // + // Initialize can be called many times- but only the first call has effect. + // + // w/o calling Initialize(), behavior for this class is undefined + static void Initialize(size_t ncpus, size_t maxpercore); + + static void DumpStats(); + + // returns an arena linked-list + static void * + AllocateArenas(size_t cpu, size_t sz); + + // allocates nhugepgs * hugepagesize contiguous bytes from CPU's region and + // returns the raw, unmanaged pointer. + // + // Note that memory returned from here cannot be released back to the + // allocator, so this should only be used for data structures which live + // throughput the duration of the system (ie log buffers) + static void * + AllocateUnmanaged(size_t cpu, size_t nhugepgs); + + static void + ReleaseArenas(void **arenas); + + static const size_t LgAllocAlignment = 4; // all allocations aligned to 2^4 = 16 + static const size_t AllocAlignment = 1 << LgAllocAlignment; + static const size_t MAX_ARENAS = 32; + + static inline std::pair + ArenaSize(size_t sz) + { + const size_t allocsz = util::round_up(sz); + const size_t arena = allocsz / AllocAlignment - 1; + return std::make_pair(allocsz, arena); + } + + // slow, but only needs to be called on initialization + static void + FaultRegion(size_t cpu); + + // returns true if managed by this allocator, false otherwise + static inline bool + ManagesPointer(const void *p) + { + return p >= g_memstart && p < g_memend; + } + + // assumes p is managed by this allocator- returns the CPU from which this pointer + // was allocated + static inline size_t + PointerToCpu(const void *p) + { + ALWAYS_ASSERT(p >= g_memstart); + ALWAYS_ASSERT(p < g_memend); + const size_t ret = + (reinterpret_cast(p) - + reinterpret_cast(g_memstart)) / g_maxpercore; + ALWAYS_ASSERT(ret < g_ncpus); + return ret; + } + +#ifdef MEMCHECK_MAGIC + struct pgmetadata { + uint32_t unit_; // 0-indexed + } PACKED; + + // returns nullptr if p is not managed, or has not been allocated yet. + // p does not have to be properly aligned + static const pgmetadata * + PointerToPgMetadata(const void *p); +#endif + + static size_t + GetPageSize() + { + static const size_t sz = GetPageSizeImpl(); + return sz; + } + + static size_t + GetHugepageSize() + { + static const size_t sz = GetHugepageSizeImpl(); + return sz; + } + +private: + static size_t GetPageSizeImpl(); + static size_t GetHugepageSizeImpl(); + static bool UseMAdvWillNeed(); + + struct regionctx { + regionctx() + : region_begin(nullptr), + region_end(nullptr), + region_faulted(false) + { + NDB_MEMSET(arenas, 0, sizeof(arenas)); + } + regionctx(const regionctx &) = delete; + regionctx(regionctx &&) = delete; + regionctx &operator=(const regionctx &) = delete; + + // set by Initialize() + void *region_begin; + void *region_end; + + bool region_faulted; + + spinlock lock; + std::mutex fault_lock; // XXX: hacky + void *arenas[MAX_ARENAS]; + }; + + // assumes caller has the regionctx lock held, and + // will release the lock. + static void * + AllocateUnmanagedWithLock(regionctx &pc, size_t nhugepgs); + + // [g_memstart, g_memstart + ncpus * maxpercore) is the region of memory mmap()-ed + static void *g_memstart; + static void *g_memend; // g_memstart + ncpus * maxpercore + static size_t g_ncpus; + static size_t g_maxpercore; + + static percore g_regions CACHE_ALIGNED; +}; + +#endif /* _NDB_ALLOCATOR_H_ */ diff --git a/silo/amd64.h b/silo/amd64.h new file mode 100644 index 0000000..6a8c673 --- /dev/null +++ b/silo/amd64.h @@ -0,0 +1,21 @@ +#ifndef _AMD64_H_ +#define _AMD64_H_ + +#include "macros.h" +#include + +inline ALWAYS_INLINE void +nop_pause() +{ + __asm volatile("pause" : :); +} + +inline ALWAYS_INLINE uint64_t +rdtsc(void) +{ + uint32_t hi, lo; + __asm volatile("rdtsc" : "=a"(lo), "=d"(hi)); + return ((uint64_t)lo)|(((uint64_t)hi)<<32); +} + +#endif /* _AMD64_H_ */ diff --git a/silo/base_txn_btree.h b/silo/base_txn_btree.h new file mode 100644 index 0000000..8a38dd8 --- /dev/null +++ b/silo/base_txn_btree.h @@ -0,0 +1,495 @@ +#ifndef _NDB_BASE_TXN_BTREE_H_ +#define _NDB_BASE_TXN_BTREE_H_ + +#include "btree_choice.h" +#include "txn.h" +#include "lockguard.h" +#include "util.h" +#include "ndb_type_traits.h" + +#include +#include +#include +#include + +// each Transaction implementation should specialize this for special +// behavior- the default implementation is just nops +template