iommu/iova: Retry from last rb tree node if iova search fails
Subsystems (2)
PATCH 1/1 iommu/iova: Retry from last rb tree node if iova search fails
From: Vijayanand Jitta <[email protected]>
When ever a new iova alloc request comes iova is always searched from the cached node and the nodes which are previous to cached node. So, even if there is free iova space available in the nodes which are next to the cached node iova allocation can still fail because of this approach.
Consider the following sequence of iova alloc and frees on 1GB of iova space
1) alloc - 500MB
2) alloc - 12MB
3) alloc - 499MB
4) free - 12MB which was allocated in step 2
5) alloc - 13MB
After the above sequence we will have 12MB of free iova space and cached node will be pointing to the iova pfn of last alloc of 13MB which will be the lowest iova pfn of that iova space. Now if we get an alloc request of 2MB we just search from cached node and then look for lower iova pfn's for free iova and as they aren't any, iova alloc fails though there is 12MB of free iova space.
To avoid such iova search failures do a retry from the last rb tree node when iova search fails, this will search the entire tree and get an iova if its available
--- drivers/iommu/iova.c | 11 +++++++++++ 1 file changed, 11 insertions(+)
drivers/iommu/iova.c +11 -0
@@ -186,6 +186,7 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad,unsigned long flags;unsigned long new_pfn;unsigned long align_mask = ~0UL ; +bool retry = false;if (size_aligned) align_mask <<=fls_long (size -1 );
@@ -198,6 +199,8 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad, curr =__get_cached_rbnode (iovad, limit_pfn); curr_iova = rb_entry(curr, struct iova, node); + +retry_search: do { limit_pfn = min(limit_pfn, curr_iova->pfn_lo); new_pfn = (limit_pfn - size) & align_mask;
@@ -207,6 +210,14 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad, }while (curr && new_pfn <= curr_iova->pfn_hi);if (limit_pfn < size || new_pfn < iovad->start_pfn) { +if (!retry) { + curr =rb_last (&iovad->rbroot); + curr_iova = rb_entry(curr, struct iova, node); + limit_pfn = curr_iova->pfn_lo; + retry = true; + goto retry_search; + } + iovad->max32_alloc_size = size; goto iova32_full; }
Signature · 2 lines
QUALCOMM INDIA, on behalf of Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation 1.9.1
Robin Murphy
maintainerQuoted 17 lines · On 2020-05-06 9:01 pm, [email protected] wrote:
From: Vijayanand Jitta <[email protected]>
When ever a new iova alloc request comes iova is always searched from the cached node and the nodes which are previous to cached node. So, even if there is free iova space available in the nodes which are next to the cached node iova allocation can still fail because of this approach.
Consider the following sequence of iova alloc and frees on 1GB of iova space
1) alloc - 500MB
2) alloc - 12MB
3) alloc - 499MB
4) free - 12MB which was allocated in step 2
5) alloc - 13MB
Quoted 6 lines
After the above sequence we will have 12MB of free iova space and cached node will be pointing to the iova pfn of last alloc of 13MB which will be the lowest iova pfn of that iova space. Now if we get an alloc request of 2MB we just search from cached node and then look for lower iova pfn's for free iova and as they aren't any, iova alloc fails though there is 12MB of free iova space.
Yup, this could definitely do with improving. Unfortunately I think this particular implementation is slightly flawed...
Quoted 31 lines
To avoid such iova search failures do a retry from the last rb tree node when iova search fails, this will search the entire tree and get an iova if its available
Signed-off-by Vijayanand Jitta <[email protected]>--- drivers/iommu/iova.c | 11 +++++++++++ 1 file changed, 11 insertions(+)drivers/iommu/iova.c +3
-0@@ -186,6 +186,7 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad,unsigned long flags;unsigned long new_pfn;unsigned long align_mask = ~0UL ; +bool retry = false;if (size_aligned) align_mask <<=fls_long (size -1 );@@ -198,6 +199,8 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad, curr =__get_cached_rbnode (iovad, limit_pfn); curr_iova = rb_entry(curr, struct iova, node); + +retry_search: do { limit_pfn = min(limit_pfn, curr_iova->pfn_lo); new_pfn = (limit_pfn - size) & align_mask;
drivers/iommu/iova.c static int __alloc_and_insert_iova_range(struct iova_domain *iovad, · line 214
Quoted 5 lines
drivers/iommu/iova.c +2
-0@@ -207,6 +210,14 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad, }while (curr && new_pfn <= curr_iova->pfn_hi);if (limit_pfn < size || new_pfn < iovad->start_pfn) { +if (!retry) { + curr =rb_last (&iovad->rbroot);
Why walk when there's an anchor node there already? However...
drivers/iommu/iova.c static int __alloc_and_insert_iova_range(struct iova_domain *iovad, · line 216
Quoted 2 lines
drivers/iommu/iova.c +2
-0+ curr_iova = rb_entry(curr, struct iova, node); + limit_pfn = curr_iova->pfn_lo;
...this doesn't look right, as by now we've lost the original limit_pfn supplied by the caller, so are highly likely to allocate beyond the range our caller asked for. In fact AFAICS we'd start allocating from directly directly below the anchor node, beyond the end of the entire address space.
The logic I was imagining we want here was something like the rapidly hacked up (and untested) diff below.
Thanks,
Robin.
----->8-----
drivers/iommu/iova.c +14 -3
@@ -186,6 +186,7 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad,unsigned long flags;unsigned long new_pfn;unsigned long align_mask = ~0UL ; +unsigned long alloc_hi, alloc_lo;if (size_aligned) align_mask <<=fls_long (size -1 );
@@ -196,17 +197,27 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad, size >= iovad->max32_alloc_size) goto iova32_full; + alloc_hi =IOVA_ANCHOR ; + alloc_lo = iovad->start_pfn; +retry: curr =__get_cached_rbnode (iovad, limit_pfn); curr_iova = rb_entry(curr, struct iova, node); +if (alloc_hi < curr_iova->pfn_hi) { + alloc_lo = curr_iova->pfn_hi; + alloc_hi = limit_pfn; + } +do { - limit_pfn =min (limit_pfn, curr_iova->pfn_lo); - new_pfn = (limit_pfn - size) & align_mask; + alloc_hi =min (alloc_hi, curr_iova->pfn_lo); + new_pfn = (alloc_hi - size) & align_mask; prev = curr; curr =rb_prev (curr); curr_iova = rb_entry(curr, struct iova, node); }while (curr && new_pfn <= curr_iova->pfn_hi); -if (limit_pfn < size || new_pfn < iovad->start_pfn) { +if (limit_pfn < size || new_pfn < alloc_lo) { +if (alloc_lo == iovad->start_pfn) + goto retry; iovad->max32_alloc_size = size; goto iova32_full; }
Quoted 64 lines · Robin Murphy
Quoted 17 lines · On 2020-05-06 9:01 pm, [email protected] wrote:
From: Vijayanand Jitta <[email protected]>
When ever a new iova alloc request comes iova is always searched from the cached node and the nodes which are previous to cached node. So, even if there is free iova space available in the nodes which are next to the cached node iova allocation can still fail because of this approach.
Consider the following sequence of iova alloc and frees on 1GB of iova space
1) alloc - 500MB
2) alloc - 12MB
3) alloc - 499MB
4) free - 12MB which was allocated in step 2
5) alloc - 13MBQuoted 6 lines
After the above sequence we will have 12MB of free iova space and cached node will be pointing to the iova pfn of last alloc of 13MB which will be the lowest iova pfn of that iova space. Now if we get an alloc request of 2MB we just search from cached node and then look for lower iova pfn's for free iova and as they aren't any, iova alloc fails though there is 12MB of free iova space.
Yup, this could definitely do with improving. Unfortunately I think this particular implementation is slightly flawed...
Quoted 36 lines
To avoid such iova search failures do a retry from the last rb tree node when iova search fails, this will search the entire tree and get an iova if its available
Signed-off-by Vijayanand Jitta <[email protected]>--- drivers/iommu/iova.c | 11 +++++++++++ 1 file changed, 11 insertions(+)drivers/iommu/iova.c +1
-0@@ -186,6 +186,7 @@ static int __alloc_and_insert_iova_range(structiova_domain *iovad, unsigned long flags;unsigned long new_pfn;unsigned long align_mask = ~0UL ; +bool retry = false;if (size_aligned)align_mask <<= fls_long(size - 1);drivers/iommu/iova.c +2
-0@@ -198,6 +199,8 @@ static int __alloc_and_insert_iova_range(structiova_domain *iovad, curr =__get_cached_rbnode (iovad, limit_pfn); curr_iova = rb_entry(curr, struct iova, node); + +retry_search: do { limit_pfn = min(limit_pfn, curr_iova->pfn_lo);new_pfn = (limit_pfn - size) & align_mask;drivers/iommu/iova.c +0
-0@@ -207,6 +210,14 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad, }while (curr && new_pfn <= curr_iova->pfn_hi);
Quoted 5 lines
drivers/iommu/iova.c static int __alloc_and_insert_iova_range(struct · line 215
Quoted 3 lines
drivers/iommu/iova.c +2
-0if (limit_pfn < size || new_pfn < iovad->start_pfn) { +if (!retry) { + curr =rb_last (&iovad->rbroot);Why walk when there's an anchor node there already? However...
+1
Quoted 9 lines
drivers/iommu/iova.c static int __alloc_and_insert_iova_range(struct · line 217
Quoted 3 lines
drivers/iommu/iova.c +2
-0+ curr_iova = rb_entry(curr, struct iova, node); + limit_pfn = curr_iova->pfn_lo;...this doesn't look right, as by now we've lost the original
limit_pfnsupplied by the caller, so are highly likely to allocate beyond the range our caller asked for. In fact AFAICS we'd start allocating from directly directly below the anchor node, beyond the end of the entire address space.
+1
Quoted 30 lines
The logic I was imagining we want here was something like the rapidly hacked up (and untested) diff below.
Thanks,
Robin.----->8-----
drivers/iommu/iova.c +1
-0@@ -186,6 +186,7 @@ static int __alloc_and_insert_iova_range(structiova_domain *iovad, unsigned long flags;unsigned long new_pfn;unsigned long align_mask = ~0UL ; +unsigned long alloc_hi, alloc_lo;if (size_aligned)align_mask <<= fls_long(size - 1);drivers/iommu/iova.c +3
-0@@ -196,17 +197,27 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad, size >= iovad->max32_alloc_size) goto iova32_full; + alloc_hi =IOVA_ANCHOR ; + alloc_lo = iovad->start_pfn; +retry: curr =__get_cached_rbnode (iovad, limit_pfn);
drivers/iommu/iova.c static int __alloc_and_insert_iova_range(struct · line 212
Quoted 10 lines
drivers/iommu/iova.c +6
-2curr_iova = rb_entry(curr, struct iova, node); +if (alloc_hi < curr_iova->pfn_hi) { + alloc_lo = curr_iova->pfn_hi; + alloc_hi = limit_pfn; + } + do { - limit_pfn = min(limit_pfn, curr_iova->pfn_lo); - new_pfn = (limit_pfn - size) & align_mask; + alloc_hi = min(alloc_hi, curr_iova->pfn_lo);
During retry case, the curr and curr_iova is not updated. Kindly check it.
Ajay
Quoted 18 lines
drivers/iommu/iova.c +4
-1+ new_pfn = (alloc_hi - size) & align_mask; prev = curr; curr =rb_prev (curr); curr_iova = rb_entry(curr, struct iova, node); }while (curr && new_pfn <= curr_iova->pfn_hi); -if (limit_pfn < size || new_pfn < iovad->start_pfn) { +if (limit_pfn < size || new_pfn < alloc_lo) { +if (alloc_lo == iovad->start_pfn) + goto retry; iovad->max32_alloc_size = size; goto iova32_full;}_______________________________________________
iommu mailing list
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/iommu
Robin Murphy
maintainerQuoted 107 lines · Ajay kumar
Quoted 64 lines · Robin Murphy
Quoted 17 lines · On 2020-05-06 9:01 pm, [email protected] wrote:
From: Vijayanand Jitta <[email protected]>
When ever a new iova alloc request comes iova is always searched from the cached node and the nodes which are previous to cached node. So, even if there is free iova space available in the nodes which are next to the cached node iova allocation can still fail because of this approach.
Consider the following sequence of iova alloc and frees on 1GB of iova space
1) alloc - 500MB
2) alloc - 12MB
3) alloc - 499MB
4) free - 12MB which was allocated in step 2
5) alloc - 13MBQuoted 6 lines
After the above sequence we will have 12MB of free iova space and cached node will be pointing to the iova pfn of last alloc of 13MB which will be the lowest iova pfn of that iova space. Now if we get an alloc request of 2MB we just search from cached node and then look for lower iova pfn's for free iova and as they aren't any, iova alloc fails though there is 12MB of free iova space.
Yup, this could definitely do with improving. Unfortunately I think this particular implementation is slightly flawed...
Quoted 36 lines
To avoid such iova search failures do a retry from the last rb tree node when iova search fails, this will search the entire tree and get an iova if its available
Signed-off-by Vijayanand Jitta <[email protected]>--- drivers/iommu/iova.c | 11 +++++++++++ 1 file changed, 11 insertions(+)drivers/iommu/iova.c +1
-0@@ -186,6 +186,7 @@ static int __alloc_and_insert_iova_range(structiova_domain *iovad, unsigned long flags;unsigned long new_pfn;unsigned long align_mask = ~0UL ; +bool retry = false;if (size_aligned)align_mask <<= fls_long(size - 1);drivers/iommu/iova.c +2
-0@@ -198,6 +199,8 @@ static int __alloc_and_insert_iova_range(structiova_domain *iovad, curr =__get_cached_rbnode (iovad, limit_pfn); curr_iova = rb_entry(curr, struct iova, node); + +retry_search: do { limit_pfn = min(limit_pfn, curr_iova->pfn_lo);new_pfn = (limit_pfn - size) & align_mask;drivers/iommu/iova.c +0
-0@@ -207,6 +210,14 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad, }while (curr && new_pfn <= curr_iova->pfn_hi);Quoted 5 lines
drivers/iommu/iova.c static int __alloc_and_insert_iova_range(struct · line 215
Quoted 3 lines
drivers/iommu/iova.c +2
-0if (limit_pfn < size || new_pfn < iovad->start_pfn) { +if (!retry) { + curr =rb_last (&iovad->rbroot);Why walk when there's an anchor node there already? However...
+1
Quoted 9 lines
drivers/iommu/iova.c static int __alloc_and_insert_iova_range(struct · line 217
Quoted 3 lines
drivers/iommu/iova.c +2
-0+ curr_iova = rb_entry(curr, struct iova, node); + limit_pfn = curr_iova->pfn_lo;...this doesn't look right, as by now we've lost the original
limit_pfnsupplied by the caller, so are highly likely to allocate beyond the range our caller asked for. In fact AFAICS we'd start allocating from directly directly below the anchor node, beyond the end of the entire address space.+1
Quoted 26 lines
The logic I was imagining we want here was something like the rapidly hacked up (and untested) diff below.
Thanks,
Robin.----->8-----
drivers/iommu/iova.c +1
-0@@ -186,6 +186,7 @@ static int __alloc_and_insert_iova_range(structiova_domain *iovad, unsigned long flags;unsigned long new_pfn;unsigned long align_mask = ~0UL ; +unsigned long alloc_hi, alloc_lo;if (size_aligned)align_mask <<= fls_long(size - 1);drivers/iommu/iova.c +0
-0@@ -196,17 +197,27 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad, size >= iovad->max32_alloc_size) goto iova32_full;
Quoted 15 lines
Quoted 4 lines
drivers/iommu/iova.c +3
-0+ alloc_hi =IOVA_ANCHOR ; + alloc_lo = iovad->start_pfn; +retry: curr =__get_cached_rbnode (iovad, limit_pfn);drivers/iommu/iova.c static int __alloc_and_insert_iova_range(struct iova_domain *iovad, · line 211
Quoted 10 lines
drivers/iommu/iova.c +6
-2curr_iova = rb_entry(curr, struct iova, node); +if (alloc_hi < curr_iova->pfn_hi) { + alloc_lo = curr_iova->pfn_hi; + alloc_hi = limit_pfn; + } + do { - limit_pfn = min(limit_pfn, curr_iova->pfn_lo); - new_pfn = (limit_pfn - size) & align_mask; + alloc_hi = min(alloc_hi, curr_iova->pfn_lo);During retry case, the curr and
curr_iovais not updated. Kindly check it.
Right, after we've used the cached node to set the lower limit for the retry pass, we also need to search the tree for the next node above limit_pfn for the actual starting point.
Did I mention this was a completely untested brain-dump? :D
Thanks,
Robin.
Quoted 19 lines
Ajay
Quoted 18 lines
drivers/iommu/iova.c +4
-1+ new_pfn = (alloc_hi - size) & align_mask; prev = curr; curr =rb_prev (curr); curr_iova = rb_entry(curr, struct iova, node); }while (curr && new_pfn <= curr_iova->pfn_hi); -if (limit_pfn < size || new_pfn < iovad->start_pfn) { +if (limit_pfn < size || new_pfn < alloc_lo) { +if (alloc_lo == iovad->start_pfn) + goto retry; iovad->max32_alloc_size = size; goto iova32_full;}_______________________________________________
iommu mailing list
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/iommu
Quoted 76 lines · Robin Murphy
Quoted 17 lines · On 2020-05-06 9:01 pm, [email protected] wrote:
From: Vijayanand Jitta <[email protected]>
When ever a new iova alloc request comes iova is always searched from the cached node and the nodes which are previous to cached node. So, even if there is free iova space available in the nodes which are next to the cached node iova allocation can still fail because of this approach.
Consider the following sequence of iova alloc and frees on 1GB of iova space
1) alloc - 500MB
2) alloc - 12MB
3) alloc - 499MB
4) free - 12MB which was allocated in step 2
5) alloc - 13MBQuoted 6 lines
After the above sequence we will have 12MB of free iova space and cached node will be pointing to the iova pfn of last alloc of 13MB which will be the lowest iova pfn of that iova space. Now if we get an alloc request of 2MB we just search from cached node and then look for lower iova pfn's for free iova and as they aren't any, iova alloc fails though there is 12MB of free iova space.
Yup, this could definitely do with improving. Unfortunately I think this particular implementation is slightly flawed...
Quoted 31 lines
To avoid such iova search failures do a retry from the last rb tree node when iova search fails, this will search the entire tree and get an iova if its available
Signed-off-by Vijayanand Jitta <[email protected]>---
drivers/iommu/iova.c| 11 +++++++++++1 file changed, 11 insertions(+)drivers/iommu/iova.c +3
-0@@ -186,6 +186,7 @@ static int __alloc_and_insert_iova_range(structiova_domain *iovad, unsigned long flags; unsigned long new_pfn; unsigned long align_mask = ~0UL; + bool retry = false; if (size_aligned) align_mask <<= fls_long(size - 1);@@ -198,6 +199,8 @@ static int __alloc_and_insert_iova_range(structiova_domain *iovad, curr = __get_cached_rbnode(iovad, limit_pfn); curr_iova = rb_entry(curr, struct iova, node); + +retry_search: do { limit_pfn = min(limit_pfn, curr_iova->pfn_lo); new_pfn = (limit_pfn - size) & align_mask;drivers/iommu/iova.c static int __alloc_and_insert_iova_range(struct · line 214
Quoted 5 lines
drivers/iommu/iova.c +2
-0@@ -207,6 +210,14 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad, } while (curr && new_pfn <= curr_iova->pfn_hi); if (limit_pfn < size || new_pfn < iovad->start_pfn) { + if (!retry) { + curr = rb_last(&iovad->rbroot);Why walk when there's an anchor node there already? However...
drivers/iommu/iova.c static int __alloc_and_insert_iova_range(struct · line 216
Quoted 2 lines
drivers/iommu/iova.c +2
-0+ curr_iova = rb_entry(curr, struct iova, node); + limit_pfn = curr_iova->pfn_lo;...this doesn't look right, as by now we've lost the original
limit_pfnsupplied by the caller, so are highly likely to allocate beyond the range our caller asked for. In fact AFAICS we'd start allocating from directly directly below the anchor node, beyond the end of the entire address space.
Quoted 6 lines
The logic I was imagining we want here was something like the rapidly hacked up (and untested) diff below.
Thanks,
Robin.
Thanks for your comments ,I have gone through below logic and I see some issue with retry check as there could be case where alloc_lo is set to some pfn other than start_pfn in that case we don't retry and there can still be iova available. I understand its a hacked up version, I can work on this.
But how about we just store limit_pfn and get the node using that and retry for once from that node, it would be similar to my patch just correcting the curr node and limit_pfn update in retry check. do you see any issue with this approach ?
Thanks,
Vijay.
Quoted 46 lines
----->8-----
drivers/iommu/iova.c +1
-0@@ -186,6 +186,7 @@ static int __alloc_and_insert_iova_range(structiova_domain *iovad, unsigned long flags; unsigned long new_pfn; unsigned long align_mask = ~0UL; + unsigned long alloc_hi, alloc_lo; if (size_aligned)
align_mask<<=fls_long(size - 1);drivers/iommu/iova.c +13
-3@@ -196,17 +197,27 @@ static int __alloc_and_insert_iova_range(structiova_domain *iovad, size >= iovad->max32_alloc_size) goto iova32_full; + alloc_hi = IOVA_ANCHOR; + alloc_lo = iovad->start_pfn; +retry: curr = __get_cached_rbnode(iovad, limit_pfn); curr_iova = rb_entry(curr, struct iova, node); + if (alloc_hi < curr_iova->pfn_hi) { + alloc_lo = curr_iova->pfn_hi; + alloc_hi = limit_pfn; + } + do { - limit_pfn = min(limit_pfn, curr_iova->pfn_lo); - new_pfn = (limit_pfn - size) & align_mask; + alloc_hi = min(alloc_hi, curr_iova->pfn_lo); + new_pfn = (alloc_hi - size) & align_mask; prev = curr; curr = rb_prev(curr); curr_iova = rb_entry(curr, struct iova, node); } while (curr && new_pfn <= curr_iova->pfn_hi); - if (limit_pfn < size || new_pfn < iovad->start_pfn) { + if (limit_pfn < size || new_pfn < alloc_lo) { + if (alloc_lo == iovad->start_pfn) + goto retry; iovad->max32_alloc_size = size; goto iova32_full;}
Quoted 92 lines · Vijayanand Jitta
Quoted 76 lines · Robin Murphy
Quoted 17 lines · On 2020-05-06 9:01 pm, [email protected] wrote:
From: Vijayanand Jitta <[email protected]>
When ever a new iova alloc request comes iova is always searched from the cached node and the nodes which are previous to cached node. So, even if there is free iova space available in the nodes which are next to the cached node iova allocation can still fail because of this approach.
Consider the following sequence of iova alloc and frees on 1GB of iova space
1) alloc - 500MB
2) alloc - 12MB
3) alloc - 499MB
4) free - 12MB which was allocated in step 2
5) alloc - 13MBQuoted 6 lines
After the above sequence we will have 12MB of free iova space and cached node will be pointing to the iova pfn of last alloc of 13MB which will be the lowest iova pfn of that iova space. Now if we get an alloc request of 2MB we just search from cached node and then look for lower iova pfn's for free iova and as they aren't any, iova alloc fails though there is 12MB of free iova space.
Yup, this could definitely do with improving. Unfortunately I think this particular implementation is slightly flawed...
Quoted 31 lines
To avoid such iova search failures do a retry from the last rb tree node when iova search fails, this will search the entire tree and get an iova if its available
Signed-off-by Vijayanand Jitta <[email protected]>---
drivers/iommu/iova.c| 11 +++++++++++1 file changed, 11 insertions(+)drivers/iommu/iova.c +3
-0@@ -186,6 +186,7 @@ static int __alloc_and_insert_iova_range(structiova_domain *iovad, unsigned long flags; unsigned long new_pfn; unsigned long align_mask = ~0UL; + bool retry = false; if (size_aligned) align_mask <<= fls_long(size - 1);@@ -198,6 +199,8 @@ static int __alloc_and_insert_iova_range(structiova_domain *iovad, curr = __get_cached_rbnode(iovad, limit_pfn); curr_iova = rb_entry(curr, struct iova, node); + +retry_search: do { limit_pfn = min(limit_pfn, curr_iova->pfn_lo); new_pfn = (limit_pfn - size) & align_mask;drivers/iommu/iova.c static int __alloc_and_insert_iova_range(struct · line 214
Quoted 5 lines
drivers/iommu/iova.c +2
-0@@ -207,6 +210,14 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad, } while (curr && new_pfn <= curr_iova->pfn_hi); if (limit_pfn < size || new_pfn < iovad->start_pfn) { + if (!retry) { + curr = rb_last(&iovad->rbroot);Why walk when there's an anchor node there already? However...
drivers/iommu/iova.c static int __alloc_and_insert_iova_range(struct · line 216
Quoted 2 lines
drivers/iommu/iova.c +2
-0+ curr_iova = rb_entry(curr, struct iova, node); + limit_pfn = curr_iova->pfn_lo;...this doesn't look right, as by now we've lost the original
limit_pfnsupplied by the caller, so are highly likely to allocate beyond the range our caller asked for. In fact AFAICS we'd start allocating from directly directly below the anchor node, beyond the end of the entire address space.Quoted 6 lines
The logic I was imagining we want here was something like the rapidly hacked up (and untested) diff below.
Thanks,
Robin.Thanks for your comments ,I have gone through below logic and I see some issue with retry check as there could be case where
alloc_lois set to some pfn other thanstart_pfnin that case we don't retry and there can still be iova available. I understand its a hacked up version, I can work on this.
Quoted 8 lines
But how about we just store
limit_pfnand get the node using that and retry for once from that node, it would be similar to my patch just correcting the curr node andlimit_pfnupdate in retry check. do you see any issue with this approach ?Thanks,
Vijay.
I found one issue with my earlier approach, where we search twice from cached node to the start_pfn, this can be avoided if we store the pfn_hi of the cached node make this as alloc_lo when we retry. I see the below diff also does the same, I have posted v2 version of the patch after going through the comments and the below diff. can you please review that.
Thanks,
Vijay
Quoted 46 lines
Quoted 46 lines
----->8-----
drivers/iommu/iova.c +1
-0@@ -186,6 +186,7 @@ static int __alloc_and_insert_iova_range(structiova_domain *iovad, unsigned long flags; unsigned long new_pfn; unsigned long align_mask = ~0UL; + unsigned long alloc_hi, alloc_lo; if (size_aligned)
align_mask<<=fls_long(size - 1);drivers/iommu/iova.c +13
-3@@ -196,17 +197,27 @@ static int __alloc_and_insert_iova_range(structiova_domain *iovad, size >= iovad->max32_alloc_size) goto iova32_full; + alloc_hi = IOVA_ANCHOR; + alloc_lo = iovad->start_pfn; +retry: curr = __get_cached_rbnode(iovad, limit_pfn); curr_iova = rb_entry(curr, struct iova, node); + if (alloc_hi < curr_iova->pfn_hi) { + alloc_lo = curr_iova->pfn_hi; + alloc_hi = limit_pfn; + } + do { - limit_pfn = min(limit_pfn, curr_iova->pfn_lo); - new_pfn = (limit_pfn - size) & align_mask; + alloc_hi = min(alloc_hi, curr_iova->pfn_lo); + new_pfn = (alloc_hi - size) & align_mask; prev = curr; curr = rb_prev(curr); curr_iova = rb_entry(curr, struct iova, node); } while (curr && new_pfn <= curr_iova->pfn_hi); - if (limit_pfn < size || new_pfn < iovad->start_pfn) { + if (limit_pfn < size || new_pfn < alloc_lo) { + if (alloc_lo == iovad->start_pfn) + goto retry; iovad->max32_alloc_size = size; goto iova32_full;}