1 // AsmJit - Machine code generation for C++
2 //
3 // * Official AsmJit Home Page: https://asmjit.com
4 // * Official Github Repository: https://github.com/asmjit/asmjit
5 //
6 // Copyright (c) 2008-2020 The AsmJit Authors
7 //
8 // This software is provided 'as-is', without any express or implied
9 // warranty. In no event will the authors be held liable for any damages
10 // arising from the use of this software.
11 //
12 // Permission is granted to anyone to use this software for any purpose,
13 // including commercial applications, and to alter it and redistribute it
14 // freely, subject to the following restrictions:
15 //
16 // 1. The origin of this software must not be misrepresented; you must not
17 // claim that you wrote the original software. If you use this software
18 // in a product, an acknowledgment in the product documentation would be
19 // appreciated but is not required.
20 // 2. Altered source versions must be plainly marked as such, and must not be
21 // misrepresented as being the original software.
22 // 3. This notice may not be removed or altered from any source distribution.
23
24 #include "../core/api-build_p.h"
25 #ifndef ASMJIT_NO_JIT
26
27 #include "../core/archtraits.h"
28 #include "../core/jitallocator.h"
29 #include "../core/osutils_p.h"
30 #include "../core/support.h"
31 #include "../core/virtmem.h"
32 #include "../core/zone.h"
33 #include "../core/zonelist.h"
34 #include "../core/zonetree.h"
35
36 ASMJIT_BEGIN_NAMESPACE
37
38 // ============================================================================
39 // [asmjit::JitAllocator - Constants]
40 // ============================================================================
41
42 enum JitAllocatorConstants : uint32_t {
43 //! Number of pools to use when `JitAllocator::kOptionUseMultiplePools` is set.
44 //!
45 //! Each pool increases granularity twice to make memory management more
46 //! efficient. Ideal number of pools appears to be 3 to 4 as it distributes
47 //! small and large functions properly.
48 kJitAllocatorMultiPoolCount = 3,
49
50 //! Minimum granularity (and the default granularity for pool #0).
51 kJitAllocatorBaseGranularity = 64,
52
53 //! Maximum block size (32MB).
54 kJitAllocatorMaxBlockSize = 1024 * 1024 * 32
55 };
56
JitAllocator_defaultFillPattern()57 static inline uint32_t JitAllocator_defaultFillPattern() noexcept {
58 // X86 and X86_64 - 4x 'int3' instruction.
59 if (ASMJIT_ARCH_X86)
60 return 0xCCCCCCCCu;
61
62 // Unknown...
63 return 0u;
64 }
65
66 // ============================================================================
67 // [asmjit::BitVectorRangeIterator]
68 // ============================================================================
69
70 template<typename T, uint32_t B>
71 class BitVectorRangeIterator {
72 public:
73 const T* _ptr;
74 size_t _idx;
75 size_t _end;
76 T _bitWord;
77
78 enum : uint32_t { kBitWordSize = Support::bitSizeOf<T>() };
79 enum : T { kXorMask = B == 0 ? Support::allOnes<T>() : T(0) };
80
BitVectorRangeIterator(const T * data,size_t numBitWords)81 ASMJIT_INLINE BitVectorRangeIterator(const T* data, size_t numBitWords) noexcept {
82 init(data, numBitWords);
83 }
84
BitVectorRangeIterator(const T * data,size_t numBitWords,size_t start,size_t end)85 ASMJIT_INLINE BitVectorRangeIterator(const T* data, size_t numBitWords, size_t start, size_t end) noexcept {
86 init(data, numBitWords, start, end);
87 }
88
init(const T * data,size_t numBitWords)89 ASMJIT_INLINE void init(const T* data, size_t numBitWords) noexcept {
90 init(data, numBitWords, 0, numBitWords * kBitWordSize);
91 }
92
init(const T * data,size_t numBitWords,size_t start,size_t end)93 ASMJIT_INLINE void init(const T* data, size_t numBitWords, size_t start, size_t end) noexcept {
94 ASMJIT_ASSERT(numBitWords >= (end + kBitWordSize - 1) / kBitWordSize);
95 DebugUtils::unused(numBitWords);
96
97 size_t idx = Support::alignDown(start, kBitWordSize);
98 const T* ptr = data + (idx / kBitWordSize);
99
100 T bitWord = 0;
101 if (idx < end)
102 bitWord = (*ptr ^ kXorMask) & (Support::allOnes<T>() << (start % kBitWordSize));
103
104 _ptr = ptr;
105 _idx = idx;
106 _end = end;
107 _bitWord = bitWord;
108 }
109
nextRange(size_t * rangeStart,size_t * rangeEnd,size_t rangeHint=std::numeric_limits<size_t>::max ())110 ASMJIT_INLINE bool nextRange(size_t* rangeStart, size_t* rangeEnd, size_t rangeHint = std::numeric_limits<size_t>::max()) noexcept {
111 // Skip all empty BitWords.
112 while (_bitWord == 0) {
113 _idx += kBitWordSize;
114 if (_idx >= _end)
115 return false;
116 _bitWord = (*++_ptr) ^ kXorMask;
117 }
118
119 size_t i = Support::ctz(_bitWord);
120
121 *rangeStart = _idx + i;
122 _bitWord = ~(_bitWord ^ ~(Support::allOnes<T>() << i));
123
124 if (_bitWord == 0) {
125 *rangeEnd = Support::min(_idx + kBitWordSize, _end);
126 while (*rangeEnd - *rangeStart < rangeHint) {
127 _idx += kBitWordSize;
128 if (_idx >= _end)
129 break;
130
131 _bitWord = (*++_ptr) ^ kXorMask;
132 if (_bitWord != Support::allOnes<T>()) {
133 size_t j = Support::ctz(~_bitWord);
134 *rangeEnd = Support::min(_idx + j, _end);
135 _bitWord = _bitWord ^ ~(Support::allOnes<T>() << j);
136 break;
137 }
138
139 *rangeEnd = Support::min(_idx + kBitWordSize, _end);
140 _bitWord = 0;
141 continue;
142 }
143
144 return true;
145 }
146 else {
147 size_t j = Support::ctz(_bitWord);
148 *rangeEnd = Support::min(_idx + j, _end);
149
150 _bitWord = ~(_bitWord ^ ~(Support::allOnes<T>() << j));
151 return true;
152 }
153 }
154 };
155
156 // ============================================================================
157 // [asmjit::JitAllocator - Pool]
158 // ============================================================================
159
160 class JitAllocatorBlock;
161
162 class JitAllocatorPool {
163 public:
164 ASMJIT_NONCOPYABLE(JitAllocatorPool)
165
JitAllocatorPool(uint32_t granularity)166 inline JitAllocatorPool(uint32_t granularity) noexcept
167 : blocks(),
168 cursor(nullptr),
169 blockCount(0),
170 granularity(uint16_t(granularity)),
171 granularityLog2(uint8_t(Support::ctz(granularity))),
172 emptyBlockCount(0),
173 totalAreaSize(0),
174 totalAreaUsed(0),
175 totalOverheadBytes(0) {}
176
reset()177 inline void reset() noexcept {
178 blocks.reset();
179 cursor = nullptr;
180 blockCount = 0;
181 totalAreaSize = 0;
182 totalAreaUsed = 0;
183 totalOverheadBytes = 0;
184 }
185
byteSizeFromAreaSize(uint32_t areaSize) const186 inline size_t byteSizeFromAreaSize(uint32_t areaSize) const noexcept { return size_t(areaSize) * granularity; }
areaSizeFromByteSize(size_t size) const187 inline uint32_t areaSizeFromByteSize(size_t size) const noexcept { return uint32_t((size + granularity - 1) >> granularityLog2); }
188
bitWordCountFromAreaSize(uint32_t areaSize) const189 inline size_t bitWordCountFromAreaSize(uint32_t areaSize) const noexcept {
190 using namespace Support;
191 return alignUp<size_t>(areaSize, kBitWordSizeInBits) / kBitWordSizeInBits;
192 }
193
194 //! Double linked list of blocks.
195 ZoneList<JitAllocatorBlock> blocks;
196 //! Where to start looking first.
197 JitAllocatorBlock* cursor;
198
199 //! Count of blocks.
200 uint32_t blockCount;
201 //! Allocation granularity.
202 uint16_t granularity;
203 //! Log2(granularity).
204 uint8_t granularityLog2;
205 //! Count of empty blocks (either 0 or 1 as we won't keep more blocks empty).
206 uint8_t emptyBlockCount;
207
208 //! Number of bits reserved across all blocks.
209 size_t totalAreaSize;
210 //! Number of bits used across all blocks.
211 size_t totalAreaUsed;
212 //! Overhead of all blocks (in bytes).
213 size_t totalOverheadBytes;
214 };
215
216 // ============================================================================
217 // [asmjit::JitAllocator - Block]
218 // ============================================================================
219
220 class JitAllocatorBlock : public ZoneTreeNodeT<JitAllocatorBlock>,
221 public ZoneListNode<JitAllocatorBlock> {
222 public:
223 ASMJIT_NONCOPYABLE(JitAllocatorBlock)
224
225 enum Flags : uint32_t {
226 //! Block is empty.
227 kFlagEmpty = 0x00000001u,
228 //! Block is dirty (largestUnusedArea, searchStart, searchEnd).
229 kFlagDirty = 0x00000002u,
230 //! Block is dual-mapped.
231 kFlagDualMapped = 0x00000004u
232 };
233
234 //! Link to the pool that owns this block.
235 JitAllocatorPool* _pool;
236 //! Virtual memory mapping - either single mapping (both pointers equal) or
237 //! dual mapping, where one pointer is Read+Execute and the second Read+Write.
238 VirtMem::DualMapping _mapping;
239 //! Virtual memory size (block size) [bytes].
240 size_t _blockSize;
241
242 //! Block flags.
243 uint32_t _flags;
244 //! Size of the whole block area (bit-vector size).
245 uint32_t _areaSize;
246 //! Used area (number of bits in bit-vector used).
247 uint32_t _areaUsed;
248 //! The largest unused continuous area in the bit-vector (or `areaSize` to initiate rescan).
249 uint32_t _largestUnusedArea;
250 //! Start of a search range (for unused bits).
251 uint32_t _searchStart;
252 //! End of a search range (for unused bits).
253 uint32_t _searchEnd;
254
255 //! Used bit-vector (0 = unused, 1 = used).
256 Support::BitWord* _usedBitVector;
257 //! Stop bit-vector (0 = don't care, 1 = stop).
258 Support::BitWord* _stopBitVector;
259
JitAllocatorBlock(JitAllocatorPool * pool,VirtMem::DualMapping mapping,size_t blockSize,uint32_t blockFlags,Support::BitWord * usedBitVector,Support::BitWord * stopBitVector,uint32_t areaSize)260 inline JitAllocatorBlock(
261 JitAllocatorPool* pool,
262 VirtMem::DualMapping mapping,
263 size_t blockSize,
264 uint32_t blockFlags,
265 Support::BitWord* usedBitVector,
266 Support::BitWord* stopBitVector,
267 uint32_t areaSize) noexcept
268 : ZoneTreeNodeT(),
269 _pool(pool),
270 _mapping(mapping),
271 _blockSize(blockSize),
272 _flags(blockFlags),
273 _areaSize(areaSize),
274 _areaUsed(0),
275 _largestUnusedArea(areaSize),
276 _searchStart(0),
277 _searchEnd(areaSize),
278 _usedBitVector(usedBitVector),
279 _stopBitVector(stopBitVector) {}
280
pool() const281 inline JitAllocatorPool* pool() const noexcept { return _pool; }
282
roPtr() const283 inline uint8_t* roPtr() const noexcept { return static_cast<uint8_t*>(_mapping.ro); }
rwPtr() const284 inline uint8_t* rwPtr() const noexcept { return static_cast<uint8_t*>(_mapping.rw); }
285
hasFlag(uint32_t f) const286 inline bool hasFlag(uint32_t f) const noexcept { return (_flags & f) != 0; }
addFlags(uint32_t f)287 inline void addFlags(uint32_t f) noexcept { _flags |= f; }
clearFlags(uint32_t f)288 inline void clearFlags(uint32_t f) noexcept { _flags &= ~f; }
289
isDirty() const290 inline bool isDirty() const noexcept { return hasFlag(kFlagDirty); }
makeDirty()291 inline void makeDirty() noexcept { addFlags(kFlagDirty); }
292
blockSize() const293 inline size_t blockSize() const noexcept { return _blockSize; }
294
areaSize() const295 inline uint32_t areaSize() const noexcept { return _areaSize; }
areaUsed() const296 inline uint32_t areaUsed() const noexcept { return _areaUsed; }
areaAvailable() const297 inline uint32_t areaAvailable() const noexcept { return _areaSize - _areaUsed; }
largestUnusedArea() const298 inline uint32_t largestUnusedArea() const noexcept { return _largestUnusedArea; }
299
decreaseUsedArea(uint32_t value)300 inline void decreaseUsedArea(uint32_t value) noexcept {
301 _areaUsed -= value;
302 _pool->totalAreaUsed -= value;
303 }
304
markAllocatedArea(uint32_t allocatedAreaStart,uint32_t allocatedAreaEnd)305 inline void markAllocatedArea(uint32_t allocatedAreaStart, uint32_t allocatedAreaEnd) noexcept {
306 uint32_t allocatedAreaSize = allocatedAreaEnd - allocatedAreaStart;
307
308 // Mark the newly allocated space as occupied and also the sentinel.
309 Support::bitVectorFill(_usedBitVector, allocatedAreaStart, allocatedAreaSize);
310 Support::bitVectorSetBit(_stopBitVector, allocatedAreaEnd - 1, true);
311
312 // Update search region and statistics.
313 _pool->totalAreaUsed += allocatedAreaSize;
314 _areaUsed += allocatedAreaSize;
315
316 if (areaAvailable() == 0) {
317 _searchStart = _areaSize;
318 _searchEnd = 0;
319 _largestUnusedArea = 0;
320 clearFlags(kFlagDirty);
321 }
322 else {
323 if (_searchStart == allocatedAreaStart)
324 _searchStart = allocatedAreaEnd;
325 if (_searchEnd == allocatedAreaEnd)
326 _searchEnd = allocatedAreaStart;
327 addFlags(kFlagDirty);
328 }
329 }
330
markReleasedArea(uint32_t releasedAreaStart,uint32_t releasedAreaEnd)331 inline void markReleasedArea(uint32_t releasedAreaStart, uint32_t releasedAreaEnd) noexcept {
332 uint32_t releasedAreaSize = releasedAreaEnd - releasedAreaStart;
333
334 // Update the search region and statistics.
335 _pool->totalAreaUsed -= releasedAreaSize;
336 _areaUsed -= releasedAreaSize;
337 _searchStart = Support::min(_searchStart, releasedAreaStart);
338 _searchEnd = Support::max(_searchEnd, releasedAreaEnd);
339
340 // Unmark occupied bits and also the sentinel.
341 Support::bitVectorClear(_usedBitVector, releasedAreaStart, releasedAreaSize);
342 Support::bitVectorSetBit(_stopBitVector, releasedAreaEnd - 1, false);
343
344 if (areaUsed() == 0) {
345 _searchStart = 0;
346 _searchEnd = _areaSize;
347 _largestUnusedArea = _areaSize;
348 addFlags(kFlagEmpty);
349 clearFlags(kFlagDirty);
350 }
351 else {
352 addFlags(kFlagDirty);
353 }
354 }
355
markShrunkArea(uint32_t shrunkAreaStart,uint32_t shrunkAreaEnd)356 inline void markShrunkArea(uint32_t shrunkAreaStart, uint32_t shrunkAreaEnd) noexcept {
357 uint32_t shrunkAreaSize = shrunkAreaEnd - shrunkAreaStart;
358
359 // Shrunk area cannot start at zero as it would mean that we have shrunk the first
360 // block to zero bytes, which is not allowed as such block must be released instead.
361 ASMJIT_ASSERT(shrunkAreaStart != 0);
362 ASMJIT_ASSERT(shrunkAreaSize != 0);
363
364 // Update the search region and statistics.
365 _pool->totalAreaUsed -= shrunkAreaSize;
366 _areaUsed -= shrunkAreaSize;
367 _searchStart = Support::min(_searchStart, shrunkAreaStart);
368 _searchEnd = Support::max(_searchEnd, shrunkAreaEnd);
369
370 // Unmark the released space and move the sentinel.
371 Support::bitVectorClear(_usedBitVector, shrunkAreaStart, shrunkAreaSize);
372 Support::bitVectorSetBit(_stopBitVector, shrunkAreaEnd - 1, false);
373 Support::bitVectorSetBit(_stopBitVector, shrunkAreaStart - 1, true);
374
375 addFlags(kFlagDirty);
376 }
377
378 // RBTree default CMP uses '<' and '>' operators.
operator <(const JitAllocatorBlock & other) const379 inline bool operator<(const JitAllocatorBlock& other) const noexcept { return roPtr() < other.roPtr(); }
operator >(const JitAllocatorBlock & other) const380 inline bool operator>(const JitAllocatorBlock& other) const noexcept { return roPtr() > other.roPtr(); }
381
382 // Special implementation for querying blocks by `key`, which must be in `[BlockPtr, BlockPtr + BlockSize)` range.
operator <(const uint8_t * key) const383 inline bool operator<(const uint8_t* key) const noexcept { return roPtr() + _blockSize <= key; }
operator >(const uint8_t * key) const384 inline bool operator>(const uint8_t* key) const noexcept { return roPtr() > key; }
385 };
386
387 // ============================================================================
388 // [asmjit::JitAllocator - PrivateImpl]
389 // ============================================================================
390
391 class JitAllocatorPrivateImpl : public JitAllocator::Impl {
392 public:
JitAllocatorPrivateImpl(JitAllocatorPool * pools,size_t poolCount)393 inline JitAllocatorPrivateImpl(JitAllocatorPool* pools, size_t poolCount) noexcept
394 : JitAllocator::Impl {},
395 pools(pools),
396 poolCount(poolCount) {}
~JitAllocatorPrivateImpl()397 inline ~JitAllocatorPrivateImpl() noexcept {}
398
399 //! Lock for thread safety.
400 mutable Lock lock;
401 //! System page size (also a minimum block size).
402 uint32_t pageSize;
403
404 //! Blocks from all pools in RBTree.
405 ZoneTree<JitAllocatorBlock> tree;
406 //! Allocator pools.
407 JitAllocatorPool* pools;
408 //! Number of allocator pools.
409 size_t poolCount;
410 };
411
412 static const JitAllocator::Impl JitAllocatorImpl_none {};
413 static const JitAllocator::CreateParams JitAllocatorParams_none {};
414
415 // ============================================================================
416 // [asmjit::JitAllocator - Utilities]
417 // ============================================================================
418
JitAllocatorImpl_new(const JitAllocator::CreateParams * params)419 static inline JitAllocatorPrivateImpl* JitAllocatorImpl_new(const JitAllocator::CreateParams* params) noexcept {
420 VirtMem::Info vmInfo = VirtMem::info();
421
422 if (!params)
423 params = &JitAllocatorParams_none;
424
425 uint32_t options = params->options;
426 uint32_t blockSize = params->blockSize;
427 uint32_t granularity = params->granularity;
428 uint32_t fillPattern = params->fillPattern;
429
430 // Setup pool count to [1..3].
431 size_t poolCount = 1;
432 if (options & JitAllocator::kOptionUseMultiplePools)
433 poolCount = kJitAllocatorMultiPoolCount;;
434
435 // Setup block size [64kB..256MB].
436 if (blockSize < 64 * 1024 || blockSize > 256 * 1024 * 1024 || !Support::isPowerOf2(blockSize))
437 blockSize = vmInfo.pageGranularity;
438
439 // Setup granularity [64..256].
440 if (granularity < 64 || granularity > 256 || !Support::isPowerOf2(granularity))
441 granularity = kJitAllocatorBaseGranularity;
442
443 // Setup fill-pattern.
444 if (!(options & JitAllocator::kOptionCustomFillPattern))
445 fillPattern = JitAllocator_defaultFillPattern();
446
447 size_t size = sizeof(JitAllocatorPrivateImpl) + sizeof(JitAllocatorPool) * poolCount;
448 void* p = ::malloc(size);
449 if (ASMJIT_UNLIKELY(!p))
450 return nullptr;
451
452 JitAllocatorPool* pools = reinterpret_cast<JitAllocatorPool*>((uint8_t*)p + sizeof(JitAllocatorPrivateImpl));
453 JitAllocatorPrivateImpl* impl = new(p) JitAllocatorPrivateImpl(pools, poolCount);
454
455 impl->options = options;
456 impl->blockSize = blockSize;
457 impl->granularity = granularity;
458 impl->fillPattern = fillPattern;
459 impl->pageSize = vmInfo.pageSize;
460
461 for (size_t poolId = 0; poolId < poolCount; poolId++)
462 new(&pools[poolId]) JitAllocatorPool(granularity << poolId);
463
464 return impl;
465 }
466
JitAllocatorImpl_destroy(JitAllocatorPrivateImpl * impl)467 static inline void JitAllocatorImpl_destroy(JitAllocatorPrivateImpl* impl) noexcept {
468 impl->~JitAllocatorPrivateImpl();
469 ::free(impl);
470 }
471
JitAllocatorImpl_sizeToPoolId(const JitAllocatorPrivateImpl * impl,size_t size)472 static inline size_t JitAllocatorImpl_sizeToPoolId(const JitAllocatorPrivateImpl* impl, size_t size) noexcept {
473 size_t poolId = impl->poolCount - 1;
474 size_t granularity = size_t(impl->granularity) << poolId;
475
476 while (poolId) {
477 if (Support::alignUp(size, granularity) == size)
478 break;
479 poolId--;
480 granularity >>= 1;
481 }
482
483 return poolId;
484 }
485
JitAllocatorImpl_bitVectorSizeToByteSize(uint32_t areaSize)486 static inline size_t JitAllocatorImpl_bitVectorSizeToByteSize(uint32_t areaSize) noexcept {
487 using Support::kBitWordSizeInBits;
488 return ((areaSize + kBitWordSizeInBits - 1u) / kBitWordSizeInBits) * sizeof(Support::BitWord);
489 }
490
JitAllocatorImpl_calculateIdealBlockSize(JitAllocatorPrivateImpl * impl,JitAllocatorPool * pool,size_t allocationSize)491 static inline size_t JitAllocatorImpl_calculateIdealBlockSize(JitAllocatorPrivateImpl* impl, JitAllocatorPool* pool, size_t allocationSize) noexcept {
492 JitAllocatorBlock* last = pool->blocks.last();
493 size_t blockSize = last ? last->blockSize() : size_t(impl->blockSize);
494
495 if (blockSize < kJitAllocatorMaxBlockSize)
496 blockSize *= 2u;
497
498 if (allocationSize > blockSize) {
499 blockSize = Support::alignUp(allocationSize, impl->blockSize);
500 if (ASMJIT_UNLIKELY(blockSize < allocationSize))
501 return 0; // Overflown.
502 }
503
504 return blockSize;
505 }
506
JitAllocatorImpl_fillPattern(void * mem,uint32_t pattern,size_t sizeInBytes)507 ASMJIT_FAVOR_SPEED static void JitAllocatorImpl_fillPattern(void* mem, uint32_t pattern, size_t sizeInBytes) noexcept {
508 size_t n = sizeInBytes / 4u;
509 uint32_t* p = static_cast<uint32_t*>(mem);
510
511 for (size_t i = 0; i < n; i++)
512 p[i] = pattern;
513 }
514
515 // Allocate a new `JitAllocatorBlock` for the given `blockSize`.
516 //
517 // NOTE: The block doesn't have `kFlagEmpty` flag set, because the new block
518 // is only allocated when it's actually needed, so it would be cleared anyway.
JitAllocatorImpl_newBlock(JitAllocatorPrivateImpl * impl,JitAllocatorPool * pool,size_t blockSize)519 static JitAllocatorBlock* JitAllocatorImpl_newBlock(JitAllocatorPrivateImpl* impl, JitAllocatorPool* pool, size_t blockSize) noexcept {
520 using Support::BitWord;
521 using Support::kBitWordSizeInBits;
522
523 uint32_t areaSize = uint32_t((blockSize + pool->granularity - 1) >> pool->granularityLog2);
524 uint32_t numBitWords = (areaSize + kBitWordSizeInBits - 1u) / kBitWordSizeInBits;
525
526 JitAllocatorBlock* block = static_cast<JitAllocatorBlock*>(::malloc(sizeof(JitAllocatorBlock)));
527 BitWord* bitWords = nullptr;
528 VirtMem::DualMapping virtMem {};
529 Error err = kErrorOutOfMemory;
530
531 if (block != nullptr)
532 bitWords = static_cast<BitWord*>(::malloc(size_t(numBitWords) * 2 * sizeof(BitWord)));
533
534 uint32_t blockFlags = 0;
535 if (bitWords != nullptr) {
536 if (impl->options & JitAllocator::kOptionUseDualMapping) {
537 err = VirtMem::allocDualMapping(&virtMem, blockSize, VirtMem::kAccessReadWrite | VirtMem::kAccessExecute);
538 blockFlags |= JitAllocatorBlock::kFlagDualMapped;
539 }
540 else {
541 err = VirtMem::alloc(&virtMem.ro, blockSize, VirtMem::kAccessReadWrite | VirtMem::kAccessExecute);
542 virtMem.rw = virtMem.ro;
543 }
544 }
545
546 // Out of memory.
547 if (ASMJIT_UNLIKELY(!block || !bitWords || err != kErrorOk)) {
548 if (bitWords) ::free(bitWords);
549 if (block) ::free(block);
550 return nullptr;
551 }
552
553 // Fill the memory if the secure mode is enabled.
554 if (impl->options & JitAllocator::kOptionFillUnusedMemory)
555 JitAllocatorImpl_fillPattern(virtMem.rw, impl->fillPattern, blockSize);
556
557 memset(bitWords, 0, size_t(numBitWords) * 2 * sizeof(BitWord));
558 return new(block) JitAllocatorBlock(pool, virtMem, blockSize, blockFlags, bitWords, bitWords + numBitWords, areaSize);
559 }
560
JitAllocatorImpl_deleteBlock(JitAllocatorPrivateImpl * impl,JitAllocatorBlock * block)561 static void JitAllocatorImpl_deleteBlock(JitAllocatorPrivateImpl* impl, JitAllocatorBlock* block) noexcept {
562 DebugUtils::unused(impl);
563
564 if (block->hasFlag(JitAllocatorBlock::kFlagDualMapped))
565 VirtMem::releaseDualMapping(&block->_mapping, block->blockSize());
566 else
567 VirtMem::release(block->roPtr(), block->blockSize());
568
569 ::free(block->_usedBitVector);
570 ::free(block);
571 }
572
JitAllocatorImpl_insertBlock(JitAllocatorPrivateImpl * impl,JitAllocatorBlock * block)573 static void JitAllocatorImpl_insertBlock(JitAllocatorPrivateImpl* impl, JitAllocatorBlock* block) noexcept {
574 JitAllocatorPool* pool = block->pool();
575
576 if (!pool->cursor)
577 pool->cursor = block;
578
579 // Add to RBTree and List.
580 impl->tree.insert(block);
581 pool->blocks.append(block);
582
583 // Update statistics.
584 pool->blockCount++;
585 pool->totalAreaSize += block->areaSize();
586 pool->totalOverheadBytes += sizeof(JitAllocatorBlock) + JitAllocatorImpl_bitVectorSizeToByteSize(block->areaSize()) * 2u;
587 }
588
JitAllocatorImpl_removeBlock(JitAllocatorPrivateImpl * impl,JitAllocatorBlock * block)589 static void JitAllocatorImpl_removeBlock(JitAllocatorPrivateImpl* impl, JitAllocatorBlock* block) noexcept {
590 JitAllocatorPool* pool = block->pool();
591
592 // Remove from RBTree and List.
593 if (pool->cursor == block)
594 pool->cursor = block->hasPrev() ? block->prev() : block->next();
595
596 impl->tree.remove(block);
597 pool->blocks.unlink(block);
598
599 // Update statistics.
600 pool->blockCount--;
601 pool->totalAreaSize -= block->areaSize();
602 pool->totalOverheadBytes -= sizeof(JitAllocatorBlock) + JitAllocatorImpl_bitVectorSizeToByteSize(block->areaSize()) * 2u;
603 }
604
JitAllocatorImpl_wipeOutBlock(JitAllocatorPrivateImpl * impl,JitAllocatorBlock * block)605 static void JitAllocatorImpl_wipeOutBlock(JitAllocatorPrivateImpl* impl, JitAllocatorBlock* block) noexcept {
606 JitAllocatorPool* pool = block->pool();
607
608 if (block->hasFlag(JitAllocatorBlock::kFlagEmpty))
609 return;
610
611 uint32_t areaSize = block->areaSize();
612 uint32_t granularity = pool->granularity;
613 size_t numBitWords = pool->bitWordCountFromAreaSize(areaSize);
614
615 if (impl->options & JitAllocator::kOptionFillUnusedMemory) {
616 uint8_t* rwPtr = block->rwPtr();
617 for (size_t i = 0; i < numBitWords; i++) {
618 Support::BitWordIterator<Support::BitWord> it(block->_usedBitVector[i]);
619 while (it.hasNext()) {
620 size_t index = it.next();
621 JitAllocatorImpl_fillPattern(rwPtr + index * granularity , impl->fillPattern, granularity);
622 }
623 rwPtr += Support::bitSizeOf<Support::BitWord>() * granularity;
624 }
625 }
626
627 memset(block->_usedBitVector, 0, size_t(numBitWords) * sizeof(Support::BitWord));
628 memset(block->_stopBitVector, 0, size_t(numBitWords) * sizeof(Support::BitWord));
629
630 block->_areaUsed = 0;
631 block->_largestUnusedArea = areaSize;
632 block->_searchStart = 0;
633 block->_searchEnd = areaSize;
634 block->addFlags(JitAllocatorBlock::kFlagEmpty);
635 block->clearFlags(JitAllocatorBlock::kFlagDirty);
636 }
637
638 // ============================================================================
639 // [asmjit::JitAllocator - Construction / Destruction]
640 // ============================================================================
641
JitAllocator(const CreateParams * params)642 JitAllocator::JitAllocator(const CreateParams* params) noexcept {
643 _impl = JitAllocatorImpl_new(params);
644 if (ASMJIT_UNLIKELY(!_impl))
645 _impl = const_cast<JitAllocator::Impl*>(&JitAllocatorImpl_none);
646 }
647
~JitAllocator()648 JitAllocator::~JitAllocator() noexcept {
649 if (_impl == &JitAllocatorImpl_none)
650 return;
651
652 reset(Globals::kResetHard);
653 JitAllocatorImpl_destroy(static_cast<JitAllocatorPrivateImpl*>(_impl));
654 }
655
656 // ============================================================================
657 // [asmjit::JitAllocator - Reset]
658 // ============================================================================
659
reset(uint32_t resetPolicy)660 void JitAllocator::reset(uint32_t resetPolicy) noexcept {
661 if (_impl == &JitAllocatorImpl_none)
662 return;
663
664 JitAllocatorPrivateImpl* impl = static_cast<JitAllocatorPrivateImpl*>(_impl);
665 impl->tree.reset();
666 size_t poolCount = impl->poolCount;
667
668 for (size_t poolId = 0; poolId < poolCount; poolId++) {
669 JitAllocatorPool& pool = impl->pools[poolId];
670 JitAllocatorBlock* block = pool.blocks.first();
671
672 JitAllocatorBlock* blockToKeep = nullptr;
673 if (resetPolicy != Globals::kResetHard && !(impl->options & kOptionImmediateRelease)) {
674 blockToKeep = block;
675 block = block->next();
676 }
677
678 while (block) {
679 JitAllocatorBlock* next = block->next();
680 JitAllocatorImpl_deleteBlock(impl, block);
681 block = next;
682 }
683
684 pool.reset();
685
686 if (blockToKeep) {
687 blockToKeep->_listNodes[0] = nullptr;
688 blockToKeep->_listNodes[1] = nullptr;
689 JitAllocatorImpl_wipeOutBlock(impl, blockToKeep);
690 JitAllocatorImpl_insertBlock(impl, blockToKeep);
691 pool.emptyBlockCount = 1;
692 }
693 }
694 }
695
696 // ============================================================================
697 // [asmjit::JitAllocator - Statistics]
698 // ============================================================================
699
statistics() const700 JitAllocator::Statistics JitAllocator::statistics() const noexcept {
701 Statistics statistics;
702 statistics.reset();
703
704 if (ASMJIT_LIKELY(_impl != &JitAllocatorImpl_none)) {
705 JitAllocatorPrivateImpl* impl = static_cast<JitAllocatorPrivateImpl*>(_impl);
706 LockGuard guard(impl->lock);
707
708 size_t poolCount = impl->poolCount;
709 for (size_t poolId = 0; poolId < poolCount; poolId++) {
710 const JitAllocatorPool& pool = impl->pools[poolId];
711 statistics._blockCount += size_t(pool.blockCount);
712 statistics._reservedSize += size_t(pool.totalAreaSize) * pool.granularity;
713 statistics._usedSize += size_t(pool.totalAreaUsed) * pool.granularity;
714 statistics._overheadSize += size_t(pool.totalOverheadBytes);
715 }
716 }
717
718 return statistics;
719 }
720
721 // ============================================================================
722 // [asmjit::JitAllocator - Alloc / Release]
723 // ============================================================================
724
alloc(void ** roPtrOut,void ** rwPtrOut,size_t size)725 Error JitAllocator::alloc(void** roPtrOut, void** rwPtrOut, size_t size) noexcept {
726 if (ASMJIT_UNLIKELY(_impl == &JitAllocatorImpl_none))
727 return DebugUtils::errored(kErrorNotInitialized);
728
729 JitAllocatorPrivateImpl* impl = static_cast<JitAllocatorPrivateImpl*>(_impl);
730 constexpr uint32_t kNoIndex = std::numeric_limits<uint32_t>::max();
731
732 *roPtrOut = nullptr;
733 *rwPtrOut = nullptr;
734
735 // Align to the minimum granularity by default.
736 size = Support::alignUp<size_t>(size, impl->granularity);
737 if (ASMJIT_UNLIKELY(size == 0))
738 return DebugUtils::errored(kErrorInvalidArgument);
739
740 if (ASMJIT_UNLIKELY(size > std::numeric_limits<uint32_t>::max() / 2))
741 return DebugUtils::errored(kErrorTooLarge);
742
743 LockGuard guard(impl->lock);
744 JitAllocatorPool* pool = &impl->pools[JitAllocatorImpl_sizeToPoolId(impl, size)];
745
746 uint32_t areaIndex = kNoIndex;
747 uint32_t areaSize = uint32_t(pool->areaSizeFromByteSize(size));
748
749 // Try to find the requested memory area in existing blocks.
750 JitAllocatorBlock* block = pool->blocks.first();
751 if (block) {
752 JitAllocatorBlock* initial = block;
753 do {
754 JitAllocatorBlock* next = block->hasNext() ? block->next() : pool->blocks.first();
755 if (block->areaAvailable() >= areaSize) {
756 if (block->isDirty() || block->largestUnusedArea() >= areaSize) {
757 BitVectorRangeIterator<Support::BitWord, 0> it(block->_usedBitVector, pool->bitWordCountFromAreaSize(block->areaSize()), block->_searchStart, block->_searchEnd);
758
759 size_t rangeStart = 0;
760 size_t rangeEnd = block->areaSize();
761
762 size_t searchStart = SIZE_MAX;
763 size_t largestArea = 0;
764
765 while (it.nextRange(&rangeStart, &rangeEnd, areaSize)) {
766 size_t rangeSize = rangeEnd - rangeStart;
767 if (rangeSize >= areaSize) {
768 areaIndex = uint32_t(rangeStart);
769 break;
770 }
771
772 searchStart = Support::min(searchStart, rangeStart);
773 largestArea = Support::max(largestArea, rangeSize);
774 }
775
776 if (areaIndex != kNoIndex)
777 break;
778
779 if (searchStart != SIZE_MAX) {
780 // Because we have iterated over the entire block, we can now mark the
781 // largest unused area that can be used to cache the next traversal.
782 size_t searchEnd = rangeEnd;
783
784 block->_searchStart = uint32_t(searchStart);
785 block->_searchEnd = uint32_t(searchEnd);
786 block->_largestUnusedArea = uint32_t(largestArea);
787 block->clearFlags(JitAllocatorBlock::kFlagDirty);
788 }
789 }
790 }
791
792 block = next;
793 } while (block != initial);
794 }
795
796 // Allocate a new block if there is no region of a required width.
797 if (areaIndex == kNoIndex) {
798 size_t blockSize = JitAllocatorImpl_calculateIdealBlockSize(impl, pool, size);
799 if (ASMJIT_UNLIKELY(!blockSize))
800 return DebugUtils::errored(kErrorOutOfMemory);
801
802 block = JitAllocatorImpl_newBlock(impl, pool, blockSize);
803 areaIndex = 0;
804
805 if (ASMJIT_UNLIKELY(!block))
806 return DebugUtils::errored(kErrorOutOfMemory);
807
808 JitAllocatorImpl_insertBlock(impl, block);
809 block->_searchStart = areaSize;
810 block->_largestUnusedArea = block->areaSize() - areaSize;
811 }
812 else if (block->hasFlag(JitAllocatorBlock::kFlagEmpty)) {
813 pool->emptyBlockCount--;
814 block->clearFlags(JitAllocatorBlock::kFlagEmpty);
815 }
816
817 // Update statistics.
818 block->markAllocatedArea(areaIndex, areaIndex + areaSize);
819
820 // Return a pointer to the allocated memory.
821 size_t offset = pool->byteSizeFromAreaSize(areaIndex);
822 ASMJIT_ASSERT(offset <= block->blockSize() - size);
823
824 *roPtrOut = block->roPtr() + offset;
825 *rwPtrOut = block->rwPtr() + offset;
826 return kErrorOk;
827 }
828
release(void * roPtr)829 Error JitAllocator::release(void* roPtr) noexcept {
830 if (ASMJIT_UNLIKELY(_impl == &JitAllocatorImpl_none))
831 return DebugUtils::errored(kErrorNotInitialized);
832
833 if (ASMJIT_UNLIKELY(!roPtr))
834 return DebugUtils::errored(kErrorInvalidArgument);
835
836 JitAllocatorPrivateImpl* impl = static_cast<JitAllocatorPrivateImpl*>(_impl);
837 LockGuard guard(impl->lock);
838
839 JitAllocatorBlock* block = impl->tree.get(static_cast<uint8_t*>(roPtr));
840 if (ASMJIT_UNLIKELY(!block))
841 return DebugUtils::errored(kErrorInvalidState);
842
843 // Offset relative to the start of the block.
844 JitAllocatorPool* pool = block->pool();
845 size_t offset = (size_t)((uint8_t*)roPtr - block->roPtr());
846
847 // The first bit representing the allocated area and its size.
848 uint32_t areaIndex = uint32_t(offset >> pool->granularityLog2);
849 uint32_t areaEnd = uint32_t(Support::bitVectorIndexOf(block->_stopBitVector, areaIndex, true)) + 1;
850 uint32_t areaSize = areaEnd - areaIndex;
851
852 block->markReleasedArea(areaIndex, areaEnd);
853
854 // Fill the released memory if the secure mode is enabled.
855 if (impl->options & kOptionFillUnusedMemory)
856 JitAllocatorImpl_fillPattern(block->rwPtr() + areaIndex * pool->granularity, impl->fillPattern, areaSize * pool->granularity);
857
858 // Release the whole block if it became empty.
859 if (block->areaUsed() == 0) {
860 if (pool->emptyBlockCount || (impl->options & kOptionImmediateRelease)) {
861 JitAllocatorImpl_removeBlock(impl, block);
862 JitAllocatorImpl_deleteBlock(impl, block);
863 }
864 else {
865 pool->emptyBlockCount++;
866 }
867 }
868
869 return kErrorOk;
870 }
871
shrink(void * roPtr,size_t newSize)872 Error JitAllocator::shrink(void* roPtr, size_t newSize) noexcept {
873 if (ASMJIT_UNLIKELY(_impl == &JitAllocatorImpl_none))
874 return DebugUtils::errored(kErrorNotInitialized);
875
876 if (ASMJIT_UNLIKELY(!roPtr))
877 return DebugUtils::errored(kErrorInvalidArgument);
878
879 if (ASMJIT_UNLIKELY(newSize == 0))
880 return release(roPtr);
881
882 JitAllocatorPrivateImpl* impl = static_cast<JitAllocatorPrivateImpl*>(_impl);
883 LockGuard guard(impl->lock);
884 JitAllocatorBlock* block = impl->tree.get(static_cast<uint8_t*>(roPtr));
885
886 if (ASMJIT_UNLIKELY(!block))
887 return DebugUtils::errored(kErrorInvalidArgument);
888
889 // Offset relative to the start of the block.
890 JitAllocatorPool* pool = block->pool();
891 size_t offset = (size_t)((uint8_t*)roPtr - block->roPtr());
892
893 // The first bit representing the allocated area and its size.
894 uint32_t areaStart = uint32_t(offset >> pool->granularityLog2);
895 uint32_t areaEnd = uint32_t(Support::bitVectorIndexOf(block->_stopBitVector, areaStart, true)) + 1;
896
897 uint32_t areaPrevSize = areaEnd - areaStart;
898 uint32_t areaShrunkSize = pool->areaSizeFromByteSize(newSize);
899
900 if (ASMJIT_UNLIKELY(areaShrunkSize > areaPrevSize))
901 return DebugUtils::errored(kErrorInvalidState);
902
903 uint32_t areaDiff = areaPrevSize - areaShrunkSize;
904 if (areaDiff) {
905 block->markShrunkArea(areaStart + areaShrunkSize, areaEnd);
906
907 // Fill released memory if the secure mode is enabled.
908 if (impl->options & kOptionFillUnusedMemory)
909 JitAllocatorImpl_fillPattern(block->rwPtr() + (areaStart + areaShrunkSize) * pool->granularity, fillPattern(), areaDiff * pool->granularity);
910 }
911
912 return kErrorOk;
913 }
914
915 // ============================================================================
916 // [asmjit::JitAllocator - Unit]
917 // ============================================================================
918
919 #if defined(ASMJIT_TEST)
920 // A pseudo random number generator based on a paper by Sebastiano Vigna:
921 // http://vigna.di.unimi.it/ftp/papers/xorshiftplus.pdf
922 class Random {
923 public:
924 // Constants suggested as `23/18/5`.
925 enum Steps : uint32_t {
926 kStep1_SHL = 23,
927 kStep2_SHR = 18,
928 kStep3_SHR = 5
929 };
930
Random(uint64_t seed=0)931 inline explicit Random(uint64_t seed = 0) noexcept { reset(seed); }
932 inline Random(const Random& other) noexcept = default;
933
reset(uint64_t seed=0)934 inline void reset(uint64_t seed = 0) noexcept {
935 // The number is arbitrary, it means nothing.
936 constexpr uint64_t kZeroSeed = 0x1F0A2BE71D163FA0u;
937
938 // Generate the state data by using splitmix64.
939 for (uint32_t i = 0; i < 2; i++) {
940 seed += 0x9E3779B97F4A7C15u;
941 uint64_t x = seed;
942 x = (x ^ (x >> 30)) * 0xBF58476D1CE4E5B9u;
943 x = (x ^ (x >> 27)) * 0x94D049BB133111EBu;
944 x = (x ^ (x >> 31));
945 _state[i] = x != 0 ? x : kZeroSeed;
946 }
947 }
948
nextUInt32()949 inline uint32_t nextUInt32() noexcept {
950 return uint32_t(nextUInt64() >> 32);
951 }
952
nextUInt64()953 inline uint64_t nextUInt64() noexcept {
954 uint64_t x = _state[0];
955 uint64_t y = _state[1];
956
957 x ^= x << kStep1_SHL;
958 y ^= y >> kStep3_SHR;
959 x ^= x >> kStep2_SHR;
960 x ^= y;
961
962 _state[0] = y;
963 _state[1] = x;
964 return x + y;
965 }
966
967 uint64_t _state[2];
968 };
969
970 // Helper class to verify that JitAllocator doesn't return addresses that overlap.
971 class JitAllocatorWrapper {
972 public:
973 // Address to a memory region of a given size.
974 class Range {
975 public:
Range(uint8_t * addr,size_t size)976 inline Range(uint8_t* addr, size_t size) noexcept
977 : addr(addr),
978 size(size) {}
979 uint8_t* addr;
980 size_t size;
981 };
982
983 // Based on JitAllocator::Block, serves our purpose well...
984 class Record : public ZoneTreeNodeT<Record>,
985 public Range {
986 public:
Record(uint8_t * addr,size_t size)987 inline Record(uint8_t* addr, size_t size)
988 : ZoneTreeNodeT<Record>(),
989 Range(addr, size) {}
990
operator <(const Record & other) const991 inline bool operator<(const Record& other) const noexcept { return addr < other.addr; }
operator >(const Record & other) const992 inline bool operator>(const Record& other) const noexcept { return addr > other.addr; }
993
operator <(const uint8_t * key) const994 inline bool operator<(const uint8_t* key) const noexcept { return addr + size <= key; }
operator >(const uint8_t * key) const995 inline bool operator>(const uint8_t* key) const noexcept { return addr > key; }
996 };
997
998 Zone _zone;
999 ZoneAllocator _heap;
1000 ZoneTree<Record> _records;
1001 JitAllocator _allocator;
1002
JitAllocatorWrapper(const JitAllocator::CreateParams * params)1003 explicit JitAllocatorWrapper(const JitAllocator::CreateParams* params) noexcept
1004 : _zone(1024 * 1024),
1005 _heap(&_zone),
1006 _allocator(params) {}
1007
_insert(void * p_,size_t size)1008 void _insert(void* p_, size_t size) noexcept {
1009 uint8_t* p = static_cast<uint8_t*>(p_);
1010 uint8_t* pEnd = p + size - 1;
1011
1012 Record* record;
1013
1014 record = _records.get(p);
1015 if (record)
1016 EXPECT(record == nullptr, "Address [%p:%p] collides with a newly allocated [%p:%p]\n", record->addr, record->addr + record->size, p, p + size);
1017
1018 record = _records.get(pEnd);
1019 if (record)
1020 EXPECT(record == nullptr, "Address [%p:%p] collides with a newly allocated [%p:%p]\n", record->addr, record->addr + record->size, p, p + size);
1021
1022 record = _heap.newT<Record>(p, size);
1023 EXPECT(record != nullptr, "Out of memory, cannot allocate 'Record'");
1024
1025 _records.insert(record);
1026 }
1027
_remove(void * p)1028 void _remove(void* p) noexcept {
1029 Record* record = _records.get(static_cast<uint8_t*>(p));
1030 EXPECT(record != nullptr, "Address [%p] doesn't exist\n", p);
1031
1032 _records.remove(record);
1033 _heap.release(record, sizeof(Record));
1034 }
1035
alloc(size_t size)1036 void* alloc(size_t size) noexcept {
1037 void* roPtr;
1038 void* rwPtr;
1039
1040 Error err = _allocator.alloc(&roPtr, &rwPtr, size);
1041 EXPECT(err == kErrorOk, "JitAllocator failed to allocate %zu bytes\n", size);
1042
1043 _insert(roPtr, size);
1044 return roPtr;
1045 }
1046
release(void * p)1047 void release(void* p) noexcept {
1048 _remove(p);
1049 EXPECT(_allocator.release(p) == kErrorOk, "JitAllocator failed to release '%p'\n", p);
1050 }
1051
shrink(void * p,size_t newSize)1052 void shrink(void* p, size_t newSize) noexcept {
1053 Record* record = _records.get(static_cast<uint8_t*>(p));
1054 EXPECT(record != nullptr, "Address [%p] doesn't exist\n", p);
1055
1056 if (!newSize)
1057 return release(p);
1058
1059 Error err = _allocator.shrink(p, newSize);
1060 EXPECT(err == kErrorOk, "JitAllocator failed to shrink %p to %zu bytes\n", p, newSize);
1061
1062 record->size = newSize;
1063 }
1064 };
1065
JitAllocatorTest_shuffle(void ** ptrArray,size_t count,Random & prng)1066 static void JitAllocatorTest_shuffle(void** ptrArray, size_t count, Random& prng) noexcept {
1067 for (size_t i = 0; i < count; ++i)
1068 std::swap(ptrArray[i], ptrArray[size_t(prng.nextUInt32() % count)]);
1069 }
1070
JitAllocatorTest_usage(JitAllocator & allocator)1071 static void JitAllocatorTest_usage(JitAllocator& allocator) noexcept {
1072 JitAllocator::Statistics stats = allocator.statistics();
1073 INFO(" Block Count : %9llu [Blocks]" , (unsigned long long)(stats.blockCount()));
1074 INFO(" Reserved (VirtMem): %9llu [Bytes]" , (unsigned long long)(stats.reservedSize()));
1075 INFO(" Used (VirtMem): %9llu [Bytes] (%.1f%%)", (unsigned long long)(stats.usedSize()), stats.usedSizeAsPercent());
1076 INFO(" Overhead (HeapMem): %9llu [Bytes] (%.1f%%)", (unsigned long long)(stats.overheadSize()), stats.overheadSizeAsPercent());
1077 }
1078
1079 template<typename T, size_t kPatternSize, bool Bit>
BitVectorRangeIterator_testRandom(Random & rnd,size_t count)1080 static void BitVectorRangeIterator_testRandom(Random& rnd, size_t count) noexcept {
1081 for (size_t i = 0; i < count; i++) {
1082 T in[kPatternSize];
1083 T out[kPatternSize];
1084
1085 for (size_t j = 0; j < kPatternSize; j++) {
1086 in[j] = T(uint64_t(rnd.nextUInt32() & 0xFFu) * 0x0101010101010101);
1087 out[j] = Bit == 0 ? Support::allOnes<T>() : T(0);
1088 }
1089
1090 {
1091 BitVectorRangeIterator<T, Bit> it(in, kPatternSize);
1092 size_t rangeStart, rangeEnd;
1093 while (it.nextRange(&rangeStart, &rangeEnd)) {
1094 if (Bit)
1095 Support::bitVectorFill(out, rangeStart, rangeEnd - rangeStart);
1096 else
1097 Support::bitVectorClear(out, rangeStart, rangeEnd - rangeStart);
1098 }
1099 }
1100
1101 for (size_t j = 0; j < kPatternSize; j++) {
1102 EXPECT(in[j] == out[j], "Invalid pattern detected at [%zu] (%llX != %llX", j, (unsigned long long)in[j], (unsigned long long)out[j]);
1103 }
1104 }
1105 }
1106
UNIT(jit_allocator)1107 UNIT(jit_allocator) {
1108 size_t kCount = BrokenAPI::hasArg("--quick") ? 1000 : 100000;
1109
1110 struct TestParams {
1111 const char* name;
1112 uint32_t options;
1113 uint32_t blockSize;
1114 uint32_t granularity;
1115 };
1116
1117 static TestParams testParams[] = {
1118 { "Default", 0, 0, 0 },
1119 { "16MB blocks", 0, 16 * 1024 * 1024, 0 },
1120 { "256B granularity", 0, 0, 256 },
1121 { "kOptionUseDualMapping", JitAllocator::kOptionUseDualMapping, 0, 0 },
1122 { "kOptionUseMultiplePools", JitAllocator::kOptionUseMultiplePools, 0, 0 },
1123 { "kOptionFillUnusedMemory", JitAllocator::kOptionFillUnusedMemory, 0, 0 },
1124 { "kOptionImmediateRelease", JitAllocator::kOptionImmediateRelease, 0, 0 },
1125 { "kOptionUseDualMapping | kOptionFillUnusedMemory", JitAllocator::kOptionUseDualMapping | JitAllocator::kOptionFillUnusedMemory, 0, 0 }
1126 };
1127
1128 INFO("BitVectorRangeIterator<uint32_t>");
1129 {
1130 Random rnd;
1131 BitVectorRangeIterator_testRandom<uint32_t, 64, 0>(rnd, kCount);
1132 }
1133
1134 INFO("BitVectorRangeIterator<uint64_t>");
1135 {
1136 Random rnd;
1137 BitVectorRangeIterator_testRandom<uint64_t, 64, 0>(rnd, kCount);
1138 }
1139
1140 for (uint32_t testId = 0; testId < ASMJIT_ARRAY_SIZE(testParams); testId++) {
1141 INFO("JitAllocator(%s)", testParams[testId].name);
1142
1143 JitAllocator::CreateParams params {};
1144 params.options = testParams[testId].options;
1145 params.blockSize = testParams[testId].blockSize;
1146 params.granularity = testParams[testId].granularity;
1147
1148 size_t fixedBlockSize = 256;
1149
1150 JitAllocatorWrapper wrapper(¶ms);
1151 Random prng(100);
1152
1153 size_t i;
1154
1155 INFO(" Memory alloc/release test - %d allocations", kCount);
1156
1157 void** ptrArray = (void**)::malloc(sizeof(void*) * size_t(kCount));
1158 EXPECT(ptrArray != nullptr,
1159 "Couldn't allocate '%u' bytes for pointer-array", unsigned(sizeof(void*) * size_t(kCount)));
1160
1161 // Random blocks tests...
1162 INFO(" Allocating random blocks...");
1163 for (i = 0; i < kCount; i++)
1164 ptrArray[i] = wrapper.alloc((prng.nextUInt32() % 1024) + 8);
1165 JitAllocatorTest_usage(wrapper._allocator);
1166
1167 INFO(" Releasing all allocated blocks from the beginning...");
1168 for (i = 0; i < kCount; i++)
1169 wrapper.release(ptrArray[i]);
1170 JitAllocatorTest_usage(wrapper._allocator);
1171
1172 INFO(" Allocating random blocks again...", kCount);
1173 for (i = 0; i < kCount; i++)
1174 ptrArray[i] = wrapper.alloc((prng.nextUInt32() % 1024) + 8);
1175 JitAllocatorTest_usage(wrapper._allocator);
1176
1177 INFO(" Shuffling allocated blocks...");
1178 JitAllocatorTest_shuffle(ptrArray, unsigned(kCount), prng);
1179
1180 INFO(" Releasing 50%% of allocated blocks...");
1181 for (i = 0; i < kCount / 2; i++)
1182 wrapper.release(ptrArray[i]);
1183 JitAllocatorTest_usage(wrapper._allocator);
1184
1185 INFO(" Allocating 50%% more blocks again...");
1186 for (i = 0; i < kCount / 2; i++)
1187 ptrArray[i] = wrapper.alloc((prng.nextUInt32() % 1024) + 8);
1188 JitAllocatorTest_usage(wrapper._allocator);
1189
1190 INFO(" Releasing all allocated blocks from the end...");
1191 for (i = 0; i < kCount; i++)
1192 wrapper.release(ptrArray[kCount - i - 1]);
1193 JitAllocatorTest_usage(wrapper._allocator);
1194
1195 // Fixed blocks tests...
1196 INFO(" Allocating %zuB blocks...", fixedBlockSize);
1197 for (i = 0; i < kCount / 2; i++)
1198 ptrArray[i] = wrapper.alloc(fixedBlockSize);
1199 JitAllocatorTest_usage(wrapper._allocator);
1200
1201 INFO(" Shrinking each %zuB block to 1 byte", fixedBlockSize);
1202 for (i = 0; i < kCount / 2; i++)
1203 wrapper.shrink(ptrArray[i], 1);
1204 JitAllocatorTest_usage(wrapper._allocator);
1205
1206 INFO(" Allocating more 64B blocks...", 64);
1207 for (i = kCount / 2; i < kCount; i++)
1208 ptrArray[i] = wrapper.alloc(64);
1209 JitAllocatorTest_usage(wrapper._allocator);
1210
1211 INFO(" Releasing all blocks from the beginning...");
1212 for (i = 0; i < kCount; i++)
1213 wrapper.release(ptrArray[i]);
1214 JitAllocatorTest_usage(wrapper._allocator);
1215
1216 INFO(" Allocating %zuB blocks...", fixedBlockSize);
1217 for (i = 0; i < kCount; i++)
1218 ptrArray[i] = wrapper.alloc(fixedBlockSize);
1219 JitAllocatorTest_usage(wrapper._allocator);
1220
1221 INFO(" Shuffling allocated blocks...");
1222 JitAllocatorTest_shuffle(ptrArray, unsigned(kCount), prng);
1223
1224 INFO(" Releasing 50%% of allocated blocks...");
1225 for (i = 0; i < kCount / 2; i++)
1226 wrapper.release(ptrArray[i]);
1227 JitAllocatorTest_usage(wrapper._allocator);
1228
1229 INFO(" Allocating 50%% more %zuB blocks again...", fixedBlockSize);
1230 for (i = 0; i < kCount / 2; i++)
1231 ptrArray[i] = wrapper.alloc(fixedBlockSize);
1232 JitAllocatorTest_usage(wrapper._allocator);
1233
1234 INFO(" Releasing all allocated blocks from the end...");
1235 for (i = 0; i < kCount; i++)
1236 wrapper.release(ptrArray[kCount - i - 1]);
1237 JitAllocatorTest_usage(wrapper._allocator);
1238
1239 ::free(ptrArray);
1240 }
1241 }
1242 #endif
1243
1244 ASMJIT_END_NAMESPACE
1245
1246 #endif
1247