// SPDX-License-Identifier: GPL-2.0 OR MIT
/*
 * Copyright 2022 Advanced Micro Devices, Inc.
 *
 * 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, sublicense,
 * 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 above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * 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 NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE COPYRIGHT HOLDER(S) OR AUTHOR(S) 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.
 */

#include <drm/drm_drv.h>

#include "amdgpu.h"
#include "amdgpu_trace.h"
#include "amdgpu_vm.h"
#include "amdgpu_job.h"

/*
 * amdgpu_vm_pt_cursor - state for for_each_amdgpu_vm_pt
 */
struct amdgpu_vm_pt_cursor {
	uint64_t pfn;
	struct amdgpu_vm_bo_base *parent;
	struct amdgpu_vm_bo_base *entry;
	unsigned int level;
};

/**
 * amdgpu_vm_pt_level_shift - return the addr shift for each level
 *
 * @adev: amdgpu_device pointer
 * @level: VMPT level
 *
 * Returns:
 * The number of bits the pfn needs to be right shifted for a level.
 */
static unsigned int amdgpu_vm_pt_level_shift(struct amdgpu_device *adev,
					     unsigned int level)
{
	switch (level) {
	case AMDGPU_VM_PDB3:
	case AMDGPU_VM_PDB2:
	case AMDGPU_VM_PDB1:
	case AMDGPU_VM_PDB0:
		return 9 * (AMDGPU_VM_PDB0 - level) +
			adev->vm_manager.block_size;
	case AMDGPU_VM_PTB:
		return 0;
	default:
		return ~0;
	}
}

/**
 * amdgpu_vm_pt_num_entries - return the number of entries in a PD/PT
 *
 * @adev: amdgpu_device pointer
 * @level: VMPT level
 *
 * Returns:
 * The number of entries in a page directory or page table.
 */
static unsigned int amdgpu_vm_pt_num_entries(struct amdgpu_device *adev,
					     unsigned int level)
{
	unsigned int shift;

	shift = amdgpu_vm_pt_level_shift(adev, adev->vm_manager.root_level);
	if (level == adev->vm_manager.root_level)
		/* For the root directory */
		return round_up(adev->vm_manager.max_pfn, 1ULL << shift)
			>> shift;
	else if (level != AMDGPU_VM_PTB)
		/* Everything in between */
		return 512;

	/* For the page tables on the leaves */
	return AMDGPU_VM_PTE_COUNT(adev);
}

/**
 * amdgpu_vm_pt_entries_mask - the mask to get the entry number of a PD/PT
 *
 * @adev: amdgpu_device pointer
 * @level: VMPT level
 *
 * Returns:
 * The mask to extract the entry number of a PD/PT from an address.
 */
static uint32_t amdgpu_vm_pt_entries_mask(struct amdgpu_device *adev,
					  unsigned int level)
{
	if (level <= adev->vm_manager.root_level)
		return 0xffffffff;
	else if (level != AMDGPU_VM_PTB)
		return 0x1ff;
	else
		return AMDGPU_VM_PTE_COUNT(adev) - 1;
}

/**
 * amdgpu_vm_pt_size - returns the size of the page table in bytes
 *
 * @adev: amdgpu_device pointer
 * @level: VMPT level
 *
 * Returns:
 * The size of the BO for a page directory or page table in bytes.
 */
static unsigned int amdgpu_vm_pt_size(struct amdgpu_device *adev,
				      unsigned int level)
{
	return AMDGPU_GPU_PAGE_ALIGN(amdgpu_vm_pt_num_entries(adev, level) * 8);
}

/**
 * amdgpu_vm_pt_parent - get the parent page directory
 *
 * @pt: child page table
 *
 * Helper to get the parent entry for the child page table. NULL if we are at
 * the root page directory.
 */
static struct amdgpu_vm_bo_base *
amdgpu_vm_pt_parent(struct amdgpu_vm_bo_base *pt)
{
	struct amdgpu_bo *parent = pt->bo->parent;

	if (!parent)
		return NULL;

	return parent->vm_bo;
}

