Skip to contentSkip to conversation

rbtree: optimize frequent tree walks

PATCH In review Davidlohr Bueso 4 participants 18 messages Feb 7, 2020 – Feb 13, 2020

Subsystems (10)
Documentation VFS KVM perf events +6 more subsystems
lore
Share & tools
lore
#0 lore raw

cover rbtree: optimize frequent tree walks

This series introduces the ll_rbtree interface to optimize rbtree users that incur in frequent in-order tree iterations (even full traversals). This can be seen as an abstraction to what is already done for dealing with VMAs (albeit non-augmented trees).

Mainly, it trades off higher per-node memory footprint (two extra pointers) for minimal runtime overhead to gain O(1) brachless next and prev node pointers. See patch 1 for full details, but, for example, the following tables show the benefits vs the costs of using this new interface.

   +--------+--------------+-----------+
   | #nodes | plain rbtree | ll-rbtree |
   +--------+--------------+-----------+
   |     10 |          138 |        24 |
   |    100 |        7,200 |       425 |
   |   1000 |       17,000 |     8,000 |
   |  10000 |      501,090 |   222,500 |
   +--------+--------------+-----------+

While there are other node representations that optimize getting such pointers without bloating the nodes as much, such as keeping a parent pointer or threaded trees where the nil prev/next pointers are recycled; both incurring in higher runtime penalization for common modification operations as well as any rotations. The overhead of tree modifications can be seen in the following table, comparing cycles to insert+delete:

   +--------+--------------+------------------+-----------+
   | #nodes | plain rbtree | augmented rbtree | ll-rbtree |
   +--------+--------------+------------------+-----------+
   |     10 |          530 |              840 |       600 |
   |    100 |        7,100 |           14,200 |     7,800 |
   |   1000 |      265,000 |          370,000 |   205,200 |
   |  10000 |    4,400,000 |        5,500,000 | 4,200,000 |
   +--------+--------------+------------------+-----------+

Patch 1 introduces the ll_rbtree machinery.

Patches 2-5 convert users that might benefit from the new interface.

Full details and justifications for the conversion are in each individual patch.

I am Cc'ing some of the maintainers of the users I have converted to the whole series such that it can the numbers and interface details can be easily seen.

Please consider for v5.7.

Thanks!

Davidlohr Bueso (5):
lib/rbtree: introduce linked-list rbtree interface proc/sysctl: optimize proc_sys_readdir
regmap: optimize sync() and drop() regcache callbacks vfio/type1: optimize dma_list tree iterations
uprobes: optimize build_probe_list()

 Documentation/rbtree.txt              |  74 ++++++++++++++++++++++++
 drivers/base/regmap/regcache-rbtree.c |  62 +++++++++++---------
 drivers/vfio/vfio_iommu_type1.c       |  50 +++++++++--------
 fs/proc/proc_sysctl.c                 |  37 ++++++------
 include/linux/ll_rbtree.h             | 103 ++++++++++++++++++++++++++++++++++
 include/linux/sysctl.h                |   6 +-
 kernel/events/uprobes.c               |  47 ++++++++--------
 7 files changed, 286 insertions(+), 93 deletions(-)
 create mode 100644 include/linux/ll_rbtree.h
Signature · 1 line
2.16.4
#1 lore raw

PATCH 1/5 lib/rbtree: introduce linked-list rbtree interface

When doing in-order tree traversals, the rb_next() and rb_prev() helpers can be sub-optimal as plain node representations incur in extra pointer chasing up the tree to compute the corresponding node. This can impact negatively in performance when traversals are a common thing. This, for example, is what we do in our vm already to efficiently manage VMAs.

This interface provides branchless O(1) access to the first node as well as both its in-order successor and predecessor. This is done at the cost of higher memory footprint: mainly additional prev and next pointers for each node. Such benefits can be seen in this table showing the amount of cycles it takes to do a full tree traversal:

   +--------+--------------+-----------+
   | #nodes | plain rbtree | ll-rbtree |
   +--------+--------------+-----------+
   |     10 |          138 |        24 |
   |    100 |        7,200 |       425 |
   |   1000 |       17,000 |     8,000 |
   |  10000 |      501,090 |   222,500 |
   +--------+--------------+-----------+

While there are other node representations that optimize getting such pointers without bloating the nodes as much, such as keeping a parent pointer or threaded trees where the nil prev/next pointers are recycled; both incurring in higher runtime penalization for common modification operations as well as any rotations. The overhead of tree modifications can be seen in the following table, comparing cycles to insert+delete:

   +--------+--------------+------------------+-----------+
   | #nodes | plain rbtree | augmented rbtree | ll-rbtree |
   +--------+--------------+------------------+-----------+
   |     10 |          530 |              840 |       600 |
   |    100 |        7,100 |           14,200 |     7,800 |
   |   1000 |      265,000 |          370,000 |   205,200 |
   |  10000 |    4,400,000 |        5,500,000 | 4,200,000 |
   +--------+--------------+------------------+-----------+

This shows that we gain fast iterators at pretty much a negligible runtime overhead, where both regular and llrb trees are rather similar, but unsurprisingly there is really a noticible cost when augmenting the rbtree (wich is not important for this series perse).

Note that all data shown here is based on randomly populated rbtrees (albeit same seed) running a hacked version of lib/rbtree_test.c on a x86-64 2.6 Ghz IvyBridge system.

---
 Documentation/rbtree.txt  |  74 +++++++++++++++++++++++++++++++++
 include/linux/ll_rbtree.h | 103 ++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 177 insertions(+)
 create mode 100644 include/linux/ll_rbtree.h
Documentation/rbtree.txt +74 -0
index 523d54b60087..fe38fb257931 100644
@@ -5,6 +5,7 @@ Red-black Trees (rbtree) in Linux
 
 :Date: January 18, 2007
 :Author: Rob Landley <[email protected]>
+         Davidlohr Bueso <[email protected]>
 
 What are red-black trees, and what are they for?
 ------------------------------------------------
@@ -226,6 +227,79 @@ trees::
 				 struct rb_augment_callbacks *);
 
 
