On Tue, Feb 25, 2014 at 10:16 AM, Davidlohr Bueso <davidlohr@xxxxxx> wrote: > 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. Actually there is also the cost of keeping the cache up to date. I'm not saying that it's an issue in your proposal - I like the proposal, especially now that you are replacing the per-mm cache rather than adding something on top - but it is a factor to consider. > +static inline void __vmacache_invalidate(struct mm_struct *mm) > +{ > +#ifdef CONFIG_MMU > + vmacache_invalidate(mm); > +#else > + mm->vmacache = NULL; > +#endif > +} Is there any reason why we can't use your proposal for !CONFIG_MMU as well ? (I'm assuming that we could reduce preprocessor checks by doing so) > +void vmacache_invalidate_all(void) > +{ > + struct task_struct *g, *p; > + > + rcu_read_lock(); > + for_each_process_thread(g, p) { > + /* > + * Only flush the vmacache pointers as the > + * mm seqnum is already set and curr's will > + * be set upon invalidation when the next > + * lookup is done. > + */ > + memset(p->vmacache, 0, sizeof(p->vmacache)); > + } > + rcu_read_unlock(); > +} Two things: - I believe we only need to invalidate vma caches for threads that share a given mm ? we should probably pass in that mm in order to avoid over-invalidation - My understanding is that the operation is safe because the caller has the mm's mmap_sem held for write, and other threads accessing the vma cache will have mmap_sem held at least for read, so we don't need extra locking to maintain the vma cache. Please 1- confirm this is the intention, 2- document this, and 3- only invalidate vma caches for threads that match the caller's mm so that mmap_sem locking can actually apply. > +struct vm_area_struct *vmacache_find(struct mm_struct *mm, > + unsigned long addr) > + > +{ > + int i; > + > + if (!vmacache_valid(mm)) > + return NULL; > + > + for (i = 0; i < VMACACHE_SIZE; i++) { > + struct vm_area_struct *vma = current->vmacache[i]; > + > + if (vma && vma->vm_start <= addr && vma->vm_end > addr) > + return vma; > + } > + > + return NULL; > +} > + > +void vmacache_update(struct mm_struct *mm, unsigned long addr, > + struct vm_area_struct *newvma) > +{ > + /* > + * Hash based on the page number. Provides a good > + * hit rate for workloads with good locality and > + * those with random accesses as well. > + */ > + int idx = (addr >> PAGE_SHIFT) & 3; > + current->vmacache[idx] = newvma; > +} I did read the previous discussion about how to compute idx here. I did not at the time realize that you are searching all 4 vmacache entries on lookup - that is, we are only talking about eviction policy here, not a lookup hash policy. My understanding is that the reason both your current and your previous idx computations work, is that a random eviction policy would work too. Basically, what you do is pick some address bits that are 'random enough' to use as an eviction policy. This is more of a question for Linus, but I am very surprised that I can't find an existing LRU eviction policy scheme in Linux. What I have in mind is to keep track of the order the cache entries have last been used. With 4 entries, there are 4! = 24 possible orders, which can be represented with an integer between 0 and 23. When vmacache_find suceeds, that integer is updated using a table lookup (table takes 24*4 = 96 bytes). In vmacache_update, the lru value module 4 indicates which cache way to evict (i.e. it's the one that's been least recently used). I don't think it makes sense to introduce such an LRU facility for this cache only, but it's so generically useful, I'm very surprised that it's not somewhere already and instead we see people inventing new eviction schemes over and over again... -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- 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>