summaryrefslogtreecommitdiffstats
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, 0 insertions, 432 deletions
diff --git a/drivers/staging/memrar/memrar_allocator.c b/drivers/staging/memrar/memrar_allocator.c
deleted file mode 100644
index a4f8c58..0000000
--- a/drivers/staging/memrar/memrar_allocator.c
+++ /dev/null
@@ -1,432 +0,0 @@
-/*
- * 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:
-*/
OpenPOWER on IntegriCloud