+Linked-list rbtrees
+-------------------
+
+When doing in-order tree traversals, the rb_next() and rb_prev() helpers can
+be sub-optimal as plain node representations incur in extra pointer chasing
+up the tree to compute the corresponding node. This can have a negative impact
+in latencies in scenarios where tree traversals are not rare. This interface
+provides branchless O(1) access to the first node as well as both its in-order
+successor and predecessor. This is done at the cost of higher memory footprint:
+mainly additional prev and next pointers for each node, essentially duplicating
+the tree data structure. While there are other node representations that optimize
+getting such pointers without bloating the nodes as much, such as keeping a
+parent pointer or threaded trees where the nil prev/next pointers are recycled;
+both incurring in higher runtime penalization for common modification operations
+as well as any rotations.
+
+As with regular rb_root structure, linked-list rbtrees are initialized to be
+empty via::
+
+  struct llrb_root mytree = LLRB_ROOT;
+
+Insertion and deletion are defined by:
+
+  void llrb_insert(struct llrb_root *, struct llrb_node *, struct llrb_node *);
+  void llrb_erase(struct llrb_node *, struct llrb_root *);
+
+The corresponding helpers needed to iterate through a tree are the following,
+equivalent to an optimized version of the regular rbtree version:
+
+  struct llrb_node *llrb_first(struct llrb_root *tree);
+  struct llrb_node *llrb_next(struct rb_node *node);
+  struct llrb_node *llrb_prev(struct rb_node *node);
+
+
+Inserting data into a Linked-list rbtree
+----------------------------------------
+
+Because llrb trees can exist anywhere regular rbtrees, the steps are similar.
+The search for insertion differs from the regular search in two ways. First
+the caller must keep track of the previous node, and secondly the caller must
+combine both regular nodes for the actual iteration down and convert from rb_node
+to llrb_node.
+
+Example::
+
+  int my_insert(struct llrb_root *root, struct mytype *data)
+  {
+	struct rb_node **new = &(root->rb_node.rb_node), *parent = NULL;
+	struct llrb_node *prev = NULL;
+
+	/* Figure out where to put new node */
+	while (*new) {
+		struct mytype *this = llrb_entry(*new, struct mytype, node);
+		int result = strcmp(data->keystring, this->keystring);
+
+		parent = *new;
+		if (result < 0)
+			new = &((*new)->rb_left);
+		else if (result > 0) {
+			prev = llrb_from_rb(*parent);
+			new = &((*new)->rb_right);
+		} else
+			return FALSE;
+	}
+
+	/* Add new node and rebalance tree. */
+	rb_link_node(&data->node.rb_node, parent, new);
+	llrb_insert(root, &data->node, prev);
+
+	return TRUE;
+  }
+
+
 Support for Augmented rbtrees
 -----------------------------
 
include/linux/ll_rbtree.h new file +103 -0

103 lines not on this page · raw message

Signature · 1 line
2.16.4
Reviewed-by on v1 1/5
#2 lore raw

Re: [PATCH 1/5] lib/rbtree: introduce linked-list rbtree interface

Quoted 7 lines · Davidlohr Bueso

When doing in-order tree traversals, the rb_next() and rb_prev() helpers can be sub-optimal as plain node representations incur in extra pointer chasing up the tree to compute the corresponding node. This can impact negatively in performance when traversals are a common thing. This, for example, is what we do in our vm already to efficiently manage VMAs.

This interface provides branchless O(1)

I think including the word "branchless" does injustice to the optimization, just O(1) sells it to me more to how I read the code. Why is the "branchless" prefix needed here?

Quoted 6 lines

access to the first node as well as
both its in-order successor and predecessor. This is done at the cost of higher memory footprint: mainly additional prev and next pointers for each node. Such benefits can be seen in this table showing the amount of cycles it takes to do a full tree traversal:

Quoted 8 lines
   +--------+--------------+-----------+
   | #nodes | plain rbtree | ll-rbtree |
   +--------+--------------+-----------+
   |     10 |          138 |        24 |
   |    100 |        7,200 |       425 |
   |   1000 |       17,000 |     8,000 |
   |  10000 |      501,090 |   222,500 |
   +--------+--------------+-----------+

Sold, however I wonder if we can have *one new API* where based on just one Kconfig you either get the two pointers or not, the performance gain then would only be observed if this new kconfig entry is enabled. The benefit of this is that we don't shove the performance benefit down all user's throughts but rather this can be decided by distributions and system integrators.

Quoted 46 lines
Documentation/rbtree.txt +31 -0
index 523d54b60087..fe38fb257931 100644
@@ -5,6 +5,7 @@ Red-black Trees (rbtree) in Linux
 
 :Date: January 18, 2007
 :Author: Rob Landley <[email protected]>
+         Davidlohr Bueso <[email protected]>
 
 What are red-black trees, and what are they for?
 ------------------------------------------------
@@ -226,6 +227,79 @@ trees::
 				 struct rb_augment_callbacks *);
 
 
+Linked-list rbtrees
+-------------------
+
+When doing in-order tree traversals, the rb_next() and rb_prev() helpers can
+be sub-optimal as plain node representations incur in extra pointer chasing
+up the tree to compute the corresponding node. This can have a negative impact
+in latencies in scenarios where tree traversals are not rare. This interface
+provides branchless O(1) access to the first node as well as both its in-order
+successor and predecessor. This is done at the cost of higher memory footprint:
+mainly additional prev and next pointers for each node, essentially duplicating
+the tree data structure. While there are other node representations that optimize
+getting such pointers without bloating the nodes as much, such as keeping a
+parent pointer or threaded trees where the nil prev/next pointers are recycled;
+both incurring in higher runtime penalization for common modification operations
+as well as any rotations.
+
+As with regular rb_root structure, linked-list rbtrees are initialized to be
+empty via::
+
+  struct llrb_root mytree = LLRB_ROOT;
+
+Insertion and deletion are defined by:
+
+  void llrb_insert(struct llrb_root *, struct llrb_node *, struct llrb_node *);
+  void llrb_erase(struct llrb_node *, struct llrb_root *);
+
+The corresponding helpers needed to iterate through a tree are the following,
+equivalent to an optimized version of the regular rbtree version:
+
+  struct llrb_node *llrb_first(struct llrb_root *tree);

Documentation/rbtree.txt trees:: · line 269

Quoted 10 lines
Documentation/rbtree.txt +10 -0
+  struct llrb_node *llrb_next(struct rb_node *node);
+  struct llrb_node *llrb_prev(struct rb_node *node);
+
+
+Inserting data into a Linked-list rbtree
+----------------------------------------
+
+Because llrb trees can exist anywhere regular rbtrees, the steps are similar.
+The search for insertion differs from the regular search in two ways. First
+the caller must keep track of the previous node,

can you explain here why, even though its clear in the code: its because we need to pass it as a parameter when the new node is inserted into the rb tree.

Also, what about a selftest for this?

Luis

#3 lore raw

Re: [PATCH 1/5] lib/rbtree: introduce linked-list rbtree interface

Quoted 3 lines · Luis Chamberlain

I think including the word "branchless" does injustice to the optimization, just O(1) sells it to me more to how I read the code. Why is the "branchless" prefix needed here?

Yes, compared to regular rb_next() 'branchless' would be unnecessary.

However compared to other node representations that are easier on the memory footprint (parent pointers or threaded trees) also have O(1) but still have branches - but most importantly, these approaches incur in higher overhead for modifications to the tree.

Quoted 16 lines
Quoted 7 lines

access to the first node as well as
both its in-order successor and predecessor. This is done at the cost of higher memory footprint: mainly additional prev and next pointers for each node. Such benefits can be seen in this table showing the amount of cycles it takes to do a full tree traversal:

