Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1690890 > unrolled thread

[PATCH -next v4 00/17] rbtree: cache leftmost node internally

Back to article view | Back to linux.kernel

Contents

  [PATCH -next v4 00/17] rbtree: cache leftmost node internally Davidlohr Bueso <dave@stgolabs.net> - 2017-07-19 03:50 +0200
    [PATCH 09/17] locking/rtmutex: replace top-waiter and pi_waiters leftmost caching Davidlohr Bueso <dave@stgolabs.net> - 2017-07-19 03:50 +0200
    [PATCH 03/17] rbtree: add some additional comments for rebalancing cases Davidlohr Bueso <dave@stgolabs.net> - 2017-07-19 03:50 +0200
    [PATCH 13/17] procfs: use faster rb_first_cached() Davidlohr Bueso <dave@stgolabs.net> - 2017-07-19 03:50 +0200
    [PATCH 16/17] mem/memcg: cache rightmost node Davidlohr Bueso <dave@stgolabs.net> - 2017-07-19 03:50 +0200
      Re: [PATCH 16/17] mem/memcg: cache rightmost node Michal Hocko <mhocko@kernel.org> - 2017-07-19 10:00 +0200
        Re: [PATCH 16/17] mem/memcg: cache rightmost node Andrew Morton <akpm@linux-foundation.org> - 2017-07-26 23:10 +0200
          Re: [PATCH 16/17] mem/memcg: cache rightmost node Michal Hocko <mhocko@kernel.org> - 2017-07-27 09:10 +0200
    [PATCH 01/17] rbtree: cache leftmost node internally Davidlohr Bueso <dave@stgolabs.net> - 2017-07-19 03:50 +0200
    [PATCH 17/17] block/cfq: cache rightmost rb_node Davidlohr Bueso <dave@stgolabs.net> - 2017-07-19 03:50 +0200
      Re: [PATCH 17/17] block/cfq: cache rightmost rb_node Jan Kara <jack@suse.cz> - 2017-07-19 10:00 +0200
    [PATCH 12/17] lib/interval-tree: correct comment wrt generic flavor Davidlohr Bueso <dave@stgolabs.net> - 2017-07-19 03:50 +0200
    [PATCH 10/17] block/cfq: replace cfq_rb_root leftmost caching Davidlohr Bueso <dave@stgolabs.net> - 2017-07-19 03:50 +0200
      Re: [PATCH 10/17] block/cfq: replace cfq_rb_root leftmost caching Jan Kara <jack@suse.cz> - 2017-07-19 09:50 +0200
    [PATCH 05/17] lib/rbtree_test.c: add (inorder) traversal test Davidlohr Bueso <dave@stgolabs.net> - 2017-07-19 04:00 +0200
    [PATCH 04/17] lib/rbtree_test.c: make input module parameters Davidlohr Bueso <dave@stgolabs.net> - 2017-07-19 04:00 +0200
    Re: [PATCH 11/17] lib/interval_tree: fast overlap detection Doug Ledford <dledford@redhat.com> - 2017-07-22 20:00 +0200

#1690890 — [PATCH -next v4 00/17] rbtree: cache leftmost node internally

Changes from v3 (https://lwn.net/Articles/726809/):
- Updated Documentation/rbtree.txt in patch 1.
- Explicitly mentioned the asymmetry wrt rightmost node in patch 1 (hch).
- Most changes in the set is adding more patches: patch 2,3,4,5,6,15,16,17.
- Added Peter's ack.

Changes from v2 (https://lkml.org/lkml/2017/6/8/857):
- Fixed 0day reported crash for drm_mm selftest program. We were
not correctly using the cached version of rbtree with the allocated
nodes.
- Added cfq patch to use internal rbtree caching.
- Added Christian's and Jan's reviews.

Changes from v1 (https://marc.info/?l=linux-kernel&m=149611025616685):
- No longer rfc.
- Removed bogus semimcolon in rb_first_cached()
- Updated missing interval tree user drivers/infiniband/hw/hfi1/
- Removed redundant @cached arg in when erasing a node.
- Added more patches that make use of rb_first_cached(), which I
  thought might be worth it: procfs and epoll.
- Cc more people for patch 5, which touches drivers such as infiniband
and gpu. The rest of the changes are pretty covered with the current
Cc'ed maintainers and mm folks.

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]. The benefits of this series are that:

(i)   Unify users that do internal leftmost node caching.
(ii)  Optimize all interval tree users.
(iii) Convert at least two new users (epoll and procfs) to the new interface.
(iv)  Enable user rightmost node caching, similar to how we deal with the
      leftmost case before this patchset.

Patch 1: Layout the rb machinery.

Patch 2,3: Adds an unlikely() prediction to root-most node for insertions
as well as some minor comment enhancements.

Patches 4-6: Improve and extend rbrtee_test.c program.

Patches 7-10:  Make use of the internal leftmost node in scheduler, realtime
mutexes and cfq.

Patch 11: Implements fast overlap checks for interval trees.

Patch 12: rocket science.

Patches 13-15: Patches that convert to O(1) rb_first_cached().

Patches 16,17: Apply rightmost node optimization explicitly by two users.

The series has survived booting, kernel builds and pistress workloads.

Applies on top of today's -next.

Thanks!

Davidlohr Bueso (17):
  rbtree: cache leftmost node internally
  rbtree: optimize root-check during rebalancing loop
  rbtree: add some additional comments for rebalancing cases
  lib/rbtree_test.c: make input module parameters
  lib/rbtree_test.c: add (inorder) traversal test
  lib/rbtree_test.c: support rb_root_cached
  sched/fair: replace cfs_rq->rb_leftmost
  sched/deadline: replace earliest dl and rq leftmost caching
  locking/rtmutex: replace top-waiter and pi_waiters leftmost caching
  block/cfq: replace cfq_rb_root leftmost caching
  lib/interval_tree: fast overlap detection
  lib/interval-tree: correct comment wrt generic flavor
  procfs: use faster rb_first_cached()
  fs/epoll: use faster rb_first_cached()
  fs/ext4: use cached rbtrees
  mem/memcg: cache rightmost node
  block/cfq: cache rightmost rb_node

 Documentation/rbtree.txt                           |  33 +++
 block/cfq-iosched.c                                |  81 +++-----
 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                           |  19 +-
 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/hfi1/mmu_rb.c                |  10 +-
 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/eventpoll.c                                     |  30 +--
 fs/ext4/dir.c                                      |  24 ++-
 fs/ext4/ext4.h                                     |   4 +-
 fs/ext4/mballoc.c                                  |  22 +-
 fs/hugetlbfs/inode.c                               |   6 +-
 fs/inode.c                                         |   2 +-
 fs/proc/generic.c                                  |  26 +--
 fs/proc/internal.h                                 |   2 +-
 fs/proc/proc_net.c                                 |   2 +-
 fs/proc/root.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              |  48 ++++-
 include/linux/mm.h                                 |  17 +-
 include/linux/rbtree.h                             |  21 ++
 include/linux/rbtree_augmented.h                   |  33 ++-
 include/linux/rmap.h                               |   4 +-
 include/linux/rtmutex.h                            |  11 +-
 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                           |  35 +---
 kernel/locking/rtmutex_common.h                    |  12 +-
 kernel/sched/deadline.c                            |  50 ++---
 kernel/sched/debug.c                               |   2 +-
 kernel/sched/fair.c                                |  39 ++--
 kernel/sched/sched.h                               |   9 +-
 lib/interval_tree_test.c                           |   4 +-
 lib/rbtree.c                                       |  65 ++++--
 lib/rbtree_test.c                                  | 230 +++++++++++++++++----
 mm/interval_tree.c                                 |  10 +-
 mm/memcontrol.c                                    |  23 ++-
 mm/memory.c                                        |   4 +-
 mm/mmap.c                                          |  10 +-
 mm/rmap.c                                          |   4 +-
 59 files changed, 643 insertions(+), 378 deletions(-)

-- 
2.12.0

[toc] | [next] | [standalone]

#1690891 — [PATCH 09/17] locking/rtmutex: replace top-waiter and pi_waiters leftmost caching

... with the generic rbtree flavor instead. No changes
in semantics whatsoever.

Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
 include/linux/init_task.h       |  5 ++---
 include/linux/rtmutex.h         | 11 +++++------
 include/linux/sched.h           |  3 +--
 kernel/fork.c                   |  3 +--
 kernel/locking/rtmutex-debug.c  |  2 +-
 kernel/locking/rtmutex.c        | 35 +++++++++++------------------------
 kernel/locking/rtmutex_common.h | 12 ++++++------
 7 files changed, 27 insertions(+), 44 deletions(-)

diff --git a/include/linux/init_task.h b/include/linux/init_task.h
index a2f6707e9fc0..2008de121705 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 44fd002f7cd5..53fcbe9de7fd 100644
--- a/include/linux/rtmutex.h
+++ b/include/linux/rtmutex.h
@@ -22,18 +22,17 @@ 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;
-	const char 		*name, *file;
+	const char		*name, *file;
 	int			line;
 	void			*magic;
 #endif
@@ -84,7 +83,7 @@ do { \
 
 #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) \
 	__DEP_MAP_RT_MUTEX_INITIALIZER(mutexname)}
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 8337e2db0bb2..99753c3e470d 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -811,8 +811,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 17921b0390b4..4235905fe9d1 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 ac35e648b0e5..f4a74e78d467 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 649dc9d3951a..6f3dba6e4e9e 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,12 @@ 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 +330,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);
 }
 
