Fix memory corruption bug in impl/memory

Fix memory corruption bug in impl/memory

When you `SetCollection` in gkvlite, it invalidates the old
collection, but keeps the Items of the previous collection. The way
that impl/memory was using SetCollection was more along the lines of
GetOrCreate, which could cause corruption or other issues if two
codepaths did SetCollection simultaneously.

This fixes the corruption bug by removing SetCollection from the
memStore interface and replaces it with a GetOrCreateCollection,
which checks for the collection, and only calls SetCollection if it
doesn't exist. As a bonus, this seems to give a slight performance
speedup over the previous broken code.

Additionally, this forces all uses of VisitItemsAscend to use
a Snapshot, to avoid accidental modification of a Collection while
its being iterated over, which can lead to the situation discussed
above, or other nasty errors.

Finally, this adds an optional 'gkvlite tracer' functionality
which came in (extremely) handy for finding this bug. When given
a folder, it will emit go-code-like invocations of the functions run
on every collection, and includes enough information to reveal which
functions are being called on the root collection v. snapshots, and
if there are any overlapping VisitItemsAscend invocations, etc.

R=dnj@chromium.org
BUG=550684
Committed: https://github.com/luci/gae/commit/e6d5b5947c9808f2ae778947377c2ef068510b34

[iannucci, 2016-04-22 03:33:17]

Example tracer output:

coll3 := newMemStore()
coll3_snap0 := coll3.Snapshot()
coll3_656e74733a := coll3.GetOrCreateCollection("ents:")
coll3_656e74733a.Get([]byte{0x88, 0x0, 0x1, 0x4d, 0xb7, 0xd9, 0x8d, 0x57, 0x60,
0x1, 0x80, 0x80, 0x1, 0x5f, 0xaf, 0xd9, 0xad, 0xe7, 0xa3, 0xa5, 0xe9, 0x79,
0xaf, 0xd9, 0xef, 0x27, 0x7b, 0xd5, 0xe1, 0x5f, 0xaf, 0xc0, 0x1, 0x80, 0x80,
0x0})
coll3_656e74733a.Set([]byte{0x88, 0x0, 0x1, 0x4d, 0xb7, 0xd9, 0x8d, 0x57, 0x60,
0x1, 0x80, 0x80, 0x1, 0x5f, 0xaf, 0xd9, 0xad, 0xe7, 0xa3, 0xa5, 0xe9, 0x79,
0xaf, 0xd9, 0xef, 0x27, 0x7b, 0xd5, 0xe1, 0x5f, 0xaf, 0xc0, 0x1, 0x80, 0x80,
0x0}, []byte{0x80, 0x80, 0x5f, 0xaf, 0xdd, 0xcd, 0x57, 0x93, 0xcd, 0xd3, 0x6f,
0xb7, 0x97, 0xeb, 0xf0, 0x80, 0x80, 0x1, 0x80, 0x80})
coll3_656e74733a.Get([]byte{0x88, 0x0, 0x1, 0x4d, 0xb7, 0xd9, 0x8d, 0x57, 0x60,
0x1, 0x80, 0x80, 0x0})
coll3_656e74733a.Set([]byte{0x88, 0x0, 0x1, 0x4d, 0xb7, 0xd9, 0x8d, 0x57, 0x60,
0x1, 0x80, 0x80, 0x0}, []byte{0x80, 0x80, 0x55, 0x35, 0x5b, 0xad, 0x50, 0x80,
0x80, 0x82, 0x80, 0x0})
coll3_snap1 := coll3.Snapshot()
// coll3_snap1.GetCollection("idx") -> nil
coll4 := newMemStore()
coll4_696478 := coll4.GetOrCreateCollection("idx")
coll5 := newMemStore()
coll5_696478 := coll5.GetOrCreateCollection("idx")
coll4_696478.Set([]byte{0x4d, 0xb7, 0xd9, 0x8d, 0x57, 0x60, 0x0, 0x1, 0x0, 0x5f,
0xaf, 0xdb, 0x6d, 0x57, 0xcb, 0x7d, 0xbf, 0x0, 0x0}, []byte{})
coll5_696478.Set([]byte{0x6b, 0xb7, 0x99, 0x80, 0x0, 0x1, 0x0, 0x5f, 0xaf, 0xdb,
0x6d, 0x57, 0xcb, 0x7d, 0xbf, 0x0, 0x0}, []byte{})
coll5_6964783a6e733a6bb799800001005fafdb6d57cb7dbf0000 :=
coll5.GetOrCreateCollection("idx:ns:k\xb7\x99\x80\x00\x01\x00_\xaf\xdbmW\xcb}\xbf\x00\x00")
coll5_6964783a6e733a6bb799800001005fafdb6d57cb7dbf0000.Set([]byte{0x88, 0x0,
0x1, 0x71, 0x31, 0x5d, 0x4d, 0x57, 0x73, 0xd1, 0x97, 0x69, 0xb7, 0x99, 0x80,
0x5, 0x73, 0xb5, 0x59, 0x80, 0x1, 0x6b, 0xb7, 0x99, 0x80, 0x1, 0x83, 0xa0, 0x0},
[]byte{})
coll5_696478.Set([]byte{0x6b, 0xb7, 0x99, 0x80, 0x0, 0x1, 0x0, 0x5f, 0xaf, 0xdb,
0x6d, 0x57, 0xcb, 0x7d, 0xbf, 0x0, 0x1, 0x0, 0x6f, 0x33, 0x5d, 0x4d, 0x40, 0x0},
[]byte{})

