Recently, we had a very heated thread about GC with the usual
arguments (for, cons, etc) being exchanged.
In one of those threads, we came into the realloc problem.
What is the realloc problem?
Well, it begins with a successfull realloc:
char *q = realloc(p,2*n); // for n size_t, a simple
// exponential strategy.
At this point p is *invalid*, and also ALL its aliases.
This means that all other pointers to that object have become
invalid, also those that are stored in some structure
to cache them instead of calling a cover function for speed,
for instance, or all those aliases for the object that were
created when a pointer to this object was passed in the
stack/activation frame of a procedure:
void someFunction(buffer *p, size_t siz)
{
DoSomeWork1(p,siz);
DoSomeWork2(p,siz);
}
where
void DoSomeWork1(buffer *p,size_t siz)
{
if (siz < SpaceNeeded) {
q = realloc(p,SpaceNeeded);
if (q) {
p = q;
}
else
NoMemoryException();
}
// Do some work Fisrt part
}
Problem is, (obvious in this simple setup) that
the call to DoSomeWork2(p,siz) uses an invalid pointer.
This is an example of an indiscipline in aliases creation.
A sensible design MUST account for any reallocation of the buffer,
for instance by modifying the interface and returning the
reallocated pointer...
I.e. a DISCIPLINE in aliases creation and keeping the value
of pointers.
As we all know, C programs can be hugely more complex than
what this simple example shows. Here all is clear and easy to see
but not so in the real world where someFunction is a huge mosnter
written ages ago, and you forget that there could exist *aliases*
for that object.
Is the GC (Garbage Collector) of any help here?
----------------------------------------------
In the heat of the discussion at first I thought the GC
could be a valuable help here if used like this:
if (siz < SpaceNeeded) {
q = GC_malloc(SpaceUsed+SpaceNeeded);
memcpy(q,p,SpaceUsed);
p = NULL;
}
Since the GC will never free an object if it finds a pointer to it,
at first sight is a better way to handle this problem.
But this is only at first sight. Actually, if there is an alias for our
object (like in the function parameters to SomeFunction above)
that alias will mean that the GC will keep the object around, BUT
we have now actually TWO objects around:
1) The old object that is pointed to by
the pointer in SomeFunction()
2) The new reallocated object within DoSomeWork1
And obviously hell will appear quickly when some function
works in the first copy and another works with the second one!
So, in this case the GC is no better than realloc, and can produce
even worst bugs since they are MUCH more harder to find.
What does it mean an alias discipline?
--------------------------------------
In C you can create an alias for an object with an incredible easy.
char *a = malloc(1024);
char *b=a;
You can even create ANONYMOUS aliases, for instance when you do:
extern T * externalFunction(T *input);
void someFunction(void)
{
T input_data;
// Fill input_data with values
externalFunction(&input_data);
// Now we have created an anonymous alias for input_data
}
An alias discipline means that externalFunction must NEVER store
that pointer that it receives under any circumstances.
And that can be extremely difficult to do, but it *must* be done.
Finding out this kind of bugs can be extremely hard because
they tend to appear as "intermitent" bugs. Sometimes
they happen, sometimes they disappear. Obviously, it depends
on the whims of the malloc/realloc/free implementation and
on the concrete pattern of memory usage of the program.
It may be that realloc does NOT reuse immediately the memory block.
In that case this bug is invisible until the memory allocation system
reuses the block.
When the allocator returns a pointer to this block, it may be that
the part of the block that is overwritten is no longer used
by the program...
OR it may be that SUDDENLY you see (after hours and hours of debugging)
that SUDDENLY a variable mysteriously changes its value
without any affectation to it!
I have had bugs like this.
I do not wish anyone here one of those!
jacob
15  2422 
jacob navia wrote:
Recently, we had a very heated thread about GC with the usual
arguments (for, cons, etc) being exchanged.
With GC, the GC dictates when free() happens, and this has semantic
implications. Usually much more so for true OO systems. In C its
actually less of a big deal since memory is really the only thing that
you care about.
In one of those threads, we came into the realloc problem.
What is the realloc problem?
Well, it begins with a successfull realloc:
char *q = realloc(p,2*n); // for n size_t, a simple
// exponential strategy.
At this point p is *invalid*, and also ALL its aliases.
C does not state *how* these functions are implemented. In fact the
reference count on the allocation for p need not be decreased at all.
If the mechanism decreases the size or requires a new allocation, then
a new allocation must be generated and stored in q, otherwise q is
simply added to the list of references for that memory location (after
possibly being expanded, but left in place). After the inevitable p =
q; operation, what p used to be pointing at loses one reference, and
whatever q is pointing at gains one. I don't see the problem.
I.e, you would implement as equivalent in functionality to q = malloc
(2*n); free (p); (in a GC system, I assume that free(p) is basically a
no-op) and just exploit the case where you can just simplify that to
enlarge(p, 2*n); q = p;
--
Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/ we******@gmail.com wrote:
jacob navia wrote:
>>Recently, we had a very heated thread about GC with the usual
arguments (for, cons, etc) being exchanged.
With GC, the GC dictates when free() happens, and this has semantic
implications. Usually much more so for true OO systems. In C its
actually less of a big deal since memory is really the only thing that
you care about.
>>In one of those threads, we came into the realloc problem.
What is the realloc problem?
Well, it begins with a successfull realloc:
char *q = realloc(p,2*n); // for n size_t, a simple
// exponential strategy.
At this point p is *invalid*, and also ALL its aliases.
C does not state *how* these functions are implemented. In fact the
reference count on the allocation for p need not be decreased at all.
If the mechanism decreases the size or requires a new allocation, then
a new allocation must be generated and stored in q, otherwise q is
simply added to the list of references for that memory location (after
possibly being expanded, but left in place). After the inevitable p =
q; operation, what p used to be pointing at loses one reference, and
whatever q is pointing at gains one. I don't see the problem.
Well the problem is difficult to see.
The problem is not with the reallocation itself, the problem is
with the aliases stored elsewhere that use the old value of
p
Of course I speak in the case that realloc MOVES the object because
there is no free block with size new_size. In this case, the object
has been MOVED and all pointers that used the old reference
point to a FREE BLOCK!!
This block will be eventually reused by the malloc/realloc/free system,
and will get to other variables.
The old pointers point to that memroy area however, and then you have
the memory overwrite!
jacob
jacob navia wrote:
we******@gmail.com wrote:
jacob navia wrote:
>Recently, we had a very heated thread about GC with the usual
arguments (for, cons, etc) being exchanged.
With GC, the GC dictates when free() happens, and this has semantic
implications. Usually much more so for true OO systems. In C its
actually less of a big deal since memory is really the only thing that
you care about.
>In one of those threads, we came into the realloc problem.
What is the realloc problem?
Well, it begins with a successfull realloc:
char *q = realloc(p,2*n); // for n size_t, a simple
// exponential strategy.
At this point p is *invalid*, and also ALL its aliases.
C does not state *how* these functions are implemented. In fact the
reference count on the allocation for p need not be decreased at all.
If the mechanism decreases the size or requires a new allocation, then
a new allocation must be generated and stored in q, otherwise q is
simply added to the list of references for that memory location (after
possibly being expanded, but left in place). After the inevitable p =
q; operation, what p used to be pointing at loses one reference, and
whatever q is pointing at gains one. I don't see the problem.
Well the problem is difficult to see.
The problem is not with the reallocation itself, the problem is
with the aliases stored elsewhere that use the old value of
p
Of course I speak in the case that realloc MOVES the object because
there is no free block with size new_size. In this case, the object
has been MOVED and all pointers that used the old reference
point to a FREE BLOCK!!
Garbage collection can't work that way. The block is not MOVED. It is
COPIED. In the GC version of realloc, you would have to open the
possiblity of a new allocation being made without the old one
disappearing. In GC the only way a block can be freed is when the
references to it are gone. This would introduce a new semantic versus
what we have in typical non-GC reallocs, but that's because it isn't
trying to solve that kind of problem. The problem, of course, is much
worse if in the non-GC case, as there is no possibility of recovery for
aliased pointers that have been freed.
Have you looked at the Boehm GC to see how it solves this problem?
--
Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/ we******@gmail.com wrote:
jacob navia wrote:
>>we******@gmail.com wrote:
>>>jacob navia wrote:
Recently, we had a very heated thread about GC with the usual
arguments (for, cons, etc) being exchanged.
With GC, the GC dictates when free() happens, and this has semantic
implications. Usually much more so for true OO systems. In C its
actually less of a big deal since memory is really the only thing that
you care about.
In one of those threads, we came into the realloc problem.
What is the realloc problem?
Well, it begins with a successfull realloc:
char *q = realloc(p,2*n); // for n size_t, a simple
// exponential strategy.
At this point p is *invalid*, and also ALL its aliases.
C does not state *how* these functions are implemented. In fact the
reference count on the allocation for p need not be decreased at all.
If the mechanism decreases the size or requires a new allocation, then
a new allocation must be generated and stored in q, otherwise q is
simply added to the list of references for that memory location (after
possibly being expanded, but left in place). After the inevitable p =
q; operation, what p used to be pointing at loses one reference, and
whatever q is pointing at gains one. I don't see the problem.
Well the problem is difficult to see.
The problem is not with the reallocation itself, the problem is
with the aliases stored elsewhere that use the old value of
p
Of course I speak in the case that realloc MOVES the object because
there is no free block with size new_size. In this case, the object
has been MOVED and all pointers that used the old reference
point to a FREE BLOCK!!
Garbage collection can't work that way. The block is not MOVED. It is
COPIED.
Copied to a NEW location yes.
Then, since the old object is still reachable from
its aliases (see the code I posted) there is some
code that will use the new location and some other code
that retained the old aliases to the object that will use the
old location.
So, in the case of the GC you have TWO objects around!!!
This is even worst than malloc/free!
Some part of the software will work with the new object, some
other will work with the old object.
HELL!!!
jacob navia wrote:
we******@gmail.com wrote:
jacob navia wrote:
>we******@gmail.com wrote:
jacob navia wrote:
Recently, we had a very heated thread about GC with the usual
arguments (for, cons, etc) being exchanged.
With GC, the GC dictates when free() happens, and this has semantic
implications. Usually much more so for true OO systems. In C its
actually less of a big deal since memory is really the only thing that
you care about.
In one of those threads, we came into the realloc problem.
What is the realloc problem?
Well, it begins with a successfull realloc:
char *q = realloc(p,2*n); // for n size_t, a simple
// exponential strategy.
At this point p is *invalid*, and also ALL its aliases.
C does not state *how* these functions are implemented. In fact the
reference count on the allocation for p need not be decreased at all.
If the mechanism decreases the size or requires a new allocation, then
a new allocation must be generated and stored in q, otherwise q is
simply added to the list of references for that memory location (after
possibly being expanded, but left in place). After the inevitable p =
q; operation, what p used to be pointing at loses one reference, and
whatever q is pointing at gains one. I don't see the problem.
Well the problem is difficult to see.
The problem is not with the reallocation itself, the problem is
with the aliases stored elsewhere that use the old value of
p
Of course I speak in the case that realloc MOVES the object because
there is no free block with size new_size. In this case, the object
has been MOVED and all pointers that used the old reference
point to a FREE BLOCK!!
Garbage collection can't work that way. The block is not MOVED. It is
COPIED.
Copied to a NEW location yes.
Then, since the old object is still reachable from
its aliases (see the code I posted) there is some
code that will use the new location and some other code
that retained the old aliases to the object that will use the
old location.
So, in the case of the GC you have TWO objects around!!!
Correct.
This is even worst than malloc/free!
No, in the non-GC case you would have UB, since the old pointers no
longer point to valid memory. A programmer's expectation that such
pointers are pointing to the same thing obviously has to be dealt with
by the programmer whether using a GC strategy or not. This is still C,
and as such a C programmer should not expect to have to do anything
less.
Some part of the software will work with the new object, some
other will work with the old object.
Yes -- see your problem is that you are calling it an *ALIAS*, when it
is nothing of the sort. Its a "stale copy". If the pointer values are
not pointing to the same object (which goes without saying after a
realloc that outputs a differen pointer), then there is no way for them
to be aliases of each other. In fact this was the addenda that I was
specifically pointing out that you needed -- the new object must not
free or overlap the old object; i.e., it has to behave as if it were a
new allocation.
Do you see that in the mere *SYNTAX* of q = realloc (p, 2*n) you *have*
to have two pointers with different values (in some non-predictable
cases)? Unless you change the declaration of realloc to void * realloc
(void * &p, size_t sz); which is a C++-ism there is no way of getting
around this. I have presented you with one simple way to map a GC
strategy to make that work. You are complaining about a curious
anomily (that is nevertheless still well defined) in a scenario that is
far worse in the non-GC case -- I have little sympathy for this point
of view.
If you want to think about alternate strategies then fine, but you'd
better think hard about them. If you have a fully ref-counted and back
pointer based system, then you can try to simultaneously update every
old pointer (including p) to become the value q, and *truly* free the
old allocation. However, this sort of strategy means you have to
directly clean up all autos upon every function return, and
auto-initialize *all* values. Sacrificing the inner loop for easier GC
-- I'm not sure that's a good trade off.
The more typical state of the art GC system scans the whole stack and
memory in "generational stages" (I am not familliar with the exact
mechanisms). But If you want to try to update those pointers by
scanning the entire stack and active memory space for matching pointer
patterns, then you will actually *fail* because the conservative
pattern scan mechanism will falsely flag some bit patterns as being
that pointer, when they just happen to coincidentally match.
If I were you, I would do it the way I suggest. Your alternatives
(which include not supporting realloc) are not nearly as ideal.
--
Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/
jacob navia wrote:
>
.... snip ...
>
What is the realloc problem?
Well, it begins with a successfull realloc:
char *q = realloc(p,2*n); // for n size_t, a simple
// exponential strategy.
At this point p is *invalid*, and also ALL its aliases.
No. At this point p MAY BE invalid. If ((p == q) || (NULL == q))
holds then p is still valid. This assumes a C99 compiler that
accepts // comments, which in turn should never be used in
newsgroups because of line wrap problems.
Do try to be exact and thorough in this newsgroup. Or else the
pedants will getcha.
--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>
CBFalconer said:
jacob navia wrote:
>>
<snip>
>>
Well, it begins with a successfull realloc:
char *q = realloc(p,2*n); // for n size_t, a simple
// exponential strategy.
At this point p is *invalid*, and also ALL its aliases.
No. At this point p MAY BE invalid. If ((p == q) || (NULL == q))
holds then p is still valid.
We know q isn't NULL because he said it's a *successful* realloc. But we
*can't* know whether p == q because p /might/ be indeterminate and
therefore we cannot safely use its value.
Do try to be exact and thorough in this newsgroup. Or else the
pedants will getcha.
Gonsider yourself getched. :-)
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
I'm not a C programmer, but what I think you're trying to solve is so
called dangling pointers(at least in C++), if that's the case, why
don't you take a look at Smart Pointers implementation, probabely a
good introduction to that can be found in C++ Primer by Lippman. I hope
it helps.
Peyman wrote:
I'm not a C programmer, but what I think you're trying to solve is so
called dangling pointers(at least in C++)
That's really hard to say, as you didn't bother to quote whatever
message you're replying to. I know Google does that automatically for
you now, so there's really little excuse.
Brian
Default User wrote:
Peyman wrote:
>>I'm not a C programmer, but what I think you're trying to solve is so
called dangling pointers(at least in C++)
That's really hard to say, as you didn't bother to quote whatever
message you're replying to. I know Google does that automatically for
you now, so there's really little excuse.
Brian
He was answering to the "Aliases in C" thread
jacob navia wrote:
Default User wrote:
Peyman wrote:
I'm not a C programmer, but what I think you're trying to solve
is so called dangling pointers(at least in C++)
That's really hard to say, as you didn't bother to quote whatever
message you're replying to. I know Google does that automatically
for you now, so there's really little excuse.
He was answering to the "Aliases in C" thread
I know what thread, obviously, but that thread title doesn't explain
what he's talking about in the post.
Brian
jacob navia <ja***@jacob.remcomp.frwrites:
Default User wrote:
>Peyman wrote:
>>>I'm not a C programmer, but what I think you're trying to solve is so
called dangling pointers(at least in C++)
That's really hard to say, as you didn't bother to quote whatever
message you're replying to. I know Google does that automatically for
you now, so there's really little excuse.
Brian
He was answering to the "Aliases in C" thread
Yes, but it's hard to tell what actual question he was answering,
since he didn't provide any context.
--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Keith Thompson wrote:
jacob navia <ja***@jacob.remcomp.frwrites:
Default User wrote:
Peyman wrote:
I'm not a C programmer, but what I think you're trying to solve is so
called dangling pointers(at least in C++)
That's really hard to say, as you didn't bother to quote whatever
message you're replying to. I know Google does that automatically for
you now, so there's really little excuse.
Brian
He was answering to the "Aliases in C" thread
Yes, but it's hard to tell what actual question he was answering,
since he didn't provide any context.
--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Sorry everyone, I answered to the first post by "Jacob Navia".
jacob navia wrote:
Default User wrote:
>Peyman wrote:
>>I'm not a C programmer, but what I think you're trying to solve
is so called dangling pointers(at least in C++)
That's really hard to say, as you didn't bother to quote whatever
message you're replying to. I know Google does that automatically
for you now, so there's really little excuse.
He was answering to the "Aliases in C" thread
So? Does that magically make the missing quotations appear?
--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>
Peyman wrote:
Keith Thompson wrote:
>jacob navia <ja***@jacob.remcomp.frwrites:
>>Default User wrote:
Peyman wrote:
I'm not a C programmer, but what I think you're trying to
solve is so called dangling pointers(at least in C++)
That's really hard to say, as you didn't bother to quote
whatever message you're replying to. I know Google does that
automatically for you now, so there's really little excuse.
He was answering to the "Aliases in C" thread
Yes, but it's hard to tell what actual question he was answering,
>since he didn't provide any context.
Sorry everyone, I answered to the first post by "Jacob Navia".
Which you have still not quoted. Google is NOT usenet. It is only
a flawed interface to the actual usenet system. There is never any
reason to assume that your reader has, or has ever had, access to
previous post. So read the links below:
--
Some informative links:
news:news.announce.newusers http://www.geocities.com/nnqweb/ http://www.catb.org/~esr/faqs/smart-questions.html http://www.caliburn.nl/topposting.html http://www.netmeister.org/news/learn2quote.html This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Mike Ash |
last post by:
I recently had a project dropped into my lap that is written in JSP
running on Apache/Resin. A previous version of the application is
already running and configured on the production server, but...
|
by: Andrew |
last post by:
With command-line interface ( 3.23.37, UNIX Socket ) all is well with
column aliasing. However, column aliases disappear in Excel, over
ODBC, when there are multiple (joined) tables in the query.
...
|
by: Kevin |
last post by:
I'm making my first attempt to put embedded
SQL in a visual C++ application and I'm
having trouble getting aliases to work.
If I try the following SQL query on MS SQL 7.0
it works fine.
SELECT...
|
by: Krzysiek |
last post by:
Hi all,
I have an issue with QSYS\QADBXREF file - it keeps aliases on tables.
I take care of an application that works on many places (servers) and
on one of them it's not possible to create...
|
by: mp |
last post by:
i have a python program which attempts to call 'cls' but fails:
sh: line 1: cls: command not found
i tried creating an alias from cls to clear in .profile, .cshrc, and
/etc/profile, but none...
|
by: Daniel Rucareanu |
last post by:
I have the following script:
function Test(){}
Test.F = function(){}
Test.F.FF = function(){}
Test.F.FF.FFF = function(){}
Test.F.FF.FFF.FFFF = function(){}
//var alias = function(){};
var...
|
by: Chris Thomasson |
last post by:
I was thinking of how I was going to create a robust versioning system in
Standard C++ for my library and was wondering exactly what the point of a
namespace alias is? The seem like a rather...
|
by: drexcol |
last post by:
I am a php newbie and am trying to write a script that will direct visitors to specific pages on my website based on which of several url’s they have entered (all are aliases of the main website)....
|
by: dom.k.black |
last post by:
Is it still common practice to use type aliases (INT, PCHAR etc).
It looks ugly and breaks the syntax highlighting, are there any
advantages these days (MSVC++6.0 and later)? I could understand...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
| |
