drm/mm: expand rb_hole_addr augmented callbacks
Subsystems (2)
PATCH 1/2 drm/mm: expand rb_hole_addr augmented callbacks
Expand RB_DECLARE_CALLBACKS_MAX so that it is possible to store extra value(max hole alignment) in the rb_hole_addr augmented rbtree.
--- drivers/gpu/drm/drm_mm.c | 72 ++++++++++++++++++++++++++++++++++++++-- 1 file changed, 69 insertions(+), 3 deletions(-)
drivers/gpu/drm/drm_mm.c +69 -3
@@ -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
--
2.26.2
_______________________________________________
dri-devel mailing list
[email protected]
https://lists.freedesktop.org/mailman/listinfo/dri-devel
PATCH 2/2 drm/mm: improve rb_hole_addr rbtree search
Userspace can still abuse alignment while allocating buffer object to slow down rb_hole_addr rbtree search. This patch improves search in fragmented rb_hole_addr rbtree by storing maximum subtree hole alignment and use that to skip a complete subtree if that subtree can not fit a (size + alignment) request.
With this patch applied, 50k bo allocs of size 4k and alignment 9k took ~0.24 sec on amdgpu, compared to 27 sec without it.
--- drivers/gpu/drm/drm_mm.c | 66 ++++++++++++++++++++++++++++++++++------ include/drm/drm_mm.h | 1 + 2 files changed, 58 insertions(+), 9 deletions(-)
drivers/gpu/drm/drm_mm.c +57 -9
@@ -212,8 +212,11 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, &drm_mm_interval_tree_augment); } +#define DRM_MM_ALIGN_SHIFT 6#define HOLE_SIZE (NODE ) ((NODE)->hole_size)#define HOLE_ADDR (NODE ) (__drm_mm_hole_node_start(NODE)) +#define HOLE_SIZE_ALIGN (NODE ) ((NODE->hole_size << DRM_MM_ALIGN_SHIFT) | \ + ffs(HOLE_ADDR(NODE)))static u64 rb_to_hole_size (struct rb_node *rb) {
@@ -241,6 +244,33 @@ static void insert_hole_size(struct rb_root_cached *root,rb_insert_color_cached (&node->rb_hole_size, root, first); } +static inline bool +augment_callbacks_compute_max_hole_align (struct drm_mm_node *node,bool exit) +{ +struct drm_mm_node *child; +u64 max =HOLE_SIZE_ALIGN (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_align > max) + max = child->subtree_max_hole_align; + } + +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_align > max) + max = child->subtree_max_hole_align; + } + +if (exit && node->subtree_max_hole_align == max) +return true; + + node->subtree_max_hole_align = max; +return false; +} +static inline bool augment_callbacks_compute_max_hole (struct drm_mm_node *node,bool exit) {
@@ -271,10 +301,14 @@ augment_callbacks_compute_max_hole(struct drm_mm_node *node, bool exit)static inline void augment_callbacks_propagate (struct rb_node *rb,struct rb_node *stop) { +bool compute_max_hole, compute_max_hole_align; +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)) + compute_max_hole =augment_callbacks_compute_max_hole (node, true); + compute_max_hole_align =augment_callbacks_compute_max_hole_align (node, true); +if (compute_max_hole && compute_max_hole_align)break ; rb =rb_parent (&node->rb_hole_addr);
@@ -290,6 +324,7 @@ augment_callbacks_copy(struct rb_node *rb_old, struct rb_node *rb_new) rb_hole_addr); new->subtree_max_hole = old->subtree_max_hole; + new->subtree_max_hole_align = old->subtree_max_hole_align; } static void
@@ -301,7 +336,9 @@ augment_callbacks_rotate(struct rb_node *rb_old, struct rb_node *rb_new) rb_hole_addr); new->subtree_max_hole = old->subtree_max_hole; + new->subtree_max_hole_align = old->subtree_max_hole_align;augment_callbacks_compute_max_hole (old, false); +augment_callbacks_compute_max_hole_align (old, false); }static const struct rb_augment_callbacks augment_callbacks = {
@@ -313,7 +350,9 @@ static const struct rb_augment_callbacks augment_callbacks = {static void insert_hole_addr (struct rb_root *root,struct drm_mm_node *node) {struct rb_node **link = &root->rb_node, *rb_parent =NULL ; -u64 start =HOLE_ADDR (node), subtree_max_hole = node->subtree_max_hole; +u64 start =HOLE_ADDR (node); +u64 subtree_max_hole = node->subtree_max_hole; +u64 subtree_max_hole_align = node->subtree_max_hole_align;struct drm_mm_node *parent;while (*link) {
@@ -322,6 +361,9 @@ static void insert_hole_addr(struct rb_root *root, struct drm_mm_node *node)if (parent->subtree_max_hole < subtree_max_hole) parent->subtree_max_hole = subtree_max_hole; +if (parent->subtree_max_hole_align < subtree_max_hole_align) + parent->subtree_max_hole_align = subtree_max_hole_align; +if (start <HOLE_ADDR (parent)) link = &parent->rb_hole_addr.rb_left;else
@@ -339,6 +381,7 @@ static void add_hole(struct drm_mm_node *node) node->hole_size =__drm_mm_hole_node_end (node) -__drm_mm_hole_node_start (node); node->subtree_max_hole = node->hole_size; + node->subtree_max_hole_align =HOLE_SIZE_ALIGN (node);DRM_MM_BUG_ON (!drm_mm_hole_follows (node));insert_hole_size (&mm->holes_size, node);
@@ -355,8 +398,10 @@ static void rm_hole(struct drm_mm_node *node)rb_erase_cached (&node->rb_hole_size, &node->mm->holes_size);rb_erase_augmented (&node->rb_hole_addr, &node->mm->holes_addr, &augment_callbacks); + node->hole_size =0 ; node->subtree_max_hole =0 ; + node->subtree_max_hole_align =0 ;DRM_MM_BUG_ON (drm_mm_hole_follows (node)); }
@@ -458,10 +503,11 @@ first_hole(struct drm_mm *mm,* else return parent of @entry */ static struct drm_mm_node * -next_hole_high_addr (struct drm_mm_node *entry,u64 size) +next_hole_high_addr (struct drm_mm_node *entry,u64 size,u64 alignment) {struct rb_node *rb_node, *left_rb_node, *parent_rb_node;struct drm_mm_node *left_node; +u64 req_align = (size + alignment) <<DRM_MM_ALIGN_SHIFT ;if (!entry)return NULL ;
@@ -473,6 +519,7 @@ next_hole_high_addr(struct drm_mm_node *entry, u64 size) left_node =rb_entry (left_rb_node, struct drm_mm_node, rb_hole_addr);if ((left_node->subtree_max_hole < size || + left_node->subtree_max_hole_align < req_align || entry->size == entry->subtree_max_hole) && parent_rb_node && parent_rb_node->rb_left != rb_node)return rb_hole_addr_to_node (parent_rb_node);
@@ -498,10 +545,11 @@ next_hole_high_addr(struct drm_mm_node *entry, u64 size)* else return parent of @entry */ static struct drm_mm_node * -next_hole_low_addr (struct drm_mm_node *entry,u64 size) +next_hole_low_addr (struct drm_mm_node *entry,u64 size,u64 alignment) {struct rb_node *rb_node, *right_rb_node, *parent_rb_node;struct drm_mm_node *right_node; +u64 req_align = (size + alignment) <<DRM_MM_ALIGN_SHIFT ;if (!entry)return NULL ;
@@ -513,6 +561,7 @@ next_hole_low_addr(struct drm_mm_node *entry, u64 size) right_node =rb_entry (right_rb_node, struct drm_mm_node, rb_hole_addr);if ((right_node->subtree_max_hole < size || + right_node->subtree_max_hole_align < req_align || entry->size == entry->subtree_max_hole) && parent_rb_node && parent_rb_node->rb_right != rb_node)return rb_hole_addr_to_node (parent_rb_node);
@@ -524,7 +573,7 @@ next_hole_low_addr(struct drm_mm_node *entry, u64 size)static struct drm_mm_node *next_hole (struct drm_mm *mm,struct drm_mm_node *node, -u64 size, +u64 size,u64 alignment,enum drm_mm_insert_mode mode) {switch (mode) {
@@ -533,10 +582,10 @@ next_hole(struct drm_mm *mm,return rb_hole_size_to_node (rb_prev (&node->rb_hole_size));case DRM_MM_INSERT_LOW : -return next_hole_low_addr (node, size); +return next_hole_low_addr (node, size, alignment);case DRM_MM_INSERT_HIGH : -return next_hole_high_addr (node, size); +return next_hole_high_addr (node, size, alignment);case DRM_MM_INSERT_EVICT : node =list_next_entry (node, hole_stack);
@@ -650,7 +699,7 @@ int drm_mm_insert_node_in_range(struct drm_mm * const mm, remainder_mask =is_power_of_2 (alignment) ? alignment -1 :0 ;for (hole =first_hole (mm, range_start, range_end, size, mode); hole; - hole = once ?NULL :next_hole (mm, hole, size, mode)) { + hole = once ?NULL :next_hole (mm, hole, size, alignment, mode)) {u64 hole_start =__drm_mm_hole_node_start (hole);u64 hole_end = hole_start + hole->hole_size;u64 adj_start, adj_end;
@@ -713,7 +762,6 @@ int drm_mm_insert_node_in_range(struct drm_mm * const mm,add_hole (hole);if (adj_start + size < hole_end)add_hole (node); -save_stack (node);return 0 ; }
include/drm/drm_mm.h +1 -0
@@ -169,6 +169,7 @@ struct drm_mm_node {u64 __subtree_last;u64 hole_size;u64 subtree_max_hole; +u64 subtree_max_hole_align;unsigned long flags;#define DRM_MM_NODE_ALLOCATED_BIT 0#define DRM_MM_NODE_SCANNED_BIT 1
Signature · 6 lines
2.26.2 _______________________________________________ dri-devel mailing list [email protected] https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH 2/2] drm/mm: improve rb_hole_addr rbtree search
Quoting Nirmoy Das (2020-05-19 09:44:36)
Quoted 191 lines
Userspace can still abuse alignment while allocating buffer object to slow down
rb_hole_addrrbtree search. This patch improves search in fragmentedrb_hole_addrrbtree by storing maximum subtree hole alignment and use that to skip a complete subtree if that subtree can not fit a (size + alignment) request.With this patch applied, 50k bo allocs of size 4k and alignment 9k took ~0.24 sec on amdgpu, compared to 27 sec without it.
Signed-off-by Nirmoy Das <[email protected]>--- drivers/gpu/drm/drm_mm.c | 66 ++++++++++++++++++++++++++++++++++------ include/drm/drm_mm.h | 1 + 2 files changed, 58 insertions(+), 9 deletions(-)drivers/gpu/drm/drm_mm.c +54
-5@@ -212,8 +212,11 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, &drm_mm_interval_tree_augment); } +#define DRM_MM_ALIGN_SHIFT 6#define HOLE_SIZE (NODE ) ((NODE)->hole_size)#define HOLE_ADDR (NODE ) (__drm_mm_hole_node_start(NODE)) +#define HOLE_SIZE_ALIGN (NODE ) ((NODE->hole_size << DRM_MM_ALIGN_SHIFT) | \ + ffs(HOLE_ADDR(NODE)))static u64 rb_to_hole_size (struct rb_node *rb) {@@ -241,6 +244,33 @@ static void insert_hole_size(struct rb_root_cached *root,rb_insert_color_cached (&node->rb_hole_size, root, first); } +static inline bool +augment_callbacks_compute_max_hole_align (struct drm_mm_node *node,bool exit) +{ +struct drm_mm_node *child; +u64 max =HOLE_SIZE_ALIGN (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_align > max) + max = child->subtree_max_hole_align; + } + +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_align > max) + max = child->subtree_max_hole_align; + } + +if (exit && node->subtree_max_hole_align == max) +return true; + + node->subtree_max_hole_align = max; +return false; +} +static inline bool augment_callbacks_compute_max_hole (struct drm_mm_node *node,bool exit) {@@ -271,10 +301,14 @@ augment_callbacks_compute_max_hole(struct drm_mm_node *node, bool exit)static inline void augment_callbacks_propagate (struct rb_node *rb,struct rb_node *stop) { +bool compute_max_hole, compute_max_hole_align; +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)) + compute_max_hole =augment_callbacks_compute_max_hole (node, true); + compute_max_hole_align =augment_callbacks_compute_max_hole_align (node, true); +if (compute_max_hole && compute_max_hole_align)break ; rb =rb_parent (&node->rb_hole_addr);@@ -290,6 +324,7 @@ augment_callbacks_copy(struct rb_node *rb_old, struct rb_node *rb_new) rb_hole_addr); new->subtree_max_hole = old->subtree_max_hole; + new->subtree_max_hole_align = old->subtree_max_hole_align; } static void@@ -301,7 +336,9 @@ augment_callbacks_rotate(struct rb_node *rb_old, struct rb_node *rb_new) rb_hole_addr); new->subtree_max_hole = old->subtree_max_hole; + new->subtree_max_hole_align = old->subtree_max_hole_align;augment_callbacks_compute_max_hole (old, false); +augment_callbacks_compute_max_hole_align (old, false); }static const struct rb_augment_callbacks augment_callbacks = {@@ -313,7 +350,9 @@ static const struct rb_augment_callbacks augment_callbacks = {static void insert_hole_addr (struct rb_root *root,struct drm_mm_node *node) {struct rb_node **link = &root->rb_node, *rb_parent =NULL ; -u64 start =HOLE_ADDR (node), subtree_max_hole = node->subtree_max_hole; +u64 start =HOLE_ADDR (node); +u64 subtree_max_hole = node->subtree_max_hole; +u64 subtree_max_hole_align = node->subtree_max_hole_align;struct drm_mm_node *parent;while (*link) {@@ -322,6 +361,9 @@ static void insert_hole_addr(struct rb_root *root, struct drm_mm_node *node)if (parent->subtree_max_hole < subtree_max_hole) parent->subtree_max_hole = subtree_max_hole; +if (parent->subtree_max_hole_align < subtree_max_hole_align) + parent->subtree_max_hole_align = subtree_max_hole_align; +if (start <HOLE_ADDR (parent)) link = &parent->rb_hole_addr.rb_left;else @@ -339,6 +381,7 @@ static void add_hole(struct drm_mm_node *node) node->hole_size =__drm_mm_hole_node_end (node) -__drm_mm_hole_node_start (node); node->subtree_max_hole = node->hole_size; + node->subtree_max_hole_align =HOLE_SIZE_ALIGN (node);DRM_MM_BUG_ON (!drm_mm_hole_follows (node));insert_hole_size (&mm->holes_size, node);@@ -355,8 +398,10 @@ static void rm_hole(struct drm_mm_node *node)rb_erase_cached (&node->rb_hole_size, &node->mm->holes_size);rb_erase_augmented (&node->rb_hole_addr, &node->mm->holes_addr, &augment_callbacks); + node->hole_size =0 ; node->subtree_max_hole =0 ; + node->subtree_max_hole_align =0 ;DRM_MM_BUG_ON (drm_mm_hole_follows (node)); }@@ -458,10 +503,11 @@ first_hole(struct drm_mm *mm,* else return parent of @entry */ static struct drm_mm_node * -next_hole_high_addr (struct drm_mm_node *entry,u64 size) +next_hole_high_addr (struct drm_mm_node *entry,u64 size,u64 alignment) {struct rb_node *rb_node, *left_rb_node, *parent_rb_node;struct drm_mm_node *left_node; +u64 req_align = (size + alignment) <<DRM_MM_ALIGN_SHIFT ;if (!entry)return NULL ;@@ -473,6 +519,7 @@ next_hole_high_addr(struct drm_mm_node *entry, u64 size) left_node =rb_entry (left_rb_node, struct drm_mm_node, rb_hole_addr);if ((left_node->subtree_max_hole < size || + left_node->subtree_max_hole_align < req_align || entry->size == entry->subtree_max_hole) && parent_rb_node && parent_rb_node->rb_left != rb_node)return rb_hole_addr_to_node (parent_rb_node);@@ -498,10 +545,11 @@ next_hole_high_addr(struct drm_mm_node *entry, u64 size)* else return parent of @entry */ static struct drm_mm_node * -next_hole_low_addr (struct drm_mm_node *entry,u64 size) +next_hole_low_addr (struct drm_mm_node *entry,u64 size,u64 alignment) {struct rb_node *rb_node, *right_rb_node, *parent_rb_node;struct drm_mm_node *right_node; +u64 req_align = (size + alignment) <<DRM_MM_ALIGN_SHIFT ;if (!entry)return NULL ;@@ -513,6 +561,7 @@ next_hole_low_addr(struct drm_mm_node *entry, u64 size) right_node =rb_entry (right_rb_node, struct drm_mm_node, rb_hole_addr);if ((right_node->subtree_max_hole < size || + right_node->subtree_max_hole_align < req_align || entry->size == entry->subtree_max_hole) && parent_rb_node && parent_rb_node->rb_right != rb_node)return rb_hole_addr_to_node (parent_rb_node);@@ -524,7 +573,7 @@ next_hole_low_addr(struct drm_mm_node *entry, u64 size)static struct drm_mm_node *next_hole (struct drm_mm *mm,struct drm_mm_node *node, -u64 size, +u64 size,u64 alignment,enum drm_mm_insert_mode mode) {switch (mode) {
drivers/gpu/drm/drm_mm.c next_hole(struct drm_mm *mm, · line 588
Quoted 9 lines
drivers/gpu/drm/drm_mm.c +2
-2@@ -533,10 +582,10 @@ next_hole(struct drm_mm *mm,return rb_hole_size_to_node (rb_prev (&node->rb_hole_size));case DRM_MM_INSERT_LOW : -return next_hole_low_addr (node, size); +return next_hole_low_addr (node, size, alignment);case DRM_MM_INSERT_HIGH : -return next_hole_high_addr (node, size); +return next_hole_high_addr (node, size, alignment);
Our test case is of course hitting DRM_MM_INSERT_BEST so shows no benefit. Though I do have an open-coded search to avoid the O(N^2) behaviour that just ascends the size rbtree until it is happy (rather than looking at all nodes within a size).
Searching top-down/bottom-up does have its merits though, so if with this rbtree it's always quicker than best...
-Chris
_______________________________________________
dri-devel mailing list
[email protected]
https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH 2/2] drm/mm: improve rb_hole_addr rbtree search
In reply to Nirmoy DasQuoting Nirmoy Das (2020-05-19 09:44:36)
drivers/gpu/drm/drm_mm.c static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, · line 219
Quoted 5 lines
drivers/gpu/drm/drm_mm.c +3
-0+#define DRM_MM_ALIGN_SHIFT 6#define HOLE_SIZE (NODE ) ((NODE)->hole_size)#define HOLE_ADDR (NODE ) (__drm_mm_hole_node_start(NODE)) +#define HOLE_SIZE_ALIGN (NODE ) ((NODE->hole_size << DRM_MM_ALIGN_SHIFT) | \ + ffs(HOLE_ADDR(NODE)))
Fwiw, max hole size of 58b, we would need to stop storing byte extents...
Quoted 11 lines
static struct
drm_mm_node*drivers/gpu/drm/drm_mm.c +2
-1-next_hole_low_addr(struct drm_mm_node *entry, u64 size) +next_hole_low_addr(struct drm_mm_node *entry, u64 size, u64 alignment) { struct rb_node *rb_node, *right_rb_node, *parent_rb_node;struct drm_mm_node *right_node; +u64 req_align = (size + alignment) <<DRM_MM_ALIGN_SHIFT ;if (!entry)return NULL ;
drivers/gpu/drm/drm_mm.c next_hole_low_addr(struct drm_mm_node *entry, u64 size) · line 564
Quoted 4 lines
drivers/gpu/drm/drm_mm.c +1
-0@@ -513,6 +561,7 @@ next_hole_low_addr(struct drm_mm_node *entry, u64 size) right_node =rb_entry (right_rb_node, struct drm_mm_node, rb_hole_addr); if ((right_node->subtree_max_hole < size || + right_node->subtree_max_hole_align < req_align ||
What was the point in storing the packed alignment if we are just searching for a hole big enough for (size + alignment)? -Chris
_______________________________________________
dri-devel mailing list
[email protected]
https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH 2/2] drm/mm: improve rb_hole_addr rbtree search
Hi Chris,
Quoted 8 lines · Chris Wilson
Quoting Nirmoy Das (2020-05-19 09:44:36)
drivers/gpu/drm/drm_mm.c static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, · line 219
Quoted 5 lines
drivers/gpu/drm/drm_mm.c +3
-0+#define DRM_MM_ALIGN_SHIFT 6#define HOLE_SIZE (NODE ) ((NODE)->hole_size)#define HOLE_ADDR (NODE ) (__drm_mm_hole_node_start(NODE)) +#define HOLE_SIZE_ALIGN (NODE ) ((NODE->hole_size << DRM_MM_ALIGN_SHIFT) | \ + ffs(HOLE_ADDR(NODE)))Fwiw, max hole size of 58b, we would need to stop storing byte extents...
Can you please explain 2nd part of this statement.
Quoted 8 lines
Quoted 8 lines
static struct
drm_mm_node*drivers/gpu/drm/drm_mm.c +2
-1-next_hole_low_addr(struct drm_mm_node *entry, u64 size) +next_hole_low_addr(struct drm_mm_node *entry, u64 size, u64 alignment) { struct rb_node *rb_node, *right_rb_node, *parent_rb_node;struct drm_mm_node *right_node; +u64 req_align = (size + alignment) <<DRM_MM_ALIGN_SHIFT ;
Quoted 9 lines
drivers/gpu/drm/drm_mm.c next_hole_low_addr(struct drm_mm_node *entry, u64 size) · line 564
Quoted 7 lines
if (!entry) return NULL;drivers/gpu/drm/drm_mm.c +1
-0@@ -513,6 +561,7 @@ next_hole_low_addr(struct drm_mm_node *entry, u64 size) right_node =rb_entry (right_rb_node, struct drm_mm_node, rb_hole_addr); if ((right_node->subtree_max_hole < size || + right_node->subtree_max_hole_align < req_align ||What was the point in storing the packed alignment if we are just searching for a hole big enough for (size + alignment)?
Yes, I realized this is not correct :/
Still thinking about a better solution to capture alignment into subtree elimination.
Regards,
Nirmoy
Quoted 5 lines
-Chris
_______________________________________________
dri-devel mailing list
[email protected]
https://nam11.safelinks.protection.outlook.com/?url=https%3A%2F%2Flists.freedesktop.org%2Fmailman%2Flistinfo%2Fdri-devel&data=02%7C01%7Cnirmoy.das%40amd.com%7C1b1ab9c2ca03412daa2108d7fc47d26e%7C3dd8961fe4884e608e11a82d994e183d%7C0%7C0%7C637255257724473951&sdata=gDRvdhwLV1M%2BKLCgpENik52gAB3O0ik1n%2B%2FaZxLgr%2Fk%3D&reserved=0
_______________________________________________
dri-devel mailing list
[email protected]
https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH 2/2] drm/mm: improve rb_hole_addr rbtree search
Quoting Nirmoy (2020-05-20 17:28:04)
Quoted 13 lines
Hi Chris,
Quoted 8 lines · Chris Wilson
Quoting Nirmoy Das (2020-05-19 09:44:36)
drivers/gpu/drm/drm_mm.c static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, · line 219
Quoted 5 lines
drivers/gpu/drm/drm_mm.c +3
-0+#define DRM_MM_ALIGN_SHIFT 6#define HOLE_SIZE (NODE ) ((NODE)->hole_size)#define HOLE_ADDR (NODE ) (__drm_mm_hole_node_start(NODE)) +#define HOLE_SIZE_ALIGN (NODE ) ((NODE->hole_size << DRM_MM_ALIGN_SHIFT) | \ + ffs(HOLE_ADDR(NODE)))Fwiw, max hole size of 58b, we would need to stop storing byte extents...
Quoted 1 line
Can you please explain 2nd part of this statement.
Currently we [i915] use drm_mm with byte-addressing, so 58b is a tad too close to the amount we actually need to track. If we used page tracking instead of bytes, we regain 12b to play around with. It makes no difference to the code at the moment (e.g. we still could not fit within u32) so there has been no pressure to rewrite the extents handling. But given sufficient reason, we could.
-Chris
_______________________________________________
dri-devel mailing list
[email protected]
https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH 2/2] drm/mm: improve rb_hole_addr rbtree search
Quoted 13 lines · Chris Wilson
Quoting Nirmoy (2020-05-20 17:28:04)
Quoted 12 lines
Hi Chris,
Quoted 8 lines · Chris Wilson
Quoting Nirmoy Das (2020-05-19 09:44:36)
drivers/gpu/drm/drm_mm.c static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, · line 219
Quoted 5 lines
drivers/gpu/drm/drm_mm.c +3
-0+#define DRM_MM_ALIGN_SHIFT 6#define HOLE_SIZE (NODE ) ((NODE)->hole_size)#define HOLE_ADDR (NODE ) (__drm_mm_hole_node_start(NODE)) +#define HOLE_SIZE_ALIGN (NODE ) ((NODE->hole_size << DRM_MM_ALIGN_SHIFT) | \ + ffs(HOLE_ADDR(NODE)))Fwiw, max hole size of 58b, we would need to stop storing byte extents...
Quoted 8 lines
Quoted 1 line
Can you please explain 2nd part of this statement.
Currently we [i915] use
drm_mmwith byte-addressing, so 58b is a tad too close to the amount we actually need to track. If we used page tracking instead of bytes, we regain 12b to play around with. It makes no difference to the code at the moment (e.g. we still could not fit within u32) so there has been no pressure to rewrite the extents handling. But given sufficient reason, we could.
-Chris
Thanks for the detailed explanation.
Nirmoy
_______________________________________________
dri-devel mailing list
[email protected]
https://lists.freedesktop.org/mailman/listinfo/dri-devel
Quoting Nirmoy Das (2020-05-19 09:44:35)
Quoted 18 lines
Expand
RB_DECLARE_CALLBACKS_MAXso that it is possible to store extra value(max hole alignment) in therb_hole_addraugmented rbtree.Signed-off-by Nirmoy Das <[email protected]>--- drivers/gpu/drm/drm_mm.c | 72 ++++++++++++++++++++++++++++++++++++++-- 1 file changed, 69 insertions(+), 3 deletions(-)drivers/gpu/drm/drm_mm.c +0
-2@@ -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,
drivers/gpu/drm/drm_mm.c static void insert_hole_size(struct rb_root_cached *root, · line 252
Quoted 10 lines
drivers/gpu/drm/drm_mm.c +9
-1- 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);
We repeat rb_entry a lot. There's rb_hole_addr_to_node() which is slightly more concise, but uses the _safe variant. Though you could
child = rb_hole_addr_to_node(node->rb_hole_addr.rb_left); if (child && child->subtree_max_hole > max) max = child->subtree_max_hole;
which the compiler should generate equivalent code for.
But do have a think of a suitable name for a helper to tidy up all the rb_entries that are overflowing 80cols.
Quoted 14 lines
drivers/gpu/drm/drm_mm.c +14
-0+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; +
drivers/gpu/drm/drm_mm.c static void insert_hole_size(struct rb_root_cached *root, · line 276
Quoted 10 lines
drivers/gpu/drm/drm_mm.c +10
-0+ 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);
Coding style / checkpatch will insist on a newline here after the vars.
Quoted 25 lines
drivers/gpu/drm/drm_mm.c +25
-0+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);
drivers/gpu/drm/drm_mm.c static void insert_hole_size(struct rb_root_cached *root, · line 311
Quoted 10 lines
drivers/gpu/drm/drm_mm.c +10
-0+ + 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 +};
Faithful expansion of the macros,
-Chris
_______________________________________________
dri-devel mailing list
[email protected]
https://lists.freedesktop.org/mailman/listinfo/dri-devel
Am 19.05.20 um 10:44 schrieb Nirmoy Das:
Quoted 2 lines
Expand
RB_DECLARE_CALLBACKS_MAXso that it is possible to store extra value(max hole alignment) in therb_hole_addraugmented rbtree.
This looks to complicated to me, why not just extend the HOLE_SIZE definition to come up with a combined size/alignment value?
Christian.
Quoted 97 lines
Signed-off-by Nirmoy Das <[email protected]>--- drivers/gpu/drm/drm_mm.c | 72 ++++++++++++++++++++++++++++++++++++++-- 1 file changed, 69 insertions(+), 3 deletions(-)drivers/gpu/drm/drm_mm.c +69
-4@@ -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 --
Quoted 2 lines
2.26.2
_______________________________________________
dri-devel mailing list
[email protected]
https://lists.freedesktop.org/mailman/listinfo/dri-devel