Garbage collection in C

[Gordon Burditt]

Yes , I know that of course. But I was commenting on the fact
I claim that any real implementation of garbage collection for C
(the implementation NEED NOT be portable) has at least one of three
(fatal) problems:

(1) It never frees anything, in which case it can't be called garbage
collection.
(2) It frees stuff when it shouldn't. In particular, it doesn't
deal properly with pointers stored in files (and read back and used
later by the same invocation of the program) or encrypted pointers
stored in files, or encrypted pointers stored in memory.
(3) It uses excessive resources during garbage collection.
(Yes, this is subjective, but I classify reading whole hundred-terabyte
files looking for pointers that aren't there as excessive.)

C already has (1).

(2) is not an issue for at least 99.99% of real programs, but it
does introduce problems doing something that ANSI C says is acceptable.

(3) is likely caused by trying to fix (2).

Why do you insist on being obtuse? Use of GC in a portable C
program is bad, unless the complete GC system is written in
portable C and published as part of that program. Otherwise the
program becomes non-portable.

This is true if a number of things available from third-party
libraries are substituted for GC: say, networking, graphics, database
access, etc.

However, I have grave doubts that it is possible to write a
completely portable GC system.

I have grave doubts that it is possible to write a practical GC
system for C that doesn't have at least one of the problems listed
above. That business about allowing pointers in files makes it
really hard.

My standard for C + GC: take the ANSI C standard, and add a statement
that a program may malloc() memory without freeing it, memory that
no longer has any reference to it anywhere is freed automatically
(eventually), putting off running out of resources. Anything that
doesn't cause Undefined Behavior in plain ANSI C shouldn't cause
it in C + GC.

Perhaps it could require that the program:

#include <stdlib.h>

int main(void) {
char *p;

while (1) {
p = malloc(1);
}
}

shouldn't ever run out of memory.

Remember, this implies making no
assumptions other than those stated in the C standard. For
example, there is no way of scanning all memory in use for any
particular value.

I'm not going to require that the IMPLEMENTATION of GC be written
in portable C (the implementation of fopen() needn't be portable
either). It won't help.

Gordon L. Burditt

 

[ArWeGod]

....
Yes , I know that of course. But I was commenting on the fact that when
somebody proposes a useful feature and all answers he get are "but my files
are not cleaned up automatically" , "it can hide bugs in my algorithms" ,
"it does not work on platform xyz" , "now I can't do free(malloc(10));". Not
one positive answer. So the consensus among C people is that "GC is bad"?

Ok, I'll say it; Garbage Collections is Evil!

The C motto is / was / will always be "Trust the programmer". No safety
nets. No namby-pamby helpful error messages. If you don't know what's wrong
then go back to writing BASIC, you simp!

"Oh, Gosh, I have a memory leak..." NO, you have a bad design! Learn to
program, you idiot!

If you can't clean up your own messes, you are not only not a programmer,
but also not fully human.

(e-mail address removed)

 

[Chris Dollin]

So the consensus among C people is that "GC is bad"?

No. I think GC is *wonderful*; I've been programming in GCy languages
for (pause) more than 30 years.

But GC doesn't fit naturally *into C* [despite Hans's fine work], and
doesn't fit into many of the contexts in which C is used, and *is not
portable* in the CLC sense - you can't assume that your target platform
will have it. If you're willing to accept the implementation constraints
it implies, then fine, but it's not CLC-topical.

If you really want to use GC in your application or design, you might
want to consider whether you want to use C at all; GC enables a whole
bunch of idioms that C just does not support, higher-order functions
to name the most obvious. There's Smalltalk and Lisp and Pop11 and
Prolog and drat-begins-with-E-telecoms-associated, for example, or if
you're desparate, you can use Java.

 

