--- a/netwerk/protocol/http/ASpdySession.cpp
+++ b/netwerk/protocol/http/ASpdySession.cpp
@@ -118,11 +118,26 @@ SpdyPushCache::RemovePushedStreamHttp2(c
   Http2PushedStream *rv = mHashHttp2.Get(key);
   LOG3(("SpdyPushCache::RemovePushedStreamHttp2 %s 0x%X\n",
         key.get(), rv ? rv->StreamID() : 0));
   if (rv)
     mHashHttp2.Remove(key);
   return rv;
 }
 
+Http2PushedStream *
+SpdyPushCache::RemovePushedStreamHttp2ByID(const nsCString& key, const uint32_t& streamID)
+{
+  Http2PushedStream *rv = mHashHttp2.Get(key);
+  LOG3(("SpdyPushCache::RemovePushedStreamHttp2ByID %s 0x%X 0x%X",
+        key.get(), rv ? rv->StreamID() : 0, streamID));
+  if (rv && streamID == rv->StreamID()) {
+    mHashHttp2.Remove(key);
+  } else {
+    // Ensure we overwrite our rv with null in case the stream IDs don't match
+    rv = nullptr;
+  }
+  return rv;
+}
+
 } // namespace net
 } // namespace mozilla
 

--- a/netwerk/protocol/http/Http2Session.cpp
+++ b/netwerk/protocol/http/Http2Session.cpp
@@ -1100,17 +1100,19 @@ Http2Session::CleanupStream(Http2Stream 
       nsAutoCString hashKey;
       DebugOnly<bool> rv = pushStream->GetHashKey(hashKey);
       MOZ_ASSERT(rv);
       nsIRequestContext *requestContext = aStream->RequestContext();
       if (requestContext) {
         SpdyPushCache *cache = nullptr;
         requestContext->GetSpdyPushCache(&cache);
         if (cache) {
-          Http2PushedStream *trash = cache->RemovePushedStreamHttp2(hashKey);
+          // Make sure the id of the stream in the push cache is the same
+          // as the id of the stream we're cleaning up! See bug 1368080.
+          Http2PushedStream *trash = cache->RemovePushedStreamHttp2ByID(hashKey, aStream->StreamID());
           LOG3(("Http2Session::CleanupStream %p aStream=%p pushStream=%p trash=%p",
                 this, aStream, pushStream, trash));
         }
       }
     }
   }
 
   RemoveStreamFromQueues(aStream);

--- a/netwerk/protocol/http/PSpdyPush.h
+++ b/netwerk/protocol/http/PSpdyPush.h
@@ -41,16 +41,17 @@ class SpdyPushCache
 {
 public:
   // The cache holds only weak pointers - no references
   SpdyPushCache();
   virtual ~SpdyPushCache();
   MOZ_MUST_USE bool  RegisterPushedStreamHttp2(const nsCString& key,
                                                Http2PushedStream *stream);
   Http2PushedStream *RemovePushedStreamHttp2(const nsCString& key);
+  Http2PushedStream *RemovePushedStreamHttp2ByID(const nsCString& key, const uint32_t& streamID);
 private:
   nsDataHashtable<nsCStringHashKey, Http2PushedStream *> mHashHttp2;
 };
 
 } // namespace net
 } // namespace mozilla
 
 #endif // mozilla_net_SpdyPush_Public_h

--- a/netwerk/test/unit/test_http2.js
+++ b/netwerk/test/unit/test_http2.js
@@ -964,16 +964,55 @@ function test_complete() {
   httpserv.stop(do_test_finished);
   do_test_pending();
   httpserv2.stop(do_test_finished);
 
   do_test_finished();
   do_timeout(0,run_next_test);
 }
 