/**
 * amdgpu_vm_pt_start - start PD/PT walk
 *
 * @adev: amdgpu_device pointer
 * @vm: amdgpu_vm structure
 * @start: start address of the walk
 * @cursor: state to initialize
 *
 * Initialize a amdgpu_vm_pt_cursor to start a walk.
 */
static void amdgpu_vm_pt_start(struct amdgpu_device *adev,
			       struct amdgpu_vm *vm, uint64_t start,
			       struct amdgpu_vm_pt_cursor *cursor)
{
	cursor->pfn = start;
	cursor->parent = NULL;
	cursor->entry = &vm->root;
	cursor->level = adev->vm_manager.root_level;
}

/**
 * amdgpu_vm_pt_descendant - go to child node
 *
 * @adev: amdgpu_device pointer
 * @cursor: current state
 *
 * Walk to the child node of the current node.
 * Returns:
 * True if the walk was possible, false otherwise.
 */
static bool amdgpu_vm_pt_descendant(struct amdgpu_device *adev,
				    struct amdgpu_vm_pt_cursor *cursor)
{
	unsigned int mask, shift, idx;

	if ((cursor->level == AMDGPU_VM_PTB) || !cursor->entry ||
	    !cursor->entry->bo)
		return false;

	mask = amdgpu_vm_pt_entries_mask(adev, cursor->level);
	shift = amdgpu_vm_pt_level_shift(adev, cursor->level);

	++cursor->level;
	idx = (cursor->pfn >> shift) & mask;
	cursor->parent = cursor->entry;
	cursor->entry = &to_amdgpu_bo_vm(cursor->entry->bo)->entries[idx];
	return true;
}

/**
 * amdgpu_vm_pt_sibling - go to sibling node
 *
 * @adev: amdgpu_device pointer
 * @cursor: current state
 *
 * Walk to the sibling node of the current node.
 * Returns:
 * True if the walk was possible, false otherwise.
 */
static bool amdgpu_vm_pt_sibling(struct amdgpu_device *adev,
				 struct amdgpu_vm_pt_cursor *cursor)
{

	unsigned int shift, num_entries;
	struct amdgpu_bo_vm *parent;

	/* Root doesn't have a sibling */
	if (!cursor->parent)
		return false;

	/* Go to our parents and see if we got a sibling */
	shift = amdgpu_vm_pt_level_shift(adev, cursor->level - 1);
	num_entries = amdgpu_vm_pt_num_entries(adev, cursor->level - 1);
	parent = to_amdgpu_bo_vm(cursor->parent->bo);

	if (cursor->entry == &parent->entries[num_entries - 1])
		return false;

	cursor->pfn += 1ULL << shift;
	cursor->pfn &= ~((1ULL << shift) - 1);
	++cursor->entry;
	return true;
}

/**
 * amdgpu_vm_pt_ancestor - go to parent node
 *
 * @cursor: current state
 *
 * Walk to the parent node of the current node.
 * Returns:
 * True if the walk was possible, false otherwise.
 */
static bool amdgpu_vm_pt_ancestor(struct amdgpu_vm_pt_cursor *cursor)
{
	if (!cursor->parent)
		return false;

	--cursor->level;
	cursor->entry = cursor->parent;
	cursor->parent = amdgpu_vm_pt_parent(cursor->parent);
	return true;
}

/**
 * amdgpu_vm_pt_next - get next PD/PT in hieratchy
 *
 * @adev: amdgpu_device pointer
 * @cursor: current state
 *
 * Walk the PD/PT tree to the next node.
 */
static void amdgpu_vm_pt_next(struct amdgpu_device *adev,
			      struct amdgpu_vm_pt_cursor *cursor)
{
	/* First try a newborn child */
	if (amdgpu_vm_pt_descendant(adev, cursor))
		return;

	/* If that didn't worked try to find a sibling */
	while (!amdgpu_vm_pt_sibling(adev, cursor)) {
		/* No sibling, go to our parents and grandparents */
		if (!amdgpu_vm_pt_ancestor(cursor)) {
			cursor->pfn = ~0ll;
			return;
		}
	}
}

