Xref: utzoo comp.arch:17241 comp.lang.functional:304 comp.lang.lisp:3423 comp.lang.prolog:2960
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!snorkelwacker!bloom-beacon!eru!luth!sunic!mcsun!hp4nl!swi.psy.uva.nl!jan
From: jan@swi.psy.uva.nl (Jan Wielemaker)
Newsgroups: comp.arch,comp.lang.functional,comp.lang.lisp,comp.lang.prolog
Subject: Re: GC triggering and stack limit checking by MMU hardware
Keywords: GC, stack, heap, MMU
Message-ID: <3260@swi.swi.psy.uva.nl>
Date: 20 Jul 90 10:07:53 GMT
References: <1990Jul19.151524.22544@diku.dk>
Reply-To: jan@swi.psy.uva.nl (Jan Wielemaker)
Organization: SWI, UvA, Amsterdam
Lines: 86

In article <1990Jul19.151524.22544@diku.dk> torbenm@diku.dk (Torben [gidius Mogensen) writes:
>
>Most implementations (that I know) of programming languages with
>stacks or heaps, use some kind of explicit check to see when a stack
>or heap is full.
[stuff deleted]
>By using the MMU facilities present in most modern computers, these
>tests can be entirely done in hardware, and fragmented stacks can be
>done transparently. This is the idea:
[stuff deleted]
>My question is: has this been done? And if not, why not?

I implemented this schema for SWI-Prolog.  Richard Tobin of Edinburgh
University noted me at the NACLP in Cleveland last year of the
possibility to reach the MMU under SunOs 4.0 via the mmap() and related
calls.  The schema supports expanding the stacks and triggering the
garbage collector.  It works as follows:

    1) A file of 1 page is created on /tmp and opened for reading.
    2) Computed from the command line options for the stack limits,
       virtual address space is reserved for all the Prolog stacks.
       A 1 page gap is always maintained between the gaps.
    3) On a segmentation violation, the stack causing the problem
       is determined.  On SunOs the address is passed via the signal
       handler; on systems that do not provide this I walk along
       all stacks, comparing the current top with the allocated
       top.  Next, a page is added to the stack and a call to
       considerGarbageCollect() is made.  Afterwards the signal
       handler returns.
    4) considerGarbageCollect() checks whether this is a stack
       that needs garbage collection and how much the stack has
       grown after the last garbage collection on this stack. If
       a garbage collection is appropriate a global flag is set
       to indicate such.
    5) On a save point (the call port for Prolog) the global flag
       indicating a garbage collection request is checked and if
       requested a garbage collection is executed.  After the
       garbage collection all pages above the new stack top are
       unmapped from the address space.

       It is next to impossible to invoke the garbage collector
       direct from the signal handler.  One does not know the
       status of the virtual machine and the stacks are not
       guarantied to be consistent at an arbirary point in time.

The proposed schema is very simple to implement.  It provides
dynamically growing stacks (to some limit, but on most modern machines
this limit can be high as the virtual address space is large).  Expanding
the stacks is almost for free.  On conventional systems a stack shifter
needs to be implemented.  This is tiresome and shifting the stacks is
an expensive operation.

I have seen mmap() and related calls only on SunOs 4.0.  The call maps
at file a specific address in the virtual address space.  SunOs both
supports shared maps (writing in the mapped addresses are forwarded to
the file) and private maps (writing is not forwarded to the file).  For
the dynamic stacks I map the same 1 page file many times using a private
map at different places.

On some system-V Unix machines the same results can be obtained using
shared memory.  In this case the shared memory segments are allocated
and mapped in the stacks.  I implemented this on a GOULD PN9000 under
UTX 2.0?  It works nice on SunOs (as an alternative to mmap()) as well.
On HPUX 6.5 for one or another reason all stacks point to the same
physical memory (the same bug occurs in SunOs 4.0.0 on SUN-3; only on
4.0.1 and later things are ok).  Finally on AIX 2.0 on a PS2 machine
shared memory segments can only be mapped on 4M boundaries, which
implies only a difficult schema can be used: 1) create a new segment,
larger than the old one and map it at an arbitrary place; 2) copy the
contents of the old into the new; 3) deallocate the old; 4) map the new
into the old place and unmap it from the temporary place.  I did not yet
implement this latter schema.

Both schemas are not ideal.  The mmap() requires a file and reads the
file into the page as a page is mapped.  This is a waste of resources; I
just want a page of uninitialised memory and need no file.  The shared
memory solution is not ideal as well because shared memory objects are
global resources in system-V and only a limited number of them is
available to ALL processes.  Also, the process is responsible for
deallocating the resource, otherwise they survive the terminating
process.  It would be ideal to have two simple calls:

    map(base, lenght)
    unmap(base, lenght)

	Jan