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#include <string.h> /* for memset */
18#include <errno.h>
19#include "tbbmalloc_internal.h"
20
21namespace rml {
22namespace internal {
23
24/*********** Code to acquire memory from the OS or other executive ****************/
25
26/*
27 syscall/malloc can set non-zero errno in case of failure,
28 but later allocator might be able to find memory to fulfill the request.
29 And we do not want changing of errno by successful scalable_malloc call.
30 To support this, restore old errno in (get|free)RawMemory, and set errno
31 in frontend just before returning to user code.
32 Please note: every syscall/libc call used inside scalable_malloc that
33 sets errno must be protected this way, not just memory allocation per se.
34*/
35
36#if USE_DEFAULT_MEMORY_MAPPING
37#include "MapMemory.h"
38#else
39/* assume MapMemory and UnmapMemory are customized */
40#endif
41
42void* getRawMemory (size_t size, PageType pageType) {
43 return MapMemory(size, pageType);
44}
45
46int freeRawMemory (void *object, size_t size) {
47 return UnmapMemory(object, size);
48}
49
50#if CHECK_ALLOCATION_RANGE
51
52void Backend::UsedAddressRange::registerAlloc(uintptr_t left, uintptr_t right)
53{
54 MallocMutex::scoped_lock lock(mutex);
55 if (left < leftBound)
56 leftBound = left;
57 if (right > rightBound)
58 rightBound = right;
59 MALLOC_ASSERT(leftBound, ASSERT_TEXT);
60 MALLOC_ASSERT(leftBound < rightBound, ASSERT_TEXT);
61 MALLOC_ASSERT(leftBound <= left && right <= rightBound, ASSERT_TEXT);
62}
63
64void Backend::UsedAddressRange::registerFree(uintptr_t left, uintptr_t right)
65{
66 MallocMutex::scoped_lock lock(mutex);
67 if (leftBound == left) {
68 if (rightBound == right) {
69 leftBound = ADDRESS_UPPER_BOUND;
70 rightBound = 0;
71 } else
72 leftBound = right;
73 } else if (rightBound == right)
74 rightBound = left;
75 MALLOC_ASSERT((!rightBound && leftBound == ADDRESS_UPPER_BOUND)
76 || leftBound < rightBound, ASSERT_TEXT);
77}
78#endif // CHECK_ALLOCATION_RANGE
79
80// Initialized in frontend inside defaultMemPool
81extern HugePagesStatus hugePages;
82
83void *Backend::allocRawMem(size_t &size)
84{
85 void *res = NULL;
86 size_t allocSize = 0;
87
88 if (extMemPool->userPool()) {
89 if (extMemPool->fixedPool && bootsrapMemDone == FencedLoad(bootsrapMemStatus))
90 return NULL;
91 MALLOC_ASSERT(bootsrapMemStatus != bootsrapMemNotDone,
92 "Backend::allocRawMem() called prematurely?");
93 // TODO: support for raw mem not aligned at sizeof(uintptr_t)
94 // memory from fixed pool is asked once and only once
95 allocSize = alignUpGeneric(size, extMemPool->granularity);
96 res = (*extMemPool->rawAlloc)(extMemPool->poolId, allocSize);
97 } else {
98 // Align allocation on page size
99 size_t pageSize = hugePages.isEnabled ? hugePages.getGranularity() : extMemPool->granularity;
100 MALLOC_ASSERT(pageSize, "Page size cannot be zero.");
101 allocSize = alignUpGeneric(size, pageSize);
102
103 // If user requested huge pages and they are available, try to use preallocated ones firstly.
104 // If there are none, lets check transparent huge pages support and use them instead.
105 if (hugePages.isEnabled) {
106 if (hugePages.isHPAvailable) {
107 res = getRawMemory(allocSize, PREALLOCATED_HUGE_PAGE);
108 }
109 if (!res && hugePages.isTHPAvailable) {
110 res = getRawMemory(allocSize, TRANSPARENT_HUGE_PAGE);
111 }
112 }
113
114 if (!res) {
115 res = getRawMemory(allocSize, REGULAR);
116 }
117 }
118
119 if (res) {
120 MALLOC_ASSERT(allocSize > 0, "Invalid size of an allocated region.");
121 size = allocSize;
122 if (!extMemPool->userPool())
123 usedAddrRange.registerAlloc((uintptr_t)res, (uintptr_t)res+size);
124#if MALLOC_DEBUG
125 volatile size_t curTotalSize = totalMemSize; // to read global value once
126 MALLOC_ASSERT(curTotalSize+size > curTotalSize, "Overflow allocation size.");
127#endif
128 AtomicAdd((intptr_t&)totalMemSize, size);
129 }
130
131 return res;
132}
133
134bool Backend::freeRawMem(void *object, size_t size)
135{
136 bool fail;
137#if MALLOC_DEBUG
138 volatile size_t curTotalSize = totalMemSize; // to read global value once
139 MALLOC_ASSERT(curTotalSize-size < curTotalSize, "Negative allocation size.");
140#endif
141 AtomicAdd((intptr_t&)totalMemSize, -size);
142 if (extMemPool->userPool()) {
143 MALLOC_ASSERT(!extMemPool->fixedPool, "No free for fixed-size pools.");
144 fail = (*extMemPool->rawFree)(extMemPool->poolId, object, size);
145 } else {
146 usedAddrRange.registerFree((uintptr_t)object, (uintptr_t)object + size);
147 fail = freeRawMemory(object, size);
148 }
149 // TODO: use result in all freeRawMem() callers
150 return !fail;
151}
152
153/********* End memory acquisition code ********************************/
154
155// Protected object size. After successful locking returns size of locked block,
156// and releasing requires setting block size.
157class GuardedSize : tbb::internal::no_copy {
158 uintptr_t value;
159public:
160 enum State {
161 LOCKED,
162 COAL_BLOCK, // block is coalescing now
163 MAX_LOCKED_VAL = COAL_BLOCK,
164 LAST_REGION_BLOCK, // used to mark last block in region
165 // values after this are "normal" block sizes
166 MAX_SPEC_VAL = LAST_REGION_BLOCK
167 };
168
169 void initLocked() { value = LOCKED; }
170 void makeCoalscing() {
171 MALLOC_ASSERT(value == LOCKED, ASSERT_TEXT);
172 value = COAL_BLOCK;
173 }
174 size_t tryLock(State state) {
175 size_t szVal, sz;
176 MALLOC_ASSERT(state <= MAX_LOCKED_VAL, ASSERT_TEXT);
177 for (;;) {
178 sz = FencedLoad((intptr_t&)value);
179 if (sz <= MAX_LOCKED_VAL)
180 break;
181 szVal = AtomicCompareExchange((intptr_t&)value, state, sz);
182
183 if (szVal==sz)
184 break;
185 }
186 return sz;
187 }
188 void unlock(size_t size) {
189 MALLOC_ASSERT(value <= MAX_LOCKED_VAL, "The lock is not locked");
190 MALLOC_ASSERT(size > MAX_LOCKED_VAL, ASSERT_TEXT);
191 FencedStore((intptr_t&)value, size);
192 }
193 bool isLastRegionBlock() const { return value==LAST_REGION_BLOCK; }
194 friend void Backend::IndexedBins::verify();
195};
196
197struct MemRegion {
198 MemRegion *next, // keep all regions in any pool to release all them on
199 *prev; // pool destroying, 2-linked list to release individual
200 // regions.
201 size_t allocSz, // got from pool callback
202 blockSz; // initial and maximal inner block size
203 MemRegionType type;
204};
205
206// this data must be unmodified while block is in use, so separate it
207class BlockMutexes {
208protected:
209 GuardedSize myL, // lock for me
210 leftL; // lock for left neighbor
211};
212
213class FreeBlock : BlockMutexes {
214public:
215 static const size_t minBlockSize;
216 friend void Backend::IndexedBins::verify();
217
218 FreeBlock *prev, // in 2-linked list related to bin
219 *next,
220 *nextToFree; // used to form a queue during coalescing
221 // valid only when block is in processing, i.e. one is not free and not
222 size_t sizeTmp; // used outside of backend
223 int myBin; // bin that is owner of the block
224 bool slabAligned;
225 bool blockInBin; // this block in myBin already
226
227 FreeBlock *rightNeig(size_t sz) const {
228 MALLOC_ASSERT(sz, ASSERT_TEXT);
229 return (FreeBlock*)((uintptr_t)this+sz);
230 }
231 FreeBlock *leftNeig(size_t sz) const {
232 MALLOC_ASSERT(sz, ASSERT_TEXT);
233 return (FreeBlock*)((uintptr_t)this - sz);
234 }
235
236 void initHeader() { myL.initLocked(); leftL.initLocked(); }
237 void setMeFree(size_t size) { myL.unlock(size); }
238 size_t trySetMeUsed(GuardedSize::State s) { return myL.tryLock(s); }
239 bool isLastRegionBlock() const { return myL.isLastRegionBlock(); }
240
241 void setLeftFree(size_t sz) { leftL.unlock(sz); }
242 size_t trySetLeftUsed(GuardedSize::State s) { return leftL.tryLock(s); }
243
244 size_t tryLockBlock() {
245 size_t rSz, sz = trySetMeUsed(GuardedSize::LOCKED);
246
247 if (sz <= GuardedSize::MAX_LOCKED_VAL)
248 return false;
249 rSz = rightNeig(sz)->trySetLeftUsed(GuardedSize::LOCKED);
250 if (rSz <= GuardedSize::MAX_LOCKED_VAL) {
251 setMeFree(sz);
252 return false;
253 }
254 MALLOC_ASSERT(rSz == sz, ASSERT_TEXT);
255 return sz;
256 }
257 void markCoalescing(size_t blockSz) {
258 myL.makeCoalscing();
259 rightNeig(blockSz)->leftL.makeCoalscing();
260 sizeTmp = blockSz;
261 nextToFree = NULL;
262 }
263 void markUsed() {
264 myL.initLocked();
265 rightNeig(sizeTmp)->leftL.initLocked();
266 nextToFree = NULL;
267 }
268 static void markBlocks(FreeBlock *fBlock, int num, size_t size) {
269 for (int i=1; i<num; i++) {
270 fBlock = (FreeBlock*)((uintptr_t)fBlock + size);
271 fBlock->initHeader();
272 }
273 }
274};
275
276// Last block in any region. Its "size" field is GuardedSize::LAST_REGION_BLOCK,
277// This kind of blocks used to find region header
278// and have a possibility to return region back to OS
279struct LastFreeBlock : public FreeBlock {
280 MemRegion *memRegion;
281};
282
283const size_t FreeBlock::minBlockSize = sizeof(FreeBlock);
284
285inline bool BackendSync::waitTillBlockReleased(intptr_t startModifiedCnt)
286{
287 AtomicBackoff backoff;
288#if __TBB_MALLOC_BACKEND_STAT
289 class ITT_Guard {
290 void *ptr;
291 public:
292 ITT_Guard(void *p) : ptr(p) {
293 MALLOC_ITT_SYNC_PREPARE(ptr);
294 }
295 ~ITT_Guard() {
296 MALLOC_ITT_SYNC_ACQUIRED(ptr);
297 }
298 };
299 ITT_Guard ittGuard(&inFlyBlocks);
300#endif
301 for (intptr_t myBinsInFlyBlocks = FencedLoad(inFlyBlocks),
302 myCoalescQInFlyBlocks = backend->blocksInCoalescing(); ;
303 backoff.pause()) {
304 MALLOC_ASSERT(myBinsInFlyBlocks>=0 && myCoalescQInFlyBlocks>=0, NULL);
305 intptr_t currBinsInFlyBlocks = FencedLoad(inFlyBlocks),
306 currCoalescQInFlyBlocks = backend->blocksInCoalescing();
307 WhiteboxTestingYield();
308 // Stop waiting iff:
309
310 // 1) blocks were removed from processing, not added
311 if (myBinsInFlyBlocks > currBinsInFlyBlocks
312 // 2) released during delayed coalescing queue
313 || myCoalescQInFlyBlocks > currCoalescQInFlyBlocks)
314 break;
315 // 3) if there are blocks in coalescing, and no progress in its processing,
316 // try to scan coalescing queue and stop waiting, if changes were made
317 // (if there are no changes and in-fly blocks exist, we continue
318 // waiting to not increase load on coalescQ)
319 if (currCoalescQInFlyBlocks > 0 && backend->scanCoalescQ(/*forceCoalescQDrop=*/false))
320 break;
321 // 4) when there are no blocks
322 if (!currBinsInFlyBlocks && !currCoalescQInFlyBlocks)
323 // re-scan make sense only if bins were modified since scanned
324 return startModifiedCnt != getNumOfMods();
325 myBinsInFlyBlocks = currBinsInFlyBlocks;
326 myCoalescQInFlyBlocks = currCoalescQInFlyBlocks;
327 }
328 return true;
329}
330
331void CoalRequestQ::putBlock(FreeBlock *fBlock)
332{
333 MALLOC_ASSERT(fBlock->sizeTmp >= FreeBlock::minBlockSize, ASSERT_TEXT);
334 fBlock->markUsed();
335 // the block is in the queue, do not forget that it's here
336 AtomicIncrement(inFlyBlocks);
337
338 for (;;) {
339 FreeBlock *myBlToFree = (FreeBlock*)FencedLoad((intptr_t&)blocksToFree);
340
341 fBlock->nextToFree = myBlToFree;
342 if (myBlToFree ==
343 (FreeBlock*)AtomicCompareExchange((intptr_t&)blocksToFree,
344 (intptr_t)fBlock,
345 (intptr_t)myBlToFree))
346 return;
347 }
348}
349
350FreeBlock *CoalRequestQ::getAll()
351{
352 for (;;) {
353 FreeBlock *myBlToFree = (FreeBlock*)FencedLoad((intptr_t&)blocksToFree);
354
355 if (!myBlToFree)
356 return NULL;
357 else {
358 if (myBlToFree ==
359 (FreeBlock*)AtomicCompareExchange((intptr_t&)blocksToFree,
360 0, (intptr_t)myBlToFree))
361 return myBlToFree;
362 else
363 continue;
364 }
365 }
366}
367
368inline void CoalRequestQ::blockWasProcessed()
369{
370 bkndSync->binsModified();
371 int prev = AtomicAdd(inFlyBlocks, -1);
372 MALLOC_ASSERT(prev > 0, ASSERT_TEXT);
373}
374
375// Try to get a block from a bin.
376// If the remaining free space would stay in the same bin,
377// split the block without removing it.
378// If the free space should go to other bin(s), remove the block.
379// alignedBin is true, if all blocks in the bin have slab-aligned right side.
380FreeBlock *Backend::IndexedBins::getFromBin(int binIdx, BackendSync *sync, size_t size,
381 bool needAlignedRes, bool alignedBin, bool wait, int *binLocked)
382{
383 Bin *b = &freeBins[binIdx];
384try_next:
385 FreeBlock *fBlock = NULL;
386 if (b->head) {
387 bool locked;
388 MallocMutex::scoped_lock scopedLock(b->tLock, wait, &locked);
389
390 if (!locked) {
391 if (binLocked) (*binLocked)++;
392 return NULL;
393 }
394
395 for (FreeBlock *curr = b->head; curr; curr = curr->next) {
396 size_t szBlock = curr->tryLockBlock();
397 if (!szBlock) {
398 // block is locked, re-do bin lock, as there is no place to spin
399 // while block coalescing
400 goto try_next;
401 }
402
403 // GENERAL CASE
404 if (alignedBin || !needAlignedRes) {
405 size_t splitSz = szBlock - size;
406 // If we got a block as split result, it must have a room for control structures.
407 if (szBlock >= size && (splitSz >= FreeBlock::minBlockSize || !splitSz))
408 fBlock = curr;
409 } else {
410 // SPECIAL CASE, to get aligned block from unaligned bin we have to cut the middle of a block
411 // and return remaining left and right part. Possible only in fixed pool scenario, assert for this
412 // is set inside splitBlock() function.
413
414 void *newB = alignUp(curr, slabSize);
415 uintptr_t rightNew = (uintptr_t)newB + size;
416 uintptr_t rightCurr = (uintptr_t)curr + szBlock;
417 // Check if the block size is sufficient,
418 // and also left and right split results are either big enough or non-existent
419 if (rightNew <= rightCurr
420 && (newB == curr || ((uintptr_t)newB - (uintptr_t)curr) >= FreeBlock::minBlockSize)
421 && (rightNew == rightCurr || (rightCurr - rightNew) >= FreeBlock::minBlockSize))
422 fBlock = curr;
423 }
424
425 if (fBlock) {
426 // consume must be called before result of removing from a bin is visible externally.
427 sync->blockConsumed();
428 // TODO: think about cases when block stays in the same bin
429 b->removeBlock(fBlock);
430 if (freeBins[binIdx].empty())
431 bitMask.set(binIdx, false);
432 fBlock->sizeTmp = szBlock;
433 break;
434 } else { // block size is not valid, search for next block in the bin
435 curr->setMeFree(szBlock);
436 curr->rightNeig(szBlock)->setLeftFree(szBlock);
437 }
438 }
439 }
440 return fBlock;
441}
442
443bool Backend::IndexedBins::tryReleaseRegions(int binIdx, Backend *backend)
444{
445 Bin *b = &freeBins[binIdx];
446 FreeBlock *fBlockList = NULL;
447
448 // got all blocks from the bin and re-do coalesce on them
449 // to release single-block regions
450try_next:
451 if (b->head) {
452 MallocMutex::scoped_lock binLock(b->tLock);
453 for (FreeBlock *curr = b->head; curr; ) {
454 size_t szBlock = curr->tryLockBlock();
455 if (!szBlock)
456 goto try_next;
457
458 FreeBlock *next = curr->next;
459
460 b->removeBlock(curr);
461 curr->sizeTmp = szBlock;
462 curr->nextToFree = fBlockList;
463 fBlockList = curr;
464 curr = next;
465 }
466 }
467 return backend->coalescAndPutList(fBlockList, /*forceCoalescQDrop=*/true,
468 /*reportBlocksProcessed=*/false);
469}
470
471void Backend::Bin::removeBlock(FreeBlock *fBlock)
472{
473 MALLOC_ASSERT(fBlock->next||fBlock->prev||fBlock==head,
474 "Detected that a block is not in the bin.");
475 if (head == fBlock)
476 head = fBlock->next;
477 if (tail == fBlock)
478 tail = fBlock->prev;
479 if (fBlock->prev)
480 fBlock->prev->next = fBlock->next;
481 if (fBlock->next)
482 fBlock->next->prev = fBlock->prev;
483}
484
485void Backend::IndexedBins::addBlock(int binIdx, FreeBlock *fBlock, size_t blockSz, bool addToTail)
486{
487 Bin *b = &freeBins[binIdx];
488 fBlock->myBin = binIdx;
489 fBlock->next = fBlock->prev = NULL;
490 {
491 MallocMutex::scoped_lock scopedLock(b->tLock);
492 if (addToTail) {
493 fBlock->prev = b->tail;
494 b->tail = fBlock;
495 if (fBlock->prev)
496 fBlock->prev->next = fBlock;
497 if (!b->head)
498 b->head = fBlock;
499 } else {
500 fBlock->next = b->head;
501 b->head = fBlock;
502 if (fBlock->next)
503 fBlock->next->prev = fBlock;
504 if (!b->tail)
505 b->tail = fBlock;
506 }
507 }
508 bitMask.set(binIdx, true);
509}
510
511bool Backend::IndexedBins::tryAddBlock(int binIdx, FreeBlock *fBlock, bool addToTail)
512{
513 bool locked;
514 Bin *b = &freeBins[binIdx];
515 fBlock->myBin = binIdx;
516 if (addToTail) {
517 fBlock->next = NULL;
518 {
519 MallocMutex::scoped_lock scopedLock(b->tLock, /*wait=*/false, &locked);
520 if (!locked)
521 return false;
522 fBlock->prev = b->tail;
523 b->tail = fBlock;
524 if (fBlock->prev)
525 fBlock->prev->next = fBlock;
526 if (!b->head)
527 b->head = fBlock;
528 }
529 } else {
530 fBlock->prev = NULL;
531 {
532 MallocMutex::scoped_lock scopedLock(b->tLock, /*wait=*/false, &locked);
533 if (!locked)
534 return false;
535 fBlock->next = b->head;
536 b->head = fBlock;
537 if (fBlock->next)
538 fBlock->next->prev = fBlock;
539 if (!b->tail)
540 b->tail = fBlock;
541 }
542 }
543 bitMask.set(binIdx, true);
544 return true;
545}
546
547void Backend::IndexedBins::reset()
548{
549 for (int i=0; i<Backend::freeBinsNum; i++)
550 freeBins[i].reset();
551 bitMask.reset();
552}
553
554void Backend::IndexedBins::lockRemoveBlock(int binIdx, FreeBlock *fBlock)
555{
556 MallocMutex::scoped_lock scopedLock(freeBins[binIdx].tLock);
557 freeBins[binIdx].removeBlock(fBlock);
558 if (freeBins[binIdx].empty())
559 bitMask.set(binIdx, false);
560}
561
562bool ExtMemoryPool::regionsAreReleaseable() const
563{
564 return !keepAllMemory && !delayRegsReleasing;
565}
566
567FreeBlock *Backend::splitBlock(FreeBlock *fBlock, int num, size_t size, bool blockIsAligned, bool needAlignedBlock)
568{
569 const size_t totalSize = num * size;
570
571 // SPECIAL CASE, for unaligned block we have to cut the middle of a block
572 // and return remaining left and right part. Possible only in a fixed pool scenario.
573 if (needAlignedBlock && !blockIsAligned) {
574 MALLOC_ASSERT(extMemPool->fixedPool,
575 "Aligned block request from unaligned bin possible only in fixed pool scenario.");
576
577 // Space to use is in the middle
578 FreeBlock *newBlock = alignUp(fBlock, slabSize);
579 FreeBlock *rightPart = (FreeBlock*)((uintptr_t)newBlock + totalSize);
580 uintptr_t fBlockEnd = (uintptr_t)fBlock + fBlock->sizeTmp;
581
582 // Return free right part
583 if ((uintptr_t)rightPart != fBlockEnd) {
584 rightPart->initHeader(); // to prevent coalescing rightPart with fBlock
585 size_t rightSize = fBlockEnd - (uintptr_t)rightPart;
586 coalescAndPut(rightPart, rightSize, toAlignedBin(rightPart, rightSize));
587 }
588 // And free left part
589 if (newBlock != fBlock) {
590 newBlock->initHeader(); // to prevent coalescing fBlock with newB
591 size_t leftSize = (uintptr_t)newBlock - (uintptr_t)fBlock;
592 coalescAndPut(fBlock, leftSize, toAlignedBin(fBlock, leftSize));
593 }
594 fBlock = newBlock;
595 } else if (size_t splitSize = fBlock->sizeTmp - totalSize) { // need to split the block
596 // GENERAL CASE, cut the left or right part of the block
597 FreeBlock *splitBlock = NULL;
598 if (needAlignedBlock) {
599 // For slab aligned blocks cut the right side of the block
600 // and return it to a requester, original block returns to backend
601 splitBlock = fBlock;
602 fBlock = (FreeBlock*)((uintptr_t)splitBlock + splitSize);
603 fBlock->initHeader();
604 } else {
605 // For large object blocks cut original block and put free righ part to backend
606 splitBlock = (FreeBlock*)((uintptr_t)fBlock + totalSize);
607 splitBlock->initHeader();
608 }
609 // Mark free block as it`s parent only when the requested type (needAlignedBlock)
610 // and returned from Bins/OS block (isAligned) are equal (XOR operation used)
611 bool markAligned = (blockIsAligned ^ needAlignedBlock) ? toAlignedBin(splitBlock, splitSize) : blockIsAligned;
612 coalescAndPut(splitBlock, splitSize, markAligned);
613 }
614 MALLOC_ASSERT(!needAlignedBlock || isAligned(fBlock, slabSize), "Expect to get aligned block, if one was requested.");
615 FreeBlock::markBlocks(fBlock, num, size);
616 return fBlock;
617}
618
619size_t Backend::getMaxBinnedSize() const
620{
621 return hugePages.isEnabled && !inUserPool() ?
622 maxBinned_HugePage : maxBinned_SmallPage;
623}
624
625inline bool Backend::MaxRequestComparator::operator()(size_t oldMaxReq, size_t requestSize) const
626{
627 return requestSize > oldMaxReq && requestSize < backend->getMaxBinnedSize();
628}
629
630// last chance to get memory
631FreeBlock *Backend::releaseMemInCaches(intptr_t startModifiedCnt,
632 int *lockedBinsThreshold, int numOfLockedBins)
633{
634 // something released from caches
635 if (extMemPool->hardCachesCleanup()
636 // ..or can use blocks that are in processing now
637 || bkndSync.waitTillBlockReleased(startModifiedCnt))
638 return (FreeBlock*)VALID_BLOCK_IN_BIN;
639 // OS can't give us more memory, but we have some in locked bins
640 if (*lockedBinsThreshold && numOfLockedBins) {
641 *lockedBinsThreshold = 0;
642 return (FreeBlock*)VALID_BLOCK_IN_BIN;
643 }
644 return NULL; // nothing found, give up
645}
646
647FreeBlock *Backend::askMemFromOS(size_t blockSize, intptr_t startModifiedCnt,
648 int *lockedBinsThreshold, int numOfLockedBins,
649 bool *splittableRet, bool needSlabRegion)
650{
651 FreeBlock *block;
652 // The block sizes can be divided into 3 groups:
653 // 1. "quite small": popular object size, we are in bootstarp or something
654 // like; request several regions.
655 // 2. "quite large": we want to have several such blocks in the region
656 // but not want several pre-allocated regions.
657 // 3. "huge": exact fit, we allocate only one block and do not allow
658 // any other allocations to placed in a region.
659 // Dividing the block sizes in these groups we are trying to balance between
660 // too small regions (that leads to fragmentation) and too large ones (that
661 // leads to excessive address space consumption). If a region is "too
662 // large", allocate only one, to prevent fragmentation. It supposedly
663 // doesn't hurt performance, because the object requested by user is large.
664 // Bounds for the groups are:
665 const size_t maxBinned = getMaxBinnedSize();
666 const size_t quiteSmall = maxBinned / 8;
667 const size_t quiteLarge = maxBinned;
668
669 if (blockSize >= quiteLarge) {
670 // Do not interact with other threads via semaphores, as for exact fit
671 // we can't share regions with them, memory requesting is individual.
672 block = addNewRegion(blockSize, MEMREG_ONE_BLOCK, /*addToBin=*/false);
673 if (!block)
674 return releaseMemInCaches(startModifiedCnt, lockedBinsThreshold, numOfLockedBins);
675 *splittableRet = false;
676 } else {
677 const size_t regSz_sizeBased = alignUp(4*maxRequestedSize, 1024*1024);
678 // Another thread is modifying backend while we can't get the block.
679 // Wait while it leaves and re-do the scan
680 // before trying other ways to extend the backend.
681 if (bkndSync.waitTillBlockReleased(startModifiedCnt)
682 // semaphore is protecting adding more more memory from OS
683 || memExtendingSema.wait())
684 return (FreeBlock*)VALID_BLOCK_IN_BIN;
685
686 if (startModifiedCnt != bkndSync.getNumOfMods()) {
687 memExtendingSema.signal();
688 return (FreeBlock*)VALID_BLOCK_IN_BIN;
689 }
690
691 if (blockSize < quiteSmall) {
692 // For this size of blocks, add NUM_OF_REG "advance" regions in bin,
693 // and return one as a result.
694 // TODO: add to bin first, because other threads can use them right away.
695 // This must be done carefully, because blocks in bins can be released
696 // in releaseCachesToLimit().
697 const unsigned NUM_OF_REG = 3;
698 MemRegionType regType = needSlabRegion ? MEMREG_SLAB_BLOCKS : MEMREG_LARGE_BLOCKS;
699 block = addNewRegion(regSz_sizeBased, regType, /*addToBin=*/false);
700 if (block)
701 for (unsigned idx=0; idx<NUM_OF_REG; idx++)
702 if (! addNewRegion(regSz_sizeBased, regType, /*addToBin=*/true))
703 break;
704 } else {
705 block = addNewRegion(regSz_sizeBased, MEMREG_LARGE_BLOCKS, /*addToBin=*/false);
706 }
707 memExtendingSema.signal();
708
709 // no regions found, try to clean cache
710 if (!block || block == (FreeBlock*)VALID_BLOCK_IN_BIN)
711 return releaseMemInCaches(startModifiedCnt, lockedBinsThreshold, numOfLockedBins);
712 // Since a region can hold more than one block it can be split.
713 *splittableRet = true;
714 }
715 // after asking memory from OS, release caches if we above the memory limits
716 releaseCachesToLimit();
717
718 return block;
719}
720
721void Backend::releaseCachesToLimit()
722{
723 if (!memSoftLimit || totalMemSize <= memSoftLimit)
724 return;
725 size_t locTotalMemSize, locMemSoftLimit;
726
727 scanCoalescQ(/*forceCoalescQDrop=*/false);
728 if (extMemPool->softCachesCleanup() &&
729 (locTotalMemSize = FencedLoad((intptr_t&)totalMemSize)) <=
730 (locMemSoftLimit = FencedLoad((intptr_t&)memSoftLimit)))
731 return;
732 // clean global large-object cache, if this is not enough, clean local caches
733 // do this in several tries, because backend fragmentation can prevent
734 // region from releasing
735 for (int cleanLocal = 0; cleanLocal<2; cleanLocal++)
736 while (cleanLocal ?
737 extMemPool->allLocalCaches.cleanup(/*cleanOnlyUnused=*/true) :
738 extMemPool->loc.decreasingCleanup())
739 if ((locTotalMemSize = FencedLoad((intptr_t&)totalMemSize)) <=
740 (locMemSoftLimit = FencedLoad((intptr_t&)memSoftLimit)))
741 return;
742 // last chance to match memSoftLimit
743 extMemPool->hardCachesCleanup();
744}
745
746int Backend::IndexedBins::getMinNonemptyBin(unsigned startBin) const
747{
748 int p = bitMask.getMinTrue(startBin);
749 return p == -1 ? Backend::freeBinsNum : p;
750}
751
752FreeBlock *Backend::IndexedBins::findBlock(int nativeBin, BackendSync *sync, size_t size,
753 bool needAlignedBlock, bool alignedBin, int *numOfLockedBins)
754{
755 for (int i=getMinNonemptyBin(nativeBin); i<freeBinsNum; i=getMinNonemptyBin(i+1))
756 if (FreeBlock *block = getFromBin(i, sync, size, needAlignedBlock, alignedBin, /*wait=*/false, numOfLockedBins))
757 return block;
758
759 return NULL;
760}
761
762void Backend::requestBootstrapMem()
763{
764 if (bootsrapMemDone == FencedLoad(bootsrapMemStatus))
765 return;
766 MallocMutex::scoped_lock lock( bootsrapMemStatusMutex );
767 if (bootsrapMemDone == bootsrapMemStatus)
768 return;
769 MALLOC_ASSERT(bootsrapMemNotDone == bootsrapMemStatus, ASSERT_TEXT);
770 bootsrapMemStatus = bootsrapMemInitializing;
771 // request some rather big region during bootstrap in advance
772 // ok to get NULL here, as later we re-do a request with more modest size
773 addNewRegion(2*1024*1024, MEMREG_SLAB_BLOCKS, /*addToBin=*/true);
774 bootsrapMemStatus = bootsrapMemDone;
775}
776
777// try to allocate size Byte block in available bins
778// needAlignedRes is true if result must be slab-aligned
779FreeBlock *Backend::genericGetBlock(int num, size_t size, bool needAlignedBlock)
780{
781 FreeBlock *block = NULL;
782 const size_t totalReqSize = num*size;
783 // no splitting after requesting new region, asks exact size
784 const int nativeBin = sizeToBin(totalReqSize);
785
786 requestBootstrapMem();
787 // If we found 2 or less locked bins, it's time to ask more memory from OS.
788 // But nothing can be asked from fixed pool. And we prefer wait, not ask
789 // for more memory, if block is quite large.
790 int lockedBinsThreshold = extMemPool->fixedPool || size>=maxBinned_SmallPage? 0 : 2;
791
792 // Find maximal requested size limited by getMaxBinnedSize()
793 AtomicUpdate(maxRequestedSize, totalReqSize, MaxRequestComparator(this));
794 scanCoalescQ(/*forceCoalescQDrop=*/false);
795
796 bool splittable = true;
797 for (;;) {
798 const intptr_t startModifiedCnt = bkndSync.getNumOfMods();
799 int numOfLockedBins;
800
801 do {
802 numOfLockedBins = 0;
803 if (needAlignedBlock) {
804 block = freeSlabAlignedBins.findBlock(nativeBin, &bkndSync, num*size, needAlignedBlock,
805 /*alignedBin=*/true, &numOfLockedBins);
806 if (!block && extMemPool->fixedPool)
807 block = freeLargeBlockBins.findBlock(nativeBin, &bkndSync, num*size, needAlignedBlock,
808 /*alignedBin=*/false, &numOfLockedBins);
809 } else {
810 block = freeLargeBlockBins.findBlock(nativeBin, &bkndSync, num*size, needAlignedBlock,
811 /*alignedBin=*/false, &numOfLockedBins);
812 if (!block && extMemPool->fixedPool)
813 block = freeSlabAlignedBins.findBlock(nativeBin, &bkndSync, num*size, needAlignedBlock,
814 /*alignedBin=*/true, &numOfLockedBins);
815 }
816 } while (!block && numOfLockedBins>lockedBinsThreshold);
817
818 if (block)
819 break;
820
821 if (!(scanCoalescQ(/*forceCoalescQDrop=*/true) | extMemPool->softCachesCleanup())) {
822 // bins are not updated,
823 // only remaining possibility is to ask for more memory
824 block = askMemFromOS(totalReqSize, startModifiedCnt, &lockedBinsThreshold,
825 numOfLockedBins, &splittable, needAlignedBlock);
826 if (!block)
827 return NULL;
828 if (block != (FreeBlock*)VALID_BLOCK_IN_BIN) {
829 // size can be increased in askMemFromOS, that's why >=
830 MALLOC_ASSERT(block->sizeTmp >= size, ASSERT_TEXT);
831 break;
832 }
833 // valid block somewhere in bins, let's find it
834 block = NULL;
835 }
836 }
837 MALLOC_ASSERT(block, ASSERT_TEXT);
838 if (splittable) {
839 // At this point we have to be sure that slabAligned attribute describes the right block state
840 block = splitBlock(block, num, size, block->slabAligned, needAlignedBlock);
841 }
842 // matched blockConsumed() from startUseBlock()
843 bkndSync.blockReleased();
844
845 return block;
846}
847
848LargeMemoryBlock *Backend::getLargeBlock(size_t size)
849{
850 LargeMemoryBlock *lmb =
851 (LargeMemoryBlock*)genericGetBlock(1, size, /*needAlignedRes=*/false);
852 if (lmb) {
853 lmb->unalignedSize = size;
854 if (extMemPool->userPool())
855 extMemPool->lmbList.add(lmb);
856 }
857 return lmb;
858}
859
860BlockI *Backend::getSlabBlock(int num) {
861 BlockI *b = (BlockI*)genericGetBlock(num, slabSize, /*slabAligned=*/true);
862 MALLOC_ASSERT(isAligned(b, slabSize), ASSERT_TEXT);
863 return b;
864}
865
866void Backend::putSlabBlock(BlockI *block) {
867 genericPutBlock((FreeBlock *)block, slabSize, /*slabAligned=*/true);
868}
869
870void *Backend::getBackRefSpace(size_t size, bool *rawMemUsed)
871{
872 // This block is released only at shutdown, so it can prevent
873 // a entire region releasing when it's received from the backend,
874 // so prefer getRawMemory using.
875 if (void *ret = getRawMemory(size, REGULAR)) {
876 *rawMemUsed = true;
877 return ret;
878 }
879 void *ret = genericGetBlock(1, size, /*needAlignedRes=*/false);
880 if (ret) *rawMemUsed = false;
881 return ret;
882}
883
884void Backend::putBackRefSpace(void *b, size_t size, bool rawMemUsed)
885{
886 if (rawMemUsed)
887 freeRawMemory(b, size);
888 // ignore not raw mem, as it released on region releasing
889}
890
891void Backend::removeBlockFromBin(FreeBlock *fBlock)
892{
893 if (fBlock->myBin != Backend::NO_BIN) {
894 if (fBlock->slabAligned)
895 freeSlabAlignedBins.lockRemoveBlock(fBlock->myBin, fBlock);
896 else
897 freeLargeBlockBins.lockRemoveBlock(fBlock->myBin, fBlock);
898 }
899}
900
901void Backend::genericPutBlock(FreeBlock *fBlock, size_t blockSz, bool slabAligned)
902{
903 bkndSync.blockConsumed();
904 coalescAndPut(fBlock, blockSz, slabAligned);
905 bkndSync.blockReleased();
906}
907
908void AllLargeBlocksList::add(LargeMemoryBlock *lmb)
909{
910 MallocMutex::scoped_lock scoped_cs(largeObjLock);
911 lmb->gPrev = NULL;
912 lmb->gNext = loHead;
913 if (lmb->gNext)
914 lmb->gNext->gPrev = lmb;
915 loHead = lmb;
916}
917
918void AllLargeBlocksList::remove(LargeMemoryBlock *lmb)
919{
920 MallocMutex::scoped_lock scoped_cs(largeObjLock);
921 if (loHead == lmb)
922 loHead = lmb->gNext;
923 if (lmb->gNext)
924 lmb->gNext->gPrev = lmb->gPrev;
925 if (lmb->gPrev)
926 lmb->gPrev->gNext = lmb->gNext;
927}
928
929void Backend::putLargeBlock(LargeMemoryBlock *lmb)
930{
931 if (extMemPool->userPool())
932 extMemPool->lmbList.remove(lmb);
933 genericPutBlock((FreeBlock *)lmb, lmb->unalignedSize, false);
934}
935
936void Backend::returnLargeObject(LargeMemoryBlock *lmb)
937{
938 removeBackRef(lmb->backRefIdx);
939 putLargeBlock(lmb);
940 STAT_increment(getThreadId(), ThreadCommonCounters, freeLargeObj);
941}
942
943#if BACKEND_HAS_MREMAP
944void *Backend::remap(void *ptr, size_t oldSize, size_t newSize, size_t alignment)
945{
946 // no remap for user pools and for object too small that living in bins
947 if (inUserPool() || min(oldSize, newSize)<maxBinned_SmallPage
948 // during remap, can't guarantee alignment more strict than current or
949 // more strict than page alignment
950 || !isAligned(ptr, alignment) || alignment>extMemPool->granularity)
951 return NULL;
952 const LargeMemoryBlock* lmbOld = ((LargeObjectHdr *)ptr - 1)->memoryBlock;
953 const size_t oldUnalignedSize = lmbOld->unalignedSize;
954 FreeBlock *oldFBlock = (FreeBlock *)lmbOld;
955 FreeBlock *right = oldFBlock->rightNeig(oldUnalignedSize);
956 // in every region only one block can have LAST_REGION_BLOCK on right,
957 // so don't need no synchronization
958 if (!right->isLastRegionBlock())
959 return NULL;
960
961 MemRegion *oldRegion = static_cast<LastFreeBlock*>(right)->memRegion;
962 MALLOC_ASSERT( oldRegion < ptr, ASSERT_TEXT );
963 const size_t oldRegionSize = oldRegion->allocSz;
964 if (oldRegion->type != MEMREG_ONE_BLOCK)
965 return NULL; // we are not single in the region
966 const size_t userOffset = (uintptr_t)ptr - (uintptr_t)oldRegion;
967 const size_t alignedSize = LargeObjectCache::alignToBin(newSize + userOffset);
968 const size_t requestSize =
969 alignUp(sizeof(MemRegion) + alignedSize + sizeof(LastFreeBlock), extMemPool->granularity);
970 if (requestSize < alignedSize) // is wrapped around?
971 return NULL;
972 regionList.remove(oldRegion);
973
974 void *ret = mremap(oldRegion, oldRegion->allocSz, requestSize, MREMAP_MAYMOVE);
975 if (MAP_FAILED == ret) { // can't remap, revert and leave
976 regionList.add(oldRegion);
977 return NULL;
978 }
979 MemRegion *region = (MemRegion*)ret;
980 MALLOC_ASSERT(region->type == MEMREG_ONE_BLOCK, ASSERT_TEXT);
981 region->allocSz = requestSize;
982 region->blockSz = alignedSize;
983
984 FreeBlock *fBlock = (FreeBlock *)alignUp((uintptr_t)region + sizeof(MemRegion),
985 largeObjectAlignment);
986
987 regionList.add(region);
988 startUseBlock(region, fBlock, /*addToBin=*/false);
989 MALLOC_ASSERT(fBlock->sizeTmp == region->blockSz, ASSERT_TEXT);
990 // matched blockConsumed() in startUseBlock().
991 // TODO: get rid of useless pair blockConsumed()/blockReleased()
992 bkndSync.blockReleased();
993
994 // object must start at same offset from region's start
995 void *object = (void*)((uintptr_t)region + userOffset);
996 MALLOC_ASSERT(isAligned(object, alignment), ASSERT_TEXT);
997 LargeObjectHdr *header = (LargeObjectHdr*)object - 1;
998 setBackRef(header->backRefIdx, header);
999
1000 LargeMemoryBlock *lmb = (LargeMemoryBlock*)fBlock;
1001 lmb->unalignedSize = region->blockSz;
1002 lmb->objectSize = newSize;
1003 lmb->backRefIdx = header->backRefIdx;
1004 header->memoryBlock = lmb;
1005 MALLOC_ASSERT((uintptr_t)lmb + lmb->unalignedSize >=
1006 (uintptr_t)object + lmb->objectSize, "An object must fit to the block.");
1007
1008 usedAddrRange.registerFree((uintptr_t)oldRegion, (uintptr_t)oldRegion + oldRegionSize);
1009 usedAddrRange.registerAlloc((uintptr_t)region, (uintptr_t)region + requestSize);
1010 AtomicAdd((intptr_t&)totalMemSize, region->allocSz - oldRegionSize);
1011
1012 return object;
1013}
1014#endif /* BACKEND_HAS_MREMAP */
1015
1016void Backend::releaseRegion(MemRegion *memRegion)
1017{
1018 regionList.remove(memRegion);
1019 freeRawMem(memRegion, memRegion->allocSz);
1020}
1021
1022// coalesce fBlock with its neighborhood
1023FreeBlock *Backend::doCoalesc(FreeBlock *fBlock, MemRegion **mRegion)
1024{
1025 FreeBlock *resBlock = fBlock;
1026 size_t resSize = fBlock->sizeTmp;
1027 MemRegion *memRegion = NULL;
1028
1029 fBlock->markCoalescing(resSize);
1030 resBlock->blockInBin = false;
1031
1032 // coalescing with left neighbor
1033 size_t leftSz = fBlock->trySetLeftUsed(GuardedSize::COAL_BLOCK);
1034 if (leftSz != GuardedSize::LOCKED) {
1035 if (leftSz == GuardedSize::COAL_BLOCK) {
1036 coalescQ.putBlock(fBlock);
1037 return NULL;
1038 } else {
1039 FreeBlock *left = fBlock->leftNeig(leftSz);
1040 size_t lSz = left->trySetMeUsed(GuardedSize::COAL_BLOCK);
1041 if (lSz <= GuardedSize::MAX_LOCKED_VAL) {
1042 fBlock->setLeftFree(leftSz); // rollback
1043 coalescQ.putBlock(fBlock);
1044 return NULL;
1045 } else {
1046 MALLOC_ASSERT(lSz == leftSz, "Invalid header");
1047 left->blockInBin = true;
1048 resBlock = left;
1049 resSize += leftSz;
1050 resBlock->sizeTmp = resSize;
1051 }
1052 }
1053 }
1054 // coalescing with right neighbor
1055 FreeBlock *right = fBlock->rightNeig(fBlock->sizeTmp);
1056 size_t rightSz = right->trySetMeUsed(GuardedSize::COAL_BLOCK);
1057 if (rightSz != GuardedSize::LOCKED) {
1058 // LastFreeBlock is on the right side
1059 if (GuardedSize::LAST_REGION_BLOCK == rightSz) {
1060 right->setMeFree(GuardedSize::LAST_REGION_BLOCK);
1061 memRegion = static_cast<LastFreeBlock*>(right)->memRegion;
1062 } else if (GuardedSize::COAL_BLOCK == rightSz) {
1063 if (resBlock->blockInBin) {
1064 resBlock->blockInBin = false;
1065 removeBlockFromBin(resBlock);
1066 }
1067 coalescQ.putBlock(resBlock);
1068 return NULL;
1069 } else {
1070 size_t rSz = right->rightNeig(rightSz)->
1071 trySetLeftUsed(GuardedSize::COAL_BLOCK);
1072 if (rSz <= GuardedSize::MAX_LOCKED_VAL) {
1073 right->setMeFree(rightSz); // rollback
1074 if (resBlock->blockInBin) {
1075 resBlock->blockInBin = false;
1076 removeBlockFromBin(resBlock);
1077 }
1078 coalescQ.putBlock(resBlock);
1079 return NULL;
1080 } else {
1081 MALLOC_ASSERT(rSz == rightSz, "Invalid header");
1082 removeBlockFromBin(right);
1083 resSize += rightSz;
1084
1085 // Is LastFreeBlock on the right side of right?
1086 FreeBlock *nextRight = right->rightNeig(rightSz);
1087 size_t nextRightSz = nextRight->
1088 trySetMeUsed(GuardedSize::COAL_BLOCK);
1089 if (nextRightSz > GuardedSize::MAX_LOCKED_VAL) {
1090 if (nextRightSz == GuardedSize::LAST_REGION_BLOCK)
1091 memRegion = static_cast<LastFreeBlock*>(nextRight)->memRegion;
1092
1093 nextRight->setMeFree(nextRightSz);
1094 }
1095 }
1096 }
1097 }
1098 if (memRegion) {
1099 MALLOC_ASSERT((uintptr_t)memRegion + memRegion->allocSz >=
1100 (uintptr_t)right + sizeof(LastFreeBlock), ASSERT_TEXT);
1101 MALLOC_ASSERT((uintptr_t)memRegion < (uintptr_t)resBlock, ASSERT_TEXT);
1102 *mRegion = memRegion;
1103 } else
1104 *mRegion = NULL;
1105 resBlock->sizeTmp = resSize;
1106 return resBlock;
1107}
1108
1109bool Backend::coalescAndPutList(FreeBlock *list, bool forceCoalescQDrop, bool reportBlocksProcessed)
1110{
1111 bool regionReleased = false;
1112
1113 for (FreeBlock *helper; list;
1114 list = helper,
1115 // matches block enqueue in CoalRequestQ::putBlock()
1116 reportBlocksProcessed? coalescQ.blockWasProcessed() : (void)0) {
1117 MemRegion *memRegion;
1118 bool addToTail = false;
1119
1120 helper = list->nextToFree;
1121 FreeBlock *toRet = doCoalesc(list, &memRegion);
1122 if (!toRet)
1123 continue;
1124
1125 if (memRegion && memRegion->blockSz == toRet->sizeTmp
1126 && !extMemPool->fixedPool) {
1127 if (extMemPool->regionsAreReleaseable()) {
1128 // release the region, because there is no used blocks in it
1129 if (toRet->blockInBin)
1130 removeBlockFromBin(toRet);
1131 releaseRegion(memRegion);
1132 regionReleased = true;
1133 continue;
1134 } else // add block from empty region to end of bin,
1135 addToTail = true; // preserving for exact fit
1136 }
1137 size_t currSz = toRet->sizeTmp;
1138 int bin = sizeToBin(currSz);
1139 bool toAligned = extMemPool->fixedPool ? toAlignedBin(toRet, currSz) : toRet->slabAligned;
1140 bool needAddToBin = true;
1141
1142 if (toRet->blockInBin) {
1143 // Does it stay in same bin?
1144 if (toRet->myBin == bin && toRet->slabAligned == toAligned)
1145 needAddToBin = false;
1146 else {
1147 toRet->blockInBin = false;
1148 removeBlockFromBin(toRet);
1149 }
1150 }
1151
1152 // Does not stay in same bin, or bin-less; add it
1153 if (needAddToBin) {
1154 toRet->prev = toRet->next = toRet->nextToFree = NULL;
1155 toRet->myBin = NO_BIN;
1156 toRet->slabAligned = toAligned;
1157
1158 // If the block is too small to fit in any bin, keep it bin-less.
1159 // It's not a leak because the block later can be coalesced.
1160 if (currSz >= minBinnedSize) {
1161 toRet->sizeTmp = currSz;
1162 IndexedBins *target = toRet->slabAligned ? &freeSlabAlignedBins : &freeLargeBlockBins;
1163 if (forceCoalescQDrop) {
1164 target->addBlock(bin, toRet, toRet->sizeTmp, addToTail);
1165 } else if (!target->tryAddBlock(bin, toRet, addToTail)) {
1166 coalescQ.putBlock(toRet);
1167 continue;
1168 }
1169 }
1170 toRet->sizeTmp = 0;
1171 }
1172 // Free (possibly coalesced) free block.
1173 // Adding to bin must be done before this point,
1174 // because after a block is free it can be coalesced, and
1175 // using its pointer became unsafe.
1176 // Remember that coalescing is not done under any global lock.
1177 toRet->setMeFree(currSz);
1178 toRet->rightNeig(currSz)->setLeftFree(currSz);
1179 }
1180 return regionReleased;
1181}
1182
1183// Coalesce fBlock and add it back to a bin;
1184// processing delayed coalescing requests.
1185void Backend::coalescAndPut(FreeBlock *fBlock, size_t blockSz, bool slabAligned)
1186{
1187 fBlock->sizeTmp = blockSz;
1188 fBlock->nextToFree = NULL;
1189 fBlock->slabAligned = slabAligned;
1190
1191 coalescAndPutList(fBlock, /*forceCoalescQDrop=*/false, /*reportBlocksProcessed=*/false);
1192}
1193
1194bool Backend::scanCoalescQ(bool forceCoalescQDrop)
1195{
1196 FreeBlock *currCoalescList = coalescQ.getAll();
1197
1198 if (currCoalescList)
1199 // reportBlocksProcessed=true informs that the blocks leave coalescQ,
1200 // matches blockConsumed() from CoalRequestQ::putBlock()
1201 coalescAndPutList(currCoalescList, forceCoalescQDrop,
1202 /*reportBlocksProcessed=*/true);
1203 // returns status of coalescQ.getAll(), as an indication of possible changes in backend
1204 // TODO: coalescAndPutList() may report is some new free blocks became available or not
1205 return currCoalescList;
1206}
1207
1208FreeBlock *Backend::findBlockInRegion(MemRegion *region, size_t exactBlockSize)
1209{
1210 FreeBlock *fBlock;
1211 size_t blockSz;
1212 uintptr_t fBlockEnd,
1213 lastFreeBlock = (uintptr_t)region + region->allocSz - sizeof(LastFreeBlock);
1214
1215 MALLOC_STATIC_ASSERT(sizeof(LastFreeBlock) % sizeof(uintptr_t) == 0,
1216 "Atomic applied on LastFreeBlock, and we put it at the end of region, that"
1217 " is uintptr_t-aligned, so no unaligned atomic operations are possible.");
1218 // right bound is slab-aligned, keep LastFreeBlock after it
1219 if (region->type == MEMREG_SLAB_BLOCKS) {
1220 fBlock = (FreeBlock *)alignUp((uintptr_t)region + sizeof(MemRegion), sizeof(uintptr_t));
1221 fBlockEnd = alignDown(lastFreeBlock, slabSize);
1222 } else {
1223 fBlock = (FreeBlock *)alignUp((uintptr_t)region + sizeof(MemRegion), largeObjectAlignment);
1224 fBlockEnd = (uintptr_t)fBlock + exactBlockSize;
1225 MALLOC_ASSERT(fBlockEnd <= lastFreeBlock, ASSERT_TEXT);
1226 }
1227 if (fBlockEnd <= (uintptr_t)fBlock)
1228 return NULL; // allocSz is too small
1229 blockSz = fBlockEnd - (uintptr_t)fBlock;
1230 // TODO: extend getSlabBlock to support degradation, i.e. getting less blocks
1231 // then requested, and then relax this check
1232 // (now all or nothing is implemented, check according to this)
1233 if (blockSz < numOfSlabAllocOnMiss*slabSize)
1234 return NULL;
1235
1236 region->blockSz = blockSz;
1237 return fBlock;
1238}
1239
1240// startUseBlock may add the free block to a bin, the block can be used and
1241// even released after this, so the region must be added to regionList already
1242void Backend::startUseBlock(MemRegion *region, FreeBlock *fBlock, bool addToBin)
1243{
1244 size_t blockSz = region->blockSz;
1245 fBlock->initHeader();
1246 fBlock->setMeFree(blockSz);
1247
1248 LastFreeBlock *lastBl = static_cast<LastFreeBlock*>(fBlock->rightNeig(blockSz));
1249 // to not get unaligned atomics during LastFreeBlock access
1250 MALLOC_ASSERT(isAligned(lastBl, sizeof(uintptr_t)), NULL);
1251 lastBl->initHeader();
1252 lastBl->setMeFree(GuardedSize::LAST_REGION_BLOCK);
1253 lastBl->setLeftFree(blockSz);
1254 lastBl->myBin = NO_BIN;
1255 lastBl->memRegion = region;
1256
1257 if (addToBin) {
1258 unsigned targetBin = sizeToBin(blockSz);
1259 // during adding advance regions, register bin for a largest block in region
1260 advRegBins.registerBin(targetBin);
1261 if (region->type == MEMREG_SLAB_BLOCKS) {
1262 fBlock->slabAligned = true;
1263 freeSlabAlignedBins.addBlock(targetBin, fBlock, blockSz, /*addToTail=*/false);
1264 } else {
1265 fBlock->slabAligned = false;
1266 freeLargeBlockBins.addBlock(targetBin, fBlock, blockSz, /*addToTail=*/false);
1267 }
1268 } else {
1269 // to match with blockReleased() in genericGetBlock
1270 bkndSync.blockConsumed();
1271 // Understand our alignment for correct splitBlock operation
1272 fBlock->slabAligned = region->type == MEMREG_SLAB_BLOCKS ? true : false;
1273 fBlock->sizeTmp = fBlock->tryLockBlock();
1274 MALLOC_ASSERT(fBlock->sizeTmp >= FreeBlock::minBlockSize, "Locking must be successful");
1275 }
1276}
1277
1278void MemRegionList::add(MemRegion *r)
1279{
1280 r->prev = NULL;
1281 MallocMutex::scoped_lock lock(regionListLock);
1282 r->next = head;
1283 head = r;
1284 if (head->next)
1285 head->next->prev = head;
1286}
1287
1288void MemRegionList::remove(MemRegion *r)
1289{
1290 MallocMutex::scoped_lock lock(regionListLock);
1291 if (head == r)
1292 head = head->next;
1293 if (r->next)
1294 r->next->prev = r->prev;
1295 if (r->prev)
1296 r->prev->next = r->next;
1297}
1298
1299#if __TBB_MALLOC_BACKEND_STAT
1300int MemRegionList::reportStat(FILE *f)
1301{
1302 int regNum = 0;
1303 MallocMutex::scoped_lock lock(regionListLock);
1304 for (MemRegion *curr = head; curr; curr = curr->next) {
1305 fprintf(f, "%p: max block %lu B, ", curr, curr->blockSz);
1306 regNum++;
1307 }
1308 return regNum;
1309}
1310#endif
1311
1312FreeBlock *Backend::addNewRegion(size_t size, MemRegionType memRegType, bool addToBin)
1313{
1314 MALLOC_STATIC_ASSERT(sizeof(BlockMutexes) <= sizeof(BlockI),
1315 "Header must be not overwritten in used blocks");
1316 MALLOC_ASSERT(FreeBlock::minBlockSize > GuardedSize::MAX_SPEC_VAL,
1317 "Block length must not conflict with special values of GuardedSize");
1318 // If the region is not "for slabs" we should reserve some space for
1319 // a region header, the worst case alignment and the last block mark.
1320 const size_t requestSize = memRegType == MEMREG_SLAB_BLOCKS ? size :
1321 size + sizeof(MemRegion) + largeObjectAlignment
1322 + FreeBlock::minBlockSize + sizeof(LastFreeBlock);
1323
1324 size_t rawSize = requestSize;
1325 MemRegion *region = (MemRegion*)allocRawMem(rawSize);
1326 if (!region) {
1327 MALLOC_ASSERT(rawSize==requestSize, "getRawMem has not allocated memory but changed the allocated size.");
1328 return NULL;
1329 }
1330 if (rawSize < sizeof(MemRegion)) {
1331 if (!extMemPool->fixedPool)
1332 freeRawMem(region, rawSize);
1333 return NULL;
1334 }
1335
1336 region->type = memRegType;
1337 region->allocSz = rawSize;
1338 FreeBlock *fBlock = findBlockInRegion(region, size);
1339 if (!fBlock) {
1340 if (!extMemPool->fixedPool)
1341 freeRawMem(region, rawSize);
1342 return NULL;
1343 }
1344 regionList.add(region);
1345 startUseBlock(region, fBlock, addToBin);
1346 bkndSync.binsModified();
1347 return addToBin? (FreeBlock*)VALID_BLOCK_IN_BIN : fBlock;
1348}
1349
1350void Backend::init(ExtMemoryPool *extMemoryPool)
1351{
1352 extMemPool = extMemoryPool;
1353 usedAddrRange.init();
1354 coalescQ.init(&bkndSync);
1355 bkndSync.init(this);
1356}
1357
1358void Backend::reset()
1359{
1360 MALLOC_ASSERT(extMemPool->userPool(), "Only user pool can be reset.");
1361 // no active threads are allowed in backend while reset() called
1362 verify();
1363
1364 freeLargeBlockBins.reset();
1365 freeSlabAlignedBins.reset();
1366 advRegBins.reset();
1367
1368 for (MemRegion *curr = regionList.head; curr; curr = curr->next) {
1369 FreeBlock *fBlock = findBlockInRegion(curr, curr->blockSz);
1370 MALLOC_ASSERT(fBlock, "A memory region unexpectedly got smaller");
1371 startUseBlock(curr, fBlock, /*addToBin=*/true);
1372 }
1373}
1374
1375bool Backend::destroy()
1376{
1377 bool noError = true;
1378 // no active threads are allowed in backend while destroy() called
1379 verify();
1380 if (!inUserPool()) {
1381 freeLargeBlockBins.reset();
1382 freeSlabAlignedBins.reset();
1383 }
1384 while (regionList.head) {
1385 MemRegion *helper = regionList.head->next;
1386 noError &= freeRawMem(regionList.head, regionList.head->allocSz);
1387 regionList.head = helper;
1388 }
1389 return noError;
1390}
1391
1392bool Backend::clean()
1393{
1394 scanCoalescQ(/*forceCoalescQDrop=*/false);
1395
1396 bool res = false;
1397 // We can have several blocks occupying a whole region,
1398 // because such regions are added in advance (see askMemFromOS() and reset()),
1399 // and never used. Release them all.
1400 for (int i = advRegBins.getMinUsedBin(0); i != -1; i = advRegBins.getMinUsedBin(i+1)) {
1401 if (i == freeSlabAlignedBins.getMinNonemptyBin(i))
1402 res |= freeSlabAlignedBins.tryReleaseRegions(i, this);
1403 if (i == freeLargeBlockBins.getMinNonemptyBin(i))
1404 res |= freeLargeBlockBins.tryReleaseRegions(i, this);
1405 }
1406
1407 return res;
1408}
1409
1410void Backend::IndexedBins::verify()
1411{
1412 for (int i=0; i<freeBinsNum; i++) {
1413 for (FreeBlock *fb = freeBins[i].head; fb; fb=fb->next) {
1414 uintptr_t mySz = fb->myL.value;
1415 MALLOC_ASSERT(mySz>GuardedSize::MAX_SPEC_VAL, ASSERT_TEXT);
1416 FreeBlock *right = (FreeBlock*)((uintptr_t)fb + mySz);
1417 suppress_unused_warning(right);
1418 MALLOC_ASSERT(right->myL.value<=GuardedSize::MAX_SPEC_VAL, ASSERT_TEXT);
1419 MALLOC_ASSERT(right->leftL.value==mySz, ASSERT_TEXT);
1420 MALLOC_ASSERT(fb->leftL.value<=GuardedSize::MAX_SPEC_VAL, ASSERT_TEXT);
1421 }
1422 }
1423}
1424
1425// For correct operation, it must be called when no other threads
1426// is changing backend.
1427void Backend::verify()
1428{
1429#if MALLOC_DEBUG
1430 scanCoalescQ(/*forceCoalescQDrop=*/false);
1431
1432 freeLargeBlockBins.verify();
1433 freeSlabAlignedBins.verify();
1434#endif // MALLOC_DEBUG
1435}
1436
1437#if __TBB_MALLOC_BACKEND_STAT
1438size_t Backend::Bin::countFreeBlocks()
1439{
1440 size_t cnt = 0;
1441 {
1442 MallocMutex::scoped_lock lock(tLock);
1443 for (FreeBlock *fb = head; fb; fb = fb->next)
1444 cnt++;
1445 }
1446 return cnt;
1447}
1448
1449size_t Backend::Bin::reportFreeBlocks(FILE *f)
1450{
1451 size_t totalSz = 0;
1452 MallocMutex::scoped_lock lock(tLock);
1453 for (FreeBlock *fb = head; fb; fb = fb->next) {
1454 size_t sz = fb->tryLockBlock();
1455 fb->setMeFree(sz);
1456 fprintf(f, " [%p;%p]", fb, (void*)((uintptr_t)fb+sz));
1457 totalSz += sz;
1458 }
1459 return totalSz;
1460}
1461
1462void Backend::IndexedBins::reportStat(FILE *f)
1463{
1464 size_t totalSize = 0;
1465
1466 for (int i=0; i<Backend::freeBinsNum; i++)
1467 if (size_t cnt = freeBins[i].countFreeBlocks()) {
1468 totalSize += freeBins[i].reportFreeBlocks(f);
1469 fprintf(f, " %d:%lu, ", i, cnt);
1470 }
1471 fprintf(f, "\ttotal size %lu KB", totalSize/1024);
1472}
1473
1474void Backend::reportStat(FILE *f)
1475{
1476 scanCoalescQ(/*forceCoalescQDrop=*/false);
1477
1478 fprintf(f, "\n regions:\n");
1479 int regNum = regionList.reportStat(f);
1480 fprintf(f, "\n%d regions, %lu KB in all regions\n free bins:\nlarge bins: ",
1481 regNum, totalMemSize/1024);
1482 freeLargeBlockBins.reportStat(f);
1483 fprintf(f, "\naligned bins: ");
1484 freeSlabAlignedBins.reportStat(f);
1485 fprintf(f, "\n");
1486}
1487#endif // __TBB_MALLOC_BACKEND_STAT
1488
1489} } // namespaces
1490