--- a/dom/media/eme/CDMCaps.cpp
+++ b/dom/media/eme/CDMCaps.cpp
@@ -3,16 +3,17 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
  * You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "CDMCaps.h"
 #include "gmp-decryption.h"
 #include "EMELog.h"
 #include "nsThreadUtils.h"
+#include "SamplesWaitingForKey.h"
 
 namespace mozilla {
 
 CDMCaps::CDMCaps()
   : mMonitor("CDMCaps")
   , mCaps(0)
 {
 }
@@ -98,22 +99,17 @@ CDMCaps::AutoLock::SetKeyUsable(const Ce
     return false;
   }
   mData.mUsableKeyIds.AppendElement(key);
   auto& waiters = mData.mWaitForKeys;
   size_t i = 0;
   while (i < waiters.Length()) {
     auto& w = waiters[i];
     if (w.mKeyId == aKeyId) {
-      if (waiters[i].mTarget) {
-        EME_LOG("SetKeyUsable() notified waiter.");
-        w.mTarget->Dispatch(w.mContinuation, NS_DISPATCH_NORMAL);
-      } else {
-        w.mContinuation->Run();
-      }
+      w.mListener->NotifyUsable(aKeyId);
       waiters.RemoveElementAt(i);
     } else {
       i++;
     }
   }
   return true;
 }
 
@@ -133,24 +129,23 @@ CDMCaps::AutoLock::SetKeyUnusable(const 
       keys.RemoveElementAt(i);
       break;
     }
   }
   return true;
 }
 
 void
-CDMCaps::AutoLock::CallWhenKeyUsable(const CencKeyId& aKey,
-                                     nsIRunnable* aContinuation,
-                                     nsIThread* aTarget)
+CDMCaps::AutoLock::NotifyWhenKeyIdUsable(const CencKeyId& aKey,
+                                         SamplesWaitingForKey* aListener)
 {
   mData.mMonitor.AssertCurrentThreadOwns();
   MOZ_ASSERT(!IsKeyUsable(aKey));
-  MOZ_ASSERT(aContinuation);
-  mData.mWaitForKeys.AppendElement(WaitForKeys(aKey, aContinuation, aTarget));
+  MOZ_ASSERT(aListener);
+  mData.mWaitForKeys.AppendElement(WaitForKeys(aKey, aListener));
 }
 
 bool
 CDMCaps::AutoLock::AreCapsKnown()
 {
   mData.mMonitor.AssertCurrentThreadOwns();
   return mData.mCaps != 0;
 }

--- a/dom/media/eme/CDMCaps.h
+++ b/dom/media/eme/CDMCaps.h
@@ -8,21 +8,20 @@
 #define CDMCaps_h_
 
 #include "nsString.h"
 #include "nsAutoPtr.h"
 #include "mozilla/Monitor.h"
 #include "nsIThread.h"
 #include "nsTArray.h"
 #include "mozilla/Attributes.h"
+#include "SamplesWaitingForKey.h"
 
 namespace mozilla {
 
-typedef nsTArray<uint8_t> CencKeyId;
-
 // CDM capabilities; what keys a CDMProxy can use, and whether it can decrypt, or
 // decrypt-and-decode on a per stream basis. Must be locked to access state.
 class CDMCaps {
 public:
   CDMCaps();
   ~CDMCaps();
 
   // Locks the CDMCaps. It must be locked to access its shared state.
@@ -56,44 +55,37 @@ public:
     bool CanDecryptAndDecodeAudio();
     bool CanDecryptAndDecodeVideo();
 
     bool CanDecryptAudio();
     bool CanDecryptVideo();
 
     void CallOnMainThreadWhenCapsAvailable(nsIRunnable* aContinuation);
 
-    // Calls aContinuation on aTarget thread when key become usable.
-    // Pass aTarget=nullptr and runnable will be called on the GMP thread
-    // when key becomes usable.
-    void CallWhenKeyUsable(const CencKeyId& aKey,
-                           nsIRunnable* aContinuation,
-                           nsIThread* aTarget = nullptr);
-
+    // Notifies the SamplesWaitingForKey when key become usable.
+    void NotifyWhenKeyIdUsable(const CencKeyId& aKey,
+                               SamplesWaitingForKey* aSamplesWaiting);
   private:
     // Not taking a strong ref, since this should be allocated on the stack.
     CDMCaps& mData;
   };
 
 private:
   void Lock();
   void Unlock();
   bool HasCap(uint64_t);
 
   struct WaitForKeys {
     WaitForKeys(const CencKeyId& aKeyId,
-                nsIRunnable* aContinuation,
-                nsIThread* aTarget)
+                SamplesWaitingForKey* aListener)
       : mKeyId(aKeyId)
-      , mContinuation(aContinuation)
-      , mTarget(aTarget)
+      , mListener(aListener)
     {}
     CencKeyId mKeyId;
-    nsRefPtr<nsIRunnable> mContinuation;
-    nsCOMPtr<nsIThread> mTarget;
+    nsRefPtr<SamplesWaitingForKey> mListener;
   };
 
   Monitor mMonitor;
 
   struct UsableKey {
     UsableKey(const CencKeyId& aId,
               const nsString& aSessionId)
       : mId(aId)

--- a/dom/media/eme/CDMProxy.cpp
+++ b/dom/media/eme/CDMProxy.cpp
@@ -331,17 +331,17 @@ CDMProxy::Shutdown()
 void
 CDMProxy::gmp_Shutdown()
 {
   MOZ_ASSERT(IsOnGMPThread());
 
   // Abort any pending decrypt jobs, to awaken any clients waiting on a job.
   for (size_t i = 0; i < mDecryptionJobs.Length(); i++) {
     DecryptJob* job = mDecryptionJobs[i];
-    job->mClient->Decrypted(NS_ERROR_ABORT, nullptr);
+    job->mClient->Decrypted(GMPAbortedErr, nullptr);
   }
   mDecryptionJobs.Clear();
 
   if (mCDM) {
     mCDM->Close();
     mCDM = nullptr;
   }
 }
@@ -517,17 +517,17 @@ CDMProxy::Decrypt(mp4_demuxer::MP4Sample
 void
 CDMProxy::gmp_Decrypt(nsAutoPtr<DecryptJob> aJob)
 {
   MOZ_ASSERT(IsOnGMPThread());
   MOZ_ASSERT(aJob->mClient);
   MOZ_ASSERT(aJob->mSample);
 
   if (!mCDM) {
-    aJob->mClient->Decrypted(NS_ERROR_FAILURE, nullptr);
+    aJob->mClient->Decrypted(GMPAbortedErr, nullptr);
     return;
   }
 
   aJob->mId = ++mDecryptionJobCount;
   nsTArray<uint8_t> data;
   data.AppendElements(aJob->mSample->data, aJob->mSample->size);
   mCDM->Decrypt(aJob->mId, aJob->mSample->crypto, data);
   mDecryptionJobs.AppendElement(aJob.forget());
@@ -544,29 +544,36 @@ CDMProxy::gmp_Decrypted(uint32_t aId,
     if (job->mId == aId) {
       if (aDecryptedData.Length() != job->mSample->size) {
         NS_WARNING("CDM returned incorrect number of decrypted bytes");
       }
       if (GMP_SUCCEEDED(aResult)) {
         PodCopy(job->mSample->data,
                 aDecryptedData.Elements(),
                 std::min<size_t>(aDecryptedData.Length(), job->mSample->size));
-        job->mClient->Decrypted(NS_OK, job->mSample.forget());
+        job->mClient->Decrypted(GMPNoErr, job->mSample.forget());
+      } else if (aResult == GMPNoKeyErr) {
+        NS_WARNING("CDM returned GMPNoKeyErr");
+        // We still have the encrypted sample, so we can re-enqueue it to be
+        // decrypted again once the key is usable again.
+        job->mClient->Decrypted(GMPNoKeyErr, job->mSample.forget());
       } else {
-        job->mClient->Decrypted(NS_ERROR_FAILURE, nullptr);
+        nsAutoCString str("CDM returned decode failure GMPErr=");
+        str.AppendInt(aResult);
+        NS_WARNING(str.get());
+        job->mClient->Decrypted(aResult, nullptr);
       }
       mDecryptionJobs.RemoveElementAt(i);
       return;
-    } else {
-      NS_WARNING("GMPDecryptorChild returned incorrect job ID");
     }
   }
+  NS_WARNING("GMPDecryptorChild returned incorrect job ID");
 }
 
 void
 CDMProxy::gmp_Terminated()
 {
   MOZ_ASSERT(IsOnGMPThread());
-  EME_LOG("CDM terminated");
+  NS_WARNING("CDM terminated");
   gmp_Shutdown();
 }
 
 } // namespace mozilla

--- a/dom/media/eme/CDMProxy.h
+++ b/dom/media/eme/CDMProxy.h
@@ -22,17 +22,17 @@ class CDMCallbackProxy;
 
 namespace dom {
 class MediaKeySession;
 }
 
 class DecryptionClient {
 public:
   virtual ~DecryptionClient() {}
-  virtual void Decrypted(nsresult aResult,
+  virtual void Decrypted(GMPErr aResult,
                          mp4_demuxer::MP4Sample* aSample) = 0;
 };
 
 // Proxies calls GMP/CDM, and proxies calls back.
 // Note: Promises are passed in via a PromiseId, so that the ID can be
 // passed via IPC to the CDM, which can then signal when to reject or
 // resolve the promise using its PromiseId.
 class CDMProxy {

--- a/dom/media/fmp4/eme/EMEAudioDecoder.cpp
+++ b/dom/media/fmp4/eme/EMEAudioDecoder.cpp
@@ -29,29 +29,34 @@ EMEAudioDecoder::EMEAudioDecoder(CDMProx
   , mAudioFrameSum(0)
   , mAudioFrameOffset(0)
   , mStreamOffset(0)
   , mProxy(aProxy)
   , mGMP(nullptr)
   , mConfig(aConfig)
   , mTaskQueue(aTaskQueue)
   , mCallback(aCallback)
+  , mSamplesWaitingForKey(new SamplesWaitingForKey(this, mTaskQueue, mProxy))
   , mMonitor("EMEAudioDecoder")
   , mFlushComplete(false)
+#ifdef DEBUG
+  , mIsShutdown(false)
+#endif
 {
 }
 
 EMEAudioDecoder::~EMEAudioDecoder()
 {
 }
 
 nsresult
 EMEAudioDecoder::Init()
 {
   // Note: this runs on the decode task queue.
+  MOZ_ASSERT(!mIsShutdown);
 
   MOZ_ASSERT((mConfig.bits_per_sample / 8) == 2); // Demuxer guarantees this.
 
   mMPS = do_GetService("@mozilla.org/gecko-media-plugin-service;1");
   MOZ_ASSERT(mMPS);
 
   nsresult rv = mMPS->GetThread(getter_AddRefs(mGMPThread));
   NS_ENSURE_SUCCESS(rv, rv);
@@ -63,28 +68,34 @@ EMEAudioDecoder::Init()
 
   return NS_OK;
 }
 
 nsresult
 EMEAudioDecoder::Input(MP4Sample* aSample)
 {
   MOZ_ASSERT(!IsOnGMPThread()); // Runs on the decode task queue.
+  MOZ_ASSERT(!mIsShutdown);
+
+  if (mSamplesWaitingForKey->WaitIfKeyNotUsable(aSample)) {
+    return NS_OK;
+  }
 
   nsRefPtr<nsIRunnable> task(new DeliverSample(this, aSample));
   nsresult rv = mGMPThread->Dispatch(task, NS_DISPATCH_NORMAL);
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 nsresult
 EMEAudioDecoder::Flush()
 {
   MOZ_ASSERT(!IsOnGMPThread()); // Runs on the decode task queue.
+  MOZ_ASSERT(!mIsShutdown);
 
   {
     MonitorAutoLock mon(mMonitor);
     mFlushComplete = false;
   }
 
   nsRefPtr<nsIRunnable> task;
   task = NS_NewRunnableMethod(this, &EMEAudioDecoder::GmpFlush);
@@ -100,33 +111,42 @@ EMEAudioDecoder::Flush()
 
   return NS_OK;
 }
 
 nsresult
 EMEAudioDecoder::Drain()
 {
   MOZ_ASSERT(!IsOnGMPThread()); // Runs on the decode task queue.
+  MOZ_ASSERT(!mIsShutdown);
 
   nsRefPtr<nsIRunnable> task;
   task = NS_NewRunnableMethod(this, &EMEAudioDecoder::GmpDrain);
   nsresult rv = mGMPThread->Dispatch(task, NS_DISPATCH_NORMAL);
   NS_ENSURE_SUCCESS(rv, rv);
   return NS_OK;
 }
 
 nsresult
 EMEAudioDecoder::Shutdown()
 {
   MOZ_ASSERT(!IsOnGMPThread()); // Runs on the decode task queue.
+  MOZ_ASSERT(!mIsShutdown);
+#ifdef DEBUG
+  mIsShutdown = true;
+#endif
 
   nsRefPtr<nsIRunnable> task;
   task = NS_NewRunnableMethod(this, &EMEAudioDecoder::GmpShutdown);
   nsresult rv = mGMPThread->Dispatch(task, NS_DISPATCH_SYNC);
   NS_ENSURE_SUCCESS(rv, rv);
+
+  mSamplesWaitingForKey->BreakCycles();
+  mSamplesWaitingForKey = nullptr;
+
   return NS_OK;
 }
 
 void
 EMEAudioDecoder::Decoded(const nsTArray<int16_t>& aPCM,
                          uint64_t aTimeStamp,
                          uint32_t aChannels,
                          uint32_t aRate)
@@ -216,19 +236,25 @@ EMEAudioDecoder::ResetComplete()
     mon.NotifyAll();
   }
 }
 
 void
 EMEAudioDecoder::Error(GMPErr aErr)
 {
   MOZ_ASSERT(IsOnGMPThread());
-  EME_LOG("EMEAudioDecoder::Error");
-  mCallback->Error();
-  GmpShutdown();
+  EME_LOG("EMEAudioDecoder::Error %d", aErr);
+  if (aErr == GMPNoKeyErr) {
+    // The GMP failed to decrypt a frame due to not having a key. This can
+    // happen if a key expires or a session is closed during playback.
+    NS_WARNING("GMP failed to decrypt due to lack of key");
+  } else {
+    mCallback->Error();
+    GmpShutdown();
+  }
 }
 
 void
 EMEAudioDecoder::Terminated()
 {
   MOZ_ASSERT(IsOnGMPThread());
   GmpShutdown();
 }
@@ -270,28 +296,16 @@ EMEAudioDecoder::GmpInput(MP4Sample* aSa
 {
   MOZ_ASSERT(IsOnGMPThread());
   nsAutoPtr<MP4Sample> sample(aSample);
   if (!mGMP) {
     mCallback->Error();
     return NS_ERROR_FAILURE;
   }
 
-  if (sample->crypto.valid) {
-    CDMCaps::AutoLock caps(mProxy->Capabilites());
-    MOZ_ASSERT(caps.CanDecryptAndDecodeAudio());
-    const auto& keyid = sample->crypto.key;
-    if (!caps.IsKeyUsable(keyid)) {
-      // DeliverSample assumes responsibility for deleting aSample.
-      nsRefPtr<nsIRunnable> task(new DeliverSample(this, sample.forget()));
-      caps.CallWhenKeyUsable(keyid, task, mGMPThread);
-      return NS_OK;
-    }
-  }
-
   gmp::GMPAudioSamplesImpl samples(sample, mAudioChannels, mAudioRate);
   mGMP->Decode(samples);
 
   mStreamOffset = sample->byte_offset;
 
   return NS_OK;
 }
 

--- a/dom/media/fmp4/eme/EMEAudioDecoder.h
+++ b/dom/media/fmp4/eme/EMEAudioDecoder.h
@@ -8,16 +8,17 @@
 #define EMEAACDecoder_h_
 
 #include "PlatformDecoderModule.h"
 #include "mp4_demuxer/DecoderData.h"
 #include "mozIGeckoMediaPluginService.h"
 #include "nsServiceManagerUtils.h"
 #include "GMPAudioHost.h"
 #include "GMPAudioDecoderProxy.h"
+#include "SamplesWaitingForKey.h"
 
 namespace mozilla {
 
 class EMEAudioDecoder : public MediaDataDecoder
                       , public GMPAudioDecoderProxyCallback
 {
   typedef mp4_demuxer::MP4Sample MP4Sample;
   typedef mp4_demuxer::AudioDecoderConfig AudioDecoderConfig;
@@ -103,15 +104,21 @@ private:
   nsCOMPtr<nsIThread> mGMPThread;
   nsRefPtr<CDMProxy> mProxy;
   GMPAudioDecoderProxy* mGMP;
 
   const mp4_demuxer::AudioDecoderConfig& mConfig;
   nsRefPtr<MediaTaskQueue> mTaskQueue;
   MediaDataDecoderCallback* mCallback;
 
+  nsRefPtr<SamplesWaitingForKey> mSamplesWaitingForKey;
+
   Monitor mMonitor;
   bool mFlushComplete;
+
+#ifdef DEBUG
+  bool mIsShutdown;
+#endif
 };
 
 } // namespace mozilla
 
 #endif

--- a/dom/media/fmp4/eme/EMEDecoderModule.cpp
+++ b/dom/media/fmp4/eme/EMEDecoderModule.cpp
@@ -16,165 +16,158 @@
 #include "mozilla/CDMProxy.h"
 #include "mozilla/EMELog.h"
 #include "MediaTaskQueue.h"
 #include "SharedThreadPool.h"
 #include "mozilla/EMELog.h"
 #include "EMEH264Decoder.h"
 #include "EMEAudioDecoder.h"
 #include "mozilla/unused.h"
+#include "SamplesWaitingForKey.h"
 #include <string>
 
 namespace mozilla {
 
 class EMEDecryptor : public MediaDataDecoder {
   typedef mp4_demuxer::MP4Sample MP4Sample;
 
 public:
 
   EMEDecryptor(MediaDataDecoder* aDecoder,
                MediaDataDecoderCallback* aCallback,
                CDMProxy* aProxy)
     : mDecoder(aDecoder)
     , mCallback(aCallback)
     , mTaskQueue(CreateMediaDecodeTaskQueue())
     , mProxy(aProxy)
+    , mSamplesWaitingForKey(new SamplesWaitingForKey(this, mTaskQueue, mProxy))
+#ifdef DEBUG
+    , mIsShutdown(false)
+#endif
   {
   }
 
   virtual nsresult Init() MOZ_OVERRIDE {
+    MOZ_ASSERT(!mIsShutdown);
     nsresult rv = mTaskQueue->SyncDispatch(
       NS_NewRunnableMethod(mDecoder, &MediaDataDecoder::Init));
     unused << NS_WARN_IF(NS_FAILED(rv));
     return rv;
   }
 
-  class RedeliverEncryptedInput : public nsRunnable {
-  public:
-    RedeliverEncryptedInput(EMEDecryptor* aDecryptor,
-                            MediaTaskQueue* aTaskQueue,
-                            MP4Sample* aSample)
-      : mDecryptor(aDecryptor)
-      , mTaskQueue(aTaskQueue)
-      , mSample(aSample)
-    {}
-
-    NS_IMETHOD Run() {
-      RefPtr<nsIRunnable> task;
-      task = NS_NewRunnableMethodWithArg<MP4Sample*>(mDecryptor,
-                                                     &EMEDecryptor::Input,
-                                                     mSample.forget());
-      mTaskQueue->Dispatch(task.forget());
-      mTaskQueue = nullptr;
-      mDecryptor = nullptr;
-      return NS_OK;
-    }
-
-  private:
-    nsRefPtr<EMEDecryptor> mDecryptor;
-    nsRefPtr<MediaTaskQueue> mTaskQueue;
-    nsAutoPtr<MP4Sample> mSample;
-  };
-
   class DeliverDecrypted : public DecryptionClient {
   public:
     DeliverDecrypted(EMEDecryptor* aDecryptor, MediaTaskQueue* aTaskQueue)
       : mDecryptor(aDecryptor)
       , mTaskQueue(aTaskQueue)
     {}
-    virtual void Decrypted(nsresult aResult,
+    virtual void Decrypted(GMPErr aResult,
                            mp4_demuxer::MP4Sample* aSample) MOZ_OVERRIDE {
-      if (NS_FAILED(aResult)) {
+      if (aResult == GMPNoKeyErr) {
+        RefPtr<nsIRunnable> task;
+        task = NS_NewRunnableMethodWithArg<MP4Sample*>(mDecryptor,
+                                                       &EMEDecryptor::Input,
+                                                       aSample);
+        mTaskQueue->Dispatch(task.forget());
+      } else if (GMP_FAILED(aResult)) {
         mDecryptor->mCallback->Error();
         MOZ_ASSERT(!aSample);
       } else {
         RefPtr<nsIRunnable> task;
         task = NS_NewRunnableMethodWithArg<MP4Sample*>(mDecryptor,
                                                        &EMEDecryptor::Decrypted,
                                                        aSample);
         mTaskQueue->Dispatch(task.forget());
-        mTaskQueue = nullptr;
-        mDecryptor = nullptr;
       }
+      mTaskQueue = nullptr;
+      mDecryptor = nullptr;
     }
   private:
     nsRefPtr<EMEDecryptor> mDecryptor;
     nsRefPtr<MediaTaskQueue> mTaskQueue;
   };
 
   virtual nsresult Input(MP4Sample* aSample) MOZ_OVERRIDE {
+    MOZ_ASSERT(!mIsShutdown);
     // We run the PDM on its own task queue. We can't run it on the decode
     // task queue, because that calls into Input() in a loop and waits until
     // output is delivered. We need to defer some Input() calls while we wait
     // for keys to become usable, and once they do we need to dispatch an event
     // to run the PDM on the same task queue, but since the decode task queue
     // is waiting in MP4Reader::Decode() for output our task would never run.
     // So we dispatch tasks to make all calls into the wrapped decoder.
-    {
-      CDMCaps::AutoLock caps(mProxy->Capabilites());
-      if (!caps.IsKeyUsable(aSample->crypto.key)) {
-        EME_LOG("Encountered a non-usable key, waiting");
-        nsRefPtr<nsIRunnable> task(new RedeliverEncryptedInput(this,
-                                                               mTaskQueue,
-                                                               aSample));
-        caps.CallWhenKeyUsable(aSample->crypto.key, task);
-        return NS_OK;
-      }
+    if (mSamplesWaitingForKey->WaitIfKeyNotUsable(aSample)) {
+      return NS_OK;
     }
+
     mProxy->Decrypt(aSample, new DeliverDecrypted(this, mTaskQueue));
     return NS_OK;
   }
 
   void Decrypted(mp4_demuxer::MP4Sample* aSample) {
+    MOZ_ASSERT(!mIsShutdown);
     nsresult rv = mTaskQueue->Dispatch(
       NS_NewRunnableMethodWithArg<mp4_demuxer::MP4Sample*>(
         mDecoder,
         &MediaDataDecoder::Input,
         aSample));
     unused << NS_WARN_IF(NS_FAILED(rv));
   }
 
   virtual nsresult Flush() MOZ_OVERRIDE {
+    MOZ_ASSERT(!mIsShutdown);
     nsresult rv = mTaskQueue->SyncDispatch(
       NS_NewRunnableMethod(
         mDecoder,
         &MediaDataDecoder::Flush));
     unused << NS_WARN_IF(NS_FAILED(rv));
+    mSamplesWaitingForKey->Flush();
     return rv;
   }
 
   virtual nsresult Drain() MOZ_OVERRIDE {
+    MOZ_ASSERT(!mIsShutdown);
     nsresult rv = mTaskQueue->Dispatch(
       NS_NewRunnableMethod(
         mDecoder,
         &MediaDataDecoder::Drain));
     unused << NS_WARN_IF(NS_FAILED(rv));
     return rv;
   }
 
   virtual nsresult Shutdown() MOZ_OVERRIDE {
+    MOZ_ASSERT(!mIsShutdown);
+#ifdef DEBUG
+    mIsShutdown = true;
+#endif
     nsresult rv = mTaskQueue->SyncDispatch(
       NS_NewRunnableMethod(
         mDecoder,
         &MediaDataDecoder::Shutdown));
     unused << NS_WARN_IF(NS_FAILED(rv));
+    mSamplesWaitingForKey->BreakCycles();
+    mSamplesWaitingForKey = nullptr;
     mDecoder = nullptr;
     mTaskQueue->BeginShutdown();
     mTaskQueue->AwaitShutdownAndIdle();
     mTaskQueue = nullptr;
     mProxy = nullptr;
     return rv;
   }
 
 private:
 
   nsRefPtr<MediaDataDecoder> mDecoder;
   MediaDataDecoderCallback* mCallback;
   nsRefPtr<MediaTaskQueue> mTaskQueue;
   nsRefPtr<CDMProxy> mProxy;
+  nsRefPtr<SamplesWaitingForKey> mSamplesWaitingForKey;
+#ifdef DEBUG
+  bool mIsShutdown;
+#endif
 };
 
 EMEDecoderModule::EMEDecoderModule(CDMProxy* aProxy,
                                    PlatformDecoderModule* aPDM,
                                    bool aCDMDecodesAudio,
                                    bool aCDMDecodesVideo)
   : mProxy(aProxy)
   , mPDM(aPDM)

--- a/dom/media/fmp4/eme/EMEH264Decoder.cpp
+++ b/dom/media/fmp4/eme/EMEH264Decoder.cpp
@@ -29,28 +29,33 @@ EMEH264Decoder::EMEH264Decoder(CDMProxy*
   : mProxy(aProxy)
   , mGMP(nullptr)
   , mHost(nullptr)
   , mConfig(aConfig)
   , mImageContainer(aImageContainer)
   , mTaskQueue(aTaskQueue)
   , mCallback(aCallback)
   , mLastStreamOffset(0)
+  , mSamplesWaitingForKey(new SamplesWaitingForKey(this, mTaskQueue, mProxy))
   , mMonitor("EMEH264Decoder")
   , mFlushComplete(false)
+#ifdef DEBUG
+  , mIsShutdown(false)
+#endif
 {
 }
 
 EMEH264Decoder::~EMEH264Decoder() {
 }
 
 nsresult
 EMEH264Decoder::Init()
 {
   // Note: this runs on the decode task queue.
+  MOZ_ASSERT(!mIsShutdown);
 
   mMPS = do_GetService("@mozilla.org/gecko-media-plugin-service;1");
   MOZ_ASSERT(mMPS);
 
   nsresult rv = mMPS->GetThread(getter_AddRefs(mGMPThread));
   NS_ENSURE_SUCCESS(rv, rv);
 
   nsRefPtr<InitTask> task(new InitTask(this));
@@ -60,28 +65,34 @@ EMEH264Decoder::Init()
 
   return NS_OK;
 }
 
 nsresult
 EMEH264Decoder::Input(MP4Sample* aSample)
 {
   MOZ_ASSERT(!IsOnGMPThread()); // Runs on the decode task queue.
+  MOZ_ASSERT(!mIsShutdown);
+
+  if (mSamplesWaitingForKey->WaitIfKeyNotUsable(aSample)) {
+    return NS_OK;
+  }
 
   nsRefPtr<nsIRunnable> task(new DeliverSample(this, aSample));
   nsresult rv = mGMPThread->Dispatch(task, NS_DISPATCH_NORMAL);
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 nsresult
 EMEH264Decoder::Flush()
 {
   MOZ_ASSERT(!IsOnGMPThread()); // Runs on the decode task queue.
+  MOZ_ASSERT(!mIsShutdown);
 
   {
     MonitorAutoLock mon(mMonitor);
     mFlushComplete = false;
   }
 
   nsRefPtr<nsIRunnable> task;
   task = NS_NewRunnableMethod(this, &EMEH264Decoder::GmpFlush);
@@ -97,33 +108,42 @@ EMEH264Decoder::Flush()
 
   return NS_OK;
 }
 
 nsresult
 EMEH264Decoder::Drain()
 {
   MOZ_ASSERT(!IsOnGMPThread()); // Runs on the decode task queue.
+  MOZ_ASSERT(!mIsShutdown);
 
   nsRefPtr<nsIRunnable> task;
   task = NS_NewRunnableMethod(this, &EMEH264Decoder::GmpDrain);
   nsresult rv = mGMPThread->Dispatch(task, NS_DISPATCH_NORMAL);
   NS_ENSURE_SUCCESS(rv, rv);
   return NS_OK;
 }
 
 nsresult
 EMEH264Decoder::Shutdown()
 {
   MOZ_ASSERT(!IsOnGMPThread()); // Runs on the decode task queue.
+  MOZ_ASSERT(!mIsShutdown);
+#ifdef DEBUG
+  mIsShutdown = true;
+#endif
 
   nsRefPtr<nsIRunnable> task;
   task = NS_NewRunnableMethod(this, &EMEH264Decoder::GmpShutdown);
   nsresult rv = mGMPThread->Dispatch(task, NS_DISPATCH_SYNC);
   NS_ENSURE_SUCCESS(rv, rv);
+
+  mSamplesWaitingForKey->BreakCycles();
+  mSamplesWaitingForKey = nullptr;
+
   return NS_OK;
 }
 
 void
 EMEH264Decoder::Decoded(GMPVideoi420Frame* aDecodedFrame)
 {
   MOZ_ASSERT(IsOnGMPThread());
 
@@ -206,19 +226,25 @@ EMEH264Decoder::ResetComplete()
     mon.NotifyAll();
   }
 }
 
 void
 EMEH264Decoder::Error(GMPErr aErr)
 {
   MOZ_ASSERT(IsOnGMPThread());
-  EME_LOG("EMEH264Decoder::Error");
-  mCallback->Error();
-  GmpShutdown();
+  EME_LOG("EMEH264Decoder::Error %d", aErr);
+  if (aErr == GMPNoKeyErr) {
+    // The GMP failed to decrypt a frame due to not having a key. This can
+    // happen if a key expires or a session is closed during playback.
+    NS_WARNING("GMP failed to decrypt due to lack of key");
+  } else {
+    mCallback->Error();
+    GmpShutdown();
+  }
 }
 
 void
 EMEH264Decoder::Terminated()
 {
   MOZ_ASSERT(IsOnGMPThread());
 
   NS_WARNING("H.264 GMP decoder terminated.");
@@ -272,28 +298,16 @@ EMEH264Decoder::GmpInput(MP4Sample* aSam
   MOZ_ASSERT(IsOnGMPThread());
 
   nsAutoPtr<MP4Sample> sample(aSample);
   if (!mGMP) {
     mCallback->Error();
     return NS_ERROR_FAILURE;
   }
 
-  if (sample->crypto.valid) {
-    CDMCaps::AutoLock caps(mProxy->Capabilites());
-    MOZ_ASSERT(caps.CanDecryptAndDecodeVideo());
-    const auto& keyid = sample->crypto.key;
-    if (!caps.IsKeyUsable(keyid)) {
-      nsRefPtr<nsIRunnable> task(new DeliverSample(this, sample.forget()));
-      caps.CallWhenKeyUsable(keyid, task, mGMPThread);
-      return NS_OK;
-    }
-  }
-
-
   mLastStreamOffset = sample->byte_offset;
 
   GMPVideoFrame* ftmp = nullptr;
   GMPErr err = mHost->CreateFrame(kGMPEncodedVideoFrame, &ftmp);
   if (GMP_FAILED(err)) {
     mCallback->Error();
     return NS_ERROR_FAILURE;
   }

--- a/dom/media/fmp4/eme/EMEH264Decoder.h
+++ b/dom/media/fmp4/eme/EMEH264Decoder.h
@@ -7,16 +7,17 @@
 #ifndef EMEH264Decoder_h_
 #define EMEH264Decoder_h_
 
 #include "PlatformDecoderModule.h"
 #include "mp4_demuxer/DecoderData.h"
 #include "ImageContainer.h"
 #include "GMPVideoDecoderProxy.h"
 #include "mozIGeckoMediaPluginService.h"
+#include "SamplesWaitingForKey.h"
 
 namespace mozilla {
 
 class CDMProxy;
 class MediaTaskQueue;
 
 class EMEH264Decoder : public MediaDataDecoder
                      , public GMPVideoDecoderCallbackProxy
@@ -99,15 +100,22 @@ private:
   GMPVideoHost* mHost;
 
   VideoInfo mVideoInfo;
   const mp4_demuxer::VideoDecoderConfig& mConfig;
   nsRefPtr<layers::ImageContainer> mImageContainer;
   nsRefPtr<MediaTaskQueue> mTaskQueue;
   MediaDataDecoderCallback* mCallback;
   int64_t mLastStreamOffset;
+
+  nsRefPtr<SamplesWaitingForKey> mSamplesWaitingForKey;
+
   Monitor mMonitor;
   bool mFlushComplete;
+
+#ifdef DEBUG
+  bool mIsShutdown;
+#endif
 };
 
 }
 
 #endif // EMEH264Decoder_h_

new file mode 100644
--- /dev/null
+++ b/dom/media/fmp4/eme/SamplesWaitingForKey.cpp
@@ -0,0 +1,82 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "SamplesWaitingForKey.h"
+#include "mozilla/CDMProxy.h"
+#include "mozilla/CDMCaps.h"
+
+namespace mozilla {
+
+SamplesWaitingForKey::SamplesWaitingForKey(MediaDataDecoder* aDecoder,
+                                           MediaTaskQueue* aTaskQueue,
+                                           CDMProxy* aProxy)
+  : mMutex("SamplesWaitingForKey")
+  , mDecoder(aDecoder)
+  , mTaskQueue(aTaskQueue)
+  , mProxy(aProxy)
+{
+}
+
+SamplesWaitingForKey::~SamplesWaitingForKey()
+{
+}
+
+bool
+SamplesWaitingForKey::WaitIfKeyNotUsable(MP4Sample* aSample)
+{
+  if (!aSample || !aSample->crypto.valid || !mProxy) {
+    return false;
+  }
+  CDMCaps::AutoLock caps(mProxy->Capabilites());
+  const auto& keyid = aSample->crypto.key;
+  if (!caps.IsKeyUsable(keyid)) {
+    {
+      MutexAutoLock lock(mMutex);
+      mSamples.AppendElement(aSample);
+    }
+    caps.NotifyWhenKeyIdUsable(aSample->crypto.key, this);
+    return true;
+  }
+  return false;
+}
+
+void
+SamplesWaitingForKey::NotifyUsable(const CencKeyId& aKeyId)
+{
+  MutexAutoLock lock(mMutex);
+  size_t i = 0;
+  while (i < mSamples.Length()) {
+    if (aKeyId == mSamples[i]->crypto.key) {
+      RefPtr<nsIRunnable> task;
+      task = NS_NewRunnableMethodWithArg<MP4Sample*>(mDecoder,
+                                                     &MediaDataDecoder::Input,
+                                                     mSamples[i].forget());
+      mSamples.RemoveElementAt(i);
+      mTaskQueue->Dispatch(task.forget());
+    } else {
+      i++;
+    }
+  }
+}
+
+void
+SamplesWaitingForKey::Flush()
+{
+  MutexAutoLock lock(mMutex);
+  mSamples.Clear();
+}
+
+void
+SamplesWaitingForKey::BreakCycles()
+{
+  MutexAutoLock lock(mMutex);
+  mDecoder = nullptr;
+  mTaskQueue = nullptr;
+  mProxy = nullptr;
+  mSamples.Clear();
+}
+
+} // namespace mozilla

new file mode 100644
--- /dev/null
+++ b/dom/media/fmp4/eme/SamplesWaitingForKey.h
@@ -0,0 +1,57 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim:set ts=2 sw=2 sts=2 et cindent: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef SamplesWaitingForKey_h_
+#define SamplesWaitingForKey_h_
+
+#include "mp4_demuxer/DecoderData.h"
+#include "MediaTaskQueue.h"
+#include "PlatformDecoderModule.h"
+
+namespace mozilla {
+
+typedef nsTArray<uint8_t> CencKeyId;
+
+class CDMProxy;
+
+// Encapsulates the task of waiting for the CDMProxy to have the necessary
+// keys to decypt a given sample.
+class SamplesWaitingForKey {
+  typedef mp4_demuxer::MP4Sample MP4Sample;
+public:
+
+  NS_INLINE_DECL_THREADSAFE_REFCOUNTING(SamplesWaitingForKey)
+
+  explicit SamplesWaitingForKey(MediaDataDecoder* aDecoder,
+                                MediaTaskQueue* aTaskQueue,
+                                CDMProxy* aProxy);
+
+  // Returns true if we need to wait for a key to become usable.
+  // Will callback MediaDataDecoder::Input(aSample) on mDecoder once the
+  // sample is ready to be decrypted. The order of input samples is
+  // preserved.
+  bool WaitIfKeyNotUsable(MP4Sample* aSample);
+
+  void NotifyUsable(const CencKeyId& aKeyId);
+
+  void Flush();
+
+  void BreakCycles();
+
+protected:
+  ~SamplesWaitingForKey();
+
+private:
+  Mutex mMutex;
+  nsRefPtr<MediaDataDecoder> mDecoder;
+  nsRefPtr<MediaTaskQueue> mTaskQueue;
+  nsRefPtr<CDMProxy> mProxy;
+  nsTArray<nsAutoPtr<MP4Sample>> mSamples;
+};
+
+} // namespace mozilla
+
+#endif //  SamplesWaitingForKey_h_

--- a/dom/media/fmp4/eme/moz.build
+++ b/dom/media/fmp4/eme/moz.build
@@ -1,26 +1,28 @@
-# -*- Mode: python; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 40 -*-
-# vim: set filetype=python:
-# This Source Code Form is subject to the terms of the Mozilla Public
-# License, v. 2.0. If a copy of the MPL was not distributed with this
-# file, You can obtain one at http://mozilla.org/MPL/2.0/.
-
-EXPORTS += [
-    'EMEAudioDecoder.h',
-    'EMEDecoderModule.h',
-    'EMEH264Decoder.h',
-]
-
-UNIFIED_SOURCES += [
-    'EMEAudioDecoder.cpp',
-    'EMEDecoderModule.cpp',
-    'EMEH264Decoder.cpp',
-]
-
-include('/ipc/chromium/chromium-config.mozbuild')
-
-FINAL_LIBRARY = 'xul'
-
-FAIL_ON_WARNINGS = True
-
-if CONFIG['OS_ARCH'] == 'WINNT':
-    DEFINES['NOMINMAX'] = True
+# -*- Mode: python; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 40 -*-
+# vim: set filetype=python:
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+EXPORTS += [
+    'EMEAudioDecoder.h',
+    'EMEDecoderModule.h',
+    'EMEH264Decoder.h',
+    'SamplesWaitingForKey.h',
+]
+
+UNIFIED_SOURCES += [
+    'EMEAudioDecoder.cpp',
+    'EMEDecoderModule.cpp',
+    'EMEH264Decoder.cpp',
+    'SamplesWaitingForKey.cpp',
+]
+
+include('/ipc/chromium/chromium-config.mozbuild')
+
+FINAL_LIBRARY = 'xul'
+
+FAIL_ON_WARNINGS = True
+
+if CONFIG['OS_ARCH'] == 'WINNT':
+    DEFINES['NOMINMAX'] = True

--- a/dom/media/gmp/gmp-api/gmp-errors.h
+++ b/dom/media/gmp/gmp-api/gmp-errors.h
@@ -42,15 +42,16 @@ typedef enum {
   GMPRecordInUse = 5,
   GMPQuotaExceededErr = 6,
   GMPDecodeErr = 7,
   GMPEncodeErr = 8,
   GMPNoKeyErr = 9,
   GMPCryptoErr = 10,
   GMPEndOfEnumeration = 11,
   GMPInvalidArgErr = 12,
+  GMPAbortedErr = 13,
   GMPLastErr // Placeholder, must be last. This enum's values must remain consecutive!
 } GMPErr;
 
 #define GMP_SUCCEEDED(x) ((x) == GMPNoErr)
 #define GMP_FAILED(x) ((x) != GMPNoErr)
 
 #endif // GMP_ERRORS_h_