[Qemu-devel] [RFC 0/6] memory: make dirty_memory[] accesses atomic

[Qemu-devel] [RFC 0/6] memory: make dirty_memory[] accesses atomic

[Stefan Hajnoczi]

The dirty_memory[] bitmap is used for live migration, TCG self-modifying code
detection, and VGA emulation.  Up until now the bitmap was always accessed
under the QEMU global mutex.  This series makes all dirty_memory[] accesses
atomic to prepare the way for threads writing to guest memory without holding
the global mutex.

In particular, this series converts non-atomic dirty_memory[] accesses to
atomic_or, atomic_xchg, and atomic_fetch_and so that race conditions are
avoided when two threads manipulate the bitmap at the same time.

There are two pieces remaining before the dirty_memory[] bitmap is truly
thread-safe:

1. Convert all cpu_physical_memory_*_dirty() callers to use the API atomically.
   There are TCG callers who things along the lines of:

     if (!cpu_physical_memory_get_dirty(addr)) {
         cpu_physical_memory_set_dirty(addr);  /* not atomic! */
     }

   At first I considered ignoring TCG completely since it is currently not
   multi-threaded, but we might as well tackle this so that
   virtio-blk/virtio-scsi dataplane can be used with TCG eventually (they still
   need ioeventfd/irqfd emulation before they can support TCG).

2. Use array RCU to safely resize dirty_memory[] for memory hotplug.  Currently
   ram_block_add() grows the bitmap in a way that is not thread-safe.

   Paolo has a QEMU userspace RCU implementation which I'd like to bring in for
   this.

I am posting this RFC to get feedback because this is my first foray into the
memory bitmap code.  Comments appreciated!

Stefan Hajnoczi (6):
  bitmap: add atomic set functions
  bitmap: add atomic test and clear
  memory: use atomic ops for setting dirty memory bits
  migration: move dirty bitmap sync to ram_addr.h
  memory: replace cpu_physical_memory_reset_dirty() with test-and-clear
  memory: make cpu_physical_memory_sync_dirty_bitmap() fully atomic

 arch_init.c             | 46 ++----------------------------
 cputlb.c                |  4 +--
 exec.c                  | 23 +++++++++++----
 include/exec/ram_addr.h | 74 ++++++++++++++++++++++++++++++++++++-------------
 include/qemu/bitmap.h   |  4 +++
 include/qemu/bitops.h   | 14 ++++++++++
 memory.c                | 11 +++-----
 util/bitmap.c           | 47 +++++++++++++++++++++++++++++++
 8 files changed, 144 insertions(+), 79 deletions(-)

-- 
2.1.0

[Qemu-devel] [RFC 1/6] bitmap: add atomic set functions

[Stefan Hajnoczi]

Use atomic_or() for atomic bitmaps where several threads may set bits at
the same time.

This avoids the race condition between threads loading an element,
bitwise ORing, and then storing the element.

Most bitmap users don't need atomicity so introduce new functions.

Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
---
 include/qemu/bitmap.h |  2 ++
 include/qemu/bitops.h | 14 ++++++++++++++
 util/bitmap.c         | 21 +++++++++++++++++++++
 3 files changed, 37 insertions(+)

diff --git a/include/qemu/bitmap.h b/include/qemu/bitmap.h
index f0273c9..3e0a4f3 100644
--- a/include/qemu/bitmap.h
+++ b/include/qemu/bitmap.h
@@ -39,6 +39,7 @@
  * bitmap_empty(src, nbits)			Are all bits zero in *src?
  * bitmap_full(src, nbits)			Are all bits set in *src?
  * bitmap_set(dst, pos, nbits)			Set specified bit area
+ * bitmap_set_atomic(dst, pos, nbits)   Set specified bit area with atomic ops
  * bitmap_clear(dst, pos, nbits)		Clear specified bit area
  * bitmap_find_next_zero_area(buf, len, pos, n, mask)	Find bit free area
  */
@@ -226,6 +227,7 @@ static inline int bitmap_intersects(const unsigned long *src1,
 }
 
 void bitmap_set(unsigned long *map, long i, long len);
