Ossama Othman | ff13209 | 2010-03-15 16:23:56 -0700 | [diff] [blame] | 1 | /* |
| 2 | * memrar_allocator 1.0: An allocator for Intel RAR. |
| 3 | * |
| 4 | * Copyright (C) 2010 Intel Corporation. All rights reserved. |
| 5 | * |
| 6 | * This program is free software; you can redistribute it and/or |
| 7 | * modify it under the terms of version 2 of the GNU General |
| 8 | * Public License as published by the Free Software Foundation. |
| 9 | * |
| 10 | * This program is distributed in the hope that it will be |
| 11 | * useful, but WITHOUT ANY WARRANTY; without even the implied |
| 12 | * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR |
| 13 | * PURPOSE. See the GNU General Public License for more details. |
| 14 | * You should have received a copy of the GNU General Public |
| 15 | * License along with this program; if not, write to the Free |
| 16 | * Software Foundation, Inc., 59 Temple Place - Suite 330, |
| 17 | * Boston, MA 02111-1307, USA. |
| 18 | * The full GNU General Public License is included in this |
| 19 | * distribution in the file called COPYING. |
| 20 | * |
| 21 | * |
| 22 | * ------------------------------------------------------------------ |
| 23 | * |
| 24 | * This simple allocator implementation provides a |
| 25 | * malloc()/free()-like interface for reserving space within a |
| 26 | * previously reserved block of memory. It is not specific to |
| 27 | * any hardware, nor is it coupled with the lower level paging |
| 28 | * mechanism. |
| 29 | * |
| 30 | * The primary goal of this implementation is to provide a means |
| 31 | * to partition an arbitrary block of memory without actually |
| 32 | * accessing the memory or incurring any hardware side-effects |
| 33 | * (e.g. paging). It is, in effect, a bookkeeping mechanism for |
| 34 | * buffers. |
| 35 | */ |
| 36 | |
| 37 | |
| 38 | #include "memrar_allocator.h" |
| 39 | #include <linux/slab.h> |
| 40 | #include <linux/bug.h> |
| 41 | #include <linux/kernel.h> |
| 42 | |
| 43 | |
| 44 | struct memrar_allocator *memrar_create_allocator(unsigned long base, |
| 45 | size_t capacity, |
| 46 | size_t block_size) |
| 47 | { |
| 48 | struct memrar_allocator *allocator = NULL; |
| 49 | struct memrar_address_ranges *first_node = NULL; |
| 50 | |
| 51 | /* |
| 52 | * Make sure the base address is aligned on a block_size |
| 53 | * boundary. |
| 54 | * |
| 55 | * @todo Is this necessary? |
| 56 | */ |
| 57 | /* base = ALIGN(base, block_size); */ |
| 58 | |
| 59 | /* Validate parameters. |
| 60 | * |
| 61 | * Make sure we can allocate the entire memory space. Zero |
| 62 | * capacity or block size are obviously invalid. |
| 63 | */ |
| 64 | if (base == 0 |
| 65 | || capacity == 0 |
| 66 | || block_size == 0 |
| 67 | || ULONG_MAX - capacity < base |
| 68 | || capacity < block_size) |
| 69 | return allocator; |
| 70 | |
| 71 | /* |
| 72 | * There isn't much point in creating a memory allocator that |
| 73 | * is only capable of holding one block but we'll allow it, |
| 74 | * and issue a diagnostic. |
| 75 | */ |
| 76 | WARN(capacity < block_size * 2, |
| 77 | "memrar: Only one block available to allocator.\n"); |
| 78 | |
| 79 | allocator = kmalloc(sizeof(*allocator), GFP_KERNEL); |
| 80 | |
| 81 | if (allocator == NULL) |
| 82 | return allocator; |
| 83 | |
| 84 | mutex_init(&allocator->lock); |
| 85 | allocator->base = base; |
| 86 | |
| 87 | /* Round the capacity down to a multiple of block_size. */ |
| 88 | allocator->capacity = (capacity / block_size) * block_size; |
| 89 | |
| 90 | allocator->block_size = block_size; |
| 91 | |
| 92 | allocator->largest_free_area = allocator->capacity; |
| 93 | |
| 94 | /* Initialize the handle and free lists. */ |
| 95 | INIT_LIST_HEAD(&allocator->allocated_list.list); |
| 96 | INIT_LIST_HEAD(&allocator->free_list.list); |
| 97 | |
| 98 | first_node = kmalloc(sizeof(*first_node), GFP_KERNEL); |
| 99 | if (first_node == NULL) { |
| 100 | kfree(allocator); |
| 101 | allocator = NULL; |
| 102 | } else { |
| 103 | /* Full range of blocks is available. */ |
| 104 | first_node->range.begin = base; |
| 105 | first_node->range.end = base + allocator->capacity; |
| 106 | list_add(&first_node->list, |
| 107 | &allocator->free_list.list); |
| 108 | } |
| 109 | |
| 110 | return allocator; |
| 111 | } |
| 112 | |
| 113 | void memrar_destroy_allocator(struct memrar_allocator *allocator) |
| 114 | { |
| 115 | /* |
| 116 | * Assume that the memory allocator lock isn't held at this |
| 117 | * point in time. Caller must ensure that. |
| 118 | */ |
| 119 | |
| 120 | struct memrar_address_ranges *pos = NULL; |
| 121 | struct memrar_address_ranges *n = NULL; |
| 122 | |
| 123 | if (allocator == NULL) |
| 124 | return; |
| 125 | |
| 126 | mutex_lock(&allocator->lock); |
| 127 | |
| 128 | /* Reclaim free list resources. */ |
| 129 | list_for_each_entry_safe(pos, |
| 130 | n, |
| 131 | &allocator->free_list.list, |
| 132 | list) { |
| 133 | list_del(&pos->list); |
| 134 | kfree(pos); |
| 135 | } |
| 136 | |
| 137 | mutex_unlock(&allocator->lock); |
| 138 | |
| 139 | kfree(allocator); |
| 140 | } |
| 141 | |
| 142 | unsigned long memrar_allocator_alloc(struct memrar_allocator *allocator, |
| 143 | size_t size) |
| 144 | { |
| 145 | struct memrar_address_ranges *pos = NULL; |
| 146 | |
| 147 | size_t num_blocks; |
| 148 | unsigned long reserved_bytes; |
| 149 | |
| 150 | /* |
| 151 | * Address of allocated buffer. We assume that zero is not a |
| 152 | * valid address. |
| 153 | */ |
| 154 | unsigned long addr = 0; |
| 155 | |
| 156 | if (allocator == NULL || size == 0) |
| 157 | return addr; |
| 158 | |
| 159 | /* Reserve enough blocks to hold the amount of bytes requested. */ |
| 160 | num_blocks = DIV_ROUND_UP(size, allocator->block_size); |
| 161 | |
| 162 | reserved_bytes = num_blocks * allocator->block_size; |
| 163 | |
| 164 | mutex_lock(&allocator->lock); |
| 165 | |
| 166 | if (reserved_bytes > allocator->largest_free_area) { |
| 167 | mutex_unlock(&allocator->lock); |
| 168 | return addr; |
| 169 | } |
| 170 | |
| 171 | /* |
| 172 | * Iterate through the free list to find a suitably sized |
| 173 | * range of free contiguous memory blocks. |
| 174 | * |
| 175 | * We also take the opportunity to reset the size of the |
| 176 | * largest free area size statistic. |
| 177 | */ |
| 178 | list_for_each_entry(pos, &allocator->free_list.list, list) { |
| 179 | struct memrar_address_range * const fr = &pos->range; |
| 180 | size_t const curr_size = fr->end - fr->begin; |
| 181 | |
| 182 | if (curr_size >= reserved_bytes && addr == 0) { |
| 183 | struct memrar_address_range *range = NULL; |
| 184 | struct memrar_address_ranges * const new_node = |
| 185 | kmalloc(sizeof(*new_node), GFP_KERNEL); |
| 186 | |
| 187 | if (new_node == NULL) |
| 188 | break; |
| 189 | |
| 190 | list_add(&new_node->list, |
| 191 | &allocator->allocated_list.list); |
| 192 | |
| 193 | /* |
| 194 | * Carve out area of memory from end of free |
| 195 | * range. |
| 196 | */ |
| 197 | range = &new_node->range; |
| 198 | range->end = fr->end; |
| 199 | fr->end -= reserved_bytes; |
| 200 | range->begin = fr->end; |
| 201 | addr = range->begin; |
| 202 | |
| 203 | /* |
| 204 | * Check if largest area has decreased in |
| 205 | * size. We'll need to continue scanning for |
| 206 | * the next largest area if it has. |
| 207 | */ |
| 208 | if (curr_size == allocator->largest_free_area) |
| 209 | allocator->largest_free_area -= |
| 210 | reserved_bytes; |
| 211 | else |
| 212 | break; |
| 213 | } |
| 214 | |
| 215 | /* |
| 216 | * Reset largest free area size statistic as needed, |
| 217 | * but only if we've actually allocated memory. |
| 218 | */ |
| 219 | if (addr != 0 |
| 220 | && curr_size > allocator->largest_free_area) { |
| 221 | allocator->largest_free_area = curr_size; |
| 222 | break; |
| 223 | } |
| 224 | } |
| 225 | |
| 226 | mutex_unlock(&allocator->lock); |
| 227 | |
| 228 | return addr; |
| 229 | } |
| 230 | |
| 231 | long memrar_allocator_free(struct memrar_allocator *allocator, |
| 232 | unsigned long addr) |
| 233 | { |
| 234 | struct list_head *pos = NULL; |
| 235 | struct list_head *tmp = NULL; |
| 236 | struct list_head *dst = NULL; |
| 237 | |
| 238 | struct memrar_address_ranges *allocated = NULL; |
| 239 | struct memrar_address_range const *handle = NULL; |
| 240 | |
| 241 | unsigned long old_end = 0; |
| 242 | unsigned long new_chunk_size = 0; |
| 243 | |
| 244 | if (allocator == NULL) |
| 245 | return -EINVAL; |
| 246 | |
| 247 | if (addr == 0) |
| 248 | return 0; /* Ignore "free(0)". */ |
| 249 | |
| 250 | mutex_lock(&allocator->lock); |
| 251 | |
| 252 | /* Find the corresponding handle. */ |
| 253 | list_for_each_entry(allocated, |
| 254 | &allocator->allocated_list.list, |
| 255 | list) { |
| 256 | if (allocated->range.begin == addr) { |
| 257 | handle = &allocated->range; |
| 258 | break; |
| 259 | } |
| 260 | } |
| 261 | |
| 262 | /* No such buffer created by this allocator. */ |
| 263 | if (handle == NULL) { |
| 264 | mutex_unlock(&allocator->lock); |
| 265 | return -EFAULT; |
| 266 | } |
| 267 | |
| 268 | /* |
| 269 | * Coalesce adjacent chunks of memory if possible. |
| 270 | * |
| 271 | * @note This isn't full blown coalescing since we're only |
| 272 | * coalescing at most three chunks of memory. |
| 273 | */ |
| 274 | list_for_each_safe(pos, tmp, &allocator->free_list.list) { |
| 275 | /* @todo O(n) performance. Optimize. */ |
| 276 | |
| 277 | struct memrar_address_range * const chunk = |
| 278 | &list_entry(pos, |
| 279 | struct memrar_address_ranges, |
| 280 | list)->range; |
| 281 | |
| 282 | /* Extend size of existing free adjacent chunk. */ |
| 283 | if (chunk->end == handle->begin) { |
| 284 | /* |
| 285 | * Chunk "less than" than the one we're |
| 286 | * freeing is adjacent. |
| 287 | * |
| 288 | * Before: |
| 289 | * |
| 290 | * +-----+------+ |
| 291 | * |chunk|handle| |
| 292 | * +-----+------+ |
| 293 | * |
| 294 | * After: |
| 295 | * |
| 296 | * +------------+ |
| 297 | * | chunk | |
| 298 | * +------------+ |
| 299 | */ |
| 300 | |
| 301 | struct memrar_address_ranges const * const next = |
| 302 | list_entry(pos->next, |
| 303 | struct memrar_address_ranges, |
| 304 | list); |
| 305 | |
| 306 | chunk->end = handle->end; |
| 307 | |
| 308 | /* |
| 309 | * Now check if next free chunk is adjacent to |
| 310 | * the current extended free chunk. |
| 311 | * |
| 312 | * Before: |
| 313 | * |
| 314 | * +------------+----+ |
| 315 | * | chunk |next| |
| 316 | * +------------+----+ |
| 317 | * |
| 318 | * After: |
| 319 | * |
| 320 | * +-----------------+ |
| 321 | * | chunk | |
| 322 | * +-----------------+ |
| 323 | */ |
| 324 | if (!list_is_singular(pos) |
| 325 | && chunk->end == next->range.begin) { |
| 326 | chunk->end = next->range.end; |
| 327 | list_del(pos->next); |
| 328 | kfree(next); |
| 329 | } |
| 330 | |
| 331 | list_del(&allocated->list); |
| 332 | |
| 333 | new_chunk_size = chunk->end - chunk->begin; |
| 334 | |
| 335 | goto exit_memrar_free; |
| 336 | |
| 337 | } else if (handle->end == chunk->begin) { |
| 338 | /* |
| 339 | * Chunk "greater than" than the one we're |
| 340 | * freeing is adjacent. |
| 341 | * |
| 342 | * +------+-----+ |
| 343 | * |handle|chunk| |
| 344 | * +------+-----+ |
| 345 | * |
| 346 | * After: |
| 347 | * |
| 348 | * +------------+ |
| 349 | * | chunk | |
| 350 | * +------------+ |
| 351 | */ |
| 352 | |
| 353 | struct memrar_address_ranges const * const prev = |
| 354 | list_entry(pos->prev, |
| 355 | struct memrar_address_ranges, |
| 356 | list); |
| 357 | |
| 358 | chunk->begin = handle->begin; |
| 359 | |
| 360 | /* |
| 361 | * Now check if previous free chunk is |
| 362 | * adjacent to the current extended free |
| 363 | * chunk. |
| 364 | * |
| 365 | * |
| 366 | * Before: |
| 367 | * |
| 368 | * +----+------------+ |
| 369 | * |prev| chunk | |
| 370 | * +----+------------+ |
| 371 | * |
| 372 | * After: |
| 373 | * |
| 374 | * +-----------------+ |
| 375 | * | chunk | |
| 376 | * +-----------------+ |
| 377 | */ |
| 378 | if (!list_is_singular(pos) |
| 379 | && prev->range.end == chunk->begin) { |
| 380 | chunk->begin = prev->range.begin; |
| 381 | list_del(pos->prev); |
| 382 | kfree(prev); |
| 383 | } |
| 384 | |
| 385 | list_del(&allocated->list); |
| 386 | |
| 387 | new_chunk_size = chunk->end - chunk->begin; |
| 388 | |
| 389 | goto exit_memrar_free; |
| 390 | |
| 391 | } else if (chunk->end < handle->begin |
| 392 | && chunk->end > old_end) { |
| 393 | /* Keep track of where the entry could be |
| 394 | * potentially moved from the "allocated" list |
| 395 | * to the "free" list if coalescing doesn't |
| 396 | * occur, making sure the "free" list remains |
| 397 | * sorted. |
| 398 | */ |
| 399 | old_end = chunk->end; |
| 400 | dst = pos; |
| 401 | } |
| 402 | } |
| 403 | |
| 404 | /* |
| 405 | * Nothing to coalesce. |
| 406 | * |
| 407 | * Move the entry from the "allocated" list to the "free" |
| 408 | * list. |
| 409 | */ |
| 410 | list_move(&allocated->list, dst); |
| 411 | new_chunk_size = handle->end - handle->begin; |
| 412 | allocated = NULL; |
| 413 | |
| 414 | exit_memrar_free: |
| 415 | |
| 416 | if (new_chunk_size > allocator->largest_free_area) |
| 417 | allocator->largest_free_area = new_chunk_size; |
| 418 | |
| 419 | mutex_unlock(&allocator->lock); |
| 420 | |
| 421 | kfree(allocated); |
| 422 | |
| 423 | return 0; |
| 424 | } |
| 425 | |
| 426 | |
| 427 | |
| 428 | /* |
| 429 | Local Variables: |
| 430 | c-file-style: "linux" |
| 431 | End: |
| 432 | */ |