Re: [LSF/MM TOPIC] lru_lock scalability

[Matthew Wilcox <willy@infradead.org>]

On Thu, Feb 01, 2018 at 11:07:56PM -0500, Daniel Jordan wrote:
> On 02/01/2018 04:44 AM, Matthew Wilcox wrote:
> > Something I've been thinking about is changing the LRU from an embedded
> > list_head to an external data structure that I call the XQueue.
> > It's based on the XArray, but is used like a queue; pushing items onto
> > the end of the queue and popping them off the beginning.  You can also
> > remove items from the middle of the queue.
> > 
> > Removing items from the list usually involves dirtying three cachelines.
> > With the XQueue, you'd only dirty one.  That's going to reduce lock
> > hold time.  There may also be opportunities to reduce lock hold time;
> > removal and addition can be done in parallel as long as there's more
> > than 64 entries between head and tail of the list.
> > 
> > The downside is that adding to the queue would require memory allocation.
> > And I don't have time to work on it at the moment.
> 
> I like the idea of touching fewer cachelines.
> 
> I looked through your latest XArray series (v6).  Am I understanding it correctly that a removal (xa_erase) is an exclusive operation within one XArray, i.e. that only one thread can do this at once?  Not sure how XQueue would implement removal though, so the answer might be different for it.

That's currently the case for the XArray, yes.  Peter Zijlstra wrote a
paper over ten years ago for allowing multiple simultaneous page-cache
writers.  https://www.kernel.org/doc/ols/2007/ols2007v2-pages-311-318.pdf

I'm not sure it's applicable to the current XArray which has grown other
features, but it should be implementable for the XQueue.

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