// SPDX-License-Identifier: GPL-2.0 OR MIT/* * Copyright 2011 Red Hat Inc. * Copyright 2023 Intel Corporation. * All Rights Reserved. * * Permission is hereby granted, free of charge, to any person obtaining a * copy of this software and associated documentation files (the * "Software"), to deal in the Software without restriction, including * without limitation the rights to use, copy, modify, merge, publish, * distribute, sub license, and/or sell copies of the Software, and to * permit persons to whom the Software is furnished to do so, subject to * the following conditions: * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE * USE OR OTHER DEALINGS IN THE SOFTWARE. * * The above copyright notice and this permission notice (including the * next paragraph) shall be included in all copies or substantial portions * of the Software. * *//* Algorithm: * * We store the last allocated bo in "hole", we always try to allocate * after the last allocated bo. Principle is that in a linear GPU ring * progression was is after last is the oldest bo we allocated and thus * the first one that should no longer be in use by the GPU. * * If it's not the case we skip over the bo after last to the closest * done bo if such one exist. If none exist and we are not asked to * block we report failure to allocate. * * If we are asked to block we wait on all the oldest fence of all * rings. We just wait for any of those fence to complete. */ #include <drm/drm_suballoc.h>#include <drm/drm_print.h>#include <linux/slab.h>#include <linux/sched.h>#include <linux/wait.h>#include <linux/dma-fence.h> static void drm_suballoc_remove_locked(struct drm_suballoc *sa);static void drm_suballoc_try_free(struct drm_suballoc_manager *sa_manager); /** * drm_suballoc_manager_init() - Initialise the drm_suballoc_manager * @sa_manager: pointer to the sa_manager * @size: number of bytes we want to suballocate * @align: alignment for each suballocated chunk * * Prepares the suballocation manager for suballocations. */void drm_suballoc_manager_init(struct drm_suballoc_manager *sa_manager,			       size_t size, size_t align){	unsigned int i; 	BUILD_BUG_ON(!is_power_of_2(DRM_SUBALLOC_MAX_QUEUES)); 	if (!align)		align = 1; 	/* alignment must be a power of 2 */	if (WARN_ON_ONCE(align & (align - 1)))		align = roundup_pow_of_two(align); 	init_waitqueue_head(&sa_manager->wq);	sa_manager->size = size;	sa_manager->align = align;	sa_manager->hole = &sa_manager->olist;	INIT_LIST_HEAD(&sa_manager->olist);	for (i = 0; i < DRM_SUBALLOC_MAX_QUEUES; ++i)		INIT_LIST_HEAD(&sa_manager->flist[i]);}EXPORT_SYMBOL(drm_suballoc_manager_init); /** * drm_suballoc_manager_fini() - Destroy the drm_suballoc_manager * @sa_manager: pointer to the sa_manager * * Cleans up the suballocation manager after use. All fences added * with drm_suballoc_free() must be signaled, or we cannot clean up * the entire manager. */void drm_suballoc_manager_fini(struct drm_suballoc_manager *sa_manager){	struct drm_suballoc *sa, *tmp; 	if (!sa_manager->size)		return; 	if (!list_empty(&sa_manager->olist)) {		sa_manager->hole = &sa_manager->olist;		drm_suballoc_try_free(sa_manager);		if (!list_empty(&sa_manager->olist))			DRM_ERROR("sa_manager is not empty, clearing anyway\n");	}	list_for_each_entry_safe(sa, tmp, &sa_manager->olist, olist) {		drm_suballoc_remove_locked(sa);	} 	sa_manager->size = 0;}EXPORT_SYMBOL(drm_suballoc_manager_fini); static void drm_suballoc_remove_locked(struct drm_suballoc *sa){	struct drm_suballoc_manager *sa_manager = sa->manager; 	if (sa_manager->hole == &sa->olist)		sa_manager->hole = sa->olist.prev; 	list_del_init(&sa->olist);	list_del_init(&sa->flist);	dma_fence_put(sa->fence);	kfree(sa);} static void drm_suballoc_try_free(struct drm_suballoc_manager *sa_manager){	struct drm_suballoc *sa, *tmp; 	if (sa_manager->hole->next == &sa_manager->olist)		return; 	sa = list_entry(sa_manager->hole->next, struct drm_suballoc, olist);	list_for_each_entry_safe_from(sa, tmp, &sa_manager->olist, olist) {		if (!sa->fence || !dma_fence_is_signaled(sa->fence))			return; 		drm_suballoc_remove_locked(sa);	}} static size_t drm_suballoc_hole_soffset(struct drm_suballoc_manager *sa_manager){	struct list_head *hole = sa_manager->hole; 	if (hole != &sa_manager->olist)		return list_entry(hole, struct drm_suballoc, olist)->eoffset; 	return 0;} static size_t drm_suballoc_hole_eoffset(struct drm_suballoc_manager *sa_manager){	struct list_head *hole = sa_manager->hole; 	if (hole->next != &sa_manager->olist)		return list_entry(hole->next, struct drm_suballoc, olist)->soffset;	return sa_manager->size;} static bool drm_suballoc_try_alloc(struct drm_suballoc_manager *sa_manager,				   struct drm_suballoc *sa,				   size_t size, size_t align){	size_t soffset, eoffset, wasted; 	soffset = drm_suballoc_hole_soffset(sa_manager);	eoffset = drm_suballoc_hole_eoffset(sa_manager);	wasted = round_up(soffset, align) - soffset; 	if ((eoffset - soffset) >= (size + wasted)) {		soffset += wasted; 		sa->manager = sa_manager;		sa->soffset = soffset;		sa->eoffset = soffset + size;		list_add(&sa->olist, sa_manager->hole);		INIT_LIST_HEAD(&sa->flist);		sa_manager->hole = &sa->olist;		return true;	}	return false;} static bool __drm_suballoc_event(struct drm_suballoc_manager *sa_manager,				 size_t size, size_t align){	size_t soffset, eoffset, wasted;	unsigned int i; 	for (i = 0; i < DRM_SUBALLOC_MAX_QUEUES; ++i)		if (!list_empty(&sa_manager->flist[i]))			return true; 	soffset = drm_suballoc_hole_soffset(sa_manager);	eoffset = drm_suballoc_hole_eoffset(sa_manager);	wasted = round_up(soffset, align) - soffset; 	return ((eoffset - soffset) >= (size + wasted));} /** * drm_suballoc_event() - Check if we can stop waiting * @sa_manager: pointer to the sa_manager * @size: number of bytes we want to allocate * @align: alignment we need to match * * Return: true if either there is a fence we can wait for or * enough free memory to satisfy the allocation directly. * false otherwise. */static bool drm_suballoc_event(struct drm_suballoc_manager *sa_manager,			       size_t size, size_t align){	bool ret; 	spin_lock(&sa_manager->wq.lock);	ret = __drm_suballoc_event(sa_manager, size, align);	spin_unlock(&sa_manager->wq.lock);	return ret;} static bool drm_suballoc_next_hole(struct drm_suballoc_manager *sa_manager,				   struct dma_fence **fences,				   unsigned int *tries){	struct drm_suballoc *best_bo = NULL;	unsigned int i, best_idx;	size_t soffset, best, tmp; 	/* if hole points to the end of the buffer */	if (sa_manager->hole->next == &sa_manager->olist) {		/* try again with its beginning */		sa_manager->hole = &sa_manager->olist;		return true;	} 	soffset = drm_suballoc_hole_soffset(sa_manager);	/* to handle wrap around we add sa_manager->size */	best = sa_manager->size * 2;	/* go over all fence list and try to find the closest sa	 * of the current last	 */	for (i = 0; i < DRM_SUBALLOC_MAX_QUEUES; ++i) {		struct drm_suballoc *sa; 		fences[i] = NULL; 		if (list_empty(&sa_manager->flist[i]))			continue; 		sa = list_first_entry(&sa_manager->flist[i],				      struct drm_suballoc, flist); 		if (!dma_fence_is_signaled(sa->fence)) {			fences[i] = sa->fence;			continue;		} 		/* limit the number of tries each freelist gets */		if (tries[i] > 2)			continue; 		tmp = sa->soffset;		if (tmp < soffset) {			/* wrap around, pretend it's after */			tmp += sa_manager->size;		}		tmp -= soffset;		if (tmp < best) {			/* this sa bo is the closest one */			best = tmp;			best_idx = i;			best_bo = sa;		}	} 	if (best_bo) {		++tries[best_idx];		sa_manager->hole = best_bo->olist.prev; 		/*		 * We know that this one is signaled,		 * so it's safe to remove it.		 */		drm_suballoc_remove_locked(best_bo);		return true;	}	return false;} /** * drm_suballoc_new() - Make a suballocation. * @sa_manager: pointer to the sa_manager * @size: number of bytes we want to suballocate. * @gfp: gfp flags used for memory allocation. Typically GFP_KERNEL but *       the argument is provided for suballocations from reclaim context or *       where the caller wants to avoid pipelining rather than wait for *       reclaim. * @intr: Whether to perform waits interruptible. This should typically *        always be true, unless the caller needs to propagate a *        non-interruptible context from above layers. * @align: Alignment. Must not exceed the default manager alignment. *         If @align is zero, then the manager alignment is used. * * Try to make a suballocation of size @size, which will be rounded * up to the alignment specified in specified in drm_suballoc_manager_init(). * * Return: a new suballocated bo, or an ERR_PTR. */struct drm_suballoc *drm_suballoc_new(struct drm_suballoc_manager *sa_manager, size_t size,		 gfp_t gfp, bool intr, size_t align){	struct dma_fence *fences[DRM_SUBALLOC_MAX_QUEUES];	unsigned int tries[DRM_SUBALLOC_MAX_QUEUES];	unsigned int count;	int i, r;	struct drm_suballoc *sa; 	if (WARN_ON_ONCE(align > sa_manager->align))		return ERR_PTR(-EINVAL);	if (WARN_ON_ONCE(size > sa_manager->size || !size))		return ERR_PTR(-EINVAL); 	if (!align)		align = sa_manager->align; 	sa = kmalloc(sizeof(*sa), gfp);	if (!sa)		return ERR_PTR(-ENOMEM);	sa->manager = sa_manager;	sa->fence = NULL;	INIT_LIST_HEAD(&sa->olist);	INIT_LIST_HEAD(&sa->flist); 	spin_lock(&sa_manager->wq.lock);	do {		for (i = 0; i < DRM_SUBALLOC_MAX_QUEUES; ++i)			tries[i] = 0; 		do {			drm_suballoc_try_free(sa_manager); 			if (drm_suballoc_try_alloc(sa_manager, sa,						   size, align)) {				spin_unlock(&sa_manager->wq.lock);				return sa;			} 			/* see if we can skip over some allocations */		} while (drm_suballoc_next_hole(sa_manager, fences, tries)); 		for (i = 0, count = 0; i < DRM_SUBALLOC_MAX_QUEUES; ++i)			if (fences[i])				fences[count++] = dma_fence_get(fences[i]); 		if (count) {			long t; 			spin_unlock(&sa_manager->wq.lock);			t = dma_fence_wait_any_timeout(fences, count, intr,						       MAX_SCHEDULE_TIMEOUT,						       NULL);			for (i = 0; i < count; ++i)				dma_fence_put(fences[i]); 			r = (t > 0) ? 0 : t;			spin_lock(&sa_manager->wq.lock);		} else if (intr) {			/* if we have nothing to wait for block */			r = wait_event_interruptible_locked				(sa_manager->wq,				 __drm_suballoc_event(sa_manager, size, align));		} else {			spin_unlock(&sa_manager->wq.lock);			wait_event(sa_manager->wq,				   drm_suballoc_event(sa_manager, size, align));			r = 0;			spin_lock(&sa_manager->wq.lock);		}	} while (!r); 	spin_unlock(&sa_manager->wq.lock);	kfree(sa);	return ERR_PTR(r);}EXPORT_SYMBOL(drm_suballoc_new); /** * drm_suballoc_free - Free a suballocation * @suballoc: pointer to the suballocation * @fence: fence that signals when suballocation is idle * * Free the suballocation. The suballocation can be re-used after @fence signals. */void drm_suballoc_free(struct drm_suballoc *suballoc,		       struct dma_fence *fence){	struct drm_suballoc_manager *sa_manager; 	if (!suballoc)		return; 	sa_manager = suballoc->manager; 	spin_lock(&sa_manager->wq.lock);	if (fence && !dma_fence_is_signaled(fence)) {		u32 idx; 		suballoc->fence = dma_fence_get(fence);		idx = fence->context & (DRM_SUBALLOC_MAX_QUEUES - 1);		list_add_tail(&suballoc->flist, &sa_manager->flist[idx]);	} else {		drm_suballoc_remove_locked(suballoc);	}	wake_up_all_locked(&sa_manager->wq);	spin_unlock(&sa_manager->wq.lock);}EXPORT_SYMBOL(drm_suballoc_free); #ifdef CONFIG_DEBUG_FSvoid drm_suballoc_dump_debug_info(struct drm_suballoc_manager *sa_manager,				  struct drm_printer *p,				  unsigned long long suballoc_base){	struct drm_suballoc *i; 	spin_lock(&sa_manager->wq.lock);	list_for_each_entry(i, &sa_manager->olist, olist) {		unsigned long long soffset = i->soffset;		unsigned long long eoffset = i->eoffset; 		if (&i->olist == sa_manager->hole)			drm_puts(p, ">");		else			drm_puts(p, " "); 		drm_printf(p, "[0x%010llx 0x%010llx] size %8lld",			   suballoc_base + soffset, suballoc_base + eoffset,			   eoffset - soffset); 		if (i->fence)			drm_printf(p, " protected by 0x%016llx on context %llu",				   (unsigned long long)i->fence->seqno,				   (unsigned long long)i->fence->context); 		drm_puts(p, "\n");	}	spin_unlock(&sa_manager->wq.lock);}EXPORT_SYMBOL(drm_suballoc_dump_debug_info);#endifMODULE_AUTHOR("Multiple");MODULE_DESCRIPTION("Range suballocator helper");MODULE_LICENSE("Dual MIT/GPL");