Thread: RE: [Dev-C++] STL Map question
Open Source C & C++ IDE for Windows
Brought to you by:
claplace
Menu
▾
▴
dev-cpp-users
|
From: Ioannis V. <iv...@em...> - 2003-07-10 00:14:17
|
-----Original Message----- From: Ioannis Vranos [mailto:iv...@em...]=20 Sent: Thursday, July 10, 2003 3:11 AM To: Dev-C++ Mailing List (dev...@li...) Subject: RE: [Dev-C++] STL Map question =20 -----Original Message----- From: dev...@li... [mailto:dev...@li...] On Behalf Of Shane = Bryldt Sent: Thursday, July 10, 2003 2:00 AM To: Ioannis Vranos Cc: C++ Subject: Re: [Dev-C++] STL Map question Yes, I appologize for not including the header definition. Here it is. =20 #ifndef USERLIST_H #define USERLIST_H =20 #include <map.h>=20 =20 #include <cmap>=20 =20 My mistake. The correct: #include <map>=20 =20 =20 =20 =20 =20 =20 Ioannis Vranos * Programming pages: http://www.noicys.freeurl.com <http://www.noicys.freeurl.com/>=20 * Alternative URL 1: http://run.to/noicys * Alternative URL 2: http://www.noicys.cjb.net = <http://www.noicys.cjb.net/> =20 |
|
From: Hossein H. <ult...@em...> - 2003-07-11 11:21:15
|
I'm not sure if it helps, but just try (!map<>::empty()) instead of (map<>::size() > 0) to see what happens! Sorry if it seems a little off-topic. But that's because I still couldn't realise what had caused the bug. I'm trying to check if there is any bug in your C++ implementation's std::map<>. Maybe, map<>::size() does something causing pointer invalidation! Let me know the result! Regards, --Hossein -- __________________________________________________________ Sign-up for your own FREE Personalized E-mail at Mail.com http://www.mail.com/?sr=signup CareerBuilder.com has over 400,000 jobs. Be smarter about your job search http://corp.mail.com/careers |
|
From: Shane B. <ast...@te...> - 2003-07-11 20:55:05
|
Actually, since I had about 20 responses on this topic, none of which
actually got close to the effect, nevermind the cause of the problem, I will
try and explain the situation in more detail. However, to make the records
clear, I don't expect to find an answer now. I have looked the code over a
number of times, and had another expert which is admittedly significantly
better with C++ and STL than myself, and even he cannot seem to find any
problems which relate. Given old working code, and my new adjusted code,
many changes were made but I cannot determine what is causing the problem.
Now, the effect of the issue, is as follows. A network of 6,000-10,000
active users at any given time is regulated by a security service. This
service runs and connects like a user, with special priviledges. Anytime a
user connects to the network, the services is informed, and the User is
added to a global UserList. The network also has smaller units, known as
Channels. Each Channel contains 3 UserList's as well. First, depicts all
users in the Channel, the second depicts all the operators of the channel,
and the third depicts the priviledged users who are not operators. 99% of
the time, the code work fine. Users constantly added and removed from the
list. Periodically, what seems like an issue without a pattern, the code
will crash with a segmentation fault while trying to call
"std::map<>::find()", with a valid key. Whether the key is in the map, is
not definate, but the key passed in valid and should not have a problem
being searched.
This said, I have narrowed the issue down to one of 2 causes. 1) Either
User's are being added to lists, and not being removed, and the UserLists
are eventually gathering enough garbage that out of memory is being
encountered. The application has a signal hook for out of memory, and it is
not being raised. So I am leaning more towards option 2) The User class is
being deleted, without being removed from the UserList. However, I can find
no indication of this in the code. The code is many thousands of lines, it
is not a small project by any means. Providing the source for the issue,
would require the entire project as the issue is not specifically a syntax
issue, but rather a situational issue. I do believe something has
invalidated a User class, which a UserList has a pointer to, and when trying
to use it, is causing a segmentation fault. I'm sure most of the experts
here will agree with my conclusion and realize tracing this problem is no
easy task.
I've considered some commercial products like Purify, or some other memory
tracking products, but I have no experience with any, since I've never had
an issue I couldn't resolve purely with GDB. Since the problem traces back
most likely to an invalid pointer reference, does anyone have suggestions on
how I could possibly detect where the pointer is being deleted? I've
considered the idea of using smart pointers to track the issue down, but
again I'm not entirely certain of how to implement some code to track where
the User is being deleted without being removed from the channels they are
in... It could also potentially be an issue with overwritting memory, but
with how often it is caused in exactly the same way, it's unlikely to be
memory overbounding.
I noticed a location where the key being used was being changed (a
nickname), and in those cases, where the old code would just rename the
nickname, I have now remove from the map and then readd to the map. When it
tries to remove from the map is when it crashes. I can only assume that the
problem is an invalid pointer, thus the map::find function is crashing
because of invalid memory. The key was based on a const char *, but the
other expert I consulted suggested using std::string to help track the
problem until it is found... Changing to use std::string is how I determined
that the key was still valid (because it had a copy of the nick instead of a
pointer to the nick which may be invalidated at some point), and the key was
still intact as far as I can remember, the pointer however caused GDB itself
to indicate that the program crashed again from a call by GDB, when trying
to access a member of the pointer.
Okay, hopefully these details will clarify for all the people who tried to
help... The problem itself is not something so simple as was suggested so
far. However, Hossein did make one point that I should have realized
myself. Not that it matters, but I should use empty() instead of size() ==
0, since it's possible empty() can execute faster than size(). But speaking
from the ANSI compliance, size() == 0 is identical to empty() == true in
result, just not exection. That said, it will not affect the problem.
-Shane
----- Original Message -----
From: "Hossein Haeri" <ult...@em...>
To: <dev...@li...>
Sent: Friday, July 11, 2003 5:19 AM
Subject: RE: [Dev-C++] STL Map question
> I'm not sure if it helps, but just try (!map<>::empty()) instead of
> (map<>::size() > 0) to see what happens!
>
> Sorry if it seems a little off-topic. But that's because I still
> couldn't realise what had caused the bug. I'm trying to check if there
> is any bug in your C++ implementation's std::map<>. Maybe,
> map<>::size() does something causing pointer invalidation!
>
> Let me know the result!
>
> Regards,
> --Hossein
> --
> __________________________________________________________
> Sign-up for your own FREE Personalized E-mail at Mail.com
> http://www.mail.com/?sr=signup
>
> CareerBuilder.com has over 400,000 jobs. Be smarter about your job search
> http://corp.mail.com/careers
>
>
>
> -------------------------------------------------------
> This SF.Net email sponsored by: Parasoft
> Error proof Web apps, automate testing & more.
> Download & eval WebKing and get a free book.
> www.parasoft.com/bulletproofapps1
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www23.brinkster.com/noicys/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>
|
|
From: Ioannis V. <iv...@em...> - 2003-07-11 22:07:34
|
> -----Original Message-----
> From: dev...@li...=20
> [mailto:dev...@li...] On Behalf=20
> Of Shane Bryldt
> Sent: Friday, July 11, 2003 11:53 PM
> To: Hossein Haeri
> Cc: C++
> Subject: Re: [Dev-C++] STL Map question
>=20
>=20
> Actually, since I had about 20 responses on this topic, none of which
> actually got close to the effect, nevermind the cause of the=20
> problem, I will
> try and explain the situation in more detail. However, to=20
> make the records
> clear, I don't expect to find an answer now. I have looked=20
> the code over a
> number of times, and had another expert which is admittedly=20
> significantly
> better with C++ and STL than myself, and even he cannot seem=20
> to find any
> problems which relate. Given old working code, and my new=20
> adjusted code,
> many changes were made but I cannot determine what is causing=20
> the problem.
>=20
> Now, the effect of the issue, is as follows. A network of 6,000-10,000
> active users at any given time is regulated by a security=20
> service. This
> service runs and connects like a user, with special=20
> priviledges. Anytime a
> user connects to the network, the services is informed, and=20
> the User is
> added to a global UserList. The network also has smaller=20
> units, known as
> Channels. Each Channel contains 3 UserList's as well. =20
> First, depicts all
> users in the Channel, the second depicts all the operators of=20
> the channel,
> and the third depicts the priviledged users who are not=20
> operators. 99% of
> the time, the code work fine. Users constantly added and=20
> removed from the
> list. Periodically, what seems like an issue without a=20
> pattern, the code
> will crash with a segmentation fault while trying to call
> "std::map<>::find()", with a valid key. Whether the key is=20
> in the map, is
> not definate, but the key passed in valid and should not have=20
> a problem
> being searched.
>=20
> This said, I have narrowed the issue down to one of 2 causes.=20
> 1) Either
> User's are being added to lists, and not being removed, and=20
> the UserLists
> are eventually gathering enough garbage that out of memory is being
> encountered.
In this case if you use the operator new as you should, an =
std::bad_alloc()
exception would be thrown (defined in <new>) and as you should you must =
have
at least a catch(std::bad_allloc) in main() to catch such exceptions and =
at
least make the problem known by displaying an error message and shutting
down the program properly).
> The application has a signal hook for out of=20
> memory, and it is
> not being raised.=20
Let's hope you mean a catch clause.
> So I am leaning more towards option 2) The=20
> User class is
> being deleted, without being removed from the UserList. =20
> However, I can find
> no indication of this in the code. The code is many=20
> thousands of lines, it
> is not a small project by any means. Providing the source=20
> for the issue,
> would require the entire project as the issue is not=20
> specifically a syntax
> issue, but rather a situational issue. I do believe something has
> invalidated a User class, which a UserList has a pointer to,=20
> and when trying
> to use it, is causing a segmentation fault. I'm sure most of=20
> the experts
> here will agree with my conclusion and realize tracing this=20
> problem is no
> easy task.
We must see at least the entire definitions of UserList and User. Can =
you
provide them?
=20
> I've considered some commercial products like Purify, or some=20
> other memory
> tracking products, but I have no experience with any, since=20
> I've never had
> an issue I couldn't resolve purely with GDB. Since the=20
> problem traces back
> most likely to an invalid pointer reference, does anyone have=20
> suggestions on
> how I could possibly detect where the pointer is being deleted?
I am not an expert, I am still learning (and unfortunately there is an
infinite number of things that I want to learn) but I think that if =
there
has been a more proper use of C++, the code would have been more bullet
proof. That is using the superior alternatives that C++ provides instead =
of
the old stuff that they exist to replace.
> I've
> considered the idea of using smart pointers to track the=20
> issue down, but
> again I'm not entirely certain of how to implement some code=20
> to track where
> the User is being deleted without being removed from the=20
> channels they are
> in... It could also potentially be an issue with overwritting=20
> memory, but
> with how often it is caused in exactly the same way, it's=20
> unlikely to be
> memory overbounding.
> I noticed a location where the key being used was being changed (a
> nickname), and in those cases, where the old code would just=20
> rename the
> nickname, I have now remove from the map and then readd to=20
> the map. When it
> tries to remove from the map is when it crashes. I can only=20
> assume that the
> problem is an invalid pointer, thus the map::find function is crashing
> because of invalid memory. The key was based on a const char=20
> *, but the
> other expert I consulted suggested using std::string to help track the
> problem until it is found... Changing to use std::string is=20
> how I determined
> that the key was still valid (because it had a copy of the=20
> nick instead of a
> pointer to the nick which may be invalidated at some point),=20
> and the key was
> still intact as far as I can remember, the pointer however=20
> caused GDB itself
> to indicate that the program crashed again from a call by=20
> GDB, when trying
> to access a member of the pointer.
>=20
>=20
> Okay, hopefully these details will clarify for all the people=20
> who tried to
> help... The problem itself is not something so simple as was=20
> suggested so
> far. However, Hossein did make one point that I should have realized
> myself. Not that it matters, but I should use empty()=20
> instead of size() =3D=3D
> 0, since it's possible empty() can execute faster than=20
> size().
Eh? Why? Both have the same speed, actually empty is usually=20
// inside the class definition
bool empty() const { return size()=3D=3D0; }
since map has to keep track of its size. In any case consider them as =
equal
(an equality comparison doesn't take time!).
> But speaking
> from the ANSI compliance, size() =3D=3D 0 is identical to empty()=20
> =3D=3D true in
> result, just not exection. That said, it will not affect the problem.
Yeap. Please provide us with the complete defintions of User and =
UserList.
:-)
Ioannis Vranos
=20
* Programming pages: http://www.noicys.freeurl.com
* Alternative URL 1: http://run.to/noicys
* Alternative URL 2: http://www.noicys.cjb.net
|
|
From: Per W. <pw...@ia...> - 2003-07-11 23:01:48
|
Ioannis:
For older compilers, new doesn't throw an exception. Depending on
configuration and/or implementation, they either return NULL, call an
installable callback function or kill the program.
The implementation of user handling might be absolutely bug-free. It
doesn't help if some other part of the program somehow goofs up and
somehow overwrites memory.
A dual delete on an object somewhere in the program is a perfect example
of how a program without any strange pointer manipulation might perform
memory overwrites, by destroying the heap.
Shane: Have you tried some heap-debugging code, that checks the following
for every memory release:
- that it is a validly allocated pointer
- that the memory hasn't already been released
- that guard bytes of the block hasn't been overwritten.
/Per W
On Sat, 12 Jul 2003, Ioannis Vranos wrote:
> > -----Original Message-----
> > From: dev...@li...
> > [mailto:dev...@li...] On Behalf
> > Of Shane Bryldt
> > Sent: Friday, July 11, 2003 11:53 PM
> > To: Hossein Haeri
> > Cc: C++
> > Subject: Re: [Dev-C++] STL Map question
> >
> >
> > Actually, since I had about 20 responses on this topic, none of which
> > actually got close to the effect, nevermind the cause of the
> > problem, I will
> > try and explain the situation in more detail. However, to
> > make the records
> > clear, I don't expect to find an answer now. I have looked
> > the code over a
> > number of times, and had another expert which is admittedly
> > significantly
> > better with C++ and STL than myself, and even he cannot seem
> > to find any
> > problems which relate. Given old working code, and my new
> > adjusted code,
> > many changes were made but I cannot determine what is causing
> > the problem.
> >
> > Now, the effect of the issue, is as follows. A network of 6,000-10,000
> > active users at any given time is regulated by a security
> > service. This
> > service runs and connects like a user, with special
> > priviledges. Anytime a
> > user connects to the network, the services is informed, and
> > the User is
> > added to a global UserList. The network also has smaller
> > units, known as
> > Channels. Each Channel contains 3 UserList's as well.
> > First, depicts all
> > users in the Channel, the second depicts all the operators of
> > the channel,
> > and the third depicts the priviledged users who are not
> > operators. 99% of
> > the time, the code work fine. Users constantly added and
> > removed from the
> > list. Periodically, what seems like an issue without a
> > pattern, the code
> > will crash with a segmentation fault while trying to call
> > "std::map<>::find()", with a valid key. Whether the key is
> > in the map, is
> > not definate, but the key passed in valid and should not have
> > a problem
> > being searched.
> >
> > This said, I have narrowed the issue down to one of 2 causes.
> > 1) Either
> > User's are being added to lists, and not being removed, and
> > the UserLists
> > are eventually gathering enough garbage that out of memory is being
> > encountered.
>
>
> In this case if you use the operator new as you should, an std::bad_alloc()
> exception would be thrown (defined in <new>) and as you should you must have
> at least a catch(std::bad_allloc) in main() to catch such exceptions and at
> least make the problem known by displaying an error message and shutting
> down the program properly).
>
>
>
>
> > The application has a signal hook for out of
> > memory, and it is
> > not being raised.
>
>
> Let's hope you mean a catch clause.
>
>
>
> > So I am leaning more towards option 2) The
> > User class is
> > being deleted, without being removed from the UserList.
> > However, I can find
> > no indication of this in the code. The code is many
> > thousands of lines, it
> > is not a small project by any means. Providing the source
> > for the issue,
> > would require the entire project as the issue is not
> > specifically a syntax
> > issue, but rather a situational issue. I do believe something has
> > invalidated a User class, which a UserList has a pointer to,
> > and when trying
> > to use it, is causing a segmentation fault. I'm sure most of
> > the experts
> > here will agree with my conclusion and realize tracing this
> > problem is no
> > easy task.
>
>
> We must see at least the entire definitions of UserList and User. Can you
> provide them?
>
>
>
> > I've considered some commercial products like Purify, or some
> > other memory
> > tracking products, but I have no experience with any, since
> > I've never had
> > an issue I couldn't resolve purely with GDB. Since the
> > problem traces back
> > most likely to an invalid pointer reference, does anyone have
> > suggestions on
> > how I could possibly detect where the pointer is being deleted?
>
>
>
> I am not an expert, I am still learning (and unfortunately there is an
> infinite number of things that I want to learn) but I think that if there
> has been a more proper use of C++, the code would have been more bullet
> proof. That is using the superior alternatives that C++ provides instead of
> the old stuff that they exist to replace.
>
>
>
>
> > I've
> > considered the idea of using smart pointers to track the
> > issue down, but
> > again I'm not entirely certain of how to implement some code
> > to track where
> > the User is being deleted without being removed from the
> > channels they are
> > in... It could also potentially be an issue with overwritting
> > memory, but
> > with how often it is caused in exactly the same way, it's
> > unlikely to be
> > memory overbounding.
> > I noticed a location where the key being used was being changed (a
> > nickname), and in those cases, where the old code would just
> > rename the
> > nickname, I have now remove from the map and then readd to
> > the map. When it
> > tries to remove from the map is when it crashes. I can only
> > assume that the
> > problem is an invalid pointer, thus the map::find function is crashing
> > because of invalid memory. The key was based on a const char
> > *, but the
> > other expert I consulted suggested using std::string to help track the
> > problem until it is found... Changing to use std::string is
> > how I determined
> > that the key was still valid (because it had a copy of the
> > nick instead of a
> > pointer to the nick which may be invalidated at some point),
> > and the key was
> > still intact as far as I can remember, the pointer however
> > caused GDB itself
> > to indicate that the program crashed again from a call by
> > GDB, when trying
> > to access a member of the pointer.
> >
> >
> > Okay, hopefully these details will clarify for all the people
> > who tried to
> > help... The problem itself is not something so simple as was
> > suggested so
> > far. However, Hossein did make one point that I should have realized
> > myself. Not that it matters, but I should use empty()
> > instead of size() ==
> > 0, since it's possible empty() can execute faster than
> > size().
>
>
> Eh? Why? Both have the same speed, actually empty is usually
>
> // inside the class definition
> bool empty() const { return size()==0; }
>
>
> since map has to keep track of its size. In any case consider them as equal
> (an equality comparison doesn't take time!).
>
>
>
> > But speaking
> > from the ANSI compliance, size() == 0 is identical to empty()
> > == true in
> > result, just not exection. That said, it will not affect the problem.
>
>
> Yeap. Please provide us with the complete defintions of User and UserList.
> :-)
>
>
>
>
>
>
> Ioannis Vranos
>
> * Programming pages: http://www.noicys.freeurl.com
> * Alternative URL 1: http://run.to/noicys
> * Alternative URL 2: http://www.noicys.cjb.net
>
>
>
>
> -------------------------------------------------------
> This SF.Net email sponsored by: Parasoft
> Error proof Web apps, automate testing & more.
> Download & eval WebKing and get a free book.
> www.parasoft.com/bulletproofapps1
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www23.brinkster.com/noicys/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>
|
|
From: Ioannis V. <iv...@em...> - 2003-07-12 00:01:39
|
> -----Original Message----- > From: Per Westermark [mailto:pw...@ia...] > Sent: Saturday, July 12, 2003 2:04 AM > To: Ioannis Vranos > Cc: Dev-C++ Mailing List > Subject: RE: [Dev-C++] STL Map question > > > Ioannis: > For older compilers, new doesn't throw an exception. Depending on > configuration and/or implementation, they either return NULL, call an > installable callback function or kill the program. I never talk about legacy stuff. :-) I assume a modern compiler and in particular I assumed Dev-C++. > The implementation of user handling might be absolutely bug-free. It > doesn't help if some other part of the program somehow goofs up and > somehow overwrites memory. Yes. > A dual delete on an object somewhere in the program is a > perfect example > of how a program without any strange pointer manipulation > might perform > memory overwrites, by destroying the heap. Yes, but without being required by the standard, most probably the program would die directly upon the second deletion. In any case we can make only assumptions without the code. And we can also make observations. And I had observed old stuff, char *s, strcmp()s. As I had pointed out in a previous email, replacing all char *s with std::string is a good starting point. Ioannis Vranos * Programming pages: http://www.noicys.freeurl.com * Alternative URL 1: http://run.to/noicys * Alternative URL 2: http://www.noicys.cjb.net |
|
From: Shane B. <ast...@te...> - 2003-07-11 20:56:20
|
Actually, since I had about 20 responses on this topic, none of which
actually got close to the effect, nevermind the cause of the problem, I will
try and explain the situation in more detail. However, to make the records
clear, I don't expect to find an answer now. I have looked the code over a
number of times, and had another expert which is admittedly significantly
better with C++ and STL than myself, and even he cannot seem to find any
problems which relate. Given old working code, and my new adjusted code,
many changes were made but I cannot determine what is causing the problem.
Now, the effect of the issue, is as follows. A network of 6,000-10,000
active users at any given time is regulated by a security service. This
service runs and connects like a user, with special priviledges. Anytime a
user connects to the network, the services is informed, and the User is
added to a global UserList. The network also has smaller units, known as
Channels. Each Channel contains 3 UserList's as well. First, depicts all
users in the Channel, the second depicts all the operators of the channel,
and the third depicts the priviledged users who are not operators. 99% of
the time, the code work fine. Users constantly added and removed from the
list. Periodically, what seems like an issue without a pattern, the code
will crash with a segmentation fault while trying to call
"std::map<>::find()", with a valid key. Whether the key is in the map, is
not definate, but the key passed in valid and should not have a problem
being searched.
This said, I have narrowed the issue down to one of 2 causes. 1) Either
User's are being added to lists, and not being removed, and the UserLists
are eventually gathering enough garbage that out of memory is being
encountered. The application has a signal hook for out of memory, and it is
not being raised. So I am leaning more towards option 2) The User class is
being deleted, without being removed from the UserList. However, I can find
no indication of this in the code. The code is many thousands of lines, it
is not a small project by any means. Providing the source for the issue,
would require the entire project as the issue is not specifically a syntax
issue, but rather a situational issue. I do believe something has
invalidated a User class, which a UserList has a pointer to, and when trying
to use it, is causing a segmentation fault. I'm sure most of the experts
here will agree with my conclusion and realize tracing this problem is no
easy task.
I've considered some commercial products like Purify, or some other memory
tracking products, but I have no experience with any, since I've never had
an issue I couldn't resolve purely with GDB. Since the problem traces back
most likely to an invalid pointer reference, does anyone have suggestions on
how I could possibly detect where the pointer is being deleted? I've
considered the idea of using smart pointers to track the issue down, but
again I'm not entirely certain of how to implement some code to track where
the User is being deleted without being removed from the channels they are
in... It could also potentially be an issue with overwritting memory, but
with how often it is caused in exactly the same way, it's unlikely to be
memory overbounding.
I noticed a location where the key being used was being changed (a
nickname), and in those cases, where the old code would just rename the
nickname, I have now remove from the map and then readd to the map. When it
tries to remove from the map is when it crashes. I can only assume that the
problem is an invalid pointer, thus the map::find function is crashing
because of invalid memory. The key was based on a const char *, but the
other expert I consulted suggested using std::string to help track the
problem until it is found... Changing to use std::string is how I determined
that the key was still valid (because it had a copy of the nick instead of a
pointer to the nick which may be invalidated at some point), and the key was
still intact as far as I can remember, the pointer however caused GDB itself
to indicate that the program crashed again from a call by GDB, when trying
to access a member of the pointer.
Okay, hopefully these details will clarify for all the people who tried to
help... The problem itself is not something so simple as was suggested so
far. However, Hossein did make one point that I should have realized
myself. Not that it matters, but I should use empty() instead of size() ==
0, since it's possible empty() can execute faster than size(). But speaking
from the ANSI compliance, size() == 0 is identical to empty() == true in
result, just not exection. That said, it will not affect the problem.
-Shane
----- Original Message -----
From: "Hossein Haeri" <ult...@em...>
To: <dev...@li...>
Sent: Friday, July 11, 2003 5:19 AM
Subject: RE: [Dev-C++] STL Map question
> I'm not sure if it helps, but just try (!map<>::empty()) instead of
> (map<>::size() > 0) to see what happens!
>
> Sorry if it seems a little off-topic. But that's because I still
> couldn't realise what had caused the bug. I'm trying to check if there
> is any bug in your C++ implementation's std::map<>. Maybe,
> map<>::size() does something causing pointer invalidation!
>
> Let me know the result!
>
> Regards,
> --Hossein
> --
> __________________________________________________________
> Sign-up for your own FREE Personalized E-mail at Mail.com
> http://www.mail.com/?sr=signup
>
> CareerBuilder.com has over 400,000 jobs. Be smarter about your job search
> http://corp.mail.com/careers
>
>
>
> -------------------------------------------------------
> This SF.Net email sponsored by: Parasoft
> Error proof Web apps, automate testing & more.
> Download & eval WebKing and get a free book.
> www.parasoft.com/bulletproofapps1
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www23.brinkster.com/noicys/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>
|
|
From: Shane B. <ast...@te...> - 2003-07-11 21:01:16
|
Actually, since I had about 20 responses on this topic, none of which
actually got close to the effect, nevermind the cause of the problem, I will
try and explain the situation in more detail. However, to make the records
clear, I don't expect to find an answer now. I have looked the code over a
number of times, and had another expert which is admittedly significantly
better with C++ and STL than myself, and even he cannot seem to find any
problems which relate. Given old working code, and my new adjusted code,
many changes were made but I cannot determine what is causing the problem.
Now, the effect of the issue, is as follows. A network of 6,000-10,000
active users at any given time is regulated by a security service. This
service runs and connects like a user, with special priviledges. Anytime a
user connects to the network, the services is informed, and the User is
added to a global UserList. The network also has smaller units, known as
Channels. Each Channel contains 3 UserList's as well. First, depicts all
users in the Channel, the second depicts all the operators of the channel,
and the third depicts the priviledged users who are not operators. 99% of
the time, the code work fine. Users constantly added and removed from the
list. Periodically, what seems like an issue without a pattern, the code
will crash with a segmentation fault while trying to call
"std::map<>::find()", with a valid key. Whether the key is in the map, is
not definate, but the key passed in valid and should not have a problem
being searched.
This said, I have narrowed the issue down to one of 2 causes. 1) Either
User's are being added to lists, and not being removed, and the UserLists
are eventually gathering enough garbage that out of memory is being
encountered. The application has a signal hook for out of memory, and it is
not being raised. So I am leaning more towards option 2) The User class is
being deleted, without being removed from the UserList. However, I can find
no indication of this in the code. The code is many thousands of lines, it
is not a small project by any means. Providing the source for the issue,
would require the entire project as the issue is not specifically a syntax
issue, but rather a situational issue. I do believe something has
invalidated a User class, which a UserList has a pointer to, and when trying
to use it, is causing a segmentation fault. I'm sure most of the experts
here will agree with my conclusion and realize tracing this problem is no
easy task.
I've considered some commercial products like Purify, or some other memory
tracking products, but I have no experience with any, since I've never had
an issue I couldn't resolve purely with GDB. Since the problem traces back
most likely to an invalid pointer reference, does anyone have suggestions on
how I could possibly detect where the pointer is being deleted? I've
considered the idea of using smart pointers to track the issue down, but
again I'm not entirely certain of how to implement some code to track where
the User is being deleted without being removed from the channels they are
in... It could also potentially be an issue with overwritting memory, but
with how often it is caused in exactly the same way, it's unlikely to be
memory overbounding.
I noticed a location where the key being used was being changed (a
nickname), and in those cases, where the old code would just rename the
nickname, I have now remove from the map and then readd to the map. When it
tries to remove from the map is when it crashes. I can only assume that the
problem is an invalid pointer, thus the map::find function is crashing
because of invalid memory. The key was based on a const char *, but the
other expert I consulted suggested using std::string to help track the
problem until it is found... Changing to use std::string is how I determined
that the key was still valid (because it had a copy of the nick instead of a
pointer to the nick which may be invalidated at some point), and the key was
still intact as far as I can remember, the pointer however caused GDB itself
to indicate that the program crashed again from a call by GDB, when trying
to access a member of the pointer.
Okay, hopefully these details will clarify for all the people who tried to
help... The problem itself is not something so simple as was suggested so
far. However, Hossein did make one point that I should have realized
myself. Not that it matters, but I should use empty() instead of size() ==
0, since it's possible empty() can execute faster than size(). But speaking
from the ANSI compliance, size() == 0 is identical to empty() == true in
result, just not exection. That said, it will not affect the problem.
-Shane
----- Original Message -----
From: "Hossein Haeri" <ult...@em...>
To: <dev...@li...>
Sent: Friday, July 11, 2003 5:19 AM
Subject: RE: [Dev-C++] STL Map question
> I'm not sure if it helps, but just try (!map<>::empty()) instead of
> (map<>::size() > 0) to see what happens!
>
> Sorry if it seems a little off-topic. But that's because I still
> couldn't realise what had caused the bug. I'm trying to check if there
> is any bug in your C++ implementation's std::map<>. Maybe,
> map<>::size() does something causing pointer invalidation!
>
> Let me know the result!
>
> Regards,
> --Hossein
> --
> __________________________________________________________
> Sign-up for your own FREE Personalized E-mail at Mail.com
> http://www.mail.com/?sr=signup
>
> CareerBuilder.com has over 400,000 jobs. Be smarter about your job search
> http://corp.mail.com/careers
>
>
>
> -------------------------------------------------------
> This SF.Net email sponsored by: Parasoft
> Error proof Web apps, automate testing & more.
> Download & eval WebKing and get a free book.
> www.parasoft.com/bulletproofapps1
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www23.brinkster.com/noicys/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>
|
|
From: Ioannis V. <iv...@em...> - 2003-07-15 18:00:26
|
> -----Original Message-----
> From: dev...@li...=20
> [mailto:dev...@li...] On Behalf=20
> Of Shane Bryldt
> Sent: Friday, July 11, 2003 11:53 PM
> To: Hossein Haeri
> Cc: C++
> Subject: Re: [Dev-C++] STL Map question
>=20
>=20
> Each Channel contains 3 UserList's as well. =20
> First, depicts all
> users in the Channel, the second depicts all the operators of=20
> the channel,
> and the third depicts the priviledged users who are not=20
> operators.=20
These above 3 UserList contain the connected-at-the-time kinds of people =
or
are their contents "constant", that is updated by another way?
> 2) The=20
> User class is
> being deleted, without being removed from the UserList. =20
> However, I can find
> no indication of this in the code. The code is many=20
> thousands of lines, it
> is not a small project by any means. Providing the source=20
> for the issue,
> would require the entire project as the issue is not=20
> specifically a syntax
> issue, but rather a situational issue. I do believe something has
> invalidated a User class, which a UserList has a pointer to,=20
> and when trying
> to use it, is causing a segmentation fault. I'm sure most of=20
> the experts
> here will agree with my conclusion and realize tracing this=20
> problem is no
> easy task.
You can place a special debugging code, a loop that checks that the =
entries
in all UserLists are consistent. An example is to sum up the sizes of =
each
map with the global to see where the problem is.
Then add a loop to verify each user using operator[]. Where you get as a
return value the pointer value 0 and in the UserList (which will be the =
one
that crashes) you get a pointer value then you have found the problem.
So make the above in a verify function which will be executed after =
every
complete entry update and which will be in the pseudocode-style:
// Assuming UserList is a typedef of a map
// and the UserList that crashes is the global
// because I do not remember.
void verify(const UserList &global, const UserList &whatever1, // etc)
{
=20
using namespace std;
UserList ::size_type sum=3Dwhatever1.size()+whatever.size()+//etc ;
if(sum!=3Dglobal.size())
{
for(UserList::const_iterator p=3Dglobal.begin(); p!=3Dglobal.end(); =
++p)
{
if(whatever1[p->first]+whatever2[p->first]+.... =3D=3D 0)
{
std::cerr<<"\n\nThe corrupted record is "<<p->first<<endl<<endl;
system("pause");
}
}
}
else cout<<"\n\nVerification phase passed\n\n";
}
=20
=20
>=20
> I've considered some commercial products like Purify, or some=20
> other memory
> tracking products, but I have no experience with any, since=20
> I've never had
> an issue I couldn't resolve purely with GDB. Since the=20
> problem traces back
> most likely to an invalid pointer reference, does anyone have=20
> suggestions on
> how I could possibly detect where the pointer is being deleted? I've
> considered the idea of using smart pointers to track the=20
> issue down, but
> again I'm not entirely certain of how to implement some code=20
> to track where
> the User is being deleted without being removed from the=20
> channels they are
> in... It could also potentially be an issue with overwritting=20
> memory, but
> with how often it is caused in exactly the same way, it's=20
> unlikely to be
> memory overbounding.
> I noticed a location where the key being used was being changed (a
> nickname), and in those cases, where the old code would just=20
> rename the
> nickname, I have now remove from the map and then readd to=20
> the map. When it
> tries to remove from the map is when it crashes. I can only=20
> assume that the
> problem is an invalid pointer, thus the map::find function is crashing
> because of invalid memory.=20
Do you check the result of map::find against map::end()?
Ioannis Vranos
=20
* Programming pages: http://www.noicys.freeurl.com
* Alternative URL 1: http://run.to/noicys
* Alternative URL 2: http://www.noicys.cjb.net
|
|
From: Ioannis V. <iv...@em...> - 2003-07-12 00:06:55
|
Here is what I said in a similar discussion in Usenet, it may help: "Sandeep Grover" <sa...@ma...> wrote in message news:3F0...@ma...... > Hi, > > If I do another delete on an object which has been deleted earlier, = then > how is > the system expected to behave ? It will get angry. > Is it an unpredictable behavior ?? Yes it is undefined behaviour. It may die, it may continue living and = die later, it may truncate data, everything. --=20 Ioannis * Programming pages: http://www.noicys.freeurl.com * Alternative URL 1: http://run.to/noicys * Alternative URL 2: http://www.noicys.cjb.net -------------------------------------------------------------------------= --- ----------------------- "Sandeep Grover" <sa...@ma...> wrote in message news:3F0...@ma...... > > > > Sandeep Grover wrote: > > > > > If I do another delete on an object which has been deleted = earlier, then > > > how is the system expected to behave? > > > > > > Is it an unpredictable behavior ?? > > > > It's undefined, so in theory, yes; anything could happen. > > > > S > > Thanks ! > > So, if I have an array of pointers; more than one of the entries could point > to > the same chunk of memory (allocated using new). How do I ensure that I > end up deleting that entry only once. I dont want to use reference-counting > kind of thing in constructor. Use a vector of the objects you want, or a list if it suits better the problem, and not a built in array of pointers. --=20 Ioannis * Programming pages: http://www.noicys.freeurl.com * Alternative URL 1: http://run.to/noicys * Alternative URL 2: http://www.noicys.cjb.net |
|
From: Hossein H. <ult...@em...> - 2003-07-12 20:39:25
|
Dear Ioannis,
I have just posted a response of this message to Shane, but
unfortunately I haven't set the header to have a Cc for the Dev-Cpp
Users. There, I have mentioned that your following assertion is most
likely to be wrong. Anyway, I will repeat it one time more to make it
clear to the group.
> Eh? Why? Both have the same speed, actually empty is usually
>
> // inside the class definition
> bool empty() const { return size()==0; }
This can be the case, but that isn't always true.
I know that holds for many of STL platforms, but they do not have to
follow that way.
> since map has to keep track of its size.
Has it? No, I don't think so! But I will be pleased if you can prove
me your assertion by mentioning its address in Standard. I don't think
that beeing the case, as I have found the followings in the STL Bible,
i.e., Generic Programming and the STL:
"size() is linear in container's size. (For many containers, such as
vector, and deque, size() is O(1). This satisfies the requirement that
it be O(n).)
maz_size() and empty() are amortised constant time."
(If you want me to address the citation precisely, it is in Section
9.1.1, i.e., Container. And the complete bibliography is:
Matthew H. Austern, Generic Programming and the STL: Using and
Extending the C++ Standard Template Library, Addisson Wesley, 1999,
ISBN: 0-201-30956-4.)
These lines make me to become more sure that there isn't any guarantee
in the Standard for size() and empty() to be equal in the sense of
runtime.
> In any case consider them as equal
> (an equality comparison doesn't take time!).
I don't know anything about the STL platform beeing used. But even if
the Standard has mentioned that O(empty()) == O(size()), that platform
may not be Standard-compliant. Therefore, size() may be a calculating
member function, meaning that it may compute the size and hence not be
constant time. But empty() is more likely to be just returning the
state of an internal flag. And that's why I mentioned to choose
empty() instead of size(). Because, the platform may well have
considered to compute the size of map every time size() is invoked.
And that beeing the case, there may be some (offencing) optimisations
the platform have chosen, and those are causing some unexpected
exception or memory invalidation that the platform itself, doesn't
know.
You may still think that there empty() and size() have the same
runtime. But that doesn't mean there are equal in any case. If you
have any doubt on this issue, consider Item 4 of Effective STL.
(Scott Meyers, Effective STL: 50 Specific Ways to Improve Your Use of
the Standard Template Library, Addison-Wesley, 2001,
ISBN: 0-201-74962-9.)
Regards,
--Hossein
--
__________________________________________________________
Sign-up for your own FREE Personalized E-mail at Mail.com
http://www.mail.com/?sr=signup
CareerBuilder.com has over 400,000 jobs. Be smarter about your job search
http://corp.mail.com/careers
|
|
From: Ioannis V. <iv...@em...> - 2003-07-12 22:03:49
|
> -----Original Message-----
> From: dev...@li...=20
> [mailto:dev...@li...] On Behalf=20
> Of Hossein Haeri
> Sent: Saturday, July 12, 2003 11:39 PM
> To: dev...@li...
> Subject: RE: [Dev-C++] STL Map question
>=20
>=20
> Dear Ioannis,
>=20
> I have just posted a response of this message to Shane, but
> unfortunately I haven't set the header to have a Cc for the Dev-Cpp
> Users. There, I have mentioned that your following assertion is most
> likely to be wrong. Anyway, I will repeat it one time more to make it
> clear to the group.
>=20
> > Eh? Why? Both have the same speed, actually empty is usually=20
> >=20
> > // inside the class definition
> > bool empty() const { return size()=3D=3D0; }
>=20
> This can be the case, but that isn't always true.
>=20
> I know that holds for many of STL platforms, but they do not have to
> follow that way.
Yes. Any implementor can follow his way, the standard defines only the
template interface but the above is a reasonable implementation. And I =
got
it straight from TC++PL 3. :-)
>=20
> > since map has to keep track of its size.=20
>=20
> Has it? No, I don't think so! But I will be pleased if you can prove
> me your assertion by mentioning its address in Standard. I don't think
> that beeing the case, as I have found the followings in the STL Bible,
> i.e., Generic Programming and the STL:
>=20
> "size() is linear in container's size. (For many containers, such as
> vector, and deque, size() is O(1). This satisfies the requirement that
> it be O(n).)
>=20
> maz_size() and empty() are amortised constant time."
It is not required by the standard but it would be prudent to not =
calculate
size() every time it is called. Also if I would have a choice between
storing information on whether it is empty or the size I would have =
chosen
the size since the empty can be estimated by the size and would require =
less
checks in the instance of the code where I would have placed a lot of =
checks
if the empty value is true or false and change it.
Anyway as I said only the interface is required by the standard but in =
C++
world all strive for maximum performance.
=20
> (If you want me to address the citation precisely, it is in Section
> 9.1.1, i.e., Container. And the complete bibliography is:
>=20
> Matthew H. Austern, Generic Programming and the STL: Using and
> Extending the C++ Standard Template Library, Addisson Wesley, 1999,
> ISBN: 0-201-30956-4.)
>=20
> These lines make me to become more sure that there isn't any guarantee
> in the Standard for size() and empty() to be equal in the sense of
> runtime.
Of course there is not. Nor there is any guarantee on which is faster =
nor
whether it takes milliseconds, seconds and weeks. However as I said what =
I
provided is a reasonable implementation.
>=20
> > In any case consider them as equal
> > (an equality comparison doesn't take time!).
>=20
> I don't know anything about the STL platform beeing used. But even if
> the Standard has mentioned that O(empty()) =3D=3D O(size()), that =
platform
> may not be Standard-compliant. Therefore, size() may be a calculating
> member function, meaning that it may compute the size and hence not be
> constant time.
Yes. It may also calculate the 1000 first digits of pi (3.14..) in the
meantime, but we are discussing reasonable implementations and having to
calculate the size() of every container that provides size() each time =
it is
called (and it may have millions) doesn't sound too reaaonable to me.
> But empty() is more likely to be just returning the
> state of an internal flag. And that's why I mentioned to choose
> empty() instead of size(). Because, the platform may well have
> considered to compute the size of map every time size() is invoked.
Yes, it may has decided manyy things. However we mau assume that all =
member
functions are maximally efficient, else throw the platform away!
> And that beeing the case, there may be some (offencing) optimisations
> the platform have chosen, and those are causing some unexpected
> exception or memory invalidation that the platform itself, doesn't
> know.
?!
> You may still think that there empty() and size() have the same
> runtime. But that doesn't mean there are equal in any case. If you
> have any doubt on this issue, consider Item 4 of Effective STL.
Read TC++PL 3. Straight from the creator of C++.
Ioannis Vranos
=20
* Programming pages: http://www.noicys.freeurl.com
* Alternative URL 1: http://run.to/noicys
* Alternative URL 2: http://www.noicys.cjb.net
|
|
From: Hossein H. <ult...@em...> - 2003-07-14 11:21:52
|
Dear Shane, > *boggle* You haven't heard of G++? GCC? These are the primary GNU based > compiler collection, used on 99% of unix systems I know of. I have, I am familiar with both, and I'm using them under the hood of Dev-C++. But I'm in doubt if you have mentioned the same name in your first email. Please excuse me if it is my fault (as I'm a careless man), but as I remember, the name of the implementation you had mentioned contained a 'D' letter, didn't it? (I have deleted that message so I can't check it anymore.) Anyway, thank you because of the links! It is obvious that you have made a big search and seemingly in a very angree state. It seems either I have misread your starting email, or your have miswritten it. I do appolgise if the first is the case! > ... I would dare say GCC is > likely used on a wider scale than Visual C++, or any other C/C++ compiler > I'm aware of. That's absolutely right! Definitely! > ... My next step, is to look into some tools for debugging memory problems. I'm > sure the program has hoards of them, but it would be nice as I said, if I > could trace back the usage of a memory address somehow. IIRC, STLPort has a good tool for your purpose. > ... Anyways, thanks for your interest, it's at least keeping my brain thinking > about the problem. I've been avoiding it for a while... Your welcome! I'm sure you would do the same if the problem was mine. > ... But I will > let you know if I figure out the problem. Hoping it to be solved ASAP, and looking for the solution. Wishes, --Hossein -- __________________________________________________________ Sign-up for your own FREE Personalized E-mail at Mail.com http://www.mail.com/?sr=signup CareerBuilder.com has over 400,000 jobs. Be smarter about your job search http://corp.mail.com/careers |
|
From: Ioannis V. <iv...@em...> - 2003-07-14 16:09:17
|
-----Original Message----- > From: dev...@li... > [mailto:dev...@li...] On Behalf > Of Hossein Haeri > Sent: Monday, July 14, 2003 2:22 PM > To: dev...@li... > Subject: Re: [Dev-C++] STL Map question > > but as I remember, the name of the implementation you had > mentioned contained a 'D' letter, didn't it? (I have deleted that > message so I can't check it anymore.) Keep in mind that there is the mailing list archive on line (which is unfortunately 12/24h behind but anyway): http://sourceforge.net/mailarchive/forum.php?forum=dev-cpp-users Ioannis Vranos * Programming pages: http://www.noicys.freeurl.com * Alternative URL 1: http://run.to/noicys * Alternative URL 2: http://www.noicys.cjb.net |
|
From: Hossein H. <ult...@em...> - 2003-07-14 12:19:53
|
Dear Ioannis,
> > > Eh? Why? Both have the same speed, actually empty is usually
> > >
> > > // inside the class definition
> > > bool empty() const { return size()==0; }
> >
> > This can be the case, but that isn't always true.
> >
> > I know that holds for many of STL platforms, but they do not have to
> > follow that way.
>
>
> Yes. Any implementor can follow his way, the standard defines only the
> template interface but the above is a reasonable implementation. And I got
> it straight from TC++PL 3. :-)
But that even doesn't mean that there aren't any other reasonable
implementations.
> It is not required by the standard but it would be prudent to not calculate
> size() every time it is called. Also if I would have a choice between
> storing information on whether it is empty or the size I would have chosen
> the size since the empty can be estimated by the size and would require less
> checks in the instance of the code where I would have placed a lot of checks
> if the empty value is true or false and change it.
Had you read "Effective STL," this has't been your answer. Sometimes,
there are policies such as willing to have a constant-time operation
on the map that have higher proiority for the implementer (for any
reason they know). And achieving that runtime needs you to cut down
the use of size update after any operation of the map.
I think the existance of nasty C++ implementations such as VC++6,
reveals that this is not just a fiction, and there even are wellknown
implementations who may have chosen that way.
> Anyway as I said only the interface is required by the standard but in C++
> world all strive for maximum performance.
You'r right. But max-performance of what? I mean, if there is an
operation, say O, that has higher priority from your point of view (as
the implementer, or disigner, etc.), and you want O to be done in a
constant time, and that forces you to forget updating size after O,
will you still think that max-performance obliges you to have size as
an internal member? Haven't you ever encountered nasty
implementations such as VC++6 that often have such higher priority
operations that don't seem to be reasonable at all? I have just
realised that the compiler we were talking about was GCC, and I
hartapologise for the suspection I have had to his majesty. But
remember that I didn't know that's GCC. Knowing that, don't you still
preserve me the right of suspecting the implementation?
> > (If you want me to address the citation precisely, it is in Section
> > 9.1.1, i.e., Container. And the complete bibliography is:
> >
> > Matthew H. Austern, Generic Programming and the STL: Using and
> > Extending the C++ Standard Template Library, Addisson Wesley, 1999,
> > ISBN: 0-201-30956-4.)
> >
> > These lines make me to become more sure that there isn't any guarantee
> > in the Standard for size() and empty() to be equal in the sense of
> > runtime.
>
>
>
> Of course there is not. Nor there is any guarantee on which is faster nor
> whether it takes milliseconds, seconds and weeks. However as I said what I
> provided is a reasonable implementation.
But, I want to mention one time more that, that doesn't mean the
shortage of any other reasonable one.
> Yes. It may also calculate the 1000 first digits of pi (3.14..) in the
> meantime, but we are discussing reasonable implementations and having to
> calculate the size() of every container that provides size() each time it is
> called (and it may have millions) doesn't sound too reaaonable to me.
Come on! I'm not joking! Even if that's not reasonable at all,
remember that there are largely-used implementations such as VC++6
that often make those mistakes.
> Yes, it may has decided manyy things. However we mau assume that all member
> functions are maximally efficient, else throw the platform away!
I agree with you in the sense of efficiency, but remember the problem
with (sometimes unwanted) priorities.
Furthermore, sometimes, the dicision of throwing a platform away is
not whithin our duty. Nor can we complain on it. E.g., the project may
be in a platform that is used for years and years, and changing it
imposes more cost to the wendors. As an other example, you may be one
of the ordinary programmers in more than 1000, in a software-house
that wants its products to have good GUIs, and so have chosen VC++6 as
they don't want to waste time for reinvnting the wheel! They may well
know about the vast erea of VC++6's bugs, but they have to tollerate
against it. So they are not going to change the platform. What would
you do then?
> > You may still think that there empty() and size() have the same
> > runtime. But that doesn't mean there are equal in any case. If you
> > have any doubt on this issue, consider Item 4 of Effective STL.
>
>
> Read TC++PL 3. Straight from the creator of C++.
Oh! That's a great book. The best "General Purpose" book in C++. I
read TC++PL:Spec, couple of years ago. (I myself, was teaching C++ in
university at those days, but unfortunately, I hadn't the opportunity
of reading that great book before. It was great and I found tones of
new fine points in it.) From that time, it's the first reference of
my C++ courses in university, and I'm very proud of it.
But that doesn't mean that the other books do not have any stuff to
mention. "Effective STL," for example, is one of the best books in the
history of C++, and is the most expert book in STL, indeed.
Regards,
--Hossein
--
__________________________________________________________
Sign-up for your own FREE Personalized E-mail at Mail.com
http://www.mail.com/?sr=signup
CareerBuilder.com has over 400,000 jobs. Be smarter about your job search
http://corp.mail.com/careers
|
|
From: Ioannis V. <iv...@em...> - 2003-07-14 16:22:43
|
> -----Original Message-----
> From: dev...@li...=20
> [mailto:dev...@li...] On Behalf=20
> Of Hossein Haeri
> Sent: Monday, July 14, 2003 3:19 PM
> To: dev...@li...
> Subject: RE: [Dev-C++] STL Map question
>=20
>=20
> Had you read "Effective STL," this has't been your answer.=20
:-)
> Sometimes,
> there are policies such as willing to have a constant-time operation
> on the map that have higher proiority for the implementer (for any
> reason they know). And achieving that runtime needs you to cut down
> the use of size update after any operation of the map.
Not any operation, size() has to be updated during insert() or erase() =
only.
Also bool empty() const { return size()=3D=3D0; } takes constant time.
=20
> I think the existance of nasty C++ implementations such as VC++6,
> reveals that this is not just a fiction, and there even are wellknown
> implementations who may have chosen that way.
Anyway we are talking without any basis here, the implementor can choose
whatever method he likes to implement size() but if he calculated size()
everytime it was called (or only the first time if no other change has =
been
made) would be unwise since our code would wait for the internal loop of =
our
thousands record counting to complete.
In any case one would expect that the perofmrmance of size() in a if()
statement wouldn't take 10 seconds. TC++PL provides the above check as a
reasonable implementation I agree with it.
> You'r right. But max-performance of what? I mean, if there is an
> operation, say O, that has higher priority from your point of view (as
> the implementer, or disigner, etc.), and you want O to be done in a
> constant time, and that forces you to forget updating size after O,
> will you still think that max-performance obliges you to have size as
> an internal member?=20
There is not any Big-Oh requirement of the standard both regarding =
size() or
empty(). In theory empty() could be slower than size() (since there is =
not
any kind of restriction), but I said let's try to be realists.
> Haven't you ever encountered nasty
> implementations such as VC++6 that often have such higher priority
> operations that don't seem to be reasonable at all?
I used VC++ 6 only to what it is best for. To learn C90. :-) Regarding =
ISO
C++ it is crap. VC++ .NET 2002/2003 on the other hand are very good
regarding C++ compliance.
> I have just
> realised that the compiler we were talking about was GCC, and I=20
> hartapologise for the suspection I have had to his majesty. But
> remember that I didn't know that's GCC. Knowing that, don't you still
> preserve me the right of suspecting the implementation?
Well I would start suspecting if the code was crawling.
=20
> I agree with you in the sense of efficiency, but remember the problem
> with (sometimes unwanted) priorities.
>=20
> Furthermore, sometimes, the dicision of throwing a platform away is
> not whithin our duty. Nor can we complain on it. E.g., the project may
> be in a platform that is used for years and years, and changing it
> imposes more cost to the wendors. As an other example, you may be one
> of the ordinary programmers in more than 1000, in a software-house
> that wants its products to have good GUIs, and so have chosen VC++6 as
> they don't want to waste time for reinvnting the wheel! They may well
> know about the vast erea of VC++6's bugs, but they have to tollerate
> against it. So they are not going to change the platform. What would
> you do then?
Does VC++ 6 crawl whem map::size() is used?
Ioannis Vranos
=20
* Programming pages: http://www.noicys.freeurl.com
* Alternative URL 1: http://run.to/noicys
* Alternative URL 2: http://www.noicys.cjb.net
|
|
From: Jaap de W. <wo...@ne...> - 2003-07-14 12:37:41
|
Hmm, I had problems like this also. Are you using a multithreaded environment? Is it possible that sometimes two threads at the same time are accessing the map, one for removing a key, and one for finding a key? Jaap > -----Original Message----- > From: Shane Bryldt [mailto:ast...@te...] > Sent: Friday, July 11, 2003 10:53 PM > To: Hossein Haeri > Cc: C++ > Subject: Re: [Dev-C++] STL Map question > ... > > Now, the effect of the issue, is as follows. A network of 6,000-10,000 > active users at any given time is regulated by a security > service. This > service runs and connects like a user, with special > priviledges. Anytime a > user connects to the network, the services is informed, and > the User is > added to a global UserList. The network also has smaller > units, known as > Channels. Each Channel contains 3 UserList's as well. > First, depicts all > users in the Channel, the second depicts all the operators of > the channel, > and the third depicts the priviledged users who are not > operators. 99% of > the time, the code work fine. Users constantly added and > removed from the > list. Periodically, what seems like an issue without a > pattern, the code > will crash with a segmentation fault while trying to call > "std::map<>::find()", with a valid key. Whether the key is > in the map, is > not definate, but the key passed in valid and should not have > a problem > being searched. > > This said, I have narrowed the issue down to one of 2 causes. > 1) Either > User's are being added to lists, and not being removed, and > the UserLists > are eventually gathering enough garbage that out of memory is being > encountered. The application has a signal hook for out of > memory, and it is > not being raised. So I am leaning more towards option 2) The > User class is > being deleted, without being removed from the UserList. > However, I can find > no indication of this in the code. The code is many > thousands of lines, it > is not a small project by any means. Providing the source > for the issue, > would require the entire project as the issue is not > specifically a syntax > issue, but rather a situational issue. I do believe something has > invalidated a User class, which a UserList has a pointer to, > and when trying > to use it, is causing a segmentation fault. I'm sure most of > the experts > here will agree with my conclusion and realize tracing this > problem is no > easy task. > > ... |
|
From: Shane B. <ast...@te...> - 2003-07-14 20:04:24
|
Actually, the program is making use of threads now, but all the memory each
thread is accessing, is independant of the memory the main thread is
accessing. To be painfully clear, the threads are used only to offload the
intensive process of dumping 60,000 records to a MySQL database. What
happens, is the database is dumped to a text file within a couple seconds,
then a thread is created to open each of the sql dump files made, and
read/import into the MySQL database. Functionally, it works perfectly and
the database has never had a problem dumping. The ONLY thing shared between
the threads, is a call to a function "Log" which is used once per thread, to
output to the logs that it's finished. Realizing the potential, a mutex
should be used on the Log class to prevent any accidental access at the same
time, but in the future I intend on pulling out the calls to "Log" and at
such a time there will be no use of shared memory, and thus no reason for
threads to be of concern.
As is stands now, I am not willing to believe that the shared call to
Log is the culprit, as it would be a more random occurance of crashes, not
always at the exact same point in the code. In fact, the point it's
crashing at, the threads never use. The threads don't even iterate the
map's, they simply open an already closed file after it's been dumped, and
then reads the file, imports to the database, and delete's the sql dump
files to indicate it is done (rather than using shared memory, the file not
existing is just as well).
After speaking with a few people, it appears to me that the problem is not
at all with STL, at least not the fault of STL, but rather of original
implementation. The original implementation used some very obscure direct
manipulation of array's, such that it would zero out array's when they
weren't used, yet left them allocated. And in some other cases, would
actually call realloc to reallocate the memory. This caused a little
confusion in the conversion to STL, with regards to performing the identical
operation with STL, and not changing the code calling on STL too
significantly. The truely strange problem is that between the two changes
of the code, the UserList code was not changed, other code that calls it
was, and so therein lies the problem. However, I am not skilled enough to
know of any good tools that can help me determine why the pointer being
accessed is invalid. More particularily, if there was a debugging tool for
checking memory, like the last time it was used before the crash occured, if
it could show me where it was free'd, or overwritten or whatever is
happening, I could most likely determine the cause, given a location as
general as a function it's occuring in. Unfortunately, I have scanned over
the code numerous times and can only find 1 location where a User class is
delete'd. And calls to that function appear to be called appropriately with
consideration for STL.
I am truely baffled, but I have given up blaming STL for the issue, there
has to be an overrun of memory writing, or somehow, something has
invalidated the memory that an STL map is still using. There is no reason
for this, and another very seasoned programmer has looked at the code with
no immediate noticable problems. If I wasn't in a position of
non-disclosure (actually, it's more like on my word that I won't release the
code, I can discuss the problems as I need to with other programmers), I
would tarball the code in question. However, with as complicated as the
code is, even a vetran programmer wouldn't want to dig into it without a lot
of patience and time, of which I could not ask of anyone anyways.
I thank everyone for exhausting their ideas, even if this thread ended up
more of a flame war about who thinks what the best book is. Unfortunately,
this problem is not resolved by any amount of books, regardless of how good
they are. The problem is in implementation, not lack of understanding. I
am almost certain that the map iterator has become invalid, and that's
causing the problem. But why, is the question regarding implementation.
A last note, just to get a couple opinions. The original code that worked,
would delete users as they were disconnected. The newer code, using the same
concept for UserList, crashes. What I have done (but not yet tested) is
changed the code where it delete's the User, instead of deleting them, it
sets a flag indicating they are ready to be processed for deletion. At the
top of every loop iteration, it generates a vector of Killed connections,
then steps through the vector and deletes them from the user list map. The
change in implementation of how the User is deleted may lend itself to
fixing the problem in certain very strange conditions. Does anyone see a
flaw with how I changed the code? I haven't tested it yet, beyond a
controlled environment where the crash wouldn't occur anyways. I'm hoping
with little hope that it may simply be a matter of iterator invalidation,
and by not deleting the User and removing it right away, it might (??? I'm
really running out of ideas) fix the problem.
Sincerely,
-Shane
----- Original Message -----
From: "Jaap de Wolff" <wo...@ne...>
To: "'Shane Bryldt'" <ast...@te...>; "Hossein Haeri"
<ult...@em...>
Cc: "C++" <dev...@li...>
Sent: Monday, July 14, 2003 6:36 AM
Subject: RE: [Dev-C++] STL Map question
> Hmm, I had problems like this also.
> Are you using a multithreaded environment?
> Is it possible that sometimes two threads at the same time are accessing
the
> map,
> one for removing a key, and one for finding a key?
>
> Jaap
>
> > -----Original Message-----
> > From: Shane Bryldt [mailto:ast...@te...]
> > Sent: Friday, July 11, 2003 10:53 PM
> > To: Hossein Haeri
> > Cc: C++
> > Subject: Re: [Dev-C++] STL Map question
> >
> ...
> >
> > Now, the effect of the issue, is as follows. A network of 6,000-10,000
> > active users at any given time is regulated by a security
> > service. This
> > service runs and connects like a user, with special
> > priviledges. Anytime a
> > user connects to the network, the services is informed, and
> > the User is
> > added to a global UserList. The network also has smaller
> > units, known as
> > Channels. Each Channel contains 3 UserList's as well.
> > First, depicts all
> > users in the Channel, the second depicts all the operators of
> > the channel,
> > and the third depicts the priviledged users who are not
> > operators. 99% of
> > the time, the code work fine. Users constantly added and
> > removed from the
> > list. Periodically, what seems like an issue without a
> > pattern, the code
> > will crash with a segmentation fault while trying to call
> > "std::map<>::find()", with a valid key. Whether the key is
> > in the map, is
> > not definate, but the key passed in valid and should not have
> > a problem
> > being searched.
> >
> > This said, I have narrowed the issue down to one of 2 causes.
> > 1) Either
> > User's are being added to lists, and not being removed, and
> > the UserLists
> > are eventually gathering enough garbage that out of memory is being
> > encountered. The application has a signal hook for out of
> > memory, and it is
> > not being raised. So I am leaning more towards option 2) The
> > User class is
> > being deleted, without being removed from the UserList.
> > However, I can find
> > no indication of this in the code. The code is many
> > thousands of lines, it
> > is not a small project by any means. Providing the source
> > for the issue,
> > would require the entire project as the issue is not
> > specifically a syntax
> > issue, but rather a situational issue. I do believe something has
> > invalidated a User class, which a UserList has a pointer to,
> > and when trying
> > to use it, is causing a segmentation fault. I'm sure most of
> > the experts
> > here will agree with my conclusion and realize tracing this
> > problem is no
> > easy task.
> >
> >
> ...
>
|
|
From: Ioannis V. <iv...@em...> - 2003-07-14 21:18:49
|
> -----Original Message-----
> From: dev...@li...
> [mailto:dev...@li...] On Behalf
> Of Shane Bryldt
> Sent: Monday, July 14, 2003 11:04 PM
> To: Jaap de Wolff
> Cc: C++
> Subject: Re: [Dev-C++] STL Map question
>
>
> After speaking with a few people, it appears to me that the
> problem is not
> at all with STL, at least not the fault of STL, but rather of original
> implementation.
[...]
It appears that you are an OK C programmer but missing the key concepts of
C++. I suggest you read "The C++ Programming Language" 3rd Edition or
Special Edition by Bjarne Stroustrup (the creator of C++), cover to cover.
It will take years, it will have pain but that's how knowledge is aquired.
> A last note, just to get a couple opinions. The original
> code that worked,
> would delete users as they were disconnected. The newer code,
> using the same
> concept for UserList, crashes. What I have done (but not yet
> tested) is
> changed the code where it delete's the User, instead of
> deleting them, it
> sets a flag indicating they are ready to be processed for
> deletion. At the
> top of every loop iteration, it generates a vector of Killed
> connections,
> then steps through the vector and deletes them from the user
> list map. The
> change in implementation of how the User is deleted may lend itself to
> fixing the problem in certain very strange conditions. Does
> anyone see a
> flaw with how I changed the code? I haven't tested it yet, beyond a
> controlled environment where the crash wouldn't occur
> anyways
Flags? See what I wrote above.
>. I'm hoping
> with little hope that it may simply be a matter of iterator
> invalidation,
> and by not deleting the User and removing it right away, it
> might (??? I'm
> really running out of ideas) fix the problem.
I have already told you what to do. Use the containers with *objects*, not
pointers.
E.g. map<string, User>Users;
map<string, User>::iterator p=Users.find("Zefxes");
if(p!=Users.end())
{
// ...
// Zefxes is erased
Users,erase(p));
// Users["Zefxes"] now returns User(0)
// Users.find("Zefxes") now returns Users.end()
}
Ioannis Vranos
* Programming pages: http://www.noicys.freeurl.com
* Alternative URL 1: http://run.to/noicys
* Alternative URL 2: http://www.noicys.cjb.net
|
|
From: Per W. <pw...@ia...> - 2003-07-14 23:45:13
|
In your text you mentioned something about the original code zeroing arrays on erase and performing reallocation. Just a note about a very important difference between C and C++. In C it is always safe to use memset() or ZeroMemory etc to clear a struct directly after allocation. You might also do it at any other time during the life of the struct with one little caveat. If the struct contained pointers to other data you might introduce a memory leak. However, in C++ it is not generally safe to perform memset() of a struct. If the object in question either is part of a multiple-inherritance hierarchy, has virtual methods, supports dynamic typecast etc, memset() might erase hidden data fields that are initialized by the object constructor. This kind of problem is very easily introduced in source code that originated as C, and then gradually transformed into C++. The result of overwriting a VMT - Virtual Method Table - field of an object is fatal and is guaranteed to bite hard. One other thing is that the STL code assumes that it controls the memory, and does not like someone else to try and reallocate items. The actual containers may not be reallocated, and if individual elements of the containsers needs to be reallocated, they should first be removed from the container, then reallocated and inserted again. /Per W On Mon, 14 Jul 2003, Shane Bryldt wrote: > The original implementation used some very obscure direct > manipulation of array's, such that it would zero out array's when they > weren't used, yet left them allocated. And in some other cases, would > actually call realloc to reallocate the memory. |
|
From: Ioannis V. <iv...@em...> - 2003-07-15 00:44:23
|
> -----Original Message----- > From: dev...@li... > [mailto:dev...@li...] On Behalf > Of Per Westermark > Sent: Tuesday, July 15, 2003 2:47 AM > To: Shane Bryldt > Cc: Jaap de Wolff; C++ > Subject: Re: [Dev-C++] STL Map question > > > In your text you mentioned something about the original code zeroing > arrays on erase and performing reallocation. > > Just a note about a very important difference between C and > C++. In C it > is always safe to use memset() or ZeroMemory etc to clear a struct You are in general right with an exception. 0 value is not necessarily in all types all bits zero (which is the 0 of a char/byte). Also a struct or a type may have padding bits and 0ing all its bytes calls for trouble. Regarding C99 I have read in Usenet (but was too bored to check the standard) that char can have padding bits because they believed that C90 allowed that, while C++ inherited from C90 the fact that a char cannot have padding bits. That's funny eh? Ioannis Vranos * Programming pages: http://www.noicys.freeurl.com * Alternative URL 1: http://run.to/noicys * Alternative URL 2: http://www.noicys.cjb.net |
|
From: Hossein H. <ult...@em...> - 2003-07-14 16:39:54
|
Dear Ioannis, > Keep in mind that there is the mailing list archive on line (which is > unfortunately 12/24h behind but anyway): > > http://sourceforge.net/mailarchive/forum.php?forum=dev-cpp-users Thanks! It was quite useful. Furthermore, I didn't know the address of the page. Thank you very much indeed. And about the compiler: I found out that you had mentioned its name as "GDB". And that's what I haven't ever heard about, and not GCC. Now, may I ask what it stands for? Thanks, --Hossein -- __________________________________________________________ Sign-up for your own FREE Personalized E-mail at Mail.com http://www.mail.com/?sr=signup CareerBuilder.com has over 400,000 jobs. Be smarter about your job search http://corp.mail.com/careers |
|
From: Ioannis V. <iv...@em...> - 2003-07-14 18:35:58
|
> -----Original Message----- > From: dev...@li... > [mailto:dev...@li...] On Behalf > Of Hossein Haeri > Sent: Monday, July 14, 2003 7:40 PM > To: dev...@li... > Subject: RE: [Dev-C++] STL Map question > > And about the compiler: I found out that you had mentioned its name as > "GDB". And that's what I haven't ever heard about, and not GCC. Now, > may I ask what it stands for? GDB is the debugger, but I have never used it. The original poster had provided us with the output of GDB. Ioannis Vranos * Programming pages: http://www.noicys.freeurl.com * Alternative URL 1: http://run.to/noicys * Alternative URL 2: http://www.noicys.cjb.net |
|
From: Shane B. <ast...@te...> - 2003-07-14 20:14:33
|
GCC is the GNU compiler collection, it includes front ends for C, C++, ADA,
Fortran and some others as I recall. GDB, is the GNU debugger. It is a
commandline debugging utility, commonly used on unix based systems. If
you've ever added -g (or -ggdb), you're adding debugging code that GDB uses
for debugging. Comparative to Win32 DEBUG versus RELEASE compilations on
VC++. GDB itself, I used mostly for tracing crash's and viewing memory.
This is how I've determined that the crash occurs when trying to access an
invalid pointer. When it breaks out into GDB in the crash, it leaves me at
a "map::find" statement, which, when I step into it, I find that the key (an
std::string) is valid, but the data portion, a pointer to an allocated User,
is somehow fubar'd, because if I try to print (no different than getting the
value of a variable in VC++ debugger) the pointer, GDB itself will indicate
that the program crashed while attempting to execute something by GDB. This
means that 1) the code crashes and drops me into the debugger, and 2) it is
in fact crashing because of the variable value, as executing the single
operation of printing the value causes an internal crash that GDB recovers
from, but ends execution of the program.
The problem I am seeing, I have never seen in all my time programming, and I
have a good 8 years background with C. Further issues with this, may result
in me reverting UserList to a true linked list implementation, instead of
STL, which could be the culprit even though I don't want to blame it. Even
reverting temporarily to a C linked list may help me in travelling the list
in the debugger to find out where the problem is (like if it's the last or
first element, etc)... Short of testing my new changes, this will be the
next step, to revert to a very slow and simple linked list until I can track
down the problem. At least I have some direction, I appreciate the help
everyone has offered.
Sincerely,
-Shane
p.s. http://www.gnu.org/software/gdb, for all the information you want on
GDB.
----- Original Message -----
From: "Hossein Haeri" <ult...@em...>
To: <dev...@li...>
Sent: Monday, July 14, 2003 10:39 AM
Subject: RE: [Dev-C++] STL Map question
> Dear Ioannis,
>
> > Keep in mind that there is the mailing list archive on line (which is
> > unfortunately 12/24h behind but anyway):
> >
> > http://sourceforge.net/mailarchive/forum.php?forum=dev-cpp-users
>
> Thanks! It was quite useful. Furthermore, I didn't know the address of
> the page. Thank you very much indeed.
>
> And about the compiler: I found out that you had mentioned its name as
> "GDB". And that's what I haven't ever heard about, and not GCC. Now,
> may I ask what it stands for?
>
> Thanks,
> --Hossein
>
> --
> __________________________________________________________
> Sign-up for your own FREE Personalized E-mail at Mail.com
> http://www.mail.com/?sr=signup
>
> CareerBuilder.com has over 400,000 jobs. Be smarter about your job search
> http://corp.mail.com/careers
>
>
>
> -------------------------------------------------------
> This SF.Net email sponsored by: Parasoft
> Error proof Web apps, automate testing & more.
> Download & eval WebKing and get a free book.
> www.parasoft.com/bulletproofapps1
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www23.brinkster.com/noicys/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
|
|
From: Ioannis V. <iv...@em...> - 2003-07-14 21:08:08
|
> -----Original Message----- > From: dev...@li...=20 > [mailto:dev...@li...] On Behalf=20 > Of Shane Bryldt > Sent: Monday, July 14, 2003 11:14 PM > To: Hossein Haeri > Cc: C++ > Subject: Re: [Dev-C++] STL Map question >=20 > When it breaks out into GDB in the crash,=20 > it leaves me at > a "map::find" statement, which, when I step into it, I find=20 > that the key (an > std::string) is valid, but the data portion, a pointer to an=20 > allocated User, > is somehow fubar'd, because if I try to print (no different=20 > than getting the > value of a variable in VC++ debugger) the pointer, GDB itself=20 > will indicate > that the program crashed while attempting to execute=20 > something by GDB. This > means that 1) the code crashes and drops me into the=20 > debugger, and 2) it is > in fact crashing because of the variable value, as executing=20 > the single > operation of printing the value causes an internal crash that=20 > GDB recovers > from, but ends execution of the program. This is happening because you use the library in an improper C style = way. Had the map contained objects instead of pointers you would find no = record when you used the find() and would get User(0) when accessed the key = using operator[]. Better use C++ as C++ and not as C. Quiz of the day: How do you write generic functions in C and how in C++? = :-) =20 > The problem I am seeing, I have never seen in all my time=20 > programming, and I > have a good 8 years background with C. Further issues with=20 > this, may result > in me reverting UserList to a true linked list=20 > implementation, instead of > STL, which could be the culprit even though I don't want to=20 > blame it.=20 !!! The problem is your programming approach, not the standard library! > Even > reverting temporarily to a C linked list may help me in=20 > travelling the list > in the debugger to find out where the problem is (like if=20 > it's the last or > first element, etc)... Short of testing my new changes, this=20 > will be the > next step, to revert to a very slow and simple linked list=20 > until I can track > down the problem. At least I have some direction, I=20 > appreciate the help > everyone has offered. The standard library provides a double linked list implementation, std::list. But your problem is that you code in C with classes, not C++! Ioannis Vranos =20 * Programming pages: http://www.noicys.freeurl.com * Alternative URL 1: http://run.to/noicys * Alternative URL 2: http://www.noicys.cjb.net |
