1249d6048SJerome Glisse /************************************************************************** 2249d6048SJerome Glisse * 3249d6048SJerome Glisse * Copyright 2006-2008 Tungsten Graphics, Inc., Cedar Park, TX. USA. 4249d6048SJerome Glisse * All Rights Reserved. 5249d6048SJerome Glisse * 6249d6048SJerome Glisse * Permission is hereby granted, free of charge, to any person obtaining a 7249d6048SJerome Glisse * copy of this software and associated documentation files (the 8249d6048SJerome Glisse * "Software"), to deal in the Software without restriction, including 9249d6048SJerome Glisse * without limitation the rights to use, copy, modify, merge, publish, 10249d6048SJerome Glisse * distribute, sub license, and/or sell copies of the Software, and to 11249d6048SJerome Glisse * permit persons to whom the Software is furnished to do so, subject to 12249d6048SJerome Glisse * the following conditions: 13249d6048SJerome Glisse * 14249d6048SJerome Glisse * The above copyright notice and this permission notice (including the 15249d6048SJerome Glisse * next paragraph) shall be included in all copies or substantial portions 16249d6048SJerome Glisse * of the Software. 17249d6048SJerome Glisse * 18249d6048SJerome Glisse * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 19249d6048SJerome Glisse * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 20249d6048SJerome Glisse * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL 21249d6048SJerome Glisse * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, 22249d6048SJerome Glisse * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR 23249d6048SJerome Glisse * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE 24249d6048SJerome Glisse * USE OR OTHER DEALINGS IN THE SOFTWARE. 25249d6048SJerome Glisse * 26249d6048SJerome Glisse * 27249d6048SJerome Glisse **************************************************************************/ 28249d6048SJerome Glisse /* 29249d6048SJerome Glisse * Authors: 30249d6048SJerome Glisse * Thomas Hellstrom <thomas-at-tungstengraphics-dot-com> 31249d6048SJerome Glisse */ 32249d6048SJerome Glisse 33249d6048SJerome Glisse #ifndef _DRM_MM_H_ 34249d6048SJerome Glisse #define _DRM_MM_H_ 35249d6048SJerome Glisse 36249d6048SJerome Glisse /* 37249d6048SJerome Glisse * Generic range manager structs 38249d6048SJerome Glisse */ 3986e81f0eSDavid Herrmann #include <linux/bug.h> 4086e81f0eSDavid Herrmann #include <linux/kernel.h> 41249d6048SJerome Glisse #include <linux/list.h> 4286e81f0eSDavid Herrmann #include <linux/spinlock.h> 43f1938cd6SDave Airlie #ifdef CONFIG_DEBUG_FS 44f1938cd6SDave Airlie #include <linux/seq_file.h> 45f1938cd6SDave Airlie #endif 46249d6048SJerome Glisse 4731e5d7c6SDavid Herrmann enum drm_mm_search_flags { 4831e5d7c6SDavid Herrmann DRM_MM_SEARCH_DEFAULT = 0, 4931e5d7c6SDavid Herrmann DRM_MM_SEARCH_BEST = 1 << 0, 5031e5d7c6SDavid Herrmann }; 5131e5d7c6SDavid Herrmann 52249d6048SJerome Glisse struct drm_mm_node { 53d1024ce9SDaniel Vetter struct list_head node_list; 54ea7b1dd4SDaniel Vetter struct list_head hole_stack; 55ea7b1dd4SDaniel Vetter unsigned hole_follows : 1; 56709ea971SDaniel Vetter unsigned scanned_block : 1; 57709ea971SDaniel Vetter unsigned scanned_prev_free : 1; 58709ea971SDaniel Vetter unsigned scanned_next_free : 1; 59ea7b1dd4SDaniel Vetter unsigned scanned_preceeds_hole : 1; 60b0b7af18SDaniel Vetter unsigned allocated : 1; 616b9d89b4SChris Wilson unsigned long color; 62249d6048SJerome Glisse unsigned long start; 63249d6048SJerome Glisse unsigned long size; 64249d6048SJerome Glisse struct drm_mm *mm; 65249d6048SJerome Glisse }; 66249d6048SJerome Glisse 67249d6048SJerome Glisse struct drm_mm { 6825985edcSLucas De Marchi /* List of all memory nodes that immediately precede a free hole. */ 69ea7b1dd4SDaniel Vetter struct list_head hole_stack; 70ea7b1dd4SDaniel Vetter /* head_node.node_list is the list of all memory nodes, ordered 71ea7b1dd4SDaniel Vetter * according to the (increasing) start address of the memory node. */ 72ea7b1dd4SDaniel Vetter struct drm_mm_node head_node; 73249d6048SJerome Glisse struct list_head unused_nodes; 74249d6048SJerome Glisse int num_unused; 75249d6048SJerome Glisse spinlock_t unused_lock; 76d935cc61SDaniel Vetter unsigned int scan_check_range : 1; 77709ea971SDaniel Vetter unsigned scan_alignment; 786b9d89b4SChris Wilson unsigned long scan_color; 79709ea971SDaniel Vetter unsigned long scan_size; 80709ea971SDaniel Vetter unsigned long scan_hit_start; 81901593f2SChris Wilson unsigned long scan_hit_end; 82709ea971SDaniel Vetter unsigned scanned_blocks; 83d935cc61SDaniel Vetter unsigned long scan_start; 84d935cc61SDaniel Vetter unsigned long scan_end; 85ae0cec28SDaniel Vetter struct drm_mm_node *prev_scanned_node; 866b9d89b4SChris Wilson 876b9d89b4SChris Wilson void (*color_adjust)(struct drm_mm_node *node, unsigned long color, 886b9d89b4SChris Wilson unsigned long *start, unsigned long *end); 89249d6048SJerome Glisse }; 90249d6048SJerome Glisse 91b0b7af18SDaniel Vetter static inline bool drm_mm_node_allocated(struct drm_mm_node *node) 92b0b7af18SDaniel Vetter { 93b0b7af18SDaniel Vetter return node->allocated; 94b0b7af18SDaniel Vetter } 95b0b7af18SDaniel Vetter 9631a5b8ceSDaniel Vetter static inline bool drm_mm_initialized(struct drm_mm *mm) 9731a5b8ceSDaniel Vetter { 98ea7b1dd4SDaniel Vetter return mm->hole_stack.next; 9931a5b8ceSDaniel Vetter } 1009e8944abSChris Wilson 1019e8944abSChris Wilson static inline unsigned long __drm_mm_hole_node_start(struct drm_mm_node *hole_node) 1029e8944abSChris Wilson { 1039e8944abSChris Wilson return hole_node->start + hole_node->size; 1049e8944abSChris Wilson } 1059e8944abSChris Wilson 1069e8944abSChris Wilson static inline unsigned long drm_mm_hole_node_start(struct drm_mm_node *hole_node) 1079e8944abSChris Wilson { 1089e8944abSChris Wilson BUG_ON(!hole_node->hole_follows); 1099e8944abSChris Wilson return __drm_mm_hole_node_start(hole_node); 1109e8944abSChris Wilson } 1119e8944abSChris Wilson 1129e8944abSChris Wilson static inline unsigned long __drm_mm_hole_node_end(struct drm_mm_node *hole_node) 1139e8944abSChris Wilson { 1149e8944abSChris Wilson return list_entry(hole_node->node_list.next, 1159e8944abSChris Wilson struct drm_mm_node, node_list)->start; 1169e8944abSChris Wilson } 1179e8944abSChris Wilson 1189e8944abSChris Wilson static inline unsigned long drm_mm_hole_node_end(struct drm_mm_node *hole_node) 1199e8944abSChris Wilson { 1209e8944abSChris Wilson return __drm_mm_hole_node_end(hole_node); 1219e8944abSChris Wilson } 1229e8944abSChris Wilson 123ea7b1dd4SDaniel Vetter #define drm_mm_for_each_node(entry, mm) list_for_each_entry(entry, \ 124ea7b1dd4SDaniel Vetter &(mm)->head_node.node_list, \ 1252bbd4492SDaniel Vetter node_list) 126ae0cec28SDaniel Vetter #define drm_mm_for_each_scanned_node_reverse(entry, n, mm) \ 127ae0cec28SDaniel Vetter for (entry = (mm)->prev_scanned_node, \ 128ae0cec28SDaniel Vetter next = entry ? list_entry(entry->node_list.next, \ 129ae0cec28SDaniel Vetter struct drm_mm_node, node_list) : NULL; \ 130ae0cec28SDaniel Vetter entry != NULL; entry = next, \ 131ae0cec28SDaniel Vetter next = entry ? list_entry(entry->node_list.next, \ 132ae0cec28SDaniel Vetter struct drm_mm_node, node_list) : NULL) \ 1339e8944abSChris Wilson 1349e8944abSChris Wilson /* Note that we need to unroll list_for_each_entry in order to inline 1359e8944abSChris Wilson * setting hole_start and hole_end on each iteration and keep the 1369e8944abSChris Wilson * macro sane. 1379e8944abSChris Wilson */ 1389e8944abSChris Wilson #define drm_mm_for_each_hole(entry, mm, hole_start, hole_end) \ 1399e8944abSChris Wilson for (entry = list_entry((mm)->hole_stack.next, struct drm_mm_node, hole_stack); \ 1409e8944abSChris Wilson &entry->hole_stack != &(mm)->hole_stack ? \ 1419e8944abSChris Wilson hole_start = drm_mm_hole_node_start(entry), \ 1429e8944abSChris Wilson hole_end = drm_mm_hole_node_end(entry), \ 1439e8944abSChris Wilson 1 : 0; \ 1449e8944abSChris Wilson entry = list_entry(entry->hole_stack.next, struct drm_mm_node, hole_stack)) 1459e8944abSChris Wilson 146249d6048SJerome Glisse /* 147249d6048SJerome Glisse * Basic range manager support (drm_mm.c) 148249d6048SJerome Glisse */ 149338710e7SBen Widawsky extern int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node); 15089579f77SThomas Hellstrom extern struct drm_mm_node *drm_mm_get_block_generic(struct drm_mm_node *node, 151249d6048SJerome Glisse unsigned long size, 15289579f77SThomas Hellstrom unsigned alignment, 1536b9d89b4SChris Wilson unsigned long color, 15489579f77SThomas Hellstrom int atomic); 155a2e68e92SJerome Glisse extern struct drm_mm_node *drm_mm_get_block_range_generic( 156a2e68e92SJerome Glisse struct drm_mm_node *node, 157a2e68e92SJerome Glisse unsigned long size, 158a2e68e92SJerome Glisse unsigned alignment, 1596b9d89b4SChris Wilson unsigned long color, 160a2e68e92SJerome Glisse unsigned long start, 161a2e68e92SJerome Glisse unsigned long end, 162a2e68e92SJerome Glisse int atomic); 163b3a070ccSBen Widawsky 16489579f77SThomas Hellstrom static inline struct drm_mm_node *drm_mm_get_block(struct drm_mm_node *parent, 165249d6048SJerome Glisse unsigned long size, 16689579f77SThomas Hellstrom unsigned alignment) 16789579f77SThomas Hellstrom { 1686b9d89b4SChris Wilson return drm_mm_get_block_generic(parent, size, alignment, 0, 0); 16989579f77SThomas Hellstrom } 17089579f77SThomas Hellstrom static inline struct drm_mm_node *drm_mm_get_block_atomic(struct drm_mm_node *parent, 17189579f77SThomas Hellstrom unsigned long size, 17289579f77SThomas Hellstrom unsigned alignment) 17389579f77SThomas Hellstrom { 1746b9d89b4SChris Wilson return drm_mm_get_block_generic(parent, size, alignment, 0, 1); 17589579f77SThomas Hellstrom } 176a2e68e92SJerome Glisse static inline struct drm_mm_node *drm_mm_get_block_range( 177a2e68e92SJerome Glisse struct drm_mm_node *parent, 178a2e68e92SJerome Glisse unsigned long size, 179a2e68e92SJerome Glisse unsigned alignment, 180a2e68e92SJerome Glisse unsigned long start, 181a2e68e92SJerome Glisse unsigned long end) 182a2e68e92SJerome Glisse { 1836b9d89b4SChris Wilson return drm_mm_get_block_range_generic(parent, size, alignment, 0, 1846b9d89b4SChris Wilson start, end, 0); 1856b9d89b4SChris Wilson } 186a2e68e92SJerome Glisse static inline struct drm_mm_node *drm_mm_get_block_atomic_range( 187a2e68e92SJerome Glisse struct drm_mm_node *parent, 188a2e68e92SJerome Glisse unsigned long size, 189a2e68e92SJerome Glisse unsigned alignment, 190a2e68e92SJerome Glisse unsigned long start, 191a2e68e92SJerome Glisse unsigned long end) 192a2e68e92SJerome Glisse { 1936b9d89b4SChris Wilson return drm_mm_get_block_range_generic(parent, size, alignment, 0, 194a2e68e92SJerome Glisse start, end, 1); 195a2e68e92SJerome Glisse } 196b8103450SChris Wilson 197b8103450SChris Wilson extern int drm_mm_insert_node_generic(struct drm_mm *mm, 198b8103450SChris Wilson struct drm_mm_node *node, 199b8103450SChris Wilson unsigned long size, 200b8103450SChris Wilson unsigned alignment, 20131e5d7c6SDavid Herrmann unsigned long color, 20231e5d7c6SDavid Herrmann enum drm_mm_search_flags flags); 20331e5d7c6SDavid Herrmann static inline int drm_mm_insert_node(struct drm_mm *mm, 20431e5d7c6SDavid Herrmann struct drm_mm_node *node, 20531e5d7c6SDavid Herrmann unsigned long size, 20631e5d7c6SDavid Herrmann unsigned alignment, 20731e5d7c6SDavid Herrmann enum drm_mm_search_flags flags) 20831e5d7c6SDavid Herrmann { 20931e5d7c6SDavid Herrmann return drm_mm_insert_node_generic(mm, node, size, alignment, 0, flags); 21031e5d7c6SDavid Herrmann } 21131e5d7c6SDavid Herrmann 212b8103450SChris Wilson extern int drm_mm_insert_node_in_range_generic(struct drm_mm *mm, 213b8103450SChris Wilson struct drm_mm_node *node, 214b8103450SChris Wilson unsigned long size, 215b8103450SChris Wilson unsigned alignment, 216b8103450SChris Wilson unsigned long color, 217b8103450SChris Wilson unsigned long start, 21831e5d7c6SDavid Herrmann unsigned long end, 21931e5d7c6SDavid Herrmann enum drm_mm_search_flags flags); 22031e5d7c6SDavid Herrmann static inline int drm_mm_insert_node_in_range(struct drm_mm *mm, 22131e5d7c6SDavid Herrmann struct drm_mm_node *node, 22231e5d7c6SDavid Herrmann unsigned long size, 22331e5d7c6SDavid Herrmann unsigned alignment, 22431e5d7c6SDavid Herrmann unsigned long start, 22531e5d7c6SDavid Herrmann unsigned long end, 22631e5d7c6SDavid Herrmann enum drm_mm_search_flags flags) 22731e5d7c6SDavid Herrmann { 22831e5d7c6SDavid Herrmann return drm_mm_insert_node_in_range_generic(mm, node, size, alignment, 22931e5d7c6SDavid Herrmann 0, start, end, flags); 23031e5d7c6SDavid Herrmann } 23131e5d7c6SDavid Herrmann 232249d6048SJerome Glisse extern void drm_mm_put_block(struct drm_mm_node *cur); 233b0b7af18SDaniel Vetter extern void drm_mm_remove_node(struct drm_mm_node *node); 234b0b7af18SDaniel Vetter extern void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new); 2356b9d89b4SChris Wilson extern struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm, 236249d6048SJerome Glisse unsigned long size, 237249d6048SJerome Glisse unsigned alignment, 2386b9d89b4SChris Wilson unsigned long color, 23931e5d7c6SDavid Herrmann enum drm_mm_search_flags flags); 2406b9d89b4SChris Wilson extern struct drm_mm_node *drm_mm_search_free_in_range_generic( 2416b9d89b4SChris Wilson const struct drm_mm *mm, 2426b9d89b4SChris Wilson unsigned long size, 2436b9d89b4SChris Wilson unsigned alignment, 2446b9d89b4SChris Wilson unsigned long color, 2456b9d89b4SChris Wilson unsigned long start, 2466b9d89b4SChris Wilson unsigned long end, 24731e5d7c6SDavid Herrmann enum drm_mm_search_flags flags); 2486b9d89b4SChris Wilson static inline struct drm_mm_node *drm_mm_search_free(const struct drm_mm *mm, 2496b9d89b4SChris Wilson unsigned long size, 2506b9d89b4SChris Wilson unsigned alignment, 25131e5d7c6SDavid Herrmann enum drm_mm_search_flags flags) 2526b9d89b4SChris Wilson { 25331e5d7c6SDavid Herrmann return drm_mm_search_free_generic(mm,size, alignment, 0, flags); 2546b9d89b4SChris Wilson } 2556b9d89b4SChris Wilson static inline struct drm_mm_node *drm_mm_search_free_in_range( 256a2e68e92SJerome Glisse const struct drm_mm *mm, 257a2e68e92SJerome Glisse unsigned long size, 258a2e68e92SJerome Glisse unsigned alignment, 259a2e68e92SJerome Glisse unsigned long start, 260a2e68e92SJerome Glisse unsigned long end, 26131e5d7c6SDavid Herrmann enum drm_mm_search_flags flags) 2626b9d89b4SChris Wilson { 2636b9d89b4SChris Wilson return drm_mm_search_free_in_range_generic(mm, size, alignment, 0, 26431e5d7c6SDavid Herrmann start, end, flags); 2656b9d89b4SChris Wilson } 26669163ea8SDaniel Vetter 26777ef8bbcSDavid Herrmann extern void drm_mm_init(struct drm_mm *mm, 2686b9d89b4SChris Wilson unsigned long start, 269249d6048SJerome Glisse unsigned long size); 270249d6048SJerome Glisse extern void drm_mm_takedown(struct drm_mm *mm); 271249d6048SJerome Glisse extern int drm_mm_clean(struct drm_mm *mm); 272249d6048SJerome Glisse extern int drm_mm_pre_get(struct drm_mm *mm); 273249d6048SJerome Glisse 274249d6048SJerome Glisse static inline struct drm_mm *drm_get_mm(struct drm_mm_node *block) 275249d6048SJerome Glisse { 276249d6048SJerome Glisse return block->mm; 277249d6048SJerome Glisse } 278249d6048SJerome Glisse 2796b9d89b4SChris Wilson void drm_mm_init_scan(struct drm_mm *mm, 2806b9d89b4SChris Wilson unsigned long size, 281d935cc61SDaniel Vetter unsigned alignment, 2826b9d89b4SChris Wilson unsigned long color); 2836b9d89b4SChris Wilson void drm_mm_init_scan_with_range(struct drm_mm *mm, 2846b9d89b4SChris Wilson unsigned long size, 2856b9d89b4SChris Wilson unsigned alignment, 2866b9d89b4SChris Wilson unsigned long color, 287d935cc61SDaniel Vetter unsigned long start, 288d935cc61SDaniel Vetter unsigned long end); 289709ea971SDaniel Vetter int drm_mm_scan_add_block(struct drm_mm_node *node); 290709ea971SDaniel Vetter int drm_mm_scan_remove_block(struct drm_mm_node *node); 291709ea971SDaniel Vetter 29299d7e48eSJerome Glisse extern void drm_mm_debug_table(struct drm_mm *mm, const char *prefix); 293fa8a1238SDave Airlie #ifdef CONFIG_DEBUG_FS 294fa8a1238SDave Airlie int drm_mm_dump_table(struct seq_file *m, struct drm_mm *mm); 295fa8a1238SDave Airlie #endif 296fa8a1238SDave Airlie 297249d6048SJerome Glisse #endif 298