protocol/orphan_manage.go

   1 package protocol
   2
   3 import (
   4         "sync"
   5         "time"
   6
   7         log "github.com/sirupsen/logrus"
   8
   9         "github.com/vapor/protocol/bc"
  10         "github.com/vapor/protocol/bc/types"
  11 )
  12
  13 var (
  14         orphanBlockTTL           = 3 * time.Minute
  15         orphanExpireWorkInterval = 1 * time.Minute
  16         numOrphanBlockLimit      = 256
  17 )
  18
  19 type orphanBlock struct {
  20         *types.Block
  21         expiration time.Time
  22 }
  23
  24 // OrphanManage is use to handle all the orphan block
  25 type OrphanManage struct {
  26         orphan      map[bc.Hash]*orphanBlock
  27         prevOrphans map[bc.Hash][]*bc.Hash
  28         mtx         sync.RWMutex
  29 }
  30
  31 // NewOrphanManage return a new orphan block
  32 func NewOrphanManage() *OrphanManage {
  33         o := &OrphanManage{
  34                 orphan:      make(map[bc.Hash]*orphanBlock),
  35                 prevOrphans: make(map[bc.Hash][]*bc.Hash),
  36         }
  37
  38         go o.orphanExpireWorker()
  39         return o
  40 }
  41
  42 // BlockExist check is the block in OrphanManage
  43 func (o *OrphanManage) BlockExist(hash *bc.Hash) bool {
  44         o.mtx.RLock()
  45         _, ok := o.orphan[*hash]
  46         o.mtx.RUnlock()
  47         return ok
  48 }
  49
  50 // Add will add the block to OrphanManage
  51 func (o *OrphanManage) Add(block *types.Block) {
  52         blockHash := block.Hash()
  53         o.mtx.Lock()
  54         defer o.mtx.Unlock()
  55
  56         if _, ok := o.orphan[blockHash]; ok {
  57                 return
  58         }
  59
  60         if len(o.orphan) >= numOrphanBlockLimit {
  61                 o.deleteLRU()
  62                 log.WithFields(log.Fields{"module": logModule, "hash": blockHash.String(), "height": block.Height}).Info("the number of orphan blocks exceeds the limit")
  63         }
  64
  65         o.orphan[blockHash] = &orphanBlock{block, time.Now().Add(orphanBlockTTL)}
  66         o.prevOrphans[block.PreviousBlockHash] = append(o.prevOrphans[block.PreviousBlockHash], &blockHash)
  67
  68         log.WithFields(log.Fields{"module": logModule, "hash": blockHash.String(), "height": block.Height}).Info("add block to orphan")
  69 }
  70
  71 // Delete will delete the block from OrphanManage
  72 func (o *OrphanManage) Delete(hash *bc.Hash) {
  73         o.mtx.Lock()
  74         defer o.mtx.Unlock()
  75         o.delete(hash)
  76 }
  77
  78 // Get return the orphan block by hash
  79 func (o *OrphanManage) Get(hash *bc.Hash) (*types.Block, bool) {
  80         o.mtx.RLock()
  81         block, ok := o.orphan[*hash]
  82         o.mtx.RUnlock()
  83         return block.Block, ok
  84 }
  85
  86 // GetPrevOrphans return the list of child orphans
  87 func (o *OrphanManage) GetPrevOrphans(hash *bc.Hash) ([]*bc.Hash, bool) {
  88         o.mtx.RLock()
  89         prevOrphans, ok := o.prevOrphans[*hash]
  90         o.mtx.RUnlock()
  91         return prevOrphans, ok
  92 }
  93
  94 func (o *OrphanManage) delete(hash *bc.Hash) {
  95         block, ok := o.orphan[*hash]
  96         if !ok {
  97                 return
  98         }
  99         delete(o.orphan, *hash)
 100
 101         prevOrphans, ok := o.prevOrphans[block.Block.PreviousBlockHash]
 102         if !ok || len(prevOrphans) == 1 {
 103                 delete(o.prevOrphans, block.Block.PreviousBlockHash)
 104                 return
 105         }
 106
 107         for i, preOrphan := range prevOrphans {
 108                 if *preOrphan == *hash {
 109                         o.prevOrphans[block.Block.PreviousBlockHash] = append(prevOrphans[:i], prevOrphans[i+1:]...)
 110                         return
 111                 }
 112         }
 113 }
 114
 115 func (o *OrphanManage) deleteLRU() {
 116         var deleteBlock *orphanBlock
 117         for _, orphan := range o.orphan {
 118                 if deleteBlock == nil || orphan.expiration.Before(deleteBlock.expiration) {
 119                         deleteBlock = orphan
 120                 }
 121         }
 122
 123         if deleteBlock != nil {
 124                 blockHash := deleteBlock.Block.Hash()
 125                 o.delete(&blockHash)
 126         }
 127 }
 128
 129 func (o *OrphanManage) orphanExpireWorker() {
 130         ticker := time.NewTicker(orphanExpireWorkInterval)
 131         for now := range ticker.C {
 132                 o.orphanExpire(now)
 133         }
 134         ticker.Stop()
 135 }
 136
 137 func (o *OrphanManage) orphanExpire(now time.Time) {
 138         o.mtx.Lock()
 139         defer o.mtx.Unlock()
 140         for hash, orphan := range o.orphan {
 141                 if orphan.expiration.Before(now) {
 142                         o.delete(&hash)
 143                 }
 144         }
 145 }