[GHC] #15665: Break up the stable pointer table

[GHC]

#15665: Break up the stable pointer table
-------------------------------------+-------------------------------------
        Reporter:  dfeuer            |                Owner:  (none)
            Type:  feature request   |               Status:  new
        Priority:  normal            |            Milestone:  8.6.1
       Component:  Compiler          |              Version:  8.4.3
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:  #7670             |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by dfeuer):

 This stream of consciousness has gotten a bit long. So here's a bit of a
 consolidation of my proposed implementation:

 Stable pointers are managed in blocks. Each block belongs (at any given
 time, anyway) to at most one capability. That capability is the only one
 that allocates stable pointers in the block.

 Each block contains a table of entries, as many non-free lists (doubly
 linked stacks) as there are GC generations, a free list (singly linked),
 and a maintenance list (a read stack and a write stack, each singly
 linked).

 An entry consists of a pointer and two half-word fields. An entry cycles
 through three states: live, marked deleted, and free. In any non-free
 entry, the half-word fields point to the previous and next non-free
 entries in the generation. In a live entry, the pointer points into the
 Haskell heap. In a marked-deleted entry, the pointer points to the next
 entry in the maintenance list. In a free entry, the pointer points to the
 next entry in the free list, and the half-word fields are unused.

 === Allocation into a block

 If there is an entry on the free list, remove it from the free list,
 populate its pointer, and add it to the non-free list in its generation.
 Otherwise, perform a maintenance step to free an entry and use it.

 === Deletion

 To delete a block, add it to the maintenance list. This can be done with a
 CAS loop by any thread.

 === Maintenance

 If the read end of the maintenance list is empty, use an exchange
 operation to remove the write end and then install it as the read end (we
 don't care too much about order). Pop an entry off the read end,
 physically delete it from the non-free list, and (unless it is needed
 immediately) as it to the free list.

 === Garbage collection

 Traverse the read end of the maintenance list performing maintenance.
 Exchange out the write end and do the same. The maintenance list may
 continue to grow during collection; that will be cleaned up later. The
 purpose of performing maintenance during GC is to avoid having to traverse
 the same deleted entries over and over when there isn't much stable
 pointer allocation.

 Traverse the non-free list for the current generation. Do whatever's
 needed to mark and update the pointers in live entries.

 === Block management

 Most of the open questions are here. I'll leave them out of this comment.

-- 
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/15665#comment:12>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler