drivers/char/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 "drmP.h"
  45
  46 drm_mm_node_t *drm_mm_get_block(drm_mm_node_t * parent,
  47                                 unsigned long size, unsigned alignment)
  48 {
  49
  50         drm_mm_node_t *child;
  51
  52         if (alignment)
  53                 size += alignment - 1;
  54
  55         if (parent->size == size) {
  56                 list_del_init(&parent->fl_entry);
  57                 parent->free = 0;
  58                 return parent;
  59         } else {
  60                 child = (drm_mm_node_t *) drm_alloc(sizeof(*child), DRM_MEM_MM);
  61                 if (!child)
  62                         return NULL;
  63
  64                 INIT_LIST_HEAD(&child->ml_entry);
  65                 INIT_LIST_HEAD(&child->fl_entry);
  66
  67                 child->free = 0;
  68                 child->size = size;
  69                 child->start = parent->start;
  70
  71                 list_add_tail(&child->ml_entry, &parent->ml_entry);
  72                 parent->size -= size;
  73                 parent->start += size;
  74         }
  75         return child;
  76 }
  77
  78 /*
  79  * Put a block. Merge with the previous and / or next block if they are free.
  80  * Otherwise add to the free stack.
  81  */
  82
  83 void drm_mm_put_block(drm_mm_t * mm, drm_mm_node_t * cur)
  84 {
  85
  86         drm_mm_node_t *list_root = &mm->root_node;
  87         struct list_head *cur_head = &cur->ml_entry;
  88         struct list_head *root_head = &list_root->ml_entry;
  89         drm_mm_node_t *prev_node = NULL;
  90         drm_mm_node_t *next_node;
  91
  92         int merged = 0;
  93
  94         if (cur_head->prev != root_head) {
  95                 prev_node = list_entry(cur_head->prev, drm_mm_node_t, ml_entry);
  96                 if (prev_node->free) {
  97                         prev_node->size += cur->size;
  98                         merged = 1;
  99                 }
 100         }
 101         if (cur_head->next != root_head) {
 102                 next_node = list_entry(cur_head->next, drm_mm_node_t, ml_entry);
 103                 if (next_node->free) {
 104                         if (merged) {
 105                                 prev_node->size += next_node->size;
 106                                 list_del(&next_node->ml_entry);
 107                                 list_del(&next_node->fl_entry);
 108                                 drm_free(next_node, sizeof(*next_node),
 109                                          DRM_MEM_MM);
 110                         } else {
 111                                 next_node->size += cur->size;
 112                                 next_node->start = cur->start;
 113                                 merged = 1;
 114                         }
 115                 }
 116         }
 117         if (!merged) {
 118                 cur->free = 1;
 119                 list_add(&cur->fl_entry, &list_root->fl_entry);
 120         } else {
 121                 list_del(&cur->ml_entry);
 122                 drm_free(cur, sizeof(*cur), DRM_MEM_MM);
 123         }
 124 }
 125
 126 drm_mm_node_t *drm_mm_search_free(const drm_mm_t * mm,
 127                                   unsigned long size,
 128                                   unsigned alignment, int best_match)
 129 {
 130         struct list_head *list;
 131         const struct list_head *free_stack = &mm->root_node.fl_entry;
 132         drm_mm_node_t *entry;
 133         drm_mm_node_t *best;
 134         unsigned long best_size;
 135
 136         best = NULL;
 137         best_size = ~0UL;
 138
 139         if (alignment)
 140                 size += alignment - 1;
 141
 142         list_for_each(list, free_stack) {
 143                 entry = list_entry(list, drm_mm_node_t, fl_entry);
 144                 if (entry->size >= size) {
 145                         if (!best_match)
 146                                 return entry;
 147                         if (size < best_size) {
 148                                 best = entry;
 149                                 best_size = entry->size;
 150                         }
 151                 }
 152         }
 153
 154         return best;
 155 }
 156
 157 int drm_mm_init(drm_mm_t * mm, unsigned long start, unsigned long size)
 158 {
 159         drm_mm_node_t *child;
 160
 161         INIT_LIST_HEAD(&mm->root_node.ml_entry);
 162         INIT_LIST_HEAD(&mm->root_node.fl_entry);
 163         child = (drm_mm_node_t *) drm_alloc(sizeof(*child), DRM_MEM_MM);
 164         if (!child)
 165                 return -ENOMEM;
 166
 167         INIT_LIST_HEAD(&child->ml_entry);
 168         INIT_LIST_HEAD(&child->fl_entry);
 169
 170         child->start = start;
 171         child->size = size;
 172         child->free = 1;
 173
 174         list_add(&child->fl_entry, &mm->root_node.fl_entry);
 175         list_add(&child->ml_entry, &mm->root_node.ml_entry);
 176
 177         return 0;
 178 }
 179
 180 EXPORT_SYMBOL(drm_mm_init);
 181
 182 void drm_mm_takedown(drm_mm_t * mm)
 183 {
 184         struct list_head *bnode = mm->root_node.fl_entry.next;
 185         drm_mm_node_t *entry;
 186
 187         entry = list_entry(bnode, drm_mm_node_t, fl_entry);
 188
 189         if (entry->ml_entry.next != &mm->root_node.ml_entry ||
 190             entry->fl_entry.next != &mm->root_node.fl_entry) {
 191                 DRM_ERROR("Memory manager not clean. Delaying takedown\n");
 192                 return;
 193         }
 194
 195         list_del(&entry->fl_entry);
 196         list_del(&entry->ml_entry);
 197
 198         drm_free(entry, sizeof(*entry), DRM_MEM_MM);
 199 }
 200
 201 EXPORT_SYMBOL(drm_mm_takedown);