libsanitizer/sanitizer_common/sanitizer_allocator64.h

   1 //===-- sanitizer_allocator64.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 // Specialized allocator which works only in 64-bit address space.
   8 // To be used by ThreadSanitizer, MemorySanitizer and possibly other tools.
   9 // The main feature of this allocator is that the header is located far away
  10 // from the user memory region, so that the tool does not use extra shadow
  11 // for the header.
  12 //
  13 // Status: not yet ready.
  14 //===----------------------------------------------------------------------===//
  15 #ifndef SANITIZER_ALLOCATOR_H
  16 #define SANITIZER_ALLOCATOR_H
  17
  18 #include "sanitizer_internal_defs.h"
  19 #if SANITIZER_WORDSIZE != 64
  20 # error "sanitizer_allocator64.h can only be used on 64-bit platforms"
  21 #endif
  22
  23 #include "sanitizer_common.h"
  24 #include "sanitizer_libc.h"
  25 #include "sanitizer_list.h"
  26 #include "sanitizer_mutex.h"
  27
  28 namespace __sanitizer {
  29
  30 // Maps size class id to size and back.
  31 class DefaultSizeClassMap {
  32  private:
  33   // Here we use a spline composed of 5 polynomials of oder 1.
  34   // The first size class is l0, then the classes go with step s0
  35   // untill they reach l1, after which they go with step s1 and so on.
  36   // Steps should be powers of two for cheap division.
  37   // The size of the last size class should be a power of two.
  38   // There should be at most 256 size classes.
  39   static const uptr l0 = 1 << 4;
  40   static const uptr l1 = 1 << 9;
  41   static const uptr l2 = 1 << 12;
  42   static const uptr l3 = 1 << 15;
  43   static const uptr l4 = 1 << 18;
  44   static const uptr l5 = 1 << 21;
  45
  46   static const uptr s0 = 1 << 4;
  47   static const uptr s1 = 1 << 6;
  48   static const uptr s2 = 1 << 9;
  49   static const uptr s3 = 1 << 12;
  50   static const uptr s4 = 1 << 15;
  51
  52   static const uptr u0 = 0  + (l1 - l0) / s0;
  53   static const uptr u1 = u0 + (l2 - l1) / s1;
  54   static const uptr u2 = u1 + (l3 - l2) / s2;
  55   static const uptr u3 = u2 + (l4 - l3) / s3;
  56   static const uptr u4 = u3 + (l5 - l4) / s4;
  57
  58   // Max cached in local cache blocks.
  59   static const uptr c0 = 256;
  60   static const uptr c1 = 64;
  61   static const uptr c2 = 16;
  62   static const uptr c3 = 4;
  63   static const uptr c4 = 1;
  64
  65  public:
  66   static const uptr kNumClasses = u4 + 1;
  67   static const uptr kMaxSize = l5;
  68   static const uptr kMinSize = l0;
  69
  70   COMPILER_CHECK(kNumClasses <= 256);
  71   COMPILER_CHECK((kMaxSize & (kMaxSize - 1)) == 0);
  72
  73   static uptr Size(uptr class_id) {
  74     if (class_id <= u0) return l0 + s0 * (class_id - 0);
  75     if (class_id <= u1) return l1 + s1 * (class_id - u0);
  76     if (class_id <= u2) return l2 + s2 * (class_id - u1);
  77     if (class_id <= u3) return l3 + s3 * (class_id - u2);
  78     if (class_id <= u4) return l4 + s4 * (class_id - u3);
  79     return 0;
  80   }
  81   static uptr ClassID(uptr size) {
  82     if (size <= l1) return 0  + (size - l0 + s0 - 1) / s0;
  83     if (size <= l2) return u0 + (size - l1 + s1 - 1) / s1;
  84     if (size <= l3) return u1 + (size - l2 + s2 - 1) / s2;
  85     if (size <= l4) return u2 + (size - l3 + s3 - 1) / s3;
  86     if (size <= l5) return u3 + (size - l4 + s4 - 1) / s4;
  87     return 0;
  88   }
  89
  90   static uptr MaxCached(uptr class_id) {
  91     if (class_id <= u0) return c0;
  92     if (class_id <= u1) return c1;
  93     if (class_id <= u2) return c2;
  94     if (class_id <= u3) return c3;
  95     if (class_id <= u4) return c4;
  96     return 0;
  97   }
  98 };
  99
 100 struct AllocatorListNode {
 101   AllocatorListNode *next;
 102 };
 103
 104 typedef IntrusiveList<AllocatorListNode> AllocatorFreeList;
 105
 106
 107 // Space: a portion of address space of kSpaceSize bytes starting at
 108 // a fixed address (kSpaceBeg). Both constants are powers of two and
 109 // kSpaceBeg is kSpaceSize-aligned.
 110 //
 111 // Region: a part of Space dedicated to a single size class.
 112 // There are kNumClasses Regions of equal size.
 113 //
 114 // UserChunk: a piece of memory returned to user.
 115 // MetaChunk: kMetadataSize bytes of metadata associated with a UserChunk.
 116 //
 117 // A Region looks like this:
 118 // UserChunk1 ... UserChunkN <gap> MetaChunkN ... MetaChunk1
 119 template <const uptr kSpaceBeg, const uptr kSpaceSize,
 120           const uptr kMetadataSize, class SizeClassMap>
 121 class SizeClassAllocator64 {
 122  public:
 123   void Init() {
 124     CHECK_EQ(AllocBeg(), reinterpret_cast<uptr>(MmapFixedNoReserve(
 125              AllocBeg(), AllocSize())));
 126   }
 127
 128   bool CanAllocate(uptr size, uptr alignment) {
 129     return size <= SizeClassMap::kMaxSize &&
 130       alignment <= SizeClassMap::kMaxSize;
 131   }
 132
 133   void *Allocate(uptr size, uptr alignment) {
 134     CHECK(CanAllocate(size, alignment));
 135     return AllocateBySizeClass(SizeClassMap::ClassID(size));
 136   }
 137
 138   void Deallocate(void *p) {
 139     CHECK(PointerIsMine(p));
 140     DeallocateBySizeClass(p, GetSizeClass(p));
 141   }
 142
 143   // Allocate several chunks of the given class_id.
 144   void BulkAllocate(uptr class_id, AllocatorFreeList *free_list) {
 145     CHECK_LT(class_id, kNumClasses);
 146     RegionInfo *region = GetRegionInfo(class_id);
 147     SpinMutexLock l(&region->mutex);
 148     if (region->free_list.empty()) {
 149       PopulateFreeList(class_id, region);
 150     }
 151     CHECK(!region->free_list.empty());
 152     uptr count = SizeClassMap::MaxCached(class_id);
 153     if (region->free_list.size() <= count) {
 154       free_list->append_front(&region->free_list);
 155     } else {
 156       for (uptr i = 0; i < count; i++) {
 157         AllocatorListNode *node = region->free_list.front();
 158         region->free_list.pop_front();
 159         free_list->push_front(node);
 160       }
 161     }
 162     CHECK(!free_list->empty());
 163   }
 164
 165   // Swallow the entire free_list for the given class_id.
 166   void BulkDeallocate(uptr class_id, AllocatorFreeList *free_list) {
 167     CHECK_LT(class_id, kNumClasses);
 168     RegionInfo *region = GetRegionInfo(class_id);
 169     SpinMutexLock l(&region->mutex);
 170     region->free_list.append_front(free_list);
 171   }
 172
 173   static bool PointerIsMine(void *p) {
 174     return reinterpret_cast<uptr>(p) / kSpaceSize == kSpaceBeg / kSpaceSize;
 175   }
 176
 177   static uptr GetSizeClass(void *p) {
 178     return (reinterpret_cast<uptr>(p) / kRegionSize) % kNumClasses;
 179   }
 180
 181   static void *GetBlockBegin(void *p) {
 182     uptr class_id = GetSizeClass(p);
 183     uptr size = SizeClassMap::Size(class_id);
 184     uptr chunk_idx = GetChunkIdx((uptr)p, size);
 185     uptr reg_beg = (uptr)p & ~(kRegionSize - 1);
 186     uptr begin = reg_beg + chunk_idx * size;
 187     return (void*)begin;
 188   }
 189
 190   static uptr GetActuallyAllocatedSize(void *p) {
 191     CHECK(PointerIsMine(p));
 192     return SizeClassMap::Size(GetSizeClass(p));
 193   }
 194
 195   uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); }
 196
 197   void *GetMetaData(void *p) {
 198     uptr class_id = GetSizeClass(p);
 199     uptr size = SizeClassMap::Size(class_id);
 200     uptr chunk_idx = GetChunkIdx(reinterpret_cast<uptr>(p), size);
 201     return reinterpret_cast<void*>(kSpaceBeg + (kRegionSize * (class_id + 1)) -
 202                                    (1 + chunk_idx) * kMetadataSize);
 203   }
 204
 205   uptr TotalMemoryUsed() {
 206     uptr res = 0;
 207     for (uptr i = 0; i < kNumClasses; i++)
 208       res += GetRegionInfo(i)->allocated_user;
 209     return res;
 210   }
 211
 212   // Test-only.
 213   void TestOnlyUnmap() {
 214     UnmapOrDie(reinterpret_cast<void*>(AllocBeg()), AllocSize());
 215   }
 216
 217   static uptr AllocBeg()  { return kSpaceBeg; }
 218   static uptr AllocSize() { return kSpaceSize + AdditionalSize(); }
 219
 220   static const uptr kNumClasses = 256;  // Power of two <= 256
 221   typedef SizeClassMap SizeClassMapT;
 222
 223  private:
 224   COMPILER_CHECK(kSpaceBeg % kSpaceSize == 0);
 225   COMPILER_CHECK(kNumClasses <= SizeClassMap::kNumClasses);
 226   static const uptr kRegionSize = kSpaceSize / kNumClasses;
 227   COMPILER_CHECK((kRegionSize >> 32) > 0);  // kRegionSize must be >= 2^32.
 228   // Populate the free list with at most this number of bytes at once
 229   // or with one element if its size is greater.
 230   static const uptr kPopulateSize = 1 << 18;
 231
 232   struct RegionInfo {
 233     SpinMutex mutex;
 234     AllocatorFreeList free_list;
 235     uptr allocated_user;  // Bytes allocated for user memory.
 236     uptr allocated_meta;  // Bytes allocated for metadata.
 237     char padding[kCacheLineSize - 3 * sizeof(uptr) - sizeof(AllocatorFreeList)];
 238   };
 239   COMPILER_CHECK(sizeof(RegionInfo) == kCacheLineSize);
 240
 241   static uptr AdditionalSize() {
 242     uptr res = sizeof(RegionInfo) * kNumClasses;
 243     CHECK_EQ(res % GetPageSizeCached(), 0);
 244     return res;
 245   }
 246
 247   RegionInfo *GetRegionInfo(uptr class_id) {
 248     CHECK_LT(class_id, kNumClasses);
 249     RegionInfo *regions = reinterpret_cast<RegionInfo*>(kSpaceBeg + kSpaceSize);
 250     return &regions[class_id];
 251   }
 252
 253   static uptr GetChunkIdx(uptr chunk, uptr size) {
 254     u32 offset = chunk % kRegionSize;
 255     // Here we divide by a non-constant. This is costly.
 256     // We require that kRegionSize is at least 2^32 so that offset is 32-bit.
 257     // We save 2x by using 32-bit div, but may need to use a 256-way switch.
 258     return offset / (u32)size;
 259   }
 260
 261   void PopulateFreeList(uptr class_id, RegionInfo *region) {
 262     uptr size = SizeClassMap::Size(class_id);
 263     uptr beg_idx = region->allocated_user;
 264     uptr end_idx = beg_idx + kPopulateSize;
 265     region->free_list.clear();
 266     uptr region_beg = kSpaceBeg + kRegionSize * class_id;
 267     uptr idx = beg_idx;
 268     uptr i = 0;
 269     do {  // do-while loop because we need to put at least one item.
 270       uptr p = region_beg + idx;
 271       region->free_list.push_front(reinterpret_cast<AllocatorListNode*>(p));
 272       idx += size;
 273       i++;
 274     } while (idx < end_idx);
 275     region->allocated_user += idx - beg_idx;
 276     region->allocated_meta += i * kMetadataSize;
 277     if (region->allocated_user + region->allocated_meta > kRegionSize) {
 278       Printf("Out of memory. Dying.\n");
 279       Printf("The process has exhausted %zuMB for size class %zu.\n",
 280           kRegionSize / 1024 / 1024, size);
 281       Die();
 282     }
 283   }
 284
 285   void *AllocateBySizeClass(uptr class_id) {
 286     CHECK_LT(class_id, kNumClasses);
 287     RegionInfo *region = GetRegionInfo(class_id);
 288     SpinMutexLock l(&region->mutex);
 289     if (region->free_list.empty()) {
 290       PopulateFreeList(class_id, region);
 291     }
 292     CHECK(!region->free_list.empty());
 293     AllocatorListNode *node = region->free_list.front();
 294     region->free_list.pop_front();
 295     return reinterpret_cast<void*>(node);
 296   }
 297
 298   void DeallocateBySizeClass(void *p, uptr class_id) {
 299     RegionInfo *region = GetRegionInfo(class_id);
 300     SpinMutexLock l(&region->mutex);
 301     region->free_list.push_front(reinterpret_cast<AllocatorListNode*>(p));
 302   }
 303 };
 304
 305 // Objects of this type should be used as local caches for SizeClassAllocator64.
 306 // Since the typical use of this class is to have one object per thread in TLS,
 307 // is has to be POD.
 308 template<const uptr kNumClasses, class SizeClassAllocator>
 309 struct SizeClassAllocatorLocalCache {
 310   // Don't need to call Init if the object is a global (i.e. zero-initialized).
 311   void Init() {
 312     internal_memset(this, 0, sizeof(*this));
 313   }
 314
 315   void *Allocate(SizeClassAllocator *allocator, uptr class_id) {
 316     CHECK_LT(class_id, kNumClasses);
 317     AllocatorFreeList *free_list = &free_lists_[class_id];
 318     if (free_list->empty())
 319       allocator->BulkAllocate(class_id, free_list);
 320     CHECK(!free_list->empty());
 321     void *res = free_list->front();
 322     free_list->pop_front();
 323     return res;
 324   }
 325
 326   void Deallocate(SizeClassAllocator *allocator, uptr class_id, void *p) {
 327     CHECK_LT(class_id, kNumClasses);
 328     AllocatorFreeList *free_list = &free_lists_[class_id];
 329     free_list->push_front(reinterpret_cast<AllocatorListNode*>(p));
 330     if (free_list->size() >= 2 * SizeClassMap::MaxCached(class_id))
 331       DrainHalf(allocator, class_id);
 332   }
 333
 334   void Drain(SizeClassAllocator *allocator) {
 335     for (uptr i = 0; i < kNumClasses; i++) {
 336       allocator->BulkDeallocate(i, &free_lists_[i]);
 337       CHECK(free_lists_[i].empty());
 338     }
 339   }
 340
 341   // private:
 342   typedef typename SizeClassAllocator::SizeClassMapT SizeClassMap;
 343   AllocatorFreeList free_lists_[kNumClasses];
 344
 345   void DrainHalf(SizeClassAllocator *allocator, uptr class_id) {
 346     AllocatorFreeList *free_list = &free_lists_[class_id];
 347     AllocatorFreeList half;
 348     half.clear();
 349     const uptr count = free_list->size() / 2;
 350     for (uptr i = 0; i < count; i++) {
 351       AllocatorListNode *node = free_list->front();
 352       free_list->pop_front();
 353       half.push_front(node);
 354     }
 355     allocator->BulkDeallocate(class_id, &half);
 356   }
 357 };
 358
 359 // This class can (de)allocate only large chunks of memory using mmap/unmap.
 360 // The main purpose of this allocator is to cover large and rare allocation
 361 // sizes not covered by more efficient allocators (e.g. SizeClassAllocator64).
 362 class LargeMmapAllocator {
 363  public:
 364   void Init() {
 365     internal_memset(this, 0, sizeof(*this));
 366     page_size_ = GetPageSizeCached();
 367   }
 368   void *Allocate(uptr size, uptr alignment) {
 369     CHECK(IsPowerOfTwo(alignment));
 370     uptr map_size = RoundUpMapSize(size);
 371     if (alignment > page_size_)
 372       map_size += alignment;
 373     if (map_size < size) return 0;  // Overflow.
 374     uptr map_beg = reinterpret_cast<uptr>(
 375         MmapOrDie(map_size, "LargeMmapAllocator"));
 376     uptr map_end = map_beg + map_size;
 377     uptr res = map_beg + page_size_;
 378     if (res & (alignment - 1))  // Align.
 379       res += alignment - (res & (alignment - 1));
 380     CHECK_EQ(0, res & (alignment - 1));
 381     CHECK_LE(res + size, map_end);
 382     Header *h = GetHeader(res);
 383     h->size = size;
 384     h->map_beg = map_beg;
 385     h->map_size = map_size;
 386     {
 387       SpinMutexLock l(&mutex_);
 388       h->next = list_;
 389       h->prev = 0;
 390       if (list_)
 391         list_->prev = h;
 392       list_ = h;
 393     }
 394     return reinterpret_cast<void*>(res);
 395   }
 396
 397   void Deallocate(void *p) {
 398     Header *h = GetHeader(p);
 399     {
 400       SpinMutexLock l(&mutex_);
 401       Header *prev = h->prev;
 402       Header *next = h->next;
 403       if (prev)
 404         prev->next = next;
 405       if (next)
 406         next->prev = prev;
 407       if (h == list_)
 408         list_ = next;
 409     }
 410     UnmapOrDie(reinterpret_cast<void*>(h->map_beg), h->map_size);
 411   }
 412
 413   uptr TotalMemoryUsed() {
 414     SpinMutexLock l(&mutex_);
 415     uptr res = 0;
 416     for (Header *l = list_; l; l = l->next) {
 417       res += RoundUpMapSize(l->size);
 418     }
 419     return res;
 420   }
 421
 422   bool PointerIsMine(void *p) {
 423     // Fast check.
 424     if ((reinterpret_cast<uptr>(p) & (page_size_ - 1))) return false;
 425     SpinMutexLock l(&mutex_);
 426     for (Header *l = list_; l; l = l->next) {
 427       if (GetUser(l) == p) return true;
 428     }
 429     return false;
 430   }
 431
 432   uptr GetActuallyAllocatedSize(void *p) {
 433     return RoundUpMapSize(GetHeader(p)->size) - page_size_;
 434   }
 435
 436   // At least page_size_/2 metadata bytes is available.
 437   void *GetMetaData(void *p) {
 438     return GetHeader(p) + 1;
 439   }
 440
 441   void *GetBlockBegin(void *p) {
 442     SpinMutexLock l(&mutex_);
 443     for (Header *l = list_; l; l = l->next) {
 444       void *b = GetUser(l);
 445       if (p >= b && p < (u8*)b + l->size)
 446         return b;
 447     }
 448     return 0;
 449   }
 450
 451  private:
 452   struct Header {
 453     uptr map_beg;
 454     uptr map_size;
 455     uptr size;
 456     Header *next;
 457     Header *prev;
 458   };
 459
 460   Header *GetHeader(uptr p) {
 461     return reinterpret_cast<Header*>(p - page_size_);
 462   }
 463   Header *GetHeader(void *p) { return GetHeader(reinterpret_cast<uptr>(p)); }
 464
 465   void *GetUser(Header *h) {
 466     return reinterpret_cast<void*>(reinterpret_cast<uptr>(h) + page_size_);
 467   }
 468
 469   uptr RoundUpMapSize(uptr size) {
 470     return RoundUpTo(size, page_size_) + page_size_;
 471   }
 472
 473   uptr page_size_;
 474   Header *list_;
 475   SpinMutex mutex_;
 476 };
 477
 478 // This class implements a complete memory allocator by using two
 479 // internal allocators:
 480 // PrimaryAllocator is efficient, but may not allocate some sizes (alignments).
 481 //  When allocating 2^x bytes it should return 2^x aligned chunk.
 482 // PrimaryAllocator is used via a local AllocatorCache.
 483 // SecondaryAllocator can allocate anything, but is not efficient.
 484 template <class PrimaryAllocator, class AllocatorCache,
 485           class SecondaryAllocator>  // NOLINT
 486 class CombinedAllocator {
 487  public:
 488   void Init() {
 489     primary_.Init();
 490     secondary_.Init();
 491   }
 492
 493   void *Allocate(AllocatorCache *cache, uptr size, uptr alignment,
 494                  bool cleared = false) {
 495     // Returning 0 on malloc(0) may break a lot of code.
 496     if (size == 0)
 497       size = 1;
 498     if (size + alignment < size)
 499       return 0;
 500     if (alignment > 8)
 501       size = RoundUpTo(size, alignment);
 502     void *res;
 503     if (primary_.CanAllocate(size, alignment))
 504       res = cache->Allocate(&primary_, primary_.ClassID(size));
 505     else
 506       res = secondary_.Allocate(size, alignment);
 507     if (alignment > 8)
 508       CHECK_EQ(reinterpret_cast<uptr>(res) & (alignment - 1), 0);
 509     if (cleared && res)
 510       internal_memset(res, 0, size);
 511     return res;
 512   }
 513
 514   void Deallocate(AllocatorCache *cache, void *p) {
 515     if (!p) return;
 516     if (primary_.PointerIsMine(p))
 517       cache->Deallocate(&primary_, primary_.GetSizeClass(p), p);
 518     else
 519       secondary_.Deallocate(p);
 520   }
 521
 522   void *Reallocate(AllocatorCache *cache, void *p, uptr new_size,
 523                    uptr alignment) {
 524     if (!p)
 525       return Allocate(cache, new_size, alignment);
 526     if (!new_size) {
 527       Deallocate(cache, p);
 528       return 0;
 529     }
 530     CHECK(PointerIsMine(p));
 531     uptr old_size = GetActuallyAllocatedSize(p);
 532     uptr memcpy_size = Min(new_size, old_size);
 533     void *new_p = Allocate(cache, new_size, alignment);
 534     if (new_p)
 535       internal_memcpy(new_p, p, memcpy_size);
 536     Deallocate(cache, p);
 537     return new_p;
 538   }
 539
 540   bool PointerIsMine(void *p) {
 541     if (primary_.PointerIsMine(p))
 542       return true;
 543     return secondary_.PointerIsMine(p);
 544   }
 545
 546   void *GetMetaData(void *p) {
 547     if (primary_.PointerIsMine(p))
 548       return primary_.GetMetaData(p);
 549     return secondary_.GetMetaData(p);
 550   }
 551
 552   void *GetBlockBegin(void *p) {
 553     if (primary_.PointerIsMine(p))
 554       return primary_.GetBlockBegin(p);
 555     return secondary_.GetBlockBegin(p);
 556   }
 557
 558   uptr GetActuallyAllocatedSize(void *p) {
 559     if (primary_.PointerIsMine(p))
 560       return primary_.GetActuallyAllocatedSize(p);
 561     return secondary_.GetActuallyAllocatedSize(p);
 562   }
 563
 564   uptr TotalMemoryUsed() {
 565     return primary_.TotalMemoryUsed() + secondary_.TotalMemoryUsed();
 566   }
 567
 568   void TestOnlyUnmap() { primary_.TestOnlyUnmap(); }
 569
 570   void SwallowCache(AllocatorCache *cache) {
 571     cache->Drain(&primary_);
 572   }
 573
 574  private:
 575   PrimaryAllocator primary_;
 576   SecondaryAllocator secondary_;
 577 };
 578
 579 }  // namespace __sanitizer
 580
 581 #endif  // SANITIZER_ALLOCATOR_H