GC does not collect cycles with finalizers

[dvyukov]

> What steps will reproduce the problem?

package main

import "runtime"

func main() {
    c := make(chan bool)
    func() {
        type X struct {
            next *X
        }
        fin := func(_ *X) {
            c <- true
        }

        x := new(X)
        x.next = x
        runtime.SetFinalizer(x, fin)

        x1 := new(X)
        x2 := new(X)
        x1.next = x2
        x2.next = x1
        runtime.SetFinalizer(x1, fin)
        runtime.SetFinalizer(x2, fin)
    }()

    go func() {
        for {
            runtime.GC()
            runtime.Gosched()
        }
    }()

    <-c
    <-c
    <-c
}

> What is the expected output? What do you see instead?

The program must terminate. The program hangs.

> Please use labels and text to provide additional information.

gc/linux/amd64
10044:c587bcb93290 tip

[dvyukov]

Comment 1:

fintab should not be considered as GC root in full sense.
I think finalizer processing must be implemented along the lines of:
void markfin(void *p, uintptr n)
{
  if(marked(p))
    return;
  scanblock(p, n);
  setmarked(p, 0);
}
It must be done serially and preferably after the parallel stage.

[rsc]

Comment 2:

It is impossible to collect cycles with finalizers.
The documentation makes clear not to do this.

Status changed to WorkingAsIntended.

[dvyukov]

Comment 3:

Is the following program intended to work?
package main
import "runtime"
func main() {
    c := make(chan bool)
    func() {
        type X struct {
            next *X
        }
        x := new(X)
        x.next = x
        runtime.SetFinalizer(x, func(_ *X) {
            c <- true
        })
    }()
    go func() {
        for {
            runtime.GC()
            runtime.Gosched()
        }
    }()
    <-c
}

[rsc]

Comment 4:

No, that program doesn't work, because it is finalizing
something with a cycle.  From godoc runtime SetFinalizer:
...
Finalizers are run in dependency order: if A points at B, both have
finalizers, and they are otherwise unreachable, only the finalizer
for A runs; once A is freed, the finalizer for B can run.
If a cyclic structure includes a block with a finalizer, that
cycle is not guaranteed to be garbage collected and the finalizer
is not guaranteed to run, because there is no ordering that
respects the dependencies.
...

[dvyukov]

Comment 5:

Hummm.. Why it is that way? Why I can reclaim memory from cycles, but can't reclaim,
say, files from cycles? Why do dependencies (and self-dependencies) play any role? If an
object is not references from roots (fintab is not a root), then it can be collected at
any point IMVHO. In the program x/x1/x2 are not references from any roots, so can be
finalized and any point...

[rsc]

Comment 6:

http://www.hpl.hp.com/personal/Hans_Boehm/gc/finalization.html

[dvyukov]

Comment 7:

I see. They appeal to "dangling pointers", it won't be the case in Go, in Go a resource
would be able reference another finalized resource (closed file). But still makes sense.