/*
 * gk20a allocator
 *
 * Copyright (c) 2011-2015, NVIDIA CORPORATION.  All rights reserved.
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms and conditions of the GNU General Public License,
 * version 2, as published by the Free Software Foundation.
 *
 * This program is distributed in the hope it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 * more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <linux/kernel.h>
#include <linux/seq_file.h>
#include <linux/slab.h>
#include <linux/debugfs.h>

#include "platform_gk20a.h"
#include "gk20a_allocator.h"

#include "mm_gk20a.h"

static struct dentry *balloc_debugfs_root;

static struct kmem_cache *buddy_cache;	/* slab cache for meta data. */

static u32 balloc_tracing_on;

#define balloc_trace_func()				\
	do {						\
		if (balloc_tracing_on)			\
			trace_printk("%s\n", __func__);	\
	} while (0)

#define balloc_trace_func_done()				\
	do {							\
		if (balloc_tracing_on)				\
			trace_printk("%s_done\n", __func__);	\
	} while (0)


static void balloc_init_alloc_debug(struct gk20a_allocator *a);
static void balloc_print_stats(struct gk20a_allocator *a, struct seq_file *s,
			       int lock);
static struct gk20a_buddy *balloc_free_buddy(struct gk20a_allocator *a,
					     u64 addr);
static void balloc_coalesce(struct gk20a_allocator *a, struct gk20a_buddy *b);
static void __balloc_do_free_fixed(struct gk20a_allocator *a,
				   struct gk20a_fixed_alloc *falloc);

/*
 * This function is not present in older kernel's list.h code.
 */
#ifndef list_last_entry
#define list_last_entry(ptr, type, member) \
	list_entry((ptr)->prev, type, member)
#endif

/*
 * GPU buddy allocator for various address spaces.
 *
 * Current limitations:
 *   o  A fixed allocation could potentially be made that borders PDEs with
 *      different PTE sizes. This would require that fixed buffer to have
 *      different sized PTEs for different parts of the allocation. Probably
 *      best to just require PDE alignment for fixed address allocs.
 *
 *   o  It is currently possible to make an allocator that has a buddy alignment
 *      out of sync with the PDE block size alignment. A simple example is a
 *      32GB address space starting at byte 1. Every buddy is shifted off by 1
 *      which means each buddy corresponf to more than one actual GPU page. The
 *      best way to fix this is probably just require PDE blocksize alignment
 *      for the start of the address space. At the moment all allocators are
 *      easily PDE aligned so this hasn't been a problem.
 */

/*
 * Pick a suitable maximum order for this allocator.
 *
 * Hueristic: Just guessing that the best max order is the largest single
 * block that will fit in the address space.
 */
static void balloc_compute_max_order(struct gk20a_allocator *a)
{
	u64 true_max_order = ilog2(a->blks);

	if (a->max_order > true_max_order)
		a->max_order = true_max_order;
	if (a->max_order > GPU_BALLOC_MAX_ORDER)
		a->max_order = GPU_BALLOC_MAX_ORDER;
}

/*
 * Since we can only allocate in chucks of a->blk_size we need to trim off
 * any excess data that is not aligned to a->blk_size.
 */
static void balloc_allocator_align(struct gk20a_allocator *a)
{
	a->start = ALIGN(a->base, a->blk_size);
	a->end   = (a->base + a->length) & ~(a->blk_size - 1);
	a->count = a->end - a->start;
	a->blks  = a->count >> a->blk_shift;
}

/*
 * Pass NULL for parent if you want a top level buddy.
 */
static struct gk20a_buddy *balloc_new_buddy(struct gk20a_allocator *a,
					    struct gk20a_buddy *parent,
					    u64 start, u64 order)
{
	struct gk20a_buddy *new_buddy;

	new_buddy = kmem_cache_alloc(buddy_cache, GFP_KERNEL);
	if (!new_buddy)
		return NULL;

	memset(new_buddy, 0, sizeof(struct gk20a_buddy));

	new_buddy->parent = parent;
	new_buddy->start = start;
	new_buddy->order = order;
	new_buddy->end = start + (1 << order) * a->blk_size;

	return new_buddy;
}

static void __balloc_buddy_list_add(struct gk20a_allocator *a,
				    struct gk20a_buddy *b,
				    struct list_head *list)
{
	if (buddy_is_in_list(b)) {
		balloc_dbg(a, "Oops: adding added buddy (%llu:0x%llx)\n",
			   b->order, b->start);
		BUG();
	}

