Patchwork [v2,04/23] memory: merge adjacent segments of a single memory region

login
register
mail settings
Submitter Avi Kivity
Date July 26, 2011, 11:26 a.m.
Message ID <1311679582-11211-5-git-send-email-avi@redhat.com>
Download mbox | patch
Permalink /patch/106829/
State New
Headers show

Comments

Avi Kivity - July 26, 2011, 11:26 a.m.
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 |   29 +++++++++++++++++++++++++++++
 1 files changed, 29 insertions(+), 0 deletions(-)
Paolo Bonzini - July 26, 2011, 11:36 a.m.
On 07/26/2011 01:26 PM, Avi Kivity wrote:
> +    while (i < view->nr) {
> +        j = i + 1;
> +        while (j < view->nr
> +               && can_merge(&view->ranges[j-1], &view->ranges[j])) {
> +            view->ranges[i].addr.size += view->ranges[j].addr.size;
> +            ++j;
> +        }
> +        ++i;

if (j != i) {

> +        memmove(&view->ranges[i], &view->ranges[j],
> +                (view->nr - j) * sizeof(view->ranges[j]));
> +        view->nr -= j - i;
> +    }

}


Paolo
Avi Kivity - July 26, 2011, 11:38 a.m.
On 07/26/2011 02:36 PM, Paolo Bonzini wrote:
> On 07/26/2011 01:26 PM, Avi Kivity wrote:
>> +    while (i < view->nr) {
>> +        j = i + 1;
>> +        while (j < view->nr
>> + && can_merge(&view->ranges[j-1], &view->ranges[j])) {
>> +            view->ranges[i].addr.size += view->ranges[j].addr.size;
>> +            ++j;
>> +        }
>> +        ++i;
>
> if (j != i) {
>
>> +        memmove(&view->ranges[i], &view->ranges[j],
>> +                (view->nr - j) * sizeof(view->ranges[j]));
>> +        view->nr -= j - i;
>> +    }
>
> }

Seems to work both ways?
Paolo Bonzini - July 26, 2011, 11:51 a.m.
On 07/26/2011 01:38 PM, Avi Kivity wrote:
>>
>> if (j != i) {
>>
>>> +        memmove(&view->ranges[i], &view->ranges[j],
>>> +                (view->nr - j) * sizeof(view->ranges[j]));
>>> +        view->nr -= j - i;
>>> +    }
>>
>> }
>
> Seems to work both ways?

Sure, but you're pointlessly memmove-ing memory over itself.  I'm not 
sure how many segments a single memory region will usually have, but 
it's better to be safe.

Paolo
Avi Kivity - July 26, 2011, 12:04 p.m.
On 07/26/2011 02:51 PM, Paolo Bonzini wrote:
> On 07/26/2011 01:38 PM, Avi Kivity wrote:
>>>
>>> if (j != i) {
>>>
>>>> +        memmove(&view->ranges[i], &view->ranges[j],
>>>> +                (view->nr - j) * sizeof(view->ranges[j]));
>>>> +        view->nr -= j - i;
>>>> +    }
>>>
>>> }
>>
>> Seems to work both ways?
>
> Sure, but you're pointlessly memmove-ing memory over itself.  I'm not 
> sure how many segments a single memory region will usually have, but 
> it's better to be safe.

This will never be an issue in practice.  We expect to have few 
FlatRanges (O(100)), simplify() will be called very rarely (never during 
normal operations; a few dozen times during boot; a few during hotplug); 
everything is in L1 cache; and the cost will be dwarfed by any calls to 
kvm (if enabled).
Richard Henderson - July 26, 2011, 3:41 p.m.
On 07/26/2011 04:36 AM, Paolo Bonzini wrote:
> On 07/26/2011 01:26 PM, Avi Kivity wrote:
>> +    while (i < view->nr) {
>> +        j = i + 1;
>> +        while (j < view->nr
>> +               && can_merge(&view->ranges[j-1], &view->ranges[j])) {
>> +            view->ranges[i].addr.size += view->ranges[j].addr.size;
>> +            ++j;
>> +        }
>> +        ++i;
> 
> if (j != i) {
> 
>> +        memmove(&view->ranges[i], &view->ranges[j],
>> +                (view->nr - j) * sizeof(view->ranges[j]));
>> +        view->nr -= j - i;
>> +    }
> 
> }

Err, j = i + 1, and increments.  Your conditional will always be true.


r~
Avi Kivity - July 26, 2011, 4:04 p.m.
On 07/26/2011 06:41 PM, Richard Henderson wrote:
> On 07/26/2011 04:36 AM, Paolo Bonzini wrote:
> >  On 07/26/2011 01:26 PM, Avi Kivity wrote:
> >>  +    while (i<  view->nr) {
> >>  +        j = i + 1;
> >>  +        while (j<  view->nr
> >>  +&&  can_merge(&view->ranges[j-1],&view->ranges[j])) {
> >>  +            view->ranges[i].addr.size += view->ranges[j].addr.size;
> >>  +            ++j;
> >>  +        }
> >>  +        ++i;
> >
> >  if (j != i) {
> >
> >>  +        memmove(&view->ranges[i],&view->ranges[j],
> >>  +                (view->nr - j) * sizeof(view->ranges[j]));
> >>  +        view->nr -= j - i;
> >>  +    }
> >
> >  }
>
> Err, j = i + 1, and increments.  Your conditional will always be true.
>

If the while loop body is never executed, then i will equal j (both 
incremented once).

Patch

diff --git a/memory.c b/memory.c
index d858b47..121f9e1 100644
--- a/memory.c
+++ b/memory.c
@@ -122,6 +122,34 @@  static void flatview_destroy(FlatView *view)
     qemu_free(view->ranges);
 }
 
+static bool can_merge(FlatRange *r1, FlatRange *r2)
+{
+    return 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;
+}
+
+/* Attempt to simplify a view by merging ajacent ranges */
+static void flatview_simplify(FlatView *view)
+{
+    unsigned i, j;
+
+    i = 0;
+    while (i < view->nr) {
+        j = i + 1;
+        while (j < view->nr
+               && can_merge(&view->ranges[j-1], &view->ranges[j])) {
+            view->ranges[i].addr.size += view->ranges[j].addr.size;
+            ++j;
+        }
+        ++i;
+        memmove(&view->ranges[i], &view->ranges[j],
+                (view->nr - j) * sizeof(view->ranges[j]));
+        view->nr -= j - i;
+    }
+}
+
 /* Render a memory region into the global view.  Ranges in @view obscure
  * ranges in @mr.
  */
@@ -209,6 +237,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;
 }