implementation.lyx

#LyX 2.2 created this file. For more info see http://www.lyx.org/
\lyxformat 508
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass extreport
\use_default_options true
\begin_modules
fixltx2e
fix-cm
theorems-ams-bytype
\end_modules
\maintain_unincluded_children false
\language british
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date true
\justification true
\use_refstyle 1
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 1
\paragraph_separation indent
\paragraph_indentation default
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\listings_params "basicstyle={\ttfamily\small}"
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Chapter
\start_of_appendix
\begin_inset CommandInset label
LatexCommand label
name "chap:Runtime-Implementation"

\end_inset

Runtime Implementation
\end_layout

\begin_layout Standard
The implementation of the ideas presented in this thesis, in the form of
 the Pony compiler and the Pony runtime, represents a significant amount
 of software engineering as well as a certain amount of systems research.
 The purpose of this appendix is to serve as a guide to some of the subtler
 aspects of the implementation of the Pony runtime library.
 The elements of the runtime explained here are those most influenced by
 the type system and garbage collection work that represent the bulk of
 this thesis.
 The dissection of the subtler aspects of the Pony compiler is left as an
 exercise for the reader.
\end_layout

\begin_layout Section
Component Architecture
\end_layout

\begin_layout Standard
The Pony runtime consists of several core components.
 Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Runtime-architecture"

\end_inset

 shows the structure of those components.
 At the bottom is the pool allocator, which handles memory allocation and
 deallocation.
 On top of this is built the Single-Producer Multiple-Consumer (SPMC) queue,
 the Multiple-Producer Single-Consumer (MPSC) queue, and the page map.
 SPMC and MPSC queues are used to build the scheduler, an MPSC queue is
 used to build the asynchronous I/O handler, and the page map is used to
 build per-actor heaps.
 Another MPSC queue and the heap are used to build the actors themselves,
 which depend on both the scheduler and the asynchronous I/O handler.
 Tracing garbage collection (GC), sharing GC, and actor GC are built on
 top of actors, heaps, the page map, and the pool allocator.
\end_layout

\begin_layout Standard
Sharing GC, as described in chapter 
\begin_inset CommandInset ref
LatexCommand ref
reference "chap:Object-Collection"

\end_inset

, uses tracing GC during message send and receive.
 Actor GC, as described in chapter 
\begin_inset CommandInset ref
LatexCommand ref
reference "chap:Actor-Collection"

\end_inset

, relies on sharing GC in order to track implicit references from some actor
 
\begin_inset Formula $\alpha_{1}$
\end_inset

 to some actor 
\begin_inset Formula $\alpha_{2}$
\end_inset

 that arise due to 
\begin_inset Formula $\alpha_{1}$
\end_inset

 having a reference to some object 
\begin_inset Formula $\omega$
\end_inset

 that is owned by 
\begin_inset Formula $\alpha_{2}$
\end_inset

, as shown in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Reachability"

\end_inset

.
 In addition, tracing GC invokes sharing GC when objects owned by other
 actors are encountered during the trace.
\end_layout

\begin_layout Standard
\begin_inset Float figure
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename graphics/graphics.001.png
	width 50col%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Runtime-architecture"

\end_inset

Runtime architecture
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
Every component's design is influenced by the type system.
 This influence is particularly felt in the garbage collection components,
 but the impact is felt at every level, including the memory allocator.
\end_layout

\begin_layout Section
Naming Conventions
\end_layout

\begin_layout Standard
The Pony runtime is implemented in C, and maintains a C API and ABI in order
 to be usable from programming languages other than Pony.
 To avoid conflicts with symbols exported from other libraries, functions
 and types intended to be used at the language level are prefixed with 
\family typewriter
pony_
\family default
, while functions intended to be used only internally by the runtime itself
 are prefixed with 
\family typewriter
ponyint_
\family default
.
 Types that are only used internally have no prefix, since they do not appear
 in the symbol table or any publicly accessible header, and so do not cause
 conflicts.
\end_layout

\begin_layout Section
Pool Allocator
\end_layout

\begin_layout Standard
General purpose memory allocation is a complex problem.
 Manual memory management allocators have seen significant research in malloc-li
ke allocators that scale better as core counts increase, including 
\family typewriter
tcmalloc
\family default

\begin_inset CommandInset citation
LatexCommand cite
key "ghemawat2009tcmalloc"

\end_inset

, 
\family typewriter
jemalloc
\family default

\begin_inset CommandInset citation
LatexCommand cite
key "evans2011scalable"

\end_inset

, the 
\family typewriter
Intel TBB
\family default
 allocator
\begin_inset CommandInset citation
LatexCommand cite
key "reinders2007intel"

\end_inset

, and most recently 
\family typewriter
scalloc
\family default

\begin_inset CommandInset citation
LatexCommand cite
key "aigner2015fast"

\end_inset

.
 This category of memory allocator faces several related problems: finding
 free memory large enough to fulfil the requested allocation size without
 wasting excessive memory, coalescing freed memory to allow larger allocations
 to reuse memory from multiple smaller freed memory blocks, and coordinating
 allocation across threads.
 Similar problems emerge with automatic memory management allocators, with
 the additional complication that the garbage collector must interact with
 the allocator, and that a compacting garbage collector may move objects
 in memory.
\end_layout

\begin_layout Standard
The Pony memory allocator is divided into three parts: an underlying pool
 allocator, a page map, and a heap implementation built on top.
 We'll begin by examining the pool allocator.
 It is important to note that the pool allocator is not directly used for
 language-level allocation.
 That is, when a new object is allocated in Pony, it is allocated from the
 currently executing actor's heap, rather than directly from the pool allocator.
 The pool allocator is used for runtime data structures, including actor
 heaps themselves.
\end_layout

\begin_layout Standard
To reduce contention, the pool allocator operates as a thread-local allocator.
 When we examine the scheduler, we'll see that this results in each core
 having a pool allocator that is pinned to that core.
 This pool allocator is responsible for pulling new pages from the kernel
 when necessary, managing size classed free lists, and making free lists
 available to other thread-local pool allocators when possible.
\end_layout

\begin_layout Standard
When a pool allocator is asked to allocate memory, it tries three sources,
 in order:
\end_layout

\begin_layout Enumerate
The thread-local size classed free list for amount of memory requested,
 rounded to the next higher size class.
\end_layout

\begin_layout Enumerate
The global size classed list of free lists for that size class, which is
 used to prevent producer-consumer allocation starvation.
\end_layout

\begin_layout Enumerate
The thread-local free block.
\end_layout

\begin_layout Enumerate
The operating system, by allocating new pages.
\end_layout

\begin_layout Subsection
Size Classes
\end_layout

\begin_layout Standard
Size classes are used to simplify free list management.
 This approach segregates free lists by the size of the allocation, and
 limits the available allocation sizes.
 The implementation currently uses power-of-two sized classes ranging from
 
\begin_inset Formula $2^{5}$
\end_inset

 to 
\begin_inset Formula $2^{20}$
\end_inset

 bytes, but these values are easily tuneable.
 Allocations exceeding the largest size class begin with the thread-local
 free block.
\end_layout

\begin_layout Standard
Such segregated free lists have a cost, in that allocations sizes are rounded
 up to a size class.
 For example, using power-of-two size classes, a 65 byte allocation request
 will instead allocate 128 bytes.
 However, in return, allocations do not require that memory in the allocated
 block be used to indicate the allocated size, and allocations are always
 cache line aligned.
\end_layout

\begin_layout Standard
In addition, no free list searching is required on allocation.
 Using the head of the free list for a size class approximates a best-fit
 search of all free memory, which improves memory utilisation and reduces
 fragmentation.
\end_layout

\begin_layout Subsection
Thread-local Size Classed Free List
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

typedef struct pool_item_t {
\end_layout

\begin_layout Plain Layout

  struct pool_item_t* next;
\end_layout

\begin_layout Plain Layout

} pool_item_t; 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:A-thread-local-free"

\end_inset

A thread-local free list node
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
Each pool allocator keeps a linked list of free memory for each size class.
 Initially, these free lists are empty, which is encoded as a 
\family typewriter
null
\family default
 pointer.
\end_layout

\begin_layout Standard
When the pool allocator is told to free memory within a size class, it prepends
 that memory to the appropriate free list.
 The memory being freed is reused as the linked list node, so that there
 is no memory overhead associated with free memory, as shown in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:A-thread-local-free"

\end_inset

.
\end_layout

\begin_layout Standard
The memory is prepended, following a last-in first-out strategy, in order
 to improve cache locality: if memory of that size class is quickly allocated
 and used again, it is more likely that the memory remains in cache.
\end_layout

\begin_layout Standard
When memory is freed to a thread-local free list, the provenance of the
 memory is not examined.
 Any pool allocator can place memory allocated by any other pool allocator
 on its thread-local free list for that size class.
 As a result, it is not necessary to perform any checks as to the origin
 of memory when it is freed.
 This differs from 
\emph on
arena
\emph default
 based allocators, such as 
\family typewriter
jemalloc
\family default

\begin_inset CommandInset citation
LatexCommand cite
key "evans2011scalable"

\end_inset

, that must return free memory to the allocating arena.
 For the Pony runtime, this behaviour is critical, as it allows both runtime
 data structures and heap chunks to be efficiently freed regardless of which
 thread an actor executes on.
 On the other hand, this approach makes coalescing free memory, either to
 reuse as a different size class or to return to the operating system, more
 difficult.
 The pool allocator relies on a stable state for a program rather than coalescin
g, which is problematic for some applications.
\end_layout

\begin_layout Subsection
Global List of Size Classed Free Lists
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

typedef struct pool_central_t {
\end_layout

\begin_layout Plain Layout

  pool_item_t* next;
\end_layout

\begin_layout Plain Layout

  uintptr_t length;
\end_layout

\begin_layout Plain Layout

  struct pool_central_t* central; 
\end_layout

\begin_layout Plain Layout

} pool_central_t; 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:A-global-list"

\end_inset

A global list of free lists node
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
The system as a whole also keeps a single global list of free lists for
 each size class.
 This is to avoid memory starvation in a producer-consumer scenario where
 one scheduler thread is consistently allocating memory and another scheduler
 thread is consistently freeing it.
\end_layout

\begin_layout Standard
When a thread-local free list exceeds a certain size, defaulting to 
\begin_inset Formula $2^{20}$
\end_inset

 bytes, that free list is pushed to a global list of free lists.
 The maximum size of a thread-local free list is a global compile-time constant,
 rather than being adaptive.
 It is possible that an adaptive approach could yield additional performance
 benefits, at the cost of evaluating some heuristic.
\end_layout

\begin_layout Standard
The first linked list node in the thread-local free list is reinterpreted
 as the first node in a global list of lists.
 This involves reusing available space in the node 
\emph on
after
\emph default
 the pointer to the next node in the thread-local free list to record both
 the length of the current list and a pointer to the next global list, as
 shown in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:A-global-list"

\end_inset

.
 Note that a 
\family typewriter
pool_central_t
\family default
 maintains the same initial structure as a 
\family typewriter
pool_item_t
\family default
.
\end_layout

\begin_layout Standard
To make this possible, the minimum allocation size must be sufficient to
 hold all three values, i.e.
 24 bytes in a 64-bit runtime or 12 bytes in a 32-bit runtime.
 The minimum allocation size is a compile-time constant that defaults to
 32 bytes.
\end_layout

\begin_layout Standard
An atomic compare-and-swap loop is used to change the global list of free
 lists pointer for the size class being pushed, so that any number of pool
 allocators can safely attempt to push a free list to the global list of
 lists simultaneously.
\end_layout

\begin_layout Standard
Similarly, when a pool allocator's thread-local free list is empty, it examines
 the global list of free lists.
 Crucially, if that global list is empty, which is encoded as a 
\family typewriter
null
\family default
 pointer, no atomic operation is required, and the pool allocator tries
 its next source of free memory.
 If the global list of free lists contains one or more lists, an atomic
 compare-and-swap loop is used to remove one list from global list.
 That list is then used as the thread-local free list, allowing memory to
 be returned immediately.
\end_layout

\begin_layout Subsection
Thread-local Free Block
\end_layout

\begin_layout Standard
A pool allocator also keeps a thread-local free block.
 This is a list of free memory, insert-sorted by size, that is initially
 empty.
 If no size classed memory is available, the first free block in this list
 large enough to fulfil the allocation is used.
 If a block is available, it is fragmented into the requested size and any
 remaining memory, with any remaining memory being insert-sorted back into
 the free block.
\end_layout

\begin_layout Standard
This approach allows large allocations to be reused for future large allocations
, or fragmented into future size classed allocations.
 It also allows freed large allocations to coexist with new pages pulled
 from the operating system.
\end_layout

\begin_layout Subsection
New Pages
\end_layout

\begin_layout Standard
If the thread-local and global size classed pools are empty, and the free
 block is either empty or contains no memory block large enough to fulfil
 the allocation request, the pool allocator uses an underlying system call
 (
\family typewriter
mmap
\family default
 on UNIX-like operating systems, 
\family typewriter
VirtualAlloc
\family default
 on Windows) to request a number of pages mapped as a contiguous chunk of
 address space.
 Some empirical testing with various work loads has lead to choosing a 128
 megabyte chunk in a 64-bit address space and a 16 megabyte chunk in a 32-bit
 address space as the default.
 These values can be easily changed in the runtime.
\end_layout

\begin_layout Standard
This address space is mapped using huge pages, where available, to minimise
 the number of address translations, reducing pressure on the translation
 lookaside buffer (TLB).
 This also reduces the TLB lookup pressure on the L2 cache, leaving more
 cache for application data.
 However, this address space is not pre-faulted.
 That is, no data is written to the mapped address space.
 This prevents unused pages from being mapped to physical memory, and significan
tly reduces allocation-time jitter, particularly on NUMA machines.
\end_layout

\begin_layout Standard
The mapped address space is then fragmented into the requested allocation
 size and any remaining size, with the remaining memory kept in the thread-local
 free block for future allocations.
\end_layout

\begin_layout Subsection
Fragmentation
\end_layout

\begin_layout Standard
The pool allocator as currently implemented has no mechanism for coalescing
 free memory.
 As a result, small allocations can result in fragmentation, such that free
 memory is available, but a request for a single large contiguous address
 space fails.
\end_layout

\begin_layout Standard
This deficiency is addressed in the per-actor heap, rather than in the pool
 allocator, as explained in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Small-Allocation-Fragmentation"

\end_inset

.
 This allows the pool allocator itself to avoid jitter caused by attempting
 to coalesce free memory.
\end_layout

\begin_layout Standard
A key area of future work is to add a coalescing mechanism for pool allocator
 fragmentation that does not overly adversely affect common cases that do
 not require coalescing, such as repeatedly allocating and freeing buffers
 used for I/O operations.
 In particular, the page map (see section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Page-Map"

\end_inset

) can be extended to cheaply track free contiguous allocations.
 The challenge is to cheaply coalesce these even when they are allocated
 and freed by different threads.
\end_layout

\begin_layout Standard
Allocations that exceed the size class limit of the pool allocator are added
 to the insert-sorted list of free blocks for the local pool allocator.
 For these very large allocations, the pool allocator performs no better
 than existing allocators.
\end_layout

\begin_layout Subsection
Role of the Type System
\end_layout

\begin_layout Standard
The type system has an indirect effect on the design of the pool allocator.
 The use of size classed allocations that do not record their size within
 the allocated memory is made possible because the program always knows
 the size of any memory being freed.
 This approach, which does not conform to the 
\family typewriter
malloc
\family default
 interface, could be used seamlessly in any language that knows allocation
 sizes, either statically or dynamically.
 It can also be used in languages where sizes are not known if the program
 explicitly tracks allocation sizes.
 For example, the Pony compiler, although implemented in 
\family typewriter
C
\family default
, uses the pool allocator.
\end_layout

\begin_layout Section
\begin_inset CommandInset label
LatexCommand label
name "subsec:Page-Map"

\end_inset

Page Map
\end_layout

\begin_layout Standard
The runtime keeps a radix tree (two-level on 32-bit architectures, three-level
 on 64-bit architectures).
 Page map levels are described in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Page-map-levels"

\end_inset

.
 The bottom level of the radix tree refers to 
\begin_inset Formula $2^{10}$
\end_inset

 byte regions, allowing the page map to associate a pointer to a chunk descripto
r with each one.
 These regions are the 
\emph on
pages
\emph default
 for the Pony runtime, although they are smaller than either the standard
 (4 kilobyte) or huge (2 megabyte) pages used by some CPUs, such as 
\family typewriter
ARM64
\family default
 and 
\family typewriter
x86
\family default
.
 Using a radix tree allows the page map to associate a pointer with every
 
\begin_inset Formula $2^{10}$
\end_inset

 byte region with a total memory overhead of 0.39% on a 32-bit architecture,
 or 0.78% on a 64-bit architecture.
\end_layout

\begin_layout Standard
The alignment of the memory areas managed by chunks, as described in section
 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Heaps"

\end_inset

, is exploited to give a simple mask-based lookup to find the chunk descriptor
 for any address.
 This is used during garbage collection to find the chunk descriptor for
 an object, as detailed in sections 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Tracing-GC"

\end_inset

 and 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Sharing-GC"

\end_inset

.
\end_layout

\begin_layout Standard
A page map is used rather than embedding a chunk descriptor in allocated
 memory as an allocation header.
 Doing so significantly reduces the memory overhead for small allocations,
 as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Small-Allocation"

\end_inset

.
 In addition, it allows the runtime to allocate and garbage collect objects
 that conform to 
\family typewriter
C/C++
\family default
 layout conventions on a particular platform, which is important for an
 efficient foreign function interface.
 Pony also follows these platform specific layout conventions.
\end_layout

\begin_layout Standard
The page map is a global rather than a thread-local data structure, with
 the root of the page map being a single global pointer.
 Because it can be written to for any allocation, and is read from during
 garbage collection, thread contention must be minimised.