	/*
	 * Add big PTE blocks to the tail, small to the head for GVA spaces.
	 * This lets the code that checks if there are available blocks check
	 * without cycling through the entire list.
	 */
	if (a->flags & GPU_BALLOC_GVA_SPACE &&
	    b->pte_size == BALLOC_PTE_SIZE_BIG)
		list_add_tail(&b->buddy_entry, list);
	else
		list_add(&b->buddy_entry, list);

	buddy_set_in_list(b);
}

static void __balloc_buddy_list_rem(struct gk20a_allocator *a,
				    struct gk20a_buddy *b)
{
	if (!buddy_is_in_list(b)) {
		balloc_dbg(a, "Oops: removing removed buddy (%llu:0x%llx)\n",
			   b->order, b->start);
		BUG();
	}

	list_del_init(&b->buddy_entry);
	buddy_clr_in_list(b);
}

/*
 * Add a buddy to one of the buddy lists and deal with the necessary
 * book keeping. Adds the buddy to the list specified by the buddy's order.
 */
static void balloc_blist_add(struct gk20a_allocator *a, struct gk20a_buddy *b)
{
	__balloc_buddy_list_add(a, b, balloc_get_order_list(a, b->order));
	a->buddy_list_len[b->order]++;
}

static void balloc_blist_rem(struct gk20a_allocator *a, struct gk20a_buddy *b)
{
	__balloc_buddy_list_rem(a, b);
	a->buddy_list_len[b->order]--;
}

static u64 balloc_get_order(struct gk20a_allocator *a, u64 len)
{
	if (len == 0)
		return 0;

	len--;
	len >>= a->blk_shift;

	return fls(len);
}

static u64 __balloc_max_order_in(struct gk20a_allocator *a, u64 start, u64 end)
{
	u64 size = (end - start) >> a->blk_shift;

	if (size > 0)
		return min_t(u64, ilog2(size), a->max_order);
	else
		return GPU_BALLOC_MAX_ORDER;
}

/*
 * Initialize the buddy lists.
 */
static int balloc_init_lists(struct gk20a_allocator *a)
{
	int i;
	u64 bstart, bend, order;
	struct gk20a_buddy *buddy;

	bstart = a->start;
	bend = a->end;

	/* First make sure the LLs are valid. */
	for (i = 0; i < GPU_BALLOC_ORDER_LIST_LEN; i++)
		INIT_LIST_HEAD(balloc_get_order_list(a, i));

	while (bstart < bend) {
		order = __balloc_max_order_in(a, bstart, bend);

		buddy = balloc_new_buddy(a, NULL, bstart, order);
		if (!buddy)
			goto cleanup;

		balloc_blist_add(a, buddy);
		bstart += balloc_order_to_len(a, order);
	}

	return 0;

cleanup:
	for (i = 0; i < GPU_BALLOC_ORDER_LIST_LEN; i++) {
		if (!list_empty(balloc_get_order_list(a, i))) {
			buddy = list_first_entry(balloc_get_order_list(a, i),
					struct gk20a_buddy, buddy_entry);
			balloc_blist_rem(a, buddy);
			kmem_cache_free(buddy_cache, buddy);
		}
	}

	return -ENOMEM;
}

/*
 * Initialize a buddy allocator. Returns 0 on success. This allocator does
 * not necessarily manage bytes. It manages distinct ranges of resources. This
 * allows the allocator to work for things like comp_tags, semaphores, etc.
 *
 * @allocator: Ptr to an allocator struct to init.
 * @vm: GPU VM to associate this allocator with. Can be NULL. Will be used to
 *      get PTE size for GVA spaces.
 * @name: Name of the allocator. Doesn't have to be static storage.
 * @base: The base address of the resource pool being managed.
 * @size: Number of resources in the pool.
 * @blk_size: Minimum number of resources to allocate at once. For things like
 *            semaphores this is 1. For GVA this might be as much as 64k. This
 *            corresponds to order 0. Must be power of 2.
 * @max_order: Pick a maximum order. If you leave this as 0, the buddy allocator
 *             will try and pick a reasonable max order.
 * @flags: Extra flags necessary. See GPU_BALLOC_*.
 */
