   another lock free queue
  So after my failed attempt to write a lock-free stack last night, i just tried to write a lock-free queue.The requirement again is one producer thread, one consumer thread, plus the queue has a fixed size.I looked at A Corrected Queue that Hodgman linked me to for reference. Their queue doesn't have a fixed size so i think i can get away with a little simpler approach.I did some tests with the queue by adding a "Sleep(10)" after each line, so that the operations get shuffled nicely and it seemed to work correctly, but the code is so simple and as history proved, the experienced programmers among you will certainly spot the thread safety issues within the blink of an eye:void push(const T& item){if(back->next == front) return;back->item = item;back = back->next;}bool pop(T* item){if(front == back) return false;*item = front->item;front = front->next;return true;}Feedback would be appreciated!   
  Looks fine, but make sure to use proper memory barriers to ensure that the operations aren't reordered. BTW, consider just using an array for the queue. I don't think the circular linked list buys you anything. Well, I guess properly done it could reduce false sharing.   ;Quote:Original post by SneftelLooks fine, but make sure to use proper memory barriers to ensure that the operations aren't reordered. BTW, consider just using an array for the queue. I don't think the circular linked list buys you anything. Well, I guess properly done it could reduce false sharing.Hi Sneftel,Thanks for you feedback, i'm glad you could approve my code for the most part.By "proper memory barriers" do you mean declaring some variables as volatile? If so, which ones should be? Otherwise, which kind of memory barrier would you suggest?I'm trying to think of a way the code could be re-ordered without breaking the logic, but i can't figure it out. Can you show me where the re-ordering could happen?I tried to implement it with an array before but it turned out to be exactly like the Lockless Queue Revision, which wasn't approved as thread safe by Hodgman (because of potential re-ordering also). The linked list version seemed a little more robust to me but maybe i'll give the array approach another chance.Before i forget it: "Well, I guess properly done it could reduce false sharing." Do you mean if the circular linked list is properly done, or the array version?   ;Quote:The linked list version seemed a little more robust to me but maybe i'll give the array approach another chance.This is not a useful lock-free queue. Where do nodes come from? How is new (or any kind of allocator) implemented in multi-threaded environments?There is a reason such queues use pre-allocated storage.Quote:because of potential re-ordering alsoMake head and tail volatile, or use platform-specific read/write barriers.   ;Quote:Original post by AntheusQuote:The linked list version seemed a little more robust to me but maybe i'll give the array approach another chance.This is not a useful lock-free queue. Where do nodes come from? How is new (or any kind of allocator) implemented in multi-threaded environments?There is a reason such queues use pre-allocated storage.For the moment i use the queue to store some pointers. The queue has a fixed size. I'm not sure why you say it's not useful, because i definately have use for such a queue :) But maybe i didn't get the point. I don't plan to write a library for public use or something like that, i'm just trying to enhance my personal project with some optimized data structures, but maybe i should just look into "boost" or something right :)Quote:Make head and tail volatile, or use platform-specific read/write barriers.Thanks pal, I will correct that.I get the feeling that i should resort to external solutions in the future, because thread safety seems to be something i don't like to worry about too much :) It was a nice experience though.   ;Quote:Original post by froopFor the moment i use the queue to store some pointers. The queue has a fixed size. I'm not sure why you say it's not useful, because i definately have use for such a queue :)Where do these pointers come from? If linked list nodes are allocated using new - new is not lock-free. So each new and delete require locking. Even if some lock-free version is used, it still adds another contention point.And if nodes are pre-allocated - that is again a contention point.   ;Quote:Original post by AntheusQuote:Original post by froopFor the moment i use the queue to store some pointers. The queue has a fixed size. I'm not sure why you say it's not useful, because i definately have use for such a queue :)Where do these pointers come from? If linked list nodes are allocated using new - new is not lock-free. So each new and delete require locking. Even if some lock-free version is used, it still adds another contention point.And if nodes are pre-allocated - that is again a contention point.The pointers come from the producer thread. I push a pointer to some object to the queue, which tells the consumer thread what to load from disc or whatever.The circular list created before the queue is used.Let me give you a little fictional code example to show you my usage intentions, and you hopefully teach me why it's not safe :)LocklessQueue queueRequest (1000);LocklessQueue queueFinished(1000);Thread1:void thread1(){   loadFile("1.txt");   loadFile("2.txt");   loadFile("3.txt");}void loadFile(std::string filename){    Request* req  = new Request();    req->filename = filename;    queueRequest.push(req);}void getLoadedFiles(){    Request* req;    while(queueFinished.pop(req))    {    *do something with req*    delete req;    }}Thread2:void thread2(){    Request* req;    while(queueRequest.pop(req))    {    loadFileFromDrive(req->filename);    queueFinishes.push(req);    }}That was written off the top of my head so it certainly contains errors.[Edited by - froop on August 1, 2010 11:46:56 PM];Quote:Original post by froopBy "proper memory barriers" do you mean declaring some variables as volatile?No, this is unrelated to volatile. (volatile provides only a very weak guarantee, and was not intended for multithreading.) The issue is that the compiler is free to optimize things by moving statements around. So it might decide, for instance, to put back->item = item; after back = back->next;, leading to the other thread popping an uninitialized value. Putting a write barrier after the first line would ensure that back does not get incremented until the item is good and written. Google "memory barriers" for more info.Quote:I tried to implement it with an array before but it turned out to be exactly like the Lockless Queue Revision, which wasn't approved as thread safe by Hodgman (because of potential re-ordering also).Waving a linked list at it doesn't address the re-ordering issue. That's what the barriers are for.Quote:Before i forget it: "Well, I guess properly done it could reduce false sharing." Do you mean if the circular linked list is properly done, or the array version?The circular linked list can avoid this. But since the front/back pointers are going to be shared anyway, it really isn't a significant issue.Oh, and also, if push() can fail on overflow then make sure to return that, rather than doing so silently.   ;Quote:Original post by SneftelQuote:Original post by froopBy "proper memory barriers" do you mean declaring some variables as volatile?No, this is unrelated to volatile. Well, not completely.  Reads or writes to volatile variables introduce a "sequence point".   ;Quote:Make head and tail volatile, or use platform-specific read/write barriers.Not OR, AND!Having it volatile only insures everything tries to read/write the origional memory. It doesn't preserve instruction order. And doesn't flush the write queues on the processor, so your writes might not make it out to the cache before another core tries to read it.@froop, you really need to look at all those OS and processor specific instructions that were linked to you in the last thread. Again, nothing in your code is technically "atomic" right now, and so the computer is free to screw with it. And that means, while on the surface it looks fine, it will eventually, randomly, fail.(ie. back=back->next might run, then a full pop, THEN back->item=item. So your pop read out a garbage item.)-edit: Sneftel seems to have beat me to those finer points.