+void bitmap_set_atomic(unsigned long *map, long i, long len);
 void bitmap_clear(unsigned long *map, long start, long nr);
 unsigned long bitmap_find_next_zero_area(unsigned long *map,
                                          unsigned long size,
diff --git a/include/qemu/bitops.h b/include/qemu/bitops.h
index 181bd46..eda4132 100644
--- a/include/qemu/bitops.h
+++ b/include/qemu/bitops.h
@@ -16,6 +16,7 @@
 #include <assert.h>
 
 #include "host-utils.h"
+#include "atomic.h"
 
 #define BITS_PER_BYTE           CHAR_BIT
 #define BITS_PER_LONG           (sizeof (unsigned long) * BITS_PER_BYTE)
@@ -39,6 +40,19 @@ static inline void set_bit(long nr, unsigned long *addr)
 }
 
 /**
+ * set_bit_atomic - Set a bit in memory atomically
+ * @nr: the bit to set
+ * @addr: the address to start counting from
+ */
+static inline void set_bit_atomic(long nr, unsigned long *addr)
+{
+    unsigned long mask = BIT_MASK(nr);
+    unsigned long *p = addr + BIT_WORD(nr);
+
+    atomic_or(p, mask);
+}
+
+/**
  * clear_bit - Clears a bit in memory
  * @nr: Bit to clear
  * @addr: Address to start counting from
diff --git a/util/bitmap.c b/util/bitmap.c
index 9c6bb52..758749c 100644
--- a/util/bitmap.c
+++ b/util/bitmap.c
@@ -11,6 +11,7 @@
 
 #include "qemu/bitops.h"
 #include "qemu/bitmap.h"
+#include "qemu/atomic.h"
 
 /*
  * bitmaps provide an array of bits, implemented using an an
@@ -177,6 +178,26 @@ void bitmap_set(unsigned long *map, long start, long nr)
     }
 }
 
+void bitmap_set_atomic(unsigned long *map, long start, long nr)
+{
+    unsigned long *p = map + BIT_WORD(start);
+    const long size = start + nr;
+    int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
+    unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
+
+    while (nr - bits_to_set >= 0) {
+        atomic_or(p, mask_to_set);
+        nr -= bits_to_set;
+        bits_to_set = BITS_PER_LONG;
+        mask_to_set = ~0UL;
+        p++;
+    }
+    if (nr) {
+        mask_to_set &= BITMAP_LAST_WORD_MASK(size);
+        atomic_or(p, mask_to_set);
+    }
+}
+
 void bitmap_clear(unsigned long *map, long start, long nr)
 {
     unsigned long *p = map + BIT_WORD(start);
-- 
2.1.0

Re: [Qemu-devel] [RFC 1/6] bitmap: add atomic set functions

[Paolo Bonzini]

On 27/11/2014 13:29, Stefan Hajnoczi wrote:
> +void bitmap_set_atomic(unsigned long *map, long start, long nr)
> +{
> +    unsigned long *p = map + BIT_WORD(start);
> +    const long size = start + nr;
> +    int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
> +    unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
> +
> +    while (nr - bits_to_set >= 0) {
> +        atomic_or(p, mask_to_set);

atomic_or is unnecessary while mask_to_set is ~0UL.  I think not even a
smp_wmb() is necessary.

Paolo

> +        nr -= bits_to_set;
> +        bits_to_set = BITS_PER_LONG;
> +        mask_to_set = ~0UL;
> +        p++;
> +    }
> +    if (nr) {
> +        mask_to_set &= BITMAP_LAST_WORD_MASK(size);
> +        atomic_or(p, mask_to_set);
> +    }
> +}
> +

Re: [Qemu-devel] [RFC 1/6] bitmap: add atomic set functions

[Stefan Hajnoczi]

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

On Thu, Nov 27, 2014 at 05:42:41PM +0100, Paolo Bonzini wrote:
> 
> 
> On 27/11/2014 13:29, Stefan Hajnoczi wrote:
> > +void bitmap_set_atomic(unsigned long *map, long start, long nr)
> > +{
> > +    unsigned long *p = map + BIT_WORD(start);
> > +    const long size = start + nr;
> > +    int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
> > +    unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
> > +
> > +    while (nr - bits_to_set >= 0) {
> > +        atomic_or(p, mask_to_set);
> 
> atomic_or is unnecessary while mask_to_set is ~0UL.  I think not even a
> smp_wmb() is necessary.

Okay, I can split this into the ~0UL case and the atomic case.

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]

[Qemu-devel] [RFC 2/6] bitmap: add atomic test and clear

[Stefan Hajnoczi]

The new bitmap_test_and_clear_atomic() function clears a range and
returns whether or not the bits were set.

Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
---
 include/qemu/bitmap.h |  2 ++
 util/bitmap.c         | 26 ++++++++++++++++++++++++++
 2 files changed, 28 insertions(+)

diff --git a/include/qemu/bitmap.h b/include/qemu/bitmap.h
index 3e0a4f3..86dd9cd 100644
--- a/include/qemu/bitmap.h
+++ b/include/qemu/bitmap.h
@@ -41,6 +41,7 @@
  * bitmap_set(dst, pos, nbits)			Set specified bit area
  * bitmap_set_atomic(dst, pos, nbits)   Set specified bit area with atomic ops
  * bitmap_clear(dst, pos, nbits)		Clear specified bit area
+ * bitmap_test_and_clear_atomic(dst, pos, nbits)    Test and clear area
  * bitmap_find_next_zero_area(buf, len, pos, n, mask)	Find bit free area
  */
 
@@ -229,6 +230,7 @@ static inline int bitmap_intersects(const unsigned long *src1,
 void bitmap_set(unsigned long *map, long i, long len);
 void bitmap_set_atomic(unsigned long *map, long i, long len);
 void bitmap_clear(unsigned long *map, long start, long nr);
+bool bitmap_test_and_clear_atomic(unsigned long *map, long start, long nr);
 unsigned long bitmap_find_next_zero_area(unsigned long *map,
                                          unsigned long size,
                                          unsigned long start,
diff --git a/util/bitmap.c b/util/bitmap.c
index 758749c..3125674 100644
--- a/util/bitmap.c
+++ b/util/bitmap.c
@@ -218,6 +218,32 @@ void bitmap_clear(unsigned long *map, long start, long nr)
     }
 }
 
