From: Oleg Nesterov <oleg@tv-sign.ru>
To: linux-kernel@vger.kernel.org
Cc: Rajesh Venkatasubramanian <vrajesh@umich.edu>
Subject: [PATCH] prio_tree 2/3: iterator cleanup
Date: Wed, 28 Jul 2004 20:14:04 +0400 [thread overview]
Message-ID: <4107D0CC.DAD982A6@tv-sign.ru> (raw)
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.
Oleg.
Signed-off-by: Oleg Nesterov <oleg@tv-sign.ru>
diff -urp prio_init/arch/arm/mm/fault-armv.c prio_iter/arch/arm/mm/fault-armv.c
--- prio_init/arch/arm/mm/fault-armv.c 2004-06-08 13:44:08.000000000 +0400
+++ prio_iter/arch/arm/mm/fault-armv.c 2004-07-27 21:00:09.000000000 +0400
@@ -80,7 +80,7 @@ static void __flush_dcache_page(struct p
{
struct address_space *mapping = page_mapping(page);
struct mm_struct *mm = current->active_mm;
- struct vm_area_struct *mpnt = NULL;
+ struct vm_area_struct *mpnt;
struct prio_tree_iter iter;
unsigned long offset;
pgoff_t pgoff;
@@ -97,8 +97,7 @@ static void __flush_dcache_page(struct p
pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
flush_dcache_mmap_lock(mapping);
- while ((mpnt = vma_prio_tree_next(mpnt, &mapping->i_mmap,
- &iter, pgoff, pgoff)) != NULL) {
+ vma_prio_tree_foreach(mpnt, &iter, &mapping->i_mmap, pgoff, pgoff) {
/*
* If this VMA is not in our MM, we can ignore it.
*/
@@ -128,7 +127,7 @@ make_coherent(struct vm_area_struct *vma
{
struct address_space *mapping = page_mapping(page);
struct mm_struct *mm = vma->vm_mm;
- struct vm_area_struct *mpnt = NULL;
+ struct vm_area_struct *mpnt;
struct prio_tree_iter iter;
unsigned long offset;
pgoff_t pgoff;
@@ -145,8 +144,7 @@ make_coherent(struct vm_area_struct *vma
* cache coherency.
*/
flush_dcache_mmap_lock(mapping);
- while ((mpnt = vma_prio_tree_next(mpnt, &mapping->i_mmap,
- &iter, pgoff, pgoff)) != NULL) {
+ vma_prio_tree_foreach(mpnt, &iter, &mapping->i_mmap, pgoff, pgoff) {
/*
* If this VMA is not in our MM, we can ignore it.
* Note that we intentionally mask out the VMA
diff -urp prio_init/arch/parisc/kernel/cache.c prio_iter/arch/parisc/kernel/cache.c
--- prio_init/arch/parisc/kernel/cache.c 2004-05-24 14:16:00.000000000 +0400
+++ prio_iter/arch/parisc/kernel/cache.c 2004-07-27 21:03:38.000000000 +0400
@@ -231,7 +231,7 @@ void disable_sr_hashing(void)
void __flush_dcache_page(struct page *page)
{
struct address_space *mapping = page_mapping(page);
- struct vm_area_struct *mpnt = NULL;
+ struct vm_area_struct *mpnt;
struct prio_tree_iter iter;
unsigned long offset;
unsigned long addr;
@@ -250,8 +250,7 @@ void __flush_dcache_page(struct page *pa
* to flush one address here for them all to become coherent */
flush_dcache_mmap_lock(mapping);
- while ((mpnt = vma_prio_tree_next(mpnt, &mapping->i_mmap,
- &iter, pgoff, pgoff)) != NULL) {
+ vma_prio_tree_foreach(mpnt, &iter, &mapping->i_mmap, pgoff, pgoff) {
offset = (pgoff - mpnt->vm_pgoff) << PAGE_SHIFT;
addr = mpnt->vm_start + offset;
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-27 20:46:03.000000000 +0400
@@ -269,11 +269,10 @@ static void hugetlbfs_drop_inode(struct
static inline void
hugetlb_vmtruncate_list(struct prio_tree_root *root, unsigned long h_pgoff)
{
- struct vm_area_struct *vma = NULL;
+ struct vm_area_struct *vma;
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-28 14:07:07.000000000 +0400
+++ prio_iter/include/linux/mm.h 2004-07-28 14:07:48.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-05-24 14:16:15.000000000 +0400
+++ prio_iter/include/linux/prio_tree.h 2004-07-27 20:29:59.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-27 20:47:10.000000000 +0400
@@ -1123,12 +1123,12 @@ no_new_page:
static inline void unmap_mapping_range_list(struct prio_tree_root *root,
struct zap_details *details)
{
- struct vm_area_struct *vma = NULL;
+ struct vm_area_struct *vma;
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-27 19:16:21.000000000 +0400
+++ prio_iter/mm/prio_tree.c 2004-07-27 20:29:59.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;
@@ -622,8 +611,7 @@ 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;
@@ -632,7 +620,7 @@ struct vm_area_struct *vma_prio_tree_nex
/*
* First call is with NULL vma
*/
- ptr = prio_tree_first(root, iter, begin, end);
+ ptr = prio_tree_first(iter);
if (ptr) {
next = prio_tree_entry(ptr, struct vm_area_struct,
shared.prio_tree_node);
@@ -657,7 +645,7 @@ struct vm_area_struct *vma_prio_tree_nex
}
}
- ptr = prio_tree_next(root, iter, begin, end);
+ ptr = prio_tree_next(iter);
if (ptr) {
next = prio_tree_entry(ptr, struct vm_area_struct,
shared.prio_tree_node);
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-27 20:49:01.000000000 +0400
@@ -277,15 +277,14 @@ static inline int page_referenced_file(s
unsigned int mapcount = page->mapcount;
struct address_space *mapping = page->mapping;
pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
- struct vm_area_struct *vma = NULL;
+ struct vm_area_struct *vma;
struct prio_tree_iter iter;
int referenced = 0;
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++;
@@ -654,7 +653,7 @@ static inline int try_to_unmap_file(stru
{
struct address_space *mapping = page->mapping;
pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
- struct vm_area_struct *vma = NULL;
+ struct vm_area_struct *vma;
struct prio_tree_iter iter;
int ret = SWAP_AGAIN;
unsigned long cursor;
@@ -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;
reply other threads:[~2004-07-28 16:14 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4107D0CC.DAD982A6@tv-sign.ru \
--to=oleg@tv-sign.ru \
--cc=linux-kernel@vger.kernel.org \
--cc=vrajesh@umich.edu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®