/* * 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 #include #include 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: */