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