/*
 * Copyright (c) 2016-2018, NVIDIA 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, 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 AUTHORS OR COPYRIGHT HOLDERS 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.
 */

#ifndef NVGPU_MM_BUDDY_ALLOCATOR_PRIV_H
#define NVGPU_MM_BUDDY_ALLOCATOR_PRIV_H

#include <nvgpu/rbtree.h>
#include <nvgpu/list.h>

struct nvgpu_kmem_cache;
struct nvgpu_allocator;
struct vm_gk20a;

/*
 * Each buddy is an element in a binary tree.
 */
struct nvgpu_buddy {
	struct nvgpu_buddy *parent;	/* Parent node. */
	struct nvgpu_buddy *buddy;	/* This node's buddy. */
	struct nvgpu_buddy *left;	/* Lower address sub-node. */
	struct nvgpu_buddy *right;	/* Higher address sub-node. */

	struct nvgpu_list_node buddy_entry;	/* List entry for various lists. */
	struct nvgpu_rbtree_node alloced_entry;	/* RB tree of allocations. */

	u64 start;			/* Start address of this buddy. */
	u64 end;			/* End address of this buddy. */
	u64 order;			/* Buddy order. */

#define BALLOC_BUDDY_ALLOCED	0x1U
#define BALLOC_BUDDY_SPLIT	0x2U
#define BALLOC_BUDDY_IN_LIST	0x4U
	u32 flags;			/* List of associated flags. */

	/*
	 * Size of the PDE this buddy is using. This allows for grouping like
	 * sized allocations into the same PDE.
	 */
#define BALLOC_PTE_SIZE_ANY	(~0U)
#define BALLOC_PTE_SIZE_INVALID	0U
#define BALLOC_PTE_SIZE_SMALL	1U
#define BALLOC_PTE_SIZE_BIG	2U
	u32 pte_size;
};

static inline struct nvgpu_buddy *
nvgpu_buddy_from_buddy_entry(struct nvgpu_list_node *node)
{
	return (struct nvgpu_buddy *)
		((uintptr_t)node - offsetof(struct nvgpu_buddy, buddy_entry));
};

static inline struct nvgpu_buddy *
nvgpu_buddy_from_rbtree_node(struct nvgpu_rbtree_node *node)
{
	return (struct nvgpu_buddy *)
		((uintptr_t)node - offsetof(struct nvgpu_buddy, alloced_entry));
};

#define __buddy_flag_ops(flag, flag_up)					\
	static inline int buddy_is_ ## flag(struct nvgpu_buddy *b)	\
	{								\
		return b->flags & BALLOC_BUDDY_ ## flag_up;		\
	}								\
	static inline void buddy_set_ ## flag(struct nvgpu_buddy *b)	\
	{								\
		b->flags |= BALLOC_BUDDY_ ## flag_up;			\
	}								\
	static inline void buddy_clr_ ## flag(struct nvgpu_buddy *b)	\
	{								\
		b->flags &= ~BALLOC_BUDDY_ ## flag_up;			\
	}

/*
 * int  buddy_is_alloced(struct nvgpu_buddy *b);
 * void buddy_set_alloced(struct nvgpu_buddy *b);
 * void buddy_clr_alloced(struct nvgpu_buddy *b);
 *
 * int  buddy_is_split(struct nvgpu_buddy *b);
 * void buddy_set_split(struct nvgpu_buddy *b);
 * void buddy_clr_split(struct nvgpu_buddy *b);
 *
 * int  buddy_is_in_list(struct nvgpu_buddy *b);
 * void buddy_set_in_list(struct nvgpu_buddy *b);
 * void buddy_clr_in_list(struct nvgpu_buddy *b);
 */
__buddy_flag_ops(alloced, ALLOCED);
__buddy_flag_ops(split,   SPLIT);
__buddy_flag_ops(in_list, IN_LIST);

/*
 * Keeps info for a fixed allocation.
 */
