[SVN-2715] Recursion of copy_source_ops() causes stack overflow in Apache

• Type: Bug
• Status: Closed
• Priority: Critical
• Resolution: Fixed
• Affects Version/s: trunk
• Fix Version/s: 1.8-consider
• Component/s: libsvn_delta
• Assignee: Unassigned
• Reporter: Subversion Importer
• Created: 14/Feb/07 09:53
• Updated: 27/Oct/18 16:30
• Resolved: 26/Aug/11 09:47

Description

See URL.  In summary, libsvn_delta/compose_delta.c:copy_source_ops() can recurse
a large number of times (the linked report describes a recursion depth of nearly
2200 calls).

If I understand DannyB correctly, the delta combiner is intrinsically O(N^2)
when considering targe-copy instructions (i.e. as generated by vdelta), so this
level of recursion may well be unavoidable (though some independent
investigation of that might be nice).

The problem here is that we typically have a limited function-call stack, so an
overflow will terminate the process.  DannyB suggested (and I agree) that we
should convert copy_source_ops() from a recursive function to one that maintains
a pool-allocated stack, so that a deep recursion can only use up heap memory,
not C stack memory.

http://svn.haxx.se/dev/archive-2007-01/0709.shtml

Original issue reported by malcolm