\end_layout

\begin_layout Standard
In figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Reading-from-the"

\end_inset

, we see that page map reads require no thread coordination and no atomic
 operations.
 In figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Writing-to-the"

\end_inset

, we see that writing to the page map may result in a non-looping atomic
 compare-and-swap.
 This is used to extend the page map.
 This results in worst case behaviour of three atomic instructions on write,
 which happens only when the page map is entirely empty.
 The common case involves no atomic instructions and no thread coordination.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

typedef struct pagemap_level_t {
\end_layout

\begin_layout Plain Layout

  int shift;
\end_layout

\begin_layout Plain Layout

  int mask;
\end_layout

\begin_layout Plain Layout

  size_t size;
\end_layout

\begin_layout Plain Layout

  size_t size_index;
\end_layout

\begin_layout Plain Layout

} pagemap_level_t; 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Page-map-levels"

\end_inset

Page map levels
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

void* pagemap_get(const void* m) {
\end_layout

\begin_layout Plain Layout

  void** v = root;
\end_layout

\begin_layout Plain Layout

  for(int i = 0; i < PAGEMAP_LEVELS; i++) {
\end_layout

\begin_layout Plain Layout

    if(v == NULL)
\end_layout

\begin_layout Plain Layout

      return NULL;
\end_layout

\begin_layout Plain Layout

    uintptr_t ix = ((uintptr_t)m >> level[i].shift)
\end_layout

\begin_layout Plain Layout

      & level[i].mask;
\end_layout

\begin_layout Plain Layout

    v = (void**)v[ix];
\end_layout

\begin_layout Plain Layout

  }
\end_layout

\begin_layout Plain Layout

  return v;
\end_layout

\begin_layout Plain Layout

} 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Reading-from-the"

\end_inset

Reading from the page map
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

void pagemap_set(const void* m, void* v) {
\end_layout

\begin_layout Plain Layout

  void*** pv = &root;
\end_layout

\begin_layout Plain Layout

  void* p;
\end_layout

\begin_layout Plain Layout

  for(int i = 0; i < PAGEMAP_LEVELS; i++) {
\end_layout

\begin_layout Plain Layout

    if(*pv == NULL)
\end_layout

\begin_layout Plain Layout

    {
\end_layout

\begin_layout Plain Layout

      p = pool_alloc(level[i].size_index);
\end_layout

\begin_layout Plain Layout

      memset(p, 0, level[i].size);
\end_layout

\begin_layout Plain Layout

      void** prev = NULL;
\end_layout

\begin_layout Plain Layout

      if(!_atomic_cas(pv, &prev, p))
\end_layout

\begin_layout Plain Layout

      {
\end_layout

\begin_layout Plain Layout

        pool_free(level[i].size_index, p);
\end_layout

\begin_layout Plain Layout

        *pv = prev;
\end_layout

\begin_layout Plain Layout

      }
\end_layout

\begin_layout Plain Layout

    }
\end_layout

\begin_layout Plain Layout

    uintptr_t ix = ((uintptr_t)m >> level[i].shift)
\end_layout

\begin_layout Plain Layout

      & level[i].mask;
\end_layout

\begin_layout Plain Layout

    pv = (void***)&((*pv)[ix]);
\end_layout

\begin_layout Plain Layout

  }
\end_layout

\begin_layout Plain Layout

  *pv = (void**)v;
\end_layout

\begin_layout Plain Layout

} 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Writing-to-the"

\end_inset

Writing to the page map
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Role of the Type System
\end_layout

\begin_layout Standard
The type system does not allow the allocating actor for an object to be
 known statically.
 As a result, when the allocating actor is needed, for example during garbage
 collection as detailed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Determining-Ownership"

\end_inset

, it must be determined dynamically.
 The page map provides an efficient way to do this.
\end_layout

\begin_layout Standard
The page map points to a chunk descriptor, which in turn points to the allocatin
g actor, in order to allow the size class for an arbitrary pointer to memory
 to be determined.
 This allows internal pointers to be easily distinguished from external
 pointers, and allows the runtime to efficiently determine the external
 pointer for any internal pointer.
 This is used to distinguish between deep and shallow marking, as shown
 in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Deep-vs.-Shallow"

\end_inset

.
\end_layout

\begin_layout Section
\begin_inset CommandInset label
LatexCommand label
name "sec:Heaps"

\end_inset

Per-Actor Heaps
\end_layout

\begin_layout Standard
All memory allocated by the runtime is handled by the thread-local pool
 allocator.
 This includes all runtime data structures that are not visible to the program,
 such as message queue nodes, scheduler queue nodes, and garbage collection
 management data, as well as memory allocated for actors themselves.
 However, when an actor allocates objects, it does so via a per-actor heap,
 rather than by using the pool allocator directly.
\end_layout

\begin_layout Standard
Each actor has its own heap, composed of lists of size classed chunks, a
 list of oversized chunks, and information used to determine if the heap
 may be in need of garbage collection, as shown in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:A-heap"

\end_inset

.
 Each standard chunk is a 
\begin_inset Formula $2^{10}$
\end_inset

 byte area of contiguous memory that is used to allocate multiple objects,
 each of the same size.
 An oversized chunk is an area of contiguous memory larger than 
\begin_inset Formula $2^{10}$
\end_inset

 bytes that is used to allocate a single large object.
 In both cases, an allocation may represent an array of objects as well
 as a single object.
 An allocation is a 
\emph on
small allocation
\emph default
 if it is less than the standard chunk size, otherwise it is a 
\emph on
large allocation
\emph default
.
\end_layout

\begin_layout Standard
A chunk descriptor is a small (24 bytes on a 32-bit architecture, 40 bytes
 on a 64-bit architecture) structure that stores the owning actor for chunk
 (i.e.
 the actor whose heap the chunk is associated with), a base memory address,
 a size class or byte size, and garbage collection information, as shown
 in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:A-chunk-descriptor"

\end_inset

.
 Chunk descriptors are used for both small allocations and large allocations.
\end_layout

\begin_layout Standard
The garbage collection information is contained in the 
\family typewriter
slots
\family default
 and 
\family typewriter
shallow
\family default
 fields.
 The use of these fields as bitmaps of free memory, and the need for separate
 fields, will be discussed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Deep-vs.-Shallow"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

typedef struct heap_t {
\end_layout

\begin_layout Plain Layout

  chunk_t* small_free[HEAP_SIZECLASSES];
\end_layout

\begin_layout Plain Layout

  chunk_t* small_full[HEAP_SIZECLASSES];
\end_layout

\begin_layout Plain Layout

  chunk_t* large;
\end_layout

\begin_layout Plain Layout

  size_t used;
\end_layout

\begin_layout Plain Layout

  size_t next_gc;
\end_layout

\begin_layout Plain Layout

} heap_t; 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:A-heap"

\end_inset

A heap
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

typedef struct chunk_t {
\end_layout

\begin_layout Plain Layout

  // immutable
\end_layout

\begin_layout Plain Layout

  pony_actor_t* actor;
\end_layout

\begin_layout Plain Layout

  char* m;
\end_layout

\begin_layout Plain Layout

  size_t size;
\end_layout

\begin_layout Plain Layout

  // mutable
\end_layout

\begin_layout Plain Layout

  uint32_t slots;
\end_layout

\begin_layout Plain Layout

  uint32_t shallow;
\end_layout

\begin_layout Plain Layout

  struct chunk_t* next;
\end_layout

\begin_layout Plain Layout

} chunk_t; 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:A-chunk-descriptor"

\end_inset

A chunk descriptor
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Small-Allocation"

\end_inset

Small Allocation
\end_layout

\begin_layout Standard
A heap keeps two singly-linked lists of chunks for each small allocation
 size class.
 The first is a list of chunks with memory available for allocation, and
 the second is a list of chunks with no available memory.
 Initially, both lists are empty for every size class.
\end_layout

\begin_layout Standard
When the program requests memory less than the configured small allocation
 size (defaulting to 
\begin_inset Formula $2^{10}$
\end_inset

 bytes), the heap uses size classed memory to fulfil the allocation.
 The amount of requested memory is turned into a size class using a bit
 shift and a table lookup on a small (16-byte) static table, as in figure
 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Determining-a-size"

\end_inset

.
 The resulting size class index is then used to determine the correct linked
 list of chunks with free memory, also in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Determining-a-size"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

static const uint8_t sizeclass_table[] = {
\end_layout

\begin_layout Plain Layout

  0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4
\end_layout

\begin_layout Plain Layout

};
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

uint32_t heap_index(size_t size) {
\end_layout

\begin_layout Plain Layout

  return sizeclass_table[(size - 1) >> HEAP_MINBITS];
\end_layout

\begin_layout Plain Layout

}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Determining-a-size"

\end_inset

Determining a size class
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
The 
\family typewriter
small_free
\family default
 and 
\family typewriter
small_full
\family default
 lists are segregated to ensure that the heap never has to walk a linked
 list when allocating memory.
 To do so, an important invariant is maintained:
\end_layout

\begin_layout Definition
\begin_inset CommandInset label
LatexCommand label
name "def:Chunk-validity"

\end_inset

Chunk validity
\end_layout

\begin_deeper
\begin_layout Itemize
All chunks allocated by this heap with free space are in the 
\family typewriter
small_free
\family default
 list for their size class.
\end_layout

\begin_layout Itemize
All chunks allocated by this heap without free space are in the 
\family typewriter
small_full
\family default
 list for their size class.
\end_layout

\end_deeper
\begin_layout Standard
As a result, when an allocation for some size class is requested, it will
 come from the first element of the 
\family typewriter
small_free
\family default
 list, if there is one.
 Otherwise, a new chunk will be allocated and the allocation will come from
 this new chunk.
\end_layout

\begin_layout Standard
This invariant is important for performance.
 Without it, small allocation would be an 
\begin_inset Formula $O(n)$
\end_inset

 operation, with 
\begin_inset Formula $n$
\end_inset

 being the amount of memory allocated in a size class.
 By keeping segregated lists, small allocation is 
\begin_inset Formula $O(1)$
\end_inset

, with at most one pointer dereference at the heap level.
\end_layout

\begin_layout Subsection
Small Chunk Bitmaps
\end_layout

\begin_layout Standard
Each chunk keeps a bitmap of free memory addresses in the memory it manages.
 This is called 
\family typewriter
slots
\family default
 in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:A-chunk-descriptor"

\end_inset

.
 The default configuration uses a single 32-bit integer to map a 
\begin_inset Formula $2^{10}$
\end_inset

 byte memory area.
 This gives enough bits to describe free memory for a 32 objects of the
 minimum allocation size of 32 bytes, which is size class 
\family typewriter
0
\family default
.
 Similarly, a chunk can hold 16 objects with a 64 byte allocation size,
 which is size class 
\family typewriter
1
\family default
.
\end_layout

\begin_layout Standard
The bitmap uses set bits to indicate addresses in the memory area that are
 both free and valid for the size class, and unset bits to indicate addresses
 that are either in use or invalid for the size class.
 For example, using the default configuration, a chunk managing a 32 byte
 size class has an empty bitmap that consists of all bits being set, whereas
 a chunk managing a 64 byte size class has an empty bitmap consisting of
 every other bit being set.
\end_layout

\begin_layout Standard
To find a free and valid address, the runtime finds the first set bit in
 the bitmap (a cheap instruction on a modern processor), unsets the bit
 in the bitmap, and returns the base memory address offset by the bit position
 multiplied by the minimum allocation size, as in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Finding-free-small"

\end_inset

.
 Note that 
\family typewriter
__pony_ffs
\family default
 (
\begin_inset Quotes eld
\end_inset

find-first-set
\begin_inset Quotes erd
\end_inset

) is a cross-platform macro for the platform specific code that finds the
 first set bit.
 Also note that no conditional branches are required.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

uint32_t bit = __pony_ffs(chunk->slots) - 1;
\end_layout

\begin_layout Plain Layout

chunk->slots &= ~(1 << bit);
\end_layout

\begin_layout Plain Layout

void* m = chunk->m + (bit << HEAP_MINBITS);
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Finding-free-small"

\end_inset

Finding free small allocation memory
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Allocating on an Existing Chunk
\end_layout

\begin_layout Standard
When a small allocation is performed and there is a non-empty linked list
 of chunks with free memory for that size class, i.e.
 
\family typewriter
heap->small_free[sizeclass] != NULL
\family default
, the allocation can always be fulfilled using memory available in the first
 element of that linked list.
 That is, there is guaranteed to be at least one bit set in the chunk's
 bitmap.
\end_layout

\begin_layout Standard
If allocation results in all memory in the chunk being exhausted (i.e.
 there was only one bit set before allocation, and so no bits set after
 allocation), the chunk is moved from the linked list of chunks with available
 memory to the linked list of chunks with no available memory.
 This is a cheap operation: it involves popping the head of a singly-linked
 list and pushing it to the head of another singly-linked list.
 This maintains the chunk validity invariant in definition 
\begin_inset CommandInset ref
LatexCommand ref
reference "def:Chunk-validity"

\end_inset

.
\end_layout

\begin_layout Subsection
Allocating on a New Chunk
\end_layout

\begin_layout Standard
If there are no non-empty chunks for a given size class, the linked list
 head will be 
\begin_inset Formula $\mathtt{NULL}$
\end_inset

.
 This indicates that a new chunk is required, without a pointer dereference.
\end_layout

\begin_layout Standard
At this point, two pool allocations are required.
 The first is for a chunk descriptor, and the second is for the chunk itself,
 i.e.
 the memory area to be managed by the new chunk descriptor.
 These are allocated separately in order to maintain address alignment for
 memory areas (a requirement for the page map, as detailed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Page-Map"

\end_inset

) while also avoiding wasting memory.
 To illustrate the advantage of this approach, a 
\begin_inset Formula $2^{10}$
\end_inset

 byte memory area used for a 
\begin_inset Formula $2^{8}$
\end_inset

 byte size class has space for four objects.
 If the chunk descriptor were embedded in the chunk memory, it would use
 the space one object would otherwise occupy, which in this case would require
 using 
\begin_inset Formula $2^{8}$
\end_inset

 bytes to store the chunk descriptor.
 With split allocation, a chunk descriptor is a fixed size.
\end_layout

\begin_layout Standard
An additional concern is to keep chunk descriptors in separate cache lines
 from program data, and, where efficient, on separate operating system pages.
 This is important to reduce cache pollution and page faults during garbage
 collection, as detailed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Tracing-GC"

\end_inset

.
 The pool allocator ensures that chunk descriptors are cache-line aligned,
 and will prefer placing different size classes on separate operating system
 pages where practicable, accomplishing both goals.
\end_layout

\begin_layout Standard
The new chunk is initialised as an empty chunk and registered with the page
 map (c.f.
 section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Page-Map"

\end_inset

).
 As an optimisation, the first valid bit in 
\family typewriter
slots 
\family default
is initialised as unset, so that the base memory address for the chunk can
 be used to fulfil the allocation without first checking for the first set
 bit.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Small-Allocation-Fragmentation"

\end_inset

Small Allocation Fragmentation
\end_layout

\begin_layout Standard
A major concern in memory allocators is avoiding fragmentation.
 This problem has two manifestations: internal fragmentation and external
 fragmentation.
\end_layout

\begin_layout Standard
Internal fragmentation occurs when an allocator must return more memory
 than is requested by the application in order to fulfil an allocation.
 This can have two causes: headers related to the allocation itself (as
 opposed to object headers in the programming language) and the need to
 align memory.
\end_layout

\begin_layout Standard
Because the type system is integrated with the runtime, the Pony allocator
 does not require memory allocation headers, and so avoids the first problem
 on a per-object basis.
 However, a chunk descriptor is still required for each memory area.
 This descriptor is allocated separately from the memory area to avoid internal
 fragmentation, although it still imposes a worst case memory size overhead
 of 3.125% (32-bit architecture) or 6.25% (64-bit architecture).
 This overhead can be configured by using a chunk size larger than 
\begin_inset Formula $2^{10}$
\end_inset

 bytes.
 The trade off is that an actor reserves memory for future small allocations
 in these block sizes.
 If the actor does not perform those future allocations, some fraction of
 that space is wasted, although this is always less than the memory area
 size multiplied by the number of size classes (i.e.
 it is 
\begin_inset Formula $O(1)$
\end_inset

 rather than 
\begin_inset Formula $O(n)$
\end_inset

 on allocation count).
 
\end_layout

\begin_layout Standard
Internal fragmentation due to memory alignment is sometimes a net performance
 benefit, due to cache line alignment and machine word alignment (e.g.
 64-bit floating point or SSE data alignment).
 The Pony runtime aligns all small allocations on the size of the allocation
 to take best advantage of this.
 This creates a worst case internal fragmentation cost approaching 50%.
 For example, if all allocated objects in a program were 65 bytes, they
 would all be fulfilled with 128 byte allocations.
 Some allocators, 
\family typewriter
tcmalloc
\family default
 
\emph on
inter alia
\emph default
, use more finely grained size classes to reduce this form of internal fragmenta
tion.
 The trade off is that more data structure overhead is required to keep
 track of the size classes themselves.
 For a thread-specific allocator such as 
\family typewriter
tcmalloc
\family default
, this overhead is only multiplied by the number of threads in a program
 (where a large number is on the order of thousands), whereas for the Pony
 runtime, the overhead would be multiplied by the number of actors in a
 program (where a large number is on the order of tens of millions).
\end_layout

\begin_layout Standard
External fragmentation occurs when free memory is interspersed with allocated
 memory, resulting in a situation where sufficient memory is available to
 fulfil an allocation request, but that memory is non-contiguous, and the
 allocation fails.
 In a garbage collected language, this can be addressed with a compacting
 collector.
 Pony does not use a compacting collector, as explained in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Tracing-GC"