struct nvgpu_fixed_alloc {
	struct nvgpu_list_node buddies;	/* List of buddies. */
	struct nvgpu_rbtree_node alloced_entry;	/* RB tree of fixed allocations. */

	u64 start;			/* Start of fixed block. */
	u64 end;			/* End address. */
};

static inline struct nvgpu_fixed_alloc *
nvgpu_fixed_alloc_from_rbtree_node(struct nvgpu_rbtree_node *node)
{
	return (struct nvgpu_fixed_alloc *)
	((uintptr_t)node - offsetof(struct nvgpu_fixed_alloc, alloced_entry));
};

/*
 * GPU buddy allocator for the various GPU address spaces. Each addressable unit
 * doesn't have to correspond to a byte. In some cases each unit is a more
 * complex object such as a comp_tag line or the like.
 *
 * The max order is computed based on the size of the minimum order and the size
 * of the address space.
 *
 * order_size is the size of an order 0 buddy.
 */
struct nvgpu_buddy_allocator {
	struct nvgpu_allocator *owner;	/* Owner of this buddy allocator. */
	struct vm_gk20a *vm;		/* Parent VM - can be NULL. */

	u64 base;			/* Base address of the space. */
	u64 length;			/* Length of the space. */
	u64 blk_size;			/* Size of order 0 allocation. */
	u64 blk_shift;			/* Shift to divide by blk_size. */

	/* Internal stuff. */
	u64 start;			/* Real start (aligned to blk_size). */
	u64 end;			/* Real end, trimmed if needed. */
	u64 count;			/* Count of objects in space. */
	u64 blks;			/* Count of blks in the space. */
	u64 max_order;			/* Specific maximum order. */

	struct nvgpu_rbtree_node *alloced_buddies;	/* Outstanding allocations. */
	struct nvgpu_rbtree_node *fixed_allocs;	/* Outstanding fixed allocations. */

	struct nvgpu_list_node co_list;

	struct nvgpu_kmem_cache *buddy_cache;

	/*
	 * Impose an upper bound on the maximum order.
	 */
#define GPU_BALLOC_ORDER_LIST_LEN	(GPU_BALLOC_MAX_ORDER + 1U)

	struct nvgpu_list_node buddy_list[GPU_BALLOC_ORDER_LIST_LEN];
	u64 buddy_list_len[GPU_BALLOC_ORDER_LIST_LEN];
	u64 buddy_list_split[GPU_BALLOC_ORDER_LIST_LEN];
	u64 buddy_list_alloced[GPU_BALLOC_ORDER_LIST_LEN];

	/*
	 * This is for when the allocator is managing a GVA space (the
	 * GPU_ALLOC_GVA_SPACE bit is set in @flags). This requires
	 * that we group like sized allocations into PDE blocks.
	 */
	u64 pte_blk_order;

	bool initialized;
	bool alloc_made;		/* True after the first alloc. */

	u64 flags;

	u64 bytes_alloced;
	u64 bytes_alloced_real;
	u64 bytes_freed;
};

static inline struct nvgpu_buddy_allocator *buddy_allocator(
	struct nvgpu_allocator *a)
{
	return (struct nvgpu_buddy_allocator *)(a)->priv;
}

static inline struct nvgpu_list_node *balloc_get_order_list(
	struct nvgpu_buddy_allocator *a, u64 order)
{
	return &a->buddy_list[order];
}

static inline u64 balloc_order_to_len(struct nvgpu_buddy_allocator *a,
				      int order)
{
	return (1 << order) * a->blk_size;
}

static inline u64 balloc_base_shift(struct nvgpu_buddy_allocator *a,
				    u64 base)
{
	return base - a->start;
}

static inline u64 balloc_base_unshift(struct nvgpu_buddy_allocator *a,
				      u64 base)
{
	return base + a->start;
}

static inline struct nvgpu_allocator *balloc_owner(
	struct nvgpu_buddy_allocator *a)
{
	return a->owner;
}

#endif /* NVGPU_MM_BUDDY_ALLOCATOR_PRIV_H */