ARM: tegra: Use proper type for physical addresses
[linux-2.6.git] / drivers / video / tegra / nvmap / nvmap_heap.c
1 /*
2  * drivers/video/tegra/nvmap/nvmap_heap.c
3  *
4  * GPU heap allocator.
5  *
6  * Copyright (c) 2011, NVIDIA Corporation.
7  *
8  * This program is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU General Public License as published by
10  * the Free Software Foundation; either version 2 of the License, or
11  * (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful, but WITHOUT
14  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
16  * more details.
17  *
18  * You should have received a copy of the GNU General Public License along
19  * with this program; if not, write to the Free Software Foundation, Inc.,
20  * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
21  */
22
23 #include <linux/device.h>
24 #include <linux/kernel.h>
25 #include <linux/list.h>
26 #include <linux/mm.h>
27 #include <linux/mutex.h>
28 #include <linux/slab.h>
29 #include <linux/err.h>
30
31 #include <mach/nvmap.h>
32 #include "nvmap.h"
33 #include "nvmap_heap.h"
34 #include "nvmap_common.h"
35
36 #include <asm/tlbflush.h>
37 #include <asm/cacheflush.h>
38
39 /*
40  * "carveouts" are platform-defined regions of physically contiguous memory
41  * which are not managed by the OS. a platform may specify multiple carveouts,
42  * for either small special-purpose memory regions (like IRAM on Tegra SoCs)
43  * or reserved regions of main system memory.
44  *
45  * the carveout allocator returns allocations which are physically contiguous.
46  * to reduce external fragmentation, the allocation algorithm implemented in
47  * this file employs 3 strategies for keeping allocations of similar size
48  * grouped together inside the larger heap: the "small", "normal" and "huge"
49  * strategies. the size thresholds (in bytes) for determining which strategy
50  * to employ should be provided by the platform for each heap. it is possible
51  * for a platform to define a heap where only the "normal" strategy is used.
52  *
53  * o "normal" allocations use an address-order first-fit allocator (called
54  *   BOTTOM_UP in the code below). each allocation is rounded up to be
55  *   an integer multiple of the "small" allocation size.
56  *
57  * o "huge" allocations use an address-order last-fit allocator (called
58  *   TOP_DOWN in the code below). like "normal" allocations, each allocation
59  *   is rounded up to be an integer multiple of the "small" allocation size.
60  *
61  * o "small" allocations are treated differently: the heap manager maintains
62  *   a pool of "small"-sized blocks internally from which allocations less
63  *   than 1/2 of the "small" size are buddy-allocated. if a "small" allocation
64  *   is requested and none of the buddy sub-heaps is able to service it,
65  *   the heap manager will try to allocate a new buddy-heap.
66  *
67  * this allocator is intended to keep "splinters" colocated in the carveout,
68  * and to ensure that the minimum free block size in the carveout (i.e., the
69  * "small" threshold) is still a meaningful size.
70  *
71  */
72
73 #define MAX_BUDDY_NR    128     /* maximum buddies in a buddy allocator */
74
75 enum direction {
76         TOP_DOWN,
77         BOTTOM_UP
78 };
79
80 enum block_type {
81         BLOCK_FIRST_FIT,        /* block was allocated directly from the heap */
82         BLOCK_BUDDY,            /* block was allocated from a buddy sub-heap */
83         BLOCK_EMPTY,
84 };
85
86 struct heap_stat {
87         size_t free;            /* total free size */
88         size_t free_largest;    /* largest free block */
89         size_t free_count;      /* number of free blocks */
90         size_t total;           /* total size */
91         size_t largest;         /* largest unique block */
92         size_t count;           /* total number of blocks */
93         /* fast compaction attempt counter */
94         unsigned int compaction_count_fast;
95         /* full compaction attempt counter */
96         unsigned int compaction_count_full;
97 };
98
99 struct buddy_heap;
100
101 struct buddy_block {
102         struct nvmap_heap_block block;
103         struct buddy_heap *heap;
104 };
105
106 struct list_block {
107         struct nvmap_heap_block block;
108         struct list_head all_list;
109         unsigned int mem_prot;
110         unsigned long orig_addr;
111         size_t size;
112         size_t align;
113         struct nvmap_heap *heap;
114         struct list_head free_list;
115 };
116
117 struct combo_block {
118         union {
119                 struct list_block lb;
120                 struct buddy_block bb;
121         };
122 };
123
124 struct buddy_bits {
125         unsigned int alloc:1;
126         unsigned int order:7;   /* log2(MAX_BUDDY_NR); */
127 };
128
129 struct buddy_heap {
130         struct list_block *heap_base;
131         unsigned int nr_buddies;
132         struct list_head buddy_list;
133         struct buddy_bits bitmap[MAX_BUDDY_NR];
134 };
135
136 struct nvmap_heap {
137         struct list_head all_list;
138         struct list_head free_list;
139         struct mutex lock;
140         struct list_head buddy_list;
141         unsigned int min_buddy_shift;
142         unsigned int buddy_heap_size;
143         unsigned int small_alloc;
144         const char *name;
145         void *arg;
146         struct device dev;
147 };
148
149 static struct kmem_cache *buddy_heap_cache;
150 static struct kmem_cache *block_cache;
151
152 static inline struct nvmap_heap *parent_of(struct buddy_heap *heap)
153 {
154         return heap->heap_base->heap;
155 }
156
157 static inline unsigned int order_of(size_t len, size_t min_shift)
158 {
159         len = 2 * DIV_ROUND_UP(len, (1 << min_shift)) - 1;
160         return fls(len)-1;
161 }
162
163 /* returns the free size in bytes of the buddy heap; must be called while
164  * holding the parent heap's lock. */
165 static void buddy_stat(struct buddy_heap *heap, struct heap_stat *stat)
166 {
167         unsigned int index;
168         unsigned int shift = parent_of(heap)->min_buddy_shift;
169
170         for (index = 0; index < heap->nr_buddies;
171              index += (1 << heap->bitmap[index].order)) {
172                 size_t curr = 1 << (heap->bitmap[index].order + shift);
173
174                 stat->largest = max(stat->largest, curr);
175                 stat->total += curr;
176                 stat->count++;
177
178                 if (!heap->bitmap[index].alloc) {
179                         stat->free += curr;
180                         stat->free_largest = max(stat->free_largest, curr);
181                         stat->free_count++;
182                 }
183         }
184 }
185
186 /* returns the free size of the heap (including any free blocks in any
187  * buddy-heap suballocators; must be called while holding the parent
188  * heap's lock. */
189 static unsigned long heap_stat(struct nvmap_heap *heap, struct heap_stat *stat)
190 {
191         struct buddy_heap *bh;
192         struct list_block *l = NULL;
193         unsigned long base = -1ul;
194
195         memset(stat, 0, sizeof(*stat));
196         mutex_lock(&heap->lock);
197         list_for_each_entry(l, &heap->all_list, all_list) {
198                 stat->total += l->size;
199                 stat->largest = max(l->size, stat->largest);
200                 stat->count++;
201                 base = min(base, l->orig_addr);
202         }
203
204         list_for_each_entry(bh, &heap->buddy_list, buddy_list) {
205                 buddy_stat(bh, stat);
206                 /* the total counts are double-counted for buddy heaps
207                  * since the blocks allocated for buddy heaps exist in the
208                  * all_list; subtract out the doubly-added stats */
209                 stat->total -= bh->heap_base->size;
210                 stat->count--;
211         }
212
213         list_for_each_entry(l, &heap->free_list, free_list) {
214                 stat->free += l->size;
215                 stat->free_count++;
216                 stat->free_largest = max(l->size, stat->free_largest);
217         }
218         mutex_unlock(&heap->lock);
219
220         return base;
221 }
222
223 static ssize_t heap_name_show(struct device *dev,
224                               struct device_attribute *attr, char *buf);
225
226 static ssize_t heap_stat_show(struct device *dev,
227                               struct device_attribute *attr, char *buf);
228
229 static struct device_attribute heap_stat_total_max =
230         __ATTR(total_max, S_IRUGO, heap_stat_show, NULL);
231
232 static struct device_attribute heap_stat_total_count =
233         __ATTR(total_count, S_IRUGO, heap_stat_show, NULL);
234
235 static struct device_attribute heap_stat_total_size =
236         __ATTR(total_size, S_IRUGO, heap_stat_show, NULL);
237
238 static struct device_attribute heap_stat_free_max =
239         __ATTR(free_max, S_IRUGO, heap_stat_show, NULL);
240
241 static struct device_attribute heap_stat_free_count =
242         __ATTR(free_count, S_IRUGO, heap_stat_show, NULL);
243
244 static struct device_attribute heap_stat_free_size =
245         __ATTR(free_size, S_IRUGO, heap_stat_show, NULL);
246
247 static struct device_attribute heap_stat_base =
248         __ATTR(base, S_IRUGO, heap_stat_show, NULL);
249
250 static struct device_attribute heap_attr_name =
251         __ATTR(name, S_IRUGO, heap_name_show, NULL);
252
253 static struct attribute *heap_stat_attrs[] = {
254         &heap_stat_total_max.attr,
255         &heap_stat_total_count.attr,
256         &heap_stat_total_size.attr,
257         &heap_stat_free_max.attr,
258         &heap_stat_free_count.attr,
259         &heap_stat_free_size.attr,
260         &heap_stat_base.attr,
261         &heap_attr_name.attr,
262         NULL,
263 };
264
265 static struct attribute_group heap_stat_attr_group = {
266         .attrs  = heap_stat_attrs,
267 };
268
269 static ssize_t heap_name_show(struct device *dev,
270                               struct device_attribute *attr, char *buf)
271 {
272
273         struct nvmap_heap *heap = container_of(dev, struct nvmap_heap, dev);
274         return sprintf(buf, "%s\n", heap->name);
275 }
276
277 static ssize_t heap_stat_show(struct device *dev,
278                               struct device_attribute *attr, char *buf)
279 {
280         struct nvmap_heap *heap = container_of(dev, struct nvmap_heap, dev);
281         struct heap_stat stat;
282         unsigned long base;
283
284         base = heap_stat(heap, &stat);
285
286         if (attr == &heap_stat_total_max)
287                 return sprintf(buf, "%u\n", stat.largest);
288         else if (attr == &heap_stat_total_count)
289                 return sprintf(buf, "%u\n", stat.count);
290         else if (attr == &heap_stat_total_size)
291                 return sprintf(buf, "%u\n", stat.total);
292         else if (attr == &heap_stat_free_max)
293                 return sprintf(buf, "%u\n", stat.free_largest);
294         else if (attr == &heap_stat_free_count)
295                 return sprintf(buf, "%u\n", stat.free_count);
296         else if (attr == &heap_stat_free_size)
297                 return sprintf(buf, "%u\n", stat.free);
298         else if (attr == &heap_stat_base)
299                 return sprintf(buf, "%08lx\n", base);
300         else
301                 return -EINVAL;
302 }
303 #ifndef CONFIG_NVMAP_CARVEOUT_COMPACTOR
304 static struct nvmap_heap_block *buddy_alloc(struct buddy_heap *heap,
305                                             size_t size, size_t align,
306                                             unsigned int mem_prot)
307 {
308         unsigned int index = 0;
309         unsigned int min_shift = parent_of(heap)->min_buddy_shift;
310         unsigned int order = order_of(size, min_shift);
311         unsigned int align_mask;
312         unsigned int best = heap->nr_buddies;
313         struct buddy_block *b;
314
315         if (heap->heap_base->mem_prot != mem_prot)
316                 return NULL;
317
318         align = max(align, (size_t)(1 << min_shift));
319         align_mask = (align >> min_shift) - 1;
320
321         for (index = 0; index < heap->nr_buddies;
322              index += (1 << heap->bitmap[index].order)) {
323
324                 if (heap->bitmap[index].alloc || (index & align_mask) ||
325                     (heap->bitmap[index].order < order))
326                         continue;
327
328                 if (best == heap->nr_buddies ||
329                     heap->bitmap[index].order < heap->bitmap[best].order)
330                         best = index;
331
332                 if (heap->bitmap[best].order == order)
333                         break;
334         }
335
336         if (best == heap->nr_buddies)
337                 return NULL;
338
339         b = kmem_cache_zalloc(block_cache, GFP_KERNEL);
340         if (!b)
341                 return NULL;
342
343         while (heap->bitmap[best].order != order) {
344                 unsigned int buddy;
345                 heap->bitmap[best].order--;
346                 buddy = best ^ (1 << heap->bitmap[best].order);
347                 heap->bitmap[buddy].order = heap->bitmap[best].order;
348                 heap->bitmap[buddy].alloc = 0;
349         }
350         heap->bitmap[best].alloc = 1;
351         b->block.base = heap->heap_base->block.base + (best << min_shift);
352         b->heap = heap;
353         b->block.type = BLOCK_BUDDY;
354         return &b->block;
355 }
356 #endif
357
358 static struct buddy_heap *do_buddy_free(struct nvmap_heap_block *block)
359 {
360         struct buddy_block *b = container_of(block, struct buddy_block, block);
361         struct buddy_heap *h = b->heap;
362         unsigned int min_shift = parent_of(h)->min_buddy_shift;
363         unsigned int index;
364
365         index = (block->base - h->heap_base->block.base) >> min_shift;
366         h->bitmap[index].alloc = 0;
367
368         for (;;) {
369                 unsigned int buddy = index ^ (1 << h->bitmap[index].order);
370                 if (buddy >= h->nr_buddies || h->bitmap[buddy].alloc ||
371                     h->bitmap[buddy].order != h->bitmap[index].order)
372                         break;
373
374                 h->bitmap[buddy].order++;
375                 h->bitmap[index].order++;
376                 index = min(buddy, index);
377         }
378
379         kmem_cache_free(block_cache, b);
380         if ((1 << h->bitmap[0].order) == h->nr_buddies)
381                 return h;
382
383         return NULL;
384 }
385
386
387 /*
388  * base_max limits position of allocated chunk in memory.
389  * if base_max is 0 then there is no such limitation.
390  */
391 static struct nvmap_heap_block *do_heap_alloc(struct nvmap_heap *heap,
392                                               size_t len, size_t align,
393                                               unsigned int mem_prot,
394                                               unsigned long base_max)
395 {
396         struct list_block *b = NULL;
397         struct list_block *i = NULL;
398         struct list_block *rem = NULL;
399         unsigned long fix_base;
400         enum direction dir;
401
402         /* since pages are only mappable with one cache attribute,
403          * and most allocations from carveout heaps are DMA coherent
404          * (i.e., non-cacheable), round cacheable allocations up to
405          * a page boundary to ensure that the physical pages will
406          * only be mapped one way. */
407         if (mem_prot == NVMAP_HANDLE_CACHEABLE ||
408             mem_prot == NVMAP_HANDLE_INNER_CACHEABLE) {
409                 align = max_t(size_t, align, PAGE_SIZE);
410                 len = PAGE_ALIGN(len);
411         }
412
413 #ifdef CONFIG_NVMAP_CARVEOUT_COMPACTOR
414         dir = BOTTOM_UP;
415 #else
416         dir = (len <= heap->small_alloc) ? BOTTOM_UP : TOP_DOWN;
417 #endif
418
419         if (dir == BOTTOM_UP) {
420                 list_for_each_entry(i, &heap->free_list, free_list) {
421                         size_t fix_size;
422                         fix_base = ALIGN(i->block.base, align);
423                         fix_size = i->size - (fix_base - i->block.base);
424
425                         /* needed for compaction. relocated chunk
426                          * should never go up */
427                         if (base_max && fix_base > base_max) {
428                                 break;
429                         }
430
431                         if (fix_size >= len) {
432                                 b = i;
433                                 break;
434                         }
435                 }
436         } else {
437                 list_for_each_entry_reverse(i, &heap->free_list, free_list) {
438                         if (i->size >= len) {
439                                 fix_base = i->block.base + i->size - len;
440                                 fix_base &= ~(align-1);
441                                 if (fix_base >= i->block.base) {
442                                         b = i;
443                                         break;
444                                 }
445                         }
446                 }
447         }
448
449         if (!b)
450                 return NULL;
451
452         if (dir == BOTTOM_UP)
453                 b->block.type = BLOCK_FIRST_FIT;
454
455         /* split free block */
456         if (b->block.base != fix_base) {
457                 /* insert a new free block before allocated */
458                 rem = kmem_cache_zalloc(block_cache, GFP_KERNEL);
459                 if (!rem) {
460                         b->orig_addr = b->block.base;
461                         b->block.base = fix_base;
462                         b->size -= (b->block.base - b->orig_addr);
463                         goto out;
464                 }
465
466                 rem->block.type = BLOCK_EMPTY;
467                 rem->block.base = b->block.base;
468                 rem->orig_addr = rem->block.base;
469                 rem->size = fix_base - rem->block.base;
470                 b->block.base = fix_base;
471                 b->orig_addr = fix_base;
472                 b->size -= rem->size;
473                 list_add_tail(&rem->all_list,  &b->all_list);
474                 list_add_tail(&rem->free_list, &b->free_list);
475         }
476
477         b->orig_addr = b->block.base;
478
479         if (b->size > len) {
480                 /* insert a new free block after allocated */
481                 rem = kmem_cache_zalloc(block_cache, GFP_KERNEL);
482                 if (!rem)
483                         goto out;
484
485                 rem->block.type = BLOCK_EMPTY;
486                 rem->block.base = b->block.base + len;
487                 rem->size = b->size - len;
488                 BUG_ON(rem->size > b->size);
489                 rem->orig_addr = rem->block.base;
490                 b->size = len;
491                 list_add(&rem->all_list,  &b->all_list);
492                 list_add(&rem->free_list, &b->free_list);
493         }
494
495 out:
496         list_del(&b->free_list);
497         b->heap = heap;
498         b->mem_prot = mem_prot;
499         b->align = align;
500         return &b->block;
501 }
502
503 #ifdef DEBUG_FREE_LIST
504 static void freelist_debug(struct nvmap_heap *heap, const char *title,
505                            struct list_block *token)
506 {
507         int i;
508         struct list_block *n;
509
510         dev_debug(&heap->dev, "%s\n", title);
511         i = 0;
512         list_for_each_entry(n, &heap->free_list, free_list) {
513                 dev_debug(&heap->dev,"\t%d [%p..%p]%s\n", i, (void *)n->orig_addr,
514                           (void *)(n->orig_addr + n->size),
515                           (n == token) ? "<--" : "");
516                 i++;
517         }
518 }
519 #else
520 #define freelist_debug(_heap, _title, _token)   do { } while (0)
521 #endif
522
523 static struct list_block *do_heap_free(struct nvmap_heap_block *block)
524 {
525         struct list_block *b = container_of(block, struct list_block, block);
526         struct list_block *n = NULL;
527         struct nvmap_heap *heap = b->heap;
528
529         BUG_ON(b->block.base > b->orig_addr);
530         b->size += (b->block.base - b->orig_addr);
531         b->block.base = b->orig_addr;
532
533         freelist_debug(heap, "free list before", b);
534
535         /* Find position of first free block to the right of freed one */
536         list_for_each_entry(n, &heap->free_list, free_list) {
537                 if (n->block.base > b->block.base)
538                         break;
539         }
540
541         /* Add freed block before found free one */
542         list_add_tail(&b->free_list, &n->free_list);
543         BUG_ON(list_empty(&b->all_list));
544
545         freelist_debug(heap, "free list pre-merge", b);
546
547         /* merge freed block with next if they connect
548          * freed block becomes bigger, next one is destroyed */
549         if (!list_is_last(&b->free_list, &heap->free_list)) {
550                 n = list_first_entry(&b->free_list, struct list_block, free_list);
551                 if (n->block.base == b->block.base + b->size) {
552                         list_del(&n->all_list);
553                         list_del(&n->free_list);
554                         BUG_ON(b->orig_addr >= n->orig_addr);
555                         b->size += n->size;
556                         kmem_cache_free(block_cache, n);
557                 }
558         }
559
560         /* merge freed block with prev if they connect
561          * previous free block becomes bigger, freed one is destroyed */
562         if (b->free_list.prev != &heap->free_list) {
563                 n = list_entry(b->free_list.prev, struct list_block, free_list);
564                 if (n->block.base + n->size == b->block.base) {
565                         list_del(&b->all_list);
566                         list_del(&b->free_list);
567                         BUG_ON(n->orig_addr >= b->orig_addr);
568                         n->size += b->size;
569                         kmem_cache_free(block_cache, b);
570                         b = n;
571                 }
572         }
573
574         freelist_debug(heap, "free list after", b);
575         b->block.type = BLOCK_EMPTY;
576         return b;
577 }
578
579 #ifndef CONFIG_NVMAP_CARVEOUT_COMPACTOR
580
581 static struct nvmap_heap_block *do_buddy_alloc(struct nvmap_heap *h,
582                                                size_t len, size_t align,
583                                                unsigned int mem_prot)
584 {
585         struct buddy_heap *bh;
586         struct nvmap_heap_block *b = NULL;
587
588         list_for_each_entry(bh, &h->buddy_list, buddy_list) {
589                 b = buddy_alloc(bh, len, align, mem_prot);
590                 if (b)
591                         return b;
592         }
593
594         /* no buddy heaps could service this allocation: try to create a new
595          * buddy heap instead */
596         bh = kmem_cache_zalloc(buddy_heap_cache, GFP_KERNEL);
597         if (!bh)
598                 return NULL;
599
600         b = do_heap_alloc(h, h->buddy_heap_size,
601                         h->buddy_heap_size, mem_prot, 0);
602         if (!b) {
603                 kmem_cache_free(buddy_heap_cache, bh);
604                 return NULL;
605         }
606
607         bh->heap_base = container_of(b, struct list_block, block);
608         bh->nr_buddies = h->buddy_heap_size >> h->min_buddy_shift;
609         bh->bitmap[0].alloc = 0;
610         bh->bitmap[0].order = order_of(h->buddy_heap_size, h->min_buddy_shift);
611         list_add_tail(&bh->buddy_list, &h->buddy_list);
612         return buddy_alloc(bh, len, align, mem_prot);
613 }
614
615 #endif
616
617 #ifdef CONFIG_NVMAP_CARVEOUT_COMPACTOR
618
619 static int do_heap_copy_listblock(struct nvmap_device *dev,
620                  unsigned long dst_base, unsigned long src_base, size_t len)
621 {
622         pte_t **pte_src = NULL;
623         pte_t **pte_dst = NULL;
624         void *addr_src = NULL;
625         void *addr_dst = NULL;
626         unsigned long kaddr_src;
627         unsigned long kaddr_dst;
628         unsigned long phys_src = src_base;
629         unsigned long phys_dst = dst_base;
630         unsigned long pfn_src;
631         unsigned long pfn_dst;
632         int error = 0;
633
634         pgprot_t prot = pgprot_writecombine(pgprot_kernel);
635
636         int page;
637
638         pte_src = nvmap_alloc_pte(dev, &addr_src);
639         if (IS_ERR(pte_src)) {
640                 pr_err("Error when allocating pte_src\n");
641                 pte_src = NULL;
642                 error = -1;
643                 goto fail;
644         }
645
646         pte_dst = nvmap_alloc_pte(dev, &addr_dst);
647         if (IS_ERR(pte_dst)) {
648                 pr_err("Error while allocating pte_dst\n");
649                 pte_dst = NULL;
650                 error = -1;
651                 goto fail;
652         }
653
654         kaddr_src = (unsigned long)addr_src;
655         kaddr_dst = (unsigned long)addr_dst;
656
657         BUG_ON(phys_dst > phys_src);
658         BUG_ON((phys_src & PAGE_MASK) != phys_src);
659         BUG_ON((phys_dst & PAGE_MASK) != phys_dst);
660         BUG_ON((len & PAGE_MASK) != len);
661
662         for (page = 0; page < (len >> PAGE_SHIFT) ; page++) {
663
664                 pfn_src = __phys_to_pfn(phys_src) + page;
665                 pfn_dst = __phys_to_pfn(phys_dst) + page;
666
667                 set_pte_at(&init_mm, kaddr_src, *pte_src,
668                                 pfn_pte(pfn_src, prot));
669                 flush_tlb_kernel_page(kaddr_src);
670
671                 set_pte_at(&init_mm, kaddr_dst, *pte_dst,
672                                 pfn_pte(pfn_dst, prot));
673                 flush_tlb_kernel_page(kaddr_dst);
674
675                 memcpy(addr_dst, addr_src, PAGE_SIZE);
676         }
677
678 fail:
679         if (pte_src)
680                 nvmap_free_pte(dev, pte_src);
681         if (pte_dst)
682                 nvmap_free_pte(dev, pte_dst);
683         return error;
684 }
685
686
687 static struct nvmap_heap_block *do_heap_relocate_listblock(
688                 struct list_block *block, bool fast)
689 {
690         struct nvmap_heap_block *heap_block = &block->block;
691         struct nvmap_heap_block *heap_block_new = NULL;
692         struct nvmap_heap *heap = block->heap;
693         struct nvmap_handle *handle = heap_block->handle;
694         unsigned long src_base = heap_block->base;
695         unsigned long dst_base;
696         size_t src_size = block->size;
697         size_t src_align = block->align;
698         unsigned int src_prot = block->mem_prot;
699         int error = 0;
700         struct nvmap_share *share;
701
702         if (!handle) {
703                 pr_err("INVALID HANDLE!\n");
704                 return NULL;
705         }
706
707         mutex_lock(&handle->lock);
708
709         share = nvmap_get_share_from_dev(handle->dev);
710
711         /* TODO: It is possible to use only handle lock and no share
712          * pin_lock, but then we'll need to lock every handle during
713          * each pinning operation. Need to estimate performance impact
714          * if we decide to simplify locking this way. */
715         mutex_lock(&share->pin_lock);
716
717         /* abort if block is pinned */
718         if (atomic_read(&handle->pin))
719                 goto fail;
720         /* abort if block is mapped */
721         if (handle->usecount)
722                 goto fail;
723
724         if (fast) {
725                 /* Fast compaction path - first allocate, then free. */
726                 heap_block_new = do_heap_alloc(heap, src_size, src_align,
727                                 src_prot, src_base);
728                 if (heap_block_new)
729                         do_heap_free(heap_block);
730                 else
731                         goto fail;
732         } else {
733                 /* Full compaction path, first free, then allocate
734                  * It is slower but provide best compaction results */
735                 do_heap_free(heap_block);
736                 heap_block_new = do_heap_alloc(heap, src_size, src_align,
737                                 src_prot, src_base);
738                 /* Allocation should always succeed*/
739                 BUG_ON(!heap_block_new);
740         }
741
742         /* update handle */
743         handle->carveout = heap_block_new;
744         heap_block_new->handle = handle;
745
746         /* copy source data to new block location */
747         dst_base = heap_block_new->base;
748
749         /* new allocation should always go lower addresses */
750         BUG_ON(dst_base >= src_base);
751
752         error = do_heap_copy_listblock(handle->dev,
753                                 dst_base, src_base, src_size);
754         BUG_ON(error);
755
756 fail:
757         mutex_unlock(&share->pin_lock);
758         mutex_unlock(&handle->lock);
759         return heap_block_new;
760 }
761
762 static void nvmap_heap_compact(struct nvmap_heap *heap,
763                                 size_t requested_size, bool fast)
764 {
765         struct list_block *block_current = NULL;
766         struct list_block *block_prev = NULL;
767         struct list_block *block_next = NULL;
768
769         struct list_head *ptr, *ptr_prev, *ptr_next;
770         int relocation_count = 0;
771
772         ptr = heap->all_list.next;
773
774         /* walk through all blocks */
775         while (ptr != &heap->all_list) {
776                 block_current = list_entry(ptr, struct list_block, all_list);
777
778                 ptr_prev = ptr->prev;
779                 ptr_next = ptr->next;
780
781                 if (block_current->block.type != BLOCK_EMPTY) {
782                         ptr = ptr_next;
783                         continue;
784                 }
785
786                 if (fast && block_current->size >= requested_size)
787                         break;
788
789                 /* relocate prev block */
790                 if (ptr_prev != &heap->all_list) {
791
792                         block_prev = list_entry(ptr_prev,
793                                         struct list_block, all_list);
794
795                         BUG_ON(block_prev->block.type != BLOCK_FIRST_FIT);
796
797                         if (do_heap_relocate_listblock(block_prev, true)) {
798
799                                 /* After relocation current free block can be
800                                  * destroyed when it is merged with previous
801                                  * free block. Updated pointer to new free
802                                  * block can be obtained from the next block */
803                                 relocation_count++;
804                                 ptr = ptr_next->prev;
805                                 continue;
806                         }
807                 }
808
809                 if (ptr_next != &heap->all_list) {
810
811                         block_next = list_entry(ptr_next,
812                                         struct list_block, all_list);
813
814                         BUG_ON(block_next->block.type != BLOCK_FIRST_FIT);
815
816                         if (do_heap_relocate_listblock(block_next, fast)) {
817                                 ptr = ptr_prev->next;
818                                 relocation_count++;
819                                 continue;
820                         }
821                 }
822                 ptr = ptr_next;
823         }
824         pr_err("Relocated %d chunks\n", relocation_count);
825 }
826 #endif
827
828 void nvmap_usecount_inc(struct nvmap_handle *h)
829 {
830         if (h->alloc && !h->heap_pgalloc) {
831                 mutex_lock(&h->lock);
832                 h->usecount++;
833                 mutex_unlock(&h->lock);
834         } else {
835                 h->usecount++;
836         }
837 }
838
839
840 void nvmap_usecount_dec(struct nvmap_handle *h)
841 {
842         h->usecount--;
843 }
844
845 /* nvmap_heap_alloc: allocates a block of memory of len bytes, aligned to
846  * align bytes. */
847 struct nvmap_heap_block *nvmap_heap_alloc(struct nvmap_heap *h, size_t len,
848                                           size_t align, unsigned int prot,
849                                           struct nvmap_handle *handle)
850 {
851         struct nvmap_heap_block *b;
852
853         mutex_lock(&h->lock);
854
855 #ifdef CONFIG_NVMAP_CARVEOUT_COMPACTOR
856         /* Align to page size */
857         align = ALIGN(align, PAGE_SIZE);
858         len = ALIGN(len, PAGE_SIZE);
859         b = do_heap_alloc(h, len, align, prot, 0);
860         if (!b) {
861                 pr_err("Compaction triggered!\n");
862                 nvmap_heap_compact(h, len, true);
863                 b = do_heap_alloc(h, len, align, prot, 0);
864                 if (!b) {
865                         pr_err("Full compaction triggered!\n");
866                         nvmap_heap_compact(h, len, false);
867                         b = do_heap_alloc(h, len, align, prot, 0);
868                 }
869         }
870 #else
871         if (len <= h->buddy_heap_size / 2) {
872                 b = do_buddy_alloc(h, len, align, prot);
873         } else {
874                 if (h->buddy_heap_size)
875                         len = ALIGN(len, h->buddy_heap_size);
876                 align = max(align, (size_t)L1_CACHE_BYTES);
877                 b = do_heap_alloc(h, len, align, prot, 0);
878         }
879 #endif
880
881         if (b) {
882                 b->handle = handle;
883                 handle->carveout = b;
884         }
885         mutex_unlock(&h->lock);
886         return b;
887 }
888
889 struct nvmap_heap *nvmap_block_to_heap(struct nvmap_heap_block *b)
890 {
891         if (b->type == BLOCK_BUDDY) {
892                 struct buddy_block *bb;
893                 bb = container_of(b, struct buddy_block, block);
894                 return parent_of(bb->heap);
895         } else {
896                 struct list_block *lb;
897                 lb = container_of(b, struct list_block, block);
898                 return lb->heap;
899         }
900 }
901
902 int nvmap_flush_heap_block(struct nvmap_client *client,
903         struct nvmap_heap_block *block, size_t len, unsigned int prot);
904
905 /* nvmap_heap_free: frees block b*/
906 void nvmap_heap_free(struct nvmap_heap_block *b)
907 {
908         struct buddy_heap *bh = NULL;
909         struct nvmap_heap *h = nvmap_block_to_heap(b);
910         struct list_block *lb;
911
912         mutex_lock(&h->lock);
913         if (b->type == BLOCK_BUDDY)
914                 bh = do_buddy_free(b);
915         else {
916                 lb = container_of(b, struct list_block, block);
917                 nvmap_flush_heap_block(NULL, b, lb->size, lb->mem_prot);
918                 do_heap_free(b);
919         }
920
921         if (bh) {
922                 list_del(&bh->buddy_list);
923                 mutex_unlock(&h->lock);
924                 nvmap_heap_free(&bh->heap_base->block);
925                 kmem_cache_free(buddy_heap_cache, bh);
926         } else
927                 mutex_unlock(&h->lock);
928 }
929
930
931 static void heap_release(struct device *heap)
932 {
933 }
934
935 /* nvmap_heap_create: create a heap object of len bytes, starting from
936  * address base.
937  *
938  * if buddy_size is >= NVMAP_HEAP_MIN_BUDDY_SIZE, then allocations <= 1/2
939  * of the buddy heap size will use a buddy sub-allocator, where each buddy
940  * heap is buddy_size bytes (should be a power of 2). all other allocations
941  * will be rounded up to be a multiple of buddy_size bytes.
942  */
943 struct nvmap_heap *nvmap_heap_create(struct device *parent, const char *name,
944                                      phys_addr_t base, size_t len,
945                                      size_t buddy_size, void *arg)
946 {
947         struct nvmap_heap *h = NULL;
948         struct list_block *l = NULL;
949
950         if (WARN_ON(buddy_size && buddy_size < NVMAP_HEAP_MIN_BUDDY_SIZE)) {
951                 dev_warn(parent, "%s: buddy_size %u too small\n", __func__,
952                         buddy_size);
953                 buddy_size = 0;
954         } else if (WARN_ON(buddy_size >= len)) {
955                 dev_warn(parent, "%s: buddy_size %u too large\n", __func__,
956                         buddy_size);
957                 buddy_size = 0;
958         } else if (WARN_ON(buddy_size & (buddy_size - 1))) {
959                 dev_warn(parent, "%s: buddy_size %u not a power of 2\n",
960                          __func__, buddy_size);
961                 buddy_size = 1 << (ilog2(buddy_size) + 1);
962         }
963
964         if (WARN_ON(buddy_size && (base & (buddy_size - 1)))) {
965                 unsigned long orig = base;
966                 dev_warn(parent, "%s: base address %p not aligned to "
967                          "buddy_size %u\n", __func__, (void *)base, buddy_size);
968                 base = ALIGN(base, buddy_size);
969                 len -= (base - orig);
970         }
971
972         if (WARN_ON(buddy_size && (len & (buddy_size - 1)))) {
973                 dev_warn(parent, "%s: length %u not aligned to "
974                          "buddy_size %u\n", __func__, len, buddy_size);
975                 len &= ~(buddy_size - 1);
976         }
977
978         h = kzalloc(sizeof(*h), GFP_KERNEL);
979         if (!h) {
980                 dev_err(parent, "%s: out of memory\n", __func__);
981                 goto fail_alloc;
982         }
983
984         l = kmem_cache_zalloc(block_cache, GFP_KERNEL);
985         if (!l) {
986                 dev_err(parent, "%s: out of memory\n", __func__);
987                 goto fail_alloc;
988         }
989
990         dev_set_name(&h->dev, "heap-%s", name);
991         h->name = name;
992         h->arg = arg;
993         h->dev.parent = parent;
994         h->dev.driver = NULL;
995         h->dev.release = heap_release;
996         if (device_register(&h->dev)) {
997                 dev_err(parent, "%s: failed to register %s\n", __func__,
998                         dev_name(&h->dev));
999                 goto fail_alloc;
1000         }
1001         if (sysfs_create_group(&h->dev.kobj, &heap_stat_attr_group)) {
1002                 dev_err(&h->dev, "%s: failed to create attributes\n", __func__);
1003                 goto fail_register;
1004         }
1005         h->small_alloc = max(2 * buddy_size, len / 256);
1006         h->buddy_heap_size = buddy_size;
1007         if (buddy_size)
1008                 h->min_buddy_shift = ilog2(buddy_size / MAX_BUDDY_NR);
1009         INIT_LIST_HEAD(&h->free_list);
1010         INIT_LIST_HEAD(&h->buddy_list);
1011         INIT_LIST_HEAD(&h->all_list);
1012         mutex_init(&h->lock);
1013         l->block.base = base;
1014         l->block.type = BLOCK_EMPTY;
1015         l->size = len;
1016         l->orig_addr = base;
1017         list_add_tail(&l->free_list, &h->free_list);
1018         list_add_tail(&l->all_list, &h->all_list);
1019
1020         inner_flush_cache_all();
1021         outer_flush_range(base, base + len);
1022         wmb();
1023         return h;
1024
1025 fail_register:
1026         device_unregister(&h->dev);
1027 fail_alloc:
1028         if (l)
1029                 kmem_cache_free(block_cache, l);
1030         kfree(h);
1031         return NULL;
1032 }
1033
1034 void *nvmap_heap_device_to_arg(struct device *dev)
1035 {
1036         struct nvmap_heap *heap = container_of(dev, struct nvmap_heap, dev);
1037         return heap->arg;
1038 }
1039
1040 void *nvmap_heap_to_arg(struct nvmap_heap *heap)
1041 {
1042         return heap->arg;
1043 }
1044
1045 /* nvmap_heap_destroy: frees all resources in heap */
1046 void nvmap_heap_destroy(struct nvmap_heap *heap)
1047 {
1048         WARN_ON(!list_empty(&heap->buddy_list));
1049
1050         sysfs_remove_group(&heap->dev.kobj, &heap_stat_attr_group);
1051         device_unregister(&heap->dev);
1052
1053         while (!list_empty(&heap->buddy_list)) {
1054                 struct buddy_heap *b;
1055                 b = list_first_entry(&heap->buddy_list, struct buddy_heap,
1056                                      buddy_list);
1057                 list_del(&heap->buddy_list);
1058                 nvmap_heap_free(&b->heap_base->block);
1059                 kmem_cache_free(buddy_heap_cache, b);
1060         }
1061
1062         WARN_ON(!list_is_singular(&heap->all_list));
1063         while (!list_empty(&heap->all_list)) {
1064                 struct list_block *l;
1065                 l = list_first_entry(&heap->all_list, struct list_block,
1066                                      all_list);
1067                 list_del(&l->all_list);
1068                 kmem_cache_free(block_cache, l);
1069         }
1070
1071         kfree(heap);
1072 }
1073
1074 /* nvmap_heap_create_group: adds the attribute_group grp to the heap kobject */
1075 int nvmap_heap_create_group(struct nvmap_heap *heap,
1076                             const struct attribute_group *grp)
1077 {
1078         return sysfs_create_group(&heap->dev.kobj, grp);
1079 }
1080
1081 /* nvmap_heap_remove_group: removes the attribute_group grp  */
1082 void nvmap_heap_remove_group(struct nvmap_heap *heap,
1083                              const struct attribute_group *grp)
1084 {
1085         sysfs_remove_group(&heap->dev.kobj, grp);
1086 }
1087
1088 int nvmap_heap_init(void)
1089 {
1090         BUG_ON(buddy_heap_cache != NULL);
1091         buddy_heap_cache = KMEM_CACHE(buddy_heap, 0);
1092         if (!buddy_heap_cache) {
1093                 pr_err("%s: unable to create buddy heap cache\n", __func__);
1094                 return -ENOMEM;
1095         }
1096
1097         block_cache = KMEM_CACHE(combo_block, 0);
1098         if (!block_cache) {
1099                 kmem_cache_destroy(buddy_heap_cache);
1100                 pr_err("%s: unable to create block cache\n", __func__);
1101                 return -ENOMEM;
1102         }
1103         return 0;
1104 }
1105
1106 void nvmap_heap_deinit(void)
1107 {
1108         if (buddy_heap_cache)
1109                 kmem_cache_destroy(buddy_heap_cache);
1110         if (block_cache)
1111                 kmem_cache_destroy(block_cache);
1112
1113         block_cache = NULL;
1114         buddy_heap_cache = NULL;
1115 }