Line data Source code
1 : /**************************************************************************
2 : *
3 : * Copyright 2006-2008 Tungsten Graphics, Inc., Cedar Park, TX. 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 : * Authors:
30 : * Thomas Hellstrom <thomas-at-tungstengraphics-dot-com>
31 : */
32 :
33 : #ifndef _DRM_MM_H_
34 : #define _DRM_MM_H_
35 :
36 : /*
37 : * Generic range manager structs
38 : */
39 : #ifdef __linux__
40 : #include <linux/bug.h>
41 : #include <linux/kernel.h>
42 : #include <linux/list.h>
43 : #include <linux/spinlock.h>
44 : #else
45 : #include <dev/pci/drm/drm_linux_list.h>
46 : #endif
47 : #ifdef CONFIG_DEBUG_FS
48 : #include <linux/seq_file.h>
49 : #endif
50 :
51 : enum drm_mm_search_flags {
52 : DRM_MM_SEARCH_DEFAULT = 0,
53 : DRM_MM_SEARCH_BEST = 1 << 0,
54 : DRM_MM_SEARCH_BELOW = 1 << 1,
55 : };
56 :
57 : enum drm_mm_allocator_flags {
58 : DRM_MM_CREATE_DEFAULT = 0,
59 : DRM_MM_CREATE_TOP = 1 << 0,
60 : };
61 :
62 : #define DRM_MM_BOTTOMUP DRM_MM_SEARCH_DEFAULT, DRM_MM_CREATE_DEFAULT
63 : #define DRM_MM_TOPDOWN DRM_MM_SEARCH_BELOW, DRM_MM_CREATE_TOP
64 :
65 : struct drm_mm_node {
66 : struct list_head node_list;
67 : struct list_head hole_stack;
68 : unsigned hole_follows : 1;
69 : unsigned scanned_block : 1;
70 : unsigned scanned_prev_free : 1;
71 : unsigned scanned_next_free : 1;
72 : unsigned scanned_preceeds_hole : 1;
73 : unsigned allocated : 1;
74 : unsigned long color;
75 : u64 start;
76 : u64 size;
77 : struct drm_mm *mm;
78 : };
79 :
80 : struct drm_mm {
81 : /* List of all memory nodes that immediately precede a free hole. */
82 : struct list_head hole_stack;
83 : /* head_node.node_list is the list of all memory nodes, ordered
84 : * according to the (increasing) start address of the memory node. */
85 : struct drm_mm_node head_node;
86 : unsigned int scan_check_range : 1;
87 : unsigned scan_alignment;
88 : unsigned long scan_color;
89 : u64 scan_size;
90 : u64 scan_hit_start;
91 : u64 scan_hit_end;
92 : unsigned scanned_blocks;
93 : u64 scan_start;
94 : u64 scan_end;
95 : struct drm_mm_node *prev_scanned_node;
96 :
97 : void (*color_adjust)(struct drm_mm_node *node, unsigned long color,
98 : u64 *start, u64 *end);
99 : };
100 :
101 : /**
102 : * drm_mm_node_allocated - checks whether a node is allocated
103 : * @node: drm_mm_node to check
104 : *
105 : * Drivers should use this helpers for proper encapusulation of drm_mm
106 : * internals.
107 : *
108 : * Returns:
109 : * True if the @node is allocated.
110 : */
111 0 : static inline bool drm_mm_node_allocated(struct drm_mm_node *node)
112 : {
113 0 : return node->allocated;
114 : }
115 :
116 : /**
117 : * drm_mm_initialized - checks whether an allocator is initialized
118 : * @mm: drm_mm to check
119 : *
120 : * Drivers should use this helpers for proper encapusulation of drm_mm
121 : * internals.
122 : *
123 : * Returns:
124 : * True if the @mm is initialized.
125 : */
126 0 : static inline bool drm_mm_initialized(struct drm_mm *mm)
127 : {
128 0 : return mm->hole_stack.next;
129 : }
130 :
131 0 : static inline u64 __drm_mm_hole_node_start(struct drm_mm_node *hole_node)
132 : {
133 0 : return hole_node->start + hole_node->size;
134 : }
135 :
136 : /**
137 : * drm_mm_hole_node_start - computes the start of the hole following @node
138 : * @hole_node: drm_mm_node which implicitly tracks the following hole
139 : *
140 : * This is useful for driver-sepific debug dumpers. Otherwise drivers should not
141 : * inspect holes themselves. Drivers must check first whether a hole indeed
142 : * follows by looking at node->hole_follows.
143 : *
144 : * Returns:
145 : * Start of the subsequent hole.
146 : */
147 0 : static inline u64 drm_mm_hole_node_start(struct drm_mm_node *hole_node)
148 : {
149 0 : BUG_ON(!hole_node->hole_follows);
150 0 : return __drm_mm_hole_node_start(hole_node);
151 : }
152 :
153 0 : static inline u64 __drm_mm_hole_node_end(struct drm_mm_node *hole_node)
154 : {
155 0 : return list_next_entry(hole_node, node_list)->start;
156 : }
157 :
158 : /**
159 : * drm_mm_hole_node_end - computes the end of the hole following @node
160 : * @hole_node: drm_mm_node which implicitly tracks the following hole
161 : *
162 : * This is useful for driver-sepific debug dumpers. Otherwise drivers should not
163 : * inspect holes themselves. Drivers must check first whether a hole indeed
164 : * follows by looking at node->hole_follows.
165 : *
166 : * Returns:
167 : * End of the subsequent hole.
168 : */
169 0 : static inline u64 drm_mm_hole_node_end(struct drm_mm_node *hole_node)
170 : {
171 0 : return __drm_mm_hole_node_end(hole_node);
172 : }
173 :
174 : /**
175 : * drm_mm_for_each_node - iterator to walk over all allocated nodes
176 : * @entry: drm_mm_node structure to assign to in each iteration step
177 : * @mm: drm_mm allocator to walk
178 : *
179 : * This iterator walks over all nodes in the range allocator. It is implemented
180 : * with list_for_each, so not save against removal of elements.
181 : */
182 : #define drm_mm_for_each_node(entry, mm) list_for_each_entry(entry, \
183 : &(mm)->head_node.node_list, \
184 : node_list)
185 :
186 : #define __drm_mm_for_each_hole(entry, mm, hole_start, hole_end, backwards) \
187 : for (entry = list_entry((backwards) ? (mm)->hole_stack.prev : (mm)->hole_stack.next, struct drm_mm_node, hole_stack); \
188 : &entry->hole_stack != &(mm)->hole_stack ? \
189 : hole_start = drm_mm_hole_node_start(entry), \
190 : hole_end = drm_mm_hole_node_end(entry), \
191 : 1 : 0; \
192 : entry = list_entry((backwards) ? entry->hole_stack.prev : entry->hole_stack.next, struct drm_mm_node, hole_stack))
193 :
194 : /**
195 : * drm_mm_for_each_hole - iterator to walk over all holes
196 : * @entry: drm_mm_node used internally to track progress
197 : * @mm: drm_mm allocator to walk
198 : * @hole_start: ulong variable to assign the hole start to on each iteration
199 : * @hole_end: ulong variable to assign the hole end to on each iteration
200 : *
201 : * This iterator walks over all holes in the range allocator. It is implemented
202 : * with list_for_each, so not save against removal of elements. @entry is used
203 : * internally and will not reflect a real drm_mm_node for the very first hole.
204 : * Hence users of this iterator may not access it.
205 : *
206 : * Implementation Note:
207 : * We need to inline list_for_each_entry in order to be able to set hole_start
208 : * and hole_end on each iteration while keeping the macro sane.
209 : *
210 : * The __drm_mm_for_each_hole version is similar, but with added support for
211 : * going backwards.
212 : */
213 : #define drm_mm_for_each_hole(entry, mm, hole_start, hole_end) \
214 : __drm_mm_for_each_hole(entry, mm, hole_start, hole_end, 0)
215 :
216 : /*
217 : * Basic range manager support (drm_mm.c)
218 : */
219 : int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node);
220 :
221 : int drm_mm_insert_node_generic(struct drm_mm *mm,
222 : struct drm_mm_node *node,
223 : u64 size,
224 : unsigned alignment,
225 : unsigned long color,
226 : enum drm_mm_search_flags sflags,
227 : enum drm_mm_allocator_flags aflags);
228 : /**
229 : * drm_mm_insert_node - search for space and insert @node
230 : * @mm: drm_mm to allocate from
231 : * @node: preallocate node to insert
232 : * @size: size of the allocation
233 : * @alignment: alignment of the allocation
234 : * @flags: flags to fine-tune the allocation
235 : *
236 : * This is a simplified version of drm_mm_insert_node_generic() with @color set
237 : * to 0.
238 : *
239 : * The preallocated node must be cleared to 0.
240 : *
241 : * Returns:
242 : * 0 on success, -ENOSPC if there's no suitable hole.
243 : */
244 0 : static inline int drm_mm_insert_node(struct drm_mm *mm,
245 : struct drm_mm_node *node,
246 : u64 size,
247 : unsigned alignment,
248 : enum drm_mm_search_flags flags)
249 : {
250 0 : return drm_mm_insert_node_generic(mm, node, size, alignment, 0, flags,
251 : DRM_MM_CREATE_DEFAULT);
252 : }
253 :
254 : int drm_mm_insert_node_in_range_generic(struct drm_mm *mm,
255 : struct drm_mm_node *node,
256 : u64 size,
257 : unsigned alignment,
258 : unsigned long color,
259 : u64 start,
260 : u64 end,
261 : enum drm_mm_search_flags sflags,
262 : enum drm_mm_allocator_flags aflags);
263 : /**
264 : * drm_mm_insert_node_in_range - ranged search for space and insert @node
265 : * @mm: drm_mm to allocate from
266 : * @node: preallocate node to insert
267 : * @size: size of the allocation
268 : * @alignment: alignment of the allocation
269 : * @start: start of the allowed range for this node
270 : * @end: end of the allowed range for this node
271 : * @flags: flags to fine-tune the allocation
272 : *
273 : * This is a simplified version of drm_mm_insert_node_in_range_generic() with
274 : * @color set to 0.
275 : *
276 : * The preallocated node must be cleared to 0.
277 : *
278 : * Returns:
279 : * 0 on success, -ENOSPC if there's no suitable hole.
280 : */
281 0 : static inline int drm_mm_insert_node_in_range(struct drm_mm *mm,
282 : struct drm_mm_node *node,
283 : u64 size,
284 : unsigned alignment,
285 : u64 start,
286 : u64 end,
287 : enum drm_mm_search_flags flags)
288 : {
289 0 : return drm_mm_insert_node_in_range_generic(mm, node, size, alignment,
290 : 0, start, end, flags,
291 : DRM_MM_CREATE_DEFAULT);
292 : }
293 :
294 : void drm_mm_remove_node(struct drm_mm_node *node);
295 : void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new);
296 : void drm_mm_init(struct drm_mm *mm,
297 : u64 start,
298 : u64 size);
299 : void drm_mm_takedown(struct drm_mm *mm);
300 : bool drm_mm_clean(struct drm_mm *mm);
301 :
302 : void drm_mm_init_scan(struct drm_mm *mm,
303 : u64 size,
304 : unsigned alignment,
305 : unsigned long color);
306 : void drm_mm_init_scan_with_range(struct drm_mm *mm,
307 : u64 size,
308 : unsigned alignment,
309 : unsigned long color,
310 : u64 start,
311 : u64 end);
312 : bool drm_mm_scan_add_block(struct drm_mm_node *node);
313 : bool drm_mm_scan_remove_block(struct drm_mm_node *node);
314 :
315 : void drm_mm_debug_table(struct drm_mm *mm, const char *prefix);
316 : #ifdef CONFIG_DEBUG_FS
317 : int drm_mm_dump_table(struct seq_file *m, struct drm_mm *mm);
318 : #endif
319 :
320 : #endif
|
