9
\$\begingroup\$

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_acquire? 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;
}
```
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Please check your initialization of the atomics to be correct. I don't know if it is, but there is usually some very weird stuff going on if done wrong. \$\endgroup\$
    – Thomas Lang
    Commented Apr 2, 2019 at 7:13
  • 1
    \$\begingroup\$ @ThomasLang: the 3 atomic<T> variables are all pointer-sized or 32-bit, and have static storage duration. On normal C++ implementations (like x86 gcc or MSVC, or ARM, or whatever), they will be lock-free, and thus zero-initialization of their object representation will give correct behaviour. (As far as C++ language rules, yes, it's a good idea to make sure you init them correctly, but this doesn't explain any weirdness observed on real systems.) \$\endgroup\$ Commented Apr 2, 2019 at 13:01
  • \$\begingroup\$ @Peter Cordes: I have completed the code. Yes, i didn't observe anything weird. The program is just a practice and i can't guarantee it works as what i think(Some times it's really hard to find bugs behind lock-free codes). So i came here and wanted to known what others thinking about this(Yes, it's really like a code review). \$\endgroup\$
    – water
    Commented Apr 3, 2019 at 1:44
  • \$\begingroup\$ @Cody: nice edit! Typo: aquery -> acquire (I don't have 2k rep on this .SE to fix it myself.) \$\endgroup\$ Commented Apr 3, 2019 at 4:20
  • \$\begingroup\$ What you may and may not do after receiving answers \$\endgroup\$
    – Jamal
    Commented Apr 8, 2019 at 3:33

2 Answers 2

3
\$\begingroup\$

'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.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for your reply. Yes, the function is allowed to return nullptr. \$\endgroup\$
    – water
    Commented Apr 3, 2019 at 1:55
  • 1
    \$\begingroup\$ For future readers: this was posted as an answer to the original question, before migration from Stack Overflow. That's why it doesn't look like a code review. \$\endgroup\$ Commented Apr 3, 2019 at 4:19
2
\$\begingroup\$

Includes and types

std::atomic<uint32_t>

You need to include <stdint.h> for this type. Or better, include <cstdint> and use std::uint32_t instead; same for std::uint8_t. Similarly:

const size_t unitSize = sizeof(MemUnit) + blockSize;

Spell that std::size_t. Although implementations are permitted to add global-namespace versions of these identifiers, they are not required to, so relying on that is a portability issue waiting to bite.


Interface

It's not clear whether all the functions are intended to be part of the public interface. Certainly there are several which aren't directly needed by the test program, so perhaps they could be moved into an anonymous namespace?

The naming of the functions is somewhat unconventional - it may well be worth re-reading the std::allocator interface to see what's expected.

InitMemPool and UninitMemPool look very much like they should be an allocator's constructor and destructor, respectively. As free functions, they are vulnerable to misuse (e.g. calling either of them more than once, or using Allocate() before init or after uninit).


Use of std::atomic

I haven't fully audited the memory barriers here, and it's less my area of expertise, so I'm hoping another reviewer will give that some scrutiny.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.