xref: /linux/drivers/gpu/buddy.c (revision 4dd10fbbeb9c33709edc89916e19c03c780a0751)
1 // SPDX-License-Identifier: MIT
2 /*
3  * Copyright © 2021 Intel Corporation
4  */
5 
6 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
7 
8 #include <linux/bug.h>
9 #include <linux/export.h>
10 #include <linux/kmemleak.h>
11 #include <linux/module.h>
12 #include <linux/sizes.h>
13 #include <linux/slab.h>
14 
15 #include <linux/gpu_buddy.h>
16 
17 /**
18  * gpu_buddy_assert - assert a condition in the buddy allocator
19  * @condition: condition expected to be true
20  *
21  * When CONFIG_KUNIT is enabled, evaluates @condition and, if false, triggers
22  * a WARN_ON() and also calls kunit_fail_current_test() so that any running
23  * kunit test is properly marked as failed. The stringified condition is
24  * included in the failure message for easy identification.
25  *
26  * When CONFIG_KUNIT is not enabled, this reduces to WARN_ON() so production
27  * builds retain the same warning semantics as before.
28  */
29 #if IS_ENABLED(CONFIG_KUNIT)
30 #include <kunit/test-bug.h>
31 #define gpu_buddy_assert(condition) do {						\
32 	if (WARN_ON(!(condition)))						\
33 		kunit_fail_current_test("gpu_buddy_assert(" #condition ")");	\
34 } while (0)
35 #else
36 #define gpu_buddy_assert(condition) WARN_ON(!(condition))
37 #endif
38 
39 static struct kmem_cache *slab_blocks;
40 static struct kmem_cache *slab_extents;
41 
42 /*
43  * Dirty tracker
44  * -------------
45  *
46  * The dirty tracker maintains an augmented interval rbtree of contiguous
47  * dirty address ranges, decoupled from the buddy free trees.
48  * Each node covers a maximal coalesced run; adjacent extents are merged
49  * on insertion so the tree always holds the smallest possible number of
50  * extents.  The augmentation field @subtree_max_size lets the allocator
51  * locate the largest dirty extent in O(log E).
52  *
53  * Free trees (mm->free_tree[])
54  * ----------------------------
55  *
56  * Per-order augmented rbtrees of FREE buddy blocks, keyed by offset.
57  * Every node carries:
58  *   - subtree_max_alignment: largest natural alignment in the subtree,
59  *     used by aligned/range allocations to skip unsuitable subtrees in
60  *     O(log N).
61  *   - subtree_block_state: the highest clear class (DIRTY < MIXED < CLEAR)
62  *     of any block in the subtree, maintained as a max augment. A value of
63  *     >= MIXED means a clear-or-mixed block exists; == CLEAR means a
64  *     fully-clear block exists.
65  *
66  * Block classes
67  * -------------
68  *
69  * Each FREE block falls into one of three classes, determined in
70  * mark_free() by querying the dirty tracker for the block's range:
71  *
72  *   clear   -- HEADER_CLEAR set; no dirty extent overlaps the range.
73  *   mixed   -- HEADER_CLEAR unset; range has both dirty and clear bytes.
74  *   dirty   -- HEADER_CLEAR unset; range is fully dirty.
75  *
76  * Clear allocation
77  * ----------------
78  *
79  * A clear (CLEAR_ALLOCATION) request prefers clear -> mixed -> dirty.
80  * Climbing from the requested order up to max_order, rbtree_last_clear_free_block()
81  * returns, in one O(log N) descent per order, the right-most clear-or-mixed block
82  * (fully-clear preferred over mixed) at the lowest order whose free tree contains
83  * such a block. Only if no clear-or-mixed block exists at any order >= the
84  * requested one does it fall back to a dirty block.
85  *
86  * Clear state is reported to the driver per whole block via HEADER_CLEAR, so a
87  * fully-clear block of the requested order lets the driver skip the clear pass.
88  *
89  * The effective allocation preference depends on how the driver handles
90  * freed blocks:
91  *
92  *   1) Never clear on free:
93  *      No free block contains clear bytes, so clear allocations always
94  *      fall back to dirty blocks.
95  *
96  *   2) Always clear on free:
97  *      Freed blocks become clear while untouched blocks remain dirty.
98  *      Merging clear and dirty buddies produces mixed blocks, which are
99  *      reclassified when split. Over time, clear blocks become dominant,
100  *      so clear allocations are typically satisfied from clear blocks,
101  *      following a clear -> mixed -> dirty preference.
102  *
103  *   3) Selective clear on free:
104  *      For each order examined, fully-clear blocks are preferred over
105  *      mixed blocks, and mixed blocks are preferred over dirty blocks.
106  *      If a clear or mixed block is found at an order, it is selected
107  *      without searching higher orders. Dirty blocks are used only when
108  *      no clear or mixed block exists at any eligible order.
109  */
110 
111 static u64 extent_size(struct gpu_dirty_extent *dirty_extent)
112 {
113 	return dirty_extent->end - dirty_extent->start;
114 }
115 
116 RB_DECLARE_CALLBACKS_MAX(static, gpu_dirty_augment_cb,
117 			 struct gpu_dirty_extent, rb,
118 			 u64, subtree_max_size,
119 			 extent_size)
120 
121 static struct gpu_dirty_extent *extent_alloc(struct gpu_dirty_tracker *dirty_tracker)
122 {
123 	return kmem_cache_alloc(slab_extents, GFP_KERNEL);
124 }
125 
126 static void extent_free(struct gpu_dirty_tracker *dirty_tracker,
127 			struct gpu_dirty_extent *dirty_extent)
128 {
129 	kmem_cache_free(slab_extents, dirty_extent);
130 }
131 
132 /* Return the rightmost extent whose start is strictly below @offset. */
133 static struct gpu_dirty_extent *
134 prev_extent(struct gpu_dirty_tracker *dirty_tracker, u64 offset)
135 {
136 	struct rb_node *rb = dirty_tracker->root.rb_node;
137 	struct gpu_dirty_extent *dirty_extent = NULL;
138 
139 	while (rb) {
140 		struct gpu_dirty_extent *tmp_extent =
141 			rb_entry(rb, struct gpu_dirty_extent, rb);
142 
143 		if (tmp_extent->start < offset) {
144 			dirty_extent = tmp_extent;
145 			rb = rb->rb_right;
146 		} else {
147 			rb = rb->rb_left;
148 		}
149 	}
150 
151 	return dirty_extent;
152 }
153 
154 /* Return the leftmost extent whose start is at or above @offset. */
155 static struct gpu_dirty_extent *
156 next_extent(struct gpu_dirty_tracker *dirty_tracker, u64 offset)
157 {
158 	struct rb_node *rb = dirty_tracker->root.rb_node;
159 	struct gpu_dirty_extent *dirty_extent = NULL;
160 
161 	while (rb) {
162 		struct gpu_dirty_extent *tmp_extent =
163 			rb_entry(rb, struct gpu_dirty_extent, rb);
164 
165 		if (tmp_extent->start >= offset) {
166 			dirty_extent = tmp_extent;
167 			rb = rb->rb_left;
168 		} else {
169 			rb = rb->rb_right;
170 		}
171 	}
172 
173 	return dirty_extent;
174 }
175 
176 static void insert_extent(struct gpu_dirty_tracker *dirty_tracker,
177 			  struct gpu_dirty_extent *dirty_extent)
178 {
179 	struct rb_node **link = &dirty_tracker->root.rb_node;
180 	struct rb_node *parent = NULL;
181 	u64 size = extent_size(dirty_extent);
182 
183 	while (*link) {
184 		struct gpu_dirty_extent *tmp_extent;
185 
186 		parent = *link;
187 		tmp_extent = rb_entry(parent, struct gpu_dirty_extent, rb);
188 
189 		if (tmp_extent->subtree_max_size < size)
190 			tmp_extent->subtree_max_size = size;
191 
192 		if (dirty_extent->start < tmp_extent->start)
193 			link = &parent->rb_left;
194 		else
195 			link = &parent->rb_right;
196 	}
197 
198 	dirty_extent->subtree_max_size = size;
199 	rb_link_node(&dirty_extent->rb, parent, link);
200 	rb_insert_augmented(&dirty_extent->rb, &dirty_tracker->root, &gpu_dirty_augment_cb);
201 }
202 
203 static void remove_extent(struct gpu_dirty_tracker *dirty_tracker,
204 			  struct gpu_dirty_extent *dirty_extent)
205 {
206 	rb_erase_augmented(&dirty_extent->rb, &dirty_tracker->root, &gpu_dirty_augment_cb);
207 	RB_CLEAR_NODE(&dirty_extent->rb);
208 }
209 
210 static void gpu_dirty_tracker_init(struct gpu_dirty_tracker *dirty_tracker)
211 {
212 	dirty_tracker->root = RB_ROOT;
213 	dirty_tracker->total_dirty = 0;
214 }
215 
216 static void gpu_dirty_tracker_empty(struct gpu_dirty_tracker *dirty_tracker)
217 {
218 	struct rb_node *rb;
219 
220 	while ((rb = rb_first(&dirty_tracker->root))) {
221 		struct gpu_dirty_extent *dirty_extent =
222 			rb_entry(rb, struct gpu_dirty_extent, rb);
223 
224 		remove_extent(dirty_tracker, dirty_extent);
225 		extent_free(dirty_tracker, dirty_extent);
226 	}
227 
228 	dirty_tracker->total_dirty = 0;
229 }
230 
231 static void gpu_dirty_tracker_fini(struct gpu_dirty_tracker *dirty_tracker)
232 {
233 	gpu_dirty_tracker_empty(dirty_tracker);
234 }
235 
236 /*
237  * Mark the range [start, start + size] as dirty. Merge with the neighbour on
238  * each side if they are contiguous, so the tree never holds two adjacent ranges.
239  */
240 static void gpu_dirty_tracker_mark_dirty(struct gpu_dirty_tracker *dirty_tracker,
241 					 u64 start, u64 size)
242 {
243 	struct gpu_dirty_extent *left, *right, *dirty_extent;
244 	u64 end = start + size;
245 
246 	gpu_buddy_assert(size);
247 
248 	/* Find contiguous neighbours, if any. */
249 	left = prev_extent(dirty_tracker, start);
250 	if (left && left->end != start)
251 		left = NULL;
252 
253 	right = next_extent(dirty_tracker, end);
254 	if (right && right->start != end)
255 		right = NULL;
256 
257 	if (left && right) {
258 		/* Merge left + new + right into a single extent. */
259 		remove_extent(dirty_tracker, left);
260 		remove_extent(dirty_tracker, right);
261 		left->end = right->end;
262 		extent_free(dirty_tracker, right);
263 		insert_extent(dirty_tracker, left);
264 	} else if (left) {
265 		/* Extend left neighbour rightwards. */
266 		remove_extent(dirty_tracker, left);
267 		left->end = end;
268 		insert_extent(dirty_tracker, left);
269 	} else if (right) {
270 		/* Extend right neighbour leftwards. */
271 		remove_extent(dirty_tracker, right);
272 		right->start = start;
273 		insert_extent(dirty_tracker, right);
274 	} else {
275 		/* Standalone extent. */
276 		dirty_extent = extent_alloc(dirty_tracker);
277 		if (!dirty_extent) {
278 			pr_warn_once("dirty extent allocation failed, skipping tracker update\n");
279 			return;
280 		}
281 		dirty_extent->start = start;
282 		dirty_extent->end   = end;
283 		insert_extent(dirty_tracker, dirty_extent);
284 	}
285 
286 	dirty_tracker->total_dirty += size;
287 }
288 
289 /*
290  * Remove the range [start, start + size] from the dirty tracker. Punch the
291  * range out of every overlapping dirty extent, splitting one extent in two if
292  * the removed range falls strictly inside it.
293  */
294 static void gpu_dirty_tracker_remove_range(struct gpu_dirty_tracker *dirty_tracker,
295 					   u64 start, u64 size)
296 {
297 	struct gpu_dirty_extent *dirty_extent, *next;
298 	u64 end = start + size;
299 
300 	gpu_buddy_assert(size);
301 
302 	dirty_extent = prev_extent(dirty_tracker, start + 1);
303 	if (!dirty_extent)
304 		dirty_extent = next_extent(dirty_tracker, start);
305 
306 	while (dirty_extent && dirty_extent->start < end) {
307 		struct rb_node *next_node = rb_next(&dirty_extent->rb);
308 		u64 extent_start = dirty_extent->start;
309 		u64 extent_end = dirty_extent->end;
310 
311 		if (next_node)
312 			next = rb_entry(next_node, struct gpu_dirty_extent, rb);
313 		else
314 			next = NULL;
315 
316 		/* Skip a non-overlapping neighbour returned by prev_extent(). */
317 		if (extent_end <= start) {
318 			dirty_extent = next;
319 			continue;
320 		}
321 
322 		if (extent_start < start && extent_end > end) {
323 			/*
324 			 * Removed range lies strictly inside this dirty extent:
325 			 * split it into the dirty left and right halves.
326 			 */
327 			struct gpu_dirty_extent *right = extent_alloc(dirty_tracker);
328 
329 			if (!right) {
330 				pr_warn_once("dirty extent allocation failed, skipping tracker update\n");
331 				dirty_extent = next;
332 				continue;
333 			}
334 
335 			remove_extent(dirty_tracker, dirty_extent);
336 
337 			dirty_extent->end = start;
338 			right->start = end;
339 			right->end   = extent_end;
340 
341 			insert_extent(dirty_tracker, dirty_extent);
342 			insert_extent(dirty_tracker, right);
343 
344 			dirty_tracker->total_dirty -= size;
345 		} else if (extent_start >= start && extent_end <= end) {
346 			/* Extent fully covered: drop it. */
347 			remove_extent(dirty_tracker, dirty_extent);
348 			extent_free(dirty_tracker, dirty_extent);
349 
350 			dirty_tracker->total_dirty -= (extent_end - extent_start);
351 		} else if (extent_start < start) {
352 			/* Extent overlaps from the left: trim its right end. */
353 			remove_extent(dirty_tracker, dirty_extent);
354 			dirty_extent->end = start;
355 			insert_extent(dirty_tracker, dirty_extent);
356 
357 			dirty_tracker->total_dirty -= (extent_end - start);
358 		} else {
359 			/* Extent overlaps from the right: trim its left end. */
360 			remove_extent(dirty_tracker, dirty_extent);
361 			dirty_extent->start = end;
362 			insert_extent(dirty_tracker, dirty_extent);
363 
364 			dirty_tracker->total_dirty -= (end - extent_start);
365 		}
366 
367 		dirty_extent = next;
368 	}
369 }
370 
371 static enum gpu_block_state
372 gpu_dirty_range_state(struct gpu_dirty_tracker *dirty_tracker,
373 		      u64 start, u64 size)
374 {
375 	struct gpu_dirty_extent *dirty_extent;
376 	u64 end = start + size;
377 
378 	dirty_extent = prev_extent(dirty_tracker, start + 1);
379 	if (dirty_extent) {
380 		if (dirty_extent->start <= start && dirty_extent->end >= end)
381 			return GPU_BLOCK_DIRTY;
382 		if (dirty_extent->start < end && dirty_extent->end > start)
383 			return GPU_BLOCK_MIXED;
384 	}
385 
386 	dirty_extent = next_extent(dirty_tracker, start);
387 	if (dirty_extent && dirty_extent->start < end)
388 		return GPU_BLOCK_MIXED;
389 
390 	return GPU_BLOCK_CLEAR;
391 }
392 
393 static struct rb_node *
394 dirty_tracker_descend_right(struct rb_node *node, u64 min_size)
395 {
396 	while (node->rb_right) {
397 		struct gpu_dirty_extent *tmp_extent;
398 
399 		tmp_extent = rb_entry(node->rb_right, struct gpu_dirty_extent, rb);
400 
401 		if (tmp_extent->subtree_max_size < min_size)
402 			break;
403 		node = node->rb_right;
404 	}
405 
406 	return node;
407 }
408 
409 static struct gpu_dirty_extent *
410 gpu_dirty_tracker_find(struct gpu_dirty_tracker *dirty_tracker,
411 		       u64 min_size, u64 *aligned_start_out)
412 {
413 	struct rb_node *rb = dirty_tracker->root.rb_node;
414 	struct gpu_dirty_extent *root_extent;
415 	struct rb_node *parent;
416 
417 	if (!min_size || !is_power_of_2(min_size))
418 		return NULL;
419 
420 	if (!rb)
421 		return NULL;
422 
423 	root_extent = rb_entry(rb, struct gpu_dirty_extent, rb);
424 	if (root_extent->subtree_max_size < min_size)
425 		return NULL;
426 
427 	rb = dirty_tracker_descend_right(rb, min_size);
428 
429 	while (rb) {
430 		struct gpu_dirty_extent *dirty_extent;
431 		u64 aligned_start;
432 
433 		dirty_extent = rb_entry(rb, struct gpu_dirty_extent, rb);
434 		aligned_start = ALIGN(dirty_extent->start, min_size);
435 
436 		/* Check if a min_size block fits after the alignment skip. */
437 		if (aligned_start <= dirty_extent->end &&
438 		    dirty_extent->end - aligned_start >= min_size) {
439 			*aligned_start_out = aligned_start;
440 			return dirty_extent;
441 		}
442 
443 		if (rb->rb_left) {
444 			struct gpu_dirty_extent *tmp_extent;
445 
446 			tmp_extent = rb_entry(rb->rb_left, struct gpu_dirty_extent, rb);
447 			if (tmp_extent->subtree_max_size >= min_size) {
448 				rb = dirty_tracker_descend_right(rb->rb_left, min_size);
449 				continue;
450 			}
451 		}
452 
453 		/* Walk up until we exit a node via its right child. */
454 		parent = rb_parent(rb);
455 		while (parent && parent->rb_right != rb) {
456 			rb = parent;
457 			parent = rb_parent(rb);
458 		}
459 		rb = parent;
460 	}
461 
462 	return NULL;
463 }
464 
465 static unsigned int
466 gpu_buddy_block_state(struct gpu_buddy_block *block)
467 {
468 	return block->header & GPU_BUDDY_HEADER_STATE;
469 }
470 
471 static bool
472 gpu_buddy_block_is_allocated(struct gpu_buddy_block *block)
473 {
474 	return gpu_buddy_block_state(block) == GPU_BUDDY_ALLOCATED;
475 }
476 
477 static bool
478 gpu_buddy_block_is_split(struct gpu_buddy_block *block)
479 {
480 	return gpu_buddy_block_state(block) == GPU_BUDDY_SPLIT;
481 }
482 
483 static unsigned int gpu_buddy_block_offset_alignment(struct gpu_buddy_block *block)
484 {
485 	u64 offset = gpu_buddy_block_offset(block);
486 
487 	if (!offset)
488 		/*
489 		 * __ffs64(0) is undefined; offset 0 is maximally aligned, so return
490 		 * a value greater than any possible alignment.
491 		 */
492 		return 64 + 1;
493 
494 	return __ffs64(offset);
495 }
496 
497 static inline enum gpu_block_state
498 gpu_block_cached_state(struct gpu_buddy_block *block)
499 {
500 	if (gpu_buddy_block_is_clear(block))
501 		return GPU_BLOCK_CLEAR;
502 	if (block->has_clear)
503 		return GPU_BLOCK_MIXED;
504 	return GPU_BLOCK_DIRTY;
505 }
506 
507 static inline void gpu_buddy_augment_compute(struct gpu_buddy_block *block)
508 {
509 	enum gpu_block_state block_state;
510 	struct gpu_buddy_block *right;
511 	struct gpu_buddy_block *left;
512 	unsigned int max_align;
513 
514 	max_align = gpu_buddy_block_offset_alignment(block);
515 	block_state = gpu_block_cached_state(block);
516 
517 	left = rb_entry_safe(block->rb.rb_left, struct gpu_buddy_block, rb);
518 	if (left) {
519 		if (left->subtree_max_alignment > max_align)
520 			max_align = left->subtree_max_alignment;
521 
522 		block_state = max(block_state, left->subtree_block_state);
523 	}
524 
525 	right = rb_entry_safe(block->rb.rb_right, struct gpu_buddy_block, rb);
526 	if (right) {
527 		if (right->subtree_max_alignment > max_align)
528 			max_align = right->subtree_max_alignment;
529 
530 		block_state = max(block_state, right->subtree_block_state);
531 	}
532 
533 	block->subtree_max_alignment = max_align;
534 	block->subtree_block_state = block_state;
535 }
536 
537 static void gpu_buddy_augment_propagate(struct rb_node *rb, struct rb_node *stop)
538 {
539 	while (rb != stop) {
540 		struct gpu_buddy_block *block;
541 		unsigned int old_align;
542 		enum gpu_block_state old_block_state;
543 
544 		block = rb_entry(rb, struct gpu_buddy_block, rb);
545 		old_align = block->subtree_max_alignment;
546 		old_block_state = block->subtree_block_state;
547 
548 		gpu_buddy_augment_compute(block);
549 		if (block->subtree_max_alignment == old_align &&
550 		    block->subtree_block_state == old_block_state)
551 			break;
552 
553 		rb = rb_parent(&block->rb);
554 	}
555 }
556 
557 static void gpu_buddy_augment_copy(struct rb_node *rb_old, struct rb_node *rb_new)
558 {
559 	struct gpu_buddy_block *old;
560 	struct gpu_buddy_block *new;
561 
562 	old = rb_entry(rb_old, struct gpu_buddy_block, rb);
563 	new = rb_entry(rb_new, struct gpu_buddy_block, rb);
564 
565 	new->subtree_max_alignment = old->subtree_max_alignment;
566 	new->subtree_block_state = old->subtree_block_state;
567 }
568 
569 static void gpu_buddy_augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new)
570 {
571 	struct gpu_buddy_block *old;
572 	struct gpu_buddy_block *new;
573 
574 	old = rb_entry(rb_old, struct gpu_buddy_block, rb);
575 	new = rb_entry(rb_new, struct gpu_buddy_block, rb);
576 
577 	new->subtree_max_alignment = old->subtree_max_alignment;
578 	new->subtree_block_state = old->subtree_block_state;
579 
580 	gpu_buddy_augment_compute(old);
581 }
582 
583 static const struct rb_augment_callbacks gpu_buddy_augment_cb = {
584 	.propagate = gpu_buddy_augment_propagate,
585 	.copy      = gpu_buddy_augment_copy,
586 	.rotate    = gpu_buddy_augment_rotate,
587 };
588 
589 static struct gpu_buddy_block *gpu_block_alloc(struct gpu_buddy *mm,
590 					       struct gpu_buddy_block *parent,
591 					       unsigned int order,
592 					       u64 offset)
593 {
594 	struct gpu_buddy_block *block;
595 
596 	BUG_ON(order > GPU_BUDDY_MAX_ORDER);
597 
598 	block = kmem_cache_zalloc(slab_blocks, GFP_KERNEL);
599 	if (!block)
600 		return NULL;
601 
602 	block->header = offset;
603 	block->header |= order;
604 	block->parent = parent;
605 
606 	RB_CLEAR_NODE(&block->rb);
607 
608 	BUG_ON(block->header & GPU_BUDDY_HEADER_UNUSED);
609 	return block;
610 }
611 
612 static void gpu_block_free(struct gpu_buddy *mm,
613 			   struct gpu_buddy_block *block)
614 {
615 	kmem_cache_free(slab_blocks, block);
616 }
617 
618 static struct gpu_buddy_block *
619 rbtree_get_free_block(const struct rb_node *node)
620 {
621 	return node ? rb_entry(node, struct gpu_buddy_block, rb) : NULL;
622 }
623 
624 static struct gpu_buddy_block *
625 rbtree_last_free_block(struct rb_root *root)
626 {
627 	return rbtree_get_free_block(rb_last(root));
628 }
629 
630 static struct gpu_buddy_block *
631 rbtree_last_clear_free_block(struct rb_root *root,
632 			     enum gpu_block_state min_block_state)
633 {
634 	struct rb_node *node = root->rb_node;
635 	struct gpu_buddy_block *block = NULL;
636 	struct gpu_buddy_block *root_block;
637 	enum gpu_block_state target_state;
638 
639 	root_block = rbtree_get_free_block(node);
640 	if (!root_block || root_block->subtree_block_state < min_block_state)
641 		return NULL;
642 
643 	target_state = root_block->subtree_block_state;
644 
645 	while (node) {
646 		struct gpu_buddy_block *right_block;
647 		struct gpu_buddy_block *node_block;
648 
649 		node_block = rbtree_get_free_block(node);
650 		right_block = rbtree_get_free_block(node->rb_right);
651 
652 		if (right_block && right_block->subtree_block_state >= target_state) {
653 			node = node->rb_right;
654 			continue;
655 		}
656 
657 		if (gpu_block_cached_state(node_block) == target_state) {
658 			block = node_block;
659 			break;
660 		}
661 
662 		node = node->rb_left;
663 	}
664 
665 	return block;
666 }
667 
668 static void rbtree_insert(struct gpu_buddy *mm,
669 			  struct gpu_buddy_block *block)
670 {
671 	struct rb_node **link, *parent = NULL;
672 	enum gpu_block_state block_state;
673 	struct gpu_buddy_block *node;
674 	unsigned int block_alignment;
675 	struct rb_root *root;
676 	unsigned int order;
677 
678 	order = gpu_buddy_block_order(block);
679 	block_alignment = gpu_buddy_block_offset_alignment(block);
680 	block_state = gpu_block_cached_state(block);
681 
682 	root = &mm->free_tree[order];
683 	link = &root->rb_node;
684 
685 	while (*link) {
686 		parent = *link;
687 		node = rbtree_get_free_block(parent);
688 		/*
689 		 * Manual augmentation update during insertion traversal. Required
690 		 * because rb_insert_augmented() only calls rotate callback during
691 		 * rotations. This ensures all ancestors on the insertion path have
692 		 * correct subtree_max_alignment / subtree_block_state values.
693 		 */
694 		if (node->subtree_max_alignment < block_alignment)
695 			node->subtree_max_alignment = block_alignment;
696 		if (node->subtree_block_state < block_state)
697 			node->subtree_block_state = block_state;
698 
699 		if (gpu_buddy_block_offset(block) < gpu_buddy_block_offset(node))
700 			link = &parent->rb_left;
701 		else
702 			link = &parent->rb_right;
703 	}
704 
705 	block->subtree_max_alignment = block_alignment;
706 	block->subtree_block_state = block_state;
707 	rb_link_node(&block->rb, parent, link);
708 	rb_insert_augmented(&block->rb, root, &gpu_buddy_augment_cb);
709 }
710 
711 static void rbtree_remove(struct gpu_buddy *mm,
712 			  struct gpu_buddy_block *block)
713 {
714 	unsigned int order = gpu_buddy_block_order(block);
715 
716 	rb_erase_augmented(&block->rb, &mm->free_tree[order], &gpu_buddy_augment_cb);
717 	RB_CLEAR_NODE(&block->rb);
718 }
719 
720 static void mark_allocated(struct gpu_buddy *mm,
721 			   struct gpu_buddy_block *block)
722 {
723 	block->header &= ~GPU_BUDDY_HEADER_STATE;
724 	block->header |= GPU_BUDDY_ALLOCATED;
725 
726 	block->has_clear = false;
727 
728 	mm->free_scoreboard[gpu_buddy_block_order(block)]--;
729 	mm->used_scoreboard[gpu_buddy_block_order(block)]++;
730 
731 	rbtree_remove(mm, block);
732 }
733 
734 static void __mark_free(struct gpu_buddy *mm,
735 			struct gpu_buddy_block *block,
736 			enum gpu_block_state block_state)
737 {
738 	if (gpu_buddy_block_is_allocated(block))
739 		mm->used_scoreboard[gpu_buddy_block_order(block)]--;
740 
741 	block->header &= ~GPU_BUDDY_HEADER_STATE;
742 	block->header |= GPU_BUDDY_FREE;
743 
744 	block->header &= ~GPU_BUDDY_HEADER_CLEAR;
745 
746 	block->has_clear = (block_state != GPU_BLOCK_DIRTY);
747 	if (block_state == GPU_BLOCK_CLEAR)
748 		block->header |= GPU_BUDDY_HEADER_CLEAR;
749 
750 	mm->free_scoreboard[gpu_buddy_block_order(block)]++;
751 
752 	rbtree_insert(mm, block);
753 }
754 
755 static void mark_free(struct gpu_buddy *mm,
756 		      struct gpu_buddy_block *block)
757 {
758 	enum gpu_block_state block_state;
759 
760 	block_state = gpu_dirty_range_state(&mm->dirty,
761 					    gpu_buddy_block_offset(block),
762 					    gpu_buddy_block_size(mm, block));
763 	__mark_free(mm, block, block_state);
764 }
765 
766 static void mark_split(struct gpu_buddy *mm,
767 		       struct gpu_buddy_block *block)
768 {
769 	block->header &= ~GPU_BUDDY_HEADER_STATE;
770 	block->header |= GPU_BUDDY_SPLIT;
771 
772 	mm->free_scoreboard[gpu_buddy_block_order(block)]--;
773 
774 	rbtree_remove(mm, block);
775 }
776 
777 static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
778 {
779 	return s1 <= e2 && e1 >= s2;
780 }
781 
782 static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2)
783 {
784 	return s1 <= s2 && e1 >= e2;
785 }
786 
787 static struct gpu_buddy_block *
788 __get_buddy(struct gpu_buddy_block *block)
789 {
790 	struct gpu_buddy_block *parent;
791 
792 	parent = block->parent;
793 	if (!parent)
794 		return NULL;
795 
796 	if (parent->left == block)
797 		return parent->right;
798 
799 	return parent->left;
800 }
801 
802 static unsigned int __gpu_buddy_free(struct gpu_buddy *mm,
803 				     struct gpu_buddy_block *block)
804 {
805 	enum gpu_block_state block_state;
806 	struct gpu_buddy_block *parent;
807 	unsigned int order;
808 
809 	block_state = gpu_block_cached_state(block);
810 
811 	while ((parent = block->parent)) {
812 		struct gpu_buddy_block *buddy = __get_buddy(block);
813 
814 		if (!gpu_buddy_block_is_free(buddy))
815 			break;
816 
817 		if (block_state != GPU_BLOCK_MIXED) {
818 			enum gpu_block_state buddy_state;
819 
820 			buddy_state = gpu_block_cached_state(buddy);
821 
822 			if (buddy_state != block_state)
823 				block_state = GPU_BLOCK_MIXED;
824 		}
825 
826 		rbtree_remove(mm, buddy);
827 		mm->free_scoreboard[gpu_buddy_block_order(buddy)]--;
828 
829 		if (gpu_buddy_block_is_allocated(block))
830 			mm->used_scoreboard[gpu_buddy_block_order(block)]--;
831 
832 		gpu_block_free(mm, block);
833 		gpu_block_free(mm, buddy);
834 
835 		block = parent;
836 	}
837 
838 	order = gpu_buddy_block_order(block);
839 	__mark_free(mm, block, block_state);
840 
841 	return order;
842 }
843 
844 /**
845  * gpu_buddy_init - init memory manager
846  *
847  * @mm: GPU buddy manager to initialize
848  * @size: size in bytes to manage
849  * @chunk_size: minimum page size in bytes for our allocations
850  *
851  * Initializes the memory manager and its resources.
852  *
853  * Returns:
854  * 0 on success, error code on failure.
855  */
856 int gpu_buddy_init(struct gpu_buddy *mm, u64 size, u64 chunk_size)
857 {
858 	unsigned int root_count = 0;
859 	u64 offset = 0;
860 
861 	if (size < chunk_size)
862 		return -EINVAL;
863 
864 	if (chunk_size < SZ_4K)
865 		return -EINVAL;
866 
867 	if (!is_power_of_2(chunk_size))
868 		return -EINVAL;
869 
870 	size = round_down(size, chunk_size);
871 
872 	mm->size = size;
873 	mm->avail = size;
874 	mm->chunk_size = chunk_size;
875 	mm->max_order = ilog2(size) - ilog2(chunk_size);
876 
877 	BUG_ON(mm->max_order > GPU_BUDDY_MAX_ORDER);
878 
879 	mm->free_scoreboard = kzalloc_objs(*mm->free_scoreboard,
880 					   mm->max_order + 1);
881 	if (!mm->free_scoreboard)
882 		return -ENOMEM;
883 
884 	mm->used_scoreboard = kzalloc_objs(*mm->used_scoreboard,
885 					   mm->max_order + 1);
886 	if (!mm->used_scoreboard)
887 		goto out_free_free_scoreboard;
888 
889 	mm->free_tree = kzalloc_objs(struct rb_root, mm->max_order + 1);
890 	if (!mm->free_tree)
891 		goto out_free_used_scoreboard;
892 
893 	gpu_dirty_tracker_init(&mm->dirty);
894 
895 	mm->n_roots = hweight64(size);
896 
897 	mm->roots = kmalloc_objs(struct gpu_buddy_block *, mm->n_roots);
898 	if (!mm->roots)
899 		goto out_free_tree;
900 
901 	/*
902 	 * Split into power-of-two blocks, in case we are given a size that is
903 	 * not itself a power-of-two.
904 	 */
905 	do {
906 		struct gpu_buddy_block *root;
907 		unsigned int order;
908 		u64 root_size;
909 
910 		order = ilog2(size) - ilog2(chunk_size);
911 		root_size = chunk_size << order;
912 
913 		root = gpu_block_alloc(mm, NULL, order, offset);
914 		if (!root)
915 			goto out_free_roots;
916 
917 		gpu_dirty_tracker_mark_dirty(&mm->dirty, offset, root_size);
918 		__mark_free(mm, root, GPU_BLOCK_DIRTY);
919 
920 		BUG_ON(root_count > mm->max_order);
921 		BUG_ON(gpu_buddy_block_size(mm, root) < chunk_size);
922 
923 		mm->roots[root_count] = root;
924 
925 		offset += root_size;
926 		size -= root_size;
927 		root_count++;
928 	} while (size);
929 
930 #ifdef CONFIG_LOCKDEP
931 	mm->lock_dep_map = NULL;
932 #endif
933 	return 0;
934 
935 out_free_roots:
936 	while (root_count--)
937 		gpu_block_free(mm, mm->roots[root_count]);
938 	kfree(mm->roots);
939 out_free_tree:
940 	gpu_dirty_tracker_fini(&mm->dirty);
941 	kfree(mm->free_tree);
942 out_free_used_scoreboard:
943 	kfree(mm->used_scoreboard);
944 out_free_free_scoreboard:
945 	kfree(mm->free_scoreboard);
946 	return -ENOMEM;
947 }
948 EXPORT_SYMBOL(gpu_buddy_init);
949 
950 /**
951  * gpu_buddy_fini - tear down the memory manager
952  *
953  * @mm: GPU buddy manager to free
954  *
955  * Cleanup memory manager resources and the freetree
956  */
957 void gpu_buddy_fini(struct gpu_buddy *mm)
958 {
959 	u64 root_size, size;
960 	unsigned int order;
961 	int i;
962 
963 	size = mm->size;
964 
965 	for (i = 0; i < mm->n_roots; ++i) {
966 		order = ilog2(size) - ilog2(mm->chunk_size);
967 		root_size = mm->chunk_size << order;
968 
969 		gpu_buddy_assert(gpu_buddy_block_is_free(mm->roots[i]));
970 		gpu_block_free(mm, mm->roots[i]);
971 		size -= root_size;
972 	}
973 
974 	gpu_buddy_assert(mm->avail == mm->size);
975 
976 	for (i = 0; i <= mm->max_order; ++i)
977 		gpu_buddy_assert(!mm->used_scoreboard[i]);
978 
979 	gpu_dirty_tracker_fini(&mm->dirty);
980 	kfree(mm->free_tree);
981 	kfree(mm->roots);
982 	kfree(mm->free_scoreboard);
983 	kfree(mm->used_scoreboard);
984 }
985 EXPORT_SYMBOL(gpu_buddy_fini);
986 
987 static int split_block(struct gpu_buddy *mm,
988 		       struct gpu_buddy_block *block)
989 {
990 	unsigned int block_order = gpu_buddy_block_order(block) - 1;
991 	u64 offset = gpu_buddy_block_offset(block);
992 	enum gpu_block_state parent_state;
993 
994 	BUG_ON(!gpu_buddy_block_is_free(block));
995 	BUG_ON(!gpu_buddy_block_order(block));
996 
997 	block->left = gpu_block_alloc(mm, block, block_order, offset);
998 	if (!block->left)
999 		return -ENOMEM;
1000 
1001 	block->right = gpu_block_alloc(mm, block, block_order,
1002 				       offset + (mm->chunk_size << block_order));
1003 	if (!block->right) {
1004 		gpu_block_free(mm, block->left);
1005 		return -ENOMEM;
1006 	}
1007 
1008 	parent_state = gpu_block_cached_state(block);
1009 
1010 	mark_split(mm, block);
1011 
1012 	if (parent_state == GPU_BLOCK_MIXED) {
1013 		mark_free(mm, block->left);
1014 		mark_free(mm, block->right);
1015 	} else {
1016 		__mark_free(mm, block->left, parent_state);
1017 		__mark_free(mm, block->right, parent_state);
1018 	}
1019 
1020 	return 0;
1021 }
1022 
1023 /**
1024  * gpu_buddy_reset_clear - reset blocks clear state
1025  *
1026  * @mm: GPU buddy manager
1027  * @is_clear: blocks clear state
1028  *
1029  * Reset the clear state based on @is_clear value for each block
1030  * in the freetree.
1031  */
1032 void gpu_buddy_reset_clear(struct gpu_buddy *mm, bool is_clear)
1033 {
1034 	unsigned int i;
1035 
1036 	gpu_buddy_driver_lock_held(mm);
1037 
1038 	gpu_dirty_tracker_empty(&mm->dirty);
1039 
1040 	for (i = 0; i <= mm->max_order; ++i) {
1041 		struct gpu_buddy_block *block, *tmp;
1042 
1043 		rbtree_postorder_for_each_entry_safe(block, tmp,
1044 						     &mm->free_tree[i], rb) {
1045 			if (is_clear) {
1046 				if (!gpu_buddy_block_is_clear(block))
1047 					block->header |= GPU_BUDDY_HEADER_CLEAR;
1048 				block->has_clear = true;
1049 			} else {
1050 				block->header &= ~GPU_BUDDY_HEADER_CLEAR;
1051 				block->has_clear = false;
1052 				gpu_dirty_tracker_mark_dirty(&mm->dirty,
1053 							     gpu_buddy_block_offset(block),
1054 							     gpu_buddy_block_size(mm, block));
1055 			}
1056 
1057 			gpu_buddy_augment_compute(block);
1058 		}
1059 	}
1060 }
1061 EXPORT_SYMBOL(gpu_buddy_reset_clear);
1062 
1063 static void __gpu_buddy_free_block_internal(struct gpu_buddy *mm,
1064 					    struct gpu_buddy_block *block)
1065 {
1066 	u64 size = gpu_buddy_block_size(mm, block);
1067 
1068 	gpu_buddy_driver_lock_held(mm);
1069 	BUG_ON(!gpu_buddy_block_is_allocated(block));
1070 
1071 	mm->avail += size;
1072 	__gpu_buddy_free(mm, block);
1073 }
1074 
1075 /**
1076  * gpu_buddy_free_block - free a block
1077  *
1078  * @mm: GPU buddy manager
1079  * @block: block to be freed
1080  */
1081 void gpu_buddy_free_block(struct gpu_buddy *mm,
1082 			  struct gpu_buddy_block *block)
1083 {
1084 	if (!gpu_buddy_block_is_clear(block))
1085 		gpu_dirty_tracker_mark_dirty(&mm->dirty,
1086 					     gpu_buddy_block_offset(block),
1087 					     gpu_buddy_block_size(mm, block));
1088 
1089 	__gpu_buddy_free_block_internal(mm, block);
1090 }
1091 EXPORT_SYMBOL(gpu_buddy_free_block);
1092 
1093 /**
1094  * gpu_buddy_allocated_addr_to_block - given relative address find the allocated block
1095  *
1096  * @mm: GPU buddy manager
1097  * @addr: Relative address
1098  *
1099  * Returns:
1100  * gpu_buddy_block on success, NULL or error code on failure
1101  */
1102 struct gpu_buddy_block *gpu_buddy_allocated_addr_to_block(struct gpu_buddy *mm, u64 addr)
1103 {
1104 	struct gpu_buddy_block *block;
1105 	LIST_HEAD(dfs);
1106 	u64 end;
1107 	int i;
1108 
1109 	gpu_buddy_driver_lock_held(mm);
1110 
1111 	end = addr + mm->chunk_size - 1;
1112 	for (i = 0; i < mm->n_roots; ++i)
1113 		list_add_tail(&mm->roots[i]->tmp_link, &dfs);
1114 
1115 	do {
1116 		u64 block_start;
1117 		u64 block_end;
1118 
1119 		block = list_first_entry_or_null(&dfs,
1120 						 struct gpu_buddy_block,
1121 						 tmp_link);
1122 		if (!block)
1123 			break;
1124 
1125 		list_del(&block->tmp_link);
1126 
1127 		block_start = gpu_buddy_block_offset(block);
1128 		block_end = block_start + gpu_buddy_block_size(mm, block) - 1;
1129 
1130 		if (!overlaps(addr, end, block_start, block_end))
1131 			continue;
1132 
1133 		if (gpu_buddy_block_is_allocated(block))
1134 			return block;
1135 		else if (gpu_buddy_block_is_free(block))
1136 			return NULL;
1137 
1138 		list_add(&block->right->tmp_link, &dfs);
1139 		list_add(&block->left->tmp_link, &dfs);
1140 	} while (1);
1141 
1142 	return ERR_PTR(-ENXIO);
1143 }
1144 EXPORT_SYMBOL(gpu_buddy_allocated_addr_to_block);
1145 
1146 static void __gpu_buddy_free_list(struct gpu_buddy *mm,
1147 				  struct list_head *objects,
1148 				  bool mark_clear,
1149 				  bool mark_dirty)
1150 {
1151 	struct gpu_buddy_block *block, *on;
1152 	u64 dirty_start = 0, dirty_size = 0;
1153 
1154 	gpu_buddy_assert(!(mark_dirty && mark_clear));
1155 
1156 	list_for_each_entry_safe(block, on, objects, link) {
1157 		u64 offset = gpu_buddy_block_offset(block);
1158 		u64 size = gpu_buddy_block_size(mm, block);
1159 
1160 		if (mark_clear)
1161 			block->header |= GPU_BUDDY_HEADER_CLEAR;
1162 		else if (mark_dirty)
1163 			block->header &= ~GPU_BUDDY_HEADER_CLEAR;
1164 
1165 		/*
1166 		 * Coalesce contiguous dirty blocks into one extent update so
1167 		 * a multi-block contiguous free costs a single mark_dirty().
1168 		 * Flush the pending extent and start over on a gap.
1169 		 */
1170 		if (!gpu_buddy_block_is_clear(block)) {
1171 			if (dirty_size &&
1172 			    (dirty_start + dirty_size == offset ||
1173 			     offset + size == dirty_start)) {
1174 				dirty_start = min(dirty_start, offset);
1175 				dirty_size += size;
1176 			} else {
1177 				if (dirty_size)
1178 					gpu_dirty_tracker_mark_dirty(&mm->dirty,
1179 								     dirty_start,
1180 								     dirty_size);
1181 				dirty_start = offset;
1182 				dirty_size = size;
1183 			}
1184 		}
1185 
1186 		__gpu_buddy_free_block_internal(mm, block);
1187 		cond_resched();
1188 	}
1189 
1190 	if (dirty_size)
1191 		gpu_dirty_tracker_mark_dirty(&mm->dirty, dirty_start, dirty_size);
1192 
1193 	INIT_LIST_HEAD(objects);
1194 }
1195 
1196 static void gpu_buddy_free_list_internal(struct gpu_buddy *mm,
1197 					 struct list_head *objects)
1198 {
1199 	/*
1200 	 * Don't touch the clear/dirty bit, since allocation is still internal
1201 	 * at this point. For example we might have just failed part of the
1202 	 * allocation.
1203 	 */
1204 	__gpu_buddy_free_list(mm, objects, false, false);
1205 }
1206 
1207 /**
1208  * gpu_buddy_free_list - free blocks
1209  *
1210  * @mm: GPU buddy manager
1211  * @objects: input list head to free blocks
1212  * @flags: optional flags like GPU_BUDDY_CLEARED
1213  */
1214 void gpu_buddy_free_list(struct gpu_buddy *mm,
1215 			 struct list_head *objects,
1216 			 unsigned int flags)
1217 {
1218 	bool mark_clear = flags & GPU_BUDDY_CLEARED;
1219 
1220 	gpu_buddy_driver_lock_held(mm);
1221 	__gpu_buddy_free_list(mm, objects, mark_clear, !mark_clear);
1222 }
1223 EXPORT_SYMBOL(gpu_buddy_free_list);
1224 
1225 static void __gpu_buddy_undo_splits(struct gpu_buddy *mm,
1226 				    struct gpu_buddy_block *block)
1227 {
1228 	struct gpu_buddy_block *buddy = __get_buddy(block);
1229 
1230 	if (buddy &&
1231 	    (gpu_buddy_block_is_free(block) &&
1232 	     gpu_buddy_block_is_free(buddy))) {
1233 		rbtree_remove(mm, block);
1234 		mm->free_scoreboard[gpu_buddy_block_order(block)]--;
1235 		__gpu_buddy_free(mm, block);
1236 	}
1237 }
1238 
1239 static struct gpu_buddy_block *
1240 __alloc_range_bias(struct gpu_buddy *mm,
1241 		   u64 start, u64 end,
1242 		   unsigned int order,
1243 		   unsigned long flags)
1244 {
1245 	u64 req_size = mm->chunk_size << order;
1246 	struct gpu_buddy_block *block;
1247 	LIST_HEAD(dfs);
1248 	int err;
1249 	int i;
1250 
1251 	end = end - 1;
1252 
1253 	/*
1254 	 * This range-constrained search hands back the highest/right-most
1255 	 * address that satisfies the request: the roots are seeded high-to-low
1256 	 * and the right (higher-address) child is descended first, making
1257 	 * top-down the default placement here. A non-top-down clear request is
1258 	 * the only exception, where the descent is biased towards clear or
1259 	 * clear-containing subtrees to satisfy the clear preference.
1260 	 */
1261 	for (i = mm->n_roots - 1; i >= 0; --i)
1262 		list_add_tail(&mm->roots[i]->tmp_link, &dfs);
1263 
1264 	do {
1265 		u64 block_start;
1266 		u64 block_end;
1267 
1268 		block = list_first_entry_or_null(&dfs,
1269 						 struct gpu_buddy_block,
1270 						 tmp_link);
1271 		if (!block)
1272 			break;
1273 
1274 		list_del(&block->tmp_link);
1275 
1276 		if (gpu_buddy_block_order(block) < order)
1277 			continue;
1278 
1279 		block_start = gpu_buddy_block_offset(block);
1280 		block_end = block_start + gpu_buddy_block_size(mm, block) - 1;
1281 
1282 		if (!overlaps(start, end, block_start, block_end))
1283 			continue;
1284 
1285 		if (gpu_buddy_block_is_allocated(block))
1286 			continue;
1287 
1288 		if (block_start < start || block_end > end) {
1289 			u64 adjusted_start = max(block_start, start);
1290 			u64 adjusted_end = min(block_end, end);
1291 
1292 			if (round_down(adjusted_end + 1, req_size) <=
1293 			    round_up(adjusted_start, req_size))
1294 				continue;
1295 		}
1296 
1297 		if (contains(start, end, block_start, block_end) &&
1298 		    order == gpu_buddy_block_order(block)) {
1299 			/*
1300 			 * Find the free block within the range.
1301 			 */
1302 			if (gpu_buddy_block_is_free(block))
1303 				return block;
1304 
1305 			continue;
1306 		}
1307 
1308 		if (!gpu_buddy_block_is_split(block)) {
1309 			err = split_block(mm, block);
1310 			if (unlikely(err))
1311 				goto err_undo;
1312 		}
1313 
1314 		/*
1315 		 * Top-down is a strict address-placement policy, so when it is
1316 		 * requested we ignore clear steering and simply descend the
1317 		 * right (higher-address) child first. Only a non-top-down clear
1318 		 * request biases the descent towards clear/has_clear subtrees.
1319 		 */
1320 		if ((flags & GPU_BUDDY_CLEAR_ALLOCATION) &&
1321 		    !(flags & GPU_BUDDY_TOPDOWN_ALLOCATION)) {
1322 			struct gpu_buddy_block *prefer;
1323 
1324 			if (gpu_buddy_block_is_clear(block->right))
1325 				prefer = block->right;
1326 			else if (gpu_buddy_block_is_clear(block->left))
1327 				prefer = block->left;
1328 			else if (block->right->has_clear)
1329 				prefer = block->right;
1330 			else if (block->left->has_clear)
1331 				prefer = block->left;
1332 			else
1333 				prefer = block->right;
1334 
1335 			if (prefer == block->right) {
1336 				list_add(&block->left->tmp_link, &dfs);
1337 				list_add(&block->right->tmp_link, &dfs);
1338 			} else {
1339 				list_add(&block->right->tmp_link, &dfs);
1340 				list_add(&block->left->tmp_link, &dfs);
1341 			}
1342 		} else {
1343 			list_add(&block->left->tmp_link, &dfs);
1344 			list_add(&block->right->tmp_link, &dfs);
1345 		}
1346 	} while (1);
1347 
1348 	return ERR_PTR(-ENOSPC);
1349 
1350 err_undo:
1351 	/*
1352 	 * We really don't want to leave around a bunch of split blocks, since
1353 	 * bigger is better, so make sure we merge everything back before we
1354 	 * free the allocated blocks.
1355 	 */
1356 	__gpu_buddy_undo_splits(mm, block);
1357 	return ERR_PTR(err);
1358 }
1359 
1360 /* Return the highest-address free block of at least @order. */
1361 static struct gpu_buddy_block *
1362 get_maxblock(struct gpu_buddy *mm,
1363 	     unsigned int order)
1364 {
1365 	struct gpu_buddy_block *max_block;
1366 	struct gpu_buddy_block *block;
1367 	unsigned int i;
1368 
1369 	/*
1370 	 * Top-down allocation is a strict address-placement policy: the block
1371 	 * is chosen purely by offset, regardless of its clear/dirty state.
1372 	 * Clear state is re-derived from the dirty tracker once the allocation
1373 	 * completes, and the driver is responsible for issuing the clear pass
1374 	 * if a clear region is required.
1375 	 */
1376 	max_block = NULL;
1377 
1378 	for (i = order; i <= mm->max_order; ++i) {
1379 		block = rbtree_last_free_block(&mm->free_tree[i]);
1380 		if (!block)
1381 			continue;
1382 
1383 		if (!max_block ||
1384 		    gpu_buddy_block_offset(block) > gpu_buddy_block_offset(max_block))
1385 			max_block = block;
1386 	}
1387 
1388 	return max_block;
1389 }
1390 
1391 static struct gpu_buddy_block *
1392 alloc_from_freetree(struct gpu_buddy *mm,
1393 		    unsigned int order,
1394 		    unsigned long flags)
1395 {
1396 	struct gpu_buddy_block *block = NULL;
1397 	unsigned int tmp;
1398 	int err;
1399 
1400 	if (flags & GPU_BUDDY_TOPDOWN_ALLOCATION) {
1401 		block = get_maxblock(mm, order);
1402 		if (block)
1403 			tmp = gpu_buddy_block_order(block);
1404 	} else {
1405 		if (flags & GPU_BUDDY_CLEAR_ALLOCATION) {
1406 			for (tmp = order; tmp <= mm->max_order; ++tmp) {
1407 				block = rbtree_last_clear_free_block(&mm->free_tree[tmp],
1408 								     GPU_BLOCK_MIXED);
1409 				if (block)
1410 					break;
1411 			}
1412 		}
1413 		if (!block) {
1414 			for (tmp = order; tmp <= mm->max_order; ++tmp) {
1415 				block = rbtree_last_free_block(&mm->free_tree[tmp]);
1416 				if (block)
1417 					break;
1418 			}
1419 		}
1420 	}
1421 
1422 	if (!block)
1423 		return ERR_PTR(-ENOSPC);
1424 
1425 	BUG_ON(!gpu_buddy_block_is_free(block));
1426 
1427 	while (tmp != order) {
1428 		err = split_block(mm, block);
1429 		if (unlikely(err))
1430 			goto err_undo;
1431 
1432 		if ((flags & GPU_BUDDY_CLEAR_ALLOCATION) &&
1433 		    !(flags & GPU_BUDDY_TOPDOWN_ALLOCATION)) {
1434 			bool right_clear, left_clear;
1435 
1436 			right_clear = gpu_buddy_block_is_clear(block->right);
1437 			left_clear = gpu_buddy_block_is_clear(block->left);
1438 
1439 			if (right_clear)
1440 				block = block->right;
1441 			else if (left_clear)
1442 				block = block->left;
1443 			else if (block->right->has_clear)
1444 				block = block->right;
1445 			else if (block->left->has_clear)
1446 				block = block->left;
1447 			else
1448 				block = block->right;
1449 		} else {
1450 			block = block->right;
1451 		}
1452 		tmp--;
1453 	}
1454 	return block;
1455 
1456 err_undo:
1457 	__gpu_buddy_undo_splits(mm, block);
1458 	return ERR_PTR(err);
1459 }
1460 
1461 static bool
1462 gpu_buddy_can_offset_align(u64 size, u64 min_block_size)
1463 {
1464 	return size < min_block_size && is_power_of_2(size);
1465 }
1466 
1467 static bool gpu_buddy_subtree_can_satisfy(struct rb_node *node,
1468 					  unsigned int alignment)
1469 {
1470 	struct gpu_buddy_block *block;
1471 
1472 	block = rbtree_get_free_block(node);
1473 	return block->subtree_max_alignment >= alignment;
1474 }
1475 
1476 static struct gpu_buddy_block *
1477 gpu_buddy_find_block_aligned(struct gpu_buddy *mm,
1478 			     unsigned int order,
1479 			     unsigned int alignment)
1480 {
1481 	struct rb_root *root = &mm->free_tree[order];
1482 	struct rb_node *rb = root->rb_node;
1483 
1484 	while (rb) {
1485 		struct gpu_buddy_block *block = rbtree_get_free_block(rb);
1486 		struct rb_node *left_node = rb->rb_left, *right_node = rb->rb_right;
1487 
1488 		if (right_node) {
1489 			if (gpu_buddy_subtree_can_satisfy(right_node, alignment)) {
1490 				rb = right_node;
1491 				continue;
1492 			}
1493 		}
1494 
1495 		if (gpu_buddy_block_offset_alignment(block) >= alignment)
1496 			return block;
1497 
1498 		if (left_node) {
1499 			if (gpu_buddy_subtree_can_satisfy(left_node, alignment)) {
1500 				rb = left_node;
1501 				continue;
1502 			}
1503 		}
1504 
1505 		break;
1506 	}
1507 
1508 	return NULL;
1509 }
1510 
1511 static struct gpu_buddy_block *
1512 gpu_buddy_offset_aligned_allocation(struct gpu_buddy *mm,
1513 				    u64 size,
1514 				    u64 min_block_size)
1515 {
1516 	struct gpu_buddy_block *block = NULL;
1517 	unsigned int order, tmp, alignment;
1518 	unsigned long pages;
1519 	int err;
1520 
1521 	alignment = ilog2(min_block_size);
1522 	pages = size >> ilog2(mm->chunk_size);
1523 	order = fls(pages) - 1;
1524 
1525 	/*
1526 	 * Offset-aligned allocation is a strict address-placement policy: the
1527 	 * block is chosen purely by its offset alignment, regardless of its
1528 	 * clear/dirty state. Clear state is re-derived from the dirty tracker
1529 	 * once the allocation completes, and the driver is responsible for
1530 	 * issuing the clear pass if a clear region is required.
1531 	 */
1532 	for (tmp = order; tmp <= mm->max_order; ++tmp) {
1533 		block = gpu_buddy_find_block_aligned(mm, tmp, alignment);
1534 		if (block)
1535 			break;
1536 	}
1537 
1538 	if (!block)
1539 		return ERR_PTR(-ENOSPC);
1540 
1541 	while (gpu_buddy_block_order(block) > order) {
1542 		struct gpu_buddy_block *left, *right;
1543 
1544 		err = split_block(mm, block);
1545 		if (unlikely(err))
1546 			goto err_undo;
1547 
1548 		left  = block->left;
1549 		right = block->right;
1550 
1551 		if (gpu_buddy_block_offset_alignment(right) >= alignment)
1552 			block = right;
1553 		else
1554 			block = left;
1555 	}
1556 
1557 	return block;
1558 
1559 err_undo:
1560 	/*
1561 	 * We really don't want to leave around a bunch of split blocks, since
1562 	 * bigger is better, so make sure we merge everything back before we
1563 	 * free the allocated blocks.
1564 	 */
1565 	__gpu_buddy_undo_splits(mm, block);
1566 	return ERR_PTR(err);
1567 }
1568 
1569 static int __alloc_range(struct gpu_buddy *mm,
1570 			 struct list_head *dfs,
1571 			 u64 start, u64 size,
1572 			 unsigned long flags,
1573 			 struct list_head *blocks,
1574 			 u64 *total_allocated_on_err)
1575 {
1576 	struct gpu_buddy_block *block;
1577 	u64 total_allocated = 0;
1578 	LIST_HEAD(allocated);
1579 	u64 end;
1580 	int err;
1581 
1582 	end = start + size - 1;
1583 
1584 	do {
1585 		u64 block_start;
1586 		u64 block_end;
1587 
1588 		block = list_first_entry_or_null(dfs,
1589 						 struct gpu_buddy_block,
1590 						 tmp_link);
1591 		if (!block)
1592 			break;
1593 
1594 		list_del(&block->tmp_link);
1595 
1596 		block_start = gpu_buddy_block_offset(block);
1597 		block_end = block_start + gpu_buddy_block_size(mm, block) - 1;
1598 
1599 		if (!overlaps(start, end, block_start, block_end))
1600 			continue;
1601 
1602 		if (gpu_buddy_block_is_allocated(block)) {
1603 			err = -ENOSPC;
1604 			goto err_free;
1605 		}
1606 
1607 		if (contains(start, end, block_start, block_end)) {
1608 			if (gpu_buddy_block_is_free(block)) {
1609 				u64 block_offset;
1610 				u64 block_size;
1611 
1612 				block_size = gpu_buddy_block_size(mm, block);
1613 				block_offset = gpu_buddy_block_offset(block);
1614 
1615 				if (!gpu_buddy_block_is_clear(block))
1616 					gpu_dirty_tracker_remove_range(&mm->dirty,
1617 								       block_offset,
1618 								       block_size);
1619 
1620 				mark_allocated(mm, block);
1621 				total_allocated += block_size;
1622 				mm->avail -= block_size;
1623 
1624 				list_add_tail(&block->link, &allocated);
1625 				continue;
1626 			}
1627 		}
1628 
1629 		if (!gpu_buddy_block_is_split(block)) {
1630 			err = split_block(mm, block);
1631 			if (unlikely(err))
1632 				goto err_undo;
1633 		}
1634 
1635 		list_add(&block->right->tmp_link, dfs);
1636 		list_add(&block->left->tmp_link, dfs);
1637 	} while (1);
1638 
1639 	if (total_allocated < size) {
1640 		err = -ENOSPC;
1641 		goto err_free;
1642 	}
1643 
1644 	list_splice_tail(&allocated, blocks);
1645 
1646 	return 0;
1647 
1648 err_undo:
1649 	/*
1650 	 * We really don't want to leave around a bunch of split blocks, since
1651 	 * bigger is better, so make sure we merge everything back before we
1652 	 * free the allocated blocks.
1653 	 */
1654 	__gpu_buddy_undo_splits(mm, block);
1655 
1656 err_free:
1657 	if (err == -ENOSPC && total_allocated_on_err) {
1658 		list_splice_tail(&allocated, blocks);
1659 		*total_allocated_on_err = total_allocated;
1660 	} else {
1661 		gpu_buddy_free_list_internal(mm, &allocated);
1662 	}
1663 
1664 	return err;
1665 }
1666 
1667 static int __gpu_buddy_alloc_range(struct gpu_buddy *mm,
1668 				   u64 start,
1669 				   u64 size,
1670 				   unsigned long flags,
1671 				   u64 *total_allocated_on_err,
1672 				   struct list_head *blocks)
1673 {
1674 	LIST_HEAD(dfs);
1675 	int i;
1676 
1677 	for (i = 0; i < mm->n_roots; ++i)
1678 		list_add_tail(&mm->roots[i]->tmp_link, &dfs);
1679 
1680 	return __alloc_range(mm, &dfs, start, size, flags,
1681 			     blocks, total_allocated_on_err);
1682 }
1683 
1684 static int __alloc_contig_aligned_retry(struct gpu_buddy *mm,
1685 					u64 unaligned_offset,
1686 					u64 size,
1687 					u64 min_block_size,
1688 					unsigned long flags,
1689 					struct list_head *blocks)
1690 {
1691 	u64 aligned_offset = round_down(unaligned_offset, min_block_size);
1692 
1693 	return __gpu_buddy_alloc_range(mm, aligned_offset, size, flags,
1694 				       NULL, blocks);
1695 }
1696 
1697 static int __alloc_contig_try_harder(struct gpu_buddy *mm,
1698 				     u64 size,
1699 				     u64 min_block_size,
1700 				     unsigned long flags,
1701 				     struct list_head *blocks)
1702 {
1703 	u64 rhs_offset, lhs_offset, filled;
1704 	struct gpu_buddy_block *block;
1705 	struct rb_root *root;
1706 	struct rb_node *iter;
1707 	unsigned long pages;
1708 	unsigned int order;
1709 	u64 modify_size;
1710 	int err;
1711 
1712 	modify_size = rounddown_pow_of_two(size);
1713 	pages = modify_size >> ilog2(mm->chunk_size);
1714 	order = fls(pages) - 1;
1715 	if (order == 0)
1716 		return -ENOSPC;
1717 
1718 	root = &mm->free_tree[order];
1719 	if (RB_EMPTY_ROOT(root))
1720 		return -ENOSPC;
1721 
1722 	iter = rb_last(root);
1723 	while (iter) {
1724 		block = rbtree_get_free_block(iter);
1725 
1726 		rhs_offset = gpu_buddy_block_offset(block);
1727 
1728 		/* Allocate blocks traversing RHS */
1729 		err =  __gpu_buddy_alloc_range(mm, rhs_offset, size,
1730 					       flags, &filled, blocks);
1731 		if (err && err != -ENOSPC)
1732 			return err;
1733 		if (!err && IS_ALIGNED(rhs_offset, min_block_size))
1734 			return 0;
1735 		if (!err) {
1736 			/* Allocate the unaligned RHS offset using round_down */
1737 			gpu_buddy_free_list_internal(mm, blocks);
1738 			err = __alloc_contig_aligned_retry(mm, rhs_offset,
1739 							   size,
1740 							   min_block_size,
1741 							   flags, blocks);
1742 			if (!err)
1743 				return 0;
1744 			if (err != -ENOSPC) {
1745 				gpu_buddy_free_list_internal(mm, blocks);
1746 				return err;
1747 			}
1748 			goto next;
1749 		}
1750 
1751 		if (size - filled > rhs_offset)
1752 			goto next;
1753 
1754 		lhs_offset = rhs_offset - (size - filled);
1755 
1756 		/* Allocate the unaligned LHS offset using round_down */
1757 		gpu_buddy_free_list_internal(mm, blocks);
1758 		err = __alloc_contig_aligned_retry(mm, lhs_offset,
1759 						   size,
1760 						   min_block_size,
1761 						   flags, blocks);
1762 		if (!err)
1763 			return 0;
1764 		if (err != -ENOSPC) {
1765 			gpu_buddy_free_list_internal(mm, blocks);
1766 			return err;
1767 		}
1768 next:
1769 		gpu_buddy_free_list_internal(mm, blocks);
1770 		iter = rb_prev(iter);
1771 	}
1772 
1773 	return -ENOSPC;
1774 }
1775 
1776 /**
1777  * gpu_buddy_block_trim - free unused pages
1778  *
1779  * @mm: GPU buddy manager
1780  * @start: start address to begin the trimming.
1781  * @new_size: original size requested
1782  * @blocks: Input and output list of allocated blocks.
1783  * MUST contain single block as input to be trimmed.
1784  * On success will contain the newly allocated blocks
1785  * making up the @new_size. Blocks always appear in
1786  * ascending order
1787  *
1788  * For contiguous allocation, we round up the size to the nearest
1789  * power of two value, drivers consume *actual* size, so remaining
1790  * portions are unused and can be optionally freed with this function
1791  *
1792  * Returns:
1793  * 0 on success, error code on failure.
1794  */
1795 int gpu_buddy_block_trim(struct gpu_buddy *mm,
1796 			 u64 *start,
1797 			 u64 new_size,
1798 			 struct list_head *blocks)
1799 {
1800 	struct gpu_buddy_block *parent;
1801 	struct gpu_buddy_block *block;
1802 	u64 block_start, block_end;
1803 	LIST_HEAD(dfs);
1804 	bool was_clear;
1805 	u64 new_start;
1806 	int err;
1807 
1808 	gpu_buddy_driver_lock_held(mm);
1809 
1810 	if (!list_is_singular(blocks))
1811 		return -EINVAL;
1812 
1813 	block = list_first_entry(blocks,
1814 				 struct gpu_buddy_block,
1815 				 link);
1816 
1817 	block_start = gpu_buddy_block_offset(block);
1818 	block_end = block_start + gpu_buddy_block_size(mm, block);
1819 
1820 	if (WARN_ON(!gpu_buddy_block_is_allocated(block)))
1821 		return -EINVAL;
1822 
1823 	if (new_size > gpu_buddy_block_size(mm, block))
1824 		return -EINVAL;
1825 
1826 	if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size))
1827 		return -EINVAL;
1828 
1829 	if (new_size == gpu_buddy_block_size(mm, block))
1830 		return 0;
1831 
1832 	new_start = block_start;
1833 	if (start) {
1834 		new_start = *start;
1835 
1836 		if (new_start < block_start)
1837 			return -EINVAL;
1838 
1839 		if (!IS_ALIGNED(new_start, mm->chunk_size))
1840 			return -EINVAL;
1841 
1842 		if (range_overflows(new_start, new_size, block_end))
1843 			return -EINVAL;
1844 	}
1845 
1846 	list_del(&block->link);
1847 
1848 	was_clear = gpu_buddy_block_is_clear(block);
1849 
1850 	if (!was_clear)
1851 		gpu_dirty_tracker_mark_dirty(&mm->dirty,
1852 					     gpu_buddy_block_offset(block),
1853 					     gpu_buddy_block_size(mm, block));
1854 
1855 	__mark_free(mm, block, was_clear ? GPU_BLOCK_CLEAR : GPU_BLOCK_DIRTY);
1856 	mm->avail += gpu_buddy_block_size(mm, block);
1857 
1858 	/* Prevent recursively freeing this node */
1859 	parent = block->parent;
1860 	block->parent = NULL;
1861 
1862 	list_add(&block->tmp_link, &dfs);
1863 	err =  __alloc_range(mm, &dfs, new_start, new_size,
1864 			     was_clear ? GPU_BUDDY_CLEAR_ALLOCATION : 0,
1865 			     blocks, NULL);
1866 	if (err) {
1867 		mark_allocated(mm, block);
1868 		mm->avail -= gpu_buddy_block_size(mm, block);
1869 		if (!was_clear) {
1870 			gpu_dirty_tracker_remove_range(&mm->dirty,
1871 						       gpu_buddy_block_offset(block),
1872 						       gpu_buddy_block_size(mm, block));
1873 		}
1874 		if (was_clear)
1875 			block->header |= GPU_BUDDY_HEADER_CLEAR;
1876 		list_add(&block->link, blocks);
1877 	}
1878 
1879 	block->parent = parent;
1880 	return err;
1881 }
1882 EXPORT_SYMBOL(gpu_buddy_block_trim);
1883 
1884 static bool dirty_steer_window(struct gpu_buddy *mm, u64 req_size,
1885 			       u64 *start, u64 *end, unsigned long *flags)
1886 {
1887 	u64 aligned_start;
1888 	struct gpu_dirty_extent *ext =
1889 		gpu_dirty_tracker_find(&mm->dirty, req_size, &aligned_start);
1890 
1891 	if (!ext)
1892 		return false;
1893 
1894 	*start  = aligned_start;
1895 	*end    = ext->end;
1896 	*flags |= GPU_BUDDY_RANGE_ALLOCATION;
1897 	return true;
1898 }
1899 
1900 static struct gpu_buddy_block *
1901 __gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
1902 			 u64 start, u64 end,
1903 			 u64 size, u64 min_block_size,
1904 			 unsigned int order,
1905 			 unsigned long flags)
1906 {
1907 	struct gpu_buddy_block *block;
1908 	bool steered = false;
1909 
1910 	/* Allocate from dirty tracker */
1911 	if (!(flags & GPU_BUDDY_RANGE_ALLOCATION) &&
1912 	    !(flags & GPU_BUDDY_CLEAR_ALLOCATION) &&
1913 	    size >= min_block_size &&
1914 	    gpu_buddy_clear_avail(mm) && mm->dirty.total_dirty) {
1915 		u64 block_size = mm->chunk_size << order;
1916 
1917 		steered = dirty_steer_window(mm, block_size,
1918 					     &start, &end, &flags);
1919 	}
1920 
1921 	if (flags & GPU_BUDDY_RANGE_ALLOCATION) {
1922 		/* Allocate traversing within the range */
1923 		block = __alloc_range_bias(mm, start, end, order, flags);
1924 		if (!IS_ERR(block) || !steered)
1925 			return block;
1926 
1927 		flags &= ~GPU_BUDDY_RANGE_ALLOCATION;
1928 	}
1929 
1930 	if (size < min_block_size)
1931 		/* Allocate from an offset-aligned region without size rounding */
1932 		return gpu_buddy_offset_aligned_allocation(mm, size,
1933 							   min_block_size);
1934 
1935 	/* Allocate from freetree */
1936 	return alloc_from_freetree(mm, order, flags);
1937 }
1938 
1939 /**
1940  * gpu_buddy_alloc_blocks - allocate power-of-two blocks
1941  *
1942  * @mm: GPU buddy manager to allocate from
1943  * @start: start of the allowed range for this block
1944  * @end: end of the allowed range for this block
1945  * @size: size of the allocation in bytes
1946  * @min_block_size: alignment of the allocation
1947  * @blocks: output list head to add allocated blocks
1948  * @flags: GPU_BUDDY_*_ALLOCATION flags
1949  *
1950  * alloc_range_bias() called on range limitations, which traverses
1951  * the tree and returns the desired block.
1952  *
1953  * alloc_from_freetree() called when *no* range restrictions
1954  * are enforced, which picks the block from the freetree.
1955  *
1956  * Returns:
1957  * 0 on success, error code on failure.
1958  */
1959 int gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
1960 			   u64 start, u64 end, u64 size,
1961 			   u64 min_block_size,
1962 			   struct list_head *blocks,
1963 			   unsigned long flags)
1964 {
1965 	struct gpu_buddy_block *block = NULL;
1966 	u64 original_size, original_min_size;
1967 	unsigned int min_order, order;
1968 	LIST_HEAD(allocated);
1969 	unsigned long pages;
1970 	int err;
1971 
1972 	gpu_buddy_driver_lock_held(mm);
1973 
1974 	if (size < mm->chunk_size)
1975 		return -EINVAL;
1976 
1977 	if (min_block_size < mm->chunk_size)
1978 		return -EINVAL;
1979 
1980 	if (!is_power_of_2(min_block_size))
1981 		return -EINVAL;
1982 
1983 	if (!IS_ALIGNED(start | end | size, mm->chunk_size))
1984 		return -EINVAL;
1985 
1986 	if (end > mm->size)
1987 		return -EINVAL;
1988 
1989 	if (range_overflows(start, size, mm->size))
1990 		return -EINVAL;
1991 
1992 	/* Actual range allocation */
1993 	if (start + size == end) {
1994 		if (!IS_ALIGNED(start | end, min_block_size))
1995 			return -EINVAL;
1996 
1997 		return __gpu_buddy_alloc_range(mm, start, size, flags, NULL, blocks);
1998 	}
1999 
2000 	original_size = size;
2001 	original_min_size = min_block_size;
2002 
2003 	/* Roundup the size to power of 2 */
2004 	if (flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION) {
2005 		size = roundup_pow_of_two(size);
2006 		min_block_size = size;
2007 		/*
2008 		 * Normalize the requested size to min_block_size for regular allocations.
2009 		 * Offset-aligned allocations intentionally skip size rounding.
2010 		 */
2011 	} else if (!gpu_buddy_can_offset_align(size, min_block_size)) {
2012 		size = round_up(size, min_block_size);
2013 	}
2014 
2015 	pages = size >> ilog2(mm->chunk_size);
2016 	order = fls(pages) - 1;
2017 	min_order = ilog2(min_block_size) - ilog2(mm->chunk_size);
2018 
2019 	if (order > mm->max_order || size > mm->size) {
2020 		if ((flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION) &&
2021 		    !(flags & GPU_BUDDY_RANGE_ALLOCATION))
2022 			return __alloc_contig_try_harder(mm, original_size,
2023 							 original_min_size,
2024 							 flags, blocks);
2025 
2026 		return -EINVAL;
2027 	}
2028 
2029 	do {
2030 		order = min(order, (unsigned int)fls(pages) - 1);
2031 		BUG_ON(order > mm->max_order);
2032 		/*
2033 		 * Regular allocations must not allocate blocks smaller than min_block_size.
2034 		 * Offset-aligned allocations deliberately bypass this constraint.
2035 		 */
2036 		BUG_ON(size >= min_block_size && order < min_order);
2037 
2038 		do {
2039 			block = __gpu_buddy_alloc_blocks(mm, start,
2040 							 end,
2041 							 size,
2042 							 min_block_size,
2043 							 order,
2044 							 flags);
2045 			if (!IS_ERR(block))
2046 				break;
2047 
2048 			if (size >= min_block_size && order > min_order) {
2049 				order--;
2050 				continue;
2051 			}
2052 
2053 			/*
2054 			 * Try contiguous block allocation through
2055 			 * try harder method.
2056 			 */
2057 			if (flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION &&
2058 			    !(flags & GPU_BUDDY_RANGE_ALLOCATION)) {
2059 				err = __alloc_contig_try_harder(mm,
2060 								original_size,
2061 								original_min_size,
2062 								flags,
2063 								blocks);
2064 				if (!err)
2065 					return 0;
2066 				if (err != -ENOSPC)
2067 					return err;
2068 				goto err_free;
2069 			}
2070 			err = -ENOSPC;
2071 			goto err_free;
2072 		} while (1);
2073 
2074 		if (!gpu_buddy_block_is_clear(block))
2075 			gpu_dirty_tracker_remove_range(&mm->dirty,
2076 						       gpu_buddy_block_offset(block),
2077 						       gpu_buddy_block_size(mm, block));
2078 
2079 		mark_allocated(mm, block);
2080 		mm->avail -= gpu_buddy_block_size(mm, block);
2081 
2082 		kmemleak_update_trace(block);
2083 		list_add_tail(&block->link, &allocated);
2084 
2085 		pages -= BIT(order);
2086 
2087 		if (!pages)
2088 			break;
2089 	} while (1);
2090 
2091 	/* Trim the allocated block to the required size */
2092 	if (!(flags & GPU_BUDDY_TRIM_DISABLE) &&
2093 	    original_size != size) {
2094 		struct list_head *trim_list;
2095 		LIST_HEAD(temp);
2096 		u64 trim_size;
2097 
2098 		trim_list = &allocated;
2099 		trim_size = original_size;
2100 
2101 		if (!list_is_singular(&allocated)) {
2102 			block = list_last_entry(&allocated, typeof(*block), link);
2103 			list_move(&block->link, &temp);
2104 			trim_list = &temp;
2105 			trim_size = gpu_buddy_block_size(mm, block) -
2106 				(size - original_size);
2107 		}
2108 
2109 		gpu_buddy_block_trim(mm,
2110 				     NULL,
2111 				     trim_size,
2112 				     trim_list);
2113 
2114 		if (!list_empty(&temp))
2115 			list_splice_tail(trim_list, &allocated);
2116 	}
2117 
2118 	list_splice_tail(&allocated, blocks);
2119 	return 0;
2120 
2121 err_free:
2122 	gpu_buddy_free_list_internal(mm, &allocated);
2123 	return err;
2124 }
2125 EXPORT_SYMBOL(gpu_buddy_alloc_blocks);
2126 
2127 /**
2128  * gpu_buddy_block_print - print block information
2129  *
2130  * @mm: GPU buddy manager
2131  * @block: GPU buddy block
2132  */
2133 void gpu_buddy_block_print(struct gpu_buddy *mm,
2134 			   struct gpu_buddy_block *block)
2135 {
2136 	u64 start = gpu_buddy_block_offset(block);
2137 	u64 size = gpu_buddy_block_size(mm, block);
2138 
2139 	pr_info("%#018llx-%#018llx: %llu\n", start, start + size, size);
2140 }
2141 EXPORT_SYMBOL(gpu_buddy_block_print);
2142 
2143 /**
2144  * gpu_buddy_print - print allocator state
2145  *
2146  * @mm: GPU buddy manager
2147  */
2148 void gpu_buddy_print(struct gpu_buddy *mm)
2149 {
2150 	int order;
2151 
2152 	gpu_buddy_driver_lock_held(mm);
2153 	pr_info("chunk_size: %lluKiB, total: %lluMiB, free: %lluMiB, clear_free: %lluMiB\n",
2154 		mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20,
2155 		gpu_buddy_clear_avail(mm) >> 20);
2156 
2157 	for (order = mm->max_order; order >= 0; order--) {
2158 		u64 free_count = mm->free_scoreboard[order];
2159 		u64 used_count = mm->used_scoreboard[order];
2160 		u64 block_size = mm->chunk_size << order;
2161 		u64 free = free_count * block_size;
2162 		u64 used = used_count * block_size;
2163 
2164 		if (block_size < SZ_1M)
2165 			pr_info("order-%2d free: %8llu KiB, used: %8llu KiB, free_blocks: %llu, used_blocks: %llu\n",
2166 				order, free >> 10, used >> 10, free_count, used_count);
2167 		else
2168 			pr_info("order-%2d free: %8llu MiB, used: %8llu MiB, free_blocks: %llu, used_blocks: %llu\n",
2169 				order, free >> 20, used >> 20, free_count, used_count);
2170 	}
2171 }
2172 EXPORT_SYMBOL(gpu_buddy_print);
2173 
2174 static void gpu_buddy_module_exit(void)
2175 {
2176 	kmem_cache_destroy(slab_extents);
2177 	kmem_cache_destroy(slab_blocks);
2178 }
2179 
2180 static int __init gpu_buddy_module_init(void)
2181 {
2182 	slab_blocks = KMEM_CACHE(gpu_buddy_block, 0);
2183 	if (!slab_blocks)
2184 		return -ENOMEM;
2185 
2186 	slab_extents = KMEM_CACHE(gpu_dirty_extent, 0);
2187 	if (!slab_extents)
2188 		goto err_destroy_blocks;
2189 
2190 	return 0;
2191 
2192 err_destroy_blocks:
2193 	kmem_cache_destroy(slab_blocks);
2194 	return -ENOMEM;
2195 }
2196 
2197 module_init(gpu_buddy_module_init);
2198 module_exit(gpu_buddy_module_exit);
2199 
2200 MODULE_DESCRIPTION("GPU Buddy Allocator");
2201 MODULE_LICENSE("Dual MIT/GPL");
2202