Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 1 | /* |
David Woodhouse | a15a519 | 2009-07-01 18:49:06 +0100 | [diff] [blame] | 2 | * Copyright © 2006-2009, Intel Corporation. |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 3 | * |
David Woodhouse | a15a519 | 2009-07-01 18:49:06 +0100 | [diff] [blame] | 4 | * This program is free software; you can redistribute it and/or modify it |
| 5 | * under the terms and conditions of the GNU General Public License, |
| 6 | * version 2, as published by the Free Software Foundation. |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 7 | * |
David Woodhouse | a15a519 | 2009-07-01 18:49:06 +0100 | [diff] [blame] | 8 | * This program is distributed in the hope it will be useful, but WITHOUT |
| 9 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| 10 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for |
| 11 | * more details. |
| 12 | * |
| 13 | * You should have received a copy of the GNU General Public License along with |
| 14 | * this program; if not, write to the Free Software Foundation, Inc., 59 Temple |
| 15 | * Place - Suite 330, Boston, MA 02111-1307 USA. |
| 16 | * |
mark gross | 98bcef5 | 2008-02-23 15:23:35 -0800 | [diff] [blame] | 17 | * Author: Anil S Keshavamurthy <anil.s.keshavamurthy@intel.com> |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 18 | */ |
| 19 | |
Kay, Allen M | 3871794 | 2008-09-09 18:37:29 +0300 | [diff] [blame] | 20 | #include <linux/iova.h> |
Robin Murphy | 85b4545 | 2015-01-12 17:51:14 +0000 | [diff] [blame^] | 21 | #include <linux/slab.h> |
| 22 | |
| 23 | static struct kmem_cache *iommu_iova_cache; |
| 24 | |
| 25 | int 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 | |
| 42 | void iommu_iova_cache_destroy(void) |
| 43 | { |
| 44 | kmem_cache_destroy(iommu_iova_cache); |
| 45 | } |
| 46 | |
| 47 | struct iova *alloc_iova_mem(void) |
| 48 | { |
| 49 | return kmem_cache_alloc(iommu_iova_cache, GFP_ATOMIC); |
| 50 | } |
| 51 | |
| 52 | void free_iova_mem(struct iova *iova) |
| 53 | { |
| 54 | kmem_cache_free(iommu_iova_cache, iova); |
| 55 | } |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 56 | |
| 57 | void |
David Miller | f661197 | 2008-02-06 01:36:23 -0800 | [diff] [blame] | 58 | init_iova_domain(struct iova_domain *iovad, unsigned long pfn_32bit) |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 59 | { |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 60 | spin_lock_init(&iovad->iova_rbtree_lock); |
| 61 | iovad->rbroot = RB_ROOT; |
| 62 | iovad->cached32_node = NULL; |
David Miller | f661197 | 2008-02-06 01:36:23 -0800 | [diff] [blame] | 63 | iovad->dma_32bit_pfn = pfn_32bit; |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 64 | } |
| 65 | |
| 66 | static struct rb_node * |
| 67 | __get_cached_rbnode(struct iova_domain *iovad, unsigned long *limit_pfn) |
| 68 | { |
David Miller | f661197 | 2008-02-06 01:36:23 -0800 | [diff] [blame] | 69 | if ((*limit_pfn != iovad->dma_32bit_pfn) || |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 70 | (iovad->cached32_node == NULL)) |
| 71 | return rb_last(&iovad->rbroot); |
| 72 | else { |
| 73 | struct rb_node *prev_node = rb_prev(iovad->cached32_node); |
| 74 | struct iova *curr_iova = |
| 75 | container_of(iovad->cached32_node, struct iova, node); |
| 76 | *limit_pfn = curr_iova->pfn_lo - 1; |
| 77 | return prev_node; |
| 78 | } |
| 79 | } |
| 80 | |
| 81 | static void |
| 82 | __cached_rbnode_insert_update(struct iova_domain *iovad, |
| 83 | unsigned long limit_pfn, struct iova *new) |
| 84 | { |
David Miller | f661197 | 2008-02-06 01:36:23 -0800 | [diff] [blame] | 85 | if (limit_pfn != iovad->dma_32bit_pfn) |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 86 | return; |
| 87 | iovad->cached32_node = &new->node; |
| 88 | } |
| 89 | |
| 90 | static void |
| 91 | __cached_rbnode_delete_update(struct iova_domain *iovad, struct iova *free) |
| 92 | { |
| 93 | struct iova *cached_iova; |
| 94 | struct rb_node *curr; |
| 95 | |
| 96 | if (!iovad->cached32_node) |
| 97 | return; |
| 98 | curr = iovad->cached32_node; |
| 99 | cached_iova = container_of(curr, struct iova, node); |
| 100 | |
Chris Wright | 1c9fc3d | 2011-05-28 13:15:04 -0500 | [diff] [blame] | 101 | if (free->pfn_lo >= cached_iova->pfn_lo) { |
| 102 | struct rb_node *node = rb_next(&free->node); |
| 103 | struct iova *iova = container_of(node, struct iova, node); |
| 104 | |
| 105 | /* only cache if it's below 32bit pfn */ |
| 106 | if (node && iova->pfn_lo < iovad->dma_32bit_pfn) |
| 107 | iovad->cached32_node = node; |
| 108 | else |
| 109 | iovad->cached32_node = NULL; |
| 110 | } |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 111 | } |
| 112 | |
Keshavamurthy, Anil S | f76aec7 | 2007-10-21 16:41:58 -0700 | [diff] [blame] | 113 | /* Computes the padding size required, to make the |
| 114 | * the start address naturally aligned on its size |
| 115 | */ |
| 116 | static int |
| 117 | iova_get_pad_size(int size, unsigned int limit_pfn) |
| 118 | { |
| 119 | unsigned int pad_size = 0; |
| 120 | unsigned int order = ilog2(size); |
| 121 | |
| 122 | if (order) |
| 123 | pad_size = (limit_pfn + 1) % (1 << order); |
| 124 | |
| 125 | return pad_size; |
| 126 | } |
| 127 | |
mark gross | ddf0288 | 2008-03-04 15:22:04 -0800 | [diff] [blame] | 128 | static int __alloc_and_insert_iova_range(struct iova_domain *iovad, |
| 129 | unsigned long size, unsigned long limit_pfn, |
| 130 | struct iova *new, bool size_aligned) |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 131 | { |
mark gross | ddf0288 | 2008-03-04 15:22:04 -0800 | [diff] [blame] | 132 | struct rb_node *prev, *curr = NULL; |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 133 | unsigned long flags; |
| 134 | unsigned long saved_pfn; |
Keshavamurthy, Anil S | f76aec7 | 2007-10-21 16:41:58 -0700 | [diff] [blame] | 135 | unsigned int pad_size = 0; |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 136 | |
| 137 | /* Walk the tree backwards */ |
| 138 | spin_lock_irqsave(&iovad->iova_rbtree_lock, flags); |
| 139 | saved_pfn = limit_pfn; |
| 140 | curr = __get_cached_rbnode(iovad, &limit_pfn); |
mark gross | ddf0288 | 2008-03-04 15:22:04 -0800 | [diff] [blame] | 141 | prev = curr; |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 142 | while (curr) { |
| 143 | struct iova *curr_iova = container_of(curr, struct iova, node); |
mark gross | ddf0288 | 2008-03-04 15:22:04 -0800 | [diff] [blame] | 144 | |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 145 | if (limit_pfn < curr_iova->pfn_lo) |
| 146 | goto move_left; |
Keshavamurthy, Anil S | f76aec7 | 2007-10-21 16:41:58 -0700 | [diff] [blame] | 147 | else if (limit_pfn < curr_iova->pfn_hi) |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 148 | goto adjust_limit_pfn; |
Keshavamurthy, Anil S | f76aec7 | 2007-10-21 16:41:58 -0700 | [diff] [blame] | 149 | else { |
| 150 | if (size_aligned) |
| 151 | pad_size = iova_get_pad_size(size, limit_pfn); |
| 152 | if ((curr_iova->pfn_hi + size + pad_size) <= limit_pfn) |
| 153 | break; /* found a free slot */ |
| 154 | } |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 155 | adjust_limit_pfn: |
| 156 | limit_pfn = curr_iova->pfn_lo - 1; |
| 157 | move_left: |
mark gross | ddf0288 | 2008-03-04 15:22:04 -0800 | [diff] [blame] | 158 | prev = curr; |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 159 | curr = rb_prev(curr); |
| 160 | } |
| 161 | |
Keshavamurthy, Anil S | f76aec7 | 2007-10-21 16:41:58 -0700 | [diff] [blame] | 162 | if (!curr) { |
| 163 | if (size_aligned) |
| 164 | pad_size = iova_get_pad_size(size, limit_pfn); |
| 165 | if ((IOVA_START_PFN + size + pad_size) > limit_pfn) { |
| 166 | spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); |
| 167 | return -ENOMEM; |
| 168 | } |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 169 | } |
Keshavamurthy, Anil S | f76aec7 | 2007-10-21 16:41:58 -0700 | [diff] [blame] | 170 | |
| 171 | /* pfn_lo will point to size aligned address if size_aligned is set */ |
| 172 | new->pfn_lo = limit_pfn - (size + pad_size) + 1; |
| 173 | new->pfn_hi = new->pfn_lo + size - 1; |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 174 | |
mark gross | ddf0288 | 2008-03-04 15:22:04 -0800 | [diff] [blame] | 175 | /* Insert the new_iova into domain rbtree by holding writer lock */ |
| 176 | /* Add new node and rebalance tree. */ |
| 177 | { |
David Woodhouse | a15a519 | 2009-07-01 18:49:06 +0100 | [diff] [blame] | 178 | struct rb_node **entry, *parent = NULL; |
| 179 | |
| 180 | /* If we have 'prev', it's a valid place to start the |
| 181 | insertion. Otherwise, start from the root. */ |
| 182 | if (prev) |
| 183 | entry = &prev; |
| 184 | else |
| 185 | entry = &iovad->rbroot.rb_node; |
| 186 | |
mark gross | ddf0288 | 2008-03-04 15:22:04 -0800 | [diff] [blame] | 187 | /* Figure out where to put new node */ |
| 188 | while (*entry) { |
| 189 | struct iova *this = container_of(*entry, |
| 190 | struct iova, node); |
| 191 | parent = *entry; |
| 192 | |
| 193 | if (new->pfn_lo < this->pfn_lo) |
| 194 | entry = &((*entry)->rb_left); |
| 195 | else if (new->pfn_lo > this->pfn_lo) |
| 196 | entry = &((*entry)->rb_right); |
| 197 | else |
| 198 | BUG(); /* this should not happen */ |
| 199 | } |
| 200 | |
| 201 | /* Add new node and rebalance tree. */ |
| 202 | rb_link_node(&new->node, parent, entry); |
| 203 | rb_insert_color(&new->node, &iovad->rbroot); |
| 204 | } |
| 205 | __cached_rbnode_insert_update(iovad, saved_pfn, new); |
| 206 | |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 207 | spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); |
mark gross | ddf0288 | 2008-03-04 15:22:04 -0800 | [diff] [blame] | 208 | |
| 209 | |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 210 | return 0; |
| 211 | } |
| 212 | |
| 213 | static void |
| 214 | iova_insert_rbtree(struct rb_root *root, struct iova *iova) |
| 215 | { |
| 216 | struct rb_node **new = &(root->rb_node), *parent = NULL; |
| 217 | /* Figure out where to put new node */ |
| 218 | while (*new) { |
| 219 | struct iova *this = container_of(*new, struct iova, node); |
| 220 | parent = *new; |
| 221 | |
| 222 | if (iova->pfn_lo < this->pfn_lo) |
| 223 | new = &((*new)->rb_left); |
| 224 | else if (iova->pfn_lo > this->pfn_lo) |
| 225 | new = &((*new)->rb_right); |
| 226 | else |
| 227 | BUG(); /* this should not happen */ |
| 228 | } |
| 229 | /* Add new node and rebalance tree. */ |
| 230 | rb_link_node(&iova->node, parent, new); |
| 231 | rb_insert_color(&iova->node, root); |
| 232 | } |
| 233 | |
| 234 | /** |
| 235 | * alloc_iova - allocates an iova |
Masanari Iida | 07db040 | 2012-07-22 02:21:32 +0900 | [diff] [blame] | 236 | * @iovad: - iova domain in question |
| 237 | * @size: - size of page frames to allocate |
| 238 | * @limit_pfn: - max limit address |
| 239 | * @size_aligned: - set if size_aligned address range is required |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 240 | * This function allocates an iova in the range limit_pfn to IOVA_START_PFN |
Keshavamurthy, Anil S | f76aec7 | 2007-10-21 16:41:58 -0700 | [diff] [blame] | 241 | * looking from limit_pfn instead from IOVA_START_PFN. If the size_aligned |
| 242 | * flag is set then the allocated address iova->pfn_lo will be naturally |
| 243 | * aligned on roundup_power_of_two(size). |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 244 | */ |
| 245 | struct iova * |
| 246 | alloc_iova(struct iova_domain *iovad, unsigned long size, |
Keshavamurthy, Anil S | f76aec7 | 2007-10-21 16:41:58 -0700 | [diff] [blame] | 247 | unsigned long limit_pfn, |
| 248 | bool size_aligned) |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 249 | { |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 250 | struct iova *new_iova; |
| 251 | int ret; |
| 252 | |
| 253 | new_iova = alloc_iova_mem(); |
| 254 | if (!new_iova) |
| 255 | return NULL; |
| 256 | |
Keshavamurthy, Anil S | f76aec7 | 2007-10-21 16:41:58 -0700 | [diff] [blame] | 257 | /* If size aligned is set then round the size to |
| 258 | * to next power of two. |
| 259 | */ |
| 260 | if (size_aligned) |
| 261 | size = __roundup_pow_of_two(size); |
| 262 | |
mark gross | ddf0288 | 2008-03-04 15:22:04 -0800 | [diff] [blame] | 263 | ret = __alloc_and_insert_iova_range(iovad, size, limit_pfn, |
| 264 | new_iova, size_aligned); |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 265 | |
| 266 | if (ret) { |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 267 | free_iova_mem(new_iova); |
| 268 | return NULL; |
| 269 | } |
| 270 | |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 271 | return new_iova; |
| 272 | } |
| 273 | |
| 274 | /** |
| 275 | * find_iova - find's an iova for a given pfn |
Masanari Iida | 07db040 | 2012-07-22 02:21:32 +0900 | [diff] [blame] | 276 | * @iovad: - iova domain in question. |
| 277 | * @pfn: - page frame number |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 278 | * This function finds and returns an iova belonging to the |
| 279 | * given doamin which matches the given pfn. |
| 280 | */ |
| 281 | struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn) |
| 282 | { |
| 283 | unsigned long flags; |
| 284 | struct rb_node *node; |
| 285 | |
| 286 | /* Take the lock so that no other thread is manipulating the rbtree */ |
| 287 | spin_lock_irqsave(&iovad->iova_rbtree_lock, flags); |
| 288 | node = iovad->rbroot.rb_node; |
| 289 | while (node) { |
| 290 | struct iova *iova = container_of(node, struct iova, node); |
| 291 | |
| 292 | /* If pfn falls within iova's range, return iova */ |
| 293 | if ((pfn >= iova->pfn_lo) && (pfn <= iova->pfn_hi)) { |
| 294 | spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); |
| 295 | /* We are not holding the lock while this iova |
| 296 | * is referenced by the caller as the same thread |
| 297 | * which called this function also calls __free_iova() |
Masanari Iida | 07db040 | 2012-07-22 02:21:32 +0900 | [diff] [blame] | 298 | * and it is by design that only one thread can possibly |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 299 | * reference a particular iova and hence no conflict. |
| 300 | */ |
| 301 | return iova; |
| 302 | } |
| 303 | |
| 304 | if (pfn < iova->pfn_lo) |
| 305 | node = node->rb_left; |
| 306 | else if (pfn > iova->pfn_lo) |
| 307 | node = node->rb_right; |
| 308 | } |
| 309 | |
| 310 | spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); |
| 311 | return NULL; |
| 312 | } |
| 313 | |
| 314 | /** |
| 315 | * __free_iova - frees the given iova |
| 316 | * @iovad: iova domain in question. |
| 317 | * @iova: iova in question. |
| 318 | * Frees the given iova belonging to the giving domain |
| 319 | */ |
| 320 | void |
| 321 | __free_iova(struct iova_domain *iovad, struct iova *iova) |
| 322 | { |
| 323 | unsigned long flags; |
| 324 | |
| 325 | spin_lock_irqsave(&iovad->iova_rbtree_lock, flags); |
| 326 | __cached_rbnode_delete_update(iovad, iova); |
| 327 | rb_erase(&iova->node, &iovad->rbroot); |
| 328 | spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); |
| 329 | free_iova_mem(iova); |
| 330 | } |
| 331 | |
| 332 | /** |
| 333 | * free_iova - finds and frees the iova for a given pfn |
| 334 | * @iovad: - iova domain in question. |
| 335 | * @pfn: - pfn that is allocated previously |
| 336 | * This functions finds an iova for a given pfn and then |
| 337 | * frees the iova from that domain. |
| 338 | */ |
| 339 | void |
| 340 | free_iova(struct iova_domain *iovad, unsigned long pfn) |
| 341 | { |
| 342 | struct iova *iova = find_iova(iovad, pfn); |
| 343 | if (iova) |
| 344 | __free_iova(iovad, iova); |
| 345 | |
| 346 | } |
| 347 | |
| 348 | /** |
| 349 | * put_iova_domain - destroys the iova doamin |
| 350 | * @iovad: - iova domain in question. |
| 351 | * All the iova's in that domain are destroyed. |
| 352 | */ |
| 353 | void put_iova_domain(struct iova_domain *iovad) |
| 354 | { |
| 355 | struct rb_node *node; |
| 356 | unsigned long flags; |
| 357 | |
| 358 | spin_lock_irqsave(&iovad->iova_rbtree_lock, flags); |
| 359 | node = rb_first(&iovad->rbroot); |
| 360 | while (node) { |
| 361 | struct iova *iova = container_of(node, struct iova, node); |
| 362 | rb_erase(node, &iovad->rbroot); |
| 363 | free_iova_mem(iova); |
| 364 | node = rb_first(&iovad->rbroot); |
| 365 | } |
| 366 | spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); |
| 367 | } |
| 368 | |
| 369 | static int |
| 370 | __is_range_overlap(struct rb_node *node, |
| 371 | unsigned long pfn_lo, unsigned long pfn_hi) |
| 372 | { |
| 373 | struct iova *iova = container_of(node, struct iova, node); |
| 374 | |
| 375 | if ((pfn_lo <= iova->pfn_hi) && (pfn_hi >= iova->pfn_lo)) |
| 376 | return 1; |
| 377 | return 0; |
| 378 | } |
| 379 | |
Jiang Liu | 75f0556 | 2014-02-19 14:07:37 +0800 | [diff] [blame] | 380 | static inline struct iova * |
| 381 | alloc_and_init_iova(unsigned long pfn_lo, unsigned long pfn_hi) |
| 382 | { |
| 383 | struct iova *iova; |
| 384 | |
| 385 | iova = alloc_iova_mem(); |
| 386 | if (iova) { |
| 387 | iova->pfn_lo = pfn_lo; |
| 388 | iova->pfn_hi = pfn_hi; |
| 389 | } |
| 390 | |
| 391 | return iova; |
| 392 | } |
| 393 | |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 394 | static struct iova * |
| 395 | __insert_new_range(struct iova_domain *iovad, |
| 396 | unsigned long pfn_lo, unsigned long pfn_hi) |
| 397 | { |
| 398 | struct iova *iova; |
| 399 | |
Jiang Liu | 75f0556 | 2014-02-19 14:07:37 +0800 | [diff] [blame] | 400 | iova = alloc_and_init_iova(pfn_lo, pfn_hi); |
| 401 | if (iova) |
| 402 | iova_insert_rbtree(&iovad->rbroot, iova); |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 403 | |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 404 | return iova; |
| 405 | } |
| 406 | |
| 407 | static void |
| 408 | __adjust_overlap_range(struct iova *iova, |
| 409 | unsigned long *pfn_lo, unsigned long *pfn_hi) |
| 410 | { |
| 411 | if (*pfn_lo < iova->pfn_lo) |
| 412 | iova->pfn_lo = *pfn_lo; |
| 413 | if (*pfn_hi > iova->pfn_hi) |
| 414 | *pfn_lo = iova->pfn_hi + 1; |
| 415 | } |
| 416 | |
| 417 | /** |
| 418 | * reserve_iova - reserves an iova in the given range |
| 419 | * @iovad: - iova domain pointer |
| 420 | * @pfn_lo: - lower page frame address |
| 421 | * @pfn_hi:- higher pfn adderss |
| 422 | * This function allocates reserves the address range from pfn_lo to pfn_hi so |
| 423 | * that this address is not dished out as part of alloc_iova. |
| 424 | */ |
| 425 | struct iova * |
| 426 | reserve_iova(struct iova_domain *iovad, |
| 427 | unsigned long pfn_lo, unsigned long pfn_hi) |
| 428 | { |
| 429 | struct rb_node *node; |
| 430 | unsigned long flags; |
| 431 | struct iova *iova; |
| 432 | unsigned int overlap = 0; |
| 433 | |
David Woodhouse | 3d39cec | 2009-07-08 15:23:30 +0100 | [diff] [blame] | 434 | spin_lock_irqsave(&iovad->iova_rbtree_lock, flags); |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 435 | for (node = rb_first(&iovad->rbroot); node; node = rb_next(node)) { |
| 436 | if (__is_range_overlap(node, pfn_lo, pfn_hi)) { |
| 437 | iova = container_of(node, struct iova, node); |
| 438 | __adjust_overlap_range(iova, &pfn_lo, &pfn_hi); |
| 439 | if ((pfn_lo >= iova->pfn_lo) && |
| 440 | (pfn_hi <= iova->pfn_hi)) |
| 441 | goto finish; |
| 442 | overlap = 1; |
| 443 | |
| 444 | } else if (overlap) |
| 445 | break; |
| 446 | } |
| 447 | |
Lucas De Marchi | 25985ed | 2011-03-30 22:57:33 -0300 | [diff] [blame] | 448 | /* We are here either because this is the first reserver node |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 449 | * or need to insert remaining non overlap addr range |
| 450 | */ |
| 451 | iova = __insert_new_range(iovad, pfn_lo, pfn_hi); |
| 452 | finish: |
| 453 | |
David Woodhouse | 3d39cec | 2009-07-08 15:23:30 +0100 | [diff] [blame] | 454 | spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 455 | return iova; |
| 456 | } |
| 457 | |
| 458 | /** |
| 459 | * copy_reserved_iova - copies the reserved between domains |
| 460 | * @from: - source doamin from where to copy |
| 461 | * @to: - destination domin where to copy |
| 462 | * This function copies reserved iova's from one doamin to |
| 463 | * other. |
| 464 | */ |
| 465 | void |
| 466 | copy_reserved_iova(struct iova_domain *from, struct iova_domain *to) |
| 467 | { |
| 468 | unsigned long flags; |
| 469 | struct rb_node *node; |
| 470 | |
David Woodhouse | 3d39cec | 2009-07-08 15:23:30 +0100 | [diff] [blame] | 471 | spin_lock_irqsave(&from->iova_rbtree_lock, flags); |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 472 | for (node = rb_first(&from->rbroot); node; node = rb_next(node)) { |
| 473 | struct iova *iova = container_of(node, struct iova, node); |
| 474 | struct iova *new_iova; |
| 475 | new_iova = reserve_iova(to, iova->pfn_lo, iova->pfn_hi); |
| 476 | if (!new_iova) |
| 477 | printk(KERN_ERR "Reserve iova range %lx@%lx failed\n", |
| 478 | iova->pfn_lo, iova->pfn_lo); |
| 479 | } |
David Woodhouse | 3d39cec | 2009-07-08 15:23:30 +0100 | [diff] [blame] | 480 | spin_unlock_irqrestore(&from->iova_rbtree_lock, flags); |
Keshavamurthy, Anil S | f8de50e | 2007-10-21 16:41:48 -0700 | [diff] [blame] | 481 | } |
Jiang Liu | 75f0556 | 2014-02-19 14:07:37 +0800 | [diff] [blame] | 482 | |
| 483 | struct iova * |
| 484 | split_and_remove_iova(struct iova_domain *iovad, struct iova *iova, |
| 485 | unsigned long pfn_lo, unsigned long pfn_hi) |
| 486 | { |
| 487 | unsigned long flags; |
| 488 | struct iova *prev = NULL, *next = NULL; |
| 489 | |
| 490 | spin_lock_irqsave(&iovad->iova_rbtree_lock, flags); |
| 491 | if (iova->pfn_lo < pfn_lo) { |
| 492 | prev = alloc_and_init_iova(iova->pfn_lo, pfn_lo - 1); |
| 493 | if (prev == NULL) |
| 494 | goto error; |
| 495 | } |
| 496 | if (iova->pfn_hi > pfn_hi) { |
| 497 | next = alloc_and_init_iova(pfn_hi + 1, iova->pfn_hi); |
| 498 | if (next == NULL) |
| 499 | goto error; |
| 500 | } |
| 501 | |
| 502 | __cached_rbnode_delete_update(iovad, iova); |
| 503 | rb_erase(&iova->node, &iovad->rbroot); |
| 504 | |
| 505 | if (prev) { |
| 506 | iova_insert_rbtree(&iovad->rbroot, prev); |
| 507 | iova->pfn_lo = pfn_lo; |
| 508 | } |
| 509 | if (next) { |
| 510 | iova_insert_rbtree(&iovad->rbroot, next); |
| 511 | iova->pfn_hi = pfn_hi; |
| 512 | } |
| 513 | spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); |
| 514 | |
| 515 | return iova; |
| 516 | |
| 517 | error: |
| 518 | spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); |
| 519 | if (prev) |
| 520 | free_iova_mem(prev); |
| 521 | return NULL; |
| 522 | } |