aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--core/consensus.go6
-rw-r--r--core/reliable-broadcast_test.go3
-rw-r--r--core/test/blocks-generator.go5
-rw-r--r--core/test/blocks-generator_test.go15
-rw-r--r--core/test/revealer_test.go3
-rw-r--r--core/total-ordering.go499
-rw-r--r--core/total-ordering_test.go466
-rw-r--r--core/utils.go11
-rw-r--r--core/utils_test.go27
9 files changed, 592 insertions, 443 deletions
diff --git a/core/consensus.go b/core/consensus.go
index 36cd57e..6c841bf 100644
--- a/core/consensus.go
+++ b/core/consensus.go
@@ -84,10 +84,14 @@ func NewConsensus(
}
// Setup sequencer by information returned from Governace.
+ var validators types.ValidatorIDs
+ for vID := range validatorSet {
+ validators = append(validators, vID)
+ }
to := newTotalOrdering(
uint64(gov.GetTotalOrderingK()),
uint64(float32(len(validatorSet)-1)*gov.GetPhiRatio()+1),
- uint64(len(validatorSet)))
+ validators)
return &Consensus{
rbModule: rb,
diff --git a/core/reliable-broadcast_test.go b/core/reliable-broadcast_test.go
index c6e9400..28edda7 100644
--- a/core/reliable-broadcast_test.go
+++ b/core/reliable-broadcast_test.go
@@ -514,7 +514,8 @@ func (s *ReliableBroadcastTest) TestRandomlyGeneratedBlocks() {
}
}()
gen := test.NewBlocksGenerator(nil, hashBlock)
- s.Require().Nil(gen.Generate(validatorCount, blockCount, nil, db))
+ _, err = gen.Generate(validatorCount, blockCount, nil, db)
+ s.Require().Nil(err)
iter, err := db.GetAll()
s.Require().Nil(err)
// Setup a revealer that would reveal blocks randomly.
diff --git a/core/test/blocks-generator.go b/core/test/blocks-generator.go
index 3cd97ee..b05d08f 100644
--- a/core/test/blocks-generator.go
+++ b/core/test/blocks-generator.go
@@ -236,7 +236,8 @@ func (gen *BlocksGenerator) Generate(
validatorCount int,
blockCount int,
ackingCountGenerator func() int,
- writer blockdb.Writer) (err error) {
+ writer blockdb.Writer) (
+ validators types.ValidatorIDs, err error) {
if ackingCountGenerator == nil {
ackingCountGenerator = normalAckingCountGenerator(
@@ -244,7 +245,7 @@ func (gen *BlocksGenerator) Generate(
float64(validatorCount/2),
float64(validatorCount/4+1))
}
- validators := []types.ValidatorID{}
+ validators = types.ValidatorIDs{}
for i := 0; i < validatorCount; i++ {
validators = append(
validators, types.ValidatorID{Hash: common.NewRandomHash()})
diff --git a/core/test/blocks-generator_test.go b/core/test/blocks-generator_test.go
index 43e994f..5c85fbd 100644
--- a/core/test/blocks-generator_test.go
+++ b/core/test/blocks-generator_test.go
@@ -39,9 +39,10 @@ func (s *BlocksGeneratorTestCase) TestGenerate() {
db, err := blockdb.NewMemBackedBlockDB()
s.Require().Nil(err)
- err = gen.Generate(
+ validators, err := gen.Generate(
validatorCount, blockCount, nil, db)
s.Require().Nil(err)
+ s.Require().Len(validators, validatorCount)
// Load all blocks in that database for further checking.
iter, err := db.GetAll()
@@ -114,8 +115,10 @@ func (s *BlocksGeneratorTestCase) TestGenerateWithMaxAckCount() {
// Generate with 0 acks.
db, err := blockdb.NewMemBackedBlockDB()
req.Nil(err)
- req.Nil(gen.Generate(
- validatorCount, blockCount, MaxAckingCountGenerator(0), db))
+ validators, err := gen.Generate(
+ validatorCount, blockCount, MaxAckingCountGenerator(0), db)
+ req.Nil(err)
+ req.Len(validators, validatorCount)
// Load blocks to check their acking count.
iter, err := db.GetAll()
req.Nil(err)
@@ -134,9 +137,11 @@ func (s *BlocksGeneratorTestCase) TestGenerateWithMaxAckCount() {
// Generate with acks as many as possible.
db, err = blockdb.NewMemBackedBlockDB()
req.Nil(err)
- req.Nil(gen.Generate(
+ validators, err = gen.Generate(
validatorCount, blockCount, MaxAckingCountGenerator(
- validatorCount), db))
+ validatorCount), db)
+ req.Nil(err)
+ req.Len(validators, validatorCount)
// Load blocks to verify the average acking count.
totalAckingCount := 0
totalBlockCount := 0
diff --git a/core/test/revealer_test.go b/core/test/revealer_test.go
index 8087136..032cab3 100644
--- a/core/test/revealer_test.go
+++ b/core/test/revealer_test.go
@@ -45,9 +45,10 @@ func (s *RevealerTestSuite) SetupSuite() {
// Randomly generate blocks.
gen := NewBlocksGenerator(nil, stableRandomHash)
- err = gen.Generate(
+ validators, err := gen.Generate(
validatorCount, blockCount, nil, s.db)
s.Require().Nil(err)
+ s.Require().Len(validators, validatorCount)
// Cache the count of total generated block.
iter, err := s.db.GetAll()
diff --git a/core/total-ordering.go b/core/total-ordering.go
index c7270c5..1edccdf 100644
--- a/core/total-ordering.go
+++ b/core/total-ordering.go
@@ -31,22 +31,45 @@ const (
infinity uint64 = math.MaxUint64
)
-// ErrNotValidDAG would be reported when block subbmitted to totalOrdering
-// didn't form a DAG.
-var ErrNotValidDAG = fmt.Errorf("not a valid dag")
+var (
+ // ErrNotValidDAG would be reported when block subbmitted to totalOrdering
+ // didn't form a DAG.
+ ErrNotValidDAG = fmt.Errorf("not a valid dag")
+ // ErrValidatorNotRecognized means the validator is unknown to this module.
+ ErrValidatorNotRecognized = fmt.Errorf("validator not recognized")
+)
// totalOrderinWinRecord caches which validators this candidate
// wins another one based on their height vector.
-type totalOrderingWinRecord map[types.ValidatorID]struct{}
+type totalOrderingWinRecord struct {
+ wins []int8
+ count uint
+}
+
+func (rec *totalOrderingWinRecord) reset() {
+ rec.count = 0
+ for idx := range rec.wins {
+ rec.wins[idx] = 0
+ }
+}
+
+func newTotalOrderingWinRecord(validatorCount int) (
+ rec *totalOrderingWinRecord) {
+
+ rec = &totalOrderingWinRecord{}
+ rec.reset()
+ rec.wins = make([]int8, validatorCount)
+ return
+}
// grade implements the 'grade' potential function described in white paper.
-func (rec totalOrderingWinRecord) grade(
+func (rec *totalOrderingWinRecord) grade(
validatorCount, phi uint64,
globalAnsLength uint64) int {
- if uint64(len(rec)) >= phi {
+ if uint64(rec.count) >= phi {
return 1
- } else if uint64(len(rec)) < phi-validatorCount+globalAnsLength {
+ } else if uint64(rec.count) < phi-validatorCount+globalAnsLength {
return 0
} else {
return -1
@@ -66,38 +89,44 @@ type totalOrderingHeightRecord struct{ minHeight, count uint64 }
// However, to reuse a map, we have no easy way to erase its content but
// iterating its keys and delete corresponding values.
type totalOrderingObjectCache struct {
- ackedStatus []map[types.ValidatorID]*totalOrderingHeightRecord
- winRecordContainers []map[common.Hash]totalOrderingWinRecord
- heightVectors []map[types.ValidatorID]uint64
+ ackedStatus [][]*totalOrderingHeightRecord
+ heightVectors [][]uint64
+ winRecordContainers [][]*totalOrderingWinRecord
ackedVectors []map[common.Hash]struct{}
winRecordPool sync.Pool
+ validatorCount int
}
// newTotalOrderingObjectCache constructs an totalOrderingObjectCache
// instance.
-func newTotalOrderingObjectCache() *totalOrderingObjectCache {
+func newTotalOrderingObjectCache(validatorCount int) *totalOrderingObjectCache {
return &totalOrderingObjectCache{
winRecordPool: sync.Pool{
New: func() interface{} {
- return make(totalOrderingWinRecord)
+ return newTotalOrderingWinRecord(validatorCount)
},
},
+ validatorCount: validatorCount,
}
}
// requestAckedStatus requests a structure to record acking status of one
// candidate (or a global view of acking status of pending set).
func (cache *totalOrderingObjectCache) requestAckedStatus() (
- acked map[types.ValidatorID]*totalOrderingHeightRecord) {
+ acked []*totalOrderingHeightRecord) {
if len(cache.ackedStatus) == 0 {
- acked = make(map[types.ValidatorID]*totalOrderingHeightRecord)
+ acked = make([]*totalOrderingHeightRecord, cache.validatorCount)
+ for idx := range acked {
+ acked[idx] = &totalOrderingHeightRecord{count: 0}
+ }
} else {
acked, cache.ackedStatus =
cache.ackedStatus[len(cache.ackedStatus)-1],
cache.ackedStatus[:len(cache.ackedStatus)-1]
- for k := range acked {
- delete(acked, k)
+ // Reset acked status.
+ for idx := range acked {
+ acked[idx].count = 0
}
}
return
@@ -105,43 +134,44 @@ func (cache *totalOrderingObjectCache) requestAckedStatus() (
// recycleAckedStatys recycles the structure to record acking status.
func (cache *totalOrderingObjectCache) recycleAckedStatus(
- acked map[types.ValidatorID]*totalOrderingHeightRecord) {
+ acked []*totalOrderingHeightRecord) {
cache.ackedStatus = append(cache.ackedStatus, acked)
}
// requestWinRecord requests an totalOrderingWinRecord instance.
func (cache *totalOrderingObjectCache) requestWinRecord() (
- win totalOrderingWinRecord) {
+ win *totalOrderingWinRecord) {
- win = cache.winRecordPool.Get().(totalOrderingWinRecord)
- for k := range win {
- delete(win, k)
- }
+ win = cache.winRecordPool.Get().(*totalOrderingWinRecord)
+ win.reset()
return
}
// recycleWinRecord recycles an totalOrderingWinRecord instance.
func (cache *totalOrderingObjectCache) recycleWinRecord(
- win totalOrderingWinRecord) {
+ win *totalOrderingWinRecord) {
+ if win == nil {
+ return
+ }
cache.winRecordPool.Put(win)
}
// requestHeightVector requests a structure to record acking heights
// of one candidate.
func (cache *totalOrderingObjectCache) requestHeightVector() (
- hv map[types.ValidatorID]uint64) {
+ hv []uint64) {
if len(cache.heightVectors) == 0 {
- hv = make(map[types.ValidatorID]uint64)
+ hv = make([]uint64, cache.validatorCount)
} else {
hv, cache.heightVectors =
cache.heightVectors[len(cache.heightVectors)-1],
cache.heightVectors[:len(cache.heightVectors)-1]
- for k := range hv {
- delete(hv, k)
- }
+ }
+ for idx := range hv {
+ hv[idx] = infinity
}
return
}
@@ -149,23 +179,23 @@ func (cache *totalOrderingObjectCache) requestHeightVector() (
// recycleHeightVector recycles an instance to record acking heights
// of one candidate.
func (cache *totalOrderingObjectCache) recycleHeightVector(
- hv map[types.ValidatorID]uint64) {
+ hv []uint64) {
cache.heightVectors = append(cache.heightVectors, hv)
}
// requestWinRecordContainer requests a map of totalOrderingWinRecord.
func (cache *totalOrderingObjectCache) requestWinRecordContainer() (
- con map[common.Hash]totalOrderingWinRecord) {
+ con []*totalOrderingWinRecord) {
if len(cache.winRecordContainers) == 0 {
- con = make(map[common.Hash]totalOrderingWinRecord)
+ con = make([]*totalOrderingWinRecord, cache.validatorCount)
} else {
con, cache.winRecordContainers =
cache.winRecordContainers[len(cache.winRecordContainers)-1],
cache.winRecordContainers[:len(cache.winRecordContainers)-1]
- for k := range con {
- delete(con, k)
+ for idx := range con {
+ con[idx] = nil
}
}
return
@@ -173,7 +203,7 @@ func (cache *totalOrderingObjectCache) requestWinRecordContainer() (
// recycleWinRecordContainer recycles a map of totalOrderingWinRecord.
func (cache *totalOrderingObjectCache) recycleWinRecordContainer(
- con map[common.Hash]totalOrderingWinRecord) {
+ con []*totalOrderingWinRecord) {
cache.winRecordContainers = append(cache.winRecordContainers, con)
}
@@ -221,26 +251,29 @@ func (cache *totalOrderingObjectCache) recycleAckedVector(
// - count of acking blocks from that proposer
// to repsent the acking status for block A.
type totalOrderingCandidateInfo struct {
- ackedStatus map[types.ValidatorID]*totalOrderingHeightRecord
- cachedHeightVector map[types.ValidatorID]uint64
- winRecords map[common.Hash]totalOrderingWinRecord
+ ackedStatus []*totalOrderingHeightRecord
+ cachedHeightVector []uint64
+ winRecords []*totalOrderingWinRecord
+ hash common.Hash
}
// newTotalOrderingCandidateInfo constructs an totalOrderingCandidateInfo
// instance.
func newTotalOrderingCandidateInfo(
+ candidateHash common.Hash,
objCache *totalOrderingObjectCache) *totalOrderingCandidateInfo {
return &totalOrderingCandidateInfo{
ackedStatus: objCache.requestAckedStatus(),
winRecords: objCache.requestWinRecordContainer(),
+ hash: candidateHash,
}
}
// clean clear information related to another candidate, which should be called
// when that candidate is selected as deliver set.
-func (v *totalOrderingCandidateInfo) clean(otherCandidate common.Hash) {
- delete(v.winRecords, otherCandidate)
+func (v *totalOrderingCandidateInfo) clean(otherCandidateIndex int) {
+ v.winRecords[otherCandidateIndex] = nil
}
// recycle objects for later usage, this eases the loading of
@@ -262,13 +295,13 @@ func (v *totalOrderingCandidateInfo) recycle(
// addBlock would update totalOrderingCandidateInfo, it's caller's duty
// to make sure the input block acutally acking the target block.
-func (v *totalOrderingCandidateInfo) addBlock(b *types.Block) (err error) {
- rec, exists := v.ackedStatus[b.ProposerID]
- if !exists {
- v.ackedStatus[b.ProposerID] = &totalOrderingHeightRecord{
- minHeight: b.Height,
- count: 1,
- }
+func (v *totalOrderingCandidateInfo) addBlock(
+ b *types.Block, proposerIndex int) (err error) {
+
+ rec := v.ackedStatus[proposerIndex]
+ if rec.count == 0 {
+ rec.minHeight = b.Height
+ rec.count = 1
} else {
if b.Height < rec.minHeight {
err = ErrNotValidDAG
@@ -294,17 +327,15 @@ func (v *totalOrderingCandidateInfo) getAckingNodeSetLength(
global *totalOrderingCandidateInfo,
k uint64) (count uint64) {
- var (
- rec *totalOrderingHeightRecord
- exists bool
- )
-
- for vID, gRec := range global.ackedStatus {
- rec, exists = v.ackedStatus[vID]
- if !exists {
+ var rec *totalOrderingHeightRecord
+ for idx, gRec := range global.ackedStatus {
+ if gRec.count == 0 {
+ continue
+ }
+ rec = v.ackedStatus[idx]
+ if rec.count == 0 {
continue
}
-
// This line would check if these two ranges would overlap:
// - (global minimum height + k, infinity)
// - (local minimum height, local minimum height + count - 1)
@@ -322,13 +353,12 @@ func (v *totalOrderingCandidateInfo) getAckingNodeSetLength(
func (v *totalOrderingCandidateInfo) updateAckingHeightVector(
global *totalOrderingCandidateInfo,
k uint64,
- dirtyValidators types.ValidatorIDs,
+ dirtyValidatorIndexes []int,
objCache *totalOrderingObjectCache) {
var (
- vID types.ValidatorID
+ idx int
gRec, rec *totalOrderingHeightRecord
- exists bool
)
// The reason not to merge the two loops is the iteration over map
@@ -339,42 +369,39 @@ func (v *totalOrderingCandidateInfo) updateAckingHeightVector(
if v.cachedHeightVector == nil {
// Generate height vector from scratch.
v.cachedHeightVector = objCache.requestHeightVector()
- for vID, gRec = range global.ackedStatus {
+ for idx, gRec = range global.ackedStatus {
if gRec.count <= k {
- delete(v.cachedHeightVector, vID)
continue
}
- rec, exists = v.ackedStatus[vID]
- if !exists {
- v.cachedHeightVector[vID] = infinity
+ rec = v.ackedStatus[idx]
+ if rec.count == 0 {
+ v.cachedHeightVector[idx] = infinity
} else if rec.minHeight <= gRec.minHeight+k {
// This check is sufficient to make sure the block height:
//
// gRec.minHeight + k
//
// would be included in this totalOrderingCandidateInfo.
- v.cachedHeightVector[vID] = gRec.minHeight + k
+ v.cachedHeightVector[idx] = gRec.minHeight + k
} else {
- v.cachedHeightVector[vID] = infinity
+ v.cachedHeightVector[idx] = infinity
}
}
} else {
// Return the cached one, only update dirty fields.
- for _, vID = range dirtyValidators {
- gRec, exists = global.ackedStatus[vID]
- if !exists {
+ for _, idx = range dirtyValidatorIndexes {
+ gRec = global.ackedStatus[idx]
+ if gRec.count == 0 || gRec.count <= k {
+ v.cachedHeightVector[idx] = infinity
continue
}
- rec, exists = v.ackedStatus[vID]
- if gRec.count <= k {
- delete(v.cachedHeightVector, vID)
- continue
- } else if !exists {
- v.cachedHeightVector[vID] = infinity
+ rec = v.ackedStatus[idx]
+ if rec.count == 0 {
+ v.cachedHeightVector[idx] = infinity
} else if rec.minHeight <= gRec.minHeight+k {
- v.cachedHeightVector[vID] = gRec.minHeight + k
+ v.cachedHeightVector[idx] = gRec.minHeight + k
} else {
- v.cachedHeightVector[vID] = infinity
+ v.cachedHeightVector[idx] = infinity
}
}
}
@@ -383,15 +410,14 @@ func (v *totalOrderingCandidateInfo) updateAckingHeightVector(
// updateWinRecord setup win records between two candidates.
func (v *totalOrderingCandidateInfo) updateWinRecord(
- otherCandidate common.Hash,
+ otherCandidateIndex int,
other *totalOrderingCandidateInfo,
- dirtyValidators types.ValidatorIDs,
+ dirtyValidatorIndexes []int,
objCache *totalOrderingObjectCache) {
var (
- vID types.ValidatorID
- hTo, hFrom uint64
- exists bool
+ idx int
+ height uint64
)
// The reason not to merge the two loops is the iteration over map
@@ -399,35 +425,38 @@ func (v *totalOrderingCandidateInfo) updateWinRecord(
// validators is cheaper.
// TODO(mission): merge the code in this if/else if add a function won't
// affect the performance.
- win, exists := v.winRecords[otherCandidate]
- if !exists {
+ win := v.winRecords[otherCandidateIndex]
+ if win == nil {
win = objCache.requestWinRecord()
- v.winRecords[otherCandidate] = win
- for vID, hFrom = range v.cachedHeightVector {
- hTo, exists = other.cachedHeightVector[vID]
- if !exists {
+ v.winRecords[otherCandidateIndex] = win
+ for idx, height = range v.cachedHeightVector {
+ if height == infinity {
continue
}
- if hFrom != infinity && hTo == infinity {
- win[vID] = struct{}{}
+ if other.cachedHeightVector[idx] == infinity {
+ win.wins[idx] = 1
+ win.count++
}
}
} else {
- for _, vID = range dirtyValidators {
- hFrom, exists = v.cachedHeightVector[vID]
- if !exists {
- delete(win, vID)
- return
- }
- hTo, exists = other.cachedHeightVector[vID]
- if !exists {
- delete(win, vID)
- return
+ for _, idx = range dirtyValidatorIndexes {
+ if v.cachedHeightVector[idx] == infinity {
+ if win.wins[idx] == 1 {
+ win.wins[idx] = 0
+ win.count--
+ }
+ continue
}
- if hFrom != infinity && hTo == infinity {
- win[vID] = struct{}{}
+ if other.cachedHeightVector[idx] == infinity {
+ if win.wins[idx] == 0 {
+ win.wins[idx] = 1
+ win.count++
+ }
} else {
- delete(win, vID)
+ if win.wins[idx] == 1 {
+ win.wins[idx] = 0
+ win.count--
+ }
}
}
}
@@ -438,22 +467,26 @@ type totalOrderingGlobalVector struct {
// blocks stores all blocks grouped by their proposers and
// sorted by their block height.
//
- // TODO: the way we use this slice would make it reallocate frequently.
- blocks map[types.ValidatorID][]*types.Block
+ // TODO(mission): the way we use this slice would make it reallocate frequently.
+ blocks [][]*types.Block
// cachedCandidateInfo is an totalOrderingCandidateInfo instance,
// which is just used for actual candidates to calculate height vector.
cachedCandidateInfo *totalOrderingCandidateInfo
}
-func newTotalOrderingGlobalVector() *totalOrderingGlobalVector {
+func newTotalOrderingGlobalVector(
+ validatorCount int) *totalOrderingGlobalVector {
+
return &totalOrderingGlobalVector{
- blocks: make(map[types.ValidatorID][]*types.Block),
+ blocks: make([][]*types.Block, validatorCount),
}
}
-func (global *totalOrderingGlobalVector) addBlock(b *types.Block) (err error) {
- blocksFromProposer := global.blocks[b.ProposerID]
+func (global *totalOrderingGlobalVector) addBlock(
+ b *types.Block, proposerIndex int) (err error) {
+
+ blocksFromProposer := global.blocks[proposerIndex]
if len(blocksFromProposer) > 0 {
lastBlock := blocksFromProposer[len(blocksFromProposer)-1]
if b.Height-lastBlock.Height != 1 {
@@ -461,44 +494,43 @@ func (global *totalOrderingGlobalVector) addBlock(b *types.Block) (err error) {
return
}
}
- global.blocks[b.ProposerID] = append(blocksFromProposer, b)
+ global.blocks[proposerIndex] = append(blocksFromProposer, b)
return
}
// updateCandidateInfo udpate cached candidate info.
func (global *totalOrderingGlobalVector) updateCandidateInfo(
- dirtyValidators types.ValidatorIDs, objCache *totalOrderingObjectCache) {
+ dirtyValidatorIndexes []int, objCache *totalOrderingObjectCache) {
var (
- vID types.ValidatorID
+ idx int
blocks []*types.Block
info *totalOrderingCandidateInfo
+ rec *totalOrderingHeightRecord
)
if global.cachedCandidateInfo == nil {
- info = newTotalOrderingCandidateInfo(objCache)
- for vID, blocks = range global.blocks {
+ info = newTotalOrderingCandidateInfo(common.Hash{}, objCache)
+ for idx, blocks = range global.blocks {
if len(blocks) == 0 {
continue
}
- info.ackedStatus[vID] = &totalOrderingHeightRecord{
- minHeight: blocks[0].Height,
- count: uint64(len(blocks)),
- }
+ rec = info.ackedStatus[idx]
+ rec.minHeight = blocks[0].Height
+ rec.count = uint64(len(blocks))
}
global.cachedCandidateInfo = info
} else {
info = global.cachedCandidateInfo
- for _, vID = range dirtyValidators {
- blocks = global.blocks[vID]
+ for _, idx = range dirtyValidatorIndexes {
+ blocks = global.blocks[idx]
if len(blocks) == 0 {
- delete(info.ackedStatus, vID)
+ info.ackedStatus[idx].count = 0
continue
}
- info.ackedStatus[vID] = &totalOrderingHeightRecord{
- minHeight: blocks[0].Height,
- count: uint64(len(blocks)),
- }
+ rec = info.ackedStatus[idx]
+ rec.minHeight = blocks[0].Height
+ rec.count = uint64(len(blocks))
}
}
return
@@ -531,31 +563,55 @@ type totalOrdering struct {
// candidates caches result of potential function during generating
// preceding sets.
- candidates map[common.Hash]*totalOrderingCandidateInfo
+ candidates []*totalOrderingCandidateInfo
// acked cache the 'block A acked by block B' relation by
// keeping a record in acked[A.Hash][B.Hash]
acked map[common.Hash]map[common.Hash]struct{}
- // dirtyValidators records which validatorID that should be updated for
- // all cached status (win record, acking status).
- dirtyValidators types.ValidatorIDs
+ // dirtyValidatorIndexes records which validatorID that should be updated
+ // for all cached status (win record, acking status).
+ dirtyValidatorIndexes []int
// objCache caches allocated objects, like map.
objCache *totalOrderingObjectCache
+
+ // validatorIndexMapping maps validatorID to an unique integer, which
+ // could be used as slice index.
+ validatorIndexMapping map[types.ValidatorID]int
+
+ // candidateIndexMapping maps block hashes of candidates to an unique
+ // integer, which could be used as slice index.
+ candidateIndexMapping map[common.Hash]int
+
+ // allocatedCandidateSlotIndexes records all used slot indexes in
+ // candidates slice.
+ allocatedCandidateSlotIndexes []int
}
-func newTotalOrdering(k, phi, validatorCount uint64) *totalOrdering {
+func newTotalOrdering(
+ k, phi uint64, validators types.ValidatorIDs) *totalOrdering {
+
+ // Setup validatorID to index mapping.
+ validatorIndexMapping := make(map[types.ValidatorID]int)
+ for _, vID := range validators {
+ validatorIndexMapping[vID] = len(validatorIndexMapping)
+ }
+ validatorCount := len(validators)
return &totalOrdering{
- candidates: make(map[common.Hash]*totalOrderingCandidateInfo),
- pendings: make(map[common.Hash]*types.Block),
- k: k,
- phi: phi,
- validatorCount: validatorCount,
- globalVector: newTotalOrderingGlobalVector(),
- dirtyValidators: make(types.ValidatorIDs, 0, int(validatorCount)),
- acked: make(map[common.Hash]map[common.Hash]struct{}),
- objCache: newTotalOrderingObjectCache(),
+ pendings: make(map[common.Hash]*types.Block),
+ k: k,
+ phi: phi,
+ validatorCount: uint64(validatorCount),
+ globalVector: newTotalOrderingGlobalVector(validatorCount),
+ dirtyValidatorIndexes: make([]int, 0, validatorCount),
+ acked: make(map[common.Hash]map[common.Hash]struct{}),
+ objCache: newTotalOrderingObjectCache(validatorCount),
+ validatorIndexMapping: validatorIndexMapping,
+ candidateIndexMapping: make(map[common.Hash]int),
+ candidates: make(
+ []*totalOrderingCandidateInfo, validatorCount),
+ allocatedCandidateSlotIndexes: make([]int, 0, validatorCount),
}
}
@@ -601,32 +657,41 @@ func (to *totalOrdering) clean(h common.Hash) {
to.objCache.recycleAckedVector(to.acked[h])
delete(to.acked, h)
delete(to.pendings, h)
- to.candidates[h].recycle(to.objCache)
- delete(to.candidates, h)
- for _, info := range to.candidates {
- info.clean(h)
+ slotIndex := to.candidateIndexMapping[h]
+ to.candidates[slotIndex].recycle(to.objCache)
+ to.candidates[slotIndex] = nil
+ delete(to.candidateIndexMapping, h)
+ // Remove this candidate from allocated slot indexes.
+ to.allocatedCandidateSlotIndexes = removeFromSortedIntSlice(
+ to.allocatedCandidateSlotIndexes, slotIndex)
+ // Clear records of this candidate from other candidates.
+ for _, idx := range to.allocatedCandidateSlotIndexes {
+ to.candidates[idx].clean(slotIndex)
}
}
// updateVectors is a helper function to update all cached vectors.
-func (to *totalOrdering) updateVectors(b *types.Block) (err error) {
+func (to *totalOrdering) updateVectors(
+ b *types.Block, proposerIndex int) (err error) {
var (
- candidate common.Hash
- info *totalOrderingCandidateInfo
- acked bool
+ candidateHash common.Hash
+ candidateIndex int
+ acked bool
)
// Update global height vector
- err = to.globalVector.addBlock(b)
+ err = to.globalVector.addBlock(b, proposerIndex)
if err != nil {
return
}
// Update acking status of candidates.
- for candidate, info = range to.candidates {
- if _, acked = to.acked[candidate][b.Hash]; !acked {
+ for candidateHash, candidateIndex = range to.candidateIndexMapping {
+ if _, acked = to.acked[candidateHash][b.Hash]; !acked {
continue
}
- if err = info.addBlock(b); err != nil {
+ if err = to.candidates[candidateIndex].addBlock(
+ b, proposerIndex); err != nil {
+
return
}
}
@@ -636,20 +701,32 @@ func (to *totalOrdering) updateVectors(b *types.Block) (err error) {
// prepareCandidate is a helper function to
// build totalOrderingCandidateInfo for new candidate.
func (to *totalOrdering) prepareCandidate(
- candidate *types.Block) (info *totalOrderingCandidateInfo) {
+ candidate *types.Block, proposerIndex int) {
+
+ var (
+ info = newTotalOrderingCandidateInfo(
+ candidate.Hash, to.objCache)
+ )
+
+ to.candidates[proposerIndex] = info
+ to.candidateIndexMapping[candidate.Hash] = proposerIndex
+ // Add index to slot to allocated list, make sure the modified list sorted.
+ to.allocatedCandidateSlotIndexes = append(
+ to.allocatedCandidateSlotIndexes, proposerIndex)
+ sort.Ints(to.allocatedCandidateSlotIndexes)
- info = newTotalOrderingCandidateInfo(to.objCache)
- info.ackedStatus[candidate.ProposerID] = &totalOrderingHeightRecord{
+ info.ackedStatus[proposerIndex] = &totalOrderingHeightRecord{
minHeight: candidate.Height,
- count: uint64(len(to.globalVector.blocks[candidate.ProposerID])),
+ count: uint64(len(to.globalVector.blocks[proposerIndex])),
}
ackedsForCandidate, exists := to.acked[candidate.Hash]
if !exists {
// This candidate is acked by nobody.
return
}
- for vID, blocks := range to.globalVector.blocks {
- if vID == candidate.ProposerID {
+ var rec *totalOrderingHeightRecord
+ for idx, blocks := range to.globalVector.blocks {
+ if idx == proposerIndex {
continue
}
for i, b := range blocks {
@@ -658,10 +735,9 @@ func (to *totalOrdering) prepareCandidate(
}
// If this block acks this candidate, all newer blocks
// from the same validator also 'indirect' acks it.
- info.ackedStatus[vID] = &totalOrderingHeightRecord{
- minHeight: b.Height,
- count: uint64(len(blocks) - i),
- }
+ rec = info.ackedStatus[idx]
+ rec.minHeight = b.Height
+ rec.count = uint64(len(blocks) - i)
break
}
}
@@ -685,32 +761,40 @@ func (to *totalOrdering) output(precedings map[common.Hash]struct{}) (ret []*typ
for p := range precedings {
// Remove the first element from corresponding blockVector.
b := to.pendings[p]
- to.globalVector.blocks[b.ProposerID] =
- to.globalVector.blocks[b.ProposerID][1:]
+ // TODO(mission): This way to use slice makes it reallocate frequently.
+ blockProposerIndex := to.validatorIndexMapping[b.ProposerID]
+ to.globalVector.blocks[blockProposerIndex] =
+ to.globalVector.blocks[blockProposerIndex][1:]
ret = append(ret, b)
// Remove block relations.
to.clean(p)
- to.dirtyValidators = append(to.dirtyValidators, b.ProposerID)
+ to.dirtyValidatorIndexes = append(
+ to.dirtyValidatorIndexes, blockProposerIndex)
}
sort.Sort(types.ByHash(ret))
// Find new candidates from tip of globalVector of each validator.
// The complexity here is O(N^2logN).
+ // TODO(mission): only those tips that acking some blocks in
+ // the devliered set should be checked. This
+ // improvment related to the latency introduced by K.
for _, blocks := range to.globalVector.blocks {
if len(blocks) == 0 {
continue
}
tip := blocks[0]
if _, alreadyCandidate :=
- to.candidates[tip.Hash]; alreadyCandidate {
+ to.candidateIndexMapping[tip.Hash]; alreadyCandidate {
continue
}
if !to.isAckOnlyPrecedings(tip) {
continue
}
// Build totalOrderingCandidateInfo for new candidate.
- to.candidates[tip.Hash] = to.prepareCandidate(tip)
+ to.prepareCandidate(
+ tip,
+ to.validatorIndexMapping[tip.ProposerID])
}
return ret
}
@@ -722,52 +806,61 @@ func (to *totalOrdering) generateDeliverSet() (
delivered map[common.Hash]struct{}, early bool) {
var (
- candidate, otherCandidate common.Hash
- info, otherInfo *totalOrderingCandidateInfo
- precedings = make(map[common.Hash]struct{})
+ candidateIndex, otherCandidateIndex int
+ info, otherInfo *totalOrderingCandidateInfo
+ precedings = make(map[int]struct{})
)
- to.globalVector.updateCandidateInfo(to.dirtyValidators, to.objCache)
+ to.globalVector.updateCandidateInfo(to.dirtyValidatorIndexes, to.objCache)
globalInfo := to.globalVector.cachedCandidateInfo
- for _, info = range to.candidates {
- info.updateAckingHeightVector(
- globalInfo, to.k, to.dirtyValidators, to.objCache)
+ for _, candidateIndex = range to.allocatedCandidateSlotIndexes {
+ to.candidates[candidateIndex].updateAckingHeightVector(
+ globalInfo, to.k, to.dirtyValidatorIndexes, to.objCache)
}
// Update winning records for each candidate.
+ // TODO(mission): It's not reasonable to
+ // request one routine for each candidate, the context
+ // switch rate would be high.
var wg sync.WaitGroup
- wg.Add(len(to.candidates))
- for candidate, info := range to.candidates {
- go func(can common.Hash, canInfo *totalOrderingCandidateInfo) {
- for otherCandidate, otherInfo := range to.candidates {
- if can == otherCandidate {
+ wg.Add(len(to.allocatedCandidateSlotIndexes))
+ for _, candidateIndex := range to.allocatedCandidateSlotIndexes {
+ info = to.candidates[candidateIndex]
+ go func(can int, canInfo *totalOrderingCandidateInfo) {
+ for _, otherCandidateIndex := range to.allocatedCandidateSlotIndexes {
+ if can == otherCandidateIndex {
continue
}
canInfo.updateWinRecord(
- otherCandidate, otherInfo, to.dirtyValidators, to.objCache)
+ otherCandidateIndex,
+ to.candidates[otherCandidateIndex],
+ to.dirtyValidatorIndexes,
+ to.objCache)
}
wg.Done()
- }(candidate, info)
+ }(candidateIndex, info)
}
wg.Wait()
// Reset dirty validators.
- to.dirtyValidators = to.dirtyValidators[:0]
+ to.dirtyValidatorIndexes = to.dirtyValidatorIndexes[:0]
globalAnsLength := globalInfo.getAckingNodeSetLength(globalInfo, to.k)
CheckNextCandidateLoop:
- for candidate = range to.candidates {
- for otherCandidate, otherInfo = range to.candidates {
- if candidate == otherCandidate {
+ for _, candidateIndex = range to.allocatedCandidateSlotIndexes {
+ info = to.candidates[candidateIndex]
+ for _, otherCandidateIndex = range to.allocatedCandidateSlotIndexes {
+ if candidateIndex == otherCandidateIndex {
continue
}
- if otherInfo.winRecords[candidate].grade(
+ otherInfo = to.candidates[otherCandidateIndex]
+ if otherInfo.winRecords[candidateIndex].grade(
to.validatorCount, to.phi, globalAnsLength) != 0 {
continue CheckNextCandidateLoop
}
}
- precedings[candidate] = struct{}{}
+ precedings[candidateIndex] = struct{}{}
}
if len(precedings) == 0 {
return
@@ -777,15 +870,15 @@ CheckNextCandidateLoop:
internal := func() bool {
var (
isPreceding, beaten bool
- p common.Hash
+ p int
)
- for candidate = range to.candidates {
- if _, isPreceding = precedings[candidate]; isPreceding {
+ for _, candidateIndex = range to.allocatedCandidateSlotIndexes {
+ if _, isPreceding = precedings[candidateIndex]; isPreceding {
continue
}
beaten = false
for p = range precedings {
- if beaten = to.candidates[p].winRecords[candidate].grade(
+ if beaten = to.candidates[p].winRecords[candidateIndex].grade(
to.validatorCount, to.phi, globalAnsLength) == 1; beaten {
break
}
@@ -802,15 +895,13 @@ CheckNextCandidateLoop:
// to lead the whole preceding set.
checkAHV := func() bool {
var (
- height uint64
- p common.Hash
- count uint64
- status *totalOrderingCandidateInfo
+ height, count uint64
+ p int
)
for p = range precedings {
count = 0
- status = to.candidates[p]
- for _, height = range status.cachedHeightVector {
+ info = to.candidates[p]
+ for _, height = range info.cachedHeightVector {
if height != infinity {
count++
if count > to.phi {
@@ -853,7 +944,10 @@ CheckNextCandidateLoop:
return
}
}
- delivered = precedings
+ delivered = make(map[common.Hash]struct{})
+ for p := range precedings {
+ delivered[to.candidates[p].hash] = struct{}{}
+ }
return
}
@@ -864,16 +958,23 @@ func (to *totalOrdering) processBlock(b *types.Block) (
// That means, all its acking blocks are during/after
// total ordering stage.
+ blockProposerIndex, exists := to.validatorIndexMapping[b.ProposerID]
+ if !exists {
+ err = ErrValidatorNotRecognized
+ return
+ }
+
to.pendings[b.Hash] = b
to.buildBlockRelation(b)
- if err = to.updateVectors(b); err != nil {
+ if err = to.updateVectors(b, blockProposerIndex); err != nil {
return
}
if to.isAckOnlyPrecedings(b) {
- to.candidates[b.Hash] = to.prepareCandidate(b)
+ to.prepareCandidate(b, blockProposerIndex)
}
// Mark the proposer of incoming block as dirty.
- to.dirtyValidators = append(to.dirtyValidators, b.ProposerID)
+ to.dirtyValidatorIndexes = append(
+ to.dirtyValidatorIndexes, blockProposerIndex)
hashes, early := to.generateDeliverSet()
// output precedings
diff --git a/core/total-ordering_test.go b/core/total-ordering_test.go
index 9fb14e7..ae6675e 100644
--- a/core/total-ordering_test.go
+++ b/core/total-ordering_test.go
@@ -66,25 +66,14 @@ func (s *TotalOrderingTestSuite) checkNotInWorkingSet(
s.NotContains(to.acked, b.Hash)
}
-func (s *TotalOrderingTestSuite) prepareDirtyValidators(
- validators []types.ValidatorID) types.ValidatorIDs {
-
- dirties := types.ValidatorIDs{}
- for _, vID := range validators {
- dirties = append(dirties, vID)
- }
- return dirties
-}
-
func (s *TotalOrderingTestSuite) TestBlockRelation() {
// This test case would verify if 'acking' and 'acked'
// accumulated correctly.
//
// The DAG used below is:
// A <- B <- C
-
- vID := types.ValidatorID{Hash: common.NewRandomHash()}
-
+ validators := test.GenerateRandomValidatorIDs(5)
+ vID := validators[0]
blockA := s.genGenesisBlock(vID, map[common.Hash]struct{}{})
blockB := &types.Block{
ProposerID: vID,
@@ -105,7 +94,7 @@ func (s *TotalOrderingTestSuite) TestBlockRelation() {
},
}
- to := newTotalOrdering(1, 3, 5)
+ to := newTotalOrdering(1, 3, validators)
s.checkNotDeliver(to, blockA)
s.checkNotDeliver(to, blockB)
s.checkNotDeliver(to, blockC)
@@ -127,66 +116,77 @@ func (s *TotalOrderingTestSuite) TestBlockRelation() {
func (s *TotalOrderingTestSuite) TestCreateAckingHeightVectorFromHeightVector() {
var (
- validators = test.GenerateRandomValidatorIDs(5)
- cache = newTotalOrderingObjectCache()
+ cache = newTotalOrderingObjectCache(5)
+ dirties = []int{0, 1, 2, 3, 4}
)
- // Generate dirty validator set.
- dirties := s.prepareDirtyValidators(validators)
// Prepare global acking status.
global := &totalOrderingCandidateInfo{
- ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{
- validators[0]: &totalOrderingHeightRecord{minHeight: 0, count: 5},
- validators[1]: &totalOrderingHeightRecord{minHeight: 0, count: 5},
- validators[2]: &totalOrderingHeightRecord{minHeight: 0, count: 5},
- validators[3]: &totalOrderingHeightRecord{minHeight: 0, count: 5},
+ ackedStatus: []*totalOrderingHeightRecord{
+ &totalOrderingHeightRecord{minHeight: 0, count: 5},
+ &totalOrderingHeightRecord{minHeight: 0, count: 5},
+ &totalOrderingHeightRecord{minHeight: 0, count: 5},
+ &totalOrderingHeightRecord{minHeight: 0, count: 5},
+ &totalOrderingHeightRecord{minHeight: 0, count: 0},
}}
// For 'not existed' record in local but exist in global,
// should be infinity.
candidate := &totalOrderingCandidateInfo{
- ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{
- validators[0]: &totalOrderingHeightRecord{minHeight: 0, count: 2},
+ ackedStatus: []*totalOrderingHeightRecord{
+ &totalOrderingHeightRecord{minHeight: 0, count: 2},
+ &totalOrderingHeightRecord{minHeight: 0, count: 0},
+ &totalOrderingHeightRecord{minHeight: 0, count: 0},
+ &totalOrderingHeightRecord{minHeight: 0, count: 0},
+ &totalOrderingHeightRecord{minHeight: 0, count: 0},
}}
candidate.updateAckingHeightVector(global, 0, dirties, cache)
- s.Len(candidate.cachedHeightVector, 4)
- s.Equal(candidate.cachedHeightVector[validators[0]], uint64(0))
- s.Equal(candidate.cachedHeightVector[validators[1]], infinity)
- s.Equal(candidate.cachedHeightVector[validators[2]], infinity)
- s.Equal(candidate.cachedHeightVector[validators[3]], infinity)
+ s.Equal(candidate.cachedHeightVector[0], uint64(0))
+ s.Equal(candidate.cachedHeightVector[1], infinity)
+ s.Equal(candidate.cachedHeightVector[2], infinity)
+ s.Equal(candidate.cachedHeightVector[3], infinity)
// For local min exceeds global's min+k-1, should be infinity
candidate = &totalOrderingCandidateInfo{
- ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{
- validators[0]: &totalOrderingHeightRecord{minHeight: 3, count: 1},
+ ackedStatus: []*totalOrderingHeightRecord{
+ &totalOrderingHeightRecord{minHeight: 3, count: 1},
+ &totalOrderingHeightRecord{minHeight: 0, count: 0},
+ &totalOrderingHeightRecord{minHeight: 0, count: 0},
+ &totalOrderingHeightRecord{minHeight: 0, count: 0},
+ &totalOrderingHeightRecord{minHeight: 0, count: 0},
}}
candidate.updateAckingHeightVector(global, 2, dirties, cache)
- s.Equal(candidate.cachedHeightVector[validators[0]], infinity)
+ s.Equal(candidate.cachedHeightVector[0], infinity)
candidate.updateAckingHeightVector(global, 3, dirties, cache)
- s.Equal(candidate.cachedHeightVector[validators[0]], uint64(3))
+ s.Equal(candidate.cachedHeightVector[0], uint64(3))
candidate = &totalOrderingCandidateInfo{
- ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{
- validators[0]: &totalOrderingHeightRecord{minHeight: 0, count: 3},
- validators[1]: &totalOrderingHeightRecord{minHeight: 0, count: 3},
+ ackedStatus: []*totalOrderingHeightRecord{
+ &totalOrderingHeightRecord{minHeight: 0, count: 3},
+ &totalOrderingHeightRecord{minHeight: 0, count: 3},
+ &totalOrderingHeightRecord{minHeight: 0, count: 0},
+ &totalOrderingHeightRecord{minHeight: 0, count: 0},
+ &totalOrderingHeightRecord{minHeight: 0, count: 0},
}}
candidate.updateAckingHeightVector(global, 5, dirties, cache)
- s.Len(candidate.cachedHeightVector, 0)
}
func (s *TotalOrderingTestSuite) TestCreateAckingNodeSetFromHeightVector() {
- validators := test.GenerateRandomValidatorIDs(5)
global := &totalOrderingCandidateInfo{
- ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{
- validators[0]: &totalOrderingHeightRecord{minHeight: 0, count: 5},
- validators[1]: &totalOrderingHeightRecord{minHeight: 0, count: 5},
- validators[2]: &totalOrderingHeightRecord{minHeight: 0, count: 5},
- validators[3]: &totalOrderingHeightRecord{minHeight: 0, count: 5},
+ ackedStatus: []*totalOrderingHeightRecord{
+ &totalOrderingHeightRecord{minHeight: 0, count: 5},
+ &totalOrderingHeightRecord{minHeight: 0, count: 5},
+ &totalOrderingHeightRecord{minHeight: 0, count: 5},
+ &totalOrderingHeightRecord{minHeight: 0, count: 5},
+ &totalOrderingHeightRecord{minHeight: 0, count: 0},
}}
local := &totalOrderingCandidateInfo{
- ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{
- validators[0]: &totalOrderingHeightRecord{
- minHeight: 1, count: 2},
+ ackedStatus: []*totalOrderingHeightRecord{
+ &totalOrderingHeightRecord{minHeight: 1, count: 2},
+ &totalOrderingHeightRecord{minHeight: 0, count: 0},
+ &totalOrderingHeightRecord{minHeight: 0, count: 0},
+ &totalOrderingHeightRecord{minHeight: 0, count: 0},
+ &totalOrderingHeightRecord{minHeight: 0, count: 0},
}}
s.Equal(local.getAckingNodeSetLength(global, 1), uint64(1))
s.Equal(local.getAckingNodeSetLength(global, 2), uint64(1))
@@ -197,55 +197,38 @@ func (s *TotalOrderingTestSuite) TestGrade() {
// This test case just fake some internal structure used
// when performing total ordering.
var (
- validators = test.GenerateRandomValidatorIDs(5)
- cache = newTotalOrderingObjectCache()
+ validators = test.GenerateRandomValidatorIDs(5)
+ cache = newTotalOrderingObjectCache(5)
+ dirtyValidators = []int{0, 1, 2, 3, 4}
)
- dirtyValidators := s.prepareDirtyValidators(validators)
ansLength := uint64(len(map[types.ValidatorID]struct{}{
validators[0]: struct{}{},
validators[1]: struct{}{},
validators[2]: struct{}{},
validators[3]: struct{}{},
}))
- candidates := common.Hashes{
- common.NewRandomHash(),
- common.NewRandomHash(),
- common.NewRandomHash(),
- }
- candidate1 := newTotalOrderingCandidateInfo(cache)
- candidate1.cachedHeightVector = map[types.ValidatorID]uint64{
- validators[0]: 1,
- validators[1]: infinity,
- validators[2]: infinity,
- validators[3]: infinity,
- }
- candidate2 := newTotalOrderingCandidateInfo(cache)
- candidate2.cachedHeightVector = map[types.ValidatorID]uint64{
- validators[0]: 1,
- validators[1]: 1,
- validators[2]: 1,
- validators[3]: 1,
- }
- candidate3 := newTotalOrderingCandidateInfo(cache)
- candidate3.cachedHeightVector = map[types.ValidatorID]uint64{
- validators[0]: 1,
- validators[1]: 1,
- validators[2]: infinity,
- validators[3]: infinity,
- }
+ candidate1 := newTotalOrderingCandidateInfo(common.Hash{}, cache)
+ candidate1.cachedHeightVector = []uint64{
+ 1, infinity, infinity, infinity, infinity}
+ candidate2 := newTotalOrderingCandidateInfo(common.Hash{}, cache)
+ candidate2.cachedHeightVector = []uint64{
+ 1, 1, 1, 1, infinity}
+ candidate3 := newTotalOrderingCandidateInfo(common.Hash{}, cache)
+ candidate3.cachedHeightVector = []uint64{
+ 1, 1, infinity, infinity, infinity}
candidate2.updateWinRecord(
- candidates[0], candidate1, dirtyValidators, cache)
- s.Equal(candidate2.winRecords[candidates[0]].grade(5, 3, ansLength), 1)
+ 0, candidate1, dirtyValidators, cache)
+ s.Equal(candidate2.winRecords[0].grade(5, 3, ansLength), 1)
candidate1.updateWinRecord(
- candidates[1], candidate2, dirtyValidators, cache)
- s.Equal(candidate1.winRecords[candidates[1]].grade(5, 3, ansLength), 0)
+ 1, candidate2, dirtyValidators, cache)
+ s.Equal(candidate1.winRecords[1].grade(5, 3, ansLength), 0)
candidate2.updateWinRecord(
- candidates[2], candidate3, dirtyValidators, cache)
- s.Equal(candidate2.winRecords[candidates[2]].grade(5, 3, ansLength), -1)
+ 2, candidate3, dirtyValidators, cache)
+ s.Equal(candidate2.winRecords[2].grade(5, 3, ansLength), -1)
candidate3.updateWinRecord(
- candidates[1], candidate2, dirtyValidators, cache)
- s.Equal(candidate3.winRecords[candidates[1]].grade(5, 3, ansLength), 0)
+ 1, candidate2, dirtyValidators, cache)
+ s.Equal(candidate3.winRecords[1].grade(5, 3, ansLength), 0)
}
func (s *TotalOrderingTestSuite) TestCycleDetection() {
@@ -291,7 +274,7 @@ func (s *TotalOrderingTestSuite) TestCycleDetection() {
b10.Acks[b10.Hash] = struct{}{}
// Make sure we won't hang when cycle exists.
- to := newTotalOrdering(1, 3, 5)
+ to := newTotalOrdering(1, 3, validators)
s.checkNotDeliver(to, b00)
s.checkNotDeliver(to, b01)
s.checkNotDeliver(to, b02)
@@ -303,8 +286,8 @@ func (s *TotalOrderingTestSuite) TestCycleDetection() {
}
func (s *TotalOrderingTestSuite) TestNotValidDAGDetection() {
- validators := test.GenerateRandomValidatorIDs(4)
- to := newTotalOrdering(1, 3, 5)
+ validators := test.GenerateRandomValidatorIDs(5)
+ to := newTotalOrdering(1, 3, validators)
b00 := s.genGenesisBlock(validators[0], map[common.Hash]struct{}{})
b01 := &types.Block{
@@ -331,8 +314,14 @@ func (s *TotalOrderingTestSuite) TestEarlyDeliver() {
// A B
// Even when B is not received, A should
// be able to be delivered.
- to := newTotalOrdering(2, 3, 5)
validators := test.GenerateRandomValidatorIDs(5)
+ to := newTotalOrdering(2, 3, validators)
+ // Get indexes of validatorID used in total ordering module.
+ var validatorIndexes []int
+ for _, vID := range validators {
+ validatorIndexes = append(
+ validatorIndexes, to.validatorIndexMapping[vID])
+ }
genNextBlock := func(b *types.Block) *types.Block {
return &types.Block{
@@ -374,11 +363,10 @@ func (s *TotalOrderingTestSuite) TestEarlyDeliver() {
s.checkNotDeliver(to, b01)
s.checkNotDeliver(to, b02)
- candidate := to.candidates[b00.Hash]
+ candidate := to.candidates[to.candidateIndexMapping[b00.Hash]]
s.Require().NotNil(candidate)
- s.Len(candidate.ackedStatus, 1)
- s.Equal(candidate.ackedStatus[validators[0]].minHeight, b00.Height)
- s.Equal(candidate.ackedStatus[validators[0]].count, uint64(3))
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b00.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(3))
s.checkNotDeliver(to, b10)
s.checkNotDeliver(to, b11)
@@ -390,19 +378,18 @@ func (s *TotalOrderingTestSuite) TestEarlyDeliver() {
s.checkNotDeliver(to, b31)
// Check the internal state before delivering.
- s.Len(to.candidates, 1) // b00 is the only candidate.
+ s.Len(to.candidateIndexMapping, 1) // b00 is the only candidate.
- candidate = to.candidates[b00.Hash]
+ candidate = to.candidates[to.candidateIndexMapping[b00.Hash]]
s.Require().NotNil(candidate)
- s.Len(candidate.ackedStatus, 4)
- s.Equal(candidate.ackedStatus[validators[0]].minHeight, b00.Height)
- s.Equal(candidate.ackedStatus[validators[0]].count, uint64(3))
- s.Equal(candidate.ackedStatus[validators[1]].minHeight, b10.Height)
- s.Equal(candidate.ackedStatus[validators[1]].count, uint64(3))
- s.Equal(candidate.ackedStatus[validators[2]].minHeight, b20.Height)
- s.Equal(candidate.ackedStatus[validators[2]].count, uint64(3))
- s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height)
- s.Equal(candidate.ackedStatus[validators[3]].count, uint64(2))
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b00.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(3))
+ s.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b10.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(3))
+ s.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b20.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(3))
+ s.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b30.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(2))
blocks, early, err := to.processBlock(b32)
s.Require().Len(blocks, 1)
@@ -411,44 +398,46 @@ func (s *TotalOrderingTestSuite) TestEarlyDeliver() {
s.checkHashSequence(blocks, common.Hashes{b00.Hash})
// Check the internal state after delivered.
- s.Len(to.candidates, 4) // b01, b10, b20, b30 are candidates.
+ s.Len(to.candidateIndexMapping, 4) // b01, b10, b20, b30 are candidates.
// Check b01.
- candidate = to.candidates[b01.Hash]
+ candidate = to.candidates[to.candidateIndexMapping[b01.Hash]]
s.Require().NotNil(candidate)
- s.Len(candidate.ackedStatus, 1)
- s.Equal(candidate.ackedStatus[validators[0]].minHeight, b01.Height)
- s.Equal(candidate.ackedStatus[validators[0]].count, uint64(2))
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b01.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(2))
// Check b10.
- candidate = to.candidates[b10.Hash]
+ candidate = to.candidates[to.candidateIndexMapping[b10.Hash]]
s.Require().NotNil(candidate)
- s.Len(candidate.ackedStatus, 1)
- s.Equal(candidate.ackedStatus[validators[1]].minHeight, b10.Height)
- s.Equal(candidate.ackedStatus[validators[1]].count, uint64(3))
+ s.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b10.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(3))
// Check b20.
- candidate = to.candidates[b20.Hash]
+ candidate = to.candidates[to.candidateIndexMapping[b20.Hash]]
s.Require().NotNil(candidate)
- s.Len(candidate.ackedStatus, 1)
- s.Equal(candidate.ackedStatus[validators[2]].minHeight, b20.Height)
- s.Equal(candidate.ackedStatus[validators[2]].count, uint64(3))
+ s.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b20.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(3))
// Check b30.
- candidate = to.candidates[b30.Hash]
+ candidate = to.candidates[to.candidateIndexMapping[b30.Hash]]
s.Require().NotNil(candidate)
- s.Len(candidate.ackedStatus, 1)
- s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height)
- s.Equal(candidate.ackedStatus[validators[3]].count, uint64(3))
+ s.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b30.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(3))
// Make sure b00 doesn't exist in current working set:
s.checkNotInWorkingSet(to, b00)
}
-func (s *TotalOrderingTestSuite) _TestBasicCaseForK2() {
+func (s *TotalOrderingTestSuite) TestBasicCaseForK2() {
// It's a handcrafted test case.
- to := newTotalOrdering(2, 3, 5)
validators := test.GenerateRandomValidatorIDs(5)
+ to := newTotalOrdering(2, 3, validators)
+ // Get indexes of validatorID used in total ordering module.
+ var validatorIndexes []int
+ for _, vID := range validators {
+ validatorIndexes = append(
+ validatorIndexes, to.validatorIndexMapping[vID])
+ }
b00 := s.genGenesisBlock(validators[0], map[common.Hash]struct{}{})
b10 := s.genGenesisBlock(validators[1], map[common.Hash]struct{}{})
@@ -631,33 +620,33 @@ func (s *TotalOrderingTestSuite) _TestBasicCaseForK2() {
s.Contains(acked, b32.Hash)
// Make sure there are 2 candidates.
- s.Require().Len(to.candidates, 2)
+ s.Require().Len(to.candidateIndexMapping, 2)
// Check b00's height vector.
- candidate := to.candidates[b00.Hash]
+ candidate := to.candidates[to.candidateIndexMapping[b00.Hash]]
s.Require().NotNil(candidate)
- s.NotContains(candidate.ackedStatus, validators[4])
- s.Equal(candidate.ackedStatus[validators[0]].minHeight, b00.Height)
- s.Equal(candidate.ackedStatus[validators[0]].count, uint64(2))
- s.Equal(candidate.ackedStatus[validators[1]].minHeight, b11.Height)
- s.Equal(candidate.ackedStatus[validators[1]].count, uint64(2))
- s.Equal(candidate.ackedStatus[validators[2]].minHeight, b21.Height)
- s.Equal(candidate.ackedStatus[validators[2]].count, uint64(2))
- s.Equal(candidate.ackedStatus[validators[3]].minHeight, b31.Height)
- s.Equal(candidate.ackedStatus[validators[3]].count, uint64(2))
+ s.NotContains(candidate.ackedStatus, validatorIndexes[4])
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b00.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(2))
+ s.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b11.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(2))
+ s.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b21.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(2))
+ s.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b31.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(2))
// Check b10's height vector.
- candidate = to.candidates[b10.Hash]
+ candidate = to.candidates[to.candidateIndexMapping[b10.Hash]]
s.Require().NotNil(candidate)
- s.NotContains(candidate.ackedStatus, validators[4])
- s.Equal(candidate.ackedStatus[validators[0]].minHeight, b01.Height)
- s.Equal(candidate.ackedStatus[validators[0]].count, uint64(1))
- s.Equal(candidate.ackedStatus[validators[1]].minHeight, b10.Height)
- s.Equal(candidate.ackedStatus[validators[1]].count, uint64(3))
- s.Equal(candidate.ackedStatus[validators[2]].minHeight, b20.Height)
- s.Equal(candidate.ackedStatus[validators[2]].count, uint64(3))
- s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height)
- s.Equal(candidate.ackedStatus[validators[3]].count, uint64(3))
+ s.NotContains(candidate.ackedStatus, validatorIndexes[4])
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b01.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(1))
+ s.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b10.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(3))
+ s.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b20.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(3))
+ s.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b30.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(3))
// Check the first deliver.
blocks, early, err := to.processBlock(b02)
@@ -670,33 +659,33 @@ func (s *TotalOrderingTestSuite) _TestBasicCaseForK2() {
s.checkNotInWorkingSet(to, b10)
// Check if candidates of next round are picked correctly.
- s.Len(to.candidates, 2)
+ s.Len(to.candidateIndexMapping, 2)
// Check b01's height vector.
- candidate = to.candidates[b11.Hash]
+ candidate = to.candidates[to.candidateIndexMapping[b11.Hash]]
s.Require().NotNil(candidate)
s.NotContains(candidate.ackedStatus, validators[4])
- s.Equal(candidate.ackedStatus[validators[0]].minHeight, b01.Height)
- s.Equal(candidate.ackedStatus[validators[0]].count, uint64(2))
- s.Equal(candidate.ackedStatus[validators[1]].minHeight, b11.Height)
- s.Equal(candidate.ackedStatus[validators[1]].count, uint64(2))
- s.Equal(candidate.ackedStatus[validators[2]].minHeight, b21.Height)
- s.Equal(candidate.ackedStatus[validators[2]].count, uint64(2))
- s.Equal(candidate.ackedStatus[validators[3]].minHeight, b11.Height)
- s.Equal(candidate.ackedStatus[validators[3]].count, uint64(2))
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b01.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(2))
+ s.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b11.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(2))
+ s.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b21.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(2))
+ s.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b11.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(2))
// Check b20's height vector.
- candidate = to.candidates[b20.Hash]
+ candidate = to.candidates[to.candidateIndexMapping[b20.Hash]]
s.Require().NotNil(candidate)
s.NotContains(candidate.ackedStatus, validators[4])
- s.Equal(candidate.ackedStatus[validators[0]].minHeight, b02.Height)
- s.Equal(candidate.ackedStatus[validators[0]].count, uint64(1))
- s.Equal(candidate.ackedStatus[validators[1]].minHeight, b12.Height)
- s.Equal(candidate.ackedStatus[validators[1]].count, uint64(1))
- s.Equal(candidate.ackedStatus[validators[2]].minHeight, b20.Height)
- s.Equal(candidate.ackedStatus[validators[2]].count, uint64(3))
- s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height)
- s.Equal(candidate.ackedStatus[validators[3]].count, uint64(3))
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b02.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(1))
+ s.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b12.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(1))
+ s.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b20.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(3))
+ s.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b30.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(3))
s.checkNotDeliver(to, b13)
@@ -717,39 +706,39 @@ func (s *TotalOrderingTestSuite) _TestBasicCaseForK2() {
s.checkNotDeliver(to, b14)
// Make sure b01, b30, b40 are candidate in next round.
- s.Len(to.candidates, 3)
- candidate = to.candidates[b01.Hash]
+ s.Len(to.candidateIndexMapping, 3)
+ candidate = to.candidates[to.candidateIndexMapping[b01.Hash]]
s.Require().NotNil(candidate)
- s.NotContains(candidate.ackedStatus, validators[4])
- s.Equal(candidate.ackedStatus[validators[0]].minHeight, b01.Height)
- s.Equal(candidate.ackedStatus[validators[0]].count, uint64(3))
- s.Equal(candidate.ackedStatus[validators[1]].minHeight, b12.Height)
- s.Equal(candidate.ackedStatus[validators[1]].count, uint64(3))
- s.Equal(candidate.ackedStatus[validators[2]].minHeight, b21.Height)
- s.Equal(candidate.ackedStatus[validators[2]].count, uint64(2))
- s.Equal(candidate.ackedStatus[validators[3]].minHeight, b31.Height)
- s.Equal(candidate.ackedStatus[validators[3]].count, uint64(2))
-
- candidate = to.candidates[b30.Hash]
+ s.NotContains(candidate.ackedStatus, validatorIndexes[4])
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b01.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(3))
+ s.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b12.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(3))
+ s.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b21.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(2))
+ s.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b31.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(2))
+
+ candidate = to.candidates[to.candidateIndexMapping[b30.Hash]]
s.Require().NotNil(candidate)
- s.NotContains(candidate.ackedStatus, validators[4])
- s.Equal(candidate.ackedStatus[validators[0]].minHeight, b03.Height)
- s.Equal(candidate.ackedStatus[validators[0]].count, uint64(1))
- s.Equal(candidate.ackedStatus[validators[1]].minHeight, b13.Height)
- s.Equal(candidate.ackedStatus[validators[1]].count, uint64(2))
- s.Equal(candidate.ackedStatus[validators[2]].minHeight, b22.Height)
- s.Equal(candidate.ackedStatus[validators[2]].count, uint64(1))
- s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height)
- s.Equal(candidate.ackedStatus[validators[3]].count, uint64(3))
-
- candidate = to.candidates[b40.Hash]
+ s.NotContains(candidate.ackedStatus, validatorIndexes[4])
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b03.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(1))
+ s.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b13.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(2))
+ s.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b22.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(1))
+ s.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b30.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(3))
+
+ candidate = to.candidates[to.candidateIndexMapping[b40.Hash]]
s.Require().NotNil(candidate)
- s.NotContains(candidate.ackedStatus, validators[0])
- s.NotContains(candidate.ackedStatus, validators[1])
- s.NotContains(candidate.ackedStatus, validators[2])
- s.NotContains(candidate.ackedStatus, validators[3])
- s.Equal(candidate.ackedStatus[validators[4]].minHeight, b40.Height)
- s.Equal(candidate.ackedStatus[validators[4]].count, uint64(3))
+ s.NotContains(candidate.ackedStatus, validatorIndexes[0])
+ s.NotContains(candidate.ackedStatus, validatorIndexes[1])
+ s.NotContains(candidate.ackedStatus, validatorIndexes[2])
+ s.NotContains(candidate.ackedStatus, validatorIndexes[3])
+ s.Equal(candidate.ackedStatus[validatorIndexes[4]].minHeight, b40.Height)
+ s.Equal(candidate.ackedStatus[validatorIndexes[4]].count, uint64(3))
// Make 'Acking Node Set' contains blocks from all validators,
// this should trigger not-early deliver.
@@ -763,8 +752,8 @@ func (s *TotalOrderingTestSuite) _TestBasicCaseForK2() {
s.checkNotInWorkingSet(to, b30)
// Make sure b21, b40 are candidates of next round.
- s.Contains(to.candidates, b21.Hash)
- s.Contains(to.candidates, b40.Hash)
+ s.Contains(to.candidateIndexMapping, b21.Hash)
+ s.Contains(to.candidateIndexMapping, b40.Hash)
}
func (s *TotalOrderingTestSuite) TestBasicCaseForK0() {
@@ -778,8 +767,17 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK0() {
// | \ | \ | |
// v v v v
// o o o <- o Height: 0
- to := newTotalOrdering(0, 3, 5)
+ var (
+ req = s.Require()
+ validatorIndexes []int
+ )
validators := test.GenerateRandomValidatorIDs(5)
+ to := newTotalOrdering(0, 3, validators)
+ // Get indexes of validatorID used in total ordering module.
+ for _, vID := range validators {
+ validatorIndexes = append(
+ validatorIndexes, to.validatorIndexMapping[vID])
+ }
b00 := s.genGenesisBlock(validators[0], map[common.Hash]struct{}{})
b10 := s.genGenesisBlock(validators[1], map[common.Hash]struct{}{})
@@ -840,46 +838,44 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK0() {
s.checkNotDeliver(to, b31)
// Check candidate status before delivering.
- candidate := to.candidates[b00.Hash]
- s.Require().NotNil(candidate)
- s.Len(candidate.ackedStatus, 1)
- s.Equal(candidate.ackedStatus[validators[0]].minHeight, b00.Height)
- s.Equal(candidate.ackedStatus[validators[0]].count, uint64(2))
-
- candidate = to.candidates[b10.Hash]
- s.Require().NotNil(candidate)
- s.Len(candidate.ackedStatus, 2)
- s.Equal(candidate.ackedStatus[validators[0]].minHeight, b01.Height)
- s.Equal(candidate.ackedStatus[validators[0]].count, uint64(1))
- s.Equal(candidate.ackedStatus[validators[1]].minHeight, b10.Height)
- s.Equal(candidate.ackedStatus[validators[1]].count, uint64(2))
-
- candidate = to.candidates[b20.Hash]
- s.Require().NotNil(candidate)
- s.Len(candidate.ackedStatus, 3)
- s.Equal(candidate.ackedStatus[validators[1]].minHeight, b11.Height)
- s.Equal(candidate.ackedStatus[validators[1]].count, uint64(1))
- s.Equal(candidate.ackedStatus[validators[2]].minHeight, b20.Height)
- s.Equal(candidate.ackedStatus[validators[2]].count, uint64(2))
- s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height)
- s.Equal(candidate.ackedStatus[validators[3]].count, uint64(2))
+ candidate := to.candidates[to.candidateIndexMapping[b00.Hash]]
+ req.NotNil(candidate)
+ req.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b00.Height)
+ req.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(2))
+
+ candidate = to.candidates[to.candidateIndexMapping[b10.Hash]]
+ req.NotNil(candidate)
+ req.Equal(candidate.ackedStatus[validatorIndexes[0]].minHeight, b01.Height)
+ req.Equal(candidate.ackedStatus[validatorIndexes[0]].count, uint64(1))
+ req.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b10.Height)
+ req.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(2))
+
+ candidate = to.candidates[to.candidateIndexMapping[b20.Hash]]
+ req.NotNil(candidate)
+ req.Equal(candidate.ackedStatus[validatorIndexes[1]].minHeight, b11.Height)
+ req.Equal(candidate.ackedStatus[validatorIndexes[1]].count, uint64(1))
+ req.Equal(candidate.ackedStatus[validatorIndexes[2]].minHeight, b20.Height)
+ req.Equal(candidate.ackedStatus[validatorIndexes[2]].count, uint64(2))
+ req.Equal(candidate.ackedStatus[validatorIndexes[3]].minHeight, b30.Height)
+ req.Equal(candidate.ackedStatus[validatorIndexes[3]].count, uint64(2))
// This new block should trigger non-early deliver.
blocks, early, err := to.processBlock(b40)
- s.False(early)
- s.Nil(err)
+ req.False(early)
+ req.Nil(err)
s.checkHashSequence(blocks, common.Hashes{b20.Hash})
// Make sure b20 is no long existing in working set.
s.checkNotInWorkingSet(to, b20)
// Make sure b10, b30 are candidates for next round.
- s.Contains(to.candidates, b10.Hash)
- s.Contains(to.candidates, b30.Hash)
+ req.Contains(to.candidateIndexMapping, b00.Hash)
+ req.Contains(to.candidateIndexMapping, b10.Hash)
+ req.Contains(to.candidateIndexMapping, b30.Hash)
}
func (s *TotalOrderingTestSuite) baseTestRandomlyGeneratedBlocks(
- totalOrderingConstructor func() *totalOrdering,
+ totalOrderingConstructor func(types.ValidatorIDs) *totalOrdering,
validatorCount, blockCount int,
ackingCountGenerator func() int,
repeat int) {
@@ -893,8 +889,10 @@ func (s *TotalOrderingTestSuite) baseTestRandomlyGeneratedBlocks(
db, err := blockdb.NewMemBackedBlockDB()
req.Nil(err)
- req.Nil(gen.Generate(
- validatorCount, blockCount, ackingCountGenerator, db))
+ validators, err := gen.Generate(
+ validatorCount, blockCount, ackingCountGenerator, db)
+ req.Nil(err)
+ req.Len(validators, validatorCount)
iter, err := db.GetAll()
req.Nil(err)
// Setup a revealer that would reveal blocks forming
@@ -907,7 +905,7 @@ func (s *TotalOrderingTestSuite) baseTestRandomlyGeneratedBlocks(
revealed := ""
ordered := ""
revealer.Reset()
- to := totalOrderingConstructor()
+ to := totalOrderingConstructor(validators)
for {
// Reveal next block.
b, err := revealer.Next()
@@ -965,26 +963,26 @@ func (s *TotalOrderingTestSuite) TestRandomlyGeneratedBlocks() {
// Test based on different acking frequency.
for _, gen := range ackingCountGenerators {
// Test for K=0.
- constructor := func() *totalOrdering {
- return newTotalOrdering(0, phi, uint64(validatorCount))
+ constructor := func(validators types.ValidatorIDs) *totalOrdering {
+ return newTotalOrdering(0, phi, validators)
}
s.baseTestRandomlyGeneratedBlocks(
constructor, validatorCount, blockCount, gen, repeat)
// Test for K=1,
- constructor = func() *totalOrdering {
- return newTotalOrdering(1, phi, uint64(validatorCount))
+ constructor = func(validators types.ValidatorIDs) *totalOrdering {
+ return newTotalOrdering(1, phi, validators)
}
s.baseTestRandomlyGeneratedBlocks(
constructor, validatorCount, blockCount, gen, repeat)
// Test for K=2,
- constructor = func() *totalOrdering {
- return newTotalOrdering(2, phi, uint64(validatorCount))
+ constructor = func(validators types.ValidatorIDs) *totalOrdering {
+ return newTotalOrdering(2, phi, validators)
}
s.baseTestRandomlyGeneratedBlocks(
constructor, validatorCount, blockCount, gen, repeat)
// Test for K=3,
- constructor = func() *totalOrdering {
- return newTotalOrdering(3, phi, uint64(validatorCount))
+ constructor = func(validators types.ValidatorIDs) *totalOrdering {
+ return newTotalOrdering(3, phi, validators)
}
s.baseTestRandomlyGeneratedBlocks(
constructor, validatorCount, blockCount, gen, repeat)
diff --git a/core/utils.go b/core/utils.go
index d023d2e..6b03f93 100644
--- a/core/utils.go
+++ b/core/utils.go
@@ -92,3 +92,14 @@ func getMedianTime(block *types.Block) (t time.Time, err error) {
return
}
+
+func removeFromSortedIntSlice(xs []int, x int) []int {
+ indexToRemove := sort.Search(len(xs), func(idx int) bool {
+ return xs[idx] >= x
+ })
+ if indexToRemove == len(xs) || xs[indexToRemove] != x {
+ // This value is not found.
+ return xs
+ }
+ return append(xs[:indexToRemove], xs[indexToRemove+1:]...)
+}
diff --git a/core/utils_test.go b/core/utils_test.go
new file mode 100644
index 0000000..5d55de3
--- /dev/null
+++ b/core/utils_test.go
@@ -0,0 +1,27 @@
+package core
+
+import (
+ "testing"
+
+ "github.com/stretchr/testify/suite"
+)
+
+type UtilsTestSuite struct {
+ suite.Suite
+}
+
+func (s *UtilsTestSuite) TestRemoveFromSortedIntSlice() {
+ // Remove something exists.
+ xs := []int{1, 2, 3, 4, 5}
+ s.Equal(
+ removeFromSortedIntSlice(xs, 3),
+ []int{1, 2, 4, 5})
+ // Remove something not exists.
+ s.Equal(removeFromSortedIntSlice(xs, 6), xs)
+ // Remove from empty slice, should not panic.
+ s.Equal([]int{}, removeFromSortedIntSlice([]int{}, 1))
+}
+
+func TestUtils(t *testing.T) {
+ suite.Run(t, new(UtilsTestSuite))
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-08 02:55:58 +0800