Optimize Tx.Check().

This commit removes several memory allocations occurring on every page and also caches the freelist map used when iterating over the pages. This results in significantly better performance.

3 files changed, 15 insertions, 14 deletions

diff --git a/cmd/bolt/check.go b/cmd/bolt/check.go
index 1466fd7..7555ec8 100644
--- a/cmd/bolt/check.go
+++ b/cmd/bolt/check.go
@@ -38,7 +38,7 @@ func Check(path string) {
 
 		// Print summary of errors.
 		if count > 0 {
-			fatalf("%d errors found")
+			fatalf("%d errors found", count)
 		} else {
 			println("OK")
 		}
diff --git a/cmd/bolt/main.go b/cmd/bolt/main.go
index 44ba5a1..a79302d 100644
--- a/cmd/bolt/main.go
+++ b/cmd/bolt/main.go
@@ -10,11 +10,13 @@ import (
 
 	"github.com/boltdb/bolt"
 	"github.com/codegangsta/cli"
+	// "github.com/davecheney/profile"
 )
 
 var branch, commit string
 
 func main() {
+	// defer profile.Start(&profile.Config{CPUProfile: true, MemProfile: true}).Stop()
 	log.SetFlags(0)
 	NewApp().Run(os.Args)
 }
diff --git a/tx.go b/tx.go
index 6ebe04e..0074a60 100644
--- a/tx.go
+++ b/tx.go
@@ -316,15 +316,13 @@ func (tx *Tx) check(ch chan error) {
 	}
 
 	// Recursively check buckets.
-	tx.checkBucket(&tx.root, reachable, ch)
+	tx.checkBucket(&tx.root, reachable, freed, ch)
 
 	// Ensure all pages below high water mark are either reachable or freed.
 	for i := pgid(0); i < tx.meta.pgid; i++ {
 		_, isReachable := reachable[i]
 		if !isReachable && !freed[i] {
 			ch <- fmt.Errorf("page %d: unreachable unfreed", int(i))
-		} else if isReachable && freed[i] {
-			ch <- fmt.Errorf("page %d: reachable freed", int(i))
 		}
 	}
 
@@ -332,7 +330,7 @@ func (tx *Tx) check(ch chan error) {
 	close(ch)
 }
 
-func (tx *Tx) checkBucket(b *Bucket, reachable map[pgid]*page, ch chan error) {
+func (tx *Tx) checkBucket(b *Bucket, reachable map[pgid]*page, freed map[pgid]bool, ch chan error) {
 	// Ignore inline buckets.
 	if b.root == 0 {
 		return
@@ -340,6 +338,10 @@ func (tx *Tx) checkBucket(b *Bucket, reachable map[pgid]*page, ch chan error) {
 
 	// Check every page used by this bucket.
 	b.tx.forEachPage(b.root, 0, func(p *page, _ int) {
+		if p.id > tx.meta.pgid {
+			ch <- fmt.Errorf("page %d: out of bounds: %d", int(p.id), int(b.tx.meta.pgid))
+		}
+
 		// Ensure each page is only referenced once.
 		for i := pgid(0); i <= pgid(p.overflow); i++ {
 			var id = p.id + i
@@ -349,21 +351,18 @@ func (tx *Tx) checkBucket(b *Bucket, reachable map[pgid]*page, ch chan error) {
 			reachable[id] = p
 		}
 
-		// Retrieve page info.
-		info, err := b.tx.Page(int(p.id))
-		if err != nil {
-			ch <- err
-		} else if info == nil {
-			ch <- fmt.Errorf("page %d: out of bounds: %d", int(p.id), int(b.tx.meta.pgid))
-		} else if info.Type != "branch" && info.Type != "leaf" {
-			ch <- fmt.Errorf("page %d: invalid type: %s", int(p.id), info.Type)
+		// We should only encounter un-freed leaf and branch pages.
+		if freed[p.id] {
+			ch <- fmt.Errorf("page %d: reachable freed", int(p.id))
+		} else if (p.flags&branchPageFlag) == 0 && (p.flags&leafPageFlag) == 0 {
+			ch <- fmt.Errorf("page %d: invalid type: %s", int(p.id), p.typ())
 		}
 	})
 
 	// Check each bucket within this bucket.
 	_ = b.ForEach(func(k, v []byte) error {
 		if child := b.Bucket(k); child != nil {
-			tx.checkBucket(child, reachable, ch)
+			tx.checkBucket(child, reachable, freed, ch)
 		}
 		return nil
 	})