GHC(STG,Cmm,asm) illustrated
for hardware persons

exploring some mental models and implementations

Takenobu T.
Rev. 0.05.0
WIP

“Any sufficiently advanced technology is
indistinguishable from magic.”

Arthur C. Clarke

NOTE- This is not an official document by the ghc development team.
- Please don't forget “semantics”. It's very important.
- This is written for ghc 9.0.

Contents- Executable binary- Compile steps- Runtime System- Development languages- Machine layer/models- STG-machine- Heap objects in STG-machine- STG-machine evaluation- Pointer tagging- Thunk and update- Allocate and free heap objects- STG - C land interface- Thread- Thread context switch- Creating main and sub threads- Thread migration- Heap and Threads- Threads and GC- Bound thread- Spark- Mvar- Software transactional memory- FFI- IO and FFI- IO manager- Bootstrap- Appendix- References

Executable binary

The GHC = Compiler + Runtime System (RTS)
Haskellsource (.hs)

GHC (compile)object (.o)

RuntimeSystem(libHsRts.o)libraries(GHC.Base, ...)

GHC (link)
Executablebinaryincluding the RTS(* static link case)

References : [1], [C1], [C3], [C12], [C21], [S7], [21], [22], [25]Compile steps

GHC transitions between five representations
Haskell language

GHC
compilesteps

Core language

STG language

Cmm language

Assembly language(native or llvm)

each intermediate code canbe dumped by :$ ghc -ddump-parsed$ ghc -ddump-rn$ ghc -ddump-ds$ ghc -ddump-simpl$ ghc -ddump-prep$ ghc -ddump-stg$ ghc -ddump-cmm$ ghc -ddump-opt-cmm$ ghc -ddump-llvm$ ghc -ddump-asm

References : [1], [C3], [C4], [9], [C5], [C6], [C7], [C8], [S7], [S8], [21], [22], [25]Runtime System

Generated binary includes the RTS

Haskell user code

executablebinaryRuntime System

softwarehardwareLibrary(* static link case)

OS(Linux, FreeBSD, Win, ...)

Physical Processor(x86, ARM, ...)

References : [C12], [9]Runtime System includes ...
Runtime System

Storage Manager

User space
Scheduler

Byte-code interpreter

Profiling

SoftwareTransactional Memory...

References : [C12], [8], [9], [5], [17], [S13]Development languages

