diff --git a/async.c b/async.c
index 5b6fe6b..687cdb2 100644
--- a/async.c
+++ b/async.c
@@ -26,6 +26,7 @@
 #include "block/aio.h"
 #include "block/thread-pool.h"
 #include "qemu/main-loop.h"
+#include "replay/replay.h"
 
 /***********************************************************/
 /* bottom halves (can be seen as timers which expire ASAP) */
@@ -38,24 +39,52 @@ struct QEMUBH {
     bool scheduled;
     bool idle;
     bool deleted;
+    bool replay;
+    uint64_t id;
 };
 
 QEMUBH *aio_bh_new(AioContext *ctx, QEMUBHFunc *cb, void *opaque)
 {
-    QEMUBH *bh;
+    QEMUBH *bh, **last;
     bh = g_malloc0(sizeof(QEMUBH));
     bh->ctx = ctx;
     bh->cb = cb;
     bh->opaque = opaque;
     qemu_mutex_lock(&ctx->bh_lock);
-    bh->next = ctx->first_bh;
-    /* Make sure that the members are ready before putting bh into list */
-    smp_wmb();
-    ctx->first_bh = bh;
+    if (replay_mode != REPLAY_NONE) {
+        /* Slower way, but this is a queue and not a stack.
+           Replay will process the BH in the same order they 
+           came into the queue. */
+        last = &ctx->first_bh;
+        while (*last) {
+            last = &(*last)->next;
+        }
+        smp_wmb();
+        *last = bh;
+    } else {
+        bh->next = ctx->first_bh;
+        /* Make sure that the members are ready before putting bh into list */
+        smp_wmb();
+        ctx->first_bh = bh;
+    }
     qemu_mutex_unlock(&ctx->bh_lock);
     return bh;
 }
 
+QEMUBH *aio_bh_new_replay(AioContext *ctx, QEMUBHFunc *cb, void *opaque, uint64_t id)
+{
+    QEMUBH *bh = aio_bh_new(ctx, cb, opaque);
+    bh->replay = true;
+    bh->id = id;
+    return bh;
+}
+
+void aio_bh_call(void *opaque)
+{
+    QEMUBH *bh = (QEMUBH *)opaque;
+    bh->cb(bh->opaque);
+}
+
 /* Multiple occurrences of aio_bh_poll cannot be called concurrently */
 int aio_bh_poll(AioContext *ctx)
 {
@@ -78,7 +107,11 @@ int aio_bh_poll(AioContext *ctx)
             if (!bh->idle)
                 ret = 1;
             bh->idle = 0;
-            bh->cb(bh->opaque);
+            if (!bh->replay) {
+                aio_bh_call(bh);
+            } else {
+                replay_add_bh_event(bh, bh->id);
+            }
         }
     }
 
diff --git a/dma-helpers.c b/dma-helpers.c
index 53cbe92..05aadea 100644
--- a/dma-helpers.c
+++ b/dma-helpers.c
@@ -12,6 +12,7 @@
 #include "qemu/range.h"
 #include "qemu/thread.h"
 #include "qemu/main-loop.h"
+#include "replay/replay.h"
 
 /* #define DEBUG_IOMMU */
 
@@ -96,7 +97,8 @@ static void continue_after_map_failure(void *opaque)
 {
     DMAAIOCB *dbs = (DMAAIOCB *)opaque;
 
-    dbs->bh = qemu_bh_new(reschedule_dma, dbs);
+    dbs->bh = qemu_bh_new_replay(reschedule_dma, dbs,
+                                 replay_get_current_step());
     qemu_bh_schedule(dbs->bh);
 }
 
diff --git a/hw/ide/ahci.c b/hw/ide/ahci.c
index 604152a..0762743 100644
--- a/hw/ide/ahci.c
+++ b/hw/ide/ahci.c
@@ -32,6 +32,7 @@
 #include "internal.h"
 #include <hw/ide/pci.h>
 #include <hw/ide/ahci.h>
+#include "replay/replay.h"
 
 /* #define DEBUG_AHCI */
 
@@ -1132,7 +1133,8 @@ static int ahci_async_cmd_done(IDEDMA *dma)
 
     if (!ad->check_bh) {
         /* maybe we still have something to process, check later */
-        ad->check_bh = qemu_bh_new(ahci_check_cmd_bh, ad);
+        ad->check_bh = qemu_bh_new_replay(ahci_check_cmd_bh, ad,
+                                          replay_get_current_step());
         qemu_bh_schedule(ad->check_bh);
     }
 
