[Gcl-devel] Re: [Fwd: Uninitialized stack gaps and conservative garbage collection]

[Camm Maguire]

Greetings!

"Boehm, Hans" <address@hidden> writes:

> The collector also tries to address this with a complicated hack that
> occasionally checks for opportune times to clear sections of the
> stack that are not currently in use.  (See GC_clear_stack()
> in misc.c.)
> 

BTW, where is the official repository of your source these days?

> I think this is currently much more sophisticated in the single-threaded
> case.  It may be possible to enhance this code to deal with the
> problems that were observed.  But it has some inherent limitations.
> It only rarely gets control, and it can't clear areas in frames that
> are always live when it gets control.  It should handle deep recursions
> somewhat acceptably.
> 

I have no problem with accidental junk on the stack, nor values left
over after function return.  The issue to me is that when one pushes
up the stack a second time, one does not wipe out the old values, but
rather they could fall into 'stack holes'.  For GCL, this is most
critical above toplevel, as one never clears this stack again once
entered.  It also appears important in alloca, which appears to 16byte
pad the stack increment regardless of -mprefered-stack-boundary.
Beyond this, I think the best strategy, if any additional strategy is
needed, is to randomly allocate a little zeroed out stack in certain
key functions just to ensure that large loops don't preserve the
location of the stack holes forever.

Given the stack clearing algorithm, my other question is how to
portably implement it.  Here again is my trial function, which appears
quite dangerous.  It assumes that anything above the address of the
first argument passed to a function belongs to the parent stack frame,
for example.

void wipe_stack(VOL void *) __attribute__ ((noinline));
void
wipe_stack(VOL void *l) {

#if CSTACK_DIRECTION == -1
   if (l>(void *)&l) bzero((void *)&l,l-(void *)&l);
#else
  l+=sizeof(l);
  if ((void *)&l>l) bzero(l,(void *)&l-l);
#endif

}

void clear_c_stack(VOL unsigned) __attribute__ ((noinline));
void
clear_c_stack(VOL unsigned n) {

  void *v=OBJNULL;
  alloca(n);
  wipe_stack(&v);

}

void
funcall(object fun)
{ 
        object VOL sfirst=NULL;
        wipe_stack(&sfirst);
        {
        object temporary=OBJNULL;
        object x=OBJNULL;
        object * VOL top=NULL;
        object *lex=NULL;
        bds_ptr old_bds_top=NULL;
        VOL bool b=0;
        bool c=0;
        DEBUG_AVMA
....

}}

Raymond Toy writes:
>On the sparc port, this area can be zeroed out with appropriate
>optimization settings.  I ran some tests using Eric Marsden's
>cl-bench.   If the stack is always cleared, the cost of some
>benchmarks go up, but some go down, because the cost of GC is
>decreased.  (The benchmarks include GC time.)

Thanks for the tip -- does this use gcc, and if so, what is the
relevant switch?

Take care,

> Hans
> 
> > -----Original Message-----
> > From: address@hidden [mailto:address@hidden 
> > On Behalf Of Bryce McKinlay
> > Sent: Wednesday, May 25, 2005 6:55 AM
> > To: Ranjit Mathew
> > Cc: address@hidden
> > Subject: Re: [Fwd: Uninitialized stack gaps and conservative 
> > garbage collection]
> > 
> > 
> > Ranjit Mathew wrote:
> > 
> > >Interesting stuff found on the GCC list. Doesn't this
> > >affect GCJ as well where we use the conservative
> > >Boehm GC?
> > >  
> > >
> > >-------- Original Message --------
> > >Subject: Uninitialized stack gaps and conservative garbage collection
> > >Date: Tue, 24 May 2005 17:40:46 -0400
> > >From: Camm Maguire <address@hidden>
> > >Newsgroups: gmane.comp.gcc.devel,gmane.lisp.gcl.devel
> > >
> > >Greetings!  GCL is a lisp system that compiles to native object code 
> > >via the intermediary of gcc.  It uses a conservative garbage 
> > collection 
> > >algorithm, which means that it walks the C stack to find 
> > likely objects 
> > >in use by automatic variables, and holds on to these. This 
> > works quite 
> > >well in practice.
> > >
> > >For very large systems, the likelihood of holding onto objects which 
> > >should be collected increases.  In looking into this, it has 
> > come to my 
> > >attention that regardless of how carefully the C programmer 
> > initializes 
> > >variables on the stack, gcc will quite commonly allocate extra space 
> > >inaccessbile via any C variable.  These 'stack gaps' can wind up 
> > >permanently preventing a large portion of user memory from 
> > ever being 
> > >collected with this algorithm.
> > >
> > 
> > 
> > Sure, with a conservative GC there is always the possibility of 
> > uninitialized "junk" on the stack being mis-identified as a valid 
> > pointer. There's even the possibility of live non-pointer 
> > data, such as 
> > an int, being mis-identified as a pointer. Hopefully this is rare in 
> > GCJ, however, as the GC only considers pointers to the start of an 
> > object to be valid - interior pointers are disregarded, significantly 
> > reducing the chance of a mis-identification. On a 64-bit 
> > system, due to 
> > the larger address space, the chance of this happening 
> > reduces even further.
> > 
> > Bryce
> > 
> > 
> 
> 
> 

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah