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 ? (curr_iova->pfn_lo - 1) : 0;
 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                 if (WARN_ON(!iova))
 680                         continue;
 681
 682                 private_free_iova(iovad, iova);
 683         }
 684
 685         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 686
 687         mag->size = 0;
 688 }
 689
 690 static bool iova_magazine_full(struct iova_magazine *mag)
 691 {
 692         return (mag && mag->size == IOVA_MAG_SIZE);
 693 }
 694
 695 static bool iova_magazine_empty(struct iova_magazine *mag)
 696 {
 697         return (!mag || mag->size == 0);
 698 }
 699
 700 static unsigned long iova_magazine_pop(struct iova_magazine *mag,
 701                                        unsigned long limit_pfn)
 702 {
 703         BUG_ON(iova_magazine_empty(mag));
 704
 705         if (mag->pfns[mag->size - 1] >= limit_pfn)
 706                 return 0;
 707
 708         return mag->pfns[--mag->size];
 709 }
 710
 711 static void iova_magazine_push(struct iova_magazine *mag, unsigned long pfn)
 712 {
 713         BUG_ON(iova_magazine_full(mag));
 714
 715         mag->pfns[mag->size++] = pfn;
 716 }
 717
 718 static void init_iova_rcaches(struct iova_domain *iovad)
 719 {
 720         struct iova_cpu_rcache *cpu_rcache;
 721         struct iova_rcache *rcache;
 722         unsigned int cpu;
 723         int i;
 724
 725         for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
 726                 rcache = &iovad->rcaches[i];
 727                 spin_lock_init(&rcache->lock);
 728                 rcache->depot_size = 0;
 729                 rcache->cpu_rcaches = __alloc_percpu(sizeof(*cpu_rcache), cache_line_size());
 730                 if (WARN_ON(!rcache->cpu_rcaches))
 731                         continue;
 732                 for_each_possible_cpu(cpu) {
 733                         cpu_rcache = per_cpu_ptr(rcache->cpu_rcaches, cpu);
 734                         spin_lock_init(&cpu_rcache->lock);
 735                         cpu_rcache->loaded = iova_magazine_alloc(GFP_KERNEL);
 736                         cpu_rcache->prev = iova_magazine_alloc(GFP_KERNEL);
 737                 }
 738         }
 739 }
 740
 741 /*
 742  * Try inserting IOVA range starting with 'iova_pfn' into 'rcache', and
 743  * return true on success.  Can fail if rcache is full and we can't free
 744  * space, and free_iova() (our only caller) will then return the IOVA
 745  * range to the rbtree instead.
 746  */
 747 static bool __iova_rcache_insert(struct iova_domain *iovad,
 748                                  struct iova_rcache *rcache,
 749                                  unsigned long iova_pfn)
 750 {
 751         struct iova_magazine *mag_to_free = NULL;
 752         struct iova_cpu_rcache *cpu_rcache;
 753         bool can_insert = false;
 754         unsigned long flags;
 755
 756         cpu_rcache = get_cpu_ptr(rcache->cpu_rcaches);
 757         spin_lock_irqsave(&cpu_rcache->lock, flags);
 758
 759         if (!iova_magazine_full(cpu_rcache->loaded)) {
 760                 can_insert = true;
 761         } else if (!iova_magazine_full(cpu_rcache->prev)) {
 762                 swap(cpu_rcache->prev, cpu_rcache->loaded);
 763                 can_insert = true;
 764         } else {
 765                 struct iova_magazine *new_mag = iova_magazine_alloc(GFP_ATOMIC);
 766
 767                 if (new_mag) {
 768                         spin_lock(&rcache->lock);
 769                         if (rcache->depot_size < MAX_GLOBAL_MAGS) {
 770                                 rcache->depot[rcache->depot_size++] =
 771                                                 cpu_rcache->loaded;
 772                         } else {
 773                                 mag_to_free = cpu_rcache->loaded;
 774                         }
 775                         spin_unlock(&rcache->lock);
 776
 777                         cpu_rcache->loaded = new_mag;
 778                         can_insert = true;
 779                 }
 780         }
 781
 782         if (can_insert)
 783                 iova_magazine_push(cpu_rcache->loaded, iova_pfn);
 784
 785         spin_unlock_irqrestore(&cpu_rcache->lock, flags);
 786         put_cpu_ptr(rcache->cpu_rcaches);
 787
 788         if (mag_to_free) {
 789                 iova_magazine_free_pfns(mag_to_free, iovad);
 790                 iova_magazine_free(mag_to_free);
 791         }
 792
 793         return can_insert;
 794 }
 795
 796 static bool iova_rcache_insert(struct iova_domain *iovad, unsigned long pfn,
 797                                unsigned long size)
 798 {
 799         unsigned int log_size = order_base_2(size);
 800
 801         if (log_size >= IOVA_RANGE_CACHE_MAX_SIZE)
 802                 return false;
 803
 804         return __iova_rcache_insert(iovad, &iovad->rcaches[log_size], pfn);
 805 }
 806
 807 /*
 808  * Caller wants to allocate a new IOVA range from 'rcache'.  If we can
 809  * satisfy the request, return a matching non-NULL range and remove
 810  * it from the 'rcache'.
 811  */
 812 static unsigned long __iova_rcache_get(struct iova_rcache *rcache,
 813                                        unsigned long limit_pfn)
 814 {
 815         struct iova_cpu_rcache *cpu_rcache;
 816         unsigned long iova_pfn = 0;
 817         bool has_pfn = false;
 818         unsigned long flags;
 819
 820         cpu_rcache = get_cpu_ptr(rcache->cpu_rcaches);
 821         spin_lock_irqsave(&cpu_rcache->lock, flags);
 822
 823         if (!iova_magazine_empty(cpu_rcache->loaded)) {
 824                 has_pfn = true;
 825         } else if (!iova_magazine_empty(cpu_rcache->prev)) {
 826                 swap(cpu_rcache->prev, cpu_rcache->loaded);
 827                 has_pfn = true;
 828         } else {
 829                 spin_lock(&rcache->lock);
 830                 if (rcache->depot_size > 0) {
 831                         iova_magazine_free(cpu_rcache->loaded);
 832                         cpu_rcache->loaded = rcache->depot[--rcache->depot_size];
 833                         has_pfn = true;
 834                 }
 835                 spin_unlock(&rcache->lock);
 836         }
 837
 838         if (has_pfn)
 839                 iova_pfn = iova_magazine_pop(cpu_rcache->loaded, limit_pfn);
 840
 841         spin_unlock_irqrestore(&cpu_rcache->lock, flags);
 842         put_cpu_ptr(rcache->cpu_rcaches);
 843
 844         return iova_pfn;
 845 }
 846
 847 /*
 848  * Try to satisfy IOVA allocation range from rcache.  Fail if requested
 849  * size is too big or the DMA limit we are given isn't satisfied by the
 850  * top element in the magazine.
 851  */
 852 static unsigned long iova_rcache_get(struct iova_domain *iovad,
 853                                      unsigned long size,
 854                                      unsigned long limit_pfn)
 855 {
 856         unsigned int log_size = order_base_2(size);
 857
 858         if (log_size >= IOVA_RANGE_CACHE_MAX_SIZE)
 859                 return 0;
 860
 861         return __iova_rcache_get(&iovad->rcaches[log_size], limit_pfn);
 862 }
 863
 864 /*
 865  * Free a cpu's rcache.
 866  */
 867 static void free_cpu_iova_rcache(unsigned int cpu, struct iova_domain *iovad,
 868                                  struct iova_rcache *rcache)
 869 {
 870         struct iova_cpu_rcache *cpu_rcache = per_cpu_ptr(rcache->cpu_rcaches, cpu);
 871         unsigned long flags;
 872
 873         spin_lock_irqsave(&cpu_rcache->lock, flags);
 874
 875         iova_magazine_free_pfns(cpu_rcache->loaded, iovad);
 876         iova_magazine_free(cpu_rcache->loaded);
 877
 878         iova_magazine_free_pfns(cpu_rcache->prev, iovad);
 879         iova_magazine_free(cpu_rcache->prev);
 880
 881         spin_unlock_irqrestore(&cpu_rcache->lock, flags);
 882 }
 883
 884 /*
 885  * free rcache data structures.
 886  */
 887 static void free_iova_rcaches(struct iova_domain *iovad)
 888 {
 889         struct iova_rcache *rcache;
 890         unsigned long flags;
 891         unsigned int cpu;
 892         int i, j;
 893
 894         for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
 895                 rcache = &iovad->rcaches[i];
 896                 for_each_possible_cpu(cpu)
 897                         free_cpu_iova_rcache(cpu, iovad, rcache);
 898                 spin_lock_irqsave(&rcache->lock, flags);
 899                 free_percpu(rcache->cpu_rcaches);
 900                 for (j = 0; j < rcache->depot_size; ++j) {
 901                         iova_magazine_free_pfns(rcache->depot[j], iovad);
 902                         iova_magazine_free(rcache->depot[j]);
 903                 }
 904                 spin_unlock_irqrestore(&rcache->lock, flags);
 905         }
 906 }
 907
 908 /*
 909  * free all the IOVA ranges cached by a cpu (used when cpu is unplugged)
 910  */
 911 void free_cpu_cached_iovas(unsigned int cpu, struct iova_domain *iovad)
 912 {
 913         struct iova_cpu_rcache *cpu_rcache;
 914         struct iova_rcache *rcache;
 915         unsigned long flags;
 916         int i;
 917
 918         for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
 919                 rcache = &iovad->rcaches[i];
 920                 cpu_rcache = per_cpu_ptr(rcache->cpu_rcaches, cpu);
 921                 spin_lock_irqsave(&cpu_rcache->lock, flags);
 922                 iova_magazine_free_pfns(cpu_rcache->loaded, iovad);
 923                 iova_magazine_free_pfns(cpu_rcache->prev, iovad);
 924                 spin_unlock_irqrestore(&cpu_rcache->lock, flags);
 925         }
 926 }
 927
 928 MODULE_AUTHOR("Anil S Keshavamurthy <anil.s.keshavamurthy@intel.com>");
 929 MODULE_LICENSE("GPL");