search

xant / libhl

Simple and fast C library implementing a thread-safe API to manage hash-tables, linked lists, lock-free ring buffers and queues
GNU Lesser General Public License v3.0
420 stars 117 forks source link

The lock-free circular queue currently requires one extra page in its internal ringbuffer to work properly #22

Open mingpepe opened 7 years ago

mingpepe commented 7 years ago

The number of successfully read from rqueue sometimes less than the number of successfully write to rqueue.

Here is the test code. https://gist.github.com/mingpepe/9d6ec5f17bdb60094d7fc980df3437ce

But i am not found the bug yet.

xant commented 7 years ago

the threadsanitizer should help identifying the bug ... I'll give a look later this week

xant commented 7 years ago

there is a problem in the algorithm when the tail reaches the head while the head is being updated. I applied a quick fix which should make your test work and make the queue work consistently (for what I have been able to test so far). I had to make some changes to the algorithm though and there is something I don't quite like at the moment : the algorithm now requires size + 1 pages to work properly the writers are now synchronized

I have some ideas on how to change the algorithm to get rid of this two limitations but will probably need some time to code and test those (it's a hectic period).

Even if in theory the race condition shouldn't be there anymore I'll keep this bug open until I'll push those changes

I also included your test in the rqueue unit tests