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