account/utxo_keeper.go

   1 package account
   2
   3 import (
   4         "container/list"
   5         "encoding/json"
   6         "sort"
   7         "sync"
   8         "sync/atomic"
   9         "time"
  10
  11         log "github.com/sirupsen/logrus"
  12         dbm "github.com/tendermint/tmlibs/db"
  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         ErrReserved     = errors.New("reservation found outputs already reserved")
  25         ErrMatchUTXO    = errors.New("can't find utxo with given hash")
  26         ErrReservation  = errors.New("couldn't find reservation")
  27 )
  28
  29 // UTXO describes an individual account utxo.
  30 type UTXO struct {
  31         OutputID            bc.Hash
  32         SourceID            bc.Hash
  33         AssetID             bc.AssetID
  34         Amount              uint64
  35         SourcePos           uint64
  36         ControlProgram      []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         db            dbm.DB
  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, walletdb dbm.DB) *utxoKeeper {
  66         uk := &utxoKeeper{
  67                 db:            walletdb,
  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, exp time.Time) (*reservation, error) {
 115         uk.mtx.Lock()
 116         defer uk.mtx.Unlock()
 117
 118         utxos, immatureAmount := uk.findUtxos(accountID, assetID, useUnconfirmed)
 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                 return nil, ErrImmature
 126         }
 127
 128         if optAmount < amount {
 129                 return nil, ErrReserved
 130         }
 131
 132         result := &reservation{
 133                 id:     atomic.AddUint64(&uk.nextIndex, 1),
 134                 utxos:  optUtxos,
 135                 change: optAmount - amount,
 136                 expiry: exp,
 137         }
 138
 139         uk.reservations[result.id] = result
 140         for _, u := range optUtxos {
 141                 uk.reserved[u.OutputID] = result.id
 142         }
 143         return result, nil
 144 }
 145
 146 func (uk *utxoKeeper) ReserveByAddress(address string, assetID *bc.AssetID, amount uint64, useUnconfirmed bool, isReserved bool) (*reservation, error) {
 147         uk.mtx.Lock()
 148         defer uk.mtx.Unlock()
 149
 150         utxos, immatureAmount := uk.findUtxosByAddress(address, assetID, useUnconfirmed)
 151         optUtxos, optAmount, reservedAmount := uk.optUTXOs(utxos, amount)
 152         if optAmount+reservedAmount+immatureAmount < amount {
 153                 return nil, ErrInsufficient
 154         }
 155         if optAmount+reservedAmount < amount {
 156                 return nil, ErrImmature
 157         }
 158
 159         if optAmount < amount {
 160                 return nil, ErrReserved
 161         }
 162
 163         result := &reservation{
 164                 id:     atomic.AddUint64(&uk.nextIndex, 1),
 165                 utxos:  optUtxos,
 166                 change: optAmount - amount,
 167         }
 168
 169         uk.reservations[result.id] = result
 170         if isReserved {
 171                 for _, u := range optUtxos {
 172                         uk.reserved[u.OutputID] = result.id
 173                 }
 174         }
 175
 176         return result, nil
 177 }
 178
 179 func (uk *utxoKeeper) ReserveParticular(outHash bc.Hash, useUnconfirmed bool, exp time.Time) (*reservation, error) {
 180         uk.mtx.Lock()
 181         defer uk.mtx.Unlock()
 182
 183         if _, ok := uk.reserved[outHash]; ok {
 184                 return nil, ErrReserved
 185         }
 186
 187         u, err := uk.findUtxo(outHash, useUnconfirmed)
 188         if err != nil {
 189                 return nil, err
 190         }
 191
 192         if u.ValidHeight > uk.currentHeight() {
 193                 return nil, ErrImmature
 194         }
 195
 196         result := &reservation{
 197                 id:     atomic.AddUint64(&uk.nextIndex, 1),
 198                 utxos:  []*UTXO{u},
 199                 expiry: exp,
 200         }
 201         uk.reservations[result.id] = result
 202         uk.reserved[u.OutputID] = result.id
 203         return result, nil
 204 }
 205
 206 func (uk *utxoKeeper) cancel(rid uint64) {
 207         res, ok := uk.reservations[rid]
 208         if !ok {
 209                 return
 210         }
 211
 212         delete(uk.reservations, rid)
 213         for _, utxo := range res.utxos {
 214                 delete(uk.reserved, utxo.OutputID)
 215         }
 216 }
 217
 218 func (uk *utxoKeeper) expireWorker() {
 219         ticker := time.NewTicker(1000 * time.Millisecond)
 220         for now := range ticker.C {
 221                 uk.expireReservation(now)
 222         }
 223 }
 224 func (uk *utxoKeeper) expireReservation(t time.Time) {
 225         uk.mtx.Lock()
 226         defer uk.mtx.Unlock()
 227
 228         for rid, res := range uk.reservations {
 229                 if res.expiry.Before(t) {
 230                         uk.cancel(rid)
 231                 }
 232         }
 233 }
 234
 235 func (uk *utxoKeeper) findUtxos(accountID string, assetID *bc.AssetID, useUnconfirmed bool) ([]*UTXO, uint64) {
 236         immatureAmount := uint64(0)
 237         currentHeight := uk.currentHeight()
 238         utxos := []*UTXO{}
 239         appendUtxo := func(u *UTXO) {
 240                 if u.AccountID != accountID || u.AssetID != *assetID {
 241                         return
 242                 }
 243                 if u.ValidHeight > currentHeight {
 244                         immatureAmount += u.Amount
 245                 } else {
 246                         utxos = append(utxos, u)
 247                 }
 248         }
 249
 250         utxoIter := uk.db.IteratorPrefix([]byte(UTXOPreFix))
 251         defer utxoIter.Release()
 252         for utxoIter.Next() {
 253                 u := &UTXO{}
 254                 if err := json.Unmarshal(utxoIter.Value(), u); err != nil {
 255                         log.WithField("err", err).Error("utxoKeeper findUtxos fail on unmarshal utxo")
 256                         continue
 257                 }
 258                 appendUtxo(u)
 259         }
 260         if !useUnconfirmed {
 261                 return utxos, immatureAmount
 262         }
 263
 264         for _, u := range uk.unconfirmed {
 265                 appendUtxo(u)
 266         }
 267         return utxos, immatureAmount
 268 }
 269
 270 func (uk *utxoKeeper) findUtxosByAddress(address string, assetID *bc.AssetID, useUnconfirmed bool) ([]*UTXO, uint64) {
 271         immatureAmount := uint64(0)
 272         currentHeight := uk.currentHeight()
 273         utxos := []*UTXO{}
 274         appendUtxo := func(u *UTXO) {
 275                 if u.Address != address || u.AssetID != *assetID {
 276                         return
 277                 }
 278                 if u.ValidHeight > currentHeight {
 279                         immatureAmount += u.Amount
 280                 } else {
 281                         utxos = append(utxos, u)
 282                 }
 283         }
 284
 285         utxoIter := uk.db.IteratorPrefix([]byte(UTXOPreFix))
 286         defer utxoIter.Release()
 287         for utxoIter.Next() {
 288                 u := &UTXO{}
 289                 if err := json.Unmarshal(utxoIter.Value(), u); err != nil {
 290                         log.WithField("err", err).Error("utxoKeeper findUtxos fail on unmarshal utxo")
 291                         continue
 292                 }
 293                 appendUtxo(u)
 294         }
 295         if !useUnconfirmed {
 296                 return utxos, immatureAmount
 297         }
 298
 299         for _, u := range uk.unconfirmed {
 300                 appendUtxo(u)
 301         }
 302         return utxos, immatureAmount
 303 }
 304
 305 func (uk *utxoKeeper) findUtxo(outHash bc.Hash, useUnconfirmed bool) (*UTXO, error) {
 306         if u, ok := uk.unconfirmed[outHash]; useUnconfirmed && ok {
 307                 return u, nil
 308         }
 309
 310         u := &UTXO{}
 311         if data := uk.db.Get(StandardUTXOKey(outHash)); data != nil {
 312                 return u, json.Unmarshal(data, u)
 313         }
 314         if data := uk.db.Get(ContractUTXOKey(outHash)); data != nil {
 315                 return u, json.Unmarshal(data, u)
 316         }
 317         return nil, ErrMatchUTXO
 318 }
 319
 320 func (uk *utxoKeeper) optUTXOs(utxos []*UTXO, amount uint64) ([]*UTXO, uint64, uint64) {
 321         //sort the utxo by amount, bigger amount in front
 322         var optAmount, reservedAmount uint64
 323         sort.Slice(utxos, func(i, j int) bool {
 324                 return utxos[i].Amount > utxos[j].Amount
 325         })
 326
 327         //push all the available utxos into list
 328         utxoList := list.New()
 329         for _, u := range utxos {
 330                 if _, ok := uk.reserved[u.OutputID]; ok {
 331                         reservedAmount += u.Amount
 332                         continue
 333                 }
 334                 utxoList.PushBack(u)
 335         }
 336
 337         optList := list.New()
 338         for node := utxoList.Front(); node != nil; node = node.Next() {
 339                 //append utxo if we haven't reached the required amount
 340                 if optAmount < amount {
 341                         optList.PushBack(node.Value)
 342                         optAmount += node.Value.(*UTXO).Amount
 343                         continue
 344                 }
 345
 346                 largestNode := optList.Front()
 347                 replaceList := list.New()
 348                 replaceAmount := optAmount - largestNode.Value.(*UTXO).Amount
 349
 350                 for ; node != nil && replaceList.Len() <= desireUtxoCount-optList.Len(); node = node.Next() {
 351                         replaceList.PushBack(node.Value)
 352                         if replaceAmount += node.Value.(*UTXO).Amount; replaceAmount >= amount {
 353                                 optList.Remove(largestNode)
 354                                 optList.PushBackList(replaceList)
 355                                 optAmount = replaceAmount
 356                                 break
 357                         }
 358                 }
 359
 360                 //largestNode remaining the same means that there is nothing to be replaced
 361                 if largestNode == optList.Front() {
 362                         break
 363                 }
 364         }
 365
 366         optUtxos := []*UTXO{}
 367         for e := optList.Front(); e != nil; e = e.Next() {
 368                 optUtxos = append(optUtxos, e.Value.(*UTXO))
 369         }
 370         return optUtxos, optAmount, reservedAmount
 371 }