{"id":1609,"date":"2009-02-17T12:58:41","date_gmt":"2009-02-17T18:58:41","guid":{"rendered":"http:\/\/bobbeaty.com\/wp\/?p=1609"},"modified":"2009-03-04T13:49:17","modified_gmt":"2009-03-04T19:49:17","slug":"interesting-application-of-thread-safe-lockless-data-structures","status":"publish","type":"post","link":"https:\/\/bobbeaty.com\/wp\/archives\/1609","title":{"rendered":"Interesting Application of Thread-Safe Lockless Data Structures"},"content":{"rendered":"

\"cplusplus.jpg\"<\/p>\n

I was looking at lockless data structures for multi-threaded programming again this morning, and I came across a link to TransactionKit<\/a>. This sounds very interesting to me. Basically, the group has implemented a thread-safe NSDictionary<\/tt> and NSMutableDictionary<\/tt> pair that are completely safe for multi-threaded environments, use no locks, and offer the basics<\/strong> of transactional integrity: begin transaction<\/tt>, commit<\/tt> and rollback<\/tt> functionality. And I have to admit I'm very intrigued.<\/p>\n

The biggest challenge to me in working with these lockless data structures is that you might<\/em> not know you're going to need them when you start the project. It's only after<\/em><\/strong> you build the project, see it scale for a while, and then hit a fundamental limit that you see it's time to switch over. Problem is, by then, you're stuck. You've got all this code that uses one form of thread-safety, and now what you realize you need is something else all together. But you can't justify the complete re-write.<\/p>\n

What you need is lockless alternatives<\/em><\/strong> to standard data components that are easily swapped in when the 'going gets tough'. For example, I like TransactionKit<\/a>'s take on the inclusion in Objective-C - make it look like a simple NSDictionary<\/tt> and NSMutableDictionary<\/tt> so that it's a simple search and replace for the vast majority of the retrofitting. This makes things a lot simpler.<\/p>\n

But now I'm looking at the CKit stuff. It'd be one thing to have a truly<\/em> lockless CKFIFOQueue<\/tt>. Then another that uses mutexes for those times when it's not a major issue for speed. Finally, one that uses the lockless atomic calls to make it appear<\/em><\/strong> to be lockless, in fact, you can even simply No-Op the lock()<\/tt> and unlock()<\/tt> methods in the subclass, but all the while, the thread-safe behavior is in play.<\/p>\n

The problems with general coding are a lot more difficult, however. Take for example, the retain<\/tt>\/release<\/tt> code I posted a few days ago. That's not so simple. Previously, I had:<\/p>\n

void<\/span> Instrument::<\/span>retain<\/span>(<\/span>)<\/span>\n{<\/span>\n    \/\/ first, lock this guy up<\/span>\n    CKStackLocker      lockem(<\/span>&<\/span>mRetainReleaseMutex)<\/span>;<\/span>\n    \/\/ now up the count<\/span>\n    ++<\/span>mRetainReleaseCount;<\/span>\n    \/\/ see if it's in the pool to be released, if so, remove it<\/span>\n    if<\/span> (<\/span>mRetainReleaseCount ==<\/span> 1<\/span>)<\/span> {<\/span>\n        CKStackLocker      lockem(<\/span>&<\/span>mReleasePoolMutex)<\/span>;<\/span>\n        mReleasePool.remove<\/span>(<\/span>this<\/span>)<\/span>;<\/span>\n    }<\/span>\n}<\/span>\n \nvoid<\/span> Instrument::<\/span>release<\/span>(<\/span>)<\/span>\n{<\/span>\n    \/\/ first, lock this guy up<\/span>\n    CKStackLocker      lockem(<\/span>&<\/span>mRetainReleaseMutex)<\/span>;<\/span>\n    \/\/ no decrease the count<\/span>\n    --<\/span>mRetainReleaseCount;<\/span>\n    \/\/ see if it's an error<\/span>\n    if<\/span> (<\/span>mRetainReleaseCount <<\/span> 0<\/span>)<\/span> {<\/span>\n        getLog(<\/span>)<\/span> <<<\/span> l_error.setErrorId<\/span>(<\/span>"Instrument.release"<\/span>)<\/span>\n                 <<<\/span> "the release count for "<\/span> <<<\/span> mmSym(<\/span>)<\/span> <<<\/span> " went negative! ("<\/span>\n                 <<<\/span> mRetainReleaseCount <<<\/span> ") This is a serious problem."<\/span> <<<\/span> endl;<\/span>\n    }<\/span>\n    \/\/ see if it's at zero, and then if so, add it to the pool<\/span>\n    if<\/span> (<\/span>mRetainReleaseCount <=<\/span> 0<\/span>)<\/span> {<\/span>\n        CKStackLocker      lockem(<\/span>&<\/span>mReleasePoolMutex)<\/span>;<\/span>\n        if<\/span> (<\/span>!<\/span>mReleasePool.contains<\/span>(<\/span>this<\/span>)<\/span>)<\/span> {<\/span>\n            \/\/ log that we're going to dump it in the trash<\/span>\n            getLog(<\/span>)<\/span> <<<\/span> l_error.setErrorId<\/span>(<\/span>"Instrument.release"<\/span>)<\/span>\n                     <<<\/span> "adding "<\/span> <<<\/span> mmSym(<\/span>)<\/span> <<<\/span> " with retain cnt="<\/span>\n                     <<<\/span> mRetainReleaseCount <<<\/span> " to garbage"<\/span> <<<\/span> endl;<\/span>\n            \/\/ ...and then do it.<\/span>\n            mReleasePool.addBack<\/span>(<\/span>this<\/span>)<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n}<\/span><\/pre>\n
where the critical points were one (1) in the retain()<\/tt> code and anything less than or equal to zero in the release()<\/tt> code. This was due to the logical assumption that the value of mRetainReleaseCount<\/tt> would be initialized to 1. But what if we have it initialized to zero? Then the critical points are zero for the retain()<\/tt> code and anything negative for the release()<\/tt> code.<\/p>\n
#include <asm\/atomic.h><\/span>\n \nvoid<\/span> Instrument::<\/span>retain<\/span>(<\/span>)<\/span>\n{<\/span>\n    \/*\n     * Increment the count. If it's zero, then we were ready to flush this guy\n     * and now we need to pull him out of the garbage before he gets flushed.\n     *\/<\/span>\n    if<\/span> (<\/span>atomic_inc_and_test(<\/span>&<\/span>mRetainReleaseCount)<\/span>)<\/span> {<\/span>\n        CKStackLocker      lockem(<\/span>&<\/span>mReleasePoolMutex)<\/span>;<\/span>\n        mReleasePool.remove<\/span>(<\/span>this<\/span>)<\/span>;<\/span>\n    }<\/span>\n}<\/span>\n \nvoid<\/span> Instrument::<\/span>release<\/span>(<\/span>)<\/span>\n{<\/span>\n    \/*\n     * Decrement the count, and if we are negative then it's time to add this\n     * guy to the release pool for deletion.\n     *\/<\/span>\n    if<\/span> (<\/span>atomic_add_negative(<\/span>-<\/span>1<\/span>, &<\/span>mRetainReleaseCount)<\/span>)<\/span> {<\/span>\n        CKStackLocker      lockem(<\/span>&<\/span>mReleasePoolMutex)<\/span>;<\/span>\n        if<\/span> (<\/span>!<\/span>mReleasePool.contains<\/span>(<\/span>this<\/span>)<\/span>)<\/span> {<\/span>\n            \/\/ log that we're going to dump it in the trash<\/span>\n            getLog(<\/span>)<\/span> <<<\/span> l_error.setErrorId<\/span>(<\/span>"Instrument.release"<\/span>)<\/span>\n                     <<<\/span> "adding "<\/span> <<<\/span> mmSym(<\/span>)<\/span> <<<\/span> " with retain cnt="<\/span>\n                     <<<\/span> mRetainReleaseCount <<<\/span> " to garbage"<\/span> <<<\/span> endl;<\/span>\n            \/\/ ...and then do it.<\/span>\n            mReleasePool.addBack<\/span>(<\/span>this<\/span>)<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n}<\/span><\/pre>\n
if I then initialize the value of mRetainReleaseCount<\/tt> with:<\/p>\n
    ...\n    mRetainReleaseCount<\/span>(<\/span>ATOMIC_INIT(<\/span>0<\/span>)<\/span>)<\/span>,\n    ...<\/pre>\n
in the constructor's code, then we'll start with zero, climb positive, and then when we go negative we'll by tossed into the release pool for the next cycle on the garbage collector thread. Since the garbage collector thread also checks the retain\/release count before it wipes out the instance, we're safe.<\/p>\n
At least I'm pretty sure we are...<\/p>\n
Well... here's the problem I see now. Because we have removed the mutex on the retain()<\/tt> and release()<\/tt> methods, we can<\/em> be doing both at once. The count will be handled properly, but what if the release()<\/tt> hits it's counter operation first<\/em>, but the retain()<\/tt> method's if()<\/tt> body executes first to get the lock on the second mutex?<\/p>\n
Now we're in trouble. The counter will be saying 'leave the instrument out of the pool', but the code will execute in the order indicating that the instance will be placed into<\/em><\/strong> the pool. Crud.<\/p>\n
Yup, this is not easy. I was ready to put the code into play, but there's no guarantee that the body of the conditional will execute in the same order as the atomic operation. This means that it's possible to have them in the wrong order. This, in turn, tells me that the greatest application of these atomic operations are in the thread-safe lockless data structures. That's about it. When you have two operations that need to be treated atomically, then you're sunk. Darn.<\/p>\n","protected":false},"excerpt":{"rendered":"
I was looking at lockless data structures for multi-threaded programming again this morning, and I came across a link to TransactionKit. This sounds very interesting to me. Basically, the group has implemented a thread-safe NSDictionary and NSMutableDictionary pair that are completely safe for multi-threaded environments, use no locks, and offer the basics of transactional integrity: […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[],"class_list":["post-1609","post","type-post","status-publish","format-standard","hentry","category-coding"],"_links":{"self":[{"href":"https:\/\/bobbeaty.com\/wp\/wp-json\/wp\/v2\/posts\/1609","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/bobbeaty.com\/wp\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/bobbeaty.com\/wp\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/bobbeaty.com\/wp\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/bobbeaty.com\/wp\/wp-json\/wp\/v2\/comments?post=1609"}],"version-history":[{"count":3,"href":"https:\/\/bobbeaty.com\/wp\/wp-json\/wp\/v2\/posts\/1609\/revisions"}],"predecessor-version":[{"id":1711,"href":"https:\/\/bobbeaty.com\/wp\/wp-json\/wp\/v2\/posts\/1609\/revisions\/1711"}],"wp:attachment":[{"href":"https:\/\/bobbeaty.com\/wp\/wp-json\/wp\/v2\/media?parent=1609"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/bobbeaty.com\/wp\/wp-json\/wp\/v2\/categories?post=1609"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/bobbeaty.com\/wp\/wp-json\/wp\/v2\/tags?post=1609"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}