----- On Apr 6, 2016, at 3:43 AM, Peter Zijlstra peterz@xxxxxxxxxxxxx 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
--
To unsubscribe from this list: send the line "unsubscribe linux-api" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
