1 // SPDX-License-Identifier: GPL-2.0-only
3 * Copyright © 2006-2009, Intel Corporation.
5 * Author: Anil S Keshavamurthy <anil.s.keshavamurthy@intel.com>
8 #include <linux/iova.h>
9 #include <linux/module.h>
10 #include <linux/slab.h>
11 #include <linux/smp.h>
12 #include <linux/bitops.h>
13 #include <linux/cpu.h>
15 /* The anchor node sits above the top of the usable address space */
16 #define IOVA_ANCHOR ~0UL
18 static bool iova_rcache_insert(struct iova_domain *iovad,
21 static unsigned long iova_rcache_get(struct iova_domain *iovad,
23 unsigned long limit_pfn);
24 static void init_iova_rcaches(struct iova_domain *iovad);
25 static void free_cpu_cached_iovas(unsigned int cpu, struct iova_domain *iovad);
26 static void free_iova_rcaches(struct iova_domain *iovad);
27 static void fq_destroy_all_entries(struct iova_domain *iovad);
28 static void fq_flush_timeout(struct timer_list *t);
30 static int iova_cpuhp_dead(unsigned int cpu, struct hlist_node *node)
32 struct iova_domain *iovad;
34 iovad = hlist_entry_safe(node, struct iova_domain, cpuhp_dead);
36 free_cpu_cached_iovas(cpu, iovad);
40 static void free_global_cached_iovas(struct iova_domain *iovad);
42 static struct iova *to_iova(struct rb_node *node)
44 return rb_entry(node, struct iova, node);
48 init_iova_domain(struct iova_domain *iovad, unsigned long granule,
49 unsigned long start_pfn)
52 * IOVA granularity will normally be equal to the smallest
53 * supported IOMMU page size; both *must* be capable of
54 * representing individual CPU pages exactly.
56 BUG_ON((granule > PAGE_SIZE) || !is_power_of_2(granule));
58 spin_lock_init(&iovad->iova_rbtree_lock);
59 iovad->rbroot = RB_ROOT;
60 iovad->cached_node = &iovad->anchor.node;
61 iovad->cached32_node = &iovad->anchor.node;
62 iovad->granule = granule;
63 iovad->start_pfn = start_pfn;
64 iovad->dma_32bit_pfn = 1UL << (32 - iova_shift(iovad));
65 iovad->max32_alloc_size = iovad->dma_32bit_pfn;
66 iovad->flush_cb = NULL;
68 iovad->anchor.pfn_lo = iovad->anchor.pfn_hi = IOVA_ANCHOR;
69 rb_link_node(&iovad->anchor.node, NULL, &iovad->rbroot.rb_node);
70 rb_insert_color(&iovad->anchor.node, &iovad->rbroot);
71 cpuhp_state_add_instance_nocalls(CPUHP_IOMMU_IOVA_DEAD, &iovad->cpuhp_dead);
72 init_iova_rcaches(iovad);
74 EXPORT_SYMBOL_GPL(init_iova_domain);
76 static bool has_iova_flush_queue(struct iova_domain *iovad)
81 static void free_iova_flush_queue(struct iova_domain *iovad)
83 if (!has_iova_flush_queue(iovad))
86 if (timer_pending(&iovad->fq_timer))
87 del_timer(&iovad->fq_timer);
89 fq_destroy_all_entries(iovad);
91 free_percpu(iovad->fq);
94 iovad->flush_cb = NULL;
95 iovad->entry_dtor = NULL;
98 int init_iova_flush_queue(struct iova_domain *iovad,
99 iova_flush_cb flush_cb, iova_entry_dtor entry_dtor)
101 struct iova_fq __percpu *queue;
104 atomic64_set(&iovad->fq_flush_start_cnt, 0);
105 atomic64_set(&iovad->fq_flush_finish_cnt, 0);
107 queue = alloc_percpu(struct iova_fq);
111 iovad->flush_cb = flush_cb;
112 iovad->entry_dtor = entry_dtor;
114 for_each_possible_cpu(cpu) {
117 fq = per_cpu_ptr(queue, cpu);
121 spin_lock_init(&fq->lock);
126 timer_setup(&iovad->fq_timer, fq_flush_timeout, 0);
127 atomic_set(&iovad->fq_timer_on, 0);
132 static struct rb_node *
133 __get_cached_rbnode(struct iova_domain *iovad, unsigned long limit_pfn)
135 if (limit_pfn <= iovad->dma_32bit_pfn)
136 return iovad->cached32_node;
138 return iovad->cached_node;
142 __cached_rbnode_insert_update(struct iova_domain *iovad, struct iova *new)
144 if (new->pfn_hi < iovad->dma_32bit_pfn)
145 iovad->cached32_node = &new->node;
147 iovad->cached_node = &new->node;
151 __cached_rbnode_delete_update(struct iova_domain *iovad, struct iova *free)
153 struct iova *cached_iova;
155 cached_iova = to_iova(iovad->cached32_node);
156 if (free == cached_iova ||
157 (free->pfn_hi < iovad->dma_32bit_pfn &&
158 free->pfn_lo >= cached_iova->pfn_lo)) {
159 iovad->cached32_node = rb_next(&free->node);
160 iovad->max32_alloc_size = iovad->dma_32bit_pfn;
163 cached_iova = to_iova(iovad->cached_node);
164 if (free->pfn_lo >= cached_iova->pfn_lo)
165 iovad->cached_node = rb_next(&free->node);
168 static struct rb_node *iova_find_limit(struct iova_domain *iovad, unsigned long limit_pfn)
170 struct rb_node *node, *next;
172 * Ideally what we'd like to judge here is whether limit_pfn is close
173 * enough to the highest-allocated IOVA that starting the allocation
174 * walk from the anchor node will be quicker than this initial work to
175 * find an exact starting point (especially if that ends up being the
176 * anchor node anyway). This is an incredibly crude approximation which
177 * only really helps the most likely case, but is at least trivially easy.
179 if (limit_pfn > iovad->dma_32bit_pfn)
180 return &iovad->anchor.node;
182 node = iovad->rbroot.rb_node;
183 while (to_iova(node)->pfn_hi < limit_pfn)
184 node = node->rb_right;
187 while (node->rb_left && to_iova(node->rb_left)->pfn_lo >= limit_pfn)
188 node = node->rb_left;
193 next = node->rb_left;
194 while (next->rb_right) {
195 next = next->rb_right;
196 if (to_iova(next)->pfn_lo >= limit_pfn) {
205 /* Insert the iova into domain rbtree by holding writer lock */
207 iova_insert_rbtree(struct rb_root *root, struct iova *iova,
208 struct rb_node *start)
210 struct rb_node **new, *parent = NULL;
212 new = (start) ? &start : &(root->rb_node);
213 /* Figure out where to put new node */
215 struct iova *this = to_iova(*new);
219 if (iova->pfn_lo < this->pfn_lo)
220 new = &((*new)->rb_left);
221 else if (iova->pfn_lo > this->pfn_lo)
222 new = &((*new)->rb_right);
224 WARN_ON(1); /* this should not happen */
228 /* Add new node and rebalance tree. */
229 rb_link_node(&iova->node, parent, new);
230 rb_insert_color(&iova->node, root);
233 static int __alloc_and_insert_iova_range(struct iova_domain *iovad,
234 unsigned long size, unsigned long limit_pfn,
235 struct iova *new, bool size_aligned)
237 struct rb_node *curr, *prev;
238 struct iova *curr_iova;
240 unsigned long new_pfn, retry_pfn;
241 unsigned long align_mask = ~0UL;
242 unsigned long high_pfn = limit_pfn, low_pfn = iovad->start_pfn;
245 align_mask <<= fls_long(size - 1);
247 /* Walk the tree backwards */
248 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
249 if (limit_pfn <= iovad->dma_32bit_pfn &&
250 size >= iovad->max32_alloc_size)
253 curr = __get_cached_rbnode(iovad, limit_pfn);
254 curr_iova = to_iova(curr);
255 retry_pfn = curr_iova->pfn_hi + 1;
259 high_pfn = min(high_pfn, curr_iova->pfn_lo);
260 new_pfn = (high_pfn - size) & align_mask;
262 curr = rb_prev(curr);
263 curr_iova = to_iova(curr);
264 } while (curr && new_pfn <= curr_iova->pfn_hi && new_pfn >= low_pfn);
266 if (high_pfn < size || new_pfn < low_pfn) {
267 if (low_pfn == iovad->start_pfn && retry_pfn < limit_pfn) {
268 high_pfn = limit_pfn;
270 curr = iova_find_limit(iovad, limit_pfn);
271 curr_iova = to_iova(curr);
274 iovad->max32_alloc_size = size;
278 /* pfn_lo will point to size aligned address if size_aligned is set */
279 new->pfn_lo = new_pfn;
280 new->pfn_hi = new->pfn_lo + size - 1;
282 /* If we have 'prev', it's a valid place to start the insertion. */
283 iova_insert_rbtree(&iovad->rbroot, new, prev);
284 __cached_rbnode_insert_update(iovad, new);
286 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
290 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
294 static struct kmem_cache *iova_cache;
295 static unsigned int iova_cache_users;
296 static DEFINE_MUTEX(iova_cache_mutex);
298 static struct iova *alloc_iova_mem(void)
300 return kmem_cache_zalloc(iova_cache, GFP_ATOMIC | __GFP_NOWARN);
303 static void free_iova_mem(struct iova *iova)
305 if (iova->pfn_lo != IOVA_ANCHOR)
306 kmem_cache_free(iova_cache, iova);
309 int iova_cache_get(void)
311 mutex_lock(&iova_cache_mutex);
312 if (!iova_cache_users) {
315 ret = cpuhp_setup_state_multi(CPUHP_IOMMU_IOVA_DEAD, "iommu/iova:dead", NULL,
318 mutex_unlock(&iova_cache_mutex);
319 pr_err("Couldn't register cpuhp handler\n");
323 iova_cache = kmem_cache_create(
324 "iommu_iova", sizeof(struct iova), 0,
325 SLAB_HWCACHE_ALIGN, NULL);
327 cpuhp_remove_multi_state(CPUHP_IOMMU_IOVA_DEAD);
328 mutex_unlock(&iova_cache_mutex);
329 pr_err("Couldn't create iova cache\n");
335 mutex_unlock(&iova_cache_mutex);
339 EXPORT_SYMBOL_GPL(iova_cache_get);
341 void iova_cache_put(void)
343 mutex_lock(&iova_cache_mutex);
344 if (WARN_ON(!iova_cache_users)) {
345 mutex_unlock(&iova_cache_mutex);
349 if (!iova_cache_users) {
350 cpuhp_remove_multi_state(CPUHP_IOMMU_IOVA_DEAD);
351 kmem_cache_destroy(iova_cache);
353 mutex_unlock(&iova_cache_mutex);
355 EXPORT_SYMBOL_GPL(iova_cache_put);
358 * alloc_iova - allocates an iova
359 * @iovad: - iova domain in question
360 * @size: - size of page frames to allocate
361 * @limit_pfn: - max limit address
362 * @size_aligned: - set if size_aligned address range is required
363 * This function allocates an iova in the range iovad->start_pfn to limit_pfn,
364 * searching top-down from limit_pfn to iovad->start_pfn. If the size_aligned
365 * flag is set then the allocated address iova->pfn_lo will be naturally
366 * aligned on roundup_power_of_two(size).
369 alloc_iova(struct iova_domain *iovad, unsigned long size,
370 unsigned long limit_pfn,
373 struct iova *new_iova;
376 new_iova = alloc_iova_mem();
380 ret = __alloc_and_insert_iova_range(iovad, size, limit_pfn + 1,
381 new_iova, size_aligned);
384 free_iova_mem(new_iova);
390 EXPORT_SYMBOL_GPL(alloc_iova);
393 private_find_iova(struct iova_domain *iovad, unsigned long pfn)
395 struct rb_node *node = iovad->rbroot.rb_node;
397 assert_spin_locked(&iovad->iova_rbtree_lock);
400 struct iova *iova = to_iova(node);
402 if (pfn < iova->pfn_lo)
403 node = node->rb_left;
404 else if (pfn > iova->pfn_hi)
405 node = node->rb_right;
407 return iova; /* pfn falls within iova's range */
413 static void remove_iova(struct iova_domain *iovad, struct iova *iova)
415 assert_spin_locked(&iovad->iova_rbtree_lock);
416 __cached_rbnode_delete_update(iovad, iova);
417 rb_erase(&iova->node, &iovad->rbroot);
421 * find_iova - finds an iova for a given pfn
422 * @iovad: - iova domain in question.
423 * @pfn: - page frame number
424 * This function finds and returns an iova belonging to the
425 * given domain which matches the given pfn.
427 struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn)
432 /* Take the lock so that no other thread is manipulating the rbtree */
433 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
434 iova = private_find_iova(iovad, pfn);
435 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
438 EXPORT_SYMBOL_GPL(find_iova);
441 * __free_iova - frees the given iova
442 * @iovad: iova domain in question.
443 * @iova: iova in question.
444 * Frees the given iova belonging to the giving domain
447 __free_iova(struct iova_domain *iovad, struct iova *iova)
451 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
452 remove_iova(iovad, iova);
453 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
456 EXPORT_SYMBOL_GPL(__free_iova);
459 * free_iova - finds and frees the iova for a given pfn
460 * @iovad: - iova domain in question.
461 * @pfn: - pfn that is allocated previously
462 * This functions finds an iova for a given pfn and then
463 * frees the iova from that domain.
466 free_iova(struct iova_domain *iovad, unsigned long pfn)
471 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
472 iova = private_find_iova(iovad, pfn);
474 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
477 remove_iova(iovad, iova);
478 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
481 EXPORT_SYMBOL_GPL(free_iova);
484 * alloc_iova_fast - allocates an iova from rcache
485 * @iovad: - iova domain in question
486 * @size: - size of page frames to allocate
487 * @limit_pfn: - max limit address
488 * @flush_rcache: - set to flush rcache on regular allocation failure
489 * This function tries to satisfy an iova allocation from the rcache,
490 * and falls back to regular allocation on failure. If regular allocation
491 * fails too and the flush_rcache flag is set then the rcache will be flushed.
494 alloc_iova_fast(struct iova_domain *iovad, unsigned long size,
495 unsigned long limit_pfn, bool flush_rcache)
497 unsigned long iova_pfn;
498 struct iova *new_iova;
500 iova_pfn = iova_rcache_get(iovad, size, limit_pfn + 1);
505 new_iova = alloc_iova(iovad, size, limit_pfn, true);
512 /* Try replenishing IOVAs by flushing rcache. */
513 flush_rcache = false;
514 for_each_online_cpu(cpu)
515 free_cpu_cached_iovas(cpu, iovad);
516 free_global_cached_iovas(iovad);
520 return new_iova->pfn_lo;
524 * free_iova_fast - free iova pfn range into rcache
525 * @iovad: - iova domain in question.
526 * @pfn: - pfn that is allocated previously
527 * @size: - # of pages in range
528 * This functions frees an iova range by trying to put it into the rcache,
529 * falling back to regular iova deallocation via free_iova() if this fails.
532 free_iova_fast(struct iova_domain *iovad, unsigned long pfn, unsigned long size)
534 if (iova_rcache_insert(iovad, pfn, size))
537 free_iova(iovad, pfn);
540 #define fq_ring_for_each(i, fq) \
541 for ((i) = (fq)->head; (i) != (fq)->tail; (i) = ((i) + 1) % IOVA_FQ_SIZE)
543 static inline bool fq_full(struct iova_fq *fq)
545 assert_spin_locked(&fq->lock);
546 return (((fq->tail + 1) % IOVA_FQ_SIZE) == fq->head);
549 static inline unsigned fq_ring_add(struct iova_fq *fq)
551 unsigned idx = fq->tail;
553 assert_spin_locked(&fq->lock);
555 fq->tail = (idx + 1) % IOVA_FQ_SIZE;
560 static void fq_ring_free(struct iova_domain *iovad, struct iova_fq *fq)
562 u64 counter = atomic64_read(&iovad->fq_flush_finish_cnt);
565 assert_spin_locked(&fq->lock);
567 fq_ring_for_each(idx, fq) {
569 if (fq->entries[idx].counter >= counter)
572 if (iovad->entry_dtor)
573 iovad->entry_dtor(fq->entries[idx].data);
575 free_iova_fast(iovad,
576 fq->entries[idx].iova_pfn,
577 fq->entries[idx].pages);
579 fq->head = (fq->head + 1) % IOVA_FQ_SIZE;
583 static void iova_domain_flush(struct iova_domain *iovad)
585 atomic64_inc(&iovad->fq_flush_start_cnt);
586 iovad->flush_cb(iovad);
587 atomic64_inc(&iovad->fq_flush_finish_cnt);
590 static void fq_destroy_all_entries(struct iova_domain *iovad)
595 * This code runs when the iova_domain is being detroyed, so don't
596 * bother to free iovas, just call the entry_dtor on all remaining
599 if (!iovad->entry_dtor)
602 for_each_possible_cpu(cpu) {
603 struct iova_fq *fq = per_cpu_ptr(iovad->fq, cpu);
606 fq_ring_for_each(idx, fq)
607 iovad->entry_dtor(fq->entries[idx].data);
611 static void fq_flush_timeout(struct timer_list *t)
613 struct iova_domain *iovad = from_timer(iovad, t, fq_timer);
616 atomic_set(&iovad->fq_timer_on, 0);
617 iova_domain_flush(iovad);
619 for_each_possible_cpu(cpu) {
623 fq = per_cpu_ptr(iovad->fq, cpu);
624 spin_lock_irqsave(&fq->lock, flags);
625 fq_ring_free(iovad, fq);
626 spin_unlock_irqrestore(&fq->lock, flags);
630 void queue_iova(struct iova_domain *iovad,
631 unsigned long pfn, unsigned long pages,
639 * Order against the IOMMU driver's pagetable update from unmapping
640 * @pte, to guarantee that iova_domain_flush() observes that if called
641 * from a different CPU before we release the lock below. Full barrier
642 * so it also pairs with iommu_dma_init_fq() to avoid seeing partially
643 * written fq state here.
647 fq = raw_cpu_ptr(iovad->fq);
648 spin_lock_irqsave(&fq->lock, flags);
651 * First remove all entries from the flush queue that have already been
652 * flushed out on another CPU. This makes the fq_full() check below less
655 fq_ring_free(iovad, fq);
658 iova_domain_flush(iovad);
659 fq_ring_free(iovad, fq);
662 idx = fq_ring_add(fq);
664 fq->entries[idx].iova_pfn = pfn;
665 fq->entries[idx].pages = pages;
666 fq->entries[idx].data = data;
667 fq->entries[idx].counter = atomic64_read(&iovad->fq_flush_start_cnt);
669 spin_unlock_irqrestore(&fq->lock, flags);
671 /* Avoid false sharing as much as possible. */
672 if (!atomic_read(&iovad->fq_timer_on) &&
673 !atomic_xchg(&iovad->fq_timer_on, 1))
674 mod_timer(&iovad->fq_timer,
675 jiffies + msecs_to_jiffies(IOVA_FQ_TIMEOUT));
679 * put_iova_domain - destroys the iova domain
680 * @iovad: - iova domain in question.
681 * All the iova's in that domain are destroyed.
683 void put_iova_domain(struct iova_domain *iovad)
685 struct iova *iova, *tmp;
687 cpuhp_state_remove_instance_nocalls(CPUHP_IOMMU_IOVA_DEAD,
690 free_iova_flush_queue(iovad);
691 free_iova_rcaches(iovad);
692 rbtree_postorder_for_each_entry_safe(iova, tmp, &iovad->rbroot, node)
695 EXPORT_SYMBOL_GPL(put_iova_domain);
698 __is_range_overlap(struct rb_node *node,
699 unsigned long pfn_lo, unsigned long pfn_hi)
701 struct iova *iova = to_iova(node);
703 if ((pfn_lo <= iova->pfn_hi) && (pfn_hi >= iova->pfn_lo))
708 static inline struct iova *
709 alloc_and_init_iova(unsigned long pfn_lo, unsigned long pfn_hi)
713 iova = alloc_iova_mem();
715 iova->pfn_lo = pfn_lo;
716 iova->pfn_hi = pfn_hi;
723 __insert_new_range(struct iova_domain *iovad,
724 unsigned long pfn_lo, unsigned long pfn_hi)
728 iova = alloc_and_init_iova(pfn_lo, pfn_hi);
730 iova_insert_rbtree(&iovad->rbroot, iova, NULL);
736 __adjust_overlap_range(struct iova *iova,
737 unsigned long *pfn_lo, unsigned long *pfn_hi)
739 if (*pfn_lo < iova->pfn_lo)
740 iova->pfn_lo = *pfn_lo;
741 if (*pfn_hi > iova->pfn_hi)
742 *pfn_lo = iova->pfn_hi + 1;
746 * reserve_iova - reserves an iova in the given range
747 * @iovad: - iova domain pointer
748 * @pfn_lo: - lower page frame address
749 * @pfn_hi:- higher pfn adderss
750 * This function allocates reserves the address range from pfn_lo to pfn_hi so
751 * that this address is not dished out as part of alloc_iova.
754 reserve_iova(struct iova_domain *iovad,
755 unsigned long pfn_lo, unsigned long pfn_hi)
757 struct rb_node *node;
760 unsigned int overlap = 0;
762 /* Don't allow nonsensical pfns */
763 if (WARN_ON((pfn_hi | pfn_lo) > (ULLONG_MAX >> iova_shift(iovad))))
766 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
767 for (node = rb_first(&iovad->rbroot); node; node = rb_next(node)) {
768 if (__is_range_overlap(node, pfn_lo, pfn_hi)) {
769 iova = to_iova(node);
770 __adjust_overlap_range(iova, &pfn_lo, &pfn_hi);
771 if ((pfn_lo >= iova->pfn_lo) &&
772 (pfn_hi <= iova->pfn_hi))
780 /* We are here either because this is the first reserver node
781 * or need to insert remaining non overlap addr range
783 iova = __insert_new_range(iovad, pfn_lo, pfn_hi);
786 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
789 EXPORT_SYMBOL_GPL(reserve_iova);
792 * Magazine caches for IOVA ranges. For an introduction to magazines,
793 * see the USENIX 2001 paper "Magazines and Vmem: Extending the Slab
794 * Allocator to Many CPUs and Arbitrary Resources" by Bonwick and Adams.
795 * For simplicity, we use a static magazine size and don't implement the
796 * dynamic size tuning described in the paper.
799 #define IOVA_MAG_SIZE 128
801 struct iova_magazine {
803 unsigned long pfns[IOVA_MAG_SIZE];
806 struct iova_cpu_rcache {
808 struct iova_magazine *loaded;
809 struct iova_magazine *prev;
812 static struct iova_magazine *iova_magazine_alloc(gfp_t flags)
814 return kzalloc(sizeof(struct iova_magazine), flags);
817 static void iova_magazine_free(struct iova_magazine *mag)
823 iova_magazine_free_pfns(struct iova_magazine *mag, struct iova_domain *iovad)
831 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
833 for (i = 0 ; i < mag->size; ++i) {
834 struct iova *iova = private_find_iova(iovad, mag->pfns[i]);
839 remove_iova(iovad, iova);
843 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
848 static bool iova_magazine_full(struct iova_magazine *mag)
850 return (mag && mag->size == IOVA_MAG_SIZE);
853 static bool iova_magazine_empty(struct iova_magazine *mag)
855 return (!mag || mag->size == 0);
858 static unsigned long iova_magazine_pop(struct iova_magazine *mag,
859 unsigned long limit_pfn)
864 BUG_ON(iova_magazine_empty(mag));
866 /* Only fall back to the rbtree if we have no suitable pfns at all */
867 for (i = mag->size - 1; mag->pfns[i] > limit_pfn; i--)
871 /* Swap it to pop it */
873 mag->pfns[i] = mag->pfns[--mag->size];
878 static void iova_magazine_push(struct iova_magazine *mag, unsigned long pfn)
880 BUG_ON(iova_magazine_full(mag));
882 mag->pfns[mag->size++] = pfn;
885 static void init_iova_rcaches(struct iova_domain *iovad)
887 struct iova_cpu_rcache *cpu_rcache;
888 struct iova_rcache *rcache;
892 for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
893 rcache = &iovad->rcaches[i];
894 spin_lock_init(&rcache->lock);
895 rcache->depot_size = 0;
896 rcache->cpu_rcaches = __alloc_percpu(sizeof(*cpu_rcache), cache_line_size());
897 if (WARN_ON(!rcache->cpu_rcaches))
899 for_each_possible_cpu(cpu) {
900 cpu_rcache = per_cpu_ptr(rcache->cpu_rcaches, cpu);
901 spin_lock_init(&cpu_rcache->lock);
902 cpu_rcache->loaded = iova_magazine_alloc(GFP_KERNEL);
903 cpu_rcache->prev = iova_magazine_alloc(GFP_KERNEL);
909 * Try inserting IOVA range starting with 'iova_pfn' into 'rcache', and
910 * return true on success. Can fail if rcache is full and we can't free
911 * space, and free_iova() (our only caller) will then return the IOVA
912 * range to the rbtree instead.
914 static bool __iova_rcache_insert(struct iova_domain *iovad,
915 struct iova_rcache *rcache,
916 unsigned long iova_pfn)
918 struct iova_magazine *mag_to_free = NULL;
919 struct iova_cpu_rcache *cpu_rcache;
920 bool can_insert = false;
923 cpu_rcache = raw_cpu_ptr(rcache->cpu_rcaches);
924 spin_lock_irqsave(&cpu_rcache->lock, flags);
926 if (!iova_magazine_full(cpu_rcache->loaded)) {
928 } else if (!iova_magazine_full(cpu_rcache->prev)) {
929 swap(cpu_rcache->prev, cpu_rcache->loaded);
932 struct iova_magazine *new_mag = iova_magazine_alloc(GFP_ATOMIC);
935 spin_lock(&rcache->lock);
936 if (rcache->depot_size < MAX_GLOBAL_MAGS) {
937 rcache->depot[rcache->depot_size++] =
940 mag_to_free = cpu_rcache->loaded;
942 spin_unlock(&rcache->lock);
944 cpu_rcache->loaded = new_mag;
950 iova_magazine_push(cpu_rcache->loaded, iova_pfn);
952 spin_unlock_irqrestore(&cpu_rcache->lock, flags);
955 iova_magazine_free_pfns(mag_to_free, iovad);
956 iova_magazine_free(mag_to_free);
962 static bool iova_rcache_insert(struct iova_domain *iovad, unsigned long pfn,
965 unsigned int log_size = order_base_2(size);
967 if (log_size >= IOVA_RANGE_CACHE_MAX_SIZE)
970 return __iova_rcache_insert(iovad, &iovad->rcaches[log_size], pfn);
974 * Caller wants to allocate a new IOVA range from 'rcache'. If we can
975 * satisfy the request, return a matching non-NULL range and remove
976 * it from the 'rcache'.
978 static unsigned long __iova_rcache_get(struct iova_rcache *rcache,
979 unsigned long limit_pfn)
981 struct iova_cpu_rcache *cpu_rcache;
982 unsigned long iova_pfn = 0;
983 bool has_pfn = false;
986 cpu_rcache = raw_cpu_ptr(rcache->cpu_rcaches);
987 spin_lock_irqsave(&cpu_rcache->lock, flags);
989 if (!iova_magazine_empty(cpu_rcache->loaded)) {
991 } else if (!iova_magazine_empty(cpu_rcache->prev)) {
992 swap(cpu_rcache->prev, cpu_rcache->loaded);
995 spin_lock(&rcache->lock);
996 if (rcache->depot_size > 0) {
997 iova_magazine_free(cpu_rcache->loaded);
998 cpu_rcache->loaded = rcache->depot[--rcache->depot_size];
1001 spin_unlock(&rcache->lock);
1005 iova_pfn = iova_magazine_pop(cpu_rcache->loaded, limit_pfn);
1007 spin_unlock_irqrestore(&cpu_rcache->lock, flags);
1013 * Try to satisfy IOVA allocation range from rcache. Fail if requested
1014 * size is too big or the DMA limit we are given isn't satisfied by the
1015 * top element in the magazine.
1017 static unsigned long iova_rcache_get(struct iova_domain *iovad,
1019 unsigned long limit_pfn)
1021 unsigned int log_size = order_base_2(size);
1023 if (log_size >= IOVA_RANGE_CACHE_MAX_SIZE)
1026 return __iova_rcache_get(&iovad->rcaches[log_size], limit_pfn - size);
1030 * free rcache data structures.
1032 static void free_iova_rcaches(struct iova_domain *iovad)
1034 struct iova_rcache *rcache;
1035 struct iova_cpu_rcache *cpu_rcache;
1039 for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
1040 rcache = &iovad->rcaches[i];
1041 for_each_possible_cpu(cpu) {
1042 cpu_rcache = per_cpu_ptr(rcache->cpu_rcaches, cpu);
1043 iova_magazine_free(cpu_rcache->loaded);
1044 iova_magazine_free(cpu_rcache->prev);
1046 free_percpu(rcache->cpu_rcaches);
1047 for (j = 0; j < rcache->depot_size; ++j)
1048 iova_magazine_free(rcache->depot[j]);
1053 * free all the IOVA ranges cached by a cpu (used when cpu is unplugged)
1055 static void free_cpu_cached_iovas(unsigned int cpu, struct iova_domain *iovad)
1057 struct iova_cpu_rcache *cpu_rcache;
1058 struct iova_rcache *rcache;
1059 unsigned long flags;
1062 for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
1063 rcache = &iovad->rcaches[i];
1064 cpu_rcache = per_cpu_ptr(rcache->cpu_rcaches, cpu);
1065 spin_lock_irqsave(&cpu_rcache->lock, flags);
1066 iova_magazine_free_pfns(cpu_rcache->loaded, iovad);
1067 iova_magazine_free_pfns(cpu_rcache->prev, iovad);
1068 spin_unlock_irqrestore(&cpu_rcache->lock, flags);
1073 * free all the IOVA ranges of global cache
1075 static void free_global_cached_iovas(struct iova_domain *iovad)
1077 struct iova_rcache *rcache;
1078 unsigned long flags;
1081 for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
1082 rcache = &iovad->rcaches[i];
1083 spin_lock_irqsave(&rcache->lock, flags);
1084 for (j = 0; j < rcache->depot_size; ++j) {
1085 iova_magazine_free_pfns(rcache->depot[j], iovad);
1086 iova_magazine_free(rcache->depot[j]);
1088 rcache->depot_size = 0;
1089 spin_unlock_irqrestore(&rcache->lock, flags);
1092 MODULE_AUTHOR("Anil S Keshavamurthy <anil.s.keshavamurthy@intel.com>");
1093 MODULE_LICENSE("GPL");