Fix SntpClient 2036 issue (1/2) am: f663ab4276 am: 87fe4ba614 am: 741fb2db90

Original change: https://android-review.googlesource.com/c/platform/frameworks/base/+/1863054

Change-Id: I667ecea0563b5d9a26b2845bd448d4b3ce327c1e

3 files changed, 399 insertions, 27 deletions

diff --git a/core/java/android/net/SntpClient.java b/core/java/android/net/SntpClient.java
index f6852e681439..aea11fad7832 100644
--- a/core/java/android/net/SntpClient.java
+++ b/core/java/android/net/SntpClient.java
@@ -20,13 +20,18 @@ import android.compat.annotation.UnsupportedAppUsage;
 import android.os.SystemClock;
 import android.util.Log;
 
+import com.android.internal.annotations.VisibleForTesting;
 import com.android.internal.util.TrafficStatsConstants;
 
 import java.net.DatagramPacket;
 import java.net.DatagramSocket;
 import java.net.InetAddress;
 import java.net.UnknownHostException;
+import java.time.Duration;
+import java.time.Instant;
 import java.util.Arrays;
+import java.util.Objects;
+import java.util.function.Supplier;
 
 /**
  * {@hide}
@@ -64,13 +69,19 @@ public class SntpClient {
     // 70 years plus 17 leap days
     private static final long OFFSET_1900_TO_1970 = ((365L * 70L) + 17L) * 24L * 60L * 60L;
 
-    // system time computed from NTP server response
+    // The source of the current system clock time, replaceable for testing.
+    private final Supplier<Instant> mSystemTimeSupplier;
+
+    // The last offset calculated from an NTP server response
+    private long mClockOffset;
+
+    // The last system time computed from an NTP server response
     private long mNtpTime;
 
-    // value of SystemClock.elapsedRealtime() corresponding to mNtpTime
+    // The value of SystemClock.elapsedRealtime() corresponding to mNtpTime / mClockOffset
     private long mNtpTimeReference;
 
-    // round trip time in milliseconds
+    // The round trip (network) time in milliseconds
     private long mRoundTripTime;
 
     private static class InvalidServerReplyException extends Exception {
@@ -81,6 +92,12 @@ public class SntpClient {
 
     @UnsupportedAppUsage
     public SntpClient() {
+        this(Instant::now);
+    }
+
+    @VisibleForTesting
+    public SntpClient(Supplier<Instant> systemTimeSupplier) {
+        mSystemTimeSupplier = Objects.requireNonNull(systemTimeSupplier);
     }
 
     /**
@@ -126,9 +143,11 @@ public class SntpClient {
             buffer[0] = NTP_MODE_CLIENT | (NTP_VERSION << 3);
 
             // get current time and write it to the request packet
-            final long requestTime = System.currentTimeMillis();
+            final Instant requestTime = mSystemTimeSupplier.get();
+            final long requestTimestamp = requestTime.toEpochMilli();
+
             final long requestTicks = SystemClock.elapsedRealtime();
-            writeTimeStamp(buffer, TRANSMIT_TIME_OFFSET, requestTime);
+            writeTimeStamp(buffer, TRANSMIT_TIME_OFFSET, requestTimestamp);
 
             socket.send(request);
 
@@ -136,42 +155,42 @@ public class SntpClient {
             DatagramPacket response = new DatagramPacket(buffer, buffer.length);
             socket.receive(response);
             final long responseTicks = SystemClock.elapsedRealtime();
-            final long responseTime = requestTime + (responseTicks - requestTicks);
+            final Instant responseTime = requestTime.plusMillis(responseTicks - requestTicks);
+            final long responseTimestamp = responseTime.toEpochMilli();
 
             // extract the results
             final byte leap = (byte) ((buffer[0] >> 6) & 0x3);
             final byte mode = (byte) (buffer[0] & 0x7);
             final int stratum = (int) (buffer[1] & 0xff);
-            final long originateTime = readTimeStamp(buffer, ORIGINATE_TIME_OFFSET);
-            final long receiveTime = readTimeStamp(buffer, RECEIVE_TIME_OFFSET);
-            final long transmitTime = readTimeStamp(buffer, TRANSMIT_TIME_OFFSET);
-            final long referenceTime = readTimeStamp(buffer, REFERENCE_TIME_OFFSET);
+            final long originateTimestamp = readTimeStamp(buffer, ORIGINATE_TIME_OFFSET);
+            final long receiveTimestamp = readTimeStamp(buffer, RECEIVE_TIME_OFFSET);
+            final long transmitTimestamp = readTimeStamp(buffer, TRANSMIT_TIME_OFFSET);
+            final long referenceTimestamp = readTimeStamp(buffer, REFERENCE_TIME_OFFSET);
 
             /* Do validation according to RFC */
             // TODO: validate originateTime == requestTime.
