account/utxo_keeper.go

   1 package account
   2
   3 import (
   4         "bytes"
   5         "container/list"
   6         "sort"
   7         "sync"
   8         "sync/atomic"
   9         "time"
  10
  11         log "github.com/sirupsen/logrus"
  12         "github.com/vapor/errors"
  13         "github.com/vapor/protocol/bc"
  14 )
  15
  16 const desireUtxoCount = 5
  17
  18 // pre-define error types
  19 var (
  20         ErrInsufficient = errors.New("reservation found insufficient funds")
  21         ErrImmature     = errors.New("reservation found immature funds")
  22         ErrVoteLock     = errors.New("Locked by the vote")
  23         ErrReserved     = errors.New("reservation found outputs already reserved")
  24         ErrMatchUTXO    = errors.New("can't find utxo with given hash")
  25         ErrReservation  = errors.New("couldn't find reservation")
  26 )
  27
  28 // UTXO describes an individual account utxo.
  29 type UTXO struct {
  30         OutputID            bc.Hash
  31         SourceID            bc.Hash
  32         AssetID             bc.AssetID
  33         Amount              uint64
  34         SourcePos           uint64
  35         ControlProgram      []byte
  36         Vote                []byte
  37         AccountID           string
  38         Address             string
  39         ControlProgramIndex uint64
  40         ValidHeight         uint64
  41         Change              bool
  42 }
  43
  44 // reservation describes a reservation of a set of UTXOs
  45 type reservation struct {
  46         id     uint64
  47         utxos  []*UTXO
  48         change uint64
  49         expiry time.Time
  50 }
  51
  52 type utxoKeeper struct {
  53         // `sync/atomic` expects the first word in an allocated struct to be 64-bit
  54         // aligned on both ARM and x86-32. See https://goo.gl/zW7dgq for more details.
  55         nextIndex     uint64
  56         store         AccountStore
  57         mtx           sync.RWMutex
  58         currentHeight func() uint64
  59
  60         unconfirmed  map[bc.Hash]*UTXO
  61         reserved     map[bc.Hash]uint64
  62         reservations map[uint64]*reservation
  63 }
  64
  65 func newUtxoKeeper(f func() uint64, store AccountStore) *utxoKeeper {
  66         uk := &utxoKeeper{
  67                 store:         store,
  68                 currentHeight: f,
  69                 unconfirmed:   make(map[bc.Hash]*UTXO),
  70                 reserved:      make(map[bc.Hash]uint64),
  71                 reservations:  make(map[uint64]*reservation),
  72         }
  73         go uk.expireWorker()
  74         return uk
  75 }
  76
  77 func (uk *utxoKeeper) AddUnconfirmedUtxo(utxos []*UTXO) {
  78         uk.mtx.Lock()
  79         defer uk.mtx.Unlock()
  80
  81         for _, utxo := range utxos {
  82                 uk.unconfirmed[utxo.OutputID] = utxo
  83         }
  84 }
  85
  86 // Cancel canceling the reservation with the provided ID.
  87 func (uk *utxoKeeper) Cancel(rid uint64) {
  88         uk.mtx.Lock()
  89         uk.cancel(rid)
  90         uk.mtx.Unlock()
  91 }
  92
  93 // ListUnconfirmed return all the unconfirmed utxos
  94 func (uk *utxoKeeper) ListUnconfirmed() []*UTXO {
  95         uk.mtx.Lock()
  96         defer uk.mtx.Unlock()
  97
  98         utxos := []*UTXO{}
  99         for _, utxo := range uk.unconfirmed {
 100                 utxos = append(utxos, utxo)
 101         }
 102         return utxos
 103 }
 104
 105 func (uk *utxoKeeper) RemoveUnconfirmedUtxo(hashes []*bc.Hash) {
 106         uk.mtx.Lock()
 107         defer uk.mtx.Unlock()
 108
 109         for _, hash := range hashes {
 110                 delete(uk.unconfirmed, *hash)
 111         }
 112 }
 113
 114 func (uk *utxoKeeper) Reserve(accountID string, assetID *bc.AssetID, amount uint64, useUnconfirmed bool, vote []byte, exp time.Time) (*reservation, error) {
 115         uk.mtx.Lock()
 116         defer uk.mtx.Unlock()
 117
 118         utxos, immatureAmount := uk.findUtxos(accountID, assetID, useUnconfirmed, vote)
 119         optUtxos, optAmount, reservedAmount := uk.optUTXOs(utxos, amount)
 120         if optAmount+reservedAmount+immatureAmount < amount {
 121                 return nil, ErrInsufficient
 122         }
 123
 124         if optAmount+reservedAmount < amount {
 125                 if vote != nil {
 126                         return nil, ErrVoteLock
 127                 }
 128                 return nil, ErrImmature
 129         }
 130
 131         if optAmount < amount {
 132                 return nil, ErrReserved
 133         }
 134
 135         result := &reservation{
 136                 id:     atomic.AddUint64(&uk.nextIndex, 1),
 137                 utxos:  optUtxos,
 138                 change: optAmount - amount,
 139                 expiry: exp,
 140         }
 141
 142         uk.reservations[result.id] = result
 143         for _, u := range optUtxos {
 144                 uk.reserved[u.OutputID] = result.id
 145         }
 146         return result, nil
 147 }
 148
 149 func (uk *utxoKeeper) ReserveParticular(outHash bc.Hash, useUnconfirmed bool, exp time.Time) (*reservation, error) {
 150         uk.mtx.Lock()
 151         defer uk.mtx.Unlock()
 152
 153         if _, ok := uk.reserved[outHash]; ok {
 154                 return nil, ErrReserved
 155         }
 156
 157         u, err := uk.findUtxo(outHash, useUnconfirmed)
 158         if err != nil {
 159                 return nil, err
 160         }
 161
 162         if u.ValidHeight > uk.currentHeight() {
 163                 return nil, ErrImmature
 164         }
 165
 166         result := &reservation{
 167                 id:     atomic.AddUint64(&uk.nextIndex, 1),
 168                 utxos:  []*UTXO{u},
 169                 expiry: exp,
 170         }
 171         uk.reservations[result.id] = result
 172         uk.reserved[u.OutputID] = result.id
 173         return result, nil
 174 }
 175
 176 func (uk *utxoKeeper) cancel(rid uint64) {
 177         res, ok := uk.reservations[rid]
 178         if !ok {
 179                 return
 180         }
 181
 182         delete(uk.reservations, rid)
 183         for _, utxo := range res.utxos {
 184                 delete(uk.reserved, utxo.OutputID)
 185         }
 186 }
 187
 188 func (uk *utxoKeeper) expireWorker() {
 189         ticker := time.NewTicker(1000 * time.Millisecond)
 190         defer ticker.Stop()
 191
 192         for now := range ticker.C {
 193                 uk.expireReservation(now)
 194         }
 195 }
 196
 197 func (uk *utxoKeeper) expireReservation(t time.Time) {
 198         uk.mtx.Lock()
 199         defer uk.mtx.Unlock()
 200
 201         for rid, res := range uk.reservations {
 202                 if res.expiry.Before(t) {
 203                         uk.cancel(rid)
 204                 }
 205         }
 206 }
 207
 208 func (uk *utxoKeeper) findUtxos(accountID string, assetID *bc.AssetID, useUnconfirmed bool, vote []byte) ([]*UTXO, uint64) {
 209         immatureAmount := uint64(0)
 210         currentHeight := uk.currentHeight()
 211         utxos := []*UTXO{}
 212         appendUtxo := func(u *UTXO) {
 213                 if u.AccountID != accountID || u.AssetID != *assetID || !bytes.Equal(u.Vote, vote) {
 214                         return
 215                 }
 216
 217                 if u.ValidHeight > currentHeight {
 218                         immatureAmount += u.Amount
 219                 } else {
 220                         utxos = append(utxos, u)
 221                 }
 222         }
 223
 224         UTXOs, err := uk.store.ListUTXOs()
 225         if err != nil {
 226                 log.WithFields(log.Fields{"module": logModule, "err": err}).Error("utxoKeeper findUtxos fail on unmarshal utxo")
 227         }
 228
 229         for _, UTXO := range UTXOs {
 230                 appendUtxo(UTXO)
 231         }
 232
 233         if !useUnconfirmed {
 234                 return utxos, immatureAmount
 235         }
 236
 237         for _, u := range uk.unconfirmed {
 238                 appendUtxo(u)
 239         }
 240         return utxos, immatureAmount
 241 }
 242
 243 func (uk *utxoKeeper) findUtxo(outHash bc.Hash, useUnconfirmed bool) (*UTXO, error) {
 244         if u, ok := uk.unconfirmed[outHash]; useUnconfirmed && ok {
 245                 return u, nil
 246         }
 247         return uk.store.GetUTXO(outHash)
 248 }
 249
 250 func (uk *utxoKeeper) optUTXOs(utxos []*UTXO, amount uint64) ([]*UTXO, uint64, uint64) {
 251         //sort the utxo by amount, bigger amount in front
 252         var optAmount, reservedAmount uint64
 253         sort.Slice(utxos, func(i, j int) bool {
 254                 return utxos[i].Amount > utxos[j].Amount
 255         })
 256
 257         //push all the available utxos into list
 258         utxoList := list.New()
 259         for _, u := range utxos {
 260                 if _, ok := uk.reserved[u.OutputID]; ok {
 261                         reservedAmount += u.Amount
 262                         continue
 263                 }
 264                 utxoList.PushBack(u)
 265         }
 266
 267         optList := list.New()
 268         for node := utxoList.Front(); node != nil; node = node.Next() {
 269                 //append utxo if we haven't reached the required amount
 270                 if optAmount < amount {
 271                         optList.PushBack(node.Value)
 272                         optAmount += node.Value.(*UTXO).Amount
 273                         continue
 274                 }
 275
 276                 largestNode := optList.Front()
 277                 replaceList := list.New()
 278                 replaceAmount := optAmount - largestNode.Value.(*UTXO).Amount
 279
 280                 for ; node != nil && replaceList.Len() <= desireUtxoCount-optList.Len(); node = node.Next() {
 281                         replaceList.PushBack(node.Value)
 282                         if replaceAmount += node.Value.(*UTXO).Amount; replaceAmount >= amount {
 283                                 optList.Remove(largestNode)
 284                                 optList.PushBackList(replaceList)
 285                                 optAmount = replaceAmount
 286                                 break
 287                         }
 288                 }
 289
 290                 //largestNode remaining the same means that there is nothing to be replaced
 291                 if largestNode == optList.Front() {
 292                         break
 293                 }
 294         }
 295
 296         optUtxos := []*UTXO{}
 297         for e := optList.Front(); e != nil; e = e.Next() {
 298                 optUtxos = append(optUtxos, e.Value.(*UTXO))
 299         }
 300         return optUtxos, optAmount, reservedAmount
 301 }