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;
Message-ID: <90e62dcc-49f2-84d7-d845-1d05c9f3dd08@amd.com>
Date:   Mon, 28 Nov 2022 22:39:39 +0530
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101
 Thunderbird/102.5.0
Subject: Re: [PATCH v3] drm: Optimise for continuous memory allocation
Content-Language: en-US
To:     xinhui pan <xinhui.pan@amd.com>, amd-gfx@lists.freedesktop.org
Cc:     linux-kernel@vger.kernel.org, dri-devel@lists.freedesktop.org,
        matthew.auld@intel.com, daniel@ffwll.ch, christian.koenig@amd.com
References: <20221128063419.101586-1-xinhui.pan@amd.com>
From:   Arunpravin Paneer Selvam <arunpravin.paneerselvam@amd.com>
In-Reply-To: <20221128063419.101586-1-xinhui.pan@amd.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?SXJoa0xtRFVtT01POU9QcWJyb3lodVgyMDFFSzVrbFRKUUdyM2IxL3YwRlY2?=
 =?utf-8?B?Rjl4cDA2NVBrVlVmeW1WNXRvdzdKNlFZa2xESmIzRGNacFBqWE1vMGZtMUJq?=
 =?utf-8?B?NkQ4OXlCbFlCT2kxczA4UmRiYjZJWVZVUEpVcEpmVUNTMWpxT2V0d2x5MU5i?=
 =?utf-8?B?UE16aW96eXNHYTMzeGk1S0cvVjJ4Ti9PNG1FOWpRUzk4aHpwY25KM0ZMakFp?=
 =?utf-8?B?VE1JL2F2SUp0Q04rSldFT2duOWdoUnNxZjVLclRLU2drQ054WWVWNmoxeW4v?=
 =?utf-8?B?eks2WHZlNjVDTURxM3dON2czUEVJaUVpUTl5eVdvR2JROUx3Q04xTjhuKzVq?=
 =?utf-8?B?ZTU3amJYL2Y3dVc1TFFkSGtLWTNXSCswbFc4QUcrR3UzVzJzNmNxOW1qWG9u?=
 =?utf-8?B?S3FrbHJJb2FKenRjaUhVNXFvVDRFMVZKdElxSEhSRTFGZXoxamdKSWVNek52?=
 =?utf-8?B?ZU5mNS9XUnJTdHcwdnNUUmk1RG8zdVU3NVNtWEZmdWt2NzRDRjc1WHlPZ0hI?=
 =?utf-8?B?a0ozWjN6eFFSY1NhUStEdlVpNnNXeEZBc2RNQVAxUmdsNFlsWEpHeEZnSGJq?=
 =?utf-8?B?V0hvbXg0cG02Vm1iVGxLaGE0b255NlFVVURnWThYVWpLaG5LVGVsVDZ4ejlJ?=
 =?utf-8?B?TmEyMTJaVmpyVUVITloyQThrVDg2UG1TRG1aeWUyRUtqK3UyNHZCV3NBYnMv?=
 =?utf-8?B?dkFYbkM2QVp0T2JlaU5YWDVvcEV6UWNSMHVzY0Zha0FnS294RElQckFNTnJD?=
 =?utf-8?B?cnVmVklHajU5dGFLRnAra0VPdzFqZTlZZDZmNzZuZGZ0Q25STkttcDRlWERK?=
 =?utf-8?B?MjMxSEtrQlRWYnZSRjJDUUFNNUUyUkNiODB3TEtYYzUyKy80eHowa1E3Qll1?=
 =?utf-8?B?M2NPajBmL0hnWmpETHZRVkZTallJWmhQZW1PUTRqaS95bklEcEJGUS9lckVs?=
 =?utf-8?B?eHBCOG5rSmhmelUwQjMwUFd1UWU5NzZYY2I5a2VxR3JweVZxUXpzT3g2SCtW?=
 =?utf-8?B?NU9Fd1BNRDk2bk9IZG5mVWpNcHdhejRoZUNKN0pBZDBDWTl1R0JyNTRHZlRB?=
 =?utf-8?B?Nmo2dm1RYy9IYU55ZTE3MElPYlBlZjNyUzVBdGtxV1gzM3c1RlNINktkUmRH?=
 =?utf-8?B?L2lBa240a2dZbzJiWTgwN1V4UXFIcldHcVVNcUN6U3lWajhkVU53b1YySURK?=
 =?utf-8?B?dU9hWE9ldFRIYXlzZnI1T2cxekErUGcvZjlKL28rSlZLdHZzbDhaMkNuVmtE?=
 =?utf-8?B?b3p0TWJEeFU3NXdlSm1Ed1BXazRlOHZlSEJieUE0YVdCTGxYSHZidnpZbTAr?=
 =?utf-8?B?TlRSMUxxd0VtbURTcWpWM2VLb0NtWThjRStwRzhXbHJ2Q3NBaVd6NUdydzcx?=
 =?utf-8?B?M3RDUkI0ak1ibUJHYzZ4ZDRUWjRjeWh6SmppYW1ybm11VVluYjJVTHcydi94?=
 =?utf-8?B?Njh5SkNDRlgrQkVESlI0QVhrRHYzL29KaXE5MU9jSEY4cklhWUNRTEt0a1Na?=
 =?utf-8?B?QWkxeGRpQnltTTRZRkN4U29KUWhUZHRTZkd5SWtJUmh6aGxqZjhETE1vT0Zq?=
 =?utf-8?B?ZHovcXlKc21RaUxGODNyTUpJcFg3YkpDb1BBQnJKNDJocHZoeklXaURwQVgx?=
 =?utf-8?B?eEt2WDdXVFRUSnVsTDhqWHozRmhHSVpQbEpMZFI0cFdscHU4Zml2UWJmdVhw?=
 =?utf-8?B?WTVGUDNNZUw3dVllY2x5RUVDSFE4UGxhRVZETTJuZkZyRHZTaStSSFp5ZWlw?=
 =?utf-8?B?bFZsa21PaTVKWXB1dGxNdVJuN3I3WHRqNi82MlpDeGZxbHRic3BsenVNMFho?=
 =?utf-8?B?bXlsNU81dVNkOFlGSWlpUEl5RXJEYVBCc0JOT0pzaGdlOG9KRHBaaXhFNXpZ?=
 =?utf-8?B?T0dSSkhJcnBCTVIwWmJ1RVRQVmpRRDRMeHYxWnBVbkE0NjNWN3AzR3hWdEhN?=
 =?utf-8?B?M2xkbjlZRzErTmxNUHRKQk9YdmFqK0ZQTWlnOFM5M2picExIYWZhbXlRZlJp?=
 =?utf-8?B?VUVSTVZ1OGE2R1NxQ3BDZ0NWMWJqaVYyTDIwcFgvUG81QzBKY0ZLdWJ5OEZG?=
 =?utf-8?B?ODljUTJpb0dndUU5ZEE4dWkwUklBQ0s5QzRxSnZaM1FVVXNJREUyeDlwTTNO?=
 =?utf-8?Q?aEMxGHHPzBnnyqz9JJ5UT2vor?=
