Repository: etcd-io/bbolt (language: go)

Issue:
freelist hashmap/array inconsistency on page reload
While testing the interface in #786, I've noticed a slight divergence in reload behavior between the array and freelist implementation.

Below testcase showcases the difference very well. TL;DR: we create a freelist with free page ids 5,6,8 and then we create a new one which frees the 5 through 9 in a transaction, marking the whole span as pending.

Now reloading the freelist again from the page that contains 5,6,8 will show different results:

```
func TestFreeList_reload_page_dedupe(t *testing.T) {
	var buf [4096]byte
	f := newTestFreelist()
	f.readIDs([]common.Pgid{5, 6, 8})

	p := (*common.Page)(unsafe.Pointer(&buf[0]))
	if err := f.write(p); err != nil {
		t.Fatal(err)
	}

	f2 := newTestFreelist()
	f2.free(common.Txid(5), common.NewPage(5, common.LeafPageFlag, 0, 4))
	// reload should deduplicate as a pending page when reading from p's freelist
	f2.reload(p)

	if len(f2.getFreePageIDs()) != 0 {
		t.Fatalf("expected empty; got=%v", f2.getFreePageIDs())
	}
	if exp := []common.Pgid{5, 6, 7, 8, 9}; !reflect.DeepEqual(exp, f2.pending[5].ids) {
		t.Fatalf("exp=%v; got=%v", exp, f2.pending[5].ids)
	}
}
```

The array freelist will pass and detect the span as pending, the hashmap will have the overlapping pages pending **and** free.

It stems from the fact that on init, the hashmap will not honor an empty list as an initial state (as in, it will not attempt to initialize anything):
https://github.com/etcd-io/bbolt/blob/main/freelist_hmap.go#L197-L200

Whereas the array will happily take what it's passed and reindex accordingly:
https://github.com/etcd-io/bbolt/blob/main/freelist_array.go#L60-L63




Discussion / hints:
Thanks @tjungblu for the finding. Indeed the arrary and hashmap freelist have different behavior on `readIDs/init`. The behavior of array freelist should be correct.

> f2.free(common.Txid(5), common.NewPage(5, common.LeafPageFlag, 0, 4))

freelist will panic when it tries to free an already freed page.

