Linux and GC

[P T Withington]

On 5/12/98 17:43, David Gadbois wrote:

>Of course, a real Lisp OS would have cheap ways to fiddle with memory
>protections and take protection traps, so there would be no need for
>such UNIXy kludges.

That's the key.  If you control the O/S, you can do _much_ better with 
your GC.  I wonder if Mach's external pager concept would be one place to 
start.

Here's my pet list of things I'd like to see an O/S support for GC (some 
of which are already available in some O/S's):

o reserve virtual address space.
o handle "unmapped" faults, assign backing store, initialize (possibly
  to computed value, not always 0)
o unmap pages, unassign backing store, but retain address space
o read protect pages (ideally, still permitting writes)
o write protect pages and/or be able to examine "dirty" bits
o pre-process pages that are candidates for page-out
o mark pages as "clean" (to avoid page-out of stale data)
o handle protection faults, possibly by simulating the read
  or write in software
o be able to "peek" at protected pages (e.g., have a priviledged thread)
o find out what pages are resident and non-resident
o pre-fetch and post-purge non-resident pages
o remap pages from one virtual address to another

Note that most O/S's have a relatively expensive mechanism for user-code
handling faults (on the order of 500 instructions).  I'd like to see a
much speedier fault-handling mechanism.  It might mean that to achieve 
this
GC code would have to be more tightly integrated with the kernel rather
than operating as user code.  Similarly for access to O/S data structures
or state info such as page status (mapped/un, resident/non, dirty/clean,
protection mode, etc.)

Also note that the Lisp Machines used a page table structure that was 
particularly suited to large, sparsely mapped virtual images.  Even 
modern O/S's tend to still do poorly on this.  The typical multi-level 
page table has fixed size tables at each level and a sparse mapping tends 
to cause the entire table to be built even though little of it is used.  
In the worst case, the page table itself may be paged out because it is 
so large.  Unfortunately, many modern CPUs have hard-wired this type of 
page table.

The LispM page table (sometimes called an inverted page table) consisted 
of a hash table sized to physical memory keyed by virtual address, backed 
by a b-tree.  The Alpha chip is one modern CPU that does not have a 
hard-wired page table format and could probably support such a structure.