1//===-- sanitizer_allocator_secondary.h -------------------------*- C++ -*-===//
2//
3// This file is distributed under the University of Illinois Open Source
4// License. See LICENSE.TXT for details.
5//
6//===----------------------------------------------------------------------===//
7//
8// Part of the Sanitizer Allocator.
9//
10//===----------------------------------------------------------------------===//
11#ifndef SANITIZER_ALLOCATOR_H
12#error This file must be included inside sanitizer_allocator.h
13#endif
14
15// Fixed array to store LargeMmapAllocator chunks list, limited to 32K total
16// allocated chunks. To be used in memory constrained or not memory hungry cases
17// (currently, 32 bits and internal allocator).
18class LargeMmapAllocatorPtrArrayStatic {
19 public:
20  INLINE void *Init() { return &p_[0]; }
21  INLINE void EnsureSpace(uptr n) { CHECK_LT(n, kMaxNumChunks); }
22 private:
23  static const int kMaxNumChunks = 1 << 15;
24  uptr p_[kMaxNumChunks];
25};
26
27// Much less restricted LargeMmapAllocator chunks list (comparing to
28// PtrArrayStatic). Backed by mmaped memory region and can hold up to 1M chunks.
29// ReservedAddressRange was used instead of just MAP_NORESERVE to achieve the
30// same functionality in Fuchsia case, which does not support MAP_NORESERVE.
31class LargeMmapAllocatorPtrArrayDynamic {
32 public:
33  INLINE void *Init() {
34    uptr p = address_range_.Init(kMaxNumChunks * sizeof(uptr),
35                                 SecondaryAllocatorName);
36    CHECK(p);
37    return reinterpret_cast<void*>(p);
38  }
39
40  INLINE void EnsureSpace(uptr n) {
41    CHECK_LT(n, kMaxNumChunks);
42    DCHECK(n <= n_reserved_);
43    if (UNLIKELY(n == n_reserved_)) {
44      address_range_.MapOrDie(
45          reinterpret_cast<uptr>(address_range_.base()) +
46              n_reserved_ * sizeof(uptr),
47          kChunksBlockCount * sizeof(uptr));
48      n_reserved_ += kChunksBlockCount;
49    }
50  }
51
52 private:
53  static const int kMaxNumChunks = 1 << 20;
54  static const int kChunksBlockCount = 1 << 14;
55  ReservedAddressRange address_range_;
56  uptr n_reserved_;
57};
58
59#if SANITIZER_WORDSIZE == 32
60typedef LargeMmapAllocatorPtrArrayStatic DefaultLargeMmapAllocatorPtrArray;
61#else
62typedef LargeMmapAllocatorPtrArrayDynamic DefaultLargeMmapAllocatorPtrArray;
63#endif
64
65// This class can (de)allocate only large chunks of memory using mmap/unmap.
66// The main purpose of this allocator is to cover large and rare allocation
67// sizes not covered by more efficient allocators (e.g. SizeClassAllocator64).
68template <class MapUnmapCallback = NoOpMapUnmapCallback,
69          class PtrArrayT = DefaultLargeMmapAllocatorPtrArray>
70class LargeMmapAllocator {
71 public:
72  void InitLinkerInitialized() {
73    page_size_ = GetPageSizeCached();
74    chunks_ = reinterpret_cast<Header**>(ptr_array_.Init());
75  }
76
77  void Init() {
78    internal_memset(this, 0, sizeof(*this));
79    InitLinkerInitialized();
80  }
81
82  void *Allocate(AllocatorStats *stat, uptr size, uptr alignment) {
83    CHECK(IsPowerOfTwo(alignment));
84    uptr map_size = RoundUpMapSize(size);
85    if (alignment > page_size_)
86      map_size += alignment;
87    // Overflow.
88    if (map_size < size) {
89      Report("WARNING: %s: LargeMmapAllocator allocation overflow: "
90             "0x%zx bytes with 0x%zx alignment requested\n",
91             SanitizerToolName, map_size, alignment);
92      return nullptr;
93    }
94    uptr map_beg = reinterpret_cast<uptr>(
95        MmapOrDieOnFatalError(map_size, SecondaryAllocatorName));
96    if (!map_beg)
97      return nullptr;
98    CHECK(IsAligned(map_beg, page_size_));
99    MapUnmapCallback().OnMap(map_beg, map_size);
100    uptr map_end = map_beg + map_size;
101    uptr res = map_beg + page_size_;
102    if (res & (alignment - 1))  // Align.
103      res += alignment - (res & (alignment - 1));
104    CHECK(IsAligned(res, alignment));
105    CHECK(IsAligned(res, page_size_));
106    CHECK_GE(res + size, map_beg);
107    CHECK_LE(res + size, map_end);
108    Header *h = GetHeader(res);
109    h->size = size;
110    h->map_beg = map_beg;
111    h->map_size = map_size;
112    uptr size_log = MostSignificantSetBitIndex(map_size);
113    CHECK_LT(size_log, ARRAY_SIZE(stats.by_size_log));
114    {
115      SpinMutexLock l(&mutex_);
116      ptr_array_.EnsureSpace(n_chunks_);
117      uptr idx = n_chunks_++;
118      h->chunk_idx = idx;
119      chunks_[idx] = h;
120      chunks_sorted_ = false;
121      stats.n_allocs++;
122      stats.currently_allocated += map_size;
123      stats.max_allocated = Max(stats.max_allocated, stats.currently_allocated);
124      stats.by_size_log[size_log]++;
125      stat->Add(AllocatorStatAllocated, map_size);
126      stat->Add(AllocatorStatMapped, map_size);
127    }
128    return reinterpret_cast<void*>(res);
129  }
130
131  void Deallocate(AllocatorStats *stat, void *p) {
132    Header *h = GetHeader(p);
133    {
134      SpinMutexLock l(&mutex_);
135      uptr idx = h->chunk_idx;
136      CHECK_EQ(chunks_[idx], h);
137      CHECK_LT(idx, n_chunks_);
138      chunks_[idx] = chunks_[--n_chunks_];
139      chunks_[idx]->chunk_idx = idx;
140      chunks_sorted_ = false;
141      stats.n_frees++;
142      stats.currently_allocated -= h->map_size;
143      stat->Sub(AllocatorStatAllocated, h->map_size);
144      stat->Sub(AllocatorStatMapped, h->map_size);
145    }
146    MapUnmapCallback().OnUnmap(h->map_beg, h->map_size);
147    UnmapOrDie(reinterpret_cast<void*>(h->map_beg), h->map_size);
148  }
149
150  uptr TotalMemoryUsed() {
151    SpinMutexLock l(&mutex_);
152    uptr res = 0;
153    for (uptr i = 0; i < n_chunks_; i++) {
154      Header *h = chunks_[i];
155      CHECK_EQ(h->chunk_idx, i);
156      res += RoundUpMapSize(h->size);
157    }
158    return res;
159  }
160
161  bool PointerIsMine(const void *p) {
162    return GetBlockBegin(p) != nullptr;
163  }
164
165  uptr GetActuallyAllocatedSize(void *p) {
166    return RoundUpTo(GetHeader(p)->size, page_size_);
167  }
168
169  // At least page_size_/2 metadata bytes is available.
170  void *GetMetaData(const void *p) {
171    // Too slow: CHECK_EQ(p, GetBlockBegin(p));
172    if (!IsAligned(reinterpret_cast<uptr>(p), page_size_)) {
173      Printf("%s: bad pointer %p\n", SanitizerToolName, p);
174      CHECK(IsAligned(reinterpret_cast<uptr>(p), page_size_));
175    }
176    return GetHeader(p) + 1;
177  }
178
179  void *GetBlockBegin(const void *ptr) {
180    uptr p = reinterpret_cast<uptr>(ptr);
181    SpinMutexLock l(&mutex_);
182    uptr nearest_chunk = 0;
183    // Cache-friendly linear search.
184    for (uptr i = 0; i < n_chunks_; i++) {
185      uptr ch = reinterpret_cast<uptr>(chunks_[i]);
186      if (p < ch) continue;  // p is at left to this chunk, skip it.
187      if (p - ch < p - nearest_chunk)
188        nearest_chunk = ch;
189    }
190    if (!nearest_chunk)
191      return nullptr;
192    Header *h = reinterpret_cast<Header *>(nearest_chunk);
193    CHECK_GE(nearest_chunk, h->map_beg);
194    CHECK_LT(nearest_chunk, h->map_beg + h->map_size);
195    CHECK_LE(nearest_chunk, p);
196    if (h->map_beg + h->map_size <= p)
197      return nullptr;
198    return GetUser(h);
199  }
200
201  void EnsureSortedChunks() {
202    if (chunks_sorted_) return;
203    Sort(reinterpret_cast<uptr *>(chunks_), n_chunks_);
204    for (uptr i = 0; i < n_chunks_; i++)
205      chunks_[i]->chunk_idx = i;
206    chunks_sorted_ = true;
207  }
208
209  // This function does the same as GetBlockBegin, but is much faster.
210  // Must be called with the allocator locked.
211  void *GetBlockBeginFastLocked(void *ptr) {
212    mutex_.CheckLocked();
213    uptr p = reinterpret_cast<uptr>(ptr);
214    uptr n = n_chunks_;
215    if (!n) return nullptr;
216    EnsureSortedChunks();
217    auto min_mmap_ = reinterpret_cast<uptr>(chunks_[0]);
218    auto max_mmap_ =
219        reinterpret_cast<uptr>(chunks_[n - 1]) + chunks_[n - 1]->map_size;
220    if (p < min_mmap_ || p >= max_mmap_)
221      return nullptr;
222    uptr beg = 0, end = n - 1;
223    // This loop is a log(n) lower_bound. It does not check for the exact match
224    // to avoid expensive cache-thrashing loads.
225    while (end - beg >= 2) {
226      uptr mid = (beg + end) / 2;  // Invariant: mid >= beg + 1
227      if (p < reinterpret_cast<uptr>(chunks_[mid]))
228        end = mid - 1;  // We are not interested in chunks_[mid].
229      else
230        beg = mid;  // chunks_[mid] may still be what we want.
231    }
232
233    if (beg < end) {
234      CHECK_EQ(beg + 1, end);
235      // There are 2 chunks left, choose one.
236      if (p >= reinterpret_cast<uptr>(chunks_[end]))
237        beg = end;
238    }
239
240    Header *h = chunks_[beg];
241    if (h->map_beg + h->map_size <= p || p < h->map_beg)
242      return nullptr;
243    return GetUser(h);
244  }
245
246  void PrintStats() {
247    Printf("Stats: LargeMmapAllocator: allocated %zd times, "
248           "remains %zd (%zd K) max %zd M; by size logs: ",
249           stats.n_allocs, stats.n_allocs - stats.n_frees,
250           stats.currently_allocated >> 10, stats.max_allocated >> 20);
251    for (uptr i = 0; i < ARRAY_SIZE(stats.by_size_log); i++) {
252      uptr c = stats.by_size_log[i];
253      if (!c) continue;
254      Printf("%zd:%zd; ", i, c);
255    }
256    Printf("\n");
257  }
258
259  // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
260  // introspection API.
261  void ForceLock() {
262    mutex_.Lock();
263  }
264
265  void ForceUnlock() {
266    mutex_.Unlock();
267  }
268
269  // Iterate over all existing chunks.
270  // The allocator must be locked when calling this function.
271  void ForEachChunk(ForEachChunkCallback callback, void *arg) {
272    EnsureSortedChunks();  // Avoid doing the sort while iterating.
273    for (uptr i = 0; i < n_chunks_; i++) {
274      auto t = chunks_[i];
275      callback(reinterpret_cast<uptr>(GetUser(t)), arg);
276      // Consistency check: verify that the array did not change.
277      CHECK_EQ(chunks_[i], t);
278      CHECK_EQ(chunks_[i]->chunk_idx, i);
279    }
280  }
281
282 private:
283  struct Header {
284    uptr map_beg;
285    uptr map_size;
286    uptr size;
287    uptr chunk_idx;
288  };
289
290  Header *GetHeader(uptr p) {
291    CHECK(IsAligned(p, page_size_));
292    return reinterpret_cast<Header*>(p - page_size_);
293  }
294  Header *GetHeader(const void *p) {
295    return GetHeader(reinterpret_cast<uptr>(p));
296  }
297
298  void *GetUser(Header *h) {
299    CHECK(IsAligned((uptr)h, page_size_));
300    return reinterpret_cast<void*>(reinterpret_cast<uptr>(h) + page_size_);
301  }
302
303  uptr RoundUpMapSize(uptr size) {
304    return RoundUpTo(size, page_size_) + page_size_;
305  }
306
307  uptr page_size_;
308  Header **chunks_;
309  PtrArrayT ptr_array_;
310  uptr n_chunks_;
311  bool chunks_sorted_;
312  struct Stats {
313    uptr n_allocs, n_frees, currently_allocated, max_allocated, by_size_log[64];
314  } stats;
315  StaticSpinMutex mutex_;
316};
317