Jump to content
  • Advertisement
Sign in to follow this  
BradDaBug

Unity Critique my lockless queue, Part II

This topic is 3170 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This is kind of a continuation of this thread. I found this GDC 2008 presentation from Microsoft where the presenter defines "channels" as a way to do IPC. He specifies some rules the channels must follow: * Writes are atomic and non-blocking * Reads block if queue empty * Supports multiple readers: each message is read once and only once Judging from his code examples in other places in the presentation it looks like channels are also expected to be able to support multiple writers in different threads too. He mentions using XLockFreeQueue as a way to implement channels (I don't have an XDK, so I don't know any of the guarantees the XLockFreeQueue makes or how it works), or that a deque and a semaphore could also work on Windows. Well, I couldn't figure out how to make a deque threadsafe without using locks and whatnot, so I made this... It's a LIFO stack implemented with a singly-linked list! Okay, it's not really a queue, but like I said, I couldn't figure out how to make a lock-free queue that followed the rules of the "channel," so I went back to something simpler and made this.
template<typename T>
class MessageStack
{
    struct Node
    {
        volatile Node* Next;
        T Data;
    };

    volatile Node* m_head;
    SDL_sem* m_semaphore;


public:
    MessageStack()
    {
        m_semaphore = SDL_CreateSemaphore(0);
        m_head = NULL;
    }

    ~MessageStack()
    {
        SDL_DestroySemaphore(m_semaphore);

        while(m_head != NULL)
        {
            volatile Node* n = m_head;
            m_head = m_head->Next;

            _aligned_free((void*)n);
        }
    }

    void AddMessage(T message)
    {
        Node* n = (Node*)_aligned_malloc(sizeof(Node), sizeof(void*));
        n->Data = message;

        while(true)
        {
            n->Next = m_head;
            
            if (InterlockedCompareExchangePointer((volatile PVOID*)&m_head, n, (void*)n->Next) == n->Next)
                break;
        }
        
        // let any waiting readers know there's an available node
        SDL_SemPost(m_semaphore);
    }

    // blocks until a message is available, and then removes it from the list
    T RemoveMessage()
    {
        // block the reader until we have something available
        SDL_SemWait(m_semaphore);

        volatile Node* n = NULL;
        while(true)
        {
            n = m_head;

            if (InterlockedCompareExchangePointer((volatile PVOID*)&m_head, (void*)m_head->Next, (void*)n) == n)
                break;
        }

        T t = n->Data;
        _aligned_free((void*)n);

        return t;
    }

    // attempts to get the next message, but won't block.
    // returns true if a message was received, false otherwise
    bool TryRemoveMessage(T* message)
    {
        if (SDL_SemTryWait(m_semaphore) == 0)
        {
            volatile Node* n = NULL;
            while(true)
            {
                n = m_head;

                if (InterlockedCompareExchangePointer((volatile PVOID*)&m_head, (void*)m_head->Next, (void*)n) == n)
                    break;
            }

            *message = n->Data;
            _aligned_free((void*)n);

            return true;
        }

        return false;
    }
};
It uses a semaphore (I happened to use SDL instead of Win32, but the basic semaphore operations should be obvious) to make the reader block if there is nothing in the list to read. I think it meets all the requirements of a "channel." So how does it look?

Share this post


Link to post
Share on other sites
Advertisement
Which compiler(s) are you targeting? volatile means different things to different compilers.

For this reason, I'm even tempted to make the somewhat more blankety statement that using volatile qualification should be viewed as a bug.

Share this post


Link to post
Share on other sites
Right now I'm just focused on Visual C++ 2005 and 2008.

InterlockedCompareExchangePointer() requires volatile pointers for the first parameter. Why wouldn't I want to use volatile?

Share this post


Link to post
Share on other sites
Quote:
Original post by swiftcoder
Quote:
Original post by BradDaBug
Why wouldn't I want to use volatile?
Required reading on the topic.

In your case, volatile is likely doing exactly what you intend it to, but this usage isn't portable.


Agreed.

OP: If you're putting together lock-free code, it's super important that you know what volatile really means, or rather, know what it really doesn't mean.

For this reason, I would recommend that you add pre-processor checks to ensure that the code is only compiled with Visual C++ 2005 or later, if you intend to distribute code in source form.

It will fall apart with a number of other compilers. Even better, re-write the code such that volatile isn't needed (by inserting the assumed fences and so on explicitly).

Share this post


