#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