linux-kernel - Re: [PATCH v2 1/3] lib/list_batch: A simple list insertion/deletion batching facility

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Mon, 1 Feb 2016 11:47:08 +1100
From:	Dave Chinner <david@...morbit.com>
To:	Waiman Long <Waiman.Long@....com>
Cc:	Thomas Gleixner <tglx@...utronix.de>,
	Ingo Molnar <mingo@...hat.com>,
	"H. Peter Anvin" <hpa@...or.com>,
	Alexander Viro <viro@...iv.linux.org.uk>,
	linux-fsdevel@...r.kernel.org, x86@...nel.org,
	linux-kernel@...r.kernel.org,
	Peter Zijlstra <peterz@...radead.org>,
	Andi Kleen <andi@...stfloor.org>,
	Scott J Norton <scott.norton@...com>,
	Douglas Hatch <doug.hatch@...com>
Subject: Re: [PATCH v2 1/3] lib/list_batch: A simple list insertion/deletion
 batching facility

On Fri, Jan 29, 2016 at 02:30:44PM -0500, Waiman Long wrote:
> Linked list insertion or deletion under lock is a very common activity
> in the Linux kernel. If this is the only activity under lock, the
> locking overhead can be pretty large compared with the actual time
> spent on the insertion or deletion operation itself especially on a
> large system with many CPUs.
> 
> This patch introduces a simple list insertion/deletion batching
> facility where a group of list insertion and deletion operations are
> grouped together in a single batch under lock. This can reduce the
> locking overhead and improve overall system performance.
> 
> The fast path of this batching facility will be similar in performance
> to the "lock; listop; unlock;" sequence of the existing code. If
> the lock is not available, it will enter slowpath where the batching
> happens.
> 
> A new config option LIST_BATCHING is added so that we can control on
> which architecture do we want to have this facility enabled.
> 
> Signed-off-by: Waiman Long <Waiman.Long@....com>
....
> +#ifdef CONFIG_LIST_BATCHING
> +
> +extern void do_list_batch_slowpath(spinlock_t *lock, enum list_batch_cmd cmd,
> +				   struct list_batch *batch,
> +				   struct list_head *entry);
> +
> +/*
> + * The caller is expected to pass in a constant cmd parameter. As a
> + * result, most of unneeded code in the switch statement of _list_batch_cmd()
> + * will be optimized away. This should make the fast path almost as fast
> + * as the "lock; listop; unlock;" sequence it replaces.
> + */

This strikes me as needlessly complex. Simple inline functions are
much easier to read and verify correct, and we don't have to rely on
the compiler to optimise out dead code:

static inline void list_batch_add(struct list_head *entry,
				  struct list_batch *batch)
{
	if (!spin_trylock(&batch->lock))
		return do_list_batch_slowpath(entry, batch, lb_cmd_add);

	list_add(entry, &batch->list)
	spin_unlock(&batch->lock);
}

> +#include <linux/list_batch.h>
> +
> +/*
> + * List processing batch size = 128
> + *
> + * The batch size shouldn't be too large. Otherwise, it will be too unfair
> + * to the task doing the batch processing. It shouldn't be too small neither
> + * as the performance benefit will be reduced.
> + */
> +#define LB_BATCH_SIZE	(1 << 7)

Ok, so arbitrary operations are going to see longer delays when they
are selected as the batch processor. I'm not sure I really like this
idea, as it will be the first in the queue that sees contention
that takes the delay which reduces the fairness of the operations.
i.e. the spinlock uses fair queuing, but now we can be grossly unfair
the to the first spinner...

> +	/*
> +	 * We rely on the implictit memory barrier of xchg() to make sure
> +	 * that node initialization will be done before its content is being
> +	 * accessed by other CPUs.
> +	 */
> +	prev = xchg(&batch->tail, &node);
> +
> +	if (prev) {
> +		WRITE_ONCE(prev->next, &node);
> +		while (READ_ONCE(node.state) == lb_state_waiting)
> +			cpu_relax();
> +		if (node.state == lb_state_done)
> +			return;

So we spin waiting for the batch processor to process the
list, or

> +		WARN_ON(node.state != lb_state_batch);

tell us we are not the batch processor.

So, effectively, the reduction in runtime is due to the fact the
list operations spin on their own cache line rather than the spin
lock cacheline until they have been processed and/or made the batch
processor?

> +	}
> +
> +	/*
> +	 * We are now the queue head, we should acquire the lock and
> +	 * process a batch of qnodes.
> +	 */
> +	loop = LB_BATCH_SIZE;
> +	next = &node;
> +	spin_lock(lock);
> +
> +do_list_again:
> +	do {

While we are batch processing, all operations will fail the
trylock and add themselves to the tail of the queue, and spin on
their own cacheline at that point. So it doesn't reduce the amount
of spinning, just removes the cacheline contention that slows the
spinning.

Hmmm - there's another point of unfairness - when switching batch
processors, other add/delete operations can get the list lock and
perform their operations directly, thereby jumping the batch
queue....

So at what point does simply replacing the list_head with a list_lru
become more efficient than this batch processing (i.e.
https://lkml.org/lkml/2015/3/10/660)?  The list_lru isn't a great
fit for the inode list (doesn't need any of the special LRU/memcg
stuff https://lkml.org/lkml/2015/3/16/261) but it will tell us if,
like Ingo suggested, moving more towards a generic per-cpu list
would provide better overall performance...

Cheers,

Dave.
-- 
Dave Chinner
david@...morbit.com