/**
 * amdgpu_vm_pt_first_dfs - start a deep first search
 *
 * @adev: amdgpu_device structure
 * @vm: amdgpu_vm structure
 * @start: optional cursor to start with
 * @cursor: state to initialize
 *
 * Starts a deep first traversal of the PD/PT tree.
 */
static void amdgpu_vm_pt_first_dfs(struct amdgpu_device *adev,
				   struct amdgpu_vm *vm,
				   struct amdgpu_vm_pt_cursor *start,
				   struct amdgpu_vm_pt_cursor *cursor)
{
	if (start)
		*cursor = *start;
	else
		amdgpu_vm_pt_start(adev, vm, 0, cursor);

	while (amdgpu_vm_pt_descendant(adev, cursor))
		;
}

/**
 * amdgpu_vm_pt_continue_dfs - check if the deep first search should continue
 *
 * @start: starting point for the search
 * @entry: current entry
 *
 * Returns:
 * True when the search should continue, false otherwise.
 */
static bool amdgpu_vm_pt_continue_dfs(struct amdgpu_vm_pt_cursor *start,
				      struct amdgpu_vm_bo_base *entry)
{
	return entry && (!start || entry != start->entry);
}

/**
 * amdgpu_vm_pt_next_dfs - get the next node for a deep first search
 *
 * @adev: amdgpu_device structure
 * @cursor: current state
 *
 * Move the cursor to the next node in a deep first search.
 */
static void amdgpu_vm_pt_next_dfs(struct amdgpu_device *adev,
				  struct amdgpu_vm_pt_cursor *cursor)
{
	if (!cursor->entry)
		return;

	if (!cursor->parent)
		cursor->entry = NULL;
	else if (amdgpu_vm_pt_sibling(adev, cursor))
		while (amdgpu_vm_pt_descendant(adev, cursor))
			;
	else
		amdgpu_vm_pt_ancestor(cursor);
}

/*
 * for_each_amdgpu_vm_pt_dfs_safe - safe deep first search of all PDs/PTs
 */
#define for_each_amdgpu_vm_pt_dfs_safe(adev, vm, start, cursor, entry)		\
	for (amdgpu_vm_pt_first_dfs((adev), (vm), (start), &(cursor)),		\
	     (entry) = (cursor).entry, amdgpu_vm_pt_next_dfs((adev), &(cursor));\
	     amdgpu_vm_pt_continue_dfs((start), (entry));			\
	     (entry) = (cursor).entry, amdgpu_vm_pt_next_dfs((adev), &(cursor)))

/**
 * amdgpu_vm_pt_clear - initially clear the PDs/PTs
 *
 * @adev: amdgpu_device pointer
 * @vm: VM to clear BO from
 * @vmbo: BO to clear
 * @immediate: use an immediate update
 *
 * Root PD needs to be reserved when calling this.
 *
 * Returns:
 * 0 on success, errno otherwise.
 */
int amdgpu_vm_pt_clear(struct amdgpu_device *adev, struct amdgpu_vm *vm,
		       struct amdgpu_bo_vm *vmbo, bool immediate)
{
	unsigned int level = adev->vm_manager.root_level;
	struct ttm_operation_ctx ctx = { true, false };
	struct amdgpu_vm_update_params params;
	struct amdgpu_bo *ancestor = &vmbo->bo;
	unsigned int entries;
	struct amdgpu_bo *bo = &vmbo->bo;
	uint64_t value = 0, flags = 0;
	uint64_t addr;
	int r, idx;

	/* Figure out our place in the hierarchy */
	if (ancestor->parent) {
		++level;
		while (ancestor->parent->parent) {
			++level;
			ancestor = ancestor->parent;
		}
	}

	entries = amdgpu_bo_size(bo) / 8;

	r = ttm_bo_validate(&bo->tbo, &bo->placement, &ctx);
	if (r)
		return r;

	if (!drm_dev_enter(adev_to_drm(adev), &idx))
		return -ENODEV;

	r = vm->update_funcs->map_table(vmbo);
	if (r)
		goto exit;

