Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

runtime: filepath.Walk panics on huge tree traversal #15615

Closed
iafan opened this issue May 9, 2016 · 12 comments
Closed

runtime: filepath.Walk panics on huge tree traversal #15615

iafan opened this issue May 9, 2016 · 12 comments

Comments

@iafan
Copy link

iafan commented May 9, 2016

My environment:

> go version
go version go1.6.2 windows/amd64

> go env
set GOARCH=amd64
set GOBIN=
set GOEXE=.exe
set GOHOSTARCH=amd64
set GOHOSTOS=windows
set GOOS=windows
set GOPATH=C:\Storage\Work\Go
set GORACE=
set GOROOT=C:\Program Files (x86)\Go
set GOTOOLDIR=C:\Program Files (x86)\Go\pkg\tool\windows_amd64
set GO15VENDOREXPERIMENT=1
set CC=gcc
set GOGCCFLAGS=-m64 -mthreads -fmessage-length=0
set CXX=g++
set CGO_ENABLED=1

Test script:

package main

import (
    "os"
    "path/filepath"
    "sync/atomic"
)

var folderCount = 0

func callback(path string, info os.FileInfo, err error) error {
    if info.IsDir() {
        folderCount++
    }
    return nil
}

func main() {
    filepath.Walk("C:\\path\\to\\some\\huge\\dir", callback)
}

When I run this script against a directory that contains ~150K folders and ~1M files (the actual folder I tried this on contained about 50 big project checkouts with pretty deep tree structure), the program works for several seconds, then crashes:

panic: runtime error: invalid memory address or nil pointer dereference

Experiment 1: if I comment out the if info.IsDir() { ... } clause (replace it with simply folderCount++), there will be no crash.

Experiment 2: if I replace the filepath.Walk with my own implementation of this function that doesn't use recursion, the program won't crash either.

So my current understanding is that this happens due to a combination of a recursive algorithm (which might take much stack/memory) and some specific code inside a callback.


A related question: did you consider getting rid of the recursive algorithm in filepath.Walk? I experimented with an alternative implementation of this function that uses goroutines/workers, and it seems not only to work correctly on huge directory trees, but also gives performance boost due to parallelism.

@bradfitz bradfitz added this to the Go1.7 milestone May 9, 2016
@bradfitz
Copy link
Contributor

bradfitz commented May 9, 2016

Let's keep this bug focused on the crash (which should not happen) and not alternate implementations of filepath.Walk. That has been discussed elsewhere, IIRC. Feel free to open a separate bug for that and we can de-dup if necessary.

@bradfitz
Copy link
Contributor

bradfitz commented May 9, 2016

Which version of Windows are you using?

Please run with GOTRACEBACK=all and post the full crash backtrace.

/cc @alexbrainman (for Windows)

@bradfitz bradfitz changed the title filepath.Walk() panics on huge tree traversal runtime: filepath.Walk panics on huge tree traversal May 9, 2016
@iafan
Copy link
Author

iafan commented May 9, 2016

Windows 10, 16 GB of RAM.

Here's the full traceback:

panic: runtime error: invalid memory address or nil pointer dereference
[signal 0xc0000005 code=0x0 addr=0x20 pc=0x401074]

goroutine 1 [running]:
panic(0x4fec80, 0xc0820040a0)
    C:/Program Files (x86)/Go/src/runtime/panic.go:481 +0x3f4
main.callback(0xc082374240, 0x104, 0x0, 0x0, 0x2690ab0, 0xc08229ecf0, 0x0, 0x0)
    C:/Storage/Work/Go/src/github.com/iafan/cwalk/cmd/~bug.go:14 +0x34
path/filepath.walk(0xc082369100, 0xf7, 0x6d41c0, 0xc08236c660, 0x555698, 0x0, 0x0)
    C:/Program Files (x86)/Go/src/path/filepath/path.go:370 +0x41c
path/filepath.walk(0xc08235fe00, 0xe8, 0x6d41c0, 0xc08236c3c0, 0x555698, 0x0, 0x0)
    C:/Program Files (x86)/Go/src/path/filepath/path.go:374 +0x503
path/filepath.walk(0xc082355340, 0xdb, 0x6d41c0, 0xc08236c060, 0x555698, 0x0, 0x0)
    C:/Program Files (x86)/Go/src/path/filepath/path.go:374 +0x503
path/filepath.walk(0xc082350680, 0xd0, 0x6d41c0, 0xc08224c6c0, 0x555698, 0x0, 0x0)
    C:/Program Files (x86)/Go/src/path/filepath/path.go:374 +0x503
path/filepath.walk(0xc08221fba0, 0xc3, 0x6d41c0, 0xc08224c420, 0x555698, 0x0, 0x0)
    C:/Program Files (x86)/Go/src/path/filepath/path.go:374 +0x503
path/filepath.walk(0xc08224b740, 0xb9, 0x6d41c0, 0xc08224c240, 0x555698, 0x0, 0x0)
    C:/Program Files (x86)/Go/src/path/filepath/path.go:374 +0x503
path/filepath.walk(0xc08223cf20, 0xac, 0x6d41c0, 0xc08222fbc0, 0x555698, 0x0, 0x0)
    C:/Program Files (x86)/Go/src/path/filepath/path.go:374 +0x503
