From ce0754b0d30c8b41e45cccccfd948677cef77a9e Mon Sep 17 00:00:00 2001
From: Ben Johnson <benbjohnson@yahoo.com>
Date: Thu, 10 Jul 2014 14:50:21 -0600
Subject: Allow freelist overflow.

This commit is a backwards compatible change that allows the freelist to overflow the
page.count (uint16). It works by checking if the overflow will occur and marking the
page.count as 0xFFFF and setting the actual count to the first element of the freelist.

This approach was used because it's backwards compatible and it doesn't make sense to
change the data type of all page counts when only the freelist's page can overflow.

Fixes #192.
---
 bucket_test.go |  7 +++----
 freelist.go    | 35 ++++++++++++++++++++++++++---------
 2 files changed, 29 insertions(+), 13 deletions(-)

diff --git a/bucket_test.go b/bucket_test.go
index 0785753..13e6a8a 100644
--- a/bucket_test.go
+++ b/bucket_test.go
@@ -190,9 +190,8 @@ func TestBucket_Delete_Large(t *testing.T) {
 	})
 }
 
-// Deleting a very large list of keys will overflow the freelist.
-// https://github.com/boltdb/bolt/issues/192
-func TestBucket_Delete_ErrFreelistOverflow(t *testing.T) {
+// Deleting a very large list of keys will cause the freelist to use overflow.
+func TestBucket_Delete_FreelistOverflow(t *testing.T) {
 	if testing.Short() {
 		t.Skip("skipping test in short mode.")
 	}
@@ -233,7 +232,7 @@ func TestBucket_Delete_ErrFreelistOverflow(t *testing.T) {
 		})
 
 		// Check that a freelist overflow occurred.
-		assert.Equal(t, ErrFreelistOverflow, err)
+		assert.NoError(t, err)
 	})
 }
 
diff --git a/freelist.go b/freelist.go
index a297354..150e3e6 100644
--- a/freelist.go
+++ b/freelist.go
@@ -149,10 +149,23 @@ func (f *freelist) freed(pgid pgid) bool {
 
 // read initializes the freelist from a freelist page.
 func (f *freelist) read(p *page) {
-	ids := ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0:p.count]
+	// If the page.count is at the max uint16 value (64k) then it's considered
+	// an overflow and the size of the freelist is stored as the first element.
+	idx, count := 0, int(p.count)
+	if count == 0xFFFF {
+		idx = 1
+		count = int(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0])
+	}
+
+	// Copy the list of page ids from the freelist.
+	ids := ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[idx:count]
 	f.ids = make([]pgid, len(ids))
 	copy(f.ids, ids)
+
+	// Make sure they're sorted.
 	sort.Sort(pgids(f.ids))
+
+	// Rebuild the page cache.
 	f.reindex()
 }
 
@@ -163,15 +176,19 @@ func (f *freelist) write(p *page) error {
 	// Combine the old free pgids and pgids waiting on an open transaction.
 	ids := f.all()
 
-	// Make sure that the sum of all free pages is less than the max uint16 size.
-	if len(ids) >= 65565 {
-		return ErrFreelistOverflow
-	}
-
-	// Update the header and write the ids to the page.
+	// Update the header flag.
 	p.flags |= freelistPageFlag
-	p.count = uint16(len(ids))
-	copy(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[:], ids)
+
+	// The page.count can only hold up to 64k elements so if we overflow that
+	// number then we handle it by putting the size in the first element.
+	if len(ids) < 0xFFFF {
+		p.count = uint16(len(ids))
+		copy(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[:], ids)
+	} else {
+		p.count = 0xFFFF
+		((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0] = pgid(len(ids))
+		copy(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[1:], ids)
+	}
 
 	return nil
 }
-- 
cgit v1.2.3


From 88c8709cb1ad82156361352a5c2e065db4f62bd8 Mon Sep 17 00:00:00 2001
From: Ben Johnson <benbjohnson@yahoo.com>
Date: Thu, 10 Jul 2014 15:01:50 -0600
Subject: Remove ErrFreelistOverflow error.

---
 errors.go | 4 ----
 1 file changed, 4 deletions(-)

diff --git a/errors.go b/errors.go
index 5b31ba0..aa504f1 100644
--- a/errors.go
+++ b/errors.go
@@ -36,10 +36,6 @@ var (
 	// ErrTxClosed is returned when committing or rolling back a transaction
 	// that has already been committed or rolled back.
 	ErrTxClosed = errors.New("tx closed")
-
-	// ErrFreelistOverflow is returned when the total number of free pages
-	// exceeds 65,536 and the freelist cannot hold any more.
-	ErrFreelistOverflow = errors.New("freelist overflow")
 )
 
 // These errors can occur when putting or deleting a value or a bucket.
-- 
cgit v1.2.3