1 //===-- sanitizer_allocator_primary32.h -------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Part of the Sanitizer Allocator. 10 // 11 //===----------------------------------------------------------------------===// 12 #ifndef SANITIZER_ALLOCATOR_H 13 #error This file must be included inside sanitizer_allocator.h 14 #endif 15 16 template<class SizeClassAllocator> struct SizeClassAllocator32LocalCache; 17 18 // SizeClassAllocator32 -- allocator for 32-bit address space. 19 // This allocator can theoretically be used on 64-bit arch, but there it is less 20 // efficient than SizeClassAllocator64. 21 // 22 // [kSpaceBeg, kSpaceBeg + kSpaceSize) is the range of addresses which can 23 // be returned by MmapOrDie(). 24 // 25 // Region: 26 // a result of a single call to MmapAlignedOrDieOnFatalError(kRegionSize, 27 // kRegionSize). 28 // Since the regions are aligned by kRegionSize, there are exactly 29 // kNumPossibleRegions possible regions in the address space and so we keep 30 // a ByteMap possible_regions to store the size classes of each Region. 31 // 0 size class means the region is not used by the allocator. 32 // 33 // One Region is used to allocate chunks of a single size class. 34 // A Region looks like this: 35 // UserChunk1 .. UserChunkN <gap> MetaChunkN .. MetaChunk1 36 // 37 // In order to avoid false sharing the objects of this class should be 38 // chache-line aligned. 39 40 struct SizeClassAllocator32FlagMasks { // Bit masks. 41 enum { 42 kRandomShuffleChunks = 1, 43 kUseSeparateSizeClassForBatch = 2, 44 }; 45 }; 46 47 template <class Params> 48 class SizeClassAllocator32 { 49 private: 50 static const u64 kTwoLevelByteMapSize1 = 51 (Params::kSpaceSize >> Params::kRegionSizeLog) >> 12; 52 static const u64 kMinFirstMapSizeTwoLevelByteMap = 4; 53 54 public: 55 using AddressSpaceView = typename Params::AddressSpaceView; 56 static const vaddr kSpaceBeg = Params::kSpaceBeg; 57 static const u64 kSpaceSize = Params::kSpaceSize; 58 static const usize kMetadataSize = Params::kMetadataSize; 59 typedef typename Params::SizeClassMap SizeClassMap; 60 static const usize kRegionSizeLog = Params::kRegionSizeLog; 61 typedef typename Params::MapUnmapCallback MapUnmapCallback; 62 using ByteMap = typename conditional< 63 (kTwoLevelByteMapSize1 < kMinFirstMapSizeTwoLevelByteMap), 64 FlatByteMap<(Params::kSpaceSize >> Params::kRegionSizeLog), 65 AddressSpaceView>, 66 TwoLevelByteMap<kTwoLevelByteMapSize1, 1 << 12, AddressSpaceView>>::type; 67 68 COMPILER_CHECK(!SANITIZER_SIGN_EXTENDED_ADDRESSES || 69 (kSpaceSize & (kSpaceSize - 1)) == 0); 70 71 static const bool kRandomShuffleChunks = Params::kFlags & 72 SizeClassAllocator32FlagMasks::kRandomShuffleChunks; 73 static const bool kUseSeparateSizeClassForBatch = Params::kFlags & 74 SizeClassAllocator32FlagMasks::kUseSeparateSizeClassForBatch; 75 76 struct TransferBatch { 77 static const usize kMaxNumCached = SizeClassMap::kMaxNumCachedHint - 2; SetFromArrayTransferBatch78 void SetFromArray(void *batch[], usize count) { 79 DCHECK_LE(count, kMaxNumCached); 80 count_ = count; 81 for (usize i = 0; i < count; i++) 82 batch_[i] = batch[i]; 83 } CountTransferBatch84 usize Count() const { return count_; } ClearTransferBatch85 void Clear() { count_ = 0; } AddTransferBatch86 void Add(void *ptr) { 87 batch_[count_++] = ptr; 88 DCHECK_LE(count_, kMaxNumCached); 89 } CopyToArrayTransferBatch90 void CopyToArray(void *to_batch[]) const { 91 for (usize i = 0, n = Count(); i < n; i++) 92 to_batch[i] = batch_[i]; 93 } 94 95 // How much memory do we need for a batch containing n elements. AllocationSizeRequiredForNElementsTransferBatch96 static usize AllocationSizeRequiredForNElements(usize n) { 97 return sizeof(usize) * 2 + sizeof(void *) * n; 98 } MaxCachedTransferBatch99 static usize MaxCached(usize size) { 100 return Min(kMaxNumCached, SizeClassMap::MaxCachedHint(size)); 101 } 102 103 TransferBatch *next; 104 105 private: 106 usize count_; 107 void *batch_[kMaxNumCached]; 108 }; 109 110 static const usize kBatchSize = sizeof(TransferBatch); 111 COMPILER_CHECK((kBatchSize & (kBatchSize - 1)) == 0); 112 COMPILER_CHECK(kBatchSize == SizeClassMap::kMaxNumCachedHint * sizeof(uptr)); 113 ClassIdToSize(usize class_id)114 static usize ClassIdToSize(usize class_id) { 115 return (class_id == SizeClassMap::kBatchClassID) ? 116 kBatchSize : SizeClassMap::Size(class_id); 117 } 118 119 typedef SizeClassAllocator32<Params> ThisT; 120 typedef SizeClassAllocator32LocalCache<ThisT> AllocatorCache; 121 Init(s32 release_to_os_interval_ms)122 void Init(s32 release_to_os_interval_ms) { 123 possible_regions.Init(); 124 internal_memset(size_class_info_array, 0, sizeof(size_class_info_array)); 125 } 126 ReleaseToOSIntervalMs()127 s32 ReleaseToOSIntervalMs() const { 128 return kReleaseToOSIntervalNever; 129 } 130 SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms)131 void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) { 132 // This is empty here. Currently only implemented in 64-bit allocator. 133 } 134 ForceReleaseToOS()135 void ForceReleaseToOS() { 136 // Currently implemented in 64-bit allocator only. 137 } 138 MapWithCallback(usize size)139 void *MapWithCallback(usize size) { 140 void *res = MmapOrDie(size, PrimaryAllocatorName); 141 MapUnmapCallback().OnMap((uptr)res, size); 142 return res; 143 } 144 UnmapWithCallback(uptr beg,usize size)145 void UnmapWithCallback(uptr beg, usize size) { 146 MapUnmapCallback().OnUnmap(beg, size); 147 UnmapOrDie(reinterpret_cast<void *>(beg), size); 148 } 149 CanAllocate(usize size,usize alignment)150 static bool CanAllocate(usize size, usize alignment) { 151 return size <= SizeClassMap::kMaxSize && 152 alignment <= SizeClassMap::kMaxSize; 153 } 154 GetMetaData(const void * p)155 void *GetMetaData(const void *p) { 156 CHECK(PointerIsMine(p)); 157 uptr mem = reinterpret_cast<uptr>(p); 158 uptr beg = ComputeRegionBeg(mem); 159 usize size = ClassIdToSize(GetSizeClass(p)); 160 u32 offset = mem - beg; 161 usize n = offset / (u32)size; // 32-bit division 162 uptr meta = (beg + kRegionSize) - (n + 1) * kMetadataSize; 163 return reinterpret_cast<void*>(meta); 164 } 165 AllocateBatch(AllocatorStats * stat,AllocatorCache * c,usize class_id)166 NOINLINE TransferBatch *AllocateBatch(AllocatorStats *stat, AllocatorCache *c, 167 usize class_id) { 168 DCHECK_LT(class_id, kNumClasses); 169 SizeClassInfo *sci = GetSizeClassInfo(class_id); 170 SpinMutexLock l(&sci->mutex); 171 if (sci->free_list.empty()) { 172 if (UNLIKELY(!PopulateFreeList(stat, c, sci, class_id))) 173 return nullptr; 174 DCHECK(!sci->free_list.empty()); 175 } 176 TransferBatch *b = sci->free_list.front(); 177 sci->free_list.pop_front(); 178 return b; 179 } 180 DeallocateBatch(AllocatorStats * stat,usize class_id,TransferBatch * b)181 NOINLINE void DeallocateBatch(AllocatorStats *stat, usize class_id, 182 TransferBatch *b) { 183 DCHECK_LT(class_id, kNumClasses); 184 CHECK_GT(b->Count(), 0); 185 SizeClassInfo *sci = GetSizeClassInfo(class_id); 186 SpinMutexLock l(&sci->mutex); 187 sci->free_list.push_front(b); 188 } 189 PointerIsMine(const void * p)190 bool PointerIsMine(const void *p) { 191 vaddr mem = reinterpret_cast<vaddr>(p); 192 if (SANITIZER_SIGN_EXTENDED_ADDRESSES) 193 mem &= (kSpaceSize - 1); 194 if (mem < kSpaceBeg || mem >= kSpaceBeg + kSpaceSize) 195 return false; 196 return GetSizeClass(p) != 0; 197 } 198 GetSizeClass(const void * p)199 usize GetSizeClass(const void *p) { 200 return possible_regions[ComputeRegionId(reinterpret_cast<uptr>(p))]; 201 } 202 GetBlockBegin(const void * p)203 void *GetBlockBegin(const void *p) { 204 CHECK(PointerIsMine(p)); 205 uptr mem = reinterpret_cast<uptr>(p); 206 uptr beg = ComputeRegionBeg(mem); 207 usize size = ClassIdToSize(GetSizeClass(p)); 208 u32 offset = mem - beg; 209 u32 n = offset / (u32)size; // 32-bit division 210 uptr res = beg + (n * (u32)size); 211 return reinterpret_cast<void*>(res); 212 } 213 GetActuallyAllocatedSize(void * p)214 usize GetActuallyAllocatedSize(void *p) { 215 CHECK(PointerIsMine(p)); 216 return ClassIdToSize(GetSizeClass(p)); 217 } 218 ClassID(usize size)219 static usize ClassID(usize size) { return SizeClassMap::ClassID(size); } 220 TotalMemoryUsed()221 usize TotalMemoryUsed() { 222 // No need to lock here. 223 usize res = 0; 224 for (usize i = 0; i < kNumPossibleRegions; i++) 225 if (possible_regions[i]) 226 res += kRegionSize; 227 return res; 228 } 229 TestOnlyUnmap()230 void TestOnlyUnmap() { 231 for (usize i = 0; i < kNumPossibleRegions; i++) 232 if (possible_regions[i]) 233 UnmapWithCallback((i * kRegionSize), kRegionSize); 234 } 235 236 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone 237 // introspection API. ForceLock()238 void ForceLock() { 239 for (usize i = 0; i < kNumClasses; i++) { 240 GetSizeClassInfo(i)->mutex.Lock(); 241 } 242 } 243 ForceUnlock()244 void ForceUnlock() { 245 for (int i = kNumClasses - 1; i >= 0; i--) { 246 GetSizeClassInfo(i)->mutex.Unlock(); 247 } 248 } 249 250 // Iterate over all existing chunks. 251 // The allocator must be locked when calling this function. ForEachChunk(ForEachChunkCallback callback,void * arg)252 void ForEachChunk(ForEachChunkCallback callback, void *arg) { 253 for (vaddr region = 0; region < kNumPossibleRegions; region++) 254 if (possible_regions[region]) { 255 usize chunk_size = ClassIdToSize(possible_regions[region]); 256 usize max_chunks_in_region = kRegionSize / (chunk_size + kMetadataSize); 257 vaddr region_beg = region * kRegionSize; 258 for (vaddr chunk = region_beg; 259 chunk < region_beg + max_chunks_in_region * chunk_size; 260 chunk += chunk_size) { 261 // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk)); 262 callback(chunk, arg); 263 } 264 } 265 } 266 PrintStats()267 void PrintStats() {} 268 AdditionalSize()269 static usize AdditionalSize() { return 0; } 270 271 typedef SizeClassMap SizeClassMapT; 272 static const usize kNumClasses = SizeClassMap::kNumClasses; 273 274 private: 275 static const usize kRegionSize = 1 << kRegionSizeLog; 276 static const usize kNumPossibleRegions = kSpaceSize / kRegionSize; 277 ALIGNED(SANITIZER_CACHE_LINE_SIZE)278 struct ALIGNED(SANITIZER_CACHE_LINE_SIZE) SizeClassInfo { 279 StaticSpinMutex mutex; 280 IntrusiveList<TransferBatch> free_list; 281 u32 rand_state; 282 }; 283 COMPILER_CHECK(sizeof(SizeClassInfo) % kCacheLineSize == 0); 284 ComputeRegionId(vaddr mem)285 uptr ComputeRegionId(vaddr mem) const { 286 if (SANITIZER_SIGN_EXTENDED_ADDRESSES) 287 mem &= (kSpaceSize - 1); 288 const usize res = (usize)mem >> kRegionSizeLog; 289 CHECK_LT(res, kNumPossibleRegions); 290 return res; 291 } 292 ComputeRegionBeg(uptr mem)293 uptr ComputeRegionBeg(uptr mem) { 294 return RoundDownTo(mem, kRegionSize); 295 } 296 AllocateRegion(AllocatorStats * stat,usize class_id)297 uptr AllocateRegion(AllocatorStats *stat, usize class_id) { 298 DCHECK_LT(class_id, kNumClasses); 299 const uptr res = reinterpret_cast<uptr>(MmapAlignedOrDieOnFatalError( 300 kRegionSize, kRegionSize, PrimaryAllocatorName)); 301 if (UNLIKELY(!res)) 302 return 0; 303 MapUnmapCallback().OnMap(res, kRegionSize); 304 stat->Add(AllocatorStatMapped, kRegionSize); 305 CHECK(IsAligned(res, kRegionSize)); 306 possible_regions.set(ComputeRegionId(res), static_cast<u8>(class_id)); 307 return res; 308 } 309 GetSizeClassInfo(usize class_id)310 SizeClassInfo *GetSizeClassInfo(usize class_id) { 311 DCHECK_LT(class_id, kNumClasses); 312 return &size_class_info_array[class_id]; 313 } 314 PopulateBatches(AllocatorCache * c,SizeClassInfo * sci,usize class_id,TransferBatch ** current_batch,usize max_count,uptr * pointers_array,usize count)315 bool PopulateBatches(AllocatorCache *c, SizeClassInfo *sci, usize class_id, 316 TransferBatch **current_batch, usize max_count, 317 uptr *pointers_array, usize count) { 318 // If using a separate class for batches, we do not need to shuffle it. 319 if (kRandomShuffleChunks && (!kUseSeparateSizeClassForBatch || 320 class_id != SizeClassMap::kBatchClassID)) 321 RandomShuffle(pointers_array, count, &sci->rand_state); 322 TransferBatch *b = *current_batch; 323 for (usize i = 0; i < count; i++) { 324 if (!b) { 325 b = c->CreateBatch(class_id, this, (TransferBatch*)pointers_array[i]); 326 if (UNLIKELY(!b)) 327 return false; 328 b->Clear(); 329 } 330 b->Add((void*)pointers_array[i]); 331 if (b->Count() == max_count) { 332 sci->free_list.push_back(b); 333 b = nullptr; 334 } 335 } 336 *current_batch = b; 337 return true; 338 } 339 PopulateFreeList(AllocatorStats * stat,AllocatorCache * c,SizeClassInfo * sci,usize class_id)340 bool PopulateFreeList(AllocatorStats *stat, AllocatorCache *c, 341 SizeClassInfo *sci, usize class_id) { 342 const uptr region = AllocateRegion(stat, class_id); 343 if (UNLIKELY(!region)) 344 return false; 345 if (kRandomShuffleChunks) 346 if (UNLIKELY(sci->rand_state == 0)) 347 // The random state is initialized from ASLR (PIE) and time. 348 sci->rand_state = reinterpret_cast<vaddr>(sci) ^ NanoTime(); 349 const usize size = ClassIdToSize(class_id); 350 const usize n_chunks = kRegionSize / (size + kMetadataSize); 351 const usize max_count = TransferBatch::MaxCached(size); 352 DCHECK_GT(max_count, 0); 353 TransferBatch *b = nullptr; 354 constexpr usize kShuffleArraySize = 48; 355 uptr shuffle_array[kShuffleArraySize]; 356 usize count = 0; 357 for (uptr i = region; i < region + n_chunks * size; i += size) { 358 shuffle_array[count++] = i; 359 if (count == kShuffleArraySize) { 360 if (UNLIKELY(!PopulateBatches(c, sci, class_id, &b, max_count, 361 shuffle_array, count))) 362 return false; 363 count = 0; 364 } 365 } 366 if (count) { 367 if (UNLIKELY(!PopulateBatches(c, sci, class_id, &b, max_count, 368 shuffle_array, count))) 369 return false; 370 } 371 if (b) { 372 CHECK_GT(b->Count(), 0); 373 sci->free_list.push_back(b); 374 } 375 return true; 376 } 377 378 ByteMap possible_regions; 379 SizeClassInfo size_class_info_array[kNumClasses]; 380 }; 381