Hi,

I am trying to implement garbage collection for C/C++ mainly for
learning purpose. I dont know where to start.

For example -
Basic questions - How do I identify the variables that contain pointers
? Where do I look for these variables and how to tell if what is
assigned to them is a pointer ?

Do I need to implement my own API for malloc/free ( or new/delete ) or
can I create a library that can be linked with the given source code
that uses the standard malloc ? Are there any tradeoffs for either
approach ?

Appreciate any pointers to any info on the web or text books etc.

TIA

[ Post a follow-up to this message ]

vk02720 wrote:
> Hi,
>
> I am trying to implement garbage collection for C/C++ mainly for
> learning purpose. I dont know where to start.
>
> For example -
> Basic questions - How do I identify the variables that contain pointers
> ? Where do I look for these variables and how to tell if what is
> assigned to them is a pointer ?
>
> Do I need to implement my own API for malloc/free ( or new/delete ) or
> can I create a library that can be linked with the given source code
> that uses the standard malloc ? Are there any tradeoffs for either
> approach ?
>
> Appreciate any pointers to any info on the web or text books etc.
>
> TIA
>

You definitely need to be aware of this:

http://www.hpl.hp.com/personal/Hans_Boehm/gc/

[ Post a follow-up to this message ]

vk02720 wrote:
> I am trying to implement garbage collection for C/C++ mainly for
> learning purpose. I dont know where to start.

Not to discourage you, but that's a plenty ambitious project.  I humbly
suggest that if you have no idea where to start, your probably biting
off significantly more than you have a reasonable chance of being able
to chew.

> For example -
> Basic questions - How do I identify the variables that contain pointers
> ? Where do I look for these variables and how to tell if what is
> assigned to them is a pointer ?
>
> Do I need to implement my own API for malloc/free ( or new/delete ) or
> can I create a library that can be linked with the given source code
> that uses the standard malloc ? Are there any tradeoffs for either
> approach ?

Garbage collection cannot simply be glued on to the standard memory
model.  There's nothing about the contents of the memory which tells
you who's referencing it.  A tool such as a profiler can do some
analysis of this sort, but with an overhead that would be unacceptable
outside of performance testing.

So, the place to start is to understand how the standard memory model
works, in excruciating detail, because what you're talking about is
stripping the whole thing out and replacing it.  Still sound like a fun
project?  (Okay, I'll confess, it sounds very fun, but I still think
you sound like you don't know what you're in for).

> Appreciate any pointers to any info on the web or text books etc.

Andrei Alexandrescu's "Modern C++ Design" has a chapter on writing a
custom allocator.  I saw him give a talk recently, though, and he now
disfavors the approach therein in favor of a policy-based design.  It's
still instructive, of course.  However, the first place I'd start is by
reading all of the relevant material in TC++PL (3rd or Special Ed.) by
Stroustrup.

Luke

[ Post a follow-up to this message ]

vk02720 wrote:
> Hi,
>
> I am trying to implement garbage collection for C/C++ mainly for
> learning purpose. I dont know where to start.
>
> For example -
> Basic questions - How do I identify the variables that contain pointers
> ? Where do I look for these variables and how to tell if what is
> assigned to them is a pointer ?

What you can do is, provide functions so that the class implementer can
register the pointers to members. Provide also a virtual base class to
register the object itself.

>
> Do I need to implement my own API for malloc/free ( or new/delete ) or
> can I create a library that can be linked with the given source code
> that uses the standard malloc ? Are there any tradeoffs for either
> approach ?

You can but I doubt you have to...if you are doing heap compacting then yes.

>
> Appreciate any pointers to any info on the web or text books etc.
>
> TIA
>

Ben

[ Post a follow-up to this message ]

"vk02720" <vk02720@my-deja.com> writes:

> Hi,
>
> I am trying to implement garbage collection for C/C++ mainly for
> learning purpose. I dont know where to start.
>
> For example -
> Basic questions - How do I identify the variables that contain pointers
> ? Where do I look for these variables and how to tell if what is
> assigned to them is a pointer ?

You have basically two ways:

- either you know them, that is, you are the compiler and you know
where you store the pointers, then you can output this information
in the object files.  This is what is done with higher level
languages.

- or you don't know them.  Then you cannot know them because stuff like:
{ char storage[100]; ((void*)storage)=malloc(4); } is perfectly val
id in C.
So the only think you can do, is to be "conservative" (see Boehm GC),
that is, you scan all the allocated  memory, and if you see a bit
pattern that looks like a pointer, then you assume it's a pointer.

What looks like a pointer?  Any bitfield that points to a zone where
there is some memory allocated.


