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