memory-device: refine memory_device_get_free_addr
cover memory-device: refine memory_device_get_free_addr
When we iterate the memory-device list to get the available range, it is not necessary to iterate the whole list.
1) the first non-overlap range is the proper one if no hint is provided
2) no more overlap for hinted range if tmp exceed it
Wei Yang (3):
memory-device: not necessary to use goto for the last check
memory-device: break the loop if no hint is provided
memory-device: break the loop if tmp exceed the hinted range
hw/mem/memory-device.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
Signature · 1 line
2.17.1
PATCH 1/3 memory-device: not necessary to use goto for the last check
We are already at the last condition check.
--- hw/mem/memory-device.c | 1 - 1 file changed, 1 deletion(-)
hw/mem/memory-device.c +0 -1
@@ -186,7 +186,6 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,if (!range_contains_range (&as, &new)) {error_setg (errp,"could not find position in guest address space for " "memory device - memory fragmented due to alignments" ); - goto out; } out:g_slist_free (list);
Signature · 1 line
2.17.1
Re: [Qemu-devel] [PATCH 1/3] memory-device: not necessary to use goto for the last check
Quoted 3 lines · On Sun, 28 Jul 2019 21:13:02 +0800 Wei Yang <[email protected]>…
We are already at the last condition check.
Signed-off-by Wei Yang <[email protected]>
Quoted 16 lines
--- hw/mem/memory-device.c | 1 - 1 file changed, 1 deletion(-)hw/mem/memory-device.c +0
-1@@ -186,7 +186,6 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,if (!range_contains_range (&as, &new)) {error_setg (errp,"could not find position in guest address space for " "memory device - memory fragmented due to alignments" ); - goto out; } out:g_slist_free (list);
Re: [Qemu-devel] [PATCH 1/3] memory-device: not necessary to use goto for the last check
In reply to Wei YangQuoted 13 lines · Wei Yang
We are already at the last condition check.
Signed-off-by Wei Yang <[email protected]>--- hw/mem/memory-device.c | 1 - 1 file changed, 1 deletion(-)hw/mem/memory-device.c +0
-0
hw/mem/memory-device.c static uint64_t memory_device_get_free_addr(MachineState *ms, · line 191
Quoted 7 lines
hw/mem/memory-device.c +0
-1@@ -186,7 +186,6 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,if (!range_contains_range (&as, &new)) {error_setg (errp,"could not find position in guest address space for " "memory device - memory fragmented due to alignments" ); - goto out; } out:g_slist_free (list);
Signature · 3 lines
Thanks, David / dhildenb
PATCH 2/3 memory-device: break the loop if no hint is provided
In reply to Wei YangWhen there is no hint, the first un-overlapped range is the proper one. Just break the loop instead of iterate the whole list.
--- hw/mem/memory-device.c | 2 ++ 1 file changed, 2 insertions(+)
hw/mem/memory-device.c +2 -0
@@ -180,6 +180,8 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,range_make_empty (&new);break ; } + }else if (!hint) { +break ; } }
Signature · 1 line
2.17.1
Re: [Qemu-devel] [PATCH 2/3] memory-device: break the loop if no hint is provided
Quoted 2 lines · On Sun, 28 Jul 2019 21:13:03 +0800 Wei Yang <[email protected]>…
When there is no hint, the first un-overlapped range is the proper one. Just break the loop instead of iterate the whole list.
could it change default pc-dimm mapping (will address assignment stay the same as before this change)?
In commit message I'd suggest to replace 'the proper one' with more verbose explanation why it is safe to break earlier.
otherwise patch look good to me
Quoted 19 lines
Signed-off-by Wei Yang <[email protected]>--- hw/mem/memory-device.c | 2 ++ 1 file changed, 2 insertions(+)hw/mem/memory-device.c +2
-0@@ -180,6 +180,8 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,range_make_empty (&new);break ; } + }else if (!hint) { +break ; } }
Re: [Qemu-devel] [PATCH 2/3] memory-device: break the loop if no hint is provided
Quoted 7 lines · Igor Mammedov
Quoted 2 lines · On Sun, 28 Jul 2019 21:13:03 +0800 Wei Yang <[email protected]>…
When there is no hint, the first un-overlapped range is the proper one. Just break the loop instead of iterate the whole list.
could it change default pc-dimm mapping (will address assignment stay the same as before this change)?
Yes, it stays the same as before.
Quoted 4 lines
In commit message I'd suggest to replace 'the proper one' with more verbose explanation why it is safe to break earlier.
ok, let me re-phrase it. Thanks
Quoted 21 lines
otherwise patch look good to me
Quoted 19 lines
Signed-off-by Wei Yang <[email protected]>--- hw/mem/memory-device.c | 2 ++ 1 file changed, 2 insertions(+)hw/mem/memory-device.c +2
-0@@ -180,6 +180,8 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,range_make_empty (&new);break ; } + }else if (!hint) { +break ; } }
Signature · 2 lines
Wei Yang Help you, Help me
Re: [Qemu-devel] [PATCH 2/3] memory-device: break the loop if no hint is provided
In reply to Wei YangQuoted 14 lines · Wei Yang
When there is no hint, the first un-overlapped range is the proper one. Just break the loop instead of iterate the whole list.
Signed-off-by Wei Yang <[email protected]>--- hw/mem/memory-device.c | 2 ++ 1 file changed, 2 insertions(+)hw/mem/memory-device.c +0
-0
hw/mem/memory-device.c static uint64_t memory_device_get_free_addr(MachineState *ms, · line 187
Quoted 8 lines
hw/mem/memory-device.c +2
-0@@ -180,6 +180,8 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,range_make_empty (&new);break ; } + }else if (!hint) { +break ; } }
I think
a) This is fine. I was not able to construct a counter-example where this would not work. Whenever we modify the range, we check against the next one in the sorted list. If there is no overlap, it fits. And, it won't overlap with any other range (and therefore never be changed again)
b) This should therefore not change the assignment order / break migration.
Maybe mention that this will not change the assigned addresses compared to old code in all scenarios.
Signature · 3 lines
Thanks, David / dhildenb
Re: [Qemu-devel] [PATCH 2/3] memory-device: break the loop if no hint is provided
Quoted 31 lines · David Hildenbrand
Quoted 14 lines · Wei Yang
When there is no hint, the first un-overlapped range is the proper one. Just break the loop instead of iterate the whole list.
Signed-off-by Wei Yang <[email protected]>--- hw/mem/memory-device.c | 2 ++ 1 file changed, 2 insertions(+)hw/mem/memory-device.c +0
-0hw/mem/memory-device.c static uint64_t memory_device_get_free_addr(MachineState *ms, · line 187
Quoted 8 lines
hw/mem/memory-device.c +2
-0@@ -180,6 +180,8 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,range_make_empty (&new);break ; } + }else if (!hint) { +break ; } }I think
a) This is fine. I was not able to construct a counter-example where this would not work. Whenever we modify the range, we check against the next one in the sorted list. If there is no overlap, it fits. And, it won't overlap with any other range (and therefore never be changed again)
Quoted 5 lines
b) This should therefore not change the assignment order / break migration.
Maybe mention that this will not change the assigned addresses compared to old code in all scenarios.
Thanks, let me add this in change log.
Quoted 7 lines
Reviewed-by David Hildenbrand <[email protected]>Signature · 3 lines
Thanks, David / dhildenb
Signature · 2 lines
Wei Yang Help you, Help me
PATCH 3/3 memory-device: break the loop if tmp exceed the hinted range
In reply to Wei YangThe memory-device list built by memory_device_build_list is ordered by its address, this means if the tmp range exceed the hinted range, all the following range will not overlap with it.
--- hw/mem/memory-device.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
hw/mem/memory-device.c +1 -1
@@ -180,7 +180,7 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,range_make_empty (&new);break ; } - }else if (!hint) { + }else if (!hint ||range_lob (&tmp) >range_upb (&new)) {break ; } }
Signature · 1 line
2.17.1
Re: [Qemu-devel] [PATCH 3/3] memory-device: break the loop if tmp exceed the hinted range
Quoted 15 lines · Wei Yang
The memory-device list built by
memory_device_build_listis ordered by its address, this means if the tmp range exceed the hinted range, all the following range will not overlap with it.Signed-off-by Wei Yang <[email protected]>--- hw/mem/memory-device.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)hw/mem/memory-device.c +0
-0
hw/mem/memory-device.c static uint64_t memory_device_get_free_addr(MachineState *ms, · line 186
Quoted 8 lines
hw/mem/memory-device.c +1
-1@@ -180,7 +180,7 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,range_make_empty (&new);break ; } - }else if (!hint) { + }else if (!hint ||range_lob (&tmp) >range_upb (&new)) {break ; } }
Lower bound is inclusive, upper bound is exclusive. Shouldn't this be
range_lob(&tmp) >= range_upb(&new)
Also, I wonder if patch #2 is now really needed?
Signature · 3 lines
Thanks, David / dhildenb
Re: [Qemu-devel] [PATCH 3/3] memory-device: break the loop if tmp exceed the hinted range
Quoted 27 lines · David Hildenbrand
Quoted 15 lines · Wei Yang
The memory-device list built by
memory_device_build_listis ordered by its address, this means if the tmp range exceed the hinted range, all the following range will not overlap with it.Signed-off-by Wei Yang <[email protected]>--- hw/mem/memory-device.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)hw/mem/memory-device.c +0
-0hw/mem/memory-device.c static uint64_t memory_device_get_free_addr(MachineState *ms, · line 186
Quoted 8 lines
hw/mem/memory-device.c +1
-1@@ -180,7 +180,7 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,range_make_empty (&new);break ; } - }else if (!hint) { + }else if (!hint ||range_lob (&tmp) >range_upb (&new)) {break ; } }Lower bound is inclusive, upper bound is exclusive. Shouldn't this be
Quoted 1 line
range_lob(&tmp)>=range_upb(&new)
Confused by the description of range_set_bounds1().
Both bounds are inclusive and this is correct.
Quoted 3 lines
Also, I wonder if patch #2 is now really needed?
Signature · 3 lines
Thanks, David / dhildenb
Re: [Qemu-devel] [PATCH 3/3] memory-device: break the loop if tmp exceed the hinted range
In reply to David HildenbrandQuoted 27 lines · David Hildenbrand
Quoted 15 lines · Wei Yang
The memory-device list built by
memory_device_build_listis ordered by its address, this means if the tmp range exceed the hinted range, all the following range will not overlap with it.Signed-off-by Wei Yang <[email protected]>--- hw/mem/memory-device.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)hw/mem/memory-device.c +0
-0hw/mem/memory-device.c static uint64_t memory_device_get_free_addr(MachineState *ms, · line 186
Quoted 8 lines
hw/mem/memory-device.c +1
-1@@ -180,7 +180,7 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,range_make_empty (&new);break ; } - }else if (!hint) { + }else if (!hint ||range_lob (&tmp) >range_upb (&new)) {break ; } }Lower bound is inclusive, upper bound is exclusive. Shouldn't this be
Quoted 2 lines
range_lob(&tmp)>=range_upb(&new)
Per my understanding, a range with start = 0, size = 0x10000, is represented
[0, 0xffff]
So if I have another range [0xffff, 0x1ffff], they seems to overlap. The range [0x10000, 0x1ffff] doesn't overlap with [0, 0xffff].
My original comparison looks right. Do I miss some point?
Quoted 2 lines
Also, I wonder if patch #2 is now really needed?
Hmm... I think you are right.
I am afraid without Patch #2, the condition check is not that intuitive. Would this bring some confusion for audience and maintenance?
I am not sure the percentage of occurrence when hint is provided, while the generated code for check NULL is less than compare two values.
Quoted 5 lines
Signature · 3 lines
Thanks, David / dhildenb
Signature · 2 lines
Wei Yang Help you, Help me
Re: [Qemu-devel] [PATCH 3/3] memory-device: break the loop if tmp exceed the hinted range
Quoted 31 lines · Wei Yang
Quoted 27 lines · David Hildenbrand
Quoted 15 lines · Wei Yang
The memory-device list built by
memory_device_build_listis ordered by its address, this means if the tmp range exceed the hinted range, all the following range will not overlap with it.Signed-off-by Wei Yang <[email protected]>--- hw/mem/memory-device.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)hw/mem/memory-device.c +0
-0hw/mem/memory-device.c static uint64_t memory_device_get_free_addr(MachineState *ms, · line 186
Quoted 8 lines
hw/mem/memory-device.c +1
-1@@ -180,7 +180,7 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,range_make_empty (&new);break ; } - }else if (!hint) { + }else if (!hint ||range_lob (&tmp) >range_upb (&new)) {break ; } }Lower bound is inclusive, upper bound is exclusive. Shouldn't this be
Quoted 2 lines
range_lob(&tmp)>=range_upb(&new)
Quoted 8 lines
Per my understanding, a range with start = 0, size =
0x10000, is represented[0, 0xffff]So if I have another range [
0xffff,0x1ffff], they seems to overlap. The range [0x10000,0x1ffff] doesn't overlap with [0,0xffff].My original comparison looks right. Do I miss some point?
I guess you saw my other reply by now. :)
Quoted 8 lines
Quoted 3 lines
Also, I wonder if patch #2 is now really needed?
Hmm... I think you are right.
I am afraid without Patch #2, the condition check is not that intuitive. Would this bring some confusion for audience and maintenance?
Less checks, less confusion :)
Quoted 3 lines
I am not sure the percentage of occurrence when hint is provided, while the generated code for check NULL is less than compare two values.
Nobody should care about that performance difference here.
I guess it is fine to just drop patch #2.
Thanks!
Signature · 3 lines
Thanks, David / dhildenb
Re: [Qemu-devel] [PATCH 3/3] memory-device: break the loop if tmp exceed the hinted range
In reply to David HildenbrandQuoted 27 lines · On Mon, 29 Jul 2019 09:49:37 +0200 David Hildenbrand <[email protected]> wrote:
Quoted 15 lines · Wei Yang
The memory-device list built by
memory_device_build_listis ordered by its address, this means if the tmp range exceed the hinted range, all the following range will not overlap with it.Signed-off-by Wei Yang <[email protected]>--- hw/mem/memory-device.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)hw/mem/memory-device.c +0
-0hw/mem/memory-device.c static uint64_t memory_device_get_free_addr(MachineState *ms, · line 186
Quoted 8 lines
hw/mem/memory-device.c +1
-1@@ -180,7 +180,7 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,range_make_empty (&new);break ; } - }else if (!hint) { + }else if (!hint ||range_lob (&tmp) >range_upb (&new)) {break ; } }Lower bound is inclusive, upper bound is exclusive. Shouldn't this be
Quoted 3 lines
range_lob(&tmp)>=range_upb(&new)Also, I wonder if patch #2 is now really needed?
Indeed, it looks like 3/3 will break early in both hinted and non-hinted cases so 2/3 looks not necessary (in case 2/3 is dropped this commit message needs to be amended).
Re: [Qemu-devel] [PATCH 3/3] memory-device: break the loop if tmp exceed the hinted range
Quoted 30 lines · Igor Mammedov
Quoted 27 lines · On Mon, 29 Jul 2019 09:49:37 +0200 David Hildenbrand <[email protected]> wrote:
Quoted 15 lines · Wei Yang
The memory-device list built by
memory_device_build_listis ordered by its address, this means if the tmp range exceed the hinted range, all the following range will not overlap with it.Signed-off-by Wei Yang <[email protected]>--- hw/mem/memory-device.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)hw/mem/memory-device.c +0
-0hw/mem/memory-device.c static uint64_t memory_device_get_free_addr(MachineState *ms, · line 186
Quoted 8 lines
hw/mem/memory-device.c +1
-1@@ -180,7 +180,7 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,range_make_empty (&new);break ; } - }else if (!hint) { + }else if (!hint ||range_lob (&tmp) >range_upb (&new)) {break ; } }Lower bound is inclusive, upper bound is exclusive. Shouldn't this be
Quoted 7 lines
Quoted 3 lines
range_lob(&tmp)>=range_upb(&new)Also, I wonder if patch #2 is now really needed?
Indeed, it looks like 3/3 will break early in both hinted and non-hinted cases so 2/3 looks not necessary (in case 2/3 is dropped this commit message needs to be amended).
ok, let me drop #2
Signature · 2 lines
Wei Yang Help you, Help me