* [PATCH 0/5] rbtree based interval tree as a prio_tree replacement
@ 2012-08-07 7:25 Michel Lespinasse
2012-08-07 7:25 ` [PATCH 1/5] rbtree: add prio tree and interval tree tests Michel Lespinasse
` (6 more replies)
0 siblings, 7 replies; 18+ messages in thread
From: Michel Lespinasse @ 2012-08-07 7:25 UTC (permalink / raw)
To: riel, peterz, vrajesh, daniel.santos, aarcange, dwmw2, akpm
Cc: linux-mm, linux-kernel, torvalds
This patchset goes over the rbtree changes that have been already integrated
into Andrew's -mm tree, as well as the augmented rbtree proposal which is
currently pending.
Patch 1 implements support for interval trees, on top of the augmented
rbtree API. It also adds synthetic tests to compare the performance of
interval trees vs prio trees. Short answers is that interval trees are
slightly faster (~25%) on insert/erase, and much faster (~2.4 - 3x)
on search. It is debatable how realistic the synthetic test is, and I have
not made such measurements yet, but my impression is that interval trees
would still come out faster.
Patch 2 uses a preprocessor template to make the interval tree generic,
and uses it as a replacement for the vma prio_tree.
Patch 3 takes the other prio_tree user, kmemleak, and converts it to use
a basic rbtree. We don't actually need the augmented rbtree support here
because the intervals are always non-overlapping.
Patch 4 removes the now-unused prio tree library.
Patch 5 proposes an additional optimization to rb_erase_augmented, now
providing it as an inline function so that the augmented callbacks can be
inlined in. This provides an additional 5-10% performance improvement
for the interval tree insert/erase benchmark. There is a maintainance cost
as it exposes augmented rbtree users to some of the rbtree library internals;
however I think this cost shouldn't be too high as I expect the augmented
rbtree will always have much less users than the base rbtree.
I should probably add a quick summary of why I think it makes sense to
replace prio trees with augmented rbtree based interval trees now.
One of the drivers is that we need augmented rbtrees for Rik's vma
gap finding code, and once you have them, it just makes sense to use them
for interval trees as well, as this is the simpler and more well known
algorithm. prio trees, in comparison, seem *too* clever: they impose an
additional 'heap' constraint on the tree, which they use to guarantee
a faster worst-case complexity of O(k+log N) for stabbing queries in a
well-balanced prio tree, vs O(k*log N) for interval trees (where k=number
of matches, N=number of intervals). Now this sounds great, but in practice
prio trees don't realize this theorical benefit. First, the additional
constraint makes them harder to update, so that the kernel implementation
has to simplify things by balancing them like a radix tree, which is not
always ideal. Second, the fact that there are both index and heap
properties makes both tree manipulation and search more complex,
which results in a higher multiplicative time constant. As it turns out,
the simple interval tree algorithm ends up running faster than the more
clever prio tree.
Michel Lespinasse (5):
rbtree: add prio tree and interval tree tests
mm: replace vma prio_tree with an interval tree
kmemleak: use rbtree instead of prio tree
prio_tree: remove
rbtree: move augmented rbtree functionality to rbtree_augmented.h
Documentation/00-INDEX | 2 -
Documentation/prio_tree.txt | 107 --------
Documentation/rbtree.txt | 13 +
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 +-
arch/x86/mm/pat_rbtree.c | 2 +-
fs/hugetlbfs/inode.c | 9 +-
fs/inode.c | 2 +-
include/linux/fs.h | 6 +-
include/linux/interval_tree.h | 27 ++
include/linux/interval_tree_tmpl.h | 219 +++++++++++++++++
include/linux/mm.h | 30 ++-
include/linux/mm_types.h | 14 +-
include/linux/prio_tree.h | 120 ---------
include/linux/rbtree.h | 48 ----
include/linux/rbtree_augmented.h | 223 +++++++++++++++++
init/main.c | 2 -
kernel/events/uprobes.c | 3 +-
kernel/fork.c | 2 +-
lib/Kconfig.debug | 6 +
lib/Makefile | 5 +-
lib/interval_tree.c | 13 +
lib/interval_tree_test_main.c | 105 ++++++++
lib/prio_tree.c | 466 ------------------------------------
lib/rbtree.c | 162 +------------
lib/rbtree_test.c | 2 +-
mm/Makefile | 4 +-
mm/filemap_xip.c | 3 +-
mm/fremap.c | 2 +-
mm/hugetlb.c | 3 +-
mm/interval_tree.c | 61 +++++
mm/kmemleak.c | 98 ++++----
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 +-
40 files changed, 803 insertions(+), 1240 deletions(-)
delete mode 100644 Documentation/prio_tree.txt
create mode 100644 include/linux/interval_tree.h
create mode 100644 include/linux/interval_tree_tmpl.h
delete mode 100644 include/linux/prio_tree.h
create mode 100644 include/linux/rbtree_augmented.h
create mode 100644 lib/interval_tree.c
create mode 100644 lib/interval_tree_test_main.c
delete mode 100644 lib/prio_tree.c
create mode 100644 mm/interval_tree.c
delete mode 100644 mm/prio_tree.c
--
1.7.7.3
^ permalink raw reply [flat|nested] 18+ messages in thread
* [PATCH 1/5] rbtree: add prio tree and interval tree tests
2012-08-07 7:25 [PATCH 0/5] rbtree based interval tree as a prio_tree replacement Michel Lespinasse
@ 2012-08-07 7:25 ` Michel Lespinasse
2012-08-07 7:25 ` [PATCH 2/5] mm: replace vma prio_tree with an interval tree Michel Lespinasse
` (5 subsequent siblings)
6 siblings, 0 replies; 18+ messages in thread
From: Michel Lespinasse @ 2012-08-07 7:25 UTC (permalink / raw)
To: riel, peterz, vrajesh, daniel.santos, aarcange, dwmw2, akpm
Cc: linux-mm, linux-kernel, torvalds
This adds two test modules:
- prio_tree_test measures the performance of lib/prio_tree.c, both for
insertion/removal and for stabbing searches
- interval_tree_test measures the performance of a library of equivalent
functionality, built using the augmented rbtree support.
In order to support the second test module, lib/interval_tree.c is
introduced. It is kept separate from the interval_tree_test main file
for two reasons: first we don't want to provide an unfair advantage
over prio_tree_test by having everything in a single compilation unit,
and second there is the possibility that the interval tree functionality
could get some non-test users in kernel over time.
Signed-off-by: Michel Lespinasse <walken@google.com>
---
include/linux/interval_tree.h | 27 +++++++
lib/Kconfig.debug | 12 +++
lib/Makefile | 4 +
lib/interval_tree.c | 159 +++++++++++++++++++++++++++++++++++++++++
lib/interval_tree_test_main.c | 105 +++++++++++++++++++++++++++
lib/prio_tree.c | 4 +
lib/prio_tree_test.c | 106 +++++++++++++++++++++++++++
7 files changed, 417 insertions(+), 0 deletions(-)
create mode 100644 include/linux/interval_tree.h
create mode 100644 lib/interval_tree.c
create mode 100644 lib/interval_tree_test_main.c
create mode 100644 lib/prio_tree_test.c
diff --git a/include/linux/interval_tree.h b/include/linux/interval_tree.h
new file mode 100644
index 0000000..724556a
--- /dev/null
+++ b/include/linux/interval_tree.h
@@ -0,0 +1,27 @@
+#ifndef _LINUX_INTERVAL_TREE_H
+#define _LINUX_INTERVAL_TREE_H
+
+#include <linux/rbtree.h>
+
+struct interval_tree_node {
+ struct rb_node rb;
+ unsigned long start; /* Start of interval */
+ unsigned long last; /* Last location _in_ interval */
+ unsigned long __subtree_last;
+};
+
+extern void
+interval_tree_insert(struct interval_tree_node *node, struct rb_root *root);
+
+extern void
+interval_tree_remove(struct interval_tree_node *node, struct rb_root *root);
+
+extern struct interval_tree_node *
+interval_tree_iter_first(struct rb_root *root,
+ unsigned long start, unsigned long last);
+
+extern struct interval_tree_node *
+interval_tree_iter_next(struct interval_tree_node *node,
+ unsigned long start, unsigned long last);
+
+#endif /* _LINUX_INTERVAL_TREE_H */
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index d751431..331c64d 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1185,6 +1185,18 @@ config RBTREE_TEST
A benchmark measuring the performance of the rbtree library.
Also includes rbtree invariant checks.
+config PRIO_TREE_TEST
+ tristate "Prio tree test"
+ depends on m && DEBUG_KERNEL
+ help
+ A benchmark measuring the performance of the prio tree library
+
+config INTERVAL_TREE_TEST
+ tristate "Interval tree test"
+ depends on m && DEBUG_KERNEL
+ help
+ A benchmark measuring the performance of the interval tree library
+
config PROVIDE_OHCI1394_DMA_INIT
bool "Remote debugging over FireWire early on boot"
depends on PCI && X86
diff --git a/lib/Makefile b/lib/Makefile
index 9c5c529..e1f109f 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -131,6 +131,10 @@ obj-$(CONFIG_GENERIC_STRNLEN_USER) += strnlen_user.o
obj-$(CONFIG_STMP_DEVICE) += stmp_device.o
obj-$(CONFIG_RBTREE_TEST) += rbtree_test.o
+obj-$(CONFIG_PRIO_TREE_TEST) += prio_tree_test.o
+obj-$(CONFIG_INTERVAL_TREE_TEST) += interval_tree_test.o
+
+interval_tree_test-objs := interval_tree_test_main.o interval_tree.o
hostprogs-y := gen_crc32table
clean-files := crc32table.h
diff --git a/lib/interval_tree.c b/lib/interval_tree.c
new file mode 100644
index 0000000..6fd540b
--- /dev/null
+++ b/lib/interval_tree.c
@@ -0,0 +1,159 @@
+#include <linux/init.h>
+#include <linux/interval_tree.h>
+
+/* Callbacks for augmented rbtree insert and remove */
+
+static inline unsigned long
+compute_subtree_last(struct interval_tree_node *node)
+{
+ unsigned long max = node->last, subtree_last;
+ if (node->rb.rb_left) {
+ subtree_last = rb_entry(node->rb.rb_left,
+ struct interval_tree_node, rb)->__subtree_last;
+ if (max < subtree_last)
+ max = subtree_last;
+ }
+ if (node->rb.rb_right) {
+ subtree_last = rb_entry(node->rb.rb_right,
+ struct interval_tree_node, rb)->__subtree_last;
+ if (max < subtree_last)
+ max = subtree_last;
+ }
+ return max;
+}
+
+RB_DECLARE_CALLBACKS(static, augment_callbacks, struct interval_tree_node, rb,
+ unsigned long, __subtree_last, compute_subtree_last)
+
+/* Insert / remove interval nodes from the tree */
+
+void interval_tree_insert(struct interval_tree_node *node,
+ struct rb_root *root)
+{
+ struct rb_node **link = &root->rb_node, *rb_parent = NULL;
+ unsigned long start = node->start, last = node->last;
+ struct interval_tree_node *parent;
+
+ while (*link) {
+ rb_parent = *link;
+ parent = rb_entry(rb_parent, struct interval_tree_node, rb);
+ if (parent->__subtree_last < last)
+ parent->__subtree_last = last;
+ if (start < parent->start)
+ link = &parent->rb.rb_left;
+ else
+ link = &parent->rb.rb_right;
+ }
+
+ node->__subtree_last = last;
+ rb_link_node(&node->rb, rb_parent, link);
+ rb_insert_augmented(&node->rb, root, &augment_callbacks);
+}
+
+void interval_tree_remove(struct interval_tree_node *node,
+ struct rb_root *root)
+{
+ rb_erase_augmented(&node->rb, root, &augment_callbacks);
+}
+
+/*
+ * Iterate over intervals intersecting [start;last]
+ *
+ * Note that a node's interval intersects [start;last] iff:
+ * Cond1: node->start <= last
+ * and
+ * Cond2: start <= node->last
+ */
+
+static struct interval_tree_node *
+subtree_search(struct interval_tree_node *node,
+ unsigned long start, unsigned long last)
+{
+ while (true) {
+ /*
+ * Loop invariant: start <= node->__subtree_last
+ * (Cond2 is satisfied by one of the subtree nodes)
+ */
+ if (node->rb.rb_left) {
+ struct interval_tree_node *left =
+ rb_entry(node->rb.rb_left,
+ struct interval_tree_node, rb);
+ if (start <= left->__subtree_last) {
+ /*
+ * Some nodes in left subtree satisfy Cond2.
+ * Iterate to find the leftmost such node N.
+ * If it also satisfies Cond1, that's the match
+ * we are looking for. Otherwise, there is no
+ * matching interval as nodes to the right of N
+ * can't satisfy Cond1 either.
+ */
+ node = left;
+ continue;
+ }
+ }
+ if (node->start <= last) { /* Cond1 */
+ if (start <= node->last) /* Cond2 */
+ return node; /* node is leftmost match */
+ if (node->rb.rb_right) {
+ node = rb_entry(node->rb.rb_right,
+ struct interval_tree_node, rb);
+ if (start <= node->__subtree_last)
+ continue;
+ }
+ }
+ return NULL; /* No match */
+ }
+}
+
+struct interval_tree_node *
+interval_tree_iter_first(struct rb_root *root,
+ unsigned long start, unsigned long last)
+{
+ struct interval_tree_node *node;
+
+ if (!root->rb_node)
+ return NULL;
+ node = rb_entry(root->rb_node, struct interval_tree_node, rb);
+ if (node->__subtree_last < start)
+ return NULL;
+ return subtree_search(node, start, last);
+}
+
+struct interval_tree_node *
+interval_tree_iter_next(struct interval_tree_node *node,
+ unsigned long start, unsigned long last)
+{
+ struct rb_node *rb = node->rb.rb_right, *prev;
+
+ while (true) {
+ /*
+ * Loop invariants:
+ * Cond1: node->start <= last
+ * rb == node->rb.rb_right
+ *
+ * First, search right subtree if suitable
+ */
+ if (rb) {
+ struct interval_tree_node *right =
+ rb_entry(rb, struct interval_tree_node, rb);
+ if (start <= right->__subtree_last)
+ return subtree_search(right, start, last);
+ }
+
+ /* Move up the tree until we come from a node's left child */
+ do {
+ rb = rb_parent(&node->rb);
+ if (!rb)
+ return NULL;
+ prev = &node->rb;
+ node = rb_entry(rb, struct interval_tree_node, rb);
+ rb = node->rb.rb_right;
+ } while (prev == rb);
+
+ /* Check if the node intersects [start;last] */
+ if (last < node->start) /* !Cond1 */
+ return NULL;
+ else if (start <= node->last) /* Cond2 */
+ return node;
+ }
+}
diff --git a/lib/interval_tree_test_main.c b/lib/interval_tree_test_main.c
new file mode 100644
index 0000000..b259039
--- /dev/null
+++ b/lib/interval_tree_test_main.c
@@ -0,0 +1,105 @@
+#include <linux/module.h>
+#include <linux/interval_tree.h>
+#include <linux/random.h>
+#include <asm/timex.h>
+
+#define NODES 100
+#define PERF_LOOPS 100000
+#define SEARCHES 100
+#define SEARCH_LOOPS 10000
+
+static struct rb_root root = RB_ROOT;
+static struct interval_tree_node nodes[NODES];
+static u32 queries[SEARCHES];
+
+static struct rnd_state rnd;
+
+static inline unsigned long
+search(unsigned long query, struct rb_root *root)
+{
+ struct interval_tree_node *node;
+ unsigned long results = 0;
+
+ for (node = interval_tree_iter_first(root, query, query); node;
+ node = interval_tree_iter_next(node, query, query))
+ results++;
+ return results;
+}
+
+static void init(void)
+{
+ int i;
+ for (i = 0; i < NODES; i++) {
+ u32 a = prandom32(&rnd), b = prandom32(&rnd);
+ if (a <= b) {
+ nodes[i].start = a;
+ nodes[i].last = b;
+ } else {
+ nodes[i].start = b;
+ nodes[i].last = a;
+ }
+ }
+ for (i = 0; i < SEARCHES; i++)
+ queries[i] = prandom32(&rnd);
+}
+
+static int interval_tree_test_init(void)
+{
+ int i, j;
+ unsigned long results;
+ cycles_t time1, time2, time;
+
+ printk(KERN_ALERT "interval tree insert/remove");
+
+ prandom32_seed(&rnd, 3141592653589793238ULL);
+ init();
+
+ time1 = get_cycles();
+
+ for (i = 0; i < PERF_LOOPS; i++) {
+ for (j = 0; j < NODES; j++)
+ interval_tree_insert(nodes + j, &root);
+ for (j = 0; j < NODES; j++)
+ interval_tree_remove(nodes + j, &root);
+ }
+
+ time2 = get_cycles();
+ time = time2 - time1;
+
+ time = div_u64(time, PERF_LOOPS);
+ printk(" -> %llu cycles\n", (unsigned long long)time);
+
+ printk(KERN_ALERT "interval tree search");
+
+ for (j = 0; j < NODES; j++)
+ interval_tree_insert(nodes + j, &root);
+
+ time1 = get_cycles();
+
+ results = 0;
+ for (i = 0; i < SEARCH_LOOPS; i++)
+ for (j = 0; j < SEARCHES; j++)
+ results += search(queries[j], &root);
+
+ time2 = get_cycles();
+ time = time2 - time1;
+
+ time = div_u64(time, SEARCH_LOOPS);
+ results = div_u64(results, SEARCH_LOOPS);
+ printk(" -> %llu cycles (%lu results)\n",
+ (unsigned long long)time, results);
+
+ return -EAGAIN; /* Fail will directly unload the module */
+}
+
+static void interval_tree_test_exit(void)
+{
+ printk(KERN_ALERT "test exit\n");
+}
+
+module_init(interval_tree_test_init)
+module_exit(interval_tree_test_exit)
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Michel Lespinasse");
+MODULE_DESCRIPTION("Interval Tree test");
diff --git a/lib/prio_tree.c b/lib/prio_tree.c
index 8d443af..4e0d2ed 100644
--- a/lib/prio_tree.c
+++ b/lib/prio_tree.c
@@ -14,6 +14,7 @@
#include <linux/init.h>
#include <linux/mm.h>
#include <linux/prio_tree.h>
+#include <linux/export.h>
/*
* A clever mix of heap and radix trees forms a radix priority search tree (PST)
@@ -241,6 +242,7 @@ struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root,
BUG();
return NULL;
}
+EXPORT_SYMBOL(prio_tree_insert);
/*
* Remove a prio_tree_node @node from a radix priority search tree @root. The
@@ -290,6 +292,7 @@ void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node)
while (cur != node)
cur = prio_tree_replace(root, cur->parent, cur);
}
+EXPORT_SYMBOL(prio_tree_remove);
static void iter_walk_down(struct prio_tree_iter *iter)
{
@@ -464,3 +467,4 @@ repeat:
goto repeat;
}
+EXPORT_SYMBOL(prio_tree_next);
diff --git a/lib/prio_tree_test.c b/lib/prio_tree_test.c
new file mode 100644
index 0000000..c26084d
--- /dev/null
+++ b/lib/prio_tree_test.c
@@ -0,0 +1,106 @@
+#include <linux/module.h>
+#include <linux/prio_tree.h>
+#include <linux/random.h>
+#include <asm/timex.h>
+
+#define NODES 100
+#define PERF_LOOPS 100000
+#define SEARCHES 100
+#define SEARCH_LOOPS 10000
+
+static struct prio_tree_root root;
+static struct prio_tree_node nodes[NODES];
+static u32 queries[SEARCHES];
+
+static struct rnd_state rnd;
+
+static inline unsigned long
+search(unsigned long query, struct prio_tree_root *root)
+{
+ struct prio_tree_iter iter;
+ unsigned long results = 0;
+
+ prio_tree_iter_init(&iter, root, query, query);
+ while (prio_tree_next(&iter))
+ results++;
+ return results;
+}
+
+static void init(void)
+{
+ int i;
+ for (i = 0; i < NODES; i++) {
+ u32 a = prandom32(&rnd), b = prandom32(&rnd);
+ if (a <= b) {
+ nodes[i].start = a;
+ nodes[i].last = b;
+ } else {
+ nodes[i].start = b;
+ nodes[i].last = a;
+ }
+ }
+ for (i = 0; i < SEARCHES; i++)
+ queries[i] = prandom32(&rnd);
+}
+
+static int prio_tree_test_init(void)
+{
+ int i, j;
+ unsigned long results;
+ cycles_t time1, time2, time;
+
+ printk(KERN_ALERT "prio tree insert/remove");
+
+ prandom32_seed(&rnd, 3141592653589793238ULL);
+ INIT_PRIO_TREE_ROOT(&root);
+ init();
+
+ time1 = get_cycles();
+
+ for (i = 0; i < PERF_LOOPS; i++) {
+ for (j = 0; j < NODES; j++)
+ prio_tree_insert(&root, nodes + j);
+ for (j = 0; j < NODES; j++)
+ prio_tree_remove(&root, nodes + j);
+ }
+
+ time2 = get_cycles();
+ time = time2 - time1;
+
+ time = div_u64(time, PERF_LOOPS);
+ printk(" -> %llu cycles\n", (unsigned long long)time);
+
+ printk(KERN_ALERT "prio tree search");
+
+ for (j = 0; j < NODES; j++)
+ prio_tree_insert(&root, nodes + j);
+
+ time1 = get_cycles();
+
+ results = 0;
+ for (i = 0; i < SEARCH_LOOPS; i++)
+ for (j = 0; j < SEARCHES; j++)
+ results += search(queries[j], &root);
+
+ time2 = get_cycles();
+ time = time2 - time1;
+
+ time = div_u64(time, SEARCH_LOOPS);
+ results = div_u64(results, SEARCH_LOOPS);
+ printk(" -> %llu cycles (%lu results)\n",
+ (unsigned long long)time, results);
+
+ return -EAGAIN; /* Fail will directly unload the module */
+}
+
+static void prio_tree_test_exit(void)
+{
+ printk(KERN_ALERT "test exit\n");
+}
+
+module_init(prio_tree_test_init)
+module_exit(prio_tree_test_exit)
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Michel Lespinasse");
+MODULE_DESCRIPTION("Prio Tree test");
--
1.7.7.3
^ permalink raw reply related [flat|nested] 18+ messages in thread
* [PATCH 2/5] mm: replace vma prio_tree with an interval tree
2012-08-07 7:25 [PATCH 0/5] rbtree based interval tree as a prio_tree replacement Michel Lespinasse
2012-08-07 7:25 ` [PATCH 1/5] rbtree: add prio tree and interval tree tests Michel Lespinasse
@ 2012-08-07 7:25 ` Michel Lespinasse
2012-08-14 12:11 ` Hillf Danton
2012-08-07 7:25 ` [PATCH 3/5] kmemleak: use rbtree instead of prio tree Michel Lespinasse
` (4 subsequent siblings)
6 siblings, 1 reply; 18+ messages in thread
From: Michel Lespinasse @ 2012-08-07 7:25 UTC (permalink / raw)
To: riel, peterz, vrajesh, daniel.santos, aarcange, dwmw2, akpm
Cc: linux-mm, linux-kernel, torvalds
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 <walken@google.com>
---
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_tmpl.h | 215 ++++++++++++++++++++++++++++++++++++
include/linux/mm.h | 30 +++--
include/linux/mm_types.h | 14 +--
kernel/events/uprobes.c | 3 +-
kernel/fork.c | 2 +-
lib/interval_tree.c | 166 ++--------------------------
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 | 61 ++++++++++
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, 357 insertions(+), 466 deletions(-)
create mode 100644 include/linux/interval_tree_tmpl.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 7599e26..2a5907b 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 7745854..ad174f6 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, &iter, &mapping->i_mmap, pgoff, pgoff) {
+ vma_interval_tree_foreach(mpnt, &mapping->i_mmap, pgoff, pgoff) {
unsigned long offset;
/*
diff --git a/arch/parisc/kernel/cache.c b/arch/parisc/kernel/cache.c
index 9d18189..48e16dc 100644
--- a/arch/parisc/kernel/cache.c
+++ b/arch/parisc/kernel/cache.c
@@ -276,7 +276,6 @@ void flush_dcache_page(struct page *page)
{
struct address_space *mapping = page_mapping(page);
struct vm_area_struct *mpnt;
- struct prio_tree_iter iter;
unsigned long offset;
unsigned long addr, old_addr = 0;
pgoff_t pgoff;
@@ -299,7 +298,7 @@ void flush_dcache_page(struct page *page)
* to flush one address here for them all to become coherent */
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) {
offset = (pgoff - mpnt->vm_pgoff) << PAGE_SHIFT;
addr = mpnt->vm_start + offset;
diff --git a/arch/x86/mm/hugetlbpage.c b/arch/x86/mm/hugetlbpage.c
index f6679a7..b396cc1 100644
--- a/arch/x86/mm/hugetlbpage.c
+++ b/arch/x86/mm/hugetlbpage.c
@@ -64,7 +64,6 @@ static void huge_pmd_share(struct mm_struct *mm, unsigned long addr, pud_t *pud)
struct address_space *mapping = vma->vm_file->f_mapping;
pgoff_t idx = ((addr - vma->vm_start) >> PAGE_SHIFT) +
vma->vm_pgoff;
- struct prio_tree_iter iter;
struct vm_area_struct *svma;
unsigned long saddr;
pte_t *spte = NULL;
@@ -73,7 +72,7 @@ static void huge_pmd_share(struct mm_struct *mm, unsigned long addr, pud_t *pud)
return;
mutex_lock(&mapping->i_mmap_mutex);
- vma_prio_tree_foreach(svma, &iter, &mapping->i_mmap, idx, idx) {
+ vma_interval_tree_foreach(svma, &mapping->i_mmap, idx, idx) {
if (svma == vma)
continue;
diff --git a/fs/hugetlbfs/inode.c b/fs/hugetlbfs/inode.c
index cc9281b..e011215 100644
--- a/fs/hugetlbfs/inode.c
+++ b/fs/hugetlbfs/inode.c
@@ -397,17 +397,16 @@ static void hugetlbfs_evict_inode(struct inode *inode)
}
static inline void
-hugetlb_vmtruncate_list(struct prio_tree_root *root, pgoff_t pgoff)
+hugetlb_vmtruncate_list(struct rb_root *root, pgoff_t pgoff)
{
struct vm_area_struct *vma;
- struct prio_tree_iter iter;
- vma_prio_tree_foreach(vma, &iter, root, pgoff, ULONG_MAX) {
+ vma_interval_tree_foreach(vma, root, pgoff, ULONG_MAX) {
unsigned long v_offset;
/*
* Can the expression below overflow on 32-bit arches?
- * No, because the prio_tree returns us only those vmas
+ * No, because the interval tree returns us only those vmas
* which overlap the truncated area starting at pgoff,
* and no vma on a 32-bit arch can span beyond the 4GB.
*/
@@ -432,7 +431,7 @@ static int hugetlb_vmtruncate(struct inode *inode, loff_t offset)
i_size_write(inode, offset);
mutex_lock(&mapping->i_mmap_mutex);
- if (!prio_tree_empty(&mapping->i_mmap))
+ if (!RB_EMPTY_ROOT(&mapping->i_mmap))
hugetlb_vmtruncate_list(&mapping->i_mmap, pgoff);
mutex_unlock(&mapping->i_mmap_mutex);
truncate_hugepages(inode, offset);
diff --git a/fs/inode.c b/fs/inode.c
index c99163b..0db8553 100644
--- a/fs/inode.c
+++ b/fs/inode.c
@@ -348,7 +348,7 @@ void address_space_init_once(struct address_space *mapping)
mutex_init(&mapping->i_mmap_mutex);
INIT_LIST_HEAD(&mapping->private_list);
spin_lock_init(&mapping->private_lock);
- INIT_RAW_PRIO_TREE_ROOT(&mapping->i_mmap);
+ mapping->i_mmap = RB_ROOT;
INIT_LIST_HEAD(&mapping->i_mmap_nonlinear);
}
EXPORT_SYMBOL(address_space_init_once);
diff --git a/include/linux/fs.h b/include/linux/fs.h
index 17fd887..f33145c 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -399,7 +399,7 @@ struct inodes_stat_t {
#include <linux/cache.h>
#include <linux/list.h>
#include <linux/radix-tree.h>
-#include <linux/prio_tree.h>
+#include <linux/rbtree.h>
#include <linux/init.h>
#include <linux/pid.h>
#include <linux/bug.h>
@@ -658,7 +658,7 @@ struct address_space {
struct radix_tree_root page_tree; /* radix tree of all pages */
spinlock_t tree_lock; /* and lock protecting it */
unsigned int i_mmap_writable;/* count VM_SHARED mappings */
- struct prio_tree_root i_mmap; /* tree of private and shared mappings */
+ struct rb_root i_mmap; /* tree of private and shared mappings */
struct list_head i_mmap_nonlinear;/*list VM_NONLINEAR mappings */
struct mutex i_mmap_mutex; /* protect tree, count, list */
/* Protected by tree_lock together with the radix tree */
@@ -730,7 +730,7 @@ int mapping_tagged(struct address_space *mapping, int tag);
*/
static inline int mapping_mapped(struct address_space *mapping)
{
- return !prio_tree_empty(&mapping->i_mmap) ||
+ return !RB_EMPTY_ROOT(&mapping->i_mmap) ||
!list_empty(&mapping->i_mmap_nonlinear);
}
diff --git a/include/linux/interval_tree_tmpl.h b/include/linux/interval_tree_tmpl.h
new file mode 100644
index 0000000..c65deda
--- /dev/null
+++ b/include/linux/interval_tree_tmpl.h
@@ -0,0 +1,215 @@
+/*
+ Interval Trees
+ (C) 2012 Michel Lespinasse <walken@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_tmpl.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 endpoing of ITSTRUCT node n
+ * ITSTATIC: 'static' or empty
+ * ITPREFIX: prefix to use for the inline tree definitions
+ */
+
+/* IT(name) -> ITPREFIX_name */
+#define _ITNAME(prefix, name) prefix ## _ ## name
+#define ITNAME(prefix, name) _ITNAME(prefix, name)
+#define IT(name) ITNAME(ITPREFIX, name)
+
+/* Callbacks for augmented rbtree insert and remove */
+
+static inline ITTYPE IT(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;
+ }
+ return max;
+}
+
+static void IT(augment_propagate)(struct rb_node *rb, struct rb_node *stop)
+{
+ while (rb != stop) {
+ ITSTRUCT *node = rb_entry(rb, ITSTRUCT, ITRB);
+ ITTYPE subtree_last = IT(compute_subtree_last)(node);
+ if (node->ITSUBTREE == subtree_last)
+ break;
+ node->ITSUBTREE = subtree_last;
+ rb = rb_parent(&node->ITRB);
+ }
+}
+
+static void IT(augment_copy)(struct rb_node *rb_old, struct rb_node *rb_new)
+{
+ ITSTRUCT *old = rb_entry(rb_old, ITSTRUCT, ITRB);
+ ITSTRUCT *new = rb_entry(rb_new, ITSTRUCT, ITRB);
+
+ new->ITSUBTREE = old->ITSUBTREE;
+}
+
+static void IT(augment_rotate)(struct rb_node *rb_old, struct rb_node *rb_new)
+{
+ ITSTRUCT *old = rb_entry(rb_old, ITSTRUCT, ITRB);
+ ITSTRUCT *new = rb_entry(rb_new, ITSTRUCT, ITRB);
+
+ new->ITSUBTREE = old->ITSUBTREE;
+ old->ITSUBTREE = IT(compute_subtree_last)(old);
+}
+
+static const struct rb_augment_callbacks IT(augment_callbacks) = {
+ IT(augment_propagate), IT(augment_copy), IT(augment_rotate)
+};
+
+/* Insert / remove interval nodes from the tree */
+
+ITSTATIC void IT(insert)(ITSTRUCT *node, struct rb_root *root)
+{
+ struct rb_node **link = &root->rb_node, *rb_parent = NULL;
+ ITTYPE start = ITSTART(node), last = ITLAST(node);
+ ITSTRUCT *parent;
+
+ while (*link) {
+ rb_parent = *link;
+ parent = rb_entry(rb_parent, ITSTRUCT, ITRB);
+ if (parent->ITSUBTREE < last)
+ parent->ITSUBTREE = last;
+ if (start < ITSTART(parent))
+ link = &parent->ITRB.rb_left;
+ else
+ link = &parent->ITRB.rb_right;
+ }
+
+ node->ITSUBTREE = last;
+ rb_link_node(&node->ITRB, rb_parent, link);
+ rb_insert_augmented(&node->ITRB, root, &IT(augment_callbacks));
+}
+
+ITSTATIC void IT(remove)(ITSTRUCT *node, struct rb_root *root)
+{
+ rb_erase_augmented(&node->ITRB, root, &IT(augment_callbacks));
+}
+
+/*
+ * Iterate over intervals intersecting [start;last]
+ *
+ * Note that a node's interval intersects [start;last] iff:
+ * Cond1: ITSTART(node) <= last
+ * and
+ * Cond2: start <= ITLAST(node)
+ */
+
+static ITSTRUCT *IT(subtree_search)(ITSTRUCT *node, ITTYPE start, ITTYPE last)
+{
+ while (true) {
+ /*
+ * Loop invariant: start <= node->ITSUBTREE
+ * (Cond2 is satisfied by one of the subtree nodes)
+ */
+ if (node->ITRB.rb_left) {
+ ITSTRUCT *left = rb_entry(node->ITRB.rb_left,
+ ITSTRUCT, ITRB);
+ if (start <= left->ITSUBTREE) {
+ /*
+ * Some nodes in left subtree satisfy Cond2.
+ * Iterate to find the leftmost such node N.
+ * If it also satisfies Cond1, that's the match
+ * we are looking for. Otherwise, there is no
+ * matching interval as nodes to the right of N
+ * can't satisfy Cond1 either.
+ */
+ node = left;
+ continue;
+ }
+ }
+ if (ITSTART(node) <= last) { /* Cond1 */
+ if (start <= ITLAST(node)) /* Cond2 */
+ return node; /* node is leftmost match */
+ if (node->ITRB.rb_right) {
+ node = rb_entry(node->ITRB.rb_right,
+ ITSTRUCT, ITRB);
+ if (start <= node->ITSUBTREE)
+ continue;
+ }
+ }
+ return NULL; /* No match */
+ }
+}
+
+ITSTATIC ITSTRUCT *IT(iter_first)(struct rb_root *root,
+ ITTYPE start, ITTYPE last)
+{
+ ITSTRUCT *node;
+
+ if (!root->rb_node)
+ return NULL;
+ node = rb_entry(root->rb_node, ITSTRUCT, ITRB);
+ if (node->ITSUBTREE < start)
+ return NULL;
+ return IT(subtree_search)(node, start, last);
+}
+
+ITSTATIC ITSTRUCT *IT(iter_next)(ITSTRUCT *node, ITTYPE start, ITTYPE last)
+{
+ struct rb_node *rb = node->ITRB.rb_right, *prev;
+
+ while (true) {
+ /*
+ * Loop invariants:
+ * Cond1: ITSTART(node) <= last
+ * rb == node->ITRB.rb_right
+ *
+ * First, search right subtree if suitable
+ */
+ if (rb) {
+ ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB);
+ if (start <= right->ITSUBTREE)
+ return IT(subtree_search)(right, start, last);
+ }
+
+ /* Move up the tree until we come from a node's left child */
+ do {
+ rb = rb_parent(&node->ITRB);
+ if (!rb)
+ return NULL;
+ prev = &node->ITRB;
+ node = rb_entry(rb, ITSTRUCT, ITRB);
+ rb = node->ITRB.rb_right;
+ } while (prev == rb);
+
+ /* Check if the node intersects [start;last] */
+ if (last < ITSTART(node)) /* !Cond1 */
+ return NULL;
+ else if (start <= ITLAST(node)) /* Cond2 */
+ return node;
+ }
+}
diff --git a/include/linux/mm.h b/include/linux/mm.h
index b36d08c..dc504c7 100644
--- a/include/linux/mm.h
+++ b/include/linux/mm.h
@@ -10,7 +10,6 @@
#include <linux/list.h>
#include <linux/mmzone.h>
#include <linux/rbtree.h>
-#include <linux/prio_tree.h>
#include <linux/atomic.h>
#include <linux/debug_locks.h>
#include <linux/mm_types.h>
@@ -1336,22 +1335,27 @@ extern void zone_pcp_update(struct zone *zone);
extern atomic_long_t mmap_pages_allocated;
extern int nommu_shrink_inode_mappings(struct inode *, size_t, size_t);
-/* prio_tree.c */
-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 *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)); )
+/* interval_tree.c */
+void vma_interval_tree_add(struct vm_area_struct *vma,
+ struct vm_area_struct *old,
+ struct address_space *mapping);
+void vma_interval_tree_insert(struct vm_area_struct *node,
+ struct rb_root *root);
+void vma_interval_tree_remove(struct vm_area_struct *node,
+ struct rb_root *root);
+struct vm_area_struct *vma_interval_tree_iter_first(struct rb_root *root,
+ unsigned long start, unsigned long last);
+struct vm_area_struct *vma_interval_tree_iter_next(struct vm_area_struct *node,
+ unsigned long start, unsigned long last);
+
+#define vma_interval_tree_foreach(vma, root, start, last) \
+ for (vma = vma_interval_tree_iter_first(root, start, last); \
+ vma; vma = vma_interval_tree_iter_next(vma, start, last))
static inline void vma_nonlinear_insert(struct vm_area_struct *vma,
struct list_head *list)
{
- vma->shared.vm_set.parent = NULL;
- list_add_tail(&vma->shared.vm_set.list, list);
+ list_add_tail(&vma->shared.nonlinear, list);
}
/* mmap.c */
diff --git a/include/linux/mm_types.h b/include/linux/mm_types.h
index 704a626..a198a40 100644
--- a/include/linux/mm_types.h
+++ b/include/linux/mm_types.h
@@ -6,7 +6,6 @@
#include <linux/threads.h>
#include <linux/list.h>
#include <linux/spinlock.h>
-#include <linux/prio_tree.h>
#include <linux/rbtree.h>
#include <linux/rwsem.h>
#include <linux/completion.h>
@@ -224,18 +223,15 @@ struct vm_area_struct {
/*
* For areas with an address space and backing store,
- * linkage into the address_space->i_mmap prio tree, or
- * linkage to the list of like vmas hanging off its node, or
+ * linkage into the address_space->i_mmap interval tree, or
* linkage of vma in the address_space->i_mmap_nonlinear list.
*/
union {
struct {
- struct list_head list;
- void *parent; /* aligns with prio_tree_node parent */
- struct vm_area_struct *head;
- } vm_set;
-
- struct raw_prio_tree_node prio_tree_node;
+ struct rb_node rb;
+ unsigned long rb_subtree_last;
+ } linear;
+ struct list_head nonlinear;
} shared;
/*
diff --git a/kernel/events/uprobes.c b/kernel/events/uprobes.c
index 985be4d..c06930e 100644
--- a/kernel/events/uprobes.c
+++ b/kernel/events/uprobes.c
@@ -754,7 +754,6 @@ static struct vma_info *
__find_next_vma_info(struct address_space *mapping, struct list_head *head,
struct vma_info *vi, loff_t offset, bool is_register)
{
- struct prio_tree_iter iter;
struct vm_area_struct *vma;
struct vma_info *tmpvi;
unsigned long pgoff;
@@ -763,7 +762,7 @@ __find_next_vma_info(struct address_space *mapping, struct list_head *head,
pgoff = offset >> PAGE_SHIFT;
- vma_prio_tree_foreach(vma, &iter, &mapping->i_mmap, pgoff, pgoff) {
+ vma_interval_tree_foreach(vma, &mapping->i_mmap, pgoff, pgoff) {
if (!valid_vma(vma, is_register))
continue;
diff --git a/kernel/fork.c b/kernel/fork.c
index f00e319..1a5a355 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -425,7 +425,7 @@ static int dup_mmap(struct mm_struct *mm, struct mm_struct *oldmm)
mapping->i_mmap_writable++;
flush_dcache_mmap_lock(mapping);
/* insert tmp into the share list, just after mpnt */
- vma_prio_tree_add(tmp, mpnt);
+ vma_interval_tree_add(tmp, mpnt, mapping);
flush_dcache_mmap_unlock(mapping);
mutex_unlock(&mapping->i_mmap_mutex);
}
diff --git a/lib/interval_tree.c b/lib/interval_tree.c
index 6fd540b..77a793e 100644
--- a/lib/interval_tree.c
+++ b/lib/interval_tree.c
@@ -1,159 +1,13 @@
#include <linux/init.h>
#include <linux/interval_tree.h>
-/* Callbacks for augmented rbtree insert and remove */
-
-static inline unsigned long
-compute_subtree_last(struct interval_tree_node *node)
-{
- unsigned long max = node->last, subtree_last;
- if (node->rb.rb_left) {
- subtree_last = rb_entry(node->rb.rb_left,
- struct interval_tree_node, rb)->__subtree_last;
- if (max < subtree_last)
- max = subtree_last;
- }
- if (node->rb.rb_right) {
- subtree_last = rb_entry(node->rb.rb_right,
- struct interval_tree_node, rb)->__subtree_last;
- if (max < subtree_last)
- max = subtree_last;
- }
- return max;
-}
-
-RB_DECLARE_CALLBACKS(static, augment_callbacks, struct interval_tree_node, rb,
- unsigned long, __subtree_last, compute_subtree_last)
-
-/* Insert / remove interval nodes from the tree */
-
-void interval_tree_insert(struct interval_tree_node *node,
- struct rb_root *root)
-{
- struct rb_node **link = &root->rb_node, *rb_parent = NULL;
- unsigned long start = node->start, last = node->last;
- struct interval_tree_node *parent;
-
- while (*link) {
- rb_parent = *link;
- parent = rb_entry(rb_parent, struct interval_tree_node, rb);
- if (parent->__subtree_last < last)
- parent->__subtree_last = last;
- if (start < parent->start)
- link = &parent->rb.rb_left;
- else
- link = &parent->rb.rb_right;
- }
-
- node->__subtree_last = last;
- rb_link_node(&node->rb, rb_parent, link);
- rb_insert_augmented(&node->rb, root, &augment_callbacks);
-}
-
-void interval_tree_remove(struct interval_tree_node *node,
- struct rb_root *root)
-{
- rb_erase_augmented(&node->rb, root, &augment_callbacks);
-}
-
-/*
- * Iterate over intervals intersecting [start;last]
- *
- * Note that a node's interval intersects [start;last] iff:
- * Cond1: node->start <= last
- * and
- * Cond2: start <= node->last
- */
-
-static struct interval_tree_node *
-subtree_search(struct interval_tree_node *node,
- unsigned long start, unsigned long last)
-{
- while (true) {
- /*
- * Loop invariant: start <= node->__subtree_last
- * (Cond2 is satisfied by one of the subtree nodes)
- */
- if (node->rb.rb_left) {
- struct interval_tree_node *left =
- rb_entry(node->rb.rb_left,
- struct interval_tree_node, rb);
- if (start <= left->__subtree_last) {
- /*
- * Some nodes in left subtree satisfy Cond2.
- * Iterate to find the leftmost such node N.
- * If it also satisfies Cond1, that's the match
- * we are looking for. Otherwise, there is no
- * matching interval as nodes to the right of N
- * can't satisfy Cond1 either.
- */
- node = left;
- continue;
- }
- }
- if (node->start <= last) { /* Cond1 */
- if (start <= node->last) /* Cond2 */
- return node; /* node is leftmost match */
- if (node->rb.rb_right) {
- node = rb_entry(node->rb.rb_right,
- struct interval_tree_node, rb);
- if (start <= node->__subtree_last)
- continue;
- }
- }
- return NULL; /* No match */
- }
-}
-
-struct interval_tree_node *
-interval_tree_iter_first(struct rb_root *root,
- unsigned long start, unsigned long last)
-{
- struct interval_tree_node *node;
-
- if (!root->rb_node)
- return NULL;
- node = rb_entry(root->rb_node, struct interval_tree_node, rb);
- if (node->__subtree_last < start)
- return NULL;
- return subtree_search(node, start, last);
-}
-
-struct interval_tree_node *
-interval_tree_iter_next(struct interval_tree_node *node,
- unsigned long start, unsigned long last)
-{
- struct rb_node *rb = node->rb.rb_right, *prev;
-
- while (true) {
- /*
- * Loop invariants:
- * Cond1: node->start <= last
- * rb == node->rb.rb_right
- *
- * First, search right subtree if suitable
- */
- if (rb) {
- struct interval_tree_node *right =
- rb_entry(rb, struct interval_tree_node, rb);
- if (start <= right->__subtree_last)
- return subtree_search(right, start, last);
- }
-
- /* Move up the tree until we come from a node's left child */
- do {
- rb = rb_parent(&node->rb);
- if (!rb)
- return NULL;
- prev = &node->rb;
- node = rb_entry(rb, struct interval_tree_node, rb);
- rb = node->rb.rb_right;
- } while (prev == rb);
-
- /* Check if the node intersects [start;last] */
- if (last < node->start) /* !Cond1 */
- return NULL;
- else if (start <= node->last) /* Cond2 */
- return node;
- }
-}
+#define ITSTRUCT struct interval_tree_node
+#define ITRB rb
+#define ITTYPE unsigned long
+#define ITSUBTREE __subtree_last
+#define ITSTART(n) ((n)->start)
+#define ITLAST(n) ((n)->last)
+#define ITSTATIC
+#define ITPREFIX interval_tree
+
+#include <linux/interval_tree_tmpl.h>
diff --git a/lib/prio_tree.c b/lib/prio_tree.c
index 4e0d2ed..bba3714 100644
--- a/lib/prio_tree.c
+++ b/lib/prio_tree.c
@@ -44,27 +44,12 @@
* The following macros are used for implementing prio_tree for i_mmap
*/
-#define RADIX_INDEX(vma) ((vma)->vm_pgoff)
-#define VMA_SIZE(vma) (((vma)->vm_end - (vma)->vm_start) >> PAGE_SHIFT)
-/* avoid overflow */
-#define HEAP_INDEX(vma) ((vma)->vm_pgoff + (VMA_SIZE(vma) - 1))
-
-
static void get_index(const struct prio_tree_root *root,
const struct prio_tree_node *node,
unsigned long *radix, unsigned long *heap)
{
- if (root->raw) {
- struct vm_area_struct *vma = prio_tree_entry(
- node, struct vm_area_struct, shared.prio_tree_node);
-
- *radix = RADIX_INDEX(vma);
- *heap = HEAP_INDEX(vma);
- }
- else {
- *radix = node->start;
- *heap = node->last;
- }
+ *radix = node->start;
+ *heap = node->last;
}
static unsigned long index_bits_to_maxindex[BITS_PER_LONG];
diff --git a/mm/Makefile b/mm/Makefile
index 2e2fbbe..fd9cc64 100644
--- a/mm/Makefile
+++ b/mm/Makefile
@@ -14,9 +14,9 @@ endif
obj-y := filemap.o mempool.o oom_kill.o fadvise.o \
maccess.o page_alloc.o page-writeback.o \
readahead.o swap.o truncate.o vmscan.o shmem.o \
- prio_tree.o util.o mmzone.o vmstat.o backing-dev.o \
+ util.o mmzone.o vmstat.o backing-dev.o \
page_isolation.o mm_init.o mmu_context.o percpu.o \
- compaction.o $(mmu-y)
+ compaction.o interval_tree.o $(mmu-y)
obj-y += init-mm.o
ifdef CONFIG_NO_BOOTMEM
diff --git a/mm/filemap_xip.c b/mm/filemap_xip.c
index 213ca1f..c126d3e 100644
--- a/mm/filemap_xip.c
+++ b/mm/filemap_xip.c
@@ -167,7 +167,6 @@ __xip_unmap (struct address_space * mapping,
{
struct vm_area_struct *vma;
struct mm_struct *mm;
- struct prio_tree_iter iter;
unsigned long address;
pte_t *pte;
pte_t pteval;
@@ -184,7 +183,7 @@ __xip_unmap (struct address_space * mapping,
retry:
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) {
mm = vma->vm_mm;
address = vma->vm_start +
((pgoff - vma->vm_pgoff) << PAGE_SHIFT);
diff --git a/mm/fremap.c b/mm/fremap.c
index 9ed4fd4..2e582fe 100644
--- a/mm/fremap.c
+++ b/mm/fremap.c
@@ -213,7 +213,7 @@ SYSCALL_DEFINE5(remap_file_pages, unsigned long, start, unsigned long, size,
mutex_lock(&mapping->i_mmap_mutex);
flush_dcache_mmap_lock(mapping);
vma->vm_flags |= VM_NONLINEAR;
- vma_prio_tree_remove(vma, &mapping->i_mmap);
+ vma_interval_tree_remove(vma, &mapping->i_mmap);
vma_nonlinear_insert(vma, &mapping->i_mmap_nonlinear);
flush_dcache_mmap_unlock(mapping);
mutex_unlock(&mapping->i_mmap_mutex);
diff --git a/mm/hugetlb.c b/mm/hugetlb.c
index e198831..ec50883 100644
--- a/mm/hugetlb.c
+++ b/mm/hugetlb.c
@@ -2408,7 +2408,6 @@ static int unmap_ref_private(struct mm_struct *mm, struct vm_area_struct *vma,
struct hstate *h = hstate_vma(vma);
struct vm_area_struct *iter_vma;
struct address_space *mapping;
- struct prio_tree_iter iter;
pgoff_t pgoff;
/*
@@ -2425,7 +2424,7 @@ static int unmap_ref_private(struct mm_struct *mm, struct vm_area_struct *vma,
* __unmap_hugepage_range() is called as the lock is already held
*/
mutex_lock(&mapping->i_mmap_mutex);
- vma_prio_tree_foreach(iter_vma, &iter, &mapping->i_mmap, pgoff, pgoff) {
+ vma_interval_tree_foreach(iter_vma, &mapping->i_mmap, pgoff, pgoff) {
/* Do not unmap the current VMA */
if (iter_vma == vma)
continue;
diff --git a/mm/interval_tree.c b/mm/interval_tree.c
new file mode 100644
index 0000000..7dc56566
--- /dev/null
+++ b/mm/interval_tree.c
@@ -0,0 +1,61 @@
+/*
+ * mm/interval_tree.c - interval tree for mapping->i_mmap
+ *
+ * Copyright (C) 2012, Michel Lespinasse <walken@google.com>
+ *
+ * This file is released under the GPL v2.
+ */
+
+#include <linux/mm.h>
+#include <linux/fs.h>
+
+#define ITSTRUCT struct vm_area_struct
+#define ITRB shared.linear.rb
+#define ITTYPE unsigned long
+#define ITSUBTREE shared.linear.rb_subtree_last
+#define ITSTART(n) ((n)->vm_pgoff)
+#define ITLAST(n) ((n)->vm_pgoff + \
+ (((n)->vm_end - (n)->vm_start) >> PAGE_SHIFT) - 1)
+#define ITSTATIC
+#define ITPREFIX vma_interval_tree
+
+#include <linux/interval_tree_tmpl.h>
+
+/* Insert old immediately after vma in the interval tree */
+void vma_interval_tree_add(struct vm_area_struct *vma,
+ struct vm_area_struct *old,
+ struct address_space *mapping)
+{
+ struct rb_node **link;
+ struct vm_area_struct *parent;
+ unsigned long last;
+
+ if (unlikely(vma->vm_flags & VM_NONLINEAR)) {
+ list_add(&vma->shared.nonlinear, &old->shared.nonlinear);
+ return;
+ }
+
+ last = ITLAST(vma);
+
+ if (!old->shared.linear.rb.rb_right) {
+ parent = old;
+ link = &old->shared.linear.rb.rb_right;
+ } else {
+ parent = rb_entry(old->shared.linear.rb.rb_right,
+ struct vm_area_struct, shared.linear.rb);
+ if (parent->shared.linear.rb_subtree_last < last)
+ parent->shared.linear.rb_subtree_last = last;
+ while (parent->shared.linear.rb.rb_left) {
+ parent = rb_entry(parent->shared.linear.rb.rb_left,
+ struct vm_area_struct, shared.linear.rb);
+ if (parent->shared.linear.rb_subtree_last < last)
+ parent->shared.linear.rb_subtree_last = last;
+ }
+ link = &parent->shared.linear.rb.rb_left;
+ }
+
+ vma->shared.linear.rb_subtree_last = last;
+ rb_link_node(&vma->shared.linear.rb, &parent->shared.linear.rb, link);
+ rb_insert_augmented(&vma->shared.linear.rb, &mapping->i_mmap,
+ &vma_interval_tree_augment_callbacks);
+}
diff --git a/mm/memory-failure.c b/mm/memory-failure.c
index ab1e714..65d5e8d 100644
--- a/mm/memory-failure.c
+++ b/mm/memory-failure.c
@@ -431,7 +431,6 @@ static void collect_procs_file(struct page *page, struct list_head *to_kill,
{
struct vm_area_struct *vma;
struct task_struct *tsk;
- struct prio_tree_iter iter;
struct address_space *mapping = page->mapping;
mutex_lock(&mapping->i_mmap_mutex);
@@ -442,7 +441,7 @@ static void collect_procs_file(struct page *page, struct list_head *to_kill,
if (!task_early_kill(tsk))
continue;
- vma_prio_tree_foreach(vma, &iter, &mapping->i_mmap, pgoff,
+ vma_interval_tree_foreach(vma, &mapping->i_mmap, pgoff,
pgoff) {
/*
* Send early kill signal to tasks where a vma covers
diff --git a/mm/memory.c b/mm/memory.c
index 2466d12..51dd129 100644
--- a/mm/memory.c
+++ b/mm/memory.c
@@ -2790,14 +2790,13 @@ static void unmap_mapping_range_vma(struct vm_area_struct *vma,
zap_page_range_single(vma, start_addr, end_addr - start_addr, details);
}
-static inline void unmap_mapping_range_tree(struct prio_tree_root *root,
+static inline void unmap_mapping_range_tree(struct rb_root *root,
struct zap_details *details)
{
struct vm_area_struct *vma;
- struct prio_tree_iter iter;
pgoff_t vba, vea, zba, zea;
- vma_prio_tree_foreach(vma, &iter, root,
+ vma_interval_tree_foreach(vma, root,
details->first_index, details->last_index) {
vba = vma->vm_pgoff;
@@ -2828,7 +2827,7 @@ static inline void unmap_mapping_range_list(struct list_head *head,
* across *all* the pages in each nonlinear VMA, not just the pages
* whose virtual address lies outside the file truncation point.
*/
- list_for_each_entry(vma, head, shared.vm_set.list) {
+ list_for_each_entry(vma, head, shared.nonlinear) {
details->nonlinear_vma = vma;
unmap_mapping_range_vma(vma, vma->vm_start, vma->vm_end, details);
}
@@ -2872,7 +2871,7 @@ void unmap_mapping_range(struct address_space *mapping,
mutex_lock(&mapping->i_mmap_mutex);
- if (unlikely(!prio_tree_empty(&mapping->i_mmap)))
+ if (unlikely(!RB_EMPTY_ROOT(&mapping->i_mmap)))
unmap_mapping_range_tree(&mapping->i_mmap, &details);
if (unlikely(!list_empty(&mapping->i_mmap_nonlinear)))
unmap_mapping_range_list(&mapping->i_mmap_nonlinear, &details);
diff --git a/mm/mmap.c b/mm/mmap.c
index 3edfcdf..cebc346 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -199,14 +199,14 @@ static void __remove_shared_vm_struct(struct vm_area_struct *vma,
flush_dcache_mmap_lock(mapping);
if (unlikely(vma->vm_flags & VM_NONLINEAR))
- list_del_init(&vma->shared.vm_set.list);
+ list_del_init(&vma->shared.nonlinear);
else
- vma_prio_tree_remove(vma, &mapping->i_mmap);
+ vma_interval_tree_remove(vma, &mapping->i_mmap);
flush_dcache_mmap_unlock(mapping);
}
/*
- * Unlink a file-based vm structure from its prio_tree, to hide
+ * Unlink a file-based vm structure from its interval tree, to hide
* vma from rmap and vmtruncate before freeing its page tables.
*/
void unlink_file_vma(struct vm_area_struct *vma)
@@ -417,7 +417,7 @@ static void __vma_link_file(struct vm_area_struct *vma)
if (unlikely(vma->vm_flags & VM_NONLINEAR))
vma_nonlinear_insert(vma, &mapping->i_mmap_nonlinear);
else
- vma_prio_tree_insert(vma, &mapping->i_mmap);
+ vma_interval_tree_insert(vma, &mapping->i_mmap);
flush_dcache_mmap_unlock(mapping);
}
}
@@ -455,7 +455,7 @@ static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma,
/*
* Helper for vma_adjust() in the split_vma insert case: insert a vma into the
- * mm's list and rbtree. It has already been inserted into the prio_tree.
+ * mm's list and rbtree. It has already been inserted into the interval tree.
*/
static void __insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vma)
{
@@ -496,7 +496,7 @@ int vma_adjust(struct vm_area_struct *vma, unsigned long start,
struct vm_area_struct *next = vma->vm_next;
struct vm_area_struct *importer = NULL;
struct address_space *mapping = NULL;
- struct prio_tree_root *root = NULL;
+ struct rb_root *root = NULL;
struct anon_vma *anon_vma = NULL;
struct file *file = vma->vm_file;
long adjust_next = 0;
@@ -559,7 +559,7 @@ again: remove_next = 1 + (end > next->vm_end);
mutex_lock(&mapping->i_mmap_mutex);
if (insert) {
/*
- * Put into prio_tree now, so instantiated pages
+ * Put into interval tree now, so instantiated pages
* are visible to arm/parisc __flush_dcache_page
* throughout; but we cannot insert into address
* space until vma start or end is updated.
@@ -583,9 +583,9 @@ again: remove_next = 1 + (end > next->vm_end);
if (root) {
flush_dcache_mmap_lock(mapping);
- vma_prio_tree_remove(vma, root);
+ vma_interval_tree_remove(vma, root);
if (adjust_next)
- vma_prio_tree_remove(next, root);
+ vma_interval_tree_remove(next, root);
}
vma->vm_start = start;
@@ -598,8 +598,8 @@ again: remove_next = 1 + (end > next->vm_end);
if (root) {
if (adjust_next)
- vma_prio_tree_insert(next, root);
- vma_prio_tree_insert(vma, root);
+ vma_interval_tree_insert(next, root);
+ vma_interval_tree_insert(vma, root);
flush_dcache_mmap_unlock(mapping);
}
diff --git a/mm/nommu.c b/mm/nommu.c
index d4b0c10..935de1a 100644
--- a/mm/nommu.c
+++ b/mm/nommu.c
@@ -698,7 +698,7 @@ static void add_vma_to_mm(struct mm_struct *mm, struct vm_area_struct *vma)
mutex_lock(&mapping->i_mmap_mutex);
flush_dcache_mmap_lock(mapping);
- vma_prio_tree_insert(vma, &mapping->i_mmap);
+ vma_interval_tree_insert(vma, &mapping->i_mmap);
flush_dcache_mmap_unlock(mapping);
mutex_unlock(&mapping->i_mmap_mutex);
}
@@ -764,7 +764,7 @@ static void delete_vma_from_mm(struct vm_area_struct *vma)
mutex_lock(&mapping->i_mmap_mutex);
flush_dcache_mmap_lock(mapping);
- vma_prio_tree_remove(vma, &mapping->i_mmap);
+ vma_interval_tree_remove(vma, &mapping->i_mmap);
flush_dcache_mmap_unlock(mapping);
mutex_unlock(&mapping->i_mmap_mutex);
}
@@ -2047,7 +2047,6 @@ int nommu_shrink_inode_mappings(struct inode *inode, size_t size,
size_t newsize)
{
struct vm_area_struct *vma;
- struct prio_tree_iter iter;
struct vm_region *region;
pgoff_t low, high;
size_t r_size, r_top;
@@ -2059,8 +2058,7 @@ int nommu_shrink_inode_mappings(struct inode *inode, size_t size,
mutex_lock(&inode->i_mapping->i_mmap_mutex);
/* search for VMAs that fall within the dead zone */
- vma_prio_tree_foreach(vma, &iter, &inode->i_mapping->i_mmap,
- low, high) {
+ vma_interval_tree_foreach(vma, &inode->i_mapping->i_mmap, low, high) {
/* found one - only interested if it's shared out of the page
* cache */
if (vma->vm_flags & VM_SHARED) {
@@ -2076,8 +2074,8 @@ int nommu_shrink_inode_mappings(struct inode *inode, size_t size,
* we don't check for any regions that start beyond the EOF as there
* shouldn't be any
*/
- vma_prio_tree_foreach(vma, &iter, &inode->i_mapping->i_mmap,
- 0, ULONG_MAX) {
+ vma_interval_tree_foreach(vma, &inode->i_mapping->i_mmap,
+ 0, ULONG_MAX) {
if (!(vma->vm_flags & VM_SHARED))
continue;
diff --git a/mm/prio_tree.c b/mm/prio_tree.c
deleted file mode 100644
index 799dcfd..0000000
--- a/mm/prio_tree.c
+++ /dev/null
@@ -1,208 +0,0 @@
-/*
- * mm/prio_tree.c - priority search tree for mapping->i_mmap
- *
- * Copyright (C) 2004, Rajesh Venkatasubramanian <vrajesh@umich.edu>
- *
- * This file is released under the GPL v2.
- *
- * Based on the radix priority search tree proposed by Edward M. McCreight
- * SIAM Journal of Computing, vol. 14, no.2, pages 257-276, May 1985
- *
- * 02Feb2004 Initial version
- */
-
-#include <linux/mm.h>
-#include <linux/prio_tree.h>
-#include <linux/prefetch.h>
-
-/*
- * See lib/prio_tree.c for details on the general radix priority search tree
- * code.
- */
-
-/*
- * The following #defines are mirrored from lib/prio_tree.c. They're only used
- * for debugging, and should be removed (along with the debugging code using
- * them) when switching also VMAs to the regular prio_tree code.
- */
-
-#define RADIX_INDEX(vma) ((vma)->vm_pgoff)
-#define VMA_SIZE(vma) (((vma)->vm_end - (vma)->vm_start) >> PAGE_SHIFT)
-/* avoid overflow */
-#define HEAP_INDEX(vma) ((vma)->vm_pgoff + (VMA_SIZE(vma) - 1))
-
-/*
- * Radix priority search tree for address_space->i_mmap
- *
- * For each vma that map a unique set of file pages i.e., unique [radix_index,
- * heap_index] value, we have a corresponding priority search tree node. If
- * multiple vmas have identical [radix_index, heap_index] value, then one of
- * them is used as a tree node and others are stored in a vm_set list. The tree
- * node points to the first vma (head) of the list using vm_set.head.
- *
- * prio_tree_root
- * |
- * A vm_set.head
- * / \ /
- * L R -> H-I-J-K-M-N-O-P-Q-S
- * ^ ^ <-- vm_set.list -->
- * tree nodes
- *
- * We need some way to identify whether a vma is a tree node, head of a vm_set
- * list, or just a member of a vm_set list. We cannot use vm_flags to store
- * such information. The reason is, in the above figure, it is possible that
- * vm_flags' of R and H are covered by the different mmap_sems. When R is
- * removed under R->mmap_sem, H replaces R as a tree node. Since we do not hold
- * H->mmap_sem, we cannot use H->vm_flags for marking that H is a tree node now.
- * That's why some trick involving shared.vm_set.parent is used for identifying
- * tree nodes and list head nodes.
- *
- * vma radix priority search tree node rules:
- *
- * vma->shared.vm_set.parent != NULL ==> a tree node
- * vma->shared.vm_set.head != NULL ==> list of others mapping same range
- * vma->shared.vm_set.head == NULL ==> no others map the same range
- *
- * vma->shared.vm_set.parent == NULL
- * vma->shared.vm_set.head != NULL ==> list head of vmas mapping same range
- * vma->shared.vm_set.head == NULL ==> a list node
- */
-
-/*
- * Add a new vma known to map the same set of pages as the old vma:
- * useful for fork's dup_mmap as well as vma_prio_tree_insert below.
- * Note that it just happens to work correctly on i_mmap_nonlinear too.
- */
-void vma_prio_tree_add(struct vm_area_struct *vma, struct vm_area_struct *old)
-{
- /* Leave these BUG_ONs till prio_tree patch stabilizes */
- BUG_ON(RADIX_INDEX(vma) != RADIX_INDEX(old));
- BUG_ON(HEAP_INDEX(vma) != HEAP_INDEX(old));
-
- vma->shared.vm_set.head = NULL;
- vma->shared.vm_set.parent = NULL;
-
- if (!old->shared.vm_set.parent)
- list_add(&vma->shared.vm_set.list,
- &old->shared.vm_set.list);
- else if (old->shared.vm_set.head)
- list_add_tail(&vma->shared.vm_set.list,
- &old->shared.vm_set.head->shared.vm_set.list);
- else {
- INIT_LIST_HEAD(&vma->shared.vm_set.list);
- vma->shared.vm_set.head = old;
- old->shared.vm_set.head = vma;
- }
-}
-
-void vma_prio_tree_insert(struct vm_area_struct *vma,
- struct prio_tree_root *root)
-{
- struct prio_tree_node *ptr;
- struct vm_area_struct *old;
-
- vma->shared.vm_set.head = NULL;
-
- ptr = raw_prio_tree_insert(root, &vma->shared.prio_tree_node);
- if (ptr != (struct prio_tree_node *) &vma->shared.prio_tree_node) {
- old = prio_tree_entry(ptr, struct vm_area_struct,
- shared.prio_tree_node);
- vma_prio_tree_add(vma, old);
- }
-}
-
-void vma_prio_tree_remove(struct vm_area_struct *vma,
- struct prio_tree_root *root)
-{
- struct vm_area_struct *node, *head, *new_head;
-
- if (!vma->shared.vm_set.head) {
- if (!vma->shared.vm_set.parent)
- list_del_init(&vma->shared.vm_set.list);
- else
- raw_prio_tree_remove(root, &vma->shared.prio_tree_node);
- } else {
- /* Leave this BUG_ON till prio_tree patch stabilizes */
- BUG_ON(vma->shared.vm_set.head->shared.vm_set.head != vma);
- if (vma->shared.vm_set.parent) {
- head = vma->shared.vm_set.head;
- if (!list_empty(&head->shared.vm_set.list)) {
- new_head = list_entry(
- head->shared.vm_set.list.next,
- struct vm_area_struct,
- shared.vm_set.list);
- list_del_init(&head->shared.vm_set.list);
- } else
- new_head = NULL;
-
- raw_prio_tree_replace(root, &vma->shared.prio_tree_node,
- &head->shared.prio_tree_node);
- head->shared.vm_set.head = new_head;
- if (new_head)
- new_head->shared.vm_set.head = head;
-
- } else {
- node = vma->shared.vm_set.head;
- if (!list_empty(&vma->shared.vm_set.list)) {
- new_head = list_entry(
- vma->shared.vm_set.list.next,
- struct vm_area_struct,
- shared.vm_set.list);
- list_del_init(&vma->shared.vm_set.list);
- node->shared.vm_set.head = new_head;
- new_head->shared.vm_set.head = node;
- } else
- node->shared.vm_set.head = NULL;
- }
- }
-}
-
-/*
- * Helper function to enumerate vmas that map a given file page or a set of
- * contiguous file pages. The function returns vmas that at least map a single
- * 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_iter *iter)
-{
- struct prio_tree_node *ptr;
- struct vm_area_struct *next;
-
- if (!vma) {
- /*
- * First call is with NULL vma
- */
- ptr = prio_tree_next(iter);
- if (ptr) {
- next = prio_tree_entry(ptr, struct vm_area_struct,
- shared.prio_tree_node);
- prefetch(next->shared.vm_set.head);
- return next;
- } else
- return NULL;
- }
-
- if (vma->shared.vm_set.parent) {
- if (vma->shared.vm_set.head) {
- next = vma->shared.vm_set.head;
- prefetch(next->shared.vm_set.list.next);
- return next;
- }
- } else {
- next = list_entry(vma->shared.vm_set.list.next,
- struct vm_area_struct, shared.vm_set.list);
- if (!next->shared.vm_set.head) {
- prefetch(next->shared.vm_set.list.next);
- return next;
- }
- }
-
- ptr = prio_tree_next(iter);
- if (ptr) {
- next = prio_tree_entry(ptr, struct vm_area_struct,
- shared.prio_tree_node);
- prefetch(next->shared.vm_set.head);
- return next;
- } else
- return NULL;
-}
diff --git a/mm/rmap.c b/mm/rmap.c
index 0f3b7cd..7b5b51d 100644
--- a/mm/rmap.c
+++ b/mm/rmap.c
@@ -820,7 +820,6 @@ static int page_referenced_file(struct page *page,
struct address_space *mapping = page->mapping;
pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
struct vm_area_struct *vma;
- struct prio_tree_iter iter;
int referenced = 0;
/*
@@ -846,7 +845,7 @@ static int page_referenced_file(struct page *page,
*/
mapcount = page_mapcount(page);
- 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;
@@ -945,13 +944,12 @@ static int page_mkclean_file(struct address_space *mapping, struct page *page)
{
pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
struct vm_area_struct *vma;
- struct prio_tree_iter iter;
int ret = 0;
BUG_ON(PageAnon(page));
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) {
if (vma->vm_flags & VM_SHARED) {
unsigned long address = vma_address(page, vma);
if (address == -EFAULT)
@@ -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);
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;
@@ -1576,7 +1573,7 @@ static int try_to_unmap_file(struct page *page, enum ttu_flags flags)
goto out;
list_for_each_entry(vma, &mapping->i_mmap_nonlinear,
- shared.vm_set.list) {
+ shared.nonlinear) {
cursor = (unsigned long) vma->vm_private_data;
if (cursor > max_nl_cursor)
max_nl_cursor = cursor;
@@ -1608,7 +1605,7 @@ static int try_to_unmap_file(struct page *page, enum ttu_flags flags)
do {
list_for_each_entry(vma, &mapping->i_mmap_nonlinear,
- shared.vm_set.list) {
+ shared.nonlinear) {
cursor = (unsigned long) vma->vm_private_data;
while ( cursor < max_nl_cursor &&
cursor < vma->vm_end - vma->vm_start) {
@@ -1631,7 +1628,7 @@ static int try_to_unmap_file(struct page *page, enum ttu_flags flags)
* in locked vmas). Reset cursor on all unreserved nonlinear
* vmas, now forgetting on which ones it had fallen behind.
*/
- list_for_each_entry(vma, &mapping->i_mmap_nonlinear, shared.vm_set.list)
+ list_for_each_entry(vma, &mapping->i_mmap_nonlinear, shared.nonlinear)
vma->vm_private_data = NULL;
out:
mutex_unlock(&mapping->i_mmap_mutex);
@@ -1748,13 +1745,12 @@ static int rmap_walk_file(struct page *page, int (*rmap_one)(struct page *,
struct address_space *mapping = page->mapping;
pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
struct vm_area_struct *vma;
- struct prio_tree_iter iter;
int ret = SWAP_AGAIN;
if (!mapping)
return ret;
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;
--
1.7.7.3
^ permalink raw reply related [flat|nested] 18+ messages in thread
* [PATCH 3/5] kmemleak: use rbtree instead of prio tree
2012-08-07 7:25 [PATCH 0/5] rbtree based interval tree as a prio_tree replacement Michel Lespinasse
2012-08-07 7:25 ` [PATCH 1/5] rbtree: add prio tree and interval tree tests Michel Lespinasse
2012-08-07 7:25 ` [PATCH 2/5] mm: replace vma prio_tree with an interval tree Michel Lespinasse
@ 2012-08-07 7:25 ` Michel Lespinasse
2012-08-08 17:07 ` Michel Lespinasse
2012-08-07 7:25 ` [PATCH 4/5] prio_tree: remove Michel Lespinasse
` (3 subsequent siblings)
6 siblings, 1 reply; 18+ messages in thread
From: Michel Lespinasse @ 2012-08-07 7:25 UTC (permalink / raw)
To: riel, peterz, vrajesh, daniel.santos, aarcange, dwmw2, akpm
Cc: linux-mm, linux-kernel, torvalds
kmemleak uses a tree where each node represents an allocated memory object
in order to quickly find out what object a given address is part of.
However, the objects don't overlap, so rbtrees are a better choice than
prio tree for this use. They are both faster and have lower memory overhead.
Tested by booting a kernel with kmemleak enabled, loading the kmemleak_test
module, and looking for the expected messages.
Signed-off-by: Michel Lespinasse <walken@google.com>
---
mm/kmemleak.c | 98 +++++++++++++++++++++++++++++----------------------------
1 files changed, 50 insertions(+), 48 deletions(-)
diff --git a/mm/kmemleak.c b/mm/kmemleak.c
index 45eb621..8de1b09 100644
--- a/mm/kmemleak.c
+++ b/mm/kmemleak.c
@@ -29,7 +29,7 @@
* - kmemleak_lock (rwlock): protects the object_list modifications and
* accesses to the object_tree_root. The object_list is the main list
* holding the metadata (struct kmemleak_object) for the allocated memory
- * blocks. The object_tree_root is a priority search tree used to look-up
+ * blocks. The object_tree_root is a red black tree used to look-up
* metadata based on a pointer to the corresponding memory block. The
* kmemleak_object structures are added to the object_list and
* object_tree_root in the create_object() function called from the
@@ -71,7 +71,7 @@
#include <linux/delay.h>
#include <linux/export.h>
#include <linux/kthread.h>
-#include <linux/prio_tree.h>
+#include <linux/rbtree.h>
#include <linux/fs.h>
#include <linux/debugfs.h>
#include <linux/seq_file.h>
@@ -132,7 +132,7 @@ struct kmemleak_scan_area {
* Structure holding the metadata for each allocated memory block.
* Modifications to such objects should be made while holding the
* object->lock. Insertions or deletions from object_list, gray_list or
- * tree_node are already protected by the corresponding locks or mutex (see
+ * rb_node are already protected by the corresponding locks or mutex (see
* the notes on locking above). These objects are reference-counted
* (use_count) and freed using the RCU mechanism.
*/
@@ -141,7 +141,7 @@ struct kmemleak_object {
unsigned long flags; /* object status flags */
struct list_head object_list;
struct list_head gray_list;
- struct prio_tree_node tree_node;
+ struct rb_node rb_node;
struct rcu_head rcu; /* object_list lockless traversal */
/* object usage count; object freed when use_count == 0 */
atomic_t use_count;
@@ -182,9 +182,9 @@ struct kmemleak_object {
static LIST_HEAD(object_list);
/* the list of gray-colored objects (see color_gray comment below) */
static LIST_HEAD(gray_list);
-/* prio search tree for object boundaries */
-static struct prio_tree_root object_tree_root;
-/* rw_lock protecting the access to object_list and prio_tree_root */
+/* search tree for object boundaries */
+static struct rb_root object_tree_root = RB_ROOT;
+/* rw_lock protecting the access to object_list and object_tree_root */
static DEFINE_RWLOCK(kmemleak_lock);
/* allocation caches for kmemleak internal data */
@@ -380,7 +380,7 @@ static void dump_object_info(struct kmemleak_object *object)
trace.entries = object->trace;
pr_notice("Object 0x%08lx (size %zu):\n",
- object->tree_node.start, object->size);
+ object->pointer, object->size);
pr_notice(" comm \"%s\", pid %d, jiffies %lu\n",
object->comm, object->pid, object->jiffies);
pr_notice(" min_count = %d\n", object->min_count);
@@ -392,32 +392,32 @@ static void dump_object_info(struct kmemleak_object *object)
}
/*
- * Look-up a memory block metadata (kmemleak_object) in the priority search
+ * Look-up a memory block metadata (kmemleak_object) in the object search
* tree based on a pointer value. If alias is 0, only values pointing to the
* beginning of the memory block are allowed. The kmemleak_lock must be held
* when calling this function.
*/
static struct kmemleak_object *lookup_object(unsigned long ptr, int alias)
{
- struct prio_tree_node *node;
- struct prio_tree_iter iter;
- struct kmemleak_object *object;
-
- prio_tree_iter_init(&iter, &object_tree_root, ptr, ptr);
- node = prio_tree_next(&iter);
- if (node) {
- object = prio_tree_entry(node, struct kmemleak_object,
- tree_node);
- if (!alias && object->pointer != ptr) {
+ struct rb_node *rb = object_tree_root.rb_node;
+
+ while (rb) {
+ struct kmemleak_object *object =
+ rb_entry(rb, struct kmemleak_object, rb_node);
+ if (ptr < object->pointer)
+ rb = object->rb_node.rb_left;
+ else if (object->pointer + object->size <= ptr)
+ rb = object->rb_node.rb_right;
+ else if (object->pointer == ptr || alias)
+ return object;
+ else {
kmemleak_warn("Found object by alias at 0x%08lx\n",
ptr);
dump_object_info(object);
- object = NULL;
+ break;
}
- } else
- object = NULL;
-
- return object;
+ }
+ return NULL;
}
/*
@@ -471,7 +471,7 @@ static void put_object(struct kmemleak_object *object)
}
/*
- * Look up an object in the prio search tree and increase its use_count.
+ * Look up an object in the object search tree and increase its use_count.
*/
static struct kmemleak_object *find_and_get_object(unsigned long ptr, int alias)
{
@@ -516,8 +516,8 @@ static struct kmemleak_object *create_object(unsigned long ptr, size_t size,
int min_count, gfp_t gfp)
{
unsigned long flags;
- struct kmemleak_object *object;
- struct prio_tree_node *node;
+ struct kmemleak_object *object, *parent;
+ struct rb_node **link, *rb_parent;
object = kmem_cache_alloc(object_cache, gfp_kmemleak_mask(gfp));
if (!object) {
@@ -560,31 +560,34 @@ static struct kmemleak_object *create_object(unsigned long ptr, size_t size,
/* kernel backtrace */
object->trace_len = __save_stack_trace(object->trace);
- INIT_PRIO_TREE_NODE(&object->tree_node);
- object->tree_node.start = ptr;
- object->tree_node.last = ptr + size - 1;
-
write_lock_irqsave(&kmemleak_lock, flags);
min_addr = min(min_addr, ptr);
max_addr = max(max_addr, ptr + size);
- node = prio_tree_insert(&object_tree_root, &object->tree_node);
- /*
- * The code calling the kernel does not yet have the pointer to the
- * memory block to be able to free it. However, we still hold the
- * kmemleak_lock here in case parts of the kernel started freeing
- * random memory blocks.
- */
- if (node != &object->tree_node) {
- kmemleak_stop("Cannot insert 0x%lx into the object search tree "
- "(already existing)\n", ptr);
- object = lookup_object(ptr, 1);
- spin_lock(&object->lock);
- dump_object_info(object);
- spin_unlock(&object->lock);
- goto out;
+ link = &object_tree_root.rb_node;
+ rb_parent = NULL;
+ while (*link) {
+ rb_parent = *link;
+ parent = rb_entry(rb_parent, struct kmemleak_object, rb_node);
+ if (ptr + size <= parent->pointer)
+ link = &parent->rb_node.rb_left;
+ else if (parent->pointer + parent->size <= ptr)
+ link = &parent->rb_node.rb_right;
+ else {
+ kmemleak_stop("Cannot insert 0x%lx into the object "
+ "search tree (overlaps existing)\n",
+ ptr);
+ object = parent;
+ spin_lock(&object->lock);
+ dump_object_info(object);
+ spin_unlock(&object->lock);
+ goto out;
+ }
}
+ rb_link_node(&object->rb_node, rb_parent, link);
+ rb_insert_color(&object->rb_node, &object_tree_root);
+
list_add_tail_rcu(&object->object_list, &object_list);
out:
write_unlock_irqrestore(&kmemleak_lock, flags);
@@ -600,7 +603,7 @@ static void __delete_object(struct kmemleak_object *object)
unsigned long flags;
write_lock_irqsave(&kmemleak_lock, flags);
- prio_tree_remove(&object_tree_root, &object->tree_node);
+ rb_erase(&object->rb_node, &object_tree_root);
list_del_rcu(&object->object_list);
write_unlock_irqrestore(&kmemleak_lock, flags);
@@ -1768,7 +1771,6 @@ void __init kmemleak_init(void)
object_cache = KMEM_CACHE(kmemleak_object, SLAB_NOLEAKTRACE);
scan_area_cache = KMEM_CACHE(kmemleak_scan_area, SLAB_NOLEAKTRACE);
- INIT_PRIO_TREE_ROOT(&object_tree_root);
if (crt_early_log >= ARRAY_SIZE(early_log))
pr_warning("Early log buffer exceeded (%d), please increase "
--
1.7.7.3
^ permalink raw reply related [flat|nested] 18+ messages in thread
* [PATCH 4/5] prio_tree: remove
2012-08-07 7:25 [PATCH 0/5] rbtree based interval tree as a prio_tree replacement Michel Lespinasse
` (2 preceding siblings ...)
2012-08-07 7:25 ` [PATCH 3/5] kmemleak: use rbtree instead of prio tree Michel Lespinasse
@ 2012-08-07 7:25 ` Michel Lespinasse
2012-08-07 7:25 ` [PATCH 5/5] rbtree: move augmented rbtree functionality to rbtree_augmented.h Michel Lespinasse
` (2 subsequent siblings)
6 siblings, 0 replies; 18+ messages in thread
From: Michel Lespinasse @ 2012-08-07 7:25 UTC (permalink / raw)
To: riel, peterz, vrajesh, daniel.santos, aarcange, dwmw2, akpm
Cc: linux-mm, linux-kernel, torvalds
After both prio_tree users have been converted to use red-black trees,
there is no need to keep around the prio tree library anymore.
Signed-off-by: Michel Lespinasse <walken@google.com>
---
Documentation/00-INDEX | 2 -
Documentation/prio_tree.txt | 107 ----------
include/linux/prio_tree.h | 120 ------------
init/main.c | 2 -
lib/Kconfig.debug | 6 -
lib/Makefile | 3 +-
lib/prio_tree.c | 455 -------------------------------------------
lib/prio_tree_test.c | 106 ----------
8 files changed, 1 insertions(+), 800 deletions(-)
delete mode 100644 Documentation/prio_tree.txt
delete mode 100644 include/linux/prio_tree.h
delete mode 100644 lib/prio_tree.c
delete mode 100644 lib/prio_tree_test.c
diff --git a/Documentation/00-INDEX b/Documentation/00-INDEX
index 49c0513..f54273e 100644
--- a/Documentation/00-INDEX
+++ b/Documentation/00-INDEX
@@ -270,8 +270,6 @@ preempt-locking.txt
- info on locking under a preemptive kernel.
printk-formats.txt
- how to get printk format specifiers right
-prio_tree.txt
- - info on radix-priority-search-tree use for indexing vmas.
ramoops.txt
- documentation of the ramoops oops/panic logging module.
rbtree.txt
diff --git a/Documentation/prio_tree.txt b/Documentation/prio_tree.txt
deleted file mode 100644
index 3aa68f9..0000000
--- a/Documentation/prio_tree.txt
+++ /dev/null
@@ -1,107 +0,0 @@
-The prio_tree.c code indexes vmas using 3 different indexes:
- * heap_index = vm_pgoff + vm_size_in_pages : end_vm_pgoff
- * radix_index = vm_pgoff : start_vm_pgoff
- * size_index = vm_size_in_pages
-
-A regular radix-priority-search-tree indexes vmas using only heap_index and
-radix_index. The conditions for indexing are:
- * ->heap_index >= ->left->heap_index &&
- ->heap_index >= ->right->heap_index
- * if (->heap_index == ->left->heap_index)
- then ->radix_index < ->left->radix_index;
- * if (->heap_index == ->right->heap_index)
- then ->radix_index < ->right->radix_index;
- * nodes are hashed to left or right subtree using radix_index
- similar to a pure binary radix tree.
-
-A regular radix-priority-search-tree helps to store and query
-intervals (vmas). However, a regular radix-priority-search-tree is only
-suitable for storing vmas with different radix indices (vm_pgoff).
-
-Therefore, the prio_tree.c extends the regular radix-priority-search-tree
-to handle many vmas with the same vm_pgoff. Such vmas are handled in
-2 different ways: 1) All vmas with the same radix _and_ heap indices are
-linked using vm_set.list, 2) if there are many vmas with the same radix
-index, but different heap indices and if the regular radix-priority-search
-tree cannot index them all, we build an overflow-sub-tree that indexes such
-vmas using heap and size indices instead of heap and radix indices. For
-example, in the figure below some vmas with vm_pgoff = 0 (zero) are
-indexed by regular radix-priority-search-tree whereas others are pushed
-into an overflow-subtree. Note that all vmas in an overflow-sub-tree have
-the same vm_pgoff (radix_index) and if necessary we build different
-overflow-sub-trees to handle each possible radix_index. For example,
-in figure we have 3 overflow-sub-trees corresponding to radix indices
-0, 2, and 4.
-
-In the final tree the first few (prio_tree_root->index_bits) levels
-are indexed using heap and radix indices whereas the overflow-sub-trees below
-those levels (i.e. levels prio_tree_root->index_bits + 1 and higher) are
-indexed using heap and size indices. In overflow-sub-trees the size_index
-is used for hashing the nodes to appropriate places.
-
-Now, an example prio_tree:
-
- vmas are represented [radix_index, size_index, heap_index]
- i.e., [start_vm_pgoff, vm_size_in_pages, end_vm_pgoff]
-
-level prio_tree_root->index_bits = 3
------
- _
- 0 [0,7,7] |
- / \ |
- ------------------ ------------ | Regular
- / \ | radix priority
- 1 [1,6,7] [4,3,7] | search tree
- / \ / \ |
- ------- ----- ------ ----- | heap-and-radix
- / \ / \ | indexed
- 2 [0,6,6] [2,5,7] [5,2,7] [6,1,7] |
- / \ / \ / \ / \ |
- 3 [0,5,5] [1,5,6] [2,4,6] [3,4,7] [4,2,6] [5,1,6] [6,0,6] [7,0,7] |
- / / / _
- / / / _
- 4 [0,4,4] [2,3,5] [4,1,5] |
- / / / |
- 5 [0,3,3] [2,2,4] [4,0,4] | Overflow-sub-trees
- / / |
- 6 [0,2,2] [2,1,3] | heap-and-size
- / / | indexed
- 7 [0,1,1] [2,0,2] |
- / |
- 8 [0,0,0] |
- _
-
-Note that we use prio_tree_root->index_bits to optimize the height
-of the heap-and-radix indexed tree. Since prio_tree_root->index_bits is
-set according to the maximum end_vm_pgoff mapped, we are sure that all
-bits (in vm_pgoff) above prio_tree_root->index_bits are 0 (zero). Therefore,
-we only use the first prio_tree_root->index_bits as radix_index.
-Whenever index_bits is increased in prio_tree_expand, we shuffle the tree
-to make sure that the first prio_tree_root->index_bits levels of the tree
-is indexed properly using heap and radix indices.
-
-We do not optimize the height of overflow-sub-trees using index_bits.
-The reason is: there can be many such overflow-sub-trees and all of
-them have to be suffled whenever the index_bits increases. This may involve
-walking the whole prio_tree in prio_tree_insert->prio_tree_expand code
-path which is not desirable. Hence, we do not optimize the height of the
-heap-and-size indexed overflow-sub-trees using prio_tree->index_bits.
-Instead the overflow sub-trees are indexed using full BITS_PER_LONG bits
-of size_index. This may lead to skewed sub-trees because most of the
-higher significant bits of the size_index are likely to be 0 (zero). In
-the example above, all 3 overflow-sub-trees are skewed. This may marginally
-affect the performance. However, processes rarely map many vmas with the
-same start_vm_pgoff but different end_vm_pgoffs. Therefore, we normally
-do not require overflow-sub-trees to index all vmas.
-
-From the above discussion it is clear that the maximum height of
-a prio_tree can be prio_tree_root->index_bits + BITS_PER_LONG.
-However, in most of the common cases we do not need overflow-sub-trees,
-so the tree height in the common cases will be prio_tree_root->index_bits.
-
-It is fair to mention here that the prio_tree_root->index_bits
-is increased on demand, however, the index_bits is not decreased when
-vmas are removed from the prio_tree. That's tricky to do. Hence, it's
-left as a home work problem.
-
-
diff --git a/include/linux/prio_tree.h b/include/linux/prio_tree.h
deleted file mode 100644
index db04abb..0000000
--- a/include/linux/prio_tree.h
+++ /dev/null
@@ -1,120 +0,0 @@
-#ifndef _LINUX_PRIO_TREE_H
-#define _LINUX_PRIO_TREE_H
-
-/*
- * K&R 2nd ed. A8.3 somewhat obliquely hints that initial sequences of struct
- * fields with identical types should end up at the same location. We'll use
- * this until we can scrap struct raw_prio_tree_node.
- *
- * Note: all this could be done more elegantly by using unnamed union/struct
- * fields. However, gcc 2.95.3 and apparently also gcc 3.0.4 don't support this
- * language extension.
- */
-
-struct raw_prio_tree_node {
- struct prio_tree_node *left;
- struct prio_tree_node *right;
- struct prio_tree_node *parent;
-};
-
-struct prio_tree_node {
- struct prio_tree_node *left;
- struct prio_tree_node *right;
- struct prio_tree_node *parent;
- unsigned long start;
- unsigned long last; /* last location _in_ interval */
-};
-
-struct prio_tree_root {
- struct prio_tree_node *prio_tree_node;
- unsigned short index_bits;
- unsigned short raw;
- /*
- * 0: nodes are of type struct prio_tree_node
- * 1: nodes are of type raw_prio_tree_node
- */
-};
-
-struct prio_tree_iter {
- struct prio_tree_node *cur;
- 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;
- iter->cur = NULL;
-}
-
-#define __INIT_PRIO_TREE_ROOT(ptr, _raw) \
-do { \
- (ptr)->prio_tree_node = NULL; \
- (ptr)->index_bits = 1; \
- (ptr)->raw = (_raw); \
-} while (0)
-
-#define INIT_PRIO_TREE_ROOT(ptr) __INIT_PRIO_TREE_ROOT(ptr, 0)
-#define INIT_RAW_PRIO_TREE_ROOT(ptr) __INIT_PRIO_TREE_ROOT(ptr, 1)
-
-#define INIT_PRIO_TREE_NODE(ptr) \
-do { \
- (ptr)->left = (ptr)->right = (ptr)->parent = (ptr); \
-} while (0)
-
-#define INIT_PRIO_TREE_ITER(ptr) \
-do { \
- (ptr)->cur = NULL; \
- (ptr)->mask = 0UL; \
- (ptr)->value = 0UL; \
- (ptr)->size_level = 0; \
-} while (0)
-
-#define prio_tree_entry(ptr, type, member) \
- ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
-
-static inline int prio_tree_empty(const struct prio_tree_root *root)
-{
- return root->prio_tree_node == NULL;
-}
-
-static inline int prio_tree_root(const struct prio_tree_node *node)
-{
- return node->parent == node;
-}
-
-static inline int prio_tree_left_empty(const struct prio_tree_node *node)
-{
- return node->left == node;
-}
-
-static inline int prio_tree_right_empty(const struct prio_tree_node *node)
-{
- return node->right == node;
-}
-
-
-struct prio_tree_node *prio_tree_replace(struct prio_tree_root *root,
- struct prio_tree_node *old, struct prio_tree_node *node);
-struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root,
- struct prio_tree_node *node);
-void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node);
-struct prio_tree_node *prio_tree_next(struct prio_tree_iter *iter);
-
-#define raw_prio_tree_replace(root, old, node) \
- prio_tree_replace(root, (struct prio_tree_node *) (old), \
- (struct prio_tree_node *) (node))
-#define raw_prio_tree_insert(root, node) \
- prio_tree_insert(root, (struct prio_tree_node *) (node))
-#define raw_prio_tree_remove(root, node) \
- prio_tree_remove(root, (struct prio_tree_node *) (node))
-
-#endif /* _LINUX_PRIO_TREE_H */
diff --git a/init/main.c b/init/main.c
index b5cc0a7..04fad8c 100644
--- a/init/main.c
+++ b/init/main.c
@@ -85,7 +85,6 @@ extern void init_IRQ(void);
extern void fork_init(unsigned long);
extern void mca_init(void);
extern void sbus_init(void);
-extern void prio_tree_init(void);
extern void radix_tree_init(void);
#ifndef CONFIG_DEBUG_RODATA
static inline void mark_rodata_ro(void) { }
@@ -546,7 +545,6 @@ asmlinkage void __init start_kernel(void)
/* init some links before init_ISA_irqs() */
early_irq_init();
init_IRQ();
- prio_tree_init();
init_timers();
hrtimers_init();
softirq_init();
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 331c64d..eba4b09 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1185,12 +1185,6 @@ config RBTREE_TEST
A benchmark measuring the performance of the rbtree library.
Also includes rbtree invariant checks.
-config PRIO_TREE_TEST
- tristate "Prio tree test"
- depends on m && DEBUG_KERNEL
- help
- A benchmark measuring the performance of the prio tree library
-
config INTERVAL_TREE_TEST
tristate "Interval tree test"
depends on m && DEBUG_KERNEL
diff --git a/lib/Makefile b/lib/Makefile
index e1f109f..eb0e62b 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -9,7 +9,7 @@ endif
lib-y := ctype.o string.o vsprintf.o cmdline.o \
rbtree.o radix-tree.o dump_stack.o timerqueue.o\
- idr.o int_sqrt.o extable.o prio_tree.o \
+ idr.o int_sqrt.o extable.o \
sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \
proportions.o prio_heap.o ratelimit.o show_mem.o \
is_single_threaded.o plist.o decompress.o
@@ -131,7 +131,6 @@ obj-$(CONFIG_GENERIC_STRNLEN_USER) += strnlen_user.o
obj-$(CONFIG_STMP_DEVICE) += stmp_device.o
obj-$(CONFIG_RBTREE_TEST) += rbtree_test.o
-obj-$(CONFIG_PRIO_TREE_TEST) += prio_tree_test.o
obj-$(CONFIG_INTERVAL_TREE_TEST) += interval_tree_test.o
interval_tree_test-objs := interval_tree_test_main.o interval_tree.o
diff --git a/lib/prio_tree.c b/lib/prio_tree.c
deleted file mode 100644
index bba3714..0000000
--- a/lib/prio_tree.c
+++ /dev/null
@@ -1,455 +0,0 @@
-/*
- * lib/prio_tree.c - priority search tree
- *
- * Copyright (C) 2004, Rajesh Venkatasubramanian <vrajesh@umich.edu>
- *
- * This file is released under the GPL v2.
- *
- * Based on the radix priority search tree proposed by Edward M. McCreight
- * SIAM Journal of Computing, vol. 14, no.2, pages 257-276, May 1985
- *
- * 02Feb2004 Initial version
- */
-
-#include <linux/init.h>
-#include <linux/mm.h>
-#include <linux/prio_tree.h>
-#include <linux/export.h>
-
-/*
- * A clever mix of heap and radix trees forms a radix priority search tree (PST)
- * which is useful for storing intervals, e.g, we can consider a vma as a closed
- * interval of file pages [offset_begin, offset_end], and store all vmas that
- * map a file in a PST. Then, using the PST, we can answer a stabbing query,
- * i.e., selecting a set of stored intervals (vmas) that overlap with (map) a
- * given input interval X (a set of consecutive file pages), in "O(log n + m)"
- * time where 'log n' is the height of the PST, and 'm' is the number of stored
- * intervals (vmas) that overlap (map) with the input interval X (the set of
- * consecutive file pages).
- *
- * In our implementation, we store closed intervals of the form [radix_index,
- * heap_index]. We assume that always radix_index <= heap_index. McCreight's PST
- * is designed for storing intervals with unique radix indices, i.e., each
- * interval have different radix_index. However, this limitation can be easily
- * overcome by using the size, i.e., heap_index - radix_index, as part of the
- * index, so we index the tree using [(radix_index,size), heap_index].
- *
- * When the above-mentioned indexing scheme is used, theoretically, in a 32 bit
- * machine, the maximum height of a PST can be 64. We can use a balanced version
- * of the priority search tree to optimize the tree height, but the balanced
- * tree proposed by McCreight is too complex and memory-hungry for our purpose.
- */
-
-/*
- * The following macros are used for implementing prio_tree for i_mmap
- */
-
-static void get_index(const struct prio_tree_root *root,
- const struct prio_tree_node *node,
- unsigned long *radix, unsigned long *heap)
-{
- *radix = node->start;
- *heap = node->last;
-}
-
-static unsigned long index_bits_to_maxindex[BITS_PER_LONG];
-
-void __init prio_tree_init(void)
-{
- unsigned int i;
-
- for (i = 0; i < ARRAY_SIZE(index_bits_to_maxindex) - 1; i++)
- index_bits_to_maxindex[i] = (1UL << (i + 1)) - 1;
- index_bits_to_maxindex[ARRAY_SIZE(index_bits_to_maxindex) - 1] = ~0UL;
-}
-
-/*
- * Maximum heap_index that can be stored in a PST with index_bits bits
- */
-static inline unsigned long prio_tree_maxindex(unsigned int bits)
-{
- return index_bits_to_maxindex[bits - 1];
-}
-
-static void prio_set_parent(struct prio_tree_node *parent,
- struct prio_tree_node *child, bool left)
-{
- if (left)
- parent->left = child;
- else
- parent->right = child;
-
- child->parent = parent;
-}
-
-/*
- * Extend a priority search tree so that it can store a node with heap_index
- * max_heap_index. In the worst case, this algorithm takes O((log n)^2).
- * However, this function is used rarely and the common case performance is
- * not bad.
- */
-static struct prio_tree_node *prio_tree_expand(struct prio_tree_root *root,
- struct prio_tree_node *node, unsigned long max_heap_index)
-{
- struct prio_tree_node *prev;
-
- if (max_heap_index > prio_tree_maxindex(root->index_bits))
- root->index_bits++;
-
- prev = node;
- INIT_PRIO_TREE_NODE(node);
-
- while (max_heap_index > prio_tree_maxindex(root->index_bits)) {
- struct prio_tree_node *tmp = root->prio_tree_node;
-
- root->index_bits++;
-
- if (prio_tree_empty(root))
- continue;
-
- prio_tree_remove(root, root->prio_tree_node);
- INIT_PRIO_TREE_NODE(tmp);
-
- prio_set_parent(prev, tmp, true);
- prev = tmp;
- }
-
- if (!prio_tree_empty(root))
- prio_set_parent(prev, root->prio_tree_node, true);
-
- root->prio_tree_node = node;
- return node;
-}
-
-/*
- * Replace a prio_tree_node with a new node and return the old node
- */
-struct prio_tree_node *prio_tree_replace(struct prio_tree_root *root,
- struct prio_tree_node *old, struct prio_tree_node *node)
-{
- INIT_PRIO_TREE_NODE(node);
-
- if (prio_tree_root(old)) {
- BUG_ON(root->prio_tree_node != old);
- /*
- * We can reduce root->index_bits here. However, it is complex
- * and does not help much to improve performance (IMO).
- */
- root->prio_tree_node = node;
- } else
- prio_set_parent(old->parent, node, old->parent->left == old);
-
- if (!prio_tree_left_empty(old))
- prio_set_parent(node, old->left, true);
-
- if (!prio_tree_right_empty(old))
- prio_set_parent(node, old->right, false);
-
- return old;
-}
-
-/*
- * Insert a prio_tree_node @node into a radix priority search tree @root. The
- * algorithm typically takes O(log n) time where 'log n' is the number of bits
- * required to represent the maximum heap_index. In the worst case, the algo
- * can take O((log n)^2) - check prio_tree_expand.
- *
- * If a prior node with same radix_index and heap_index is already found in
- * the tree, then returns the address of the prior node. Otherwise, inserts
- * @node into the tree and returns @node.
- */
-struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root,
- struct prio_tree_node *node)
-{
- struct prio_tree_node *cur, *res = node;
- unsigned long radix_index, heap_index;
- unsigned long r_index, h_index, index, mask;
- int size_flag = 0;
-
- get_index(root, node, &radix_index, &heap_index);
-
- if (prio_tree_empty(root) ||
- heap_index > prio_tree_maxindex(root->index_bits))
- return prio_tree_expand(root, node, heap_index);
-
- cur = root->prio_tree_node;
- mask = 1UL << (root->index_bits - 1);
-
- while (mask) {
- get_index(root, cur, &r_index, &h_index);
-
- if (r_index == radix_index && h_index == heap_index)
- return cur;
-
- if (h_index < heap_index ||
- (h_index == heap_index && r_index > radix_index)) {
- struct prio_tree_node *tmp = node;
- node = prio_tree_replace(root, cur, node);
- cur = tmp;
- /* swap indices */
- index = r_index;
- r_index = radix_index;
- radix_index = index;
- index = h_index;
- h_index = heap_index;
- heap_index = index;
- }
-
- if (size_flag)
- index = heap_index - radix_index;
- else
- index = radix_index;
-
- if (index & mask) {
- if (prio_tree_right_empty(cur)) {
- INIT_PRIO_TREE_NODE(node);
- prio_set_parent(cur, node, false);
- return res;
- } else
- cur = cur->right;
- } else {
- if (prio_tree_left_empty(cur)) {
- INIT_PRIO_TREE_NODE(node);
- prio_set_parent(cur, node, true);
- return res;
- } else
- cur = cur->left;
- }
-
- mask >>= 1;
-
- if (!mask) {
- mask = 1UL << (BITS_PER_LONG - 1);
- size_flag = 1;
- }
- }
- /* Should not reach here */
- BUG();
- return NULL;
-}
-EXPORT_SYMBOL(prio_tree_insert);
-
-/*
- * Remove a prio_tree_node @node from a radix priority search tree @root. The
- * algorithm takes O(log n) time where 'log n' is the number of bits required
- * to represent the maximum heap_index.
- */
-void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node)
-{
- struct prio_tree_node *cur;
- unsigned long r_index, h_index_right, h_index_left;
-
- cur = node;
-
- while (!prio_tree_left_empty(cur) || !prio_tree_right_empty(cur)) {
- if (!prio_tree_left_empty(cur))
- get_index(root, cur->left, &r_index, &h_index_left);
- else {
- cur = cur->right;
- continue;
- }
-
- if (!prio_tree_right_empty(cur))
- get_index(root, cur->right, &r_index, &h_index_right);
- else {
- cur = cur->left;
- continue;
- }
-
- /* both h_index_left and h_index_right cannot be 0 */
- if (h_index_left >= h_index_right)
- cur = cur->left;
- else
- cur = cur->right;
- }
-
- if (prio_tree_root(cur)) {
- BUG_ON(root->prio_tree_node != cur);
- __INIT_PRIO_TREE_ROOT(root, root->raw);
- return;
- }
-
- if (cur->parent->right == cur)
- cur->parent->right = cur->parent;
- else
- cur->parent->left = cur->parent;
-
- while (cur != node)
- cur = prio_tree_replace(root, cur->parent, cur);
-}
-EXPORT_SYMBOL(prio_tree_remove);
-
-static void iter_walk_down(struct prio_tree_iter *iter)
-{
- iter->mask >>= 1;
- if (iter->mask) {
- if (iter->size_level)
- iter->size_level++;
- return;
- }
-
- if (iter->size_level) {
- BUG_ON(!prio_tree_left_empty(iter->cur));
- BUG_ON(!prio_tree_right_empty(iter->cur));
- iter->size_level++;
- iter->mask = ULONG_MAX;
- } else {
- iter->size_level = 1;
- iter->mask = 1UL << (BITS_PER_LONG - 1);
- }
-}
-
-static void iter_walk_up(struct prio_tree_iter *iter)
-{
- if (iter->mask == ULONG_MAX)
- iter->mask = 1UL;
- else if (iter->size_level == 1)
- iter->mask = 1UL;
- else
- iter->mask <<= 1;
- if (iter->size_level)
- iter->size_level--;
- if (!iter->size_level && (iter->value & iter->mask))
- iter->value ^= iter->mask;
-}
-
-/*
- * Following functions help to enumerate all prio_tree_nodes in the tree that
- * overlap with the input interval X [radix_index, heap_index]. The enumeration
- * takes O(log n + m) time where 'log n' is the height of the tree (which is
- * proportional to # of bits required to represent the maximum heap_index) and
- * 'm' is the number of prio_tree_nodes that overlap the interval X.
- */
-
-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))
- return NULL;
-
- get_index(iter->root, iter->cur->left, r_index, h_index);
-
- if (iter->r_index <= *h_index) {
- iter->cur = iter->cur->left;
- iter_walk_down(iter);
- return iter->cur;
- }
-
- return NULL;
-}
-
-static struct prio_tree_node *prio_tree_right(struct prio_tree_iter *iter,
- unsigned long *r_index, unsigned long *h_index)
-{
- unsigned long value;
-
- if (prio_tree_right_empty(iter->cur))
- return NULL;
-
- if (iter->size_level)
- value = iter->value;
- else
- value = iter->value | iter->mask;
-
- if (iter->h_index < value)
- return NULL;
-
- get_index(iter->root, iter->cur->right, r_index, h_index);
-
- if (iter->r_index <= *h_index) {
- iter->cur = iter->cur->right;
- iter_walk_down(iter);
- return iter->cur;
- }
-
- return NULL;
-}
-
-static struct prio_tree_node *prio_tree_parent(struct prio_tree_iter *iter)
-{
- iter->cur = iter->cur->parent;
- iter_walk_up(iter);
- return iter->cur;
-}
-
-static inline int overlap(struct prio_tree_iter *iter,
- unsigned long r_index, unsigned long h_index)
-{
- return iter->h_index >= r_index && iter->r_index <= h_index;
-}
-
-/*
- * prio_tree_first:
- *
- * Get the first prio_tree_node that overlaps with the interval [radix_index,
- * 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_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, root->prio_tree_node, &r_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(iter, r_index, h_index))
- return iter->cur;
-
- if (prio_tree_left(iter, &r_index, &h_index))
- continue;
-
- if (prio_tree_right(iter, &r_index, &h_index))
- continue;
-
- break;
- }
- return NULL;
-}
-
-/*
- * prio_tree_next:
- *
- * Get the next prio_tree_node that overlaps with the input interval in iter
- */
-struct prio_tree_node *prio_tree_next(struct prio_tree_iter *iter)
-{
- unsigned long r_index, h_index;
-
- if (iter->cur == NULL)
- return prio_tree_first(iter);
-
-repeat:
- while (prio_tree_left(iter, &r_index, &h_index))
- if (overlap(iter, r_index, h_index))
- return iter->cur;
-
- 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);
-
- if (prio_tree_root(iter->cur))
- return NULL;
-
- prio_tree_parent(iter);
- }
-
- if (overlap(iter, r_index, h_index))
- return iter->cur;
-
- goto repeat;
-}
-EXPORT_SYMBOL(prio_tree_next);
diff --git a/lib/prio_tree_test.c b/lib/prio_tree_test.c
deleted file mode 100644
index c26084d..0000000
--- a/lib/prio_tree_test.c
+++ /dev/null
@@ -1,106 +0,0 @@
-#include <linux/module.h>
-#include <linux/prio_tree.h>
-#include <linux/random.h>
-#include <asm/timex.h>
-
-#define NODES 100
-#define PERF_LOOPS 100000
-#define SEARCHES 100
-#define SEARCH_LOOPS 10000
-
-static struct prio_tree_root root;
-static struct prio_tree_node nodes[NODES];
-static u32 queries[SEARCHES];
-
-static struct rnd_state rnd;
-
-static inline unsigned long
-search(unsigned long query, struct prio_tree_root *root)
-{
- struct prio_tree_iter iter;
- unsigned long results = 0;
-
- prio_tree_iter_init(&iter, root, query, query);
- while (prio_tree_next(&iter))
- results++;
- return results;
-}
-
-static void init(void)
-{
- int i;
- for (i = 0; i < NODES; i++) {
- u32 a = prandom32(&rnd), b = prandom32(&rnd);
- if (a <= b) {
- nodes[i].start = a;
- nodes[i].last = b;
- } else {
- nodes[i].start = b;
- nodes[i].last = a;
- }
- }
- for (i = 0; i < SEARCHES; i++)
- queries[i] = prandom32(&rnd);
-}
-
-static int prio_tree_test_init(void)
-{
- int i, j;
- unsigned long results;
- cycles_t time1, time2, time;
-
- printk(KERN_ALERT "prio tree insert/remove");
-
- prandom32_seed(&rnd, 3141592653589793238ULL);
- INIT_PRIO_TREE_ROOT(&root);
- init();
-
- time1 = get_cycles();
-
- for (i = 0; i < PERF_LOOPS; i++) {
- for (j = 0; j < NODES; j++)
- prio_tree_insert(&root, nodes + j);
- for (j = 0; j < NODES; j++)
- prio_tree_remove(&root, nodes + j);
- }
-
- time2 = get_cycles();
- time = time2 - time1;
-
- time = div_u64(time, PERF_LOOPS);
- printk(" -> %llu cycles\n", (unsigned long long)time);
-
- printk(KERN_ALERT "prio tree search");
-
- for (j = 0; j < NODES; j++)
- prio_tree_insert(&root, nodes + j);
-
- time1 = get_cycles();
-
- results = 0;
- for (i = 0; i < SEARCH_LOOPS; i++)
- for (j = 0; j < SEARCHES; j++)
- results += search(queries[j], &root);
-
- time2 = get_cycles();
- time = time2 - time1;
-
- time = div_u64(time, SEARCH_LOOPS);
- results = div_u64(results, SEARCH_LOOPS);
- printk(" -> %llu cycles (%lu results)\n",
- (unsigned long long)time, results);
-
- return -EAGAIN; /* Fail will directly unload the module */
-}
-
-static void prio_tree_test_exit(void)
-{
- printk(KERN_ALERT "test exit\n");
-}
-
-module_init(prio_tree_test_init)
-module_exit(prio_tree_test_exit)
-
-MODULE_LICENSE("GPL");
-MODULE_AUTHOR("Michel Lespinasse");
-MODULE_DESCRIPTION("Prio Tree test");
--
1.7.7.3
^ permalink raw reply related [flat|nested] 18+ messages in thread
* [PATCH 5/5] rbtree: move augmented rbtree functionality to rbtree_augmented.h
2012-08-07 7:25 [PATCH 0/5] rbtree based interval tree as a prio_tree replacement Michel Lespinasse
` (3 preceding siblings ...)
2012-08-07 7:25 ` [PATCH 4/5] prio_tree: remove Michel Lespinasse
@ 2012-08-07 7:25 ` Michel Lespinasse
2012-08-08 1:19 ` Michel Lespinasse
2012-08-13 8:20 ` [PATCH 0/5] rbtree based interval tree as a prio_tree replacement Peter Zijlstra
2012-08-30 21:34 ` Andrew Morton
6 siblings, 1 reply; 18+ messages in thread
From: Michel Lespinasse @ 2012-08-07 7:25 UTC (permalink / raw)
To: riel, peterz, vrajesh, daniel.santos, aarcange, dwmw2, akpm
Cc: linux-mm, linux-kernel, torvalds
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 <walken@google.com>
---
Documentation/rbtree.txt | 13 ++
arch/x86/mm/pat_rbtree.c | 2 +-
include/linux/interval_tree_tmpl.h | 8 +-
include/linux/rbtree.h | 48 --------
include/linux/rbtree_augmented.h | 223 ++++++++++++++++++++++++++++++++++++
lib/rbtree.c | 162 ++------------------------
lib/rbtree_test.c | 2 +-
7 files changed, 255 insertions(+), 203 deletions(-)
create mode 100644 include/linux/rbtree_augmented.h
diff --git a/Documentation/rbtree.txt b/Documentation/rbtree.txt
index 0a0b6dc..61b6c48 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 4d11695..415f6c4 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_tmpl.h b/include/linux/interval_tree_tmpl.h
index c65deda..c1aeb92 100644
--- a/include/linux/interval_tree_tmpl.h
+++ b/include/linux/interval_tree_tmpl.h
@@ -19,6 +19,8 @@
include/linux/interval_tree_tmpl.h
*/
+#include <linux/rbtree_augmented.h>
+
/*
* Template for implementing interval trees
*
@@ -57,7 +59,8 @@ static inline ITTYPE IT(compute_subtree_last)(ITSTRUCT *node)
return max;
}
-static void IT(augment_propagate)(struct rb_node *rb, struct rb_node *stop)
+static inline void
+IT(augment_propagate)(struct rb_node *rb, struct rb_node *stop)
{
while (rb != stop) {
ITSTRUCT *node = rb_entry(rb, ITSTRUCT, ITRB);
@@ -69,7 +72,8 @@ static void IT(augment_propagate)(struct rb_node *rb, struct rb_node *stop)
}
}
-static void IT(augment_copy)(struct rb_node *rb_old, struct rb_node *rb_new)
+static inline void
+IT(augment_copy)(struct rb_node *rb_old, struct rb_node *rb_new)
{
ITSTRUCT *old = rb_entry(rb_old, ITSTRUCT, ITRB);
ITSTRUCT *new = rb_entry(rb_new, ITSTRUCT, ITRB);
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 8d1e83b..0022c1b 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 *augment);
-static inline void
-rb_insert_augmented(struct rb_node *node, struct rb_root *root,
- const struct rb_augment_callbacks *augment)
-{
- __rb_insert_augmented(node, root, augment->rotate);
-}
-
-#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
- rbtype, rbaugmented, rbcompute) \
-static void rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
-{ \
- while (rb != stop) { \
- rbstruct *node = rb_entry(rb, rbstruct, rbfield); \
- rbtype augmented = rbcompute(node); \
- if (node->rbaugmented == augmented) \
- break; \
- node->rbaugmented = augmented; \
- rb = rb_parent(&node->rbfield); \
- } \
-} \
-static void rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
-{ \
- rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
- rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
- new->rbaugmented = old->rbaugmented; \
-} \
-static void rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
-{ \
- rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
- rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
- new->rbaugmented = old->rbaugmented; \
- old->rbaugmented = rbcompute(old); \
-} \
-rbstatic const struct rb_augment_callbacks rbname = { \
- rbname ## _propagate, rbname ## _copy, rbname ## _rotate \
-};
-
-
/* Find logical next and previous nodes in a tree */
extern struct rb_node *rb_next(const struct rb_node *);
extern struct rb_node *rb_prev(const struct rb_node *);
diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
new file mode 100644
index 0000000..214caa3
--- /dev/null
+++ b/include/linux/rbtree_augmented.h
@@ -0,0 +1,223 @@
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <andrea@suse.de>
+ (C) 2002 David Woodhouse <dwmw2@infradead.org>
+ (C) 2012 Michel Lespinasse <walken@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
+
+ linux/include/linux/rbtree_augmented.h
+*/
+
+#ifndef _LINUX_RBTREE_AUGMENTED_H
+#define _LINUX_RBTREE_AUGMENTED_H
+
+#include <linux/rbtree.h>
+
+/*
+ * Please note - only struct rb_augment_callbacks and the prototypes for
+ * rb_insert_augmented() and rb_erase_augmented() are intended to be public.
+ * The rest are implementation details you are not expected to depend on.
+ *
+ * See Documentation/rbtree.txt for documentation and samples.
+ */
+
+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));
+static inline void
+rb_insert_augmented(struct rb_node *node, struct rb_root *root,
+ const struct rb_augment_callbacks *augment)
+{
+ __rb_insert_augmented(node, root, augment->rotate);
+}
+
+#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
+ rbtype, rbaugmented, rbcompute) \
+static inline void \
+rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
+{ \
+ while (rb != stop) { \
+ rbstruct *node = rb_entry(rb, rbstruct, rbfield); \
+ rbtype augmented = rbcompute(node); \
+ if (node->rbaugmented == augmented) \
+ break; \
+ node->rbaugmented = augmented; \
+ rb = rb_parent(&node->rbfield); \
+ } \
+} \
+static inline void \
+rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
+{ \
+ rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
+ rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
+ new->rbaugmented = old->rbaugmented; \
+} \
+static void \
+rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
+{ \
+ rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
+ rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
+ new->rbaugmented = old->rbaugmented; \
+ old->rbaugmented = rbcompute(old); \
+} \
+rbstatic const struct rb_augment_callbacks rbname = { \
+ rbname ## _propagate, rbname ## _copy, rbname ## _rotate \
+};
+
+
+#define RB_RED 0
+#define RB_BLACK 1
+
+#define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
+
+#define __rb_color(pc) ((pc) & 1)
+#define __rb_is_black(pc) __rb_color(pc)
+#define __rb_is_red(pc) (!__rb_color(pc))
+#define rb_color(rb) __rb_color((rb)->__rb_parent_color)
+#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
+#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
+
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
+ rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
+}
+
+static inline void rb_set_parent_color(struct rb_node *rb,
+ struct rb_node *p, int color)
+{
+ rb->__rb_parent_color = (unsigned long)p | color;
+}
+
+static inline void
+__rb_change_child(struct rb_node *old, struct rb_node *new,
+ struct rb_node *parent, struct rb_root *root)
+{
+ if (parent) {
+ if (parent->rb_left == old)
+ parent->rb_left = new;
+ else
+ parent->rb_right = new;
+ } else
+ root->rb_node = new;
+}
+
+extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
+
+static __always_inline void
+rb_erase_augmented(struct rb_node *node, struct rb_root *root,
+ const struct rb_augment_callbacks *augment)
+{
+ struct rb_node *child = node->rb_right, *tmp = node->rb_left;
+ struct rb_node *parent, *rebalance;
+ unsigned long pc;
+
+ if (!tmp) {
+ /*
+ * Case 1: node to erase has no more than 1 child (easy!)
+ *
+ * Note that if there is one child it must be red due to 5)
+ * and node must be black due to 4). We adjust colors locally
+ * so as to bypass __rb_erase_color() later on.
+ */
+ pc = node->__rb_parent_color;
+ parent = __rb_parent(pc);
+ __rb_change_child(node, child, parent, root);
+ if (child) {
+ child->__rb_parent_color = pc;
+ rebalance = NULL;
+ } else
+ rebalance = __rb_is_black(pc) ? parent : NULL;
+ tmp = parent;
+ } else if (!child) {
+ /* Still case 1, but this time the child is node->rb_left */
+ tmp->__rb_parent_color = pc = node->__rb_parent_color;
+ parent = __rb_parent(pc);
+ __rb_change_child(node, tmp, parent, root);
+ rebalance = NULL;
+ tmp = parent;
+ } else {
+ struct rb_node *successor = child, *child2;
+ tmp = child->rb_left;
+ if (!tmp) {
+ /*
+ * Case 2: node's successor is its right child
+ *
+ * (n) (s)
+ * / \ / \
+ * (x) (s) -> (x) (c)
+ * \
+ * (c)
+ */
+ parent = successor;
+ child2 = successor->rb_right;
+ augment->copy(node, successor);
+ } else {
+ /*
+ * Case 3: node's successor is leftmost under
+ * node's right child subtree
+ *
+ * (n) (s)
+ * / \ / \
+ * (x) (y) -> (x) (y)
+ * / /
+ * (p) (p)
+ * / /
+ * (s) (c)
+ * \
+ * (c)
+ */
+ do {
+ parent = successor;
+ successor = tmp;
+ tmp = tmp->rb_left;
+ } while (tmp);
+ parent->rb_left = child2 = successor->rb_right;
+ successor->rb_right = child;
+ rb_set_parent(child, successor);
+ augment->copy(node, successor);
+ augment->propagate(parent, successor);
+ }
+
+ successor->rb_left = tmp = node->rb_left;
+ rb_set_parent(tmp, successor);
+
+ pc = node->__rb_parent_color;
+ tmp = __rb_parent(pc);
+ __rb_change_child(node, successor, tmp, root);
+ if (child2) {
+ successor->__rb_parent_color = pc;
+ rb_set_parent_color(child2, parent, RB_BLACK);
+ rebalance = NULL;
+ } else {
+ unsigned long pc2 = successor->__rb_parent_color;
+ successor->__rb_parent_color = pc;
+ rebalance = __rb_is_black(pc2) ? parent : NULL;
+ }
+ tmp = successor;
+ }
+
+ augment->propagate(tmp, NULL);
+ if (rebalance)
+ __rb_erase_color(rebalance, root, augment->rotate);
+}
+
+#endif /* _LINUX_RBTREE_AUGMENTED_H */
diff --git a/lib/rbtree.c b/lib/rbtree.c
index c0088ca..4f56a11 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -21,7 +21,7 @@
linux/lib/rbtree.c
*/
-#include <linux/rbtree.h>
+#include <linux/rbtree_augmented.h>
#include <linux/export.h>
/*
@@ -44,52 +44,16 @@
* parentheses and have some accompanying text comment.
*/
-#define RB_RED 0
-#define RB_BLACK 1
-
-#define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
-
-#define __rb_color(pc) ((pc) & 1)
-#define __rb_is_black(pc) __rb_color(pc)
-#define __rb_is_red(pc) (!__rb_color(pc))
-#define rb_color(rb) __rb_color((rb)->__rb_parent_color)
-#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
-#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
-
static inline void rb_set_black(struct rb_node *rb)
{
rb->__rb_parent_color |= RB_BLACK;
}
-static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
-{
- rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
-}
-
-static inline void rb_set_parent_color(struct rb_node *rb,
- struct rb_node *p, int color)
-{
- rb->__rb_parent_color = (unsigned long)p | color;
-}
-
static inline struct rb_node *rb_red_parent(struct rb_node *red)
{
return (struct rb_node *)red->__rb_parent_color;
}
-static inline void
-__rb_change_child(struct rb_node *old, struct rb_node *new,
- struct rb_node *parent, struct rb_root *root)
-{
- if (parent) {
- if (parent->rb_left == old)
- parent->rb_left = new;
- else
- parent->rb_right = new;
- } else
- root->rb_node = new;
-}
-
/*
* Helper function for rotations:
* - old's parent and color get assigned to new
@@ -230,9 +194,9 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
}
}
-static __always_inline void
+__always_inline void
__rb_erase_color(struct rb_node *parent, struct rb_root *root,
- const struct rb_augment_callbacks *augment)
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
@@ -261,7 +225,7 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
rb_set_parent_color(tmp1, parent, RB_BLACK);
__rb_rotate_set_parents(parent, sibling, root,
RB_RED);
- augment->rotate(parent, sibling);
+ augment_rotate(parent, sibling);
sibling = tmp1;
}
tmp1 = sibling->rb_right;
@@ -313,7 +277,7 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
if (tmp1)
rb_set_parent_color(tmp1, sibling,
RB_BLACK);
- augment->rotate(sibling, tmp2);
+ augment_rotate(sibling, tmp2);
tmp1 = sibling;
sibling = tmp2;
}
@@ -336,7 +300,7 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
rb_set_parent(tmp2, parent);
__rb_rotate_set_parents(parent, sibling, root,
RB_BLACK);
- augment->rotate(parent, sibling);
+ augment_rotate(parent, sibling);
break;
} else {
sibling = parent->rb_left;
@@ -347,7 +311,7 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
rb_set_parent_color(tmp1, parent, RB_BLACK);
__rb_rotate_set_parents(parent, sibling, root,
RB_RED);
- augment->rotate(parent, sibling);
+ augment_rotate(parent, sibling);
sibling = tmp1;
}
tmp1 = sibling->rb_left;
@@ -374,7 +338,7 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
if (tmp1)
rb_set_parent_color(tmp1, sibling,
RB_BLACK);
- augment->rotate(sibling, tmp2);
+ augment_rotate(sibling, tmp2);
tmp1 = sibling;
sibling = tmp2;
}
@@ -386,109 +350,12 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
rb_set_parent(tmp2, parent);
__rb_rotate_set_parents(parent, sibling, root,
RB_BLACK);
- augment->rotate(parent, sibling);
+ augment_rotate(parent, sibling);
break;
}
}
}
-
-static __always_inline void
-__rb_erase(struct rb_node *node, struct rb_root *root,
- const struct rb_augment_callbacks *augment)
-{
- struct rb_node *child = node->rb_right, *tmp = node->rb_left;
- struct rb_node *parent, *rebalance;
- unsigned long pc;
-
- if (!tmp) {
- /*
- * Case 1: node to erase has no more than 1 child (easy!)
- *
- * Note that if there is one child it must be red due to 5)
- * and node must be black due to 4). We adjust colors locally
- * so as to bypass __rb_erase_color() later on.
- */
- pc = node->__rb_parent_color;
- parent = __rb_parent(pc);
- __rb_change_child(node, child, parent, root);
- if (child) {
- child->__rb_parent_color = pc;
- rebalance = NULL;
- } else
- rebalance = __rb_is_black(pc) ? parent : NULL;
- tmp = parent;
- } else if (!child) {
- /* Still case 1, but this time the child is node->rb_left */
- tmp->__rb_parent_color = pc = node->__rb_parent_color;
- parent = __rb_parent(pc);
- __rb_change_child(node, tmp, parent, root);
- rebalance = NULL;
- tmp = parent;
- } else {
- struct rb_node *successor = child, *child2;
- tmp = child->rb_left;
- if (!tmp) {
- /*
- * Case 2: node's successor is its right child
- *
- * (n) (s)
- * / \ / \
- * (x) (s) -> (x) (c)
- * \
- * (c)
- */
- parent = successor;
- child2 = successor->rb_right;
- augment->copy(node, successor);
- } else {
- /*
- * Case 3: node's successor is leftmost under
- * node's right child subtree
- *
- * (n) (s)
- * / \ / \
- * (x) (y) -> (x) (y)
- * / /
- * (p) (p)
- * / /
- * (s) (c)
- * \
- * (c)
- */
- do {
- parent = successor;
- successor = tmp;
- tmp = tmp->rb_left;
- } while (tmp);
- parent->rb_left = child2 = successor->rb_right;
- successor->rb_right = child;
- rb_set_parent(child, successor);
- augment->copy(node, successor);
- augment->propagate(parent, successor);
- }
-
- successor->rb_left = tmp = node->rb_left;
- rb_set_parent(tmp, successor);
-
- pc = node->__rb_parent_color;
- tmp = __rb_parent(pc);
- __rb_change_child(node, successor, tmp, root);
- if (child2) {
- successor->__rb_parent_color = pc;
- rb_set_parent_color(child2, parent, RB_BLACK);
- rebalance = NULL;
- } else {
- unsigned long pc2 = successor->__rb_parent_color;
- successor->__rb_parent_color = pc;
- rebalance = __rb_is_black(pc2) ? parent : NULL;
- }
- tmp = successor;
- }
-
- augment->propagate(tmp, NULL);
- if (rebalance)
- __rb_erase_color(rebalance, root, augment);
-}
+EXPORT_SYMBOL(__rb_erase_color);
/*
* Non-augmented rbtree manipulation functions.
@@ -513,7 +380,7 @@ EXPORT_SYMBOL(rb_insert_color);
void rb_erase(struct rb_node *node, struct rb_root *root)
{
- __rb_erase(node, root, &dummy_callbacks);
+ rb_erase_augmented(node, root, &dummy_callbacks);
}
EXPORT_SYMBOL(rb_erase);
@@ -531,13 +398,6 @@ void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
}
EXPORT_SYMBOL(__rb_insert_augmented);
-void rb_erase_augmented(struct rb_node *node, struct rb_root *root,
- const struct rb_augment_callbacks *augment)
-{
- __rb_erase(node, root, augment);
-}
-EXPORT_SYMBOL(rb_erase_augmented);
-
/*
* This function returns the first node (in sort order) of the tree.
*/
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index b20e999..268b239 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -1,5 +1,5 @@
#include <linux/module.h>
-#include <linux/rbtree.h>
+#include <linux/rbtree_augmented.h>
#include <linux/random.h>
#include <asm/timex.h>
--
1.7.7.3
^ permalink raw reply related [flat|nested] 18+ messages in thread
* Re: [PATCH 5/5] rbtree: move augmented rbtree functionality to rbtree_augmented.h
2012-08-07 7:25 ` [PATCH 5/5] rbtree: move augmented rbtree functionality to rbtree_augmented.h Michel Lespinasse
@ 2012-08-08 1:19 ` Michel Lespinasse
0 siblings, 0 replies; 18+ messages in thread
From: Michel Lespinasse @ 2012-08-08 1:19 UTC (permalink / raw)
To: riel, peterz, vrajesh, daniel.santos, aarcange, dwmw2, akpm
Cc: linux-mm, linux-kernel, torvalds
On Tue, Aug 7, 2012 at 12:25 AM, Michel Lespinasse <walken@google.com> wrote:
> 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.
I should probably add this to show how the code generation works out
in practice (with a gcc 4.6 based compiler)
Before this change:
text data bss dec hex filename
3426 0 0 3426 d62 lib/rbtree.o
0000000000000af0 g F .text 000000000000001e rb_last
0000000000000b80 g F .text 0000000000000047 rb_next
0000000000000000 g F .text 0000000000000165 rb_insert_color
0000000000000bd0 g F .text 0000000000000047 rb_prev
00000000000004e0 g F .text 00000000000001cd __rb_insert_augmented
0000000000000170 g F .text 000000000000036f rb_erase
00000000000006b0 g F .text 0000000000000416 rb_erase_augmented
0000000000000ad0 g F .text 000000000000001e rb_first
0000000000000b10 g F .text 000000000000006e rb_replace_node
text data bss dec hex filename
540 0 0 540 21c lib/interval_tree.o
0000000000000000 l F .text 0000000000000054
interval_tree_augment_propagate
0000000000000060 l F .text 000000000000000e interval_tree_augment_copy
0000000000000070 l F .text 000000000000003e
interval_tree_augment_rotate
00000000000000b0 g F .text 0000000000000065 interval_tree_insert
0000000000000120 g F .text 0000000000000012 interval_tree_remove
0000000000000140 g F .text 000000000000004c interval_tree_iter_first
0000000000000190 g F .text 0000000000000074 interval_tree_iter_next
After this change:
text data bss dec hex filename
2976 0 0 2976 ba0 lib/rbtree.o
0000000000000000 g F .text 000000000000025c __rb_erase_color
0000000000000930 g F .text 000000000000001e rb_last
00000000000009c0 g F .text 0000000000000047 rb_next
0000000000000260 g F .text 0000000000000165 rb_insert_color
0000000000000a10 g F .text 0000000000000047 rb_prev
0000000000000740 g F .text 00000000000001cd __rb_insert_augmented
00000000000003d0 g F .text 000000000000036f rb_erase
0000000000000910 g F .text 000000000000001e rb_first
0000000000000950 g F .text 000000000000006e rb_replace_node
text data bss dec hex filename
900 0 0 900 384 lib/interval_tree.o
0000000000000000 l F .text 000000000000003e
interval_tree_augment_rotate
0000000000000040 g F .text 0000000000000065 interval_tree_insert
00000000000000b0 g F .text 000000000000020b interval_tree_remove
00000000000002c0 g F .text 000000000000004c interval_tree_iter_first
0000000000000310 g F .text 0000000000000074 interval_tree_iter_next
So the code size effect is that the library code for augmented erase
shrinks by 450 bytes, and each augmented rb_erase user grows by (well,
this will very between users, but I think interval tree is
representative of a typical user) ~360 bytes. The rotate callback is
generated as a static function so it can be passed by pointer to the
library rebalancing routines; the copy and propagate functions are
inlined into interval_tree_remove (and the compiler is able to
determine that there are no remaining non-inlined calls, so it doesn't
generate an additional static definition).
--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH 3/5] kmemleak: use rbtree instead of prio tree
2012-08-07 7:25 ` [PATCH 3/5] kmemleak: use rbtree instead of prio tree Michel Lespinasse
@ 2012-08-08 17:07 ` Michel Lespinasse
2012-08-09 8:31 ` Catalin Marinas
0 siblings, 1 reply; 18+ messages in thread
From: Michel Lespinasse @ 2012-08-08 17:07 UTC (permalink / raw)
To: Catalin Marinas, riel, peterz, vrajesh, daniel.santos, aarcange,
dwmw2, akpm
Cc: linux-mm, linux-kernel, torvalds
Forgot to add Catalin on this review...
---------- Forwarded message ----------
From: Michel Lespinasse <walken@google.com>
Date: Tue, Aug 7, 2012 at 12:25 AM
Subject: [PATCH 3/5] kmemleak: use rbtree instead of prio tree
To: riel@redhat.com, peterz@infradead.org, vrajesh@umich.edu,
daniel.santos@pobox.com, aarcange@redhat.com, dwmw2@infradead.org,
akpm@linux-foundation.org
Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org,
torvalds@linux-foundation.org
kmemleak uses a tree where each node represents an allocated memory object
in order to quickly find out what object a given address is part of.
However, the objects don't overlap, so rbtrees are a better choice than
prio tree for this use. They are both faster and have lower memory overhead.
Tested by booting a kernel with kmemleak enabled, loading the kmemleak_test
module, and looking for the expected messages.
Signed-off-by: Michel Lespinasse <walken@google.com>
---
mm/kmemleak.c | 98 +++++++++++++++++++++++++++++----------------------------
1 files changed, 50 insertions(+), 48 deletions(-)
diff --git a/mm/kmemleak.c b/mm/kmemleak.c
index 45eb621..8de1b09 100644
--- a/mm/kmemleak.c
+++ b/mm/kmemleak.c
@@ -29,7 +29,7 @@
* - kmemleak_lock (rwlock): protects the object_list modifications and
* accesses to the object_tree_root. The object_list is the main list
* holding the metadata (struct kmemleak_object) for the allocated memory
- * blocks. The object_tree_root is a priority search tree used to look-up
+ * blocks. The object_tree_root is a red black tree used to look-up
* metadata based on a pointer to the corresponding memory block. The
* kmemleak_object structures are added to the object_list and
* object_tree_root in the create_object() function called from the
@@ -71,7 +71,7 @@
#include <linux/delay.h>
#include <linux/export.h>
#include <linux/kthread.h>
-#include <linux/prio_tree.h>
+#include <linux/rbtree.h>
#include <linux/fs.h>
#include <linux/debugfs.h>
#include <linux/seq_file.h>
@@ -132,7 +132,7 @@ struct kmemleak_scan_area {
* Structure holding the metadata for each allocated memory block.
* Modifications to such objects should be made while holding the
* object->lock. Insertions or deletions from object_list, gray_list or
- * tree_node are already protected by the corresponding locks or mutex (see
+ * rb_node are already protected by the corresponding locks or mutex (see
* the notes on locking above). These objects are reference-counted
* (use_count) and freed using the RCU mechanism.
*/
@@ -141,7 +141,7 @@ struct kmemleak_object {
unsigned long flags; /* object status flags */
struct list_head object_list;
struct list_head gray_list;
- struct prio_tree_node tree_node;
+ struct rb_node rb_node;
struct rcu_head rcu; /* object_list lockless traversal */
/* object usage count; object freed when use_count == 0 */
atomic_t use_count;
@@ -182,9 +182,9 @@ struct kmemleak_object {
static LIST_HEAD(object_list);
/* the list of gray-colored objects (see color_gray comment below) */
static LIST_HEAD(gray_list);
-/* prio search tree for object boundaries */
-static struct prio_tree_root object_tree_root;
-/* rw_lock protecting the access to object_list and prio_tree_root */
+/* search tree for object boundaries */
+static struct rb_root object_tree_root = RB_ROOT;
+/* rw_lock protecting the access to object_list and object_tree_root */
static DEFINE_RWLOCK(kmemleak_lock);
/* allocation caches for kmemleak internal data */
@@ -380,7 +380,7 @@ static void dump_object_info(struct kmemleak_object *object)
trace.entries = object->trace;
pr_notice("Object 0x%08lx (size %zu):\n",
- object->tree_node.start, object->size);
+ object->pointer, object->size);
pr_notice(" comm \"%s\", pid %d, jiffies %lu\n",
object->comm, object->pid, object->jiffies);
pr_notice(" min_count = %d\n", object->min_count);
@@ -392,32 +392,32 @@ static void dump_object_info(struct
kmemleak_object *object)
}
/*
- * Look-up a memory block metadata (kmemleak_object) in the priority search
+ * Look-up a memory block metadata (kmemleak_object) in the object search
* tree based on a pointer value. If alias is 0, only values pointing to the
* beginning of the memory block are allowed. The kmemleak_lock must be held
* when calling this function.
*/
static struct kmemleak_object *lookup_object(unsigned long ptr, int alias)
{
- struct prio_tree_node *node;
- struct prio_tree_iter iter;
- struct kmemleak_object *object;
-
- prio_tree_iter_init(&iter, &object_tree_root, ptr, ptr);
- node = prio_tree_next(&iter);
- if (node) {
- object = prio_tree_entry(node, struct kmemleak_object,
- tree_node);
- if (!alias && object->pointer != ptr) {
+ struct rb_node *rb = object_tree_root.rb_node;
+
+ while (rb) {
+ struct kmemleak_object *object =
+ rb_entry(rb, struct kmemleak_object, rb_node);
+ if (ptr < object->pointer)
+ rb = object->rb_node.rb_left;
+ else if (object->pointer + object->size <= ptr)
+ rb = object->rb_node.rb_right;
+ else if (object->pointer == ptr || alias)
+ return object;
+ else {
kmemleak_warn("Found object by alias at 0x%08lx\n",
ptr);
dump_object_info(object);
- object = NULL;
+ break;
}
- } else
- object = NULL;
-
- return object;
+ }
+ return NULL;
}
/*
@@ -471,7 +471,7 @@ static void put_object(struct kmemleak_object *object)
}
/*
- * Look up an object in the prio search tree and increase its use_count.
+ * Look up an object in the object search tree and increase its use_count.
*/
static struct kmemleak_object *find_and_get_object(unsigned long ptr,
int alias)
{
@@ -516,8 +516,8 @@ static struct kmemleak_object
*create_object(unsigned long ptr, size_t size,
int min_count, gfp_t gfp)
{
unsigned long flags;
- struct kmemleak_object *object;
- struct prio_tree_node *node;
+ struct kmemleak_object *object, *parent;
+ struct rb_node **link, *rb_parent;
object = kmem_cache_alloc(object_cache, gfp_kmemleak_mask(gfp));
if (!object) {
@@ -560,31 +560,34 @@ static struct kmemleak_object
*create_object(unsigned long ptr, size_t size,
/* kernel backtrace */
object->trace_len = __save_stack_trace(object->trace);
- INIT_PRIO_TREE_NODE(&object->tree_node);
- object->tree_node.start = ptr;
- object->tree_node.last = ptr + size - 1;
-
write_lock_irqsave(&kmemleak_lock, flags);
min_addr = min(min_addr, ptr);
max_addr = max(max_addr, ptr + size);
- node = prio_tree_insert(&object_tree_root, &object->tree_node);
- /*
- * The code calling the kernel does not yet have the pointer to the
- * memory block to be able to free it. However, we still hold the
- * kmemleak_lock here in case parts of the kernel started freeing
- * random memory blocks.
- */
- if (node != &object->tree_node) {
- kmemleak_stop("Cannot insert 0x%lx into the object search tree "
- "(already existing)\n", ptr);
- object = lookup_object(ptr, 1);
- spin_lock(&object->lock);
- dump_object_info(object);
- spin_unlock(&object->lock);
- goto out;
+ link = &object_tree_root.rb_node;
+ rb_parent = NULL;
+ while (*link) {
+ rb_parent = *link;
+ parent = rb_entry(rb_parent, struct kmemleak_object, rb_node);
+ if (ptr + size <= parent->pointer)
+ link = &parent->rb_node.rb_left;
+ else if (parent->pointer + parent->size <= ptr)
+ link = &parent->rb_node.rb_right;
+ else {
+ kmemleak_stop("Cannot insert 0x%lx into the object "
+ "search tree (overlaps existing)\n",
+ ptr);
+ object = parent;
+ spin_lock(&object->lock);
+ dump_object_info(object);
+ spin_unlock(&object->lock);
+ goto out;
+ }
}
+ rb_link_node(&object->rb_node, rb_parent, link);
+ rb_insert_color(&object->rb_node, &object_tree_root);
+
list_add_tail_rcu(&object->object_list, &object_list);
out:
write_unlock_irqrestore(&kmemleak_lock, flags);
@@ -600,7 +603,7 @@ static void __delete_object(struct kmemleak_object *object)
unsigned long flags;
write_lock_irqsave(&kmemleak_lock, flags);
- prio_tree_remove(&object_tree_root, &object->tree_node);
+ rb_erase(&object->rb_node, &object_tree_root);
list_del_rcu(&object->object_list);
write_unlock_irqrestore(&kmemleak_lock, flags);
@@ -1768,7 +1771,6 @@ void __init kmemleak_init(void)
object_cache = KMEM_CACHE(kmemleak_object, SLAB_NOLEAKTRACE);
scan_area_cache = KMEM_CACHE(kmemleak_scan_area, SLAB_NOLEAKTRACE);
- INIT_PRIO_TREE_ROOT(&object_tree_root);
if (crt_early_log >= ARRAY_SIZE(early_log))
pr_warning("Early log buffer exceeded (%d), please increase "
--
1.7.7.3
--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
^ permalink raw reply related [flat|nested] 18+ messages in thread
* Re: [PATCH 3/5] kmemleak: use rbtree instead of prio tree
2012-08-08 17:07 ` Michel Lespinasse
@ 2012-08-09 8:31 ` Catalin Marinas
2012-08-15 16:36 ` Catalin Marinas
0 siblings, 1 reply; 18+ messages in thread
From: Catalin Marinas @ 2012-08-09 8:31 UTC (permalink / raw)
To: Michel Lespinasse
Cc: riel, peterz, vrajesh, daniel.santos, aarcange, dwmw2, akpm,
linux-mm, linux-kernel, torvalds
On Wed, Aug 08, 2012 at 06:07:39PM +0100, Michel Lespinasse wrote:
> kmemleak uses a tree where each node represents an allocated memory object
> in order to quickly find out what object a given address is part of.
> However, the objects don't overlap, so rbtrees are a better choice than
> prio tree for this use. They are both faster and have lower memory overhead.
>
> Tested by booting a kernel with kmemleak enabled, loading the kmemleak_test
> module, and looking for the expected messages.
>
> Signed-off-by: Michel Lespinasse <walken@google.com>
The patch looks fine to me but I'll give it a test later today and let
you know.
--
Catalin
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH 0/5] rbtree based interval tree as a prio_tree replacement
2012-08-07 7:25 [PATCH 0/5] rbtree based interval tree as a prio_tree replacement Michel Lespinasse
` (4 preceding siblings ...)
2012-08-07 7:25 ` [PATCH 5/5] rbtree: move augmented rbtree functionality to rbtree_augmented.h Michel Lespinasse
@ 2012-08-13 8:20 ` Peter Zijlstra
2012-08-13 10:37 ` Michel Lespinasse
2012-08-30 21:34 ` Andrew Morton
6 siblings, 1 reply; 18+ messages in thread
From: Peter Zijlstra @ 2012-08-13 8:20 UTC (permalink / raw)
To: Michel Lespinasse
Cc: riel, vrajesh, daniel.santos, aarcange, dwmw2, akpm, linux-mm,
linux-kernel, torvalds
On Tue, 2012-08-07 at 00:25 -0700, Michel Lespinasse wrote:
> a faster worst-case complexity of O(k+log N) for stabbing queries in a
> well-balanced prio tree, vs O(k*log N) for interval trees (where k=number
> of matches, N=number of intervals). Now this sounds great, but in practice
> prio trees don't realize this theorical benefit. First, the additional
> constraint makes them harder to update, so that the kernel implementation
> has to simplify things by balancing them like a radix tree, which is not
> always ideal.
Not something spending a great deal of time on, but do you have any idea
what the radix like balancing does the the worst case stabbing
complexity?
Anyway, I like the thing, that prio-tree code always made my head hurt.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH 0/5] rbtree based interval tree as a prio_tree replacement
2012-08-13 8:20 ` [PATCH 0/5] rbtree based interval tree as a prio_tree replacement Peter Zijlstra
@ 2012-08-13 10:37 ` Michel Lespinasse
0 siblings, 0 replies; 18+ messages in thread
From: Michel Lespinasse @ 2012-08-13 10:37 UTC (permalink / raw)
To: Peter Zijlstra
Cc: riel, vrajesh, daniel.santos, aarcange, dwmw2, akpm, linux-mm,
linux-kernel, torvalds
On Mon, Aug 13, 2012 at 1:20 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Tue, 2012-08-07 at 00:25 -0700, Michel Lespinasse wrote:
>> a faster worst-case complexity of O(k+log N) for stabbing queries in a
>> well-balanced prio tree, vs O(k*log N) for interval trees (where k=number
>> of matches, N=number of intervals). Now this sounds great, but in practice
>> prio trees don't realize this theorical benefit. First, the additional
>> constraint makes them harder to update, so that the kernel implementation
>> has to simplify things by balancing them like a radix tree, which is not
>> always ideal.
>
> Not something spending a great deal of time on, but do you have any idea
> what the radix like balancing does the the worst case stabbing
> complexity?
Well, it's not terribly bad as the height of the radix tree is still
bounded by (IIRC) log(ULONG_MAX) + log(max pgoff_t in the file). So
the complexity ends up being O(k + some constant) where the constant
is in practice always larger than log(N).
One can still construct cases where a prio tree stabbing query would
read less nodes (so touch less cache lines) than with augmented
rbtree. I think the best way to explain this is to look at what
augmented rbtree does - for a stabbing query returning k matches, it
visits all nodes between the root and the k matching nodes (plus one
extra path at the end to conclude that there are no further matches).
So the worst case there would be if the matching nodes are all close
to leaf level in the tree, and if the paths leading to them branch up
close to the root level. It's easy to construct such a case by making
all N nodes in the tree start to the left of the stabbing query, and
having only an arbitrary k among them end to the right of the query.
Prio tree achieves a better worst case complexity by placing these k
nodes near the top of the tree (due to the heap constraint). But this
worst case situation isn't very likely to begin with, and in the
typical case the k paths leading to the matching nodes in an augmented
rbtree don't branch up so close to the root so typically prio tree
doesn't get an advantage there.
To sum it up, I would say that both algorithms are really pretty good,
with prio tree getting a slightly better theorical worst-case and
augmented rbtree getting (IMO) a practical advantage due to lower
constant factors and a still very acceptable worst case.
> Anyway, I like the thing, that prio-tree code always made my head hurt.
Black magic I tell you ;-)
--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH 2/5] mm: replace vma prio_tree with an interval tree
2012-08-07 7:25 ` [PATCH 2/5] mm: replace vma prio_tree with an interval tree Michel Lespinasse
@ 2012-08-14 12:11 ` Hillf Danton
0 siblings, 0 replies; 18+ messages in thread
From: Hillf Danton @ 2012-08-14 12:11 UTC (permalink / raw)
To: Michel Lespinasse
Cc: riel, peterz, vrajesh, daniel.santos, aarcange, dwmw2, akpm,
linux-mm, linux-kernel, torvalds
On Tue, Aug 7, 2012 at 3:25 PM, Michel Lespinasse <walken@google.com> wrote:
> +#define ITSTRUCT struct vm_area_struct
> +#define ITSTART(n) ((n)->vm_pgoff)
> +#define ITLAST(n) ((n)->vm_pgoff + \
> + (((n)->vm_end - (n)->vm_start) >> PAGE_SHIFT) - 1)
[...]
> @@ -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);
> 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) {
Given the above defines for ITSTART and ITLAST, page index perhaps could not
be used directly in scanning interval tree for vma when ttum hugetlb page?
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH 3/5] kmemleak: use rbtree instead of prio tree
2012-08-09 8:31 ` Catalin Marinas
@ 2012-08-15 16:36 ` Catalin Marinas
2012-08-15 20:53 ` Michel Lespinasse
0 siblings, 1 reply; 18+ messages in thread
From: Catalin Marinas @ 2012-08-15 16:36 UTC (permalink / raw)
To: Michel Lespinasse
Cc: riel, peterz, vrajesh, daniel.santos, aarcange, dwmw2, akpm,
linux-mm, linux-kernel, torvalds
On 9 August 2012 09:31, Catalin Marinas <catalin.marinas@arm.com> wrote:
> On Wed, Aug 08, 2012 at 06:07:39PM +0100, Michel Lespinasse wrote:
>> kmemleak uses a tree where each node represents an allocated memory object
>> in order to quickly find out what object a given address is part of.
>> However, the objects don't overlap, so rbtrees are a better choice than
>> prio tree for this use. They are both faster and have lower memory overhead.
>>
>> Tested by booting a kernel with kmemleak enabled, loading the kmemleak_test
>> module, and looking for the expected messages.
>>
>> Signed-off-by: Michel Lespinasse <walken@google.com>
>
> The patch looks fine to me but I'll give it a test later today and let
> you know.
Couldn't test it because the patch got messed up somewhere on the
email path (tabs replaced with spaces). Is there a Git tree I can grab
it from (or you could just send it to me separately as attachment)?
Thanks,
Catalin
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH 3/5] kmemleak: use rbtree instead of prio tree
2012-08-15 16:36 ` Catalin Marinas
@ 2012-08-15 20:53 ` Michel Lespinasse
2012-08-16 15:06 ` Catalin Marinas
0 siblings, 1 reply; 18+ messages in thread
From: Michel Lespinasse @ 2012-08-15 20:53 UTC (permalink / raw)
To: Catalin Marinas
Cc: riel, peterz, vrajesh, daniel.santos, aarcange, dwmw2, akpm,
linux-mm, linux-kernel, torvalds
On Wed, Aug 15, 2012 at 9:36 AM, Catalin Marinas
<catalin.marinas@arm.com> wrote:
> Couldn't test it because the patch got messed up somewhere on the
> email path (tabs replaced with spaces). Is there a Git tree I can grab
> it from (or you could just send it to me separately as attachment)?
Sorry about that. The original patch I sent to lkml & linux-mm wasn't
corrupted, but the forward I sent you after I realized I had forgotten
to include you was.
https://lkml.org/lkml/2012/8/7/52 has the original patch, and "get
diff 1" in the left column can be used to retrieve it.
--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH 3/5] kmemleak: use rbtree instead of prio tree
2012-08-15 20:53 ` Michel Lespinasse
@ 2012-08-16 15:06 ` Catalin Marinas
0 siblings, 0 replies; 18+ messages in thread
From: Catalin Marinas @ 2012-08-16 15:06 UTC (permalink / raw)
To: Michel Lespinasse
Cc: riel, peterz, vrajesh, daniel.santos, aarcange, dwmw2, akpm,
linux-mm, linux-kernel, torvalds
On Wed, Aug 15, 2012 at 09:53:07PM +0100, Michel Lespinasse wrote:
> On Wed, Aug 15, 2012 at 9:36 AM, Catalin Marinas
> <catalin.marinas@arm.com> wrote:
> > Couldn't test it because the patch got messed up somewhere on the
> > email path (tabs replaced with spaces). Is there a Git tree I can grab
> > it from (or you could just send it to me separately as attachment)?
>
> Sorry about that. The original patch I sent to lkml & linux-mm wasn't
> corrupted, but the forward I sent you after I realized I had forgotten
> to include you was.
>
> https://lkml.org/lkml/2012/8/7/52 has the original patch, and "get
> diff 1" in the left column can be used to retrieve it.
Thanks. It works fine in my tests and the scanning time seems to have
got down from 22s to 19s on my board.
Acked-by: Catalin Marinas <catalin.marinas@arm.com>
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH 0/5] rbtree based interval tree as a prio_tree replacement
2012-08-07 7:25 [PATCH 0/5] rbtree based interval tree as a prio_tree replacement Michel Lespinasse
` (5 preceding siblings ...)
2012-08-13 8:20 ` [PATCH 0/5] rbtree based interval tree as a prio_tree replacement Peter Zijlstra
@ 2012-08-30 21:34 ` Andrew Morton
2012-08-30 21:43 ` Rik van Riel
2012-08-30 22:33 ` Michel Lespinasse
6 siblings, 2 replies; 18+ messages in thread
From: Andrew Morton @ 2012-08-30 21:34 UTC (permalink / raw)
To: Michel Lespinasse
Cc: riel, peterz, vrajesh, daniel.santos, aarcange, dwmw2, linux-mm,
linux-kernel, torvalds
On Tue, 7 Aug 2012 00:25:38 -0700
Michel Lespinasse <walken@google.com> wrote:
> This patchset goes over the rbtree changes that have been already integrated
> into Andrew's -mm tree, as well as the augmented rbtree proposal which is
> currently pending.
hm. Well I grabbed these for a bit of testing.
It's a large change in MM and it depends on code which hasn't yet been
merged in mainline. It's probably prudent to do all this in two steps
- we'll see.
It would good to have solid acknowledgement from Rik that this approach
does indeed suit his pending vma changes.
The templates-with-CPP thing is not terribly appealing. It's not
obvious that it really needed to be done this way - we've avoided it in
plenty of other places. It would be nice to see that alternatives have
been thoroughly explored, and why they were rejected.
AFAICT the code will work OK when expanding macros which reference their
arguments multiple times. For example, interval_tree.c has
#define ITLAST(n) ((n)->vm_pgoff + \
(((n)->vm_end - (n)->vm_start) >> PAGE_SHIFT) - 1)
which will explode if passed "foo++". Things like that.
The code uses the lame-and-useless "inline" absolutely all over the
place. I do think that for new code it would be better to get down and
actually make proper engineering decisions about which functions should
be inlined and mark them __always_inline.
Hillf has made a review suggestion which AFAICT remains unresponded to.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH 0/5] rbtree based interval tree as a prio_tree replacement
2012-08-30 21:34 ` Andrew Morton
@ 2012-08-30 21:43 ` Rik van Riel
2012-08-30 22:33 ` Michel Lespinasse
1 sibling, 0 replies; 18+ messages in thread
From: Rik van Riel @ 2012-08-30 21:43 UTC (permalink / raw)
To: Andrew Morton
Cc: Michel Lespinasse, peterz, vrajesh, daniel.santos, aarcange,
dwmw2, linux-mm, linux-kernel, torvalds
On 08/30/2012 05:34 PM, Andrew Morton wrote:
> It would good to have solid acknowledgement from Rik that this approach
> does indeed suit his pending vma changes.
It does. Michel's rbtree rework is exactly what I need.
I do not need the interval tree bits, but the faster
augmented rbtree is required for my vma changes to
no longer have the performance regression Johannes
measured with a kernel build.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH 0/5] rbtree based interval tree as a prio_tree replacement
2012-08-30 21:34 ` Andrew Morton
2012-08-30 21:43 ` Rik van Riel
@ 2012-08-30 22:33 ` Michel Lespinasse
1 sibling, 0 replies; 18+ messages in thread
From: Michel Lespinasse @ 2012-08-30 22:33 UTC (permalink / raw)
To: Andrew Morton
Cc: riel, peterz, vrajesh, daniel.santos, aarcange, dwmw2, linux-mm,
linux-kernel, torvalds
On Thu, Aug 30, 2012 at 2:34 PM, Andrew Morton
<akpm@linux-foundation.org> wrote:
> On Tue, 7 Aug 2012 00:25:38 -0700
> Michel Lespinasse <walken@google.com> wrote:
>
>> This patchset goes over the rbtree changes that have been already integrated
>> into Andrew's -mm tree, as well as the augmented rbtree proposal which is
>> currently pending.
>
> hm. Well I grabbed these for a bit of testing.
>
> It's a large change in MM and it depends on code which hasn't yet been
> merged in mainline. It's probably prudent to do all this in two steps
> - we'll see.
Makes sense to me. If we want to split the series as they get sent
upstream, I would suggest sending all the rbtree and augmented rbtree
infrastructure first, and then the rbtree usages (prio tree
replacement, anon rmap interval tree which I'm going to send next, and
rik's augmented rbtree based vma gap finder) in the next kernel.
> The templates-with-CPP thing is not terribly appealing. It's not
> obvious that it really needed to be done this way - we've avoided it in
> plenty of other places. It would be nice to see that alternatives have
> been thoroughly explored, and why they were rejected.
I am actually wondering if the interval_tree_tmpl.h include file
shouldn't be done as one large preprocessor #define instead. The
ITSTRUCT, ITRB, etc... definitions would then become arguments to that
large definition. It would also be possible to break up that #define
into smaller ones - most likely, one for insertion, one for removal,
and one for the subtree_search / iter_first / iter_next functions. Do
you think this might help ?
I don't really see other workable alternatives that don't involve code
replication.
> The code uses the lame-and-useless "inline" absolutely all over the
> place. I do think that for new code it would be better to get down and
> actually make proper engineering decisions about which functions should
> be inlined and mark them __always_inline.
You mentionned this before, but I'm not convinced that __always_inline
would be better. The kernel is full of 2-line functions that we really
want inlined, and I don't see what the value would be in converting
these all to __always_inline. I am tempted to stick with the current
usage, which I understand as being:
- use inline when the programmer believes a function should be inlined
(this includes the static inline functions in header files - if the
programmer didn't believe this should be inlined, he wouldn't put the
function in a header file)
- use __always_inline if the function absolutely needs to be inlined
for correct operation (I believe scheduler has some of these, which
need to be included in the parent in order to end up in the correct
section), OR in rare cases if the compiler is known to generate bad
code with a mere inline and the programmer wants to force the issue.
I would also note that replacing inline with __always_inline is not a
no-op change, even when the compiler was already inlining the original
(marked inline) function. Sometimes the generated code ends up being
different with __always_inline and I would rather not apply these
changes blindly.
> Hillf has made a review suggestion which AFAICT remains unresponded to.
To be honest, I wasn't quite sure what he was suggesting ?
--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
^ permalink raw reply [flat|nested] 18+ messages in thread
end of thread, other threads:[~2012-08-30 22:33 UTC | newest]
Thread overview: 18+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-08-07 7:25 [PATCH 0/5] rbtree based interval tree as a prio_tree replacement Michel Lespinasse
2012-08-07 7:25 ` [PATCH 1/5] rbtree: add prio tree and interval tree tests Michel Lespinasse
2012-08-07 7:25 ` [PATCH 2/5] mm: replace vma prio_tree with an interval tree Michel Lespinasse
2012-08-14 12:11 ` Hillf Danton
2012-08-07 7:25 ` [PATCH 3/5] kmemleak: use rbtree instead of prio tree Michel Lespinasse
2012-08-08 17:07 ` Michel Lespinasse
2012-08-09 8:31 ` Catalin Marinas
2012-08-15 16:36 ` Catalin Marinas
2012-08-15 20:53 ` Michel Lespinasse
2012-08-16 15:06 ` Catalin Marinas
2012-08-07 7:25 ` [PATCH 4/5] prio_tree: remove Michel Lespinasse
2012-08-07 7:25 ` [PATCH 5/5] rbtree: move augmented rbtree functionality to rbtree_augmented.h Michel Lespinasse
2012-08-08 1:19 ` Michel Lespinasse
2012-08-13 8:20 ` [PATCH 0/5] rbtree based interval tree as a prio_tree replacement Peter Zijlstra
2012-08-13 10:37 ` Michel Lespinasse
2012-08-30 21:34 ` Andrew Morton
2012-08-30 21:43 ` Rik van Riel
2012-08-30 22:33 ` Michel Lespinasse
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).