Reference Object Processing inOn-The-Fly Garbage Collection
Tomoharu Ugawa, Kochi University of Technology
Richard Jones, Carl Ritson, University of Kent

Weak Pointers• Weak pointers are a mechanism to allow mutators tocommunicate with GC• java.lang.ref.Reference• Specification requires us to process weak references
atomically from the view point of mutators• Fully concurrent (on-the-fly) GC never stops allmutators

Java reference types
stronger• Strong - usual references.
• Soft - used for caches that the GC can reclaim.
• Weak - used for canonicalize mappings (e.g., interned•

weakerstrings) that do not prevent GC from reclaiming theirkeys or values.
Phantom - used for scheduling pre-mortem cleanup
actions more flexibility than finalisers.

Java reference typesstronger• Strong - usual references.
the GC can reclaim.
• Soft - used for caches thatreduce
to strong/weak references• Weak - used for canonicalize mapping (e.g., interned•

weakerstrings) that do not prevent GC from reclaiming theirkeys or values.
Phantom - used for scheduling pre-mortem cleanup
actions more flexibility than finalisers.
no interaction with mutators

Reachability
Strongly - can be reached without traversing anyother references.
Weakly - not strongly reachable but can bereached by traversing weak references.

strongly
reachable
strongreference

weakreference• No formal specification• Specification is written in English.
• There are errors in implementations• We formalised the specificationrootGC actions
The GC finds all strongly reachable objects andreclaims others.
The GC “clears” references whose referents areweakly reachable.
Weak reference to Strongly - to be retained
Weak reference to Weakly - to be cleared••

strongly
reachablerootReference.get()
Reference
objectstrongly
reachable

NormalobjectReference.get() - returns a strong reference to its
target or null if the GC has cleared.
get() may make some objects that were weakly
reachable strongly reachable.

rootReference.get()
Reference
objectstrongly
reachable

Normalobjectget()
Reference.get() - returns a strong reference to its
target or null if the GC has cleared.
get() may make some objects that were weakly
reachable strongly reachable.

root

AO

RaceB

AO

Race• Collector clears weak reference AB

AORace get()• Collector clears weak reference ABAORace get()B• Collector clears weak reference A• Mutator makes O strongly reachable by creating a strong
reference to the upstream

from the OpenJDK mailing list
“I've  been  tuning  a  Java  7u51,  Solaris  10,  T4  system  with  24G  heap.    My  customer  is  not  very  happy  with  the  remark  pauses  of    up  to  2  seconds.” Thomas  Viessmann“It  looks  like  the  application  is  using  a  lot  of  Reference  objects.  The  time  spent  in  remark  is  dominated  by   2
reference  processing.” Bengt Rutisson

Pauses (sec)1

blue: reference processing0Solutions
the world - Pauseless GC [Click et al., 2005], Staccato• Stop[McCloskey et al., 2008]• Stop all mutators and process references• Lock - “On-the-fly” GC [Domani et al., 2000]• Block any mutator that calls get()• On-the-fly - Metronome-TS [Auerbach et al., 2008]• Implementation technique is not public

Global GC StateGC and mutator race in TRACING
GC want to finish tracing and then start clearing
Mutator force GC to do more work••by collector
by collector (atomic)

REPEATget()
NORMALstart tracing

start tracing

TRACINGGC traces strongly
reachable objects

by mutator (atomic)

no tracing work

CLEARING

TRACING State• GC traverses strong references• to colour strongly reachable objects black• Write barrier• insertion barrier [Dijkstra]• deletion barrier (a.k.a. snapshot) [Yuasa]• Read barrier for Reference.get()

REPEATNORMALTRACING

CLEARING

TRACING State• GC traverses strong references• to colour strongly reachable objects black• Write barrier• insertion barrier [Dijkstra]• deletion barrier (a.k.a. snapshot) [Yuasa]• Read barrier for Reference.get()

REPEATNORMALTRACING

CLEARING

Insertion Barrier
INVARIANT: Root is grey (allows root to referto white objects)
GC repeat tracing until it finds root black
Reference.get() changes the state to REPEAT
to notify the GC that the root may not be
NORMALblack••rootget()

REPEATTRACING

CLEARING

Deletion Barrier
INVARIANT: Root is black --- root is never rescanned• Reference.get() colours target grey• Reference.get() changes the state to REPEAT

to notify the GC that the root may not be
NORMALblackrootget()REPEATTRACING

CLEARING

CLEARING
Once GC enters CLEARING state• Reference.get() returns null if its target is white• no more objects become strongly reachable• GC clears weak references whose targets
are white

NORMALget() returns null

REPEATTRACING

CLEARING

Evaluation• Jikes RVM• Sapphire on-the-fly copying collector• Trigger GC immediately after the previous GCcompletes• Configuration• Core i7-4770 (4-core, 3.4 GHz)
• 1 GB heap
• 2 collector threads

Pause Time distribution• Stop-the-world GC, or• Block mutator.get() with “lock”
100STW
lock ins
lock del

10

100
101

Frequency (%)

STWlock ins
lock del

6

12

183ms
buckets

100
10

24

STW
lock ins
lock del30