path/filepath.walk(0xc08223c4d0, 0xa3, 0x6d41c0, 0xc08222f7a0, 0x555698, 0x0, 0x0)
    C:/Program Files (x86)/Go/src/path/filepath/path.go:374 +0x503
path/filepath.walk(0xc08228f680, 0x96, 0x6d41c0, 0xc08222f500, 0x555698, 0x0, 0x0)
    C:/Program Files (x86)/Go/src/path/filepath/path.go:374 +0x503
path/filepath.walk(0xc0820bf7a0, 0x84, 0x6d41c0, 0xc0822f37a0, 0x555698, 0x0, 0x0)
    C:/Program Files (x86)/Go/src/path/filepath/path.go:374 +0x503
path/filepath.walk(0xc0820b1c00, 0x77, 0x6d41c0, 0xc0822f3440, 0x555698, 0x0, 0x0)
    C:/Program Files (x86)/Go/src/path/filepath/path.go:374 +0x503
path/filepath.walk(0xc0822af9d0, 0x6e, 0x6d41c0, 0xc0820a5680, 0x555698, 0x0, 0x0)
    C:/Program Files (x86)/Go/src/path/filepath/path.go:374 +0x503
path/filepath.walk(0xc0822af420, 0x61, 0x6d41c0, 0xc0820a53e0, 0x555698, 0x0, 0x0)
    C:/Program Files (x86)/Go/src/path/filepath/path.go:374 +0x503
path/filepath.walk(0xc082198140, 0x4a, 0x6d41c0, 0xc082210f00, 0x555698, 0x0, 0x0)
    C:/Program Files (x86)/Go/src/path/filepath/path.go:374 +0x503
path/filepath.walk(0xc082437b00, 0x3d, 0x6d41c0, 0xc0820cf440, 0x555698, 0x0, 0x0)
    C:/Program Files (x86)/Go/src/path/filepath/path.go:374 +0x503
path/filepath.walk(0x542c40, 0x23, 0x6d41c0, 0xc08200e300, 0x555698, 0x0, 0x0)
    C:/Program Files (x86)/Go/src/path/filepath/path.go:374 +0x503
path/filepath.Walk(0x542c40, 0x23, 0x555698, 0x0, 0x0)
    C:/Program Files (x86)/Go/src/path/filepath/path.go:396 +0xe8
main.main()
    C:/Storage/Work/Go/src/github.com/iafan/cwalk/cmd/~bug.go:27 +0x58
exit status 2

@bradfitz
Copy link
Contributor

bradfitz commented May 9, 2016

Thanks. 17-18 frames isn't very deep.

@iafan
Copy link
Author

iafan commented May 9, 2016

I also updated the sample code — it's actually the if info.IsDir() { ... } inside the callback that makes things bad.

@bradfitz
Copy link
Contributor

bradfitz commented May 9, 2016

Thanks for the update. For future reference, try not to update previous comments, as it makes following threads difficult. In this case it's probably, since it's already been done, and the thread is new.

@minux
Copy link
Member

minux commented May 9, 2016

OK, that's expected then.

callback is called with a nil info and non-nil error.
I think callback should check err first before looking
at info.

Closing, please comment if you disagree.

@minux minux closed this as completed May 9, 2016
@bradfitz
Copy link
Contributor

bradfitz commented May 9, 2016

Indeed, you can see the nil os.FileInfo here and the non-nil error:

main.callback(0xc082374240, 0x104, 0x0, 0x0, 0x2690ab0, 0xc08229ecf0, 0x0, 0x0)

(The first two are the path, the next two are the FileInfo, and the 5th/6th are the non-nil error)

@iafan
Copy link
Author

iafan commented May 9, 2016

@minux @bradfitz thanks much!

Indeed, the culprit was that for certain paths which are more than 255 characters long (and this is a path size limit in non-Unicode Windows API) there was an error reported:
GetFileAttributesEx: C:\Storage\Work\xxxxxxxx\xxxxxxxxxx\xxxxxxxxxxxxxxxxxxxxxxxxx\node_modules\juice\node_modules\web-resource-inliner\node_modules\request\node_modules\har-validator\node_modules\is-my-json-valid\node_modules\generate-object-property\node_modules\is-property\package.json: The system cannot find the path specified.

A solution (for others who stumble into this) would be to prepend the passed path with \\?\, e.g.:

filepath.Walk("\\\\?\\C:\\path\\to\\some\\dir")

This will make sure that GetFileAttributesEx uses the newer Unicode-aware code which has the path size limit extended to 32767 characters.

@bradfitz
Copy link
Contributor

bradfitz commented May 9, 2016

#3358 strikes again.

@ipstone
Copy link

ipstone commented Nov 9, 2016

I bumped into this bug also, on windows 7, with go 1.6, as well as go 1.7.3.
As i followed the #3358, that ticket was closed, but it's still not fixed?

@bradfitz
Copy link
Contributor

bradfitz commented Nov 9, 2016

The fix for this (231aa9d) will be in Go 1.8.

@golang golang locked and limited conversation to collaborators Nov 9, 2017
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

6 participants