new file mode 100644
--- /dev/null
+++ b/dom/canvas/CacheMap.cpp
@@ -0,0 +1,43 @@
+/* -*- Mode: C++; tab-width: 13; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/* vim: set ts=13 sts=4 et sw=4 tw=90: */
+/* 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 "CacheMap.h"
+
+namespace mozilla {
+
+void
+CacheMapInvalidator::InvalidateCaches() const
+{
+    while (mCacheEntries.size()) {
+        const auto& entry = *(mCacheEntries.begin());
+        entry->Invalidate();
+        MOZ_ASSERT(mCacheEntries.find(entry) == mCacheEntries.end());
+    }
+}
+
+namespace detail {
+
+CacheMapUntypedEntry::CacheMapUntypedEntry(std::vector<const CacheMapInvalidator*>&& invalidators)
+    : mInvalidators(Move(invalidators))
+{
+    for (const auto& cur : mInvalidators) {
+        // Don't assert that we insert, since there may be dupes in `invalidators`.
+        // (and it's not worth removing the dupes)
+        (void)cur->mCacheEntries.insert(this);
+    }
+}
+
+CacheMapUntypedEntry::~CacheMapUntypedEntry()
+{
+    for (const auto& cur : mInvalidators) {
+        // There might be dupes, so erase might return >1.
+        (void)cur->mCacheEntries.erase(this);
+    }
+}
+
+} // namespace detail
+
+} // namespace mozilla

new file mode 100644
--- /dev/null
+++ b/dom/canvas/CacheMap.h
@@ -0,0 +1,128 @@
+/* -*- Mode: C++; tab-width: 13; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/* vim: set ts=13 sts=4 et sw=4 tw=90: */
+/* 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 MOZILLA_CACHE_MAP_H_
+#define MOZILLA_CACHE_MAP_H_
+
+#include "mozilla/UniquePtr.h"
+#include <map>
+#include <unordered_set>
+#include <vector>
+
+namespace mozilla {
+
+namespace detail {
+struct CacheMapUntypedEntry;
+}
+
+class CacheMapInvalidator
+{
+    friend struct detail::CacheMapUntypedEntry;
+
+    mutable std::unordered_set<const detail::CacheMapUntypedEntry*> mCacheEntries;
+
+public:
+    ~CacheMapInvalidator() {
+        InvalidateCaches();
+    }
+
+    void InvalidateCaches() const;
+};
+
+namespace detail {
+
+struct CacheMapUntypedEntry
+{
+    template<typename, typename> friend class CacheMap;
+
+    const std::vector<const CacheMapInvalidator*> mInvalidators;
+
+    CacheMapUntypedEntry(std::vector<const CacheMapInvalidator*>&& invalidators);
+    ~CacheMapUntypedEntry();
+
+public:
+    virtual void Invalidate() const = 0;
+};
+
+template<typename T>
+struct DerefLess final {
+    bool operator ()(const T* const a, const T* const b) const {
+        return *a < *b;
+    }
+};
+
+} // namespace detail
+
+
+template<typename KeyT, typename ValueT>
+class CacheMap final
+{
+    struct Entry final : public detail::CacheMapUntypedEntry {
+        CacheMap& mParent;
+        const KeyT mKey;
+        const ValueT mValue;
+
+        Entry(std::vector<const CacheMapInvalidator*>&& invalidators, CacheMap& parent,
+              KeyT&& key, ValueT&& value)
+            : detail::CacheMapUntypedEntry(Move(invalidators))
+            , mParent(parent)
+            , mKey(Move(key))
+            , mValue(Move(value))
+        { }
+
+        void Invalidate() const override {
+            const auto erased = mParent.mMap.erase(&mKey);
+            MOZ_ALWAYS_TRUE( erased == 1 );
+        }
+
+        bool operator <(const Entry& x) const {
+            return mKey < x.mKey;
+        }
+    };
+
+    typedef std::map<const KeyT*, UniquePtr<const Entry>, detail::DerefLess<KeyT>> MapT;
+    MapT mMap;
+
+public:
+    const ValueT* Insert(KeyT&& key, ValueT&& value,
+                         std::vector<const CacheMapInvalidator*>&& invalidators)
+    {
+        UniquePtr<const Entry> entry( new Entry(Move(invalidators), *this, Move(key),
+                                                Move(value)) );
+
+        typename MapT::value_type insertable{
+            &entry->mKey,
+            nullptr
+        };
+        insertable.second = Move(entry);
+
+        const auto res = mMap.insert(Move(insertable));
+        const auto& didInsert = res.second;
+        MOZ_ALWAYS_TRUE( didInsert );
+
+        const auto& itr = res.first;
+        return &itr->second->mValue;
+    }
+
+    const ValueT* Find(const KeyT& key) const {
+        const auto itr = mMap.find(&key);
+        if (itr == mMap.end())
+            return nullptr;
+
+        return &itr->second->mValue;
+    }
+
+    void Invalidate() {
+        while (mMap.size()) {
+            const auto& itr = mMap.begin();
+            itr->second->Invalidate();
+        }
+    }
+};
+
+} // namespace mozilla
+
+#endif // MOZILLA_CACHE_MAP_H_

--- a/dom/canvas/moz.build
+++ b/dom/canvas/moz.build
@@ -89,16 +89,17 @@ UNIFIED_SOURCES += [
 ]
 
 SOURCES += [
     'ImageUtils.cpp',
 ]
 
 # WebGL Sources
 UNIFIED_SOURCES += [
+    'CacheMap.cpp',
     'TexUnpackBlob.cpp',
     'WebGL1Context.cpp',
     'WebGL2Context.cpp',
     'WebGL2ContextBuffers.cpp',
     'WebGL2ContextFramebuffers.cpp',
     'WebGL2ContextMRTs.cpp',
     'WebGL2ContextPrograms.cpp',
     'WebGL2ContextQueries.cpp',