Queues Vs Ring Buffers

[mje]

Wow, you two got way ahead of my ability to follow this thread, took me a while to catch up. Needless to say my playing about is way behind what you have been thinking about.
 

You Init. Then you Uninit. Then you take that same already-uninitialized pointer block and wire it into a Read or a Write. How does the Read or Write know that the pointer block has been deallocated and it should return an error?
Screen shot 2013-07-12 at 10.37.50 PM.png

 
This is a very interesting problem. Well for me it is. While a DSCheckPtr call would help in that specific case, It wouldn't likely be robust if LabVIEW is in the habit of regularly recycling memory as might be done in a real application. The check is near useless if you don't check the pointer under some kind of lock-- there's a race condition because who is to say the pointer wasn't released after you check but before you operate on the pointer? It's easy to see if you do the check before entering the loop and have to do a significant wait, but even if you check it on every iteration there's still the possibility. Of the pointer being released between calls.
 
What if in every set of pointers has an additional sentinel pointer was allocated? The value in this sentinel would tell us if rest of the pointers were still usable. When uninitialize is done, all the pointers are released except the sentinel, which is instead is operated on to guard against the rest of the structure being used. However this causes a memory leak: we need someway to release this sentinel pointer. Is there a way to register a callback with LabVIEW such that when whatever VI hierarchy goes idle which started this whole mess, we can invoke some code to release the sentinel? I imagine registering sentinel pointers somewhere, and when the callback is invoked releasing them.
 
The issue of the pointer being released while a read/write is stuck in its polling loop also needs to be addressed. If someone splits a wire and manages to block a read/write call while uninit is called bad things will happen. We may have to build a lock into read/write that is shared with uninit. Don't panic, I don't mean a traditional LabVIEW lock-- I think we can do this with another pointer. Here's my logic. Say we have our private data as something like this (ignoring the buffer proper since it's not part of the discussion):

