Garbage collection

[Flash Gordon]

Eligiusz Narutowicz wrote, On 27/04/08 20:19:

Obviously it *can* fail. A programmers job is to ensure it doesnt in a
properly configured system.

So how are you going to ensure that memory fragmentation does not occur?

And not using it is not a solution.

Only some of the time. Some times not using it is the *best* solution,
and that is far more likely to be the case in safety critical (or even
safety related) SW than in other areas.

Very, very, very , very limited yes.

So limited that people can spend there entire careers on such SW. I
worked in a company for 15 years where dynamic allocation and recursion
where banned, and I was one of many developers and the ban was in place
before I joined. Most of that SW was not safety critical, but some was.
A lot more of the SW was mission critical.

Obviously there is a massive amount of SW where such a ban is not
appropriate.

But if you program for worst case then you might as well give up in my
opinion.

When developing for a safety critical system your job *is* to develop
for the worst case, because if not someone (or many people) can end up
dead! I'm not exaggerating by the way, I have worked on a system where
an incorrect result from the SW could lead pretty directly to a
fatality, although normally the system designers managed to have things
arranged so that there was a physical system to prevent fatality rather
than just SW.

 

[Hallvard B Furuseth]

Yes you can use it. I was referring to the process of scanning memory
for adjacent blocks and trying to build bigger blocks from scattered
pieces of memory.

Join freed memory blocks? A bad malloc/free implementation can fail at
that too.

But that's not compacting. Compacting is when you move used memory and
update all pointers to it, so that many small fragments of freed memory
can get joined into one or few bigger fragments.

One could implement compacting collections in C with indirect pointers:
Keep a table of pointers to live memory blocks. Implement a C pointer
as a pair (table entry, offset into that memory block). When moving a
block of memory, you only need to update the pointer in the table.

 

[Hallvard B Furuseth]

Join
adjacent

freed memory blocks? A bad malloc/free implementation can fail at
that too.

But that's not compacting.

Er, yes it was, when I didn't say "adjacent" above

 

[Ian Collins]

Not with an off-the-shelf C compiler, at least. It should be possible
to produce a C implementation that reliably knows which locations are
pointers, and have the GC adjust them accordingly.

That would be very hard to do. A conservative GC has the option of
assuming a block of memory that matches a pointer is a pointer and not
freeing said pointer. Any code attempting to relocate a block of memory
would have to know with absolute certainty that a matching pattern in
memory was a pointer in order to update it.

You would have to
impose some more restrictions of the kind that conservative GCs
already have concerning the "hiding" of pointers.

As I said, you would end up with an ultraconservative GC..

 

[Eligiusz Narutowicz]

A common technique for tracking memory allocations and frees is to
provide a logging implementation for testing. Remember it isn't the
allocation functions that are being tested, its the balance of
allocations and frees.

Indeed.

And I never said anything differently. But Jacob misses the obvious
thing - "modules" pass around a lot of malloc info. The logging I was
referring to was as simple as showing a balance between malloc and free.

 

[Ian Collins]

Actually, I would be most concerned with fragmentation since proving
that memory isn't going to get fragmented will be a real bitch.

Which is why GC really only comes into its own when it is designed into
a language from day 1.

 

[Friedrich Dominicus]

Some people are content with a few false references and thus the Boehm
GC works for them. I hope that their software isn't used for something
involving human lives, and that the allocations retained aren't
large.

Well I bet C is used in that area also. I just can hope it was
"tested" long and well enough to not contain any of the typical bugs
which plagues us C programmers.

Regards
Friedrich

 

[Friedrich Dominicus]

Thanks for this interesting link. I did not know it, but looking over
it the suggestions seems to be better not using C++ at all. I can
agree witht that wholeheartly ;-)

Regards
Friedrich

 

[Friedrich Dominicus]

Unfortunately making an accurate GC for C would require compiler
support, and even then it would break in some cases due to the design of
C.

Yes it would change considerably instead of
"The programmers knows what he does" it would be
"The programmer knows what he does but I know better in the dynamic
memory allocation area"

that alone suggest it would be more complex ;-)

Some people are content with a few false references and thus the Boehm
GC works for them. I hope that their software isn't used for something
involving human lives, and that the allocations retained aren't
> large.

I can not folow the arguments follow you mean the GC has bugs while
collecting things it is not supposed to collect or how do I have to
understand that.

This thread now has goten quite long. And many good and not so good
arguments were brought up. But seein it in a context of safety-critial
I think it's just one part (and I would think a smaller problem) to
have or not to have GC.

I for my part am nervouis with both alternatives, and I think
programmers should feel a bit uneasy about that area be it that they
support GC or beeing against it. There are so many other things which
can go wrong.

But let's see what might lead to use of C despite it's
shortcomings. It seem one thing C is well beyond nearly every other
language under the programming sun is that C compilers are now around
for more than 50 years. And the shortcomings have been surely
recogniced and they lead to a really big industry for "handling those
shortcomings". So I'd argue there's hardly a language whith more tools
for "getting around the early design decisions" than for every other
language.

Well nearly every other language does not need them. But are those
tools as mature? The questions still would be how one can judge that?
For C the "history of things implemented" is IMHO a hint on how "good
C really is" nearly all our "base tool" are based on C. Be it the
Operating Systems, Databases or any kind of Server. So I think one can
conclude that C is in the top of the maturity list. Probably this has
lead to use C in areas where there might be (theoretical or practical)
better alternatives. Howerver any time I read about safety-critical
software I have a somehow ungut feeling. But isn't somehow larger
while thinking of using GC with C or sticking to the manual memory
handling....