10avrora2009 0.1

jython2006 0.1
00

6

100

12Notelogarithmic
scale

1824

STW
lock ins
lock del100.1

pmd2009 0.1

sunflow2009 0.1

18

24

30

06

12

18

24

Pause times (ms)1218302430

STW
lock ins
lock del101

12

6100

16lusearch2009

30 010STW
lock ins
lock del1

10.1

100xalan2009
0612182430

Pause Time distribution
100STW
lock ins
lock del10
1xalan2009

0.1
061218
Pause time2430

Reference Processing
Phase Time
Mutators running

Mutators blocked
100

100

STW
lock ins
lock del10

OTF ins
OTF del10

1avrora2009

1

0.1

0.1
06

1218

100

2430

61218

100

STW
lock ins
lock del100

lusearch2009

10.1

30

OTF ins
OTF del10

1

240.1
030

6090120 150 180 210 240 270 300

100306090120 150 180 210 240 270 300

100

STW
lock inslock del

100OTF ins
OTF del

101xalan2009

10.1

0.1
06121824300612182430

Execution times

Conclusion• Reference types are frequently used in a significant
number of programs.
• On-the-fly GC must not ignore reference types.
• Formalised the definition of reference types.
• On-the-fly reference processing.
• Model checked with SPIN.
• Implemented in Jikes RVM.
• On-the-fly reference processing phases are longer in theworst case, but with deletion barrier, not by much.
• Overall execution time is not increased significantly byprocessing references on-the-fly, and is often reduced.

http://github.com/perlfu/sapphire

Questions?

Reference type usage
Calls to get() per msec x 103

21

T = 3790ms

xalan2009021101

T = 4480ms

sunﬂow2009

T = 4139ms

lusearch200921

T = 2651ms

luindex2009

0T = 13639
ms

Jython2006

21021

T = 3005ms

pmd200900022

T = 5112ms

avrora2009

x-axis:Normalised
execution timeModel Checking• Model checked with SPIN
• Correctness:
appears to mutators to be processed by GC atomically• Terminates only with deletion barrier

xr

r

r

ooo

root

Figure 7: The model

reference objects
normal objects

faithful
to Fig.r4.
Thereturnvalue
is passed
to the Whencaller get()througoi and whether
beenclearedor not,respectively.
i has
theparameter
reti.tomark[i]represent
thealsocolourreturnsoi , it sets
ret . In andorderCLEARED[i]to check P2,
the model
puts oin global
variables
getRef_arg
getRef_ret.
oi iand
andretwhetherri hasbeen clearedor not, andrespectively.
When get(For themodel
faithfulpseudocode
returnsoi , itcollector
sets i toside,
ret . ourIn order
to ischeck
P2,tothethemodel
also pu
Fig.ret3 and
5. At theend ofgetRef_arg
a cycle, the collector
reclaims white
iinandin global
variablesand getRef_ret.
objects
by callingreclaim():
we introduce
a fourthstate
For thecollector
side, our modelis faithful
to theobject
pseudocod
dangling
is
RECLAIMED.
Our
modelof reclaim()
whitereclaims
objects and• inNo
Fig.
3 andpointer5. At
thecreated
endof a cycle, reclaims
the collector
whit
If a variable
is notnull, its
hasnotreclaimed
reverts
theobjects
to targetwhite.we
P1introduce
and been
P2 caninterpreted•objects
by blackcallingreclaim():a befourth
object as:
stat
RECLAIMED.
modelreclaim()
reclaims white objects an
P1 !((x !=OurNULL)=⇒of (mark[x]!= RECLAIMED))
reverts the black objects to white. P1 and P2 can be interpreted as
P2!(RETNULL¬♦(x =i))it (i1, 2, 3)i =⇒ returns
Once get()of a Reference
null,will=never• P1!= NULL) =⇒ (mark[x] != RECLAIMED))
returns!((xits target
where RETNULLi ≡(getRef_arg= i)∧ (getRef_ret= NULL).
P2 We!(RETNULL=⇒ ¬♦(xi)) (i =with1, 2,models3)
have modeli checked
these=properties
both forcollectors withinsertion
barrier
and a deletion barrier. We alsor anrr≡(getRef_arg=i)∧ (getRef_ret= NULL).
where RETNULLi

tried to model check the termination property.
reference
objects
We have model checked these properties
withmodels both focollectorswith
insertion
barrier
and a deletion barrier. We als
P3 (Termination)
terminates.
o anGC
oeventuallyo

normal objects
triedtomodel
check
thetermination
property.
xPropertiesroot

P3 (Termination) GC eventually terminates.
Figure 7: The modelRace• Mutator makes an object strongly reachable• Collector clears weak reference
target object
strongly
not strongly
reachable
reachable
not cleared

weakreferenceclearedget()

GCAnswer• Handshake ensure that GC changes to TRACING afterthe get() that change the state to REPEAT returned• Second handshake ensures all mutators acknowledge GC
is in TRACING• CAS tells which thread won the race
CAS=> REPEAT

ackget()handshake-1

handshake-2

CAS=>failreq→ TRACING

CAS=>CLEARING