account/utxo_keeper.go

   1 package account
   2
   3 import (
   4         "bytes"
   5         "container/list"
   6         "sort"
   7         "sync"
   8         "sync/atomic"
   9         "time"
  10
  11         "github.com/vapor/errors"
  12         "github.com/vapor/protocol/bc"
  13 )
  14
  15 const desireUtxoCount = 5
  16
  17 // pre-define error types
  18 var (
  19         ErrInsufficient = errors.New("reservation found insufficient funds")
  20         ErrImmature     = errors.New("reservation found immature funds")
  21         ErrVoteLock     = errors.New("Locked by the vote")
  22         ErrReserved     = errors.New("reservation found outputs already reserved")
  23         ErrMatchUTXO    = errors.New("can't find utxo with given hash")
  24         ErrReservation  = errors.New("couldn't find reservation")
  25 )
  26
  27 // UTXO describes an individual account utxo.
  28 type UTXO struct {
  29         OutputID            bc.Hash
  30         SourceID            bc.Hash
  31         AssetID             bc.AssetID
  32         Amount              uint64
  33         SourcePos           uint64
  34         ControlProgram      []byte
  35         Vote                []byte
  36         AccountID           string
  37         Address             string
  38         ControlProgramIndex uint64
  39         ValidHeight         uint64
  40         Change              bool
  41 }
  42
  43 // reservation describes a reservation of a set of UTXOs
  44 type reservation struct {
  45         id     uint64
  46         utxos  []*UTXO
  47         change uint64
  48         expiry time.Time
  49 }
  50
  51 type utxoKeeper struct {
  52         // `sync/atomic` expects the first word in an allocated struct to be 64-bit
  53         // aligned on both ARM and x86-32. See https://goo.gl/zW7dgq for more details.
  54         nextIndex     uint64
  55         store         AccountStorer
  56         mtx           sync.RWMutex
  57         currentHeight func() uint64
  58
  59         unconfirmed  map[bc.Hash]*UTXO
  60         reserved     map[bc.Hash]uint64
  61         reservations map[uint64]*reservation
  62 }
  63
  64 func newUtxoKeeper(f func() uint64, store AccountStorer) *utxoKeeper {
  65         uk := &utxoKeeper{
  66                 store:         store,
  67                 currentHeight: f,
  68                 unconfirmed:   make(map[bc.Hash]*UTXO),
  69                 reserved:      make(map[bc.Hash]uint64),
  70                 reservations:  make(map[uint64]*reservation),
  71         }
  72         go uk.expireWorker()
  73         return uk
  74 }
  75
  76 func (uk *utxoKeeper) AddUnconfirmedUtxo(utxos []*UTXO) {
  77         uk.mtx.Lock()
  78         defer uk.mtx.Unlock()
  79
  80         for _, utxo := range utxos {
  81                 uk.unconfirmed[utxo.OutputID] = utxo
  82         }
  83 }
  84
  85 // Cancel canceling the reservation with the provided ID.
  86 func (uk *utxoKeeper) Cancel(rid uint64) {
  87         uk.mtx.Lock()
  88         uk.cancel(rid)
  89         uk.mtx.Unlock()
  90 }
  91
  92 // ListUnconfirmed return all the unconfirmed utxos
  93 func (uk *utxoKeeper) ListUnconfirmed() []*UTXO {
  94         uk.mtx.Lock()
  95         defer uk.mtx.Unlock()
  96
  97         utxos := []*UTXO{}
  98         for _, utxo := range uk.unconfirmed {
  99                 utxos = append(utxos, utxo)
 100         }
 101         return utxos
 102 }
 103
 104 func (uk *utxoKeeper) RemoveUnconfirmedUtxo(hashes []*bc.Hash) {
 105         uk.mtx.Lock()
 106         defer uk.mtx.Unlock()
 107
 108         for _, hash := range hashes {
 109                 delete(uk.unconfirmed, *hash)
 110         }
 111 }
 112
 113 func (uk *utxoKeeper) Reserve(accountID string, assetID *bc.AssetID, amount uint64, useUnconfirmed bool, vote []byte, exp time.Time) (*reservation, error) {
 114         uk.mtx.Lock()
 115         defer uk.mtx.Unlock()
 116
 117         utxos, immatureAmount := uk.findUtxos(accountID, assetID, useUnconfirmed, vote)
 118         optUtxos, optAmount, reservedAmount := uk.optUTXOs(utxos, amount)
 119         if optAmount+reservedAmount+immatureAmount < amount {
 120                 return nil, ErrInsufficient
 121         }
 122
 123         if optAmount+reservedAmount < amount {
 124                 if vote != nil {
 125                         return nil, ErrVoteLock
 126                 }
 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         UTXOs := uk.store.GetUTXOs()
 223         for _, UTXO := range UTXOs {
 224                 appendUtxo(UTXO)
 225         }
 226
 227         if !useUnconfirmed {
 228                 return utxos, immatureAmount
 229         }
 230
 231         for _, u := range uk.unconfirmed {
 232                 appendUtxo(u)
 233         }
 234         return utxos, immatureAmount
 235 }
 236
 237 func (uk *utxoKeeper) findUtxo(outHash bc.Hash, useUnconfirmed bool) (*UTXO, error) {
 238         if u, ok := uk.unconfirmed[outHash]; useUnconfirmed && ok {
 239                 return u, nil
 240         }
 241         return uk.store.GetUTXO(outHash)
 242 }
 243
 244 func (uk *utxoKeeper) optUTXOs(utxos []*UTXO, amount uint64) ([]*UTXO, uint64, uint64) {
 245         //sort the utxo by amount, bigger amount in front
 246         var optAmount, reservedAmount uint64
 247         sort.Slice(utxos, func(i, j int) bool {
 248                 return utxos[i].Amount > utxos[j].Amount
 249         })
 250
 251         //push all the available utxos into list
 252         utxoList := list.New()
 253         for _, u := range utxos {
 254                 if _, ok := uk.reserved[u.OutputID]; ok {
 255                         reservedAmount += u.Amount
 256                         continue
 257                 }
 258                 utxoList.PushBack(u)
 259         }
 260
 261         optList := list.New()
 262         for node := utxoList.Front(); node != nil; node = node.Next() {
 263                 //append utxo if we haven't reached the required amount
 264                 if optAmount < amount {
 265                         optList.PushBack(node.Value)
 266                         optAmount += node.Value.(*UTXO).Amount
 267                         continue
 268                 }
 269
 270                 largestNode := optList.Front()
 271                 replaceList := list.New()
 272                 replaceAmount := optAmount - largestNode.Value.(*UTXO).Amount
 273
 274                 for ; node != nil && replaceList.Len() <= desireUtxoCount-optList.Len(); node = node.Next() {
 275                         replaceList.PushBack(node.Value)
 276                         if replaceAmount += node.Value.(*UTXO).Amount; replaceAmount >= amount {
 277                                 optList.Remove(largestNode)
 278                                 optList.PushBackList(replaceList)
 279                                 optAmount = replaceAmount
 280                                 break
 281                         }
 282                 }
 283
 284                 //largestNode remaining the same means that there is nothing to be replaced
 285                 if largestNode == optList.Front() {
 286                         break
 287                 }
 288         }
 289
 290         optUtxos := []*UTXO{}
 291         for e := optList.Front(); e != nil; e = e.Next() {
 292                 optUtxos = append(optUtxos, e.Value.(*UTXO))
 293         }
 294         return optUtxos, optAmount, reservedAmount
 295 }