1 files changed, 64 insertions, 27 deletions

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c
index 3166026a1874..3cc5fbd78ee2 100644
--- a/drivers/gpu/drm/drm_mm.c
+++ b/drivers/gpu/drm/drm_mm.c
@@ -239,6 +239,32 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node,
 #define HOLE_SIZE(NODE) ((NODE)->hole_size)
 #define HOLE_ADDR(NODE) (__drm_mm_hole_node_start(NODE))
 
+static u64 rb_to_hole_size(struct rb_node *rb)
+{
+	return rb_entry(rb, struct drm_mm_node, rb_hole_size)->hole_size;
+}
+
+static void insert_hole_size(struct rb_root_cached *root,
+			     struct drm_mm_node *node)
+{
+	struct rb_node **link = &root->rb_root.rb_node, *rb = NULL;
+	u64 x = node->hole_size;
+	bool first = true;
+
+	while (*link) {
+		rb = *link;
+		if (x > rb_to_hole_size(rb)) {
+			link = &rb->rb_left;
+		} else {
+			link = &rb->rb_right;
+			first = false;
+		}
+	}
+
+	rb_link_node(&node->rb_hole_size, rb, link);
+	rb_insert_color_cached(&node->rb_hole_size, root, first);
+}
+
 static void add_hole(struct drm_mm_node *node)
 {
 	struct drm_mm *mm = node->mm;
@@ -247,7 +273,7 @@ static void add_hole(struct drm_mm_node *node)
 		__drm_mm_hole_node_end(node) - __drm_mm_hole_node_start(node);
 	DRM_MM_BUG_ON(!drm_mm_hole_follows(node));
 
-	RB_INSERT(mm->holes_size, rb_hole_size, HOLE_SIZE);
+	insert_hole_size(&mm->holes_size, node);
 	RB_INSERT(mm->holes_addr, rb_hole_addr, HOLE_ADDR);
 
 	list_add(&node->hole_stack, &mm->hole_stack);
@@ -258,7 +284,7 @@ static void rm_hole(struct drm_mm_node *node)
 	DRM_MM_BUG_ON(!drm_mm_hole_follows(node));
 
 	list_del(&node->hole_stack);
-	rb_erase(&node->rb_hole_size, &node->mm->holes_size);
+	rb_erase_cached(&node->rb_hole_size, &node->mm->holes_size);
 	rb_erase(&node->rb_hole_addr, &node->mm->holes_addr);
 	node->hole_size = 0;
 
@@ -282,38 +308,39 @@ static inline u64 rb_hole_size(struct rb_node *rb)
 
 static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size)
 {
-	struct rb_node *best = NULL;
-	struct rb_node **link = &mm->holes_size.rb_node;
+	struct rb_node *rb = mm->holes_size.rb_root.rb_node;
+	struct drm_mm_node *best = NULL;
 
-	while (*link) {
-		struct rb_node *rb = *link;
+	do {
+		struct drm_mm_node *node =
+			rb_entry(rb, struct drm_mm_node, rb_hole_size);
 
-		if (size <= rb_hole_size(rb)) {
-			link = &rb->rb_left;
-			best = rb;
+		if (size <= node->hole_size) {
+			best = node;
+			rb = rb->rb_right;
 		} else {
-			link = &rb->rb_right;
+			rb = rb->rb_left;
 		}
-	}
+	} while (rb);
 
-	return rb_hole_size_to_node(best);
+	return best;
 }
 
 static struct drm_mm_node *find_hole(struct drm_mm *mm, u64 addr)
 {
+	struct rb_node *rb = mm->holes_addr.rb_node;
 	struct drm_mm_node *node = NULL;
-	struct rb_node **link = &mm->holes_addr.rb_node;
 
-	while (*link) {
+	while (rb) {
 		u64 hole_start;
 
-		node = rb_hole_addr_to_node(*link);
+		node = rb_hole_addr_to_node(rb);
 		hole_start = __drm_mm_hole_node_start(node);
 
 		if (addr < hole_start)
-			link = &node->rb_hole_addr.rb_left;
+			rb = node->rb_hole_addr.rb_left;
 		else if (addr > hole_start + node->hole_size)
-			link = &node->rb_hole_addr.rb_right;
+			rb = node->rb_hole_addr.rb_right;
 		else
 			break;
 	}
@@ -326,9 +353,6 @@ first_hole(struct drm_mm *mm,
 	   u64 start, u64 end, u64 size,
 	   enum drm_mm_insert_mode mode)
 {
-	if (RB_EMPTY_ROOT(&mm->holes_size))
-		return NULL;
-
 	switch (mode) {
 	default:
 	case DRM_MM_INSERT_BEST:
@@ -355,7 +379,7 @@ next_hole(struct drm_mm *mm,
 	switch (mode) {
 	default:
 	case DRM_MM_INSERT_BEST:
-		return rb_hole_size_to_node(rb_next(&node->rb_hole_size));
+		return rb_hole_size_to_node(rb_prev(&node->rb_hole_size));
 
 	case DRM_MM_INSERT_LOW:
 		return rb_hole_addr_to_node(rb_next(&node->rb_hole_addr));
@@ -426,6 +450,11 @@ int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node)
 }
 EXPORT_SYMBOL(drm_mm_reserve_node);
 
+static u64 rb_to_hole_size_or_zero(struct rb_node *rb)
+{
+	return rb ? rb_to_hole_size(rb) : 0;
+}
+
 /**
  * drm_mm_insert_node_in_range - ranged search for space and insert @node
  * @mm: drm_mm to allocate from
@@ -451,18 +480,26 @@ int drm_mm_insert_node_in_range(struct drm_mm * const mm,
 {
 	struct drm_mm_node *hole;
 	u64 remainder_mask;
+	bool once;
 
 	DRM_MM_BUG_ON(range_start >= range_end);
 
 	if (unlikely(size == 0 || range_end - range_start < size))
 		return -ENOSPC;
 
+	if (rb_to_hole_size_or_zero(rb_first_cached(&mm->holes_size)) < size)
+		return -ENOSPC;
+
 	if (alignment <= 1)
 		alignment = 0;
 
+	once = mode & DRM_MM_INSERT_ONCE;
+	mode &= ~DRM_MM_INSERT_ONCE;
+
 	remainder_mask = is_power_of_2(alignment) ? alignment - 1 : 0;
-	for (hole = first_hole(mm, range_start, range_end, size, mode); hole;
-	     hole = next_hole(mm, hole, mode)) {
+	for (hole = first_hole(mm, range_start, range_end, size, mode);
+	     hole;
+	     hole = once ? NULL : next_hole(mm, hole, mode)) {
 		u64 hole_start = __drm_mm_hole_node_start(hole);
 		u64 hole_end = hole_start + hole->hole_size;
 		u64 adj_start, adj_end;
@@ -587,9 +624,9 @@ void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new)
 
 	if (drm_mm_hole_follows(old)) {
 		list_replace(&old->hole_stack, &new->hole_stack);
-		rb_replace_node(&old->rb_hole_size,
-				&new->rb_hole_size,
-				&mm->holes_size);
+		rb_replace_node_cached(&old->rb_hole_size,
+				       &new->rb_hole_size,
+				       &mm->holes_size);
 		rb_replace_node(&old->rb_hole_addr,
 				&new->rb_hole_addr,
 				&mm->holes_addr);
@@ -885,7 +922,7 @@ void drm_mm_init(struct drm_mm *mm, u64 start, u64 size)
 
 	INIT_LIST_HEAD(&mm->hole_stack);
 	mm->interval_tree = RB_ROOT_CACHED;
-	mm->holes_size = RB_ROOT;
+	mm->holes_size = RB_ROOT_CACHED;
 	mm->holes_addr = RB_ROOT;
 
 	/* Clever trick to avoid a special case in the free hole tracking. */