LinuxQuestions.org
Download your favorite Linux distribution at LQ ISO.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 04-11-2011, 04:37 PM   #16
johnsfine
LQ Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,286

Rep: Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190

Quote:
Originally Posted by MTK358 View Post
What's Rb_tree?
Red Black tree is a data structure used in the internal implementation of map and set.
 
Old 04-11-2011, 04:54 PM   #17
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721
Quote:
Originally Posted by johnsfine View Post
Red Black tree is a data structure used in the internal implementation of map and set.
OK.

Quote:
Originally Posted by johnsfine View Post
In your backtrace I see

I don't have the internals of GNU Rb_tree either memorized or handy. If I debug one of these myself, I just look as disassembly and register values to be sure of what I can guess at from just the above.

I assume all three of the above items are pointers. this, __y and __k are valid pointers. __x is very much not a valid pointer.

I expect __x and __y are nodes withing the existing map. this is the map itself and __k is the new name.

So __x being bad implies the map was corrupt before you got into the code with the actual crash.

It's always harder to debug something where the crash occurs as an after effect of a previous silent bug.

If it is a memory clobber bug (rather than something that specifically hits the map) that is harder still.

Assuming a map clobber bug (rather than a memory clobber bug), I would suggest writing or finding some map testing function and insert it in a bunch of asserts scattered through the code to help find the point at which the map is corrupted.
What does the "_M_lower_bound" function do?
 
Old 04-11-2011, 05:29 PM   #18
johnsfine
LQ Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,286

Rep: Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190
Quote:
Originally Posted by MTK358 View Post
What does the "_M_lower_bound" function do?
Look it up yourself, or notice the approximate purpose of the function is obvious from the name (assuming you know how to use maps and sets) or realize it doesn't matter to your problem.

I'm pretty sure the map was corrupt before the call to find() was made.

It doesn't matter what is executing when the seg fault due to previous corruption occurs.

What matters is what was executing when the map got corrupted.
 
Old 04-11-2011, 05:32 PM   #19
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721
About your "assert" idea: how would I check if the map is corrupt?
 
Old 04-11-2011, 05:42 PM   #20
johnsfine
LQ Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,286

Rep: Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190
Quote:
Originally Posted by MTK358 View Post
About your "assert" idea: how would I check if the map is corrupt?
First idea that comes to mind:

Iterate over the items in the map and compute the sum of the first byte of the key of each item. Then just return true.

It's hard and probably not worth it to make a function that returns false if the map is corrupt. It is much simpler to use something like the above that seg faults if the map is corrupt.

I hope you know how to iterate over a map (like iterating over a std::set of std::pair). That syntax is a bit ugly and one of the things I hate about std::map.

Last edited by johnsfine; 04-11-2011 at 05:43 PM.
 
1 members found this post helpful.
Old 04-11-2011, 06:32 PM   #21
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721
Quote:
Originally Posted by johnsfine View Post
First idea that comes to mind:

Iterate over the items in the map and compute the sum of the first byte of the key of each item. Then just return true.
I'll try that later and report back.

Quote:
Originally Posted by johnsfine View Post
I hope you know how to iterate over a map (like iterating over a std::set of std:air). That syntax is a bit ugly and one of the things I hate about std::map.
Yes, I know how. In fact, there are a few places in my code already that iterate over a map.
 
Old 04-11-2011, 08:31 PM   #22
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721
I added a validate() method to Table that ran map.find() with a rendom string.

I found the error, it's in MemberNode. Turns out to be an ininitialized pointer:

Code:
LangObject* MemberNode::eval(Table *scope) {
	Table *t;
	if (objNode)
		/* I forgot the "t = " part */t = (Table*) LangObject::discardIfWrongType(objNode->eval(scope), LangObject::TableType);
	else
		t = scope;
	if (t) {
		LangObject *temp = t->get(name);
		if (temp) temp->getref();
		return temp;
	} else {
		//TODO throw error
	}
	return NULL;
}
Why does it always have to be these stupid, seemingly obvious errors?

Last edited by MTK358; 04-11-2011 at 08:32 PM.
 
Old 04-11-2011, 09:14 PM   #23
johnsfine
LQ Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,286

