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

Stack overflow when parsing deeply nested $not query

    • Type: Icon: Bug Bug
    • Resolution: Done
    • Priority: Icon: Major - P3 Major - P3
    • 2.6.2, 2.7.0
    • Affects Version/s: 2.6.0, 2.6.1-rc0
    • Component/s: Querying
    • None
    • ALL
    • Hide

      The repro script is in Python because the shell prevents such deeply nested queries (see: SERVER-11781).

      from pymongo import MongoClient
      
      def main():
          c = MongoClient()
          db = c.test.nested_queries
      
          query = {"$not": {"$eq": 5}}
          for i in xrange(650):
              query = {"$not": query}
          query = {"a": query}
      
          print query
      
          db.find_one(query)
      
      if __name__ == "__main__":
          main()
      
      Show
      The repro script is in Python because the shell prevents such deeply nested queries (see: SERVER-11781 ). from pymongo import MongoClient def main(): c = MongoClient() db = c.test.nested_queries query = {"$not": {"$eq": 5}} for i in xrange(650): query = {"$not": query} query = {"a": query} print query db.find_one(query) if __name__ == "__main__": main()

      Issue Status as of May 28, 2014

      ISSUE SUMMARY
      The query depth limit of 100 is not applied to deeply nested $not queries. For example:

      db.coll.find({a: {$not: {$not: {$not: ... {$gt: 3} ... }}}})
      

      USER IMPACT
      Deeply nested $not queries crash mongod due to excessive recursion.

      WORKAROUNDS
      Rewrite the query to avoid excessive recursion.

      AFFECTED VERSIONS
      MongoDB production releases 2.6.0 and 2.6.1 are affected by this issue.

      FIX VERSION
      The fix is included in the 2.6.2 production release.

      RESOLUTION DETAILS
      The query depth limit of 100 now applies to $not trees.

      Original description

      The query depth limit of 100 (from SERVER-13661) is not applied to deeply nested $not queries. This leads to stack overflows due to excessive recursion.

      Partial backtrace:

          frame #0: 0x00000001002dd1b9 mongod-2.6.1-rc0`mongo::MatchExpressionParser::_parseNot(char const*, mongo::BSONElement const&) + 439
          frame #1: 0x00000001002d4f3a mongod-2.6.1-rc0`mongo::MatchExpressionParser::_parseSubField(mongo::BSONObj const&, mongo::AndMatchExpression const*, char const*, mongo::BSONElement const&) + 338
          frame #2: 0x00000001002d85b4 mongod-2.6.1-rc0`mongo::MatchExpressionParser::_parseSub(char const*, mongo::BSONObj const&, mongo::AndMatchExpression*) + 656
          frame #3: 0x00000001002dd26d mongod-2.6.1-rc0`mongo::MatchExpressionParser::_parseNot(char const*, mongo::BSONElement const&) + 619
          frame #4: 0x00000001002d4f3a mongod-2.6.1-rc0`mongo::MatchExpressionParser::_parseSubField(mongo::BSONObj const&, mongo::AndMatchExpression const*, char const*, mongo::BSONElement const&) + 338
          frame #5: 0x00000001002d85b4 mongod-2.6.1-rc0`mongo::MatchExpressionParser::_parseSub(char const*, mongo::BSONObj const&, mongo::AndMatchExpression*) + 656
          frame #6: 0x00000001002dd26d mongod-2.6.1-rc0`mongo::MatchExpressionParser::_parseNot(char const*, mongo::BSONElement const&) + 619
          frame #7: 0x00000001002d4f3a mongod-2.6.1-rc0`mongo::MatchExpressionParser::_parseSubField(mongo::BSONObj const&, mongo::AndMatchExpression const*, char const*, mongo::BSONElement const&) + 338
          frame #8: 0x00000001002d85b4 mongod-2.6.1-rc0`mongo::MatchExpressionParser::_parseSub(char const*, mongo::BSONObj const&, mongo::AndMatchExpression*) + 656
          frame #9: 0x00000001002dd26d mongod-2.6.1-rc0`mongo::MatchExpressionParser::_parseNot(char const*, mongo::BSONElement const&) + 619
          frame #10: 0x00000001002d4f3a mongod-2.6.1-rc0`mongo::MatchExpressionParser::_parseSubField(mongo::BSONObj const&, mongo::AndMatchExpression const*, char const*, mongo::BSONElement const&) + 338
          frame #11: 0x00000001002d85b4 mongod-2.6.1-rc0`mongo::MatchExpressionParser::_parseSub(char const*, mongo::BSONObj const&, mongo::AndMatchExpression*) + 656
      ...
          frame #1544: 0x00000001002d85b4 mongod-2.6.1-rc0`mongo::MatchExpressionParser::_parseSub(char const*, mongo::BSONObj const&, mongo::AndMatchExpression*) + 656
          frame #1545: 0x00000001002d9743 mongod-2.6.1-rc0`mongo::MatchExpressionParser::_parse(mongo::BSONObj const&, int) + 4125
          frame #1546: 0x00000001003ae465 mongod-2.6.1-rc0`mongo::CanonicalQuery::canonicalize(mongo::QueryMessage const&, mongo::CanonicalQuery**) + 85
          frame #1547: 0x00000001003d0525 mongod-2.6.1-rc0`mongo::newRunQuery(mongo::Message&, mongo::QueryMessage&, mongo::CurOp&, mongo::Message&) + 2725
          frame #1548: 0x00000001002a14a0 mongod-2.6.1-rc0`mongo::assembleResponse(mongo::Message&, mongo::DbResponse&, mongo::HostAndPort const&) + 1968
          frame #1549: 0x0000000100006ca4 mongod-2.6.1-rc0`mongo::MyMessageHandler::process(mongo::Message&, mongo::AbstractMessagingPort*, mongo::LastError*) + 308
          frame #1550: 0x0000000100671c51 mongod-2.6.1-rc0`mongo::PortMessageServer::handleIncomingMsg(void*) + 1681
          frame #1551: 0x00000001006e0c95 mongod-2.6.1-rc0`thread_proxy + 229
          frame #1552: 0x00007fff93d8b772 libsystem_c.dylib`_pthread_start + 327
          frame #1553: 0x00007fff93d781a1 libsystem_c.dylib`thread_start + 13
      

            Assignee:
            david.storch@mongodb.com David Storch
            Reporter:
            kamran.khan Kamran K.
            Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

              Created:
              Updated:
              Resolved: