• Davidlohr Bueso's avatar
    mm: per-thread vma caching · 615d6e87
    Davidlohr Bueso authored
    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:
    
    1) System bootup: Most programs are single threaded, so the per-thread
       scheme does improve ~50% hit rate by just adding a few more slots to
       the cache.
    
    +----------------+----------+------------------+
    | caching scheme | hit-rate | cycles (billion) |
    +----------------+----------+------------------+
    | baseline       | 50.61%   | 19.90            |
    | patched        | 73.45%   | 13.58            |
    +----------------+----------+------------------+
    
    2) Kernel build: This one is already pretty good with the current
       approach as we're dealing with good locality.
    
    +----------------+----------+------------------+
    | caching scheme | hit-rate | cycles (billion) |
    +----------------+----------+------------------+
    | baseline       | 75.28%   | 11.03            |
    | patched        | 88.09%   | 9.31             |
    +----------------+----------+------------------+
    
    3) Oracle 11g Data Mining (4k pages): Similar to the kernel build workload.
    
    +----------------+----------+------------------+
    | caching scheme | hit-rate | cycles (billion) |
    +----------------+----------+------------------+
    | baseline       | 70.66%   | 17.14            |
    | patched        | 91.15%   | 12.57            |
    +----------------+----------+------------------+
    
    4) Ebizzy: There's a fair amount of variation from run to run, but this
       approach always shows nearly perfect hit rates, while baseline is just
       about non-existent.  The amounts of cycles can fluctuate between
       anywhere from ~60 to ~116 for the baseline scheme, but this approach
       reduces it considerably.  For instance, with 80 threads:
    
    +----------------+----------+------------------+
    | caching scheme | hit-rate | cycles (billion) |
    +----------------+----------+------------------+
    | baseline       | 1.06%    | 91.54            |
    | patched        | 99.97%   | 14.18            |
    +----------------+----------+------------------+
    
    [akpm@linux-foundation.org: fix nommu build, per Davidlohr]
    [akpm@linux-foundation.org: document vmacache_valid() logic]
    [akpm@linux-foundation.org: attempt to untangle header files]
    [akpm@linux-foundation.org: add vmacache_find() BUG_ON]
    [hughd@google.com: add vmacache_valid_mm() (from Oleg)]
    [akpm@linux-foundation.org: coding-style fixes]
    [akpm@linux-foundation.org: adjust and enhance comments]
    Signed-off-by: default avatarDavidlohr Bueso <davidlohr@hp.com>
    Reviewed-by: default avatarRik van Riel <riel@redhat.com>
    Acked-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    Reviewed-by: default avatarMichel Lespinasse <walken@google.com>
    Cc: Oleg Nesterov <oleg@redhat.com>
    Tested-by: default avatarHugh Dickins <hughd@google.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    615d6e87
mmap.c 86.5 KB