Subj : YALFAm (Yet Another Lock Free Approach, maybe) To : comp.programming.threads From : James Talbut Date : Sun May 15 2005 09:03 am Folks, I have an idea about a 'mainly' lock free implementation that I'd appreciate comments on. I'm attempting to solve the same sort of problem as Joe Seigh's atomic_ptr (http://atomic-ptr-plus.sourceforge.net/), but in a way that will work on win64 and win32 (so I want to avoid assembly and reliance on instructions that are not present on some processors). What I'm trying to have is a global pointer, but I need to be able to replace that pointer with a new value every so often (it's configuration data that needs to be updateable). Obviously replacing it is easy, but then I have to track the previous value (which may still be in use) to ensure that it is destructed correctly. This is a problem that I have hit many time and I'm sure I'm not alone in that. The problem with the atomic_ptr approach (for me) is that it stores reference data in the same double word (64 bits) as the pointer itself. This is fine is you have a CAS instruction that works with a double word, but AMD64 (and hence win64) does not reliably (that would be a 128bit CAS). Fortunately for me atomic_ptr is more flexible than I need as I know my updates will only occur infrequently and I know at compile time how many of these global pointers I will want. So my idea is to separate the pointer from the reference count, and to just track the reference count. In order to do this I need to have somewhere to keep the pointers, so my global pointer becomes a singleton containing an array of pointers and a matching array of reference counts. When working with the reference counts I need to know some things about the pointers, so I reserve two bits in each count, one for IsAvailable and one for IsLocked. When a pointer is being changed IsLocked is set and no other function will read or write that pointer (they will work with another one). When a pointer has been set, IsAvailable is set for that count and cleared for all the other counts (noting that having two available pointers is fine, having none is not). When setting a pointer it doesn't matter where I work from - I can either start at the beginning each time and get the first once that I can, or I can rotate around the buffer. Similarly when being asked for the 'current' pointer I can either track a rotating index or I can simply return the first that is available - the latter may have a a race condition that prevents pointers from being freed, but I'll look into that (I don't think it does 'cos IsAvailable won't be set). When a 'pointer' is requested from the object it will return an object of a local class that contains a reference to the singleton and the array index of a pointer. Each copy of the local class will increment the reference count for the index (which may have IsAvailable set and will not have IsLocked set). Each destructor of the local class will decrement the reference count, when it gets to zero if IsAvailable is not set IsLocked will be set, the destructor will be called, the pointer destructed and set to null and the ref count will be reset to zero (both flags cleared). IsAvailable signifies that the pointer is available for new local pointers, existing local pointers will be quite happy regardless of whether IsAvailable is set or not. All changes to the reference count (or the flags) will be done using CAS - and note that if the CAS fails it may be necessary to move to a different array entry. There are obviously limitations on this: * It's a singleton, with the inherent issues that causes, but as this is intended for the sort of config data that is explicitly read at startup I can live with those constraints - and if you want to copy it you can have a shared_ptr to it (the copying of that will lock, but accesses through it won't). * If anyone takes a copy of the bare pointer returned from the local object then all bets are off, but the same applies with any reference counting implementation. * The time between updates must not be less than the time is takes for all readers to free their local pointers multiplied by the size of the arrays (if it is the writer will wait/spin/block) (this is a compile time tuning issue, the size of the arrays will probably be a template parameter). * It wastes some memory on startup, but at least it's constant. Two additional features that I have thought about but don't currently think I need: 1. An IsNull flag - will be needed if there is any way for a thread to read a pointer after IsAvailable and RefCount reach zero but before the pointer is set to null, IsLocked is intended to sort that out. 2. A version number to prevent ABA - I don't think I should get an ABA problem (only one reference can exist when refcount gets to zero, and it will set IsLocked for the duration of the destruction). I may want to have a lightweight mutex of some sort on setting a pointer, though in my uses of the class setting will always be done from one thread. This is why I class it as 'mainly' lock free, I'm after lock free high speed reading, writing can take its time. The use of IsLocked does not actually cause locking on reading - there will always be at least one unlocked available pointer (even if it's null). A few questions that I'd be grateful for answers to: 1. Does this make sense (i.e. have I explained enough)? 2. Does it look like it should work (presuming, of course, that I code it correctly)? 3. Are you aware of any existing implementation that either works like this or that solve the same problem? 4. Am I way out of my depth/wasting my time? 5. I have seen derogatory comments about the win Interlocked* functions, could you direct me to something that details the deficiencies in these functions? 6. Any other comments at all? Thank you for even bothering to read this far, and thank you again if you have any comments. -- J.T. Please reply via the newsgroup. .