12d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===-- msan_chained_origin_depot.cc -----------------------------------===// 22d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 32d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// The LLVM Compiler Infrastructure 42d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 52d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// This file is distributed under the University of Illinois Open Source 62d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// License. See LICENSE.TXT for details. 72d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 82d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===----------------------------------------------------------------------===// 92d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// A storage for chained origins. 112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===----------------------------------------------------------------------===// 122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "msan_chained_origin_depot.h" 142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_common/sanitizer_stackdepotbase.h" 162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesnamespace __msan { 182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesstruct ChainedOriginDepotDesc { 202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 here_id; 212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 prev_id; 226d1862363c88c183b0ed7740fca876342cf0474bStephen Hines}; 236d1862363c88c183b0ed7740fca876342cf0474bStephen Hines 246d1862363c88c183b0ed7740fca876342cf0474bStephen Hinesstruct ChainedOriginDepotNode { 256d1862363c88c183b0ed7740fca876342cf0474bStephen Hines ChainedOriginDepotNode *link; 266d1862363c88c183b0ed7740fca876342cf0474bStephen Hines u32 id; 276d1862363c88c183b0ed7740fca876342cf0474bStephen Hines u32 here_id; 286d1862363c88c183b0ed7740fca876342cf0474bStephen Hines u32 prev_id; 296d1862363c88c183b0ed7740fca876342cf0474bStephen Hines 306d1862363c88c183b0ed7740fca876342cf0474bStephen Hines typedef ChainedOriginDepotDesc args_type; 316d1862363c88c183b0ed7740fca876342cf0474bStephen Hines bool eq(u32 hash, const args_type &args) const { 326d1862363c88c183b0ed7740fca876342cf0474bStephen Hines return here_id == args.here_id && prev_id == args.prev_id; 336d1862363c88c183b0ed7740fca876342cf0474bStephen Hines } 346d1862363c88c183b0ed7740fca876342cf0474bStephen Hines static uptr storage_size(const args_type &args) { 356d1862363c88c183b0ed7740fca876342cf0474bStephen Hines return sizeof(ChainedOriginDepotNode); 366d1862363c88c183b0ed7740fca876342cf0474bStephen Hines } 376d1862363c88c183b0ed7740fca876342cf0474bStephen Hines /* This is murmur2 hash for the 64->32 bit case. 386d1862363c88c183b0ed7740fca876342cf0474bStephen Hines It does not behave all that well because the keys have a very biased 396d1862363c88c183b0ed7740fca876342cf0474bStephen Hines distribution (I've seen 7-element buckets with the table only 14% full). 406d1862363c88c183b0ed7740fca876342cf0474bStephen Hines 416d1862363c88c183b0ed7740fca876342cf0474bStephen Hines here_id is built of 426d1862363c88c183b0ed7740fca876342cf0474bStephen Hines * (1 bits) Reserved, zero. 436d1862363c88c183b0ed7740fca876342cf0474bStephen Hines * (8 bits) Part id = bits 13..20 of the hash value of here_id's key. 446d1862363c88c183b0ed7740fca876342cf0474bStephen Hines * (23 bits) Sequential number (each part has each own sequence). 456d1862363c88c183b0ed7740fca876342cf0474bStephen Hines 466d1862363c88c183b0ed7740fca876342cf0474bStephen Hines prev_id has either the same distribution as here_id (but with 3:8:21) 476d1862363c88c183b0ed7740fca876342cf0474bStephen Hines split, or one of two reserved values (-1) or (-2). Either case can 486d1862363c88c183b0ed7740fca876342cf0474bStephen Hines dominate depending on the workload. 496d1862363c88c183b0ed7740fca876342cf0474bStephen Hines */ 506d1862363c88c183b0ed7740fca876342cf0474bStephen Hines static u32 hash(const args_type &args) { 516a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines const u32 m = 0x5bd1e995; 526a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines const u32 seed = 0x9747b28c; 536a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines const u32 r = 24; 546a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines u32 h = seed; 556d1862363c88c183b0ed7740fca876342cf0474bStephen Hines u32 k = args.here_id; 566a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines k *= m; 576a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines k ^= k >> r; 586a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines k *= m; 596a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines h *= m; 606a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines h ^= k; 616a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines 626d1862363c88c183b0ed7740fca876342cf0474bStephen Hines k = args.prev_id; 636a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines k *= m; 646a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines k ^= k >> r; 656a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines k *= m; 666a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines h *= m; 676a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines h ^= k; 686a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines 696a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines h ^= h >> 13; 706a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines h *= m; 716a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines h ^= h >> 15; 726a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines return h; 736a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines } 746d1862363c88c183b0ed7740fca876342cf0474bStephen Hines static bool is_valid(const args_type &args) { return true; } 752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void store(const args_type &args, u32 other_hash) { 762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines here_id = args.here_id; 772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines prev_id = args.prev_id; 782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines args_type load() const { 802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines args_type ret = {here_id, prev_id}; 812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return ret; 822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines struct Handle { 842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ChainedOriginDepotNode *node_; 852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Handle() : node_(0) {} 862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines explicit Handle(ChainedOriginDepotNode *node) : node_(node) {} 872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool valid() { return node_; } 882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 id() { return node_->id; } 892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines int here_id() { return node_->here_id; } 902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines int prev_id() { return node_->prev_id; } 912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines }; 922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Handle get_handle() { return Handle(this); } 932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines typedef Handle handle_type; 952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines}; 962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 9786277eb844c4983c81de62d7c050e92fe7155788Stephen Hinesstatic StackDepotBase<ChainedOriginDepotNode, 4, 20> chainedOriginDepot; 982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesStackDepotStats *ChainedOriginDepotGetStats() { 1002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return chainedOriginDepot.GetStats(); 1012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesbool ChainedOriginDepotPut(u32 here_id, u32 prev_id, u32 *new_id) { 1042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ChainedOriginDepotDesc desc = {here_id, prev_id}; 1052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool inserted; 1062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ChainedOriginDepotNode::Handle h = chainedOriginDepot.Put(desc, &inserted); 1072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines *new_id = h.valid() ? h.id() : 0; 1082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return inserted; 1092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Retrieves a stored stack trace by the id. 1122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesu32 ChainedOriginDepotGet(u32 id, u32 *other) { 1132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ChainedOriginDepotDesc desc = chainedOriginDepot.Get(id); 1142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines *other = desc.prev_id; 1152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return desc.here_id; 1162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1186d1862363c88c183b0ed7740fca876342cf0474bStephen Hinesvoid ChainedOriginDepotLockAll() { 1196d1862363c88c183b0ed7740fca876342cf0474bStephen Hines chainedOriginDepot.LockAll(); 1206d1862363c88c183b0ed7740fca876342cf0474bStephen Hines} 1216d1862363c88c183b0ed7740fca876342cf0474bStephen Hines 1226d1862363c88c183b0ed7740fca876342cf0474bStephen Hinesvoid ChainedOriginDepotUnlockAll() { 1236d1862363c88c183b0ed7740fca876342cf0474bStephen Hines chainedOriginDepot.UnlockAll(); 1246d1862363c88c183b0ed7740fca876342cf0474bStephen Hines} 1256d1862363c88c183b0ed7740fca876342cf0474bStephen Hines 1262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} // namespace __msan 127