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