www.digitalmars.com         C & C++   DMDScript  

D - Garbage Collection: Please don't track non-pointers

reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
I wanted to know if D is designed to track object references through
non-pointer objects.  I know that you've said that you won't track
references hidden behind bitmasks and such, but are you going to allow
people to store pointers in integers?

It's an old nightmare legacy of C that you can easily store an address
in an integer.  While I'm not against letting people do the cast, I
don't think that we should make the garbage collector account for it.

If we decide to only track pointers, then we can use reference
counting.  I know, reference counting doesn't work with cycles...but a
guy here in IBM has developed and tested a collector that detects loops
in a reference-counting system.  And he does it entirely without having
to ever trace the object tree!



http://www.research.ibm.com/people/d/dfb/papers.html#Bacon01Java

especially his articles on "Recycler":
 http://www.research.ibm.com/people/d/dfb/papers/Bacon01Java.pdf
 http://www.research.ibm.com/people/d/dfb/papers/Bacon01Concurrent.pdf



I think that this, or something much like it, should be D's garbage
collector.

--
The Villagers are Online! villagersonline.com

.[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
.[ (a version.of(English).(precise.more)) is(possible) ]
?[ you want.to(help(develop(it))) ]
Nov 15 2001
next sibling parent reply "Pavel Minayev" <evilone omen.ru> writes:
"Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
news:3BF401E9.BE45CA0F deming-os.org...

 I wanted to know if D is designed to track object references through
 non-pointer objects.  I know that you've said that you won't track
 references hidden behind bitmasks and such, but are you going to allow
 people to store pointers in integers?


According to the specification:

"Casting pointers to non-pointers and vice versa is not allowed in
D. This is to prevent casual manipulation of pointers as integers,
as these kinds of practices can play havoc with the garbage collector
and in porting code from one machine to another. If it is really,
absolutely, positively necessary to do this, use a union, and even then,
be very careful that the garbage collector won't get botched by this."

And further on the topic:

"Perhaps we should do away with unions entirely, or at least unions
that contain pointers."

I believe this means that direct manupulation of pointers will
be absolutely prohibited. Not something I'm against about, though =)
Nov 15 2001
parent reply "Sean L. Palmer" <spalmer iname.com> writes:
Just so long as there's still a way to align a pointer somehow.  Sometimes
you *do* need to know the bits of a pointer and do more kinds of math on
them than simple add/subtract.  For instance binary &, |, &=, and |= would
need to work on pointers, and ints should be castable to pointer type.  Alot
of time people need to shift parts of a pointer down and analyze them.

What's already in the spec is to allow casting pointer to int (with some
pain), but not support that in the garbage collector, thus it's up to the
programmer to make sure not to confuse the garbage collector with what they
do with said pointer.  That's fine with me.

It would be hard to prevent pointer abuse without absolutely disallowing any
conversion from int to pointer or back, and disallowing any manipulation of
pointer values (disallowing adding integer offsets to a pointer),
disallowing taking the address of a pointer variable, etc.  Even that's not
foolproof.  Somebody will hack with pointers if it's necessary, no matter
how hard the language tries to prevent it.

Sean


"Pavel Minayev" <evilone omen.ru> wrote in message
news:9t14c2$1glj$1 digitaldaemon.com...

 "Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
 news:3BF401E9.BE45CA0F deming-os.org...

 I wanted to know if D is designed to track object references through
 non-pointer objects.  I know that you've said that you won't track
 references hidden behind bitmasks and such, but are you going to allow
 people to store pointers in integers?


 According to the specification:

 "Casting pointers to non-pointers and vice versa is not allowed in
 D. This is to prevent casual manipulation of pointers as integers,
 as these kinds of practices can play havoc with the garbage collector
 and in porting code from one machine to another. If it is really,
 absolutely, positively necessary to do this, use a union, and even then,
 be very careful that the garbage collector won't get botched by this."

 And further on the topic:

 "Perhaps we should do away with unions entirely, or at least unions
 that contain pointers."

 I believe this means that direct manupulation of pointers will
 be absolutely prohibited. Not something I'm against about, though =)
Nov 15 2001
parent reply "Pavel Minayev" <evilone omen.ru> writes:
"Sean L. Palmer" <spalmer iname.com> wrote in message
news:9t15m4$1it7$1 digitaldaemon.com...


 Just so long as there's still a way to align a pointer somehow.  Sometimes


Sorry, I don't get this one... since you can only store null and
addresses of variables in the pointer, you always have it aligned
unless you do some shifting.

And anyhow, why worry about that? Let the compiler do its job.


 you *do* need to know the bits of a pointer and do more kinds of math on
 them than simple add/subtract.  For instance binary &, |, &=, and |= would
 need to work on pointers, and ints should be castable to pointer type.


Alot

 of time people need to shift parts of a pointer down and analyze them.


Why? If you mean storing something else in pointer, then
here's what the specs say:

a.. Do not take advantage of alignment of pointers to store bit flags in
  the low order bits, do not store bit flags in the high order bits.
