gpu: nvgpu: Add NVIDIA GPU Driver

This patch moves the NVIDIA GPU driver to a new location.

Bug 1482562

Change-Id: I24293810b9d0f1504fd9be00135e21dad656ccb6
Signed-off-by: Arto Merilainen <amerilainen@nvidia.com>
Reviewed-on: http://git-master/r/383722
Reviewed-by: Terje Bergstrom <tbergstrom@nvidia.com>

1 files changed, 1247 insertions, 0 deletions

diff --git a/drivers/gpu/nvgpu/gk20a/gk20a_allocator.c b/drivers/gpu/nvgpu/gk20a/gk20a_allocator.c
new file mode 100644
index 00000000..32c003b6
--- /dev/null
+++ b/drivers/gpu/nvgpu/gk20a/gk20a_allocator.c
@@ -0,0 +1,1247 @@
+/*
+ * gk20a allocator
+ *
+ * Copyright (c) 2011-2014, 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 "gk20a_allocator.h"
+
+static inline void link_block_list(struct gk20a_allocator *allocator,
+                struct gk20a_alloc_block *block,
+                struct gk20a_alloc_block *prev,
+                struct rb_node *rb_parent);
+static inline void link_block_rb(struct gk20a_allocator *allocator,
+                struct gk20a_alloc_block *block,
+                struct rb_node **rb_link,
+                struct rb_node *rb_parent);
+static void link_block(struct gk20a_allocator *allocator,
+                struct gk20a_alloc_block *block,
+                struct gk20a_alloc_block *prev, struct rb_node **rb_link,
+                struct rb_node *rb_parent);
+static void insert_block(struct gk20a_allocator *allocator,
+                struct gk20a_alloc_block *block);
+
+static void unlink_block(struct gk20a_allocator *allocator,
+                struct gk20a_alloc_block *block,
+                struct gk20a_alloc_block *prev);
+static struct gk20a_alloc_block *unlink_blocks(
+                struct gk20a_allocator *allocator,
+                struct gk20a_alloc_block *block,
+                struct gk20a_alloc_block *prev, u32 end);
+
+static struct gk20a_alloc_block *find_block(
+                struct gk20a_allocator *allocator, u32 addr);
+static struct gk20a_alloc_block *find_block_prev(
+                struct gk20a_allocator *allocator, u32 addr,
+                struct gk20a_alloc_block **pprev);
+static struct gk20a_alloc_block *find_block_prepare(
+                struct gk20a_allocator *allocator, u32 addr,
+                struct gk20a_alloc_block **pprev, struct rb_node ***rb_link,
+                struct rb_node **rb_parent);
+
+static u32 check_free_space(u32 addr, u32 limit, u32 len, u32 align);
+static void update_free_addr_cache(struct gk20a_allocator *allocator,
+                struct gk20a_alloc_block *block,
+                u32 addr, u32 len, bool free);
+static int find_free_area(struct gk20a_allocator *allocator,
+                u32 *addr, u32 len);
+static int find_free_area_nc(struct gk20a_allocator *allocator,
+                u32 *addr, u32 *len);
+
+static void adjust_block(struct gk20a_alloc_block *block,
+                u32 start, u32 end,
+                struct gk20a_alloc_block *insert);
+static struct gk20a_alloc_block *merge_block(
+                struct gk20a_allocator *allocator,
+                struct gk20a_alloc_block *block, u32 addr, u32 end);
+static int split_block(struct gk20a_allocator *allocator,
+                struct gk20a_alloc_block *block,
+                u32 addr, int new_below);
+
+static int block_alloc_single_locked(struct gk20a_allocator *allocator,
+                u32 *addr, u32 len);
+static int block_alloc_list_locked(struct gk20a_allocator *allocator,
+                u32 *addr, u32 len,
+                struct gk20a_alloc_block **pblock);
+static int block_free_locked(struct gk20a_allocator *allocator,
+                u32 addr, u32 len);
+static void block_free_list_locked(struct gk20a_allocator *allocator,
+                struct gk20a_alloc_block *list);
+
+/* link a block into allocator block list */
+static inline void link_block_list(struct gk20a_allocator *allocator,
+                struct gk20a_alloc_block *block,
+                struct gk20a_alloc_block *prev,
+                struct rb_node *rb_parent)
+{
+        struct gk20a_alloc_block *next;
+
+        block->prev = prev;
+        if (prev) {
+                next = prev->next;
+                prev->next = block;
+        } else {
+                allocator->block_first = block;
+                if (rb_parent)
+                        next = rb_entry(rb_parent,
+                                        struct gk20a_alloc_block, rb);
+                else
+                        next = NULL;
+        }
+        block->next = next;
+        if (next)
+                next->prev = block;
+}
+
+/* link a block into allocator rb tree */
+static inline void link_block_rb(struct gk20a_allocator *allocator,
+                struct gk20a_alloc_block *block, struct rb_node **rb_link,
+                struct rb_node *rb_parent)
+{
+        rb_link_node(&block->rb, rb_parent, rb_link);
+        rb_insert_color(&block->rb, &allocator->rb_root);
+}
+
+/* add a block to allocator with known location */
+static void link_block(struct gk20a_allocator *allocator,
+                struct gk20a_alloc_block *block,
+                struct gk20a_alloc_block *prev, struct rb_node **rb_link,
+                struct rb_node *rb_parent)
+{
+        struct gk20a_alloc_block *next;
+
+        link_block_list(allocator, block, prev, rb_parent);
+        link_block_rb(allocator, block, rb_link, rb_parent);
+        allocator->block_count++;
+
+        next = block->next;
+        allocator_dbg(allocator, "link new block %d:%d between block %d:%d and block %d:%d",
+                block->start, block->end,
+                prev ? prev->start : -1, prev ? prev->end : -1,
+                next ? next->start : -1, next ? next->end : -1);
+}
+
+/* add a block to allocator */
+static void insert_block(struct gk20a_allocator *allocator,
+                        struct gk20a_alloc_block *block)
+{
+        struct gk20a_alloc_block *prev;
+        struct rb_node **rb_link, *rb_parent;
+
+        find_block_prepare(allocator, block->start,
+                        &prev, &rb_link, &rb_parent);
+        link_block(allocator, block, prev, rb_link, rb_parent);
+}
+
+/* remove a block from allocator */
+static void unlink_block(struct gk20a_allocator *allocator,
+                        struct gk20a_alloc_block *block,
+                        struct gk20a_alloc_block *prev)
+{
+        struct gk20a_alloc_block *next = block->next;
+
+        allocator_dbg(allocator, "unlink block %d:%d between block %d:%d and block %d:%d",
+                block->start, block->end,
+                prev ? prev->start : -1, prev ? prev->end : -1,
+                next ? next->start : -1, next ? next->end : -1);
+
+        BUG_ON(block->start < allocator->base);
+        BUG_ON(block->end > allocator->limit);
+
+        if (prev)
+                prev->next = next;
+        else
+                allocator->block_first = next;
+
+        if (next)
+                next->prev = prev;
+        rb_erase(&block->rb, &allocator->rb_root);
+        if (allocator->block_recent == block)
+                allocator->block_recent = prev;
+
+        allocator->block_count--;
+}
+
+/* remove a list of blocks from allocator. the list can contain both
+   regular blocks and non-contiguous blocks. skip all non-contiguous
+   blocks, remove regular blocks into a separate list, return list head */
+static struct gk20a_alloc_block *
+unlink_blocks(struct gk20a_allocator *allocator,
+                struct gk20a_alloc_block *block,
+                struct gk20a_alloc_block *prev,
+                u32 end)
+{
+        struct gk20a_alloc_block **insertion_point;
+        struct gk20a_alloc_block *last_unfreed_block = prev;
+        struct gk20a_alloc_block *last_freed_block = NULL;
+        struct gk20a_alloc_block *first_freed_block = NULL;
+
+        insertion_point = (prev ? &prev->next : &allocator->block_first);
+        *insertion_point = NULL;
+
+        do {
+                if (!block->nc_block) {
+                        allocator_dbg(allocator, "unlink block %d:%d",
+                                block->start, block->end);
+                        if (last_freed_block)
+                                last_freed_block->next = block;
+                        block->prev = last_freed_block;
+                        rb_erase(&block->rb, &allocator->rb_root);
+                        last_freed_block = block;
+                        allocator->block_count--;
+                        if (!first_freed_block)
+                                first_freed_block = block;
+                } else {
+                        allocator_dbg(allocator, "skip nc block %d:%d",
+                                block->start, block->end);
+                        if (!*insertion_point)
+                                *insertion_point = block;
+                        if (last_unfreed_block)
+                                last_unfreed_block->next = block;
+                        block->prev = last_unfreed_block;
+                        last_unfreed_block = block;
+                }
+                block = block->next;
+        } while (block && block->start < end);
+
+        if (!*insertion_point)
+                *insertion_point = block;
+
+        if (block)
+                block->prev = last_unfreed_block;
+        if (last_unfreed_block)
+                last_unfreed_block->next = block;
+        if (last_freed_block)
+                last_freed_block->next = NULL;
+
+        allocator->block_recent = NULL;
+
+        return first_freed_block;
+}
+
+/* Look up the first block which satisfies addr < block->end,
+   NULL if none */
+static struct gk20a_alloc_block *
+find_block(struct gk20a_allocator *allocator, u32 addr)
+{
+        struct gk20a_alloc_block *block = allocator->block_recent;
+
+        if (!(block && block->end > addr && block->start <= addr)) {
+                struct rb_node *rb_node;
+
+                rb_node = allocator->rb_root.rb_node;
+                block = NULL;
+
+                while (rb_node) {
+                        struct gk20a_alloc_block *block_tmp;
+
+                        block_tmp = rb_entry(rb_node,
+                                        struct gk20a_alloc_block, rb);
+
+                        if (block_tmp->end > addr) {
+                                block = block_tmp;
+                                if (block_tmp->start <= addr)
+                                        break;
+                                rb_node = rb_node->rb_left;
+                        } else
+                                rb_node = rb_node->rb_right;
+                        if (block)
+                                allocator->block_recent = block;
+                }
+        }
+        return block;
+}
+
+/* Same as find_block, but also return a pointer to the previous block */
+static struct gk20a_alloc_block *
+find_block_prev(struct gk20a_allocator *allocator, u32 addr,
+                struct gk20a_alloc_block **pprev)
+{
+        struct gk20a_alloc_block *block = NULL, *prev = NULL;
+        struct rb_node *rb_node;
+        if (!allocator)
+                goto out;
+
+        block = allocator->block_first;
+
+        rb_node = allocator->rb_root.rb_node;
+
+        while (rb_node) {
+                struct gk20a_alloc_block *block_tmp;
+                block_tmp = rb_entry(rb_node, struct gk20a_alloc_block, rb);
+
+                if (addr < block_tmp->end)
+                        rb_node = rb_node->rb_left;
+                else {
+                        prev = block_tmp;
+                        if (!prev->next || addr < prev->next->end)
+                                break;
+                        rb_node = rb_node->rb_right;
+                }
+        }
+
+out:
+        *pprev = prev;
+        return prev ? prev->next : block;
+}
+
+/* Same as find_block, but also return a pointer to the previous block
+   and return rb_node to prepare for rbtree insertion */
+static struct gk20a_alloc_block *
+find_block_prepare(struct gk20a_allocator *allocator, u32 addr,
+                struct gk20a_alloc_block **pprev, struct rb_node ***rb_link,
+                struct rb_node **rb_parent)
+{
+        struct gk20a_alloc_block *block;
+        struct rb_node **__rb_link, *__rb_parent, *rb_prev;
+
+        __rb_link = &allocator->rb_root.rb_node;
+        rb_prev = __rb_parent = NULL;
+        block = NULL;
+
+        while (*__rb_link) {
+                struct gk20a_alloc_block *block_tmp;
+
+                __rb_parent = *__rb_link;
+                block_tmp = rb_entry(__rb_parent,
+                                struct gk20a_alloc_block, rb);
+
+                if (block_tmp->end > addr) {
+                        block = block_tmp;
+                        if (block_tmp->start <= addr)
+                                break;
+                        __rb_link = &__rb_parent->rb_left;
+                } else {
+                        rb_prev = __rb_parent;
+                        __rb_link = &__rb_parent->rb_right;
+                }
+        }
+
+        *pprev = NULL;
+        if (rb_prev)
+                *pprev = rb_entry(rb_prev, struct gk20a_alloc_block, rb);
+        *rb_link = __rb_link;
+        *rb_parent = __rb_parent;
+        return block;
+}
+
+/* return available space */
+static u32 check_free_space(u32 addr, u32 limit, u32 len, u32 align)
+{
+        if (addr >= limit)
+                return 0;
+        if (addr + len <= limit)
+                return len;
+        return (limit - addr) & ~(align - 1);
+}
+
+/* update first_free_addr/last_free_addr based on new free addr
+   called when free block(s) and allocate block(s) */
+static void update_free_addr_cache(struct gk20a_allocator *allocator,
+                struct gk20a_alloc_block *next,
+                u32 addr, u32 len, bool free)
+{
+        /* update from block free */
+        if (free) {
+                if (allocator->first_free_addr > addr)
+                        allocator->first_free_addr = addr;
+        } else { /* update from block alloc */
+                if (allocator->last_free_addr < addr + len)
+                        allocator->last_free_addr = addr + len;
+                if (allocator->first_free_addr == addr) {
+                        if (!next || next->start > addr + len)
+                                allocator->first_free_addr = addr + len;
+                        else
+                                allocator->first_free_addr = next->end;
+                }
+        }
+
+        if (allocator->first_free_addr > allocator->last_free_addr)
+                allocator->first_free_addr = allocator->last_free_addr;
+}
+
+/* find a free address range for a fixed len */
+static int find_free_area(struct gk20a_allocator *allocator,
+                        u32 *addr, u32 len)
+{
+        struct gk20a_alloc_block *block;
+        u32 start_addr, search_base, search_limit;
+
+        /* fixed addr allocation */
+        /* note: constraints for fixed are handled by caller */
+        if (*addr) {
+                block = find_block(allocator, *addr);
+                if (allocator->limit - len >= *addr &&
+                    (!block || *addr + len <= block->start)) {
+                        update_free_addr_cache(allocator, block,
+                                        *addr, len, false);
+                        return 0;
+                } else
+                        return -ENOMEM;
+        }
+
+        if (!allocator->constraint.enable) {
+                search_base  = allocator->base;
+                search_limit = allocator->limit;
+        } else {
+                start_addr = *addr = allocator->constraint.base;
+                search_base = allocator->constraint.base;
+                search_limit = allocator->constraint.limit;
+        }
+
+        /* cached_hole_size has max free space up to last_free_addr */
+        if (len > allocator->cached_hole_size)
+                start_addr = *addr = allocator->last_free_addr;
+        else {
+                start_addr = *addr = allocator->base;
+                allocator->cached_hole_size = 0;
+        }
+
+        allocator_dbg(allocator, "start search addr : %d", start_addr);
+
+full_search:
+        for (block = find_block(allocator, *addr);; block = block->next) {
+                if (search_limit - len < *addr) {
+                        /* start a new search in case we missed any hole */
+                        if (start_addr != search_base) {
+                                start_addr = *addr = search_base;
+                                allocator->cached_hole_size = 0;
+                                allocator_dbg(allocator, "start a new search from base");
+                                goto full_search;
+                        }
+                        return -ENOMEM;
+                }
+                if (!block || *addr + len <= block->start) {
+                        update_free_addr_cache(allocator, block,
+                                        *addr, len, false);
+                        allocator_dbg(allocator, "free space from %d, len %d",
+                                *addr, len);
+                        allocator_dbg(allocator, "next free addr: %d",
+                                allocator->last_free_addr);
+                        return 0;
+                }
+                if (*addr + allocator->cached_hole_size < block->start)
+                        allocator->cached_hole_size = block->start - *addr;
+                *addr = block->end;
+        }
+}
+
+/* find a free address range for as long as it meets alignment or meet len */
+static int find_free_area_nc(struct gk20a_allocator *allocator,
+                        u32 *addr, u32 *len)
+{
+        struct gk20a_alloc_block *block;
+        u32 start_addr;
+        u32 avail_len;
+
+        /* fixed addr allocation */
+        if (*addr) {
+                block = find_block(allocator, *addr);
+                if (allocator->limit - *len >= *addr) {
+                        if (!block)
+                                return 0;
+
+                        avail_len = check_free_space(*addr, block->start,
+                                                *len, allocator->align);
+                        if (avail_len != 0) {
+                                update_free_addr_cache(allocator, block,
+                                        *addr, avail_len, false);
+                                allocator_dbg(allocator,
+                                        "free space between %d, %d, len %d",
+                                        *addr, block->start, avail_len);
+                                allocator_dbg(allocator, "next free addr: %d",
+                                        allocator->last_free_addr);
+                                *len = avail_len;
+                                return 0;
+                        } else
+                                return -ENOMEM;
+                } else
+                        return -ENOMEM;
+        }
+
+        start_addr = *addr = allocator->first_free_addr;
+
+        allocator_dbg(allocator, "start search addr : %d", start_addr);
+
+        for (block = find_block(allocator, *addr);; block = block->next) {
+                if (allocator->limit - *len < *addr)
+                        return -ENOMEM;
+                if (!block) {
+                        update_free_addr_cache(allocator, block,
+                                        *addr, *len, false);
+                        allocator_dbg(allocator, "free space from %d, len %d",
+                                *addr, *len);
+                        allocator_dbg(allocator, "next free addr: %d",
+                                allocator->first_free_addr);
+                        return 0;
+                }
+
+                avail_len = check_free_space(*addr, block->start,
+                                        *len, allocator->align);
+                if (avail_len != 0) {
+                        update_free_addr_cache(allocator, block,
+                                        *addr, avail_len, false);
+                        allocator_dbg(allocator, "free space between %d, %d, len %d",
+                                *addr, block->start, avail_len);
+                        allocator_dbg(allocator, "next free addr: %d",
+                                allocator->first_free_addr);
+                        *len = avail_len;
+                        return 0;
+                }
+                if (*addr + allocator->cached_hole_size < block->start)
+                        allocator->cached_hole_size = block->start - *addr;
+                *addr = block->end;
+        }
+}
+
+/* expand/shrink a block with new start and new end
+   split_block function provides insert block for shrink */
+static void adjust_block(struct gk20a_alloc_block *block,
+                u32 start, u32 end, struct gk20a_alloc_block *insert)
+{
+        struct gk20a_allocator *allocator = block->allocator;
+
+        allocator_dbg(allocator, "curr block %d:%d, new start %d, new end %d",
+                block->start, block->end, start, end);
+
+        /* expand */
+        if (!insert) {
+                if (start == block->end) {
+                        struct gk20a_alloc_block *next = block->next;
+
+                        if (next && end == next->start) {
+                                /* ....AAAA.... */
+                                /* PPPP....NNNN */
+                                /* PPPPPPPPPPPP */
+                                unlink_block(allocator, next, block);
+                                block->end = next->end;
+                                kmem_cache_free(allocator->block_cache, next);
+                        } else {
+                                /* ....AAAA.... */
+                                /* PPPP........ */
+                                /* PPPPPPPP.... */
+                                block->end = end;
+                        }
+                }
+
+                if (end == block->start) {
+                        /* ....AAAA.... */
+                        /* ........NNNN */
+                        /* PP..NNNNNNNN        ....NNNNNNNN */
+                        block->start = start;
+                }
+        } else { /* shrink */
+                /* BBBBBBBB -> BBBBIIII  OR  BBBBBBBB -> IIIIBBBB */
+                block->start = start;
+                block->end = end;
+                insert_block(allocator, insert);
+        }
+}
+
+/* given a range [addr, end], merge it with blocks before or after or both
+   if they can be combined into a contiguous block */
+static struct gk20a_alloc_block *
+merge_block(struct gk20a_allocator *allocator,
+        struct gk20a_alloc_block *prev, u32 addr, u32 end)
+{
+        struct gk20a_alloc_block *next;
+
+        if (prev)
+                next = prev->next;
+        else
+                next = allocator->block_first;
+
+        allocator_dbg(allocator, "curr block %d:%d", addr, end);
+        if (prev)
+                allocator_dbg(allocator, "prev block %d:%d",
+                        prev->start, prev->end);
+        if (next)
+                allocator_dbg(allocator, "next block %d:%d",
+                        next->start, next->end);
+
+        /* don't merge with non-contiguous allocation block */
+        if (prev && prev->end == addr && !prev->nc_block) {
+                adjust_block(prev, addr, end, NULL);
+                return prev;
+        }
+
+        /* don't merge with non-contiguous allocation block */
+        if (next && end == next->start && !next->nc_block) {
+                adjust_block(next, addr, end, NULL);
+                return next;
+        }
+
+        return NULL;
+}
+
+/* split a block based on addr. addr must be within (start, end).
+   if new_below == 1, link new block before adjusted current block */
+static int split_block(struct gk20a_allocator *allocator,
+                struct gk20a_alloc_block *block, u32 addr, int new_below)
+{
+        struct gk20a_alloc_block *new_block;
+
+        allocator_dbg(allocator, "start %d, split %d, end %d, new_below %d",
+                block->start, addr, block->end, new_below);
+
+        BUG_ON(!(addr > block->start && addr < block->end));
+
+        new_block = kmem_cache_alloc(allocator->block_cache, GFP_KERNEL);
+        if (!new_block)
+                return -ENOMEM;
+
+        *new_block = *block;
+
+        if (new_below)
+                new_block->end = addr;
+        else
+                new_block->start = addr;
+
+        if (new_below)
+                adjust_block(block, addr, block->end, new_block);
+        else
+                adjust_block(block, block->start, addr, new_block);
+
+        return 0;
+}
+
+/* free a list of blocks */
+static void free_blocks(struct gk20a_allocator *allocator,
+                        struct gk20a_alloc_block *block)
+{
+        struct gk20a_alloc_block *curr_block;
+        while (block) {
+                curr_block = block;
+                block = block->next;
+                kmem_cache_free(allocator->block_cache, curr_block);
+        }
+}
+
+/* called with rw_sema acquired */
+static int block_alloc_single_locked(struct gk20a_allocator *allocator,
+                                u32 *addr_req, u32 len)
+{
+        struct gk20a_alloc_block *block, *prev;
+        struct rb_node **rb_link, *rb_parent;
+        u32 addr = *addr_req;
+        int err;
+
+        *addr_req = ~0;
+
+        err = find_free_area(allocator, &addr, len);
+        if (err)
+                return err;
+
+        find_block_prepare(allocator, addr, &prev, &rb_link, &rb_parent);
+
+        /* merge requested free space with existing block(s)
+           if they can be combined into one contiguous block */
+        block = merge_block(allocator, prev, addr, addr + len);
+        if (block) {
+                *addr_req = addr;
+                return 0;
+        }
+
+        /* create a new block if cannot merge */
+        block = kmem_cache_zalloc(allocator->block_cache, GFP_KERNEL);
+        if (!block)
+                return -ENOMEM;
+
+        block->allocator = allocator;
+        block->start = addr;
+        block->end = addr + len;
+
+        link_block(allocator, block, prev, rb_link, rb_parent);
+
+        *addr_req = addr;
+
+        return 0;
+}
+
+static int block_alloc_list_locked(struct gk20a_allocator *allocator,
+        u32 *addr_req, u32 nc_len, struct gk20a_alloc_block **pblock)
+{
+        struct gk20a_alloc_block *block;
+        struct gk20a_alloc_block *nc_head = NULL, *nc_prev = NULL;
+        u32 addr = *addr_req, len = nc_len;
+        int err = 0;
+
+        *addr_req = ~0;
+
+        while (nc_len > 0) {
+                err = find_free_area_nc(allocator, &addr, &len);
+                if (err) {
+                        allocator_dbg(allocator, "not enough free space");
+                        goto clean_up;
+                }
+
+                /* never merge non-contiguous allocation block,
+                   just create a new block */
+                block = kmem_cache_zalloc(allocator->block_cache,
+                                        GFP_KERNEL);
+                if (!block) {
+                        err = -ENOMEM;
+                        goto clean_up;
+                }
+
+                block->allocator = allocator;
+                block->start = addr;
+                block->end = addr + len;
+
+                insert_block(allocator, block);
+
+                block->nc_prev = nc_prev;
+                if (nc_prev)
+                        nc_prev->nc_next = block;
+                nc_prev = block;
+                block->nc_block = true;
+
+                if (!nc_head)
+                        nc_head = block;
+
+                if (*addr_req == ~0)
+                        *addr_req = addr;
+
+                addr = 0;
+                nc_len -= len;
+                len = nc_len;
+                allocator_dbg(allocator, "remaining length %d", nc_len);
+        }
+
+clean_up:
+        if (err) {
+                while (nc_head) {
+                        unlink_block(allocator, nc_head, nc_head->prev);
+                        nc_prev = nc_head;
+                        nc_head = nc_head->nc_next;
+                        kmem_cache_free(allocator->block_cache, nc_prev);
+                }
+                *pblock = NULL;
+                *addr_req = ~0;
+        } else {
+                *pblock = nc_head;
+        }
+
+        return err;
+}
+
+/* called with rw_sema acquired */
+static int block_free_locked(struct gk20a_allocator *allocator,
+                        u32 addr, u32 len)
+{
+        struct gk20a_alloc_block *block, *prev, *last;
+        u32 end;
+        int err;
+
+        /* no block has block->end > addr, already free */
+        block = find_block_prev(allocator, addr, &prev);
+        if (!block)
+                return 0;
+
+        allocator_dbg(allocator, "first block in free range %d:%d",
+                block->start, block->end);
+
+        end = addr + len;
+        /* not in any block, already free */
+        if (block->start >= end)
+                return 0;
+
+        /* don't touch nc_block in range free */
+        if (addr > block->start && !block->nc_block) {
+                int err = split_block(allocator, block, addr, 0);
+                if (err)
+                        return err;
+                prev = block;
+        }
+
+        last = find_block(allocator, end);
+        if (last && end > last->start && !last->nc_block) {
+
+                allocator_dbg(allocator, "last block in free range %d:%d",
+                        last->start, last->end);
+
+                err = split_block(allocator, last, end, 1);
+                if (err)
+                        return err;
+        }
+
+        block = prev ? prev->next : allocator->block_first;
+
+        allocator_dbg(allocator, "first block for free %d:%d",
+                block->start, block->end);
+
+        /* remove blocks between [addr, addr + len) from rb tree
+           and put them in a list */
+        block = unlink_blocks(allocator, block, prev, end);
+        free_blocks(allocator, block);
+
+        update_free_addr_cache(allocator, NULL, addr, len, true);
+
+        return 0;
+}
+
+/* called with rw_sema acquired */
+static void block_free_list_locked(struct gk20a_allocator *allocator,
+                        struct gk20a_alloc_block *list)
+{
+        struct gk20a_alloc_block *block;
+        u32 len;
+
+        update_free_addr_cache(allocator, NULL,
+                        list->start, list->end - list->start, true);
+
+        while (list) {
+                block = list;
+                unlink_block(allocator, block, block->prev);
+
+                len = block->end - block->start;
+                if (allocator->cached_hole_size < len)
+                        allocator->cached_hole_size = len;
+
+                list = block->nc_next;
+                kmem_cache_free(allocator->block_cache, block);
+        }
+}
+
+static int
+gk20a_allocator_constrain(struct gk20a_allocator *a,
+                           bool enable, u32 base, u32 limit)
+{
+        if (enable) {
+                a->constraint.enable = (base >= a->base &&
+                                        limit <= a->limit);
+                if (!a->constraint.enable)
+                        return -EINVAL;
+                a->constraint.base  = base;
+                a->constraint.limit = limit;
+                a->first_free_addr = a->last_free_addr = base;
+
+        } else {
+                a->constraint.enable = false;
+                a->first_free_addr = a->last_free_addr = a->base;
+        }
+
+        a->cached_hole_size = 0;
+
+        return 0;
+}
+
+/* init allocator struct */
+int gk20a_allocator_init(struct gk20a_allocator *allocator,
+                const char *name, u32 start, u32 len, u32 align)
+{
+        memset(allocator, 0, sizeof(struct gk20a_allocator));
+
+        strncpy(allocator->name, name, 32);
+
+        allocator->block_cache =
+                kmem_cache_create(allocator->name,
+                        sizeof(struct gk20a_alloc_block), 0,
+                        SLAB_RECLAIM_ACCOUNT | SLAB_MEM_SPREAD, NULL);
+        if (!allocator->block_cache)
+                return -ENOMEM;
+
+        allocator->rb_root = RB_ROOT;
+
+        allocator->base = start;
+        allocator->limit = start + len - 1;
+        allocator->align = align;
+
+        allocator_dbg(allocator, "%s : base %d, limit %d, align %d",
+                allocator->name, allocator->base,
+                allocator->limit, allocator->align);
+
+        allocator->first_free_addr = allocator->last_free_addr = start;
+        allocator->cached_hole_size = len;
+
+        init_rwsem(&allocator->rw_sema);
+
+        allocator->alloc = gk20a_allocator_block_alloc;
+        allocator->alloc_nc = gk20a_allocator_block_alloc_nc;
+        allocator->free = gk20a_allocator_block_free;
+        allocator->free_nc = gk20a_allocator_block_free_nc;
+        allocator->constrain = gk20a_allocator_constrain;
+
+        return 0;
+}
+
+/* destroy allocator, free all remaining blocks if any */
+void gk20a_allocator_destroy(struct gk20a_allocator *allocator)
+{
+        struct gk20a_alloc_block *block, *next;
+        u32 free_count = 0;
+
+        down_write(&allocator->rw_sema);
+
+        for (block = allocator->block_first; block; ) {
+                allocator_dbg(allocator, "free remaining block %d:%d",
+                        block->start, block->end);
+                next = block->next;
+                kmem_cache_free(allocator->block_cache, block);
+                free_count++;
+                block = next;
+        }
+
+        up_write(&allocator->rw_sema);
+
+        /* block_count doesn't match real number of blocks */
+        BUG_ON(free_count != allocator->block_count);
+
+        kmem_cache_destroy(allocator->block_cache);
+
+        memset(allocator, 0, sizeof(struct gk20a_allocator));
+}
+
+/*
+ * *addr != ~0 for fixed address allocation. if *addr == 0, base addr is
+ * returned to caller in *addr.
+ *
+ * contiguous allocation, which allocates one block of
+ * contiguous address.
+*/
+int gk20a_allocator_block_alloc(struct gk20a_allocator *allocator,
+                u32 *addr, u32 len)
+{
+        int ret;
+#if defined(ALLOCATOR_DEBUG)
+        struct gk20a_alloc_block *block;
+        bool should_fail = false;
+#endif
+
+        allocator_dbg(allocator, "[in] addr %d, len %d", *addr, len);
+
+        if (*addr + len > allocator->limit || /* check addr range */
+            *addr & (allocator->align - 1) || /* check addr alignment */
+             len == 0)                        /* check len */
+                return -EINVAL;
+
+        if (allocator->constraint.enable &&
+            (*addr + len > allocator->constraint.limit ||
+             *addr > allocator->constraint.base))
+                return -EINVAL;
+
+        len = ALIGN(len, allocator->align);
+        if (!len)
+                return -ENOMEM;
+
+        down_write(&allocator->rw_sema);
+
+#if defined(ALLOCATOR_DEBUG)
+        if (*addr) {
+                for (block = allocator->block_first;
+                     block; block = block->next) {
+                        if (block->end > *addr && block->start < *addr + len) {
+                                should_fail = true;
+                                break;
+                        }
+                }
+        }
+#endif
+
+        ret = block_alloc_single_locked(allocator, addr, len);
+
+#if defined(ALLOCATOR_DEBUG)
+        if (!ret) {
+                bool allocated = false;
+                BUG_ON(should_fail);
+                BUG_ON(*addr < allocator->base);
+                BUG_ON(*addr + len > allocator->limit);
+                for (block = allocator->block_first;
+                     block; block = block->next) {
+                        if (!block->nc_block &&
+                            block->start <= *addr &&
+                            block->end >= *addr + len) {
+                                allocated = true;
+                                break;
+                        }
+                }
+                BUG_ON(!allocated);
+        }
+#endif
+
+        up_write(&allocator->rw_sema);
+
+        allocator_dbg(allocator, "[out] addr %d, len %d", *addr, len);
+
+        return ret;
+}
+
+/*
+ * *addr != ~0 for fixed address allocation. if *addr == 0, base addr is
+ * returned to caller in *addr.
+ *
+ * non-contiguous allocation, which returns a list of blocks with aggregated
+ * size == len. Individual block size must meet alignment requirement.
+ */
+int gk20a_allocator_block_alloc_nc(struct gk20a_allocator *allocator,
+                u32 *addr, u32 len, struct gk20a_alloc_block **pblock)
+{
+        int ret;
+
+        allocator_dbg(allocator, "[in] addr %d, len %d", *addr, len);
+
+        BUG_ON(pblock == NULL);
+        *pblock = NULL;
+
+        if (*addr + len > allocator->limit || /* check addr range */
+            *addr & (allocator->align - 1) || /* check addr alignment */
+             len == 0)                        /* check len */
+                return -EINVAL;
+
+        len = ALIGN(len, allocator->align);
+        if (!len)
+                return -ENOMEM;
+
+        down_write(&allocator->rw_sema);
+
+        ret = block_alloc_list_locked(allocator, addr, len, pblock);
+
+#if defined(ALLOCATOR_DEBUG)
+        if (!ret) {
+                struct gk20a_alloc_block *block = *pblock;
+                BUG_ON(!block);
+                BUG_ON(block->start < allocator->base);
+                while (block->nc_next) {
+                        BUG_ON(block->end > block->nc_next->start);
+                        block = block->nc_next;
+                }
+                BUG_ON(block->end > allocator->limit);
+        }
+#endif
+
+        up_write(&allocator->rw_sema);
+
+        allocator_dbg(allocator, "[out] addr %d, len %d", *addr, len);
+
+        return ret;
+}
+
+/* free all blocks between start and end */
+int gk20a_allocator_block_free(struct gk20a_allocator *allocator,
+                u32 addr, u32 len)
+{
+        int ret;
+
+        allocator_dbg(allocator, "[in] addr %d, len %d", addr, len);
+
+        if (addr + len > allocator->limit || /* check addr range */
+            addr < allocator->base ||
+            addr & (allocator->align - 1))   /* check addr alignment */
+                return -EINVAL;
+
+        len = ALIGN(len, allocator->align);
+        if (!len)
+                return -EINVAL;
+
+        down_write(&allocator->rw_sema);
+
+        ret = block_free_locked(allocator, addr, len);
+
+#if defined(ALLOCATOR_DEBUG)
+        if (!ret) {
+                struct gk20a_alloc_block *block;
+                for (block = allocator->block_first;
+                     block; block = block->next) {
+                        if (!block->nc_block)
+                                BUG_ON(block->start >= addr &&
+                                        block->end <= addr + len);
+                }
+        }
+#endif
+        up_write(&allocator->rw_sema);
+
+        allocator_dbg(allocator, "[out] addr %d, len %d", addr, len);
+
+        return ret;
+}
+
+/* free non-contiguous allocation block list */
+void gk20a_allocator_block_free_nc(struct gk20a_allocator *allocator,
+                struct gk20a_alloc_block *block)
+{
+        /* nothing to free */
+        if (!block)
+                return;
+
+        down_write(&allocator->rw_sema);
+        block_free_list_locked(allocator, block);
+        up_write(&allocator->rw_sema);
+}
+
+#if defined(ALLOCATOR_DEBUG)
+
+#include <linux/random.h>
+
+/* test suite */
+void gk20a_allocator_test(void)
+{
+        struct gk20a_allocator allocator;
+        struct gk20a_alloc_block *list[5];
+        u32 addr, len;
+        u32 count;
+        int n;
+
+        gk20a_allocator_init(&allocator, "test", 0, 10, 1);
+
+        /* alloc/free a single block in the beginning */
+        addr = 0;
+        gk20a_allocator_block_alloc(&allocator, &addr, 2);
+        gk20a_allocator_dump(&allocator);
+        gk20a_allocator_block_free(&allocator, addr, 2);
+        gk20a_allocator_dump(&allocator);
+        /* alloc/free a single block in the middle */
+        addr = 4;
+        gk20a_allocator_block_alloc(&allocator, &addr, 2);
+        gk20a_allocator_dump(&allocator);
+        gk20a_allocator_block_free(&allocator, addr, 2);
+        gk20a_allocator_dump(&allocator);
+        /* alloc/free a single block in the end */
+        addr = 8;
+        gk20a_allocator_block_alloc(&allocator, &addr, 2);
+        gk20a_allocator_dump(&allocator);
+        gk20a_allocator_block_free(&allocator, addr, 2);
+        gk20a_allocator_dump(&allocator);
+
+        /* allocate contiguous blocks */
+        addr = 0;
+        gk20a_allocator_block_alloc(&allocator, &addr, 2);
+        gk20a_allocator_dump(&allocator);
+        addr = 0;
+        gk20a_allocator_block_alloc(&allocator, &addr, 4);
+        gk20a_allocator_dump(&allocator);
+        addr = 0;
+        gk20a_allocator_block_alloc(&allocator, &addr, 4);
+        gk20a_allocator_dump(&allocator);
+
+        /* no free space */
+        addr = 0;
+        gk20a_allocator_block_alloc(&allocator, &addr, 2);
+        gk20a_allocator_dump(&allocator);
+
+        /* free in the end */
+        gk20a_allocator_block_free(&allocator, 8, 2);
+        gk20a_allocator_dump(&allocator);
+        /* free in the beginning */
+        gk20a_allocator_block_free(&allocator, 0, 2);
+        gk20a_allocator_dump(&allocator);
+        /* free in the middle */
+        gk20a_allocator_block_free(&allocator, 4, 2);
+        gk20a_allocator_dump(&allocator);
+
+        /* merge case PPPPAAAANNNN */
+        addr = 4;
+        gk20a_allocator_block_alloc(&allocator, &addr, 2);
+        gk20a_allocator_dump(&allocator);
+        /* merge case ....AAAANNNN */
+        addr = 0;
+        gk20a_allocator_block_alloc(&allocator, &addr, 2);
+        gk20a_allocator_dump(&allocator);
+        /* merge case PPPPAAAA.... */
+        addr = 8;
+        gk20a_allocator_block_alloc(&allocator, &addr, 2);
+        gk20a_allocator_dump(&allocator);
+
+        /* test free across multiple blocks and split */
+        gk20a_allocator_block_free(&allocator, 2, 2);
+        gk20a_allocator_dump(&allocator);
+        gk20a_allocator_block_free(&allocator, 6, 2);
+        gk20a_allocator_dump(&allocator);
+        gk20a_allocator_block_free(&allocator, 1, 8);
+        gk20a_allocator_dump(&allocator);
+
+        /* test non-contiguous allocation */
+        addr = 4;
+        gk20a_allocator_block_alloc(&allocator, &addr, 2);
+        gk20a_allocator_dump(&allocator);
+        addr = 0;
+        gk20a_allocator_block_alloc_nc(&allocator, &addr, 5, &list[0]);
+        gk20a_allocator_dump(&allocator);
+        gk20a_allocator_dump_nc_list(&allocator, list[0]);
+
+        /* test free a range overlaping non-contiguous blocks */
+        gk20a_allocator_block_free(&allocator, 2, 6);
+        gk20a_allocator_dump(&allocator);
+
+        /* test non-contiguous free */
+        gk20a_allocator_block_free_nc(&allocator, list[0]);
+        gk20a_allocator_dump(&allocator);
+
+        gk20a_allocator_destroy(&allocator);
+
+        /* random stress test */
+        gk20a_allocator_init(&allocator, "test", 4096, 4096 * 1024, 4096);
+        for (;;) {
+                pr_debug("alloc tests...\n");
+                for (count = 0; count < 50; count++) {
+                        addr = 0;
+                        len = random32() % (4096 * 1024 / 16);
+                        gk20a_allocator_block_alloc(&allocator, &addr, len);
+                        gk20a_allocator_dump(&allocator);
+                }
+
+                pr_debug("free tests...\n");
+                for (count = 0; count < 30; count++) {
+                        addr = (random32() % (4096 * 1024)) & ~(4096 - 1);
+                        len = random32() % (4096 * 1024 / 16);
+                        gk20a_allocator_block_free(&allocator, addr, len);
+                        gk20a_allocator_dump(&allocator);
+                }
+
+                pr_debug("non-contiguous alloc tests...\n");
+                for (n = 0; n < 5; n++) {
+                        addr = 0;
+                        len = random32() % (4096 * 1024 / 8);
+                        gk20a_allocator_block_alloc_nc(&allocator, &addr,
+                                len, &list[n]);
+                        gk20a_allocator_dump(&allocator);
+                        gk20a_allocator_dump_nc_list(&allocator, list[n]);
+                }
+
+                pr_debug("free tests...\n");
+                for (count = 0; count < 10; count++) {
+                        addr = (random32() % (4096 * 1024)) & ~(4096 - 1);
+                        len = random32() % (4096 * 1024 / 16);
+                        gk20a_allocator_block_free(&allocator, addr, len);
+                        gk20a_allocator_dump(&allocator);
+                }
+
+                pr_debug("non-contiguous free tests...\n");
+                for (n = 4; n >= 0; n--) {
+                        gk20a_allocator_dump_nc_list(&allocator, list[n]);
+                        gk20a_allocator_block_free_nc(&allocator, list[n]);
+                        gk20a_allocator_dump(&allocator);
+                }
+
+                pr_debug("fixed addr alloc tests...\n");
+                for (count = 0; count < 10; count++) {
+                        addr = (random32() % (4096 * 1024)) & ~(4096 - 1);
+                        len = random32() % (4096 * 1024 / 32);
+                        gk20a_allocator_block_alloc(&allocator, &addr, len);
+                        gk20a_allocator_dump(&allocator);
+                }
+
+                pr_debug("free tests...\n");
+                for (count = 0; count < 10; count++) {
+                        addr = (random32() % (4096 * 1024)) & ~(4096 - 1);
+                        len = random32() % (4096 * 1024 / 16);
+                        gk20a_allocator_block_free(&allocator, addr, len);
+                        gk20a_allocator_dump(&allocator);
+                }
+        }
+        gk20a_allocator_destroy(&allocator);
+}
+
+#endif /* ALLOCATOR_DEBUG */
+