Re: [PATCH 1/7] mm: interval tree updates
Hello Michel
Lets first see snippet in another work.
https://lkml.org/lkml/2012/9/4/75
[PATCH 5/7] mm rmap: remove vma_address check for address inside vma
On Tue, Sep 4, 2012 at 5:20 PM, Michel Lespinasse wrote:
> diff --git a/mm/rmap.c b/mm/rmap.c
> index 9c61bf387fd1..28777412de62 100644
> --- a/mm/rmap.c
> +++ b/mm/rmap.c
> @@ -510,22 +510,26 @@ void page_unlock_anon_vma(struct anon_vma *anon_vma)
>
> /*
> * At what user virtual address is page expected in @vma?
> - * Returns virtual address or -EFAULT if page's index/offset is not
> - * within the range mapped the @vma.
> */
> -inline unsigned long
> -vma_address(struct page *page, struct vm_area_struct *vma)
> +static inline unsigned long
> +__vma_address(struct page *page, struct vm_area_struct *vma)
> {
> pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
> - unsigned long address;
>
> if (unlikely(is_vm_hugetlb_page(vma)))
> pgoff = page->index << huge_page_order(page_hstate(page));
The pgoff computation for huge page remains as it was.
> - address = vma->vm_start + ((pgoff - vma->vm_pgoff) << PAGE_SHIFT);
> - if (unlikely(address < vma->vm_start || address >= vma->vm_end)) {
> - /* page should be within @vma mapping range */
> - return -EFAULT;
> - }
> +
> + return vma->vm_start + ((pgoff - vma->vm_pgoff) << PAGE_SHIFT);
> +}
> +
> +inline unsigned long
> +vma_address(struct page *page, struct vm_area_struct *vma)
> +{
> + unsigned long address = __vma_address(page, vma);
> +
> + /* page should be within @vma mapping range */
> + VM_BUG_ON(address < vma->vm_start || address >= vma->vm_end);
> +
> return address;
> }
>
Then lets see this work.
On Sat, Sep 8, 2012 at 7:26 AM, Michel Lespinasse wrote:
> -8<-
> From: Michel Lespinasse
> Subject: mm: replace vma prio_tree with an interval tree
>
> Implement an interval tree as a replacement for the VMA prio_tree.
> The algorithms are similar to lib/interval_tree.c; however that code
> can't be directly reused as the interval endpoints are not explicitly
> stored in the VMA. So instead, the common algorithm is moved into
> a template and the details (node type, how to get interval endpoints
> from the node, etc) are filled in using the C preprocessor.
>
> Once the interval tree functions are available, using them as a replacement
> to the VMA prio tree is a relatively simple, mechanical job.
>
> Signed-off-by: Michel Lespinasse
> Cc: Rik van Riel
> Cc: Hillf Danton
> Cc: Peter Zijlstra
> Cc: Catalin Marinas
> Cc: Andrea Arcangeli
> Cc: David Woodhouse
> Signed-off-by: Andrew Morton
> ---
[...]
> --- /dev/null
> +++ b/mm/interval_tree.c
> @@ -0,0 +1,59 @@
> +/*
> + * mm/interval_tree.c - interval tree for mapping->i_mmap
> + *
> + * Copyright (C) 2012, Michel Lespinasse
> + *
> + * This file is released under the GPL v2.
> + */
> +
> +#include
> +#include
> +#include
> +
> +static inline unsigned long vma_start_pgoff(struct vm_area_struct *v)
> +{
> + return v->vm_pgoff;
> +}
> +
> +static inline unsigned long vma_last_pgoff(struct vm_area_struct *v)
> +{
> + return v->vm_pgoff + ((v->vm_end - v->vm_start) >> PAGE_SHIFT) - 1;
> +}
> +
The pgoff computations are only for regular page, yes?
> +INTERVAL_TREE_DEFINE(struct vm_area_struct, shared.linear.rb,
> +unsigned long, shared.linear.rb_subtree_last,
> +vma_start_pgoff, vma_last_pgoff,, vma_interval_tree)
> +
[...]
> @@ -1547,7 +1545,6 @@ static int try_to_unmap_file(struct page *page, enum
> ttu_flags flags)
> struct address_space *mapping = page->mapping;
> pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
What if page is huge?
> struct vm_area_struct *vma;
> - struct prio_tree_iter iter;
> int ret = SWAP_AGAIN;
> unsigned long cursor;
> unsigned long max_nl_cursor = 0;
> @@ -1555,7 +1552,7 @@ static int try_to_unmap_file(struct page *page, enum
> ttu_flags flags)
> unsigned int mapcount;
>
> mutex_lock(>i_mmap_mutex);
> - vma_prio_tree_foreach(vma, , >i_mmap, pgoff, pgoff) {
> + vma_interval_tree_foreach(vma, >i_mmap, pgoff, pgoff) {
> unsigned long address = vma_address(page, vma);
> if (address == -EFAULT)
> continue;
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/7] mm: interval tree updates
On Fri, Sep 07, 2012 at 03:55:14PM -0700, Andrew Morton wrote:
> On Fri, 7 Sep 2012 15:29:36 -0700
> Michel Lespinasse wrote:
>
> > > Ho hum. I don't think I can be bothered untangling all this.
> >
> > I don't think you should have to do it yourself either.
>
> Patch wrangling is what I do ;)
>
> > But, if you're willing to take it, I can send you replacement patches for
> > (mm-replace-vma-prio_tree-with-an-interval-tree.patch +
> > mm-interval-tree-updates.patch) collapsed into one, and
> > rbtree-move-augmented-rbtree-functionality-to-rbtree_augmentedh.patch
> > fixed so that it'd apply after the collapsed patch (and get to the
> > same end state).
>
> Yes please, I suppose we should do this.
Here is the replacement for
+ rbtree-move-augmented-rbtree-functionality-to-rbtree_augmentedh.patch
(I also copied the signed-offs and ccs from the original change)
-8<-
From: Michel Lespinasse
Subject: rbtree: move augmented rbtree functionality to rbtree_augmented.h
Provide rb_insert_augmented() and rb_erase_augmented through
a new rbtree_augmented.h include file. rb_erase_augmented() is defined
there as an __always_inline function, in order to allow inlining of
augmented rbtree callbacks into it. Since this generates a relatively
large function, each augmented rbtree users should make sure to
have a single call site.
Signed-off-by: Michel Lespinasse
Cc: Rik van Riel
Cc: Hillf Danton
Cc: Peter Zijlstra
Cc: Catalin Marinas
Cc: Andrea Arcangeli
Cc: David Woodhouse
Signed-off-by: Andrew Morton
---
Documentation/rbtree.txt | 13 ++
arch/x86/mm/pat_rbtree.c |2 +-
include/linux/interval_tree_generic.h |2 +
include/linux/rbtree.h| 48 ---
include/linux/rbtree_augmented.h | 223 +
lib/rbtree.c | 162 ++--
lib/rbtree_test.c |2 +-
7 files changed, 251 insertions(+), 201 deletions(-)
create mode 100644 include/linux/rbtree_augmented.h
diff --git a/Documentation/rbtree.txt b/Documentation/rbtree.txt
index 0a0b6dce3e08..61b6c48871a0 100644
--- a/Documentation/rbtree.txt
+++ b/Documentation/rbtree.txt
@@ -202,6 +202,14 @@ An rbtree user who wants this feature will have to call
the augmentation
functions with the user provided augmentation callback when inserting
and erasing nodes.
+C files implementing augmented rbtree manipulation must include
+ instead of . Note that
+linux/rbtree_augmented.h exposes some rbtree implementations details
+you are not expected to rely on; please stick to the documented APIs
+there and do not include from header files
+either so as to minimize chances of your users accidentally relying on
+such implementation details.
+
On insertion, the user must update the augmented information on the path
leading to the inserted node, then call rb_link_node() as usual and
rb_augment_inserted() instead of the usual rb_insert_color() call.
@@ -227,6 +235,11 @@ In both cases, the callbacks are provided through struct
rb_augment_callbacks.
subtree to a newly assigned subtree root AND recomputes the augmented
information for the former subtree root.
+The compiled code for rb_erase_augmented() may inline the propagation and
+copy callbacks, which results in a large function, so each augmented rbtree
+user should have a single rb_erase_augmented() call site in order to limit
+compiled code size.
+
Sample usage:
diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c
index 4d116959075d..415f6c4ced36 100644
--- a/arch/x86/mm/pat_rbtree.c
+++ b/arch/x86/mm/pat_rbtree.c
@@ -12,7 +12,7 @@
#include
#include
#include
-#include
+#include
#include
#include
diff --git a/include/linux/interval_tree_generic.h
b/include/linux/interval_tree_generic.h
index 46232114dde0..58370e1862ad 100644
--- a/include/linux/interval_tree_generic.h
+++ b/include/linux/interval_tree_generic.h
@@ -19,6 +19,8 @@
include/linux/interval_tree_generic.h
*/
+#include
+
/*
* Template for implementing interval trees
*
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 8d1e83b1c87b..0022c1bb1e26 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -62,54 +62,6 @@ extern void rb_insert_color(struct rb_node *, struct rb_root
*);
extern void rb_erase(struct rb_node *, struct rb_root *);
-struct rb_augment_callbacks {
- void (*propagate)(struct rb_node *node, struct rb_node *stop);
- void (*copy)(struct rb_node *old, struct rb_node *new);
- void (*rotate)(struct rb_node *old, struct rb_node *new);
-};
-
-extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
- void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
-extern void rb_erase_augmented(struct rb_node *node, struct rb_root *root,
- const struct rb_augment_callbacks
Re: [PATCH 1/7] mm: interval tree updates
On Fri, Sep 07, 2012 at 03:55:14PM -0700, Andrew Morton wrote:
> On Fri, 7 Sep 2012 15:29:36 -0700
> Michel Lespinasse wrote:
>
> > > Ho hum. I don't think I can be bothered untangling all this.
> >
> > I don't think you should have to do it yourself either.
>
> Patch wrangling is what I do ;)
>
> > But, if you're willing to take it, I can send you replacement patches for
> > (mm-replace-vma-prio_tree-with-an-interval-tree.patch +
> > mm-interval-tree-updates.patch) collapsed into one, and
> > rbtree-move-augmented-rbtree-functionality-to-rbtree_augmentedh.patch
> > fixed so that it'd apply after the collapsed patch (and get to the
> > same end state).
>
> Yes please, I suppose we should do this.
All right, here is the replacement for
+ mm-replace-vma-prio_tree-with-an-interval-tree.patch
and
+ mm-interval-tree-updates.patch
all collapsed into one:
(I also copied the signed-offs and ccs from the original change)
-8<-
From: Michel Lespinasse
Subject: mm: replace vma prio_tree with an interval tree
Implement an interval tree as a replacement for the VMA prio_tree.
The algorithms are similar to lib/interval_tree.c; however that code
can't be directly reused as the interval endpoints are not explicitly
stored in the VMA. So instead, the common algorithm is moved into
a template and the details (node type, how to get interval endpoints
from the node, etc) are filled in using the C preprocessor.
Once the interval tree functions are available, using them as a replacement
to the VMA prio tree is a relatively simple, mechanical job.
Signed-off-by: Michel Lespinasse
Cc: Rik van Riel
Cc: Hillf Danton
Cc: Peter Zijlstra
Cc: Catalin Marinas
Cc: Andrea Arcangeli
Cc: David Woodhouse
Signed-off-by: Andrew Morton
---
arch/arm/mm/fault-armv.c |3 +-
arch/arm/mm/flush.c |3 +-
arch/parisc/kernel/cache.c|3 +-
arch/x86/mm/hugetlbpage.c |3 +-
fs/hugetlbfs/inode.c |9 +-
fs/inode.c|2 +-
include/linux/fs.h|6 +-
include/linux/interval_tree_generic.h | 189 ++
include/linux/mm.h| 30 +++--
include/linux/mm_types.h | 14 +--
kernel/events/uprobes.c |3 +-
kernel/fork.c |7 +-
lib/interval_tree.c | 161 +
lib/prio_tree.c | 19 +---
mm/Makefile |4 +-
mm/filemap_xip.c |3 +-
mm/fremap.c |2 +-
mm/hugetlb.c |3 +-
mm/interval_tree.c| 59 +
mm/memory-failure.c |3 +-
mm/memory.c |9 +-
mm/mmap.c | 22 ++--
mm/nommu.c| 12 +-
mm/prio_tree.c| 208 -
mm/rmap.c | 18 +--
25 files changed, 330 insertions(+), 465 deletions(-)
create mode 100644 include/linux/interval_tree_generic.h
create mode 100644 mm/interval_tree.c
delete mode 100644 mm/prio_tree.c
diff --git a/arch/arm/mm/fault-armv.c b/arch/arm/mm/fault-armv.c
index 7599e2625c7d..2a5907b5c8d2 100644
--- a/arch/arm/mm/fault-armv.c
+++ b/arch/arm/mm/fault-armv.c
@@ -134,7 +134,6 @@ make_coherent(struct address_space *mapping, struct
vm_area_struct *vma,
{
struct mm_struct *mm = vma->vm_mm;
struct vm_area_struct *mpnt;
- struct prio_tree_iter iter;
unsigned long offset;
pgoff_t pgoff;
int aliases = 0;
@@ -147,7 +146,7 @@ make_coherent(struct address_space *mapping, struct
vm_area_struct *vma,
* cache coherency.
*/
flush_dcache_mmap_lock(mapping);
- vma_prio_tree_foreach(mpnt, , >i_mmap, pgoff, pgoff) {
+ vma_interval_tree_foreach(mpnt, >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 --git a/arch/arm/mm/flush.c b/arch/arm/mm/flush.c
index 77458548e031..ad174f68b200 100644
--- a/arch/arm/mm/flush.c
+++ b/arch/arm/mm/flush.c
@@ -196,7 +196,6 @@ static void __flush_dcache_aliases(struct address_space
*mapping, struct page *p
{
struct mm_struct *mm = current->active_mm;
struct vm_area_struct *mpnt;
- struct prio_tree_iter iter;
pgoff_t pgoff;
/*
@@ -208,7 +207,7 @@ static void __flush_dcache_aliases(struct address_space
*mapping, struct page *p
pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
flush_dcache_mmap_lock(mapping);
- vma_prio_tree_foreach(mpnt, , >i_mmap, pgoff, pgoff) {
+ vma_interval_tree_foreach(mpnt, >i_mmap, pgoff, pgoff) {
Re: [PATCH 1/7] mm: interval tree updates
On Fri, 7 Sep 2012 15:29:36 -0700 Michel Lespinasse wrote: > > Ho hum. I don't think I can be bothered untangling all this. > > I don't think you should have to do it yourself either. Patch wrangling is what I do ;) > But, if you're willing to take it, I can send you replacement patches for > (mm-replace-vma-prio_tree-with-an-interval-tree.patch + > mm-interval-tree-updates.patch) collapsed into one, and > rbtree-move-augmented-rbtree-functionality-to-rbtree_augmentedh.patch > fixed so that it'd apply after the collapsed patch (and get to the > same end state). Yes please, I suppose we should do this. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/7] mm: interval tree updates
On Fri, Sep 7, 2012 at 3:13 PM, Andrew Morton wrote: > On Tue, 4 Sep 2012 02:20:51 -0700 > Michel Lespinasse wrote: > >> This commit updates the generic interval tree code that was >> introduced in "mm: replace vma prio_tree with an interval tree". >> >> Changes: >> >> - fixed 'endpoing' typo noticed by Andrew Morton >> >> - replaced include/linux/interval_tree_tmpl.h, which was used as a >> template (including it automatically defined the interval tree >> functions) with include/linux/interval_tree_generic.h, which only >> defines a preprocessor macro INTERVAL_TREE_DEFINE(), which itself >> defines the interval tree functions when invoked. Now that is a very >> long macro which is unfortunate, but it does make the usage sites >> (lib/interval_tree.c and mm/interval_tree.c) a bit nicer than previously. >> >> - make use of RB_DECLARE_CALLBACKS() in the INTERVAL_TREE_DEFINE() macro, >> instead of duplicating that code in the interval tree template. >> >> - replaced vma_interval_tree_add(), which was actually handling the >> nonlinear and interval tree cases, with vma_interval_tree_insert_after() >> which handles only the interval tree case and has an API that is more >> consistent with the other interval tree handling functions. >> The nonlinear case is now handled explicitly in kernel/fork.c dup_mmap(). >> >> Signed-off-by: Michel Lespinasse >> --- >> include/linux/interval_tree_generic.h | 191 >> include/linux/interval_tree_tmpl.h| 219 >> - > > Well that's a mess. We create interval_tree_generic.h then four > commits later it vanishes, never to return. And I can't fold > mm-interval-tree-updates.patch into > mm-replace-vma-prio_tree-with-an-interval-tree.patch because > rbtree-move-augmented-rbtree-functionality-to-rbtree_augmentedh.patch > mucks with interval_tree_generic.h within those four commits. > > Ho hum. I don't think I can be bothered untangling all this. I don't think you should have to do it yourself either. But, if you're willing to take it, I can send you replacement patches for (mm-replace-vma-prio_tree-with-an-interval-tree.patch + mm-interval-tree-updates.patch) collapsed into one, and rbtree-move-augmented-rbtree-functionality-to-rbtree_augmentedh.patch fixed so that it'd apply after the collapsed patch (and get to the same end state). -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/7] mm: interval tree updates
On Tue, 4 Sep 2012 02:20:51 -0700 Michel Lespinasse wrote: > This commit updates the generic interval tree code that was > introduced in "mm: replace vma prio_tree with an interval tree". > > Changes: > > - fixed 'endpoing' typo noticed by Andrew Morton > > - replaced include/linux/interval_tree_tmpl.h, which was used as a > template (including it automatically defined the interval tree > functions) with include/linux/interval_tree_generic.h, which only > defines a preprocessor macro INTERVAL_TREE_DEFINE(), which itself > defines the interval tree functions when invoked. Now that is a very > long macro which is unfortunate, but it does make the usage sites > (lib/interval_tree.c and mm/interval_tree.c) a bit nicer than previously. > > - make use of RB_DECLARE_CALLBACKS() in the INTERVAL_TREE_DEFINE() macro, > instead of duplicating that code in the interval tree template. > > - replaced vma_interval_tree_add(), which was actually handling the > nonlinear and interval tree cases, with vma_interval_tree_insert_after() > which handles only the interval tree case and has an API that is more > consistent with the other interval tree handling functions. > The nonlinear case is now handled explicitly in kernel/fork.c dup_mmap(). > > Signed-off-by: Michel Lespinasse > --- > include/linux/interval_tree_generic.h | 191 > include/linux/interval_tree_tmpl.h| 219 > - Well that's a mess. We create interval_tree_generic.h then four commits later it vanishes, never to return. And I can't fold mm-interval-tree-updates.patch into mm-replace-vma-prio_tree-with-an-interval-tree.patch because rbtree-move-augmented-rbtree-functionality-to-rbtree_augmentedh.patch mucks with interval_tree_generic.h within those four commits. Ho hum. I don't think I can be bothered untangling all this. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/7] mm: interval tree updates
On Tue, 4 Sep 2012 02:20:51 -0700 Michel Lespinasse wal...@google.com wrote: This commit updates the generic interval tree code that was introduced in mm: replace vma prio_tree with an interval tree. Changes: - fixed 'endpoing' typo noticed by Andrew Morton - replaced include/linux/interval_tree_tmpl.h, which was used as a template (including it automatically defined the interval tree functions) with include/linux/interval_tree_generic.h, which only defines a preprocessor macro INTERVAL_TREE_DEFINE(), which itself defines the interval tree functions when invoked. Now that is a very long macro which is unfortunate, but it does make the usage sites (lib/interval_tree.c and mm/interval_tree.c) a bit nicer than previously. - make use of RB_DECLARE_CALLBACKS() in the INTERVAL_TREE_DEFINE() macro, instead of duplicating that code in the interval tree template. - replaced vma_interval_tree_add(), which was actually handling the nonlinear and interval tree cases, with vma_interval_tree_insert_after() which handles only the interval tree case and has an API that is more consistent with the other interval tree handling functions. The nonlinear case is now handled explicitly in kernel/fork.c dup_mmap(). Signed-off-by: Michel Lespinasse wal...@google.com --- include/linux/interval_tree_generic.h | 191 include/linux/interval_tree_tmpl.h| 219 - Well that's a mess. We create interval_tree_generic.h then four commits later it vanishes, never to return. And I can't fold mm-interval-tree-updates.patch into mm-replace-vma-prio_tree-with-an-interval-tree.patch because rbtree-move-augmented-rbtree-functionality-to-rbtree_augmentedh.patch mucks with interval_tree_generic.h within those four commits. Ho hum. I don't think I can be bothered untangling all this. -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/7] mm: interval tree updates
On Fri, Sep 7, 2012 at 3:13 PM, Andrew Morton a...@linux-foundation.org wrote: On Tue, 4 Sep 2012 02:20:51 -0700 Michel Lespinasse wal...@google.com wrote: This commit updates the generic interval tree code that was introduced in mm: replace vma prio_tree with an interval tree. Changes: - fixed 'endpoing' typo noticed by Andrew Morton - replaced include/linux/interval_tree_tmpl.h, which was used as a template (including it automatically defined the interval tree functions) with include/linux/interval_tree_generic.h, which only defines a preprocessor macro INTERVAL_TREE_DEFINE(), which itself defines the interval tree functions when invoked. Now that is a very long macro which is unfortunate, but it does make the usage sites (lib/interval_tree.c and mm/interval_tree.c) a bit nicer than previously. - make use of RB_DECLARE_CALLBACKS() in the INTERVAL_TREE_DEFINE() macro, instead of duplicating that code in the interval tree template. - replaced vma_interval_tree_add(), which was actually handling the nonlinear and interval tree cases, with vma_interval_tree_insert_after() which handles only the interval tree case and has an API that is more consistent with the other interval tree handling functions. The nonlinear case is now handled explicitly in kernel/fork.c dup_mmap(). Signed-off-by: Michel Lespinasse wal...@google.com --- include/linux/interval_tree_generic.h | 191 include/linux/interval_tree_tmpl.h| 219 - Well that's a mess. We create interval_tree_generic.h then four commits later it vanishes, never to return. And I can't fold mm-interval-tree-updates.patch into mm-replace-vma-prio_tree-with-an-interval-tree.patch because rbtree-move-augmented-rbtree-functionality-to-rbtree_augmentedh.patch mucks with interval_tree_generic.h within those four commits. Ho hum. I don't think I can be bothered untangling all this. I don't think you should have to do it yourself either. But, if you're willing to take it, I can send you replacement patches for (mm-replace-vma-prio_tree-with-an-interval-tree.patch + mm-interval-tree-updates.patch) collapsed into one, and rbtree-move-augmented-rbtree-functionality-to-rbtree_augmentedh.patch fixed so that it'd apply after the collapsed patch (and get to the same end state). -- Michel Walken Lespinasse A program is never fully debugged until the last user dies. -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/7] mm: interval tree updates
On Fri, 7 Sep 2012 15:29:36 -0700 Michel Lespinasse wal...@google.com wrote: Ho hum. I don't think I can be bothered untangling all this. I don't think you should have to do it yourself either. Patch wrangling is what I do ;) But, if you're willing to take it, I can send you replacement patches for (mm-replace-vma-prio_tree-with-an-interval-tree.patch + mm-interval-tree-updates.patch) collapsed into one, and rbtree-move-augmented-rbtree-functionality-to-rbtree_augmentedh.patch fixed so that it'd apply after the collapsed patch (and get to the same end state). Yes please, I suppose we should do this. -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/7] mm: interval tree updates
On Fri, Sep 07, 2012 at 03:55:14PM -0700, Andrew Morton wrote:
On Fri, 7 Sep 2012 15:29:36 -0700
Michel Lespinasse wal...@google.com wrote:
Ho hum. I don't think I can be bothered untangling all this.
I don't think you should have to do it yourself either.
Patch wrangling is what I do ;)
But, if you're willing to take it, I can send you replacement patches for
(mm-replace-vma-prio_tree-with-an-interval-tree.patch +
mm-interval-tree-updates.patch) collapsed into one, and
rbtree-move-augmented-rbtree-functionality-to-rbtree_augmentedh.patch
fixed so that it'd apply after the collapsed patch (and get to the
same end state).
Yes please, I suppose we should do this.
All right, here is the replacement for
+ mm-replace-vma-prio_tree-with-an-interval-tree.patch
and
+ mm-interval-tree-updates.patch
all collapsed into one:
(I also copied the signed-offs and ccs from the original change)
-8-
From: Michel Lespinasse wal...@google.com
Subject: mm: replace vma prio_tree with an interval tree
Implement an interval tree as a replacement for the VMA prio_tree.
The algorithms are similar to lib/interval_tree.c; however that code
can't be directly reused as the interval endpoints are not explicitly
stored in the VMA. So instead, the common algorithm is moved into
a template and the details (node type, how to get interval endpoints
from the node, etc) are filled in using the C preprocessor.
Once the interval tree functions are available, using them as a replacement
to the VMA prio tree is a relatively simple, mechanical job.
Signed-off-by: Michel Lespinasse wal...@google.com
Cc: Rik van Riel r...@redhat.com
Cc: Hillf Danton dhi...@gmail.com
Cc: Peter Zijlstra a.p.zijls...@chello.nl
Cc: Catalin Marinas catalin.mari...@arm.com
Cc: Andrea Arcangeli aarca...@redhat.com
Cc: David Woodhouse dw...@infradead.org
Signed-off-by: Andrew Morton a...@linux-foundation.org
---
arch/arm/mm/fault-armv.c |3 +-
arch/arm/mm/flush.c |3 +-
arch/parisc/kernel/cache.c|3 +-
arch/x86/mm/hugetlbpage.c |3 +-
fs/hugetlbfs/inode.c |9 +-
fs/inode.c|2 +-
include/linux/fs.h|6 +-
include/linux/interval_tree_generic.h | 189 ++
include/linux/mm.h| 30 +++--
include/linux/mm_types.h | 14 +--
kernel/events/uprobes.c |3 +-
kernel/fork.c |7 +-
lib/interval_tree.c | 161 +
lib/prio_tree.c | 19 +---
mm/Makefile |4 +-
mm/filemap_xip.c |3 +-
mm/fremap.c |2 +-
mm/hugetlb.c |3 +-
mm/interval_tree.c| 59 +
mm/memory-failure.c |3 +-
mm/memory.c |9 +-
mm/mmap.c | 22 ++--
mm/nommu.c| 12 +-
mm/prio_tree.c| 208 -
mm/rmap.c | 18 +--
25 files changed, 330 insertions(+), 465 deletions(-)
create mode 100644 include/linux/interval_tree_generic.h
create mode 100644 mm/interval_tree.c
delete mode 100644 mm/prio_tree.c
diff --git a/arch/arm/mm/fault-armv.c b/arch/arm/mm/fault-armv.c
index 7599e2625c7d..2a5907b5c8d2 100644
--- a/arch/arm/mm/fault-armv.c
+++ b/arch/arm/mm/fault-armv.c
@@ -134,7 +134,6 @@ make_coherent(struct address_space *mapping, struct
vm_area_struct *vma,
{
struct mm_struct *mm = vma-vm_mm;
struct vm_area_struct *mpnt;
- struct prio_tree_iter iter;
unsigned long offset;
pgoff_t pgoff;
int aliases = 0;
@@ -147,7 +146,7 @@ make_coherent(struct address_space *mapping, struct
vm_area_struct *vma,
* cache coherency.
*/
flush_dcache_mmap_lock(mapping);
- vma_prio_tree_foreach(mpnt, iter, mapping-i_mmap, pgoff, pgoff) {
+ vma_interval_tree_foreach(mpnt, 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 --git a/arch/arm/mm/flush.c b/arch/arm/mm/flush.c
index 77458548e031..ad174f68b200 100644
--- a/arch/arm/mm/flush.c
+++ b/arch/arm/mm/flush.c
@@ -196,7 +196,6 @@ static void __flush_dcache_aliases(struct address_space
*mapping, struct page *p
{
struct mm_struct *mm = current-active_mm;
struct vm_area_struct *mpnt;
- struct prio_tree_iter iter;
pgoff_t pgoff;
/*
@@ -208,7 +207,7 @@ static void __flush_dcache_aliases(struct address_space
*mapping, struct page *p
pgoff = page-index (PAGE_CACHE_SHIFT - PAGE_SHIFT);
Re: [PATCH 1/7] mm: interval tree updates
On Fri, Sep 07, 2012 at 03:55:14PM -0700, Andrew Morton wrote:
On Fri, 7 Sep 2012 15:29:36 -0700
Michel Lespinasse wal...@google.com wrote:
Ho hum. I don't think I can be bothered untangling all this.
I don't think you should have to do it yourself either.
Patch wrangling is what I do ;)
But, if you're willing to take it, I can send you replacement patches for
(mm-replace-vma-prio_tree-with-an-interval-tree.patch +
mm-interval-tree-updates.patch) collapsed into one, and
rbtree-move-augmented-rbtree-functionality-to-rbtree_augmentedh.patch
fixed so that it'd apply after the collapsed patch (and get to the
same end state).
Yes please, I suppose we should do this.
Here is the replacement for
+ rbtree-move-augmented-rbtree-functionality-to-rbtree_augmentedh.patch
(I also copied the signed-offs and ccs from the original change)
-8-
From: Michel Lespinasse wal...@google.com
Subject: rbtree: move augmented rbtree functionality to rbtree_augmented.h
Provide rb_insert_augmented() and rb_erase_augmented through
a new rbtree_augmented.h include file. rb_erase_augmented() is defined
there as an __always_inline function, in order to allow inlining of
augmented rbtree callbacks into it. Since this generates a relatively
large function, each augmented rbtree users should make sure to
have a single call site.
Signed-off-by: Michel Lespinasse wal...@google.com
Cc: Rik van Riel r...@redhat.com
Cc: Hillf Danton dhi...@gmail.com
Cc: Peter Zijlstra a.p.zijls...@chello.nl
Cc: Catalin Marinas catalin.mari...@arm.com
Cc: Andrea Arcangeli aarca...@redhat.com
Cc: David Woodhouse dw...@infradead.org
Signed-off-by: Andrew Morton a...@linux-foundation.org
---
Documentation/rbtree.txt | 13 ++
arch/x86/mm/pat_rbtree.c |2 +-
include/linux/interval_tree_generic.h |2 +
include/linux/rbtree.h| 48 ---
include/linux/rbtree_augmented.h | 223 +
lib/rbtree.c | 162 ++--
lib/rbtree_test.c |2 +-
7 files changed, 251 insertions(+), 201 deletions(-)
create mode 100644 include/linux/rbtree_augmented.h
diff --git a/Documentation/rbtree.txt b/Documentation/rbtree.txt
index 0a0b6dce3e08..61b6c48871a0 100644
--- a/Documentation/rbtree.txt
+++ b/Documentation/rbtree.txt
@@ -202,6 +202,14 @@ An rbtree user who wants this feature will have to call
the augmentation
functions with the user provided augmentation callback when inserting
and erasing nodes.
+C files implementing augmented rbtree manipulation must include
+linux/rbtree_augmented.h instead of linus/rbtree.h. Note that
+linux/rbtree_augmented.h exposes some rbtree implementations details
+you are not expected to rely on; please stick to the documented APIs
+there and do not include linux/rbtree_augmented.h from header files
+either so as to minimize chances of your users accidentally relying on
+such implementation details.
+
On insertion, the user must update the augmented information on the path
leading to the inserted node, then call rb_link_node() as usual and
rb_augment_inserted() instead of the usual rb_insert_color() call.
@@ -227,6 +235,11 @@ In both cases, the callbacks are provided through struct
rb_augment_callbacks.
subtree to a newly assigned subtree root AND recomputes the augmented
information for the former subtree root.
+The compiled code for rb_erase_augmented() may inline the propagation and
+copy callbacks, which results in a large function, so each augmented rbtree
+user should have a single rb_erase_augmented() call site in order to limit
+compiled code size.
+
Sample usage:
diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c
index 4d116959075d..415f6c4ced36 100644
--- a/arch/x86/mm/pat_rbtree.c
+++ b/arch/x86/mm/pat_rbtree.c
@@ -12,7 +12,7 @@
#include linux/debugfs.h
#include linux/kernel.h
#include linux/module.h
-#include linux/rbtree.h
+#include linux/rbtree_augmented.h
#include linux/sched.h
#include linux/gfp.h
diff --git a/include/linux/interval_tree_generic.h
b/include/linux/interval_tree_generic.h
index 46232114dde0..58370e1862ad 100644
--- a/include/linux/interval_tree_generic.h
+++ b/include/linux/interval_tree_generic.h
@@ -19,6 +19,8 @@
include/linux/interval_tree_generic.h
*/
+#include linux/rbtree_augmented.h
+
/*
* Template for implementing interval trees
*
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 8d1e83b1c87b..0022c1bb1e26 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -62,54 +62,6 @@ extern void rb_insert_color(struct rb_node *, struct rb_root
*);
extern void rb_erase(struct rb_node *, struct rb_root *);
-struct rb_augment_callbacks {
- void (*propagate)(struct rb_node *node, struct rb_node *stop);
- void (*copy)(struct rb_node *old, struct rb_node *new);
- void
Re: [PATCH 1/7] mm: interval tree updates
Hello Michel
Lets first see snippet in another work.
https://lkml.org/lkml/2012/9/4/75
[PATCH 5/7] mm rmap: remove vma_address check for address inside vma
On Tue, Sep 4, 2012 at 5:20 PM, Michel Lespinasse wal...@google.com wrote:
diff --git a/mm/rmap.c b/mm/rmap.c
index 9c61bf387fd1..28777412de62 100644
--- a/mm/rmap.c
+++ b/mm/rmap.c
@@ -510,22 +510,26 @@ void page_unlock_anon_vma(struct anon_vma *anon_vma)
/*
* At what user virtual address is page expected in @vma?
- * Returns virtual address or -EFAULT if page's index/offset is not
- * within the range mapped the @vma.
*/
-inline unsigned long
-vma_address(struct page *page, struct vm_area_struct *vma)
+static inline unsigned long
+__vma_address(struct page *page, struct vm_area_struct *vma)
{
pgoff_t pgoff = page-index (PAGE_CACHE_SHIFT - PAGE_SHIFT);
- unsigned long address;
if (unlikely(is_vm_hugetlb_page(vma)))
pgoff = page-index huge_page_order(page_hstate(page));
The pgoff computation for huge page remains as it was.
- address = vma-vm_start + ((pgoff - vma-vm_pgoff) PAGE_SHIFT);
- if (unlikely(address vma-vm_start || address = vma-vm_end)) {
- /* page should be within @vma mapping range */
- return -EFAULT;
- }
+
+ return vma-vm_start + ((pgoff - vma-vm_pgoff) PAGE_SHIFT);
+}
+
+inline unsigned long
+vma_address(struct page *page, struct vm_area_struct *vma)
+{
+ unsigned long address = __vma_address(page, vma);
+
+ /* page should be within @vma mapping range */
+ VM_BUG_ON(address vma-vm_start || address = vma-vm_end);
+
return address;
}
Then lets see this work.
On Sat, Sep 8, 2012 at 7:26 AM, Michel Lespinasse wal...@google.com wrote:
-8-
From: Michel Lespinasse wal...@google.com
Subject: mm: replace vma prio_tree with an interval tree
Implement an interval tree as a replacement for the VMA prio_tree.
The algorithms are similar to lib/interval_tree.c; however that code
can't be directly reused as the interval endpoints are not explicitly
stored in the VMA. So instead, the common algorithm is moved into
a template and the details (node type, how to get interval endpoints
from the node, etc) are filled in using the C preprocessor.
Once the interval tree functions are available, using them as a replacement
to the VMA prio tree is a relatively simple, mechanical job.
Signed-off-by: Michel Lespinasse wal...@google.com
Cc: Rik van Riel r...@redhat.com
Cc: Hillf Danton dhi...@gmail.com
Cc: Peter Zijlstra a.p.zijls...@chello.nl
Cc: Catalin Marinas catalin.mari...@arm.com
Cc: Andrea Arcangeli aarca...@redhat.com
Cc: David Woodhouse dw...@infradead.org
Signed-off-by: Andrew Morton a...@linux-foundation.org
---
[...]
--- /dev/null
+++ b/mm/interval_tree.c
@@ -0,0 +1,59 @@
+/*
+ * mm/interval_tree.c - interval tree for mapping-i_mmap
+ *
+ * Copyright (C) 2012, Michel Lespinasse wal...@google.com
+ *
+ * This file is released under the GPL v2.
+ */
+
+#include linux/mm.h
+#include linux/fs.h
+#include linux/interval_tree_generic.h
+
+static inline unsigned long vma_start_pgoff(struct vm_area_struct *v)
+{
+ return v-vm_pgoff;
+}
+
+static inline unsigned long vma_last_pgoff(struct vm_area_struct *v)
+{
+ return v-vm_pgoff + ((v-vm_end - v-vm_start) PAGE_SHIFT) - 1;
+}
+
The pgoff computations are only for regular page, yes?
+INTERVAL_TREE_DEFINE(struct vm_area_struct, shared.linear.rb,
+unsigned long, shared.linear.rb_subtree_last,
+vma_start_pgoff, vma_last_pgoff,, vma_interval_tree)
+
[...]
@@ -1547,7 +1545,6 @@ static int try_to_unmap_file(struct page *page, enum
ttu_flags flags)
struct address_space *mapping = page-mapping;
pgoff_t pgoff = page-index (PAGE_CACHE_SHIFT - PAGE_SHIFT);
What if page is huge?
struct vm_area_struct *vma;
- struct prio_tree_iter iter;
int ret = SWAP_AGAIN;
unsigned long cursor;
unsigned long max_nl_cursor = 0;
@@ -1555,7 +1552,7 @@ static int try_to_unmap_file(struct page *page, enum
ttu_flags flags)
unsigned int mapcount;
mutex_lock(mapping-i_mmap_mutex);
- vma_prio_tree_foreach(vma, iter, mapping-i_mmap, pgoff, pgoff) {
+ vma_interval_tree_foreach(vma, mapping-i_mmap, pgoff, pgoff) {
unsigned long address = vma_address(page, vma);
if (address == -EFAULT)
continue;
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[PATCH 1/7] mm: interval tree updates
This commit updates the generic interval tree code that was
introduced in "mm: replace vma prio_tree with an interval tree".
Changes:
- fixed 'endpoing' typo noticed by Andrew Morton
- replaced include/linux/interval_tree_tmpl.h, which was used as a
template (including it automatically defined the interval tree
functions) with include/linux/interval_tree_generic.h, which only
defines a preprocessor macro INTERVAL_TREE_DEFINE(), which itself
defines the interval tree functions when invoked. Now that is a very
long macro which is unfortunate, but it does make the usage sites
(lib/interval_tree.c and mm/interval_tree.c) a bit nicer than previously.
- make use of RB_DECLARE_CALLBACKS() in the INTERVAL_TREE_DEFINE() macro,
instead of duplicating that code in the interval tree template.
- replaced vma_interval_tree_add(), which was actually handling the
nonlinear and interval tree cases, with vma_interval_tree_insert_after()
which handles only the interval tree case and has an API that is more
consistent with the other interval tree handling functions.
The nonlinear case is now handled explicitly in kernel/fork.c dup_mmap().
Signed-off-by: Michel Lespinasse
---
include/linux/interval_tree_generic.h | 191
include/linux/interval_tree_tmpl.h| 219 -
include/linux/mm.h|6 +-
kernel/fork.c |7 +-
lib/interval_tree.c | 15 +--
mm/interval_tree.c| 60 +-
6 files changed, 235 insertions(+), 263 deletions(-)
create mode 100644 include/linux/interval_tree_generic.h
delete mode 100644 include/linux/interval_tree_tmpl.h
diff --git a/include/linux/interval_tree_generic.h
b/include/linux/interval_tree_generic.h
new file mode 100644
index ..58370e1862ad
--- /dev/null
+++ b/include/linux/interval_tree_generic.h
@@ -0,0 +1,191 @@
+/*
+ Interval Trees
+ (C) 2012 Michel Lespinasse
+
+ 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 program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ include/linux/interval_tree_generic.h
+*/
+
+#include
+
+/*
+ * Template for implementing interval trees
+ *
+ * ITSTRUCT: struct type of the interval tree nodes
+ * ITRB: name of struct rb_node field within ITSTRUCT
+ * ITTYPE: type of the interval endpoints
+ * ITSUBTREE: name of ITTYPE field within ITSTRUCT holding last-in-subtree
+ * ITSTART(n): start endpoint of ITSTRUCT node n
+ * ITLAST(n): last endpoint of ITSTRUCT node n
+ * ITSTATIC: 'static' or empty
+ * ITPREFIX: prefix to use for the inline tree definitions
+ *
+ * Note - before using this, please consider if non-generic version
+ * (interval_tree.h) would work for you...
+ */
+
+#define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE,
\
+ITSTART, ITLAST, ITSTATIC, ITPREFIX) \
+ \
+/* Callbacks for augmented rbtree insert and remove */ \
+ \
+static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node) \
+{\
+ ITTYPE max = ITLAST(node), subtree_last; \
+ if (node->ITRB.rb_left) { \
+ subtree_last = rb_entry(node->ITRB.rb_left, \
+ ITSTRUCT, ITRB)->ITSUBTREE; \
+ if (max < subtree_last) \
+ max = subtree_last; \
+ } \
+ if (node->ITRB.rb_right) {\
+ subtree_last = rb_entry(node->ITRB.rb_right, \
+ ITSTRUCT, ITRB)->ITSUBTREE; \
+ if (max < subtree_last) \
+ max = subtree_last; \
+ }
[PATCH 1/7] mm: interval tree updates
This commit updates the generic interval tree code that was
introduced in mm: replace vma prio_tree with an interval tree.
Changes:
- fixed 'endpoing' typo noticed by Andrew Morton
- replaced include/linux/interval_tree_tmpl.h, which was used as a
template (including it automatically defined the interval tree
functions) with include/linux/interval_tree_generic.h, which only
defines a preprocessor macro INTERVAL_TREE_DEFINE(), which itself
defines the interval tree functions when invoked. Now that is a very
long macro which is unfortunate, but it does make the usage sites
(lib/interval_tree.c and mm/interval_tree.c) a bit nicer than previously.
- make use of RB_DECLARE_CALLBACKS() in the INTERVAL_TREE_DEFINE() macro,
instead of duplicating that code in the interval tree template.
- replaced vma_interval_tree_add(), which was actually handling the
nonlinear and interval tree cases, with vma_interval_tree_insert_after()
which handles only the interval tree case and has an API that is more
consistent with the other interval tree handling functions.
The nonlinear case is now handled explicitly in kernel/fork.c dup_mmap().
Signed-off-by: Michel Lespinasse wal...@google.com
---
include/linux/interval_tree_generic.h | 191
include/linux/interval_tree_tmpl.h| 219 -
include/linux/mm.h|6 +-
kernel/fork.c |7 +-
lib/interval_tree.c | 15 +--
mm/interval_tree.c| 60 +-
6 files changed, 235 insertions(+), 263 deletions(-)
create mode 100644 include/linux/interval_tree_generic.h
delete mode 100644 include/linux/interval_tree_tmpl.h
diff --git a/include/linux/interval_tree_generic.h
b/include/linux/interval_tree_generic.h
new file mode 100644
index ..58370e1862ad
--- /dev/null
+++ b/include/linux/interval_tree_generic.h
@@ -0,0 +1,191 @@
+/*
+ Interval Trees
+ (C) 2012 Michel Lespinasse wal...@google.com
+
+ 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 program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ include/linux/interval_tree_generic.h
+*/
+
+#include linux/rbtree_augmented.h
+
+/*
+ * Template for implementing interval trees
+ *
+ * ITSTRUCT: struct type of the interval tree nodes
+ * ITRB: name of struct rb_node field within ITSTRUCT
+ * ITTYPE: type of the interval endpoints
+ * ITSUBTREE: name of ITTYPE field within ITSTRUCT holding last-in-subtree
+ * ITSTART(n): start endpoint of ITSTRUCT node n
+ * ITLAST(n): last endpoint of ITSTRUCT node n
+ * ITSTATIC: 'static' or empty
+ * ITPREFIX: prefix to use for the inline tree definitions
+ *
+ * Note - before using this, please consider if non-generic version
+ * (interval_tree.h) would work for you...
+ */
+
+#define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE,
\
+ITSTART, ITLAST, ITSTATIC, ITPREFIX) \
+ \
+/* Callbacks for augmented rbtree insert and remove */ \
+ \
+static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node) \
+{\
+ ITTYPE max = ITLAST(node), subtree_last; \
+ if (node-ITRB.rb_left) { \
+ subtree_last = rb_entry(node-ITRB.rb_left, \
+ ITSTRUCT, ITRB)-ITSUBTREE; \
+ if (max subtree_last) \
+ max = subtree_last; \
+ } \
+ if (node-ITRB.rb_right) {\
+ subtree_last = rb_entry(node-ITRB.rb_right, \
+ ITSTRUCT, ITRB)-ITSUBTREE; \
+ if (max subtree_last) \
+ max = subtree_last; \
+ }
