cc: Fix bugs found by fuzzer due to floating point imprecision.

cc/tiles/picture_layer_tiling.cc

 // Copyright 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "cc/tiles/picture_layer_tiling.h"
 
 #include <stddef.h>
 
 #include <algorithm>
 #include <cmath>
@@ skipping 12 matching lines @@
 #include "cc/tiles/tile.h"
 #include "cc/tiles/tile_priority.h"
 #include "ui/gfx/geometry/point_conversions.h"
 #include "ui/gfx/geometry/rect_conversions.h"
 #include "ui/gfx/geometry/rect_f.h"
 #include "ui/gfx/geometry/safe_integer_conversions.h"
 #include "ui/gfx/geometry/size_conversions.h"
 
 namespace cc {
 
+namespace {
+float SnapToOne(float n) {
+  return (std::abs(1.f - n) < std::numeric_limits<float>::epsilon()) ? 1.f : n;
+}

[trchen, 2017/04/14 22:07:33]

I doubt this function works as intended...

By definition, epsilion is the difference between 1.f and the nearest machine
number, that means there is only one machine number within the range (1.f -
epsilion, 1.f + epsilon). That is, 1.f. In other words, this function is no-op
in theory.

C/C++ excessive precision rule complicates the issue. C++11 only requires
truncating to specified precision when binding value to a variable, but in
reality compilers may or may not respect the rule depends on compiler flags.

Nevertheless x86_64 targets now default to use SSE for FP implementation, which
doesn't carry excessive precision. Thus I still believe this function is no-op
(except for corner cases such as +-NaN, +-Inf).

[vmpstr, 2017/04/14 23:36:26]

The definition of epsilon is the difference between 1.f and the next
representable machine number. We need to be careful when generalizing this
definition to all numbers representable by a float. As a trivial example, there
are certainly numbers that are between 0 and epsilon, since the exponent of the
float can be large negative. Specifically in this case, the reasoning that that
there are no numbers representable in (1 - eps, 1 + eps) other than 1 itself is
not true, since the definition of epsilon does not mention anything that needs
to be representable in the (1 - eps, 1) range. Consider this:

float one = 1.f - std::numeric_limits<float>::epsilon() * .5f;

fprintf (stderr, "epsilon: %.10f\n", std::numeric_limits<float>::epsilon());
fprintf (stderr, "1 - one: %.10f\n", 1.f - one);

This yields:
epsilon: 0.0000001192
1 - one: 0.0000000596

which means that this number "one" is representable by float and is between (1 -
eps) and 1.

Multiplying this by some arbitrarily large int (such as 1 << 30) yields:
number * one = 1073741760
number * SnapToOne(one) = 1073741824 (= 1 << 30)

[trchen, 2017/04/14 23:53:43]

You're right. I forgot (1-epsilon) contains only 23 digits. But the only
exception is 1-2^-24. Your code would be equivalent to

constexpr float before_one = 1.f - std::numeric_limits<float>::epsilon() * 0.5f;
return (n == before_one) ? 1.f : n;

Why is the value special? Why is (1.f - epsilon) fine?

[vmpstr, 2017/04/15 00:31:24]

It just happens that when coverage scale is 7352.331055f and the raster
transform scale is 7352.331055f, then the math on lines 384-385 of the "before"
code makes the resulting scale be that. (That's the scale that fuzzer found).
I'm happy to use a larger epsilon.

Overall, I think we might have to rethink our whole approach to float scales in
combination with floating math and integer conversions when it comes to large
values, otherwise we'll keep running into situations like this.

[trchen, 2017/04/18 21:13:46]

Does this helps with the bug you're fixing? I seems to me it is mainly line
441~463 that adjusted the tile range to match coverage rect.

In general I feel snapping would make analysis harder, because error and
tolerance is a part of FP programming and snapping introduces one more error
source.

+}
+
 PictureLayerTiling::PictureLayerTiling(
     WhichTree tree,
     const gfx::AxisTransform2d& raster_transform,
     scoped_refptr<RasterSource> raster_source,
     PictureLayerTilingClient* client,
     float min_preraster_distance,
     float max_preraster_distance)
     : raster_transform_(raster_transform),
       client_(client),
       tree_(tree),
@@ skipping 330 matching lines @@
 }
 
 PictureLayerTiling::CoverageIterator::CoverageIterator() = default;
 
 PictureLayerTiling::CoverageIterator::CoverageIterator(
     const PictureLayerTiling* tiling,
     float coverage_scale,
     const gfx::Rect& coverage_rect)
     : tiling_(tiling),
       coverage_rect_(coverage_rect),
+      // Note that since this iterator will map possibly large numbers, it's
+      // very sensitive to small differences in scale (even less than epsilon).
+      // It is also very likely that this coverage iterator would be used with a
+      // scale that matches the contents scale (since majority of the time,
+      // we're rasterizing high res content. As a result, snap the scale to one
+      // if it's within the epsilon.
       coverage_to_content_(
-          gfx::PreScaleAxisTransform2d(tiling->raster_transform(),
-                                       1.f / coverage_scale)) {
+          SnapToOne(tiling->raster_transform().scale() / coverage_scale),
+          tiling->raster_transform().translation()) {
   DCHECK(tiling_);
   // In order to avoid artifacts in geometry_rect scaling and clamping to ints,
   // the |coverage_scale| should always be at least as big as the tiling's
   // raster scales.
   DCHECK_GE(coverage_scale, tiling_->raster_transform_.scale());
 
   // Clamp |coverage_rect| to the bounds of this tiling's raster source.
   coverage_rect_max_bounds_ =
       gfx::ScaleToCeiledSize(tiling->raster_source_->GetSize(), coverage_scale);
   coverage_rect_.Intersect(gfx::Rect(coverage_rect_max_bounds_));
@@ skipping 17 matching lines @@
   // Or in integer index:
   // wanted_texels(integer index) = (l:99, t:189, r:280, b:371)
   gfx::RectF content_rect =
       coverage_to_content_.MapRect(gfx::RectF(coverage_rect_));
   content_rect.Offset(-0.5f, -0.5f);
   gfx::Rect wanted_texels = gfx::ToEnclosingRect(content_rect);
 
   const TilingData& data = tiling_->tiling_data_;
   left_ = data.LastBorderTileXIndexFromSrcCoord(wanted_texels.x());
   top_ = data.LastBorderTileYIndexFromSrcCoord(wanted_texels.y());
+
   right_ = std::max(
       left_, data.FirstBorderTileXIndexFromSrcCoord(wanted_texels.right()));
   bottom_ = std::max(
       top_, data.FirstBorderTileYIndexFromSrcCoord(wanted_texels.bottom()));
 
+  // Unfortunately due to floating point math in ToEnclosingRect, wanted_texels
+  // could be lying about its dimensions. For example, consider the following:
+  //
+  // float a = 192.f;
+  // float b = 2104670720.f;
+  // output("%.0f\n", static_cast<double>(a + b) - b);
+  //
+  // This code prints out 256. So if that happens to be our coverage rect
+  // position and dimension, then the texel extent would try to grab something
+  // outside of it, resulting in a DCHECK later (or empty geometry rect with
+  // DCHECks disabled), which is undesirable. The solution is to simply
+  // backtrack the value until the content rect actually intersects the texel
+  // extent for the values we generated. Note this only happens with
+  // right/bottom values.
+  while (!content_rect.Intersects(data.TexelExtent(right_, top_)) &&

[enne (OOO), 2017/04/14 05:35:56]

Hmmm, do you think that FirstBorderTileXIndexFromSrcCoord should return the
correct value here, rather than having PictureLayerTiling do this work?

[vmpstr, 2017/04/14 18:17:42]

The problem is that FirstBorderTileXIndexFromSrcCoord takes a float, and at that
point we've already accessed "right()" which returns a wrong value... I'm happy
to do this some other way if there are other options.

[trchen, 2017/04/14 22:07:33]

Just double checked FirstBorderTileXIndexFromSrcCoord takes an int. Since
wanted_texels is integer rect, wanted_texels.right() must be accurate (unless it
overflowed). The accurate description of the problem would be wanted_texels
being inaccurate because ToEnclosingRect introduced errors.

I think it is possible to implement a version of ToEnclosingRect that is
accurate (and not too expensive!):

void EnclosingSegment(float x, float w, int& ox, int& ow)
__attribute__((optimize("no-associative-math")));
void EnclosingSegment(float x, float w, int& ox, int& ow) {
  float floorx = floorf(x);
  ox = static_cast<int>(floorx);
  float ceilw = ceilf(w);
  ow = static_cast<int>(ceilw);
  float delta = ceilf((x - floorx) + (w - ceilw));
  ow += static_cast<int>(delta);
}

[vmpstr, 2017/04/14 23:36:26]

Yes, I meant the access to right/bottom in enclosing rect is what causes the
issue.

[trchen, 2017/04/18 21:13:46]

Just sync'd up with enne@ offline. We agreed that there is some unknown
performance implication with accurate ToEnclosingRect. Needs to do it with a
separate CL and see if performance is acceptable.

Also ToEnclosingRect is not the only error source here. For example, line
427~429 could all introduce errors, not just in width/height but also x/y. (We
may even need fix-up for left_ and top_ too. I'll need to think about this
more.)

IMO doing fix-up here is the right thing to do, but I think this could be more
numerical robust. The most important invariant is to have iter->geometry_rect()
to cover coverage_rect. As content space and coverage space mapping can
introduce error, it is possible that a content_rect full coverage doesn't map to
coverage_rect full coverage.

I think we can do this: Refactor line 499~537 to a helper function (computes
canonical geometry rect for tile(i, j)). Then doing the fix-up here in coverage
space instead.

+         right_ > left_) {
+    --right_;
+  }
+  while (!content_rect.Intersects(data.TexelExtent(left_, bottom_)) &&
+         bottom_ > top_) {
+    --bottom_;
+  }
+
   tile_i_ = left_ - 1;
   tile_j_ = top_;
   ++(*this);
 }
 
 PictureLayerTiling::CoverageIterator::~CoverageIterator() {
 }
 
 PictureLayerTiling::CoverageIterator&
 PictureLayerTiling::CoverageIterator::operator++() {
   if (tile_j_ > bottom_)
     return *this;
 
   bool first_time = tile_i_ < left_;
   bool new_row = false;
   tile_i_++;
   if (tile_i_ > right_) {
     tile_i_ = left_;
     tile_j_++;
     new_row = true;
     if (tile_j_ > bottom_) {
       current_tile_ = NULL;
       return *this;
     }
   }
 
+  DCHECK_LT(tile_i_, tiling_->tiling_data_.num_tiles_x());
+  DCHECK_LT(tile_j_, tiling_->tiling_data_.num_tiles_y());
   current_tile_ = tiling_->TileAt(tile_i_, tile_j_);
 
   // Calculate the current geometry rect. As we reserved overlap between tiles
   // to accommodate bilinear filtering and rounding errors in destination
   // space, the geometry rect might overlap on the edges.
   gfx::Rect last_geometry_rect = current_geometry_rect_;
 
   gfx::RectF texel_extent = tiling_->tiling_data_.TexelExtent(tile_i_, tile_j_);
   {
     // Adjust tile extent to accommodate numerical errors.
@@ skipping 50 matching lines @@
     min_top = last_geometry_rect.bottom();
   } else {
     min_left = last_geometry_rect.right();
     min_top = last_geometry_rect.y();
   }
 
   int inset_left = std::max(0, min_left - current_geometry_rect_.x());
   int inset_top = std::max(0, min_top - current_geometry_rect_.y());
   current_geometry_rect_.Inset(inset_left, inset_top, 0, 0);
 
+#if DCHECK_IS_ON()

[enne (OOO), 2017/04/14 05:35:56]

Do you need these extra #ifs?

[vmpstr, 2017/04/14 18:17:42]

Not really, it's just everything is DCHECK in there.. I can remove.

   if (!new_row) {
     DCHECK_EQ(last_geometry_rect.right(), current_geometry_rect_.x());
     DCHECK_EQ(last_geometry_rect.bottom(), current_geometry_rect_.bottom());
     DCHECK_EQ(last_geometry_rect.y(), current_geometry_rect_.y());
   }
+#endif
 
   return *this;
 }
 
 gfx::Rect PictureLayerTiling::CoverageIterator::geometry_rect() const {
   return current_geometry_rect_;
 }
 
 gfx::RectF PictureLayerTiling::CoverageIterator::texture_rect() const {
   auto tex_origin = gfx::PointF(
@@ skipping 38 matching lines @@
     float ideal_contents_scale,
     const Occlusion& occlusion_in_layer_space) {
   // If we have, or had occlusions, mark the tiles as 'not done' to ensure that
   // we reiterate the tiles for rasterization.
   if (occlusion_in_layer_space.HasOcclusion() ||
       current_occlusion_in_layer_space_.HasOcclusion()) {
     set_all_tiles_done(false);
   }
 
   const float content_to_screen_scale =
-      ideal_contents_scale / raster_transform_.scale();
+      SnapToOne(ideal_contents_scale / raster_transform_.scale());
 
   const gfx::Rect* input_rects[] = {
       &visible_rect_in_layer_space, &skewport_in_layer_space,
       &soon_border_rect_in_layer_space, &eventually_rect_in_layer_space};
   gfx::Rect output_rects[4];
   for (size_t i = 0; i < arraysize(input_rects); ++i)
     output_rects[i] = EnclosingContentsRectFromLayerRect(*input_rects[i]);
   // Make sure the eventually rect is aligned to tile bounds.
   output_rects[3] =
       tiling_data_.ExpandRectIgnoringBordersToTileBounds(output_rects[3]);
@@ skipping 360 matching lines @@
   return ToEnclosingRect(raster_transform_.MapRect(gfx::RectF(layer_rect)));
 }
 
 gfx::Rect PictureLayerTiling::EnclosingLayerRectFromContentsRect(
     const gfx::Rect& contents_rect) const {
   return ToEnclosingRect(
       raster_transform_.InverseMapRect(gfx::RectF(contents_rect)));
 }
 
 }  // namespace cc