Re: Stack overflow issue

Alexander Korotkov <aekorotkov@gmail.com> writes:
> The revised set of remaining patches is attached.
> ...
> 0003 Avoid recursion in MemoryContext functions
> I've renamed MemoryContextTraverse() => MemoryContextTraverseNext(),
> which I think is a bit more intuitive.  Also I fixed
> MemoryContextMemConsumed(), which was still trying to use the removed
> argument "print" of MemoryContextStatsInternal() function.

This patch still doesn't compile for me --- MemoryContextMemConsumed
got modified some more by commit 743112a2e, and needs minor fixes.

I initially didn't like the definition of MemoryContextTraverseNext
because it requires two copies of the "process node" logic.  However,
that seems fine for most of the callers, and even where we are
duplicating logic it's just a line or so, so I guess it's ok.
However, MemoryContextTraverseNext seems undercommented to me, plus
the claim that it traverses in depth-first order is just wrong.

I found some bugs in MemoryContextStatsInternal too: the old
logic assumed that ichild exceeding max_children was the only
way to get into the summarization logic, but now ichild minus
max_children could very well be negative.  Fortunately we can
just reset ichild to zero and not worry about having any
connection between the first loop and the second.

Here's a v5 of 0003 with those issues and some more-cosmetic ones
cleaned up.  I didn't look at 0001 or 0002.

            regards, tom lane

diff --git a/src/backend/utils/mmgr/mcxt.c b/src/backend/utils/mmgr/mcxt.c
index 1a615becae..5d426795d9 100644
--- a/src/backend/utils/mmgr/mcxt.c
+++ b/src/backend/utils/mmgr/mcxt.c
@@ -145,9 +145,10 @@ MemoryContext CurTransactionContext = NULL;
 /* This is a transient link to the active portal's memory context: */
 MemoryContext PortalContext = NULL;

+static void MemoryContextDeleteOnly(MemoryContext context);
 static void MemoryContextCallResetCallbacks(MemoryContext context);
 static void MemoryContextStatsInternal(MemoryContext context, int level,
-                                       bool print, int max_children,
+                                       int max_level, int max_children,
                                        MemoryContextCounters *totals,
                                        bool print_to_stderr);
 static void MemoryContextStatsPrint(MemoryContext context, void *passthru,
@@ -219,6 +220,50 @@ GetMemoryChunkHeader(const void *pointer)
     return header;
 }

+/*
+ * MemoryContextTraverseNext
+ *        Helper function to traverse all descendants of a memory context
+ *        without recursion.
+ *
+ * Recursion could lead to out-of-stack errors with deep context hierarchies,
+ * which would be unpleasant in error cleanup code paths.
+ *
+ * To process 'context' and all its descendants, use a loop like this:
+ *
+ *     <process 'context'>
+ *     for (MemoryContext curr = context->firstchild;
+ *          curr != NULL;
+ *          curr = MemoryContextTraverseNext(curr, context))
+ *     {
+ *         <process 'curr'>
+ *     }
+ *
+ * This visits all the contexts in pre-order, that is a node is visited
+ * before its children.
+ */
+static MemoryContext
+MemoryContextTraverseNext(MemoryContext curr, MemoryContext top)
+{
+    /* After processing a node, traverse to its first child if any */
+    if (curr->firstchild != NULL)
+        return curr->firstchild;
+
+    /*
+     * After processing a childless node, traverse to its next sibling if
+     * there is one.  If there isn't, traverse back up to the parent (which
+     * has already been visited, and now so have all its descendants).  We're
+     * done if that is "top", otherwise traverse to its next sibling if any,
+     * otherwise repeat moving up.
+     */
+    while (curr->nextchild == NULL)
+    {
+        curr = curr->parent;
+        if (curr == top)
+            return NULL;
+    }
+    return curr->nextchild;
+}
+
 /*
  * Support routines to trap use of invalid memory context method IDs
  * (from calling pfree or the like on a bogus pointer).  As a possible
@@ -375,14 +420,13 @@ MemoryContextResetOnly(MemoryContext context)
 void
 MemoryContextResetChildren(MemoryContext context)
 {
-    MemoryContext child;
-
     Assert(MemoryContextIsValid(context));

-    for (child = context->firstchild; child != NULL; child = child->nextchild)
+    for (MemoryContext curr = context->firstchild;
+         curr != NULL;
+         curr = MemoryContextTraverseNext(curr, context))
     {
-        MemoryContextResetChildren(child);
-        MemoryContextResetOnly(child);
+        MemoryContextResetOnly(curr);
     }
 }

@@ -392,21 +436,60 @@ MemoryContextResetChildren(MemoryContext context)
  *        allocated therein.
  *
  * The type-specific delete routine removes all storage for the context,
- * but we have to recurse to handle the children.
- * We must also delink the context from its parent, if it has one.
+ * but we have to deal with descendant nodes here.
  */
 void
 MemoryContextDelete(MemoryContext context)