Rep: Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190
Quote:
Originally Posted by MTK358 View Post
I found the error, it's in MemberNode. Turns out to be an ininitialized pointer:
Maybe you're right. But I can't see any way that bug could explain the symptom. So I think you found an error, not the error.

The error you found might easily switch between symptom free and faulting as a result of unrelated changes elsewhere in your code (such as adding a validate method for the map). So that could create the appearance of a connection between the search for the other bug and the discovery of this one.

So the bug you set out to find might not be in temporary hiding rather than fixed.

Maybe there are some other factors in your code that I'm not aware of, that make it all fit together. But I doubt it. I don't think the bug you just described fits the symptoms you described earlier.

Quote:
Why does it always have to be these stupid, seemingly obvious errors?
The bug you found looks like one the compiler has an optional warning for. You should turn on warnings so more of the obvious errors can be reported by the compiler.
 
Old 04-11-2011, 09:31 PM   #24
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721
Quote:
Originally Posted by johnsfine View Post
Maybe you're right. But I can't see any way that bug could explain the symptom. So I think you found an error, not the error.
It perfectly explains the symptom. It's calling Table::get with the this parameter set to in uninitialized pointer. And it's pretty clear that the "map" member will contain random data rather than an actual map.
 
Old 04-11-2011, 09:32 PM   #25
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721Reputation: 721
Quote:
Originally Posted by johnsfine View Post
The bug you found looks like one the compiler has an optional warning for. You should turn on warnings so more of the obvious errors can be reported by the compiler.
I'm using the -Wall option, I thought that includes all warnings?
 
Old 04-12-2011, 01:09 AM   #26
Sergei Steshenko
Senior Member
 
Registered: May 2005
Posts: 4,481

Rep: Reputation: 454Reputation: 454Reputation: 454Reputation: 454Reputation: 454
Quote:
Originally Posted by MTK358 View Post
I'm using the -Wall option, I thought that includes all warnings?
-Wall -Wextra

is my default.
 
Old 04-12-2011, 04:36 AM   #27
dwhitney67
Senior Member
 
Registered: Jun 2006
Location: Maryland
Distribution: Kubuntu, Fedora, RHEL
Posts: 1,533

Rep: Reputation: 335Reputation: 335Reputation: 335Reputation: 335
The main issue was the the OP was dealing with an uninitialized pointer. I'm not sure if it is always possible to get the compiler to generate a warning for such. In certain cases, when optimization is enabled, the compiler will generate a warning, but in other cases (such as what the OP has), I don't believe a warning would be generated.

