Segmentation fault

bennyandthejets · 09-07-2005, 05:18 AM

I'm making a program to work with very large integers. The numbers are stored as a dynamic array of bytes. The arithmetic operations I've implemented involve a lot of brute force, and a lot of temporary arrays which are soon deleted.

Everything works fine for low numbers, but for larger numbers like 25^400, I start getting segmentation faults at strange places. After many repetitions of the same code, a segmentation fault suddenly occurs when I delete a temporary array. The fault doesn't occur for smaller numbers, and it doesn't occur every time that particular array is deleted. If I comment out that delete line, a segmentation fault now occurs at another line, now on a 'new' allocation.

The code is long and boring, but I could post some if anyone really wants. Does anyone have any general advice about segmentation faults and how to find their cause?

ZuK · 09-07-2005, 05:23 AM

Quote:

but for larger numbers like 25^400, I start getting segmentation faults at strange places.

I would check for array bounds errors.
Kurt

bennyandthejets · 09-07-2005, 05:34 AM

I've done that pretty thoroughly. I'll recheck again though. I'm also going to try compress the code down as much as I can, but so much code is interrelated, so it might be difficult.

**Salem** · 09-07-2005, 06:10 AM

Maybe this ?
http://www.softwareverify.com/faq.html
Your wizzy compiler should have some tools to help you track down such problems.

bennyandthejets · 09-07-2005, 06:45 AM

I'll have a look at that, thanks. In the meantime, here's some code which I have shrunk as much as possible. The error is still occuring.

bennyandthejets · 09-07-2005, 04:34 PM

I increased how high the code above can calculate by truncating the numbers when they have too many leading zeros. However, I still get segmentation faults at around 3^92, and I need to go far higher than that.

Does that code work for anyone? If it does, increase the exponent until it faults and then let me know how large you got it.

bennyandthejets · 09-07-2005, 04:48 PM

I added some counters to check if I'm destructing all instances and deleting all memory. I lowered the exponent just enough so that I wouldn't get a seg fault, and both counters were at zero, indicating that everything is being disposed of properly. Then from whence cometh this seg fault?

bennyandthejets · 09-07-2005, 05:04 PM

I found the problem. It was a sly, sneaky out of bounds error. All it did was corrupt the heap behind the scenes, while still allowing the correct answer to be output if the numbers were small enough. Here is where it was:

Code:

                int iSrc=(a.nSize*8)-1;
                int iDest=(Terms[c]->nSize*8); //<!!!!!!!!!!! Should subtract there

                while (iDest>(8*i)+j+(a.nSize*8)-1) {
                    if (static_cast<int>(iDest/8)>=ubound) std::cout << "<oob> " << std::flush;
                    SETBIT(Terms[c]->pNum[static_cast<int>(iDest/8)],iDest%8,0);
                    iDest--;
                }
                while (iSrc>=0) {
                    int BitSet=GETBIT(a.pNum[static_cast<int>(iSrc/8)],iSrc%8);
                    if (static_cast<int>(iDest/8)>=ubound) std::cout << "<oob> " << std::flush;
                    SETBIT(Terms[c]->pNum[static_cast<int>(iDest/8)],iDest%8,BitSet);
                    iSrc--;
                    iDest--;
                }
                while (iDest>=0) {
                    if (static_cast<int>(iDest/8)>=ubound) std::cout << "<oob> " << std::flush;
                    SETBIT(Terms[c]->pNum[static_cast<int>(iDest/8)],iDest%8,0);
                    iDest--;
                }

The effect of that tiny error was that a single byte beyond the allocated memory was being zeroed hundreds of times. I guess that caused some heap damage or hurt its feelings or something.

I can now push it pretty high. I tried 3^5000, it took 5 seconds but it worked.

Any tips on how to speed it up?

09-07-2005, 05:18 AM	#1
bennyandthejets mustang benny Join Date: Jul 2002 Posts: 1,401	Segmentation fault I'm making a program to work with very large integers. The numbers are stored as a dynamic array of bytes. The arithmetic operations I've implemented involve a lot of brute force, and a lot of temporary arrays which are soon deleted. Everything works fine for low numbers, but for larger numbers like 25^400, I start getting segmentation faults at strange places. After many repetitions of the same code, a segmentation fault suddenly occurs when I delete a temporary array. The fault doesn't occur for smaller numbers, and it doesn't occur every time that particular array is deleted. If I comment out that delete line, a segmentation fault now occurs at another line, now on a 'new' allocation. The code is long and boring, but I could post some if anyone really wants. Does anyone have any general advice about segmentation faults and how to find their cause? __________________ benforbes@optusnet.com.au Microsoft Visual Studio .NET 2003 Enterprise Architect Windows XP Pro Code Tags Programming FAQ Tutorials
bennyandthejets is offline

