1 /* 2 * Copyright © 2006-2009, Intel Corporation. 3 * 4 * This program is free software; you can redistribute it and/or modify it 5 * under the terms and conditions of the GNU General Public License, 6 * version 2, as published by the Free Software Foundation. 7 * 8 * This program is distributed in the hope it will be useful, but WITHOUT 9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 11 * more details. 12 * 13 * You should have received a copy of the GNU General Public License along with 14 * this program; if not, write to the Free Software Foundation, Inc., 59 Temple 15 * Place - Suite 330, Boston, MA 02111-1307 USA. 16 * 17 * Author: Anil S Keshavamurthy <anil.s.keshavamurthy@intel.com> 18 */ 19 20 #include <linux/iova.h> 21 #include <linux/module.h> 22 #include <linux/slab.h> 23 #include <linux/smp.h> 24 #include <linux/bitops.h> 25 26 static bool iova_rcache_insert(struct iova_domain *iovad, 27 unsigned long pfn, 28 unsigned long size); 29 static unsigned long iova_rcache_get(struct iova_domain *iovad, 30 unsigned long size, 31 unsigned long limit_pfn); 32 static void init_iova_rcaches(struct iova_domain *iovad); 33 static void free_iova_rcaches(struct iova_domain *iovad); 34 35 void 36 init_iova_domain(struct iova_domain *iovad, unsigned long granule, 37 unsigned long start_pfn, unsigned long pfn_32bit) 38 { 39 /* 40 * IOVA granularity will normally be equal to the smallest 41 * supported IOMMU page size; both *must* be capable of 42 * representing individual CPU pages exactly. 43 */ 44 BUG_ON((granule > PAGE_SIZE) || !is_power_of_2(granule)); 45 46 spin_lock_init(&iovad->iova_rbtree_lock); 47 iovad->rbroot = RB_ROOT; 48 iovad->cached32_node = NULL; 49 iovad->granule = granule; 50 iovad->start_pfn = start_pfn; 51 iovad->dma_32bit_pfn = pfn_32bit; 52 init_iova_rcaches(iovad); 53 } 54 EXPORT_SYMBOL_GPL(init_iova_domain); 55 56 static struct rb_node * 57 __get_cached_rbnode(struct iova_domain *iovad, unsigned long *limit_pfn) 58 { 59 if ((*limit_pfn > iovad->dma_32bit_pfn) || 60 (iovad->cached32_node == NULL)) 61 return rb_last(&iovad->rbroot); 62 else { 63 struct rb_node *prev_node = rb_prev(iovad->cached32_node); 64 struct iova *curr_iova = 65 container_of(iovad->cached32_node, struct iova, node); 66 *limit_pfn = curr_iova->pfn_lo - 1; 67 return prev_node; 68 } 69 } 70 71 static void 72 __cached_rbnode_insert_update(struct iova_domain *iovad, 73 unsigned long limit_pfn, struct iova *new) 74 { 75 if (limit_pfn != iovad->dma_32bit_pfn) 76 return; 77 iovad->cached32_node = &new->node; 78 } 79 80 static void 81 __cached_rbnode_delete_update(struct iova_domain *iovad, struct iova *free) 82 { 83 struct iova *cached_iova; 84 struct rb_node *curr; 85 86 if (!iovad->cached32_node) 87 return; 88 curr = iovad->cached32_node; 89 cached_iova = container_of(curr, struct iova, node); 90 91 if (free->pfn_lo >= cached_iova->pfn_lo) { 92 struct rb_node *node = rb_next(&free->node); 93 struct iova *iova = container_of(node, struct iova, node); 94 95 /* only cache if it's below 32bit pfn */ 96 if (node && iova->pfn_lo < iovad->dma_32bit_pfn) 97 iovad->cached32_node = node; 98 else 99 iovad->cached32_node = NULL; 100 } 101 } 102 103 /* 104 * Computes the padding size required, to make the start address 105 * naturally aligned on the power-of-two order of its size 106 */ 107 static unsigned int 108 iova_get_pad_size(unsigned int size, unsigned int limit_pfn) 109 { 110 return (limit_pfn + 1 - size) & (__roundup_pow_of_two(size) - 1); 111 } 112 113 static int __alloc_and_insert_iova_range(struct iova_domain *iovad, 114 unsigned long size, unsigned long limit_pfn, 115 struct iova *new, bool size_aligned) 116 { 117 struct rb_node *prev, *curr = NULL; 118 unsigned long flags; 119 unsigned long saved_pfn; 120 unsigned int pad_size = 0; 121 122 /* Walk the tree backwards */ 123 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags); 124 saved_pfn = limit_pfn; 125 curr = __get_cached_rbnode(iovad, &limit_pfn); 126 prev = curr; 127 while (curr) { 128 struct iova *curr_iova = container_of(curr, struct iova, node); 129 130 if (limit_pfn < curr_iova->pfn_lo) 131 goto move_left; 132 else if (limit_pfn < curr_iova->pfn_hi) 133 goto adjust_limit_pfn; 134 else { 135 if (size_aligned) 136 pad_size = iova_get_pad_size(size, limit_pfn); 137 if ((curr_iova->pfn_hi + size + pad_size) <= limit_pfn) 138 break; /* found a free slot */ 139 } 140 adjust_limit_pfn: 141 limit_pfn = curr_iova->pfn_lo - 1; 142 move_left: 143 prev = curr; 144 curr = rb_prev(curr); 145 } 146 147 if (!curr) { 148 if (size_aligned) 149 pad_size = iova_get_pad_size(size, limit_pfn); 150 if ((iovad->start_pfn + size + pad_size) > limit_pfn) { 151 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); 152 return -ENOMEM; 153 } 154 } 155 156 /* pfn_lo will point to size aligned address if size_aligned is set */ 157 new->pfn_lo = limit_pfn - (size + pad_size) + 1; 158 new->pfn_hi = new->pfn_lo + size - 1; 159 160 /* Insert the new_iova into domain rbtree by holding writer lock */ 161 /* Add new node and rebalance tree. */ 162 { 163 struct rb_node **entry, *parent = NULL; 164 165 /* If we have 'prev', it's a valid place to start the 166 insertion. Otherwise, start from the root. */ 167 if (prev) 168 entry = &prev; 169 else 170 entry = &iovad->rbroot.rb_node; 171 172 /* Figure out where to put new node */ 173 while (*entry) { 174 struct iova *this = container_of(*entry, 175 struct iova, node); 176 parent = *entry; 177 178 if (new->pfn_lo < this->pfn_lo) 179 entry = &((*entry)->rb_left); 180 else if (new->pfn_lo > this->pfn_lo) 181 entry = &((*entry)->rb_right); 182 else 183 BUG(); /* this should not happen */ 184 } 185 186 /* Add new node and rebalance tree. */ 187 rb_link_node(&new->node, parent, entry); 188 rb_insert_color(&new->node, &iovad->rbroot); 189 } 190 __cached_rbnode_insert_update(iovad, saved_pfn, new); 191 192 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); 193 194 195 return 0; 196 } 197 198 static void 199 iova_insert_rbtree(struct rb_root *root, struct iova *iova) 200 { 201 struct rb_node **new = &(root->rb_node), *parent = NULL; 202 /* Figure out where to put new node */ 203 while (*new) { 204 struct iova *this = container_of(*new, struct iova, node); 205 206 parent = *new; 207 208 if (iova->pfn_lo < this->pfn_lo) 209 new = &((*new)->rb_left); 210 else if (iova->pfn_lo > this->pfn_lo) 211 new = &((*new)->rb_right); 212 else 213 BUG(); /* this should not happen */ 214 } 215 /* Add new node and rebalance tree. */ 216 rb_link_node(&iova->node, parent, new); 217 rb_insert_color(&iova->node, root); 218 } 219 220 static struct kmem_cache *iova_cache; 221 static unsigned int iova_cache_users; 222 static DEFINE_MUTEX(iova_cache_mutex); 223 224 struct iova *alloc_iova_mem(void) 225 { 226 return kmem_cache_alloc(iova_cache, GFP_ATOMIC); 227 } 228 EXPORT_SYMBOL(alloc_iova_mem); 229 230 void free_iova_mem(struct iova *iova) 231 { 232 kmem_cache_free(iova_cache, iova); 233 } 234 EXPORT_SYMBOL(free_iova_mem); 235 236 int iova_cache_get(void) 237 { 238 mutex_lock(&iova_cache_mutex); 239 if (!iova_cache_users) { 240 iova_cache = kmem_cache_create( 241 "iommu_iova", sizeof(struct iova), 0, 242 SLAB_HWCACHE_ALIGN, NULL); 243 if (!iova_cache) { 244 mutex_unlock(&iova_cache_mutex); 245 printk(KERN_ERR "Couldn't create iova cache\n"); 246 return -ENOMEM; 247 } 248 } 249 250 iova_cache_users++; 251 mutex_unlock(&iova_cache_mutex); 252 253 return 0; 254 } 255 EXPORT_SYMBOL_GPL(iova_cache_get); 256 257 void iova_cache_put(void) 258 { 259 mutex_lock(&iova_cache_mutex); 260 if (WARN_ON(!iova_cache_users)) { 261 mutex_unlock(&iova_cache_mutex); 262 return; 263 } 264 iova_cache_users--; 265 if (!iova_cache_users) 266 kmem_cache_destroy(iova_cache); 267 mutex_unlock(&iova_cache_mutex); 268 } 269 EXPORT_SYMBOL_GPL(iova_cache_put); 270 271 /** 272 * alloc_iova - allocates an iova 273 * @iovad: - iova domain in question 274 * @size: - size of page frames to allocate 275 * @limit_pfn: - max limit address 276 * @size_aligned: - set if size_aligned address range is required 277 * This function allocates an iova in the range iovad->start_pfn to limit_pfn, 278 * searching top-down from limit_pfn to iovad->start_pfn. If the size_aligned 279 * flag is set then the allocated address iova->pfn_lo will be naturally 280 * aligned on roundup_power_of_two(size). 281 */ 282 struct iova * 283 alloc_iova(struct iova_domain *iovad, unsigned long size, 284 unsigned long limit_pfn, 285 bool size_aligned) 286 { 287 struct iova *new_iova; 288 int ret; 289 290 new_iova = alloc_iova_mem(); 291 if (!new_iova) 292 return NULL; 293 294 ret = __alloc_and_insert_iova_range(iovad, size, limit_pfn, 295 new_iova, size_aligned); 296 297 if (ret) { 298 free_iova_mem(new_iova); 299 return NULL; 300 } 301 302 return new_iova; 303 } 304 EXPORT_SYMBOL_GPL(alloc_iova); 305 306 static struct iova * 307 private_find_iova(struct iova_domain *iovad, unsigned long pfn) 308 { 309 struct rb_node *node = iovad->rbroot.rb_node; 310 311 assert_spin_locked(&iovad->iova_rbtree_lock); 312 313 while (node) { 314 struct iova *iova = container_of(node, struct iova, node); 315 316 /* If pfn falls within iova's range, return iova */ 317 if ((pfn >= iova->pfn_lo) && (pfn <= iova->pfn_hi)) { 318 return iova; 319 } 320 321 if (pfn < iova->pfn_lo) 322 node = node->rb_left; 323 else if (pfn > iova->pfn_lo) 324 node = node->rb_right; 325 } 326 327 return NULL; 328 } 329 330 static void private_free_iova(struct iova_domain *iovad, struct iova *iova) 331 { 332 assert_spin_locked(&iovad->iova_rbtree_lock); 333 __cached_rbnode_delete_update(iovad, iova); 334 rb_erase(&iova->node, &iovad->rbroot); 335 free_iova_mem(iova); 336 } 337 338 /** 339 * find_iova - finds an iova for a given pfn 340 * @iovad: - iova domain in question. 341 * @pfn: - page frame number 342 * This function finds and returns an iova belonging to the 343 * given doamin which matches the given pfn. 344 */ 345 struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn) 346 { 347 unsigned long flags; 348 struct iova *iova; 349 350 /* Take the lock so that no other thread is manipulating the rbtree */ 351 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags); 352 iova = private_find_iova(iovad, pfn); 353 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); 354 return iova; 355 } 356 EXPORT_SYMBOL_GPL(find_iova); 357 358 /** 359 * __free_iova - frees the given iova 360 * @iovad: iova domain in question. 361 * @iova: iova in question. 362 * Frees the given iova belonging to the giving domain 363 */ 364 void 365 __free_iova(struct iova_domain *iovad, struct iova *iova) 366 { 367 unsigned long flags; 368 369 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags); 370 private_free_iova(iovad, iova); 371 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); 372 } 373 EXPORT_SYMBOL_GPL(__free_iova); 374 375 /** 376 * free_iova - finds and frees the iova for a given pfn 377 * @iovad: - iova domain in question. 378 * @pfn: - pfn that is allocated previously 379 * This functions finds an iova for a given pfn and then 380 * frees the iova from that domain. 381 */ 382 void 383 free_iova(struct iova_domain *iovad, unsigned long pfn) 384 { 385 struct iova *iova = find_iova(iovad, pfn); 386 387 if (iova) 388 __free_iova(iovad, iova); 389 390 } 391 EXPORT_SYMBOL_GPL(free_iova); 392 393 /** 394 * alloc_iova_fast - allocates an iova from rcache 395 * @iovad: - iova domain in question 396 * @size: - size of page frames to allocate 397 * @limit_pfn: - max limit address 398 * This function tries to satisfy an iova allocation from the rcache, 399 * and falls back to regular allocation on failure. 400 */ 401 unsigned long 402 alloc_iova_fast(struct iova_domain *iovad, unsigned long size, 403 unsigned long limit_pfn) 404 { 405 bool flushed_rcache = false; 406 unsigned long iova_pfn; 407 struct iova *new_iova; 408 409 iova_pfn = iova_rcache_get(iovad, size, limit_pfn); 410 if (iova_pfn) 411 return iova_pfn; 412 413 retry: 414 new_iova = alloc_iova(iovad, size, limit_pfn, true); 415 if (!new_iova) { 416 unsigned int cpu; 417 418 if (flushed_rcache) 419 return 0; 420 421 /* Try replenishing IOVAs by flushing rcache. */ 422 flushed_rcache = true; 423 preempt_disable(); 424 for_each_online_cpu(cpu) 425 free_cpu_cached_iovas(cpu, iovad); 426 preempt_enable(); 427 goto retry; 428 } 429 430 return new_iova->pfn_lo; 431 } 432 EXPORT_SYMBOL_GPL(alloc_iova_fast); 433 434 /** 435 * free_iova_fast - free iova pfn range into rcache 436 * @iovad: - iova domain in question. 437 * @pfn: - pfn that is allocated previously 438 * @size: - # of pages in range 439 * This functions frees an iova range by trying to put it into the rcache, 440 * falling back to regular iova deallocation via free_iova() if this fails. 441 */ 442 void 443 free_iova_fast(struct iova_domain *iovad, unsigned long pfn, unsigned long size) 444 { 445 if (iova_rcache_insert(iovad, pfn, size)) 446 return; 447 448 free_iova(iovad, pfn); 449 } 450 EXPORT_SYMBOL_GPL(free_iova_fast); 451 452 /** 453 * put_iova_domain - destroys the iova doamin 454 * @iovad: - iova domain in question. 455 * All the iova's in that domain are destroyed. 456 */ 457 void put_iova_domain(struct iova_domain *iovad) 458 { 459 struct rb_node *node; 460 unsigned long flags; 461 462 free_iova_rcaches(iovad); 463 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags); 464 node = rb_first(&iovad->rbroot); 465 while (node) { 466 struct iova *iova = container_of(node, struct iova, node); 467 468 rb_erase(node, &iovad->rbroot); 469 free_iova_mem(iova); 470 node = rb_first(&iovad->rbroot); 471 } 472 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); 473 } 474 EXPORT_SYMBOL_GPL(put_iova_domain); 475 476 static int 477 __is_range_overlap(struct rb_node *node, 478 unsigned long pfn_lo, unsigned long pfn_hi) 479 { 480 struct iova *iova = container_of(node, struct iova, node); 481 482 if ((pfn_lo <= iova->pfn_hi) && (pfn_hi >= iova->pfn_lo)) 483 return 1; 484 return 0; 485 } 486 487 static inline struct iova * 488 alloc_and_init_iova(unsigned long pfn_lo, unsigned long pfn_hi) 489 { 490 struct iova *iova; 491 492 iova = alloc_iova_mem(); 493 if (iova) { 494 iova->pfn_lo = pfn_lo; 495 iova->pfn_hi = pfn_hi; 496 } 497 498 return iova; 499 } 500 501 static struct iova * 502 __insert_new_range(struct iova_domain *iovad, 503 unsigned long pfn_lo, unsigned long pfn_hi) 504 { 505 struct iova *iova; 506 507 iova = alloc_and_init_iova(pfn_lo, pfn_hi); 508 if (iova) 509 iova_insert_rbtree(&iovad->rbroot, iova); 510 511 return iova; 512 } 513 514 static void 515 __adjust_overlap_range(struct iova *iova, 516 unsigned long *pfn_lo, unsigned long *pfn_hi) 517 { 518 if (*pfn_lo < iova->pfn_lo) 519 iova->pfn_lo = *pfn_lo; 520 if (*pfn_hi > iova->pfn_hi) 521 *pfn_lo = iova->pfn_hi + 1; 522 } 523 524 /** 525 * reserve_iova - reserves an iova in the given range 526 * @iovad: - iova domain pointer 527 * @pfn_lo: - lower page frame address 528 * @pfn_hi:- higher pfn adderss 529 * This function allocates reserves the address range from pfn_lo to pfn_hi so 530 * that this address is not dished out as part of alloc_iova. 531 */ 532 struct iova * 533 reserve_iova(struct iova_domain *iovad, 534 unsigned long pfn_lo, unsigned long pfn_hi) 535 { 536 struct rb_node *node; 537 unsigned long flags; 538 struct iova *iova; 539 unsigned int overlap = 0; 540 541 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags); 542 for (node = rb_first(&iovad->rbroot); node; node = rb_next(node)) { 543 if (__is_range_overlap(node, pfn_lo, pfn_hi)) { 544 iova = container_of(node, struct iova, node); 545 __adjust_overlap_range(iova, &pfn_lo, &pfn_hi); 546 if ((pfn_lo >= iova->pfn_lo) && 547 (pfn_hi <= iova->pfn_hi)) 548 goto finish; 549 overlap = 1; 550 551 } else if (overlap) 552 break; 553 } 554 555 /* We are here either because this is the first reserver node 556 * or need to insert remaining non overlap addr range 557 */ 558 iova = __insert_new_range(iovad, pfn_lo, pfn_hi); 559 finish: 560 561 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); 562 return iova; 563 } 564 EXPORT_SYMBOL_GPL(reserve_iova); 565 566 /** 567 * copy_reserved_iova - copies the reserved between domains 568 * @from: - source doamin from where to copy 569 * @to: - destination domin where to copy 570 * This function copies reserved iova's from one doamin to 571 * other. 572 */ 573 void 574 copy_reserved_iova(struct iova_domain *from, struct iova_domain *to) 575 { 576 unsigned long flags; 577 struct rb_node *node; 578 579 spin_lock_irqsave(&from->iova_rbtree_lock, flags); 580 for (node = rb_first(&from->rbroot); node; node = rb_next(node)) { 581 struct iova *iova = container_of(node, struct iova, node); 582 struct iova *new_iova; 583 584 new_iova = reserve_iova(to, iova->pfn_lo, iova->pfn_hi); 585 if (!new_iova) 586 printk(KERN_ERR "Reserve iova range %lx@%lx failed\n", 587 iova->pfn_lo, iova->pfn_lo); 588 } 589 spin_unlock_irqrestore(&from->iova_rbtree_lock, flags); 590 } 591 EXPORT_SYMBOL_GPL(copy_reserved_iova); 592 593 struct iova * 594 split_and_remove_iova(struct iova_domain *iovad, struct iova *iova, 595 unsigned long pfn_lo, unsigned long pfn_hi) 596 { 597 unsigned long flags; 598 struct iova *prev = NULL, *next = NULL; 599 600 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags); 601 if (iova->pfn_lo < pfn_lo) { 602 prev = alloc_and_init_iova(iova->pfn_lo, pfn_lo - 1); 603 if (prev == NULL) 604 goto error; 605 } 606 if (iova->pfn_hi > pfn_hi) { 607 next = alloc_and_init_iova(pfn_hi + 1, iova->pfn_hi); 608 if (next == NULL) 609 goto error; 610 } 611 612 __cached_rbnode_delete_update(iovad, iova); 613 rb_erase(&iova->node, &iovad->rbroot); 614 615 if (prev) { 616 iova_insert_rbtree(&iovad->rbroot, prev); 617 iova->pfn_lo = pfn_lo; 618 } 619 if (next) { 620 iova_insert_rbtree(&iovad->rbroot, next); 621 iova->pfn_hi = pfn_hi; 622 } 623 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); 624 625 return iova; 626 627 error: 628 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); 629 if (prev) 630 free_iova_mem(prev); 631 return NULL; 632 } 633 634 /* 635 * Magazine caches for IOVA ranges. For an introduction to magazines, 636 * see the USENIX 2001 paper "Magazines and Vmem: Extending the Slab 637 * Allocator to Many CPUs and Arbitrary Resources" by Bonwick and Adams. 638 * For simplicity, we use a static magazine size and don't implement the 639 * dynamic size tuning described in the paper. 640 */ 641 642 #define IOVA_MAG_SIZE 128 643 644 struct iova_magazine { 645 unsigned long size; 646 unsigned long pfns[IOVA_MAG_SIZE]; 647 }; 648 649 struct iova_cpu_rcache { 650 spinlock_t lock; 651 struct iova_magazine *loaded; 652 struct iova_magazine *prev; 653 }; 654 655 static struct iova_magazine *iova_magazine_alloc(gfp_t flags) 656 { 657 return kzalloc(sizeof(struct iova_magazine), flags); 658 } 659 660 static void iova_magazine_free(struct iova_magazine *mag) 661 { 662 kfree(mag); 663 } 664 665 static void 666 iova_magazine_free_pfns(struct iova_magazine *mag, struct iova_domain *iovad) 667 { 668 unsigned long flags; 669 int i; 670 671 if (!mag) 672 return; 673 674 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags); 675 676 for (i = 0 ; i < mag->size; ++i) { 677 struct iova *iova = private_find_iova(iovad, mag->pfns[i]); 678 679 BUG_ON(!iova); 680 private_free_iova(iovad, iova); 681 } 682 683 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); 684 685 mag->size = 0; 686 } 687 688 static bool iova_magazine_full(struct iova_magazine *mag) 689 { 690 return (mag && mag->size == IOVA_MAG_SIZE); 691 } 692 693 static bool iova_magazine_empty(struct iova_magazine *mag) 694 { 695 return (!mag || mag->size == 0); 696 } 697 698 static unsigned long iova_magazine_pop(struct iova_magazine *mag, 699 unsigned long limit_pfn) 700 { 701 BUG_ON(iova_magazine_empty(mag)); 702 703 if (mag->pfns[mag->size - 1] >= limit_pfn) 704 return 0; 705 706 return mag->pfns[--mag->size]; 707 } 708 709 static void iova_magazine_push(struct iova_magazine *mag, unsigned long pfn) 710 { 711 BUG_ON(iova_magazine_full(mag)); 712 713 mag->pfns[mag->size++] = pfn; 714 } 715 716 static void init_iova_rcaches(struct iova_domain *iovad) 717 { 718 struct iova_cpu_rcache *cpu_rcache; 719 struct iova_rcache *rcache; 720 unsigned int cpu; 721 int i; 722 723 for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) { 724 rcache = &iovad->rcaches[i]; 725 spin_lock_init(&rcache->lock); 726 rcache->depot_size = 0; 727 rcache->cpu_rcaches = __alloc_percpu(sizeof(*cpu_rcache), cache_line_size()); 728 if (WARN_ON(!rcache->cpu_rcaches)) 729 continue; 730 for_each_possible_cpu(cpu) { 731 cpu_rcache = per_cpu_ptr(rcache->cpu_rcaches, cpu); 732 spin_lock_init(&cpu_rcache->lock); 733 cpu_rcache->loaded = iova_magazine_alloc(GFP_KERNEL); 734 cpu_rcache->prev = iova_magazine_alloc(GFP_KERNEL); 735 } 736 } 737 } 738 739 /* 740 * Try inserting IOVA range starting with 'iova_pfn' into 'rcache', and 741 * return true on success. Can fail if rcache is full and we can't free 742 * space, and free_iova() (our only caller) will then return the IOVA 743 * range to the rbtree instead. 744 */ 745 static bool __iova_rcache_insert(struct iova_domain *iovad, 746 struct iova_rcache *rcache, 747 unsigned long iova_pfn) 748 { 749 struct iova_magazine *mag_to_free = NULL; 750 struct iova_cpu_rcache *cpu_rcache; 751 bool can_insert = false; 752 unsigned long flags; 753 754 cpu_rcache = get_cpu_ptr(rcache->cpu_rcaches); 755 spin_lock_irqsave(&cpu_rcache->lock, flags); 756 757 if (!iova_magazine_full(cpu_rcache->loaded)) { 758 can_insert = true; 759 } else if (!iova_magazine_full(cpu_rcache->prev)) { 760 swap(cpu_rcache->prev, cpu_rcache->loaded); 761 can_insert = true; 762 } else { 763 struct iova_magazine *new_mag = iova_magazine_alloc(GFP_ATOMIC); 764 765 if (new_mag) { 766 spin_lock(&rcache->lock); 767 if (rcache->depot_size < MAX_GLOBAL_MAGS) { 768 rcache->depot[rcache->depot_size++] = 769 cpu_rcache->loaded; 770 } else { 771 mag_to_free = cpu_rcache->loaded; 772 } 773 spin_unlock(&rcache->lock); 774 775 cpu_rcache->loaded = new_mag; 776 can_insert = true; 777 } 778 } 779 780 if (can_insert) 781 iova_magazine_push(cpu_rcache->loaded, iova_pfn); 782 783 spin_unlock_irqrestore(&cpu_rcache->lock, flags); 784 put_cpu_ptr(rcache->cpu_rcaches); 785 786 if (mag_to_free) { 787 iova_magazine_free_pfns(mag_to_free, iovad); 788 iova_magazine_free(mag_to_free); 789 } 790 791 return can_insert; 792 } 793 794 static bool iova_rcache_insert(struct iova_domain *iovad, unsigned long pfn, 795 unsigned long size) 796 { 797 unsigned int log_size = order_base_2(size); 798 799 if (log_size >= IOVA_RANGE_CACHE_MAX_SIZE) 800 return false; 801 802 return __iova_rcache_insert(iovad, &iovad->rcaches[log_size], pfn); 803 } 804 805 /* 806 * Caller wants to allocate a new IOVA range from 'rcache'. If we can 807 * satisfy the request, return a matching non-NULL range and remove 808 * it from the 'rcache'. 809 */ 810 static unsigned long __iova_rcache_get(struct iova_rcache *rcache, 811 unsigned long limit_pfn) 812 { 813 struct iova_cpu_rcache *cpu_rcache; 814 unsigned long iova_pfn = 0; 815 bool has_pfn = false; 816 unsigned long flags; 817 818 cpu_rcache = get_cpu_ptr(rcache->cpu_rcaches); 819 spin_lock_irqsave(&cpu_rcache->lock, flags); 820 821 if (!iova_magazine_empty(cpu_rcache->loaded)) { 822 has_pfn = true; 823 } else if (!iova_magazine_empty(cpu_rcache->prev)) { 824 swap(cpu_rcache->prev, cpu_rcache->loaded); 825 has_pfn = true; 826 } else { 827 spin_lock(&rcache->lock); 828 if (rcache->depot_size > 0) { 829 iova_magazine_free(cpu_rcache->loaded); 830 cpu_rcache->loaded = rcache->depot[--rcache->depot_size]; 831 has_pfn = true; 832 } 833 spin_unlock(&rcache->lock); 834 } 835 836 if (has_pfn) 837 iova_pfn = iova_magazine_pop(cpu_rcache->loaded, limit_pfn); 838 839 spin_unlock_irqrestore(&cpu_rcache->lock, flags); 840 put_cpu_ptr(rcache->cpu_rcaches); 841 842 return iova_pfn; 843 } 844 845 /* 846 * Try to satisfy IOVA allocation range from rcache. Fail if requested 847 * size is too big or the DMA limit we are given isn't satisfied by the 848 * top element in the magazine. 849 */ 850 static unsigned long iova_rcache_get(struct iova_domain *iovad, 851 unsigned long size, 852 unsigned long limit_pfn) 853 { 854 unsigned int log_size = order_base_2(size); 855 856 if (log_size >= IOVA_RANGE_CACHE_MAX_SIZE) 857 return 0; 858 859 return __iova_rcache_get(&iovad->rcaches[log_size], limit_pfn); 860 } 861 862 /* 863 * Free a cpu's rcache. 864 */ 865 static void free_cpu_iova_rcache(unsigned int cpu, struct iova_domain *iovad, 866 struct iova_rcache *rcache) 867 { 868 struct iova_cpu_rcache *cpu_rcache = per_cpu_ptr(rcache->cpu_rcaches, cpu); 869 unsigned long flags; 870 871 spin_lock_irqsave(&cpu_rcache->lock, flags); 872 873 iova_magazine_free_pfns(cpu_rcache->loaded, iovad); 874 iova_magazine_free(cpu_rcache->loaded); 875 876 iova_magazine_free_pfns(cpu_rcache->prev, iovad); 877 iova_magazine_free(cpu_rcache->prev); 878 879 spin_unlock_irqrestore(&cpu_rcache->lock, flags); 880 } 881 882 /* 883 * free rcache data structures. 884 */ 885 static void free_iova_rcaches(struct iova_domain *iovad) 886 { 887 struct iova_rcache *rcache; 888 unsigned long flags; 889 unsigned int cpu; 890 int i, j; 891 892 for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) { 893 rcache = &iovad->rcaches[i]; 894 for_each_possible_cpu(cpu) 895 free_cpu_iova_rcache(cpu, iovad, rcache); 896 spin_lock_irqsave(&rcache->lock, flags); 897 free_percpu(rcache->cpu_rcaches); 898 for (j = 0; j < rcache->depot_size; ++j) { 899 iova_magazine_free_pfns(rcache->depot[j], iovad); 900 iova_magazine_free(rcache->depot[j]); 901 } 902 spin_unlock_irqrestore(&rcache->lock, flags); 903 } 904 } 905 906 /* 907 * free all the IOVA ranges cached by a cpu (used when cpu is unplugged) 908 */ 909 void free_cpu_cached_iovas(unsigned int cpu, struct iova_domain *iovad) 910 { 911 struct iova_cpu_rcache *cpu_rcache; 912 struct iova_rcache *rcache; 913 unsigned long flags; 914 int i; 915 916 for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) { 917 rcache = &iovad->rcaches[i]; 918 cpu_rcache = per_cpu_ptr(rcache->cpu_rcaches, cpu); 919 spin_lock_irqsave(&cpu_rcache->lock, flags); 920 iova_magazine_free_pfns(cpu_rcache->loaded, iovad); 921 iova_magazine_free_pfns(cpu_rcache->prev, iovad); 922 spin_unlock_irqrestore(&cpu_rcache->lock, flags); 923 } 924 } 925 926 MODULE_AUTHOR("Anil S Keshavamurthy <anil.s.keshavamurthy@intel.com>"); 927 MODULE_LICENSE("GPL"); 928