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
15  2363 
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/
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
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
"vk02720" <vk*****@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 valid 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.
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.
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/>
On Mon, 23 Jan 2006 01:25:14 +0100,
Pascal Bourguignon <sp**@mouse-potato.com> wrote: "vk02720" <vk*****@my-deja.com> writes: I am trying to implement garbage collection for C/C++ mainly for
learning purpose. I dont know where to start.
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 in 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.
Giorgos Keramidas <ke******@ceid.upatras.gr> writes: On Mon, 23 Jan 2006 01:25:14 +0100,
Pascal Bourguignon <sp**@mouse-potato.com> wrote: "vk02720" <vk*****@my-deja.com> writes: I am trying to implement garbage collection for C/C++ mainly for
learning purpose. I dont know where to start.
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 in C.
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); return(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.
On Mon, 23 Jan 2006 04:23:36 +0100, Pascal Bourguignon <sp**@mouse-potato.com> wrote: Giorgos Keramidas <ke******@ceid.upatras.gr> writes: On Mon, 23 Jan 2006 01:25:14 +0100,
Pascal Bourguignon <sp**@mouse-potato.com> wrote: "vk02720" <vk*****@my-deja.com> writes:
I am trying to implement garbage collection for C/C++ mainly for
learning purpose. I dont know where to start.
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 in C.
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); return(0);}
Effectively, this ends up allocating at compile time a storage area of
100 (char) values, and then using only sizeof(void *) bytes of that
storage. Using the allocated memory would require again the same
trickery, to obtain the pointer value.
There's probably no way to 'free' the rest of the original `storage'
bytes, unless one knows already too much about the underlying platform
and the way automatic variables are organized on the stack :-(
Giorgos Keramidas <ke******@ceid.upatras.gr> writes: On Mon, 23 Jan 2006 04:23:36 +0100, Pascal Bourguignon <sp**@mouse-potato.com> wrote: Giorgos Keramidas <ke******@ceid.upatras.gr> writes: On Mon, 23 Jan 2006 01:25:14 +0100,
Pascal Bourguignon <sp**@mouse-potato.com> wrote:
"vk02720" <vk*****@my-deja.com> writes:
> I am trying to implement garbage collection for C/C++ mainly for
> learning purpose. I dont know where to start.
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 in C.
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); return(0);}
Effectively, this ends up allocating at compile time a storage area of
100 (char) values, and then using only sizeof(void *) bytes of that
storage. Using the allocated memory would require again the same
trickery, to obtain the pointer value.
There's probably no way to 'free' the rest of the original `storage'
bytes, unless one knows already too much about the underlying platform
and the way automatic variables are organized on the stack :-(
My point was that here we have a variable that is declared to hold
only characters, but it actually holds a pointer to some memory block
allocated on the heap. The storage memory is on the stack, as an
automatic variable, so it belongs to the root set (as long as its
function is active, which in the case of main is always). But the
memory allocated on the heap could be subject to garbage collecting.
Now there is no conceptual difference between these two programs (and
possibly no difference at all):
int main(void){ char storage[100];
(*(void**)storage)=malloc(4);
/* here */
return(0);}
int main(void){ char storage[100];
malloc(4); /* could be garbage collected right now */
storage[0]=0x04;
storage[1]=0x12;
storage[2]=0x04;
storage[3]=0x10;
/* here */
return(0);}
At the points marked here, in both case, storage may contain the
pointers to the heap, and the correspond heap memory blocks cannot be
garbage collected.
Since the garbage collector cannot distinguish these cases, it must be
"conservative", and mark the memory blocks corresponding to the
"pointers" any storage contains.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we. -- Georges W. Bush
Pascal Bourguignon wrote: "vk02720" <vk*****@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.
That is exactly what I am trying to find out. Where does the compiler (
or kernel after it loads the program in memory ) store these variables.
How do I get a list of all variables in my program ?
Assume this simple program on Linux. To start, how do I get hold of the
data and stack regions and look into these regions and print the values
assigned to these variables ?
#include <stdio.h>
#include <stdlib.h>
void *ptrglobal;
main()
{
void *ptrlocal = malloc(10);
ptrglobal = malloc(20);
// dump_my_program_vars();
ptrlocal = NULL;
// collect_garbage();
}
- or you don't know them. Then you cannot know them because stuff like:
{ char storage[100]; ((void*)storage)=malloc(4); } is perfectly valid 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.
How do I access stack and global memory from within the program ?
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.
"vk02720" <vk*****@my-deja.com> writes: Pascal Bourguignon wrote: "vk02720" <vk*****@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.
^^^^^^^^^
That is exactly what I am trying to find out. Where does the compiler (
or kernel after it loads the program in memory ) store these variables.
How do I get a list of all variables in my program ?
It's useless to seek this metadata in C!
See my example with { char storage[100];... }
If you want to take the knowledge about the variables from the source
code, you must change the language. Leave C and come to a higher level
programming language. Modula-3, Eiffel, Haskell, Lisp, anything but C
or C++. - or you don't know them. Then you cannot know them because stuff like:
{ char storage[100]; ((void*)storage)=malloc(4); } is perfectly valid 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.
How do I access stack and global memory from within the program ?
I don't know. But if you looked at the sources of BoehmGC which has
already been mentionned, you'd find out...
--
__Pascal Bourguignon__ http://www.informatimago.com/
CONSUMER NOTICE: Because of the "uncertainty principle," it is
impossible for the consumer to simultaneously know both the precise
location and velocity of this product.
>> - 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.
That is exactly what I am trying to find out. Where does the compiler (
or kernel after it loads the program in memory ) store these variables.
How do I get a list of all variables in my program ?
It is quite probable that you can't, unless the compiler cooperates.
And even then, it won't know about how memory allocated by malloc()
is being used. (In particular, a routine that allocates a block
of memory may not have any idea that its caller several levels up
is casting the pointer to a structure pointer for a linked list node,
then using it as one.)
Assume this simple program on Linux. To start, how do I get hold of the
data and stack regions and look into these regions and print the values
assigned to these variables ?
Compile with debugging information turned on, and learn how to
interpret the debugging information. This is extremely system-specific.
Or write a compiler that puts out debugging information in a format
you know.
#include <stdio.h>
#include <stdlib.h>
void *ptrglobal;
main()
{
void *ptrlocal = malloc(10);
ptrglobal = malloc(20);
// dump_my_program_vars();
ptrlocal = NULL;
// collect_garbage();
}
- or you don't know them. Then you cannot know them because stuff like:
{ char storage[100]; ((void*)storage)=malloc(4); } is perfectly valid 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.
How do I access stack and global memory from within the program ?
Load a pointer with a value and dereference it.
A pointer into somewhere in the so-called "stack" can be obtained by
taking the address of an auto variable.
A pointer into somewhere in the global memory area can be obtained
by taking the address of a global variable. Sometimes symbols
like _edata delimit the boundaries of memory sections. > 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.
Your own API for malloc/free would need to include something about
what the memory will be used for (will it contain pointers, and
where?). How you do this, I'm not sure.
Gordon L. Burditt
vk02720 wrote: Pascal Bourguignon wrote: "vk02720" <vk*****@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.
That is exactly what I am trying to find out. Where does the compiler (
or kernel after it loads the program in memory ) store these variables.
How do I get a list of all variables in my program ?
Assume this simple program on Linux. To start, how do I get hold of the
data and stack regions and look into these regions and print the values
assigned to these variables ?
<snip>
All this is highly implementation specific. I doubt it is the same on
all Posix systems, let alone all systems of all varieties. So you will
probably have ask in a Linux group. The same applies to the rest of your
questions. Continuing this is certainly off topic for both comp.lang.c
and comp.lang.c++, I'm less certain about comp.unix.programmer so I've
set follow ups there.
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: JC |
last post by:
How does garbage collection work in C# and VB.NET for data returned from COM
object? For example, a COM object written in C++ returns a SAFEARRAY to C#
or VB.NET, will this SAFEARRAY (mapped to...
|
by: Ă–mer KUL |
last post by:
hi,
i have a garbage collection problem. i have an application writen by
vb.net, i am opening a form and in this form there is a big query. when i
open the form, it takes 80 mb memory because of...
|
by: joe |
last post by:
I have a simple .NET application with two or three listViews which are
filled with icons and when the user click on the proper item, they display
the related images. I use "image = null ; " for all...
|
by: Chris |
last post by:
Hi,
I think I'm having some problems here with garbage collection. Currently, I
have the following code:
public struct Event
{
public int timestamp;
|
by: [Yosi] |
last post by:
How can I make sure that a spicific function location in memory will not
moved , by OS/Garbage collection ?????
The problem is : I'm using a DLL this dll have an call backerror function,
in my...
| | |
by: vk02720 |
last post by:
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...
|
by: R. MacDonald |
last post by:
Hello, all,
I am currently working on a .Net (VB) application that invokes routines
in unmanaged (Fortran) DLLs. The unmanaged routines then communicate
with the .Net application by means of a...
|
by: roger.dunham |
last post by:
I am trying to identify whether a .NET 1.1 application that I have
written has a memory leak. I thought I understood how .NET memory
management worked, but it appears that there is more to it...
|
by: Carl Banks |
last post by:
On Apr 12, 7:02 am, andreas.eis...@gmail.com wrote:
Well, the garbage collector activates whenever allocations exceed
deallocations by a certain amount, which for obvious reasons is the
reason...
|
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...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The...
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated ...
| | |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence...
| |
