Xref: utzoo comp.arch:17239 comp.lang.functional:303 comp.lang.lisp:3422 comp.lang.prolog:2956
Path: utzoo!attcan!uunet!ns-mx!iowasp.physics.uiowa.edu!maverick.ksu.ksu.edu!zaphod.mps.ohio-state.edu!rpi!uupsi!sunic!dkuug!freja.diku.dk!torbenm
From: torbenm@diku.dk (Torben [gidius Mogensen)
Newsgroups: comp.arch,comp.lang.functional,comp.lang.lisp,comp.lang.prolog
Subject: GC triggering and stack limit checking by MMU hardware
Keywords: GC, stack, heap, MMU
Message-ID: <1990Jul19.151524.22544@diku.dk>
Date: 19 Jul 90 15:15:24 GMT
Organization: Department Of Computer Science, University Of Copenhagen
Lines: 40


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. This is used to trigger events such as error
messages, garbage collection or allocation of more memory for a
fragmented stack. Usually, good implementations avoid testing on every
use of the stack / heap, but only once for every basic block or
procedure.

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:

Give each stack or heap a small number of pages of memory and make
sure that the logical addresses are far apart, and that a large
logical address space is given each, but where only the first small
part is actually mapped to physical (or virtual) memory.

Assign to each stack/heap an event that is invoked by the MMU trap
handler on access to unmapped memory. An event can ask for a new
physical page to be mapped to the corresponding area, or maybe try to
do garbage collection.

Virtual memory can handle the stack problem, as the only sensible
thing to do would be to assign new pages. However, triggering garbage
collection in the way described above is different from just extending
the virtual memory space. Furthermore, the idea is perfectly usable
even on systems with no virtual memory support.

I believe heap intensive languages like LISP, Prolog or functional
languages could benefit from such a strategy, especially if procedures
and basic blocks are short, which is often the case for object code
for these languages.

My question is: has this been done? And if not, why not?

I suspect that operating systems like Unix doesn't provide such
facilities to user processes, but the issue is then: should they?

	Torben Mogensen (torbenm@diku.dk)