	memset(&params, 0, sizeof(params));
	params.adev = adev;
	params.vm = vm;
	params.immediate = immediate;

	r = vm->update_funcs->prepare(&params, NULL,
				      AMDGPU_KERNEL_JOB_ID_VM_PT_CLEAR);
	if (r)
		goto exit;

	addr = 0;

	if (adev->asic_type >= CHIP_VEGA10) {
		if (level != AMDGPU_VM_PTB) {
			/* Handle leaf PDEs as PTEs */
			flags |= AMDGPU_PDE_PTE_FLAG(adev);
			amdgpu_gmc_get_vm_pde(adev, level,
					      &value, &flags);
		} else {
			/* Workaround for fault priority problem on GMC9 */
			flags = AMDGPU_PTE_EXECUTABLE | adev->gmc.init_pte_flags;
		}
	}

	r = vm->update_funcs->update(&params, vmbo, addr, 0, entries,
				     value, flags);
	if (r)
		goto exit;

	r = vm->update_funcs->commit(&params, NULL);
exit:
	drm_dev_exit(idx);
	return r;
}

/**
 * amdgpu_vm_pt_create - create bo for PD/PT
 *
 * @adev: amdgpu_device pointer
 * @vm: requesting vm
 * @level: the page table level
 * @immediate: use a immediate update
 * @vmbo: pointer to the buffer object pointer
 * @xcp_id: GPU partition id
 */
int amdgpu_vm_pt_create(struct amdgpu_device *adev, struct amdgpu_vm *vm,
			int level, bool immediate, struct amdgpu_bo_vm **vmbo,
			int32_t xcp_id)
{
	struct amdgpu_bo_param bp;
	unsigned int num_entries;

	memset(&bp, 0, sizeof(bp));

	bp.size = amdgpu_vm_pt_size(adev, level);
	bp.byte_align = AMDGPU_GPU_PAGE_SIZE;

	if (!adev->gmc.is_app_apu)
		bp.domain = AMDGPU_GEM_DOMAIN_VRAM;
	else
		bp.domain = AMDGPU_GEM_DOMAIN_GTT;

	bp.domain = amdgpu_bo_get_preferred_domain(adev, bp.domain);
	bp.flags = AMDGPU_GEM_CREATE_VRAM_CONTIGUOUS |
		AMDGPU_GEM_CREATE_CPU_GTT_USWC;

	if (level < AMDGPU_VM_PTB)
		num_entries = amdgpu_vm_pt_num_entries(adev, level);
	else
		num_entries = 0;

	bp.bo_ptr_size = struct_size((*vmbo), entries, num_entries);

	if (vm->use_cpu_for_update)
		bp.flags |= AMDGPU_GEM_CREATE_CPU_ACCESS_REQUIRED;

	bp.type = ttm_bo_type_kernel;
	bp.no_wait_gpu = immediate;
	bp.xcp_id_plus1 = xcp_id + 1;

	if (vm->root.bo)
		bp.resv = vm->root.bo->tbo.base.resv;

	return amdgpu_bo_create_vm(adev, &bp, vmbo);
}

/**
 * amdgpu_vm_pt_alloc - Allocate a specific page table
 *
 * @adev: amdgpu_device pointer
 * @vm: VM to allocate page tables for
 * @cursor: Which page table to allocate
 * @immediate: use an immediate update
 *
 * Make sure a specific page table or directory is allocated.
 *
 * Returns:
 * 1 if page table needed to be allocated, 0 if page table was already
 * allocated, negative errno if an error occurred.
 */
