contrib/compiler-rt/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>
  19 class FlatByteMap {
  20  public:
  21   void Init() {
  22     internal_memset(map_, 0, sizeof(map_));
  23   }
  24
  25   void set(uptr idx, u8 val) {
  26     CHECK_LT(idx, kSize);
  27     CHECK_EQ(0U, map_[idx]);
  28     map_[idx] = val;
  29   }
  30   u8 operator[] (uptr idx) {
  31     CHECK_LT(idx, kSize);
  32     // FIXME: CHECK may be too expensive here.
  33     return map_[idx];
  34   }
  35  private:
  36   u8 map_[kSize];
  37 };
  38
  39 // TwoLevelByteMap maps integers in range [0, kSize1*kSize2) to u8 values.
  40 // It is implemented as a two-dimensional array: array of kSize1 pointers
  41 // to kSize2-byte arrays. The secondary arrays are mmaped on demand.
  42 // Each value is initially zero and can be set to something else only once.
  43 // Setting and getting values from multiple threads is safe w/o extra locking.
  44 template <u64 kSize1, u64 kSize2, class MapUnmapCallback = NoOpMapUnmapCallback>
  45 class TwoLevelByteMap {
  46  public:
  47   void Init() {
  48     internal_memset(map1_, 0, sizeof(map1_));
  49     mu_.Init();
  50   }
  51
  52   void TestOnlyUnmap() {
  53     for (uptr i = 0; i < kSize1; i++) {
  54       u8 *p = Get(i);
  55       if (!p) continue;
  56       MapUnmapCallback().OnUnmap(reinterpret_cast<uptr>(p), kSize2);
  57       UnmapOrDie(p, kSize2);
  58     }
  59   }
  60
  61   uptr size() const { return kSize1 * kSize2; }
  62   uptr size1() const { return kSize1; }
  63   uptr size2() const { return kSize2; }
  64
  65   void set(uptr idx, u8 val) {
  66     CHECK_LT(idx, kSize1 * kSize2);
  67     u8 *map2 = GetOrCreate(idx / kSize2);
  68     CHECK_EQ(0U, map2[idx % kSize2]);
  69     map2[idx % kSize2] = val;
  70   }
  71
  72   u8 operator[] (uptr idx) const {
  73     CHECK_LT(idx, kSize1 * kSize2);
  74     u8 *map2 = Get(idx / kSize2);
  75     if (!map2) return 0;
  76     return map2[idx % kSize2];
  77   }
  78
  79  private:
  80   u8 *Get(uptr idx) const {
  81     CHECK_LT(idx, kSize1);
  82     return reinterpret_cast<u8 *>(
  83         atomic_load(&map1_[idx], memory_order_acquire));
  84   }
  85
  86   u8 *GetOrCreate(uptr idx) {
  87     u8 *res = Get(idx);
  88     if (!res) {
  89       SpinMutexLock l(&mu_);
  90       if (!(res = Get(idx))) {
  91         res = (u8*)MmapOrDie(kSize2, "TwoLevelByteMap");
  92         MapUnmapCallback().OnMap(reinterpret_cast<uptr>(res), kSize2);
  93         atomic_store(&map1_[idx], reinterpret_cast<uptr>(res),
  94                      memory_order_release);
  95       }
  96     }
  97     return res;
  98   }
  99
 100   atomic_uintptr_t map1_[kSize1];
 101   StaticSpinMutex mu_;
 102 };
 103