[3/3] memory-device: break the loop if tmp exceed the hinted range
diff mbox series

Message ID 20190728131304.1282-4-richardw.yang@linux.intel.com
State New
Headers show
Series
  • memory-device: refine memory_device_get_free_addr
Related show

Commit Message

Wei Yang July 28, 2019, 1:13 p.m. UTC
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(-)

Comments

David Hildenbrand July 29, 2019, 7:49 a.m. UTC | #1
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?
David Hildenbrand July 29, 2019, 7:53 a.m. UTC | #2
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?
>
Wei Yang July 29, 2019, 8:30 a.m. UTC | #3
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
Igor Mammedov July 29, 2019, 8:30 a.m. UTC | #4
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).
David Hildenbrand July 29, 2019, 8:42 a.m. UTC | #5
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!
Wei Yang July 29, 2019, 12:56 p.m. UTC | #6
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

Patch
diff mbox series

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