diff --git a/hw/scsi/megasas.c b/hw/scsi/megasas.c
index e6dc7ec..8e21ed5 100644
--- a/hw/scsi/megasas.c
+++ b/hw/scsi/megasas.c
@@ -114,7 +114,7 @@ typedef struct MegasasState {
     uint64_t producer_pa;
 
     MegasasCmd frames[MEGASAS_MAX_FRAMES];
-
+    DECLARE_BITMAP(frame_map, MEGASAS_MAX_FRAMES);
     SCSIBus bus;
 } MegasasState;
 
@@ -462,34 +462,20 @@ static MegasasCmd *megasas_lookup_frame(MegasasState *s,
     return cmd;
 }
 
-static MegasasCmd *megasas_next_frame(MegasasState *s,
-    hwaddr frame)
+static void megasas_unmap_frame(MegasasState *s, MegasasCmd *cmd)
 {
-    MegasasCmd *cmd = NULL;
-    int num = 0, index;
+    PCIDevice *p = PCI_DEVICE(s);
 
-    cmd = megasas_lookup_frame(s, frame);
-    if (cmd) {
-        trace_megasas_qf_found(cmd->index, cmd->pa);
-        return cmd;
-    }
-    index = s->reply_queue_head;
-    num = 0;
-    while (num < s->fw_cmds) {
-        if (!s->frames[index].pa) {
-            cmd = &s->frames[index];
-            break;
-        }
-        index = megasas_next_index(s, index, s->fw_cmds);
-        num++;
-    }
-    if (!cmd) {
-        trace_megasas_qf_failed(frame);
-    }
-    trace_megasas_qf_new(index, cmd);
-    return cmd;
+    pci_dma_unmap(p, cmd->frame, cmd->pa_size, 0, 0);
+    cmd->frame = NULL;
+    cmd->pa = 0;
+    clear_bit(cmd->index, s->frame_map);
 }
 
