[PATCH] drm/mm: Fix search for smallest hole satisfying constraints

[PATCH] drm/mm: Fix search for smallest hole satisfying constraints

[Michel Dänzer]

From: Michel Dänzer <michel.daenzer@amd.com>

entry->size is the size of the node, not the size of the hole after it.
So the code would actually find the hole which can satisfy the
constraints and which is preceded by the smallest node, not the smallest
hole satisfying the constraints.

Reported-by: "Huang, FrankR" <FrankR.Huang@amd.com>
Signed-off-by: Michel Dänzer <michel.daenzer@amd.com>
---
 drivers/gpu/drm/drm_mm.c | 33 +++++++++++++++++----------------
 1 file changed, 17 insertions(+), 16 deletions(-)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c
index af93cc5..5d921e5 100644
--- a/drivers/gpu/drm/drm_mm.c
+++ b/drivers/gpu/drm/drm_mm.c
@@ -306,8 +306,8 @@ static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm,
 {
 	struct drm_mm_node *entry;
 	struct drm_mm_node *best;
-	unsigned long adj_start;
-	unsigned long adj_end;
+	unsigned long hole_start;
+	unsigned long hole_end;
 	unsigned long best_size;
 
 	BUG_ON(mm->scanned_blocks);
@@ -315,7 +315,10 @@ static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm,
 	best = NULL;
 	best_size = ~0UL;
 
-	drm_mm_for_each_hole(entry, mm, adj_start, adj_end) {
+	drm_mm_for_each_hole(entry, mm, hole_start, hole_end) {
+		unsigned long adj_start = hole_start;
+		unsigned long adj_end = hole_end;
+
 		if (mm->color_adjust) {
 			mm->color_adjust(entry, color, &adj_start, &adj_end);
 			if (adj_end <= adj_start)
@@ -328,9 +331,9 @@ static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm,
 		if (!(flags & DRM_MM_SEARCH_BEST))
 			return entry;
 
-		if (entry->size < best_size) {
+		if ((hole_end - hole_start) < best_size) {
 			best = entry;
-			best_size = entry->size;
+			best_size = hole_end - hole_start;
 		}
 	}
 
@@ -341,14 +344,14 @@ static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_
 							unsigned long size,
 							unsigned alignment,
 							unsigned long color,
-							unsigned long start,
-							unsigned long end,
+							unsigned long range_start,
+							unsigned long range_end,
 							enum drm_mm_search_flags flags)
 {
 	struct drm_mm_node *entry;
 	struct drm_mm_node *best;
-	unsigned long adj_start;
-	unsigned long adj_end;
+	unsigned long hole_start;
+	unsigned long hole_end;
 	unsigned long best_size;
 
 	BUG_ON(mm->scanned_blocks);
@@ -356,11 +359,9 @@ static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_
 	best = NULL;
 	best_size = ~0UL;
 
-	drm_mm_for_each_hole(entry, mm, adj_start, adj_end) {
-		if (adj_start < start)
-			adj_start = start;
-		if (adj_end > end)
-			adj_end = end;
+	drm_mm_for_each_hole(entry, mm, hole_start, hole_end) {
+		unsigned long adj_start = max(hole_start, range_start);
+		unsigned long adj_end = min(hole_end, range_end);
 
 		if (mm->color_adjust) {
 			mm->color_adjust(entry, color, &adj_start, &adj_end);
@@ -374,9 +375,9 @@ static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_
 		if (!(flags & DRM_MM_SEARCH_BEST))
 			return entry;
 
-		if (entry->size < best_size) {
+		if ((hole_end - hole_start) < best_size) {
 			best = entry;
-			best_size = entry->size;
+			best_size = hole_end - hole_start;
 		}
 	}
 
-- 
1.9.0


_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/dri-devel

Re: [PATCH] drm/mm: Fix search for smallest hole satisfying constraints

[Daniel Vetter]

On Tue, Mar 18, 2014 at 09:58:14AM +0900, Michel Dänzer wrote:
> From: Michel Dänzer <michel.daenzer@amd.com>
> 
> entry->size is the size of the node, not the size of the hole after it.
> So the code would actually find the hole which can satisfy the
> constraints and which is preceded by the smallest node, not the smallest
> hole satisfying the constraints.
> 
> Reported-by: "Huang, FrankR" <FrankR.Huang@amd.com>
> Signed-off-by: Michel Dänzer <michel.daenzer@amd.com>

But drm-next just gained my kerneldoc patch for drm_mm, so can you please
respin your patch and update the docs too? While at it ... could you
perhaps smash a bit of kerneldoc on top of enum drm_mm_search_flags, I
seem to have missed it. With that this is

Reviewed-by: Daniel Vetter <daniel.vetter@ffwll.ch>

Thanks, Daniel

> ---
>  drivers/gpu/drm/drm_mm.c | 33 +++++++++++++++++----------------
>  1 file changed, 17 insertions(+), 16 deletions(-)
> 
> diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c
> index af93cc5..5d921e5 100644
> --- a/drivers/gpu/drm/drm_mm.c
> +++ b/drivers/gpu/drm/drm_mm.c
> @@ -306,8 +306,8 @@ static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm,
>  {
>  	struct drm_mm_node *entry;
>  	struct drm_mm_node *best;
> -	unsigned long adj_start;
> -	unsigned long adj_end;
> +	unsigned long hole_start;
> +	unsigned long hole_end;
>  	unsigned long best_size;
>  
>  	BUG_ON(mm->scanned_blocks);
> @@ -315,7 +315,10 @@ static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm,
>  	best = NULL;
>  	best_size = ~0UL;
>  
> -	drm_mm_for_each_hole(entry, mm, adj_start, adj_end) {
> +	drm_mm_for_each_hole(entry, mm, hole_start, hole_end) {
> +		unsigned long adj_start = hole_start;
> +		unsigned long adj_end = hole_end;
> +
>  		if (mm->color_adjust) {
>  			mm->color_adjust(entry, color, &adj_start, &adj_end);
>  			if (adj_end <= adj_start)
> @@ -328,9 +331,9 @@ static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm,
>  		if (!(flags & DRM_MM_SEARCH_BEST))
>  			return entry;
>  
> -		if (entry->size < best_size) {
> +		if ((hole_end - hole_start) < best_size) {
>  			best = entry;
> -			best_size = entry->size;
> +			best_size = hole_end - hole_start;
>  		}
>  	}
>  
> @@ -341,14 +344,14 @@ static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_
>  							unsigned long size,
>  							unsigned alignment,
>  							unsigned long color,
> -							unsigned long start,
> -							unsigned long end,
> +							unsigned long range_start,
> +							unsigned long range_end,
>  							enum drm_mm_search_flags flags)
>  {
>  	struct drm_mm_node *entry;
>  	struct drm_mm_node *best;
> -	unsigned long adj_start;
> -	unsigned long adj_end;
> +	unsigned long hole_start;
> +	unsigned long hole_end;
>  	unsigned long best_size;
>  
>  	BUG_ON(mm->scanned_blocks);
> @@ -356,11 +359,9 @@ static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_
>  	best = NULL;
>  	best_size = ~0UL;
>  
> -	drm_mm_for_each_hole(entry, mm, adj_start, adj_end) {
> -		if (adj_start < start)
> -			adj_start = start;
> -		if (adj_end > end)
> -			adj_end = end;
> +	drm_mm_for_each_hole(entry, mm, hole_start, hole_end) {
> +		unsigned long adj_start = max(hole_start, range_start);
> +		unsigned long adj_end = min(hole_end, range_end);
>  
>  		if (mm->color_adjust) {
>  			mm->color_adjust(entry, color, &adj_start, &adj_end);
> @@ -374,9 +375,9 @@ static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_
>  		if (!(flags & DRM_MM_SEARCH_BEST))
>  			return entry;
>  
> -		if (entry->size < best_size) {
> +		if ((hole_end - hole_start) < best_size) {
>  			best = entry;
> -			best_size = entry->size;
> +			best_size = hole_end - hole_start;
>  		}
>  	}
>  
> -- 
> 1.9.0
> 
> 
> _______________________________________________
> dri-devel mailing list
> dri-devel@lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/dri-devel

-- 
Daniel Vetter
Software Engineer, Intel Corporation
+41 (0) 79 365 57 48 - http://blog.ffwll.ch

Re: [PATCH] drm/mm: Fix search for smallest hole satisfying constraints

[Michel Dänzer]

On Die, 2014-03-18 at 11:01 +0100, Daniel Vetter wrote:
> On Tue, Mar 18, 2014 at 09:58:14AM +0900, Michel Dänzer wrote:
> > From: Michel Dänzer <michel.daenzer@amd.com>
> > 
> > entry->size is the size of the node, not the size of the hole after it.
> > So the code would actually find the hole which can satisfy the
> > constraints and which is preceded by the smallest node, not the smallest
> > hole satisfying the constraints.
> > 
> > Reported-by: "Huang, FrankR" <FrankR.Huang@amd.com>
> > Signed-off-by: Michel Dänzer <michel.daenzer@amd.com>
> 
> But drm-next just gained my kerneldoc patch for drm_mm, so can you please
> respin your patch and update the docs too?

What kind of update are you thinking of?


> While at it ... could you perhaps smash a bit of kerneldoc on top of
> enum drm_mm_search_flags, I seem to have missed it. With that this is
> 
> Reviewed-by: Daniel Vetter <daniel.vetter@ffwll.ch>

Thanks, but I'm afraid I'll have to pass on that. I'm just submitting a
fix for a problem Frank stumbled upon. I don't have the time right now,
nor the particular inclination to clean up the surrounding code.

Meanwhile, I've submitted a less invasive v2 fix.


BTW, do you think the fix would interact properly with coloring?


-- 
Earthling Michel Dänzer            |                  http://www.amd.com
Libre software enthusiast          |                Mesa and X developer

_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/dri-devel

Re: [PATCH] drm/mm: Fix search for smallest hole satisfying constraints

[Daniel Vetter]

On Wed, Mar 19, 2014 at 05:42:27PM +0900, Michel Dänzer wrote:
> On Die, 2014-03-18 at 11:01 +0100, Daniel Vetter wrote:
> > On Tue, Mar 18, 2014 at 09:58:14AM +0900, Michel Dänzer wrote:
> > > From: Michel Dänzer <michel.daenzer@amd.com>
> > > 
> > > entry->size is the size of the node, not the size of the hole after it.
> > > So the code would actually find the hole which can satisfy the
> > > constraints and which is preceded by the smallest node, not the smallest
> > > hole satisfying the constraints.
> > > 
> > > Reported-by: "Huang, FrankR" <FrankR.Huang@amd.com>
> > > Signed-off-by: Michel Dänzer <michel.daenzer@amd.com>
> > 
> > But drm-next just gained my kerneldoc patch for drm_mm, so can you please
> > respin your patch and update the docs too?
> 
> What kind of update are you thinking of?

you've changed the function parameters, which breaks the kerneldoc. v2 is
ok in that regard.

> > While at it ... could you perhaps smash a bit of kerneldoc on top of
> > enum drm_mm_search_flags, I seem to have missed it. With that this is
> > 
> > Reviewed-by: Daniel Vetter <daniel.vetter@ffwll.ch>
> 
> Thanks, but I'm afraid I'll have to pass on that. I'm just submitting a
> fix for a problem Frank stumbled upon. I don't have the time right now,
> nor the particular inclination to clean up the surrounding code.

I've made a note to add the missing kerneldoc, still some patches left
over.

> Meanwhile, I've submitted a less invasive v2 fix.

Reviewed-by: Daniel Vetter <daniel.vetter@ffwll.ch> on that one.

> BTW, do you think the fix would interact properly with coloring?

Coloring only adjusts start/end so won't affect the size of the hole. If
you really see benefits from best_match then I guess you could look into
pessimising holes which need to be split, presuming radeon has a pile of
alignment or otherwise constrained buffers.

Cheers, Daniel
-- 
Daniel Vetter
Software Engineer, Intel Corporation
+41 (0) 79 365 57 48 - http://blog.ffwll.ch

Re: [PATCH] drm/mm: Fix search for smallest hole satisfying constraints

[Michel Dänzer]

On Mit, 2014-03-19 at 11:38 +0100, Daniel Vetter wrote:
> On Wed, Mar 19, 2014 at 05:42:27PM +0900, Michel Dänzer wrote:
> > On Die, 2014-03-18 at 11:01 +0100, Daniel Vetter wrote:
> > > On Tue, Mar 18, 2014 at 09:58:14AM +0900, Michel Dänzer wrote:
> > > > From: Michel Dänzer <michel.daenzer@amd.com>
> > > > 
> > > > entry->size is the size of the node, not the size of the hole after it.
> > > > So the code would actually find the hole which can satisfy the
> > > > constraints and which is preceded by the smallest node, not the smallest
> > > > hole satisfying the constraints.
> > > > 
> > > > Reported-by: "Huang, FrankR" <FrankR.Huang@amd.com>
> > > > Signed-off-by: Michel Dänzer <michel.daenzer@amd.com>
> > > 
> > > But drm-next just gained my kerneldoc patch for drm_mm, so can you please
> > > respin your patch and update the docs too?
> > 
> > What kind of update are you thinking of?
> 
> you've changed the function parameters, which breaks the kerneldoc. v2 is
> ok in that regard.

Ah, I see.


> > Meanwhile, I've submitted a less invasive v2 fix.
> 
> Reviewed-by: Daniel Vetter <daniel.vetter@ffwll.ch> on that one.

Merci! :)


> > BTW, do you think the fix would interact properly with coloring?
> 
> Coloring only adjusts start/end so won't affect the size of the hole. If
> you really see benefits from best_match

I've been wondering about the potential effects of this fix... I hope it
won't cause regressions.

> then I guess you could look into pessimising holes which need to be
> split, presuming radeon has a pile of alignment or otherwise
> constrained buffers.

E.g. textures with 2D tiling can require pretty large alignment, so that
might indeed be interesting.


-- 
Earthling Michel Dänzer            |                  http://www.amd.com
Libre software enthusiast          |                Mesa and X developer

_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/dri-devel

[PATCH v2] drm/mm: Fix search for smallest hole satisfying constraints

[Michel Dänzer]

From: Michel Dänzer <michel.daenzer@amd.com>

entry->size is the size of the node, not the size of the hole after it.
So the code would actually find the hole which can satisfy the
constraints and which is preceded by the smallest node, not the smallest
hole satisfying the constraints.

Reported-by: "Huang, FrankR" <FrankR.Huang@amd.com>
Signed-off-by: Michel Dänzer <michel.daenzer@amd.com>
---

v2: Less invasive fix.

 drivers/gpu/drm/drm_mm.c | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c
index a2d45b74..8b16a10 100644
--- a/drivers/gpu/drm/drm_mm.c
+++ b/drivers/gpu/drm/drm_mm.c
@@ -392,6 +392,8 @@ static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm,
 	best_size = ~0UL;
 
 	drm_mm_for_each_hole(entry, mm, adj_start, adj_end) {
+		unsigned long hole_size = adj_end - adj_start;
+
 		if (mm->color_adjust) {
 			mm->color_adjust(entry, color, &adj_start, &adj_end);
 			if (adj_end <= adj_start)
@@ -404,9 +406,9 @@ static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm,
 		if (!(flags & DRM_MM_SEARCH_BEST))
 			return entry;
 
-		if (entry->size < best_size) {
+		if (hole_size < best_size) {
 			best = entry;
-			best_size = entry->size;
+			best_size = hole_size;
 		}
 	}
 
@@ -433,6 +435,8 @@ static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_
 	best_size = ~0UL;
 
 	drm_mm_for_each_hole(entry, mm, adj_start, adj_end) {
+		unsigned long hole_size = adj_end - adj_start;
+
 		if (adj_start < start)
 			adj_start = start;
 		if (adj_end > end)
@@ -450,9 +454,9 @@ static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_
 		if (!(flags & DRM_MM_SEARCH_BEST))
 			return entry;
 
-		if (entry->size < best_size) {
+		if (hole_size < best_size) {
 			best = entry;
-			best_size = entry->size;
+			best_size = hole_size;
 		}
 	}
 
-- 
1.9.0

_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/dri-devel