iova: allow allocation of lowest domain PFN
Subsystems (2)
PATCH 1/1 iova: allow allocation of lowest domain PFN
I found it was impossible to allocate all of the address space defined by an IOVA domain. For example, a trivial domain with 2 pages would cover PFNs 0 (start) and 1 (limit), but attempting to allocate more than one total PFN would fail because the start PFN could never be allocated.
This adds a function to prevent PFN limit calculations from dipping "below" the start PFN in __alloc_and_insert_iova_range() and __get_cached_rbnode(). It also alters the PFN validity checks in __alloc_and_insert_iova_range() to anticipate possible PFN rollover. These combine to allow every PFN within the IOVA domain to be available for allocation.
--- drivers/iommu/iova.c | 43 +++++++++++++++++++++++++++++++------------ 1 file changed, 31 insertions(+), 12 deletions(-)
drivers/iommu/iova.c +31 -12
@@ -32,6 +32,18 @@ static unsigned long iova_rcache_get(struct iova_domain *iovad,static void init_iova_rcaches (struct iova_domain *iovad);static void free_iova_rcaches (struct iova_domain *iovad); +static inline unsigned long +bounded_next_pfn (struct iova_domain *iovad,struct iova *iova) +{ +unsigned long next_pfn = iova->pfn_lo -1 ; + +if (!iova->pfn_lo) +return iovad->start_pfn; + +/* make sure the PFN doesn't rollover */ +return (next_pfn > iova->pfn_lo) ? iovad->start_pfn : next_pfn; +} +void init_iova_domain (struct iova_domain *iovad,unsigned long granule,unsigned long start_pfn,unsigned long pfn_32bit)
@@ -63,7 +75,7 @@ __get_cached_rbnode(struct iova_domain *iovad, unsigned long *limit_pfn)struct rb_node *prev_node =rb_prev (iovad->cached32_node);struct iova *curr_iova = rb_entry(iovad->cached32_node, struct iova, node); - *limit_pfn = curr_iova->pfn_lo -1 ; + *limit_pfn =bounded_next_pfn (iovad, curr_iova);return prev_node; } }
@@ -146,6 +158,7 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad,unsigned long flags;unsigned long saved_pfn;unsigned int pad_size =0 ; +unsigned long pfn_lo, pfn_hi;/* Walk the tree backwards */ spin_lock_irqsave (&iovad->iova_rbtree_lock, flags);
@@ -166,24 +179,30 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad,break ;/* found a free slot */ } adjust_limit_pfn: - limit_pfn = curr_iova->pfn_lo ? (curr_iova->pfn_lo -1 ) :0 ; + limit_pfn =bounded_next_pfn (iovad, curr_iova); move_left: prev = curr; curr =rb_prev (curr); } -if (!curr) { -if (size_aligned) - pad_size =iova_get_pad_size (size, limit_pfn); -if ((iovad->start_pfn + size + pad_size) > limit_pfn) { -spin_unlock_irqrestore (&iovad->iova_rbtree_lock, flags); -return -ENOMEM ; - } - } +if (size_aligned) + pad_size =iova_get_pad_size (size, limit_pfn);/* pfn_lo will point to size aligned address if size_aligned is set */ - new->pfn_lo = limit_pfn - (size + pad_size) +1 ; - new->pfn_hi = new->pfn_lo + size -1 ; + pfn_lo = limit_pfn - (size + pad_size) +1 ; + pfn_hi = pfn_lo + size -1 ; + +/* +* We're working with unsigned values, so we have to be careful about +* how we detect a PFN "below" the lowest PFN possible; zero. +*/ +if (pfn_lo < iovad->start_pfn || pfn_lo > limit_pfn) { +spin_unlock_irqrestore (&iovad->iova_rbtree_lock, flags); +return -ENOMEM ; + } + + new->pfn_lo = pfn_lo; + new->pfn_hi = pfn_hi;/* If we have 'prev', it's a valid place to start the insertion. */ iova_insert_rbtree (&iovad->rbroot, new, prev);
Signature · 1 line
2.7.4
A message that is not in the archive (sent off-list or not yet received): 102275367.137137.1494509795293.JavaMail.zimbra-AQeFf1F/[email protected]
----- Original Message -----
Quoted 9 lines
From: "Aaron Sierra" <asierra-AQeFf1F/[email protected]>
Sent: Thursday, May 11, 2017 8:36:35 AMI found it was impossible to allocate all of the address space defined by an IOVA domain. For example, a trivial domain with 2 pages would cover PFNs 0 (start) and 1 (limit), but attempting to allocate more than one total PFN would fail because the start PFN could never be allocated.
Quoted 6 lines
This adds a function to prevent PFN limit calculations from dipping "below" the start PFN in
__alloc_and_insert_iova_range()and__get_cached_rbnode(). It also alters the PFN validity checks in__alloc_and_insert_iova_range()to anticipate possible PFN rollover. These combine to allow every PFN within the IOVA domain to be available for allocation.
I should point out that I've understated the impact a bit. In the trivial example, 1 page isn't just 1 page, it represents half of the available address space. In less trivial examples, not being able to allocate the start PFN can prevent a range of any size that would include it. Therefore, attempting to allocate:
* all of the address space in one shot will fail
* the 2nd half of the address space in one shot will fail
* the 4th quarter of the address space in one shot will fail
* et cetera
-Aaron S.
Quoted 4 lines
Signed-off-by Aaron Sierra <asierra-AQeFf1F/[email protected]>---
drivers/iommu/iova.c| 43 +++++++++++++++++++++++++++++++------------1 file changed, 31 insertions(+), 12 deletions(-)
Hi Aaron,
Quoted 5 lines · Aaron Sierra
I found it was impossible to allocate all of the address space defined by an IOVA domain. For example, a trivial domain with 2 pages would cover PFNs 0 (start) and 1 (limit), but attempting to allocate more than one total PFN would fail because the start PFN could never be allocated.
Does this only happen when start_pfn is 0? The recent fix in 5016bdb796b3 implies that allocating the entire address space works fine, albeit with a non-zero start_pfn. I was about to say that for all current callers, start_pfn is always at least 1 anyway, but I see the Nvidia DRM stuff in next is making that no longer true, oh well.
Quoted 20 lines
This adds a function to prevent PFN limit calculations from dipping "below" the start PFN in
__alloc_and_insert_iova_range()and__get_cached_rbnode(). It also alters the PFN validity checks in__alloc_and_insert_iova_range()to anticipate possible PFN rollover. These combine to allow every PFN within the IOVA domain to be available for allocation.Signed-off-by Aaron Sierra <asierra-AQeFf1F/[email protected]>--- drivers/iommu/iova.c | 43 +++++++++++++++++++++++++++++++------------ 1 file changed, 31 insertions(+), 12 deletions(-)drivers/iommu/iova.c +0
-0@@ -32,6 +32,18 @@ static unsigned long iova_rcache_get(struct iova_domain *iovad,static void init_iova_rcaches (struct iova_domain *iovad);static void free_iova_rcaches (struct iova_domain *iovad);
drivers/iommu/iova.c static unsigned long iova_rcache_get(struct iova_domain *iovad, · line 44
Quoted 10 lines
drivers/iommu/iova.c +10
-0+static inline unsigned long +bounded_next_pfn (struct iova_domain *iovad,struct iova *iova) +{ +unsigned long next_pfn = iova->pfn_lo -1 ; + +if (!iova->pfn_lo) +return iovad->start_pfn; + +/* make sure the PFN doesn't rollover */ +return (next_pfn > iova->pfn_lo) ? iovad->start_pfn : next_pfn;
Why this check? Substituting the definition of next_pfn:
((iova->pfn_lo - 1) > iova->pfn_lo)
which is only true if iova->pfn_lo == 0, in which case we never get this far anyway.
I'm also not sure about returning start_pfn instead of 0 in the underflow case, since reserved entries may exist in the tree such that pfn_lo < start_pfn, and I'm not convinced that returning a "next" PFN which is actually "previous" to the lowest entry won't cause things to go horrendously wrong.
Quoted 27 lines
drivers/iommu/iova.c +4
-2+} +void init_iova_domain (struct iova_domain *iovad,unsigned long granule,unsigned long start_pfn,unsigned long pfn_32bit)@@ -63,7 +75,7 @@ __get_cached_rbnode(struct iova_domain *iovad, unsigned long *limit_pfn)struct rb_node *prev_node =rb_prev (iovad->cached32_node);struct iova *curr_iova = rb_entry(iovad->cached32_node, struct iova, node); - *limit_pfn = curr_iova->pfn_lo -1 ; + *limit_pfn =bounded_next_pfn (iovad, curr_iova);return prev_node; } }@@ -146,6 +158,7 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad,unsigned long flags;unsigned long saved_pfn;unsigned int pad_size =0 ; +unsigned long pfn_lo, pfn_hi;/* Walk the tree backwards */ spin_lock_irqsave (&iovad->iova_rbtree_lock, flags);@@ -166,24 +179,30 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad,break ;/* found a free slot */ } adjust_limit_pfn: - limit_pfn = curr_iova->pfn_lo ? (curr_iova->pfn_lo -1 ) :0 ;
drivers/iommu/iova.c static int __alloc_and_insert_iova_range(struct iova_domain *iovad, · line 178
Quoted 10 lines
drivers/iommu/iova.c +1
-4+ limit_pfn =bounded_next_pfn (iovad, curr_iova); move_left: prev = curr; curr =rb_prev (curr); } -if (!curr) { -if (size_aligned) - pad_size =iova_get_pad_size (size, limit_pfn); -if ((iovad->start_pfn + size + pad_size) > limit_pfn) {
Wouldn't it be sufficient to just change this to
if ((iovad->start_pfn + size + pad_size - 1) > limit_pfn)
?
Since a size of 0 is invalid, that would appear to be sufficiently resistant to underflow.
Robin.
Quoted 28 lines
drivers/iommu/iova.c +16
-6-spin_unlock_irqrestore (&iovad->iova_rbtree_lock, flags); -return -ENOMEM ; - } - } +if (size_aligned) + pad_size =iova_get_pad_size (size, limit_pfn);/* pfn_lo will point to size aligned address if size_aligned is set */ - new->pfn_lo = limit_pfn - (size + pad_size) +1 ; - new->pfn_hi = new->pfn_lo + size -1 ; + pfn_lo = limit_pfn - (size + pad_size) +1 ; + pfn_hi = pfn_lo + size -1 ; + +/* +* We're working with unsigned values, so we have to be careful about +* how we detect a PFN "below" the lowest PFN possible; zero. +*/ +if (pfn_lo < iovad->start_pfn || pfn_lo > limit_pfn) { +spin_unlock_irqrestore (&iovad->iova_rbtree_lock, flags); +return -ENOMEM ; + } + + new->pfn_lo = pfn_lo; + new->pfn_hi = pfn_hi;/* If we have 'prev', it's a valid place to start the insertion. */ iova_insert_rbtree (&iovad->rbroot, new, prev);
A message that is not in the archive (sent off-list or not yet received): 7c703cfd-e667-bdce-de49-ae31a696b5dd-5wv7dgnIgG8@public.gmane.org
----- Original Message -----
Quoted 5 lines
From: "Robin Murphy" <[email protected]>
To: "Aaron Sierra" <asierra-AQeFf1F/[email protected]>, "Joerg Roedel" <[email protected]>
Cc: "iommu" <iommu-cunTk1MwBs9QetFLy7KEm3xJsTq8ys+cHZ5vskTnxNA@public.gmane.org>, "Nate Watterson" <[email protected]>
Sent: Thursday, May 11, 2017 12:39:01 PM
Subject: Re: [PATCH] iova: allow allocation of lowest domain PFN
Robin,
Quoted 9 lines
Hi Aaron,
Quoted 5 lines · Aaron Sierra
I found it was impossible to allocate all of the address space defined by an IOVA domain. For example, a trivial domain with 2 pages would cover PFNs 0 (start) and 1 (limit), but attempting to allocate more than one total PFN would fail because the start PFN could never be allocated.
Quoted 5 lines
Does this only happen when
start_pfnis 0? The recent fix in5016bdb796b3implies that allocating the entire address space works fine, albeit with a non-zerostart_pfn. I was about to say that for all current callers,start_pfnis always at least 1 anyway, but I see the Nvidia DRM stuff in next is making that no longer true, oh well.
No, this limitation exists regardless of the start_pfn value. I've tested 0, 1, then powers-of-two up to half of the limit_pfn.
The problem with the test case laid out in 5016bdb796b3 is that start_pfn is 1 and limit_pfn is odd (as usual), so the number of available PFNs is odd. Therefore allocating two at a time can't possibly allocate all of the address space.
Quoted 34 lines
Quoted 21 lines
This adds a function to prevent PFN limit calculations from dipping "below" the start PFN in
__alloc_and_insert_iova_range()and__get_cached_rbnode(). It also alters the PFN validity checks in__alloc_and_insert_iova_range()to anticipate possible PFN rollover. These combine to allow every PFN within the IOVA domain to be available for allocation.Signed-off-by Aaron Sierra <asierra-AQeFf1F/[email protected]>--- drivers/iommu/iova.c | 43 +++++++++++++++++++++++++++++++------------ 1 file changed, 31 insertions(+), 12 deletions(-)drivers/iommu/iova.c +0
-0@@ -32,6 +32,18 @@ static unsigned long iova_rcache_get(struct iova_domain *iovad, static void init_iova_rcaches(struct iova_domain *iovad);static void free_iova_rcaches (struct iova_domain *iovad);drivers/iommu/iova.c static unsigned long iova_rcache_get(struct iova_domain · line 45
Quoted 10 lines
drivers/iommu/iova.c +10
-0+static inline unsigned long +bounded_next_pfn (struct iova_domain *iovad,struct iova *iova) +{ +unsigned long next_pfn = iova->pfn_lo -1 ; + +if (!iova->pfn_lo) +return iovad->start_pfn; + +/* make sure the PFN doesn't rollover */ +return (next_pfn > iova->pfn_lo) ? iovad->start_pfn : next_pfn;Why this check? Substituting the definition of
next_pfn:
Quoted 4 lines
((iova->pfn_lo - 1) > iova->pfn_lo)which is only true if
iova->pfn_lo== 0, in which case we never get this far anyway.
That's a good question. That should be able to be simplified.
Quoted 5 lines
I'm also not sure about returning
start_pfninstead of 0 in the underflow case, since reserved entries may exist in the tree such thatpfn_lo<start_pfn, and I'm not convinced that returning a "next" PFN which is actually "previous" to the lowest entry won't cause things to go horrendously wrong.
I didn't realize that reservations could occur below the defined IOVA domain lower limit. Is that really intended behavior? I'd expected that if you wanted to reserve 0, for example, you'd define a domain starting at zero, then reserve that PFN before making the domain generally available.
[ snip ]
Quoted 9 lines
drivers/iommu/iova.c static int __alloc_and_insert_iova_range(struct iova_domain *iovad, · line 178
Quoted 5 lines
drivers/iommu/iova.c +0
-4-if (!curr) { -if (size_aligned) - pad_size =iova_get_pad_size (size, limit_pfn); -if ((iovad->start_pfn + size + pad_size) > limit_pfn) {Wouldn't it be sufficient to just change this to
if ((iovad->start_pfn + size + pad_size - 1) > limit_pfn)
That may be. My original solution was equivalent, but factored differently (i.e. limit_pfn + 1). I couldn't fully wrap my head around the logic and was worried about missing corner cases. If that is indeed a complete fix, could the refactoring below still be beneficial?
-Aaron S.
Quoted 34 lines
?
Since a size of 0 is invalid, that would appear to be sufficiently resistant to underflow.
Robin.
Quoted 27 lines
drivers/iommu/iova.c +16
-6-spin_unlock_irqrestore (&iovad->iova_rbtree_lock, flags); -return -ENOMEM ; - } - } +if (size_aligned) + pad_size =iova_get_pad_size (size, limit_pfn);/* pfn_lo will point to size aligned address if size_aligned is set */ - new->pfn_lo = limit_pfn - (size + pad_size) +1 ; - new->pfn_hi = new->pfn_lo + size -1 ; + pfn_lo = limit_pfn - (size + pad_size) +1 ; + pfn_hi = pfn_lo + size -1 ; + +/* +* We're working with unsigned values, so we have to be careful about +* how we detect a PFN "below" the lowest PFN possible; zero. +*/ +if (pfn_lo < iovad->start_pfn || pfn_lo > limit_pfn) { +spin_unlock_irqrestore (&iovad->iova_rbtree_lock, flags); +return -ENOMEM ; + } + + new->pfn_lo = pfn_lo; + new->pfn_hi = pfn_hi;/* If we have 'prev', it's a valid place to start the insertion. */ iova_insert_rbtree (&iovad->rbroot, new, prev);
A message that is not in the archive (sent off-list or not yet received): 433111847.511288.1494527238012.JavaMail.zimbra-AQeFf1F/[email protected]
Quoted 24 lines · Aaron Sierra
----- Original Message -----
Quoted 5 lines
From: "Robin Murphy" <[email protected]>
To: "Aaron Sierra" <asierra-AQeFf1F/[email protected]>, "Joerg Roedel" <[email protected]>
Cc: "iommu" <iommu-cunTk1MwBs9QetFLy7KEm3xJsTq8ys+cHZ5vskTnxNA@public.gmane.org>, "Nate Watterson" <[email protected]>
Sent: Thursday, May 11, 2017 12:39:01 PM
Subject: Re: [PATCH] iova: allow allocation of lowest domain PFNRobin,
Quoted 9 lines
Hi Aaron,
Quoted 5 lines · Aaron Sierra
I found it was impossible to allocate all of the address space defined by an IOVA domain. For example, a trivial domain with 2 pages would cover PFNs 0 (start) and 1 (limit), but attempting to allocate more than one total PFN would fail because the start PFN could never be allocated.
Quoted 5 lines
Does this only happen when
start_pfnis 0? The recent fix in5016bdb796b3implies that allocating the entire address space works fine, albeit with a non-zerostart_pfn. I was about to say that for all current callers,start_pfnis always at least 1 anyway, but I see the Nvidia DRM stuff in next is making that no longer true, oh well.
Quoted 7 lines
No, this limitation exists regardless of the
start_pfnvalue. I've tested 0, 1, then powers-of-two up to half of thelimit_pfn.The problem with the test case laid out in
5016bdb796b3is thatstart_pfnis 1 andlimit_pfnis odd (as usual), so the number of available PFNs is odd. Therefore allocating two at a time can't possibly allocate all of the address space.
Ah, right you are. I had misread Nate's example as a 2-page address space, not a 3-page one.
Quoted 47 lines
Quoted 34 lines
Quoted 21 lines
This adds a function to prevent PFN limit calculations from dipping "below" the start PFN in
__alloc_and_insert_iova_range()and__get_cached_rbnode(). It also alters the PFN validity checks in__alloc_and_insert_iova_range()to anticipate possible PFN rollover. These combine to allow every PFN within the IOVA domain to be available for allocation.Signed-off-by Aaron Sierra <asierra-AQeFf1F/[email protected]>--- drivers/iommu/iova.c | 43 +++++++++++++++++++++++++++++++------------ 1 file changed, 31 insertions(+), 12 deletions(-)drivers/iommu/iova.c +0
-0@@ -32,6 +32,18 @@ static unsigned long iova_rcache_get(struct iova_domain *iovad, static void init_iova_rcaches(struct iova_domain *iovad);static void free_iova_rcaches (struct iova_domain *iovad);drivers/iommu/iova.c static unsigned long iova_rcache_get(struct iova_domain · line 45
Quoted 10 lines
drivers/iommu/iova.c +10
-0+static inline unsigned long +bounded_next_pfn (struct iova_domain *iovad,struct iova *iova) +{ +unsigned long next_pfn = iova->pfn_lo -1 ; + +if (!iova->pfn_lo) +return iovad->start_pfn; + +/* make sure the PFN doesn't rollover */ +return (next_pfn > iova->pfn_lo) ? iovad->start_pfn : next_pfn;Why this check? Substituting the definition of
next_pfn:Quoted 4 lines
((iova->pfn_lo - 1) > iova->pfn_lo)which is only true if
iova->pfn_lo== 0, in which case we never get this far anyway.That's a good question. That should be able to be simplified.
Quoted 5 lines
I'm also not sure about returning
start_pfninstead of 0 in the underflow case, since reserved entries may exist in the tree such thatpfn_lo<start_pfn, and I'm not convinced that returning a "next" PFN which is actually "previous" to the lowest entry won't cause things to go horrendously wrong.
Quoted 4 lines
I didn't realize that reservations could occur below the defined IOVA domain lower limit. Is that really intended behavior? I'd expected that if you wanted to reserve 0, for example, you'd define a domain starting at zero, then reserve that PFN before making the domain generally available.
Yes, reservations are inserted directly into the tree without reference to the allocation limits. It's not really set in stone, but it seems that the general pattern is the the limits are for addresses which would never be considered valid (i.e. anything physically out of range for the given device, plus 0 for the sake of software), whereas reservations are for addresses which are nominally valid, but can't be remapped due to other reasons.
Quoted 10 lines
[ snip ]
Quoted 8 lines
drivers/iommu/iova.c
Quoted 5 lines
drivers/iommu/iova.c +0
-4-if (!curr) { -if (size_aligned) - pad_size =iova_get_pad_size (size, limit_pfn); -if ((iovad->start_pfn + size + pad_size) > limit_pfn) {Wouldn't it be sufficient to just change this to
Quoted 6 lines
Quoted 1 line
if ((iovad->start_pfn + size + pad_size - 1) > limit_pfn)That may be. My original solution was equivalent, but factored differently (i.e.
limit_pfn+ 1). I couldn't fully wrap my head around the logic and was worried about missing corner cases. If that is indeed a complete fix, could the refactoring below still be beneficial?
Having given it some more thought, it's clear that the fundamental problem is that having both start_pfn and limit_pfn be inclusive creates a troublesome ambiguity, and we're really just adding further complication in attempts to paper over that. I reckon it might be a lot more straightforward to cut that ambiguity out altogether by just making limit_pfn exclusive, since it has plenty of room to avoid overflow - I've lightly tested the below via dma-iommu (i.e. booting a machine and doing some I/O), but at this stage it comes with no guarantees (after all, it's basically the mother of all off-by-ones...)
If it checks out I'm happy to write up a proper patch.
Robin.
----->8-----
drivers/iommu/iova.c +0 -0
@@ -48,7 +48,7 @@ init_iova_domain(struct iova_domain *iovad, unsigned
long granule,
iovad->cached32_node = NULL;
iovad->granule = granule;
iovad->start_pfn = start_pfn;
- iovad->dma_32bit_pfn = pfn_32bit;
+ iovad->dma_32bit_pfn = pfn_32bit + 1;
init_iova_rcaches(iovad);
}
EXPORT_SYMBOL_GPL(init_iova_domain);
@@ -63,7 +63,7 @@ __get_cached_rbnode(struct iova_domain *iovad, unsigned long *limit_pfn)
struct rb_node *prev_node = rb_prev(iovad->cached32_node); struct iova *curr_iova =
rb_entry(iovad->cached32_node, struct iova, node);
- *limit_pfn = curr_iova->pfn_lo - 1;
+ *limit_pfn = curr_iova->pfn_lo;
return prev_node;
}
}
@@ -135,7 +135,7 @@ iova_insert_rbtree(struct rb_root *root, struct iova *iova,
static unsigned int
iova_get_pad_size(unsigned int size, unsigned int limit_pfn) {
- return (limit_pfn + 1 - size) & (__roundup_pow_of_two(size) - 1);
+ return (limit_pfn - size) & (__roundup_pow_of_two(size) - 1);
}
static int __alloc_and_insert_iova_range(struct iova_domain *iovad,
@@ -155,18 +155,18 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad,
while (curr) {
struct iova *curr_iova = rb_entry(curr, struct iova, node);
- if (limit_pfn < curr_iova->pfn_lo)
+ if (limit_pfn <= curr_iova->pfn_lo)
goto move_left;
- else if (limit_pfn < curr_iova->pfn_hi)
+ else if (limit_pfn <= curr_iova->pfn_hi)
goto adjust_limit_pfn;
else {
if (size_aligned)
pad_size = iova_get_pad_size(size, limit_pfn);
- if ((curr_iova->pfn_hi + size + pad_size) <= limit_pfn)
+ if ((curr_iova->pfn_hi + size + pad_size) < limit_pfn)
break; /* found a free slot */
}
adjust_limit_pfn:
- limit_pfn = curr_iova->pfn_lo ? (curr_iova->pfn_lo - 1) : 0;
+ limit_pfn = curr_iova->pfn_lo;
move_left:
prev = curr;
curr = rb_prev(curr);
@@ -182,7 +182,7 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad,
}
/* pfn_lo will point to size aligned address if size_aligned is set */
- new->pfn_lo = limit_pfn - (size + pad_size) + 1;
+ new->pfn_lo = limit_pfn - (size + pad_size);
new->pfn_hi = new->pfn_lo + size - 1;
/* If we have 'prev', it's a valid place to start the insertion. */
@@ -269,7 +269,7 @@ alloc_iova(struct iova_domain *iovad, unsigned long size,
if (!new_iova)
return NULL;
- ret = __alloc_and_insert_iova_range(iovad, size, limit_pfn,
+ ret = __alloc_and_insert_iova_range(iovad, size, limit_pfn + 1,
new_iova, size_aligned);
if (ret) {
----- Original Message -----
Quoted 5 lines
From: "Robin Murphy" <[email protected]>
To: "Aaron Sierra" <asierra-AQeFf1F/[email protected]>, "Joerg Roedel" <[email protected]>
Cc: "iommu" <iommu-cunTk1MwBs9QetFLy7KEm3xJsTq8ys+cHZ5vskTnxNA@public.gmane.org>, "Nate Watterson" <[email protected]>
Sent: Thursday, May 11, 2017 12:39:01 PM
Subject: Re: [PATCH] iova: allow allocation of lowest domain PFN
Robin,
Quoted 9 lines
Hi Aaron,
Quoted 5 lines · Aaron Sierra
I found it was impossible to allocate all of the address space defined by an IOVA domain. For example, a trivial domain with 2 pages would cover PFNs 0 (start) and 1 (limit), but attempting to allocate more than one total PFN would fail because the start PFN could never be allocated.
Quoted 5 lines
Does this only happen when
start_pfnis 0? The recent fix in5016bdb796b3implies that allocating the entire address space works fine, albeit with a non-zerostart_pfn. I was about to say that for all current callers,start_pfnis always at least 1 anyway, but I see the Nvidia DRM stuff in next is making that no longer true, oh well.
No, this limitation exists regardless of the start_pfn value. I've tested 0, 1, then powers-of-two up to half of the limit_pfn.
The problem with the test case laid out in 5016bdb796b3 is that start_pfn is 1 and limit_pfn is odd (as usual), so the number of available PFNs is odd. Therefore allocating two at a time can't possibly allocate all of the address space.
Quoted 34 lines
Quoted 21 lines
This adds a function to prevent PFN limit calculations from dipping "below" the start PFN in
__alloc_and_insert_iova_range()and__get_cached_rbnode(). It also alters the PFN validity checks in__alloc_and_insert_iova_range()to anticipate possible PFN rollover. These combine to allow every PFN within the IOVA domain to be available for allocation.Signed-off-by Aaron Sierra <asierra-AQeFf1F/[email protected]>--- drivers/iommu/iova.c | 43 +++++++++++++++++++++++++++++++------------ 1 file changed, 31 insertions(+), 12 deletions(-)drivers/iommu/iova.c +0
-0@@ -32,6 +32,18 @@ static unsigned long iova_rcache_get(struct iova_domain *iovad, static void init_iova_rcaches(struct iova_domain *iovad);static void free_iova_rcaches (struct iova_domain *iovad);drivers/iommu/iova.c static unsigned long iova_rcache_get(struct iova_domain · line 45
Quoted 10 lines
drivers/iommu/iova.c +10
-0+static inline unsigned long +bounded_next_pfn (struct iova_domain *iovad,struct iova *iova) +{ +unsigned long next_pfn = iova->pfn_lo -1 ; + +if (!iova->pfn_lo) +return iovad->start_pfn; + +/* make sure the PFN doesn't rollover */ +return (next_pfn > iova->pfn_lo) ? iovad->start_pfn : next_pfn;Why this check? Substituting the definition of
next_pfn:
Quoted 4 lines
((iova->pfn_lo - 1) > iova->pfn_lo)which is only true if
iova->pfn_lo== 0, in which case we never get this far anyway.
That's a good question. That should be able to be simplified.
Quoted 5 lines
I'm also not sure about returning
start_pfninstead of 0 in the underflow case, since reserved entries may exist in the tree such thatpfn_lo<start_pfn, and I'm not convinced that returning a "next" PFN which is actually "previous" to the lowest entry won't cause things to go horrendously wrong.
I didn't realize that reservations could occur below the defined IOVA domain lower limit. Is that really intended behavior? I'd expected that if you wanted to reserve 0, for example, you'd define a domain starting at zero, then reserve that PFN before making the domain generally available.
[ snip ]
Quoted 9 lines
drivers/iommu/iova.c static int __alloc_and_insert_iova_range(struct iova_domain *iovad, · line 178
Quoted 5 lines
drivers/iommu/iova.c +0
-4-if (!curr) { -if (size_aligned) - pad_size =iova_get_pad_size (size, limit_pfn); -if ((iovad->start_pfn + size + pad_size) > limit_pfn) {Wouldn't it be sufficient to just change this to
if ((iovad->start_pfn + size + pad_size - 1) > limit_pfn)
That may be. My original solution was equivalent, but factored differently (i.e. limit_pfn + 1). I couldn't fully wrap my head around the logic and was worried about missing corner cases. If that is indeed a complete fix, could the refactoring below still be beneficial?
-Aaron S.
Quoted 34 lines
?
Since a size of 0 is invalid, that would appear to be sufficiently resistant to underflow.
Robin.
Quoted 27 lines
drivers/iommu/iova.c +16
-6-spin_unlock_irqrestore (&iovad->iova_rbtree_lock, flags); -return -ENOMEM ; - } - } +if (size_aligned) + pad_size =iova_get_pad_size (size, limit_pfn);/* pfn_lo will point to size aligned address if size_aligned is set */ - new->pfn_lo = limit_pfn - (size + pad_size) +1 ; - new->pfn_hi = new->pfn_lo + size -1 ; + pfn_lo = limit_pfn - (size + pad_size) +1 ; + pfn_hi = pfn_lo + size -1 ; + +/* +* We're working with unsigned values, so we have to be careful about +* how we detect a PFN "below" the lowest PFN possible; zero. +*/ +if (pfn_lo < iovad->start_pfn || pfn_lo > limit_pfn) { +spin_unlock_irqrestore (&iovad->iova_rbtree_lock, flags); +return -ENOMEM ; + } + + new->pfn_lo = pfn_lo; + new->pfn_hi = pfn_hi;/* If we have 'prev', it's a valid place to start the insertion. */ iova_insert_rbtree (&iovad->rbroot, new, prev);