int __gk20a_allocator_init(struct gk20a_allocator *a,
			   struct vm_gk20a *vm, const char *name,
			   u64 base, u64 size, u64 blk_size, u64 max_order,
			   u64 flags)
{
	int err;

	memset(a, 0, sizeof(struct gk20a_allocator));
	strncpy(a->name, name, 32);

	a->base = base;
	a->length = size;
	a->blk_size = blk_size;
	a->blk_shift = __ffs(blk_size);

	/* blk_size must be greater than 0 and a power of 2. */
	if (blk_size == 0)
		return -EINVAL;
	if (blk_size & (blk_size - 1))
		return -EINVAL;

	if (max_order > GPU_BALLOC_MAX_ORDER)
		return -EINVAL;

	/* If this is to manage a GVA space we need a VM. */
	if (flags & GPU_BALLOC_GVA_SPACE && !vm)
		return -EINVAL;

	a->vm = vm;
	if (flags & GPU_BALLOC_GVA_SPACE)
		a->pte_blk_order = balloc_get_order(a, vm->big_page_size << 10);

	a->flags = flags;
	a->max_order = max_order;

	balloc_allocator_align(a);
	balloc_compute_max_order(a);

	/* Shared buddy kmem_cache for all allocators. */
	if (!buddy_cache)
		buddy_cache = KMEM_CACHE(gk20a_buddy, 0);
	if (!buddy_cache)
		return -ENOMEM;

	a->alloced_buddies = RB_ROOT;
	err = balloc_init_lists(a);
	if (err)
		return err;

	mutex_init(&a->lock);

	a->init = 1;

	balloc_init_alloc_debug(a);
	balloc_dbg(a, "New allocator: base      0x%llx\n", a->base);
	balloc_dbg(a, "               size      0x%llx\n", a->length);
	balloc_dbg(a, "               blk_size  0x%llx\n", a->blk_size);
	balloc_dbg(a, "               max_order %llu\n", a->max_order);
	balloc_dbg(a, "               flags     0x%llx\n", a->flags);

	return 0;
}

int gk20a_allocator_init(struct gk20a_allocator *a, const char *name,
			 u64 base, u64 size, u64 blk_size)
{
	return __gk20a_allocator_init(a, NULL, name,
				      base, size, blk_size, 0, 0);
}

/*
 * Clean up and destroy the passed allocator.
 */
void gk20a_allocator_destroy(struct gk20a_allocator *a)
{
	struct rb_node *node;
	struct gk20a_buddy *bud;
	struct gk20a_fixed_alloc *falloc;
	int i;

	balloc_lock(a);

	if (!IS_ERR_OR_NULL(a->debugfs_entry))
		debugfs_remove(a->debugfs_entry);

	/*
	 * Free the fixed allocs first.
	 */
	while ((node = rb_first(&a->fixed_allocs)) != NULL) {
		falloc = container_of(node,
				      struct gk20a_fixed_alloc, alloced_entry);

		rb_erase(node, &a->fixed_allocs);
		__balloc_do_free_fixed(a, falloc);
	}

	/*
	 * And now free all outstanding allocations.
	 */
	while ((node = rb_first(&a->alloced_buddies)) != NULL) {
		bud = container_of(node, struct gk20a_buddy, alloced_entry);
		balloc_free_buddy(a, bud->start);
		balloc_blist_add(a, bud);
		balloc_coalesce(a, bud);
	}

	/*
	 * Now clean up the unallocated buddies.
	 */
	for (i = 0; i < GPU_BALLOC_ORDER_LIST_LEN; i++) {
		BUG_ON(a->buddy_list_alloced[i] != 0);

		while (!list_empty(balloc_get_order_list(a, i))) {
			bud = list_first_entry(balloc_get_order_list(a, i),
					       struct gk20a_buddy, buddy_entry);
			balloc_blist_rem(a, bud);
			kmem_cache_free(buddy_cache, bud);
		}

		if (a->buddy_list_len[i] != 0) {
			pr_info("Excess buddies!!! (%d: %llu)\n",
				i, a->buddy_list_len[i]);
			BUG();
		}
		if (a->buddy_list_split[i] != 0) {
			pr_info("Excess split nodes!!! (%d: %llu)\n",
				i, a->buddy_list_split[i]);
			BUG();
		}
		if (a->buddy_list_alloced[i] != 0) {
			pr_info("Excess alloced nodes!!! (%d: %llu)\n",
				i, a->buddy_list_alloced[i]);
			BUG();
		}
	}

	a->init = 0;

	balloc_unlock(a);

	/*
	 * We cant unlock an allocator after memsetting it. That wipes the
	 * state of the mutex. Hopefully no one uses the allocator after
	 * destroying it...
	 */
	memset(a, 0, sizeof(struct gk20a_allocator));
}