+{
+    MemoryContext curr;
+
+    Assert(MemoryContextIsValid(context));
+
+    /*
+     * Delete subcontexts from the bottom up.
+     *
+     * Note: Do not use recursion here.  A "stack depth limit exceeded" error
+     * would be unpleasant if we're already in the process of cleaning up from
+     * transaction abort.  We also cannot use MemoryContextTraverseNext() here
+     * because we modify the tree as we go.
+     */
+    curr = context;
+    for (;;)
+    {
+        MemoryContext parent;
+
+        /* Descend down until we find a leaf context with no children */
+        while (curr->firstchild != NULL)
+            curr = curr->firstchild;
+
+        /*
+         * We're now at a leaf with no children. Free it and continue from the
+         * parent.  Or if this was the original node, we're all done.
+         */
+        parent = curr->parent;
+        MemoryContextDeleteOnly(curr);
+
+        if (curr == context)
+            break;
+        curr = parent;
+    }
+}
+
+/*
+ * Subroutine of MemoryContextDelete,
+ * to delete a context that has no children.
+ * We must also delink the context from its parent, if it has one.
+ */
+static void
+MemoryContextDeleteOnly(MemoryContext context)
 {
     Assert(MemoryContextIsValid(context));
     /* We had better not be deleting TopMemoryContext ... */
     Assert(context != TopMemoryContext);
     /* And not CurrentMemoryContext, either */
     Assert(context != CurrentMemoryContext);
-
-    /* save a function call in common case where there are no children */
-    if (context->firstchild != NULL)
-        MemoryContextDeleteChildren(context);
+    /* All the children should've been deleted already */
+    Assert(context->firstchild == NULL);

     /*
      * It's not entirely clear whether 'tis better to do this before or after
@@ -672,12 +755,12 @@ MemoryContextMemAllocated(MemoryContext context, bool recurse)

     if (recurse)
     {
-        MemoryContext child;
-
-        for (child = context->firstchild;
-             child != NULL;
-             child = child->nextchild)
-            total += MemoryContextMemAllocated(child, true);
+        for (MemoryContext curr = context->firstchild;
+             curr != NULL;
+             curr = MemoryContextTraverseNext(curr, context))
+        {
+            total += curr->mem_allocated;
+        }
     }

     return total;
@@ -691,9 +774,20 @@ void
 MemoryContextMemConsumed(MemoryContext context,
                          MemoryContextCounters *consumed)
 {
+    Assert(MemoryContextIsValid(context));
+
     memset(consumed, 0, sizeof(*consumed));

-    MemoryContextStatsInternal(context, 0, false, 0, consumed, false);
+    /* Examine the context itself */
+    context->methods->stats(context, NULL, NULL, consumed, false);
+
+    /* Examine children, using iteration not recursion */
+    for (MemoryContext curr = context->firstchild;
+         curr != NULL;
+         curr = MemoryContextTraverseNext(curr, context))
+    {
+        curr->methods->stats(curr, NULL, NULL, consumed, false);
+    }
 }

 /*
@@ -707,8 +801,8 @@ MemoryContextMemConsumed(MemoryContext context,
 void
 MemoryContextStats(MemoryContext context)
 {
-    /* A hard-wired limit on the number of children is usually good enough */
-    MemoryContextStatsDetail(context, 100, true);
+    /* Hard-wired limits are usually good enough */
+    MemoryContextStatsDetail(context, 100, 100, true);
 }

 /*
@@ -720,14 +814,16 @@ MemoryContextStats(MemoryContext context)
  * with fprintf(stderr), otherwise use ereport().
  */
 void
-MemoryContextStatsDetail(MemoryContext context, int max_children,
+MemoryContextStatsDetail(MemoryContext context,
+                         int max_level, int max_children,
                          bool print_to_stderr)
 {
     MemoryContextCounters grand_totals;

     memset(&grand_totals, 0, sizeof(grand_totals));

-    MemoryContextStatsInternal(context, 0, true, max_children, &grand_totals, print_to_stderr);
+    MemoryContextStatsInternal(context, 0, max_level, max_children,
+                               &grand_totals, print_to_stderr);

     if (print_to_stderr)
         fprintf(stderr,
@@ -736,7 +832,7 @@ MemoryContextStatsDetail(MemoryContext context, int max_children,
                 grand_totals.freespace, grand_totals.freechunks,
                 grand_totals.totalspace - grand_totals.freespace);
     else
-
+    {
         /*
          * Use LOG_SERVER_ONLY to prevent the memory contexts from being sent
          * to the connected client.
@@ -754,22 +850,22 @@ MemoryContextStatsDetail(MemoryContext context, int max_children,
                                  grand_totals.totalspace, grand_totals.nblocks,
                                  grand_totals.freespace, grand_totals.freechunks,
                                  grand_totals.totalspace - grand_totals.freespace)));
+    }
 }

 /*
  * MemoryContextStatsInternal
  *        One recursion level for MemoryContextStats
  *
- * Print this context if print is true, but in any case accumulate counts into
- * *totals (if given).
+ * Print stats for this context if possible, but in any case accumulate counts
+ * into *totals (if not NULL).
  */
 static void
 MemoryContextStatsInternal(MemoryContext context, int level,
-                           bool print, int max_children,
+                           int max_level, int max_children,
                            MemoryContextCounters *totals,
                            bool print_to_stderr)
 {
-    MemoryContextCounters local_totals;
     MemoryContext child;
     int            ichild;

@@ -777,65 +873,72 @@ MemoryContextStatsInternal(MemoryContext context, int level,

     /* Examine the context itself */
     context->methods->stats(context,
-                            print ? MemoryContextStatsPrint : NULL,
+                            MemoryContextStatsPrint,
                             (void *) &level,
                             totals, print_to_stderr);

     /*
-     * Examine children.  If there are more than max_children of them, we do
-     * not print the rest explicitly, but just summarize them.
+     * Examine children.
+     *
+     * If we are past the recursion depth limit or already running low on
+     * stack, do not print them explicitly but just summarize them. Similarly,
+     * if there are more than max_children of them, we do not print the rest
+     * explicitly, but just summarize them.
      */
-    memset(&local_totals, 0, sizeof(local_totals));
-
-    for (child = context->firstchild, ichild = 0;
-         child != NULL;
-         child = child->nextchild, ichild++)
+    child = context->firstchild;
+    ichild = 0;
+    if (level < max_level && !stack_is_too_deep())
     {
-        if (ichild < max_children)
+        for (; child != NULL && ichild < max_children;
+             child = child->nextchild, ichild++)
+        {
             MemoryContextStatsInternal(child, level + 1,
-                                       print, max_children,
+                                       max_level, max_children,
                                        totals,
                                        print_to_stderr);
-        else
-            MemoryContextStatsInternal(child, level + 1,
-                                       false, max_children,
-                                       &local_totals,
-                                       print_to_stderr);
+        }
     }

-    /* Deal with excess children */
-    if (ichild > max_children)
+    if (child != NULL)
     {
-        if (print)
+        /* Summarize the rest of the children, avoiding recursion. */
+        MemoryContextCounters local_totals;
+
+        memset(&local_totals, 0, sizeof(local_totals));
+
+        ichild = 0;
+        while (child != NULL)
+        {
+            child->methods->stats(child, NULL, NULL, &local_totals, false);
+            ichild++;
+            child = MemoryContextTraverseNext(child, context);
+        }
+
+        if (print_to_stderr)
         {
-            if (print_to_stderr)
-            {
-                int            i;
-
-                for (i = 0; i <= level; i++)
-                    fprintf(stderr, "  ");
-                fprintf(stderr,
-                        "%d more child contexts containing %zu total in %zu blocks; %zu free (%zu chunks); %zu
used\n",
-                        ichild - max_children,
-                        local_totals.totalspace,
-                        local_totals.nblocks,
-                        local_totals.freespace,
-                        local_totals.freechunks,
-                        local_totals.totalspace - local_totals.freespace);
-            }
-            else
-                ereport(LOG_SERVER_ONLY,
-                        (errhidestmt(true),
-                         errhidecontext(true),
-                         errmsg_internal("level: %d; %d more child contexts containing %zu total in %zu blocks; %zu
free(%zu chunks); %zu used", 
-                                         level,
-                                         ichild - max_children,
-                                         local_totals.totalspace,
-                                         local_totals.nblocks,
-                                         local_totals.freespace,
-                                         local_totals.freechunks,
-                                         local_totals.totalspace - local_totals.freespace)));
+            for (int i = 0; i <= level; i++)
+                fprintf(stderr, "  ");
+            fprintf(stderr,
+                    "%d more child contexts containing %zu total in %zu blocks; %zu free (%zu chunks); %zu used\n",
+                    ichild,
+                    local_totals.totalspace,
+                    local_totals.nblocks,
+                    local_totals.freespace,
+                    local_totals.freechunks,
+                    local_totals.totalspace - local_totals.freespace);
         }
+        else
+            ereport(LOG_SERVER_ONLY,
+                    (errhidestmt(true),
+                     errhidecontext(true),
+                     errmsg_internal("level: %d; %d more child contexts containing %zu total in %zu blocks; %zu free
(%zuchunks); %zu used", 
+                                     level,
+                                     ichild,
+                                     local_totals.totalspace,
+                                     local_totals.nblocks,
+                                     local_totals.freespace,
+                                     local_totals.freechunks,
+                                     local_totals.totalspace - local_totals.freespace)));

         if (totals)
         {
@@ -928,7 +1031,7 @@ MemoryContextStatsPrint(MemoryContext context, void *passthru,

 /*
  * MemoryContextCheck
- *        Check all chunks in the named context.
+ *        Check all chunks in the named context and its children.
  *
  * This is just a debugging utility, so it's not fancy.
  */
@@ -936,13 +1039,16 @@ MemoryContextStatsPrint(MemoryContext context, void *passthru,
 void
 MemoryContextCheck(MemoryContext context)
 {
-    MemoryContext child;
-
     Assert(MemoryContextIsValid(context));
-
     context->methods->check(context);
-    for (child = context->firstchild; child != NULL; child = child->nextchild)
-        MemoryContextCheck(child);
+
+    for (MemoryContext curr = context->firstchild;
+         curr != NULL;
+         curr = MemoryContextTraverseNext(curr, context))
+    {
+        Assert(MemoryContextIsValid(curr));
+        curr->methods->check(curr);
+    }
 }
 #endif

@@ -1183,14 +1289,15 @@ ProcessLogMemoryContextInterrupt(void)
     /*
      * When a backend process is consuming huge memory, logging all its memory
      * contexts might overrun available disk space. To prevent this, we limit
-     * the number of child contexts to log per parent to 100.
+     * the depth of the hierarchy, as well as the number of child contexts to
+     * log per parent to 100.
      *
      * As with MemoryContextStats(), we suppose that practical cases where the
      * dump gets long will typically be huge numbers of siblings under the
      * same parent context; while the additional debugging value from seeing
      * details about individual siblings beyond 100 will not be large.
      */
-    MemoryContextStatsDetail(TopMemoryContext, 100, false);
+    MemoryContextStatsDetail(TopMemoryContext, 100, 100, false);
 }

 void *
diff --git a/src/include/utils/memutils.h b/src/include/utils/memutils.h
index 7fd41d20ca..6e5fa72b0e 100644
--- a/src/include/utils/memutils.h
+++ b/src/include/utils/memutils.h
@@ -87,7 +87,8 @@ extern Size MemoryContextMemAllocated(MemoryContext context, bool recurse);
 extern void MemoryContextMemConsumed(MemoryContext context,
                                      MemoryContextCounters *consumed);
 extern void MemoryContextStats(MemoryContext context);
-extern void MemoryContextStatsDetail(MemoryContext context, int max_children,
+extern void MemoryContextStatsDetail(MemoryContext context,
+                                     int max_level, int max_children,
                                      bool print_to_stderr);
 extern void MemoryContextAllowInCriticalSection(MemoryContext context,
                                                 bool allow);