To mitigate the problem from occurring again, I would suggest that the OP get into the habit of initializing his variables; perhaps something like the following (and it ain't pretty):
Code:
LangObject* MemberNode::eval(Table* scope)
{
   Table* t = (objNode ? (Table*) LangObject::discardIfWrongType(objNode->eval(scope), LangObject::TableType) : scope);

   if (t)
   {
      LangObject* temp = t->get(name);

      if (temp) temp->getref();

      return temp;
   }
   else
   {
      //TODO throw error
   }

   return NULL;
}
 
Old 04-12-2011, 05:27 AM   #28
Sergei Steshenko
Senior Member
 
Registered: May 2005
Posts: 4,481

Rep: Reputation: 454Reputation: 454Reputation: 454Reputation: 454Reputation: 454
Quote:
Originally Posted by dwhitney67 View Post
...
To mitigate the problem from occurring again, I would suggest that the OP get into the habit of initializing his variables ...
Oh, it really depends, and, say, in Perl it's a disaster. It's a disaster because no warnings are generated (I'm still talking about Perl), and the program appears to work. Only some data produced by it looks strange under some circumstances. Debugging is long and painful, and in the end it shows that the initialized variables have never gotten true values.

In C/C++ one can probably have a habit of writing

Code:
Foo *ptr = NULL;
// give a true value to 'ptr' later
- null pointers are easily seen as wrong during debugging.

And, further along those lines:

Code:
#define INTRODUCE_POINTER(type, var) type *var = Null
...
INTRODUCE_POINTER(Foo, ptr);
...
// give a true value to 'ptr'
...
No, I do not want to hear anything about templates here.
 
Old 04-12-2011, 07:04 AM   #29
johnsfine
LQ Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,286

Rep: Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190
Quote:
Originally Posted by MTK358 View Post
It perfectly explains the symptom. It's calling Table::get with the this parameter set to in uninitialized pointer. And it's pretty clear that the "map" member will contain random data rather than an actual map.
You're right. I should have looked more carefully.

The fact that only __x looked like a bad pointer made me assume the map was really a map (externally corrupted as opposed to never having been a map at all).

Quote:
Originally Posted by dwhitney67 View Post
I'm not sure if it is always possible to get the compiler to generate a warning for such. In certain cases, when optimization is enabled, the compiler will generate a warning, but in other cases (such as what the OP has), I don't believe a warning would be generated.
I forgot MTK358 might be doing only debug builds, plus I'm used to using ICC, not GCC.

I assumed an optimized build, which in ICC would report that uninitialized pointer. Then only after a run time failure of the optimized build, use an unoptimized build to debug.

The optimizer is often quite confused about whether a variable is initialized. For class/struct members it generally doesn't warn about uninitialized, so there are a lot of such bugs not caught by warnings. For function local variables, I don't know of any case where ICC is confused enough to fail to warn about uninitialized. There are plenty of cases where it is confused enough to warn uninitialized when that is not correct.

Quote:
Originally Posted by Sergei Steshenko View Post
In C/C++ one can probably have a habit of writing

Code:
Foo *ptr = NULL;
// give a true value to 'ptr' later
You're probably right. I would never code that way myself, because I almost always code as if size and speed of the code matters and I can't remember ever coding an uninitialized pointer bug myself (fixed plenty in other people's code). But for advising less extreme programmers, initializing pointers to 0 is probably wise.

In C++, I hate use of "NULL". Simply using 0 is clearer.

In my own code and in advising others, I usually avoid uninitialized local variables by not even declaring the variable until the first time it is assigned. In most cases that makes the code safer, more readable, and easier for the compiler to optimize. But in this specific case, most programmers would consider it less readable to use dwhitney67's suggesting and change:
Code:
X* p;
if (condition)
   p = something;
else
   p = something_else;
into
Code:
X* p = (condition) ? something : something_else;
That is semantically clearer and certainly easier to optimize, but still is harder to read.

If you did that a lot and inserted consistent line breaks, it might become readable one you're used to it:
Code:
X* p = (condition) ?
       something
     : something_else;

Last edited by johnsfine; 04-12-2011 at 07:27 AM.
 
Old 04-12-2011, 07:57 AM   #30
Sergei Steshenko
Senior Member
 
Registered: May 2005
Posts: 4,481

Rep: Reputation: 454Reputation: 454Reputation: 454Reputation: 454Reputation: 454
Quote:
Originally Posted by johnsfine View Post
...
You're probably right. I would never code that way myself, because I almost always code as if size and speed of the code matters...
Modern compilers are pretty smart regarding optimization. For example, I once played with my own FFT implementation, and I've noticed that compiler eliminates about 1/3 (!) of unneeded assignments. I.e. assignments whose result is either never used or overwritten - I don't remember exactly. The code was autogenerated, so I eliminated the unneeded assignments myself later. And overall number of assignments was hundreds (all loops unrolled).

My point is that most likely if one has

Code:
Foo *ptr = NULL; // ptr is of class 'auto'
// ptr is not actually used until next line:
ptr = true_value;
, the compiler will most likely eliminate the

Code:
Foo *ptr = NULL;
assignment.

Also, the proposed 'INTRODUCE_POINTER' macro can have two incarnations - the debug one (with assignment of NULL) and the "release" one - without the assignment.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Apache2 segfaulting Cheater512 Linux - Networking 1 07-12-2006 11:05 AM
slackware 9.0 everything segfaulting ranger12002 Slackware 6 10-31-2003 06:47 PM
RPM segfaulting wapcaplet Linux - Software 10 10-22-2003 04:45 PM
segfaulting on end acid_kewpie Programming 11 10-11-2002 04:53 PM
Gcc segfaulting salman Linux - General 1 07-14-2002 07:15 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 07:23 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration