From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <linux-kernel-owner@vger.kernel.org>
Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand
	id S1758111AbcDFHnZ (ORCPT <rfc822;w@1wt.eu>);
	Wed, 6 Apr 2016 03:43:25 -0400
Received: from bombadil.infradead.org ([198.137.202.9]:44603 "EHLO
	bombadil.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org
	with ESMTP id S1752476AbcDFHnX (ORCPT
	<rfc822;linux-kernel@vger.kernel.org>);
	Wed, 6 Apr 2016 03:43:23 -0400
Date: Wed, 6 Apr 2016 09:43:09 +0200
From: Peter Zijlstra <peterz@infradead.org>
To: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: Paul Turner <commonly@gmail.com>, Andrew Hunter <ahh@google.com>,
        Andy Lutomirski <luto@amacapital.net>,
        Andi Kleen <andi@firstfloor.org>, Dave Watson <davejwatson@fb.com>,
        "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>,
        linux-api <linux-api@vger.kernel.org>, linux-kernel@vger.kernel.org,
        Josh Triplett <josh@joshtriplett.org>, Ingo Molnar <mingo@redhat.com>,
        Chris Lameter <cl@linux.com>,
        Linus Torvalds <torvalds@linux-foundation.org>
Subject: Re: [RFC PATCH v2 3/3] restartable sequences: basic self-tests
Message-ID: <20160406074309.GE3430@twins.programming.kicks-ass.net>
References: <20151027235635.16059.11630.stgit@pjt-glaptop.roam.corp.google.com>
 <20151027235716.16059.47610.stgit@pjt-glaptop.roam.corp.google.com>
 <1276514010.46061.1459888406999.JavaMail.zimbra@efficios.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <1276514010.46061.1459888406999.JavaMail.zimbra@efficios.com>
User-Agent: Mutt/1.5.21 (2012-12-30)
Sender: linux-kernel-owner@vger.kernel.org
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

On Tue, Apr 05, 2016 at 08:33:27PM +0000, Mathieu Desnoyers wrote:

> A problematic execution sequence would be
> 
> * Exhibit A: ABA (all threads running on same CPU):
> 
> Initial state: the list has a single entry "object Z"
> 
>        Thread A                       Thread B
> - percpu_list_pop()
>   - cpu = rseq_current_cpu();
>   - head = list->heads[cpu];
>     (head is a pointer to object Z)
>   - next = head->next;
>   (preempted)
>                                       (scheduled in)
>                                       - percpu_list_pop()
>                                         - cpu = rseq_current_cpu();
>                                         - head = list->heads[cpu];
>                                           (head is a pointer to object Z)
>                                         - rseq_percpu_cmpxchgcheck succeeds
>                                       - percpu_list_push of a new object Y
>                                       - percpu_list_push of a re-used object Z
>                                         (its next pointer now points to object Y
>                                         rather than end of list)
>                                       (preempted)
>   (scheduled in)
>   - rseq_percpu_cmpxchgcheck succeeds,
>     setting a wrong value into the list
>     head: it will store an end of list,
>     thus skipping over object Y.

OK, so I'm still trying to wake up, but I'm not seeing how
rseq_percpu_cmpxchgcheck() would succeed in this case.

If you look at the code, the 'check' part would fail, that is:

> +struct percpu_list_node *percpu_list_pop(struct percpu_list *list)
> +{
> +	int cpu;
> +	struct percpu_list_node *head, *next;
> +
> +	do {
> +		cpu = rseq_current_cpu();
> +		head = list->heads[cpu];
> +		/*
> +		 * Unlike a traditional lock-less linked list; the availability
> +		 * of a cmpxchg-check primitive allows us to implement pop
> +		 * without concerns over ABA-type races.
> +		 */
> +		if (!head) return 0;
> +		next = head->next;
> +	} while (cpu != rseq_percpu_cmpxchgcheck(cpu,
> +		(intptr_t *)&list->heads[cpu], (intptr_t)head, (intptr_t)next,
> +		(intptr_t *)&head->next, (intptr_t)next));

The extra compare is 'head->next == next', and our thread-A will have
@next == NULL (EOL), while the state after thread-B ran would be
@head->next = &Y.

So the check will fail, the cmpxchg will fail, and around we go.

> +
> +	return head;
> +}

Or am I completely not getting it?