class CBufferPointers{private:    // Sentinel, guards the rest of the pointers.    U8 *pSentinel;    // Our read/write lock. Same lifetime as pSentinel.    U8 *pLock;    // Writer cursor    U32 *pWCursor;    // Reader cursors    U32 *pRCursors;    // Tracks the size of the pReaders array.    I32 Readers;}

Then I can see the read/write/uninit logic working something like this:

if (pSentinel == 0){    // None of the pointers are initialized,    // set error out to a not a refnum or something similar.}else{    // Local constant on the block diagram    U8 sentinel = 0;    MoveBlock(&sentinel, pSentinel, 1)    if (sentinel == 0)    {        // The cursor pointers have already been deallocated.        // Return some error    }    else    {        do        {            // Local constant on the diagram            U8 lock = 1;            // Assert our lock while reading the existing state.            SwapBlock(&lock, pLock, 1);            // The loop condition ensures that we are asserting a new            // lock by asserting that we have changed the value from            // 0 to 1. If something else already set the lock to 1, we            // just keep trying.        } while (lock == 1);        // Rest of read/write/uninit algorithm        // When done we release our lock        U8 lock = 0;        MoveBlock(&lock, pLock, 1);    }}

Of course for any of that to work, we need atomic operations on the move/swap calls. Rolf's earlier statements worry me that we don't have that. Is there some low level function/instruction we have in LabVIEW that can be used to implement something like this? I've never delved so greedily in to the depths of LabVIEW before...

[Rolf Kalbermatter]

Wow, you two got way ahead of my ability to follow this thread, took me a while to catch up. Needless to say my playing about is way behind what you have been thinking about.

 

 

This is a very interesting problem. Well for me it is. While a DSCheckPtr call would help in that specific case, It wouldn't likely be robust if LabVIEW is in the habit of regularly recycling memory as might be done in a real application. The check is near useless if you don't check the pointer under some kind of lock-- there's a race condition because who is to say the pointer wasn't released after you check but before you operate on the pointer? It's easy to see if you do the check before entering the loop and have to do a significant wait, but even if you check it on every iteration there's still the possibility. Of the pointer being released between calls.

 

What if in every set of pointers has an additional sentinel pointer was allocated? The value in this sentinel would tell us if rest of the pointers were still usable. When uninitialize is done, all the pointers are released except the sentinel, which is instead is operated on to guard against the rest of the structure being used. However this causes a memory leak: we need someway to release this sentinel pointer. Is there a way to register a callback with LabVIEW such that when whatever VI hierarchy goes idle which started this whole mess, we can invoke some code to release the sentinel? I imagine registering sentinel pointers somewhere, and when the callback is invoked releasing them.

 

The issue of the pointer being released while a read/write is stuck in its polling loop also needs to be addressed. If someone splits a wire and manages to block a read/write call while uninit is called bad things will happen. We may have to build a lock into read/write that is shared with uninit. Don't panic, I don't mean a traditional LabVIEW lock-- I think we can do this with another pointer. Here's my logic. Say we have our private data as something like this (ignoring the buffer proper since it's not part of the discussion):

class CBufferPointers{private:    // Sentinel, guards the rest of the pointers.    U8 *pSentinel;    // Our read/write lock. Same lifetime as pSentinel.    U8 *pLock;    // Writer cursor    U32 *pWCursor;    // Reader cursors    U32 *pRCursors;    // Tracks the size of the pReaders array.    I32 Readers;}

Then I can see the read/write/uninit logic working something like this:

if (pSentinel == 0){    // None of the pointers are initialized,    // set error out to a not a refnum or something similar.}else{    // Local constant on the block diagram    U8 sentinel = 0;    MoveBlock(&sentinel, pSentinel, 1)    if (sentinel == 0)    {        // The cursor pointers have already been deallocated.        // Return some error    }    else    {        do        {            // Local constant on the diagram            U8 lock = 1;            // Assert our lock while reading the existing state.            SwapBlock(&lock, pLock, 1);            // The loop condition ensures that we are asserting a new            // lock by asserting that we have changed the value from            // 0 to 1. If something else already set the lock to 1, we            // just keep trying.        } while (lock == 1);        // Rest of read/write/uninit algorithm        // When done we release our lock        U8 lock = 0;        MoveBlock(&lock, pLock, 1);    }}

Of course for any of that to work, we need atomic operations on the move/swap calls. Rolf's earlier statements worry me that we don't have that. Is there some low level function/instruction we have in LabVIEW that can be used to implement something like this? I've never delved so greedily in to the depths of LabVIEW before...

 

DSCheckPtr() is generally a bad idea for several reasons: For one it gives you a false security since there are situations where this check would simply have to conclude that the pointer is valid but it still could be not valid in the context you make the check. Such a function can check a few basic attributes of a pointer such as if the pointer is not NULL, a real pointer already allocated in the heap rather than just an address to some memory location but it can not check if this pointer was allocated by the original context in which you make the check or since been freed and reallocated by someone else. And anything but the trivial NULL pointer check will cost significant performance as the function has to walk the allocated heap pointers to find if it exists at all in there.

 

Windows knows also such a function, which only works if the memory was allocated through the HeapAlloc() function but its performance is notorical and its false security too. Use of this function is a clear indication that someone tried to patch up a badly designed library by adding some extra pseudo security.

 

As to atomic operations in the exported C API of LabVIEW, I'm not really aware of any but haven't checked in 2012 or 2013 if there are new exports available that might sound like atomic cmpxchg(). Even if there were, I find releasing a library that would not support at least 3 versions of LabVIEW not really a good idea. On the other hand with some preprocessor magic it would be not to difficult to create a source code file that resorts to compiler intrinsics where available (MSVC >= 2005 and GCC >= 4.1.4) and implements the according inline assembly instructions for the others (VxWorks 6.1 and 6.3 and MSVC 6 for Pharlap ETS).

 

I could even provide my partly tested version of a header file for this.

 

And if you want to be safe you should avoid using an U8 as lock. SwapBlock() not being atomic as far as I know, has no way to guarantee that another concurrent call to it on an address adjunct to the currently swapped byte would not destroy the just swapped byte, since the CPU generally works on 32 bit addresses. Also avoid the temptation to make any data structure you want to access in such a way packed in memory. Only aligned address accesses to memory will generally be safe from being stomped on by another thread trying to access a memory address directly adjunct to this address.

If you can use 32bit locks and assure the 32 bit element is properly aligned in memory, SwapBlock() won't need to be atomic as long as you can guarantee that no concurrent read/modify/write (SwapBlock()) access to the same address will ever happen.

[ShaunR]

Vesion 3 is still using the First Call and the feedback nodes. This is causing your program to hang when you call Init a second time. Just throw a For Loop around your test program and wire a 2 to the N terminal. Run the VI. It won't finish. The First Call value and the Feedback Node value have to be part of the pointer block. End of story.

 

Also, you crash if a pointer block that has never been initialized is passed in... need to check for NULL on every call. Test this by just hitting Run on your Read or your Write VI. LV goes away.  You've got guards on DeInit ... need same guards on read/write.

 

I fixed both the hang and the crash on never initialized.

 

Found another crash scenario -- DeInit called twice on the same pointer block. I can't do anything about that or the crash caused by DeInit being called while Read or Write are still running unless/until we figure out how to generate a CAS instruction or some other equivalent atomic instruction.

Circular_BufferV4_AQ.zip

Indeed. There is zero error checking in the prototyping beyond what prevented me from achieving the feasability testing(thats one of the reasons why I call it prototyping rather than alpha or beta). Now I have piqued interest, we can start productionising and locking down the robustness. We also need to do the standard checks like ensuring that allocation actually succeeds etc. I'll add some of your changes to the next release.

There is no point in adding a first call flag to the pointer block. That would require shift registers in the users code. Although you have added it, you haven't actually used it have you?

 

Wow, you two got way ahead of my ability to follow this thread, took me a while to catch up. Needless to say my playing about is way behind what you have been thinking about.

 

 

This is a very interesting problem. Well for me it is. While a DSCheckPtr call would help in that specific case, It wouldn't likely be robust if LabVIEW is in the habit of regularly recycling memory as might be done in a real application. The check is near useless if you don't check the pointer under some kind of lock-- there's a race condition because who is to say the pointer wasn't released after you check but before you operate on the pointer? It's easy to see if you do the check before entering the loop and have to do a significant wait, but even if you check it on every iteration there's still the possibility. Of the pointer being released between calls.

 

What if in every set of pointers has an additional sentinel pointer was allocated? The value in this sentinel would tell us if rest of the pointers were still usable. When uninitialize is done, all the pointers are released except the sentinel, which is instead is operated on to guard against the rest of the structure being used. However this causes a memory leak: we need someway to release this sentinel pointer. Is there a way to register a callback with LabVIEW such that when whatever VI hierarchy goes idle which started this whole mess, we can invoke some code to release the sentinel? I imagine registering sentinel pointers somewhere, and when the callback is invoked releasing them.

 

The issue of the pointer being released while a read/write is stuck in its polling loop also needs to be addressed. If someone splits a wire and manages to block a read/write call while uninit is called bad things will happen. We may have to build a lock into read/write that is shared with uninit. Don't panic, I don't mean a traditional LabVIEW lock-- I think we can do this with another pointer. Here's my logic. Say we have our private data as something like this (ignoring the buffer proper since it's not part of the discussion):

<snip>

Of course for any of that to work, we need atomic operations on the move/swap calls. Rolf's earlier statements worry me that we don't have that. Is there some low level function/instruction we have in LabVIEW that can be used to implement something like this? I've never delved so greedily in to the depths of LabVIEW before...

I think I will pretty much be echoing what others are saying when I say DSCheclPtr isn't even worth being a function. The only thing it seems to check is if it is not-null (pass in "1" and it will pass). Not surprising really, it's the same problem in C.

Any pointer checking is probably not going to yield a robust method. The method I described earlier works really well. It doesn't rely on the readers or writers trying to detect pointers. It relies on not being able to deallocate until everything has finished using them. This raises a slightly different issue though.

It works great for asynchronous deallocation as long as the readers and writers are able to propagate their state. In a while loop this is fine as an extra iteration is possible so that they can read the registration bit and un-set their active bit. Not so good for the fixed for-loops though as the extra iteration cannot happen if you wait until all have completed their full number of iterations (works ok before then though).

Edited July 14, 2013 by ShaunR

[Aristos Queue]

There is no point in adding a first call flag to the pointer block. That would require shift registers in the users code. Although you have added it, you haven't actually used it have you?

Yes I have used it. No, there's no need for shift registers in the user's code. It is used in the Write VI. Without it, your code hangs when Write is called with a second pointer block. The Writers 2nd Call pointer block is needed *per pointer block*. It is not a First Call for the function itself. It records whether or not the newly initialized block has ever been written to.

 

 

This is a very interesting problem. Well for me it is. While a DSCheckPtr call would help in that specific case, It wouldn't likely be robust if LabVIEW is in the habit of regularly recycling memory as might be done in a real application.

 

 

There are only two known solutions that I can find in any literature ... the refnum solution and the compare-and-set-atomic-instruction solution, both of which I described earlier. The refnum solution cannot be used in this case because of the locks it introduces. That leaves us with CAS and a pointer block that cannot ever be fully deallocated while the application is running.

 

[EDIT] I should point out that the refnum solution is essentially equivalent to the DSPtrCheck coupled with a guarantee of no reallocation of an already-used refnum.

[Aristos Queue]

I cleaned up a lot of wiring and layout in Version 4 to make the code more accessible to others -- making wires easier to follow, that sort of thing.

 

In this version, I put the class layer in to replace the raw pointer block.

Circular_BufferV5_AQ.zip

I'm done making modifications until we can figure out the CAS issue which I consider to be a showstopper to this framework making any further progress. Without a solution to that, there's the potential that this whole mechanism will have to be scrapped in favor of something very different (perhaps a library that implements exactly one disruptor and there can't be dynamic instantiation or some equally radical change).  I'll talk to co-workers on Monday, though it might be later in the week before I get back to this.