Fix patch:
diff --git a/internal/freelist/array.go b/internal/freelist/array.go
index 93ccc5edc..0cc1ba715 100644
--- a/internal/freelist/array.go
+++ b/internal/freelist/array.go
@@ -101,6 +101,7 @@ func (f *array) mergeSpans(ids common.Pgids) {
 func NewArrayFreelist() Interface {
 	a := &array{
 		shared: newShared(),
+		ids:    []common.Pgid{},
 	}
 	a.Interface = a
 	return a
diff --git a/internal/freelist/hashmap.go b/internal/freelist/hashmap.go
index a6bad8976..8d471f4b5 100644
--- a/internal/freelist/hashmap.go
+++ b/internal/freelist/hashmap.go
@@ -21,22 +21,22 @@ type hashMap struct {
 }
 
 func (f *hashMap) Init(pgids common.Pgids) {
+	// reset the counter when freelist init
+	f.freePagesCount = 0
+	f.freemaps = make(map[uint64]pidSet)
+	f.forwardMap = make(map[common.Pgid]uint64)
+	f.backwardMap = make(map[common.Pgid]uint64)
+
 	if len(pgids) == 0 {
 		return
 	}
 
-	size := uint64(1)
-	start := pgids[0]
-	// reset the counter when freelist init
-	f.freePagesCount = 0
-
 	if !sort.SliceIsSorted([]common.Pgid(pgids), func(i, j int) bool { return pgids[i] < pgids[j] }) {
 		panic("pgids not sorted")
 	}
 
-	f.freemaps = make(map[uint64]pidSet)
-	f.forwardMap = make(map[common.Pgid]uint64)
-	f.backwardMap = make(map[common.Pgid]uint64)
+	size := uint64(1)
+	start := pgids[0]
 
 	for i := 1; i < len(pgids); i++ {
 		// continuous page
@@ -117,7 +117,7 @@ func (f *hashMap) FreeCount() int {
 func (f *hashMap) freePageIds() common.Pgids {
 	count := f.FreeCount()
 	if count == 0 {
-		return nil
+		return common.Pgids{}
 	}
 
 	m := make([]common.Pgid, 0, count)
diff --git a/internal/freelist/shared.go b/internal/freelist/shared.go
index ac06309df..ba405239c 100644
--- a/internal/freelist/shared.go
+++ b/internal/freelist/shared.go
@@ -167,7 +167,7 @@ func (t *shared) releaseRange(begin, end common.Txid) {
 	if begin > end {
 		return
 	}
-	var m common.Pgids
+	m := common.Pgids{}
 	for tid, txp := range t.pending {
 		if tid < begin || tid > end {
 			continue


Test patch:
diff --git a/internal/freelist/freelist_test.go b/internal/freelist/freelist_test.go
index df7c7697e..181e0932e 100644
--- a/internal/freelist/freelist_test.go
+++ b/internal/freelist/freelist_test.go
@@ -8,6 +8,8 @@ import (
 	"testing"
 	"unsafe"
 
+	"github.com/stretchr/testify/require"
+
 	"go.etcd.io/bbolt/internal/common"
 )
 
@@ -85,7 +87,7 @@ func TestFreelist_releaseRange(t *testing.T) {
 			title:         "Single pending outsize minimum end range",
 			pagesIn:       []testPage{{id: 3, n: 1, allocTxn: 100, freeTxn: 200}},
 			releaseRanges: []testRange{{1, 199}},
-			wantFree:      nil,
+			wantFree:      []common.Pgid{},
 		},
 		{
 			title:         "Single pending with minimum begin range",
@@ -97,7 +99,7 @@ func TestFreelist_releaseRange(t *testing.T) {
 			title:         "Single pending outside minimum begin range",
 			pagesIn:       []testPage{{id: 3, n: 1, allocTxn: 100, freeTxn: 200}},
 			releaseRanges: []testRange{{101, 300}},
-			wantFree:      nil,
+			wantFree:      []common.Pgid{},
 		},
 		{
 			title:         "Single pending in minimum range",
@@ -109,7 +111,7 @@ func TestFreelist_releaseRange(t *testing.T) {
 			title:         "Single pending and read transaction at 199",
 			pagesIn:       []testPage{{id: 3, n: 1, allocTxn: 199, freeTxn: 200}},
 			releaseRanges: []testRange{{100, 198}, {200, 300}},
-			wantFree:      nil,
+			wantFree:      []common.Pgid{},
 		},
 		{
 			title: "Adjacent pending and read transactions at 199, 200",
@@ -122,7 +124,7 @@ func TestFreelist_releaseRange(t *testing.T) {
 				{200, 199}, // Simulate the ranges db.freePages might produce.
 				{201, 300},
 			},
-			wantFree: nil,
+			wantFree: []common.Pgid{},
 		},
 		{
 			title: "Out of order ranges",
@@ -135,7 +137,7 @@ func TestFreelist_releaseRange(t *testing.T) {
 				{201, 200},
 				{200, 200},
 			},
-			wantFree: nil,
+			wantFree: []common.Pgid{},
 		},
 		{
 			title: "Multiple pending, read transaction at 150",
@@ -153,32 +155,71 @@ func TestFreelist_releaseRange(t *testing.T) {
 	}
 
 	for _, c := range releaseRangeTests {
-		f := newTestFreelist()
-		var ids []common.Pgid
-		for _, p := range c.pagesIn {
-			for i := uint64(0); i < uint64(p.n); i++ {
-				ids = append(ids, common.Pgid(uint64(p.id)+i))
+		t.Run(c.title, func(t *testing.T) {
+			f := newTestFreelist()
+			var ids []common.Pgid
+			for _, p := range c.pagesIn {
+				for i := uint64(0); i < uint64(p.n); i++ {
+					ids = append(ids, common.Pgid(uint64(p.id)+i))
+				}
+			}
+			f.Init(ids)
+			for _, p := range c.pagesIn {
+				f.Allocate(p.allocTxn, p.n)
 			}
-		}
-		f.Init(ids)
-		for _, p := range c.pagesIn {
-			f.Allocate(p.allocTxn, p.n)
-		}
 
-		for _, p := range c.pagesIn {
-			f.Free(p.freeTxn, common.NewPage(p.id, 0, 0, uint32(p.n-1)))
-		}
+			for _, p := range c.pagesIn {
+				f.Free(p.freeTxn, common.NewPage(p.id, 0, 0, uint32(p.n-1)))
+			}
 
-		for _, r := range c.releaseRanges {
-			f.releaseRange(r.begin, r.end)
-		}
+			for _, r := range c.releaseRanges {
+				f.releaseRange(r.begin, r.end)
+			}
 
-		if exp := common.Pgids(c.wantFree); !reflect.DeepEqual(exp, f.freePageIds()) {
-			t.Errorf("exp=%v; got=%v for %s", exp, f.freePageIds(), c.title)
-		}
+			require.Equal(t, common.Pgids(c.wantFree), f.freePageIds())
+		})
 	}
 }
 
+func TestFreeList_init(t *testing.T) {
+	buf := make([]byte, 4096)
+	f := newTestFreelist()
+	f.Init(common.Pgids{5, 6, 8})
+
+	p := common.LoadPage(buf)
+	f.Write(p)
+
+	f2 := newTestFreelist()
+	f2.Read(p)
+	require.Equal(t, common.Pgids{5, 6, 8}, f2.freePageIds())
+
+	// When initializing the freelist with an empty list of page ID,
+	// it should reset the freelist page IDs.
+	f2.Init([]common.Pgid{})
+	require.Equal(t, common.Pgids{}, f2.freePageIds())
+}
+
+func TestFreeList_reload(t *testing.T) {
+	buf := make([]byte, 4096)
+	f := newTestFreelist()
+	f.Init(common.Pgids{5, 6, 8})
+
+	p := common.LoadPage(buf)
+	f.Write(p)
+
+	f2 := newTestFreelist()
+	f2.Read(p)
+	require.Equal(t, common.Pgids{5, 6, 8}, f2.freePageIds())
+
+	f2.Free(common.Txid(5), common.NewPage(10, common.LeafPageFlag, 0, 2))
+
+	// reload shouldn't affect the pending list
+	f2.Reload(p)
+
+	require.Equal(t, common.Pgids{5, 6, 8}, f2.freePageIds())
+	require.Equal(t, []common.Pgid{10, 11, 12}, f2.pendingPageIds()[5].ids)
+}
+
 // Ensure that a freelist can deserialize from a freelist page.
 func TestFreelist_read(t *testing.T) {
 	// Create a page.
@@ -263,7 +304,7 @@ func Test_freelist_ReadIDs_and_getFreePageIDs(t *testing.T) {
 	}
 
 	f2 := newTestFreelist()
-	var exp2 []common.Pgid
+	exp2 := []common.Pgid{}
 	f2.Init(exp2)
 
 	if got2 := f2.freePageIds(); !reflect.DeepEqual(got2, common.Pgids(exp2)) {