+bool bitmap_test_and_clear_atomic(unsigned long *map, long start, long nr)
+{
+    unsigned long *p = map + BIT_WORD(start);
+    const long size = start + nr;
+    int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
+    unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
+    unsigned long dirty = 0;
+    unsigned long old_bits;
+
+    while (nr - bits_to_clear >= 0) {
+        old_bits = atomic_fetch_and(p, ~mask_to_clear);
+        dirty |= old_bits & mask_to_clear;
+        nr -= bits_to_clear;
+        bits_to_clear = BITS_PER_LONG;
+        mask_to_clear = ~0UL;
+        p++;
+    }
+    if (nr) {
+        mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
+        old_bits = atomic_fetch_and(p, ~mask_to_clear);
+        dirty |= old_bits & mask_to_clear;
+    }
+
+    return dirty;
+}
+
 #define ALIGN_MASK(x,mask)      (((x)+(mask))&~(mask))
 
 /**
-- 
2.1.0

Re: [Qemu-devel] [RFC 2/6] bitmap: add atomic test and clear

[Paolo Bonzini]

On 27/11/2014 13:29, Stefan Hajnoczi wrote:
> +bool bitmap_test_and_clear_atomic(unsigned long *map, long start, long nr)
> +{
> +    unsigned long *p = map + BIT_WORD(start);
> +    const long size = start + nr;
> +    int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
> +    unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
> +    unsigned long dirty = 0;
> +    unsigned long old_bits;
> +
> +    while (nr - bits_to_clear >= 0) {
> +        old_bits = atomic_fetch_and(p, ~mask_to_clear);
> +        dirty |= old_bits & mask_to_clear;
> +        nr -= bits_to_clear;
> +        bits_to_clear = BITS_PER_LONG;
> +        mask_to_clear = ~0UL;
> +        p++;
> +    }
> +    if (nr) {
> +        mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
> +        old_bits = atomic_fetch_and(p, ~mask_to_clear);
> +        dirty |= old_bits & mask_to_clear;
> +    }
> +
> +    return dirty;
> +}

Same here; you can use atomic_xchg, which is faster because on x86
atomic_fetch_and must do a compare-and-swap loop.

Paolo

Re: [Qemu-devel] [RFC 2/6] bitmap: add atomic test and clear

[Stefan Hajnoczi]

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

On Thu, Nov 27, 2014 at 05:43:56PM +0100, Paolo Bonzini wrote:
> 
> 
> On 27/11/2014 13:29, Stefan Hajnoczi wrote:
> > +bool bitmap_test_and_clear_atomic(unsigned long *map, long start, long nr)
> > +{
> > +    unsigned long *p = map + BIT_WORD(start);
> > +    const long size = start + nr;
> > +    int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
> > +    unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
> > +    unsigned long dirty = 0;
> > +    unsigned long old_bits;
> > +
> > +    while (nr - bits_to_clear >= 0) {
> > +        old_bits = atomic_fetch_and(p, ~mask_to_clear);
> > +        dirty |= old_bits & mask_to_clear;
> > +        nr -= bits_to_clear;
> > +        bits_to_clear = BITS_PER_LONG;
> > +        mask_to_clear = ~0UL;
> > +        p++;
> > +    }
> > +    if (nr) {
> > +        mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
> > +        old_bits = atomic_fetch_and(p, ~mask_to_clear);
> > +        dirty |= old_bits & mask_to_clear;
> > +    }
> > +
> > +    return dirty;
> > +}
> 
> Same here; you can use atomic_xchg, which is faster because on x86
> atomic_fetch_and must do a compare-and-swap loop.

Will fix in v2.

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]

[Qemu-devel] [RFC 3/6] memory: use atomic ops for setting dirty memory bits

[Stefan Hajnoczi]

Use set_bit_atomic() and bitmap_set_atomic() so that multiple threads
can dirty memory without race conditions.

Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
---
I had to get creative to stay under 80 characters per line.  I'm open to
suggestions if you prefer me to format it another way.
---
 include/exec/ram_addr.h | 21 ++++++++++++---------
 1 file changed, 12 insertions(+), 9 deletions(-)

diff --git a/include/exec/ram_addr.h b/include/exec/ram_addr.h
index 8fc75cd..ba90daa 100644
--- a/include/exec/ram_addr.h
+++ b/include/exec/ram_addr.h
@@ -93,30 +93,32 @@ static inline void cpu_physical_memory_set_dirty_flag(ram_addr_t addr,
                                                       unsigned client)
 {
     assert(client < DIRTY_MEMORY_NUM);
-    set_bit(addr >> TARGET_PAGE_BITS, ram_list.dirty_memory[client]);
+    set_bit_atomic(addr >> TARGET_PAGE_BITS, ram_list.dirty_memory[client]);
 }
 
 static inline void cpu_physical_memory_set_dirty_range_nocode(ram_addr_t start,
                                                               ram_addr_t length)
 {
     unsigned long end, page;
+    unsigned long **dirty_memory = ram_list.dirty_memory;
 
     end = TARGET_PAGE_ALIGN(start + length) >> TARGET_PAGE_BITS;
     page = start >> TARGET_PAGE_BITS;
-    bitmap_set(ram_list.dirty_memory[DIRTY_MEMORY_MIGRATION], page, end - page);
-    bitmap_set(ram_list.dirty_memory[DIRTY_MEMORY_VGA], page, end - page);
+    bitmap_set_atomic(dirty_memory[DIRTY_MEMORY_MIGRATION], page, end - page);
+    bitmap_set_atomic(dirty_memory[DIRTY_MEMORY_VGA], page, end - page);
 }
 
 static inline void cpu_physical_memory_set_dirty_range(ram_addr_t start,
                                                        ram_addr_t length)
 {
     unsigned long end, page;
+    unsigned long **dirty_memory = ram_list.dirty_memory;
 
     end = TARGET_PAGE_ALIGN(start + length) >> TARGET_PAGE_BITS;
     page = start >> TARGET_PAGE_BITS;
-    bitmap_set(ram_list.dirty_memory[DIRTY_MEMORY_MIGRATION], page, end - page);
-    bitmap_set(ram_list.dirty_memory[DIRTY_MEMORY_VGA], page, end - page);
-    bitmap_set(ram_list.dirty_memory[DIRTY_MEMORY_CODE], page, end - page);
+    bitmap_set_atomic(dirty_memory[DIRTY_MEMORY_MIGRATION], page, end - page);
+    bitmap_set_atomic(dirty_memory[DIRTY_MEMORY_VGA], page, end - page);
+    bitmap_set_atomic(dirty_memory[DIRTY_MEMORY_CODE], page, end - page);
     xen_modified_memory(start, length);
 }
 
@@ -142,10 +144,11 @@ static inline void cpu_physical_memory_set_dirty_lebitmap(unsigned long *bitmap,
         for (k = 0; k < nr; k++) {
             if (bitmap[k]) {
                 unsigned long temp = leul_to_cpu(bitmap[k]);
+                unsigned long **d = ram_list.dirty_memory;
 
-                ram_list.dirty_memory[DIRTY_MEMORY_MIGRATION][page + k] |= temp;
-                ram_list.dirty_memory[DIRTY_MEMORY_VGA][page + k] |= temp;
-                ram_list.dirty_memory[DIRTY_MEMORY_CODE][page + k] |= temp;
+                atomic_or(&d[DIRTY_MEMORY_MIGRATION][page + k], temp);
+                atomic_or(&d[DIRTY_MEMORY_VGA][page + k], temp);
+                atomic_or(&d[DIRTY_MEMORY_CODE][page + k], temp);
             }
         }
         xen_modified_memory(start, pages);
-- 
2.1.0

[Qemu-devel] [RFC 4/6] migration: move dirty bitmap sync to ram_addr.h

[Stefan Hajnoczi]

The dirty memory bitmap is managed by ram_addr.h and copied to
migration_bitmap[] periodically during live migration.

Move the code to sync the bitmap to ram_addr.h where related code lives.

Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
---
 arch_init.c             | 46 ++--------------------------------------------
 include/exec/ram_addr.h | 44 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 46 insertions(+), 44 deletions(-)

diff --git a/arch_init.c b/arch_init.c
index 7680d28..79c7784 100644
--- a/arch_init.c
+++ b/arch_init.c
@@ -436,52 +436,10 @@ ram_addr_t migration_bitmap_find_and_reset_dirty(MemoryRegion *mr,
     return (next - base) << TARGET_PAGE_BITS;
 }
 
-static inline bool migration_bitmap_set_dirty(ram_addr_t addr)
-{
-    bool ret;
-    int nr = addr >> TARGET_PAGE_BITS;
-
-    ret = test_and_set_bit(nr, migration_bitmap);
-
-    if (!ret) {
-        migration_dirty_pages++;
-    }
-    return ret;
-}
-
 static void migration_bitmap_sync_range(ram_addr_t start, ram_addr_t length)
 {
-    ram_addr_t addr;
-    unsigned long page = BIT_WORD(start >> TARGET_PAGE_BITS);
-
-    /* start address is aligned at the start of a word? */
-    if (((page * BITS_PER_LONG) << TARGET_PAGE_BITS) == start) {
-        int k;
-        int nr = BITS_TO_LONGS(length >> TARGET_PAGE_BITS);
-        unsigned long *src = ram_list.dirty_memory[DIRTY_MEMORY_MIGRATION];
-
-        for (k = page; k < page + nr; k++) {
-            if (src[k]) {
-                unsigned long new_dirty;
-                new_dirty = ~migration_bitmap[k];
-                migration_bitmap[k] |= src[k];
-                new_dirty &= src[k];
-                migration_dirty_pages += ctpopl(new_dirty);
-                src[k] = 0;
-            }
-        }
-    } else {
-        for (addr = 0; addr < length; addr += TARGET_PAGE_SIZE) {
-            if (cpu_physical_memory_get_dirty(start + addr,
-                                              TARGET_PAGE_SIZE,
-                                              DIRTY_MEMORY_MIGRATION)) {
-                cpu_physical_memory_reset_dirty(start + addr,
-                                                TARGET_PAGE_SIZE,
-                                                DIRTY_MEMORY_MIGRATION);
-                migration_bitmap_set_dirty(start + addr);
-            }
-        }
-    }
+    migration_dirty_pages +=
+        cpu_physical_memory_sync_dirty_bitmap(migration_bitmap, start, length);
 }
 
 
