| //===-- 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 |