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 #define MM_UNUSED_TARGET 4
  51
  52 static struct drm_mm_node *drm_mm_kmalloc(struct drm_mm *mm, int atomic)
  53 {
  54         struct drm_mm_node *child;
  55
  56         if (atomic)
  57                 child = kzalloc(sizeof(*child), GFP_ATOMIC);
  58         else
  59                 child = kzalloc(sizeof(*child), GFP_KERNEL);
  60
  61         if (unlikely(child == NULL)) {
  62                 spin_lock(&mm->unused_lock);
  63                 if (list_empty(&mm->unused_nodes))
  64                         child = NULL;
  65                 else {
  66                         child =
  67                             list_entry(mm->unused_nodes.next,
  68                                        struct drm_mm_node, node_list);
  69                         list_del(&child->node_list);
  70                         --mm->num_unused;
  71                 }
  72                 spin_unlock(&mm->unused_lock);
  73         }
  74         return child;
  75 }
  76
  77 /* drm_mm_pre_get() - pre allocate drm_mm_node structure
  78  * drm_mm:      memory manager struct we are pre-allocating for
  79  *
  80  * Returns 0 on success or -ENOMEM if allocation fails.
  81  */
  82 int drm_mm_pre_get(struct drm_mm *mm)
  83 {
  84         struct drm_mm_node *node;
  85
  86         spin_lock(&mm->unused_lock);
  87         while (mm->num_unused < MM_UNUSED_TARGET) {
  88                 spin_unlock(&mm->unused_lock);
  89                 node = kzalloc(sizeof(*node), GFP_KERNEL);
  90                 spin_lock(&mm->unused_lock);
  91
  92                 if (unlikely(node == NULL)) {
  93                         int ret = (mm->num_unused < 2) ? -ENOMEM : 0;
  94                         spin_unlock(&mm->unused_lock);
  95                         return ret;
  96                 }
  97                 ++mm->num_unused;
  98                 list_add_tail(&node->node_list, &mm->unused_nodes);
  99         }
 100         spin_unlock(&mm->unused_lock);
 101         return 0;
 102 }
 103 EXPORT_SYMBOL(drm_mm_pre_get);
 104
 105 static void drm_mm_insert_helper(struct drm_mm_node *hole_node,
 106                                  struct drm_mm_node *node,
 107                                  unsigned long size, unsigned alignment,
 108                                  unsigned long color)
 109 {
 110         struct drm_mm *mm = hole_node->mm;
 111         unsigned long hole_start = drm_mm_hole_node_start(hole_node);
 112         unsigned long hole_end = drm_mm_hole_node_end(hole_node);
 113         unsigned long adj_start = hole_start;
 114         unsigned long adj_end = hole_end;
 115
 116         BUG_ON(node->allocated);
 117
 118         if (mm->color_adjust)
 119                 mm->color_adjust(hole_node, color, &adj_start, &adj_end);
 120
 121         if (alignment) {
 122                 unsigned tmp = adj_start % alignment;
 123                 if (tmp)
 124                         adj_start += alignment - tmp;
 125         }
 126
 127         if (adj_start == hole_start) {
 128                 hole_node->hole_follows = 0;
 129                 list_del(&hole_node->hole_stack);
 130         }
 131
 132         node->start = adj_start;
 133         node->size = size;
 134         node->mm = mm;
 135         node->color = color;
 136         node->allocated = 1;
 137
 138         INIT_LIST_HEAD(&node->hole_stack);
 139         list_add(&node->node_list, &hole_node->node_list);
 140
 141         BUG_ON(node->start + node->size > adj_end);
 142
 143         node->hole_follows = 0;
 144         if (__drm_mm_hole_node_start(node) < hole_end) {
 145                 list_add(&node->hole_stack, &mm->hole_stack);
 146                 node->hole_follows = 1;
 147         }
 148 }
 149
 150 struct drm_mm_node *drm_mm_create_block(struct drm_mm *mm,
 151                                         unsigned long start,
 152                                         unsigned long size,
 153                                         bool atomic)
 154 {
 155         struct drm_mm_node *hole, *node;
 156         unsigned long end = start + size;
 157         unsigned long hole_start;
 158         unsigned long hole_end;
 159
 160         drm_mm_for_each_hole(hole, mm, hole_start, hole_end) {
 161                 if (hole_start > start || hole_end < end)
 162                         continue;
 163
 164                 node = drm_mm_kmalloc(mm, atomic);
 165                 if (unlikely(node == NULL))
 166                         return NULL;
 167
 168                 node->start = start;
 169                 node->size = size;
 170                 node->mm = mm;
 171                 node->allocated = 1;
 172
 173                 INIT_LIST_HEAD(&node->hole_stack);
 174                 list_add(&node->node_list, &hole->node_list);
 175
 176                 if (start == hole_start) {
 177                         hole->hole_follows = 0;
 178                         list_del_init(&hole->hole_stack);
 179                 }
 180
 181                 node->hole_follows = 0;
 182                 if (end != hole_end) {
 183                         list_add(&node->hole_stack, &mm->hole_stack);
 184                         node->hole_follows = 1;
 185                 }
 186
 187                 return node;
 188         }
 189
 190         WARN(1, "no hole found for block 0x%lx + 0x%lx\n", start, size);
 191         return NULL;
 192 }
 193 EXPORT_SYMBOL(drm_mm_create_block);
 194
 195 struct drm_mm_node *drm_mm_get_block_generic(struct drm_mm_node *hole_node,
 196                                              unsigned long size,
 197                                              unsigned alignment,
 198                                              unsigned long color,
 199                                              int atomic)
 200 {
 201         struct drm_mm_node *node;
 202
 203         node = drm_mm_kmalloc(hole_node->mm, atomic);
 204         if (unlikely(node == NULL))
 205                 return NULL;
 206
 207         drm_mm_insert_helper(hole_node, node, size, alignment, color);
 208
 209         return node;
 210 }
 211 EXPORT_SYMBOL(drm_mm_get_block_generic);
 212
 213 /**
 214  * Search for free space and insert a preallocated memory node. Returns
 215  * -ENOSPC if no suitable free area is available. The preallocated memory node
 216  * must be cleared.
 217  */
 218 int drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node,
 219                                unsigned long size, unsigned alignment,
 220                                unsigned long color)
 221 {
 222         struct drm_mm_node *hole_node;
 223
 224         hole_node = drm_mm_search_free_generic(mm, size, alignment,
 225                                                color, 0);
 226         if (!hole_node)
 227                 return -ENOSPC;
 228
 229         drm_mm_insert_helper(hole_node, node, size, alignment, color);
 230         return 0;
 231 }
 232 EXPORT_SYMBOL(drm_mm_insert_node_generic);
 233
 234 int drm_mm_insert_node(struct drm_mm *mm, struct drm_mm_node *node,
 235                        unsigned long size, unsigned alignment)
 236 {
 237         return drm_mm_insert_node_generic(mm, node, size, alignment, 0);
 238 }
 239 EXPORT_SYMBOL(drm_mm_insert_node);
 240
 241 static void drm_mm_insert_helper_range(struct drm_mm_node *hole_node,
 242                                        struct drm_mm_node *node,
 243                                        unsigned long size, unsigned alignment,
 244                                        unsigned long color,
 245                                        unsigned long start, unsigned long end)
 246 {
 247         struct drm_mm *mm = hole_node->mm;
 248         unsigned long hole_start = drm_mm_hole_node_start(hole_node);
 249         unsigned long hole_end = drm_mm_hole_node_end(hole_node);
 250         unsigned long adj_start = hole_start;
 251         unsigned long adj_end = hole_end;
 252
 253         BUG_ON(!hole_node->hole_follows || node->allocated);
 254
 255         if (mm->color_adjust)
 256                 mm->color_adjust(hole_node, color, &adj_start, &adj_end);
 257
 258         if (adj_start < start)
 259                 adj_start = start;
 260
 261         if (alignment) {
 262                 unsigned tmp = adj_start % alignment;
 263                 if (tmp)
 264                         adj_start += alignment - tmp;
 265         }
 266
 267         if (adj_start == hole_start) {
 268                 hole_node->hole_follows = 0;
 269                 list_del(&hole_node->hole_stack);
 270         }
 271
 272         node->start = adj_start;
 273         node->size = size;
 274         node->mm = mm;
 275         node->color = color;
 276         node->allocated = 1;
 277
 278         INIT_LIST_HEAD(&node->hole_stack);
 279         list_add(&node->node_list, &hole_node->node_list);
 280
 281         BUG_ON(node->start + node->size > adj_end);
 282         BUG_ON(node->start + node->size > end);
 283
 284         node->hole_follows = 0;
 285         if (__drm_mm_hole_node_start(node) < hole_end) {
 286                 list_add(&node->hole_stack, &mm->hole_stack);
 287                 node->hole_follows = 1;
 288         }
 289 }
 290
 291 struct drm_mm_node *drm_mm_get_block_range_generic(struct drm_mm_node *hole_node,
 292                                                 unsigned long size,
 293                                                 unsigned alignment,
 294                                                 unsigned long color,
 295                                                 unsigned long start,
 296                                                 unsigned long end,
 297                                                 int atomic)
 298 {
 299         struct drm_mm_node *node;
 300
 301         node = drm_mm_kmalloc(hole_node->mm, atomic);
 302         if (unlikely(node == NULL))
 303                 return NULL;
 304
 305         drm_mm_insert_helper_range(hole_node, node, size, alignment, color,
 306                                    start, end);
 307
 308         return node;
 309 }
 310 EXPORT_SYMBOL(drm_mm_get_block_range_generic);
 311
 312 /**
 313  * Search for free space and insert a preallocated memory node. Returns
 314  * -ENOSPC if no suitable free area is available. This is for range
 315  * restricted allocations. The preallocated memory node must be cleared.
 316  */
 317 int drm_mm_insert_node_in_range_generic(struct drm_mm *mm, struct drm_mm_node *node,
 318                                         unsigned long size, unsigned alignment, unsigned long color,
 319                                         unsigned long start, unsigned long end)
 320 {
 321         struct drm_mm_node *hole_node;
 322
 323         hole_node = drm_mm_search_free_in_range_generic(mm,
 324                                                         size, alignment, color,
 325                                                         start, end, 0);
 326         if (!hole_node)
 327                 return -ENOSPC;
 328
 329         drm_mm_insert_helper_range(hole_node, node,
 330                                    size, alignment, color,
 331                                    start, end);
 332         return 0;
 333 }
 334 EXPORT_SYMBOL(drm_mm_insert_node_in_range_generic);
 335
 336 int drm_mm_insert_node_in_range(struct drm_mm *mm, struct drm_mm_node *node,
 337                                 unsigned long size, unsigned alignment,
 338                                 unsigned long start, unsigned long end)
 339 {
 340         return drm_mm_insert_node_in_range_generic(mm, node, size, alignment, 0, start, end);
 341 }
 342 EXPORT_SYMBOL(drm_mm_insert_node_in_range);
 343
 344 /**
 345  * Remove a memory node from the allocator.
 346  */
 347 void drm_mm_remove_node(struct drm_mm_node *node)
 348 {
 349         struct drm_mm *mm = node->mm;
 350         struct drm_mm_node *prev_node;
 351
 352         BUG_ON(node->scanned_block || node->scanned_prev_free
 353                                    || node->scanned_next_free);
 354
 355         prev_node =
 356             list_entry(node->node_list.prev, struct drm_mm_node, node_list);
 357
 358         if (node->hole_follows) {
 359                 BUG_ON(__drm_mm_hole_node_start(node) ==
 360                        __drm_mm_hole_node_end(node));
 361                 list_del(&node->hole_stack);
 362         } else
 363                 BUG_ON(__drm_mm_hole_node_start(node) !=
 364                        __drm_mm_hole_node_end(node));
 365
 366
 367         if (!prev_node->hole_follows) {
 368                 prev_node->hole_follows = 1;
 369                 list_add(&prev_node->hole_stack, &mm->hole_stack);
 370         } else
 371                 list_move(&prev_node->hole_stack, &mm->hole_stack);
 372
 373         list_del(&node->node_list);
 374         node->allocated = 0;
 375 }
 376 EXPORT_SYMBOL(drm_mm_remove_node);
 377
 378 /*
 379  * Remove a memory node from the allocator and free the allocated struct
 380  * drm_mm_node. Only to be used on a struct drm_mm_node obtained by one of the
 381  * drm_mm_get_block functions.
 382  */
 383 void drm_mm_put_block(struct drm_mm_node *node)
 384 {
 385
 386         struct drm_mm *mm = node->mm;
 387
 388         drm_mm_remove_node(node);
 389
 390         spin_lock(&mm->unused_lock);
 391         if (mm->num_unused < MM_UNUSED_TARGET) {
 392                 list_add(&node->node_list, &mm->unused_nodes);
 393                 ++mm->num_unused;
 394         } else
 395                 kfree(node);
 396         spin_unlock(&mm->unused_lock);
 397 }
 398 EXPORT_SYMBOL(drm_mm_put_block);
 399
 400 static int check_free_hole(unsigned long start, unsigned long end,
 401                            unsigned long size, unsigned alignment)
 402 {
 403         if (end - start < size)
 404                 return 0;
 405
 406         if (alignment) {
 407                 unsigned tmp = start % alignment;
 408                 if (tmp)
 409                         start += alignment - tmp;
 410         }
 411
 412         return end >= start + size;
 413 }
 414
 415 struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm,
 416                                                unsigned long size,
 417                                                unsigned alignment,
 418                                                unsigned long color,
 419                                                bool best_match)
 420 {
 421         struct drm_mm_node *entry;
 422         struct drm_mm_node *best;
 423         unsigned long adj_start;
 424         unsigned long adj_end;
 425         unsigned long best_size;
 426
 427         BUG_ON(mm->scanned_blocks);
 428
 429         best = NULL;
 430         best_size = ~0UL;
 431
 432         drm_mm_for_each_hole(entry, mm, adj_start, adj_end) {
 433                 if (mm->color_adjust) {
 434                         mm->color_adjust(entry, color, &adj_start, &adj_end);
 435                         if (adj_end <= adj_start)
 436                                 continue;
 437                 }
 438
 439                 if (!check_free_hole(adj_start, adj_end, size, alignment))
 440                         continue;
 441
 442                 if (!best_match)
 443                         return entry;
 444
 445                 if (entry->size < best_size) {
 446                         best = entry;
 447                         best_size = entry->size;
 448                 }
 449         }
 450
 451         return best;
 452 }
 453 EXPORT_SYMBOL(drm_mm_search_free_generic);
 454
 455 struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_mm *mm,
 456                                                         unsigned long size,
 457                                                         unsigned alignment,
 458                                                         unsigned long color,
 459                                                         unsigned long start,
 460                                                         unsigned long end,
 461                                                         bool best_match)
 462 {
 463         struct drm_mm_node *entry;
 464         struct drm_mm_node *best;
 465         unsigned long adj_start;
 466         unsigned long adj_end;
 467         unsigned long best_size;
 468
 469         BUG_ON(mm->scanned_blocks);
 470
 471         best = NULL;
 472         best_size = ~0UL;
 473
 474         drm_mm_for_each_hole(entry, mm, adj_start, adj_end) {
 475                 if (adj_start < start)
 476                         adj_start = start;
 477                 if (adj_end > end)
 478                         adj_end = end;
 479
 480                 if (mm->color_adjust) {
 481                         mm->color_adjust(entry, color, &adj_start, &adj_end);
 482                         if (adj_end <= adj_start)
 483                                 continue;
 484                 }
 485
 486                 if (!check_free_hole(adj_start, adj_end, size, alignment))
 487                         continue;
 488
 489                 if (!best_match)
 490                         return entry;
 491
 492                 if (entry->size < best_size) {
 493                         best = entry;
 494                         best_size = entry->size;
 495                 }
 496         }
 497
 498         return best;
 499 }
 500 EXPORT_SYMBOL(drm_mm_search_free_in_range_generic);
 501
 502 /**
 503  * Moves an allocation. To be used with embedded struct drm_mm_node.
 504  */
 505 void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new)
 506 {
 507         list_replace(&old->node_list, &new->node_list);
 508         list_replace(&old->hole_stack, &new->hole_stack);
 509         new->hole_follows = old->hole_follows;
 510         new->mm = old->mm;
 511         new->start = old->start;
 512         new->size = old->size;
 513         new->color = old->color;
 514
 515         old->allocated = 0;
 516         new->allocated = 1;
 517 }
 518 EXPORT_SYMBOL(drm_mm_replace_node);
 519
 520 /**
 521  * Initializa lru scanning.
 522  *
 523  * This simply sets up the scanning routines with the parameters for the desired
 524  * hole.
 525  *
 526  * Warning: As long as the scan list is non-empty, no other operations than
 527  * adding/removing nodes to/from the scan list are allowed.
 528  */
 529 void drm_mm_init_scan(struct drm_mm *mm,
 530                       unsigned long size,
 531                       unsigned alignment,
 532                       unsigned long color)
 533 {
 534         mm->scan_color = color;
 535         mm->scan_alignment = alignment;
 536         mm->scan_size = size;
 537         mm->scanned_blocks = 0;
 538         mm->scan_hit_start = 0;
 539         mm->scan_hit_size = 0;
 540         mm->scan_check_range = 0;
 541         mm->prev_scanned_node = NULL;
 542 }
 543 EXPORT_SYMBOL(drm_mm_init_scan);
 544
 545 /**
 546  * Initializa lru scanning.
 547  *
 548  * This simply sets up the scanning routines with the parameters for the desired
 549  * hole. This version is for range-restricted scans.
 550  *
 551  * Warning: As long as the scan list is non-empty, no other operations than
 552  * adding/removing nodes to/from the scan list are allowed.
 553  */
 554 void drm_mm_init_scan_with_range(struct drm_mm *mm,
 555                                  unsigned long size,
 556                                  unsigned alignment,
 557                                  unsigned long color,
 558                                  unsigned long start,
 559                                  unsigned long end)
 560 {
 561         mm->scan_color = color;
 562         mm->scan_alignment = alignment;
 563         mm->scan_size = size;
 564         mm->scanned_blocks = 0;
 565         mm->scan_hit_start = 0;
 566         mm->scan_hit_size = 0;
 567         mm->scan_start = start;
 568         mm->scan_end = end;
 569         mm->scan_check_range = 1;
 570         mm->prev_scanned_node = NULL;
 571 }
 572 EXPORT_SYMBOL(drm_mm_init_scan_with_range);
 573
 574 /**
 575  * Add a node to the scan list that might be freed to make space for the desired
 576  * hole.
 577  *
 578  * Returns non-zero, if a hole has been found, zero otherwise.
 579  */
 580 int drm_mm_scan_add_block(struct drm_mm_node *node)
 581 {
 582         struct drm_mm *mm = node->mm;
 583         struct drm_mm_node *prev_node;
 584         unsigned long hole_start, hole_end;
 585         unsigned long adj_start;
 586         unsigned long adj_end;
 587
 588         mm->scanned_blocks++;
 589
 590         BUG_ON(node->scanned_block);
 591         node->scanned_block = 1;
 592
 593         prev_node = list_entry(node->node_list.prev, struct drm_mm_node,
 594                                node_list);
 595
 596         node->scanned_preceeds_hole = prev_node->hole_follows;
 597         prev_node->hole_follows = 1;
 598         list_del(&node->node_list);
 599         node->node_list.prev = &prev_node->node_list;
 600         node->node_list.next = &mm->prev_scanned_node->node_list;
 601         mm->prev_scanned_node = node;
 602
 603         hole_start = drm_mm_hole_node_start(prev_node);
 604         hole_end = drm_mm_hole_node_end(prev_node);
 605
 606         adj_start = hole_start;
 607         adj_end = hole_end;
 608
 609         if (mm->color_adjust)
 610                 mm->color_adjust(prev_node, mm->scan_color, &adj_start, &adj_end);
 611
 612         if (mm->scan_check_range) {
 613                 if (adj_start < mm->scan_start)
 614                         adj_start = mm->scan_start;
 615                 if (adj_end > mm->scan_end)
 616                         adj_end = mm->scan_end;
 617         }
 618
 619         if (check_free_hole(adj_start, adj_end,
 620                             mm->scan_size, mm->scan_alignment)) {
 621                 mm->scan_hit_start = hole_start;
 622                 mm->scan_hit_size = hole_end;
 623
 624                 return 1;
 625         }
 626
 627         return 0;
 628 }
 629 EXPORT_SYMBOL(drm_mm_scan_add_block);
 630
 631 /**
 632  * Remove a node from the scan list.
 633  *
 634  * Nodes _must_ be removed in the exact same order from the scan list as they
 635  * have been added, otherwise the internal state of the memory manager will be
 636  * corrupted.
 637  *
 638  * When the scan list is empty, the selected memory nodes can be freed. An
 639  * immediately following drm_mm_search_free with best_match = 0 will then return
 640  * the just freed block (because its at the top of the free_stack list).
 641  *
 642  * Returns one if this block should be evicted, zero otherwise. Will always
 643  * return zero when no hole has been found.
 644  */
 645 int drm_mm_scan_remove_block(struct drm_mm_node *node)
 646 {
 647         struct drm_mm *mm = node->mm;
 648         struct drm_mm_node *prev_node;
 649
 650         mm->scanned_blocks--;
 651
 652         BUG_ON(!node->scanned_block);
 653         node->scanned_block = 0;
 654
 655         prev_node = list_entry(node->node_list.prev, struct drm_mm_node,
 656                                node_list);
 657
 658         prev_node->hole_follows = node->scanned_preceeds_hole;
 659         INIT_LIST_HEAD(&node->node_list);
 660         list_add(&node->node_list, &prev_node->node_list);
 661
 662         /* Only need to check for containement because start&size for the
 663          * complete resulting free block (not just the desired part) is
 664          * stored. */
 665         if (node->start >= mm->scan_hit_start &&
 666             node->start + node->size
 667                         <= mm->scan_hit_start + mm->scan_hit_size) {
 668                 return 1;
 669         }
 670
 671         return 0;
 672 }
 673 EXPORT_SYMBOL(drm_mm_scan_remove_block);
 674
 675 int drm_mm_clean(struct drm_mm * mm)
 676 {
 677         struct list_head *head = &mm->head_node.node_list;
 678
 679         return (head->next->next == head);
 680 }
 681 EXPORT_SYMBOL(drm_mm_clean);
 682
 683 int drm_mm_init(struct drm_mm * mm, unsigned long start, unsigned long size)
 684 {
 685         INIT_LIST_HEAD(&mm->hole_stack);
 686         INIT_LIST_HEAD(&mm->unused_nodes);
 687         mm->num_unused = 0;
 688         mm->scanned_blocks = 0;
 689         spin_lock_init(&mm->unused_lock);
 690
 691         /* Clever trick to avoid a special case in the free hole tracking. */
 692         INIT_LIST_HEAD(&mm->head_node.node_list);
 693         INIT_LIST_HEAD(&mm->head_node.hole_stack);
 694         mm->head_node.hole_follows = 1;
 695         mm->head_node.scanned_block = 0;
 696         mm->head_node.scanned_prev_free = 0;
 697         mm->head_node.scanned_next_free = 0;
 698         mm->head_node.mm = mm;
 699         mm->head_node.start = start + size;
 700         mm->head_node.size = start - mm->head_node.start;
 701         list_add_tail(&mm->head_node.hole_stack, &mm->hole_stack);
 702
 703         mm->color_adjust = NULL;
 704
 705         return 0;
 706 }
 707 EXPORT_SYMBOL(drm_mm_init);
 708
 709 void drm_mm_takedown(struct drm_mm * mm)
 710 {
 711         struct drm_mm_node *entry, *next;
 712
 713         if (!list_empty(&mm->head_node.node_list)) {
 714                 DRM_ERROR("Memory manager not clean. Delaying takedown\n");
 715                 return;
 716         }
 717
 718         spin_lock(&mm->unused_lock);
 719         list_for_each_entry_safe(entry, next, &mm->unused_nodes, node_list) {
 720                 list_del(&entry->node_list);
 721                 kfree(entry);
 722                 --mm->num_unused;
 723         }
 724         spin_unlock(&mm->unused_lock);
 725
 726         BUG_ON(mm->num_unused != 0);
 727 }
 728 EXPORT_SYMBOL(drm_mm_takedown);
 729
 730 void drm_mm_debug_table(struct drm_mm *mm, const char *prefix)
 731 {
 732         struct drm_mm_node *entry;
 733         unsigned long total_used = 0, total_free = 0, total = 0;
 734         unsigned long hole_start, hole_end, hole_size;
 735
 736         hole_start = drm_mm_hole_node_start(&mm->head_node);
 737         hole_end = drm_mm_hole_node_end(&mm->head_node);
 738         hole_size = hole_end - hole_start;
 739         if (hole_size)
 740                 printk(KERN_DEBUG "%s 0x%08lx-0x%08lx: %8lu: free\n",
 741                         prefix, hole_start, hole_end,
 742                         hole_size);
 743         total_free += hole_size;
 744
 745         drm_mm_for_each_node(entry, mm) {
 746                 printk(KERN_DEBUG "%s 0x%08lx-0x%08lx: %8lu: used\n",
 747                         prefix, entry->start, entry->start + entry->size,
 748                         entry->size);
 749                 total_used += entry->size;
 750
 751                 if (entry->hole_follows) {
 752                         hole_start = drm_mm_hole_node_start(entry);
 753                         hole_end = drm_mm_hole_node_end(entry);
 754                         hole_size = hole_end - hole_start;
 755                         printk(KERN_DEBUG "%s 0x%08lx-0x%08lx: %8lu: free\n",
 756                                 prefix, hole_start, hole_end,
 757                                 hole_size);
 758                         total_free += hole_size;
 759                 }
 760         }
 761         total = total_free + total_used;
 762
 763         printk(KERN_DEBUG "%s total: %lu, used %lu free %lu\n", prefix, total,
 764                 total_used, total_free);
 765 }
 766 EXPORT_SYMBOL(drm_mm_debug_table);
 767
 768 #if defined(CONFIG_DEBUG_FS)
 769 int drm_mm_dump_table(struct seq_file *m, struct drm_mm *mm)
 770 {
 771         struct drm_mm_node *entry;
 772         unsigned long total_used = 0, total_free = 0, total = 0;
 773         unsigned long hole_start, hole_end, hole_size;
 774
 775         hole_start = drm_mm_hole_node_start(&mm->head_node);
 776         hole_end = drm_mm_hole_node_end(&mm->head_node);
 777         hole_size = hole_end - hole_start;
 778         if (hole_size)
 779                 seq_printf(m, "0x%08lx-0x%08lx: 0x%08lx: free\n",
 780                                 hole_start, hole_end, hole_size);
 781         total_free += hole_size;
 782
 783         drm_mm_for_each_node(entry, mm) {
 784                 seq_printf(m, "0x%08lx-0x%08lx: 0x%08lx: used\n",
 785                                 entry->start, entry->start + entry->size,
 786                                 entry->size);
 787                 total_used += entry->size;
 788                 if (entry->hole_follows) {
 789                         hole_start = drm_mm_hole_node_start(entry);
 790                         hole_end = drm_mm_hole_node_end(entry);
 791                         hole_size = hole_end - hole_start;
 792                         seq_printf(m, "0x%08lx-0x%08lx: 0x%08lx: free\n",
 793                                         hole_start, hole_end, hole_size);
 794                         total_free += hole_size;
 795                 }
 796         }
 797         total = total_free + total_used;
 798
 799         seq_printf(m, "total: %lu, used %lu free %lu\n", total, total_used, total_free);
 800         return 0;
 801 }
 802 EXPORT_SYMBOL(drm_mm_dump_table);
 803 #endif