Dynamic Memory Allocation

[Nehil]

can i find about following 2 things, by providing my own API of
functions for a C program :

1) static, global and const section of variables (pointers only), and
to pickout only those which are dynamically allocated.

2) Local variable which are pointers and have dynamically allocated
memory.

Actually, i want to develop an API, which will help in collection
garbage in C program. i.e. programmer will not explicitely call free()
function. The algorithm choosen is : Mark & Sweep.
if somehow i get the info about above mentioned points, the path
further will be easier for me.

I'm concentrating on pointer variables only, as they only can be
allocated memory dynamically. (plz correct me if i'm wrong).

please tell me, if i'm on wrong path. and if i'm not :-), plz tell me
how to proceed to get information about dynamically allocated memory.

[Eric Sosman]

Re: Dynamic Memory Allocation

Nehil wrote:

can i find about following 2 things, by providing my own API of
functions for a C program :
>
1) static, global and const section of variables (pointers only), and
to pickout only those which are dynamically allocated.
>
2) Local variable which are pointers and have dynamically allocated
memory.

There is no portable way to test whether a particular
pointer points to dynamic, static, or automatic memory.

Actually, i want to develop an API, which will help in collection
garbage in C program. i.e. programmer will not explicitely call free()
function. The algorithm choosen is : Mark & Sweep.
if somehow i get the info about above mentioned points, the path
further will be easier for me.
>
I'm concentrating on pointer variables only, as they only can be
allocated memory dynamically. (plz correct me if i'm wrong).

You are wrong: A pointer variable can point to memory
of all three kinds. The same pointer variable can point to
different kinds of memory at different points during the
program's execution.

please tell me, if i'm on wrong path. and if i'm not :-), plz tell me
how to proceed to get information about dynamically allocated memory.

There have been some implementations of garbage collection
for C. The resulting implementation cannot, I believe, be a
conforming C implementation (unless it never decides to collect
any "garbage" at all). GIYF.

--
Eric Sosman
esosman@ieee-dot-org.invalid

[santosh]

Re: Dynamic Memory Allocation

Nehil wrote:

can i find about following 2 things, by providing my own API of
functions for a C program :
>
1) static, global and const section of variables (pointers only), and
to pickout only those which are dynamically allocated.
>
2) Local variable which are pointers and have dynamically allocated
memory.

Pointers can point to different types of objects, static, dynamic,
automatic etc. You cannot portably determine what type of memory it's
pointing to.

Actually, i want to develop an API, which will help in collection
garbage in C program. i.e. programmer will not explicitely call free()
function. The algorithm choosen is : Mark & Sweep.
if somehow i get the info about above mentioned points, the path
further will be easier for me.
>
I'm concentrating on pointer variables only, as they only can be
allocated memory dynamically. (plz correct me if i'm wrong).
>
please tell me, if i'm on wrong path. and if i'm not :-), plz tell me
how to proceed to get information about dynamically allocated memory.

Try to study the internals of existing GCs like Boehm's
implementation. A quick Google search also turns up a lot of
interesting links with information on implementing GCs and their
associated issues.

[Ben Bacarisse]

Re: Dynamic Memory Allocation

Nehil <nehilparashar@ gmail.comwrites :

can i find about following 2 things, by providing my own API of
functions for a C program :
>
1) static, global and const section of variables (pointers only), and
to pickout only those which are dynamically allocated.
>
2) Local variable which are pointers and have dynamically allocated
memory.

No portable solution exists.

<snip>

