head     1.1;
access   ;
symbols  ;
locks    ; strict;
comment  @# @;


1.1
date     89.08.08.12.58.23;  author dld;  state Exp;
branches ;
next     ;


desc
@@



1.1
log
@Initial revision
@
text
@STORAGE ALLOCATION:

alloc(int words) {
  if (it is smaller than the breakage_threshold && free list exists) {
    use head of free list;
    if (that makes head of free_list smaller than breakage_threshold) {
      pop head of free_list;
    }
  } elseif (it will fit on the current page) {
    do it;
  } else {
    if (there is less than breakage_threshold left on current page) {
      set current_page to next free page;
    }
    if (can fit on the next set of contiguous pages) {
      do that;
    } else {
      if (abandoned part of current page > breakage_threshold)
	push it on free list;
      find a set of contiguous pages that it will fit on;
      if (none exists) give an error;
      else use the set found;
    }
    current page becomes last partially allocated page;
  }
}
      

COLLECTION:

How to handle late promotion?  Problem is that the object may have been
copied before we decide that the page it lives on needs to be promoted.

Possible Solution:
Have a fixed size array of pointers to slots containing unsure references.
Have the allocation function that takes a scan function find the unsure
offsets, record the resulting pointers in this array.

Problem:
What happens when this array gets full?  One possibility: do the collection
then.  Another:  realloc the array.  Another: record overflow, do different
kind of GC.  Could work with a mark-and-sweep algorithm?


Restatement of Bartlett's solution for late promotion:

1) Set promoted flag in each page reference by the root.
2) Do copying collection, without correcting pointers in new-space
objects, promoting pages when unsure references are found.  Leave
forwarding pointers.
3) Re-traverse new-space, correcting pointers:
   If references promoted page, do nothing, else follow forwarding pointer.
4) Traverse promoted pages, restoring data overwritten with forwarding
pointers.

Refinements:

In step 1):
  mark a bit in each referenced object on a promoted page.
In step 2):
  a) only scan marked objects in initial set of promoted pages.
  b) if a pointer to an object on a promoted page is found, don't
     copy.  If it is marked, do nothing, otherwise mark it and
     recursively scan (not a no-no, because it requires a lot of
     promoted pages to blow up.)
  c) if an unsure reference is found:
     i) promote the page it refers to.
     ii) mark the object
     iii) recursively scan.
In step 3):
  Traverse new-space & promoted pages.
  If the page is not promoted:
    a) for each object, correct pointers.
  Otherwise, it is promoted.
    b) for each marked object:
       i) if the object has a forwarding pointer, restore its object
          header.
       ii) correct its pointers.
    c) make the page part of new-space.

"correct" does
  if the pointer points outside the heap, OK.
  if the pointer points to a new or promoted page, OK.
  otherwise, it points at a current-space page.
    If it points to a valid object, that object should have a
      forwarding pointer.  If not, belly up.
    Update pointer according to forwarding pointer.



@
