Thread overview
Garbage Collection: Please don't track non-pointers
Nov 15, 2001
Russ Lewis
Nov 15, 2001
Pavel Minayev
Nov 15, 2001
Sean L. Palmer
Nov 15, 2001
Pavel Minayev
Nov 15, 2001
Russell Borogove
Nov 16, 2001
Walter
Nov 16, 2001
Walter
Dec 03, 2001
Charles Hixson
November 15, 2001
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))) ]


November 15, 2001
"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 =)


November 15, 2001
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 =)



November 15, 2001
"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.


November 15, 2001
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:
# D will retain the ability to do down-and-dirty programming
# without resorting to referring to external modules compiled
# in a different language. Sometimes, it's just necessary to
# coerce a pointer or dip into assembly when doing systems work.
# D's goal is not to prevent down and dirty programming, but
# to minimize the need for it in solving routine coding tasks.

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

-RB
November 16, 2001
"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.





November 16, 2001
"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.


December 03, 2001
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.