Subject: Re: Possible ABA in use of llist.h llist_del_first() in tty_buffer
 and ib_rdma
To: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
References: <513177315.41302.1459417186529.JavaMail.zimbra@efficios.com>
 <1934237589.41303.1459417221186.JavaMail.zimbra@efficios.com>
 <56FD2D1B.2010208@hurleysoftware.com>
 <895607180.43531.1459546342768.JavaMail.zimbra@efficios.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>
From: Peter Hurley <peter@hurleysoftware.com>
Message-ID: <56FF095E.8030604@hurleysoftware.com>
Date: Fri, 1 Apr 2016 16:50:54 -0700
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101
 Thunderbird/38.6.0
MIME-Version: 1.0
In-Reply-To: <895607180.43531.1459546342768.JavaMail.zimbra@efficios.com>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 2867
Lines: 73

On 04/01/2016 02:32 PM, Mathieu Desnoyers wrote:
> ----- On Mar 31, 2016, at 9:58 AM, Peter Hurley peter@hurleysoftware.com wrote:
>> 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 ?

There is little to no documentation on the tty flip buffer interface,
so you're not missing anything there.

The driver-side flip buffer interface is purely single-threaded;
it is exclusively called from interrupt handlers and single-threaded
bottom halves.

None of the functions are atomic, nor is the interface design.

For example, ignoring tty_buffer_request_room() for a moment, consider
how broken concurrent use of tty_insert_flip_string_flags() would be;
input from multiple threads would be overwritten/lost/mixed.

The interface itself is not atomic because tty_flip_buffer_push()
marks the conclusion of input and the hand-off to kworker, which may
already be running at the time.

The tty core doesn't support multi-channel input directly; the driver
is expected to deliver input from each channel to a separate tty,
or mux the inputs before tty_insert_flip_string_fixed_flag().


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

And way more obvious problems than that, such as I wrote above,
if used concurrently.

Regards,
Peter Hurley