gpu: nvgpu: use nvgpu rbtree for page allocator

Use nvgpu rbtree instead of linux rbtree for page allocator
Move to use nvgpu_rbtree_node structure and
nvgpu_rbtree_* APIs

Jira NVGPU-13

Change-Id: I3faf843762652c6005186cbe715377050f65ee2c
Signed-off-by: Deepak Nibade <dnibade@nvidia.com>
Reviewed-on: http://git-master/r/1457858
Reviewed-by: svccoveritychecker <svccoveritychecker@nvidia.com>
GVS: Gerrit_Virtual_Submit
Reviewed-by: Bharat Nihalani <bnihalani@nvidia.com>

2 files changed, 19 insertions, 38 deletions

diff --git a/drivers/gpu/nvgpu/common/mm/page_allocator.c b/drivers/gpu/nvgpu/common/mm/page_allocator.c
index 14d66efe..1b6a2092 100644
--- a/drivers/gpu/nvgpu/common/mm/page_allocator.c
+++ b/drivers/gpu/nvgpu/common/mm/page_allocator.c
@@ -151,28 +151,10 @@ static void __nvgpu_free_pages(struct nvgpu_page_allocator *a,
 static int __insert_page_alloc(struct nvgpu_page_allocator *a,
                                struct nvgpu_page_alloc *alloc)
 {
-        struct rb_node **new = &a->allocs.rb_node;
-        struct rb_node *parent = NULL;
-
-        while (*new) {
-                struct nvgpu_page_alloc *tmp =
-                        container_of(*new, struct nvgpu_page_alloc,
-                                     tree_entry);
-
-                parent = *new;
-                if (alloc->base < tmp->base) {
-                        new = &((*new)->rb_left);
-                } else if (alloc->base > tmp->base) {
-                        new = &((*new)->rb_right);
-                } else {
-                        WARN(1, "Duplicate entries in allocated list!\n");
-                        return 0;
-                }
-        }
-
-        rb_link_node(&alloc->tree_entry, parent, new);
-        rb_insert_color(&alloc->tree_entry, &a->allocs);
+        alloc->tree_entry.key_start = alloc->base;
+        alloc->tree_entry.key_end = alloc->base + alloc->length;
 
+        nvgpu_rbtree_insert(&alloc->tree_entry, &a->allocs);
         return 0;
 }
 
@@ -180,24 +162,16 @@ static struct nvgpu_page_alloc *__find_page_alloc(
         struct nvgpu_page_allocator *a,
         u64 addr)
 {
-        struct rb_node *node = a->allocs.rb_node;
         struct nvgpu_page_alloc *alloc;
+        struct nvgpu_rbtree_node *node = NULL;
 
-        while (node) {
-                alloc = container_of(node, struct nvgpu_page_alloc, tree_entry);
-
-                if (addr < alloc->base)
-                        node = node->rb_left;
-                else if (addr > alloc->base)
-                        node = node->rb_right;
-                else
-                        break;
-        }
-
+        nvgpu_rbtree_search(addr, &node, a->allocs);
         if (!node)
                 return NULL;
 
-        rb_erase(node, &a->allocs);
+        alloc = nvgpu_page_alloc_from_rbtree_node(node);
+
+        nvgpu_rbtree_unlink(node, &a->allocs);
 
         return alloc;
 }
@@ -906,7 +880,7 @@ int nvgpu_page_allocator_init(struct gk20a *g, struct nvgpu_allocator *__a,
         a->length = length;
         a->page_size = blk_size;
         a->page_shift = __ffs(blk_size);
-        a->allocs = RB_ROOT;
+        a->allocs = NULL;
         a->owner = __a;
         a->flags = flags;
 
diff --git a/drivers/gpu/nvgpu/include/nvgpu/page_allocator.h b/drivers/gpu/nvgpu/include/nvgpu/page_allocator.h
index 92f48ac5..70ed81c3 100644
--- a/drivers/gpu/nvgpu/include/nvgpu/page_allocator.h
+++ b/drivers/gpu/nvgpu/include/nvgpu/page_allocator.h
@@ -18,11 +18,11 @@
 #define PAGE_ALLOCATOR_PRIV_H
 
 #include <linux/list.h>
-#include <linux/rbtree.h>
 
 #include <nvgpu/allocator.h>
 #include <nvgpu/kmem.h>
 #include <nvgpu/list.h>
+#include <nvgpu/rbtree.h>
 
 struct nvgpu_allocator;
 
@@ -110,7 +110,7 @@ struct nvgpu_page_alloc {
          */
         u64 base;
 
-        struct rb_node tree_entry;
+        struct nvgpu_rbtree_node tree_entry;
 
         /*
          * Set if this is a slab alloc. Points back to the slab page that owns
@@ -120,6 +120,13 @@ struct nvgpu_page_alloc {
         struct page_alloc_slab_page *slab_page;
 };
 
+static inline struct nvgpu_page_alloc *
+nvgpu_page_alloc_from_rbtree_node(struct nvgpu_rbtree_node *node)
+{
+        return (struct nvgpu_page_alloc *)
+              ((uintptr_t)node - offsetof(struct nvgpu_page_alloc, tree_entry));
+};
+
 struct nvgpu_page_allocator {
         struct nvgpu_allocator *owner;  /* Owner of this allocator. */
 
@@ -138,7 +145,7 @@ struct nvgpu_page_allocator {
         u64 page_size;
         u32 page_shift;
 
-        struct rb_root allocs;          /* Outstanding allocations. */
+        struct nvgpu_rbtree_node *allocs;       /* Outstanding allocations. */
 
         struct page_alloc_slab *slabs;
         int nr_slabs;