-            checkValidServerReply(leap, mode, stratum, transmitTime, referenceTime);
-
-            long roundTripTime = responseTicks - requestTicks - (transmitTime - receiveTime);
-            // receiveTime = originateTime + transit + skew
-            // responseTime = transmitTime + transit - skew
-            // clockOffset = ((receiveTime - originateTime) + (transmitTime - responseTime))/2
-            //             = ((originateTime + transit + skew - originateTime) +
-            //                (transmitTime - (transmitTime + transit - skew)))/2
-            //             = ((transit + skew) + (transmitTime - transmitTime - transit + skew))/2
-            //             = (transit + skew - transit + skew)/2
-            //             = (2 * skew)/2 = skew
-            long clockOffset = ((receiveTime - originateTime) + (transmitTime - responseTime))/2;
-            EventLogTags.writeNtpSuccess(address.toString(), roundTripTime, clockOffset);
+            checkValidServerReply(leap, mode, stratum, transmitTimestamp, referenceTimestamp);
+
+            long roundTripTimeMillis = responseTicks - requestTicks
+                    - (transmitTimestamp - receiveTimestamp);
+
+            Duration clockOffsetDuration = calculateClockOffset(requestTimestamp,
+                    receiveTimestamp, transmitTimestamp, responseTimestamp);
+            long clockOffsetMillis = clockOffsetDuration.toMillis();
+
+            EventLogTags.writeNtpSuccess(
+                    address.toString(), roundTripTimeMillis, clockOffsetMillis);
             if (DBG) {
-                Log.d(TAG, "round trip: " + roundTripTime + "ms, " +
-                        "clock offset: " + clockOffset + "ms");
+                Log.d(TAG, "round trip: " + roundTripTimeMillis + "ms, "
+                        + "clock offset: " + clockOffsetMillis + "ms");
             }
 
             // save our results - use the times on this side of the network latency
             // (response rather than request time)
-            mNtpTime = responseTime + clockOffset;
+            mClockOffset = clockOffsetMillis;
+            mNtpTime = responseTime.plus(clockOffsetDuration).toEpochMilli();
             mNtpTimeReference = responseTicks;
