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         dbm "github.com/vapor/database/leveldb"
  15         "github.com/vapor/errors"
  16         "github.com/vapor/protocol/bc"
  17 )
  18
  19 const desireUtxoCount = 5
  20
  21 // pre-define error types
  22 var (
  23         ErrInsufficient = errors.New("reservation found insufficient funds")
  24         ErrImmature     = errors.New("reservation found immature funds")
  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         db            dbm.DB
  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, walletdb dbm.DB) *utxoKeeper {
  68         uk := &utxoKeeper{
  69                 db:            walletdb,
  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                 return nil, ErrImmature
 128         }
 129
 130         if optAmount < amount {
 131                 return nil, ErrReserved
 132         }
 133
 134         result := &reservation{
 135                 id:     atomic.AddUint64(&uk.nextIndex, 1),
 136                 utxos:  optUtxos,
 137                 change: optAmount - amount,
 138                 expiry: exp,
 139         }
 140
 141         uk.reservations[result.id] = result
 142         for _, u := range optUtxos {
 143                 uk.reserved[u.OutputID] = result.id
 144         }
 145         return result, nil
 146 }
 147
 148 func (uk *utxoKeeper) ReserveParticular(outHash bc.Hash, useUnconfirmed bool, exp time.Time) (*reservation, error) {
 149         uk.mtx.Lock()
 150         defer uk.mtx.Unlock()
 151
 152         if _, ok := uk.reserved[outHash]; ok {
 153                 return nil, ErrReserved
 154         }
 155
 156         u, err := uk.findUtxo(outHash, useUnconfirmed)
 157         if err != nil {
 158                 return nil, err
 159         }
 160
 161         if u.ValidHeight > uk.currentHeight() {
 162                 return nil, ErrImmature
 163         }
 164
 165         result := &reservation{
 166                 id:     atomic.AddUint64(&uk.nextIndex, 1),
 167                 utxos:  []*UTXO{u},
 168                 expiry: exp,
 169         }
 170         uk.reservations[result.id] = result
 171         uk.reserved[u.OutputID] = result.id
 172         return result, nil
 173 }
 174
 175 func (uk *utxoKeeper) cancel(rid uint64) {
 176         res, ok := uk.reservations[rid]
 177         if !ok {
 178                 return
 179         }
 180
 181         delete(uk.reservations, rid)
 182         for _, utxo := range res.utxos {
 183                 delete(uk.reserved, utxo.OutputID)
 184         }
 185 }
 186
 187 func (uk *utxoKeeper) expireWorker() {
 188         ticker := time.NewTicker(1000 * time.Millisecond)
 189         defer ticker.Stop()
 190
 191         for now := range ticker.C {
 192                 uk.expireReservation(now)
 193         }
 194 }
 195
 196 func (uk *utxoKeeper) expireReservation(t time.Time) {
 197         uk.mtx.Lock()
 198         defer uk.mtx.Unlock()
 199
 200         for rid, res := range uk.reservations {
 201                 if res.expiry.Before(t) {
 202                         uk.cancel(rid)
 203                 }
 204         }
 205 }
 206
 207 func (uk *utxoKeeper) findUtxos(accountID string, assetID *bc.AssetID, useUnconfirmed bool, vote []byte) ([]*UTXO, uint64) {
 208         immatureAmount := uint64(0)
 209         currentHeight := uk.currentHeight()
 210         utxos := []*UTXO{}
 211         appendUtxo := func(u *UTXO) {
 212                 if u.AccountID != accountID || u.AssetID != *assetID || !bytes.Equal(u.Vote, vote) {
 213                         return
 214                 }
 215                 if u.ValidHeight > currentHeight {
 216                         immatureAmount += u.Amount
 217                 } else {
 218                         utxos = append(utxos, u)
 219                 }
 220         }
 221
 222         utxoIter := uk.db.IteratorPrefix([]byte(UTXOPreFix))
 223         defer utxoIter.Release()
 224         for utxoIter.Next() {
 225                 u := &UTXO{}
 226                 if err := json.Unmarshal(utxoIter.Value(), u); err != nil {
 227                         log.WithFields(log.Fields{"module": logModule, "err": err}).Error("utxoKeeper findUtxos fail on unmarshal utxo")
 228                         continue
 229                 }
 230                 appendUtxo(u)
 231         }
 232         if !useUnconfirmed {
 233                 return utxos, immatureAmount
 234         }
 235
 236         for _, u := range uk.unconfirmed {
 237                 appendUtxo(u)
 238         }
 239         return utxos, immatureAmount
 240 }
 241
 242 func (uk *utxoKeeper) findUtxo(outHash bc.Hash, useUnconfirmed bool) (*UTXO, error) {
 243         if u, ok := uk.unconfirmed[outHash]; useUnconfirmed && ok {
 244                 return u, nil
 245         }
 246
 247         u := &UTXO{}
 248         if data := uk.db.Get(StandardUTXOKey(outHash)); data != nil {
 249                 return u, json.Unmarshal(data, u)
 250         }
 251         if data := uk.db.Get(ContractUTXOKey(outHash)); data != nil {
 252                 return u, json.Unmarshal(data, u)
 253         }
 254         return nil, ErrMatchUTXO
 255 }
 256
 257 func (uk *utxoKeeper) optUTXOs(utxos []*UTXO, amount uint64) ([]*UTXO, uint64, uint64) {
 258         //sort the utxo by amount, bigger amount in front
 259         var optAmount, reservedAmount uint64
 260         sort.Slice(utxos, func(i, j int) bool {
 261                 return utxos[i].Amount > utxos[j].Amount
 262         })
 263
 264         //push all the available utxos into list
 265         utxoList := list.New()
 266         for _, u := range utxos {
 267                 if _, ok := uk.reserved[u.OutputID]; ok {
 268                         reservedAmount += u.Amount
 269                         continue
 270                 }
 271                 utxoList.PushBack(u)
 272         }
 273
 274         optList := list.New()
 275         for node := utxoList.Front(); node != nil; node = node.Next() {
 276                 //append utxo if we haven't reached the required amount
 277                 if optAmount < amount {
 278                         optList.PushBack(node.Value)
 279                         optAmount += node.Value.(*UTXO).Amount
 280                         continue
 281                 }
 282
 283                 largestNode := optList.Front()
 284                 replaceList := list.New()
 285                 replaceAmount := optAmount - largestNode.Value.(*UTXO).Amount
 286
 287                 for ; node != nil && replaceList.Len() <= desireUtxoCount-optList.Len(); node = node.Next() {
 288                         replaceList.PushBack(node.Value)
 289                         if replaceAmount += node.Value.(*UTXO).Amount; replaceAmount >= amount {
 290                                 optList.Remove(largestNode)
 291                                 optList.PushBackList(replaceList)
 292                                 optAmount = replaceAmount
 293                                 break
 294                         }
 295                 }
 296
 297                 //largestNode remaining the same means that there is nothing to be replaced
 298                 if largestNode == optList.Front() {
 299                         break
 300                 }
 301         }
 302
 303         optUtxos := []*UTXO{}
 304         for e := optList.Front(); e != nil; e = e.Next() {
 305                 optUtxos = append(optUtxos, e.Value.(*UTXO))
 306         }
 307         return optUtxos, optAmount, reservedAmount
 308 }