libsanitizer/sanitizer_common/sanitizer_allocator_primary64.h

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