Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-92930

GeoHash might downcast with undefined behavior for point near the edge of 2d index bounds

    • Type: Icon: Bug Bug
    • Resolution: Fixed
    • Priority: Icon: Major - P3 Major - P3
    • 8.1.0-rc0
    • Affects Version/s: None
    • Component/s: None
    • Query Integration
    • Fully Compatible
    • ALL
    • v8.0, v7.3, v7.0, v6.0, v5.0
    • Hide

      Create a 2d index, and insert a document with one coordinate eerily close to the max bounds. For example, 

       

      db.test.createIndex({loc: "2d"}, {min: -180, max: 0});
      db.test.insert({loc: [0, -0.0000000000001]})
      

      Upon insert, we reach the undefined behavior when trying to hash the value -0.0000000000001.

       

      Show
      Create a 2d index, and insert a document with one coordinate eerily close to the max bounds. For example,    db.test.createIndex({loc: "2d" }, {min: -180, max: 0}); db.test.insert({loc: [0, -0.0000000000001]}) Upon insert, we reach the undefined behavior when trying to hash the value -0.0000000000001.  
    • 200

      Since 2d indexes do not "wrap" (like how +180 and -180 longitude are the same on a sphere), we have to be careful that we do not treat the minimum and maximum bounds the same for a 2d index. We handle this when generating the geo hash as a special case when the value == the maximum bounds, by slightly decrementing the value (treating 180, for example, as 179.9999) before scaling it to compute the relevant geo index bucket for the key string.

      If the input value is not quite the maximum but very close, we may reach a case of undefined behavior. We've seen that in some cases, convertToDoubleHashScale may return 4,294,967,296, which is exactly the number of geo buckets we have (0-indexed). Once we cast that value to an unsigned int, we reach undefined behavior: depending on the architecture, it will either truncate to 4,294,967,295 (which is the value we'd hope for, indicating the maximum bounds geo bucket), or max overflow to 0 (which would treat it as if the index "wrapped" back around to the minimum bounds, incorrectly). In my local testing, I only observed the more ideal behavior, maintaining query correctness.

            Assignee:
            will.buerger@mongodb.com Will Buerger
            Reporter:
            will.buerger@mongodb.com Will Buerger
            Votes:
            0 Vote for this issue
            Watchers:
            5 Start watching this issue

              Created:
              Updated:
              Resolved: