Garbage Collection in C

[Kenny McCormack]

heathfield FORBID ME EXPLICIRELY to call him by his first
name. Before I called him "richard" but HE told me not to do so.

Then I suppose calling him [a] Dick would be right out, as well.

 

[CBFalconer]

[garbage collection]

I'd suggest use of resource pools as a viable alternative to
garbage collection that can actually be implemented in standard
C. Resource pools are not perfect, but when used in a
disciplined way they can make some kinds of programming much
simpler.

Here's a discussion of what I mean:
http://freetype.sourceforge.net/david/reliable-c.html

That looks interesting, but I see no obvious way to submit
corrections. For example (after partial reading), he recommends:

int do_something( .... )
{
int error;
char *block1, *block2, *block3;

error = ERR_OK;
block1 = NULL;
block2 = NULL;
block3 = NULL;

block1 = (char*) malloc( 1024 );
if ( block1 == NULL ) goto Fail;

block2 = (char*) malloc( 1024 );
if ( block2 == NULL ) goto Fail;

block3 = (char*) malloc( 1024 );
if ( block3 == NULL ) goto Fail;

.... // do something

Exit:
if (block3) free( block3 );
if (block2) free( block2 );
if (block1) free( block1 );

return error;

Fail:
error = ERR_MALLOC;
goto Exit;
}

which would be better (and more accurately IMO) written as:

int do_something( .... )
{
int error;
char *block1, *block2, *block3;

error = ERR_OK;
block1 = malloc( 1024 );
block2 = malloc( 1024 );
block3 = malloc( 1024 );
if (!block1 || !block2 || !block3) error = ERR_MALLOC
else {
.... /* do something */
}
free( block3 );
free( block2 );
free( block1 );
return error;
}

Use of the ERR_MALLOC and ERR_OK identifiers are also suspect.

Later: Found an email address in the paper, and I have sent a copy
of this article to him.

--
Some informative links:
< <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>
<http://cfaj.freeshell.org/google/>

 

[William Hughes]

William Hughes wrote:

jacob navia wrote:

[...]

This is of no practical significance. Pointers aren't XORed in normal
programs, and if you stay within the normal alignment requirements
of the processor, everything works without any problems.


No, but I might well subtract 1 from my pointers to change the
indexing.


This is allowed of course. Your pointer will be within the bounds
of the pointed-to object and that object will NOT be reclaimed since
there is (at least) one pointer to somewhere in it.

You missed William's point entirely.

p = malloc(N * sizeof *p) -1; /* I now have an array indexed by 1 */

Non-standard, but people do it. It means that the pointer is no longer
no longer points in to the object, so the GC will free it.

Well, this is NON-STANDARD. As far as C is concerned, a subtracting
one from the start of an object is undefined behavior.

So. Are you claiming that GC will work on any conforming program?

In any case, by casting from a pointer to an integer, subtracting
the size of an array element, and casting back to a pointer, I get
implementation defined behaviour, which will probably be the
behaviour I want.

If you do things like that yes, you should not use the GC.

And this is my point. If you do things like that you shouldn't use
GC. It took me 30 seconds to come up with that example. This
does not give me a warm fuzzy about GC.

You can
however have the same effect by

p = malloc((1+N) * sizeof *p) ; /* I now have an array indexed by 1 */

You never use the zeroth member and you keep out of undefined behavior.

The fact that you can do things that don't break GC is not the
point. The fact that you can do things that do break GC and that
these things are not that unlikely , is.

Exvuse me but that is likely to be done by the OS, not by a third party
library.

So? The program may have a better idea of what is going
to be needed next than the OS. In that case the program may well
implement its own "swapping" mechanism. This is certainly not
likely, but it is not that rare either.

Maybe, I can't guarantee all third party libraries in the world. As far
as I know, and from the experience of people using the GC, that never
happens.

I have used a lot of NR code. Good thing I never used
GC.

- William Hughes

 

[jacob navia]

So. Are you claiming that GC will work on any conforming program?

In any case, by casting from a pointer to an integer, subtracting
the size of an array element, and casting back to a pointer, I get
implementation defined behaviour, which will probably be the
behaviour I want.





And this is my point. If you do things like that you shouldn't use
GC. It took me 30 seconds to come up with that example. This
does not give me a warm fuzzy about GC.

As I said, that is undefined behavior in C.
It happens to work in YOUR implementation, it will not work in a
segmented implementation where pointer arithmetic is not defined
at a segment boundaries, for example any 286 compatible processor.

The fact that you can do things that don't break GC is not the
point. The fact that you can do things that do break GC and that
these things are not that unlikely , is.

Well, if you do things that are not allowed by the standard
you are in your own.

So? The program may have a better idea of what is going
to be needed next than the OS. In that case the program may well
implement its own "swapping" mechanism. This is certainly not
likely, but it is not that rare either.

It is funny the contortions people will invent to find something that
is against a GC.

We both agree that "this is certainly not likely".

I have used a lot of NR code. Good thing I never used
GC.

NR code invokes undefined behavior if it subtracts one from
the beginning of the array. I repeat. That works in some
implementations, in some others it will break.

 

