From 248fdaa5ccca535ddce93173f2f0f3bc60b9381d Mon Sep 17 00:00:00 2001 From: Wei-Ning Huang Date: Fri, 2 Nov 2018 12:04:20 +0800 Subject: Rename import due to dexon-consensus rename --- .../dexon-consensus/core/lattice.go | 317 +++++++++++++++++++++ 1 file changed, 317 insertions(+) create mode 100644 vendor/github.com/dexon-foundation/dexon-consensus/core/lattice.go (limited to 'vendor/github.com/dexon-foundation/dexon-consensus/core/lattice.go') diff --git a/vendor/github.com/dexon-foundation/dexon-consensus/core/lattice.go b/vendor/github.com/dexon-foundation/dexon-consensus/core/lattice.go new file mode 100644 index 000000000..af9c3c42f --- /dev/null +++ b/vendor/github.com/dexon-foundation/dexon-consensus/core/lattice.go @@ -0,0 +1,317 @@ +// Copyright 2018 The dexon-consensus Authors +// This file is part of the dexon-consensus library. +// +// The dexon-consensus library is free software: you can redistribute it +// and/or modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation, either version 3 of the License, +// or (at your option) any later version. +// +// The dexon-consensus library is distributed in the hope that it will be +// useful, but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser +// General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the dexon-consensus library. If not, see +// . + +package core + +import ( + "fmt" + "sync" + "time" + + "github.com/dexon-foundation/dexon-consensus/common" + "github.com/dexon-foundation/dexon-consensus/core/blockdb" + "github.com/dexon-foundation/dexon-consensus/core/types" +) + +// Errors for sanity check error. +var ( + ErrRetrySanityCheckLater = fmt.Errorf("retry sanity check later") +) + +// Lattice represents a unit to produce a global ordering from multiple chains. +type Lattice struct { + lock sync.RWMutex + authModule *Authenticator + app Application + debug Debug + pool blockPool + retryAdd bool + data *latticeData + toModule *totalOrdering + ctModule *consensusTimestamp + logger common.Logger +} + +// NewLattice constructs an Lattice instance. +func NewLattice( + dMoment time.Time, + cfg *types.Config, + authModule *Authenticator, + app Application, + debug Debug, + db blockdb.BlockDatabase, + logger common.Logger) (s *Lattice) { + // Create genesis latticeDataConfig. + dataConfig := newGenesisLatticeDataConfig(dMoment, cfg) + toConfig := newGenesisTotalOrderingConfig(dMoment, cfg) + s = &Lattice{ + authModule: authModule, + app: app, + debug: debug, + pool: newBlockPool(cfg.NumChains), + data: newLatticeData(db, dataConfig), + toModule: newTotalOrdering(toConfig), + ctModule: newConsensusTimestamp(dMoment, 0, cfg.NumChains), + logger: logger, + } + return +} + +// PrepareBlock setup block's field based on current lattice status. +func (s *Lattice) PrepareBlock( + b *types.Block, proposeTime time.Time) (err error) { + + s.lock.RLock() + defer s.lock.RUnlock() + + b.Timestamp = proposeTime + if err = s.data.prepareBlock(b); err != nil { + return + } + s.logger.Debug("Calling Application.PreparePayload", "position", b.Position) + if b.Payload, err = s.app.PreparePayload(b.Position); err != nil { + return + } + s.logger.Debug("Calling Application.PrepareWitness", + "height", b.Witness.Height) + if b.Witness, err = s.app.PrepareWitness(b.Witness.Height); err != nil { + return + } + if err = s.authModule.SignBlock(b); err != nil { + return + } + return +} + +// PrepareEmptyBlock setup block's field based on current lattice status. +func (s *Lattice) PrepareEmptyBlock(b *types.Block) (err error) { + s.lock.RLock() + defer s.lock.RUnlock() + s.data.prepareEmptyBlock(b) + if b.Hash, err = hashBlock(b); err != nil { + return + } + return +} + +// SanityCheck check if a block is valid. +// +// If some acking blocks don't exists, Lattice would help to cache this block +// and retry when lattice updated in Lattice.ProcessBlock. +func (s *Lattice) SanityCheck(b *types.Block) (err error) { + if b.IsEmpty() { + // Only need to verify block's hash. + var hash common.Hash + if hash, err = hashBlock(b); err != nil { + return + } + if b.Hash != hash { + return ErrInvalidBlock + } + } else { + // Verify block's signature. + if err = s.authModule.VerifyBlock(b); err != nil { + return + } + } + // Make sure acks are sorted. + for i := range b.Acks { + if i == 0 { + continue + } + if !b.Acks[i-1].Less(b.Acks[i]) { + err = ErrAcksNotSorted + return + } + } + if err = func() (err error) { + s.lock.RLock() + defer s.lock.RUnlock() + if err = s.data.sanityCheck(b); err != nil { + if _, ok := err.(*ErrAckingBlockNotExists); ok { + err = ErrRetrySanityCheckLater + } + s.logger.Error("Sanity Check failed", "error", err) + return + } + return + }(); err != nil { + return + } + // Verify data in application layer. + s.logger.Debug("Calling Application.VerifyBlock", "block", b) + switch s.app.VerifyBlock(b) { + case types.VerifyInvalidBlock: + err = ErrInvalidBlock + case types.VerifyRetryLater: + err = ErrRetrySanityCheckLater + } + return +} + +// addBlockToLattice adds a block into lattice, and deliver blocks with the acks +// already delivered. +// +// NOTE: assume the block passed sanity check. +func (s *Lattice) addBlockToLattice( + input *types.Block) (outputBlocks []*types.Block, err error) { + if tip := s.data.chains[input.Position.ChainID].tip; tip != nil { + if !input.Position.Newer(&tip.Position) { + return + } + } + s.pool.addBlock(input) + // Replay tips in pool to check their validity. + for { + hasOutput := false + for i := uint32(0); i < uint32(len(s.pool)); i++ { + var tip *types.Block + if tip = s.pool.tip(i); tip == nil { + continue + } + err = s.data.sanityCheck(tip) + if err == nil { + var output []*types.Block + if output, err = s.data.addBlock(tip); err != nil { + s.logger.Error("Sanity Check failed", "error", err) + continue + } + hasOutput = true + outputBlocks = append(outputBlocks, output...) + } + if _, ok := err.(*ErrAckingBlockNotExists); ok { + err = nil + continue + } + s.pool.removeTip(i) + } + if !hasOutput { + break + } + } + + for _, b := range outputBlocks { + // TODO(jimmy-dexon): change this name of classic DEXON algorithm. + if s.debug != nil { + s.debug.StronglyAcked(b.Hash) + } + s.logger.Debug("Calling Application.BlockConfirmed", "block", input) + s.app.BlockConfirmed(*b.Clone()) + // Purge blocks in pool with the same chainID and lower height. + s.pool.purgeBlocks(b.Position.ChainID, b.Position.Height) + } + + return +} + +// ProcessBlock adds a block into lattice, and deliver ordered blocks. +// If any block pass sanity check after this block add into lattice, they +// would be returned, too. +// +// NOTE: assume the block passed sanity check. +func (s *Lattice) ProcessBlock( + input *types.Block) (delivered []*types.Block, err error) { + var ( + b *types.Block + inLattice []*types.Block + toDelivered []*types.Block + deliveredMode uint32 + ) + + s.lock.Lock() + defer s.lock.Unlock() + + if inLattice, err = s.addBlockToLattice(input); err != nil { + return + } + + if len(inLattice) == 0 { + return + } + + // Perform total ordering for each block added to lattice. + for _, b = range inLattice { + toDelivered, deliveredMode, err = s.toModule.processBlock(b) + if err != nil { + // All errors from total ordering is serious, should panic. + panic(err) + } + if len(toDelivered) == 0 { + continue + } + hashes := make(common.Hashes, len(toDelivered)) + for idx := range toDelivered { + hashes[idx] = toDelivered[idx].Hash + } + if s.debug != nil { + s.debug.TotalOrderingDelivered(hashes, deliveredMode) + } + // Perform timestamp generation. + if err = s.ctModule.processBlocks(toDelivered); err != nil { + return + } + delivered = append(delivered, toDelivered...) + } + return +} + +// NextPosition returns expected position of incoming block for that chain. +func (s *Lattice) NextPosition(chainID uint32) types.Position { + s.lock.RLock() + defer s.lock.RUnlock() + + return s.data.nextPosition(chainID) +} + +// PurgeBlocks from cache of blocks in memory, this is called when the caller +// make sure those blocks are saved to db. +func (s *Lattice) PurgeBlocks(blocks []*types.Block) error { + s.lock.Lock() + defer s.lock.Unlock() + + return s.data.purgeBlocks(blocks) +} + +// AppendConfig add new configs for upcoming rounds. If you add a config for +// round R, next time you can only add the config for round R+1. +func (s *Lattice) AppendConfig(round uint64, config *types.Config) (err error) { + s.lock.Lock() + defer s.lock.Unlock() + + s.pool.resize(config.NumChains) + if err = s.data.appendConfig(round, config); err != nil { + return + } + if err = s.toModule.appendConfig(round, config); err != nil { + return + } + if err = s.ctModule.appendConfig(round, config); err != nil { + return + } + return +} + +// ProcessFinalizedBlock is used for syncing lattice data. +func (s *Lattice) ProcessFinalizedBlock(input *types.Block) { + defer func() { s.retryAdd = true }() + s.lock.Lock() + defer s.lock.Unlock() + if err := s.data.addFinalizedBlock(input); err != nil { + panic(err) + } + s.pool.purgeBlocks(input.Position.ChainID, input.Position.Height) +} -- cgit