static int amdgpu_vm_pt_alloc(struct amdgpu_device *adev,
			      struct amdgpu_vm *vm,
			      struct amdgpu_vm_pt_cursor *cursor,
			      bool immediate)
{
	struct amdgpu_vm_bo_base *entry = cursor->entry;
	struct amdgpu_bo *pt_bo;
	struct amdgpu_bo_vm *pt;
	int r;

	if (entry->bo)
		return 0;

	amdgpu_vm_eviction_unlock(vm);
	r = amdgpu_vm_pt_create(adev, vm, cursor->level, immediate, &pt,
				vm->root.bo->xcp_id);
	amdgpu_vm_eviction_lock(vm);
	if (r)
		return r;

	/* Keep a reference to the root directory to avoid
	 * freeing them up in the wrong order.
	 */
	pt_bo = &pt->bo;
	pt_bo->parent = amdgpu_bo_ref(cursor->parent->bo);
	amdgpu_vm_bo_base_init(entry, vm, pt_bo);
	r = amdgpu_vm_pt_clear(adev, vm, pt, immediate);
	if (r)
		goto error_free_pt;

	return 0;

error_free_pt:
	amdgpu_bo_unref(&pt_bo);
	return r;
}

/**
 * amdgpu_vm_pt_free - free one PD/PT
 *
 * @entry: PDE to free
 */
static void amdgpu_vm_pt_free(struct amdgpu_vm_bo_base *entry)
{
	if (!entry->bo)
		return;

	amdgpu_vm_update_stats(entry, entry->bo->tbo.resource, -1);
	entry->bo->vm_bo = NULL;
	ttm_bo_set_bulk_move(&entry->bo->tbo, NULL);

	list_del(&entry->vm_status);
	amdgpu_bo_unref(&entry->bo);
}

/**
 * amdgpu_vm_pt_free_list - free PD/PT levels
 *
 * @adev: amdgpu device structure
 * @params: see amdgpu_vm_update_params definition
 *
 * Free the page directory objects saved in the flush list
 */
void amdgpu_vm_pt_free_list(struct amdgpu_device *adev,
			    struct amdgpu_vm_update_params *params)
{
	struct amdgpu_vm_bo_base *entry, *next;
	bool unlocked = params->unlocked;

	if (list_empty(&params->tlb_flush_waitlist))
		return;

	/*
	 * unlocked unmap clear page table leaves, warning to free the page entry.
	 */
	WARN_ON(unlocked);

	list_for_each_entry_safe(entry, next, &params->tlb_flush_waitlist, vm_status)
		amdgpu_vm_pt_free(entry);
}

/**
 * amdgpu_vm_pt_add_list - add PD/PT level to the flush list
 *
 * @params: parameters for the update
 * @cursor: first PT entry to start DF search from, non NULL
 *
 * This list will be freed after TLB flush.
 */
static void amdgpu_vm_pt_add_list(struct amdgpu_vm_update_params *params,
				  struct amdgpu_vm_pt_cursor *cursor)
{
	struct amdgpu_vm_pt_cursor seek;
	struct amdgpu_vm_bo_base *entry;

	for_each_amdgpu_vm_pt_dfs_safe(params->adev, params->vm, cursor, seek, entry) {
		if (entry && entry->bo)
			list_move(&entry->vm_status, &params->tlb_flush_waitlist);
	}

	/* enter start node now */
	list_move(&cursor->entry->vm_status, &params->tlb_flush_waitlist);
}

/**
 * amdgpu_vm_pt_free_root - free root PD
 * @adev: amdgpu device structure
 * @vm: amdgpu vm structure
 *
 * Free the root page directory and everything below it.
 */
void amdgpu_vm_pt_free_root(struct amdgpu_device *adev, struct amdgpu_vm *vm)
{
	struct amdgpu_vm_pt_cursor cursor;
	struct amdgpu_vm_bo_base *entry;

	for_each_amdgpu_vm_pt_dfs_safe(adev, vm, NULL, cursor, entry) {
		if (entry)
			amdgpu_vm_pt_free(entry);
	}
}

/**
 * amdgpu_vm_pde_update - update a single level in the hierarchy
 *
 * @params: parameters for the update
 * @entry: entry to update
 *
 * Makes sure the requested entry in parent is up to date.
 */
int amdgpu_vm_pde_update(struct amdgpu_vm_update_params *params,
			 struct amdgpu_vm_bo_base *entry)
{
	struct amdgpu_vm_bo_base *parent = amdgpu_vm_pt_parent(entry);
	struct amdgpu_bo *bo, *pbo;
	struct amdgpu_vm *vm = params->vm;
	uint64_t pde, pt, flags;
	unsigned int level;

