Skip to contentSkip to conversation

memory-device: refine memory_device_get_free_addr

PATCH Superseded Wei Yang 4 participants 16 messages Jul 28, 2019 – Jul 29, 2019

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Wei Yang

author
#0 lore raw

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
author
#1 lore raw

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
index 5f2c408036..df3261b32a 100644
@@ -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
Reviewed-by on v1 1/3
#2 lore raw

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.

Quoted 16 lines
---
 hw/mem/memory-device.c | 1 -
 1 file changed, 1 deletion(-)
hw/mem/memory-device.c +0 -1
index 5f2c408036..df3261b32a 100644
@@ -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);
Reviewed-by on v1 1/3
#3 lore raw

Re: [Qemu-devel] [PATCH 1/3] memory-device: not necessary to use goto for the last check

In reply to Wei Yang
Quoted 13 lines · Wei Yang

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 -0
index 5f2c408036..df3261b32a 100644

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
author
#4 lore raw

PATCH 2/3 memory-device: break the loop if no hint is provided

In reply to 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.

---
 hw/mem/memory-device.c | 2 ++
 1 file changed, 2 insertions(+)
hw/mem/memory-device.c +2 -0
index df3261b32a..413b514586 100644
@@ -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
#5 lore raw

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
---
 hw/mem/memory-device.c | 2 ++
 1 file changed, 2 insertions(+)
hw/mem/memory-device.c +2 -0
index df3261b32a..413b514586 100644
@@ -180,6 +180,8 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,
                 range_make_empty(&new);
                 break;
             }
+        } else if (!hint) {
+            break;
         }
     }
 
author
#6 lore raw

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
---
 hw/mem/memory-device.c | 2 ++
 1 file changed, 2 insertions(+)
hw/mem/memory-device.c +2 -0
index df3261b32a..413b514586 100644
@@ -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
Reviewed-by on v1 2/3
#7 lore raw

Re: [Qemu-devel] [PATCH 2/3] memory-device: break the loop if no hint is provided

In reply to Wei Yang
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.

---
 hw/mem/memory-device.c | 2 ++
 1 file changed, 2 insertions(+)
hw/mem/memory-device.c +0 -0
index df3261b32a..413b514586 100644

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
author
#8 lore raw

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.

---
 hw/mem/memory-device.c | 2 ++
 1 file changed, 2 insertions(+)
hw/mem/memory-device.c +0 -0
index df3261b32a..413b514586 100644

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)

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
Signature · 3 lines
Thanks,

David / dhildenb
Signature · 2 lines
Wei Yang
Help you, Help me
author
#9 lore raw

PATCH 3/3 memory-device: break the loop if tmp exceed the hinted range

In reply to Wei Yang

The 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
index 413b514586..aea47ab3e8 100644
@@ -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
#10 lore raw

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_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 +0 -0
index 413b514586..aea47ab3e8 100644

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
#11 lore raw

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_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 +0 -0
index 413b514586..aea47ab3e8 100644

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

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
author
#12 lore raw

Re: [Qemu-devel] [PATCH 3/3] memory-device: break the loop if tmp exceed the hinted range

In reply to David Hildenbrand
Quoted 27 lines · David Hildenbrand
Quoted 15 lines · Wei Yang

The 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 +0 -0
index 413b514586..aea47ab3e8 100644

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

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
#13 lore raw

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_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 +0 -0
index 413b514586..aea47ab3e8 100644

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

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
#14 lore raw

Re: [Qemu-devel] [PATCH 3/3] memory-device: break the loop if tmp exceed the hinted range

In reply to David Hildenbrand
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_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 +0 -0
index 413b514586..aea47ab3e8 100644

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

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).

#15 lore raw

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_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 +0 -0
index 413b514586..aea47ab3e8 100644

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

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