[03/23] memory: merge adjacent segments of a single memory region

Simple implementations of memory routers, for example the Cirrus VGA memory banks
or the 440FX PAM registers can generate adjacent memory regions which are contiguous.
Detect these and merge them; this saves kvm memory slots and shortens lookup times.

Signed-off-by: Avi Kivity <avi@redhat.com>
---
 memory.c |   22 ++++++++++++++++++++++
 1 files changed, 22 insertions(+), 0 deletions(-)

On 07/25/2011 09:02 AM, Avi Kivity wrote:
> Simple implementations of memory routers, for example the Cirrus VGA memory banks
> or the 440FX PAM registers can generate adjacent memory regions which are contiguous.
> Detect these and merge them; this saves kvm memory slots and shortens lookup times.
>
> Signed-off-by: Avi Kivity<avi@redhat.com>
> ---
>   memory.c |   22 ++++++++++++++++++++++
>   1 files changed, 22 insertions(+), 0 deletions(-)
>
> diff --git a/memory.c b/memory.c
> index a569666..339bea3 100644
> --- a/memory.c
> +++ b/memory.c
> @@ -122,6 +122,27 @@ static void flatview_destroy(FlatView *view)
>       qemu_free(view->ranges);
>   }
>
> +/* Attempt to simplify a view by merging ajacent ranges */
> +static void flatview_simplify(FlatView *view)
> +{
> +    unsigned i;
> +    FlatRange *r1, *r2;
> +
> +    for (i = 0; i + 1<  view->nr; ++i) {
> +        r1 =&view->ranges[i];
> +        r2 =&view->ranges[i+1];
> +        if (addrrange_end(r1->addr) == r2->addr.start
> +&&  r1->mr == r2->mr
> +&&  r1->offset_in_region + r1->addr.size == r2->offset_in_region
> +&&  r1->dirty_log_mask == r2->dirty_log_mask) {
> +            r1->addr.size += r2->addr.size;
> +            memmove(r2, r2 + 1, (view->nr - (i + 2)) * sizeof(*r2));
> +            --view->nr;
> +            --i;
> +        }

The --i is pretty subtle.  Moving the index variable backwards in a 
conditional in a for loop is pretty evil :-)  I started writing up why 
this was wrong until I noticed that.

I think the following would be more straight forward:

i = 0;
while (i + 1 < view->nr) {
    int begin = i, end = i + 1;

    while (matches(&view->ranges[begin], &view->ranges[end])) {
       end++;
    }

    memmove(...)
}

Regards,

Anthony Liguori

> +    }
> +}
> +
>   /* Render a memory region into the global view.  Ranges in @view obscure
>    * ranges in @mr.
>    */
> @@ -209,6 +230,7 @@ static FlatView generate_memory_topology(MemoryRegion *mr)
>       flatview_init(&view);
>
>       render_memory_region(&view, mr, 0, addrrange_make(0, UINT64_MAX));
> +    flatview_simplify(&view);
>
>       return view;
>   }

On 07/25/2011 09:48 PM, Anthony Liguori wrote:
>> +/* Attempt to simplify a view by merging ajacent ranges */
>> +static void flatview_simplify(FlatView *view)
>> +{
>> +    unsigned i;
>> +    FlatRange *r1, *r2;
>> +
>> +    for (i = 0; i + 1<  view->nr; ++i) {
>> +        r1 =&view->ranges[i];
>> +        r2 =&view->ranges[i+1];
>> +        if (addrrange_end(r1->addr) == r2->addr.start
>> +&&  r1->mr == r2->mr
>> +&&  r1->offset_in_region + r1->addr.size == r2->offset_in_region
>> +&&  r1->dirty_log_mask == r2->dirty_log_mask) {
>> +            r1->addr.size += r2->addr.size;
>> +            memmove(r2, r2 + 1, (view->nr - (i + 2)) * sizeof(*r2));
>> +            --view->nr;
>> +            --i;
>> +        }
>
>
> The --i is pretty subtle.  Moving the index variable backwards in a 
> conditional in a for loop is pretty evil :-)  I started writing up why 
> this was wrong until I noticed that.
>
> I think the following would be more straight forward:
>
> i = 0;
> while (i + 1 < view->nr) {
>    int begin = i, end = i + 1;
>
>    while (matches(&view->ranges[begin], &view->ranges[end])) {
>       end++;
>    }
>
>    memmove(...)
> }
>

Right; updated to something along these lines.