On Thu, 27 Feb 2014 13:48:24 -0800 Davidlohr Bueso <davidlohr@xxxxxx> wrote: > From: Davidlohr Bueso <davidlohr@xxxxxx> > > This patch is a continuation of efforts trying to optimize find_vma(), > avoiding potentially expensive rbtree walks to locate a vma upon faults. > The original approach (https://lkml.org/lkml/2013/11/1/410), where the > largest vma was also cached, ended up being too specific and random, thus > further comparison with other approaches were needed. There are two things > to consider when dealing with this, the cache hit rate and the latency of > find_vma(). Improving the hit-rate does not necessarily translate in finding > the vma any faster, as the overhead of any fancy caching schemes can be too > high to consider. > > We currently cache the last used vma for the whole address space, which > provides a nice optimization, reducing the total cycles in find_vma() by up > to 250%, for workloads with good locality. On the other hand, this simple > scheme is pretty much useless for workloads with poor locality. Analyzing > ebizzy runs shows that, no matter how many threads are running, the > mmap_cache hit rate is less than 2%, and in many situations below 1%. > > The proposed approach is to replace this scheme with a small per-thread cache, > maximizing hit rates at a very low maintenance cost. Invalidations are > performed by simply bumping up a 32-bit sequence number. The only expensive > operation is in the rare case of a seq number overflow, where all caches that > share the same address space are flushed. Upon a miss, the proposed replacement > policy is based on the page number that contains the virtual address in > question. Concretely, the following results are seen on an 80 core, 8 socket > x86-64 box: A second look... > Please note that kgdb, nommu and unicore32 arch are *untested*. Thanks. I build tested nommu, fwiw. > > ... > > --- a/include/linux/mm_types.h > +++ b/include/linux/mm_types.h > @@ -342,9 +342,9 @@ struct mm_rss_stat { > > struct kioctx_table; > struct mm_struct { > - struct vm_area_struct * mmap; /* list of VMAs */ > + struct vm_area_struct *mmap; /* list of VMAs */ > struct rb_root mm_rb; > - struct vm_area_struct * mmap_cache; /* last find_vma result */ > + u32 vmacache_seqnum; /* per-thread vmacache */ nitpick: in kernelese this is typically "per-task". If it was in the mm_struct then it would be "per process". And I guess if it was in the thread_struct it would be "per thread", but that isn't a distinction I've seen made. > --- a/include/linux/sched.h > +++ b/include/linux/sched.h > @@ -23,6 +23,7 @@ struct sched_param { > #include <linux/errno.h> > #include <linux/nodemask.h> > #include <linux/mm_types.h> > +#include <linux/vmacache.h> This might be awkward - vmacache.h drags in mm.h and we have had tangly problems with these major header files in the past. I'd be inclined to remove this inclusion and just forward-declare vm_area_struct, but we still need VMACACHE_SIZE, sigh. Wait and see what happens, I guess. > > ... > > --- /dev/null > +++ b/include/linux/vmacache.h > @@ -0,0 +1,40 @@ > +#ifndef __LINUX_VMACACHE_H > +#define __LINUX_VMACACHE_H > + > +#include <linux/mm.h> > + > +#define VMACACHE_BITS 2 > +#define VMACACHE_SIZE (1U << VMACACHE_BITS) > +#define VMACACHE_MASK (VMACACHE_SIZE - 1) > +/* > + * Hash based on the page number. Provides a good hit rate for > + * workloads with good locality and those with random accesses as well. > + */ > +#define VMACACHE_HASH(addr) ((addr >> PAGE_SHIFT) & VMACACHE_MASK) > + > +#define vmacache_flush(tsk) \ > + do { \ > + memset(tsk->vmacache, 0, sizeof(tsk->vmacache)); \ > + } while (0) There's no particular reason to implement this in cpp. Using C is typesafer and nicer. But then we get into header file issues again. More sigh > +extern void vmacache_flush_all(struct mm_struct *mm); > +extern void vmacache_update(unsigned long addr, struct vm_area_struct *newvma); > +extern struct vm_area_struct *vmacache_find(struct mm_struct *mm, > + unsigned long addr); > + > +#ifndef CONFIG_MMU > +extern struct vm_area_struct *vmacache_find_exact(struct mm_struct *mm, > + unsigned long start, > + unsigned long end); > +#endif We often omit the ifdefs in this case. It means that a compile-time error becomes a link-time error but that's a small cost for unmucking the header files. It doesn't matter much in vmacache.h, but some headers would become a complete maze of ifdefs otherwise. > > ... > > --- /dev/null > +++ b/mm/vmacache.c > @@ -0,0 +1,94 @@ > +/* > + * Copyright (C) 2014 Davidlohr Bueso. > + */ > +#include <linux/sched.h> > +#include <linux/vmacache.h> > + > +/* > + * Flush vma caches for threads that share a given mm. > + * > + * The operation is safe because the caller holds the mmap_sem > + * exclusively and other threads accessing the vma cache will > + * have mmap_sem held at least for read, so no extra locking > + * is required to maintain the vma cache. > + */ Ah, there are our locking rules. > > ... > > +static bool vmacache_valid(struct mm_struct *mm) > +{ > + struct task_struct *curr = current; > + > + if (mm != curr->mm) > + return false; What's going on here? Handling a task poking around in someone else's mm? I'm thinking "__access_remote_vm", but I don't know what you were thinking ;) An explanatory comment would be revealing. > + if (mm->vmacache_seqnum != curr->vmacache_seqnum) { > + /* > + * First attempt will always be invalid, initialize > + * the new cache for this task here. > + */ > + curr->vmacache_seqnum = mm->vmacache_seqnum; > + vmacache_flush(curr); > + return false; > + } > + return true; > +} > + > > ... > -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@xxxxxxxxx. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>