freelist hashmap/array inconsistency on page reload

[tjungblu]

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

[ahrtr]

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.