To find the variables you must identify the root set: all the
potential pointer in the stack and the global memory.


> Do I need to implement my own API for malloc/free ( or new/delete ) or
> can I create a library that can be linked with the given source code
> that uses the standard malloc ? Are there any tradeoffs for either
> approach ?

Well, at a minimum, you'd have to replace free by a version that does
nothing, and malloc by a version that calls the garbage collector from
time to time.


--
__Pascal Bourguignon__                     http://www.informatimago.com/

This universe shipped by weight, not volume.  Some expansion may have
occurred during shipment.

[ Post a follow-up to this message ]

vk02720 wrote:
> For example -
> Basic questions - How do I identify the variables that contain pointers
> ? Where do I look for these variables and how to tell if what is
> assigned to them is a pointer ?

In theory this is very hard because the internals of the implementation
are hidden. The language people may say: new and malloc allocate on the
heap, but the heap can have different meanings, depending on what data
structures your compiler uses to accomplish the functionality.

If you know what your implementation does for memory
allocation/deallocation (e.g. if you know everything about gcc
compiler) you can make such an attempt. If you just wanna change the
world, try writing a garbage collector for
http://fabrice.bellard.free.fr/otcc/ or
http://fabrice.bellard.free.fr/tcc/ to start with and it will hopefully
give you pointer to work with gcc.

[ Post a follow-up to this message ]

"vk02720" <vk02720@my-deja.com> wrote in message
news:1137971702.828975.313560@o13g2000cwo.googlegroups.com...
> I am trying to implement garbage collection for C/C++ mainly for
> learning purpose. I dont know where to start.

http://www.amazon.com/gp/product/04...glance&n=283155

Walter Bright
www.digitalmars.com C, C++, D programming language compilers

[ Post a follow-up to this message ]

vk02720 wrote:
>
> I am trying to implement garbage collection for C/C++ mainly for
> learning purpose. I dont know where to start.

You have already made some fatal mistakes.  There is no language
C/C++.  There is C, and there is C++.  Make up your mind.  Do not
cross post between the two languages, because they are different
and have different rules and standards.

Never post with cross-posting without setting followups to the
single appropriate newsgroup.

Always post your efforts.

F'ups set.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article.  Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>

[ Post a follow-up to this message ]

On Mon, 23 Jan 2006 01:25:14 +0100,
Pascal Bourguignon <spam@mouse-potato.com> wrote:
> "vk02720" <vk02720@my-deja.com> writes: 
>
> You have basically two ways:
>
> - either you know them, that is, you are the compiler and you know
>   where you store the pointers, then you can output this information
>   in the object files.  This is what is done with higher level
>   languages.
>
> - or you don't know them.  Then you cannot know them because stuff like:
>   { char storage[100]; ((void*)storage)=malloc(4); } is perfectly valid i
n C.

Not really, because storage is not an `lvalue', but garbage collection
in cases like this (when "you don't know all the details about all the
variables") is pretty hard.  For instance, it cannot help in bugs like
the following:

void function (void)
{
char storage[4];
memset(storage, 0, 100);
}

But this is not really garbage collection related, I guess.

[ Post a follow-up to this message ]

Giorgos Keramidas <keramida@ceid.upatras.gr> writes:

> On Mon, 23 Jan 2006 01:25:14 +0100,
> Pascal Bourguignon <spam@mouse-potato.com> wrote: 
>
> Not really, because storage is not an `lvalue',

Indeed.  I remember having done this kind of thing, but perhaps it has
always been with pointers instead of automatically allocated memory.
Anyways, you can just add a pair of stars to trick the compiler:

% cat m.c ; gcc -S -c -o m.s m.c ; cat m.s
#include <stdlib.h>
int main(void){ char storage[100]; (*(void**)storage)=malloc(4); re
turn(0);}

.file	"m.c"
.text
.globl main
.type	main, @function
main:
pushl	%ebp
movl	%esp, %ebp
subl	$120, %esp             ; allocates char storage[100]
andl	$-16, %esp
movl	$0, %eax
subl	%eax, %esp
subl	$12, %esp
pushl	$4
call	malloc
addl	$16, %esp
movl	%eax, -120(%ebp)       ; store the result of malloc to the
; first four bytes of storage.
movl	$0, %eax
leave
ret
.size	main, .-main
.ident	"GCC: (GNU) 3.3 20030226 (prerelease) (SuSE Linux)"


--
__Pascal Bourguignon__                     http://www.informatimago.com/

PLEASE NOTE: Some quantum physics theories suggest that when the
consumer is not directly observing this product, it may cease to
exist or will exist only in a vague and undetermined state.

[ Post a follow-up to this message ]