cmd, les, eth, eth/gasprice: using new gas price oracle (#13853)

* cmd, les, eth, eth/gasprice: using new gas price oracle

* eth/gasprice: renamed source file

* eth/gasprice: added security checks for gpo params

* eth/gasprice: fixed naming issues

* eth/gasprice: max limit, maxEmpty

4 files changed, 137 insertions, 358 deletions

diff --git a/eth/api_backend.go b/eth/api_backend.go
index 418a34435..61e184401 100644
--- a/eth/api_backend.go
+++ b/eth/api_backend.go
@@ -39,7 +39,7 @@ import (
 // EthApiBackend implements ethapi.Backend for full nodes
 type EthApiBackend struct {
 	eth *Ethereum
-	gpo *gasprice.GasPriceOracle
+	gpo *gasprice.Oracle
 }
 
 func (b *EthApiBackend) ChainConfig() *params.ChainConfig {
@@ -186,7 +186,7 @@ func (b *EthApiBackend) ProtocolVersion() int {
 }
 
 func (b *EthApiBackend) SuggestPrice(ctx context.Context) (*big.Int, error) {
-	return b.gpo.SuggestPrice(), nil
+	return b.gpo.SuggestPrice(ctx)
 }
 
 func (b *EthApiBackend) ChainDb() ethdb.Database {
diff --git a/eth/backend.go b/eth/backend.go
index af1d46a2c..f241d5f34 100644
--- a/eth/backend.go
+++ b/eth/backend.go
@@ -84,12 +84,8 @@ type Config struct {
 	MinerThreads int
 	SolcPath     string
 
-	GpoMinGasPrice          *big.Int
-	GpoMaxGasPrice          *big.Int
-	GpoFullBlockRatio       int
-	GpobaseStepDown         int
-	GpobaseStepUp           int
-	GpobaseCorrectionFactor int
+	GpoBlocks     int
+	GpoPercentile int
 
 	EnablePreimageRecording bool
 }
@@ -211,16 +207,13 @@ func New(ctx *node.ServiceContext, config *Config) (*Ethereum, error) {
 	eth.miner.SetGasPrice(config.GasPrice)
 	eth.miner.SetExtra(config.ExtraData)
 
-	gpoParams := &gasprice.GpoParams{
-		GpoMinGasPrice:          config.GpoMinGasPrice,
-		GpoMaxGasPrice:          config.GpoMaxGasPrice,
-		GpoFullBlockRatio:       config.GpoFullBlockRatio,
-		GpobaseStepDown:         config.GpobaseStepDown,
-		GpobaseStepUp:           config.GpobaseStepUp,
-		GpobaseCorrectionFactor: config.GpobaseCorrectionFactor,
+	eth.ApiBackend = &EthApiBackend{eth, nil}
+	gpoParams := gasprice.Config{
+		Blocks:     config.GpoBlocks,
+		Percentile: config.GpoPercentile,
+		Default:    config.GasPrice,
 	}
-	gpo := gasprice.NewGasPriceOracle(eth.blockchain, chainDb, eth.eventMux, gpoParams)
-	eth.ApiBackend = &EthApiBackend{eth, gpo}
+	eth.ApiBackend.gpo = gasprice.NewOracle(eth.ApiBackend, gpoParams)
 
 	return eth, nil
 }
diff --git a/eth/gasprice/gasprice.go b/eth/gasprice/gasprice.go
index 73951bce9..bac048c88 100644
--- a/eth/gasprice/gasprice.go
+++ b/eth/gasprice/gasprice.go
@@ -1,4 +1,4 @@
-// Copyright 2015 The go-ethereum Authors
+// Copyright 2016 The go-ethereum Authors
 // This file is part of the go-ethereum library.
 //
 // The go-ethereum library is free software: you can redistribute it and/or modify
@@ -17,212 +17,158 @@
 package gasprice
 
 import (
+	"context"
 	"math/big"
-	"math/rand"
+	"sort"
 	"sync"
 
-	"github.com/ethereum/go-ethereum/core"
-	"github.com/ethereum/go-ethereum/core/types"
-	"github.com/ethereum/go-ethereum/ethdb"
-	"github.com/ethereum/go-ethereum/event"
-	"github.com/ethereum/go-ethereum/log"
+	"github.com/ethereum/go-ethereum/common"
+	"github.com/ethereum/go-ethereum/internal/ethapi"
+	"github.com/ethereum/go-ethereum/params"
+	"github.com/ethereum/go-ethereum/rpc"
 )
 
-const (
-	gpoProcessPastBlocks = 100
+var maxPrice = big.NewInt(500 * params.Shannon)
 
-	// for testing
-	gpoDefaultBaseCorrectionFactor = 110
-	gpoDefaultMinGasPrice          = 10000000000000
-)
-
-type blockPriceInfo struct {
-	baseGasPrice *big.Int
-}
-
-type GpoParams struct {
-	GpoMinGasPrice          *big.Int
-	GpoMaxGasPrice          *big.Int
-	GpoFullBlockRatio       int
-	GpobaseStepDown         int
-	GpobaseStepUp           int
-	GpobaseCorrectionFactor int
+type Config struct {
+	Blocks     int
+	Percentile int
+	Default    *big.Int
 }
 
-// GasPriceOracle recommends gas prices based on the content of recent
-// blocks.
-type GasPriceOracle struct {
-	chain         *core.BlockChain
-	db            ethdb.Database
-	evmux         *event.TypeMux
-	params        *GpoParams
-	initOnce      sync.Once
-	minPrice      *big.Int
-	lastBaseMutex sync.Mutex
-	lastBase      *big.Int
-
-	// state of listenLoop
-	blocks                        map[uint64]*blockPriceInfo
-	firstProcessed, lastProcessed uint64
-	minBase                       *big.Int
+// Oracle recommends gas prices based on the content of recent
+// blocks. Suitable for both light and full clients.
+type Oracle struct {
+	backend   ethapi.Backend
+	lastHead  common.Hash
+	lastPrice *big.Int
+	cacheLock sync.RWMutex
+	fetchLock sync.Mutex
+
+	checkBlocks, maxEmpty, maxBlocks int
+	percentile                       int
 }
 
-// NewGasPriceOracle returns a new oracle.
-func NewGasPriceOracle(chain *core.BlockChain, db ethdb.Database, evmux *event.TypeMux, params *GpoParams) *GasPriceOracle {
-	minprice := params.GpoMinGasPrice
-	if minprice == nil {
-		minprice = big.NewInt(gpoDefaultMinGasPrice)
+// NewOracle returns a new oracle.
+func NewOracle(backend ethapi.Backend, params Config) *Oracle {
+	blocks := params.Blocks
+	if blocks < 1 {
+		blocks = 1
 	}
-	minbase := new(big.Int).Mul(minprice, big.NewInt(100))
-	if params.GpobaseCorrectionFactor > 0 {
-		minbase = minbase.Div(minbase, big.NewInt(int64(params.GpobaseCorrectionFactor)))
+	percent := params.Percentile
+	if percent < 0 {
+		percent = 0
 	}
-	return &GasPriceOracle{
-		chain:    chain,
-		db:       db,
-		evmux:    evmux,
-		params:   params,
-		blocks:   make(map[uint64]*blockPriceInfo),
-		minBase:  minbase,
-		minPrice: minprice,
-		lastBase: minprice,
+	if percent > 100 {
+		percent = 100
 	}
-}
-
-func (gpo *GasPriceOracle) init() {
-	gpo.initOnce.Do(func() {
-		gpo.processPastBlocks()
-		go gpo.listenLoop()
-	})
-}
-
-func (self *GasPriceOracle) processPastBlocks() {
-	last := int64(-1)
-	cblock := self.chain.CurrentBlock()
-	if cblock != nil {
-		last = int64(cblock.NumberU64())
-	}
-	first := int64(0)
-	if last > gpoProcessPastBlocks {
-		first = last - gpoProcessPastBlocks
-	}
-	self.firstProcessed = uint64(first)
-	for i := first; i <= last; i++ {
-		block := self.chain.GetBlockByNumber(uint64(i))
-		if block != nil {
-			self.processBlock(block)
-		}
+	return &Oracle{
+		backend:     backend,
+		lastPrice:   params.Default,
+		checkBlocks: blocks,
+		maxEmpty:    blocks / 2,
+		maxBlocks:   blocks * 5,
+		percentile:  percent,
 	}
-
 }
 
-func (self *GasPriceOracle) listenLoop() {
-	events := self.evmux.Subscribe(core.ChainEvent{}, core.ChainSplitEvent{})
-	defer events.Unsubscribe()
-
-	for event := range events.Chan() {
-		switch event := event.Data.(type) {
-		case core.ChainEvent:
-			self.processBlock(event.Block)
-		case core.ChainSplitEvent:
-			self.processBlock(event.Block)
+// SuggestPrice returns the recommended gas price.
+func (gpo *Oracle) SuggestPrice(ctx context.Context) (*big.Int, error) {
+	gpo.cacheLock.RLock()
+	lastHead := gpo.lastHead
+	lastPrice := gpo.lastPrice
+	gpo.cacheLock.RUnlock()
+
+	head, _ := gpo.backend.HeaderByNumber(ctx, rpc.LatestBlockNumber)
+	headHash := head.Hash()
+	if headHash == lastHead {
+		return lastPrice, nil
+	}
+
+	gpo.fetchLock.Lock()
+	defer gpo.fetchLock.Unlock()
+
+	// try checking the cache again, maybe the last fetch fetched what we need
+	gpo.cacheLock.RLock()
+	lastHead = gpo.lastHead
+	lastPrice = gpo.lastPrice
+	gpo.cacheLock.RUnlock()
+	if headHash == lastHead {
+		return lastPrice, nil
+	}
+
+	blockNum := head.Number.Uint64()
+	ch := make(chan getBlockPricesResult, gpo.checkBlocks)
+	sent := 0
+	exp := 0
+	var txPrices []*big.Int
+	for sent < gpo.checkBlocks && blockNum > 0 {
+		go gpo.getBlockPrices(ctx, blockNum, ch)
+		sent++
+		exp++
+		blockNum--
+	}
+	maxEmpty := gpo.maxEmpty
+	for exp > 0 {
+		res := <-ch
+		if res.err != nil {
+			return lastPrice, res.err
+		}
+		exp--
+		if len(res.prices) > 0 {
+			txPrices = append(txPrices, res.prices...)
+			continue
+		}
+		if maxEmpty > 0 {
+			maxEmpty--
+			continue
+		}
+		if blockNum > 0 && sent < gpo.maxBlocks {
+			go gpo.getBlockPrices(ctx, blockNum, ch)
+			sent++
+			exp++
+			blockNum--
 		}
 	}
-}
-
-func (self *GasPriceOracle) processBlock(block *types.Block) {
-	i := block.NumberU64()
-	if i > self.lastProcessed {
-		self.lastProcessed = i
-	}
-
-	lastBase := self.minPrice
-	bpl := self.blocks[i-1]
-	if bpl != nil {
-		lastBase = bpl.baseGasPrice
-	}
-	if lastBase == nil {
-		return
-	}
-
-	var corr int
-	lp := self.lowestPrice(block)
-	if lp == nil {
-		return
-	}
-
-	if lastBase.Cmp(lp) < 0 {
-		corr = self.params.GpobaseStepUp
-	} else {
-		corr = -self.params.GpobaseStepDown
-	}
-
-	crand := int64(corr * (900 + rand.Intn(201)))
-	newBase := new(big.Int).Mul(lastBase, big.NewInt(1000000+crand))
-	newBase.Div(newBase, big.NewInt(1000000))
-
-	if newBase.Cmp(self.minBase) < 0 {
-		newBase = self.minBase
+	price := lastPrice
+	if len(txPrices) > 0 {
+		sort.Sort(bigIntArray(txPrices))
+		price = txPrices[(len(txPrices)-1)*gpo.percentile/100]
 	}
-
-	bpi := self.blocks[i]
-	if bpi == nil {
-		bpi = &blockPriceInfo{}
-		self.blocks[i] = bpi
+	if price.Cmp(maxPrice) > 0 {
+		price = new(big.Int).Set(maxPrice)
 	}
-	bpi.baseGasPrice = newBase
-	self.lastBaseMutex.Lock()
-	self.lastBase = newBase
-	self.lastBaseMutex.Unlock()
 
-	log.Trace("Processed block, base price updated", "number", i, "base", newBase)
+	gpo.cacheLock.Lock()
+	gpo.lastHead = headHash
+	gpo.lastPrice = price
+	gpo.cacheLock.Unlock()
+	return price, nil
 }
 
-// returns the lowers possible price with which a tx was or could have been included
-func (self *GasPriceOracle) lowestPrice(block *types.Block) *big.Int {
-	gasUsed := big.NewInt(0)
-
-	receipts := core.GetBlockReceipts(self.db, block.Hash(), block.NumberU64())
-	if len(receipts) > 0 {
-		if cgu := receipts[len(receipts)-1].CumulativeGasUsed; cgu != nil {
-			gasUsed = receipts[len(receipts)-1].CumulativeGasUsed
-		}
-	}
+type getBlockPricesResult struct {
+	prices []*big.Int
+	err    error
+}
 
-	if new(big.Int).Mul(gasUsed, big.NewInt(100)).Cmp(new(big.Int).Mul(block.GasLimit(),
-		big.NewInt(int64(self.params.GpoFullBlockRatio)))) < 0 {
-		// block is not full, could have posted a tx with MinGasPrice
-		return big.NewInt(0)
+// getLowestPrice calculates the lowest transaction gas price in a given block
+// and sends it to the result channel. If the block is empty, price is nil.
+func (gpo *Oracle) getBlockPrices(ctx context.Context, blockNum uint64, ch chan getBlockPricesResult) {
+	block, err := gpo.backend.BlockByNumber(ctx, rpc.BlockNumber(blockNum))
+	if block == nil {
+		ch <- getBlockPricesResult{nil, err}
+		return
 	}
-
 	txs := block.Transactions()
-	if len(txs) == 0 {
-		return big.NewInt(0)
+	prices := make([]*big.Int, len(txs))
+	for i, tx := range txs {
+		prices[i] = tx.GasPrice()
 	}
-	// block is full, find smallest gasPrice
-	minPrice := txs[0].GasPrice()
-	for i := 1; i < len(txs); i++ {
-		price := txs[i].GasPrice()
-		if price.Cmp(minPrice) < 0 {
-			minPrice = price
-		}
-	}
-	return minPrice
+	ch <- getBlockPricesResult{prices, nil}
 }
 
-// SuggestPrice returns the recommended gas price.
-func (self *GasPriceOracle) SuggestPrice() *big.Int {
-	self.init()
-	self.lastBaseMutex.Lock()
-	price := new(big.Int).Set(self.lastBase)
-	self.lastBaseMutex.Unlock()
-
-	price.Mul(price, big.NewInt(int64(self.params.GpobaseCorrectionFactor)))
-	price.Div(price, big.NewInt(100))
-	if price.Cmp(self.minPrice) < 0 {
-		price.Set(self.minPrice)
-	} else if self.params.GpoMaxGasPrice != nil && price.Cmp(self.params.GpoMaxGasPrice) > 0 {
-		price.Set(self.params.GpoMaxGasPrice)
-	}
-	return price
-}
+type bigIntArray []*big.Int
+
+func (s bigIntArray) Len() int           { return len(s) }
+func (s bigIntArray) Less(i, j int) bool { return s[i].Cmp(s[j]) < 0 }
+func (s bigIntArray) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
diff --git a/eth/gasprice/lightprice.go b/eth/gasprice/lightprice.go
deleted file mode 100644
index 562c7dd97..000000000
--- a/eth/gasprice/lightprice.go
+++ /dev/null
@@ -1,160 +0,0 @@
-// Copyright 2016 The go-ethereum Authors
-// This file is part of the go-ethereum library.
-//
-// The go-ethereum library is free software: you can redistribute it and/or modify
-// it under the terms of the GNU Lesser General Public License as published by
-// the Free Software Foundation, either version 3 of the License, or
-// (at your option) any later version.
-//
-// The go-ethereum library is distributed in the hope that it will be useful,
-// but WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-// GNU Lesser General Public License for more details.
-//
-// You should have received a copy of the GNU Lesser General Public License
-// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
-
-package gasprice
-
-import (
-	"context"
-	"math/big"
-	"sort"
-	"sync"
-
-	"github.com/ethereum/go-ethereum/common"
-	"github.com/ethereum/go-ethereum/internal/ethapi"
-	"github.com/ethereum/go-ethereum/rpc"
-)
-
-const (
-	LpoAvgCount     = 5
-	LpoMinCount     = 3
-	LpoMaxBlocks    = 20
-	LpoSelect       = 50
-	LpoDefaultPrice = 20000000000
-)
-
-// LightPriceOracle recommends gas prices based on the content of recent
-// blocks. Suitable for both light and full clients.
-type LightPriceOracle struct {
-	backend   ethapi.Backend
-	lastHead  common.Hash
-	lastPrice *big.Int
-	cacheLock sync.RWMutex
-	fetchLock sync.Mutex
-}
-
-// NewLightPriceOracle returns a new oracle.
-func NewLightPriceOracle(backend ethapi.Backend) *LightPriceOracle {
-	return &LightPriceOracle{
-		backend:   backend,
-		lastPrice: big.NewInt(LpoDefaultPrice),
-	}
-}
-
-// SuggestPrice returns the recommended gas price.
-func (self *LightPriceOracle) SuggestPrice(ctx context.Context) (*big.Int, error) {
-	self.cacheLock.RLock()
-	lastHead := self.lastHead
-	lastPrice := self.lastPrice
-	self.cacheLock.RUnlock()
-
-	head, _ := self.backend.HeaderByNumber(ctx, rpc.LatestBlockNumber)
-	headHash := head.Hash()
-	if headHash == lastHead {
-		return lastPrice, nil
-	}
-
-	self.fetchLock.Lock()
-	defer self.fetchLock.Unlock()
-
-	// try checking the cache again, maybe the last fetch fetched what we need
-	self.cacheLock.RLock()
-	lastHead = self.lastHead
-	lastPrice = self.lastPrice
-	self.cacheLock.RUnlock()
-	if headHash == lastHead {
-		return lastPrice, nil
-	}
-
-	blockNum := head.Number.Uint64()
-	chn := make(chan lpResult, LpoMaxBlocks)
-	sent := 0
-	exp := 0
-	var lps bigIntArray
-	for sent < LpoAvgCount && blockNum > 0 {
-		go self.getLowestPrice(ctx, blockNum, chn)
-		sent++
-		exp++
-		blockNum--
-	}
-	maxEmpty := LpoAvgCount - LpoMinCount
-	for exp > 0 {
-		res := <-chn
-		if res.err != nil {
-			return nil, res.err
-		}
-		exp--
-		if res.price != nil {
-			lps = append(lps, res.price)
-		} else {
-			if maxEmpty > 0 {
-				maxEmpty--
-			} else {
-				if blockNum > 0 && sent < LpoMaxBlocks {
-					go self.getLowestPrice(ctx, blockNum, chn)
-					sent++
-					exp++
-					blockNum--
-				}
-			}
-		}
-	}
-	price := lastPrice
-	if len(lps) > 0 {
-		sort.Sort(lps)
-		price = lps[(len(lps)-1)*LpoSelect/100]
-	}
-
-	self.cacheLock.Lock()
-	self.lastHead = headHash
-	self.lastPrice = price
-	self.cacheLock.Unlock()
-	return price, nil
-}
-
-type lpResult struct {
-	price *big.Int
-	err   error
-}
-
-// getLowestPrice calculates the lowest transaction gas price in a given block
-// and sends it to the result channel. If the block is empty, price is nil.
-func (self *LightPriceOracle) getLowestPrice(ctx context.Context, blockNum uint64, chn chan lpResult) {
-	block, err := self.backend.BlockByNumber(ctx, rpc.BlockNumber(blockNum))
-	if block == nil {
-		chn <- lpResult{nil, err}
-		return
-	}
-	txs := block.Transactions()
-	if len(txs) == 0 {
-		chn <- lpResult{nil, nil}
-		return
-	}
-	// find smallest gasPrice
-	minPrice := txs[0].GasPrice()
-	for i := 1; i < len(txs); i++ {
-		price := txs[i].GasPrice()
-		if price.Cmp(minPrice) < 0 {
-			minPrice = price
-		}
-	}
-	chn <- lpResult{minPrice, nil}
-}
-
-type bigIntArray []*big.Int
-
-func (s bigIntArray) Len() int           { return len(s) }
-func (s bigIntArray) Less(i, j int) bool { return s[i].Cmp(s[j]) < 0 }
-func (s bigIntArray) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }