lkml.org 
[lkml]   [2004]   [Jul]   [26]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
SubjectRe: [PATCH] prio_tree iterator cleanup.

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;
>
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 14:04    [W:0.047 / U:1.248 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site