[iannucci, 2016-04-22 04:01:44]

Description was changed from

==========
Fix memory corruption bug in impl/memory

When you `SetCollection` in gkvlite, it invalidates the old
collection, but keeps the Items of the previous collection. The way
that impl/memory was using SetCollection was more along the lines of
GetOrCreate, which could cause corruption or other issues if two
codepaths did SetCollection simultaneously.

This fixes the corruption bug by removing SetCollection from the
memStore interface and replaces it with a GetOrCreateCollection,
which checks for the collection, and only calls SetCollection if it
doesn't exist. As a bonus, this seems to give a slight performance
speedup over the previous broken code.

Additionally, this forces all uses of VisitItemsAscend to use
a Snapshot, to avoid accidental modification of a Collection while
its being iterated over, which can lead to the situation discussed
above, or other nasty errors.

Finally, this adds an optional 'gkvlite tracer' functionality
which came in (extremely) handy for finding this bug. When given
a folder, it will emit go-code-like invocations of the functions run
on every collection, and includes enough information to reveal which
functions are being called on the root collection v. snapshots, and
if there are any overlapping VisitItemsAscend invocations, etc.

R=dnj@chromium.org
BUG=
==========

to

==========
Fix memory corruption bug in impl/memory

When you `SetCollection` in gkvlite, it invalidates the old
collection, but keeps the Items of the previous collection. The way
that impl/memory was using SetCollection was more along the lines of
GetOrCreate, which could cause corruption or other issues if two
codepaths did SetCollection simultaneously.

This fixes the corruption bug by removing SetCollection from the
memStore interface and replaces it with a GetOrCreateCollection,
which checks for the collection, and only calls SetCollection if it
doesn't exist. As a bonus, this seems to give a slight performance
speedup over the previous broken code.

Additionally, this forces all uses of VisitItemsAscend to use
a Snapshot, to avoid accidental modification of a Collection while
its being iterated over, which can lead to the situation discussed
above, or other nasty errors.

Finally, this adds an optional 'gkvlite tracer' functionality
which came in (extremely) handy for finding this bug. When given
a folder, it will emit go-code-like invocations of the functions run
on every collection, and includes enough information to reveal which
functions are being called on the root collection v. snapshots, and
if there are any overlapping VisitItemsAscend invocations, etc.

R=dnj@chromium.org
BUG=550684
==========

[dnj, 2016-04-22 06:09:45]

