]> git.karo-electronics.de Git - karo-tx-linux.git/blob - drivers/gpu/drm/drm_mm.c
drm/mm: Remove MM_UNUSED_TARGET
[karo-tx-linux.git] / drivers / gpu / drm / drm_mm.c
1 /**************************************************************************
2  *
3  * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND., USA.
4  * All Rights Reserved.
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a
7  * copy of this software and associated documentation files (the
8  * "Software"), to deal in the Software without restriction, including
9  * without limitation the rights to use, copy, modify, merge, publish,
10  * distribute, sub license, and/or sell copies of the Software, and to
11  * permit persons to whom the Software is furnished to do so, subject to
12  * the following conditions:
13  *
14  * The above copyright notice and this permission notice (including the
15  * next paragraph) shall be included in all copies or substantial portions
16  * of the Software.
17  *
18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20  * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
21  * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
22  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
23  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
24  * USE OR OTHER DEALINGS IN THE SOFTWARE.
25  *
26  *
27  **************************************************************************/
28
29 /*
30  * Generic simple memory manager implementation. Intended to be used as a base
31  * class implementation for more advanced memory managers.
32  *
33  * Note that the algorithm used is quite simple and there might be substantial
34  * performance gains if a smarter free list is implemented. Currently it is just an
35  * unordered stack of free regions. This could easily be improved if an RB-tree
36  * is used instead. At least if we expect heavy fragmentation.
37  *
38  * Aligned allocations can also see improvement.
39  *
40  * Authors:
41  * Thomas Hellström <thomas-at-tungstengraphics-dot-com>
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 static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm,
51                                                 unsigned long size,
52                                                 unsigned alignment,
53                                                 unsigned long color,
54                                                 enum drm_mm_search_flags flags);
55 static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_mm *mm,
56                                                 unsigned long size,
57                                                 unsigned alignment,
58                                                 unsigned long color,
59                                                 unsigned long start,
60                                                 unsigned long end,
61                                                 enum drm_mm_search_flags flags);
62
63 static void drm_mm_insert_helper(struct drm_mm_node *hole_node,
64                                  struct drm_mm_node *node,
65                                  unsigned long size, unsigned alignment,
66                                  unsigned long color)
67 {
68         struct drm_mm *mm = hole_node->mm;
69         unsigned long hole_start = drm_mm_hole_node_start(hole_node);
70         unsigned long hole_end = drm_mm_hole_node_end(hole_node);
71         unsigned long adj_start = hole_start;
72         unsigned long adj_end = hole_end;
73
74         BUG_ON(node->allocated);
75
76         if (mm->color_adjust)
77                 mm->color_adjust(hole_node, color, &adj_start, &adj_end);
78
79         if (alignment) {
80                 unsigned tmp = adj_start % alignment;
81                 if (tmp)
82                         adj_start += alignment - tmp;
83         }
84
85         if (adj_start == hole_start) {
86                 hole_node->hole_follows = 0;
87                 list_del(&hole_node->hole_stack);
88         }
89
90         node->start = adj_start;
91         node->size = size;
92         node->mm = mm;
93         node->color = color;
94         node->allocated = 1;
95
96         INIT_LIST_HEAD(&node->hole_stack);
97         list_add(&node->node_list, &hole_node->node_list);
98
99         BUG_ON(node->start + node->size > adj_end);
100
101         node->hole_follows = 0;
102         if (__drm_mm_hole_node_start(node) < hole_end) {
103                 list_add(&node->hole_stack, &mm->hole_stack);
104                 node->hole_follows = 1;
105         }
106 }
107
108 int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node)
109 {
110         struct drm_mm_node *hole;
111         unsigned long end = node->start + node->size;
112         unsigned long hole_start;
113         unsigned long hole_end;
114
115         BUG_ON(node == NULL);
116
117         /* Find the relevant hole to add our node to */
118         drm_mm_for_each_hole(hole, mm, hole_start, hole_end) {
119                 if (hole_start > node->start || hole_end < end)
120                         continue;
121
122                 node->mm = mm;
123                 node->allocated = 1;
124
125                 INIT_LIST_HEAD(&node->hole_stack);
126                 list_add(&node->node_list, &hole->node_list);
127
128                 if (node->start == hole_start) {
129                         hole->hole_follows = 0;
130                         list_del_init(&hole->hole_stack);
131                 }
132
133                 node->hole_follows = 0;
134                 if (end != hole_end) {
135                         list_add(&node->hole_stack, &mm->hole_stack);
136                         node->hole_follows = 1;
137                 }
138
139                 return 0;
140         }
141
142         WARN(1, "no hole found for node 0x%lx + 0x%lx\n",
143              node->start, node->size);
144         return -ENOSPC;
145 }
146 EXPORT_SYMBOL(drm_mm_reserve_node);
147
148 /**
149  * Search for free space and insert a preallocated memory node. Returns
150  * -ENOSPC if no suitable free area is available. The preallocated memory node
151  * must be cleared.
152  */
153 int drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node,
154                                unsigned long size, unsigned alignment,
155                                unsigned long color,
156                                enum drm_mm_search_flags flags)
157 {
158         struct drm_mm_node *hole_node;
159
160         hole_node = drm_mm_search_free_generic(mm, size, alignment,
161                                                color, flags);
162         if (!hole_node)
163                 return -ENOSPC;
164
165         drm_mm_insert_helper(hole_node, node, size, alignment, color);
166         return 0;
167 }
168 EXPORT_SYMBOL(drm_mm_insert_node_generic);
169
170 static void drm_mm_insert_helper_range(struct drm_mm_node *hole_node,
171                                        struct drm_mm_node *node,
172                                        unsigned long size, unsigned alignment,
173                                        unsigned long color,
174                                        unsigned long start, unsigned long end)
175 {
176         struct drm_mm *mm = hole_node->mm;
177         unsigned long hole_start = drm_mm_hole_node_start(hole_node);
178         unsigned long hole_end = drm_mm_hole_node_end(hole_node);
179         unsigned long adj_start = hole_start;
180         unsigned long adj_end = hole_end;
181
182         BUG_ON(!hole_node->hole_follows || node->allocated);
183
184         if (adj_start < start)
185                 adj_start = start;
186         if (adj_end > end)
187                 adj_end = end;
188
189         if (mm->color_adjust)
190                 mm->color_adjust(hole_node, color, &adj_start, &adj_end);
191
192         if (alignment) {
193                 unsigned tmp = adj_start % alignment;
194                 if (tmp)
195                         adj_start += alignment - tmp;
196         }
197
198         if (adj_start == hole_start) {
199                 hole_node->hole_follows = 0;
200                 list_del(&hole_node->hole_stack);
201         }
202
203         node->start = adj_start;
204         node->size = size;
205         node->mm = mm;
206         node->color = color;
207         node->allocated = 1;
208
209         INIT_LIST_HEAD(&node->hole_stack);
210         list_add(&node->node_list, &hole_node->node_list);
211
212         BUG_ON(node->start + node->size > adj_end);
213         BUG_ON(node->start + node->size > end);
214
215         node->hole_follows = 0;
216         if (__drm_mm_hole_node_start(node) < hole_end) {
217                 list_add(&node->hole_stack, &mm->hole_stack);
218                 node->hole_follows = 1;
219         }
220 }
221
222 /**
223  * Search for free space and insert a preallocated memory node. Returns
224  * -ENOSPC if no suitable free area is available. This is for range
225  * restricted allocations. The preallocated memory node must be cleared.
226  */
227 int drm_mm_insert_node_in_range_generic(struct drm_mm *mm, struct drm_mm_node *node,
228                                         unsigned long size, unsigned alignment, unsigned long color,
229                                         unsigned long start, unsigned long end,
230                                         enum drm_mm_search_flags flags)
231 {
232         struct drm_mm_node *hole_node;
233
234         hole_node = drm_mm_search_free_in_range_generic(mm,
235                                                         size, alignment, color,
236                                                         start, end, flags);
237         if (!hole_node)
238                 return -ENOSPC;
239
240         drm_mm_insert_helper_range(hole_node, node,
241                                    size, alignment, color,
242                                    start, end);
243         return 0;
244 }
245 EXPORT_SYMBOL(drm_mm_insert_node_in_range_generic);
246
247 /**
248  * Remove a memory node from the allocator.
249  */
250 void drm_mm_remove_node(struct drm_mm_node *node)
251 {
252         struct drm_mm *mm = node->mm;
253         struct drm_mm_node *prev_node;
254
255         if (WARN_ON(!node->allocated))
256                 return;
257
258         BUG_ON(node->scanned_block || node->scanned_prev_free
259                                    || node->scanned_next_free);
260
261         prev_node =
262             list_entry(node->node_list.prev, struct drm_mm_node, node_list);
263
264         if (node->hole_follows) {
265                 BUG_ON(__drm_mm_hole_node_start(node) ==
266                        __drm_mm_hole_node_end(node));
267                 list_del(&node->hole_stack);
268         } else
269                 BUG_ON(__drm_mm_hole_node_start(node) !=
270                        __drm_mm_hole_node_end(node));
271
272
273         if (!prev_node->hole_follows) {
274                 prev_node->hole_follows = 1;
275                 list_add(&prev_node->hole_stack, &mm->hole_stack);
276         } else
277                 list_move(&prev_node->hole_stack, &mm->hole_stack);
278
279         list_del(&node->node_list);
280         node->allocated = 0;
281 }
282 EXPORT_SYMBOL(drm_mm_remove_node);
283
284 static int check_free_hole(unsigned long start, unsigned long end,
285                            unsigned long size, unsigned alignment)
286 {
287         if (end - start < size)
288                 return 0;
289
290         if (alignment) {
291                 unsigned tmp = start % alignment;
292                 if (tmp)
293                         start += alignment - tmp;
294         }
295
296         return end >= start + size;
297 }
298
299 static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm,
300                                                       unsigned long size,
301                                                       unsigned alignment,
302                                                       unsigned long color,
303                                                       enum drm_mm_search_flags flags)
304 {
305         struct drm_mm_node *entry;
306         struct drm_mm_node *best;
307         unsigned long adj_start;
308         unsigned long adj_end;
309         unsigned long best_size;
310
311         BUG_ON(mm->scanned_blocks);
312
313         best = NULL;
314         best_size = ~0UL;
315
316         drm_mm_for_each_hole(entry, mm, adj_start, adj_end) {
317                 if (mm->color_adjust) {
318                         mm->color_adjust(entry, color, &adj_start, &adj_end);
319                         if (adj_end <= adj_start)
320                                 continue;
321                 }
322
323                 if (!check_free_hole(adj_start, adj_end, size, alignment))
324                         continue;
325
326                 if (!(flags & DRM_MM_SEARCH_BEST))
327                         return entry;
328
329                 if (entry->size < best_size) {
330                         best = entry;
331                         best_size = entry->size;
332                 }
333         }
334
335         return best;
336 }
337
338 static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_mm *mm,
339                                                         unsigned long size,
340                                                         unsigned alignment,
341                                                         unsigned long color,
342                                                         unsigned long start,
343                                                         unsigned long end,
344                                                         enum drm_mm_search_flags flags)
345 {
346         struct drm_mm_node *entry;
347         struct drm_mm_node *best;
348         unsigned long adj_start;
349         unsigned long adj_end;
350         unsigned long best_size;
351
352         BUG_ON(mm->scanned_blocks);
353
354         best = NULL;
355         best_size = ~0UL;
356
357         drm_mm_for_each_hole(entry, mm, adj_start, adj_end) {
358                 if (adj_start < start)
359                         adj_start = start;
360                 if (adj_end > end)
361                         adj_end = end;
362
363                 if (mm->color_adjust) {
364                         mm->color_adjust(entry, color, &adj_start, &adj_end);
365                         if (adj_end <= adj_start)
366                                 continue;
367                 }
368
369                 if (!check_free_hole(adj_start, adj_end, size, alignment))
370                         continue;
371
372                 if (!(flags & DRM_MM_SEARCH_BEST))
373                         return entry;
374
375                 if (entry->size < best_size) {
376                         best = entry;
377                         best_size = entry->size;
378                 }
379         }
380
381         return best;
382 }
383
384 /**
385  * Moves an allocation. To be used with embedded struct drm_mm_node.
386  */
387 void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new)
388 {
389         list_replace(&old->node_list, &new->node_list);
390         list_replace(&old->hole_stack, &new->hole_stack);
391         new->hole_follows = old->hole_follows;
392         new->mm = old->mm;
393         new->start = old->start;
394         new->size = old->size;
395         new->color = old->color;
396
397         old->allocated = 0;
398         new->allocated = 1;
399 }
400 EXPORT_SYMBOL(drm_mm_replace_node);
401
402 /**
403  * Initializa lru scanning.
404  *
405  * This simply sets up the scanning routines with the parameters for the desired
406  * hole.
407  *
408  * Warning: As long as the scan list is non-empty, no other operations than
409  * adding/removing nodes to/from the scan list are allowed.
410  */
411 void drm_mm_init_scan(struct drm_mm *mm,
412                       unsigned long size,
413                       unsigned alignment,
414                       unsigned long color)
415 {
416         mm->scan_color = color;
417         mm->scan_alignment = alignment;
418         mm->scan_size = size;
419         mm->scanned_blocks = 0;
420         mm->scan_hit_start = 0;
421         mm->scan_hit_end = 0;
422         mm->scan_check_range = 0;
423         mm->prev_scanned_node = NULL;
424 }
425 EXPORT_SYMBOL(drm_mm_init_scan);
426
427 /**
428  * Initializa lru scanning.
429  *
430  * This simply sets up the scanning routines with the parameters for the desired
431  * hole. This version is for range-restricted scans.
432  *
433  * Warning: As long as the scan list is non-empty, no other operations than
434  * adding/removing nodes to/from the scan list are allowed.
435  */
436 void drm_mm_init_scan_with_range(struct drm_mm *mm,
437                                  unsigned long size,
438                                  unsigned alignment,
439                                  unsigned long color,
440                                  unsigned long start,
441                                  unsigned long end)
442 {
443         mm->scan_color = color;
444         mm->scan_alignment = alignment;
445         mm->scan_size = size;
446         mm->scanned_blocks = 0;
447         mm->scan_hit_start = 0;
448         mm->scan_hit_end = 0;
449         mm->scan_start = start;
450         mm->scan_end = end;
451         mm->scan_check_range = 1;
452         mm->prev_scanned_node = NULL;
453 }
454 EXPORT_SYMBOL(drm_mm_init_scan_with_range);
455
456 /**
457  * Add a node to the scan list that might be freed to make space for the desired
458  * hole.
459  *
460  * Returns non-zero, if a hole has been found, zero otherwise.
461  */
462 int drm_mm_scan_add_block(struct drm_mm_node *node)
463 {
464         struct drm_mm *mm = node->mm;
465         struct drm_mm_node *prev_node;
466         unsigned long hole_start, hole_end;
467         unsigned long adj_start, adj_end;
468
469         mm->scanned_blocks++;
470
471         BUG_ON(node->scanned_block);
472         node->scanned_block = 1;
473
474         prev_node = list_entry(node->node_list.prev, struct drm_mm_node,
475                                node_list);
476
477         node->scanned_preceeds_hole = prev_node->hole_follows;
478         prev_node->hole_follows = 1;
479         list_del(&node->node_list);
480         node->node_list.prev = &prev_node->node_list;
481         node->node_list.next = &mm->prev_scanned_node->node_list;
482         mm->prev_scanned_node = node;
483
484         adj_start = hole_start = drm_mm_hole_node_start(prev_node);
485         adj_end = hole_end = drm_mm_hole_node_end(prev_node);
486
487         if (mm->scan_check_range) {
488                 if (adj_start < mm->scan_start)
489                         adj_start = mm->scan_start;
490                 if (adj_end > mm->scan_end)
491                         adj_end = mm->scan_end;
492         }
493
494         if (mm->color_adjust)
495                 mm->color_adjust(prev_node, mm->scan_color,
496                                  &adj_start, &adj_end);
497
498         if (check_free_hole(adj_start, adj_end,
499                             mm->scan_size, mm->scan_alignment)) {
500                 mm->scan_hit_start = hole_start;
501                 mm->scan_hit_end = hole_end;
502                 return 1;
503         }
504
505         return 0;
506 }
507 EXPORT_SYMBOL(drm_mm_scan_add_block);
508
509 /**
510  * Remove a node from the scan list.
511  *
512  * Nodes _must_ be removed in the exact same order from the scan list as they
513  * have been added, otherwise the internal state of the memory manager will be
514  * corrupted.
515  *
516  * When the scan list is empty, the selected memory nodes can be freed. An
517  * immediately following drm_mm_search_free with !DRM_MM_SEARCH_BEST will then
518  * return the just freed block (because its at the top of the free_stack list).
519  *
520  * Returns one if this block should be evicted, zero otherwise. Will always
521  * return zero when no hole has been found.
522  */
523 int drm_mm_scan_remove_block(struct drm_mm_node *node)
524 {
525         struct drm_mm *mm = node->mm;
526         struct drm_mm_node *prev_node;
527
528         mm->scanned_blocks--;
529
530         BUG_ON(!node->scanned_block);
531         node->scanned_block = 0;
532
533         prev_node = list_entry(node->node_list.prev, struct drm_mm_node,
534                                node_list);
535
536         prev_node->hole_follows = node->scanned_preceeds_hole;
537         list_add(&node->node_list, &prev_node->node_list);
538
539          return (drm_mm_hole_node_end(node) > mm->scan_hit_start &&
540                  node->start < mm->scan_hit_end);
541 }
542 EXPORT_SYMBOL(drm_mm_scan_remove_block);
543
544 int drm_mm_clean(struct drm_mm * mm)
545 {
546         struct list_head *head = &mm->head_node.node_list;
547
548         return (head->next->next == head);
549 }
550 EXPORT_SYMBOL(drm_mm_clean);
551
552 void drm_mm_init(struct drm_mm * mm, unsigned long start, unsigned long size)
553 {
554         INIT_LIST_HEAD(&mm->hole_stack);
555         mm->scanned_blocks = 0;
556
557         /* Clever trick to avoid a special case in the free hole tracking. */
558         INIT_LIST_HEAD(&mm->head_node.node_list);
559         INIT_LIST_HEAD(&mm->head_node.hole_stack);
560         mm->head_node.hole_follows = 1;
561         mm->head_node.scanned_block = 0;
562         mm->head_node.scanned_prev_free = 0;
563         mm->head_node.scanned_next_free = 0;
564         mm->head_node.mm = mm;
565         mm->head_node.start = start + size;
566         mm->head_node.size = start - mm->head_node.start;
567         list_add_tail(&mm->head_node.hole_stack, &mm->hole_stack);
568
569         mm->color_adjust = NULL;
570 }
571 EXPORT_SYMBOL(drm_mm_init);
572
573 void drm_mm_takedown(struct drm_mm * mm)
574 {
575         WARN(!list_empty(&mm->head_node.node_list),
576              "Memory manager not clean during takedown.\n");
577 }
578 EXPORT_SYMBOL(drm_mm_takedown);
579
580 static unsigned long drm_mm_debug_hole(struct drm_mm_node *entry,
581                                        const char *prefix)
582 {
583         unsigned long hole_start, hole_end, hole_size;
584
585         if (entry->hole_follows) {
586                 hole_start = drm_mm_hole_node_start(entry);
587                 hole_end = drm_mm_hole_node_end(entry);
588                 hole_size = hole_end - hole_start;
589                 printk(KERN_DEBUG "%s 0x%08lx-0x%08lx: %8lu: free\n",
590                         prefix, hole_start, hole_end,
591                         hole_size);
592                 return hole_size;
593         }
594
595         return 0;
596 }
597
598 void drm_mm_debug_table(struct drm_mm *mm, const char *prefix)
599 {
600         struct drm_mm_node *entry;
601         unsigned long total_used = 0, total_free = 0, total = 0;
602
603         total_free += drm_mm_debug_hole(&mm->head_node, prefix);
604
605         drm_mm_for_each_node(entry, mm) {
606                 printk(KERN_DEBUG "%s 0x%08lx-0x%08lx: %8lu: used\n",
607                         prefix, entry->start, entry->start + entry->size,
608                         entry->size);
609                 total_used += entry->size;
610                 total_free += drm_mm_debug_hole(entry, prefix);
611         }
612         total = total_free + total_used;
613
614         printk(KERN_DEBUG "%s total: %lu, used %lu free %lu\n", prefix, total,
615                 total_used, total_free);
616 }
617 EXPORT_SYMBOL(drm_mm_debug_table);
618
619 #if defined(CONFIG_DEBUG_FS)
620 static unsigned long drm_mm_dump_hole(struct seq_file *m, struct drm_mm_node *entry)
621 {
622         unsigned long hole_start, hole_end, hole_size;
623
624         if (entry->hole_follows) {
625                 hole_start = drm_mm_hole_node_start(entry);
626                 hole_end = drm_mm_hole_node_end(entry);
627                 hole_size = hole_end - hole_start;
628                 seq_printf(m, "0x%08lx-0x%08lx: 0x%08lx: free\n",
629                                 hole_start, hole_end, hole_size);
630                 return hole_size;
631         }
632
633         return 0;
634 }
635
636 int drm_mm_dump_table(struct seq_file *m, struct drm_mm *mm)
637 {
638         struct drm_mm_node *entry;
639         unsigned long total_used = 0, total_free = 0, total = 0;
640
641         total_free += drm_mm_dump_hole(m, &mm->head_node);
642
643         drm_mm_for_each_node(entry, mm) {
644                 seq_printf(m, "0x%08lx-0x%08lx: 0x%08lx: used\n",
645                                 entry->start, entry->start + entry->size,
646                                 entry->size);
647                 total_used += entry->size;
648                 total_free += drm_mm_dump_hole(m, entry);
649         }
650         total = total_free + total_used;
651
652         seq_printf(m, "total: %lu, used %lu free %lu\n", total, total_used, total_free);
653         return 0;
654 }
655 EXPORT_SYMBOL(drm_mm_dump_table);
656 #endif