drivers/pci/iova.c

   1 /*
   2  * Copyright (c) 2006, Intel Corporation.
   3  *
   4  * This file is released under the GPLv2.
   5  *
   6 <<<<<<< HEAD:drivers/pci/iova.c
   7  * Copyright (C) 2006 Anil S Keshavamurthy <anil.s.keshavamurthy@intel.com>
   8 =======
   9  * Copyright (C) 2006-2008 Intel Corporation
  10  * Author: Anil S Keshavamurthy <anil.s.keshavamurthy@intel.com>
  11 >>>>>>> 264e3e889d86e552b4191d69bb60f4f3b383135a:drivers/pci/iova.c
  12  */
  13
  14 #include "iova.h"
  15
  16 void
  17 init_iova_domain(struct iova_domain *iovad, unsigned long pfn_32bit)
  18 {
  19         spin_lock_init(&iovad->iova_alloc_lock);
  20         spin_lock_init(&iovad->iova_rbtree_lock);
  21         iovad->rbroot = RB_ROOT;
  22         iovad->cached32_node = NULL;
  23         iovad->dma_32bit_pfn = pfn_32bit;
  24 }
  25
  26 static struct rb_node *
  27 __get_cached_rbnode(struct iova_domain *iovad, unsigned long *limit_pfn)
  28 {
  29         if ((*limit_pfn != iovad->dma_32bit_pfn) ||
  30                 (iovad->cached32_node == NULL))
  31                 return rb_last(&iovad->rbroot);
  32         else {
  33                 struct rb_node *prev_node = rb_prev(iovad->cached32_node);
  34                 struct iova *curr_iova =
  35                         container_of(iovad->cached32_node, struct iova, node);
  36                 *limit_pfn = curr_iova->pfn_lo - 1;
  37                 return prev_node;
  38         }
  39 }
  40
  41 static void
  42 __cached_rbnode_insert_update(struct iova_domain *iovad,
  43         unsigned long limit_pfn, struct iova *new)
  44 {
  45         if (limit_pfn != iovad->dma_32bit_pfn)
  46                 return;
  47         iovad->cached32_node = &new->node;
  48 }
  49
  50 static void
  51 __cached_rbnode_delete_update(struct iova_domain *iovad, struct iova *free)
  52 {
  53         struct iova *cached_iova;
  54         struct rb_node *curr;
  55
  56         if (!iovad->cached32_node)
  57                 return;
  58         curr = iovad->cached32_node;
  59         cached_iova = container_of(curr, struct iova, node);
  60
  61         if (free->pfn_lo >= cached_iova->pfn_lo)
  62                 iovad->cached32_node = rb_next(&free->node);
  63 }
  64
  65 /* Computes the padding size required, to make the
  66  * the start address naturally aligned on its size
  67  */
  68 static int
  69 iova_get_pad_size(int size, unsigned int limit_pfn)
  70 {
  71         unsigned int pad_size = 0;
  72         unsigned int order = ilog2(size);
  73
  74         if (order)
  75                 pad_size = (limit_pfn + 1) % (1 << order);
  76
  77         return pad_size;
  78 }
  79
  80 static int __alloc_iova_range(struct iova_domain *iovad, unsigned long size,
  81                 unsigned long limit_pfn, struct iova *new, bool size_aligned)
  82 {
  83         struct rb_node *curr = NULL;
  84         unsigned long flags;
  85         unsigned long saved_pfn;
  86         unsigned int pad_size = 0;
  87
  88         /* Walk the tree backwards */
  89         spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
  90         saved_pfn = limit_pfn;
  91         curr = __get_cached_rbnode(iovad, &limit_pfn);
  92         while (curr) {
  93                 struct iova *curr_iova = container_of(curr, struct iova, node);
  94                 if (limit_pfn < curr_iova->pfn_lo)
  95                         goto move_left;
  96                 else if (limit_pfn < curr_iova->pfn_hi)
  97                         goto adjust_limit_pfn;
  98                 else {
  99                         if (size_aligned)
 100                                 pad_size = iova_get_pad_size(size, limit_pfn);
 101                         if ((curr_iova->pfn_hi + size + pad_size) <= limit_pfn)
 102                                 break;  /* found a free slot */
 103                 }
 104 adjust_limit_pfn:
 105                 limit_pfn = curr_iova->pfn_lo - 1;
 106 move_left:
 107                 curr = rb_prev(curr);
 108         }
 109
 110         if (!curr) {
 111                 if (size_aligned)
 112                         pad_size = iova_get_pad_size(size, limit_pfn);
 113                 if ((IOVA_START_PFN + size + pad_size) > limit_pfn) {
 114                         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 115                         return -ENOMEM;
 116                 }
 117         }
 118
 119         /* pfn_lo will point to size aligned address if size_aligned is set */
 120         new->pfn_lo = limit_pfn - (size + pad_size) + 1;
 121         new->pfn_hi = new->pfn_lo + size - 1;
 122
 123         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 124         return 0;
 125 }
 126
 127 static void
 128 iova_insert_rbtree(struct rb_root *root, struct iova *iova)
 129 {
 130         struct rb_node **new = &(root->rb_node), *parent = NULL;
 131         /* Figure out where to put new node */
 132         while (*new) {
 133                 struct iova *this = container_of(*new, struct iova, node);
 134                 parent = *new;
 135
 136                 if (iova->pfn_lo < this->pfn_lo)
 137                         new = &((*new)->rb_left);
 138                 else if (iova->pfn_lo > this->pfn_lo)
 139                         new = &((*new)->rb_right);
 140                 else
 141                         BUG(); /* this should not happen */
 142         }
 143         /* Add new node and rebalance tree. */
 144         rb_link_node(&iova->node, parent, new);
 145         rb_insert_color(&iova->node, root);
 146 }
 147
 148 /**
 149  * alloc_iova - allocates an iova
 150  * @iovad - iova domain in question
 151  * @size - size of page frames to allocate
 152  * @limit_pfn - max limit address
 153  * @size_aligned - set if size_aligned address range is required
 154  * This function allocates an iova in the range limit_pfn to IOVA_START_PFN
 155  * looking from limit_pfn instead from IOVA_START_PFN. If the size_aligned
 156  * flag is set then the allocated address iova->pfn_lo will be naturally
 157  * aligned on roundup_power_of_two(size).
 158  */
 159 struct iova *
 160 alloc_iova(struct iova_domain *iovad, unsigned long size,
 161         unsigned long limit_pfn,
 162         bool size_aligned)
 163 {
 164         unsigned long flags;
 165         struct iova *new_iova;
 166         int ret;
 167
 168         new_iova = alloc_iova_mem();
 169         if (!new_iova)
 170                 return NULL;
 171
 172         /* If size aligned is set then round the size to
 173          * to next power of two.
 174          */
 175         if (size_aligned)
 176                 size = __roundup_pow_of_two(size);
 177
 178         spin_lock_irqsave(&iovad->iova_alloc_lock, flags);
 179         ret = __alloc_iova_range(iovad, size, limit_pfn, new_iova,
 180                         size_aligned);
 181
 182         if (ret) {
 183                 spin_unlock_irqrestore(&iovad->iova_alloc_lock, flags);
 184                 free_iova_mem(new_iova);
 185                 return NULL;
 186         }
 187
 188         /* Insert the new_iova into domain rbtree by holding writer lock */
 189         spin_lock(&iovad->iova_rbtree_lock);
 190         iova_insert_rbtree(&iovad->rbroot, new_iova);
 191         __cached_rbnode_insert_update(iovad, limit_pfn, new_iova);
 192         spin_unlock(&iovad->iova_rbtree_lock);
 193
 194         spin_unlock_irqrestore(&iovad->iova_alloc_lock, flags);
 195
 196         return new_iova;
 197 }
 198
 199 /**
 200  * find_iova - find's an iova for a given pfn
 201  * @iovad - iova domain in question.
 202  * pfn - page frame number
 203  * This function finds and returns an iova belonging to the
 204  * given doamin which matches the given pfn.
 205  */
 206 struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn)
 207 {
 208         unsigned long flags;
 209         struct rb_node *node;
 210
 211         /* Take the lock so that no other thread is manipulating the rbtree */
 212         spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
 213         node = iovad->rbroot.rb_node;
 214         while (node) {
 215                 struct iova *iova = container_of(node, struct iova, node);
 216
 217                 /* If pfn falls within iova's range, return iova */
 218                 if ((pfn >= iova->pfn_lo) && (pfn <= iova->pfn_hi)) {
 219                         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 220                         /* We are not holding the lock while this iova
 221                          * is referenced by the caller as the same thread
 222                          * which called this function also calls __free_iova()
 223                          * and it is by desing that only one thread can possibly
 224                          * reference a particular iova and hence no conflict.
 225                          */
 226                         return iova;
 227                 }
 228
 229                 if (pfn < iova->pfn_lo)
 230                         node = node->rb_left;
 231                 else if (pfn > iova->pfn_lo)
 232                         node = node->rb_right;
 233         }
 234
 235         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 236         return NULL;
 237 }
 238
 239 /**
 240  * __free_iova - frees the given iova
 241  * @iovad: iova domain in question.
 242  * @iova: iova in question.
 243  * Frees the given iova belonging to the giving domain
 244  */
 245 void
 246 __free_iova(struct iova_domain *iovad, struct iova *iova)
 247 {
 248         unsigned long flags;
 249
 250         spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
 251         __cached_rbnode_delete_update(iovad, iova);
 252         rb_erase(&iova->node, &iovad->rbroot);
 253         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 254         free_iova_mem(iova);
 255 }
 256
 257 /**
 258  * free_iova - finds and frees the iova for a given pfn
 259  * @iovad: - iova domain in question.
 260  * @pfn: - pfn that is allocated previously
 261  * This functions finds an iova for a given pfn and then
 262  * frees the iova from that domain.
 263  */
 264 void
 265 free_iova(struct iova_domain *iovad, unsigned long pfn)
 266 {
 267         struct iova *iova = find_iova(iovad, pfn);
 268         if (iova)
 269                 __free_iova(iovad, iova);
 270
 271 }
 272
 273 /**
 274  * put_iova_domain - destroys the iova doamin
 275  * @iovad: - iova domain in question.
 276  * All the iova's in that domain are destroyed.
 277  */
 278 void put_iova_domain(struct iova_domain *iovad)
 279 {
 280         struct rb_node *node;
 281         unsigned long flags;
 282
 283         spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
 284         node = rb_first(&iovad->rbroot);
 285         while (node) {
 286                 struct iova *iova = container_of(node, struct iova, node);
 287                 rb_erase(node, &iovad->rbroot);
 288                 free_iova_mem(iova);
 289                 node = rb_first(&iovad->rbroot);
 290         }
 291         spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 292 }
 293
 294 static int
 295 __is_range_overlap(struct rb_node *node,
 296         unsigned long pfn_lo, unsigned long pfn_hi)
 297 {
 298         struct iova *iova = container_of(node, struct iova, node);
 299
 300         if ((pfn_lo <= iova->pfn_hi) && (pfn_hi >= iova->pfn_lo))
 301                 return 1;
 302         return 0;
 303 }
 304
 305 static struct iova *
 306 __insert_new_range(struct iova_domain *iovad,
 307         unsigned long pfn_lo, unsigned long pfn_hi)
 308 {
 309         struct iova *iova;
 310
 311         iova = alloc_iova_mem();
 312         if (!iova)
 313                 return iova;
 314
 315         iova->pfn_hi = pfn_hi;
 316         iova->pfn_lo = pfn_lo;
 317         iova_insert_rbtree(&iovad->rbroot, iova);
 318         return iova;
 319 }
 320
 321 static void
 322 __adjust_overlap_range(struct iova *iova,
 323         unsigned long *pfn_lo, unsigned long *pfn_hi)
 324 {
 325         if (*pfn_lo < iova->pfn_lo)
 326                 iova->pfn_lo = *pfn_lo;
 327         if (*pfn_hi > iova->pfn_hi)
 328                 *pfn_lo = iova->pfn_hi + 1;
 329 }
 330
 331 /**
 332  * reserve_iova - reserves an iova in the given range
 333  * @iovad: - iova domain pointer
 334  * @pfn_lo: - lower page frame address
 335  * @pfn_hi:- higher pfn adderss
 336  * This function allocates reserves the address range from pfn_lo to pfn_hi so
 337  * that this address is not dished out as part of alloc_iova.
 338  */
 339 struct iova *
 340 reserve_iova(struct iova_domain *iovad,
 341         unsigned long pfn_lo, unsigned long pfn_hi)
 342 {
 343         struct rb_node *node;
 344         unsigned long flags;
 345         struct iova *iova;
 346         unsigned int overlap = 0;
 347
 348         spin_lock_irqsave(&iovad->iova_alloc_lock, flags);
 349         spin_lock(&iovad->iova_rbtree_lock);
 350         for (node = rb_first(&iovad->rbroot); node; node = rb_next(node)) {
 351                 if (__is_range_overlap(node, pfn_lo, pfn_hi)) {
 352                         iova = container_of(node, struct iova, node);
 353                         __adjust_overlap_range(iova, &pfn_lo, &pfn_hi);
 354                         if ((pfn_lo >= iova->pfn_lo) &&
 355                                 (pfn_hi <= iova->pfn_hi))
 356                                 goto finish;
 357                         overlap = 1;
 358
 359                 } else if (overlap)
 360                                 break;
 361         }
 362
 363         /* We are here either becasue this is the first reserver node
 364          * or need to insert remaining non overlap addr range
 365          */
 366         iova = __insert_new_range(iovad, pfn_lo, pfn_hi);
 367 finish:
 368
 369         spin_unlock(&iovad->iova_rbtree_lock);
 370         spin_unlock_irqrestore(&iovad->iova_alloc_lock, flags);
 371         return iova;
 372 }
 373
 374 /**
 375  * copy_reserved_iova - copies the reserved between domains
 376  * @from: - source doamin from where to copy
 377  * @to: - destination domin where to copy
 378  * This function copies reserved iova's from one doamin to
 379  * other.
 380  */
 381 void
 382 copy_reserved_iova(struct iova_domain *from, struct iova_domain *to)
 383 {
 384         unsigned long flags;
 385         struct rb_node *node;
 386
 387         spin_lock_irqsave(&from->iova_alloc_lock, flags);
 388         spin_lock(&from->iova_rbtree_lock);
 389         for (node = rb_first(&from->rbroot); node; node = rb_next(node)) {
 390                 struct iova *iova = container_of(node, struct iova, node);
 391                 struct iova *new_iova;
 392                 new_iova = reserve_iova(to, iova->pfn_lo, iova->pfn_hi);
 393                 if (!new_iova)
 394                         printk(KERN_ERR "Reserve iova range %lx@%lx failed\n",
 395                                 iova->pfn_lo, iova->pfn_lo);
 396         }
 397         spin_unlock(&from->iova_rbtree_lock);
 398         spin_unlock_irqrestore(&from->iova_alloc_lock, flags);
 399 }