/*
 * Combine the passed buddy if possible. The pointer in @b may not be valid
 * after this as the buddy may be freed.
 *
 * @a must be locked.
 */
static void balloc_coalesce(struct gk20a_allocator *a, struct gk20a_buddy *b)
{
	struct gk20a_buddy *parent;

	if (buddy_is_alloced(b) || buddy_is_split(b))
		return;

	/*
	 * If both our buddy and I are both not allocated and not split then
	 * we can coalesce ourselves.
	 */
	if (!b->buddy)
		return;
	if (buddy_is_alloced(b->buddy) || buddy_is_split(b->buddy))
		return;

	parent = b->parent;

	balloc_blist_rem(a, b);
	balloc_blist_rem(a, b->buddy);

	buddy_clr_split(parent);
	a->buddy_list_split[parent->order]--;
	balloc_blist_add(a, parent);

	/*
	 * Recursively coalesce as far as we can go.
	 */
	balloc_coalesce(a, parent);

	/* Clean up the remains. */
	kmem_cache_free(buddy_cache, b->buddy);
	kmem_cache_free(buddy_cache, b);
}

/*
 * Split a buddy into two new buddies who are 1/2 the size of the parent buddy.
 *
 * @a must be locked.
 */
static int balloc_split_buddy(struct gk20a_allocator *a, struct gk20a_buddy *b,
			      int pte_size)
{
	struct gk20a_buddy *left, *right;
	u64 half;

	left = balloc_new_buddy(a, b, b->start, b->order - 1);
	if (!left)
		return -ENOMEM;

	half = (b->end - b->start) / 2;

	right = balloc_new_buddy(a, b, b->start + half, b->order - 1);
	if (!right) {
		kmem_cache_free(buddy_cache, left);
		return -ENOMEM;
	}

	buddy_set_split(b);
	a->buddy_list_split[b->order]++;

	b->left = left;
	b->right = right;
	left->buddy = right;
	right->buddy = left;
	left->parent = b;
	right->parent = b;

	/* PTE considerations. */
	if (a->flags & GPU_BALLOC_GVA_SPACE &&
	    left->order <= a->pte_blk_order) {
			left->pte_size = pte_size;
			right->pte_size = pte_size;
	}

	balloc_blist_rem(a, b);
	balloc_blist_add(a, left);
	balloc_blist_add(a, right);

	return 0;
}

/*
 * Place the passed buddy into the RB tree for allocated buddies. Never fails
 * unless the passed entry is a duplicate which is a bug.
 *
 * @a must be locked.
 */
static void balloc_alloc_buddy(struct gk20a_allocator *a, struct gk20a_buddy *b)
{
	struct rb_node **new = &(a->alloced_buddies.rb_node);
	struct rb_node *parent = NULL;

	while (*new) {
		struct gk20a_buddy *bud = container_of(*new, struct gk20a_buddy,
						       alloced_entry);

		parent = *new;
		if (b->start < bud->start)
			new = &((*new)->rb_left);
		else if (b->start > bud->start)
			new = &((*new)->rb_right);
		else
			BUG_ON("Duplicate entries in allocated list!\n");
	}

	rb_link_node(&b->alloced_entry, parent, new);
	rb_insert_color(&b->alloced_entry, &a->alloced_buddies);

	buddy_set_alloced(b);
	a->buddy_list_alloced[b->order]++;
}

/*
 * Remove the passed buddy from the allocated buddy RB tree. Returns the
 * deallocated buddy for further processing.
 *
 * @a must be locked.
 */
static struct gk20a_buddy *balloc_free_buddy(struct gk20a_allocator *a,
					     u64 addr)
{
	struct rb_node *node = a->alloced_buddies.rb_node;
	struct gk20a_buddy *bud;

	while (node) {
		bud = container_of(node, struct gk20a_buddy, alloced_entry);

		if (addr < bud->start)
			node = node->rb_left;
		else if (addr > bud->start)
			node = node->rb_right;
		else
			break;
	}

	if (!node)
		return NULL;

	rb_erase(node, &a->alloced_buddies);
	buddy_clr_alloced(bud);
	a->buddy_list_alloced[bud->order]--;

	return bud;
}

/*
 * Find a suitable buddy for the given order and PTE type (big or little).
 */
