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