Rev 1963 | Rev 3192 | Go to most recent revision | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 1963 | Rev 3031 | ||
---|---|---|---|
Line 39... | Line 39... | ||
39 | * |
39 | * |
40 | * Authors: |
40 | * Authors: |
41 | * Thomas Hellström |
41 | * Thomas Hellström |
42 | */ |
42 | */ |
Line 43... | Line 43... | ||
43 | 43 | ||
44 | #include "drmP.h" |
44 | #include |
45 | #include "drm_mm.h" |
45 | #include |
46 | #include |
46 | #include |
- | 47 | #include |
|
Line 47... | Line 48... | ||
47 | #include |
48 | #include |
Line 48... | Line 49... | ||
48 | 49 | ||
49 | #define MM_UNUSED_TARGET 4 |
50 | #define MM_UNUSED_TARGET 4 |
Line 115... | Line 116... | ||
115 | return next_node->start; |
116 | return next_node->start; |
116 | } |
117 | } |
Line 117... | Line 118... | ||
117 | 118 | ||
118 | static void drm_mm_insert_helper(struct drm_mm_node *hole_node, |
119 | static void drm_mm_insert_helper(struct drm_mm_node *hole_node, |
119 | struct drm_mm_node *node, |
120 | struct drm_mm_node *node, |
- | 121 | unsigned long size, unsigned alignment, |
|
120 | unsigned long size, unsigned alignment) |
122 | unsigned long color) |
121 | { |
123 | { |
122 | struct drm_mm *mm = hole_node->mm; |
- | |
123 | unsigned long tmp = 0, wasted = 0; |
124 | struct drm_mm *mm = hole_node->mm; |
124 | unsigned long hole_start = drm_mm_hole_node_start(hole_node); |
125 | unsigned long hole_start = drm_mm_hole_node_start(hole_node); |
- | 126 | unsigned long hole_end = drm_mm_hole_node_end(hole_node); |
|
- | 127 | unsigned long adj_start = hole_start; |
|
Line 125... | Line 128... | ||
125 | unsigned long hole_end = drm_mm_hole_node_end(hole_node); |
128 | unsigned long adj_end = hole_end; |
Line -... | Line 129... | ||
- | 129 | ||
- | 130 | BUG_ON(!hole_node->hole_follows || node->allocated); |
|
- | 131 | ||
126 | 132 | if (mm->color_adjust) |
|
127 | BUG_ON(!hole_node->hole_follows || node->allocated); |
133 | mm->color_adjust(hole_node, color, &adj_start, &adj_end); |
- | 134 | ||
- | 135 | if (alignment) { |
|
- | 136 | unsigned tmp = adj_start % alignment; |
|
Line 128... | Line 137... | ||
128 | 137 | if (tmp) |
|
129 | if (alignment) |
138 | adj_start += alignment - tmp; |
130 | tmp = hole_start % alignment; |
139 | } |
131 | 140 | ||
132 | if (!tmp) { |
- | |
Line 133... | Line 141... | ||
133 | hole_node->hole_follows = 0; |
141 | if (adj_start == hole_start) { |
134 | list_del_init(&hole_node->hole_stack); |
142 | hole_node->hole_follows = 0; |
135 | } else |
143 | list_del(&hole_node->hole_stack); |
- | 144 | } |
|
136 | wasted = alignment - tmp; |
145 | |
Line 137... | Line 146... | ||
137 | 146 | node->start = adj_start; |
|
138 | node->start = hole_start + wasted; |
147 | node->size = size; |
Line 139... | Line 148... | ||
139 | node->size = size; |
148 | node->mm = mm; |
Line -... | Line 149... | ||
- | 149 | node->color = color; |
|
140 | node->mm = mm; |
150 | node->allocated = 1; |
141 | node->allocated = 1; |
151 | |
142 | 152 | INIT_LIST_HEAD(&node->hole_stack); |
|
143 | INIT_LIST_HEAD(&node->hole_stack); |
- | |
144 | list_add(&node->node_list, &hole_node->node_list); |
- | |
145 | 153 | list_add(&node->node_list, &hole_node->node_list); |
|
146 | BUG_ON(node->start + node->size > hole_end); |
154 | |
Line 147... | Line 155... | ||
147 | 155 | BUG_ON(node->start + node->size > adj_end); |
|
148 | if (node->start + node->size < hole_end) { |
156 | |
149 | list_add(&node->hole_stack, &mm->hole_stack); |
157 | node->hole_follows = 0; |
- | 158 | if (node->start + node->size < hole_end) { |
|
150 | node->hole_follows = 1; |
159 | list_add(&node->hole_stack, &mm->hole_stack); |
151 | } else { |
160 | node->hole_follows = 1; |
152 | node->hole_follows = 0; |
161 | } |
Line 153... | Line 162... | ||
153 | } |
162 | } |
154 | } |
163 | |
155 | 164 | struct drm_mm_node *drm_mm_get_block_generic(struct drm_mm_node *hole_node, |
|
Line 156... | Line 165... | ||
156 | struct drm_mm_node *drm_mm_get_block_generic(struct drm_mm_node *hole_node, |
165 | unsigned long size, |
Line 157... | Line 166... | ||
157 | unsigned long size, |
166 | unsigned alignment, |
158 | unsigned alignment, |
167 | unsigned long color, |
159 | int atomic) |
168 | int atomic) |
Line 178... | Line 187... | ||
178 | int drm_mm_insert_node(struct drm_mm *mm, struct drm_mm_node *node, |
187 | int drm_mm_insert_node(struct drm_mm *mm, struct drm_mm_node *node, |
179 | unsigned long size, unsigned alignment) |
188 | unsigned long size, unsigned alignment) |
180 | { |
189 | { |
181 | struct drm_mm_node *hole_node; |
190 | struct drm_mm_node *hole_node; |
Line 182... | Line 191... | ||
182 | 191 | ||
183 | hole_node = drm_mm_search_free(mm, size, alignment, 0); |
192 | hole_node = drm_mm_search_free(mm, size, alignment, false); |
184 | if (!hole_node) |
193 | if (!hole_node) |
Line 185... | Line 194... | ||
185 | return -ENOSPC; |
194 | return -ENOSPC; |
Line 186... | Line 195... | ||
186 | 195 | ||
187 | drm_mm_insert_helper(hole_node, node, size, alignment); |
196 | drm_mm_insert_helper(hole_node, node, size, alignment, 0); |
188 | 197 | ||
Line 189... | Line 198... | ||
189 | return 0; |
198 | return 0; |
190 | } |
199 | } |
191 | EXPORT_SYMBOL(drm_mm_insert_node); |
200 | EXPORT_SYMBOL(drm_mm_insert_node); |
- | 201 | ||
192 | 202 | static void drm_mm_insert_helper_range(struct drm_mm_node *hole_node, |
|
193 | static void drm_mm_insert_helper_range(struct drm_mm_node *hole_node, |
203 | struct drm_mm_node *node, |
194 | struct drm_mm_node *node, |
204 | unsigned long size, unsigned alignment, |
195 | unsigned long size, unsigned alignment, |
- | |
196 | unsigned long start, unsigned long end) |
205 | unsigned long color, |
197 | { |
206 | unsigned long start, unsigned long end) |
- | 207 | { |
|
- | 208 | struct drm_mm *mm = hole_node->mm; |
|
Line 198... | Line 209... | ||
198 | struct drm_mm *mm = hole_node->mm; |
209 | unsigned long hole_start = drm_mm_hole_node_start(hole_node); |
Line 199... | Line 210... | ||
199 | unsigned long tmp = 0, wasted = 0; |
210 | unsigned long hole_end = drm_mm_hole_node_end(hole_node); |
200 | unsigned long hole_start = drm_mm_hole_node_start(hole_node); |
- | |
201 | unsigned long hole_end = drm_mm_hole_node_end(hole_node); |
- | |
202 | 211 | unsigned long adj_start = hole_start; |
|
Line -... | Line 212... | ||
- | 212 | unsigned long adj_end = hole_end; |
|
- | 213 | ||
- | 214 | BUG_ON(!hole_node->hole_follows || node->allocated); |
|
- | 215 | ||
- | 216 | if (mm->color_adjust) |
|
203 | BUG_ON(!hole_node->hole_follows || node->allocated); |
217 | mm->color_adjust(hole_node, color, &adj_start, &adj_end); |
204 | 218 | ||
- | 219 | if (adj_start < start) |
|
Line 205... | Line 220... | ||
205 | if (hole_start < start) |
220 | adj_start = start; |
206 | wasted += start - hole_start; |
221 | |
207 | if (alignment) |
222 | if (alignment) { |
208 | tmp = (hole_start + wasted) % alignment; |
223 | unsigned tmp = adj_start % alignment; |
Line 209... | Line 224... | ||
209 | 224 | if (tmp) |
|
210 | if (tmp) |
225 | adj_start += alignment - tmp; |
211 | wasted += alignment - tmp; |
226 | } |
- | 227 | ||
212 | 228 | if (adj_start == hole_start) { |
|
Line 213... | Line 229... | ||
213 | if (!wasted) { |
229 | hole_node->hole_follows = 0; |
214 | hole_node->hole_follows = 0; |
230 | list_del(&hole_node->hole_stack); |
Line 215... | Line 231... | ||
215 | list_del_init(&hole_node->hole_stack); |
231 | } |
216 | } |
232 | |
Line -... | Line 233... | ||
- | 233 | node->start = adj_start; |
|
217 | 234 | node->size = size; |
|
218 | node->start = hole_start + wasted; |
235 | node->mm = mm; |
219 | node->size = size; |
236 | node->color = color; |
220 | node->mm = mm; |
- | |
221 | node->allocated = 1; |
- | |
222 | 237 | node->allocated = 1; |
|
223 | INIT_LIST_HEAD(&node->hole_stack); |
238 | |
Line 224... | Line 239... | ||
224 | list_add(&node->node_list, &hole_node->node_list); |
239 | INIT_LIST_HEAD(&node->hole_stack); |
225 | 240 | list_add(&node->node_list, &hole_node->node_list); |
|
226 | BUG_ON(node->start + node->size > hole_end); |
241 | |
- | 242 | BUG_ON(node->start + node->size > adj_end); |
|
227 | BUG_ON(node->start + node->size > end); |
243 | BUG_ON(node->start + node->size > end); |
228 | 244 | ||
229 | if (node->start + node->size < hole_end) { |
245 | node->hole_follows = 0; |
230 | list_add(&node->hole_stack, &mm->hole_stack); |
246 | if (node->start + node->size < hole_end) { |
231 | node->hole_follows = 1; |
247 | list_add(&node->hole_stack, &mm->hole_stack); |
Line 232... | Line 248... | ||
232 | } else { |
248 | node->hole_follows = 1; |
233 | node->hole_follows = 0; |
249 | } |
234 | } |
250 | } |
Line 235... | Line 251... | ||
235 | } |
251 | |
236 | 252 | struct drm_mm_node *drm_mm_get_block_range_generic(struct drm_mm_node *hole_node, |
|
Line 237... | Line 253... | ||
237 | struct drm_mm_node *drm_mm_get_block_range_generic(struct drm_mm_node *hole_node, |
253 | unsigned long size, |
238 | unsigned long size, |
254 | unsigned alignment, |
239 | unsigned alignment, |
255 | unsigned long color, |
Line 264... | Line 280... | ||
264 | unsigned long start, unsigned long end) |
280 | unsigned long start, unsigned long end) |
265 | { |
281 | { |
266 | struct drm_mm_node *hole_node; |
282 | struct drm_mm_node *hole_node; |
Line 267... | Line 283... | ||
267 | 283 | ||
268 | hole_node = drm_mm_search_free_in_range(mm, size, alignment, |
284 | hole_node = drm_mm_search_free_in_range(mm, size, alignment, |
269 | start, end, 0); |
285 | start, end, false); |
270 | if (!hole_node) |
286 | if (!hole_node) |
Line 271... | Line 287... | ||
271 | return -ENOSPC; |
287 | return -ENOSPC; |
272 | 288 | ||
Line 273... | Line 289... | ||
273 | drm_mm_insert_helper_range(hole_node, node, size, alignment, |
289 | drm_mm_insert_helper_range(hole_node, node, size, alignment, 0, |
274 | start, end); |
290 | start, end); |
275 | 291 | ||
Line 333... | Line 349... | ||
333 | EXPORT_SYMBOL(drm_mm_put_block); |
349 | EXPORT_SYMBOL(drm_mm_put_block); |
Line 334... | Line 350... | ||
334 | 350 | ||
335 | static int check_free_hole(unsigned long start, unsigned long end, |
351 | static int check_free_hole(unsigned long start, unsigned long end, |
336 | unsigned long size, unsigned alignment) |
352 | unsigned long size, unsigned alignment) |
337 | { |
- | |
338 | unsigned wasted = 0; |
- | |
339 | 353 | { |
|
340 | if (end - start < size) |
354 | if (end - start < size) |
Line 341... | Line 355... | ||
341 | return 0; |
355 | return 0; |
342 | 356 | ||
343 | if (alignment) { |
357 | if (alignment) { |
344 | unsigned tmp = start % alignment; |
358 | unsigned tmp = start % alignment; |
345 | if (tmp) |
359 | if (tmp) |
Line 346... | Line 360... | ||
346 | wasted = alignment - tmp; |
360 | start += alignment - tmp; |
347 | } |
- | |
348 | - | ||
349 | if (end >= start + size + wasted) { |
- | |
350 | return 1; |
- | |
351 | } |
361 | } |
Line 352... | Line 362... | ||
352 | 362 | ||
353 | return 0; |
363 | return end >= start + size; |
354 | } |
364 | } |
- | 365 | ||
- | 366 | struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm, |
|
355 | 367 | unsigned long size, |
|
356 | struct drm_mm_node *drm_mm_search_free(const struct drm_mm *mm, |
368 | unsigned alignment, |
357 | unsigned long size, |
369 | unsigned long color, |
358 | unsigned alignment, int best_match) |
370 | bool best_match) |
Line 365... | Line 377... | ||
365 | 377 | ||
366 | best = NULL; |
378 | best = NULL; |
Line 367... | Line 379... | ||
367 | best_size = ~0UL; |
379 | best_size = ~0UL; |
- | 380 | ||
- | 381 | list_for_each_entry(entry, &mm->hole_stack, hole_stack) { |
|
- | 382 | unsigned long adj_start = drm_mm_hole_node_start(entry); |
|
- | 383 | unsigned long adj_end = drm_mm_hole_node_end(entry); |
|
- | 384 | ||
- | 385 | if (mm->color_adjust) { |
|
- | 386 | mm->color_adjust(entry, color, &adj_start, &adj_end); |
|
- | 387 | if (adj_end <= adj_start) |
|
- | 388 | continue; |
|
368 | 389 | } |
|
369 | list_for_each_entry(entry, &mm->hole_stack, hole_stack) { |
390 | |
370 | BUG_ON(!entry->hole_follows); |
- | |
371 | if (!check_free_hole(drm_mm_hole_node_start(entry), |
- | |
372 | drm_mm_hole_node_end(entry), |
391 | BUG_ON(!entry->hole_follows); |
Line 373... | Line 392... | ||
373 | size, alignment)) |
392 | if (!check_free_hole(adj_start, adj_end, size, alignment)) |
374 | continue; |
393 | continue; |
Line 382... | Line 401... | ||
382 | } |
401 | } |
383 | } |
402 | } |
Line 384... | Line 403... | ||
384 | 403 | ||
385 | return best; |
404 | return best; |
386 | } |
405 | } |
Line 387... | Line 406... | ||
387 | EXPORT_SYMBOL(drm_mm_search_free); |
406 | EXPORT_SYMBOL(drm_mm_search_free_generic); |
388 | 407 | ||
389 | struct drm_mm_node *drm_mm_search_free_in_range(const struct drm_mm *mm, |
408 | struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_mm *mm, |
- | 409 | unsigned long size, |
|
390 | unsigned long size, |
410 | unsigned alignment, |
391 | unsigned alignment, |
411 | unsigned long color, |
392 | unsigned long start, |
412 | unsigned long start, |
393 | unsigned long end, |
413 | unsigned long end, |
394 | int best_match) |
414 | bool best_match) |
395 | { |
415 | { |
396 | struct drm_mm_node *entry; |
416 | struct drm_mm_node *entry; |
Line 407... | Line 427... | ||
407 | start : drm_mm_hole_node_start(entry); |
427 | start : drm_mm_hole_node_start(entry); |
408 | unsigned long adj_end = drm_mm_hole_node_end(entry) > end ? |
428 | unsigned long adj_end = drm_mm_hole_node_end(entry) > end ? |
409 | end : drm_mm_hole_node_end(entry); |
429 | end : drm_mm_hole_node_end(entry); |
Line 410... | Line 430... | ||
410 | 430 | ||
- | 431 | BUG_ON(!entry->hole_follows); |
|
- | 432 | ||
- | 433 | if (mm->color_adjust) { |
|
- | 434 | mm->color_adjust(entry, color, &adj_start, &adj_end); |
|
- | 435 | if (adj_end <= adj_start) |
|
- | 436 | continue; |
|
- | 437 | } |
|
411 | BUG_ON(!entry->hole_follows); |
438 | |
412 | if (!check_free_hole(adj_start, adj_end, size, alignment)) |
439 | if (!check_free_hole(adj_start, adj_end, size, alignment)) |
Line 413... | Line 440... | ||
413 | continue; |
440 | continue; |
414 | 441 | ||
Line 421... | Line 448... | ||
421 | } |
448 | } |
422 | } |
449 | } |
Line 423... | Line 450... | ||
423 | 450 | ||
424 | return best; |
451 | return best; |
425 | } |
452 | } |
Line 426... | Line 453... | ||
426 | EXPORT_SYMBOL(drm_mm_search_free_in_range); |
453 | EXPORT_SYMBOL(drm_mm_search_free_in_range_generic); |
427 | 454 | ||
428 | /** |
455 | /** |
429 | * Moves an allocation. To be used with embedded struct drm_mm_node. |
456 | * Moves an allocation. To be used with embedded struct drm_mm_node. |
Line 434... | Line 461... | ||
434 | list_replace(&old->hole_stack, &new->hole_stack); |
461 | list_replace(&old->hole_stack, &new->hole_stack); |
435 | new->hole_follows = old->hole_follows; |
462 | new->hole_follows = old->hole_follows; |
436 | new->mm = old->mm; |
463 | new->mm = old->mm; |
437 | new->start = old->start; |
464 | new->start = old->start; |
438 | new->size = old->size; |
465 | new->size = old->size; |
- | 466 | new->color = old->color; |
|
Line 439... | Line 467... | ||
439 | 467 | ||
440 | old->allocated = 0; |
468 | old->allocated = 0; |
441 | new->allocated = 1; |
469 | new->allocated = 1; |
442 | } |
470 | } |
Line 449... | Line 477... | ||
449 | * hole. |
477 | * hole. |
450 | * |
478 | * |
451 | * Warning: As long as the scan list is non-empty, no other operations than |
479 | * Warning: As long as the scan list is non-empty, no other operations than |
452 | * adding/removing nodes to/from the scan list are allowed. |
480 | * adding/removing nodes to/from the scan list are allowed. |
453 | */ |
481 | */ |
454 | void drm_mm_init_scan(struct drm_mm *mm, unsigned long size, |
482 | void drm_mm_init_scan(struct drm_mm *mm, |
- | 483 | unsigned long size, |
|
455 | unsigned alignment) |
484 | unsigned alignment, |
- | 485 | unsigned long color) |
|
456 | { |
486 | { |
- | 487 | mm->scan_color = color; |
|
457 | mm->scan_alignment = alignment; |
488 | mm->scan_alignment = alignment; |
458 | mm->scan_size = size; |
489 | mm->scan_size = size; |
459 | mm->scanned_blocks = 0; |
490 | mm->scanned_blocks = 0; |
460 | mm->scan_hit_start = 0; |
491 | mm->scan_hit_start = 0; |
461 | mm->scan_hit_size = 0; |
492 | mm->scan_hit_size = 0; |
Line 471... | Line 502... | ||
471 | * hole. This version is for range-restricted scans. |
502 | * hole. This version is for range-restricted scans. |
472 | * |
503 | * |
473 | * Warning: As long as the scan list is non-empty, no other operations than |
504 | * Warning: As long as the scan list is non-empty, no other operations than |
474 | * adding/removing nodes to/from the scan list are allowed. |
505 | * adding/removing nodes to/from the scan list are allowed. |
475 | */ |
506 | */ |
476 | void drm_mm_init_scan_with_range(struct drm_mm *mm, unsigned long size, |
507 | void drm_mm_init_scan_with_range(struct drm_mm *mm, |
- | 508 | unsigned long size, |
|
477 | unsigned alignment, |
509 | unsigned alignment, |
- | 510 | unsigned long color, |
|
478 | unsigned long start, |
511 | unsigned long start, |
479 | unsigned long end) |
512 | unsigned long end) |
480 | { |
513 | { |
- | 514 | mm->scan_color = color; |
|
481 | mm->scan_alignment = alignment; |
515 | mm->scan_alignment = alignment; |
482 | mm->scan_size = size; |
516 | mm->scan_size = size; |
483 | mm->scanned_blocks = 0; |
517 | mm->scanned_blocks = 0; |
484 | mm->scan_hit_start = 0; |
518 | mm->scan_hit_start = 0; |
485 | mm->scan_hit_size = 0; |
519 | mm->scan_hit_size = 0; |
Line 519... | Line 553... | ||
519 | node->node_list.next = &mm->prev_scanned_node->node_list; |
553 | node->node_list.next = &mm->prev_scanned_node->node_list; |
520 | mm->prev_scanned_node = node; |
554 | mm->prev_scanned_node = node; |
Line 521... | Line 555... | ||
521 | 555 | ||
522 | hole_start = drm_mm_hole_node_start(prev_node); |
556 | hole_start = drm_mm_hole_node_start(prev_node); |
523 | hole_end = drm_mm_hole_node_end(prev_node); |
- | |
524 | if (mm->scan_check_range) { |
- | |
525 | adj_start = hole_start < mm->scan_start ? |
- | |
526 | mm->scan_start : hole_start; |
- | |
527 | adj_end = hole_end > mm->scan_end ? |
- | |
528 | mm->scan_end : hole_end; |
557 | hole_end = drm_mm_hole_node_end(prev_node); |
529 | } else { |
558 | |
530 | adj_start = hole_start; |
559 | adj_start = hole_start; |
- | 560 | adj_end = hole_end; |
|
- | 561 | ||
- | 562 | if (mm->color_adjust) |
|
- | 563 | mm->color_adjust(prev_node, mm->scan_color, &adj_start, &adj_end); |
|
- | 564 | ||
- | 565 | if (mm->scan_check_range) { |
|
- | 566 | if (adj_start < mm->scan_start) |
|
- | 567 | adj_start = mm->scan_start; |
|
- | 568 | if (adj_end > mm->scan_end) |
|
531 | adj_end = hole_end; |
569 | adj_end = mm->scan_end; |
Line 532... | Line 570... | ||
532 | } |
570 | } |
533 | 571 | ||
534 | if (check_free_hole(adj_start , adj_end, |
572 | if (check_free_hole(adj_start, adj_end, |
Line 613... | Line 651... | ||
613 | mm->head_node.mm = mm; |
651 | mm->head_node.mm = mm; |
614 | mm->head_node.start = start + size; |
652 | mm->head_node.start = start + size; |
615 | mm->head_node.size = start - mm->head_node.start; |
653 | mm->head_node.size = start - mm->head_node.start; |
616 | list_add_tail(&mm->head_node.hole_stack, &mm->hole_stack); |
654 | list_add_tail(&mm->head_node.hole_stack, &mm->hole_stack); |
Line -... | Line 655... | ||
- | 655 | ||
- | 656 | mm->color_adjust = NULL; |
|
617 | 657 | ||
618 | return 0; |
658 | return 0; |
619 | } |
659 | } |
Line 620... | Line 660... | ||
620 | EXPORT_SYMBOL(drm_mm_init); |
660 | EXPORT_SYMBOL(drm_mm_init); |