+/*
+ * This absolutely needs to be locked if
+ * qemu ever goes multithreaded.
+ */
 static MegasasCmd *megasas_enqueue_frame(MegasasState *s,
     hwaddr frame, uint64_t context, int count)
 {
@@ -497,31 +483,40 @@ static MegasasCmd *megasas_enqueue_frame(MegasasState *s,
     MegasasCmd *cmd = NULL;
     int frame_size = MFI_FRAME_SIZE * 16;
     hwaddr frame_size_p = frame_size;
+    unsigned long index;
 
-    cmd = megasas_next_frame(s, frame);
-    /* All frames busy */
-    if (!cmd) {
+    index = 0;
+    while (index < s->fw_cmds) {
+        index = find_next_zero_bit(s->frame_map, s->fw_cmds, index);
+        if (!s->frames[index].pa)
+            break;
+        /* Busy frame found */
+        trace_megasas_qf_mapped(index);
+    }
+    if (index >= s->fw_cmds) {
+        /* All frames busy */
+        trace_megasas_qf_busy(frame);
         return NULL;
     }
-    if (!cmd->pa) {
-        cmd->pa = frame;
-        /* Map all possible frames */
-        cmd->frame = pci_dma_map(pcid, frame, &frame_size_p, 0);
-        if (frame_size_p != frame_size) {
-            trace_megasas_qf_map_failed(cmd->index, (unsigned long)frame);
-            if (cmd->frame) {
-                pci_dma_unmap(pcid, cmd->frame, frame_size_p, 0, 0);
-                cmd->frame = NULL;
-                cmd->pa = 0;
-            }
-            s->event_count++;
-            return NULL;
-        }
-        cmd->pa_size = frame_size_p;
-        cmd->context = context;
-        if (!megasas_use_queue64(s)) {
-            cmd->context &= (uint64_t)0xFFFFFFFF;
+    cmd = &s->frames[index];
+    set_bit(index, s->frame_map);
+    trace_megasas_qf_new(index, frame);
+
+    cmd->pa = frame;
+    /* Map all possible frames */
+    cmd->frame = pci_dma_map(pcid, frame, &frame_size_p, 0);
+    if (frame_size_p != frame_size) {
+        trace_megasas_qf_map_failed(cmd->index, (unsigned long)frame);
+        if (cmd->frame) {
+            megasas_unmap_frame(s, cmd);
         }
+        s->event_count++;
+        return NULL;
+    }
+    cmd->pa_size = frame_size_p;
+    cmd->context = context;
+    if (!megasas_use_queue64(s)) {
+        cmd->context &= (uint64_t)0xFFFFFFFF;
     }
     cmd->count = count;
     s->busy++;
@@ -543,7 +538,6 @@ static void megasas_complete_frame(MegasasState *s, uint64_t context)
 
     /* Decrement busy count */
     s->busy--;
-
     if (s->reply_queue_pa) {
         /*
          * Put command on the reply queue.
@@ -589,18 +583,16 @@ static void megasas_complete_frame(MegasasState *s, uint64_t context)
 
 static void megasas_reset_frames(MegasasState *s)
 {
-    PCIDevice *pcid = PCI_DEVICE(s);
     int i;
     MegasasCmd *cmd;
 
     for (i = 0; i < s->fw_cmds; i++) {
         cmd = &s->frames[i];
         if (cmd->pa) {
-            pci_dma_unmap(pcid, cmd->frame, cmd->pa_size, 0, 0);
-            cmd->frame = NULL;
-            cmd->pa = 0;
+            megasas_unmap_frame(s, cmd);
         }
     }
+    bitmap_zero(s->frame_map, MEGASAS_MAX_FRAMES);
 }
 
 static void megasas_abort_command(MegasasCmd *cmd)
@@ -1897,6 +1889,7 @@ static void megasas_command_complete(SCSIRequest *req, uint32_t status,
         cmd->req = NULL;
     }
     cmd->frame->header.cmd_status = cmd_status;
+    megasas_unmap_frame(cmd->state, cmd);
     megasas_complete_frame(cmd->state, cmd->context);
 }
 
@@ -2000,6 +1993,7 @@ static void megasas_handle_frame(MegasasState *s, uint64_t frame_addr,
         } else {
             megasas_frame_set_cmd_status(frame_addr, frame_status);
         }
+        megasas_unmap_frame(s, cmd);
         megasas_complete_frame(s, cmd->context);
     }
 }
diff --git a/trace-events b/trace-events
index 9c75501..8bf133b 100644
--- a/trace-events
+++ b/trace-events
@@ -699,9 +699,9 @@ megasas_init_queue(uint64_t queue_pa, int queue_len, uint64_t head, uint64_t tai
 megasas_initq_map_failed(int frame) "scmd %d: failed to map queue"
 megasas_initq_mapped(uint64_t pa) "queue already mapped at %" PRIx64 ""
 megasas_initq_mismatch(int queue_len, int fw_cmds) "queue size %d max fw cmds %d"
-megasas_qf_found(unsigned int index, uint64_t pa) "mapped frame %x pa %" PRIx64 ""
-megasas_qf_new(unsigned int index, void *cmd) "return new frame %x cmd %p"
-megasas_qf_failed(unsigned long pa) "all frames busy for frame %lx"
+megasas_qf_mapped(unsigned int index) "skip mapped frame %x"
+megasas_qf_new(unsigned int index, uint64_t frame) "frame %x addr %" PRIx64 ""
+megasas_qf_busy(unsigned long pa) "all frames busy for frame %lx"
 megasas_qf_enqueue(unsigned int index, unsigned int count, uint64_t context, unsigned int head, unsigned int tail, int busy) "frame %x count %d context %" PRIx64 " head %x tail %x busy %d"
 megasas_qf_update(unsigned int head, unsigned int tail, unsigned int busy) "head %x tail %x busy %d"
 megasas_qf_map_failed(int cmd, unsigned long frame) "scmd %d: frame %lu"
