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]

Date:	Wed, 6 Apr 2016 13:39:22 +0000 (UTC)
From:	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
To:	Peter Zijlstra <peterz@...radead.org>
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 Apr 6, 2016, at 3:43 AM, Peter Zijlstra peterz@...radead.org wrote:

> 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?

No, you're right. I entirely missed the role of check_ptr and
check_val in rseq_percpu_cmpxchgcheck. That indeed ensures we
atomically check, from a per-cpu perspective, that both the
pointer we are about to update and the next pointer are still
the same. Mystery solved. :-)

And of course, for the percpu_list_push(), the rseq_percpu_cmpxchg()
there is enough, because we always try to add a node we own into
the list, and only ever compare to the head. This one is
straightforwardly ABA-free even without rseq.

There is still the question of use-after-free however that
remains open. My understanding is that this lock-free list
should be paired with either a type-safe memory allocator,
using RCU, or a garbage collector.

Thoughts ?

Thanks,

Mathieu


-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com