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