From 6e57576f2eeedcb8109cd9f84574fbdd7ec4fdc4 Mon Sep 17 00:00:00 2001
From: Brian Warner <warner@allmydata.com>
Date: Fri, 13 Mar 2009 16:31:35 -0700
Subject: [PATCH] dirnode deep_traverse: insert a turn break (fireEventually)
 at least once every 100 files, otherwise a CHK followed by more than 158 LITs
 can overflow the stack, sort of like #237.

---
 src/allmydata/dirnode.py             | 11 ++++++-
 src/allmydata/test/test_deepcheck.py | 47 ++++++++++++++++++++++++++++
 2 files changed, 57 insertions(+), 1 deletion(-)

diff --git a/src/allmydata/dirnode.py b/src/allmydata/dirnode.py
index 0aee386b..d8b65ba8 100644
--- a/src/allmydata/dirnode.py
+++ b/src/allmydata/dirnode.py
@@ -3,6 +3,7 @@ import os, time, math
 
 from zope.interface import implements
 from twisted.internet import defer
+from foolscap.eventual import fireEventually
 import simplejson
 from allmydata.mutable.common import NotMutableError
 from allmydata.mutable.filenode import MutableFileNode
@@ -537,9 +538,17 @@ class NewDirectoryNode:
                 dirkids.append( (child, childpath) )
             else:
                 filekids.append( (child, childpath) )
-        for (child, childpath) in filekids:
+        for i, (child, childpath) in enumerate(filekids):
             d.addCallback(lambda ignored, child=child, childpath=childpath:
                           walker.add_node(child, childpath))
+            # to work around the Deferred tail-recursion problem
+            # (specifically the defer.succeed flavor) requires us to avoid
+            # doing more than 158 LIT files in a row. We insert a turn break
+            # once every 100 files (LIT or CHK) to preserve some stack space
+            # for other code. This is a different expression of the same
+            # Twisted problem as in #237.
+            if i % 100 == 99:
+                d.addCallback(lambda ignored: fireEventually())
         for (child, childpath) in dirkids:
             d.addCallback(lambda ignored, child=child, childpath=childpath:
                           self._deep_traverse_dirnode(child, childpath,
diff --git a/src/allmydata/test/test_deepcheck.py b/src/allmydata/test/test_deepcheck.py
index 9b2318a2..a01d7809 100644
--- a/src/allmydata/test/test_deepcheck.py
+++ b/src/allmydata/test/test_deepcheck.py
@@ -12,6 +12,7 @@ from allmydata.scripts import runner
 from allmydata.interfaces import ICheckResults, ICheckAndRepairResults, \
      IDeepCheckResults, IDeepCheckAndRepairResults
 from allmydata.monitor import Monitor, OperationCancelledError
+from allmydata.uri import LiteralFileURI
 from twisted.web.client import getPage
 
 from allmydata.test.common import ErrorMixin, _corrupt_mutable_share_data, \
@@ -1156,3 +1157,49 @@ class DeepCheckWebBad(DeepCheckBase, unittest.TestCase):
                                          self.json_is_unrecoverable))
 
         return d
+
+class Large(DeepCheckBase, unittest.TestCase):
+    def test_lots_of_lits(self):
+        self.basedir = "deepcheck/Large/lots_of_lits"
+        self.set_up_grid()
+        # create the following directory structure:
+        #  root/
+        #   subdir/
+        #    000-large (CHK)
+        #    001-small (LIT)
+        #    002-small
+        #    ...
+        #    399-small
+        # then do a deepcheck and make sure it doesn't cause a
+        # Deferred-tail-recursion stack overflow
+
+        COUNT = 400
+        c0 = self.g.clients[0]
+        d = c0.create_empty_dirnode()
+        self.stash = {}
+        def _created_root(n):
+            self.root = n
+            return n
+        d.addCallback(_created_root)
+        d.addCallback(lambda root: root.create_empty_directory(u"subdir"))
+        def _add_children(subdir_node):
+            self.subdir_node = subdir_node
+            kids = []
+            for i in range(1, COUNT):
+                litnode = LiteralFileURI("%03d-data" % i)
+                kids.append( (u"%03d-small" % i, litnode) )
+            return subdir_node.set_children(kids)
+        d.addCallback(_add_children)
+        up = upload.Data("large enough for CHK" * 100, "")
+        d.addCallback(lambda ign: self.subdir_node.add_file(u"0000-large", up))
+
+        def _start_deepcheck(ignored):
+            return self.web(self.root, method="POST", t="stream-deep-check")
+        d.addCallback(_start_deepcheck)
+        def _check( (output, url) ):
+            units = list(self.parse_streamed_json(output))
+            self.failUnlessEqual(len(units), 2+COUNT+1)
+        d.addCallback(_check)
+
+        return d
+    test_lots_of_lits.timeout = 10
-- 
2.45.2