diff --git a/hw/ide/core.c b/hw/ide/core.c
index 3a38f1e..3df26f0 100644
--- a/hw/ide/core.c
+++ b/hw/ide/core.c
@@ -32,6 +32,7 @@
 #include "sysemu/dma.h"
 #include "hw/block/block.h"
 #include "sysemu/blockdev.h"
+#include "replay/replay.h"
 
 #include <hw/ide/internal.h>
 
@@ -409,7 +410,8 @@ BlockDriverAIOCB *ide_issue_trim(BlockDriverState *bs,
     TrimAIOCB *iocb;
 
     iocb = qemu_aio_get(&trim_aiocb_info, bs, cb, opaque);
-    iocb->bh = qemu_bh_new(ide_trim_bh_cb, iocb);
+    iocb->bh = qemu_bh_new_replay(ide_trim_bh_cb, iocb,
+                                  replay_get_current_step());
     iocb->ret = 0;
     iocb->qiov = qiov;
     iocb->i = -1;
diff --git a/hw/timer/arm_timer.c b/hw/timer/arm_timer.c
index 1452910..97784a0 100644
--- a/hw/timer/arm_timer.c
+++ b/hw/timer/arm_timer.c
@@ -168,7 +168,7 @@ static arm_timer_state *arm_timer_init(uint32_t freq)
     s->freq = freq;
     s->control = TIMER_CTRL_IE;
 
-    bh = qemu_bh_new(arm_timer_tick, s);
+    bh = qemu_bh_new_replay(arm_timer_tick, s, 0);
     s->timer = ptimer_init(bh);
     vmstate_register(NULL, -1, &vmstate_arm_timer, s);
     return s;
diff --git a/hw/usb/hcd-uhci.c b/hw/usb/hcd-uhci.c
index c3bf72c..3aaf506 100644
--- a/hw/usb/hcd-uhci.c
+++ b/hw/usb/hcd-uhci.c
@@ -1224,7 +1224,7 @@ static int usb_uhci_common_initfn(PCIDevice *dev)
                               USB_SPEED_MASK_LOW | USB_SPEED_MASK_FULL);
         }
     }
-    s->bh = qemu_bh_new(uhci_bh, s);
+    s->bh = qemu_bh_new_replay(uhci_bh, s, 0);
     s->frame_timer = timer_new_ns(QEMU_CLOCK_VIRTUAL, uhci_frame_timer, s);
     s->num_ports_vmstate = NB_PORTS;
     QTAILQ_INIT(&s->queues);
diff --git a/include/block/aio.h b/include/block/aio.h
index a92511b..3268ffa 100644
--- a/include/block/aio.h
+++ b/include/block/aio.h
@@ -34,6 +34,8 @@ struct BlockDriverAIOCB {
     const AIOCBInfo *aiocb_info;
     BlockDriverState *bs;
     BlockDriverCompletionFunc *cb;
+    bool replay;
+    uint64_t replay_step;
     void *opaque;
 };
 
