contrib/llvm-project/compiler-rt/lib/sanitizer_common/sanitizer_allocator_primary64.h

   1 //===-- sanitizer_allocator_primary64.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 SizeClassAllocator64LocalCache;
  17
  18 // SizeClassAllocator64 -- allocator for 64-bit address space.
  19 // The template parameter Params is a class containing the actual parameters.
  20 //
  21 // Space: a portion of address space of kSpaceSize bytes starting at SpaceBeg.
  22 // If kSpaceBeg is ~0 then SpaceBeg is chosen dynamically my mmap.
  23 // Otherwise SpaceBeg=kSpaceBeg (fixed address).
  24 // kSpaceSize is a power of two.
  25 // At the beginning the entire space is mprotect-ed, then small parts of it
  26 // are mapped on demand.
  27 //
  28 // Region: a part of Space dedicated to a single size class.
  29 // There are kNumClasses Regions of equal size.
  30 //
  31 // UserChunk: a piece of memory returned to user.
  32 // MetaChunk: kMetadataSize bytes of metadata associated with a UserChunk.
  33
  34 // FreeArray is an array free-d chunks (stored as 4-byte offsets)
  35 //
  36 // A Region looks like this:
  37 // UserChunk1 ... UserChunkN <gap> MetaChunkN ... MetaChunk1 FreeArray
  38
  39 struct SizeClassAllocator64FlagMasks {  //  Bit masks.
  40   enum {
  41     kRandomShuffleChunks = 1,
  42   };
  43 };
  44
  45 template <class Params>
  46 class SizeClassAllocator64 {
  47  public:
  48   using AddressSpaceView = typename Params::AddressSpaceView;
  49   static const uptr kSpaceBeg = Params::kSpaceBeg;
  50   static const uptr kSpaceSize = Params::kSpaceSize;
  51   static const uptr kMetadataSize = Params::kMetadataSize;
  52   typedef typename Params::SizeClassMap SizeClassMap;
  53   typedef typename Params::MapUnmapCallback MapUnmapCallback;
  54
  55   static const bool kRandomShuffleChunks =
  56       Params::kFlags & SizeClassAllocator64FlagMasks::kRandomShuffleChunks;
  57
  58   typedef SizeClassAllocator64<Params> ThisT;
  59   typedef SizeClassAllocator64LocalCache<ThisT> AllocatorCache;
  60
  61   // When we know the size class (the region base) we can represent a pointer
  62   // as a 4-byte integer (offset from the region start shifted right by 4).
  63   typedef u32 CompactPtrT;
  64   static const uptr kCompactPtrScale = 4;
  65   CompactPtrT PointerToCompactPtr(uptr base, uptr ptr) const {
  66     return static_cast<CompactPtrT>((ptr - base) >> kCompactPtrScale);
  67   }
  68   uptr CompactPtrToPointer(uptr base, CompactPtrT ptr32) const {
  69     return base + (static_cast<uptr>(ptr32) << kCompactPtrScale);
  70   }
  71
  72   void Init(s32 release_to_os_interval_ms) {
  73     uptr TotalSpaceSize = kSpaceSize + AdditionalSize();
  74     if (kUsingConstantSpaceBeg) {
  75       CHECK(IsAligned(kSpaceBeg, SizeClassMap::kMaxSize));
  76       CHECK_EQ(kSpaceBeg, address_range.Init(TotalSpaceSize,
  77                                              PrimaryAllocatorName, kSpaceBeg));
  78     } else {
  79       // Combined allocator expects that an 2^N allocation is always aligned to
  80       // 2^N. For this to work, the start of the space needs to be aligned as
  81       // high as the largest size class (which also needs to be a power of 2).
  82       NonConstSpaceBeg = address_range.InitAligned(
  83           TotalSpaceSize, SizeClassMap::kMaxSize, PrimaryAllocatorName);
  84       CHECK_NE(NonConstSpaceBeg, ~(uptr)0);
  85     }
  86     SetReleaseToOSIntervalMs(release_to_os_interval_ms);
  87     MapWithCallbackOrDie(SpaceEnd(), AdditionalSize(),
  88                          "SizeClassAllocator: region info");
  89     // Check that the RegionInfo array is aligned on the CacheLine size.
  90     DCHECK_EQ(SpaceEnd() % kCacheLineSize, 0);
  91   }
  92
  93   s32 ReleaseToOSIntervalMs() const {
  94     return atomic_load(&release_to_os_interval_ms_, memory_order_relaxed);
  95   }
  96
  97   void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) {
  98     atomic_store(&release_to_os_interval_ms_, release_to_os_interval_ms,
  99                  memory_order_relaxed);
 100   }
 101
 102   void ForceReleaseToOS() {
 103     for (uptr class_id = 1; class_id < kNumClasses; class_id++) {
 104       BlockingMutexLock l(&GetRegionInfo(class_id)->mutex);
 105       MaybeReleaseToOS(class_id, true /*force*/);
 106     }
 107   }
 108
 109   static bool CanAllocate(uptr size, uptr alignment) {
 110     return size <= SizeClassMap::kMaxSize &&
 111       alignment <= SizeClassMap::kMaxSize;
 112   }
 113
 114   NOINLINE void ReturnToAllocator(AllocatorStats *stat, uptr class_id,
 115                                   const CompactPtrT *chunks, uptr n_chunks) {
 116     RegionInfo *region = GetRegionInfo(class_id);
 117     uptr region_beg = GetRegionBeginBySizeClass(class_id);
 118     CompactPtrT *free_array = GetFreeArray(region_beg);
 119
 120     BlockingMutexLock l(&region->mutex);
 121     uptr old_num_chunks = region->num_freed_chunks;
 122     uptr new_num_freed_chunks = old_num_chunks + n_chunks;
 123     // Failure to allocate free array space while releasing memory is non
 124     // recoverable.
 125     if (UNLIKELY(!EnsureFreeArraySpace(region, region_beg,
 126                                        new_num_freed_chunks))) {
 127       Report("FATAL: Internal error: %s's allocator exhausted the free list "
 128              "space for size class %zd (%zd bytes).\n", SanitizerToolName,
 129              class_id, ClassIdToSize(class_id));
 130       Die();
 131     }
 132     for (uptr i = 0; i < n_chunks; i++)
 133       free_array[old_num_chunks + i] = chunks[i];
 134     region->num_freed_chunks = new_num_freed_chunks;
 135     region->stats.n_freed += n_chunks;
 136
 137     MaybeReleaseToOS(class_id, false /*force*/);
 138   }
 139
 140   NOINLINE bool GetFromAllocator(AllocatorStats *stat, uptr class_id,
 141                                  CompactPtrT *chunks, uptr n_chunks) {
 142     RegionInfo *region = GetRegionInfo(class_id);
 143     uptr region_beg = GetRegionBeginBySizeClass(class_id);
 144     CompactPtrT *free_array = GetFreeArray(region_beg);
 145
 146     BlockingMutexLock l(&region->mutex);
 147     if (UNLIKELY(region->num_freed_chunks < n_chunks)) {
 148       if (UNLIKELY(!PopulateFreeArray(stat, class_id, region,
 149                                       n_chunks - region->num_freed_chunks)))
 150         return false;
 151       CHECK_GE(region->num_freed_chunks, n_chunks);
 152     }
 153     region->num_freed_chunks -= n_chunks;
 154     uptr base_idx = region->num_freed_chunks;
 155     for (uptr i = 0; i < n_chunks; i++)
 156       chunks[i] = free_array[base_idx + i];
 157     region->stats.n_allocated += n_chunks;
 158     return true;
 159   }
 160
 161   bool PointerIsMine(const void *p) const {
 162     uptr P = reinterpret_cast<uptr>(p);
 163     if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0)
 164       return P / kSpaceSize == kSpaceBeg / kSpaceSize;
 165     return P >= SpaceBeg() && P < SpaceEnd();
 166   }
 167
 168   uptr GetRegionBegin(const void *p) {
 169     if (kUsingConstantSpaceBeg)
 170       return reinterpret_cast<uptr>(p) & ~(kRegionSize - 1);
 171     uptr space_beg = SpaceBeg();
 172     return ((reinterpret_cast<uptr>(p)  - space_beg) & ~(kRegionSize - 1)) +
 173         space_beg;
 174   }
 175
 176   uptr GetRegionBeginBySizeClass(uptr class_id) const {
 177     return SpaceBeg() + kRegionSize * class_id;
 178   }
 179
 180   uptr GetSizeClass(const void *p) {
 181     if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0)
 182       return ((reinterpret_cast<uptr>(p)) / kRegionSize) % kNumClassesRounded;
 183     return ((reinterpret_cast<uptr>(p) - SpaceBeg()) / kRegionSize) %
 184            kNumClassesRounded;
 185   }
 186
 187   void *GetBlockBegin(const void *p) {
 188     uptr class_id = GetSizeClass(p);
 189     uptr size = ClassIdToSize(class_id);
 190     if (!size) return nullptr;
 191     uptr chunk_idx = GetChunkIdx((uptr)p, size);
 192     uptr reg_beg = GetRegionBegin(p);
 193     uptr beg = chunk_idx * size;
 194     uptr next_beg = beg + size;
 195     if (class_id >= kNumClasses) return nullptr;
 196     const RegionInfo *region = AddressSpaceView::Load(GetRegionInfo(class_id));
 197     if (region->mapped_user >= next_beg)
 198       return reinterpret_cast<void*>(reg_beg + beg);
 199     return nullptr;
 200   }
 201
 202   uptr GetActuallyAllocatedSize(void *p) {
 203     CHECK(PointerIsMine(p));
 204     return ClassIdToSize(GetSizeClass(p));
 205   }
 206
 207   static uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); }
 208
 209   void *GetMetaData(const void *p) {
 210     uptr class_id = GetSizeClass(p);
 211     uptr size = ClassIdToSize(class_id);
 212     uptr chunk_idx = GetChunkIdx(reinterpret_cast<uptr>(p), size);
 213     uptr region_beg = GetRegionBeginBySizeClass(class_id);
 214     return reinterpret_cast<void *>(GetMetadataEnd(region_beg) -
 215                                     (1 + chunk_idx) * kMetadataSize);
 216   }
 217
 218   uptr TotalMemoryUsed() {
 219     uptr res = 0;
 220     for (uptr i = 0; i < kNumClasses; i++)
 221       res += GetRegionInfo(i)->allocated_user;
 222     return res;
 223   }
 224
 225   // Test-only.
 226   void TestOnlyUnmap() {
 227     UnmapWithCallbackOrDie((uptr)address_range.base(), address_range.size());
 228   }
 229
 230   static void FillMemoryProfile(uptr start, uptr rss, bool file, uptr *stats,
 231                            uptr stats_size) {
 232     for (uptr class_id = 0; class_id < stats_size; class_id++)
 233       if (stats[class_id] == start)
 234         stats[class_id] = rss;
 235   }
 236
 237   void PrintStats(uptr class_id, uptr rss) {
 238     RegionInfo *region = GetRegionInfo(class_id);
 239     if (region->mapped_user == 0) return;
 240     uptr in_use = region->stats.n_allocated - region->stats.n_freed;
 241     uptr avail_chunks = region->allocated_user / ClassIdToSize(class_id);
 242     Printf(
 243         "%s %02zd (%6zd): mapped: %6zdK allocs: %7zd frees: %7zd inuse: %6zd "
 244         "num_freed_chunks %7zd avail: %6zd rss: %6zdK releases: %6zd "
 245         "last released: %6zdK region: 0x%zx\n",
 246         region->exhausted ? "F" : " ", class_id, ClassIdToSize(class_id),
 247         region->mapped_user >> 10, region->stats.n_allocated,
 248         region->stats.n_freed, in_use, region->num_freed_chunks, avail_chunks,
 249         rss >> 10, region->rtoi.num_releases,
 250         region->rtoi.last_released_bytes >> 10,
 251         SpaceBeg() + kRegionSize * class_id);
 252   }
 253
 254   void PrintStats() {
 255     uptr rss_stats[kNumClasses];
 256     for (uptr class_id = 0; class_id < kNumClasses; class_id++)
 257       rss_stats[class_id] = SpaceBeg() + kRegionSize * class_id;
 258     GetMemoryProfile(FillMemoryProfile, rss_stats, kNumClasses);
 259
 260     uptr total_mapped = 0;
 261     uptr total_rss = 0;
 262     uptr n_allocated = 0;
 263     uptr n_freed = 0;
 264     for (uptr class_id = 1; class_id < kNumClasses; class_id++) {
 265       RegionInfo *region = GetRegionInfo(class_id);
 266       if (region->mapped_user != 0) {
 267         total_mapped += region->mapped_user;
 268         total_rss += rss_stats[class_id];
 269       }
 270       n_allocated += region->stats.n_allocated;
 271       n_freed += region->stats.n_freed;
 272     }
 273
 274     Printf("Stats: SizeClassAllocator64: %zdM mapped (%zdM rss) in "
 275            "%zd allocations; remains %zd\n", total_mapped >> 20,
 276            total_rss >> 20, n_allocated, n_allocated - n_freed);
 277     for (uptr class_id = 1; class_id < kNumClasses; class_id++)
 278       PrintStats(class_id, rss_stats[class_id]);
 279   }
 280
 281   // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
 282   // introspection API.
 283   void ForceLock() {
 284     for (uptr i = 0; i < kNumClasses; i++) {
 285       GetRegionInfo(i)->mutex.Lock();
 286     }
 287   }
 288
 289   void ForceUnlock() {
 290     for (int i = (int)kNumClasses - 1; i >= 0; i--) {
 291       GetRegionInfo(i)->mutex.Unlock();
 292     }
 293   }
 294
 295   // Iterate over all existing chunks.
 296   // The allocator must be locked when calling this function.
 297   void ForEachChunk(ForEachChunkCallback callback, void *arg) {
 298     for (uptr class_id = 1; class_id < kNumClasses; class_id++) {
 299       RegionInfo *region = GetRegionInfo(class_id);
 300       uptr chunk_size = ClassIdToSize(class_id);
 301       uptr region_beg = SpaceBeg() + class_id * kRegionSize;
 302       uptr region_allocated_user_size =
 303           AddressSpaceView::Load(region)->allocated_user;
 304       for (uptr chunk = region_beg;
 305            chunk < region_beg + region_allocated_user_size;
 306            chunk += chunk_size) {
 307         // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));
 308         callback(chunk, arg);
 309       }
 310     }
 311   }
 312
 313   static uptr ClassIdToSize(uptr class_id) {
 314     return SizeClassMap::Size(class_id);
 315   }
 316
 317   static uptr AdditionalSize() {
 318     return RoundUpTo(sizeof(RegionInfo) * kNumClassesRounded,
 319                      GetPageSizeCached());
 320   }
 321
 322   typedef SizeClassMap SizeClassMapT;
 323   static const uptr kNumClasses = SizeClassMap::kNumClasses;
 324   static const uptr kNumClassesRounded = SizeClassMap::kNumClassesRounded;
 325
 326   // A packed array of counters. Each counter occupies 2^n bits, enough to store
 327   // counter's max_value. Ctor will try to allocate the required buffer via
 328   // mapper->MapPackedCounterArrayBuffer and the caller is expected to check
 329   // whether the initialization was successful by checking IsAllocated() result.
 330   // For the performance sake, none of the accessors check the validity of the
 331   // arguments, it is assumed that index is always in [0, n) range and the value
 332   // is not incremented past max_value.
 333   template<class MemoryMapperT>
 334   class PackedCounterArray {
 335    public:
 336     PackedCounterArray(u64 num_counters, u64 max_value, MemoryMapperT *mapper)
 337         : n(num_counters), memory_mapper(mapper) {
 338       CHECK_GT(num_counters, 0);
 339       CHECK_GT(max_value, 0);
 340       constexpr u64 kMaxCounterBits = sizeof(*buffer) * 8ULL;
 341       // Rounding counter storage size up to the power of two allows for using
 342       // bit shifts calculating particular counter's index and offset.
 343       uptr counter_size_bits =
 344           RoundUpToPowerOfTwo(MostSignificantSetBitIndex(max_value) + 1);
 345       CHECK_LE(counter_size_bits, kMaxCounterBits);
 346       counter_size_bits_log = Log2(counter_size_bits);
 347       counter_mask = ~0ULL >> (kMaxCounterBits - counter_size_bits);
 348
 349       uptr packing_ratio = kMaxCounterBits >> counter_size_bits_log;
 350       CHECK_GT(packing_ratio, 0);
 351       packing_ratio_log = Log2(packing_ratio);
 352       bit_offset_mask = packing_ratio - 1;
 353
 354       buffer_size =
 355           (RoundUpTo(n, 1ULL << packing_ratio_log) >> packing_ratio_log) *
 356           sizeof(*buffer);
 357       buffer = reinterpret_cast<u64*>(
 358           memory_mapper->MapPackedCounterArrayBuffer(buffer_size));
 359     }
 360     ~PackedCounterArray() {
 361       if (buffer) {
 362         memory_mapper->UnmapPackedCounterArrayBuffer(
 363             reinterpret_cast<uptr>(buffer), buffer_size);
 364       }
 365     }
 366
 367     bool IsAllocated() const {
 368       return !!buffer;
 369     }
 370
 371     u64 GetCount() const {
 372       return n;
 373     }
 374
 375     uptr Get(uptr i) const {
 376       DCHECK_LT(i, n);
 377       uptr index = i >> packing_ratio_log;
 378       uptr bit_offset = (i & bit_offset_mask) << counter_size_bits_log;
 379       return (buffer[index] >> bit_offset) & counter_mask;
 380     }
 381
 382     void Inc(uptr i) const {
 383       DCHECK_LT(Get(i), counter_mask);
 384       uptr index = i >> packing_ratio_log;
 385       uptr bit_offset = (i & bit_offset_mask) << counter_size_bits_log;
 386       buffer[index] += 1ULL << bit_offset;
 387     }
 388
 389     void IncRange(uptr from, uptr to) const {
 390       DCHECK_LE(from, to);
 391       for (uptr i = from; i <= to; i++)
 392         Inc(i);
 393     }
 394
 395    private:
 396     const u64 n;
 397     u64 counter_size_bits_log;
 398     u64 counter_mask;
 399     u64 packing_ratio_log;
 400     u64 bit_offset_mask;
 401
 402     MemoryMapperT* const memory_mapper;
 403     u64 buffer_size;
 404     u64* buffer;
 405   };
 406
 407   template<class MemoryMapperT>
 408   class FreePagesRangeTracker {
 409    public:
 410     explicit FreePagesRangeTracker(MemoryMapperT* mapper)
 411         : memory_mapper(mapper),
 412           page_size_scaled_log(Log2(GetPageSizeCached() >> kCompactPtrScale)),
 413           in_the_range(false), current_page(0), current_range_start_page(0) {}
 414
 415     void NextPage(bool freed) {
 416       if (freed) {
 417         if (!in_the_range) {
 418           current_range_start_page = current_page;
 419           in_the_range = true;
 420         }
 421       } else {
 422         CloseOpenedRange();
 423       }
 424       current_page++;
 425     }
 426
 427     void Done() {
 428       CloseOpenedRange();
 429     }
 430
 431    private:
 432     void CloseOpenedRange() {
 433       if (in_the_range) {
 434         memory_mapper->ReleasePageRangeToOS(
 435             current_range_start_page << page_size_scaled_log,
 436             current_page << page_size_scaled_log);
 437         in_the_range = false;
 438       }
 439     }
 440
 441     MemoryMapperT* const memory_mapper;
 442     const uptr page_size_scaled_log;
 443     bool in_the_range;
 444     uptr current_page;
 445     uptr current_range_start_page;
 446   };
 447
 448   // Iterates over the free_array to identify memory pages containing freed
 449   // chunks only and returns these pages back to OS.
 450   // allocated_pages_count is the total number of pages allocated for the
 451   // current bucket.
 452   template<class MemoryMapperT>
 453   static void ReleaseFreeMemoryToOS(CompactPtrT *free_array,
 454                                     uptr free_array_count, uptr chunk_size,
 455                                     uptr allocated_pages_count,
 456                                     MemoryMapperT *memory_mapper) {
 457     const uptr page_size = GetPageSizeCached();
 458
 459     // Figure out the number of chunks per page and whether we can take a fast
 460     // path (the number of chunks per page is the same for all pages).
 461     uptr full_pages_chunk_count_max;
 462     bool same_chunk_count_per_page;
 463     if (chunk_size <= page_size && page_size % chunk_size == 0) {
 464       // Same number of chunks per page, no cross overs.
 465       full_pages_chunk_count_max = page_size / chunk_size;
 466       same_chunk_count_per_page = true;
 467     } else if (chunk_size <= page_size && page_size % chunk_size != 0 &&
 468         chunk_size % (page_size % chunk_size) == 0) {
 469       // Some chunks are crossing page boundaries, which means that the page
 470       // contains one or two partial chunks, but all pages contain the same
 471       // number of chunks.
 472       full_pages_chunk_count_max = page_size / chunk_size + 1;
 473       same_chunk_count_per_page = true;
 474     } else if (chunk_size <= page_size) {
 475       // Some chunks are crossing page boundaries, which means that the page
 476       // contains one or two partial chunks.
 477       full_pages_chunk_count_max = page_size / chunk_size + 2;
 478       same_chunk_count_per_page = false;
 479     } else if (chunk_size > page_size && chunk_size % page_size == 0) {
 480       // One chunk covers multiple pages, no cross overs.
 481       full_pages_chunk_count_max = 1;
 482       same_chunk_count_per_page = true;
 483     } else if (chunk_size > page_size) {
 484       // One chunk covers multiple pages, Some chunks are crossing page
 485       // boundaries. Some pages contain one chunk, some contain two.
 486       full_pages_chunk_count_max = 2;
 487       same_chunk_count_per_page = false;
 488     } else {
 489       UNREACHABLE("All chunk_size/page_size ratios must be handled.");
 490     }
 491
 492     PackedCounterArray<MemoryMapperT> counters(allocated_pages_count,
 493                                                full_pages_chunk_count_max,
 494                                                memory_mapper);
 495     if (!counters.IsAllocated())
 496       return;
 497
 498     const uptr chunk_size_scaled = chunk_size >> kCompactPtrScale;
 499     const uptr page_size_scaled = page_size >> kCompactPtrScale;
 500     const uptr page_size_scaled_log = Log2(page_size_scaled);
 501
 502     // Iterate over free chunks and count how many free chunks affect each
 503     // allocated page.
 504     if (chunk_size <= page_size && page_size % chunk_size == 0) {
 505       // Each chunk affects one page only.
 506       for (uptr i = 0; i < free_array_count; i++)
 507         counters.Inc(free_array[i] >> page_size_scaled_log);
 508     } else {
 509       // In all other cases chunks might affect more than one page.
 510       for (uptr i = 0; i < free_array_count; i++) {
 511         counters.IncRange(
 512             free_array[i] >> page_size_scaled_log,
 513             (free_array[i] + chunk_size_scaled - 1) >> page_size_scaled_log);
 514       }
 515     }
 516
 517     // Iterate over pages detecting ranges of pages with chunk counters equal
 518     // to the expected number of chunks for the particular page.
 519     FreePagesRangeTracker<MemoryMapperT> range_tracker(memory_mapper);
 520     if (same_chunk_count_per_page) {
 521       // Fast path, every page has the same number of chunks affecting it.
 522       for (uptr i = 0; i < counters.GetCount(); i++)
 523         range_tracker.NextPage(counters.Get(i) == full_pages_chunk_count_max);
 524     } else {
 525       // Show path, go through the pages keeping count how many chunks affect
 526       // each page.
 527       const uptr pn =
 528           chunk_size < page_size ? page_size_scaled / chunk_size_scaled : 1;
 529       const uptr pnc = pn * chunk_size_scaled;
 530       // The idea is to increment the current page pointer by the first chunk
 531       // size, middle portion size (the portion of the page covered by chunks
 532       // except the first and the last one) and then the last chunk size, adding
 533       // up the number of chunks on the current page and checking on every step
 534       // whether the page boundary was crossed.
 535       uptr prev_page_boundary = 0;
 536       uptr current_boundary = 0;
 537       for (uptr i = 0; i < counters.GetCount(); i++) {
 538         uptr page_boundary = prev_page_boundary + page_size_scaled;
 539         uptr chunks_per_page = pn;
 540         if (current_boundary < page_boundary) {
 541           if (current_boundary > prev_page_boundary)
 542             chunks_per_page++;
 543           current_boundary += pnc;
 544           if (current_boundary < page_boundary) {
 545             chunks_per_page++;
 546             current_boundary += chunk_size_scaled;
 547           }
 548         }
 549         prev_page_boundary = page_boundary;
 550
 551         range_tracker.NextPage(counters.Get(i) == chunks_per_page);
 552       }
 553     }
 554     range_tracker.Done();
 555   }
 556
 557  private:
 558   friend class MemoryMapper;
 559
 560   ReservedAddressRange address_range;
 561
 562   static const uptr kRegionSize = kSpaceSize / kNumClassesRounded;
 563   // FreeArray is the array of free-d chunks (stored as 4-byte offsets).
 564   // In the worst case it may reguire kRegionSize/SizeClassMap::kMinSize
 565   // elements, but in reality this will not happen. For simplicity we
 566   // dedicate 1/8 of the region's virtual space to FreeArray.
 567   static const uptr kFreeArraySize = kRegionSize / 8;
 568
 569   static const bool kUsingConstantSpaceBeg = kSpaceBeg != ~(uptr)0;
 570   uptr NonConstSpaceBeg;
 571   uptr SpaceBeg() const {
 572     return kUsingConstantSpaceBeg ? kSpaceBeg : NonConstSpaceBeg;
 573   }
 574   uptr SpaceEnd() const { return  SpaceBeg() + kSpaceSize; }
 575   // kRegionSize must be >= 2^32.
 576   COMPILER_CHECK((kRegionSize) >= (1ULL << (SANITIZER_WORDSIZE / 2)));
 577   // kRegionSize must be <= 2^36, see CompactPtrT.
 578   COMPILER_CHECK((kRegionSize) <= (1ULL << (SANITIZER_WORDSIZE / 2 + 4)));
 579   // Call mmap for user memory with at least this size.
 580   static const uptr kUserMapSize = 1 << 16;
 581   // Call mmap for metadata memory with at least this size.
 582   static const uptr kMetaMapSize = 1 << 16;
 583   // Call mmap for free array memory with at least this size.
 584   static const uptr kFreeArrayMapSize = 1 << 16;
 585
 586   atomic_sint32_t release_to_os_interval_ms_;
 587
 588   struct Stats {
 589     uptr n_allocated;
 590     uptr n_freed;
 591   };
 592
 593   struct ReleaseToOsInfo {
 594     uptr n_freed_at_last_release;
 595     uptr num_releases;
 596     u64 last_release_at_ns;
 597     u64 last_released_bytes;
 598   };
 599
 600   struct ALIGNED(SANITIZER_CACHE_LINE_SIZE) RegionInfo {
 601     BlockingMutex mutex;
 602     uptr num_freed_chunks;  // Number of elements in the freearray.
 603     uptr mapped_free_array;  // Bytes mapped for freearray.
 604     uptr allocated_user;  // Bytes allocated for user memory.
 605     uptr allocated_meta;  // Bytes allocated for metadata.
 606     uptr mapped_user;  // Bytes mapped for user memory.
 607     uptr mapped_meta;  // Bytes mapped for metadata.
 608     u32 rand_state;  // Seed for random shuffle, used if kRandomShuffleChunks.
 609     bool exhausted;  // Whether region is out of space for new chunks.
 610     Stats stats;
 611     ReleaseToOsInfo rtoi;
 612   };
 613   COMPILER_CHECK(sizeof(RegionInfo) % kCacheLineSize == 0);
 614
 615   RegionInfo *GetRegionInfo(uptr class_id) const {
 616     DCHECK_LT(class_id, kNumClasses);
 617     RegionInfo *regions = reinterpret_cast<RegionInfo *>(SpaceEnd());
 618     return &regions[class_id];
 619   }
 620
 621   uptr GetMetadataEnd(uptr region_beg) const {
 622     return region_beg + kRegionSize - kFreeArraySize;
 623   }
 624
 625   uptr GetChunkIdx(uptr chunk, uptr size) const {
 626     if (!kUsingConstantSpaceBeg)
 627       chunk -= SpaceBeg();
 628
 629     uptr offset = chunk % kRegionSize;
 630     // Here we divide by a non-constant. This is costly.
 631     // size always fits into 32-bits. If the offset fits too, use 32-bit div.
 632     if (offset >> (SANITIZER_WORDSIZE / 2))
 633       return offset / size;
 634     return (u32)offset / (u32)size;
 635   }
 636
 637   CompactPtrT *GetFreeArray(uptr region_beg) const {
 638     return reinterpret_cast<CompactPtrT *>(GetMetadataEnd(region_beg));
 639   }
 640
 641   bool MapWithCallback(uptr beg, uptr size, const char *name) {
 642     uptr mapped = address_range.Map(beg, size, name);
 643     if (UNLIKELY(!mapped))
 644       return false;
 645     CHECK_EQ(beg, mapped);
 646     MapUnmapCallback().OnMap(beg, size);
 647     return true;
 648   }
 649
 650   void MapWithCallbackOrDie(uptr beg, uptr size, const char *name) {
 651     CHECK_EQ(beg, address_range.MapOrDie(beg, size, name));
 652     MapUnmapCallback().OnMap(beg, size);
 653   }
 654
 655   void UnmapWithCallbackOrDie(uptr beg, uptr size) {
 656     MapUnmapCallback().OnUnmap(beg, size);
 657     address_range.Unmap(beg, size);
 658   }
 659
 660   bool EnsureFreeArraySpace(RegionInfo *region, uptr region_beg,
 661                             uptr num_freed_chunks) {
 662     uptr needed_space = num_freed_chunks * sizeof(CompactPtrT);
 663     if (region->mapped_free_array < needed_space) {
 664       uptr new_mapped_free_array = RoundUpTo(needed_space, kFreeArrayMapSize);
 665       CHECK_LE(new_mapped_free_array, kFreeArraySize);
 666       uptr current_map_end = reinterpret_cast<uptr>(GetFreeArray(region_beg)) +
 667                              region->mapped_free_array;
 668       uptr new_map_size = new_mapped_free_array - region->mapped_free_array;
 669       if (UNLIKELY(!MapWithCallback(current_map_end, new_map_size,
 670                                     "SizeClassAllocator: freearray")))
 671         return false;
 672       region->mapped_free_array = new_mapped_free_array;
 673     }
 674     return true;
 675   }
 676
 677   // Check whether this size class is exhausted.
 678   bool IsRegionExhausted(RegionInfo *region, uptr class_id,
 679                          uptr additional_map_size) {
 680     if (LIKELY(region->mapped_user + region->mapped_meta +
 681                additional_map_size <= kRegionSize - kFreeArraySize))
 682       return false;
 683     if (!region->exhausted) {
 684       region->exhausted = true;
 685       Printf("%s: Out of memory. ", SanitizerToolName);
 686       Printf("The process has exhausted %zuMB for size class %zu.\n",
 687              kRegionSize >> 20, ClassIdToSize(class_id));
 688     }
 689     return true;
 690   }
 691
 692   NOINLINE bool PopulateFreeArray(AllocatorStats *stat, uptr class_id,
 693                                   RegionInfo *region, uptr requested_count) {
 694     // region->mutex is held.
 695     const uptr region_beg = GetRegionBeginBySizeClass(class_id);
 696     const uptr size = ClassIdToSize(class_id);
 697
 698     const uptr total_user_bytes =
 699         region->allocated_user + requested_count * size;
 700     // Map more space for chunks, if necessary.
 701     if (LIKELY(total_user_bytes > region->mapped_user)) {
 702       if (UNLIKELY(region->mapped_user == 0)) {
 703         if (!kUsingConstantSpaceBeg && kRandomShuffleChunks)
 704           // The random state is initialized from ASLR.
 705           region->rand_state = static_cast<u32>(region_beg >> 12);
 706         // Postpone the first release to OS attempt for ReleaseToOSIntervalMs,
 707         // preventing just allocated memory from being released sooner than
 708         // necessary and also preventing extraneous ReleaseMemoryPagesToOS calls
 709         // for short lived processes.
 710         // Do it only when the feature is turned on, to avoid a potentially
 711         // extraneous syscall.
 712         if (ReleaseToOSIntervalMs() >= 0)
 713           region->rtoi.last_release_at_ns = MonotonicNanoTime();
 714       }
 715       // Do the mmap for the user memory.
 716       const uptr user_map_size =
 717           RoundUpTo(total_user_bytes - region->mapped_user, kUserMapSize);
 718       if (UNLIKELY(IsRegionExhausted(region, class_id, user_map_size)))
 719         return false;
 720       if (UNLIKELY(!MapWithCallback(region_beg + region->mapped_user,
 721                                     user_map_size,
 722                                     "SizeClassAllocator: region data")))
 723         return false;
 724       stat->Add(AllocatorStatMapped, user_map_size);
 725       region->mapped_user += user_map_size;
 726     }
 727     const uptr new_chunks_count =
 728         (region->mapped_user - region->allocated_user) / size;
 729
 730     if (kMetadataSize) {
 731       // Calculate the required space for metadata.
 732       const uptr total_meta_bytes =
 733           region->allocated_meta + new_chunks_count * kMetadataSize;
 734       const uptr meta_map_size = (total_meta_bytes > region->mapped_meta) ?
 735           RoundUpTo(total_meta_bytes - region->mapped_meta, kMetaMapSize) : 0;
 736       // Map more space for metadata, if necessary.
 737       if (meta_map_size) {
 738         if (UNLIKELY(IsRegionExhausted(region, class_id, meta_map_size)))
 739           return false;
 740         if (UNLIKELY(!MapWithCallback(
 741             GetMetadataEnd(region_beg) - region->mapped_meta - meta_map_size,
 742             meta_map_size, "SizeClassAllocator: region metadata")))
 743           return false;
 744         region->mapped_meta += meta_map_size;
 745       }
 746     }
 747
 748     // If necessary, allocate more space for the free array and populate it with
 749     // newly allocated chunks.
 750     const uptr total_freed_chunks = region->num_freed_chunks + new_chunks_count;
 751     if (UNLIKELY(!EnsureFreeArraySpace(region, region_beg, total_freed_chunks)))
 752       return false;
 753     CompactPtrT *free_array = GetFreeArray(region_beg);
 754     for (uptr i = 0, chunk = region->allocated_user; i < new_chunks_count;
 755          i++, chunk += size)
 756       free_array[total_freed_chunks - 1 - i] = PointerToCompactPtr(0, chunk);
 757     if (kRandomShuffleChunks)
 758       RandomShuffle(&free_array[region->num_freed_chunks], new_chunks_count,
 759                     &region->rand_state);
 760
 761     // All necessary memory is mapped and now it is safe to advance all
 762     // 'allocated_*' counters.
 763     region->num_freed_chunks += new_chunks_count;
 764     region->allocated_user += new_chunks_count * size;
 765     CHECK_LE(region->allocated_user, region->mapped_user);
 766     region->allocated_meta += new_chunks_count * kMetadataSize;
 767     CHECK_LE(region->allocated_meta, region->mapped_meta);
 768     region->exhausted = false;
 769
 770     // TODO(alekseyshl): Consider bumping last_release_at_ns here to prevent
 771     // MaybeReleaseToOS from releasing just allocated pages or protect these
 772     // not yet used chunks some other way.
 773
 774     return true;
 775   }
 776
 777   class MemoryMapper {
 778    public:
 779     MemoryMapper(const ThisT& base_allocator, uptr class_id)
 780         : allocator(base_allocator),
 781           region_base(base_allocator.GetRegionBeginBySizeClass(class_id)),
 782           released_ranges_count(0),
 783           released_bytes(0) {
 784     }
 785
 786     uptr GetReleasedRangesCount() const {
 787       return released_ranges_count;
 788     }
 789
 790     uptr GetReleasedBytes() const {
 791       return released_bytes;
 792     }
 793
 794     uptr MapPackedCounterArrayBuffer(uptr buffer_size) {
 795       // TODO(alekseyshl): The idea to explore is to check if we have enough
 796       // space between num_freed_chunks*sizeof(CompactPtrT) and
 797       // mapped_free_array to fit buffer_size bytes and use that space instead
 798       // of mapping a temporary one.
 799       return reinterpret_cast<uptr>(
 800           MmapOrDieOnFatalError(buffer_size, "ReleaseToOSPageCounters"));
 801     }
 802
 803     void UnmapPackedCounterArrayBuffer(uptr buffer, uptr buffer_size) {
 804       UnmapOrDie(reinterpret_cast<void *>(buffer), buffer_size);
 805     }
 806
 807     // Releases [from, to) range of pages back to OS.
 808     void ReleasePageRangeToOS(CompactPtrT from, CompactPtrT to) {
 809       const uptr from_page = allocator.CompactPtrToPointer(region_base, from);
 810       const uptr to_page = allocator.CompactPtrToPointer(region_base, to);
 811       ReleaseMemoryPagesToOS(from_page, to_page);
 812       released_ranges_count++;
 813       released_bytes += to_page - from_page;
 814     }
 815
 816    private:
 817     const ThisT& allocator;
 818     const uptr region_base;
 819     uptr released_ranges_count;
 820     uptr released_bytes;
 821   };
 822
 823   // Attempts to release RAM occupied by freed chunks back to OS. The region is
 824   // expected to be locked.
 825   void MaybeReleaseToOS(uptr class_id, bool force) {
 826     RegionInfo *region = GetRegionInfo(class_id);
 827     const uptr chunk_size = ClassIdToSize(class_id);
 828     const uptr page_size = GetPageSizeCached();
 829
 830     uptr n = region->num_freed_chunks;
 831     if (n * chunk_size < page_size)
 832       return;  // No chance to release anything.
 833     if ((region->stats.n_freed -
 834          region->rtoi.n_freed_at_last_release) * chunk_size < page_size) {
 835       return;  // Nothing new to release.
 836     }
 837
 838     if (!force) {
 839       s32 interval_ms = ReleaseToOSIntervalMs();
 840       if (interval_ms < 0)
 841         return;
 842
 843       if (region->rtoi.last_release_at_ns + interval_ms * 1000000ULL >
 844           MonotonicNanoTime()) {
 845         return;  // Memory was returned recently.
 846       }
 847     }
 848
 849     MemoryMapper memory_mapper(*this, class_id);
 850
 851     ReleaseFreeMemoryToOS<MemoryMapper>(
 852         GetFreeArray(GetRegionBeginBySizeClass(class_id)), n, chunk_size,
 853         RoundUpTo(region->allocated_user, page_size) / page_size,
 854         &memory_mapper);
 855
 856     if (memory_mapper.GetReleasedRangesCount() > 0) {
 857       region->rtoi.n_freed_at_last_release = region->stats.n_freed;
 858       region->rtoi.num_releases += memory_mapper.GetReleasedRangesCount();
 859       region->rtoi.last_released_bytes = memory_mapper.GetReleasedBytes();
 860     }
 861     region->rtoi.last_release_at_ns = MonotonicNanoTime();
 862   }
 863 };