Operational Defect Database

BugZero found this defect 2498 days ago.

MongoDB | 377566

[SERVER-28971] Error in depth_first_search algorithm incorrectly recurses on visited nodes

Last update date:

10/30/2023

Affected products:

MongoDB Server

Affected releases:

3.5.6

Fixed releases:

3.4.5

3.5.7

Description:

Info

In one of our CR for SERVER-28348 we missed this logic bug. The recursion should only happen for nodes that we have not visited yet. def depth_first_search(self, node_key, nodes_visited, nodes_in_cycle=[]): """ The nodes_visited is a set of nodes which indicates it has been visited. The node_in_cycle is a list of nodes in the potential cycle. Returns the list of nodes in the cycle or None. """ nodes_visited.add(node_key) nodes_in_cycle.append(node_key) for node in self.nodes[node_key]['next_nodes']: if node in nodes_in_cycle: # The graph cycle starts at the index of node in nodes_in_cycle. return nodes_in_cycle[nodes_in_cycle.index(node):] if node in nodes_visited: <<<<------------ Should be "node not in nodes_visited" dfs_nodes = self.depth_first_search(node, nodes_visited, nodes_in_cycle) if dfs_nodes: return dfs_nodes   # This node_key is not part of the graph cycle. nodes_in_cycle.pop() return None

Top User Comments

xgen-internal-githook commented on Fri, 28 Apr 2017 20:55:12 +0000: Author: {u'username': u'elouie99', u'name': u'Eddie Louie', u'email': u'eddie.louie@mongodb.com'} Message: SERVER-28971 Error in depth_first_search algorithm incorrectly recurses on visited nodes (cherry picked from commit e2196c8ee508a99c0d9472f061414da2f79c1e50) Branch: v3.4 https://github.com/mongodb/mongo/commit/70cddc46ab0dee311711bffc16a61d02d413e506 xgen-internal-githook commented on Tue, 25 Apr 2017 21:45:53 +0000: Author: {u'username': u'elouie99', u'name': u'Eddie Louie', u'email': u'eddie.louie@mongodb.com'} Message: SERVER-28971 Error in depth_first_search algorithm incorrectly recurses on visited nodes Branch: master https://github.com/mongodb/mongo/commit/e2196c8ee508a99c0d9472f061414da2f79c1e50

Additional Resources / Links

Share:

BugZero Risk Score

Coming soon

Status

Closed

Have you been affected by this bug?

cost-cta-background

Do you know how much operational outages are costing you?

Understand the cost to your business and how BugZero can help you reduce those costs.

Discussion

Login to read and write comments.

Have you ever...

had your data corrupted from a

VMware

bug?

Search:

...