1/*
2 Copyright (c) 2005-2019 Intel Corporation
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15*/
16
17
18#include "tbbmalloc_internal.h"
19#include <errno.h>
20#include <new> /* for placement new */
21#include <string.h> /* for memset */
22
23#include "../tbb/tbb_version.h"
24#include "../tbb/tbb_environment.h"
25#include "../tbb/itt_notify.h" // for __TBB_load_ittnotify()
26
27#if USE_PTHREAD
28 #define TlsSetValue_func pthread_setspecific
29 #define TlsGetValue_func pthread_getspecific
30 #define GetMyTID() pthread_self()
31 #include <sched.h>
32 inline void do_yield() {sched_yield();}
33 extern "C" { static void mallocThreadShutdownNotification(void*); }
34 #if __sun || __SUNPRO_CC
35 #define __asm__ asm
36 #endif
37 #include <unistd.h> // sysconf(_SC_PAGESIZE)
38#elif USE_WINTHREAD
39 #define GetMyTID() GetCurrentThreadId()
40#if __TBB_WIN8UI_SUPPORT
41 #include<thread>
42 #define TlsSetValue_func FlsSetValue
43 #define TlsGetValue_func FlsGetValue
44 #define TlsAlloc() FlsAlloc(NULL)
45 #define TLS_ALLOC_FAILURE FLS_OUT_OF_INDEXES
46 #define TlsFree FlsFree
47 inline void do_yield() {std::this_thread::yield();}
48#else
49 #define TlsSetValue_func TlsSetValue
50 #define TlsGetValue_func TlsGetValue
51 #define TLS_ALLOC_FAILURE TLS_OUT_OF_INDEXES
52 inline void do_yield() {SwitchToThread();}
53#endif
54#else
55 #error Must define USE_PTHREAD or USE_WINTHREAD
56
57#endif
58
59
60#define FREELIST_NONBLOCKING 1
61
62namespace rml {
63class MemoryPool;
64namespace internal {
65
66class Block;
67class MemoryPool;
68
69#if MALLOC_CHECK_RECURSION
70
71inline bool isMallocInitialized();
72
73bool RecursiveMallocCallProtector::noRecursion() {
74 MALLOC_ASSERT(isMallocInitialized(),
75 "Recursion status can be checked only when initialization was done.");
76 return !mallocRecursionDetected;
77}
78
79#endif // MALLOC_CHECK_RECURSION
80
81/** Support for handling the special UNUSABLE pointer state **/
82const intptr_t UNUSABLE = 0x1;
83inline bool isSolidPtr( void* ptr ) {
84 return (UNUSABLE|(intptr_t)ptr)!=UNUSABLE;
85}
86inline bool isNotForUse( void* ptr ) {
87 return (intptr_t)ptr==UNUSABLE;
88}
89
90/*
91 * Block::objectSize value used to mark blocks allocated by startupAlloc
92 */
93const uint16_t startupAllocObjSizeMark = ~(uint16_t)0;
94
95/*
96 * The following constant is used to define the size of struct Block, the block header.
97 * The intent is to have the size of a Block multiple of the cache line size, this allows us to
98 * get good alignment at the cost of some overhead equal to the amount of padding included in the Block.
99 */
100const int blockHeaderAlignment = estimatedCacheLineSize;
101
102/********* The data structures and global objects **************/
103
104/*
105 * The malloc routines themselves need to be able to occasionally malloc some space,
106 * in order to set up the structures used by the thread local structures. This
107 * routine performs that functions.
108 */
109class BootStrapBlocks {
110 MallocMutex bootStrapLock;
111 Block *bootStrapBlock;
112 Block *bootStrapBlockUsed;
113 FreeObject *bootStrapObjectList;
114public:
115 void *allocate(MemoryPool *memPool, size_t size);
116 void free(void* ptr);
117 void reset();
118};
119
120#if USE_INTERNAL_TID
121class ThreadId {
122 static tls_key_t Tid_key;
123 static intptr_t ThreadCount;
124
125 unsigned int id;
126
127 static unsigned int tlsNumber() {
128 unsigned int result = reinterpret_cast<intptr_t>(TlsGetValue_func(Tid_key));
129 if( !result ) {
130 RecursiveMallocCallProtector scoped;
131 // Thread-local value is zero -> first call from this thread,
132 // need to initialize with next ID value (IDs start from 1)
133 result = AtomicIncrement(ThreadCount); // returned new value!
134 TlsSetValue_func( Tid_key, reinterpret_cast<void*>(result) );
135 }
136 return result;
137 }
138public:
139 static bool init() {
140#if USE_WINTHREAD
141 Tid_key = TlsAlloc();
142 if (Tid_key == TLS_ALLOC_FAILURE)
143 return false;
144#else
145 int status = pthread_key_create( &Tid_key, NULL );
146 if ( status ) {
147 fprintf (stderr, "The memory manager cannot create tls key during initialization\n");
148 return false;
149 }
150#endif /* USE_WINTHREAD */
151 return true;
152 }
153 static void destroy() {
154 if( Tid_key ) {
155#if USE_WINTHREAD
156 BOOL status = !(TlsFree( Tid_key )); // fail is zero
157#else
158 int status = pthread_key_delete( Tid_key );
159#endif /* USE_WINTHREAD */
160 if ( status )
161 fprintf (stderr, "The memory manager cannot delete tls key\n");
162 Tid_key = 0;
163 }
164 }
165
166 ThreadId() : id(ThreadId::tlsNumber()) {}
167 bool isCurrentThreadId() const { return id == ThreadId::tlsNumber(); }
168
169#if COLLECT_STATISTICS || MALLOC_TRACE
170 friend unsigned int getThreadId() { return ThreadId::tlsNumber(); }
171#endif
172#if COLLECT_STATISTICS
173 static unsigned getMaxThreadId() { return ThreadCount; }
174
175 friend int STAT_increment(ThreadId tid, int bin, int ctr);
176#endif
177};
178
179tls_key_t ThreadId::Tid_key;
180intptr_t ThreadId::ThreadCount;
181
182#if COLLECT_STATISTICS
183int STAT_increment(ThreadId tid, int bin, int ctr)
184{
185 return ::STAT_increment(tid.id, bin, ctr);
186}
187#endif
188
189#else // USE_INTERNAL_TID
190
191class ThreadId {
192#if USE_PTHREAD
193 pthread_t tid;
194#else
195 DWORD tid;
196#endif
197public:
198 ThreadId() : tid(GetMyTID()) {}
199#if USE_PTHREAD
200 bool isCurrentThreadId() const { return pthread_equal(pthread_self(), tid); }
201#else
202 bool isCurrentThreadId() const { return GetCurrentThreadId() == tid; }
203#endif
204 static bool init() { return true; }
205 static void destroy() {}
206};
207
208#endif // USE_INTERNAL_TID
209
210/*********** Code to provide thread ID and a thread-local void pointer **********/
211
212bool TLSKey::init()
213{
214#if USE_WINTHREAD
215 TLS_pointer_key = TlsAlloc();
216 if (TLS_pointer_key == TLS_ALLOC_FAILURE)
217 return false;
218#else
219 int status = pthread_key_create( &TLS_pointer_key, mallocThreadShutdownNotification );
220 if ( status )
221 return false;
222#endif /* USE_WINTHREAD */
223 return true;
224}
225
226bool TLSKey::destroy()
227{
228#if USE_WINTHREAD
229 BOOL status1 = !(TlsFree(TLS_pointer_key)); // fail is zero
230#else
231 int status1 = pthread_key_delete(TLS_pointer_key);
232#endif /* USE_WINTHREAD */
233 MALLOC_ASSERT(!status1, "The memory manager cannot delete tls key.");
234 return status1==0;
235}
236
237inline TLSData* TLSKey::getThreadMallocTLS() const
238{
239 return (TLSData *)TlsGetValue_func( TLS_pointer_key );
240}
241
242inline void TLSKey::setThreadMallocTLS( TLSData * newvalue ) {
243 RecursiveMallocCallProtector scoped;
244 TlsSetValue_func( TLS_pointer_key, newvalue );
245}
246
247/* The 'next' field in the block header has to maintain some invariants:
248 * it needs to be on a 16K boundary and the first field in the block.
249 * Any value stored there needs to have the lower 14 bits set to 0
250 * so that various assert work. This means that if you want to smash this memory
251 * for debugging purposes you will need to obey this invariant.
252 * The total size of the header needs to be a power of 2 to simplify
253 * the alignment requirements. For now it is a 128 byte structure.
254 * To avoid false sharing, the fields changed only locally are separated
255 * from the fields changed by foreign threads.
256 * Changing the size of the block header would require to change
257 * some bin allocation sizes, in particular "fitting" sizes (see above).
258 */
259class Bin;
260class StartupBlock;
261
262class MemoryPool {
263 // if no explicit grainsize, expect to see malloc in user's pAlloc
264 // and set reasonable low granularity
265 static const size_t defaultGranularity = estimatedCacheLineSize;
266
267 MemoryPool(); // deny
268public:
269 static MallocMutex memPoolListLock;
270
271 // list of all active pools is used to release
272 // all TLS data on thread termination or library unload
273 MemoryPool *next,
274 *prev;
275 ExtMemoryPool extMemPool;
276 BootStrapBlocks bootStrapBlocks;
277
278 static void initDefaultPool();
279
280 bool init(intptr_t poolId, const MemPoolPolicy* memPoolPolicy);
281 bool reset();
282 bool destroy();
283 void onThreadShutdown(TLSData *tlsData);
284
285 inline TLSData *getTLS(bool create);
286 void clearTLS() { extMemPool.tlsPointerKey.setThreadMallocTLS(NULL); }
287
288 Block *getEmptyBlock(size_t size);
289 void returnEmptyBlock(Block *block, bool poolTheBlock);
290
291 // get/put large object to/from local large object cache
292 void *getFromLLOCache(TLSData *tls, size_t size, size_t alignment);
293 void putToLLOCache(TLSData *tls, void *object);
294};
295
296static intptr_t defaultMemPool_space[sizeof(MemoryPool)/sizeof(intptr_t) +
297 (sizeof(MemoryPool)%sizeof(intptr_t)? 1 : 0)];
298static MemoryPool *defaultMemPool = (MemoryPool*)defaultMemPool_space;
299const size_t MemoryPool::defaultGranularity;
300// zero-initialized
301MallocMutex MemoryPool::memPoolListLock;
302// TODO: move huge page status to default pool, because that's its states
303HugePagesStatus hugePages;
304static bool usedBySrcIncluded = false;
305
306// Padding helpers
307template<size_t padd>
308struct PaddingImpl {
309 size_t __padding[padd];
310};
311
312template<>
313struct PaddingImpl<0> {};
314
315template<int N>
316struct Padding : PaddingImpl<N/sizeof(size_t)> {};
317
318// Slab block is 16KB-aligned. To prevent false sharing, separate locally-accessed
319// fields and fields commonly accessed by not owner threads.
320class GlobalBlockFields : public BlockI {
321protected:
322 FreeObject *publicFreeList;
323 Block *nextPrivatizable;
324 MemoryPool *poolPtr;
325};
326
327class LocalBlockFields : public GlobalBlockFields, Padding<blockHeaderAlignment - sizeof(GlobalBlockFields)> {
328protected:
329 Block *next;
330 Block *previous; /* Use double linked list to speed up removal */
331 FreeObject *bumpPtr; /* Bump pointer moves from the end to the beginning of a block */
332 FreeObject *freeList;
333 /* Pointer to local data for the owner thread. Used for fast finding tls
334 when releasing object from a block that current thread owned.
335 NULL for orphaned blocks. */
336 TLSData *tlsPtr;
337 ThreadId ownerTid; /* the ID of the thread that owns or last owned the block */
338 BackRefIdx backRefIdx;
339 uint16_t allocatedCount; /* Number of objects allocated (obviously by the owning thread) */
340 uint16_t objectSize;
341 bool isFull;
342
343 friend class FreeBlockPool;
344 friend class StartupBlock;
345 friend class LifoList;
346 friend void *BootStrapBlocks::allocate(MemoryPool *, size_t);
347 friend bool OrphanedBlocks::cleanup(Backend*);
348 friend Block *MemoryPool::getEmptyBlock(size_t);
349};
350
351// Use inheritance to guarantee that a user data start on next cache line.
352// Can't use member for it, because when LocalBlockFields already on cache line,
353// we must have no additional memory consumption for all compilers.
354class Block : public LocalBlockFields,
355 Padding<2*blockHeaderAlignment - sizeof(LocalBlockFields)> {
356public:
357 bool empty() const {
358 if (allocatedCount > 0) return false;
359 MALLOC_ASSERT(!isSolidPtr(publicFreeList), ASSERT_TEXT);
360 return true;
361 }
362 inline FreeObject* allocate();
363 inline FreeObject *allocateFromFreeList();
364
365 inline bool adjustFullness();
366 void adjustPositionInBin(Bin* bin = NULL);
367
368 bool freeListNonNull() { return freeList; }
369 void freePublicObject(FreeObject *objectToFree);
370 inline void freeOwnObject(void *object);
371 void reset();
372 void privatizePublicFreeList( bool reset = true );
373 void restoreBumpPtr();
374 void privatizeOrphaned(TLSData *tls, unsigned index);
375 bool readyToShare();
376 void shareOrphaned(intptr_t binTag, unsigned index);
377 unsigned int getSize() const {
378 MALLOC_ASSERT(isStartupAllocObject() || objectSize<minLargeObjectSize,
379 "Invalid object size");
380 return isStartupAllocObject()? 0 : objectSize;
381 }
382 const BackRefIdx *getBackRefIdx() const { return &backRefIdx; }
383 inline bool isOwnedByCurrentThread() const;
384 bool isStartupAllocObject() const { return objectSize == startupAllocObjSizeMark; }
385 inline FreeObject *findObjectToFree(const void *object) const;
386 void checkFreePrecond(const void *object) const {
387#if MALLOC_DEBUG
388 const char *msg = "Possible double free or heap corruption.";
389 // small objects are always at least sizeof(size_t) Byte aligned,
390 // try to check this before this dereference as for invalid objects
391 // this may be unreadable
392 MALLOC_ASSERT(isAligned(object, sizeof(size_t)), "Try to free invalid small object");
393 // releasing to free slab
394 MALLOC_ASSERT(allocatedCount>0, msg);
395 // must not point to slab's header
396 MALLOC_ASSERT((uintptr_t)object - (uintptr_t)this >= sizeof(Block), msg);
397 if (startupAllocObjSizeMark == objectSize) // startup block
398 MALLOC_ASSERT(object<=bumpPtr, msg);
399 else {
400 // non-startup objects are 8 Byte aligned
401 MALLOC_ASSERT(isAligned(object, 8), "Try to free invalid small object");
402 MALLOC_ASSERT(allocatedCount <= (slabSize-sizeof(Block))/objectSize
403 && (!bumpPtr || object>bumpPtr), msg);
404 FreeObject *toFree = findObjectToFree(object);
405 // check against head of freeList, as this is mostly
406 // expected after double free
407 MALLOC_ASSERT(toFree != freeList, msg);
408 // check against head of publicFreeList, to detect double free
409 // involving foreign thread
410 MALLOC_ASSERT(toFree != publicFreeList, msg);
411 }
412#else
413 suppress_unused_warning(object);
414#endif
415 }
416 void initEmptyBlock(TLSData *tls, size_t size);
417 size_t findObjectSize(void *object) const;
418 MemoryPool *getMemPool() const { return poolPtr; } // do not use on the hot path!
419
420protected:
421 void cleanBlockHeader();
422
423private:
424 static const float emptyEnoughRatio; /* Threshold on free space needed to "reactivate" a block */
425
426 inline FreeObject *allocateFromBumpPtr();
427 inline FreeObject *findAllocatedObject(const void *address) const;
428 inline bool isProperlyPlaced(const void *object) const;
429 inline void markOwned(TLSData *tls) {
430 MALLOC_ASSERT(!tlsPtr, ASSERT_TEXT);
431 ownerTid = ThreadId(); /* save the ID of the current thread */
432 tlsPtr = tls;
433 }
434 inline void markOrphaned() {
435 MALLOC_ASSERT(tlsPtr, ASSERT_TEXT);
436 tlsPtr = NULL;
437 }
438
439 friend class Bin;
440 friend class TLSData;
441 friend bool MemoryPool::destroy();
442};
443
444const float Block::emptyEnoughRatio = 1.0 / 4.0;
445
446MALLOC_STATIC_ASSERT(sizeof(Block) <= 2*estimatedCacheLineSize,
447 "The class Block does not fit into 2 cache lines on this platform. "
448 "Defining USE_INTERNAL_TID may help to fix it.");
449
450class Bin {
451private:
452 Block *activeBlk;
453 Block *mailbox;
454 MallocMutex mailLock;
455
456public:
457 inline Block* getActiveBlock() const { return activeBlk; }
458 void resetActiveBlock() { activeBlk = NULL; }
459 bool activeBlockUnused() const { return activeBlk && !activeBlk->allocatedCount; }
460 inline void setActiveBlock(Block *block);
461 inline Block* setPreviousBlockActive();
462 Block* getPrivatizedFreeListBlock();
463 void moveBlockToFront(Block *block);
464 bool cleanPublicFreeLists();
465 void processEmptyBlock(Block *block, bool poolTheBlock);
466 void addPublicFreeListBlock(Block* block);
467
468 void outofTLSBin(Block* block);
469 void verifyTLSBin(size_t size) const;
470 void pushTLSBin(Block* block);
471
472 void verifyInitState() const {
473 MALLOC_ASSERT( !activeBlk, ASSERT_TEXT );
474 MALLOC_ASSERT( !mailbox, ASSERT_TEXT );
475 }
476
477 friend void Block::freePublicObject (FreeObject *objectToFree);
478};
479
480/********* End of the data structures **************/
481
482/*
483 * There are bins for all 8 byte aligned objects less than this segregated size; 8 bins in total
484 */
485const uint32_t minSmallObjectIndex = 0;
486const uint32_t numSmallObjectBins = 8;
487const uint32_t maxSmallObjectSize = 64;
488
489/*
490 * There are 4 bins between each couple of powers of 2 [64-128-256-...]
491 * from maxSmallObjectSize till this size; 16 bins in total
492 */
493const uint32_t minSegregatedObjectIndex = minSmallObjectIndex+numSmallObjectBins;
494const uint32_t numSegregatedObjectBins = 16;
495const uint32_t maxSegregatedObjectSize = 1024;
496
497/*
498 * And there are 5 bins with allocation sizes that are multiples of estimatedCacheLineSize
499 * and selected to fit 9, 6, 4, 3, and 2 allocations in a block.
500 */
501const uint32_t minFittingIndex = minSegregatedObjectIndex+numSegregatedObjectBins;
502const uint32_t numFittingBins = 5;
503
504const uint32_t fittingAlignment = estimatedCacheLineSize;
505
506#define SET_FITTING_SIZE(N) ( (slabSize-sizeof(Block))/N ) & ~(fittingAlignment-1)
507// For blockSize=16*1024, sizeof(Block)=2*estimatedCacheLineSize and fittingAlignment=estimatedCacheLineSize,
508// the comments show the fitting sizes and the amounts left unused for estimatedCacheLineSize=64/128:
509const uint32_t fittingSize1 = SET_FITTING_SIZE(9); // 1792/1792 128/000
510const uint32_t fittingSize2 = SET_FITTING_SIZE(6); // 2688/2688 128/000
511const uint32_t fittingSize3 = SET_FITTING_SIZE(4); // 4032/3968 128/256
512const uint32_t fittingSize4 = SET_FITTING_SIZE(3); // 5376/5376 128/000
513const uint32_t fittingSize5 = SET_FITTING_SIZE(2); // 8128/8064 000/000
514#undef SET_FITTING_SIZE
515
516/*
517 * The total number of thread-specific Block-based bins
518 */
519const uint32_t numBlockBins = minFittingIndex+numFittingBins;
520
521/*
522 * Objects of this size and larger are considered large objects.
523 */
524const uint32_t minLargeObjectSize = fittingSize5 + 1;
525
526/*
527 * Per-thread pool of slab blocks. Idea behind it is to not share with other
528 * threads memory that are likely in local cache(s) of our CPU.
529 */
530class FreeBlockPool {
531private:
532 Block *head;
533 int size;
534 Backend *backend;
535 bool lastAccessMiss;
536public:
537 static const int POOL_HIGH_MARK = 32;
538 static const int POOL_LOW_MARK = 8;
539
540 class ResOfGet {
541 ResOfGet();
542 public:
543 Block* block;
544 bool lastAccMiss;
545 ResOfGet(Block *b, bool lastMiss) : block(b), lastAccMiss(lastMiss) {}
546 };
547
548 // allocated in zero-initialized memory
549 FreeBlockPool(Backend *bknd) : backend(bknd) {}
550 ResOfGet getBlock();
551 void returnBlock(Block *block);
552 bool externalCleanup(); // can be called by another thread
553};
554
555template<int LOW_MARK, int HIGH_MARK>
556class LocalLOCImpl {
557private:
558 static const size_t MAX_TOTAL_SIZE = 4*1024*1024;
559 // TODO: can single-linked list be faster here?
560 LargeMemoryBlock *head,
561 *tail; // need it when do releasing on overflow
562 size_t totalSize;
563 int numOfBlocks;
564public:
565 bool put(LargeMemoryBlock *object, ExtMemoryPool *extMemPool);
566 LargeMemoryBlock *get(size_t size);
567 bool externalCleanup(ExtMemoryPool *extMemPool);
568#if __TBB_MALLOC_WHITEBOX_TEST
569 LocalLOCImpl() : head(NULL), tail(NULL), totalSize(0), numOfBlocks(0) {}
570 static size_t getMaxSize() { return MAX_TOTAL_SIZE; }
571 static const int LOC_HIGH_MARK = HIGH_MARK;
572#else
573 // no ctor, object must be created in zero-initialized memory
574#endif
575};
576
577typedef LocalLOCImpl<8,32> LocalLOC; // set production code parameters
578
579class TLSData : public TLSRemote {
580 MemoryPool *memPool;
581public:
582 Bin bin[numBlockBinLimit];
583 FreeBlockPool freeSlabBlocks;
584 LocalLOC lloc;
585 unsigned currCacheIdx;
586private:
587 bool unused;
588public:
589 TLSData(MemoryPool *mPool, Backend *bknd) : memPool(mPool), freeSlabBlocks(bknd) {}
590 MemoryPool *getMemPool() const { return memPool; }
591 Bin* getAllocationBin(size_t size);
592 void release();
593 bool externalCleanup(bool cleanOnlyUnused, bool cleanBins) {
594 if (!unused && cleanOnlyUnused) return false;
595 // Heavy operation in terms of synchronization complexity,
596 // should be called only for the current thread
597 bool released = cleanBins ? cleanupBlockBins() : false;
598 // both cleanups to be called, and the order is not important
599 return released | lloc.externalCleanup(&memPool->extMemPool) | freeSlabBlocks.externalCleanup();
600 }
601 bool cleanupBlockBins();
602 void markUsed() { unused = false; } // called by owner when TLS touched
603 void markUnused() { unused = true; } // can be called by not owner thread
604};
605
606TLSData *TLSKey::createTLS(MemoryPool *memPool, Backend *backend)
607{
608 MALLOC_ASSERT( sizeof(TLSData) >= sizeof(Bin) * numBlockBins + sizeof(FreeBlockPool), ASSERT_TEXT );
609 TLSData* tls = (TLSData*) memPool->bootStrapBlocks.allocate(memPool, sizeof(TLSData));
610 if ( !tls )
611 return NULL;
612 new(tls) TLSData(memPool, backend);
613 /* the block contains zeroes after bootStrapMalloc, so bins are initialized */
614#if MALLOC_DEBUG
615 for (uint32_t i = 0; i < numBlockBinLimit; i++)
616 tls->bin[i].verifyInitState();
617#endif
618 setThreadMallocTLS(tls);
619 memPool->extMemPool.allLocalCaches.registerThread(tls);
620 return tls;
621}
622
623bool TLSData::cleanupBlockBins()
624{
625 bool released = false;
626 for (uint32_t i = 0; i < numBlockBinLimit; i++) {
627 released |= bin[i].cleanPublicFreeLists();
628 // After cleaning public free lists, only the active block might be empty.
629 // Do not use processEmptyBlock because it will just restore bumpPtr.
630 Block *block = bin[i].getActiveBlock();
631 if (block && block->empty()) {
632 bin[i].outofTLSBin(block);
633 memPool->returnEmptyBlock(block, /*poolTheBlock=*/false);
634 released = true;
635 }
636 }
637 return released;
638}
639
640bool ExtMemoryPool::releaseAllLocalCaches()
641{
642 // Iterate all registered TLS data and clean LLOC and Slab pools
643 bool released = allLocalCaches.cleanup(/*cleanOnlyUnused=*/false);
644
645 // Bins privatization is done only for the current thread
646 if (TLSData *tlsData = tlsPointerKey.getThreadMallocTLS())
647 released |= tlsData->cleanupBlockBins();
648
649 return released;
650}
651
652void AllLocalCaches::registerThread(TLSRemote *tls)
653{
654 tls->prev = NULL;
655 MallocMutex::scoped_lock lock(listLock);
656 MALLOC_ASSERT(head!=tls, ASSERT_TEXT);
657 tls->next = head;
658 if (head)
659 head->prev = tls;
660 head = tls;
661 MALLOC_ASSERT(head->next!=head, ASSERT_TEXT);
662}
663
664void AllLocalCaches::unregisterThread(TLSRemote *tls)
665{
666 MallocMutex::scoped_lock lock(listLock);
667 MALLOC_ASSERT(head, "Can't unregister thread: no threads are registered.");
668 if (head == tls)
669 head = tls->next;
670 if (tls->next)
671 tls->next->prev = tls->prev;
672 if (tls->prev)
673 tls->prev->next = tls->next;
674 MALLOC_ASSERT(!tls->next || tls->next->next!=tls->next, ASSERT_TEXT);
675}
676
677bool AllLocalCaches::cleanup(bool cleanOnlyUnused)
678{
679 bool released = false;
680 {
681 MallocMutex::scoped_lock lock(listLock);
682 for (TLSRemote *curr=head; curr; curr=curr->next)
683 released |= static_cast<TLSData*>(curr)->externalCleanup(cleanOnlyUnused, /*cleanBins=*/false);
684 }
685 return released;
686}
687
688void AllLocalCaches::markUnused()
689{
690 bool locked;
691 MallocMutex::scoped_lock lock(listLock, /*block=*/false, &locked);
692 if (!locked) // not wait for marking if someone doing something with it
693 return;
694
695 for (TLSRemote *curr=head; curr; curr=curr->next)
696 static_cast<TLSData*>(curr)->markUnused();
697}
698
699#if MALLOC_CHECK_RECURSION
700MallocMutex RecursiveMallocCallProtector::rmc_mutex;
701pthread_t RecursiveMallocCallProtector::owner_thread;
702void *RecursiveMallocCallProtector::autoObjPtr;
703bool RecursiveMallocCallProtector::mallocRecursionDetected;
704#if __FreeBSD__
705bool RecursiveMallocCallProtector::canUsePthread;
706#endif
707
708#endif
709
710/*********** End code to provide thread ID and a TLS pointer **********/
711
712// Parameter for isLargeObject, keeps our expectations on memory origin.
713// Assertions must use unknownMem to reliably report object invalidity.
714enum MemoryOrigin {
715 ourMem, // allocated by TBB allocator
716 unknownMem // can be allocated by system allocator or TBB allocator
717};
718
719template<MemoryOrigin> bool isLargeObject(void *object);
720static void *internalMalloc(size_t size);
721static void internalFree(void *object);
722static void *internalPoolMalloc(MemoryPool* mPool, size_t size);
723static bool internalPoolFree(MemoryPool *mPool, void *object, size_t size);
724
725#if !MALLOC_DEBUG
726#if __INTEL_COMPILER || _MSC_VER
727#define NOINLINE(decl) __declspec(noinline) decl
728#define ALWAYSINLINE(decl) __forceinline decl
729#elif __GNUC__
730#define NOINLINE(decl) decl __attribute__ ((noinline))
731#define ALWAYSINLINE(decl) decl __attribute__ ((always_inline))
732#else
733#define NOINLINE(decl) decl
734#define ALWAYSINLINE(decl) decl
735#endif
736
737static NOINLINE( bool doInitialization() );
738ALWAYSINLINE( bool isMallocInitialized() );
739
740#undef ALWAYSINLINE
741#undef NOINLINE
742#endif /* !MALLOC_DEBUG */
743
744
745/********* Now some rough utility code to deal with indexing the size bins. **************/
746
747/*
748 * Given a number return the highest non-zero bit in it. It is intended to work with 32-bit values only.
749 * Moreover, on IPF, for sake of simplicity and performance, it is narrowed to only serve for 64 to 1023.
750 * This is enough for current algorithm of distribution of sizes among bins.
751 * __TBB_Log2 is not used here to minimize dependencies on TBB specific sources.
752 */
753#if _WIN64 && _MSC_VER>=1400 && !__INTEL_COMPILER
754extern "C" unsigned char _BitScanReverse( unsigned long* i, unsigned long w );
755#pragma intrinsic(_BitScanReverse)
756#endif
757static inline unsigned int highestBitPos(unsigned int n)
758{
759 MALLOC_ASSERT( n>=64 && n<1024, ASSERT_TEXT ); // only needed for bsr array lookup, but always true
760 unsigned int pos;
761#if __ARCH_x86_32||__ARCH_x86_64
762
763# if __linux__||__APPLE__||__FreeBSD__||__NetBSD__||__OpenBSD__||__sun||__MINGW32__
764 __asm__ ("bsr %1,%0" : "=r"(pos) : "r"(n));
765# elif (_WIN32 && (!_WIN64 || __INTEL_COMPILER))
766 __asm
767 {
768 bsr eax, n
769 mov pos, eax
770 }
771# elif _WIN64 && _MSC_VER>=1400
772 _BitScanReverse((unsigned long*)&pos, (unsigned long)n);
773# else
774# error highestBitPos() not implemented for this platform
775# endif
776#elif __arm__
777 __asm__ __volatile__
778 (
779 "clz %0, %1\n"
780 "rsb %0, %0, %2\n"
781 :"=r" (pos) :"r" (n), "I" (31)
782 );
783#else
784 static unsigned int bsr[16] = {0/*N/A*/,6,7,7,8,8,8,8,9,9,9,9,9,9,9,9};
785 pos = bsr[ n>>6 ];
786#endif /* __ARCH_* */
787 return pos;
788}
789
790template<bool Is32Bit>
791unsigned int getSmallObjectIndex(unsigned int size)
792{
793 return (size-1)>>3;
794}
795template<>
796unsigned int getSmallObjectIndex</*Is32Bit=*/false>(unsigned int size)
797{
798 // For 64-bit malloc, 16 byte alignment is needed except for bin 0.
799 unsigned int result = (size-1)>>3;
800 if (result) result |= 1; // 0,1,3,5,7; bins 2,4,6 are not aligned to 16 bytes
801 return result;
802}
803/*
804 * Depending on indexRequest, for a given size return either the index into the bin
805 * for objects of this size, or the actual size of objects in this bin.
806 */
807template<bool indexRequest>
808static unsigned int getIndexOrObjectSize (unsigned int size)
809{
810 if (size <= maxSmallObjectSize) { // selection from 8/16/24/32/40/48/56/64
811 unsigned int index = getSmallObjectIndex</*Is32Bit=*/(sizeof(size_t)<=4)>( size );
812 /* Bin 0 is for 8 bytes, bin 1 is for 16, and so forth */
813 return indexRequest ? index : (index+1)<<3;
814 }
815 else if (size <= maxSegregatedObjectSize ) { // 80/96/112/128 / 160/192/224/256 / 320/384/448/512 / 640/768/896/1024
816 unsigned int order = highestBitPos(size-1); // which group of bin sizes?
817 MALLOC_ASSERT( 6<=order && order<=9, ASSERT_TEXT );
818 if (indexRequest)
819 return minSegregatedObjectIndex - (4*6) - 4 + (4*order) + ((size-1)>>(order-2));
820 else {
821 unsigned int alignment = 128 >> (9-order); // alignment in the group
822 MALLOC_ASSERT( alignment==16 || alignment==32 || alignment==64 || alignment==128, ASSERT_TEXT );
823 return alignUp(size,alignment);
824 }
825 }
826 else {
827 if( size <= fittingSize3 ) {
828 if( size <= fittingSize2 ) {
829 if( size <= fittingSize1 )
830 return indexRequest ? minFittingIndex : fittingSize1;
831 else
832 return indexRequest ? minFittingIndex+1 : fittingSize2;
833 } else
834 return indexRequest ? minFittingIndex+2 : fittingSize3;
835 } else {
836 if( size <= fittingSize5 ) {
837 if( size <= fittingSize4 )
838 return indexRequest ? minFittingIndex+3 : fittingSize4;
839 else
840 return indexRequest ? minFittingIndex+4 : fittingSize5;
841 } else {
842 MALLOC_ASSERT( 0,ASSERT_TEXT ); // this should not happen
843 return ~0U;
844 }
845 }
846 }
847}
848
849static unsigned int getIndex (unsigned int size)
850{
851 return getIndexOrObjectSize</*indexRequest=*/true>(size);
852}
853
854static unsigned int getObjectSize (unsigned int size)
855{
856 return getIndexOrObjectSize</*indexRequest=*/false>(size);
857}
858
859
860void *BootStrapBlocks::allocate(MemoryPool *memPool, size_t size)
861{
862 FreeObject *result;
863
864 MALLOC_ASSERT( size == sizeof(TLSData), ASSERT_TEXT );
865
866 { // Lock with acquire
867 MallocMutex::scoped_lock scoped_cs(bootStrapLock);
868
869 if( bootStrapObjectList) {
870 result = bootStrapObjectList;
871 bootStrapObjectList = bootStrapObjectList->next;
872 } else {
873 if (!bootStrapBlock) {
874 bootStrapBlock = memPool->getEmptyBlock(size);
875 if (!bootStrapBlock) return NULL;
876 }
877 result = bootStrapBlock->bumpPtr;
878 bootStrapBlock->bumpPtr = (FreeObject *)((uintptr_t)bootStrapBlock->bumpPtr - bootStrapBlock->objectSize);
879 if ((uintptr_t)bootStrapBlock->bumpPtr < (uintptr_t)bootStrapBlock+sizeof(Block)) {
880 bootStrapBlock->bumpPtr = NULL;
881 bootStrapBlock->next = bootStrapBlockUsed;
882 bootStrapBlockUsed = bootStrapBlock;
883 bootStrapBlock = NULL;
884 }
885 }
886 } // Unlock with release
887
888 memset (result, 0, size);
889 return (void*)result;
890}
891
892void BootStrapBlocks::free(void* ptr)
893{
894 MALLOC_ASSERT( ptr, ASSERT_TEXT );
895 { // Lock with acquire
896 MallocMutex::scoped_lock scoped_cs(bootStrapLock);
897 ((FreeObject*)ptr)->next = bootStrapObjectList;
898 bootStrapObjectList = (FreeObject*)ptr;
899 } // Unlock with release
900}
901
902void BootStrapBlocks::reset()
903{
904 bootStrapBlock = bootStrapBlockUsed = NULL;
905 bootStrapObjectList = NULL;
906}
907
908#if !(FREELIST_NONBLOCKING)
909static MallocMutex publicFreeListLock; // lock for changes of publicFreeList
910#endif
911
912/********* End rough utility code **************/
913
914/* LifoList assumes zero initialization so a vector of it can be created
915 * by just allocating some space with no call to constructor.
916 * On Linux, it seems to be necessary to avoid linking with C++ libraries.
917 *
918 * By usage convention there is no race on the initialization. */
919LifoList::LifoList( ) : top(NULL)
920{
921 // MallocMutex assumes zero initialization
922 memset(&lock, 0, sizeof(MallocMutex));
923}
924
925void LifoList::push(Block *block)
926{
927 MallocMutex::scoped_lock scoped_cs(lock);
928 block->next = top;
929 top = block;
930}
931
932Block *LifoList::pop()
933{
934 Block *block=NULL;
935 if (top) {
936 MallocMutex::scoped_lock scoped_cs(lock);
937 if (top) {
938 block = top;
939 top = block->next;
940 }
941 }
942 return block;
943}
944
945Block *LifoList::grab()
946{
947 Block *block = NULL;
948 if (top) {
949 MallocMutex::scoped_lock scoped_cs(lock);
950 block = top;
951 top = NULL;
952 }
953 return block;
954}
955
956/********* Thread and block related code *************/
957
958template<bool poolDestroy> void AllLargeBlocksList::releaseAll(Backend *backend) {
959 LargeMemoryBlock *next, *lmb = loHead;
960 loHead = NULL;
961
962 for (; lmb; lmb = next) {
963 next = lmb->gNext;
964 if (poolDestroy) {
965 // as it's pool destruction, no need to return object to backend,
966 // only remove backrefs, as they are global
967 removeBackRef(lmb->backRefIdx);
968 } else {
969 // clean g(Next|Prev) to prevent removing lmb
970 // from AllLargeBlocksList inside returnLargeObject
971 lmb->gNext = lmb->gPrev = NULL;
972 backend->returnLargeObject(lmb);
973 }
974 }
975}
976
977TLSData* MemoryPool::getTLS(bool create)
978{
979 TLSData* tls = extMemPool.tlsPointerKey.getThreadMallocTLS();
980 if (create && !tls)
981 tls = extMemPool.tlsPointerKey.createTLS(this, &extMemPool.backend);
982 return tls;
983}
984
985/*
986 * Return the bin for the given size.
987 */
988inline Bin* TLSData::getAllocationBin(size_t size)
989{
990 return bin + getIndex(size);
991}
992
993/* Return an empty uninitialized block in a non-blocking fashion. */
994Block *MemoryPool::getEmptyBlock(size_t size)
995{
996 TLSData* tls = getTLS(/*create=*/false);
997 // try to use per-thread cache, if TLS available
998 FreeBlockPool::ResOfGet resOfGet = tls?
999 tls->freeSlabBlocks.getBlock() : FreeBlockPool::ResOfGet(NULL, false);
1000 Block *result = resOfGet.block;
1001
1002 if (!result) { // not found in local cache, asks backend for slabs
1003 int num = resOfGet.lastAccMiss? Backend::numOfSlabAllocOnMiss : 1;
1004 BackRefIdx backRefIdx[Backend::numOfSlabAllocOnMiss];
1005
1006 result = static_cast<Block*>(extMemPool.backend.getSlabBlock(num));
1007 if (!result) return NULL;
1008
1009 if (!extMemPool.userPool())
1010 for (int i=0; i<num; i++) {
1011 backRefIdx[i] = BackRefIdx::newBackRef(/*largeObj=*/false);
1012 if (backRefIdx[i].isInvalid()) {
1013 // roll back resource allocation
1014 for (int j=0; j<i; j++)
1015 removeBackRef(backRefIdx[j]);
1016 Block *b = result;
1017 for (int j=0; j<num; b=(Block*)((uintptr_t)b+slabSize), j++)
1018 extMemPool.backend.putSlabBlock(b);
1019 return NULL;
1020 }
1021 }
1022 // resources were allocated, register blocks
1023 Block *b = result;
1024 for (int i=0; i<num; b=(Block*)((uintptr_t)b+slabSize), i++) {
1025 // slab block in user's pool must have invalid backRefIdx
1026 if (extMemPool.userPool()) {
1027 new (&b->backRefIdx) BackRefIdx();
1028 } else {
1029 setBackRef(backRefIdx[i], b);
1030 b->backRefIdx = backRefIdx[i];
1031 }
1032 b->tlsPtr = tls;
1033 b->poolPtr = this;
1034 // all but first one go to per-thread pool
1035 if (i > 0) {
1036 MALLOC_ASSERT(tls, ASSERT_TEXT);
1037 tls->freeSlabBlocks.returnBlock(b);
1038 }
1039 }
1040 }
1041 MALLOC_ASSERT(result, ASSERT_TEXT);
1042 result->initEmptyBlock(tls, size);
1043 STAT_increment(getThreadId(), getIndex(result->objectSize), allocBlockNew);
1044 return result;
1045}
1046
1047void MemoryPool::returnEmptyBlock(Block *block, bool poolTheBlock)
1048{
1049 block->reset();
1050 if (poolTheBlock) {
1051 getTLS(/*create=*/false)->freeSlabBlocks.returnBlock(block);
1052 } else {
1053 // slab blocks in user's pools do not have valid backRefIdx
1054 if (!extMemPool.userPool())
1055 removeBackRef(*(block->getBackRefIdx()));
1056 extMemPool.backend.putSlabBlock(block);
1057 }
1058}
1059
1060bool ExtMemoryPool::init(intptr_t poolId, rawAllocType rawAlloc,
1061 rawFreeType rawFree, size_t granularity,
1062 bool keepAllMemory, bool fixedPool)
1063{
1064 this->poolId = poolId;
1065 this->rawAlloc = rawAlloc;
1066 this->rawFree = rawFree;
1067 this->granularity = granularity;
1068 this->keepAllMemory = keepAllMemory;
1069 this->fixedPool = fixedPool;
1070 this->delayRegsReleasing = false;
1071 if (!initTLS())
1072 return false;
1073 loc.init(this);
1074 backend.init(this);
1075 MALLOC_ASSERT(isPoolValid(), NULL);
1076 return true;
1077}
1078
1079bool ExtMemoryPool::initTLS() { return tlsPointerKey.init(); }
1080
1081bool MemoryPool::init(intptr_t poolId, const MemPoolPolicy *policy)
1082{
1083 if (!extMemPool.init(poolId, policy->pAlloc, policy->pFree,
1084 policy->granularity? policy->granularity : defaultGranularity,
1085 policy->keepAllMemory, policy->fixedPool))
1086 return false;
1087 {
1088 MallocMutex::scoped_lock lock(memPoolListLock);
1089 next = defaultMemPool->next;
1090 defaultMemPool->next = this;
1091 prev = defaultMemPool;
1092 if (next)
1093 next->prev = this;
1094 }
1095 return true;
1096}
1097
1098bool MemoryPool::reset()
1099{
1100 MALLOC_ASSERT(extMemPool.userPool(), "No reset for the system pool.");
1101 // memory is not releasing during pool reset
1102 // TODO: mark regions to release unused on next reset()
1103 extMemPool.delayRegionsReleasing(true);
1104
1105 bootStrapBlocks.reset();
1106 extMemPool.lmbList.releaseAll</*poolDestroy=*/false>(&extMemPool.backend);
1107 if (!extMemPool.reset())
1108 return false;
1109
1110 if (!extMemPool.initTLS())
1111 return false;
1112 extMemPool.delayRegionsReleasing(false);
1113 return true;
1114}
1115
1116bool MemoryPool::destroy()
1117{
1118#if __TBB_MALLOC_LOCACHE_STAT
1119 extMemPool.loc.reportStat(stdout);
1120#endif
1121#if __TBB_MALLOC_BACKEND_STAT
1122 extMemPool.backend.reportStat(stdout);
1123#endif
1124 {
1125 MallocMutex::scoped_lock lock(memPoolListLock);
1126 // remove itself from global pool list
1127 if (prev)
1128 prev->next = next;
1129 if (next)
1130 next->prev = prev;
1131 }
1132 // slab blocks in non-default pool do not have backreferences,
1133 // only large objects do
1134 if (extMemPool.userPool())
1135 extMemPool.lmbList.releaseAll</*poolDestroy=*/true>(&extMemPool.backend);
1136 else {
1137 // only one non-userPool() is supported now
1138 MALLOC_ASSERT(this==defaultMemPool, NULL);
1139 // There and below in extMemPool.destroy(), do not restore initial state
1140 // for user pool, because it's just about to be released. But for system
1141 // pool restoring, we do not want to do zeroing of it on subsequent reload.
1142 bootStrapBlocks.reset();
1143 extMemPool.orphanedBlocks.reset();
1144 }
1145 return extMemPool.destroy();
1146}
1147
1148void MemoryPool::onThreadShutdown(TLSData *tlsData)
1149{
1150 if (tlsData) { // might be called for "empty" TLS
1151 tlsData->release();
1152 bootStrapBlocks.free(tlsData);
1153 clearTLS();
1154 }
1155}
1156
1157#if MALLOC_DEBUG
1158void Bin::verifyTLSBin (size_t size) const
1159{
1160/* The debug version verifies the TLSBin as needed */
1161 uint32_t objSize = getObjectSize(size);
1162
1163 if (activeBlk) {
1164 MALLOC_ASSERT( activeBlk->isOwnedByCurrentThread(), ASSERT_TEXT );
1165 MALLOC_ASSERT( activeBlk->objectSize == objSize, ASSERT_TEXT );
1166#if MALLOC_DEBUG>1
1167 for (Block* temp = activeBlk->next; temp; temp=temp->next) {
1168 MALLOC_ASSERT( temp!=activeBlk, ASSERT_TEXT );
1169 MALLOC_ASSERT( temp->isOwnedByCurrentThread(), ASSERT_TEXT );
1170 MALLOC_ASSERT( temp->objectSize == objSize, ASSERT_TEXT );
1171 MALLOC_ASSERT( temp->previous->next == temp, ASSERT_TEXT );
1172 if (temp->next) {
1173 MALLOC_ASSERT( temp->next->previous == temp, ASSERT_TEXT );
1174 }
1175 }
1176 for (Block* temp = activeBlk->previous; temp; temp=temp->previous) {
1177 MALLOC_ASSERT( temp!=activeBlk, ASSERT_TEXT );
1178 MALLOC_ASSERT( temp->isOwnedByCurrentThread(), ASSERT_TEXT );
1179 MALLOC_ASSERT( temp->objectSize == objSize, ASSERT_TEXT );
1180 MALLOC_ASSERT( temp->next->previous == temp, ASSERT_TEXT );
1181 if (temp->previous) {
1182 MALLOC_ASSERT( temp->previous->next == temp, ASSERT_TEXT );
1183 }
1184 }
1185#endif /* MALLOC_DEBUG>1 */
1186 }
1187}
1188#else /* MALLOC_DEBUG */
1189inline void Bin::verifyTLSBin (size_t) const { }
1190#endif /* MALLOC_DEBUG */
1191
1192/*
1193 * Add a block to the start of this tls bin list.
1194 */
1195void Bin::pushTLSBin(Block* block)
1196{
1197 /* The objectSize should be defined and not a parameter
1198 because the function is applied to partially filled blocks as well */
1199 unsigned int size = block->objectSize;
1200
1201 MALLOC_ASSERT( block->isOwnedByCurrentThread(), ASSERT_TEXT );
1202 MALLOC_ASSERT( block->objectSize != 0, ASSERT_TEXT );
1203 MALLOC_ASSERT( block->next == NULL, ASSERT_TEXT );
1204 MALLOC_ASSERT( block->previous == NULL, ASSERT_TEXT );
1205
1206 MALLOC_ASSERT( this, ASSERT_TEXT );
1207 verifyTLSBin(size);
1208
1209 block->next = activeBlk;
1210 if( activeBlk ) {
1211 block->previous = activeBlk->previous;
1212 activeBlk->previous = block;
1213 if( block->previous )
1214 block->previous->next = block;
1215 } else {
1216 activeBlk = block;
1217 }
1218
1219 verifyTLSBin(size);
1220}
1221
1222/*
1223 * Take a block out of its tls bin (e.g. before removal).
1224 */
1225void Bin::outofTLSBin(Block* block)
1226{
1227 unsigned int size = block->objectSize;
1228
1229 MALLOC_ASSERT( block->isOwnedByCurrentThread(), ASSERT_TEXT );
1230 MALLOC_ASSERT( block->objectSize != 0, ASSERT_TEXT );
1231
1232 MALLOC_ASSERT( this, ASSERT_TEXT );
1233 verifyTLSBin(size);
1234
1235 if (block == activeBlk) {
1236 activeBlk = block->previous? block->previous : block->next;
1237 }
1238 /* Unlink the block */
1239 if (block->previous) {
1240 MALLOC_ASSERT( block->previous->next == block, ASSERT_TEXT );
1241 block->previous->next = block->next;
1242 }
1243 if (block->next) {
1244 MALLOC_ASSERT( block->next->previous == block, ASSERT_TEXT );
1245 block->next->previous = block->previous;
1246 }
1247 block->next = NULL;
1248 block->previous = NULL;
1249
1250 verifyTLSBin(size);
1251}
1252
1253Block* Bin::getPrivatizedFreeListBlock()
1254{
1255 Block* block;
1256 MALLOC_ASSERT( this, ASSERT_TEXT );
1257 // if this method is called, active block usage must be unsuccessful
1258 MALLOC_ASSERT( !activeBlk && !mailbox || activeBlk && activeBlk->isFull, ASSERT_TEXT );
1259
1260// the counter should be changed STAT_increment(getThreadId(), ThreadCommonCounters, lockPublicFreeList);
1261 if (!FencedLoad((intptr_t&)mailbox)) // hotpath is empty mailbox
1262 return NULL;
1263 else { // mailbox is not empty, take lock and inspect it
1264 MallocMutex::scoped_lock scoped_cs(mailLock);
1265 block = mailbox;
1266 if( block ) {
1267 MALLOC_ASSERT( block->isOwnedByCurrentThread(), ASSERT_TEXT );
1268 MALLOC_ASSERT( !isNotForUse(block->nextPrivatizable), ASSERT_TEXT );
1269 mailbox = block->nextPrivatizable;
1270 block->nextPrivatizable = (Block*) this;
1271 }
1272 }
1273 if( block ) {
1274 MALLOC_ASSERT( isSolidPtr(block->publicFreeList), ASSERT_TEXT );
1275 block->privatizePublicFreeList();
1276 block->adjustPositionInBin(this);
1277 }
1278 return block;
1279}
1280
1281void Bin::addPublicFreeListBlock(Block* block)
1282{
1283 MallocMutex::scoped_lock scoped_cs(mailLock);
1284 block->nextPrivatizable = mailbox;
1285 mailbox = block;
1286}
1287
1288// Process publicly freed objects in all blocks and return empty blocks
1289// to the backend in order to reduce overall footprint.
1290bool Bin::cleanPublicFreeLists()
1291{
1292 Block* block;
1293 if (!FencedLoad((intptr_t&)mailbox))
1294 return false;
1295 else {
1296 // Grab all the blocks in the mailbox
1297 MallocMutex::scoped_lock scoped_cs(mailLock);
1298 block = mailbox;
1299 mailbox = NULL;
1300 }
1301 bool released = false;
1302 while (block) {
1303 MALLOC_ASSERT( block->isOwnedByCurrentThread(), ASSERT_TEXT );
1304 Block* tmp = block->nextPrivatizable;
1305 block->nextPrivatizable = (Block*) this;
1306 block->privatizePublicFreeList();
1307 if (block->empty()) {
1308 processEmptyBlock(block, /*poolTheBlock=*/false);
1309 released = true;
1310 } else
1311 block->adjustPositionInBin(this);
1312 block = tmp;
1313 }
1314 return released;
1315}
1316
1317bool Block::adjustFullness()
1318{
1319 if (bumpPtr) {
1320 /* If we are still using a bump ptr for this block it is empty enough to use. */
1321 STAT_increment(getThreadId(), getIndex(objectSize), examineEmptyEnough);
1322 isFull = false;
1323 } else {
1324 const float threshold = (slabSize - sizeof(Block)) * (1 - emptyEnoughRatio);
1325 /* allocatedCount shows how many objects in the block are in use; however it still counts
1326 * blocks freed by other threads; so prior call to privatizePublicFreeList() is recommended */
1327 isFull = (allocatedCount*objectSize > threshold) ? true : false;
1328#if COLLECT_STATISTICS
1329 if (isFull)
1330 STAT_increment(getThreadId(), getIndex(objectSize), examineNotEmpty);
1331 else
1332 STAT_increment(getThreadId(), getIndex(objectSize), examineEmptyEnough);
1333#endif
1334 }
1335 return isFull;
1336}
1337
1338// This method resides in class Block, and not in class Bin, in order to avoid
1339// calling getAllocationBin on a reasonably hot path in Block::freeOwnObject
1340void Block::adjustPositionInBin(Bin* bin/*=NULL*/)
1341{
1342 // If the block were full, but became empty enough to use,
1343 // move it to the front of the list
1344 if (isFull && !adjustFullness()) {
1345 if (!bin)
1346 bin = tlsPtr->getAllocationBin(objectSize);
1347 bin->moveBlockToFront(this);
1348 }
1349}
1350
1351/* Restore the bump pointer for an empty block that is planned to use */
1352void Block::restoreBumpPtr()
1353{
1354 MALLOC_ASSERT( allocatedCount == 0, ASSERT_TEXT );
1355 MALLOC_ASSERT( !isSolidPtr(publicFreeList), ASSERT_TEXT );
1356 STAT_increment(getThreadId(), getIndex(objectSize), freeRestoreBumpPtr);
1357 bumpPtr = (FreeObject *)((uintptr_t)this + slabSize - objectSize);
1358 freeList = NULL;
1359 isFull = false;
1360}
1361
1362void Block::freeOwnObject(void *object)
1363{
1364 tlsPtr->markUsed();
1365 allocatedCount--;
1366 MALLOC_ASSERT( allocatedCount < (slabSize-sizeof(Block))/objectSize, ASSERT_TEXT );
1367#if COLLECT_STATISTICS
1368 // Note that getAllocationBin is not called on the hottest path with statistics off.
1369 if (tlsPtr->getAllocationBin(objectSize)->getActiveBlock() != this)
1370 STAT_increment(getThreadId(), getIndex(objectSize), freeToInactiveBlock);
1371 else
1372 STAT_increment(getThreadId(), getIndex(objectSize), freeToActiveBlock);
1373#endif
1374 if (empty()) {
1375 // If the last object of a slab is freed, the slab cannot be marked full
1376 MALLOC_ASSERT(!isFull, ASSERT_TEXT);
1377 tlsPtr->getAllocationBin(objectSize)->processEmptyBlock(this, /*poolTheBlock=*/true);
1378 } else { // hot path
1379 FreeObject *objectToFree = findObjectToFree(object);
1380 objectToFree->next = freeList;
1381 freeList = objectToFree;
1382 adjustPositionInBin();
1383 }
1384}
1385
1386void Block::freePublicObject (FreeObject *objectToFree)
1387{
1388 FreeObject *localPublicFreeList;
1389
1390 MALLOC_ITT_SYNC_RELEASING(&publicFreeList);
1391#if FREELIST_NONBLOCKING
1392 FreeObject *temp = publicFreeList;
1393 do {
1394 localPublicFreeList = objectToFree->next = temp;
1395 temp = (FreeObject*)AtomicCompareExchange(
1396 (intptr_t&)publicFreeList,
1397 (intptr_t)objectToFree, (intptr_t)localPublicFreeList );
1398 // no backoff necessary because trying to make change, not waiting for a change
1399 } while( temp != localPublicFreeList );
1400#else
1401 STAT_increment(getThreadId(), ThreadCommonCounters, lockPublicFreeList);
1402 {
1403 MallocMutex::scoped_lock scoped_cs(publicFreeListLock);
1404 localPublicFreeList = objectToFree->next = publicFreeList;
1405 publicFreeList = objectToFree;
1406 }
1407#endif
1408
1409 if( localPublicFreeList==NULL ) {
1410 // if the block is abandoned, its nextPrivatizable pointer should be UNUSABLE
1411 // otherwise, it should point to the bin the block belongs to.
1412 // reading nextPrivatizable is thread-safe below, because:
1413 // 1) the executing thread atomically got publicFreeList==NULL and changed it to non-NULL;
1414 // 2) only owning thread can change it back to NULL,
1415 // 3) but it can not be done until the block is put to the mailbox
1416 // So the executing thread is now the only one that can change nextPrivatizable
1417 if( !isNotForUse(nextPrivatizable) ) {
1418 MALLOC_ASSERT( nextPrivatizable!=NULL, ASSERT_TEXT );
1419 Bin* theBin = (Bin*) nextPrivatizable;
1420 theBin->addPublicFreeListBlock(this);
1421 }
1422 }
1423 STAT_increment(getThreadId(), ThreadCommonCounters, freeToOtherThread);
1424 STAT_increment(ownerTid, getIndex(objectSize), freeByOtherThread);
1425}
1426
1427// Make objects freed by other threads available for use again
1428void Block::privatizePublicFreeList( bool reset )
1429{
1430 FreeObject *localPublicFreeList;
1431 // If reset is false, publicFreeList should not be zeroed but set to UNUSABLE
1432 // to properly synchronize with other threads freeing objects to this slab.
1433 const intptr_t endMarker = reset ? 0 : UNUSABLE;
1434
1435 // Only the owner thread may reset the pointer to NULL
1436 MALLOC_ASSERT( isOwnedByCurrentThread() || !reset, ASSERT_TEXT );
1437#if FREELIST_NONBLOCKING
1438 localPublicFreeList = (FreeObject*)AtomicFetchStore( &publicFreeList, endMarker );
1439#else
1440 STAT_increment(getThreadId(), ThreadCommonCounters, lockPublicFreeList);
1441 {
1442 MallocMutex::scoped_lock scoped_cs(publicFreeListLock);
1443 localPublicFreeList = publicFreeList;
1444 publicFreeList = endMarker;
1445 }
1446#endif
1447 MALLOC_ITT_SYNC_ACQUIRED(&publicFreeList);
1448 MALLOC_ASSERT( !(reset && isNotForUse(publicFreeList)), ASSERT_TEXT );
1449
1450 // publicFreeList must have been UNUSABLE or valid, but not NULL
1451 MALLOC_ASSERT( localPublicFreeList!=NULL, ASSERT_TEXT );
1452 if( isSolidPtr(localPublicFreeList) ) {
1453 MALLOC_ASSERT( allocatedCount <= (slabSize-sizeof(Block))/objectSize, ASSERT_TEXT );
1454 /* other threads did not change the counter freeing our blocks */
1455 allocatedCount--;
1456 FreeObject *temp = localPublicFreeList;
1457 while( isSolidPtr(temp->next) ){ // the list will end with either NULL or UNUSABLE
1458 temp = temp->next;
1459 allocatedCount--;
1460 MALLOC_ASSERT( allocatedCount < (slabSize-sizeof(Block))/objectSize, ASSERT_TEXT );
1461 }
1462 /* merge with local freeList */
1463 temp->next = freeList;
1464 freeList = localPublicFreeList;
1465 STAT_increment(getThreadId(), getIndex(objectSize), allocPrivatized);
1466 }
1467}
1468
1469void Block::privatizeOrphaned(TLSData *tls, unsigned index)
1470{
1471 Bin* bin = tls->bin + index;
1472 STAT_increment(getThreadId(), index, allocBlockPublic);
1473 next = NULL;
1474 previous = NULL;
1475 MALLOC_ASSERT( publicFreeList!=NULL, ASSERT_TEXT );
1476 /* There is not a race here since no other thread owns this block */
1477 markOwned(tls);
1478 // It is safe to change nextPrivatizable, as publicFreeList is not null
1479 MALLOC_ASSERT( isNotForUse(nextPrivatizable), ASSERT_TEXT );
1480 nextPrivatizable = (Block*)bin;
1481 // the next call is required to change publicFreeList to 0
1482 privatizePublicFreeList();
1483 if( empty() ) {
1484 restoreBumpPtr();
1485 } else {
1486 adjustFullness(); // check the block fullness and set isFull
1487 }
1488 MALLOC_ASSERT( !isNotForUse(publicFreeList), ASSERT_TEXT );
1489}
1490
1491
1492bool Block::readyToShare()
1493{
1494 void* oldval;
1495#if FREELIST_NONBLOCKING
1496 oldval = (void*)AtomicCompareExchange((intptr_t&)publicFreeList, UNUSABLE, 0);
1497#else
1498 STAT_increment(getThreadId(), ThreadCommonCounters, lockPublicFreeList);
1499 {
1500 MallocMutex::scoped_lock scoped_cs(publicFreeListLock);
1501 if ( (oldval=publicFreeList)==NULL )
1502 (intptr_t&)(publicFreeList) = UNUSABLE;
1503 }
1504#endif
1505 return oldval==NULL;
1506}
1507
1508void Block::shareOrphaned(intptr_t binTag, unsigned index)
1509{
1510 MALLOC_ASSERT( binTag, ASSERT_TEXT );
1511 STAT_increment(getThreadId(), index, freeBlockPublic);
1512 markOrphaned();
1513 if ((intptr_t)nextPrivatizable==binTag) {
1514 // First check passed: the block is not in mailbox yet.
1515 // Need to set publicFreeList to non-zero, so other threads
1516 // will not change nextPrivatizable and it can be zeroed.
1517 if ( !readyToShare() ) {
1518 // another thread freed an object; we need to wait until it finishes.
1519 // There is no need for exponential backoff, as the wait here is not for a lock;
1520 // but need to yield, so the thread we wait has a chance to run.
1521 // TODO: add a pause to also be friendly to hyperthreads
1522 int count = 256;
1523 while( (intptr_t)const_cast<Block* volatile &>(nextPrivatizable)==binTag ) {
1524 if (--count==0) {
1525 do_yield();
1526 count = 256;
1527 }
1528 }
1529 }
1530 }
1531 MALLOC_ASSERT( publicFreeList!=NULL, ASSERT_TEXT );
1532 // now it is safe to change our data
1533 previous = NULL;
1534 // it is caller responsibility to ensure that the list of blocks
1535 // formed by nextPrivatizable pointers is kept consistent if required.
1536 // if only called from thread shutdown code, it does not matter.
1537 (intptr_t&)(nextPrivatizable) = UNUSABLE;
1538}
1539
1540void Block::cleanBlockHeader()
1541{
1542 next = NULL;
1543 previous = NULL;
1544 freeList = NULL;
1545 allocatedCount = 0;
1546 isFull = false;
1547 tlsPtr = NULL;
1548
1549 publicFreeList = NULL;
1550}
1551
1552void Block::initEmptyBlock(TLSData *tls, size_t size)
1553{
1554 // Having getIndex and getObjectSize called next to each other
1555 // allows better compiler optimization as they basically share the code.
1556 unsigned int index = getIndex(size);
1557 unsigned int objSz = getObjectSize(size);
1558
1559 cleanBlockHeader();
1560 objectSize = objSz;
1561 markOwned(tls);
1562 // bump pointer should be prepared for first allocation - thus mode it down to objectSize
1563 bumpPtr = (FreeObject *)((uintptr_t)this + slabSize - objectSize);
1564
1565 // each block should have the address where the head of the list of "privatizable" blocks is kept
1566 // the only exception is a block for boot strap which is initialized when TLS is yet NULL
1567 nextPrivatizable = tls? (Block*)(tls->bin + index) : NULL;
1568 TRACEF(( "[ScalableMalloc trace] Empty block %p is initialized, owner is %ld, objectSize is %d, bumpPtr is %p\n",
1569 this, tlsPtr ? getThreadId() : -1, objectSize, bumpPtr ));
1570}
1571
1572Block *OrphanedBlocks::get(TLSData *tls, unsigned int size)
1573{
1574 // TODO: try to use index from getAllocationBin
1575 unsigned int index = getIndex(size);
1576 Block *block = bins[index].pop();
1577 if (block) {
1578 MALLOC_ITT_SYNC_ACQUIRED(bins+index);
1579 block->privatizeOrphaned(tls, index);
1580 }
1581 return block;
1582}
1583
1584void OrphanedBlocks::put(intptr_t binTag, Block *block)
1585{
1586 unsigned int index = getIndex(block->getSize());
1587 block->shareOrphaned(binTag, index);
1588 MALLOC_ITT_SYNC_RELEASING(bins+index);
1589 bins[index].push(block);
1590}
1591
1592void OrphanedBlocks::reset()
1593{
1594 for (uint32_t i=0; i<numBlockBinLimit; i++)
1595 new (bins+i) LifoList();
1596}
1597
1598bool OrphanedBlocks::cleanup(Backend* backend)
1599{
1600 bool released = false;
1601 for (uint32_t i=0; i<numBlockBinLimit; i++) {
1602 Block* block = bins[i].grab();
1603 MALLOC_ITT_SYNC_ACQUIRED(bins+i);
1604 while (block) {
1605 Block* next = block->next;
1606 block->privatizePublicFreeList( /*reset=*/false ); // do not set publicFreeList to NULL
1607 if (block->empty()) {
1608 block->reset();
1609 // slab blocks in user's pools do not have valid backRefIdx
1610 if (!backend->inUserPool())
1611 removeBackRef(*(block->getBackRefIdx()));
1612 backend->putSlabBlock(block);
1613 released = true;
1614 } else {
1615 MALLOC_ITT_SYNC_RELEASING(bins+i);
1616 bins[i].push(block);
1617 }
1618 block = next;
1619 }
1620 }
1621 return released;
1622}
1623
1624FreeBlockPool::ResOfGet FreeBlockPool::getBlock()
1625{
1626 Block *b = (Block*)AtomicFetchStore(&head, 0);
1627
1628 if (b) {
1629 size--;
1630 Block *newHead = b->next;
1631 lastAccessMiss = false;
1632 FencedStore((intptr_t&)head, (intptr_t)newHead);
1633 } else
1634 lastAccessMiss = true;
1635
1636 return ResOfGet(b, lastAccessMiss);
1637}
1638
1639void FreeBlockPool::returnBlock(Block *block)
1640{
1641 MALLOC_ASSERT( size <= POOL_HIGH_MARK, ASSERT_TEXT );
1642 Block *localHead = (Block*)AtomicFetchStore(&head, 0);
1643
1644 if (!localHead)
1645 size = 0; // head was stolen by externalClean, correct size accordingly
1646 else if (size == POOL_HIGH_MARK) {
1647 // release cold blocks and add hot one,
1648 // so keep POOL_LOW_MARK-1 blocks and add new block to head
1649 Block *headToFree = localHead, *helper;
1650 for (int i=0; i<POOL_LOW_MARK-2; i++)
1651 headToFree = headToFree->next;
1652 Block *last = headToFree;
1653 headToFree = headToFree->next;
1654 last->next = NULL;
1655 size = POOL_LOW_MARK-1;
1656 for (Block *currBl = headToFree; currBl; currBl = helper) {
1657 helper = currBl->next;
1658 // slab blocks in user's pools do not have valid backRefIdx
1659 if (!backend->inUserPool())
1660 removeBackRef(currBl->backRefIdx);
1661 backend->putSlabBlock(currBl);
1662 }
1663 }
1664 size++;
1665 block->next = localHead;
1666 FencedStore((intptr_t&)head, (intptr_t)block);
1667}
1668
1669bool FreeBlockPool::externalCleanup()
1670{
1671 Block *helper;
1672 bool released = false;
1673
1674 for (Block *currBl=(Block*)AtomicFetchStore(&head, 0); currBl; currBl=helper) {
1675 helper = currBl->next;
1676 // slab blocks in user's pools do not have valid backRefIdx
1677 if (!backend->inUserPool())
1678 removeBackRef(currBl->backRefIdx);
1679 backend->putSlabBlock(currBl);
1680 released = true;
1681 }
1682 return released;
1683}
1684
1685/* Prepare the block for returning to FreeBlockPool */
1686void Block::reset()
1687{
1688 // it is caller's responsibility to ensure no data is lost before calling this
1689 MALLOC_ASSERT( allocatedCount==0, ASSERT_TEXT );
1690 MALLOC_ASSERT( !isSolidPtr(publicFreeList), ASSERT_TEXT );
1691 if (!isStartupAllocObject())
1692 STAT_increment(getThreadId(), getIndex(objectSize), freeBlockBack);
1693
1694 cleanBlockHeader();
1695
1696 nextPrivatizable = NULL;
1697
1698 objectSize = 0;
1699 // for an empty block, bump pointer should point right after the end of the block
1700 bumpPtr = (FreeObject *)((uintptr_t)this + slabSize);
1701}
1702
1703inline void Bin::setActiveBlock (Block *block)
1704{
1705// MALLOC_ASSERT( bin, ASSERT_TEXT );
1706 MALLOC_ASSERT( block->isOwnedByCurrentThread(), ASSERT_TEXT );
1707 // it is the caller responsibility to keep bin consistence (i.e. ensure this block is in the bin list)
1708 activeBlk = block;
1709}
1710
1711inline Block* Bin::setPreviousBlockActive()
1712{
1713 MALLOC_ASSERT( activeBlk, ASSERT_TEXT );
1714 Block* temp = activeBlk->previous;
1715 if( temp ) {
1716 MALLOC_ASSERT( !(temp->isFull), ASSERT_TEXT );
1717 activeBlk = temp;
1718 }
1719 return temp;
1720}
1721
1722inline bool Block::isOwnedByCurrentThread() const {
1723 return tlsPtr && ownerTid.isCurrentThreadId();
1724}
1725
1726FreeObject *Block::findObjectToFree(const void *object) const
1727{
1728 FreeObject *objectToFree;
1729 // Due to aligned allocations, a pointer passed to scalable_free
1730 // might differ from the address of internally allocated object.
1731 // Small objects however should always be fine.
1732 if (objectSize <= maxSegregatedObjectSize)
1733 objectToFree = (FreeObject*)object;
1734 // "Fitting size" allocations are suspicious if aligned higher than naturally
1735 else {
1736 if ( ! isAligned(object,2*fittingAlignment) )
1737 // TODO: the above check is questionable - it gives false negatives in ~50% cases,
1738 // so might even be slower in average than unconditional use of findAllocatedObject.
1739 // here it should be a "real" object
1740 objectToFree = (FreeObject*)object;
1741 else
1742 // here object can be an aligned address, so applying additional checks
1743 objectToFree = findAllocatedObject(object);
1744 MALLOC_ASSERT( isAligned(objectToFree,fittingAlignment), ASSERT_TEXT );
1745 }
1746 MALLOC_ASSERT( isProperlyPlaced(objectToFree), ASSERT_TEXT );
1747
1748 return objectToFree;
1749}
1750
1751void TLSData::release()
1752{
1753 memPool->extMemPool.allLocalCaches.unregisterThread(this);
1754 externalCleanup(/*cleanOnlyUnused=*/false, /*cleanBins=*/false);
1755
1756 for (unsigned index = 0; index < numBlockBins; index++) {
1757 Block *activeBlk = bin[index].getActiveBlock();
1758 if (!activeBlk)
1759 continue;
1760 Block *threadlessBlock = activeBlk->previous;
1761 while (threadlessBlock) {
1762 Block *threadBlock = threadlessBlock->previous;
1763 if (threadlessBlock->empty()) {
1764 /* we destroy the thread, so not use its block pool */
1765 memPool->returnEmptyBlock(threadlessBlock, /*poolTheBlock=*/false);
1766 } else {
1767 memPool->extMemPool.orphanedBlocks.put(intptr_t(bin+index), threadlessBlock);
1768 }
1769 threadlessBlock = threadBlock;
1770 }
1771 threadlessBlock = activeBlk;
1772 while (threadlessBlock) {
1773 Block *threadBlock = threadlessBlock->next;
1774 if (threadlessBlock->empty()) {
1775 /* we destroy the thread, so not use its block pool */
1776 memPool->returnEmptyBlock(threadlessBlock, /*poolTheBlock=*/false);
1777 } else {
1778 memPool->extMemPool.orphanedBlocks.put(intptr_t(bin+index), threadlessBlock);
1779 }
1780 threadlessBlock = threadBlock;
1781 }
1782 bin[index].resetActiveBlock();
1783 }
1784}
1785
1786
1787#if MALLOC_CHECK_RECURSION
1788// TODO: Use dedicated heap for this
1789
1790/*
1791 * It's a special kind of allocation that can be used when malloc is
1792 * not available (either during startup or when malloc was already called and
1793 * we are, say, inside pthread_setspecific's call).
1794 * Block can contain objects of different sizes,
1795 * allocations are performed by moving bump pointer and increasing of object counter,
1796 * releasing is done via counter of objects allocated in the block
1797 * or moving bump pointer if releasing object is on a bound.
1798 * TODO: make bump pointer to grow to the same backward direction as all the others.
1799 */
1800
1801class StartupBlock : public Block {
1802 size_t availableSize() const {
1803 return slabSize - ((uintptr_t)bumpPtr - (uintptr_t)this);
1804 }
1805 static StartupBlock *getBlock();
1806public:
1807 static FreeObject *allocate(size_t size);
1808 static size_t msize(void *ptr) { return *((size_t*)ptr - 1); }
1809 void free(void *ptr);
1810};
1811
1812static MallocMutex startupMallocLock;
1813static StartupBlock *firstStartupBlock;
1814
1815StartupBlock *StartupBlock::getBlock()
1816{
1817 BackRefIdx backRefIdx = BackRefIdx::newBackRef(/*largeObj=*/false);
1818 if (backRefIdx.isInvalid()) return NULL;
1819
1820 StartupBlock *block = static_cast<StartupBlock*>(
1821 defaultMemPool->extMemPool.backend.getSlabBlock(1));
1822 if (!block) return NULL;
1823
1824 block->cleanBlockHeader();
1825 setBackRef(backRefIdx, block);
1826 block->backRefIdx = backRefIdx;
1827 // use startupAllocObjSizeMark to mark objects from startup block marker
1828 block->objectSize = startupAllocObjSizeMark;
1829 block->bumpPtr = (FreeObject *)((uintptr_t)block + sizeof(StartupBlock));
1830 return block;
1831}
1832
1833FreeObject *StartupBlock::allocate(size_t size)
1834{
1835 FreeObject *result;
1836 StartupBlock *newBlock = NULL;
1837 bool newBlockUnused = false;
1838
1839 /* Objects must be aligned on their natural bounds,
1840 and objects bigger than word on word's bound. */
1841 size = alignUp(size, sizeof(size_t));
1842 // We need size of an object to implement msize.
1843 size_t reqSize = size + sizeof(size_t);
1844 // speculatively allocates newBlock to try avoid allocation while holding lock
1845 /* TODO: The function is called when malloc nested call is detected,
1846 so simultaneous usage from different threads seems unlikely.
1847 If pre-allocation is found useless, the code might be simplified. */
1848 if (!firstStartupBlock || firstStartupBlock->availableSize() < reqSize) {
1849 newBlock = StartupBlock::getBlock();
1850 if (!newBlock) return NULL;
1851 }
1852 {
1853 MallocMutex::scoped_lock scoped_cs(startupMallocLock);
1854 // Re-check whether we need a new block (conditions might have changed)
1855 if (!firstStartupBlock || firstStartupBlock->availableSize() < reqSize) {
1856 if (!newBlock) {
1857 newBlock = StartupBlock::getBlock();
1858 if (!newBlock) return NULL;
1859 }
1860 newBlock->next = (Block*)firstStartupBlock;
1861 if (firstStartupBlock)
1862 firstStartupBlock->previous = (Block*)newBlock;
1863 firstStartupBlock = newBlock;
1864 } else
1865 newBlockUnused = true;
1866 result = firstStartupBlock->bumpPtr;
1867 firstStartupBlock->allocatedCount++;
1868 firstStartupBlock->bumpPtr =
1869 (FreeObject *)((uintptr_t)firstStartupBlock->bumpPtr + reqSize);
1870 }
1871 if (newBlock && newBlockUnused)
1872 defaultMemPool->returnEmptyBlock(newBlock, /*poolTheBlock=*/false);
1873
1874 // keep object size at the negative offset
1875 *((size_t*)result) = size;
1876 return (FreeObject*)((size_t*)result+1);
1877}
1878
1879void StartupBlock::free(void *ptr)
1880{
1881 Block* blockToRelease = NULL;
1882 {
1883 MallocMutex::scoped_lock scoped_cs(startupMallocLock);
1884
1885 MALLOC_ASSERT(firstStartupBlock, ASSERT_TEXT);
1886 MALLOC_ASSERT(startupAllocObjSizeMark==objectSize
1887 && allocatedCount>0, ASSERT_TEXT);
1888 MALLOC_ASSERT((uintptr_t)ptr>=(uintptr_t)this+sizeof(StartupBlock)
1889 && (uintptr_t)ptr+StartupBlock::msize(ptr)<=(uintptr_t)this+slabSize,
1890 ASSERT_TEXT);
1891 if (0 == --allocatedCount) {
1892 if (this == firstStartupBlock)
1893 firstStartupBlock = (StartupBlock*)firstStartupBlock->next;
1894 if (previous)
1895 previous->next = next;
1896 if (next)
1897 next->previous = previous;
1898 blockToRelease = this;
1899 } else if ((uintptr_t)ptr + StartupBlock::msize(ptr) == (uintptr_t)bumpPtr) {
1900 // last object in the block released
1901 FreeObject *newBump = (FreeObject*)((size_t*)ptr - 1);
1902 MALLOC_ASSERT((uintptr_t)newBump>(uintptr_t)this+sizeof(StartupBlock),
1903 ASSERT_TEXT);
1904 bumpPtr = newBump;
1905 }
1906 }
1907 if (blockToRelease) {
1908 blockToRelease->previous = blockToRelease->next = NULL;
1909 defaultMemPool->returnEmptyBlock(blockToRelease, /*poolTheBlock=*/false);
1910 }
1911}
1912
1913#endif /* MALLOC_CHECK_RECURSION */
1914
1915/********* End thread related code *************/
1916
1917/********* Library initialization *************/
1918
1919//! Value indicating the state of initialization.
1920/* 0 = initialization not started.
1921 * 1 = initialization started but not finished.
1922 * 2 = initialization finished.
1923 * In theory, we only need values 0 and 2. But value 1 is nonetheless
1924 * useful for detecting errors in the double-check pattern.
1925 */
1926static intptr_t mallocInitialized; // implicitly initialized to 0
1927static MallocMutex initMutex;
1928
1929/** The leading "\0" is here so that applying "strings" to the binary
1930 delivers a clean result. */
1931static char VersionString[] = "\0" TBBMALLOC_VERSION_STRINGS;
1932
1933#if USE_PTHREAD && (__TBB_SOURCE_DIRECTLY_INCLUDED || __TBB_USE_DLOPEN_REENTRANCY_WORKAROUND)
1934
1935/* Decrease race interval between dynamic library unloading and pthread key
1936 destructor. Protect only Pthreads with supported unloading. */
1937class ShutdownSync {
1938/* flag is the number of threads in pthread key dtor body
1939 (i.e., between threadDtorStart() and threadDtorDone())
1940 or the signal to skip dtor, if flag < 0 */
1941 intptr_t flag;
1942 static const intptr_t skipDtor = INTPTR_MIN/2;
1943public:
1944 void init() { flag = 0; }
1945/* Suppose that 2*abs(skipDtor) or more threads never call threadDtorStart()
1946 simultaneously, so flag never becomes negative because of that. */
1947 bool threadDtorStart() {
1948 if (flag < 0)
1949 return false;
1950 if (AtomicIncrement(flag) <= 0) { // note that new value returned
1951 AtomicAdd(flag, -1); // flag is spoiled by us, restore it
1952 return false;
1953 }
1954 return true;
1955 }
1956 void threadDtorDone() {
1957 AtomicAdd(flag, -1);
1958 }
1959 void processExit() {
1960 if (AtomicAdd(flag, skipDtor) != 0)
1961 SpinWaitUntilEq(flag, skipDtor);
1962 }
1963};
1964
1965#else
1966
1967class ShutdownSync {
1968public:
1969 void init() { }
1970 bool threadDtorStart() { return true; }
1971 void threadDtorDone() { }
1972 void processExit() { }
1973};
1974
1975#endif // USE_PTHREAD && (__TBB_SOURCE_DIRECTLY_INCLUDED || __TBB_USE_DLOPEN_REENTRANCY_WORKAROUND)
1976
1977static ShutdownSync shutdownSync;
1978
1979inline bool isMallocInitialized() {
1980 // Load must have acquire fence; otherwise thread taking "initialized" path
1981 // might perform textually later loads *before* mallocInitialized becomes 2.
1982 return 2 == FencedLoad(mallocInitialized);
1983}
1984
1985bool isMallocInitializedExt() {
1986 return isMallocInitialized();
1987}
1988
1989/* Caller is responsible for ensuring this routine is called exactly once. */
1990extern "C" void MallocInitializeITT() {
1991#if DO_ITT_NOTIFY
1992 if (!usedBySrcIncluded)
1993 tbb::internal::__TBB_load_ittnotify();
1994#endif
1995}
1996
1997void MemoryPool::initDefaultPool() {
1998 hugePages.init();
1999}
2000
2001/*
2002 * Allocator initialization routine;
2003 * it is called lazily on the very first scalable_malloc call.
2004 */
2005static bool initMemoryManager()
2006{
2007 TRACEF(( "[ScalableMalloc trace] sizeof(Block) is %d (expected 128); sizeof(uintptr_t) is %d\n",
2008 sizeof(Block), sizeof(uintptr_t) ));
2009 MALLOC_ASSERT( 2*blockHeaderAlignment == sizeof(Block), ASSERT_TEXT );
2010 MALLOC_ASSERT( sizeof(FreeObject) == sizeof(void*), ASSERT_TEXT );
2011 MALLOC_ASSERT( isAligned(defaultMemPool, sizeof(intptr_t)),
2012 "Memory pool must be void*-aligned for atomic to work over aligned arguments.");
2013
2014#if USE_WINTHREAD
2015 const size_t granularity = 64*1024; // granulatity of VirtualAlloc
2016#else
2017 // POSIX.1-2001-compliant way to get page size
2018 const size_t granularity = sysconf(_SC_PAGESIZE);
2019#endif
2020 if (!defaultMemPool) {
2021 // Do not rely on static constructors and do the assignment in case
2022 // of library static section not initialized at this call yet.
2023 defaultMemPool = (MemoryPool*)defaultMemPool_space;
2024 }
2025 bool initOk = defaultMemPool->
2026 extMemPool.init(0, NULL, NULL, granularity,
2027 /*keepAllMemory=*/false, /*fixedPool=*/false);
2028// TODO: extMemPool.init() to not allocate memory
2029 if (!initOk || !initBackRefMaster(&defaultMemPool->extMemPool.backend) || !ThreadId::init())
2030 return false;
2031 MemoryPool::initDefaultPool();
2032 // init() is required iff initMemoryManager() is called
2033 // after mallocProcessShutdownNotification()
2034 shutdownSync.init();
2035#if COLLECT_STATISTICS
2036 initStatisticsCollection();
2037#endif
2038 return true;
2039}
2040
2041static bool GetBoolEnvironmentVariable(const char* name) {
2042 return tbb::internal::GetBoolEnvironmentVariable(name);
2043}
2044
2045//! Ensures that initMemoryManager() is called once and only once.
2046/** Does not return until initMemoryManager() has been completed by a thread.
2047 There is no need to call this routine if mallocInitialized==2 . */
2048static bool doInitialization()
2049{
2050 MallocMutex::scoped_lock lock( initMutex );
2051 if (mallocInitialized!=2) {
2052 MALLOC_ASSERT( mallocInitialized==0, ASSERT_TEXT );
2053 mallocInitialized = 1;
2054 RecursiveMallocCallProtector scoped;
2055 if (!initMemoryManager()) {
2056 mallocInitialized = 0; // restore and out
2057 return false;
2058 }
2059#ifdef MALLOC_EXTRA_INITIALIZATION
2060 MALLOC_EXTRA_INITIALIZATION;
2061#endif
2062#if MALLOC_CHECK_RECURSION
2063 RecursiveMallocCallProtector::detectNaiveOverload();
2064#endif
2065 MALLOC_ASSERT( mallocInitialized==1, ASSERT_TEXT );
2066 // Store must have release fence, otherwise mallocInitialized==2
2067 // might become remotely visible before side effects of
2068 // initMemoryManager() become remotely visible.
2069 FencedStore( mallocInitialized, 2 );
2070 if( GetBoolEnvironmentVariable("TBB_VERSION") ) {
2071 fputs(VersionString+1,stderr);
2072 hugePages.printStatus();
2073 }
2074 }
2075 /* It can't be 0 or I would have initialized it */
2076 MALLOC_ASSERT( mallocInitialized==2, ASSERT_TEXT );
2077 return true;
2078}
2079
2080/********* End library initialization *************/
2081
2082/********* The malloc show begins *************/
2083
2084
2085FreeObject *Block::allocateFromFreeList()
2086{
2087 FreeObject *result;
2088
2089 if (!freeList) return NULL;
2090
2091 result = freeList;
2092 MALLOC_ASSERT( result, ASSERT_TEXT );
2093
2094 freeList = result->next;
2095 MALLOC_ASSERT( allocatedCount < (slabSize-sizeof(Block))/objectSize, ASSERT_TEXT );
2096 allocatedCount++;
2097 STAT_increment(getThreadId(), getIndex(objectSize), allocFreeListUsed);
2098
2099 return result;
2100}
2101
2102FreeObject *Block::allocateFromBumpPtr()
2103{
2104 FreeObject *result = bumpPtr;
2105 if (result) {
2106 bumpPtr = (FreeObject *) ((uintptr_t) bumpPtr - objectSize);
2107 if ( (uintptr_t)bumpPtr < (uintptr_t)this+sizeof(Block) ) {
2108 bumpPtr = NULL;
2109 }
2110 MALLOC_ASSERT( allocatedCount < (slabSize-sizeof(Block))/objectSize, ASSERT_TEXT );
2111 allocatedCount++;
2112 STAT_increment(getThreadId(), getIndex(objectSize), allocBumpPtrUsed);
2113 }
2114 return result;
2115}
2116
2117inline FreeObject* Block::allocate()
2118{
2119 MALLOC_ASSERT( isOwnedByCurrentThread(), ASSERT_TEXT );
2120
2121 /* for better cache locality, first looking in the free list. */
2122 if ( FreeObject *result = allocateFromFreeList() ) {
2123 return result;
2124 }
2125 MALLOC_ASSERT( !freeList, ASSERT_TEXT );
2126
2127 /* if free list is empty, try thread local bump pointer allocation. */
2128 if ( FreeObject *result = allocateFromBumpPtr() ) {
2129 return result;
2130 }
2131 MALLOC_ASSERT( !bumpPtr, ASSERT_TEXT );
2132
2133 /* the block is considered full. */
2134 isFull = true;
2135 return NULL;
2136}
2137
2138size_t Block::findObjectSize(void *object) const
2139{
2140 size_t blSize = getSize();
2141#if MALLOC_CHECK_RECURSION
2142 // Currently, there is no aligned allocations from startup blocks,
2143 // so we can return just StartupBlock::msize().
2144 // TODO: This must be extended if we add aligned allocation from startup blocks.
2145 if (!blSize)
2146 return StartupBlock::msize(object);
2147#endif
2148 // object can be aligned, so real size can be less than block's
2149 size_t size =
2150 blSize - ((uintptr_t)object - (uintptr_t)findObjectToFree(object));
2151 MALLOC_ASSERT(size>0 && size<minLargeObjectSize, ASSERT_TEXT);
2152 return size;
2153}
2154
2155void Bin::moveBlockToFront(Block *block)
2156{
2157 /* move the block to the front of the bin */
2158 if (block == activeBlk) return;
2159 outofTLSBin(block);
2160 pushTLSBin(block);
2161}
2162
2163void Bin::processEmptyBlock(Block *block, bool poolTheBlock)
2164{
2165 if (block != activeBlk) {
2166 /* We are not using this block; return it to the pool */
2167 outofTLSBin(block);
2168 block->getMemPool()->returnEmptyBlock(block, poolTheBlock);
2169 } else {
2170 /* all objects are free - let's restore the bump pointer */
2171 block->restoreBumpPtr();
2172 }
2173}
2174
2175template<int LOW_MARK, int HIGH_MARK>
2176bool LocalLOCImpl<LOW_MARK, HIGH_MARK>::put(LargeMemoryBlock *object, ExtMemoryPool *extMemPool)
2177{
2178 const size_t size = object->unalignedSize;
2179 // not spoil cache with too large object, that can cause its total cleanup
2180 if (size > MAX_TOTAL_SIZE)
2181 return false;
2182 LargeMemoryBlock *localHead = (LargeMemoryBlock*)AtomicFetchStore(&head, 0);
2183
2184 object->prev = NULL;
2185 object->next = localHead;
2186 if (localHead)
2187 localHead->prev = object;
2188 else {
2189 // those might not be cleaned during local cache stealing, correct them
2190 totalSize = 0;
2191 numOfBlocks = 0;
2192 tail = object;
2193 }
2194 localHead = object;
2195 totalSize += size;
2196 numOfBlocks++;
2197 // must meet both size and number of cached objects constrains
2198 if (totalSize > MAX_TOTAL_SIZE || numOfBlocks >= HIGH_MARK) {
2199 // scanning from tail until meet conditions
2200 while (totalSize > MAX_TOTAL_SIZE || numOfBlocks > LOW_MARK) {
2201 totalSize -= tail->unalignedSize;
2202 numOfBlocks--;
2203 tail = tail->prev;
2204 }
2205 LargeMemoryBlock *headToRelease = tail->next;
2206 tail->next = NULL;
2207
2208 extMemPool->freeLargeObjectList(headToRelease);
2209 }
2210
2211 FencedStore((intptr_t&)head, (intptr_t)localHead);
2212 return true;
2213}
2214
2215template<int LOW_MARK, int HIGH_MARK>
2216LargeMemoryBlock *LocalLOCImpl<LOW_MARK, HIGH_MARK>::get(size_t size)
2217{
2218 LargeMemoryBlock *localHead, *res=NULL;
2219
2220 if (size > MAX_TOTAL_SIZE)
2221 return NULL;
2222
2223 if (!head || (localHead = (LargeMemoryBlock*)AtomicFetchStore(&head, 0)) == NULL) {
2224 // do not restore totalSize, numOfBlocks and tail at this point,
2225 // as they are used only in put(), where they must be restored
2226 return NULL;
2227 }
2228
2229 for (LargeMemoryBlock *curr = localHead; curr; curr=curr->next) {
2230 if (curr->unalignedSize == size) {
2231 res = curr;
2232 if (curr->next)
2233 curr->next->prev = curr->prev;
2234 else
2235 tail = curr->prev;
2236 if (curr != localHead)
2237 curr->prev->next = curr->next;
2238 else
2239 localHead = curr->next;
2240 totalSize -= size;
2241 numOfBlocks--;
2242 break;
2243 }
2244 }
2245 FencedStore((intptr_t&)head, (intptr_t)localHead);
2246 return res;
2247}
2248
2249template<int LOW_MARK, int HIGH_MARK>
2250bool LocalLOCImpl<LOW_MARK, HIGH_MARK>::externalCleanup(ExtMemoryPool *extMemPool)
2251{
2252 if (LargeMemoryBlock *localHead = (LargeMemoryBlock*)AtomicFetchStore(&head, 0)) {
2253 extMemPool->freeLargeObjectList(localHead);
2254 return true;
2255 }
2256 return false;
2257}
2258
2259void *MemoryPool::getFromLLOCache(TLSData* tls, size_t size, size_t alignment)
2260{
2261 LargeMemoryBlock *lmb = NULL;
2262
2263 size_t headersSize = sizeof(LargeMemoryBlock)+sizeof(LargeObjectHdr);
2264 size_t allocationSize = LargeObjectCache::alignToBin(size+headersSize+alignment);
2265 if (allocationSize < size) // allocationSize is wrapped around after alignToBin
2266 return NULL;
2267 MALLOC_ASSERT(allocationSize >= alignment, "Overflow must be checked before.");
2268
2269 if (tls) {
2270 tls->markUsed();
2271 lmb = tls->lloc.get(allocationSize);
2272 }
2273 if (!lmb)
2274 lmb = extMemPool.mallocLargeObject(this, allocationSize);
2275
2276 if (lmb) {
2277 // doing shuffle we suppose that alignment offset guarantees
2278 // that different cache lines are in use
2279 MALLOC_ASSERT(alignment >= estimatedCacheLineSize, ASSERT_TEXT);
2280
2281 void *alignedArea = (void*)alignUp((uintptr_t)lmb+headersSize, alignment);
2282 uintptr_t alignedRight =
2283 alignDown((uintptr_t)lmb+lmb->unalignedSize - size, alignment);
2284 // Has some room to shuffle object between cache lines?
2285 // Note that alignedRight and alignedArea are aligned at alignment.
2286 unsigned ptrDelta = alignedRight - (uintptr_t)alignedArea;
2287 if (ptrDelta && tls) { // !tls is cold path
2288 // for the hot path of alignment==estimatedCacheLineSize,
2289 // allow compilers to use shift for division
2290 // (since estimatedCacheLineSize is a power-of-2 constant)
2291 unsigned numOfPossibleOffsets = alignment == estimatedCacheLineSize?
2292 ptrDelta / estimatedCacheLineSize :
2293 ptrDelta / alignment;
2294 unsigned myCacheIdx = ++tls->currCacheIdx;
2295 unsigned offset = myCacheIdx % numOfPossibleOffsets;
2296
2297 // Move object to a cache line with an offset that is different from
2298 // previous allocation. This supposedly allows us to use cache
2299 // associativity more efficiently.
2300 alignedArea = (void*)((uintptr_t)alignedArea + offset*alignment);
2301 }
2302 MALLOC_ASSERT((uintptr_t)lmb+lmb->unalignedSize >=
2303 (uintptr_t)alignedArea+size, "Object doesn't fit the block.");
2304 LargeObjectHdr *header = (LargeObjectHdr*)alignedArea-1;
2305 header->memoryBlock = lmb;
2306 header->backRefIdx = lmb->backRefIdx;
2307 setBackRef(header->backRefIdx, header);
2308
2309 lmb->objectSize = size;
2310
2311 MALLOC_ASSERT( isLargeObject<unknownMem>(alignedArea), ASSERT_TEXT );
2312 MALLOC_ASSERT( isAligned(alignedArea, alignment), ASSERT_TEXT );
2313
2314 return alignedArea;
2315 }
2316 return NULL;
2317}
2318
2319void MemoryPool::putToLLOCache(TLSData *tls, void *object)
2320{
2321 LargeObjectHdr *header = (LargeObjectHdr*)object - 1;
2322 // overwrite backRefIdx to simplify double free detection
2323 header->backRefIdx = BackRefIdx();
2324
2325 if (tls) {
2326 tls->markUsed();
2327 if (tls->lloc.put(header->memoryBlock, &extMemPool))
2328 return;
2329 }
2330 extMemPool.freeLargeObject(header->memoryBlock);
2331}
2332
2333/*
2334 * All aligned allocations fall into one of the following categories:
2335 * 1. if both request size and alignment are <= maxSegregatedObjectSize,
2336 * we just align the size up, and request this amount, because for every size
2337 * aligned to some power of 2, the allocated object is at least that aligned.
2338 * 2. for size<minLargeObjectSize, check if already guaranteed fittingAlignment is enough.
2339 * 3. if size+alignment<minLargeObjectSize, we take an object of fittingSizeN and align
2340 * its address up; given such pointer, scalable_free could find the real object.
2341 * Wrapping of size+alignment is impossible because maximal allowed
2342 * alignment plus minLargeObjectSize can't lead to wrapping.
2343 * 4. otherwise, aligned large object is allocated.
2344 */
2345static void *allocateAligned(MemoryPool *memPool, size_t size, size_t alignment)
2346{
2347 MALLOC_ASSERT( isPowerOfTwo(alignment), ASSERT_TEXT );
2348
2349 if (!isMallocInitialized())
2350 if (!doInitialization())
2351 return NULL;
2352
2353 void *result;
2354 if (size<=maxSegregatedObjectSize && alignment<=maxSegregatedObjectSize)
2355 result = internalPoolMalloc(memPool, alignUp(size? size: sizeof(size_t), alignment));
2356 else if (size<minLargeObjectSize) {
2357 if (alignment<=fittingAlignment)
2358 result = internalPoolMalloc(memPool, size);
2359 else if (size+alignment < minLargeObjectSize) {
2360 void *unaligned = internalPoolMalloc(memPool, size+alignment);
2361 if (!unaligned) return NULL;
2362 result = alignUp(unaligned, alignment);
2363 } else
2364 goto LargeObjAlloc;
2365 } else {
2366 LargeObjAlloc:
2367 TLSData *tls = memPool->getTLS(/*create=*/true);
2368 // take into account only alignment that are higher then natural
2369 result =
2370 memPool->getFromLLOCache(tls, size, largeObjectAlignment>alignment?
2371 largeObjectAlignment: alignment);
2372 }
2373
2374 MALLOC_ASSERT( isAligned(result, alignment), ASSERT_TEXT );
2375 return result;
2376}
2377
2378static void *reallocAligned(MemoryPool *memPool, void *ptr,
2379 size_t newSize, size_t alignment = 0)
2380{
2381 void *result;
2382 size_t copySize;
2383
2384 if (isLargeObject<ourMem>(ptr)) {
2385 LargeMemoryBlock* lmb = ((LargeObjectHdr *)ptr - 1)->memoryBlock;
2386 copySize = lmb->unalignedSize-((uintptr_t)ptr-(uintptr_t)lmb);
2387
2388 // Apply different strategies if size decreases
2389 if (newSize <= copySize && (0 == alignment || isAligned(ptr, alignment))) {
2390
2391 // For huge objects (that do not fit in backend cache), keep the same space unless
2392 // the new size is at least twice smaller
2393 bool isMemoryBlockHuge = copySize > memPool->extMemPool.backend.getMaxBinnedSize();
2394 size_t threshold = isMemoryBlockHuge ? copySize / 2 : 0;
2395 if (newSize > threshold) {
2396 lmb->objectSize = newSize;
2397 return ptr;
2398 }
2399 // TODO: For large objects suitable for the backend cache,
2400 // split out the excessive part and put it to the backend.
2401 }
2402 // Reallocate for real
2403 copySize = lmb->objectSize;
2404#if BACKEND_HAS_MREMAP
2405 if (void *r = memPool->extMemPool.remap(ptr, copySize, newSize,
2406 alignment < largeObjectAlignment ? largeObjectAlignment : alignment))
2407 return r;
2408#endif
2409 result = alignment ? allocateAligned(memPool, newSize, alignment) :
2410 internalPoolMalloc(memPool, newSize);
2411
2412 } else {
2413 Block* block = (Block *)alignDown(ptr, slabSize);
2414 copySize = block->findObjectSize(ptr);
2415
2416 // TODO: Move object to another bin if size decreases and the current bin is "empty enough".
2417 // Currently, in case of size decreasing, old pointer is returned
2418 if (newSize <= copySize && (0==alignment || isAligned(ptr, alignment))) {
2419 return ptr;
2420 } else {
2421 result = alignment ? allocateAligned(memPool, newSize, alignment) :
2422 internalPoolMalloc(memPool, newSize);
2423 }
2424 }
2425 if (result) {
2426 memcpy(result, ptr, copySize < newSize ? copySize : newSize);
2427 internalPoolFree(memPool, ptr, 0);
2428 }
2429 return result;
2430}
2431
2432/* A predicate checks if an object is properly placed inside its block */
2433inline bool Block::isProperlyPlaced(const void *object) const
2434{
2435 return 0 == ((uintptr_t)this + slabSize - (uintptr_t)object) % objectSize;
2436}
2437
2438/* Finds the real object inside the block */
2439FreeObject *Block::findAllocatedObject(const void *address) const
2440{
2441 // calculate offset from the end of the block space
2442 uint16_t offset = (uintptr_t)this + slabSize - (uintptr_t)address;
2443 MALLOC_ASSERT( offset<=slabSize-sizeof(Block), ASSERT_TEXT );
2444 // find offset difference from a multiple of allocation size
2445 offset %= objectSize;
2446 // and move the address down to where the real object starts.
2447 return (FreeObject*)((uintptr_t)address - (offset? objectSize-offset: 0));
2448}
2449
2450/*
2451 * Bad dereference caused by a foreign pointer is possible only here, not earlier in call chain.
2452 * Separate function isolates SEH code, as it has bad influence on compiler optimization.
2453 */
2454static inline BackRefIdx safer_dereference (const BackRefIdx *ptr)
2455{
2456 BackRefIdx id;
2457#if _MSC_VER
2458 __try {
2459#endif
2460 id = *ptr;
2461#if _MSC_VER
2462 } __except( GetExceptionCode() == EXCEPTION_ACCESS_VIOLATION?
2463 EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH ) {
2464 id = BackRefIdx();
2465 }
2466#endif
2467 return id;
2468}
2469
2470template<MemoryOrigin memOrigin>
2471bool isLargeObject(void *object)
2472{
2473 if (!isAligned(object, largeObjectAlignment))
2474 return false;
2475 LargeObjectHdr *header = (LargeObjectHdr*)object - 1;
2476 BackRefIdx idx = (memOrigin == unknownMem) ?
2477 safer_dereference(&header->backRefIdx) : header->backRefIdx;
2478
2479 return idx.isLargeObject()
2480 // in valid LargeObjectHdr memoryBlock is not NULL
2481 && header->memoryBlock
2482 // in valid LargeObjectHdr memoryBlock points somewhere before header
2483 // TODO: more strict check
2484 && (uintptr_t)header->memoryBlock < (uintptr_t)header
2485 && getBackRef(idx) == header;
2486}
2487
2488static inline bool isSmallObject (void *ptr)
2489{
2490 Block* expectedBlock = (Block*)alignDown(ptr, slabSize);
2491 const BackRefIdx* idx = expectedBlock->getBackRefIdx();
2492
2493 bool isSmall = expectedBlock == getBackRef(safer_dereference(idx));
2494 if (isSmall)
2495 expectedBlock->checkFreePrecond(ptr);
2496 return isSmall;
2497}
2498
2499/**** Check if an object was allocated by scalable_malloc ****/
2500static inline bool isRecognized (void* ptr)
2501{
2502 return defaultMemPool->extMemPool.backend.ptrCanBeValid(ptr) &&
2503 (isLargeObject<unknownMem>(ptr) || isSmallObject(ptr));
2504}
2505
2506static inline void freeSmallObject(void *object)
2507{
2508 /* mask low bits to get the block */
2509 Block *block = (Block *)alignDown(object, slabSize);
2510 block->checkFreePrecond(object);
2511
2512#if MALLOC_CHECK_RECURSION
2513 if (block->isStartupAllocObject()) {
2514 ((StartupBlock *)block)->free(object);
2515 return;
2516 }
2517#endif
2518 if (block->isOwnedByCurrentThread()) {
2519 block->freeOwnObject(object);
2520 } else { /* Slower path to add to the shared list, the allocatedCount is updated by the owner thread in malloc. */
2521 FreeObject *objectToFree = block->findObjectToFree(object);
2522 block->freePublicObject(objectToFree);
2523 }
2524}
2525
2526static void *internalPoolMalloc(MemoryPool* memPool, size_t size)
2527{
2528 Bin* bin;
2529 Block * mallocBlock;
2530
2531 if (!memPool) return NULL;
2532
2533 if (!size) size = sizeof(size_t);
2534
2535 TLSData *tls = memPool->getTLS(/*create=*/true);
2536
2537 /* Allocate a large object */
2538 if (size >= minLargeObjectSize)
2539 return memPool->getFromLLOCache(tls, size, largeObjectAlignment);
2540
2541 if (!tls) return NULL;
2542
2543 tls->markUsed();
2544 /*
2545 * Get an element in thread-local array corresponding to the given size;
2546 * It keeps ptr to the active block for allocations of this size
2547 */
2548 bin = tls->getAllocationBin(size);
2549 if ( !bin ) return NULL;
2550
2551 /* Get a block to try to allocate in. */
2552 for( mallocBlock = bin->getActiveBlock(); mallocBlock;
2553 mallocBlock = bin->setPreviousBlockActive() ) // the previous block should be empty enough
2554 {
2555 if( FreeObject *result = mallocBlock->allocate() )
2556 return result;
2557 }
2558
2559 /*
2560 * else privatize publicly freed objects in some block and allocate from it
2561 */
2562 mallocBlock = bin->getPrivatizedFreeListBlock();
2563 if (mallocBlock) {
2564 MALLOC_ASSERT( mallocBlock->freeListNonNull(), ASSERT_TEXT );
2565 if ( FreeObject *result = mallocBlock->allocateFromFreeList() )
2566 return result;
2567 /* Else something strange happened, need to retry from the beginning; */
2568 TRACEF(( "[ScalableMalloc trace] Something is wrong: no objects in public free list; reentering.\n" ));
2569 return internalPoolMalloc(memPool, size);
2570 }
2571
2572 /*
2573 * no suitable own blocks, try to get a partial block that some other thread has discarded.
2574 */
2575 mallocBlock = memPool->extMemPool.orphanedBlocks.get(tls, size);
2576 while (mallocBlock) {
2577 bin->pushTLSBin(mallocBlock);
2578 bin->setActiveBlock(mallocBlock); // TODO: move under the below condition?
2579 if( FreeObject *result = mallocBlock->allocate() )
2580 return result;
2581 mallocBlock = memPool->extMemPool.orphanedBlocks.get(tls, size);
2582 }
2583
2584 /*
2585 * else try to get a new empty block
2586 */
2587 mallocBlock = memPool->getEmptyBlock(size);
2588 if (mallocBlock) {
2589 bin->pushTLSBin(mallocBlock);
2590 bin->setActiveBlock(mallocBlock);
2591 if( FreeObject *result = mallocBlock->allocate() )
2592 return result;
2593 /* Else something strange happened, need to retry from the beginning; */
2594 TRACEF(( "[ScalableMalloc trace] Something is wrong: no objects in empty block; reentering.\n" ));
2595 return internalPoolMalloc(memPool, size);
2596 }
2597 /*
2598 * else nothing works so return NULL
2599 */
2600 TRACEF(( "[ScalableMalloc trace] No memory found, returning NULL.\n" ));
2601 return NULL;
2602}
2603
2604// When size==0 (i.e. unknown), detect here whether the object is large.
2605// For size is known and < minLargeObjectSize, we still need to check
2606// if the actual object is large, because large objects might be used
2607// for aligned small allocations.
2608static bool internalPoolFree(MemoryPool *memPool, void *object, size_t size)
2609{
2610 if (!memPool || !object) return false;
2611
2612 // The library is initialized at allocation call, so releasing while
2613 // not initialized means foreign object is releasing.
2614 MALLOC_ASSERT(isMallocInitialized(), ASSERT_TEXT);
2615 MALLOC_ASSERT(memPool->extMemPool.userPool() || isRecognized(object),
2616 "Invalid pointer during object releasing is detected.");
2617
2618 if (size >= minLargeObjectSize || isLargeObject<ourMem>(object))
2619 memPool->putToLLOCache(memPool->getTLS(/*create=*/false), object);
2620 else
2621 freeSmallObject(object);
2622 return true;
2623}
2624
2625static void *internalMalloc(size_t size)
2626{
2627 if (!size) size = sizeof(size_t);
2628
2629#if MALLOC_CHECK_RECURSION
2630 if (RecursiveMallocCallProtector::sameThreadActive())
2631 return size<minLargeObjectSize? StartupBlock::allocate(size) :
2632 // nested allocation, so skip tls
2633 (FreeObject*)defaultMemPool->getFromLLOCache(NULL, size, slabSize);
2634#endif
2635
2636 if (!isMallocInitialized())
2637 if (!doInitialization())
2638 return NULL;
2639 return internalPoolMalloc(defaultMemPool, size);
2640}
2641
2642static void internalFree(void *object)
2643{
2644 internalPoolFree(defaultMemPool, object, 0);
2645}
2646
2647static size_t internalMsize(void* ptr)
2648{
2649 MALLOC_ASSERT(ptr, "Invalid pointer passed to internalMsize");
2650 if (isLargeObject<ourMem>(ptr)) {
2651 // TODO: return the maximum memory size, that can be written to this object
2652 LargeMemoryBlock* lmb = ((LargeObjectHdr*)ptr - 1)->memoryBlock;
2653 return lmb->objectSize;
2654 } else {
2655 Block *block = (Block*)alignDown(ptr, slabSize);
2656 return block->findObjectSize(ptr);
2657 }
2658}
2659
2660} // namespace internal
2661
2662using namespace rml::internal;
2663
2664// legacy entry point saved for compatibility with binaries complied
2665// with pre-6003 versions of TBB
2666rml::MemoryPool *pool_create(intptr_t pool_id, const MemPoolPolicy *policy)
2667{
2668 rml::MemoryPool *pool;
2669 MemPoolPolicy pol(policy->pAlloc, policy->pFree, policy->granularity);
2670
2671 pool_create_v1(pool_id, &pol, &pool);
2672 return pool;
2673}
2674
2675rml::MemPoolError pool_create_v1(intptr_t pool_id, const MemPoolPolicy *policy,
2676 rml::MemoryPool **pool)
2677{
2678 if ( !policy->pAlloc || policy->version<MemPoolPolicy::TBBMALLOC_POOL_VERSION
2679 // empty pFree allowed only for fixed pools
2680 || !(policy->fixedPool || policy->pFree)) {
2681 *pool = NULL;
2682 return INVALID_POLICY;
2683 }
2684 if ( policy->version>MemPoolPolicy::TBBMALLOC_POOL_VERSION // future versions are not supported
2685 // new flags can be added in place of reserved, but default
2686 // behaviour must be supported by this version
2687 || policy->reserved ) {
2688 *pool = NULL;
2689 return UNSUPPORTED_POLICY;
2690 }
2691 if (!isMallocInitialized())
2692 if (!doInitialization()) {
2693 *pool = NULL;
2694 return NO_MEMORY;
2695 }
2696 rml::internal::MemoryPool *memPool =
2697 (rml::internal::MemoryPool*)internalMalloc((sizeof(rml::internal::MemoryPool)));
2698 if (!memPool) {
2699 *pool = NULL;
2700 return NO_MEMORY;
2701 }
2702 memset(memPool, 0, sizeof(rml::internal::MemoryPool));
2703 if (!memPool->init(pool_id, policy)) {
2704 internalFree(memPool);
2705 *pool = NULL;
2706 return NO_MEMORY;
2707 }
2708
2709 *pool = (rml::MemoryPool*)memPool;
2710 return POOL_OK;
2711}
2712
2713bool pool_destroy(rml::MemoryPool* memPool)
2714{
2715 if (!memPool) return false;
2716 bool ret = ((rml::internal::MemoryPool*)memPool)->destroy();
2717 internalFree(memPool);
2718
2719 return ret;
2720}
2721
2722bool pool_reset(rml::MemoryPool* memPool)
2723{
2724 if (!memPool) return false;
2725
2726 return ((rml::internal::MemoryPool*)memPool)->reset();
2727}
2728
2729void *pool_malloc(rml::MemoryPool* mPool, size_t size)
2730{
2731 return internalPoolMalloc((rml::internal::MemoryPool*)mPool, size);
2732}
2733
2734void *pool_realloc(rml::MemoryPool* mPool, void *object, size_t size)
2735{
2736 if (!object)
2737 return internalPoolMalloc((rml::internal::MemoryPool*)mPool, size);
2738 if (!size) {
2739 internalPoolFree((rml::internal::MemoryPool*)mPool, object, 0);
2740 return NULL;
2741 }
2742 return reallocAligned((rml::internal::MemoryPool*)mPool, object, size, 0);
2743}
2744
2745void *pool_aligned_malloc(rml::MemoryPool* mPool, size_t size, size_t alignment)
2746{
2747 if (!isPowerOfTwo(alignment) || 0==size)
2748 return NULL;
2749
2750 return allocateAligned((rml::internal::MemoryPool*)mPool, size, alignment);
2751}
2752
2753void *pool_aligned_realloc(rml::MemoryPool* memPool, void *ptr, size_t size, size_t alignment)
2754{
2755 if (!isPowerOfTwo(alignment))
2756 return NULL;
2757 rml::internal::MemoryPool *mPool = (rml::internal::MemoryPool*)memPool;
2758 void *tmp;
2759
2760 if (!ptr)
2761 tmp = allocateAligned(mPool, size, alignment);
2762 else if (!size) {
2763 internalPoolFree(mPool, ptr, 0);
2764 return NULL;
2765 } else
2766 tmp = reallocAligned(mPool, ptr, size, alignment);
2767
2768 return tmp;
2769}
2770
2771bool pool_free(rml::MemoryPool *mPool, void *object)
2772{
2773 return internalPoolFree((rml::internal::MemoryPool*)mPool, object, 0);
2774}
2775
2776rml::MemoryPool *pool_identify(void *object)
2777{
2778 rml::internal::MemoryPool *pool;
2779 if (isLargeObject<ourMem>(object)) {
2780 LargeObjectHdr *header = (LargeObjectHdr*)object - 1;
2781 pool = header->memoryBlock->pool;
2782 } else {
2783 Block *block = (Block*)alignDown(object, slabSize);
2784 pool = block->getMemPool();
2785 }
2786 // do not return defaultMemPool, as it can't be used in pool_free() etc
2787 __TBB_ASSERT_RELEASE(pool!=defaultMemPool,
2788 "rml::pool_identify() can't be used for scalable_malloc() etc results.");
2789 return (rml::MemoryPool*)pool;
2790}
2791
2792size_t pool_msize(rml::MemoryPool *mPool, void* object)
2793{
2794 if (object) {
2795 // No assert for object recognition, cause objects allocated from non-default
2796 // memory pool do not participate in range checking and do not have valid backreferences for
2797 // small objects. Instead, check that an object belong to the certain memory pool.
2798 MALLOC_ASSERT_EX(mPool == pool_identify(object), "Object does not belong to the specified pool");
2799 return internalMsize(object);
2800 }
2801 errno = EINVAL;
2802 // Unlike _msize, return 0 in case of parameter error.
2803 // Returning size_t(-1) looks more like the way to troubles.
2804 return 0;
2805}
2806
2807} // namespace rml
2808
2809using namespace rml::internal;
2810
2811#if MALLOC_TRACE
2812static unsigned int threadGoingDownCount = 0;
2813#endif
2814
2815/*
2816 * When a thread is shutting down this routine should be called to remove all the thread ids
2817 * from the malloc blocks and replace them with a NULL thread id.
2818 *
2819 * For pthreads, the function is set as a callback in pthread_key_create for TLS bin.
2820 * It will be automatically called at thread exit with the key value as the argument,
2821 * unless that value is NULL.
2822 * For Windows, it is called from DllMain( DLL_THREAD_DETACH ).
2823 *
2824 * However neither of the above is called for the main process thread, so the routine
2825 * also needs to be called during the process shutdown.
2826 *
2827*/
2828// TODO: Consider making this function part of class MemoryPool.
2829void doThreadShutdownNotification(TLSData* tls, bool main_thread)
2830{
2831 TRACEF(( "[ScalableMalloc trace] Thread id %d blocks return start %d\n",
2832 getThreadId(), threadGoingDownCount++ ));
2833
2834#if USE_PTHREAD
2835 if (tls) {
2836 if (!shutdownSync.threadDtorStart()) return;
2837 tls->getMemPool()->onThreadShutdown(tls);
2838 shutdownSync.threadDtorDone();
2839 } else
2840#endif
2841 {
2842 suppress_unused_warning(tls); // not used on Windows
2843 // The default pool is safe to use at this point:
2844 // on Linux, only the main thread can go here before destroying defaultMemPool;
2845 // on Windows, shutdown is synchronized via loader lock and isMallocInitialized().
2846 // See also __TBB_mallocProcessShutdownNotification()
2847 defaultMemPool->onThreadShutdown(defaultMemPool->getTLS(/*create=*/false));
2848 // Take lock to walk through other pools; but waiting might be dangerous at this point
2849 // (e.g. on Windows the main thread might deadlock)
2850 bool locked;
2851 MallocMutex::scoped_lock lock(MemoryPool::memPoolListLock, /*wait=*/!main_thread, &locked);
2852 if (locked) { // the list is safe to process
2853 for (MemoryPool *memPool = defaultMemPool->next; memPool; memPool = memPool->next)
2854 memPool->onThreadShutdown(memPool->getTLS(/*create=*/false));
2855 }
2856 }
2857
2858 TRACEF(( "[ScalableMalloc trace] Thread id %d blocks return end\n", getThreadId() ));
2859}
2860
2861#if USE_PTHREAD
2862void mallocThreadShutdownNotification(void* arg)
2863{
2864 // The routine is called for each pool (as TLS dtor) on each thread, except for the main thread
2865 if (!isMallocInitialized()) return;
2866 doThreadShutdownNotification((TLSData*)arg, false);
2867}
2868#else
2869extern "C" void __TBB_mallocThreadShutdownNotification()
2870{
2871 // The routine is called once per thread on Windows
2872 if (!isMallocInitialized()) return;
2873 doThreadShutdownNotification(NULL, false);
2874}
2875#endif
2876
2877extern "C" void __TBB_mallocProcessShutdownNotification(bool windows_process_dying)
2878{
2879 if (!isMallocInitialized()) return;
2880
2881 // Don't clean allocator internals if the entire process is exiting
2882 if (!windows_process_dying) {
2883 doThreadShutdownNotification(NULL, /*main_thread=*/true);
2884 }
2885#if __TBB_MALLOC_LOCACHE_STAT
2886 printf("cache hit ratio %f, size hit %f\n",
2887 1.*cacheHits/mallocCalls, 1.*memHitKB/memAllocKB);
2888 defaultMemPool->extMemPool.loc.reportStat(stdout);
2889#endif
2890
2891 shutdownSync.processExit();
2892#if __TBB_SOURCE_DIRECTLY_INCLUDED
2893/* Pthread keys must be deleted as soon as possible to not call key dtor
2894 on thread termination when then the tbbmalloc code can be already unloaded.
2895*/
2896 defaultMemPool->destroy();
2897 destroyBackRefMaster(&defaultMemPool->extMemPool.backend);
2898 ThreadId::destroy(); // Delete key for thread id
2899 hugePages.reset();
2900 // new total malloc initialization is possible after this point
2901 FencedStore(mallocInitialized, 0);
2902#elif __TBB_USE_DLOPEN_REENTRANCY_WORKAROUND
2903/* In most cases we prevent unloading tbbmalloc, and don't clean up memory
2904 on process shutdown. When impossible to prevent, library unload results
2905 in shutdown notification, and it makes sense to release unused memory
2906 at that point (we can't release all memory because it's possible that
2907 it will be accessed after this point).
2908 TODO: better support systems where we can't prevent unloading by removing
2909 pthread destructors and releasing caches.
2910 */
2911 defaultMemPool->extMemPool.hardCachesCleanup();
2912#endif // __TBB_SOURCE_DIRECTLY_INCLUDED
2913
2914#if COLLECT_STATISTICS
2915 unsigned nThreads = ThreadId::getMaxThreadId();
2916 for( int i=1; i<=nThreads && i<MAX_THREADS; ++i )
2917 STAT_print(i);
2918#endif
2919 if (!usedBySrcIncluded)
2920 MALLOC_ITT_FINI_ITTLIB();
2921}
2922
2923extern "C" void * scalable_malloc(size_t size)
2924{
2925 void *ptr = internalMalloc(size);
2926 if (!ptr) errno = ENOMEM;
2927 return ptr;
2928}
2929
2930extern "C" void scalable_free(void *object)
2931{
2932 internalFree(object);
2933}
2934
2935#if MALLOC_ZONE_OVERLOAD_ENABLED
2936extern "C" void __TBB_malloc_free_definite_size(void *object, size_t size)
2937{
2938 internalPoolFree(defaultMemPool, object, size);
2939}
2940#endif
2941
2942/*
2943 * A variant that provides additional memory safety, by checking whether the given address
2944 * was obtained with this allocator, and if not redirecting to the provided alternative call.
2945 */
2946extern "C" void __TBB_malloc_safer_free(void *object, void (*original_free)(void*))
2947{
2948 if (!object)
2949 return;
2950
2951 // tbbmalloc can allocate object only when tbbmalloc has been initialized
2952 if (FencedLoad(mallocInitialized) && defaultMemPool->extMemPool.backend.ptrCanBeValid(object)) {
2953 if (isLargeObject<unknownMem>(object)) {
2954 // must check 1st for large object, because small object check touches 4 pages on left,
2955 // and it can be inaccessible
2956 TLSData *tls = defaultMemPool->getTLS(/*create=*/false);
2957
2958 defaultMemPool->putToLLOCache(tls, object);
2959 return;
2960 } else if (isSmallObject(object)) {
2961 freeSmallObject(object);
2962 return;
2963 }
2964 }
2965 if (original_free)
2966 original_free(object);
2967}
2968
2969/********* End the free code *************/
2970
2971/********* Code for scalable_realloc ***********/
2972
2973/*
2974 * From K&R
2975 * "realloc changes the size of the object pointed to by p to size. The contents will
2976 * be unchanged up to the minimum of the old and the new sizes. If the new size is larger,
2977 * the new space is uninitialized. realloc returns a pointer to the new space, or
2978 * NULL if the request cannot be satisfied, in which case *p is unchanged."
2979 *
2980 */
2981extern "C" void* scalable_realloc(void* ptr, size_t size)
2982{
2983 void *tmp;
2984
2985 if (!ptr)
2986 tmp = internalMalloc(size);
2987 else if (!size) {
2988 internalFree(ptr);
2989 return NULL;
2990 } else
2991 tmp = reallocAligned(defaultMemPool, ptr, size, 0);
2992
2993 if (!tmp) errno = ENOMEM;
2994 return tmp;
2995}
2996
2997/*
2998 * A variant that provides additional memory safety, by checking whether the given address
2999 * was obtained with this allocator, and if not redirecting to the provided alternative call.
3000 */
3001extern "C" void* __TBB_malloc_safer_realloc(void* ptr, size_t sz, void* original_realloc)
3002{
3003 void *tmp; // TODO: fix warnings about uninitialized use of tmp
3004
3005 if (!ptr) {
3006 tmp = internalMalloc(sz);
3007 } else if (FencedLoad(mallocInitialized) && isRecognized(ptr)) {
3008 if (!sz) {
3009 internalFree(ptr);
3010 return NULL;
3011 } else {
3012 tmp = reallocAligned(defaultMemPool, ptr, sz, 0);
3013 }
3014 }
3015#if USE_WINTHREAD
3016 else if (original_realloc && sz) {
3017 orig_ptrs *original_ptrs = static_cast<orig_ptrs*>(original_realloc);
3018 if ( original_ptrs->msize ){
3019 size_t oldSize = original_ptrs->msize(ptr);
3020 tmp = internalMalloc(sz);
3021 if (tmp) {
3022 memcpy(tmp, ptr, sz<oldSize? sz : oldSize);
3023 if ( original_ptrs->free ){
3024 original_ptrs->free( ptr );
3025 }
3026 }
3027 } else
3028 tmp = NULL;
3029 }
3030#else
3031 else if (original_realloc) {
3032 typedef void* (*realloc_ptr_t)(void*,size_t);
3033 realloc_ptr_t original_realloc_ptr;
3034 (void *&)original_realloc_ptr = original_realloc;
3035 tmp = original_realloc_ptr(ptr,sz);
3036 }
3037#endif
3038 else tmp = NULL;
3039
3040 if (!tmp) errno = ENOMEM;
3041 return tmp;
3042}
3043
3044/********* End code for scalable_realloc ***********/
3045
3046/********* Code for scalable_calloc ***********/
3047
3048/*
3049 * From K&R
3050 * calloc returns a pointer to space for an array of nobj objects,
3051 * each of size size, or NULL if the request cannot be satisfied.
3052 * The space is initialized to zero bytes.
3053 *
3054 */
3055
3056extern "C" void * scalable_calloc(size_t nobj, size_t size)
3057{
3058 // it's square root of maximal size_t value
3059 const size_t mult_not_overflow = size_t(1) << (sizeof(size_t)*CHAR_BIT/2);
3060 const size_t arraySize = nobj * size;
3061
3062 // check for overflow during multiplication:
3063 if (nobj>=mult_not_overflow || size>=mult_not_overflow) // 1) heuristic check
3064 if (nobj && arraySize / nobj != size) { // 2) exact check
3065 errno = ENOMEM;
3066 return NULL;
3067 }
3068 void* result = internalMalloc(arraySize);
3069 if (result)
3070 memset(result, 0, arraySize);
3071 else
3072 errno = ENOMEM;
3073 return result;
3074}
3075
3076/********* End code for scalable_calloc ***********/
3077
3078/********* Code for aligned allocation API **********/
3079
3080extern "C" int scalable_posix_memalign(void **memptr, size_t alignment, size_t size)
3081{
3082 if ( !isPowerOfTwoAtLeast(alignment, sizeof(void*)) )
3083 return EINVAL;
3084 void *result = allocateAligned(defaultMemPool, size, alignment);
3085 if (!result)
3086 return ENOMEM;
3087 *memptr = result;
3088 return 0;
3089}
3090
3091extern "C" void * scalable_aligned_malloc(size_t size, size_t alignment)
3092{
3093 if (!isPowerOfTwo(alignment) || 0==size) {
3094 errno = EINVAL;
3095 return NULL;
3096 }
3097 void *tmp = allocateAligned(defaultMemPool, size, alignment);
3098 if (!tmp) errno = ENOMEM;
3099 return tmp;
3100}
3101
3102extern "C" void * scalable_aligned_realloc(void *ptr, size_t size, size_t alignment)
3103{
3104 if (!isPowerOfTwo(alignment)) {
3105 errno = EINVAL;
3106 return NULL;
3107 }
3108 void *tmp;
3109
3110 if (!ptr)
3111 tmp = allocateAligned(defaultMemPool, size, alignment);
3112 else if (!size) {
3113 scalable_free(ptr);
3114 return NULL;
3115 } else
3116 tmp = reallocAligned(defaultMemPool, ptr, size, alignment);
3117
3118 if (!tmp) errno = ENOMEM;
3119 return tmp;
3120}
3121
3122extern "C" void * __TBB_malloc_safer_aligned_realloc(void *ptr, size_t size, size_t alignment, void* orig_function)
3123{
3124 /* corner cases left out of reallocAligned to not deal with errno there */
3125 if (!isPowerOfTwo(alignment)) {
3126 errno = EINVAL;
3127 return NULL;
3128 }
3129 void *tmp = NULL;
3130
3131 if (!ptr) {
3132 tmp = allocateAligned(defaultMemPool, size, alignment);
3133 } else if (FencedLoad(mallocInitialized) && isRecognized(ptr)) {
3134 if (!size) {
3135 internalFree(ptr);
3136 return NULL;
3137 } else {
3138 tmp = reallocAligned(defaultMemPool, ptr, size, alignment);
3139 }
3140 }
3141#if USE_WINTHREAD
3142 else {
3143 orig_aligned_ptrs *original_ptrs = static_cast<orig_aligned_ptrs*>(orig_function);
3144 if (size) {
3145 // Without orig_msize, we can't do anything with this.
3146 // Just keeping old pointer.
3147 if ( original_ptrs->aligned_msize ){
3148 // set alignment and offset to have possibly correct oldSize
3149 size_t oldSize = original_ptrs->aligned_msize(ptr, sizeof(void*), 0);
3150 tmp = allocateAligned(defaultMemPool, size, alignment);
3151 if (tmp) {
3152 memcpy(tmp, ptr, size<oldSize? size : oldSize);
3153 if ( original_ptrs->aligned_free ){
3154 original_ptrs->aligned_free( ptr );
3155 }
3156 }
3157 }
3158 } else {
3159 if ( original_ptrs->aligned_free ){
3160 original_ptrs->aligned_free( ptr );
3161 }
3162 return NULL;
3163 }
3164 }
3165#else
3166 // As original_realloc can't align result, and there is no way to find
3167 // size of reallocating object, we are giving up.
3168 suppress_unused_warning(orig_function);
3169#endif
3170 if (!tmp) errno = ENOMEM;
3171 return tmp;
3172}
3173
3174extern "C" void scalable_aligned_free(void *ptr)
3175{
3176 internalFree(ptr);
3177}
3178
3179/********* end code for aligned allocation API **********/
3180
3181/********* Code for scalable_msize ***********/
3182
3183/*
3184 * Returns the size of a memory block allocated in the heap.
3185 */
3186extern "C" size_t scalable_msize(void* ptr)
3187{
3188 if (ptr) {
3189 MALLOC_ASSERT(isRecognized(ptr), "Invalid pointer in scalable_msize detected.");
3190 return internalMsize(ptr);
3191 }
3192 errno = EINVAL;
3193 // Unlike _msize, return 0 in case of parameter error.
3194 // Returning size_t(-1) looks more like the way to troubles.
3195 return 0;
3196}
3197
3198/*
3199 * A variant that provides additional memory safety, by checking whether the given address
3200 * was obtained with this allocator, and if not redirecting to the provided alternative call.
3201 */
3202extern "C" size_t __TBB_malloc_safer_msize(void *object, size_t (*original_msize)(void*))
3203{
3204 if (object) {
3205 // Check if the memory was allocated by scalable_malloc
3206 if (FencedLoad(mallocInitialized) && isRecognized(object))
3207 return internalMsize(object);
3208 else if (original_msize)
3209 return original_msize(object);
3210 }
3211 // object is NULL or unknown, or foreign and no original_msize
3212#if USE_WINTHREAD
3213 errno = EINVAL; // errno expected to be set only on this platform
3214#endif
3215 return 0;
3216}
3217
3218/*
3219 * The same as above but for _aligned_msize case
3220 */
3221extern "C" size_t __TBB_malloc_safer_aligned_msize(void *object, size_t alignment, size_t offset, size_t (*orig_aligned_msize)(void*,size_t,size_t))
3222{
3223 if (object) {
3224 // Check if the memory was allocated by scalable_malloc
3225 if (FencedLoad(mallocInitialized) && isRecognized(object))
3226 return internalMsize(object);
3227 else if (orig_aligned_msize)
3228 return orig_aligned_msize(object,alignment,offset);
3229 }
3230 // object is NULL or unknown
3231 errno = EINVAL;
3232 return 0;
3233}
3234
3235/********* End code for scalable_msize ***********/
3236
3237extern "C" int scalable_allocation_mode(int param, intptr_t value)
3238{
3239 if (param == TBBMALLOC_SET_SOFT_HEAP_LIMIT) {
3240 defaultMemPool->extMemPool.backend.setRecommendedMaxSize((size_t)value);
3241 return TBBMALLOC_OK;
3242 } else if (param == USE_HUGE_PAGES) {
3243#if __linux__
3244 switch (value) {
3245 case 0:
3246 case 1:
3247 hugePages.setMode(value);
3248 return TBBMALLOC_OK;
3249 default:
3250 return TBBMALLOC_INVALID_PARAM;
3251 }
3252#else
3253 return TBBMALLOC_NO_EFFECT;
3254#endif
3255#if __TBB_SOURCE_DIRECTLY_INCLUDED
3256 } else if (param == TBBMALLOC_INTERNAL_SOURCE_INCLUDED) {
3257 switch (value) {
3258 case 0: // used by dynamic library
3259 case 1: // used by static library or directly included sources
3260 usedBySrcIncluded = value;
3261 return TBBMALLOC_OK;
3262 default:
3263 return TBBMALLOC_INVALID_PARAM;
3264 }
3265#endif
3266 } else if (param == TBBMALLOC_SET_HUGE_SIZE_THRESHOLD) {
3267 defaultMemPool->extMemPool.loc.setHugeSizeThreshold((size_t)value);
3268 return TBBMALLOC_OK;
3269 }
3270 return TBBMALLOC_INVALID_PARAM;
3271}
3272
3273extern "C" int scalable_allocation_command(int cmd, void *param)
3274{
3275 if (param)
3276 return TBBMALLOC_INVALID_PARAM;
3277
3278 bool released = false;
3279 switch(cmd) {
3280 case TBBMALLOC_CLEAN_THREAD_BUFFERS:
3281 if (TLSData *tls = defaultMemPool->getTLS(/*create=*/false))
3282 released = tls->externalCleanup(/*cleanOnlyUnused*/false, /*cleanBins=*/true);
3283 break;
3284 case TBBMALLOC_CLEAN_ALL_BUFFERS:
3285 released = defaultMemPool->extMemPool.hardCachesCleanup();
3286 break;
3287 default:
3288 return TBBMALLOC_INVALID_PARAM;
3289 }
3290 return released ? TBBMALLOC_OK : TBBMALLOC_NO_EFFECT;
3291}
3292