static struct gk20a_buddy *__balloc_find_buddy(struct gk20a_allocator *a,
					       u64 order, int pte_size)
{
	struct gk20a_buddy *bud;

	if (order > a->max_order ||
	    list_empty(balloc_get_order_list(a, order)))
		return NULL;

	if (a->flags & GPU_BALLOC_GVA_SPACE &&
	    pte_size == BALLOC_PTE_SIZE_BIG)
		bud = list_last_entry(balloc_get_order_list(a, order),
				      struct gk20a_buddy, buddy_entry);
	else
		bud = list_first_entry(balloc_get_order_list(a, order),
				       struct gk20a_buddy, buddy_entry);

	if (bud->pte_size != BALLOC_PTE_SIZE_ANY &&
	    bud->pte_size != pte_size)
		return NULL;

	return bud;
}

/*
 * Allocate a suitably sized buddy. If no suitable buddy exists split higher
 * order buddies until we have a suitable buddy to allocate.
 *
 * For PDE grouping add an extra check to see if a buddy is suitable: that the
 * buddy exists in a PDE who's PTE size is reasonable
 *
 * @a must be locked.
 */
static u64 __balloc_do_alloc(struct gk20a_allocator *a, u64 order, int pte_size)
{
	u64 split_order;
	struct gk20a_buddy *bud = NULL;

	split_order = order;
	while (split_order <= a->max_order &&
	       !(bud = __balloc_find_buddy(a, split_order, pte_size)))
		split_order++;

	/* Out of memory! */
	if (!bud)
		return 0;

	while (bud->order != order) {
		if (balloc_split_buddy(a, bud, pte_size))
			return 0; /* No mem... */
		bud = bud->left;
	}

	balloc_blist_rem(a, bud);
	balloc_alloc_buddy(a, bud);

	return bud->start;
}

/*
 * Allocate memory from the passed allocator.
 */
u64 gk20a_balloc(struct gk20a_allocator *a, u64 len)
{
	u64 order, addr;
	int pte_size;

	balloc_trace_func();

	balloc_lock(a);

	order = balloc_get_order(a, len);

	if (order > a->max_order) {
		balloc_unlock(a);
		balloc_dbg(a, "Alloc fail\n");
		balloc_trace_func_done();
		return 0;
	}

	/*
	 * For now pass the base address of the allocator's region to
	 * __get_pte_size(). This ensures we get the right page size for
	 * the alloc but we don't have to know what the real address is
	 * going to be quite yet.
	 *
	 * TODO: once userspace supports a unified address space pass 0 for
	 * the base. This will make only 'len' affect the PTE size.
	 */
	if (a->flags & GPU_BALLOC_GVA_SPACE)
		pte_size = __get_pte_size(a->vm, a->base, len);
	else
		pte_size = BALLOC_PTE_SIZE_ANY;

	addr = __balloc_do_alloc(a, order, pte_size);

	if (addr) {
		a->bytes_alloced += len;
		a->bytes_alloced_real += balloc_order_to_len(a, order);
		balloc_dbg(a, "Alloc 0x%-10llx %3lld:0x%-10llx pte_size=%s\n",
			   addr, order, len,
			   pte_size == gmmu_page_size_big   ? "big" :
			   pte_size == gmmu_page_size_small ? "small" :
			   "NA/any");
	} else {
		balloc_dbg(a, "Alloc failed: no mem!\n");
	}

	balloc_unlock(a);

	balloc_trace_func_done();
	return addr;
}

/*
 * See if the passed range is actually available for allocation. If so, then
 * return 1, otherwise return 0.
 *
 * TODO: Right now this uses the unoptimal approach of going through all
 * outstanding allocations and checking their base/ends. This could be better.
 */
static int balloc_is_range_free(struct gk20a_allocator *a, u64 base, u64 end)
{
	struct rb_node *node;
	struct gk20a_buddy *bud;

	node = rb_first(&a->alloced_buddies);
	if (!node)
		return 1; /* No allocs yet. */

	bud = container_of(node, struct gk20a_buddy, alloced_entry);

	while (bud->start < end) {
		if ((bud->start > base && bud->start < end) ||
		    (bud->end   > base && bud->end   < end))
			return 0;

		node = rb_next(node);
		if (!node)
			break;
		bud = container_of(node, struct gk20a_buddy, alloced_entry);
	}

	return 1;
}

static void balloc_alloc_fixed(struct gk20a_allocator *a,
			       struct gk20a_fixed_alloc *f)
{
	struct rb_node **new = &(a->fixed_allocs.rb_node);
	struct rb_node *parent = NULL;