\end_inset

.
 Instead, external fragmentation is addressed in two ways: chunk bitmap
 management and pool allocator reuse.
\end_layout

\begin_layout Standard
By using a chunk bitmap, free memory of a given size class is reused when
 a new allocation occurs, without the need to search through or coalesce
 a free list.
 This addresses the most common cause of external fragmentation: repeated
 allocation and freeing of objects of a finite number of sizes in an interleaved
 manner.
 Essentially, space in a chunk is back-filled when new objects of that size
 class are allocated.
\end_layout

\begin_layout Standard
In addition, when all of the memory in a chunk is marked as free, that chunk
 descriptor and the memory area it manages are returned to the pool allocator.
 This allows a chunk to be reused for a different size class.
 As a result, repeated small allocations of any size are always defragmented,
 even if those allocations are temporally disparate or have an unpredictable
 layout.
 The worst case behaviour for a given size class is to free all but one
 object per chunk, preventing the chunk itself from being returned to the
 pool, without ever allocating additional memory in that size class.
 However, even this worst case is strictly bounded: any additional allocation
 in that size class will use memory available in the existing chunks.
\end_layout

\begin_layout Subsection
Large Allocation
\end_layout

\begin_layout Standard
When a program requests contiguous memory larger than the maximum size that
 can be handled by a small allocation, by default 
\begin_inset Formula $2^{10}$
\end_inset

 bytes, the heap performs a large allocation.
 This includes allocating a chunk descriptor and a single contiguous space
 for the full allocation, both using the underlying pool allocator.
 The requested contiguous memory area size is rounded up to be a multiple
 of the chunk size.
 This is done to allow large allocations that are later freed to be efficiently
 subdivided into chunks by the pool allocator if the pool allocator determines
 that doing so would be more efficient than pulling new pages from the operating
 system to fulfil an allocation request.
\end_layout

\begin_layout Standard
Aligning large allocations in this way also allows the memory used by a
 large allocation to be efficiently represented in the page map, as described
 in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Page-Map"

\end_inset

.
\end_layout

\begin_layout Standard
Unlike the chunk descriptors for small allocations, there is no list of
 chunk descriptors for large allocations that contain free space, as each
 large allocation is either entirely in-use or entirely free.
 When garbage collection determines that a large allocation is no longer
 required, both the chunk descriptor and the contiguous memory area is describes
 are returned to the pool allocator.
\end_layout

\begin_layout Standard
Large allocations occur primarily for contiguous arrays, including strings.
 It is unusual for a single object to require more than 
\begin_inset Formula $2^{10}$
\end_inset

 bytes of storage.
\end_layout

\begin_layout Subsection
Large Allocation Fragmentation
\end_layout

\begin_layout Standard
Since the contiguous memory areas required for large allocations are handled
 by the pool allocator, and each chunk descriptor represents a single allocation
, there is no chunk bitmap and no cross-size defragmentation performed by
 the heap.
 Instead, fragmentation is handled by the pool allocator.
\end_layout

\begin_layout Subsection
Role of the Type System
\end_layout

\begin_layout Standard
The type system distinguishes between active objects, in the form of actors,
 and passive objects.
 This allows the runtime to distinguish possibly concurrent allocations
 (i.e.
 those occurring in different actors) from allocations guaranteed to be
 sequential (i.e.
 those occurring in the same actor).
 Per-actor heaps allow both allocation and garbage collection without contention
, even when memory is shared by pointer across actors, as detailed in section
 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Sharing-GC"

\end_inset

.
\end_layout

\begin_layout Section
MPSC Queues
\end_layout

\begin_layout Standard
Each actor has its own message queue, and all messages to an actor are delivered
 through that single queue.
 A message queue can therefore be a bottleneck in a program, particularly
 if a program uses a pattern whereby many actors send messages to a single
 receiving actor.
\end_layout

\begin_layout Standard
In the Pony runtime, an actor's message queue is implemented as a multi-producer
 single-consumer (MPSC) queue.
 Any actor can push a message on to a queue, but only the owning actor can
 pop a message off the queue.
 The point of contention is the push, where many actors could simultaneously
 push messages to the same queue.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

bool ponyint_messageq_push(messageq_t* q, pony_msg_t* m) {
\end_layout

\begin_layout Plain Layout

  atomic_store_explicit(&m->next, NULL, memory_order_relaxed);
\end_layout

\begin_layout Plain Layout

  pony_msg_t* prev = atomic_exchange_explicit(&q->head, m, memory_order_relaxed)
;
\end_layout

\begin_layout Plain Layout

  bool was_empty = ((uintptr_t)prev & 1) != 0;
\end_layout

\begin_layout Plain Layout

  prev = (pony_msg_t*)((uintptr_t)prev & ~(uintptr_t)1);
\end_layout

\begin_layout Plain Layout

  atomic_store_explicit(&prev->next, m, memory_order_release);
\end_layout

\begin_layout Plain Layout

  return was_empty;
\end_layout

\begin_layout Plain Layout

} 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Pushing-to-a"

\end_inset

Pushing to a message queue
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

pony_msg_t* ponyint_messageq_pop(messageq_t* q) {
\end_layout

\begin_layout Plain Layout

  pony_msg_t* tail = q->tail;
\end_layout

\begin_layout Plain Layout

  pony_msg_t* next = atomic_load_explicit(&tail->next, memory_order_acquire);
\end_layout

\begin_layout Plain Layout

  if(next != NULL) {
\end_layout

\begin_layout Plain Layout

    q->tail = next;
\end_layout

\begin_layout Plain Layout

    ponyint_pool_free(tail->index, tail);
\end_layout

\begin_layout Plain Layout

  }
\end_layout

\begin_layout Plain Layout

  return next;
\end_layout

\begin_layout Plain Layout

} 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Popping-from-a"

\end_inset

Popping from a message queue
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
In figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Pushing-to-a"

\end_inset

, we see that pushing a message on to a queue is accomplished with a single
 atomic exchange operation (the atomic stores are logically atomic, but
 on most common architectures, e.g.
 X86, X86-64, AArch32, AArch64, et al., all stores are inherently atomic).
 Critically, there is no compare-and-swap loop or other waiting construct.
 As a result, sending a message is lock-free and wait-free.
 The use of the low bit for empty queue detection will be discussed in section
 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Empty-Queue-Detection"

\end_inset

.
\end_layout

\begin_layout Standard
In figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Popping-from-a"

\end_inset

, we see that popping a message from a queue is accomplished with zero atomic
 operations (the atomic load is logically atomic, but like the store when
 pushing, results in a normal load instruction on most common architectures),
 and without any loop or wait.
 This means that popping a message in order to begin a behaviour is lock-free,
 wait-free, and uses no atomic operations.
 The memory management of queue nodes is discussed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Queue-Node-Memory"

\end_inset

.
\end_layout

\begin_layout Standard
In addition to being a safe MPSC queue, an actor's queue must provide two
 additional features: it must be unbounded, and it must atomically detect
 when a message is pushed on to an empty queue.
\end_layout

\begin_layout Standard
Although there has been extensive research on queues, usefully sumarized
 in 
\begin_inset CommandInset citation
LatexCommand cite
key "herlihy2011art"

\end_inset

, the MPSC queue in the Pony runtime has more in common with a CLH queue
 lock 
\begin_inset CommandInset citation
LatexCommand cite
key "magnusson1994queue"

\end_inset

.
 While it is asynchronous and non-blocking, it uses a similar mechanism
 for maintaining a queue.
 Unlike the classic Michael and Scott queue 
\begin_inset CommandInset citation
LatexCommand cite
key "michael1996simple"

\end_inset

, the Pony queue does not require atomic compare-and-swap operations, and
 so does not suffer from performance scalability problems due to CAS failures
 on the x86/x64 architecture 
\begin_inset CommandInset citation
LatexCommand cite
key "morrison2013fast"

\end_inset

.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Unbounded-Message-Queues"

\end_inset

Unbounded Message Queues
\end_layout

\begin_layout Standard
Unbounded message queues are required to prevent both deadlock and incorrectly
 reporting resource exhaustion.
 If an actor's queue had any bound, even a large one, then some actor 
\begin_inset Formula $\alpha_{1}$
\end_inset

 that sent a message to an actor 
\begin_inset Formula $\alpha_{2}$
\end_inset

, where 
\begin_inset Formula $\alpha_{2}$
\end_inset

 had a full queue, would have to handle the inability to send a message.
 There are two strategies for this: 
\begin_inset Formula $\alpha_{1}$
\end_inset

 could either block until 
\begin_inset Formula $\alpha_{2}$
\end_inset

's queue is not full, or fail to send the message (a retry and time-out
 mechanism is simply a combination of these two approaches).
\end_layout

\begin_layout Itemize
If 
\begin_inset Formula $\alpha_{1}$
\end_inset

 adopts the strategy of blocking while attempting to push a message on to
 
\begin_inset Formula $\alpha_{2}$
\end_inset

's queue, then the system could deadlock.
 This occurs when 
\begin_inset Formula $\alpha_{1}$
\end_inset

 also has a full queue and 
\begin_inset Formula $\alpha_{2}$
\end_inset

 is attempting to send a message to 
\begin_inset Formula $\alpha_{1}$
\end_inset

.
 More complex message sending patterns could also lead to a deadlock.
 The key observation is that 
\begin_inset Formula $\alpha_{1}$
\end_inset

 cannot pop a message from its own queue while it is waiting for 
\begin_inset Formula $\alpha_{2}$
\end_inset

's queue to no longer be full, as doing so would cause behaviours on 
\begin_inset Formula $\alpha_{1}$
\end_inset

 to be interleaved, resulting in inconsistent state.
\end_layout

\begin_layout Itemize
If 
\begin_inset Formula $\alpha_{1}$
\end_inset

 adopts the strategy of failing to send a message when 
\begin_inset Formula $\alpha_{2}$
\end_inset

's queue is full, all asynchronous behaviour calls would have to be able
 to propagate an error, and that error would have to be checked in the program.
 The error would relate to resource exhaustion (a full queue) but unlike
 other forms of resource exhaustion (e.g.
 running out of memory, reaching file handle limits, etc.), the condition
 is inherently temporary.
 That is, 
\begin_inset Formula $\alpha_{2}$
\end_inset

 would eventually pop a message from its queue, and the program would need
 to restart or retry actions in response.
 Effectively, this would transform any behaviour that sent one or more messages
 into a state machine depending on message sending progress.
 To keep consistent state, all of an actor's behaviours would have to be
 integrated into a single state machine that tracked this progress.
 This is effectively interleaved behaviours, but with a complex mechanism
 for the programmer to manually resolve inconsistent state.
\end_layout

\begin_layout Standard
Unbounded message queues transform a temporary resource exhaustion problem
 into a less common permanent resource exhaustion problem, i.e.
 an unrecoverable out of memory error when a queue grows so large that it
 exhausts all available memory.
 This results in a simpler error handling mechanism (the program terminates),
 but, more importantly, in an error condition that represents an actual
 unrecoverable program error, rather than a transient and recoverable condition.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Empty-Queue-Detection"

\end_inset

Empty Queue Detection
\end_layout

\begin_layout Standard
An important aspect of the scheduler is that an actor with no pending work
 must not consume scheduler resources.
 That is, it must not be present on any scheduler queue.
 In order to accomplish this, a scheduler thread that is executing an actor
 must be able to detect when that actor's queue is empty in order to not
 reschedule it.
 In addition, whenever a message is sent to an actor, it must be possible
 to atomically detect that the queue was empty when the message was sent,
 in order to allow the receiving actor to be scheduled on some scheduler
 thread.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

bool ponyint_messageq_markempty(messageq_t* q) {
\end_layout

\begin_layout Plain Layout

  pony_msg_t* tail = q->tail;
\end_layout

\begin_layout Plain Layout

  pony_msg_t* head = atomic_load_explicit(&q->head, memory_order_relaxed);
\end_layout

\begin_layout Plain Layout

  if(((uintptr_t)head & 1) != 0)
\end_layout

\begin_layout Plain Layout

    return true;
\end_layout

\begin_layout Plain Layout

  if(head != tail)
\end_layout

\begin_layout Plain Layout

    return false;
\end_layout

\begin_layout Plain Layout

  head = (pony_msg_t*)((uintptr_t)head | 1);
\end_layout

\begin_layout Plain Layout

  return atomic_compare_exchange_strong_explicit(&q->head, &tail, head,
\end_layout

\begin_layout Plain Layout

    memory_order_release, memory_order_relaxed);
\end_layout

\begin_layout Plain Layout

} 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Marking-a-message"

\end_inset

Marking a message queue as empty
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
When a scheduler thread executes an actor, it is possible that the actor
 will attempt to pop a message from its queue, as in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Popping-from-a"

\end_inset

, and no message will be available.
 When this happens, the actor will attempt to set the low bit on the stub
 message (stub messages are discussed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Queue-Node-Memory"

\end_inset

) remaining in its queue, as shown in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Marking-a-message"

\end_inset

.
 This requires a single atomic compare-and-swap, with no loop, i.e.
 it is a lock-free and wait-free operation.
 It will succeed only if the queue is truly empty.
\end_layout

\begin_layout Standard
If the actor is able to mark its queue as empty, the scheduler thread will
 not reschedule the actor.
 At this point, the actor will not be referenced by any scheduler thread.
\end_layout

\begin_layout Standard
Returning to figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Pushing-to-a"

\end_inset

, we can see that when some actor 
\begin_inset Formula $\alpha_{1}$
\end_inset

 sends a message to some actor 
\begin_inset Formula $\alpha_{2}$
\end_inset

 and 
\begin_inset Formula $\alpha_{2}$
\end_inset

's queue is empty at the moment when the message is sent, it will be atomically
 detected.
 When this happens, the sending actor 
\begin_inset Formula $\alpha_{1}$
\end_inset

 will reschedule 
\begin_inset Formula $\alpha_{2}$
\end_inset

, as 
\begin_inset Formula $\alpha_{2}$
\end_inset

 now has pending work.
 Rescheduling involves pushing the actor onto the scheduler queue of the
 currently executing scheduler thread, as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Scheduler"

\end_inset

.
\end_layout

\begin_layout Standard
Critically, this empty queue detection and rescheduling will happen only
 once, regardless of contention on 
\begin_inset Formula $\alpha_{2}$
\end_inset

's queue, and will not occur again until 
\begin_inset Formula $\alpha_{2}$
\end_inset

 marks its own queue as empty again.
 As a result, any given actor will always be present on either zero or one
 scheduler queue.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Queue-Node-Memory"

\end_inset

Queue Node Memory Management
\end_layout

\begin_layout Standard
When a message is pushed to a queue, the sender implicitly uses the pool
 allocator to allocate a new message queue node that will contain the arguments.
 This is the message queue node that is pushed on to the receiver's queue,
 as seen in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Pushing-to-a"

\end_inset

.
\end_layout

\begin_layout Standard
However, when the receiver pops a message from its queue, the receiver reads
 the next node from the tail, rather than the tail, as seen in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Popping-from-a"

\end_inset

.
 If the pop is successful, the previous tail is freed, and the message node
 containing the popped message remains on the queue.
\end_layout

\begin_layout Standard
This has two key advantages.
 The first is that the message queue node is not freed until after the behaviour
 that handles the message has finished executing, which simplifies memory
 management.
 The second, more critical, advantage is that the message queue is never
 empty.
 It always contains at least one message queue node, which may or may not
 point to another node that represents a pending message.
 This allows the code that pushes a new message on the queue to separate
 the atomic exchange on the queue head and the setting of the next pointer
 without causing a race condition.
\end_layout

\begin_layout Standard
When the push code executes the atomic store, it will always write the correct
 next node, even if the head has in the meantime changed due to another
 message being pushed on to the queue.
 This can result in a message pop returning 
\begin_inset Formula $\mathtt{NULL}$
\end_inset

 even though a new message has been partially pushed on to the queue (that
 is, the queue head has been changed, but the tail does not yet point to
 the new head).
 However, this is not a race condition.
 Under these circumstances, the actor will report that is has no pending
 messages, but when it is asked to mark its queue as empty, it will fail
 to do so, due to the head no longer being the same as the tail.
 In fact, the actor will determine the queue is non-empty without an atomic
 operation.
 As a result, the actor will be rescheduled, and the newly pending message
 will eventually be handled, as expected.
\end_layout

\begin_layout Section
Actors
\end_layout

\begin_layout Standard
In the runtime, an actor is represented as an object header 
\family typewriter
type
\family default
, a message queue 
\family typewriter
q
\family default
, a set of operational 
\family typewriter
flags
\family default
, a 
\family typewriter
heap
\family default
, and information for tracking cross-actor garbage collection 
\family typewriter
gc 
\family default
(as discussed in sections 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Sharing-GC"

\end_inset

 and 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Actor-GC"

\end_inset

), as seen in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Internal-actor-description"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

typedef struct pony_actor_t {
\end_layout

\begin_layout Plain Layout

  pony_type_t* type;
\end_layout

\begin_layout Plain Layout

  messageq_t q;
\end_layout

\begin_layout Plain Layout

  uint8_t flags;
\end_layout

\begin_layout Plain Layout

  __pony_spec_align__(heap_t heap, 64); // 52/104 bytes
\end_layout

\begin_layout Plain Layout

  gc_t gc; // 44/80 bytes 
\end_layout

\begin_layout Plain Layout

} pony_actor_t; 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Internal-actor-description"

\end_inset

Internal actor description
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
The heap and garbage collection structure are aligned on a 64 byte boundary
 to keep them on a separate cache line from the type, queue, and flags,
 to reduce false sharing in the cache coherency protocol.
 The actor description, including padding, is 156 bytes on a 32-bit architecture
 and 240 bytes on a 64-bit architecture.
\end_layout

