From patchwork Mon Jun 15 14:54:13 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Christian_K=C3=B6nig?= X-Patchwork-Id: 11605299 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id B01AC90 for ; Mon, 15 Jun 2020 15:05:10 +0000 (UTC) Received: from gabe.freedesktop.org (gabe.freedesktop.org [131.252.210.177]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 8D76E20739 for ; Mon, 15 Jun 2020 15:05:10 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="nHlCzFEV" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 8D76E20739 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=intel-gfx-bounces@lists.freedesktop.org Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id 48E636E343; Mon, 15 Jun 2020 15:05:07 +0000 (UTC) X-Original-To: intel-gfx@lists.freedesktop.org Delivered-To: intel-gfx@lists.freedesktop.org Received: from mail-wm1-x343.google.com (mail-wm1-x343.google.com [IPv6:2a00:1450:4864:20::343]) by gabe.freedesktop.org (Postfix) with ESMTPS id EC52A89D5F; Mon, 15 Jun 2020 14:54:18 +0000 (UTC) Received: by mail-wm1-x343.google.com with SMTP id o8so5521980wmh.4; Mon, 15 Jun 2020 07:54:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:subject:date:message-id:mime-version :content-transfer-encoding; bh=d6FJC4M7yb6UETXkb1sZmFJEHJtepxmsrbWdTkTqQQ8=; b=nHlCzFEVyKRzMVFnW9EaJYrbpsYcACAz4JdpYOBNQCPg4rDMm9haKlCBs1UsnF7cDQ C5I8Kxd3nluUECfM1zxGfYo5VneriB2dzlEflZxpSqW2vwua4ceYiRP/iPMR+HabD5gs wgRcwtwpXzsmHgpoQAoSYabj3qFo20rPgA4jF80JIbwIfEjRcZVd8jBNLV5VpWXR8za/ lFSHWv7OpXAsPmeiZ3fCjHXB6Dy6vDc+U9NvLiiSWLM43aNmPRuipT1/3+N9HXaVreFI b2qK/yv7C/vSg3/rBYfhuLjqqkVjBJmduEJ2AQ2hTE1W5QT6WCvSESxAcgHkMxgn+vLw f/+w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:mime-version :content-transfer-encoding; bh=d6FJC4M7yb6UETXkb1sZmFJEHJtepxmsrbWdTkTqQQ8=; b=LdCV6lF7/Fa7Cr6qsrFYW5DApf+vus0P3qndWO6k7HjqT5ljq+W2xrfxQScI2Tbb75 FvNdi4guBvacu1083NFQpkISy9S24zlpgmfKnlQuxjUWlcUzl3diGwfWuLaxps60Zq9i aIJKZAJzf1rfyXExYot40yb5dImGtM9+fWw5dNKFoNj5ZDbozEdHexnb+jIejnBQrgK7 4fMWFdY7whFTuDiDVj90D2KA3PbLpvc53Gzn1rISb1OS6nWWWM/Ewu3ifpEPI0ay3k+c 4DBAEHwjRYdb3a/8klVr28yjgVggDEsis0KZ1inDmCDE1mpdQet9nKa8hxkvH4g3klKB Lneg== X-Gm-Message-State: AOAM53226dwTZi4+2DvFZtCYtcz4bIxM6t/wS6UbFB3dto5xQaAKWAUu hNa5pW1ExB1DLuHub7LliRs= X-Google-Smtp-Source: ABdhPJzFlr3SK4cW5QFYIWou/UGCvXUjzgf6XkNhGl3ErV2Y7alWL1lv/fphIYIiRJ78f7jsFFvYpw== X-Received: by 2002:a7b:cb11:: with SMTP id u17mr13445453wmj.84.1592232857593; Mon, 15 Jun 2020 07:54:17 -0700 (PDT) Received: from abel.fritz.box ([2a02:908:1252:fb60:a5ab:7330:3773:519a]) by smtp.gmail.com with ESMTPSA id j4sm24277442wma.7.2020.06.15.07.54.15 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 15 Jun 2020 07:54:16 -0700 (PDT) From: " =?utf-8?q?Christian_K=C3=B6nig?= " X-Google-Original-From: =?utf-8?q?Christian_K=C3=B6nig?= To: chris@chris-wilson.co.uk, intel-gfx@lists.freedesktop.org, nirmoy.das@amd.com, dri-devel@lists.freedesktop.org Date: Mon, 15 Jun 2020 16:54:13 +0200 Message-Id: <20200615145415.1775-1-christian.koenig@amd.com> X-Mailer: git-send-email 2.17.1 MIME-Version: 1.0 X-Mailman-Approved-At: Mon, 15 Jun 2020 15:05:06 +0000 Subject: [Intel-gfx] [PATCH 1/3] drm/mm: remove unused rb_hole_size() X-BeenThere: intel-gfx@lists.freedesktop.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Intel graphics driver community testing & development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: intel-gfx-bounces@lists.freedesktop.org Sender: "Intel-gfx" Just some code cleanup. Signed-off-by: Christian König Reviewed-by: Nirmoy Das --- drivers/gpu/drm/drm_mm.c | 5 ----- 1 file changed, 5 deletions(-) diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 82d2888eb7fe..425fcd3590e8 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -305,11 +305,6 @@ static inline struct drm_mm_node *rb_hole_addr_to_node(struct rb_node *rb) return rb_entry_safe(rb, struct drm_mm_node, rb_hole_addr); } -static inline u64 rb_hole_size(struct rb_node *rb) -{ - return rb_entry(rb, struct drm_mm_node, rb_hole_size)->hole_size; -} - static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size) { struct rb_node *rb = mm->holes_size.rb_root.rb_node; From patchwork Mon Jun 15 14:54:14 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Christian_K=C3=B6nig?= X-Patchwork-Id: 11605297 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 1B43290 for ; Mon, 15 Jun 2020 15:05:09 +0000 (UTC) Received: from gabe.freedesktop.org (gabe.freedesktop.org [131.252.210.177]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id EAE0D20739 for ; Mon, 15 Jun 2020 15:05:08 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="AUYeuwlk" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org EAE0D20739 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=intel-gfx-bounces@lists.freedesktop.org Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id 314346E33E; Mon, 15 Jun 2020 15:05:07 +0000 (UTC) X-Original-To: intel-gfx@lists.freedesktop.org Delivered-To: intel-gfx@lists.freedesktop.org Received: from mail-wm1-x342.google.com (mail-wm1-x342.google.com [IPv6:2a00:1450:4864:20::342]) by gabe.freedesktop.org (Postfix) with ESMTPS id CFD9D89D5F; Mon, 15 Jun 2020 14:54:19 +0000 (UTC) Received: by mail-wm1-x342.google.com with SMTP id r9so14960184wmh.2; Mon, 15 Jun 2020 07:54:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:subject:date:message-id:in-reply-to:references:mime-version :content-transfer-encoding; bh=AI5FhLk9FP9TGZGo8fRTGDecjA5Rowrr5/b2Hx2l40Y=; b=AUYeuwlkzeTEMmKgkzuG7NQaiCFAqtRRURHNkXegKZ4aAEqchXQ2HtmG2tFMQoyVZp HJiOi/501eEEOMkupz/zBxekgirdUq9qCDFtGoaEqnoQzFZVvAGTurku1HQ1vj74UoOv s1Jorx7T+s/hi1ms4vfFK7qKvES1X0dn9tDPjhhAjL0NB1ztdkBvDJOOxBJQDjo3lrzi fJDRkXZkkr3xJiLbmv5Tj6wvqmSsGnZP+J30etVnaHawvtYIW2Ajo0VoQr/yRdASxyS7 sUMtn2Dh96f0qp0lc/lsMzzOZkQFXTS5CvO3q7dCJfGFINiXdCdtOjcu8CQdzXm5O0z6 7SLQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=AI5FhLk9FP9TGZGo8fRTGDecjA5Rowrr5/b2Hx2l40Y=; b=L/xn5k3SBqPgy4kFdIVGungduOpOpsVIOg+pOSEfbmNzKJeHByIL/lJTjRhqECpihd NkqLT7dxGt8Kk4fDbzlySKK/UOthAFHghXAXPkO5lox/S93PHkNRjTTYRTm4oBAPjwSm ww4MmwCEHyoxB8KBihWreVH2jJB39JRmUbfLX6mphsXCGEHfEWn7M+z5Sb8jqckAl+1b YazZ2v4l0Et5h45pyHQy1elzxn0wOYeEm1CnXIdBma/vOewRw6zWHDJZQX5HAp4W8+Zf V/KhDyw7cXi/SwWzSKu2sf+g5/7waITXlNVKHouv514vJO1iwamptMQZdRs6fIUtCbB2 tLCA== X-Gm-Message-State: AOAM530cSiXOkQy/kOB6aUoWZZxrm49JgxGPjpPpijBP9M5CUKRKPSeE 9neyTQA1c1SumWFLMMxBVygg1rQr X-Google-Smtp-Source: ABdhPJzs34cUZA9c8hhih4GsKBtPO5mVLb8jD3HNJbjUYETf2wBiCMUtuHDdJ5AJYFvtQcxQVLyq3Q== X-Received: by 2002:a1c:9ec5:: with SMTP id h188mr13399954wme.9.1592232858550; Mon, 15 Jun 2020 07:54:18 -0700 (PDT) Received: from abel.fritz.box ([2a02:908:1252:fb60:a5ab:7330:3773:519a]) by smtp.gmail.com with ESMTPSA id j4sm24277442wma.7.2020.06.15.07.54.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 15 Jun 2020 07:54:17 -0700 (PDT) From: " =?utf-8?q?Christian_K=C3=B6nig?= " X-Google-Original-From: =?utf-8?q?Christian_K=C3=B6nig?= To: chris@chris-wilson.co.uk, intel-gfx@lists.freedesktop.org, nirmoy.das@amd.com, dri-devel@lists.freedesktop.org Date: Mon, 15 Jun 2020 16:54:14 +0200 Message-Id: <20200615145415.1775-2-christian.koenig@amd.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200615145415.1775-1-christian.koenig@amd.com> References: <20200615145415.1775-1-christian.koenig@amd.com> MIME-Version: 1.0 X-Mailman-Approved-At: Mon, 15 Jun 2020 15:05:06 +0000 Subject: [Intel-gfx] [PATCH 2/3] drm/mm: optimize find_hole() as well X-BeenThere: intel-gfx@lists.freedesktop.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Intel graphics driver community testing & development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: intel-gfx-bounces@lists.freedesktop.org Sender: "Intel-gfx" Abort early if there isn't enough space to allocate from a subtree. Signed-off-by: Christian König Acked-by: Nirmoy Das --- drivers/gpu/drm/drm_mm.c | 11 +++++++---- drivers/gpu/drm/selftests/test-drm_mm.c | 11 ----------- 2 files changed, 7 insertions(+), 15 deletions(-) diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 425fcd3590e8..177a5df0fe95 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -325,7 +325,7 @@ static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size) return best; } -static struct drm_mm_node *find_hole(struct drm_mm *mm, u64 addr) +static struct drm_mm_node *find_hole_addr(struct drm_mm *mm, u64 addr, u64 size) { struct rb_node *rb = mm->holes_addr.rb_node; struct drm_mm_node *node = NULL; @@ -333,6 +333,9 @@ static struct drm_mm_node *find_hole(struct drm_mm *mm, u64 addr) while (rb) { u64 hole_start; + if (rb_hole_addr_to_node(rb)->subtree_max_hole < size) + break; + node = rb_hole_addr_to_node(rb); hole_start = __drm_mm_hole_node_start(node); @@ -358,10 +361,10 @@ first_hole(struct drm_mm *mm, return best_hole(mm, size); case DRM_MM_INSERT_LOW: - return find_hole(mm, start); + return find_hole_addr(mm, start, size); case DRM_MM_INSERT_HIGH: - return find_hole(mm, end); + return find_hole_addr(mm, end, size); case DRM_MM_INSERT_EVICT: return list_first_entry_or_null(&mm->hole_stack, @@ -497,7 +500,7 @@ int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node) return -ENOSPC; /* Find the relevant hole to add our node to */ - hole = find_hole(mm, node->start); + hole = find_hole_addr(mm, node->start, 0); if (!hole) return -ENOSPC; diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c index ca5f35def905..b879aedfc00d 100644 --- a/drivers/gpu/drm/selftests/test-drm_mm.c +++ b/drivers/gpu/drm/selftests/test-drm_mm.c @@ -1981,16 +1981,6 @@ static int __igt_once(unsigned int mode) } memset(&node, 0, sizeof(node)); - err = drm_mm_insert_node_generic(&mm, &node, - 2, 0, 0, - mode | DRM_MM_INSERT_ONCE); - if (!err) { - pr_err("Unexpectedly inserted the node into the wrong hole: node.start=%llx\n", - node.start); - err = -EINVAL; - goto err_node; - } - err = drm_mm_insert_node_generic(&mm, &node, 2, 0, 0, mode); if (err) { pr_err("Could not insert the node into the available hole!\n"); @@ -1998,7 +1988,6 @@ static int __igt_once(unsigned int mode) goto err_hi; } -err_node: drm_mm_remove_node(&node); err_hi: drm_mm_remove_node(&rsvd_hi); From patchwork Mon Jun 15 14:54:15 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Christian_K=C3=B6nig?= X-Patchwork-Id: 11605301 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 03ECF14DD for ; Mon, 15 Jun 2020 15:05:12 +0000 (UTC) Received: from gabe.freedesktop.org (gabe.freedesktop.org [131.252.210.177]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id D637920739 for ; Mon, 15 Jun 2020 15:05:11 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="hARkJctl" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org D637920739 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=intel-gfx-bounces@lists.freedesktop.org Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id 8B7B46E34B; Mon, 15 Jun 2020 15:05:07 +0000 (UTC) X-Original-To: intel-gfx@lists.freedesktop.org Delivered-To: intel-gfx@lists.freedesktop.org Received: from mail-wm1-x342.google.com (mail-wm1-x342.google.com [IPv6:2a00:1450:4864:20::342]) by gabe.freedesktop.org (Postfix) with ESMTPS id E6BDF6E330; Mon, 15 Jun 2020 14:54:20 +0000 (UTC) Received: by mail-wm1-x342.google.com with SMTP id r15so15140090wmh.5; Mon, 15 Jun 2020 07:54:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:subject:date:message-id:in-reply-to:references:mime-version :content-transfer-encoding; bh=k09U0VG1ixp4ZkjUC6lkt8f6MU6uFqrJ3qqTzv3/HJY=; b=hARkJctlAC8+yGOj6dpu0fz7YlhrZrQNiJYN6/ccdlxyb54Qy3cFuOCmA6eHaFYwYX zANsaaV/5cMjh0IWncnZDPFxPezHASG9NOQJDlSq/CUqMHCJEky0rCi3VgxsJYogGocx u5fmuFgUg4DNiFUJvIz905VwSnfJDXXvkrtyUN9XLHWEksq60mcmTS1MjNu80v4N3UFT 1ZCv0icCJMukEDlyCwqJxr35pppsvpzdbSJpa3bnOGTWV5BhGDgS2MYEbhFO4Vtlccv1 htZIUlqbXlq/JTHT+GhuJx+ebe2mLOx5yNwlwNA8ZNE1GUf25MV4IFymA5k45C7jhPdh NEHw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=k09U0VG1ixp4ZkjUC6lkt8f6MU6uFqrJ3qqTzv3/HJY=; b=Dn46baxJjQk2pxL4K8QsdXeLxSXZi5vaBq5l3W2kkY/EZemdbqZ0iOIy+IKEOh6/1K UK+Q/3jLnDEsFKe+oTLpoistYQ9uLyyQa4RzrbKVUvkkeyD3DI3ErLl2LdGAbn4Zq/IQ CkM/PojEMOtRO10jiufAbTUsKvv9BBYqw6FR3bJD4tkEdAFEyHaB+eJUb5cZt/alwyOM I5SyjKbWMlvxhoC6ysduPl3GUvler+yHm4NBl1YHowTKhYYWYzl5JEK1U5C5K4z0Br0Z HzhfSxSkckonLfIodLcg4nTEWGglff+XdbAdzX7CY/DWHUWIB/HkYbNjEy5xMR0ws7oa cMtw== X-Gm-Message-State: AOAM532c8JavQzGffJ34SqkAfYCOb8tbYkHQZHnmFv3wJx3DCKnvwGBs a4TXII26QbpemlCILZssb//Xk4Aq X-Google-Smtp-Source: ABdhPJxzrizoSk90HuvD8yGlAKVZGJ1JOZKoLLvE/jRValE3Qp3ktENr6Jj/CI7LFxJ+quqC/+FsZA== X-Received: by 2002:a1c:9d09:: with SMTP id g9mr13162436wme.31.1592232859603; Mon, 15 Jun 2020 07:54:19 -0700 (PDT) Received: from abel.fritz.box ([2a02:908:1252:fb60:a5ab:7330:3773:519a]) by smtp.gmail.com with ESMTPSA id j4sm24277442wma.7.2020.06.15.07.54.18 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 15 Jun 2020 07:54:19 -0700 (PDT) From: " =?utf-8?q?Christian_K=C3=B6nig?= " X-Google-Original-From: =?utf-8?q?Christian_K=C3=B6nig?= To: chris@chris-wilson.co.uk, intel-gfx@lists.freedesktop.org, nirmoy.das@amd.com, dri-devel@lists.freedesktop.org Date: Mon, 15 Jun 2020 16:54:15 +0200 Message-Id: <20200615145415.1775-3-christian.koenig@amd.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200615145415.1775-1-christian.koenig@amd.com> References: <20200615145415.1775-1-christian.koenig@amd.com> MIME-Version: 1.0 X-Mailman-Approved-At: Mon, 15 Jun 2020 15:05:06 +0000 Subject: [Intel-gfx] [PATCH 3/3] drm/mm: cleanup and improve next_hole_*_addr() X-BeenThere: intel-gfx@lists.freedesktop.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Intel graphics driver community testing & development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: intel-gfx-bounces@lists.freedesktop.org Sender: "Intel-gfx" Skipping just one branch of the tree is not the most effective approach. Instead use a macro to define the traversal functions and sort out both branch sides. This improves the performance of the unit tests by a factor of more than 4. Signed-off-by: Christian König Reviewed-by: Nirmoy Das --- drivers/gpu/drm/drm_mm.c | 106 +++++++++++++-------------------------- 1 file changed, 34 insertions(+), 72 deletions(-) diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 177a5df0fe95..a4a04d246135 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -325,6 +325,11 @@ static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size) return best; } +static bool usable_hole_addr(struct rb_node *rb, u64 size) +{ + return rb && rb_hole_addr_to_node(rb)->subtree_max_hole >= size; +} + static struct drm_mm_node *find_hole_addr(struct drm_mm *mm, u64 addr, u64 size) { struct rb_node *rb = mm->holes_addr.rb_node; @@ -333,7 +338,7 @@ static struct drm_mm_node *find_hole_addr(struct drm_mm *mm, u64 addr, u64 size) while (rb) { u64 hole_start; - if (rb_hole_addr_to_node(rb)->subtree_max_hole < size) + if (!usable_hole_addr(rb, size)) break; node = rb_hole_addr_to_node(rb); @@ -374,82 +379,39 @@ first_hole(struct drm_mm *mm, } /** - * next_hole_high_addr - returns next hole for a DRM_MM_INSERT_HIGH mode request - * @entry: previously selected drm_mm_node - * @size: size of the a hole needed for the request - * - * This function will verify whether left subtree of @entry has hole big enough - * to fit the requtested size. If so, it will return previous node of @entry or - * else it will return parent node of @entry + * DECLARE_NEXT_HOLE_ADDR - macro to declare next hole functions + * @name: name of function to declare + * @first: first rb member to traverse (either rb_left or rb_right). + * @last: last rb member to traverse (either rb_right or rb_left). * - * It will also skip the complete left subtree if subtree_max_hole of that - * subtree is same as the subtree_max_hole of the @entry. - * - * Returns: - * previous node of @entry if left subtree of @entry can serve the request or - * else return parent of @entry + * This macro declares a function to return the next hole of the addr rb tree. + * While traversing the tree we take the searched size into account and only + * visit branches with potential big enough holes. */ -static struct drm_mm_node * -next_hole_high_addr(struct drm_mm_node *entry, u64 size) -{ - struct rb_node *rb_node, *left_rb_node, *parent_rb_node; - struct drm_mm_node *left_node; - - if (!entry) - return NULL; - rb_node = &entry->rb_hole_addr; - if (rb_node->rb_left) { - left_rb_node = rb_node->rb_left; - parent_rb_node = rb_parent(rb_node); - left_node = rb_entry(left_rb_node, - struct drm_mm_node, rb_hole_addr); - if (left_node->subtree_max_hole < size && - parent_rb_node && parent_rb_node->rb_left != rb_node) - return rb_hole_addr_to_node(parent_rb_node); - } - - return rb_hole_addr_to_node(rb_prev(rb_node)); +#define DECLARE_NEXT_HOLE_ADDR(name, first, last) \ +static struct drm_mm_node *name(struct drm_mm_node *entry, u64 size) \ +{ \ + struct rb_node *parent, *node = &entry->rb_hole_addr; \ + \ + if (!entry || RB_EMPTY_NODE(node)) \ + return NULL; \ + \ + if (usable_hole_addr(node->first, size)) { \ + node = node->first; \ + while (usable_hole_addr(node->last, size)) \ + node = node->last; \ + return rb_hole_addr_to_node(node); \ + } \ + \ + while ((parent = rb_parent(node)) && node == parent->first) \ + node = parent; \ + \ + return rb_hole_addr_to_node(parent); \ } -/** - * next_hole_low_addr - returns next hole for a DRM_MM_INSERT_LOW mode request - * @entry: previously selected drm_mm_node - * @size: size of the a hole needed for the request - * - * This function will verify whether right subtree of @entry has hole big enough - * to fit the requtested size. If so, it will return next node of @entry or - * else it will return parent node of @entry - * - * It will also skip the complete right subtree if subtree_max_hole of that - * subtree is same as the subtree_max_hole of the @entry. - * - * Returns: - * next node of @entry if right subtree of @entry can serve the request or - * else return parent of @entry - */ -static struct drm_mm_node * -next_hole_low_addr(struct drm_mm_node *entry, u64 size) -{ - struct rb_node *rb_node, *right_rb_node, *parent_rb_node; - struct drm_mm_node *right_node; - - if (!entry) - return NULL; - - rb_node = &entry->rb_hole_addr; - if (rb_node->rb_right) { - right_rb_node = rb_node->rb_right; - parent_rb_node = rb_parent(rb_node); - right_node = rb_entry(right_rb_node, - struct drm_mm_node, rb_hole_addr); - if (right_node->subtree_max_hole < size && - parent_rb_node && parent_rb_node->rb_right != rb_node) - return rb_hole_addr_to_node(parent_rb_node); - } - - return rb_hole_addr_to_node(rb_next(rb_node)); -} +DECLARE_NEXT_HOLE_ADDR(next_hole_high_addr, rb_left, rb_right) +DECLARE_NEXT_HOLE_ADDR(next_hole_low_addr, rb_right, rb_left) static struct drm_mm_node * next_hole(struct drm_mm *mm,