aboutsummaryrefslogtreecommitdiffstats
path: root/trie/trie_test.go
diff options
context:
space:
mode:
authorFelix Lange <fjl@twurst.com>2016-10-17 22:13:50 +0800
committerFelix Lange <fjl@twurst.com>2016-10-18 10:57:47 +0800
commit177cab5fe70910ee0af3fcf493d51999ae2d923d (patch)
tree54a8c78b9e2a25880b1d9cc284affad7d0830d33 /trie/trie_test.go
parent187d6a66a5176a1dc3e75d5ad4baad623762acb9 (diff)
downloaddexon-177cab5fe70910ee0af3fcf493d51999ae2d923d.tar
dexon-177cab5fe70910ee0af3fcf493d51999ae2d923d.tar.gz
dexon-177cab5fe70910ee0af3fcf493d51999ae2d923d.tar.bz2
dexon-177cab5fe70910ee0af3fcf493d51999ae2d923d.tar.lz
dexon-177cab5fe70910ee0af3fcf493d51999ae2d923d.tar.xz
dexon-177cab5fe70910ee0af3fcf493d51999ae2d923d.tar.zst
dexon-177cab5fe70910ee0af3fcf493d51999ae2d923d.zip
trie: ensure resolved nodes stay loaded
Commit 40cdcf1183 broke the optimisation which kept nodes resolved during Get in the trie. The decoder assigned cache generation 0 unconditionally, causing resolved nodes to get flushed on Commit. This commit fixes it and adds two tests.
Diffstat (limited to 'trie/trie_test.go')
-rw-r--r--trie/trie_test.go91
1 files changed, 70 insertions, 21 deletions
diff --git a/trie/trie_test.go b/trie/trie_test.go
index 32fbe6801..da0d2360b 100644
--- a/trie/trie_test.go
+++ b/trie/trie_test.go
@@ -300,25 +300,6 @@ func TestReplication(t *testing.T) {
}
}
-// Not an actual test
-func TestOutput(t *testing.T) {
- t.Skip()
-
- base := "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
- trie := newEmpty()
- for i := 0; i < 50; i++ {
- updateString(trie, fmt.Sprintf("%s%d", base, i), "valueeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee")
- }
- fmt.Println("############################## FULL ################################")
- fmt.Println(trie.root)
-
- trie.Commit()
- fmt.Println("############################## SMALL ################################")
- trie2, _ := New(trie.Hash(), trie.db)
- getString(trie2, base+"20")
- fmt.Println(trie2.root)
-}
-
func TestLargeValue(t *testing.T) {
trie := newEmpty()
trie.Update([]byte("key1"), []byte{99, 99, 99, 99})
@@ -326,14 +307,56 @@ func TestLargeValue(t *testing.T) {
trie.Hash()
}
+type countingDB struct {
+ Database
+ gets map[string]int
+}
+
+func (db *countingDB) Get(key []byte) ([]byte, error) {
+ db.gets[string(key)]++
+ return db.Database.Get(key)
+}
+
+// TestCacheUnload checks that decoded nodes are unloaded after a
+// certain number of commit operations.
+func TestCacheUnload(t *testing.T) {
+ // Create test trie with two branches.
+ trie := newEmpty()
+ key1 := "---------------------------------"
+ key2 := "---some other branch"
+ updateString(trie, key1, "this is the branch of key1.")
+ updateString(trie, key2, "this is the branch of key2.")
+ root, _ := trie.Commit()
+
+ // Commit the trie repeatedly and access key1.
+ // The branch containing it is loaded from DB exactly two times:
+ // in the 0th and 6th iteration.
+ db := &countingDB{Database: trie.db, gets: make(map[string]int)}
+ trie, _ = New(root, db)
+ trie.SetCacheLimit(5)
+ for i := 0; i < 12; i++ {
+ getString(trie, key1)
+ trie.Commit()
+ }
+
+ // Check that it got loaded two times.
+ for dbkey, count := range db.gets {
+ if count != 2 {
+ t.Errorf("db key %x loaded %d times, want %d times", []byte(dbkey), count, 2)
+ }
+ }
+}
+
+// randTest performs random trie operations.
+// Instances of this test are created by Generate.
+type randTest []randTestStep
+
type randTestStep struct {
op int
key []byte // for opUpdate, opDelete, opGet
value []byte // for opUpdate
}
-type randTest []randTestStep
-
const (
opUpdate = iota
opDelete
@@ -342,6 +365,7 @@ const (
opHash
opReset
opItercheckhash
+ opCheckCacheInvariant
opMax // boundary value, not an actual op
)
@@ -437,7 +461,32 @@ func runRandTest(rt randTest) bool {
fmt.Println("hashes not equal")
return false
}
+ case opCheckCacheInvariant:
+ return checkCacheInvariant(tr.root, tr.cachegen, 0)
+ }
+ }
+ return true
+}
+
+func checkCacheInvariant(n node, parentCachegen uint16, depth int) bool {
+ switch n := n.(type) {
+ case *shortNode:
+ if n.flags.gen > parentCachegen {
+ fmt.Printf("cache invariant violation: %d > %d\nat depth %d node %s", n.flags.gen, parentCachegen, depth, spew.Sdump(n))
+ return false
+ }
+ return checkCacheInvariant(n.Val, n.flags.gen, depth+1)
+ case *fullNode:
+ if n.flags.gen > parentCachegen {
+ fmt.Printf("cache invariant violation: %d > %d\nat depth %d node %s", n.flags.gen, parentCachegen, depth, spew.Sdump(n))
+ return false
+ }
+ for _, child := range n.Children {
+ if !checkCacheInvariant(child, n.flags.gen, depth+1) {
+ return false
+ }
}
+ return true
}
return true
}