\begin_layout Standard
For a concrete actor type, this structure is extended with the fields of
 the actor.
 For example, if the concrete actor type has 16 bytes of field data on a
 64-bit architecture, an instance of the type will be allocated with a single
 256 byte allocation, i.e.
 240 bytes of actor description plus 16 bytes of field data.
 This is done to avoid a memory indirection when reading from or writing
 to the fields of an actor.
\end_layout

\begin_layout Standard
It is important to note that an actor has no stack associated with it.
 Instead, only scheduler threads have stacks.
 This allows actors to consume significantly less memory, while avoiding
 the execution speed penalties associated with segmented stacks.
 In addition, the foreign-function interface (FFI) can use the same unsegmented
 stack that the actor executing the FFI call is currently using, providing
 a simple and efficient FFI mechanism.
\end_layout

\begin_layout Subsection
Message Handling
\end_layout

\begin_layout Standard
When an actor is scheduled for execution by a scheduler thread, the actor
 will pop messages from its own queue and handle each one in turn.
 These messages are divided between internal garbage collection messages,
 as described in sections 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Sharing-GC"

\end_inset

 and 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Actor-GC"

\end_inset

, and messages explicitly generated by the program, which are termed application
 messages, as in chapter 
\begin_inset CommandInset ref
LatexCommand ref
reference "chap:Object-Collection"

\end_inset

.
\end_layout

\begin_layout Standard
An application message is handled by executing a behaviour on an actor.
 That behaviour is executed to completion by the scheduler thread.
 Since the type system enforces isolation and immutability, as detailed
 in chapter 
\begin_inset CommandInset ref
LatexCommand ref
reference "chap:Reference-Capabilities"

\end_inset

, this results in every actor behaviour being logically atomic.
 That is, each behaviour on an actor can reach only the actor's state and
 the arguments to the behaviour, and the behaviour cannot witness any mutation
 other than mutations it performs itself.
\end_layout

\begin_layout Subsection
Message Batching
\end_layout

\begin_layout Standard
Popping an actor from a scheduler queue requires an atomic compare-and-swap
 loop, as discussed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Scheduler-Queues"

\end_inset

, whereas popping a message from a message queue requires no atomic operations
 and is wait-free, as discussed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Popping-from-a"

\end_inset

.
 As a result, it is beneficial to handle more than one message each time
 an actor is scheduled for execution.
\end_layout

\begin_layout Standard
Actors are not asked to handle every message in their queue entirely when
 they are scheduled as this would lead to starvation.
 For example, an actor could send itself one or more messages in a behaviour,
 resulting in the actor never yielding execution, or a producer-consumer
 pattern could result in a consumer receiving messages as or more quickly
 than it could handle them, again resulting in starvation.
\end_layout

\begin_layout Standard
In the current implementation, actors are asked by the scheduler thread
 to handle up to a fixed number of application messages (defaulting to 100)
 each time they are scheduled, amortising the cost of a scheduler queue
 pop across many behaviours.
 In addition, any number of interleaved internal, garbage collection related,
 messages can be processed without counting against the batch limit.
 In future work, the number of application messages an actor is asked to
 handle will fluctuate dynamically based on back-pressure.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Blocking-and-Unblocking"

\end_inset

Blocking and Unblocking
\end_layout

\begin_layout Standard
When an actor believes it has no pending messages, it sets a flag indicating
 that it is blocked and sends a message to the cycle detector (described
 in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:The-Cycle-Detector"

\end_inset

) indicating that it should be considered blocked.
 It then attempts to mark its own message queue as empty, as discussed in
 section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Empty-Queue-Detection"

\end_inset

.
 Because the actor may be rescheduled on any scheduler thread as soon as
 its queue is marked as empty, the actor must set the blocked flag and send
 the message to the cycle detector before it marks its own message queue
 as empty.
 As a result, the state reported to the cycle detector may already be out
 of date by the time it is sent.
 The implications of this are discussed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Actor-GC"

\end_inset

.
\end_layout

\begin_layout Standard
When an actor handles an application message and its own blocked flag is
 set, it unsets the flag and sends a message to the cycle detector indicating
 that is should be considered unblocked.
 However, internal garbage collection messages do not result in the actor
 unblocking.
 Instead, if these are received while blocked, the actor sets a flag indicating
 that its garbage collection status has changed.
 This flag influences the way the actor responds to the cycle detector,
 as discussed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Acknowledgement-Messages"

\end_inset

.
\end_layout

\begin_layout Standard
If an actor has handled one or more application messages when scheduled,
 as an optimisation it will not attempt to block or mark its message queue
 as empty even if it believes its message queue to be empty.
 Instead, it will reschedule as if it had pending work.
 This is an optimisation that results in fewer block and unblock messages,
 significantly reducing state churn and message load on the cycle detector.
\end_layout

\begin_layout Subsection
Rescheduling
\end_layout

\begin_layout Standard
If an actor handles any application messages or is unable to mark its queue
 as empty (indicating there are new pending messages), it asks the scheduler
 thread to reschedule it.
 However, if the actor successfully marks its queue as empty, the actor
 is not rescheduled.
 This results in the actor not being in any scheduler queue, and so consuming
 no resources (memory or CPU time), other than the memory required to hold
 its own state, when it is not scheduled.
\end_layout

\begin_layout Section
\begin_inset CommandInset label
LatexCommand label
name "subsec:Tracing-GC"

\end_inset

Tracing GC
\end_layout

\begin_layout Standard
The core of the Pony garbage collector is the per-actor tracing garbage
 collection step.
 This step traces and collects actor heaps independently, without requiring
 coordination between actors.
 The algorithm used is a mark-and-don't-sweep collector that has a time
 complexity of 
\begin_inset Formula $O(m+n)$
\end_inset

, where 
\begin_inset Formula $n$
\end_inset

 is the number of objects reachable by the actor, and 
\begin_inset Formula $m$
\end_inset

 is the number of chunks (as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Heaps"

\end_inset

) on the actor's heap.
\end_layout

\begin_layout Standard
The algorithm begins by setting all the valid bits in every chunk descriptor
 on the heap.
 This tentatively frees all memory allocated by the actor, without releasing
 chunk descriptors or the memory areas managed by those chunks.
 The counter for the amount of memory in use by the actor is also reset
 to zero.
\end_layout

\begin_layout Standard
While this phase involves the chunk descriptors for all memory allocated
 on the actor's heap, it does not actually touch the allocated memory itself.
 This is important as it avoids unnecessary cache pollution and page faults
 that can result from reading unreachable memory.
\end_layout

\begin_layout Standard
In the next phase, the garbage collection roots are marked as reachable,
 and any root with a trace function, as detailed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Trace-Functions"

\end_inset

, is pushed on to a stack of objects that have not yet been traced.
 If the trace function can be determined statically, the code generator
 inserts it directly.
 Otherwise, it is dynamically determined by reading from the object header.
 While additional roots are introduced by the sharing protocol in section
 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Sharing-GC"

\end_inset

, the only root introduced here is the actor itself.
\end_layout

\begin_layout Standard
The stack of as yet untraced objects is then processed.
 When an object is traced, its memory address is looked up in the page map
 (described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Page-Map"

\end_inset

).
 This gives the address of the chunk descriptor that manages the memory
 area the object has been allocated in.
 The offset of the object's address from the base address of the memory
 area gives the bit that should be unset to represent that this memory is
 reachable.
\end_layout

\begin_layout Standard
When the stack of objects and their trace functions is empty, every reachable
 object in the actor's heap has been traced.
 At this point, the chunk descriptors are examined again.
 A chunk descriptor with no available memory is placed on the linked list
 of full chunks for its size class, and a chunk descriptor that has some
 available memory, but is not empty, is placed on the linked list of chunks
 with available memory for its size class.
 An empty chunk, i.e.
 one with all valid bits set indicating the memory is free, is returned
 to the pool allocator along with the memory area it manages.
 This maintains the chunk validity invariant in definition 
\begin_inset CommandInset ref
LatexCommand ref
reference "def:Chunk-validity"

\end_inset

.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Deep-vs.-Shallow"

\end_inset

Deep vs.
 Shallow Marking
\end_layout

\begin_layout Standard
A distinction is made when clearing bits (to indicate that memory is in
 use) between deep and shallow marking.
 A deep mark is used when the object is reachable with a reference capability
 that allows reading from the object.
 This indicates not only that the object is reachable, but also that it
 has already been placed on the reachable object stack with its trace function.
 On the other hand, when an object is reachable as a 
\begin_inset Formula $\mathtt{tag}$
\end_inset

, and so its fields are not reachable, a shallow mark is used.
 This indicates that the object is reachable, but it has not yet been placed
 on the reachable object stack.
 In this case, if the object is reachable via some other path with a readable
 reference capability, the object's fields will be correctly traced.
 The distinction between deep and shallow mark bits is shown in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:A-chunk-descriptor"

\end_inset

.
\end_layout

\begin_layout Standard
This approach treats internal pointers (pointers inside a small allocation
 as opposed to a pointer to the beginning of a small allocation) as shallow
 marks, even if their fields are reachable.
 This is because internal pointers do not have bitmap entries of their own,
 but rather all internal pointers within an allocation share the bitmap
 entry of the external pointer.
 By using shallow marks, other internal pointers, or the enclosing external
 pointer, will be correctly traced if they are reached after an internal
 pointer has been traced.
\end_layout

\begin_layout Standard
Correctly accounting for internal pointers allows optimisations at the language
 level.
 Array and string slices, which use internal pointers to arrays of objects,
 can be naturally expressed.
 In addition, complex object layouts, such as embedded fields (in a similar
 manner as would be done in C by defining a field as a 
\family typewriter
struct
\family default
 instead of a pointer to a 
\family typewriter
struct
\family default
), or the transformation of an array of 
\family typewriter
struct
\family default
s to a 
\family typewriter
struct
\family default
 of arrays, can be handled without specialising the garbage collector.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Trace-Functions"

\end_inset

Trace Functions
\end_layout

\begin_layout Standard
Each concrete type generated by the compiler has a trace function.
 The trace function describes how to trace the fields of a reachable and
 readable reference to an instance of the type.
\end_layout

\begin_layout Standard
Fields are traced based on the field type visible from the object, without
 taking into account any viewpoint adaptation in the type system, as detailed
 in sections 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Reachability"

\end_inset

 and 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Reachability-1"

\end_inset

.
 In other words, the trace function for a type implicitly treats the instance
 being traced as a 
\begin_inset Formula $\mathtt{ref}$
\end_inset

.
 This allows the trace function to reach the maximal set of objects that
 could be reached from the program, without requiring reference capabilities
 to be encoded at runtime.
 Doing so is safe, because garbage collection does not mutate objects: all
 garbage collection related state is kept in parallel, actor-specific, data
 structures, rather than in the objects themselves.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

primitive P
\end_layout

\begin_layout Plain Layout

interface I
\end_layout

\begin_layout Plain Layout

class C1 // No fields
\end_layout

\begin_layout Plain Layout

class C2
\end_layout

\begin_layout Plain Layout

  let f1: P val // No trace
\end_layout

\begin_layout Plain Layout

  let f2: C2 ref // Static trace function
\end_layout

\begin_layout Plain Layout

  let f3: I ref // Dynamic trace function
\end_layout

\begin_layout Plain Layout

  let f4: C2 tag // Shallow mark
\end_layout

\begin_layout Plain Layout

  let f5: I tag // Shallow mark or actor
\end_layout

\begin_layout Plain Layout

  let f6: (P val, C2 ref, I ref) // Destructured
\end_layout

\begin_layout Plain Layout

  let f7: (C2 ref | I tag) // Shallow mark or actor
\end_layout

\begin_layout Plain Layout

  let f8: ((C1 ref, C2 tag) | (C2 tag, C1 ref))
\end_layout

\begin_layout Plain Layout

    // Dynamically destructured
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Trace-functions-and"

\end_inset

Classes, fields, and associated tracing
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
The action taken by a trace function for each field depends on the type
 of the field.
 Some examples are given in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Trace-functions-and"

\end_inset

.
 Note that this example covers more of the Pony type system than is described
 in chapter 
\begin_inset CommandInset ref
LatexCommand ref
reference "chap:Reference-Capabilities"

\end_inset

, and covers 
\family typewriter
primitive
\family default
 types (singleton types with no state, also usable as first-class parameterised
 modules), 
\family typewriter
interface
\family default
 types (structural types, also usable as type classes), tuples, and unions.
 The full Pony type system also includes 
\family typewriter
traits 
\family default
(nominal types), generic types and functions, as well as intersection types.
 Their behaviour during tracing is a natural extension of the behaviour
 presented here.
\end_layout

\begin_layout Standard
For primitive types, no action is taken, as in 
\begin_inset Formula $\mathtt{C2.f1}$
\end_inset

.
 For types with a known 
\begin_inset Formula $\mathtt{tag}$
\end_inset

 reference capability, such as 
\begin_inset Formula $\mathtt{C2.f4}$
\end_inset

, the object is shallowly marked, and is not placed on the trace stack,
 as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Deep-vs.-Shallow"

\end_inset

.
 If the type could be an actor, either because it is an interface or trait
 type or because a concrete actor type is present in an algebraic data type,
 such as 
\begin_inset Formula $\mathtt{C2.f5}$
\end_inset

, then the object's header is examined at runtime to determine if it is
 actually an actor.
 If so, it is handled via the actor garbage collector, as described in section
 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Actor-GC"

\end_inset

, instead of being marked.
 Otherwise, the trace function of the object is called dynamically.
\end_layout

\begin_layout Standard
If the field has a known concrete type, that is, a 
\family typewriter
struct
\family default
 or 
\family typewriter
class
\family default
, and does not have a 
\begin_inset Formula $\mathtt{tag}$
\end_inset

 reference capability, such as 
\begin_inset Formula $\mathtt{C2.f2}$
\end_inset

, the object is marked and placed on the trace stack with its statically
 known trace function.
 If the field has an unknown concrete type, either because it is a trait
 or interface or because it is an algebraic data type, but it can be determined
 statically that the object will not have a 
\begin_inset Formula $\mathtt{tag}$
\end_inset

 reference capability, such as 
\begin_inset Formula $\mathtt{C2.f3}$
\end_inset

, the object is marked and placed on the trace stack with a dynamically
 determined trace function that is looked up in the object's header.
\end_layout

\begin_layout Standard
A field that is statically known to be a tuple, such as 
\begin_inset Formula $\mathtt{C2.f6}$
\end_inset

, is de-structured and each field is traced independently.
 The tuple itself does not have to be marked, as statically known tuple
 fields are embedded in the parent instance rather than being reached via
 a pointer indirection.
\end_layout

\begin_layout Standard
The complex case comes when it is not possible to determine statically whether
 or not a field has a 
\begin_inset Formula $\mathtt{tag}$
\end_inset

 reference capability.
 This case requires the object to be examined at runtime.
 The issue is not just that tracing a 
\begin_inset Formula $\mathtt{tag}$
\end_inset

 reference as if it was readable would lead to unreachable objects not being
 collected (which would be sub-optimal but still correct), but that tracing
 a 
\begin_inset Formula $\mathtt{tag}$
\end_inset

 reference as if it was readable in some actor 
\begin_inset Formula $\alpha_{1}$
\end_inset

 could result in 
\begin_inset Formula $\alpha_{1}$
\end_inset

 reading the fields of an object (for tracing purposes) while some other
 actor 
\begin_inset Formula $\alpha_{2}$
\end_inset

 modifies those fields.
\end_layout

\begin_layout Standard
Handling this case requires the code generator to use the type system to
 determine which types a field could be visible as to the program.
 For example, 
\begin_inset Formula $\mathtt{C2.f7}$
\end_inset

 is treated as an 
\begin_inset Formula $\mathtt{I\,tag}$
\end_inset

, i.e.
 the same as 
\begin_inset Formula $\mathtt{C2.f5}$
\end_inset

, because 
\begin_inset Formula $\mathtt{C2}$
\end_inset

 is a subtype of 
\begin_inset Formula $\mathtt{I}$
\end_inset

, so that it is not possible for the program to pattern match on 
\begin_inset Formula $\mathtt{C2.f7}$
\end_inset

 as a 
\begin_inset Formula $\mathtt{C2\,ref}$
\end_inset

, or indeed as any readable capability.
\end_layout

\begin_layout Standard
This particular example is somewhat counterintuitive, as it results in the
 fields of 
\begin_inset Formula $\mathtt{C2.f7}$
\end_inset

 not being traced, and so possibly garbage collected if they are not reachable
 via some other path.
 This initially appears to be unsound.
 However, the inability to pattern match on 
\begin_inset Formula $\mathtt{C2.f7}$
\end_inset

 as any readable capability, which is enforced by the type checker, prevents
 the fields of 
\begin_inset Formula $\mathtt{C2.f7}$
\end_inset

 from being read or written to.
 As such, it is safe to garbage collect those fields if they are not otherwise
 reachable.
\end_layout

\begin_layout Standard
When tuples are contained in algebraic data types, the code generator must
 determine the set of possible ways each element of each tuple could be
 viewed.
 For example, in 
\begin_inset Formula $\mathtt{C2.f8}$
\end_inset

, each element must be dynamically examined, as each may or may not have
 a 
\begin_inset Formula $\mathtt{tag}$
\end_inset

 reference capability at runtime.
\end_layout

\begin_layout Standard
Generating trace functions that can make these distinctions at runtime is
 important because reference capabilities, being based on viewpoints, cannot
 be encoded in objects.
 That is, any given object may be viewed with a collection of reference
 capabilities, depending on the path used to reach the object.
 As a result, if reference capabilities were to be encoded at runtime, every
 object reference would have to include both a pointer and a capability,
 which would impose both a memory overhead and an execution speed overhead.
 In addition, such an encoding would still require adapted capabilities
 to be calculated at runtime based on the encoded field or local variable
 capabilities.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Garbage-Collecting-During"

