account/utxo_keeper.go

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