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                 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");