\end_inset

Garbage Collecting During Behaviours
\end_layout

\begin_layout Standard
The current implementation performs per-actor garbage collection on an actor
 in between behaviours.
 As a result, garbage collection does not occur during actor execution.
 This approach reduces performance jitter within a behaviour.
 In addition, it means that object references on the stack do not have to
 be tracked as garbage collection roots, so that no stack map need be compiled
 into the program.
\end_layout

\begin_layout Standard
However, this approach has a significant downside: behaviours that allocate
 large amounts of short-lived memory (i.e.
 memory that is not further referenced within the behaviour) will not collect
 that short-lived memory until the behaviour finishes executing.
\end_layout

\begin_layout Standard
In future work, the code generator will be extended to optionally generate
 a stack map.
 This will allow object references on the stack to function as garbage collectio
n roots.
 To do so, the stack map will have to encode the same ability to distinguish
 possible types at runtime as trace functions encode on fields, as described
 in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Trace-Functions"

\end_inset

.
\end_layout

\begin_layout Standard
The stack map on its own is sufficient to allow garbage collection during
 behaviour execution, without the addition of read or write barriers, or
 of safe-points.
 This is possible because each actor heap is independently collectable (no
 safe-points required), and because concurrent garbage collection is handled
 through the message-based protocol described in chapter 
\begin_inset CommandInset ref
LatexCommand ref
reference "chap:Object-Collection"

\end_inset

 rather than with a stop-the-world phase.
\end_layout

\begin_layout Standard
In addition, the design decision to not use a copying collector means that
 stack references do not need to be changed to point to objects moved to
 new addresses by the copying collector.
 This is also true of heap pointers, but is arguably more significant for
 stack pointers.
 Changing stack pointers requires the single static assignment (SSA) intermediat
e representation (IR) of the program used by LLVM to generate machine code
 to account for relocations, which can impede certain compiler optimisations.
\end_layout

\begin_layout Subsection
Role of the Type System
\end_layout

\begin_layout Standard
The tracing phase of the garbage collector is heavily dependent on the type
 system.
 The use of a data-race free type system enables independent heap tracing.
 It also allows normal program execution to proceed without read or write
 barriers.
\end_layout

\begin_layout Standard
In addition, the existence of object references that do not allow reading
 from the object (i.e.
 the 
\begin_inset Formula $\mathtt{tag}$
\end_inset

 reference capability) requires the distinction between shallow and deep
 marking, as well as the generation of trace functions which can distinguish,
 either statically or dynamically, between readable and unreadable object
 references.
\end_layout

\begin_layout Section
\begin_inset CommandInset label
LatexCommand label
name "sec:Sharing-GC"

\end_inset

Sharing GC
\end_layout

\begin_layout Standard
The per-actor tracing phase of the garbage collector, described in section
 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Tracing-GC"

\end_inset

, is unsafe if used alone: it would garbage collect memory allocated by
 some actor 
\begin_inset Formula $\alpha_{1}$
\end_inset

 that is no longer reachable by 
\begin_inset Formula $\alpha_{1}$
\end_inset

, but is reachable by some other actor 
\begin_inset Formula $\alpha_{2}$
\end_inset

.
 The message-based protocol described in chapter 
\begin_inset CommandInset ref
LatexCommand ref
reference "chap:Object-Collection"

\end_inset

 is used to protect such objects from premature collection.
 This description goes beyond the formal model in chapter 
\begin_inset CommandInset ref
LatexCommand ref
reference "chap:Object-Collection"

\end_inset

 and describes both the overall implementation and specific optimisations,
 such as generational marks, that are necessary to achieve the desired performan
ce.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

typedef struct gc_t {
\end_layout

\begin_layout Plain Layout

  uint32_t mark;
\end_layout

\begin_layout Plain Layout

  uint32_t rc_mark;
\end_layout

\begin_layout Plain Layout

  size_t rc;
\end_layout

\begin_layout Plain Layout

  objectmap_t local;
\end_layout

\begin_layout Plain Layout

  actormap_t foreign;
\end_layout

\begin_layout Plain Layout

  deltamap_t* delta;
\end_layout

\begin_layout Plain Layout

} gc_t; 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Tracking-local-and"

\end_inset

Tracking local and foreign reference counts
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

typedef struct object_t {
\end_layout

\begin_layout Plain Layout

  void* address;
\end_layout

\begin_layout Plain Layout

  size_t rc;
\end_layout

\begin_layout Plain Layout

  uint32_t mark;
\end_layout

\begin_layout Plain Layout

  bool immutable;
\end_layout

\begin_layout Plain Layout

} object_t; 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Object-GC-information"

\end_inset

Object GC information
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

typedef struct actorref_t {
\end_layout

\begin_layout Plain Layout

  pony_actor_t* actor;
\end_layout

\begin_layout Plain Layout

  size_t rc;
\end_layout

\begin_layout Plain Layout

  uint32_t mark;
\end_layout

\begin_layout Plain Layout

  objectmap_t map;
\end_layout

\begin_layout Plain Layout

} actorref_t; 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Actor-GC-information"

\end_inset

Actor GC information
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
The implementation of the protocol requires keeping a data structure to
 track local and foreign reference counts, as shown in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Tracking-local-and"

\end_inset

.
 Each actor has a 
\family typewriter
gc_t 
\family default
to track its view of shared objects, as shows in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Internal-actor-description"

\end_inset

.
 The 
\family typewriter
local
\family default
 map associates locally owned pointers with a reference count, as shown
 in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Object-GC-information"

\end_inset

.
 The 
\family typewriter
foreign
\family default
 map associates actors with objects they own, as shown in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Actor-GC-information"

\end_inset

.
 Note that this is a map of actors to a map of objects, i.e.
 
\begin_inset Formula $[\mathit{Actor}\mapsto(\mathit{RC},\mathit{Mark,}[\mathit{Object}\mapsto(\mathit{RC},\mathit{Mark},\mathit{Immutable})])]$
\end_inset

, allowing foreign object GC information to be kept segregated by owner.
\end_layout

\begin_layout Standard
This per-object and per-actor GC information is kept outside of the object
 itself, i.e.
 in a separately allocated data structure rather than in fields of the object,
 because it is not intrinsic to the object: it is information about an object
 from the perspective of some actor.
 As such, each actor has GC map entries only for the local objects it has
 sent and the foreign actors and objects it has received.
\end_layout

\begin_layout Standard
The map algorithm used for both 
\family typewriter
actormap_t 
\family default
and 
\family typewriter
objectmap_t 
\family default
is a linear probing Robin Hood hash map where the key is embedded in the
 same data structure as the value.
 In an 
\family typewriter
objectmap_t
\family default
, the key is the 
\family typewriter
address
\family default
 field, and in an 
\family typewriter
actormap_t
\family default
, the key is the 
\family typewriter
actor
\family default
 field.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Mark,-Send,-and"

\end_inset

Mark, Send, and Receive Phases
\end_layout

\begin_layout Standard
There are three distinct phases when the 
\family typewriter
gc_t
\family default
 for an actor is used.
 The first is during the mark phase of the tracing garbage collection described
 in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Tracing-GC"

\end_inset

.
 The second is when a message is sent, and the third is when a message is
 received.
\end_layout

\begin_layout Standard
In the second and third phases, which correspond to definitions 
\begin_inset CommandInset ref
LatexCommand ref
reference "def:Sending-a-reference-1"

\end_inset

 and 
\begin_inset CommandInset ref
LatexCommand ref
reference "def:Receiving-a-reference-1"

\end_inset

 from chapter 
\begin_inset CommandInset ref
LatexCommand ref
reference "chap:Object-Collection"

\end_inset

, the tracing algorithm from section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Tracing-GC"

\end_inset

 is used, but the roots are the arguments to the behaviour rather than the
 fields of the actor.
 That is, when a message is sent or received, the arguments to the message
 are traced to determine what garbage collection information must be updated.
 This is used to determine reachability as defined in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Reachability-1"

\end_inset

.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Generational-Marks"

\end_inset

Generational Marks
\end_layout

\begin_layout Standard
The 
\begin_inset Formula $\mathtt{mark}$
\end_inset

 field in the data structures in figures 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Tracking-local-and"

\end_inset

, 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Object-GC-information"

\end_inset

, and 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Actor-GC-information"

\end_inset

 is used to track whether an object has been marked in the current garbage
 collection phase.
 Its purpose is to allow cyclic structures to be correctly traced, with
 each object being examined only once.
\end_layout

\begin_layout Standard
Because the number of objects tracked in an actor's 
\begin_inset Formula $\mathtt{gc\_t}$
\end_inset

 structure could be significantly larger than the number of objects being
 sent or received in a message, a generational mark is kept for each object
 rather than a simple mark bit.
 The 
\begin_inset Formula $\mathtt{mark}$
\end_inset

 field of 
\begin_inset Formula $\mathtt{gc\_t}$
\end_inset

 indicates the current generation, with this number being incremented after
 the completion of any mark, send, or receive phase.
\end_layout

\begin_layout Standard
When an actor or object is visited in a garbage collection phase, its 
\begin_inset Formula $\mathtt{mark}$
\end_inset

 is set to the current generation.
 Thus, an actor or object entry with a 
\begin_inset Formula $\mathtt{mark}$
\end_inset

 field that differs from the 
\begin_inset Formula $\mathtt{mark}$
\end_inset

 field in the 
\begin_inset Formula $\mathtt{gc\_t}$
\end_inset

 has not yet been visited.
\end_layout

\begin_layout Standard
The purpose of this is to avoid the need to sweep the actors and objects
 being tracked.
 Instead, the generational mark is incremented, which implicitly invalidates
 the mark for every tracked actor or object.
 This not only reduces the time complexity of a phase, it also avoids the
 cache pollution that would result from sweeping these data structures.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Determining-Ownership"

\end_inset

Determining Ownership
\end_layout

\begin_layout Standard
When an object is encountered in any garbage collection phase, the first
 step is to determine the owner of the object.
 To do so, the object's address is looked up in the page map, as described
 in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Page-Map"

\end_inset

.
 This returns the chunk descriptor for the memory area the object is allocated
 in.
 The chunk descriptor, in turn, contains a pointer to the owning actor.
\end_layout

\begin_layout Standard
Because the chunk descriptor contains both the mark bits for the managed
 memory area and the owning actor, the chunk descriptor lookup performed
 in the tracing garbage collector described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Tracing-GC"

\end_inset

 also serves to distinguish between local and foreign object ownership.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Sending-and-Receiving"

\end_inset

Sending and Receiving Local Objects
\end_layout

\begin_layout Standard
When a locally owned object is sent in a message, the sending actor must
 protect that object from garbage collection, as described in chapter 
\begin_inset CommandInset ref
LatexCommand ref
reference "chap:Object-Collection"

\end_inset

.
 To do so, the object's address is looked up in the 
\begin_inset Formula $\mathtt{local}$
\end_inset

 map.
 If the object is not present in the map, it is added with an 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 of one and the object's 
\begin_inset Formula $\mathtt{mark}$
\end_inset

 is set to the current mark.
 If the object is present in the map and the object's 
\begin_inset Formula $\mathtt{mark}$
\end_inset

 is not current, the object's 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 is incremented by one, and its 
\begin_inset Formula $\mathtt{mark}$
\end_inset

 is set to the current mark.
\end_layout

\begin_layout Standard
The result of this is that an object's local 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 is incremented by one each time it is sent in a message, where being sent
 in a message means that the object is a message argument or is reachable
 from some message argument, as defined in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Reachability-1"

\end_inset

.
\end_layout

\begin_layout Standard
Similarly, when a locally owned object is received in a message, the object's
 address is looked up in the 
\begin_inset Formula $\mathtt{local}$
\end_inset

 map and, if the object's 
\begin_inset Formula $\mathtt{mark}$
\end_inset

 is not current, its 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 is decremented by one.
 Because of the invariants described in chapter 
\begin_inset CommandInset ref
LatexCommand ref
reference "chap:Object-Collection"

\end_inset

, the object will always be present in the 
\begin_inset Formula $\mathtt{local}$
\end_inset

 map and will always have an 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 greater than zero.
\end_layout

\begin_layout Standard
If an object's local reference count drops to zero, it is not removed from
 the 
\begin_inset Formula $\mathtt{local}$
\end_inset

 map at this point.
 That bookkeeping is done when the local map is traced during garbage collection
, as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Tracing-the-Local"

\end_inset

.
 This is done to avoid adding and removing an object's 
\begin_inset Formula $\mathtt{local}$
\end_inset

 map entry multiple times in between garbage collection phases.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Sending-and-Receiving-1"

\end_inset

Sending and Receiving Foreign Objects
\end_layout

\begin_layout Standard
For foreign objects, the simpler case is when they are received.
 When this happens, the object's owning actor address is looked up in the
 
\begin_inset Formula $\mathtt{foreign}$
\end_inset

 map, and is added if it is not present.
 Then a second lookup, in the resulting 
\begin_inset Formula $\mathtt{map}$
\end_inset

 for that actor, is performed using the object's address, again adding the
 object if it is not present.
 At this point, if the object's 
\begin_inset Formula $\mathtt{mark}$
\end_inset

 is not current, the object's foreign 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 is incremented by one and its 
\begin_inset Formula $\mathtt{mark}$
\end_inset

 is set to the current mark.
\end_layout

\begin_layout Standard
As a result, while a local object's 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 is incremented when it is sent, a foreign object's 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 is incremented when it is received.
\end_layout

\begin_layout Standard
The more complex case occurs when a foreign object is sent in a message.
 In this case, the owning actor and then the object are looked up, just
 as when a foreign object is received.
 If the object's 
\begin_inset Formula $\mathtt{mark}$
\end_inset

 is not current, its 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 is decremented by one.
 The complexity occurs when the sending actor's foreign 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 for the object is one.
 In this case, the foreign 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 cannot be decremented without breaking the invariant that an actor that
 can reach a foreign object, either through its fields or on the stack,
 must hold a foreign 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 for that object of at least one, as required by definition 
\begin_inset CommandInset ref
LatexCommand ref
reference "Reachability-invariant"

\end_inset

.
\end_layout

\begin_layout Standard
When this occurs, the sending actor increases its foreign 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 for the object by an arbitrary amount (256 in the default configuration).
 To maintain all of the reference count invariants described in chapter
 
\begin_inset CommandInset ref
LatexCommand ref
reference "chap:Object-Collection"

\end_inset

, a message must be sent to the owning actor informing it of the increased
 reference count.
 To do so, the object is added to the set of objects for which an 
\emph on
acquire message
\emph default
 will be sent when the current garbage collection phase finishes, as detailed
 in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Acquire-and-Release"

\end_inset

.
 This is the implementation of the 
\noun on
Acquire
\noun default
 rule from figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:opsem-for-object-GC"

\end_inset

.
\end_layout

\begin_layout Standard
Note that an 
\emph on
acquire message
\emph default
 consists of a set of 
\family typewriter
object_t
\family default
, as defined in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Object-GC-information"

\end_inset

.
 This is equivalent to the
\emph on
 
\begin_inset Formula $\mathit{ExMap}$
\end_inset

 
\emph default
defined in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Runtime-entities-for-actor-GC"

\end_inset

.
 The 
\family typewriter
mark
\family default
 field is ignored, but the 
\family typewriter
immutable
\family default
 field is used in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Sending-and-Receiving-2"

\end_inset

.
 When the 
\family typewriter
immutable
\family default
 field is 
\family typewriter
false
\family default
, an 
\emph on
acquire message
\emph default
 behaves exactly as detailed in chapter 
\begin_inset CommandInset ref
LatexCommand ref
reference "chap:Object-Collection"

\end_inset

.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Sending-and-Receiving-2"

\end_inset

Sending and Receiving Immutable Objects
\end_layout

\begin_layout Standard
The process of tracing message arguments leads to an 
\begin_inset Formula $O(n)$
\end_inset

 step both when sending and receiving the message, where 
\begin_inset Formula $n$
\end_inset

 is the number of objects reachable from those arguments.
 For large data structures, this can be a significant cost.
\end_layout

\begin_layout Standard
The purpose of tracing the message arguments is to protect the contents
 from premature garbage collection by adjusting the distributed weighted
 reference counts.
 The end result is that the owner of an object with a positive local 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 will not collect that object.
\end_layout

\begin_layout Standard
The type system can be used to provide an important optimisation: when some
 immutable object 
\begin_inset Formula $\omega$
\end_inset

 is sent in a message, either as an argument or reachable from an argument,
 any objects reachable from 
\begin_inset Formula $\omega$
\end_inset

 do not have to be protected from premature garbage collection.
 This is possible because the owner of 
\begin_inset Formula $\omega$
\end_inset

 can safely trace the fields of 
\begin_inset Formula $\omega$
\end_inset

 when it traces its local object map, as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Tracing-the-Local"

\end_inset

.
 The fields of 
\begin_inset Formula $\omega$
\end_inset

 can be traced by the owner precisely because 
\begin_inset Formula $\omega$
\end_inset

 is immutable: it is safe for the owner to read the fields because no other
 actor will write to those fields.
\end_layout

\begin_layout Standard
As a result, sending and receiving an immutable object in a message requires
 
\begin_inset Formula $O(1)$
\end_inset

 tracing instead of 
\begin_inset Formula $O(n)$
\end_inset

.
 To achieve this, the per-object garbage collection information in figure
 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Object-GC-information"

\end_inset

 includes the flag 
\family typewriter
immutable
\family default
, which indicates the object is immutable and that the owner knows this.
 When that flag is 
\family typewriter
true
\family default
, the owner traces the fields of the object.
\end_layout

\begin_layout Standard
Maintaining this flag is trivial if the owner initially sends the immutable
 object.
 However, it is possible for some actor 
\begin_inset Formula $\alpha_{1}$
\end_inset

 that owns some object 
\begin_inset Formula $\omega$
\end_inset

 to send it as an isolated object, and then for some other actor 
\begin_inset Formula $\alpha_{2}$
\end_inset

 to later send 
\begin_inset Formula $\omega$
\end_inset

 as an immutable object to some receiver 
\begin_inset Formula $\alpha_{3}$
\end_inset

.
 In this case, 
\begin_inset Formula $\alpha_{1}$
\end_inset

 will have protected the fields of 
\begin_inset Formula $\omega$
\end_inset

 against premature garbage collection by tracing them when the message was
 sent, but 
\begin_inset Formula $\alpha_{2}$
\end_inset

 may have written to those fields before sending 
\begin_inset Formula $\omega$
\end_inset

 as an immutable object.
\end_layout

\begin_layout Standard
When 
\begin_inset Formula $\alpha_{2}$
\end_inset

 initially receives 
\begin_inset Formula $\omega$
\end_inset

, the flag will not be set, since 
\begin_inset Formula $\alpha_{1}$
\end_inset

 has sent 
\begin_inset Formula $\omega$
\end_inset

 as an isolated object.
 When 
\begin_inset Formula $\alpha_{2}$
\end_inset

 later sends 
\begin_inset Formula $\omega$
\end_inset

 as an immutable object, this discrepancy will be detected.
 At this point, 
\begin_inset Formula $\alpha_{2}$
\end_inset

 will mark 
\begin_inset Formula $\omega$
\end_inset

 as immutable in its foreign map, but it will also send an acquire message
 for 
\begin_inset Formula $\omega$
\end_inset

 to 
\begin_inset Formula $\alpha_{1}$
\end_inset

 with the 
\family typewriter
immutable
\family default
 flag set to 
\family typewriter
true
\family default
, as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Acquire-and-Release"

\end_inset

, and it will trace the fields of 
\begin_inset Formula $\omega$
\end_inset

 for the current message.
 Note that this process is recursive: all objects 
\begin_inset Formula $\omega'$
\end_inset

 reachable from 
\begin_inset Formula $\omega$
\end_inset

 that 
\begin_inset Formula $\alpha_{2}$
\end_inset

 sees as mutable are also marked as immutable, and the owners of such objects
 
\begin_inset Formula $\omega'$
\end_inset

 are sent acquire messages with the 
\family typewriter
immutable
\family default
 flag set to 
\family typewriter
true
\family default
.
\end_layout

\begin_layout Standard
This will result in 
\begin_inset Formula $\alpha_{1}$
\end_inset

 receiving an acquire message that tells 
\begin_inset Formula $\alpha_{1}$
\end_inset

 to mark 
\begin_inset Formula $\omega$
\end_inset

 as immutable in its local map 
\emph on
before
\emph default
 it receives any reference count decrement for 
\begin_inset Formula $\omega$
\end_inset

 from 
\begin_inset Formula $\alpha_{2}$
\end_inset

.
 At this point, 
\begin_inset Formula $\alpha_{2}$
\end_inset

 can safely send 
\begin_inset Formula $\omega$
\end_inset

 to 
\begin_inset Formula $\alpha_{3}$
\end_inset

 without tracing 
\begin_inset Formula $\omega$
\end_inset

.
 The object graph reachable by 
\begin_inset Formula $\omega$
\end_inset

 will be protected from premature collection because 
\begin_inset Formula $\alpha_{1}$
\end_inset

 will trace the fields of 
\begin_inset Formula $\omega$
\end_inset

 during garbage collection as long as 
\begin_inset Formula $\omega$
\end_inset

 itself is live, i.e.
 has a positive reference count.
\end_layout

\begin_layout Standard
When 
\begin_inset Formula $\alpha_{3}$
\end_inset

 receives 
\begin_inset Formula $\omega$
\end_inset

 as an immutable object from 
\begin_inset Formula $\alpha_{2}$
\end_inset

, 
\begin_inset Formula $\alpha_{3}$
\end_inset

 can safely mark 
\begin_inset Formula $\omega$
\end_inset

 as immutable in its foreign map, and not trace the fields of 
\begin_inset Formula $\omega$
\end_inset

 when receiving 
\begin_inset Formula $\omega$
\end_inset

.
 Indeed, all future sends of 
\begin_inset Formula $\omega$
\end_inset

, any corresponding receives, and future garbage collection phases by any
 actor other than 
\begin_inset Formula $\alpha_{1}$
\end_inset

 (the owner of 
\begin_inset Formula $\omega$
\end_inset

) need not trace 
\begin_inset Formula $\omega$
\end_inset

.
\end_layout

\begin_layout Standard
Effectively, 
\emph on
freezing
\emph default
 some isolated 
\begin_inset Formula $\omega$
\end_inset

, such that 
\begin_inset Formula $\omega$
\end_inset

 becomes deeply immutable, requires a single 
\begin_inset Formula $O(n)$
\end_inset

 tracing phase in order to replace future 
\begin_inset Formula $O(n)$
\end_inset

 tracing phases with an 
\begin_inset Formula $O(1)$
\end_inset

 change in the reference count of 
\begin_inset Formula $\omega$
\end_inset

.
\end_layout

\begin_layout Standard
A similar situation arises if 
\begin_inset Formula $\alpha_{3}$
\end_inset

 receives 
\begin_inset Formula $\omega$
\end_inset

 in a message, then reads some field 
\begin_inset Formula $\omega'$
\end_inset

 from 
\begin_inset Formula $\omega$
\end_inset

.
 It is then possible for 
\begin_inset Formula $\alpha_{3}$
\end_inset

 to drop its reference to 
\begin_inset Formula $\omega$
\end_inset

 while continuing to hold a reference to 
\begin_inset Formula $\omega'$
\end_inset

.
 To protect 
\begin_inset Formula $\omega'$
\end_inset

 from premature collection, 
\begin_inset Formula $\alpha_{3}$
\end_inset

 treats 
\begin_inset Formula $\omega'$
\end_inset

 as described above: an acquire message for 
\begin_inset Formula $\omega'$
\end_inset

 is sent to the owner of 
\begin_inset Formula $\omega'$
\end_inset

 (which may or may not be 
\begin_inset Formula $\alpha_{1}$
\end_inset

).
 This message is sent before the release message for 
\begin_inset Formula $\omega$
\end_inset

, as detailed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Acquire-and-Release"

\end_inset

, which correctly protects 
\begin_inset Formula $\omega'$
\end_inset

 while allowing 
\begin_inset Formula $\alpha_{1}$
\end_inset

 to possibly collect 
\begin_inset Formula $\omega$
\end_inset

.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Tracing-the-Local"

\end_inset

Tracing the Local Map
\end_layout

\begin_layout Standard
The local map is used by an actor to mark memory on its heap that it cannot
 reach as in-use because it may be reachable from some other actor.
 To do so, the map is iterated over, and every object with an 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 greater than zero is marked.
 If the object is also marked as 
\family typewriter
immutable
\family default
 in the describing 
\family typewriter
object_t
\family default
, it is placed on the trace stack with its trace function, so that its fields
 are traced as well, as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Sending-and-Receiving-2"

\end_inset

.
\end_layout

\begin_layout Standard
During this iteration, an object is removed from the local map if its local
 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 is zero.
 If the object has a finaliser, then it is only removed from the local map
 if it is also unreachable from the owning actor, at which point its finaliser
 is run as well.
 This is described in detail in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Finalisation"

\end_inset

.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Tracing-the-Foreign"

\end_inset

Tracing the Foreign Map
\end_layout

\begin_layout Standard
After an actor's reachable objects and local map are traced, the weighted
 reference count held for any objects in the actor's foreign map that have
 not been marked can be released.
 The object garbage collection information for an unreachable foreign object
 is removed from the foreign map and sent to the owning actor as a 
\emph on
release message
\emph default
, as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Acquire-and-Release"

\end_inset

.
 This is the implementation of the 
\noun on
Release
\noun default
 rule from figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:opsem-for-object-GC"

\end_inset

.
\end_layout

\begin_layout Standard
The organisation of the foreign map into a map of actors, each of which
 has a map of objects, allows these release messages to be easily aggregated.
 All of the unreachable foreign objects owned by some actor 
\begin_inset Formula $\alpha$
\end_inset

 are combined in a single message to 
\begin_inset Formula $\alpha$
\end_inset

.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Acquire-and-Release"

\end_inset

Acquire and Release Messages
\end_layout

\begin_layout Standard
An owning actor adjusts the local 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 for an object both implicitly when sending or receiving the object in a
 message, and explicitly when it receives acquire and release messages generated
 by other actors.
\end_layout

\begin_layout Standard
Acquire messages are generated when some actor 
\begin_inset Formula $\alpha$
\end_inset

 sends some foreign object 
\begin_inset Formula $\omega_{1}$
\end_inset

 for which it has a foreign 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 of one or less, or when 
\begin_inset Formula $\alpha$
\end_inset

 traces its reachable objects and discovers an immutable object 
\begin_inset Formula $\omega_{1}$
\end_inset

 that is not in 
\begin_inset Formula $\alpha$
\end_inset

's foreign map because it was previously reachable only via some other immutable
 object 
\begin_inset Formula $\omega_{2}$
\end_inset

 that is in 
\begin_inset Formula $\alpha$
\end_inset

's foreign map.
 In both these cases, 
\begin_inset Formula $\alpha$
\end_inset

 is free to increase its weighted reference count for 
\begin_inset Formula $\omega_{1}$
\end_inset

 by an arbitrary amount and inform the owner of 
\begin_inset Formula $\omega_{1}$
\end_inset

 that it has done so.
\end_layout

\begin_layout Standard
This is accomplished by building an alternate foreign map during a garbage
 collection phase that consists of the objects that need to be acquired.
 The structure used is the same as the foreign map.
 When the phase completes, each actor in the acquire map is sent the accumulated
 actor garbage collection information, as described in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Actor-GC-information"

\end_inset

, as an acquire message.
 When that acquire message is received by the owning actor, the 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 for each object is added to its local 
\begin_inset Formula $\mathtt{rc}$
\end_inset

.
\end_layout

\begin_layout Standard
Release messages are generated when an actor finishes a garbage collection
 pass.
 Unmarked objects in the foreign map are removed and sent to their owning
 actor.
 Like acquire messages, these are aggregated, so that each owning actor
 is sent at most a single release message as the result of a garbage collection
 pass.
 When that release message is received by the owning actor, the 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 for each object is subtracted from its local 
\begin_inset Formula $\mathtt{rc}$
\end_inset

.
\end_layout

\begin_layout Section
\begin_inset CommandInset label
LatexCommand label
name "sec:Actor-GC"

\end_inset

Actor GC
\end_layout

\begin_layout Standard
The garbage collection mechanism described in sections 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Tracing-GC"

\end_inset

 and 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Sharing-GC"

\end_inset

 collects objects allocated on actor heaps, even when those objects are
 shared across actors.
 The same mechanism is extended in the runtime to garbage collect actors
 themselves.
\end_layout

\begin_layout Standard
Each actor keeps track of a local 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 for itself in the structure described in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Tracking-local-and"

\end_inset

.
 This local actor 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 works in the same fashion as a local 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 for an object.
 Similarly, actors keep a foreign 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 for every other actor they can reach, in the structure described in figure
 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Actor-GC-information"

\end_inset

.
 These weighted reference counts are managed in the same way as for objects.
\end_layout

\begin_layout Standard
As a result, an actor can be garbage collected when it is both blocked,
 as discussed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Blocking-and-Unblocking"

\end_inset

, and its local 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 is zero.
 This condition is sufficient, but not necessary: an isolated graph of blocked
 actors may be collectable even if each actor's local 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 is not zero, as described in chapter 
\begin_inset CommandInset ref
LatexCommand ref
reference "chap:Actor-Collection"

\end_inset

.
 The implementation is described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:The-Cycle-Detector"

\end_inset

.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Implicit-Actor-Reachability"

\end_inset

Implicit Actor Reachability
\end_layout

\begin_layout Standard
An actor is implicitly reachable from an object if it owns that object.
 This prevents an actor from being collected, and its heap destroyed, if
 any object on its heap is reachable.
 To account for this, during each garbage collection phase, if a foreign
 object is marked, the owner of that foreign object is also marked.
\end_layout

\begin_layout Standard
This means that it is possible to mark an actor that does not appear in
 the foreign map.
 This happens when an immutable object that is not in the foreign map is
 encountered, as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Sending-and-Receiving-2"

\end_inset

.
 When this occurs, the same mechanism is used: the actor is inserted into
 the foreign map and an acquire message is generated for that actor.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Topology-Deltas"

\end_inset

Topology Deltas
\end_layout

\begin_layout Standard
In addition to the local and foreign maps, each actor keeps an additional
 data structure that describes the change in the actor's view of its own
 topology since the last time that actor blocked.
 This is a simple map of actor address to a reference count, as shown in
 figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Topology-delta-information"

\end_inset

.
 Note that these are stored in the 
\family typewriter
deltamap_t
\family default
 contained in each actor's 
\family typewriter
gc_t
\family default
, as shown in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Tracking-local-and"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

typedef struct delta_t {
\end_layout

\begin_layout Plain Layout

  pony_actor_t* actor;
\end_layout

\begin_layout Plain Layout

  size_t rc;
\end_layout

\begin_layout Plain Layout

} delta_t; 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Topology-delta-information"

\end_inset

Topology delta information
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
When some actor 
\begin_inset Formula $\alpha_{1}$
\end_inset

 changes its local 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 for some actor 
\begin_inset Formula $\alpha_{2}$
\end_inset

, the new 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 is stored both in the foreign map and in the topology delta.
 When 
\begin_inset Formula $\alpha_{1}$
\end_inset

 blocks, its topology delta is sent to the cycle detector, and it begins
 again with an empty topology delta.
\end_layout

\begin_layout Standard
As a result, an actor that blocks sends the cycle detector only the minimal
 information that the cycle detector needs to recreate the actor's view
 of its own topology.
 This eliminates an 
\begin_inset Formula $O(n)$
\end_inset

 step to gather local topology when an actor blocks, where 
\begin_inset Formula $n$
\end_inset

 is the number of other actors that actor has in its foreign map.
 This is replaced with an 
\begin_inset Formula $O(1)$
\end_inset

 step for each local topology change, no cost when sending a block message,
 and an 
\begin_inset Formula $O(m)$
\end_inset

 step when the cycle detector receives a block message, where 
\begin_inset Formula $m$
\end_inset

 is the number of actors for which a topology change occurred.
 Importantly, 
\begin_inset Formula $m<n$
\end_inset

, possibly significantly less, and the step is performed in the cycle detector
 rather than in a program actor.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:The-Cycle-Detector"

\end_inset

The Cycle Detector
\end_layout

\begin_layout Standard
Unlike shared object collection, it is possible to have an isolated cyclic
 graph of actors where all the actors in the graph are blocked, and their
 local 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 is held entirely by other blocked actors in the graph, but the actors are
 not collectable because their local 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 is not zero, as detailed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Cycle-Detection"

\end_inset

.
\end_layout

\begin_layout Standard
The cycle detector is implemented as an actor in the runtime.
 It is instantiated when a program begins, and its address is kept as global
 data with ambient authority.
 That is, all actors can implicitly send messages to the cycle detector.
 However, the cycle detector does not itself take part in garbage collection.
 The memory it uses is manually managed, and its references to actors that
 have reported their topology do not influence local or foreign reference
 counts.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

struct view_t {
\end_layout

\begin_layout Plain Layout

  pony_actor_t* actor;
\end_layout

\begin_layout Plain Layout

  size_t rc;
\end_layout

\begin_layout Plain Layout

  uint32_t view_rc;
\end_layout

\begin_layout Plain Layout

  bool blocked;
\end_layout

\begin_layout Plain Layout

  bool deferred;
\end_layout

\begin_layout Plain Layout

  uint8_t color;
\end_layout

\begin_layout Plain Layout

  viewrefmap_t map;
\end_layout

\begin_layout Plain Layout

  deltamap_t* delta;
\end_layout

\begin_layout Plain Layout

  perceived_t* perceived;
\end_layout

\begin_layout Plain Layout

};
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

typedef struct viewref_t {
\end_layout

\begin_layout Plain Layout

  view_t* view;
\end_layout

\begin_layout Plain Layout

  size_t rc;
\end_layout

\begin_layout Plain Layout

} viewref_t; 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:A-view-of"

\end_inset

The cycle detector's representation of a view of an actor's topology
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

typedef struct detector_t {
\end_layout

\begin_layout Plain Layout

  pony_actor_pad_t pad; 
\end_layout

\begin_layout Plain Layout

  size_t next_token;
\end_layout

\begin_layout Plain Layout

  size_t min_deferred;
\end_layout

\begin_layout Plain Layout

  size_t max_deferred;
\end_layout

\begin_layout Plain Layout

  size_t conf_group;
\end_layout

\begin_layout Plain Layout

  size_t next_deferred;
\end_layout

\begin_layout Plain Layout

  size_t since_deferred;
\end_layout

\begin_layout Plain Layout

  viewmap_t views;
\end_layout

\begin_layout Plain Layout

  viewmap_t deferred;
\end_layout

\begin_layout Plain Layout

  perceivedmap_t perceived;
\end_layout

\begin_layout Plain Layout

  size_t attempted;
\end_layout

\begin_layout Plain Layout

  size_t detected;
\end_layout

\begin_layout Plain Layout

  size_t collected;
\end_layout

\begin_layout Plain Layout

  size_t created;
\end_layout

\begin_layout Plain Layout

  size_t destroyed;
\end_layout

\begin_layout Plain Layout

} detector_t;
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

struct perceived_t {
\end_layout

\begin_layout Plain Layout

  size_t token;
\end_layout

\begin_layout Plain Layout

  size_t ack;
\end_layout

\begin_layout Plain Layout

  size_t last_conf;
\end_layout

\begin_layout Plain Layout

