2 * Copyright © 2006-2009, Intel Corporation.
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.
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
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.
17 * Author: Anil S Keshavamurthy <anil.s.keshavamurthy@intel.com>
20 #include <linux/iova.h>
23 init_iova_domain(struct iova_domain
*iovad
, unsigned long pfn_32bit
)
25 spin_lock_init(&iovad
->iova_alloc_lock
);
26 spin_lock_init(&iovad
->iova_rbtree_lock
);
27 iovad
->rbroot
= RB_ROOT
;
28 iovad
->cached32_node
= NULL
;
29 iovad
->dma_32bit_pfn
= pfn_32bit
;
32 static struct rb_node
*
33 __get_cached_rbnode(struct iova_domain
*iovad
, unsigned long *limit_pfn
)
35 if ((*limit_pfn
!= iovad
->dma_32bit_pfn
) ||
36 (iovad
->cached32_node
== NULL
))
37 return rb_last(&iovad
->rbroot
);
39 struct rb_node
*prev_node
= rb_prev(iovad
->cached32_node
);
40 struct iova
*curr_iova
=
41 container_of(iovad
->cached32_node
, struct iova
, node
);
42 *limit_pfn
= curr_iova
->pfn_lo
- 1;
48 __cached_rbnode_insert_update(struct iova_domain
*iovad
,
49 unsigned long limit_pfn
, struct iova
*new)
51 if (limit_pfn
!= iovad
->dma_32bit_pfn
)
53 iovad
->cached32_node
= &new->node
;
57 __cached_rbnode_delete_update(struct iova_domain
*iovad
, struct iova
*free
)
59 struct iova
*cached_iova
;
62 if (!iovad
->cached32_node
)
64 curr
= iovad
->cached32_node
;
65 cached_iova
= container_of(curr
, struct iova
, node
);
67 if (free
->pfn_lo
>= cached_iova
->pfn_lo
)
68 iovad
->cached32_node
= rb_next(&free
->node
);
71 /* Computes the padding size required, to make the
72 * the start address naturally aligned on its size
75 iova_get_pad_size(int size
, unsigned int limit_pfn
)
77 unsigned int pad_size
= 0;
78 unsigned int order
= ilog2(size
);
81 pad_size
= (limit_pfn
+ 1) % (1 << order
);
86 static int __alloc_and_insert_iova_range(struct iova_domain
*iovad
,
87 unsigned long size
, unsigned long limit_pfn
,
88 struct iova
*new, bool size_aligned
)
90 struct rb_node
*prev
, *curr
= NULL
;
92 unsigned long saved_pfn
;
93 unsigned int pad_size
= 0;
95 /* Walk the tree backwards */
96 spin_lock_irqsave(&iovad
->iova_rbtree_lock
, flags
);
97 saved_pfn
= limit_pfn
;
98 curr
= __get_cached_rbnode(iovad
, &limit_pfn
);
101 struct iova
*curr_iova
= container_of(curr
, struct iova
, node
);
103 if (limit_pfn
< curr_iova
->pfn_lo
)
105 else if (limit_pfn
< curr_iova
->pfn_hi
)
106 goto adjust_limit_pfn
;
109 pad_size
= iova_get_pad_size(size
, limit_pfn
);
110 if ((curr_iova
->pfn_hi
+ size
+ pad_size
) <= limit_pfn
)
111 break; /* found a free slot */
114 limit_pfn
= curr_iova
->pfn_lo
- 1;
117 curr
= rb_prev(curr
);
122 pad_size
= iova_get_pad_size(size
, limit_pfn
);
123 if ((IOVA_START_PFN
+ size
+ pad_size
) > limit_pfn
) {
124 spin_unlock_irqrestore(&iovad
->iova_rbtree_lock
, flags
);
129 /* pfn_lo will point to size aligned address if size_aligned is set */
130 new->pfn_lo
= limit_pfn
- (size
+ pad_size
) + 1;
131 new->pfn_hi
= new->pfn_lo
+ size
- 1;
133 /* Insert the new_iova into domain rbtree by holding writer lock */
134 /* Add new node and rebalance tree. */
136 struct rb_node
**entry
, *parent
= NULL
;
138 /* If we have 'prev', it's a valid place to start the
139 insertion. Otherwise, start from the root. */
143 entry
= &iovad
->rbroot
.rb_node
;
145 /* Figure out where to put new node */
147 struct iova
*this = container_of(*entry
,
151 if (new->pfn_lo
< this->pfn_lo
)
152 entry
= &((*entry
)->rb_left
);
153 else if (new->pfn_lo
> this->pfn_lo
)
154 entry
= &((*entry
)->rb_right
);
156 BUG(); /* this should not happen */
159 /* Add new node and rebalance tree. */
160 rb_link_node(&new->node
, parent
, entry
);
161 rb_insert_color(&new->node
, &iovad
->rbroot
);
163 __cached_rbnode_insert_update(iovad
, saved_pfn
, new);
165 spin_unlock_irqrestore(&iovad
->iova_rbtree_lock
, flags
);
172 iova_insert_rbtree(struct rb_root
*root
, struct iova
*iova
)
174 struct rb_node
**new = &(root
->rb_node
), *parent
= NULL
;
175 /* Figure out where to put new node */
177 struct iova
*this = container_of(*new, struct iova
, node
);
180 if (iova
->pfn_lo
< this->pfn_lo
)
181 new = &((*new)->rb_left
);
182 else if (iova
->pfn_lo
> this->pfn_lo
)
183 new = &((*new)->rb_right
);
185 BUG(); /* this should not happen */
187 /* Add new node and rebalance tree. */
188 rb_link_node(&iova
->node
, parent
, new);
189 rb_insert_color(&iova
->node
, root
);
193 * alloc_iova - allocates an iova
194 * @iovad - iova domain in question
195 * @size - size of page frames to allocate
196 * @limit_pfn - max limit address
197 * @size_aligned - set if size_aligned address range is required
198 * This function allocates an iova in the range limit_pfn to IOVA_START_PFN
199 * looking from limit_pfn instead from IOVA_START_PFN. If the size_aligned
200 * flag is set then the allocated address iova->pfn_lo will be naturally
201 * aligned on roundup_power_of_two(size).
204 alloc_iova(struct iova_domain
*iovad
, unsigned long size
,
205 unsigned long limit_pfn
,
209 struct iova
*new_iova
;
212 new_iova
= alloc_iova_mem();
216 /* If size aligned is set then round the size to
217 * to next power of two.
220 size
= __roundup_pow_of_two(size
);
222 spin_lock_irqsave(&iovad
->iova_alloc_lock
, flags
);
223 ret
= __alloc_and_insert_iova_range(iovad
, size
, limit_pfn
,
224 new_iova
, size_aligned
);
226 spin_unlock_irqrestore(&iovad
->iova_alloc_lock
, flags
);
228 free_iova_mem(new_iova
);
236 * find_iova - find's an iova for a given pfn
237 * @iovad - iova domain in question.
238 * pfn - page frame number
239 * This function finds and returns an iova belonging to the
240 * given doamin which matches the given pfn.
242 struct iova
*find_iova(struct iova_domain
*iovad
, unsigned long pfn
)
245 struct rb_node
*node
;
247 /* Take the lock so that no other thread is manipulating the rbtree */
248 spin_lock_irqsave(&iovad
->iova_rbtree_lock
, flags
);
249 node
= iovad
->rbroot
.rb_node
;
251 struct iova
*iova
= container_of(node
, struct iova
, node
);
253 /* If pfn falls within iova's range, return iova */
254 if ((pfn
>= iova
->pfn_lo
) && (pfn
<= iova
->pfn_hi
)) {
255 spin_unlock_irqrestore(&iovad
->iova_rbtree_lock
, flags
);
256 /* We are not holding the lock while this iova
257 * is referenced by the caller as the same thread
258 * which called this function also calls __free_iova()
259 * and it is by desing that only one thread can possibly
260 * reference a particular iova and hence no conflict.
265 if (pfn
< iova
->pfn_lo
)
266 node
= node
->rb_left
;
267 else if (pfn
> iova
->pfn_lo
)
268 node
= node
->rb_right
;
271 spin_unlock_irqrestore(&iovad
->iova_rbtree_lock
, flags
);
276 * __free_iova - frees the given iova
277 * @iovad: iova domain in question.
278 * @iova: iova in question.
279 * Frees the given iova belonging to the giving domain
282 __free_iova(struct iova_domain
*iovad
, struct iova
*iova
)
286 spin_lock_irqsave(&iovad
->iova_rbtree_lock
, flags
);
287 __cached_rbnode_delete_update(iovad
, iova
);
288 rb_erase(&iova
->node
, &iovad
->rbroot
);
289 spin_unlock_irqrestore(&iovad
->iova_rbtree_lock
, flags
);
294 * free_iova - finds and frees the iova for a given pfn
295 * @iovad: - iova domain in question.
296 * @pfn: - pfn that is allocated previously
297 * This functions finds an iova for a given pfn and then
298 * frees the iova from that domain.
301 free_iova(struct iova_domain
*iovad
, unsigned long pfn
)
303 struct iova
*iova
= find_iova(iovad
, pfn
);
305 __free_iova(iovad
, iova
);
310 * put_iova_domain - destroys the iova doamin
311 * @iovad: - iova domain in question.
312 * All the iova's in that domain are destroyed.
314 void put_iova_domain(struct iova_domain
*iovad
)
316 struct rb_node
*node
;
319 spin_lock_irqsave(&iovad
->iova_rbtree_lock
, flags
);
320 node
= rb_first(&iovad
->rbroot
);
322 struct iova
*iova
= container_of(node
, struct iova
, node
);
323 rb_erase(node
, &iovad
->rbroot
);
325 node
= rb_first(&iovad
->rbroot
);
327 spin_unlock_irqrestore(&iovad
->iova_rbtree_lock
, flags
);
331 __is_range_overlap(struct rb_node
*node
,
332 unsigned long pfn_lo
, unsigned long pfn_hi
)
334 struct iova
*iova
= container_of(node
, struct iova
, node
);
336 if ((pfn_lo
<= iova
->pfn_hi
) && (pfn_hi
>= iova
->pfn_lo
))
342 __insert_new_range(struct iova_domain
*iovad
,
343 unsigned long pfn_lo
, unsigned long pfn_hi
)
347 iova
= alloc_iova_mem();
351 iova
->pfn_hi
= pfn_hi
;
352 iova
->pfn_lo
= pfn_lo
;
353 iova_insert_rbtree(&iovad
->rbroot
, iova
);
358 __adjust_overlap_range(struct iova
*iova
,
359 unsigned long *pfn_lo
, unsigned long *pfn_hi
)
361 if (*pfn_lo
< iova
->pfn_lo
)
362 iova
->pfn_lo
= *pfn_lo
;
363 if (*pfn_hi
> iova
->pfn_hi
)
364 *pfn_lo
= iova
->pfn_hi
+ 1;
368 * reserve_iova - reserves an iova in the given range
369 * @iovad: - iova domain pointer
370 * @pfn_lo: - lower page frame address
371 * @pfn_hi:- higher pfn adderss
372 * This function allocates reserves the address range from pfn_lo to pfn_hi so
373 * that this address is not dished out as part of alloc_iova.
376 reserve_iova(struct iova_domain
*iovad
,
377 unsigned long pfn_lo
, unsigned long pfn_hi
)
379 struct rb_node
*node
;
382 unsigned int overlap
= 0;
384 spin_lock_irqsave(&iovad
->iova_alloc_lock
, flags
);
385 spin_lock(&iovad
->iova_rbtree_lock
);
386 for (node
= rb_first(&iovad
->rbroot
); node
; node
= rb_next(node
)) {
387 if (__is_range_overlap(node
, pfn_lo
, pfn_hi
)) {
388 iova
= container_of(node
, struct iova
, node
);
389 __adjust_overlap_range(iova
, &pfn_lo
, &pfn_hi
);
390 if ((pfn_lo
>= iova
->pfn_lo
) &&
391 (pfn_hi
<= iova
->pfn_hi
))
399 /* We are here either becasue this is the first reserver node
400 * or need to insert remaining non overlap addr range
402 iova
= __insert_new_range(iovad
, pfn_lo
, pfn_hi
);
405 spin_unlock(&iovad
->iova_rbtree_lock
);
406 spin_unlock_irqrestore(&iovad
->iova_alloc_lock
, flags
);
411 * copy_reserved_iova - copies the reserved between domains
412 * @from: - source doamin from where to copy
413 * @to: - destination domin where to copy
414 * This function copies reserved iova's from one doamin to
418 copy_reserved_iova(struct iova_domain
*from
, struct iova_domain
*to
)
421 struct rb_node
*node
;
423 spin_lock_irqsave(&from
->iova_alloc_lock
, flags
);
424 spin_lock(&from
->iova_rbtree_lock
);
425 for (node
= rb_first(&from
->rbroot
); node
; node
= rb_next(node
)) {
426 struct iova
*iova
= container_of(node
, struct iova
, node
);
427 struct iova
*new_iova
;
428 new_iova
= reserve_iova(to
, iova
->pfn_lo
, iova
->pfn_hi
);
430 printk(KERN_ERR
"Reserve iova range %lx@%lx failed\n",
431 iova
->pfn_lo
, iova
->pfn_lo
);
433 spin_unlock(&from
->iova_rbtree_lock
);
434 spin_unlock_irqrestore(&from
->iova_alloc_lock
, flags
);
This page took 0.038247 seconds and 5 git commands to generate.