a.. Do not store integer values into pointers.
a.. Do not store magic values into pointers, other than null.


 What's already in the spec is to allow casting pointer to int (with some


Where???

"Casting pointers to non-pointers... is not allowed in D"

Or do you mean by using unions? Then it's not casting.
It's hacking.


 It would be hard to prevent pointer abuse without absolutely disallowing


any

 conversion from int to pointer or back, and disallowing any manipulation


of

 pointer values (disallowing adding integer offsets to a pointer),


I agree that there is a way to play tricks with pointers,
like that:

    int* screen = null;
    screen += 0xA00000;

Still it's more "foolproof" as in C.


 disallowing taking the address of a pointer variable, etc.  Even that's


not

 foolproof.  Somebody will hack with pointers if it's necessary, no matter
 how hard the language tries to prevent it.


Yes, but at least this won't lead to any confusion. You can hack
with pointers only when you really need it, not just here or there
or even accidently.
Nov 15 2001
parent reply Russell Borogove <kaleja estarcion.com> writes:
Pavel Minayev wrote:

 
 "Sean L. Palmer" <spalmer iname.com> wrote:

 you *do* need to know the bits of a pointer and do more kinds of math on
 them than simple add/subtract.  For instance binary &, |, &=, and |= would
 need to work on pointers, and ints should be castable to pointer type.


 Alot

 of time people need to shift parts of a pointer down and analyze them.


 
 Why? If you mean storing something else in pointer, then
 here's what the specs say:
 
 a.. Do not take advantage of alignment of pointers to store bit flags in
   the low order bits, do not store bit flags in the high order bits.
 a.. Do not store integer values into pointers.
 a.. Do not store magic values into pointers, other than null.


It's not a factor for the initial target platforms like 
standard-architecture x86 systems, but some hardware platforms
specify features like bypassing the cache when bit 30 is set 
in an access address, or have different address ranges 
being significant in different ways, like on-chip scratchpad 
memories, memories shared with coprocessors, etc.

(Me, working on a Playstation 2 project? Why do you ask?)

(Walter -- you may want to bear in mind the possibility that 
different bit patterns could refer to the same memory address 
while designing/implementing the GC. I don't know how much 
impact that will have, but future D-porters might be grateful.)

From the D overview:







I think this will ultimately require the capability of bitwise 
pointer manipulation in a code-efficient way.

-RB
Nov 15 2001
parent "Walter" <walter digitalmars.com> writes:
"Russell Borogove" <kaleja estarcion.com> wrote in message
news:3BF43C1A.EFB704AA estarcion.com...

 (Walter -- you may want to bear in mind the possibility that
 different bit patterns could refer to the same memory address
 while designing/implementing the GC. I don't know how much
 impact that will have, but future D-porters might be grateful.)


The implementation of the gc will necessarilly have some platform specific
code in it. I try to eliminate platform specific stuff from the spec of the
language itself, but it is intended for systems work, so there will be some
inherently non-portable aspects of it (like the size of ints vs the size of
pointers).

Java's goal is write once, run anywhere. While D tries to avoid
*unnecessary* platform specific cruft, real code will have some, and D's
main focus is on improving the reliability of your programs, not
portability.
Nov 15 2001
prev sibling parent reply "Walter" <walter digitalmars.com> writes:
"Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
news:3BF401E9.BE45CA0F deming-os.org...

 I wanted to know if D is designed to track object references through
 non-pointer objects.  I know that you've said that you won't track
 references hidden behind bitmasks and such, but are you going to allow
 people to store pointers in integers?


No. Use a union!


 It's an old nightmare legacy of C that you can easily store an address
 in an integer.  While I'm not against letting people do the cast, I
 don't think that we should make the garbage collector account for it.


The way it will be supported is if the code unions a pointer and integer.
The gc will treat such as ambiguous pointers.


 If we decide to only track pointers, then we can use reference
 counting.  I know, reference counting doesn't work with cycles...but a
 guy here in IBM has developed and tested a collector that detects loops
 in a reference-counting system.  And he does it entirely without having
 to ever trace the object tree!


I've written mark-and-sweep generational collectors before, so I'm
comfortable with using that technology. Reference counting likely will not
work also because the array semantics allow pointers into the middle of
allocated objects.
Nov 15 2001
parent Charles Hixson <charleshixsn earthlink.net> writes:
I have occasionally felt that there should be bit addressable 
pointers for use within a structure.  There specifications would 
be something like:
based on sturcture st, Interpreting bits 59 through 63 and a 
binary integer, use the name: furgle;

Of course that's not a valid syntax, but that would be the 
meaning.  As to the syntax, it would be rather like:

struct 
st
{ 
...
};

offset st(59, 63) furgle;

This would be defined at compile time, but would allow one to 
address arbitrary bits within a structure.  Presumably it would 
be implemented via copy shift op shift mask or semantics. 
Messy, but a lot less dangerous if the compiler figures things 
out than if I do.
Dec 03 2001