Reachability

A software development writeup. Geek factor: high.

A concept used by Tracing garbage collectors to approximate liveness.

To determine reachability, a tracing collector starts at the root set. In Java, the root set is all variables in static and stack data areas. The collector checks all of these variables for references to objects in the heap. It then checks all of those objects for references to other objects. This process is repeated until all there are no more objects to check. All objects found this way are reachable, and all others are allocated, but not reachable. This can be seen in the text diagram below. It is based on the diagram included in Lycklama and Henry, DDJ Feb 2000, which can be found at: http://www.ddj.com/documents/s=888/ddj0002l/0002lf2.htm

                   ,i7rrrr7:,                     
            :r;Xi7i    O     X;iXXi.              
         ;7;,     O   / \          irr:           
      :7r        / \ /   O----O        ;X         
    ,;,   O-----O---O          \         ir       
   7:    /        Allocated     O----O     ;:     
  Z     /       XiSiSXi;;i2r;X;;      \     ,i    
 2     O    .7;r  Reachable   rrr      O     r.   
 7        :;i            O---O-O   ;7         8   
r        S     O            /   \    i;       S   
r       a       \X7rSi;;;i7/7ir  O    .r      S   
.,     X   O  i;i\  Live  O    i7      r,     B   
 Z     M    \X    O      /       ii     S     7   
 .7    @    8\   /      O         ,r    S    a    
  .7   7    S \ /      /|          S   7.   2     
    r.  2   a  O      / |  Live    S  ,i  ;i      
     ,7: i, 7        /  |         i. :. i7        
        rii, ..     O---O        : .ri;r          
           ;:8SZ7              7BSSi;             
                :7ZSZr.  :XS2a7

The root set gives us access to all of the live objects, that is, objects which the programmers intend to keep around and use again later in the program's execution. However, we may also be able to access objects which are still referenced by live objects, but will never be used again in the program. These objects are reachable, but not live. They cannot be removed by a garbage collector since they are not algorithmically detectable as unnecessary objects. Lycklama and Henry call these "loiterers."

Other objects which have been allocated may have references to one another, but cannot be reached from the root set. They fail the reachability test. These objects can no longer be used by the application, and are candidates for recycling by garbage collection.

Sources

http://www.ddj.com/documents/s=888/ddj0002l/0002l.htm
http://www.artima.com/insidejvm/ed2/ch09GarbageCollection01.html