# Is my lockless data structure correct?

I need multiple read access to some data which can be updated from time to time. I created a class for managing lock-less access to the data. The class uses 2 counters, one for count of the acquired references and another one for the count of released references. The update function replaces the data pointer and then waits for the completion of the previous reads.

Can someone with more experience in lock-less programming comment on the correction and performance of the code?

template<typename T>
inline void IgnorePolicy(T* item) {}
template<typename T>
inline void DeletePolicy(T* item)
{
delete item;
}
template<typename T>
inline void ReleasePolicy(T* item)
{
if(item != NULL)
item->Release();
}

template<typename T, void (* DestroyPolicy)(T* item) = IgnorePolicy>
{
private:
volatile int m_acquireCount, m_releaseCount;
T* m_data;

bool CheckReleaseCount(int limit) //wrap-safe check to see if release count has reached the required limit
{
int releaseCount = m_releaseCount;
return (limit < 0 || releaseCount >= 0) ? limit <= releaseCount : limit >= 0 && releaseCount < 0;
}

public:
ReadUpdateData() : m_acquireCount(0), m_releaseCount(0), m_data(NULL) {}
{
assert(m_acquireCount == m_releaseCount);
DestroyPolicy(m_data);
}

T* Acquire()
{
AtomicIncrement(&m_acquireCount);
return m_data;
}
void Release()
{
AtomicIncrement(&m_releaseCount);
}

void Update(T* newData)
{
T* oldData = m_data;
while(AtomicCompareExchangePtr(&m_data, newData, oldData) == oldData)
oldData = m_data;

int acquireCount = m_acquireCount;
while(!CheckReleaseCount(acquireCount))
Yield();

DestroyPolicy(oldData);
}
};


## migrated from stackoverflow.comFeb 16 '12 at 23:29

This question came from our site for professional and enthusiast programmers.

• (limit >= 0) <= (releaseCount >= 0) ouch. What's wrong with limit < 0 || releaseCount >= 0 ? – CB Bailey Feb 15 '12 at 15:10

There is a flaw in the code.

int acquireCount = m_acquireCount;
while(!CheckReleaseCount(acquireCount))
Yield();
DestroyPolicy(oldData);


You read the acquire counter, then wait for the release counter to be equal to what you read, and think that this indicates the old data are not used anymore. This is incorrect, because after reading you might get both counters incremented by threads that use new data. Thus, despite the release counter being equal to or greater than the value you read, some threads still may use the old data.

I'm not an expert, but I this line caught my eye:

volatile int m_acquireCount, m_releaseCount;


m_acquireCount and m_releaseCount will be part of the same cache line!

Therefor I expect no performance advantages compared to the simpler AtomicIncrement/AtomicDecrement on one variable.

    bool CheckReleaseCount(int limit) //wrap-safe check to see if release count has reached the required limit
{
int releaseCount = m_releaseCount;
return (limit >= 0) <= (releaseCount >= 0) ? limit <= releaseCount : limit >= 0 && releaseCount < 0;
}


This has no protection on m_releaseCount. Most threading platforms claim UB if a variable is accessed in one thread while another thread is, or might be, modifying it. So this code is only usable on platforms that have defined semantics for concurrent accesses to aligned volatile integers. Don't you have some kind of AtomicFetch function for just this purpose?

• I'm sorry, but can you explain what UB stands for? – Chris Feb 15 '12 at 15:23
• But aren't int assignments atomic on 32/64 bit platforms anyway? And m_releaseCount is volatile. – Tudor Feb 15 '12 at 15:29
• Undefined Behavior. That is, nothing specifically tells you what will happen, so in principle anything can happen. – David Schwartz Feb 15 '12 at 15:29
• @Tudor If you know your platform has defined semantics for concurrent accesses to aligned volatile integers, then this isn't an issue. Windows (with either GCC, ICC, or VC) has defined semantics for these accesses on 32-bit and 64-bit x86 platforms. – David Schwartz Feb 15 '12 at 15:31
• I'm only familiar with x86/x64 processors which have atomic reads/writes to aligned memory. I guess that may not be the case on other platforms. I'll add and AtomicFetch function also. Thank you. – Chris Feb 15 '12 at 15:34

if you have C++11, use std::atomic instead.