When different regions have the same address, we currently
sort them by the priority. Also sort them by the region
size.

Signed-off-by: Philippe Mathieu-Daudé <f4bug@amsat.org>
---
 softmmu/memory.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/softmmu/memory.c b/softmmu/memory.c
index af25987518..c28dcaf4d6 100644
--- a/softmmu/memory.c
+++ b/softmmu/memory.c
@@ -2960,7 +2960,8 @@ static void mtree_print_mr(const MemoryRegion *mr, unsigned int level,
         QTAILQ_FOREACH(ml, &submr_print_queue, mrqueue) {
             if (new_ml->mr->addr < ml->mr->addr ||
                 (new_ml->mr->addr == ml->mr->addr &&
-                 new_ml->mr->priority > ml->mr->priority)) {
+                 (MR_SIZE(new_ml->mr->size) > MR_SIZE(ml->mr->size) ||
+                  new_ml->mr->priority > ml->mr->priority))) {
                 QTAILQ_INSERT_BEFORE(ml, new_ml, mrqueue);
                 new_ml = NULL;
                 break;
-- 
2.21.3

On Mon, Jul 27, 2020 at 07:45:43PM +0200, Philippe Mathieu-Daudé wrote:
> When different regions have the same address, we currently
> sort them by the priority. Also sort them by the region
> size.
> 
> Signed-off-by: Philippe Mathieu-Daudé <f4bug@amsat.org>
> ---
>  softmmu/memory.c | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
> 
> diff --git a/softmmu/memory.c b/softmmu/memory.c
> index af25987518..c28dcaf4d6 100644
> --- a/softmmu/memory.c
> +++ b/softmmu/memory.c
> @@ -2960,7 +2960,8 @@ static void mtree_print_mr(const MemoryRegion *mr, unsigned int level,
>          QTAILQ_FOREACH(ml, &submr_print_queue, mrqueue) {
>              if (new_ml->mr->addr < ml->mr->addr ||
>                  (new_ml->mr->addr == ml->mr->addr &&
> -                 new_ml->mr->priority > ml->mr->priority)) {
> +                 (MR_SIZE(new_ml->mr->size) > MR_SIZE(ml->mr->size) ||
> +                  new_ml->mr->priority > ml->mr->priority))) {
>                  QTAILQ_INSERT_BEFORE(ml, new_ml, mrqueue);
>                  new_ml = NULL;
>                  break;

Note that this change could make the outcome unpredictable... Assuming two
memory regions:

  mr1: addr=0, size=0x1000, pri=2
  mr2: addr=0, size=0x2000, pri=1

Then assuming submr_print_queue only contains these two mrs.  Then when
submr_print_queue has mr1 at head, then when we insert mr2 we'll think it
should be inserted before mr1 (because mr2's size bigger), so the result will be:

  mr2:...
  mr1:...

If submr_print_queue has mr2 at head, then when we insert mr1 we'll think it
should be inserted before mr2 (because mr1's priority higher).  We'll instead
get:

  mr1:...
  mr2:...

Phil, could I ask what's the case to be fixed?

-- 
Peter Xu

Hi Peter,

On 7/27/20 8:09 PM, Peter Xu wrote:
> On Mon, Jul 27, 2020 at 07:45:43PM +0200, Philippe Mathieu-Daudé wrote:
>> When different regions have the same address, we currently
>> sort them by the priority. Also sort them by the region
>> size.
>>
>> Signed-off-by: Philippe Mathieu-Daudé <f4bug@amsat.org>
>> ---
>>  softmmu/memory.c | 3 ++-
>>  1 file changed, 2 insertions(+), 1 deletion(-)
>>
>> diff --git a/softmmu/memory.c b/softmmu/memory.c
>> index af25987518..c28dcaf4d6 100644
>> --- a/softmmu/memory.c
>> +++ b/softmmu/memory.c
>> @@ -2960,7 +2960,8 @@ static void mtree_print_mr(const MemoryRegion *mr, unsigned int level,
>>          QTAILQ_FOREACH(ml, &submr_print_queue, mrqueue) {
>>              if (new_ml->mr->addr < ml->mr->addr ||
>>                  (new_ml->mr->addr == ml->mr->addr &&
>> -                 new_ml->mr->priority > ml->mr->priority)) {
>> +                 (MR_SIZE(new_ml->mr->size) > MR_SIZE(ml->mr->size) ||
>> +                  new_ml->mr->priority > ml->mr->priority))) {
>>                  QTAILQ_INSERT_BEFORE(ml, new_ml, mrqueue);
>>                  new_ml = NULL;
>>                  break;
> 
> Note that this change could make the outcome unpredictable... Assuming two
> memory regions:
> 
>   mr1: addr=0, size=0x1000, pri=2
>   mr2: addr=0, size=0x2000, pri=1
> 
> Then assuming submr_print_queue only contains these two mrs.  Then when
> submr_print_queue has mr1 at head, then when we insert mr2 we'll think it
> should be inserted before mr1 (because mr2's size bigger), so the result will be:
> 
>   mr2:...
>   mr1:...
> 
> If submr_print_queue has mr2 at head, then when we insert mr1 we'll think it
> should be inserted before mr2 (because mr1's priority higher).  We'll instead
> get:
> 
>   mr1:...
>   mr2:...
> 
> Phil, could I ask what's the case to be fixed?

What I want is sort regions of same priority by bigger size first,
the smaller size last (as a leaf of the tree, the leaf is the MR
that handles the memory access).

Maybe this patch is not complete. I'll follow Peter Maydell suggestion
to split the compare() function out to make it more readable.
This qtailq is only used for the monitor 'mtree' command, right?
I understand the flatview uses something else.

Regards,

Phil.

On 8/5/20 4:21 PM, Philippe Mathieu-Daudé wrote:
> Hi Peter,
> 
> On 7/27/20 8:09 PM, Peter Xu wrote:
>> On Mon, Jul 27, 2020 at 07:45:43PM +0200, Philippe Mathieu-Daudé wrote:
>>> When different regions have the same address, we currently
>>> sort them by the priority. Also sort them by the region
>>> size.
>>>
>>> Signed-off-by: Philippe Mathieu-Daudé <f4bug@amsat.org>
>>> ---
>>>  softmmu/memory.c | 3 ++-
>>>  1 file changed, 2 insertions(+), 1 deletion(-)
>>>
>>> diff --git a/softmmu/memory.c b/softmmu/memory.c
>>> index af25987518..c28dcaf4d6 100644
>>> --- a/softmmu/memory.c
>>> +++ b/softmmu/memory.c
>>> @@ -2960,7 +2960,8 @@ static void mtree_print_mr(const MemoryRegion *mr, unsigned int level,
>>>          QTAILQ_FOREACH(ml, &submr_print_queue, mrqueue) {
>>>              if (new_ml->mr->addr < ml->mr->addr ||
>>>                  (new_ml->mr->addr == ml->mr->addr &&
>>> -                 new_ml->mr->priority > ml->mr->priority)) {
>>> +                 (MR_SIZE(new_ml->mr->size) > MR_SIZE(ml->mr->size) ||
>>> +                  new_ml->mr->priority > ml->mr->priority))) {
>>>                  QTAILQ_INSERT_BEFORE(ml, new_ml, mrqueue);
>>>                  new_ml = NULL;
>>>                  break;
>>
>> Note that this change could make the outcome unpredictable... Assuming two
>> memory regions:
>>
>>   mr1: addr=0, size=0x1000, pri=2
>>   mr2: addr=0, size=0x2000, pri=1
>>
>> Then assuming submr_print_queue only contains these two mrs.  Then when
>> submr_print_queue has mr1 at head, then when we insert mr2 we'll think it
>> should be inserted before mr1 (because mr2's size bigger), so the result will be:
>>
>>   mr2:...
>>   mr1:...
>>
>> If submr_print_queue has mr2 at head, then when we insert mr1 we'll think it
>> should be inserted before mr2 (because mr1's priority higher).  We'll instead
>> get:
>>
>>   mr1:...
>>   mr2:...
>>
>> Phil, could I ask what's the case to be fixed?
> 
> What I want is sort regions of same priority by bigger size first,
> the smaller size last (as a leaf of the tree, the leaf is the MR
> that handles the memory access).

As example as easier to understand, this is the change I expect:

 memory-region: io
   0000000000000000-000000000000ffff (prio 0, i/o): io
+    0000000000000000-0000000000000007 (prio 0, i/o): dma-chan
       0000000000000000-0000000000000003 (prio 0, i/o): acpi-evt
       0000000000000004-0000000000000005 (prio 0, i/o): acpi-cnt
       0000000000000008-000000000000000b (prio 0, i/o): acpi-tmr
-    0000000000000000-0000000000000007 (prio 0, i/o): dma-chan
     0000000000000008-000000000000000f (prio 0, i/o): dma-cont
     0000000000000020-0000000000000021 (prio 0, i/o): pic
     0000000000000040-0000000000000043 (prio 0, i/o): pit

For me it doesn't seem natural to look after 0x8 if there is another
region mapped at 0x0. Now it is easier to see 'dma-chan' is
masking the acpi events.

Note I'd expect 'acpi-tmr' to be after 'dma-cont' to also realize
it is masked.

FYI the resulting flatview:

(qemu) info mtree -f
FlatView #2
 AS "I/O", root: io
 Root memory region: io
  0000000000000000-0000000000000007 (prio 0, i/o): dma-chan
  0000000000000008-000000000000000f (prio 0, i/o): dma-cont

> 
> Maybe this patch is not complete. I'll follow Peter Maydell suggestion
> to split the compare() function out to make it more readable.
> This qtailq is only used for the monitor 'mtree' command, right?
> I understand the flatview uses something else.
> 
> Regards,
> 
> Phil.
> 

On Mon, 27 Jul 2020 at 18:46, Philippe Mathieu-Daudé <f4bug@amsat.org> wrote:
>
> When different regions have the same address, we currently
> sort them by the priority. Also sort them by the region
> size.
>
> Signed-off-by: Philippe Mathieu-Daudé <f4bug@amsat.org>
> ---
>  softmmu/memory.c | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
>
> diff --git a/softmmu/memory.c b/softmmu/memory.c
> index af25987518..c28dcaf4d6 100644
> --- a/softmmu/memory.c
> +++ b/softmmu/memory.c
> @@ -2960,7 +2960,8 @@ static void mtree_print_mr(const MemoryRegion *mr, unsigned int level,
>          QTAILQ_FOREACH(ml, &submr_print_queue, mrqueue) {
>              if (new_ml->mr->addr < ml->mr->addr ||
>                  (new_ml->mr->addr == ml->mr->addr &&
> -                 new_ml->mr->priority > ml->mr->priority)) {
> +                 (MR_SIZE(new_ml->mr->size) > MR_SIZE(ml->mr->size) ||
> +                  new_ml->mr->priority > ml->mr->priority))) {
>                  QTAILQ_INSERT_BEFORE(ml, new_ml, mrqueue);
>                  new_ml = NULL;
>                  break;

I think this is the point where you want to factor out the
comparison-of-two-MRs function. Which then makes it easier
to implement the required logic, which as Peter Xu says
should be "address compare first; if those are equal look
at the priority; if those are also equal look at the size",
ie the usual comparison-with-multiple-fields.

thanks
-- PMM