+var Http2DoublepushListener = function () {};
+Http2DoublepushListener.prototype = new Http2CheckListener();
+Http2DoublepushListener.prototype.onStopRequest = function (request, ctx, status) {
+  do_check_true(this.onStartRequestFired);
+  do_check_true(Components.isSuccessCode(status));
+  do_check_true(this.onDataAvailableFired);
+  do_check_true(this.isHttp2Connection == this.shouldBeHttp2);
+
+  var chan = makeChan("https://localhost:" + serverPort + "/doublypushed");
+  var listener = new Http2DoublypushedListener();
+  chan.loadGroup = loadGroup;
+  chan.asyncOpen2(listener);
+};
+
+var Http2DoublypushedListener = function () {};
+Http2DoublypushedListener.prototype = new Http2CheckListener();
+Http2DoublypushedListener.prototype.readData = "";
+Http2DoublypushedListener.prototype.onDataAvailable = function (request, ctx, stream, off, cnt) {
+  this.onDataAvailableFired = true;
+  this.accum += cnt;
+  this.readData += read_stream(stream, cnt);
+};
+Http2DoublypushedListener.prototype.onStopRequest = function (request, ctx, status) {
+  do_check_true(this.onStartRequestFired);
+  do_check_true(Components.isSuccessCode(status));
+  do_check_true(this.onDataAvailableFired);
+  do_check_eq(this.readData, "pushed");
+
+  run_next_test();
+  do_test_finished();
+};
+
+function test_http2_doublepush() {
+  var chan = makeChan("https://localhost:" + serverPort + "/doublepush");
+  var listener = new Http2DoublepushListener();
+  chan.loadGroup = loadGroup;
+  chan.asyncOpen2(listener);
+}
+
 // hack - the header test resets the multiplex object on the server,
 // so make sure header is always run before the multiplex test.
 //
 // make sure post_big runs first to test race condition in restarting
 // a stalled stream when a SETTINGS frame arrives
 var tests = [ test_http2_post_big
             , test_http2_basic
             , test_http2_concurrent
@@ -999,16 +1038,17 @@ var tests = [ test_http2_post_big
             , test_http2_pushapi_1
             , test_http2_continuations
             , test_http2_blocking_download
             , test_http2_illegalhpacksoft
             , test_http2_illegalhpackhard
             , test_http2_folded_header
             , test_http2_empty_data
             , test_http2_status_phrase
+            , test_http2_doublepush
             // Add new tests above here - best to add new tests before h1
             // streams get too involved
             // These next two must always come in this order
             , test_http2_h11required_stream
             , test_http2_h11required_session
             , test_http2_retry_rst
             , test_http2_wrongsuite
             , test_http2_push_firstparty1

--- a/testing/xpcshell/moz-http2/moz-http2.js
+++ b/testing/xpcshell/moz-http2/moz-http2.js
@@ -802,16 +802,40 @@ function handleRequest(req, res) {
   else if (u.pathname === "/statusphrase") {
     // Fortunately, the node-http2 API is dumb enough to allow this right on
     // through, so we can easily test rejecting this on gecko's end.
     res.writeHead("200 OK");
     res.end(content);
     return;
   }
 
+  else if (u.pathname === "/doublepush") {
+    push1 = res.push('/doublypushed');
+    push1.writeHead(200, {
+      'content-type': 'text/plain',
+      'pushed' : 'yes',
+      'content-length' : 6,
+      'X-Connection-Http2': 'yes'
+    });
+    push1.end('pushed');
+
+    push2 = res.push('/doublypushed');
+    push2.writeHead(200, {
+      'content-type': 'text/plain',
+      'pushed' : 'yes',
+      'content-length' : 6,
+      'X-Connection-Http2': 'yes'
+    });
+    push2.end('pushed');
+  }
+
+  else if (u.pathname === "/doublypushed") {
+    content = 'not pushed';
+  }
+
   res.setHeader('Content-Type', 'text/html');
   if (req.httpVersionMajor != 2) {
     res.setHeader('Connection', 'close');
   }
   res.writeHead(200);
   res.end(content);
 }