Source file src/go.etcd.io/bbolt/freelist_test.go

Documentation: go.etcd.io/bbolt

     1  package bbolt
     2  
     3  import (
     4  	"math/rand"
     5  	"os"
     6  	"reflect"
     7  	"sort"
     8  	"testing"
     9  	"unsafe"
    10  )
    11  
    12  // TestFreelistType is used as a env variable for test to indicate the backend type
    13  const TestFreelistType = "TEST_FREELIST_TYPE"
    14  
    15  // Ensure that a page is added to a transaction's freelist.
    16  func TestFreelist_free(t *testing.T) {
    17  	f := newTestFreelist()
    18  	f.free(100, &page{id: 12})
    19  	if !reflect.DeepEqual([]pgid{12}, f.pending[100].ids) {
    20  		t.Fatalf("exp=%v; got=%v", []pgid{12}, f.pending[100].ids)
    21  	}
    22  }
    23  
    24  // Ensure that a page and its overflow is added to a transaction's freelist.
    25  func TestFreelist_free_overflow(t *testing.T) {
    26  	f := newTestFreelist()
    27  	f.free(100, &page{id: 12, overflow: 3})
    28  	if exp := []pgid{12, 13, 14, 15}; !reflect.DeepEqual(exp, f.pending[100].ids) {
    29  		t.Fatalf("exp=%v; got=%v", exp, f.pending[100].ids)
    30  	}
    31  }
    32  
    33  // Ensure that a transaction's free pages can be released.
    34  func TestFreelist_release(t *testing.T) {
    35  	f := newTestFreelist()
    36  	f.free(100, &page{id: 12, overflow: 1})
    37  	f.free(100, &page{id: 9})
    38  	f.free(102, &page{id: 39})
    39  	f.release(100)
    40  	f.release(101)
    41  	if exp := []pgid{9, 12, 13}; !reflect.DeepEqual(exp, f.getFreePageIDs()) {
    42  		t.Fatalf("exp=%v; got=%v", exp, f.getFreePageIDs())
    43  	}
    44  
    45  	f.release(102)
    46  	if exp := []pgid{9, 12, 13, 39}; !reflect.DeepEqual(exp, f.getFreePageIDs()) {
    47  		t.Fatalf("exp=%v; got=%v", exp, f.getFreePageIDs())
    48  	}
    49  }
    50  
    51  // Ensure that releaseRange handles boundary conditions correctly
    52  func TestFreelist_releaseRange(t *testing.T) {
    53  	type testRange struct {
    54  		begin, end txid
    55  	}
    56  
    57  	type testPage struct {
    58  		id       pgid
    59  		n        int
    60  		allocTxn txid
    61  		freeTxn  txid
    62  	}
    63  
    64  	var releaseRangeTests = []struct {
    65  		title         string
    66  		pagesIn       []testPage
    67  		releaseRanges []testRange
    68  		wantFree      []pgid
    69  	}{
    70  		{
    71  			title:         "Single pending in range",
    72  			pagesIn:       []testPage{{id: 3, n: 1, allocTxn: 100, freeTxn: 200}},
    73  			releaseRanges: []testRange{{1, 300}},
    74  			wantFree:      []pgid{3},
    75  		},
    76  		{
    77  			title:         "Single pending with minimum end range",
    78  			pagesIn:       []testPage{{id: 3, n: 1, allocTxn: 100, freeTxn: 200}},
    79  			releaseRanges: []testRange{{1, 200}},
    80  			wantFree:      []pgid{3},
    81  		},
    82  		{
    83  			title:         "Single pending outsize minimum end range",
    84  			pagesIn:       []testPage{{id: 3, n: 1, allocTxn: 100, freeTxn: 200}},
    85  			releaseRanges: []testRange{{1, 199}},
    86  			wantFree:      nil,
    87  		},
    88  		{
    89  			title:         "Single pending with minimum begin range",
    90  			pagesIn:       []testPage{{id: 3, n: 1, allocTxn: 100, freeTxn: 200}},
    91  			releaseRanges: []testRange{{100, 300}},
    92  			wantFree:      []pgid{3},
    93  		},
    94  		{
    95  			title:         "Single pending outside minimum begin range",
    96  			pagesIn:       []testPage{{id: 3, n: 1, allocTxn: 100, freeTxn: 200}},
    97  			releaseRanges: []testRange{{101, 300}},
    98  			wantFree:      nil,
    99  		},
   100  		{
   101  			title:         "Single pending in minimum range",
   102  			pagesIn:       []testPage{{id: 3, n: 1, allocTxn: 199, freeTxn: 200}},
   103  			releaseRanges: []testRange{{199, 200}},
   104  			wantFree:      []pgid{3},
   105  		},
   106  		{
   107  			title:         "Single pending and read transaction at 199",
   108  			pagesIn:       []testPage{{id: 3, n: 1, allocTxn: 199, freeTxn: 200}},
   109  			releaseRanges: []testRange{{100, 198}, {200, 300}},
   110  			wantFree:      nil,
   111  		},
   112  		{
   113  			title: "Adjacent pending and read transactions at 199, 200",
   114  			pagesIn: []testPage{
   115  				{id: 3, n: 1, allocTxn: 199, freeTxn: 200},
   116  				{id: 4, n: 1, allocTxn: 200, freeTxn: 201},
   117  			},
   118  			releaseRanges: []testRange{
   119  				{100, 198},
   120  				{200, 199}, // Simulate the ranges db.freePages might produce.
   121  				{201, 300},
   122  			},
   123  			wantFree: nil,
   124  		},
   125  		{
   126  			title: "Out of order ranges",
   127  			pagesIn: []testPage{
   128  				{id: 3, n: 1, allocTxn: 199, freeTxn: 200},
   129  				{id: 4, n: 1, allocTxn: 200, freeTxn: 201},
   130  			},
   131  			releaseRanges: []testRange{
   132  				{201, 199},
   133  				{201, 200},
   134  				{200, 200},
   135  			},
   136  			wantFree: nil,
   137  		},
   138  		{
   139  			title: "Multiple pending, read transaction at 150",
   140  			pagesIn: []testPage{
   141  				{id: 3, n: 1, allocTxn: 100, freeTxn: 200},
   142  				{id: 4, n: 1, allocTxn: 100, freeTxn: 125},
   143  				{id: 5, n: 1, allocTxn: 125, freeTxn: 150},
   144  				{id: 6, n: 1, allocTxn: 125, freeTxn: 175},
   145  				{id: 7, n: 2, allocTxn: 150, freeTxn: 175},
   146  				{id: 9, n: 2, allocTxn: 175, freeTxn: 200},
   147  			},
   148  			releaseRanges: []testRange{{50, 149}, {151, 300}},
   149  			wantFree:      []pgid{4, 9, 10},
   150  		},
   151  	}
   152  
   153  	for _, c := range releaseRangeTests {
   154  		f := newTestFreelist()
   155  		var ids []pgid
   156  		for _, p := range c.pagesIn {
   157  			for i := uint64(0); i < uint64(p.n); i++ {
   158  				ids = append(ids, pgid(uint64(p.id)+i))
   159  			}
   160  		}
   161  		f.readIDs(ids)
   162  		for _, p := range c.pagesIn {
   163  			f.allocate(p.allocTxn, p.n)
   164  		}
   165  
   166  		for _, p := range c.pagesIn {
   167  			f.free(p.freeTxn, &page{id: p.id, overflow: uint32(p.n - 1)})
   168  		}
   169  
   170  		for _, r := range c.releaseRanges {
   171  			f.releaseRange(r.begin, r.end)
   172  		}
   173  
   174  		if exp := c.wantFree; !reflect.DeepEqual(exp, f.getFreePageIDs()) {
   175  			t.Errorf("exp=%v; got=%v for %s", exp, f.getFreePageIDs(), c.title)
   176  		}
   177  	}
   178  }
   179  
   180  func TestFreelistHashmap_allocate(t *testing.T) {
   181  	f := newTestFreelist()
   182  	if f.freelistType != FreelistMapType {
   183  		t.Skip()
   184  	}
   185  
   186  	ids := []pgid{3, 4, 5, 6, 7, 9, 12, 13, 18}
   187  	f.readIDs(ids)
   188  
   189  	f.allocate(1, 3)
   190  	if x := f.free_count(); x != 6 {
   191  		t.Fatalf("exp=6; got=%v", x)
   192  	}
   193  
   194  	f.allocate(1, 2)
   195  	if x := f.free_count(); x != 4 {
   196  		t.Fatalf("exp=4; got=%v", x)
   197  	}
   198  	f.allocate(1, 1)
   199  	if x := f.free_count(); x != 3 {
   200  		t.Fatalf("exp=3; got=%v", x)
   201  	}
   202  
   203  	f.allocate(1, 0)
   204  	if x := f.free_count(); x != 3 {
   205  		t.Fatalf("exp=3; got=%v", x)
   206  	}
   207  }
   208  
   209  // Ensure that a freelist can find contiguous blocks of pages.
   210  func TestFreelistArray_allocate(t *testing.T) {
   211  	f := newTestFreelist()
   212  	if f.freelistType != FreelistArrayType {
   213  		t.Skip()
   214  	}
   215  	ids := []pgid{3, 4, 5, 6, 7, 9, 12, 13, 18}
   216  	f.readIDs(ids)
   217  	if id := int(f.allocate(1, 3)); id != 3 {
   218  		t.Fatalf("exp=3; got=%v", id)
   219  	}
   220  	if id := int(f.allocate(1, 1)); id != 6 {
   221  		t.Fatalf("exp=6; got=%v", id)
   222  	}
   223  	if id := int(f.allocate(1, 3)); id != 0 {
   224  		t.Fatalf("exp=0; got=%v", id)
   225  	}
   226  	if id := int(f.allocate(1, 2)); id != 12 {
   227  		t.Fatalf("exp=12; got=%v", id)
   228  	}
   229  	if id := int(f.allocate(1, 1)); id != 7 {
   230  		t.Fatalf("exp=7; got=%v", id)
   231  	}
   232  	if id := int(f.allocate(1, 0)); id != 0 {
   233  		t.Fatalf("exp=0; got=%v", id)
   234  	}
   235  	if id := int(f.allocate(1, 0)); id != 0 {
   236  		t.Fatalf("exp=0; got=%v", id)
   237  	}
   238  	if exp := []pgid{9, 18}; !reflect.DeepEqual(exp, f.getFreePageIDs()) {
   239  		t.Fatalf("exp=%v; got=%v", exp, f.getFreePageIDs())
   240  	}
   241  
   242  	if id := int(f.allocate(1, 1)); id != 9 {
   243  		t.Fatalf("exp=9; got=%v", id)
   244  	}
   245  	if id := int(f.allocate(1, 1)); id != 18 {
   246  		t.Fatalf("exp=18; got=%v", id)
   247  	}
   248  	if id := int(f.allocate(1, 1)); id != 0 {
   249  		t.Fatalf("exp=0; got=%v", id)
   250  	}
   251  	if exp := []pgid{}; !reflect.DeepEqual(exp, f.getFreePageIDs()) {
   252  		t.Fatalf("exp=%v; got=%v", exp, f.getFreePageIDs())
   253  	}
   254  }
   255  
   256  // Ensure that a freelist can deserialize from a freelist page.
   257  func TestFreelist_read(t *testing.T) {
   258  	// Create a page.
   259  	var buf [4096]byte
   260  	page := (*page)(unsafe.Pointer(&buf[0]))
   261  	page.flags = freelistPageFlag
   262  	page.count = 2
   263  
   264  	// Insert 2 page ids.
   265  	ids := (*[3]pgid)(unsafe.Pointer(uintptr(unsafe.Pointer(page)) + unsafe.Sizeof(*page)))
   266  	ids[0] = 23
   267  	ids[1] = 50
   268  
   269  	// Deserialize page into a freelist.
   270  	f := newTestFreelist()
   271  	f.read(page)
   272  
   273  	// Ensure that there are two page ids in the freelist.
   274  	if exp := []pgid{23, 50}; !reflect.DeepEqual(exp, f.getFreePageIDs()) {
   275  		t.Fatalf("exp=%v; got=%v", exp, f.getFreePageIDs())
   276  	}
   277  }
   278  
   279  // Ensure that a freelist can serialize into a freelist page.
   280  func TestFreelist_write(t *testing.T) {
   281  	// Create a freelist and write it to a page.
   282  	var buf [4096]byte
   283  	f := newTestFreelist()
   284  
   285  	f.readIDs([]pgid{12, 39})
   286  	f.pending[100] = &txPending{ids: []pgid{28, 11}}
   287  	f.pending[101] = &txPending{ids: []pgid{3}}
   288  	p := (*page)(unsafe.Pointer(&buf[0]))
   289  	if err := f.write(p); err != nil {
   290  		t.Fatal(err)
   291  	}
   292  
   293  	// Read the page back out.
   294  	f2 := newTestFreelist()
   295  	f2.read(p)
   296  
   297  	// Ensure that the freelist is correct.
   298  	// All pages should be present and in reverse order.
   299  	if exp := []pgid{3, 11, 12, 28, 39}; !reflect.DeepEqual(exp, f2.getFreePageIDs()) {
   300  		t.Fatalf("exp=%v; got=%v", exp, f2.getFreePageIDs())
   301  	}
   302  }
   303  
   304  func Benchmark_FreelistRelease10K(b *testing.B)    { benchmark_FreelistRelease(b, 10000) }
   305  func Benchmark_FreelistRelease100K(b *testing.B)   { benchmark_FreelistRelease(b, 100000) }
   306  func Benchmark_FreelistRelease1000K(b *testing.B)  { benchmark_FreelistRelease(b, 1000000) }
   307  func Benchmark_FreelistRelease10000K(b *testing.B) { benchmark_FreelistRelease(b, 10000000) }
   308  
   309  func benchmark_FreelistRelease(b *testing.B, size int) {
   310  	ids := randomPgids(size)
   311  	pending := randomPgids(len(ids) / 400)
   312  	b.ResetTimer()
   313  	for i := 0; i < b.N; i++ {
   314  		txp := &txPending{ids: pending}
   315  		f := newTestFreelist()
   316  		f.pending = map[txid]*txPending{1: txp}
   317  		f.readIDs(ids)
   318  		f.release(1)
   319  	}
   320  }
   321  
   322  func randomPgids(n int) []pgid {
   323  	rand.Seed(42)
   324  	pgids := make(pgids, n)
   325  	for i := range pgids {
   326  		pgids[i] = pgid(rand.Int63())
   327  	}
   328  	sort.Sort(pgids)
   329  	return pgids
   330  }
   331  
   332  func Test_freelist_ReadIDs_and_getFreePageIDs(t *testing.T) {
   333  	f := newTestFreelist()
   334  	exp := []pgid{3, 4, 5, 6, 7, 9, 12, 13, 18}
   335  
   336  	f.readIDs(exp)
   337  
   338  	if got := f.getFreePageIDs(); !reflect.DeepEqual(exp, got) {
   339  		t.Fatalf("exp=%v; got=%v", exp, got)
   340  	}
   341  
   342  	f2 := newTestFreelist()
   343  	var exp2 []pgid
   344  	f2.readIDs(exp2)
   345  
   346  	if got2 := f2.getFreePageIDs(); !reflect.DeepEqual(got2, exp2) {
   347  		t.Fatalf("exp2=%#v; got2=%#v", exp2, got2)
   348  	}
   349  
   350  }
   351  
   352  func Test_freelist_mergeWithExist(t *testing.T) {
   353  	bm1 := pidSet{1: struct{}{}}
   354  
   355  	bm2 := pidSet{5: struct{}{}}
   356  	tests := []struct {
   357  		name            string
   358  		ids             []pgid
   359  		pgid            pgid
   360  		want            []pgid
   361  		wantForwardmap  map[pgid]uint64
   362  		wantBackwardmap map[pgid]uint64
   363  		wantfreemap     map[uint64]pidSet
   364  	}{
   365  		{
   366  			name:            "test1",
   367  			ids:             []pgid{1, 2, 4, 5, 6},
   368  			pgid:            3,
   369  			want:            []pgid{1, 2, 3, 4, 5, 6},
   370  			wantForwardmap:  map[pgid]uint64{1: 6},
   371  			wantBackwardmap: map[pgid]uint64{6: 6},
   372  			wantfreemap:     map[uint64]pidSet{6: bm1},
   373  		},
   374  		{
   375  			name:            "test2",
   376  			ids:             []pgid{1, 2, 5, 6},
   377  			pgid:            3,
   378  			want:            []pgid{1, 2, 3, 5, 6},
   379  			wantForwardmap:  map[pgid]uint64{1: 3, 5: 2},
   380  			wantBackwardmap: map[pgid]uint64{6: 2, 3: 3},
   381  			wantfreemap:     map[uint64]pidSet{3: bm1, 2: bm2},
   382  		},
   383  		{
   384  			name:            "test3",
   385  			ids:             []pgid{1, 2},
   386  			pgid:            3,
   387  			want:            []pgid{1, 2, 3},
   388  			wantForwardmap:  map[pgid]uint64{1: 3},
   389  			wantBackwardmap: map[pgid]uint64{3: 3},
   390  			wantfreemap:     map[uint64]pidSet{3: bm1},
   391  		},
   392  		{
   393  			name:            "test4",
   394  			ids:             []pgid{2, 3},
   395  			pgid:            1,
   396  			want:            []pgid{1, 2, 3},
   397  			wantForwardmap:  map[pgid]uint64{1: 3},
   398  			wantBackwardmap: map[pgid]uint64{3: 3},
   399  			wantfreemap:     map[uint64]pidSet{3: bm1},
   400  		},
   401  	}
   402  	for _, tt := range tests {
   403  		f := newTestFreelist()
   404  		if f.freelistType == FreelistArrayType {
   405  			t.Skip()
   406  		}
   407  		f.readIDs(tt.ids)
   408  
   409  		f.mergeWithExistingSpan(tt.pgid)
   410  
   411  		if got := f.getFreePageIDs(); !reflect.DeepEqual(tt.want, got) {
   412  			t.Fatalf("name %s; exp=%v; got=%v", tt.name, tt.want, got)
   413  		}
   414  		if got := f.forwardMap; !reflect.DeepEqual(tt.wantForwardmap, got) {
   415  			t.Fatalf("name %s; exp=%v; got=%v", tt.name, tt.wantForwardmap, got)
   416  		}
   417  		if got := f.backwardMap; !reflect.DeepEqual(tt.wantBackwardmap, got) {
   418  			t.Fatalf("name %s; exp=%v; got=%v", tt.name, tt.wantBackwardmap, got)
   419  		}
   420  		if got := f.freemaps; !reflect.DeepEqual(tt.wantfreemap, got) {
   421  			t.Fatalf("name %s; exp=%v; got=%v", tt.name, tt.wantfreemap, got)
   422  		}
   423  	}
   424  }
   425  
   426  // newTestFreelist get the freelist type from env and initial the freelist
   427  func newTestFreelist() *freelist {
   428  	freelistType := FreelistArrayType
   429  	if env := os.Getenv(TestFreelistType); env == string(FreelistMapType) {
   430  		freelistType = FreelistMapType
   431  	}
   432  
   433  	return newFreelist(freelistType)
   434  }
   435  

View as plain text