123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270 |
- // Copyright 2020 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 utils
- import (
- "math"
- "sync"
- "github.com/ethereum/go-ethereum/common/mclock"
- )
- // ExpiredValue is a scalar value that is continuously expired (decreased
- // exponentially) based on the provided logarithmic expiration offset value.
- //
- // The formula for value calculation is: base*2^(exp-logOffset). In order to
- // simplify the calculation of ExpiredValue, its value is expressed in the form
- // of an exponent with a base of 2.
- //
- // Also here is a trick to reduce a lot of calculations. In theory, when a value X
- // decays over time and then a new value Y is added, the final result should be
- // X*2^(exp-logOffset)+Y. However it's very hard to represent in memory.
- // So the trick is using the idea of inflation instead of exponential decay. At this
- // moment the temporary value becomes: X*2^exp+Y*2^logOffset_1, apply the exponential
- // decay when we actually want to calculate the value.
- //
- // e.g.
- // t0: V = 100
- // t1: add 30, inflationary value is: 100 + 30/0.3, 0.3 is the decay coefficient
- // t2: get value, decay coefficient is 0.2 now, final result is: 200*0.2 = 40
- type ExpiredValue struct {
- Base, Exp uint64 // rlp encoding works by default
- }
- // ExpirationFactor is calculated from logOffset. 1 <= Factor < 2 and Factor*2^Exp
- // describes the multiplier applicable for additions and the divider for readouts.
- // If logOffset changes slowly then it saves some expensive operations to not calculate
- // them for each addition and readout but cache this intermediate form for some time.
- // It is also useful for structures where multiple values are expired with the same
- // Expirer.
- type ExpirationFactor struct {
- Exp uint64
- Factor float64
- }
- // ExpFactor calculates ExpirationFactor based on logOffset
- func ExpFactor(logOffset Fixed64) ExpirationFactor {
- return ExpirationFactor{Exp: logOffset.ToUint64(), Factor: logOffset.Fraction().Pow2()}
- }
- // Value calculates the expired value based on a floating point base and integer
- // power-of-2 exponent. This function should be used by multi-value expired structures.
- func (e ExpirationFactor) Value(base float64, exp uint64) float64 {
- return base / e.Factor * math.Pow(2, float64(int64(exp-e.Exp)))
- }
- // value calculates the value at the given moment.
- func (e ExpiredValue) Value(logOffset Fixed64) uint64 {
- offset := Uint64ToFixed64(e.Exp) - logOffset
- return uint64(float64(e.Base) * offset.Pow2())
- }
- // add adds a signed value at the given moment
- func (e *ExpiredValue) Add(amount int64, logOffset Fixed64) int64 {
- integer, frac := logOffset.ToUint64(), logOffset.Fraction()
- factor := frac.Pow2()
- base := factor * float64(amount)
- if integer < e.Exp {
- base /= math.Pow(2, float64(e.Exp-integer))
- }
- if integer > e.Exp {
- e.Base >>= (integer - e.Exp)
- e.Exp = integer
- }
- if base >= 0 || uint64(-base) <= e.Base {
- // The conversion from negative float64 to
- // uint64 is undefined in golang, and doesn't
- // work with ARMv8. More details at:
- // https://github.com/golang/go/issues/43047
- if base >= 0 {
- e.Base += uint64(base)
- } else {
- e.Base -= uint64(-base)
- }
- return amount
- }
- net := int64(-float64(e.Base) / factor)
- e.Base = 0
- return net
- }
- // addExp adds another ExpiredValue
- func (e *ExpiredValue) AddExp(a ExpiredValue) {
- if e.Exp > a.Exp {
- a.Base >>= (e.Exp - a.Exp)
- }
- if e.Exp < a.Exp {
- e.Base >>= (a.Exp - e.Exp)
- e.Exp = a.Exp
- }
- e.Base += a.Base
- }
- // subExp subtracts another ExpiredValue
- func (e *ExpiredValue) SubExp(a ExpiredValue) {
- if e.Exp > a.Exp {
- a.Base >>= (e.Exp - a.Exp)
- }
- if e.Exp < a.Exp {
- e.Base >>= (a.Exp - e.Exp)
- e.Exp = a.Exp
- }
- if e.Base > a.Base {
- e.Base -= a.Base
- } else {
- e.Base = 0
- }
- }
- // IsZero returns true if the value is zero
- func (e *ExpiredValue) IsZero() bool {
- return e.Base == 0
- }
- // LinearExpiredValue is very similar with the expiredValue which the value
- // will continuously expired. But the different part is it's expired linearly.
- type LinearExpiredValue struct {
- Offset uint64 // The latest time offset
- Val uint64 // The remaining value, can never be negative
- Rate mclock.AbsTime `rlp:"-"` // Expiration rate(by nanosecond), will ignored by RLP
- }
- // value calculates the value at the given moment. This function always has the
- // assumption that the given timestamp shouldn't less than the recorded one.
- func (e LinearExpiredValue) Value(now mclock.AbsTime) uint64 {
- offset := uint64(now / e.Rate)
- if e.Offset < offset {
- diff := offset - e.Offset
- if e.Val >= diff {
- e.Val -= diff
- } else {
- e.Val = 0
- }
- }
- return e.Val
- }
- // add adds a signed value at the given moment. This function always has the
- // assumption that the given timestamp shouldn't less than the recorded one.
- func (e *LinearExpiredValue) Add(amount int64, now mclock.AbsTime) uint64 {
- offset := uint64(now / e.Rate)
- if e.Offset < offset {
- diff := offset - e.Offset
- if e.Val >= diff {
- e.Val -= diff
- } else {
- e.Val = 0
- }
- e.Offset = offset
- }
- if amount < 0 && uint64(-amount) > e.Val {
- e.Val = 0
- } else {
- e.Val = uint64(int64(e.Val) + amount)
- }
- return e.Val
- }
- // ValueExpirer controls value expiration rate
- type ValueExpirer interface {
- SetRate(now mclock.AbsTime, rate float64)
- SetLogOffset(now mclock.AbsTime, logOffset Fixed64)
- LogOffset(now mclock.AbsTime) Fixed64
- }
- // Expirer changes logOffset with a linear rate which can be changed during operation.
- // It is not thread safe, if access by multiple goroutines is needed then it should be
- // encapsulated into a locked structure.
- // Note that if neither SetRate nor SetLogOffset are used during operation then LogOffset
- // is thread safe.
- type Expirer struct {
- lock sync.RWMutex
- logOffset Fixed64
- rate float64
- lastUpdate mclock.AbsTime
- }
- // SetRate changes the expiration rate which is the inverse of the time constant in
- // nanoseconds.
- func (e *Expirer) SetRate(now mclock.AbsTime, rate float64) {
- e.lock.Lock()
- defer e.lock.Unlock()
- dt := now - e.lastUpdate
- if dt > 0 {
- e.logOffset += Fixed64(logToFixedFactor * float64(dt) * e.rate)
- }
- e.lastUpdate = now
- e.rate = rate
- }
- // SetLogOffset sets logOffset instantly.
- func (e *Expirer) SetLogOffset(now mclock.AbsTime, logOffset Fixed64) {
- e.lock.Lock()
- defer e.lock.Unlock()
- e.lastUpdate = now
- e.logOffset = logOffset
- }
- // LogOffset returns the current logarithmic offset.
- func (e *Expirer) LogOffset(now mclock.AbsTime) Fixed64 {
- e.lock.RLock()
- defer e.lock.RUnlock()
- dt := now - e.lastUpdate
- if dt <= 0 {
- return e.logOffset
- }
- return e.logOffset + Fixed64(logToFixedFactor*float64(dt)*e.rate)
- }
- // fixedFactor is the fixed point multiplier factor used by Fixed64.
- const fixedFactor = 0x1000000
- // Fixed64 implements 64-bit fixed point arithmetic functions.
- type Fixed64 int64
- // Uint64ToFixed64 converts uint64 integer to Fixed64 format.
- func Uint64ToFixed64(f uint64) Fixed64 {
- return Fixed64(f * fixedFactor)
- }
- // float64ToFixed64 converts float64 to Fixed64 format.
- func Float64ToFixed64(f float64) Fixed64 {
- return Fixed64(f * fixedFactor)
- }
- // toUint64 converts Fixed64 format to uint64.
- func (f64 Fixed64) ToUint64() uint64 {
- return uint64(f64) / fixedFactor
- }
- // fraction returns the fractional part of a Fixed64 value.
- func (f64 Fixed64) Fraction() Fixed64 {
- return f64 % fixedFactor
- }
- var (
- logToFixedFactor = float64(fixedFactor) / math.Log(2)
- fixedToLogFactor = math.Log(2) / float64(fixedFactor)
- )
- // pow2Fixed returns the base 2 power of the fixed point value.
- func (f64 Fixed64) Pow2() float64 {
- return math.Exp(float64(f64) * fixedToLogFactor)
- }
|