Link to post
Share on other sites
volatile is required for variables to be used with the Interlocked* functions only to ensure the compiler doesn't re-order (or otherwise optimise) reads and writes to the variable.
Any call to an Interlocked* function will create the required memory fence to ensure that none of these optimisations occur at run-time.

AFAIK, this usage of volatile should be portable across any compiler.

BradDaBug's code doesn't seem (I'd have to look closer to make sure!) to rely on the non-standard behaviour of volatile adding memory-fences -- the interlocked API does that for him (and this API requires your variable to be marked volatile, otherwise the fence would be useless if the compiler is going to reorder things anyway!).

Share this post


Link to post
Share on other sites
Quote:
Original post by Hodgman
volatile is required for variables to be used with the Interlocked* functions only to ensure the compiler doesn't re-order (or otherwise optimise) reads and writes to the variable.
Any call to an Interlocked* function will create the required memory fence to ensure that none of these optimisations occur at run-time.

AFAIK, this usage of volatile should be portable across any compiler.

BradDaBug's code doesn't seem (I'd have to look closer to make sure!) to rely on the non-standard behaviour of volatile adding memory-fences -- the interlocked API does that for him (and this API requires your variable to be marked volatile, otherwise the fence would be useless if the compiler is going to reorder things anyway!).



You're contradicting yourself. First you say that the usage of volatile to ensure that the compiler doesn't re-order access should be portable, then you say it's nonstandard behavior of volatile adding memory fences. That's exactly what memory fences are for, making sure operations aren't re-ordered.

FWIW, it's Microsoft specific behavior, and as far as the C++ standard goes, it says nothing about re-ordering or anything of the sort. volatile is almost completely useless if you're only interested in it's standard defined behavior.

Share this post


Link to post
Share on other sites
Bob pendleton has added some preliminary support for more low level multithreading primitives for SDL 1.3, analogous to InterlockedCompareExchange etc You might find it interesting.

Share this post


Link to post
Share on other sites
Quote:
Original post by cache_hit
Quote:
Original post by Hodgman
volatile is required for variables to be used with the Interlocked* functions only to ensure the compiler doesn't re-order (or otherwise optimise) reads and writes to the variable.
Any call to an Interlocked* function will create the required memory fence to ensure that none of these optimisations occur at run-time.

AFAIK, this usage of volatile should be portable across any compiler.

BradDaBug's code doesn't seem (I'd have to look closer to make sure!) to rely on the non-standard behaviour of volatile adding memory-fences -- the interlocked API does that for him (and this API requires your variable to be marked volatile, otherwise the fence would be useless if the compiler is going to reorder things anyway!).
You're contradicting yourself. First you say that the usage of volatile to ensure that the compiler doesn't re-order access should be portable, then you say it's nonstandard behavior of volatile adding memory fences. That's exactly what memory fences are for, making sure operations aren't re-ordered.

FWIW, it's Microsoft specific behavior, and as far as the C++ standard goes, it says nothing about re-ordering or anything of the sort. volatile is almost completely useless if you're only interested in it's standard defined behavior.
Nope, Hodgman is correct. The key here is that the 'volatile' keyword isn't doing much of anything - it is merely a requirement of the Interlocked* functions. The Interlocked* functions themselves handle the memory fences, so the code as it stands is perfectly valid.

Equally, the reason it isn't portable has nothing to do with the use of volatile - instead it is the fact that the Interlocked* functions are Windows-specific.

Share this post


Link to post
Share on other sites
Quote:
Original post by swiftcoder
Nope, Hodgman is correct. The key here is that the 'volatile' keyword isn't doing much of anything - it is merely a requirement of the Interlocked* functions. The Interlocked* functions themselves handle the memory fences, so the code as it stands is perfectly valid.

Equally, the reason it isn't portable has nothing to do with the use of volatile - instead it is the fact that the Interlocked* functions are Windows-specific.


Maybe I'm misreading his sentence, but this is what I see.

Quote:

volatile is required for variables to be used with the Interlocked* functions only to ensure the compiler doesn't re-order (or otherwise optimise) reads and writes to the variable.

...

AFAIK, this usage of volatile should be portable across any compiler.


According to the standard, volatile has nothing to do with whether or not a compiler re-orders reads or writes to a variable. It's required because a) the function signature demands it, and b) it just so happens that msvc does use memory fences on volatile accesses. But I still dont' see anything "portable" about this usage of volatile at all.

Am I missing something?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!