  viewmap_t map;
\end_layout

\begin_layout Plain Layout

}; 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Cycle-detector-state"

\end_inset

Cycle detector state
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
The cycle detector's representation of a view of an actor's topology is
 shown in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:A-view-of"

\end_inset

.
 Here, the 
\family typewriter
rc
\family default
 is the actor's last reported view of its own local reference count.
 The 
\family typewriter
view_rc
\family default
 is used internally to manually manage the view structure memory.
 The 
\family typewriter
blocked
\family default
 flag indicates the actor's last report of whether or not it believed it
 had an empty message queue.
 The 
\family typewriter
deferred 
\family default
flag is set if the actor is in the 
\family typewriter
deferred
\family default
 map, as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Block-Messages"

\end_inset

.
 The 
\family typewriter
color
\family default
 is used in a tri-colour tracing scheme for finding isolated graphs of actors,
 as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Finding-Isolated-Graphs"

\end_inset

.
 The 
\family typewriter
map
\family default
 is a map of 
\family typewriter
viewref_t
\family default
, tracking the actor's last reported references to other actors, and the
 
\family typewriter
rc 
\family default
held for each.
 The 
\family typewriter
delta
\family default
 pointer keeps the last topology delta reported by the actor.
 This is applied to the 
\family typewriter
map
\family default
 in a deferred manner, as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Block-Messages"

\end_inset

.
 Finally, the 
\family typewriter
perceived
\family default
 pointer is a reference to the perceived cycle the actor is a member of,
 if any, as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Finding-Isolated-Graphs"

\end_inset

.
\end_layout

\begin_layout Standard
The cycle detector's view of the actor topology is tracked in the 
\begin_inset Formula $\mathtt{views}$
\end_inset

 map of actor addresses to topology views, as shown in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Cycle-detector-state"

\end_inset

.
 In addition, the cycle detector keeps track of the next confirmation-acknowledg
ment token, detailed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Acknowledgement-Messages"

\end_inset

, state related to deferred checks for isolated graphs of blocked actors,
 detailed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Finding-Isolated-Graphs"

\end_inset

, a map of tokens to perceived cycles, and some useful debugging statistics.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Block-Messages"

\end_inset

Block Messages 
\end_layout

\begin_layout Standard
When an actor believes it has blocked, as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Blocking-and-Unblocking"

\end_inset

, it sends a message to the cycle detector indicating that it is blocked,
 and also indicating the actor's view of its own topology.
 This is sent as the actor's view of its own local reference count, from
 the structure in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Tracking-local-and"

\end_inset

, and its topology delta, as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Topology-Deltas"

\end_inset

.
\end_layout

\begin_layout Standard
When the cycle detector receives a block message from an actor, it first
 retrieves the actor from the 
\begin_inset Formula $\mathtt{views}$
\end_inset

 map in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Cycle-detector-state"

\end_inset

, or adds it if the actor is not yet present.
 The cycle detector updates the view 
\begin_inset Formula $\mathtt{rc}$
\end_inset

 with the value reported by the actor.
 Any previous topology delta that has been cached in the 
\begin_inset Formula $\mathtt{delta}$
\end_inset

 field of the view is applied to the actor, as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Apply-Topology-Deltas"

\end_inset

.
 The current topology delta is then cached in the 
\begin_inset Formula $\mathtt{delta}$
\end_inset

 field.
 This delayed application of the topology delta is used to avoid unnecessary
 work by the cycle detector.
\end_layout

\begin_layout Standard
The actor is then marked as 
\begin_inset Formula $\mathtt{blocked}$
\end_inset

, and any perceived cycles (as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Finding-Isolated-Graphs"

\end_inset

) that the actor is a member of are cancelled.
 Note that perceived cycles are cancelled due to block messages as well
 as due to unblock messages (as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Unblock-Messages"

\end_inset

).
 This allows actors that update their view of their own 
\family typewriter
rc
\family default
 while blocked, due to receiving acquire and release messages as described
 in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Acquire-and-Release"

\end_inset

, to send a new block message to the cycle detector to update the cycle
 detector's view of the actor's topology.
 An actor with a new view of its topology is not collectable on the basis
 of its old view of its topology, and so any perceived cycle detected based
 on the old topology must be cancelled.
\end_layout

\begin_layout Standard
If the actor's perceived reference count is zero, it is removed from the
 
\begin_inset Formula $\mathtt{deferred}$
\end_inset

 map and immediately collected.
 Otherwise, the actor is added to the 
\begin_inset Formula $\mathtt{deferred}$
\end_inset

 map.
 The 
\begin_inset Formula $\mathtt{deferred}$
\end_inset

 map is used to reduce the total work done by the cycle detector.
 Rather than finding isolated graphs of blocked actors every time an actor
 blocks, the process is deferred until some number of actors have blocked.
 At that point, some actor in the 
\begin_inset Formula $\mathtt{deferred}$
\end_inset

 map is chosen as a starting point, and an attempt is made.
 If the attempt touches actors in the 
\begin_inset Formula $\mathtt{deferred}$
\end_inset

 map, they are removed from the map, effectively reducing the total number
 of isolated graph searches.
 Finding or not finding an isolated graph is used as a feedback mechanism
 to the number of deferred actors required to trigger a detection attempt.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Apply-Topology-Deltas"

\end_inset

Applying Topology Deltas
\end_layout

\begin_layout Standard
Topology deltas are applied lazily, in order to avoid the work required
 to update a topology until the blocked actor's view of its own topology
 is required for a cycle detection attempt, or until the blocked actor sends
 another topology update to the cycle detector.
 The topology delta map shown in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Topology-delta-information"

\end_inset

 is applied to the 
\begin_inset Formula $\mathtt{viewrefmap\_t}$
\end_inset

 from figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:A-view-of"

\end_inset

.
 Each entry in the delta map sets a new reference count that some actor
 
\begin_inset Formula $\alpha$
\end_inset

 whose topology is being updated holds for some other actor 
\begin_inset Formula $\alpha'$
\end_inset

.
 
\end_layout

\begin_layout Standard
If the cycle detector did not previously see 
\begin_inset Formula $\alpha$
\end_inset

 as holding a reference count for 
\begin_inset Formula $\alpha'$
\end_inset

, then 
\begin_inset Formula $\alpha'$
\end_inset

 is added to the 
\begin_inset Formula $\mathtt{viewrefmap\_t}$
\end_inset

 of 
\begin_inset Formula $\alpha$
\end_inset

.
 Doing so increments the 
\begin_inset Formula $\mathtt{view\_rc}$
\end_inset

 field of the 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 the cycle detector holds for 
\begin_inset Formula $\alpha'$
\end_inset

.
 This provides a simple acyclic reference count for 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 structures.
 The purpose of the reference count is to allow a 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 to hold an out-of-date reference to an actor that has already been collected.
\end_layout

\begin_layout Standard
For example, suppose 
\begin_inset Formula $\alpha_{1}$
\end_inset

 holds the only reference to 
\begin_inset Formula $\alpha_{2}$
\end_inset

 and both actors block.
 Later, 
\begin_inset Formula $\alpha_{1}$
\end_inset

 unblocks and drops its reference to 
\begin_inset Formula $\alpha_{2}$
\end_inset

, which remains blocked.
 At this point, 
\begin_inset Formula $\alpha_{2}$
\end_inset

 can be collected, even though the cycle detector has an out-of-date topology
 for 
\begin_inset Formula $\alpha_{1}$
\end_inset

 in which 
\begin_inset Formula $\alpha_{1}$
\end_inset

 still holds a reference for 
\begin_inset Formula $\alpha_{2}$
\end_inset

.
 By using a reference counted 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 structure, the cycle detector avoids keeping inverse reference lists for
 actors or searching for all actors with out-of-date references to an actor
 that is being collected.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Unblock-Messages"

\end_inset

Unblock Messages
\end_layout

\begin_layout Standard
When an actor 
\begin_inset Formula $\alpha$
\end_inset

 unblocks, it notifies the cycle detector.
 When the cycle detector receives an unblock message from 
\begin_inset Formula $\alpha$
\end_inset

, it removes 
\begin_inset Formula $\alpha$
\end_inset

 from the 
\begin_inset Formula $\mathtt{deferred}$
\end_inset

 map if it is present and cancels all perceived cycles that 
\begin_inset Formula $\alpha$
\end_inset

 is a member of.
 Rather than search all perceived cycles, each 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 keeps a map of perceived cycle that the actor is a member of.
 This allows the cycles to be cancelled directly.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Finding-Isolated-Graphs"

\end_inset

Finding Isolated Graphs of Blocked Actors
\end_layout

\begin_layout Standard
Detecting isolated graphs is done using a tri-colour algorithm that combines
 finding graphs with determining if the cycle's view of the graph topology
 indicates that the graph is isolated.
 The algorithm divides actors into three sets:
\end_layout

\begin_layout Itemize
The white set are actors that are candidates for collection.
 The cycle detector's view of the actor topology indicates that these actors
 have no incoming edges from unblocked actors.
\end_layout

\begin_layout Itemize
The black set are actors that cannot be collected.
 The cycle detector's view of the actor topology indicates that these actors
 have incoming edges from unblocked actors.
\end_layout

\begin_layout Itemize
The grey set are actors that have not yet been scanned for outgoing edges.
\end_layout

\begin_layout Standard
The algorithm preserves the strong tri-colour invariant 
\begin_inset CommandInset citation
LatexCommand cite
key "pirinen1998barrier"

\end_inset

: there is no edge from a black node to a white node.
 To achieve this, all 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 structures begin coloured black.
 A 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 from the 
\begin_inset Formula $\mathtt{deferred}$
\end_inset

 map is selected as the entry point and placed on a processing stack with
 an incoming reference count of zero.
 Elements are popped from the stack and processed until the stack is empty.
\end_layout

\begin_layout Standard
For each element, when it is popped from the stack with some incoming reference
 count:
\end_layout

\begin_layout Enumerate
If the 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 has a deferred topology delta, it is applied.
\end_layout

\begin_layout Enumerate
If the 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 is in the 
\begin_inset Formula $\mathtt{deferred}$
\end_inset

 map, it is removed.
 This is the key step in allowing the 
\begin_inset Formula $\mathtt{deferred}$
\end_inset

 map to reduce the overall work performed by the cycle detector.
\end_layout

\begin_layout Enumerate
The incoming reference count on the stack is subtracted from the cycle detector'
s view of the actor's view of it's own reference count.
\end_layout

\begin_layout Enumerate
If the 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 is not coloured grey, then it is coloured grey and the elements of its
 
\begin_inset Formula $\mathtt{viewref}$
\end_inset

 map are pushed on the stack.
 The outgoing reference count from the current actor is pushed as the incoming
 reference count on the processing stack.
\end_layout

\begin_layout Standard
When this process is complete, all actors reachable from the initially selected
 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 are marked grey, including the initial actor.
 Another scan is performed, this time looking for 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 entries with zero reference counts.
 The process begins with the same initial 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 being pushed on the processing stack.
 Stack processing in this phase consists of:
\end_layout

\begin_layout Enumerate
If the 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 is not marked grey, it is skipped.
\end_layout

\begin_layout Enumerate
If the 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 has a reference count of zero, it is marked white.
\end_layout

\begin_layout Enumerate
Otherwise, the 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 is marked black, and a scan using a new stack is begun starting from that
 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

.
 This scan marks each reachable 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 black.
\end_layout

\begin_layout Standard
Upon completion, all actors reachable from the initially selected 
\begin_inset Formula $\mathtt{view\_t}$
\end_inset

 will be marked black or white.
 The actors marked white form a 
\emph on
perceived cycle
\emph default
 and are candidates for collection.
 The perceived cycle is stored as a 
\family typewriter
perceived_t
\family default
, as shown in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Cycle-detector-state"

\end_inset

, and is added to the map of tokens to perceived cycles kept by the cycle
 detector.
\end_layout

\begin_layout Standard
If no actors are marked white (i.e.
 no perceived cycle is detected), the cycle detector will increase the threshold
 of deferred actors required before another cycle detection attempt is made.
 Similarly, if a perceived cycle is detected, the cycle detector will decrease
 the threshold.
 The result is an adaptive cycle detector that will collect more often when
 a program has short-lived actors and less often when a program has long-lived
 actors.
\end_layout

\begin_layout Subsection
Confirmation Messages
\end_layout

\begin_layout Standard
When a perceived cycle is detected, confirmation messages are sent to the
 members of the perceived cycle.
 Rather than send confirmation messages to all actors in the perceived cycle,
 an initial subset is sent messages.
 Additional messages are sent when acknowledgment messages arrive for a
 perceived cycle that has not been cancelled.
 This deferment reduces the number of confirmation messages sent when a
 perceived cycle is cancelled.
\end_layout

\begin_layout Standard
Confirmation messages carry a token identifying the perceived cycle.
 Rather than use the perceived cycle's memory address, which could be reused
 if a perceived cycle were cancelled and a new one detected, a 64 bit integer
 is used as a monotonic counter.
 A perceived cycle is simply assigned the next integer.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Acknowledgement-Messages"

\end_inset

Acknowledgement Messages
\end_layout

\begin_layout Standard
Actors respond to confirmation messages by echoing an acknowledgement message
 with the perceived cycle token back to the cycle detector.
 When the cycle detector receives an acknowledgement message, the token
 echoed back is used to look up the 
\family typewriter
perceived_t
\family default
 that represents the perceived cycle in the 
\family typewriter
perceived
\family default
 map.
 The acknowledgment count, 
\family typewriter
ack
\family default
, for the perceived cycle is incremented.
 In addition, if any actors in the perceived cycle have not yet been sent
 a confirmation message, an additional confirmation message is sent.
\end_layout

\begin_layout Standard
If the cycle detector receives an unblock message from any member of a perceived
 cycle, that cycle is cancelled, as in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Unblock-Messages"

\end_inset

.
 If an acknowledgement message arrives for a cancelled cycle, it is ignored.
\end_layout

\begin_layout Standard
When a perceived cycle has received acknowledgement messages from all actors
 in the perceived cycle, it is a 
\emph on
true cycle
\emph default
, and all actors in the cycle can be collected.
\end_layout

\begin_layout Subsection
Actor Collection
\end_layout

\begin_layout Standard
Actors are collected by the cycle detector when a perceived cycle is fully
 acknowledged.
 Each actor in the cycle is marked as 
\emph on
pending destruction 
\emph default
and its finaliser is run, as described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Finalisation"

\end_inset

.
 Following this, each actor generates release messages for actors in its
 foreign map that are not marked as pending destruction.
 This avoids sending unnecessary release messages within the cycle, while
 correctly releasing held reference count for actors and objects outside
 the cycle.
\end_layout

\begin_layout Standard
Each actor is then destroyed, freeing everything allocated on its heap as
 well as the heap structure itself, any garbage collection data such as
 local and foreign maps, and the remaining stub message in its message queue.
 Importantly, before destruction of some actor 
\begin_inset Formula $\alpha$
\end_inset

 can proceed, it is necessary to wait in a tight loop until the message
 queue head for 
\begin_inset Formula $\alpha$
\end_inset

 has had its lower bit marked, indicating that it is empty, as described
 in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Empty-Queue-Detection"

\end_inset

.
 This is required because it is possible for 
\begin_inset Formula $\alpha$
\end_inset

 to send a block message but not yet have marked its queue as empty in some
 thread 
\begin_inset Formula $t_{1}$
\end_inset

 while the cycle detector is collecting it in another thread 
\begin_inset Formula $t_{2}$
\end_inset

.
 Waiting until the queue is marked empty prevents 
\begin_inset Formula $\alpha$
\end_inset

 from failing to mark its queue as empty because the queue has itself been
 collected.
 Such a failure would result in spuriously rescheduling 
\begin_inset Formula $\alpha$
\end_inset

 for execution after it has been destroyed.
\end_layout

\begin_layout Standard
This race condition can occur even though 
\begin_inset Formula $\alpha$
\end_inset

 marks its queue as empty immediately after sending the block message.
\end_layout

\begin_layout Section
\begin_inset CommandInset label
LatexCommand label
name "sec:Finalisation"

\end_inset

Finalisation
\end_layout

\begin_layout Standard
The runtime supports both actor and object finalisation.
 This was a difficult decision to take, as finalisation can cause significant
 problems, such as resurrection.
 In addition, the non-deterministic finalisation that occurs in a garbage
 collected environment interacts poorly with releasing non-memory resources,
 which is the most common task of a finaliser.
\end_layout

\begin_layout Standard
However, for interacting with non-memory system resources, a finaliser provides
 a guarantee that the resource will be 
\emph on
eventually
\emph default
 released, which is critical.
 Designing interfaces that also encourage 
\emph on
explicit
\emph default
 resource release, using a 
\begin_inset Formula $\mathtt{dispose}$
\end_inset

 method, allows the programmer to achieve deterministic resource management,
 which combines well with a finaliser that acts as a backstop.
\end_layout

\begin_layout Standard
Pony provides a less problematic finalisation sequence by using a combination
 of reference capabilities and pessimistic static analysis.
 Finalisers on both actors and objects run with a 
\begin_inset Formula $\mathtt{box}$
\end_inset

 capability, with no arguments.
 As a result, finalisers cannot cause resurrection by mutating the object
 graph: the object being finalised can reach only itself and the transitive
 closure of objects reachable via its fields, and due to viewpoint adaptation
 has no write access to any part of that graph.
 It is possible for finalisers to 
\emph on
create
\emph default
 new objects, and to mutate those objects, but such objects cannot outlive
 the finaliser unless they are sent in a message to another actor, so they
 do not result in resurrection.
\end_layout

\begin_layout Standard
It is not only new objects that could outlive the finaliser if sent in a
 message: any part of the object graph could be sent as a 
