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(1) E(6)
Then, records A and B become nullptr as they are erased from the DOM. Popping three times from the heap will give A(8)-discarded, C(5), B(7)-discarded, E(6), D(1), which is out of order.
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(1) E(6)
Then, records A and B become nullptr as they are erased from the DOM. Popping three times from the heap will give A(null), C(5), B(null), E(6), D(1), which is out of order.
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(1) E(6)
At this time, if we make A and B nullptr, the sequence given by the heap will become A(null), C(5), B(null), E(6), D(1), which is out of order.
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.
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 1 by maxlg@google.com, Dec 13
Components: Blink>PerformanceAPIs
Owner: maxlg@chromium.org
Status: Assigned (was: Untriaged)