I'm concentrating on pointer variables only, as they only can be
allocated memory dynamically. (plz correct me if i'm wrong).

Your terminology is a little off, but the logic is way off. To
implement mark-and-sweep you need to find all pointers to allocated
memory, and these will not always be in "pointer variables".
Consider:

union either {
int i;
void *p;
};

and a code fragment like:

union either *ep = malloc(10 * sizeof *ep);
ep[0].i = 42;
ep[1].p = malloc(10);

You will have to find and mark ep[1].p. I use a union to show that
you can not tell, even by looking at the declaration, what may and may
not contain a pointer.

--
Ben.

[Default User]

Re: Dynamic Memory Allocation

Nehil wrote:

Actually, i want to develop an API, which will help in collection
garbage in C program. i.e. programmer will not explicitely call free()
function. The algorithm choosen is : Mark & Sweep.

I recommend you thoroughly learn the standard C language before
embarking on any such task.

Oh, and "plz" is not a standard English abreviation for anything.




Brian

[Malcolm McLean]

Re: Dynamic Memory Allocation


"Ben Bacarisse" <ben.usenet@bsb .me.ukwrote in message
news:87ejjj3rrs .fsf@bsb.me.uk. ..

Nehil <nehilparashar@ gmail.comwrites :
>

>can i find about following 2 things, by providing my own API of
>functions for a C program :
>>
>1) static, global and const section of variables (pointers only), and
>to pickout only those which are dynamically allocated.
>>
>2) Local variable which are pointers and have dynamically allocated
>memory.

>
No portable solution exists.
>
<snip>

>I'm concentrating on pointer variables only, as they only can be
>allocated memory dynamically. (plz correct me if i'm wrong).

>
Your terminology is a little off, but the logic is way off. To
implement mark-and-sweep you need to find all pointers to allocated
memory, and these will not always be in "pointer variables".
Consider:
>
union either {
int i;
void *p;
};
>
and a code fragment like:
>
union either *ep = malloc(10 * sizeof *ep);
ep[0].i = 42;
ep[1].p = malloc(10);
>
You will have to find and mark ep[1].p. I use a union to show that
you can not tell, even by looking at the declaration, what may and may
not contain a pointer.
>

However it is only a problem is you cannot tolerate a few false positives.
Unless the program is deliberately engineered to break your system, it is
most unlikely that a valid 32-bit pointer will also be an integer of use. It
will happen once or twice, in which case you hold the data until the integer
changes. Only if the block pointed to happens to be very large do you have a
problem, although then it could be a severe one.
--
Free games and programming goodies.

http://www.personal.leeds.ac.uk/~bgy1mm

[Ben Bacarisse]

Re: Dynamic Memory Allocation

"Malcolm McLean" <regniztar@btin ternet.comwrite s:

"Ben Bacarisse" <ben.usenet@bsb .me.ukwrote in message
news:87ejjj3rrs .fsf@bsb.me.uk. ..

>Nehil <nehilparashar@ gmail.comwrites :
>>

>>can i find about following 2 things, by providing my own API of
>>functions for a C program :
>>>
>>1) static, global and const section of variables (pointers only), and
>>to pickout only those which are dynamically allocated.
>>>
>>2) Local variable which are pointers and have dynamically allocated
>>memory.

>>
>No portable solution exists.
>>
><snip>