\begin_inset Formula $\mathtt{tag}$
\end_inset

 in a message, resulting in resurrection.
 To curtail this, pessimistic static analysis is used when compiling finaliser
 methods.
 Any expression that could result in sending a message is prohibited in
 a finaliser.
 This is extremely strict, as it prevents method calls on objects with an
 
\begin_inset Formula $\mathtt{interface}$
\end_inset

 or 
\begin_inset Formula $\mathtt{trait}$
\end_inset

 type, as the concrete implementation of the method is not known at compile
 time.
 However, in practice, objects and actors being finalised should be freeing
 non-memory resources held by the instance itself, rather than interacting
 with other parts of the objects graph (which can be independently finalised
 if necessary).
 As a result, this restriction has not so far proven to be problematic in
 the standard library or in end-user code.
\end_layout

\begin_layout Section
\begin_inset CommandInset label
LatexCommand label
name "sec:Scheduler"

\end_inset

Scheduler
\end_layout

\begin_layout Standard
The Pony runtime uses a work-stealing scheduler built around single-producer
 multi-consumer queues of actors with pending work.
 The runtime can be started with any number of scheduler threads, defaulting
 to the number of cores on the machine.
 Threads are pinned to cores, and, on a NUMA machine, thread stacks are
 allocated on the local NUMA node.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

struct scheduler_t {
\end_layout

\begin_layout Plain Layout

  // These are rarely changed.
\end_layout

\begin_layout Plain Layout

  pony_thread_id_t tid;
\end_layout

\begin_layout Plain Layout

  uint32_t cpu;
\end_layout

\begin_layout Plain Layout

  uint32_t node;
\end_layout

\begin_layout Plain Layout

  bool terminate;
\end_layout

\begin_layout Plain Layout

  bool asio_stopped;
\end_layout

\begin_layout Plain Layout

  
\end_layout

\begin_layout Plain Layout

  // These are changed primarily by the owning scheduler thread.
  
\end_layout

\begin_layout Plain Layout

  __pony_spec_align__(struct scheduler_t* last_victim, 64);
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

  pony_ctx_t ctx;
\end_layout

\begin_layout Plain Layout

  uint32_t block_count;
\end_layout

\begin_layout Plain Layout

  int32_t ack_token;
\end_layout

\begin_layout Plain Layout

  uint32_t ack_count;
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

  // These are accessed by other scheduler threads.
 The mpmcq_t is aligned.
\end_layout

\begin_layout Plain Layout

  mpmcq_t q;
\end_layout

\begin_layout Plain Layout

  messageq_t mq;
\end_layout

\begin_layout Plain Layout

};
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Scheduler-thread-state"

\end_inset

Scheduler thread state
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
A scheduler thread has a queue of actors, described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Scheduler-Queues"

\end_inset

, a message queue that is used to detect quiescence, described in section
 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Quiescence"

\end_inset

, and a victim indicator that is used for round-robin work-stealing, as
 described in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Work-Stealing"

\end_inset

.
\end_layout

\begin_layout Standard
Each scheduler thread also keeps a context, which holds per-thread runtime
 information that would otherwise be encoded as thread-local storage.
 This is done to improve performance on platforms where thread-local storage
 is less efficient.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "sec:Scheduler-Queues"

\end_inset

SPMC Queues
\end_layout

\begin_layout Standard
Each scheduler has a single-producer multi-consumer queue of actors that
 may have pending work.
 These queues are effectively the inverse of actor message queues.
 They are single-producer because only the owning scheduler thread will
 place work (in the form of an actor that may have pending work) on the
 queue, but any scheduler thread can remove work from the queue, in order
 to enable work-stealing, as detailed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Work-Stealing"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

void ponyint_mpmcq_push_single(mpmcq_t* q,
\end_layout

\begin_layout Plain Layout

  void* data) {
\end_layout

\begin_layout Plain Layout

  mpmcq_node_t* node = POOL_ALLOC(mpmcq_node_t);
\end_layout

\begin_layout Plain Layout

  atomic_store_explicit(&node->data, data,
\end_layout

\begin_layout Plain Layout

    memory_order_relaxed);
\end_layout

\begin_layout Plain Layout

  atomic_store_explicit(&node->next, NULL,
\end_layout

\begin_layout Plain Layout

    memory_order_relaxed);
\end_layout

\begin_layout Plain Layout

  mpmcq_node_t* prev = atomic_load_explicit(
\end_layout

\begin_layout Plain Layout

    &q->head, memory_order_relaxed);
\end_layout

\begin_layout Plain Layout

  atomic_store_explicit(&q->head, node,
\end_layout

\begin_layout Plain Layout

    memory_order_relaxed);
\end_layout

\begin_layout Plain Layout

  atomic_store_explicit(&prev->next, node,
\end_layout

\begin_layout Plain Layout

    memory_order_release);
\end_layout

\begin_layout Plain Layout

} 
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Pushing-to-a-1"

\end_inset

Pushing to a scheduler queue
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

void* ponyint_mpmcq_pop(mpmcq_t* q) {
\end_layout

\begin_layout Plain Layout

  mpmcq_node_t* cmp, xchg, next, tail;
\end_layout

\begin_layout Plain Layout

  cmp = atomic_load_explicit(&q->tail,
\end_layout

\begin_layout Plain Layout

    memory_order_acquire);
\end_layout

\begin_layout Plain Layout

  uintptr_t mask = UINTPTR_MAX ^
\end_layout

\begin_layout Plain Layout

    ((1 << (POOL_MIN_BITS +
\end_layout

\begin_layout Plain Layout

      POOL_INDEX(sizeof(mpmcq_node_t*)))) - 1);
\end_layout

\begin_layout Plain Layout

  do {
\end_layout

\begin_layout Plain Layout

    uintptr_t aba = (uintptr_t)cmp & ~mask;
\end_layout

\begin_layout Plain Layout

    tail = (mpmcq_node_t*)((uintptr_t)cmp & mask);
\end_layout

\begin_layout Plain Layout

    next = atomic_load_explicit(&tail->next,
\end_layout

\begin_layout Plain Layout

      memory_order_acquire);
\end_layout

\begin_layout Plain Layout

    if(next == NULL)
\end_layout

\begin_layout Plain Layout

      return NULL;
\end_layout

\begin_layout Plain Layout

    xchg = (mpmcq_node_t*)((uintptr_t)next
\end_layout

\begin_layout Plain Layout

      | ((aba + 1) & ~mask));
\end_layout

\begin_layout Plain Layout

  } while(!atomic_compare_exchange_weak_explicit(
\end_layout

\begin_layout Plain Layout

      &q->tail, &cmp, xchg, memory_order_acq_rel,
\end_layout

\begin_layout Plain Layout

      memory_order_relaxed));
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

  void* data = atomic_load_explicit(&next->data, 
\end_layout

\begin_layout Plain Layout

    memory_order_relaxed);
\end_layout

\begin_layout Plain Layout

  atomic_store_explicit(&next->data, NULL, 
\end_layout

\begin_layout Plain Layout

    memory_order_release);
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

  while(atomic_load_explicit(&tail->data,
\end_layout

\begin_layout Plain Layout

    memory_order_acquire) != NULL)
\end_layout

\begin_layout Plain Layout

    ponyint_cpu_relax();
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

  POOL_FREE(mpmcq_node_t, tail);
\end_layout

\begin_layout Plain Layout

  return data;
\end_layout

\begin_layout Plain Layout

}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:Popping-from-a-1"

\end_inset

Popping from a scheduler queue
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
As seen in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Pushing-to-a-1"

\end_inset

, pushing to a scheduler queue is lock-free, wait-free, and requires zero
 atomic operations (aligned stores always being atomic on common architectures).
 However, in figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Popping-from-a-1"

\end_inset

 we see that popping from a scheduler queue is more complex.
 A compare-and-swap loop is necessary, to allow multiple schedulers to pop
 actors from a scheduler queue.
 This necessitates an ABA counter to avoid a situation where a CAS succeeds
 on queue node, but should fail, as the queue node has actually been popped
 and replaced on the queue.
 In addition, there is a second loop, where the data pointer of the queue
 node must be 
\begin_inset Formula $\mathtt{NULL}$
\end_inset

 in order to continue.
 This is because the pop operation frees the 
\emph on
previous
\emph default
 queue node.
 For that to be safe, any previous consumer must be finished reading the
 data pointer from the queue node.
 By setting the data pointer to 
\begin_inset Formula $\mathtt{NULL}$
\end_inset

 and testing for the previous data pointer being 
\begin_inset Formula $\mathtt{NULL}$
\end_inset

, consumers can coordinate memory management without locks.
\end_layout

\begin_layout Standard
If this step were to happen on every queue pop, the coordination cost would
 be very high.
 However, it occurs only when a scheduler thread successfully steals work
 from another thread.
 Otherwise, a scheduler thread will only be coordinating with itself, and
 no cost will be paid.
\end_layout

\begin_layout Standard
Like message queues, it is important that scheduler queues are unbounded.
 An actor 
\begin_inset Formula $\alpha$
\end_inset

 executing on a scheduler thread 
\begin_inset Formula $t$
\end_inset

 may generate an unbounded number of messages.
 In doing so, an unbounded number of previously unscheduled actors may need
 to be scheduled.
 A bounded scheduler queue would make this impossible, resulting in situations
 similar to those outlined for message queues in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Unbounded-Message-Queues"

\end_inset

.
\end_layout

\begin_layout Standard
The SPMC queue uses a compare-and-swap loop to pop, and so it could suffer
 from CAS-failure related scalability problems on the x86/x64 architecture
 
\begin_inset CommandInset citation
LatexCommand cite
key "michael1996simple"

\end_inset

.
 These problems could be reduced while maintaining an unbounded queue by
 using a linearizable concurrent ring queue (LCRQ), also in 
\begin_inset CommandInset citation
LatexCommand cite
key "michael1996simple"

\end_inset

.
 However, an LCRQ requires additional overhead in the form of an atomic
 fetch-and-add in addition to the CAS on pop, and requiring an atomic fetch-and-
add and CAS on push, as well as requiring individual concurrent ring queues
 (CRQs) to be used as nodes in a Michael and Scott list.
 This overhead reduces CAS failures by reducing CAS contention.
 The Pony SPMC queues reduce CAS contention by requiring scheduler threads
 to pop from SPMC queues in a round robin fashion, as described in section
 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Work-Stealing"

\end_inset

.
 This is an interesting research area, and it may be possible to use a combinati
on of these techniques to further reduce contention.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Work-Stealing"

\end_inset

Work-Stealing
\end_layout

\begin_layout Standard
If a scheduler thread's queue is empty, it will attempt to steal an actor
 from another thread's queue.
 The victim thread is selected in round robin fashion.
 Other selection algorithms, such as preferring scheduler threads running
 on cores in the same NUMA node or preferring scheduler threads running
 on cores with the same L3 cache, have not as yet performed as well as simple
 round robin selection.
\end_layout

\begin_layout Standard
Once a victim is selected, an actor is popped from the victim's scheduler
 queue.
 This actor is then processed by the stealing scheduler thread.
 If the victim's queue is empty, the stealing thread checks for quiescence
 (as detailed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Quiescence"

\end_inset

).
 If the program is not quiescent, the stealing thread may pause in order
 to avoid excessive work-stealing attempts.
\end_layout

\begin_layout Standard
A scheduler thread's back-off pause length is based on the time since the
 scheduler thread last performed useful work.
 In practice, this is estimated with a processor cycle count when possible,
 using 
\begin_inset Formula $\mathtt{RDTSC}$
\end_inset

 on x86/x64, or a fast monotonic system clock if 
\begin_inset Formula $\mathtt{RDTSC}$
\end_inset

 is not available.
 This pause also allows the runtime to avoid spinning a core when there
 is no work to do, avoiding unnecessary energy expenditure.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Quiescence"

\end_inset

Quiescence
\end_layout

\begin_layout Standard
Rather than waiting for the cycle detector to collect all actors in the
 program, the runtime determines quiescence by detecting when all scheduler
 threads have empty queues and no actors are awaiting asynchronous I/O (as
 detailed in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:Asynchronous-I/O"

\end_inset

).
 To do this without locks, scheduler threads have message queues: effectively,
 the scheduler threads are also actors.
\end_layout

\begin_layout Standard
When a scheduler thread 
\begin_inset Formula $t$
\end_inset

 has an empty queue, before 
\begin_inset Formula $t$
\end_inset

 attempts to steal work from another scheduler thread 
\begin_inset Formula $t'$
\end_inset

, it sends a message to the the 
\emph on
coordinating thread 
\emph default

\begin_inset Formula $t_{0}$
\end_inset

 indicating that it is blocked.
 The coordinating thread is simply the first thread spawned by the runtime.
 Similarly, if 
\begin_inset Formula $t$
\end_inset

 then successfully steals work, it will send a message to 
\begin_inset Formula $t_{0}$
\end_inset

 indicating that it has unblocked.
\end_layout

\begin_layout Standard
When 
\begin_inset Formula $t_{0}$
\end_inset

 has received block messages from all other scheduler threads and is itself
 blocked, it engages in the same CNF-ACK protocol that the cycle detector
 uses, sending CNF messages to the other scheduler threads and expecting
 ACK messages.
 If an unblock messages is received before all ACK messages (or if 
\begin_inset Formula $t_{0}$
\end_inset

 itself unblocks), the attempt at quiescence is cancelled.
\end_layout

\begin_layout Standard
If ACK messages from all scheduler threads are received, 
\begin_inset Formula $t_{0}$
\end_inset

 will attempt to shut down the asynchronous I/O thread.
 If this is not possible, due to actors still awaiting asynchronous I/O,
 then the attempt at quiescence is cancelled.
 Otherwise, another CNF-ACK series is run.
 The second CNF-ACK ensures that a scheduler thread that was woken up by
 asynchronous I/O before it was shut down has now reached quiescence.
\end_layout

\begin_layout Standard
At this point, the runtime can terminate without collecting the remaining
 actors.
 The quiescence protocol improves program termination performance by short-circu
iting the actor garbage collection algorithm with a scheduler thread collection
 algorithm, which operates on fewer participants.
\end_layout

\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Cache-Locality"

\end_inset

Cache Locality
\end_layout

\begin_layout Standard
When some actor 
\begin_inset Formula $\alpha$
\end_inset

 is sent a message and the actor is already scheduled on some scheduler
 thread 
\begin_inset Formula $t$
\end_inset

, 
\begin_inset Formula $\alpha$
\end_inset

 remains on 
\begin_inset Formula $t$
\end_inset

.
 This is because the working set of 
\begin_inset Formula $\alpha$
\end_inset

 is more likely to be in the cache on 
\begin_inset Formula $t$
\end_inset

 than on any other thread.
 Conversely, if 
\begin_inset Formula $\alpha$
\end_inset

 is not currently scheduled on any thread, it is unlikely that the working
 set of 
\begin_inset Formula $\alpha$
\end_inset

 is in the cache of any core.
 In this case, 
\begin_inset Formula $\alpha$
\end_inset

 is scheduled on the thread where the message send takes place, as the message
 is in the cache of the sending core.
\end_layout

\begin_layout Section
\begin_inset CommandInset label
LatexCommand label
name "sec:Asynchronous-I/O"

\end_inset

Asynchronous I/O
\end_layout

\begin_layout Standard
The Pony runtime uses a separate, non-scheduler, thread to transform operating
 system events into messages to the actors that will handle those events.
 The underlying mechanism is operating system dependent (
\family typewriter
epoll 
\family default
on Linux, 
\family typewriter
kqueue 
\family default
on OSX and FreeBSD, and 
\family typewriter
IOCP 
\family default
on Windows), but the approach is the same: a single thread is used to block
 on a unified view of pending events.
 When that thread is woken up, notification of pending events is dispatched
 to the appropriate actors.
 Importantly, the event itself is not handled in the non-scheduler thread.
\end_layout

\begin_layout Standard
When the asynchronous I/O thread sends a message to some actor 
\begin_inset Formula $\alpha$
\end_inset

 with an empty message queue, 
\begin_inset Formula $\alpha$
\end_inset

 must be scheduled.
 The asynchronous I/O thread cannot directly push 
\begin_inset Formula $\alpha$
\end_inset

 on to a scheduler queue, as they are single-producer queues.
 Instead, 
\begin_inset Formula $\alpha$
\end_inset

 is placed on a separate queue that is checked by all scheduler threads.
 This helps to reduce event response latency.
\end_layout

\begin_layout Standard
While the initial implementation of asynchronous I/O handling was intended
 for network activity, it has been extended to cover signals, timers, 
\family typewriter
stdin 
\family default
input, and reading both 
\family typewriter
stdout 
\family default
and 
\family typewriter
stderr
\family default
 of any spawned child processes.
 Each of these functions as input in the sense that they represent events
 that are not directly generated by the program.
 Translating those events asynchronously to actor messages allows the runtime
 to treat external events in a unified way.
\end_layout

\begin_layout Standard
This approach is primarily used for 
\emph on
input
\emph default
 events.
 However, some 
\emph on
output
\emph default
 is also treated in an asynchronous manner.
 For example, socket writes that result in back-pressure result in the actor
 handling the socket ceasing to try to write to the socket until an event
 is received from the asynchronous I/O thread that indicates the socket
 is once again writeable.
\end_layout

\begin_layout Standard
File system access is not treated as fundamentally asynchronous in the runtime.
 The interfaces presented by operating systems for file system access are
 largely synchronous, and where asynchronous interfaces exist, they can
 be restrictive.
 In Pony, a synchronous operating system interface can easily be made asynchrono
us by wrapping it in an actor.
 On the other hand, this still results in a scheduler thread being used
 to call synchronous OS APIs.
 An adaptive scheduler that could create new scheduler threads when an existing
 thread was waiting on a kernel operation would address this, without requiring
 a flexible, high performance, asynchronous file system API to be provided
 by the operating system.
\end_layout

\end_body
\end_document