Regards
Friedrich

 

[Flash Gordon]

Chris Thomasson wrote, On 28/04/08 05:46:

[...]

Read again. I said that a CONSERVATIVE GC is not OK for airplane
software because it can leak memory because random correspondence
between pointers and other data in the stack.

[...]

JSF C++ standards:

http://www.research.att.com/~bs/JSF-AV-rules.pdf

You would nead a slick real-time garbage collector in order for it to
work real within that type of hardcore dynamic environment...

Well, yes, since it does exactly what I said and bans the use of
malloc/realloc. Well, it allows you to use them during initialisation
which someone else pointed out does not have the same problems.

I don't have access to the coding standards I used to work to so I can't
post them.

 

[Stuart]

With GC in safety-critical programs, the question is "will this be the
time the collector pauses the program for a dangerously long time in
order to do its job, or fails to collect enough memory?"

With CBFalconer-code the question is "has cbfalconer.home.att.net
recently been outsourced to some kid in India?"

This is why GC is the best choice for safety-critical programs nowadays.

How do you conclude this from the two statements you made?

The first seems to describe a classically difficult problem and so indicates
that using GC creates a difficult to resolve safety issue.

The second appears to be trying to suggest some problem of being unsure as
to who actually wrote the code [I say appears because there are many
programmers on the Indian subcontinent, some quite youthful, who are very
skilled and well-educated - but this would make the conclusion even more
bizarre. So assuming it is some reference to the recurrent appearance of,
apparently Indian, students submitting coursework questions on this forum
and is intended to be derogatory...]. There are two immediate difficulties
from this suggestion:

1) The design/code is available for review (and typically for a
safety-critical system would be) so any shoddy work would be discernible.
Since establishing code quality is something that needs to be done for all
the safety-critical software this particular element of the code does not
seem to be posing any different or new problem.
2) Any concern about the people undertaking the design/coding of the
software would appliy to all the software - not just some element of it.

So the second statement is [ir]relevant irrespective of the use of GC.

Given this I fail to see how you draw your conclusion.

 

[Bartc]

Eligiusz Narutowicz said: ....

It's not just easy. It's almost trivial.

Sure. Have a look at 4.26 p.59 here as to why they restrict use of
malloc/free. This is nothing to do with how able the programmer is:

JSF C++ standards:
http://www.research.att.com/~bs/JSF-AV-rules.pdf

And I mentioned (if I can quote myself!) regarding avoid use of malloc():

Compare these two pieces of code:
(1)
char array[10000];

(2)
char *array;
array=malloc(10000);
if (array==NULL) puts("YOU'RE DEAD"); /* what else can it do? */

That's must be plenty of code examples so complex (I'm thinking in terms of
recursive stuff) where: (a) you can't determine easily if it will run out of
memory, even ignoring fragmentation issues; (b) nor whether you can always
balance malloc() and free(); (c) if malloc() fails recovery is next to
impossible.

So it can only be almost trivial where the program itself is almost trivial
(in complexity and runtime unknowns rather than in size).

 

[jacob navia]

Eligiusz Narutowicz said: ...
It's not just easy. It's almost trivial.

Sure. Have a look at 4.26 p.59 here as to why they restrict use of
malloc/free. This is nothing to do with how able the programmer is:

JSF C++ standards:
http://www.research.att.com/~bs/JSF-AV-rules.pdf

And I mentioned (if I can quote myself!) regarding avoid use of malloc():

Compare these two pieces of code:
(1)
char array[10000];

(2)
char *array;
array=malloc(10000);
if (array==NULL) puts("YOU'RE DEAD"); /* what else can it do? */

That's must be plenty of code examples so complex (I'm thinking in terms of
recursive stuff) where: (a) you can't determine easily if it will run out of
memory, even ignoring fragmentation issues; (b) nor whether you can always
balance malloc() and free(); (c) if malloc() fails recovery is next to
impossible.

So it can only be almost trivial where the program itself is almost trivial
(in complexity and runtime unknowns rather than in size).

For Mr Heathfield all is trivial... He doesn't even need a debugger most
of the time. Superman comes to him to receive lessons in programming.

Now, he could be a millionaire because all people that buy expensive
malloc debugging tools would switch to his trivial method and pay HIM
instead of all those expensive tools...

 

[Hallvard B Furuseth]

(...)
With CBFalconer-code the question is "has cbfalconer.home.att.net
recently been outsourced to some kid in India?"

This is why GC is the best choice for safety-critical programs nowadays.

Clearly forgetting the "" was unfortunate. Sorry about that.

 

[Ian Collins]

For Mr Heathfield all is trivial... He doesn't even need a debugger most
of the time. Superman comes to him to receive lessons in programming.

Now, he could be a millionaire because all people that buy expensive
malloc debugging tools would switch to his trivial method and pay HIM
instead of all those expensive tools...

Na, I'll stick with the excellent and free tools my platform of choice
provides.

 

[Stuart]

Clearly forgetting the "" was unfortunate. Sorry about that.

It would have clarified things somewhat ;-)

 

[Flash Gordon]

Hallvard B Furuseth wrote, On 28/04/08 11:25:

Clearly forgetting the "" was unfortunate. Sorry about that.

Hey, it happens.

 

[Flash Gordon]

Ian Collins wrote, On 28/04/08 00:05:

Which is why GC really only comes into its own when it is designed into
a language from day 1.

I agree that is where it is most useful. Obviously it can also be used
with a slightly restricted C (as some people do), but for any given
feature a language designed with that feature will always do it better.