Gfrktyl

I have created a thread-safe and lock-free memory pool program using C++11 features. A couple of notable features:

• 
  g_memStack is a stack that contains the memory unit; we can allocate memory from it.


• 
  g_waitingReclaims is something like a stack that contains units waiting reclaim from the memory unit.


• 
  g_allocatingCounter is a counter to specify the thread number in the Allocate function. It will have a value of 1 to indicate that there is no other thread waiting to allocate memory from the pool. This indicates that it is safe to reclaim memory in g_waitingReclaims.

I am looking for a review of both correctness and style. Specifically:

• Is there anything wrong with the memory ordering in g_allocatingCounter.fetch_add(1, std::memory_order_relaxed (the first line in the Allocate function?)?




• Is it possible that the next line (MemUnit *unit = g_memStack.load(std::memory_order_acquire); could be re-ordered to execute first at runtime?




• If so, how would I fix that? Could I just change the memory order to std::memory_order_aquery? Would that require another release operation to cooperate with it (I don't think so, because cppreference said std::memory_order_acquire will prevent read and write from reordering before it)?




• Anything else?

#include <string>

#include <thread>

#include <vector>

#include <cstdlib>

#include <atomic>

#include <cassert>



struct MemUnit

{

    MemUnit *m_next;//next unit

    void    *m_data;//memory for data

};



void                    *g_buffer{nullptr};

std::atomic<MemUnit *>  g_memStack{};

std::atomic<MemUnit *>  g_waitingReclaims{};

std::atomic<uint32_t>   g_allocatingCounter{};



void InitMemPool(size_t poolSize, size_t blockSize);

void UninitMemPool();



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.

}



void InitMemPool(size_t poolSize, size_t blockSize)

{

    const size_t unitSize = sizeof(MemUnit) + blockSize;

    g_buffer = reinterpret_cast<uint8_t *>(std::malloc(unitSize * poolSize));



    MemUnit* next = nullptr;

    uint8_t* rawBuffer = reinterpret_cast<uint8_t*>(g_buffer);

    for (size_t i = 0; i != poolSize; ++i)

    {

        MemUnit* pObj = reinterpret_cast<MemUnit *>(rawBuffer);

        pObj->m_next = next;

        next = pObj;

        rawBuffer += unitSize;

    }

    g_memStack.store(next, std::memory_order_relaxed);

}



void UninitMemPool()

{

    assert(g_allocatingCounter.load(std::memory_order_relaxed) == 0);



    g_memStack.store(nullptr, std::memory_order_relaxed);

    g_waitingReclaims.store(nullptr, std::memory_order_relaxed);

    std::free(g_buffer);

    g_buffer = nullptr;

}







void WorkThread()

{

    for (size_t i = 0; i != 128; ++i)

    {

        MemUnit *unit = Allocate();

        if (unit != nullptr)

        {

            //do something use unit.m_data;

            FreeMemUnit(unit);

        }

    }

}



int main()

{

    InitMemPool(128, 1024);



    std::vector<std::thread> allThreads;

    for (size_t i = 0; i != 8; ++i)

    {

        std::thread t(WorkThread);

        allThreads.push_back(std::move(t));

    }

    for (auto &t : allThreads)

    {

        t.join();

    }

    UninitMemPool();

    return 0;

}

'g_memStack' is a stack that contains memory unit. We can allocate
memory unit from it

There is not a single line of code allocating MemUnit

This a thread safe and lock-free memory pool program

Unfortunately this is not true. Assume two threads are executing Allocate on an empty stack in a fully interleaved manner.

g_allocatingCounter.fetch_add(1, std::memory_order_relaxed); //T1 : 1, T2 : 2

MemUnit *unit = g_memStack.load(std::memory_order_acquire);  //T1 : nullptr, T2 : nullptr

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)

{

   //let's assume its fine here

    return unit; // T1 : something

}

g_allocatingCounter.fetch_sub(1, std::memory_order_relaxed);

return unit; //T2 : nullptr

They reach if (g_allocatingCounter.load(std::memory_order_relaxed) == 1) with the variable unit being null. The condition is true for one thread but not the other.

The thread for which the condition is false will return nullptr.