New issue
Advanced search Search tips
Starred by 1 user

Issue metadata

Status: Fixed
Owner:
Closed: Jan 7
Cc:
Components:
EstimatedDays: ----
NextAction: ----
OS: ----
Pri: 3
Type: Bug



Sign in to add a comment
link

Issue 914933: [FCP++] Priority queue's assumption of constant properties is violated

Reported by maxlg@google.com, Dec 13 Project Member

Issue description

In our current design of ImagePaintTiming, we use priority queue for sorting the records. The priority queue provides O(1) operation to find the largest and last image in records.

However, the current usage of priority queue has a design problem. Priority queue depends on a comparison function to rank the entries. The comparison function has an assumption that the properties involving comparison remain constant during the whole life cycle. The current design has violated this assumption.

This is the comparison function, which involves a, b pointers and the first_size property.

static bool LargeImageOnTop(const base::WeakPtr<ImageRecord>& a,
                            const base::WeakPtr<ImageRecord>& b) {
  // null value should be at the bottom of the priority queue, so:
  // * When a == null && b!=null, we treat b as larger, return true.
  // * When a != null && b==null, we treat b as no larger than a, return false.
  // * When a == null && b==null, we treat b as no larger than a, return false.
  return (a && b) ? (a->first_size < b->first_size) : bool(b);
}

The violation happens when ImagePaintTimingDetector erases a ImageRecord pointer from |id_record_map_|. As the heap references the pointer as a WeakPtr, the erasing make the WeakPtr a nullptr.

The consequence of this bug is that the top of the heap doesn't always point to the largest value. For example, imagine that we have this heap at some point:

    A(8)
   /   \
  B(7)  C(5)
 /   \
D(6)  E(1)



At this time, if we make A and B nullptr, the sequence given by the heap will become A(null), C(5), E(6), D(1), B(null) which is out of order.
 

Comment 1 by maxlg@google.com, Dec 13

Cc: skobes@chromium.org tdres...@chromium.org
Components: Blink>PerformanceAPIs
Owner: maxlg@chromium.org
Status: Assigned (was: Untriaged)

Comment 2 by maxlg@google.com, Dec 13

Description: Show this description

Comment 3 by maxlg@google.com, Dec 13

Description: Show this description

Comment 4 by maxlg@google.com, Dec 13

Description: Show this description

Comment 5 by maxlg@google.com, Dec 13

Cc: bmcquade@chromium.org
+Bryan, FYI, I've just discovered a design issue within LargestImagePaint that makes the results inaccurate.

Comment 6 by maxlg@chromium.org, Dec 13

Solutions:
1. We keep adding nodes to the priority queue, never removing value from it. This will make the priority queue grow very quickly. This indicates that nodes keep being removed and reattached will add a lot of weight to the priority queue.
2. We resort the whole heap once we find the top node to be null. This will add some overhead if the largest image keeps being removed. If we can bet on the possibility that largest image won't be removed frequently, this would be relatively economical.

Comment 7 by bugdroid1@chromium.org, Dec 15

Project Member
The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/12a1fcaa108a2a13ab91180386285cd77709ea3e

commit 12a1fcaa108a2a13ab91180386285cd77709ea3e
Author: Liquan(Max) Gu <maxlg@chromium.org>
Date: Sat Dec 15 17:05:58 2018

[FCP++] Replace priority queue with ordered set

In our current design of ImagePaintTiming, we use priority queue to sort the
records. The priority queue provides O(1) operation to find the largest and
last image in records. However, the current usage of priority queue has a design
problem. Priority queue depends on a comparison function to rank the entries.
The comparison function has an assumption that the properties involving
comparison remain constant during the whole life cycle. The current design has
violated this assumption.

In order to fix this issue, we use ordered set to replace priority queue.
Ordered set allows us to iterate on entries by order of size or time, whereas
priority queue doesn't allow iteration unless popping up the head entry.

The new design also has a detached_ids to record the nodes that are detached
from the DOM node. While looking up the largest and last image, the detached
image will be ignored until it's reattached.

Bug:  914933 
Change-Id: I3728a375b4d622a8fa62911285e6b162504611e5
Reviewed-on: https://chromium-review.googlesource.com/c/1377726
Commit-Queue: Liquan (Max) Gu <maxlg@chromium.org>
Reviewed-by: Steve Kobes <skobes@chromium.org>
Cr-Commit-Position: refs/heads/master@{#616984}
[modify] https://crrev.com/12a1fcaa108a2a13ab91180386285cd77709ea3e/third_party/blink/renderer/core/paint/image_paint_timing_detector.cc
[modify] https://crrev.com/12a1fcaa108a2a13ab91180386285cd77709ea3e/third_party/blink/renderer/core/paint/image_paint_timing_detector.h
[modify] https://crrev.com/12a1fcaa108a2a13ab91180386285cd77709ea3e/third_party/blink/renderer/core/paint/image_paint_timing_detector_test.cc

Comment 8 by maxlg@chromium.org, Jan 7

Status: Fixed (was: Assigned)

Sign in to add a comment