X-OriginatorOrg: amd.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 574d9731-0292-4724-e1d2-08dad1635afc
X-MS-Exchange-CrossTenant-AuthSource: MN2PR12MB4342.namprd12.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 28 Nov 2022 17:09:48.5773
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 3dd8961f-e488-4e60-8e11-a82d994e183d
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: J2O6WfegHIVpz3ef48/eZZ2UYtefbq58JUeGTM2NU9QF535CDDtNcjtswly0A/oMB+JeYnpj2WIWeTpmBVzZlw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: LV2PR12MB5751
X-Spam-Status: No, score=-2.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,NICE_REPLY_A,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

Hi Xinhui,

On 11/28/2022 12:04 PM, xinhui pan wrote:
> Currently drm-buddy does not have full knowledge of continuous memory.
>
> Lets consider scenario below.
> order 1:    L		    R
> order 0: LL	LR	RL	RR
> for order 1 allocation, it can offer L or R or LR+RL.
>
> For now, we only implement L or R case for continuous memory allocation.
> So this patch aims to implement the LR+RL case.
>
> Signed-off-by: xinhui pan <xinhui.pan@amd.com>
> ---
> change from v2:
> search continuous block in nearby root if needed
>
> change from v1:
> implement top-down continuous allocation
> ---
>   drivers/gpu/drm/drm_buddy.c | 78 +++++++++++++++++++++++++++++++++----
>   1 file changed, 71 insertions(+), 7 deletions(-)
>
> diff --git a/drivers/gpu/drm/drm_buddy.c b/drivers/gpu/drm/drm_buddy.c
> index 11bb59399471..ff58eb3136d2 100644
> --- a/drivers/gpu/drm/drm_buddy.c
> +++ b/drivers/gpu/drm/drm_buddy.c
> @@ -386,6 +386,58 @@ alloc_range_bias(struct drm_buddy *mm,
>   	return ERR_PTR(err);
>   }
>   
> +static struct drm_buddy_block *
> +find_continuous_blocks(struct drm_buddy *mm,
> +		       int order,
> +		       unsigned long flags,
> +		       struct drm_buddy_block **rn)
> +{
> +	struct list_head *head = &mm->free_list[order];
> +	struct drm_buddy_block *node, *parent, *free_node, *max_node = NULL;
NIT: We usually name the variable as *block or ***_block for drm buddy 
and we have *node or ***_node for drm mm manager.
> +	int i;
> +
> +	list_for_each_entry(free_node, head, link) {
> +		if (max_node) {
> +			if (!(flags & DRM_BUDDY_TOPDOWN_ALLOCATION))
> +				break;
> +
> +			if (drm_buddy_block_offset(free_node) <
> +			    drm_buddy_block_offset(max_node))
> +				continue;
> +		}
> +
> +		parent = free_node;
> +		do {
> +			node = parent;
> +			parent = parent->parent;
> +		} while (parent && parent->right == node);
> +
> +		if (!parent) {
> +			for (i = 0; i < mm->n_roots - 1; i++)
> +				if (mm->roots[i] == node)
> +					break;
> +			if (i == mm->n_roots - 1)
> +				continue;
> +			node = mm->roots[i + 1];
> +		} else {
> +			node = parent->right;
> +		}
> +
> +		while (drm_buddy_block_is_split(node))
> +			node = node->left;
> +
> +		if (drm_buddy_block_is_free(node) &&
> +		    drm_buddy_block_order(node) == order) {
> +			*rn = node;
> +			max_node = free_node;
> +			BUG_ON(drm_buddy_block_offset(node) !=
> +				drm_buddy_block_offset(max_node) +
> +				drm_buddy_block_size(mm, max_node));
> +		}
> +	}
> +	return max_node;
> +}
> +
>   static struct drm_buddy_block *
>   get_maxblock(struct list_head *head)
>   {
> @@ -637,7 +689,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, *rblock = NULL;
>   	unsigned int min_order, order;
>   	unsigned long pages;
>   	LIST_HEAD(allocated);
> @@ -689,17 +741,29 @@ 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(order + 1)) {
> +					block = find_continuous_blocks(mm,
> +								       order,
> +								       flags,
> +								       &rblock);
> +					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(order);
> +			block = rblock;
> +			rblock = NULL;
> +		} while (block);
I think with this approach, if we are lucky enough we may get contiguous 
blocks in one order level down in RL
combination from the freelist?

Regards,
Arun
>   
>   		if (!pages)
>   			break;