Signed-off-by: xinhui pan <xinhui.pan@xxxxxxx>
---
change from v5:
reworked
---
drivers/gpu/drm/drm_buddy.c | 161 ++++++++++++++++++++++++++++++++++--
1 file changed, 154 insertions(+), 7 deletions(-)
diff --git a/drivers/gpu/drm/drm_buddy.c b/drivers/gpu/drm/drm_buddy.c
index 11bb59399471..6c795e1b3247 100644
--- a/drivers/gpu/drm/drm_buddy.c
+++ b/drivers/gpu/drm/drm_buddy.c
@@ -386,6 +386,140 @@ alloc_range_bias(struct drm_buddy *mm,
return ERR_PTR(err);
}
+static void __continuous_block_in_tree(struct drm_buddy_block *top_block,
+ struct list_head *fbl,
+ int left,
+ int min_order)
+{
+ /*
+ * Look for continuous memory of
+ * [top_block) when left is true or (top_block] when left is false.
+ * The list of fbl looks like (top_block1][free_block][...][top_blockX).
+ * Memory offset is in ascending order.
+ */
+ while (top_block) {
+ struct drm_buddy_block *block = top_block;
+ int order;
+
+ while (drm_buddy_block_is_split(block))
+ block = left ? block->left : block->right;
+
+ order = drm_buddy_block_order(block);
+ if (order < min_order || !drm_buddy_block_is_free(block))
+ return;
+
+ if (left)
+ list_add_tail(&block->tmp_link, fbl);
+ else
+ list_add(&block->tmp_link, fbl);
+
+ if (order == min_order)
+ return;
+ top_block = __get_buddy(block);
+ }
+}
+
+static bool __free_block_in_order(struct list_head *fbl,
+ struct drm_buddy_block *cur,
+ int order,
+ struct drm_buddy_block **first,
+ struct drm_buddy_block **last)
+{
+ struct drm_buddy_block *fb = cur, *lb = list_next_entry(cur, tmp_link);
+ u64 pages = BIT(order);
+ u64 cur_pages = 0;
+
+ /*
+ * Look for continuous memory which satisfy requested order.
+ * Memory in list fbl are already in below order.
+ * 1) Memory offset are in ascending order.
+ * 2) Memory size are in ascending order from left to middle and
+ * descending order from middle to right.
+ * So walk through the list of fbl from middle to both sides to
+ * choose the bigger memory.
+ * This is because one memory with order X are composed with 2 of order X-1
+ * or 1 of order X-1 and 2 of order X-2, etc. Looks like below.
+ * n
+ * {∑(X - y)} + {2 * (X-n-1))}
+ * 1
+ * And the last 2 memory of order (X-n-1) are at the two sides of list.
+ */
+ list_for_each_entry_from_reverse(fb, fbl, tmp_link) {
+ int prev_order = drm_buddy_block_order(fb);
+
+ list_for_each_entry_from(lb, fbl, tmp_link) {
+ int next_order = drm_buddy_block_order(lb);
+
+ if (prev_order <= next_order)
+ cur_pages += BIT(next_order);
+ else
+ break;
+ }
+
+ cur_pages += BIT(prev_order);
+ if (pages == cur_pages) {
+ *first = fb;
+ *last = list_prev_entry(lb, tmp_link);
+ return true;
+ }
+ BUG_ON(pages < cur_pages);
+ }
+
+ *first = *last = NULL;
+ return false;
+}
+
+static struct drm_buddy_block *
+find_continuous_blocks(struct drm_buddy *mm,
+ int order,
+ unsigned long flags,
+ struct drm_buddy_block **lb)
+{
+ struct list_head *head = &mm->free_list[order - 1];
+ struct drm_buddy_block *free_block, *first = NULL, *last = NULL;
+
+ /*
+ * Look for continuous free memory in buddy and buddy-in-law.
+ * IOW, the most left blocks at right of free block and the most right
+ * blocks at left of free block.
+ */
+
+ list_for_each_entry(free_block, head, link) {
+ struct drm_buddy_block *buddy, *parent, *block;
+ int left, min_order = 0;
+ LIST_HEAD(fbl);
+
+ parent = free_block->parent;
+ if (!parent)
+ continue;
+
+ left = parent->left == free_block;
+ list_add(&free_block->tmp_link, &fbl);
+ buddy = __get_buddy(free_block);
+ __continuous_block_in_tree(buddy, &fbl, left, min_order);
+
+ while (parent && !((parent->left == block) ^ left)) {
+ block = parent;
+ parent = parent->parent;
+ }
+
+ if (!parent)
+ continue;
+
+ buddy = __get_buddy(block);
+ __continuous_block_in_tree(buddy, &fbl, !left, min_order);
+
+ /* list head of fbl is invalid outside.
+ * Walk through list from first fo last only.
+ */
+ if (__free_block_in_order(&fbl, free_block, order, &first, &last))
+ break;
+ }
+
+ *lb = last;
+ return first;
+}
+
static struct drm_buddy_block *
get_maxblock(struct list_head *head)
{
@@ -637,7 +771,7 @@ int drm_buddy_alloc_blocks(struct drm_buddy *mm,
struct list_head *blocks,
unsigned long flags)
{
- struct drm_buddy_block *block = NULL;
+ struct drm_buddy_block *block = NULL, *last_block = NULL;
unsigned int min_order, order;
unsigned long pages;
LIST_HEAD(allocated);
@@ -689,17 +823,30 @@ int drm_buddy_alloc_blocks(struct drm_buddy *mm,
break;
if (order-- == min_order) {
+ if (!(flags & DRM_BUDDY_RANGE_ALLOCATION) &&
+ min_order != 0 && pages == BIT(min_order)) {
+ block = find_continuous_blocks(mm,
+ min_order,
+ flags,
+ &last_block);
+ if (block)
+ break;
+ }
err = -ENOSPC;
goto err_free;
}
} while (1);
- mark_allocated(block);
- mm->avail -= drm_buddy_block_size(mm, block);
- kmemleak_update_trace(block);
- list_add_tail(&block->link, &allocated);
-
- pages -= BIT(order);
+ do {
+ mark_allocated(block);
+ mm->avail -= drm_buddy_block_size(mm, block);
+ kmemleak_update_trace(block);
+ list_add_tail(&block->link, &allocated);
+ pages -= BIT(drm_buddy_block_order(block));
+ if (block == last_block || !last_block)
+ break;
+ block = list_next_entry(block, tmp_link);
+ } while (block);
if (!pages)
break;
