linux-kernel - Re: [RFC PATCH v2 3/3] restartable sequences: basic self-tests

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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <20160406074309.GE3430@twins.programming.kicks-ass.net>
Date:	Wed, 6 Apr 2016 09:43:09 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Cc:	Paul Turner <commonly@...il.com>, Andrew Hunter <ahh@...gle.com>,
	Andy Lutomirski <luto@...capital.net>,
	Andi Kleen <andi@...stfloor.org>,
	Dave Watson <davejwatson@...com>,
	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>,
	linux-api <linux-api@...r.kernel.org>,
	linux-kernel@...r.kernel.org,
	Josh Triplett <josh@...htriplett.org>,
	Ingo Molnar <mingo@...hat.com>, Chris Lameter <cl@...ux.com>,
	Linus Torvalds <torvalds@...ux-foundation.org>
Subject: Re: [RFC PATCH v2 3/3] restartable sequences: basic self-tests

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?