Message-ID: <20110904205009.GA19876@Krystal>
Date:	Sun, 4 Sep 2011 16:50:09 -0400
From:	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
To:	Andi Kleen <andi@...stfloor.org>
Cc:	LKML <linux-kernel@...r.kernel.org>,
	Peter Zijlstra <peterz@...radead.org>,
	Huang Ying <ying.huang@...el.com>, lenb@...nel.org,
	Andrew Morton <akpm@...ux-foundation.org>,
	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
Subject: Re: [RFC patch 1/2] Rename the "llist" (lockless list) to
	"llstack" (lockless stack)

Hi Andi,

* Andi Kleen (andi@...stfloor.org) wrote:
> 
> I don't see why a rename is necessary. People implement stacks and queues
> and all other kinds of data structures using the standard list.h.
> No reason why this shouldn't work with llist.h either.

What you are saying here is only partially true. Gien that Linux
supports multiprocessing, people implement stack ans queues with list.h
_and_ mutual exclusion (spin locks, mutexes, rwlocks) for SMP
synchronization.

The flexibility of list.h combined with the flexibility of mutual
exclusion synchronisation primitives allow people to implement basically
all the list-based data structure they feel like implementing, with the
known performance downsides of mutual exclusion: only one thread can
touch the data structure at a given time, and touching the mutex adds
cache-line bouncing. It's also not permitted to use mutual exclusion in
NMI handlers.

However, in the realm of lock-free data structures, things are very much
different. Synchronization can be performed in a much more fine-grained
fashion and the data structure is tailored to the needed
synchronization, which enables performance enhancements not possible
with mutual-exclusion techniques. The lock-free queue is a good example
(FIFO behavior):

With list.h and mutexes, you would implement this queue very
straightforwardly using:

DEFINE_MUTEX(somemutex);
LIST_HEAD(somelist);

And then protect all list_add_tail (enqueue) operations and list_del of
list_first_entry (dequeue) operations with the mutex.

A lock-free queue has come very interesting advantages compared to the
mutex-protected queue. One of them being that if the queue list
structure is crafted appropriately, enqueuer and dequeuer threads can
concurrently enqueue and dequeue elements to/from the queue without
wrestling for the same cache-line (when there is at least one element in
the queue, which is usually the case when high-throughput matters).

Now some words about stacks (LIFO behavior):

You can indeed implement stacks with mutex/list.h by using list_add
(push) and list_del of list_first_entry (pop) protected by a mutex, with
the downside of having to touch both the mutex and the list head for
each of these operations. Also, this is not safe to use in NMI handlers,
which seems to be a use-case NMI handler implementors are facing
(which is I think what motivated the implementation of llist.h in the
first place).

A lock-free stack lets you do this with a single cmpxchg on the push,
and an xchg on the "pop all" (there are also variants that can use a
xchg() on the push). In addition, it lets you return whether the stack
was empty when performing the push operation, which is a feature quite
useful to know if a wakeup should be triggered or not.

But the data structures required to implement a lock-free queue and a
lock-free stack differ quite significantly: some ways to implement a
lock-free queue require either special sequence numbering of both ends,
or dummy elements that ensures the queue is never empty. The lock-free
stack can be implemented by putting a NULL bottom node to detect the end
of stack. Moreover, even though the stack "push" operation can return
whether the stack was previously empty at no cost, it is not true for
the queue, because this would require the enqueuer to touch the dequeuer
cache-lines.


> I would assume everyone hacking on the Linux kernel will understand
> that a list can be used as a building block for all of these.

Although strictly speaking this is true, I'm afraid a single "generic"
list container would be at best a building block for either efficient
lock-free queues or stacks, but not both.

This is why I'm proposing to turn the generic "llist.h" namespace into
the more specific "llstack.h", so the API reflects not only the basic
list structure, but also the exposed behavior and the implicit
synchronization performed within this API, because those are
intrinsically linked to the data structure layout, unlike
mutual-exclusion-based approaches.

Best regards,

Mathieu

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists