Memory Management Strategy

[bokee]

I'm a fresh for TBB and I want to read and find out how TBB to manage and allocate the memory ,in the demand of work.But I failed because I'm in lack of resouces or documents.Anybody can give me a hand and explain the routine calable_malloc,in MemoryAllocator.cpp or the terms like block ,freeobject ,and differences between allcoate from bumpptr and from freelist.If it's hard to express.Can you supply or recommend some documents or resouces about it.
Thank you very much and waiting on line

[Alexey-Kukanov]

I suggest you to read http://www.intel.com/technology/itj/2007/v11i4/5-foundations/1-abstract.htm; this paper has a high-level overview of the TBB scalable allocator. Be aware that a few initial sections in the paper are about TBB task scheduler; so keep reading or just skip to the 5th section.

I will be glad to answer any specific questions or concerns.

[bokee]

Thanks for your reply and I have read that paper.But I'm still confused by some details.
Totally,How scalable allocator is initialized???
In detail,when I read source code in MemoryAllocator.cpp,I'm confused by nextPrivatizable item In struct BlockS!!!
Can you explain breifly how functions as getPublicFreeListBlock,privatizePulbicFreeList,getPartialBlock to work?

[Alexey-Kukanov]

The allocator is initialized lazily, i.e. at the first call to scalable_malloc. Look for checkInitialization and what is called from there.

nextPrivatizable initially points to the mailbox, which is the list of the blocks where some objects were free'd by a foreign thread, and later to the next block in this list.

I can not briefly explain how the functions work, sorry. It would require an extensive post about internal implementation of the allocator, which I have no time to write (yet).

[bokee]

It's enough and I'll try to find out myself.

Thanks

[bokee]

I have read through scalable allocator codes and get through the memory allocation process.

But I can't think out how TBB maintain nextPrivatizable in Block and mailbox in BinS

and why pointer to Bin can be assigned to pointer to Block without access errors,like codes in function freePublicObject, also for Block* to Bin* as below:

//freePublicObject
        if( !isNotForUse(block->nextPrivatizable) ) {
            MALLOC_ASSERT(block->nextPrivatizable!=NULL, ASSERT_TEXT);
            MALLOC_ASSERT(block->owner!=0, ASSERT_TEXT);
            theBin = (Bin*) block->nextPrivatizable;
#ifdef MALLOC_DEBUG
            { // check that nextPrivatizable points to the bin the block belongs to
                uint32_t index = getIndex( block->objectSize );
                Bin* tls = (Bin*)getThreadMallocTLS();
                MALLOC_ASSERT(theBin==tls+index, ASSERT_TEXT);
            }
#endif
// the counter should be changed            STAT_increment(getThreadId(), ThreadCommonCounters, lockPublicFreeList);
            MallocMutex::scoped_lock scoped_cs(theBin->mailLock);
            block->nextPrivatizable = theBin->mailbox;
           theBin->mailbox = block;
        } else {
            MALLOC_ASSERT(block->owner==0, ASSERT_TEXT);
        }
    }

[Alexey-Kukanov]

bokee:

But I can't think out how TBB maintain nextPrivatizable in Block and mailbox in BinS and why pointer to Bin can be assigned to pointer to Block without access errors,like codes in function freePublicObject, also for Block* to Bin* ...

Pointers to any objects are always of the same size, and thus are interexchangeable in some sense. For example, you could cast any pointer to void* and vice versa. Casts like those in the allocator code should be used with care; a programmer should be sure that a proper type of object is accessed via the pointer. For example, the code in freePublicObject you quoted only runs when it is known that the block does not yet contain any object in its public free list, and thus it is guaranteed that nextPrivatizable points to the bin and not to a block.

I agree this is not the best piece of code for readability and understanding. Possibly it would be more clear if the casting was done with reinterpret_cast. It would be even more clear if the pointer was declared as void* and named differently, and casts to proper type were used everywhere with the pointer.

[bokee]

Hi,I'm back.

I found someting interesting about codes related to memory free.

//scalable_free
} else {
if(block->allocatedCount==0&&block->publicFreeList==NULL) {
if (block != getActiveBlock(bin)&&
block!=getActiveBlock(bin)->previous){
outofTLSBin(bin, block);
returnEmptyBlock(block);
} else {
restoreBumpPtr(block);
}
}
}

I find that there is no situations when block->allocatedCount==0 and block->publicFreeList!=NULL at the same time

I just want to know whether I miss some especial situations or It just ensures correct because I'think when allocatedCount==0,the publicFreeList must be NULL. because allocatedCount can be modified by owner thread only.

It's import to me because It can examine whether I'm familiar whith the procedure of memory allocation.

[Alexey-Kukanov]

You are both right and wrong :)

You are right that allocatedCount can only be modified by the owning thread, so if there were some objects returnedvia publicFreeList, then allocatedCount is not zero.

But you are wrong that publicFreeList must be NULL if allocatedCount is zero. It can temporarily be set to something different than NULL, but not a valid pointer either. See *PartialBlock methods.

I think you probably have got reasonably good grasp of what's going on inside the allocator. The part you misjudge aboutis quite a complex one.

[bokee]

something different than NULL? You mean unusable?

But publicFreeList can be set unusable only when returnPartialBlock is called,that is when the thread will exit immediately. and privatizePublicList will be called, which will set publicFreeList to NULL again ,when getPartialBlock is called.

So,when owner thread invokes scalable_free, publicFreeList can be only NULL or valid pointer, I think.

[Alexey-Kukanov]

No, scalable_free can be called by another thread at any time in between returnPartialBlock and getPartialBlock. The idea of these two functions is to leave a block, which is not empty at the moment its owning thread exits, still accessible so another thread can later adopt it if run short of its own heap. But in between, any thread can free any object in this block; and it shouldn't be owned for that.

[bokee]

MADakukanov:

scalable_free can be called by another thread at any time in between returnPartialBlock and getPartialBlock.

Maybe you ignore someting.

I know what you said. But scalable_free can be only called by foreign
thread between returnPartialBlock(which is called by DLLMAIN) and getPartialBlock because owner thread will exit immediately.And

//scalable_free
if (myTid == block->owner) {
......
if(block->allocatedCount==0&&block->publicFreeList==NULL)

is executed by owner thread only.

[Alexey-Kukanov]

Okay, you convinced me that for the owner thread, public free list only exists when allocatedCount is greater than zero. At least in theory :)

The easiest thing to check it in practice would be converting that second check into an assertion, and then running it through excessive testing with irregular allocation/deallocation and thread creation/destruction patterns. If that passed, there would be enough confidence to eliminate that second check.

Thanks for your persistence.