Recursion in golang is giving deadlock or negative WaitGroup counter when using goroutines, channels and sync.Waitgroup

Question

I am trying to find the list of all directories using a recursive function. The code to the function is

func FindDirs(dir string, nativePartitions []int64, wg *sync.WaitGroup, dirlistchan chan string) {
    // defer wg.Done here will give negative waitgroup panic, commenting it will give negative waitgroup counter panic
    fd, err := os.Open(dir)
    if err != nil {
        panic(err)
    }
    filenames, err := fd.Readdir(0)
    if err != nil {
        panic(err)
    }

    for _, i := range filenames {

        var buff bytes.Buffer
        buff.WriteString(dir)
        switch dir {
        case "/":
        default:
            buff.WriteString("/")
        }

        buff.WriteString(i.Name())
        /*err := os.Chdir(dir)
        if err != nil {
            return err
        }*/

        t := new(syscall.Statfs_t)
        err = syscall.Statfs(buff.String(), t)
        if err != nil {
            //fmt.Println("Error accessing", buff.String())
        }
        if checkDirIsNative(t.Type, nativePartitions) && i.IsDir(){
            dirlistchan <- buff.String()
            FindDirs(buff.String(), nativePartitions, wg, dirlistchan) //recursion happens here
        } else {
            //fmt.Println(i.Name(), "is not native")
        }


    }
}

and in the main function, I am calling it as

wg := new(sync.WaitGroup)
dirlistchan := make(chan string, 1000)
wg.Add(1)
go func() {
    filtermounts.FindDirs(parsedConfig.ScanFrom, []int64{filtermounts.EXT4_SUPER_MAGIC}, wg, dirlistchan)
}()


go func() {
    wg.Wait()
    close(dirlistchan)
}()
for i := range dirlistchan {
    fmt.Println(i)
}
wg.Wait()

and I am getting a

fatal error: all goroutines are asleep - deadlock!

I was able to get this working if I am printing the result instead of using channels, or append to a slice using mutex. (verified with the linux find command to see if the results are same.) Please find the function after omitting channels and using sync.Mutex and append.

func FindDirs(dir string, nativePartitions []int64, dirlist *[]string, mutex *sync.Mutex) []string{


    fd, err := os.Open(dir)
    defer fd.Close()
    if err != nil {
        panic(err)
    }
    filenames, err := fd.Readdir(0)
    if err != nil {
        panic(err)
    }

    for _, i := range filenames {
        var buff bytes.Buffer
        buff.WriteString(dir)
        switch dir {
        case "/":
        default:
            buff.WriteString("/")
        }

        buff.WriteString(i.Name())
        /*err := os.Chdir(dir)
        if err != nil {
            return err
        }*/

        t := new(syscall.Statfs_t)
        err = syscall.Statfs(buff.String(), t)
        if err != nil {
            //fmt.Println("Error accessing", buff.String())
        }
        if checkDirIsNative(t.Type, nativePartitions) && i.IsDir(){
            //dirlistchan <- buff.String()
            mutex.Lock()
            *dirlist = append(*dirlist, buff.String())
            mutex.Unlock()
            //fmt.Println(buff.String())

            FindDirs(buff.String(), nativePartitions, dirlist, mutex)
        } else {
            //fmt.Println(i.Name(), "is not native")
        }

    }
    return *dirlist
}

But I cannot think of a way to make this work with channels and goroutines. Any help is greatly appreciated.

Note: Here is a link to the golang playground with the code. I couldn't find a workaround to get the syscall thing to work on the playground either. It works on my system though.

Thanks.

Answer 1

Short answer : You are not closing the channel.

Fix : add defer wg.Done() at beginning of the go routine that calls FindDirs

go func() {
    defer wg.Done()
    filtermounts.FindDirs(parsedConfig.ScanFrom, []int64{filtermounts.EXT4_SUPER_MAGIC}, wg, dirlistchan)
}()

Why did it happen

The go routine that is responsponsible for closing the channel waits for wg there is no wg.Done in the code above. So close never happens

Now the for loop blocks on the channel for close or a value for ever, this cause the error

fatal error: all goroutines are asleep - deadlock!

So here is your code ,this may be run as

go run filename.go /path/to/folder

Code

package main

import (
    "bytes"
    "fmt"
    "os"
    "sync"
    "syscall"
)

func main() {

    wg := new(sync.WaitGroup)
    dirlistchan := make(chan string, 1000)
    wg.Add(1)
    go func() {
        defer wg.Done()
        FindDirs(os.Args[1], []int64{61267}, wg, dirlistchan)
    }()

    go func() {
        wg.Wait()
        close(dirlistchan)
    }()
    for i := range dirlistchan {
        fmt.Println(i)
    }
    wg.Wait()

}

func FindDirs(dir string, nativePartitions []int64, wg *sync.WaitGroup, dirlistchan chan string) {
    fd, err := os.Open(dir)
    if err != nil {
        panic(err)
    }
    filenames, err := fd.Readdir(0)
    if err != nil {
        panic(err)
    }

    for _, i := range filenames {

        var buff bytes.Buffer
        buff.WriteString(dir)
        switch dir {
        case "/":
        default:
            buff.WriteString("/")
        }

        buff.WriteString(i.Name())
        /*err := os.Chdir(dir)
          if err != nil {
              return err
          }*/

        t := new(syscall.Statfs_t)
        err = syscall.Statfs(buff.String(), t)
        if err != nil {
            //fmt.Println("Error accessing", buff.String())
        }
        if checkDirIsNative(t.Type, nativePartitions) && i.IsDir() {
            dirlistchan <- buff.String()
            FindDirs(buff.String(), nativePartitions, wg, dirlistchan) //recursion happens here
        } else {
            //fmt.Println(i.Name(), "is not native")
        }

    }
}

func checkDirIsNative(dirtype int64, nativetypes []int64) bool {
    for _, i := range nativetypes {
        if dirtype == i {
            return true
        }
    }
    return false
}

Find the go.play link here

Answer 2

As has been stated already you should close the channel if you want the main goroutine to exit.

Example of implementation : In function func FindDirs you could make an additional channel for every recursive func FindDirs call that this function is going to make and pass that new channel in the argument. Then simultaneously listen to all those new channels and forward the strings back to the channel that function got in the argument. After all new channels has been closed close the channel given in the argument.

In other words every func call should have its own channel that it sends to. The string is then forwarded all the way to main function.

Dynamic select described here : how to listen to N channels? (dynamic select statement)