[Frederick Gotham]

William Hughes posted:

So. Are you claiming that GC will work on any conforming program?

It's simple to write a fully-portable GC.

 

[William Hughes]

As I said, that is undefined behavior in C.
It happens to work in YOUR implementation, it will not work in a
segmented implementation where pointer arithmetic is not defined
at a segment boundaries, for example any 286 compatible processor.

By strange coincidence I do happen to use my
implementation.

Well, if you do things that are not allowed by the standard
you are in your own.

And if you only do things that are allowed by the standard you
are still on your own.

It is funny the contortions people will invent to find something that
is against a GC.

We both agree that "this is certainly not likely".

Contortions? I have done something very similar.
Thre question is not "Is this likely?", but
"Is this rare enough to be ignored?" My opinion is no.

NR code invokes undefined behavior if it subtracts one from
the beginning of the array. I repeat. That works in some
implementations, in some others it will break.

How do you know. Suppose my NR libraries are
written in Fortran? (Guess which book came first.)

- William Hughes

 

[Al Balmer]

I think this particular carp is unfair. Jacob has been
fundamentally advertising the available of the Boehm library for
GC, which I presume is written in standard C, or nearly so.

That doesn't make it topical. He's discussing the product, not the
code. As we keep reminding people here, the fact that a program is
written in C doesn't make discussion of the program itself topical.

 

[William Hughes]

William Hughes posted:



It's simple to write a fully-portable GC.

Which wasn't the question.
It doesn't matter if the GC is written in a combination of
assembler and Lithp ( a programming language that the Igors
use to process lithtths). The question is whether it will
work on any conforming program.
This includes a program that allocates some memory,
xor's a pointer twice with the same string, and
then uses the memory.

- William Hughes

 

[Walter Roberson]

The question is whether it will
work on any conforming program.
This includes a program that allocates some memory,
xor's a pointer twice with the same string, and
then uses the memory.

In order to xor a pointer with anything, you would need to
convert the pointer into an integral value, then convert the
integral value to a pointer and have the resulting pointer compare
equal to the original pointer.

C89 and C99 allow implementations to define casting pointers to and
from integral values, but does not define the meaning of that
conversion. C99 promises that the conversion is reversable, but C89
does not (but K&R2 does.)

There is a reversable pointer operation in C89:
printing out and scanning in a pointer with %p format.
I would, though, need to recheck the wording to see whether
implementations are allowed to do nothing useful with %p, and I would
need to recheck to see if there are any constraints on the lifetime
of the reconversion (and do the same checks in C99).

This suggests a variant scheme to yours that has more certainty of
portability: take a pointer, sprintf("%p") it to a string,
reversably munge the string and set the pointer to NULL. Invoke
or hypothesize a GC at that point. Now unmunge the string and sscanf("%p")
it back into the pointer. If this is done within the same function,
then surely any potential lifetime constraints on the %p reversability
would be met, so the doubly converted pointer would be valid -- but
any GC scheme that invokes mark/sweep operations would consider
the area unreachable and might release it.

 

[Frederick Gotham]

William Hughes posted:

Which wasn't the question.
It doesn't matter if the GC is written in a combination of
assembler and Lithp ( a programming language that the Igors
use to process lithtths). The question is whether it will
work on any conforming program.
This includes a program that allocates some memory,
xor's a pointer twice with the same string, and
then uses the memory.

Why do think it might not work? I don't see any barriers.

Even something as primitive as the following should work, although "gc.h"
would have to be included _after_ all Standard headers.

/* FILE BEGIN: gc.h */

#include <stddef.h>

void *mallocGC(size_t const len);

#undef malloc
#undef free

#define malloc mallocGC
#define free ((void)0)

/* FILE END: gc.h */

/* FILE BEGIN: gc.c */

#include <stddef.h>
#include <stdlib.h>

typedef struct AllocLink {
void *p;
struct AllocLink *p_prev;
} AllocLink;

static AllocLink first_link = {0,0};
static AllocLink *plink = &first_link;

void *mallocGC(size_t const len)
{
static void CleanupGC(void);

static int first_time = 1;
AllocLink *const p_new_link = malloc(sizeof *p_new_link);

if (!p_new_link) return 0;

p_new_link->p = malloc(len);

if(!p_new_link->p) { free(p_new_link); return 0; }

p_new_link->p_prev = plink;

plink = p_new_link;

if(first_time) first_time = 0, atexit(CleanupGC);

return plink->p;
}

static void CleanupGC(void)
{
AllocLink *p_prev;

do
{
free(plink->p);
p_prev = plink->p_prev;
free(plink);
plink = p_prev;
} while(plink->p);
}

/* FILE END: gc.c */

 

[Richard Tobin]

Even something as primitive as the following should work

As I think you must know, that's not garbage collection in the sense
being discussed.

-- Richard

 

[Frederick Gotham]

Richard Tobin posted:

As I think you must know, that's not garbage collection in the sense
being discussed.

I haven't been following the discussion much (as I've no use for garbage
collection), nor have I read up on the topic... so I just presumed it had
something to do with automatic-freeing of allocated memory.

 

