summaryrefslogtreecommitdiffstats
path: root/drivers/gpu/nvgpu/common/mm/buddy_allocator.c
diff options
context:
space:
mode:
Diffstat (limited to 'drivers/gpu/nvgpu/common/mm/buddy_allocator.c')
-rw-r--r--drivers/gpu/nvgpu/common/mm/buddy_allocator.c1323
1 files changed, 1323 insertions, 0 deletions
diff --git a/drivers/gpu/nvgpu/common/mm/buddy_allocator.c b/drivers/gpu/nvgpu/common/mm/buddy_allocator.c
new file mode 100644
index 00000000..a2546e9d
--- /dev/null
+++ b/drivers/gpu/nvgpu/common/mm/buddy_allocator.c
@@ -0,0 +1,1323 @@
1/*
2 * Copyright (c) 2016-2017, NVIDIA CORPORATION. All rights reserved.
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
17 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
20 * DEALINGS IN THE SOFTWARE.
21 */
22
23#include <nvgpu/allocator.h>
24#include <nvgpu/kmem.h>
25#include <nvgpu/bug.h>
26#include <nvgpu/log2.h>
27#include <nvgpu/barrier.h>
28#include <nvgpu/mm.h>
29#include <nvgpu/vm.h>
30
31#include "buddy_allocator_priv.h"
32
33/* Some other buddy allocator functions. */
34static struct nvgpu_buddy *balloc_free_buddy(struct nvgpu_buddy_allocator *a,
35 u64 addr);
36static void balloc_coalesce(struct nvgpu_buddy_allocator *a,
37 struct nvgpu_buddy *b);
38static void __balloc_do_free_fixed(struct nvgpu_buddy_allocator *a,
39 struct nvgpu_fixed_alloc *falloc);
40
41/*
42 * This function is not present in older kernel's list.h code.
43 */
44#ifndef list_last_entry
45#define list_last_entry(ptr, type, member) \
46 list_entry((ptr)->prev, type, member)
47#endif
48
49/*
50 * GPU buddy allocator for various address spaces.
51 *
52 * Current limitations:
53 * o A fixed allocation could potentially be made that borders PDEs with
54 * different PTE sizes. This would require that fixed buffer to have
55 * different sized PTEs for different parts of the allocation. Probably
56 * best to just require PDE alignment for fixed address allocs.
57 *
58 * o It is currently possible to make an allocator that has a buddy alignment
59 * out of sync with the PDE block size alignment. A simple example is a
60 * 32GB address space starting at byte 1. Every buddy is shifted off by 1
61 * which means each buddy corresponf to more than one actual GPU page. The
62 * best way to fix this is probably just require PDE blocksize alignment
63 * for the start of the address space. At the moment all allocators are
64 * easily PDE aligned so this hasn't been a problem.
65 */
66
67/*
68 * Pick a suitable maximum order for this allocator.
69 *
70 * Hueristic: Just guessing that the best max order is the largest single
71 * block that will fit in the address space.
72 */
73static void balloc_compute_max_order(struct nvgpu_buddy_allocator *a)
74{
75 u64 true_max_order = ilog2(a->blks);
76
77 if (a->max_order == 0) {
78 a->max_order = true_max_order;
79 return;
80 }
81
82 if (a->max_order > true_max_order)
83 a->max_order = true_max_order;
84 if (a->max_order > GPU_BALLOC_MAX_ORDER)
85 a->max_order = GPU_BALLOC_MAX_ORDER;
86}
87
88/*
89 * Since we can only allocate in chucks of a->blk_size we need to trim off
90 * any excess data that is not aligned to a->blk_size.
91 */
92static void balloc_allocator_align(struct nvgpu_buddy_allocator *a)
93{
94 a->start = ALIGN(a->base, a->blk_size);
95 WARN_ON(a->start != a->base);
96 a->end = (a->base + a->length) & ~(a->blk_size - 1);
97 a->count = a->end - a->start;
98 a->blks = a->count >> a->blk_shift;
99}
100
101/*
102 * Pass NULL for parent if you want a top level buddy.
103 */
104static struct nvgpu_buddy *balloc_new_buddy(struct nvgpu_buddy_allocator *a,
105 struct nvgpu_buddy *parent,
106 u64 start, u64 order)
107{
108 struct nvgpu_buddy *new_buddy;
109
110 new_buddy = nvgpu_kmem_cache_alloc(a->buddy_cache);
111 if (!new_buddy)
112 return NULL;
113
114 memset(new_buddy, 0, sizeof(struct nvgpu_buddy));
115
116 new_buddy->parent = parent;
117 new_buddy->start = start;
118 new_buddy->order = order;
119 new_buddy->end = start + (1 << order) * a->blk_size;
120 new_buddy->pte_size = BALLOC_PTE_SIZE_ANY;
121
122 return new_buddy;
123}
124
125static void __balloc_buddy_list_add(struct nvgpu_buddy_allocator *a,
126 struct nvgpu_buddy *b,
127 struct nvgpu_list_node *list)
128{
129 if (buddy_is_in_list(b)) {
130 alloc_dbg(balloc_owner(a),
131 "Oops: adding added buddy (%llu:0x%llx)\n",
132 b->order, b->start);
133 BUG();
134 }
135
136 /*
137 * Add big PTE blocks to the tail, small to the head for GVA spaces.
138 * This lets the code that checks if there are available blocks check
139 * without cycling through the entire list.
140 */
141 if (a->flags & GPU_ALLOC_GVA_SPACE &&
142 b->pte_size == gmmu_page_size_big)
143 nvgpu_list_add_tail(&b->buddy_entry, list);
144 else
145 nvgpu_list_add(&b->buddy_entry, list);
146
147 buddy_set_in_list(b);
148}
149
150static void __balloc_buddy_list_rem(struct nvgpu_buddy_allocator *a,
151 struct nvgpu_buddy *b)
152{
153 if (!buddy_is_in_list(b)) {
154 alloc_dbg(balloc_owner(a),
155 "Oops: removing removed buddy (%llu:0x%llx)\n",
156 b->order, b->start);
157 BUG();
158 }
159
160 nvgpu_list_del(&b->buddy_entry);
161 buddy_clr_in_list(b);
162}
163
164/*
165 * Add a buddy to one of the buddy lists and deal with the necessary
166 * book keeping. Adds the buddy to the list specified by the buddy's order.
167 */
168static void balloc_blist_add(struct nvgpu_buddy_allocator *a,
169 struct nvgpu_buddy *b)
170{
171 __balloc_buddy_list_add(a, b, balloc_get_order_list(a, b->order));
172 a->buddy_list_len[b->order]++;
173}
174
175static void balloc_blist_rem(struct nvgpu_buddy_allocator *a,
176 struct nvgpu_buddy *b)
177{
178 __balloc_buddy_list_rem(a, b);
179 a->buddy_list_len[b->order]--;
180}
181
182static u64 balloc_get_order(struct nvgpu_buddy_allocator *a, u64 len)
183{
184 if (len == 0)
185 return 0;
186
187 len--;
188 len >>= a->blk_shift;
189
190 return fls(len);
191}
192
193static u64 __balloc_max_order_in(struct nvgpu_buddy_allocator *a,
194 u64 start, u64 end)
195{
196 u64 size = (end - start) >> a->blk_shift;
197
198 if (size > 0)
199 return min_t(u64, ilog2(size), a->max_order);
200 else
201 return GPU_BALLOC_MAX_ORDER;
202}
203
204/*
205 * Initialize the buddy lists.
206 */
207static int balloc_init_lists(struct nvgpu_buddy_allocator *a)
208{
209 int i;
210 u64 bstart, bend, order;
211 struct nvgpu_buddy *buddy;
212
213 bstart = a->start;
214 bend = a->end;
215
216 /* First make sure the LLs are valid. */
217 for (i = 0; i < GPU_BALLOC_ORDER_LIST_LEN; i++)
218 nvgpu_init_list_node(balloc_get_order_list(a, i));
219
220 while (bstart < bend) {
221 order = __balloc_max_order_in(a, bstart, bend);
222
223 buddy = balloc_new_buddy(a, NULL, bstart, order);
224 if (!buddy)
225 goto cleanup;
226
227 balloc_blist_add(a, buddy);
228 bstart += balloc_order_to_len(a, order);
229 }
230
231 return 0;
232
233cleanup:
234 for (i = 0; i < GPU_BALLOC_ORDER_LIST_LEN; i++) {
235 if (!nvgpu_list_empty(balloc_get_order_list(a, i))) {
236 buddy = nvgpu_list_first_entry(
237 balloc_get_order_list(a, i),
238 nvgpu_buddy, buddy_entry);
239 balloc_blist_rem(a, buddy);
240 nvgpu_kmem_cache_free(a->buddy_cache, buddy);
241 }
242 }
243
244 return -ENOMEM;
245}
246
247/*
248 * Clean up and destroy the passed allocator.
249 */
250static void nvgpu_buddy_allocator_destroy(struct nvgpu_allocator *__a)
251{
252 int i;
253 struct nvgpu_rbtree_node *node = NULL;
254 struct nvgpu_buddy *bud;
255 struct nvgpu_fixed_alloc *falloc;
256 struct nvgpu_buddy_allocator *a = __a->priv;
257
258 alloc_lock(__a);
259
260#ifdef CONFIG_DEBUG_FS
261 nvgpu_fini_alloc_debug(__a);
262#endif
263
264 /*
265 * Free the fixed allocs first.
266 */
267 nvgpu_rbtree_enum_start(0, &node, a->fixed_allocs);
268 while (node) {
269 falloc = nvgpu_fixed_alloc_from_rbtree_node(node);
270
271 nvgpu_rbtree_unlink(node, &a->fixed_allocs);
272 __balloc_do_free_fixed(a, falloc);
273
274 nvgpu_rbtree_enum_start(0, &node, a->fixed_allocs);
275 }
276
277 /*
278 * And now free all outstanding allocations.
279 */
280 nvgpu_rbtree_enum_start(0, &node, a->alloced_buddies);
281 while (node) {
282 bud = nvgpu_buddy_from_rbtree_node(node);
283
284 balloc_free_buddy(a, bud->start);
285 balloc_blist_add(a, bud);
286 balloc_coalesce(a, bud);
287
288 nvgpu_rbtree_enum_start(0, &node, a->alloced_buddies);
289 }
290
291 /*
292 * Now clean up the unallocated buddies.
293 */
294 for (i = 0; i < GPU_BALLOC_ORDER_LIST_LEN; i++) {
295 BUG_ON(a->buddy_list_alloced[i] != 0);
296
297 while (!nvgpu_list_empty(balloc_get_order_list(a, i))) {
298 bud = nvgpu_list_first_entry(
299 balloc_get_order_list(a, i),
300 nvgpu_buddy, buddy_entry);
301 balloc_blist_rem(a, bud);
302 nvgpu_kmem_cache_free(a->buddy_cache, bud);
303 }
304
305 if (a->buddy_list_len[i] != 0) {
306 nvgpu_info(__a->g,
307 "Excess buddies!!! (%d: %llu)\n",
308 i, a->buddy_list_len[i]);
309 BUG();
310 }
311 if (a->buddy_list_split[i] != 0) {
312 nvgpu_info(__a->g,
313 "Excess split nodes!!! (%d: %llu)\n",
314 i, a->buddy_list_split[i]);
315 BUG();
316 }
317 if (a->buddy_list_alloced[i] != 0) {
318 nvgpu_info(__a->g,
319 "Excess alloced nodes!!! (%d: %llu)\n",
320 i, a->buddy_list_alloced[i]);
321 BUG();
322 }
323 }
324
325 nvgpu_kmem_cache_destroy(a->buddy_cache);
326 nvgpu_kfree(nvgpu_alloc_to_gpu(__a), a);
327
328 alloc_unlock(__a);
329}
330
331/*
332 * Combine the passed buddy if possible. The pointer in @b may not be valid
333 * after this as the buddy may be freed.
334 *
335 * @a must be locked.
336 */
337static void balloc_coalesce(struct nvgpu_buddy_allocator *a,
338 struct nvgpu_buddy *b)
339{
340 struct nvgpu_buddy *parent;
341
342 if (buddy_is_alloced(b) || buddy_is_split(b))
343 return;
344
345 /*
346 * If both our buddy and I are both not allocated and not split then
347 * we can coalesce ourselves.
348 */
349 if (!b->buddy)
350 return;
351 if (buddy_is_alloced(b->buddy) || buddy_is_split(b->buddy))
352 return;
353
354 parent = b->parent;
355
356 balloc_blist_rem(a, b);
357 balloc_blist_rem(a, b->buddy);
358
359 buddy_clr_split(parent);
360 a->buddy_list_split[parent->order]--;
361 balloc_blist_add(a, parent);
362
363 /*
364 * Recursively coalesce as far as we can go.
365 */
366 balloc_coalesce(a, parent);
367
368 /* Clean up the remains. */
369 nvgpu_kmem_cache_free(a->buddy_cache, b->buddy);
370 nvgpu_kmem_cache_free(a->buddy_cache, b);
371}
372
373/*
374 * Split a buddy into two new buddies who are 1/2 the size of the parent buddy.
375 *
376 * @a must be locked.
377 */
378static int balloc_split_buddy(struct nvgpu_buddy_allocator *a,
379 struct nvgpu_buddy *b, int pte_size)
380{
381 struct nvgpu_buddy *left, *right;
382 u64 half;
383
384 left = balloc_new_buddy(a, b, b->start, b->order - 1);
385 if (!left)
386 return -ENOMEM;
387
388 half = (b->end - b->start) / 2;
389
390 right = balloc_new_buddy(a, b, b->start + half, b->order - 1);
391 if (!right) {
392 nvgpu_kmem_cache_free(a->buddy_cache, left);
393 return -ENOMEM;
394 }
395
396 buddy_set_split(b);
397 a->buddy_list_split[b->order]++;
398
399 b->left = left;
400 b->right = right;
401 left->buddy = right;
402 right->buddy = left;
403 left->parent = b;
404 right->parent = b;
405
406 /* PTE considerations. */
407 if (a->flags & GPU_ALLOC_GVA_SPACE &&
408 left->order <= a->pte_blk_order) {
409 left->pte_size = pte_size;
410 right->pte_size = pte_size;
411 }
412
413 balloc_blist_rem(a, b);
414 balloc_blist_add(a, left);
415 balloc_blist_add(a, right);
416
417 return 0;
418}
419
420/*
421 * Place the passed buddy into the RB tree for allocated buddies. Never fails
422 * unless the passed entry is a duplicate which is a bug.
423 *
424 * @a must be locked.
425 */
426static void balloc_alloc_buddy(struct nvgpu_buddy_allocator *a,
427 struct nvgpu_buddy *b)
428{
429 b->alloced_entry.key_start = b->start;
430 b->alloced_entry.key_end = b->end;
431
432 nvgpu_rbtree_insert(&b->alloced_entry, &a->alloced_buddies);
433
434 buddy_set_alloced(b);
435 a->buddy_list_alloced[b->order]++;
436}
437
438/*
439 * Remove the passed buddy from the allocated buddy RB tree. Returns the
440 * deallocated buddy for further processing.
441 *
442 * @a must be locked.
443 */
444static struct nvgpu_buddy *balloc_free_buddy(struct nvgpu_buddy_allocator *a,
445 u64 addr)
446{
447 struct nvgpu_rbtree_node *node = NULL;
448 struct nvgpu_buddy *bud;
449
450 nvgpu_rbtree_search(addr, &node, a->alloced_buddies);
451 if (!node)
452 return NULL;
453
454 bud = nvgpu_buddy_from_rbtree_node(node);
455
456 nvgpu_rbtree_unlink(node, &a->alloced_buddies);
457 buddy_clr_alloced(bud);
458 a->buddy_list_alloced[bud->order]--;
459
460 return bud;
461}
462
463/*
464 * Find a suitable buddy for the given order and PTE type (big or little).
465 */
466static struct nvgpu_buddy *__balloc_find_buddy(struct nvgpu_buddy_allocator *a,
467 u64 order, int pte_size)
468{
469 struct nvgpu_buddy *bud;
470
471 if (order > a->max_order ||
472 nvgpu_list_empty(balloc_get_order_list(a, order)))
473 return NULL;
474
475 if (a->flags & GPU_ALLOC_GVA_SPACE &&
476 pte_size == gmmu_page_size_big)
477 bud = nvgpu_list_last_entry(balloc_get_order_list(a, order),
478 nvgpu_buddy, buddy_entry);
479 else
480 bud = nvgpu_list_first_entry(balloc_get_order_list(a, order),
481 nvgpu_buddy, buddy_entry);
482
483 if (pte_size != BALLOC_PTE_SIZE_ANY &&
484 pte_size != bud->pte_size &&
485 bud->pte_size != BALLOC_PTE_SIZE_ANY)
486 return NULL;
487
488 return bud;
489}
490
491/*
492 * Allocate a suitably sized buddy. If no suitable buddy exists split higher
493 * order buddies until we have a suitable buddy to allocate.
494 *
495 * For PDE grouping add an extra check to see if a buddy is suitable: that the
496 * buddy exists in a PDE who's PTE size is reasonable
497 *
498 * @a must be locked.
499 */
500static u64 __balloc_do_alloc(struct nvgpu_buddy_allocator *a,
501 u64 order, int pte_size)
502{
503 u64 split_order;
504 struct nvgpu_buddy *bud = NULL;
505
506 split_order = order;
507 while (split_order <= a->max_order &&
508 !(bud = __balloc_find_buddy(a, split_order, pte_size)))
509 split_order++;
510
511 /* Out of memory! */
512 if (!bud)
513 return 0;
514
515 while (bud->order != order) {
516 if (balloc_split_buddy(a, bud, pte_size))
517 return 0; /* No mem... */
518 bud = bud->left;
519 }
520
521 balloc_blist_rem(a, bud);
522 balloc_alloc_buddy(a, bud);
523
524 return bud->start;
525}
526
527/*
528 * See if the passed range is actually available for allocation. If so, then
529 * return 1, otherwise return 0.
530 *
531 * TODO: Right now this uses the unoptimal approach of going through all
532 * outstanding allocations and checking their base/ends. This could be better.
533 */
534static int balloc_is_range_free(struct nvgpu_buddy_allocator *a,
535 u64 base, u64 end)
536{
537 struct nvgpu_rbtree_node *node = NULL;
538 struct nvgpu_buddy *bud;
539
540 nvgpu_rbtree_enum_start(0, &node, a->alloced_buddies);
541 if (!node)
542 return 1; /* No allocs yet. */
543
544 bud = nvgpu_buddy_from_rbtree_node(node);
545
546 while (bud->start < end) {
547 if ((bud->start > base && bud->start < end) ||
548 (bud->end > base && bud->end < end))
549 return 0;
550
551 nvgpu_rbtree_enum_next(&node, node);
552 if (!node)
553 break;
554 bud = nvgpu_buddy_from_rbtree_node(node);
555 }
556
557 return 1;
558}
559
560static void balloc_alloc_fixed(struct nvgpu_buddy_allocator *a,
561 struct nvgpu_fixed_alloc *f)
562{
563 f->alloced_entry.key_start = f->start;
564 f->alloced_entry.key_end = f->end;
565
566 nvgpu_rbtree_insert(&f->alloced_entry, &a->fixed_allocs);
567}
568
569/*
570 * Remove the passed buddy from the allocated buddy RB tree. Returns the
571 * deallocated buddy for further processing.
572 *
573 * @a must be locked.
574 */
575static struct nvgpu_fixed_alloc *balloc_free_fixed(
576 struct nvgpu_buddy_allocator *a, u64 addr)
577{
578 struct nvgpu_fixed_alloc *falloc;
579 struct nvgpu_rbtree_node *node = NULL;
580
581 nvgpu_rbtree_search(addr, &node, a->fixed_allocs);
582 if (!node)
583 return NULL;
584
585 falloc = nvgpu_fixed_alloc_from_rbtree_node(node);
586
587 nvgpu_rbtree_unlink(node, &a->fixed_allocs);
588
589 return falloc;
590}
591
592/*
593 * Find the parent range - doesn't necessarily need the parent to actually exist
594 * as a buddy. Finding an existing parent comes later...
595 */
596static void __balloc_get_parent_range(struct nvgpu_buddy_allocator *a,
597 u64 base, u64 order,
598 u64 *pbase, u64 *porder)
599{
600 u64 base_mask;
601 u64 shifted_base = balloc_base_shift(a, base);
602
603 order++;
604 base_mask = ~((a->blk_size << order) - 1);
605
606 shifted_base &= base_mask;
607
608 *pbase = balloc_base_unshift(a, shifted_base);
609 *porder = order;
610}
611
612/*
613 * Makes a buddy at the passed address. This will make all parent buddies
614 * necessary for this buddy to exist as well.
615 */
616static struct nvgpu_buddy *__balloc_make_fixed_buddy(
617 struct nvgpu_buddy_allocator *a, u64 base, u64 order, int pte_size)
618{
619 struct nvgpu_buddy *bud = NULL;
620 struct nvgpu_list_node *order_list;
621 u64 cur_order = order, cur_base = base;
622
623 /*
624 * Algo:
625 * 1. Keep jumping up a buddy order until we find the real buddy that
626 * this buddy exists in.
627 * 2. Then work our way down through the buddy tree until we hit a dead
628 * end.
629 * 3. Start splitting buddies until we split to the one we need to
630 * make.
631 */
632 while (cur_order <= a->max_order) {
633 int found = 0;
634
635 order_list = balloc_get_order_list(a, cur_order);
636 nvgpu_list_for_each_entry(bud, order_list,
637 nvgpu_buddy, buddy_entry) {
638 if (bud->start == cur_base) {
639 /*
640 * Make sure page size matches if it's smaller
641 * than a PDE sized buddy.
642 */
643 if (bud->order <= a->pte_blk_order &&
644 bud->pte_size != BALLOC_PTE_SIZE_ANY &&
645 bud->pte_size != pte_size) {
646 /* Welp, that's the end of that. */
647 alloc_dbg(balloc_owner(a),
648 "Fixed buddy PTE "
649 "size mismatch!\n");
650 return NULL;
651 }
652
653 found = 1;
654 break;
655 }
656 }
657
658 if (found)
659 break;
660
661 __balloc_get_parent_range(a, cur_base, cur_order,
662 &cur_base, &cur_order);
663 }
664
665 if (cur_order > a->max_order) {
666 alloc_dbg(balloc_owner(a), "No buddy for range ???\n");
667 return NULL;
668 }
669
670 /* Split this buddy as necessary until we get the target buddy. */
671 while (bud->start != base || bud->order != order) {
672 if (balloc_split_buddy(a, bud, pte_size)) {
673 alloc_dbg(balloc_owner(a),
674 "split buddy failed? {0x%llx, %llu}\n",
675 bud->start, bud->order);
676 balloc_coalesce(a, bud);
677 return NULL;
678 }
679
680 if (base < bud->right->start)
681 bud = bud->left;
682 else
683 bud = bud->right;
684
685 }
686
687 return bud;
688}
689
690static u64 __balloc_do_alloc_fixed(struct nvgpu_buddy_allocator *a,
691 struct nvgpu_fixed_alloc *falloc,
692 u64 base, u64 len, int pte_size)
693{
694 u64 shifted_base, inc_base;
695 u64 align_order;
696
697 shifted_base = balloc_base_shift(a, base);
698 if (shifted_base == 0)
699 align_order = __fls(len >> a->blk_shift);
700 else
701 align_order = min_t(u64,
702 __ffs(shifted_base >> a->blk_shift),
703 __fls(len >> a->blk_shift));
704
705 if (align_order > a->max_order) {
706 alloc_dbg(balloc_owner(a),
707 "Align order too big: %llu > %llu\n",
708 align_order, a->max_order);
709 return 0;
710 }
711
712 /*
713 * Generate a list of buddies that satisfy this allocation.
714 */
715 inc_base = shifted_base;
716 while (inc_base < (shifted_base + len)) {
717 u64 order_len = balloc_order_to_len(a, align_order);
718 u64 remaining;
719 struct nvgpu_buddy *bud;
720
721 bud = __balloc_make_fixed_buddy(a,
722 balloc_base_unshift(a, inc_base),
723 align_order, pte_size);
724 if (!bud) {
725 alloc_dbg(balloc_owner(a),
726 "Fixed buddy failed: {0x%llx, %llu}!\n",
727 balloc_base_unshift(a, inc_base),
728 align_order);
729 goto err_and_cleanup;
730 }
731
732 balloc_blist_rem(a, bud);
733 balloc_alloc_buddy(a, bud);
734 __balloc_buddy_list_add(a, bud, &falloc->buddies);
735
736 /* Book keeping. */
737 inc_base += order_len;
738 remaining = (shifted_base + len) - inc_base;
739 align_order = __ffs(inc_base >> a->blk_shift);
740
741 /* If we don't have much left - trim down align_order. */
742 if (balloc_order_to_len(a, align_order) > remaining)
743 align_order = __balloc_max_order_in(a, inc_base,
744 inc_base + remaining);
745 }
746
747 return base;
748
749err_and_cleanup:
750 while (!nvgpu_list_empty(&falloc->buddies)) {
751 struct nvgpu_buddy *bud = nvgpu_list_first_entry(
752 &falloc->buddies,
753 nvgpu_buddy, buddy_entry);
754
755 __balloc_buddy_list_rem(a, bud);
756 balloc_free_buddy(a, bud->start);
757 nvgpu_kmem_cache_free(a->buddy_cache, bud);
758 }
759
760 return 0;
761}
762
763static void __balloc_do_free_fixed(struct nvgpu_buddy_allocator *a,
764 struct nvgpu_fixed_alloc *falloc)
765{
766 struct nvgpu_buddy *bud;
767
768 while (!nvgpu_list_empty(&falloc->buddies)) {
769 bud = nvgpu_list_first_entry(&falloc->buddies,
770 nvgpu_buddy,
771 buddy_entry);
772 __balloc_buddy_list_rem(a, bud);
773
774 balloc_free_buddy(a, bud->start);
775 balloc_blist_add(a, bud);
776 a->bytes_freed += balloc_order_to_len(a, bud->order);
777
778 /*
779 * Attemp to defrag the allocation.
780 */
781 balloc_coalesce(a, bud);
782 }
783
784 nvgpu_kfree(nvgpu_alloc_to_gpu(a->owner), falloc);
785}
786
787/*
788 * Allocate memory from the passed allocator.
789 */
790static u64 nvgpu_buddy_balloc(struct nvgpu_allocator *__a, u64 len)
791{
792 u64 order, addr;
793 int pte_size;
794 struct nvgpu_buddy_allocator *a = __a->priv;
795
796 alloc_lock(__a);
797
798 order = balloc_get_order(a, len);
799
800 if (order > a->max_order) {
801 alloc_unlock(__a);
802 alloc_dbg(balloc_owner(a), "Alloc fail\n");
803 return 0;
804 }
805
806 if (a->flags & GPU_ALLOC_GVA_SPACE)
807 pte_size = __get_pte_size(a->vm, 0, len);
808 else
809 pte_size = BALLOC_PTE_SIZE_ANY;
810
811 addr = __balloc_do_alloc(a, order, pte_size);
812
813 if (addr) {
814 a->bytes_alloced += len;
815 a->bytes_alloced_real += balloc_order_to_len(a, order);
816 alloc_dbg(balloc_owner(a),
817 "Alloc 0x%-10llx %3lld:0x%-10llx pte_size=%s\n",
818 addr, order, len,
819 pte_size == gmmu_page_size_big ? "big" :
820 pte_size == gmmu_page_size_small ? "small" :
821 "NA/any");
822 } else {
823 alloc_dbg(balloc_owner(a), "Alloc failed: no mem!\n");
824 }
825
826 a->alloc_made = 1;
827
828 alloc_unlock(__a);
829
830 return addr;
831}
832
833/*
834 * Requires @__a to be locked.
835 */
836static u64 __nvgpu_balloc_fixed_buddy(struct nvgpu_allocator *__a,
837 u64 base, u64 len, u32 page_size)
838{
839 int pte_size = BALLOC_PTE_SIZE_ANY;
840 u64 ret, real_bytes = 0;
841 struct nvgpu_buddy *bud;
842 struct nvgpu_fixed_alloc *falloc = NULL;
843 struct nvgpu_buddy_allocator *a = __a->priv;
844
845 /* If base isn't aligned to an order 0 block, fail. */
846 if (base & (a->blk_size - 1))
847 goto fail;
848
849 if (len == 0)
850 goto fail;
851
852 /* Check that the page size is valid. */
853 if (a->flags & GPU_ALLOC_GVA_SPACE && a->vm->big_pages) {
854 if (page_size == a->vm->big_page_size)
855 pte_size = gmmu_page_size_big;
856 else if (page_size == SZ_4K)
857 pte_size = gmmu_page_size_small;
858 else
859 goto fail;
860 }
861
862 falloc = nvgpu_kmalloc(nvgpu_alloc_to_gpu(__a), sizeof(*falloc));
863 if (!falloc)
864 goto fail;
865
866 nvgpu_init_list_node(&falloc->buddies);
867 falloc->start = base;
868 falloc->end = base + len;
869
870 if (!balloc_is_range_free(a, base, base + len)) {
871 alloc_dbg(balloc_owner(a),
872 "Range not free: 0x%llx -> 0x%llx\n",
873 base, base + len);
874 goto fail_unlock;
875 }
876
877 ret = __balloc_do_alloc_fixed(a, falloc, base, len, pte_size);
878 if (!ret) {
879 alloc_dbg(balloc_owner(a),
880 "Alloc-fixed failed ?? 0x%llx -> 0x%llx\n",
881 base, base + len);
882 goto fail_unlock;
883 }
884
885 balloc_alloc_fixed(a, falloc);
886
887 nvgpu_list_for_each_entry(bud, &falloc->buddies,
888 nvgpu_buddy, buddy_entry)
889 real_bytes += (bud->end - bud->start);
890
891 a->bytes_alloced += len;
892 a->bytes_alloced_real += real_bytes;
893
894 alloc_dbg(balloc_owner(a), "Alloc (fixed) 0x%llx\n", base);
895
896 return base;
897
898fail_unlock:
899 alloc_unlock(__a);
900fail:
901 nvgpu_kfree(nvgpu_alloc_to_gpu(__a), falloc);
902 return 0;
903}
904
905/*
906 * Allocate a fixed address allocation. The address of the allocation is @base
907 * and the length is @len. This is not a typical buddy allocator operation and
908 * as such has a high posibility of failure if the address space is heavily in
909 * use.
910 *
911 * Please do not use this function unless _absolutely_ necessary.
912 */
913static u64 nvgpu_balloc_fixed_buddy(struct nvgpu_allocator *__a,
914 u64 base, u64 len, u32 page_size)
915{
916 u64 alloc;
917 struct nvgpu_buddy_allocator *a = __a->priv;
918
919 alloc_lock(__a);
920 alloc = __nvgpu_balloc_fixed_buddy(__a, base, len, page_size);
921 a->alloc_made = 1;
922 alloc_unlock(__a);
923
924 return alloc;
925}
926
927/*
928 * Free the passed allocation.
929 */
930static void nvgpu_buddy_bfree(struct nvgpu_allocator *__a, u64 addr)
931{
932 struct nvgpu_buddy *bud;
933 struct nvgpu_fixed_alloc *falloc;
934 struct nvgpu_buddy_allocator *a = __a->priv;
935
936 if (!addr)
937 return;
938
939 alloc_lock(__a);
940
941 /*
942 * First see if this is a fixed alloc. If not fall back to a regular
943 * buddy.
944 */
945 falloc = balloc_free_fixed(a, addr);
946 if (falloc) {
947 __balloc_do_free_fixed(a, falloc);
948 goto done;
949 }
950
951 bud = balloc_free_buddy(a, addr);
952 if (!bud)
953 goto done;
954
955 balloc_blist_add(a, bud);
956 a->bytes_freed += balloc_order_to_len(a, bud->order);
957
958 /*
959 * Attemp to defrag the allocation.
960 */
961 balloc_coalesce(a, bud);
962
963done:
964 alloc_unlock(__a);
965 alloc_dbg(balloc_owner(a), "Free 0x%llx\n", addr);
966 return;
967}
968
969static bool nvgpu_buddy_reserve_is_possible(struct nvgpu_buddy_allocator *a,
970 struct nvgpu_alloc_carveout *co)
971{
972 struct nvgpu_alloc_carveout *tmp;
973 u64 co_base, co_end;
974
975 co_base = co->base;
976 co_end = co->base + co->length;
977
978 /*
979 * Not the fastest approach but we should not have that many carveouts
980 * for any reasonable allocator.
981 */
982 nvgpu_list_for_each_entry(tmp, &a->co_list,
983 nvgpu_alloc_carveout, co_entry) {
984 if ((co_base >= tmp->base &&
985 co_base < (tmp->base + tmp->length)) ||
986 (co_end >= tmp->base &&
987 co_end < (tmp->base + tmp->length)))
988 return false;
989 }
990
991 return true;
992}
993
994/*
995 * Carveouts can only be reserved before any regular allocations have been
996 * made.
997 */
998static int nvgpu_buddy_reserve_co(struct nvgpu_allocator *__a,
999 struct nvgpu_alloc_carveout *co)
1000{
1001 struct nvgpu_buddy_allocator *a = __a->priv;
1002 u64 addr;
1003 int err = 0;
1004
1005 if (co->base < a->start || (co->base + co->length) > a->end ||
1006 a->alloc_made)
1007 return -EINVAL;
1008
1009 alloc_lock(__a);
1010
1011 if (!nvgpu_buddy_reserve_is_possible(a, co)) {
1012 err = -EBUSY;
1013 goto done;
1014 }
1015
1016 /* Should not be possible to fail... */
1017 addr = __nvgpu_balloc_fixed_buddy(__a, co->base, co->length, 0);
1018 if (!addr) {
1019 err = -ENOMEM;
1020 nvgpu_warn(__a->g,
1021 "%s: Failed to reserve a valid carveout!\n",
1022 __func__);
1023 goto done;
1024 }
1025
1026 nvgpu_list_add(&co->co_entry, &a->co_list);
1027
1028done:
1029 alloc_unlock(__a);
1030 return err;
1031}
1032
1033/*
1034 * Carveouts can be release at any time.
1035 */
1036static void nvgpu_buddy_release_co(struct nvgpu_allocator *__a,
1037 struct nvgpu_alloc_carveout *co)
1038{
1039 alloc_lock(__a);
1040
1041 nvgpu_list_del(&co->co_entry);
1042 nvgpu_free(__a, co->base);
1043
1044 alloc_unlock(__a);
1045}
1046
1047static u64 nvgpu_buddy_alloc_length(struct nvgpu_allocator *a)
1048{
1049 struct nvgpu_buddy_allocator *ba = a->priv;
1050
1051 return ba->length;
1052}
1053
1054static u64 nvgpu_buddy_alloc_base(struct nvgpu_allocator *a)
1055{
1056 struct nvgpu_buddy_allocator *ba = a->priv;
1057
1058 return ba->start;
1059}
1060
1061static int nvgpu_buddy_alloc_inited(struct nvgpu_allocator *a)
1062{
1063 struct nvgpu_buddy_allocator *ba = a->priv;
1064 int inited = ba->initialized;
1065
1066 nvgpu_smp_rmb();
1067 return inited;
1068}
1069
1070static u64 nvgpu_buddy_alloc_end(struct nvgpu_allocator *a)
1071{
1072 struct nvgpu_buddy_allocator *ba = a->priv;
1073
1074 return ba->end;
1075}
1076
1077static u64 nvgpu_buddy_alloc_space(struct nvgpu_allocator *a)
1078{
1079 struct nvgpu_buddy_allocator *ba = a->priv;
1080 u64 space;
1081
1082 alloc_lock(a);
1083 space = ba->end - ba->start -
1084 (ba->bytes_alloced_real - ba->bytes_freed);
1085 alloc_unlock(a);
1086
1087 return space;
1088}
1089
1090#ifdef __KERNEL__
1091/*
1092 * Print the buddy allocator top level stats. If you pass @s as NULL then the
1093 * stats are printed to the kernel log. This lets this code be used for
1094 * debugging purposes internal to the allocator.
1095 */
1096static void nvgpu_buddy_print_stats(struct nvgpu_allocator *__a,
1097 struct seq_file *s, int lock)
1098{
1099 int i = 0;
1100 struct nvgpu_rbtree_node *node = NULL;
1101 struct nvgpu_fixed_alloc *falloc;
1102 struct nvgpu_alloc_carveout *tmp;
1103 struct nvgpu_buddy_allocator *a = __a->priv;
1104
1105 __alloc_pstat(s, __a, "base = %llu, limit = %llu, blk_size = %llu\n",
1106 a->base, a->length, a->blk_size);
1107 __alloc_pstat(s, __a, "Internal params:\n");
1108 __alloc_pstat(s, __a, " start = 0x%llx\n", a->start);
1109 __alloc_pstat(s, __a, " end = 0x%llx\n", a->end);
1110 __alloc_pstat(s, __a, " count = 0x%llx\n", a->count);
1111 __alloc_pstat(s, __a, " blks = 0x%llx\n", a->blks);
1112 __alloc_pstat(s, __a, " max_order = %llu\n", a->max_order);
1113
1114 if (lock)
1115 alloc_lock(__a);
1116
1117 if (!nvgpu_list_empty(&a->co_list)) {
1118 __alloc_pstat(s, __a, "\n");
1119 __alloc_pstat(s, __a, "Carveouts:\n");
1120 nvgpu_list_for_each_entry(tmp, &a->co_list,
1121 nvgpu_alloc_carveout, co_entry)
1122 __alloc_pstat(s, __a,
1123 " CO %2d: %-20s 0x%010llx + 0x%llx\n",
1124 i++, tmp->name, tmp->base, tmp->length);
1125 }
1126
1127 __alloc_pstat(s, __a, "\n");
1128 __alloc_pstat(s, __a, "Buddy blocks:\n");
1129 __alloc_pstat(s, __a, " Order Free Alloced Split\n");
1130 __alloc_pstat(s, __a, " ----- ---- ------- -----\n");
1131
1132 for (i = a->max_order; i >= 0; i--) {
1133 if (a->buddy_list_len[i] == 0 &&
1134 a->buddy_list_alloced[i] == 0 &&
1135 a->buddy_list_split[i] == 0)
1136 continue;
1137
1138 __alloc_pstat(s, __a, " %3d %-7llu %-9llu %llu\n", i,
1139 a->buddy_list_len[i],
1140 a->buddy_list_alloced[i],
1141 a->buddy_list_split[i]);
1142 }
1143
1144 __alloc_pstat(s, __a, "\n");
1145
1146 nvgpu_rbtree_enum_start(0, &node, a->fixed_allocs);
1147 i = 1;
1148 while (node) {
1149 falloc = nvgpu_fixed_alloc_from_rbtree_node(node);
1150
1151 __alloc_pstat(s, __a, "Fixed alloc (%d): [0x%llx -> 0x%llx]\n",
1152 i, falloc->start, falloc->end);
1153
1154 nvgpu_rbtree_enum_next(&node, a->fixed_allocs);
1155 }
1156
1157 __alloc_pstat(s, __a, "\n");
1158 __alloc_pstat(s, __a, "Bytes allocated: %llu\n",
1159 a->bytes_alloced);
1160 __alloc_pstat(s, __a, "Bytes allocated (real): %llu\n",
1161 a->bytes_alloced_real);
1162 __alloc_pstat(s, __a, "Bytes freed: %llu\n",
1163 a->bytes_freed);
1164
1165 if (lock)
1166 alloc_unlock(__a);
1167}
1168#endif
1169
1170static const struct nvgpu_allocator_ops buddy_ops = {
1171 .alloc = nvgpu_buddy_balloc,
1172 .free = nvgpu_buddy_bfree,
1173
1174 .alloc_fixed = nvgpu_balloc_fixed_buddy,
1175 /* .free_fixed not needed. */
1176
1177 .reserve_carveout = nvgpu_buddy_reserve_co,
1178 .release_carveout = nvgpu_buddy_release_co,
1179
1180 .base = nvgpu_buddy_alloc_base,
1181 .length = nvgpu_buddy_alloc_length,
1182 .end = nvgpu_buddy_alloc_end,
1183 .inited = nvgpu_buddy_alloc_inited,
1184 .space = nvgpu_buddy_alloc_space,
1185
1186 .fini = nvgpu_buddy_allocator_destroy,
1187
1188#ifdef __KERNEL__
1189 .print_stats = nvgpu_buddy_print_stats,
1190#endif
1191};
1192
1193/*
1194 * Initialize a buddy allocator. Returns 0 on success. This allocator does
1195 * not necessarily manage bytes. It manages distinct ranges of resources. This
1196 * allows the allocator to work for things like comp_tags, semaphores, etc.
1197 *
1198 * @allocator: Ptr to an allocator struct to init.
1199 * @vm: GPU VM to associate this allocator with. Can be NULL. Will be used to
1200 * get PTE size for GVA spaces.
1201 * @name: Name of the allocator. Doesn't have to be static storage.
1202 * @base: The base address of the resource pool being managed.
1203 * @size: Number of resources in the pool.
1204 * @blk_size: Minimum number of resources to allocate at once. For things like
1205 * semaphores this is 1. For GVA this might be as much as 64k. This
1206 * corresponds to order 0. Must be power of 2.
1207 * @max_order: Pick a maximum order. If you leave this as 0, the buddy allocator
1208 * will try and pick a reasonable max order.
1209 * @flags: Extra flags necessary. See GPU_BALLOC_*.
1210 */
1211int __nvgpu_buddy_allocator_init(struct gk20a *g, struct nvgpu_allocator *__a,
1212 struct vm_gk20a *vm, const char *name,
1213 u64 base, u64 size, u64 blk_size,
1214 u64 max_order, u64 flags)
1215{
1216 int err;
1217 u64 pde_size;
1218 struct nvgpu_buddy_allocator *a;
1219
1220 /* blk_size must be greater than 0 and a power of 2. */
1221 if (blk_size == 0)
1222 return -EINVAL;
1223 if (blk_size & (blk_size - 1))
1224 return -EINVAL;
1225
1226 if (max_order > GPU_BALLOC_MAX_ORDER)
1227 return -EINVAL;
1228
1229 /* If this is to manage a GVA space we need a VM. */
1230 if (flags & GPU_ALLOC_GVA_SPACE && !vm)
1231 return -EINVAL;
1232
1233 a = nvgpu_kzalloc(g, sizeof(struct nvgpu_buddy_allocator));
1234 if (!a)
1235 return -ENOMEM;
1236
1237 err = __nvgpu_alloc_common_init(__a, g, name, a, false, &buddy_ops);
1238 if (err)
1239 goto fail;
1240
1241 a->base = base;
1242 a->length = size;
1243 a->blk_size = blk_size;
1244 a->blk_shift = __ffs(blk_size);
1245 a->owner = __a;
1246
1247 /*
1248 * If base is 0 then modfy base to be the size of one block so that we
1249 * can return errors by returning addr == 0.
1250 */
1251 if (a->base == 0) {
1252 a->base = a->blk_size;
1253 a->length -= a->blk_size;
1254 }
1255
1256 a->vm = vm;
1257 if (flags & GPU_ALLOC_GVA_SPACE) {
1258 pde_size = ((u64)vm->big_page_size) << 10;
1259 a->pte_blk_order = balloc_get_order(a, pde_size);
1260 }
1261
1262 /*
1263 * When we have a GVA space with big_pages enabled the size and base
1264 * must be PDE aligned. If big_pages are not enabled then this
1265 * requirement is not necessary.
1266 */
1267 if (flags & GPU_ALLOC_GVA_SPACE && vm->big_pages &&
1268 (base & ((vm->big_page_size << 10) - 1) ||
1269 size & ((vm->big_page_size << 10) - 1)))
1270 return -EINVAL;
1271
1272 a->flags = flags;
1273 a->max_order = max_order;
1274
1275 balloc_allocator_align(a);
1276 balloc_compute_max_order(a);
1277
1278 a->buddy_cache = nvgpu_kmem_cache_create(g, sizeof(struct nvgpu_buddy));
1279 if (!a->buddy_cache) {
1280 err = -ENOMEM;
1281 goto fail;
1282 }
1283
1284 a->alloced_buddies = NULL;
1285 a->fixed_allocs = NULL;
1286 nvgpu_init_list_node(&a->co_list);
1287 err = balloc_init_lists(a);
1288 if (err)
1289 goto fail;
1290
1291 nvgpu_smp_wmb();
1292 a->initialized = 1;
1293
1294#ifdef CONFIG_DEBUG_FS
1295 nvgpu_init_alloc_debug(g, __a);
1296#endif
1297 alloc_dbg(__a, "New allocator: type buddy\n");
1298 alloc_dbg(__a, " base 0x%llx\n", a->base);
1299 alloc_dbg(__a, " size 0x%llx\n", a->length);
1300 alloc_dbg(__a, " blk_size 0x%llx\n", a->blk_size);
1301 if (flags & GPU_ALLOC_GVA_SPACE)
1302 alloc_dbg(balloc_owner(a),
1303 " pde_size 0x%llx\n",
1304 balloc_order_to_len(a, a->pte_blk_order));
1305 alloc_dbg(__a, " max_order %llu\n", a->max_order);
1306 alloc_dbg(__a, " flags 0x%llx\n", a->flags);
1307
1308 return 0;
1309
1310fail:
1311 if (a->buddy_cache)
1312 nvgpu_kmem_cache_destroy(a->buddy_cache);
1313 nvgpu_kfree(g, a);
1314 return err;
1315}
1316
1317int nvgpu_buddy_allocator_init(struct gk20a *g, struct nvgpu_allocator *a,
1318 const char *name, u64 base, u64 size,
1319 u64 blk_size, u64 flags)
1320{
1321 return __nvgpu_buddy_allocator_init(g, a, NULL, name,
1322 base, size, blk_size, 0, 0);
1323}
generated by cgit v1.2.2 (git 2.25.0) at 2024-08-22 14:22:47 -0400