]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/blob - contrib/compiler-rt/lib/sanitizer_common/sanitizer_allocator_primary32.h
Merge llvm, clang, lld, lldb, compiler-rt and libc++ r304149, and update
[FreeBSD/FreeBSD.git] / contrib / compiler-rt / lib / sanitizer_common / sanitizer_allocator_primary32.h
1 //===-- sanitizer_allocator_primary32.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 SizeClassAllocator32LocalCache;
18
19 // SizeClassAllocator32 -- allocator for 32-bit address space.
20 // This allocator can theoretically be used on 64-bit arch, but there it is less
21 // efficient than SizeClassAllocator64.
22 //
23 // [kSpaceBeg, kSpaceBeg + kSpaceSize) is the range of addresses which can
24 // be returned by MmapOrDie().
25 //
26 // Region:
27 //   a result of a single call to MmapAlignedOrDie(kRegionSize, kRegionSize).
28 // Since the regions are aligned by kRegionSize, there are exactly
29 // kNumPossibleRegions possible regions in the address space and so we keep
30 // a ByteMap possible_regions to store the size classes of each Region.
31 // 0 size class means the region is not used by the allocator.
32 //
33 // One Region is used to allocate chunks of a single size class.
34 // A Region looks like this:
35 // UserChunk1 .. UserChunkN <gap> MetaChunkN .. MetaChunk1
36 //
37 // In order to avoid false sharing the objects of this class should be
38 // chache-line aligned.
39
40 struct SizeClassAllocator32FlagMasks {  //  Bit masks.
41   enum {
42     kRandomShuffleChunks = 1,
43   };
44 };
45
46 template <class Params>
47 class SizeClassAllocator32 {
48  public:
49   static const uptr kSpaceBeg = Params::kSpaceBeg;
50   static const u64 kSpaceSize = Params::kSpaceSize;
51   static const uptr kMetadataSize = Params::kMetadataSize;
52   typedef typename Params::SizeClassMap SizeClassMap;
53   static const uptr kRegionSizeLog = Params::kRegionSizeLog;
54   typedef typename Params::ByteMap ByteMap;
55   typedef typename Params::MapUnmapCallback MapUnmapCallback;
56
57   static const bool kRandomShuffleChunks =
58       Params::kFlags & SizeClassAllocator32FlagMasks::kRandomShuffleChunks;
59
60   struct TransferBatch {
61     static const uptr kMaxNumCached = SizeClassMap::kMaxNumCachedHint - 2;
62     void SetFromArray(uptr region_beg_unused, void *batch[], uptr count) {
63       count_ = count;
64       CHECK_LE(count_, kMaxNumCached);
65       for (uptr i = 0; i < count; i++)
66         batch_[i] = batch[i];
67     }
68     uptr Count() const { return count_; }
69     void Clear() { count_ = 0; }
70     void Add(void *ptr) {
71       batch_[count_++] = ptr;
72       CHECK_LE(count_, kMaxNumCached);
73     }
74     void CopyToArray(void *to_batch[]) {
75       for (uptr i = 0, n = Count(); i < n; i++)
76         to_batch[i] = batch_[i];
77     }
78
79     // How much memory do we need for a batch containing n elements.
80     static uptr AllocationSizeRequiredForNElements(uptr n) {
81       return sizeof(uptr) * 2 + sizeof(void *) * n;
82     }
83     static uptr MaxCached(uptr class_id) {
84       return Min(kMaxNumCached, SizeClassMap::MaxCachedHint(class_id));
85     }
86
87     TransferBatch *next;
88
89    private:
90     uptr count_;
91     void *batch_[kMaxNumCached];
92   };
93
94   static const uptr kBatchSize = sizeof(TransferBatch);
95   COMPILER_CHECK((kBatchSize & (kBatchSize - 1)) == 0);
96   COMPILER_CHECK(sizeof(TransferBatch) ==
97                  SizeClassMap::kMaxNumCachedHint * sizeof(uptr));
98
99   static uptr ClassIdToSize(uptr class_id) {
100     return SizeClassMap::Size(class_id);
101   }
102
103   typedef SizeClassAllocator32<Params> ThisT;
104   typedef SizeClassAllocator32LocalCache<ThisT> AllocatorCache;
105
106   void Init(s32 release_to_os_interval_ms) {
107     possible_regions.TestOnlyInit();
108     internal_memset(size_class_info_array, 0, sizeof(size_class_info_array));
109   }
110
111   s32 ReleaseToOSIntervalMs() const {
112     return kReleaseToOSIntervalNever;
113   }
114
115   void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) {
116     // This is empty here. Currently only implemented in 64-bit allocator.
117   }
118
119   void *MapWithCallback(uptr size) {
120     size = RoundUpTo(size, GetPageSizeCached());
121     void *res = MmapOrDie(size, "SizeClassAllocator32");
122     MapUnmapCallback().OnMap((uptr)res, size);
123     return res;
124   }
125
126   void UnmapWithCallback(uptr beg, uptr size) {
127     MapUnmapCallback().OnUnmap(beg, size);
128     UnmapOrDie(reinterpret_cast<void *>(beg), size);
129   }
130
131   static bool CanAllocate(uptr size, uptr alignment) {
132     return size <= SizeClassMap::kMaxSize &&
133       alignment <= SizeClassMap::kMaxSize;
134   }
135
136   void *GetMetaData(const void *p) {
137     CHECK(PointerIsMine(p));
138     uptr mem = reinterpret_cast<uptr>(p);
139     uptr beg = ComputeRegionBeg(mem);
140     uptr size = ClassIdToSize(GetSizeClass(p));
141     u32 offset = mem - beg;
142     uptr n = offset / (u32)size;  // 32-bit division
143     uptr meta = (beg + kRegionSize) - (n + 1) * kMetadataSize;
144     return reinterpret_cast<void*>(meta);
145   }
146
147   NOINLINE TransferBatch *AllocateBatch(AllocatorStats *stat, AllocatorCache *c,
148                                         uptr class_id) {
149     CHECK_LT(class_id, kNumClasses);
150     SizeClassInfo *sci = GetSizeClassInfo(class_id);
151     SpinMutexLock l(&sci->mutex);
152     if (sci->free_list.empty())
153       PopulateFreeList(stat, c, sci, class_id);
154     CHECK(!sci->free_list.empty());
155     TransferBatch *b = sci->free_list.front();
156     sci->free_list.pop_front();
157     return b;
158   }
159
160   NOINLINE void DeallocateBatch(AllocatorStats *stat, uptr class_id,
161                                 TransferBatch *b) {
162     CHECK_LT(class_id, kNumClasses);
163     SizeClassInfo *sci = GetSizeClassInfo(class_id);
164     SpinMutexLock l(&sci->mutex);
165     CHECK_GT(b->Count(), 0);
166     sci->free_list.push_front(b);
167   }
168
169   uptr GetRegionBeginBySizeClass(uptr class_id) { return 0; }
170
171   bool PointerIsMine(const void *p) {
172     uptr mem = reinterpret_cast<uptr>(p);
173     if (mem < kSpaceBeg || mem >= kSpaceBeg + kSpaceSize)
174       return false;
175     return GetSizeClass(p) != 0;
176   }
177
178   uptr GetSizeClass(const void *p) {
179     return possible_regions[ComputeRegionId(reinterpret_cast<uptr>(p))];
180   }
181
182   void *GetBlockBegin(const void *p) {
183     CHECK(PointerIsMine(p));
184     uptr mem = reinterpret_cast<uptr>(p);
185     uptr beg = ComputeRegionBeg(mem);
186     uptr size = ClassIdToSize(GetSizeClass(p));
187     u32 offset = mem - beg;
188     u32 n = offset / (u32)size;  // 32-bit division
189     uptr res = beg + (n * (u32)size);
190     return reinterpret_cast<void*>(res);
191   }
192
193   uptr GetActuallyAllocatedSize(void *p) {
194     CHECK(PointerIsMine(p));
195     return ClassIdToSize(GetSizeClass(p));
196   }
197
198   uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); }
199
200   uptr TotalMemoryUsed() {
201     // No need to lock here.
202     uptr res = 0;
203     for (uptr i = 0; i < kNumPossibleRegions; i++)
204       if (possible_regions[i])
205         res += kRegionSize;
206     return res;
207   }
208
209   void TestOnlyUnmap() {
210     for (uptr i = 0; i < kNumPossibleRegions; i++)
211       if (possible_regions[i])
212         UnmapWithCallback((i * kRegionSize), kRegionSize);
213   }
214
215   // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
216   // introspection API.
217   void ForceLock() {
218     for (uptr i = 0; i < kNumClasses; i++) {
219       GetSizeClassInfo(i)->mutex.Lock();
220     }
221   }
222
223   void ForceUnlock() {
224     for (int i = kNumClasses - 1; i >= 0; i--) {
225       GetSizeClassInfo(i)->mutex.Unlock();
226     }
227   }
228
229   // Iterate over all existing chunks.
230   // The allocator must be locked when calling this function.
231   void ForEachChunk(ForEachChunkCallback callback, void *arg) {
232     for (uptr region = 0; region < kNumPossibleRegions; region++)
233       if (possible_regions[region]) {
234         uptr chunk_size = ClassIdToSize(possible_regions[region]);
235         uptr max_chunks_in_region = kRegionSize / (chunk_size + kMetadataSize);
236         uptr region_beg = region * kRegionSize;
237         for (uptr chunk = region_beg;
238              chunk < region_beg + max_chunks_in_region * chunk_size;
239              chunk += chunk_size) {
240           // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));
241           callback(chunk, arg);
242         }
243       }
244   }
245
246   void PrintStats() {
247   }
248
249   static uptr AdditionalSize() {
250     return 0;
251   }
252
253   typedef SizeClassMap SizeClassMapT;
254   static const uptr kNumClasses = SizeClassMap::kNumClasses;
255
256  private:
257   static const uptr kRegionSize = 1 << kRegionSizeLog;
258   static const uptr kNumPossibleRegions = kSpaceSize / kRegionSize;
259
260   struct SizeClassInfo {
261     SpinMutex mutex;
262     IntrusiveList<TransferBatch> free_list;
263     char padding[kCacheLineSize - sizeof(uptr) -
264                  sizeof(IntrusiveList<TransferBatch>)];
265   };
266   COMPILER_CHECK(sizeof(SizeClassInfo) == kCacheLineSize);
267
268   uptr ComputeRegionId(uptr mem) {
269     uptr res = mem >> kRegionSizeLog;
270     CHECK_LT(res, kNumPossibleRegions);
271     return res;
272   }
273
274   uptr ComputeRegionBeg(uptr mem) {
275     return mem & ~(kRegionSize - 1);
276   }
277
278   uptr AllocateRegion(AllocatorStats *stat, uptr class_id) {
279     CHECK_LT(class_id, kNumClasses);
280     uptr res = reinterpret_cast<uptr>(MmapAlignedOrDie(kRegionSize, kRegionSize,
281                                       "SizeClassAllocator32"));
282     MapUnmapCallback().OnMap(res, kRegionSize);
283     stat->Add(AllocatorStatMapped, kRegionSize);
284     CHECK_EQ(0U, (res & (kRegionSize - 1)));
285     possible_regions.set(ComputeRegionId(res), static_cast<u8>(class_id));
286     return res;
287   }
288
289   SizeClassInfo *GetSizeClassInfo(uptr class_id) {
290     CHECK_LT(class_id, kNumClasses);
291     return &size_class_info_array[class_id];
292   }
293
294   void PopulateFreeList(AllocatorStats *stat, AllocatorCache *c,
295                         SizeClassInfo *sci, uptr class_id) {
296     uptr size = ClassIdToSize(class_id);
297     uptr reg = AllocateRegion(stat, class_id);
298     uptr n_chunks = kRegionSize / (size + kMetadataSize);
299     uptr max_count = TransferBatch::MaxCached(class_id);
300     TransferBatch *b = nullptr;
301     for (uptr i = reg; i < reg + n_chunks * size; i += size) {
302       if (!b) {
303         b = c->CreateBatch(class_id, this, (TransferBatch*)i);
304         b->Clear();
305       }
306       b->Add((void*)i);
307       if (b->Count() == max_count) {
308         CHECK_GT(b->Count(), 0);
309         sci->free_list.push_back(b);
310         b = nullptr;
311       }
312     }
313     if (b) {
314       CHECK_GT(b->Count(), 0);
315       sci->free_list.push_back(b);
316     }
317   }
318
319   ByteMap possible_regions;
320   SizeClassInfo size_class_info_array[kNumClasses];
321 };