Garbage Collection

Algorithms for Automatic Dynamic Memory Management

Errata

Printings: June 2000
Last updated 29 September 2003

These errors appear in the June 2000 reprinting.


Chapter 1 The Classical Algorithms

Page 23, Diagram 2.5, the new free list should be S, U, V, ... (i.e. the order is reversed) [18]. Thus,


Diagram 2.5 After Update(rught(R), nil).

Pages 33 and 34, in the left-hand diagrams, the arrow from A' to B' in Diagram 2.10 and from A' to C' in Diagram 2.11 should be removed: the pointers are not written until the recursive step is complete [15].

Chapter 3 Reference Counting
Page 46, Deautsch-Bobrow algorithm. The first paragraph implies, but fails to state explicitly, that allocation of a new object causes a new entry to be added to the ZCT, risking overflow. [20].

Page 47, Algorithm 3.4, the test x>t is better written y>t [14]. Thus,

    gcd(x,y) =            -- assert: x >= y >= 0
        if y == 0
            return x
        t = x - y
        if y > t
            return gcd(y,t)
        else return gcd(t,yyuasa)
Algorithm 3.4 Greatest common divisor.
Page 66, Algorithm 3.19, the caption to should refer to mark_grey (not scan_grey) [19].

Chapter 6 Copying Garbage Collection

Page 124, Diagram 6.5, the caption should read [22] "left(F') is updated with the forwarding address found in A." (not C).

Chapter 7 Generational Garbage Collection

Page 148, Diagram 7.3, in attempting to correct a minor labelling error in the earlier printings, Diagram 7.3 instead repeats Diagram 7.2 [16]. It should of course be:


Diagram 7.3 Overwriting R creates old-young pointers.

Chapter 8 Incremental and Concurrent Garbage Collection

Page 194: The discussion of how Steele allocates cells omits an account of allocation during the sweep phase, although this is described in Algorithm 8.6 [21]. In summary,

Page 195, Algorithm 8.7,

      colour(X) = black
  
should be
      mark_bit(X) = true                           -colour(X) is now black
  
Note also the omitted (if obvious) definitions,
  marked(X) == (mark_bit(X) == true)
  unmarked(X) == (mark_bit(X) == false)
  

Page 204, Algorithm 8.12, the final test on B should be B>=T-n [6]. Thus,

  New(n) =
      if B >= T - n                              - Flip phase
          if scan < B
              abort "Haven't finished scavenging"
  
          flip()
          for root R
              R = copy(R)
  
      repeat k times while scan < B                 - scavenge a bit
          for P in Children(scan)
              *P = copy(*P)
          scan = scan + size(scan)
  
      if B >= T
          abort "Heap full"
      T = T - n
      return T
  
  read(T) =
      T' = copy(T)
      return T'
Algorithm 8.12 Baker's incremental copying algorithm.

Page 204, line 2: the reference should be to Diagram 8.8 on the previous page [17].

 

Chapter 9 Garbage Collectors for C

Page 242, second paragraph: the block's count of free slots should be decremented, not incremented, and the allocator decrements the number of free, rather than allocated, blocks [19].

 

Chapter 10 Garbage Collectors for C++

Page 262, last paragraph, second sentence, should refer to "A or B", not "A of B" [19].

 


Errata

Printings: June 1996, February 1997, November 1997.
Last updated 4 January 1999

The errors below were corrected in the January 1999 reprinting.


Chapter 1 Introduction

Page 3, first paragraph, last sentence: occam does not use static allocation.

Chapter 2 The Classical Algorithms

Page 21, Algorithm 2.2, Update should increment the reference count of the new target before deleting the pointer to the old target to prevent incorrect reclamation in the case that both targets are one and the same and that this is the only reference to it. Thus,

  Update(R, S) =
      RC(S) = RC(S) + 1
      delete(*R)
      *R = S
Algorithm 2.2 Updating pointer fields under reference counting
Page 35, the constants in the formula for efficiency of mark-sweep should be transposed [6]. Thus,
eMS = (1-r) / (br+c)
Similarly, the y-intercept for the Mark-Sweep curve in the graph in Diagram 2.12 should be 1/c [9].

Chapter 3 Reference Counting
All algorithms in this chapter should increment reference counts of new targets before deleting the pointers to the old targets.

Page 46, Algorithm 3.2

  Update(R,S) =               - R and S are heap objects
      incrementRC(S)
      delete(*R)
      remove S from ZCT
      *R = S
Algorithm 3.2 Deferred Reference Counting: updating pointer values.
Page 52, Algorithm 3.7
  Update(R,S) =
      T = sticky(*S)
      if RC(*S) == unique
	  *S = T
      delete(*R)
      *R = T
Algorithm 3.7 One-bit reference counting with tagged pointers.
Page 57, Algorithm 3.9
  Update(R,S) =
      T = *R
      gr = group_no(R)

      if gr != group_no(S)              - external reference
	  increment_groupRC(S)

      if gr != group_no(T)              - external reference
	  decrement_groupRC(T)
	  if groupRC(T) == 0
              reclaim_group(T)

      *R = S
Algorithm 3.9 Bobrow's algorithm.
Page 59, Algorithm 3.11
  Update(R,S) =
      WRC(S) = WRC(S) + 1
      delete(*R)
      *R = S
      weaken(*R)
Algorithm 3.11 Salkild's Update.
Page 64, Algorithm 3.15
  Update(R,S) =
      RC(S) = RC(S) + 1
      colour(R) = black       - `remove' R,S from control set
      colour(S) = black
      delete(*R)
      *R = S
Algorithm 3.15 Cyclic reference counting Update.
Page 66, Algorithm 3.20, the cell being swept into the free-list must be coloured black before its children are examined (otherwise the algorithm does not terminate) [3].
  collect_white(S) =
      if colour(S) == white
          colour(S) = black
	  for T in Children(S)
	      collect_white(*T)
	  free(S)
Algorithm 3.20 collect_white sweeps white cells into the free-list.

Page 63, paragraph five, Update should paint cells black not purple.

Page 69, last line: "method" should be "methods".

Chapter 4 Mark-Sweep Garbage Collection

Page 78, Algorithm 4.2: if this version of mark is used, mark_heap should not set mark bits [11].

Page 80, second paragraph, the figures given are in milliseconds, not microseconds as stated. The reference should be to [Zorn, 1990a], not to [Zorn, 1990b] [10].

Page 81, last paragraph, fifth sentence should read [10]:

"If none of the node's children are unmarked, that stack slot is deemed to be empty and is squeezed out by sliding up the next useful entry."
Page 89, Algoritm 4.4 should sweep again after marking the heap.
allocate() =
    while sweep < Heap_top               -- continue sweep
	if mark_bit(sweep) == marked
	    mark_bit(sweep) = unmarked
            sweep = sweep + size(sweep)
	else
            result = sweep
            sweep = sweep + size(sweep)
            return result

    mark_heap()                          -- heap is full

    sweep = Heap_bottom
    while sweep < Heap_top               -- try again
	if mark_bit(sweep) == marked
            mark_bit(sweep) = unmarked
            sweep = sweep + size(sweep)
	else
            result = sweep
            sweep = sweep + size(sweep)
            return result

    abort "Memory exhausted"
Algorithm 4.4 Lazy sweeping.

Page 87, the shift in the code fragment in the centre of the page should be 3 [2]. Thus
  mark_bit(p) =
      return bitmap[p>>3]
Page 92, the names of several instructions in Algorithms 4.5 and 4.6 of Zorn's allocation sequence are incorrect: sub does not set the condition codes, and bgz and load are not standard SPARC assembly instructions. Furthermore, brackets were omitted from ld and st instructions [2]. The correct versions are:
  -- is a collection needed? 
    subcc %g_allocated, ConsSize, %g_allocated 
    bg,a  noCollect 
    subcc %g_freeConsIndex, 4, %g_free_ConsIndex 
    call  Collect 
    nop 
    subcc %g_freeConsIndex, 4, %g_free_ConsIndex 

  noCollect: 
    -- need to sweep? 
    bg,a done 
    ld [%g_freeCons + %g_freeConsIndex], %result 
    call lazySweep 
    nop 
    ld [%g_freeCons + %g_freeConsIndex], %result 

  done: ...
Algorithm 4.5 Zorn's allocation sequence for cons cells

  lazySweep: 
    ... 
    -- %bitsLeft contains the remaining bits
    andcc %bitsLeft, 1, %thisBit 
    bnz,a nextBit 
    add %currentRef, ConsSize, %currentRef 

    -- sweep the word into the cons free-list
    st %currentRef, [%g_freeCons + %g_freeConsIndex] 
    add %g_freeConsIndex, 4, %g_free_ConsIndex 
    add %currentRef, ConsSize, %currentRef 

  nextBit: 
    -- on to the next bit 
    srl %bitsLeft, 1,%bitsLeft
Algorithm 4.6 The inner loop of Zorn's lazy-sweep allocator processes one bit of the bitmap.

Chapter 5 Mark-Compact Garbage Collection

Page 102, Algorithm 5.2 does not clear mark-bits [11].

relocate() =
    free=heap_bottom
    live=heap_top
    mark_bit(Heap[heap_top+1]) = unmarked           - sentinel 

    repeat
        while marked(free)                          - find the next hole
            mark_bit(Heap[free]) = unmarked
            free=free+1

        while not marked(live) and live > free      - find the previous live cell
            live=live-1

        if live>free
            mark_bit(Heap[live]) = unmarked         - unmark it 
            move(live, free)
            Heap[live] = free                       - leave forwarding address
            free=free+1
            live=live-1
    until live <= free
Algorithm 5.2 The first pass of the Two-Finger compaction algorithm

Page 104, Algorithm 5.5, the second line of compute_addresses should read [11]:

  P = Heap_bottom
  

Page 113, subsection Handling abnormal residencies should read: "Sansom has proposed..." [2].

Chapter 6 Copying Garbage Collection

Page 123, Algorithm 6.1 [7]. In order to fit with the procedure New given in Algorithm 2.7 on page 29 of Chapter 2 the flip should also reset the top_of_space to Tospace+space_size.

Page 123, penultimate paragraph [2]. All references to C in the last two sentences should be replaced by references to A. Thus: "The scan finds a pointer to A at left(F'). This pointer is updated with the forwarding address A' found in A (see diagram 6.5 on the next page)."

Page 125, Algorithm 6.2: the first two lines of Zorn's allocation sequence are similarly wrong [2]. They should be
  subcc %g_allocated, ConsSize, %g_allocated 
  bg,a noCollect
Page 125, Algorithm 6.3: the first line should be indented by one tab [2].

Page 139, Algorithm 6.4: for compatibility with New, Moon's flip should set top_of_space.
flip() =
  Fromspace, Tospace = Tospace, Fromspace
  top_of_space = Tospace + space_size
  scan, partial, free = Tospace

for R in Roots R = copy(R)
while scan < free scan_partial() scan_all()
Algorithm 6.4 Moon's approximately depth-first algorithm.
Page 140, Notes: in paragraph 3, the second sentence should read [5].
"Although they accepted Appel's general case, they found that heap allocation of procedure activation frames required an extra two instructions per call (to save the frame pointer and move the heap pointer) -- 18 percent more instructions than was needed for stack allocation."

Chapter 7 Generational Garbage Collection

Page 145: Apple's Smalltalk was never released.

Page 146, paragraph two should read [1]:

"On the other hand, the strong generational hypothesis, that the older an object is the less likely it is to die, does not appear to hold generally."
Page 147, paragraph two: the reachable cells in the younger generation are a, b, c and R.

Page 147, final paragraph: the last phrase of the fifth sentence should be deleted. Thus:
"Third, the minor collection successfully reclaimed all short-lived cells in the graph."
Page 156, Diagram 7.9: the size of the area marked `reserve' should be zero [1]. Thus


