[Qemu-devel] [PATCH 0/3] memory-device: refine memory_device_get_free_addr

[Qemu-devel] [PATCH 0/3] memory-device: refine memory_device_get_free_addr

[Wei Yang]

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

-- 
2.17.1

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

[Wei Yang]

We are already at the last condition check.

Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
---
 hw/mem/memory-device.c | 1 -
 1 file changed, 1 deletion(-)

diff --git a/hw/mem/memory-device.c b/hw/mem/memory-device.c
index 5f2c408036..df3261b32a 100644
--- a/hw/mem/memory-device.c
+++ b/hw/mem/memory-device.c
@@ -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);
-- 
2.17.1

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

[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 <richardw.yang@linux.intel.com>
---
 hw/mem/memory-device.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/hw/mem/memory-device.c b/hw/mem/memory-device.c
index df3261b32a..413b514586 100644
--- a/hw/mem/memory-device.c
+++ b/hw/mem/memory-device.c
@@ -180,6 +180,8 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,
                 range_make_empty(&new);
                 break;
             }
+        } else if (!hint) {
+            break;
         }
     }
 
-- 
2.17.1

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

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

Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
---
 hw/mem/memory-device.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/hw/mem/memory-device.c b/hw/mem/memory-device.c
index 413b514586..aea47ab3e8 100644
--- a/hw/mem/memory-device.c
+++ b/hw/mem/memory-device.c
@@ -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;
         }
     }
-- 
2.17.1

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

[Igor Mammedov]

On Sun, 28 Jul 2019 21:13:02 +0800
Wei Yang <richardw.yang@linux.intel.com> wrote:

> We are already at the last condition check.
> 
> Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>

Reviewed-by: Igor Mammedov <imammedo@redhat.com>

> ---
>  hw/mem/memory-device.c | 1 -
>  1 file changed, 1 deletion(-)
> 
> diff --git a/hw/mem/memory-device.c b/hw/mem/memory-device.c
> index 5f2c408036..df3261b32a 100644
> --- a/hw/mem/memory-device.c
> +++ b/hw/mem/memory-device.c
> @@ -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 2/3] memory-device: break the loop if no hint is provided

[Igor Mammedov]

On Sun, 28 Jul 2019 21:13:03 +0800
Wei Yang <richardw.yang@linux.intel.com> wrote:

> 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

> 
> Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
> ---
>  hw/mem/memory-device.c | 2 ++
>  1 file changed, 2 insertions(+)
> 
> diff --git a/hw/mem/memory-device.c b/hw/mem/memory-device.c
> index df3261b32a..413b514586 100644
> --- a/hw/mem/memory-device.c
> +++ b/hw/mem/memory-device.c
> @@ -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 1/3] memory-device: not necessary to use goto for the last check

[David Hildenbrand]

On 28.07.19 15:13, Wei Yang wrote:
> We are already at the last condition check.
> 
> Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
> ---
>  hw/mem/memory-device.c | 1 -
>  1 file changed, 1 deletion(-)
> 
> diff --git a/hw/mem/memory-device.c b/hw/mem/memory-device.c
> index 5f2c408036..df3261b32a 100644
> --- a/hw/mem/memory-device.c
> +++ b/hw/mem/memory-device.c
> @@ -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: David Hildenbrand <david@redhat.com>

-- 

Thanks,

David / dhildenb

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

[David Hildenbrand]

On 28.07.19 15:13, Wei Yang wrote:
> 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 <richardw.yang@linux.intel.com>
> ---
>  hw/mem/memory-device.c | 2 ++
>  1 file changed, 2 insertions(+)
> 
> diff --git a/hw/mem/memory-device.c b/hw/mem/memory-device.c
> index df3261b32a..413b514586 100644
> --- a/hw/mem/memory-device.c
> +++ b/hw/mem/memory-device.c
> @@ -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.

Reviewed-by: David Hildenbrand <david@redhat.com>

-- 

Thanks,

David / dhildenb

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

[David Hildenbrand]

On 28.07.19 15:13, Wei Yang wrote:
> 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.
> 
> Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
> ---
>  hw/mem/memory-device.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/hw/mem/memory-device.c b/hw/mem/memory-device.c
> index 413b514586..aea47ab3e8 100644
> --- a/hw/mem/memory-device.c
> +++ b/hw/mem/memory-device.c
> @@ -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?

-- 

Thanks,

David / dhildenb

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

[Wei Yang]

On Mon, Jul 29, 2019 at 09:04:01AM +0200, Igor Mammedov wrote:
>On Sun, 28 Jul 2019 21:13:03 +0800
>Wei Yang <richardw.yang@linux.intel.com> wrote:
>
>> 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.

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

>otherwise patch look good to me
>
>> 
>> Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
>> ---
>>  hw/mem/memory-device.c | 2 ++
>>  1 file changed, 2 insertions(+)
>> 
>> diff --git a/hw/mem/memory-device.c b/hw/mem/memory-device.c
>> index df3261b32a..413b514586 100644
>> --- a/hw/mem/memory-device.c
>> +++ b/hw/mem/memory-device.c
>> @@ -180,6 +180,8 @@ static uint64_t memory_device_get_free_addr(MachineState *ms,
>>                  range_make_empty(&new);
>>                  break;
>>              }
>> +        } else if (!hint) {
>> +            break;
>>          }
>>      }
>>  

