// 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/export.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_alloc() - Allocate uninitialized suballoc object.
 * @gfp: gfp flags used for memory allocation.
 *
 * Allocate memory for an uninitialized suballoc object. Intended usage is
 * allocate memory for suballoc object outside of a reclaim tainted context
 * and then be initialized at a later time in a reclaim tainted context.
 *
 * @drm_suballoc_free() should be used to release the memory if returned
 * suballoc object is in uninitialized state.
 *
 * Return: a new uninitialized suballoc object, or an ERR_PTR(-ENOMEM).
 */
struct drm_suballoc *drm_suballoc_alloc(gfp_t gfp)
{
	struct drm_suballoc *sa;

	sa = kmalloc_obj(*sa, gfp);
	if (!sa)
		return ERR_PTR(-ENOMEM);

	sa->manager = NULL;

	return sa;
}
EXPORT_SYMBOL(drm_suballoc_alloc);

/**
 * drm_suballoc_insert() - Initialize a suballocation and insert a hole.
 * @sa_manager: pointer to the sa_manager
 * @sa: The struct drm_suballoc.
 * @size: number of bytes we want to suballocate.
 * @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 on a pre-allocated suballoc object of size @size,
 * which will be rounded up to the alignment specified in specified in
 * drm_suballoc_manager_init().
 *
 * Return: zero on success, errno on failure.
 */
int drm_suballoc_insert(struct drm_suballoc_manager *sa_manager,
			struct drm_suballoc *sa, size_t size,
			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;

	if (WARN_ON_ONCE(align > sa_manager->align))
		return -EINVAL;
	if (WARN_ON_ONCE(size > sa_manager->size || !size))
		return -EINVAL;

	if (!align)
		align = sa_manager->align;

	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 0;
			}

			/* 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);
	sa->manager = NULL;
	return r;
}
EXPORT_SYMBOL(drm_suballoc_insert);

/**
 * 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 drm_suballoc *sa;
	int err;

	sa = drm_suballoc_alloc(gfp);
	if (IS_ERR(sa))
		return sa;

	err = drm_suballoc_insert(sa_manager, sa, size, intr, align);
	if (err) {
		drm_suballoc_free(sa, NULL);
		return ERR_PTR(err);
	}

	return sa;
}
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;

	if (!suballoc->manager) {
		kfree(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_FS
void 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);
#endif
MODULE_AUTHOR("Multiple");
MODULE_DESCRIPTION("Range suballocator helper");
MODULE_LICENSE("Dual MIT/GPL");