mm/cma-best-fit.c

   1 /*
   2  * Contiguous Memory Allocator framework: Best Fit allocator
   3  * Copyright (c) 2010 by Samsung Electronics.
   4  * Written by Michal Nazarewicz (m.nazarewicz@samsung.com)
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License as
   8  * published by the Free Software Foundation; either version 2 of the
   9  * License or (at your optional) any later version of the license.
  10  */
  11
  12 #define pr_fmt(fmt) "cma: bf: " fmt
  13
  14 #ifdef CONFIG_CMA_DEBUG
  15 #  define DEBUG
  16 #endif
  17
  18 #include <linux/errno.h>       /* Error numbers */
  19 #include <linux/slab.h>        /* kmalloc() */
  20
  21 #include <linux/cma.h>         /* CMA structures */
  22
  23
  24 /************************* Data Types *************************/
  25
  26 struct cma_bf_item {
  27         struct cma_chunk ch;
  28         struct rb_node by_size;
  29 };
  30
  31 struct cma_bf_private {
  32         struct rb_root by_start_root;
  33         struct rb_root by_size_root;
  34 };
  35
  36
  37 /************************* Prototypes *************************/
  38
  39 /*
  40  * Those are only for holes.  They must be called whenever hole's
  41  * properties change but also whenever chunk becomes a hole or hole
  42  * becames a chunk.
  43  */
  44 static void __cma_bf_hole_insert_by_size(struct cma_bf_item *item);
  45 static void __cma_bf_hole_erase_by_size(struct cma_bf_item *item);
  46 static int  __must_check
  47 __cma_bf_hole_insert_by_start(struct cma_bf_item *item);
  48 static void __cma_bf_hole_erase_by_start(struct cma_bf_item *item);
  49
  50 /**
  51  * __cma_bf_hole_take - takes a chunk of memory out of a hole.
  52  * @hole:       hole to take chunk from
  53  * @size:       chunk's size
  54  * @alignment:  chunk's starting address alignment (must be power of two)
  55  *
  56  * Takes a @size bytes large chunk from hole @hole which must be able
  57  * to hold the chunk.  The "must be able" includes also alignment
  58  * constraint.
  59  *
  60  * Returns allocated item or NULL on error (if kmalloc() failed).
  61  */
  62 static struct cma_bf_item *__must_check
  63 __cma_bf_hole_take(struct cma_bf_item *hole, size_t size, dma_addr_t alignment);
  64
  65 /**
  66  * __cma_bf_hole_merge_maybe - tries to merge hole with neighbours.
  67  * @item: hole to try and merge
  68  *
  69  * Which items are preserved is undefined so you may not rely on it.
  70  */
  71 static void __cma_bf_hole_merge_maybe(struct cma_bf_item *item);
  72
  73
  74 /************************* Device API *************************/
  75
  76 int cma_bf_init(struct cma_region *reg)
  77 {
  78         struct cma_bf_private *prv;
  79         struct cma_bf_item *item;
  80
  81         prv = kzalloc(sizeof *prv, GFP_KERNEL);
  82         if (unlikely(!prv))
  83                 return -ENOMEM;
  84
  85         item = kzalloc(sizeof *item, GFP_KERNEL);
  86         if (unlikely(!item)) {
  87                 kfree(prv);
  88                 return -ENOMEM;
  89         }
  90
  91         item->ch.start = reg->start;
  92         item->ch.size  = reg->size;
  93         item->ch.reg   = reg;
  94
  95         rb_root_init(&prv->by_start_root, &item->ch.by_start);
  96         rb_root_init(&prv->by_size_root, &item->by_size);
  97
  98         reg->private_data = prv;
  99         return 0;
 100 }
 101
 102 void cma_bf_cleanup(struct cma_region *reg)
 103 {
 104         struct cma_bf_private *prv = reg->private_data;
 105         struct cma_bf_item *item =
 106                 rb_entry(prv->by_size_root.rb_node,
 107                          struct cma_bf_item, by_size);
 108
 109         /* We can assume there is only a single hole in the tree. */
 110         WARN_ON(item->by_size.rb_left || item->by_size.rb_right ||
 111                 item->ch.by_start.rb_left || item->ch.by_start.rb_right);
 112
 113         kfree(item);
 114         kfree(prv);
 115 }
 116
 117 struct cma_chunk *cma_bf_alloc(struct cma_region *reg,
 118                                size_t size, dma_addr_t alignment)
 119 {
 120         struct cma_bf_private *prv = reg->private_data;
 121         struct rb_node *node = prv->by_size_root.rb_node;
 122         struct cma_bf_item *item = NULL;
 123
 124         /* First find hole that is large enough */
 125         while (node) {
 126                 struct cma_bf_item *i =
 127                         rb_entry(node, struct cma_bf_item, by_size);
 128
 129                 if (i->ch.size < size) {
 130                         node = node->rb_right;
 131                 } else if (i->ch.size >= size) {
 132                         node = node->rb_left;
 133                         item = i;
 134                 }
 135         }
 136         if (!item)
 137                 return NULL;
 138
 139         /* Now look for items which can satisfy alignment requirements */
 140         for (;;) {
 141                 dma_addr_t start = ALIGN(item->ch.start, alignment);
 142                 dma_addr_t end   = item->ch.start + item->ch.size;
 143                 if (start < end && end - start >= size) {
 144                         item = __cma_bf_hole_take(item, size, alignment);
 145                         return likely(item) ? &item->ch : NULL;
 146                 }
 147
 148                 node = rb_next(node);
 149                 if (!node)
 150                         return NULL;
 151
 152                 item  = rb_entry(node, struct cma_bf_item, by_size);
 153         }
 154 }
 155
 156 void cma_bf_free(struct cma_chunk *chunk)
 157 {
 158         struct cma_bf_item *item = container_of(chunk, struct cma_bf_item, ch);
 159
 160         /* Add new hole */
 161         if (unlikely(__cma_bf_hole_insert_by_start(item))) {
 162                 /*
 163                  * We're screwed...  Just free the item and forget
 164                  * about it.  Things are broken beyond repair so no
 165                  * sense in trying to recover.
 166                  */
 167                 kfree(item);
 168         } else {
 169                 __cma_bf_hole_insert_by_size(item);
 170
 171                 /* Merge with prev and next sibling */
 172                 __cma_bf_hole_merge_maybe(item);
 173         }
 174 }
 175
 176
 177 /************************* Basic Tree Manipulation *************************/
 178
 179 static void __cma_bf_hole_insert_by_size(struct cma_bf_item *item)
 180 {
 181         struct cma_bf_private *prv = item->ch.reg->private_data;
 182         struct rb_node **link = &prv->by_size_root.rb_node, *parent = NULL;
 183         const typeof(item->ch.size) value = item->ch.size;
 184
 185         while (*link) {
 186                 struct cma_bf_item *i;
 187                 parent = *link;
 188                 i = rb_entry(parent, struct cma_bf_item, by_size);
 189                 link = value <= i->ch.size
 190                         ? &parent->rb_left
 191                         : &parent->rb_right;
 192         }
 193
 194         rb_link_node(&item->by_size, parent, link);
 195         rb_insert_color(&item->by_size, &prv->by_size_root);
 196 }
 197
 198 static void __cma_bf_hole_erase_by_size(struct cma_bf_item *item)
 199 {
 200         struct cma_bf_private *prv = item->ch.reg->private_data;
 201         rb_erase(&item->by_size, &prv->by_size_root);
 202 }
 203
 204 static int  __must_check
 205 __cma_bf_hole_insert_by_start(struct cma_bf_item *item)
 206 {
 207         struct cma_bf_private *prv = item->ch.reg->private_data;
 208         struct rb_node **link = &prv->by_start_root.rb_node, *parent = NULL;
 209         const typeof(item->ch.start) value = item->ch.start;
 210
 211         while (*link) {
 212                 struct cma_bf_item *i;
 213                 parent = *link;
 214                 i = rb_entry(parent, struct cma_bf_item, ch.by_start);
 215
 216                 if (WARN_ON(value == i->ch.start))
 217                         /*
 218                          * This should *never* happen.  And I mean
 219                          * *never*.  We could even BUG on it but
 220                          * hopefully things are only a bit broken,
 221                          * ie. system can still run.  We produce
 222                          * a warning and return an error.
 223                          */
 224                         return -EBUSY;
 225
 226                 link = value <= i->ch.start
 227                         ? &parent->rb_left
 228                         : &parent->rb_right;
 229         }
 230
 231         rb_link_node(&item->ch.by_start, parent, link);
 232         rb_insert_color(&item->ch.by_start, &prv->by_start_root);
 233         return 0;
 234 }
 235
 236 static void __cma_bf_hole_erase_by_start(struct cma_bf_item *item)
 237 {
 238         struct cma_bf_private *prv = item->ch.reg->private_data;
 239         rb_erase(&item->ch.by_start, &prv->by_start_root);
 240 }
 241
 242
 243 /************************* More Tree Manipulation *************************/
 244
 245 static struct cma_bf_item *__must_check
 246 __cma_bf_hole_take(struct cma_bf_item *hole, size_t size, size_t alignment)
 247 {
 248         struct cma_bf_item *item;
 249
 250         /*
 251          * There are three cases:
 252          * 1. the chunk takes the whole hole,
 253          * 2. the chunk is at the beginning or at the end of the hole, or
 254          * 3. the chunk is in the middle of the hole.
 255          */
 256
 257
 258         /* Case 1, the whole hole */
 259         if (size == hole->ch.size) {
 260                 __cma_bf_hole_erase_by_size(hole);
 261                 __cma_bf_hole_erase_by_start(hole);
 262                 return hole;
 263         }
 264
 265
 266         /* Allocate */
 267         item = kmalloc(sizeof *item, GFP_KERNEL);
 268         if (unlikely(!item))
 269                 return NULL;
 270
 271         item->ch.start = ALIGN(hole->ch.start, alignment);
 272         item->ch.size  = size;
 273
 274         /* Case 3, in the middle */
 275         if (item->ch.start != hole->ch.start
 276          && item->ch.start + item->ch.size !=
 277             hole->ch.start + hole->ch.size) {
 278                 struct cma_bf_item *tail;
 279
 280                 /*
 281                  * Space between the end of the chunk and the end of
 282                  * the region, ie. space left after the end of the
 283                  * chunk.  If this is dividable by alignment we can
 284                  * move the chunk to the end of the hole.
 285                  */
 286                 size_t left =
 287                         hole->ch.start + hole->ch.size -
 288                         (item->ch.start + item->ch.size);
 289                 if (left % alignment == 0) {
 290                         item->ch.start += left;
 291                         goto case_2;
 292                 }
 293
 294                 /*
 295                  * We are going to add a hole at the end.  This way,
 296                  * we will reduce the problem to case 2 -- the chunk
 297                  * will be at the end of the hole.
 298                  */
 299                 tail = kmalloc(sizeof *tail, GFP_KERNEL);
 300                 if (unlikely(!tail)) {
 301                         kfree(item);
 302                         return NULL;
 303                 }
 304
 305                 tail->ch.start = item->ch.start + item->ch.size;
 306                 tail->ch.size  =
 307                         hole->ch.start + hole->ch.size - tail->ch.start;
 308                 tail->ch.reg   = hole->ch.reg;
 309
 310                 if (unlikely(__cma_bf_hole_insert_by_start(tail))) {
 311                         /*
 312                          * Things are broken beyond repair...  Abort
 313                          * inserting the hole but still continue with
 314                          * allocation (seems like the best we can do).
 315                          */
 316
 317                         hole->ch.size = tail->ch.start - hole->ch.start;
 318                         kfree(tail);
 319                 } else {
 320                         __cma_bf_hole_insert_by_size(tail);
 321                         /*
 322                          * It's important that we first insert the new
 323                          * hole in the tree sorted by size and later
 324                          * reduce the size of the old hole.  We will
 325                          * update the position of the old hole in the
 326                          * rb tree in code that handles case 2.
 327                          */
 328                         hole->ch.size = tail->ch.start - hole->ch.start;
 329                 }
 330
 331                 /* Go to case 2 */
 332         }
 333
 334
 335         /* Case 2, at the beginning or at the end */
 336 case_2:
 337         /* No need to update the tree; order preserved. */
 338         if (item->ch.start == hole->ch.start)
 339                 hole->ch.start += item->ch.size;
 340
 341         /* Alter hole's size */
 342         hole->ch.size -= size;
 343         __cma_bf_hole_erase_by_size(hole);
 344         __cma_bf_hole_insert_by_size(hole);
 345
 346         return item;
 347 }
 348
 349
 350 static void __cma_bf_hole_merge_maybe(struct cma_bf_item *item)
 351 {
 352         struct cma_bf_item *prev;
 353         struct rb_node *node;
 354         int twice = 2;
 355
 356         node = rb_prev(&item->ch.by_start);
 357         if (unlikely(!node))
 358                 goto next;
 359         prev = rb_entry(node, struct cma_bf_item, ch.by_start);
 360
 361         for (;;) {
 362                 if (prev->ch.start + prev->ch.size == item->ch.start) {
 363                         /* Remove previous hole from trees */
 364                         __cma_bf_hole_erase_by_size(prev);
 365                         __cma_bf_hole_erase_by_start(prev);
 366
 367                         /* Alter this hole */
 368                         item->ch.size += prev->ch.size;
 369                         item->ch.start = prev->ch.start;
 370                         __cma_bf_hole_erase_by_size(item);
 371                         __cma_bf_hole_insert_by_size(item);
 372                         /*
 373                          * No need to update by start trees as we do
 374                          * not break sequence order
 375                          */
 376
 377                         /* Free prev hole */
 378                         kfree(prev);
 379                 }
 380
 381 next:
 382                 if (!--twice)
 383                         break;
 384
 385                 node = rb_next(&item->ch.by_start);
 386                 if (unlikely(!node))
 387                         break;
 388                 prev = item;
 389                 item = rb_entry(node, struct cma_bf_item, ch.by_start);
 390         }
 391 }
 392
 393
 394
 395 /************************* Register *************************/
 396 static int cma_bf_module_init(void)
 397 {
 398         static struct cma_allocator alloc = {
 399                 .name    = "bf",
 400                 .init    = cma_bf_init,
 401                 .cleanup = cma_bf_cleanup,
 402                 .alloc   = cma_bf_alloc,
 403                 .free    = cma_bf_free,
 404         };
 405         return cma_allocator_register(&alloc);
 406 }
 407 subsys_initcall_sync(cma_bf_module_init);