diff options
Diffstat (limited to 'drivers/staging/memrar/memrar_allocator.c')
-rw-r--r-- | drivers/staging/memrar/memrar_allocator.c | 432 |
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: -*/ |