diff options
| -rw-r--r-- | bucket_test.go | 7 | ||||
| -rw-r--r-- | errors.go | 4 | ||||
| -rw-r--r-- | freelist.go | 35 |
3 files changed, 29 insertions, 17 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) }) } @@ -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. 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 } |