The GHC is developed by some languages
compilerruntime system( $(TOP)/compiler/*)( $(TOP)/rts/*)

Haskell+Alex (lex)Happy (yacc)
Cmm (C--)
AssemblyC+
Cmm
Assembly

library( $(TOP)/libraries/*)

Haskell+C
References : [C2], [22], [25]Machine layer/models

Machine layer

STG-machine(Abstract machine)

HEC - Haskell Execution Context(Capability, Virtual processor)

Physical Processor(x86, ARM, ...)

Each Haskell code is executed in STG semantics.
References : [C16], [C6], [2], [C19], [8], [S15], [S16], [S11]Machine layer
STG Registers

STG-machine(Abstract machine)

Stack

Heap

Static region

Heap

Static region

BaseReg
R1
Hp
Sp:
Register table

HEC - Haskell Execution Context(Capability,
Virtual processor)

BaseReg
R1
Hp:

Registers

Physical Processor(x86, ARM, ...)

Memory

r13
rbx
r12
rbp
:

References : [C16], [C6], [2], [C19], [8], [S15], [S16], [S11]Runtime system and HEC

user code

Haskell user codeby STG-semantics
STG-machine

runtime system

HECs

user space

Runtime System
OS Threads(native threads, kernel threads)

OS Process

OS

OS(Linux, FreeBSD, Win, ...)

supervisor
space(kernel space)

hardwarePhysical Processor(x86, ARM, ...)
References : [C16], [C6], [2], [C19], [8], [S15], [S16], [S11]many HECs
Multi HECs can be generated by compile and runtime options :$ ghc -rtsopts -threaded$ ./xxx +RTS -N4

HEC(Capability,
Virtual processor)

Task(Worker Thread)

HEC

HEC

HEC

HEC

Tasks
(abstract OS Thread)

OS Threads
OS Process

softwarehardwareOS(Linux, FreeBSD, Win, ...)

Physical Processor(x86, ARM, ...)
References : [1], [5], [8], [9], [14], [C19], [C13], [19], [S17], [S16], [S23], [S22], [S14]HEC (Capability) data structure[rts/Capability.h] (ghc 9.0)
struct Capability_ {StgFunTable f;
StgRegTable r;
register table
uint32_t no;
uint32_t node;
Task *running_task;bool in_haskell;uint32_t idle;
run queue
bool disabled;
StgTSO *run_queue_hd;
StgTSO *run_queue_tl;
uint32_t n_run_queue;
InCall *suspended_ccalls;
uint32_t n_suspended_ccalls;
bdescr **mut_lists;
bdescr **saved_mut_lists;
bdescr *pinned_object_block;bdescr *pinned_object_blocks;
StgWeak *weak_ptr_list_hd;
StgWeak *weak_ptr_list_tl;
int context_switch;

int interrupt;
W_ total_allocated;#if defined(THREADED_RTS)
Task *spare_workers;
uint32_t n_spare_workers;
Mutex lock;Task *returning_tasks_hd;
Task *returning_tasks_tl;
uint32_t n_returning_tasks;
Message *inbox;
struct PutMVar_ *putMVars;
SparkPool *sparks;
SparkCounters spark_stats;#endifStgTVarWatchQueue *free_tvar_watch_queues;
StgTRecChunk *free_trec_chunks;
StgTRecHeader *free_trec_headers;
uint32_t transaction_tokens;}

Each HEC (Capability) has a register table and a run queue and ...
Each HEC (Capability) is initialized at initCapabilities [rts/Capability.c]
References : [S15], [S16], [C13], [C19]STG-machine

The STG-machine consists of three parts
STG Registers

BaseReg
R1
Hp

HpLim

Sp

SpLim

:

Stack
Sp

grows downwards

SpLim

Heap

HpLim

Hp

grows upwards

References : [2], [C17], [C13], [C14]STG-machine is mapped to physical processor
logical view

STG Registers

physical view
physical register(x86 example)

Register table

BaseReg
R1
R2
Hp
Sp
:

r13
rbx
r14
r12
rbp
:

r13
rbx
r14
r12
:

:

:

:

...

References : [C17], [S1], [S2]

STG-machine is mapped to physical processor
logical view

physical view
Heap memory

Stack
TSO
Thread State Object

Heap

Stack

A stack and a TSO object are in the heap.
The stack is stored separately from the TSO for size extension and GC.
References : [C13], [C14], [S16], [S5]

TSO data structure[includes/rts/storage/TSO.h] (ghc 9.0)
typedef struct StgTSO_ {StgHeaderheader;struct StgTSO_*_link;
struct StgTSO_*
global_link;
struct StgStack_*stackobj;
link to stack object
StgWord16
what_next;
StgWord16
why_blocked;
StgWord32
flags;
StgTSOBlockInfo
block_info;
StgThreadID
id;
StgWord32
saved_errno;
StgWord32
dirty;
struct InCall_*bound;
struct Capability_* cap;
struct StgTRecHeader_ * trec;
struct MessageThrowTo_ * blocked_exceptions;struct StgBlockingQueue_ *bq;
StgInt64 alloc_limit;
StgWord32 tot_stack_size;} *StgTSOPtr;

A TSO object is only ~18words + stack. Lightweight!

References : [S5]

Heap objects in STG-machineEvery heap object is represented uniformly

headerpayloadinfo ptr

info table

meta data

entry code

actual machine code

Closure (header + payload) + Info Table + Entry CodeReferences : [C13], [S3], [S4], [S6], [2]Heap object (closure)logical view

headerpayloadinfo ptr

physical viewheap memory
payload1
payload0
info ptr

info tablestatic memory
entry code
info tableentry code

References : [C13], [S3], [C9], [C8], [2], [12], [13]Closure examples : Char, Int'a' :: Char

7 :: Int

headerpayloadheaderpayload

C#

'a‘#

I#

7#

info
ptr

GHC.Types.C#_static_info
layout : 0_1
type : CONSTR
bitmap :inc %rbx
jmpq *0x0(%rbp)

info
ptr

GHC.Types.I#_static_info

info tablelayout : 0_1
type : CONSTR
bitmap :info tableentry code

inc %rbx
jmpq *0x0(%rbp)

entry code

References : [C13], [S3], [C9], [C8], [2], [S20], [13]Closure example (code)[Example.hs]
module Example where
value1 :: Intvalue1 = 7

STG[ghc -O -ddump-stg Example.hs]
Example.value1 :: GHC.Types.Int[GblId, Caf=NoCafRefs, Str=m, Unf=OtherCon []] =CCS_DONT_CARE GHC.Types.I#! [7#];Cmm[ghc -O -ddump-opt-cmm Example.hs]
section ""data" . Example.value1_closure" {Example.value1_closure:const GHC.Types.I#_con_info;
const 7;}[ghc -O -ddump-asm
asm

Example.hs].section .data.align 8.align 1.globl Example.value1_closure.type Example.value1_closure, @object
Example.value1_closure:.quad GHC.Types.I#_con_info.quad 7

headerpayloadI#

7#

References : [C13], [S3], [C9], [C8], [2], [S20]Closure examples : Maybe
Just 7 :: Maybe Int

headerpayloadheaderpayload

I#

7#

Just

info
ptr

Data.Maybe.Just_static_info
layout :type : CONSTR
bitmap :info table

add $0x2,%rbx entry code
jmpq *0x0(%rbp)

info
ptr

GHC.Types.I#_static_info
layout :type : CONSTR
bitmap :info tableinc %rbx
entry code
jmpq *0x0(%rbp)

References : [C13], [S3], [C9], [C8], [2], [S20]Closure examples : List
[ 1, 2 ] :: [Int]header
Cons
info
ptr

GHC.Types.[]_closure

payload

I#

Cons

1#

GHC.Types.:_static_info

Nil

I#

2#

GHC.Types.[]_static_info

layout :type : CONSTR
bitmap :layout :type : CONSTR
bitmap :add $0x2,%rbx
jmpq *0x0(%rbp)

inc %rbx
jmpq *0x0(%rbp)

References : [C13], [S3], [C9], [C8], [2], [S20]Closure examples : Thunk"thunk"x + 1 :: Int(free variable : x = 7)

headerx+1

payloadreserved

info
ptr

headerpayload

I#

7#

x

info
ptr

info table
type : THUNK

info table
type : CONSTR

entry code for
λx -> x + 1

entry code forI#

References : [C13], [S3], [C9], [C8], [2], [S20]STG-machine evaluation

STG evaluation flow

stack

Sp

continuation

stack

current
expression
R1(1)
push a continuation code(next code) to the stack
top(2)
enter to R1 closure

jump

a valueSp

continuation

R1(3)
set a result to R1(4)
jump (return)to the stack top code(5)
repeat from (1)References : [C8], [3], [12], [13]

Enter to a closure
unevaluated closure
R1(1) read R1
to get a closure address(2) read header(info ptr)
to get a Entry code address(3) jump to the Entry code address(4) execute the Entry code(5) set a result to R1

headerpayloadinfo
ptr

layoutclosure type...
if ((Sp + -12) < SpLim)
goto c3h9;
else goto c3ha;:

Info table

Entry code(6) jump to the stack top address(continuation)
References : [C13], [C9], [C8], [10], [3], [2], [12], [13]Pointer tagging

Pointer tagging

pointerheader(info ptr)

payloadR1 or ...

pointer
000
00 1

010
01 1

... an unevaluated closure... an evaluated closure;
1st constructor value or evaluated.
(for instance: "Nothing" )... an evaluated closure; 2nd constructor value.
(for instance: "Just xx")... an evaluated closure; 3rd constructor value.
* 64bit machine casefast judgment!
check only pointer's lower bits without evaluating the closure.
References : [4], [2], [C18], [12], [13]Thunk and update

Thunk and update"thunk"x + 1 :: Int (free variable : x = 7)
payloadheader
Thunk
info
ptr

x

type : THUNK(empty)I##7evaluate ( x + 1 )

x+1

Thunk
info
ptr

(empty)x

type : THUNK
x+1

I#

#7

I#

#8

updateInd (indirect)

info
ptr

type : THUNK
x+1

lock free
I#

#7

I#

#8

type : IND

GC (eliminate Indirect)

References : [3], [2], [C8]Allocate and free heap objects

Allocate heap objects
heap memory (nursery)

HpLim

Hp

allocate(without malloc)

HpLim

Hp

can't allocate
because full

HpLim

Hp

if (Hp > HpLim ) goto ...
call stg_gc_...

References : [C13], [C15], [8], [9], [5], [15], [12], [13], [19], [S25]free and collect heap objects

HpLim

copyingcollection(minor GC)

from space

if (Hp > HpLim ) goto ...
call stg_gc_...

to space

References : [C13], [C15], [8], [9], [5], [15], [12], [13], [19], [S25]STG - C land interface

STG (Haskell) land - C land interface

User code
R1
STG land(Haskell land)
C landRtsAPI
StgRunStgReturnresultfunction f
BaseReg

Runtime System(Scheduler)

References : [S18], [S17], [S19], [S21]ThreadThread layer (single core)
Haskell Threads
HaskellThreads
HEC(Capability,
Virtual processor)

exclusive execution

...

HEC

user space

OS Thread
OS ProcessOSsoftware(Linux, FreeBSD, Win, ...)

hardwarePhysical Processor

supervisor
space(x86, ARM, ...)

References : [5], [8], [9], [14], [C19], [C13], [19], [S17], [S16], [S23], [S22], [S14]Thread layer (multi core)
Haskell Threads

Haskell Threads

HaskellThreads
HEC(Capability,
Virtual processor)

...

...

HEC

HEC

user space
OS Thread

OS Thread
OS Process

softwarehardwaresupervisor
space

OS
(Linux, FreeBSD, Win, ...)

Physical Processor

Physical Processor(x86, ARM, ...)

(x86, ARM, ...)

*Threaded option case (ghc -threaded)
References : [5], [8], [9], [14], [C19], [C13], [19], [S17], [S16], [S23], [S22], [S14]Thread context switch

Threads and context switch
logical viewThreadstatesThread #0

Thread #1

Thread #2

Registers

Registers

Registers

Stack
load
state

STG-machine

Registers
Stack

Stack

Stack

...

interleaved
exclusive execution

save
state

execution andpre-empted via the context switch

heap

References : [5], [8], [9], [14], [C19], [C13], [19], [S17], [S16], [S23], [S22], [S14]Threads and TSOs
logical viewThreadstatesThread #0

Thread #1

Thread #2

Registers

Registers

Registers

Stack
load
state

STG-machine

physical view

Stack
save
state

Stack

heap memory...

TSO #0(Thread State
Object)TSO #1(Thread State
Object)Registers
Stack

TSO #2(Thread State
Object)heap

References : [5], [8], [9], [14], [C19], [C13], [19], [S17], [S16], [S23], [S22], [S14]Scheduling by run queue
STG-machine

Registers
Stack

STG land(Haskell land)
StgRunC landStgReturn

Scheduler

run queue

popRunQueue

appendToRunQueueround robin

...
heap

TSO

TSO

...

References : [5], [8], [9], [14], [C19], [C13], [19], [S17], [S16], [S23], [S22], [S14]Context switch flow
Haskell thread

heap
heap
HpLim
-> 0

if (Hp > HpLim)(2) HpLim -> 0

RTS(8) context switch(3) heap size check

Interrupt

TSO

TSO

(4) call GC

GC

Scheduler(5) HpLim check
HpLim = 0 ?

(7) scheduling(6) goto schedule(1) interrupt
platform OS timer

context switch at safe points
References : [5], [8], [9], [14], [C19], [C13], [19], [S17], [S16], [S23], [S22], [S14], [S24]Context switch flow (code)
stg_gc_noregs
if (HpLim == 0) {jump stg_returnToSched [R1];

STG land(Haskell land)
C landcap->r.rHpLim = NULL;
stopCapability

stg_returnToSched
W_ r1;
r1 = R1; // foreign calls may clobber R1
SAVE_THREAD_STATE();
foreign "C" threadPaused(MyCapability()"ptr", CurrentTSO);
R1 = r1;
jump StgReturn [R1];schedule

contextSwitchCapability
contextSwitchAllCapabilities
handle_tick

next
handle_tick ..

CreateTimerQueue
initTicker
initTimer

startTimer

hs_init_ghc
hs_mainOS*Windows case
References : [5], [8], [9], [14], [C19], [C13], [19], [S17], [S16], [S21], [S23], [S22], [S14], [S24]Creating main and sub threads

Create a main thread
Runtime
System

Runtime system bootstrap code [rts/RtsAPI.c]
rts_evalLazyIO
createIOThread
createThread ... (1), (2), (3)pushClosure ... (4)scheduleWaitThread
appendToRunQueue ... (5)scheduler
run queue

(5)

(1)
TSO

heap memory

(2)
stack

(3)

*stackobj

closure(4)

static memory

ZCMain_main_closure

headerpayloadinfo tableentry code

References : [5], [8], [9], [14], [C19], [C13], [19], [S17], [S16], [S23], [S22], [S14], [S24]Create a sub thread using forkIO
Haskell Threads

forkIO
stg_forkzh
ccall createIOThread ... (1), (2), (3), (4)ccall scheduleThread ... (5)User code
Runtime Systemappend(5)scheduler
run queue(1)
TSO

heap memory

forked closure(2)*stackobj

(3)

stack

(4)

headerpayloadclosureinfo tablestatic memory

entry code
References : [5], [8], [9], [14], [C19], [C13], [19], [S17], [S16], [S23], [S22], [S14], [S24]Thread migration

Threads are migrated to idle HECs

HaskellThreads

Idle HEC
run queue

Idle HEC

Idle HEC

run queue

run queue

run queue

empty

empty

empty

HEC

HEC

HEC

HEC

OS Thread

OS Thread

OS Thread

OS Thread

Physical Processor

Physical Processor

Work pushing

OS Process
hardwarePhysical Processor

Physical Processor

References : [5], [8], [9], [14], [C19], [C20], [S17], [S16], [S23], [S24]Heap and Threads

Threads share a heap
Haskell Threads
Registers

Registers

Stack

Stack

...

Registers

Registers

Stack

Stack

...

heap memory (shared)

static memory (shared)

hardware

HEC

HEC

Physical Processor

Physical Processor

References : [5], [8], [9], [14], [C19], [C13], [19], [S17], [S16], [S23], [S22], [S14], [S17], [S16], [S25]Local allocation area (nursery)
Haskell Threads

heap memory(shared)Registers

Registers

Stack

Stack

Registers

Stack

Stack

nursery...

nursery
generation N

static memory(shared)hardware...

Registers

static memory
HEC

HEC

Physical Processor

Physical Processor

fast access using nursery for each processors
References : [5], [8], [9], [14], [C19], [C13], [19], [S17], [S16], [S23], [S22], [S14], [S17], [S16], [S25]Threads and GC

GC, nursery, generation, aging, promotion
HaskellThreadSTG land(Haskell land)
Runtime System

allocate
generation 0, step 0

Hpnursery
HEC

nursery
aging

HEC

nursery
HEC

nursery
HEC

generation 0, step 1
promotion

generation 1

heap memory
References : [8], [9], [15], [C15], [C13], [S25]Threads and minor GC
sequential GC for young generation (minor GC)“stop-the-world” GC
HaskellThreads

GC threadGC threadGC threadGC threadnursery

nursery

nursery

nursery

generation 0, step 1

heap

generation 1
HEC

HEC

HEC

HEC

Physical Processor

Physical Processor

Physical Processor

Physical Processor

References : [8], [9], [15], [C15], [C13], [S25]Threads and major GC
parallel GC for oldest generation (major GC)“stop-the-world” GC
HaskellThreads

GC threadGC threadGC threadGC threadnursery

nursery

nursery

nursery

generation 0, step 1

heap

generation 1
HEC

HEC

HEC

HEC

Physical Processor

Physical Processor

Physical Processor

Physical Processor

References : [8], [9], [15], [C15], [C13], [S25]GC discovers live objects from the root
Runtime Systemscheduler
run queuerootheap memorystackclosureTSO

TSO

closurestack
TSO

closurereachable from root

GC aging or promote

unreachable(garbage)

freeReferences : [8], [9], [15], [C15], [C13], [S25]Bound threadA bound thread has a fixed associated OS Thread
forkOS
Bound
ThreadHaskellThreads

HEC(Capability,
Virtual processor)

fixed association
for safe foreign calls

HEC

OS Thread

OS Thread
OS Process

Foreign calls from a bound thread are all made by the same OS thread.
A bound thread is created using forkOS.
The main thread is bound thread.

References : [6], [5], [8], [9], [14], [C19], [19], [S17], [S16], [S23], [S22]forkIO, forkOn, forkOS

forkIO

forkOS

forkOnBound
Threads

HaskellThreads

affinity

bound

HEC

HEC

HEC

OS Thread

OS Thread

OS Threadcreate a haskell unboundthreadcreate a haskell unboundthreadon the specified HEC

OS Threadcreate a haskell bound thread
and an OS thread

References : [6], [5], [8], [9], [14], [C19], [19], [S17], [S16], [S23], [S22]SparkSpark layer
serial execution on each Spark Threads

Sparks
HaskellThreadHEC(Capability,
Virtual processor)...
Spark Thread

HEC

user space

OS Thread
OS ProcessOSsoftware(Linux, FreeBSD, Win, ...)

hardwarePhysical Processor

supervisor
space(x86, ARM, ...)

Spark Threads are generated on idle HECs.
References : [C19], [19], [S17], [S26], [S27], [S34], [S12]Sparks and Spark poollogical view
Spark

Spark

Spark

Spark

Spark Thread

Spark Thread

Spark Thread

Spark Thread

HEC

HEC

HEC

HEC

Physical Processor

Physical Processor

Physical Processor

Physical Processor

Spark pool

rpar
Spark
(Thunk)References : [C19], [19], [S17], [S26], [S27], [S34], [S12]Spark pool and work stealing
physical view
Spark

Spark

Spark Thread

Spark

Spark Thread

Spark

Spark Thread

Spark Thread

Spark pool

Spark pool

Work stealing

HEC

Spark pool

Spark pool

References : [C19], [19], [S17], [S26], [S27], [S34], [S12]Sparks and closures
Spark Thread
runSparks

STG land(Haskell land)

getSpark

C landSpark pool
(WSDeque)

HEC

rpar
push

...
heap

closure(thunk)closure(thunk)...

(not TSO objects, but closures. therefore very lightweight)
References : [C19], [19], [S17], [S26], [S27], [S34], [S12]

MVar

MVar

Haskell Thread #0

Haskell Thread #1

putMVar

takeMVar
empty?
or
full?
MVar

References : [16], [18], [19], [S32], [S12]MVar and blocking
Haskell Thread

Haskell Thread

putMVar

takeMVar

BLOCKED
if full

BLOCKEDif empty

full

empty

MVar

MVar

References : [16], [18], [19], [S32], [S12]MVar example
Haskell Thread #0

Haskell Thread #1(3)

takeMVar(2)(1)

putMVarMVar

timer context switch

time
Thread #0

Running

BlockedNon Blocked

takeMVar(1)
MVar

Running(3) wakeup and takeMVar (atomic)
empty

full
putMVarThread #1

empty

(2)

Running* single core case

References : [16], [18], [19], [S32], [S12]MVar object view
User viewlogical MVar object

heap

MVar
empty?
orfull?

physical MVar object

StgReturn
FIFO
ofStgMVarTSOQueue
head
tail

head
tail
value
closurevalue
StgMVarTSOQueue

StgMVarTSOQueue

TSO

TSO

References : [16], [18], [19], [S32], [S12]newEmptyMVar
Haskell Threads
newEmptyMVar
newMVar#(1) call the Runtime primitive
Runtime System

stg_newMVarzh
ALLOC_PRIM_
SET_HDR
StgMVar_head
StgMVar_tail
StgMVar_value(2) create a MVar object in the heap
MVar object

heap

stg_END_TSO_QUEUE_closure

head
tail
value
(3) link each fields

References : [16], [18], [19], [S32], [S12]takeMVar (empty case)
Haskell Threads
takeMVar
takeMVar#

Runtime System

stg_takeMVarzh
create StgMVarTSOQueue … (1)append… (2)StgReturn … (3)(3) return to the scheduler(1) create
StgMVarTSOQueueFIFO of StgMVarTSOQueuehead(2) append

tail
value
MVar object
References : [16], [18], [19], [S32], [S12]takeMVar (full case)
Haskell Threads
takeMVar
takeMVar#

Runtime System

stg_takeMVarzh(1) get value(2) set empty(3) remove head(4) tryWakeupThread(3) remove headscheduler
run queue

fairness round robinheadappendtailvalue(1) get value(2) set empty(4) wakeup
Only one of the blocked threads becomes unblocked.

MVar object
References : [16], [18], [19], [S32], [S12]Software transactional memory

Create a atomic block using atomicallyatomically :: STM a -> IO a
atomically
STM awriteTVar
writeTVar
readTVar
readTVar

TVar

readTVar

TVar

transactionalvariable

Create and evaluate a composable “atomic block”
Atomic block = All or Nothing
References : [17], [19], [20], [C20], [S12], [S28]Rollback and blocking control using retry
retry :: STM a

STM a
writeTVar
retry :: STM a

readTVar

TVar

TVar

Discard, blocking and try again

References : [17], [19], [20], [C20], [S12], [S28]Compose OR case using orElse
orElse :: STM a -> STM a -> STM a

STM a

STM a
A

A

orElse ::STM aresult

STM a -> STM a -> STM a

B

if no retry AorB

if retry A

A or B or Nothing
References : [17], [19], [20], [C20], [S12], [S28]STM, TVar example (normal case)
STM awriteTVar

writeTVar

TVar

TVar

atomic block (critical section)

time
Thread #0

writeTVar writeTVar

commitTVar #A

old value

new value

TVar #B

old value

new value
atomic update

References : [17], [19], [20], [C20], [S12], [S28]STM, TVar example (conflict case)atomic blockrollback andtry again

atomic blocktime

Thread #0
commitTVar #A
TVar #B

commitold value
old value

new valueother value

new valuecommitother threaddifferent

References : [17], [19], [20], [C20], [S12], [S28]retry example

atomic block

retryatomic blocktime

Thread #0

blockedwake upTVar #A
TVar #B

commitold value

new value

old valuechanged value

new valuecommitother thread

References : [17], [19], [20], [C20], [S12], [S28]STM, TVar data structure
retryatomicallynewTVar
StgTVar

StgTVarwriteTVar
readTVar
StgTVarWatchQueue

StgTVarWatchQueue

CurrentTSO
TRecEntry

TRecEntry

StgTRecHeader

StgTRecChunkatomically

StgInvariantCheckQueue

References : [17], [19], [20], [C20], [S12], [S28]newTVar, writeTVar, readTVar
newTVarwriteTVar

readTVaror

Runtime System
TRecEntry(transaction
Record)TRecEntry

TRecEntry

invariant checkwhen commit
TVar
StgTVarheap

References : [17], [19], [20], [C20], [S12], [S28]block by retry, wake up by commit

retry :: STM a
Runtime Systemcommit by other thread(4) commit(1) retry

TSO
StgTVar(3)yieldscheduler
run queue

WatchQueue(2) append

TVar

…

(5)append…
(4) commit
wakeup all threads in the WatchQueueno guarantee of fairness,because the RTS has to run all the blocked transaction.
References : [17], [19], [20], [C20], [S12], [S28]FFIFFI (Foreign Function Interface)
Haskell thread

ccall

STG land(Haskell land)

foreignout-call

StgReturn

Stg interface
C landforeign
in-call
FFI

StgRunScheduler

FFI management

user space

Runtime system

Foreign
C codeOS API (system call)OSsupervisor
space

References : [6], [11], [20], [S40], [S39], [S38], [S37], [S41]FFI and OS Threads
HaskellThreads(4)

HaskellThreads

non-blocked(2)(1) HEC

HEC(5)

Foreign
C codeOS Thread
Physical Processor(1) a safe foreign call (FFI)

HEC

Foreign
C code(3)

OS Thread

OS Thread

Physical Processor(2) move the HEC to other OS thread(3) spawn or draw an OS thread(4) move Haskell threads(5) call the foreign C code
References : [6], [11], [20], [S40], [S39], [S38], [S37], [S41]A safe foreign call (code)
Haskell Threads
ccall suspendThread
ccall FOREIGN_C_CODE
ccall resumeThread… (3)non-blocked
HaskellThreads(3)

releaseCapability_
giveCapabilityToTask
startWorkerTask
createOSThread… (2)waitForReturnCapability

… (4)

… (1)

(1)
HEC

HEC

(4)

Foreign
C code(2)

OS Thread

OS Thread

Physical Processor

References : [6], [11], [20], [S40], [S39], [S38], [S37], [S41]a safe and an unsafe foreign calla safe foreign callan unsafe foreign callnon-blocked

HaskellThreads

blocking
safe
foreign call

blockedHaskellThreads

HEC

HEC

Foreign
C codeblocking
unsafeforeign call

HEC
Foreign
C codeOS Thread

OS Thread

Physical Processor

OS Thread
Physical Processor

faster,but blocking to the other Haskell threads

References : [6], [11], [20], [S40], [S39], [S38], [S37], [S41]Safe/unsafe foreign call and bound/unbound threada safe foreign callnon-blocked

unboundthreadan unsafe foreign callnon-blocked

non-blocked

ccall

an unboundthreadHEC #0

Processor #0

non-blocked

blockedccall
HEC #1

HEC #1

HEC #0Foreign
C codeOS Thread

unboundthreadOS Thread

Foreign
C codeOS Thread

Processor #1

non-blocked

HEC #1bound
threadOS Thread

OS Thread

Processor #0

Processor #1

non-blocked

blockedccall

a boundthreadHEC #0HEC #1

HEC #1

ccall
HEC #0HEC #1

Foreign
C codeOS Thread
Processor #0

OS Thread

OS Thread

Processor #1

boundthreadHEC #1
Foreign
C codeOS Thread
Processor #0

OS Thread

OS Thread

Processor #1

References : [6], [11], [20], [S40], [S39], [S38], [S37], [S41]IO and FFI

IO

Haskell Thread

getLine (IO)

IO String?

References : [6], [11]

IO example: getLine
getLineIO Stringstandard IO lib
STG land(Haskell land)c_readFFI (Foreign Function Interface)

C landuser
space

C IO lib (libio.a)“read” system call
OS API (system call)supervisor
space

OS
Device driver
Hardware
UART, serial, ...

References : [6], [11], [20], [S40], [S39], [S38], [S37], [S41]IO example: getLine (code)
User code

getLinehGetLine
hGetLineBuffered
hGetLineBufferedLoop
maybeFillReadBuffer
getSomeCharacters
readTextDevice

Library

Buffered.fillReadBuffer
readBuf’
readBuf
RawIO.read

STG land(Haskell land)

fdReadreadRawBufferPtr
c_read… switch safe/unsafe,
non-threaded/ioManager

FFI (Foreign Function Interface)

C landread

Runtime
SystemOS API (system call)OS
References : [6], [11], [20], [S40], [S39], [S38], [S37], [S41]IO manager

IO manager (single core)

Haskell Threads
IO manager
dispatcher thread
HEC

HEC

OS Thread

OS Threadaffinity

user space

OS Process
softwarehardwareOS(Linux, FreeBSD, Win, ...)

supervisor
space

Physical Processor(x86, ARM, ...)

*Threaded option case (ghc -threaded)
References : [7], [5], [8]IO manager (multi core)

HaskellThreads

HaskellThreads
IO manager
dispatcher
threadIO manager
dispatcher
thread

HEC

HEC

HEC

HEC

OS Thread

OS Thread

OS Thread

OS Threaduser space

OS ProcessOSsoftwarehardwaresupervisor
space(Linux, FreeBSD, Win, ...)

Physical Processor

Physical Processor(x86, ARM, ...)

(x86, ARM, ...)

*Threaded option case (ghc -threaded)
References : [7], [5], [8]IO manager
Haskell Threads

IO manager
event table

blocking IO
registerFd

event
loop
request andset callback (MVar)
IO access(epoll, kqueue)

takeMVar(wait and wake up)

putMVarHEC

HEC

OS Thread

OS Thread
OS Process*Threaded option case (ghc -threaded)system call
References : [7], [5], [8], [S29], [S30], [S33], [S38], [S36], [S3]

Bootstrap

Bootstrap sequence

ZCMain_main_closure

User
code

stg_enter_info
loadThreadState
emitLoadThreadState

STG land(Haskell land)

stg_returnToStackTop
StgRunschedule

C landscheduleWaitThread
createIOThread
createThread, pushClosure
rts_evalLazyIO
hs_init_ghc
initScheduler, initStorage, initTimer, ioManagerStart, ...
main

Runtime
System(lib/libHSrts.a)

hs_main

mainCRTStartup(*Windows case)

OS
References : [S7], [S13], [S14], [S17], [S18], [S19], [S9], [S10], [S21], [S42]Exit sequence
User
code

STG land(Haskell land)

stg_stop_thread_info
StgReturnC landRuntime
System(lib/libHSrts.a)schedule
shutdownHaskellAndExit
stg_exit

exit

OS
References : [S19], [S18], [S17]Initializing
startIOManagerThread
startIOManagerThreads
ensureIOManagerIsRunning

STG land(Haskell land)

create IO Manager Threads (+RTS -N)

ioManagerStart

C landinitTimer, startTimercreate Timer

initGcThreads
allocNurseries
storageAddCapabilities
initGeneration
initStorage

initializing GC Threads (+RTS -N)
create nurseries (+RTS -N)

createOSThread
newTask
startWorkerTask
startWorkerTasks
initCapabilities
initScheduler

create GC generations (+RTS -GN)

Runtime
Systemcreate OS Threads (+RTS -N)
create Tasks (+RTS -N)

create capabilities (+RTS -N)

hs_init_ghc
hs_mainmain

OS

References : [1], [S7], [S13], [S14], [S17], [S15], [S16], [S24], [S21], [S35]Create each layers
User code

SparksUser
code

Runtimesystem

Haskell threads

newSpark

forkIO
forkOnforkOS

stg_forkzh, createThread
stg_forkOnzh, createThread
forkOS_createThread

OS Threads
OS Process

OS API

initCapability(Capability, Virtual processor)(Worker thread) abstract OS Thread

OS

rpar

HECs
Tasks

Runtime system

forkOS

newTask

forkOS

createOSThread

pthread_create
fork

OS

software(Linux, FreeBSD, Win, ...)

hardwarePhysical Processor(x86, ARM, ...)

References : [1], [5], [8], [9], [C13], [C19], [S12], [S26], [S22], [S15], [S23]Appendix

Boxity : boxed and unboxedBoxed and unboxed types
A boxed typex = 7 :: Int
pointedAn unboxed typeheaderpayloadx = 7# :: Int#

I#

7#

7#

heap memory

A boxed type is represented by a pointerto a heap-allocated object.

An unboxed type is represented by thevalue itself.

References : [C10], [C13], [S31], [23], [24]Boxity examples
Boxed types

Unboxed types

x :: Intx :: Int#I#

7#

x :: Float

7#x :: Float#

F#

1.0#

x :: Double

1.0#

x :: Double#
D#

2.2##

2.2##

x :: ByteArray#ef 81 de 10

References : [C10], [C13], [S31], [23], [24]Levity : lifted and unliftedLifted and unlifted types
x :: IntA lifted type

I#

0#

I#

1#

:
⊥
A lifted type has one extra element
representing a non-terminating computation (bottom, ⊥).

x :: Int#An unlifted type1#⊥

An unlifted type has no bottom.

References : [C11], [C10], [C13], [S31], [24], [23]Boxity and levity

Boxity and levity examples
Boxed types

represented by a pointerUnboxed types

Int
I#

Lifted
types

7#

Maybe
Just

include bottom

I#

7#

Int#
Unlifted
types

7#

ByteArray#ab 89 cf 68

Float#
1.0#

References : [24], [C11], [C10], [C13], [S31], [23]Calling convention examples
callerLifted types(non-strict,call-by-need)IntcalleeR2 register(r14 on x86_64)

heap memoryIntpointedcallerInt#

R2 register(r14 on x86_64)

Unlifted types(strict,
call-by-value)

F1 register(xmm1 on x86_64)

7#callee7#
itselfcallerFloat#

I#

callee1.0#
itself

References : [24], [C11], [C10], [C13], [S31], [23]

ReferencesReferences[1]

The Glorious Glasgow Haskell Compilation System User's Guide
https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/index.html[2]Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine Version 2.5
https://www.microsoft.com/en-us/research/wp-content/uploads/1992/04/spineless-tagless-gmachine.pdf[3]Making a Fast Curry Push/Enter vs Eval/Apply for Higher-order Languages
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/eval-apply.pdf[4]

Faster Laziness Using Dynamic Pointer Tagging
https://research.microsoft.com/en-us/um/people/simonpj/papers/ptr-tag/ptr-tagging.pdf[5]

Runtime Support for Multicore Haskell
https://research.microsoft.com/en-us/um/people/simonpj/papers/parallel/multicore-ghc.pdf[6]Extending the Haskell Foreign Function Interface with Concurrency
https://simonmar.github.io/bib/papers/conc-ffi.pdf[7]

Mio: A High-Performance Multicore IO Manager for GHC
https://dl.acm.org/doi/pdf/10.1145/2503778.2503790[8]

The GHC Runtime System
https://web.mit.edu/~ezyang/Public/jfp-ghc-rts.pdf[9]

The GHC Runtime System
https://www.scs.stanford.edu/14sp-cs240h/slides/ghc-rts.pdf[10]Evaluation on the Haskell Heap
http://blog.ezyang.com/2011/04/evaluation-on-the-haskell-heap/

References[11]

IO evaluates the Haskell Heap
http://blog.ezyang.com/2011/04/io-evaluates-the-haskell-heap/[12]

Understanding the Stack
https://www.well-typed.com/blog/94/[13]

Understanding the RealWorld
https://www.well-typed.com/blog/95/[14]

The GHC scheduler
http://blog.ezyang.com/2013/01/the-ghc-scheduler/[15]

GHC’s Garbage Collector(Lost link: Garbage Collection & Memory Management Summer School, 2004)[16]

Concurrent Haskell
https://www.microsoft.com/en-us/research/wp-content/uploads/1996/01/concurrent-haskell.pdf[17]

Beautiful Concurrency
https://www.schoolofhaskell.com/school/advanced-haskell/beautiful-concurrency[18]

Anatomy of an MVar operation
http://blog.ezyang.com/2013/05/anatomy-of-an-mvar-operation/[19]

Parallel and Concurrent Programming in Haskell
https://simonmar.github.io/pages/pcph.html[20] Real World Haskell
http://book.realworldhaskell.org/

References[21]

A Haskell Compiler
https://www.scs.stanford.edu/16wi-cs240h/slides/ghc-compiler-slides.html[22] Dive into GHC
https://www.stephendiehl.com/posts/ghc_01.html[23] Unboxed Values as First-Class Citizens
https://www.microsoft.com/en-us/research/wp-content/uploads/1991/01/unboxed-values.pdf[24] Levity Polymorphism (extended version)
https://cs.brynmawr.edu/~rae/papers/2017/levity/levity.pdf[25] GHC Reading Guide
https://takenobu-hs.github.io/downloads/haskell_ghc_reading_guide.pdf

References
The GHC Commentary[C1] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary[C2] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/source-tree[C3] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/compiler[C4] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/compiler/hsc-main[C5] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/compiler/core-syn-type[C6] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/compiler/stg-syn-type[C7] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/compiler/cmm-type[C8] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/compiler/generated-code[C9] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/compiler/symbol-names[C10] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/compiler/type-type[C11] https://gitlab.haskell.org/ghc/ghc/-/wikis/levity-polymorphism[C12] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/rts[C13] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/rts/storage/heap-objects[C14] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/rts/storage/stack[C15] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/rts/storage/gc[C16] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/rts/haskell-execution[C17] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/rts/haskell-execution/registers[C18] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/rts/haskell-execution/pointer-tagging[C19] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/rts/scheduler[C20] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/rts/stm[C21] https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/libraries

References
Source code[S1] includes/stg/Regs.h[S2] includes/stg/MachRegs.h[S3] includes/rts/storage/ClosureTypes.h[S4] includes/rts/storage/Closures.h[S5] includes/rts/storage/TSO.h[S6] includes/rts/storage/InfoTables.h[S7] compiler/GHC/Driver/Pipeline.hs[S8] compiler/GHC/Driver/Main.hs[S9] compiler/GHC/Parser.y[S10] compiler/GHC/StgToCmm/Foreign.hs[S11] compiler/GHC/StgToCmm/*.hs[S12] rts/PrimOps.cmm[S13] rts/RtsMain.c[S14] rts/RtsAPI.c[S15] rts/Capability.h[S16] rts/Capability.c[S17] rts/Schedule.c[S18] rts/StgCRun.c[S19] rts/StgStartup.cmm[S20] rts/StgMiscClosures.cmm[S21] rts/HeapStackCheck.cmm[S22] rts/Threads.c[S23] rts/Task.c[S24] rts/Timer.c[S25] rts/sm/GC.c[S26] rts/Sparks.c[S27] rts/WSDeque.c[S28] rts/STM.h[S29] rts/posix/Signals.c[S30] rts/win32/ThrIOManager.c[S31] libraries/ghc-prim/GHC/Types.hs[S32] libraries/base/GHC/MVar.hs[S33] libraries/base/GHC/Conc/IO.hs[S34] libraries/base/GHC/Conc/Sync.hs[S35] libraries/base/GHC/Event/Manager.hs[S36] libraries/base/GHC/Event/Thread.hs[S37] libraries/base/GHC/IO/BufferedIO.hs[S38] libraries/base/GHC/IO/FD.hs[S39] libraries/base/GHC/IO/Handle/Text.hs[S40] libraries/base/System/IO.hs[S41] libraries/base/System/Posix/Internals.hs[S42] AutoApply.o (utils/genapply/Main.hs)

Connect the algorithm and transistor

Here is the slide: https://github.com/takenobu-hs/haskell-ghc-illustrated