	while (*new) {
		struct gk20a_fixed_alloc *falloc =
			container_of(*new, struct gk20a_fixed_alloc,
				     alloced_entry);

		parent = *new;
		if (f->start < falloc->start)
			new = &((*new)->rb_left);
		else if (f->start > falloc->start)
			new = &((*new)->rb_right);
		else
			BUG_ON("Duplicate entries in allocated list!\n");
	}

	rb_link_node(&f->alloced_entry, parent, new);
	rb_insert_color(&f->alloced_entry, &a->fixed_allocs);
}

/*
 * Remove the passed buddy from the allocated buddy RB tree. Returns the
 * deallocated buddy for further processing.
 *
 * @a must be locked.
 */
static struct gk20a_fixed_alloc *balloc_free_fixed(struct gk20a_allocator *a,
						   u64 addr)
{
	struct rb_node *node = a->fixed_allocs.rb_node;
	struct gk20a_fixed_alloc *falloc;

	while (node) {
		falloc = container_of(node,
				      struct gk20a_fixed_alloc, alloced_entry);

		if (addr < falloc->start)
			node = node->rb_left;
		else if (addr > falloc->start)
			node = node->rb_right;
		else
			break;
	}

	if (!node)
		return NULL;

	rb_erase(node, &a->fixed_allocs);

	return falloc;
}

/*
 * Find the parent range - doesn't necessarily need the parent to actually exist
 * as a buddy. Finding an existing parent comes later...
 */
static void __balloc_get_parent_range(struct gk20a_allocator *a,
				      u64 base, u64 order,
				      u64 *pbase, u64 *porder)
{
	u64 base_mask;
	u64 shifted_base = balloc_base_shift(a, base);

	order++;
	base_mask = ~((a->blk_size << order) - 1);

	shifted_base &= base_mask;

	*pbase = balloc_base_unshift(a, shifted_base);
	*porder = order;
}

/*
 * Makes a buddy at the passed address. This will make all parent buddies
 * necessary for this buddy to exist as well.
 */
static struct gk20a_buddy *__balloc_make_fixed_buddy(struct gk20a_allocator *a,
						     u64 base, u64 order)
{
	struct gk20a_buddy *bud = NULL;
	struct list_head *order_list;
	u64 cur_order = order, cur_base = base;

	/*
	 * Algo:
	 *  1. Keep jumping up a buddy order until we find the real buddy that
	 *     this buddy exists in.
	 *  2. Then work our way down through the buddy tree until we hit a dead
	 *     end.
	 *  3. Start splitting buddies until we split to the one we need to
	 *     make.
	 */
	while (cur_order <= a->max_order) {
		int found = 0;

		order_list = balloc_get_order_list(a, cur_order);
		list_for_each_entry(bud, order_list, buddy_entry) {
			if (bud->start == cur_base) {
				found = 1;
				break;
			}
		}

		if (found)
			break;

		__balloc_get_parent_range(a, cur_base, cur_order,
					  &cur_base, &cur_order);
	}

	if (cur_order > a->max_order) {
		balloc_dbg(a, "No buddy for range ???\n");
		return NULL;
	}

	/* Split this buddy as necessary until we get the target buddy. */
	while (bud->start != base || bud->order != order) {
		if (balloc_split_buddy(a, bud, BALLOC_PTE_SIZE_ANY)) {
			balloc_coalesce(a, bud);
			return NULL;
		}

		if (base < bud->right->start)
			bud = bud->left;
		else
			bud = bud->right;

	}

	return bud;
}

