1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45#include <linux/export.h>
46#include <linux/interval_tree_generic.h>
47#include <linux/seq_file.h>
48#include <linux/slab.h>
49#include <linux/stacktrace.h>
50
51#include <drm/drm_mm.h>
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101#ifdef CONFIG_DRM_DEBUG_MM
102#include <linux/stackdepot.h>
103
104#define STACKDEPTH 32
105#define BUFSZ 4096
106
107static noinline void save_stack(struct drm_mm_node *node)
108{
109 unsigned long entries[STACKDEPTH];
110 unsigned int n;
111
112 n = stack_trace_save(entries, ARRAY_SIZE(entries), 1);
113
114
115 node->stack = stack_depot_save(entries, n, GFP_NOWAIT);
116}
117
118static void show_leaks(struct drm_mm *mm)
119{
120 struct drm_mm_node *node;
121 unsigned long *entries;
122 unsigned int nr_entries;
123 char *buf;
124
125 buf = kmalloc(BUFSZ, GFP_KERNEL);
126 if (!buf)
127 return;
128
129 list_for_each_entry(node, drm_mm_nodes(mm), node_list) {
130 if (!node->stack) {
131 DRM_ERROR("node [%08llx + %08llx]: unknown owner\n",
132 node->start, node->size);
133 continue;
134 }
135
136 nr_entries = stack_depot_fetch(node->stack, &entries);
137 stack_trace_snprint(buf, BUFSZ, entries, nr_entries, 0);
138 DRM_ERROR("node [%08llx + %08llx]: inserted at\n%s",
139 node->start, node->size, buf);
140 }
141
142 kfree(buf);
143}
144
145#undef STACKDEPTH
146#undef BUFSZ
147#else
148static void save_stack(struct drm_mm_node *node) { }
149static void show_leaks(struct drm_mm *mm) { }
150#endif
151
152#define START(node) ((node)->start)
153#define LAST(node) ((node)->start + (node)->size - 1)
154
155INTERVAL_TREE_DEFINE(struct drm_mm_node, rb,
156 u64, __subtree_last,
157 START, LAST, static inline, drm_mm_interval_tree)
158
159struct drm_mm_node *
160__drm_mm_interval_first(const struct drm_mm *mm, u64 start, u64 last)
161{
162 return drm_mm_interval_tree_iter_first((struct rb_root_cached *)&mm->interval_tree,
163 start, last) ?: (struct drm_mm_node *)&mm->head_node;
164}
165EXPORT_SYMBOL(__drm_mm_interval_first);
166
167static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node,
168 struct drm_mm_node *node)
169{
170 struct drm_mm *mm = hole_node->mm;
171 struct rb_node **link, *rb;
172 struct drm_mm_node *parent;
173 bool leftmost;
174
175 node->__subtree_last = LAST(node);
176
177 if (drm_mm_node_allocated(hole_node)) {
178 rb = &hole_node->rb;
179 while (rb) {
180 parent = rb_entry(rb, struct drm_mm_node, rb);
181 if (parent->__subtree_last >= node->__subtree_last)
182 break;
183
184 parent->__subtree_last = node->__subtree_last;
185 rb = rb_parent(rb);
186 }
187
188 rb = &hole_node->rb;
189 link = &hole_node->rb.rb_right;
190 leftmost = false;
191 } else {
192 rb = NULL;
193 link = &mm->interval_tree.rb_root.rb_node;
194 leftmost = true;
195 }
196
197 while (*link) {
198 rb = *link;
199 parent = rb_entry(rb, struct drm_mm_node, rb);
200 if (parent->__subtree_last < node->__subtree_last)
201 parent->__subtree_last = node->__subtree_last;
202 if (node->start < parent->start) {
203 link = &parent->rb.rb_left;
204 } else {
205 link = &parent->rb.rb_right;
206 leftmost = false;
207 }
208 }
209
210 rb_link_node(&node->rb, rb, link);
211 rb_insert_augmented_cached(&node->rb, &mm->interval_tree, leftmost,
212 &drm_mm_interval_tree_augment);
213}
214
215#define HOLE_SIZE(NODE) ((NODE)->hole_size)
216#define HOLE_ADDR(NODE) (__drm_mm_hole_node_start(NODE))
217
218static u64 rb_to_hole_size(struct rb_node *rb)
219{
220 return rb_entry(rb, struct drm_mm_node, rb_hole_size)->hole_size;
221}
222
223static void insert_hole_size(struct rb_root_cached *root,
224 struct drm_mm_node *node)
225{
226 struct rb_node **link = &root->rb_root.rb_node, *rb = NULL;
227 u64 x = node->hole_size;
228 bool first = true;
229
230 while (*link) {
231 rb = *link;
232 if (x > rb_to_hole_size(rb)) {
233 link = &rb->rb_left;
234 } else {
235 link = &rb->rb_right;
236 first = false;
237 }
238 }
239
240 rb_link_node(&node->rb_hole_size, rb, link);
241 rb_insert_color_cached(&node->rb_hole_size, root, first);
242}
243
244RB_DECLARE_CALLBACKS_MAX(static, augment_callbacks,
245 struct drm_mm_node, rb_hole_addr,
246 u64, subtree_max_hole, HOLE_SIZE)
247
248static void insert_hole_addr(struct rb_root *root, struct drm_mm_node *node)
249{
250 struct rb_node **link = &root->rb_node, *rb_parent = NULL;
251 u64 start = HOLE_ADDR(node), subtree_max_hole = node->subtree_max_hole;
252 struct drm_mm_node *parent;
253
254 while (*link) {
255 rb_parent = *link;
256 parent = rb_entry(rb_parent, struct drm_mm_node, rb_hole_addr);
257 if (parent->subtree_max_hole < subtree_max_hole)
258 parent->subtree_max_hole = subtree_max_hole;
259 if (start < HOLE_ADDR(parent))
260 link = &parent->rb_hole_addr.rb_left;
261 else
262 link = &parent->rb_hole_addr.rb_right;
263 }
264
265 rb_link_node(&node->rb_hole_addr, rb_parent, link);
266 rb_insert_augmented(&node->rb_hole_addr, root, &augment_callbacks);
267}
268
269static void add_hole(struct drm_mm_node *node)
270{
271 struct drm_mm *mm = node->mm;
272
273 node->hole_size =
274 __drm_mm_hole_node_end(node) - __drm_mm_hole_node_start(node);
275 node->subtree_max_hole = node->hole_size;
276 DRM_MM_BUG_ON(!drm_mm_hole_follows(node));
277
278 insert_hole_size(&mm->holes_size, node);
279 insert_hole_addr(&mm->holes_addr, node);
280
281 list_add(&node->hole_stack, &mm->hole_stack);
282}
283
284static void rm_hole(struct drm_mm_node *node)
285{
286 DRM_MM_BUG_ON(!drm_mm_hole_follows(node));
287
288 list_del(&node->hole_stack);
289 rb_erase_cached(&node->rb_hole_size, &node->mm->holes_size);
290 rb_erase_augmented(&node->rb_hole_addr, &node->mm->holes_addr,
291 &augment_callbacks);
292 node->hole_size = 0;
293 node->subtree_max_hole = 0;
294
295 DRM_MM_BUG_ON(drm_mm_hole_follows(node));
296}
297
298static inline struct drm_mm_node *rb_hole_size_to_node(struct rb_node *rb)
299{
300 return rb_entry_safe(rb, struct drm_mm_node, rb_hole_size);
301}
302
303static inline struct drm_mm_node *rb_hole_addr_to_node(struct rb_node *rb)
304{
305 return rb_entry_safe(rb, struct drm_mm_node, rb_hole_addr);
306}
307
308static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size)
309{
310 struct rb_node *rb = mm->holes_size.rb_root.rb_node;
311 struct drm_mm_node *best = NULL;
312
313 do {
314 struct drm_mm_node *node =
315 rb_entry(rb, struct drm_mm_node, rb_hole_size);
316
317 if (size <= node->hole_size) {
318 best = node;
319 rb = rb->rb_right;
320 } else {
321 rb = rb->rb_left;
322 }
323 } while (rb);
324
325 return best;
326}
327
328static bool usable_hole_addr(struct rb_node *rb, u64 size)
329{
330 return rb && rb_hole_addr_to_node(rb)->subtree_max_hole >= size;
331}
332
333static struct drm_mm_node *find_hole_addr(struct drm_mm *mm, u64 addr, u64 size)
334{
335 struct rb_node *rb = mm->holes_addr.rb_node;
336 struct drm_mm_node *node = NULL;
337
338 while (rb) {
339 u64 hole_start;
340
341 if (!usable_hole_addr(rb, size))
342 break;
343
344 node = rb_hole_addr_to_node(rb);
345 hole_start = __drm_mm_hole_node_start(node);
346
347 if (addr < hole_start)
348 rb = node->rb_hole_addr.rb_left;
349 else if (addr > hole_start + node->hole_size)
350 rb = node->rb_hole_addr.rb_right;
351 else
352 break;
353 }
354
355 return node;
356}
357
358static struct drm_mm_node *
359first_hole(struct drm_mm *mm,
360 u64 start, u64 end, u64 size,
361 enum drm_mm_insert_mode mode)
362{
363 switch (mode) {
364 default:
365 case DRM_MM_INSERT_BEST:
366 return best_hole(mm, size);
367
368 case DRM_MM_INSERT_LOW:
369 return find_hole_addr(mm, start, size);
370
371 case DRM_MM_INSERT_HIGH:
372 return find_hole_addr(mm, end, size);
373
374 case DRM_MM_INSERT_EVICT:
375 return list_first_entry_or_null(&mm->hole_stack,
376 struct drm_mm_node,
377 hole_stack);
378 }
379}
380
381
382
383
384
385
386
387
388
389
390
391
392#define DECLARE_NEXT_HOLE_ADDR(name, first, last) \
393static struct drm_mm_node *name(struct drm_mm_node *entry, u64 size) \
394{ \
395 struct rb_node *parent, *node = &entry->rb_hole_addr; \
396 \
397 if (!entry || RB_EMPTY_NODE(node)) \
398 return NULL; \
399 \
400 if (usable_hole_addr(node->first, size)) { \
401 node = node->first; \
402 while (usable_hole_addr(node->last, size)) \
403 node = node->last; \
404 return rb_hole_addr_to_node(node); \
405 } \
406 \
407 while ((parent = rb_parent(node)) && node == parent->first) \
408 node = parent; \
409 \
410 return rb_hole_addr_to_node(parent); \
411}
412
413DECLARE_NEXT_HOLE_ADDR(next_hole_high_addr, rb_left, rb_right)
414DECLARE_NEXT_HOLE_ADDR(next_hole_low_addr, rb_right, rb_left)
415
416static struct drm_mm_node *
417next_hole(struct drm_mm *mm,
418 struct drm_mm_node *node,
419 u64 size,
420 enum drm_mm_insert_mode mode)
421{
422 switch (mode) {
423 default:
424 case DRM_MM_INSERT_BEST:
425 return rb_hole_size_to_node(rb_prev(&node->rb_hole_size));
426
427 case DRM_MM_INSERT_LOW:
428 return next_hole_low_addr(node, size);
429
430 case DRM_MM_INSERT_HIGH:
431 return next_hole_high_addr(node, size);
432
433 case DRM_MM_INSERT_EVICT:
434 node = list_next_entry(node, hole_stack);
435 return &node->hole_stack == &mm->hole_stack ? NULL : node;
436 }
437}
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node)
454{
455 struct drm_mm_node *hole;
456 u64 hole_start, hole_end;
457 u64 adj_start, adj_end;
458 u64 end;
459
460 end = node->start + node->size;
461 if (unlikely(end <= node->start))
462 return -ENOSPC;
463
464
465 hole = find_hole_addr(mm, node->start, 0);
466 if (!hole)
467 return -ENOSPC;
468
469 adj_start = hole_start = __drm_mm_hole_node_start(hole);
470 adj_end = hole_end = hole_start + hole->hole_size;
471
472 if (mm->color_adjust)
473 mm->color_adjust(hole, node->color, &adj_start, &adj_end);
474
475 if (adj_start > node->start || adj_end < end)
476 return -ENOSPC;
477
478 node->mm = mm;
479
480 __set_bit(DRM_MM_NODE_ALLOCATED_BIT, &node->flags);
481 list_add(&node->node_list, &hole->node_list);
482 drm_mm_interval_tree_add_node(hole, node);
483 node->hole_size = 0;
484
485 rm_hole(hole);
486 if (node->start > hole_start)
487 add_hole(hole);
488 if (end < hole_end)
489 add_hole(node);
490
491 save_stack(node);
492 return 0;
493}
494EXPORT_SYMBOL(drm_mm_reserve_node);
495
496static u64 rb_to_hole_size_or_zero(struct rb_node *rb)
497{
498 return rb ? rb_to_hole_size(rb) : 0;
499}
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517int drm_mm_insert_node_in_range(struct drm_mm * const mm,
518 struct drm_mm_node * const node,
519 u64 size, u64 alignment,
520 unsigned long color,
521 u64 range_start, u64 range_end,
522 enum drm_mm_insert_mode mode)
523{
524 struct drm_mm_node *hole;
525 u64 remainder_mask;
526 bool once;
527
528 DRM_MM_BUG_ON(range_start > range_end);
529
530 if (unlikely(size == 0 || range_end - range_start < size))
531 return -ENOSPC;
532
533 if (rb_to_hole_size_or_zero(rb_first_cached(&mm->holes_size)) < size)
534 return -ENOSPC;
535
536 if (alignment <= 1)
537 alignment = 0;
538
539 once = mode & DRM_MM_INSERT_ONCE;
540 mode &= ~DRM_MM_INSERT_ONCE;
541
542 remainder_mask = is_power_of_2(alignment) ? alignment - 1 : 0;
543 for (hole = first_hole(mm, range_start, range_end, size, mode);
544 hole;
545 hole = once ? NULL : next_hole(mm, hole, size, mode)) {
546 u64 hole_start = __drm_mm_hole_node_start(hole);
547 u64 hole_end = hole_start + hole->hole_size;
548 u64 adj_start, adj_end;
549 u64 col_start, col_end;
550
551 if (mode == DRM_MM_INSERT_LOW && hole_start >= range_end)
552 break;
553
554 if (mode == DRM_MM_INSERT_HIGH && hole_end <= range_start)
555 break;
556
557 col_start = hole_start;
558 col_end = hole_end;
559 if (mm->color_adjust)
560 mm->color_adjust(hole, color, &col_start, &col_end);
561
562 adj_start = max(col_start, range_start);
563 adj_end = min(col_end, range_end);
564
565 if (adj_end <= adj_start || adj_end - adj_start < size)
566 continue;
567
568 if (mode == DRM_MM_INSERT_HIGH)
569 adj_start = adj_end - size;
570
571 if (alignment) {
572 u64 rem;
573
574 if (likely(remainder_mask))
575 rem = adj_start & remainder_mask;
576 else
577 div64_u64_rem(adj_start, alignment, &rem);
578 if (rem) {
579 adj_start -= rem;
580 if (mode != DRM_MM_INSERT_HIGH)
581 adj_start += alignment;
582
583 if (adj_start < max(col_start, range_start) ||
584 min(col_end, range_end) - adj_start < size)
585 continue;
586
587 if (adj_end <= adj_start ||
588 adj_end - adj_start < size)
589 continue;
590 }
591 }
592
593 node->mm = mm;
594 node->size = size;
595 node->start = adj_start;
596 node->color = color;
597 node->hole_size = 0;
598
599 __set_bit(DRM_MM_NODE_ALLOCATED_BIT, &node->flags);
600 list_add(&node->node_list, &hole->node_list);
601 drm_mm_interval_tree_add_node(hole, node);
602
603 rm_hole(hole);
604 if (adj_start > hole_start)
605 add_hole(hole);
606 if (adj_start + size < hole_end)
607 add_hole(node);
608
609 save_stack(node);
610 return 0;
611 }
612
613 return -ENOSPC;
614}
615EXPORT_SYMBOL(drm_mm_insert_node_in_range);
616
617static inline bool drm_mm_node_scanned_block(const struct drm_mm_node *node)
618{
619 return test_bit(DRM_MM_NODE_SCANNED_BIT, &node->flags);
620}
621
622
623
624
625
626
627
628
629
630void drm_mm_remove_node(struct drm_mm_node *node)
631{
632 struct drm_mm *mm = node->mm;
633 struct drm_mm_node *prev_node;
634
635 DRM_MM_BUG_ON(!drm_mm_node_allocated(node));
636 DRM_MM_BUG_ON(drm_mm_node_scanned_block(node));
637
638 prev_node = list_prev_entry(node, node_list);
639
640 if (drm_mm_hole_follows(node))
641 rm_hole(node);
642
643 drm_mm_interval_tree_remove(node, &mm->interval_tree);
644 list_del(&node->node_list);
645
646 if (drm_mm_hole_follows(prev_node))
647 rm_hole(prev_node);
648 add_hole(prev_node);
649
650 clear_bit_unlock(DRM_MM_NODE_ALLOCATED_BIT, &node->flags);
651}
652EXPORT_SYMBOL(drm_mm_remove_node);
653
654
655
656
657
658
659
660
661
662
663void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new)
664{
665 struct drm_mm *mm = old->mm;
666
667 DRM_MM_BUG_ON(!drm_mm_node_allocated(old));
668
669 *new = *old;
670
671 __set_bit(DRM_MM_NODE_ALLOCATED_BIT, &new->flags);
672 list_replace(&old->node_list, &new->node_list);
673 rb_replace_node_cached(&old->rb, &new->rb, &mm->interval_tree);
674
675 if (drm_mm_hole_follows(old)) {
676 list_replace(&old->hole_stack, &new->hole_stack);
677 rb_replace_node_cached(&old->rb_hole_size,
678 &new->rb_hole_size,
679 &mm->holes_size);
680 rb_replace_node(&old->rb_hole_addr,
681 &new->rb_hole_addr,
682 &mm->holes_addr);
683 }
684
685 clear_bit_unlock(DRM_MM_NODE_ALLOCATED_BIT, &old->flags);
686}
687EXPORT_SYMBOL(drm_mm_replace_node);
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739void drm_mm_scan_init_with_range(struct drm_mm_scan *scan,
740 struct drm_mm *mm,
741 u64 size,
742 u64 alignment,
743 unsigned long color,
744 u64 start,
745 u64 end,
746 enum drm_mm_insert_mode mode)
747{
748 DRM_MM_BUG_ON(start >= end);
749 DRM_MM_BUG_ON(!size || size > end - start);
750 DRM_MM_BUG_ON(mm->scan_active);
751
752 scan->mm = mm;
753
754 if (alignment <= 1)
755 alignment = 0;
756
757 scan->color = color;
758 scan->alignment = alignment;
759 scan->remainder_mask = is_power_of_2(alignment) ? alignment - 1 : 0;
760 scan->size = size;
761 scan->mode = mode;
762
763 DRM_MM_BUG_ON(end <= start);
764 scan->range_start = start;
765 scan->range_end = end;
766
767 scan->hit_start = U64_MAX;
768 scan->hit_end = 0;
769}
770EXPORT_SYMBOL(drm_mm_scan_init_with_range);
771
772
773
774
775
776
777
778
779
780
781
782
783bool drm_mm_scan_add_block(struct drm_mm_scan *scan,
784 struct drm_mm_node *node)
785{
786 struct drm_mm *mm = scan->mm;
787 struct drm_mm_node *hole;
788 u64 hole_start, hole_end;
789 u64 col_start, col_end;
790 u64 adj_start, adj_end;
791
792 DRM_MM_BUG_ON(node->mm != mm);
793 DRM_MM_BUG_ON(!drm_mm_node_allocated(node));
794 DRM_MM_BUG_ON(drm_mm_node_scanned_block(node));
795 __set_bit(DRM_MM_NODE_SCANNED_BIT, &node->flags);
796 mm->scan_active++;
797
798
799
800
801
802
803 hole = list_prev_entry(node, node_list);
804 DRM_MM_BUG_ON(list_next_entry(hole, node_list) != node);
805 __list_del_entry(&node->node_list);
806
807 hole_start = __drm_mm_hole_node_start(hole);
808 hole_end = __drm_mm_hole_node_end(hole);
809
810 col_start = hole_start;
811 col_end = hole_end;
812 if (mm->color_adjust)
813 mm->color_adjust(hole, scan->color, &col_start, &col_end);
814
815 adj_start = max(col_start, scan->range_start);
816 adj_end = min(col_end, scan->range_end);
817 if (adj_end <= adj_start || adj_end - adj_start < scan->size)
818 return false;
819
820 if (scan->mode == DRM_MM_INSERT_HIGH)
821 adj_start = adj_end - scan->size;
822
823 if (scan->alignment) {
824 u64 rem;
825
826 if (likely(scan->remainder_mask))
827 rem = adj_start & scan->remainder_mask;
828 else
829 div64_u64_rem(adj_start, scan->alignment, &rem);
830 if (rem) {
831 adj_start -= rem;
832 if (scan->mode != DRM_MM_INSERT_HIGH)
833 adj_start += scan->alignment;
834 if (adj_start < max(col_start, scan->range_start) ||
835 min(col_end, scan->range_end) - adj_start < scan->size)
836 return false;
837
838 if (adj_end <= adj_start ||
839 adj_end - adj_start < scan->size)
840 return false;
841 }
842 }
843
844 scan->hit_start = adj_start;
845 scan->hit_end = adj_start + scan->size;
846
847 DRM_MM_BUG_ON(scan->hit_start >= scan->hit_end);
848 DRM_MM_BUG_ON(scan->hit_start < hole_start);
849 DRM_MM_BUG_ON(scan->hit_end > hole_end);
850
851 return true;
852}
853EXPORT_SYMBOL(drm_mm_scan_add_block);
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874bool drm_mm_scan_remove_block(struct drm_mm_scan *scan,
875 struct drm_mm_node *node)
876{
877 struct drm_mm_node *prev_node;
878
879 DRM_MM_BUG_ON(node->mm != scan->mm);
880 DRM_MM_BUG_ON(!drm_mm_node_scanned_block(node));
881 __clear_bit(DRM_MM_NODE_SCANNED_BIT, &node->flags);
882
883 DRM_MM_BUG_ON(!node->mm->scan_active);
884 node->mm->scan_active--;
885
886
887
888
889
890
891
892
893
894 prev_node = list_prev_entry(node, node_list);
895 DRM_MM_BUG_ON(list_next_entry(prev_node, node_list) !=
896 list_next_entry(node, node_list));
897 list_add(&node->node_list, &prev_node->node_list);
898
899 return (node->start + node->size > scan->hit_start &&
900 node->start < scan->hit_end);
901}
902EXPORT_SYMBOL(drm_mm_scan_remove_block);
903
904
905
906
907
908
909
910
911
912
913
914
915struct drm_mm_node *drm_mm_scan_color_evict(struct drm_mm_scan *scan)
916{
917 struct drm_mm *mm = scan->mm;
918 struct drm_mm_node *hole;
919 u64 hole_start, hole_end;
920
921 DRM_MM_BUG_ON(list_empty(&mm->hole_stack));
922
923 if (!mm->color_adjust)
924 return NULL;
925
926
927
928
929
930
931 list_for_each_entry(hole, &mm->hole_stack, hole_stack) {
932 hole_start = __drm_mm_hole_node_start(hole);
933 hole_end = hole_start + hole->hole_size;
934
935 if (hole_start <= scan->hit_start &&
936 hole_end >= scan->hit_end)
937 break;
938 }
939
940
941 DRM_MM_BUG_ON(&hole->hole_stack == &mm->hole_stack);
942 if (unlikely(&hole->hole_stack == &mm->hole_stack))
943 return NULL;
944
945 DRM_MM_BUG_ON(hole_start > scan->hit_start);
946 DRM_MM_BUG_ON(hole_end < scan->hit_end);
947
948 mm->color_adjust(hole, scan->color, &hole_start, &hole_end);
949 if (hole_start > scan->hit_start)
950 return hole;
951 if (hole_end < scan->hit_end)
952 return list_next_entry(hole, node_list);
953
954 return NULL;
955}
956EXPORT_SYMBOL(drm_mm_scan_color_evict);
957
958
959
960
961
962
963
964
965
966void drm_mm_init(struct drm_mm *mm, u64 start, u64 size)
967{
968 DRM_MM_BUG_ON(start + size <= start);
969
970 mm->color_adjust = NULL;
971
972 INIT_LIST_HEAD(&mm->hole_stack);
973 mm->interval_tree = RB_ROOT_CACHED;
974 mm->holes_size = RB_ROOT_CACHED;
975 mm->holes_addr = RB_ROOT;
976
977
978 INIT_LIST_HEAD(&mm->head_node.node_list);
979 mm->head_node.flags = 0;
980 mm->head_node.mm = mm;
981 mm->head_node.start = start + size;
982 mm->head_node.size = -size;
983 add_hole(&mm->head_node);
984
985 mm->scan_active = 0;
986}
987EXPORT_SYMBOL(drm_mm_init);
988
989
990
991
992
993
994
995
996void drm_mm_takedown(struct drm_mm *mm)
997{
998 if (WARN(!drm_mm_clean(mm),
999 "Memory manager not clean during takedown.\n"))
1000 show_leaks(mm);
1001}
1002EXPORT_SYMBOL(drm_mm_takedown);
1003
1004static u64 drm_mm_dump_hole(struct drm_printer *p, const struct drm_mm_node *entry)
1005{
1006 u64 start, size;
1007
1008 size = entry->hole_size;
1009 if (size) {
1010 start = drm_mm_hole_node_start(entry);
1011 drm_printf(p, "%#018llx-%#018llx: %llu: free\n",
1012 start, start + size, size);
1013 }
1014
1015 return size;
1016}
1017
1018
1019
1020
1021
1022void drm_mm_print(const struct drm_mm *mm, struct drm_printer *p)
1023{
1024 const struct drm_mm_node *entry;
1025 u64 total_used = 0, total_free = 0, total = 0;
1026
1027 total_free += drm_mm_dump_hole(p, &mm->head_node);
1028
1029 drm_mm_for_each_node(entry, mm) {
1030 drm_printf(p, "%#018llx-%#018llx: %llu: used\n", entry->start,
1031 entry->start + entry->size, entry->size);
1032 total_used += entry->size;
1033 total_free += drm_mm_dump_hole(p, entry);
1034 }
1035 total = total_free + total_used;
1036
1037 drm_printf(p, "total: %llu, used %llu free %llu\n", total,
1038 total_used, total_free);
1039}
1040EXPORT_SYMBOL(drm_mm_print);
1041