[Gcl-devel] Re: dynamic-extent make-list initialization error?

[Camm Maguire]

Greetings!

Robert Boyer <address@hidden> writes:

> Here is a totally off the wall idea.
> 
> What should GCL (or Common Lisp) do with stack conses that are actually free?
> I mean stack conses that are pointed to by no one, as established by their
> not getting marked in the mark phase of the GC.  One possibility is that the
> garbage collector could be "enhanced" to mark such conses by placing a
> special (but ordinary Lisp) object in the conses' cars as a way to signal to
> the Lisp user that they are indeed now free.  Then the Lisp user could
> possibly make further use of them.
> 
> Probably utterly crazy.
> 

OK, almost certainly not crazy, but it is quite likely that I am not
following you completely yet.

Conses are marked recursively, but the recursion is truncated if the
address satisfies the NULL_OR_ON_C_STACK macro -- i.e. unlike the
static array case, none of your stack conses should be marked by the
gc unless I'm misunderstanding something, which is always quite
likely.

Secondly, even if the gc marking did traverse into the stack (which
could be achieved easily enough), sweeping is done pagewise stepping
through the heap, i.e. for each heap page, traverse all objects
therein according to their known size (from the page type), unmark
those marked, and free the rest.  contiguous pages are freed by
inserting a linked list in the data area, and relocatable pages are
freed by a giant copy of the moved data into its new location.  Lisp
objects are not intended to be held in either of the latter two
locations, so no object bit-mangling is necessary.  As for the C
stack, on the other hand, if one has a :dynamic-extent object, if the
mark is allowed to traverse into the stack area and modify it, then one
must be able to unmark at a minimum unless chaos is to ensue -- as
there is no easy way to do the latter, the former is skipped.

The only obstacle to this is designing a reliable algorithm to walk
the stack and a) determine which areas contain lisp objects (as
opposed to pointers thereto), and b) determine what type of object
this is.  The latter might not be so tough -- we could walk the area 8
bytes at a time and use the normal bit identifiers to determne the
type and step to the next location according to its size.  The former
is well-nigh impossible as far as I can see, at least to accomplish in
the general case, as the stack is shared by necessity with all sorts
of non-lisp data, any of which might be confused as a lisp object,
i.e. any even number less than 0xc0000000 on an 8 byte boundary is a
cons, etc.  Confusing a lisp pointer is not a disaster according to
the conservative gc algorithm, for at worst we will hold on to too much
garbage.  But in this case the gc algorithm would have to modify the
stack memory directly.  One might not even be able to return from GBC
if one makes a sufficient error here!

This said, it is entirely possible to reserve certain stack areas and
handle these in normal gc fashion.  It might be interesting to see how
stack_alloc_start and stack_alloc_end are used in forked children, for
example.   One must be carefuly to rationalize such ad-noc uses of
stack space -- we already have alloca_val for compiled :dynamic-extent
allocations in addition to the stack_alloc_start for example.  One
might even conceive of a linked list in stack space demarking areas
reserved for lisp objects somewhat akin to the contiguous page
algorithm. 


<fascinating stuff I'm trying to digest snipped>


> (defun after-gbc (type)
>   ;;  When this function is called we have completed a garbage
>   ;;  collection but not yet unmarked things in *cht* that need
>   ;;  unmarking.  As a result any pointer into *cht* is likely to
>   ;;  cause a stack overflow if it is handled by GCL in any way until
>   ;;  we get the unmarking done.  So we must use as small a subset of
>   ;;  GCL as we possibly can, in particular no I/O, except when
>   ;;  debugging and taking our chances.  No consing.  No boxing.
>   
>   (declare (ignore type))
>   (let ((tail *hut-alist*)
>         (prev nil))
>     (loop while tail do
>           (let ((ar (caar tail)))
>             (declare (counter ar))
>             ;; Uses of si::nani are extremely dangerous!  What we are
>             ;; hoping to establish here is whether the cons that was
>             ;; created as part of a hut or hhut is now free.
>             ;; According to Camm, the cdr is changed when a cons is
>             ;; freed -- it is made to be not a imm fixnum if it was,
>             ;; and its "free" bit is turned on.
>             (cond ((not (= (the fixnum (aref ar 1))
>                            (si::address (cdr (si::nani (the fixnum (aref ar 
> 0)))))))

I'm not sure I understand the logic above -- might you elaborate if
you have time?

take care,


>                    (cond (prev (rplacd prev (cdr tail))
>                                (setq tail (cdr tail)))
>                          (t (setq *hut-alist* (cdr tail))
>                             (setq tail *hut-alist*))))
>                   (t (setq prev tail)
>                      (setq tail (cdr tail))))))))
> 
> (cond ((and (fboundp 'after-gbc)
>             (compiled-function-p (symbol-function 'after-gbc)))
>        (setq si::*after-gbc-hook* (function after-gbc))))
> 

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