[William Hughes]

William Hughes posted:


Why do think it might not work? I don't see any barriers.

Because either the garbage collector would free the memory
after the first xor, in which case it breaks the program,
or the garbage collector would not free the memory after
the first xor in which case either the GC is not a garbage
collector in any useful sense of the term, or the GC is
so smart that I will let it write the program.

- William Hughes

 

[Christopher Benson-Manica]

jacob navia wrote:

[inflammatory off-topic crap]

Ok, that's finally enough for a plonk.

I will join you, only because the skirmishes he tends to instigate are
quite tiresome to wade through. Richard is too valuable of a poster
to plonk, so I will settle for reading the better half of the ongoing
Hatfield/McCoy battles.

 

[Flash Gordon]

In order to xor a pointer with anything, you would need to
convert the pointer into an integral value, then convert the
integral value to a pointer and have the resulting pointer compare
equal to the original pointer.

C89 and C99 allow implementations to define casting pointers to and
from integral values, but does not define the meaning of that
conversion. C99 promises that the conversion is reversable, but C89
does not (but K&R2 does.)

No, you do not have to do that. You can treat it as an unsigned char
array and do it that way.

 

[Bart]

Why should the destructors be touched? They just
do not call free() (delete in C++) and that is it.

<OT>
Code that relies on objects being destroyed at a specific point is very
common in C++ (e.g. the standard C++ library). GCs don't guarantee
*when* objects are deallocated, only that they do eventually get
deallocated. BTW, that's the reason Java has a 'finally' clause instead
of destructors.
</OT>

Regards,
Bart.

 

[CBFalconer]

That doesn't make it topical. He's discussing the product, not the
code. As we keep reminding people here, the fact that a program is
written in C doesn't make discussion of the program itself topical.

I looked back at the original post. He doesn't mention his product
(lcc-win32) once in the article. I think he made an effort to
comply with topicality here, while still recommending the use of
such a library, and think that this is fair. The fact is that his
previous off-topic insistence have colored the reaction to anything
he posts, and I think we should lean over backwards to accept
topical (or even nearly topical) posts from him.

We can, and should, criticize the actual portability of the
library. I have not looked at the code involved, so cannot really
comment on that aspect.

As I have posted elsethread (or is it elsegroup?) I feel free to
advertise the availability of my nmalloc system [1], which is not
completely portable, but does list the requirements of the
underlying system. No malloc system can be totally portable, and
thus no GC system can be either. This does not make such systems
uninteresting. As a fairly well known USAnian once said: "you
gotta know your limitations".

As a further example I often include the following code in my
applications, enabling automatic help when run with no parameters:

/* This is very likely to be non-portable
DOES NOT check fp open for reading
NULL fp is considered a keyboard here!
With "gcc -W -Wall -ansi -pedantic" we can expect
implicit declaration warnings for isatty and fileno.
However the result should link correctly.
If it always returns 0 the system still works
but will not give the automatic help.
*/
static int akeyboard(FILE *fp)
{
#ifndef __TURBOC__ /* TC2 is peculiar */
# ifdef __STDC__
/* This dirty operation allows gcc -ansi -pedantic */
extern int fileno(FILE *fp);
extern int isatty(int fn);
# endif
#endif
return ((fp != NULL) && isatty(fileno(fp)));
} /* akeyboard */

This returns false if stdin has been redirected, on most systems.
It is easily replaced at the cost of the automatic help feature. I
don't feel shy about using it in otherwise portable programs. It
also makes the automatic assumption that the default connection for
stdin is a keyboard.

[1] Aside to Jacob: You are perfectly free to incorporate nmalloc
in the lcc-win32 library if you wish. It also provides a fairly
well tested user debugging mechanism, and a way to extract the
essential parameters of the malloc system in a standard conforming
manner. This provides all the hooks needed (IMO) to implement GC
on the systems of interest to you. It should be possible to
dynamically switch such a GC system on and off with it.

--
Some informative links:
< <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>
<http://cfaj.freeshell.org/google/>

 

[Keith Thompson]

In order to xor a pointer with anything, you would need to
convert the pointer into an integral value, then convert the
integral value to a pointer and have the resulting pointer compare
equal to the original pointer.

[...]

You can extract the representation of the pointer by aliasing or
memcpy()ing it to an appropriately sized array of unsigned char.

 

[jacob navia]

<OT>
Code that relies on objects being destroyed at a specific point is very
common in C++ (e.g. the standard C++ library). GCs don't guarantee
*when* objects are deallocated, only that they do eventually get
deallocated. BTW, that's the reason Java has a 'finally' clause instead
of destructors.
</OT>

Regards,
Bart.

You misunderstand. The object *IS* destroyed. Only its storage is
not reclaimed. The destructor is called as the C++ rules want. It just
doesn't call delete.

 

[Bart]

You misunderstand. The object *IS* destroyed. Only its storage is
not reclaimed. The destructor is called as the C++ rules want. It just
doesn't call delete.

So how is the object destroyed? I have to actually put a delete
statement in my program. Talk about garbage collection. Way to go!

Regards,
Bart.