1 //===-- sanitizer_stackdepot.cpp ------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file is shared between AddressSanitizer and ThreadSanitizer 10 // run-time libraries. 11 //===----------------------------------------------------------------------===// 12 13 #include "sanitizer_stackdepot.h" 14 15 #include "sanitizer_common.h" 16 #include "sanitizer_hash.h" 17 #include "sanitizer_persistent_allocator.h" 18 #include "sanitizer_stackdepotbase.h" 19 20 namespace __sanitizer { 21 22 static PersistentAllocator<uptr> traceAllocator; 23 24 struct StackDepotNode { 25 using hash_type = u64; 26 hash_type stack_hash; 27 u32 link; 28 atomic_uint32_t tag_and_use_count; // tag : 12 high bits; use_count : 20; 29 30 static const u32 kTabSizeLog = SANITIZER_ANDROID ? 16 : 20; 31 static const u32 kUseCountBits = 20; 32 static const u32 kMaxUseCount = 1 << kUseCountBits; 33 static const u32 kUseCountMask = (1 << kUseCountBits) - 1; 34 35 typedef StackTrace args_type; 36 bool eq(hash_type hash, const args_type &args) const { 37 return hash == stack_hash; 38 } 39 static uptr allocated() { return traceAllocator.allocated(); } 40 static hash_type hash(const args_type &args) { 41 MurMur2Hash64Builder H(args.size * sizeof(uptr)); 42 for (uptr i = 0; i < args.size; i++) H.add(args.trace[i]); 43 H.add(args.tag); 44 return H.get(); 45 } 46 static bool is_valid(const args_type &args) { 47 return args.size > 0 && args.trace; 48 } 49 void store(u32 id, const args_type &args, hash_type hash); 50 args_type load(u32 id) const; 51 static StackDepotHandle get_handle(u32 id); 52 53 typedef StackDepotHandle handle_type; 54 }; 55 56 COMPILER_CHECK(StackDepotNode::kMaxUseCount >= (u32)kStackDepotMaxUseCount); 57 58 int StackDepotHandle::use_count() const { 59 return atomic_load(&node_->tag_and_use_count, memory_order_relaxed) & 60 StackDepotNode::kUseCountMask; 61 } 62 void StackDepotHandle::inc_use_count_unsafe() { 63 u32 prev = 64 atomic_fetch_add(&node_->tag_and_use_count, 1, memory_order_relaxed) & 65 StackDepotNode::kUseCountMask; 66 CHECK_LT(prev + 1, StackDepotNode::kMaxUseCount); 67 } 68 69 // FIXME(dvyukov): this single reserved bit is used in TSan. 70 typedef StackDepotBase<StackDepotNode, 1, StackDepotNode::kTabSizeLog> 71 StackDepot; 72 static StackDepot theDepot; 73 // Keep rarely accessed stack traces out of frequently access nodes to improve 74 // caching efficiency. 75 static TwoLevelMap<uptr *, StackDepot::kNodesSize1, StackDepot::kNodesSize2> 76 tracePtrs; 77 78 void StackDepotNode::store(u32 id, const args_type &args, hash_type hash) { 79 CHECK_EQ(args.tag & (~kUseCountMask >> kUseCountBits), args.tag); 80 atomic_store(&tag_and_use_count, args.tag << kUseCountBits, 81 memory_order_relaxed); 82 stack_hash = hash; 83 uptr *stack_trace = traceAllocator.alloc(args.size + 1); 84 *stack_trace = args.size; 85 internal_memcpy(stack_trace + 1, args.trace, args.size * sizeof(uptr)); 86 tracePtrs[id] = stack_trace; 87 } 88 89 StackDepotNode::args_type StackDepotNode::load(u32 id) const { 90 const uptr *stack_trace = tracePtrs[id]; 91 if (!stack_trace) 92 return {}; 93 u32 tag = 94 atomic_load(&tag_and_use_count, memory_order_relaxed) >> kUseCountBits; 95 return args_type(stack_trace + 1, *stack_trace, tag); 96 } 97 98 StackDepotStats StackDepotGetStats() { return theDepot.GetStats(); } 99 100 u32 StackDepotPut(StackTrace stack) { return theDepot.Put(stack); } 101 102 StackDepotHandle StackDepotPut_WithHandle(StackTrace stack) { 103 return StackDepotNode::get_handle(theDepot.Put(stack)); 104 } 105 106 StackTrace StackDepotGet(u32 id) { 107 return theDepot.Get(id); 108 } 109 110 void StackDepotLockAll() { 111 theDepot.LockAll(); 112 } 113 114 void StackDepotUnlockAll() { 115 theDepot.UnlockAll(); 116 } 117 118 void StackDepotPrintAll() { 119 #if !SANITIZER_GO 120 theDepot.PrintAll(); 121 #endif 122 } 123 124 StackDepotHandle StackDepotNode::get_handle(u32 id) { 125 return StackDepotHandle(&theDepot.nodes[id], id); 126 } 127 128 } // namespace __sanitizer 129