1package bbolt 2 3import ( 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 13const TestFreelistType = "TEST_FREELIST_TYPE" 14 15// Ensure that a page is added to a transaction's freelist. 16func 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. 25func 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. 34func 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 52func 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 180func 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. 210func 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. 257func 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. 280func 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 304func Benchmark_FreelistRelease10K(b *testing.B) { benchmark_FreelistRelease(b, 10000) } 305func Benchmark_FreelistRelease100K(b *testing.B) { benchmark_FreelistRelease(b, 100000) } 306func Benchmark_FreelistRelease1000K(b *testing.B) { benchmark_FreelistRelease(b, 1000000) } 307func Benchmark_FreelistRelease10000K(b *testing.B) { benchmark_FreelistRelease(b, 10000000) } 308 309func 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 322func 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 332func 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 352func 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 427func 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