Re: Possible ABA in use of llist.h llist_del_first() in tty_buffer and ib_rdma

[Peter Hurley]

Hi Mathieu,

On 03/31/2016 02:40 AM, Mathieu Desnoyers wrote:
> CCing LKML.
> 
> ----- On Mar 31, 2016, at 5:39 AM, Mathieu Desnoyers mathieu.desnoyers@xxxxxxxxxxxx wrote:
> 
>> Hi,
>>
>> Code review (really: grepping the Linux kernel for
>> llist_del_first) leads me to notice two possible ABA issues.
>> The first one is in drivers/tty/tty_buffer.c, and is due to
>> its use of llist_del_all and llist_del_first without locking
>> since commit 809850b7a5 "tty: Use lockless flip buffer free list".
>>
>> Unfortunately, it appears to do so without respecting the
>> locking requirements associated with llist_del_first.
>>
>> Quoting llist.h:
>>
>> " * If there are multiple producers and one consumer, llist_add can be
>> * used in producers and llist_del_all or llist_del_first can be used
>> * in the consumer.

The use of llist_del_all in tty_buffer_free_all() is not concurrent with
any other use of the free list; the comments for tty_buffer_free_all() even
note the special condition.

Only the llist_del_first() and llist_add() usage are concurrent, and fwiw,
that usage is single-producer/single-consumer.

Regards,
Peter Hurley

>> * This can be summarized as follow:
>> *
>> *           |   add    | del_first |  del_all
>> * add       |    -     |     -     |     -
>> * del_first |          |     L     |     L
>> * del_all   |          |           |     -
>> *
>> * Where "-" stands for no lock is needed, while "L" stands for lock
>> * is needed.
>> "
>>
>> As soon as a llist_del_first() is used, then both llist_del_first()
>> and llist_del_all() need to be protected by a lock, thus preventing
>> ABA in llist_del_first().
>>
>> An alternative to locking would be to only use llist_del_all() and
>> never llist_del_first().
>>
>> I'm also noticing a similar concurrent use of llist_del_first() and
>> llist_del_all() in commit 1bc144b625 "net, rds, Replace xlist in net/rds/xlist.h
>> with llist".
>> The locking surrounding their use (especially in rds_ib_reuse_mr)
>> don't appear clearly documented there. Perhaps there was a preexisting
>> issue with the xlist.h use too ?
>>
>> Thanks,
>>
>> Mathieu
>>
>> --
>> Mathieu Desnoyers
>> EfficiOS Inc.
>> http://www.efficios.com
>