contrib/compiler-rt/lib/scudo/scudo_allocator.cpp

   1 //===-- scudo_allocator.cpp -------------------------------------*- 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 /// Scudo Hardened Allocator implementation.
  11 /// It uses the sanitizer_common allocator as a base and aims at mitigating
  12 /// heap corruption vulnerabilities. It provides a checksum-guarded chunk
  13 /// header, a delayed free list, and additional sanity checks.
  14 ///
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "scudo_allocator.h"
  18 #include "scudo_crc32.h"
  19 #include "scudo_errors.h"
  20 #include "scudo_flags.h"
  21 #include "scudo_interface_internal.h"
  22 #include "scudo_tsd.h"
  23 #include "scudo_utils.h"
  24
  25 #include "sanitizer_common/sanitizer_allocator_checks.h"
  26 #include "sanitizer_common/sanitizer_allocator_interface.h"
  27 #include "sanitizer_common/sanitizer_quarantine.h"
  28
  29 #include <errno.h>
  30 #include <string.h>
  31
  32 namespace __scudo {
  33
  34 // Global static cookie, initialized at start-up.
  35 static u32 Cookie;
  36
  37 // We default to software CRC32 if the alternatives are not supported, either
  38 // at compilation or at runtime.
  39 static atomic_uint8_t HashAlgorithm = { CRC32Software };
  40
  41 INLINE u32 computeCRC32(u32 Crc, uptr Value, uptr *Array, uptr ArraySize) {
  42   // If the hardware CRC32 feature is defined here, it was enabled everywhere,
  43   // as opposed to only for scudo_crc32.cpp. This means that other hardware
  44   // specific instructions were likely emitted at other places, and as a
  45   // result there is no reason to not use it here.
  46 #if defined(__SSE4_2__) || defined(__ARM_FEATURE_CRC32)
  47   Crc = CRC32_INTRINSIC(Crc, Value);
  48   for (uptr i = 0; i < ArraySize; i++)
  49     Crc = CRC32_INTRINSIC(Crc, Array[i]);
  50   return Crc;
  51 #else
  52   if (atomic_load_relaxed(&HashAlgorithm) == CRC32Hardware) {
  53     Crc = computeHardwareCRC32(Crc, Value);
  54     for (uptr i = 0; i < ArraySize; i++)
  55       Crc = computeHardwareCRC32(Crc, Array[i]);
  56     return Crc;
  57   }
  58   Crc = computeSoftwareCRC32(Crc, Value);
  59   for (uptr i = 0; i < ArraySize; i++)
  60     Crc = computeSoftwareCRC32(Crc, Array[i]);
  61   return Crc;
  62 #endif  // defined(__SSE4_2__) || defined(__ARM_FEATURE_CRC32)
  63 }
  64
  65 static BackendT &getBackend();
  66
  67 namespace Chunk {
  68   static INLINE AtomicPackedHeader *getAtomicHeader(void *Ptr) {
  69     return reinterpret_cast<AtomicPackedHeader *>(reinterpret_cast<uptr>(Ptr) -
  70         getHeaderSize());
  71   }
  72   static INLINE
  73   const AtomicPackedHeader *getConstAtomicHeader(const void *Ptr) {
  74     return reinterpret_cast<const AtomicPackedHeader *>(
  75         reinterpret_cast<uptr>(Ptr) - getHeaderSize());
  76   }
  77
  78   static INLINE bool isAligned(const void *Ptr) {
  79     return IsAligned(reinterpret_cast<uptr>(Ptr), MinAlignment);
  80   }
  81
  82   // We can't use the offset member of the chunk itself, as we would double
  83   // fetch it without any warranty that it wouldn't have been tampered. To
  84   // prevent this, we work with a local copy of the header.
  85   static INLINE void *getBackendPtr(const void *Ptr, UnpackedHeader *Header) {
  86     return reinterpret_cast<void *>(reinterpret_cast<uptr>(Ptr) -
  87         getHeaderSize() - (Header->Offset << MinAlignmentLog));
  88   }
  89
  90   // Returns the usable size for a chunk, meaning the amount of bytes from the
  91   // beginning of the user data to the end of the backend allocated chunk.
  92   static INLINE uptr getUsableSize(const void *Ptr, UnpackedHeader *Header) {
  93     const uptr ClassId = Header->ClassId;
  94     if (ClassId)
  95       return PrimaryT::ClassIdToSize(ClassId) - getHeaderSize() -
  96           (Header->Offset << MinAlignmentLog);
  97     return SecondaryT::GetActuallyAllocatedSize(
  98         getBackendPtr(Ptr, Header)) - getHeaderSize();
  99   }
 100
 101   // Returns the size the user requested when allocating the chunk.
 102   static INLINE uptr getSize(const void *Ptr, UnpackedHeader *Header) {
 103     const uptr SizeOrUnusedBytes = Header->SizeOrUnusedBytes;
 104     if (Header->ClassId)
 105       return SizeOrUnusedBytes;
 106     return SecondaryT::GetActuallyAllocatedSize(
 107         getBackendPtr(Ptr, Header)) - getHeaderSize() - SizeOrUnusedBytes;
 108   }
 109
 110   // Compute the checksum of the chunk pointer and its header.
 111   static INLINE u16 computeChecksum(const void *Ptr, UnpackedHeader *Header) {
 112     UnpackedHeader ZeroChecksumHeader = *Header;
 113     ZeroChecksumHeader.Checksum = 0;
 114     uptr HeaderHolder[sizeof(UnpackedHeader) / sizeof(uptr)];
 115     memcpy(&HeaderHolder, &ZeroChecksumHeader, sizeof(HeaderHolder));
 116     const u32 Crc = computeCRC32(Cookie, reinterpret_cast<uptr>(Ptr),
 117                                  HeaderHolder, ARRAY_SIZE(HeaderHolder));
 118     return static_cast<u16>(Crc);
 119   }
 120
 121   // Checks the validity of a chunk by verifying its checksum. It doesn't
 122   // incur termination in the event of an invalid chunk.
 123   static INLINE bool isValid(const void *Ptr) {
 124     PackedHeader NewPackedHeader =
 125         atomic_load_relaxed(getConstAtomicHeader(Ptr));
 126     UnpackedHeader NewUnpackedHeader =
 127         bit_cast<UnpackedHeader>(NewPackedHeader);
 128     return (NewUnpackedHeader.Checksum ==
 129             computeChecksum(Ptr, &NewUnpackedHeader));
 130   }
 131
 132   // Ensure that ChunkAvailable is 0, so that if a 0 checksum is ever valid
 133   // for a fully nulled out header, its state will be available anyway.
 134   COMPILER_CHECK(ChunkAvailable == 0);
 135
 136   // Loads and unpacks the header, verifying the checksum in the process.
 137   static INLINE
 138   void loadHeader(const void *Ptr, UnpackedHeader *NewUnpackedHeader) {
 139     PackedHeader NewPackedHeader =
 140         atomic_load_relaxed(getConstAtomicHeader(Ptr));
 141     *NewUnpackedHeader = bit_cast<UnpackedHeader>(NewPackedHeader);
 142     if (UNLIKELY(NewUnpackedHeader->Checksum !=
 143         computeChecksum(Ptr, NewUnpackedHeader)))
 144       dieWithMessage("corrupted chunk header at address %p\n", Ptr);
 145   }
 146
 147   // Packs and stores the header, computing the checksum in the process.
 148   static INLINE void storeHeader(void *Ptr, UnpackedHeader *NewUnpackedHeader) {
 149     NewUnpackedHeader->Checksum = computeChecksum(Ptr, NewUnpackedHeader);
 150     PackedHeader NewPackedHeader = bit_cast<PackedHeader>(*NewUnpackedHeader);
 151     atomic_store_relaxed(getAtomicHeader(Ptr), NewPackedHeader);
 152   }
 153
 154   // Packs and stores the header, computing the checksum in the process. We
 155   // compare the current header with the expected provided one to ensure that
 156   // we are not being raced by a corruption occurring in another thread.
 157   static INLINE void compareExchangeHeader(void *Ptr,
 158                                            UnpackedHeader *NewUnpackedHeader,
 159                                            UnpackedHeader *OldUnpackedHeader) {
 160     NewUnpackedHeader->Checksum = computeChecksum(Ptr, NewUnpackedHeader);
 161     PackedHeader NewPackedHeader = bit_cast<PackedHeader>(*NewUnpackedHeader);
 162     PackedHeader OldPackedHeader = bit_cast<PackedHeader>(*OldUnpackedHeader);
 163     if (UNLIKELY(!atomic_compare_exchange_strong(
 164             getAtomicHeader(Ptr), &OldPackedHeader, NewPackedHeader,
 165             memory_order_relaxed)))
 166       dieWithMessage("race on chunk header at address %p\n", Ptr);
 167   }
 168 }  // namespace Chunk
 169
 170 struct QuarantineCallback {
 171   explicit QuarantineCallback(AllocatorCacheT *Cache)
 172     : Cache_(Cache) {}
 173
 174   // Chunk recycling function, returns a quarantined chunk to the backend,
 175   // first making sure it hasn't been tampered with.
 176   void Recycle(void *Ptr) {
 177     UnpackedHeader Header;
 178     Chunk::loadHeader(Ptr, &Header);
 179     if (UNLIKELY(Header.State != ChunkQuarantine))
 180       dieWithMessage("invalid chunk state when recycling address %p\n", Ptr);
 181     UnpackedHeader NewHeader = Header;
 182     NewHeader.State = ChunkAvailable;
 183     Chunk::compareExchangeHeader(Ptr, &NewHeader, &Header);
 184     void *BackendPtr = Chunk::getBackendPtr(Ptr, &Header);
 185     if (Header.ClassId)
 186       getBackend().deallocatePrimary(Cache_, BackendPtr, Header.ClassId);
 187     else
 188       getBackend().deallocateSecondary(BackendPtr);
 189   }
 190
 191   // Internal quarantine allocation and deallocation functions. We first check
 192   // that the batches are indeed serviced by the Primary.
 193   // TODO(kostyak): figure out the best way to protect the batches.
 194   void *Allocate(uptr Size) {
 195     const uptr BatchClassId = SizeClassMap::ClassID(sizeof(QuarantineBatch));
 196     return getBackend().allocatePrimary(Cache_, BatchClassId);
 197   }
 198
 199   void Deallocate(void *Ptr) {
 200     const uptr BatchClassId = SizeClassMap::ClassID(sizeof(QuarantineBatch));
 201     getBackend().deallocatePrimary(Cache_, Ptr, BatchClassId);
 202   }
 203
 204   AllocatorCacheT *Cache_;
 205   COMPILER_CHECK(sizeof(QuarantineBatch) < SizeClassMap::kMaxSize);
 206 };
 207
 208 typedef Quarantine<QuarantineCallback, void> QuarantineT;
 209 typedef QuarantineT::Cache QuarantineCacheT;
 210 COMPILER_CHECK(sizeof(QuarantineCacheT) <=
 211                sizeof(ScudoTSD::QuarantineCachePlaceHolder));
 212
 213 QuarantineCacheT *getQuarantineCache(ScudoTSD *TSD) {
 214   return reinterpret_cast<QuarantineCacheT *>(TSD->QuarantineCachePlaceHolder);
 215 }
 216
 217 struct Allocator {
 218   static const uptr MaxAllowedMallocSize =
 219       FIRST_32_SECOND_64(2UL << 30, 1ULL << 40);
 220
 221   BackendT Backend;
 222   QuarantineT Quarantine;
 223
 224   u32 QuarantineChunksUpToSize;
 225
 226   bool DeallocationTypeMismatch;
 227   bool ZeroContents;
 228   bool DeleteSizeMismatch;
 229
 230   bool CheckRssLimit;
 231   uptr HardRssLimitMb;
 232   uptr SoftRssLimitMb;
 233   atomic_uint8_t RssLimitExceeded;
 234   atomic_uint64_t RssLastCheckedAtNS;
 235
 236   explicit Allocator(LinkerInitialized)
 237     : Quarantine(LINKER_INITIALIZED) {}
 238
 239   NOINLINE void performSanityChecks();
 240
 241   void init() {
 242     SanitizerToolName = "Scudo";
 243     PrimaryAllocatorName = "ScudoPrimary";
 244     SecondaryAllocatorName = "ScudoSecondary";
 245
 246     initFlags();
 247
 248     performSanityChecks();
 249
 250     // Check if hardware CRC32 is supported in the binary and by the platform,
 251     // if so, opt for the CRC32 hardware version of the checksum.
 252     if (&computeHardwareCRC32 && hasHardwareCRC32())
 253       atomic_store_relaxed(&HashAlgorithm, CRC32Hardware);
 254
 255     SetAllocatorMayReturnNull(common_flags()->allocator_may_return_null);
 256     Backend.init(common_flags()->allocator_release_to_os_interval_ms);
 257     HardRssLimitMb = common_flags()->hard_rss_limit_mb;
 258     SoftRssLimitMb = common_flags()->soft_rss_limit_mb;
 259     Quarantine.Init(
 260         static_cast<uptr>(getFlags()->QuarantineSizeKb) << 10,
 261         static_cast<uptr>(getFlags()->ThreadLocalQuarantineSizeKb) << 10);
 262     QuarantineChunksUpToSize = (Quarantine.GetCacheSize() == 0) ? 0 :
 263         getFlags()->QuarantineChunksUpToSize;
 264     DeallocationTypeMismatch = getFlags()->DeallocationTypeMismatch;
 265     DeleteSizeMismatch = getFlags()->DeleteSizeMismatch;
 266     ZeroContents = getFlags()->ZeroContents;
 267
 268     if (UNLIKELY(!GetRandom(reinterpret_cast<void *>(&Cookie), sizeof(Cookie),
 269                             /*blocking=*/false))) {
 270       Cookie = static_cast<u32>((NanoTime() >> 12) ^
 271                                 (reinterpret_cast<uptr>(this) >> 4));
 272     }
 273
 274     CheckRssLimit = HardRssLimitMb || SoftRssLimitMb;
 275     if (CheckRssLimit)
 276       atomic_store_relaxed(&RssLastCheckedAtNS, MonotonicNanoTime());
 277   }
 278
 279   // Helper function that checks for a valid Scudo chunk. nullptr isn't.
 280   bool isValidPointer(const void *Ptr) {
 281     initThreadMaybe();
 282     if (UNLIKELY(!Ptr))
 283       return false;
 284     if (!Chunk::isAligned(Ptr))
 285       return false;
 286     return Chunk::isValid(Ptr);
 287   }
 288
 289   NOINLINE bool isRssLimitExceeded();
 290
 291   // Allocates a chunk.
 292   void *allocate(uptr Size, uptr Alignment, AllocType Type,
 293                  bool ForceZeroContents = false) {
 294     initThreadMaybe();
 295     if (UNLIKELY(Alignment > MaxAlignment)) {
 296       if (AllocatorMayReturnNull())
 297         return nullptr;
 298       reportAllocationAlignmentTooBig(Alignment, MaxAlignment);
 299     }
 300     if (UNLIKELY(Alignment < MinAlignment))
 301       Alignment = MinAlignment;
 302
 303     const uptr NeededSize = RoundUpTo(Size ? Size : 1, MinAlignment) +
 304         Chunk::getHeaderSize();
 305     const uptr AlignedSize = (Alignment > MinAlignment) ?
 306         NeededSize + (Alignment - Chunk::getHeaderSize()) : NeededSize;
 307     if (UNLIKELY(Size >= MaxAllowedMallocSize) ||
 308         UNLIKELY(AlignedSize >= MaxAllowedMallocSize)) {
 309       if (AllocatorMayReturnNull())
 310         return nullptr;
 311       reportAllocationSizeTooBig(Size, AlignedSize, MaxAllowedMallocSize);
 312     }
 313
 314     if (CheckRssLimit && UNLIKELY(isRssLimitExceeded())) {
 315       if (AllocatorMayReturnNull())
 316         return nullptr;
 317       reportRssLimitExceeded();
 318     }
 319
 320     // Primary and Secondary backed allocations have a different treatment. We
 321     // deal with alignment requirements of Primary serviced allocations here,
 322     // but the Secondary will take care of its own alignment needs.
 323     void *BackendPtr;
 324     uptr BackendSize;
 325     u8 ClassId;
 326     if (PrimaryT::CanAllocate(AlignedSize, MinAlignment)) {
 327       BackendSize = AlignedSize;
 328       ClassId = SizeClassMap::ClassID(BackendSize);
 329       bool UnlockRequired;
 330       ScudoTSD *TSD = getTSDAndLock(&UnlockRequired);
 331       BackendPtr = Backend.allocatePrimary(&TSD->Cache, ClassId);
 332       if (UnlockRequired)
 333         TSD->unlock();
 334     } else {
 335       BackendSize = NeededSize;
 336       ClassId = 0;
 337       BackendPtr = Backend.allocateSecondary(BackendSize, Alignment);
 338     }
 339     if (UNLIKELY(!BackendPtr)) {
 340       SetAllocatorOutOfMemory();
 341       if (AllocatorMayReturnNull())
 342         return nullptr;
 343       reportOutOfMemory(Size);
 344     }
 345
 346     // If requested, we will zero out the entire contents of the returned chunk.
 347     if ((ForceZeroContents || ZeroContents) && ClassId)
 348       memset(BackendPtr, 0, PrimaryT::ClassIdToSize(ClassId));
 349
 350     UnpackedHeader Header = {};
 351     uptr UserPtr = reinterpret_cast<uptr>(BackendPtr) + Chunk::getHeaderSize();
 352     if (UNLIKELY(!IsAligned(UserPtr, Alignment))) {
 353       // Since the Secondary takes care of alignment, a non-aligned pointer
 354       // means it is from the Primary. It is also the only case where the offset
 355       // field of the header would be non-zero.
 356       DCHECK(ClassId);
 357       const uptr AlignedUserPtr = RoundUpTo(UserPtr, Alignment);
 358       Header.Offset = (AlignedUserPtr - UserPtr) >> MinAlignmentLog;
 359       UserPtr = AlignedUserPtr;
 360     }
 361     DCHECK_LE(UserPtr + Size, reinterpret_cast<uptr>(BackendPtr) + BackendSize);
 362     Header.State = ChunkAllocated;
 363     Header.AllocType = Type;
 364     if (ClassId) {
 365       Header.ClassId = ClassId;
 366       Header.SizeOrUnusedBytes = Size;
 367     } else {
 368       // The secondary fits the allocations to a page, so the amount of unused
 369       // bytes is the difference between the end of the user allocation and the
 370       // next page boundary.
 371       const uptr PageSize = GetPageSizeCached();
 372       const uptr TrailingBytes = (UserPtr + Size) & (PageSize - 1);
 373       if (TrailingBytes)
 374         Header.SizeOrUnusedBytes = PageSize - TrailingBytes;
 375     }
 376     void *Ptr = reinterpret_cast<void *>(UserPtr);
 377     Chunk::storeHeader(Ptr, &Header);
 378     if (SCUDO_CAN_USE_HOOKS && &__sanitizer_malloc_hook)
 379       __sanitizer_malloc_hook(Ptr, Size);
 380     return Ptr;
 381   }
 382
 383   // Place a chunk in the quarantine or directly deallocate it in the event of
 384   // a zero-sized quarantine, or if the size of the chunk is greater than the
 385   // quarantine chunk size threshold.
 386   void quarantineOrDeallocateChunk(void *Ptr, UnpackedHeader *Header,
 387                                    uptr Size) {
 388     const bool BypassQuarantine = !Size || (Size > QuarantineChunksUpToSize);
 389     if (BypassQuarantine) {
 390       UnpackedHeader NewHeader = *Header;
 391       NewHeader.State = ChunkAvailable;
 392       Chunk::compareExchangeHeader(Ptr, &NewHeader, Header);
 393       void *BackendPtr = Chunk::getBackendPtr(Ptr, Header);
 394       if (Header->ClassId) {
 395         bool UnlockRequired;
 396         ScudoTSD *TSD = getTSDAndLock(&UnlockRequired);
 397         getBackend().deallocatePrimary(&TSD->Cache, BackendPtr,
 398                                        Header->ClassId);
 399         if (UnlockRequired)
 400           TSD->unlock();
 401       } else {
 402         getBackend().deallocateSecondary(BackendPtr);
 403       }
 404     } else {
 405       // If a small memory amount was allocated with a larger alignment, we want
 406       // to take that into account. Otherwise the Quarantine would be filled
 407       // with tiny chunks, taking a lot of VA memory. This is an approximation
 408       // of the usable size, that allows us to not call
 409       // GetActuallyAllocatedSize.
 410       const uptr EstimatedSize = Size + (Header->Offset << MinAlignmentLog);
 411       UnpackedHeader NewHeader = *Header;
 412       NewHeader.State = ChunkQuarantine;
 413       Chunk::compareExchangeHeader(Ptr, &NewHeader, Header);
 414       bool UnlockRequired;
 415       ScudoTSD *TSD = getTSDAndLock(&UnlockRequired);
 416       Quarantine.Put(getQuarantineCache(TSD), QuarantineCallback(&TSD->Cache),
 417                      Ptr, EstimatedSize);
 418       if (UnlockRequired)
 419         TSD->unlock();
 420     }
 421   }
 422
 423   // Deallocates a Chunk, which means either adding it to the quarantine or
 424   // directly returning it to the backend if criteria are met.
 425   void deallocate(void *Ptr, uptr DeleteSize, uptr DeleteAlignment,
 426                   AllocType Type) {
 427     // For a deallocation, we only ensure minimal initialization, meaning thread
 428     // local data will be left uninitialized for now (when using ELF TLS). The
 429     // fallback cache will be used instead. This is a workaround for a situation
 430     // where the only heap operation performed in a thread would be a free past
 431     // the TLS destructors, ending up in initialized thread specific data never
 432     // being destroyed properly. Any other heap operation will do a full init.
 433     initThreadMaybe(/*MinimalInit=*/true);
 434     if (SCUDO_CAN_USE_HOOKS && &__sanitizer_free_hook)
 435       __sanitizer_free_hook(Ptr);
 436     if (UNLIKELY(!Ptr))
 437       return;
 438     if (UNLIKELY(!Chunk::isAligned(Ptr)))
 439       dieWithMessage("misaligned pointer when deallocating address %p\n", Ptr);
 440     UnpackedHeader Header;
 441     Chunk::loadHeader(Ptr, &Header);
 442     if (UNLIKELY(Header.State != ChunkAllocated))
 443       dieWithMessage("invalid chunk state when deallocating address %p\n", Ptr);
 444     if (DeallocationTypeMismatch) {
 445       // The deallocation type has to match the allocation one.
 446       if (Header.AllocType != Type) {
 447         // With the exception of memalign'd Chunks, that can be still be free'd.
 448         if (Header.AllocType != FromMemalign || Type != FromMalloc)
 449           dieWithMessage("allocation type mismatch when deallocating address "
 450                          "%p\n", Ptr);
 451       }
 452     }
 453     const uptr Size = Chunk::getSize(Ptr, &Header);
 454     if (DeleteSizeMismatch) {
 455       if (DeleteSize && DeleteSize != Size)
 456         dieWithMessage("invalid sized delete when deallocating address %p\n",
 457                        Ptr);
 458     }
 459     (void)DeleteAlignment;  // TODO(kostyak): verify that the alignment matches.
 460     quarantineOrDeallocateChunk(Ptr, &Header, Size);
 461   }
 462
 463   // Reallocates a chunk. We can save on a new allocation if the new requested
 464   // size still fits in the chunk.
 465   void *reallocate(void *OldPtr, uptr NewSize) {
 466     initThreadMaybe();
 467     if (UNLIKELY(!Chunk::isAligned(OldPtr)))
 468       dieWithMessage("misaligned address when reallocating address %p\n",
 469                      OldPtr);
 470     UnpackedHeader OldHeader;
 471     Chunk::loadHeader(OldPtr, &OldHeader);
 472     if (UNLIKELY(OldHeader.State != ChunkAllocated))
 473       dieWithMessage("invalid chunk state when reallocating address %p\n",
 474                      OldPtr);
 475     if (DeallocationTypeMismatch) {
 476       if (UNLIKELY(OldHeader.AllocType != FromMalloc))
 477         dieWithMessage("allocation type mismatch when reallocating address "
 478                        "%p\n", OldPtr);
 479     }
 480     const uptr UsableSize = Chunk::getUsableSize(OldPtr, &OldHeader);
 481     // The new size still fits in the current chunk, and the size difference
 482     // is reasonable.
 483     if (NewSize <= UsableSize &&
 484         (UsableSize - NewSize) < (SizeClassMap::kMaxSize / 2)) {
 485       UnpackedHeader NewHeader = OldHeader;
 486       NewHeader.SizeOrUnusedBytes =
 487           OldHeader.ClassId ? NewSize : UsableSize - NewSize;
 488       Chunk::compareExchangeHeader(OldPtr, &NewHeader, &OldHeader);
 489       return OldPtr;
 490     }
 491     // Otherwise, we have to allocate a new chunk and copy the contents of the
 492     // old one.
 493     void *NewPtr = allocate(NewSize, MinAlignment, FromMalloc);
 494     if (NewPtr) {
 495       const uptr OldSize = OldHeader.ClassId ? OldHeader.SizeOrUnusedBytes :
 496           UsableSize - OldHeader.SizeOrUnusedBytes;
 497       memcpy(NewPtr, OldPtr, Min(NewSize, UsableSize));
 498       quarantineOrDeallocateChunk(OldPtr, &OldHeader, OldSize);
 499     }
 500     return NewPtr;
 501   }
 502
 503   // Helper function that returns the actual usable size of a chunk.
 504   uptr getUsableSize(const void *Ptr) {
 505     initThreadMaybe();
 506     if (UNLIKELY(!Ptr))
 507       return 0;
 508     UnpackedHeader Header;
 509     Chunk::loadHeader(Ptr, &Header);
 510     // Getting the usable size of a chunk only makes sense if it's allocated.
 511     if (UNLIKELY(Header.State != ChunkAllocated))
 512       dieWithMessage("invalid chunk state when sizing address %p\n", Ptr);
 513     return Chunk::getUsableSize(Ptr, &Header);
 514   }
 515
 516   void *calloc(uptr NMemB, uptr Size) {
 517     initThreadMaybe();
 518     if (UNLIKELY(CheckForCallocOverflow(NMemB, Size))) {
 519       if (AllocatorMayReturnNull())
 520         return nullptr;
 521       reportCallocOverflow(NMemB, Size);
 522     }
 523     return allocate(NMemB * Size, MinAlignment, FromMalloc, true);
 524   }
 525
 526   void commitBack(ScudoTSD *TSD) {
 527     Quarantine.Drain(getQuarantineCache(TSD), QuarantineCallback(&TSD->Cache));
 528     Backend.destroyCache(&TSD->Cache);
 529   }
 530
 531   uptr getStats(AllocatorStat StatType) {
 532     initThreadMaybe();
 533     uptr stats[AllocatorStatCount];
 534     Backend.getStats(stats);
 535     return stats[StatType];
 536   }
 537
 538   bool canReturnNull() {
 539     initThreadMaybe();
 540     return AllocatorMayReturnNull();
 541   }
 542
 543   void setRssLimit(uptr LimitMb, bool HardLimit) {
 544     if (HardLimit)
 545       HardRssLimitMb = LimitMb;
 546     else
 547       SoftRssLimitMb = LimitMb;
 548     CheckRssLimit = HardRssLimitMb || SoftRssLimitMb;
 549   }
 550
 551   void printStats() {
 552     initThreadMaybe();
 553     Backend.printStats();
 554   }
 555 };
 556
 557 NOINLINE void Allocator::performSanityChecks() {
 558   // Verify that the header offset field can hold the maximum offset. In the
 559   // case of the Secondary allocator, it takes care of alignment and the
 560   // offset will always be 0. In the case of the Primary, the worst case
 561   // scenario happens in the last size class, when the backend allocation
 562   // would already be aligned on the requested alignment, which would happen
 563   // to be the maximum alignment that would fit in that size class. As a
 564   // result, the maximum offset will be at most the maximum alignment for the
 565   // last size class minus the header size, in multiples of MinAlignment.
 566   UnpackedHeader Header = {};
 567   const uptr MaxPrimaryAlignment =
 568       1 << MostSignificantSetBitIndex(SizeClassMap::kMaxSize - MinAlignment);
 569   const uptr MaxOffset =
 570       (MaxPrimaryAlignment - Chunk::getHeaderSize()) >> MinAlignmentLog;
 571   Header.Offset = MaxOffset;
 572   if (Header.Offset != MaxOffset)
 573     dieWithMessage("maximum possible offset doesn't fit in header\n");
 574   // Verify that we can fit the maximum size or amount of unused bytes in the
 575   // header. Given that the Secondary fits the allocation to a page, the worst
 576   // case scenario happens in the Primary. It will depend on the second to
 577   // last and last class sizes, as well as the dynamic base for the Primary.
 578   // The following is an over-approximation that works for our needs.
 579   const uptr MaxSizeOrUnusedBytes = SizeClassMap::kMaxSize - 1;
 580   Header.SizeOrUnusedBytes = MaxSizeOrUnusedBytes;
 581   if (Header.SizeOrUnusedBytes != MaxSizeOrUnusedBytes)
 582     dieWithMessage("maximum possible unused bytes doesn't fit in header\n");
 583
 584   const uptr LargestClassId = SizeClassMap::kLargestClassID;
 585   Header.ClassId = LargestClassId;
 586   if (Header.ClassId != LargestClassId)
 587     dieWithMessage("largest class ID doesn't fit in header\n");
 588 }
 589
 590 // Opportunistic RSS limit check. This will update the RSS limit status, if
 591 // it can, every 100ms, otherwise it will just return the current one.
 592 NOINLINE bool Allocator::isRssLimitExceeded() {
 593   u64 LastCheck = atomic_load_relaxed(&RssLastCheckedAtNS);
 594   const u64 CurrentCheck = MonotonicNanoTime();
 595   if (LIKELY(CurrentCheck < LastCheck + (100ULL * 1000000ULL)))
 596     return atomic_load_relaxed(&RssLimitExceeded);
 597   if (!atomic_compare_exchange_weak(&RssLastCheckedAtNS, &LastCheck,
 598                                     CurrentCheck, memory_order_relaxed))
 599     return atomic_load_relaxed(&RssLimitExceeded);
 600   // TODO(kostyak): We currently use sanitizer_common's GetRSS which reads the
 601   //                RSS from /proc/self/statm by default. We might want to
 602   //                call getrusage directly, even if it's less accurate.
 603   const uptr CurrentRssMb = GetRSS() >> 20;
 604   if (HardRssLimitMb && UNLIKELY(HardRssLimitMb < CurrentRssMb))
 605     dieWithMessage("hard RSS limit exhausted (%zdMb vs %zdMb)\n",
 606                    HardRssLimitMb, CurrentRssMb);
 607   if (SoftRssLimitMb) {
 608     if (atomic_load_relaxed(&RssLimitExceeded)) {
 609       if (CurrentRssMb <= SoftRssLimitMb)
 610         atomic_store_relaxed(&RssLimitExceeded, false);
 611     } else {
 612       if (CurrentRssMb > SoftRssLimitMb) {
 613         atomic_store_relaxed(&RssLimitExceeded, true);
 614         Printf("Scudo INFO: soft RSS limit exhausted (%zdMb vs %zdMb)\n",
 615                SoftRssLimitMb, CurrentRssMb);
 616       }
 617     }
 618   }
 619   return atomic_load_relaxed(&RssLimitExceeded);
 620 }
 621
 622 static Allocator Instance(LINKER_INITIALIZED);
 623
 624 static BackendT &getBackend() {
 625   return Instance.Backend;
 626 }
 627
 628 void initScudo() {
 629   Instance.init();
 630 }
 631
 632 void ScudoTSD::init() {
 633   getBackend().initCache(&Cache);
 634   memset(QuarantineCachePlaceHolder, 0, sizeof(QuarantineCachePlaceHolder));
 635 }
 636
 637 void ScudoTSD::commitBack() {
 638   Instance.commitBack(this);
 639 }
 640
 641 void *scudoAllocate(uptr Size, uptr Alignment, AllocType Type) {
 642   if (Alignment && UNLIKELY(!IsPowerOfTwo(Alignment))) {
 643     errno = EINVAL;
 644     if (Instance.canReturnNull())
 645       return nullptr;
 646     reportAllocationAlignmentNotPowerOfTwo(Alignment);
 647   }
 648   return SetErrnoOnNull(Instance.allocate(Size, Alignment, Type));
 649 }
 650
 651 void scudoDeallocate(void *Ptr, uptr Size, uptr Alignment, AllocType Type) {
 652   Instance.deallocate(Ptr, Size, Alignment, Type);
 653 }
 654
 655 void *scudoRealloc(void *Ptr, uptr Size) {
 656   if (!Ptr)
 657     return SetErrnoOnNull(Instance.allocate(Size, MinAlignment, FromMalloc));
 658   if (Size == 0) {
 659     Instance.deallocate(Ptr, 0, 0, FromMalloc);
 660     return nullptr;
 661   }
 662   return SetErrnoOnNull(Instance.reallocate(Ptr, Size));
 663 }
 664
 665 void *scudoCalloc(uptr NMemB, uptr Size) {
 666   return SetErrnoOnNull(Instance.calloc(NMemB, Size));
 667 }
 668
 669 void *scudoValloc(uptr Size) {
 670   return SetErrnoOnNull(
 671       Instance.allocate(Size, GetPageSizeCached(), FromMemalign));
 672 }
 673
 674 void *scudoPvalloc(uptr Size) {
 675   const uptr PageSize = GetPageSizeCached();
 676   if (UNLIKELY(CheckForPvallocOverflow(Size, PageSize))) {
 677     errno = ENOMEM;
 678     if (Instance.canReturnNull())
 679       return nullptr;
 680     reportPvallocOverflow(Size);
 681   }
 682   // pvalloc(0) should allocate one page.
 683   Size = Size ? RoundUpTo(Size, PageSize) : PageSize;
 684   return SetErrnoOnNull(Instance.allocate(Size, PageSize, FromMemalign));
 685 }
 686
 687 int scudoPosixMemalign(void **MemPtr, uptr Alignment, uptr Size) {
 688   if (UNLIKELY(!CheckPosixMemalignAlignment(Alignment))) {
 689     if (!Instance.canReturnNull())
 690       reportInvalidPosixMemalignAlignment(Alignment);
 691     return EINVAL;
 692   }
 693   void *Ptr = Instance.allocate(Size, Alignment, FromMemalign);
 694   if (UNLIKELY(!Ptr))
 695     return ENOMEM;
 696   *MemPtr = Ptr;
 697   return 0;
 698 }
 699
 700 void *scudoAlignedAlloc(uptr Alignment, uptr Size) {
 701   if (UNLIKELY(!CheckAlignedAllocAlignmentAndSize(Alignment, Size))) {
 702     errno = EINVAL;
 703     if (Instance.canReturnNull())
 704       return nullptr;
 705     reportInvalidAlignedAllocAlignment(Size, Alignment);
 706   }
 707   return SetErrnoOnNull(Instance.allocate(Size, Alignment, FromMalloc));
 708 }
 709
 710 uptr scudoMallocUsableSize(void *Ptr) {
 711   return Instance.getUsableSize(Ptr);
 712 }
 713
 714 }  // namespace __scudo
 715
 716 using namespace __scudo;
 717
 718 // MallocExtension helper functions
 719
 720 uptr __sanitizer_get_current_allocated_bytes() {
 721   return Instance.getStats(AllocatorStatAllocated);
 722 }
 723
 724 uptr __sanitizer_get_heap_size() {
 725   return Instance.getStats(AllocatorStatMapped);
 726 }
 727
 728 uptr __sanitizer_get_free_bytes() {
 729   return 1;
 730 }
 731
 732 uptr __sanitizer_get_unmapped_bytes() {
 733   return 1;
 734 }
 735
 736 uptr __sanitizer_get_estimated_allocated_size(uptr Size) {
 737   return Size;
 738 }
 739
 740 int __sanitizer_get_ownership(const void *Ptr) {
 741   return Instance.isValidPointer(Ptr);
 742 }
 743
 744 uptr __sanitizer_get_allocated_size(const void *Ptr) {
 745   return Instance.getUsableSize(Ptr);
 746 }
 747
 748 #if !SANITIZER_SUPPORTS_WEAK_HOOKS
 749 SANITIZER_INTERFACE_WEAK_DEF(void, __sanitizer_malloc_hook,
 750                              void *Ptr, uptr Size) {
 751   (void)Ptr;
 752   (void)Size;
 753 }
 754
 755 SANITIZER_INTERFACE_WEAK_DEF(void, __sanitizer_free_hook, void *Ptr) {
 756   (void)Ptr;
 757 }
 758 #endif
 759
 760 // Interface functions
 761
 762 void __scudo_set_rss_limit(uptr LimitMb, s32 HardLimit) {
 763   if (!SCUDO_CAN_USE_PUBLIC_INTERFACE)
 764     return;
 765   Instance.setRssLimit(LimitMb, !!HardLimit);
 766 }
 767
 768 void __scudo_print_stats() {
 769   Instance.printStats();
 770 }