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#include <drm/drmP.h>
45#include <drm/drm_mm.h>
46#include <linux/slab.h>
47#include <linux/seq_file.h>
48#include <linux/export.h>
49
50
51
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
93static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm,
94 u64 size,
95 unsigned alignment,
96 unsigned long color,
97 enum drm_mm_search_flags flags);
98static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_mm *mm,
99 u64 size,
100 unsigned alignment,
101 unsigned long color,
102 u64 start,
103 u64 end,
104 enum drm_mm_search_flags flags);
105
106static void drm_mm_insert_helper(struct drm_mm_node *hole_node,
107 struct drm_mm_node *node,
108 u64 size, unsigned alignment,
109 unsigned long color,
110 enum drm_mm_allocator_flags flags)
111{
112 struct drm_mm *mm = hole_node->mm;
113 u64 hole_start = drm_mm_hole_node_start(hole_node);
114 u64 hole_end = drm_mm_hole_node_end(hole_node);
115 u64 adj_start = hole_start;
116 u64 adj_end = hole_end;
117
118 BUG_ON(node->allocated);
119
120 if (mm->color_adjust)
121 mm->color_adjust(hole_node, color, &adj_start, &adj_end);
122
123 if (flags & DRM_MM_CREATE_TOP)
124 adj_start = adj_end - size;
125
126 if (alignment) {
127 u64 tmp = adj_start;
128 unsigned rem;
129
130 rem = do_div(tmp, alignment);
131 if (rem) {
132 if (flags & DRM_MM_CREATE_TOP)
133 adj_start -= rem;
134 else
135 adj_start += alignment - rem;
136 }
137 }
138
139 BUG_ON(adj_start < hole_start);
140 BUG_ON(adj_end > hole_end);
141
142 if (adj_start == hole_start) {
143 hole_node->hole_follows = 0;
144 list_del(&hole_node->hole_stack);
145 }
146
147 node->start = adj_start;
148 node->size = size;
149 node->mm = mm;
150 node->color = color;
151 node->allocated = 1;
152
153 INIT_LIST_HEAD(&node->hole_stack);
154 list_add(&node->node_list, &hole_node->node_list);
155
156 BUG_ON(node->start + node->size > adj_end);
157
158 node->hole_follows = 0;
159 if (__drm_mm_hole_node_start(node) < hole_end) {
160 list_add(&node->hole_stack, &mm->hole_stack);
161 node->hole_follows = 1;
162 }
163}
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node)
180{
181 struct drm_mm_node *hole;
182 u64 end = node->start + node->size;
183 u64 hole_start;
184 u64 hole_end;
185
186 BUG_ON(node == NULL);
187
188
189 drm_mm_for_each_hole(hole, mm, hole_start, hole_end) {
190 if (hole_start > node->start || hole_end < end)
191 continue;
192
193 node->mm = mm;
194 node->allocated = 1;
195
196 INIT_LIST_HEAD(&node->hole_stack);
197 list_add(&node->node_list, &hole->node_list);
198
199 if (node->start == hole_start) {
200 hole->hole_follows = 0;
201 list_del_init(&hole->hole_stack);
202 }
203
204 node->hole_follows = 0;
205 if (end != hole_end) {
206 list_add(&node->hole_stack, &mm->hole_stack);
207 node->hole_follows = 1;
208 }
209
210 return 0;
211 }
212
213 return -ENOSPC;
214}
215EXPORT_SYMBOL(drm_mm_reserve_node);
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232int drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node,
233 u64 size, unsigned alignment,
234 unsigned long color,
235 enum drm_mm_search_flags sflags,
236 enum drm_mm_allocator_flags aflags)
237{
238 struct drm_mm_node *hole_node;
239
240 hole_node = drm_mm_search_free_generic(mm, size, alignment,
241 color, sflags);
242 if (!hole_node)
243 return -ENOSPC;
244
245 drm_mm_insert_helper(hole_node, node, size, alignment, color, aflags);
246 return 0;
247}
248EXPORT_SYMBOL(drm_mm_insert_node_generic);
249
250static void drm_mm_insert_helper_range(struct drm_mm_node *hole_node,
251 struct drm_mm_node *node,
252 u64 size, unsigned alignment,
253 unsigned long color,
254 u64 start, u64 end,
255 enum drm_mm_allocator_flags flags)
256{
257 struct drm_mm *mm = hole_node->mm;
258 u64 hole_start = drm_mm_hole_node_start(hole_node);
259 u64 hole_end = drm_mm_hole_node_end(hole_node);
260 u64 adj_start = hole_start;
261 u64 adj_end = hole_end;
262
263 BUG_ON(!hole_node->hole_follows || node->allocated);
264
265 if (adj_start < start)
266 adj_start = start;
267 if (adj_end > end)
268 adj_end = end;
269
270 if (flags & DRM_MM_CREATE_TOP)
271 adj_start = adj_end - size;
272
273 if (mm->color_adjust)
274 mm->color_adjust(hole_node, color, &adj_start, &adj_end);
275
276 if (alignment) {
277 u64 tmp = adj_start;
278 unsigned rem;
279
280 rem = do_div(tmp, alignment);
281 if (rem) {
282 if (flags & DRM_MM_CREATE_TOP)
283 adj_start -= rem;
284 else
285 adj_start += alignment - rem;
286 }
287 }
288
289 if (adj_start == hole_start) {
290 hole_node->hole_follows = 0;
291 list_del(&hole_node->hole_stack);
292 }
293
294 node->start = adj_start;
295 node->size = size;
296 node->mm = mm;
297 node->color = color;
298 node->allocated = 1;
299
300 INIT_LIST_HEAD(&node->hole_stack);
301 list_add(&node->node_list, &hole_node->node_list);
302
303 BUG_ON(node->start < start);
304 BUG_ON(node->start < adj_start);
305 BUG_ON(node->start + node->size > adj_end);
306 BUG_ON(node->start + node->size > end);
307
308 node->hole_follows = 0;
309 if (__drm_mm_hole_node_start(node) < hole_end) {
310 list_add(&node->hole_stack, &mm->hole_stack);
311 node->hole_follows = 1;
312 }
313}
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332int drm_mm_insert_node_in_range_generic(struct drm_mm *mm, struct drm_mm_node *node,
333 u64 size, unsigned alignment,
334 unsigned long color,
335 u64 start, u64 end,
336 enum drm_mm_search_flags sflags,
337 enum drm_mm_allocator_flags aflags)
338{
339 struct drm_mm_node *hole_node;
340
341 hole_node = drm_mm_search_free_in_range_generic(mm,
342 size, alignment, color,
343 start, end, sflags);
344 if (!hole_node)
345 return -ENOSPC;
346
347 drm_mm_insert_helper_range(hole_node, node,
348 size, alignment, color,
349 start, end, aflags);
350 return 0;
351}
352EXPORT_SYMBOL(drm_mm_insert_node_in_range_generic);
353
354
355
356
357
358
359
360
361
362void drm_mm_remove_node(struct drm_mm_node *node)
363{
364 struct drm_mm *mm = node->mm;
365 struct drm_mm_node *prev_node;
366
367 if (WARN_ON(!node->allocated))
368 return;
369
370 BUG_ON(node->scanned_block || node->scanned_prev_free
371 || node->scanned_next_free);
372
373 prev_node =
374 list_entry(node->node_list.prev, struct drm_mm_node, node_list);
375
376 if (node->hole_follows) {
377 BUG_ON(__drm_mm_hole_node_start(node) ==
378 __drm_mm_hole_node_end(node));
379 list_del(&node->hole_stack);
380 } else
381 BUG_ON(__drm_mm_hole_node_start(node) !=
382 __drm_mm_hole_node_end(node));
383
384
385 if (!prev_node->hole_follows) {
386 prev_node->hole_follows = 1;
387 list_add(&prev_node->hole_stack, &mm->hole_stack);
388 } else
389 list_move(&prev_node->hole_stack, &mm->hole_stack);
390
391 list_del(&node->node_list);
392 node->allocated = 0;
393}
394EXPORT_SYMBOL(drm_mm_remove_node);
395
396static int check_free_hole(u64 start, u64 end, u64 size, unsigned alignment)
397{
398 if (end - start < size)
399 return 0;
400
401 if (alignment) {
402 u64 tmp = start;
403 unsigned rem;
404
405 rem = do_div(tmp, alignment);
406 if (rem)
407 start += alignment - rem;
408 }
409
410 return end >= start + size;
411}
412
413static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm,
414 u64 size,
415 unsigned alignment,
416 unsigned long color,
417 enum drm_mm_search_flags flags)
418{
419 struct drm_mm_node *entry;
420 struct drm_mm_node *best;
421 u64 adj_start;
422 u64 adj_end;
423 u64 best_size;
424
425 BUG_ON(mm->scanned_blocks);
426
427 best = NULL;
428 best_size = ~0UL;
429
430 __drm_mm_for_each_hole(entry, mm, adj_start, adj_end,
431 flags & DRM_MM_SEARCH_BELOW) {
432 u64 hole_size = adj_end - adj_start;
433
434 if (mm->color_adjust) {
435 mm->color_adjust(entry, color, &adj_start, &adj_end);
436 if (adj_end <= adj_start)
437 continue;
438 }
439
440 if (!check_free_hole(adj_start, adj_end, size, alignment))
441 continue;
442
443 if (!(flags & DRM_MM_SEARCH_BEST))
444 return entry;
445
446 if (hole_size < best_size) {
447 best = entry;
448 best_size = hole_size;
449 }
450 }
451
452 return best;
453}
454
455static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_mm *mm,
456 u64 size,
457 unsigned alignment,
458 unsigned long color,
459 u64 start,
460 u64 end,
461 enum drm_mm_search_flags flags)
462{
463 struct drm_mm_node *entry;
464 struct drm_mm_node *best;
465 u64 adj_start;
466 u64 adj_end;
467 u64 best_size;
468
469 BUG_ON(mm->scanned_blocks);
470
471 best = NULL;
472 best_size = ~0UL;
473
474 __drm_mm_for_each_hole(entry, mm, adj_start, adj_end,
475 flags & DRM_MM_SEARCH_BELOW) {
476 u64 hole_size = adj_end - adj_start;
477
478 if (adj_start < start)
479 adj_start = start;
480 if (adj_end > end)
481 adj_end = end;
482
483 if (mm->color_adjust) {
484 mm->color_adjust(entry, color, &adj_start, &adj_end);
485 if (adj_end <= adj_start)
486 continue;
487 }
488
489 if (!check_free_hole(adj_start, adj_end, size, alignment))
490 continue;
491
492 if (!(flags & DRM_MM_SEARCH_BEST))
493 return entry;
494
495 if (hole_size < best_size) {
496 best = entry;
497 best_size = hole_size;
498 }
499 }
500
501 return best;
502}
503
504
505
506
507
508
509
510
511
512
513void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new)
514{
515 list_replace(&old->node_list, &new->node_list);
516 list_replace(&old->hole_stack, &new->hole_stack);
517 new->hole_follows = old->hole_follows;
518 new->mm = old->mm;
519 new->start = old->start;
520 new->size = old->size;
521 new->color = old->color;
522
523 old->allocated = 0;
524 new->allocated = 1;
525}
526EXPORT_SYMBOL(drm_mm_replace_node);
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571void drm_mm_init_scan(struct drm_mm *mm,
572 u64 size,
573 unsigned alignment,
574 unsigned long color)
575{
576 mm->scan_color = color;
577 mm->scan_alignment = alignment;
578 mm->scan_size = size;
579 mm->scanned_blocks = 0;
580 mm->scan_hit_start = 0;
581 mm->scan_hit_end = 0;
582 mm->scan_check_range = 0;
583 mm->prev_scanned_node = NULL;
584}
585EXPORT_SYMBOL(drm_mm_init_scan);
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604void drm_mm_init_scan_with_range(struct drm_mm *mm,
605 u64 size,
606 unsigned alignment,
607 unsigned long color,
608 u64 start,
609 u64 end)
610{
611 mm->scan_color = color;
612 mm->scan_alignment = alignment;
613 mm->scan_size = size;
614 mm->scanned_blocks = 0;
615 mm->scan_hit_start = 0;
616 mm->scan_hit_end = 0;
617 mm->scan_start = start;
618 mm->scan_end = end;
619 mm->scan_check_range = 1;
620 mm->prev_scanned_node = NULL;
621}
622EXPORT_SYMBOL(drm_mm_init_scan_with_range);
623
624
625
626
627
628
629
630
631
632
633
634bool drm_mm_scan_add_block(struct drm_mm_node *node)
635{
636 struct drm_mm *mm = node->mm;
637 struct drm_mm_node *prev_node;
638 u64 hole_start, hole_end;
639 u64 adj_start, adj_end;
640
641 mm->scanned_blocks++;
642
643 BUG_ON(node->scanned_block);
644 node->scanned_block = 1;
645
646 prev_node = list_entry(node->node_list.prev, struct drm_mm_node,
647 node_list);
648
649 node->scanned_preceeds_hole = prev_node->hole_follows;
650 prev_node->hole_follows = 1;
651 list_del(&node->node_list);
652 node->node_list.prev = &prev_node->node_list;
653 node->node_list.next = &mm->prev_scanned_node->node_list;
654 mm->prev_scanned_node = node;
655
656 adj_start = hole_start = drm_mm_hole_node_start(prev_node);
657 adj_end = hole_end = drm_mm_hole_node_end(prev_node);
658
659 if (mm->scan_check_range) {
660 if (adj_start < mm->scan_start)
661 adj_start = mm->scan_start;
662 if (adj_end > mm->scan_end)
663 adj_end = mm->scan_end;
664 }
665
666 if (mm->color_adjust)
667 mm->color_adjust(prev_node, mm->scan_color,
668 &adj_start, &adj_end);
669
670 if (check_free_hole(adj_start, adj_end,
671 mm->scan_size, mm->scan_alignment)) {
672 mm->scan_hit_start = hole_start;
673 mm->scan_hit_end = hole_end;
674 return true;
675 }
676
677 return false;
678}
679EXPORT_SYMBOL(drm_mm_scan_add_block);
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697bool drm_mm_scan_remove_block(struct drm_mm_node *node)
698{
699 struct drm_mm *mm = node->mm;
700 struct drm_mm_node *prev_node;
701
702 mm->scanned_blocks--;
703
704 BUG_ON(!node->scanned_block);
705 node->scanned_block = 0;
706
707 prev_node = list_entry(node->node_list.prev, struct drm_mm_node,
708 node_list);
709
710 prev_node->hole_follows = node->scanned_preceeds_hole;
711 list_add(&node->node_list, &prev_node->node_list);
712
713 return (drm_mm_hole_node_end(node) > mm->scan_hit_start &&
714 node->start < mm->scan_hit_end);
715}
716EXPORT_SYMBOL(drm_mm_scan_remove_block);
717
718
719
720
721
722
723
724
725
726bool drm_mm_clean(struct drm_mm * mm)
727{
728 struct list_head *head = &mm->head_node.node_list;
729
730 return (head->next->next == head);
731}
732EXPORT_SYMBOL(drm_mm_clean);
733
734
735
736
737
738
739
740
741
742void drm_mm_init(struct drm_mm * mm, u64 start, u64 size)
743{
744 INIT_LIST_HEAD(&mm->hole_stack);
745 mm->scanned_blocks = 0;
746
747
748 INIT_LIST_HEAD(&mm->head_node.node_list);
749 INIT_LIST_HEAD(&mm->head_node.hole_stack);
750 mm->head_node.hole_follows = 1;
751 mm->head_node.scanned_block = 0;
752 mm->head_node.scanned_prev_free = 0;
753 mm->head_node.scanned_next_free = 0;
754 mm->head_node.mm = mm;
755 mm->head_node.start = start + size;
756 mm->head_node.size = start - mm->head_node.start;
757 list_add_tail(&mm->head_node.hole_stack, &mm->hole_stack);
758
759 mm->color_adjust = NULL;
760}
761EXPORT_SYMBOL(drm_mm_init);
762
763
764
765
766
767
768
769
770void drm_mm_takedown(struct drm_mm * mm)
771{
772 WARN(!list_empty(&mm->head_node.node_list),
773 "Memory manager not clean during takedown.\n");
774}
775EXPORT_SYMBOL(drm_mm_takedown);
776
777static u64 drm_mm_debug_hole(struct drm_mm_node *entry,
778 const char *prefix)
779{
780 u64 hole_start, hole_end, hole_size;
781
782 if (entry->hole_follows) {
783 hole_start = drm_mm_hole_node_start(entry);
784 hole_end = drm_mm_hole_node_end(entry);
785 hole_size = hole_end - hole_start;
786 pr_debug("%s %#llx-%#llx: %llu: free\n", prefix, hole_start,
787 hole_end, hole_size);
788 return hole_size;
789 }
790
791 return 0;
792}
793
794
795
796
797
798
799void drm_mm_debug_table(struct drm_mm *mm, const char *prefix)
800{
801 struct drm_mm_node *entry;
802 u64 total_used = 0, total_free = 0, total = 0;
803
804 total_free += drm_mm_debug_hole(&mm->head_node, prefix);
805
806 drm_mm_for_each_node(entry, mm) {
807 pr_debug("%s %#llx-%#llx: %llu: used\n", prefix, entry->start,
808 entry->start + entry->size, entry->size);
809 total_used += entry->size;
810 total_free += drm_mm_debug_hole(entry, prefix);
811 }
812 total = total_free + total_used;
813
814 pr_debug("%s total: %llu, used %llu free %llu\n", prefix, total,
815 total_used, total_free);
816}
817EXPORT_SYMBOL(drm_mm_debug_table);
818
819#if defined(CONFIG_DEBUG_FS)
820static u64 drm_mm_dump_hole(struct seq_file *m, struct drm_mm_node *entry)
821{
822 u64 hole_start, hole_end, hole_size;
823
824 if (entry->hole_follows) {
825 hole_start = drm_mm_hole_node_start(entry);
826 hole_end = drm_mm_hole_node_end(entry);
827 hole_size = hole_end - hole_start;
828 seq_printf(m, "%#llx-%#llx: %llu: free\n", hole_start,
829 hole_end, hole_size);
830 return hole_size;
831 }
832
833 return 0;
834}
835
836
837
838
839
840
841int drm_mm_dump_table(struct seq_file *m, struct drm_mm *mm)
842{
843 struct drm_mm_node *entry;
844 u64 total_used = 0, total_free = 0, total = 0;
845
846 total_free += drm_mm_dump_hole(m, &mm->head_node);
847
848 drm_mm_for_each_node(entry, mm) {
849 seq_printf(m, "%#016llx-%#016llx: %llu: used\n", entry->start,
850 entry->start + entry->size, entry->size);
851 total_used += entry->size;
852 total_free += drm_mm_dump_hole(m, entry);
853 }
854 total = total_free + total_used;
855
856 seq_printf(m, "total: %llu, used %llu free %llu\n", total,
857 total_used, total_free);
858 return 0;
859}
860EXPORT_SYMBOL(drm_mm_dump_table);
861#endif
862