[1/2] drm/mm: expand rb_hole_addr augmented callbacks

Commit Message

Nirmoy Das May 19, 2020, 8:44 a.m. UTC

Expand RB_DECLARE_CALLBACKS_MAX so that it is possible to store
extra value(max hole alignment) in the rb_hole_addr augmented rbtree.

Signed-off-by: Nirmoy Das <[e-mail]>
---
 drivers/gpu/drm/drm_mm.c | 72 ++++++++++++++++++++++++++++++++++++++--
 1 file changed, 69 insertions(+), 3 deletions(-)

--
2.26.2

Patch

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c
index f4ca1ff80af9..91e90c635e05 100644
--- a/drivers/gpu/drm/drm_mm.c
+++ b/drivers/gpu/drm/drm_mm.c
@@ -241,9 +241,74 @@  static void insert_hole_size(struct rb_root_cached *root,
 	rb_insert_color_cached(&node->rb_hole_size, root, first);
 }

-RB_DECLARE_CALLBACKS_MAX(static, augment_callbacks,
-			 struct drm_mm_node, rb_hole_addr,
-			 u64, subtree_max_hole, HOLE_SIZE)
+static inline bool
+augment_callbacks_compute_max_hole(struct drm_mm_node *node, bool exit)
+{
+	struct drm_mm_node *child;
+	u64 max = HOLE_SIZE(node);
+
+	if (node->rb_hole_addr.rb_left) {
+		child = rb_entry(node->rb_hole_addr.rb_left, struct drm_mm_node,
+				 rb_hole_addr);
+		if (child->subtree_max_hole > max)
+			max = child->subtree_max_hole;
+	}
+
+	if (node->rb_hole_addr.rb_right) {
+		child = rb_entry(node->rb_hole_addr.rb_right,
+				 struct drm_mm_node, rb_hole_addr);
+		if (child->subtree_max_hole > max)
+			max = child->subtree_max_hole;
+	}
+
+	if (exit && node->subtree_max_hole == max)
+		return true;
+
+	node->subtree_max_hole = max;
+	return false;
+}
+
+static inline void
+augment_callbacks_propagate(struct rb_node *rb, struct rb_node *stop)
+{
+	while (rb != stop) {
+		struct drm_mm_node *node = rb_entry(rb,  struct drm_mm_node,
+						    rb_hole_addr);
+		if (augment_callbacks_compute_max_hole(node, true))
+			break;
+
+		rb = rb_parent(&node->rb_hole_addr);
+	}
+}
+
+static inline void
+augment_callbacks_copy(struct rb_node *rb_old, struct rb_node *rb_new)
+{
+	struct drm_mm_node *old = rb_entry(rb_old, struct drm_mm_node,
+					   rb_hole_addr);
+	struct drm_mm_node *new = rb_entry(rb_new, struct drm_mm_node,
+					   rb_hole_addr);
+
+	new->subtree_max_hole = old->subtree_max_hole;
+}
+
+static void
+augment_callbacks_rotate(struct rb_node *rb_old, struct rb_node *rb_new)
+{
+	struct drm_mm_node *old = rb_entry(rb_old, struct drm_mm_node,
+					   rb_hole_addr);
+	struct drm_mm_node *new = rb_entry(rb_new, struct drm_mm_node,
+					   rb_hole_addr);
+
+	new->subtree_max_hole = old->subtree_max_hole;
+	augment_callbacks_compute_max_hole(old, false);
+}
+
+static const struct rb_augment_callbacks augment_callbacks = {
+	.propagate = augment_callbacks_propagate,
+	.copy = augment_callbacks_copy,
+	.rotate = augment_callbacks_rotate
+};

 static void insert_hole_addr(struct rb_root *root, struct drm_mm_node *node)
 {
@@ -256,6 +321,7 @@  static void insert_hole_addr(struct rb_root *root, struct drm_mm_node *node)
 		parent = rb_entry(rb_parent, struct drm_mm_node, rb_hole_addr);
 		if (parent->subtree_max_hole < subtree_max_hole)
 			parent->subtree_max_hole = subtree_max_hole;
+
 		if (start < HOLE_ADDR(parent))
 			link = &parent->rb_hole_addr.rb_left;
 		else