Skip to main content
deleted 249 characters in body
Source Link
G. Sliepen
  • 65.7k
  • 3
  • 67
  • 165

Be careful claiming it is wait-free

You claim your queue is wait-free, but you have a potentially unbounded for-loop doing a compare-exchange operation. At the very least, this means consumer_get_head() and consumer_get_tail() are's time complexity is actually \$O(N)\$ operations. Sure, you are unlikely to hit that case, but the whole point of a wait-free algorithm is that you never have to wait.

Access to the data is not atomicConfusing API

WhenThe API is very confusing. As you call producer_force_put(), it finds the next empty spotmention in the queue, updates the indices, and then returns a pointer to the actual data in msgs_buffer. Howevercomments, before the producer can actually writealready has to that spot via thatknow the pointer, to the consumer could already start reading it.

Similarlyfirst free element, when the consumer callsand then consumer_get_tailproducer_force_put(), it marks the tail will mark that element as consumed, updates the tail index,produced and then returns a pointer to the datanext free element. HoweverAnd something similar is going on with the consumer functions. For me, before it can read from that date,was very unexpected. It also means the producer could already overwrite itcaller now shares some of the bookkeeping.

To solve this issue, you need to ensure the producer gets a chance to write and the consumer gets a chance to read before updating the indices. This can be done by splitting access in two stages; for example for the producer,I would rather have a function to getproducer_get_head() that returns a pointer to the first empty spot in the queuefree element, then haveand a second functionproducer_force_get_head() to update the indicesforce it to free up an element if there is none, and signalthen a producer_put() that returns void and that merely marks the data is now ready to be readelement as produced and increments the head index.

Be careful claiming it is wait-free

You claim your queue is wait-free, but you have a potentially unbounded for-loop doing a compare-exchange operation. At the very least, this means consumer_get_head() and consumer_get_tail() are actually \$O(N)\$ operations. Sure, you are unlikely to hit that case, but the whole point of a wait-free algorithm is that you never have to wait.

Access to the data is not atomic

When you call producer_force_put(), it finds the next empty spot in the queue, updates the indices, and then returns a pointer to the actual data in msgs_buffer. However, before the producer can actually write to that spot via that pointer, the consumer could already start reading it.

Similarly, when the consumer calls consumer_get_tail(), it marks the tail as consumed, updates the tail index, and then returns a pointer to the data. However, before it can read from that date, the producer could already overwrite it.

To solve this issue, you need to ensure the producer gets a chance to write and the consumer gets a chance to read before updating the indices. This can be done by splitting access in two stages; for example for the producer, have a function to get a pointer to the first empty spot in the queue, then have a second function to update the indices and signal that the data is now ready to be read.

Be careful claiming it is wait-free

You claim your queue is wait-free, but you have a potentially unbounded for-loop doing a compare-exchange operation. At the very least, this means consumer_get_head()'s time complexity is actually \$O(N)\$. Sure, you are unlikely to hit that case, but the whole point of a wait-free algorithm is that you never have to wait.

Confusing API

The API is very confusing. As you mention in the comments, the producer already has to know the pointer to the first free element, and then producer_force_put() will mark that element as produced and returns a pointer to the next free element. And something similar is going on with the consumer functions. For me, that was very unexpected. It also means the caller now shares some of the bookkeeping.

I would rather have a function producer_get_head() that returns a pointer to the first free element, and a producer_force_get_head() to force it to free up an element if there is none, and then a producer_put() that returns void and that merely marks the element as produced and increments the head index.

Source Link
G. Sliepen
  • 65.7k
  • 3
  • 67
  • 165

Be careful claiming it is wait-free

You claim your queue is wait-free, but you have a potentially unbounded for-loop doing a compare-exchange operation. At the very least, this means consumer_get_head() and consumer_get_tail() are actually \$O(N)\$ operations. Sure, you are unlikely to hit that case, but the whole point of a wait-free algorithm is that you never have to wait.

Access to the data is not atomic

When you call producer_force_put(), it finds the next empty spot in the queue, updates the indices, and then returns a pointer to the actual data in msgs_buffer. However, before the producer can actually write to that spot via that pointer, the consumer could already start reading it.

Similarly, when the consumer calls consumer_get_tail(), it marks the tail as consumed, updates the tail index, and then returns a pointer to the data. However, before it can read from that date, the producer could already overwrite it.

To solve this issue, you need to ensure the producer gets a chance to write and the consumer gets a chance to read before updating the indices. This can be done by splitting access in two stages; for example for the producer, have a function to get a pointer to the first empty spot in the queue, then have a second function to update the indices and signal that the data is now ready to be read.