Quoted 8 lines
   +--------+--------------+-----------+
   | #nodes | plain rbtree | ll-rbtree |
   +--------+--------------+-----------+
   |     10 |          138 |        24 |
   |    100 |        7,200 |       425 |
   |   1000 |       17,000 |     8,000 |
   |  10000 |      501,090 |   222,500 |
   +--------+--------------+-----------+
Quoted 6 lines

Sold, however I wonder if we can have *one new API* where based on just one Kconfig you either get the two pointers or not, the performance gain then would only be observed if this new kconfig entry is enabled. The benefit of this is that we don't shove the performance benefit down all user's throughts but rather this can be decided by distributions and system integrators.

I don't think we want an all or nothing approach as different users in the kernel have different needs and some users are simply unable to deal with enlarging data structures, while others have no problem.

Quoted 12 lines

...

Documentation/rbtree.txt trees::

Quoted 6 lines
Documentation/rbtree.txt +6 -0
+Inserting data into a Linked-list rbtree
+----------------------------------------
+
+Because llrb trees can exist anywhere regular rbtrees, the steps are similar.
+The search for insertion differs from the regular search in two ways. First
+the caller must keep track of the previous node,

can you explain here why, even though its clear in the code: its because we need to pass it as a parameter when the new node is inserted into the rb tree.

Right. We piggyback from the node info we already have available ie when user iterates down the tree to find a point of insertion.

Quoted 2 lines

Also, what about a selftest for this?

So we have lib/rbtree_test.c which does functional+latency testing - which I am planning on updating if this series is merged. I first have some patches that improve the overall module that are unrelated to this series and therefore did not send it.

Quoted 2 lines

Thanks,
Davidlohr

#4 lore raw

Re: [PATCH 1/5] lib/rbtree: introduce linked-list rbtree interface

Quoted 16 lines · Davidlohr Bueso
Quoted 15 lines · Luis Chamberlain
Quoted 14 lines

access to the first node as well as
both its in-order successor and predecessor. This is done at the cost of higher memory footprint: mainly additional prev and next pointers for each node. Such benefits can be seen in this table showing the amount of cycles it takes to do a full tree traversal:

   +--------+--------------+-----------+
   | #nodes | plain rbtree | ll-rbtree |
   +--------+--------------+-----------+
   |     10 |          138 |        24 |
   |    100 |        7,200 |       425 |
   |   1000 |       17,000 |     8,000 |
   |  10000 |      501,090 |   222,500 |
   +--------+--------------+-----------+
Quoted 8 lines
Quoted 6 lines

Sold, however I wonder if we can have *one new API* where based on just one Kconfig you either get the two pointers or not, the performance gain then would only be observed if this new kconfig entry is enabled. The benefit of this is that we don't shove the performance benefit down all user's throughts but rather this can be decided by distributions and system integrators.

I don't think we want an all or nothing approach

I'm not suggesting all or nothing for all rb tree users, I'm suggesting an all or nothing approach to users of a *new* API. That is, users would still need to be converted over, and *iff* the new kconfig entry is enabled would the two pointers be added / used, otherwise we'd fallback to the default current boring rbtree.

Quoted 3 lines

as different users in the
kernel have different needs and some users are simply unable to deal with enlarging data structures, while others have no problem.

The approach would allow distros which are not yet sure if two pointers are worth it yet to continue to chug on as they used to, but also allow them to explore this prospect in a flexible way.

Luis

#5 lore raw

PATCH 2/5 proc/sysctl: optimize proc_sys_readdir

In reply to Davidlohr Bueso

This patch coverts struct ctl_dir to use an llrbtree instead of a regular rbtree such that computing nodes for potential usable entries becomes a branchless O(1) operation, therefore optimizing first_usable_entry(). The cost are mainly three additional pointers: one for the root and two for each struct ctl_node next/prev nodes, enlarging it from 32 to 48 bytes on x86-64.

---
 fs/proc/proc_sysctl.c  | 37 +++++++++++++++++++------------------
 include/linux/sysctl.h |  6 +++---
 2 files changed, 22 insertions(+), 21 deletions(-)