	if (WARN_ON(!parent))
		return -EINVAL;

	bo = parent->bo;
	for (level = 0, pbo = bo->parent; pbo; ++level)
		pbo = pbo->parent;

	level += params->adev->vm_manager.root_level;
	amdgpu_gmc_get_pde_for_bo(entry->bo, level, &pt, &flags);
	pde = (entry - to_amdgpu_bo_vm(parent->bo)->entries) * 8;
	return vm->update_funcs->update(params, to_amdgpu_bo_vm(bo), pde, pt,
					1, 0, flags);
}

/**
 * amdgpu_vm_pte_update_noretry_flags - Update PTE no-retry flags
 *
 * @adev: amdgpu_device pointer
 * @flags: pointer to PTE flags
 *
 * Update PTE no-retry flags when TF is enabled.
 */
static void amdgpu_vm_pte_update_noretry_flags(struct amdgpu_device *adev,
						uint64_t *flags)
{
	/*
	 * Update no-retry flags with the corresponding TF
	 * no-retry combination.
	 */
	if ((*flags & AMDGPU_VM_NORETRY_FLAGS) == AMDGPU_VM_NORETRY_FLAGS) {
		*flags &= ~AMDGPU_VM_NORETRY_FLAGS;
		*flags |= adev->gmc.noretry_flags;
	}
}

/*
 * amdgpu_vm_pte_update_flags - figure out flags for PTE updates
 *
 * Make sure to set the right flags for the PTEs at the desired level.
 */
static void amdgpu_vm_pte_update_flags(struct amdgpu_vm_update_params *params,
				       struct amdgpu_bo_vm *pt,
				       unsigned int level,
				       uint64_t pe, uint64_t addr,
				       unsigned int count, uint32_t incr,
				       uint64_t flags)
{
	struct amdgpu_device *adev = params->adev;

	if (level != AMDGPU_VM_PTB) {
		flags |= AMDGPU_PDE_PTE_FLAG(params->adev);
		amdgpu_gmc_get_vm_pde(adev, level, &addr, &flags);

	} else if (adev->asic_type >= CHIP_VEGA10 &&
		   !(flags & AMDGPU_PTE_VALID) &&
		   !(flags & AMDGPU_PTE_PRT_FLAG(params->adev))) {

		/* Workaround for fault priority problem on GMC9 and GFX12,
		 * EXECUTABLE for GMC9 fault priority and init_pte_flags
		 * (e.g. AMDGPU_PTE_IS_PTE on GFX12)
		 */
		flags |= AMDGPU_PTE_EXECUTABLE | adev->gmc.init_pte_flags;
	}

	/*
	 * Update no-retry flags to use the no-retry flag combination
	 * with TF enabled. The AMDGPU_VM_NORETRY_FLAGS flag combination
	 * does not work when TF is enabled. So, replace them with
	 * AMDGPU_VM_NORETRY_FLAGS_TF flag combination which works for
	 * all cases.
	 */
	if (level == AMDGPU_VM_PTB)
		amdgpu_vm_pte_update_noretry_flags(adev, &flags);

	params->vm->update_funcs->update(params, pt, pe, addr, count, incr,
					 flags);
}

/**
 * amdgpu_vm_pte_fragment - get fragment for PTEs
 *
 * @params: see amdgpu_vm_update_params definition
 * @start: first PTE to handle
 * @end: last PTE to handle
 * @flags: hw mapping flags
 * @frag: resulting fragment size
 * @frag_end: end of this fragment
 *
 * Returns the first possible fragment for the start and end address.
 */
