[PATCH 2/2] drm/mm: Micro-optimise updating the upper layers of the interval tree

[Chris Wilson]

When we insert a node into a hole inside the interval tree, we need to
climb the layers above us to update the cached interval. When doing so,
we know that the initial node exists as it is our starting hole.

add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-10 (-10)
Function                                     old     new   delta
drm_mm_interval_tree_add_node                221     211     -10

Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
---
 drivers/gpu/drm/drm_mm.c | 16 ++++++++++------
 1 file changed, 10 insertions(+), 6 deletions(-)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c
index a351bd888a61..2d844c9a288f 100644
--- a/drivers/gpu/drm/drm_mm.c
+++ b/drivers/gpu/drm/drm_mm.c
@@ -179,21 +179,23 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node,
 {
 	struct drm_mm *mm = hole_node->mm;
 	struct rb_node **link, *rb;
-	struct drm_mm_node *parent;
 	bool leftmost;
 
 	node->__subtree_last = LAST(node);
 
-	if (hole_node->allocated) {
-		rb = &hole_node->rb;
-		while (rb) {
-			parent = rb_entry(rb, struct drm_mm_node, rb);
+	if (likely(hole_node->allocated)) {
+		struct drm_mm_node *parent;
+
+		/* Update the interval range above us */
+		parent = hole_node;
+		do {
 			if (parent->__subtree_last >= node->__subtree_last)
 				break;
 
 			parent->__subtree_last = node->__subtree_last;
 			rb = rb_parent(rb);
-		}
+		} while ((parent = rb_entry_safe(&parent->rb,
+						 struct drm_mm_node, rb)));
 
 		rb = &hole_node->rb;
 		link = &hole_node->rb.rb_right;
@@ -205,6 +207,8 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node,
 	}
 
 	while (*link) {
+		struct drm_mm_node *parent;
+
 		rb = *link;
 		parent = rb_entry(rb, struct drm_mm_node, rb);
 		if (parent->__subtree_last < node->__subtree_last)
-- 
2.16.1