← Back to branch summary

~ubuntu-branches/ubuntu/precise/linux-ti-omap4/precise

« back to all changes in this revision

Viewing changes to drivers/gpu/drm/drm_mm.c

  • Committer: Bazaar Package Importer
  • Author(s): Paolo Pisati
  • Date: 2011-06-29 15:23:51 UTC
  • mfrom: (26.1.1 natty-proposed)
  • Revision ID: james.westby@ubuntu.com-20110629152351-xs96tm303d95rpbk
Tags: 3.0.0-1200.2
* Rebased against 3.0.0-6.7
* BSP from TI based on 3.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
drivers/gpu/drm/drm_mm.c
64
64
                else {
65
65
                        child =
66
66
                            list_entry(mm->unused_nodes.next,
67
 
                                       struct drm_mm_node, free_stack);
68
 
                        list_del(&child->free_stack);
 
67
                                       struct drm_mm_node, node_list);
 
68
                        list_del(&child->node_list);
69
69
                        --mm->num_unused;
70
70
                }
71
71
                spin_unlock(&mm->unused_lock);
94
94
                        return ret;
95
95
                }
96
96
                ++mm->num_unused;
97
 
                list_add_tail(&node->free_stack, &mm->unused_nodes);
 
97
                list_add_tail(&node->node_list, &mm->unused_nodes);
98
98
        }
99
99
        spin_unlock(&mm->unused_lock);
100
100
        return 0;
101
101
}
102
102
EXPORT_SYMBOL(drm_mm_pre_get);
103
103
 
104
 
static int drm_mm_create_tail_node(struct drm_mm *mm,
105
 
                                   unsigned long start,
106
 
                                   unsigned long size, int atomic)
107
 
{
108
 
        struct drm_mm_node *child;
109
 
 
110
 
        child = drm_mm_kmalloc(mm, atomic);
111
 
        if (unlikely(child == NULL))
112
 
                return -ENOMEM;
113
 
 
114
 
        child->free = 1;
115
 
        child->size = size;
116
 
        child->start = start;
117
 
        child->mm = mm;
118
 
 
119
 
        list_add_tail(&child->node_list, &mm->node_list);
120
 
        list_add_tail(&child->free_stack, &mm->free_stack);
121
 
 
122
 
        return 0;
123
 
}
124
 
 
125
 
static struct drm_mm_node *drm_mm_split_at_start(struct drm_mm_node *parent,
126
 
                                                 unsigned long size,
127
 
                                                 int atomic)
128
 
{
129
 
        struct drm_mm_node *child;
130
 
 
131
 
        child = drm_mm_kmalloc(parent->mm, atomic);
132
 
        if (unlikely(child == NULL))
133
 
                return NULL;
134
 
 
135
 
        INIT_LIST_HEAD(&child->free_stack);
136
 
 
137
 
        child->size = size;
138
 
        child->start = parent->start;
139
 
        child->mm = parent->mm;
140
 
 
141
 
        list_add_tail(&child->node_list, &parent->node_list);
142
 
        INIT_LIST_HEAD(&child->free_stack);
143
 
 
144
 
        parent->size -= size;
145
 
        parent->start += size;
146
 
        return child;
147
 
}
148
 
 
149
 
 
150
 
