Re: [PATCH v10 11/35] list_lru: per-node list infrastructure

[Dave Chinner <david@fromorbit.com>]

On Wed, Jun 05, 2013 at 04:08:04PM -0700, Andrew Morton wrote:
> On Mon,  3 Jun 2013 23:29:40 +0400 Glauber Costa <glommer@openvz.org> wrote:
> 
> > From: Dave Chinner <dchinner@redhat.com>
> > 
> > Now that we have an LRU list API, we can start to enhance the
> > implementation.  This splits the single LRU list into per-node lists
> > and locks to enhance scalability.
> 
> Do we have any runtime measurements?  They're pretty important for
> justifying inclusion of the code.

Nothing I've officially posted, because I've been busy with other
XFS stuff. But, well, if you look here:

http://oss.sgi.com/pipermail/xfs/2013-June/026888.html

-  12.74%  [kernel]  [k] __ticket_spin_trylock
   - __ticket_spin_trylock
      - 60.49% _raw_spin_lock
         + 91.79% inode_add_lru			>>> inode_lru_lock
         + 2.98% dentry_lru_del			>>> dcache_lru_lock
         + 1.30% shrink_dentry_list
         + 0.71% evict
      - 20.42% do_raw_spin_lock
         - _raw_spin_lock
            + 13.41% inode_add_lru		>>> inode_lru_lock
            + 10.55% evict
            + 8.26% dentry_lru_del		>>> dcache_lru_lock
            + 7.62% __remove_inode_hash
....
      - 10.37% do_raw_spin_trylock
         - _raw_spin_trylock
            + 79.65% prune_icache_sb		>>> inode_lru_lock
            + 11.04% shrink_dentry_list
            + 9.24% prune_dcache_sb		>>> dcache_lru_lock
      - 8.72% _raw_spin_trylock
         + 46.33% prune_icache_sb		>>> inode_lru_lock
         + 46.08% shrink_dentry_list
         + 7.60% prune_dcache_sb		>>> dcache_lru_lock

This is from an 8p system w/ fake-numa=4 running an 8-way find+stat
workload on 50 million files. 12.5% CPU usage means we are burning
an entire CPU of that system just in __ticket_spin_trylock(), and
the numbers above indicate that roughly 60% of that CPU time is from
the inode_lru_lock.

So, more than half a CPU being spent just trying to get the
inode_lru_lock. The generic LRU list code drops
__ticket_spin_trylock() back down to roughly 2% of the total CPU
usage for the same workload - the CPU burn associated with the
contention on the global lock goes away.

It's pretty obvious if a global lock is causing contention issues on
an 8p system, then larger systems are going to be much, much worse.

> Measurememnts for non-NUMA and uniprocessor kernels would be useful in
> making that decision as well.

I get the same spinlock contention problems when I run without the
fake-numa kernel parameter on the VM. The generic LRU lists can't
fix the problem for non-numa systems.

> In fact a lot of the patchset is likely to be injurious to small
> machines.  We should quantify this and then persade ourselves that the
> large-machine gains are worth the small-machine losses.

I haven't been able to measure any CPU usage difference from the
changes for non-numa systems on workloads that stress the LRUs. if
you've got any ideas on how I might demonstrate a regression, then
I'm all ears. But If I can't measure the difference, there is
none...

> 
> > Items are placed on lists
> > according to the node the memory belongs to. To make scanning the
> > lists efficient, also track whether the per-node lists have entries
> > in them in a active nodemask.
> > 
> > Note:
> > We use a fixed-size array for the node LRU, this struct can be very big
> > if MAX_NUMNODES is big. If this becomes a problem this is fixable by
> > turning this into a pointer and dynamically allocating this to
> > nr_node_ids. This quantity is firwmare-provided, and still would provide
> > room for all nodes at the cost of a pointer lookup and an extra
> > allocation. Because that allocation will most likely come from a
> > different slab cache than the main structure holding this structure, we
> > may very well fail.
> 
> Surprised.  How big is MAX_NUMNODES likely to get?

AFAICT, 1024.

> lib/flex_array.c might be of use here.

Never heard of it :/

Perhaps it might, but that woul dbe something to do further down the
track...

> 
> >
> > ...
> >
> > -struct list_lru {
> > +struct list_lru_node {
> >  	spinlock_t		lock;
> >  	struct list_head	list;
> >  	long			nr_items;
> > +} ____cacheline_aligned_in_smp;
> > +
> > +struct list_lru {
> > +	/*
> > +	 * Because we use a fixed-size array, this struct can be very big if
> > +	 * MAX_NUMNODES is big. If this becomes a problem this is fixable by
> > +	 * turning this into a pointer and dynamically allocating this to
> > +	 * nr_node_ids. This quantity is firwmare-provided, and still would
> > +	 * provide room for all nodes at the cost of a pointer lookup and an
> > +	 * extra allocation. Because that allocation will most likely come from
> > +	 * a different slab cache than the main structure holding this
> > +	 * structure, we may very well fail.
> > +	 */
> > +	struct list_lru_node	node[MAX_NUMNODES];
> > +	nodemask_t		active_nodes;
> 
> Some documentation of the data structure would be helpful.  It appears
> that active_nodes tracks (ie: duplicates) node[x].nr_items!=0.
> 
> It's unclear that active_nodes is really needed - we could just iterate
> across all items in list_lru.node[].  Are we sure that the correct
> tradeoff decision was made here?

Yup. Think of all the cache line misses that checking
node[x].nr_items != 0 entails. If MAX_NUMNODES = 1024, there's 1024
cacheline misses right there. The nodemask is a much more cache
friendly method of storing active node state.

not to mention that for small machines with a large MAX_NUMNODES,
we'd be checking nodes that never have items stored on them...

> What's the story on NUMA node hotplug, btw?

Do we care? hotplug doesn't change MAX_NUMNODES, and if you are
removing a node you have to free all the memory on the node,
so that should already be tken care of by external code....

> 
> >  };
> >  
> >
> > ...
> >
> >  unsigned long
> > -list_lru_walk(
> > -	struct list_lru *lru,
> > -	list_lru_walk_cb isolate,
> > -	void		*cb_arg,
> > -	unsigned long	nr_to_walk)
> > +list_lru_count(struct list_lru *lru)
> >  {
> > +	long count = 0;
> > +	int nid;
> > +
> > +	for_each_node_mask(nid, lru->active_nodes) {
> > +		struct list_lru_node *nlru = &lru->node[nid];
> > +
> > +		spin_lock(&nlru->lock);
> > +		BUG_ON(nlru->nr_items < 0);
> 
> This is buggy.

Yup, good catch.

> > +EXPORT_SYMBOL_GPL(list_lru_count);
> 
> list_lru_count()'s return value is of course approximate.  If callers
> require that the returned value be exact, they will need to provide
> their own locking on top of list_lru's internal locking (which would
> then become redundant).
> 
> This is the sort of thing which should be discussed in the interface
> documentation.

Yup.

> list_lru_count() can be very expensive.

Well, yes. But it's far less expensive than a global LRU lock on a
machine of the size that we are concerned about list_lru_count()
being expensive.

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>