Diagram 7.9 Immediately after a major collection, but before the old generation is compacted.

The most recent versions of SML/NJ no longer use the simple two-generation collector described in the book and in Appel's 1989 paper Simple Generational Garbage Collection and Fast Allocation [1]. SML/NJ now uses a multigeneration collector implemented by John Reppy and described in A High-Performance Garbage Collector for Standard ML.

Appel points out that he no longer believes that heap limit checks should be done by a virtual-memory test [Appel, 1991; Appel, 1996]. This is discussed further on page 125 of my book.

Pages 157 and 158, the first lines of Algorithms 7.1 to 7.3 should be indented.

Page 169, Algorithm 7.4: the first line should be indented by one tab and the order of the arguments should be reversed [2]. Thus,
  st  %ptr, [%obj]     -- store ptr into obj
  st  %obj, [%ssb]     -- add obj to SSB
  add %ssb, 4, %ssb
Algorithm 7.4 The write-barrier for a sequential store buffer.

Page 169, penultimate paragraph, second sentence should read [8]:
"Notice that hashing prevents duplicate entries from being introduced from the SSB."

Pages 172-3: all the code fragments given in Hölzle's A Fast Write Barrier for Generational Garbage Collectors share similar errors of order of arguments to st, use of sll instead of srl for division and st instead of stb for clearing bytes [2]. Thus,
  st  %ptr, [%obj + offset]       -- store ptr into obj's field
  add %obj, offset, %temp          -- calculate address of updated word
  srl %temp, k, %temp             -- divide by card size, 2^k
  stb %g0, [%byte_map + %temp]    -- clear byte in byte_map
Algorithm 7.5 Chamber's write-barrier. k is log_2(card size).

  st  %ptr, [%obj + offset]       -- store ptr into obj's field
  srl %temp, k, %temp             -- calculate approximate byte index
  stb %g0, [%byte_map + %temp]    -- clear byte in byte_map