>>I'm concentrating on pointer variables only, as they only can be
>>allocated memory dynamically. (plz correct me if i'm wrong).

>>
>Your terminology is a little off, but the logic is way off. To
>implement mark-and-sweep you need to find all pointers to allocated
>memory, and these will not always be in "pointer variables".
>Consider:
>>
> union either {
> int i;
> void *p;
> };
>>
>and a code fragment like:
>>
> union either *ep = malloc(10 * sizeof *ep);
> ep[0].i = 42;
> ep[1].p = malloc(10);
>>
>You will have to find and mark ep[1].p. I use a union to show that
>you can not tell, even by looking at the declaration, what may and may
>not contain a pointer.
>>

However it is only a problem is you cannot tolerate a few false
positives.

The problem is deeper than that. How do you know how big the area
pointed to be ep is? If can get that in some non-portable way from
ep, how do know which offsets within it have pointers? On a machine
which can align pointers on any boundary, you have to look at every
single byte offset from ep. All the false positives lead to further
such searches (because you have to assume there is valid block size,
wherever you look for it). Any of these may lead to a run-time fault
and you need to find some way round that.

But you can't do any of this in a portable way.

system, it is most unlikely that a valid 32-bit pointer will also be
an integer of use. It will happen once or twice, in which case you
hold the data until the integer changes. Only if the block pointed to
happens to be very large do you have a problem, although then it could
be a severe one.

The block may appear to be huge entirely by accident and not be an
allocated block at all. You will have to follow leads even when that
are daft.

--
Ben.

[Malcolm McLean]

Re: Dynamic Memory Allocation


"Ben Bacarisse" <ben.usenet@bsb .me.ukwrote in message
news:87zm263izr .fsf@bsb.me.uk. ..

"Malcolm McLean" <regniztar@btin ternet.comwrite s:
>

>"Ben Bacarisse" <ben.usenet@bsb .me.ukwrote in message
>news:87ejjj3rr s.fsf@bsb.me.uk ...

>>Nehil <nehilparashar@ gmail.comwrites :
>>>
>>>can i find about following 2 things, by providing my own API of
>>>functions for a C program :
>>>>
>>>1) static, global and const section of variables (pointers only), and
>>>to pickout only those which are dynamically allocated.
>>>>
>>>2) Local variable which are pointers and have dynamically allocated
>>>memory.
>>>
>>No portable solution exists.
>>>
>><snip>
>>>I'm concentrating on pointer variables only, as they only can be
>>>allocated memory dynamically. (plz correct me if i'm wrong).
>>>
>>Your terminology is a little off, but the logic is way off. To
>>implement mark-and-sweep you need to find all pointers to allocated
>>memory, and these will not always be in "pointer variables".
>>Consider:
>>>
>> union either {
>> int i;
>> void *p;
>> };
>>>
>>and a code fragment like:
>>>
>> union either *ep = malloc(10 * sizeof *ep);
>> ep[0].i = 42;
>> ep[1].p = malloc(10);
>>>
>>You will have to find and mark ep[1].p. I use a union to show that
>>you can not tell, even by looking at the declaration, what may and may
>>not contain a pointer.
>>>

>However it is only a problem is you cannot tolerate a few false
>positives.

>
The problem is deeper than that. How do you know how big the area
pointed to be ep is?
>
The block may appear to be huge entirely by accident and not be an
allocated block at all. You will have to follow leads even when that
are daft.
>

That's another problem. In practical terms you need control of the malloc
system so that you have a list of blocks.
Then dynamic blocks can and often do contain pointers to other dynamic
blocks. But since you have a full list of blocks the problem is only O(N).
You can sweep, and remove orphan blocks. Ring blocks are a bit trickier;
ultimately you've got to track back to scope and caller scope.

Another snag is if the caller keeps a pointer in a disguised form. Again,
normally this would only be done in a deliberate attempt to subvert the
system, but it could be legitimate if, for instance, a pointer is
incremented to point to block plus some user-defined header.

--
Free games and programming goodies.

http://www.personal.leeds.ac.uk/~bgy1mm

[Ben Bacarisse]

Re: Dynamic Memory Allocation

"Malcolm McLean" <regniztar@btin ternet.comwrite s:

"Ben Bacarisse" <ben.usenet@bsb .me.ukwrote in message
news:87zm263izr .fsf@bsb.me.uk. ..

>"Malcolm McLean" <regniztar@btin ternet.comwrite s:
>>

>>"Ben Bacarisse" <ben.usenet@bsb .me.ukwrote in message
>>news:87ejjj3r rs.fsf@bsb.me.u k...
>>>Nehil <nehilparashar@ gmail.comwrites :
>>>>
>>><snip>
>>>>I'm concentrating on pointer variables only, as they only can be
>>>>allocated memory dynamically. (plz correct me if i'm wrong).
>>>>
>>>Your terminology is a little off, but the logic is way off.

<snip>

>>However it is only a problem is you cannot tolerate a few false
>>positives.

>>
>The problem is deeper than that. How do you know how big the area
>pointed to be ep is?
>>
>The block may appear to be huge entirely by accident and not be an
>allocated block at all. You will have to follow leads even when that
>are daft.
>>

That's another problem.

We are in danger of going round in circles. I know that with enough
assumptions about the environment, sufficient non-portable code, and a
lot of machinery, something can be done that will work for a subset of
C programs. The OP seemed to think that "dynamicall y allocated"
memory could be found by looking only at "pointer variables". It
seemed worth showing that that is not enough.

In practical terms you need control of the malloc system so that you
have a list of blocks.

In practical terms you need to use a language that has garbage
collection (or is amenable to it). The big question hanging over all
this is why on Earth do it at all? Why struggle (and it would be a
struggle) to do something half-baked for C when there are so many fine
programming languages languishing in obscurity?

There are one or two complex execution patterns where it is not
possible to decide in the normal way when something can be safely
freed. For example: an interpreter for a functional programming
language. But in such cases you can portably implement a garbage
collected memory area for that application. In the example of an FP,
you provide garbage collection for that language, not for the C
program that implements it.

--
Ben.

[Gordon Burditt]

Re: Dynamic Memory Allocation

>Another snag is if the caller keeps a pointer in a disguised form. Again,

>normally this would only be done in a deliberate attempt to subvert the
>system, but it could be legitimate if, for instance, a pointer is
>incremented to point to block plus some user-defined header.

Another type of snag is the pointer kept in a *file*. There's nothing
wrong with that if the pointer is written and later read by the same
instance of the running program.

That could horribly slow down garbage collection if the program has
a 4TB file open, even if there aren't any pointers in it, but there
*might* be.

[CBFalconer]

Re: Dynamic Memory Allocation

Ben Bacarisse wrote:

>

.... snip about garbage collection ...

>
In practical terms you need to use a language that has garbage
collection (or is amenable to it). The big question hanging over
all this is why on Earth do it at all? Why struggle (and it
would be a struggle) to do something half-baked for C when there
are so many fine programming languages languishing in obscurity?

One (of many) possibilities is that you don't want the obscurity of
program delays at possibly awkward times. Another is the
(non-)reliability of such methods.

--
<http://www.cs.auckland .ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfoc us.com/columnists/423>
<http://www.aaxnet.com/editor/edit043.html>
cbfalconer at maineline dot net


--
Posted via a free Usenet account from http://www.teranews.com

[jacob navia]

Re: Dynamic Memory Allocation

Nehil wrote:

can i find about following 2 things, by providing my own API of
functions for a C program :
>
1) static, global and const section of variables (pointers only), and
to pickout only those which are dynamically allocated.
>
2) Local variable which are pointers and have dynamically allocated
memory.
>
Actually, i want to develop an API, which will help in collection
garbage in C program. i.e. programmer will not explicitely call free()
function. The algorithm choosen is : Mark & Sweep.
if somehow i get the info about above mentioned points, the path
further will be easier for me.
>
I'm concentrating on pointer variables only, as they only can be
allocated memory dynamically. (plz correct me if i'm wrong).
>
please tell me, if i'm on wrong path. and if i'm not :-), plz tell me
how to proceed to get information about dynamically allocated memory.
>