struct drm_mm_node *drm_mm_get_block_generic(struct drm_mm_node *node,
 
104
static inline unsigned long drm_mm_hole_node_start(struct drm_mm_node *hole_node)
 
105
{
 
106
        return hole_node->start + hole_node->size;
 
107
}
 
108
 
 
109
static inline unsigned long drm_mm_hole_node_end(struct drm_mm_node *hole_node)
 
110
{
 
111
        struct drm_mm_node *next_node =
 
112
                list_entry(hole_node->node_list.next, struct drm_mm_node,
 
113
                           node_list);
 
114
 
 
115
        return next_node->start;
 
116
}
 
117
 
 
118
static void drm_mm_insert_helper(struct drm_mm_node *hole_node,
 
119
                                 struct drm_mm_node *node,
 
120
                                 unsigned long size, unsigned alignment)
 
121
{
 
122
        struct drm_mm *mm = hole_node->mm;
 
123
        unsigned long tmp = 0, wasted = 0;
 
124
        unsigned long hole_start = drm_mm_hole_node_start(hole_node);
 
125
        unsigned long hole_end = drm_mm_hole_node_end(hole_node);
 
126
 
 
127
        BUG_ON(!hole_node->hole_follows || node->allocated);
 
128
 
 
129
        if (alignment)
 
130
                tmp = hole_start % alignment;
 
131
 
 
132
        if (!tmp) {
 
133
                hole_node->hole_follows = 0;
 
134
                list_del_init(&hole_node->hole_stack);
 
135
        } else
 
136
                wasted = alignment - tmp;
 
137
 
 
138
        node->start = hole_start + wasted;
 
139
        node->size = size;
 
140
        node->mm = mm;
 
141
        node->allocated = 1;
 
142
 
 
143
        INIT_LIST_HEAD(&node->hole_stack);
 
144
        list_add(&node->node_list, &hole_node->node_list);
 
145
 
 
146
        BUG_ON(node->start + node->size > hole_end);
 
147
 
 
148
        if (node->start + node->size < hole_end) {
 
149
                list_add(&node->hole_stack, &mm->hole_stack);
 
150
                node->hole_follows = 1;
 
151
        } else {
 
152
                node->hole_follows = 0;
 
153
        }
 
154
}
 
155
 
 
156
struct drm_mm_node *drm_mm_get_block_generic(struct drm_mm_node *hole_node,
151
157
                                             unsigned long size,
152
158
                                             unsigned alignment,
153
159
                                             int atomic)
154
160
{
155
 
 
156
 
        struct drm_mm_node *align_splitoff = NULL;
157
 
        unsigned tmp = 0;
158
 
 
159
 
        if (alignment)
160
 
                tmp = node->start % alignment;
161
 
 
162
 
        if (tmp) {
163
 
                align_splitoff =
164
 
                    drm_mm_split_at_start(node, alignment - tmp, atomic);
165
 
                if (unlikely(align_splitoff == NULL))
166
 
                        return NULL;
167
 
        }
168
 
 
169
 
        if (node->size == size) {
170
 
                list_del_init(&node->free_stack);
171
 
                node->free = 0;
172
 
        } else {
173
 
                node = drm_mm_split_at_start(node, size, atomic);
174
 
        }
175
 
 
176
 
        if (align_splitoff)
177
 
                drm_mm_put_block(align_splitoff);
 
161
        struct drm_mm_node *node;
 
162
 
 
163
        node = drm_mm_kmalloc(hole_node->mm, atomic);
 
164
        if (unlikely(node == NULL))
 
165
                return NULL;
 
166
 
 
167
        drm_mm_insert_helper(hole_node, node, size, alignment);
178
168
 
179
169
        return node;
180
170
}
181
171
EXPORT_SYMBOL(drm_mm_get_block_generic);
182
172
 
183
 
struct drm_mm_node *drm_mm_get_block_range_generic(struct drm_mm_node *node,
184
 
                                                unsigned long size,
185
 
                                                unsigned alignment,
186
 
                                                unsigned long start,
187
 
                                                unsigned long end,
188
 
                                                int atomic)
189
 
{
190
 
        struct drm_mm_node *align_splitoff = NULL;
191
 
        unsigned tmp = 0;
192
 
        unsigned wasted = 0;
193
 
 
194
 
        if (node->start < start)
195
 
                wasted += start - node->start;
 
173
/**
 
174
 * Search for free space and insert a preallocated memory node. Returns
 
175
 * -ENOSPC if no suitable free area is available. The preallocated memory node
 
176
 * must be cleared.
 
177
 */
 
178
int drm_mm_insert_node(struct drm_mm *mm, struct drm_mm_node *node,
 
179
                       unsigned long size, unsigned alignment)
 
180
{
 
181
        struct drm_mm_node *hole_node;
 
182
 
 
183
        hole_node = drm_mm_search_free(mm, size, alignment, 0);
 
184
        if (!hole_node)
 
185
                return -ENOSPC;
 
186
 
 
187
        drm_mm_insert_helper(hole_node, node, size, alignment);
 
188
 
 
189
        return 0;
 
190
}
 
191
EXPORT_SYMBOL(drm_mm_insert_node);
 
192
 
 
193
static void drm_mm_insert_helper_range(struct drm_mm_node *hole_node,
 
194
                                       struct drm_mm_node *node,
 
195
                                       unsigned long size, unsigned alignment,
 
196
                                       unsigned long start, unsigned long end)
 
197
{
 
198
        struct drm_mm *mm = hole_node->mm;
 
199
        unsigned long tmp = 0, wasted = 0;
 
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
 
 
203
        BUG_ON(!hole_node->hole_follows || node->allocated);
 
204
 
 
205
        if (hole_start < start)
 
206
                wasted += start - hole_start;
196
207
        if (alignment)
197
 
                tmp = ((node->start + wasted) % alignment);
 
208
                tmp = (hole_start + wasted) % alignment;
198
209
 
199
210
        if (tmp)
200
211
                wasted += alignment - tmp;
201
 
        if (wasted) {
202
 
                align_splitoff = drm_mm_split_at_start(node, wasted, atomic);
203
 
                if (unlikely(align_splitoff == NULL))
204
 
                        return NULL;
 
212
 
 
213
        if (!wasted) {
 
214
                hole_node->hole_follows = 0;
 
215
                list_del_init(&hole_node->hole_stack);
205
216
        }
206
217
 
207
 
        if (node->size == size) {
208
 
                list_del_init(&node->free_stack);
209
 
                node->free = 0;
 
218
        node->start = hole_start + wasted;
 
219
        node->size = size;
 
220
        node->mm = mm;
 
221
        node->allocated = 1;
 
222
 
 
223
        INIT_LIST_HEAD(&node->hole_stack);
 
224
        list_add(&node->node_list, &hole_node->node_list);
 
225
 
 
226
        BUG_ON(node->start + node->size > hole_end);
 
227
        BUG_ON(node->start + node->size > end);
 
228
 
 
229
        if (node->start + node->size < hole_end) {
 
230
                list_add(&node->hole_stack, &mm->hole_stack);
 
231
                node->hole_follows = 1;
210
232
        } else {
211
 
                node = drm_mm_split_at_start(node, size, atomic);
 
233
                node->hole_follows = 0;
212
234
        }
213
 
 
214
 
        if (align_splitoff)
215
 
                drm_mm_put_block(align_splitoff);
 
235
}
 
236
 
 
237
struct drm_mm_node *drm_mm_get_block_range_generic(struct drm_mm_node *hole_node,
 
238
                                                unsigned long size,
 
239
                                                unsigned alignment,
 
240
                                                unsigned long start,
 
241
                                                unsigned long end,
 
242
                                                int atomic)
 
243
{
 
244
        struct drm_mm_node *node;
 
245
 
 
246
        node = drm_mm_kmalloc(hole_node->mm, atomic);
 
247
        if (unlikely(node == NULL))
 
248
                return NULL;
 
249
 
 
250
        drm_mm_insert_helper_range(hole_node, node, size, alignment,
 
251
                                   start, end);
216
252
 
217
253
        return node;
218
254
}
219
255
EXPORT_SYMBOL(drm_mm_get_block_range_generic);
220
256
 
 
257
/**
 
258
 * Search for free space and insert a preallocated memory node. Returns
 
259
 * -ENOSPC if no suitable free area is available. This is for range
 
260
 * restricted allocations. The preallocated memory node must be cleared.
 
261
 */
 
262
int drm_mm_insert_node_in_range(struct drm_mm *mm, struct drm_mm_node *node,
 
263
                                unsigned long size, unsigned alignment,
 
264
                                unsigned long start, unsigned long end)
 
265
{
 
266
        struct drm_mm_node *hole_node;
 
267
 
 
268
        hole_node = drm_mm_search_free_in_range(mm, size, alignment,
 
269
                                                start, end, 0);
 
270
        if (!hole_node)
 
271
                return -ENOSPC;
 
272
 
 
273
        drm_mm_insert_helper_range(hole_node, node, size, alignment,
 
274
                                   start, end);
 
275
 
 
276
        return 0;
 
277
}
 
278
EXPORT_SYMBOL(drm_mm_insert_node_in_range);
 
279
 
 
280
/**
 
281
 * Remove a memory node from the allocator.
 
282
 */
 
283
void drm_mm_remove_node(struct drm_mm_node *node)
 
284
{
 
285
        struct drm_mm *mm = node->mm;
 
286
        struct drm_mm_node *prev_node;
 
287
 
 
288
        BUG_ON(node->scanned_block || node->scanned_prev_free
 
289
                                   || node->scanned_next_free);
 
290
 
 
291
        prev_node =
 
292
            list_entry(node->node_list.prev, struct drm_mm_node, node_list);
 
293
 
 
294
        if (node->hole_follows) {
 
295
                BUG_ON(drm_mm_hole_node_start(node)
 
296
                                == drm_mm_hole_node_end(node));
 
297
                list_del(&node->hole_stack);
 
298
        } else
 
299
                BUG_ON(drm_mm_hole_node_start(node)
 
300
                                != drm_mm_hole_node_end(node));
 
301
 
 
302
        if (!prev_node->hole_follows) {
 
303
                prev_node->hole_follows = 1;
 
304
                list_add(&prev_node->hole_stack, &mm->hole_stack);
 
305
        } else
 
306
                list_move(&prev_node->hole_stack, &mm->hole_stack);
 
307
 
 
308
        list_del(&node->node_list);
 
309
        node->allocated = 0;
 
310
}
 
311
EXPORT_SYMBOL(drm_mm_remove_node);
 
312
 
221
313
/*
222
 
 * Put a block. Merge with the previous and / or next block if they are free.
223
 
 * Otherwise add to the free stack.
 
314
 * Remove a memory node from the allocator and free the allocated struct
 
315
 * drm_mm_node. Only to be used on a struct drm_mm_node obtained by one of the
 
316
 * drm_mm_get_block functions.
224
317
 */
225
 
 
226
 
void drm_mm_put_block(struct drm_mm_node *cur)
 
318
void drm_mm_put_block(struct drm_mm_node *node)
227
319
{
228
320
 
229
 
        struct drm_mm *mm = cur->mm;
230
 
        struct list_head *cur_head = &cur->node_list;
231
 
        struct list_head *root_head = &mm->node_list;
232
 
        struct drm_mm_node *prev_node = NULL;
233
 
        struct drm_mm_node *next_node;
234
 
 
235
 
        int merged = 0;
236
 
 
237
 
        BUG_ON(cur->scanned_block || cur->scanned_prev_free
238
 
                                  || cur->scanned_next_free);
239
 
 
240
 
        if (cur_head->prev != root_head) {
241
 
                prev_node =
242
 
                    list_entry(cur_head->prev, struct drm_mm_node, node_list);
243
 
                if (prev_node->free) {
244
 
                        prev_node->size += cur->size;
245
 
                        merged = 1;
246
 
                }
247
 
        }
248
 
        if (cur_head->next != root_head) {
249
 
                next_node =
250
 
                    list_entry(cur_head->next, struct drm_mm_node, node_list);
251
 
                if (next_node->free) {
252
 
                        if (merged) {
253
 
                                prev_node->size += next_node->size;
254
 
                                list_del(&next_node->node_list);
255
 
                                list_del(&next_node->free_stack);
256
 
                                spin_lock(&mm->unused_lock);
257
 
                                if (mm->num_unused < MM_UNUSED_TARGET) {
258
 
                                        list_add(&next_node->free_stack,
259
 
                                                 &mm->unused_nodes);
260
 
                                        ++mm->num_unused;
261
 
                                } else
262
 
                                        kfree(next_node);
263
 
                                spin_unlock(&mm->unused_lock);
264
 
                        } else {
265
 
                                next_node->size += cur->size;
266
 
                                next_node->start = cur->start;
267
 
                                merged = 1;
268
 
                        }
269
 
                }
270
 
        }
271
 
        if (!merged) {
272
 
                cur->free = 1;
273
 
                list_add(&cur->free_stack, &mm->free_stack);
274
 
        } else {
275
 
                list_del(&cur->node_list);
276
 
                spin_lock(&mm->unused_lock);
277
 
                if (mm->num_unused < MM_UNUSED_TARGET) {
278
 
                        list_add(&cur->free_stack, &mm->unused_nodes);
279
 
                        ++mm->num_unused;
280
 
                } else
281
 
                        kfree(cur);
282
 
                spin_unlock(&mm->unused_lock);
283
 
        }
 
321
        struct drm_mm *mm = node->mm;
 
322
 
 
323
        drm_mm_remove_node(node);
 
324
 
 
325
        spin_lock(&mm->unused_lock);
 
326
        if (mm->num_unused < MM_UNUSED_TARGET) {
 
327
                list_add(&node->node_list, &mm->unused_nodes);
 
328
                ++mm->num_unused;
 
329
        } else
 
330
                kfree(node);
 
331
        spin_unlock(&mm->unused_lock);
284
332
}
285
 
 
286
333
EXPORT_SYMBOL(drm_mm_put_block);
287
334
 
288
335
static int check_free_hole(unsigned long start, unsigned long end,
319
366
        best = NULL;
320
367
        best_size = ~0UL;
321
368
 
322
 
        list_for_each_entry(entry, &mm->free_stack, free_stack) {
323
 
                if (!check_free_hole(entry->start, entry->start + entry->size,
 
369
        list_for_each_entry(entry, &mm->hole_stack, hole_stack) {
 
370
                BUG_ON(!entry->hole_follows);
 
371
                if (!check_free_hole(drm_mm_hole_node_start(entry),
 
372
                                     drm_mm_hole_node_end(entry),
324
373
                                     size, alignment))
325
374
                        continue;
326
375
 
353
402
        best = NULL;
354
403
        best_size = ~0UL;
355
404
 
356
 
        list_for_each_entry(entry, &mm->free_stack, free_stack) {
357
 
                unsigned long adj_start = entry->start < start ?
358
 
                        start : entry->start;
359
 
                unsigned long adj_end = entry->start + entry->size > end ?
360
 
                        end : entry->start + entry->size;
 
405
        list_for_each_entry(entry, &mm->hole_stack, hole_stack) {
 
406
                unsigned long adj_start = drm_mm_hole_node_start(entry) < start ?
 
407
                        start : drm_mm_hole_node_start(entry);
 
408
                unsigned long adj_end = drm_mm_hole_node_end(entry) > end ?
 
409
                        end : drm_mm_hole_node_end(entry);
361
410
 
 
411
                BUG_ON(!entry->hole_follows);
362
412
                if (!check_free_hole(adj_start, adj_end, size, alignment))
363
413
                        continue;
364
414
 
376
426
EXPORT_SYMBOL(drm_mm_search_free_in_range);
377
427
 
378
428
/**
 
429
 * Moves an allocation. To be used with embedded struct drm_mm_node.
 
430
 */
 
431
void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new)
 
432
{
 
433
        list_replace(&old->node_list, &new->node_list);
 
434
        list_replace(&old->hole_stack, &new->hole_stack);
 
435
        new->hole_follows = old->hole_follows;
 
436
        new->mm = old->mm;
 
437
        new->start = old->start;
 
438
        new->size = old->size;
 
439
 
 
440
        old->allocated = 0;
 
441
        new->allocated = 1;
 
442
}
 
443
EXPORT_SYMBOL(drm_mm_replace_node);
 
444
 
 
445
/**
379
446
 * Initializa lru scanning.
380
447
 *
381
448
 * This simply sets up the scanning routines with the parameters for the desired
393
460
        mm->scan_hit_start = 0;
394
461
        mm->scan_hit_size = 0;
395
462
        mm->scan_check_range = 0;
 
463
        mm->prev_scanned_node = NULL;
396
464
}
397
465
EXPORT_SYMBOL(drm_mm_init_scan);
398
466
 
418
486
        mm->scan_start = start;
419
487
        mm->scan_end = end;
420
488
        mm->scan_check_range = 1;
 
489
        mm->prev_scanned_node = NULL;
421
490
}
422
491
EXPORT_SYMBOL(drm_mm_init_scan_with_range);
423
492
 
430
499
int drm_mm_scan_add_block(struct drm_mm_node *node)
431
500
{
432
501
        struct drm_mm *mm = node->mm;
433
 
        struct list_head *prev_free, *next_free;
434
 
        struct drm_mm_node *prev_node, *next_node;
 
502
        struct drm_mm_node *prev_node;
 
503
        unsigned long hole_start, hole_end;
435
504
        unsigned long adj_start;
436
505
        unsigned long adj_end;
437
506
 
438
507
        mm->scanned_blocks++;
439
508
 
440
 
        prev_free = next_free = NULL;
441
 
 
442
 
        BUG_ON(node->free);
 
509
        BUG_ON(node->scanned_block);
443
510
        node->scanned_block = 1;
444
 
        node->free = 1;
445
 
 
446
 
        if (node->node_list.prev != &mm->node_list) {
447
 
                prev_node = list_entry(node->node_list.prev, struct drm_mm_node,
448
 
                                       node_list);
449
 
 
450
 
                if (prev_node->free) {
451
 
                        list_del(&prev_node->node_list);
452
 
 
453
 
                        node->start = prev_node->start;
454
 
                        node->size += prev_node->size;
455
 
 
456
 
                        prev_node->scanned_prev_free = 1;
457
 
 
458
 
                        prev_free = &prev_node->free_stack;
459
 
                }
460
 
        }
461
 
 
462
 
        if (node->node_list.next != &mm->node_list) {
463
 
                next_node = list_entry(node->node_list.next, struct drm_mm_node,
464
 
                                       node_list);
465
 
 
466
 
                if (next_node->free) {
467
 
                        list_del(&next_node->node_list);
468
 
 
469
 
                        node->size += next_node->size;
470
 
 
471
 
                        next_node->scanned_next_free = 1;
472
 
 
473
 
                        next_free = &next_node->free_stack;
474
 
                }
475
 
        }
476
 
 
477
 
        /* The free_stack list is not used for allocated objects, so these two
478
 
         * pointers can be abused (as long as no allocations in this memory
479
 
         * manager happens). */
480
 
        node->free_stack.prev = prev_free;
481
 
        node->free_stack.next = next_free;
482
 
 
 
511
 
 
512
        prev_node = list_entry(node->node_list.prev, struct drm_mm_node,
 
513
                               node_list);
 
514
 
 
515
        node->scanned_preceeds_hole = prev_node->hole_follows;
 
516
        prev_node->hole_follows = 1;
 
517
        list_del(&node->node_list);
 
518
        node->node_list.prev = &prev_node->node_list;
 
519
        node->node_list.next = &mm->prev_scanned_node->node_list;
 
520
        mm->prev_scanned_node = node;
 
521
 
 
522
        hole_start = drm_mm_hole_node_start(prev_node);
 
523
        hole_end = drm_mm_hole_node_end(prev_node);
483
524
        if (mm->scan_check_range) {
484
 
                adj_start = node->start < mm->scan_start ?
485
 
                        mm->scan_start : node->start;
486
 
                adj_end = node->start + node->size > mm->scan_end ?
487
 
                        mm->scan_end : node->start + node->size;
 
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;
488
529
        } else {
489
 
                adj_start = node->start;
490
 
                adj_end = node->start + node->size;
 
530
                adj_start = hole_start;
 
531
                adj_end = hole_end;
491
532
        }
492
533
 
493
534
        if (check_free_hole(adj_start , adj_end,
494
535
                            mm->scan_size, mm->scan_alignment)) {
495
 
                mm->scan_hit_start = node->start;
496
 
                mm->scan_hit_size = node->size;
 
536
                mm->scan_hit_start = hole_start;
 
537
                mm->scan_hit_size = hole_end;
497
538
 
498
539
                return 1;
499
540
        }
510
551
 * corrupted.
511
552
 *
512
553
 * When the scan list is empty, the selected memory nodes can be freed. An
513
 
 * immediatly following drm_mm_search_free with best_match = 0 will then return
 
554
 * immediately following drm_mm_search_free with best_match = 0 will then return
514
555
 * the just freed block (because its at the top of the free_stack list).
515
556
 *
516
557
 * Returns one if this block should be evicted, zero otherwise. Will always
519
560
int drm_mm_scan_remove_block(struct drm_mm_node *node)
520
561
{
521
562
        struct drm_mm *mm = node->mm;
522
 
        struct drm_mm_node *prev_node, *next_node;
 
563
        struct drm_mm_node *prev_node;
523
564
 
524
565
        mm->scanned_blocks--;
525
566
 
526
567
        BUG_ON(!node->scanned_block);
527
568
        node->scanned_block = 0;
528
 
        node->free = 0;
529
 
 
530
 
        prev_node = list_entry(node->free_stack.prev, struct drm_mm_node,
531
 
                               free_stack);
532
 
        next_node = list_entry(node->free_stack.next, struct drm_mm_node,
533
 
                               free_stack);
534
 
 
535
 
        if (prev_node) {
536
 
                BUG_ON(!prev_node->scanned_prev_free);
537
 
                prev_node->scanned_prev_free = 0;
538
 
 
539
 
                list_add_tail(&prev_node->node_list, &node->node_list);
540
 
 
541
 
                node->start = prev_node->start + prev_node->size;
542
 
                node->size -= prev_node->size;
543
 
        }
544
 
 
545
 
        if (next_node) {
546
 
                BUG_ON(!next_node->scanned_next_free);
547
 
                next_node->scanned_next_free = 0;
548
 
 
549
 
                list_add(&next_node->node_list, &node->node_list);
550
 
 
551
 
                node->size -= next_node->size;
552
 
        }
553
 
 
554
 
        INIT_LIST_HEAD(&node->free_stack);
 
569
 
 
570
        prev_node = list_entry(node->node_list.prev, struct drm_mm_node,
 
571
                               node_list);
 
572
 
 
573
        prev_node->hole_follows = node->scanned_preceeds_hole;
 
574
        INIT_LIST_HEAD(&node->node_list);
 
575
        list_add(&node->node_list, &prev_node->node_list);
555
576
 
556
577
        /* Only need to check for containement because start&size for the
557
578
         * complete resulting free block (not just the desired part) is
568
589
 
569
590
int drm_mm_clean(struct drm_mm * mm)
570
591
{
571
 
        struct list_head *head = &mm->node_list;
 
592
        struct list_head *head = &mm->head_node.node_list;
572
593
 
573
594
        return (head->next->next == head);
574
595
}
576
597
 
577
598
int drm_mm_init(struct drm_mm * mm, unsigned long start, unsigned long size)
578
599
{
579
 
        INIT_LIST_HEAD(&mm->node_list);
580
 
        INIT_LIST_HEAD(&mm->free_stack);
 
600
        INIT_LIST_HEAD(&mm->hole_stack);
581
601
        INIT_LIST_HEAD(&mm->unused_nodes);
582
602
        mm->num_unused = 0;
583
603
        mm->scanned_blocks = 0;
584
604
        spin_lock_init(&mm->unused_lock);
585
605
 
586
 
        return drm_mm_create_tail_node(mm, start, size, 0);
 
606
        /* Clever trick to avoid a special case in the free hole tracking. */
 
607
        INIT_LIST_HEAD(&mm->head_node.node_list);
 
608
        INIT_LIST_HEAD(&mm->head_node.hole_stack);
 
609
        mm->head_node.hole_follows = 1;
 
610
        mm->head_node.scanned_block = 0;
 
611
        mm->head_node.scanned_prev_free = 0;
 
612
        mm->head_node.scanned_next_free = 0;
 
613
        mm->head_node.mm = mm;
 
614
        mm->head_node.start = start + size;
 
615
        mm->head_node.size = start - mm->head_node.start;
 
616
        list_add_tail(&mm->head_node.hole_stack, &mm->hole_stack);
 
617
 
 
618
        return 0;
587
619
}
588
620
EXPORT_SYMBOL(drm_mm_init);
589
621
 
590
622
void drm_mm_takedown(struct drm_mm * mm)
591
623
{
592
 
        struct list_head *bnode = mm->free_stack.next;
593
 
        struct drm_mm_node *entry;
594
 
        struct drm_mm_node *next;
595
 
 
596
 
        entry = list_entry(bnode, struct drm_mm_node, free_stack);
597
 
 
598
 
        if (entry->node_list.next != &mm->node_list ||
599
 
            entry->free_stack.next != &mm->free_stack) {
 
624
        struct drm_mm_node *entry, *next;
 
625
 
 
626
        if (!list_empty(&mm->head_node.node_list)) {
600
627
                DRM_ERROR("Memory manager not clean. Delaying takedown\n");
601
628
                return;
602
629
        }
603
630
 
604
 
        list_del(&entry->free_stack);
605
 
        list_del(&entry->node_list);
606
 
        kfree(entry);
607
 
 
608
631
        spin_lock(&mm->unused_lock);
609
 
        list_for_each_entry_safe(entry, next, &mm->unused_nodes, free_stack) {
610
 
                list_del(&entry->free_stack);
 
632
        list_for_each_entry_safe(entry, next, &mm->unused_nodes, node_list) {
 
633
                list_del(&entry->node_list);
611
634
                kfree(entry);
612
635
                --mm->num_unused;
613
636
        }
620
643
void drm_mm_debug_table(struct drm_mm *mm, const char *prefix)
621
644
{
622
645
        struct drm_mm_node *entry;
623
 
        int total_used = 0, total_free = 0, total = 0;
624
 
 
625
 
        list_for_each_entry(entry, &mm->node_list, node_list) {
626
 
                printk(KERN_DEBUG "%s 0x%08lx-0x%08lx: %8ld: %s\n",
 
646
        unsigned long total_used = 0, total_free = 0, total = 0;
 
647
        unsigned long hole_start, hole_end, hole_size;
 
648
 
 
649
        hole_start = drm_mm_hole_node_start(&mm->head_node);
 
650
        hole_end = drm_mm_hole_node_end(&mm->head_node);
 
651
        hole_size = hole_end - hole_start;
 
652
        if (hole_size)
 
653
                printk(KERN_DEBUG "%s 0x%08lx-0x%08lx: %8lu: free\n",
 
654
                        prefix, hole_start, hole_end,
 
655
                        hole_size);
 
656
        total_free += hole_size;
 
657
 
 
658
        drm_mm_for_each_node(entry, mm) {
 
659
                printk(KERN_DEBUG "%s 0x%08lx-0x%08lx: %8lu: used\n",
627
660
                        prefix, entry->start, entry->start + entry->size,
628
 
                        entry->size, entry->free ? "free" : "used");
629
 
                total += entry->size;
630
 
                if (entry->free)
631
 
                        total_free += entry->size;
632
 
                else
633
 
                        total_used += entry->size;
 
661
                        entry->size);
 
662
                total_used += entry->size;
 
663
 
 
664
                if (entry->hole_follows) {
 
665
                        hole_start = drm_mm_hole_node_start(entry);
 
666
                        hole_end = drm_mm_hole_node_end(entry);
 
667
                        hole_size = hole_end - hole_start;
 
668
                        printk(KERN_DEBUG "%s 0x%08lx-0x%08lx: %8lu: free\n",
 
669
                                prefix, hole_start, hole_end,
 
670
                                hole_size);
 
671
                        total_free += hole_size;
 
672
                }
634
673
        }
635
 
        printk(KERN_DEBUG "%s total: %d, used %d free %d\n", prefix, total,
 
674
        total = total_free + total_used;
 
675
 
 
676
        printk(KERN_DEBUG "%s total: %lu, used %lu free %lu\n", prefix, total,
636
677
                total_used, total_free);
637
678
}
638
679
EXPORT_SYMBOL(drm_mm_debug_table);
641
682
int drm_mm_dump_table(struct seq_file *m, struct drm_mm *mm)
642
683
{
643
684
        struct drm_mm_node *entry;
644
 
        int total_used = 0, total_free = 0, total = 0;
645
 
 
646
 
        list_for_each_entry(entry, &mm->node_list, node_list) {
647
 
                seq_printf(m, "0x%08lx-0x%08lx: 0x%08lx: %s\n", entry->start, entry->start + entry->size, entry->size, entry->free ? "free" : "used");
648
 
                total += entry->size;
649
 
                if (entry->free)
650
 
                        total_free += entry->size;
651
 
                else
652
 
                        total_used += entry->size;
 
685
        unsigned long total_used = 0, total_free = 0, total = 0;
 
686
        unsigned long hole_start, hole_end, hole_size;
 
687
 
 
688
        hole_start = drm_mm_hole_node_start(&mm->head_node);
 
689
        hole_end = drm_mm_hole_node_end(&mm->head_node);
 
690
        hole_size = hole_end - hole_start;
 
691
        if (hole_size)
 
692
                seq_printf(m, "0x%08lx-0x%08lx: 0x%08lx: free\n",
 
693
                                hole_start, hole_end, hole_size);
 
694
        total_free += hole_size;
 
695
 
 
696
        drm_mm_for_each_node(entry, mm) {
 
697
                seq_printf(m, "0x%08lx-0x%08lx: 0x%08lx: used\n",
 
698
                                entry->start, entry->start + entry->size,
 
699
                                entry->size);
 
700
                total_used += entry->size;
 
701
                if (entry->hole_follows) {
 
702
                        hole_start = drm_mm_hole_node_start(entry);
 
703
                        hole_end = drm_mm_hole_node_end(entry);
 
704
                        hole_size = hole_end - hole_start;
 
705
                        seq_printf(m, "0x%08lx-0x%08lx: 0x%08lx: free\n",
 
706
                                        hole_start, hole_end, hole_size);
 
707
                        total_free += hole_size;
 
708
                }
653
709
        }
654
 
        seq_printf(m, "total: %d, used %d free %d\n", total, total_used, total_free);
 
710
        total = total_free + total_used;
 
711
 
 
712
        seq_printf(m, "total: %lu, used %lu free %lu\n", total, total_used, total_free);
655
713
        return 0;
656
714
}
657
715
EXPORT_SYMBOL(drm_mm_dump_table);