1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255 |
- package bitmap
- import (
- "math/rand"
- "testing"
- "time"
- )
- func TestSequenceGetAvailableBit(t *testing.T) {
- input := []struct {
- head *sequence
- from uint64
- bytePos uint64
- bitPos uint64
- }{
- {&sequence{block: 0x0, count: 0}, 0, invalidPos, invalidPos},
- {&sequence{block: 0x0, count: 1}, 0, 0, 0},
- {&sequence{block: 0x0, count: 100}, 0, 0, 0},
- {&sequence{block: 0x80000000, count: 0}, 0, invalidPos, invalidPos},
- {&sequence{block: 0x80000000, count: 1}, 0, 0, 1},
- {&sequence{block: 0x80000000, count: 100}, 0, 0, 1},
- {&sequence{block: 0xFF000000, count: 0}, 0, invalidPos, invalidPos},
- {&sequence{block: 0xFF000000, count: 1}, 0, 1, 0},
- {&sequence{block: 0xFF000000, count: 100}, 0, 1, 0},
- {&sequence{block: 0xFF800000, count: 0}, 0, invalidPos, invalidPos},
- {&sequence{block: 0xFF800000, count: 1}, 0, 1, 1},
- {&sequence{block: 0xFF800000, count: 100}, 0, 1, 1},
- {&sequence{block: 0xFFC0FF00, count: 0}, 0, invalidPos, invalidPos},
- {&sequence{block: 0xFFC0FF00, count: 1}, 0, 1, 2},
- {&sequence{block: 0xFFC0FF00, count: 100}, 0, 1, 2},
- {&sequence{block: 0xFFE0FF00, count: 0}, 0, invalidPos, invalidPos},
- {&sequence{block: 0xFFE0FF00, count: 1}, 0, 1, 3},
- {&sequence{block: 0xFFE0FF00, count: 100}, 0, 1, 3},
- {&sequence{block: 0xFFFEFF00, count: 0}, 0, invalidPos, invalidPos},
- {&sequence{block: 0xFFFEFF00, count: 1}, 0, 1, 7},
- {&sequence{block: 0xFFFEFF00, count: 100}, 0, 1, 7},
- {&sequence{block: 0xFFFFC0FF, count: 0}, 0, invalidPos, invalidPos},
- {&sequence{block: 0xFFFFC0FF, count: 1}, 0, 2, 2},
- {&sequence{block: 0xFFFFC0FF, count: 100}, 0, 2, 2},
- {&sequence{block: 0xFFFFFF00, count: 0}, 0, invalidPos, invalidPos},
- {&sequence{block: 0xFFFFFF00, count: 1}, 0, 3, 0},
- {&sequence{block: 0xFFFFFF00, count: 100}, 0, 3, 0},
- {&sequence{block: 0xFFFFFFFE, count: 0}, 0, invalidPos, invalidPos},
- {&sequence{block: 0xFFFFFFFE, count: 1}, 0, 3, 7},
- {&sequence{block: 0xFFFFFFFE, count: 100}, 0, 3, 7},
- {&sequence{block: 0xFFFFFFFF, count: 0}, 0, invalidPos, invalidPos},
- {&sequence{block: 0xFFFFFFFF, count: 1}, 0, invalidPos, invalidPos},
- {&sequence{block: 0xFFFFFFFF, count: 100}, 0, invalidPos, invalidPos},
- // now test with offset
- {&sequence{block: 0x0, count: 0}, 0, invalidPos, invalidPos},
- {&sequence{block: 0x0, count: 0}, 31, invalidPos, invalidPos},
- {&sequence{block: 0x0, count: 0}, 32, invalidPos, invalidPos},
- {&sequence{block: 0x0, count: 1}, 0, 0, 0},
- {&sequence{block: 0x0, count: 1}, 1, 0, 1},
- {&sequence{block: 0x0, count: 1}, 31, 3, 7},
- {&sequence{block: 0xF0FF0000, count: 1}, 0, 0, 4},
- {&sequence{block: 0xF0FF0000, count: 1}, 8, 2, 0},
- {&sequence{block: 0xFFFFFFFF, count: 1}, 0, invalidPos, invalidPos},
- {&sequence{block: 0xFFFFFFFF, count: 1}, 16, invalidPos, invalidPos},
- {&sequence{block: 0xFFFFFFFF, count: 1}, 31, invalidPos, invalidPos},
- {&sequence{block: 0xFFFFFFFE, count: 1}, 0, 3, 7},
- {&sequence{block: 0xFFFFFFFF, count: 2}, 0, invalidPos, invalidPos},
- {&sequence{block: 0xFFFFFFFF, count: 2}, 32, invalidPos, invalidPos},
- }
- for n, i := range input {
- b, bb, err := i.head.getAvailableBit(i.from)
- if b != i.bytePos || bb != i.bitPos {
- t.Fatalf("Error in sequence.getAvailableBit(%d) (%d).\nExp: (%d, %d)\nGot: (%d, %d), err: %v", i.from, n, i.bytePos, i.bitPos, b, bb, err)
- }
- }
- }
- func TestSequenceEqual(t *testing.T) {
- input := []struct {
- first *sequence
- second *sequence
- areEqual bool
- }{
- {&sequence{block: 0x0, count: 8, next: nil}, &sequence{block: 0x0, count: 8}, true},
- {&sequence{block: 0x0, count: 0, next: nil}, &sequence{block: 0x0, count: 0}, true},
- {&sequence{block: 0x0, count: 2, next: nil}, &sequence{block: 0x0, count: 1, next: &sequence{block: 0x0, count: 1}}, false},
- {&sequence{block: 0x0, count: 2, next: &sequence{block: 0x1, count: 1}}, &sequence{block: 0x0, count: 2}, false},
- {&sequence{block: 0x12345678, count: 8, next: nil}, &sequence{block: 0x12345678, count: 8}, true},
- {&sequence{block: 0x12345678, count: 8, next: nil}, &sequence{block: 0x12345678, count: 9}, false},
- {&sequence{block: 0x12345678, count: 1, next: &sequence{block: 0xFFFFFFFF, count: 1}}, &sequence{block: 0x12345678, count: 1}, false},
- {&sequence{block: 0x12345678, count: 1}, &sequence{block: 0x12345678, count: 1, next: &sequence{block: 0xFFFFFFFF, count: 1}}, false},
- }
- for n, i := range input {
- if i.areEqual != i.first.equal(i.second) {
- t.Fatalf("Error in sequence.equal() (%d).\nExp: %t\nGot: %t,", n, i.areEqual, !i.areEqual)
- }
- }
- }
- func TestSequenceCopy(t *testing.T) {
- s := getTestSequence()
- n := s.getCopy()
- if !s.equal(n) {
- t.Fatal("copy of s failed")
- }
- if n == s {
- t.Fatal("not true copy of s")
- }
- }
- func TestGetFirstAvailable(t *testing.T) {
- input := []struct {
- mask *sequence
- bytePos uint64
- bitPos uint64
- start uint64
- }{
- {&sequence{block: 0xffffffff, count: 2048}, invalidPos, invalidPos, 0},
- {&sequence{block: 0x0, count: 8}, 0, 0, 0},
- {&sequence{block: 0x80000000, count: 8}, 0, 1, 0},
- {&sequence{block: 0xC0000000, count: 8}, 0, 2, 0},
- {&sequence{block: 0xE0000000, count: 8}, 0, 3, 0},
- {&sequence{block: 0xF0000000, count: 8}, 0, 4, 0},
- {&sequence{block: 0xF8000000, count: 8}, 0, 5, 0},
- {&sequence{block: 0xFC000000, count: 8}, 0, 6, 0},
- {&sequence{block: 0xFE000000, count: 8}, 0, 7, 0},
- {&sequence{block: 0xFE000000, count: 8}, 3, 0, 24},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0x00000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 4, 0, 0},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0x80000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 4, 1, 0},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xC0000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 4, 2, 0},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xE0000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 4, 3, 0},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xF0000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 4, 4, 0},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xF8000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 4, 5, 0},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFC000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 4, 6, 0},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFE000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 4, 7, 0},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0x0E000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 4, 0, 16},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFF000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 5, 0, 0},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFF800000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 5, 1, 0},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFC00000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 5, 2, 0},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFE00000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 5, 3, 0},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFF00000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 5, 4, 0},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFF80000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 5, 5, 0},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFFC0000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 5, 6, 0},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFFE0000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 5, 7, 0},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xfffffffe, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 7, 7, 0},
- {&sequence{block: 0xffffffff, count: 2, next: &sequence{block: 0x0, count: 6}}, 8, 0, 0},
- {&sequence{block: 0xfffcffff, count: 1, next: &sequence{block: 0x0, count: 6}}, 4, 0, 16},
- {&sequence{block: 0xfffcffff, count: 1, next: &sequence{block: 0x0, count: 6}}, 1, 7, 15},
- {&sequence{block: 0xfffcffff, count: 1, next: &sequence{block: 0x0, count: 6}}, 1, 6, 10},
- {&sequence{block: 0xfffcfffe, count: 1, next: &sequence{block: 0x0, count: 6}}, 3, 7, 31},
- {&sequence{block: 0xfffcffff, count: 1, next: &sequence{block: 0xffffffff, count: 6}}, invalidPos, invalidPos, 31},
- }
- for n, i := range input {
- bytePos, bitPos, _ := getFirstAvailable(i.mask, i.start)
- if bytePos != i.bytePos || bitPos != i.bitPos {
- t.Fatalf("Error in (%d) getFirstAvailable(). Expected (%d, %d). Got (%d, %d)", n, i.bytePos, i.bitPos, bytePos, bitPos)
- }
- }
- }
- func TestFindSequence(t *testing.T) {
- input := []struct {
- head *sequence
- bytePos uint64
- precBlocks uint64
- inBlockBytePos uint64
- }{
- {&sequence{block: 0xffffffff, count: 0}, 0, 0, invalidPos},
- {&sequence{block: 0xffffffff, count: 0}, 31, 0, invalidPos},
- {&sequence{block: 0xffffffff, count: 0}, 100, 0, invalidPos},
- {&sequence{block: 0x0, count: 1}, 0, 0, 0},
- {&sequence{block: 0x0, count: 1}, 1, 0, 1},
- {&sequence{block: 0x0, count: 1}, 31, 0, invalidPos},
- {&sequence{block: 0x0, count: 1}, 60, 0, invalidPos},
- {&sequence{block: 0xffffffff, count: 10}, 0, 0, 0},
- {&sequence{block: 0xffffffff, count: 10}, 3, 0, 3},
- {&sequence{block: 0xffffffff, count: 10}, 4, 1, 0},
- {&sequence{block: 0xffffffff, count: 10}, 7, 1, 3},
- {&sequence{block: 0xffffffff, count: 10}, 8, 2, 0},
- {&sequence{block: 0xffffffff, count: 10}, 39, 9, 3},
- {&sequence{block: 0xffffffff, count: 10, next: &sequence{block: 0xcc000000, count: 10}}, 79, 9, 3},
- {&sequence{block: 0xffffffff, count: 10, next: &sequence{block: 0xcc000000, count: 10}}, 80, 0, invalidPos},
- }
- for n, i := range input {
- _, _, precBlocks, inBlockBytePos := findSequence(i.head, i.bytePos)
- if precBlocks != i.precBlocks || inBlockBytePos != i.inBlockBytePos {
- t.Fatalf("Error in (%d) findSequence(). Expected (%d, %d). Got (%d, %d)", n, i.precBlocks, i.inBlockBytePos, precBlocks, inBlockBytePos)
- }
- }
- }
- func TestCheckIfAvailable(t *testing.T) {
- input := []struct {
- head *sequence
- ordinal uint64
- bytePos uint64
- bitPos uint64
- }{
- {&sequence{block: 0xffffffff, count: 0}, 0, invalidPos, invalidPos},
- {&sequence{block: 0xffffffff, count: 0}, 31, invalidPos, invalidPos},
- {&sequence{block: 0xffffffff, count: 0}, 100, invalidPos, invalidPos},
- {&sequence{block: 0x0, count: 1}, 0, 0, 0},
- {&sequence{block: 0x0, count: 1}, 1, 0, 1},
- {&sequence{block: 0x0, count: 1}, 31, 3, 7},
- {&sequence{block: 0x0, count: 1}, 60, invalidPos, invalidPos},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0x800000ff, count: 1}}, 31, invalidPos, invalidPos},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0x800000ff, count: 1}}, 32, invalidPos, invalidPos},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0x800000ff, count: 1}}, 33, 4, 1},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xC00000ff, count: 1}}, 33, invalidPos, invalidPos},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xC00000ff, count: 1}}, 34, 4, 2},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xC00000ff, count: 1, next: &sequence{block: 0x0, count: 1}}}, 55, 6, 7},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xC00000ff, count: 1, next: &sequence{block: 0x0, count: 1}}}, 56, invalidPos, invalidPos},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xC00000ff, count: 1, next: &sequence{block: 0x0, count: 1}}}, 63, invalidPos, invalidPos},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xC00000ff, count: 1, next: &sequence{block: 0x0, count: 1}}}, 64, 8, 0},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xC00000ff, count: 1, next: &sequence{block: 0x0, count: 1}}}, 95, 11, 7},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xC00000ff, count: 1, next: &sequence{block: 0x0, count: 1}}}, 96, invalidPos, invalidPos},
- }
- for n, i := range input {
- bytePos, bitPos, err := checkIfAvailable(i.head, i.ordinal)
- if bytePos != i.bytePos || bitPos != i.bitPos {
- t.Fatalf("Error in (%d) checkIfAvailable(ord:%d). Expected (%d, %d). Got (%d, %d). err: %v", n, i.ordinal, i.bytePos, i.bitPos, bytePos, bitPos, err)
- }
- }
- }
- func TestMergeSequences(t *testing.T) {
- input := []struct {
- original *sequence
- merged *sequence
- }{
- {&sequence{block: 0xFE000000, count: 8, next: &sequence{block: 0xFE000000, count: 2}}, &sequence{block: 0xFE000000, count: 10}},
- {&sequence{block: 0xFFFFFFFF, count: 8, next: &sequence{block: 0xFFFFFFFF, count: 1}}, &sequence{block: 0xFFFFFFFF, count: 9}},
- {&sequence{block: 0xFFFFFFFF, count: 1, next: &sequence{block: 0xFFFFFFFF, count: 8}}, &sequence{block: 0xFFFFFFFF, count: 9}},
- {&sequence{block: 0xFFFFFFF0, count: 8, next: &sequence{block: 0xFFFFFFF0, count: 1}}, &sequence{block: 0xFFFFFFF0, count: 9}},
- {&sequence{block: 0xFFFFFFF0, count: 1, next: &sequence{block: 0xFFFFFFF0, count: 8}}, &sequence{block: 0xFFFFFFF0, count: 9}},
- {&sequence{block: 0xFE, count: 8, next: &sequence{block: 0xFE, count: 1, next: &sequence{block: 0xFE, count: 5}}}, &sequence{block: 0xFE, count: 14}},
- {&sequence{block: 0xFE, count: 8, next: &sequence{block: 0xFE, count: 1, next: &sequence{block: 0xFE, count: 5, next: &sequence{block: 0xFF, count: 1}}}},
- &sequence{block: 0xFE, count: 14, next: &sequence{block: 0xFF, count: 1}}},
- // No merge
- {&sequence{block: 0xFE, count: 8, next: &sequence{block: 0xF8, count: 1, next: &sequence{block: 0xFE, count: 5}}},
- &sequence{block: 0xFE, count: 8, next: &sequence{block: 0xF8, count: 1, next: &sequence{block: 0xFE, count: 5}}}},
- // No merge from head: // Merge function tries to merge from passed head. If it can't merge with next, it does not reattempt with next as head
- {&sequence{block: 0xFE, count: 8, next: &sequence{block: 0xFF, count: 1, next: &sequence{block: 0xFF, count: 5}}},
- &sequence{block: 0xFE, count: 8, next: &sequence{block: 0xFF, count: 6}}},
- }
- for n, i := range input {
- mergeSequences(i.original)
- for !i.merged.equal(i.original) {
- t.Fatalf("Error in (%d) mergeSequences().\nExp: %s\nGot: %s,", n, i.merged.toString(), i.original.toString())
- }
- }
- }
- func TestPushReservation(t *testing.T) {
- input := []struct {
- mask *sequence
- bytePos uint64
- bitPos uint64
- newMask *sequence
- }{
- // Create first sequence and fill in 8 addresses starting from address 0
- {&sequence{block: 0x0, count: 8, next: nil}, 0, 0, &sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 7, next: nil}}},
- {&sequence{block: 0x80000000, count: 8}, 0, 1, &sequence{block: 0xC0000000, count: 1, next: &sequence{block: 0x80000000, count: 7, next: nil}}},
- {&sequence{block: 0xC0000000, count: 8}, 0, 2, &sequence{block: 0xE0000000, count: 1, next: &sequence{block: 0xC0000000, count: 7, next: nil}}},
- {&sequence{block: 0xE0000000, count: 8}, 0, 3, &sequence{block: 0xF0000000, count: 1, next: &sequence{block: 0xE0000000, count: 7, next: nil}}},
- {&sequence{block: 0xF0000000, count: 8}, 0, 4, &sequence{block: 0xF8000000, count: 1, next: &sequence{block: 0xF0000000, count: 7, next: nil}}},
- {&sequence{block: 0xF8000000, count: 8}, 0, 5, &sequence{block: 0xFC000000, count: 1, next: &sequence{block: 0xF8000000, count: 7, next: nil}}},
- {&sequence{block: 0xFC000000, count: 8}, 0, 6, &sequence{block: 0xFE000000, count: 1, next: &sequence{block: 0xFC000000, count: 7, next: nil}}},
- {&sequence{block: 0xFE000000, count: 8}, 0, 7, &sequence{block: 0xFF000000, count: 1, next: &sequence{block: 0xFE000000, count: 7, next: nil}}},
- {&sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 7}}, 0, 1, &sequence{block: 0xC0000000, count: 1, next: &sequence{block: 0x0, count: 7, next: nil}}},
- // Create second sequence and fill in 8 addresses starting from address 32
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0x00000000, count: 1, next: &sequence{block: 0xffffffff, count: 6, next: nil}}}, 4, 0,
- &sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0x80000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0x80000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 4, 1,
- &sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xC0000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xC0000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 4, 2,
- &sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xE0000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xE0000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 4, 3,
- &sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xF0000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xF0000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 4, 4,
- &sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xF8000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xF8000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 4, 5,
- &sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFC000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFC000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 4, 6,
- &sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFE000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFE000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 4, 7,
- &sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFF000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}},
- // fill in 8 addresses starting from address 40
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFF000000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 5, 0,
- &sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFF800000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFF800000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 5, 1,
- &sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFC00000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFC00000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 5, 2,
- &sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFE00000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFE00000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 5, 3,
- &sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFF00000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFF00000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 5, 4,
- &sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFF80000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFF80000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 5, 5,
- &sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFFC0000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFFC0000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 5, 6,
- &sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFFE0000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFFE0000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}, 5, 7,
- &sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xFFFF0000, count: 1, next: &sequence{block: 0xffffffff, count: 6}}}},
- // Insert new sequence
- {&sequence{block: 0xffffffff, count: 2, next: &sequence{block: 0x0, count: 6}}, 8, 0,
- &sequence{block: 0xffffffff, count: 2, next: &sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 5}}}},
- {&sequence{block: 0xffffffff, count: 2, next: &sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 5}}}, 8, 1,
- &sequence{block: 0xffffffff, count: 2, next: &sequence{block: 0xC0000000, count: 1, next: &sequence{block: 0x0, count: 5}}}},
- // Merge affected with next
- {&sequence{block: 0xffffffff, count: 7, next: &sequence{block: 0xfffffffe, count: 2, next: &sequence{block: 0xffffffff, count: 1}}}, 31, 7,
- &sequence{block: 0xffffffff, count: 8, next: &sequence{block: 0xfffffffe, count: 1, next: &sequence{block: 0xffffffff, count: 1}}}},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xfffffffc, count: 1, next: &sequence{block: 0xfffffffe, count: 6}}}, 7, 6,
- &sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xfffffffe, count: 7}}},
- // Merge affected with next and next.next
- {&sequence{block: 0xffffffff, count: 7, next: &sequence{block: 0xfffffffe, count: 1, next: &sequence{block: 0xffffffff, count: 1}}}, 31, 7,
- &sequence{block: 0xffffffff, count: 9}},
- {&sequence{block: 0xffffffff, count: 7, next: &sequence{block: 0xfffffffe, count: 1}}, 31, 7,
- &sequence{block: 0xffffffff, count: 8}},
- // Merge affected with previous and next
- {&sequence{block: 0xffffffff, count: 7, next: &sequence{block: 0xfffffffe, count: 1, next: &sequence{block: 0xffffffff, count: 1}}}, 31, 7,
- &sequence{block: 0xffffffff, count: 9}},
- // Redundant push: No change
- {&sequence{block: 0xffff0000, count: 1}, 0, 0, &sequence{block: 0xffff0000, count: 1}},
- {&sequence{block: 0xffff0000, count: 7}, 25, 7, &sequence{block: 0xffff0000, count: 7}},
- {&sequence{block: 0xffffffff, count: 7, next: &sequence{block: 0xfffffffe, count: 1, next: &sequence{block: 0xffffffff, count: 1}}}, 7, 7,
- &sequence{block: 0xffffffff, count: 7, next: &sequence{block: 0xfffffffe, count: 1, next: &sequence{block: 0xffffffff, count: 1}}}},
- // Set last bit
- {&sequence{block: 0x0, count: 8}, 31, 7, &sequence{block: 0x0, count: 7, next: &sequence{block: 0x1, count: 1}}},
- // Set bit in a middle sequence in the first block, first bit
- {&sequence{block: 0x40000000, count: 1, next: &sequence{block: 0x0, count: 6, next: &sequence{block: 0x1, count: 1}}}, 4, 0,
- &sequence{block: 0x40000000, count: 1, next: &sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 5,
- next: &sequence{block: 0x1, count: 1}}}}},
- // Set bit in a middle sequence in the first block, first bit (merge involved)
- {&sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 6, next: &sequence{block: 0x1, count: 1}}}, 4, 0,
- &sequence{block: 0x80000000, count: 2, next: &sequence{block: 0x0, count: 5, next: &sequence{block: 0x1, count: 1}}}},
- // Set bit in a middle sequence in the first block, last bit
- {&sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 6, next: &sequence{block: 0x1, count: 1}}}, 4, 31,
- &sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x1, count: 1, next: &sequence{block: 0x0, count: 5,
- next: &sequence{block: 0x1, count: 1}}}}},
- // Set bit in a middle sequence in the first block, middle bit
- {&sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 6, next: &sequence{block: 0x1, count: 1}}}, 4, 16,
- &sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x8000, count: 1, next: &sequence{block: 0x0, count: 5,
- next: &sequence{block: 0x1, count: 1}}}}},
- // Set bit in a middle sequence in a middle block, first bit
- {&sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 6, next: &sequence{block: 0x1, count: 1}}}, 16, 0,
- &sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 3, next: &sequence{block: 0x80000000, count: 1,
- next: &sequence{block: 0x0, count: 2, next: &sequence{block: 0x1, count: 1}}}}}},
- // Set bit in a middle sequence in a middle block, last bit
- {&sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 6, next: &sequence{block: 0x1, count: 1}}}, 16, 31,
- &sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 3, next: &sequence{block: 0x1, count: 1,
- next: &sequence{block: 0x0, count: 2, next: &sequence{block: 0x1, count: 1}}}}}},
- // Set bit in a middle sequence in a middle block, middle bit
- {&sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 6, next: &sequence{block: 0x1, count: 1}}}, 16, 15,
- &sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 3, next: &sequence{block: 0x10000, count: 1,
- next: &sequence{block: 0x0, count: 2, next: &sequence{block: 0x1, count: 1}}}}}},
- // Set bit in a middle sequence in the last block, first bit
- {&sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 6, next: &sequence{block: 0x1, count: 1}}}, 24, 0,
- &sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 5, next: &sequence{block: 0x80000000, count: 1,
- next: &sequence{block: 0x1, count: 1}}}}},
- // Set bit in a middle sequence in the last block, last bit
- {&sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 6, next: &sequence{block: 0x4, count: 1}}}, 24, 31,
- &sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 5, next: &sequence{block: 0x1, count: 1,
- next: &sequence{block: 0x4, count: 1}}}}},
- // Set bit in a middle sequence in the last block, last bit (merge involved)
- {&sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 6, next: &sequence{block: 0x1, count: 1}}}, 24, 31,
- &sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 5, next: &sequence{block: 0x1, count: 2}}}},
- // Set bit in a middle sequence in the last block, middle bit
- {&sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 6, next: &sequence{block: 0x1, count: 1}}}, 24, 16,
- &sequence{block: 0x80000000, count: 1, next: &sequence{block: 0x0, count: 5, next: &sequence{block: 0x8000, count: 1,
- next: &sequence{block: 0x1, count: 1}}}}},
- }
- for n, i := range input {
- mask := pushReservation(i.bytePos, i.bitPos, i.mask, false)
- if !mask.equal(i.newMask) {
- t.Fatalf("Error in (%d) pushReservation():\n%s + (%d,%d):\nExp: %s\nGot: %s,",
- n, i.mask.toString(), i.bytePos, i.bitPos, i.newMask.toString(), mask.toString())
- }
- }
- }
- func TestSerializeDeserialize(t *testing.T) {
- s := getTestSequence()
- data, err := s.toByteArray()
- if err != nil {
- t.Fatal(err)
- }
- r := &sequence{}
- err = r.fromByteArray(data)
- if err != nil {
- t.Fatal(err)
- }
- if !s.equal(r) {
- t.Fatalf("Sequences are different: \n%v\n%v", s, r)
- }
- }
- func getTestSequence() *sequence {
- // Returns a custom sequence of 1024 * 32 bits
- return &sequence{
- block: 0xFFFFFFFF,
- count: 100,
- next: &sequence{
- block: 0xFFFFFFFE,
- count: 1,
- next: &sequence{
- block: 0xFF000000,
- count: 10,
- next: &sequence{
- block: 0xFFFFFFFF,
- count: 50,
- next: &sequence{
- block: 0xFFFFFFFC,
- count: 1,
- next: &sequence{
- block: 0xFF800000,
- count: 1,
- next: &sequence{
- block: 0xFFFFFFFF,
- count: 87,
- next: &sequence{
- block: 0x0,
- count: 150,
- next: &sequence{
- block: 0xFFFFFFFF,
- count: 200,
- next: &sequence{
- block: 0x0000FFFF,
- count: 1,
- next: &sequence{
- block: 0x0,
- count: 399,
- next: &sequence{
- block: 0xFFFFFFFF,
- count: 23,
- next: &sequence{
- block: 0x1,
- count: 1,
- },
- },
- },
- },
- },
- },
- },
- },
- },
- },
- },
- },
- }
- }
- func TestSet(t *testing.T) {
- hnd := New(1024 * 32)
- hnd.head = getTestSequence()
- firstAv := uint64(32*100 + 31)
- last := uint64(1024*32 - 1)
- if hnd.IsSet(100000) {
- t.Fatal("IsSet() returned wrong result")
- }
- if !hnd.IsSet(0) {
- t.Fatal("IsSet() returned wrong result")
- }
- if hnd.IsSet(firstAv) {
- t.Fatal("IsSet() returned wrong result")
- }
- if !hnd.IsSet(last) {
- t.Fatal("IsSet() returned wrong result")
- }
- if err := hnd.Set(0); err == nil {
- t.Fatal("Expected failure, but succeeded")
- }
- os, err := hnd.SetAny(false)
- if err != nil {
- t.Fatalf("Unexpected failure: %v", err)
- }
- if os != firstAv {
- t.Fatalf("SetAny returned unexpected ordinal. Expected %d. Got %d.", firstAv, os)
- }
- if !hnd.IsSet(firstAv) {
- t.Fatal("IsSet() returned wrong result")
- }
- if err := hnd.Unset(firstAv); err != nil {
- t.Fatalf("Unexpected failure: %v", err)
- }
- if hnd.IsSet(firstAv) {
- t.Fatal("IsSet() returned wrong result")
- }
- if err := hnd.Set(firstAv); err != nil {
- t.Fatalf("Unexpected failure: %v", err)
- }
- if err := hnd.Set(last); err == nil {
- t.Fatal("Expected failure, but succeeded")
- }
- }
- func TestSetUnset(t *testing.T) {
- numBits := uint64(32 * blockLen)
- hnd := New(numBits)
- if err := hnd.Set(uint64(32 * blockLen)); err == nil {
- t.Fatal("Expected failure, but succeeded")
- }
- if err := hnd.Unset(uint64(32 * blockLen)); err == nil {
- t.Fatal("Expected failure, but succeeded")
- }
- // set and unset all one by one
- for hnd.Unselected() > 0 {
- if _, err := hnd.SetAny(false); err != nil {
- t.Fatal(err)
- }
- }
- if _, err := hnd.SetAny(false); err != ErrNoBitAvailable {
- t.Fatal("Expected error. Got success")
- }
- if _, err := hnd.SetAnyInRange(10, 20, false); err != ErrNoBitAvailable {
- t.Fatal("Expected error. Got success")
- }
- if err := hnd.Set(50); err != ErrBitAllocated {
- t.Fatalf("Expected error. Got %v: %s", err, hnd)
- }
- i := uint64(0)
- for hnd.Unselected() < numBits {
- if err := hnd.Unset(i); err != nil {
- t.Fatal(err)
- }
- i++
- }
- }
- func TestOffsetSetUnset(t *testing.T) {
- numBits := uint64(32 * blockLen)
- hnd := New(numBits)
- // set and unset all one by one
- for hnd.Unselected() > 0 {
- if _, err := hnd.SetAny(false); err != nil {
- t.Fatal(err)
- }
- }
- if _, err := hnd.SetAny(false); err != ErrNoBitAvailable {
- t.Fatal("Expected error. Got success")
- }
- if _, err := hnd.SetAnyInRange(10, 20, false); err != ErrNoBitAvailable {
- t.Fatal("Expected error. Got success")
- }
- if err := hnd.Unset(288); err != nil {
- t.Fatal(err)
- }
- //At this point sequence is (0xffffffff, 9)->(0x7fffffff, 1)->(0xffffffff, 22)->end
- o, err := hnd.SetAnyInRange(32, 500, false)
- if err != nil {
- t.Fatal(err)
- }
- if o != 288 {
- t.Fatalf("Expected ordinal not received, Received:%d", o)
- }
- }
- func TestSetInRange(t *testing.T) {
- numBits := uint64(1024 * blockLen)
- hnd := New(numBits)
- hnd.head = getTestSequence()
- firstAv := uint64(100*blockLen + blockLen - 1)
- if o, err := hnd.SetAnyInRange(4, 3, false); err == nil {
- t.Fatalf("Expected failure. Got success with ordinal:%d", o)
- }
- if o, err := hnd.SetAnyInRange(0, numBits, false); err == nil {
- t.Fatalf("Expected failure. Got success with ordinal:%d", o)
- }
- o, err := hnd.SetAnyInRange(100*uint64(blockLen), 101*uint64(blockLen), false)
- if err != nil {
- t.Fatalf("Unexpected failure: (%d, %v)", o, err)
- }
- if o != firstAv {
- t.Fatalf("Unexpected ordinal: %d", o)
- }
- if o, err := hnd.SetAnyInRange(0, uint64(blockLen), false); err == nil {
- t.Fatalf("Expected failure. Got success with ordinal:%d", o)
- }
- if o, err := hnd.SetAnyInRange(0, firstAv-1, false); err == nil {
- t.Fatalf("Expected failure. Got success with ordinal:%d", o)
- }
- if o, err := hnd.SetAnyInRange(111*uint64(blockLen), 161*uint64(blockLen), false); err == nil {
- t.Fatalf("Expected failure. Got success with ordinal:%d", o)
- }
- o, err = hnd.SetAnyInRange(161*uint64(blockLen), 162*uint64(blockLen), false)
- if err != nil {
- t.Fatal(err)
- }
- if o != 161*uint64(blockLen)+30 {
- t.Fatalf("Unexpected ordinal: %d", o)
- }
- o, err = hnd.SetAnyInRange(161*uint64(blockLen), 162*uint64(blockLen), false)
- if err != nil {
- t.Fatal(err)
- }
- if o != 161*uint64(blockLen)+31 {
- t.Fatalf("Unexpected ordinal: %d", o)
- }
- o, err = hnd.SetAnyInRange(161*uint64(blockLen), 162*uint64(blockLen), false)
- if err == nil {
- t.Fatalf("Expected failure. Got success with ordinal:%d", o)
- }
- if _, err := hnd.SetAnyInRange(0, numBits-1, false); err != nil {
- t.Fatalf("Unexpected failure: %v", err)
- }
- // set one bit using the set range with 1 bit size range
- if _, err := hnd.SetAnyInRange(uint64(163*blockLen-1), uint64(163*blockLen-1), false); err != nil {
- t.Fatal(err)
- }
- // create a non multiple of 32 mask
- hnd = New(30)
- // set all bit in the first range
- for hnd.Unselected() > 22 {
- if o, err := hnd.SetAnyInRange(0, 7, false); err != nil {
- t.Fatalf("Unexpected failure: (%d, %v)", o, err)
- }
- }
- // try one more set, which should fail
- o, err = hnd.SetAnyInRange(0, 7, false)
- if err == nil {
- t.Fatalf("Expected failure. Got success with ordinal:%d", o)
- }
- if err != ErrNoBitAvailable {
- t.Fatalf("Unexpected error: %v", err)
- }
- // set all bit in a second range
- for hnd.Unselected() > 14 {
- if o, err := hnd.SetAnyInRange(8, 15, false); err != nil {
- t.Fatalf("Unexpected failure: (%d, %v)", o, err)
- }
- }
- // try one more set, which should fail
- o, err = hnd.SetAnyInRange(0, 15, false)
- if err == nil {
- t.Fatalf("Expected failure. Got success with ordinal:%d", o)
- }
- if err != ErrNoBitAvailable {
- t.Fatalf("Unexpected error: %v", err)
- }
- // set all bit in a range which includes the last bit
- for hnd.Unselected() > 12 {
- if o, err := hnd.SetAnyInRange(28, 29, false); err != nil {
- t.Fatalf("Unexpected failure: (%d, %v)", o, err)
- }
- }
- o, err = hnd.SetAnyInRange(28, 29, false)
- if err == nil {
- t.Fatalf("Expected failure. Got success with ordinal:%d", o)
- }
- if err != ErrNoBitAvailable {
- t.Fatalf("Unexpected error: %v", err)
- }
- }
- // This one tests an allocation pattern which unveiled an issue in pushReservation
- // Specifically a failure in detecting when we are in the (B) case (the bit to set
- // belongs to the last block of the current sequence). Because of a bug, code
- // was assuming the bit belonged to a block in the middle of the current sequence.
- // Which in turn caused an incorrect allocation when requesting a bit which is not
- // in the first or last sequence block.
- func TestSetAnyInRange(t *testing.T) {
- numBits := uint64(8 * blockLen)
- hnd := New(numBits)
- if err := hnd.Set(0); err != nil {
- t.Fatal(err)
- }
- if err := hnd.Set(255); err != nil {
- t.Fatal(err)
- }
- o, err := hnd.SetAnyInRange(128, 255, false)
- if err != nil {
- t.Fatal(err)
- }
- if o != 128 {
- t.Fatalf("Unexpected ordinal: %d", o)
- }
- o, err = hnd.SetAnyInRange(128, 255, false)
- if err != nil {
- t.Fatal(err)
- }
- if o != 129 {
- t.Fatalf("Unexpected ordinal: %d", o)
- }
- o, err = hnd.SetAnyInRange(246, 255, false)
- if err != nil {
- t.Fatal(err)
- }
- if o != 246 {
- t.Fatalf("Unexpected ordinal: %d", o)
- }
- o, err = hnd.SetAnyInRange(246, 255, false)
- if err != nil {
- t.Fatal(err)
- }
- if o != 247 {
- t.Fatalf("Unexpected ordinal: %d", o)
- }
- }
- func TestMethods(t *testing.T) {
- numBits := uint64(256 * blockLen)
- hnd := New(numBits)
- if hnd.Bits() != numBits {
- t.Fatalf("Unexpected bit number: %d", hnd.Bits())
- }
- if hnd.Unselected() != numBits {
- t.Fatalf("Unexpected bit number: %d", hnd.Unselected())
- }
- exp := "(0x0, 256)->end"
- if hnd.head.toString() != exp {
- t.Fatalf("Unexpected sequence string: %s", hnd.head.toString())
- }
- for i := 0; i < 192; i++ {
- _, err := hnd.SetAny(false)
- if err != nil {
- t.Fatal(err)
- }
- }
- exp = "(0xffffffff, 6)->(0x0, 250)->end"
- if hnd.head.toString() != exp {
- t.Fatalf("Unexpected sequence string: %s", hnd.head.toString())
- }
- }
- func TestRandomAllocateDeallocate(t *testing.T) {
- numBits := int(16 * blockLen)
- hnd := New(uint64(numBits))
- seed := time.Now().Unix()
- rand.Seed(seed)
- // Allocate all bits using a random pattern
- pattern := rand.Perm(numBits)
- for _, bit := range pattern {
- err := hnd.Set(uint64(bit))
- if err != nil {
- t.Fatalf("Unexpected failure on allocation of %d: %v.\nSeed: %d.\n%s", bit, err, seed, hnd)
- }
- }
- if hnd.Unselected() != 0 {
- t.Fatalf("Expected full sequence. Instead found %d free bits. Seed: %d.\n%s", hnd.unselected, seed, hnd)
- }
- if hnd.head.toString() != "(0xffffffff, 16)->end" {
- t.Fatalf("Unexpected db: %s", hnd.head.toString())
- }
- // Deallocate all bits using a random pattern
- pattern = rand.Perm(numBits)
- for _, bit := range pattern {
- err := hnd.Unset(uint64(bit))
- if err != nil {
- t.Fatalf("Unexpected failure on deallocation of %d: %v.\nSeed: %d.\n%s", bit, err, seed, hnd)
- }
- }
- if hnd.Unselected() != uint64(numBits) {
- t.Fatalf("Expected full sequence. Instead found %d free bits. Seed: %d.\n%s", hnd.unselected, seed, hnd)
- }
- if hnd.head.toString() != "(0x0, 16)->end" {
- t.Fatalf("Unexpected db: %s", hnd.head.toString())
- }
- }
- func TestAllocateRandomDeallocate(t *testing.T) {
- numBlocks := uint32(8)
- numBits := int(numBlocks * blockLen)
- hnd := New(uint64(numBits))
- expected := &sequence{block: 0xffffffff, count: uint64(numBlocks / 2), next: &sequence{block: 0x0, count: uint64(numBlocks / 2)}}
- // Allocate first half of the bits
- for i := 0; i < numBits/2; i++ {
- _, err := hnd.SetAny(false)
- if err != nil {
- t.Fatalf("Unexpected failure on allocation %d: %v\n%s", i, err, hnd)
- }
- }
- if hnd.Unselected() != uint64(numBits/2) {
- t.Fatalf("Expected full sequence. Instead found %d free bits. %s", hnd.unselected, hnd)
- }
- if !hnd.head.equal(expected) {
- t.Fatalf("Unexpected sequence. Got:\n%s", hnd)
- }
- seed := time.Now().Unix()
- rand.Seed(seed)
- // Deallocate half of the allocated bits following a random pattern
- pattern := rand.Perm(numBits / 2)
- for i := 0; i < numBits/4; i++ {
- bit := pattern[i]
- err := hnd.Unset(uint64(bit))
- if err != nil {
- t.Fatalf("Unexpected failure on deallocation of %d: %v.\nSeed: %d.\n%s", bit, err, seed, hnd)
- }
- }
- if hnd.Unselected() != uint64(3*numBits/4) {
- t.Fatalf("Expected full sequence. Instead found %d free bits.\nSeed: %d.\n%s", hnd.unselected, seed, hnd)
- }
- // Request a quarter of bits
- for i := 0; i < numBits/4; i++ {
- _, err := hnd.SetAny(false)
- if err != nil {
- t.Fatalf("Unexpected failure on allocation %d: %v\nSeed: %d\n%s", i, err, seed, hnd)
- }
- }
- if hnd.Unselected() != uint64(numBits/2) {
- t.Fatalf("Expected half sequence. Instead found %d free bits.\nSeed: %d\n%s", hnd.unselected, seed, hnd)
- }
- if !hnd.head.equal(expected) {
- t.Fatalf("Unexpected sequence. Got:\n%s", hnd)
- }
- }
- func TestAllocateRandomDeallocateSerialize(t *testing.T) {
- numBlocks := uint32(8)
- numBits := int(numBlocks * blockLen)
- hnd := New(uint64(numBits))
- expected := &sequence{block: 0xffffffff, count: uint64(numBlocks / 2), next: &sequence{block: 0x0, count: uint64(numBlocks / 2)}}
- // Allocate first half of the bits
- for i := 0; i < numBits/2; i++ {
- _, err := hnd.SetAny(true)
- if err != nil {
- t.Fatalf("Unexpected failure on allocation %d: %v\n%s", i, err, hnd)
- }
- }
- if hnd.Unselected() != uint64(numBits/2) {
- t.Fatalf("Expected full sequence. Instead found %d free bits. %s", hnd.unselected, hnd)
- }
- if !hnd.head.equal(expected) {
- t.Fatalf("Unexpected sequence. Got:\n%s", hnd)
- }
- seed := time.Now().Unix()
- rand.Seed(seed)
- // Deallocate half of the allocated bits following a random pattern
- pattern := rand.Perm(numBits / 2)
- for i := 0; i < numBits/4; i++ {
- bit := pattern[i]
- err := hnd.Unset(uint64(bit))
- if err != nil {
- t.Fatalf("Unexpected failure on deallocation of %d: %v.\nSeed: %d.\n%s", bit, err, seed, hnd)
- }
- }
- if hnd.Unselected() != uint64(3*numBits/4) {
- t.Fatalf("Expected full sequence. Instead found %d free bits.\nSeed: %d.\n%s", hnd.unselected, seed, hnd)
- }
- // Request a quarter of bits
- for i := 0; i < numBits/4; i++ {
- _, err := hnd.SetAny(true)
- if err != nil {
- t.Fatalf("Unexpected failure on allocation %d: %v\nSeed: %d\n%s", i, err, seed, hnd)
- }
- }
- if hnd.Unselected() != uint64(numBits/2) {
- t.Fatalf("Expected half sequence. Instead found %d free bits.\nSeed: %d\n%s", hnd.unselected, seed, hnd)
- }
- }
- func TestIsCorrupted(t *testing.T) {
- // Negative test
- hnd := New(1024)
- if hnd.CheckConsistency() {
- t.Fatalf("Unexpected corrupted for %s", hnd)
- }
- hnd.Set(0)
- if hnd.CheckConsistency() {
- t.Fatalf("Unexpected corrupted for %s", hnd)
- }
- hnd.Set(1023)
- if hnd.CheckConsistency() {
- t.Fatalf("Unexpected corrupted for %s", hnd)
- }
- // Try real corrupted ipam handles found in the local store files reported by three docker users,
- // plus a generic ipam handle from docker 1.9.1. This last will fail as well, because of how the
- // last node in the sequence is expressed (This is true for IPAM handle only, because of the broadcast
- // address reservation: last bit). This will allow an application using bitseq that runs a consistency
- // check to detect and replace the 1.9.0/1 old vulnerable handle with the new one.
- input := []*Bitmap{
- {
- bits: 65536,
- unselected: 65412,
- head: &sequence{
- block: 0xffffffff,
- count: 3,
- next: &sequence{
- block: 0xffffffbf,
- count: 0,
- next: &sequence{
- block: 0xfe98816e,
- count: 1,
- next: &sequence{
- block: 0xffffffff,
- count: 0,
- next: &sequence{
- block: 0xe3bc0000,
- count: 1,
- next: &sequence{
- block: 0x0,
- count: 2042,
- next: &sequence{
- block: 0x1, count: 1,
- next: &sequence{
- block: 0x0, count: 0,
- },
- },
- },
- },
- },
- },
- },
- },
- },
- {
- bits: 65536,
- unselected: 65319,
- head: &sequence{
- block: 0xffffffff,
- count: 7,
- next: &sequence{
- block: 0xffffff7f,
- count: 0,
- next: &sequence{
- block: 0xffffffff,
- count: 0,
- next: &sequence{
- block: 0x2000000,
- count: 1,
- next: &sequence{
- block: 0x0,
- count: 2039,
- next: &sequence{
- block: 0x1,
- count: 1,
- next: &sequence{
- block: 0x0,
- count: 0,
- },
- },
- },
- },
- },
- },
- },
- },
- {
- bits: 65536,
- unselected: 65456,
- head: &sequence{
- block: 0xffffffff, count: 2,
- next: &sequence{
- block: 0xfffbffff, count: 0,
- next: &sequence{
- block: 0xffd07000, count: 1,
- next: &sequence{
- block: 0x0, count: 333,
- next: &sequence{
- block: 0x40000000, count: 1,
- next: &sequence{
- block: 0x0, count: 1710,
- next: &sequence{
- block: 0x1, count: 1,
- next: &sequence{
- block: 0x0, count: 0,
- },
- },
- },
- },
- },
- },
- },
- },
- },
- }
- for idx, hnd := range input {
- if !hnd.CheckConsistency() {
- t.Fatalf("Expected corrupted for (%d): %s", idx, hnd)
- }
- if hnd.CheckConsistency() {
- t.Fatalf("Sequence still marked corrupted (%d): %s", idx, hnd)
- }
- }
- }
- func testSetRollover(t *testing.T, serial bool) {
- numBlocks := uint32(8)
- numBits := int(numBlocks * blockLen)
- hnd := New(uint64(numBits))
- // Allocate first half of the bits
- for i := 0; i < numBits/2; i++ {
- _, err := hnd.SetAny(serial)
- if err != nil {
- t.Fatalf("Unexpected failure on allocation %d: %v\n%s", i, err, hnd)
- }
- }
- if hnd.Unselected() != uint64(numBits/2) {
- t.Fatalf("Expected full sequence. Instead found %d free bits. %s", hnd.unselected, hnd)
- }
- seed := time.Now().Unix()
- rand.Seed(seed)
- // Deallocate half of the allocated bits following a random pattern
- pattern := rand.Perm(numBits / 2)
- for i := 0; i < numBits/4; i++ {
- bit := pattern[i]
- err := hnd.Unset(uint64(bit))
- if err != nil {
- t.Fatalf("Unexpected failure on deallocation of %d: %v.\nSeed: %d.\n%s", bit, err, seed, hnd)
- }
- }
- if hnd.Unselected() != uint64(3*numBits/4) {
- t.Fatalf("Unexpected free bits: found %d free bits.\nSeed: %d.\n%s", hnd.unselected, seed, hnd)
- }
- //request to allocate for remaining half of the bits
- for i := 0; i < numBits/2; i++ {
- _, err := hnd.SetAny(serial)
- if err != nil {
- t.Fatalf("Unexpected failure on allocation %d: %v\nSeed: %d\n%s", i, err, seed, hnd)
- }
- }
- //At this point all the bits must be allocated except the randomly unallocated bits
- //which were unallocated in the first half of the bit sequence
- if hnd.Unselected() != uint64(numBits/4) {
- t.Fatalf("Unexpected number of unselected bits %d, Expected %d", hnd.Unselected(), numBits/4)
- }
- for i := 0; i < numBits/4; i++ {
- _, err := hnd.SetAny(serial)
- if err != nil {
- t.Fatalf("Unexpected failure on allocation %d: %v\nSeed: %d\n%s", i, err, seed, hnd)
- }
- }
- //Now requesting to allocate the unallocated random bits (qurter of the number of bits) should
- //leave no more bits that can be allocated.
- if hnd.Unselected() != 0 {
- t.Fatalf("Unexpected number of unselected bits %d, Expected %d", hnd.Unselected(), 0)
- }
- }
- func TestSetRollover(t *testing.T) {
- testSetRollover(t, false)
- }
- func TestSetRolloverSerial(t *testing.T) {
- testSetRollover(t, true)
- }
- func TestGetFirstAvailableFromCurrent(t *testing.T) {
- input := []struct {
- mask *sequence
- bytePos uint64
- bitPos uint64
- start uint64
- curr uint64
- end uint64
- }{
- {&sequence{block: 0xffffffff, count: 2048}, invalidPos, invalidPos, 0, 0, 65536},
- {&sequence{block: 0x0, count: 8}, 0, 0, 0, 0, 256},
- {&sequence{block: 0x80000000, count: 8}, 1, 0, 0, 8, 256},
- {&sequence{block: 0xC0000000, count: 8}, 0, 2, 0, 2, 256},
- {&sequence{block: 0xE0000000, count: 8}, 0, 3, 0, 0, 256},
- {&sequence{block: 0xFFFB1FFF, count: 8}, 2, 0, 14, 0, 256},
- {&sequence{block: 0xFFFFFFFE, count: 8}, 3, 7, 0, 0, 256},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0x00000000, count: 1, next: &sequence{block: 0xffffffff, count: 14}}}, 4, 0, 0, 32, 512},
- {&sequence{block: 0xfffeffff, count: 1, next: &sequence{block: 0xffffffff, count: 15}}, 1, 7, 0, 16, 512},
- {&sequence{block: 0xfffeffff, count: 15, next: &sequence{block: 0xffffffff, count: 1}}, 5, 7, 0, 16, 512},
- {&sequence{block: 0xfffeffff, count: 15, next: &sequence{block: 0xffffffff, count: 1}}, 9, 7, 0, 48, 512},
- {&sequence{block: 0xffffffff, count: 2, next: &sequence{block: 0xffffffef, count: 14}}, 19, 3, 0, 124, 512},
- {&sequence{block: 0xfffeffff, count: 15, next: &sequence{block: 0x0fffffff, count: 1}}, 60, 0, 0, 480, 512},
- {&sequence{block: 0xffffffff, count: 1, next: &sequence{block: 0xfffeffff, count: 14, next: &sequence{block: 0xffffffff, count: 1}}}, 17, 7, 0, 124, 512},
- {&sequence{block: 0xfffffffb, count: 1, next: &sequence{block: 0xffffffff, count: 14, next: &sequence{block: 0xffffffff, count: 1}}}, 3, 5, 0, 124, 512},
- {&sequence{block: 0xfffffffb, count: 1, next: &sequence{block: 0xfffeffff, count: 14, next: &sequence{block: 0xffffffff, count: 1}}}, 13, 7, 0, 80, 512},
- }
- for n, i := range input {
- bytePos, bitPos, _ := getAvailableFromCurrent(i.mask, i.start, i.curr, i.end)
- if bytePos != i.bytePos || bitPos != i.bitPos {
- t.Fatalf("Error in (%d) getFirstAvailable(). Expected (%d, %d). Got (%d, %d)", n, i.bytePos, i.bitPos, bytePos, bitPos)
- }
- }
- }
- func TestMarshalJSON(t *testing.T) {
- expected := []byte("hello libnetwork")
- hnd := New(uint64(len(expected) * 8))
- for i, c := range expected {
- for j := 0; j < 8; j++ {
- if c&(1<<j) == 0 {
- continue
- }
- if err := hnd.Set(uint64(i*8 + j)); err != nil {
- t.Fatal(err)
- }
- }
- }
- hstr := hnd.String()
- t.Log(hstr)
- marshaled, err := hnd.MarshalJSON()
- if err != nil {
- t.Fatalf("MarshalJSON() err = %v", err)
- }
- t.Logf("%s", marshaled)
- // Serializations of hnd as would be marshaled by versions of the code
- // found in the wild. We need to support unmarshaling old versions to
- // maintain backwards compatibility with sequences persisted on disk.
- const (
- goldenV0 = `"AAAAAAAAAIAAAAAAAAAAPRamNjYAAAAAAAAAAfYENpYAAAAAAAAAAUZ2pi4AAAAAAAAAAe72TtYAAAAAAAAAAQ=="`
- )
- if string(marshaled) != goldenV0 {
- t.Errorf("MarshalJSON() output differs from golden. Please add a new golden case to this test.")
- }
- for _, tt := range []struct {
- name string
- data []byte
- }{
- {name: "Live", data: marshaled},
- {name: "Golden-v0", data: []byte(goldenV0)},
- } {
- tt := tt
- t.Run("UnmarshalJSON="+tt.name, func(t *testing.T) {
- hnd2 := New(0)
- if err := hnd2.UnmarshalJSON(tt.data); err != nil {
- t.Errorf("UnmarshalJSON() err = %v", err)
- }
- h2str := hnd2.String()
- t.Log(h2str)
- if hstr != h2str {
- t.Errorf("Unmarshaled a different bitmap: want %q, got %q", hstr, h2str)
- }
- })
- }
- }
|