[Qemu-devel] [PATCH 0/2] find_ram_offset cleanups and alignment

[Qemu-devel] [PATCH 0/2] find_ram_offset cleanups and alignment

[Dr. David Alan Gilbert (git)]

From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>

Hi,
  This is mainly the alignment change that Paolo asked for
in the 2nd commit, but while I was there I added some comments
and tracing that I've split out.

Dave

Dr. David Alan Gilbert (2):
  find_ram_offset: Add comments and tracing
  find_ram_offset: Align ram_addr_t allocation on long boundaries

 exec.c       | 22 +++++++++++++++++++++-
 trace-events |  3 +++
 2 files changed, 24 insertions(+), 1 deletion(-)

-- 
2.14.3

[Qemu-devel] [PATCH 1/2] find_ram_offset: Add comments and tracing

[Dr. David Alan Gilbert (git)]

From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>

Add some comments so I can understand the various nested loops.
Add some tracing so I can see what they're doing.

Signed-off-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
---
 exec.c       | 17 ++++++++++++++++-
 trace-events |  3 +++
 2 files changed, 19 insertions(+), 1 deletion(-)

diff --git a/exec.c b/exec.c
index 5973c666c8..7966570231 100644
--- a/exec.c
+++ b/exec.c
@@ -1665,7 +1665,10 @@ static void *file_ram_alloc(RAMBlock *block,
 }
 #endif
 
-/* Called with the ramlist lock held.  */
+/* Allocate space within the ram_addr_t space that governs the
+ * dirty bitmaps.
+ * Called with the ramlist lock held.
+ */
 static ram_addr_t find_ram_offset(ram_addr_t size)
 {
     RAMBlock *block, *next_block;
@@ -1682,15 +1685,25 @@ static ram_addr_t find_ram_offset(ram_addr_t size)
 
         end = block->offset + block->max_length;
 
+        /* Search for the closest following block
+         * and find the gap.
+         */
         RAMBLOCK_FOREACH(next_block) {
             if (next_block->offset >= end) {
                 next = MIN(next, next_block->offset);
             }
         }
+
+        /* If it fits remember our place and remember the size
+         * of gap, but keep going so that we might find a smaller
+         * gap to fill so avoiding fragmentation.
+         */
         if (next - end >= size && next - end < mingap) {
             offset = end;
             mingap = next - end;
         }
+
+        trace_find_ram_offset_loop(size, offset, end, next, mingap);
     }
 
     if (offset == RAM_ADDR_MAX) {
@@ -1699,6 +1712,8 @@ static ram_addr_t find_ram_offset(ram_addr_t size)
         abort();
     }
 
+    trace_find_ram_offset(size, offset);
+
     return offset;
 }
 
diff --git a/trace-events b/trace-events
index a8861bd800..23bc036aa1 100644
--- a/trace-events
+++ b/trace-events
@@ -56,6 +56,9 @@ dma_blk_cb(void *dbs, int ret) "dbs=%p ret=%d"
 dma_map_wait(void *dbs) "dbs=%p"
 
 # exec.c
+find_ram_offset(uint64_t size, uint64_t offset) "size: 0x%"PRIx64 " @ 0x%"PRIx64
+find_ram_offset_loop(uint64_t size, uint64_t offset, uint64_t end, uint64_t next, uint64_t mingap) "size: 0x%"PRIx64 " @ 0x%"PRIx64 " end: 0x%"PRIx64" next: 0x%"PRIx64 " mingap: 0x%"PRIx64
+
 ram_block_discard_range(const char *rbname, void *hva, bool need_madvise, bool need_fallocate, int ret) "%s@%p: madvise: %d fallocate: %d ret: %d"
 
 # memory.c
-- 
2.14.3

[Qemu-devel] [PATCH 2/2] find_ram_offset: Align ram_addr_t allocation on long boundaries

[Dr. David Alan Gilbert (git)]

From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>

The dirty bitmaps are built from 'long'sand there is fast-path code
for synchronising the case where the RAMBlock is aligned to the start
of a long boundary.  Align the allocation to this boundary
to cause the fast path to be used.

Offsets before change:
11398@1515169675.018566:find_ram_offset size: 0x1e0000 @ 0x8000000
11398@1515169675.020064:find_ram_offset size: 0x20000 @ 0x81e0000
11398@1515169675.020244:find_ram_offset size: 0x20000 @ 0x8200000
11398@1515169675.024343:find_ram_offset size: 0x1000000 @ 0x8220000
11398@1515169675.025154:find_ram_offset size: 0x10000 @ 0x9220000
11398@1515169675.027682:find_ram_offset size: 0x40000 @ 0x9230000
11398@1515169675.032921:find_ram_offset size: 0x200000 @ 0x9270000
11398@1515169675.033307:find_ram_offset size: 0x1000 @ 0x9470000
11398@1515169675.033601:find_ram_offset size: 0x1000 @ 0x9471000

