diff options
author | Christian Pointner <equinox@anytun.org> | 2017-10-08 21:58:45 +0200 |
---|---|---|
committer | Christian Pointner <equinox@anytun.org> | 2017-10-08 21:58:45 +0200 |
commit | 7be50b1aa299949f0e287a519209ccaf8078a47c (patch) | |
tree | 6075a8f38e4ecd8c94c6c47355a44ada320431d4 /satp | |
parent | found a more global place :) (diff) |
check-only for sequence window is done (needs more testing)
Diffstat (limited to 'satp')
-rw-r--r-- | satp/sequence-window.go | 107 | ||||
-rw-r--r-- | satp/sequence-window_test.go | 100 |
2 files changed, 184 insertions, 23 deletions
diff --git a/satp/sequence-window.go b/satp/sequence-window.go index 4c53ee5..c527f4e 100644 --- a/satp/sequence-window.go +++ b/satp/sequence-window.go @@ -32,9 +32,29 @@ package satp import ( "errors" + "fmt" "sync" ) +// calculate distance of seq from top and whether it is less than top +func seqDistance(top, seq uint32) (less bool, distance uint32) { + d := int32(seq - top) + if d < 0 { + return true, uint32(-d) + } + return false, uint32(d) +} + +// index will only be valid if seq is inside the window +// aka: top >= seq && (top-seq) <= window_size +// (with both conditions compensated for value wrap around) +func bitSliceIndex(top, seq uint32) int { + if top > seq { + return int(top/32) - int(seq/32) + } + return int(top/32) + int(1<<(32-5)) - int(seq/32) +} + type SequenceWindow struct { size int head uint64 @@ -42,39 +62,96 @@ type SequenceWindow struct { mtx *sync.RWMutex } +func octet2str(octet uint8) (str string) { + for i := 0; i < 8; i++ { + if (octet & 0x80) == 0 { + str += "." + } else { + str += "x" + } + octet <<= 1 + } + return +} + +func octet2str4(octets uint32) (str string) { + str += octet2str(uint8(octets>>24)) + " " + str += octet2str(uint8(octets>>16)) + " " + str += octet2str(uint8(octets>>8)) + " " + str += octet2str(uint8(octets)) + return +} + +func (w *SequenceWindow) String() string { + w.mtx.RLock() + defer w.mtx.RUnlock() + + str := fmt.Sprintf("%d/[%d]{", w.top(), w.size) + str += octet2str4(w.bitSlice(0)) + for i := 1; i <= len(w.body); i++ { + str += " " + octet2str4(w.bitSlice(i)) + } + return str + "}" +} + func (w *SequenceWindow) Size() int { return w.size } +func (w *SequenceWindow) bitSlice(idx int) uint32 { + if idx <= 0 { + // return uint32(atomic.LoadUint64(&w.head)) + return uint32(w.head) + } + // return atomic.LoadUint32(&w.body[idx-1]) + return w.body[idx-1] +} + +func (w *SequenceWindow) top() uint32 { + // return uint32(atomic.LoadUint64(&w.head) >> 32) + return uint32(w.head >> 32) +} + func (w *SequenceWindow) Top() uint32 { w.mtx.RLock() defer w.mtx.RUnlock() - // return uint32(atomic.LoadUint64(&w.head) >> 32) - return uint32(w.head >> 32) + return w.top() } -func (w *SequenceWindow) Check(sequenceNumber uint32) (bool, error) { +func (w *SequenceWindow) Check(sequenceNumber uint32) bool { if w.size <= 0 { - return false, nil + return true } w.mtx.RLock() defer w.mtx.RUnlock() - // TODO: implement this - return false, nil -} -func (w *SequenceWindow) CheckAndSet(sequenceNumber uint32) (bool, error) { - if w.size <= 0 { - return false, nil + top := w.top() + lt, d := seqDistance(top, sequenceNumber) + if lt { + if d > uint32(w.size) { + return false + } + bits := w.bitSlice(bitSliceIndex(top, sequenceNumber)) + return ((bits >> (sequenceNumber % 32)) & 1) != 1 } - w.mtx.Lock() - defer w.mtx.Unlock() - // TODO: implement this - return false, nil + return true } +// func (w *SequenceWindow) advanceTop(sequenceNumber uint32) { +// } + +// func (w *SequenceWindow) CheckAndSet(sequenceNumber uint32) bool { +// if w.size <= 0 { +// return true +// } +// w.mtx.Lock() +// defer w.mtx.Unlock() +// // TODO: implement this +// return false +// } + func NewSequenceWindow(size int, top uint32) (w *SequenceWindow, err error) { - if size < 0 { + if size < 0 || size > int(^uint32(0)/4) { return nil, errors.New("invalid sequence window size") } w = &SequenceWindow{size: size, head: uint64(top) << 32, mtx: &sync.RWMutex{}} diff --git a/satp/sequence-window_test.go b/satp/sequence-window_test.go index 2f38a23..097cacd 100644 --- a/satp/sequence-window_test.go +++ b/satp/sequence-window_test.go @@ -34,6 +34,47 @@ import ( "testing" ) +func TestSequenceWindowDistance(t *testing.T) { + testvectors := []struct { + top uint32 + seq uint32 + less bool + distance uint32 + }{ + {0, 0, false, 0}, + {1, 0, true, 1}, + {1, 1, false, 0}, + {10, 0, true, 10}, + {0, 1, false, 1}, + {0, 10, false, 10}, + {10, 10, false, 0}, + {10, 11, false, 1}, + {10, 12, false, 2}, + {0, ^uint32(0), true, 1}, + {10, ^uint32(0), true, 11}, + {^uint32(0), ^uint32(0), false, 0}, + {^uint32(0), 0, false, 1}, + {((^uint32(0)) / 2) - 1, 0, true, 2147483646}, + {((^uint32(0)) / 2), 0, true, 2147483647}, + {((^uint32(0)) / 2) + 1, 0, true, 2147483648}, + {((^uint32(0)) / 2) + 1, 1, true, 2147483647}, + {((^uint32(0)) / 2) + 1, 18, true, 2147483630}, + {((^uint32(0)) / 2) + 1, ^uint32(0), false, 2147483647}, + {((^uint32(0)) / 2) + 2, 0, false, 2147483647}, + } + + for _, vector := range testvectors { + less, distance := seqDistance(vector.top, vector.seq) + if less != vector.less { + t.Fatalf("top=%d > seq=%d is %v but should be %v", vector.top, vector.seq, less, vector.less) + } + + if distance != vector.distance { + t.Fatalf("distance between top=%d and seq=%d is %d but should be %d", vector.top, vector.seq, distance, vector.distance) + } + } +} + func TestSequenceWindowNew(t *testing.T) { testvectors := []struct { size int @@ -56,14 +97,16 @@ func TestSequenceWindowNew(t *testing.T) { {63, 0, 0, 2, true}, {64, 0, 0, 2, true}, {65, 0, 0, 3, true}, - {100, 0, 0, 4, true}, - {100, 0xFFFF0000, 0xFFFF000000000000, 4, true}, - {100, 0xFFFF0001, 0xFFFF000100000001, 4, true}, - {100, 0xFFFF0002, 0xFFFF000200000003, 4, true}, - {100, 0xFFFF0003, 0xFFFF000300000007, 4, true}, - {100, 0xFFFF0004, 0xFFFF00040000000F, 4, true}, - {100, 0xFFFF0005, 0xFFFF00050000001F, 4, true}, - {100, 0xAAAA5555, 0xAAAA5555001FFFFF, 4, true}, + {80, 0, 0, 3, true}, + {80, 0xFFFF0000, 0xFFFF000000000000, 3, true}, + {80, 0xFFFF0001, 0xFFFF000100000001, 3, true}, + {80, 0xFFFF0002, 0xFFFF000200000003, 3, true}, + {80, 0xFFFF0003, 0xFFFF000300000007, 3, true}, + {80, 0xFFFF0004, 0xFFFF00040000000F, 3, true}, + {80, 0xFFFF0005, 0xFFFF00050000001F, 3, true}, + {80, 0xAAAA5555, 0xAAAA5555001FFFFF, 3, true}, + {96, 0, 0, 3, true}, + {97, 0, 0, 4, true}, } for _, vector := range testvectors { @@ -100,5 +143,46 @@ func TestSequenceWindowNew(t *testing.T) { } } } +} + +func TestSequenceWindowCheck(t *testing.T) { + testvectors := []struct { + size int + top uint32 + seq uint32 + result bool + }{ + {0, 0, 0, true}, + {0, 0, ^uint32(0), true}, + {0, 17, 12, true}, + {10, 17, 12, false}, + {10, 17, 17, true}, + {10, 17, 18, true}, + {10, 0, ^uint32(0), false}, + {32, 0, 0, true}, + {32, 0, 12, true}, + {32, 13, 12, false}, + {32, 100, 12, false}, + {32, 33, 12, false}, + {32, 33, 32, false}, + {64, 36, 0, false}, + {64, 36, 12, false}, + {64, 36, ^uint32(0), false}, + {64, 100, ^uint32(0), false}, + {64, 100, 96, false}, + {64, 100, 95, false}, + {64, 100, 63, false}, + {64, 100, 110, true}, + } + for _, vector := range testvectors { + w, err := NewSequenceWindow(vector.size, vector.top) + if err != nil { + t.Fatal("unexpected error:", err) + } + result := w.Check(vector.seq) + if result != vector.result { + t.Fatalf("checking %d against %s returned %v but should be %v", vector.seq, w, result, vector.result) + } + } } |