diff --git a/include/exec/ram_addr.h b/include/exec/ram_addr.h
index ba90daa..87a8b28 100644
--- a/include/exec/ram_addr.h
+++ b/include/exec/ram_addr.h
@@ -190,5 +190,49 @@ static inline void cpu_physical_memory_clear_dirty_range(ram_addr_t start,
 void cpu_physical_memory_reset_dirty(ram_addr_t start, ram_addr_t length,
                                      unsigned client);
 
+static inline
+uint64_t cpu_physical_memory_sync_dirty_bitmap(unsigned long *dest,
+                                               ram_addr_t start,
+                                               ram_addr_t length)
+{
+    ram_addr_t addr;
+    unsigned long page = BIT_WORD(start >> TARGET_PAGE_BITS);
+    uint64_t num_dirty = 0;
+
+    /* start address is aligned at the start of a word? */
+    if (((page * BITS_PER_LONG) << TARGET_PAGE_BITS) == start) {
+        int k;
+        int nr = BITS_TO_LONGS(length >> TARGET_PAGE_BITS);
+        unsigned long *src = ram_list.dirty_memory[DIRTY_MEMORY_MIGRATION];
+
+        for (k = page; k < page + nr; k++) {
+            if (src[k]) {
+                unsigned long new_dirty;
+                new_dirty = ~dest[k];
+                dest[k] |= src[k];
+                new_dirty &= src[k];
+                num_dirty += ctpopl(new_dirty);
+                src[k] = 0;
+            }
+        }
+    } else {
+        for (addr = 0; addr < length; addr += TARGET_PAGE_SIZE) {
+            if (cpu_physical_memory_get_dirty(start + addr,
+                                              TARGET_PAGE_SIZE,
+                                              DIRTY_MEMORY_MIGRATION)) {
+                cpu_physical_memory_reset_dirty(start + addr,
+                                                TARGET_PAGE_SIZE,
+                                                DIRTY_MEMORY_MIGRATION);
+                long k = (start + addr) >> TARGET_PAGE_BITS;
+                if (!test_and_set_bit(k, dest)) {
+                    num_dirty++;
+                }
+            }
+        }
+    }
+
+    return num_dirty;
+}
+
 #endif
 #endif
-- 
2.1.0

Re: [Qemu-devel] [RFC 4/6] migration: move dirty bitmap sync to ram_addr.h

[Dr. David Alan Gilbert]

* Stefan Hajnoczi (stefanha@redhat.com) wrote:
> The dirty memory bitmap is managed by ram_addr.h and copied to
> migration_bitmap[] periodically during live migration.
> 
> Move the code to sync the bitmap to ram_addr.h where related code lives.

Is this sync code going to need to gain a barrier (although I'm not quite
sure which) to ensure it's picked up all changes?

Dave

> 
> Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
> ---
>  arch_init.c             | 46 ++--------------------------------------------
>  include/exec/ram_addr.h | 44 ++++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 46 insertions(+), 44 deletions(-)
> 
> diff --git a/arch_init.c b/arch_init.c
> index 7680d28..79c7784 100644
> --- a/arch_init.c
> +++ b/arch_init.c
> @@ -436,52 +436,10 @@ ram_addr_t migration_bitmap_find_and_reset_dirty(MemoryRegion *mr,
>      return (next - base) << TARGET_PAGE_BITS;
>  }
>  
> -static inline bool migration_bitmap_set_dirty(ram_addr_t addr)
> -{
> -    bool ret;
> -    int nr = addr >> TARGET_PAGE_BITS;
> -
> -    ret = test_and_set_bit(nr, migration_bitmap);
> -
> -    if (!ret) {
> -        migration_dirty_pages++;
> -    }
> -    return ret;
> -}
> -
>  static void migration_bitmap_sync_range(ram_addr_t start, ram_addr_t length)
>  {
> -    ram_addr_t addr;
> -    unsigned long page = BIT_WORD(start >> TARGET_PAGE_BITS);
> -
> -    /* start address is aligned at the start of a word? */
> -    if (((page * BITS_PER_LONG) << TARGET_PAGE_BITS) == start) {
> -        int k;
> -        int nr = BITS_TO_LONGS(length >> TARGET_PAGE_BITS);
> -        unsigned long *src = ram_list.dirty_memory[DIRTY_MEMORY_MIGRATION];
> -
> -        for (k = page; k < page + nr; k++) {
> -            if (src[k]) {
> -                unsigned long new_dirty;
> -                new_dirty = ~migration_bitmap[k];
> -                migration_bitmap[k] |= src[k];
> -                new_dirty &= src[k];
> -                migration_dirty_pages += ctpopl(new_dirty);
> -                src[k] = 0;
> -            }
> -        }
> -    } else {
> -        for (addr = 0; addr < length; addr += TARGET_PAGE_SIZE) {
> -            if (cpu_physical_memory_get_dirty(start + addr,
> -                                              TARGET_PAGE_SIZE,
> -                                              DIRTY_MEMORY_MIGRATION)) {
> -                cpu_physical_memory_reset_dirty(start + addr,
> -                                                TARGET_PAGE_SIZE,
> -                                                DIRTY_MEMORY_MIGRATION);
> -                migration_bitmap_set_dirty(start + addr);
> -            }
> -        }
> -    }
> +    migration_dirty_pages +=
> +        cpu_physical_memory_sync_dirty_bitmap(migration_bitmap, start, length);
>  }
>  
>  
> diff --git a/include/exec/ram_addr.h b/include/exec/ram_addr.h
> index ba90daa..87a8b28 100644
> --- a/include/exec/ram_addr.h
> +++ b/include/exec/ram_addr.h
> @@ -190,5 +190,49 @@ static inline void cpu_physical_memory_clear_dirty_range(ram_addr_t start,
>  void cpu_physical_memory_reset_dirty(ram_addr_t start, ram_addr_t length,
>                                       unsigned client);
>  
> +static inline
> +uint64_t cpu_physical_memory_sync_dirty_bitmap(unsigned long *dest,
> +                                               ram_addr_t start,
> +                                               ram_addr_t length)
> +{
> +    ram_addr_t addr;
> +    unsigned long page = BIT_WORD(start >> TARGET_PAGE_BITS);
> +    uint64_t num_dirty = 0;
> +
> +    /* start address is aligned at the start of a word? */
> +    if (((page * BITS_PER_LONG) << TARGET_PAGE_BITS) == start) {
> +        int k;
> +        int nr = BITS_TO_LONGS(length >> TARGET_PAGE_BITS);
> +        unsigned long *src = ram_list.dirty_memory[DIRTY_MEMORY_MIGRATION];
> +
> +        for (k = page; k < page + nr; k++) {
> +            if (src[k]) {
> +                unsigned long new_dirty;
> +                new_dirty = ~dest[k];
> +                dest[k] |= src[k];
> +                new_dirty &= src[k];
> +                num_dirty += ctpopl(new_dirty);
> +                src[k] = 0;
> +            }
> +        }
> +    } else {
> +        for (addr = 0; addr < length; addr += TARGET_PAGE_SIZE) {
> +            if (cpu_physical_memory_get_dirty(start + addr,
> +                                              TARGET_PAGE_SIZE,
> +                                              DIRTY_MEMORY_MIGRATION)) {
> +                cpu_physical_memory_reset_dirty(start + addr,
> +                                                TARGET_PAGE_SIZE,
> +                                                DIRTY_MEMORY_MIGRATION);
> +                long k = (start + addr) >> TARGET_PAGE_BITS;
> +                if (!test_and_set_bit(k, dest)) {
> +                    num_dirty++;
> +                }
> +            }
> +        }
> +    }
> +
> +    return num_dirty;
> +}
> +
>  #endif
>  #endif
> -- 
> 2.1.0
> 
> 
--
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK

Re: [Qemu-devel] [RFC 4/6] migration: move dirty bitmap sync to ram_addr.h

[Stefan Hajnoczi]

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

On Thu, Nov 27, 2014 at 04:29:06PM +0000, Dr. David Alan Gilbert wrote:
> * Stefan Hajnoczi (stefanha@redhat.com) wrote:
> > The dirty memory bitmap is managed by ram_addr.h and copied to
> > migration_bitmap[] periodically during live migration.
> > 
> > Move the code to sync the bitmap to ram_addr.h where related code lives.
> 
> Is this sync code going to need to gain a barrier (although I'm not quite
> sure which) to ensure it's picked up all changes?

gcc makes these operations a full barrier:
https://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Atomic-Builtins.html

Stefan

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]

Re: [Qemu-devel] [RFC 4/6] migration: move dirty bitmap sync to ram_addr.h

[Dr. David Alan Gilbert]

* Stefan Hajnoczi (stefanha@redhat.com) wrote:
> On Thu, Nov 27, 2014 at 04:29:06PM +0000, Dr. David Alan Gilbert wrote:
> > * Stefan Hajnoczi (stefanha@redhat.com) wrote:
> > > The dirty memory bitmap is managed by ram_addr.h and copied to
> > > migration_bitmap[] periodically during live migration.
> > > 
> > > Move the code to sync the bitmap to ram_addr.h where related code lives.
> > 
> > Is this sync code going to need to gain a barrier (although I'm not quite
> > sure which) to ensure it's picked up all changes?
> 
> gcc makes these operations a full barrier:
> https://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Atomic-Builtins.html

Ah yes; actually our docs/atomics.txt is a good reference - all
the operations you're using are in the sequentially consistent
half of that doc.

Dave

> 
> Stefan


--
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK

[Qemu-devel] [RFC 5/6] memory: replace cpu_physical_memory_reset_dirty() with test-and-clear

[Stefan Hajnoczi]

The cpu_physical_memory_reset_dirty() function is sometimes used
together with cpu_physical_memory_get_dirty().  This is not atomic since
two separate accesses to the dirty memory bitmap are made.

Turn cpu_physical_memory_reset_dirty() into the atomic
cpu_physical_memory_test_and_clear_dirty().

The cpu_physical_memory_clear_dirty_range() function is no longer used
and can be dropped.

Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
---
 cputlb.c                |  4 ++--
 exec.c                  | 23 +++++++++++++++++------
 include/exec/ram_addr.h | 27 +++++++--------------------
 memory.c                | 11 ++++-------
 4 files changed, 30 insertions(+), 35 deletions(-)

diff --git a/cputlb.c b/cputlb.c
index a55518a..3d5b9a7 100644
--- a/cputlb.c
+++ b/cputlb.c
@@ -125,8 +125,8 @@ void tlb_flush_page(CPUState *cpu, target_ulong addr)
    can be detected */
 void tlb_protect_code(ram_addr_t ram_addr)
 {
-    cpu_physical_memory_reset_dirty(ram_addr, TARGET_PAGE_SIZE,
-                                    DIRTY_MEMORY_CODE);
+    cpu_physical_memory_test_and_clear_dirty(ram_addr, TARGET_PAGE_SIZE,
+                                             DIRTY_MEMORY_CODE);
 }
 
 /* update the TLB so that writes in physical page 'phys_addr' are no longer
diff --git a/exec.c b/exec.c
index 71ac104..72bdb2e 100644
--- a/exec.c
+++ b/exec.c
@@ -845,16 +845,27 @@ static void tlb_reset_dirty_range_all(ram_addr_t start, ram_addr_t length)
 }
 
 /* Note: start and end must be within the same ram block.  */
-void cpu_physical_memory_reset_dirty(ram_addr_t start, ram_addr_t length,
-                                     unsigned client)
+bool cpu_physical_memory_test_and_clear_dirty(ram_addr_t start,
+                                              ram_addr_t length,
+                                              unsigned client)
 {
-    if (length == 0)
-        return;
-    cpu_physical_memory_clear_dirty_range(start, length, client);
+    unsigned long end, page;
+    bool dirty;
 
-    if (tcg_enabled()) {
+    if (length == 0) {
+        return false;
+    }
+
+    end = TARGET_PAGE_ALIGN(start + length) >> TARGET_PAGE_BITS;
+    page = start >> TARGET_PAGE_BITS;
+    dirty = bitmap_test_and_clear_atomic(ram_list.dirty_memory[client],
+                                         page, end - page);
+
+    if (dirty && tcg_enabled()) {
         tlb_reset_dirty_range_all(start, length);
     }
+
+    return dirty;
 }
 
 static void cpu_physical_memory_set_dirty_tracking(bool enable)
diff --git a/include/exec/ram_addr.h b/include/exec/ram_addr.h
index 87a8b28..cdcbe9a 100644
--- a/include/exec/ram_addr.h
+++ b/include/exec/ram_addr.h
@@ -175,20 +175,9 @@ static inline void cpu_physical_memory_set_dirty_lebitmap(unsigned long *bitmap,
 }
 #endif /* not _WIN32 */
 
-static inline void cpu_physical_memory_clear_dirty_range(ram_addr_t start,
-                                                         ram_addr_t length,
-                                                         unsigned client)
-{
-    unsigned long end, page;
-
-    assert(client < DIRTY_MEMORY_NUM);
-    end = TARGET_PAGE_ALIGN(start + length) >> TARGET_PAGE_BITS;
-    page = start >> TARGET_PAGE_BITS;
-    bitmap_clear(ram_list.dirty_memory[client], page, end - page);
-}
-
-void cpu_physical_memory_reset_dirty(ram_addr_t start, ram_addr_t length,
-                                     unsigned client);
+bool cpu_physical_memory_test_and_clear_dirty(ram_addr_t start,
+                                              ram_addr_t length,
+                                              unsigned client);
 
 static inline
 uint64_t cpu_physical_memory_sync_dirty_bitmap(unsigned long *dest,
@@ -217,12 +206,10 @@ uint64_t cpu_physical_memory_sync_dirty_bitmap(unsigned long *dest,
         }
     } else {
         for (addr = 0; addr < length; addr += TARGET_PAGE_SIZE) {
-            if (cpu_physical_memory_get_dirty(start + addr,
-                                              TARGET_PAGE_SIZE,
-                                              DIRTY_MEMORY_MIGRATION)) {
-                cpu_physical_memory_reset_dirty(start + addr,
-                                                TARGET_PAGE_SIZE,
-                                                DIRTY_MEMORY_MIGRATION);
+            if (cpu_physical_memory_test_and_clear_dirty(
+                        start + addr,
+                        TARGET_PAGE_SIZE,
+                        DIRTY_MEMORY_MIGRATION)) {
                 long k = (start + addr) >> TARGET_PAGE_BITS;
                 if (!test_and_set_bit(k, dest)) {
                     num_dirty++;
diff --git a/memory.c b/memory.c
index 15cf9eb..4d7761e 100644
--- a/memory.c
+++ b/memory.c
@@ -1375,13 +1375,9 @@ void memory_region_set_dirty(MemoryRegion *mr, hwaddr addr,
 bool memory_region_test_and_clear_dirty(MemoryRegion *mr, hwaddr addr,
                                         hwaddr size, unsigned client)
 {
-    bool ret;
     assert(mr->terminates);
-    ret = cpu_physical_memory_get_dirty(mr->ram_addr + addr, size, client);
-    if (ret) {
-        cpu_physical_memory_reset_dirty(mr->ram_addr + addr, size, client);
-    }
-    return ret;
+    return cpu_physical_memory_test_and_clear_dirty(mr->ram_addr + addr,
+                                                    size, client);
 }
 
 
@@ -1425,7 +1421,8 @@ void memory_region_reset_dirty(MemoryRegion *mr, hwaddr addr,
                                hwaddr size, unsigned client)
 {
     assert(mr->terminates);
-    cpu_physical_memory_reset_dirty(mr->ram_addr + addr, size, client);
+    cpu_physical_memory_test_and_clear_dirty(mr->ram_addr + addr, size,
+                                             client);
 }
 
 int memory_region_get_fd(MemoryRegion *mr)
-- 
2.1.0

[Qemu-devel] [RFC 6/6] memory: make cpu_physical_memory_sync_dirty_bitmap() fully atomic

[Stefan Hajnoczi]

The fast path of cpu_physical_memory_sync_dirty_bitmap() directly
manipulates the dirty bitmap.  Use atomic_xchg() to make the
test-and-clear atomic.

Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
---
 include/exec/ram_addr.h | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/include/exec/ram_addr.h b/include/exec/ram_addr.h
index cdcbe9a..3d2a4c1 100644
--- a/include/exec/ram_addr.h
+++ b/include/exec/ram_addr.h
@@ -195,13 +195,13 @@ uint64_t cpu_physical_memory_sync_dirty_bitmap(unsigned long *dest,
         unsigned long *src = ram_list.dirty_memory[DIRTY_MEMORY_MIGRATION];
 
         for (k = page; k < page + nr; k++) {
-            if (src[k]) {
+            unsigned long bits = atomic_xchg(&src[k], 0);
+            if (bits) {
                 unsigned long new_dirty;
                 new_dirty = ~dest[k];
-                dest[k] |= src[k];
-                new_dirty &= src[k];
+                dest[k] |= bits;
+                new_dirty &= bits;
                 num_dirty += ctpopl(new_dirty);
-                src[k] = 0;
             }
         }
     } else {
-- 
2.1.0

Re: [Qemu-devel] [RFC 0/6] memory: make dirty_memory[] accesses atomic

[Peter Maydell]

On 27 November 2014 at 12:29, Stefan Hajnoczi <stefanha@redhat.com> wrote:
> 1. Convert all cpu_physical_memory_*_dirty() callers to use the API atomically.
>    There are TCG callers who things along the lines of:
>
>      if (!cpu_physical_memory_get_dirty(addr)) {
>          cpu_physical_memory_set_dirty(addr);  /* not atomic! */
>      }

Which bit of code is this? Note that for the TCG DIRTY_MEMORY_CODE
flag you have bigger problems than just whether the bitmap updates
are atomic, because the sequence is:
 write to memory
 if (!dirty) {
     flush generated code tbs;
     set dirty;
 }

and what you care about is that the existence of cached translations
for this area of memory should be in sync with the state of the dirty
bit, so the whole operation of "flush affected translations and set
the dirty bit" needs to be thread-safe, I think.

-- PMM

Re: [Qemu-devel] [RFC 0/6] memory: make dirty_memory[] accesses atomic

[Stefan Hajnoczi]

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

On Thu, Nov 27, 2014 at 01:21:54PM +0000, Peter Maydell wrote:
> On 27 November 2014 at 12:29, Stefan Hajnoczi <stefanha@redhat.com> wrote:
> > 1. Convert all cpu_physical_memory_*_dirty() callers to use the API atomically.
> >    There are TCG callers who things along the lines of:
> >
> >      if (!cpu_physical_memory_get_dirty(addr)) {
> >          cpu_physical_memory_set_dirty(addr);  /* not atomic! */
> >      }
> 
> Which bit of code is this? Note that for the TCG DIRTY_MEMORY_CODE
> flag you have bigger problems than just whether the bitmap updates
> are atomic, because the sequence is:
>  write to memory
>  if (!dirty) {
>      flush generated code tbs;
>      set dirty;
>  }
> 
> and what you care about is that the existence of cached translations
> for this area of memory should be in sync with the state of the dirty
> bit, so the whole operation of "flush affected translations and set
> the dirty bit" needs to be thread-safe, I think.

This is an example of what I mean.

I'm not going to work on making TCG thread-safe in this series, and
there is no dangerous race condition in this code if we leave it as is.

But I'm not 100% sure of all cases, so I'll audit them again.

Stefan

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]

Re: [Qemu-devel] [RFC 0/6] memory: make dirty_memory[] accesses atomic

[Paolo Bonzini]

On 28/11/2014 13:44, Stefan Hajnoczi wrote:
> This is an example of what I mean.
> 
> I'm not going to work on making TCG thread-safe in this series, and
> there is no dangerous race condition in this code if we leave it as is.
> 
> But I'm not 100% sure of all cases, so I'll audit them again.

I looked at this again, and I agree that this series is not making
anything worse.

We have to start somewhere, so I'm thinking of queuing this series for
2.4.  Making dirty bitmaps thread-safe with respect to memory hotplug
can be done on top---especially since we already have a plan for that.

Paolo

Re: [Qemu-devel] [RFC 0/6] memory: make dirty_memory[] accesses atomic

[Stefan Hajnoczi]

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

On Mon, Mar 23, 2015 at 12:09:55PM +0100, Paolo Bonzini wrote:
> 
> 
> On 28/11/2014 13:44, Stefan Hajnoczi wrote:
> > This is an example of what I mean.
> > 
> > I'm not going to work on making TCG thread-safe in this series, and
> > there is no dangerous race condition in this code if we leave it as is.
> > 
> > But I'm not 100% sure of all cases, so I'll audit them again.
> 
> I looked at this again, and I agree that this series is not making
> anything worse.
> 
> We have to start somewhere, so I'm thinking of queuing this series for
> 2.4.  Making dirty bitmaps thread-safe with respect to memory hotplug
> can be done on top---especially since we already have a plan for that.

Hi Paolo,
Thanks for bringing this series up again.

I'm still happy with it.  Let me know if you'd like me to rebase.

Stefan

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]