diff options
author | Wei-Ning Huang <w@byzantine-lab.io> | 2019-06-12 17:31:08 +0800 |
---|---|---|
committer | Wei-Ning Huang <w@byzantine-lab.io> | 2019-09-17 16:57:29 +0800 |
commit | ac088de6322fc16ebe75c2e5554be73754bf1fe2 (patch) | |
tree | 086b7827d46a4d07b834cd94be73beaabb77b734 /vendor/github.com/byzantine-lab/dexon-consensus/core/utils/nodeset-cache.go | |
parent | 67d565f3f0e398e99bef96827f729e3e4b0edf31 (diff) | |
download | go-tangerine-ac088de6322fc16ebe75c2e5554be73754bf1fe2.tar go-tangerine-ac088de6322fc16ebe75c2e5554be73754bf1fe2.tar.gz go-tangerine-ac088de6322fc16ebe75c2e5554be73754bf1fe2.tar.bz2 go-tangerine-ac088de6322fc16ebe75c2e5554be73754bf1fe2.tar.lz go-tangerine-ac088de6322fc16ebe75c2e5554be73754bf1fe2.tar.xz go-tangerine-ac088de6322fc16ebe75c2e5554be73754bf1fe2.tar.zst go-tangerine-ac088de6322fc16ebe75c2e5554be73754bf1fe2.zip |
Rebrand as tangerine-network/go-tangerine
Diffstat (limited to 'vendor/github.com/byzantine-lab/dexon-consensus/core/utils/nodeset-cache.go')
-rw-r--r-- | vendor/github.com/byzantine-lab/dexon-consensus/core/utils/nodeset-cache.go | 245 |
1 files changed, 245 insertions, 0 deletions
diff --git a/vendor/github.com/byzantine-lab/dexon-consensus/core/utils/nodeset-cache.go b/vendor/github.com/byzantine-lab/dexon-consensus/core/utils/nodeset-cache.go new file mode 100644 index 000000000..028690e18 --- /dev/null +++ b/vendor/github.com/byzantine-lab/dexon-consensus/core/utils/nodeset-cache.go @@ -0,0 +1,245 @@ +// 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 +// <http://www.gnu.org/licenses/>. + +package utils + +import ( + "errors" + "sync" + + "github.com/byzantine-lab/dexon-consensus/common" + "github.com/byzantine-lab/dexon-consensus/core/crypto" + "github.com/byzantine-lab/dexon-consensus/core/types" +) + +var ( + // ErrNodeSetNotReady means we got nil empty node set. + ErrNodeSetNotReady = errors.New("node set is not ready") + // ErrCRSNotReady means we got empty CRS. + ErrCRSNotReady = errors.New("crs is not ready") + // ErrConfigurationNotReady means we go nil configuration. + ErrConfigurationNotReady = errors.New("configuration is not ready") +) + +type sets struct { + crs common.Hash + nodeSet *types.NodeSet + notarySet map[types.NodeID]struct{} +} + +// NodeSetCacheInterface interface specifies interface used by NodeSetCache. +type NodeSetCacheInterface interface { + // Configuration returns the configuration at a given round. + // Return the genesis configuration if round == 0. + Configuration(round uint64) *types.Config + + // CRS returns the CRS for a given round. + // Return the genesis CRS if round == 0. + CRS(round uint64) common.Hash + + // NodeSet returns the node set at a given round. + // Return the genesis node set if round == 0. + NodeSet(round uint64) []crypto.PublicKey +} + +// NodeSetCache caches node set information. +// +// NOTE: this module doesn't handle DKG resetting and can only be used along +// with utils.RoundEvent. +type NodeSetCache struct { + lock sync.RWMutex + nsIntf NodeSetCacheInterface + rounds map[uint64]*sets + keyPool map[types.NodeID]*struct { + pubKey crypto.PublicKey + refCnt int + } +} + +// NewNodeSetCache constructs an NodeSetCache instance. +func NewNodeSetCache(nsIntf NodeSetCacheInterface) *NodeSetCache { + return &NodeSetCache{ + nsIntf: nsIntf, + rounds: make(map[uint64]*sets), + keyPool: make(map[types.NodeID]*struct { + pubKey crypto.PublicKey + refCnt int + }), + } +} + +// Exists checks if a node is in node set of that round. +func (cache *NodeSetCache) Exists( + round uint64, nodeID types.NodeID) (exists bool, err error) { + + nIDs, exists := cache.get(round) + if !exists { + if nIDs, err = cache.update(round); err != nil { + return + } + } + _, exists = nIDs.nodeSet.IDs[nodeID] + return +} + +// GetPublicKey return public key for that node: +func (cache *NodeSetCache) GetPublicKey( + nodeID types.NodeID) (key crypto.PublicKey, exists bool) { + + cache.lock.RLock() + defer cache.lock.RUnlock() + + rec, exists := cache.keyPool[nodeID] + if exists { + key = rec.pubKey + } + return +} + +// GetNodeSet returns IDs of nodes set of this round as map. +func (cache *NodeSetCache) GetNodeSet(round uint64) (*types.NodeSet, error) { + IDs, exists := cache.get(round) + if !exists { + var err error + if IDs, err = cache.update(round); err != nil { + return nil, err + } + } + return IDs.nodeSet.Clone(), nil +} + +// GetNotarySet returns of notary set of this round. +func (cache *NodeSetCache) GetNotarySet( + round uint64) (map[types.NodeID]struct{}, error) { + IDs, err := cache.getOrUpdate(round) + if err != nil { + return nil, err + } + return cache.cloneMap(IDs.notarySet), nil +} + +// Purge a specific round. +func (cache *NodeSetCache) Purge(rID uint64) { + cache.lock.Lock() + defer cache.lock.Unlock() + nIDs, exist := cache.rounds[rID] + if !exist { + return + } + for nID := range nIDs.nodeSet.IDs { + rec := cache.keyPool[nID] + if rec.refCnt--; rec.refCnt == 0 { + delete(cache.keyPool, nID) + } + } + delete(cache.rounds, rID) +} + +// Touch updates the internal cache of round. +func (cache *NodeSetCache) Touch(round uint64) (err error) { + _, err = cache.update(round) + return +} + +func (cache *NodeSetCache) cloneMap( + nIDs map[types.NodeID]struct{}) map[types.NodeID]struct{} { + nIDsCopy := make(map[types.NodeID]struct{}, len(nIDs)) + for k := range nIDs { + nIDsCopy[k] = struct{}{} + } + return nIDsCopy +} + +func (cache *NodeSetCache) getOrUpdate(round uint64) (nIDs *sets, err error) { + s, exists := cache.get(round) + if !exists { + if s, err = cache.update(round); err != nil { + return + } + } + nIDs = s + return +} + +// update node set for that round. +// +// This cache would maintain 10 rounds before the updated round and purge +// rounds not in this range. +func (cache *NodeSetCache) update(round uint64) (nIDs *sets, err error) { + cache.lock.Lock() + defer cache.lock.Unlock() + // Get information for the requested round. + keySet := cache.nsIntf.NodeSet(round) + if keySet == nil { + err = ErrNodeSetNotReady + return + } + crs := cache.nsIntf.CRS(round) + if (crs == common.Hash{}) { + err = ErrCRSNotReady + return + } + // Cache new round. + nodeSet := types.NewNodeSet() + for _, key := range keySet { + nID := types.NewNodeID(key) + nodeSet.Add(nID) + if rec, exists := cache.keyPool[nID]; exists { + rec.refCnt++ + } else { + cache.keyPool[nID] = &struct { + pubKey crypto.PublicKey + refCnt int + }{key, 1} + } + } + cfg := cache.nsIntf.Configuration(round) + if cfg == nil { + err = ErrConfigurationNotReady + return + } + nIDs = &sets{ + crs: crs, + nodeSet: nodeSet, + notarySet: make(map[types.NodeID]struct{}), + } + nIDs.notarySet = nodeSet.GetSubSet( + int(cfg.NotarySetSize), types.NewNotarySetTarget(crs)) + cache.rounds[round] = nIDs + // Purge older rounds. + for rID, nIDs := range cache.rounds { + nodeSet := nIDs.nodeSet + if round-rID <= 5 { + continue + } + for nID := range nodeSet.IDs { + rec := cache.keyPool[nID] + if rec.refCnt--; rec.refCnt == 0 { + delete(cache.keyPool, nID) + } + } + delete(cache.rounds, rID) + } + return +} + +func (cache *NodeSetCache) get(round uint64) (nIDs *sets, exists bool) { + cache.lock.RLock() + defer cache.lock.RUnlock() + nIDs, exists = cache.rounds[round] + return +} |