Re: missing madvise functionality

[Nick Piggin <nickpiggin@yahoo.com.au>]

[-- Attachment #1: Type: text/plain, Size: 962 bytes --]

Peter Zijlstra wrote:
> On Wed, 2007-04-04 at 12:22 +1000, Nick Piggin wrote:
> 
>>Eric Dumazet wrote:
> 
> 
>>>I do think such workloads might benefit from a vma_cache not shared by 
>>>all threads but private to each thread. A sequence could invalidate the 
>>>cache(s).
>>>
>>>ie instead of a mm->mmap_cache, having a mm->sequence, and each thread 
>>>having a current->mmap_cache and current->mm_sequence
>>
>>I have a patchset to do exactly this, btw.
> 
> 
> /me too
> 
> However, I decided against pushing it because when it does happen that a
> task is not involved with a vma lookup for longer than it takes the seq
> count to wrap we have a stale pointer...
> 
> We could go and walk the tasks once in a while to reset the pointer, but
> it all got a tad involved.

Well here is my core patch (against I think 2.6.16 + a set of vma cache
cleanups and abstractions). I didn't think the wrapping aspect was
terribly involved.

-- 
SUSE Labs, Novell Inc.

[-- Attachment #2: mm-thread-vma-cache.patch --]
[-- Type: text/plain, Size: 4389 bytes --]

Index: linux-2.6/include/linux/sched.h
===================================================================
--- linux-2.6.orig/include/linux/sched.h
+++ linux-2.6/include/linux/sched.h
@@ -296,6 +296,8 @@ struct mm_struct {
 	struct vm_area_struct *mmap;		/* list of VMAs */
 	struct rb_root mm_rb;
 	struct vm_area_struct *vma_cache;	/* find_vma cache */
+ 	unsigned long vma_sequence;
+
 	unsigned long (*get_unmapped_area) (struct file *filp,
 				unsigned long addr, unsigned long len,
 				unsigned long pgoff, unsigned long flags);
@@ -693,6 +695,8 @@ enum sleep_type {
 	SLEEP_INTERRUPTED,
 };
 
+#define VMA_CACHE_SIZE	4
+
 struct task_struct {
 	volatile long state;	/* -1 unrunnable, 0 runnable, >0 stopped */
 	struct thread_info *thread_info;
@@ -734,6 +738,8 @@ struct task_struct {
 	struct list_head ptrace_list;
 
 	struct mm_struct *mm, *active_mm;
+	struct vm_area_struct *vma_cache[VMA_CACHE_SIZE];
+	unsigned long vma_cache_sequence;
 
 /* task state */
 	struct linux_binfmt *binfmt;
Index: linux-2.6/mm/mmap.c
===================================================================
--- linux-2.6.orig/mm/mmap.c
+++ linux-2.6/mm/mmap.c
@@ -32,6 +32,40 @@
 
 static void vma_cache_touch(struct mm_struct *mm, struct vm_area_struct *vma)
 {
+	struct task_struct *curr = current;
+	if (mm == curr->mm) {
+		int i;
+		if (curr->vma_cache_sequence != mm->vma_sequence) {
+			curr->vma_cache_sequence = mm->vma_sequence;
+			curr->vma_cache[0] = vma;
+			for (i = 1; i < VMA_CACHE_SIZE; i++)
+				curr->vma_cache[i] = NULL;
+		} else {
+			int update_mm;
+
+			if (curr->vma_cache[0] == vma)
+				return;
+
+			for (i = 1; i < VMA_CACHE_SIZE; i++) {
+				if (curr->vma_cache[i] == vma)
+					break;
+			}
+			update_mm = 0;
+			if (i == VMA_CACHE_SIZE) {
+				update_mm = 1;
+				i = VMA_CACHE_SIZE-1;
+			}
+			while (i != 0) {
+				curr->vma_cache[i] = curr->vma_cache[i-1];
+				i--;
+			}
+			curr->vma_cache[0] = vma;
+
+			if (!update_mm)
+				return;
+		}
+	}
+
 	if (mm->vma_cache != vma) /* prevent cacheline bouncing */
 		mm->vma_cache = vma;
 }
@@ -39,27 +73,56 @@ static void vma_cache_touch(struct mm_st
 static void vma_cache_replace(struct mm_struct *mm, struct vm_area_struct *vma,
 						struct vm_area_struct *repl)
 {
+	mm->vma_sequence++;
+	if (unlikely(mm->vma_sequence == 0)) {
+		struct task_struct *curr = current, *t;
+		t = curr;
+		rcu_read_lock();
+		do {
+			t->vma_cache_sequence = -1;
+			t = next_thread(t);
+		} while (t != curr);
+		rcu_read_unlock();
+	}
+
 	if (mm->vma_cache == vma)
 		mm->vma_cache = repl;
 }
 
 static void vma_cache_invalidate(struct mm_struct *mm, struct vm_area_struct *vma)
 {
- 	if (mm->vma_cache == vma)
-		mm->vma_cache = NULL;
+	vma_cache_replace(mm, vma, NULL);
 }
 
 static struct vm_area_struct *vma_cache_find(struct mm_struct *mm,
 						unsigned long addr)
 {
-	struct vm_area_struct *vma = mm->vma_cache;
+	struct task_struct *curr;
+	struct vm_area_struct *vma;
 
 	preempt_disable();
 	__inc_page_state(vma_cache_query);
-	if (vma && vma->vm_end > addr && vma->vm_start <= addr)
+
+	curr = current;
+	if (mm == curr->mm && mm->vma_sequence == curr->vma_cache_sequence) {
+		int i;
+		for (i = 0; i < VMA_CACHE_SIZE; i++) {
+			vma = curr->vma_cache[i];
+			if (vma && vma->vm_end > addr && vma->vm_start <= addr){
+				__inc_page_state(vma_cache_hit);
+				goto out;
+			}
+		}
+	}
+
+	vma = mm->vma_cache;
+	if (vma && vma->vm_end > addr && vma->vm_start <= addr) {
 		__inc_page_state(vma_cache_hit);
-	else
-		vma = NULL;
+		goto out;
+	}
+
+	vma = NULL;
+out:
 	preempt_enable();
 
 	return vma;
@@ -1439,9 +1502,9 @@ struct vm_area_struct * find_vma(struct 
 				} else
 					rb_node = rb_node->rb_right;
 			}
-			if (vma)
-				vma_cache_touch(mm, vma);
 		}
+		if (vma)
+			vma_cache_touch(mm, vma);
 	}
 	return vma;
 }
@@ -1487,6 +1550,9 @@ find_vma_prev(struct mm_struct *mm, unsi
 	}
 
 out:
+	if (vma)
+		vma_cache_touch(mm, vma);
+
 	*pprev = prev;
 	return prev ? prev->vm_next : vma;
 }
Index: linux-2.6/kernel/fork.c
===================================================================
--- linux-2.6.orig/kernel/fork.c
+++ linux-2.6/kernel/fork.c
@@ -198,6 +198,7 @@ static inline int dup_mmap(struct mm_str
 	mm->locked_vm = 0;
 	mm->mmap = NULL;
 	mm->vma_cache = NULL;
+	mm->vma_sequence = 0;
 	mm->free_area_cache = oldmm->mmap_base;
 	mm->cached_hole_size = ~0UL;
 	mm->map_count = 0;