text: /*
   * 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.
   */
  
  #include <nvgpu/bitops.h>
  #include <nvgpu/allocator.h>
  #include <nvgpu/page_allocator.h>
  #include <nvgpu/kmem.h>
  #include <nvgpu/bug.h>
  #include <nvgpu/log2.h>
  #include <nvgpu/sizes.h>
  
  #include "buddy_allocator_priv.h"
  
  #define palloc_dbg(a, fmt, arg...)			\
  	alloc_dbg(palloc_owner(a), fmt, ##arg)
  
  /*
   * Since some Linux headers are still leaked into common code this is necessary
   * for some builds.
   */
  #ifdef PAGE_SIZE
  #undef PAGE_SIZE
  #endif
  
  #ifdef PAGE_ALIGN
  #undef PAGE_ALIGN
  #endif
  
  /*
   * VIDMEM page size is 4k.
   */
  #define PAGE_SIZE		0x1000
  #define PAGE_ALIGN(addr)	((addr + (PAGE_SIZE - 1)) &		\
  				 ((typeof(addr)) ~(PAGE_SIZE - 1)))
  
  /*
   * Handle the book-keeping for these operations.
   */
  static inline void add_slab_page_to_empty(struct page_alloc_slab *slab,
  					  struct page_alloc_slab_page *page)
  {
  	BUG_ON(page->state != SP_NONE);
  	nvgpu_list_add(&page->list_entry, &slab->empty);
  	slab->nr_empty++;
  	page->state = SP_EMPTY;
  }
  static inline void add_slab_page_to_partial(struct page_alloc_slab *slab,
  					    struct page_alloc_slab_page *page)
  {
  	BUG_ON(page->state != SP_NONE);
  	nvgpu_list_add(&page->list_entry, &slab->partial);
  	slab->nr_partial++;
  	page->state = SP_PARTIAL;
  }
  static inline void add_slab_page_to_full(struct page_alloc_slab *slab,
  					 struct page_alloc_slab_page *page)
  {
  	BUG_ON(page->state != SP_NONE);
  	nvgpu_list_add(&page->list_entry, &slab->full);
  	slab->nr_full++;
  	page->state = SP_FULL;
  }
  
  static inline void del_slab_page_from_empty(struct page_alloc_slab *slab,
  					    struct page_alloc_slab_page *page)
  {
  	nvgpu_list_del(&page->list_entry);
  	slab->nr_empty--;
  	page->state = SP_NONE;
  }
  static inline void del_slab_page_from_partial(struct page_alloc_slab *slab,
  					      struct page_alloc_slab_page *page)
  {
  	nvgpu_list_del(&page->list_entry);
  	slab->nr_partial--;
  	page->state = SP_NONE;
  }
  static inline void del_slab_page_from_full(struct page_alloc_slab *slab,
  					   struct page_alloc_slab_page *page)
  {
  	nvgpu_list_del(&page->list_entry);
  	slab->nr_full--;
  	page->state = SP_NONE;
  }
  
  static u64 nvgpu_page_alloc_length(struct nvgpu_allocator *a)
  {
  	struct nvgpu_page_allocator *va = a->priv;
  
  	return nvgpu_alloc_length(&va->source_allocator);
  }
  
  static u64 nvgpu_page_alloc_base(struct nvgpu_allocator *a)
  {
  	struct nvgpu_page_allocator *va = a->priv;
  
  	return nvgpu_alloc_base(&va->source_allocator);
  }
  
  static bool nvgpu_page_alloc_inited(struct nvgpu_allocator *a)
  {
  	struct nvgpu_page_allocator *va = a->priv;
  
  	return nvgpu_alloc_initialized(&va->source_allocator);
  }
  
  static u64 nvgpu_page_alloc_end(struct nvgpu_allocator *a)
  {
  	struct nvgpu_page_allocator *va = a->priv;
  
  	return nvgpu_alloc_end(&va->source_allocator);
  }
  
  static u64 nvgpu_page_alloc_space(struct nvgpu_allocator *a)
  {
  	struct nvgpu_page_allocator *va = a->priv;
  
  	return nvgpu_alloc_space(&va->source_allocator);
  }
  
  static int nvgpu_page_reserve_co(struct nvgpu_allocator *a,
  				 struct nvgpu_alloc_carveout *co)
  {
  	struct nvgpu_page_allocator *va = a->priv;
  
  	return nvgpu_alloc_reserve_carveout(&va->source_allocator, co);
  }
  
  static void nvgpu_page_release_co(struct nvgpu_allocator *a,
  				  struct nvgpu_alloc_carveout *co)
  {
  	struct nvgpu_page_allocator *va = a->priv;
  
  	nvgpu_alloc_release_carveout(&va->source_allocator, co);
  }
  
  static struct nvgpu_sgl *nvgpu_page_alloc_sgl_next(struct nvgpu_sgl *sgl)
  {
  	struct nvgpu_mem_sgl *sgl_impl = (struct nvgpu_mem_sgl *)sgl;
  
  	return (struct nvgpu_sgl *)sgl_impl->next;
  }
  
  static u64 nvgpu_page_alloc_sgl_phys(struct gk20a *g, struct nvgpu_sgl *sgl)
  {
  	struct nvgpu_mem_sgl *sgl_impl = (struct nvgpu_mem_sgl *)sgl;
  
  	return sgl_impl->phys;
  }
  
  static u64 nvgpu_page_alloc_sgl_dma(struct nvgpu_sgl *sgl)
  {
  	struct nvgpu_mem_sgl *sgl_impl = (struct nvgpu_mem_sgl *)sgl;
  
  	return sgl_impl->dma;
  }
  
  static u64 nvgpu_page_alloc_sgl_length(struct nvgpu_sgl *sgl)
  {
  	struct nvgpu_mem_sgl *sgl_impl = (struct nvgpu_mem_sgl *)sgl;
  
  	return sgl_impl->length;
  }
  
  static u64 nvgpu_page_alloc_sgl_gpu_addr(struct gk20a *g,
  					 struct nvgpu_sgl *sgl,
  					 struct nvgpu_gmmu_attrs *attrs)
  {
  	struct nvgpu_mem_sgl *sgl_impl = (struct nvgpu_mem_sgl *)sgl;
  
  	return sgl_impl->phys;
  }
  
  static void nvgpu_page_alloc_sgt_free(struct gk20a *g, struct nvgpu_sgt *sgt)
  {
  	/*
  	 * No-op here. The free is handled by the page_alloc free() functions.
  	 */
  }
  
  /*
   * These implement the generic scatter gather ops for pages allocated
   * by the page allocator. however, the primary aim for this, is of course,
   * vidmem.
   */
  static const struct nvgpu_sgt_ops page_alloc_sgl_ops = {
  	.sgl_next = nvgpu_page_alloc_sgl_next,
  	.sgl_phys = nvgpu_page_alloc_sgl_phys,
  	.sgl_dma = nvgpu_page_alloc_sgl_dma,
  	.sgl_length = nvgpu_page_alloc_sgl_length,
  	.sgl_gpu_addr = nvgpu_page_alloc_sgl_gpu_addr,
  	.sgt_free = nvgpu_page_alloc_sgt_free,
  };
  
  /*
   * This actually frees the sgl memory. Used by the page_alloc free() functions.
   */
  static void nvgpu_page_alloc_sgl_proper_free(struct gk20a *g,
  					     struct nvgpu_mem_sgl *sgl)
  {
  	struct nvgpu_mem_sgl *next;
  
  	while (sgl) {
  		next = sgl->next;
  		nvgpu_kfree(g, sgl);
  		sgl = next;
  	}
  }
  
  static void nvgpu_page_alloc_free_pages(struct nvgpu_page_allocator *a,
  					struct nvgpu_page_alloc *alloc,
  					bool free_buddy_alloc)
  {
  	struct nvgpu_sgl *sgl = alloc->sgt.sgl;
  	struct gk20a *g = a->owner->g;
  
  	if (free_buddy_alloc) {
  		while (sgl) {
  			nvgpu_free(&a->source_allocator,
  				   nvgpu_sgt_get_phys(g, &alloc->sgt, sgl));
  			sgl = nvgpu_sgt_get_next(&alloc->sgt, sgl);
  		}
  	}
  
  	nvgpu_page_alloc_sgl_proper_free(a->owner->g,
  			(struct nvgpu_mem_sgl *)sgl);
  	nvgpu_kmem_cache_free(a->alloc_cache, alloc);
  }
  
  static int insert_page_alloc(struct nvgpu_page_allocator *a,
  			     struct nvgpu_page_alloc *alloc)
  {
  	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;
  }
  
  static struct nvgpu_page_alloc *find_page_alloc(
  	struct nvgpu_page_allocator *a,
  	u64 addr)
  {
  	struct nvgpu_page_alloc *alloc;
  	struct nvgpu_rbtree_node *node = NULL;
  
  	nvgpu_rbtree_search(addr, &node, a->allocs);
  	if (node == NULL) {
  		return NULL;
  	}
  
  	alloc = nvgpu_page_alloc_from_rbtree_node(node);
  
  	nvgpu_rbtree_unlink(node, &a->allocs);
  
  	return alloc;
  }
  
  static struct page_alloc_slab_page *alloc_slab_page(
  	struct nvgpu_page_allocator *a,
  	struct page_alloc_slab *slab)
  {
  	struct page_alloc_slab_page *slab_page;
  
  	slab_page = nvgpu_kmem_cache_alloc(a->slab_page_cache);
  	if (slab_page == NULL) {
  		palloc_dbg(a, "OOM: unable to alloc slab_page struct!");
  		return NULL;
  	}
  
  	memset(slab_page, 0, sizeof(*slab_page));
  
  	slab_page->page_addr = nvgpu_alloc(&a->source_allocator, a->page_size);
  	if (slab_page->page_addr == 0ULL) {
  		nvgpu_kmem_cache_free(a->slab_page_cache, slab_page);
  		palloc_dbg(a, "OOM: vidmem is full!");
  		return NULL;
  	}
  
  	nvgpu_init_list_node(&slab_page->list_entry);
  	slab_page->slab_size = slab->slab_size;
  	slab_page->nr_objects = (u32)a->page_size / slab->slab_size;
  	slab_page->nr_objects_alloced = 0;
  	slab_page->owner = slab;
  	slab_page->state = SP_NONE;
  
  	a->pages_alloced++;
  
  	palloc_dbg(a, "Allocated new slab page @ 0x%012llx size=%u",
  		   slab_page->page_addr, slab_page->slab_size);
  
  	return slab_page;
  }
  
  static void free_slab_page(struct nvgpu_page_allocator *a,
  			   struct page_alloc_slab_page *slab_page)
  {
  	palloc_dbg(a, "Freeing slab page @ 0x%012llx", slab_page->page_addr);
  
  	BUG_ON((slab_page->state != SP_NONE && slab_page->state != SP_EMPTY) ||
  	       slab_page->nr_objects_alloced != 0U ||
  	       slab_page->bitmap != 0U);
  
  	nvgpu_free(&a->source_allocator, slab_page->page_addr);
  	a->pages_freed++;
  
  	nvgpu_kmem_cache_free(a->slab_page_cache, slab_page);
  }
  
  /*
   * This expects @alloc to have 1 empty sgl_entry ready for usage.
   */
  static int do_slab_alloc(struct nvgpu_page_allocator *a,
  			 struct page_alloc_slab *slab,
  			 struct nvgpu_page_alloc *alloc)
  {
  	struct page_alloc_slab_page *slab_page = NULL;
  	struct nvgpu_mem_sgl *sgl;
  	unsigned long offs;
  
  	/*
  	 * Check the partial and empty lists to see if we have some space
  	 * readily available. Take the slab_page out of what ever list it
  	 * was in since it may be put back into a different list later.
  	 */
  	if (!nvgpu_list_empty(&slab->partial)) {
  		slab_page = nvgpu_list_first_entry(&slab->partial,
  					     page_alloc_slab_page,
  					     list_entry);
  		del_slab_page_from_partial(slab, slab_page);
  	} else if (!nvgpu_list_empty(&slab->empty)) {
  		slab_page = nvgpu_list_first_entry(&slab->empty,
  					     page_alloc_slab_page,
  					     list_entry);
  		del_slab_page_from_empty(slab, slab_page);
  	}
  
  	if (slab_page == NULL) {
  		slab_page = alloc_slab_page(a, slab);
  		if (slab_page == NULL) {
  			return -ENOMEM;
  		}
  	}
  
  	/*
  	 * We now have a slab_page. Do the alloc.
  	 */
  	offs = bitmap_find_next_zero_area(&slab_page->bitmap,
  					  slab_page->nr_objects,
  					  0, 1, 0);
  	if (offs >= slab_page->nr_objects) {
  		WARN(1, "Empty/partial slab with no free objects?");
  
  		/* Add the buggy page to the full list... This isn't ideal. */
  		add_slab_page_to_full(slab, slab_page);
  		return -ENOMEM;
  	}
  
  	bitmap_set(&slab_page->bitmap, offs, 1);
  	slab_page->nr_objects_alloced++;
  
  	if (slab_page->nr_objects_alloced < slab_page->nr_objects) {
  		add_slab_page_to_partial(slab, slab_page);
  	} else if (slab_page->nr_objects_alloced == slab_page->nr_objects) {
  		add_slab_page_to_full(slab, slab_page);
  	} else {
  		BUG(); /* Should be impossible to hit this. */
  	}
  
  	/*
  	 * Handle building the nvgpu_page_alloc struct. We expect one sgl
  	 * to be present.
  	 */
  	alloc->slab_page = slab_page;
  	alloc->nr_chunks = 1;
  	alloc->length = slab_page->slab_size;
  	alloc->base = slab_page->page_addr + (offs * slab_page->slab_size);
  
  	sgl         = (struct nvgpu_mem_sgl *)alloc->sgt.sgl;
  	sgl->phys   = alloc->base;
  	sgl->dma    = alloc->base;
  	sgl->length = alloc->length;
  	sgl->next   = NULL;
  
  	return 0;
  }
  
  /*
   * Allocate from a slab instead of directly from the page allocator.
   */
  static struct nvgpu_page_alloc *nvgpu_alloc_slab(
  	struct nvgpu_page_allocator *a, u64 len)
  {
  	int err, slab_nr;
  	struct page_alloc_slab *slab;
  	struct nvgpu_page_alloc *alloc = NULL;
  	struct nvgpu_mem_sgl *sgl = NULL;
  
  	/*
  	 * Align the length to a page and then divide by the page size (4k for
  	 * this code). ilog2() of that then gets us the correct slab to use.
  	 */
  	slab_nr = (int)ilog2(PAGE_ALIGN(len) >> 12);
  	slab = &a->slabs[slab_nr];
  
  	alloc = nvgpu_kmem_cache_alloc(a->alloc_cache);
  	if (alloc == NULL) {
  		palloc_dbg(a, "OOM: could not alloc page_alloc struct!");
  		goto fail;
  	}
  
  	alloc->sgt.ops = &page_alloc_sgl_ops;
  
  	sgl = nvgpu_kzalloc(a->owner->g, sizeof(*sgl));
  	if (sgl == NULL) {
  		palloc_dbg(a, "OOM: could not alloc sgl struct!");
  		goto fail;
  	}
  
  	alloc->sgt.sgl = (struct nvgpu_sgl *)sgl;
  	err = do_slab_alloc(a, slab, alloc);
  	if (err) {
  		goto fail;
  	}
  
  	palloc_dbg(a, "Alloc 0x%04llx sr=%d id=0x%010llx [slab]",
  		   len, slab_nr, alloc->base);
  	a->nr_slab_allocs++;
  
  	return alloc;
  
  fail:
  	if (alloc) {
  		nvgpu_kmem_cache_free(a->alloc_cache, alloc);
  	}
  	if (sgl) {
  		nvgpu_kfree(a->owner->g, sgl);
  	}
  	return NULL;
  }
  
  static void nvgpu_free_slab(struct nvgpu_page_allocator *a,
  			    struct nvgpu_page_alloc *alloc)
  {
  	struct page_alloc_slab_page *slab_page = alloc->slab_page;
  	struct page_alloc_slab *slab = slab_page->owner;
  	enum slab_page_state new_state;
  	int offs;
  
  	offs = (u32)(alloc->base - slab_page->page_addr) / slab_page->slab_size;
  	bitmap_clear(&slab_page->bitmap, offs, 1);
  
  	slab_page->nr_objects_alloced--;
  
  	if (slab_page->nr_objects_alloced == 0U) {
  		new_state = SP_EMPTY;
  	} else {
  		new_state = SP_PARTIAL;
  	}
  
  	/*
  	 * Need to migrate the page to a different list.
  	 */
  	if (new_state != slab_page->state) {
  		/* Delete - can't be in empty. */
  		if (slab_page->state == SP_PARTIAL) {
  			del_slab_page_from_partial(slab, slab_page);
  		} else {
  			del_slab_page_from_full(slab, slab_page);
  		}
  
  		/* And add. */
  		if (new_state == SP_EMPTY) {
  			if (nvgpu_list_empty(&slab->empty)) {
  				add_slab_page_to_empty(slab, slab_page);
  			} else {
  				free_slab_page(a, slab_page);
  			}
  		} else {
  			add_slab_page_to_partial(slab, slab_page);
  		}
  	}
  
  	/*
  	 * Now handle the page_alloc.
  	 */
  	nvgpu_page_alloc_free_pages(a, alloc, false);
  	a->nr_slab_frees++;
  
  	return;
  }
  
  /*
   * Allocate physical pages. Since the underlying allocator is a buddy allocator
   * the returned pages are always contiguous. However, since there could be
   * fragmentation in the space this allocator will collate smaller non-contiguous
   * allocations together if necessary.
   */
  static struct nvgpu_page_alloc *do_nvgpu_alloc_pages(
  	struct nvgpu_page_allocator *a, u64 pages)
  {
  	struct nvgpu_page_alloc *alloc;
  	struct nvgpu_mem_sgl *sgl, *prev_sgl = NULL;
  	u64 max_chunk_len = pages << a->page_shift;
  	int i = 0;
  
  	alloc = nvgpu_kmem_cache_alloc(a->alloc_cache);
  	if (alloc == NULL) {
  		goto fail;
  	}
  
  	memset(alloc, 0, sizeof(*alloc));
  
  	alloc->length = pages << a->page_shift;
  	alloc->sgt.ops = &page_alloc_sgl_ops;
  
  	while (pages) {
  		u64 chunk_addr = 0;
  		u64 chunk_pages = (u64)1 << __fls(pages);
  		u64 chunk_len = chunk_pages << a->page_shift;
  
  		/*
  		 * Take care of the possibility that the allocation must be
  		 * contiguous. If this is not the first iteration then that
  		 * means the first iteration failed to alloc the entire
  		 * requested size. The buddy allocator guarantees any given
  		 * single alloc is contiguous.
  		 */
  		if ((a->flags & GPU_ALLOC_FORCE_CONTIG) != 0ULL && i != 0) {
  			goto fail_cleanup;
  		}
  
  		if (chunk_len > max_chunk_len) {
  			chunk_len = max_chunk_len;
  		}
  
  		/*
  		 * Keep attempting to allocate in smaller chunks until the alloc
  		 * either succeeds or is smaller than the page_size of the
  		 * allocator (i.e the allocator is OOM).
  		 */
  		do {
  			chunk_addr = nvgpu_alloc(&a->source_allocator,
  						 chunk_len);
  
  			/* Divide by 2 and try again */
  			if (chunk_addr == 0ULL) {
  				palloc_dbg(a, "balloc failed: 0x%llx",
  					   chunk_len);
  				chunk_len >>= 1;
  				max_chunk_len = chunk_len;
  			}
  		} while (chunk_addr == 0ULL && chunk_len >= a->page_size);
  
  		chunk_pages = chunk_len >> a->page_shift;
  
  		if (chunk_addr == 0ULL) {
  			palloc_dbg(a, "bailing @ 0x%llx", chunk_len);
  			goto fail_cleanup;
  		}
  
  		sgl = nvgpu_kzalloc(a->owner->g, sizeof(*sgl));
  		if (sgl == NULL) {
  			nvgpu_free(&a->source_allocator, chunk_addr);
  			goto fail_cleanup;
  		}
  
  		pages -= chunk_pages;
  
  		sgl->phys   = chunk_addr;
  		sgl->dma    = chunk_addr;
  		sgl->length = chunk_len;
  
  		/*
  		 * Build the singly linked list with a head node that is part of
  		 * the list.
  		 */
  		if (prev_sgl) {
  			prev_sgl->next = sgl;
  		} else {
  			alloc->sgt.sgl = (struct nvgpu_sgl *)sgl;
  		}
  
  		prev_sgl = sgl;
  
  		i++;
  	}
  
  	alloc->nr_chunks = i;
  	alloc->base = ((struct nvgpu_mem_sgl *)alloc->sgt.sgl)->phys;
  
  	return alloc;
  
  fail_cleanup:
  	sgl = (struct nvgpu_mem_sgl *)alloc->sgt.sgl;
  	while (sgl) {
  		struct nvgpu_mem_sgl *next = sgl->next;
  
  		nvgpu_free(&a->source_allocator, sgl->phys);
  		nvgpu_kfree(a->owner->g, sgl);
  
  		sgl = next;
  	}
  
  	nvgpu_kmem_cache_free(a->alloc_cache, alloc);
  fail:
  	return NULL;
  }
  
  static struct nvgpu_page_alloc *nvgpu_alloc_pages(
  	struct nvgpu_page_allocator *a, u64 len)
  {
  	struct gk20a *g = a->owner->g;
  	struct nvgpu_page_alloc *alloc = NULL;
  	struct nvgpu_sgl *sgl;
  	u64 pages;
  	int i = 0;
  
  	pages = ALIGN(len, a->page_size) >> a->page_shift;
  
  	alloc = do_nvgpu_alloc_pages(a, pages);
  	if (alloc == NULL) {
  		palloc_dbg(a, "Alloc 0x%llx (%llu) (failed)",
  			   pages << a->page_shift, pages);
  		return NULL;
  	}
  
  	palloc_dbg(a, "Alloc 0x%llx (%llu) id=0x%010llx",
  		   pages << a->page_shift, pages, alloc->base);
  	sgl = alloc->sgt.sgl;
  	while (sgl) {
  		palloc_dbg(a, "  Chunk %2d: 0x%010llx + 0x%llx",
  			   i++,
  			   nvgpu_sgt_get_phys(g, &alloc->sgt, sgl),
  			   nvgpu_sgt_get_length(&alloc->sgt, sgl));
  		sgl = nvgpu_sgt_get_next(&alloc->sgt, sgl);
  	}
  	palloc_dbg(a, "Alloc done");
  
  	return alloc;
  }
  
  /*
   * Allocate enough pages to satisfy @len. Page size is determined at
   * initialization of the allocator.
   *
   * The return is actually a pointer to a struct nvgpu_page_alloc pointer. This
   * is because it doesn't make a lot of sense to return the address of the first
   * page in the list of pages (since they could be discontiguous). This has
   * precedent in the dma_alloc APIs, though, it's really just an annoying
   * artifact of the fact that the nvgpu_alloc() API requires a u64 return type.
   */
  static u64 nvgpu_page_alloc(struct nvgpu_allocator *na, u64 len)
  {
  	struct nvgpu_page_allocator *a = page_allocator(na);
  	struct nvgpu_page_alloc *alloc = NULL;
  	u64 real_len;
  
  	/*
  	 * If we want contig pages we have to round up to a power of two. It's
  	 * easier to do that here than in the buddy allocator.
  	 */
  	real_len = ((a->flags & GPU_ALLOC_FORCE_CONTIG) != 0ULL) ?
  		roundup_pow_of_two(len) : len;
  
  	alloc_lock(na);
  	if ((a->flags & GPU_ALLOC_4K_VIDMEM_PAGES) != 0ULL &&
  	    real_len <= (a->page_size / 2U)) {
  		alloc = nvgpu_alloc_slab(a, real_len);
  	} else {
  		alloc = nvgpu_alloc_pages(a, real_len);
  	}
  
  	if (alloc == NULL) {
  		alloc_unlock(na);
  		return 0;
  	}
  
  	insert_page_alloc(a, alloc);
  
  	a->nr_allocs++;
  	if (real_len > a->page_size / 2U) {
  		a->pages_alloced += alloc->length >> a->page_shift;
  	}
  	alloc_unlock(na);
  
  	if (a->flags & GPU_ALLOC_NO_SCATTER_GATHER) {
  		return alloc->base;
  	} else {
  		return (u64) (uintptr_t) alloc;
  	}
  }
  
  /*
   * Note: this will remove the nvgpu_page_alloc struct from the RB tree
   * if it's found.
   */
  static void nvgpu_page_free(struct nvgpu_allocator *na, u64 base)
  {
  	struct nvgpu_page_allocator *a = page_allocator(na);
  	struct nvgpu_page_alloc *alloc;
  
  	alloc_lock(na);
  
  	if (a->flags & GPU_ALLOC_NO_SCATTER_GATHER) {
  		alloc = find_page_alloc(a, base);
  	} else {
  		alloc = find_page_alloc(a,
  			((struct nvgpu_page_alloc *)(uintptr_t)base)->base);
  	}
  
  	if (alloc == NULL) {
  		palloc_dbg(a, "Hrm, found no alloc?");
  		goto done;
  	}
  
  	a->nr_frees++;
  
  	palloc_dbg(a, "Free  0x%llx id=0x%010llx",
  		   alloc->length, alloc->base);
  
  	/*
  	 * Frees *alloc.
  	 */
  	if (alloc->slab_page) {
  		nvgpu_free_slab(a, alloc);
  	} else {
  		a->pages_freed += (alloc->length >> a->page_shift);
  		nvgpu_page_alloc_free_pages(a, alloc, true);
  	}
  
  done:
  	alloc_unlock(na);
  }
  
  static struct nvgpu_page_alloc *nvgpu_alloc_pages_fixed(
  	struct nvgpu_page_allocator *a, u64 base, u64 length, u32 unused)
  {
  	struct nvgpu_page_alloc *alloc;
  	struct nvgpu_mem_sgl *sgl;
  
  	alloc = nvgpu_kmem_cache_alloc(a->alloc_cache);
  	sgl = nvgpu_kzalloc(a->owner->g, sizeof(*sgl));
  	if (alloc == NULL || sgl == NULL) {
  		goto fail;
  	}
  
  	alloc->sgt.ops = &page_alloc_sgl_ops;
  	alloc->base = nvgpu_alloc_fixed(&a->source_allocator, base, length, 0);
  	if (alloc->base == 0ULL) {
  		WARN(1, "nvgpu: failed to fixed alloc pages @ 0x%010llx", base);
  		goto fail;
  	}
  
  	alloc->nr_chunks = 1;
  	alloc->length = length;
  	alloc->sgt.sgl = (struct nvgpu_sgl *)sgl;
  
  	sgl->phys   = alloc->base;
  	sgl->dma    = alloc->base;
  	sgl->length = length;
  	sgl->next   = NULL;
  
  	return alloc;
  
  fail:
  	if (sgl) {
  		nvgpu_kfree(a->owner->g, sgl);
  	}
  	if (alloc) {
  		nvgpu_kmem_cache_free(a->alloc_cache, alloc);
  	}
  	return NULL;
  }
  
  /*
   * @page_size is ignored.
   */
  static u64 nvgpu_page_alloc_fixed(struct nvgpu_allocator *na,
  				  u64 base, u64 len, u32 page_size)
  {
  	struct nvgpu_page_allocator *a = page_allocator(na);
  	struct nvgpu_page_alloc *alloc = NULL;
  	struct nvgpu_sgl *sgl;
  	struct gk20a *g = a->owner->g;
  	u64 aligned_len, pages;
  	int i = 0;
  
  	aligned_len = ALIGN(len, a->page_size);
  	pages = aligned_len >> a->page_shift;
  
  	alloc_lock(na);
  
  	alloc = nvgpu_alloc_pages_fixed(a, base, aligned_len, 0);
  	if (alloc == NULL) {
  		alloc_unlock(na);
  		return 0;
  	}
  
  	insert_page_alloc(a, alloc);
  	alloc_unlock(na);
  
  	palloc_dbg(a, "Alloc [fixed] @ 0x%010llx + 0x%llx (%llu)",
  		   alloc->base, aligned_len, pages);
  	sgl = alloc->sgt.sgl;
  	while (sgl) {
  		palloc_dbg(a, "  Chunk %2d: 0x%010llx + 0x%llx",
  			   i++,
  			   nvgpu_sgt_get_phys(g, &alloc->sgt, sgl),
  			   nvgpu_sgt_get_length(&alloc->sgt, sgl));
  		sgl = nvgpu_sgt_get_next(&alloc->sgt, sgl);
  	}
  
  	a->nr_fixed_allocs++;
  	a->pages_alloced += pages;
  
  	if (a->flags & GPU_ALLOC_NO_SCATTER_GATHER) {
  		return alloc->base;
  	} else {
  		return (u64) (uintptr_t) alloc;
  	}
  }
  
  static void nvgpu_page_free_fixed(struct nvgpu_allocator *na,
  				  u64 base, u64 len)
  {
  	struct nvgpu_page_allocator *a = page_allocator(na);
  	struct nvgpu_page_alloc *alloc;
  
  	alloc_lock(na);
  
  	if (a->flags & GPU_ALLOC_NO_SCATTER_GATHER) {
  		alloc = find_page_alloc(a, base);
  		if (alloc == NULL) {
  			goto done;
  		}
  	} else {
  		alloc = (struct nvgpu_page_alloc *) (uintptr_t) base;
  	}
  
  	palloc_dbg(a, "Free  [fixed] 0x%010llx + 0x%llx",
  		   alloc->base, alloc->length);
  
  	a->nr_fixed_frees++;
  	a->pages_freed += (alloc->length >> a->page_shift);
  
  	/*
  	 * This works for the time being since the buddy allocator
  	 * uses the same free function for both fixed and regular
  	 * allocs. This would have to be updated if the underlying
  	 * allocator were to change.
  	 */
  	nvgpu_page_alloc_free_pages(a, alloc, true);
  
  done:
  	alloc_unlock(na);
  }
  
  static void nvgpu_page_allocator_destroy(struct nvgpu_allocator *na)
  {
  	struct nvgpu_page_allocator *a = page_allocator(na);
  
  	alloc_lock(na);
  	nvgpu_kfree(nvgpu_alloc_to_gpu(na), a);
  	na->priv = NULL;
  	alloc_unlock(na);
  }
  
  #ifdef __KERNEL__
  static void nvgpu_page_print_stats(struct nvgpu_allocator *na,
  				   struct seq_file *s, int lock)
  {
  	struct nvgpu_page_allocator *a = page_allocator(na);
  	int i;
  
  	if (lock)
  		alloc_lock(na);
  
  	__alloc_pstat(s, na, "Page allocator:");
  	__alloc_pstat(s, na, "  allocs         %lld", a->nr_allocs);
  	__alloc_pstat(s, na, "  frees          %lld", a->nr_frees);
  	__alloc_pstat(s, na, "  fixed_allocs   %lld", a->nr_fixed_allocs);
  	__alloc_pstat(s, na, "  fixed_frees    %lld", a->nr_fixed_frees);
  	__alloc_pstat(s, na, "  slab_allocs    %lld", a->nr_slab_allocs);
  	__alloc_pstat(s, na, "  slab_frees     %lld", a->nr_slab_frees);
  	__alloc_pstat(s, na, "  pages alloced  %lld", a->pages_alloced);
  	__alloc_pstat(s, na, "  pages freed    %lld", a->pages_freed);
  	__alloc_pstat(s, na, "");
  
  	__alloc_pstat(s, na, "Page size:       %lld KB",
  		      a->page_size >> 10);
  	__alloc_pstat(s, na, "Total pages:     %lld (%lld MB)",
  		      a->length / a->page_size,
  		      a->length >> 20);
  	__alloc_pstat(s, na, "Available pages: %lld (%lld MB)",
  		      nvgpu_alloc_space(&a->source_allocator) / a->page_size,
  		      nvgpu_alloc_space(&a->source_allocator) >> 20);
  	__alloc_pstat(s, na, "");
  
  	/*
  	 * Slab info.
  	 */
  	if (a->flags & GPU_ALLOC_4K_VIDMEM_PAGES) {
  		__alloc_pstat(s, na, "Slabs:");
  		__alloc_pstat(s, na, "  size      empty     partial   full");
  		__alloc_pstat(s, na, "  ----      -----     -------   ----");
  
  		for (i = 0; i < a->nr_slabs; i++) {
  			struct page_alloc_slab *slab = &a->slabs[i];
  
  			__alloc_pstat(s, na, "  %-9u %-9d %-9u %u",
  				      slab->slab_size,
  				      slab->nr_empty, slab->nr_partial,
  				      slab->nr_full);
  		}
  		__alloc_pstat(s, na, "");
  	}
  
  	__alloc_pstat(s, na, "Source alloc: %s",
  		      a->source_allocator.name);
  	nvgpu_alloc_print_stats(&a->source_allocator, s, lock);
  
  	if (lock)
  		alloc_unlock(na);
  }
  #endif
  
  static const struct nvgpu_allocator_ops page_ops = {
  	.alloc		= nvgpu_page_alloc,
  	.free		= nvgpu_page_free,
  
  	.alloc_fixed	= nvgpu_page_alloc_fixed,
  	.free_fixed	= nvgpu_page_free_fixed,
  
  	.reserve_carveout	= nvgpu_page_reserve_co,
  	.release_carveout	= nvgpu_page_release_co,
  
  	.base		= nvgpu_page_alloc_base,
  	.length		= nvgpu_page_alloc_length,
  	.end		= nvgpu_page_alloc_end,
  	.inited		= nvgpu_page_alloc_inited,
  	.space		= nvgpu_page_alloc_space,
  
  	.fini		= nvgpu_page_allocator_destroy,
  
  #ifdef __KERNEL__
  	.print_stats	= nvgpu_page_print_stats,
  #endif
  };
  
  /*
   * nr_slabs is computed as follows: divide page_size by 4096 to get number of
   * 4k pages in page_size. Then take the base 2 log of that to get number of
   * slabs. For 64k page_size that works on like:
   *
   *   1024*64 / 1024*4 = 16
   *   ilog2(16) = 4
   *
   * That gives buckets of 1, 2, 4, and 8 pages (i.e 4k, 8k, 16k, 32k).
   */
  static int nvgpu_page_alloc_init_slabs(struct nvgpu_page_allocator *a)
  {
  	size_t nr_slabs = ilog2(a->page_size >> 12);
  	unsigned int i;
  
  	a->slabs = nvgpu_kcalloc(nvgpu_alloc_to_gpu(a->owner),
  				 nr_slabs,
  				 sizeof(struct page_alloc_slab));
  	if (a->slabs == NULL) {
  		return -ENOMEM;
  	}
  	a->nr_slabs = nr_slabs;
  
  	for (i = 0; i < nr_slabs; i++) {
  		struct page_alloc_slab *slab = &a->slabs[i];
  
  		slab->slab_size = SZ_4K * (1 << i);
  		nvgpu_init_list_node(&slab->empty);
  		nvgpu_init_list_node(&slab->partial);
  		nvgpu_init_list_node(&slab->full);
  		slab->nr_empty = 0;
  		slab->nr_partial = 0;
  		slab->nr_full = 0;
  	}
  
  	return 0;
  }
  
  int nvgpu_page_allocator_init(struct gk20a *g, struct nvgpu_allocator *na,
  			      const char *name, u64 base, u64 length,
  			      u64 blk_size, u64 flags)
  {
  	struct nvgpu_page_allocator *a;
  	char buddy_name[sizeof(na->name)];
  	int err;
  
  	if (blk_size < SZ_4K) {
  		return -EINVAL;
  	}
  
  	a = nvgpu_kzalloc(g, sizeof(struct nvgpu_page_allocator));
  	if (a == NULL) {
  		return -ENOMEM;
  	}
  
  	err = nvgpu_alloc_common_init(na, g, name, a, false, &page_ops);
  	if (err) {
  		goto fail;
  	}
  
  	a->alloc_cache = nvgpu_kmem_cache_create(g,
  					sizeof(struct nvgpu_page_alloc));
  	a->slab_page_cache = nvgpu_kmem_cache_create(g,
  					sizeof(struct page_alloc_slab_page));
  	if (a->alloc_cache == NULL || a->slab_page_cache == NULL) {
  		err = -ENOMEM;
  		goto fail;
  	}
  
  	a->base = base;
  	a->length = length;
  	a->page_size = blk_size;
  	a->page_shift = __ffs(blk_size);
  	a->allocs = NULL;
  	a->owner = na;
  	a->flags = flags;
  
  	if ((flags & GPU_ALLOC_4K_VIDMEM_PAGES) != 0ULL &&
  	    blk_size > SZ_4K) {
  		err = nvgpu_page_alloc_init_slabs(a);
  		if (err) {
  			goto fail;
  		}
  	}
  
  	snprintf(buddy_name, sizeof(buddy_name), "%s-src", name);
  
  	err = nvgpu_buddy_allocator_init(g, &a->source_allocator, NULL,
  					 buddy_name, base, length, blk_size,
  					 0ULL, 0ULL);
  	if (err) {
  		goto fail;
  	}
  
  #ifdef CONFIG_DEBUG_FS
  	nvgpu_init_alloc_debug(g, na);
  #endif
  	palloc_dbg(a, "New allocator: type      page");
  	palloc_dbg(a, "               base      0x%llx", a->base);
  	palloc_dbg(a, "               size      0x%llx", a->length);
  	palloc_dbg(a, "               page_size 0x%llx", a->page_size);
  	palloc_dbg(a, "               flags     0x%llx", a->flags);
  	palloc_dbg(a, "               slabs:    %d", a->nr_slabs);
  
  	return 0;
  
  fail:
  	if (a->alloc_cache) {
  		nvgpu_kmem_cache_destroy(a->alloc_cache);
  	}
  	if (a->slab_page_cache) {
  		nvgpu_kmem_cache_destroy(a->slab_page_cache);
  	}
  	nvgpu_kfree(g, a);
  	return err;
  }
  