lundi 1 avril 2019

Something weired about a lock-free memory pool

Something about the program:

  1. This a thread safe and lock-free memory pool program
  2. 'g_memStack' is a stack that contains memory unit. We can allocate memory unit from it
  3. 'g_waitingReclaims' is something like a stack that contains memory unit waiting reclaim.
  4. 'g_allocatingCounter' is a counter to specify thread number in function 'Allocate'. 'g_allocatingCounter' is 1 indicate that there is no other thread is allocating memory from the pool. So it's safe to reclaim memory in 'g_waitingReclaims'

My questing is:

  1. Is there anything wrong about the memory order in 'g_allocatingCounter.fetch_add(1, std::memory_order_relaxed)'(The first line in function 'Allocate'). I think it's next line(MemUnit *unit = g_memStack.load(std::memory_order_acquire);) maybe reorder before it at runtime.

  2. How to fix it? Just change the memory order to 'std::memory_order_aquery' will be alright? It's really a little weird. Does that need another release operation cooperate with it(I don't think so, because the cpprefefence said std::memory_order_acquire will prevent read and write from reorder before it.)

  3. Is there anything else wrong in your opinion about the program

Thank you very much in advance

struct MemUnit
{
    MemUnit *m_next;//next unit
    void    *m_data;//memory for data
};

std::atomic<MemUnit *>  g_memStack;//We will initialize the stack in somewhere else
std::atomic<MemUnit *>  g_waitingReclaims;
std::atomic<uint32_t>   g_allocatingCounter{};

MemUnit *StepToTail(MemUnit* listHead);
void Reclaim(MemUnit* listHead, MemUnit* listTail);
void GiveBackToWaitings(MemUnit* listHead, MemUnit* listTail);

MemUnit *Allocate()
{
    g_allocatingCounter.fetch_add(1, std::memory_order_relaxed);//Warning: Something wrong with the memory order. It maybe reorder after the next line at runtime.
    MemUnit *unit = g_memStack.load(std::memory_order_acquire);
    while (unit != nullptr && !g_memStack.compare_exchange_weak(unit, unit->m_next, std::memory_order_acquire, std::memory_order_acquire));
    if (g_allocatingCounter.load(std::memory_order_relaxed) == 1)
    {
        MemUnit *pendingList = g_waitingReclaims.exchange(nullptr, std::memory_order_acquire);
        const bool canReclaim = g_allocatingCounter.fetch_sub(1, std::memory_order_relaxed) == 1;//this operation can not reorder before exchange operation Just because the 'memory_order_acquire'
        //If 'canReclaim' is true, it's ABA problem free. Because there is nobody in 'Allocate' hold same pointer within pending list.
        if (canReclaim && pendingList != nullptr)
        {
            canReclaim ? Reclaim(pendingList, StepToTail(pendingList)) : GiveBackToWaitings(pendingList, StepToTail(pendingList));
        }
        return unit;
    }
    g_allocatingCounter.fetch_sub(1, std::memory_order_relaxed);//this operation can not reorder before 'compare_exchange_weak' Just because the 'memory_order_acquire'
    return unit;
}

void FreeMemUnit(MemUnit* item)
{
    item->m_next = g_waitingReclaims.load(std::memory_order_relaxed);
    while (!g_waitingReclaims.compare_exchange_weak(item->m_next, item, std::memory_order_release, std::memory_order_relaxed));
}

MemUnit *StepToTail(MemUnit* listHead)
{
    assert(listHead != nullptr);
    while (listHead->m_next) listHead = listHead->m_next;
    return listHead;
}

void Reclaim(MemUnit* listHead, MemUnit* listTail)
{
    listTail->m_next = g_memStack.load(std::memory_order_relaxed);
    while (!g_memStack.compare_exchange_weak(listTail->m_next, listHead, std::memory_order_release, std::memory_order_relaxed));
}

void GiveBackToWaitings(MemUnit* listHead, MemUnit* listTail)
{
    listTail->m_next = g_waitingReclaims.load(std::memory_order_relaxed);
    while (!g_waitingReclaims.compare_exchange_weak(listTail->m_next, listHead, std::memory_order_relaxed, std::memory_order_relaxed));
    //Yes, it's 'relaxed' memory order when it's success.
}

Aucun commentaire:

Enregistrer un commentaire