-- 
Wei Yang
Help you, Help me

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

[Wei Yang]

On Mon, Jul 29, 2019 at 09:45:24AM +0200, David Hildenbrand wrote:
>On 28.07.19 15:13, Wei Yang wrote:
>> 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 <richardw.yang@linux.intel.com>
>> ---
>>  hw/mem/memory-device.c | 2 ++
>>  1 file changed, 2 insertions(+)
>> 
>> diff --git a/hw/mem/memory-device.c b/hw/mem/memory-device.c
>> index df3261b32a..413b514586 100644
>> --- a/hw/mem/memory-device.c
>> +++ b/hw/mem/memory-device.c
>> @@ -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.
>

Thanks, let me add this in change log.

>Reviewed-by: David Hildenbrand <david@redhat.com>
>
>-- 
>
>Thanks,
>
>David / dhildenb

-- 
Wei Yang
Help you, Help me

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

[David Hildenbrand]

On 29.07.19 09:49, David Hildenbrand wrote:
> On 28.07.19 15:13, Wei Yang wrote:
>> 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.
>>
>> Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
>> ---
>>  hw/mem/memory-device.c | 2 +-
>>  1 file changed, 1 insertion(+), 1 deletion(-)
>>
>> diff --git a/hw/mem/memory-device.c b/hw/mem/memory-device.c
>> index 413b514586..aea47ab3e8 100644
>> --- a/hw/mem/memory-device.c
>> +++ b/hw/mem/memory-device.c
>> @@ -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)

Confused by the description of range_set_bounds1().

Both bounds are inclusive and this is correct.

> 
> Also, I wonder if patch #2 is now really needed?
> 


-- 

Thanks,

David / dhildenb

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

[Wei Yang]

On Mon, Jul 29, 2019 at 09:49:37AM +0200, David Hildenbrand wrote:
>On 28.07.19 15:13, Wei Yang wrote:
>> 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.
>> 
>> Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
>> ---
>>  hw/mem/memory-device.c | 2 +-
>>  1 file changed, 1 insertion(+), 1 deletion(-)
>> 
>> diff --git a/hw/mem/memory-device.c b/hw/mem/memory-device.c
>> index 413b514586..aea47ab3e8 100644
>> --- a/hw/mem/memory-device.c
>> +++ b/hw/mem/memory-device.c
>> @@ -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)
>

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?

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

>-- 
>
>Thanks,
>
>David / dhildenb

-- 
Wei Yang
Help you, Help me

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

[Igor Mammedov]

On Mon, 29 Jul 2019 09:49:37 +0200
David Hildenbrand <david@redhat.com> wrote:

> On 28.07.19 15:13, Wei Yang wrote:
> > 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.
> > 
> > Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
> > ---
> >  hw/mem/memory-device.c | 2 +-
> >  1 file changed, 1 insertion(+), 1 deletion(-)
> > 
> > diff --git a/hw/mem/memory-device.c b/hw/mem/memory-device.c
> > index 413b514586..aea47ab3e8 100644
> > --- a/hw/mem/memory-device.c
> > +++ b/hw/mem/memory-device.c
> > @@ -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?
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

[David Hildenbrand]

On 29.07.19 10:30, Wei Yang wrote:
> On Mon, Jul 29, 2019 at 09:49:37AM +0200, David Hildenbrand wrote:
>> On 28.07.19 15:13, Wei Yang wrote:
>>> 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.
>>>
>>> Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
>>> ---
>>>  hw/mem/memory-device.c | 2 +-
>>>  1 file changed, 1 insertion(+), 1 deletion(-)
>>>
>>> diff --git a/hw/mem/memory-device.c b/hw/mem/memory-device.c
>>> index 413b514586..aea47ab3e8 100644
>>> --- a/hw/mem/memory-device.c
>>> +++ b/hw/mem/memory-device.c
>>> @@ -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)
>>
> 
> 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. :)

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

> 
> 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!


-- 

Thanks,

David / dhildenb

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

[Wei Yang]

On Mon, Jul 29, 2019 at 10:30:56AM +0200, Igor Mammedov wrote:
>On Mon, 29 Jul 2019 09:49:37 +0200
>David Hildenbrand <david@redhat.com> wrote:
>
>> On 28.07.19 15:13, Wei Yang wrote:
>> > 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.
>> > 
>> > Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
>> > ---
>> >  hw/mem/memory-device.c | 2 +-
>> >  1 file changed, 1 insertion(+), 1 deletion(-)
>> > 
>> > diff --git a/hw/mem/memory-device.c b/hw/mem/memory-device.c
>> > index 413b514586..aea47ab3e8 100644
>> > --- a/hw/mem/memory-device.c
>> > +++ b/hw/mem/memory-device.c
>> > @@ -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?
>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

-- 
Wei Yang
Help you, Help me