[SERVER-13731] Stack overflow when parsing deeply nested $not query Created: 24/Apr/14  Updated: 11/Jul/16  Resolved: 28/Apr/14

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 2.6.0, 2.6.1-rc0
Fix Version/s: 2.6.2, 2.7.0

Type: Bug Priority: Major - P3
Reporter: Kamran K. Assignee: David Storch
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Depends
Related
Operating System: ALL
Backport Completed:
Steps To Reproduce:

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()

Participants:

 Description   
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



 Comments   
Comment by Githook User [ 15/May/14 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: SERVER-13731 make depth limit in parsing work for deep trees other than AND and OR
(cherry picked from commit 78c850d9c512596a3a8f7e937840d67f52a14baf)
Branch: v2.6
https://github.com/mongodb/mongo/commit/5f50fe901bdd34c5c539c612e22b30f339e57e81

Comment by Githook User [ 28/Apr/14 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: SERVER-13731 make depth limit in parsing work for deep trees other than AND and OR
Branch: master
https://github.com/mongodb/mongo/commit/78c850d9c512596a3a8f7e937840d67f52a14baf

Generated at Thu Feb 08 03:32:42 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.