382 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9// Part of the Sanitizer Allocator.10//11//===----------------------------------------------------------------------===//12#ifndef SANITIZER_ALLOCATOR_H13#error This file must be included inside sanitizer_allocator.h14#endif15 16template<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 less20// efficient than SizeClassAllocator64.21//22// [kSpaceBeg, kSpaceBeg + kSpaceSize) is the range of addresses which can23// 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 exactly29// kNumPossibleRegions possible regions in the address space and so we keep30// 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 .. MetaChunk136//37// In order to avoid false sharing the objects of this class should be38// chache-line aligned.39 40struct SizeClassAllocator32FlagMasks { // Bit masks.41 enum {42 kRandomShuffleChunks = 1,43 kUseSeparateSizeClassForBatch = 2,44 };45};46 47template <class Params>48class 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, uptr heap_start = 0) {123 CHECK(!heap_start);124 possible_regions.Init();125 internal_memset(size_class_info_array, 0, sizeof(size_class_info_array));126 }127 128 s32 ReleaseToOSIntervalMs() const {129 return kReleaseToOSIntervalNever;130 }131 132 void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) {133 // This is empty here. Currently only implemented in 64-bit allocator.134 }135 136 void ForceReleaseToOS() {137 // Currently implemented in 64-bit allocator only.138 }139 140 void *MapWithCallback(uptr size) {141 void *res = MmapOrDie(size, PrimaryAllocatorName);142 MapUnmapCallback().OnMap((uptr)res, size);143 return res;144 }145 146 void UnmapWithCallback(uptr beg, uptr size) {147 MapUnmapCallback().OnUnmap(beg, size);148 UnmapOrDie(reinterpret_cast<void *>(beg), size);149 }150 151 static bool CanAllocate(uptr size, uptr alignment) {152 return size <= SizeClassMap::kMaxSize &&153 alignment <= SizeClassMap::kMaxSize;154 }155 156 void *GetMetaData(const void *p) {157 CHECK(kMetadataSize);158 CHECK(PointerIsMine(p));159 uptr mem = reinterpret_cast<uptr>(p);160 uptr beg = ComputeRegionBeg(mem);161 uptr size = ClassIdToSize(GetSizeClass(p));162 u32 offset = mem - beg;163 uptr n = offset / (u32)size; // 32-bit division164 uptr meta = (beg + kRegionSize) - (n + 1) * kMetadataSize;165 return reinterpret_cast<void*>(meta);166 }167 168 NOINLINE TransferBatch *AllocateBatch(AllocatorStats *stat, AllocatorCache *c,169 uptr class_id) {170 DCHECK_LT(class_id, kNumClasses);171 SizeClassInfo *sci = GetSizeClassInfo(class_id);172 SpinMutexLock l(&sci->mutex);173 if (sci->free_list.empty()) {174 if (UNLIKELY(!PopulateFreeList(stat, c, sci, class_id)))175 return nullptr;176 DCHECK(!sci->free_list.empty());177 }178 TransferBatch *b = sci->free_list.front();179 sci->free_list.pop_front();180 return b;181 }182 183 NOINLINE void DeallocateBatch(AllocatorStats *stat, uptr class_id,184 TransferBatch *b) {185 DCHECK_LT(class_id, kNumClasses);186 CHECK_GT(b->Count(), 0);187 SizeClassInfo *sci = GetSizeClassInfo(class_id);188 SpinMutexLock l(&sci->mutex);189 sci->free_list.push_front(b);190 }191 192 bool PointerIsMine(const void *p) const {193 uptr mem = reinterpret_cast<uptr>(p);194 if (SANITIZER_SIGN_EXTENDED_ADDRESSES)195 mem &= (kSpaceSize - 1);196 if (mem < kSpaceBeg || mem >= kSpaceBeg + kSpaceSize)197 return false;198 return GetSizeClass(p) != 0;199 }200 201 uptr GetSizeClass(const void *p) const {202 uptr id = ComputeRegionId(reinterpret_cast<uptr>(p));203 return possible_regions.contains(id) ? possible_regions[id] : 0;204 }205 206 void *GetBlockBegin(const void *p) {207 CHECK(PointerIsMine(p));208 uptr mem = reinterpret_cast<uptr>(p);209 uptr beg = ComputeRegionBeg(mem);210 uptr size = ClassIdToSize(GetSizeClass(p));211 u32 offset = mem - beg;212 u32 n = offset / (u32)size; // 32-bit division213 uptr res = beg + (n * (u32)size);214 return reinterpret_cast<void*>(res);215 }216 217 uptr GetActuallyAllocatedSize(void *p) {218 CHECK(PointerIsMine(p));219 return ClassIdToSize(GetSizeClass(p));220 }221 222 static uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); }223 224 uptr TotalMemoryUsed() {225 // No need to lock here.226 uptr res = 0;227 for (uptr i = 0; i < kNumPossibleRegions; i++)228 if (possible_regions[i])229 res += kRegionSize;230 return res;231 }232 233 void TestOnlyUnmap() {234 for (uptr i = 0; i < kNumPossibleRegions; i++)235 if (possible_regions[i])236 UnmapWithCallback((i * kRegionSize), kRegionSize);237 }238 239 // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone240 // introspection API.241 void ForceLock() SANITIZER_NO_THREAD_SAFETY_ANALYSIS {242 for (uptr i = 0; i < kNumClasses; i++) {243 GetSizeClassInfo(i)->mutex.Lock();244 }245 }246 247 void ForceUnlock() SANITIZER_NO_THREAD_SAFETY_ANALYSIS {248 for (int i = kNumClasses - 1; i >= 0; i--) {249 GetSizeClassInfo(i)->mutex.Unlock();250 }251 }252 253 // Iterate over all existing chunks.254 // The allocator must be locked when calling this function.255 void ForEachChunk(ForEachChunkCallback callback, void *arg) const {256 for (uptr region = 0; region < kNumPossibleRegions; region++)257 if (possible_regions.contains(region) && possible_regions[region]) {258 uptr chunk_size = ClassIdToSize(possible_regions[region]);259 uptr max_chunks_in_region = kRegionSize / (chunk_size + kMetadataSize);260 uptr region_beg = region * kRegionSize;261 for (uptr chunk = region_beg;262 chunk < region_beg + max_chunks_in_region * chunk_size;263 chunk += chunk_size) {264 // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));265 callback(chunk, arg);266 }267 }268 }269 270 void PrintStats() {}271 272 static uptr AdditionalSize() { return 0; }273 274 typedef SizeClassMap SizeClassMapT;275 static const uptr kNumClasses = SizeClassMap::kNumClasses;276 277 private:278 static const uptr kRegionSize = 1 << kRegionSizeLog;279 static const uptr kNumPossibleRegions = kSpaceSize / kRegionSize;280 281 struct alignas(SANITIZER_CACHE_LINE_SIZE) SizeClassInfo {282 StaticSpinMutex mutex;283 IntrusiveList<TransferBatch> free_list;284 u32 rand_state;285 };286 COMPILER_CHECK(sizeof(SizeClassInfo) % kCacheLineSize == 0);287 288 uptr ComputeRegionId(uptr mem) const {289 if (SANITIZER_SIGN_EXTENDED_ADDRESSES)290 mem &= (kSpaceSize - 1);291 const uptr res = mem >> kRegionSizeLog;292 CHECK_LT(res, kNumPossibleRegions);293 return res;294 }295 296 uptr ComputeRegionBeg(uptr mem) const { return mem & ~(kRegionSize - 1); }297 298 uptr AllocateRegion(AllocatorStats *stat, uptr class_id) {299 DCHECK_LT(class_id, kNumClasses);300 const uptr res = reinterpret_cast<uptr>(MmapAlignedOrDieOnFatalError(301 kRegionSize, kRegionSize, PrimaryAllocatorName));302 if (UNLIKELY(!res))303 return 0;304 MapUnmapCallback().OnMap(res, kRegionSize);305 stat->Add(AllocatorStatMapped, kRegionSize);306 CHECK(IsAligned(res, kRegionSize));307 possible_regions[ComputeRegionId(res)] = class_id;308 return res;309 }310 311 SizeClassInfo *GetSizeClassInfo(uptr class_id) {312 DCHECK_LT(class_id, kNumClasses);313 return &size_class_info_array[class_id];314 }315 316 bool PopulateBatches(AllocatorCache *c, SizeClassInfo *sci, uptr class_id,317 TransferBatch **current_batch, uptr max_count,318 uptr *pointers_array, uptr count) {319 // If using a separate class for batches, we do not need to shuffle it.320 if (kRandomShuffleChunks && (!kUseSeparateSizeClassForBatch ||321 class_id != SizeClassMap::kBatchClassID))322 RandomShuffle(pointers_array, count, &sci->rand_state);323 TransferBatch *b = *current_batch;324 for (uptr i = 0; i < count; i++) {325 if (!b) {326 b = c->CreateBatch(class_id, this, (TransferBatch*)pointers_array[i]);327 if (UNLIKELY(!b))328 return false;329 b->Clear();330 }331 b->Add((void*)pointers_array[i]);332 if (b->Count() == max_count) {333 sci->free_list.push_back(b);334 b = nullptr;335 }336 }337 *current_batch = b;338 return true;339 }340 341 bool PopulateFreeList(AllocatorStats *stat, AllocatorCache *c,342 SizeClassInfo *sci, uptr class_id) {343 const uptr region = AllocateRegion(stat, class_id);344 if (UNLIKELY(!region))345 return false;346 if (kRandomShuffleChunks)347 if (UNLIKELY(sci->rand_state == 0))348 // The random state is initialized from ASLR (PIE) and time.349 sci->rand_state = reinterpret_cast<uptr>(sci) ^ NanoTime();350 const uptr size = ClassIdToSize(class_id);351 const uptr n_chunks = kRegionSize / (size + kMetadataSize);352 const uptr max_count = TransferBatch::MaxCached(size);353 DCHECK_GT(max_count, 0);354 TransferBatch *b = nullptr;355 constexpr uptr kShuffleArraySize = 48;356 UNINITIALIZED uptr shuffle_array[kShuffleArraySize];357 uptr count = 0;358 for (uptr i = region; i < region + n_chunks * size; i += size) {359 shuffle_array[count++] = i;360 if (count == kShuffleArraySize) {361 if (UNLIKELY(!PopulateBatches(c, sci, class_id, &b, max_count,362 shuffle_array, count)))363 return false;364 count = 0;365 }366 }367 if (count) {368 if (UNLIKELY(!PopulateBatches(c, sci, class_id, &b, max_count,369 shuffle_array, count)))370 return false;371 }372 if (b) {373 CHECK_GT(b->Count(), 0);374 sci->free_list.push_back(b);375 }376 return true;377 }378 379 ByteMap possible_regions;380 SizeClassInfo size_class_info_array[kNumClasses];381};382