1//===-- sanitizer_allocator_bytemap.h ---------------------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// Part of the Sanitizer Allocator. 11// 12//===----------------------------------------------------------------------===// 13#ifndef SANITIZER_ALLOCATOR_H 14#error This file must be included inside sanitizer_allocator.h 15#endif 16 17// Maps integers in rage [0, kSize) to u8 values. 18template <u64 kSize, typename AddressSpaceViewTy = LocalAddressSpaceView> 19class FlatByteMap { 20 public: 21 using AddressSpaceView = AddressSpaceViewTy; 22 void Init() { 23 internal_memset(map_, 0, sizeof(map_)); 24 } 25 26 void set(uptr idx, u8 val) { 27 CHECK_LT(idx, kSize); 28 CHECK_EQ(0U, map_[idx]); 29 map_[idx] = val; 30 } 31 u8 operator[] (uptr idx) { 32 CHECK_LT(idx, kSize); 33 // FIXME: CHECK may be too expensive here. 34 return map_[idx]; 35 } 36 private: 37 u8 map_[kSize]; 38}; 39 40// TwoLevelByteMap maps integers in range [0, kSize1*kSize2) to u8 values. 41// It is implemented as a two-dimensional array: array of kSize1 pointers 42// to kSize2-byte arrays. The secondary arrays are mmaped on demand. 43// Each value is initially zero and can be set to something else only once. 44// Setting and getting values from multiple threads is safe w/o extra locking. 45template <u64 kSize1, u64 kSize2, 46 typename AddressSpaceViewTy = LocalAddressSpaceView, 47 class MapUnmapCallback = NoOpMapUnmapCallback> 48class TwoLevelByteMap { 49 public: 50 using AddressSpaceView = AddressSpaceViewTy; 51 void Init() { 52 internal_memset(map1_, 0, sizeof(map1_)); 53 mu_.Init(); 54 } 55 56 void TestOnlyUnmap() { 57 for (uptr i = 0; i < kSize1; i++) { 58 u8 *p = Get(i); 59 if (!p) continue; 60 MapUnmapCallback().OnUnmap(reinterpret_cast<uptr>(p), kSize2); 61 UnmapOrDie(p, kSize2); 62 } 63 } 64 65 uptr size() const { return kSize1 * kSize2; } 66 uptr size1() const { return kSize1; } 67 uptr size2() const { return kSize2; } 68 69 void set(uptr idx, u8 val) { 70 CHECK_LT(idx, kSize1 * kSize2); 71 u8 *map2 = GetOrCreate(idx / kSize2); 72 CHECK_EQ(0U, map2[idx % kSize2]); 73 map2[idx % kSize2] = val; 74 } 75 76 u8 operator[] (uptr idx) const { 77 CHECK_LT(idx, kSize1 * kSize2); 78 u8 *map2 = Get(idx / kSize2); 79 if (!map2) return 0; 80 auto value_ptr = AddressSpaceView::Load(&map2[idx % kSize2]); 81 return *value_ptr; 82 } 83 84 private: 85 u8 *Get(uptr idx) const { 86 CHECK_LT(idx, kSize1); 87 return reinterpret_cast<u8 *>( 88 atomic_load(&map1_[idx], memory_order_acquire)); 89 } 90 91 u8 *GetOrCreate(uptr idx) { 92 u8 *res = Get(idx); 93 if (!res) { 94 SpinMutexLock l(&mu_); 95 if (!(res = Get(idx))) { 96 res = (u8*)MmapOrDie(kSize2, "TwoLevelByteMap"); 97 MapUnmapCallback().OnMap(reinterpret_cast<uptr>(res), kSize2); 98 atomic_store(&map1_[idx], reinterpret_cast<uptr>(res), 99 memory_order_release); 100 } 101 } 102 return res; 103 } 104 105 atomic_uintptr_t map1_[kSize1]; 106 StaticSpinMutex mu_; 107}; 108 109