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

   1 //===-- sanitizer_allocator_primary64.h -------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Part of the Sanitizer Allocator.
  11 //
  12 //===----------------------------------------------------------------------===//
  13 #ifndef SANITIZER_ALLOCATOR_H
  14 #error This file must be included inside sanitizer_allocator.h
  15 #endif
  16
  17 template<class SizeClassAllocator> struct SizeClassAllocator64LocalCache;
  18
  19 // SizeClassAllocator64 -- allocator for 64-bit address space.
  20 // The template parameter Params is a class containing the actual parameters.
  21 //
  22 // Space: a portion of address space of kSpaceSize bytes starting at SpaceBeg.
  23 // If kSpaceBeg is ~0 then SpaceBeg is chosen dynamically my mmap.
  24 // Otherwise SpaceBeg=kSpaceBeg (fixed address).
  25 // kSpaceSize is a power of two.
  26 // At the beginning the entire space is mprotect-ed, then small parts of it
  27 // are mapped on demand.
  28 //
  29 // Region: a part of Space dedicated to a single size class.
  30 // There are kNumClasses Regions of equal size.
  31 //
  32 // UserChunk: a piece of memory returned to user.
  33 // MetaChunk: kMetadataSize bytes of metadata associated with a UserChunk.
  34
  35 // FreeArray is an array free-d chunks (stored as 4-byte offsets)
  36 //
  37 // A Region looks like this:
  38 // UserChunk1 ... UserChunkN <gap> MetaChunkN ... MetaChunk1 FreeArray
  39
  40 struct SizeClassAllocator64FlagMasks {  //  Bit masks.
  41   enum {
  42     kRandomShuffleChunks = 1,
  43   };
  44 };
  45
  46 template <class Params>
  47 class SizeClassAllocator64 {
  48  public:
  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) {
  66     return static_cast<CompactPtrT>((ptr - base) >> kCompactPtrScale);
  67   }
  68   uptr CompactPtrToPointer(uptr base, CompactPtrT ptr32) {
  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_EQ(kSpaceBeg, reinterpret_cast<uptr>(
  76                               MmapFixedNoAccess(kSpaceBeg, TotalSpaceSize)));
  77     } else {
  78       NonConstSpaceBeg =
  79           reinterpret_cast<uptr>(MmapNoAccess(TotalSpaceSize));
  80       CHECK_NE(NonConstSpaceBeg, ~(uptr)0);
  81     }
  82     SetReleaseToOSIntervalMs(release_to_os_interval_ms);
  83     MapWithCallbackOrDie(SpaceEnd(), AdditionalSize());
  84   }
  85
  86   s32 ReleaseToOSIntervalMs() const {
  87     return atomic_load(&release_to_os_interval_ms_, memory_order_relaxed);
  88   }
  89
  90   void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) {
  91     atomic_store(&release_to_os_interval_ms_, release_to_os_interval_ms,
  92                  memory_order_relaxed);
  93   }
  94
  95   static bool CanAllocate(uptr size, uptr alignment) {
  96     return size <= SizeClassMap::kMaxSize &&
  97       alignment <= SizeClassMap::kMaxSize;
  98   }
  99
 100   NOINLINE void ReturnToAllocator(AllocatorStats *stat, uptr class_id,
 101                                   const CompactPtrT *chunks, uptr n_chunks) {
 102     RegionInfo *region = GetRegionInfo(class_id);
 103     uptr region_beg = GetRegionBeginBySizeClass(class_id);
 104     CompactPtrT *free_array = GetFreeArray(region_beg);
 105
 106     BlockingMutexLock l(&region->mutex);
 107     uptr old_num_chunks = region->num_freed_chunks;
 108     uptr new_num_freed_chunks = old_num_chunks + n_chunks;
 109     // Failure to allocate free array space while releasing memory is non
 110     // recoverable.
 111     if (UNLIKELY(!EnsureFreeArraySpace(region, region_beg,
 112                                        new_num_freed_chunks)))
 113       DieOnFailure::OnOOM();
 114     for (uptr i = 0; i < n_chunks; i++)
 115       free_array[old_num_chunks + i] = chunks[i];
 116     region->num_freed_chunks = new_num_freed_chunks;
 117     region->stats.n_freed += n_chunks;
 118
 119     MaybeReleaseToOS(class_id);
 120   }
 121
 122   NOINLINE bool GetFromAllocator(AllocatorStats *stat, uptr class_id,
 123                                  CompactPtrT *chunks, uptr n_chunks) {
 124     RegionInfo *region = GetRegionInfo(class_id);
 125     uptr region_beg = GetRegionBeginBySizeClass(class_id);
 126     CompactPtrT *free_array = GetFreeArray(region_beg);
 127
 128     BlockingMutexLock l(&region->mutex);
 129     if (UNLIKELY(region->num_freed_chunks < n_chunks)) {
 130       if (UNLIKELY(!PopulateFreeArray(stat, class_id, region,
 131                                       n_chunks - region->num_freed_chunks)))
 132         return false;
 133       CHECK_GE(region->num_freed_chunks, n_chunks);
 134     }
 135     region->num_freed_chunks -= n_chunks;
 136     uptr base_idx = region->num_freed_chunks;
 137     for (uptr i = 0; i < n_chunks; i++)
 138       chunks[i] = free_array[base_idx + i];
 139     region->stats.n_allocated += n_chunks;
 140     return true;
 141   }
 142
 143   bool PointerIsMine(const void *p) {
 144     uptr P = reinterpret_cast<uptr>(p);
 145     if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0)
 146       return P / kSpaceSize == kSpaceBeg / kSpaceSize;
 147     return P >= SpaceBeg() && P < SpaceEnd();
 148   }
 149
 150   uptr GetRegionBegin(const void *p) {
 151     if (kUsingConstantSpaceBeg)
 152       return reinterpret_cast<uptr>(p) & ~(kRegionSize - 1);
 153     uptr space_beg = SpaceBeg();
 154     return ((reinterpret_cast<uptr>(p)  - space_beg) & ~(kRegionSize - 1)) +
 155         space_beg;
 156   }
 157
 158   uptr GetRegionBeginBySizeClass(uptr class_id) {
 159     return SpaceBeg() + kRegionSize * class_id;
 160   }
 161
 162   uptr GetSizeClass(const void *p) {
 163     if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0)
 164       return ((reinterpret_cast<uptr>(p)) / kRegionSize) % kNumClassesRounded;
 165     return ((reinterpret_cast<uptr>(p) - SpaceBeg()) / kRegionSize) %
 166            kNumClassesRounded;
 167   }
 168
 169   void *GetBlockBegin(const void *p) {
 170     uptr class_id = GetSizeClass(p);
 171     uptr size = ClassIdToSize(class_id);
 172     if (!size) return nullptr;
 173     uptr chunk_idx = GetChunkIdx((uptr)p, size);
 174     uptr reg_beg = GetRegionBegin(p);
 175     uptr beg = chunk_idx * size;
 176     uptr next_beg = beg + size;
 177     if (class_id >= kNumClasses) return nullptr;
 178     RegionInfo *region = GetRegionInfo(class_id);
 179     if (region->mapped_user >= next_beg)
 180       return reinterpret_cast<void*>(reg_beg + beg);
 181     return nullptr;
 182   }
 183
 184   uptr GetActuallyAllocatedSize(void *p) {
 185     CHECK(PointerIsMine(p));
 186     return ClassIdToSize(GetSizeClass(p));
 187   }
 188
 189   uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); }
 190
 191   void *GetMetaData(const void *p) {
 192     uptr class_id = GetSizeClass(p);
 193     uptr size = ClassIdToSize(class_id);
 194     uptr chunk_idx = GetChunkIdx(reinterpret_cast<uptr>(p), size);
 195     uptr region_beg = GetRegionBeginBySizeClass(class_id);
 196     return reinterpret_cast<void *>(GetMetadataEnd(region_beg) -
 197                                     (1 + chunk_idx) * kMetadataSize);
 198   }
 199
 200   uptr TotalMemoryUsed() {
 201     uptr res = 0;
 202     for (uptr i = 0; i < kNumClasses; i++)
 203       res += GetRegionInfo(i)->allocated_user;
 204     return res;
 205   }
 206
 207   // Test-only.
 208   void TestOnlyUnmap() {
 209     UnmapWithCallbackOrDie(SpaceBeg(), kSpaceSize + AdditionalSize());
 210   }
 211
 212   static void FillMemoryProfile(uptr start, uptr rss, bool file, uptr *stats,
 213                            uptr stats_size) {
 214     for (uptr class_id = 0; class_id < stats_size; class_id++)
 215       if (stats[class_id] == start)
 216         stats[class_id] = rss;
 217   }
 218
 219   void PrintStats(uptr class_id, uptr rss) {
 220     RegionInfo *region = GetRegionInfo(class_id);
 221     if (region->mapped_user == 0) return;
 222     uptr in_use = region->stats.n_allocated - region->stats.n_freed;
 223     uptr avail_chunks = region->allocated_user / ClassIdToSize(class_id);
 224     Printf(
 225         "%s %02zd (%6zd): mapped: %6zdK allocs: %7zd frees: %7zd inuse: %6zd "
 226         "num_freed_chunks %7zd avail: %6zd rss: %6zdK releases: %6zd\n",
 227         region->exhausted ? "F" : " ", class_id, ClassIdToSize(class_id),
 228         region->mapped_user >> 10, region->stats.n_allocated,
 229         region->stats.n_freed, in_use, region->num_freed_chunks, avail_chunks,
 230         rss >> 10, region->rtoi.num_releases);
 231   }
 232
 233   void PrintStats() {
 234     uptr total_mapped = 0;
 235     uptr n_allocated = 0;
 236     uptr n_freed = 0;
 237     for (uptr class_id = 1; class_id < kNumClasses; class_id++) {
 238       RegionInfo *region = GetRegionInfo(class_id);
 239       total_mapped += region->mapped_user;
 240       n_allocated += region->stats.n_allocated;
 241       n_freed += region->stats.n_freed;
 242     }
 243     Printf("Stats: SizeClassAllocator64: %zdM mapped in %zd allocations; "
 244            "remains %zd\n",
 245            total_mapped >> 20, n_allocated, n_allocated - n_freed);
 246     uptr rss_stats[kNumClasses];
 247     for (uptr class_id = 0; class_id < kNumClasses; class_id++)
 248       rss_stats[class_id] = SpaceBeg() + kRegionSize * class_id;
 249     GetMemoryProfile(FillMemoryProfile, rss_stats, kNumClasses);
 250     for (uptr class_id = 1; class_id < kNumClasses; class_id++)
 251       PrintStats(class_id, rss_stats[class_id]);
 252   }
 253
 254   // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
 255   // introspection API.
 256   void ForceLock() {
 257     for (uptr i = 0; i < kNumClasses; i++) {
 258       GetRegionInfo(i)->mutex.Lock();
 259     }
 260   }
 261
 262   void ForceUnlock() {
 263     for (int i = (int)kNumClasses - 1; i >= 0; i--) {
 264       GetRegionInfo(i)->mutex.Unlock();
 265     }
 266   }
 267
 268   // Iterate over all existing chunks.
 269   // The allocator must be locked when calling this function.
 270   void ForEachChunk(ForEachChunkCallback callback, void *arg) {
 271     for (uptr class_id = 1; class_id < kNumClasses; class_id++) {
 272       RegionInfo *region = GetRegionInfo(class_id);
 273       uptr chunk_size = ClassIdToSize(class_id);
 274       uptr region_beg = SpaceBeg() + class_id * kRegionSize;
 275       for (uptr chunk = region_beg;
 276            chunk < region_beg + region->allocated_user;
 277            chunk += chunk_size) {
 278         // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));
 279         callback(chunk, arg);
 280       }
 281     }
 282   }
 283
 284   static uptr ClassIdToSize(uptr class_id) {
 285     return SizeClassMap::Size(class_id);
 286   }
 287
 288   static uptr AdditionalSize() {
 289     return RoundUpTo(sizeof(RegionInfo) * kNumClassesRounded,
 290                      GetPageSizeCached());
 291   }
 292
 293   typedef SizeClassMap SizeClassMapT;
 294   static const uptr kNumClasses = SizeClassMap::kNumClasses;
 295   static const uptr kNumClassesRounded = SizeClassMap::kNumClassesRounded;
 296
 297  private:
 298   static const uptr kRegionSize = kSpaceSize / kNumClassesRounded;
 299   // FreeArray is the array of free-d chunks (stored as 4-byte offsets).
 300   // In the worst case it may reguire kRegionSize/SizeClassMap::kMinSize
 301   // elements, but in reality this will not happen. For simplicity we
 302   // dedicate 1/8 of the region's virtual space to FreeArray.
 303   static const uptr kFreeArraySize = kRegionSize / 8;
 304
 305   static const bool kUsingConstantSpaceBeg = kSpaceBeg != ~(uptr)0;
 306   uptr NonConstSpaceBeg;
 307   uptr SpaceBeg() const {
 308     return kUsingConstantSpaceBeg ? kSpaceBeg : NonConstSpaceBeg;
 309   }
 310   uptr SpaceEnd() const { return  SpaceBeg() + kSpaceSize; }
 311   // kRegionSize must be >= 2^32.
 312   COMPILER_CHECK((kRegionSize) >= (1ULL << (SANITIZER_WORDSIZE / 2)));
 313   // kRegionSize must be <= 2^36, see CompactPtrT.
 314   COMPILER_CHECK((kRegionSize) <= (1ULL << (SANITIZER_WORDSIZE / 2 + 4)));
 315   // Call mmap for user memory with at least this size.
 316   static const uptr kUserMapSize = 1 << 16;
 317   // Call mmap for metadata memory with at least this size.
 318   static const uptr kMetaMapSize = 1 << 16;
 319   // Call mmap for free array memory with at least this size.
 320   static const uptr kFreeArrayMapSize = 1 << 16;
 321
 322   atomic_sint32_t release_to_os_interval_ms_;
 323
 324   struct Stats {
 325     uptr n_allocated;
 326     uptr n_freed;
 327   };
 328
 329   struct ReleaseToOsInfo {
 330     uptr n_freed_at_last_release;
 331     uptr num_releases;
 332     u64 last_release_at_ns;
 333   };
 334
 335   struct RegionInfo {
 336     BlockingMutex mutex;
 337     uptr num_freed_chunks;  // Number of elements in the freearray.
 338     uptr mapped_free_array;  // Bytes mapped for freearray.
 339     uptr allocated_user;  // Bytes allocated for user memory.
 340     uptr allocated_meta;  // Bytes allocated for metadata.
 341     uptr mapped_user;  // Bytes mapped for user memory.
 342     uptr mapped_meta;  // Bytes mapped for metadata.
 343     u32 rand_state;  // Seed for random shuffle, used if kRandomShuffleChunks.
 344     bool exhausted;  // Whether region is out of space for new chunks.
 345     Stats stats;
 346     ReleaseToOsInfo rtoi;
 347   };
 348   COMPILER_CHECK(sizeof(RegionInfo) >= kCacheLineSize);
 349
 350   u32 Rand(u32 *state) {  // ANSI C linear congruential PRNG.
 351     return (*state = *state * 1103515245 + 12345) >> 16;
 352   }
 353
 354   u32 RandN(u32 *state, u32 n) { return Rand(state) % n; }  // [0, n)
 355
 356   void RandomShuffle(u32 *a, u32 n, u32 *rand_state) {
 357     if (n <= 1) return;
 358     for (u32 i = n - 1; i > 0; i--)
 359       Swap(a[i], a[RandN(rand_state, i + 1)]);
 360   }
 361
 362   RegionInfo *GetRegionInfo(uptr class_id) {
 363     CHECK_LT(class_id, kNumClasses);
 364     RegionInfo *regions =
 365         reinterpret_cast<RegionInfo *>(SpaceBeg() + kSpaceSize);
 366     return &regions[class_id];
 367   }
 368
 369   uptr GetMetadataEnd(uptr region_beg) {
 370     return region_beg + kRegionSize - kFreeArraySize;
 371   }
 372
 373   uptr GetChunkIdx(uptr chunk, uptr size) {
 374     if (!kUsingConstantSpaceBeg)
 375       chunk -= SpaceBeg();
 376
 377     uptr offset = chunk % kRegionSize;
 378     // Here we divide by a non-constant. This is costly.
 379     // size always fits into 32-bits. If the offset fits too, use 32-bit div.
 380     if (offset >> (SANITIZER_WORDSIZE / 2))
 381       return offset / size;
 382     return (u32)offset / (u32)size;
 383   }
 384
 385   CompactPtrT *GetFreeArray(uptr region_beg) {
 386     return reinterpret_cast<CompactPtrT *>(region_beg + kRegionSize -
 387                                            kFreeArraySize);
 388   }
 389
 390   bool MapWithCallback(uptr beg, uptr size) {
 391     uptr mapped = reinterpret_cast<uptr>(MmapFixedOrDieOnFatalError(beg, size));
 392     if (UNLIKELY(!mapped))
 393       return false;
 394     CHECK_EQ(beg, mapped);
 395     MapUnmapCallback().OnMap(beg, size);
 396     return true;
 397   }
 398
 399   void MapWithCallbackOrDie(uptr beg, uptr size) {
 400     CHECK_EQ(beg, reinterpret_cast<uptr>(MmapFixedOrDie(beg, size)));
 401     MapUnmapCallback().OnMap(beg, size);
 402   }
 403
 404   void UnmapWithCallbackOrDie(uptr beg, uptr size) {
 405     MapUnmapCallback().OnUnmap(beg, size);
 406     UnmapOrDie(reinterpret_cast<void *>(beg), size);
 407   }
 408
 409   bool EnsureFreeArraySpace(RegionInfo *region, uptr region_beg,
 410                             uptr num_freed_chunks) {
 411     uptr needed_space = num_freed_chunks * sizeof(CompactPtrT);
 412     if (region->mapped_free_array < needed_space) {
 413       CHECK_LE(needed_space, kFreeArraySize);
 414       uptr new_mapped_free_array = RoundUpTo(needed_space, kFreeArrayMapSize);
 415       uptr current_map_end = reinterpret_cast<uptr>(GetFreeArray(region_beg)) +
 416                              region->mapped_free_array;
 417       uptr new_map_size = new_mapped_free_array - region->mapped_free_array;
 418       if (UNLIKELY(!MapWithCallback(current_map_end, new_map_size)))
 419         return false;
 420       region->mapped_free_array = new_mapped_free_array;
 421     }
 422     return true;
 423   }
 424
 425   NOINLINE bool PopulateFreeArray(AllocatorStats *stat, uptr class_id,
 426                                   RegionInfo *region, uptr requested_count) {
 427     // region->mutex is held.
 428     const uptr size = ClassIdToSize(class_id);
 429     const uptr new_space_beg = region->allocated_user;
 430     const uptr new_space_end = new_space_beg + requested_count * size;
 431     const uptr region_beg = GetRegionBeginBySizeClass(class_id);
 432
 433     // Map more space for chunks, if necessary.
 434     if (new_space_end > region->mapped_user) {
 435       if (!kUsingConstantSpaceBeg && region->mapped_user == 0)
 436         region->rand_state = static_cast<u32>(region_beg >> 12);  // From ASLR.
 437       // Do the mmap for the user memory.
 438       uptr map_size = kUserMapSize;
 439       while (new_space_end > region->mapped_user + map_size)
 440         map_size += kUserMapSize;
 441       CHECK_GE(region->mapped_user + map_size, new_space_end);
 442       if (UNLIKELY(!MapWithCallback(region_beg + region->mapped_user,
 443                                     map_size)))
 444         return false;
 445       stat->Add(AllocatorStatMapped, map_size);
 446       region->mapped_user += map_size;
 447     }
 448     const uptr new_chunks_count = (region->mapped_user - new_space_beg) / size;
 449
 450     // Calculate the required space for metadata.
 451     const uptr requested_allocated_meta =
 452         region->allocated_meta + new_chunks_count * kMetadataSize;
 453     uptr requested_mapped_meta = region->mapped_meta;
 454     while (requested_allocated_meta > requested_mapped_meta)
 455       requested_mapped_meta += kMetaMapSize;
 456     // Check whether this size class is exhausted.
 457     if (region->mapped_user + requested_mapped_meta >
 458         kRegionSize - kFreeArraySize) {
 459       if (!region->exhausted) {
 460         region->exhausted = true;
 461         Printf("%s: Out of memory. ", SanitizerToolName);
 462         Printf("The process has exhausted %zuMB for size class %zu.\n",
 463                kRegionSize >> 20, size);
 464       }
 465       return false;
 466     }
 467     // Map more space for metadata, if necessary.
 468     if (requested_mapped_meta > region->mapped_meta) {
 469       if (UNLIKELY(!MapWithCallback(
 470               GetMetadataEnd(region_beg) - requested_mapped_meta,
 471               requested_mapped_meta - region->mapped_meta)))
 472         return false;
 473       region->mapped_meta = requested_mapped_meta;
 474     }
 475
 476     // If necessary, allocate more space for the free array and populate it with
 477     // newly allocated chunks.
 478     const uptr total_freed_chunks = region->num_freed_chunks + new_chunks_count;
 479     if (UNLIKELY(!EnsureFreeArraySpace(region, region_beg, total_freed_chunks)))
 480       return false;
 481     CompactPtrT *free_array = GetFreeArray(region_beg);
 482     for (uptr i = 0, chunk = new_space_beg; i < new_chunks_count;
 483          i++, chunk += size)
 484       free_array[total_freed_chunks - 1 - i] = PointerToCompactPtr(0, chunk);
 485     if (kRandomShuffleChunks)
 486       RandomShuffle(&free_array[region->num_freed_chunks], new_chunks_count,
 487                     &region->rand_state);
 488
 489     // All necessary memory is mapped and now it is safe to advance all
 490     // 'allocated_*' counters.
 491     region->num_freed_chunks += new_chunks_count;
 492     region->allocated_user += new_chunks_count * size;
 493     CHECK_LE(region->allocated_user, region->mapped_user);
 494     region->allocated_meta = requested_allocated_meta;
 495     CHECK_LE(region->allocated_meta, region->mapped_meta);
 496     region->exhausted = false;
 497
 498     return true;
 499   }
 500
 501   void MaybeReleaseChunkRange(uptr region_beg, uptr chunk_size,
 502                               CompactPtrT first, CompactPtrT last) {
 503     uptr beg_ptr = CompactPtrToPointer(region_beg, first);
 504     uptr end_ptr = CompactPtrToPointer(region_beg, last) + chunk_size;
 505     ReleaseMemoryPagesToOS(beg_ptr, end_ptr);
 506   }
 507
 508   // Attempts to release some RAM back to OS. The region is expected to be
 509   // locked.
 510   // Algorithm:
 511   // * Sort the chunks.
 512   // * Find ranges fully covered by free-d chunks
 513   // * Release them to OS with madvise.
 514   void MaybeReleaseToOS(uptr class_id) {
 515     RegionInfo *region = GetRegionInfo(class_id);
 516     const uptr chunk_size = ClassIdToSize(class_id);
 517     const uptr page_size = GetPageSizeCached();
 518
 519     uptr n = region->num_freed_chunks;
 520     if (n * chunk_size < page_size)
 521       return;  // No chance to release anything.
 522     if ((region->stats.n_freed -
 523          region->rtoi.n_freed_at_last_release) * chunk_size < page_size) {
 524       return;  // Nothing new to release.
 525     }
 526
 527     s32 interval_ms = ReleaseToOSIntervalMs();
 528     if (interval_ms < 0)
 529       return;
 530
 531     u64 now_ns = NanoTime();
 532     if (region->rtoi.last_release_at_ns + interval_ms * 1000000ULL > now_ns)
 533       return;  // Memory was returned recently.
 534     region->rtoi.last_release_at_ns = now_ns;
 535
 536     uptr region_beg = GetRegionBeginBySizeClass(class_id);
 537     CompactPtrT *free_array = GetFreeArray(region_beg);
 538     SortArray(free_array, n);
 539
 540     const uptr scaled_chunk_size = chunk_size >> kCompactPtrScale;
 541     const uptr kScaledGranularity = page_size >> kCompactPtrScale;
 542
 543     uptr range_beg = free_array[0];
 544     uptr prev = free_array[0];
 545     for (uptr i = 1; i < n; i++) {
 546       uptr chunk = free_array[i];
 547       CHECK_GT(chunk, prev);
 548       if (chunk - prev != scaled_chunk_size) {
 549         CHECK_GT(chunk - prev, scaled_chunk_size);
 550         if (prev + scaled_chunk_size - range_beg >= kScaledGranularity) {
 551           MaybeReleaseChunkRange(region_beg, chunk_size, range_beg, prev);
 552           region->rtoi.n_freed_at_last_release = region->stats.n_freed;
 553           region->rtoi.num_releases++;
 554         }
 555         range_beg = chunk;
 556       }
 557       prev = chunk;
 558     }
 559   }
 560 };