drivers/staging/memrar/memrar_allocator.c

   1 /*
   2  *      memrar_allocator 1.0:  An allocator for Intel RAR.
   3  *
   4  *      Copyright (C) 2010 Intel Corporation. All rights reserved.
   5  *
   6  *      This program is free software; you can redistribute it and/or
   7  *      modify it under the terms of version 2 of the GNU General
   8  *      Public License as published by the Free Software Foundation.
   9  *
  10  *      This program is distributed in the hope that it will be
  11  *      useful, but WITHOUT ANY WARRANTY; without even the implied
  12  *      warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13  *      PURPOSE.  See the GNU General Public License for more details.
  14  *      You should have received a copy of the GNU General Public
  15  *      License along with this program; if not, write to the Free
  16  *      Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  *      Boston, MA  02111-1307, USA.
  18  *      The full GNU General Public License is included in this
  19  *      distribution in the file called COPYING.
  20  *
  21  *
  22  *  ------------------------------------------------------------------
  23  *
  24  *      This simple allocator implementation provides a
  25  *      malloc()/free()-like interface for reserving space within a
  26  *      previously reserved block of memory.  It is not specific to
  27  *      any hardware, nor is it coupled with the lower level paging
  28  *      mechanism.
  29  *
  30  *      The primary goal of this implementation is to provide a means
  31  *      to partition an arbitrary block of memory without actually
  32  *      accessing the memory or incurring any hardware side-effects
  33  *      (e.g. paging).  It is, in effect, a bookkeeping mechanism for
  34  *      buffers.
  35  */
  36
  37
  38 #include "memrar_allocator.h"
  39 #include <linux/slab.h>
  40 #include <linux/bug.h>
  41 #include <linux/kernel.h>
  42
  43
  44 struct memrar_allocator *memrar_create_allocator(unsigned long base,
  45                                                  size_t capacity,
  46                                                  size_t block_size)
  47 {
  48         struct memrar_allocator *allocator  = NULL;
  49         struct memrar_address_ranges *first_node = NULL;
  50
  51         /*
  52          * Make sure the base address is aligned on a block_size
  53          * boundary.
  54          *
  55          * @todo Is this necessary?
  56          */
  57         /* base = ALIGN(base, block_size); */
  58
  59         /* Validate parameters.
  60          *
  61          * Make sure we can allocate the entire memory space.  Zero
  62          * capacity or block size are obviously invalid.
  63          */
  64         if (base == 0
  65             || capacity == 0
  66             || block_size == 0
  67             || ULONG_MAX - capacity < base
  68             || capacity < block_size)
  69                 return allocator;
  70
  71         /*
  72          * There isn't much point in creating a memory allocator that
  73          * is only capable of holding one block but we'll allow it,
  74          * and issue a diagnostic.
  75          */
  76         WARN(capacity < block_size * 2,
  77              "memrar: Only one block available to allocator.\n");
  78
  79         allocator = kmalloc(sizeof(*allocator), GFP_KERNEL);
  80
  81         if (allocator == NULL)
  82                 return allocator;
  83
  84         mutex_init(&allocator->lock);
  85         allocator->base = base;
  86
  87         /* Round the capacity down to a multiple of block_size. */
  88         allocator->capacity = (capacity / block_size) * block_size;
  89
  90         allocator->block_size = block_size;
  91
  92         allocator->largest_free_area = allocator->capacity;
  93
  94         /* Initialize the handle and free lists. */
  95         INIT_LIST_HEAD(&allocator->allocated_list.list);
  96         INIT_LIST_HEAD(&allocator->free_list.list);
  97
  98         first_node = kmalloc(sizeof(*first_node), GFP_KERNEL);
  99         if (first_node == NULL) {
 100                 kfree(allocator);
 101                 allocator = NULL;
 102         } else {
 103                 /* Full range of blocks is available. */
 104                 first_node->range.begin = base;
 105                 first_node->range.end   = base + allocator->capacity;
 106                 list_add(&first_node->list,
 107                          &allocator->free_list.list);
 108         }
 109
 110         return allocator;
 111 }
 112
 113 void memrar_destroy_allocator(struct memrar_allocator *allocator)
 114 {
 115         /*
 116          * Assume that the memory allocator lock isn't held at this
 117          * point in time.  Caller must ensure that.
 118          */
 119
 120         struct memrar_address_ranges *pos = NULL;
 121         struct memrar_address_ranges *n   = NULL;
 122
 123         if (allocator == NULL)
 124                 return;
 125
 126         mutex_lock(&allocator->lock);
 127
 128         /* Reclaim free list resources. */
 129         list_for_each_entry_safe(pos,
 130                                  n,
 131                                  &allocator->free_list.list,
 132                                  list) {
 133                 list_del(&pos->list);
 134                 kfree(pos);
 135         }
 136
 137         mutex_unlock(&allocator->lock);
 138
 139         kfree(allocator);
 140 }
 141
 142 unsigned long memrar_allocator_alloc(struct memrar_allocator *allocator,
 143                                      size_t size)
 144 {
 145         struct memrar_address_ranges *pos = NULL;
 146
 147         size_t num_blocks;
 148         unsigned long reserved_bytes;
 149
 150         /*
 151          * Address of allocated buffer.  We assume that zero is not a
 152          * valid address.
 153          */
 154         unsigned long addr = 0;
 155
 156         if (allocator == NULL || size == 0)
 157                 return addr;
 158
 159         /* Reserve enough blocks to hold the amount of bytes requested. */
 160         num_blocks = DIV_ROUND_UP(size, allocator->block_size);
 161
 162         reserved_bytes = num_blocks * allocator->block_size;
 163
 164         mutex_lock(&allocator->lock);
 165
 166         if (reserved_bytes > allocator->largest_free_area) {
 167                 mutex_unlock(&allocator->lock);
 168                 return addr;
 169         }
 170
 171         /*
 172          * Iterate through the free list to find a suitably sized
 173          * range of free contiguous memory blocks.
 174          *
 175          * We also take the opportunity to reset the size of the
 176          * largest free area size statistic.
 177          */
 178         list_for_each_entry(pos, &allocator->free_list.list, list) {
 179                 struct memrar_address_range * const fr = &pos->range;
 180                 size_t const curr_size = fr->end - fr->begin;
 181
 182                 if (curr_size >= reserved_bytes && addr == 0) {
 183                         struct memrar_address_range *range = NULL;
 184                         struct memrar_address_ranges * const new_node =
 185                                 kmalloc(sizeof(*new_node), GFP_KERNEL);
 186
 187                         if (new_node == NULL)
 188                                 break;
 189
 190                         list_add(&new_node->list,
 191                                  &allocator->allocated_list.list);
 192
 193                         /*
 194                          * Carve out area of memory from end of free
 195                          * range.
 196                          */
 197                         range        = &new_node->range;
 198                         range->end   = fr->end;
 199                         fr->end     -= reserved_bytes;
 200                         range->begin = fr->end;
 201                         addr         = range->begin;
 202
 203                         /*
 204                          * Check if largest area has decreased in
 205                          * size.  We'll need to continue scanning for
 206                          * the next largest area if it has.
 207                          */
 208                         if (curr_size == allocator->largest_free_area)
 209                                 allocator->largest_free_area -=
 210                                         reserved_bytes;
 211                         else
 212                                 break;
 213                 }
 214
 215                 /*
 216                  * Reset largest free area size statistic as needed,
 217                  * but only if we've actually allocated memory.
 218                  */
 219                 if (addr != 0
 220                     && curr_size > allocator->largest_free_area) {
 221                         allocator->largest_free_area = curr_size;
 222                         break;
 223                 }
 224         }
 225
 226         mutex_unlock(&allocator->lock);
 227
 228         return addr;
 229 }
 230
 231 long memrar_allocator_free(struct memrar_allocator *allocator,
 232                            unsigned long addr)
 233 {
 234         struct list_head *pos = NULL;
 235         struct list_head *tmp = NULL;
 236         struct list_head *dst = NULL;
 237
 238         struct memrar_address_ranges      *allocated = NULL;
 239         struct memrar_address_range const *handle    = NULL;
 240
 241         unsigned long old_end        = 0;
 242         unsigned long new_chunk_size = 0;
 243
 244         if (allocator == NULL)
 245                 return -EINVAL;
 246
 247         if (addr == 0)
 248                 return 0;  /* Ignore "free(0)". */
 249
 250         mutex_lock(&allocator->lock);
 251
 252         /* Find the corresponding handle. */
 253         list_for_each_entry(allocated,
 254                             &allocator->allocated_list.list,
 255                             list) {
 256                 if (allocated->range.begin == addr) {
 257                         handle = &allocated->range;
 258                         break;
 259                 }
 260         }
 261
 262         /* No such buffer created by this allocator. */
 263         if (handle == NULL) {
 264                 mutex_unlock(&allocator->lock);
 265                 return -EFAULT;
 266         }
 267
 268         /*
 269          * Coalesce adjacent chunks of memory if possible.
 270          *
 271          * @note This isn't full blown coalescing since we're only
 272          *       coalescing at most three chunks of memory.
 273          */
 274         list_for_each_safe(pos, tmp, &allocator->free_list.list) {
 275                 /* @todo O(n) performance.  Optimize. */
 276
 277                 struct memrar_address_range * const chunk =
 278                         &list_entry(pos,
 279                                     struct memrar_address_ranges,
 280                                     list)->range;
 281
 282                 /* Extend size of existing free adjacent chunk. */
 283                 if (chunk->end == handle->begin) {
 284                         /*
 285                          * Chunk "less than" than the one we're
 286                          * freeing is adjacent.
 287                          *
 288                          * Before:
 289                          *
 290                          *   +-----+------+
 291                          *   |chunk|handle|
 292                          *   +-----+------+
 293                          *
 294                          * After:
 295                          *
 296                          *   +------------+
 297                          *   |   chunk    |
 298                          *   +------------+
 299                          */
 300
 301                         struct memrar_address_ranges const * const next =
 302                                 list_entry(pos->next,
 303                                            struct memrar_address_ranges,
 304                                            list);
 305
 306                         chunk->end = handle->end;
 307
 308                         /*
 309                          * Now check if next free chunk is adjacent to
 310                          * the current extended free chunk.
 311                          *
 312                          * Before:
 313                          *
 314                          *   +------------+----+
 315                          *   |   chunk    |next|
 316                          *   +------------+----+
 317                          *
 318                          * After:
 319                          *
 320                          *   +-----------------+
 321                          *   |      chunk      |
 322                          *   +-----------------+
 323                          */
 324                         if (!list_is_singular(pos)
 325                             && chunk->end == next->range.begin) {
 326                                 chunk->end = next->range.end;
 327                                 list_del(pos->next);
 328                                 kfree(next);
 329                         }
 330
 331                         list_del(&allocated->list);
 332
 333                         new_chunk_size = chunk->end - chunk->begin;
 334
 335                         goto exit_memrar_free;
 336
 337                 } else if (handle->end == chunk->begin) {
 338                         /*
 339                          * Chunk "greater than" than the one we're
 340                          * freeing is adjacent.
 341                          *
 342                          *   +------+-----+
 343                          *   |handle|chunk|
 344                          *   +------+-----+
 345                          *
 346                          * After:
 347                          *
 348                          *   +------------+
 349                          *   |   chunk    |
 350                          *   +------------+
 351                          */
 352
 353                         struct memrar_address_ranges const * const prev =
 354                                 list_entry(pos->prev,
 355                                            struct memrar_address_ranges,
 356                                            list);
 357
 358                         chunk->begin = handle->begin;
 359
 360                         /*
 361                          * Now check if previous free chunk is
 362                          * adjacent to the current extended free
 363                          * chunk.
 364                          *
 365                          *
 366                          * Before:
 367                          *
 368                          *   +----+------------+
 369                          *   |prev|   chunk    |
 370                          *   +----+------------+
 371                          *
 372                          * After:
 373                          *
 374                          *   +-----------------+
 375                          *   |      chunk      |
 376                          *   +-----------------+
 377                          */
 378                         if (!list_is_singular(pos)
 379                             && prev->range.end == chunk->begin) {
 380                                 chunk->begin = prev->range.begin;
 381                                 list_del(pos->prev);
 382                                 kfree(prev);
 383                         }
 384
 385                         list_del(&allocated->list);
 386
 387                         new_chunk_size = chunk->end - chunk->begin;
 388
 389                         goto exit_memrar_free;
 390
 391                 } else if (chunk->end < handle->begin
 392                            && chunk->end > old_end) {
 393                         /* Keep track of where the entry could be
 394                          * potentially moved from the "allocated" list
 395                          * to the "free" list if coalescing doesn't
 396                          * occur, making sure the "free" list remains
 397                          * sorted.
 398                          */
 399                         old_end = chunk->end;
 400                         dst = pos;
 401                 }
 402         }
 403
 404         /*
 405          * Nothing to coalesce.
 406          *
 407          * Move the entry from the "allocated" list to the "free"
 408          * list.
 409          */
 410         list_move(&allocated->list, dst);
 411         new_chunk_size = handle->end - handle->begin;
 412         allocated = NULL;
 413
 414 exit_memrar_free:
 415
 416         if (new_chunk_size > allocator->largest_free_area)
 417                 allocator->largest_free_area = new_chunk_size;
 418
 419         mutex_unlock(&allocator->lock);
 420
 421         kfree(allocated);
 422
 423         return 0;
 424 }
 425
 426
 427
 428 /*
 429   Local Variables:
 430     c-file-style: "linux"
 431   End:
 432 */