[Arthur J. O'Dwyer]

C is over 30 years old. Are you saying that it was given a garbage
collector in the 80s? Are you talking about C++?

Of course not! and Of course not! respectively.

BTW, K&R1 was published in 1978 according to my sources, and
modern C was not standardized until 1989. The current year is 2003.

-Arthur

 

[Shill]

BTW, K&R1 was published in 1978 according to my sources, and

modern C was not standardized until 1989. The current year is 2003.

C was designed in the early 1970s. The current year is 2003

 

[Keith Thompson]

Standard C allows pointer values to be hidden away anywhere the
programmer likes, erased from memory, and then read back in; as long
as all the bits are retrieved consistently, the pointer is still
valid. A GC subsystem that assumes that only pointers stored in
memory (or registers) are valid, and that anything not pointed to by a
valid pointer may be safely deallocated, will break some valid C
programs. (A GC subsystem that doesn't make such an assumption
probably won't collect much garbage.)

An implementation that implements a language that's ISO C, minus the
guarantee that pointers remain valid when they're not in memory, plus
GC, implements a language that isn't really C. It may be a very
interesting and useful language. It may even look a lot like C200X.
And it will probably support almost all existing valid C code. (Do
you know of any real world programs that erase pointer values from
memory, then later retrieve them and expect them to be valid? I
don't.) But it isn't really C.

Whether such a not-quite-C language is topical for this newsgroup is
left as an exercise for the ongoing flamewar. On the other hand,
discussion of whether it's topical (i.e., of whether a conforming C
implementation may legally provide GC) seems quite topical, even if
the answer happens to be no.

 

[Jussi Ekholm]

There is "magic bullet" of course, I am not trying to sell you
something since my compiler system is free. It is a great tool for PC
applications, where there are no real time and memory constraints.

I apologize if this is a stupid question (although, I recall someone
saying "there is no stupid questions, only stupid people...), but what
is this "magic bullet" you're talking about?

 

[Richard Heathfield]

I apologize if this is a stupid question (although, I recall someone
saying "there is no stupid questions, only stupid people...), but what
is this "magic bullet" you're talking about?

Jacob, I'm sure, meant to write "there is no silver bullet".

In "The Mythical Man-Month" by Fred Brooks, there is a chapter entitled "No
Silver Bullet - Essence and Accident in Software Engineering". The chapter
is subtitled: "There is no single development, in either technology or
management technique, which by itself promises even one order-of-magnitude
improvement within a decade in productivity, in reliability, in
simplicity".

 

[Bjorn Reese]

#define free GC_free [...]
#define free(a) (a=NULL)

What about memory allocated by third-party libraries, which was not
allocated using GC_malloc() and thus must be freed with free()?

I know this problem can be circumvented by putting parantheses around
'free', but errors made by omitting this can be very difficult to see.

I would be more inclined to use GC_malloc/GC_free throughout the
program, and redefine these if no GC is available.

 

[jacob navia]

#define free GC_free [...]
#define free(a) (a=NULL)

What about memory allocated by third-party libraries, which was not
allocated using GC_malloc() and thus must be freed with free()?

Memory not allocated by the collector will not be touched of course.
External libraries work without any problems!

 

[jacob navia]

Jacob, I'm sure, meant to write "there is no silver bullet".

Exactly. Thanks for the correction

 

[Mark Gordon]

#define free GC_free [...]
#define free(a) (a=NULL)

What about memory allocated by third-party libraries, which was not
allocated using GC_malloc() and thus must be freed with free()?

Memory not allocated by the collector will not be touched of course.
External libraries work without any problems!

The point was that if the external library passes you a pointer that you
are expected to free, then after your redefinition of free the following
code fragment gives a memory leak

{
char *derf;
derf = foo(); /* foo is in library and returns pointer from malloc */
/* do some stuff */
free(derf);
}

I would also point out that if you don't have to free some dynamically
allocated memory but other pieces of dynamically allocated memory do
need freeing you (or at least I) am more likely to make a mistake and
either use the standard free on a pointer that should be left for the GC
or not call it on a pointer to memory provided (though a library) by
malloc.

 

[jacob navia]

The point was that if the external library passes you a pointer that you
are expected to free, then after your redefinition of free the following
code fragment gives a memory leak

{
char *derf;
derf = foo(); /* foo is in library and returns pointer from malloc */
/* do some stuff */
free(derf);
}

I would also point out that if you don't have to free some dynamically
allocated memory but other pieces of dynamically allocated memory do
need freeing you (or at least I) am more likely to make a mistake and
either use the standard free on a pointer that should be left for the GC
or not call it on a pointer to memory provided (though a library) by
malloc.

Yes, this could be a problem. Fortunately libraries that pass allocated
memory expecting you to free it are very rare. This is because they can
only work with one compiler system. The "malloc" implementations are
not compatible: you can't free with gcc's free() a piece of memory allocated
with MSVC, for instance.

That's why this example is not very real. Most libraries are designed to
work with many compiler systems and do not rely on the user freeing memory.
Usually they give an interface where you call some API to free the
allocated memory.

jacob

 

[Mark McIntyre]

In "The Mythical Man-Month" by Fred Brooks, there is a chapter entitled "No
Silver Bullet - Essence and Accident in Software Engineering". The chapter
is subtitled: "There is no single development, in either technology or
management technique, which by itself promises even one order-of-magnitude
improvement within a decade in productivity, in reliability, in
simplicity".

Like all generalisations, this one is wrong. Counterexamples:

Clean water in london wiped out cholera inside a few year
pennicilin stopped a wide range of deaths
consumer GPS in the 1990s reliably position you to within feet
and what about HTTP?

I guess you could argue that none of these is a "single development".
Hmm, in that case, nothing ever is.

 

[Arthur J. O'Dwyer]

Simple answer: GC_free(x) can look to see if it allocated x. If it
did, it marks it for cleanup. If it didn't, it can pass x on to the
implementation's 'free' function (and kind of assume the user must
know what he's doing). Not a silver bullet, but avoids memory leaks.

Yes, this could be a problem. Fortunately libraries that pass allocated
memory expecting you to free it are very rare. This is because they can
only work with one compiler system. The "malloc" implementations are
not compatible: you can't free with gcc's free() a piece of memory allocated
with MSVC, for instance.

Well, *if* the library is compiled with the same object file format as
the compiler's generated code, then the library function (say Strdup())
doesn't actually contain any memory management code. It just contains
a call to '_malloc' or '@_MALLOC' or whatever, and when the linker
does its magic, the '_malloc' in the library code and the '_free' in
the user code match up and everyone's happy.

Of course, last I checked you couldn't use MSVC library files with GCC
object files, so all bets are off. But it's a file format problem,
not a library problem.

That's why this example is not very real. Most libraries are designed to
work with many compiler systems and do not rely on the user freeing memory.
Usually they give an interface where you call some API to free the
allocated memory.

Strdup.

Also, I'm in the middle [or end, depending on motivation] of writing
an image-format library that has lots of functions like

int ReadPPM(const char *fname, unsigned char *(*data)[3], int *w, int *h);

for which the user is expected to call 'free' on the data pointer
when necessary:

unsigned char (*data)[3];
int w, h;
int rc = ReadPPM("input.ppm", &data, &w, &h);
if (rc < 0)
return EXIT_FAILURE;
else {
process(data, w, h);
free(data);
return 0;
}

Obviously the answer to this particular case is, "Don't use GC for
your image-format library's applications," and that's perfectly
reasonable. Just pointing out that there probably are a lot of
libraries in C for which GC would eventually be a problem.

-Arthur

 

[Zeljko Vrba]

Yes, this could be a problem. Fortunately libraries that pass allocated
memory expecting you to free it are very rare. This is because they can
only work with one compiler system. The "malloc" implementations are
not compatible: you can't free with gcc's free() a piece of memory allocated
with MSVC, for instance.

Wrong. Shared and static libraries will contain only reference to malloc
and free calls. They will be resolved only when the final program is
linked (or, in case of dynamic linking, when it is run). At that point
a single implementation of malloc will be used an all is well. As long as
MS linker can read gcc's object files (and vice-versa), there is no problem in
mixing different compilers at all.