The garbage collector of Boehm does this for C and C++.
Read that source code first, before embarking in your own
coding, since it is working since several years.

That garbage collector is distributed (among others) with the
lcc-win32 compiler

http://www.cs.virginia.edu/~lcc-win32

[Keith Thompson]

Re: Dynamic Memory Allocation

Ben Bacarisse <ben.usenet@bsb .me.ukwrites:

Keith Thompson <kst-u@mib.orgwrites :

[...]

>In practical terms, my understanding is that the Boehm garbage
>collector works well enough for many purposes, even in C.

>
That implementation looks very good. They have certainly covered all
the bases save for those that are logically doomed.

[...]

Yes, there must be situations where it is useful in C, but one of the
suggested uses is to remove memory leaks from existing code. That
just rubs all my aesthetic fur the wrong way. If I were still being
paid for fixing bugs, I am sure I would use it for that too, but I
would feel it was the wrong solution.

I suspect (and this is only speculation, really) that you should
designed your code from the start to use GC (garbage collection).
Applying GC to an existing application is likely to be difficult.
Applying GC to an existing application *for the purpose of fixing
memory leaks* is likely to be an act of desperation.

I have a gut feeling (which I am totally unable to justify with any
evidence) that the other use cases are very rare and are likely to
ones where other solutions such using another language or writing an
application specific memory management system are also options.
>
Did you have any uses cases in mind?

Nope. I've actually never used Boehm GC, or any other garbage
collector in C. (I do a lot of programming in Perl, which has
built-in GC; in Perl, I don't really think about it, because I don't
have to. But Perl is a very different language from C.)

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"