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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Thu, 27 Jun 2019 00:53:15 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     John Ogness <john.ogness@...utronix.de>
Cc:     linux-kernel@...r.kernel.org, Petr Mladek <pmladek@...e.com>,
        Sergey Senozhatsky <sergey.senozhatsky.work@...il.com>,
        Steven Rostedt <rostedt@...dmis.org>,
        Linus Torvalds <torvalds@...ux-foundation.org>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
        Andrea Parri <andrea.parri@...rulasolutions.com>,
        Thomas Gleixner <tglx@...utronix.de>,
        Sergey Senozhatsky <sergey.senozhatsky@...il.com>
Subject: Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer
 implementation

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;
> 	}