Creating a lock-free memory pool using C++11 features
Should I tell management that I intend to leave due to bad software development practices?
Forgetting the musical notes while performing in concert
Why is it a bad idea to hire a hitman to eliminate most corrupt politicians?
files created then deleted at every second in tmp directory
Car headlights in a world without electricity
How seriously should I take size and weight limits of hand luggage?
Implication of namely
How to show a landlord what we have in savings?
Does the Idaho Potato Commission associate potato skins with healthy eating?
Was the Stack Exchange "Happy April Fools" page fitting with the '90's code?
Fair gambler's ruin problem intuition
Notepad++ delete until colon for every line with replace all
Mathematica command that allows it to read my intentions
Why do I get negative height?
How does a refinance allow a mortgage to be repaid?
Different meanings of こわい
How can a day be of 24 hours?
ssTTsSTtRrriinInnnnNNNIiinngg
Sums of two squares in arithmetic progressions
Getting extremely large arrows with tikzcd
How badly should I try to prevent a user from XSSing themselves?
In the UK, is it possible to get a referendum by a court decision?
Knowledge-based authentication using Domain-driven Design in C#
Can compressed videos be decoded back to their uncompresed original format?
Creating a lock-free memory pool using C++11 features
$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 theAllocate
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 ing_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 theAllocate
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 saidstd::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;
c++ c++11 lock-free
$endgroup$
migrated from stackoverflow.com 2 mins ago
This question came from our site for professional and enthusiast programmers.
add a comment |
$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 theAllocate
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 ing_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 theAllocate
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 saidstd::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;
c++ c++11 lock-free
$endgroup$
migrated from stackoverflow.com 2 mins ago
This question came from our site for professional and enthusiast programmers.
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
21 hours ago
$begingroup$
@ThomasLang: the 3atomic<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$
– Peter Cordes
15 hours ago
$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
2 hours ago
add a comment |
$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 theAllocate
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 ing_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 theAllocate
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 saidstd::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;
c++ c++11 lock-free
$endgroup$
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 theAllocate
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 ing_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 theAllocate
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 saidstd::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;
c++ c++11 lock-free
c++ c++11 lock-free
asked 22 hours ago
water
migrated from stackoverflow.com 2 mins ago
This question came from our site for professional and enthusiast programmers.
migrated from stackoverflow.com 2 mins ago
This question came from our site for professional and enthusiast programmers.
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
21 hours ago
$begingroup$
@ThomasLang: the 3atomic<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$
– Peter Cordes
15 hours ago
$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
2 hours ago
add a comment |
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
21 hours ago
$begingroup$
@ThomasLang: the 3atomic<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$
– Peter Cordes
15 hours ago
$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
2 hours ago
1
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
21 hours ago
$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
21 hours ago
$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$
– Peter Cordes
15 hours ago
$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$
– Peter Cordes
15 hours ago
$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
2 hours ago
$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
2 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$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$
$begingroup$
Thanks for your reply. Yes, the function is allowed to return nullptr.
$endgroup$
– water
2 hours ago
$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$
– Peter Cordes
13 secs ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f216762%2fcreating-a-lock-free-memory-pool-using-c11-features%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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$
$begingroup$
Thanks for your reply. Yes, the function is allowed to return nullptr.
$endgroup$
– water
2 hours ago
$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$
– Peter Cordes
13 secs ago
add a comment |
$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$
$begingroup$
Thanks for your reply. Yes, the function is allowed to return nullptr.
$endgroup$
– water
2 hours ago
$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$
– Peter Cordes
13 secs ago
add a comment |
$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$
'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
.
answered 19 hours ago
UmNyobeUmNyobe
17910
17910
$begingroup$
Thanks for your reply. Yes, the function is allowed to return nullptr.
$endgroup$
– water
2 hours ago
$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$
– Peter Cordes
13 secs ago
add a comment |
$begingroup$
Thanks for your reply. Yes, the function is allowed to return nullptr.
$endgroup$
– water
2 hours ago
$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$
– Peter Cordes
13 secs ago
$begingroup$
Thanks for your reply. Yes, the function is allowed to return nullptr.
$endgroup$
– water
2 hours ago
$begingroup$
Thanks for your reply. Yes, the function is allowed to return nullptr.
$endgroup$
– water
2 hours ago
$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$
– Peter Cordes
13 secs ago
$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$
– Peter Cordes
13 secs ago
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f216762%2fcreating-a-lock-free-memory-pool-using-c11-features%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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
21 hours ago
$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$
– Peter Cordes
15 hours ago
$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
2 hours ago