Understanding Linux Kernel Circular Buffer

dicroce picture dicroce · Jan 17, 2013 · Viewed 12.7k times · Source

There is an article at: http://lwn.net/Articles/378262/ that describes the Linux kernels circular buffer implementation. I have some questions:

Here is the "producer":

spin_lock(&producer_lock);

unsigned long head = buffer->head;
unsigned long tail = ACCESS_ONCE(buffer->tail);

if (CIRC_SPACE(head, tail, buffer->size) >= 1) {
    /* insert one item into the buffer */
    struct item *item = buffer[head];

    produce_item(item);

    smp_wmb(); /* commit the item before incrementing the head */

    buffer->head = (head + 1) & (buffer->size - 1);

    /* wake_up() will make sure that the head is committed before
     * waking anyone up */
    wake_up(consumer);
}

spin_unlock(&producer_lock);

Questions:

  1. Since this code explicitly deals with memory ordering and atomicity what is the point of the spin_lock()?
  2. So far, my understanding is that ACCESS_ONCE stops compiler reordering, true?
  3. Does produce_item(item) simply issue all of the writes associated with the item?
  4. I believe smp_wmb() guarantees that all of the writes in produce_item(item) complete BEFORE the "publishing" write that follows it. true?
  5. The commentary on the page where I got this code seems to imply that a smp_wmb() would normally be needed after updating the head index, but wake_up(consumer) does this, so its not necessary. Is that true? If so why?

Here is the "consumer":

spin_lock(&consumer_lock);

unsigned long head = ACCESS_ONCE(buffer->head);
unsigned long tail = buffer->tail;

if (CIRC_CNT(head, tail, buffer->size) >= 1) {
    /* read index before reading contents at that index */
    smp_read_barrier_depends();

    /* extract one item from the buffer */
    struct item *item = buffer[tail];

    consume_item(item);

    smp_mb(); /* finish reading descriptor before incrementing tail */

    buffer->tail = (tail + 1) & (buffer->size - 1);
}

spin_unlock(&consumer_lock);

Questions specific to "consumer":

  1. What does smp_read_barrier_depends() do? From some comments in a forum it seems like you could have issued an smp_rmb() here, but on some architectures this is unnecessary (x86) and too expensive, so smp_read_barrier_depends() was created to do this optionally... That said, I don't really understand why smp_rmb() is ever necessary!
  2. Is the smp_mb() there to guarantee that all of the reads before it complete before the write after it?

Answer

Hasturkun picture Hasturkun · Jan 17, 2013

For the producer:

  1. The spin_lock() here is to prevent two producers from trying to modify the queue at the same time.
  2. ACCESS_ONCE does prevent reordering, it also prevents the compiler from reloading the value later. (There's an article about ACCESS_ONCE on LWN that expands on this further)
  3. Correct.
  4. Also correct.
  5. The (implied) write barrier here is needed before waking the consumer as otherwise the consumer might not see the updated head value.

Consumer:

  1. smp_read_barrier_depends() is a data dependency barrier, which is a weaker form of a read barrier (see 2). The effect in this case is to ensure that buffer->tail is read before using it as an array index in buffer[tail].
  2. smp_mb() here is a full memory barrier, ensuring all reads and writes are committed by this point.

Additional references:

(Note: I'm not entirely sure about my answers for 5 in the producer and 1 for the consumer, but I believe they're a fair approximation of the facts. I highly recommend reading the documentation page about memory barriers, as it's more comprehensive than anything I could write here.)