Mostly looks good, a handful of comments.

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
File impl/memory/gkvlite_tracing_utils.go (right):

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_tracing_utils.go:19: var logMemCollectionFolder =
flag.String(
Note this will be compiled into every binary. It may be worth splitting this off
as a sub-package. Just a thought.

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_tracing_utils.go:40: fmt.Fprintln(os.Stderr, "REMOVING LOG
COLLECTION FOLDER:", *logMemCollectionFolder)
The possibility of me doing something stupid here like setting this to "/tmp" or
"$HOME" makes me really scared about the RemoveAll part. WDYT about just using
the folder. If the user wants to clean it, they can "rm" its contents before
running the code pretty easily:

$ rm $PLACE; go test -v luci.gae.gkvlite_trace_folder=$PLACE

That or create a "luci-gae"-prefixed tempdir within the folder that is specified
and write there. This has the added benefit of letting the user easily compare
different runs, and cleanup is just "rm -rf $PLACE/luci-gae*"

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_tracing_utils.go:44: if err :=
os.MkdirAll(*logMemCollectionFolder, 0755); err != nil {
I would say the user should ensure that the directory exists, and it's an error
if it doesn't.

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_tracing_utils.go:50: fname := fmt.Sprintf("%s/%d.trace",
*logMemCollectionFolder, logNum)
Use filepath.Join: https://golang.org/pkg/path/filepath/#Join

Also should probably abspath *logMemCollectionFolder to remove any problems if
the user changes CWD an the path is relative. You are a mere package after all
:)

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_tracing_utils.go:87: if format[0] == '/' { // comment
Might as well just do a strings.HasPrefix("//") to be clear here.

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_tracing_utils.go:132: t.snapNum++
Non-atomic? Is Snapshot not goroutine-safe? I suppose not, since gkvlite needs
locks. Just checking though.

If not, just use an "int" here instead of a uint32. This is a thing I think we
settled on a few months back.

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_tracing_utils.go:178: vnum := t.visitNumber
Same, non-atomic check? If not, just use an "int" here instead of a uint32. This
is a thing I think we settled on a few months back.

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
File impl/memory/gkvlite_utils.go (right):

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_utils.go:18: panic("gkvCollide: old collection is rw")
nit: not sure if you need "gkvCollide" prefix here, since the panic will include
a stack trace *shrug*

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_utils.go:80: GetCollection(name string) memCollection
nit: these *could* all be lowercase methods, since none of this is exported.
OTOH if you split tracer into a package, upper-case makes sense.

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_utils.go:95: Name() string
(same r.e. export)

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_utils.go:132: runtime.SetFinalizer(ret, func(s
*gkvlite.Store) { go s.Close() })
If we're doing this, should we just have store/collection export Close and use
conventional channels? This'd also let you avoid the finalizer Close for the
tracer.

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_utils.go:191: panic("attempting to VisitItemsAscend from r/w
memCollection")
nit: above you use "rw", might as well be consistent.

[iannucci, 2016-04-22 06:56:25]

PTAL

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
File impl/memory/gkvlite_tracing_utils.go (right):

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_tracing_utils.go:19: var logMemCollectionFolder =
flag.String(
On 2016/04/22 06:09:44, dnj wrote:
> Note this will be compiled into every binary. It may be worth splitting this
off
> as a sub-package. Just a thought.

I thought about that, but I think it'll be worse to have to change the source
and recompile to debug a crash (if there is one).

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_tracing_utils.go:40: fmt.Fprintln(os.Stderr, "REMOVING LOG
COLLECTION FOLDER:", *logMemCollectionFolder)
On 2016/04/22 06:09:44, dnj wrote:
> The possibility of me doing something stupid here like setting this to "/tmp"
or
> "$HOME" makes me really scared about the RemoveAll part. WDYT about just using
> the folder. If the user wants to clean it, they can "rm" its contents before
> running the code pretty easily:
> 
> $ rm $PLACE; go test -v luci.gae.gkvlite_trace_folder=$PLACE
> 
> That or create a "luci-gae"-prefixed tempdir within the folder that is
specified
> and write there. This has the added benefit of letting the user easily compare
> different runs, and cleanup is just "rm -rf $PLACE/luci-gae*"

Good point, changed to use a tempdir at the designated folder.

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_tracing_utils.go:44: if err :=
os.MkdirAll(*logMemCollectionFolder, 0755); err != nil {
On 2016/04/22 06:09:44, dnj wrote:
> I would say the user should ensure that the directory exists, and it's an
error
> if it doesn't.

Acknowledged.

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_tracing_utils.go:50: fname := fmt.Sprintf("%s/%d.trace",
*logMemCollectionFolder, logNum)
On 2016/04/22 06:09:44, dnj wrote:
> Use filepath.Join: https://golang.org/pkg/path/filepath/#Join
> 
> Also should probably abspath *logMemCollectionFolder to remove any problems if
> the user changes CWD an the path is relative. You are a mere package after all
> :)

Done.

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_tracing_utils.go:87: if format[0] == '/' { // comment
On 2016/04/22 06:09:44, dnj wrote:
> Might as well just do a strings.HasPrefix("//") to be clear here.

Done.

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_tracing_utils.go:132: t.snapNum++
On 2016/04/22 06:09:44, dnj wrote:
> Non-atomic? Is Snapshot not goroutine-safe? I suppose not, since gkvlite needs
> locks. Just checking though.
> 

not safe, snapshot already needs a lock.

> If not, just use an "int" here instead of a uint32. This is a thing I think we
> settled on a few months back.

uint is the correct type to use here, since we don't use this for subtraction,
and negative values will cause invalid trace file content. Changed to uint.

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_tracing_utils.go:178: vnum := t.visitNumber
On 2016/04/22 06:09:44, dnj wrote:
> Same, non-atomic check? If not, just use an "int" here instead of a uint32.
This
> is a thing I think we settled on a few months back.

changed to uint

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
File impl/memory/gkvlite_utils.go (right):

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_utils.go:18: panic("gkvCollide: old collection is rw")
On 2016/04/22 06:09:45, dnj wrote:
> nit: not sure if you need "gkvCollide" prefix here, since the panic will
include
> a stack trace *shrug*

Done.

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_utils.go:80: GetCollection(name string) memCollection
On 2016/04/22 06:09:45, dnj wrote:
> nit: these *could* all be lowercase methods, since none of this is exported.
> OTOH if you split tracer into a package, upper-case makes sense.

I'd rather stick with uppercase, since it means that something else /could/
implement it easily. There's no reason not to.

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_utils.go:132: runtime.SetFinalizer(ret, func(s
*gkvlite.Store) { go s.Close() })
On 2016/04/22 06:09:45, dnj wrote:
> If we're doing this, should we just have store/collection export Close and use
> conventional channels? This'd also let you avoid the finalizer Close for the
> tracer.

I'm not aware of any benefit to doing this. Additionally, I can think of at
least one downside (the API for snapshots, both internally to the package, and
externally to users) will be made more complex. A finalizer seems perfectly
appropriate here. Note also that this is not a new behavior: the old code has
always done this.

https://chromiumcodereview.appspot.com/1911263002/diff/1/impl/memory/gkvlite_...
impl/memory/gkvlite_utils.go:191: panic("attempting to VisitItemsAscend from r/w
memCollection")
On 2016/04/22 06:09:45, dnj wrote:
> nit: above you use "rw", might as well be consistent.

Done.

[dnj, 2016-04-22 16:00:00]

lgtm

[iannucci, 2016-04-22 16:24:30]

The CQ bit was checked by iannucci@chromium.org

[commit-bot: I haz the power, 2016-04-22 16:24:35]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1911263002/20001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1911263002/20001

[commit-bot: I haz the power, 2016-04-22 16:29:50]

Description was changed from

==========
Fix memory corruption bug in impl/memory

When you `SetCollection` in gkvlite, it invalidates the old
collection, but keeps the Items of the previous collection. The way
that impl/memory was using SetCollection was more along the lines of
GetOrCreate, which could cause corruption or other issues if two
codepaths did SetCollection simultaneously.

This fixes the corruption bug by removing SetCollection from the
memStore interface and replaces it with a GetOrCreateCollection,
which checks for the collection, and only calls SetCollection if it
doesn't exist. As a bonus, this seems to give a slight performance
speedup over the previous broken code.

Additionally, this forces all uses of VisitItemsAscend to use
a Snapshot, to avoid accidental modification of a Collection while
its being iterated over, which can lead to the situation discussed
above, or other nasty errors.

Finally, this adds an optional 'gkvlite tracer' functionality
which came in (extremely) handy for finding this bug. When given
a folder, it will emit go-code-like invocations of the functions run
on every collection, and includes enough information to reveal which
functions are being called on the root collection v. snapshots, and
if there are any overlapping VisitItemsAscend invocations, etc.

R=dnj@chromium.org
BUG=550684
==========

to

==========
Fix memory corruption bug in impl/memory

When you `SetCollection` in gkvlite, it invalidates the old
collection, but keeps the Items of the previous collection. The way
that impl/memory was using SetCollection was more along the lines of
GetOrCreate, which could cause corruption or other issues if two
codepaths did SetCollection simultaneously.

This fixes the corruption bug by removing SetCollection from the
memStore interface and replaces it with a GetOrCreateCollection,
which checks for the collection, and only calls SetCollection if it
doesn't exist. As a bonus, this seems to give a slight performance
speedup over the previous broken code.

Additionally, this forces all uses of VisitItemsAscend to use
a Snapshot, to avoid accidental modification of a Collection while
its being iterated over, which can lead to the situation discussed
above, or other nasty errors.

Finally, this adds an optional 'gkvlite tracer' functionality
which came in (extremely) handy for finding this bug. When given
a folder, it will emit go-code-like invocations of the functions run
on every collection, and includes enough information to reveal which
functions are being called on the root collection v. snapshots, and
if there are any overlapping VisitItemsAscend invocations, etc.

R=dnj@chromium.org
BUG=550684

Committed:
https://github.com/luci/gae/commit/e6d5b5947c9808f2ae778947377c2ef068510b34
==========

[commit-bot: I haz the power, 2016-04-22 16:29:51]

Committed patchset #2 (id:20001) as
https://github.com/luci/gae/commit/e6d5b5947c9808f2ae778947377c2ef068510b34