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