* [rfc PATCH -next 0/5] rbtree: Cache leftmost node internally
@ 2017-05-30 2:09 Davidlohr Bueso
2017-05-30 2:09 ` [PATCH 1/5] " Davidlohr Bueso
` (6 more replies)
0 siblings, 7 replies; 12+ messages in thread
From: Davidlohr Bueso @ 2017-05-30 2:09 UTC (permalink / raw)
To: mingo, peterz, akpm
Cc: jack, kirill.shutemov, ldufour, mhocko, mgorman, dave, linux-kernel
Hi,
Here's a proposal for extending rbtrees to internally cache the leftmost
node such that we can have fast overlap check optimization for all interval
tree users[1]. I've marked this rfc as I don't know how folks will react
to a new rb_root_cached structure; which is explained in patch 1. The
rest of the patches make use of the internal leftmost node in scheduler
and rtmutexes and finally patch 5 implements fast overlap checks for
interval trees.
The series has survived booting, kernel builds and pistress workloads.
Applies on top of 4.12-rc3 (next).
Thanks!
[1] https://lkml.org/lkml/2017/5/16/676
Davidlohr Bueso (5):
rbtree: Cache leftmost node internally
sched/fair: Replace cfs_rq->rb_leftmost
locking/rtmutex: Replace top-waiter and pi_waiters leftmost caching
sched/deadline: Replace earliest deadline and runqueue leftmost caching
lib/interval_tree: Fast overlap detection
drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c | 8 ++--
drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c | 7 +--
drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h | 2 +-
drivers/gpu/drm/drm_mm.c | 10 ++---
drivers/gpu/drm/drm_vma_manager.c | 2 +-
drivers/gpu/drm/i915/i915_gem_userptr.c | 6 +--
drivers/gpu/drm/radeon/radeon.h | 2 +-
drivers/gpu/drm/radeon/radeon_mn.c | 8 ++--
drivers/gpu/drm/radeon/radeon_vm.c | 7 +--
drivers/infiniband/core/umem_rbtree.c | 4 +-
drivers/infiniband/core/uverbs_cmd.c | 2 +-
drivers/infiniband/hw/usnic/usnic_uiom.c | 6 +--
drivers/infiniband/hw/usnic/usnic_uiom.h | 2 +-
.../infiniband/hw/usnic/usnic_uiom_interval_tree.c | 15 ++++---
.../infiniband/hw/usnic/usnic_uiom_interval_tree.h | 12 +++---
drivers/vhost/vhost.c | 2 +-
drivers/vhost/vhost.h | 2 +-
fs/hugetlbfs/inode.c | 6 +--
fs/inode.c | 2 +-
include/drm/drm_mm.h | 2 +-
include/linux/fs.h | 4 +-
include/linux/init_task.h | 5 +--
include/linux/interval_tree.h | 8 ++--
include/linux/interval_tree_generic.h | 46 +++++++++++++++-----
include/linux/mm.h | 17 ++++----
include/linux/rbtree.h | 11 +++++
include/linux/rbtree_augmented.h | 33 ++++++++++++--
include/linux/rmap.h | 4 +-
include/linux/rtmutex.h | 9 ++--
include/linux/sched.h | 3 +-
include/rdma/ib_umem_odp.h | 11 +++--
include/rdma/ib_verbs.h | 2 +-
kernel/fork.c | 3 +-
kernel/locking/rtmutex-debug.c | 2 +-
kernel/locking/rtmutex.c | 36 ++++++----------
kernel/locking/rtmutex_common.h | 10 ++---
kernel/sched/deadline.c | 50 ++++++++--------------
kernel/sched/debug.c | 2 +-
kernel/sched/fair.c | 35 +++++----------
kernel/sched/sched.h | 9 ++--
lib/interval_tree_test.c | 4 +-
lib/rbtree.c | 34 ++++++++++++---
mm/interval_tree.c | 10 ++---
mm/memory.c | 4 +-
mm/mmap.c | 10 ++---
mm/rmap.c | 4 +-
46 files changed, 264 insertions(+), 209 deletions(-)
--
2.12.0
^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH 1/5] rbtree: Cache leftmost node internally
2017-05-30 2:09 [rfc PATCH -next 0/5] rbtree: Cache leftmost node internally Davidlohr Bueso
@ 2017-05-30 2:09 ` Davidlohr Bueso
2017-06-08 13:03 ` Peter Zijlstra
2017-05-30 2:09 ` [PATCH 2/5] sched/fair: Replace cfs_rq->rb_leftmost Davidlohr Bueso
` (5 subsequent siblings)
6 siblings, 1 reply; 12+ messages in thread
From: Davidlohr Bueso @ 2017-05-30 2:09 UTC (permalink / raw)
To: mingo, peterz, akpm
Cc: jack, kirill.shutemov, ldufour, mhocko, mgorman, dave,
linux-kernel, Davidlohr Bueso
Red-black tree semantics imply that nodes with smaller or
greater (or equal for duplicates) keys always be to the
left and right, respectively. For the kernel this is
extremely evident when considering our rb_first() semantics.
Enabling lookups for the smallest node in the tree in O(1)
can save a good chunk of cycles in not having to walk down the
tree each time. To this end there are a few core users that
explicitly do this, such as the scheduler and rtmutexes.
There is also the desire for interval trees to have this
optimization allowing faster overlap checking.
This patch introduces a new 'struct rb_root_cached' which
is just the root with a cached pointer to the leftmost node.
The reason why the regular rb_root was not extended instead
of adding a new structure was that this allows the user to
have the choice between memory footprint and actual tree
performance. The new wrappers on top of the regular rb_root
calls are:
- rb_first_cached(cached_root) -- which is a fast replacement
for rb_first.
- rb_insert_color_cached(node, cached_root, new)
- rb_erase_cached(node, cached_root)
In addition, augmented cached interfaces are also added for
basic insertion and deletion operations; which becomes
important for the interval tree changes.
With the exception of the inserts, which adds a bool for
updating the new leftmost, the interfaces are kept the same.
To this end, porting rb users to the cached version becomes really
trivial, and keeping current rbtree semantics for users that
don't care about the optimization requires zero overhead.
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
include/linux/rbtree.h | 11 +++++++++++
include/linux/rbtree_augmented.h | 33 ++++++++++++++++++++++++++++++---
lib/rbtree.c | 34 +++++++++++++++++++++++++++++-----
3 files changed, 70 insertions(+), 8 deletions(-)
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index e585018498d5..eb4544811cfd 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -44,10 +44,15 @@ struct rb_root {
struct rb_node *rb_node;
};
+struct rb_root_cached {
+ struct rb_root rb_root;
+ struct rb_node *rb_leftmost;
+};
#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
#define RB_ROOT (struct rb_root) { NULL, }
+#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
#define rb_entry(ptr, type, member) container_of(ptr, type, member)
#define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL)
@@ -69,6 +74,12 @@ extern struct rb_node *rb_prev(const struct rb_node *);
extern struct rb_node *rb_first(const struct rb_root *);
extern struct rb_node *rb_last(const struct rb_root *);
+extern void rb_insert_color_cached(struct rb_node *,
+ struct rb_root_cached *, bool);
+extern void rb_erase_cached(struct rb_node *node, struct rb_root_cached *);
+/* Same as rb_first(), but O(1) */
+#define rb_first_cached(root) (root)->rb_leftmost;
+
/* Postorder iteration - always visit the parent after its children */
extern struct rb_node *rb_first_postorder(const struct rb_root *);
extern struct rb_node *rb_next_postorder(const struct rb_node *);
diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
index 9702b6e183bc..b84ee26c19d9 100644
--- a/include/linux/rbtree_augmented.h
+++ b/include/linux/rbtree_augmented.h
@@ -41,7 +41,9 @@ struct rb_augment_callbacks {
void (*rotate)(struct rb_node *old, struct rb_node *new);
};
-extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
+extern void __rb_insert_augmented(struct rb_node *node,
+ struct rb_root *root,
+ bool newleft, struct rb_node **leftmost,
void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
/*
* Fixup the rbtree and update the augmented information when rebalancing.
@@ -57,7 +59,16 @@ 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);
+ __rb_insert_augmented(node, root, false, NULL, augment->rotate);
+}
+
+static inline void
+rb_insert_augmented_cached(struct rb_node *node,
+ struct rb_root_cached *root, bool newleft,
+ const struct rb_augment_callbacks *augment)
+{
+ __rb_insert_augmented(node, &root->rb_root,
+ newleft, &root->rb_leftmost, augment->rotate);
}
#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
@@ -150,6 +161,7 @@ extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
static __always_inline struct rb_node *
__rb_erase_augmented(struct rb_node *node, struct rb_root *root,
+ bool cached, struct rb_node **leftmost,
const struct rb_augment_callbacks *augment)
{
struct rb_node *child = node->rb_right;
@@ -157,6 +169,9 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
struct rb_node *parent, *rebalance;
unsigned long pc;
+ if (cached && node == *leftmost)
+ *leftmost = rb_next(node);
+
if (!tmp) {
/*
* Case 1: node to erase has no more than 1 child (easy!)
@@ -256,9 +271,21 @@ static __always_inline void
rb_erase_augmented(struct rb_node *node, struct rb_root *root,
const struct rb_augment_callbacks *augment)
{
- struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);
+ struct rb_node *rebalance = __rb_erase_augmented(node, root,
+ false, NULL, augment);
if (rebalance)
__rb_erase_color(rebalance, root, augment->rotate);
}
+static __always_inline void
+rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root,
+ const struct rb_augment_callbacks *augment)
+{
+ struct rb_node *rebalance = __rb_erase_augmented(node, &root->rb_root,
+ true, &root->rb_leftmost,
+ augment);
+ if (rebalance)
+ __rb_erase_color(rebalance, &root->rb_root, augment->rotate);
+}
+
#endif /* _LINUX_RBTREE_AUGMENTED_H */
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 4ba2828a67c0..6a9ed5e5a71b 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -95,10 +95,14 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
static __always_inline void
__rb_insert(struct rb_node *node, struct rb_root *root,
+ bool newleft, struct rb_node **leftmost,
void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
+ if (newleft)
+ *leftmost = node;
+
while (true) {
/*
* Loop invariant: node is red
@@ -434,19 +438,38 @@ static const struct rb_augment_callbacks dummy_callbacks = {
void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
- __rb_insert(node, root, dummy_rotate);
+ __rb_insert(node, root, false, NULL, dummy_rotate);
}
EXPORT_SYMBOL(rb_insert_color);
void rb_erase(struct rb_node *node, struct rb_root *root)
{
struct rb_node *rebalance;
- rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
+ rebalance = __rb_erase_augmented(node, root,
+ false, NULL, &dummy_callbacks);
if (rebalance)
____rb_erase_color(rebalance, root, dummy_rotate);
}
EXPORT_SYMBOL(rb_erase);
+void rb_insert_color_cached(struct rb_node *node,
+ struct rb_root_cached *root, bool leftmost)
+{
+ __rb_insert(node, &root->rb_root, leftmost,
+ &root->rb_leftmost, dummy_rotate);
+}
+EXPORT_SYMBOL(rb_insert_color_cached);
+
+void rb_erase_cached(struct rb_node *node, struct rb_root_cached *root)
+{
+ struct rb_node *rebalance;
+ rebalance = __rb_erase_augmented(node, &root->rb_root, true,
+ &root->rb_leftmost, &dummy_callbacks);
+ if (rebalance)
+ ____rb_erase_color(rebalance, &root->rb_root, dummy_rotate);
+}
+EXPORT_SYMBOL(rb_erase_cached);
+
/*
* Augmented rbtree manipulation functions.
*
@@ -455,9 +478,10 @@ EXPORT_SYMBOL(rb_erase);
*/
void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
+ bool newleft, struct rb_node **leftmost,
void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
- __rb_insert(node, root, augment_rotate);
+ __rb_insert(node, root, newleft, leftmost, augment_rotate);
}
EXPORT_SYMBOL(__rb_insert_augmented);
@@ -502,7 +526,7 @@ struct rb_node *rb_next(const struct rb_node *node)
* as we can.
*/
if (node->rb_right) {
- node = node->rb_right;
+ node = node->rb_right;
while (node->rb_left)
node=node->rb_left;
return (struct rb_node *)node;
@@ -534,7 +558,7 @@ struct rb_node *rb_prev(const struct rb_node *node)
* as we can.
*/
if (node->rb_left) {
- node = node->rb_left;
+ node = node->rb_left;
while (node->rb_right)
node=node->rb_right;
return (struct rb_node *)node;
--
2.12.0
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH 2/5] sched/fair: Replace cfs_rq->rb_leftmost
2017-05-30 2:09 [rfc PATCH -next 0/5] rbtree: Cache leftmost node internally Davidlohr Bueso
2017-05-30 2:09 ` [PATCH 1/5] " Davidlohr Bueso
@ 2017-05-30 2:09 ` Davidlohr Bueso
2017-05-30 2:09 ` [PATCH 3/5] locking/rtmutex: Replace top-waiter and pi_waiters leftmost caching Davidlohr Bueso
` (4 subsequent siblings)
6 siblings, 0 replies; 12+ messages in thread
From: Davidlohr Bueso @ 2017-05-30 2:09 UTC (permalink / raw)
To: mingo, peterz, akpm
Cc: jack, kirill.shutemov, ldufour, mhocko, mgorman, dave,
linux-kernel, Davidlohr Bueso
... with the generic rbtree flavor instead. No changes
in semantics whatsoever.
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
kernel/sched/debug.c | 2 +-
kernel/sched/fair.c | 35 +++++++++++------------------------
kernel/sched/sched.h | 3 +--
3 files changed, 13 insertions(+), 27 deletions(-)
diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c
index 38f019324f1a..85df87666f6e 100644
--- a/kernel/sched/debug.c
+++ b/kernel/sched/debug.c
@@ -488,7 +488,7 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)
SPLIT_NS(cfs_rq->exec_clock));
raw_spin_lock_irqsave(&rq->lock, flags);
- if (cfs_rq->rb_leftmost)
+ if (cfs_rq->tasks_timeline.rb_leftmost)
MIN_vruntime = (__pick_first_entity(cfs_rq))->vruntime;
last = __pick_last_entity(cfs_rq);
if (last)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 47a0c552c77b..63b0c5f4770a 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -523,8 +523,8 @@ static void update_min_vruntime(struct cfs_rq *cfs_rq)
curr = NULL;
}
- if (cfs_rq->rb_leftmost) {
- struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
+ if (cfs_rq->tasks_timeline.rb_leftmost) {
+ struct sched_entity *se = rb_entry(cfs_rq->tasks_timeline.rb_leftmost,
struct sched_entity,
run_node);
@@ -547,10 +547,10 @@ static void update_min_vruntime(struct cfs_rq *cfs_rq)
*/
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
- struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
+ struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
struct rb_node *parent = NULL;
struct sched_entity *entry;
- int leftmost = 1;
+ bool leftmost = true;
/*
* Find the right place in the rbtree:
@@ -566,36 +566,23 @@ static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
link = &parent->rb_left;
} else {
link = &parent->rb_right;
- leftmost = 0;
+ leftmost = false;
}
}
- /*
- * Maintain a cache of leftmost tree entries (it is frequently
- * used):
- */
- if (leftmost)
- cfs_rq->rb_leftmost = &se->run_node;
-
rb_link_node(&se->run_node, parent, link);
- rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
+ rb_insert_color_cached(&se->run_node,
+ &cfs_rq->tasks_timeline, leftmost);
}
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
- if (cfs_rq->rb_leftmost == &se->run_node) {
- struct rb_node *next_node;
-
- next_node = rb_next(&se->run_node);
- cfs_rq->rb_leftmost = next_node;
- }
-
- rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
+ rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
}
struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
- struct rb_node *left = cfs_rq->rb_leftmost;
+ struct rb_node *left = cfs_rq->tasks_timeline.rb_leftmost;
if (!left)
return NULL;
@@ -616,7 +603,7 @@ static struct sched_entity *__pick_next_entity(struct sched_entity *se)
#ifdef CONFIG_SCHED_DEBUG
struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
{
- struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);
+ struct rb_node *last = rb_last(&cfs_rq->tasks_timeline.rb_root);
if (!last)
return NULL;
@@ -9235,7 +9222,7 @@ static void set_curr_task_fair(struct rq *rq)
void init_cfs_rq(struct cfs_rq *cfs_rq)
{
- cfs_rq->tasks_timeline = RB_ROOT;
+ cfs_rq->tasks_timeline = RB_ROOT_CACHED;
cfs_rq->min_vruntime = (u64)(-(1LL << 20));
#ifndef CONFIG_64BIT
cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index f8cf1d87f065..6fe986abfeee 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -404,8 +404,7 @@ struct cfs_rq {
u64 min_vruntime_copy;
#endif
- struct rb_root tasks_timeline;
- struct rb_node *rb_leftmost;
+ struct rb_root_cached tasks_timeline;
/*
* 'curr' points to currently running entity on this cfs_rq.
--
2.12.0
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH 3/5] locking/rtmutex: Replace top-waiter and pi_waiters leftmost caching
2017-05-30 2:09 [rfc PATCH -next 0/5] rbtree: Cache leftmost node internally Davidlohr Bueso
2017-05-30 2:09 ` [PATCH 1/5] " Davidlohr Bueso
2017-05-30 2:09 ` [PATCH 2/5] sched/fair: Replace cfs_rq->rb_leftmost Davidlohr Bueso
@ 2017-05-30 2:09 ` Davidlohr Bueso
2017-05-30 2:09 ` [PATCH 4/5] sched/deadline: Replace earliest deadline and runqueue " Davidlohr Bueso
` (3 subsequent siblings)
6 siblings, 0 replies; 12+ messages in thread
From: Davidlohr Bueso @ 2017-05-30 2:09 UTC (permalink / raw)
To: mingo, peterz, akpm
Cc: jack, kirill.shutemov, ldufour, mhocko, mgorman, dave,
linux-kernel, Davidlohr Bueso
... with the generic rbtree flavor instead. No changes
in semantics whatsoever.
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
include/linux/init_task.h | 5 ++---
include/linux/rtmutex.h | 9 ++++-----
include/linux/sched.h | 3 +--
kernel/fork.c | 3 +--
kernel/locking/rtmutex-debug.c | 2 +-
kernel/locking/rtmutex.c | 36 ++++++++++++------------------------
kernel/locking/rtmutex_common.h | 10 +++++-----
7 files changed, 26 insertions(+), 42 deletions(-)
diff --git a/include/linux/init_task.h b/include/linux/init_task.h
index e049526bc188..d58c3b072f4a 100644
--- a/include/linux/init_task.h
+++ b/include/linux/init_task.h
@@ -181,9 +181,8 @@ extern struct cred init_cred;
#ifdef CONFIG_RT_MUTEXES
# define INIT_RT_MUTEXES(tsk) \
- .pi_waiters = RB_ROOT, \
- .pi_top_task = NULL, \
- .pi_waiters_leftmost = NULL,
+ .pi_waiters = RB_ROOT_CACHED, \
+ .pi_top_task = NULL,
#else
# define INIT_RT_MUTEXES(tsk)
#endif
diff --git a/include/linux/rtmutex.h b/include/linux/rtmutex.h
index 1abba5ce2a2f..3c65d110fc2d 100644
--- a/include/linux/rtmutex.h
+++ b/include/linux/rtmutex.h
@@ -22,14 +22,13 @@ extern int max_lock_depth; /* for sysctl */
* The rt_mutex structure
*
* @wait_lock: spinlock to protect the structure
- * @waiters: rbtree root to enqueue waiters in priority order
- * @waiters_leftmost: top waiter
+ * @waiters: rbtree root to enqueue waiters in priority order;
+ * caches top-waiter (leftmost node).
* @owner: the mutex owner
*/
struct rt_mutex {
raw_spinlock_t wait_lock;
- struct rb_root waiters;
- struct rb_node *waiters_leftmost;
+ struct rb_root_cached waiters;
struct task_struct *owner;
#ifdef CONFIG_DEBUG_RT_MUTEXES
int save_state;
@@ -68,7 +67,7 @@ struct hrtimer_sleeper;
#define __RT_MUTEX_INITIALIZER(mutexname) \
{ .wait_lock = __RAW_SPIN_LOCK_UNLOCKED(mutexname.wait_lock) \
- , .waiters = RB_ROOT \
+ , .waiters = RB_ROOT_CACHED \
, .owner = NULL \
__DEBUG_RT_MUTEX_INITIALIZER(mutexname)}
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 6c7b5f426598..f909a3cb8d77 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -778,8 +778,7 @@ struct task_struct {
#ifdef CONFIG_RT_MUTEXES
/* PI waiters blocked on a rt_mutex held by this task: */
- struct rb_root pi_waiters;
- struct rb_node *pi_waiters_leftmost;
+ struct rb_root_cached pi_waiters;
/* Updated under owner's pi_lock and rq lock */
struct task_struct *pi_top_task;
/* Deadlock detection and priority inheritance handling: */
diff --git a/kernel/fork.c b/kernel/fork.c
index ebf3ba03c5b8..5e4985192c36 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -1458,8 +1458,7 @@ static void rt_mutex_init_task(struct task_struct *p)
{
raw_spin_lock_init(&p->pi_lock);
#ifdef CONFIG_RT_MUTEXES
- p->pi_waiters = RB_ROOT;
- p->pi_waiters_leftmost = NULL;
+ p->pi_waiters = RB_ROOT_CACHED;
p->pi_top_task = NULL;
p->pi_blocked_on = NULL;
#endif
diff --git a/kernel/locking/rtmutex-debug.c b/kernel/locking/rtmutex-debug.c
index 58e366ad36f4..0e4d0619d06d 100644
--- a/kernel/locking/rtmutex-debug.c
+++ b/kernel/locking/rtmutex-debug.c
@@ -58,7 +58,7 @@ static void printk_lock(struct rt_mutex *lock, int print_owner)
void rt_mutex_debug_task_free(struct task_struct *task)
{
- DEBUG_LOCKS_WARN_ON(!RB_EMPTY_ROOT(&task->pi_waiters));
+ DEBUG_LOCKS_WARN_ON(!RB_EMPTY_ROOT(&task->pi_waiters.rb_root));
DEBUG_LOCKS_WARN_ON(task->pi_blocked_on);
}
diff --git a/kernel/locking/rtmutex.c b/kernel/locking/rtmutex.c
index 28cd09e635ed..1f5d0c9220b4 100644
--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -271,10 +271,10 @@ rt_mutex_waiter_equal(struct rt_mutex_waiter *left,
static void
rt_mutex_enqueue(struct rt_mutex *lock, struct rt_mutex_waiter *waiter)
{
- struct rb_node **link = &lock->waiters.rb_node;
+ struct rb_node **link = &lock->waiters.rb_root.rb_node;
struct rb_node *parent = NULL;
struct rt_mutex_waiter *entry;
- int leftmost = 1;
+ bool leftmost = true;
while (*link) {
parent = *link;
@@ -283,15 +283,12 @@ rt_mutex_enqueue(struct rt_mutex *lock, struct rt_mutex_waiter *waiter)
link = &parent->rb_left;
} else {
link = &parent->rb_right;
- leftmost = 0;
+ leftmost = false;
}
}
- if (leftmost)
- lock->waiters_leftmost = &waiter->tree_entry;
-
rb_link_node(&waiter->tree_entry, parent, link);
- rb_insert_color(&waiter->tree_entry, &lock->waiters);
+ rb_insert_color_cached(&waiter->tree_entry, &lock->waiters, leftmost);
}
static void
@@ -300,20 +297,17 @@ rt_mutex_dequeue(struct rt_mutex *lock, struct rt_mutex_waiter *waiter)
if (RB_EMPTY_NODE(&waiter->tree_entry))
return;
- if (lock->waiters_leftmost == &waiter->tree_entry)
- lock->waiters_leftmost = rb_next(&waiter->tree_entry);
-
- rb_erase(&waiter->tree_entry, &lock->waiters);
+ rb_erase_cached(&waiter->tree_entry, &lock->waiters);
RB_CLEAR_NODE(&waiter->tree_entry);
}
static void
rt_mutex_enqueue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter)
{
- struct rb_node **link = &task->pi_waiters.rb_node;
+ struct rb_node **link = &task->pi_waiters.rb_root.rb_node;
struct rb_node *parent = NULL;
struct rt_mutex_waiter *entry;
- int leftmost = 1;
+ bool leftmost = true;
while (*link) {
parent = *link;
@@ -322,15 +316,13 @@ rt_mutex_enqueue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter)
link = &parent->rb_left;
} else {
link = &parent->rb_right;
- leftmost = 0;
+ leftmost = false;
}
}
- if (leftmost)
- task->pi_waiters_leftmost = &waiter->pi_tree_entry;
-
rb_link_node(&waiter->pi_tree_entry, parent, link);
- rb_insert_color(&waiter->pi_tree_entry, &task->pi_waiters);
+ rb_insert_color_cached(&waiter->pi_tree_entry,
+ &task->pi_waiters, leftmost);
}
static void
@@ -339,10 +331,7 @@ rt_mutex_dequeue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter)
if (RB_EMPTY_NODE(&waiter->pi_tree_entry))
return;
- if (task->pi_waiters_leftmost == &waiter->pi_tree_entry)
- task->pi_waiters_leftmost = rb_next(&waiter->pi_tree_entry);
-
- rb_erase(&waiter->pi_tree_entry, &task->pi_waiters);
+ rb_erase_cached(&waiter->pi_tree_entry, &task->pi_waiters);
RB_CLEAR_NODE(&waiter->pi_tree_entry);
}
@@ -1636,8 +1625,7 @@ void __rt_mutex_init(struct rt_mutex *lock, const char *name)
{
lock->owner = NULL;
raw_spin_lock_init(&lock->wait_lock);
- lock->waiters = RB_ROOT;
- lock->waiters_leftmost = NULL;
+ lock->waiters = RB_ROOT_CACHED;
debug_rt_mutex_init(lock, name);
}
diff --git a/kernel/locking/rtmutex_common.h b/kernel/locking/rtmutex_common.h
index 72ad45a9a794..f0cd41939867 100644
--- a/kernel/locking/rtmutex_common.h
+++ b/kernel/locking/rtmutex_common.h
@@ -42,7 +42,7 @@ struct rt_mutex_waiter {
*/
static inline int rt_mutex_has_waiters(struct rt_mutex *lock)
{
- return !RB_EMPTY_ROOT(&lock->waiters);
+ return !RB_EMPTY_ROOT(&lock->waiters.rb_root);
}
static inline struct rt_mutex_waiter *
@@ -50,8 +50,8 @@ rt_mutex_top_waiter(struct rt_mutex *lock)
{
struct rt_mutex_waiter *w;
- w = rb_entry(lock->waiters_leftmost, struct rt_mutex_waiter,
- tree_entry);
+ w = rb_entry(lock->waiters.rb_leftmost,
+ struct rt_mutex_waiter, tree_entry);
BUG_ON(w->lock != lock);
return w;
@@ -59,13 +59,13 @@ rt_mutex_top_waiter(struct rt_mutex *lock)
static inline int task_has_pi_waiters(struct task_struct *p)
{
- return !RB_EMPTY_ROOT(&p->pi_waiters);
+ return !RB_EMPTY_ROOT(&p->pi_waiters.rb_root);
}
static inline struct rt_mutex_waiter *
task_top_pi_waiter(struct task_struct *p)
{
- return rb_entry(p->pi_waiters_leftmost, struct rt_mutex_waiter,
+ return rb_entry(p->pi_waiters.rb_leftmost, struct rt_mutex_waiter,
pi_tree_entry);
}
--
2.12.0
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH 4/5] sched/deadline: Replace earliest deadline and runqueue leftmost caching
2017-05-30 2:09 [rfc PATCH -next 0/5] rbtree: Cache leftmost node internally Davidlohr Bueso
` (2 preceding siblings ...)
2017-05-30 2:09 ` [PATCH 3/5] locking/rtmutex: Replace top-waiter and pi_waiters leftmost caching Davidlohr Bueso
@ 2017-05-30 2:09 ` Davidlohr Bueso
2017-05-30 2:09 ` [PATCH 5/5] lib/interval_tree: Fast overlap detection Davidlohr Bueso
` (2 subsequent siblings)
6 siblings, 0 replies; 12+ messages in thread
From: Davidlohr Bueso @ 2017-05-30 2:09 UTC (permalink / raw)
To: mingo, peterz, akpm
Cc: jack, kirill.shutemov, ldufour, mhocko, mgorman, dave,
linux-kernel, Davidlohr Bueso
... with the generic rbtree flavor instead. No changes
in semantics whatsoever.
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
kernel/sched/deadline.c | 50 +++++++++++++++++++------------------------------
kernel/sched/sched.h | 6 ++----
2 files changed, 21 insertions(+), 35 deletions(-)
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index df6c2912bd60..4e564276c634 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -47,7 +47,7 @@ static inline int is_leftmost(struct task_struct *p, struct dl_rq *dl_rq)
{
struct sched_dl_entity *dl_se = &p->dl;
- return dl_rq->rb_leftmost == &dl_se->rb_node;
+ return dl_rq->root.rb_leftmost == &dl_se->rb_node;
}
void init_dl_bandwidth(struct dl_bandwidth *dl_b, u64 period, u64 runtime)
@@ -71,7 +71,7 @@ void init_dl_bw(struct dl_bw *dl_b)
void init_dl_rq(struct dl_rq *dl_rq)
{
- dl_rq->rb_root = RB_ROOT;
+ dl_rq->root = RB_ROOT_CACHED;
#ifdef CONFIG_SMP
/* zero means no -deadline tasks */
@@ -79,7 +79,7 @@ void init_dl_rq(struct dl_rq *dl_rq)
dl_rq->dl_nr_migratory = 0;
dl_rq->overloaded = 0;
- dl_rq->pushable_dl_tasks_root = RB_ROOT;
+ dl_rq->pushable_dl_tasks_root = RB_ROOT_CACHED;
#else
init_dl_bw(&dl_rq->dl_bw);
#endif
@@ -157,10 +157,10 @@ static void dec_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
static void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
{
struct dl_rq *dl_rq = &rq->dl;
- struct rb_node **link = &dl_rq->pushable_dl_tasks_root.rb_node;
+ struct rb_node **link = &dl_rq->pushable_dl_tasks_root.rb_root.rb_node;
struct rb_node *parent = NULL;
struct task_struct *entry;
- int leftmost = 1;
+ bool leftmost = true;
BUG_ON(!RB_EMPTY_NODE(&p->pushable_dl_tasks));
@@ -172,17 +172,16 @@ static void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
link = &parent->rb_left;
else {
link = &parent->rb_right;
- leftmost = 0;
+ leftmost = false;
}
}
- if (leftmost) {
- dl_rq->pushable_dl_tasks_leftmost = &p->pushable_dl_tasks;
+ if (leftmost)
dl_rq->earliest_dl.next = p->dl.deadline;
- }
rb_link_node(&p->pushable_dl_tasks, parent, link);
- rb_insert_color(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
+ rb_insert_color_cached(&p->pushable_dl_tasks,
+ &dl_rq->pushable_dl_tasks_root, leftmost);
}
static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
@@ -192,24 +191,23 @@ static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
if (RB_EMPTY_NODE(&p->pushable_dl_tasks))
return;
- if (dl_rq->pushable_dl_tasks_leftmost == &p->pushable_dl_tasks) {
+ if (dl_rq->pushable_dl_tasks_root.rb_leftmost == &p->pushable_dl_tasks) {
struct rb_node *next_node;
next_node = rb_next(&p->pushable_dl_tasks);
- dl_rq->pushable_dl_tasks_leftmost = next_node;
if (next_node) {
dl_rq->earliest_dl.next = rb_entry(next_node,
struct task_struct, pushable_dl_tasks)->dl.deadline;
}
}
- rb_erase(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
+ rb_erase_cached(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
RB_CLEAR_NODE(&p->pushable_dl_tasks);
}
static inline int has_pushable_dl_tasks(struct rq *rq)
{
- return !RB_EMPTY_ROOT(&rq->dl.pushable_dl_tasks_root);
+ return !RB_EMPTY_ROOT(&rq->dl.pushable_dl_tasks_root.rb_root);
}
static int push_dl_task(struct rq *rq);
@@ -841,7 +839,7 @@ static void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
dl_rq->earliest_dl.next = 0;
cpudl_clear(&rq->rd->cpudl, rq->cpu);
} else {
- struct rb_node *leftmost = dl_rq->rb_leftmost;
+ struct rb_node *leftmost = dl_rq->root.rb_leftmost;
struct sched_dl_entity *entry;
entry = rb_entry(leftmost, struct sched_dl_entity, rb_node);
@@ -888,7 +886,7 @@ void dec_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
static void __enqueue_dl_entity(struct sched_dl_entity *dl_se)
{
struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
- struct rb_node **link = &dl_rq->rb_root.rb_node;
+ struct rb_node **link = &dl_rq->root.rb_root.rb_node;
struct rb_node *parent = NULL;
struct sched_dl_entity *entry;
int leftmost = 1;
@@ -906,11 +904,8 @@ static void __enqueue_dl_entity(struct sched_dl_entity *dl_se)
}
}
- if (leftmost)
- dl_rq->rb_leftmost = &dl_se->rb_node;
-
rb_link_node(&dl_se->rb_node, parent, link);
- rb_insert_color(&dl_se->rb_node, &dl_rq->rb_root);
+ rb_insert_color_cached(&dl_se->rb_node, &dl_rq->root, leftmost);
inc_dl_tasks(dl_se, dl_rq);
}
@@ -922,14 +917,7 @@ static void __dequeue_dl_entity(struct sched_dl_entity *dl_se)
if (RB_EMPTY_NODE(&dl_se->rb_node))
return;
- if (dl_rq->rb_leftmost == &dl_se->rb_node) {
- struct rb_node *next_node;
-
- next_node = rb_next(&dl_se->rb_node);
- dl_rq->rb_leftmost = next_node;
- }
-
- rb_erase(&dl_se->rb_node, &dl_rq->rb_root);
+ rb_erase_cached(&dl_se->rb_node, &dl_rq->root);
RB_CLEAR_NODE(&dl_se->rb_node);
dec_dl_tasks(dl_se, dl_rq);
@@ -1160,7 +1148,7 @@ static void start_hrtick_dl(struct rq *rq, struct task_struct *p)
static struct sched_dl_entity *pick_next_dl_entity(struct rq *rq,
struct dl_rq *dl_rq)
{
- struct rb_node *left = dl_rq->rb_leftmost;
+ struct rb_node *left = rb_first_cached(&dl_rq->root);
if (!left)
return NULL;
@@ -1297,7 +1285,7 @@ static int pick_dl_task(struct rq *rq, struct task_struct *p, int cpu)
*/
static struct task_struct *pick_earliest_pushable_dl_task(struct rq *rq, int cpu)
{
- struct rb_node *next_node = rq->dl.pushable_dl_tasks_leftmost;
+ struct rb_node *next_node = rq->dl.pushable_dl_tasks_root.rb_leftmost;
struct task_struct *p = NULL;
if (!has_pushable_dl_tasks(rq))
@@ -1470,7 +1458,7 @@ static struct task_struct *pick_next_pushable_dl_task(struct rq *rq)
if (!has_pushable_dl_tasks(rq))
return NULL;
- p = rb_entry(rq->dl.pushable_dl_tasks_leftmost,
+ p = rb_entry(rq->dl.pushable_dl_tasks_root.rb_leftmost,
struct task_struct, pushable_dl_tasks);
BUG_ON(rq->cpu != task_cpu(p));
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 6fe986abfeee..49c311c10e16 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -527,8 +527,7 @@ struct rt_rq {
/* Deadline class' related fields in a runqueue */
struct dl_rq {
/* runqueue is an rbtree, ordered by deadline */
- struct rb_root rb_root;
- struct rb_node *rb_leftmost;
+ struct rb_root_cached root;
unsigned long dl_nr_running;
@@ -552,8 +551,7 @@ struct dl_rq {
* an rb-tree, ordered by tasks' deadlines, with caching
* of the leftmost (earliest deadline) element.
*/
- struct rb_root pushable_dl_tasks_root;
- struct rb_node *pushable_dl_tasks_leftmost;
+ struct rb_root_cached pushable_dl_tasks_root;
#else
struct dl_bw dl_bw;
#endif
--
2.12.0
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH 5/5] lib/interval_tree: Fast overlap detection
2017-05-30 2:09 [rfc PATCH -next 0/5] rbtree: Cache leftmost node internally Davidlohr Bueso
` (3 preceding siblings ...)
2017-05-30 2:09 ` [PATCH 4/5] sched/deadline: Replace earliest deadline and runqueue " Davidlohr Bueso
@ 2017-05-30 2:09 ` Davidlohr Bueso
2017-05-30 4:54 ` kbuild test robot
2017-06-07 15:05 ` [rfc PATCH -next 0/5] rbtree: Cache leftmost node internally Davidlohr Bueso
2017-06-08 13:42 ` Peter Zijlstra
6 siblings, 1 reply; 12+ messages in thread
From: Davidlohr Bueso @ 2017-05-30 2:09 UTC (permalink / raw)
To: mingo, peterz, akpm
Cc: jack, kirill.shutemov, ldufour, mhocko, mgorman, dave,
linux-kernel, Davidlohr Bueso
Allow interval trees to quickly check for overlaps to avoid
unnecesary tree lookups in interval_tree_iter_first(). Currently
we only do this for searches with ranges completely to the right.
As of this patch, all interval tree flavors will require
using a 'rb_root_cached' such that we can have the leftmost
node easily available. While most users will make use of this
feature, those with special functions (in addition to the generic
insert, delete, search calls) will avoid using the cached
option as they can do funky things with insertions -- for example,
vma_interval_tree_insert_after().
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c | 8 ++--
drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c | 7 ++--
drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h | 2 +-
drivers/gpu/drm/drm_mm.c | 10 ++---
drivers/gpu/drm/drm_vma_manager.c | 2 +-
drivers/gpu/drm/i915/i915_gem_userptr.c | 6 +--
drivers/gpu/drm/radeon/radeon.h | 2 +-
drivers/gpu/drm/radeon/radeon_mn.c | 8 ++--
drivers/gpu/drm/radeon/radeon_vm.c | 7 ++--
drivers/infiniband/core/umem_rbtree.c | 4 +-
drivers/infiniband/core/uverbs_cmd.c | 2 +-
drivers/infiniband/hw/usnic/usnic_uiom.c | 6 +--
drivers/infiniband/hw/usnic/usnic_uiom.h | 2 +-
.../infiniband/hw/usnic/usnic_uiom_interval_tree.c | 15 +++----
.../infiniband/hw/usnic/usnic_uiom_interval_tree.h | 12 +++---
drivers/vhost/vhost.c | 2 +-
drivers/vhost/vhost.h | 2 +-
fs/hugetlbfs/inode.c | 6 +--
fs/inode.c | 2 +-
include/drm/drm_mm.h | 2 +-
include/linux/fs.h | 4 +-
include/linux/interval_tree.h | 8 ++--
include/linux/interval_tree_generic.h | 46 +++++++++++++++++-----
include/linux/mm.h | 17 ++++----
include/linux/rmap.h | 4 +-
include/rdma/ib_umem_odp.h | 11 ++++--
include/rdma/ib_verbs.h | 2 +-
lib/interval_tree_test.c | 4 +-
mm/interval_tree.c | 10 ++---
mm/memory.c | 4 +-
mm/mmap.c | 10 ++---
mm/rmap.c | 4 +-
32 files changed, 134 insertions(+), 97 deletions(-)
diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c b/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c
index 38f739fb727b..3f8aef21b9a6 100644
--- a/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c
+++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c
@@ -51,7 +51,7 @@ struct amdgpu_mn {
/* objects protected by lock */
struct mutex lock;
- struct rb_root objects;
+ struct rb_root_cached objects;
};
struct amdgpu_mn_node {
@@ -76,8 +76,8 @@ static void amdgpu_mn_destroy(struct work_struct *work)
mutex_lock(&adev->mn_lock);
mutex_lock(&rmn->lock);
hash_del(&rmn->node);
- rbtree_postorder_for_each_entry_safe(node, next_node, &rmn->objects,
- it.rb) {
+ rbtree_postorder_for_each_entry_safe(node, next_node,
+ &rmn->objects.rb_root, it.rb) {
list_for_each_entry_safe(bo, next_bo, &node->bos, mn_list) {
bo->mn = NULL;
list_del_init(&bo->mn_list);
@@ -252,7 +252,7 @@ static struct amdgpu_mn *amdgpu_mn_get(struct amdgpu_device *adev)
rmn->mm = mm;
rmn->mn.ops = &amdgpu_mn_ops;
mutex_init(&rmn->lock);
- rmn->objects = RB_ROOT;
+ rmn->objects = RB_ROOT_CACHED;
r = __mmu_notifier_register(&rmn->mn, mm);
if (r)
diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c b/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c
index 83c172a6e938..ab73ace3d38a 100644
--- a/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c
+++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c
@@ -2150,7 +2150,7 @@ int amdgpu_vm_init(struct amdgpu_device *adev, struct amdgpu_vm *vm)
struct amd_sched_rq *rq;
int r;
- vm->va = RB_ROOT;
+ vm->va = RB_ROOT_CACHED;
vm->client_id = atomic64_inc_return(&adev->vm_manager.client_counter);
spin_lock_init(&vm->status_lock);
INIT_LIST_HEAD(&vm->invalidated);
@@ -2239,10 +2239,11 @@ void amdgpu_vm_fini(struct amdgpu_device *adev, struct amdgpu_vm *vm)
amd_sched_entity_fini(vm->entity.sched, &vm->entity);
- if (!RB_EMPTY_ROOT(&vm->va)) {
+ if (!RB_EMPTY_ROOT(&vm->va.rb_root)) {
dev_err(adev->dev, "still active bo inside vm\n");
}
- rbtree_postorder_for_each_entry_safe(mapping, tmp, &vm->va, rb) {
+ rbtree_postorder_for_each_entry_safe(mapping, tmp,
+ &vm->va.rb_root, rb) {
list_del(&mapping->list);
amdgpu_vm_it_remove(mapping, &vm->va);
kfree(mapping);
diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h b/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h
index e1d951ece433..6b2e8309ca70 100644
--- a/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h
+++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h
@@ -96,7 +96,7 @@ struct amdgpu_vm_pt {
struct amdgpu_vm {
/* tree of virtual addresses mapped */
- struct rb_root va;
+ struct rb_root_cached va;
/* protecting invalidated */
spinlock_t status_lock;
diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c
index f794089d30ac..21863f0afb87 100644
--- a/drivers/gpu/drm/drm_mm.c
+++ b/drivers/gpu/drm/drm_mm.c
@@ -169,7 +169,7 @@ INTERVAL_TREE_DEFINE(struct drm_mm_node, rb,
struct drm_mm_node *
__drm_mm_interval_first(const struct drm_mm *mm, u64 start, u64 last)
{
- return drm_mm_interval_tree_iter_first((struct rb_root *)&mm->interval_tree,
+ return drm_mm_interval_tree_iter_first((struct rb_root_cached *)&mm->interval_tree,
start, last) ?: (struct drm_mm_node *)&mm->head_node;
}
EXPORT_SYMBOL(__drm_mm_interval_first);
@@ -198,7 +198,7 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node,
link = &hole_node->rb.rb_right;
} else {
rb = NULL;
- link = &mm->interval_tree.rb_node;
+ link = &mm->interval_tree.rb_root.rb_node;
}
while (*link) {
@@ -214,7 +214,7 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node,
rb_link_node(&node->rb, rb, link);
rb_insert_augmented(&node->rb,
- &mm->interval_tree,
+ &mm->interval_tree.rb_root,
&drm_mm_interval_tree_augment);
}
@@ -577,7 +577,7 @@ void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new)
*new = *old;
list_replace(&old->node_list, &new->node_list);
- rb_replace_node(&old->rb, &new->rb, &old->mm->interval_tree);
+ rb_replace_node(&old->rb, &new->rb, &old->mm->interval_tree.rb_root);
if (drm_mm_hole_follows(old)) {
list_replace(&old->hole_stack, &new->hole_stack);
@@ -863,7 +863,7 @@ void drm_mm_init(struct drm_mm *mm, u64 start, u64 size)
mm->color_adjust = NULL;
INIT_LIST_HEAD(&mm->hole_stack);
- mm->interval_tree = RB_ROOT;
+ mm->interval_tree = RB_ROOT_CACHED;
mm->holes_size = RB_ROOT;
mm->holes_addr = RB_ROOT;
diff --git a/drivers/gpu/drm/drm_vma_manager.c b/drivers/gpu/drm/drm_vma_manager.c
index d9100b565198..28f1226576f8 100644
--- a/drivers/gpu/drm/drm_vma_manager.c
+++ b/drivers/gpu/drm/drm_vma_manager.c
@@ -147,7 +147,7 @@ struct drm_vma_offset_node *drm_vma_offset_lookup_locked(struct drm_vma_offset_m
struct rb_node *iter;
unsigned long offset;
- iter = mgr->vm_addr_space_mm.interval_tree.rb_node;
+ iter = mgr->vm_addr_space_mm.interval_tree.rb_root.rb_node;
best = NULL;
while (likely(iter)) {
diff --git a/drivers/gpu/drm/i915/i915_gem_userptr.c b/drivers/gpu/drm/i915/i915_gem_userptr.c
index 1a0ce1dc68f5..40cd8c32a153 100644
--- a/drivers/gpu/drm/i915/i915_gem_userptr.c
+++ b/drivers/gpu/drm/i915/i915_gem_userptr.c
@@ -49,7 +49,7 @@ struct i915_mmu_notifier {
spinlock_t lock;
struct hlist_node node;
struct mmu_notifier mn;
- struct rb_root objects;
+ struct rb_root_cached objects;
struct workqueue_struct *wq;
};
@@ -123,7 +123,7 @@ static void i915_gem_userptr_mn_invalidate_range_start(struct mmu_notifier *_mn,
struct interval_tree_node *it;
LIST_HEAD(cancelled);
- if (RB_EMPTY_ROOT(&mn->objects))
+ if (RB_EMPTY_ROOT(&mn->objects.rb_root))
return;
/* interval ranges are inclusive, but invalidate range is exclusive */
@@ -172,7 +172,7 @@ i915_mmu_notifier_create(struct mm_struct *mm)
spin_lock_init(&mn->lock);
mn->mn.ops = &i915_gem_userptr_notifier;
- mn->objects = RB_ROOT;
+ mn->objects = RB_ROOT_CACHED;
mn->wq = alloc_workqueue("i915-userptr-release", WQ_UNBOUND, 0);
if (mn->wq == NULL) {
kfree(mn);
diff --git a/drivers/gpu/drm/radeon/radeon.h b/drivers/gpu/drm/radeon/radeon.h
index 342e3b1fb9c7..569915163b57 100644
--- a/drivers/gpu/drm/radeon/radeon.h
+++ b/drivers/gpu/drm/radeon/radeon.h
@@ -937,7 +937,7 @@ struct radeon_vm_id {
struct radeon_vm {
struct mutex mutex;
- struct rb_root va;
+ struct rb_root_cached va;
/* protecting invalidated and freed */
spinlock_t status_lock;
diff --git a/drivers/gpu/drm/radeon/radeon_mn.c b/drivers/gpu/drm/radeon/radeon_mn.c
index 896f2cf51e4e..1d62288b7ee3 100644
--- a/drivers/gpu/drm/radeon/radeon_mn.c
+++ b/drivers/gpu/drm/radeon/radeon_mn.c
@@ -50,7 +50,7 @@ struct radeon_mn {
/* objects protected by lock */
struct mutex lock;
- struct rb_root objects;
+ struct rb_root_cached objects;
};
struct radeon_mn_node {
@@ -75,8 +75,8 @@ static void radeon_mn_destroy(struct work_struct *work)
mutex_lock(&rdev->mn_lock);
mutex_lock(&rmn->lock);
hash_del(&rmn->node);
- rbtree_postorder_for_each_entry_safe(node, next_node, &rmn->objects,
- it.rb) {
+ rbtree_postorder_for_each_entry_safe(node, next_node,
+ &rmn->objects.rb_root, it.rb) {
interval_tree_remove(&node->it, &rmn->objects);
list_for_each_entry_safe(bo, next_bo, &node->bos, mn_list) {
@@ -205,7 +205,7 @@ static struct radeon_mn *radeon_mn_get(struct radeon_device *rdev)
rmn->mm = mm;
rmn->mn.ops = &radeon_mn_ops;
mutex_init(&rmn->lock);
- rmn->objects = RB_ROOT;
+ rmn->objects = RB_ROOT_CACHED;
r = __mmu_notifier_register(&rmn->mn, mm);
if (r)
diff --git a/drivers/gpu/drm/radeon/radeon_vm.c b/drivers/gpu/drm/radeon/radeon_vm.c
index 5f68245579a3..f44777a6c2e8 100644
--- a/drivers/gpu/drm/radeon/radeon_vm.c
+++ b/drivers/gpu/drm/radeon/radeon_vm.c
@@ -1185,7 +1185,7 @@ int radeon_vm_init(struct radeon_device *rdev, struct radeon_vm *vm)
vm->ids[i].last_id_use = NULL;
}
mutex_init(&vm->mutex);
- vm->va = RB_ROOT;
+ vm->va = RB_ROOT_CACHED;
spin_lock_init(&vm->status_lock);
INIT_LIST_HEAD(&vm->invalidated);
INIT_LIST_HEAD(&vm->freed);
@@ -1232,10 +1232,11 @@ void radeon_vm_fini(struct radeon_device *rdev, struct radeon_vm *vm)
struct radeon_bo_va *bo_va, *tmp;
int i, r;
- if (!RB_EMPTY_ROOT(&vm->va)) {
+ if (!RB_EMPTY_ROOT(&vm->va.rb_root)) {
dev_err(rdev->dev, "still active bo inside vm\n");
}
- rbtree_postorder_for_each_entry_safe(bo_va, tmp, &vm->va, it.rb) {
+ rbtree_postorder_for_each_entry_safe(bo_va, tmp,
+ &vm->va.rb_root, it.rb) {
interval_tree_remove(&bo_va->it, &vm->va);
r = radeon_bo_reserve(bo_va->bo, false);
if (!r) {
diff --git a/drivers/infiniband/core/umem_rbtree.c b/drivers/infiniband/core/umem_rbtree.c
index d176597b4d78..fc801920e341 100644
--- a/drivers/infiniband/core/umem_rbtree.c
+++ b/drivers/infiniband/core/umem_rbtree.c
@@ -72,7 +72,7 @@ INTERVAL_TREE_DEFINE(struct umem_odp_node, rb, u64, __subtree_last,
/* @last is not a part of the interval. See comment for function
* node_last.
*/
-int rbt_ib_umem_for_each_in_range(struct rb_root *root,
+int rbt_ib_umem_for_each_in_range(struct rb_root_cached *root,
u64 start, u64 last,
umem_call_back cb,
void *cookie)
@@ -95,7 +95,7 @@ int rbt_ib_umem_for_each_in_range(struct rb_root *root,
}
EXPORT_SYMBOL(rbt_ib_umem_for_each_in_range);
-struct ib_umem_odp *rbt_ib_umem_lookup(struct rb_root *root,
+struct ib_umem_odp *rbt_ib_umem_lookup(struct rb_root_cached *root,
u64 addr, u64 length)
{
struct umem_odp_node *node;
diff --git a/drivers/infiniband/core/uverbs_cmd.c b/drivers/infiniband/core/uverbs_cmd.c
index 0ad3b05405d8..f73d4153dbd0 100644
--- a/drivers/infiniband/core/uverbs_cmd.c
+++ b/drivers/infiniband/core/uverbs_cmd.c
@@ -117,7 +117,7 @@ ssize_t ib_uverbs_get_context(struct ib_uverbs_file *file,
ucontext->closing = 0;
#ifdef CONFIG_INFINIBAND_ON_DEMAND_PAGING
- ucontext->umem_tree = RB_ROOT;
+ ucontext->umem_tree = RB_ROOT_CACHED;
init_rwsem(&ucontext->umem_rwsem);
ucontext->odp_mrs_count = 0;
INIT_LIST_HEAD(&ucontext->no_private_counters);
diff --git a/drivers/infiniband/hw/usnic/usnic_uiom.c b/drivers/infiniband/hw/usnic/usnic_uiom.c
index c49db7c33979..4381c0a9a873 100644
--- a/drivers/infiniband/hw/usnic/usnic_uiom.c
+++ b/drivers/infiniband/hw/usnic/usnic_uiom.c
@@ -227,7 +227,7 @@ static void __usnic_uiom_reg_release(struct usnic_uiom_pd *pd,
vpn_last = vpn_start + npages - 1;
spin_lock(&pd->lock);
- usnic_uiom_remove_interval(&pd->rb_root, vpn_start,
+ usnic_uiom_remove_interval(&pd->root, vpn_start,
vpn_last, &rm_intervals);
usnic_uiom_unmap_sorted_intervals(&rm_intervals, pd);
@@ -379,7 +379,7 @@ struct usnic_uiom_reg *usnic_uiom_reg_get(struct usnic_uiom_pd *pd,
err = usnic_uiom_get_intervals_diff(vpn_start, vpn_last,
(writable) ? IOMMU_WRITE : 0,
IOMMU_WRITE,
- &pd->rb_root,
+ &pd->root,
&sorted_diff_intervals);
if (err) {
usnic_err("Failed disjoint interval vpn [0x%lx,0x%lx] err %d\n",
@@ -395,7 +395,7 @@ struct usnic_uiom_reg *usnic_uiom_reg_get(struct usnic_uiom_pd *pd,
}
- err = usnic_uiom_insert_interval(&pd->rb_root, vpn_start, vpn_last,
+ err = usnic_uiom_insert_interval(&pd->root, vpn_start, vpn_last,
(writable) ? IOMMU_WRITE : 0);
if (err) {
usnic_err("Failed insert interval vpn [0x%lx,0x%lx] err %d\n",
diff --git a/drivers/infiniband/hw/usnic/usnic_uiom.h b/drivers/infiniband/hw/usnic/usnic_uiom.h
index 45ca7c1613a7..431efe4143f4 100644
--- a/drivers/infiniband/hw/usnic/usnic_uiom.h
+++ b/drivers/infiniband/hw/usnic/usnic_uiom.h
@@ -55,7 +55,7 @@ struct usnic_uiom_dev {
struct usnic_uiom_pd {
struct iommu_domain *domain;
spinlock_t lock;
- struct rb_root rb_root;
+ struct rb_root_cached root;
struct list_head devs;
int dev_cnt;
};
diff --git a/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c b/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c
index 42b4b4c4e452..d399523206c7 100644
--- a/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c
+++ b/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c
@@ -100,9 +100,9 @@ static int interval_cmp(void *priv, struct list_head *a, struct list_head *b)
}
static void
-find_intervals_intersection_sorted(struct rb_root *root, unsigned long start,
- unsigned long last,
- struct list_head *list)
+find_intervals_intersection_sorted(struct rb_root_cached *root,
+ unsigned long start, unsigned long last,
+ struct list_head *list)
{
struct usnic_uiom_interval_node *node;
@@ -118,7 +118,7 @@ find_intervals_intersection_sorted(struct rb_root *root, unsigned long start,
int usnic_uiom_get_intervals_diff(unsigned long start, unsigned long last,
int flags, int flag_mask,
- struct rb_root *root,
+ struct rb_root_cached *root,
struct list_head *diff_set)
{
struct usnic_uiom_interval_node *interval, *tmp;
@@ -175,7 +175,7 @@ void usnic_uiom_put_interval_set(struct list_head *intervals)
kfree(interval);
}
-int usnic_uiom_insert_interval(struct rb_root *root, unsigned long start,
+int usnic_uiom_insert_interval(struct rb_root_cached *root, unsigned long start,
unsigned long last, int flags)
{
struct usnic_uiom_interval_node *interval, *tmp;
@@ -246,8 +246,9 @@ int usnic_uiom_insert_interval(struct rb_root *root, unsigned long start,
return err;
}
-void usnic_uiom_remove_interval(struct rb_root *root, unsigned long start,
- unsigned long last, struct list_head *removed)
+void usnic_uiom_remove_interval(struct rb_root_cached *root,
+ unsigned long start, unsigned long last,
+ struct list_head *removed)
{
struct usnic_uiom_interval_node *interval;
diff --git a/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.h b/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.h
index c0b0b876ab90..1d7fc3226bca 100644
--- a/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.h
+++ b/drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.h
@@ -48,12 +48,12 @@ struct usnic_uiom_interval_node {
extern void
usnic_uiom_interval_tree_insert(struct usnic_uiom_interval_node *node,
- struct rb_root *root);
+ struct rb_root_cached *root);
extern void
usnic_uiom_interval_tree_remove(struct usnic_uiom_interval_node *node,
- struct rb_root *root);
+ struct rb_root_cached *root);
extern struct usnic_uiom_interval_node *
-usnic_uiom_interval_tree_iter_first(struct rb_root *root,
+usnic_uiom_interval_tree_iter_first(struct rb_root_cached *root,
unsigned long start,
unsigned long last);
extern struct usnic_uiom_interval_node *
@@ -63,7 +63,7 @@ usnic_uiom_interval_tree_iter_next(struct usnic_uiom_interval_node *node,
* Inserts {start...last} into {root}. If there are overlaps,
* nodes will be broken up and merged
*/
-int usnic_uiom_insert_interval(struct rb_root *root,
+int usnic_uiom_insert_interval(struct rb_root_cached *root,
unsigned long start, unsigned long last,
int flags);
/*
@@ -71,7 +71,7 @@ int usnic_uiom_insert_interval(struct rb_root *root,
* 'removed.' The caller is responsibile for freeing memory of nodes in
* 'removed.'
*/
-void usnic_uiom_remove_interval(struct rb_root *root,
+void usnic_uiom_remove_interval(struct rb_root_cached *root,
unsigned long start, unsigned long last,
struct list_head *removed);
/*
@@ -81,7 +81,7 @@ void usnic_uiom_remove_interval(struct rb_root *root,
int usnic_uiom_get_intervals_diff(unsigned long start,
unsigned long last, int flags,
int flag_mask,
- struct rb_root *root,
+ struct rb_root_cached *root,
struct list_head *diff_set);
/* Call this to free diff_set returned by usnic_uiom_get_intervals_diff */
void usnic_uiom_put_interval_set(struct list_head *intervals);
diff --git a/drivers/vhost/vhost.c b/drivers/vhost/vhost.c
index 042030e5a035..80ea4b23e097 100644
--- a/drivers/vhost/vhost.c
+++ b/drivers/vhost/vhost.c
@@ -1272,7 +1272,7 @@ static struct vhost_umem *vhost_umem_alloc(void)
if (!umem)
return NULL;
- umem->umem_tree = RB_ROOT;
+ umem->umem_tree = RB_ROOT_CACHED;
umem->numem = 0;
INIT_LIST_HEAD(&umem->umem_list);
diff --git a/drivers/vhost/vhost.h b/drivers/vhost/vhost.h
index f55671d53f28..4e2e54cc4102 100644
--- a/drivers/vhost/vhost.h
+++ b/drivers/vhost/vhost.h
@@ -71,7 +71,7 @@ struct vhost_umem_node {
};
struct vhost_umem {
- struct rb_root umem_tree;
+ struct rb_root_cached umem_tree;
struct list_head umem_list;
int numem;
};
diff --git a/fs/hugetlbfs/inode.c b/fs/hugetlbfs/inode.c
index dde861387a40..a1ba7835bd60 100644
--- a/fs/hugetlbfs/inode.c
+++ b/fs/hugetlbfs/inode.c
@@ -334,7 +334,7 @@ static void remove_huge_page(struct page *page)
}
static void
-hugetlb_vmdelete_list(struct rb_root *root, pgoff_t start, pgoff_t end)
+hugetlb_vmdelete_list(struct rb_root_cached *root, pgoff_t start, pgoff_t end)
{
struct vm_area_struct *vma;
@@ -514,7 +514,7 @@ static int hugetlb_vmtruncate(struct inode *inode, loff_t offset)
i_size_write(inode, offset);
i_mmap_lock_write(mapping);
- if (!RB_EMPTY_ROOT(&mapping->i_mmap))
+ if (!RB_EMPTY_ROOT(&mapping->i_mmap.rb_root))
hugetlb_vmdelete_list(&mapping->i_mmap, pgoff, 0);
i_mmap_unlock_write(mapping);
remove_inode_hugepages(inode, offset, LLONG_MAX);
@@ -539,7 +539,7 @@ static long hugetlbfs_punch_hole(struct inode *inode, loff_t offset, loff_t len)
inode_lock(inode);
i_mmap_lock_write(mapping);
- if (!RB_EMPTY_ROOT(&mapping->i_mmap))
+ if (!RB_EMPTY_ROOT(&mapping->i_mmap.rb_root))
hugetlb_vmdelete_list(&mapping->i_mmap,
hole_start >> PAGE_SHIFT,
hole_end >> PAGE_SHIFT);
diff --git a/fs/inode.c b/fs/inode.c
index a25b9d5fb52e..afeedfc096bb 100644
--- a/fs/inode.c
+++ b/fs/inode.c
@@ -352,7 +352,7 @@ void address_space_init_once(struct address_space *mapping)
init_rwsem(&mapping->i_mmap_rwsem);
INIT_LIST_HEAD(&mapping->private_list);
spin_lock_init(&mapping->private_lock);
- mapping->i_mmap = RB_ROOT;
+ mapping->i_mmap = RB_ROOT_CACHED;
}
EXPORT_SYMBOL(address_space_init_once);
diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h
index 49b292e98fec..8d10fc97801c 100644
--- a/include/drm/drm_mm.h
+++ b/include/drm/drm_mm.h
@@ -172,7 +172,7 @@ struct drm_mm {
* according to the (increasing) start address of the memory node. */
struct drm_mm_node head_node;
/* Keep an interval_tree for fast lookup of drm_mm_nodes by address. */
- struct rb_root interval_tree;
+ struct rb_root_cached interval_tree;
struct rb_root holes_size;
struct rb_root holes_addr;
diff --git a/include/linux/fs.h b/include/linux/fs.h
index aa4affb38c39..0aaaa9bc3d4b 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -379,7 +379,7 @@ struct address_space {
struct radix_tree_root page_tree; /* radix tree of all pages */
spinlock_t tree_lock; /* and lock protecting it */
atomic_t i_mmap_writable;/* count VM_SHARED mappings */
- struct rb_root i_mmap; /* tree of private and shared mappings */
+ struct rb_root_cached i_mmap; /* tree of private and shared mappings */
struct rw_semaphore i_mmap_rwsem; /* protect tree, count, list */
/* Protected by tree_lock together with the radix tree */
unsigned long nrpages; /* number of total pages */
@@ -472,7 +472,7 @@ static inline void i_mmap_unlock_read(struct address_space *mapping)
*/
static inline int mapping_mapped(struct address_space *mapping)
{
- return !RB_EMPTY_ROOT(&mapping->i_mmap);
+ return !RB_EMPTY_ROOT(&mapping->i_mmap.rb_root);
}
/*
diff --git a/include/linux/interval_tree.h b/include/linux/interval_tree.h
index 724556aa3c95..202ee1283f4b 100644
--- a/include/linux/interval_tree.h
+++ b/include/linux/interval_tree.h
@@ -11,13 +11,15 @@ struct interval_tree_node {
};
extern void
-interval_tree_insert(struct interval_tree_node *node, struct rb_root *root);
+interval_tree_insert(struct interval_tree_node *node,
+ struct rb_root_cached *root);
extern void
-interval_tree_remove(struct interval_tree_node *node, struct rb_root *root);
+interval_tree_remove(struct interval_tree_node *node,
+ struct rb_root_cached *root);
extern struct interval_tree_node *
-interval_tree_iter_first(struct rb_root *root,
+interval_tree_iter_first(struct rb_root_cached *root,
unsigned long start, unsigned long last);
extern struct interval_tree_node *
diff --git a/include/linux/interval_tree_generic.h b/include/linux/interval_tree_generic.h
index 58370e1862ad..f096423c8cbd 100644
--- a/include/linux/interval_tree_generic.h
+++ b/include/linux/interval_tree_generic.h
@@ -65,11 +65,13 @@ RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB, \
\
/* Insert / remove interval nodes from the tree */ \
\
-ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, struct rb_root *root) \
+ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, \
+ struct rb_root_cached *root) \
{ \
- struct rb_node **link = &root->rb_node, *rb_parent = NULL; \
+ struct rb_node **link = &root->rb_root.rb_node, *rb_parent = NULL; \
ITTYPE start = ITSTART(node), last = ITLAST(node); \
ITSTRUCT *parent; \
+ bool leftmost = true; \
\
while (*link) { \
rb_parent = *link; \
@@ -78,18 +80,22 @@ ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, struct rb_root *root) \
parent->ITSUBTREE = last; \
if (start < ITSTART(parent)) \
link = &parent->ITRB.rb_left; \
- else \
+ else { \
link = &parent->ITRB.rb_right; \
+ leftmost = false; \
+ } \
} \
\
node->ITSUBTREE = last; \
rb_link_node(&node->ITRB, rb_parent, link); \
- rb_insert_augmented(&node->ITRB, root, &ITPREFIX ## _augment); \
+ rb_insert_augmented_cached(&node->ITRB, root, \
+ leftmost, &ITPREFIX ## _augment); \
} \
\
-ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, struct rb_root *root) \
+ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, \
+ struct rb_root_cached *root) \
{ \
- rb_erase_augmented(&node->ITRB, root, &ITPREFIX ## _augment); \
+ rb_erase_augmented_cached(&node->ITRB, root, &ITPREFIX ## _augment); \
} \
\
/* \
@@ -140,15 +146,35 @@ ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \
} \
\
ITSTATIC ITSTRUCT * \
-ITPREFIX ## _iter_first(struct rb_root *root, ITTYPE start, ITTYPE last) \
+ITPREFIX ## _iter_first(struct rb_root_cached *root, \
+ ITTYPE start, ITTYPE last) \
{ \
- ITSTRUCT *node; \
+ ITSTRUCT *node, *leftmost; \
\
- if (!root->rb_node) \
+ if (!root->rb_root.rb_node) \
return NULL; \
- node = rb_entry(root->rb_node, ITSTRUCT, ITRB); \
+ \
+ /* \
+ * Fastpath range intersection/overlap between A: [a0, a1] and \
+ * B: [b0, b1] is given by: \
+ * \
+ * a0 <= b1 && b0 <= a1 \
+ * \
+ * ... where A holds the lock range and B holds the smallest \
+ * 'start' and largest 'last' in the tree. For the later, we \
+ * rely on the root node, which by augmented interval tree \
+ * property, holds the largest value in its last-in-subtree. \
+ * This allows mitigating some of the tree walk overhead for \
+ * for non-intersecting ranges, maintained and consulted in O(1). \
+ */ \
+ node = rb_entry(root->rb_root.rb_node, ITSTRUCT, ITRB); \
if (node->ITSUBTREE < start) \
return NULL; \
+ \
+ leftmost = rb_entry(root->rb_leftmost, ITSTRUCT, ITRB); \
+ if (ITSTART(leftmost) > last) \
+ return NULL; \
+ \
return ITPREFIX ## _subtree_search(node, start, last); \
} \
\
diff --git a/include/linux/mm.h b/include/linux/mm.h
index c0b1759304ec..feb47006e2f5 100644
--- a/include/linux/mm.h
+++ b/include/linux/mm.h
@@ -2020,13 +2020,13 @@ extern int nommu_shrink_inode_mappings(struct inode *, size_t, size_t);
/* interval_tree.c */
void vma_interval_tree_insert(struct vm_area_struct *node,
- struct rb_root *root);
+ struct rb_root_cached *root);
void vma_interval_tree_insert_after(struct vm_area_struct *node,
struct vm_area_struct *prev,
- struct rb_root *root);
+ struct rb_root_cached *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,
+ struct rb_root_cached *root);
+struct vm_area_struct *vma_interval_tree_iter_first(struct rb_root_cached *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);
@@ -2036,11 +2036,12 @@ struct vm_area_struct *vma_interval_tree_iter_next(struct vm_area_struct *node,
vma; vma = vma_interval_tree_iter_next(vma, start, last))
void anon_vma_interval_tree_insert(struct anon_vma_chain *node,
- struct rb_root *root);
+ struct rb_root_cached *root);
void anon_vma_interval_tree_remove(struct anon_vma_chain *node,
- struct rb_root *root);
-struct anon_vma_chain *anon_vma_interval_tree_iter_first(
- struct rb_root *root, unsigned long start, unsigned long last);
+ struct rb_root_cached *root);
+struct anon_vma_chain *
+anon_vma_interval_tree_iter_first(struct rb_root_cached *root,
+ unsigned long start, unsigned long last);
struct anon_vma_chain *anon_vma_interval_tree_iter_next(
struct anon_vma_chain *node, unsigned long start, unsigned long last);
#ifdef CONFIG_DEBUG_VM_RB
diff --git a/include/linux/rmap.h b/include/linux/rmap.h
index 43ef2c30cb0f..22c298c6cc26 100644
--- a/include/linux/rmap.h
+++ b/include/linux/rmap.h
@@ -55,7 +55,9 @@ struct anon_vma {
* is serialized by a system wide lock only visible to
* mm_take_all_locks() (mm_all_locks_mutex).
*/
- struct rb_root rb_root; /* Interval tree of private "related" vmas */
+
+ /* Interval tree of private "related" vmas */
+ struct rb_root_cached rb_root;
};
/*
diff --git a/include/rdma/ib_umem_odp.h b/include/rdma/ib_umem_odp.h
index fb67554aabd6..5eb7f5bc8248 100644
--- a/include/rdma/ib_umem_odp.h
+++ b/include/rdma/ib_umem_odp.h
@@ -111,22 +111,25 @@ int ib_umem_odp_map_dma_pages(struct ib_umem *umem, u64 start_offset, u64 bcnt,
void ib_umem_odp_unmap_dma_pages(struct ib_umem *umem, u64 start_offset,
u64 bound);
-void rbt_ib_umem_insert(struct umem_odp_node *node, struct rb_root *root);
-void rbt_ib_umem_remove(struct umem_odp_node *node, struct rb_root *root);
+void rbt_ib_umem_insert(struct umem_odp_node *node,
+ struct rb_root_cached *root);
+void rbt_ib_umem_remove(struct umem_odp_node *node,
+ struct rb_root_cached *root);
typedef int (*umem_call_back)(struct ib_umem *item, u64 start, u64 end,
void *cookie);
/*
* Call the callback on each ib_umem in the range. Returns the logical or of
* the return values of the functions called.
*/
-int rbt_ib_umem_for_each_in_range(struct rb_root *root, u64 start, u64 end,
+int rbt_ib_umem_for_each_in_range(struct rb_root_cached *root,
+ u64 start, u64 end,
umem_call_back cb, void *cookie);
/*
* Find first region intersecting with address range.
* Return NULL if not found
*/
-struct ib_umem_odp *rbt_ib_umem_lookup(struct rb_root *root,
+struct ib_umem_odp *rbt_ib_umem_lookup(struct rb_root_cached *root,
u64 addr, u64 length);
static inline int ib_umem_mmu_notifier_retry(struct ib_umem *item,
diff --git a/include/rdma/ib_verbs.h b/include/rdma/ib_verbs.h
index 0e480a5630d4..3b54b19a8eac 100644
--- a/include/rdma/ib_verbs.h
+++ b/include/rdma/ib_verbs.h
@@ -1417,7 +1417,7 @@ struct ib_ucontext {
struct pid *tgid;
#ifdef CONFIG_INFINIBAND_ON_DEMAND_PAGING
- struct rb_root umem_tree;
+ struct rb_root_cached umem_tree;
/*
* Protects .umem_rbroot and tree, as well as odp_mrs_count and
* mmu notifiers registration.
diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c
index df495fe81421..0e343fd29570 100644
--- a/lib/interval_tree_test.c
+++ b/lib/interval_tree_test.c
@@ -19,14 +19,14 @@ __param(bool, search_all, false, "Searches will iterate all nodes in the tree");
__param(uint, max_endpoint, ~0, "Largest value for the interval's endpoint");
-static struct rb_root root = RB_ROOT;
+static struct rb_root_cached root = RB_ROOT_CACHED;
static struct interval_tree_node *nodes = NULL;
static u32 *queries = NULL;
static struct rnd_state rnd;
static inline unsigned long
-search(struct rb_root *root, unsigned long start, unsigned long last)
+search(struct rb_root_cached *root, unsigned long start, unsigned long last)
{
struct interval_tree_node *node;
unsigned long results = 0;
diff --git a/mm/interval_tree.c b/mm/interval_tree.c
index f2c2492681bf..b47664358796 100644
--- a/mm/interval_tree.c
+++ b/mm/interval_tree.c
@@ -28,7 +28,7 @@ INTERVAL_TREE_DEFINE(struct vm_area_struct, shared.rb,
/* Insert node immediately after prev in the interval tree */
void vma_interval_tree_insert_after(struct vm_area_struct *node,
struct vm_area_struct *prev,
- struct rb_root *root)
+ struct rb_root_cached *root)
{
struct rb_node **link;
struct vm_area_struct *parent;
@@ -55,7 +55,7 @@ void vma_interval_tree_insert_after(struct vm_area_struct *node,
node->shared.rb_subtree_last = last;
rb_link_node(&node->shared.rb, &parent->shared.rb, link);
- rb_insert_augmented(&node->shared.rb, root,
+ rb_insert_augmented(&node->shared.rb, &root->rb_root,
&vma_interval_tree_augment);
}
@@ -74,7 +74,7 @@ INTERVAL_TREE_DEFINE(struct anon_vma_chain, rb, unsigned long, rb_subtree_last,
static inline, __anon_vma_interval_tree)
void anon_vma_interval_tree_insert(struct anon_vma_chain *node,
- struct rb_root *root)
+ struct rb_root_cached *root)
{
#ifdef CONFIG_DEBUG_VM_RB
node->cached_vma_start = avc_start_pgoff(node);
@@ -84,13 +84,13 @@ void anon_vma_interval_tree_insert(struct anon_vma_chain *node,
}
void anon_vma_interval_tree_remove(struct anon_vma_chain *node,
- struct rb_root *root)
+ struct rb_root_cached *root)
{
__anon_vma_interval_tree_remove(node, root);
}
struct anon_vma_chain *
-anon_vma_interval_tree_iter_first(struct rb_root *root,
+anon_vma_interval_tree_iter_first(struct rb_root_cached *root,
unsigned long first, unsigned long last)
{
return __anon_vma_interval_tree_iter_first(root, first, last);
diff --git a/mm/memory.c b/mm/memory.c
index 206902395512..44200e6671e1 100644
--- a/mm/memory.c
+++ b/mm/memory.c
@@ -2593,7 +2593,7 @@ 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 rb_root *root,
+static inline void unmap_mapping_range_tree(struct rb_root_cached *root,
struct zap_details *details)
{
struct vm_area_struct *vma;
@@ -2657,7 +2657,7 @@ void unmap_mapping_range(struct address_space *mapping,
details.last_index = ULONG_MAX;
i_mmap_lock_write(mapping);
- if (unlikely(!RB_EMPTY_ROOT(&mapping->i_mmap)))
+ if (unlikely(!RB_EMPTY_ROOT(&mapping->i_mmap.rb_root)))
unmap_mapping_range_tree(&mapping->i_mmap, &details);
i_mmap_unlock_write(mapping);
}
diff --git a/mm/mmap.c b/mm/mmap.c
index 3bd5ecd20d4d..31482e1f008a 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -670,7 +670,7 @@ int __vma_adjust(struct vm_area_struct *vma, unsigned long start,
struct mm_struct *mm = vma->vm_mm;
struct vm_area_struct *next = vma->vm_next, *orig_vma = vma;
struct address_space *mapping = NULL;
- struct rb_root *root = NULL;
+ struct rb_root_cached *root = NULL;
struct anon_vma *anon_vma = NULL;
struct file *file = vma->vm_file;
bool start_changed = false, end_changed = false;
@@ -3279,7 +3279,7 @@ static DEFINE_MUTEX(mm_all_locks_mutex);
static void vm_lock_anon_vma(struct mm_struct *mm, struct anon_vma *anon_vma)
{
- if (!test_bit(0, (unsigned long *) &anon_vma->root->rb_root.rb_node)) {
+ if (!test_bit(0, (unsigned long *) &anon_vma->rb_root.rb_root.rb_node)) {
/*
* The LSB of head.next can't change from under us
* because we hold the mm_all_locks_mutex.
@@ -3295,7 +3295,7 @@ static void vm_lock_anon_vma(struct mm_struct *mm, struct anon_vma *anon_vma)
* anon_vma->root->rwsem.
*/
if (__test_and_set_bit(0, (unsigned long *)
- &anon_vma->root->rb_root.rb_node))
+ &anon_vma->root->rb_root.rb_root.rb_node))
BUG();
}
}
@@ -3397,7 +3397,7 @@ int mm_take_all_locks(struct mm_struct *mm)
static void vm_unlock_anon_vma(struct anon_vma *anon_vma)
{
- if (test_bit(0, (unsigned long *) &anon_vma->root->rb_root.rb_node)) {
+ if (test_bit(0, (unsigned long *) &anon_vma->root->rb_root.rb_root.rb_node)) {
/*
* The LSB of head.next can't change to 0 from under
* us because we hold the mm_all_locks_mutex.
@@ -3411,7 +3411,7 @@ static void vm_unlock_anon_vma(struct anon_vma *anon_vma)
* anon_vma->root->rwsem.
*/
if (!__test_and_clear_bit(0, (unsigned long *)
- &anon_vma->root->rb_root.rb_node))
+ &anon_vma->root->rb_root.rb_root.rb_node))
BUG();
anon_vma_unlock_write(anon_vma);
}
diff --git a/mm/rmap.c b/mm/rmap.c
index b255743351e5..0107503b2adb 100644
--- a/mm/rmap.c
+++ b/mm/rmap.c
@@ -390,7 +390,7 @@ void unlink_anon_vmas(struct vm_area_struct *vma)
* Leave empty anon_vmas on the list - we'll need
* to free them outside the lock.
*/
- if (RB_EMPTY_ROOT(&anon_vma->rb_root)) {
+ if (RB_EMPTY_ROOT(&anon_vma->rb_root.rb_root)) {
anon_vma->parent->degree--;
continue;
}
@@ -424,7 +424,7 @@ static void anon_vma_ctor(void *data)
init_rwsem(&anon_vma->rwsem);
atomic_set(&anon_vma->refcount, 0);
- anon_vma->rb_root = RB_ROOT;
+ anon_vma->rb_root = RB_ROOT_CACHED;
}
void __init anon_vma_init(void)
--
2.12.0
^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [PATCH 5/5] lib/interval_tree: Fast overlap detection
2017-05-30 2:09 ` [PATCH 5/5] lib/interval_tree: Fast overlap detection Davidlohr Bueso
@ 2017-05-30 4:54 ` kbuild test robot
2017-05-30 15:44 ` Davidlohr Bueso
0 siblings, 1 reply; 12+ messages in thread
From: kbuild test robot @ 2017-05-30 4:54 UTC (permalink / raw)
To: Davidlohr Bueso
Cc: kbuild-all, mingo, peterz, akpm, jack, kirill.shutemov, ldufour,
mhocko, mgorman, dave, linux-kernel, Davidlohr Bueso
[-- Attachment #1: Type: text/plain, Size: 25895 bytes --]
Hi Davidlohr,
[auto build test ERROR on next-20170529]
url: https://github.com/0day-ci/linux/commits/Davidlohr-Bueso/rbtree-Cache-leftmost-node-internally/20170530-101713
config: x86_64-allmodconfig (attached as .config)
compiler: gcc-6 (Debian 6.2.0-3) 6.2.0 20160901
reproduce:
# save the attached .config to linux build tree
make ARCH=x86_64
All errors (new ones prefixed by >>):
include/linux/compiler.h:260:8: sparse: attribute 'no_sanitize_address': unknown attribute
drivers/infiniband/hw/hfi1/mmu_rb.c: In function 'hfi1_mmu_rb_insert':
>> drivers/infiniband/hw/hfi1/mmu_rb.c:183:29: error: passing argument 2 of '__mmu_int_rb_insert' from incompatible pointer type [-Werror=incompatible-pointer-types]
__mmu_int_rb_insert(mnode, &handler->root);
^
In file included from drivers/infiniband/hw/hfi1/mmu_rb.c:50:0:
drivers/infiniband/hw/hfi1/mmu_rb.c:90:47: note: expected 'struct rb_root_cached *' but argument is of type 'struct rb_root *'
mmu_node_start, mmu_node_last, static, __mmu_int_rb);
^
include/linux/interval_tree_generic.h:68:15: note: in definition of macro 'INTERVAL_TREE_DEFINE'
ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, \
^~~~~~~~
>> drivers/infiniband/hw/hfi1/mmu_rb.c:188:30: error: passing argument 2 of '__mmu_int_rb_remove' from incompatible pointer type [-Werror=incompatible-pointer-types]
__mmu_int_rb_remove(mnode, &handler->root);
^
In file included from drivers/infiniband/hw/hfi1/mmu_rb.c:50:0:
drivers/infiniband/hw/hfi1/mmu_rb.c:90:47: note: expected 'struct rb_root_cached *' but argument is of type 'struct rb_root *'
mmu_node_start, mmu_node_last, static, __mmu_int_rb);
^
include/linux/interval_tree_generic.h:95:15: note: in definition of macro 'INTERVAL_TREE_DEFINE'
ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, \
^~~~~~~~
drivers/infiniband/hw/hfi1/mmu_rb.c: In function '__mmu_rb_search':
>> drivers/infiniband/hw/hfi1/mmu_rb.c:205:34: error: passing argument 1 of '__mmu_int_rb_iter_first' from incompatible pointer type [-Werror=incompatible-pointer-types]
node = __mmu_int_rb_iter_first(&handler->root, addr,
^
In file included from drivers/infiniband/hw/hfi1/mmu_rb.c:50:0:
drivers/infiniband/hw/hfi1/mmu_rb.c:90:47: note: expected 'struct rb_root_cached *' but argument is of type 'struct rb_root *'
mmu_node_start, mmu_node_last, static, __mmu_int_rb);
^
include/linux/interval_tree_generic.h:149:1: note: in definition of macro 'INTERVAL_TREE_DEFINE'
ITPREFIX ## _iter_first(struct rb_root_cached *root, \
^~~~~~~~
drivers/infiniband/hw/hfi1/mmu_rb.c:208:39: error: passing argument 1 of '__mmu_int_rb_iter_first' from incompatible pointer type [-Werror=incompatible-pointer-types]
for (node = __mmu_int_rb_iter_first(&handler->root, addr,
^
In file included from drivers/infiniband/hw/hfi1/mmu_rb.c:50:0:
drivers/infiniband/hw/hfi1/mmu_rb.c:90:47: note: expected 'struct rb_root_cached *' but argument is of type 'struct rb_root *'
mmu_node_start, mmu_node_last, static, __mmu_int_rb);
^
include/linux/interval_tree_generic.h:149:1: note: in definition of macro 'INTERVAL_TREE_DEFINE'
ITPREFIX ## _iter_first(struct rb_root_cached *root, \
^~~~~~~~
drivers/infiniband/hw/hfi1/mmu_rb.c: In function 'hfi1_mmu_rb_extract':
drivers/infiniband/hw/hfi1/mmu_rb.c:229:29: error: passing argument 2 of '__mmu_int_rb_remove' from incompatible pointer type [-Werror=incompatible-pointer-types]
__mmu_int_rb_remove(node, &handler->root);
^
In file included from drivers/infiniband/hw/hfi1/mmu_rb.c:50:0:
drivers/infiniband/hw/hfi1/mmu_rb.c:90:47: note: expected 'struct rb_root_cached *' but argument is of type 'struct rb_root *'
mmu_node_start, mmu_node_last, static, __mmu_int_rb);
^
include/linux/interval_tree_generic.h:95:15: note: in definition of macro 'INTERVAL_TREE_DEFINE'
ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, \
^~~~~~~~
drivers/infiniband/hw/hfi1/mmu_rb.c: In function 'hfi1_mmu_rb_evict':
drivers/infiniband/hw/hfi1/mmu_rb.c:251:32: error: passing argument 2 of '__mmu_int_rb_remove' from incompatible pointer type [-Werror=incompatible-pointer-types]
__mmu_int_rb_remove(rbnode, &handler->root);
^
In file included from drivers/infiniband/hw/hfi1/mmu_rb.c:50:0:
drivers/infiniband/hw/hfi1/mmu_rb.c:90:47: note: expected 'struct rb_root_cached *' but argument is of type 'struct rb_root *'
mmu_node_start, mmu_node_last, static, __mmu_int_rb);
^
include/linux/interval_tree_generic.h:95:15: note: in definition of macro 'INTERVAL_TREE_DEFINE'
ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, \
^~~~~~~~
drivers/infiniband/hw/hfi1/mmu_rb.c: In function 'hfi1_mmu_rb_remove':
drivers/infiniband/hw/hfi1/mmu_rb.c:281:28: error: passing argument 2 of '__mmu_int_rb_remove' from incompatible pointer type [-Werror=incompatible-pointer-types]
__mmu_int_rb_remove(node, &handler->root);
^
In file included from drivers/infiniband/hw/hfi1/mmu_rb.c:50:0:
drivers/infiniband/hw/hfi1/mmu_rb.c:90:47: note: expected 'struct rb_root_cached *' but argument is of type 'struct rb_root *'
mmu_node_start, mmu_node_last, static, __mmu_int_rb);
^
include/linux/interval_tree_generic.h:95:15: note: in definition of macro 'INTERVAL_TREE_DEFINE'
ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, \
^~~~~~~~
drivers/infiniband/hw/hfi1/mmu_rb.c: In function 'mmu_notifier_mem_invalidate':
drivers/infiniband/hw/hfi1/mmu_rb.c:314:38: error: passing argument 1 of '__mmu_int_rb_iter_first' from incompatible pointer type [-Werror=incompatible-pointer-types]
for (node = __mmu_int_rb_iter_first(root, start, end - 1);
^~~~
In file included from drivers/infiniband/hw/hfi1/mmu_rb.c:50:0:
drivers/infiniband/hw/hfi1/mmu_rb.c:90:47: note: expected 'struct rb_root_cached *' but argument is of type 'struct rb_root *'
mmu_node_start, mmu_node_last, static, __mmu_int_rb);
^
include/linux/interval_tree_generic.h:149:1: note: in definition of macro 'INTERVAL_TREE_DEFINE'
ITPREFIX ## _iter_first(struct rb_root_cached *root, \
^~~~~~~~
drivers/infiniband/hw/hfi1/mmu_rb.c:321:30: error: passing argument 2 of '__mmu_int_rb_remove' from incompatible pointer type [-Werror=incompatible-pointer-types]
__mmu_int_rb_remove(node, root);
^~~~
In file included from drivers/infiniband/hw/hfi1/mmu_rb.c:50:0:
drivers/infiniband/hw/hfi1/mmu_rb.c:90:47: note: expected 'struct rb_root_cached *' but argument is of type 'struct rb_root *'
mmu_node_start, mmu_node_last, static, __mmu_int_rb);
^
include/linux/interval_tree_generic.h:95:15: note: in definition of macro 'INTERVAL_TREE_DEFINE'
ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, \
^~~~~~~~
cc1: some warnings being treated as errors
vim +/__mmu_int_rb_insert +183 drivers/infiniband/hw/hfi1/mmu_rb.c
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 44 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 45 *
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 46 */
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 47 #include <linux/list.h>
67caea1fe drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-05-12 48 #include <linux/rculist.h>
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 49 #include <linux/mmu_notifier.h>
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 @50 #include <linux/interval_tree_generic.h>
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 51
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 52 #include "mmu_rb.h"
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 53 #include "trace.h"
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 54
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 55 struct mmu_rb_handler {
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 56 struct mmu_notifier mn;
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 57 struct rb_root root;
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 58 void *ops_arg;
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 59 spinlock_t lock; /* protect the RB tree */
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 60 struct mmu_rb_ops *ops;
3faa3d9a3 drivers/infiniband/hw/hfi1/mmu_rb.c Ira Weiny 2016-07-28 61 struct mm_struct *mm;
0636e9ab8 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 62 struct list_head lru_list;
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 63 struct work_struct del_work;
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 64 struct list_head del_list;
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 65 struct workqueue_struct *wq;
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 66 };
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 67
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 68 static unsigned long mmu_node_start(struct mmu_rb_node *);
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 69 static unsigned long mmu_node_last(struct mmu_rb_node *);
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 70 static inline void mmu_notifier_page(struct mmu_notifier *, struct mm_struct *,
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 71 unsigned long);
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 72 static inline void mmu_notifier_range_start(struct mmu_notifier *,
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 73 struct mm_struct *,
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 74 unsigned long, unsigned long);
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 75 static void mmu_notifier_mem_invalidate(struct mmu_notifier *,
f19bd643d drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-04-12 76 struct mm_struct *,
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 77 unsigned long, unsigned long);
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 78 static struct mmu_rb_node *__mmu_rb_search(struct mmu_rb_handler *,
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 79 unsigned long, unsigned long);
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 80 static void do_remove(struct mmu_rb_handler *handler,
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 81 struct list_head *del_list);
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 82 static void handle_remove(struct work_struct *work);
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 83
0fc859a65 drivers/infiniband/hw/hfi1/mmu_rb.c Bhumika Goyal 2016-11-19 84 static const struct mmu_notifier_ops mn_opts = {
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 85 .invalidate_page = mmu_notifier_page,
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 86 .invalidate_range_start = mmu_notifier_range_start,
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 87 };
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 88
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 89 INTERVAL_TREE_DEFINE(struct mmu_rb_node, node, unsigned long, __last,
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 90 mmu_node_start, mmu_node_last, static, __mmu_int_rb);
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 91
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 92 static unsigned long mmu_node_start(struct mmu_rb_node *node)
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 93 {
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 94 return node->addr & PAGE_MASK;
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 95 }
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 96
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 97 static unsigned long mmu_node_last(struct mmu_rb_node *node)
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 98 {
de79093b2 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-04-12 99 return PAGE_ALIGN(node->addr + node->len) - 1;
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 100 }
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 101
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 102 int hfi1_mmu_rb_register(void *ops_arg, struct mm_struct *mm,
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 103 struct mmu_rb_ops *ops,
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 104 struct workqueue_struct *wq,
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 105 struct mmu_rb_handler **handler)
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 106 {
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 107 struct mmu_rb_handler *handlr;
3faa3d9a3 drivers/infiniband/hw/hfi1/mmu_rb.c Ira Weiny 2016-07-28 108 int ret;
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 109
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 110 handlr = kmalloc(sizeof(*handlr), GFP_KERNEL);
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 111 if (!handlr)
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 112 return -ENOMEM;
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 113
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 114 handlr->root = RB_ROOT;
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 115 handlr->ops = ops;
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 116 handlr->ops_arg = ops_arg;
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 117 INIT_HLIST_NODE(&handlr->mn.hlist);
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 118 spin_lock_init(&handlr->lock);
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 119 handlr->mn.ops = &mn_opts;
3faa3d9a3 drivers/infiniband/hw/hfi1/mmu_rb.c Ira Weiny 2016-07-28 120 handlr->mm = mm;
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 121 INIT_WORK(&handlr->del_work, handle_remove);
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 122 INIT_LIST_HEAD(&handlr->del_list);
0636e9ab8 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 123 INIT_LIST_HEAD(&handlr->lru_list);
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 124 handlr->wq = wq;
3faa3d9a3 drivers/infiniband/hw/hfi1/mmu_rb.c Ira Weiny 2016-07-28 125
3faa3d9a3 drivers/infiniband/hw/hfi1/mmu_rb.c Ira Weiny 2016-07-28 126 ret = mmu_notifier_register(&handlr->mn, handlr->mm);
3faa3d9a3 drivers/infiniband/hw/hfi1/mmu_rb.c Ira Weiny 2016-07-28 127 if (ret) {
3faa3d9a3 drivers/infiniband/hw/hfi1/mmu_rb.c Ira Weiny 2016-07-28 128 kfree(handlr);
3faa3d9a3 drivers/infiniband/hw/hfi1/mmu_rb.c Ira Weiny 2016-07-28 129 return ret;
3faa3d9a3 drivers/infiniband/hw/hfi1/mmu_rb.c Ira Weiny 2016-07-28 130 }
3faa3d9a3 drivers/infiniband/hw/hfi1/mmu_rb.c Ira Weiny 2016-07-28 131
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 132 *handler = handlr;
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 133 return 0;
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 134 }
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 135
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 136 void hfi1_mmu_rb_unregister(struct mmu_rb_handler *handler)
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 137 {
20a42d083 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 138 struct mmu_rb_node *rbnode;
20a42d083 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 139 struct rb_node *node;
c81e1f645 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 140 unsigned long flags;
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 141 struct list_head del_list;
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 142
782f6697d drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-04-12 143 /* Unregister first so we don't get any more notifications. */
3faa3d9a3 drivers/infiniband/hw/hfi1/mmu_rb.c Ira Weiny 2016-07-28 144 mmu_notifier_unregister(&handler->mn, handler->mm);
782f6697d drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-04-12 145
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 146 /*
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 147 * Make sure the wq delete handler is finished running. It will not
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 148 * be triggered once the mmu notifiers are unregistered above.
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 149 */
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 150 flush_work(&handler->del_work);
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 151
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 152 INIT_LIST_HEAD(&del_list);
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 153
782f6697d drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-04-12 154 spin_lock_irqsave(&handler->lock, flags);
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 155 while ((node = rb_first(&handler->root))) {
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 156 rbnode = rb_entry(node, struct mmu_rb_node, node);
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 157 rb_erase(node, &handler->root);
0636e9ab8 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 158 /* move from LRU list to delete list */
0636e9ab8 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 159 list_move(&rbnode->list, &del_list);
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 160 }
782f6697d drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-04-12 161 spin_unlock_irqrestore(&handler->lock, flags);
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 162
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 163 do_remove(handler, &del_list);
b85ced915 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 164
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 165 kfree(handler);
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 166 }
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 167
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 168 int hfi1_mmu_rb_insert(struct mmu_rb_handler *handler,
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 169 struct mmu_rb_node *mnode)
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 170 {
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 171 struct mmu_rb_node *node;
c81e1f645 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 172 unsigned long flags;
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 173 int ret = 0;
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 174
c81e1f645 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 175 spin_lock_irqsave(&handler->lock, flags);
353b71c7c drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 176 hfi1_cdbg(MMU, "Inserting node addr 0x%llx, len %u", mnode->addr,
353b71c7c drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 177 mnode->len);
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 178 node = __mmu_rb_search(handler, mnode->addr, mnode->len);
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 179 if (node) {
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 180 ret = -EINVAL;
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 181 goto unlock;
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 182 }
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 @183 __mmu_int_rb_insert(mnode, &handler->root);
0636e9ab8 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 184 list_add(&mnode->list, &handler->lru_list);
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 185
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 186 ret = handler->ops->insert(handler->ops_arg, mnode);
0636e9ab8 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 187 if (ret) {
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 @188 __mmu_int_rb_remove(mnode, &handler->root);
0636e9ab8 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 189 list_del(&mnode->list); /* remove from LRU list */
0636e9ab8 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 190 }
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 191 unlock:
c81e1f645 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 192 spin_unlock_irqrestore(&handler->lock, flags);
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 193 return ret;
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 194 }
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 195
de82bdff6 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-04-12 196 /* Caller must hold handler lock */
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 197 static struct mmu_rb_node *__mmu_rb_search(struct mmu_rb_handler *handler,
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 198 unsigned long addr,
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 199 unsigned long len)
06e0ffa69 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 200 {
0f310a00e drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 201 struct mmu_rb_node *node = NULL;
df5a00f81 drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 202
353b71c7c drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 203 hfi1_cdbg(MMU, "Searching for addr 0x%llx, len %u", addr, len);
0f310a00e drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 204 if (!handler->ops->filter) {
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 @205 node = __mmu_int_rb_iter_first(&handler->root, addr,
0f310a00e drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 206 (addr + len) - 1);
0f310a00e drivers/staging/rdma/hfi1/mmu_rb.c Mitko Haralanov 2016-03-08 207 } else {
e0b09ac55 drivers/infiniband/hw/hfi1/mmu_rb.c Dean Luick 2016-07-28 208 for (node = __mmu_int_rb_iter_first(&handler->root, addr,
:::::: The code at line 183 was first introduced by commit
:::::: e0b09ac55d51bb9bf6a4a320bf4029e40bdabd6c IB/hfi1: Make the cache handler own its rb tree root
:::::: TO: Dean Luick <dean.luick@intel.com>
:::::: CC: Doug Ledford <dledford@redhat.com>
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
[-- Attachment #2: .config.gz --]
[-- Type: application/gzip, Size: 60174 bytes --]
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 5/5] lib/interval_tree: Fast overlap detection
2017-05-30 4:54 ` kbuild test robot
@ 2017-05-30 15:44 ` Davidlohr Bueso
0 siblings, 0 replies; 12+ messages in thread
From: Davidlohr Bueso @ 2017-05-30 15:44 UTC (permalink / raw)
To: kbuild test robot
Cc: kbuild-all, mingo, peterz, akpm, jack, kirill.shutemov, ldufour,
mhocko, mgorman, linux-kernel, Davidlohr Bueso
On Tue, 30 May 2017, kbuild test robot wrote:
>Hi Davidlohr,
>
>[auto build test ERROR on next-20170529]
>
>url: https://github.com/0day-ci/linux/commits/Davidlohr-Bueso/rbtree-Cache-leftmost-node-internally/20170530-101713
>config: x86_64-allmodconfig (attached as .config)
>compiler: gcc-6 (Debian 6.2.0-3) 6.2.0 20160901
>reproduce:
> # save the attached .config to linux build tree
> make ARCH=x86_64
>
>All errors (new ones prefixed by >>):
>
> include/linux/compiler.h:260:8: sparse: attribute 'no_sanitize_address': unknown attribute
> drivers/infiniband/hw/hfi1/mmu_rb.c: In function 'hfi1_mmu_rb_insert':
>>> drivers/infiniband/hw/hfi1/mmu_rb.c:183:29: error: passing argument 2 of '__mmu_int_rb_insert' from incompatible pointer type [-Werror=incompatible-pointer-types]
> __mmu_int_rb_insert(mnode, &handler->root);
Ah, I missed that interval tree user. The following fixes it along with
a bogus semicolon for rb_cached_first(). I can add this in v2 if we get
there.
Thanks,
Davidlohr
diff --git a/drivers/infiniband/hw/hfi1/mmu_rb.c b/drivers/infiniband/hw/hfi1/mmu_rb.c
index ccbf52c8ff6f..1835447dcd73 100644
--- a/drivers/infiniband/hw/hfi1/mmu_rb.c
+++ b/drivers/infiniband/hw/hfi1/mmu_rb.c
@@ -54,7 +54,7 @@
struct mmu_rb_handler {
struct mmu_notifier mn;
- struct rb_root root;
+ struct rb_root_cached root;
void *ops_arg;
spinlock_t lock; /* protect the RB tree */
struct mmu_rb_ops *ops;
@@ -111,7 +111,7 @@ int hfi1_mmu_rb_register(void *ops_arg, struct mm_struct *mm,
if (!handlr)
return -ENOMEM;
- handlr->root = RB_ROOT;
+ handlr->root = RB_ROOT_CACHED;
handlr->ops = ops;
handlr->ops_arg = ops_arg;
INIT_HLIST_NODE(&handlr->mn.hlist);
@@ -152,9 +152,9 @@ void hfi1_mmu_rb_unregister(struct mmu_rb_handler *handler)
INIT_LIST_HEAD(&del_list);
spin_lock_irqsave(&handler->lock, flags);
- while ((node = rb_first(&handler->root))) {
+ while ((node = rb_first_cached(&handler->root))) {
rbnode = rb_entry(node, struct mmu_rb_node, node);
- rb_erase(node, &handler->root);
+ rb_erase_cached(node, &handler->root);
/* move from LRU list to delete list */
list_move(&rbnode->list, &del_list);
}
@@ -305,7 +305,7 @@ static void mmu_notifier_mem_invalidate(struct mmu_notifier *mn,
{
struct mmu_rb_handler *handler =
container_of(mn, struct mmu_rb_handler, mn);
- struct rb_root *root = &handler->root;
+ struct rb_root_cached *root = &handler->root;
struct mmu_rb_node *node, *ptr = NULL;
unsigned long flags;
bool added = false;
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index eb4544811cfd..71c9ee585454 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -78,7 +78,7 @@ extern void rb_insert_color_cached(struct rb_node *,
struct rb_root_cached *, bool);
extern void rb_erase_cached(struct rb_node *node, struct rb_root_cached *);
/* Same as rb_first(), but O(1) */
-#define rb_first_cached(root) (root)->rb_leftmost;
+#define rb_first_cached(root) (root)->rb_leftmost
/* Postorder iteration - always visit the parent after its children */
extern struct rb_node *rb_first_postorder(const struct rb_root *);
^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [rfc PATCH -next 0/5] rbtree: Cache leftmost node internally
2017-05-30 2:09 [rfc PATCH -next 0/5] rbtree: Cache leftmost node internally Davidlohr Bueso
` (4 preceding siblings ...)
2017-05-30 2:09 ` [PATCH 5/5] lib/interval_tree: Fast overlap detection Davidlohr Bueso
@ 2017-06-07 15:05 ` Davidlohr Bueso
2017-06-08 13:42 ` Peter Zijlstra
6 siblings, 0 replies; 12+ messages in thread
From: Davidlohr Bueso @ 2017-06-07 15:05 UTC (permalink / raw)
To: mingo, peterz, akpm
Cc: jack, kirill.shutemov, ldufour, mhocko, mgorman, linux-kernel
ping?
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 1/5] rbtree: Cache leftmost node internally
2017-05-30 2:09 ` [PATCH 1/5] " Davidlohr Bueso
@ 2017-06-08 13:03 ` Peter Zijlstra
2017-06-08 15:36 ` Davidlohr Bueso
0 siblings, 1 reply; 12+ messages in thread
From: Peter Zijlstra @ 2017-06-08 13:03 UTC (permalink / raw)
To: Davidlohr Bueso
Cc: mingo, akpm, jack, kirill.shutemov, ldufour, mhocko, mgorman,
linux-kernel, Davidlohr Bueso
On Mon, May 29, 2017 at 07:09:36PM -0700, Davidlohr Bueso wrote:
> diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
> index 9702b6e183bc..b84ee26c19d9 100644
> --- a/include/linux/rbtree_augmented.h
> +++ b/include/linux/rbtree_augmented.h
> @@ -41,7 +41,9 @@ struct rb_augment_callbacks {
> void (*rotate)(struct rb_node *old, struct rb_node *new);
> };
>
> -extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
> +extern void __rb_insert_augmented(struct rb_node *node,
> + struct rb_root *root,
> + bool newleft, struct rb_node **leftmost,
> void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
> /*
> * Fixup the rbtree and update the augmented information when rebalancing.
> @@ -150,6 +161,7 @@ extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
>
> static __always_inline struct rb_node *
> __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
> + bool cached, struct rb_node **leftmost,
> const struct rb_augment_callbacks *augment)
> {
> struct rb_node *child = node->rb_right;
> @@ -157,6 +169,9 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
> struct rb_node *parent, *rebalance;
> unsigned long pc;
>
> + if (cached && node == *leftmost)
> + *leftmost = rb_next(node);
> +
> if (!tmp) {
> /*
> * Case 1: node to erase has no more than 1 child (easy!)
Why do we have @cached ? Wouldn't simply testing @leftmost for NULL not
do the same?
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [rfc PATCH -next 0/5] rbtree: Cache leftmost node internally
2017-05-30 2:09 [rfc PATCH -next 0/5] rbtree: Cache leftmost node internally Davidlohr Bueso
` (5 preceding siblings ...)
2017-06-07 15:05 ` [rfc PATCH -next 0/5] rbtree: Cache leftmost node internally Davidlohr Bueso
@ 2017-06-08 13:42 ` Peter Zijlstra
6 siblings, 0 replies; 12+ messages in thread
From: Peter Zijlstra @ 2017-06-08 13:42 UTC (permalink / raw)
To: Davidlohr Bueso
Cc: mingo, akpm, jack, kirill.shutemov, ldufour, mhocko, mgorman,
linux-kernel
On Mon, May 29, 2017 at 07:09:35PM -0700, Davidlohr Bueso wrote:
> Davidlohr Bueso (5):
> rbtree: Cache leftmost node internally
> sched/fair: Replace cfs_rq->rb_leftmost
> locking/rtmutex: Replace top-waiter and pi_waiters leftmost caching
> sched/deadline: Replace earliest deadline and runqueue leftmost caching
> lib/interval_tree: Fast overlap detection
Seems mostly OK. Except that last patch is unfortunately large, but I
must admit to not seeing a sensible way to shrink that either :/
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 1/5] rbtree: Cache leftmost node internally
2017-06-08 13:03 ` Peter Zijlstra
@ 2017-06-08 15:36 ` Davidlohr Bueso
0 siblings, 0 replies; 12+ messages in thread
From: Davidlohr Bueso @ 2017-06-08 15:36 UTC (permalink / raw)
To: Peter Zijlstra
Cc: mingo, akpm, jack, kirill.shutemov, ldufour, mhocko, mgorman,
linux-kernel, Davidlohr Bueso
On Thu, 08 Jun 2017, Peter Zijlstra wrote:
>On Mon, May 29, 2017 at 07:09:36PM -0700, Davidlohr Bueso wrote:
>>
>> static __always_inline struct rb_node *
>> __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
>> + bool cached, struct rb_node **leftmost,
>> const struct rb_augment_callbacks *augment)
>> {
>> struct rb_node *child = node->rb_right;
>> @@ -157,6 +169,9 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
>> struct rb_node *parent, *rebalance;
>> unsigned long pc;
>>
>> + if (cached && node == *leftmost)
>> + *leftmost = rb_next(node);
>> +
>> if (!tmp) {
>> /*
>> * Case 1: node to erase has no more than 1 child (easy!)
>
>Why do we have @cached ? Wouldn't simply testing @leftmost for NULL not
>do the same?
I added that so that we can differentiate between regular rbtrees and the
cached flavor. However, you are right, we can avoid that arg considering
that the tree is never empty (this is an erase call), thus if leftmost
is nil, it was never cached in the first place.
Thanks,
Davidlohr
^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2017-06-08 15:36 UTC | newest]
Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-05-30 2:09 [rfc PATCH -next 0/5] rbtree: Cache leftmost node internally Davidlohr Bueso
2017-05-30 2:09 ` [PATCH 1/5] " Davidlohr Bueso
2017-06-08 13:03 ` Peter Zijlstra
2017-06-08 15:36 ` Davidlohr Bueso
2017-05-30 2:09 ` [PATCH 2/5] sched/fair: Replace cfs_rq->rb_leftmost Davidlohr Bueso
2017-05-30 2:09 ` [PATCH 3/5] locking/rtmutex: Replace top-waiter and pi_waiters leftmost caching Davidlohr Bueso
2017-05-30 2:09 ` [PATCH 4/5] sched/deadline: Replace earliest deadline and runqueue " Davidlohr Bueso
2017-05-30 2:09 ` [PATCH 5/5] lib/interval_tree: Fast overlap detection Davidlohr Bueso
2017-05-30 4:54 ` kbuild test robot
2017-05-30 15:44 ` Davidlohr Bueso
2017-06-07 15:05 ` [rfc PATCH -next 0/5] rbtree: Cache leftmost node internally Davidlohr Bueso
2017-06-08 13:42 ` Peter Zijlstra
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).