summaryrefslogtreecommitdiffhomepage
path: root/pkg/sentry/time/parameters.go
diff options
context:
space:
mode:
Diffstat (limited to 'pkg/sentry/time/parameters.go')
-rw-r--r--pkg/sentry/time/parameters.go239
1 files changed, 239 insertions, 0 deletions
diff --git a/pkg/sentry/time/parameters.go b/pkg/sentry/time/parameters.go
new file mode 100644
index 000000000..594b4874b
--- /dev/null
+++ b/pkg/sentry/time/parameters.go
@@ -0,0 +1,239 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package time
+
+import (
+ "fmt"
+ "time"
+
+ "gvisor.googlesource.com/gvisor/pkg/log"
+)
+
+const (
+ // ApproxUpdateInterval is the approximate interval that parameters
+ // should be updated at.
+ //
+ // Error correction assumes that the next update will occur after this
+ // much time.
+ //
+ // If an update occurs before ApproxUpdateInterval passes, it has no
+ // adverse effect on error correction behavior.
+ //
+ // If an update occurs after ApproxUpdateInterval passes, the clock
+ // will overshoot its error correction target and begin accumulating
+ // error in the other direction.
+ //
+ // If updates occur after more than 2*ApproxUpdateInterval passes, the
+ // clock becomes unstable, accumulating more error than it had
+ // originally. Repeated updates after more than 2*ApproxUpdateInterval
+ // will cause unbounded increases in error.
+ //
+ // These statements assume that the host clock does not change. Actual
+ // error will depend upon host clock changes.
+ //
+ // TODO: make error correction more robust to delayed
+ // updates.
+ ApproxUpdateInterval = 1 * time.Second
+
+ // MaxClockError is the maximum amount of error that the clocks will
+ // try to correct.
+ //
+ // This limit:
+ //
+ // * Puts a limit on cases of otherwise unbounded increases in error.
+ //
+ // * Avoids unreasonably large frequency adjustments required to
+ // correct large errors over a single update interval.
+ MaxClockError = ReferenceNS(ApproxUpdateInterval) / 4
+)
+
+// Parameters are the timekeeping parameters needed to compute the current
+// time.
+type Parameters struct {
+ // BaseCycles was the TSC counter value when the time was BaseRef.
+ BaseCycles TSCValue
+
+ // BaseRef is the reference clock time in nanoseconds corresponding to
+ // BaseCycles.
+ BaseRef ReferenceNS
+
+ // Frequency is the frequency of the cycle clock in Hertz.
+ Frequency uint64
+}
+
+// muldiv64 multiplies two 64-bit numbers, then divides the result by another
+// 64-bit number.
+//
+// It requires that the result fit in 64 bits, but doesn't require that
+// intermediate values do; in particular, the result of the multiplication may
+// require 128 bits.
+//
+// It returns !ok if divisor is zero or the result does not fit in 64 bits.
+func muldiv64(value, multiplier, divisor uint64) (uint64, bool)
+
+// ComputeTime calculates the current time from a "now" TSC value.
+//
+// time = ref + (now - base) / f
+func (p Parameters) ComputeTime(nowCycles TSCValue) (int64, bool) {
+ diffCycles := nowCycles - p.BaseCycles
+ if diffCycles < 0 {
+ log.Warningf("now cycles %v < base cycles %v", nowCycles, p.BaseCycles)
+ diffCycles = 0
+ }
+
+ // Overflow "won't ever happen". If diffCycles is the max value
+ // (2^63 - 1), then to overflow,
+ //
+ // frequency <= ((2^63 - 1) * 10^9) / 2^64 = 500Mhz
+ //
+ // A TSC running at 2GHz takes 201 years to reach 2^63-1. 805 years at
+ // 500MHz.
+ diffNS, ok := muldiv64(uint64(diffCycles), uint64(time.Second.Nanoseconds()), p.Frequency)
+ return int64(uint64(p.BaseRef) + diffNS), ok
+}
+
+// errorAdjust returns a new Parameters struct "adjusted" that satisfies:
+//
+// 1. adjusted.ComputeTime(now) = prevParams.ComputeTime(now)
+// * i.e., the current time does not jump.
+//
+// 2. adjusted.ComputeTime(TSC at next update) = newParams.ComputeTime(TSC at next update)
+// * i.e., Any error between prevParams and newParams will be corrected over
+// the course of the next update period.
+//
+// errorAdjust also returns the current clock error.
+//
+// Preconditions:
+// * newParams.BaseCycles >= prevParams.BaseCycles; i.e., TSC must not go
+// backwards.
+// * newParams.BaseCycles <= now; i.e., the new parameters be computed at or
+// before now.
+func errorAdjust(prevParams Parameters, newParams Parameters, now TSCValue) (Parameters, ReferenceNS, error) {
+ if newParams.BaseCycles < prevParams.BaseCycles {
+ // Oh dear! Something is very wrong.
+ return Parameters{}, 0, fmt.Errorf("TSC went backwards in updated clock params: %v < %v", newParams.BaseCycles, prevParams.BaseCycles)
+ }
+ if newParams.BaseCycles > now {
+ return Parameters{}, 0, fmt.Errorf("parameters contain base cycles later than now: %v > %v", newParams.BaseCycles, now)
+ }
+
+ intervalNS := int64(ApproxUpdateInterval.Nanoseconds())
+ nsPerSec := uint64(time.Second.Nanoseconds())
+
+ // Current time as computed by prevParams.
+ oldNowNS, ok := prevParams.ComputeTime(now)
+ if !ok {
+ return Parameters{}, 0, fmt.Errorf("old now time computation overflowed. params = %+v, now = %v", prevParams, now)
+ }
+
+ // We expect the update ticker to run based on this clock (i.e., it has
+ // been using prevParams and will use the returned adjusted
+ // parameters). Hence it will decide to fire intervalNS from the
+ // current (oldNowNS) "now".
+ nextNS := oldNowNS + intervalNS
+
+ if nextNS <= int64(newParams.BaseRef) {
+ // The next update time already passed before the new
+ // parameters were created! We definitely can't correct the
+ // error by then.
+ return Parameters{}, 0, fmt.Errorf("unable to correct error in single period. oldNowNS = %v, nextNS = %v, p = %v", oldNowNS, nextNS, newParams)
+ }
+
+ // For what TSC value next will newParams.ComputeTime(next) = nextNS?
+ //
+ // Solve ComputeTime for next:
+ //
+ // next = newParams.Frequency * (nextNS - newParams.BaseRef) + newParams.BaseCycles
+ c, ok := muldiv64(newParams.Frequency, uint64(nextNS-int64(newParams.BaseRef)), nsPerSec)
+ if !ok {
+ return Parameters{}, 0, fmt.Errorf("%v * (%v - %v) / %v overflows", newParams.Frequency, nextNS, newParams.BaseRef, nsPerSec)
+ }
+
+ cycles := TSCValue(c)
+ next := cycles + newParams.BaseCycles
+
+ if next <= now {
+ // The next update time already passed now with the new
+ // parameters! We can't correct the error in a single period.
+ return Parameters{}, 0, fmt.Errorf("unable to correct error in single period. oldNowNS = %v, nextNS = %v, now = %v, next = %v", oldNowNS, nextNS, now, next)
+ }
+
+ // We want to solve for parameters that satisfy:
+ //
+ // adjusted.ComputeTime(now) = oldNowNS
+ //
+ // adjusted.ComputeTime(next) = nextNS
+ //
+ // i.e., the current time does not change, but by the time we reach
+ // next we reach the same time as newParams.
+
+ // We choose to keep BaseCycles fixed.
+ adjusted := Parameters{
+ BaseCycles: newParams.BaseCycles,
+ }
+
+ // We want a slope such that time goes from oldNowNS to nextNS when
+ // we reach next.
+ //
+ // In other words, cycles should increase by next - now in the next
+ // interval.
+
+ cycles = next - now
+ ns := intervalNS
+
+ // adjusted.Frequency = cycles / ns
+ adjusted.Frequency, ok = muldiv64(uint64(cycles), nsPerSec, uint64(ns))
+ if !ok {
+ return Parameters{}, 0, fmt.Errorf("(%v - %v) * %v / %v overflows", next, now, nsPerSec, ns)
+ }
+
+ // Now choose a base reference such that the current time remains the
+ // same. Note that this is just ComputeTime, solving for BaseRef:
+ //
+ // oldNowNS = BaseRef + (now - BaseCycles) / Frequency
+ // BaseRef = oldNowNS - (now - BaseCycles) / Frequency
+ diffNS, ok := muldiv64(uint64(now-adjusted.BaseCycles), nsPerSec, adjusted.Frequency)
+ if !ok {
+ return Parameters{}, 0, fmt.Errorf("(%v - %v) * %v / %v overflows", now, adjusted.BaseCycles, nsPerSec, adjusted.Frequency)
+ }
+
+ adjusted.BaseRef = ReferenceNS(oldNowNS - int64(diffNS))
+
+ // The error is the difference between the current time and what the
+ // new parameters say the current time should be.
+ newNowNS, ok := newParams.ComputeTime(now)
+ if !ok {
+ return Parameters{}, 0, fmt.Errorf("new now time computation overflowed. params = %+v, now = %v", newParams, now)
+ }
+
+ errorNS := ReferenceNS(oldNowNS - newNowNS)
+
+ return adjusted, errorNS, nil
+}
+
+// logErrorAdjustment logs the clock error and associated error correction
+// frequency adjustment.
+//
+// The log level is determined by the error severity.
+func logErrorAdjustment(clock ClockID, errorNS ReferenceNS, orig, adjusted Parameters) {
+ fn := log.Debugf
+ if int64(errorNS.Magnitude()) > time.Millisecond.Nanoseconds() {
+ fn = log.Warningf
+ } else if int64(errorNS.Magnitude()) > 10*time.Microsecond.Nanoseconds() {
+ fn = log.Infof
+ }
+
+ fn("Clock(%v): error: %v ns, adjusted frequency from %v Hz to %v Hz", clock, errorNS, orig.Frequency, adjusted.Frequency)
+}