prio_tree iterator cleanup.

Hello.

Currently we have:

	while ((vma = vma_prio_tree_next(vma, root, &iter,
                                        begin, end)) != NULL)
		do_something_with_vma;

Then iter,root,begin,end are all transfered unchanged to various functions. This patch hides them in struct iter instead.

It slightly lessens source, code size, and stack usage.

I hope it makes the code a bit more readable too.

Patch on top of "kill vma_prio_tree_init()", see
http://marc.theaimsgroup.com/?l=linux-kernel&m=109034156613288

Oleg.

Signed-off-by Oleg Nesterov <[email protected]>

diff -urp prio_init/fs/hugetlbfs/inode.c prio_iter/fs/hugetlbfs/inode.c

fs/hugetlbfs/inode.c +1 -2

@@ -272,8 +272,7 @@ hugetlb_vmtruncate_list(struct prio_tree
 	struct vm_area_struct *vma = NULL;
 	struct prio_tree_iter iter;
 
-	while ((vma = vma_prio_tree_next(vma, root, &iter,
-					h_pgoff, ULONG_MAX)) != NULL) {
+	vma_prio_tree_foreach(vma, &iter, root, h_pgoff, ULONG_MAX) {
 		unsigned long h_vm_pgoff;
 		unsigned long v_length;
 		unsigned long v_offset;

diff -urp prio_init/include/linux/mm.h prio_iter/include/linux/mm.h

include/linux/mm.h +6 -3

@@ -602,9 +602,12 @@ extern void si_meminfo_node(struct sysin
 void vma_prio_tree_add(struct vm_area_struct *, struct vm_area_struct *old);
 void vma_prio_tree_insert(struct vm_area_struct *, struct prio_tree_root *);
 void vma_prio_tree_remove(struct vm_area_struct *, struct prio_tree_root *);
-struct vm_area_struct *vma_prio_tree_next(
-	struct vm_area_struct *, struct prio_tree_root *,
-	struct prio_tree_iter *, pgoff_t begin, pgoff_t end);
+struct vm_area_struct *vma_prio_tree_next(struct vm_area_struct *vma,
+	struct prio_tree_iter *iter);
+
+#define vma_prio_tree_foreach(vma, iter, root, begin, end)	\
+	for (prio_tree_iter_init(iter, root, begin, end), vma = NULL;	\
+		(vma = vma_prio_tree_next(vma, iter)); )
 
 static inline void vma_nonlinear_insert(struct vm_area_struct *vma,
 					struct list_head *list)

diff -urp prio_init/include/linux/prio_tree.h prio_iter/include/linux/prio_tree.h

include/linux/prio_tree.h +12 -0

@@ -17,8 +17,20 @@ struct prio_tree_iter {
 	unsigned long		mask;
 	unsigned long		value;
 	int			size_level;
+
+	struct prio_tree_root	*root;
+	pgoff_t			r_index;
+	pgoff_t			h_index;
 };
 
+static inline void prio_tree_iter_init(struct prio_tree_iter *iter,
+		struct prio_tree_root *root, pgoff_t r_index, pgoff_t h_index)
+{
+	iter->root = root;
+	iter->r_index = r_index;
+	iter->h_index = h_index;
+}
+
 #define INIT_PRIO_TREE_ROOT(ptr)	\
 do {					\
 	(ptr)->prio_tree_node = NULL;	\

diff -urp prio_init/mm/memory.c prio_iter/mm/memory.c

mm/memory.c +2 -2

@@ -1127,8 +1127,8 @@ static inline void unmap_mapping_range_l
 	struct prio_tree_iter iter;
 	pgoff_t vba, vea, zba, zea;
 
-	while ((vma = vma_prio_tree_next(vma, root, &iter,
-			details->first_index, details->last_index)) != NULL) {
+	vma_prio_tree_foreach(vma, &iter, root,
+			details->first_index, details->last_index) {
 		vba = vma->vm_pgoff;
 		vea = vba + ((vma->vm_end - vma->vm_start) >> PAGE_SHIFT) - 1;
 		/* Assume for now that PAGE_CACHE_SHIFT == PAGE_SHIFT */

diff -urp prio_init/mm/prio_tree.c prio_iter/mm/prio_tree.c

mm/prio_tree.c +24 -36

@@ -312,9 +312,7 @@ static void prio_tree_remove(struct prio
  * 'm' is the number of prio_tree_nodes that overlap the interval X.
  */
 
-static struct prio_tree_node *prio_tree_left(
-		struct prio_tree_root *root, struct prio_tree_iter *iter,
-		unsigned long radix_index, unsigned long heap_index,
+static struct prio_tree_node *prio_tree_left(struct prio_tree_iter *iter,
 		unsigned long *r_index, unsigned long *h_index)
 {
 	if (prio_tree_left_empty(iter->cur))

@@ -322,7 +320,7 @@ static struct prio_tree_node *prio_tree_
 
 	GET_INDEX(iter->cur->left, *r_index, *h_index);
 
-	if (radix_index <= *h_index) {
+	if (iter->r_index <= *h_index) {
 		iter->cur = iter->cur->left;
 		iter->mask >>= 1;
 		if (iter->mask) {

@@ -336,7 +334,7 @@ static struct prio_tree_node *prio_tree_
 				iter->mask = ULONG_MAX;
 			} else {
 				iter->size_level = 1;
-				iter->mask = 1UL << (root->index_bits - 1);
+				iter->mask = 1UL << (iter->root->index_bits - 1);
 			}
 		}
 		return iter->cur;

@@ -345,9 +343,7 @@ static struct prio_tree_node *prio_tree_
 	return NULL;
 }
 
-static struct prio_tree_node *prio_tree_right(
-		struct prio_tree_root *root, struct prio_tree_iter *iter,
-		unsigned long radix_index, unsigned long heap_index,
+static struct prio_tree_node *prio_tree_right(struct prio_tree_iter *iter,
 		unsigned long *r_index, unsigned long *h_index)
 {
 	unsigned long value;

@@ -360,12 +356,12 @@ static struct prio_tree_node *prio_tree_
 	else
 		value = iter->value | iter->mask;
 
-	if (heap_index < value)
+	if (iter->h_index < value)
 		return NULL;
 
 	GET_INDEX(iter->cur->right, *r_index, *h_index);
 
-	if (radix_index <= *h_index) {
+	if (iter->r_index <= *h_index) {
 		iter->cur = iter->cur->right;
 		iter->mask >>= 1;
 		iter->value = value;

@@ -380,7 +376,7 @@ static struct prio_tree_node *prio_tree_
 				iter->mask = ULONG_MAX;
 			} else {
 				iter->size_level = 1;
-				iter->mask = 1UL << (root->index_bits - 1);
+				iter->mask = 1UL << (iter->root->index_bits - 1);
 			}
 		}
 		return iter->cur;

@@ -405,10 +401,10 @@ static struct prio_tree_node *prio_tree_
 	return iter->cur;
 }
 
-static inline int overlap(unsigned long radix_index, unsigned long heap_index,
+static inline int overlap(struct prio_tree_iter *iter,
 		unsigned long r_index, unsigned long h_index)
 {
-	return heap_index >= r_index && radix_index <= h_index;
+	return iter->h_index >= r_index && iter->r_index <= h_index;
 }
 
 /*

@@ -418,35 +414,33 @@ static inline int overlap(unsigned long
  * heap_index]. Note that always radix_index <= heap_index. We do a pre-order
  * traversal of the tree.
  */
-static struct prio_tree_node *prio_tree_first(struct prio_tree_root *root,
-		struct prio_tree_iter *iter, unsigned long radix_index,
-		unsigned long heap_index)
+static struct prio_tree_node *prio_tree_first(struct prio_tree_iter *iter)
 {
+	struct prio_tree_root *root;
 	unsigned long r_index, h_index;
 
 	INIT_PRIO_TREE_ITER(iter);
 
+	root = iter->root;
 	if (prio_tree_empty(root))
 		return NULL;
 
 	GET_INDEX(root->prio_tree_node, r_index, h_index);
 
-	if (radix_index > h_index)
+	if (iter->r_index > h_index)
 		return NULL;
 
 	iter->mask = 1UL << (root->index_bits - 1);
 	iter->cur = root->prio_tree_node;
 
 	while (1) {
-		if (overlap(radix_index, heap_index, r_index, h_index))
+		if (overlap(iter, r_index, h_index))
 			return iter->cur;
 
-		if (prio_tree_left(root, iter, radix_index, heap_index,
-					&r_index, &h_index))
+		if (prio_tree_left(iter, &r_index, &h_index))
 			continue;
 
-		if (prio_tree_right(root, iter, radix_index, heap_index,
-					&r_index, &h_index))
+		if (prio_tree_right(iter, &r_index, &h_index))
 			continue;
 
 		break;

@@ -459,21 +453,16 @@ static struct prio_tree_node *prio_tree_
  *
  * Get the next prio_tree_node that overlaps with the input interval in iter
  */
-static struct prio_tree_node *prio_tree_next(struct prio_tree_root *root,
-		struct prio_tree_iter *iter, unsigned long radix_index,
-		unsigned long heap_index)
+static struct prio_tree_node *prio_tree_next(struct prio_tree_iter *iter)
 {
 	unsigned long r_index, h_index;
 
 repeat:
-	while (prio_tree_left(root, iter, radix_index,
-				heap_index, &r_index, &h_index)) {
-		if (overlap(radix_index, heap_index, r_index, h_index))
+	while (prio_tree_left(iter, &r_index, &h_index))
+		if (overlap(iter, r_index, h_index))
 			return iter->cur;
-	}
 
-	while (!prio_tree_right(root, iter, radix_index,
-				heap_index, &r_index, &h_index)) {
+	while (!prio_tree_right(iter, &r_index, &h_index)) {
 	    	while (!prio_tree_root(iter->cur) &&
 				iter->cur->parent->right == iter->cur)
 			prio_tree_parent(iter);

@@ -484,7 +473,7 @@ repeat:
 		prio_tree_parent(iter);
 	}
 
-	if (overlap(radix_index, heap_index, r_index, h_index))
+	if (overlap(iter, r_index, h_index))
 		return iter->cur;
 
 	goto repeat;

@@ -606,19 +595,18 @@ void vma_prio_tree_remove(struct vm_area
  * page in the given range of contiguous file pages.
  */
 struct vm_area_struct *vma_prio_tree_next(struct vm_area_struct *vma,
-		struct prio_tree_root *root, struct prio_tree_iter *iter,
-		pgoff_t begin, pgoff_t end)
+					struct prio_tree_iter *iter)
 {
 	struct prio_tree_node *ptr;
 	struct vm_area_struct *next;
 
 	if (!vma) {
-		ptr = prio_tree_first(root, iter, begin, end);
+		ptr = prio_tree_first(iter);
 		goto check;
 	}
 
 	if (!vma->shared.vm_set.list.prev) {
-		ptr = prio_tree_next(root, iter, begin, end);
+		ptr = prio_tree_next(iter);
 		goto check;
 	}
 

diff -urp prio_init/mm/rmap.c prio_iter/mm/rmap.c

mm/rmap.c +2 -4

@@ -284,8 +284,7 @@ static inline int page_referenced_file(s
 	if (!spin_trylock(&mapping->i_mmap_lock))
 		return 0;
 
-	while ((vma = vma_prio_tree_next(vma, &mapping->i_mmap,
-					&iter, pgoff, pgoff)) != NULL) {
+	vma_prio_tree_foreach(vma, &iter, &mapping->i_mmap, pgoff, pgoff) {
 		if ((vma->vm_flags & (VM_LOCKED|VM_MAYSHARE))
 				  == (VM_LOCKED|VM_MAYSHARE)) {
 			referenced++;

@@ -665,8 +664,7 @@ static inline int try_to_unmap_file(stru
 	if (!spin_trylock(&mapping->i_mmap_lock))
 		return ret;
 
-	while ((vma = vma_prio_tree_next(vma, &mapping->i_mmap,
-					&iter, pgoff, pgoff)) != NULL) {
+	vma_prio_tree_foreach(vma, &iter, &mapping->i_mmap, pgoff, pgoff) {
 		ret = try_to_unmap_one(page, vma);
 		if (ret == SWAP_FAIL || !page->mapcount)
 			goto out;

I have gone through all the 3 prio_tree patches you have sent
over the last few weeks. Your 2nd (kill vma_prio_tree_init) and 3rd (iterator cleanup) patches look straight-forward.

I agree that vm_set.head linking is ugly. Your 1st patch attempts to simplify it and removes few lines of code. However, your 1st patch is intrusive and I am not convinced that it improves the code very much.

If you can post your 2nd and 3rd patches independent of your first patch, that will be great. Please covert vma_prio_tree_next in arch/* directories if you plan to post a new version of your 3rd patch.

Overall I am inclined to leave the prio_tree code as it is. However, your 2nd and 3rd patches are quiet straight-forward and I am okay with them.