@@ -132,6 +134,16 @@ void aio_context_release(AioContext *ctx);
 QEMUBH *aio_bh_new(AioContext *ctx, QEMUBHFunc *cb, void *opaque);
 
 /**
+ * aio_bh_new_replay: Allocate a new bottom half structure for replay.
+ *
+ * This function calls aio_bh_new function and also fills replay parameters
+ * of the BH structure. BH created with this function in record/replay mode
+ * are executed through the replay queue only at checkpoints and instructions
+ * executions.
+ */
+QEMUBH *aio_bh_new_replay(AioContext *ctx, QEMUBHFunc *cb, void *opaque, uint64_t id);
+
+/**
  * aio_notify: Force processing of pending events.
  *
  * Similar to signaling a condition variable, aio_notify forces
@@ -147,6 +159,11 @@ QEMUBH *aio_bh_new(AioContext *ctx, QEMUBHFunc *cb, void *opaque);
 void aio_notify(AioContext *ctx);
 
 /**
+ * aio_bh_call: Executes callback function of the specified BH.
+ */
+void aio_bh_call(void *opaque);
+
+/**
  * aio_bh_poll: Poll bottom halves for an AioContext.
  *
  * These are internal functions used by the QEMU main loop.
diff --git a/include/qemu/main-loop.h b/include/qemu/main-loop.h
index 6f0200a..c221ddd 100644
--- a/include/qemu/main-loop.h
+++ b/include/qemu/main-loop.h
@@ -306,6 +306,7 @@ void qemu_iohandler_fill(GArray *pollfds);
 void qemu_iohandler_poll(GArray *pollfds, int rc);
 
 QEMUBH *qemu_bh_new(QEMUBHFunc *cb, void *opaque);
+QEMUBH *qemu_bh_new_replay(QEMUBHFunc *cb, void *opaque, uint64_t id);
 void qemu_bh_schedule_idle(QEMUBH *bh);
 
 #endif
diff --git a/main-loop.c b/main-loop.c
index 8a85493..4e1af51 100644
--- a/main-loop.c
+++ b/main-loop.c
@@ -499,6 +499,11 @@ QEMUBH *qemu_bh_new(QEMUBHFunc *cb, void *opaque)
     return aio_bh_new(qemu_aio_context, cb, opaque);
 }
 
+QEMUBH *qemu_bh_new_replay(QEMUBHFunc *cb, void *opaque, uint64_t id)
+{
+    return aio_bh_new_replay(qemu_aio_context, cb, opaque, id);
+}
+
 bool qemu_aio_wait(void)
 {
     return aio_poll(qemu_aio_context, true);
diff --git a/replay/replay-events.c b/replay/replay-events.c
index eda574e..81a5a6b 100755
--- a/replay/replay-events.c
+++ b/replay/replay-events.c
@@ -35,6 +35,9 @@ static bool replay_events_enabled = false;
 static void replay_run_event(Event *event)
 {
     switch (event->event_kind) {
+    case REPLAY_ASYNC_EVENT_BH:
+        aio_bh_call(event->opaque);
+        break;
     default:
         fprintf(stderr, "Replay: invalid async event ID (%d) in the queue\n", 
                 event->event_kind);
@@ -117,6 +120,11 @@ void replay_add_event(int event_kind, void *opaque)
     replay_add_event_internal(event_kind, opaque, NULL, 0);
 }
 
+void replay_add_bh_event(void *bh, uint64_t id)
+{
+    replay_add_event_internal(REPLAY_ASYNC_EVENT_BH, bh, NULL, id);
+}
+
 void replay_save_events(int opt)
 {
     qemu_mutex_lock(&lock);
@@ -134,6 +142,9 @@ void replay_save_events(int opt)
 
             /* save event-specific data */
             switch (event->event_kind) {
+            case REPLAY_ASYNC_EVENT_BH:
+                replay_put_qword(event->id);
+                break;
             }
         }
 
@@ -163,6 +174,11 @@ void replay_read_events(int opt)
             break;
         /* Execute some events without searching them in the queue */
         switch (read_event_kind) {
+        case REPLAY_ASYNC_EVENT_BH:
+            if (read_id == -1) {
+                read_id = replay_get_qword();
+            }
+            break;
         default:
             fprintf(stderr, "Unknown ID %d of replay event\n", read_event_kind);
             exit(1);
diff --git a/replay/replay-internal.h b/replay/replay-internal.h
index 95cbde6..bbb117e 100755
--- a/replay/replay-internal.h
+++ b/replay/replay-internal.h
@@ -39,7 +39,8 @@
 
 /* Asynchronous events IDs */
 
-#define REPLAY_ASYNC_COUNT             0
+#define REPLAY_ASYNC_EVENT_BH          0
+#define REPLAY_ASYNC_COUNT             1
 
 typedef struct ReplayState {
     /*! Cached clock values. */
diff --git a/replay/replay.h b/replay/replay.h
index 69a20af..3040b6b 100755
--- a/replay/replay.h
+++ b/replay/replay.h
@@ -98,5 +98,7 @@ int replay_checkpoint(unsigned int checkpoint);
 
 /*! Disables storing events in the queue */
 void replay_disable_events(void);
+/*! Adds BH event to the queue */
+void replay_add_bh_event(void *bh, uint64_t id);
 
 #endif
diff --git a/stubs/replay.c b/stubs/replay.c
index 1b0b78f..8a4d69e 100755
--- a/stubs/replay.c
+++ b/stubs/replay.c
@@ -27,3 +27,7 @@ int runstate_is_running(void)
 {
     return 0;
 }
+
+void replay_add_bh_event(void *bh, uint64_t id)
+{
+}
