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 uptr kSpaceBeg = Params::kSpaceBeg; 57 static const u64 kSpaceSize = Params::kSpaceSize; 58 static const uptr kMetadataSize = Params::kMetadataSize; 59 typedef typename Params::SizeClassMap SizeClassMap; 60 static const uptr 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 uptr kMaxNumCached = SizeClassMap::kMaxNumCachedHint - 2; 78 void SetFromArray(void *batch[], uptr count) { 79 DCHECK_LE(count, kMaxNumCached); 80 count_ = count; 81 for (uptr i = 0; i < count; i++) 82 batch_[i] = batch[i]; 83 } 84 uptr Count() const { return count_; } 85 void Clear() { count_ = 0; } 86 void Add(void *ptr) { 87 batch_[count_++] = ptr; 88 DCHECK_LE(count_, kMaxNumCached); 89 } 90 void CopyToArray(void *to_batch[]) const { 91 for (uptr 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. 96 static uptr AllocationSizeRequiredForNElements(uptr n) { 97 return sizeof(uptr) * 2 + sizeof(void *) * n; 98 } 99 static uptr MaxCached(uptr size) { 100 return Min(kMaxNumCached, SizeClassMap::MaxCachedHint(size)); 101 } 102 103 TransferBatch *next; 104 105 private: 106 uptr count_; 107 void *batch_[kMaxNumCached]; 108 }; 109 110 static const uptr kBatchSize = sizeof(TransferBatch); 111 COMPILER_CHECK((kBatchSize & (kBatchSize - 1)) == 0); 112 COMPILER_CHECK(kBatchSize == SizeClassMap::kMaxNumCachedHint * sizeof(uptr)); 113 114 static uptr ClassIdToSize(uptr 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 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 127 s32 ReleaseToOSIntervalMs() const { 128 return kReleaseToOSIntervalNever; 129 } 130 131 void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) { 132 // This is empty here. Currently only implemented in 64-bit allocator. 133 } 134 135 void ForceReleaseToOS() { 136 // Currently implemented in 64-bit allocator only. 137 } 138 139 void *MapWithCallback(uptr size) { 140 void *res = MmapOrDie(size, PrimaryAllocatorName); 141 MapUnmapCallback().OnMap((uptr)res, size); 142 return res; 143 } 144 145 void UnmapWithCallback(uptr beg, uptr size) { 146 MapUnmapCallback().OnUnmap(beg, size); 147 UnmapOrDie(reinterpret_cast<void *>(beg), size); 148 } 149 150 static bool CanAllocate(uptr size, uptr alignment) { 151 return size <= SizeClassMap::kMaxSize && 152 alignment <= SizeClassMap::kMaxSize; 153 } 154 155 void *GetMetaData(const void *p) { 156 CHECK(PointerIsMine(p)); 157 uptr mem = reinterpret_cast<uptr>(p); 158 uptr beg = ComputeRegionBeg(mem); 159 uptr size = ClassIdToSize(GetSizeClass(p)); 160 u32 offset = mem - beg; 161 uptr n = offset / (u32)size; // 32-bit division 162 uptr meta = (beg + kRegionSize) - (n + 1) * kMetadataSize; 163 return reinterpret_cast<void*>(meta); 164 } 165 166 NOINLINE TransferBatch *AllocateBatch(AllocatorStats *stat, AllocatorCache *c, 167 uptr 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 181 NOINLINE void DeallocateBatch(AllocatorStats *stat, uptr 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 190 bool PointerIsMine(const void *p) { 191 uptr mem = reinterpret_cast<uptr>(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 199 uptr GetSizeClass(const void *p) { 200 return possible_regions[ComputeRegionId(reinterpret_cast<uptr>(p))]; 201 } 202 203 void *GetBlockBegin(const void *p) { 204 CHECK(PointerIsMine(p)); 205 uptr mem = reinterpret_cast<uptr>(p); 206 uptr beg = ComputeRegionBeg(mem); 207 uptr 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 214 uptr GetActuallyAllocatedSize(void *p) { 215 CHECK(PointerIsMine(p)); 216 return ClassIdToSize(GetSizeClass(p)); 217 } 218 219 static uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); } 220 221 uptr TotalMemoryUsed() { 222 // No need to lock here. 223 uptr res = 0; 224 for (uptr i = 0; i < kNumPossibleRegions; i++) 225 if (possible_regions[i]) 226 res += kRegionSize; 227 return res; 228 } 229 230 void TestOnlyUnmap() { 231 for (uptr 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. 238 void ForceLock() { 239 for (uptr i = 0; i < kNumClasses; i++) { 240 GetSizeClassInfo(i)->mutex.Lock(); 241 } 242 } 243 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. 252 void ForEachChunk(ForEachChunkCallback callback, void *arg) { 253 for (uptr region = 0; region < kNumPossibleRegions; region++) 254 if (possible_regions[region]) { 255 uptr chunk_size = ClassIdToSize(possible_regions[region]); 256 uptr max_chunks_in_region = kRegionSize / (chunk_size + kMetadataSize); 257 uptr region_beg = region * kRegionSize; 258 for (uptr 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 267 void PrintStats() {} 268 269 static uptr AdditionalSize() { return 0; } 270 271 typedef SizeClassMap SizeClassMapT; 272 static const uptr kNumClasses = SizeClassMap::kNumClasses; 273 274 private: 275 static const uptr kRegionSize = 1 << kRegionSizeLog; 276 static const uptr kNumPossibleRegions = kSpaceSize / kRegionSize; 277 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 285 uptr ComputeRegionId(uptr mem) const { 286 if (SANITIZER_SIGN_EXTENDED_ADDRESSES) 287 mem &= (kSpaceSize - 1); 288 const uptr res = mem >> kRegionSizeLog; 289 CHECK_LT(res, kNumPossibleRegions); 290 return res; 291 } 292 293 uptr ComputeRegionBeg(uptr mem) { 294 return mem & ~(kRegionSize - 1); 295 } 296 297 uptr AllocateRegion(AllocatorStats *stat, uptr 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 310 SizeClassInfo *GetSizeClassInfo(uptr class_id) { 311 DCHECK_LT(class_id, kNumClasses); 312 return &size_class_info_array[class_id]; 313 } 314 315 bool PopulateBatches(AllocatorCache *c, SizeClassInfo *sci, uptr class_id, 316 TransferBatch **current_batch, uptr max_count, 317 uptr *pointers_array, uptr 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 (uptr 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 340 bool PopulateFreeList(AllocatorStats *stat, AllocatorCache *c, 341 SizeClassInfo *sci, uptr 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<uptr>(sci) ^ NanoTime(); 349 const uptr size = ClassIdToSize(class_id); 350 const uptr n_chunks = kRegionSize / (size + kMetadataSize); 351 const uptr max_count = TransferBatch::MaxCached(size); 352 DCHECK_GT(max_count, 0); 353 TransferBatch *b = nullptr; 354 constexpr uptr kShuffleArraySize = 48; 355 uptr shuffle_array[kShuffleArraySize]; 356 uptr 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