-            mRoundTripTime = roundTripTime;
+            mRoundTripTime = roundTripTimeMillis;
         } catch (Exception e) {
             EventLogTags.writeNtpFailure(address.toString(), e.toString());
             if (DBG) Log.d(TAG, "request time failed: " + e);
@@ -186,6 +205,24 @@ public class SntpClient {
         return true;
     }
 
+    /** Performs the NTP clock offset calculation. */
+    @VisibleForTesting
+    public static Duration calculateClockOffset(long clientRequestTimestamp,
+            long serverReceiveTimestamp, long serverTransmitTimestamp,
+            long clientResponseTimestamp) {
+        // receiveTime = originateTime + transit + skew
+        // responseTime = transmitTime + transit - skew
+        // clockOffset = ((receiveTime - originateTime) + (transmitTime - responseTime))/2
+        //             = ((originateTime + transit + skew - originateTime) +
+        //                (transmitTime - (transmitTime + transit - skew)))/2
+        //             = ((transit + skew) + (transmitTime - transmitTime - transit + skew))/2
+        //             = (transit + skew - transit + skew)/2
+        //             = (2 * skew)/2 = skew
+        long clockOffsetMillis = ((serverReceiveTimestamp - clientRequestTimestamp)
+                + (serverTransmitTimestamp - clientResponseTimestamp)) / 2;
+        return Duration.ofMillis(clockOffsetMillis);
+    }
+
     @Deprecated
     @UnsupportedAppUsage
     public boolean requestTime(String host, int timeout) {
@@ -194,6 +231,14 @@ public class SntpClient {
     }
 
     /**
+     * Returns the offset calculated to apply to the client clock to arrive at {@link #getNtpTime()}
+     */
+    @VisibleForTesting
+    public long getClockOffset() {
+        return mClockOffset;
+    }
+
+    /**
      * Returns the time computed from the NTP transaction.
      *
      * @return time value computed from NTP server response.
diff --git a/core/java/android/net/sntp/Duration64.java b/core/java/android/net/sntp/Duration64.java
new file mode 100644
index 000000000000..939b2892a18f
--- /dev/null
+++ b/core/java/android/net/sntp/Duration64.java
@@ -0,0 +1,141 @@
+/*
+ * Copyright (C) 2021 The Android Open Source Project
+ *
+ * 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 android.net.sntp;
+
+import java.time.Duration;
+
+/**
+ * A type similar to {@link Timestamp64} but used when calculating the difference between two
+ * timestamps. As such, it is a signed type, but still uses 64-bits in total and so can only
+ * represent half the magnitude of {@link Timestamp64}.
+ *
+ * <p>See <a href="https://www.eecis.udel.edu/~mills/time.html">4. Time Difference Calculations</a>.
+ *
+ * @hide
+ */
+public class Duration64 {
+
+    public static final Duration64 ZERO = new Duration64(0);
+    private final long mBits;
+
+    private Duration64(long bits) {
+        this.mBits = bits;
+    }
+
+    /**
+     * Returns the difference between two 64-bit NTP timestamps as a {@link Duration64}, as
+     * described in the NTP spec. The times represented by the timestamps have to be within {@link
+     * Timestamp64#MAX_SECONDS_IN_ERA} (~68 years) of each other for the calculation to produce a
+     * correct answer.
+     */
+    public static Duration64 between(Timestamp64 startInclusive, Timestamp64 endExclusive) {
+        long oneBits = (startInclusive.getEraSeconds() << 32)
+                | (startInclusive.getFractionBits() & 0xFFFF_FFFFL);
+        long twoBits = (endExclusive.getEraSeconds() << 32)
+                | (endExclusive.getFractionBits() & 0xFFFF_FFFFL);
+        long resultBits = twoBits - oneBits;
+        return new Duration64(resultBits);
+    }
+
+    /**
+     * Add two {@link Duration64} instances together. This performs the calculation in {@link
+     * Duration} and returns a {@link Duration} to increase the magnitude of accepted arguments,
+     * since {@link Duration64} only supports signed 32-bit seconds. The use of {@link Duration}
+     * limits precision to nanoseconds.
+     */
+    public Duration plus(Duration64 other) {
+        // From https://www.eecis.udel.edu/~mills/time.html:
+        // "The offset and delay calculations require sums and differences of these raw timestamp
+        // differences that can span no more than from 34 years in the future to 34 years in the
+        // past without overflow. This is a fundamental limitation in 64-bit integer calculations.
+        //
+        // In the NTPv4 reference implementation, all calculations involving offset and delay values
+        // use 64-bit floating double arithmetic, with the exception of raw timestamp subtraction,
+        // as mentioned above. The raw timestamp differences are then converted to 64-bit floating
+        // double format without loss of precision or chance of overflow in subsequent
+        // calculations."
+        //
+        // Here, we use Duration instead, which provides sufficient range, but loses precision below
+        // nanos.
+        return this.toDuration().plus(other.toDuration());
+    }
+
+    /**
+     * Returns a {@link Duration64} equivalent of the supplied duration, if the magnitude can be
+     * represented. Because {@link Duration64} uses a fixed point type for sub-second values it
+     * cannot represent all nanosecond values precisely and so the conversion can be lossy.
+     *
+     * @throws IllegalArgumentException if the supplied duration is too big to be represented
+     */
+    public static Duration64 fromDuration(Duration duration) {
+        long seconds = duration.getSeconds();
+        if (seconds < Integer.MIN_VALUE || seconds > Integer.MAX_VALUE) {
+            throw new IllegalArgumentException();
+        }
+        long bits = (seconds << 32)
+                | (Timestamp64.nanosToFractionBits(duration.getNano()) & 0xFFFF_FFFFL);
+        return new Duration64(bits);
+    }
+
+    /**
+     * Returns a {@link Duration} equivalent of this duration. Because {@link Duration64} uses a
+     * fixed point type for sub-second values it can values smaller than nanosecond precision and so
+     * the conversion can be lossy.
+     */
+    public Duration toDuration() {
+        int seconds = getSeconds();
+        int nanos = getNanos();
+        return Duration.ofSeconds(seconds, nanos);
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) {
+            return true;
+        }
+        if (o == null || getClass() != o.getClass()) {
+            return false;
+        }
+        Duration64 that = (Duration64) o;
+        return mBits == that.mBits;
+    }
+
+    @Override
+    public int hashCode() {
+        return java.util.Objects.hash(mBits);
+    }
+
+    @Override
+    public String toString() {
+        Duration duration = toDuration();
+        return Long.toHexString(mBits)
+                + "(" + duration.getSeconds() + "s " + duration.getNano() + "ns)";
+    }
+
+    /**
+     * Returns the <em>signed</em> seconds in this duration.
+     */
+    public int getSeconds() {
+        return (int) (mBits >> 32);
+    }
+
+    /**
+     * Returns the <em>unsigned</em> nanoseconds in this duration (truncated).
+     */
+    public int getNanos() {
+        return Timestamp64.fractionBitsToNanos((int) (mBits & 0xFFFF_FFFFL));
+    }
+}
diff --git a/core/java/android/net/sntp/Timestamp64.java b/core/java/android/net/sntp/Timestamp64.java
new file mode 100644
index 000000000000..81a33108ed85
--- /dev/null
+++ b/core/java/android/net/sntp/Timestamp64.java
@@ -0,0 +1,186 @@
+/*
+ * Copyright (C) 2021 The Android Open Source Project
+ *
+ * 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 android.net.sntp;
+
+import com.android.internal.annotations.VisibleForTesting;
+
+import java.time.Instant;
+import java.util.Objects;
+import java.util.Random;
+
+/**
+ * The 64-bit type ("timestamp") that NTP uses to represent a point in time. It only holds the
+ * lowest 32-bits of the number of seconds since 1900-01-01 00:00:00. Consequently, to turn an
+ * instance into an unambiguous point in time the era number must be known. Era zero runs from
+ * 1900-01-01 00:00:00 to a date in 2036.
+ *
+ * It stores sub-second values using a 32-bit fixed point type, so it can resolve values smaller
+ * than a nanosecond, but is imprecise (i.e. it truncates).
+ *
+ * See also <a href=https://www.eecis.udel.edu/~mills/y2k.html>NTP docs</a>.
+ *
+ * @hide
+ */
+public final class Timestamp64 {
+
+    public static final Timestamp64 ZERO = fromComponents(0, 0);
+    static final int SUB_MILLIS_BITS_TO_RANDOMIZE = 32 - 10;
+
+    // Number of seconds between Jan 1, 1900 and Jan 1, 1970
+    // 70 years plus 17 leap days
+    static final long OFFSET_1900_TO_1970 = ((365L * 70L) + 17L) * 24L * 60L * 60L;
+    static final long MAX_SECONDS_IN_ERA = 0xFFFF_FFFFL;
+    static final long SECONDS_IN_ERA = MAX_SECONDS_IN_ERA + 1;
+
+    static final int NANOS_PER_SECOND = 1_000_000_000;
+
+    /** Creates a {@link Timestamp64} from the seconds and fraction components. */
+    public static Timestamp64 fromComponents(long eraSeconds, int fractionBits) {
+        return new Timestamp64(eraSeconds, fractionBits);
+    }
+
+    /** Creates a {@link Timestamp64} by decoding a string in the form "e4dc720c.4d4fc9eb". */
+    public static Timestamp64 fromString(String string) {
+        final int requiredLength = 17;
+        if (string.length() != requiredLength || string.charAt(8) != '.') {
+            throw new IllegalArgumentException(string);
+        }
+        String eraSecondsString = string.substring(0, 8);
+        String fractionString = string.substring(9);
+        long eraSeconds = Long.parseLong(eraSecondsString, 16);
+
+        // Use parseLong() because the type is unsigned. Integer.parseInt() will reject 0x70000000
+        // or above as being out of range.
+        long fractionBitsAsLong = Long.parseLong(fractionString, 16);
+        if (fractionBitsAsLong < 0 || fractionBitsAsLong > 0xFFFFFFFFL) {
+            throw new IllegalArgumentException("Invalid fractionBits:" + fractionString);
+        }
+        return new Timestamp64(eraSeconds, (int) fractionBitsAsLong);
+    }
+
+    /**
+     * Converts an {@link Instant} into a {@link Timestamp64}. This is lossy: Timestamp64 only
+     * contains the number of seconds in a given era, but the era is not stored. Also, sub-second
+     * values are not stored precisely.
+     */
+    public static Timestamp64 fromInstant(Instant instant) {
+        long ntpEraSeconds = instant.getEpochSecond() + OFFSET_1900_TO_1970;
+        if (ntpEraSeconds < 0) {
+            ntpEraSeconds = SECONDS_IN_ERA - (-ntpEraSeconds % SECONDS_IN_ERA);
+        }
+        ntpEraSeconds %= SECONDS_IN_ERA;
+
+        long nanos = instant.getNano();
+        int fractionBits = nanosToFractionBits(nanos);
+
+        return new Timestamp64(ntpEraSeconds, fractionBits);
+    }
+
+    private final long mEraSeconds;
+    private final int mFractionBits;
+
+    private Timestamp64(long eraSeconds, int fractionBits) {
+        if (eraSeconds < 0 || eraSeconds > MAX_SECONDS_IN_ERA) {
+            throw new IllegalArgumentException(
+                    "Invalid parameters. seconds=" + eraSeconds + ", fraction=" + fractionBits);
+        }
+        this.mEraSeconds = eraSeconds;
+        this.mFractionBits = fractionBits;
+    }
+
+    /** Returns the number of seconds in the NTP era. */
+    public long getEraSeconds() {
+        return mEraSeconds;
+    }
+
+    /** Returns the fraction of a second as 32-bit, unsigned fixed-point bits. */
+    public int getFractionBits() {
+        return mFractionBits;
+    }
+
+    @Override
+    public String toString() {
+        return String.format("%08x.%08x", mEraSeconds, mFractionBits);
+    }
+
+    /** Returns the instant represented by this value in the specified NTP era. */
+    public Instant toInstant(int ntpEra) {
+        long secondsSinceEpoch = mEraSeconds - OFFSET_1900_TO_1970;
+        secondsSinceEpoch += ntpEra * SECONDS_IN_ERA;
+
+        int nanos = fractionBitsToNanos(mFractionBits);
+        return Instant.ofEpochSecond(secondsSinceEpoch, nanos);
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) {
+            return true;
+        }
+        if (o == null || getClass() != o.getClass()) {
+            return false;
+        }
+        Timestamp64 that = (Timestamp64) o;
+        return mEraSeconds == that.mEraSeconds && mFractionBits == that.mFractionBits;
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(mEraSeconds, mFractionBits);
+    }
+
+    static int fractionBitsToNanos(int fractionBits) {
+        long fractionBitsLong = fractionBits & 0xFFFF_FFFFL;
+        return (int) ((fractionBitsLong * NANOS_PER_SECOND) >>> 32);
+    }
+
+    static int nanosToFractionBits(long nanos) {
+        if (nanos > NANOS_PER_SECOND) {
+            throw new IllegalArgumentException();
+        }
+        return (int) ((nanos << 32) / NANOS_PER_SECOND);
+    }
+
+    /**
+     * Randomizes the fraction bits that represent sub-millisecond values. i.e. the randomization
+     * won't change the number of milliseconds represented after truncation. This is used to
+     * implement the part of the NTP spec that calls for clients with millisecond accuracy clocks
+     * to send randomized LSB values rather than zeros.
+     */
+    public Timestamp64 randomizeSubMillis(Random random) {
+        int randomizedFractionBits =
+                randomizeLowestBits(random, this.mFractionBits, SUB_MILLIS_BITS_TO_RANDOMIZE);
+        return new Timestamp64(mEraSeconds, randomizedFractionBits);
+    }
+
+    /**
+     * Randomizes the specified number of LSBs in {@code value} by using replacement bits from
+     * {@code Random.getNextInt()}.
+     */
+    @VisibleForTesting
+    public static int randomizeLowestBits(Random random, int value, int bitsToRandomize) {
+        if (bitsToRandomize < 1 || bitsToRandomize >= Integer.SIZE) {
+            // There's no point in randomizing all bits or none of the bits.
+            throw new IllegalArgumentException(Integer.toString(bitsToRandomize));
+        }
+
+        int upperBitMask = 0xFFFF_FFFF << bitsToRandomize;
+        int lowerBitMask = ~upperBitMask;
+
+        int randomValue = random.nextInt();
+        return (value & upperBitMask) | (randomValue & lowerBitMask);
+    }
+}