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