aboutsummaryrefslogtreecommitdiffstats
path: root/lib/msan/msan_chained_origin_depot.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/msan/msan_chained_origin_depot.cpp')
-rw-r--r--lib/msan/msan_chained_origin_depot.cpp131
1 files changed, 131 insertions, 0 deletions
diff --git a/lib/msan/msan_chained_origin_depot.cpp b/lib/msan/msan_chained_origin_depot.cpp
new file mode 100644
index 000000000000..d2897481a4b9
--- /dev/null
+++ b/lib/msan/msan_chained_origin_depot.cpp
@@ -0,0 +1,131 @@
+//===-- msan_chained_origin_depot.cpp ----------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// A storage for chained origins.
+//===----------------------------------------------------------------------===//
+
+#include "msan_chained_origin_depot.h"
+
+#include "sanitizer_common/sanitizer_stackdepotbase.h"
+
+namespace __msan {
+
+struct ChainedOriginDepotDesc {
+ u32 here_id;
+ u32 prev_id;
+};
+
+struct ChainedOriginDepotNode {
+ ChainedOriginDepotNode *link;
+ u32 id;
+ u32 here_id;
+ u32 prev_id;
+
+ typedef ChainedOriginDepotDesc args_type;
+
+ bool eq(u32 hash, const args_type &args) const {
+ return here_id == args.here_id && prev_id == args.prev_id;
+ }
+
+ static uptr storage_size(const args_type &args) {
+ return sizeof(ChainedOriginDepotNode);
+ }
+
+ /* This is murmur2 hash for the 64->32 bit case.
+ It does not behave all that well because the keys have a very biased
+ distribution (I've seen 7-element buckets with the table only 14% full).
+
+ here_id is built of
+ * (1 bits) Reserved, zero.
+ * (8 bits) Part id = bits 13..20 of the hash value of here_id's key.
+ * (23 bits) Sequential number (each part has each own sequence).
+
+ prev_id has either the same distribution as here_id (but with 3:8:21)
+ split, or one of two reserved values (-1) or (-2). Either case can
+ dominate depending on the workload.
+ */
+ static u32 hash(const args_type &args) {
+ const u32 m = 0x5bd1e995;
+ const u32 seed = 0x9747b28c;
+ const u32 r = 24;
+ u32 h = seed;
+ u32 k = args.here_id;
+ k *= m;
+ k ^= k >> r;
+ k *= m;
+ h *= m;
+ h ^= k;
+
+ k = args.prev_id;
+ k *= m;
+ k ^= k >> r;
+ k *= m;
+ h *= m;
+ h ^= k;
+
+ h ^= h >> 13;
+ h *= m;
+ h ^= h >> 15;
+ return h;
+ }
+ static bool is_valid(const args_type &args) { return true; }
+ void store(const args_type &args, u32 other_hash) {
+ here_id = args.here_id;
+ prev_id = args.prev_id;
+ }
+
+ args_type load() const {
+ args_type ret = {here_id, prev_id};
+ return ret;
+ }
+
+ struct Handle {
+ ChainedOriginDepotNode *node_;
+ Handle() : node_(nullptr) {}
+ explicit Handle(ChainedOriginDepotNode *node) : node_(node) {}
+ bool valid() { return node_; }
+ u32 id() { return node_->id; }
+ int here_id() { return node_->here_id; }
+ int prev_id() { return node_->prev_id; }
+ };
+
+ Handle get_handle() { return Handle(this); }
+
+ typedef Handle handle_type;
+};
+
+static StackDepotBase<ChainedOriginDepotNode, 4, 20> chainedOriginDepot;
+
+StackDepotStats *ChainedOriginDepotGetStats() {
+ return chainedOriginDepot.GetStats();
+}
+
+bool ChainedOriginDepotPut(u32 here_id, u32 prev_id, u32 *new_id) {
+ ChainedOriginDepotDesc desc = {here_id, prev_id};
+ bool inserted;
+ ChainedOriginDepotNode::Handle h = chainedOriginDepot.Put(desc, &inserted);
+ *new_id = h.valid() ? h.id() : 0;
+ return inserted;
+}
+
+// Retrieves a stored stack trace by the id.
+u32 ChainedOriginDepotGet(u32 id, u32 *other) {
+ ChainedOriginDepotDesc desc = chainedOriginDepot.Get(id);
+ *other = desc.prev_id;
+ return desc.here_id;
+}
+
+void ChainedOriginDepotLockAll() {
+ chainedOriginDepot.LockAll();
+}
+
+void ChainedOriginDepotUnlockAll() {
+ chainedOriginDepot.UnlockAll();
+}
+
+} // namespace __msan