mem: Allow inserts in the begining of a packet queue

A packet queue keeps track of packets that are scheduled to be sent at
a specified time. Packets are sorted such that the packet with the
earliest scheduled time is at the front of the list (unless there are
other ordering requirements). Previouly, the implemented algorithm
didn't allow packets to be placed at the front of the queue resulting
in uneccessary delays. This change fixes the implementation of
schedSendTiming.

Change-Id: Ic74abec7c3f4c12dbf67b5ab26a8d4232e18e19e
Signed-off-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Reviewed-on: https://gem5-review.googlesource.com/c/15556
Reviewed-by: Bradley Wang <radwang@ucdavis.edu>
Reviewed-by: Jason Lowe-Power <jason@lowepower.com>
Maintainer: Jason Lowe-Power <jason@lowepower.com>
diff --git a/src/mem/packet_queue.cc b/src/mem/packet_queue.cc
index 45378ae..282625a 100644
--- a/src/mem/packet_queue.cc
+++ b/src/mem/packet_queue.cc
@@ -123,13 +123,6 @@
               name());
     }
 
-    // nothing on the list
-    if (transmitList.empty()) {
-        transmitList.emplace_front(when, pkt);
-        schedSendEvent(when);
-        return;
-    }
-
     // we should either have an outstanding retry, or a send event
     // scheduled, but there is an unfortunate corner case where the
     // x86 page-table walker and timing CPU send out a new request as
@@ -142,15 +135,21 @@
     // order by tick; however, if forceOrder is set, also make sure
     // not to re-order in front of some existing packet with the same
     // address
-    auto i = transmitList.end();
-    --i;
-    while (i != transmitList.begin() && when < i->tick &&
-           !(forceOrder && i->pkt->getAddr() == pkt->getAddr()))
-        --i;
-
-    // emplace inserts the element before the position pointed to by
-    // the iterator, so advance it one step
-    transmitList.emplace(++i, when, pkt);
+    auto it = transmitList.end();
+    while (it != transmitList.begin()) {
+        --it;
+        if ((forceOrder && it->pkt->getAddr() == pkt->getAddr()) ||
+            it->tick <= when) {
+            // emplace inserts the element before the position pointed to by
+            // the iterator, so advance it one step
+            transmitList.emplace(++it, when, pkt);
+            return;
+        }
+    }
+    // either the packet list is empty or this has to be inserted
+    // before every other packet
+    transmitList.emplace_front(when, pkt);
+    schedSendEvent(when);
 }
 
 void