drivers/iommu/iova.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * Copyright © 2006-2009, Intel Corporation.
   4  *
   5  * Author: Anil S Keshavamurthy <[email protected]>
   6  */
   7
   8 #include <linux/iova.h>
   9 #include <linux/kmemleak.h>
  10 #include <linux/module.h>
  11 #include <linux/slab.h>
  12 #include <linux/smp.h>
  13 #include <linux/bitops.h>
  14 #include <linux/cpu.h>
  15 #include <linux/workqueue.h>
  16
  17 /* The anchor node sits above the top of the usable address space */
  18 #define IOVA_ANCHOR     ~0UL
  19
  20 #define IOVA_RANGE_CACHE_MAX_SIZE 6     /* log of max cached IOVA range size (in pages) */
  21
  22 static bool iova_rcache_insert(struct iova_domain *iovad,
  23                                unsigned long pfn,
  24                                unsigned long size);
  25 static unsigned long iova_rcache_get(struct iova_domain *iovad,
  26                                      unsigned long size,
  27                                      unsigned long limit_pfn);
  28 static void free_iova_rcaches(struct iova_domain *iovad);
  29 static void free_cpu_cached_iovas(unsigned int cpu, struct iova_domain *iovad);
  30 static void free_global_cached_iovas(struct iova_domain *iovad);
  31
  32 static struct iova *to_iova(struct rb_node *node)
  33 {
  34         return rb_entry(node, struct iova, node);
  35 }
  36
  37 void
  38 init_iova_domain(struct iova_domain *iovad, unsigned long granule,
  39         unsigned long start_pfn)
  40 {
  41         /*
  42          * IOVA granularity will normally be equal to the smallest
  43          * supported IOMMU page size; both *must* be capable of
  44          * representing individual CPU pages exactly.
  45          */
  46         BUG_ON((granule > PAGE_SIZE) || !is_power_of_2(granule));
  47
  48         spin_lock_init(&iovad->iova_rbtree_lock);
  49         iovad->rbroot = RB_ROOT;
  50         iovad->cached_node = &iovad->anchor.node;
  51         iovad->cached32_node = &iovad->anchor.node;
  52         iovad->granule = granule;
  53         iovad->start_pfn = start_pfn;
  54         iovad->dma_32bit_pfn = 1UL << (32 - iova_shift(iovad));
  55         iovad->max32_alloc_size = iovad->dma_32bit_pfn;
  56         iovad->anchor.pfn_lo = iovad->anchor.pfn_hi = IOVA_ANCHOR;
  57         rb_link_node(&iovad->anchor.node, NULL, &iovad->rbroot.rb_node);
  58         rb_insert_color(&iovad->anchor.node, &iovad->rbroot);
  59 }
  60 EXPORT_SYMBOL_GPL(init_iova_domain);
  61
  62 static struct rb_node *
  63 __get_cached_rbnode(struct iova_domain *iovad, unsigned long limit_pfn)
  64 {
  65         if (limit_pfn <= iovad->dma_32bit_pfn)
  66                 return iovad->cached32_node;
  67
  68         return iovad->cached_node;
  69 }
  70
  71 static void
  72 __cached_rbnode_insert_update(struct iova_domain *iovad, struct iova *new)
  73 {
  74         if (new->pfn_hi < iovad->dma_32bit_pfn)
  75                 iovad->cached32_node = &new->node;
  76         else
  77                 iovad->cached_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
  85         cached_iova = to_iova(iovad->cached32_node);
  86         if (free == cached_iova ||
  87             (free->pfn_hi < iovad->dma_32bit_pfn &&
  88              free->pfn_lo >= cached_iova->pfn_lo))
  89                 iovad->cached32_node = rb_next(&free->node);
  90
  91         if (free->pfn_lo < iovad->dma_32bit_pfn)
  92                 iovad->max32_alloc_size = iovad->dma_32bit_pfn;
  93
  94         cached_iova = to_iova(iovad->cached_node);
  95         if (free->pfn_lo >= cached_iova->pfn_lo)
  96                 iovad->cached_node = rb_next(&free->node);
  97 }
  98
  99 static struct rb_node *iova_find_limit(struct iova_domain *iovad, unsigned long limit_pfn)
 100 {
 101         struct rb_node *node, *next;
 102         /*
 103          * Ideally what we'd like to judge here is whether limit_pfn is close
 104          * enough to the highest-allocated IOVA that starting the allocation
 105          * walk from the anchor node will be quicker than this initial work to
 106          * find an exact starting point (especially if that ends up being the
 107          * anchor node anyway). This is an incredibly crude approximation which
 108          * only really helps the most likely case, but is at least trivially easy.
 109          */
 110         if (limit_pfn > iovad->dma_32bit_pfn)
 111                 return &iovad->anchor.node;
 112
 113         node = iovad->rbroot.rb_node;
 114         while (to_iova(node)->pfn_hi < limit_pfn)
 115                 node = node->rb_right;
 116
 117 search_left:
 118         while (node->rb_left && to_iova(node->rb_left)->pfn_lo >= limit_pfn)
 119                 node = node->rb_left;
 120
 121         if (!node->rb_left)
 122                 return node;
 123
 124         next = node->rb_left;
 125         while (next->rb_right) {
 126                 next = next->rb_right;
 127                 if (to_iova(next)->pfn_lo >= limit_pfn) {
 128                         node = next;
 129                         goto search_left;
 130                 }
 131         }
 132
 133         return node;
 134 }
 135
 136 /* Insert the iova into domain rbtree by holding writer lock */
 137 static void
 138 iova_insert_rbtree(struct rb_root *root, struct iova *iova,
 139                    struct rb_node *start)
 140 {
 141         struct rb_node **new, *parent = NULL;
 142
 143         new = (start) ? &start : &(root->rb_node);
 144         /* Figure out where to put new node */
 145         while (*new) {
 146                 struct iova *this = to_iova(*new);
 147
 148                 parent = *new;
 149
 150                 if (iova->pfn_lo < this->pfn_lo)
 151                         new = &((*new)->rb_left);
 152                 else if (iova->pfn_lo > this->pfn_lo)
 153                         new = &((*new)->rb_right);
 154                 else {
 155                         WARN_ON(1); /* this should not happen */
 156                         return;
 157                 }
 158         }
 159         /* Add new node and rebalance tree. */
 160         rb_link_node(&iova->node, parent, new);
 161         rb_insert_color(&iova->node, root);
 162 }
 163
 164 static int __alloc_and_insert_iova_range(struct iova_domain *iovad,
 165                 unsigned long size, unsigned long limit_pfn,
 166                         struct iova *new, bool size_aligned)
 167 {
 168         struct rb_node *curr, *prev;
 169         struct iova *curr_iova;
 170         unsigned long flags;
 171         unsigned long new_pfn, retry_pfn;
 172         unsigned long align_mask = ~0UL;
 173         unsigned long high_pfn = limit_pfn, low_pfn = iovad->start_pfn;
 174
 175         if (size_aligned)
 176                 align_mask <<= fls_long(size - 1);
 177
 178         /* Walk the tree backwards */
 179         spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
 180         if (limit_pfn <= iovad->dma_32bit_pfn &&
 181                         size >= iovad->max32_alloc_size)
 182                 goto iova32_full;
 183
 184         curr = __get_cached_rbnode(iovad, limit_pfn);
 185         curr_iova = to_iova(curr);
 186         retry_pfn = curr_iova->pfn_hi;
 187
 188 retry:
 189         do {
 190                 high_pfn = min(high_pfn, curr_iova->pfn_lo);
 191                 new_pfn = (high_pfn - size) & align_mask;
 192                 prev = curr;
 193                 curr = rb_prev(curr);
 194                 curr_iova = to_iova(curr);
 195         } while (curr && new_pfn <= curr_iova->pfn_hi && new_pfn >= low_pfn);
 196
 197         if (high_pfn < size || new_pfn < low_pfn) {
 198                 if (low_pfn == iovad->start_pfn && retry_pfn < limit_pfn) {
 199                         high_pfn = limit_pfn;
 200                         low_pfn = retry_pfn + 1;
 201                         curr = iova_find_limit(iovad, limit_pfn);
 202                         curr_iova = to_iova(curr);
 203                         goto retry;
 204                 }
 205                 iovad->max32_alloc_size = size;
 206                 goto iova32_full;
 207         }
 208
 209         /* pfn_lo will point to size aligned address if size_aligned is set */
 210         new->pfn_lo = new_pfn;
 211         new->pfn_hi = new->pfn_lo + size - 1;
 212
 213         /* If we have 'prev', it's a valid place to start the insertion. */
 214         iova_insert_rbtree(&iovad->rbroot, new, prev);
 215         __cached_rbnode_insert_update(iovad, new);
 216
 217         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 218         return 0;
 219
 220 iova32_full:
 221         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 222         return -ENOMEM;
 223 }
 224
 225 static struct kmem_cache *iova_cache;
 226 static unsigned int iova_cache_users;
 227 static DEFINE_MUTEX(iova_cache_mutex);
 228
 229 static struct iova *alloc_iova_mem(void)
 230 {
 231         return kmem_cache_zalloc(iova_cache, GFP_ATOMIC | __GFP_NOWARN);
 232 }
 233
 234 static void free_iova_mem(struct iova *iova)
 235 {
 236         if (iova->pfn_lo != IOVA_ANCHOR)
 237                 kmem_cache_free(iova_cache, iova);
 238 }
 239
 240 /**
 241  * alloc_iova - allocates an iova
 242  * @iovad: - iova domain in question
 243  * @size: - size of page frames to allocate
 244  * @limit_pfn: - max limit address
 245  * @size_aligned: - set if size_aligned address range is required
 246  * This function allocates an iova in the range iovad->start_pfn to limit_pfn,
 247  * searching top-down from limit_pfn to iovad->start_pfn. If the size_aligned
 248  * flag is set then the allocated address iova->pfn_lo will be naturally
 249  * aligned on roundup_power_of_two(size).
 250  */
 251 struct iova *
 252 alloc_iova(struct iova_domain *iovad, unsigned long size,
 253         unsigned long limit_pfn,
 254         bool size_aligned)
 255 {
 256         struct iova *new_iova;
 257         int ret;
 258
 259         new_iova = alloc_iova_mem();
 260         if (!new_iova)
 261                 return NULL;
 262
 263         ret = __alloc_and_insert_iova_range(iovad, size, limit_pfn + 1,
 264                         new_iova, size_aligned);
 265
 266         if (ret) {
 267                 free_iova_mem(new_iova);
 268                 return NULL;
 269         }
 270
 271         return new_iova;
 272 }
 273 EXPORT_SYMBOL_GPL(alloc_iova);
 274
 275 static struct iova *
 276 private_find_iova(struct iova_domain *iovad, unsigned long pfn)
 277 {
 278         struct rb_node *node = iovad->rbroot.rb_node;
 279
 280         assert_spin_locked(&iovad->iova_rbtree_lock);
 281
 282         while (node) {
 283                 struct iova *iova = to_iova(node);
 284
 285                 if (pfn < iova->pfn_lo)
 286                         node = node->rb_left;
 287                 else if (pfn > iova->pfn_hi)
 288                         node = node->rb_right;
 289                 else
 290                         return iova;    /* pfn falls within iova's range */
 291         }
 292
 293         return NULL;
 294 }
 295
 296 static void remove_iova(struct iova_domain *iovad, struct iova *iova)
 297 {
 298         assert_spin_locked(&iovad->iova_rbtree_lock);
 299         __cached_rbnode_delete_update(iovad, iova);
 300         rb_erase(&iova->node, &iovad->rbroot);
 301 }
 302
 303 /**
 304  * find_iova - finds an iova for a given pfn
 305  * @iovad: - iova domain in question.
 306  * @pfn: - page frame number
 307  * This function finds and returns an iova belonging to the
 308  * given domain which matches the given pfn.
 309  */
 310 struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn)
 311 {
 312         unsigned long flags;
 313         struct iova *iova;
 314
 315         /* Take the lock so that no other thread is manipulating the rbtree */
 316         spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
 317         iova = private_find_iova(iovad, pfn);
 318         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 319         return iova;
 320 }
 321 EXPORT_SYMBOL_GPL(find_iova);
 322
 323 /**
 324  * __free_iova - frees the given iova
 325  * @iovad: iova domain in question.
 326  * @iova: iova in question.
 327  * Frees the given iova belonging to the giving domain
 328  */
 329 void
 330 __free_iova(struct iova_domain *iovad, struct iova *iova)
 331 {
 332         unsigned long flags;
 333
 334         spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
 335         remove_iova(iovad, iova);
 336         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 337         free_iova_mem(iova);
 338 }
 339 EXPORT_SYMBOL_GPL(__free_iova);
 340
 341 /**
 342  * free_iova - finds and frees the iova for a given pfn
 343  * @iovad: - iova domain in question.
 344  * @pfn: - pfn that is allocated previously
 345  * This functions finds an iova for a given pfn and then
 346  * frees the iova from that domain.
 347  */
 348 void
 349 free_iova(struct iova_domain *iovad, unsigned long pfn)
 350 {
 351         unsigned long flags;
 352         struct iova *iova;
 353
 354         spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
 355         iova = private_find_iova(iovad, pfn);
 356         if (!iova) {
 357                 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 358                 return;
 359         }
 360         remove_iova(iovad, iova);
 361         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 362         free_iova_mem(iova);
 363 }
 364 EXPORT_SYMBOL_GPL(free_iova);
 365
 366 /**
 367  * alloc_iova_fast - allocates an iova from rcache
 368  * @iovad: - iova domain in question
 369  * @size: - size of page frames to allocate
 370  * @limit_pfn: - max limit address
 371  * @flush_rcache: - set to flush rcache on regular allocation failure
 372  * This function tries to satisfy an iova allocation from the rcache,
 373  * and falls back to regular allocation on failure. If regular allocation
 374  * fails too and the flush_rcache flag is set then the rcache will be flushed.
 375 */
 376 unsigned long
 377 alloc_iova_fast(struct iova_domain *iovad, unsigned long size,
 378                 unsigned long limit_pfn, bool flush_rcache)
 379 {
 380         unsigned long iova_pfn;
 381         struct iova *new_iova;
 382
 383         /*
 384          * Freeing non-power-of-two-sized allocations back into the IOVA caches
 385          * will come back to bite us badly, so we have to waste a bit of space
 386          * rounding up anything cacheable to make sure that can't happen. The
 387          * order of the unadjusted size will still match upon freeing.
 388          */
 389         if (size < (1 << (IOVA_RANGE_CACHE_MAX_SIZE - 1)))
 390                 size = roundup_pow_of_two(size);
 391
 392         iova_pfn = iova_rcache_get(iovad, size, limit_pfn + 1);
 393         if (iova_pfn)
 394                 return iova_pfn;
 395
 396 retry:
 397         new_iova = alloc_iova(iovad, size, limit_pfn, true);
 398         if (!new_iova) {
 399                 unsigned int cpu;
 400
 401                 if (!flush_rcache)
 402                         return 0;
 403
 404                 /* Try replenishing IOVAs by flushing rcache. */
 405                 flush_rcache = false;
 406                 for_each_online_cpu(cpu)
 407                         free_cpu_cached_iovas(cpu, iovad);
 408                 free_global_cached_iovas(iovad);
 409                 goto retry;
 410         }
 411
 412         return new_iova->pfn_lo;
 413 }
 414 EXPORT_SYMBOL_GPL(alloc_iova_fast);
 415
 416 /**
 417  * free_iova_fast - free iova pfn range into rcache
 418  * @iovad: - iova domain in question.
 419  * @pfn: - pfn that is allocated previously
 420  * @size: - # of pages in range
 421  * This functions frees an iova range by trying to put it into the rcache,
 422  * falling back to regular iova deallocation via free_iova() if this fails.
 423  */
 424 void
 425 free_iova_fast(struct iova_domain *iovad, unsigned long pfn, unsigned long size)
 426 {
 427         if (iova_rcache_insert(iovad, pfn, size))
 428                 return;
 429
 430         free_iova(iovad, pfn);
 431 }
 432 EXPORT_SYMBOL_GPL(free_iova_fast);
 433
 434 static void iova_domain_free_rcaches(struct iova_domain *iovad)
 435 {
 436         cpuhp_state_remove_instance_nocalls(CPUHP_IOMMU_IOVA_DEAD,
 437                                             &iovad->cpuhp_dead);
 438         free_iova_rcaches(iovad);
 439 }
 440
 441 /**
 442  * put_iova_domain - destroys the iova domain
 443  * @iovad: - iova domain in question.
 444  * All the iova's in that domain are destroyed.
 445  */
 446 void put_iova_domain(struct iova_domain *iovad)
 447 {
 448         struct iova *iova, *tmp;
 449
 450         if (iovad->rcaches)
 451                 iova_domain_free_rcaches(iovad);
 452
 453         rbtree_postorder_for_each_entry_safe(iova, tmp, &iovad->rbroot, node)
 454                 free_iova_mem(iova);
 455 }
 456 EXPORT_SYMBOL_GPL(put_iova_domain);
 457
 458 static int
 459 __is_range_overlap(struct rb_node *node,
 460         unsigned long pfn_lo, unsigned long pfn_hi)
 461 {
 462         struct iova *iova = to_iova(node);
 463
 464         if ((pfn_lo <= iova->pfn_hi) && (pfn_hi >= iova->pfn_lo))
 465                 return 1;
 466         return 0;
 467 }
 468
 469 static inline struct iova *
 470 alloc_and_init_iova(unsigned long pfn_lo, unsigned long pfn_hi)
 471 {
 472         struct iova *iova;
 473
 474         iova = alloc_iova_mem();
 475         if (iova) {
 476                 iova->pfn_lo = pfn_lo;
 477                 iova->pfn_hi = pfn_hi;
 478         }
 479
 480         return iova;
 481 }
 482
 483 static struct iova *
 484 __insert_new_range(struct iova_domain *iovad,
 485         unsigned long pfn_lo, unsigned long pfn_hi)
 486 {
 487         struct iova *iova;
 488
 489         iova = alloc_and_init_iova(pfn_lo, pfn_hi);
 490         if (iova)
 491                 iova_insert_rbtree(&iovad->rbroot, iova, NULL);
 492
 493         return iova;
 494 }
 495
 496 static void
 497 __adjust_overlap_range(struct iova *iova,
 498         unsigned long *pfn_lo, unsigned long *pfn_hi)
 499 {
 500         if (*pfn_lo < iova->pfn_lo)
 501                 iova->pfn_lo = *pfn_lo;
 502         if (*pfn_hi > iova->pfn_hi)
 503                 *pfn_lo = iova->pfn_hi + 1;
 504 }
 505
 506 /**
 507  * reserve_iova - reserves an iova in the given range
 508  * @iovad: - iova domain pointer
 509  * @pfn_lo: - lower page frame address
 510  * @pfn_hi:- higher pfn address
 511  * This function allocates reserves the address range from pfn_lo to pfn_hi so
 512  * that this address is not dished out as part of alloc_iova.
 513  */
 514 struct iova *
 515 reserve_iova(struct iova_domain *iovad,
 516         unsigned long pfn_lo, unsigned long pfn_hi)
 517 {
 518         struct rb_node *node;
 519         unsigned long flags;
 520         struct iova *iova;
 521         unsigned int overlap = 0;
 522
 523         /* Don't allow nonsensical pfns */
 524         if (WARN_ON((pfn_hi | pfn_lo) > (ULLONG_MAX >> iova_shift(iovad))))
 525                 return NULL;
 526
 527         spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
 528         for (node = rb_first(&iovad->rbroot); node; node = rb_next(node)) {
 529                 if (__is_range_overlap(node, pfn_lo, pfn_hi)) {
 530                         iova = to_iova(node);
 531                         __adjust_overlap_range(iova, &pfn_lo, &pfn_hi);
 532                         if ((pfn_lo >= iova->pfn_lo) &&
 533                                 (pfn_hi <= iova->pfn_hi))
 534                                 goto finish;
 535                         overlap = 1;
 536
 537                 } else if (overlap)
 538                                 break;
 539         }
 540
 541         /* We are here either because this is the first reserver node
 542          * or need to insert remaining non overlap addr range
 543          */
 544         iova = __insert_new_range(iovad, pfn_lo, pfn_hi);
 545 finish:
 546
 547         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 548         return iova;
 549 }
 550 EXPORT_SYMBOL_GPL(reserve_iova);
 551
 552 /*
 553  * Magazine caches for IOVA ranges.  For an introduction to magazines,
 554  * see the USENIX 2001 paper "Magazines and Vmem: Extending the Slab
 555  * Allocator to Many CPUs and Arbitrary Resources" by Bonwick and Adams.
 556  * For simplicity, we use a static magazine size and don't implement the
 557  * dynamic size tuning described in the paper.
 558  */
 559
 560 /*
 561  * As kmalloc's buffer size is fixed to power of 2, 127 is chosen to
 562  * assure size of 'iova_magazine' to be 1024 bytes, so that no memory
 563  * will be wasted. Since only full magazines are inserted into the depot,
 564  * we don't need to waste PFN capacity on a separate list head either.
 565  */
 566 #define IOVA_MAG_SIZE 127
 567
 568 #define IOVA_DEPOT_DELAY msecs_to_jiffies(100)
 569
 570 struct iova_magazine {
 571         union {
 572                 unsigned long size;
 573                 struct iova_magazine *next;
 574         };
 575         unsigned long pfns[IOVA_MAG_SIZE];
 576 };
 577 static_assert(!(sizeof(struct iova_magazine) & (sizeof(struct iova_magazine) - 1)));
 578
 579 struct iova_cpu_rcache {
 580         spinlock_t lock;
 581         struct iova_magazine *loaded;
 582         struct iova_magazine *prev;
 583 };
 584
 585 struct iova_rcache {
 586         spinlock_t lock;
 587         unsigned int depot_size;
 588         struct iova_magazine *depot;
 589         struct iova_cpu_rcache __percpu *cpu_rcaches;
 590         struct iova_domain *iovad;
 591         struct delayed_work work;
 592 };
 593
 594 static struct kmem_cache *iova_magazine_cache;
 595
 596 unsigned long iova_rcache_range(void)
 597 {
 598         return PAGE_SIZE << (IOVA_RANGE_CACHE_MAX_SIZE - 1);
 599 }
 600
 601 static struct iova_magazine *iova_magazine_alloc(gfp_t flags)
 602 {
 603         struct iova_magazine *mag;
 604
 605         mag = kmem_cache_alloc(iova_magazine_cache, flags);
 606         if (mag)
 607                 mag->size = 0;
 608
 609         return mag;
 610 }
 611
 612 static void iova_magazine_free(struct iova_magazine *mag)
 613 {
 614         kmem_cache_free(iova_magazine_cache, mag);
 615 }
 616
 617 static void
 618 iova_magazine_free_pfns(struct iova_magazine *mag, struct iova_domain *iovad)
 619 {
 620         unsigned long flags;
 621         int i;
 622
 623         spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
 624
 625         for (i = 0 ; i < mag->size; ++i) {
 626                 struct iova *iova = private_find_iova(iovad, mag->pfns[i]);
 627
 628                 if (WARN_ON(!iova))
 629                         continue;
 630
 631                 remove_iova(iovad, iova);
 632                 free_iova_mem(iova);
 633         }
 634
 635         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 636
 637         mag->size = 0;
 638 }
 639
 640 static bool iova_magazine_full(struct iova_magazine *mag)
 641 {
 642         return mag->size == IOVA_MAG_SIZE;
 643 }
 644
 645 static bool iova_magazine_empty(struct iova_magazine *mag)
 646 {
 647         return mag->size == 0;
 648 }
 649
 650 static unsigned long iova_magazine_pop(struct iova_magazine *mag,
 651                                        unsigned long limit_pfn)
 652 {
 653         int i;
 654         unsigned long pfn;
 655
 656         /* Only fall back to the rbtree if we have no suitable pfns at all */
 657         for (i = mag->size - 1; mag->pfns[i] > limit_pfn; i--)
 658                 if (i == 0)
 659                         return 0;
 660
 661         /* Swap it to pop it */
 662         pfn = mag->pfns[i];
 663         mag->pfns[i] = mag->pfns[--mag->size];
 664
 665         return pfn;
 666 }
 667
 668 static void iova_magazine_push(struct iova_magazine *mag, unsigned long pfn)
 669 {
 670         mag->pfns[mag->size++] = pfn;
 671 }
 672
 673 static struct iova_magazine *iova_depot_pop(struct iova_rcache *rcache)
 674 {
 675         struct iova_magazine *mag = rcache->depot;
 676
 677         /*
 678          * As the mag->next pointer is moved to rcache->depot and reset via
 679          * the mag->size assignment, mark it as a transient false positive.
 680          */
 681         kmemleak_transient_leak(mag->next);
 682         rcache->depot = mag->next;
 683         mag->size = IOVA_MAG_SIZE;
 684         rcache->depot_size--;
 685         return mag;
 686 }
 687
 688 static void iova_depot_push(struct iova_rcache *rcache, struct iova_magazine *mag)
 689 {
 690         mag->next = rcache->depot;
 691         rcache->depot = mag;
 692         rcache->depot_size++;
 693 }
 694
 695 static void iova_depot_work_func(struct work_struct *work)
 696 {
 697         struct iova_rcache *rcache = container_of(work, typeof(*rcache), work.work);
 698         struct iova_magazine *mag = NULL;
 699         unsigned long flags;
 700
 701         spin_lock_irqsave(&rcache->lock, flags);
 702         if (rcache->depot_size > num_online_cpus())
 703                 mag = iova_depot_pop(rcache);
 704         spin_unlock_irqrestore(&rcache->lock, flags);
 705
 706         if (mag) {
 707                 iova_magazine_free_pfns(mag, rcache->iovad);
 708                 iova_magazine_free(mag);
 709                 schedule_delayed_work(&rcache->work, IOVA_DEPOT_DELAY);
 710         }
 711 }
 712
 713 int iova_domain_init_rcaches(struct iova_domain *iovad)
 714 {
 715         unsigned int cpu;
 716         int i, ret;
 717
 718         iovad->rcaches = kcalloc(IOVA_RANGE_CACHE_MAX_SIZE,
 719                                  sizeof(struct iova_rcache),
 720                                  GFP_KERNEL);
 721         if (!iovad->rcaches)
 722                 return -ENOMEM;
 723
 724         for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
 725                 struct iova_cpu_rcache *cpu_rcache;
 726                 struct iova_rcache *rcache;
 727
 728                 rcache = &iovad->rcaches[i];
 729                 spin_lock_init(&rcache->lock);
 730                 rcache->iovad = iovad;
 731                 INIT_DELAYED_WORK(&rcache->work, iova_depot_work_func);
 732                 rcache->cpu_rcaches = __alloc_percpu(sizeof(*cpu_rcache),
 733                                                      cache_line_size());
 734                 if (!rcache->cpu_rcaches) {
 735                         ret = -ENOMEM;
 736                         goto out_err;
 737                 }
 738                 for_each_possible_cpu(cpu) {
 739                         cpu_rcache = per_cpu_ptr(rcache->cpu_rcaches, cpu);
 740
 741                         spin_lock_init(&cpu_rcache->lock);
 742                         cpu_rcache->loaded = iova_magazine_alloc(GFP_KERNEL);
 743                         cpu_rcache->prev = iova_magazine_alloc(GFP_KERNEL);
 744                         if (!cpu_rcache->loaded || !cpu_rcache->prev) {
 745                                 ret = -ENOMEM;
 746                                 goto out_err;
 747                         }
 748                 }
 749         }
 750
 751         ret = cpuhp_state_add_instance_nocalls(CPUHP_IOMMU_IOVA_DEAD,
 752                                                &iovad->cpuhp_dead);
 753         if (ret)
 754                 goto out_err;
 755         return 0;
 756
 757 out_err:
 758         free_iova_rcaches(iovad);
 759         return ret;
 760 }
 761 EXPORT_SYMBOL_GPL(iova_domain_init_rcaches);
 762
 763 /*
 764  * Try inserting IOVA range starting with 'iova_pfn' into 'rcache', and
 765  * return true on success.  Can fail if rcache is full and we can't free
 766  * space, and free_iova() (our only caller) will then return the IOVA
 767  * range to the rbtree instead.
 768  */
 769 static bool __iova_rcache_insert(struct iova_domain *iovad,
 770                                  struct iova_rcache *rcache,
 771                                  unsigned long iova_pfn)
 772 {
 773         struct iova_cpu_rcache *cpu_rcache;
 774         bool can_insert = false;
 775         unsigned long flags;
 776
 777         cpu_rcache = raw_cpu_ptr(rcache->cpu_rcaches);
 778         spin_lock_irqsave(&cpu_rcache->lock, flags);
 779
 780         if (!iova_magazine_full(cpu_rcache->loaded)) {
 781                 can_insert = true;
 782         } else if (!iova_magazine_full(cpu_rcache->prev)) {
 783                 swap(cpu_rcache->prev, cpu_rcache->loaded);
 784                 can_insert = true;
 785         } else {
 786                 struct iova_magazine *new_mag = iova_magazine_alloc(GFP_ATOMIC);
 787
 788                 if (new_mag) {
 789                         spin_lock(&rcache->lock);
 790                         iova_depot_push(rcache, cpu_rcache->loaded);
 791                         spin_unlock(&rcache->lock);
 792                         schedule_delayed_work(&rcache->work, IOVA_DEPOT_DELAY);
 793
 794                         cpu_rcache->loaded = new_mag;
 795                         can_insert = true;
 796                 }
 797         }
 798
 799         if (can_insert)
 800                 iova_magazine_push(cpu_rcache->loaded, iova_pfn);
 801
 802         spin_unlock_irqrestore(&cpu_rcache->lock, flags);
 803
 804         return can_insert;
 805 }
 806
 807 static bool iova_rcache_insert(struct iova_domain *iovad, unsigned long pfn,
 808                                unsigned long size)
 809 {
 810         unsigned int log_size = order_base_2(size);
 811
 812         if (log_size >= IOVA_RANGE_CACHE_MAX_SIZE)
 813                 return false;
 814
 815         return __iova_rcache_insert(iovad, &iovad->rcaches[log_size], pfn);
 816 }
 817
 818 /*
 819  * Caller wants to allocate a new IOVA range from 'rcache'.  If we can
 820  * satisfy the request, return a matching non-NULL range and remove
 821  * it from the 'rcache'.
 822  */
 823 static unsigned long __iova_rcache_get(struct iova_rcache *rcache,
 824                                        unsigned long limit_pfn)
 825 {
 826         struct iova_cpu_rcache *cpu_rcache;
 827         unsigned long iova_pfn = 0;
 828         bool has_pfn = false;
 829         unsigned long flags;
 830
 831         cpu_rcache = raw_cpu_ptr(rcache->cpu_rcaches);
 832         spin_lock_irqsave(&cpu_rcache->lock, flags);
 833
 834         if (!iova_magazine_empty(cpu_rcache->loaded)) {
 835                 has_pfn = true;
 836         } else if (!iova_magazine_empty(cpu_rcache->prev)) {
 837                 swap(cpu_rcache->prev, cpu_rcache->loaded);
 838                 has_pfn = true;
 839         } else {
 840                 spin_lock(&rcache->lock);
 841                 if (rcache->depot) {
 842                         iova_magazine_free(cpu_rcache->loaded);
 843                         cpu_rcache->loaded = iova_depot_pop(rcache);
 844                         has_pfn = true;
 845                 }
 846                 spin_unlock(&rcache->lock);
 847         }
 848
 849         if (has_pfn)
 850                 iova_pfn = iova_magazine_pop(cpu_rcache->loaded, limit_pfn);
 851
 852         spin_unlock_irqrestore(&cpu_rcache->lock, flags);
 853
 854         return iova_pfn;
 855 }
 856
 857 /*
 858  * Try to satisfy IOVA allocation range from rcache.  Fail if requested
 859  * size is too big or the DMA limit we are given isn't satisfied by the
 860  * top element in the magazine.
 861  */
 862 static unsigned long iova_rcache_get(struct iova_domain *iovad,
 863                                      unsigned long size,
 864                                      unsigned long limit_pfn)
 865 {
 866         unsigned int log_size = order_base_2(size);
 867
 868         if (log_size >= IOVA_RANGE_CACHE_MAX_SIZE)
 869                 return 0;
 870
 871         return __iova_rcache_get(&iovad->rcaches[log_size], limit_pfn - size);
 872 }
 873
 874 /*
 875  * free rcache data structures.
 876  */
 877 static void free_iova_rcaches(struct iova_domain *iovad)
 878 {
 879         struct iova_rcache *rcache;
 880         struct iova_cpu_rcache *cpu_rcache;
 881         unsigned int cpu;
 882
 883         for (int i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
 884                 rcache = &iovad->rcaches[i];
 885                 if (!rcache->cpu_rcaches)
 886                         break;
 887                 for_each_possible_cpu(cpu) {
 888                         cpu_rcache = per_cpu_ptr(rcache->cpu_rcaches, cpu);
 889                         iova_magazine_free(cpu_rcache->loaded);
 890                         iova_magazine_free(cpu_rcache->prev);
 891                 }
 892                 free_percpu(rcache->cpu_rcaches);
 893                 cancel_delayed_work_sync(&rcache->work);
 894                 while (rcache->depot)
 895                         iova_magazine_free(iova_depot_pop(rcache));
 896         }
 897
 898         kfree(iovad->rcaches);
 899         iovad->rcaches = NULL;
 900 }
 901
 902 /*
 903  * free all the IOVA ranges cached by a cpu (used when cpu is unplugged)
 904  */
 905 static 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 /*
 923  * free all the IOVA ranges of global cache
 924  */
 925 static void free_global_cached_iovas(struct iova_domain *iovad)
 926 {
 927         struct iova_rcache *rcache;
 928         unsigned long flags;
 929
 930         for (int i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
 931                 rcache = &iovad->rcaches[i];
 932                 spin_lock_irqsave(&rcache->lock, flags);
 933                 while (rcache->depot) {
 934                         struct iova_magazine *mag = iova_depot_pop(rcache);
 935
 936                         iova_magazine_free_pfns(mag, iovad);
 937                         iova_magazine_free(mag);
 938                 }
 939                 spin_unlock_irqrestore(&rcache->lock, flags);
 940         }
 941 }
 942
 943 static int iova_cpuhp_dead(unsigned int cpu, struct hlist_node *node)
 944 {
 945         struct iova_domain *iovad;
 946
 947         iovad = hlist_entry_safe(node, struct iova_domain, cpuhp_dead);
 948
 949         free_cpu_cached_iovas(cpu, iovad);
 950         return 0;
 951 }
 952
 953 int iova_cache_get(void)
 954 {
 955         int err = -ENOMEM;
 956
 957         mutex_lock(&iova_cache_mutex);
 958         if (!iova_cache_users) {
 959                 iova_cache = kmem_cache_create("iommu_iova", sizeof(struct iova), 0,
 960                                                SLAB_HWCACHE_ALIGN, NULL);
 961                 if (!iova_cache)
 962                         goto out_err;
 963
 964                 iova_magazine_cache = kmem_cache_create("iommu_iova_magazine",
 965                                                         sizeof(struct iova_magazine),
 966                                                         0, SLAB_HWCACHE_ALIGN, NULL);
 967                 if (!iova_magazine_cache)
 968                         goto out_err;
 969
 970                 err = cpuhp_setup_state_multi(CPUHP_IOMMU_IOVA_DEAD, "iommu/iova:dead",
 971                                               NULL, iova_cpuhp_dead);
 972                 if (err) {
 973                         pr_err("IOVA: Couldn't register cpuhp handler: %pe\n", ERR_PTR(err));
 974                         goto out_err;
 975                 }
 976         }
 977
 978         iova_cache_users++;
 979         mutex_unlock(&iova_cache_mutex);
 980
 981         return 0;
 982
 983 out_err:
 984         kmem_cache_destroy(iova_cache);
 985         kmem_cache_destroy(iova_magazine_cache);
 986         mutex_unlock(&iova_cache_mutex);
 987         return err;
 988 }
 989 EXPORT_SYMBOL_GPL(iova_cache_get);
 990
 991 void iova_cache_put(void)
 992 {
 993         mutex_lock(&iova_cache_mutex);
 994         if (WARN_ON(!iova_cache_users)) {
 995                 mutex_unlock(&iova_cache_mutex);
 996                 return;
 997         }
 998         iova_cache_users--;
 999         if (!iova_cache_users) {
1000                 cpuhp_remove_multi_state(CPUHP_IOMMU_IOVA_DEAD);
1001                 kmem_cache_destroy(iova_cache);
1002                 kmem_cache_destroy(iova_magazine_cache);
1003         }
1004         mutex_unlock(&iova_cache_mutex);
1005 }
1006 EXPORT_SYMBOL_GPL(iova_cache_put);
1007
1008 MODULE_AUTHOR("Anil S Keshavamurthy <[email protected]>");
1009 MODULE_DESCRIPTION("IOMMU I/O Virtual Address management");
1010 MODULE_LICENSE("GPL");