@@ -1657,8 +1645,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;
 
 	if (name && key)
 		debug_rt_mutex_init(lock, name, key);
diff --git a/kernel/locking/rtmutex_common.h b/kernel/locking/rtmutex_common.h
index 72ad45a9a794..524beeee24b0 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,14 +59,14 @@ 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,
-			pi_tree_entry);
+	return rb_entry(p->pi_waiters.rb_leftmost,
+			struct rt_mutex_waiter, pi_tree_entry);
 }
 
 /*
-- 
2.12.0

[toc] | [prev] | [next] | [standalone]

#1690894 — [PATCH 03/17] rbtree: add some additional comments for rebalancing cases

While overall the code is very nicely commented, it might not be
immediately obvious from the diagrams what is going on. Add a
very brief summary of each case. Opposite cases where the node
is the left child are left untouched.

Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
 lib/rbtree.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index e7cce12f404f..ba4a9d165f1b 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -132,7 +132,7 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
 		if (parent != tmp) {	/* parent == gparent->rb_left */
 			if (tmp && rb_is_red(tmp)) {
 				/*
-				 * Case 1 - color flips
+				 * Case 1 - node's uncle is red (color flips).
 				 *
 				 *       G            g
 				 *      / \          / \
@@ -155,7 +155,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
 			tmp = parent->rb_right;
 			if (node == tmp) {
 				/*
-				 * Case 2 - left rotate at parent
+				 * Case 2 - node's uncle is black and node is
+				 * the parent's right child (left rotate at parent).
 				 *
 				 *      G             G
 				 *     / \           / \
@@ -179,7 +180,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
 			}
 
 			/*
-			 * Case 3 - right rotate at gparent
+			 * Case 3 - node's uncle is black and node is
+			 * the parent's left child (right rotate at gparent).
 			 *
 			 *        G           P
 			 *       / \         / \
-- 
2.12.0

[toc] | [prev] | [next] | [standalone]

#1690895 — [PATCH 13/17] procfs: use faster rb_first_cached()

... such that we can avoid the tree walks to get the
node with the smallest key. Semantically the same,
as the previously used rb_first(), but O(1). The
main overhead is the extra footprint for the cached
rb_node pointer, which should not matter for procfs.

Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
 fs/proc/generic.c  | 26 ++++++++++++++------------
 fs/proc/internal.h |  2 +-
 fs/proc/proc_net.c |  2 +-
 fs/proc/root.c     |  2 +-
 4 files changed, 17 insertions(+), 15 deletions(-)

diff --git a/fs/proc/generic.c b/fs/proc/generic.c
index e3cda0b5968f..ab6496356dc2 100644
--- a/fs/proc/generic.c
+++ b/fs/proc/generic.c
@@ -40,8 +40,8 @@ static int proc_match(unsigned int len, const char *name, struct proc_dir_entry
 
 static struct proc_dir_entry *pde_subdir_first(struct proc_dir_entry *dir)
 {
-	return rb_entry_safe(rb_first(&dir->subdir), struct proc_dir_entry,
-			     subdir_node);
+	return rb_entry_safe(rb_first_cached(&dir->subdir),
+			     struct proc_dir_entry, subdir_node);
 }
 
 static struct proc_dir_entry *pde_subdir_next(struct proc_dir_entry *dir)
@@ -54,7 +54,7 @@ static struct proc_dir_entry *pde_subdir_find(struct proc_dir_entry *dir,
 					      const char *name,
 					      unsigned int len)
 {
-	struct rb_node *node = dir->subdir.rb_node;
+	struct rb_node *node = dir->subdir.rb_root.rb_node;
 
 	while (node) {
 		struct proc_dir_entry *de = rb_entry(node,
@@ -75,8 +75,9 @@ static struct proc_dir_entry *pde_subdir_find(struct proc_dir_entry *dir,
 static bool pde_subdir_insert(struct proc_dir_entry *dir,
 			      struct proc_dir_entry *de)
 {
-	struct rb_root *root = &dir->subdir;
-	struct rb_node **new = &root->rb_node, *parent = NULL;
+	struct rb_root_cached *root = &dir->subdir;
+	struct rb_node **new = &root->rb_root.rb_node, *parent = NULL;
+	bool leftmost = true;
 
 	/* Figure out where to put new node */
 	while (*new) {
@@ -88,15 +89,16 @@ static bool pde_subdir_insert(struct proc_dir_entry *dir,
 		parent = *new;
 		if (result < 0)
 			new = &(*new)->rb_left;
-		else if (result > 0)
+		else if (result > 0) {
 			new = &(*new)->rb_right;
-		else
+			leftmost = false;
+		} else
 			return false;
 	}
 
 	/* Add new node and rebalance tree. */
 	rb_link_node(&de->subdir_node, parent, new);
-	rb_insert_color(&de->subdir_node, root);
+	rb_insert_color_cached(&de->subdir_node, root, leftmost);
 	return true;
 }
 
@@ -369,7 +371,7 @@ static struct proc_dir_entry *__proc_create(struct proc_dir_entry **parent,
 	ent->namelen = qstr.len;
 	ent->mode = mode;
 	ent->nlink = nlink;
-	ent->subdir = RB_ROOT;
+	ent->subdir = RB_ROOT_CACHED;
 	atomic_set(&ent->count, 1);
 	spin_lock_init(&ent->pde_unload_lock);
 	INIT_LIST_HEAD(&ent->pde_openers);
@@ -545,7 +547,7 @@ void remove_proc_entry(const char *name, struct proc_dir_entry *parent)
 
 	de = pde_subdir_find(parent, fn, len);
 	if (de)
-		rb_erase(&de->subdir_node, &parent->subdir);
+		rb_erase_cached(&de->subdir_node, &parent->subdir);
 	write_unlock(&proc_subdir_lock);
 	if (!de) {
 		WARN(1, "name '%s'\n", name);
@@ -582,13 +584,13 @@ int remove_proc_subtree(const char *name, struct proc_dir_entry *parent)
 		write_unlock(&proc_subdir_lock);
 		return -ENOENT;
 	}
-	rb_erase(&root->subdir_node, &parent->subdir);
+	rb_erase_cached(&root->subdir_node, &parent->subdir);
 
 	de = root;
 	while (1) {
 		next = pde_subdir_first(de);
 		if (next) {
-			rb_erase(&next->subdir_node, &de->subdir);
+			rb_erase_cached(&next->subdir_node, &de->subdir);
 			de = next;
 			continue;
 		}
diff --git a/fs/proc/internal.h b/fs/proc/internal.h
index aa2b89071630..8382d08385a9 100644
--- a/fs/proc/internal.h
+++ b/fs/proc/internal.h
@@ -40,7 +40,7 @@ struct proc_dir_entry {
 	const struct inode_operations *proc_iops;
 	const struct file_operations *proc_fops;
 	struct proc_dir_entry *parent;
-	struct rb_root subdir;
+	struct rb_root_cached subdir;
 	struct rb_node subdir_node;
 	void *data;
 	atomic_t count;		/* use count */
diff --git a/fs/proc/proc_net.c b/fs/proc/proc_net.c
index d72fc40241d9..a2bf369c923d 100644
--- a/fs/proc/proc_net.c
+++ b/fs/proc/proc_net.c
@@ -196,7 +196,7 @@ static __net_init int proc_net_ns_init(struct net *net)
 	if (!netd)
 		goto out;
 
-	netd->subdir = RB_ROOT;
+	netd->subdir = RB_ROOT_CACHED;
 	netd->data = net;
 	netd->nlink = 2;
 	netd->namelen = 3;
diff --git a/fs/proc/root.c b/fs/proc/root.c
index deecb397daa3..926fb27f4ca2 100644
--- a/fs/proc/root.c
+++ b/fs/proc/root.c
@@ -210,7 +210,7 @@ struct proc_dir_entry proc_root = {
 	.proc_iops	= &proc_root_inode_operations, 
 	.proc_fops	= &proc_root_operations,
 	.parent		= &proc_root,
-	.subdir		= RB_ROOT,
+	.subdir		= RB_ROOT_CACHED,
 	.name		= "/proc",
 };
 
-- 
2.12.0

[toc] | [prev] | [next] | [standalone]

#1690896 — [PATCH 16/17] mem/memcg: cache rightmost node

Such that we can optimize __mem_cgroup_largest_soft_limit_node().
The only overhead is the extra footprint for the cached pointer,
but this should not be an issue for mem_cgroup_tree_per_node.

Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
 mm/memcontrol.c | 23 ++++++++++++++++++-----
 1 file changed, 18 insertions(+), 5 deletions(-)

diff --git a/mm/memcontrol.c b/mm/memcontrol.c
index 3df3c04d73ab..2ef9328ace2e 100644
--- a/mm/memcontrol.c
+++ b/mm/memcontrol.c
@@ -119,6 +119,7 @@ static const char *const mem_cgroup_lru_names[] = {
 
 struct mem_cgroup_tree_per_node {
 	struct rb_root rb_root;
+	struct rb_node *rb_rightmost;
 	spinlock_t lock;
 };
 
@@ -386,6 +387,7 @@ static void __mem_cgroup_insert_exceeded(struct mem_cgroup_per_node *mz,
 	struct rb_node **p = &mctz->rb_root.rb_node;
 	struct rb_node *parent = NULL;
 	struct mem_cgroup_per_node *mz_node;
+	bool rightmost = true;
 
 	if (mz->on_tree)
 		return;
@@ -397,8 +399,11 @@ static void __mem_cgroup_insert_exceeded(struct mem_cgroup_per_node *mz,
 		parent = *p;
 		mz_node = rb_entry(parent, struct mem_cgroup_per_node,
 					tree_node);
-		if (mz->usage_in_excess < mz_node->usage_in_excess)
+		if (mz->usage_in_excess < mz_node->usage_in_excess) {
 			p = &(*p)->rb_left;
+			rightmost = false;
+		}
+
 		/*
 		 * We can't avoid mem cgroups that are over their soft
 		 * limit by the same amount
@@ -406,6 +411,10 @@ static void __mem_cgroup_insert_exceeded(struct mem_cgroup_per_node *mz,
 		else if (mz->usage_in_excess >= mz_node->usage_in_excess)
 			p = &(*p)->rb_right;
 	}
+
+	if (rightmost)
+		mctz->rb_rightmost = &mz->tree_node;
+
 	rb_link_node(&mz->tree_node, parent, p);
 	rb_insert_color(&mz->tree_node, &mctz->rb_root);
 	mz->on_tree = true;
@@ -416,6 +425,10 @@ static void __mem_cgroup_remove_exceeded(struct mem_cgroup_per_node *mz,
 {
 	if (!mz->on_tree)
 		return;
+
+	if (&mz->tree_node == mctz->rb_rightmost)
+		mctz->rb_rightmost = rb_next(&mz->tree_node);
+
 	rb_erase(&mz->tree_node, &mctz->rb_root);
 	mz->on_tree = false;
 }
@@ -496,16 +509,15 @@ static void mem_cgroup_remove_from_trees(struct mem_cgroup *memcg)
 static struct mem_cgroup_per_node *
 __mem_cgroup_largest_soft_limit_node(struct mem_cgroup_tree_per_node *mctz)
 {
-	struct rb_node *rightmost = NULL;
 	struct mem_cgroup_per_node *mz;
 
 retry:
 	mz = NULL;
-	rightmost = rb_last(&mctz->rb_root);
-	if (!rightmost)
+	if (!mctz->rb_rightmost)
 		goto done;		/* Nothing to reclaim from */
 
-	mz = rb_entry(rightmost, struct mem_cgroup_per_node, tree_node);
+	mz = rb_entry(mctz->rb_rightmost,
+		      struct mem_cgroup_per_node, tree_node);
 	/*
 	 * Remove the node now but someone else can add it back,
 	 * we will to add it back at the end of reclaim to its correct
@@ -5850,6 +5862,7 @@ static int __init mem_cgroup_init(void)
 				    node_online(node) ? node : NUMA_NO_NODE);
 
 		rtpn->rb_root = RB_ROOT;
+		rtpn->rb_rightmost = NULL;
 		spin_lock_init(&rtpn->lock);
 		soft_limit_tree.rb_tree_per_node[node] = rtpn;
 	}
-- 
2.12.0

[toc] | [prev] | [next] | [standalone]

#1691085 — Re: [PATCH 16/17] mem/memcg: cache rightmost node

[CC Johannes and Vladimir - the whole series is
http://lkml.kernel.org/r/20170719014603.19029-1-dave@stgolabs.net]

On Tue 18-07-17 18:46:02, Davidlohr Bueso wrote:
> Such that we can optimize __mem_cgroup_largest_soft_limit_node().
> The only overhead is the extra footprint for the cached pointer,
> but this should not be an issue for mem_cgroup_tree_per_node.

The soft limit reclaim and the associated tree manipulation is not worth
touching/optimizing IMHO. We strongly discourage anybody configuring
soft limit because of the way how it is implemented and disruptive.

> Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
> ---
>  mm/memcontrol.c | 23 ++++++++++++++++++-----
>  1 file changed, 18 insertions(+), 5 deletions(-)
> 
> diff --git a/mm/memcontrol.c b/mm/memcontrol.c
> index 3df3c04d73ab..2ef9328ace2e 100644
> --- a/mm/memcontrol.c
> +++ b/mm/memcontrol.c
> @@ -119,6 +119,7 @@ static const char *const mem_cgroup_lru_names[] = {
>  
>  struct mem_cgroup_tree_per_node {
>  	struct rb_root rb_root;
> +	struct rb_node *rb_rightmost;
>  	spinlock_t lock;
>  };
>  
> @@ -386,6 +387,7 @@ static void __mem_cgroup_insert_exceeded(struct mem_cgroup_per_node *mz,
>  	struct rb_node **p = &mctz->rb_root.rb_node;
>  	struct rb_node *parent = NULL;
>  	struct mem_cgroup_per_node *mz_node;
> +	bool rightmost = true;
>  
>  	if (mz->on_tree)
>  		return;
> @@ -397,8 +399,11 @@ static void __mem_cgroup_insert_exceeded(struct mem_cgroup_per_node *mz,
>  		parent = *p;
>  		mz_node = rb_entry(parent, struct mem_cgroup_per_node,
>  					tree_node);
> -		if (mz->usage_in_excess < mz_node->usage_in_excess)
> +		if (mz->usage_in_excess < mz_node->usage_in_excess) {
>  			p = &(*p)->rb_left;
> +			rightmost = false;
> +		}
> +
>  		/*
>  		 * We can't avoid mem cgroups that are over their soft
>  		 * limit by the same amount
> @@ -406,6 +411,10 @@ static void __mem_cgroup_insert_exceeded(struct mem_cgroup_per_node *mz,
>  		else if (mz->usage_in_excess >= mz_node->usage_in_excess)
>  			p = &(*p)->rb_right;
>  	}
> +
> +	if (rightmost)
> +		mctz->rb_rightmost = &mz->tree_node;
> +
>  	rb_link_node(&mz->tree_node, parent, p);
>  	rb_insert_color(&mz->tree_node, &mctz->rb_root);
>  	mz->on_tree = true;
> @@ -416,6 +425,10 @@ static void __mem_cgroup_remove_exceeded(struct mem_cgroup_per_node *mz,
>  {
>  	if (!mz->on_tree)
>  		return;
> +
> +	if (&mz->tree_node == mctz->rb_rightmost)
> +		mctz->rb_rightmost = rb_next(&mz->tree_node);
> +
>  	rb_erase(&mz->tree_node, &mctz->rb_root);
>  	mz->on_tree = false;
>  }
> @@ -496,16 +509,15 @@ static void mem_cgroup_remove_from_trees(struct mem_cgroup *memcg)
>  static struct mem_cgroup_per_node *
>  __mem_cgroup_largest_soft_limit_node(struct mem_cgroup_tree_per_node *mctz)
>  {
> -	struct rb_node *rightmost = NULL;
>  	struct mem_cgroup_per_node *mz;
>  
>  retry:
>  	mz = NULL;
> -	rightmost = rb_last(&mctz->rb_root);
> -	if (!rightmost)
> +	if (!mctz->rb_rightmost)
>  		goto done;		/* Nothing to reclaim from */
>  
> -	mz = rb_entry(rightmost, struct mem_cgroup_per_node, tree_node);
> +	mz = rb_entry(mctz->rb_rightmost,
> +		      struct mem_cgroup_per_node, tree_node);
>  	/*
>  	 * Remove the node now but someone else can add it back,
>  	 * we will to add it back at the end of reclaim to its correct
> @@ -5850,6 +5862,7 @@ static int __init mem_cgroup_init(void)
>  				    node_online(node) ? node : NUMA_NO_NODE);
>  
>  		rtpn->rb_root = RB_ROOT;
> +		rtpn->rb_rightmost = NULL;
>  		spin_lock_init(&rtpn->lock);
>  		soft_limit_tree.rb_tree_per_node[node] = rtpn;
>  	}
> -- 
> 2.12.0

-- 
Michal Hocko
SUSE Labs

[toc] | [prev] | [next] | [standalone]

#1697561 — Re: [PATCH 16/17] mem/memcg: cache rightmost node

On Wed, 19 Jul 2017 09:50:36 +0200 Michal Hocko <mhocko@kernel.org> wrote:

> [CC Johannes and Vladimir - the whole series is
> http://lkml.kernel.org/r/20170719014603.19029-1-dave@stgolabs.net]
> 
> On Tue 18-07-17 18:46:02, Davidlohr Bueso wrote:
> > Such that we can optimize __mem_cgroup_largest_soft_limit_node().
> > The only overhead is the extra footprint for the cached pointer,
> > but this should not be an issue for mem_cgroup_tree_per_node.
> 
> The soft limit reclaim and the associated tree manipulation is not worth
> touching/optimizing IMHO. We strongly discourage anybody configuring
> soft limit because of the way how it is implemented and disruptive.

I'm inclined to merge this.  Unless we plan to actually remove the code
"soon", I think it's best to continue to improve it.  Improving
performance may never matter to anyone, but there is benefit in keeping
up to date with the current interfaces and best practices.

[toc] | [prev] | [next] | [standalone]

#1697759 — Re: [PATCH 16/17] mem/memcg: cache rightmost node

On Wed 26-07-17 14:09:27, Andrew Morton wrote:
> On Wed, 19 Jul 2017 09:50:36 +0200 Michal Hocko <mhocko@kernel.org> wrote:
> 
> > [CC Johannes and Vladimir - the whole series is
> > http://lkml.kernel.org/r/20170719014603.19029-1-dave@stgolabs.net]
> > 
> > On Tue 18-07-17 18:46:02, Davidlohr Bueso wrote:
> > > Such that we can optimize __mem_cgroup_largest_soft_limit_node().
> > > The only overhead is the extra footprint for the cached pointer,
> > > but this should not be an issue for mem_cgroup_tree_per_node.
> > 
> > The soft limit reclaim and the associated tree manipulation is not worth
> > touching/optimizing IMHO. We strongly discourage anybody configuring
> > soft limit because of the way how it is implemented and disruptive.
> 
> I'm inclined to merge this.  Unless we plan to actually remove the code
> "soon",

this is not going to happen. It is a user visible interface so we will
have to maintain it as long as cgroup v1 interface is available

> I think it's best to continue to improve it.  Improving
> performance may never matter to anyone, but there is benefit in keeping
> up to date with the current interfaces and best practices.
 
 Well, I am not opposing the change I just think it is not worth
 bothering. Soft limit reclaim tends to be so expensive (direct limit
 down to the soft limit) that a tiny otimization has hard times to help.

-- 
Michal Hocko
SUSE Labs

[toc] | [prev] | [next] | [standalone]

#1690897 — [PATCH 01/17] rbtree: cache leftmost node internally

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.

Reviewed-by: Jan Kara <jack@suse.cz>
Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
 Documentation/rbtree.txt         | 33 +++++++++++++++++++++++++++++++++
 include/linux/rbtree.h           | 21 +++++++++++++++++++++
 include/linux/rbtree_augmented.h | 33 ++++++++++++++++++++++++++++++---
 lib/rbtree.c                     | 34 +++++++++++++++++++++++++++++-----
 4 files changed, 113 insertions(+), 8 deletions(-)

diff --git a/Documentation/rbtree.txt b/Documentation/rbtree.txt
index b8a8c70b0188..c42a21b99046 100644
--- a/Documentation/rbtree.txt
+++ b/Documentation/rbtree.txt
@@ -193,6 +193,39 @@ Example::
   for (node = rb_first(&mytree); node; node = rb_next(node))
 	printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring);
 
+Cached rbtrees
+--------------
+
+Computing the leftmost (smallest) node is quite a common task for binary
+search trees, such as for traversals or users relying on a the particular
+order for their own logic. To this end, users can use 'struct rb_root_cached'
+to optimize O(logN) rb_first() calls to a simple pointer fetch avoiding
+potentially expensive tree iterations. This is done at negligible runtime
+overhead for maintanence; albeit larger memory footprint.
+
+Similar to the rb_root structure, cached rbtrees are initialized to be
+empty via:
+
+  struct rb_root_cached mytree = RB_ROOT_CACHED;
+
+Cached rbtree is simply a regular rb_root with an extra pointer to cache the
+leftmost node. This allows rb_root_cached to exist wherever rb_root does,
+which permits augmented trees to be supported as well as only a few extra
+interfaces:
+
+  struct rb_node *rb_first_cached(struct rb_root_cached *tree);
+  void rb_insert_color_cached(struct rb_node *, struct rb_root_cached *, bool);
+  void rb_erase_cached(struct rb_node *node, struct rb_root_cached *);
+
+Both insert and erase calls have their respective counterpart of augmented
+trees:
+
+  void rb_insert_augmented_cached(struct rb_node *node, struct rb_root_cached *,
+				  bool, struct rb_augment_callbacks *);
+  void rb_erase_augmented_cached(struct rb_node *, struct rb_root_cached *,
+				 struct rb_augment_callbacks *);
+
+
 Support for Augmented rbtrees
 -----------------------------
 
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index e585018498d5..d574361943ea 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -44,10 +44,25 @@ struct rb_root {
 	struct rb_node *rb_node;
 };
 
+/*
+ * Leftmost-cached rbtrees.
+ *
+ * We do not cache the rightmost node based on footprint
+ * size vs number of potential users that could benefit
+ * from O(1) rb_last(). Just not worth it, users that want
+ * this feature can always implement the logic explicitly.
+ * Furthermore, users that want to cache both pointers may
+ * find it a bit asymmetric, but that's ok.
+ */
+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 +84,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..6bfd2b581f75 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,
+		     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 (leftmost && 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,
+							 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,
+							 &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..d102d9d2ffaa 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,
+					 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,
+					 &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

[toc] | [prev] | [next] | [standalone]

#1690898 — [PATCH 17/17] block/cfq: cache rightmost rb_node

For the same reasons we already cache the leftmost pointer,
apply the same optimization for rb_last() calls. Users must
explicitly do this as rb_root_cached only deals with the
smallest node.

Cc: axboe@fb.com
Cc: linux-block@vger.kernel.org
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
This is part of the rbtree internal caching series:
https://lwn.net/Articles/726809/

 block/cfq-iosched.c | 19 ++++++++++++++-----
 1 file changed, 14 insertions(+), 5 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 92c31683a2bb..57ec45fd4590 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -94,11 +94,13 @@ struct cfq_ttime {
  */
 struct cfq_rb_root {
 	struct rb_root_cached rb;
+	struct rb_node *rb_rightmost;
 	unsigned count;
 	u64 min_vdisktime;
 	struct cfq_ttime ttime;
 };
 #define CFQ_RB_ROOT	(struct cfq_rb_root) { .rb = RB_ROOT_CACHED, \
+			.rb_rightmost = NULL,			     \
 			.ttime = {.last_end_request = ktime_get_ns(),},}
 
 /*
@@ -1183,6 +1185,9 @@ static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root)
 
 static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
 {
+	if (root->rb_rightmost == n)
+		root->rb_rightmost = rb_next(n);
+
 	rb_erase_cached(n, &root->rb);
 	RB_CLEAR_NODE(n);
 
@@ -1239,20 +1244,24 @@ __cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
 	struct rb_node *parent = NULL;
 	struct cfq_group *__cfqg;
 	s64 key = cfqg_key(st, cfqg);
-	bool leftmost = true;
+	bool leftmost = true, rightmost = true;
 
 	while (*node != NULL) {
 		parent = *node;
 		__cfqg = rb_entry_cfqg(parent);
 
-		if (key < cfqg_key(st, __cfqg))
+		if (key < cfqg_key(st, __cfqg)) {
 			node = &parent->rb_left;
-		else {
+			rightmost = false;
+		} else {
 			node = &parent->rb_right;
 			leftmost = false;
 		}
 	}
 
+	if (rightmost)
+		st->rb_rightmost = &cfqg->rb_node;
+
 	rb_link_node(&cfqg->rb_node, parent, node);
 	rb_insert_color_cached(&cfqg->rb_node, &st->rb, leftmost);
 }
@@ -1355,7 +1364,7 @@ cfq_group_notify_queue_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
 	 * so that groups get lesser vtime based on their weights, so that
 	 * if group does not loose all if it was not continuously backlogged.
 	 */
-	n = rb_last(&st->rb.rb_root);
+	n = st->rb_rightmost;
 	if (n) {
 		__cfqg = rb_entry_cfqg(n);
 		cfqg->vdisktime = __cfqg->vdisktime +
@@ -2204,7 +2213,7 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 	st = st_for(cfqq->cfqg, cfqq_class(cfqq), cfqq_type(cfqq));
 	if (cfq_class_idle(cfqq)) {
 		rb_key = CFQ_IDLE_DELAY;
-		parent = rb_last(&st->rb.rb_root);
+		parent = st->rb_rightmost;
 		if (parent && parent != &cfqq->rb_node) {
 			__cfqq = rb_entry(parent, struct cfq_queue, rb_node);
 			rb_key += __cfqq->rb_key;
-- 
2.12.0

[toc] | [prev] | [next] | [standalone]

#1691087 — Re: [PATCH 17/17] block/cfq: cache rightmost rb_node

On Tue 18-07-17 18:46:03, Davidlohr Bueso wrote:
> For the same reasons we already cache the leftmost pointer,
> apply the same optimization for rb_last() calls. Users must
> explicitly do this as rb_root_cached only deals with the
> smallest node.
> 
> Cc: axboe@fb.com
> Cc: linux-block@vger.kernel.org
> Signed-off-by: Davidlohr Bueso <dbueso@suse.de>

Hum, as I'm reading the code, here we have about 1:1 ratio of cached
lookups and tree insert / delete where we have to maintain the cached
value. Is the optimization worth it in such case?

								Honza

> ---
> This is part of the rbtree internal caching series:
> https://lwn.net/Articles/726809/
> 
>  block/cfq-iosched.c | 19 ++++++++++++++-----
>  1 file changed, 14 insertions(+), 5 deletions(-)
> 
> diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
> index 92c31683a2bb..57ec45fd4590 100644
> --- a/block/cfq-iosched.c
> +++ b/block/cfq-iosched.c
> @@ -94,11 +94,13 @@ struct cfq_ttime {
>   */
>  struct cfq_rb_root {
>  	struct rb_root_cached rb;
> +	struct rb_node *rb_rightmost;
>  	unsigned count;
>  	u64 min_vdisktime;
>  	struct cfq_ttime ttime;
>  };
>  #define CFQ_RB_ROOT	(struct cfq_rb_root) { .rb = RB_ROOT_CACHED, \
> +			.rb_rightmost = NULL,			     \
>  			.ttime = {.last_end_request = ktime_get_ns(),},}
>  
>  /*
> @@ -1183,6 +1185,9 @@ static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root)
>  
>  static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
>  {
> +	if (root->rb_rightmost == n)
> +		root->rb_rightmost = rb_next(n);
> +
>  	rb_erase_cached(n, &root->rb);
>  	RB_CLEAR_NODE(n);
>  
> @@ -1239,20 +1244,24 @@ __cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
>  	struct rb_node *parent = NULL;
>  	struct cfq_group *__cfqg;
>  	s64 key = cfqg_key(st, cfqg);
> -	bool leftmost = true;
> +	bool leftmost = true, rightmost = true;
>  
>  	while (*node != NULL) {
>  		parent = *node;
>  		__cfqg = rb_entry_cfqg(parent);
>  
> -		if (key < cfqg_key(st, __cfqg))
> +		if (key < cfqg_key(st, __cfqg)) {
>  			node = &parent->rb_left;
> -		else {
> +			rightmost = false;
> +		} else {
>  			node = &parent->rb_right;
>  			leftmost = false;
>  		}
>  	}
>  
> +	if (rightmost)
> +		st->rb_rightmost = &cfqg->rb_node;
> +
>  	rb_link_node(&cfqg->rb_node, parent, node);
>  	rb_insert_color_cached(&cfqg->rb_node, &st->rb, leftmost);
>  }
> @@ -1355,7 +1364,7 @@ cfq_group_notify_queue_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
>  	 * so that groups get lesser vtime based on their weights, so that
>  	 * if group does not loose all if it was not continuously backlogged.
>  	 */
> -	n = rb_last(&st->rb.rb_root);
> +	n = st->rb_rightmost;
>  	if (n) {
>  		__cfqg = rb_entry_cfqg(n);
>  		cfqg->vdisktime = __cfqg->vdisktime +
> @@ -2204,7 +2213,7 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
>  	st = st_for(cfqq->cfqg, cfqq_class(cfqq), cfqq_type(cfqq));
>  	if (cfq_class_idle(cfqq)) {
>  		rb_key = CFQ_IDLE_DELAY;
> -		parent = rb_last(&st->rb.rb_root);
> +		parent = st->rb_rightmost;
>  		if (parent && parent != &cfqq->rb_node) {
>  			__cfqq = rb_entry(parent, struct cfq_queue, rb_node);
>  			rb_key += __cfqq->rb_key;
> -- 
> 2.12.0
> 
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

[toc] | [prev] | [next] | [standalone]

#1690899 — [PATCH 12/17] lib/interval-tree: correct comment wrt generic flavor

interval_tree.h _is_ the generic flavor.

Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
 include/linux/interval_tree_generic.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/include/linux/interval_tree_generic.h b/include/linux/interval_tree_generic.h
index f096423c8cbd..1f97ce26cccc 100644
--- a/include/linux/interval_tree_generic.h
+++ b/include/linux/interval_tree_generic.h
@@ -33,7 +33,7 @@
  * ITSTATIC:   'static' or empty
  * ITPREFIX:   prefix to use for the inline tree definitions
  *
- * Note - before using this, please consider if non-generic version
+ * Note - before using this, please consider if generic version
  * (interval_tree.h) would work for you...
  */
 
-- 
2.12.0

[toc] | [prev] | [next] | [standalone]

#1690900 — [PATCH 10/17] block/cfq: replace cfq_rb_root leftmost caching

... with the generic rbtree flavor instead. No changes
in semantics whatsoever.

Cc: axboe@fb.com
Cc: linux-block@vger.kernel.org
Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
 block/cfq-iosched.c | 70 +++++++++++++++--------------------------------------
 1 file changed, 20 insertions(+), 50 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 3d5c28945719..92c31683a2bb 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -93,13 +93,12 @@ struct cfq_ttime {
  * move this into the elevator for the rq sorting as well.
  */
 struct cfq_rb_root {
-	struct rb_root rb;
-	struct rb_node *left;
+	struct rb_root_cached rb;
 	unsigned count;
 	u64 min_vdisktime;
 	struct cfq_ttime ttime;
 };
-#define CFQ_RB_ROOT	(struct cfq_rb_root) { .rb = RB_ROOT, \
+#define CFQ_RB_ROOT	(struct cfq_rb_root) { .rb = RB_ROOT_CACHED, \
 			.ttime = {.last_end_request = ktime_get_ns(),},}
 
 /*
@@ -984,10 +983,9 @@ static inline u64 max_vdisktime(u64 min_vdisktime, u64 vdisktime)
 
 static void update_min_vdisktime(struct cfq_rb_root *st)
 {
-	struct cfq_group *cfqg;
+	if (!RB_EMPTY_ROOT(&st->rb.rb_root)) {
+		struct cfq_group *cfqg = rb_entry_cfqg(st->rb.rb_leftmost);
 
-	if (st->left) {
-		cfqg = rb_entry_cfqg(st->left);
 		st->min_vdisktime = max_vdisktime(st->min_vdisktime,
 						  cfqg->vdisktime);
 	}
@@ -1169,46 +1167,25 @@ cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2,
 	}
 }
 
-/*
- * The below is leftmost cache rbtree addon
- */
 static struct cfq_queue *cfq_rb_first(struct cfq_rb_root *root)
 {
 	/* Service tree is empty */
 	if (!root->count)
 		return NULL;
 
-	if (!root->left)
-		root->left = rb_first(&root->rb);
-
-	if (root->left)
-		return rb_entry(root->left, struct cfq_queue, rb_node);
-
-	return NULL;
+	return rb_entry(rb_first_cached(&root->rb), struct cfq_queue, rb_node);
 }
 
 static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root)
 {
-	if (!root->left)
-		root->left = rb_first(&root->rb);
-
-	if (root->left)
-		return rb_entry_cfqg(root->left);
-
-	return NULL;
+	return rb_entry_cfqg(rb_first_cached(&root->rb));
 }
 
-static void rb_erase_init(struct rb_node *n, struct rb_root *root)
+static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
 {
-	rb_erase(n, root);
+	rb_erase_cached(n, &root->rb);
 	RB_CLEAR_NODE(n);
-}
 
-static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
-{
-	if (root->left == n)
-		root->left = NULL;
-	rb_erase_init(n, &root->rb);
 	--root->count;
 }
 
@@ -1258,11 +1235,11 @@ cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg)
 static void
 __cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
 {
-	struct rb_node **node = &st->rb.rb_node;
+	struct rb_node **node = &st->rb.rb_root.rb_node;
 	struct rb_node *parent = NULL;
 	struct cfq_group *__cfqg;
 	s64 key = cfqg_key(st, cfqg);
-	int left = 1;
+	bool leftmost = true;
 
 	while (*node != NULL) {
 		parent = *node;
@@ -1272,15 +1249,12 @@ __cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
 			node = &parent->rb_left;
 		else {
 			node = &parent->rb_right;
-			left = 0;
+			leftmost = false;
 		}
 	}
 
-	if (left)
-		st->left = &cfqg->rb_node;
-
 	rb_link_node(&cfqg->rb_node, parent, node);
-	rb_insert_color(&cfqg->rb_node, &st->rb);
+	rb_insert_color_cached(&cfqg->rb_node, &st->rb, leftmost);
 }
 
 /*
@@ -1381,7 +1355,7 @@ cfq_group_notify_queue_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
 	 * so that groups get lesser vtime based on their weights, so that
 	 * if group does not loose all if it was not continuously backlogged.
 	 */
-	n = rb_last(&st->rb);
+	n = rb_last(&st->rb.rb_root);
 	if (n) {
 		__cfqg = rb_entry_cfqg(n);
 		cfqg->vdisktime = __cfqg->vdisktime +
@@ -2223,14 +2197,14 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 	struct cfq_queue *__cfqq;
 	u64 rb_key;
 	struct cfq_rb_root *st;
-	int left;
+	bool leftmost = true;
 	int new_cfqq = 1;
 	u64 now = ktime_get_ns();
 
 	st = st_for(cfqq->cfqg, cfqq_class(cfqq), cfqq_type(cfqq));
 	if (cfq_class_idle(cfqq)) {
 		rb_key = CFQ_IDLE_DELAY;
-		parent = rb_last(&st->rb);
+		parent = rb_last(&st->rb.rb_root);
 		if (parent && parent != &cfqq->rb_node) {
 			__cfqq = rb_entry(parent, struct cfq_queue, rb_node);
 			rb_key += __cfqq->rb_key;
@@ -2264,10 +2238,9 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 		cfqq->service_tree = NULL;
 	}
 
-	left = 1;
 	parent = NULL;
 	cfqq->service_tree = st;
-	p = &st->rb.rb_node;
+	p = &st->rb.rb_root.rb_node;
 	while (*p) {
 		parent = *p;
 		__cfqq = rb_entry(parent, struct cfq_queue, rb_node);
@@ -2279,16 +2252,13 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 			p = &parent->rb_left;
 		else {
 			p = &parent->rb_right;
-			left = 0;
+			leftmost = false;
 		}
 	}
 
-	if (left)
-		st->left = &cfqq->rb_node;
-
 	cfqq->rb_key = rb_key;
 	rb_link_node(&cfqq->rb_node, parent, p);
-	rb_insert_color(&cfqq->rb_node, &st->rb);
+	rb_insert_color_cached(&cfqq->rb_node, &st->rb, leftmost);
 	st->count++;
 	if (add_front || !new_cfqq)
 		return;
@@ -2735,7 +2705,7 @@ static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
 	/* There is nothing to dispatch */
 	if (!st)
 		return NULL;
-	if (RB_EMPTY_ROOT(&st->rb))
+	if (RB_EMPTY_ROOT(&st->rb.rb_root))
 		return NULL;
 	return cfq_rb_first(st);
 }
@@ -3221,7 +3191,7 @@ static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd)
 	struct cfq_rb_root *st = &cfqd->grp_service_tree;
 	struct cfq_group *cfqg;
 
-	if (RB_EMPTY_ROOT(&st->rb))
+	if (RB_EMPTY_ROOT(&st->rb.rb_root))
 		return NULL;
 	cfqg = cfq_rb_first_group(st);
 	update_min_vdisktime(st);
-- 
2.12.0

[toc] | [prev] | [next] | [standalone]

#1691076 — Re: [PATCH 10/17] block/cfq: replace cfq_rb_root leftmost caching

On Tue 18-07-17 18:45:56, Davidlohr Bueso wrote:
> ... with the generic rbtree flavor instead. No changes
> in semantics whatsoever.
> 
> Cc: axboe@fb.com
> Cc: linux-block@vger.kernel.org
> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> Signed-off-by: Davidlohr Bueso <dbueso@suse.de>

Looks good to me. You can add:

Reviewed-by: Jan Kara <jack@suse.cz>

								Honza

> ---
>  block/cfq-iosched.c | 70 +++++++++++++++--------------------------------------
>  1 file changed, 20 insertions(+), 50 deletions(-)
> 
> diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
> index 3d5c28945719..92c31683a2bb 100644
> --- a/block/cfq-iosched.c
> +++ b/block/cfq-iosched.c
> @@ -93,13 +93,12 @@ struct cfq_ttime {
>   * move this into the elevator for the rq sorting as well.
>   */
>  struct cfq_rb_root {
> -	struct rb_root rb;
> -	struct rb_node *left;
> +	struct rb_root_cached rb;
>  	unsigned count;
>  	u64 min_vdisktime;
>  	struct cfq_ttime ttime;
>  };
> -#define CFQ_RB_ROOT	(struct cfq_rb_root) { .rb = RB_ROOT, \
> +#define CFQ_RB_ROOT	(struct cfq_rb_root) { .rb = RB_ROOT_CACHED, \
>  			.ttime = {.last_end_request = ktime_get_ns(),},}
>  
>  /*
> @@ -984,10 +983,9 @@ static inline u64 max_vdisktime(u64 min_vdisktime, u64 vdisktime)
>  
>  static void update_min_vdisktime(struct cfq_rb_root *st)
>  {
> -	struct cfq_group *cfqg;
> +	if (!RB_EMPTY_ROOT(&st->rb.rb_root)) {
> +		struct cfq_group *cfqg = rb_entry_cfqg(st->rb.rb_leftmost);
>  
> -	if (st->left) {
> -		cfqg = rb_entry_cfqg(st->left);
>  		st->min_vdisktime = max_vdisktime(st->min_vdisktime,
>  						  cfqg->vdisktime);
>  	}
> @@ -1169,46 +1167,25 @@ cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2,
>  	}
>  }
>  
> -/*
> - * The below is leftmost cache rbtree addon
> - */
>  static struct cfq_queue *cfq_rb_first(struct cfq_rb_root *root)
>  {
>  	/* Service tree is empty */
>  	if (!root->count)
>  		return NULL;
>  
> -	if (!root->left)
> -		root->left = rb_first(&root->rb);
> -
> -	if (root->left)
> -		return rb_entry(root->left, struct cfq_queue, rb_node);
> -
> -	return NULL;
> +	return rb_entry(rb_first_cached(&root->rb), struct cfq_queue, rb_node);
>  }
>  
>  static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root)
>  {
> -	if (!root->left)
> -		root->left = rb_first(&root->rb);
> -
> -	if (root->left)
> -		return rb_entry_cfqg(root->left);
> -
> -	return NULL;
> +	return rb_entry_cfqg(rb_first_cached(&root->rb));
>  }
>  
> -static void rb_erase_init(struct rb_node *n, struct rb_root *root)
> +static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
>  {
> -	rb_erase(n, root);
> +	rb_erase_cached(n, &root->rb);
>  	RB_CLEAR_NODE(n);
> -}
>  
> -static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
> -{
> -	if (root->left == n)
> -		root->left = NULL;
> -	rb_erase_init(n, &root->rb);
>  	--root->count;
>  }
>  
> @@ -1258,11 +1235,11 @@ cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg)
>  static void
>  __cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
>  {
> -	struct rb_node **node = &st->rb.rb_node;
> +	struct rb_node **node = &st->rb.rb_root.rb_node;
>  	struct rb_node *parent = NULL;
>  	struct cfq_group *__cfqg;
>  	s64 key = cfqg_key(st, cfqg);
> -	int left = 1;
> +	bool leftmost = true;
>  
>  	while (*node != NULL) {
>  		parent = *node;
> @@ -1272,15 +1249,12 @@ __cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
>  			node = &parent->rb_left;
>  		else {
>  			node = &parent->rb_right;
> -			left = 0;
> +			leftmost = false;
>  		}
>  	}
>  
> -	if (left)
> -		st->left = &cfqg->rb_node;
> -
>  	rb_link_node(&cfqg->rb_node, parent, node);
> -	rb_insert_color(&cfqg->rb_node, &st->rb);
> +	rb_insert_color_cached(&cfqg->rb_node, &st->rb, leftmost);
>  }
>  
>  /*
> @@ -1381,7 +1355,7 @@ cfq_group_notify_queue_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
>  	 * so that groups get lesser vtime based on their weights, so that
>  	 * if group does not loose all if it was not continuously backlogged.
>  	 */
> -	n = rb_last(&st->rb);
> +	n = rb_last(&st->rb.rb_root);
>  	if (n) {
>  		__cfqg = rb_entry_cfqg(n);
>  		cfqg->vdisktime = __cfqg->vdisktime +
> @@ -2223,14 +2197,14 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
>  	struct cfq_queue *__cfqq;
>  	u64 rb_key;
>  	struct cfq_rb_root *st;
> -	int left;
> +	bool leftmost = true;
>  	int new_cfqq = 1;
>  	u64 now = ktime_get_ns();
>  
>  	st = st_for(cfqq->cfqg, cfqq_class(cfqq), cfqq_type(cfqq));
>  	if (cfq_class_idle(cfqq)) {
>  		rb_key = CFQ_IDLE_DELAY;
> -		parent = rb_last(&st->rb);
> +		parent = rb_last(&st->rb.rb_root);
>  		if (parent && parent != &cfqq->rb_node) {
>  			__cfqq = rb_entry(parent, struct cfq_queue, rb_node);
>  			rb_key += __cfqq->rb_key;
> @@ -2264,10 +2238,9 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
>  		cfqq->service_tree = NULL;
>  	}
>  
> -	left = 1;
>  	parent = NULL;
>  	cfqq->service_tree = st;
> -	p = &st->rb.rb_node;
> +	p = &st->rb.rb_root.rb_node;
>  	while (*p) {
>  		parent = *p;
>  		__cfqq = rb_entry(parent, struct cfq_queue, rb_node);
> @@ -2279,16 +2252,13 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
>  			p = &parent->rb_left;
>  		else {
>  			p = &parent->rb_right;
> -			left = 0;
> +			leftmost = false;
>  		}
>  	}
>  
> -	if (left)
> -		st->left = &cfqq->rb_node;
> -
>  	cfqq->rb_key = rb_key;
>  	rb_link_node(&cfqq->rb_node, parent, p);
> -	rb_insert_color(&cfqq->rb_node, &st->rb);
> +	rb_insert_color_cached(&cfqq->rb_node, &st->rb, leftmost);
>  	st->count++;
>  	if (add_front || !new_cfqq)
>  		return;
> @@ -2735,7 +2705,7 @@ static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
>  	/* There is nothing to dispatch */
>  	if (!st)
>  		return NULL;
> -	if (RB_EMPTY_ROOT(&st->rb))
> +	if (RB_EMPTY_ROOT(&st->rb.rb_root))
>  		return NULL;
>  	return cfq_rb_first(st);
>  }
> @@ -3221,7 +3191,7 @@ static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd)
>  	struct cfq_rb_root *st = &cfqd->grp_service_tree;
>  	struct cfq_group *cfqg;
>  
> -	if (RB_EMPTY_ROOT(&st->rb))
> +	if (RB_EMPTY_ROOT(&st->rb.rb_root))
>  		return NULL;
>  	cfqg = cfq_rb_first_group(st);
>  	update_min_vdisktime(st);
> -- 
> 2.12.0
> 
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

[toc] | [prev] | [next] | [standalone]

#1690902 — [PATCH 05/17] lib/rbtree_test.c: add (inorder) traversal test

This adds a second test for regular rb-tree testing in
that there is no need to repeat it for the augmented
flavor.

Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
 lib/rbtree_test.c | 25 +++++++++++++++++++++++--
 1 file changed, 23 insertions(+), 2 deletions(-)

diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index e83331aa1b7f..967999ff46db 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -183,6 +183,7 @@ static int __init rbtree_test_init(void)
 {
 	int i, j;
 	cycles_t time1, time2, time;
+	struct rb_node *node;
 
 	nodes = kmalloc(nnodes * sizeof(*nodes), GFP_KERNEL);
 	if (!nodes)
@@ -206,8 +207,28 @@ static int __init rbtree_test_init(void)
 	time = time2 - time1;
 
 	time = div_u64(time, perf_loops);
-	printk(" -> %llu cycles\n", (unsigned long long)time);
+	printk(" -> test 1 (latency of nnodes insert+delete): %llu cycles\n", (unsigned long long)time);
 
+	for (i = 0; i < nnodes; i++)
+		insert(nodes + i, &root);
+
+	time1 = get_cycles();
+
+	for (i = 0; i < perf_loops; i++) {
+		for (node = rb_first(&root); node; node = rb_next(node))
+			;
+	}
+
+	time2 = get_cycles();
+	time = time2 - time1;
+
+	time = div_u64(time, perf_loops);
+	printk(" -> test 2 (latency of inorder traversal): %llu cycles\n", (unsigned long long)time);
+
+	for (i = 0; i < nnodes; i++)
+		erase(nodes + i, &root);
+
+	/* run checks */
 	for (i = 0; i < check_loops; i++) {
 		init();
 		for (j = 0; j < nnodes; j++) {
@@ -238,7 +259,7 @@ static int __init rbtree_test_init(void)
 	time = time2 - time1;
 
 	time = div_u64(time, perf_loops);
-	printk(" -> %llu cycles\n", (unsigned long long)time);
+	printk(" -> test 1 (latency of nnodes insert+delete): %llu cycles\n", (unsigned long long)time);
 
 	for (i = 0; i < check_loops; i++) {
 		init();
-- 
2.12.0

[toc] | [prev] | [next] | [standalone]

#1690907 — [PATCH 04/17] lib/rbtree_test.c: make input module parameters

Allows for more flexible debugging.

Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
 lib/rbtree_test.c | 55 ++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 34 insertions(+), 21 deletions(-)

diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index 8b3c9dc88262..e83331aa1b7f 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -1,11 +1,18 @@
 #include <linux/module.h>
+#include <linux/moduleparam.h>
 #include <linux/rbtree_augmented.h>
 #include <linux/random.h>
+#include <linux/slab.h>
 #include <asm/timex.h>
 
-#define NODES       100
-#define PERF_LOOPS  100000
-#define CHECK_LOOPS 100
+#define __param(type, name, init, msg)		\
+	static type name = init;		\
+	module_param(name, type, 0444);		\
+	MODULE_PARM_DESC(name, msg);
+
+__param(int, nnodes, 100, "Number of nodes in the rb-tree");
+__param(int, perf_loops, 100000, "Number of iterations modifying the rb-tree");
+__param(int, check_loops, 100, "Number of iterations modifying and verifying the rb-tree");
 
 struct test_node {
 	u32 key;
@@ -17,7 +24,7 @@ struct test_node {
 };
 
 static struct rb_root root = RB_ROOT;
-static struct test_node nodes[NODES];
+static struct test_node *nodes = NULL;
 
 static struct rnd_state rnd;
 
@@ -95,7 +102,7 @@ static void erase_augmented(struct test_node *node, struct rb_root *root)
 static void init(void)
 {
 	int i;
-	for (i = 0; i < NODES; i++) {
+	for (i = 0; i < nnodes; i++) {
 		nodes[i].key = prandom_u32_state(&rnd);
 		nodes[i].val = prandom_u32_state(&rnd);
 	}
@@ -177,6 +184,10 @@ static int __init rbtree_test_init(void)
 	int i, j;
 	cycles_t time1, time2, time;
 
+	nodes = kmalloc(nnodes * sizeof(*nodes), GFP_KERNEL);
+	if (!nodes)
+		return -ENOMEM;
+
 	printk(KERN_ALERT "rbtree testing");
 
 	prandom_seed_state(&rnd, 3141592653589793238ULL);
@@ -184,27 +195,27 @@ static int __init rbtree_test_init(void)
 
 	time1 = get_cycles();
 
-	for (i = 0; i < PERF_LOOPS; i++) {
-		for (j = 0; j < NODES; j++)
+	for (i = 0; i < perf_loops; i++) {
+		for (j = 0; j < nnodes; j++)
 			insert(nodes + j, &root);
-		for (j = 0; j < NODES; j++)
+		for (j = 0; j < nnodes; j++)
 			erase(nodes + j, &root);
 	}
 
 	time2 = get_cycles();
 	time = time2 - time1;
 
-	time = div_u64(time, PERF_LOOPS);
+	time = div_u64(time, perf_loops);
 	printk(" -> %llu cycles\n", (unsigned long long)time);
 
-	for (i = 0; i < CHECK_LOOPS; i++) {
+	for (i = 0; i < check_loops; i++) {
 		init();
-		for (j = 0; j < NODES; j++) {
+		for (j = 0; j < nnodes; j++) {
 			check(j);
 			insert(nodes + j, &root);
 		}
-		for (j = 0; j < NODES; j++) {
-			check(NODES - j);
+		for (j = 0; j < nnodes; j++) {
+			check(nnodes - j);
 			erase(nodes + j, &root);
 		}
 		check(0);
@@ -216,32 +227,34 @@ static int __init rbtree_test_init(void)
 
 	time1 = get_cycles();
 
-	for (i = 0; i < PERF_LOOPS; i++) {
-		for (j = 0; j < NODES; j++)
+	for (i = 0; i < perf_loops; i++) {
+		for (j = 0; j < nnodes; j++)
 			insert_augmented(nodes + j, &root);
-		for (j = 0; j < NODES; j++)
+		for (j = 0; j < nnodes; j++)
 			erase_augmented(nodes + j, &root);
 	}
 
 	time2 = get_cycles();
 	time = time2 - time1;
 
-	time = div_u64(time, PERF_LOOPS);
+	time = div_u64(time, perf_loops);
 	printk(" -> %llu cycles\n", (unsigned long long)time);
 
-	for (i = 0; i < CHECK_LOOPS; i++) {
+	for (i = 0; i < check_loops; i++) {
 		init();
-		for (j = 0; j < NODES; j++) {
+		for (j = 0; j < nnodes; j++) {
 			check_augmented(j);
 			insert_augmented(nodes + j, &root);
 		}
-		for (j = 0; j < NODES; j++) {
-			check_augmented(NODES - j);
+		for (j = 0; j < nnodes; j++) {
+			check_augmented(nnodes - j);
 			erase_augmented(nodes + j, &root);
 		}
 		check_augmented(0);
 	}
 
+	kfree(nodes);
+
 	return -EAGAIN; /* Fail will directly unload the module */
 }
 
-- 
2.12.0

[toc] | [prev] | [next] | [standalone]

#1694181 — Re: [PATCH 11/17] lib/interval_tree: fast overlap detection

[Multipart message — attachments visible in raw view] — view raw

On 7/18/2017 9:45 PM, Davidlohr Bueso wrote:
> Allow interval trees to quickly check for overlaps to avoid
> unnecesary tree lookups in interval_tree_iter_first().
> 
> 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().
> 
> Cc: David Airlie <airlied@linux.ie>
> Cc: dri-devel@lists.freedesktop.org
> Cc: "Michael S. Tsirkin" <mst@redhat.com>
> Cc: Jason Wang <jasowang@redhat.com>
> Cc: Doug Ledford <dledford@redhat.com>
> Cc: Christian Benvenuti <benve@cisco.com>
> Cc: linux-rdma@vger.kernel.org
> Acked-by: Christian König <christian.koenig@amd.com>
> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> Signed-off-by: Davidlohr Bueso <dbueso@suse.de>

Ack for the RDMA parts.

Acked-by: Doug Ledford <dledford@redhat.com>


-- 
Doug Ledford <dledford@redhat.com>
    GPG Key ID: B826A3330E572FDD
    Key fingerprint = AE6B 1BDA 122B 23B4 265B  1274 B826 A333 0E57 2FDD

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web