drivers/iommu/iova.c

   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                 for_each_online_cpu(cpu)
 424                         free_cpu_cached_iovas(cpu, iovad);
 425                 goto retry;
 426         }
 427
 428         return new_iova->pfn_lo;
 429 }
 430 EXPORT_SYMBOL_GPL(alloc_iova_fast);
 431
 432 /**
 433  * free_iova_fast - free iova pfn range into rcache
 434  * @iovad: - iova domain in question.
 435  * @pfn: - pfn that is allocated previously
 436  * @size: - # of pages in range
 437  * This functions frees an iova range by trying to put it into the rcache,
 438  * falling back to regular iova deallocation via free_iova() if this fails.
 439  */
 440 void
 441 free_iova_fast(struct iova_domain *iovad, unsigned long pfn, unsigned long size)
 442 {
 443         if (iova_rcache_insert(iovad, pfn, size))
 444                 return;
 445
 446         free_iova(iovad, pfn);
 447 }
 448 EXPORT_SYMBOL_GPL(free_iova_fast);
 449
 450 /**
 451  * put_iova_domain - destroys the iova doamin
 452  * @iovad: - iova domain in question.
 453  * All the iova's in that domain are destroyed.
 454  */
 455 void put_iova_domain(struct iova_domain *iovad)
 456 {
 457         struct rb_node *node;
 458         unsigned long flags;
 459
 460         free_iova_rcaches(iovad);
 461         spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
 462         node = rb_first(&iovad->rbroot);
 463         while (node) {
 464                 struct iova *iova = container_of(node, struct iova, node);
 465
 466                 rb_erase(node, &iovad->rbroot);
 467                 free_iova_mem(iova);
 468                 node = rb_first(&iovad->rbroot);
 469         }
 470         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 471 }
 472 EXPORT_SYMBOL_GPL(put_iova_domain);
 473
 474 static int
 475 __is_range_overlap(struct rb_node *node,
 476         unsigned long pfn_lo, unsigned long pfn_hi)
 477 {
 478         struct iova *iova = container_of(node, struct iova, node);
 479
 480         if ((pfn_lo <= iova->pfn_hi) && (pfn_hi >= iova->pfn_lo))
 481                 return 1;
 482         return 0;
 483 }
 484
 485 static inline struct iova *
 486 alloc_and_init_iova(unsigned long pfn_lo, unsigned long pfn_hi)
 487 {
 488         struct iova *iova;
 489
 490         iova = alloc_iova_mem();
 491         if (iova) {
 492                 iova->pfn_lo = pfn_lo;
 493                 iova->pfn_hi = pfn_hi;
 494         }
 495
 496         return iova;
 497 }
 498
 499 static struct iova *
 500 __insert_new_range(struct iova_domain *iovad,
 501         unsigned long pfn_lo, unsigned long pfn_hi)
 502 {
 503         struct iova *iova;
 504
 505         iova = alloc_and_init_iova(pfn_lo, pfn_hi);
 506         if (iova)
 507                 iova_insert_rbtree(&iovad->rbroot, iova);
 508
 509         return iova;
 510 }
 511
 512 static void
 513 __adjust_overlap_range(struct iova *iova,
 514         unsigned long *pfn_lo, unsigned long *pfn_hi)
 515 {
 516         if (*pfn_lo < iova->pfn_lo)
 517                 iova->pfn_lo = *pfn_lo;
 518         if (*pfn_hi > iova->pfn_hi)
 519                 *pfn_lo = iova->pfn_hi + 1;
 520 }
 521
 522 /**
 523  * reserve_iova - reserves an iova in the given range
 524  * @iovad: - iova domain pointer
 525  * @pfn_lo: - lower page frame address
 526  * @pfn_hi:- higher pfn adderss
 527  * This function allocates reserves the address range from pfn_lo to pfn_hi so
 528  * that this address is not dished out as part of alloc_iova.
 529  */
 530 struct iova *
 531 reserve_iova(struct iova_domain *iovad,
 532         unsigned long pfn_lo, unsigned long pfn_hi)
 533 {
 534         struct rb_node *node;
 535         unsigned long flags;
 536         struct iova *iova;
 537         unsigned int overlap = 0;
 538
 539         spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
 540         for (node = rb_first(&iovad->rbroot); node; node = rb_next(node)) {
 541                 if (__is_range_overlap(node, pfn_lo, pfn_hi)) {
 542                         iova = container_of(node, struct iova, node);
 543                         __adjust_overlap_range(iova, &pfn_lo, &pfn_hi);
 544                         if ((pfn_lo >= iova->pfn_lo) &&
 545                                 (pfn_hi <= iova->pfn_hi))
 546                                 goto finish;
 547                         overlap = 1;
 548
 549                 } else if (overlap)
 550                                 break;
 551         }
 552
 553         /* We are here either because this is the first reserver node
 554          * or need to insert remaining non overlap addr range
 555          */
 556         iova = __insert_new_range(iovad, pfn_lo, pfn_hi);
 557 finish:
 558
 559         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 560         return iova;
 561 }
 562 EXPORT_SYMBOL_GPL(reserve_iova);
 563
 564 /**
 565  * copy_reserved_iova - copies the reserved between domains
 566  * @from: - source doamin from where to copy
 567  * @to: - destination domin where to copy
 568  * This function copies reserved iova's from one doamin to
 569  * other.
 570  */
 571 void
 572 copy_reserved_iova(struct iova_domain *from, struct iova_domain *to)
 573 {
 574         unsigned long flags;
 575         struct rb_node *node;
 576
 577         spin_lock_irqsave(&from->iova_rbtree_lock, flags);
 578         for (node = rb_first(&from->rbroot); node; node = rb_next(node)) {
 579                 struct iova *iova = container_of(node, struct iova, node);
 580                 struct iova *new_iova;
 581
 582                 new_iova = reserve_iova(to, iova->pfn_lo, iova->pfn_hi);
 583                 if (!new_iova)
 584                         printk(KERN_ERR "Reserve iova range %lx@%lx failed\n",
 585                                 iova->pfn_lo, iova->pfn_lo);
 586         }
 587         spin_unlock_irqrestore(&from->iova_rbtree_lock, flags);
 588 }
 589 EXPORT_SYMBOL_GPL(copy_reserved_iova);
 590
 591 struct iova *
 592 split_and_remove_iova(struct iova_domain *iovad, struct iova *iova,
 593                       unsigned long pfn_lo, unsigned long pfn_hi)
 594 {
 595         unsigned long flags;
 596         struct iova *prev = NULL, *next = NULL;
 597
 598         spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
 599         if (iova->pfn_lo < pfn_lo) {
 600                 prev = alloc_and_init_iova(iova->pfn_lo, pfn_lo - 1);
 601                 if (prev == NULL)
 602                         goto error;
 603         }
 604         if (iova->pfn_hi > pfn_hi) {
 605                 next = alloc_and_init_iova(pfn_hi + 1, iova->pfn_hi);
 606                 if (next == NULL)
 607                         goto error;
 608         }
 609
 610         __cached_rbnode_delete_update(iovad, iova);
 611         rb_erase(&iova->node, &iovad->rbroot);
 612
 613         if (prev) {
 614                 iova_insert_rbtree(&iovad->rbroot, prev);
 615                 iova->pfn_lo = pfn_lo;
 616         }
 617         if (next) {
 618                 iova_insert_rbtree(&iovad->rbroot, next);
 619                 iova->pfn_hi = pfn_hi;
 620         }
 621         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 622
 623         return iova;
 624
 625 error:
 626         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 627         if (prev)
 628                 free_iova_mem(prev);
 629         return NULL;
 630 }
 631
 632 /*
 633  * Magazine caches for IOVA ranges.  For an introduction to magazines,
 634  * see the USENIX 2001 paper "Magazines and Vmem: Extending the Slab
 635  * Allocator to Many CPUs and Arbitrary Resources" by Bonwick and Adams.
 636  * For simplicity, we use a static magazine size and don't implement the
 637  * dynamic size tuning described in the paper.
 638  */
 639
 640 #define IOVA_MAG_SIZE 128
 641
 642 struct iova_magazine {
 643         unsigned long size;
 644         unsigned long pfns[IOVA_MAG_SIZE];
 645 };
 646
 647 struct iova_cpu_rcache {
 648         spinlock_t lock;
 649         struct iova_magazine *loaded;
 650         struct iova_magazine *prev;
 651 };
 652
 653 static struct iova_magazine *iova_magazine_alloc(gfp_t flags)
 654 {
 655         return kzalloc(sizeof(struct iova_magazine), flags);
 656 }
 657
 658 static void iova_magazine_free(struct iova_magazine *mag)
 659 {
 660         kfree(mag);
 661 }
 662
 663 static void
 664 iova_magazine_free_pfns(struct iova_magazine *mag, struct iova_domain *iovad)
 665 {
 666         unsigned long flags;
 667         int i;
 668
 669         if (!mag)
 670                 return;
 671
 672         spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
 673
 674         for (i = 0 ; i < mag->size; ++i) {
 675                 struct iova *iova = private_find_iova(iovad, mag->pfns[i]);
 676
 677                 BUG_ON(!iova);
 678                 private_free_iova(iovad, iova);
 679         }
 680
 681         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 682
 683         mag->size = 0;
 684 }
 685
 686 static bool iova_magazine_full(struct iova_magazine *mag)
 687 {
 688         return (mag && mag->size == IOVA_MAG_SIZE);
 689 }
 690
 691 static bool iova_magazine_empty(struct iova_magazine *mag)
 692 {
 693         return (!mag || mag->size == 0);
 694 }
 695
 696 static unsigned long iova_magazine_pop(struct iova_magazine *mag,
 697                                        unsigned long limit_pfn)
 698 {
 699         BUG_ON(iova_magazine_empty(mag));
 700
 701         if (mag->pfns[mag->size - 1] >= limit_pfn)
 702                 return 0;
 703
 704         return mag->pfns[--mag->size];
 705 }
 706
 707 static void iova_magazine_push(struct iova_magazine *mag, unsigned long pfn)
 708 {
 709         BUG_ON(iova_magazine_full(mag));
 710
 711         mag->pfns[mag->size++] = pfn;
 712 }
 713
 714 static void init_iova_rcaches(struct iova_domain *iovad)
 715 {
 716         struct iova_cpu_rcache *cpu_rcache;
 717         struct iova_rcache *rcache;
 718         unsigned int cpu;
 719         int i;
 720
 721         for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
 722                 rcache = &iovad->rcaches[i];
 723                 spin_lock_init(&rcache->lock);
 724                 rcache->depot_size = 0;
 725                 rcache->cpu_rcaches = __alloc_percpu(sizeof(*cpu_rcache), cache_line_size());
 726                 if (WARN_ON(!rcache->cpu_rcaches))
 727                         continue;
 728                 for_each_possible_cpu(cpu) {
 729                         cpu_rcache = per_cpu_ptr(rcache->cpu_rcaches, cpu);
 730                         spin_lock_init(&cpu_rcache->lock);
 731                         cpu_rcache->loaded = iova_magazine_alloc(GFP_KERNEL);
 732                         cpu_rcache->prev = iova_magazine_alloc(GFP_KERNEL);
 733                 }
 734         }
 735 }
 736
 737 /*
 738  * Try inserting IOVA range starting with 'iova_pfn' into 'rcache', and
 739  * return true on success.  Can fail if rcache is full and we can't free
 740  * space, and free_iova() (our only caller) will then return the IOVA
 741  * range to the rbtree instead.
 742  */
 743 static bool __iova_rcache_insert(struct iova_domain *iovad,
 744                                  struct iova_rcache *rcache,
 745                                  unsigned long iova_pfn)
 746 {
 747         struct iova_magazine *mag_to_free = NULL;
 748         struct iova_cpu_rcache *cpu_rcache;
 749         bool can_insert = false;
 750         unsigned long flags;
 751
 752         cpu_rcache = this_cpu_ptr(rcache->cpu_rcaches);
 753         spin_lock_irqsave(&cpu_rcache->lock, flags);
 754
 755         if (!iova_magazine_full(cpu_rcache->loaded)) {
 756                 can_insert = true;
 757         } else if (!iova_magazine_full(cpu_rcache->prev)) {
 758                 swap(cpu_rcache->prev, cpu_rcache->loaded);
 759                 can_insert = true;
 760         } else {
 761                 struct iova_magazine *new_mag = iova_magazine_alloc(GFP_ATOMIC);
 762
 763                 if (new_mag) {
 764                         spin_lock(&rcache->lock);
 765                         if (rcache->depot_size < MAX_GLOBAL_MAGS) {
 766                                 rcache->depot[rcache->depot_size++] =
 767                                                 cpu_rcache->loaded;
 768                         } else {
 769                                 mag_to_free = cpu_rcache->loaded;
 770                         }
 771                         spin_unlock(&rcache->lock);
 772
 773                         cpu_rcache->loaded = new_mag;
 774                         can_insert = true;
 775                 }
 776         }
 777
 778         if (can_insert)
 779                 iova_magazine_push(cpu_rcache->loaded, iova_pfn);
 780
 781         spin_unlock_irqrestore(&cpu_rcache->lock, flags);
 782
 783         if (mag_to_free) {
 784                 iova_magazine_free_pfns(mag_to_free, iovad);
 785                 iova_magazine_free(mag_to_free);
 786         }
 787
 788         return can_insert;
 789 }
 790
 791 static bool iova_rcache_insert(struct iova_domain *iovad, unsigned long pfn,
 792                                unsigned long size)
 793 {
 794         unsigned int log_size = order_base_2(size);
 795
 796         if (log_size >= IOVA_RANGE_CACHE_MAX_SIZE)
 797                 return false;
 798
 799         return __iova_rcache_insert(iovad, &iovad->rcaches[log_size], pfn);
 800 }
 801
 802 /*
 803  * Caller wants to allocate a new IOVA range from 'rcache'.  If we can
 804  * satisfy the request, return a matching non-NULL range and remove
 805  * it from the 'rcache'.
 806  */
 807 static unsigned long __iova_rcache_get(struct iova_rcache *rcache,
 808                                        unsigned long limit_pfn)
 809 {
 810         struct iova_cpu_rcache *cpu_rcache;
 811         unsigned long iova_pfn = 0;
 812         bool has_pfn = false;
 813         unsigned long flags;
 814
 815         cpu_rcache = this_cpu_ptr(rcache->cpu_rcaches);
 816         spin_lock_irqsave(&cpu_rcache->lock, flags);
 817
 818         if (!iova_magazine_empty(cpu_rcache->loaded)) {
 819                 has_pfn = true;
 820         } else if (!iova_magazine_empty(cpu_rcache->prev)) {
 821                 swap(cpu_rcache->prev, cpu_rcache->loaded);
 822                 has_pfn = true;
 823         } else {
 824                 spin_lock(&rcache->lock);
 825                 if (rcache->depot_size > 0) {
 826                         iova_magazine_free(cpu_rcache->loaded);
 827                         cpu_rcache->loaded = rcache->depot[--rcache->depot_size];
 828                         has_pfn = true;
 829                 }
 830                 spin_unlock(&rcache->lock);
 831         }
 832
 833         if (has_pfn)
 834                 iova_pfn = iova_magazine_pop(cpu_rcache->loaded, limit_pfn);
 835
 836         spin_unlock_irqrestore(&cpu_rcache->lock, flags);
 837
 838         return iova_pfn;
 839 }
 840
 841 /*
 842  * Try to satisfy IOVA allocation range from rcache.  Fail if requested
 843  * size is too big or the DMA limit we are given isn't satisfied by the
 844  * top element in the magazine.
 845  */
 846 static unsigned long iova_rcache_get(struct iova_domain *iovad,
 847                                      unsigned long size,
 848                                      unsigned long limit_pfn)
 849 {
 850         unsigned int log_size = order_base_2(size);
 851
 852         if (log_size >= IOVA_RANGE_CACHE_MAX_SIZE)
 853                 return 0;
 854
 855         return __iova_rcache_get(&iovad->rcaches[log_size], limit_pfn);
 856 }
 857
 858 /*
 859  * Free a cpu's rcache.
 860  */
 861 static void free_cpu_iova_rcache(unsigned int cpu, struct iova_domain *iovad,
 862                                  struct iova_rcache *rcache)
 863 {
 864         struct iova_cpu_rcache *cpu_rcache = per_cpu_ptr(rcache->cpu_rcaches, cpu);
 865         unsigned long flags;
 866
 867         spin_lock_irqsave(&cpu_rcache->lock, flags);
 868
 869         iova_magazine_free_pfns(cpu_rcache->loaded, iovad);
 870         iova_magazine_free(cpu_rcache->loaded);
 871
 872         iova_magazine_free_pfns(cpu_rcache->prev, iovad);
 873         iova_magazine_free(cpu_rcache->prev);
 874
 875         spin_unlock_irqrestore(&cpu_rcache->lock, flags);
 876 }
 877
 878 /*
 879  * free rcache data structures.
 880  */
 881 static void free_iova_rcaches(struct iova_domain *iovad)
 882 {
 883         struct iova_rcache *rcache;
 884         unsigned long flags;
 885         unsigned int cpu;
 886         int i, j;
 887
 888         for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
 889                 rcache = &iovad->rcaches[i];
 890                 for_each_possible_cpu(cpu)
 891                         free_cpu_iova_rcache(cpu, iovad, rcache);
 892                 spin_lock_irqsave(&rcache->lock, flags);
 893                 free_percpu(rcache->cpu_rcaches);
 894                 for (j = 0; j < rcache->depot_size; ++j) {
 895                         iova_magazine_free_pfns(rcache->depot[j], iovad);
 896                         iova_magazine_free(rcache->depot[j]);
 897                 }
 898                 spin_unlock_irqrestore(&rcache->lock, flags);
 899         }
 900 }
 901
 902 /*
 903  * free all the IOVA ranges cached by a cpu (used when cpu is unplugged)
 904  */
 905 void free_cpu_cached_iovas(unsigned int cpu, struct iova_domain *iovad)
 906 {
 907         struct iova_cpu_rcache *cpu_rcache;
 908         struct iova_rcache *rcache;
 909         unsigned long flags;
 910         int i;
 911
 912         for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
 913                 rcache = &iovad->rcaches[i];
 914                 cpu_rcache = per_cpu_ptr(rcache->cpu_rcaches, cpu);
 915                 spin_lock_irqsave(&cpu_rcache->lock, flags);
 916                 iova_magazine_free_pfns(cpu_rcache->loaded, iovad);
 917                 iova_magazine_free_pfns(cpu_rcache->prev, iovad);
 918                 spin_unlock_irqrestore(&cpu_rcache->lock, flags);
 919         }
 920 }
 921
 922 MODULE_AUTHOR("Anil S Keshavamurthy <anil.s.keshavamurthy@intel.com>");
 923 MODULE_LICENSE("GPL");