[PATCH v7 3/3] drm/buddy: Add defragmentation support

[Arunpravin Paneer Selvam]

Add a function to support defragmentation.

v1:
  - Defragment the memory beginning from min_order
    till the required memory space is available.

v2(Matthew):
  - add amdgpu user for defragmentation
  - add a warning if the two blocks are incompatible on
    defragmentation
  - call full defragmentation in the fini() function
  - place a condition to test if min_order is equal to 0
  - replace the list with safe_reverse() variant as we might
    remove the block from the list.

Signed-off-by: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam at amd.com>
Suggested-by: Matthew Auld <matthew.auld at intel.com>
---
 drivers/gpu/drm/amd/amdgpu/amdgpu_vram_mgr.c | 17 +++-
 drivers/gpu/drm/drm_buddy.c                  | 93 +++++++++++++++++---
 include/drm/drm_buddy.h                      |  3 +
 3 files changed, 97 insertions(+), 16 deletions(-)

diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_vram_mgr.c b/drivers/gpu/drm/amd/amdgpu/amdgpu_vram_mgr.c
index e494f5bf136a..cff8a526c622 100644
--- a/drivers/gpu/drm/amd/amdgpu/amdgpu_vram_mgr.c
+++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_vram_mgr.c
@@ -533,8 +533,21 @@ static int amdgpu_vram_mgr_new(struct ttm_resource_manager *man,
 					   min_block_size,
 					   &vres->blocks,
 					   vres->flags);
-		if (unlikely(r))
-			goto error_free_blocks;
+		if (unlikely(r)) {
+			if (r == -ENOSPC) {
+				drm_buddy_defrag(mm, min_block_size);
+				r = drm_buddy_alloc_blocks(mm, fpfn,
+							   lpfn,
+							   size,
+							   min_block_size,
+							   &vres->blocks,
+							   vres->flags);
+				if (unlikely(r))
+					goto error_free_blocks;
+			} else {
+				goto error_free_blocks;
+			}
+		}
 
 		if (size > remaining_size)
 			remaining_size = 0;
diff --git a/drivers/gpu/drm/drm_buddy.c b/drivers/gpu/drm/drm_buddy.c
index 18e004fa39d3..56bd1560fbcd 100644
--- a/drivers/gpu/drm/drm_buddy.c
+++ b/drivers/gpu/drm/drm_buddy.c
@@ -203,6 +203,8 @@ void drm_buddy_fini(struct drm_buddy *mm)
 		drm_block_free(mm, mm->roots[i]);
 	}
 
+	drm_buddy_defrag(mm, mm->chunk_size << mm->max_order);
+
 	WARN_ON(mm->avail != mm->size);
 
 	kfree(mm->roots);
@@ -276,25 +278,39 @@ drm_get_buddy(struct drm_buddy_block *block)
 }
 EXPORT_SYMBOL(drm_get_buddy);
 
