12d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===-- sanitizer_stackdepotbase.h ------------------------------*- C++ -*-===// 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// Implementation of a mapping from arbitrary values to unique 32-bit 112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// identifiers. 122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===----------------------------------------------------------------------===// 132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#ifndef SANITIZER_STACKDEPOTBASE_H 142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#define SANITIZER_STACKDEPOTBASE_H 152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_internal_defs.h" 172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_mutex.h" 182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_atomic.h" 192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_persistent_allocator.h" 202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesnamespace __sanitizer { 222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 235d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinestemplate <class Node, int kReservedBits, int kTabSizeLog> 242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesclass StackDepotBase { 252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines public: 262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines typedef typename Node::args_type args_type; 272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines typedef typename Node::handle_type handle_type; 282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Maps stack trace to an unique id. 292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines handle_type Put(args_type args, bool *inserted = 0); 302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Retrieves a stored stack trace by the id. 312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines args_type Get(u32 id); 322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StackDepotStats *GetStats() { return &stats; } 342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines private: 362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines static Node *find(Node *s, args_type args, u32 hash); 372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines static Node *lock(atomic_uintptr_t *p); 382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines static void unlock(atomic_uintptr_t *p, Node *s); 392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 405d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines static const int kTabSize = 1 << kTabSizeLog; // Hash table size. 412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines static const int kPartBits = 8; 422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines static const int kPartShift = sizeof(u32) * 8 - kPartBits - kReservedBits; 432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines static const int kPartCount = 442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1 << kPartBits; // Number of subparts in the table. 452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines static const int kPartSize = kTabSize / kPartCount; 462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines static const int kMaxId = 1 << kPartShift; 472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_uintptr_t tab[kTabSize]; // Hash table of Node's. 492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_uint32_t seq[kPartCount]; // Unique id generators. 502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines StackDepotStats stats; 522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines friend class StackDepotReverseMap; 542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines}; 552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 565d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinestemplate <class Node, int kReservedBits, int kTabSizeLog> 575d71de26cedae3dafc17449fe0182045c0bd20e8Stephen HinesNode *StackDepotBase<Node, kReservedBits, kTabSizeLog>::find(Node *s, 585d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines args_type args, 595d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines u32 hash) { 602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Searches linked list s for the stack, returns its id. 612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (; s; s = s->link) { 622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (s->eq(hash, args)) { 632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return s; 642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return 0; 672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 695d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinestemplate <class Node, int kReservedBits, int kTabSizeLog> 705d71de26cedae3dafc17449fe0182045c0bd20e8Stephen HinesNode *StackDepotBase<Node, kReservedBits, kTabSizeLog>::lock( 715d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines atomic_uintptr_t *p) { 722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Uses the pointer lsb as mutex. 732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (int i = 0;; i++) { 742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr cmp = atomic_load(p, memory_order_relaxed); 752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if ((cmp & 1) == 0 && 762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_compare_exchange_weak(p, &cmp, cmp | 1, memory_order_acquire)) 772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return (Node *)cmp; 782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (i < 10) 792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines proc_yield(10); 802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines else 812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines internal_sched_yield(); 822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 855d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinestemplate <class Node, int kReservedBits, int kTabSizeLog> 865d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinesvoid StackDepotBase<Node, kReservedBits, kTabSizeLog>::unlock( 875d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines atomic_uintptr_t *p, Node *s) { 882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DCHECK_EQ((uptr)s & 1, 0); 892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_store(p, (uptr)s, memory_order_release); 902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 925d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinestemplate <class Node, int kReservedBits, int kTabSizeLog> 935d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinestypename StackDepotBase<Node, kReservedBits, kTabSizeLog>::handle_type 945d71de26cedae3dafc17449fe0182045c0bd20e8Stephen HinesStackDepotBase<Node, kReservedBits, kTabSizeLog>::Put(args_type args, 955d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines bool *inserted) { 962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (inserted) *inserted = false; 972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!args.is_valid()) return handle_type(); 982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr h = args.hash(); 992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_uintptr_t *p = &tab[h % kTabSize]; 1002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr v = atomic_load(p, memory_order_consume); 1012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Node *s = (Node *)(v & ~1); 1022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // First, try to find the existing stack. 1032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Node *node = find(s, args, h); 1042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (node) return node->get_handle(); 1052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // If failed, lock, retry and insert new. 1062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Node *s2 = lock(p); 1072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (s2 != s) { 1082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines node = find(s2, args, h); 1092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (node) { 1102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines unlock(p, s2); 1112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return node->get_handle(); 1122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr part = (h % kTabSize) / kPartSize; 1152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 id = atomic_fetch_add(&seq[part], 1, memory_order_relaxed) + 1; 1162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines stats.n_uniq_ids++; 1172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_LT(id, kMaxId); 1182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines id |= part << kPartShift; 1192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_NE(id, 0); 1202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_EQ(id & (((u32)-1) >> kReservedBits), id); 1212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr memsz = Node::storage_size(args); 1222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines s = (Node *)PersistentAlloc(memsz); 1232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines stats.allocated += memsz; 1242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines s->id = id; 1252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines s->store(args, h); 1262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines s->link = s2; 1272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines unlock(p, s); 1282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (inserted) *inserted = true; 1292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return s->get_handle(); 1302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1325d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinestemplate <class Node, int kReservedBits, int kTabSizeLog> 1335d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hinestypename StackDepotBase<Node, kReservedBits, kTabSizeLog>::args_type 1345d71de26cedae3dafc17449fe0182045c0bd20e8Stephen HinesStackDepotBase<Node, kReservedBits, kTabSizeLog>::Get(u32 id) { 1352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (id == 0) { 1362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return args_type(); 1372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_EQ(id & (((u32)-1) >> kReservedBits), id); 1392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // High kPartBits contain part id, so we need to scan at most kPartSize lists. 1402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr part = id >> kPartShift; 1412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (int i = 0; i != kPartSize; i++) { 1422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr idx = part * kPartSize + i; 1432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_LT(idx, kTabSize); 1442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_uintptr_t *p = &tab[idx]; 1452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr v = atomic_load(p, memory_order_consume); 1462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Node *s = (Node *)(v & ~1); 1472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (; s; s = s->link) { 1482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (s->id == id) { 1492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return s->load(); 1502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return args_type(); 1542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1565d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines} // namespace __sanitizer 1572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#endif // SANITIZER_STACKDEPOTBASE_H 158