--- a/browser/components/places/content/browserPlacesViews.js
+++ b/browser/components/places/content/browserPlacesViews.js
@@ -506,16 +506,18 @@ PlacesViewBase.prototype = {
     // be done when the icon changes.
     if (elt == this._rootElt)
       return;
 
     // Here we need the <menu>.
     if (elt.localName == "menupopup") {
       elt = elt.parentNode;
     }
+    // We must remove and reset the attribute to force an update.
+    elt.removeAttribute("image");
     elt.setAttribute("image", aPlacesNode.icon);
   },
 
   nodeAnnotationChanged:
   function PVB_nodeAnnotationChanged(aPlacesNode, aAnno) {
     let elt = this._getDOMNodeForPlacesNode(aPlacesNode);
 
     // All livemarks have a feedURI, so use it as our indicator of a livemark

--- a/browser/components/places/content/treeView.js
+++ b/browser/components/places/content/treeView.js
@@ -776,18 +776,21 @@ PlacesTreeView.prototype = {
     if (aNode == this._rootNode)
       return;
 
     let row = this._getRowForNode(aNode);
     if (row == -1)
       return;
 
     let column = this._findColumnByType(aColumnType);
-    if (column && !column.element.hidden)
+    if (column && !column.element.hidden) {
+      if (aColumnType == this.COLUMN_TYPE_TITLE)
+        this._tree.removeImageCacheEntry(row, column);
       this._tree.invalidateCell(row, column);
+    }
 
     // Last modified time is altered for almost all node changes.
     if (aColumnType != this.COLUMN_TYPE_LASTMODIFIED) {
       let lastModifiedColumn =
         this._findColumnByType(this.COLUMN_TYPE_LASTMODIFIED);
       if (lastModifiedColumn && !lastModifiedColumn.hidden)
         this._tree.invalidateCell(row, lastModifiedColumn);
     }

--- a/browser/components/places/tests/browser/browser.ini
+++ b/browser/components/places/tests/browser/browser.ini
@@ -48,13 +48,16 @@ support-files =
 [browser_library_panel_leak.js]
 [browser_library_search.js]
 [browser_library_views_liveupdate.js]
 [browser_markPageAsFollowedLink.js]
 [browser_sidebarpanels_click.js]
 skip-if = true # temporarily disabled for breaking the treeview - bug 658744
 [browser_sort_in_library.js]
 [browser_toolbarbutton_menu_context.js]
+[browser_views_iconsupdate.js]
+support-files =
+  favicon-normal16.png
 [browser_views_liveupdate.js]
 [browser_bookmark_all_tabs.js]
 support-files =
   bookmark_dummy_1.html
   bookmark_dummy_2.html

new file mode 100644
--- /dev/null
+++ b/browser/components/places/tests/browser/browser_views_iconsupdate.js
@@ -0,0 +1,119 @@
+/* Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/publicdomain/zero/1.0/ */
+
+/**
+ * Tests Places views (toolbar, tree) for icons update.
+ * The menu is not tested since it uses the same code as the toolbar.
+ */
+
+add_task(function* () {
+  const PAGE_URI = NetUtil.newURI("http://places.test/");
+  const ICON_URI = NetUtil.newURI("http://mochi.test:8888/browser/browser/components/places/tests/browser/favicon-normal16.png");
+
+  info("Uncollapse the personal toolbar if needed");
+  let toolbar = document.getElementById("PersonalToolbar");
+  let wasCollapsed = toolbar.collapsed;
+  if (wasCollapsed) {
+    yield promiseSetToolbarVisibility(toolbar, true);
+    registerCleanupFunction(function* () {
+      yield promiseSetToolbarVisibility(toolbar, false);
+    });
+  }
+
+  info("Open the bookmarks sidebar");
+  let sidebar = document.getElementById("sidebar");
+  let promiseSidebarLoaded = new Promise(resolve => {
+    sidebar.addEventListener("load", resolve, {capture: true, once: true});
+  });
+  SidebarUI.show("viewBookmarksSidebar");
+  registerCleanupFunction(() => {
+    SidebarUI.hide();
+  });
+  yield promiseSidebarLoaded;
+
+  // Add a bookmark to the bookmarks toolbar.
+  let bm = yield PlacesUtils.bookmarks.insert({
+    url: PAGE_URI,
+    title: "test icon",
+    parentGuid: PlacesUtils.bookmarks.toolbarGuid
+  });
+  registerCleanupFunction(function* () {
+    yield PlacesUtils.bookmarks.remove(bm);
+  });
+
+  // The icon is read asynchronously from the network, we don't have an easy way
+  // to wait for that.
+  yield new Promise(resolve => {
+    setTimeout(resolve, 3000);
+  });
+
+  let toolbarElt = getNodeForToolbarItem(bm.guid);
+  let toolbarShot1 = TestUtils.screenshotArea(toolbarElt, window);
+  let sidebarRect = yield getRectForSidebarItem(bm.guid);
+  let sidebarShot1 = TestUtils.screenshotArea(sidebarRect, window);
+
+  yield new Promise(resolve => {
+    PlacesUtils.favicons.setAndFetchFaviconForPage(
+      PAGE_URI, ICON_URI, true,
+      PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
+      resolve,
+      Services.scriptSecurityManager.getSystemPrincipal()
+    );
+  });
+
+  // The icon is read asynchronously from the network, we don't have an easy way
+  // to wait for that.
+  yield new Promise(resolve => {
+    setTimeout(resolve, 3000);
+  });
+
+  // Assert.notEqual truncates the strings, so it is unusable here for failure
+  // debugging purposes.
+  let toolbarShot2 = TestUtils.screenshotArea(toolbarElt, window);
+  if (toolbarShot1 != toolbarShot2) {
+    info("Before toolbar: " + toolbarShot1);
+    info("After toolbar: " + toolbarShot2);
+  }
+  Assert.notEqual(toolbarShot1, toolbarShot2, "The UI should have updated");
+
+  let sidebarShot2 = TestUtils.screenshotArea(sidebarRect, window);
+  if (sidebarShot1 != sidebarShot2) {
+    info("Before sidebar: " + sidebarShot1);
+    info("After sidebar: " + sidebarShot2);
+  }
+  Assert.notEqual(sidebarShot1, sidebarShot2, "The UI should have updated");
+});
+
+/**
+ * Get Element for a bookmark in the bookmarks toolbar.
+ *
+ * @param guid
+ *        GUID of the item to search.
+ * @returns DOM Node of the element.
+ */
+function getNodeForToolbarItem(guid) {
+  return Array.from(document.getElementById("PlacesToolbarItems").childNodes)
+              .find(child => child._placesNode && child._placesNode.bookmarkGuid == guid);
+}
+
+/**
+ * Get a rect for a bookmark in the bookmarks sidebar
+ *
+ * @param guid
+ *        GUID of the item to search.
+ * @returns DOM Node of the element.
+ */
+function* getRectForSidebarItem(guid) {
+  let itemId = yield PlacesUtils.promiseItemId(guid);
+  let sidebar = document.getElementById("sidebar");
+  let tree = sidebar.contentDocument.getElementById("bookmarks-view");
+  tree.selectItems([itemId]);
+  let rect = {};
+  [rect.left, rect.top, rect.width, rect.height] = tree.treeBoxObject
+                                                       .selectionRegion
+                                                       .getRects();
+  // Adjust the position for the sidebar.
+  rect.left += sidebar.getBoundingClientRect().left;
+  rect.top += sidebar.getBoundingClientRect().top;
+  return rect;
+}

new file mode 100644
index 0000000000000000000000000000000000000000..62b69a3d031f616ad622eb67aa0e57bd400be50d
GIT binary patch
literal 286
zc$@(q0pb3MP)<h;3K|Lk000e1NJLTq000mG000mO1^@s6AM^iV0002xNkl<ZILpP;
zy-Gtt5C!0GC17mCpIS&M*edt{c6kYVE1${Q!Xljn?8VkJK7xr>7RDS4jk(vv8$t>X
z4D2j3XLrublq9hRHmr%(+)YM!AOj51rgU(O14^rbAW!6q^zn!hHc5waLOCa=ly)U&
zipenfxJ<@7$=DxumQ3!G$@@=QMT0wXjhBXsZ^;c_7l@eNcg=HU*8TMGyog|cx3A;)
zm##H`7PqvGrM1c&ltXMaygWrcu0qho-f|5}7yHZG$jqABIO8t6xWG2)%eXQ~Dud*x
k_N6knOe>CZ`S)%71OS<-E}v@0ssI2007*qoM6N<$g2c>!G5`Po

--- a/browser/components/places/tests/browser/head.js
+++ b/browser/components/places/tests/browser/head.js
@@ -1,14 +1,16 @@
 XPCOMUtils.defineLazyModuleGetter(this, "NetUtil",
   "resource://gre/modules/NetUtil.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "Promise",
   "resource://gre/modules/Promise.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "PlacesTestUtils",
   "resource://testing-common/PlacesTestUtils.jsm");
+XPCOMUtils.defineLazyModuleGetter(this, "TestUtils",
+  "resource://testing-common/TestUtils.jsm");
 
 // Imported via PlacesOverlay.xul
 /* global doGetPlacesControllerForCommand:false, PlacesControllerDragHelper:false,
           PlacesUIUtils:false
 */
 
 // We need to cache this before test runs...
 var cachedLeftPaneFolderIdGetter;

--- a/dom/webidl/TreeBoxObject.webidl
+++ b/dom/webidl/TreeBoxObject.webidl
@@ -199,9 +199,15 @@ interface TreeBoxObject : BoxObject {
    * Notify the tree that the view has completed a batch update.
    */
   void endUpdateBatch();
 
   /**
    * Called on a theme switch to flush out the tree's style and image caches.
    */
   void clearStyleAndImageCaches();
+
+  /**
+   * Remove an image source from the image cache to allow its invalidation.
+   */
+  [Throws]
+  void removeImageCacheEntry(long row, TreeColumn col);
 };

--- a/layout/xul/tree/TreeBoxObject.cpp
+++ b/layout/xul/tree/TreeBoxObject.cpp
@@ -662,16 +662,34 @@ NS_IMETHODIMP
 TreeBoxObject::ClearStyleAndImageCaches()
 {
   nsTreeBodyFrame* body = GetTreeBodyFrame();
   if (body)
     return body->ClearStyleAndImageCaches();
   return NS_OK;
 }
 
+NS_IMETHODIMP
+TreeBoxObject::RemoveImageCacheEntry(int32_t aRowIndex, nsITreeColumn* aCol)
+{
+  NS_ENSURE_ARG(aCol);
+  NS_ENSURE_TRUE(aRowIndex >= 0, NS_ERROR_INVALID_ARG);
+  nsTreeBodyFrame* body = GetTreeBodyFrame();
+  if (body) {
+    return body->RemoveImageCacheEntry(aRowIndex, aCol);
+  }
+  return NS_OK;
+}
+
+void
+TreeBoxObject::RemoveImageCacheEntry(int32_t row, nsITreeColumn& col, ErrorResult& aRv)
+{
+  aRv = RemoveImageCacheEntry(row, &col);
+}
+
 void
 TreeBoxObject::ClearCachedValues()
 {
   mTreeBody = nullptr;
 }
 
 JSObject*
 TreeBoxObject::WrapObject(JSContext* aCx, JS::Handle<JSObject*> aGivenProto)

--- a/layout/xul/tree/TreeBoxObject.h
+++ b/layout/xul/tree/TreeBoxObject.h
@@ -70,16 +70,18 @@ public:
 
   already_AddRefed<DOMRect> GetCoordsForCellItem(int32_t row,
                                                  nsTreeColumn& col,
                                                  const nsAString& element,
                                                  ErrorResult& aRv);
 
   bool IsCellCropped(int32_t row, nsITreeColumn* col, ErrorResult& aRv);
 
+  void RemoveImageCacheEntry(int32_t row, nsITreeColumn& col, ErrorResult& aRv);
+
   // Deprecated APIs from old IDL
   void GetCellAt(JSContext* cx,
                  int32_t x, int32_t y,
                  JS::Handle<JSObject*> rowOut,
                  JS::Handle<JSObject*> colOut,
                  JS::Handle<JSObject*> childEltOut,
                  ErrorResult& aRv);
 

--- a/layout/xul/tree/nsITreeBoxObject.idl
+++ b/layout/xul/tree/nsITreeBoxObject.idl
@@ -43,17 +43,17 @@ interface nsITreeBoxObject : nsISupports
   readonly attribute long rowHeight;
 
   /**
    * Obtain the width of a row.
    */
   readonly attribute long rowWidth;
 
   /**
-   * Get the pixel position of the horizontal scrollbar. 
+   * Get the pixel position of the horizontal scrollbar.
    */
   readonly attribute long horizontalPosition;
 
   /**
    * Return the region for the visible parts of the selection, in device pixels.
    */
   readonly attribute nsIScriptableRegion selectionRegion;
 
@@ -181,9 +181,17 @@ interface nsITreeBoxObject : nsISupports
    * Notify the tree that the view has completed a batch update.
    */
   void endUpdateBatch();
 
   /**
    * Called on a theme switch to flush out the tree's style and image caches.
    */
   void clearStyleAndImageCaches();
+
+  /**
+   * Remove an image source from the image cache to allow its invalidation.
+   *
+   * @note This only affects images supplied by the view, not the ones supplied
+   *       through the styling context, like twisties or checkboxes.
+   */
+  void removeImageCacheEntry(in long row, in nsITreeColumn col);
 };

--- a/layout/xul/tree/nsTreeBodyFrame.cpp
+++ b/layout/xul/tree/nsTreeBodyFrame.cpp
@@ -1104,17 +1104,17 @@ nsTreeBodyFrame::GetCoordsForCellItem(in
   *aX = 0;
   *aY = 0;
   *aWidth = 0;
   *aHeight = 0;
 
   bool isRTL = StyleVisibility()->mDirection == NS_STYLE_DIRECTION_RTL;
   nscoord currX = mInnerBox.x - mHorzPosition;
 
-  // The Rect for the requested item. 
+  // The Rect for the requested item.
   nsRect theRect;
 
   nsPresContext* presContext = PresContext();
 
   for (nsTreeColumn* currCol = mColumns->GetFirstColumn(); currCol; currCol = currCol->GetNext()) {
 
     // The Rect for the current cell.
     nscoord colWidth;
@@ -4524,16 +4524,32 @@ nsresult
 nsTreeBodyFrame::ClearStyleAndImageCaches()
 {
   mStyleCache.Clear();
   CancelImageRequests();
   mImageCache.Clear();
   return NS_OK;
 }
 
+nsresult
+nsTreeBodyFrame::RemoveImageCacheEntry(int32_t aRowIndex, nsITreeColumn* aCol)
+{
+  nsAutoString imageSrc;
+  if (NS_SUCCEEDED(mView->GetImageSrc(aRowIndex, aCol, imageSrc))) {
+    nsTreeImageCacheEntry entry;
+    if (mImageCache.Get(imageSrc, &entry)) {
+      nsLayoutUtils::DeregisterImageRequest(PresContext(), entry.request,
+                                            nullptr);
+      entry.request->CancelAndForgetObserver(NS_BINDING_ABORTED);
+      mImageCache.Remove(imageSrc);
+    }
+  }
+  return NS_OK;
+}
+
 /* virtual */ void
 nsTreeBodyFrame::DidSetStyleContext(nsStyleContext* aOldStyleContext)
 {
   nsLeafBoxFrame::DidSetStyleContext(aOldStyleContext);
 
   // Clear the style cache; the pointers are no longer even valid
   mStyleCache.Clear();
   // XXX The following is hacky, but it's not incorrect,

--- a/layout/xul/tree/nsTreeBodyFrame.h
+++ b/layout/xul/tree/nsTreeBodyFrame.h
@@ -113,16 +113,17 @@ public:
                                 const nsACString &aElt,
                                 int32_t *aX, int32_t *aY,
                                 int32_t *aWidth, int32_t *aHeight);
   nsresult IsCellCropped(int32_t aRow, nsITreeColumn *aCol, bool *aResult);
   nsresult RowCountChanged(int32_t aIndex, int32_t aCount);
   nsresult BeginUpdateBatch();
   nsresult EndUpdateBatch();
   nsresult ClearStyleAndImageCaches();
+  nsresult RemoveImageCacheEntry(int32_t aRowIndex, nsITreeColumn* aCol);
 
   void CancelImageRequests();
 
   void ManageReflowCallback(const nsRect& aRect, nscoord aHorzWidth);
 
   virtual nsSize GetXULMinSize(nsBoxLayoutState& aBoxLayoutState) override;
   virtual void SetXULBounds(nsBoxLayoutState& aBoxLayoutState, const nsRect& aRect,
                             bool aRemoveOverflowArea = false) override;

--- a/testing/modules/TestUtils.jsm
+++ b/testing/modules/TestUtils.jsm
@@ -56,9 +56,32 @@ this.TestUtils = {
           resolve([subject, data]);
         } catch (ex) {
           Services.obs.removeObserver(observer, topic);
           reject(ex);
         }
       }, topic);
     });
   },
+
+  /**
+   * Takes a screenshot of an area and returns it as a data URL.
+   *
+   * @param eltOrRect
+   *        The DOM node or rect ({left, top, width, height}) to screenshot.
+   * @param win
+   *        The current window.
+   */
+  screenshotArea(eltOrRect, win) {
+    if (eltOrRect instanceof Ci.nsIDOMElement) {
+      eltOrRect = eltOrRect.getBoundingClientRect();
+    }
+    let { left, top, width, height } = eltOrRect;
+    let canvas = win.document.createElementNS("http://www.w3.org/1999/xhtml", "canvas");
+    let ctx = canvas.getContext("2d");
+    let ratio = win.devicePixelRatio;
+    canvas.width = width * ratio;
+    canvas.height = height * ratio;
+    ctx.scale(ratio, ratio);
+    ctx.drawWindow(win, left, top, width, height, "#fff");
+    return canvas.toDataURL();
+  }
 };