fs/proc/proc_sysctl.c +19 -18
index d80989b6c344..5a1b3b8be16b 100644
@@ -111,15 +111,14 @@ static struct ctl_table *find_entry(struct ctl_table_header **phead,
 {
 	struct ctl_table_header *head;
 	struct ctl_table *entry;
-	struct rb_node *node = dir->root.rb_node;
+	struct rb_node *node = dir->root.rb_root.rb_node;
 
-	while (node)
-	{
+	while (node) {
 		struct ctl_node *ctl_node;
 		const char *procname;
 		int cmp;
 
-		ctl_node = rb_entry(node, struct ctl_node, node);
+		ctl_node = llrb_entry(node, struct ctl_node, node);
 		head = ctl_node->header;
 		entry = &head->ctl_table[ctl_node - head->node];
 		procname = entry->procname;
@@ -139,9 +138,10 @@ static struct ctl_table *find_entry(struct ctl_table_header **phead,
 
 static int insert_entry(struct ctl_table_header *head, struct ctl_table *entry)
 {
-	struct rb_node *node = &head->node[entry - head->ctl_table].node;
-	struct rb_node **p = &head->parent->root.rb_node;
+	struct rb_node *node = &head->node[entry - head->ctl_table].node.rb_node;
+	struct rb_node **p = &head->parent->root.rb_root.rb_node;
 	struct rb_node *parent = NULL;
+	struct llrb_node *prev = NULL;
 	const char *name = entry->procname;
 	int namelen = strlen(name);
 
@@ -153,7 +153,7 @@ static int insert_entry(struct ctl_table_header *head, struct ctl_table *entry)
 		int cmp;
 
 		parent = *p;
-		parent_node = rb_entry(parent, struct ctl_node, node);
+		parent_node = llrb_entry(parent, struct ctl_node, node);
 		parent_head = parent_node->header;
 		parent_entry = &parent_head->ctl_table[parent_node - parent_head->node];
 		parent_name = parent_entry->procname;
@@ -161,9 +161,10 @@ static int insert_entry(struct ctl_table_header *head, struct ctl_table *entry)
 		cmp = namecmp(name, namelen, parent_name, strlen(parent_name));
 		if (cmp < 0)
 			p = &(*p)->rb_left;
-		else if (cmp > 0)
+		else if (cmp > 0) {
+			prev = llrb_from_rb(parent);
 			p = &(*p)->rb_right;
-		else {
+		} else {
 			pr_err("sysctl duplicate entry: ");
 			sysctl_print_dir(head->parent);
 			pr_cont("/%s\n", entry->procname);
@@ -172,15 +173,15 @@ static int insert_entry(struct ctl_table_header *head, struct ctl_table *entry)
 	}
 
 	rb_link_node(node, parent, p);
-	rb_insert_color(node, &head->parent->root);
+	llrb_insert(&head->parent->root, llrb_from_rb(node), prev);
 	return 0;
 }
 
 static void erase_entry(struct ctl_table_header *head, struct ctl_table *entry)
 {
-	struct rb_node *node = &head->node[entry - head->ctl_table].node;
+	struct llrb_node *node = &head->node[entry - head->ctl_table].node;
 
-	rb_erase(node, &head->parent->root);
+	llrb_erase(node, &head->parent->root);
 }
 
 static void init_header(struct ctl_table_header *head,
@@ -223,7 +224,7 @@ static int insert_header(struct ctl_dir *dir, struct ctl_table_header *header)
 
 	/* Am I creating a permanently empty directory? */
 	if (header->ctl_table == sysctl_mount_point) {
-		if (!RB_EMPTY_ROOT(&dir->root))
+		if (!RB_EMPTY_ROOT(&dir->root.rb_root))
 			return -EINVAL;
 		set_empty_dir(dir);
 	}
@@ -381,11 +382,11 @@ static struct ctl_table *lookup_entry(struct ctl_table_header **phead,
 	return entry;
 }
 
-static struct ctl_node *first_usable_entry(struct rb_node *node)
+static struct ctl_node *first_usable_entry(struct llrb_node *node)
 {
 	struct ctl_node *ctl_node;
 
-	for (;node; node = rb_next(node)) {
+	for (; node; node = llrb_next(node)) {
 		ctl_node = rb_entry(node, struct ctl_node, node);
 		if (use_table(ctl_node->header))
 			return ctl_node;
@@ -401,7 +402,7 @@ static void first_entry(struct ctl_dir *dir,
 	struct ctl_node *ctl_node;
 
 	spin_lock(&sysctl_lock);
-	ctl_node = first_usable_entry(rb_first(&dir->root));
+	ctl_node = first_usable_entry(llrb_first(&dir->root));
 	spin_unlock(&sysctl_lock);
 	if (ctl_node) {
 		head = ctl_node->header;
@@ -420,7 +421,7 @@ static void next_entry(struct ctl_table_header **phead, struct ctl_table **pentr
 	spin_lock(&sysctl_lock);
 	unuse_table(head);
 
-	ctl_node = first_usable_entry(rb_next(&ctl_node->node));
+	ctl_node = first_usable_entry(llrb_next(&ctl_node->node));
 	spin_unlock(&sysctl_lock);
 	head = NULL;
 	if (ctl_node) {
@@ -1711,7 +1712,7 @@ void setup_sysctl_set(struct ctl_table_set *set,
 
 void retire_sysctl_set(struct ctl_table_set *set)
 {
-	WARN_ON(!RB_EMPTY_ROOT(&set->dir.root));
+	WARN_ON(!RB_EMPTY_ROOT(&set->dir.root.rb_root));
 }
 
 int __init proc_sys_init(void)
include/linux/sysctl.h +3 -3
index 02fa84493f23..afb35fa61b91 100644
@@ -25,7 +25,7 @@
 #include <linux/list.h>
 #include <linux/rcupdate.h>
 #include <linux/wait.h>
-#include <linux/rbtree.h>
+#include <linux/ll_rbtree.h>
 #include <linux/uidgid.h>
 #include <uapi/linux/sysctl.h>
 
@@ -133,7 +133,7 @@ struct ctl_table {
 } __randomize_layout;
 
 struct ctl_node {
-	struct rb_node node;
+	struct llrb_node node;
 	struct ctl_table_header *header;
 };
 
@@ -161,7 +161,7 @@ struct ctl_table_header {
 struct ctl_dir {
 	/* Header must be at the start of ctl_dir */
 	struct ctl_table_header header;
-	struct rb_root root;
+	struct llrb_root root;
 };
 
 struct ctl_table_set {
Signature · 1 line
2.16.4
Acked-by on v1 2/5
#6 lore raw

Re: [PATCH 2/5] proc/sysctl: optimize proc_sys_readdir

Quoted 7 lines · Davidlohr Bueso

This patch coverts struct ctl_dir to use an llrbtree instead of a regular rbtree such that computing nodes for potential usable entries becomes a branchless O(1) operation, therefore optimizing first_usable_entry(). The cost are mainly three additional pointers: one for the root and two for each struct ctl_node next/prev nodes, enlarging it from 32 to 48 bytes on x86-64.

Luis

#7 lore raw

PATCH 3/5 regmap: optimize sync() and drop() regcache callbacks

In reply to Davidlohr Bueso

At a higher memory footprint (two additional pointers per node) we can get branchless O(1) tree iterators which can optimize in-order tree walks/traversals. For example, on my laptop looking at the rbtree debugfs entries:

before:
60 nodes, 165 registers, average 2 registers, used 4036 bytes
after:
60 nodes, 165 registers, average 2 registers, used 5004 bytes

---
 drivers/base/regmap/regcache-rbtree.c | 62 +++++++++++++++++++----------------
 1 file changed, 34 insertions(+), 28 deletions(-)
drivers/base/regmap/regcache-rbtree.c +34 -28
index cfa29dc89bbf..d55f6b6c87b4 100644
@@ -8,7 +8,7 @@
 
 #include <linux/debugfs.h>
 #include <linux/device.h>
-#include <linux/rbtree.h>
+#include <linux/ll_rbtree.h>
 #include <linux/seq_file.h>
 #include <linux/slab.h>
 
@@ -28,11 +28,11 @@ struct regcache_rbtree_node {
 	/* number of registers available in the block */
 	unsigned int blklen;
 	/* the actual rbtree node holding this block */
-	struct rb_node node;
+	struct llrb_node node;
 };
 
 struct regcache_rbtree_ctx {
-	struct rb_root root;
+	struct llrb_root root;
 	struct regcache_rbtree_node *cached_rbnode;
 };
 
@@ -75,9 +75,9 @@ static struct regcache_rbtree_node *regcache_rbtree_lookup(struct regmap *map,
 			return rbnode;
 	}
 
-	node = rbtree_ctx->root.rb_node;
+	node = rbtree_ctx->root.rb_root.rb_node;
 	while (node) {
-		rbnode = rb_entry(node, struct regcache_rbtree_node, node);
+		rbnode = llrb_entry(node, struct regcache_rbtree_node, node);
 		regcache_rbtree_get_base_top_reg(map, rbnode, &base_reg,
 						 &top_reg);
 		if (reg >= base_reg && reg <= top_reg) {
@@ -93,18 +93,20 @@ static struct regcache_rbtree_node *regcache_rbtree_lookup(struct regmap *map,
 	return NULL;
 }
 
-static int regcache_rbtree_insert(struct regmap *map, struct rb_root *root,
+static int regcache_rbtree_insert(struct regmap *map, struct llrb_root *root,
 				  struct regcache_rbtree_node *rbnode)
 {
 	struct rb_node **new, *parent;
+	struct llrb_node *prev = NULL;
 	struct regcache_rbtree_node *rbnode_tmp;
 	unsigned int base_reg_tmp, top_reg_tmp;
 	unsigned int base_reg;
 
 	parent = NULL;
-	new = &root->rb_node;
+	new = &root->rb_root.rb_node;
 	while (*new) {
-		rbnode_tmp = rb_entry(*new, struct regcache_rbtree_node, node);
+		rbnode_tmp = llrb_entry(*new,
+					struct regcache_rbtree_node, node);
 		/* base and top registers of the current rbnode */
 		regcache_rbtree_get_base_top_reg(map, rbnode_tmp, &base_reg_tmp,
 						 &top_reg_tmp);
@@ -115,15 +117,16 @@ static int regcache_rbtree_insert(struct regmap *map, struct rb_root *root,
 		if (base_reg >= base_reg_tmp &&
 		    base_reg <= top_reg_tmp)
 			return 0;
-		else if (base_reg > top_reg_tmp)
+		else if (base_reg > top_reg_tmp) {
+			prev = llrb_from_rb(parent);
 			new = &((*new)->rb_right);
-		else if (base_reg < base_reg_tmp)
+		} else if (base_reg < base_reg_tmp)
 			new = &((*new)->rb_left);
 	}
 
 	/* insert the node into the rbtree */
-	rb_link_node(&rbnode->node, parent, new);
-	rb_insert_color(&rbnode->node, root);
+	rb_link_node(&rbnode->node.rb_node, parent, new);
+	llrb_insert(root, &rbnode->node, prev);
 
 	return 1;
 }
@@ -134,7 +137,7 @@ static int rbtree_show(struct seq_file *s, void *ignored)
 	struct regmap *map = s->private;
 	struct regcache_rbtree_ctx *rbtree_ctx = map->cache;
 	struct regcache_rbtree_node *n;
-	struct rb_node *node;
+	struct llrb_node *node;
 	unsigned int base, top;
 	size_t mem_size;
 	int nodes = 0;
@@ -145,8 +148,8 @@ static int rbtree_show(struct seq_file *s, void *ignored)
 
 	mem_size = sizeof(*rbtree_ctx);
 
-	for (node = rb_first(&rbtree_ctx->root); node != NULL;
-	     node = rb_next(node)) {
+	for (node = llrb_first(&rbtree_ctx->root); node != NULL;
+	     node = llrb_next(node)) {
 		n = rb_entry(node, struct regcache_rbtree_node, node);
 		mem_size += sizeof(*n);
 		mem_size += (n->blklen * map->cache_word_size);
@@ -192,7 +195,7 @@ static int regcache_rbtree_init(struct regmap *map)
 		return -ENOMEM;
 
 	rbtree_ctx = map->cache;
-	rbtree_ctx->root = RB_ROOT;
+	rbtree_ctx->root = LLRB_ROOT;
 	rbtree_ctx->cached_rbnode = NULL;
 
 	for (i = 0; i < map->num_reg_defaults; i++) {
@@ -212,7 +215,7 @@ static int regcache_rbtree_init(struct regmap *map)
 
 static int regcache_rbtree_exit(struct regmap *map)
 {
-	struct rb_node *next;
+	struct llrb_node *next;
 	struct regcache_rbtree_ctx *rbtree_ctx;
 	struct regcache_rbtree_node *rbtree_node;
 
@@ -222,11 +225,11 @@ static int regcache_rbtree_exit(struct regmap *map)
 		return 0;
 
 	/* free up the rbtree */
-	next = rb_first(&rbtree_ctx->root);
+	next = llrb_first(&rbtree_ctx->root);
 	while (next) {
 		rbtree_node = rb_entry(next, struct regcache_rbtree_node, node);
-		next = rb_next(&rbtree_node->node);
-		rb_erase(&rbtree_node->node, &rbtree_ctx->root);
+		next = llrb_next(&rbtree_node->node);
+		llrb_erase(&rbtree_node->node, &rbtree_ctx->root);
 		kfree(rbtree_node->cache_present);
 		kfree(rbtree_node->block);
 		kfree(rbtree_node);
@@ -400,10 +403,10 @@ static int regcache_rbtree_write(struct regmap *map, unsigned int reg,
 		max = reg + max_dist;
 
 		/* look for an adjacent register to the one we are about to add */
-		node = rbtree_ctx->root.rb_node;
+		node = rbtree_ctx->root.rb_root.rb_node;
 		while (node) {
-			rbnode_tmp = rb_entry(node, struct regcache_rbtree_node,
-					      node);
+			rbnode_tmp = llrb_entry(node,
+					      struct regcache_rbtree_node, node);
 
 			regcache_rbtree_get_base_top_reg(map, rbnode_tmp,
 				&base_reg, &top_reg);
@@ -466,15 +469,17 @@ static int regcache_rbtree_sync(struct regmap *map, unsigned int min,
 				unsigned int max)
 {
 	struct regcache_rbtree_ctx *rbtree_ctx;
-	struct rb_node *node;
+	struct llrb_node *node;
 	struct regcache_rbtree_node *rbnode;
 	unsigned int base_reg, top_reg;
 	unsigned int start, end;
 	int ret;
 
 	rbtree_ctx = map->cache;
-	for (node = rb_first(&rbtree_ctx->root); node; node = rb_next(node)) {
-		rbnode = rb_entry(node, struct regcache_rbtree_node, node);
+	for (node = llrb_first(&rbtree_ctx->root); node;
+	     node = llrb_next(node)) {
+		rbnode = rb_entry(node,
+				  struct regcache_rbtree_node, node);
 
 		regcache_rbtree_get_base_top_reg(map, rbnode, &base_reg,
 			&top_reg);
@@ -508,12 +513,13 @@ static int regcache_rbtree_drop(struct regmap *map, unsigned int min,
 {
 	struct regcache_rbtree_ctx *rbtree_ctx;
 	struct regcache_rbtree_node *rbnode;
-	struct rb_node *node;
+	struct llrb_node *node;
 	unsigned int base_reg, top_reg;
 	unsigned int start, end;
 
 	rbtree_ctx = map->cache;
-	for (node = rb_first(&rbtree_ctx->root); node; node = rb_next(node)) {
+	for (node = llrb_first(&rbtree_ctx->root); node;
+	     node = llrb_next(node)) {
 		rbnode = rb_entry(node, struct regcache_rbtree_node, node);
 
 		regcache_rbtree_get_base_top_reg(map, rbnode, &base_reg,
Signature · 1 line
2.16.4
maintainer Acked-by on v1 3/5
#8 lore raw

Re: [PATCH 3/5] regmap: optimize sync() and drop() regcache callbacks

Quoted 4 lines · Davidlohr Bueso

At a higher memory footprint (two additional pointers per node) we can get branchless O(1) tree iterators which can optimize in-order tree walks/traversals. For example, on my laptop looking at the rbtree debugfs entries:

It's not clear that this is a good optimization - we're increasing the memory footprint for a bit of performance but our performance is all relative to the I2C or SPI I/O we're most likely all in the noise here whereas for larger maps the size cost looks like it could be quite bad (but equally your case looks to have a lot of 2 register blocks which is almost the worst case for overhead so...).

That said the code is fine so from that point of view:

#9 lore raw

PATCH 4/5 vfio/type1: optimize dma_list tree iterations

In reply to Davidlohr Bueso

Both ->release() and ->attach_group() vfio_iommu driver callbacks can incur in full in-order iommu->dma_list traversals, which can be suboptimal under regular rbtree interators. This patch proposes using the optimized llrbtree interface such that we always have a branchless O(1) next node available. The cost is higher memory footprint, mainly enlarging struct vfio_dma by two pointers. This allows for minimal runtime overhead when doing tree modifications.

---
 drivers/vfio/vfio_iommu_type1.c | 50 +++++++++++++++++++++++------------------
 1 file changed, 28 insertions(+), 22 deletions(-)
drivers/vfio/vfio_iommu_type1.c +28 -22
index 2ada8e6cdb88..875170fc8515 100644
@@ -28,6 +28,7 @@
 #include <linux/module.h>
 #include <linux/mm.h>
 #include <linux/rbtree.h>
+#include <linux/ll_rbtree.h>
 #include <linux/sched/signal.h>
 #include <linux/sched/mm.h>
 #include <linux/slab.h>
@@ -65,7 +66,7 @@ struct vfio_iommu {
 	struct list_head	iova_list;
 	struct vfio_domain	*external_domain; /* domain for external user */
 	struct mutex		lock;
-	struct rb_root		dma_list;
+	struct llrb_root	dma_list;
 	struct blocking_notifier_head notifier;
 	unsigned int		dma_avail;
 	bool			v2;
@@ -81,7 +82,7 @@ struct vfio_domain {
 };
 
 struct vfio_dma {
-	struct rb_node		node;
+	struct llrb_node	node;
 	dma_addr_t		iova;		/* Device address */
 	unsigned long		vaddr;		/* Process virtual addr */
 	size_t			size;		/* Map size (bytes) */
@@ -134,10 +135,10 @@ static int put_pfn(unsigned long pfn, int prot);
 static struct vfio_dma *vfio_find_dma(struct vfio_iommu *iommu,
 				      dma_addr_t start, size_t size)
 {
-	struct rb_node *node = iommu->dma_list.rb_node;
+	struct rb_node *node = iommu->dma_list.rb_root.rb_node;
 
 	while (node) {
-		struct vfio_dma *dma = rb_entry(node, struct vfio_dma, node);
+		struct vfio_dma *dma = llrb_entry(node, struct vfio_dma, node);
 
 		if (start + size <= dma->iova)
 			node = node->rb_left;
@@ -152,26 +153,30 @@ static struct vfio_dma *vfio_find_dma(struct vfio_iommu *iommu,
 
 static void vfio_link_dma(struct vfio_iommu *iommu, struct vfio_dma *new)
 {
-	struct rb_node **link = &iommu->dma_list.rb_node, *parent = NULL;
+	struct rb_node **link = &iommu->dma_list.rb_root.rb_node;
+	struct rb_node *parent = NULL;
+	struct llrb_node *prev = NULL;
 	struct vfio_dma *dma;
 
 	while (*link) {
 		parent = *link;
-		dma = rb_entry(parent, struct vfio_dma, node);
+		dma = llrb_entry(parent, struct vfio_dma, node);
 
 		if (new->iova + new->size <= dma->iova)
 			link = &(*link)->rb_left;
-		else
+		else {
 			link = &(*link)->rb_right;
+			prev = llrb_from_rb(parent);
+		}
 	}
 
-	rb_link_node(&new->node, parent, link);
-	rb_insert_color(&new->node, &iommu->dma_list);
+	rb_link_node(&new->node.rb_node, parent, link);
+	llrb_insert(&iommu->dma_list, &new->node, prev);
 }
 
 static void vfio_unlink_dma(struct vfio_iommu *iommu, struct vfio_dma *old)
 {
-	rb_erase(&old->node, &iommu->dma_list);
+	llrb_erase(&old->node, &iommu->dma_list);
 }
 
 /*
@@ -1170,15 +1175,15 @@ static int vfio_iommu_replay(struct vfio_iommu *iommu,
 			     struct vfio_domain *domain)
 {
 	struct vfio_domain *d;
-	struct rb_node *n;
+	struct llrb_node *n;
 	unsigned long limit = rlimit(RLIMIT_MEMLOCK) >> PAGE_SHIFT;
 	int ret;
 
 	/* Arbitrarily pick the first domain in the list for lookups */
 	d = list_first_entry(&iommu->domain_list, struct vfio_domain, next);
-	n = rb_first(&iommu->dma_list);
+	n = llrb_first(&iommu->dma_list);
 
-	for (; n; n = rb_next(n)) {
+	for (; n; n = llrb_next(n)) {
 		struct vfio_dma *dma;
 		dma_addr_t iova;
 
@@ -1835,18 +1840,19 @@ static int vfio_iommu_type1_attach_group(void *iommu_data,
 
 static void vfio_iommu_unmap_unpin_all(struct vfio_iommu *iommu)
 {
-	struct rb_node *node;
+	struct llrb_node *node;
 
-	while ((node = rb_first(&iommu->dma_list)))
+	while ((node = llrb_first(&iommu->dma_list)))
 		vfio_remove_dma(iommu, rb_entry(node, struct vfio_dma, node));
 }
 
 static void vfio_iommu_unmap_unpin_reaccount(struct vfio_iommu *iommu)
 {
-	struct rb_node *n, *p;
+	struct llrb_node *n;
+	struct rb_node *p;
 
-	n = rb_first(&iommu->dma_list);
-	for (; n; n = rb_next(n)) {
+	n = llrb_first(&iommu->dma_list);
+	for (; n; n = llrb_next(n)) {
 		struct vfio_dma *dma;
 		long locked = 0, unlocked = 0;
 
@@ -1866,10 +1872,10 @@ static void vfio_iommu_unmap_unpin_reaccount(struct vfio_iommu *iommu)
 
 static void vfio_sanity_check_pfn_list(struct vfio_iommu *iommu)
 {
-	struct rb_node *n;
+	struct llrb_node *n;
 
-	n = rb_first(&iommu->dma_list);
-	for (; n; n = rb_next(n)) {
+	n = llrb_first(&iommu->dma_list);
+	for (; n; n = llrb_next(n)) {
 		struct vfio_dma *dma;
 
 		dma = rb_entry(n, struct vfio_dma, node);
@@ -2060,7 +2066,7 @@ static void *vfio_iommu_type1_open(unsigned long arg)
 
 	INIT_LIST_HEAD(&iommu->domain_list);
 	INIT_LIST_HEAD(&iommu->iova_list);
-	iommu->dma_list = RB_ROOT;
+	iommu->dma_list = LLRB_ROOT;
 	iommu->dma_avail = dma_entry_limit;
 	mutex_init(&iommu->lock);
 	BLOCKING_INIT_NOTIFIER_HEAD(&iommu->notifier);
Signature · 1 line
2.16.4
#10 lore raw

PATCH 5/5 uprobes: optimize build_probe_list()

In reply to Davidlohr Bueso

We can optimize the uprobes_tree iterators when calling build_probe_list() by using llrbtrees, having the previous and next nodes from the given range available in branchless O(1). The runtime overhead to maintain this data is minimal for tree modifications, however the cost comes from enlarging mostly the struct uprobe by two pointers and therefore we sacrifice memory footprint.

---
 kernel/events/uprobes.c | 47 +++++++++++++++++++++++++----------------------
 1 file changed, 25 insertions(+), 22 deletions(-)
kernel/events/uprobes.c +25 -22
index ece7e13f6e4a..0a7b593578d1 100644
@@ -27,18 +27,19 @@
 #include <linux/task_work.h>
 #include <linux/shmem_fs.h>
 #include <linux/khugepaged.h>
+#include <linux/ll_rbtree.h>
 
 #include <linux/uprobes.h>
 
 #define UINSNS_PER_PAGE			(PAGE_SIZE/UPROBE_XOL_SLOT_BYTES)
 #define MAX_UPROBE_XOL_SLOTS		UINSNS_PER_PAGE
 
-static struct rb_root uprobes_tree = RB_ROOT;
+static struct llrb_root uprobes_tree = LLRB_ROOT;
 /*
  * allows us to skip the uprobe_mmap if there are no uprobe events active
  * at this time.  Probably a fine grained per inode count is better?
  */
-#define no_uprobe_events()	RB_EMPTY_ROOT(&uprobes_tree)
+#define no_uprobe_events()	RB_EMPTY_ROOT(&uprobes_tree.rb_root)
 
 static DEFINE_SPINLOCK(uprobes_treelock);	/* serialize rbtree access */
 
@@ -53,7 +54,7 @@ DEFINE_STATIC_PERCPU_RWSEM(dup_mmap_sem);
 #define UPROBE_COPY_INSN	0
 
 struct uprobe {
-	struct rb_node		rb_node;	/* node in the rb tree */
+	struct llrb_node	rb_node;	/* node in the llrb tree */
 	refcount_t		ref;
 	struct rw_semaphore	register_rwsem;
 	struct rw_semaphore	consumer_rwsem;
@@ -639,12 +640,12 @@ static int match_uprobe(struct uprobe *l, struct uprobe *r)
 static struct uprobe *__find_uprobe(struct inode *inode, loff_t offset)
 {
 	struct uprobe u = { .inode = inode, .offset = offset };
-	struct rb_node *n = uprobes_tree.rb_node;
+	struct rb_node *n = uprobes_tree.rb_root.rb_node;
 	struct uprobe *uprobe;
 	int match;
 
 	while (n) {
-		uprobe = rb_entry(n, struct uprobe, rb_node);
+		uprobe = llrb_entry(n, struct uprobe, rb_node);
 		match = match_uprobe(&u, uprobe);
 		if (!match)
 			return get_uprobe(uprobe);
@@ -674,28 +675,30 @@ static struct uprobe *find_uprobe(struct inode *inode, loff_t offset)
 
 static struct uprobe *__insert_uprobe(struct uprobe *uprobe)
 {
-	struct rb_node **p = &uprobes_tree.rb_node;
+	struct rb_node **p = &uprobes_tree.rb_root.rb_node;
 	struct rb_node *parent = NULL;
+	struct llrb_node *prev = NULL;
 	struct uprobe *u;
 	int match;
 
 	while (*p) {
 		parent = *p;
-		u = rb_entry(parent, struct uprobe, rb_node);
+		u = llrb_entry(parent, struct uprobe, rb_node);
 		match = match_uprobe(uprobe, u);
 		if (!match)
 			return get_uprobe(u);
 
 		if (match < 0)
 			p = &parent->rb_left;
-		else
+		else {
 			p = &parent->rb_right;
-
+			prev = llrb_from_rb(parent);
+		}
 	}
 
 	u = NULL;
-	rb_link_node(&uprobe->rb_node, parent, p);
-	rb_insert_color(&uprobe->rb_node, &uprobes_tree);
+	rb_link_node(&uprobe->rb_node.rb_node, parent, p);
+	llrb_insert(&uprobes_tree, &uprobe->rb_node, prev);
 	/* get access + creation ref */
 	refcount_set(&uprobe->ref, 2);
 
@@ -940,7 +943,7 @@ remove_breakpoint(struct uprobe *uprobe, struct mm_struct *mm, unsigned long vad
 
 static inline bool uprobe_is_active(struct uprobe *uprobe)
 {
-	return !RB_EMPTY_NODE(&uprobe->rb_node);
+	return !RB_EMPTY_NODE(&uprobe->rb_node.rb_node);
 }
 /*
  * There could be threads that have already hit the breakpoint. They
@@ -953,9 +956,9 @@ static void delete_uprobe(struct uprobe *uprobe)
 		return;
 
 	spin_lock(&uprobes_treelock);
-	rb_erase(&uprobe->rb_node, &uprobes_tree);
+	llrb_erase(&uprobe->rb_node, &uprobes_tree);
 	spin_unlock(&uprobes_treelock);
-	RB_CLEAR_NODE(&uprobe->rb_node); /* for uprobe_is_active() */
+	RB_CLEAR_NODE(&uprobe->rb_node.rb_node); /* for uprobe_is_active() */
 	put_uprobe(uprobe);
 }
 
@@ -1263,13 +1266,13 @@ static int unapply_uprobe(struct uprobe *uprobe, struct mm_struct *mm)
 	return err;
 }
 
-static struct rb_node *
+static struct llrb_node *
 find_node_in_range(struct inode *inode, loff_t min, loff_t max)
 {
-	struct rb_node *n = uprobes_tree.rb_node;
+	struct rb_node *n = uprobes_tree.rb_root.rb_node;
 
 	while (n) {
-		struct uprobe *u = rb_entry(n, struct uprobe, rb_node);
+		struct uprobe *u = llrb_entry(n, struct uprobe, rb_node);
 
 		if (inode < u->inode) {
 			n = n->rb_left;
@@ -1285,7 +1288,7 @@ find_node_in_range(struct inode *inode, loff_t min, loff_t max)
 		}
 	}
 
-	return n;
+	return llrb_from_rb(n);
 }
 
 /*
@@ -1297,7 +1300,7 @@ static void build_probe_list(struct inode *inode,
 				struct list_head *head)
 {
 	loff_t min, max;
-	struct rb_node *n, *t;
+	struct llrb_node *n, *t;
 	struct uprobe *u;
 
 	INIT_LIST_HEAD(head);
@@ -1307,14 +1310,14 @@ static void build_probe_list(struct inode *inode,
 	spin_lock(&uprobes_treelock);
 	n = find_node_in_range(inode, min, max);
 	if (n) {
-		for (t = n; t; t = rb_prev(t)) {
+		for (t = n; t; t = llrb_prev(t)) {
 			u = rb_entry(t, struct uprobe, rb_node);
 			if (u->inode != inode || u->offset < min)
 				break;
 			list_add(&u->pending_list, head);
 			get_uprobe(u);
 		}
-		for (t = n; (t = rb_next(t)); ) {
+		for (t = n; (t = llrb_next(t)); ) {
 			u = rb_entry(t, struct uprobe, rb_node);
 			if (u->inode != inode || u->offset > max)
 				break;
@@ -1406,7 +1409,7 @@ vma_has_uprobes(struct vm_area_struct *vma, unsigned long start, unsigned long e
 {
 	loff_t min, max;
 	struct inode *inode;
-	struct rb_node *n;
+	struct llrb_node *n;
 
 	inode = file_inode(vma->vm_file);
 
Signature · 1 line
2.16.4
#11 lore raw
In reply to Davidlohr Bueso
Quoted 40 lines · On Fri, 7 Feb 2020 10:03:00 -0800 Davidlohr Bueso <[email protected]> wrote:

This series introduces the ll_rbtree interface to optimize rbtree users that incur in frequent in-order tree iterations (even full traversals). This can be seen as an abstraction to what is already done for dealing with VMAs (albeit non-augmented trees).

Mainly, it trades off higher per-node memory footprint (two extra pointers) for minimal runtime overhead to gain O(1) brachless next and prev node pointers. See patch 1 for full details, but, for example, the following tables show the benefits vs the costs of using this new interface.

   +--------+--------------+-----------+
   | #nodes | plain rbtree | ll-rbtree |
   +--------+--------------+-----------+
   |     10 |          138 |        24 |
   |    100 |        7,200 |       425 |
   |   1000 |       17,000 |     8,000 |
   |  10000 |      501,090 |   222,500 |
   +--------+--------------+-----------+

While there are other node representations that optimize getting such pointers without bloating the nodes as much, such as keeping a parent pointer or threaded trees where the nil prev/next pointers are recycled; both incurring in higher runtime penalization for common modification operations as well as any rotations. The overhead of tree modifications can be seen in the following table, comparing cycles to insert+delete:

   +--------+--------------+------------------+-----------+
   | #nodes | plain rbtree | augmented rbtree | ll-rbtree |
   +--------+--------------+------------------+-----------+
   |     10 |          530 |              840 |       600 |
   |    100 |        7,100 |           14,200 |     7,800 |
   |   1000 |      265,000 |          370,000 |   205,200 |
   |  10000 |    4,400,000 |        5,500,000 | 4,200,000 |
   +--------+--------------+------------------+-----------+

Patch 1 introduces the ll_rbtree machinery.

Patches 2-5 convert users that might benefit from the new interface.

Quoted 7 lines

Full details and justifications for the conversion are in each individual patch.

I am Cc'ing some of the maintainers of the users I have converted to the whole series such that it can the numbers and interface details can be easily seen.

Please consider for v5.7.

Seems that all the caller sites you've converted use a fairly small number of rbnodes, so the additional storage shouldn't be a big problem. Are there any other sites you're eyeing? If so, do you expect any of those will use a significant amount of memory for the nodes?

And... are these patches really worth merging? Complexity is added, but what end-user benefit can we expect?

#12 lore raw
Quoted 4 lines · Andrew Morton

Seems that all the caller sites you've converted use a fairly small number of rbnodes, so the additional storage shouldn't be a big problem. Are there any other sites you're eyeing? If so, do you expect any of those will use a significant amount of memory for the nodes?

I also thought about converting the deadline scheduler to use these, mainly benefiting pull_dl_task() but didn't get to it and I don't expect the extra footprint to be prohibitive.

Quoted 3 lines

And... are these patches really worth merging? Complexity is added, but what end-user benefit can we expect?

Yes they are worth merging, imo (which of course is biased :)

I don't think there is too much added complexity overall, particularly considering that the user conversions are rather trivial. And even for small trees (ie 100 nodes) we still benefit in a measurable way from these optimizations.

Thanks,
Davidlohr

#13 lore raw
Quoted 14 lines · On Mon, 10 Feb 2020 07:56:11 -0800 Davidlohr Bueso <[email protected]> wrote:
Quoted 4 lines · Andrew Morton

Seems that all the caller sites you've converted use a fairly small number of rbnodes, so the additional storage shouldn't be a big problem. Are there any other sites you're eyeing? If so, do you expect any of those will use a significant amount of memory for the nodes?

I also thought about converting the deadline scheduler to use these, mainly benefiting pull_dl_task() but didn't get to it and I don't expect the extra footprint to be prohibitive.

Quoted 3 lines

And... are these patches really worth merging? Complexity is added, but what end-user benefit can we expect?

Quoted 7 lines

Yes they are worth merging, imo (which of course is biased :)

I don't think there is too much added complexity overall, particularly considering that the user conversions are rather trivial. And even for small trees (ie 100 nodes) we still benefit in a measurable way from these optimizations.

Measurable for microbenchmarks, I think? But what benefit will a user see, running a workload that is cared about?

#14 lore raw
Quoted 2 lines · Andrew Morton

Measurable for microbenchmarks, I think? But what benefit will a user see, running a workload that is cared about?

Well avoiding pointer chasing on large SMP systems has been shown to be something we care about in the past. And yes my performance data comes from an adhoc test scenario which only measures iteration latencies but that doesn't mean there isn't value here.

Thanks,
Davidlohr

maintainer
#15 lore raw
In reply to Davidlohr Bueso
Quoted 11 lines · Davidlohr Bueso
Quoted 2 lines · Andrew Morton

And... are these patches really worth merging? Complexity is added, but what end-user benefit can we expect?

Yes they are worth merging, imo (which of course is biased :)

I don't think there is too much added complexity overall, particularly considering that the user conversions are rather trivial. And even for small trees (ie 100 nodes) we still benefit in a measurable way from these optimizations.

As I said in reply to the regmap patch I'm really unconvinced that any benefit will outweigh the increased memory costs for that usage.

#16 lore raw
Quoted 2 lines · Mark Brown

As I said in reply to the regmap patch I'm really unconvinced that any benefit will outweigh the increased memory costs for that usage.

I'm not arguing the regmap case; if it's not worth it it's not worth it. With that conversion I was merely hoping that sync was used enough for it to be considered.

Thanks,
Davidlohr

maintainer
#17 lore raw
Quoted 8 lines · Davidlohr Bueso
Quoted 2 lines · Mark Brown

As I said in reply to the regmap patch I'm really unconvinced that any benefit will outweigh the increased memory costs for that usage.

I'm not arguing the regmap case; if it's not worth it it's not worth it. With that conversion I was merely hoping that sync was used enough for it to be considered.

Well, it's used a fair amount but like I say it's mainly used in the context of working out what I2C or SPI I/O to do so the amount of CPU time consumed is neither here nor there really, we'd have to be doing spectacularly badly for it to register.