diff --git a/compiler-rt/lib/msan/msan_chained_origin_depot.h b/compiler-rt/lib/msan/msan_chained_origin_depot.h --- a/compiler-rt/lib/msan/msan_chained_origin_depot.h +++ b/compiler-rt/lib/msan/msan_chained_origin_depot.h @@ -1,4 +1,4 @@ -//===-- msan_chained_origin_depot.h --------------------------*- C++ -*-===// +//===-- msan_chained_origin_depot.h -----------------------------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -6,8 +6,11 @@ // //===----------------------------------------------------------------------===// // +// This file is a part of MemorySanitizer. +// // A storage for chained origins. //===----------------------------------------------------------------------===// + #ifndef MSAN_CHAINED_ORIGIN_DEPOT_H #define MSAN_CHAINED_ORIGIN_DEPOT_H @@ -15,9 +18,16 @@ namespace __msan { +// Gets the statistic of the origin chain storage. StackDepotStats *ChainedOriginDepotGetStats(); + +// Stores a chain with StackDepot ID here_id and previous chain ID prev_id. +// If successful, returns true and the new chain id new_id. +// If the same element already exists, returns false and sets new_id to the +// existing ID. bool ChainedOriginDepotPut(u32 here_id, u32 prev_id, u32 *new_id); -// Retrieves a stored stack trace by the id. + +// Retrieves the stored StackDepot ID for the given origin ID. u32 ChainedOriginDepotGet(u32 id, u32 *other); void ChainedOriginDepotLockAll(); diff --git a/compiler-rt/lib/msan/msan_chained_origin_depot.cpp b/compiler-rt/lib/msan/msan_chained_origin_depot.cpp --- a/compiler-rt/lib/msan/msan_chained_origin_depot.cpp +++ b/compiler-rt/lib/msan/msan_chained_origin_depot.cpp @@ -1,4 +1,4 @@ -//===-- msan_chained_origin_depot.cpp ----------------------------------===// +//===-- 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. @@ -6,118 +6,29 @@ // //===----------------------------------------------------------------------===// // +// This file is a part of MemorySanitizer. +// // A storage for chained origins. //===----------------------------------------------------------------------===// #include "msan_chained_origin_depot.h" -#include "sanitizer_common/sanitizer_stackdepotbase.h" +#include "sanitizer_common/sanitizer_chained_origin_depot.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 chainedOriginDepot; +static ChainedOriginDepot 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; + return chainedOriginDepot.Put(here_id, prev_id, new_id); } -// 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; + return chainedOriginDepot.Get(id, other); } void ChainedOriginDepotLockAll() { diff --git a/compiler-rt/lib/sanitizer_common/CMakeLists.txt b/compiler-rt/lib/sanitizer_common/CMakeLists.txt --- a/compiler-rt/lib/sanitizer_common/CMakeLists.txt +++ b/compiler-rt/lib/sanitizer_common/CMakeLists.txt @@ -73,6 +73,7 @@ set(SANITIZER_SYMBOLIZER_SOURCES sanitizer_allocator_report.cpp + sanitizer_chained_origin_depot.cpp sanitizer_stackdepot.cpp sanitizer_stacktrace.cpp sanitizer_stacktrace_libcdep.cpp @@ -119,6 +120,7 @@ sanitizer_atomic_msvc.h sanitizer_bitvector.h sanitizer_bvgraph.h + sanitizer_chained_origin_depot.h sanitizer_common.h sanitizer_common_interceptors.inc sanitizer_common_interceptors_format.inc diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.h b/compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.h new file mode 100644 --- /dev/null +++ b/compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.h @@ -0,0 +1,88 @@ +//===-- sanitizer_chained_origin_depot.h ------------------------*- C++ -*-===// +// +// 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. +//===----------------------------------------------------------------------===// + +#ifndef SANITIZER_CHAINED_ORIGIN_DEPOT_H +#define SANITIZER_CHAINED_ORIGIN_DEPOT_H + +#include "sanitizer_common.h" +#include "sanitizer_stackdepotbase.h" + +namespace __sanitizer { + +class ChainedOriginDepot { + public: + ChainedOriginDepot(); + + // Gets the statistic of the origin chain storage. + StackDepotStats *GetStats(); + + // Stores a chain with StackDepot ID here_id and previous chain ID prev_id. + // If successful, returns true and the new chain id new_id. + // If the same element already exists, returns false and sets new_id to the + // existing ID. + bool Put(u32 here_id, u32 prev_id, u32 *new_id); + + // Retrieves the stored StackDepot ID for the given origin ID. + u32 Get(u32 id, u32 *other); + + void LockAll(); + void UnlockAll(); + + private: + 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; + + static uptr storage_size(const args_type &args); + + static u32 hash(const args_type &args); + + static bool is_valid(const args_type &args); + + void store(const args_type &args, u32 other_hash); + + args_type load() const; + + 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(); + + typedef Handle handle_type; + }; + + StackDepotBase depot; + + ChainedOriginDepot(const ChainedOriginDepot &) = delete; + void operator=(const ChainedOriginDepot &) = delete; +}; + +} // namespace __sanitizer + +#endif // SANITIZER_CHAINED_ORIGIN_DEPOT_H diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.cpp b/compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.cpp new file mode 100644 --- /dev/null +++ b/compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.cpp @@ -0,0 +1,108 @@ +//===-- sanitizer_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 "sanitizer_chained_origin_depot.h" + +namespace __sanitizer { + +bool ChainedOriginDepot::ChainedOriginDepotNode::eq( + u32 hash, const args_type &args) const { + return here_id == args.here_id && prev_id == args.prev_id; +} + +uptr ChainedOriginDepot::ChainedOriginDepotNode::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. +*/ +u32 ChainedOriginDepot::ChainedOriginDepotNode::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; +} + +bool ChainedOriginDepot::ChainedOriginDepotNode::is_valid( + const args_type &args) { + return true; +} + +void ChainedOriginDepot::ChainedOriginDepotNode::store(const args_type &args, + u32 other_hash) { + here_id = args.here_id; + prev_id = args.prev_id; +} + +ChainedOriginDepot::ChainedOriginDepotNode::args_type +ChainedOriginDepot::ChainedOriginDepotNode::load() const { + args_type ret = {here_id, prev_id}; + return ret; +} + +ChainedOriginDepot::ChainedOriginDepotNode::Handle +ChainedOriginDepot::ChainedOriginDepotNode::get_handle() { + return Handle(this); +} + +ChainedOriginDepot::ChainedOriginDepot() {} + +StackDepotStats *ChainedOriginDepot::GetStats() { return depot.GetStats(); } + +bool ChainedOriginDepot::Put(u32 here_id, u32 prev_id, u32 *new_id) { + ChainedOriginDepotDesc desc = {here_id, prev_id}; + bool inserted; + ChainedOriginDepotNode::Handle h = depot.Put(desc, &inserted); + *new_id = h.valid() ? h.id() : 0; + return inserted; +} + +u32 ChainedOriginDepot::Get(u32 id, u32 *other) { + ChainedOriginDepotDesc desc = depot.Get(id); + *other = desc.prev_id; + return desc.here_id; +} + +void ChainedOriginDepot::LockAll() { depot.LockAll(); } + +void ChainedOriginDepot::UnlockAll() { depot.UnlockAll(); } + +} // namespace __sanitizer diff --git a/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt b/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt --- a/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt +++ b/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt @@ -13,6 +13,7 @@ sanitizer_atomic_test.cpp sanitizer_bitvector_test.cpp sanitizer_bvgraph_test.cpp + sanitizer_chained_origin_depot_test.cpp sanitizer_common_test.cpp sanitizer_deadlock_detector_test.cpp sanitizer_flags_test.cpp diff --git a/compiler-rt/lib/sanitizer_common/tests/sanitizer_chained_origin_depot_test.cpp b/compiler-rt/lib/sanitizer_common/tests/sanitizer_chained_origin_depot_test.cpp new file mode 100644 --- /dev/null +++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_chained_origin_depot_test.cpp @@ -0,0 +1,90 @@ +//===-- sanitizer_chained_origin_depot_test.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 +// +//===----------------------------------------------------------------------===// +// +// This file is a part of Sanitizer runtime. +// Tests for sanitizer_chained_origin_depot.h. +// +//===----------------------------------------------------------------------===// + +#include "sanitizer_common/sanitizer_chained_origin_depot.h" + +#include "gtest/gtest.h" +#include "sanitizer_common/sanitizer_internal_defs.h" +#include "sanitizer_common/sanitizer_libc.h" + +namespace __sanitizer { + +static ChainedOriginDepot chainedOriginDepot; + +TEST(SanitizerCommon, ChainedOriginDepotBasic) { + u32 new_id; + EXPECT_TRUE(chainedOriginDepot.Put(1, 2, &new_id)); + u32 prev_id; + EXPECT_EQ(chainedOriginDepot.Get(new_id, &prev_id), 1U); + EXPECT_EQ(prev_id, 2U); +} + +TEST(SanitizerCommon, ChainedOriginDepotAbsent) { + u32 prev_id; + EXPECT_EQ(0U, chainedOriginDepot.Get(99, &prev_id)); + EXPECT_EQ(0U, prev_id); +} + +TEST(SanitizerCommon, ChainedOriginDepotZeroId) { + u32 prev_id; + EXPECT_EQ(0U, chainedOriginDepot.Get(0, &prev_id)); + EXPECT_EQ(0U, prev_id); +} + +TEST(SanitizerCommon, ChainedOriginDepotSame) { + u32 new_id1; + EXPECT_TRUE(chainedOriginDepot.Put(11, 12, &new_id1)); + u32 new_id2; + EXPECT_FALSE(chainedOriginDepot.Put(11, 12, &new_id2)); + EXPECT_EQ(new_id1, new_id2); + + u32 prev_id; + EXPECT_EQ(chainedOriginDepot.Get(new_id1, &prev_id), 11U); + EXPECT_EQ(prev_id, 12U); +} + +TEST(SanitizerCommon, ChainedOriginDepotDifferent) { + u32 new_id1; + EXPECT_TRUE(chainedOriginDepot.Put(21, 22, &new_id1)); + u32 new_id2; + EXPECT_TRUE(chainedOriginDepot.Put(21, 23, &new_id2)); + EXPECT_NE(new_id1, new_id2); + + u32 prev_id; + EXPECT_EQ(chainedOriginDepot.Get(new_id1, &prev_id), 21U); + EXPECT_EQ(prev_id, 22U); + EXPECT_EQ(chainedOriginDepot.Get(new_id2, &prev_id), 21U); + EXPECT_EQ(prev_id, 23U); +} + +TEST(SanitizerCommon, ChainedOriginDepotStats) { + StackDepotStats stats0 = *chainedOriginDepot.GetStats(); + + u32 new_id; + EXPECT_TRUE(chainedOriginDepot.Put(33, 34, &new_id)); + StackDepotStats stats1 = *chainedOriginDepot.GetStats(); + EXPECT_EQ(stats1.n_uniq_ids, stats0.n_uniq_ids + 1); + EXPECT_GT(stats1.allocated, stats0.allocated); + + EXPECT_FALSE(chainedOriginDepot.Put(33, 34, &new_id)); + StackDepotStats stats2 = *chainedOriginDepot.GetStats(); + EXPECT_EQ(stats2.n_uniq_ids, stats1.n_uniq_ids); + EXPECT_EQ(stats2.allocated, stats1.allocated); + + EXPECT_TRUE(chainedOriginDepot.Put(35, 36, &new_id)); + StackDepotStats stats3 = *chainedOriginDepot.GetStats(); + EXPECT_EQ(stats3.n_uniq_ids, stats2.n_uniq_ids + 1); + EXPECT_GT(stats3.allocated, stats2.allocated); +} + +} // namespace __sanitizer