blob: 9dd8208312c2e75874ce70dcc6008a166eb5ffca [file] [log] [blame]
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -07001/*
David Woodhousea15a5192009-07-01 18:49:06 +01002 * Copyright © 2006-2009, Intel Corporation.
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -07003 *
David Woodhousea15a5192009-07-01 18:49:06 +01004 * This program is free software; you can redistribute it and/or modify it
5 * under the terms and conditions of the GNU General Public License,
6 * version 2, as published by the Free Software Foundation.
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -07007 *
David Woodhousea15a5192009-07-01 18:49:06 +01008 * This program is distributed in the hope it will be useful, but WITHOUT
9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
11 * more details.
12 *
13 * You should have received a copy of the GNU General Public License along with
14 * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
15 * Place - Suite 330, Boston, MA 02111-1307 USA.
16 *
mark gross98bcef52008-02-23 15:23:35 -080017 * Author: Anil S Keshavamurthy <anil.s.keshavamurthy@intel.com>
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -070018 */
19
Kay, Allen M38717942008-09-09 18:37:29 +030020#include <linux/iova.h>
Robin Murphy85b45452015-01-12 17:51:14 +000021#include <linux/slab.h>
22
23static struct kmem_cache *iommu_iova_cache;
24
25int iommu_iova_cache_init(void)
26{
27 int ret = 0;
28
29 iommu_iova_cache = kmem_cache_create("iommu_iova",
30 sizeof(struct iova),
31 0,
32 SLAB_HWCACHE_ALIGN,
33 NULL);
34 if (!iommu_iova_cache) {
35 pr_err("Couldn't create iova cache\n");
36 ret = -ENOMEM;
37 }
38
39 return ret;
40}
41
42void iommu_iova_cache_destroy(void)
43{
44 kmem_cache_destroy(iommu_iova_cache);
45}
46
47struct iova *alloc_iova_mem(void)
48{
49 return kmem_cache_alloc(iommu_iova_cache, GFP_ATOMIC);
50}
51
52void free_iova_mem(struct iova *iova)
53{
54 kmem_cache_free(iommu_iova_cache, iova);
55}
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -070056
57void
Robin Murphy0fb5fe82015-01-12 17:51:16 +000058init_iova_domain(struct iova_domain *iovad, unsigned long granule,
59 unsigned long start_pfn, unsigned long pfn_32bit)
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -070060{
Robin Murphy0fb5fe82015-01-12 17:51:16 +000061 /*
62 * IOVA granularity will normally be equal to the smallest
63 * supported IOMMU page size; both *must* be capable of
64 * representing individual CPU pages exactly.
65 */
66 BUG_ON((granule > PAGE_SIZE) || !is_power_of_2(granule));
67
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -070068 spin_lock_init(&iovad->iova_rbtree_lock);
69 iovad->rbroot = RB_ROOT;
70 iovad->cached32_node = NULL;
Robin Murphy0fb5fe82015-01-12 17:51:16 +000071 iovad->granule = granule;
Robin Murphy1b722502015-01-12 17:51:15 +000072 iovad->start_pfn = start_pfn;
David Millerf6611972008-02-06 01:36:23 -080073 iovad->dma_32bit_pfn = pfn_32bit;
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -070074}
75
76static struct rb_node *
77__get_cached_rbnode(struct iova_domain *iovad, unsigned long *limit_pfn)
78{
David Millerf6611972008-02-06 01:36:23 -080079 if ((*limit_pfn != iovad->dma_32bit_pfn) ||
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -070080 (iovad->cached32_node == NULL))
81 return rb_last(&iovad->rbroot);
82 else {
83 struct rb_node *prev_node = rb_prev(iovad->cached32_node);
84 struct iova *curr_iova =
85 container_of(iovad->cached32_node, struct iova, node);
86 *limit_pfn = curr_iova->pfn_lo - 1;
87 return prev_node;
88 }
89}
90
91static void
92__cached_rbnode_insert_update(struct iova_domain *iovad,
93 unsigned long limit_pfn, struct iova *new)
94{
David Millerf6611972008-02-06 01:36:23 -080095 if (limit_pfn != iovad->dma_32bit_pfn)
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -070096 return;
97 iovad->cached32_node = &new->node;
98}
99
100static void
101__cached_rbnode_delete_update(struct iova_domain *iovad, struct iova *free)
102{
103 struct iova *cached_iova;
104 struct rb_node *curr;
105
106 if (!iovad->cached32_node)
107 return;
108 curr = iovad->cached32_node;
109 cached_iova = container_of(curr, struct iova, node);
110
Chris Wright1c9fc3d2011-05-28 13:15:04 -0500111 if (free->pfn_lo >= cached_iova->pfn_lo) {
112 struct rb_node *node = rb_next(&free->node);
113 struct iova *iova = container_of(node, struct iova, node);
114
115 /* only cache if it's below 32bit pfn */
116 if (node && iova->pfn_lo < iovad->dma_32bit_pfn)
117 iovad->cached32_node = node;
118 else
119 iovad->cached32_node = NULL;
120 }
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700121}
122
Keshavamurthy, Anil Sf76aec72007-10-21 16:41:58 -0700123/* Computes the padding size required, to make the
124 * the start address naturally aligned on its size
125 */
126static int
127iova_get_pad_size(int size, unsigned int limit_pfn)
128{
129 unsigned int pad_size = 0;
130 unsigned int order = ilog2(size);
131
132 if (order)
133 pad_size = (limit_pfn + 1) % (1 << order);
134
135 return pad_size;
136}
137
mark grossddf02882008-03-04 15:22:04 -0800138static int __alloc_and_insert_iova_range(struct iova_domain *iovad,
139 unsigned long size, unsigned long limit_pfn,
140 struct iova *new, bool size_aligned)
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700141{
mark grossddf02882008-03-04 15:22:04 -0800142 struct rb_node *prev, *curr = NULL;
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700143 unsigned long flags;
144 unsigned long saved_pfn;
Keshavamurthy, Anil Sf76aec72007-10-21 16:41:58 -0700145 unsigned int pad_size = 0;
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700146
147 /* Walk the tree backwards */
148 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
149 saved_pfn = limit_pfn;
150 curr = __get_cached_rbnode(iovad, &limit_pfn);
mark grossddf02882008-03-04 15:22:04 -0800151 prev = curr;
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700152 while (curr) {
153 struct iova *curr_iova = container_of(curr, struct iova, node);
mark grossddf02882008-03-04 15:22:04 -0800154
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700155 if (limit_pfn < curr_iova->pfn_lo)
156 goto move_left;
Keshavamurthy, Anil Sf76aec72007-10-21 16:41:58 -0700157 else if (limit_pfn < curr_iova->pfn_hi)
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700158 goto adjust_limit_pfn;
Keshavamurthy, Anil Sf76aec72007-10-21 16:41:58 -0700159 else {
160 if (size_aligned)
161 pad_size = iova_get_pad_size(size, limit_pfn);
162 if ((curr_iova->pfn_hi + size + pad_size) <= limit_pfn)
163 break; /* found a free slot */
164 }
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700165adjust_limit_pfn:
166 limit_pfn = curr_iova->pfn_lo - 1;
167move_left:
mark grossddf02882008-03-04 15:22:04 -0800168 prev = curr;
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700169 curr = rb_prev(curr);
170 }
171
Keshavamurthy, Anil Sf76aec72007-10-21 16:41:58 -0700172 if (!curr) {
173 if (size_aligned)
174 pad_size = iova_get_pad_size(size, limit_pfn);
Robin Murphy1b722502015-01-12 17:51:15 +0000175 if ((iovad->start_pfn + size + pad_size) > limit_pfn) {
Keshavamurthy, Anil Sf76aec72007-10-21 16:41:58 -0700176 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
177 return -ENOMEM;
178 }
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700179 }
Keshavamurthy, Anil Sf76aec72007-10-21 16:41:58 -0700180
181 /* pfn_lo will point to size aligned address if size_aligned is set */
182 new->pfn_lo = limit_pfn - (size + pad_size) + 1;
183 new->pfn_hi = new->pfn_lo + size - 1;
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700184
mark grossddf02882008-03-04 15:22:04 -0800185 /* Insert the new_iova into domain rbtree by holding writer lock */
186 /* Add new node and rebalance tree. */
187 {
David Woodhousea15a5192009-07-01 18:49:06 +0100188 struct rb_node **entry, *parent = NULL;
189
190 /* If we have 'prev', it's a valid place to start the
191 insertion. Otherwise, start from the root. */
192 if (prev)
193 entry = &prev;
194 else
195 entry = &iovad->rbroot.rb_node;
196
mark grossddf02882008-03-04 15:22:04 -0800197 /* Figure out where to put new node */
198 while (*entry) {
199 struct iova *this = container_of(*entry,
200 struct iova, node);
201 parent = *entry;
202
203 if (new->pfn_lo < this->pfn_lo)
204 entry = &((*entry)->rb_left);
205 else if (new->pfn_lo > this->pfn_lo)
206 entry = &((*entry)->rb_right);
207 else
208 BUG(); /* this should not happen */
209 }
210
211 /* Add new node and rebalance tree. */
212 rb_link_node(&new->node, parent, entry);
213 rb_insert_color(&new->node, &iovad->rbroot);
214 }
215 __cached_rbnode_insert_update(iovad, saved_pfn, new);
216
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700217 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
mark grossddf02882008-03-04 15:22:04 -0800218
219
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700220 return 0;
221}
222
223static void
224iova_insert_rbtree(struct rb_root *root, struct iova *iova)
225{
226 struct rb_node **new = &(root->rb_node), *parent = NULL;
227 /* Figure out where to put new node */
228 while (*new) {
229 struct iova *this = container_of(*new, struct iova, node);
230 parent = *new;
231
232 if (iova->pfn_lo < this->pfn_lo)
233 new = &((*new)->rb_left);
234 else if (iova->pfn_lo > this->pfn_lo)
235 new = &((*new)->rb_right);
236 else
237 BUG(); /* this should not happen */
238 }
239 /* Add new node and rebalance tree. */
240 rb_link_node(&iova->node, parent, new);
241 rb_insert_color(&iova->node, root);
242}
243
244/**
245 * alloc_iova - allocates an iova
Masanari Iida07db0402012-07-22 02:21:32 +0900246 * @iovad: - iova domain in question
247 * @size: - size of page frames to allocate
248 * @limit_pfn: - max limit address
249 * @size_aligned: - set if size_aligned address range is required
Robin Murphy1b722502015-01-12 17:51:15 +0000250 * This function allocates an iova in the range iovad->start_pfn to limit_pfn,
251 * searching top-down from limit_pfn to iovad->start_pfn. If the size_aligned
Keshavamurthy, Anil Sf76aec72007-10-21 16:41:58 -0700252 * flag is set then the allocated address iova->pfn_lo will be naturally
253 * aligned on roundup_power_of_two(size).
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700254 */
255struct iova *
256alloc_iova(struct iova_domain *iovad, unsigned long size,
Keshavamurthy, Anil Sf76aec72007-10-21 16:41:58 -0700257 unsigned long limit_pfn,
258 bool size_aligned)
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700259{
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700260 struct iova *new_iova;
261 int ret;
262
263 new_iova = alloc_iova_mem();
264 if (!new_iova)
265 return NULL;
266
Keshavamurthy, Anil Sf76aec72007-10-21 16:41:58 -0700267 /* If size aligned is set then round the size to
268 * to next power of two.
269 */
270 if (size_aligned)
271 size = __roundup_pow_of_two(size);
272
mark grossddf02882008-03-04 15:22:04 -0800273 ret = __alloc_and_insert_iova_range(iovad, size, limit_pfn,
274 new_iova, size_aligned);
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700275
276 if (ret) {
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700277 free_iova_mem(new_iova);
278 return NULL;
279 }
280
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700281 return new_iova;
282}
283
284/**
285 * find_iova - find's an iova for a given pfn
Masanari Iida07db0402012-07-22 02:21:32 +0900286 * @iovad: - iova domain in question.
287 * @pfn: - page frame number
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700288 * This function finds and returns an iova belonging to the
289 * given doamin which matches the given pfn.
290 */
291struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn)
292{
293 unsigned long flags;
294 struct rb_node *node;
295
296 /* Take the lock so that no other thread is manipulating the rbtree */
297 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
298 node = iovad->rbroot.rb_node;
299 while (node) {
300 struct iova *iova = container_of(node, struct iova, node);
301
302 /* If pfn falls within iova's range, return iova */
303 if ((pfn >= iova->pfn_lo) && (pfn <= iova->pfn_hi)) {
304 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
305 /* We are not holding the lock while this iova
306 * is referenced by the caller as the same thread
307 * which called this function also calls __free_iova()
Masanari Iida07db0402012-07-22 02:21:32 +0900308 * and it is by design that only one thread can possibly
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700309 * reference a particular iova and hence no conflict.
310 */
311 return iova;
312 }
313
314 if (pfn < iova->pfn_lo)
315 node = node->rb_left;
316 else if (pfn > iova->pfn_lo)
317 node = node->rb_right;
318 }
319
320 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
321 return NULL;
322}
323
324/**
325 * __free_iova - frees the given iova
326 * @iovad: iova domain in question.
327 * @iova: iova in question.
328 * Frees the given iova belonging to the giving domain
329 */
330void
331__free_iova(struct iova_domain *iovad, struct iova *iova)
332{
333 unsigned long flags;
334
335 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
336 __cached_rbnode_delete_update(iovad, iova);
337 rb_erase(&iova->node, &iovad->rbroot);
338 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
339 free_iova_mem(iova);
340}
341
342/**
343 * free_iova - finds and frees the iova for a given pfn
344 * @iovad: - iova domain in question.
345 * @pfn: - pfn that is allocated previously
346 * This functions finds an iova for a given pfn and then
347 * frees the iova from that domain.
348 */
349void
350free_iova(struct iova_domain *iovad, unsigned long pfn)
351{
352 struct iova *iova = find_iova(iovad, pfn);
353 if (iova)
354 __free_iova(iovad, iova);
355
356}
357
358/**
359 * put_iova_domain - destroys the iova doamin
360 * @iovad: - iova domain in question.
361 * All the iova's in that domain are destroyed.
362 */
363void put_iova_domain(struct iova_domain *iovad)
364{
365 struct rb_node *node;
366 unsigned long flags;
367
368 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
369 node = rb_first(&iovad->rbroot);
370 while (node) {
371 struct iova *iova = container_of(node, struct iova, node);
372 rb_erase(node, &iovad->rbroot);
373 free_iova_mem(iova);
374 node = rb_first(&iovad->rbroot);
375 }
376 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
377}
378
379static int
380__is_range_overlap(struct rb_node *node,
381 unsigned long pfn_lo, unsigned long pfn_hi)
382{
383 struct iova *iova = container_of(node, struct iova, node);
384
385 if ((pfn_lo <= iova->pfn_hi) && (pfn_hi >= iova->pfn_lo))
386 return 1;
387 return 0;
388}
389
Jiang Liu75f05562014-02-19 14:07:37 +0800390static inline struct iova *
391alloc_and_init_iova(unsigned long pfn_lo, unsigned long pfn_hi)
392{
393 struct iova *iova;
394
395 iova = alloc_iova_mem();
396 if (iova) {
397 iova->pfn_lo = pfn_lo;
398 iova->pfn_hi = pfn_hi;
399 }
400
401 return iova;
402}
403
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700404static struct iova *
405__insert_new_range(struct iova_domain *iovad,
406 unsigned long pfn_lo, unsigned long pfn_hi)
407{
408 struct iova *iova;
409
Jiang Liu75f05562014-02-19 14:07:37 +0800410 iova = alloc_and_init_iova(pfn_lo, pfn_hi);
411 if (iova)
412 iova_insert_rbtree(&iovad->rbroot, iova);
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700413
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700414 return iova;
415}
416
417static void
418__adjust_overlap_range(struct iova *iova,
419 unsigned long *pfn_lo, unsigned long *pfn_hi)
420{
421 if (*pfn_lo < iova->pfn_lo)
422 iova->pfn_lo = *pfn_lo;
423 if (*pfn_hi > iova->pfn_hi)
424 *pfn_lo = iova->pfn_hi + 1;
425}
426
427/**
428 * reserve_iova - reserves an iova in the given range
429 * @iovad: - iova domain pointer
430 * @pfn_lo: - lower page frame address
431 * @pfn_hi:- higher pfn adderss
432 * This function allocates reserves the address range from pfn_lo to pfn_hi so
433 * that this address is not dished out as part of alloc_iova.
434 */
435struct iova *
436reserve_iova(struct iova_domain *iovad,
437 unsigned long pfn_lo, unsigned long pfn_hi)
438{
439 struct rb_node *node;
440 unsigned long flags;
441 struct iova *iova;
442 unsigned int overlap = 0;
443
David Woodhouse3d39cec2009-07-08 15:23:30 +0100444 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700445 for (node = rb_first(&iovad->rbroot); node; node = rb_next(node)) {
446 if (__is_range_overlap(node, pfn_lo, pfn_hi)) {
447 iova = container_of(node, struct iova, node);
448 __adjust_overlap_range(iova, &pfn_lo, &pfn_hi);
449 if ((pfn_lo >= iova->pfn_lo) &&
450 (pfn_hi <= iova->pfn_hi))
451 goto finish;
452 overlap = 1;
453
454 } else if (overlap)
455 break;
456 }
457
Lucas De Marchi25985ed2011-03-30 22:57:33 -0300458 /* We are here either because this is the first reserver node
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700459 * or need to insert remaining non overlap addr range
460 */
461 iova = __insert_new_range(iovad, pfn_lo, pfn_hi);
462finish:
463
David Woodhouse3d39cec2009-07-08 15:23:30 +0100464 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700465 return iova;
466}
467
468/**
469 * copy_reserved_iova - copies the reserved between domains
470 * @from: - source doamin from where to copy
471 * @to: - destination domin where to copy
472 * This function copies reserved iova's from one doamin to
473 * other.
474 */
475void
476copy_reserved_iova(struct iova_domain *from, struct iova_domain *to)
477{
478 unsigned long flags;
479 struct rb_node *node;
480
David Woodhouse3d39cec2009-07-08 15:23:30 +0100481 spin_lock_irqsave(&from->iova_rbtree_lock, flags);
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700482 for (node = rb_first(&from->rbroot); node; node = rb_next(node)) {
483 struct iova *iova = container_of(node, struct iova, node);
484 struct iova *new_iova;
485 new_iova = reserve_iova(to, iova->pfn_lo, iova->pfn_hi);
486 if (!new_iova)
487 printk(KERN_ERR "Reserve iova range %lx@%lx failed\n",
488 iova->pfn_lo, iova->pfn_lo);
489 }
David Woodhouse3d39cec2009-07-08 15:23:30 +0100490 spin_unlock_irqrestore(&from->iova_rbtree_lock, flags);
Keshavamurthy, Anil Sf8de50e2007-10-21 16:41:48 -0700491}
Jiang Liu75f05562014-02-19 14:07:37 +0800492
493struct iova *
494split_and_remove_iova(struct iova_domain *iovad, struct iova *iova,
495 unsigned long pfn_lo, unsigned long pfn_hi)
496{
497 unsigned long flags;
498 struct iova *prev = NULL, *next = NULL;
499
500 spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
501 if (iova->pfn_lo < pfn_lo) {
502 prev = alloc_and_init_iova(iova->pfn_lo, pfn_lo - 1);
503 if (prev == NULL)
504 goto error;
505 }
506 if (iova->pfn_hi > pfn_hi) {
507 next = alloc_and_init_iova(pfn_hi + 1, iova->pfn_hi);
508 if (next == NULL)
509 goto error;
510 }
511
512 __cached_rbnode_delete_update(iovad, iova);
513 rb_erase(&iova->node, &iovad->rbroot);
514
515 if (prev) {
516 iova_insert_rbtree(&iovad->rbroot, prev);
517 iova->pfn_lo = pfn_lo;
518 }
519 if (next) {
520 iova_insert_rbtree(&iovad->rbroot, next);
521 iova->pfn_hi = pfn_hi;
522 }
523 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
524
525 return iova;
526
527error:
528 spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
529 if (prev)
530 free_iova_mem(prev);
531 return NULL;
532}