From be8524d522a1efc6fd3d5d76c797e3e76f40354a Mon Sep 17 00:00:00 2001 From: Luiz Capitulino Date: Wed, 8 Jul 2009 10:15:19 -0300 Subject: [PATCH] Introduce uni-final-project patches Signed-off-by: Luiz Capitulino --- .../bstree/introduce-binary-search-tree.patch | 120 ++++ uni-final-project/bstree/makefile-version.patch | 17 + .../bstree/port-vma-code-to-bstree.patch | 455 +++++++++++++++ uni-final-project/bstree/report-struct-sizes.patch | 33 ++ uni-final-project/bstree/series | 4 + uni-final-project/rbtree/makefile-version.patch | 17 + uni-final-project/rbtree/report-struct-sizes.patch | 33 ++ uni-final-project/rbtree/series | 2 + .../sptree/change-find-vma-locks.patch | 627 +++++++++++++++++++++ .../sptree/check-vma-splay-tree.patch | 133 +++++ .../sptree/introduce-vma-splay-tree.patch | 481 ++++++++++++++++ uni-final-project/sptree/makefile-version.patch | 17 + uni-final-project/sptree/report-struct-sizes.patch | 33 ++ uni-final-project/sptree/series | 8 + uni-final-project/sptree/use-vma-splay-tree.patch | 444 +++++++++++++++ 15 files changed, 2424 insertions(+) create mode 100644 uni-final-project/bstree/introduce-binary-search-tree.patch create mode 100644 uni-final-project/bstree/makefile-version.patch create mode 100644 uni-final-project/bstree/port-vma-code-to-bstree.patch create mode 100644 uni-final-project/bstree/report-struct-sizes.patch create mode 100644 uni-final-project/bstree/series create mode 100644 uni-final-project/rbtree/makefile-version.patch create mode 100644 uni-final-project/rbtree/report-struct-sizes.patch create mode 100644 uni-final-project/rbtree/series create mode 100644 uni-final-project/sptree/change-find-vma-locks.patch create mode 100644 uni-final-project/sptree/check-vma-splay-tree.patch create mode 100644 uni-final-project/sptree/introduce-vma-splay-tree.patch create mode 100644 uni-final-project/sptree/makefile-version.patch create mode 100644 uni-final-project/sptree/report-struct-sizes.patch create mode 100644 uni-final-project/sptree/series create mode 100644 uni-final-project/sptree/use-vma-splay-tree.patch diff --git a/uni-final-project/bstree/introduce-binary-search-tree.patch b/uni-final-project/bstree/introduce-binary-search-tree.patch new file mode 100644 index 0000000..db8c912 --- /dev/null +++ b/uni-final-project/bstree/introduce-binary-search-tree.patch @@ -0,0 +1,120 @@ +Introduce Binary Search tree API (V1) + +Signed-off-by: Luiz Fernando N. Capitulino + +--- + include/linux/bstree.h | 33 ++++++++++++++++++++++++++++++ + lib/Makefile | 3 +- + lib/bstree.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++++ + 3 files changed, 88 insertions(+), 1 deletion(-) + +Index: linux-2.6.29.y/include/linux/bstree.h +=================================================================== +--- /dev/null ++++ linux-2.6.29.y/include/linux/bstree.h +@@ -0,0 +1,33 @@ ++#ifndef _LINUX_BSTREE_H ++#define _LINUX_BSTREE_H ++ ++#include ++#include ++ ++struct bs_node ++{ ++ struct bs_node *bs_parent; ++ struct bs_node *bs_right; ++ struct bs_node *bs_left; ++}; ++ ++struct bs_root ++{ ++ struct bs_node *bs_node; ++}; ++ ++#define BS_ROOT (struct bs_root) { NULL, } ++#define bs_entry(ptr, type, member) container_of(ptr, type, member) ++ ++extern void bs_delete(struct bs_root *root, struct bs_node *node); ++ ++static inline void bs_link_node(struct bs_node *node, struct bs_node *parent, ++ struct bs_node **bs_link) ++{ ++ node->bs_parent = parent; ++ node->bs_left = node->bs_right = NULL; ++ ++ *bs_link = node; ++} ++ ++#endif /* _LINUX_BSTREE_H */ +Index: linux-2.6.29.y/lib/Makefile +=================================================================== +--- linux-2.6.29.y.orig/lib/Makefile ++++ linux-2.6.29.y/lib/Makefile +@@ -11,7 +11,8 @@ lib-y := ctype.o string.o vsprintf.o cmd + rbtree.o radix-tree.o dump_stack.o \ + idr.o int_sqrt.o extable.o prio_tree.o \ + sha1.o irq_regs.o reciprocal_div.o argv_split.o \ +- proportions.o prio_heap.o ratelimit.o show_mem.o is_single_threaded.o ++ proportions.o prio_heap.o ratelimit.o show_mem.o \ ++ is_single_threaded.o bstree.o + + lib-$(CONFIG_MMU) += ioremap.o + lib-$(CONFIG_SMP) += cpumask.o +Index: linux-2.6.29.y/lib/bstree.c +=================================================================== +--- /dev/null ++++ linux-2.6.29.y/lib/bstree.c +@@ -0,0 +1,53 @@ ++#include ++#include ++ ++static inline struct bs_node *bs_find_sucessor(struct bs_node *node) ++{ ++ while (node->bs_left != NULL) ++ node = node->bs_left; ++ return node; ++} ++ ++static void bs_update_parent(struct bs_root *root, ++ struct bs_node *node, struct bs_node *new_child) ++{ ++ struct bs_node *parent = node->bs_parent; ++ ++ if (parent) { ++ if (parent->bs_left == node) ++ parent->bs_left = new_child; ++ else ++ parent->bs_right = new_child; ++ } else { ++ root->bs_node = new_child; ++ } ++ ++ if (new_child) ++ new_child->bs_parent = parent; ++} ++ ++void bs_delete(struct bs_root *root, struct bs_node *node) ++{ ++ if (!node->bs_right) { ++ bs_update_parent(root, node, node->bs_left); ++ } else { ++ struct bs_node *r = node->bs_right; ++ if (!r->bs_left) { ++ r->bs_left = node->bs_left; ++ if (node->bs_left) ++ node->bs_left->bs_parent = r; ++ bs_update_parent(root, node, r); ++ } else { ++ struct bs_node *s = bs_find_sucessor(r); ++ bs_delete(root, s); ++ s->bs_left = node->bs_left; ++ if (s->bs_left) ++ s->bs_left->bs_parent = s; ++ s->bs_right = node->bs_right; ++ if (s->bs_right) ++ s->bs_right->bs_parent = s; ++ bs_update_parent(root, node, s); ++ } ++ } ++} ++EXPORT_SYMBOL(bs_delete); diff --git a/uni-final-project/bstree/makefile-version.patch b/uni-final-project/bstree/makefile-version.patch new file mode 100644 index 0000000..158b2e7 --- /dev/null +++ b/uni-final-project/bstree/makefile-version.patch @@ -0,0 +1,17 @@ +--- + Makefile | 2 +- + 1 file changed, 1 insertion(+), 1 deletion(-) + +Index: linux-2.6.29.y/Makefile +=================================================================== +--- linux-2.6.29.y.orig/Makefile ++++ linux-2.6.29.y/Makefile +@@ -1,7 +1,7 @@ + VERSION = 2 + PATCHLEVEL = 6 + SUBLEVEL = 29 +-EXTRAVERSION = .2 ++EXTRAVERSION = .2-bstree1 + NAME = Temporary Tasmanian Devil + + # *DOCUMENTATION* diff --git a/uni-final-project/bstree/port-vma-code-to-bstree.patch b/uni-final-project/bstree/port-vma-code-to-bstree.patch new file mode 100644 index 0000000..86d03c4 --- /dev/null +++ b/uni-final-project/bstree/port-vma-code-to-bstree.patch @@ -0,0 +1,455 @@ +Port VMA functions to use bstree (V1) + +Signed-off-by: Luiz Fernando N. Capitulino + +--- + include/linux/init_task.h | 3 - + include/linux/mm.h | 5 + + include/linux/mm_types.h | 6 +- + kernel/fork.c | 14 ++--- + mm/mmap.c | 123 ++++++++++++++++++++++------------------------ + 5 files changed, 76 insertions(+), 75 deletions(-) + +Index: linux-2.6.29.y/include/linux/init_task.h +=================================================================== +--- linux-2.6.29.y.orig/include/linux/init_task.h ++++ linux-2.6.29.y/include/linux/init_task.h +@@ -9,6 +9,7 @@ + #include + #include + #include ++#include + #include + + extern struct files_struct init_files; +@@ -29,7 +30,7 @@ extern struct fs_struct init_fs; + + #define INIT_MM(name) \ + { \ +- .mm_rb = RB_ROOT, \ ++ .mm_bs = BS_ROOT, \ + .pgd = swapper_pg_dir, \ + .mm_users = ATOMIC_INIT(2), \ + .mm_count = ATOMIC_INIT(1), \ +Index: linux-2.6.29.y/include/linux/mm.h +=================================================================== +--- linux-2.6.29.y.orig/include/linux/mm.h ++++ linux-2.6.29.y/include/linux/mm.h +@@ -10,6 +10,7 @@ + #include + #include + #include ++#include + #include + #include + #include +@@ -1119,8 +1120,8 @@ extern struct anon_vma *find_mergeable_a + extern int split_vma(struct mm_struct *, + struct vm_area_struct *, unsigned long addr, int new_below); + extern int insert_vm_struct(struct mm_struct *, struct vm_area_struct *); +-extern void __vma_link_rb(struct mm_struct *, struct vm_area_struct *, +- struct rb_node **, struct rb_node *); ++extern void __vma_link_bs(struct mm_struct *, struct vm_area_struct *, ++ struct bs_node **, struct bs_node *); + extern void unlink_file_vma(struct vm_area_struct *); + extern struct vm_area_struct *copy_vma(struct vm_area_struct **, + unsigned long addr, unsigned long len, pgoff_t pgoff); +Index: linux-2.6.29.y/include/linux/mm_types.h +=================================================================== +--- linux-2.6.29.y.orig/include/linux/mm_types.h ++++ linux-2.6.29.y/include/linux/mm_types.h +@@ -7,7 +7,7 @@ + #include + #include + #include +-#include ++#include + #include + #include + #include +@@ -131,7 +131,7 @@ struct vm_area_struct { + pgprot_t vm_page_prot; /* Access permissions of this VMA. */ + unsigned long vm_flags; /* Flags, see mm.h. */ + +- struct rb_node vm_rb; ++ struct bs_node vm_bs; + + /* + * For areas with an address space and backing store, +@@ -189,7 +189,7 @@ struct core_state { + + struct mm_struct { + struct vm_area_struct * mmap; /* list of VMAs */ +- struct rb_root mm_rb; ++ struct bs_root mm_bs; + struct vm_area_struct * mmap_cache; /* last find_vma result */ + unsigned long (*get_unmapped_area) (struct file *filp, + unsigned long addr, unsigned long len, +Index: linux-2.6.29.y/kernel/fork.c +=================================================================== +--- linux-2.6.29.y.orig/kernel/fork.c ++++ linux-2.6.29.y/kernel/fork.c +@@ -261,7 +261,7 @@ out: + static int dup_mmap(struct mm_struct *mm, struct mm_struct *oldmm) + { + struct vm_area_struct *mpnt, *tmp, **pprev; +- struct rb_node **rb_link, *rb_parent; ++ struct bs_node **bs_link, *bs_parent; + int retval; + unsigned long charge; + struct mempolicy *pol; +@@ -280,9 +280,9 @@ static int dup_mmap(struct mm_struct *mm + mm->cached_hole_size = ~0UL; + mm->map_count = 0; + cpus_clear(mm->cpu_vm_mask); +- mm->mm_rb = RB_ROOT; +- rb_link = &mm->mm_rb.rb_node; +- rb_parent = NULL; ++ mm->mm_bs = BS_ROOT; ++ bs_link = &mm->mm_bs.bs_node; ++ bs_parent = NULL; + pprev = &mm->mmap; + + for (mpnt = oldmm->mmap; mpnt; mpnt = mpnt->vm_next) { +@@ -348,9 +348,9 @@ static int dup_mmap(struct mm_struct *mm + *pprev = tmp; + pprev = &tmp->vm_next; + +- __vma_link_rb(mm, tmp, rb_link, rb_parent); +- rb_link = &tmp->vm_rb.rb_right; +- rb_parent = &tmp->vm_rb; ++ __vma_link_bs(mm, tmp, bs_link, bs_parent); ++ bs_link = &tmp->vm_bs.bs_right; ++ bs_parent = &tmp->vm_bs; + + mm->map_count++; + retval = copy_page_range(mm, oldmm, mpnt); +Index: linux-2.6.29.y/mm/mmap.c +=================================================================== +--- linux-2.6.29.y.orig/mm/mmap.c ++++ linux-2.6.29.y/mm/mmap.c +@@ -352,63 +352,62 @@ void validate_mm(struct mm_struct *mm) + + static struct vm_area_struct * + find_vma_prepare(struct mm_struct *mm, unsigned long addr, +- struct vm_area_struct **pprev, struct rb_node ***rb_link, +- struct rb_node ** rb_parent) ++ struct vm_area_struct **pprev, struct bs_node ***bs_link, ++ struct bs_node ** bs_parent) + { +- struct vm_area_struct * vma; +- struct rb_node ** __rb_link, * __rb_parent, * rb_prev; ++ struct vm_area_struct *vma; ++ struct bs_node ** __bs_link, * __bs_parent, * bs_prev; + +- __rb_link = &mm->mm_rb.rb_node; +- rb_prev = __rb_parent = NULL; ++ __bs_link = &mm->mm_bs.bs_node; ++ bs_prev = __bs_parent = NULL; + vma = NULL; + +- while (*__rb_link) { ++ while (*__bs_link) { + struct vm_area_struct *vma_tmp; + +- __rb_parent = *__rb_link; +- vma_tmp = rb_entry(__rb_parent, struct vm_area_struct, vm_rb); ++ __bs_parent = *__bs_link; ++ vma_tmp = bs_entry(__bs_parent, struct vm_area_struct, vm_bs); + + if (vma_tmp->vm_end > addr) { + vma = vma_tmp; + if (vma_tmp->vm_start <= addr) + break; +- __rb_link = &__rb_parent->rb_left; ++ __bs_link = &__bs_parent->bs_left; + } else { +- rb_prev = __rb_parent; +- __rb_link = &__rb_parent->rb_right; ++ bs_prev = __bs_parent; ++ __bs_link = &__bs_parent->bs_right; + } + } + + *pprev = NULL; +- if (rb_prev) +- *pprev = rb_entry(rb_prev, struct vm_area_struct, vm_rb); +- *rb_link = __rb_link; +- *rb_parent = __rb_parent; ++ if (bs_prev) ++ *pprev = bs_entry(bs_prev, struct vm_area_struct, vm_bs); ++ *bs_link = __bs_link; ++ *bs_parent = __bs_parent; + return vma; + } + + static inline void + __vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma, +- struct vm_area_struct *prev, struct rb_node *rb_parent) ++ struct vm_area_struct *prev, struct bs_node *bs_parent) + { + if (prev) { + vma->vm_next = prev->vm_next; + prev->vm_next = vma; + } else { + mm->mmap = vma; +- if (rb_parent) +- vma->vm_next = rb_entry(rb_parent, +- struct vm_area_struct, vm_rb); ++ if (bs_parent) ++ vma->vm_next = bs_entry(bs_parent, ++ struct vm_area_struct, vm_bs); + else + vma->vm_next = NULL; + } + } + +-void __vma_link_rb(struct mm_struct *mm, struct vm_area_struct *vma, +- struct rb_node **rb_link, struct rb_node *rb_parent) ++void __vma_link_bs(struct mm_struct *mm, struct vm_area_struct *vma, ++ struct bs_node **bs_link, struct bs_node *bs_parent) + { +- rb_link_node(&vma->vm_rb, rb_parent, rb_link); +- rb_insert_color(&vma->vm_rb, &mm->mm_rb); ++ bs_link_node(&vma->vm_bs, bs_parent, bs_link); + } + + static void __vma_link_file(struct vm_area_struct *vma) +@@ -435,17 +434,17 @@ static void __vma_link_file(struct vm_ar + + static void + __vma_link(struct mm_struct *mm, struct vm_area_struct *vma, +- struct vm_area_struct *prev, struct rb_node **rb_link, +- struct rb_node *rb_parent) ++ struct vm_area_struct *prev, struct bs_node **bs_link, ++ struct bs_node *bs_parent) + { +- __vma_link_list(mm, vma, prev, rb_parent); +- __vma_link_rb(mm, vma, rb_link, rb_parent); ++ __vma_link_list(mm, vma, prev, bs_parent); ++ __vma_link_bs(mm, vma, bs_link, bs_parent); + __anon_vma_link(vma); + } + + static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma, +- struct vm_area_struct *prev, struct rb_node **rb_link, +- struct rb_node *rb_parent) ++ struct vm_area_struct *prev, struct bs_node **bs_link, ++ struct bs_node *bs_parent) + { + struct address_space *mapping = NULL; + +@@ -458,7 +457,7 @@ static void vma_link(struct mm_struct *m + } + anon_vma_lock(vma); + +- __vma_link(mm, vma, prev, rb_link, rb_parent); ++ __vma_link(mm, vma, prev, bs_link, bs_parent); + __vma_link_file(vma); + + anon_vma_unlock(vma); +@@ -477,11 +476,11 @@ static void vma_link(struct mm_struct *m + static void __insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vma) + { + struct vm_area_struct *__vma, *prev; +- struct rb_node **rb_link, *rb_parent; ++ struct bs_node **bs_link, *bs_parent; + +- __vma = find_vma_prepare(mm, vma->vm_start,&prev, &rb_link, &rb_parent); ++ __vma = find_vma_prepare(mm, vma->vm_start,&prev, &bs_link, &bs_parent); + BUG_ON(__vma && __vma->vm_start < vma->vm_end); +- __vma_link(mm, vma, prev, rb_link, rb_parent); ++ __vma_link(mm, vma, prev, bs_link, bs_parent); + mm->map_count++; + } + +@@ -490,7 +489,7 @@ __vma_unlink(struct mm_struct *mm, struc + struct vm_area_struct *prev) + { + prev->vm_next = vma->vm_next; +- rb_erase(&vma->vm_rb, &mm->mm_rb); ++ bs_delete(&mm->mm_bs, &vma->vm_bs); + if (mm->mmap_cache == vma) + mm->mmap_cache = prev; + } +@@ -1110,14 +1109,14 @@ unsigned long mmap_region(struct file *f + struct vm_area_struct *vma, *prev; + int correct_wcount = 0; + int error; +- struct rb_node **rb_link, *rb_parent; ++ struct bs_node **bs_link, *bs_parent; + unsigned long charged = 0; + struct inode *inode = file ? file->f_path.dentry->d_inode : NULL; + + /* Clear old maps */ + error = -ENOMEM; + munmap_back: +- vma = find_vma_prepare(mm, addr, &prev, &rb_link, &rb_parent); ++ vma = find_vma_prepare(mm, addr, &prev, &bs_link, &bs_parent); + if (vma && vma->vm_start < addr + len) { + if (do_munmap(mm, addr, len)) + return -ENOMEM; +@@ -1212,7 +1211,7 @@ munmap_back: + if (vma_wants_writenotify(vma)) + vma->vm_page_prot = vm_get_page_prot(vm_flags & ~VM_SHARED); + +- vma_link(mm, vma, prev, rb_link, rb_parent); ++ vma_link(mm, vma, prev, bs_link, bs_parent); + file = vma->vm_file; + + /* Once vma denies write, undo our temporary denial count */ +@@ -1469,24 +1468,24 @@ struct vm_area_struct *find_vma(struct m + /* (Cache hit rate is typically around 35%.) */ + vma = mm->mmap_cache; + if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) { +- struct rb_node * rb_node; ++ struct bs_node *bs_node; + +- rb_node = mm->mm_rb.rb_node; ++ bs_node = mm->mm_bs.bs_node; + vma = NULL; + +- while (rb_node) { +- struct vm_area_struct * vma_tmp; ++ while (bs_node) { ++ struct vm_area_struct *vma_tmp; + +- vma_tmp = rb_entry(rb_node, +- struct vm_area_struct, vm_rb); ++ vma_tmp = bs_entry(bs_node, ++ struct vm_area_struct, vm_bs); + + if (vma_tmp->vm_end > addr) { + vma = vma_tmp; + if (vma_tmp->vm_start <= addr) + break; +- rb_node = rb_node->rb_left; ++ bs_node = bs_node->bs_left; + } else +- rb_node = rb_node->rb_right; ++ bs_node = bs_node->bs_right; + } + if (vma) + mm->mmap_cache = vma; +@@ -1503,7 +1502,7 @@ find_vma_prev(struct mm_struct *mm, unsi + struct vm_area_struct **pprev) + { + struct vm_area_struct *vma = NULL, *prev = NULL; +- struct rb_node *rb_node; ++ struct bs_node *bs_node; + if (!mm) + goto out; + +@@ -1511,19 +1510,19 @@ find_vma_prev(struct mm_struct *mm, unsi + vma = mm->mmap; + + /* Go through the RB tree quickly. */ +- rb_node = mm->mm_rb.rb_node; ++ bs_node = mm->mm_bs.bs_node; + +- while (rb_node) { ++ while (bs_node) { + struct vm_area_struct *vma_tmp; +- vma_tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb); ++ vma_tmp = bs_entry(bs_node, struct vm_area_struct, vm_bs); + + if (addr < vma_tmp->vm_end) { +- rb_node = rb_node->rb_left; ++ bs_node = bs_node->bs_left; + } else { + prev = vma_tmp; + if (!prev->vm_next || (addr < prev->vm_next->vm_end)) + break; +- rb_node = rb_node->rb_right; ++ bs_node = bs_node->bs_right; + } + } + +@@ -1796,7 +1795,7 @@ detach_vmas_to_be_unmapped(struct mm_str + + insertion_point = (prev ? &prev->vm_next : &mm->mmap); + do { +- rb_erase(&vma->vm_rb, &mm->mm_rb); ++ bs_delete(&mm->mm_bs, &vma->vm_bs); + mm->map_count--; + tail_vma = vma; + vma = vma->vm_next; +@@ -1978,7 +1977,7 @@ unsigned long do_brk(unsigned long addr, + struct mm_struct * mm = current->mm; + struct vm_area_struct * vma, * prev; + unsigned long flags; +- struct rb_node ** rb_link, * rb_parent; ++ struct bs_node ** bs_link, * bs_parent; + pgoff_t pgoff = addr >> PAGE_SHIFT; + int error; + +@@ -2025,7 +2024,7 @@ unsigned long do_brk(unsigned long addr, + * Clear old maps. this also does some error checking for us + */ + munmap_back: +- vma = find_vma_prepare(mm, addr, &prev, &rb_link, &rb_parent); ++ vma = find_vma_prepare(mm, addr, &prev, &bs_link, &bs_parent); + if (vma && vma->vm_start < addr + len) { + if (do_munmap(mm, addr, len)) + return -ENOMEM; +@@ -2063,7 +2062,7 @@ unsigned long do_brk(unsigned long addr, + vma->vm_pgoff = pgoff; + vma->vm_flags = flags; + vma->vm_page_prot = vm_get_page_prot(flags); +- vma_link(mm, vma, prev, rb_link, rb_parent); ++ vma_link(mm, vma, prev, bs_link, bs_parent); + out: + mm->total_vm += len >> PAGE_SHIFT; + if (flags & VM_LOCKED) { +@@ -2128,7 +2127,7 @@ void exit_mmap(struct mm_struct *mm) + int insert_vm_struct(struct mm_struct * mm, struct vm_area_struct * vma) + { + struct vm_area_struct * __vma, * prev; +- struct rb_node ** rb_link, * rb_parent; ++ struct bs_node ** bs_link, * bs_parent; + + /* + * The vm_pgoff of a purely anonymous vma should be irrelevant +@@ -2146,13 +2145,13 @@ int insert_vm_struct(struct mm_struct * + BUG_ON(vma->anon_vma); + vma->vm_pgoff = vma->vm_start >> PAGE_SHIFT; + } +- __vma = find_vma_prepare(mm,vma->vm_start,&prev,&rb_link,&rb_parent); ++ __vma = find_vma_prepare(mm,vma->vm_start,&prev,&bs_link,&bs_parent); + if (__vma && __vma->vm_start < vma->vm_end) + return -ENOMEM; + if ((vma->vm_flags & VM_ACCOUNT) && + security_vm_enough_memory_mm(mm, vma_pages(vma))) + return -ENOMEM; +- vma_link(mm, vma, prev, rb_link, rb_parent); ++ vma_link(mm, vma, prev, bs_link, bs_parent); + return 0; + } + +@@ -2167,7 +2166,7 @@ struct vm_area_struct *copy_vma(struct v + unsigned long vma_start = vma->vm_start; + struct mm_struct *mm = vma->vm_mm; + struct vm_area_struct *new_vma, *prev; +- struct rb_node **rb_link, *rb_parent; ++ struct bs_node **bs_link, *bs_parent; + struct mempolicy *pol; + + /* +@@ -2177,7 +2176,7 @@ struct vm_area_struct *copy_vma(struct v + if (!vma->vm_file && !vma->anon_vma) + pgoff = addr >> PAGE_SHIFT; + +- find_vma_prepare(mm, addr, &prev, &rb_link, &rb_parent); ++ find_vma_prepare(mm, addr, &prev, &bs_link, &bs_parent); + new_vma = vma_merge(mm, prev, addr, addr + len, vma->vm_flags, + vma->anon_vma, vma->vm_file, pgoff, vma_policy(vma)); + if (new_vma) { +@@ -2207,7 +2206,7 @@ struct vm_area_struct *copy_vma(struct v + } + if (new_vma->vm_ops && new_vma->vm_ops->open) + new_vma->vm_ops->open(new_vma); +- vma_link(mm, new_vma, prev, rb_link, rb_parent); ++ vma_link(mm, new_vma, prev, bs_link, bs_parent); + } + } + return new_vma; diff --git a/uni-final-project/bstree/report-struct-sizes.patch b/uni-final-project/bstree/report-struct-sizes.patch new file mode 100644 index 0000000..bf2690e --- /dev/null +++ b/uni-final-project/bstree/report-struct-sizes.patch @@ -0,0 +1,33 @@ +--- + init/main.c | 11 +++++++++++ + 1 file changed, 11 insertions(+) + +Index: linux-2.6.29.y/init/main.c +=================================================================== +--- linux-2.6.29.y.orig/init/main.c ++++ linux-2.6.29.y/init/main.c +@@ -527,6 +527,15 @@ void __init __weak thread_info_cache_ini + { + } + ++static void __init report_struct_sizes(void) ++{ ++ printk("-> Binary Search Tree sizes:\n"); ++ printk("\tmm_struct: %d\n", sizeof(struct mm_struct)); ++ printk("\tvm_area_struct: %d\n", sizeof(struct vm_area_struct)); ++ printk("\tbs_node: %d\n", sizeof(struct bs_node)); ++ printk("\tbs_root: %d\n", sizeof(struct bs_root)); ++} ++ + asmlinkage void __init start_kernel(void) + { + char * command_line; +@@ -683,6 +692,8 @@ asmlinkage void __init start_kernel(void + + ftrace_init(); + ++ report_struct_sizes(); ++ + /* Do the rest non-__init'ed, we're now alive */ + rest_init(); + } diff --git a/uni-final-project/bstree/series b/uni-final-project/bstree/series new file mode 100644 index 0000000..b7f795d --- /dev/null +++ b/uni-final-project/bstree/series @@ -0,0 +1,4 @@ +makefile-version.patch +introduce-binary-search-tree.patch +report-struct-sizes.patch +port-vma-code-to-bstree.patch diff --git a/uni-final-project/rbtree/makefile-version.patch b/uni-final-project/rbtree/makefile-version.patch new file mode 100644 index 0000000..1a1c9e9 --- /dev/null +++ b/uni-final-project/rbtree/makefile-version.patch @@ -0,0 +1,17 @@ +--- + Makefile | 2 +- + 1 file changed, 1 insertion(+), 1 deletion(-) + +Index: linux-2.6.29.y/Makefile +=================================================================== +--- linux-2.6.29.y.orig/Makefile ++++ linux-2.6.29.y/Makefile +@@ -1,7 +1,7 @@ + VERSION = 2 + PATCHLEVEL = 6 + SUBLEVEL = 29 +-EXTRAVERSION = .2 ++EXTRAVERSION = .2-rbtree1 + NAME = Temporary Tasmanian Devil + + # *DOCUMENTATION* diff --git a/uni-final-project/rbtree/report-struct-sizes.patch b/uni-final-project/rbtree/report-struct-sizes.patch new file mode 100644 index 0000000..cf0209b --- /dev/null +++ b/uni-final-project/rbtree/report-struct-sizes.patch @@ -0,0 +1,33 @@ +--- + init/main.c | 11 +++++++++++ + 1 file changed, 11 insertions(+) + +Index: linux-2.6.29.y/init/main.c +=================================================================== +--- linux-2.6.29.y.orig/init/main.c ++++ linux-2.6.29.y/init/main.c +@@ -527,6 +527,15 @@ void __init __weak thread_info_cache_ini + { + } + ++static void __init report_struct_sizes(void) ++{ ++ printk("-> Red-Black Tree sizes:\n"); ++ printk("\tmm_struct: %d\n", sizeof(struct mm_struct)); ++ printk("\tvm_area_struct: %d\n", sizeof(struct vm_area_struct)); ++ printk("\trb_node: %d\n", sizeof(struct rb_node)); ++ printk("\trb_root: %d\n", sizeof(struct rb_root)); ++} ++ + asmlinkage void __init start_kernel(void) + { + char * command_line; +@@ -683,6 +692,8 @@ asmlinkage void __init start_kernel(void + + ftrace_init(); + ++ report_struct_sizes(); ++ + /* Do the rest non-__init'ed, we're now alive */ + rest_init(); + } diff --git a/uni-final-project/rbtree/series b/uni-final-project/rbtree/series new file mode 100644 index 0000000..9a8a235 --- /dev/null +++ b/uni-final-project/rbtree/series @@ -0,0 +1,2 @@ +makefile-version.patch +report-struct-sizes.patch diff --git a/uni-final-project/sptree/change-find-vma-locks.patch b/uni-final-project/sptree/change-find-vma-locks.patch new file mode 100644 index 0000000..94bd0aa --- /dev/null +++ b/uni-final-project/sptree/change-find-vma-locks.patch @@ -0,0 +1,627 @@ +--- + arch/x86/lib/usercopy_32.c | 8 ++++---- + arch/x86/mm/fault.c | 12 ++++++------ + arch/x86/mm/gup.c | 4 ++-- + drivers/dma/iovlock.c | 4 ++-- + drivers/gpu/drm/via/via_dmablit.c | 4 ++-- + drivers/media/video/videobuf-dma-sg.c | 4 ++-- + drivers/scsi/st.c | 4 ++-- + fs/fuse/dev.c | 4 ++-- + fs/fuse/file.c | 4 ++-- + fs/nfs/direct.c | 8 ++++---- + fs/proc/base.c | 4 ++-- + fs/proc/task_mmu.c | 8 ++++---- + kernel/futex.c | 4 ++-- + kernel/trace/trace.c | 4 ++-- + mm/fremap.c | 3 ++- + mm/madvise.c | 2 ++ + mm/memory.c | 8 ++++---- + mm/mempolicy.c | 12 ++++++------ + mm/migrate.c | 8 ++++---- + mm/mincore.c | 4 ++-- + mm/msync.c | 8 ++++---- + mm/nommu.c | 4 ++-- + mm/util.c | 4 ++-- + 23 files changed, 66 insertions(+), 63 deletions(-) + +Index: linux-2.6.29.y/kernel/futex.c +=================================================================== +--- linux-2.6.29.y.orig/kernel/futex.c ++++ linux-2.6.29.y/kernel/futex.c +@@ -311,7 +311,7 @@ static int futex_handle_fault(unsigned l + if (attempt > 2) + return ret; + +- down_read(&mm->mmap_sem); ++ down_write(&mm->mmap_sem); + vma = find_vma(mm, address); + if (vma && address >= vma->vm_start && + (vma->vm_flags & VM_WRITE)) { +@@ -331,7 +331,7 @@ static int futex_handle_fault(unsigned l + current->min_flt++; + } + } +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + return ret; + } + +Index: linux-2.6.29.y/kernel/trace/trace.c +=================================================================== +--- linux-2.6.29.y.orig/kernel/trace/trace.c ++++ linux-2.6.29.y/kernel/trace/trace.c +@@ -1558,7 +1558,7 @@ static inline int seq_print_user_ip(stru + if (mm) { + const struct vm_area_struct *vma; + +- down_read(&mm->mmap_sem); ++ down_write(&mm->mmap_sem); + vma = find_vma(mm, ip); + if (vma) { + file = vma->vm_file; +@@ -1569,7 +1569,7 @@ static inline int seq_print_user_ip(stru + if (ret) + ret = trace_seq_printf(s, "[+0x%lx]", ip - vmstart); + } +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + } + if (ret && ((sym_flags & TRACE_ITER_SYM_ADDR) || !file)) + ret = trace_seq_printf(s, " <" IP_FMT ">", ip); +Index: linux-2.6.29.y/mm/fremap.c +=================================================================== +--- linux-2.6.29.y.orig/mm/fremap.c ++++ linux-2.6.29.y/mm/fremap.c +@@ -149,7 +149,8 @@ SYSCALL_DEFINE5(remap_file_pages, unsign + #endif + + /* We need down_write() to change vma->vm_flags. */ +- down_read(&mm->mmap_sem); ++ down_write(&mm->mmap_sem); ++ has_write_lock = 1; + retry: + vma = find_vma(mm, start); + +Index: linux-2.6.29.y/mm/memory.c +=================================================================== +--- linux-2.6.29.y.orig/mm/memory.c ++++ linux-2.6.29.y/mm/memory.c +@@ -3080,7 +3080,7 @@ int access_process_vm(struct task_struct + if (!mm) + return 0; + +- down_read(&mm->mmap_sem); ++ down_write(&mm->mmap_sem); + /* ignore errors, just check how much was successfully transferred */ + while (len) { + int bytes, ret, offset; +@@ -3127,7 +3127,7 @@ int access_process_vm(struct task_struct + buf += bytes; + addr += bytes; + } +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + mmput(mm); + + return buf - old_buf; +@@ -3148,7 +3148,7 @@ void print_vma_addr(char *prefix, unsign + if (preempt_count()) + return; + +- down_read(&mm->mmap_sem); ++ down_write(&mm->mmap_sem); + vma = find_vma(mm, ip); + if (vma && vma->vm_file) { + struct file *f = vma->vm_file; +@@ -3168,7 +3168,7 @@ void print_vma_addr(char *prefix, unsign + free_page((unsigned long)buf); + } + } +- up_read(¤t->mm->mmap_sem); ++ up_write(¤t->mm->mmap_sem); + } + + #ifdef CONFIG_PROVE_LOCKING +Index: linux-2.6.29.y/mm/mempolicy.c +=================================================================== +--- linux-2.6.29.y.orig/mm/mempolicy.c ++++ linux-2.6.29.y/mm/mempolicy.c +@@ -693,10 +693,10 @@ static long do_get_mempolicy(int *policy + * vma/shared policy at addr is NULL. We + * want to return MPOL_DEFAULT in this case. + */ +- down_read(&mm->mmap_sem); ++ down_write(&mm->mmap_sem); + vma = find_vma_intersection(mm, addr, addr+1); + if (!vma) { +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + return -EFAULT; + } + if (vma->vm_ops && vma->vm_ops->get_policy) +@@ -733,7 +733,7 @@ static long do_get_mempolicy(int *policy + } + + if (vma) { +- up_read(¤t->mm->mmap_sem); ++ up_write(¤t->mm->mmap_sem); + vma = NULL; + } + +@@ -744,7 +744,7 @@ static long do_get_mempolicy(int *policy + out: + mpol_cond_put(pol); + if (vma) +- up_read(¤t->mm->mmap_sem); ++ up_write(¤t->mm->mmap_sem); + return err; + } + +@@ -810,7 +810,7 @@ int do_migrate_pages(struct mm_struct *m + if (err) + return err; + +- down_read(&mm->mmap_sem); ++ down_write(&mm->mmap_sem); + + err = migrate_vmas(mm, from_nodes, to_nodes, flags); + if (err) +@@ -876,7 +876,7 @@ int do_migrate_pages(struct mm_struct *m + break; + } + out: +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + if (err < 0) + return err; + return busy; +Index: linux-2.6.29.y/mm/migrate.c +=================================================================== +--- linux-2.6.29.y.orig/mm/migrate.c ++++ linux-2.6.29.y/mm/migrate.c +@@ -821,7 +821,7 @@ static int do_move_page_to_node_array(st + LIST_HEAD(pagelist); + + migrate_prep(); +- down_read(&mm->mmap_sem); ++ down_write(&mm->mmap_sem); + + /* + * Build a list of pages to migrate +@@ -881,7 +881,7 @@ set_status: + err = migrate_pages(&pagelist, new_page_node, + (unsigned long)pm); + +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + return err; + } + +@@ -977,7 +977,7 @@ static void do_pages_stat_array(struct m + { + unsigned long i; + +- down_read(&mm->mmap_sem); ++ down_write(&mm->mmap_sem); + + for (i = 0; i < nr_pages; i++) { + unsigned long addr = (unsigned long)(*pages); +@@ -1008,7 +1008,7 @@ set_status: + status++; + } + +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + } + + /* +Index: linux-2.6.29.y/mm/msync.c +=================================================================== +--- linux-2.6.29.y.orig/mm/msync.c ++++ linux-2.6.29.y/mm/msync.c +@@ -54,7 +54,7 @@ SYSCALL_DEFINE3(msync, unsigned long, st + * If the interval [start,end) covers some unmapped address ranges, + * just ignore them, but return -ENOMEM at the end. + */ +- down_read(&mm->mmap_sem); ++ down_write(&mm->mmap_sem); + vma = find_vma(mm, start); + for (;;) { + struct file *file; +@@ -81,12 +81,12 @@ SYSCALL_DEFINE3(msync, unsigned long, st + if ((flags & MS_SYNC) && file && + (vma->vm_flags & VM_SHARED)) { + get_file(file); +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + error = vfs_fsync(file, file->f_path.dentry, 0); + fput(file); + if (error || start >= end) + goto out; +- down_read(&mm->mmap_sem); ++ down_write(&mm->mmap_sem); + vma = find_vma(mm, start); + } else { + if (start >= end) { +@@ -97,7 +97,7 @@ SYSCALL_DEFINE3(msync, unsigned long, st + } + } + out_unlock: +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + out: + return error ? : unmapped_error; + } +Index: linux-2.6.29.y/mm/nommu.c +=================================================================== +--- linux-2.6.29.y.orig/mm/nommu.c ++++ linux-2.6.29.y/mm/nommu.c +@@ -1889,7 +1889,7 @@ int access_process_vm(struct task_struct + if (!mm) + return 0; + +- down_read(&mm->mmap_sem); ++ down_write(&mm->mmap_sem); + + /* the access must start within one of the target process's mappings */ + vma = find_vma(mm, addr); +@@ -1909,7 +1909,7 @@ int access_process_vm(struct task_struct + len = 0; + } + +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + mmput(mm); + return len; + } +Index: linux-2.6.29.y/mm/util.c +=================================================================== +--- linux-2.6.29.y.orig/mm/util.c ++++ linux-2.6.29.y/mm/util.c +@@ -198,10 +198,10 @@ int __attribute__((weak)) get_user_pages + struct mm_struct *mm = current->mm; + int ret; + +- down_read(&mm->mmap_sem); ++ down_write(&mm->mmap_sem); + ret = get_user_pages(current, mm, start, nr_pages, + write, 0, pages, NULL); +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + + return ret; + } +Index: linux-2.6.29.y/arch/x86/mm/fault.c +=================================================================== +--- linux-2.6.29.y.orig/arch/x86/mm/fault.c ++++ linux-2.6.29.y/arch/x86/mm/fault.c +@@ -687,11 +687,11 @@ void __kprobes do_page_fault(struct pt_r + * source. If this is invalid we can skip the address space check, + * thus avoiding the deadlock. + */ +- if (!down_read_trylock(&mm->mmap_sem)) { ++ if (!down_write_trylock(&mm->mmap_sem)) { + if ((error_code & PF_USER) == 0 && + !search_exception_tables(regs->ip)) + goto bad_area_nosemaphore; +- down_read(&mm->mmap_sem); ++ down_write(&mm->mmap_sem); + } + + vma = find_vma(mm, address); +@@ -763,7 +763,7 @@ good_area: + tsk->thread.screen_bitmap |= 1 << bit; + } + #endif +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + return; + + /* +@@ -771,7 +771,7 @@ good_area: + * Fix it, but check if it's kernel or user first.. + */ + bad_area: +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + + bad_area_nosemaphore: + /* User mode accesses just cause a SIGSEGV */ +@@ -867,12 +867,12 @@ out_of_memory: + * We ran out of memory, call the OOM killer, and return the userspace + * (which will retry the fault, or kill us if we got oom-killed). + */ +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + pagefault_out_of_memory(); + return; + + do_sigbus: +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + + /* Kernel mode? Handle exceptions or die */ + if (!(error_code & PF_USER)) +Index: linux-2.6.29.y/arch/x86/mm/gup.c +=================================================================== +--- linux-2.6.29.y.orig/arch/x86/mm/gup.c ++++ linux-2.6.29.y/arch/x86/mm/gup.c +@@ -280,10 +280,10 @@ slow_irqon: + start += nr << PAGE_SHIFT; + pages += nr; + +- down_read(&mm->mmap_sem); ++ down_write(&mm->mmap_sem); + ret = get_user_pages(current, mm, start, + (end - start) >> PAGE_SHIFT, write, 0, pages, NULL); +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + + /* Have to be a bit careful with return values */ + if (nr > 0) { +Index: linux-2.6.29.y/fs/proc/base.c +=================================================================== +--- linux-2.6.29.y.orig/fs/proc/base.c ++++ linux-2.6.29.y/fs/proc/base.c +@@ -247,7 +247,7 @@ struct mm_struct *mm_for_maps(struct tas + struct mm_struct *mm = get_task_mm(task); + if (!mm) + return NULL; +- down_read(&mm->mmap_sem); ++ down_write(&mm->mmap_sem); + task_lock(task); + if (task->mm != mm) + goto out; +@@ -258,7 +258,7 @@ struct mm_struct *mm_for_maps(struct tas + return mm; + out: + task_unlock(task); +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + mmput(mm); + return NULL; + } +Index: linux-2.6.29.y/fs/proc/task_mmu.c +=================================================================== +--- linux-2.6.29.y.orig/fs/proc/task_mmu.c ++++ linux-2.6.29.y/fs/proc/task_mmu.c +@@ -85,7 +85,7 @@ static void vma_stop(struct proc_maps_pr + { + if (vma && vma != priv->tail_vma) { + struct mm_struct *mm = vma->vm_mm; +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + mmput(mm); + } + } +@@ -151,7 +151,7 @@ out: + + /* End of vmas has been reached */ + m->version = (tail_vma != NULL)? 0: -1UL; +- up_read(&mm->mmap_sem); ++ up_write(&mm->mmap_sem); + mmput(mm); + return tail_vma; + } +@@ -679,10 +679,10 @@ static ssize_t pagemap_read(struct file + if (!pages) + goto out_mm; + +- down_read(¤t->mm->mmap_sem); ++ down_write(¤t->mm->mmap_sem); + ret = get_user_pages(current, current->mm, uaddr, pagecount, + 1, 0, pages, NULL); +- up_read(¤t->mm->mmap_sem); ++ up_write(¤t->mm->mmap_sem); + + if (ret < 0) + goto out_free; +Index: linux-2.6.29.y/mm/madvise.c +=================================================================== +--- linux-2.6.29.y.orig/mm/madvise.c ++++ linux-2.6.29.y/mm/madvise.c +@@ -19,6 +19,8 @@ + */ + static int madvise_need_mmap_write(int behavior) + { ++ return 1; // always take mmap_sem fo writing ++ + switch (behavior) { + case MADV_REMOVE: + case MADV_WILLNEED: +Index: linux-2.6.29.y/mm/mincore.c +=================================================================== +--- linux-2.6.29.y.orig/mm/mincore.c ++++ linux-2.6.29.y/mm/mincore.c +@@ -209,9 +209,9 @@ SYSCALL_DEFINE3(mincore, unsigned long, + * Do at most PAGE_SIZE entries per iteration, due to + * the temporary buffer size. + */ +- down_read(¤t->mm->mmap_sem); ++ down_write(¤t->mm->mmap_sem); + retval = do_mincore(start, tmp, min(pages, PAGE_SIZE)); +- up_read(¤t->mm->mmap_sem); ++ up_write(¤t->mm->mmap_sem); + + if (retval <= 0) + break; +Index: linux-2.6.29.y/arch/x86/lib/usercopy_32.c +=================================================================== +--- linux-2.6.29.y.orig/arch/x86/lib/usercopy_32.c ++++ linux-2.6.29.y/arch/x86/lib/usercopy_32.c +@@ -745,18 +745,18 @@ unsigned long __copy_to_user_ll(void __u + len = n; + + survive: +- down_read(¤t->mm->mmap_sem); ++ down_write(¤t->mm->mmap_sem); + retval = get_user_pages(current, current->mm, + (unsigned long)to, 1, 1, 0, &pg, NULL); + + if (retval == -ENOMEM && is_global_init(current)) { +- up_read(¤t->mm->mmap_sem); ++ up_write(¤t->mm->mmap_sem); + congestion_wait(WRITE, HZ/50); + goto survive; + } + + if (retval != 1) { +- up_read(¤t->mm->mmap_sem); ++ up_write(¤t->mm->mmap_sem); + break; + } + +@@ -765,7 +765,7 @@ survive: + kunmap_atomic(maddr, KM_USER0); + set_page_dirty_lock(pg); + put_page(pg); +- up_read(¤t->mm->mmap_sem); ++ up_write(¤t->mm->mmap_sem); + + from += len; + to += len; +Index: linux-2.6.29.y/drivers/dma/iovlock.c +=================================================================== +--- linux-2.6.29.y.orig/drivers/dma/iovlock.c ++++ linux-2.6.29.y/drivers/dma/iovlock.c +@@ -94,7 +94,7 @@ struct dma_pinned_list *dma_pin_iovec_pa + pages += page_list->nr_pages; + + /* pin pages down */ +- down_read(¤t->mm->mmap_sem); ++ down_write(¤t->mm->mmap_sem); + ret = get_user_pages( + current, + current->mm, +@@ -104,7 +104,7 @@ struct dma_pinned_list *dma_pin_iovec_pa + 0, /* force */ + page_list->pages, + NULL); +- up_read(¤t->mm->mmap_sem); ++ up_write(¤t->mm->mmap_sem); + + if (ret != page_list->nr_pages) + goto unpin; +Index: linux-2.6.29.y/drivers/gpu/drm/via/via_dmablit.c +=================================================================== +--- linux-2.6.29.y.orig/drivers/gpu/drm/via/via_dmablit.c ++++ linux-2.6.29.y/drivers/gpu/drm/via/via_dmablit.c +@@ -239,14 +239,14 @@ via_lock_all_dma_pages(drm_via_sg_info_t + if (NULL == (vsg->pages = vmalloc(sizeof(struct page *) * vsg->num_pages))) + return -ENOMEM; + memset(vsg->pages, 0, sizeof(struct page *) * vsg->num_pages); +- down_read(¤t->mm->mmap_sem); ++ down_write(¤t->mm->mmap_sem); + ret = get_user_pages(current, current->mm, + (unsigned long)xfer->mem_addr, + vsg->num_pages, + (vsg->direction == DMA_FROM_DEVICE), + 0, vsg->pages, NULL); + +- up_read(¤t->mm->mmap_sem); ++ up_write(¤t->mm->mmap_sem); + if (ret != vsg->num_pages) { + if (ret < 0) + return ret; +Index: linux-2.6.29.y/drivers/media/video/videobuf-dma-sg.c +=================================================================== +--- linux-2.6.29.y.orig/drivers/media/video/videobuf-dma-sg.c ++++ linux-2.6.29.y/drivers/media/video/videobuf-dma-sg.c +@@ -177,9 +177,9 @@ int videobuf_dma_init_user(struct videob + unsigned long data, unsigned long size) + { + int ret; +- down_read(¤t->mm->mmap_sem); ++ down_write(¤t->mm->mmap_sem); + ret = videobuf_dma_init_user_locked(dma, direction, data, size); +- up_read(¤t->mm->mmap_sem); ++ up_write(¤t->mm->mmap_sem); + + return ret; + } +Index: linux-2.6.29.y/drivers/scsi/st.c +=================================================================== +--- linux-2.6.29.y.orig/drivers/scsi/st.c ++++ linux-2.6.29.y/drivers/scsi/st.c +@@ -4555,7 +4555,7 @@ static int sgl_map_user_pages(struct st_ + return -ENOMEM; + + /* Try to fault in all of the necessary pages */ +- down_read(¤t->mm->mmap_sem); ++ down_write(¤t->mm->mmap_sem); + /* rw==READ means read from drive, write into memory area */ + res = get_user_pages( + current, +@@ -4566,7 +4566,7 @@ static int sgl_map_user_pages(struct st_ + 0, /* don't force */ + pages, + NULL); +- up_read(¤t->mm->mmap_sem); ++ up_write(¤t->mm->mmap_sem); + + /* Errors and no page mapped should return here */ + if (res < nr_pages) +Index: linux-2.6.29.y/fs/nfs/direct.c +=================================================================== +--- linux-2.6.29.y.orig/fs/nfs/direct.c ++++ linux-2.6.29.y/fs/nfs/direct.c +@@ -306,10 +306,10 @@ static ssize_t nfs_direct_read_schedule_ + if (unlikely(!data)) + break; + +- down_read(¤t->mm->mmap_sem); ++ down_write(¤t->mm->mmap_sem); + result = get_user_pages(current, current->mm, user_addr, + data->npages, 1, 0, data->pagevec, NULL); +- up_read(¤t->mm->mmap_sem); ++ up_write(¤t->mm->mmap_sem); + if (result < 0) { + nfs_readdata_release(data); + break; +@@ -720,10 +720,10 @@ static ssize_t nfs_direct_write_schedule + if (unlikely(!data)) + break; + +- down_read(¤t->mm->mmap_sem); ++ down_write(¤t->mm->mmap_sem); + result = get_user_pages(current, current->mm, user_addr, + data->npages, 0, 0, data->pagevec, NULL); +- up_read(¤t->mm->mmap_sem); ++ up_write(¤t->mm->mmap_sem); + if (result < 0) { + nfs_writedata_release(data); + break; +Index: linux-2.6.29.y/fs/fuse/dev.c +=================================================================== +--- linux-2.6.29.y.orig/fs/fuse/dev.c ++++ linux-2.6.29.y/fs/fuse/dev.c +@@ -545,10 +545,10 @@ static int fuse_copy_fill(struct fuse_co + cs->iov++; + cs->nr_segs--; + } +- down_read(¤t->mm->mmap_sem); ++ down_write(¤t->mm->mmap_sem); + err = get_user_pages(current, current->mm, cs->addr, 1, cs->write, 0, + &cs->pg, NULL); +- up_read(¤t->mm->mmap_sem); ++ up_write(¤t->mm->mmap_sem); + if (err < 0) + return err; + BUG_ON(err != 1); +Index: linux-2.6.29.y/fs/fuse/file.c +=================================================================== +--- linux-2.6.29.y.orig/fs/fuse/file.c ++++ linux-2.6.29.y/fs/fuse/file.c +@@ -948,10 +948,10 @@ static int fuse_get_user_pages(struct fu + nbytes = min(nbytes, (unsigned) FUSE_MAX_PAGES_PER_REQ << PAGE_SHIFT); + npages = (nbytes + offset + PAGE_SIZE - 1) >> PAGE_SHIFT; + npages = clamp(npages, 1, FUSE_MAX_PAGES_PER_REQ); +- down_read(¤t->mm->mmap_sem); ++ down_write(¤t->mm->mmap_sem); + npages = get_user_pages(current, current->mm, user_addr, npages, write, + 0, req->pages, NULL); +- up_read(¤t->mm->mmap_sem); ++ up_write(¤t->mm->mmap_sem); + if (npages < 0) + return npages; + diff --git a/uni-final-project/sptree/check-vma-splay-tree.patch b/uni-final-project/sptree/check-vma-splay-tree.patch new file mode 100644 index 0000000..03120b7 --- /dev/null +++ b/uni-final-project/sptree/check-vma-splay-tree.patch @@ -0,0 +1,133 @@ +--- + lib/Kconfig.debug | 4 ++++ + mm/mmap.c | 41 +++++++++++++++++++++++++++++++++++++++++ + mm/vma-sptree.c | 11 +++++++++++ + 3 files changed, 56 insertions(+) + +Index: linux-2.6.29.y/mm/mmap.c +=================================================================== +--- linux-2.6.29.y.orig/mm/mmap.c ++++ linux-2.6.29.y/mm/mmap.c +@@ -44,6 +44,31 @@ + #define arch_rebalance_pgtables(addr, len) (addr) + #endif + ++#ifdef CONFIG_DEBUG_VMA_SPTREE ++static void check_trees(struct mm_struct *mm) ++{ ++ struct vm_area_struct *p; ++ ++ for (p = mm->mmap; p; p = p->vm_next) ++ sp_find_vma(mm, p->vm_start, NULL); ++} ++ ++static inline void ++check_list(const struct mm_struct *mm) ++{ ++ struct vm_area_struct *p = mm->mmap; ++ ++ for (p = mm->mmap; p != NULL; p = p->vm_next) { ++ if (!p->vm_next) ++ break; ++ BUG_ON(p->vm_end > p->vm_next->vm_end); ++ } ++} ++#else // !CONFIG_DEBUG_VMA_SPTREE ++#define check_trees(mm) while (0) { } ++#define check_list(mm) while (0) { } ++#endif // !CONFIG_DEBUG_VMA_SPTREE ++ + static void unmap_region(struct mm_struct *mm, + struct vm_area_struct *vma, struct vm_area_struct *prev, + unsigned long start, unsigned long end); +@@ -399,9 +424,15 @@ __vma_link(struct mm_struct *mm, struct + { + struct vm_area_struct *sp_prev, *sp_parent; + ++ check_list(mm); ++ check_trees(mm); ++ + sp_vma_insert(mm, vma, &sp_prev, &sp_parent); + __vma_link_list(mm, vma, sp_prev, sp_parent); + __anon_vma_link(vma); ++ ++ check_list(mm); ++ check_trees(mm); + } + + static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma) +@@ -467,6 +498,8 @@ void vma_adjust(struct vm_area_struct *v + long adjust_next = 0; + int remove_next = 0; + ++ check_trees(mm); ++ + if (next && !insert) { + if (end >= next->vm_end) { + /* +@@ -609,6 +642,8 @@ again: remove_next = 1 + (end > next-> + } + + validate_mm(mm); ++ ++ check_trees(mm); + } + + /* Flags that can be inherited from an existing mapping when merging */ +@@ -1689,6 +1724,9 @@ detach_vmas_to_be_unmapped(struct mm_str + struct vm_area_struct *tail_vma = NULL; + unsigned long addr; + ++ check_list(mm); ++ check_trees(mm); ++ + insertion_point = (prev ? &prev->vm_next : &mm->mmap); + do { + sp_vma_erase(mm, vma); +@@ -1703,6 +1741,9 @@ detach_vmas_to_be_unmapped(struct mm_str + else + addr = vma ? vma->vm_start : mm->mmap_base; + mm->unmap_area(mm, addr); ++ ++ check_list(mm); ++ check_trees(mm); + } + + /* +Index: linux-2.6.29.y/mm/vma-sptree.c +=================================================================== +--- linux-2.6.29.y.orig/mm/vma-sptree.c ++++ linux-2.6.29.y/mm/vma-sptree.c +@@ -242,6 +242,17 @@ void sp_vma_erase(struct mm_struct *mm, + return; + + node = top_down_splay(*root, NULL, NULL, vma->vm_start); ++#ifdef CONFIG_DEBUG_VMA_SPTREE ++ if ((node->vm_start != vma->vm_start) || ++ (node->vm_end != vma->vm_end)) { ++ /* not found */ ++ printk("-> vma: 0x%lx-0x%lx\n", vma->vm_start, vma->vm_end); ++ printk("-> node: 0x%lx-0x%lx\n", node->vm_start, node->vm_end); ++ BUG(); ++ *root = &node->vm_sp; ++ return; ++ } ++#endif + + if (!node->vm_sp.sp_left) { + new_root = sp_entry(node->vm_sp.sp_right, +Index: linux-2.6.29.y/lib/Kconfig.debug +=================================================================== +--- linux-2.6.29.y.orig/lib/Kconfig.debug ++++ linux-2.6.29.y/lib/Kconfig.debug +@@ -503,6 +503,10 @@ config DEBUG_VM + + If unsure, say N. + ++config DEBUG_VMA_SPTREE ++ bool "Debug VMA Splay Tree" ++ depends on DEBUG_KERNEL ++ + config DEBUG_VIRTUAL + bool "Debug VM translations" + depends on DEBUG_KERNEL && X86 diff --git a/uni-final-project/sptree/introduce-vma-splay-tree.patch b/uni-final-project/sptree/introduce-vma-splay-tree.patch new file mode 100644 index 0000000..d711951 --- /dev/null +++ b/uni-final-project/sptree/introduce-vma-splay-tree.patch @@ -0,0 +1,481 @@ +--- + include/linux/init_task.h | 1 + include/linux/mm.h | 12 + + include/linux/mm_types.h | 3 + include/linux/sptree.h | 38 +++++ + kernel/fork.c | 1 + mm/Makefile | 2 + mm/vma-sptree.c | 335 ++++++++++++++++++++++++++++++++++++++++++++++ + 7 files changed, 391 insertions(+), 1 deletion(-) + +Index: linux-2.6.29.y/include/linux/sptree.h +=================================================================== +--- /dev/null ++++ linux-2.6.29.y/include/linux/sptree.h +@@ -0,0 +1,38 @@ ++/* ++ * Splay Trees ++ * ++ * (C) 2009 Luiz Fernando N. Capitulino ++ * ++ * This program is free software; you can redistribute it and/or modify ++ * it under the terms of the GNU General Public License as published by ++ * the Free Software Foundation; either version 2 of the License, or ++ * (at your option) any later version. ++ * ++ * ++ * This implementation is done in the Linux kernel's rbtree style, in ++ * which the user has to implement his or her own insert and search ++ * cores. This way we avoid callbacks and the associated performance ++ * loss. ++ */ ++#ifndef _LINUX_SPTREE_H ++#define _LINUX_SPTREE_H ++ ++#include ++#include ++ ++struct sp_node ++{ ++ struct sp_node *sp_right; ++ struct sp_node *sp_left; ++}; ++ ++struct sp_root ++{ ++ struct sp_node *sp_node; ++}; ++ ++#define SP_ROOT (struct sp_root) { NULL, } ++ ++#define sp_entry(ptr, type, member) container_of(ptr, type, member) ++ ++#endif /* _LINUX_SPTREE_H */ +Index: linux-2.6.29.y/mm/vma-sptree.c +=================================================================== +--- /dev/null ++++ linux-2.6.29.y/mm/vma-sptree.c +@@ -0,0 +1,335 @@ ++/* ++ * VMA Splay Tree ++ * ++ * Luiz Fernando N. Capitulino ++ * ++ */ ++#include ++#include ++ ++/* ++ * top_down_splay(): Splay Tree core. All functions use it but ++ * find_vma_prev(). ++ */ ++static struct vm_area_struct *top_down_splay(struct sp_node *root, ++ struct vm_area_struct **prev, ++ struct vm_area_struct **last, ++ unsigned long addr) ++{ ++ struct sp_node *r, *l, nil; ++ struct vm_area_struct *node, *p, *pprev, *plast; ++ ++ r = l = &nil; ++ nil.sp_left = nil.sp_right = NULL; ++ plast = pprev = NULL; ++ node = sp_entry(root, struct vm_area_struct, vm_sp); ++ ++ for (;;) { ++ if (node->vm_end > addr) { ++ plast = node; ++ ++ if (node->vm_start <= addr) ++ break; ++ ++ if (!node->vm_sp.sp_left) ++ break; ++ ++ p = sp_entry(node->vm_sp.sp_left, ++ struct vm_area_struct, vm_sp); ++ if (p->vm_end > addr) { ++ /* rotate right */ ++ node->vm_sp.sp_left = p->vm_sp.sp_right; ++ p->vm_sp.sp_right = &node->vm_sp; ++ node = plast = p; ++ ++ if (node->vm_start <= addr) ++ break; ++ ++ if (!node->vm_sp.sp_left) ++ break; ++ } ++ ++ /* link right */ ++ r->sp_left = &node->vm_sp; ++ r = &node->vm_sp; ++ node = sp_entry(node->vm_sp.sp_left, ++ struct vm_area_struct, vm_sp); ++ ++ } else { ++ pprev = node; ++ ++ if (!node->vm_sp.sp_right) ++ break; ++ ++ p = sp_entry(node->vm_sp.sp_right, ++ struct vm_area_struct, vm_sp); ++ if (p->vm_end <= addr) { ++ /* rotate left */ ++ node->vm_sp.sp_right = p->vm_sp.sp_left; ++ p->vm_sp.sp_left = &node->vm_sp; ++ node = pprev = p; ++ ++ if (!node->vm_sp.sp_right) ++ break; ++ } ++ ++ /* link left */ ++ l->sp_right = &node->vm_sp; ++ l = &node->vm_sp; ++ node = sp_entry(node->vm_sp.sp_right, ++ struct vm_area_struct, vm_sp); ++ } ++ } ++ ++ /* assemble */ ++ l->sp_right = node->vm_sp.sp_left; ++ r->sp_left = node->vm_sp.sp_right; ++ node->vm_sp.sp_left = nil.sp_right; ++ node->vm_sp.sp_right = nil.sp_left; ++ ++ if (prev) ++ *prev = pprev; ++ if (last) ++ *last = plast; ++ ++ return node; ++} ++ ++/* ++ * find_vma_prev() with top-down splaying. Unfortunately it duplicates ++ * code from top_down_splay(). ++ */ ++struct vm_area_struct *sp_find_vma_prev(struct mm_struct *mm, ++ unsigned long addr, ++ struct vm_area_struct **prev) ++{ ++ struct sp_node *r, *l, nil; ++ struct vm_area_struct *node, *p, *pprev, *vma; ++ ++ pprev = vma = NULL; ++ ++ if (unlikely(!mm) || unlikely(!mm->mm_sp.sp_node)) ++ goto out; ++ ++ vma = mm->mmap; ++ r = l = &nil; ++ nil.sp_left = nil.sp_right = NULL; ++ node = sp_entry(mm->mm_sp.sp_node, struct vm_area_struct, vm_sp); ++ ++ for (;;) { ++ if (node->vm_end > addr) { ++ if (!node->vm_sp.sp_left) ++ break; ++ ++ p = sp_entry(node->vm_sp.sp_left, ++ struct vm_area_struct, vm_sp); ++ if (p->vm_end > addr) { ++ /* rotate right */ ++ node->vm_sp.sp_left = p->vm_sp.sp_right; ++ p->vm_sp.sp_right = &node->vm_sp; ++ node = p; ++ ++ if (!node->vm_sp.sp_left) ++ break; ++ } ++ ++ /* link right */ ++ r->sp_left = &node->vm_sp; ++ r = &node->vm_sp; ++ node = sp_entry(node->vm_sp.sp_left, ++ struct vm_area_struct, vm_sp); ++ ++ } else { ++ pprev = node; ++ ++ if (!pprev->vm_next || (addr < pprev->vm_next->vm_end)) ++ break; ++ ++ if (!node->vm_sp.sp_right) ++ break; ++ ++ p = sp_entry(node->vm_sp.sp_right, ++ struct vm_area_struct, vm_sp); ++ if (p->vm_end <= addr) { ++ /* rotate left */ ++ node->vm_sp.sp_right = p->vm_sp.sp_left; ++ p->vm_sp.sp_left = &node->vm_sp; ++ node = pprev = p; ++ ++ if (!pprev->vm_next || ++ (addr < pprev->vm_next->vm_end)) ++ break; ++ ++ if (!node->vm_sp.sp_right) ++ break; ++ } ++ ++ /* link left */ ++ l->sp_right = &node->vm_sp; ++ l = &node->vm_sp; ++ node = sp_entry(node->vm_sp.sp_right, ++ struct vm_area_struct, vm_sp); ++ } ++ } ++ ++ /* assemble */ ++ l->sp_right = node->vm_sp.sp_left; ++ r->sp_left = node->vm_sp.sp_right; ++ node->vm_sp.sp_left = nil.sp_right; ++ node->vm_sp.sp_right = nil.sp_left; ++ ++ mm->mm_sp.sp_node = &node->vm_sp; ++ ++out: ++ *prev = pprev; ++ return pprev ? pprev->vm_next : vma; ++} ++ ++struct vm_area_struct *sp_find_vma(struct mm_struct *mm, ++ unsigned long addr, ++ struct vm_area_struct **pprev) ++{ ++ struct vm_area_struct *p, *last; ++ ++ if (unlikely(!mm->mm_sp.sp_node)) ++ return NULL; ++ ++ p = top_down_splay(mm->mm_sp.sp_node, pprev, &last, addr); ++ mm->mm_sp.sp_node = &p->vm_sp; ++ ++ return ((p->vm_end > addr && p->vm_start <= addr) ? p : last); ++} ++ ++void sp_vma_insert(struct mm_struct *mm, struct vm_area_struct *new, ++ struct vm_area_struct **prev, struct vm_area_struct **parent) ++{ ++ struct sp_node **root = &mm->mm_sp.sp_node; ++ struct vm_area_struct *node, *pparent = NULL; ++ ++ if (unlikely(*root == NULL)) { ++ new->vm_sp.sp_left = new->vm_sp.sp_right = NULL; ++ if (prev) ++ *prev = NULL; ++ goto out; ++ } ++ ++ node = top_down_splay(*root, prev, NULL, new->vm_start); ++ ++ if (node->vm_end > new->vm_start) { ++ new->vm_sp.sp_left = node->vm_sp.sp_left; ++ new->vm_sp.sp_right = &node->vm_sp; ++ node->vm_sp.sp_left = NULL; ++ pparent = node; ++ } else { ++ /* node->vm_end <= new->vm_start */ ++ new->vm_sp.sp_right = node->vm_sp.sp_right; ++ new->vm_sp.sp_left = &node->vm_sp; ++ node->vm_sp.sp_right = NULL; ++ } ++ ++out: ++ *root = &new->vm_sp; ++ if (parent) ++ *parent = pparent; ++} ++ ++void sp_vma_erase(struct mm_struct *mm, struct vm_area_struct *vma) ++{ ++ struct vm_area_struct *node, *new_root; ++ struct sp_node **root = &mm->mm_sp.sp_node; ++ ++ if (unlikely(*root == NULL)) ++ return; ++ ++ node = top_down_splay(*root, NULL, NULL, vma->vm_start); ++ ++ if (!node->vm_sp.sp_left) { ++ new_root = sp_entry(node->vm_sp.sp_right, ++ struct vm_area_struct, vm_sp); ++ } else { ++ new_root = top_down_splay(node->vm_sp.sp_left, NULL, NULL, ++ vma->vm_start); ++ new_root->vm_sp.sp_right = node->vm_sp.sp_right; ++ } ++ ++ *root = &new_root->vm_sp; ++} ++ ++#if 0 ++ ++/* debug functions */ ++ ++void sp_show_tree(const struct vm_area_struct *vma) ++{ ++ if (!vma) ++ return; ++ ++ printk("-> 0x%lx-0x%lx\n", vma->vm_start, vma->vm_end); ++ if (vma->vm_sp.sp_left) ++ sp_show_tree(sp_entry(vma->vm_sp.sp_left, ++ struct vm_area_struct, vm_sp)); ++ if (vma->vm_sp.sp_right) ++ sp_show_tree(sp_entry(vma->vm_sp.sp_right, ++ struct vm_area_struct, vm_sp)); ++} ++ ++/* read-only find_vma_prev() version */ ++struct vm_area_struct * ++sp_find_vma_prev(struct mm_struct *mm, unsigned long addr, ++ struct vm_area_struct **pprev) ++{ ++ struct sp_node *sp_node; ++ struct vm_area_struct *vma = NULL, *prev = NULL; ++ ++ if (!mm) ++ goto out; ++ ++ /* Guard against addr being lower than the first VMA */ ++ vma = mm->mmap; ++ ++ sp_node = mm->mm_sp.sp_node; ++ ++ while (sp_node) { ++ struct vm_area_struct *vma_tmp; ++ vma_tmp = sp_entry(sp_node, struct vm_area_struct, vm_sp); ++ ++ if (addr < vma_tmp->vm_end) { ++ sp_node = sp_node->sp_left; ++ } else { ++ prev = vma_tmp; ++ if (!prev->vm_next || (addr < prev->vm_next->vm_end)) ++ break; ++ sp_node = sp_node->sp_right; ++ } ++ } ++ ++out: ++ *pprev = prev; ++ return prev ? prev->vm_next : vma; ++} ++ ++/* read-only find_vma() version */ ++struct vm_area_struct *sp_ro_find_vma(struct mm_struct *mm, unsigned long addr) ++{ ++ struct vm_area_struct *vma = NULL; ++ struct sp_node *sp_node = mm->mm_sp.sp_node; ++ ++ while (sp_node) { ++ struct vm_area_struct *vma_tmp; ++ ++ vma_tmp = sp_entry(sp_node, ++ struct vm_area_struct, vm_sp); ++ ++ if (vma_tmp->vm_end > addr) { ++ vma = vma_tmp; ++ if (vma_tmp->vm_start <= addr) ++ break; ++ sp_node = sp_node->sp_left; ++ } else { ++ sp_node = sp_node->sp_right; ++ } ++ } ++ ++ return vma; ++} ++#endif +Index: linux-2.6.29.y/include/linux/init_task.h +=================================================================== +--- linux-2.6.29.y.orig/include/linux/init_task.h ++++ linux-2.6.29.y/include/linux/init_task.h +@@ -30,6 +30,7 @@ extern struct fs_struct init_fs; + #define INIT_MM(name) \ + { \ + .mm_rb = RB_ROOT, \ ++ .mm_sp = SP_ROOT, \ + .pgd = swapper_pg_dir, \ + .mm_users = ATOMIC_INIT(2), \ + .mm_count = ATOMIC_INIT(1), \ +Index: linux-2.6.29.y/include/linux/mm_types.h +=================================================================== +--- linux-2.6.29.y.orig/include/linux/mm_types.h ++++ linux-2.6.29.y/include/linux/mm_types.h +@@ -8,6 +8,7 @@ + #include + #include + #include ++#include + #include + #include + #include +@@ -132,6 +133,7 @@ struct vm_area_struct { + unsigned long vm_flags; /* Flags, see mm.h. */ + + struct rb_node vm_rb; ++ struct sp_node vm_sp; + + /* + * For areas with an address space and backing store, +@@ -190,6 +192,7 @@ struct core_state { + struct mm_struct { + struct vm_area_struct * mmap; /* list of VMAs */ + struct rb_root mm_rb; ++ struct sp_root mm_sp; + struct vm_area_struct * mmap_cache; /* last find_vma result */ + unsigned long (*get_unmapped_area) (struct file *filp, + unsigned long addr, unsigned long len, +Index: linux-2.6.29.y/kernel/fork.c +=================================================================== +--- linux-2.6.29.y.orig/kernel/fork.c ++++ linux-2.6.29.y/kernel/fork.c +@@ -281,6 +281,7 @@ static int dup_mmap(struct mm_struct *mm + mm->map_count = 0; + cpus_clear(mm->cpu_vm_mask); + mm->mm_rb = RB_ROOT; ++ mm->mm_sp = SP_ROOT; + rb_link = &mm->mm_rb.rb_node; + rb_parent = NULL; + pprev = &mm->mmap; +Index: linux-2.6.29.y/mm/Makefile +=================================================================== +--- linux-2.6.29.y.orig/mm/Makefile ++++ linux-2.6.29.y/mm/Makefile +@@ -11,7 +11,7 @@ obj-y := bootmem.o filemap.o mempool.o + maccess.o page_alloc.o page-writeback.o pdflush.o \ + readahead.o swap.o truncate.o vmscan.o shmem.o \ + prio_tree.o util.o mmzone.o vmstat.o backing-dev.o \ +- page_isolation.o mm_init.o $(mmu-y) ++ page_isolation.o mm_init.o vma-sptree.o $(mmu-y) + + obj-$(CONFIG_PROC_PAGE_MONITOR) += pagewalk.o + obj-$(CONFIG_BOUNCE) += bounce.o +Index: linux-2.6.29.y/include/linux/mm.h +=================================================================== +--- linux-2.6.29.y.orig/include/linux/mm.h ++++ linux-2.6.29.y/include/linux/mm.h +@@ -1129,6 +1129,18 @@ extern void exit_mmap(struct mm_struct * + extern int mm_take_all_locks(struct mm_struct *mm); + extern void mm_drop_all_locks(struct mm_struct *mm); + ++/* vma-sptree.c */ ++void sp_vma_insert(struct mm_struct *mm, struct vm_area_struct *new, ++ struct vm_area_struct **prev, struct vm_area_struct **parent); ++struct vm_area_struct *sp_find_vma(struct mm_struct *mm, ++ unsigned long addr, ++ struct vm_area_struct **pprev); ++struct vm_area_struct *sp_ro_find_vma(struct mm_struct *mm, unsigned long addr); ++struct vm_area_struct * ++sp_find_vma_prev(struct mm_struct *mm, unsigned long addr, ++ struct vm_area_struct **pprev); ++void sp_vma_erase(struct mm_struct *mm, struct vm_area_struct *vma); ++ + #ifdef CONFIG_PROC_FS + /* From fs/proc/base.c. callers must _not_ hold the mm's exe_file_lock */ + extern void added_exe_file_vma(struct mm_struct *mm); diff --git a/uni-final-project/sptree/makefile-version.patch b/uni-final-project/sptree/makefile-version.patch new file mode 100644 index 0000000..85f816a --- /dev/null +++ b/uni-final-project/sptree/makefile-version.patch @@ -0,0 +1,17 @@ +--- + Makefile | 2 +- + 1 file changed, 1 insertion(+), 1 deletion(-) + +Index: linux-2.6.29.y/Makefile +=================================================================== +--- linux-2.6.29.y.orig/Makefile ++++ linux-2.6.29.y/Makefile +@@ -1,7 +1,7 @@ + VERSION = 2 + PATCHLEVEL = 6 + SUBLEVEL = 29 +-EXTRAVERSION = .2 ++EXTRAVERSION = .2-sptree1 + NAME = Temporary Tasmanian Devil + + # *DOCUMENTATION* diff --git a/uni-final-project/sptree/report-struct-sizes.patch b/uni-final-project/sptree/report-struct-sizes.patch new file mode 100644 index 0000000..071218e --- /dev/null +++ b/uni-final-project/sptree/report-struct-sizes.patch @@ -0,0 +1,33 @@ +--- + init/main.c | 11 +++++++++++ + 1 file changed, 11 insertions(+) + +Index: linux-2.6.29.y/init/main.c +=================================================================== +--- linux-2.6.29.y.orig/init/main.c ++++ linux-2.6.29.y/init/main.c +@@ -527,6 +527,15 @@ void __init __weak thread_info_cache_ini + { + } + ++static void __init report_struct_sizes(void) ++{ ++ printk("-> Splay Tree sizes:\n"); ++ printk("\tmm_struct: %d\n", sizeof(struct mm_struct)); ++ printk("\tvm_area_struct: %d\n", sizeof(struct vm_area_struct)); ++ printk("\tsp_node: %d\n", sizeof(struct sp_node)); ++ printk("\tsp_root: %d\n", sizeof(struct sp_root)); ++} ++ + asmlinkage void __init start_kernel(void) + { + char * command_line; +@@ -683,6 +692,8 @@ asmlinkage void __init start_kernel(void + + ftrace_init(); + ++ report_struct_sizes(); ++ + /* Do the rest non-__init'ed, we're now alive */ + rest_init(); + } diff --git a/uni-final-project/sptree/series b/uni-final-project/sptree/series new file mode 100644 index 0000000..2e52a1a --- /dev/null +++ b/uni-final-project/sptree/series @@ -0,0 +1,8 @@ +# Fully working VMA Splay Tree for 2.6.29.1 + +makefile-version.patch +introduce-vma-splay-tree.patch +report-struct-sizes.patch +use-vma-splay-tree.patch +check-vma-splay-tree.patch +change-find-vma-locks.patch diff --git a/uni-final-project/sptree/use-vma-splay-tree.patch b/uni-final-project/sptree/use-vma-splay-tree.patch new file mode 100644 index 0000000..f536779 --- /dev/null +++ b/uni-final-project/sptree/use-vma-splay-tree.patch @@ -0,0 +1,444 @@ +--- + include/linux/init_task.h | 1 + include/linux/mm.h | 2 + include/linux/mm_types.h | 3 + kernel/fork.c | 9 -- + mm/mmap.c | 167 +++++++--------------------------------------- + 5 files changed, 30 insertions(+), 152 deletions(-) + +Index: linux-2.6.29.y/mm/mmap.c +=================================================================== +--- linux-2.6.29.y.orig/mm/mmap.c ++++ linux-2.6.29.y/mm/mmap.c +@@ -27,6 +27,7 @@ + #include + #include + #include ++#include + + #include + #include +@@ -350,67 +351,27 @@ void validate_mm(struct mm_struct *mm) + #define validate_mm(mm) do { } while (0) + #endif + +-static struct vm_area_struct * ++static inline struct vm_area_struct * + find_vma_prepare(struct mm_struct *mm, unsigned long addr, +- struct vm_area_struct **pprev, struct rb_node ***rb_link, +- struct rb_node ** rb_parent) ++ struct vm_area_struct **pprev) + { +- struct vm_area_struct * vma; +- struct rb_node ** __rb_link, * __rb_parent, * rb_prev; +- +- __rb_link = &mm->mm_rb.rb_node; +- rb_prev = __rb_parent = NULL; +- vma = NULL; +- +- while (*__rb_link) { +- struct vm_area_struct *vma_tmp; +- +- __rb_parent = *__rb_link; +- vma_tmp = rb_entry(__rb_parent, struct vm_area_struct, vm_rb); +- +- if (vma_tmp->vm_end > addr) { +- vma = vma_tmp; +- if (vma_tmp->vm_start <= addr) +- break; +- __rb_link = &__rb_parent->rb_left; +- } else { +- rb_prev = __rb_parent; +- __rb_link = &__rb_parent->rb_right; +- } +- } +- + *pprev = NULL; +- if (rb_prev) +- *pprev = rb_entry(rb_prev, struct vm_area_struct, vm_rb); +- *rb_link = __rb_link; +- *rb_parent = __rb_parent; +- return vma; ++ return sp_find_vma(mm, addr, pprev); + } + + static inline void + __vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma, +- struct vm_area_struct *prev, struct rb_node *rb_parent) ++ struct vm_area_struct *prev, struct vm_area_struct *parent) + { + if (prev) { + vma->vm_next = prev->vm_next; + prev->vm_next = vma; + } else { + mm->mmap = vma; +- if (rb_parent) +- vma->vm_next = rb_entry(rb_parent, +- struct vm_area_struct, vm_rb); +- else +- vma->vm_next = NULL; ++ vma->vm_next = parent; + } + } + +-void __vma_link_rb(struct mm_struct *mm, struct vm_area_struct *vma, +- struct rb_node **rb_link, struct rb_node *rb_parent) +-{ +- rb_link_node(&vma->vm_rb, rb_parent, rb_link); +- rb_insert_color(&vma->vm_rb, &mm->mm_rb); +-} +- + static void __vma_link_file(struct vm_area_struct *vma) + { + struct file *file; +@@ -434,18 +395,16 @@ static void __vma_link_file(struct vm_ar + } + + static void +-__vma_link(struct mm_struct *mm, struct vm_area_struct *vma, +- struct vm_area_struct *prev, struct rb_node **rb_link, +- struct rb_node *rb_parent) ++__vma_link(struct mm_struct *mm, struct vm_area_struct *vma) + { +- __vma_link_list(mm, vma, prev, rb_parent); +- __vma_link_rb(mm, vma, rb_link, rb_parent); ++ struct vm_area_struct *sp_prev, *sp_parent; ++ ++ sp_vma_insert(mm, vma, &sp_prev, &sp_parent); ++ __vma_link_list(mm, vma, sp_prev, sp_parent); + __anon_vma_link(vma); + } + +-static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma, +- struct vm_area_struct *prev, struct rb_node **rb_link, +- struct rb_node *rb_parent) ++static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma) + { + struct address_space *mapping = NULL; + +@@ -458,7 +417,7 @@ static void vma_link(struct mm_struct *m + } + anon_vma_lock(vma); + +- __vma_link(mm, vma, prev, rb_link, rb_parent); ++ __vma_link(mm, vma); + __vma_link_file(vma); + + anon_vma_unlock(vma); +@@ -474,14 +433,10 @@ static void vma_link(struct mm_struct *m + * insert vm structure into list and rbtree and anon_vma, + * but it has already been inserted into prio_tree earlier. + */ +-static void __insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vma) ++static inline void ++__insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vma) + { +- struct vm_area_struct *__vma, *prev; +- struct rb_node **rb_link, *rb_parent; +- +- __vma = find_vma_prepare(mm, vma->vm_start,&prev, &rb_link, &rb_parent); +- BUG_ON(__vma && __vma->vm_start < vma->vm_end); +- __vma_link(mm, vma, prev, rb_link, rb_parent); ++ __vma_link(mm, vma); + mm->map_count++; + } + +@@ -490,9 +445,6 @@ __vma_unlink(struct mm_struct *mm, struc + struct vm_area_struct *prev) + { + prev->vm_next = vma->vm_next; +- rb_erase(&vma->vm_rb, &mm->mm_rb); +- if (mm->mmap_cache == vma) +- mm->mmap_cache = prev; + } + + /* +@@ -525,6 +477,7 @@ again: remove_next = 1 + (end > next-> + end = next->vm_end; + anon_vma = next->anon_vma; + importer = vma; ++ sp_vma_erase(mm, next); + } else if (end > next->vm_start) { + /* + * vma expands, overlapping part of the next: +@@ -1110,14 +1063,13 @@ unsigned long mmap_region(struct file *f + struct vm_area_struct *vma, *prev; + int correct_wcount = 0; + int error; +- struct rb_node **rb_link, *rb_parent; + unsigned long charged = 0; + struct inode *inode = file ? file->f_path.dentry->d_inode : NULL; + + /* Clear old maps */ + error = -ENOMEM; + munmap_back: +- vma = find_vma_prepare(mm, addr, &prev, &rb_link, &rb_parent); ++ vma = find_vma_prepare(mm, addr, &prev); + if (vma && vma->vm_start < addr + len) { + if (do_munmap(mm, addr, len)) + return -ENOMEM; +@@ -1212,7 +1164,7 @@ munmap_back: + if (vma_wants_writenotify(vma)) + vma->vm_page_prot = vm_get_page_prot(vm_flags & ~VM_SHARED); + +- vma_link(mm, vma, prev, rb_link, rb_parent); ++ vma_link(mm, vma); + file = vma->vm_file; + + /* Once vma denies write, undo our temporary denial count */ +@@ -1462,37 +1414,7 @@ EXPORT_SYMBOL(get_unmapped_area); + /* Look up the first VMA which satisfies addr < vm_end, NULL if none. */ + struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr) + { +- struct vm_area_struct *vma = NULL; +- +- if (mm) { +- /* Check the cache first. */ +- /* (Cache hit rate is typically around 35%.) */ +- vma = mm->mmap_cache; +- if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) { +- struct rb_node * rb_node; +- +- rb_node = mm->mm_rb.rb_node; +- vma = NULL; +- +- while (rb_node) { +- struct vm_area_struct * vma_tmp; +- +- vma_tmp = rb_entry(rb_node, +- struct vm_area_struct, vm_rb); +- +- if (vma_tmp->vm_end > addr) { +- vma = vma_tmp; +- if (vma_tmp->vm_start <= addr) +- break; +- rb_node = rb_node->rb_left; +- } else +- rb_node = rb_node->rb_right; +- } +- if (vma) +- mm->mmap_cache = vma; +- } +- } +- return vma; ++ return sp_find_vma(mm, addr, NULL); + } + + EXPORT_SYMBOL(find_vma); +@@ -1502,34 +1424,7 @@ struct vm_area_struct * + find_vma_prev(struct mm_struct *mm, unsigned long addr, + struct vm_area_struct **pprev) + { +- struct vm_area_struct *vma = NULL, *prev = NULL; +- struct rb_node *rb_node; +- if (!mm) +- goto out; +- +- /* Guard against addr being lower than the first VMA */ +- vma = mm->mmap; +- +- /* Go through the RB tree quickly. */ +- rb_node = mm->mm_rb.rb_node; +- +- while (rb_node) { +- struct vm_area_struct *vma_tmp; +- vma_tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb); +- +- if (addr < vma_tmp->vm_end) { +- rb_node = rb_node->rb_left; +- } else { +- prev = vma_tmp; +- if (!prev->vm_next || (addr < prev->vm_next->vm_end)) +- break; +- rb_node = rb_node->rb_right; +- } +- } +- +-out: +- *pprev = prev; +- return prev ? prev->vm_next : vma; ++ return sp_find_vma_prev(mm, addr, pprev); + } + + /* +@@ -1796,7 +1691,7 @@ detach_vmas_to_be_unmapped(struct mm_str + + insertion_point = (prev ? &prev->vm_next : &mm->mmap); + do { +- rb_erase(&vma->vm_rb, &mm->mm_rb); ++ sp_vma_erase(mm, vma); + mm->map_count--; + tail_vma = vma; + vma = vma->vm_next; +@@ -1808,7 +1703,6 @@ detach_vmas_to_be_unmapped(struct mm_str + else + addr = vma ? vma->vm_start : mm->mmap_base; + mm->unmap_area(mm, addr); +- mm->mmap_cache = NULL; /* Kill the cache. */ + } + + /* +@@ -1978,7 +1872,6 @@ unsigned long do_brk(unsigned long addr, + struct mm_struct * mm = current->mm; + struct vm_area_struct * vma, * prev; + unsigned long flags; +- struct rb_node ** rb_link, * rb_parent; + pgoff_t pgoff = addr >> PAGE_SHIFT; + int error; + +@@ -2025,7 +1918,7 @@ unsigned long do_brk(unsigned long addr, + * Clear old maps. this also does some error checking for us + */ + munmap_back: +- vma = find_vma_prepare(mm, addr, &prev, &rb_link, &rb_parent); ++ vma = find_vma_prepare(mm, addr, &prev); + if (vma && vma->vm_start < addr + len) { + if (do_munmap(mm, addr, len)) + return -ENOMEM; +@@ -2063,7 +1956,7 @@ unsigned long do_brk(unsigned long addr, + vma->vm_pgoff = pgoff; + vma->vm_flags = flags; + vma->vm_page_prot = vm_get_page_prot(flags); +- vma_link(mm, vma, prev, rb_link, rb_parent); ++ vma_link(mm, vma); + out: + mm->total_vm += len >> PAGE_SHIFT; + if (flags & VM_LOCKED) { +@@ -2127,8 +2020,7 @@ void exit_mmap(struct mm_struct *mm) + */ + int insert_vm_struct(struct mm_struct * mm, struct vm_area_struct * vma) + { +- struct vm_area_struct * __vma, * prev; +- struct rb_node ** rb_link, * rb_parent; ++ struct vm_area_struct * __vma; + + /* + * The vm_pgoff of a purely anonymous vma should be irrelevant +@@ -2146,13 +2038,13 @@ int insert_vm_struct(struct mm_struct * + BUG_ON(vma->anon_vma); + vma->vm_pgoff = vma->vm_start >> PAGE_SHIFT; + } +- __vma = find_vma_prepare(mm,vma->vm_start,&prev,&rb_link,&rb_parent); ++ __vma = find_vma(mm, vma->vm_start); + if (__vma && __vma->vm_start < vma->vm_end) + return -ENOMEM; + if ((vma->vm_flags & VM_ACCOUNT) && + security_vm_enough_memory_mm(mm, vma_pages(vma))) + return -ENOMEM; +- vma_link(mm, vma, prev, rb_link, rb_parent); ++ vma_link(mm, vma); + return 0; + } + +@@ -2167,7 +2059,6 @@ struct vm_area_struct *copy_vma(struct v + unsigned long vma_start = vma->vm_start; + struct mm_struct *mm = vma->vm_mm; + struct vm_area_struct *new_vma, *prev; +- struct rb_node **rb_link, *rb_parent; + struct mempolicy *pol; + + /* +@@ -2177,7 +2068,7 @@ struct vm_area_struct *copy_vma(struct v + if (!vma->vm_file && !vma->anon_vma) + pgoff = addr >> PAGE_SHIFT; + +- find_vma_prepare(mm, addr, &prev, &rb_link, &rb_parent); ++ find_vma_prepare(mm, addr, &prev); + new_vma = vma_merge(mm, prev, addr, addr + len, vma->vm_flags, + vma->anon_vma, vma->vm_file, pgoff, vma_policy(vma)); + if (new_vma) { +@@ -2207,7 +2098,7 @@ struct vm_area_struct *copy_vma(struct v + } + if (new_vma->vm_ops && new_vma->vm_ops->open) + new_vma->vm_ops->open(new_vma); +- vma_link(mm, new_vma, prev, rb_link, rb_parent); ++ vma_link(mm, new_vma); + } + } + return new_vma; +Index: linux-2.6.29.y/kernel/fork.c +=================================================================== +--- linux-2.6.29.y.orig/kernel/fork.c ++++ linux-2.6.29.y/kernel/fork.c +@@ -261,7 +261,6 @@ out: + static int dup_mmap(struct mm_struct *mm, struct mm_struct *oldmm) + { + struct vm_area_struct *mpnt, *tmp, **pprev; +- struct rb_node **rb_link, *rb_parent; + int retval; + unsigned long charge; + struct mempolicy *pol; +@@ -275,15 +274,11 @@ static int dup_mmap(struct mm_struct *mm + + mm->locked_vm = 0; + mm->mmap = NULL; +- mm->mmap_cache = NULL; + mm->free_area_cache = oldmm->mmap_base; + mm->cached_hole_size = ~0UL; + mm->map_count = 0; + cpus_clear(mm->cpu_vm_mask); +- mm->mm_rb = RB_ROOT; + mm->mm_sp = SP_ROOT; +- rb_link = &mm->mm_rb.rb_node; +- rb_parent = NULL; + pprev = &mm->mmap; + + for (mpnt = oldmm->mmap; mpnt; mpnt = mpnt->vm_next) { +@@ -349,9 +344,7 @@ static int dup_mmap(struct mm_struct *mm + *pprev = tmp; + pprev = &tmp->vm_next; + +- __vma_link_rb(mm, tmp, rb_link, rb_parent); +- rb_link = &tmp->vm_rb.rb_right; +- rb_parent = &tmp->vm_rb; ++ sp_vma_insert(mm, tmp, NULL, NULL); + + mm->map_count++; + retval = copy_page_range(mm, oldmm, mpnt); +Index: linux-2.6.29.y/include/linux/init_task.h +=================================================================== +--- linux-2.6.29.y.orig/include/linux/init_task.h ++++ linux-2.6.29.y/include/linux/init_task.h +@@ -29,7 +29,6 @@ extern struct fs_struct init_fs; + + #define INIT_MM(name) \ + { \ +- .mm_rb = RB_ROOT, \ + .mm_sp = SP_ROOT, \ + .pgd = swapper_pg_dir, \ + .mm_users = ATOMIC_INIT(2), \ +Index: linux-2.6.29.y/include/linux/mm_types.h +=================================================================== +--- linux-2.6.29.y.orig/include/linux/mm_types.h ++++ linux-2.6.29.y/include/linux/mm_types.h +@@ -132,7 +132,6 @@ struct vm_area_struct { + pgprot_t vm_page_prot; /* Access permissions of this VMA. */ + unsigned long vm_flags; /* Flags, see mm.h. */ + +- struct rb_node vm_rb; + struct sp_node vm_sp; + + /* +@@ -191,9 +190,7 @@ struct core_state { + + struct mm_struct { + struct vm_area_struct * mmap; /* list of VMAs */ +- struct rb_root mm_rb; + struct sp_root mm_sp; +- struct vm_area_struct * mmap_cache; /* last find_vma result */ + unsigned long (*get_unmapped_area) (struct file *filp, + unsigned long addr, unsigned long len, + unsigned long pgoff, unsigned long flags); +Index: linux-2.6.29.y/include/linux/mm.h +=================================================================== +--- linux-2.6.29.y.orig/include/linux/mm.h ++++ linux-2.6.29.y/include/linux/mm.h +@@ -1119,8 +1119,6 @@ extern struct anon_vma *find_mergeable_a + extern int split_vma(struct mm_struct *, + struct vm_area_struct *, unsigned long addr, int new_below); + extern int insert_vm_struct(struct mm_struct *, struct vm_area_struct *); +-extern void __vma_link_rb(struct mm_struct *, struct vm_area_struct *, +- struct rb_node **, struct rb_node *); + extern void unlink_file_vma(struct vm_area_struct *); + extern struct vm_area_struct *copy_vma(struct vm_area_struct **, + unsigned long addr, unsigned long len, pgoff_t pgoff); -- 2.11.4.GIT