static void amdgpu_vm_pte_fragment(struct amdgpu_vm_update_params *params,
				   uint64_t start, uint64_t end, uint64_t flags,
				   unsigned int *frag, uint64_t *frag_end)
{
	/**
	 * The MC L1 TLB supports variable sized pages, based on a fragment
	 * field in the PTE. When this field is set to a non-zero value, page
	 * granularity is increased from 4KB to (1 << (12 + frag)). The PTE
	 * flags are considered valid for all PTEs within the fragment range
	 * and corresponding mappings are assumed to be physically contiguous.
	 *
	 * The L1 TLB can store a single PTE for the whole fragment,
	 * significantly increasing the space available for translation
	 * caching. This leads to large improvements in throughput when the
	 * TLB is under pressure.
	 *
	 * The L2 TLB distributes small and large fragments into two
	 * asymmetric partitions. The large fragment cache is significantly
	 * larger. Thus, we try to use large fragments wherever possible.
	 * Userspace can support this by aligning virtual base address and
	 * allocation size to the fragment size.
	 *
	 * Starting with Vega10 the fragment size only controls the L1. The L2
	 * is now directly feed with small/huge/giant pages from the walker.
	 */
	unsigned int max_frag;

	if (params->adev->asic_type < CHIP_VEGA10)
		max_frag = params->adev->vm_manager.fragment_size;
	else
		max_frag = 31;

	/* system pages are non continuously */
	if (params->pages_addr) {
		*frag = 0;
		*frag_end = end;
		return;
	}

	/* This intentionally wraps around if no bit is set */
	*frag = min_t(unsigned int, ffs(start) - 1, fls64(end - start) - 1);
	if (*frag >= max_frag) {
		*frag = max_frag;
		*frag_end = end & ~((1ULL << max_frag) - 1);
	} else {
		*frag_end = start + (1 << *frag);
	}
}

/**
 * amdgpu_vm_ptes_update - make sure that page tables are valid
 *
 * @params: see amdgpu_vm_update_params definition
 * @start: start of GPU address range
 * @end: end of GPU address range
 * @dst: destination address to map to, the next dst inside the function
 * @flags: mapping flags
 *
 * Update the page tables in the range @start - @end.
 *
 * Returns:
 * 0 for success, -EINVAL for failure.
 */
