--- a/toolkit/components/places/FaviconHelpers.cpp
+++ b/toolkit/components/places/FaviconHelpers.cpp
@@ -50,32 +50,33 @@ FetchPageInfo(const RefPtr<Database>& aD
               PageData& _page)
 {
   MOZ_ASSERT(_page.spec.Length(), "Must have a non-empty spec!");
   MOZ_ASSERT(!NS_IsMainThread());
 
   // This query finds the bookmarked uri we want to set the icon for,
   // walking up to two redirect levels.
   nsCString query = nsPrintfCString(
-    "SELECT h.id, h.guid, ( "
+    "SELECT h.id, pi.id, h.guid, ( "
       "SELECT h.url FROM moz_bookmarks b WHERE b.fk = h.id "
       "UNION ALL " // Union not directly bookmarked pages.
       "SELECT url FROM moz_places WHERE id = ( "
         "SELECT COALESCE(grandparent.place_id, parent.place_id) as r_place_id "
         "FROM moz_historyvisits dest "
         "LEFT JOIN moz_historyvisits parent ON parent.id = dest.from_visit "
                                           "AND dest.visit_type IN (%d, %d) "
         "LEFT JOIN moz_historyvisits grandparent ON parent.from_visit = grandparent.id "
           "AND parent.visit_type IN (%d, %d) "
         "WHERE dest.place_id = h.id "
         "AND EXISTS(SELECT 1 FROM moz_bookmarks b WHERE b.fk = r_place_id) "
         "LIMIT 1 "
       ") "
     ") "
     "FROM moz_places h "
+    "LEFT JOIN moz_pages_w_icons pi ON page_url_hash = hash(:page_url) AND page_url = :page_url "
     "WHERE h.url_hash = hash(:page_url) AND h.url = :page_url",
     nsINavHistoryService::TRANSITION_REDIRECT_PERMANENT,
     nsINavHistoryService::TRANSITION_REDIRECT_TEMPORARY,
     nsINavHistoryService::TRANSITION_REDIRECT_PERMANENT,
     nsINavHistoryService::TRANSITION_REDIRECT_TEMPORARY
   );
 
   nsCOMPtr<mozIStorageStatement> stmt = aDB->GetStatement(query);
@@ -89,27 +90,29 @@ FetchPageInfo(const RefPtr<Database>& aD
   bool hasResult;
   rv = stmt->ExecuteStep(&hasResult);
   NS_ENSURE_SUCCESS(rv, rv);
   if (!hasResult) {
     // The page does not exist.
     return NS_ERROR_NOT_AVAILABLE;
   }
 
-  rv = stmt->GetInt64(0, &_page.id);
+  rv = stmt->GetInt64(0, &_page.placeId);
   NS_ENSURE_SUCCESS(rv, rv);
-  rv = stmt->GetUTF8String(1, _page.guid);
+  // May be null, and in such a case this will be 0.
+  _page.id = stmt->AsInt64(1);
+  rv = stmt->GetUTF8String(2, _page.guid);
   NS_ENSURE_SUCCESS(rv, rv);
   // Bookmarked url can be nullptr.
   bool isNull;
-  rv = stmt->GetIsNull(2, &isNull);
+  rv = stmt->GetIsNull(3, &isNull);
   NS_ENSURE_SUCCESS(rv, rv);
   // The page could not be bookmarked.
   if (!isNull) {
-    rv = stmt->GetUTF8String(2, _page.bookmarkedSpec);
+    rv = stmt->GetUTF8String(3, _page.bookmarkedSpec);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   if (!_page.canAddToHistory) {
     // Either history is disabled or the scheme is not supported.  In such a
     // case we want to update the icon only if the page is bookmarked.
 
     if (_page.bookmarkedSpec.IsEmpty()) {
@@ -789,55 +792,81 @@ AsyncAssociateIconToPage::Run()
     NS_ENSURE_SUCCESS(rv, rv);
 
     mIcon.status = (mIcon.status & ~(ICON_STATUS_CACHED)) | ICON_STATUS_SAVED;
   }
 
   // If the page does not have an id, don't try to insert a new one, cause we
   // don't know where the page comes from.  Not doing so we may end adding
   // a page that otherwise we'd explicitly ignore, like a POST or an error page.
-  if (mPage.id == 0) {
+  if (mPage.placeId == 0) {
     rv = transaction.Commit();
     NS_ENSURE_SUCCESS(rv, rv);
     return NS_OK;
   }
 
-  // First we need to create the page entry.
-  {
+  // The page may have associated payloads already, and those could have to be
+  // expired. For example at a certain point a page could decide to stop serving
+  // its usual 16px and 32px pngs, and use an svg instead.
+  // On the other side, we could also be in the process of adding more payloads
+  // to this page, and we should not expire the payloads we just added.
+  // For this, we use the expiration field as an indicator and remove relations
+  // based on it being elapsed. We don't remove orphan icons at this time since
+  // it would have a cost. The privacy hit is limited since history removal
+  // methods already expire orphan icons.
+  if (mPage.id != 0)  {
     nsCOMPtr<mozIStorageStatement> stmt;
     stmt = DB->GetStatement(
-      "INSERT OR IGNORE INTO moz_pages_w_icons (id, page_url, page_url_hash) "
-      "VALUES (:page_id, :page_url, hash(:page_url)) "
+      "DELETE FROM moz_icons_to_pages WHERE icon_id IN ( "
+        "SELECT icon_id FROM moz_icons_to_pages "
+        "JOIN moz_icons i ON icon_id = i.id "
+        "WHERE page_id = :page_id "
+          "AND expire_ms < strftime('%s','now','localtime','start of day','-7 days','utc') * 1000 "
+      ") "
     );
     NS_ENSURE_STATE(stmt);
     mozStorageStatementScoper scoper(stmt);
     rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("page_id"), mPage.id);
     NS_ENSURE_SUCCESS(rv, rv);
+    rv = stmt->Execute();
+    NS_ENSURE_SUCCESS(rv, rv);
+  } else {
+    // We need to create the page entry.
+    // By default, we use the place id for the insertion. While we can't
+    // guarantee 1:1 mapping, in general it should do.
+    nsCOMPtr<mozIStorageStatement> stmt;
+    stmt = DB->GetStatement(
+      "INSERT OR IGNORE INTO moz_pages_w_icons (page_url, page_url_hash) "
+      "VALUES (:page_url, hash(:page_url)) "
+    );
+    NS_ENSURE_STATE(stmt);
+    mozStorageStatementScoper scoper(stmt);
     rv = URIBinder::Bind(stmt, NS_LITERAL_CSTRING("page_url"), mPage.spec);
     NS_ENSURE_SUCCESS(rv, rv);
     rv = stmt->Execute();
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   // Then we can create the relations.
   nsCOMPtr<mozIStorageStatement> stmt;
   stmt = DB->GetStatement(
     "INSERT OR IGNORE INTO moz_icons_to_pages (page_id, icon_id) "
-    "VALUES (:page_id, :icon_id) "
+    "VALUES ((SELECT id from moz_pages_w_icons WHERE page_url_hash = hash(:page_url) AND page_url = :page_url), "
+            ":icon_id) "
   );
   NS_ENSURE_STATE(stmt);
   mozStorageStatementScoper scoper(stmt);
   nsCOMPtr<mozIStorageBindingParamsArray> paramsArray;
   rv = stmt->NewBindingParamsArray(getter_AddRefs(paramsArray));
   NS_ENSURE_SUCCESS(rv, rv);
   for (const auto& payload : mIcon.payloads) {
     nsCOMPtr<mozIStorageBindingParams> params;
     rv = paramsArray->NewBindingParams(getter_AddRefs(params));
     NS_ENSURE_SUCCESS(rv, rv);
-    rv = params->BindInt64ByName(NS_LITERAL_CSTRING("page_id"), mPage.id);
+    rv = URIBinder::Bind(params, NS_LITERAL_CSTRING("page_url"), mPage.spec);
     NS_ENSURE_SUCCESS(rv, rv);
     rv = params->BindInt64ByName(NS_LITERAL_CSTRING("icon_id"), payload.id);
     NS_ENSURE_SUCCESS(rv, rv);
     rv = paramsArray->AddParams(params);
     NS_ENSURE_SUCCESS(rv, rv);
   }
   rv = stmt->BindParameters(paramsArray);
   NS_ENSURE_SUCCESS(rv, rv);

--- a/toolkit/components/places/FaviconHelpers.h
+++ b/toolkit/components/places/FaviconHelpers.h
@@ -99,22 +99,24 @@ struct IconData
 
 /**
  * Data cache for a page entry.
  */
 struct PageData
 {
   PageData()
   : id(0)
+  , placeId(0)
   , canAddToHistory(true)
   {
     guid.SetIsVoid(true);
   }
 
-  int64_t id;
+  int64_t id; // This is the moz_pages_w_icons id.
+  int64_t placeId; // This is the moz_places page id.
   nsCString spec;
   nsCString bookmarkedSpec;
   nsString revHost;
   bool canAddToHistory; // False for disabled history and unsupported schemas.
   nsCString guid;
 };
 
 /**

new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/tests/favicons/test_expire_on_new_icons.js
@@ -0,0 +1,43 @@
+/*
+ * Tests that adding new icons for a page expired old ones.
+ */
+
+add_task(function* test_replaceFaviconData_validHistoryURI() {
+  const TEST_URL = "http://mozilla.com/"
+  yield PlacesTestUtils.addVisits(TEST_URL);
+
+  let favicons = [
+    {
+      name: "favicon-normal16.png",
+      mimeType: "image/png",
+      expire: PlacesUtils.toPRTime(new Date(1)) // Very old.
+    },
+    {
+      name: "favicon-normal32.png",
+      mimeType: "image/png",
+      expire: 0
+    },
+    {
+      name: "favicon-big64.png",
+      mimeType: "image/png",
+      expire: 0
+    },
+  ];
+
+  for (let icon of favicons) {
+    let data = readFileData(do_get_file(icon.name));
+    PlacesUtils.favicons.replaceFaviconData(NetUtil.newURI(TEST_URL + icon.name),
+                                            data, data.length,
+                                            icon.mimeType,
+                                            icon.expire);
+    yield setFaviconForPage(TEST_URL, TEST_URL + icon.name);
+  }
+
+  // Only the second and the third icons should have survived.
+  Assert.equal(yield getFaviconUrlForPage(TEST_URL, 16),
+               TEST_URL + favicons[1].name,
+               "Should retrieve the 32px icon, not the 16px one.");
+  Assert.equal(yield getFaviconUrlForPage(TEST_URL, 64),
+               TEST_URL + favicons[2].name,
+               "Should retrieve the 64px icon");
+});

--- a/toolkit/components/places/tests/favicons/xpcshell.ini
+++ b/toolkit/components/places/tests/favicons/xpcshell.ini
@@ -15,16 +15,17 @@ support-files =
   favicon-big48.ico
   favicon-big64.png
   favicon-normal16.png
   favicon-normal32.png
   favicon-scale160x3.jpg
   favicon-scale3x160.jpg
 
 [test_expireAllFavicons.js]
+[test_expire_on_new_icons.js]
 [test_favicons_conversions.js]
 [test_favicons_protocols_ref.js]
 [test_getFaviconDataForPage.js]
 [test_getFaviconURLForPage.js]
 [test_moz-anno_favicon_mime_type.js]
 [test_page-icon_protocol.js]
 [test_query_result_favicon_changed_on_child.js]
 [test_replaceFaviconData.js]

--- a/toolkit/components/places/tests/head_common.js
+++ b/toolkit/components/places/tests/head_common.js
@@ -874,16 +874,26 @@ function setFaviconForPage(page, icon) {
       pageURI, iconURI, true,
       PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
       resolve,
       Services.scriptSecurityManager.getSystemPrincipal()
     );
   });
 }
 
+function getFaviconUrlForPage(page, width = 0) {
+  let pageURI = page instanceof Ci.nsIURI ? page
+                                          : NetUtil.newURI(new URL(page).href);
+  return new Promise(resolve => {
+    PlacesUtils.favicons.getFaviconURLForPage(pageURI, iconURI => {
+      resolve(iconURI.spec);
+    }, width);
+  });
+}
+
 /**
  * Asynchronously compares contents from 2 favicon urls.
  */
 function* compareFavicons(icon1, icon2, msg) {
   icon1 = new URL(icon1 instanceof Ci.nsIURI ? icon1.spec : icon1);
   icon2 = new URL(icon2 instanceof Ci.nsIURI ? icon2.spec : icon2);
 
   function getIconData(icon) {