Home | History | Annotate | Line # | Download | only in sanitizer_common 
      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.
     18 template <u64 kSize, typename AddressSpaceViewTy = LocalAddressSpaceView>
     19 class 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.
     45 template <u64 kSize1, u64 kSize2,
     46           typename AddressSpaceViewTy = LocalAddressSpaceView,
     47           class MapUnmapCallback = NoOpMapUnmapCallback>
     48 class 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