diff --git a/balloon.c b/balloon.c
index f2ef50c..c814102 100644
--- a/balloon.c
+++ b/balloon.c
@@ -33,9 +33,19 @@
 #include "qmp-commands.h"
 #include "qapi/qmp/qerror.h"
 #include "qapi/qmp/qjson.h"
+#include "exec/ram_addr.h"
+#include "migration/vmstate.h"
+
+#define BALLOON_BMAP_NAME       "balloon.bmap"
+#define BALLOON_BMAP_SIZE(nr)   (nr / (((1UL << balloon_bitmap_pfn_shift) * \
+                                         sizeof(unsigned long)) - 1))
 
 static QEMUBalloonEvent *balloon_event_fn;
 static QEMUBalloonStatus *balloon_stat_fn;
+static QemuMutex balloon_bmap_mutex;
+static MemoryRegion *bmap_mr;
+static unsigned long *bmap;
+static unsigned int balloon_bitmap_pfn_shift;
 static void *balloon_opaque;
 static bool balloon_inhibited;
 
@@ -49,6 +59,16 @@ void qemu_balloon_inhibit(bool state)
     balloon_inhibited = state;
 }
 
+void qemu_mutex_lock_balloon_bitmap(void)
+{
+    qemu_mutex_lock(&balloon_bmap_mutex);
+}
+
+void qemu_mutex_unlock_balloon_bitmap(void)
+{
+    qemu_mutex_unlock(&balloon_bmap_mutex);
+}
+
 static bool have_balloon(Error **errp)
 {
     if (kvm_enabled() && !kvm_has_sync_mmu()) {
@@ -65,7 +85,8 @@ static bool have_balloon(Error **errp)
 }
 
 int qemu_add_balloon_handler(QEMUBalloonEvent *event_func,
-                             QEMUBalloonStatus *stat_func, void *opaque)
+                             QEMUBalloonStatus *stat_func,
+                             void *opaque, int balloon_pfn_shift)
 {
     if (balloon_event_fn || balloon_stat_fn || balloon_opaque) {
         /* We're already registered one balloon handler.  How many can
@@ -75,7 +96,18 @@ int qemu_add_balloon_handler(QEMUBalloonEvent *event_func,
     }
     balloon_event_fn = event_func;
     balloon_stat_fn = stat_func;
+    balloon_bitmap_pfn_shift = balloon_pfn_shift;
     balloon_opaque = opaque;
+
+    qemu_mutex_init(&balloon_bmap_mutex);
+    bmap_mr = g_new(MemoryRegion, 1);
+    memory_region_init_resizeable_ram(bmap_mr, NULL, BALLOON_BMAP_NAME,
+                                      BALLOON_BMAP_SIZE((last_ram_offset())),
+                                      BALLOON_BMAP_SIZE((last_ram_offset())),
+                                      NULL, &error_fatal);
+    vmstate_register_ram_global(bmap_mr);
+    bmap = memory_region_get_ram_ptr(bmap_mr);
+    bitmap_clear(bmap, 0, (last_ram_offset() >> balloon_bitmap_pfn_shift));
     return 0;
 }
 
@@ -84,6 +116,8 @@ void qemu_remove_balloon_handler(void *opaque)
     if (balloon_opaque != opaque) {
         return;
     }
+    object_unref(OBJECT(bmap_mr));
+    bmap = NULL;
     balloon_event_fn = NULL;
     balloon_stat_fn = NULL;
     balloon_opaque = NULL;
@@ -116,3 +150,58 @@ void qmp_balloon(int64_t target, Error **errp)
     trace_balloon_event(balloon_opaque, target);
     balloon_event_fn(balloon_opaque, target);
 }
+
+/* Should be called with balloon bitmap mutex lock held */
+void qemu_balloon_bitmap_update(ram_addr_t addr, int deflate)
+{
+    unsigned long offset = 0;
+
+    if (!bmap) {
+        return;
+    }
+    offset = (addr >> balloon_bitmap_pfn_shift);
+    if (deflate == 0) {
+        set_bit(offset, bmap);
+    } else {
+        clear_bit(offset, bmap);
+    }
+}
+
+/* Handle Ram hotplug case, only called in case old < new */
+void qemu_balloon_bitmap_extend(RAMBlock *new_block,
+                                ram_addr_t old, ram_addr_t new)
+{
+    RAMBlock *block = NULL;
+    unsigned long *old_bitmap;
+
+    if (!bmap || !new_block || (new_block->mr &&
+        (strcmp(new_block->mr->name, BALLOON_BMAP_NAME) == 0))) {
+        return;
+    }
+
+    block = qemu_ram_block_by_name(BALLOON_BMAP_NAME);
+    if (BALLOON_BMAP_SIZE((last_ram_offset())) <= block->used_length) {
+        /* Current bitmap already considers new size */
+        return;
+    }
+
+    old = old >> balloon_bitmap_pfn_shift;
+    new = new >> balloon_bitmap_pfn_shift;
+
+    old_bitmap = bitmap_new(old);
+    bitmap_clear(old_bitmap, 0, old);
+    qemu_mutex_lock_balloon_bitmap();
+    bitmap_copy(old_bitmap, bmap, old);
+    object_unref(OBJECT(bmap_mr));
+    memory_region_init_resizeable_ram(bmap_mr, NULL, BALLOON_BMAP_NAME,
+                                      BALLOON_BMAP_SIZE((last_ram_offset())),
+                                      BALLOON_BMAP_SIZE((last_ram_offset())),
+                                      NULL, &error_fatal);
+
+    vmstate_register_ram_global(bmap_mr);
+    bmap = memory_region_get_ram_ptr(bmap_mr);
+    bitmap_clear(bmap, 0, new);
+    bitmap_copy(bmap, old_bitmap, old);
+    qemu_mutex_unlock_balloon_bitmap();
+    g_free(old_bitmap);
+}
diff --git a/exec.c b/exec.c
index ee45472..5a67a4f 100644
--- a/exec.c
+++ b/exec.c
@@ -44,6 +44,7 @@
 #else /* !CONFIG_USER_ONLY */
 #include "sysemu/xen-mapcache.h"
 #include "trace.h"
+#include "sysemu/balloon.h"
 #endif
 #include "exec/cpu-all.h"
 #include "qemu/rcu_queue.h"
@@ -1636,6 +1637,11 @@ static void ram_block_add(RAMBlock *new_block, Error **errp)
     smp_wmb();
     ram_list.version++;
     qemu_mutex_unlock_ramlist();
+    if (new_ram_size > old_ram_size) {
+        qemu_balloon_bitmap_extend(new_block,
+                                   (old_ram_size << TARGET_PAGE_BITS),
+                                   (new_ram_size << TARGET_PAGE_BITS));
+    }
 
     cpu_physical_memory_set_dirty_range(new_block->offset,
                                         new_block->used_length,
diff --git a/hw/virtio/virtio-balloon.c b/hw/virtio/virtio-balloon.c
index 8c15e09..33750f7 100644
--- a/hw/virtio/virtio-balloon.c
+++ b/hw/virtio/virtio-balloon.c
@@ -216,17 +216,21 @@ static void virtio_balloon_handle_output(VirtIODevice *vdev, VirtQueue *vq)
     VirtQueueElement *elem;
     MemoryRegionSection section;
 
+    qemu_mutex_lock_balloon_bitmap();
     for (;;) {
         size_t offset = 0;
         uint32_t pfn;
         elem = virtqueue_pop(vq, sizeof(VirtQueueElement));
         if (!elem) {
+            qemu_mutex_unlock_balloon_bitmap();
             return;
         }
 
         while (iov_to_buf(elem->out_sg, elem->out_num, offset, &pfn, 4) == 4) {
             ram_addr_t pa;
             ram_addr_t addr;
+            void *user_addr;
+            ram_addr_t ram_addr, ram_addr_offset;
             int p = virtio_ldl_p(vdev, &pfn);
 
             pa = (ram_addr_t) p << VIRTIO_BALLOON_PFN_SHIFT;
@@ -244,6 +248,15 @@ static void virtio_balloon_handle_output(VirtIODevice *vdev, VirtQueue *vq)
             addr = section.offset_within_region;
             balloon_page(memory_region_get_ram_ptr(section.mr) + addr,
                          !!(vq == s->dvq));
+            user_addr = memory_region_get_ram_ptr(section.mr) + addr;
+            qemu_ram_block_from_host(user_addr, true, &ram_addr,
+                                     &ram_addr_offset);
+            if (TARGET_PAGE_BITS > VIRTIO_BALLOON_PFN_SHIFT) {
+                /* ram_addr will be TARGET_PAGE_BITS alligned, add offset */
+                ram_addr = ram_addr +  ((unsigned long)user_addr &
+                                        ((1UL << TARGET_PAGE_BITS) - 1));
+            }
+            qemu_balloon_bitmap_update(ram_addr, !!(vq == s->dvq));
             memory_region_unref(section.mr);
         }
 
@@ -251,6 +264,7 @@ static void virtio_balloon_handle_output(VirtIODevice *vdev, VirtQueue *vq)
         virtio_notify(vdev, vq);
         g_free(elem);
     }
+    qemu_mutex_unlock_balloon_bitmap();
 }
 
 static void virtio_balloon_receive_stats(VirtIODevice *vdev, VirtQueue *vq)
@@ -445,7 +459,8 @@ static void virtio_balloon_device_realize(DeviceState *dev, Error **errp)
                 sizeof(struct virtio_balloon_config));
 
     ret = qemu_add_balloon_handler(virtio_balloon_to_target,
-                                   virtio_balloon_stat, s);
+                                   virtio_balloon_stat,
+                                   s, VIRTIO_BALLOON_PFN_SHIFT);
 
     if (ret < 0) {
         error_setg(errp, "Only one balloon device is supported");
diff --git a/include/sysemu/balloon.h b/include/sysemu/balloon.h
index 3f976b4..ebaa292 100644
--- a/include/sysemu/balloon.h
+++ b/include/sysemu/balloon.h
@@ -20,9 +20,15 @@ typedef void (QEMUBalloonEvent)(void *opaque, ram_addr_t target);
 typedef void (QEMUBalloonStatus)(void *opaque, BalloonInfo *info);
 
 int qemu_add_balloon_handler(QEMUBalloonEvent *event_func,
-			     QEMUBalloonStatus *stat_func, void *opaque);
+                             QEMUBalloonStatus *stat_func,
+                             void *opaque, int balloon_pfn_shift);
 void qemu_remove_balloon_handler(void *opaque);
 bool qemu_balloon_is_inhibited(void);
 void qemu_balloon_inhibit(bool state);
+void qemu_mutex_lock_balloon_bitmap(void);
+void qemu_mutex_unlock_balloon_bitmap(void);
+void qemu_balloon_bitmap_update(ram_addr_t addr, int deflate);
+void qemu_balloon_bitmap_extend(RAMBlock *new_block,
+                                ram_addr_t old, ram_addr_t new);
 
 #endif
