"light" recursive function explodes stack

This is a discussion on "light" recursive function explodes stack within the C++ Programming forums, part of the General Programming Boards category; Hello, As much as I know recursive programming is dangerous and possibly not scalable, I don't have much of a ...

  1. #1
    Registered User
    Join Date
    Apr 2011
    Posts
    5

    "light" recursive function explodes stack

    Hello,

    As much as I know recursive programming is dangerous and possibly not scalable, I don't have much of a choice here.

    To put it simply, I have a tree of elements that represent a hierarchy of components (FlowVR application), and my function, for every node, outputs a subgraph to a Graphviz DOT text file. Every node can contain subgraphs.

    Since I have some understanding of how the stack works, most of my variables are dynamically allocated to the heap. As a result I only have pointers and a few strings with tops 50 chars as local variables.

    Here's the recursive function's header:
    void renderNode(Component* node, ofstream& Fdot, int depth, Viewer* v)

    If I get it right, I'm only storing 3 bytes and an int in the callstack for every call.


    Here's the code. I am sorry, it is a bit beefy and perhaps "light" isn't deserved ^^.
    I have highlighted the recursive call.
    The code following the call shouldn't be related to my problem, but I've left it just in case.

    Here's the catch: this function stack overflows after only 1 to 3 recursive calls.
    And I have no bloody idea as to why.

    So my question essentially is...
    Where could such a problem come from? What could be causing it that I should investigate?

    Thanks a lot for your help,
    Xavier

    Code:
    void renderNode(Component* node, ofstream& Fdot, int depth, Viewer* v) {
    	// render a node and call recursively on children
    	/*
    	 * Symbols
    	 * -------
    	 *  ## C ## : Compute
    	 *  	The code following this symbol performs computation.
    	 *  	It could produce a formatted cluster label for instance.
    	 *
    	 *	## W ## : Write
    	 *		Following code will write to a target file.
    	 */
    
    	// Is the component a composite?
    	if (!node->children.empty()) {
    		// {component is a composite}
    		v->displayInfo("Component is a composite");
    		/*
    		 *
    		 */
    		// 1) Begin cluster
    		Fdot << genIndent(depth) << " subgraph cluster_" << sanitize(node->id) << " {\n";
    		/*
    		 *
    		 */
    		// 2) Generate a reasonably sized cluster label
    
    		// You can only see as far as the parent, provided there is one.
    		// Pick a filling color for the cluster.
    		// Write your results.
    
    		// ##..C ##
    
    		string clusterLabel;
    		if (node->parent == NULL || node->parent->parent == NULL)
    			// If we're looking at the root node => get the raw id
    			// If we're looking at a level 1 node, get the raw id too
    			clusterLabel = node->id;
    
    		else {
    			// There is a parent, and the parent isn't root.
    			// This means we have at least two delimiters in our id.
    			const string id = node->id;
    			// pos is the boundary between our component and it's parent
    			int pos = id.find_last_of('/');
    
    			// Get a substring and find out where the second boundary is.
    			// Truncate at second delimiter.
    			string subStr = id.substr(0, pos-1);
    			int pos2 = subStr.find_last_of('/');
    
    			clusterLabel = id.substr(pos2 +1);
    		}
    		// {clusterLabel is fit for duty and not sanitized, as it isn't a dot ID}
    
    		// ## W ## Cluster label and fillcolor
    
    		v->displayInfo("About to write to file");
    		Fdot << genIndent(depth+1) << " label=\"" << clusterLabel << "\";\n";
    		Fdot << genIndent(depth+1) << " fillcolor=\"#" << selectClusterFillColor(depth) << "\";\n";
    		/*
    		 *
    		 */
    		v->displayInfo("About to render children nodes");
    		// 3) Render children nodes
    		for (std::list<Component*>::iterator c = node->children.begin();
    				c != node->children.end();
    					c++) {
    			v->displayInfo("From composite -> renderNode");
    
    
    
    // RECURSIVE CALL
    
    
    			renderNode((*c), Fdot, depth+1, v);
    
    
    // RECURSIVE CALL
    
    		}
    		/*
    		 *
    		 */
    		// 4) Render ports
    
    		// ##..W ## Input
    		Fdot << genIndent(depth+1) << " subgraph " << sanitize(node->id) << "_inputPorts_ {\n";
    		Fdot << genIndent(depth+2) << " label=\"\"\n";
    		Fdot << genIndent(depth+2) << " rank=same\n";
    
    		// Browse through all the ports
    		for (std::list<Port*>::iterator p = node->ports.begin();
    				p != node->ports.end();
    					p++) {
    			if ((*p)->type == "INPUT") {
    				// We've found an input port
    				Fdot << genIndent(depth+2) << " " << sanitize(node->id) << "  " << (*p)->id
    						<< " [ label=\"" << (*p)->id << "\", shape=square, style=filled, fillcolor=" << determinePortColor(*p) << " ];\n";
    			}
    		}//{input ports rendered}
    
    		Fdot << genIndent(depth + 1) << " }\n";
    
    
    		// ##..W ##..Output
    		Fdot << genIndent(depth + 1) << " subgraph " << sanitize(node->id) << "_outputPorts_ {\n";
    		Fdot << genIndent(depth + 2) << " label=\"\"\n";
    		Fdot << genIndent(depth + 2) << " rank=same\n";
    
    		// Browse through all the ports
    		for (std::list<Port*>::iterator p = node->ports.begin(); p
    				!= node->ports.end(); p++) {
    			if ((*p)->type == "OUTPUT") {
    				// We've found an output port
    				Fdot << genIndent(depth + 2) << " " << sanitize(node->id)
    						<< "  " << (*p)->id << " [ label=\"" << (*p)->id
    						<< "\", shape=square, style=filled, fillcolor="
    						<< determinePortColor(*p) << " ];\n";
    			}
    		}//{output ports rendered}
    
    		Fdot << genIndent(depth + 1) << " }\n";
    
    		/*
    		 *
    		 */
    		// 5) Links
    
    		// If you're reaching a primitive's port, the separator you have to use is ':'
    		// On the other hand, if you're reaching a composite's port, the separator is '__'
    		// Be careful, as those are _two_ underscores.
    
    		// This naming convention for composite ports gets rid of a major conflict and introduces a smaller one instead.
    		// Thanks to this addition, you can have a port "A" and a component "A" living in the same composite.
    		// But you can't have a port "A" and a component "_A" in the same composite, as those will collide.
    		// You can have a port "_A" and a component "A" though.
    
    		// This should not happen, but you never know.
    		// The easy way to tackle this is to forbid component names to begin with an underscore.
    
    		// If you are willing to change this naming convention,
    		// be well aware that only alphanumerical characters and underscores are allowed in a DOT ID.
    
    
    		// ##..C ##..\AND/ ##..W ## mixed
    
    		// Process every link
    		for (std::list<LinkBetweenComponents*>::iterator l = node->links.begin();
    				l != node->links.end();
    					l++) {
    
    
    			// Let's find source
    			if ((*l)->source == node->id) {
    				// source is the working node
    
    				// ## W ##
    
    				Fdot << genIndent(depth+1) << " " << sanitize((*l)->source) << "__" << (*l)->outport << " ->";
    				// {we're done with the source}
    
    			} else {
    				// source is not the working node
    				// Browse through children components to find it
    				for (std::list<Component*>::iterator c = node->children.begin();
    						c != node->children.end();
    							c++) {
    					if ((*c)->id == (*l)->source) {
    						// We have found the source node
    						if (!(*c)->children.empty()) {
    							// Source node is a composite
    
    							// ## W ##
    
    							Fdot << genIndent(depth+1) << " " << sanitize((*l)->source) << "__" << (*l)->outport << " ->";
    						} else {
    							// Source node is a primitive
    
    							// ## W ##
    
    							Fdot << genIndent(depth+1) << " " << sanitize((*l)->source) << ":" << (*l)->outport << " ->";
    						}
    						// {we're done with the source}
    					}
    				}
    			}
    			// {source part of the link written}
    
    
    			// Let's find dest
    			if ((*l)->dest == node->id) {
    				// dest is the working node
    
    				// ## W ##
    
    				Fdot << sanitize((*l)->dest) << "__" << (*l)->inport << "\n";
    				// {we're done with the dest}
    
    			} else {
    				// dest is not the working node
    				// Browse through children components to find it
    				for (std::list<Component*>::iterator c = node->children.begin(); c
    						!= node->children.end(); c++) {
    
    					if ((*c)->id == (*l)->dest) {
    						// We have found the dest node
    						if (!(*c)->children.empty()) {
    							// Dest node is a composite
    
    							// ## W ##
    
    							Fdot << sanitize((*l)->dest) << "__" << (*l)->inport << "\n";
    						} else {
    							// Dest node is a primitive
    
    							// ## W ##
    
    							Fdot << sanitize((*l)->dest) << ":" << (*l)->inport << "\n";
    						}
    						// {we're done with the dest}
    					}
    				}
    			}
    			// {dest part of the link written}
    			// {link written}
    
    		}// {all links are processed}
    
    		Fdot << genIndent(depth) << " }\n";
    		// #end cluster
    		v->displayInfo("End of composite");
    	}//#endcomposite
    	else if (node->type == "connection") {
    		Fdot << genIndent(depth) << " " << sanitize(node->id) << " [ shape=" << shapeToUse(node->type) << ", label=\"" << generateLabel(node) << "\" ];\n";
    	} else {
    		// {component is a primitive}
    		Fdot << genIndent(depth) << " " << sanitize(node->id) << " [ shape=" << shapeToUse(node->type) << ", style=" << selectStyle(node) << ", fillcolor=" << selectFillColor(node) << ", label=\"" << generateLabel(node) << "\" ];\n";
    	}
    }

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,540
    > If I get it right, I'm only storing 3 bytes and an int in the callstack for every call.
    References and pointers would typically be 4 bytes each (on a 32-bit machine).

    Then you have several local variables and loop variables (which may be optimised out)

    > Here's the catch: this function stack overflows after only 1 to 3 recursive calls.
    That seems like you have another problem instead.
    What is the exact error message?

    One way to blow the stack quickly is to have very large local arrays. I didn't see any in that code, but you could have already pushed close to the limit in some outer level caller, such that it only takes a few recursive calls here to tip over the edge.

    Here's how to tell how large each stack frame is
    Code:
    void foo ( void ) {
      volatile int dummy = 1;
      cout << (void*)&dummy;
      foo();
    }
    If you compare the address of dummy on adjacent pairs of calls, you can work out what each stack frame is costing you.

    Which OS/Compiler are you using?
    There is usually an option to increase the default stack size of a process.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Apr 2011
    Posts
    5
    Quote Originally Posted by Salem View Post
    > Here's the catch: this function stack overflows after only 1 to 3 recursive calls.
    That seems like you have another problem instead.
    What is the exact error message?
    The error message is... dynamic.

    Sometimes I can go through two recursive calls. In which case I get this message:
    Code:
    ./build-glgraph.sh: line 6: 20024 Erreur de segmentation  ./bin/flowvr-glgraph /home/martinx/flowvr/flowvr-suite-hierarchy/primes.adl.out.xml
    When I get this message, the '20024' varies but remains in this region.
    But sometimes I can't even get one call in, and I get this big report:

    Code:
    *** glibc detected *** ./bin/flowvr-glgraph: free(): invalid pointer: 0x00007fffb74bfd18 ***
    ======= Backtrace: =========
    /lib/libc.so.6(+0x71ad6)[0x7fe2f8b1fad6]
    /lib/libc.so.6(cfree+0x6c)[0x7fe2f8b2484c]
    /usr/lib/libstdc++.so.6(_ZNSsD1Ev+0x39)[0x7fe2f934fee9]
    ./bin/flowvr-glgraph(_Z10renderNodeP9ComponentRSt14basic_ofstreamIcSt11char_traitsIcEEiP6Viewer+0x15d)[0x476d95]
    ./bin/flowvr-glgraph(_ZN6Viewer7adl2dotEPKcS1_+0xaf)[0x45e2ef]
    ./bin/flowvr-glgraph(_ZN6Viewer11load_file_2E7QString+0xdc3)[0x45f337]
    ./bin/flowvr-glgraph(main+0x2a9e)[0x46c38a]
    /lib/libc.so.6(__libc_start_main+0xfd)[0x7fe2f8accc4d]
    ./bin/flowvr-glgraph[0x450889]
    ======= Memory map: ========
    00400000-00527000 r-xp 00000000 fe:01 12820780                           /home/martinx/flowvr/flowvr-suite-hierarchy/INSTALL/bin/flowvr-glgraph
    00726000-00729000 rw-p 00126000 fe:01 12820780                           /home/martinx/flowvr/flowvr-suite-hierarchy/INSTALL/bin/flowvr-glgraph
    00729000-0072a000 rw-p 00000000 00:00 0 
    009ae000-01533000 rw-p 00000000 00:00 0                                  [heap]
    7fe2e0000000-7fe2e0021000 rw-p 00000000 00:00 0 
    7fe2e0021000-7fe2e4000000 ---p 00000000 00:00 0 
    7fe2e6326000-7fe2e6386000 rw-s 00000000 00:04 3342351                    /SYSV00000000 (deleted)
    7fe2e6386000-7fe2e63a1000 r--s 00000000 fe:00 1165427                    /usr/share/mime/mime.cache
    7fe2e63a1000-7fe2e63ae000 r-xp 00000000 fe:00 1114415                    /lib/libudev.so.0.9.3
    7fe2e63ae000-7fe2e65ad000 ---p 0000d000 fe:00 1114415                    /lib/libudev.so.0.9.3
    7fe2e65ad000-7fe2e65ae000 r--p 0000c000 fe:00 1114415                    /lib/libudev.so.0.9.3
    7fe2e65ae000-7fe2e65af000 rw-p 0000d000 fe:00 1114415                    /lib/libudev.so.0.9.3
    7fe2e65af000-7fe2e65c7000 r-xp 00000000 fe:00 25754                      /usr/lib/gvfs/libgvfscommon.so
    7fe2e65c7000-7fe2e67c7000 ---p 00018000 fe:00 25754                      /usr/lib/gvfs/libgvfscommon.so
    7fe2e67c7000-7fe2e67c8000 rw-p 00018000 fe:00 25754                      /usr/lib/gvfs/libgvfscommon.so
    7fe2e67c8000-7fe2e67f1000 r-xp 00000000 fe:00 25748                      /usr/lib/gio/modules/libgvfsdbus.so
    7fe2e67f1000-7fe2e69f1000 ---p 00029000 fe:00 25748                      /usr/lib/gio/modules/libgvfsdbus.so
    7fe2e69f1000-7fe2e69f2000 rw-p 00029000 fe:00 25748                      /usr/lib/gio/modules/libgvfsdbus.so
    7fe2e69f2000-7fe2e69f3000 rw-p 00000000 00:00 0 
    7fe2e69f3000-7fe2e6f31000 r--p 00000000 fe:00 1175112                    /usr/share/icons/hicolor/icon-theme.cache
    7fe2e6f31000-7fe2e9e97000 r--p 00000000 fe:00 1175108                    /usr/share/icons/gnome/icon-theme.cache
    7fe2e9e97000-7fe2ea634000 rw-p 00000000 00:00 0 
    7fe2ea634000-7fe2ea6cf000 r--p 00000000 fe:00 1164007                    /usr/share/fonts/truetype/ttf-dejavu/DejaVuSans.ttf
    7fe2ea6cf000-7fe2ea72f000 r-xp 00000000 fe:00 1126611                    /usr/lib/libtiff.so.4.3.3
    7fe2ea72f000-7fe2ea92f000 ---p 00060000 fe:00 1126611                    /usr/lib/libtiff.so.4.3.3
    7fe2ea92f000-7fe2ea932000 rw-p 00060000 fe:00 1126611                    /usr/lib/libtiff.so.4.3.3
    7fe2ea932000-7fe2ea939000 r-xp 00000000 fe:00 82646                      /usr/lib/qt4/plugins/imageformats/libqtiff.so
    7fe2ea939000-7fe2eab38000 ---p 00007000 fe:00 82646                      /usr/lib/qt4/plugins/imageformats/libqtiff.so
    7fe2eab38000-7fe2eab39000 rw-p 00006000 fe:00 82646                      /usr/lib/qt4/plugins/imageformats/libqtiff.so
    7fe2eab39000-7fe2eab92000 r-xp 00000000 fe:00 557630                     /usr/lib/libQtSvg.so.4.6.3
    7fe2eab92000-7fe2ead91000 ---p 00059000 fe:00 557630                     /usr/lib/libQtSvg.so.4.6.3
    7fe2ead91000-7fe2ead94000 rw-p 00058000 fe:00 557630                     /usr/lib/libQtSvg.so.4.6.3
    7fe2ead94000-7fe2ead98000 r-xp 00000000 fe:00 82731                      /usr/lib/qt4/plugins/imageformats/libqsvg.so
    7fe2ead98000-7fe2eaf97000 ---p 00004000 fe:00 82731                      /usr/lib/qt4/plugins/imageformats/libqsvg.so
    7fe2eaf97000-7fe2eaf98000 rw-p 00003000 fe:00 82731                      /usr/lib/qt4/plugins/imageformats/libqsvg.so
    7fe2eaf98000-7fe2eafcd000 r-xp 00000000 fe:00 1129800                    /usr/lib/liblcms.so.1.0.18
    7fe2eafcd000-7fe2eb1cc000 ---p 00035000 fe:00 1129800                    /usr/lib/liblcms.so.1.0.18
    7fe2eb1cc000-7fe2eb1ce000 rw-p 00034000 fe:00 1129800                    /usr/lib/liblcms.so.1.0.18
    7fe2eb1ce000-7fe2eb1d0000 rw-p 00000000 00:00 0 
    7fe2eb1d0000-7fe2eb254000 r-xp 00000000 fe:00 557320                     /usr/lib/libmng.so.1.1.0.10
    7fe2eb254000-7fe2eb453000 ---p 00084000 fe:00 557320                     /usr/lib/libmng.so.1.1.0.10
    7fe2eb453000-7fe2eb458000 rw-p 00083000 fe:00 557320                     /usr/lib/libmng.so.1.1.0.10
    7fe2eb458000-7fe2eb45e000 r-xp 00000000 fe:00 82645                      /usr/lib/qt4/plugins/imageformats/libqmng.so
    7fe2eb45e000-7fe2eb65d000 ---p 00006000 fe:00 82645                      /usr/lib/qt4/plugins/imageformats/libqmng.so
    7fe2eb65d000-7fe2eb65e000 rw-p 00005000 fe:00 82645                      /usr/lib/qt4/plugins/imageformats/libqmng.so
    7fe2eb65e000-7fe2eb681000 r-xp 00000000 fe:00 1126538                    /usr/lib/libjpeg.so.62.0.0
    7fe2eb681000-7fe2eb880000 ---p 00023000 fe:00 1126538                    /usr/lib/libjpeg.so.62.0.0
    7fe2eb880000-7fe2eb881000 rw-p 00022000 fe:00 1126538                    /usr/lib/libjpeg.so.62.0.0
    7fe2eb89a000-7fe2eb8a2000 r-xp 00000000 fe:00 82644                      /usr/lib/qt4/plugins/imageformats/libqjpeg.so
    7fe2eb8a2000-7fe2ebaa2000 ---p 00008000 fe:00 82644                      /usr/lib/qt4/plugins/imageformats/libqjpeg.so
    7fe2ebaa2000-7fe2ebaa3000 rw-p 00008000 fe:00 82644                      /usr/lib/qt4/plugins/imageformats/libqjpeg.so
    7fe2ebaa3000-7fe2ebaaa000 r-xp 00000000 fe:00 82643                      /usr/lib/qt4/plugins/imageformats/libqico.so
    7fe2ebaaa000-7fe2ebca9000 ---p 00007000 fe:00 82643                      /usr/lib/qt4/plugins/imageformats/libqico.so
    7fe2ebca9000-7fe2ebcaa000 rw-p 00006000 fe:00 82643                      /usr/lib/qt4/plugins/imageformats/libqico.so
    7fe2ebcaa000-7fe2ebcb1000 r-xp 00000000 fe:00 82642                      /usr/lib/qt4/plugins/imageformats/libqgif.so
    7fe2ebcb1000-7fe2ebeb0000 ---p 00007000 fe:00 82642                      /usr/lib/qt4/plugins/imageformats/libqgif.so
    7fe2ebeb0000-7fe2ebeb1000 rw-p 00006000 fe:00 82642                      /usr/lib/qt4/plugins/imageformats/libqgif.so
    7fe2ebeb1000-7fe2ec37c000 rw-p 00000000 00:00 0 
    7fe2ec37c000-7fe2ec5bb000 r-xp 00000000 fe:00 279882                     /usr/lib/dri/swrast_dri.so
    7fe2ec5bb000-7fe2ec7ba000 ---p 0023f000 fe:00 279882                     /usr/lib/dri/swrast_dri.so
    7fe2ec7ba000-7fe2ec7c3000 rw-p 0023e000 fe:00 279882                     /usr/lib/dri/swrast_dri.so
    7fe2ec7c3000-7fe2ec7d2000 rw-p 00000000 00:00 0 
    7fe2ec7d2000-7fe2ec7d3000 r-xp 00000000 fe:00 1165083                    /usr/lib/gtk-2.0/2.10.0/immodules/im-cedilla.so
    7fe2ec7d3000-7fe2ec9d3000 ---p 00001000 fe:00 1165083                    /usr/lib/gtk-2.0/2.10.0/immodules/im-cedilla.so
    7fe2ec9d3000-7fe2ec9d4000 rw-p 00001000 fe:00 1165083                    /usr/lib/gtk-2.0/2.10.0/immodules/im-cedilla.so
    7fe2ec9d4000-7fe2eca6f000 r--p 00000000 fe:00 1164007                    /usr/share/fonts/truetype/ttf-dejavu/DejaVuSans.ttf
    7fe2eca6f000-7fe2eca71000 r-xp 00000000 fe:00 1164976                    /usr/lib/pango/1.6.0/modules/pango-basic-fc.so
    7fe2eca71000-7fe2ecc70000 ---p 00002000 fe:00 1164976                    /usr/lib/pango/1.6.0/modules/pango-basic-fc.so
    7fe2ecc70000-7fe2ecc71000 rw-p 00001000 fe:00 1164976                    /usr/lib/pango/1.6.0/modules/pango-basic-fc.so
    7fe2ecc71000-7fe2ecc9c000 r-xp 00000000 fe:00 1183751                    /usr/lib/gtk-2.0/2.10.0/engines/libclearlooks.so
    7fe2ecc9c000-7fe2ece9c000 ---p 0002b000 fe:00 1183751                    /usr/lib/gtk-2.0/2.10.0/engines/libclearlooks.so
    7fe2ece9c000-7fe2ece9d000 rw-p 0002b000 fe:00 1183751                    /usr/lib/gtk-2.0/2.10.0/engines/libclearlooks.so
    7fe2ece9d000-7fe2ecea6000 r-xp 00000000 fe:00 1126392                    /usr/lib/libltdl.so.7.2.1
    7fe2ecea6000-7fe2ed0a5000 ---p 00009000 fe:00 1126392                    /usr/lib/libltdl.so.7.2.1
    7fe2ed0a5000-7fe2ed0a6000 rw-p 00008000 fe:00 1126392                    /usr/lib/libltdl.so.7.2.1
    7fe2ed0a6000-7fe2ed0b4000 r-xp 00000000 fe:00 1126396                    /usr/lib/libtdb.so.1.2.1
    7fe2ed0b4000-7fe2ed2b3000 ---p 0000e000 fe:00 1126396                    /usr/lib/libtdb.so.1.2.1
    7fe2ed2b3000-7fe2ed2b4000 rw-p 0000d000 fe:00 1126396                    /usr/lib/libtdb.so.1.2.1
    7fe2ed2b4000-7fe2ed2ba000 r-xp 00000000 fe:00 1126394                    /usr/lib/libogg.so.0.7.0
    7fe2ed2ba000-7fe2ed4b9000 ---p 00006000 fe:00 1126394                    /usr/lib/libogg.so.0.7.0
    7fe2ed4b9000-7fe2ed4ba000 rw-p 00005000 fe:00 1126394                    /usr/lib/libogg.so.0.7.0
    7fe2ed4ba000-7fe2ed4e5000 r-xp 00000000 fe:00 1126398                    /usr/lib/libvorbis.so.0.4.4
    7fe2ed4e5000-7fe2ed6e5000 ---p 0002b000 fe:00 1126398                    /usr/lib/libvorbis.so.0.4.4
    7fe2ed6e5000-7fe2ed6e6000 rw-p 0002b000 fe:00 1126398                    /usr/lib/libvorbis.so.0.4.4
    7fe2ed6e6000-7fe2ed6ed000 r-xp 00000000 fe:00 1126401                    /usr/lib/libvorbisfile.so.3.3.2
    7fe2ed6ed000-7fe2ed8ec000 ---p 00007000 fe:00 1126401                    /usr/lib/libvorbisfile.so.3.3.2
    7fe2ed8ec000-7fe2ed8ed000 rw-p 00006000 fe:00 1126401                    /usr/lib/libvorbisfile.so.3.3.2
    7fe2ed8ed000-7fe2ed8fc000 r-xp 00000000 fe:00 1126404                    /usr/lib/libcanberra.so.0.2.3
    7fe2ed8fc000-7fe2edafc000 ---p 0000f000 fe:00 1126404                    /usr/lib/libcanberra.so.0.2.3
    7fe2edafc000-7fe2edafd000 rw-p 0000f000 fe:00 1126404                    /usr/lib/libcanberra.so.0.2.3
    7fe2edafd000-7fe2edb01000 r-xp 00000000 fe:00 1126675                    /usr/lib/libcanberra-gtk.so.0.1.6
    7fe2edb01000-7fe2edd00000 ---p 00004000 fe:00 1126675                    /usr/lib/libcanberra-gtk.so.0.1.6
    7fe2edd00000-7fe2edd01000 rw-p 00003000 fe:00 1126675                    /usr/lib/libcanberra-gtk.so.0.1.6
    7fe2edd0e000-7fe2edd1a000 r--p 00000000 fe:00 1214734                    /usr/share/locale/fr/LC_MESSAGES/glib20.mo
    7fe2edd1a000-7fe2edd1f000 r-xp 00000000 fe:00 27409                      /usr/lib/gtk-2.0/modules/libcanberra-gtk-module.so
    7fe2edd1f000-7fe2edf1f000 ---p 00005000 fe:00 27409                      /usr/lib/gtk-2.0/modules/libcanberra-gtk-module.so
    7fe2edf1f000-7fe2edf20000 rw-p 00005000 fe:00 27409                      /usr/lib/gtk-2.0/modules/libcanberra-gtk-module.so
    7fe2edf20000-7fe2edf4a000 r--p 00000000 fe:00 1126463                    /usr/share/locale/fr/LC_MESSAGES/gtk20-properties.mo
    7fe2edf4a000-7fe2edf4d000 r-xp 00000000 fe:00 1126240                    /usr/lib/libgpg-error.so.0.4.0
    7fe2edf4d000-7fe2ee14c000 ---p 00003000 fe:00 1126240                    /usr/lib/libgpg-error.so.0.4.0
    7fe2ee14c000-7fe2ee14d000 rw-p 00002000 fe:00 1126240                    /usr/lib/libgpg-error.so.0.4.0
    7fe2ee14d000-7fe2ee15d000 r-xp 00000000 fe:00 1126244                    /usr/lib/libtasn1.so.3.1.9
    7fe2ee15d000-7fe2ee35c000 ---p 00010000 fe:00 1126244                    /usr/lib/libtasn1.so.3.1.9
    7fe2ee35c000-7fe2ee35d000 rw-p 0000f000 fe:00 1126244                    /usr/lib/libtasn1.so.3.1.9
    7fe2ee35d000-7fe2ee43b000 r-xp 00000000 fe:00 1126390                    /usr/lib/libasound.so.2.0.0
    7fe2ee43b000-7fe2ee63a000 ---p 000de000 fe:00 1126390                    /usr/lib/libasound.so.2.0.0
    7fe2ee63a000-7fe2ee642000 rw-p 000dd000 fe:00 1126390                    /usr/lib/libasound.so.2.0.0
    7fe2ee642000-7fe2ee6b6000 r-xp 00000000 fe:00 1126242                    /usr/lib/libgcrypt.so.11.5.3
    7fe2ee6b6000-7fe2ee8b6000 ---p 00074000 fe:00 1126242                    /usr/lib/libgcrypt.so.11.5.3
    7fe2ee8b6000-7fe2ee8ba000 rw-p 00074000 fe:00 1126242                    /usr/lib/libgcrypt.so.11.5.3
    7fe2ee8ba000-7fe2ee8bc000 r-xp 00000000 fe:00 1114128                    /lib/libutil-2.11.2.so
    7fe2ee8bc000-7fe2eeabb000 ---p 00002000 fe:00 1114128                    /lib/libutil-2.11.2.so
    7fe2eeabb000-7fe2eeabc000 r--p 00001000 fe:00 1114128                    /lib/libutil-2.11.2.so./build-glgraph.sh: line 6: 21959 Abandon                 ./bin/flowvr-glgraph /home/martinx/flowvr/flowvr-suite-hierarchy/primes.adl.out.xml
    I've never seen anything like it.

    Quote Originally Posted by Salem View Post
    One way to blow the stack quickly is to have very large local arrays. I didn't see any in that code, but you could have already pushed close to the limit in some outer level caller, such that it only takes a few recursive calls here to tip over the edge.

    Here's how to tell how large each stack frame is
    Code:
    void foo ( void ) {
      volatile int dummy = 1;
      cout << (void*)&dummy;
      foo();
    }
    If you compare the address of dummy on adjacent pairs of calls, you can work out what each stack frame is costing you.
    Truth be told, the outer level caller might be a good candidate.
    My work is adding a layer on top of an application that wasn't 'properly' coded; I'll look into it.

    About your code, that is a nice trick, thanks
    Unfortunately, for some reason, I can't write to the console. (The application is written with Qt if that has anything to do with it)

    I'm using this code to try and achieve the same result:
    Code:
    		for (std::list<Component*>::iterator c = node->children.begin();
    				c != node->children.end();
    					c++) {
    			v->displayInfo("From composite -> renderNode");
    
    			volatile int dummy = 1;
    			std::ostringstream oss;
    			oss << (void*)&dummy;
    			std::string result = oss.str();
    			v->displayInfo(oss);
    
    			renderNode((*c), Fdot, depth+1, v);
    		}
    The displayInfo method opens a dialog with the text inside.

    It outputs this:
    @σίG
    Then this:
    @σίG


    Quote Originally Posted by Salem View Post
    Which OS/Compiler are you using?
    There is usually an option to increase the default stack size of a process.
    I'm using gcc, running on Debian 64 bits.
    Increasing the default stack size could certainly help
    Have to look into it aswell.

    Thank you for your help, Salem. ^^
    Xavier

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,540
    > *** glibc detected *** ./bin/flowvr-glgraph: free(): invalid pointer: 0x00007fffb74bfd18 ***
    This is NOT stack overflow, this is either freeing a garbage pointer, or the memory pool has been trashed by a buffer overrun.

    Definitely start to look at anything which calls 'new' or 'malloc' directly.

    Code:
    ======= Backtrace: =========
    /lib/libc.so.6(+0x71ad6)[0x7fe2f8b1fad6]
    /lib/libc.so.6(cfree+0x6c)[0x7fe2f8b2484c]
    /usr/lib/libstdc++.so.6(_ZNSsD1Ev+0x39)[0x7fe2f934fee9]
    ./bin/flowvr-glgraph(_Z10renderNodeP9ComponentRSt14basic_ofstreamIcSt11char_traitsIcEEiP6Viewer+0x15d)[0x476d95]
    ./bin/flowvr-glgraph(_ZN6Viewer7adl2dotEPKcS1_+0xaf)[0x45e2ef]
    ./bin/flowvr-glgraph(_ZN6Viewer11load_file_2E7QString+0xdc3)[0x45f337]
    ./bin/flowvr-glgraph(main+0x2a9e)[0x46c38a]
    /lib/libc.so.6(__libc_start_main+0xfd)[0x7fe2f8accc4d]
    ./bin/flowvr-glgraph[0x450889]
    This is the stack trace back to main, indicating which calls are involved. The red line is your RenderNode function.

    If you compile the code with the -g flag, the debugger will be able to point you to the actual line of code.


    > ./build-glgraph.sh: line 6: 20024 Erreur de segmentation ./bin/flowvr-glgraph /home/martinx/flowvr/flowvr-suite-hierarchy/primes.adl.out.xml
    This line comes from the outer level shell script (.sh) file, which is running this program with the specified XML file as a command line parameter (to flowvr-glgraph).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Apr 2011
    Posts
    5
    With your insight on the meaning of the error message, the logical explanation would be that the tree structure I'm accessing is corrupt / has pointers to de-allocated data.

    Well, I had experienced the same "problem" with the recursive function that built the tree itself; it would crash after a few cycles with what seemed to be a stack overflow.
    I circumvented that by hammering together an iterative version off the recursive one.

    I thought the issue was related to the recursive nature of the function, since it ran just fine on smaller, simple graphs; but thanks to you, I am now pretty sure that it is where the problem originates from. There's probably a special case I overlooked, in more complex graphs, where a pointer references a local variable that no longer exists, somewhere.

    Ahh, having a lead to work on is so much better. Thanks

  6. #6
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,540
    Valgrind Home
    With this, you stand a much better chance of spotting where the memory is corrupted for the first time, rather than waiting for some unrelated code to blow up mysteriously later on.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  7. #7
    Registered User
    Join Date
    Apr 2011
    Posts
    5
    Quote Originally Posted by Salem View Post
    Valgrind Home
    With this, you stand a much better chance of spotting where the memory is corrupted for the first time, rather than waiting for some unrelated code to blow up mysteriously later on.
    I have fixed a problem in the tree building, however it seems it wasn't the cause of the problem.

    I have installed Valgrind, and I've been toying with it for about an hour.

    Everytime my application crash, I look up where the problem originated from and comment the whole line.
    Everytime, I can go further into the tree.
    And everytime, the culprit line is an output stream to a file, such as:
    Code:
    Fdot << genIndent(depth) << " " << sanitize(node->id) << " [ shape=" << shapeToUse(node->type) << ", style=" << selectStyle(node) << ", fillcolor=" << selectFillColor(node) << ", label=\"" << generateLabel(node, v) << "\" ];\n";
    Some output lines do work and produce readable output.
    Some work fine 4 times, then make the program crash.

    It seems like any such output stream has a probability of making my program crash, but could as well run fine.

    Any idea?

    edit: lines that make the program crash also render the file un-readable when they run fine

    EDIT2: You are welcome to gently slap me.
    Those lines all had in common one thing: they called a function that didn't have a return statement.
    And the compiler didn't even tell me. How sweet!

    Well, at least I have discovered a cool trick and a great tool.
    You've helped me taking some distance to discover what was right beneath my nose, and for that I am grateful.

    Have a nice day, and good luck in your projects.
    Xavier
    Last edited by Babouche; 04-29-2011 at 09:23 AM.

  8. #8
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,604
    Might I suggest you look into smart pointers? No manual new/delete.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. "Apply", "OK" and "CANCEL" strings
    By Joelito in forum Windows Programming
    Replies: 2
    Last Post: 05-12-2006, 04:07 AM
  2. Replies: 9
    Last Post: 12-02-2003, 01:24 PM
  3. "itoa"-"_itoa" , "inp"-"_inp", Why some functions have "
    By L.O.K. in forum Windows Programming
    Replies: 5
    Last Post: 12-08-2002, 07:25 AM
  4. "CWnd"-"HWnd","CBitmap"-"HBitmap"...., What is mean by "
    By L.O.K. in forum Windows Programming
    Replies: 2
    Last Post: 12-04-2002, 06:59 AM
  5. More on C...(the speed of light "c", that is...)
    By Sebastiani in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 08-20-2001, 12:34 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21