Simple memory testing for gae/wrapper

go/src/infra/gae/libs/wrapper/memory/datastore_data.go

Index: go/src/infra/gae/libs/wrapper/memory/datastore_data.go
diff --git a/go/src/infra/gae/libs/wrapper/memory/datastore_data.go b/go/src/infra/gae/libs/wrapper/memory/datastore_data.go
new file mode 100644
index 0000000000000000000000000000000000000000..a9a3fe793f1989fde13b86077dc7177349519f6a
--- /dev/null
+++ b/go/src/infra/gae/libs/wrapper/memory/datastore_data.go
@@ -0,0 +1,481 @@
+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+package memory
+
+import (
+	"errors"
+	"math/rand"
+	"sync"
+	"sync/atomic"
+
+	"appengine/datastore"
+	pb "appengine_internal/datastore"
+
+	"github.com/mjibson/goon"
+
+	"infra/gae/libs/wrapper"
+)
+
+////////////////////////////////// knrKeeper ///////////////////////////////////
+
+type knrKeeper struct {
+	lock sync.RWMutex

[M-A Ruel, 2015/05/25 18:21:09]

When the readers hold the lock for a trivial amount of time like here (line 38),
it's often more performant to use a normal sync.Mutex, due to its simplicity. In
particular, the chances to hit the fast path referenced below is extremely high,
offsetting the potential speed up by enabling concurrent access.

http://golang.org/src/sync/rwmutex.go

vs fast path of sync.Mutex.Lock
http://golang.org/src/sync/mutex.go

It's also much more easier to rationale about.

[iannucci, 2015/05/27 19:33:31]

sgtm, done

+	fun  goon.KindNameResolver
+}
+
+func newKnrKeeper(fun goon.KindNameResolver) *knrKeeper {

[iannucci, 2015/05/27 19:33:31]

also removed, now embedding non-pointer

+	if fun == nil {
+		fun = goon.DefaultKindName
+	}
+	return &knrKeeper{fun: fun}
+}
+
+func (k *knrKeeper) KindNameResolver() goon.KindNameResolver {
+	k.lock.RLock()
+	defer k.lock.RUnlock()
+	return k.fun
+}
+
+func (k *knrKeeper) SetKindNameResolver(knr goon.KindNameResolver) {
+	k.lock.Lock()
+	defer k.lock.Unlock()
+	if knr == nil {
+		knr = goon.DefaultKindName
+	}
+	k.fun = knr
+}
+
+//////////////////////////////// dataStoreData /////////////////////////////////
+
+type dataStoreData struct {
+	*wrapper.BrokenFeatures
+	*knrKeeper
+
+	sync.RWMutex

[M-A Ruel, 2015/05/25 18:21:09]

You are sure you want to expose RLock and friends?

[iannucci, 2015/05/27 19:33:31]

yeah maybe not. un-embedded.

+	store *boomStore
+	snap  *boomStore
+
+	/* collections:
+	 *   ents:ns                    -> key -> value
+	 *                                 (rootkind, rootid, __entity_group__,1) -> {__version__: int}
+	 *                                 (rootkind, rootid, __entity_group_ids__,1) -> {__version__: int}
+	 *                                 (__entity_group_ids__,1) -> {__version__: int}
+	 *   idx                        -> kind,A?,[-?prop]*
+	 *   idx:ns:kind                -> key = nil
+	 *   idx:ns:kind|prop           -> propval|key = [prev val]
+	 *   idx:ns:kind|-prop          -> -propval|key = [next val]
+	 *   idx:ns:kind|A|?prop|?prop  -> A|propval|propval|key = [prev/next val]|[prev/next val]
+	 *   idx:ns:kind|?prop|?prop    -> propval|propval|key = [prev/next val]|[prev/next val]
+	 */
+}
+
+////////////////////////////// New(dataStoreData) //////////////////////////////
+
+func newDataStoreData() *dataStoreData {
+	store := newBoomStore()
+	return &dataStoreData{
+		BrokenFeatures: wrapper.NewBrokenFeatures(newDSError(pb.Error_INTERNAL_ERROR)),

[M-A Ruel, 2015/05/25 18:21:09]

By enabling support for dummy BrokenFeatures as explained on the other CL and
enabling per broken function an error, you'd remove this line entirely.

[iannucci, 2015/05/27 19:33:31]

not entirely because the default error is still important.

[M-A Ruel, 2015/05/27 20:14:47]

Yes but you don't need a function for that, simply doing:

BrokenFeatures: BrokenFeature{DefaultError: newDSError(...)},

+		knrKeeper:      newKnrKeeper(nil),
+		store:          store,
+		snap:           store.Snapshot(), // empty but better than a nil pointer.
+	}
+}
+
+func groupMetaKey(key *datastore.Key) []byte {
+	return keyBytes(noNS, newKey("", "__entity_group__", "", 1, rootKey(key)))
+}
+
+func groupIDsKey(key *datastore.Key) []byte {
+	return keyBytes(noNS, newKey("", "__entity_group_ids__", "", 1, rootKey(key)))
+}
+
+func rootIDsKey(kind string) []byte {
+	return keyBytes(noNS, newKey("", "__entity_root_ids__", kind, 0, nil))
+}
+
+func curval(ents *boomCollection, key []byte) (int64, error) {
+	var err error
+	v := ents.Get(key)
+	num := int64(0)
+	numData := &propertyList{}
+	if v != nil {
+		err = numData.UnmarshalBinary(v)

[M-A Ruel, 2015/05/25 18:21:09]

UnmarshalBinary mutates propertyList? Do not like. It's really at odd of the
general design of encoding packages in Go.

[iannucci, 2015/05/27 19:33:31]

I'm emulating the appengine sdk's behavior here (e.g.
(*PropertyList).Load(chan<- Property) ). I agree that it sucks. If I fix it for
UnmarshalBinary, I am not going to be able to fix it for Load/Save, which need
to be self mutating to work with PropertyLoaderSaver. Is the discrepancy worth
it?

[M-A Ruel, 2015/05/27 20:14:47]

No.

+		num = (*numData)[0].Value.(int64)
+	}
+	return num, err
+}
+
+func plusPlusLocked(ents *boomCollection, key []byte) (int64, error) {
+	v := ents.Get(key)
+
+	num := int64(0)
+	numData := &propertyList{}
+	if v == nil {
+		num++
+		*numData = append(*numData, datastore.Property{Name: "__version__"})
+	} else {
+		err := numData.UnmarshalBinary(v)
+		if err != nil {
+			return 0, err
+		}
+		num = (*numData)[0].Value.(int64)
+		num++
+	}
+	(*numData)[0].Value = num
+	incData, err := numData.MarshalBinary()
+	if err != nil {
+		return 0, err
+	}
+	ents.Set(key, incData)
+
+	return num, nil
+}
+
+func (d *dataStoreData) entsKeyLocked(key *datastore.Key) (*boomCollection, *datastore.Key, error) {
+	coll := "ents:" + key.Namespace()
+	ents := d.store.GetCollection(coll)
+	if ents == nil {
+		ents = d.store.SetCollection(coll, nil)
+	}
+
+	if key.Incomplete() {
+		var idKey []byte
+		if key.Parent() == nil {
+			idKey = rootIDsKey(key.Kind())
+		} else {
+			idKey = groupIDsKey(key)
+		}
+
+		id, err := plusPlusLocked(ents, idKey)
+		if err != nil {
+			return nil, nil, err
+		}
+		key = newKey(key.Namespace(), key.Kind(), "", id, key.Parent())
+	}
+
+	return ents, key, nil
+}
+
+func putPrelim(ns string, knr goon.KindNameResolver, src interface{}) (key *datastore.Key, data *propertyList, err error) {

[M-A Ruel, 2015/05/25 18:21:09]

I'd prefer not using named return values here for consistency with the rest.

[iannucci, 2015/05/27 19:33:31]

done

+	key = newKeyObj(ns, knr, src)
+	if !KeyCouldBeValid(ns, key, UserKeyOnly) {
+		// TODO(riannucci): different error for Put-ing to reserved Keys?
+		return nil, nil, datastore.ErrInvalidKey
+	}
+
+	data, err = toPL(src)
+	return
+}
+
+func (d *dataStoreData) put(ns string, src interface{}) (*datastore.Key, error) {
+	key, plData, err := putPrelim(ns, d.KindNameResolver(), src)
+	if err != nil {
+		return nil, err
+	}
+	key, err = d.putInner(key, plData)
+	if err != nil {
+		return nil, err
+	}
+	return key, setStructKey(src, key, d.KindNameResolver())
+}
+
+func (d *dataStoreData) putInner(key *datastore.Key, data *propertyList) (*datastore.Key, error) {
+	dataBytes, err := data.MarshalBinary()
+	if err != nil {
+		return nil, err
+	}
+
+	d.Lock()
+	defer d.Unlock()
+
+	ents, key, err := d.entsKeyLocked(key)
+	if err != nil {
+		return nil, err
+	}
+
+	_, err = plusPlusLocked(ents, groupMetaKey(key))

[M-A Ruel, 2015/05/25 18:21:09]

It's fine to group 198 & 199 on one line.

[iannucci, 2015/05/27 19:33:31]

done, am glad I know this trick now.

+	if err != nil {
+		return nil, err
+	}
+
+	old := ents.Get(keyBytes(noNS, key))
+	oldPl := (*propertyList)(nil)
+	if old != nil {
+		oldPl = &propertyList{}
+		err = oldPl.UnmarshalBinary(old)
+		if err != nil {
+			return nil, err
+		}
+	}
+	ents.Set(keyBytes(noNS, key), dataBytes)
+
+	return key, nil
+}
+
+func getInner(ns string, knr goon.KindNameResolver, dst interface{}, f func(*datastore.Key) (*boomCollection, error)) error {
+	key := newKeyObj(ns, knr, dst)
+	if !KeyValid(ns, key, AllowSpecialKeys) {
+		return datastore.ErrInvalidKey
+	}
+
+	ents, err := f(key)
+	if err != nil {
+		return err
+	}
+	if ents == nil {
+		return datastore.ErrNoSuchEntity

[M-A Ruel, 2015/05/25 18:21:09]

That's weird, I would expect f() to do it.

[iannucci, 2015/05/27 19:33:31]

renamed f to make its function clearer

+	}
+	pdata := ents.Get(keyBytes(noNS, key))
+	if pdata == nil {
+		return datastore.ErrNoSuchEntity
+	}
+	pl := &propertyList{}
+	err = pl.UnmarshalBinary(pdata)
+	if err != nil {
+		return err
+	}
+	return fromPL(pl, dst)
+}
+
+func (d *dataStoreData) get(ns string, dst interface{}) error {
+	return getInner(ns, d.KindNameResolver(), dst, func(*datastore.Key) (*boomCollection, error) {
+		d.RLock()
+		defer d.RUnlock()
+		return d.store.Snapshot().GetCollection("ents:" + ns), nil
+	})
+}
+
+func (d *dataStoreData) del(ns string, key *datastore.Key) error {
+	if !KeyValid(ns, key, UserKeyOnly) {
+		return datastore.ErrInvalidKey
+	}
+
+	keyBuf := keyBytes(noNS, key)
+
+	d.Lock()
+	defer d.Unlock()
+
+	ents := d.store.GetCollection("ents:" + ns)
+	if ents == nil {
+		return nil
+	}
+
+	_, err := plusPlusLocked(ents, groupMetaKey(key))
+	if err != nil {
+		return err
+	}
+
+	old := ents.Get(keyBuf)
+	oldPl := (*propertyList)(nil)
+	if old != nil {
+		oldPl = &propertyList{}
+		err = oldPl.UnmarshalBinary(old)

[M-A Ruel, 2015/05/25 18:21:09]

Why do you unmarshal an entity when you are about to delete it?

[iannucci, 2015/05/27 19:33:31]

oh, that's a leftover from the next CL. We load the old one so that we can do a
differential update to the indices. I'll remove here.

+		if err != nil {
+			return err
+		}
+	}
+
+	ents.Delete(keyBuf)
+	return nil
+}
+
+///////////////////////// memContextObj(dataStoreData) /////////////////////////
+
+func (d *dataStoreData) canApplyTxn(obj memContextObj) bool {
+	// TODO(riannucci): implement with Flush/FlushRevert for persistance.
+
+	txn := obj.(*txnDataStoreData)

[M-A Ruel, 2015/05/25 18:21:09]

There should be a lock to ensure no mutation happens in the meantime.

The lock could either be global (slightly slower, easy to do) or per entity
(more complex, more concurrent)

[iannucci, 2015/05/27 19:33:31]

There is a lock, it's in RunInTransaction. It locks the transactionData and then
the main datastoreData for the duration of canApplyTxt + applyTxn.

+	for rk, muts := range txn.muts {
+		if len(muts) == 0 { // read-only
+			continue
+		}
+		k, err := keyFromByteString(withNS, rk)
+		if err != nil {
+			panic(err)
+		}
+		entKey := "ents:" + k.Namespace()
+		mkey := groupMetaKey(k)
+		entsHead := d.store.GetCollection(entKey)
+		entsSnap := txn.snap.GetCollection(entKey)
+		vHead, err := curval(entsHead, mkey)
+		if err != nil {
+			panic(err)
+		}
+		vSnap, err := curval(entsSnap, mkey)
+		if err != nil {
+			panic(err)
+		}
+		if vHead != vSnap {
+			return false
+		}
+	}
+	return true
+}
+
+func (d *dataStoreData) applyTxn(r *rand.Rand, obj memContextObj) {
+	txn := obj.(*txnDataStoreData)
+	for _, muts := range txn.muts {
+		if len(muts) == 0 { // read-only
+			continue
+		}
+		for _, m := range muts {
+			var err error
+			if m.data == nil {
+				err = d.del(m.key.Namespace(), m.key)
+			} else {
+				_, err = d.putInner(m.key, m.data)
+			}
+			if err != nil {
+				panic(err)
+			}
+		}
+	}
+}
+
+func (d *dataStoreData) mkTxn(o *datastore.TransactionOptions) (memContextObj, error) {
+	return &txnDataStoreData{
+		BrokenFeatures: d.BrokenFeatures,
+		parent:         d,
+		knrKeeper:      newKnrKeeper(d.KindNameResolver()),
+		isXG:           o != nil && o.XG,
+		snap:           d.store.Snapshot(),
+		muts:           map[string][]txnMutation{},
+	}, nil
+}
+
+func (d *dataStoreData) endTxn() {}
+
+/////////////////////////////// txnDataStoreData ///////////////////////////////
+type txnMutation struct {
+	key  *datastore.Key
+	data *propertyList
+}
+
+type txnDataStoreData struct {
+	*wrapper.BrokenFeatures
+	*knrKeeper
+	sync.Mutex
+
+	parent *dataStoreData
+
+	// boolean 0 or 1, use atomic.*Int32 to access.
+	closed int32
+	isXG   bool
+
+	snap *boomStore
+
+	// string is the raw-bytes encoding of the entity root incl. namespace
+	muts map[string][]txnMutation
+	// TODO(riannucci): account for 'transaction size' limit of 10MB by summing
+	// length of encoded keys + values.
+}
+
+const xgEGLimit = 25
+
+/////////////////////// memContextObj(txnDataStoreData) ////////////////////////
+
+func (*txnDataStoreData) canApplyTxn(memContextObj) bool { return false }
+func (td *txnDataStoreData) endTxn() {
+	if atomic.LoadInt32(&td.closed) == 1 {
+		panic("cannot end transaction twice")
+	}
+	atomic.StoreInt32(&td.closed, 1)
+}
+func (*txnDataStoreData) applyTxn(*rand.Rand, memContextObj) {
+	panic("txnDataStoreData cannot apply transactions")
+}
+func (*txnDataStoreData) mkTxn(*datastore.TransactionOptions) (memContextObj, error) {
+	return nil, errors.New("datastore: nested transactions are not supported")
+}
+
+/////////////////// wrapper.BrokenFeatures(txnDataStoreData) ///////////////////
+
+func (td *txnDataStoreData) IsBroken() error {
+	// Slightly different from the SDK... datastore and taskqueue each implement
+	// this here, where in the SDK only datastore.transaction.Call does.
+	if atomic.LoadInt32(&td.closed) == 1 {
+		return errors.New("datastore: transaction context has expired")
+	}
+	return td.BrokenFeatures.IsBroken()
+}
+
+// writeMutation ensures that this transaction can support the given key/value
+// mutation.
+//
+//   if getOnly is true, don't record the actual mutation data, just ensure that
+//	   the key is in an included entity group (or add an empty entry for that
+//	   group).
+//
+//   if !getOnly && data == nil, this counts as a deletion instead of a Put.
+//
+// will return an error if we're crossing too many entity groups.

