diff mbox

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

Message ID 20180219085728.7517-2-chris@chris-wilson.co.uk (mailing list archive)
State New, archived
Headers show

Commit Message

Chris Wilson Feb. 19, 2018, 8:57 a.m. UTC 
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@chris-wilson.co.uk>
---
 drivers/gpu/drm/drm_mm.c | 16 ++++++++++------
 1 file changed, 10 insertions(+), 6 deletions(-)

Comments

Joonas Lahtinen Feb. 20, 2018, 9:58 a.m. UTC | #1 
Quoting Chris Wilson (2018-02-19 10:57:28)
> 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@chris-wilson.co.uk>

Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>

Regards, Joonas
diff mbox

Patch

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)