[PATCH] prio_tree iterator cleanup.

[PATCH] prio_tree iterator cleanup.

[Oleg Nesterov]

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 <oleg@tv-sign.ru>

diff -urp prio_init/fs/hugetlbfs/inode.c prio_iter/fs/hugetlbfs/inode.c
--- prio_init/fs/hugetlbfs/inode.c	2004-07-13 17:52:41.000000000 +0400
+++ prio_iter/fs/hugetlbfs/inode.c	2004-07-24 16:13:40.000000000 +0400
@@ -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
--- prio_init/include/linux/mm.h	2004-07-20 17:47:23.000000000 +0400
+++ prio_iter/include/linux/mm.h	2004-07-24 17:13:11.000000000 +0400
@@ -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
--- prio_init/include/linux/prio_tree.h	2004-07-19 17:16:26.000000000 +0400
+++ prio_iter/include/linux/prio_tree.h	2004-07-24 16:30:07.000000000 +0400
@@ -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
--- prio_init/mm/memory.c	2004-07-13 17:52:49.000000000 +0400
+++ prio_iter/mm/memory.c	2004-07-24 16:08:29.000000000 +0400
@@ -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
--- prio_init/mm/prio_tree.c	2004-07-20 17:25:15.000000000 +0400
+++ prio_iter/mm/prio_tree.c	2004-07-24 16:31:34.000000000 +0400
@@ -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
--- prio_init/mm/rmap.c	2004-07-13 17:52:49.000000000 +0400
+++ prio_iter/mm/rmap.c	2004-07-24 16:20:58.000000000 +0400
@@ -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;

Re: [PATCH] prio_tree iterator cleanup.

[Rajesh Venkatasubramanian]

Hello Oleg,

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.

Thanking you,
Rajesh

On Sat, 24 Jul 2004, Oleg Nesterov wrote:

> 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 <oleg@tv-sign.ru>
>
> diff -urp prio_init/fs/hugetlbfs/inode.c prio_iter/fs/hugetlbfs/inode.c
> --- prio_init/fs/hugetlbfs/inode.c	2004-07-13 17:52:41.000000000 +0400
> +++ prio_iter/fs/hugetlbfs/inode.c	2004-07-24 16:13:40.000000000 +0400
> @@ -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
> --- prio_init/include/linux/mm.h	2004-07-20 17:47:23.000000000 +0400
> +++ prio_iter/include/linux/mm.h	2004-07-24 17:13:11.000000000 +0400
> @@ -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
> --- prio_init/include/linux/prio_tree.h	2004-07-19 17:16:26.000000000 +0400
> +++ prio_iter/include/linux/prio_tree.h	2004-07-24 16:30:07.000000000 +0400
> @@ -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
> --- prio_init/mm/memory.c	2004-07-13 17:52:49.000000000 +0400
> +++ prio_iter/mm/memory.c	2004-07-24 16:08:29.000000000 +0400
> @@ -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
> --- prio_init/mm/prio_tree.c	2004-07-20 17:25:15.000000000 +0400
> +++ prio_iter/mm/prio_tree.c	2004-07-24 16:31:34.000000000 +0400
> @@ -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
> --- prio_init/mm/rmap.c	2004-07-13 17:52:49.000000000 +0400
> +++ prio_iter/mm/rmap.c	2004-07-24 16:20:58.000000000 +0400
> @@ -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;
>

Re: [PATCH] prio_tree iterator cleanup.

[Andrew Morton]

Rajesh Venkatasubramanian <vrajesh@umich.edu> wrote:
>
> 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.

Thanks, Rajesh.

Oleg, I didn't apply any patches in this area.  Please reissue any
prio-tree patches from scratch.  Thanks.

Re: [PATCH] prio_tree iterator cleanup.

[Oleg Nesterov]

Hello Rajesh,

Rajesh Venkatasubramanian wrote:
>
> If you can post your 2nd and 3rd patches independent of your
> first patch, that will be great.

Ok, i'll do it at weekend.

> Please covert vma_prio_tree_next in arch/* directories if you
> plan to post a new version of your 3rd patch.

Oh, sorry. I promise, i will read man grep 3 times.

> However, your 1st patch is intrusive and I am not convinced
> that it improves the code very much.
> Overall I am inclined to leave the prio_tree code as it is.

Yes, i understand, it changes working code without real gain.
However, i will send it as 3rd patch, in the case you will
change you mind.

Thank you,
Oleg.