Algorithm 7.6 Hölzle's write-barrier.

Chapter 8 Incremental and Concurrent Garbage Collection

Page 190, Algorithm 8.2 should refer to k3 throughout the procedure sweep [8]. The algorithm is also clearer, and more consistent stylistically with Algorithm 8.3 if free_count is explicitly incremented by sweep rather than implicitly in free. Thus
sweep(k3) = 				sweep k3 items
    i = 0
    while i<k3 and sweeper <= Heap_top
	if mark_bit(sweeper) == unmarked
            free(sweeper)
	    increment free_count
	else mark_bit(sweeper) = unmarked
	increment sweeper
	i = i+1
Algorithm 8.2 Auxiliary procedures for Yuasa's algorithm.

There's also a stylistic inconsistency between Algorithms 8.2 and 8.3 on the page [8]. It would be better if mark in Algorithm 8.3 also took k1 as a parameter (rather than as a global variable).

Page 191, Algorithm 8.3 should also refer to save_stack rather than saved_stack [8].

Page 193, penultimate line should read [8]:
"The conservatism ..."

Page 195, Algorithm 8.7: in both cases in mark, finished should be set to mark_stack==empty [8]. Thus,
mark() =
    phase = mark_phase
    for R in Roots
	gcpush(R,mark_stack)
	mark1()

    for S in system_stack
	LOCK S, system_stack
            gcpush(S,mark_stack)
	mark1()

    LOCK gcstate
	finished = mark_stack==empty
    while not finished
	mark1()
	LOCK gcstate
            finished = mark_stack==empty
  
Algorithm 8.7 Steele's concurrent marker.
Pages 200 and 224, final paragraph, incorrectly claims that the first implementation of concurrent reference counting was the DEC Systems Research Center Modula-2+ collector by Paul Rovner and Butler Lampson. In fact the first implementation was by Rovner for the Cedar implementation from Xerox PARC [rovn85] [12].

 

Chapter 9 Garbage Collection for C

Page 230, penultimate paragraph, penultimate sentence: for code read data [8].

Page 237, Diagram 9.6 has the second block obscured by the shading.

Diagram 9.6 Space leaks in a cons-list are limited to the target of the false reference.

Page 242, first paragraph: the auxiliary list of unscanned blocks in Tospace is shown in Diagram 9.9 (not 9.8).

Page 243, Diagram 9.9 and the first paragraph, last sentence, could be improved as follows:

Diagram 9.9 Mostly Copying garbage collection.

"A drawback is that other objects in those blocks have also been retained (for example, object X in Diagram 9.9)."

Page 248, Algorithm 9.3: the first line should be indented by one tab [2].

Chapter 10 Garbage Collection for C++

Pages 260, 264 and 269, Algorithms 10.2 to 10.4: the first lines should be indented by one tab [2].

Page 260, Algorithm 10.2: the first line should be indented by one tab [2].

Chapter 11 Cache-conscious Garbage Collection

Page 289 says, "Goncalves and Appel confirm these predictions, using Appel's generational copying collector for SML/NJ." SML/NJ no longer uses the two-generation collector described in his 1989 paper Simple Generational Garbage Collection and Fast Allocation, but now uses a multigeneration collector implemented by John Reppy and described in A High-Performance Garbage Collector for Standard ML. It was this many-generation collector that the FPCA'95 paper measured [1].

Bibliography
Page 337, [Dickman, 1992] should refer to Peter Dickman's IWOOS'91 paper Effective Load Balancing in a Distributed Object-Support Operating System rather than his PhD thesis Distributed Object Management in a Non-Small Graph of Autonomous Networks with Few Failures [4].

Page 340, [Fiterman, 1995] was published in USENET comp.lang.c++ [2].

Acknowledgements

My thanks for pointing out errors go to:
  1. Andrew Appel
  2. Stephen Bevan
  3. Thomas Burri
  4. Peter Dickman
  5. Nick Barnes
  6. Morris Chang
  7. Tim Geisler
  8. Pekka Pirinen
  9. Sid Chatterjee
  10. Alex Garthwaite
  11. Matthieu Blondeau
  12. Hans Boehm
  13. Daniel Sobral
  14. Taiichi Yuasa
  15. Chai Sheng Hau
  16. Pete Sheill
  17. Paul McCullough
  18. Hai Fang
  19. Netheril Xie
  20. David Bacon
  21. Hanzu
  22. Suriya Subramanian

Richard Jones


[ book ] [ GC page ] [ home ]