lib/sanitizer_common/sanitizer_allocator_bytemap.h

   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