after change:
10923@1515169108.818245:find_ram_offset size: 0x1e0000 @ 0x8000000
10923@1515169108.819410:find_ram_offset size: 0x20000 @ 0x8200000
10923@1515169108.819587:find_ram_offset size: 0x20000 @ 0x8240000
10923@1515169108.823708:find_ram_offset size: 0x1000000 @ 0x8280000
10923@1515169108.824503:find_ram_offset size: 0x10000 @ 0x9280000
10923@1515169108.827093:find_ram_offset size: 0x40000 @ 0x92c0000
10923@1515169108.833045:find_ram_offset size: 0x200000 @ 0x9300000
10923@1515169108.833504:find_ram_offset size: 0x1000 @ 0x9500000
10923@1515169108.833787:find_ram_offset size: 0x1000 @ 0x9540000

Suggested-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
---
 exec.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/exec.c b/exec.c
index 7966570231..644603f05e 100644
--- a/exec.c
+++ b/exec.c
@@ -1694,6 +1694,11 @@ static ram_addr_t find_ram_offset(ram_addr_t size)
             }
         }
 
+        /* Align blocks to start on a 'long' in the bitmap
+         * which makes the bitmap sync'ing take the fast path.
+         */
+        end = ROUND_UP(end, BITS_PER_LONG << TARGET_PAGE_BITS);
+
         /* If it fits remember our place and remember the size
          * of gap, but keep going so that we might find a smaller
          * gap to fill so avoiding fragmentation.
-- 
2.14.3

Re: [Qemu-devel] [PATCH 2/2] find_ram_offset: Align ram_addr_t allocation on long boundaries

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1399 bytes --]

On 01/05/2018 11:01 AM, Dr. David Alan Gilbert (git) wrote:
> From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> 
> The dirty bitmaps are built from 'long'sand there is fast-path code

s/'long'sand/'long's, and/

> for synchronising the case where the RAMBlock is aligned to the start
> of a long boundary.  Align the allocation to this boundary
> to cause the fast path to be used.
> 

> Suggested-by: Paolo Bonzini <pbonzini@redhat.com>
> Signed-off-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
> ---
>  exec.c | 5 +++++
>  1 file changed, 5 insertions(+)

Reviewed-by: Eric Blake <eblake@redhat.com>

> 
> diff --git a/exec.c b/exec.c
> index 7966570231..644603f05e 100644
> --- a/exec.c
> +++ b/exec.c
> @@ -1694,6 +1694,11 @@ static ram_addr_t find_ram_offset(ram_addr_t size)
>              }
>          }
>  
> +        /* Align blocks to start on a 'long' in the bitmap
> +         * which makes the bitmap sync'ing take the fast path.
> +         */
> +        end = ROUND_UP(end, BITS_PER_LONG << TARGET_PAGE_BITS);
> +
>          /* If it fits remember our place and remember the size
>           * of gap, but keep going so that we might find a smaller
>           * gap to fill so avoiding fragmentation.
> 

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 619 bytes --]

Re: [Qemu-devel] [PATCH 1/2] find_ram_offset: Add comments and tracing

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 851 bytes --]

On 01/05/2018 11:01 AM, Dr. David Alan Gilbert (git) wrote:
> From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> 
> Add some comments so I can understand the various nested loops.
> Add some tracing so I can see what they're doing.
> 
> Signed-off-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
> ---
>  exec.c       | 17 ++++++++++++++++-
>  trace-events |  3 +++
>  2 files changed, 19 insertions(+), 1 deletion(-)
> 

> +
> +        /* If it fits remember our place and remember the size
> +         * of gap, but keep going so that we might find a smaller
> +         * gap to fill so avoiding fragmentation.

s/so avoiding/in order to avoid/

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 619 bytes --]

Re: [Qemu-devel] [PATCH 1/2] find_ram_offset: Add comments and tracing

[Juan Quintela]

"Dr. David Alan Gilbert (git)" <dgilbert@redhat.com> wrote:
> From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
>
> Add some comments so I can understand the various nested loops.
> Add some tracing so I can see what they're doing.
>
> Signed-off-by: Dr. David Alan Gilbert <dgilbert@redhat.com>


Reviewed-by: Juan Quintela <quintela@redhat.com>

Re: [Qemu-devel] [PATCH 2/2] find_ram_offset: Align ram_addr_t allocation on long boundaries

[Juan Quintela]

"Dr. David Alan Gilbert (git)" <dgilbert@redhat.com> wrote:
> From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
>
> The dirty bitmaps are built from 'long'sand there is fast-path code
> for synchronising the case where the RAMBlock is aligned to the start
> of a long boundary.  Align the allocation to this boundary
> to cause the fast path to be used.
>
> Offsets before change:
> 11398@1515169675.018566:find_ram_offset size: 0x1e0000 @ 0x8000000
> 11398@1515169675.020064:find_ram_offset size: 0x20000 @ 0x81e0000
> 11398@1515169675.020244:find_ram_offset size: 0x20000 @ 0x8200000
> 11398@1515169675.024343:find_ram_offset size: 0x1000000 @ 0x8220000
> 11398@1515169675.025154:find_ram_offset size: 0x10000 @ 0x9220000
> 11398@1515169675.027682:find_ram_offset size: 0x40000 @ 0x9230000
> 11398@1515169675.032921:find_ram_offset size: 0x200000 @ 0x9270000
> 11398@1515169675.033307:find_ram_offset size: 0x1000 @ 0x9470000
> 11398@1515169675.033601:find_ram_offset size: 0x1000 @ 0x9471000
>
> after change:
> 10923@1515169108.818245:find_ram_offset size: 0x1e0000 @ 0x8000000
> 10923@1515169108.819410:find_ram_offset size: 0x20000 @ 0x8200000
> 10923@1515169108.819587:find_ram_offset size: 0x20000 @ 0x8240000
> 10923@1515169108.823708:find_ram_offset size: 0x1000000 @ 0x8280000
> 10923@1515169108.824503:find_ram_offset size: 0x10000 @ 0x9280000
> 10923@1515169108.827093:find_ram_offset size: 0x40000 @ 0x92c0000
> 10923@1515169108.833045:find_ram_offset size: 0x200000 @ 0x9300000
> 10923@1515169108.833504:find_ram_offset size: 0x1000 @ 0x9500000
> 10923@1515169108.833787:find_ram_offset size: 0x1000 @ 0x9540000
>
> Suggested-by: Paolo Bonzini <pbonzini@redhat.com>
> Signed-off-by: Dr. David Alan Gilbert <dgilbert@redhat.com>

Reviewed-by: Juan Quintela <quintela@redhat.com>

Re: [Qemu-devel] [PATCH 2/2] find_ram_offset: Align ram_addr_t allocation on long boundaries

[Paolo Bonzini]

On 05/01/2018 18:01, Dr. David Alan Gilbert (git) wrote:
> From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> 
> The dirty bitmaps are built from 'long'sand there is fast-path code
> for synchronising the case where the RAMBlock is aligned to the start
> of a long boundary.  Align the allocation to this boundary
> to cause the fast path to be used.
> 
> Offsets before change:
> 11398@1515169675.018566:find_ram_offset size: 0x1e0000 @ 0x8000000
> 11398@1515169675.020064:find_ram_offset size: 0x20000 @ 0x81e0000
> 11398@1515169675.020244:find_ram_offset size: 0x20000 @ 0x8200000
> 11398@1515169675.024343:find_ram_offset size: 0x1000000 @ 0x8220000
> 11398@1515169675.025154:find_ram_offset size: 0x10000 @ 0x9220000
> 11398@1515169675.027682:find_ram_offset size: 0x40000 @ 0x9230000
> 11398@1515169675.032921:find_ram_offset size: 0x200000 @ 0x9270000
> 11398@1515169675.033307:find_ram_offset size: 0x1000 @ 0x9470000
> 11398@1515169675.033601:find_ram_offset size: 0x1000 @ 0x9471000
> 
> after change:
> 10923@1515169108.818245:find_ram_offset size: 0x1e0000 @ 0x8000000
> 10923@1515169108.819410:find_ram_offset size: 0x20000 @ 0x8200000
> 10923@1515169108.819587:find_ram_offset size: 0x20000 @ 0x8240000
> 10923@1515169108.823708:find_ram_offset size: 0x1000000 @ 0x8280000
> 10923@1515169108.824503:find_ram_offset size: 0x10000 @ 0x9280000
> 10923@1515169108.827093:find_ram_offset size: 0x40000 @ 0x92c0000
> 10923@1515169108.833045:find_ram_offset size: 0x200000 @ 0x9300000
> 10923@1515169108.833504:find_ram_offset size: 0x1000 @ 0x9500000
> 10923@1515169108.833787:find_ram_offset size: 0x1000 @ 0x9540000
> 
> Suggested-by: Paolo Bonzini <pbonzini@redhat.com>
> Signed-off-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
> ---
>  exec.c | 5 +++++
>  1 file changed, 5 insertions(+)
> 
> diff --git a/exec.c b/exec.c
> index 7966570231..644603f05e 100644
> --- a/exec.c
> +++ b/exec.c
> @@ -1694,6 +1694,11 @@ static ram_addr_t find_ram_offset(ram_addr_t size)
>              }
>          }
>  
> +        /* Align blocks to start on a 'long' in the bitmap
> +         * which makes the bitmap sync'ing take the fast path.
> +         */
> +        end = ROUND_UP(end, BITS_PER_LONG << TARGET_PAGE_BITS);

I think this should be done before the nested loop.  Otherwise, "next -
end" can become negative, which is always going to be >= size.  It's
also very large, so it's likely to fail the mingap test, but it's buggy
nevertheless.

In fact "end" could be renamed to "candidate" which explains more
clearly what's going on.  I'll post a v2 shortly...

Thanks,

Paolo


>          /* If it fits remember our place and remember the size
>           * of gap, but keep going so that we might find a smaller
>           * gap to fill so avoiding fragmentation.
>