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