Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation

[Peter Zijlstra]

On Thu, Jun 27, 2019 at 12:40:34AM +0200, Peter Zijlstra wrote:
> You have a single linked list going from the tail to the head, while
> adding to the head and removing from the tail. And that sounds like a
> FIFO queue:
> 
> 	struct lqueue_head {
> 		struct lqueue_node *head, *tail;
> 	};
> 
> 	struct lqueue_node {
> 		struct lqueue_node *next;
> 	};
> 
> 	void lqueue_push(struct lqueue_head *h, struct lqueue_node *n)
> 	{
> 		struct lqueue_node *prev;
> 
> 		n->next = NULL;
> 		/*
> 		 * xchg() implies RELEASE; and thereby ensures @n is
> 		 * complete before getting published.
> 		 */
> 		prev = xchg(&h->head, n);
> 		/*
> 		 * xchg() implies ACQUIRE; and thereby ensures @tail is
> 		 * written after @head, see lqueue_pop()'s smp_rmb().
> 		 */
> 		if (prev)
> 			WRITE_ONCE(prev->next, n);
> 		else
> 			WRITE_ONCE(h->tail, n);
> 	}
> 
> 	struct lqueue_node *lqueue_pop(struct lqueue_head *h)
> 	{
> 		struct lqueue_node *head, *tail, *next;
> 
> 		do {
> 			tail = READ_ONCE(h->tail);
> 			/* If the list is empty, nothing to remove. */
> 			if (!tail)
> 				return NULL;
> 
> 			/*
> 			 * If we see @tail, we must then also see @head.
> 			 * Pairs with the xchg() in lqueue_push(),
> 			 * ensure no false positive on the singleton
> 			 * test below.

or is it false negative?, I'm too tired to think staight. What can
happen without the rmb is that the head load can get hoisted over the
tail load and then observe a NULL head and a !NULL tail and thus head !=
tail and we think there's multiple entries on the list and stuff goes
wobbly.

> 			 */
> 			smp_rmb();
> 			head = READ_ONCE(h->head);
> 
> 			/* If there is but one item; fail to remove. */
> 			if (head == tail)
> 				return NULL;
> 
> 			next = smp_cond_load_relaxed(&tail->next, VAL);
> 
> 		} while (cmpxchg(h->tail, tail, next) != tail);
> 
> 		return tail;
> 	}