This file explains the concurrency control scheme used in libcGc.

There are 6 resources that may be accessed concurrently, each
protected by a mutex:

1.  The mutator allocation point.  Only one mutator threads is allowed
to do allocation at a time.  This is ensured by locking
'mut_alloc_pt.lock.'

2.  The gc allocation point.  The main gc thread modifies this, but
gc-wait threads need to look at it.  Protected by 'gc_alloc_pt.lock.'

3.  The variable 'roots_scanned.'  The mutator task reads this while the
Gc task may write it.  Protected by 'roots_scan_lock.'

4.  The 'scanned' field of page_data entries.  Gc_wait threads read
this while the the main gc thread may write it.  Protected by
'pd_scanned_lock.'

5.  The "new space queue."  Both Gc_wait threads and the main gc
thread may read and modify this concurrently.  Protected by 'nsq_lock.'

6.  The "free page ring."  Mutator threads and the main gc thread lock
this to get new free pages.  Protected by the 'free_ring_lock.'


To prevent deadlock, I will assign a precedence to each lock, and require
that all threads dynamically obtain locks in the order indicated by
this precedence; that is, if a thread ever holds multiple locks, they
were obtained in precedence order (low precedence numbers first.)

First, I will list the maximal sets of locks that need to be held at
one time by any threads:

Mutator thread:
{ mut_alloc, free_ring, roots_scanned }

Gc-wait thread:
{ pd_scanned, gc_alloc }, { pd_scanned, nsq }

Gc-main thread:
  gc_task:
    { gc_alloc, free_ring }
    page_allocate WL free_ring, gc_alloc_pt
    
  scan_page_set:
    { pd_scan }
    nsq_enq WL pd_scan

  scan_page:
    { pd_scan }

  copy_obj_if_necessary:
    { pd_scan }
    nsq_enq WL pd_scan

  internal_alloc:
    { gc_alloc_pt }
    alloc_at_free_list_head WL gc_alloc_pt
    alloc_on_cur_page WL gc_alloc_pt
    tot_allocated_pages WL gc_alloc_pt
    expand_heap WL gc_alloc_pt
    alloc_multi_page WL gc_alloc_pt

  alloc_multi_page:
    { free_ring }
    find_contig_block WL free_ring
    page_allocate WL free_ring

  page_allocate:
    { pd_scan }
    nsq_enq WL pd_scan

  expand_heap:
    { free_ring }

  init:
    { mut_alloc_pt, free_ring }

  promote_page:
    { pd_scan }
    nsq_enq WL pd_scan

  collect_newly_free
    { free_ring }
    check_gc_invariants WL free_ring

  nsq_enq:
    { nsq_lock }

  nsq_deq:
    { nsq_lock }

  nsq_move_to_front:
    { nsq_lock }

  rep_inv:
    { free_ring, nsq_lock }

  check_gc_invariants
    { mut_alloc_pt }

Now, if I follow the call chains and "collapse the upwards" (wave
hands, wave hands) I get the following maximal sets.

  gc_task:
    { gc_alloc, free_ring, pd_scan, nsq_lock }
    
  internal_alloc:
    { gc_alloc_pt, free_ring, pd_scan, nsq_lock }

*    tot_allocated_pages WL gc_alloc_pt
     (tot_allocated_pages should require { gc_alloc_pt, mut_alloc_pt }

  collect_newly_free:
    { free_ring, mut_alloc_pt }


So gc_alloc, free_ring, pd_scan, and nsq_lock need to be totally
ordered.  The precedence order has to respect the "calls with lock"
constraints:

{ free_ring, gc_alloc } < { pd_scan, nsq_lock }      	(from gc_task)
pd_scan < nsq_lock				(from scan_page_set, for one.)
gc_alloc < free_ring				(from internal_alloc)
free_ring < { pd_scan, nsq_lock }		(from alloc_multi_page)
mut_alloc < free_ring				(from internal_alloc calls
						 page allocate.)
mut_alloc < roots_scanned			(from internal_alloc calls
						 collect)

The following is a precedence that satisfies these constraints:

gc_alloc: 	1
free_ring:	2
mut_alloc:	3
roots_scanned:	4
pd_scan:	5
nsq_lock:	6