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.