Let's throw out SCM_NEWCELL

[Marius Vollmer]

Hi,

I have just returned from the land of half-initialized cells, and I'd
say we need to do something for the poor (half) souls there.

The specific problem that I was chasing was that scm_gc_mark is trying
to handle half-initialized cells by conservatively marking their
contents, but the luck had it so that it conservatively latched onto a
real free-list, and crashed because of a stack overflow.  (I think
this is your problem with the threads, Chris.  More on this in another
mail.)

Let me try to explain the logic behind the current behavior, to see
whether I understand it.

It can happen that the GC is invoked during the code that initializes
a cell.  The half initialized cell is seen by the GC, which would
normally cause it to crash.  To prevent this, the initialization code
is careful to set the type tag of the cell last, so that the GC will
either see a completely initialized cell, or a cell with type tag
`free_cell'.  However, some slot of that `free' cell might be the only
place where a live object is referenced from (since the compiler might
reuse the stack location or register that held it before it was
stuffed into the cell).  To protect such an object, the contents of
the cell (except the first word) is marked conservatively.


What happened to me was that scm_gc_mark hit upon a completely
uninitialized cell, that was tagged a s a free cell, and still pointed
to the rest of the freelist were it came from.  (It was probably this code

     :
    SCM_NEWCELL (port);                  // port is a free cell
    SCM_DEFER_INTS;
    pt = scm_add_to_port_table (port);   // this invokes the GC
     :

that caused it.)

scm_gc_mark would conservatively mark the cdr of the free cell, which
resulted in marking the whole free list.  This caused a stack overflow
because the marking didn't happen in a tail-calling manner.  (Even if
it doesn't crash, a lot of unnecessary work is done.)


I propose to change the current practice so that no half initialized
cell is ever seen by the GC.  scm_gc_mark would abort on seeing a free
cell, and scm_mark_locations (and scm_gc_mark_cell_conservatively if
will survive) would not mark a free cell, even if the pointer points
to a valid cell.  scm_gc_sweep would continue to ignore free cells.

To ensure that initialization can not be interrupted by a GC, we
provide new functions/macros to allocate a cell that include
initialization.  For example

    SCM scm_newcell_init (scm_bits_t car, scm_bits_t cdr)
    {
      SCM z;
      if (SCM_NULLP (scm_freelist))
        z = scm_gc_for_newcell (&scm_master_freelist,
                                &scm_freelist);
      else
        {
          z = scm_freelist;
          scm_freelist = SCM_FREE_CELL_CDR (scm_freelist);
        }
      SCM_SET_CELL_WORD_1 (z, cdr);
      SCM_SET_CELL_WORD_0 (z, car);
      scm_remember_upto_here (cdr);
      return into;
    }

For performance, we might turn this into a macro, and find some
specialized ways to make the compiler remember certain values (like
some `asm' statement for GCC).

In the transition period, while SCM_NEWCELL is deprecated, we can make
it always initialize the first slot with scm_tc16_allocated.  Such
cells are marked conservatively by the GC.  SCM_NEWCELL can have
abysmal performance while being deprecated.


This change is maybe best done together with straightening the
malloc/free thing and the SCM_DEFER/ALLOW_INTS chaos.


Did I get this right?