1// Copyright 2015 CoreOS, Inc. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package storage 16 17import ( 18 "reflect" 19 "testing" 20) 21 22func TestKeyIndexGet(t *testing.T) { 23 // key: "foo" 24 // rev: 16 25 // generations: 26 // {empty} 27 // {{14, 0}[1], {14, 1}[2], {16, 0}(t)[3]} 28 // {{8, 0}[1], {10, 0}[2], {12, 0}(t)[3]} 29 // {{2, 0}[1], {4, 0}[2], {6, 0}(t)[3]} 30 ki := newTestKeyIndex() 31 ki.compact(4, make(map[revision]struct{})) 32 33 tests := []struct { 34 rev int64 35 36 wmod revision 37 wcreat revision 38 wver int64 39 werr error 40 }{ 41 {17, revision{}, revision{}, 0, ErrRevisionNotFound}, 42 {16, revision{}, revision{}, 0, ErrRevisionNotFound}, 43 44 // get on generation 3 45 {15, revision{14, 1}, revision{14, 0}, 2, nil}, 46 {14, revision{14, 1}, revision{14, 0}, 2, nil}, 47 48 {13, revision{}, revision{}, 0, ErrRevisionNotFound}, 49 {12, revision{}, revision{}, 0, ErrRevisionNotFound}, 50 51 // get on generation 2 52 {11, revision{10, 0}, revision{8, 0}, 2, nil}, 53 {10, revision{10, 0}, revision{8, 0}, 2, nil}, 54 {9, revision{8, 0}, revision{8, 0}, 1, nil}, 55 {8, revision{8, 0}, revision{8, 0}, 1, nil}, 56 57 {7, revision{}, revision{}, 0, ErrRevisionNotFound}, 58 {6, revision{}, revision{}, 0, ErrRevisionNotFound}, 59 60 // get on generation 1 61 {5, revision{4, 0}, revision{2, 0}, 2, nil}, 62 {4, revision{4, 0}, revision{2, 0}, 2, nil}, 63 64 {3, revision{}, revision{}, 0, ErrRevisionNotFound}, 65 {2, revision{}, revision{}, 0, ErrRevisionNotFound}, 66 {1, revision{}, revision{}, 0, ErrRevisionNotFound}, 67 {0, revision{}, revision{}, 0, ErrRevisionNotFound}, 68 } 69 70 for i, tt := range tests { 71 mod, creat, ver, err := ki.get(tt.rev) 72 if err != tt.werr { 73 t.Errorf("#%d: err = %v, want %v", i, err, tt.werr) 74 } 75 if mod != tt.wmod { 76 t.Errorf("#%d: modified = %+v, want %+v", i, mod, tt.wmod) 77 } 78 if creat != tt.wcreat { 79 t.Errorf("#%d: created = %+v, want %+v", i, creat, tt.wcreat) 80 } 81 if ver != tt.wver { 82 t.Errorf("#%d: version = %d, want %d", i, ver, tt.wver) 83 } 84 } 85} 86 87func TestKeyIndexSince(t *testing.T) { 88 ki := newTestKeyIndex() 89 ki.compact(4, make(map[revision]struct{})) 90 91 allRevs := []revision{{4, 0}, {6, 0}, {8, 0}, {10, 0}, {12, 0}, {14, 1}, {16, 0}} 92 tests := []struct { 93 rev int64 94 95 wrevs []revision 96 }{ 97 {17, nil}, 98 {16, allRevs[6:]}, 99 {15, allRevs[6:]}, 100 {14, allRevs[5:]}, 101 {13, allRevs[5:]}, 102 {12, allRevs[4:]}, 103 {11, allRevs[4:]}, 104 {10, allRevs[3:]}, 105 {9, allRevs[3:]}, 106 {8, allRevs[2:]}, 107 {7, allRevs[2:]}, 108 {6, allRevs[1:]}, 109 {5, allRevs[1:]}, 110 {4, allRevs}, 111 {3, allRevs}, 112 {2, allRevs}, 113 {1, allRevs}, 114 {0, allRevs}, 115 } 116 117 for i, tt := range tests { 118 revs := ki.since(tt.rev) 119 if !reflect.DeepEqual(revs, tt.wrevs) { 120 t.Errorf("#%d: revs = %+v, want %+v", i, revs, tt.wrevs) 121 } 122 } 123} 124 125func TestKeyIndexPut(t *testing.T) { 126 ki := &keyIndex{key: []byte("foo")} 127 ki.put(5, 0) 128 129 wki := &keyIndex{ 130 key: []byte("foo"), 131 modified: revision{5, 0}, 132 generations: []generation{{created: revision{5, 0}, ver: 1, revs: []revision{{main: 5}}}}, 133 } 134 if !reflect.DeepEqual(ki, wki) { 135 t.Errorf("ki = %+v, want %+v", ki, wki) 136 } 137 138 ki.put(7, 0) 139 140 wki = &keyIndex{ 141 key: []byte("foo"), 142 modified: revision{7, 0}, 143 generations: []generation{{created: revision{5, 0}, ver: 2, revs: []revision{{main: 5}, {main: 7}}}}, 144 } 145 if !reflect.DeepEqual(ki, wki) { 146 t.Errorf("ki = %+v, want %+v", ki, wki) 147 } 148} 149 150func TestKeyIndexRestore(t *testing.T) { 151 ki := &keyIndex{key: []byte("foo")} 152 ki.restore(revision{5, 0}, revision{7, 0}, 2) 153 154 wki := &keyIndex{ 155 key: []byte("foo"), 156 modified: revision{7, 0}, 157 generations: []generation{{created: revision{5, 0}, ver: 2, revs: []revision{{main: 7}}}}, 158 } 159 if !reflect.DeepEqual(ki, wki) { 160 t.Errorf("ki = %+v, want %+v", ki, wki) 161 } 162} 163 164func TestKeyIndexTombstone(t *testing.T) { 165 ki := &keyIndex{key: []byte("foo")} 166 ki.put(5, 0) 167 168 err := ki.tombstone(7, 0) 169 if err != nil { 170 t.Errorf("unexpected tombstone error: %v", err) 171 } 172 173 wki := &keyIndex{ 174 key: []byte("foo"), 175 modified: revision{7, 0}, 176 generations: []generation{{created: revision{5, 0}, ver: 2, revs: []revision{{main: 5}, {main: 7}}}, {}}, 177 } 178 if !reflect.DeepEqual(ki, wki) { 179 t.Errorf("ki = %+v, want %+v", ki, wki) 180 } 181 182 ki.put(8, 0) 183 ki.put(9, 0) 184 err = ki.tombstone(15, 0) 185 if err != nil { 186 t.Errorf("unexpected tombstone error: %v", err) 187 } 188 189 wki = &keyIndex{ 190 key: []byte("foo"), 191 modified: revision{15, 0}, 192 generations: []generation{ 193 {created: revision{5, 0}, ver: 2, revs: []revision{{main: 5}, {main: 7}}}, 194 {created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 9}, {main: 15}}}, 195 {}, 196 }, 197 } 198 if !reflect.DeepEqual(ki, wki) { 199 t.Errorf("ki = %+v, want %+v", ki, wki) 200 } 201 202 err = ki.tombstone(16, 0) 203 if err != ErrRevisionNotFound { 204 t.Errorf("tombstone error = %v, want %v", err, ErrRevisionNotFound) 205 } 206} 207 208func TestKeyIndexCompact(t *testing.T) { 209 tests := []struct { 210 compact int64 211 212 wki *keyIndex 213 wam map[revision]struct{} 214 }{ 215 { 216 1, 217 &keyIndex{ 218 key: []byte("foo"), 219 modified: revision{16, 0}, 220 generations: []generation{ 221 {created: revision{2, 0}, ver: 3, revs: []revision{{main: 2}, {main: 4}, {main: 6}}}, 222 {created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}}, 223 {created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}}, 224 {}, 225 }, 226 }, 227 map[revision]struct{}{}, 228 }, 229 { 230 2, 231 &keyIndex{ 232 key: []byte("foo"), 233 modified: revision{16, 0}, 234 generations: []generation{ 235 {created: revision{2, 0}, ver: 3, revs: []revision{{main: 2}, {main: 4}, {main: 6}}}, 236 {created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}}, 237 {created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}}, 238 {}, 239 }, 240 }, 241 map[revision]struct{}{ 242 revision{main: 2}: {}, 243 }, 244 }, 245 { 246 3, 247 &keyIndex{ 248 key: []byte("foo"), 249 modified: revision{16, 0}, 250 generations: []generation{ 251 {created: revision{2, 0}, ver: 3, revs: []revision{{main: 2}, {main: 4}, {main: 6}}}, 252 {created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}}, 253 {created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}}, 254 {}, 255 }, 256 }, 257 map[revision]struct{}{ 258 revision{main: 2}: {}, 259 }, 260 }, 261 { 262 4, 263 &keyIndex{ 264 key: []byte("foo"), 265 modified: revision{16, 0}, 266 generations: []generation{ 267 {created: revision{2, 0}, ver: 3, revs: []revision{{main: 4}, {main: 6}}}, 268 {created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}}, 269 {created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}}, 270 {}, 271 }, 272 }, 273 map[revision]struct{}{ 274 revision{main: 4}: {}, 275 }, 276 }, 277 { 278 5, 279 &keyIndex{ 280 key: []byte("foo"), 281 modified: revision{16, 0}, 282 generations: []generation{ 283 {created: revision{2, 0}, ver: 3, revs: []revision{{main: 4}, {main: 6}}}, 284 {created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}}, 285 {created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}}, 286 {}, 287 }, 288 }, 289 map[revision]struct{}{ 290 revision{main: 4}: {}, 291 }, 292 }, 293 { 294 6, 295 &keyIndex{ 296 key: []byte("foo"), 297 modified: revision{16, 0}, 298 generations: []generation{ 299 {created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}}, 300 {created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}}, 301 {}, 302 }, 303 }, 304 map[revision]struct{}{}, 305 }, 306 { 307 7, 308 &keyIndex{ 309 key: []byte("foo"), 310 modified: revision{16, 0}, 311 generations: []generation{ 312 {created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}}, 313 {created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}}, 314 {}, 315 }, 316 }, 317 map[revision]struct{}{}, 318 }, 319 { 320 8, 321 &keyIndex{ 322 key: []byte("foo"), 323 modified: revision{16, 0}, 324 generations: []generation{ 325 {created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}}, 326 {created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}}, 327 {}, 328 }, 329 }, 330 map[revision]struct{}{ 331 revision{main: 8}: {}, 332 }, 333 }, 334 { 335 9, 336 &keyIndex{ 337 key: []byte("foo"), 338 modified: revision{16, 0}, 339 generations: []generation{ 340 {created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}}, 341 {created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}}, 342 {}, 343 }, 344 }, 345 map[revision]struct{}{ 346 revision{main: 8}: {}, 347 }, 348 }, 349 { 350 10, 351 &keyIndex{ 352 key: []byte("foo"), 353 modified: revision{16, 0}, 354 generations: []generation{ 355 {created: revision{8, 0}, ver: 3, revs: []revision{{main: 10}, {main: 12}}}, 356 {created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}}, 357 {}, 358 }, 359 }, 360 map[revision]struct{}{ 361 revision{main: 10}: {}, 362 }, 363 }, 364 { 365 11, 366 &keyIndex{ 367 key: []byte("foo"), 368 modified: revision{16, 0}, 369 generations: []generation{ 370 {created: revision{8, 0}, ver: 3, revs: []revision{{main: 10}, {main: 12}}}, 371 {created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}}, 372 {}, 373 }, 374 }, 375 map[revision]struct{}{ 376 revision{main: 10}: {}, 377 }, 378 }, 379 { 380 12, 381 &keyIndex{ 382 key: []byte("foo"), 383 modified: revision{16, 0}, 384 generations: []generation{ 385 {created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}}, 386 {}, 387 }, 388 }, 389 map[revision]struct{}{}, 390 }, 391 { 392 13, 393 &keyIndex{ 394 key: []byte("foo"), 395 modified: revision{16, 0}, 396 generations: []generation{ 397 {created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}}, 398 {}, 399 }, 400 }, 401 map[revision]struct{}{}, 402 }, 403 { 404 14, 405 &keyIndex{ 406 key: []byte("foo"), 407 modified: revision{16, 0}, 408 generations: []generation{ 409 {created: revision{14, 0}, ver: 3, revs: []revision{{main: 14, sub: 1}, {main: 16}}}, 410 {}, 411 }, 412 }, 413 map[revision]struct{}{ 414 revision{main: 14, sub: 1}: {}, 415 }, 416 }, 417 { 418 15, 419 &keyIndex{ 420 key: []byte("foo"), 421 modified: revision{16, 0}, 422 generations: []generation{ 423 {created: revision{14, 0}, ver: 3, revs: []revision{{main: 14, sub: 1}, {main: 16}}}, 424 {}, 425 }, 426 }, 427 map[revision]struct{}{ 428 revision{main: 14, sub: 1}: {}, 429 }, 430 }, 431 { 432 16, 433 &keyIndex{ 434 key: []byte("foo"), 435 modified: revision{16, 0}, 436 generations: []generation{ 437 {}, 438 }, 439 }, 440 map[revision]struct{}{}, 441 }, 442 } 443 444 // Continuous Compaction 445 ki := newTestKeyIndex() 446 for i, tt := range tests { 447 am := make(map[revision]struct{}) 448 ki.compact(tt.compact, am) 449 if !reflect.DeepEqual(ki, tt.wki) { 450 t.Errorf("#%d: ki = %+v, want %+v", i, ki, tt.wki) 451 } 452 if !reflect.DeepEqual(am, tt.wam) { 453 t.Errorf("#%d: am = %+v, want %+v", i, am, tt.wam) 454 } 455 } 456 457 // Jump Compaction 458 ki = newTestKeyIndex() 459 for i, tt := range tests { 460 if (i%2 == 0 && i < 6) || (i%2 == 1 && i > 6) { 461 am := make(map[revision]struct{}) 462 ki.compact(tt.compact, am) 463 if !reflect.DeepEqual(ki, tt.wki) { 464 t.Errorf("#%d: ki = %+v, want %+v", i, ki, tt.wki) 465 } 466 if !reflect.DeepEqual(am, tt.wam) { 467 t.Errorf("#%d: am = %+v, want %+v", i, am, tt.wam) 468 } 469 } 470 } 471 472 // Once Compaction 473 for i, tt := range tests { 474 ki := newTestKeyIndex() 475 am := make(map[revision]struct{}) 476 ki.compact(tt.compact, am) 477 if !reflect.DeepEqual(ki, tt.wki) { 478 t.Errorf("#%d: ki = %+v, want %+v", i, ki, tt.wki) 479 } 480 if !reflect.DeepEqual(am, tt.wam) { 481 t.Errorf("#%d: am = %+v, want %+v", i, am, tt.wam) 482 } 483 } 484} 485 486// test that compact on version that higher than last modified version works well 487func TestKeyIndexCompactOnFurtherRev(t *testing.T) { 488 ki := &keyIndex{key: []byte("foo")} 489 ki.put(1, 0) 490 ki.put(2, 0) 491 am := make(map[revision]struct{}) 492 ki.compact(3, am) 493 494 wki := &keyIndex{ 495 key: []byte("foo"), 496 modified: revision{2, 0}, 497 generations: []generation{ 498 {created: revision{1, 0}, ver: 2, revs: []revision{{main: 2}}}, 499 }, 500 } 501 wam := map[revision]struct{}{ 502 revision{main: 2}: {}, 503 } 504 if !reflect.DeepEqual(ki, wki) { 505 t.Errorf("ki = %+v, want %+v", ki, wki) 506 } 507 if !reflect.DeepEqual(am, wam) { 508 t.Errorf("am = %+v, want %+v", am, wam) 509 } 510} 511 512func TestKeyIndexIsEmpty(t *testing.T) { 513 tests := []struct { 514 ki *keyIndex 515 w bool 516 }{ 517 { 518 &keyIndex{ 519 key: []byte("foo"), 520 generations: []generation{{}}, 521 }, 522 true, 523 }, 524 { 525 &keyIndex{ 526 key: []byte("foo"), 527 modified: revision{2, 0}, 528 generations: []generation{ 529 {created: revision{1, 0}, ver: 2, revs: []revision{{main: 2}}}, 530 }, 531 }, 532 false, 533 }, 534 } 535 for i, tt := range tests { 536 g := tt.ki.isEmpty() 537 if g != tt.w { 538 t.Errorf("#%d: isEmpty = %v, want %v", i, g, tt.w) 539 } 540 } 541} 542 543func TestKeyIndexFindGeneration(t *testing.T) { 544 ki := newTestKeyIndex() 545 546 tests := []struct { 547 rev int64 548 wg *generation 549 }{ 550 {0, nil}, 551 {1, nil}, 552 {2, &ki.generations[0]}, 553 {3, &ki.generations[0]}, 554 {4, &ki.generations[0]}, 555 {5, &ki.generations[0]}, 556 {6, nil}, 557 {7, nil}, 558 {8, &ki.generations[1]}, 559 {9, &ki.generations[1]}, 560 {10, &ki.generations[1]}, 561 {11, &ki.generations[1]}, 562 {12, nil}, 563 {13, nil}, 564 } 565 for i, tt := range tests { 566 g := ki.findGeneration(tt.rev) 567 if g != tt.wg { 568 t.Errorf("#%d: generation = %+v, want %+v", i, g, tt.wg) 569 } 570 } 571} 572 573func TestKeyIndexLess(t *testing.T) { 574 ki := &keyIndex{key: []byte("foo")} 575 576 tests := []struct { 577 ki *keyIndex 578 w bool 579 }{ 580 {&keyIndex{key: []byte("doo")}, false}, 581 {&keyIndex{key: []byte("foo")}, false}, 582 {&keyIndex{key: []byte("goo")}, true}, 583 } 584 for i, tt := range tests { 585 g := ki.Less(tt.ki) 586 if g != tt.w { 587 t.Errorf("#%d: Less = %v, want %v", i, g, tt.w) 588 } 589 } 590} 591 592func TestGenerationIsEmpty(t *testing.T) { 593 tests := []struct { 594 g *generation 595 w bool 596 }{ 597 {nil, true}, 598 {&generation{}, true}, 599 {&generation{revs: []revision{{main: 1}}}, false}, 600 } 601 for i, tt := range tests { 602 g := tt.g.isEmpty() 603 if g != tt.w { 604 t.Errorf("#%d: isEmpty = %v, want %v", i, g, tt.w) 605 } 606 } 607} 608 609func TestGenerationWalk(t *testing.T) { 610 g := &generation{ 611 ver: 3, 612 created: revision{2, 0}, 613 revs: []revision{{main: 2}, {main: 4}, {main: 6}}, 614 } 615 tests := []struct { 616 f func(rev revision) bool 617 wi int 618 }{ 619 {func(rev revision) bool { return rev.main >= 7 }, 2}, 620 {func(rev revision) bool { return rev.main >= 6 }, 1}, 621 {func(rev revision) bool { return rev.main >= 5 }, 1}, 622 {func(rev revision) bool { return rev.main >= 4 }, 0}, 623 {func(rev revision) bool { return rev.main >= 3 }, 0}, 624 {func(rev revision) bool { return rev.main >= 2 }, -1}, 625 } 626 for i, tt := range tests { 627 idx := g.walk(tt.f) 628 if idx != tt.wi { 629 t.Errorf("#%d: index = %d, want %d", i, idx, tt.wi) 630 } 631 } 632} 633 634func newTestKeyIndex() *keyIndex { 635 // key: "foo" 636 // rev: 16 637 // generations: 638 // {empty} 639 // {{14, 0}[1], {14, 1}[2], {16, 0}(t)[3]} 640 // {{8, 0}[1], {10, 0}[2], {12, 0}(t)[3]} 641 // {{2, 0}[1], {4, 0}[2], {6, 0}(t)[3]} 642 643 ki := &keyIndex{key: []byte("foo")} 644 ki.put(2, 0) 645 ki.put(4, 0) 646 ki.tombstone(6, 0) 647 ki.put(8, 0) 648 ki.put(10, 0) 649 ki.tombstone(12, 0) 650 ki.put(14, 0) 651 ki.put(14, 1) 652 ki.tombstone(16, 0) 653 return ki 654} 655