[tsan] make the 64-bit allocator build (but not work) in 32-bit mode to simplify...
[lldb.git] / compiler-rt / lib / sanitizer_common / sanitizer_allocator64.h
1 //===-- sanitizer_allocator64.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 // Specialized allocator which works only in 64-bit address space.
10 // It is used by ThreadSanitizer, MemorySanitizer and possibly other tools.
11 // The main feature of this allocator is that the header is located far away
12 // from the user memory region, so that the tool does not use extra shadow
13 // for the header.
14 // Another important feature is that the size class of a pointer is computed
15 // without any memory accesses by simply looking at the address.
16 //
17 //===----------------------------------------------------------------------===//
18 #ifndef SANITIZER_ALLOCATOR64_H
19 #define SANITIZER_ALLOCATOR64_H
20
21 #include "sanitizer_allocator.h"
22
23 namespace __sanitizer {
24
25 // SizeClassAllocator64 -- allocator for 64-bit address space.
26 //
27 // Space: a portion of address space of kSpaceSize bytes starting at
28 // a fixed address (kSpaceBeg). Both constants are powers of two and
29 // kSpaceBeg is kSpaceSize-aligned.
30 //
31 // Region: a part of Space dedicated to a single size class.
32 // There are kNumClasses Regions of equal size.
33 //
34 // UserChunk: a piece of memory returned to user.
35 // MetaChunk: kMetadataSize bytes of metadata associated with a UserChunk.
36 //
37 // A Region looks like this:
38 // UserChunk1 ... UserChunkN <gap> MetaChunkN ... MetaChunk1
39 template <const uptr kSpaceBeg, const uptr kSpaceSize,
40           const uptr kMetadataSize, class SizeClassMap>
41 class SizeClassAllocator64 {
42  public:
43   void Init() {
44     CHECK_EQ(AllocBeg(), reinterpret_cast<uptr>(MmapFixedNoReserve(
45              AllocBeg(), AllocSize())));
46   }
47
48   bool CanAllocate(uptr size, uptr alignment) {
49     return size <= SizeClassMap::kMaxSize &&
50       alignment <= SizeClassMap::kMaxSize;
51   }
52
53   void *Allocate(uptr size, uptr alignment) {
54     CHECK(CanAllocate(size, alignment));
55     return AllocateBySizeClass(SizeClassMap::ClassID(size));
56   }
57
58   void Deallocate(void *p) {
59     CHECK(PointerIsMine(p));
60     DeallocateBySizeClass(p, GetSizeClass(p));
61   }
62
63   // Allocate several chunks of the given class_id.
64   void BulkAllocate(uptr class_id, AllocatorFreeList *free_list) {
65     CHECK_LT(class_id, kNumClasses);
66     RegionInfo *region = GetRegionInfo(class_id);
67     SpinMutexLock l(&region->mutex);
68     if (region->free_list.empty()) {
69       PopulateFreeList(class_id, region);
70     }
71     CHECK(!region->free_list.empty());
72     uptr count = SizeClassMap::MaxCached(class_id);
73     if (region->free_list.size() <= count) {
74       free_list->append_front(&region->free_list);
75     } else {
76       for (uptr i = 0; i < count; i++) {
77         AllocatorListNode *node = region->free_list.front();
78         region->free_list.pop_front();
79         free_list->push_front(node);
80       }
81     }
82     CHECK(!free_list->empty());
83   }
84
85   // Swallow the entire free_list for the given class_id.
86   void BulkDeallocate(uptr class_id, AllocatorFreeList *free_list) {
87     CHECK_LT(class_id, kNumClasses);
88     RegionInfo *region = GetRegionInfo(class_id);
89     SpinMutexLock l(&region->mutex);
90     region->free_list.append_front(free_list);
91   }
92
93   static bool PointerIsMine(void *p) {
94     return reinterpret_cast<uptr>(p) / kSpaceSize == kSpaceBeg / kSpaceSize;
95   }
96
97   static uptr GetSizeClass(void *p) {
98     return (reinterpret_cast<uptr>(p) / kRegionSize) % kNumClasses;
99   }
100
101   static void *GetBlockBegin(void *p) {
102     uptr class_id = GetSizeClass(p);
103     uptr size = SizeClassMap::Size(class_id);
104     uptr chunk_idx = GetChunkIdx((uptr)p, size);
105     uptr reg_beg = (uptr)p & ~(kRegionSize - 1);
106     uptr begin = reg_beg + chunk_idx * size;
107     return (void*)begin;
108   }
109
110   static uptr GetActuallyAllocatedSize(void *p) {
111     CHECK(PointerIsMine(p));
112     return SizeClassMap::Size(GetSizeClass(p));
113   }
114
115   uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); }
116
117   void *GetMetaData(void *p) {
118     uptr class_id = GetSizeClass(p);
119     uptr size = SizeClassMap::Size(class_id);
120     uptr chunk_idx = GetChunkIdx(reinterpret_cast<uptr>(p), size);
121     return reinterpret_cast<void*>(kSpaceBeg + (kRegionSize * (class_id + 1)) -
122                                    (1 + chunk_idx) * kMetadataSize);
123   }
124
125   uptr TotalMemoryUsed() {
126     uptr res = 0;
127     for (uptr i = 0; i < kNumClasses; i++)
128       res += GetRegionInfo(i)->allocated_user;
129     return res;
130   }
131
132   // Test-only.
133   void TestOnlyUnmap() {
134     UnmapOrDie(reinterpret_cast<void*>(AllocBeg()), AllocSize());
135   }
136
137   static uptr AllocBeg()  { return kSpaceBeg; }
138   static uptr AllocSize() { return kSpaceSize + AdditionalSize(); }
139
140   typedef SizeClassMap SizeClassMapT;
141   static const uptr kNumClasses = SizeClassMap::kNumClasses;  // 2^k <= 256
142
143  private:
144   static const uptr kRegionSize = kSpaceSize / kNumClasses;
145   COMPILER_CHECK(kSpaceBeg % kSpaceSize == 0);
146   COMPILER_CHECK(kNumClasses <= SizeClassMap::kNumClasses);
147   // kRegionSize must be >= 2^32.
148   COMPILER_CHECK((kRegionSize) >= (1ULL << (SANITIZER_WORDSIZE / 2)));
149   // Populate the free list with at most this number of bytes at once
150   // or with one element if its size is greater.
151   static const uptr kPopulateSize = 1 << 18;
152
153   struct RegionInfo {
154     SpinMutex mutex;
155     AllocatorFreeList free_list;
156     uptr allocated_user;  // Bytes allocated for user memory.
157     uptr allocated_meta;  // Bytes allocated for metadata.
158     char padding[kCacheLineSize - 3 * sizeof(uptr) - sizeof(AllocatorFreeList)];
159   };
160   COMPILER_CHECK(sizeof(RegionInfo) == kCacheLineSize);
161
162   static uptr AdditionalSize() {
163     uptr PageSize = GetPageSizeCached();
164     uptr res = Max(sizeof(RegionInfo) * kNumClasses, PageSize);
165     CHECK_EQ(res % PageSize, 0);
166     return res;
167   }
168
169   RegionInfo *GetRegionInfo(uptr class_id) {
170     CHECK_LT(class_id, kNumClasses);
171     RegionInfo *regions = reinterpret_cast<RegionInfo*>(kSpaceBeg + kSpaceSize);
172     return &regions[class_id];
173   }
174
175   static uptr GetChunkIdx(uptr chunk, uptr size) {
176     u32 offset = chunk % kRegionSize;
177     // Here we divide by a non-constant. This is costly.
178     // We require that kRegionSize is at least 2^32 so that offset is 32-bit.
179     // We save 2x by using 32-bit div, but may need to use a 256-way switch.
180     return offset / (u32)size;
181   }
182
183   void PopulateFreeList(uptr class_id, RegionInfo *region) {
184     uptr size = SizeClassMap::Size(class_id);
185     uptr beg_idx = region->allocated_user;
186     uptr end_idx = beg_idx + kPopulateSize;
187     region->free_list.clear();
188     uptr region_beg = kSpaceBeg + kRegionSize * class_id;
189     uptr idx = beg_idx;
190     uptr i = 0;
191     do {  // do-while loop because we need to put at least one item.
192       uptr p = region_beg + idx;
193       region->free_list.push_front(reinterpret_cast<AllocatorListNode*>(p));
194       idx += size;
195       i++;
196     } while (idx < end_idx);
197     region->allocated_user += idx - beg_idx;
198     region->allocated_meta += i * kMetadataSize;
199     if (region->allocated_user + region->allocated_meta > kRegionSize) {
200       Printf("Out of memory. Dying.\n");
201       Printf("The process has exhausted %zuMB for size class %zu.\n",
202           kRegionSize / 1024 / 1024, size);
203       Die();
204     }
205   }
206
207   void *AllocateBySizeClass(uptr class_id) {
208     CHECK_LT(class_id, kNumClasses);
209     RegionInfo *region = GetRegionInfo(class_id);
210     SpinMutexLock l(&region->mutex);
211     if (region->free_list.empty()) {
212       PopulateFreeList(class_id, region);
213     }
214     CHECK(!region->free_list.empty());
215     AllocatorListNode *node = region->free_list.front();
216     region->free_list.pop_front();
217     return reinterpret_cast<void*>(node);
218   }
219
220   void DeallocateBySizeClass(void *p, uptr class_id) {
221     RegionInfo *region = GetRegionInfo(class_id);
222     SpinMutexLock l(&region->mutex);
223     region->free_list.push_front(reinterpret_cast<AllocatorListNode*>(p));
224   }
225 };
226
227 }  // namespace __sanitizer
228
229 #endif  // SANITIZER_ALLOCATOR64_H