09-07-2005, 05:34 AM	#3
bennyandthejets mustang benny Join Date: Jul 2002 Posts: 1,401	I've done that pretty thoroughly. I'll recheck again though. I'm also going to try compress the code down as much as I can, but so much code is interrelated, so it might be difficult. __________________ benforbes@optusnet.com.au Microsoft Visual Studio .NET 2003 Enterprise Architect Windows XP Pro Code Tags Programming FAQ Tutorials
bennyandthejets is offline

09-07-2005, 06:10 AM	#4
Salem and the hat of vanishing Join Date: Aug 2001 Location: The edge of the known universe Posts: 21,214	Maybe this ? http://www.softwareverify.com/faq.html Your wizzy compiler should have some tools to help you track down such problems. __________________ If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut. Up to 8Mb PlusNet broadband from only £5.99 a month!
Salem is offline

09-07-2005, 04:34 PM	#6
bennyandthejets mustang benny Join Date: Jul 2002 Posts: 1,401	I increased how high the code above can calculate by truncating the numbers when they have too many leading zeros. However, I still get segmentation faults at around 3^92, and I need to go far higher than that. Does that code work for anyone? If it does, increase the exponent until it faults and then let me know how large you got it. __________________ benforbes@optusnet.com.au Microsoft Visual Studio .NET 2003 Enterprise Architect Windows XP Pro Code Tags Programming FAQ Tutorials
bennyandthejets is offline

09-07-2005, 04:48 PM	#7
bennyandthejets mustang benny Join Date: Jul 2002 Posts: 1,401	I added some counters to check if I'm destructing all instances and deleting all memory. I lowered the exponent just enough so that I wouldn't get a seg fault, and both counters were at zero, indicating that everything is being disposed of properly. Then from whence cometh this seg fault? __________________ benforbes@optusnet.com.au Microsoft Visual Studio .NET 2003 Enterprise Architect Windows XP Pro Code Tags Programming FAQ Tutorials
bennyandthejets is offline

09-07-2005, 05:04 PM	#8
bennyandthejets mustang benny Join Date: Jul 2002 Posts: 1,401	I found the problem. It was a sly, sneaky out of bounds error. All it did was corrupt the heap behind the scenes, while still allowing the correct answer to be output if the numbers were small enough. Here is where it was: Code: int iSrc=(a.nSize8)-1; int iDest=(Terms[c]->nSize8); //<!!!!!!!!!!! Should subtract there while (iDest>(8i)+j+(a.nSize8)-1) { if (static_cast<int>(iDest/8)>=ubound) std::cout << "<oob> " << std::flush; SETBIT(Terms[c]->pNum[static_cast<int>(iDest/8)],iDest%8,0); iDest--; } while (iSrc>=0) { int BitSet=GETBIT(a.pNum[static_cast<int>(iSrc/8)],iSrc%8); if (static_cast<int>(iDest/8)>=ubound) std::cout << "<oob> " << std::flush; SETBIT(Terms[c]->pNum[static_cast<int>(iDest/8)],iDest%8,BitSet); iSrc--; iDest--; } while (iDest>=0) { if (static_cast<int>(iDest/8)>=ubound) std::cout << "<oob> " << std::flush; SETBIT(Terms[c]->pNum[static_cast<int>(iDest/8)],iDest%8,0); iDest--; } The effect of that tiny error was that a single byte beyond the allocated memory was being zeroed hundreds of times. I guess that caused some heap damage or hurt its feelings or something. I can now push it pretty high. I tried 3^5000, it took 5 seconds but it worked. Any tips on how to speed it up? __________________ benforbes@optusnet.com.au Microsoft Visual Studio .NET 2003 Enterprise Architect Windows XP Pro Code Tags Programming FAQ Tutorials
bennyandthejets is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Segmentation fault problem	odedbobi	Linux Programming	1	11-19-2008 03:36 AM
Why am I getting segmentation fault on this?	arya6000	C++ Programming	6	10-12-2008 06:32 AM
Segmentation fault	NoUse	C Programming	4	03-26-2005 03:29 PM
Locating A Segmentation Fault	Stack Overflow	C Programming	12	12-14-2004 01:33 PM
Segmentation fault...	alvifarooq	C++ Programming	14	09-26-2004 12:53 PM