int amdgpu_vm_ptes_update(struct amdgpu_vm_update_params *params,
			  uint64_t start, uint64_t end,
			  uint64_t dst, uint64_t flags)
{
	struct amdgpu_device *adev = params->adev;
	struct amdgpu_vm_pt_cursor cursor;
	uint64_t frag_start = start, frag_end;
	unsigned int frag;
	int r;

	/* figure out the initial fragment */
	amdgpu_vm_pte_fragment(params, frag_start, end, flags, &frag,
			       &frag_end);

	/* walk over the address space and update the PTs */
	amdgpu_vm_pt_start(adev, params->vm, start, &cursor);
	while (cursor.pfn < end) {
		unsigned int shift, parent_shift, mask;
		uint64_t incr, entry_end, pe_start;
		struct amdgpu_bo *pt;

		if (!params->unlocked) {
			/* make sure that the page tables covering the
			 * address range are actually allocated
			 */
			r = amdgpu_vm_pt_alloc(params->adev, params->vm,
					       &cursor, params->immediate);
			if (r)
				return r;
		}

		shift = amdgpu_vm_pt_level_shift(adev, cursor.level);
		parent_shift = amdgpu_vm_pt_level_shift(adev, cursor.level - 1);
		if (params->unlocked) {
			/* Unlocked updates are only allowed on the leaves */
			if (amdgpu_vm_pt_descendant(adev, &cursor))
				continue;
		} else if (adev->asic_type < CHIP_VEGA10 &&
			   (flags & AMDGPU_PTE_VALID)) {
			/* No huge page support before GMC v9 */
			if (cursor.level != AMDGPU_VM_PTB) {
				if (!amdgpu_vm_pt_descendant(adev, &cursor))
					return -ENOENT;
				continue;
			}
		} else if (frag < shift) {
			/* We can't use this level when the fragment size is
			 * smaller than the address shift. Go to the next
			 * child entry and try again.
			 */
			if (amdgpu_vm_pt_descendant(adev, &cursor))
				continue;
		} else if (frag >= parent_shift) {
			/* If the fragment size is even larger than the parent
			 * shift we should go up one level and check it again.
			 */
			if (!amdgpu_vm_pt_ancestor(&cursor))
				return -EINVAL;
			continue;
		}

		pt = cursor.entry->bo;
		if (!pt) {
			/* We need all PDs and PTs for mapping something, */
			if (flags & AMDGPU_PTE_VALID)
				return -ENOENT;

			/* but unmapping something can happen at a higher
			 * level.
			 */
			if (!amdgpu_vm_pt_ancestor(&cursor))
				return -EINVAL;

			pt = cursor.entry->bo;
			shift = parent_shift;
			frag_end = max(frag_end, ALIGN(frag_start + 1,
				   1ULL << shift));
		}

		/* Looks good so far, calculate parameters for the update */
		incr = (uint64_t)AMDGPU_GPU_PAGE_SIZE << shift;
		mask = amdgpu_vm_pt_entries_mask(adev, cursor.level);
		pe_start = ((cursor.pfn >> shift) & mask) * 8;

		if (cursor.level < AMDGPU_VM_PTB && params->unlocked)
			/*
			 * MMU notifier callback unlocked unmap huge page, leave is PDE entry,
			 * only clear one entry. Next entry search again for PDE or PTE leave.
			 */
			entry_end = 1ULL << shift;
		else
			entry_end = ((uint64_t)mask + 1) << shift;
		entry_end += cursor.pfn & ~(entry_end - 1);
		entry_end = min(entry_end, end);

		do {
			struct amdgpu_vm *vm = params->vm;
			uint64_t upd_end = min(entry_end, frag_end);
			unsigned int nptes = (upd_end - frag_start) >> shift;
			uint64_t upd_flags = flags | AMDGPU_PTE_FRAG(frag);

			/* This can happen when we set higher level PDs to
			 * silent to stop fault floods.
			 */
			nptes = max(nptes, 1u);

			trace_amdgpu_vm_update_ptes(params, frag_start, upd_end,
						    min(nptes, 32u), dst, incr,
						    upd_flags,
						    vm->task_info ? vm->task_info->tgid : 0,
						    vm->immediate.fence_context);
			amdgpu_vm_pte_update_flags(params, to_amdgpu_bo_vm(pt),
						   cursor.level, pe_start, dst,
						   nptes, incr, upd_flags);

			pe_start += nptes * 8;
			dst += nptes * incr;

			frag_start = upd_end;
			if (frag_start >= frag_end) {
				/* figure out the next fragment */
				amdgpu_vm_pte_fragment(params, frag_start, end,
						       flags, &frag, &frag_end);
				if (frag < shift)
					break;
			}
		} while (frag_start < entry_end);

		if (amdgpu_vm_pt_descendant(adev, &cursor)) {
			/* Free all child entries.
			 * Update the tables with the flags and addresses and free up subsequent
			 * tables in the case of huge pages or freed up areas.
			 * This is the maximum you can free, because all other page tables are not
			 * completely covered by the range and so potentially still in use.
			 */
			while (cursor.pfn < frag_start) {
				/* Make sure previous mapping is freed */
				if (cursor.entry->bo) {
					params->needs_flush = true;
					amdgpu_vm_pt_add_list(params, &cursor);
				}
				amdgpu_vm_pt_next(adev, &cursor);
			}

		} else if (frag >= shift) {
			/* or just move on to the next on the same level. */
			amdgpu_vm_pt_next(adev, &cursor);
		}
	}

	return 0;
}

/**
 * amdgpu_vm_pt_map_tables - have bo of root PD cpu accessible
 * @adev: amdgpu device structure
 * @vm: amdgpu vm structure
 *
 * make root page directory and everything below it cpu accessible.
 */
int amdgpu_vm_pt_map_tables(struct amdgpu_device *adev, struct amdgpu_vm *vm)
{
	struct amdgpu_vm_pt_cursor cursor;
	struct amdgpu_vm_bo_base *entry;

	for_each_amdgpu_vm_pt_dfs_safe(adev, vm, NULL, cursor, entry) {

		struct amdgpu_bo_vm *bo;
		int r;

		if (entry->bo) {
			bo = to_amdgpu_bo_vm(entry->bo);
			r = vm->update_funcs->map_table(bo);
			if (r)
				return r;
		}
	}

	return 0;
}