12d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===-- sanitizer_addrhashmap.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// Concurrent uptr->T hashmap. 112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===----------------------------------------------------------------------===// 132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#ifndef SANITIZER_ADDRHASHMAP_H 152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#define SANITIZER_ADDRHASHMAP_H 162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_common.h" 182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_mutex.h" 192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_atomic.h" 202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_allocator_internal.h" 212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesnamespace __sanitizer { 232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Concurrent uptr->T hashmap. 252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// T must be a POD type, kSize is preferably a prime but can be any number. 262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Usage example: 272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// typedef AddrHashMap<uptr, 11> Map; 292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Map m; 302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// { 312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Map::Handle h(&m, addr); 322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// use h.operator->() to access the data 332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// if h.created() then the element was just created, and the current thread 342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// has exclusive access to it 352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// otherwise the current thread has only read access to the data 362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// } 372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// { 382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Map::Handle h(&m, addr, true); 392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// this will remove the data from the map in Handle dtor 402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// the current thread has exclusive access to the data 412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// if !h.exists() then the element never existed 422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// } 432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate<typename T, uptr kSize> 442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesclass AddrHashMap { 452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines private: 462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines struct Cell { 472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_uintptr_t addr; 482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines T val; 492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines }; 502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines struct AddBucket { 522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr cap; 532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr size; 542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Cell cells[1]; // variable len 552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines }; 562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines static const uptr kBucketSize = 3; 582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines struct Bucket { 602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RWMutex mtx; 612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_uintptr_t add; 622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Cell cells[kBucketSize]; 632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines }; 642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines public: 662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines AddrHashMap(); 672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines class Handle { 692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines public: 702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Handle(AddrHashMap<T, kSize> *map, uptr addr); 712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Handle(AddrHashMap<T, kSize> *map, uptr addr, bool remove); 722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Handle(AddrHashMap<T, kSize> *map, uptr addr, bool remove, bool create); 732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ~Handle(); 752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines T *operator->(); 762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool created() const; 772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool exists() const; 782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines private: 802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines friend AddrHashMap<T, kSize>; 812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines AddrHashMap<T, kSize> *map_; 822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Bucket *bucket_; 832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Cell *cell_; 842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr addr_; 852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr addidx_; 862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool created_; 872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool remove_; 882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool create_; 892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines }; 902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines private: 922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines friend class Handle; 932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Bucket *table_; 942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void acquire(Handle *h); 962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void release(Handle *h); 972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr calcHash(uptr addr); 982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines}; 992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate<typename T, uptr kSize> 1012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesAddrHashMap<T, kSize>::Handle::Handle(AddrHashMap<T, kSize> *map, uptr addr) { 1022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines map_ = map; 1032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines addr_ = addr; 1042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines remove_ = false; 1052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines create_ = true; 1062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines map_->acquire(this); 1072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate<typename T, uptr kSize> 1102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesAddrHashMap<T, kSize>::Handle::Handle(AddrHashMap<T, kSize> *map, uptr addr, 1112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool remove) { 1122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines map_ = map; 1132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines addr_ = addr; 1142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines remove_ = remove; 1152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines create_ = true; 1162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines map_->acquire(this); 1172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate<typename T, uptr kSize> 1202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesAddrHashMap<T, kSize>::Handle::Handle(AddrHashMap<T, kSize> *map, uptr addr, 1212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool remove, bool create) { 1222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines map_ = map; 1232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines addr_ = addr; 1242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines remove_ = remove; 1252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines create_ = create; 1262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines map_->acquire(this); 1272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate<typename T, uptr kSize> 1302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesAddrHashMap<T, kSize>::Handle::~Handle() { 1312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines map_->release(this); 1322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <typename T, uptr kSize> 1352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesT *AddrHashMap<T, kSize>::Handle::operator->() { 1362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return &cell_->val; 1372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate<typename T, uptr kSize> 1402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesbool AddrHashMap<T, kSize>::Handle::created() const { 1412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return created_; 1422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate<typename T, uptr kSize> 1452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesbool AddrHashMap<T, kSize>::Handle::exists() const { 1462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return cell_ != 0; 1472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate<typename T, uptr kSize> 1502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesAddrHashMap<T, kSize>::AddrHashMap() { 1512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines table_ = (Bucket*)MmapOrDie(kSize * sizeof(table_[0]), "AddrHashMap"); 1522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate<typename T, uptr kSize> 1552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid AddrHashMap<T, kSize>::acquire(Handle *h) { 1562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr addr = h->addr_; 1572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr hash = calcHash(addr); 1582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Bucket *b = &table_[hash]; 1592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h->created_ = false; 1612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h->addidx_ = -1U; 1622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h->bucket_ = b; 1632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h->cell_ = 0; 1642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // If we want to remove the element, we need exclusive access to the bucket, 1662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // so skip the lock-free phase. 1672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (h->remove_) 1682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines goto locked; 1692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines retry: 1712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // First try to find an existing element w/o read mutex. 1722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK(!h->remove_); 1732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Check the embed cells. 1742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < kBucketSize; i++) { 1752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Cell *c = &b->cells[i]; 1762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr addr1 = atomic_load(&c->addr, memory_order_acquire); 1772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (addr1 == addr) { 1782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h->cell_ = c; 1792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return; 1802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Check the add cells with read lock. 1842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (atomic_load(&b->add, memory_order_relaxed)) { 1852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines b->mtx.ReadLock(); 1862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines AddBucket *add = (AddBucket*)atomic_load(&b->add, memory_order_relaxed); 1872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < add->size; i++) { 1882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Cell *c = &add->cells[i]; 1892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr addr1 = atomic_load(&c->addr, memory_order_relaxed); 1902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (addr1 == addr) { 1912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h->addidx_ = i; 1922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h->cell_ = c; 1932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return; 1942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines b->mtx.ReadUnlock(); 1972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines locked: 2002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Re-check existence under write lock. 2012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Embed cells. 2022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines b->mtx.Lock(); 2032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < kBucketSize; i++) { 2042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Cell *c = &b->cells[i]; 2052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr addr1 = atomic_load(&c->addr, memory_order_relaxed); 2062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (addr1 == addr) { 2072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (h->remove_) { 2082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h->cell_ = c; 2092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return; 2102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines b->mtx.Unlock(); 2122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines goto retry; 2132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Add cells. 2172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines AddBucket *add = (AddBucket*)atomic_load(&b->add, memory_order_relaxed); 2182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (add) { 2192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < add->size; i++) { 2202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Cell *c = &add->cells[i]; 2212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr addr1 = atomic_load(&c->addr, memory_order_relaxed); 2222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (addr1 == addr) { 2232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (h->remove_) { 2242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h->addidx_ = i; 2252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h->cell_ = c; 2262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return; 2272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines b->mtx.Unlock(); 2292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines goto retry; 2302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // The element does not exist, no need to create it if we want to remove. 2352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (h->remove_ || !h->create_) { 2362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines b->mtx.Unlock(); 2372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return; 2382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Now try to create it under the mutex. 2412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h->created_ = true; 2422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // See if we have a free embed cell. 2432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < kBucketSize; i++) { 2442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Cell *c = &b->cells[i]; 2452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr addr1 = atomic_load(&c->addr, memory_order_relaxed); 2462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (addr1 == 0) { 2472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h->cell_ = c; 2482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return; 2492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Store in the add cells. 2532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (add == 0) { 2542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Allocate a new add array. 2552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines const uptr kInitSize = 64; 2562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines add = (AddBucket*)InternalAlloc(kInitSize); 2572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines internal_memset(add, 0, kInitSize); 2582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines add->cap = (kInitSize - sizeof(*add)) / sizeof(add->cells[0]) + 1; 2592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines add->size = 0; 2602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_store(&b->add, (uptr)add, memory_order_relaxed); 2612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (add->size == add->cap) { 2632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Grow existing add array. 2642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr oldsize = sizeof(*add) + (add->cap - 1) * sizeof(add->cells[0]); 2652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr newsize = oldsize * 2; 2662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines AddBucket *add1 = (AddBucket*)InternalAlloc(newsize); 2672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines internal_memset(add1, 0, newsize); 2682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines add1->cap = (newsize - sizeof(*add)) / sizeof(add->cells[0]) + 1; 2692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines add1->size = add->size; 2702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines internal_memcpy(add1->cells, add->cells, add->size * sizeof(add->cells[0])); 2712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines InternalFree(add); 2722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_store(&b->add, (uptr)add1, memory_order_relaxed); 2732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines add = add1; 2742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Store. 2762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i = add->size++; 2772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Cell *c = &add->cells[i]; 2782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_EQ(atomic_load(&c->addr, memory_order_relaxed), 0); 2792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h->addidx_ = i; 2802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines h->cell_ = c; 2812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 2822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate<typename T, uptr kSize> 2842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid AddrHashMap<T, kSize>::release(Handle *h) { 2852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (h->cell_ == 0) 2862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return; 2872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Bucket *b = h->bucket_; 2882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Cell *c = h->cell_; 2892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr addr1 = atomic_load(&c->addr, memory_order_relaxed); 2902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (h->created_) { 2912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Denote completion of insertion. 2922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_EQ(addr1, 0); 2932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // After the following store, the element becomes available 2942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // for lock-free reads. 2952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_store(&c->addr, h->addr_, memory_order_release); 2962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines b->mtx.Unlock(); 2972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } else if (h->remove_) { 2982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Denote that the cell is empty now. 2992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_EQ(addr1, h->addr_); 3002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_store(&c->addr, 0, memory_order_release); 3012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // See if we need to compact the bucket. 3022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines AddBucket *add = (AddBucket*)atomic_load(&b->add, memory_order_relaxed); 3032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (h->addidx_ == -1U) { 3042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Removed from embed array, move an add element into the freed cell. 3052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (add && add->size != 0) { 3062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr last = --add->size; 3072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Cell *c1 = &add->cells[last]; 3082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines c->val = c1->val; 3092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr addr1 = atomic_load(&c1->addr, memory_order_relaxed); 3102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_store(&c->addr, addr1, memory_order_release); 3112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_store(&c1->addr, 0, memory_order_release); 3122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } else { 3142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Removed from add array, compact it. 3152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr last = --add->size; 3162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Cell *c1 = &add->cells[last]; 3172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (c != c1) { 3182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines *c = *c1; 3192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines atomic_store(&c1->addr, 0, memory_order_relaxed); 3202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (add && add->size == 0) { 3232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // FIXME(dvyukov): free add? 3242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines b->mtx.Unlock(); 3262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } else { 3272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_EQ(addr1, h->addr_); 3282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (h->addidx_ != -1U) 3292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines b->mtx.ReadUnlock(); 3302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 3322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate<typename T, uptr kSize> 3342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesuptr AddrHashMap<T, kSize>::calcHash(uptr addr) { 3352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines addr += addr << 10; 3362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines addr ^= addr >> 6; 3372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return addr % kSize; 3382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 3392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} // namespace __sanitizer 3412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#endif // SANITIZER_ADDRHASHMAP_H 343