1353944Sdim//===-- sanitizer_stackdepot.cpp ------------------------------------------===// 2353944Sdim// 3353944Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353944Sdim// See https://llvm.org/LICENSE.txt for license information. 5353944Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6353944Sdim// 7353944Sdim//===----------------------------------------------------------------------===// 8353944Sdim// 9353944Sdim// This file is shared between AddressSanitizer and ThreadSanitizer 10353944Sdim// run-time libraries. 11353944Sdim//===----------------------------------------------------------------------===// 12353944Sdim 13353944Sdim#include "sanitizer_stackdepot.h" 14353944Sdim 15353944Sdim#include "sanitizer_common.h" 16353944Sdim#include "sanitizer_hash.h" 17353944Sdim#include "sanitizer_stackdepotbase.h" 18353944Sdim 19353944Sdimnamespace __sanitizer { 20353944Sdim 21353944Sdimstruct StackDepotNode { 22353944Sdim StackDepotNode *link; 23353944Sdim u32 id; 24353944Sdim atomic_uint32_t hash_and_use_count; // hash_bits : 12; use_count : 20; 25353944Sdim u32 size; 26353944Sdim u32 tag; 27353944Sdim uptr stack[1]; // [size] 28353944Sdim 29353944Sdim static const u32 kTabSizeLog = SANITIZER_ANDROID ? 16 : 20; 30353944Sdim // Lower kTabSizeLog bits are equal for all items in one bucket. 31353944Sdim // We use these bits to store the per-stack use counter. 32353944Sdim static const u32 kUseCountBits = kTabSizeLog; 33353944Sdim static const u32 kMaxUseCount = 1 << kUseCountBits; 34353944Sdim static const u32 kUseCountMask = (1 << kUseCountBits) - 1; 35353944Sdim static const u32 kHashMask = ~kUseCountMask; 36353944Sdim 37353944Sdim typedef StackTrace args_type; 38353944Sdim bool eq(u32 hash, const args_type &args) const { 39353944Sdim u32 hash_bits = 40353944Sdim atomic_load(&hash_and_use_count, memory_order_relaxed) & kHashMask; 41353944Sdim if ((hash & kHashMask) != hash_bits || args.size != size || args.tag != tag) 42353944Sdim return false; 43353944Sdim uptr i = 0; 44353944Sdim for (; i < size; i++) { 45353944Sdim if (stack[i] != args.trace[i]) return false; 46353944Sdim } 47353944Sdim return true; 48353944Sdim } 49353944Sdim static uptr storage_size(const args_type &args) { 50353944Sdim return sizeof(StackDepotNode) + (args.size - 1) * sizeof(uptr); 51353944Sdim } 52353944Sdim static u32 hash(const args_type &args) { 53353944Sdim MurMur2HashBuilder H(args.size * sizeof(uptr)); 54353944Sdim for (uptr i = 0; i < args.size; i++) H.add(args.trace[i]); 55353944Sdim return H.get(); 56353944Sdim } 57353944Sdim static bool is_valid(const args_type &args) { 58353944Sdim return args.size > 0 && args.trace; 59353944Sdim } 60353944Sdim void store(const args_type &args, u32 hash) { 61353944Sdim atomic_store(&hash_and_use_count, hash & kHashMask, memory_order_relaxed); 62353944Sdim size = args.size; 63353944Sdim tag = args.tag; 64353944Sdim internal_memcpy(stack, args.trace, size * sizeof(uptr)); 65353944Sdim } 66353944Sdim args_type load() const { 67353944Sdim return args_type(&stack[0], size, tag); 68353944Sdim } 69353944Sdim StackDepotHandle get_handle() { return StackDepotHandle(this); } 70353944Sdim 71353944Sdim typedef StackDepotHandle handle_type; 72353944Sdim}; 73353944Sdim 74353944SdimCOMPILER_CHECK(StackDepotNode::kMaxUseCount == (u32)kStackDepotMaxUseCount); 75353944Sdim 76353944Sdimu32 StackDepotHandle::id() { return node_->id; } 77353944Sdimint StackDepotHandle::use_count() { 78353944Sdim return atomic_load(&node_->hash_and_use_count, memory_order_relaxed) & 79353944Sdim StackDepotNode::kUseCountMask; 80353944Sdim} 81353944Sdimvoid StackDepotHandle::inc_use_count_unsafe() { 82353944Sdim u32 prev = 83353944Sdim atomic_fetch_add(&node_->hash_and_use_count, 1, memory_order_relaxed) & 84353944Sdim StackDepotNode::kUseCountMask; 85353944Sdim CHECK_LT(prev + 1, StackDepotNode::kMaxUseCount); 86353944Sdim} 87353944Sdim 88353944Sdim// FIXME(dvyukov): this single reserved bit is used in TSan. 89353944Sdimtypedef StackDepotBase<StackDepotNode, 1, StackDepotNode::kTabSizeLog> 90353944Sdim StackDepot; 91353944Sdimstatic StackDepot theDepot; 92353944Sdim 93353944SdimStackDepotStats *StackDepotGetStats() { 94353944Sdim return theDepot.GetStats(); 95353944Sdim} 96353944Sdim 97353944Sdimu32 StackDepotPut(StackTrace stack) { 98353944Sdim StackDepotHandle h = theDepot.Put(stack); 99353944Sdim return h.valid() ? h.id() : 0; 100353944Sdim} 101353944Sdim 102353944SdimStackDepotHandle StackDepotPut_WithHandle(StackTrace stack) { 103353944Sdim return theDepot.Put(stack); 104353944Sdim} 105353944Sdim 106353944SdimStackTrace StackDepotGet(u32 id) { 107353944Sdim return theDepot.Get(id); 108353944Sdim} 109353944Sdim 110353944Sdimvoid StackDepotLockAll() { 111353944Sdim theDepot.LockAll(); 112353944Sdim} 113353944Sdim 114353944Sdimvoid StackDepotUnlockAll() { 115353944Sdim theDepot.UnlockAll(); 116353944Sdim} 117353944Sdim 118353944Sdimbool StackDepotReverseMap::IdDescPair::IdComparator( 119353944Sdim const StackDepotReverseMap::IdDescPair &a, 120353944Sdim const StackDepotReverseMap::IdDescPair &b) { 121353944Sdim return a.id < b.id; 122353944Sdim} 123353944Sdim 124353944SdimStackDepotReverseMap::StackDepotReverseMap() { 125353944Sdim map_.reserve(StackDepotGetStats()->n_uniq_ids + 100); 126353944Sdim for (int idx = 0; idx < StackDepot::kTabSize; idx++) { 127353944Sdim atomic_uintptr_t *p = &theDepot.tab[idx]; 128353944Sdim uptr v = atomic_load(p, memory_order_consume); 129353944Sdim StackDepotNode *s = (StackDepotNode*)(v & ~1); 130353944Sdim for (; s; s = s->link) { 131353944Sdim IdDescPair pair = {s->id, s}; 132353944Sdim map_.push_back(pair); 133353944Sdim } 134353944Sdim } 135353944Sdim Sort(map_.data(), map_.size(), &IdDescPair::IdComparator); 136353944Sdim} 137353944Sdim 138353944SdimStackTrace StackDepotReverseMap::Get(u32 id) { 139353944Sdim if (!map_.size()) 140353944Sdim return StackTrace(); 141353944Sdim IdDescPair pair = {id, nullptr}; 142353944Sdim uptr idx = 143353944Sdim InternalLowerBound(map_, 0, map_.size(), pair, IdDescPair::IdComparator); 144353944Sdim if (idx > map_.size() || map_[idx].id != id) 145353944Sdim return StackTrace(); 146353944Sdim return map_[idx].desc->load(); 147353944Sdim} 148353944Sdim 149353944Sdim} // namespace __sanitizer 150