[M-A Ruel, 2015/05/25 18:21:08]

s/will return/Returns/
s/we're/the keys are/

[iannucci, 2015/05/27 19:33:31]

done

+func (td *txnDataStoreData) writeMutation(getOnly bool, key *datastore.Key, data *propertyList) error {
+	rk := string(keyBytes(withNS, rootKey(key)))
+
+	td.Lock()
+	defer td.Unlock()
+
+	if _, ok := td.muts[rk]; !ok {
+		limit := 1
+		if td.isXG {
+			limit = xgEGLimit
+		}
+		if len(td.muts)+1 > limit {
+			msg := "cross-group transaction need to be explicitly specified (xg=True)"
+			if td.isXG {
+				msg = "operating on too many entity groups in a single transaction"
+			}
+			return newDSError(pb.Error_BAD_REQUEST, msg)
+		}
+		td.muts[rk] = []txnMutation{}
+	}
+	if !getOnly {
+		td.muts[rk] = append(td.muts[rk], txnMutation{key, data})
+	}
+
+	return nil
+}
+
+func (td *txnDataStoreData) put(ns string, src interface{}) (*datastore.Key, error) {
+	key, plData, err := putPrelim(ns, td.KindNameResolver(), src)
+	if err != nil {
+		return nil, err
+	}
+
+	key, err = func(key *datastore.Key) (*datastore.Key, error) {

[M-A Ruel, 2015/05/25 18:21:09]

 func() would work, since it's in a closure.

personally I'd prefer a separate method.

[iannucci, 2015/05/27 19:33:31]

done
I don't want it to be a separate method because I don't want anything else to
call it (unless you have a trick for that?)

+		td.parent.Lock()
+		defer td.parent.Unlock()
+		_, key, err := td.parent.entsKeyLocked(key)
+		return key, err
+	}(key)
+	if err != nil {
+		return nil, err
+	}
+
+	err = td.writeMutation(false, key, plData)

[M-A Ruel, 2015/05/25 18:21:09]

45-458 fit one line

[iannucci, 2015/05/27 19:33:31]

done

+	if err != nil {
+		return nil, err
+	}
+
+	return key, setStructKey(src, key, td.KindNameResolver())
+}
+
+func (td *txnDataStoreData) get(ns string, dst interface{}) error {
+	return getInner(ns, td.KindNameResolver(), dst, func(key *datastore.Key) (*boomCollection, error) {
+		err := td.writeMutation(true, key, nil)

[M-A Ruel, 2015/05/25 18:21:09]

Fits one line

[iannucci, 2015/05/27 19:33:31]

done (I wish gofmt did this)

+		if err != nil {
+			return nil, err
+		}
+		return td.snap.GetCollection("ents:" + ns), nil
+	})
+}
+
+func (td *txnDataStoreData) del(ns string, key *datastore.Key) error {
+	if !KeyValid(ns, key, UserKeyOnly) {
+		return datastore.ErrInvalidKey
+	}
+

[M-A Ruel, 2015/05/25 18:21:09]

empty line not necessary

[iannucci, 2015/05/27 19:33:31]

done

+	return td.writeMutation(false, key, nil)
+}