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