summaryrefslogtreecommitdiff
path: root/drivers/staging/memrar/memrar_allocator.c
diff options
context:
space:
mode:
Diffstat (limited to 'drivers/staging/memrar/memrar_allocator.c')
-rw-r--r--drivers/staging/memrar/memrar_allocator.c432
1 files changed, 432 insertions, 0 deletions
diff --git a/drivers/staging/memrar/memrar_allocator.c b/drivers/staging/memrar/memrar_allocator.c
new file mode 100644
index 000000000000..a4f8c5846a00
--- /dev/null
+++ b/drivers/staging/memrar/memrar_allocator.c
@@ -0,0 +1,432 @@
+/*
+ * memrar_allocator 1.0: An allocator for Intel RAR.
+ *
+ * Copyright (C) 2010 Intel Corporation. All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of version 2 of the GNU General
+ * Public License as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be
+ * useful, but WITHOUT ANY WARRANTY; without even the implied
+ * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ * You should have received a copy of the GNU General Public
+ * License along with this program; if not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ * The full GNU General Public License is included in this
+ * distribution in the file called COPYING.
+ *
+ *
+ * ------------------------------------------------------------------
+ *
+ * This simple allocator implementation provides a
+ * malloc()/free()-like interface for reserving space within a
+ * previously reserved block of memory. It is not specific to
+ * any hardware, nor is it coupled with the lower level paging
+ * mechanism.
+ *
+ * The primary goal of this implementation is to provide a means
+ * to partition an arbitrary block of memory without actually
+ * accessing the memory or incurring any hardware side-effects
+ * (e.g. paging). It is, in effect, a bookkeeping mechanism for
+ * buffers.
+ */
+
+
+#include "memrar_allocator.h"
+#include <linux/slab.h>
+#include <linux/bug.h>
+#include <linux/kernel.h>
+
+
+struct memrar_allocator *memrar_create_allocator(unsigned long base,
+ size_t capacity,
+ size_t block_size)
+{
+ struct memrar_allocator *allocator = NULL;
+ struct memrar_address_ranges *first_node = NULL;
+
+ /*
+ * Make sure the base address is aligned on a block_size
+ * boundary.
+ *
+ * @todo Is this necessary?
+ */
+ /* base = ALIGN(base, block_size); */
+
+ /* Validate parameters.
+ *
+ * Make sure we can allocate the entire memory space. Zero
+ * capacity or block size are obviously invalid.
+ */
+ if (base == 0
+ || capacity == 0
+ || block_size == 0
+ || ULONG_MAX - capacity < base
+ || capacity < block_size)
+ return allocator;
+
+ /*
+ * There isn't much point in creating a memory allocator that
+ * is only capable of holding one block but we'll allow it,
+ * and issue a diagnostic.
+ */
+ WARN(capacity < block_size * 2,
+ "memrar: Only one block available to allocator.\n");
+
+ allocator = kmalloc(sizeof(*allocator), GFP_KERNEL);
+
+ if (allocator == NULL)
+ return allocator;
+
+ mutex_init(&allocator->lock);
+ allocator->base = base;
+
+ /* Round the capacity down to a multiple of block_size. */
+ allocator->capacity = (capacity / block_size) * block_size;
+
+ allocator->block_size = block_size;
+
+ allocator->largest_free_area = allocator->capacity;
+
+ /* Initialize the handle and free lists. */
+ INIT_LIST_HEAD(&allocator->allocated_list.list);
+ INIT_LIST_HEAD(&allocator->free_list.list);
+
+ first_node = kmalloc(sizeof(*first_node), GFP_KERNEL);
+ if (first_node == NULL) {
+ kfree(allocator);
+ allocator = NULL;
+ } else {
+ /* Full range of blocks is available. */
+ first_node->range.begin = base;
+ first_node->range.end = base + allocator->capacity;
+ list_add(&first_node->list,
+ &allocator->free_list.list);
+ }
+
+ return allocator;
+}
+
+void memrar_destroy_allocator(struct memrar_allocator *allocator)
+{
+ /*
+ * Assume that the memory allocator lock isn't held at this
+ * point in time. Caller must ensure that.
+ */
+
+ struct memrar_address_ranges *pos = NULL;
+ struct memrar_address_ranges *n = NULL;
+
+ if (allocator == NULL)
+ return;
+
+ mutex_lock(&allocator->lock);
+
+ /* Reclaim free list resources. */
+ list_for_each_entry_safe(pos,
+ n,
+ &allocator->free_list.list,
+ list) {
+ list_del(&pos->list);
+ kfree(pos);
+ }
+
+ mutex_unlock(&allocator->lock);
+
+ kfree(allocator);
+}
+
+unsigned long memrar_allocator_alloc(struct memrar_allocator *allocator,
+ size_t size)
+{
+ struct memrar_address_ranges *pos = NULL;
+
+ size_t num_blocks;
+ unsigned long reserved_bytes;
+
+ /*
+ * Address of allocated buffer. We assume that zero is not a
+ * valid address.
+ */
+ unsigned long addr = 0;
+
+ if (allocator == NULL || size == 0)
+ return addr;
+
+ /* Reserve enough blocks to hold the amount of bytes requested. */
+ num_blocks = DIV_ROUND_UP(size, allocator->block_size);
+
+ reserved_bytes = num_blocks * allocator->block_size;
+
+ mutex_lock(&allocator->lock);
+
+ if (reserved_bytes > allocator->largest_free_area) {
+ mutex_unlock(&allocator->lock);
+ return addr;
+ }
+
+ /*
+ * Iterate through the free list to find a suitably sized
+ * range of free contiguous memory blocks.
+ *
+ * We also take the opportunity to reset the size of the
+ * largest free area size statistic.
+ */
+ list_for_each_entry(pos, &allocator->free_list.list, list) {
+ struct memrar_address_range * const fr = &pos->range;
+ size_t const curr_size = fr->end - fr->begin;
+
+ if (curr_size >= reserved_bytes && addr == 0) {
+ struct memrar_address_range *range = NULL;
+ struct memrar_address_ranges * const new_node =
+ kmalloc(sizeof(*new_node), GFP_KERNEL);
+
+ if (new_node == NULL)
+ break;
+
+ list_add(&new_node->list,
+ &allocator->allocated_list.list);
+
+ /*
+ * Carve out area of memory from end of free
+ * range.
+ */
+ range = &new_node->range;
+ range->end = fr->end;
+ fr->end -= reserved_bytes;
+ range->begin = fr->end;
+ addr = range->begin;
+
+ /*
+ * Check if largest area has decreased in
+ * size. We'll need to continue scanning for
+ * the next largest area if it has.
+ */
+ if (curr_size == allocator->largest_free_area)
+ allocator->largest_free_area -=
+ reserved_bytes;
+ else
+ break;
+ }
+
+ /*
+ * Reset largest free area size statistic as needed,
+ * but only if we've actually allocated memory.
+ */
+ if (addr != 0
+ && curr_size > allocator->largest_free_area) {
+ allocator->largest_free_area = curr_size;
+ break;
+ }
+ }
+
+ mutex_unlock(&allocator->lock);
+
+ return addr;
+}
+
+long memrar_allocator_free(struct memrar_allocator *allocator,
+ unsigned long addr)
+{
+ struct list_head *pos = NULL;
+ struct list_head *tmp = NULL;
+ struct list_head *dst = NULL;
+
+ struct memrar_address_ranges *allocated = NULL;
+ struct memrar_address_range const *handle = NULL;
+
+ unsigned long old_end = 0;
+ unsigned long new_chunk_size = 0;
+
+ if (allocator == NULL)
+ return -EINVAL;
+
+ if (addr == 0)
+ return 0; /* Ignore "free(0)". */
+
+ mutex_lock(&allocator->lock);
+
+ /* Find the corresponding handle. */
+ list_for_each_entry(allocated,
+ &allocator->allocated_list.list,
+ list) {
+ if (allocated->range.begin == addr) {
+ handle = &allocated->range;
+ break;
+ }
+ }
+
+ /* No such buffer created by this allocator. */
+ if (handle == NULL) {
+ mutex_unlock(&allocator->lock);
+ return -EFAULT;
+ }
+
+ /*
+ * Coalesce adjacent chunks of memory if possible.
+ *
+ * @note This isn't full blown coalescing since we're only
+ * coalescing at most three chunks of memory.
+ */
+ list_for_each_safe(pos, tmp, &allocator->free_list.list) {
+ /* @todo O(n) performance. Optimize. */
+
+ struct memrar_address_range * const chunk =
+ &list_entry(pos,
+ struct memrar_address_ranges,
+ list)->range;
+
+ /* Extend size of existing free adjacent chunk. */
+ if (chunk->end == handle->begin) {
+ /*
+ * Chunk "less than" than the one we're
+ * freeing is adjacent.
+ *
+ * Before:
+ *
+ * +-----+------+
+ * |chunk|handle|
+ * +-----+------+
+ *
+ * After:
+ *
+ * +------------+
+ * | chunk |
+ * +------------+
+ */
+
+ struct memrar_address_ranges const * const next =
+ list_entry(pos->next,
+ struct memrar_address_ranges,
+ list);
+
+ chunk->end = handle->end;
+
+ /*
+ * Now check if next free chunk is adjacent to
+ * the current extended free chunk.
+ *
+ * Before:
+ *
+ * +------------+----+
+ * | chunk |next|
+ * +------------+----+
+ *
+ * After:
+ *
+ * +-----------------+
+ * | chunk |
+ * +-----------------+
+ */
+ if (!list_is_singular(pos)
+ && chunk->end == next->range.begin) {
+ chunk->end = next->range.end;
+ list_del(pos->next);
+ kfree(next);
+ }
+
+ list_del(&allocated->list);
+
+ new_chunk_size = chunk->end - chunk->begin;
+
+ goto exit_memrar_free;
+
+ } else if (handle->end == chunk->begin) {
+ /*
+ * Chunk "greater than" than the one we're
+ * freeing is adjacent.
+ *
+ * +------+-----+
+ * |handle|chunk|
+ * +------+-----+
+ *
+ * After:
+ *
+ * +------------+
+ * | chunk |
+ * +------------+
+ */
+
+ struct memrar_address_ranges const * const prev =
+ list_entry(pos->prev,
+ struct memrar_address_ranges,
+ list);
+
+ chunk->begin = handle->begin;
+
+ /*
+ * Now check if previous free chunk is
+ * adjacent to the current extended free
+ * chunk.
+ *
+ *
+ * Before:
+ *
+ * +----+------------+
+ * |prev| chunk |
+ * +----+------------+
+ *
+ * After:
+ *
+ * +-----------------+
+ * | chunk |
+ * +-----------------+
+ */
+ if (!list_is_singular(pos)
+ && prev->range.end == chunk->begin) {
+ chunk->begin = prev->range.begin;
+ list_del(pos->prev);
+ kfree(prev);
+ }
+
+ list_del(&allocated->list);
+
+ new_chunk_size = chunk->end - chunk->begin;
+
+ goto exit_memrar_free;
+
+ } else if (chunk->end < handle->begin
+ && chunk->end > old_end) {
+ /* Keep track of where the entry could be
+ * potentially moved from the "allocated" list
+ * to the "free" list if coalescing doesn't
+ * occur, making sure the "free" list remains
+ * sorted.
+ */
+ old_end = chunk->end;
+ dst = pos;
+ }
+ }
+
+ /*
+ * Nothing to coalesce.
+ *
+ * Move the entry from the "allocated" list to the "free"
+ * list.
+ */
+ list_move(&allocated->list, dst);
+ new_chunk_size = handle->end - handle->begin;
+ allocated = NULL;
+
+exit_memrar_free:
+
+ if (new_chunk_size > allocator->largest_free_area)
+ allocator->largest_free_area = new_chunk_size;
+
+ mutex_unlock(&allocator->lock);
+
+ kfree(allocated);
+
+ return 0;
+}
+
+
+
+/*
+ Local Variables:
+ c-file-style: "linux"
+ End:
+*/
generated by cgit v1.2.3 (git 2.0.4) at 2024-05-24 20:34:25 +0000