-static void __drm_buddy_free(struct drm_buddy *mm,
-			     struct drm_buddy_block *block)
+static unsigned int __drm_buddy_free(struct drm_buddy *mm,
+				     struct drm_buddy_block *block,
+				     bool defrag)
 {
+	unsigned int order, block_order;
 	struct drm_buddy_block *parent;
 
+	block_order = drm_buddy_block_order(block);
+
 	while ((parent = block->parent)) {
-		struct drm_buddy_block *buddy;
+		struct drm_buddy_block *buddy = NULL;
 
 		buddy = __get_buddy(block);
 
 		if (!drm_buddy_block_is_free(buddy))
 			break;
 
-		if (drm_buddy_block_is_clear(block) !=
-		    drm_buddy_block_is_clear(buddy))
-			break;
+		if (!defrag) {
+			/*
+			 * Check the block and its buddy clear state and exit
+			 * the loop if they both have the dissimilar state.
+			 */
+			if (drm_buddy_block_is_clear(block) !=
+			    drm_buddy_block_is_clear(buddy))
+				break;
 
-		if (drm_buddy_block_is_clear(block))
-			mark_cleared(parent);
+			if (drm_buddy_block_is_clear(block))
+				mark_cleared(parent);
+		}
+
+		WARN_ON(defrag &&
+			(drm_buddy_block_is_clear(block) ==
+			 drm_buddy_block_is_clear(buddy)));
 
 		list_del(&buddy->link);
 
@@ -304,8 +320,57 @@ static void __drm_buddy_free(struct drm_buddy *mm,
 		block = parent;
 	}
 
-	mark_free(mm, block);
+	order = drm_buddy_block_order(block);
+	if (block_order != order)
+		mark_free(mm, block);
+
+	return order;
+}
+
+/**
+ * drm_buddy_defrag - Defragmentation routine
+ *
+ * @mm: DRM buddy manager
+ * @min_block_size: minimum size in bytes to begin
+ * the defragmentation process
+ *
+ * Driver calls the defragmentation function when the
+ * requested memory allocation returns -ENOSPC.
+ */
+void drm_buddy_defrag(struct drm_buddy *mm,
+		      unsigned int min_block_size)
+{
+	struct drm_buddy_block *block, *tmp;
+	unsigned int order, min_order;
+	struct list_head *list;
+	unsigned long pages;
+	int i;
+
+	pages = min_block_size >> ilog2(mm->chunk_size);
+	min_order = fls(pages) - 1;
+
+	if (!min_order)
+		return;
+
+	if (min_order > mm->max_order)
+		return;
+
+	for (i = min_order - 1; i >= 0; i--) {
+		list = &mm->free_list[i];
+		if (list_empty(list))
+			continue;
+
+		list_for_each_entry_safe_reverse(block, tmp, list, link) {
+			if (!block->parent)
+				continue;
+
+			order = __drm_buddy_free(mm, block, 1);
+			if (order >= min_order)
+				return;
+		}
+	}
 }
+EXPORT_SYMBOL(drm_buddy_defrag);
 
 /**
  * drm_buddy_free_block - free a block
@@ -321,7 +386,7 @@ void drm_buddy_free_block(struct drm_buddy *mm,
 	if (drm_buddy_block_is_clear(block))
 		mm->clear_avail += drm_buddy_block_size(mm, block);
 
-	__drm_buddy_free(mm, block);
+	__drm_buddy_free(mm, block, 0);
 }
 EXPORT_SYMBOL(drm_buddy_free_block);
 
@@ -468,7 +533,7 @@ __alloc_range_bias(struct drm_buddy *mm,
 	if (buddy &&
 	    (drm_buddy_block_is_free(block) &&
 	     drm_buddy_block_is_free(buddy)))
-		__drm_buddy_free(mm, block);
+		__drm_buddy_free(mm, block, 0);
 	return ERR_PTR(err);
 }
 
@@ -586,7 +651,7 @@ alloc_from_freelist(struct drm_buddy *mm,
 
 err_undo:
 	if (tmp != order)
-		__drm_buddy_free(mm, block);
+		__drm_buddy_free(mm, block, 0);
 	return ERR_PTR(err);
 }
 
@@ -666,7 +731,7 @@ static int __alloc_range(struct drm_buddy *mm,
 	if (buddy &&
 	    (drm_buddy_block_is_free(block) &&
 	     drm_buddy_block_is_free(buddy)))
-		__drm_buddy_free(mm, block);
+		__drm_buddy_free(mm, block, 0);
 
 err_free:
 	if (err == -ENOSPC && total_allocated_on_err) {
@@ -828,7 +893,7 @@ EXPORT_SYMBOL(drm_buddy_block_trim);
  * @mm: DRM buddy manager to allocate from
  * @start: start of the allowed range for this block
  * @end: end of the allowed range for this block
- * @size: size of the allocation
+ * @size: size of the allocation in bytes
  * @min_block_size: alignment of the allocation
  * @blocks: output list head to add allocated blocks
  * @flags: DRM_BUDDY_*_ALLOCATION flags
diff --git a/include/drm/drm_buddy.h b/include/drm/drm_buddy.h
index 352a6364e26a..68a874846e78 100644
--- a/include/drm/drm_buddy.h
+++ b/include/drm/drm_buddy.h
@@ -167,6 +167,9 @@ void drm_buddy_free_list(struct drm_buddy *mm,
 			 struct list_head *objects,
 			 unsigned int flags);
 
+void drm_buddy_defrag(struct drm_buddy *mm,
+		      unsigned int min_order);
+
 void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p);
 void drm_buddy_block_print(struct drm_buddy *mm,
 			   struct drm_buddy_block *block,
-- 
2.25.1