| 1 | /* |
| 2 | * Copyright 2010-2017 Intel Corporation. |
| 3 | * |
| 4 | * This program is free software; you can redistribute it and/or modify |
| 5 | * it under the terms of the GNU General Public License, version 2, |
| 6 | * as published by the Free Software Foundation. |
| 7 | * |
| 8 | * This program is distributed in the hope that it will be useful, |
| 9 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 10 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 11 | * General Public License for more details. |
| 12 | * |
| 13 | * Disclaimer: The codes contained in these modules may be specific to |
| 14 | * the Intel Software Development Platform codenamed Knights Ferry, |
| 15 | * and the Intel product codenamed Knights Corner, and are not backward |
| 16 | * compatible with other Intel products. Additionally, Intel will NOT |
| 17 | * support the codes or instruction set in future products. |
| 18 | * |
| 19 | * Intel offers no warranty of any kind regarding the code. This code is |
| 20 | * licensed on an "AS IS" basis and Intel is not obligated to provide |
| 21 | * any support, assistance, installation, training, or other services |
| 22 | * of any kind. Intel is also not obligated to provide any updates, |
| 23 | * enhancements or extensions. Intel specifically disclaims any warranty |
| 24 | * of merchantability, non-infringement, fitness for any particular |
| 25 | * purpose, and any other warranty. |
| 26 | * |
| 27 | * Further, Intel disclaims all liability of any kind, including but |
| 28 | * not limited to liability for infringement of any proprietary rights, |
| 29 | * relating to the use of the code, even if Intel is notified of the |
| 30 | * possibility of such liability. Except as expressly stated in an Intel |
| 31 | * license agreement provided with this code and agreed upon with Intel, |
| 32 | * no license, express or implied, by estoppel or otherwise, to any |
| 33 | * intellectual property rights is granted herein. |
| 34 | */ |
| 35 | |
| 36 | /* ************************************************************************* *\ |
| 37 | generate a virtual address for a given size |
| 38 | \* ************************************************************************* */ |
| 39 | #include "mic/micscif.h" |
| 40 | |
| 41 | /* ************************************************************************* *\ |
| 42 | FUNCTION: VaGenAddress::Initialize |
| 43 | |
| 44 | DESCRIPTION: Initialize VaGenAddress to point to one node of size = range |
| 45 | \* ************************************************************************* */ |
| 46 | static int |
| 47 | va_gen_init_internal(struct va_gen_addr *addr, uint64_t range) |
| 48 | { |
| 49 | struct va_node *node; |
| 50 | int err; |
| 51 | |
| 52 | va_node_init(&addr->allocator); |
| 53 | if ((err = va_node_alloc(&addr->allocator, &addr->hole_list)) < 0) |
| 54 | goto init_err; |
| 55 | if (va_node_is_valid(addr->hole_list)) { |
| 56 | node = va_node_get(&addr->allocator, addr->hole_list); |
| 57 | node->next = invalid_va_node_index; |
| 58 | node->base = 0; |
| 59 | node->range = range; |
| 60 | } |
| 61 | addr->claims_list = invalid_va_node_index; |
| 62 | init_err: |
| 63 | return err; |
| 64 | } |
| 65 | |
| 66 | /* ************************************************************************* *\ |
| 67 | FUNCTION: VaGenAddress::Alloc |
| 68 | Allocate virtual memory by searching through free virtual memory |
| 69 | linked list for first range >= desired range. |
| 70 | |
| 71 | Note: Free list is sorted by base, we are searching for range. |
| 72 | |
| 73 | Return: Offset to allocated virtual address if successful (in pages). |
| 74 | INVALID_VA_PAGE_INDEX if failed |
| 75 | \* ************************************************************************* */ |
| 76 | static uint64_t |
| 77 | va_gen_alloc_internal(struct va_gen_addr *addr, uint64_t range) |
| 78 | { |
| 79 | //========================================================================== |
| 80 | // Search for a sufficiently large memory hole (first-fit). |
| 81 | //-------------------------------------------------------------------------- |
| 82 | |
| 83 | // Search for first available hole of sufficient size. |
| 84 | uint32_t index = addr->hole_list; |
| 85 | struct va_node *pFind; |
| 86 | // Used to handle case of an exact range match. |
| 87 | struct va_node *pPrev = 0; |
| 88 | uint64_t base; |
| 89 | |
| 90 | if (0 == range || !va_node_is_valid(addr->hole_list)) |
| 91 | return INVALID_VA_PAGE_INDEX; |
| 92 | |
| 93 | pFind = va_node_get(&addr->allocator, index); |
| 94 | |
| 95 | for ( ; ; ) { |
| 96 | if (pFind->range >= range) |
| 97 | break; |
| 98 | else { |
| 99 | index = pFind->next; |
| 100 | // No hole sufficiently large. |
| 101 | if (!va_node_is_valid(index)) |
| 102 | return INVALID_VA_PAGE_INDEX; |
| 103 | pPrev = pFind; |
| 104 | pFind = va_node_get(&addr->allocator, index); |
| 105 | } |
| 106 | } |
| 107 | |
| 108 | // Found an adequate hole. Get its base. |
| 109 | base = pFind->base; |
| 110 | |
| 111 | //============================================================================ |
| 112 | // Uncommon case: pFind->range == in_range |
| 113 | // Remove node from the hole list when exact fit. Note, could leave the |
| 114 | // hole list empty. |
| 115 | //---------------------------------------------------------------------------- |
| 116 | |
| 117 | if (pFind->range == range) { |
| 118 | // first node? |
| 119 | if (addr->hole_list == index) |
| 120 | addr->hole_list = pFind->next; |
| 121 | else { |
| 122 | BUG_ON(!pPrev); |
| 123 | pPrev->next = pFind->next; |
| 124 | } |
| 125 | va_node_free(&addr->allocator, index); |
| 126 | return base; |
| 127 | } |
| 128 | |
| 129 | //================================================================================ |
| 130 | // Shrink an existing node that is too large. |
| 131 | //-------------------------------------------------------------------------------- |
| 132 | |
| 133 | else { |
| 134 | pFind->base += range; |
| 135 | pFind->range -= range; |
| 136 | } |
| 137 | |
| 138 | return base; |
| 139 | } |
| 140 | |
| 141 | /* ************************************************************************* *\ |
| 142 | FUNCTION: VaGenAddress::FreeClaim |
| 143 | |
| 144 | DESCRIPTION: |
| 145 | Removes claimed range from the claims list. |
| 146 | \* ************************************************************************* */ |
| 147 | static void |
| 148 | va_gen_free_claim(struct va_gen_addr *addr, uint64_t base, uint64_t range) |
| 149 | { |
| 150 | struct va_node *pNode = 0; |
| 151 | struct va_node *pPrev = 0; |
| 152 | uint32_t index, new_index; |
| 153 | struct va_node *pNewNode; |
| 154 | int err; |
| 155 | |
| 156 | if (0 == range) |
| 157 | return; |
| 158 | |
| 159 | for (index = addr->claims_list; va_node_is_valid(index); index = pNode->next) { |
| 160 | pNode = va_node_get(&addr->allocator, index); |
| 161 | |
| 162 | if (pNode->base <= base && pNode->base + pNode->range >= base + range) { |
| 163 | if (pNode->base == base) { |
| 164 | pNode->base += range; |
| 165 | pNode->range -= range; |
| 166 | if (0 == pNode->range) { |
| 167 | if (pPrev) |
| 168 | pPrev->next = pNode->next; |
| 169 | else |
| 170 | addr->claims_list = pNode->next; |
| 171 | va_node_free(&addr->allocator, index); |
| 172 | } |
| 173 | } else if (pNode->base + pNode->range == base + range) { |
| 174 | pNode->range -= range; |
| 175 | } else { |
| 176 | err = va_node_alloc(&addr->allocator, &new_index); |
| 177 | BUG_ON(err < 0); |
| 178 | pNewNode = va_node_get(&addr->allocator, new_index); |
| 179 | pNewNode->base = base + range; |
| 180 | pNewNode->range = pNode->range - pNewNode->base; |
| 181 | pNewNode->next = pNode->next; |
| 182 | pNode->range = base - pNode->base; |
| 183 | pNode->next = new_index; |
| 184 | } |
| 185 | return; |
| 186 | } |
| 187 | if (pNode->base > base + range) { |
| 188 | pr_debug("Freed claim not found in the list\n"); |
| 189 | return; |
| 190 | } |
| 191 | |
| 192 | if ((pNode->base < base) ? |
| 193 | (pNode->base + pNode->range > base) : |
| 194 | (base + range > pNode->base)) { |
| 195 | pr_debug("Freed claim partially overlaps the list\n"); |
| 196 | return; |
| 197 | } |
| 198 | pPrev = pNode; |
| 199 | } |
| 200 | } |
| 201 | |
| 202 | /* ************************************************************************* *\ |
| 203 | FUNCTION: VaGenAddress::InsertAndCoalesce |
| 204 | |
| 205 | DESCRIPTION: |
| 206 | O(n) search through free list sorted by base |
| 207 | should average O(n/2), and free list should be much less than the # allocated |
| 208 | coalesce with node before/after if possible |
| 209 | 3 possible outcomes: |
| 210 | 1. freed node is inserted into list (0 deallocated) |
| 211 | 2. freed node range coalesced with existing node, |
| 212 | so freed node can be deallocated (1 deallocated) |
| 213 | 3. freed node + another node are coalesced + deallocated |
| 214 | (2 deallocated) |
| 215 | Fails if there is full or partial overlap between inserted |
| 216 | range and ranges in the list |
| 217 | |
| 218 | returns false if insert failed |
| 219 | \* ************************************************************************* */ |
| 220 | static int |
| 221 | va_gen_insert_and_coalesce(struct va_node_allocator *allocator, uint32_t *list, |
| 222 | uint64_t base, uint64_t range) |
| 223 | { |
| 224 | // search through free list, insert ordered |
| 225 | // also check for coalesce |
| 226 | uint32_t findPtr = *list; |
| 227 | uint32_t prev = *list; |
| 228 | uint64_t end_range = base + range; |
| 229 | uint32_t nextPtr, ptr; |
| 230 | struct va_node *nextNode, *node; |
| 231 | int err; |
| 232 | |
| 233 | while (va_node_is_valid(findPtr)) { |
| 234 | struct va_node *find = va_node_get(allocator, findPtr); |
| 235 | // overlap? |
| 236 | // A.start < B.start && A.end > B.start A-B==A-B A-B==B-A otherwise A-A B-B |
| 237 | // B.start < A.start && B.end > A.start B-A==B-A B-A==A-B otherwise B-B A-A |
| 238 | // => |
| 239 | // A.start < B.start ? A.end > B.start : B.end > A.start |
| 240 | |
| 241 | if ((find->base < base) ? |
| 242 | (find->base + find->range > base) : |
| 243 | (end_range > find->base)) { |
| 244 | return -1; |
| 245 | } |
| 246 | //---------------------------------------------------------- |
| 247 | // coalesce? 2 possibilities: |
| 248 | // 1. (pFind->base + pFind->range) == current.base |
| 249 | // coalesce, check next node base = endrange, |
| 250 | // coalesce with next if possible, deallocate next, exit |
| 251 | // 2. end_range == pFind->base |
| 252 | // coalesce, exit |
| 253 | if (end_range == find->base) { |
| 254 | // pr_debug("Coalesce base %lld before %lld\n", base, find->base); |
| 255 | find->base = base; |
| 256 | find->range += range; |
| 257 | return 0; |
| 258 | } else if ((find->base + find->range) == base) { |
| 259 | // pr_debug("Coalesce base %lld after %lld\n", base, find->base); |
| 260 | // leave the base unchanged |
| 261 | find->range += range; |
| 262 | // check the next node to see if it coalesces too |
| 263 | nextPtr = find->next; |
| 264 | if (va_node_is_valid(nextPtr)) { |
| 265 | nextNode = va_node_get(allocator, nextPtr); |
| 266 | // end_range is the same after prior coalesce |
| 267 | if (nextNode->base == end_range) { |
| 268 | // pr_debug("Double Coalesce index %d before %d\n", findPtr, nextPtr); |
| 269 | find->range += nextNode->range; |
| 270 | find->next = nextNode->next; |
| 271 | va_node_free(allocator, nextPtr); |
| 272 | } |
| 273 | } |
| 274 | return 0; |
| 275 | } |
| 276 | // end coalesce |
| 277 | |
| 278 | //---------------------------------------------------------- |
| 279 | // insert if found a node at a greater address |
| 280 | else if (find->base > end_range) |
| 281 | // exit loop, insert node |
| 282 | break; |
| 283 | // nothing found yet, next index |
| 284 | prev = findPtr; |
| 285 | findPtr = find->next; |
| 286 | } |
| 287 | |
| 288 | //---------------------------------------------------------- |
| 289 | // insert or append if node |
| 290 | // could be at the end or empty free list (find index = INVALID) |
| 291 | // or, next node has larger base |
| 292 | //---------------------------------------------------------- |
| 293 | err = va_node_alloc(allocator, &ptr); |
| 294 | BUG_ON(err < 0); |
| 295 | if (!va_node_is_valid(ptr)) { |
| 296 | printk(KERN_ERR "FAILED to add hole! base = %lld, range = %lld\n", base, range); |
| 297 | return 0; |
| 298 | } |
| 299 | node = va_node_get(allocator, ptr); |
| 300 | node->base = base; |
| 301 | node->range = range; |
| 302 | node->next = findPtr; |
| 303 | // First node or empty list (Alloc() can empty the list) |
| 304 | if (findPtr == *list) |
| 305 | // pr_debug("List now starts with %d\n", ptr); |
| 306 | *list = ptr; |
| 307 | else { // reached the end of the list or insertion |
| 308 | BUG_ON(!va_node_is_valid(prev)); |
| 309 | // pr_debug("Append index %d after %d\n", ptr, prev); |
| 310 | (va_node_get(allocator, prev))->next = ptr; |
| 311 | } |
| 312 | return 0; |
| 313 | } |
| 314 | |
| 315 | /* ************************************************************************* *\ |
| 316 | FUNCTION: VaGenAddress::Free |
| 317 | |
| 318 | DESCRIPTION: |
| 319 | Frees allocated Virtual Address. Inserts freed range in the list of holes |
| 320 | (available virtual addresses) |
| 321 | \* ************************************************************************* */ |
| 322 | static void |
| 323 | va_gen_free_internal(struct va_gen_addr *addr, uint64_t base, uint64_t range) |
| 324 | { |
| 325 | int result = va_gen_insert_and_coalesce(&addr->allocator, &addr->hole_list, base, range); |
| 326 | BUG_ON(result < 0); |
| 327 | } |
| 328 | |
| 329 | /* ************************************************************************* *\ |
| 330 | FUNCTION: VaGenAddress::Alloc |
| 331 | Allocate virtual memory space. |
| 332 | |
| 333 | Note: "Quick and dirty" implementation of aligned Alloc on top of |
| 334 | non-aligned Alloc. |
| 335 | |
| 336 | Return: Offset to allocated virtual address if successful (in pages). |
| 337 | INVALID_VA_PAGE_INDEX if failed |
| 338 | \* ************************************************************************* */ |
| 339 | static uint64_t |
| 340 | va_gen_alloc_aligned(struct va_gen_addr *addr, uint64_t range, uint32_t unit_align) |
| 341 | { |
| 342 | uint64_t base_address = va_gen_alloc_internal(addr, range + unit_align - 1); |
| 343 | uint64_t aligned_base = base_address; |
| 344 | if (0 == range || 0 == unit_align) |
| 345 | return INVALID_VA_PAGE_INDEX; |
| 346 | //BUG_ON(IsPowerOfTwo(in_unitAlign)); |
| 347 | |
| 348 | if (unit_align == 1 || base_address == INVALID_VA_PAGE_INDEX) |
| 349 | return base_address; |
| 350 | |
| 351 | if (aligned_base > base_address) |
| 352 | va_gen_free_internal(addr, base_address, aligned_base - base_address); |
| 353 | |
| 354 | if (aligned_base + range < base_address + unit_align - 1) |
| 355 | va_gen_free_internal(addr, aligned_base + range, |
| 356 | base_address + unit_align - 1 - aligned_base - range); |
| 357 | return aligned_base; |
| 358 | } |
| 359 | |
| 360 | /* ************************************************************************* *\ |
| 361 | FUNCTION: VaGenAddress::Claim |
| 362 | |
| 363 | DESCRIPTION: |
| 364 | Claims a SVAS range. Checks if range was claimed before; if not, records |
| 365 | the claim in the claims list |
| 366 | |
| 367 | returns false if claim failed |
| 368 | \* ************************************************************************* */ |
| 369 | static int |
| 370 | va_gen_claim_internal(struct va_gen_addr *addr, uint64_t base, uint64_t range) |
| 371 | { |
| 372 | return va_gen_insert_and_coalesce(&addr->allocator, &addr->claims_list, base, range); |
| 373 | } |
| 374 | |
| 375 | /* ************************************************************************* *\ |
| 376 | FUNCTION: VaGenAddressMutex::Alloc |
| 377 | Allocate virtual memory space. |
| 378 | |
| 379 | Note: Wrapper for unit-testable address generator to add critical |
| 380 | section and convert bytes to pages. |
| 381 | Note: Free() selects between Free[Alloc] and FreeClaim based on |
| 382 | the address range of the freed address. |
| 383 | |
| 384 | Return: Allocated virtual address if successful (in bytes) |
| 385 | INVALID_VA_GEN_ADDRESS if failed |
| 386 | \* ************************************************************************* */ |
| 387 | uint64_t |
| 388 | va_gen_alloc(struct va_gen_addr *addr, uint64_t num_bytes, uint32_t align_bytes) |
| 389 | { |
| 390 | // Convert input bytes to pages which is our unit for the address generator. |
| 391 | uint64_t num_pages = (uint64_t)(((PAGE_SIZE - 1) + num_bytes) / PAGE_SIZE); |
| 392 | uint64_t align_pages = align_bytes / PAGE_SIZE; |
| 393 | uint64_t va_page_index, ret; |
| 394 | |
| 395 | if (align_bytes < PAGE_SIZE) { |
| 396 | ret = INVALID_VA_GEN_ADDRESS; |
| 397 | WARN_ON(1); |
| 398 | goto done; |
| 399 | } |
| 400 | |
| 401 | if (num_bytes > (0xffffffffULL * PAGE_SIZE)) { |
| 402 | ret = INVALID_VA_GEN_ADDRESS; |
| 403 | WARN_ON(1); |
| 404 | goto done; |
| 405 | } |
| 406 | va_page_index = va_gen_alloc_aligned(addr, num_pages, (uint32_t)(align_pages % 0xffffffff) ); |
| 407 | |
| 408 | if (va_page_index == INVALID_VA_PAGE_INDEX) |
| 409 | return INVALID_VA_GEN_ADDRESS; |
| 410 | |
| 411 | // Convert page number to virtual address, adding base. |
| 412 | ret = va_page_index << PAGE_SHIFT; |
| 413 | ret += addr->base; |
| 414 | done: |
| 415 | return ret; |
| 416 | } |
| 417 | |
| 418 | // Claims ownership of a memory region |
| 419 | uint64_t |
| 420 | va_gen_claim(struct va_gen_addr *addr, uint64_t address, uint64_t num_bytes) |
| 421 | { |
| 422 | uint64_t va, num_pages; |
| 423 | int result; |
| 424 | |
| 425 | if (address + num_bytes > addr->base) |
| 426 | address = INVALID_VA_GEN_ADDRESS; |
| 427 | else if (address & (PAGE_SIZE - 1)) |
| 428 | // address not aligned |
| 429 | address = INVALID_VA_GEN_ADDRESS; |
| 430 | else { |
| 431 | va = (uint64_t)(address >> PAGE_SHIFT); |
| 432 | // pr_debug("%s %d (%#llx,%llx)\n", __func__, __LINE__, va, num_bytes); |
| 433 | // convert input bytes to pages, our unit for the address generator |
| 434 | num_pages = (uint64_t)(((PAGE_SIZE-1) + num_bytes) / PAGE_SIZE); |
| 435 | if ((result = va_gen_claim_internal(addr, va, num_pages)) < 0) |
| 436 | address = INVALID_VA_GEN_ADDRESS; |
| 437 | } |
| 438 | return address; |
| 439 | } |
| 440 | |
| 441 | // frees the address range so the pages may be re-assigned |
| 442 | void |
| 443 | va_gen_free(struct va_gen_addr *addr, uint64_t address, uint64_t num_bytes) |
| 444 | { |
| 445 | uint64_t va, num_pages; |
| 446 | |
| 447 | if (address >= addr->base) { |
| 448 | // convert virtual address to page number, subtracting base |
| 449 | address -= addr->base; |
| 450 | va = (uint64_t)(address >> PAGE_SHIFT); |
| 451 | // pr_debug("%s %d (%#llx,%llx)\n", __func__, __LINE__, va, num_bytes); |
| 452 | // convert input bytes to pages, our unit for the address generator |
| 453 | num_pages = (uint64_t)(((PAGE_SIZE-1) + num_bytes) / PAGE_SIZE); |
| 454 | va_gen_free_internal(addr, va, num_pages); |
| 455 | } else { |
| 456 | va = (uint64_t)(address >> PAGE_SHIFT); |
| 457 | // pr_debug("%s %d (%#llx,%llx)\n", __func__, __LINE__, va, num_bytes); |
| 458 | // convert input bytes to pages, our unit for the address generator |
| 459 | num_pages = (uint64_t)(((PAGE_SIZE-1) + num_bytes) / PAGE_SIZE); |
| 460 | va_gen_free_claim(addr, va, num_pages); |
| 461 | } |
| 462 | } |
| 463 | |
| 464 | // base and range in bytes, though internal va generator works in pages |
| 465 | int |
| 466 | va_gen_init(struct va_gen_addr *addr, uint64_t base, uint64_t range) |
| 467 | { |
| 468 | uint64_t rangeInPages = (uint64_t)(range >> PAGE_SHIFT); |
| 469 | int ret; |
| 470 | |
| 471 | if (!(ret = va_gen_init_internal(addr, rangeInPages))) |
| 472 | addr->base = base; |
| 473 | return ret; |
| 474 | } |
| 475 | |
| 476 | void |
| 477 | va_gen_destroy(struct va_gen_addr *addr) |
| 478 | { |
| 479 | va_node_destroy(&addr->allocator); |
| 480 | } |