static u64 __balloc_do_alloc_fixed(struct gk20a_allocator *a,
				   struct gk20a_fixed_alloc *falloc,
				   u64 base, u64 len)
{
	u64 shifted_base, inc_base;
	u64 align_order;

	shifted_base = balloc_base_shift(a, base);
	if (shifted_base == 0)
		align_order = __fls(len >> a->blk_shift);
	else
		align_order = min_t(u64,
				    __ffs(shifted_base >> a->blk_shift),
				    __fls(len >> a->blk_shift));

	if (align_order > a->max_order) {
		balloc_dbg(a, "Align order too big: %llu > %llu\n",
			   align_order, a->max_order);
		return 0;
	}

	/*
	 * Generate a list of buddies that satisfy this allocation.
	 */
	inc_base = shifted_base;
	while (inc_base < (shifted_base + len)) {
		u64 order_len = balloc_order_to_len(a, align_order);
		u64 remaining;
		struct gk20a_buddy *bud;

		bud = __balloc_make_fixed_buddy(a,
					balloc_base_unshift(a, inc_base),
					align_order);
		if (!bud) {
			balloc_dbg(a, "Fixed buddy failed: {0x%llx, %llu}!\n",
				   balloc_base_unshift(a, inc_base),
				   align_order);
			goto err_and_cleanup;
		}

		balloc_blist_rem(a, bud);
		balloc_alloc_buddy(a, bud);
		__balloc_buddy_list_add(a, bud, &falloc->buddies);

		/* Book keeping. */
		inc_base += order_len;
		remaining = (shifted_base + len) - inc_base;
		align_order = __ffs(inc_base >> a->blk_shift);

		/* If we don't have much left - trim down align_order. */
		if (balloc_order_to_len(a, align_order) > remaining)
			align_order = __balloc_max_order_in(a, inc_base,
						inc_base + remaining);
	}

	return base;

err_and_cleanup:
	while (!list_empty(&falloc->buddies)) {
		struct gk20a_buddy *bud = list_first_entry(&falloc->buddies,
							   struct gk20a_buddy,
							   buddy_entry);

		__balloc_buddy_list_rem(a, bud);
		balloc_free_buddy(a, bud->start);
		kmem_cache_free(buddy_cache, bud);
	}

	return 0;
}

/*
 * Allocate a fixed address allocation. The address of the allocation is @base
 * and the length is @len. This is not a typical buddy allocator operation and
 * as such has a high posibility of failure if the address space is heavily in
 * use.
 *
 * Please do not use this function unless _absolutely_ necessary.
 */
u64 gk20a_balloc_fixed(struct gk20a_allocator *a, u64 base, u64 len)
{
	struct gk20a_fixed_alloc *falloc = NULL;
	struct gk20a_buddy *bud;
	u64 ret, real_bytes = 0;

	balloc_trace_func();

	/* If base isn't aligned to an order 0 block, fail. */
	if (base & (a->blk_size - 1))
		goto fail;

	if (len == 0)
		goto fail;

	falloc = kmalloc(sizeof(*falloc), GFP_KERNEL);
	if (!falloc)
		goto fail;

	INIT_LIST_HEAD(&falloc->buddies);
	falloc->start = base;
	falloc->end = base + len;

	balloc_lock(a);
	if (!balloc_is_range_free(a, base, base + len)) {
		balloc_dbg(a, "Range not free: 0x%llx -> 0x%llx\n",
			   base, base + len);
		goto fail_unlock;
	}

	ret = __balloc_do_alloc_fixed(a, falloc, base, len);
	if (!ret) {
		balloc_dbg(a, "Alloc-fixed failed ?? 0x%llx -> 0x%llx\n",
			   base, base + len);
		goto fail_unlock;
	}

	balloc_alloc_fixed(a, falloc);

	list_for_each_entry(bud, &falloc->buddies, buddy_entry)
		real_bytes += (bud->end - bud->start);

	a->bytes_alloced += len;
	a->bytes_alloced_real += real_bytes;

	balloc_unlock(a);
	balloc_dbg(a, "Alloc (fixed) 0x%llx\n", base);

	balloc_trace_func_done();
	return base;

fail_unlock:
	balloc_unlock(a);
fail:
	kfree(falloc);
	balloc_trace_func_done();
	return 0;
}

static void __balloc_do_free_fixed(struct gk20a_allocator *a,
				   struct gk20a_fixed_alloc *falloc)
{
	struct gk20a_buddy *bud;

	while (!list_empty(&falloc->buddies)) {
		bud = list_first_entry(&falloc->buddies,
				       struct gk20a_buddy,
				       buddy_entry);
		__balloc_buddy_list_rem(a, bud);

		balloc_free_buddy(a, bud->start);
		balloc_blist_add(a, bud);
		a->bytes_freed += balloc_order_to_len(a, bud->order);

		/*
		 * Attemp to defrag the allocation.
		 */
		balloc_coalesce(a, bud);
	}

	kfree(falloc);
}

/*
 * Free the passed allocation.
 */
void gk20a_bfree(struct gk20a_allocator *a, u64 addr)
{
	struct gk20a_buddy *bud;
	struct gk20a_fixed_alloc *falloc;

	balloc_trace_func();

	if (!addr) {
		balloc_trace_func_done();
		return;
	}

	balloc_lock(a);

	/*
	 * First see if this is a fixed alloc. If not fall back to a regular
	 * buddy.
	 */
	falloc = balloc_free_fixed(a, addr);
	if (falloc) {
		__balloc_do_free_fixed(a, falloc);
		goto done;
	}

	bud = balloc_free_buddy(a, addr);
	if (!bud)
		goto done;

	balloc_blist_add(a, bud);
	a->bytes_freed += balloc_order_to_len(a, bud->order);

	/*
	 * Attemp to defrag the allocation.
	 */
	balloc_coalesce(a, bud);

done:
	balloc_unlock(a);
	balloc_dbg(a, "Free 0x%llx\n", addr);
	balloc_trace_func_done();
	return;
}

