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