Ttykuu

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_buffernullptr;
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.