/*
 * Print the buddy allocator top level stats. If you pass @s as NULL then the
 * stats are printed to the kernel log. This lets this code be used for
 * debugging purposes internal to the allocator.
 */
static void balloc_print_stats(struct gk20a_allocator *a, struct seq_file *s,
			       int lock)
{
#define __balloc_pstat(s, fmt, arg...)			\
	do {						\
		if (s)					\
			seq_printf(s, fmt, ##arg);	\
		else					\
			balloc_dbg(a, fmt, ##arg);	\
	} while (0)

	int i;
	struct rb_node *node;
	struct gk20a_fixed_alloc *falloc;

	__balloc_pstat(s, "base = %llu, limit = %llu, blk_size = %llu\n",
		   a->base, a->length, a->blk_size);
	__balloc_pstat(s, "Internal params:\n");
	__balloc_pstat(s, "  start = 0x%llx\n", a->start);
	__balloc_pstat(s, "  end   = 0x%llx\n", a->end);
	__balloc_pstat(s, "  count = 0x%llx\n", a->count);
	__balloc_pstat(s, "  blks  = 0x%llx\n", a->blks);
	__balloc_pstat(s, "  max_order = %llu\n", a->max_order);

	__balloc_pstat(s, "Buddy blocks:\n");
	__balloc_pstat(s, "  Order   Free    Alloced   Split\n");
	__balloc_pstat(s, "  -----   ----    -------   -----\n");

	if (lock)
		balloc_lock(a);
	for (i = a->max_order; i >= 0; i--) {
		if (a->buddy_list_len[i] == 0 &&
		    a->buddy_list_alloced[i] == 0 &&
		    a->buddy_list_split[i] == 0)
			continue;

		__balloc_pstat(s, "  %3d     %-7llu %-9llu %llu\n", i,
			       a->buddy_list_len[i],
			       a->buddy_list_alloced[i],
			       a->buddy_list_split[i]);
	}

	__balloc_pstat(s, "\n");

	for (node = rb_first(&a->fixed_allocs), i = 1;
	     node != NULL;
	     node = rb_next(node)) {
		falloc = container_of(node,
				      struct gk20a_fixed_alloc, alloced_entry);

		__balloc_pstat(s, "Fixed alloc (%d): [0x%llx -> 0x%llx]\n",
				i, falloc->start, falloc->end);
	}

	__balloc_pstat(s, "\n");
	__balloc_pstat(s, "Bytes allocated:        %llu\n", a->bytes_alloced);
	__balloc_pstat(s, "Bytes allocated (real): %llu\n",
		       a->bytes_alloced_real);
	__balloc_pstat(s, "Bytes freed:            %llu\n", a->bytes_freed);

	if (lock)
		balloc_unlock(a);

#undef __balloc_pstats
}

static int __alloc_show(struct seq_file *s, void *unused)
{
	struct gk20a_allocator *a = s->private;

	balloc_print_stats(a, s, 1);

	return 0;
}

static int __alloc_open(struct inode *inode, struct file *file)
{
	return single_open(file, __alloc_show, inode->i_private);
}

static const struct file_operations __alloc_fops = {
	.open = __alloc_open,
	.read = seq_read,
	.llseek = seq_lseek,
	.release = single_release,
};

static void balloc_init_alloc_debug(struct gk20a_allocator *a)
{
	if (!balloc_debugfs_root)
		return;

	a->debugfs_entry = debugfs_create_file(a->name, S_IRUGO,
					       balloc_debugfs_root,
					       a, &__alloc_fops);
}

void gk20a_alloc_debugfs_init(struct platform_device *pdev)
{
	struct gk20a_platform *platform = platform_get_drvdata(pdev);
	struct dentry *gpu_root = platform->debugfs;

	balloc_debugfs_root = debugfs_create_dir("allocators", gpu_root);
	if (IS_ERR_OR_NULL(balloc_debugfs_root))
		return;

	debugfs_create_u32("tracing", 0664, balloc_debugfs_root,
			   &balloc_tracing_on);
}