Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Received-SPF: Pass (protection.outlook.com: domain of amd.com designates
 165.204.84.17 as permitted sender) receiver=protection.outlook.com;
 client-ip=165.204.84.17; helo=SATLEXMB04.amd.com; pr=C
From:   xinhui pan <xinhui.pan@amd.com>
To:     <amd-gfx@lists.freedesktop.org>
CC:     <daniel@ffwll.ch>, <matthew.auld@intel.com>,
        <christian.koenig@amd.com>, <dri-devel@lists.freedesktop.org>,
        <linux-kernel@vger.kernel.org>, <intel-gfx@lists.freedesktop.org>,
        <arunpravin.paneerselvam@amd.com>,
        "xinhui pan" <xinhui.pan@amd.com>
Subject: [PATCH v6] drm: Optimise for continuous memory allocation
Date:   Sun, 18 Dec 2022 14:57:08 +0800
Message-ID: <20221218065708.93332-1-xinhui.pan@amd.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8bit
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 18 Dec 2022 06:57:31.7678
 (UTC)
X-MS-Exchange-CrossTenant-Network-Message-Id: fdbb26fb-0852-4ed5-11d7-08dae0c5227d
X-MS-Exchange-CrossTenant-Id: 3dd8961f-e488-4e60-8e11-a82d994e183d
X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=3dd8961f-e488-4e60-8e11-a82d994e183d;Ip=[165.204.84.17];Helo=[SATLEXMB04.amd.com]
X-MS-Exchange-CrossTenant-AuthSource: BN8NAM11FT116.eop-nam11.prod.protection.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Anonymous
X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN7PR12MB8170
X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE,
        RCVD_IN_MSPIKE_H2,SPF_HELO_PASS,SPF_PASS autolearn=ham
        autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

Optimise a little when continuous memory request fails.

There are memory holes and continuous memory request usually fails when
order is too big.
Currently buddy only look for exactly order memory for such request.
Now we can try again to look for several smaller continuous memory on
failure.

Signed-off-by: xinhui pan <xinhui.pan@amd.com>
---
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;
-- 
2.34.1