Re: Great Circle and Ada?

Re: Great Circle and Ada?

[Lars Farm]

Robert Dewar <dewar@cs.nyu.edu> wrote:

> An obvious counter-example is the use of virtual
> origins to reference dynamically allocated arrays.

What is virtual origin? Somewhere there has to be a way to reach the block
from users code if one is to use it. Is is a pointer into the interior of
an allocated block rather than to the start of the block? If so, at least
Boehms GC has no problems with it and Great Circle can probably handle
interior pointers too.


-- 
Lars Farm, lars.farm@ite.mh.se

Re: Great Circle and Ada?

[Robert A Duff]

In article <AE643969966856B24@dialup112-5-3.swipnet.se>,
Lars Farm <lars.farm@ite.mh.se> wrote:
>What is virtual origin?

This means you represent a pointer to array A as the address of A[0].
If the zeroth element doesn't exist, then use the address of where it
"would" be.  So, if A has bounds 1..10, the pointer to A is the address
just before the array in memory.  If A has bounds -10..10, the pointer
is an address of the middle of A.  If A has bounds 1_000_000..2_000_000,
then the pointer is the address of some word very far from A.

>... Somewhere there has to be a way to reach the block
>from users code if one is to use it.

The compiler knows it's doing this, and so can generate the right code.
The address of the N'th element is simply
(the pointer) + N*(size-of-component).  The efficiency advantage is
that you avoid subtracting off the lower bound (which would be necessary
if you always used the address of A(A'First).

The compiler needs to keep the bounds of the array "somewhere else", so
it can do bounds checking.

>... Is is a pointer into the interior of
>an allocated block rather than to the start of the block? If so, at least
>Boehms GC has no problems with it and Great Circle can probably handle
>interior pointers too.

It's quite possible to implement GC with virtual origins, but the GC has
to know about it, and do the appropriate thing (just like the
compiler-generated code does).  This requires some cooperation between
the compiler and the GC (which is a Good Thing anyway, IMHO, but is not
the case with gcc/GNAT).

- Bob

Re: Great Circle and Ada?

[Norman H. Cohen]

In article <DxvLyG.J86@world.std.com>, bobduff@world.std.com
(Robert A Duff) writes: 

|> In article <AE643969966856B24@dialup112-5-3.swipnet.se>,
|> Lars Farm <lars.farm@ite.mh.se> wrote: 
|> >What is virtual origin?
...
|> >... Is is a pointer into the interior of
|> >an allocated block rather than to the start of the block? If so, at least
|> >Boehms GC has no problems with it and Great Circle can probably handle
|> >interior pointers too.
|>
|> It's quite possible to implement GC with virtual origins, but the GC has
|> to know about it, and do the appropriate thing (just like the
|> compiler-generated code does).  This requires some cooperation between
|> the compiler and the GC (which is a Good Thing anyway, IMHO, but is not
|> the case with gcc/GNAT).

However, a CONSERVATIVE garbage collector makes guesses about which words
are pointers precisely because it has no information about how the
compiler has laid out storage.  The only knowledge exploited by a
conservative garbage collector is knowledge of the data structure
(typically boundary tags) used by the run-time system's allocator.  If a
word contains a value that happens to lie between the addresses of the
beginning and ending boundary tags for an allocated block, the
conservative collector marks that block as reachable, and goes on to
examine the words in that block in the same manner.  (For typical
versions of malloc, it is possible to find all boundary tags by
recognizing the first word on the heap as a beginning tag, using the
length information to find the corresponding closing tag, recognizing the
next word as the beginning tag of the next block, and so forth.)

If a compiler uses virtual origins, then a block may be, in effect,
pointed to by a word whose value does not lie between the addresses of
the beginning and ending boundary tags.

--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Great Circle and Ada?

[Robert A Duff]

In article <51mj21$jif@watnews1.watson.ibm.com>,
Norman H. Cohen <ncohen@watson.ibm.com> wrote:
>However, a CONSERVATIVE garbage collector makes guesses about which words
>are pointers precisely because it has no information about how the
>compiler has laid out storage.  The only knowledge exploited by a
>conservative garbage collector is knowledge of the data structure
>(typically boundary tags) used by the run-time system's allocator.

I wouldn't say that's the *only* knowledge.  The conservative GC also
knows (or hopes!) that the compiler represents access types or pointers
or whatever language feature it is using machine addresses.  And that
these machine addresses always point at the data, or perhaps in the
middle of the data.

There are *lots* of tricks compilers can play that will break a
conservative garbage collector.  Virtual origins is one.  Playing games
with pointer representation is another.  E.g. packing a small integer
field and a pointer into one 32-bit word.  (A pointer doesn't always
need all 32 bits -- the low bits are always zero, because the thing is
known to be aligned, and the high bits are known, because the compiler
knows where the heap and other data is in the address space).  How about
the Lisp-ish tricks for representing fixnums vs. bignums?

Compiler writers blame it on the conservative gc, and gc writers blame
it on the compiler.  ;-)  Either way, there has to be *some* known
information about the interface between the two, or gc won't work.

- Bob

Great Circle and Ada?

[John G. Volan]

Anybody around here ever heard of Great Circle, an automatic garbage
collector for C/C++ produced by Geodesic? I just stumbled upon their
web-site: <http://www.geodesic.com/>  It's described as a conservative,
incremental, real-time, thread-safe (?) garbage collector that can be
transparently linked into existing software, without having to recompile
your code (it replaces the system default versions of malloc() and
free()
with its own versions -- apparently their version of free() does
nothing).
They claim that they can automatically eliminate all memory leaks and
all premature/multiple deallocation problems, even in third party
libraries (for instance, the notoriously leaky X/Motif library).

The name "Great Circle" reminds me of Henry Baker's work on real-time
incremental garbage collection. Can anybody tell me whether there's a
connection?

The "transparent" version of Great Circle is a conservative garbage
collector: It determines which heap-allocated objects are still
accessible,
by searching through memory for any 32-bit value that contains an
address
on the heap. Obviously, this scheme can miss some garbage if a
non-pointer bit-pattern happens to look like a heap address.

There's also a "wrapped" version of Great Circle that's faster and
more precise, but it requires you to rewrite your code to make use of 
a garbage collected "smart pointer" class template (this is only for
C++,
of course).

It seems to me that it would be fairly straightforward to use the
transparent form of Great Circle with the GNAT compiler. (The way I
understand it, GNAT translates an Ada allocator into a call to malloc(),
and Ada.Unchecked_Deallocation into free().)  Has anybody tried this,
and if so, what results did you get?

Another possibility, which would take a lot more work, would be to map
Ada access types into Great Circle smart pointers. (Maybe someone could
experiment with the GNAT compiler to do this. Anybody already at it?)
As long as a programmer remained within the abstractions of Ada and
didn't venture into Unchecked_Conversions etc., the garbage collector
would always know the location of every access value.

I'm wondering whether this product is in fact thread-safe. If so, 
does it perform correctly and/or efficiently in the presence of Ada95
tasking. They claim it's great for real time (a GC pause supposedly
can be reduced down to a microsecond), but I have my doubts.

------------------------------------------------------------------------
Internet.Usenet.Put_Signature 
  (Name => "John G. Volan",  Home_Email => "John_Volan@syspac.com",
   Employer => "S.A.I.C.",   Work_Email => "John_Volan@dayton.saic.com",
   Slogan => "Ada95: The World's *FIRST* International-Standard OOPL",
   Disclaimer => "My employer never defined these opinions, so using " &
     "them is totally erroneous...or is that a bounded error now? :-)");
------------------------------------------------------------------------

Re: Great Circle and Ada?

[Robert Dewar]

John Volan says

"The "transparent" version of Great Circle is a conservative garbage
collector: It determines which heap-allocated objects are still
accessible,
by searching through memory for any 32-bit value that contains an
address
on the heap. Obviously, this scheme can miss some garbage if a
non-pointer bit-pattern happens to look like a heap address.
"

It can also garbage collect good stuff, there is no requirement that
a pointer to a block exist as such for a block to still be required
to stay around. An obvious counter-example is the use of virtual
origins to reference dynamically allocated arrays.


That's not to say this kind of technology is not useful, just that you
have to be careful to discount any bogus claims that it is bound to
be reliable!