Date: Fri, 1 Apr 2016 21:32:22 +0000 (UTC)
From: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
To: Peter Hurley <peter@hurleysoftware.com>
Cc: Huang Ying <ying.huang@intel.com>,
        Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
        "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>,
        Andi Kleen <ak@linux.intel.com>,
        "David S. Miller" <davem@davemloft.net>,
        lkml <linux-kernel@vger.kernel.org>
Message-ID: <895607180.43531.1459546342768.JavaMail.zimbra@efficios.com>
In-Reply-To: <56FD2D1B.2010208@hurleysoftware.com>
References: <513177315.41302.1459417186529.JavaMail.zimbra@efficios.com> <1934237589.41303.1459417221186.JavaMail.zimbra@efficios.com> <56FD2D1B.2010208@hurleysoftware.com>
Subject: Re: Possible ABA in use of llist.h llist_del_first() in tty_buffer
 and ib_rdma
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Thread-Topic: Possible ABA in use of llist.h llist_del_first() in tty_buffer and ib_rdma
Thread-Index: HAVUEoYep1Kae0psITDjmAH4xUW5/A==
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 2984
Lines: 94

----- On Mar 31, 2016, at 9:58 AM, Peter Hurley peter@hurleysoftware.com wrote:

> 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@efficios.com 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.

This one looks OK indeed.

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

I see that tty_buffer_request_room is an exported symbol, and no
documentation indicate that it should never be called concurrently
for a struct tty_port. Also, there does not appear to be any locking
within this function preventing concurrent execution on a struct tty_port.
Is there some documentation about this interface that I am missing ?

If it's possible to call llist_del_first() concurrently, then we can run
into ABA scenarios, even if llist_add() is protected from concurrent
llist_add() by a lock.

Thanks,

Mathieu


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

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