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 // This class can (de)allocate only large chunks of memory using mmap/unmap.
16 // The main purpose of this allocator is to cover large and rare allocation
17 // sizes not covered by more efficient allocators (e.g. SizeClassAllocator64).
18 template <class MapUnmapCallback = NoOpMapUnmapCallback,
19           class FailureHandlerT = ReturnNullOrDieOnFailure>
20 class LargeMmapAllocator {
21  public:
22   typedef FailureHandlerT FailureHandler;
23 
InitLinkerInitialized()24   void InitLinkerInitialized() {
25     page_size_ = GetPageSizeCached();
26   }
27 
Init()28   void Init() {
29     internal_memset(this, 0, sizeof(*this));
30     InitLinkerInitialized();
31   }
32 
Allocate(AllocatorStats * stat,uptr size,uptr alignment)33   void *Allocate(AllocatorStats *stat, uptr size, uptr alignment) {
34     CHECK(IsPowerOfTwo(alignment));
35     uptr map_size = RoundUpMapSize(size);
36     if (alignment > page_size_)
37       map_size += alignment;
38     // Overflow.
39     if (map_size < size)
40       return FailureHandler::OnBadRequest();
41     uptr map_beg = reinterpret_cast<uptr>(
42         MmapOrDieOnFatalError(map_size, "LargeMmapAllocator"));
43     if (!map_beg)
44       return FailureHandler::OnOOM();
45     CHECK(IsAligned(map_beg, page_size_));
46     MapUnmapCallback().OnMap(map_beg, map_size);
47     uptr map_end = map_beg + map_size;
48     uptr res = map_beg + page_size_;
49     if (res & (alignment - 1))  // Align.
50       res += alignment - (res & (alignment - 1));
51     CHECK(IsAligned(res, alignment));
52     CHECK(IsAligned(res, page_size_));
53     CHECK_GE(res + size, map_beg);
54     CHECK_LE(res + size, map_end);
55     Header *h = GetHeader(res);
56     h->size = size;
57     h->map_beg = map_beg;
58     h->map_size = map_size;
59     uptr size_log = MostSignificantSetBitIndex(map_size);
60     CHECK_LT(size_log, ARRAY_SIZE(stats.by_size_log));
61     {
62       SpinMutexLock l(&mutex_);
63       uptr idx = n_chunks_++;
64       chunks_sorted_ = false;
65       CHECK_LT(idx, kMaxNumChunks);
66       h->chunk_idx = idx;
67       chunks_[idx] = h;
68       stats.n_allocs++;
69       stats.currently_allocated += map_size;
70       stats.max_allocated = Max(stats.max_allocated, stats.currently_allocated);
71       stats.by_size_log[size_log]++;
72       stat->Add(AllocatorStatAllocated, map_size);
73       stat->Add(AllocatorStatMapped, map_size);
74     }
75     return reinterpret_cast<void*>(res);
76   }
77 
Deallocate(AllocatorStats * stat,void * p)78   void Deallocate(AllocatorStats *stat, void *p) {
79     Header *h = GetHeader(p);
80     {
81       SpinMutexLock l(&mutex_);
82       uptr idx = h->chunk_idx;
83       CHECK_EQ(chunks_[idx], h);
84       CHECK_LT(idx, n_chunks_);
85       chunks_[idx] = chunks_[n_chunks_ - 1];
86       chunks_[idx]->chunk_idx = idx;
87       n_chunks_--;
88       chunks_sorted_ = false;
89       stats.n_frees++;
90       stats.currently_allocated -= h->map_size;
91       stat->Sub(AllocatorStatAllocated, h->map_size);
92       stat->Sub(AllocatorStatMapped, h->map_size);
93     }
94     MapUnmapCallback().OnUnmap(h->map_beg, h->map_size);
95     UnmapOrDie(reinterpret_cast<void*>(h->map_beg), h->map_size);
96   }
97 
TotalMemoryUsed()98   uptr TotalMemoryUsed() {
99     SpinMutexLock l(&mutex_);
100     uptr res = 0;
101     for (uptr i = 0; i < n_chunks_; i++) {
102       Header *h = chunks_[i];
103       CHECK_EQ(h->chunk_idx, i);
104       res += RoundUpMapSize(h->size);
105     }
106     return res;
107   }
108 
PointerIsMine(const void * p)109   bool PointerIsMine(const void *p) {
110     return GetBlockBegin(p) != nullptr;
111   }
112 
GetActuallyAllocatedSize(void * p)113   uptr GetActuallyAllocatedSize(void *p) {
114     return RoundUpTo(GetHeader(p)->size, page_size_);
115   }
116 
117   // At least page_size_/2 metadata bytes is available.
GetMetaData(const void * p)118   void *GetMetaData(const void *p) {
119     // Too slow: CHECK_EQ(p, GetBlockBegin(p));
120     if (!IsAligned(reinterpret_cast<uptr>(p), page_size_)) {
121       Printf("%s: bad pointer %p\n", SanitizerToolName, p);
122       CHECK(IsAligned(reinterpret_cast<uptr>(p), page_size_));
123     }
124     return GetHeader(p) + 1;
125   }
126 
GetBlockBegin(const void * ptr)127   void *GetBlockBegin(const void *ptr) {
128     uptr p = reinterpret_cast<uptr>(ptr);
129     SpinMutexLock l(&mutex_);
130     uptr nearest_chunk = 0;
131     // Cache-friendly linear search.
132     for (uptr i = 0; i < n_chunks_; i++) {
133       uptr ch = reinterpret_cast<uptr>(chunks_[i]);
134       if (p < ch) continue;  // p is at left to this chunk, skip it.
135       if (p - ch < p - nearest_chunk)
136         nearest_chunk = ch;
137     }
138     if (!nearest_chunk)
139       return nullptr;
140     Header *h = reinterpret_cast<Header *>(nearest_chunk);
141     CHECK_GE(nearest_chunk, h->map_beg);
142     CHECK_LT(nearest_chunk, h->map_beg + h->map_size);
143     CHECK_LE(nearest_chunk, p);
144     if (h->map_beg + h->map_size <= p)
145       return nullptr;
146     return GetUser(h);
147   }
148 
EnsureSortedChunks()149   void EnsureSortedChunks() {
150     if (chunks_sorted_) return;
151     SortArray(reinterpret_cast<uptr*>(chunks_), n_chunks_);
152     for (uptr i = 0; i < n_chunks_; i++)
153       chunks_[i]->chunk_idx = i;
154     chunks_sorted_ = true;
155   }
156 
157   // This function does the same as GetBlockBegin, but is much faster.
158   // Must be called with the allocator locked.
GetBlockBeginFastLocked(void * ptr)159   void *GetBlockBeginFastLocked(void *ptr) {
160     mutex_.CheckLocked();
161     uptr p = reinterpret_cast<uptr>(ptr);
162     uptr n = n_chunks_;
163     if (!n) return nullptr;
164     EnsureSortedChunks();
165     auto min_mmap_ = reinterpret_cast<uptr>(chunks_[0]);
166     auto max_mmap_ =
167         reinterpret_cast<uptr>(chunks_[n - 1]) + chunks_[n - 1]->map_size;
168     if (p < min_mmap_ || p >= max_mmap_)
169       return nullptr;
170     uptr beg = 0, end = n - 1;
171     // This loop is a log(n) lower_bound. It does not check for the exact match
172     // to avoid expensive cache-thrashing loads.
173     while (end - beg >= 2) {
174       uptr mid = (beg + end) / 2;  // Invariant: mid >= beg + 1
175       if (p < reinterpret_cast<uptr>(chunks_[mid]))
176         end = mid - 1;  // We are not interested in chunks_[mid].
177       else
178         beg = mid;  // chunks_[mid] may still be what we want.
179     }
180 
181     if (beg < end) {
182       CHECK_EQ(beg + 1, end);
183       // There are 2 chunks left, choose one.
184       if (p >= reinterpret_cast<uptr>(chunks_[end]))
185         beg = end;
186     }
187 
188     Header *h = chunks_[beg];
189     if (h->map_beg + h->map_size <= p || p < h->map_beg)
190       return nullptr;
191     return GetUser(h);
192   }
193 
PrintStats()194   void PrintStats() {
195     Printf("Stats: LargeMmapAllocator: allocated %zd times, "
196            "remains %zd (%zd K) max %zd M; by size logs: ",
197            stats.n_allocs, stats.n_allocs - stats.n_frees,
198            stats.currently_allocated >> 10, stats.max_allocated >> 20);
199     for (uptr i = 0; i < ARRAY_SIZE(stats.by_size_log); i++) {
200       uptr c = stats.by_size_log[i];
201       if (!c) continue;
202       Printf("%zd:%zd; ", i, c);
203     }
204     Printf("\n");
205   }
206 
207   // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
208   // introspection API.
ForceLock()209   void ForceLock() {
210     mutex_.Lock();
211   }
212 
ForceUnlock()213   void ForceUnlock() {
214     mutex_.Unlock();
215   }
216 
217   // Iterate over all existing chunks.
218   // The allocator must be locked when calling this function.
ForEachChunk(ForEachChunkCallback callback,void * arg)219   void ForEachChunk(ForEachChunkCallback callback, void *arg) {
220     EnsureSortedChunks();  // Avoid doing the sort while iterating.
221     for (uptr i = 0; i < n_chunks_; i++) {
222       auto t = chunks_[i];
223       callback(reinterpret_cast<uptr>(GetUser(chunks_[i])), arg);
224       // Consistency check: verify that the array did not change.
225       CHECK_EQ(chunks_[i], t);
226       CHECK_EQ(chunks_[i]->chunk_idx, i);
227     }
228   }
229 
230  private:
231   static const int kMaxNumChunks = 1 << FIRST_32_SECOND_64(15, 18);
232   struct Header {
233     uptr map_beg;
234     uptr map_size;
235     uptr size;
236     uptr chunk_idx;
237   };
238 
GetHeader(uptr p)239   Header *GetHeader(uptr p) {
240     CHECK(IsAligned(p, page_size_));
241     return reinterpret_cast<Header*>(p - page_size_);
242   }
GetHeader(const void * p)243   Header *GetHeader(const void *p) {
244     return GetHeader(reinterpret_cast<uptr>(p));
245   }
246 
GetUser(Header * h)247   void *GetUser(Header *h) {
248     CHECK(IsAligned((uptr)h, page_size_));
249     return reinterpret_cast<void*>(reinterpret_cast<uptr>(h) + page_size_);
250   }
251 
RoundUpMapSize(uptr size)252   uptr RoundUpMapSize(uptr size) {
253     return RoundUpTo(size, page_size_) + page_size_;
254   }
255 
256   uptr page_size_;
257   Header *chunks_[kMaxNumChunks];
258   uptr n_chunks_;
259   bool chunks_sorted_;
260   struct Stats {
261     uptr n_allocs, n_frees, currently_allocated, max_allocated, by_size_log[64];
262   } stats;
263   SpinMutex mutex_;
264 };
265