Merge "Collect historical network stats."
diff --git a/Android.mk b/Android.mk
index 270ee2e..e987f91 100644
--- a/Android.mk
+++ b/Android.mk
@@ -112,6 +112,7 @@
 	core/java/android/net/IThrottleManager.aidl \
 	core/java/android/net/INetworkPolicyListener.aidl \
 	core/java/android/net/INetworkPolicyManager.aidl \
+	core/java/android/net/INetworkStatsService.aidl \
 	core/java/android/nfc/ILlcpConnectionlessSocket.aidl \
 	core/java/android/nfc/ILlcpServiceSocket.aidl \
 	core/java/android/nfc/ILlcpSocket.aidl \
@@ -124,7 +125,6 @@
 	core/java/android/os/IHardwareService.aidl \
 	core/java/android/os/IMessenger.aidl \
 	core/java/android/os/INetworkManagementService.aidl \
-	core/java/android/os/INetStatService.aidl \
 	core/java/android/os/IPermissionController.aidl \
 	core/java/android/os/IPowerManager.aidl \
     core/java/android/os/IRemoteCallback.aidl \
diff --git a/CleanSpec.mk b/CleanSpec.mk
index b19bed0..1e59ff6 100644
--- a/CleanSpec.mk
+++ b/CleanSpec.mk
@@ -98,6 +98,7 @@
 $(call add-clean-step, rm -rf $(OUT_DIR)/target/common/obj/JAVA_LIBRARIES/framework_intermediates/src/core/java/android/nfc)
 $(call add-clean-step, rm -rf $(OUT_DIR)/target/common/obj/JAVA_LIBRARIES/framework_intermediates)
 $(call add-clean-step, rm -rf $(PRODUCT_OUT)/obj/SHARED_LIBRARIES/libstagefright_intermediates)
+$(call add-clean-step, rm -rf $(OUT_DIR)/target/common/obj/JAVA_LIBRARIES/framework_intermediates/src/core/java/android/os)
 # ************************************************
 # NEWER CLEAN STEPS MUST BE AT THE END OF THE LIST
 # ************************************************
diff --git a/core/java/android/content/Context.java b/core/java/android/content/Context.java
index a660bd7..aecec66 100644
--- a/core/java/android/content/Context.java
+++ b/core/java/android/content/Context.java
@@ -1545,6 +1545,8 @@
     public static final String NETWORKMANAGEMENT_SERVICE = "network_management";
 
     /** {@hide} */
+    public static final String NETWORK_STATS_SERVICE = "netstats";
+    /** {@hide} */
     public static final String NETWORK_POLICY_SERVICE = "netpolicy";
 
     /**
diff --git a/core/java/android/net/INetworkStatsService.aidl b/core/java/android/net/INetworkStatsService.aidl
new file mode 100644
index 0000000..6d57036
--- /dev/null
+++ b/core/java/android/net/INetworkStatsService.aidl
@@ -0,0 +1,27 @@
+/*
+ * Copyright (C) 2011 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;
+
+import android.net.NetworkStatsHistory;
+
+/** {@hide} */
+interface INetworkStatsService {
+
+    NetworkStatsHistory[] getNetworkStatsSummary(int networkType);
+    NetworkStatsHistory getNetworkStatsUid(int uid);
+
+}
diff --git a/core/java/android/net/NetworkStats.java b/core/java/android/net/NetworkStats.java
index 0f207bc..588bf64 100644
--- a/core/java/android/net/NetworkStats.java
+++ b/core/java/android/net/NetworkStats.java
@@ -22,19 +22,22 @@
 
 import java.io.CharArrayWriter;
 import java.io.PrintWriter;
+import java.util.HashSet;
 
 /**
- * Collection of network statistics. Can contain summary details across all
- * interfaces, or details with per-UID granularity. Designed to parcel quickly
- * across process boundaries.
+ * Collection of active network statistics. Can contain summary details across
+ * all interfaces, or details with per-UID granularity. Internally stores data
+ * as a large table, closely matching {@code /proc/} data format. This structure
+ * optimizes for rapid in-memory comparison, but consider using
+ * {@link NetworkStatsHistory} when persisting.
  *
  * @hide
  */
 public class NetworkStats implements Parcelable {
-    /** {@link #iface} value when entry is summarized over all interfaces. */
+    /** {@link #iface} value when interface details unavailable. */
     public static final String IFACE_ALL = null;
-    /** {@link #uid} value when entry is summarized over all UIDs. */
-    public static final int UID_ALL = 0;
+    /** {@link #uid} value when UID details unavailable. */
+    public static final int UID_ALL = -1;
 
     // NOTE: data should only be accounted for once in this structure; if data
     // is broken out, the summarized version should not be included.
@@ -49,7 +52,7 @@
     public final long[] rx;
     public final long[] tx;
 
-    // TODO: add fg/bg stats and tag granularity
+    // TODO: add fg/bg stats once reported by kernel
 
     private NetworkStats(long elapsedRealtime, String[] iface, int[] uid, long[] rx, long[] tx) {
         this.elapsedRealtime = elapsedRealtime;
@@ -120,15 +123,35 @@
     }
 
     /**
+     * Return list of unique interfaces known by this data structure.
+     */
+    public String[] getKnownIfaces() {
+        final HashSet<String> ifaces = new HashSet<String>();
+        for (String iface : this.iface) {
+            if (iface != IFACE_ALL) {
+                ifaces.add(iface);
+            }
+        }
+        return ifaces.toArray(new String[ifaces.size()]);
+    }
+
+    /**
      * Subtract the given {@link NetworkStats}, effectively leaving the delta
      * between two snapshots in time. Assumes that statistics rows collect over
      * time, and that none of them have disappeared.
+     *
+     * @param enforceMonotonic Validate that incoming value is strictly
+     *            monotonic compared to this object.
      */
-    public NetworkStats subtract(NetworkStats value) {
-        // result will have our rows, but no meaningful timestamp
-        final int length = length();
-        final NetworkStats.Builder result = new NetworkStats.Builder(-1, length);
+    public NetworkStats subtract(NetworkStats value, boolean enforceMonotonic) {
+        final long deltaRealtime = this.elapsedRealtime - value.elapsedRealtime;
+        if (enforceMonotonic && deltaRealtime < 0) {
+            throw new IllegalArgumentException("found non-monotonic realtime");
+        }
 
+        // result will have our rows, and elapsed time between snapshots
+        final int length = length();
+        final NetworkStats.Builder result = new NetworkStats.Builder(deltaRealtime, length);
         for (int i = 0; i < length; i++) {
             final String iface = this.iface[i];
             final int uid = this.uid[i];
@@ -142,6 +165,9 @@
                 // existing row, subtract remote value
                 final long rx = this.rx[i] - value.rx[j];
                 final long tx = this.tx[i] - value.tx[j];
+                if (enforceMonotonic && (rx < 0 || tx < 0)) {
+                    throw new IllegalArgumentException("found non-monotonic values");
+                }
                 result.addEntry(iface, uid, rx, tx);
             }
         }
diff --git a/core/java/android/net/NetworkStatsHistory.aidl b/core/java/android/net/NetworkStatsHistory.aidl
new file mode 100644
index 0000000..8b9069f
--- /dev/null
+++ b/core/java/android/net/NetworkStatsHistory.aidl
@@ -0,0 +1,19 @@
+/**
+ * Copyright (c) 2011, 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;
+
+parcelable NetworkStatsHistory;
diff --git a/core/java/android/net/NetworkStatsHistory.java b/core/java/android/net/NetworkStatsHistory.java
new file mode 100644
index 0000000..b16101f
--- /dev/null
+++ b/core/java/android/net/NetworkStatsHistory.java
@@ -0,0 +1,285 @@
+/*
+ * Copyright (C) 2011 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;
+
+import android.os.Parcel;
+import android.os.Parcelable;
+
+import java.io.CharArrayWriter;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.io.PrintWriter;
+import java.util.Arrays;
+
+/**
+ * Collection of historical network statistics, recorded into equally-sized
+ * "buckets" in time. Internally it stores data in {@code long} series for more
+ * efficient persistence.
+ * <p>
+ * Each bucket is defined by a {@link #bucketStart} timestamp, and lasts for
+ * {@link #bucketDuration}. Internally assumes that {@link #bucketStart} is
+ * sorted at all times.
+ *
+ * @hide
+ */
+public class NetworkStatsHistory implements Parcelable {
+    private static final int VERSION = 1;
+
+    /** {@link #uid} value when UID details unavailable. */
+    public static final int UID_ALL = -1;
+
+    // TODO: teach about zigzag encoding to use less disk space
+    // TODO: teach how to convert between bucket sizes
+
+    public final int networkType;
+    public final String identity;
+    public final int uid;
+    public final long bucketDuration;
+
+    int bucketCount;
+    long[] bucketStart;
+    long[] rx;
+    long[] tx;
+
+    public NetworkStatsHistory(int networkType, String identity, int uid, long bucketDuration) {
+        this.networkType = networkType;
+        this.identity = identity;
+        this.uid = uid;
+        this.bucketDuration = bucketDuration;
+        bucketStart = new long[0];
+        rx = new long[0];
+        tx = new long[0];
+        bucketCount = bucketStart.length;
+    }
+
+    public NetworkStatsHistory(Parcel in) {
+        networkType = in.readInt();
+        identity = in.readString();
+        uid = in.readInt();
+        bucketDuration = in.readLong();
+        bucketStart = readLongArray(in);
+        rx = in.createLongArray();
+        tx = in.createLongArray();
+        bucketCount = bucketStart.length;
+    }
+
+    /** {@inheritDoc} */
+    public void writeToParcel(Parcel out, int flags) {
+        out.writeInt(networkType);
+        out.writeString(identity);
+        out.writeInt(uid);
+        out.writeLong(bucketDuration);
+        writeLongArray(out, bucketStart, bucketCount);
+        writeLongArray(out, rx, bucketCount);
+        writeLongArray(out, tx, bucketCount);
+    }
+
+    public NetworkStatsHistory(DataInputStream in) throws IOException {
+        final int version = in.readInt();
+        networkType = in.readInt();
+        identity = in.readUTF();
+        uid = in.readInt();
+        bucketDuration = in.readLong();
+        bucketStart = readLongArray(in);
+        rx = readLongArray(in);
+        tx = readLongArray(in);
+        bucketCount = bucketStart.length;
+    }
+
+    public void writeToStream(DataOutputStream out) throws IOException {
+        out.writeInt(VERSION);
+        out.writeInt(networkType);
+        out.writeUTF(identity);
+        out.writeInt(uid);
+        out.writeLong(bucketDuration);
+        writeLongArray(out, bucketStart, bucketCount);
+        writeLongArray(out, rx, bucketCount);
+        writeLongArray(out, tx, bucketCount);
+    }
+
+    /** {@inheritDoc} */
+    public int describeContents() {
+        return 0;
+    }
+
+    /**
+     * Record that data traffic occurred in the given time range. Will
+     * distribute across internal buckets, creating new buckets as needed.
+     */
+    public void recordData(long start, long end, long rx, long tx) {
+        // create any buckets needed by this range
+        ensureBuckets(start, end);
+
+        // distribute data usage into buckets
+        final long duration = end - start;
+        for (int i = bucketCount - 1; i >= 0; i--) {
+            final long curStart = bucketStart[i];
+            final long curEnd = curStart + bucketDuration;
+
+            // bucket is older than record; we're finished
+            if (curEnd < start) break;
+            // bucket is newer than record; keep looking
+            if (curStart > end) continue;
+
+            final long overlap = Math.min(curEnd, end) - Math.max(curStart, start);
+            if (overlap > 0) {
+                this.rx[i] += rx * overlap / duration;
+                this.tx[i] += tx * overlap / duration;
+            }
+        }
+    }
+
+    /**
+     * Ensure that buckets exist for given time range, creating as needed.
+     */
+    private void ensureBuckets(long start, long end) {
+        // normalize incoming range to bucket boundaries
+        start -= start % bucketDuration;
+        end += (bucketDuration - (end % bucketDuration)) % bucketDuration;
+
+        for (long now = start; now < end; now += bucketDuration) {
+            // try finding existing bucket
+            final int index = Arrays.binarySearch(bucketStart, 0, bucketCount, now);
+            if (index < 0) {
+                // bucket missing, create and insert
+                insertBucket(~index, now);
+            }
+        }
+    }
+
+    /**
+     * Insert new bucket at requested index and starting time.
+     */
+    private void insertBucket(int index, long start) {
+        // create more buckets when needed
+        if (bucketCount + 1 > bucketStart.length) {
+            final int newLength = bucketStart.length + 10;
+            bucketStart = Arrays.copyOf(bucketStart, newLength);
+            rx = Arrays.copyOf(rx, newLength);
+            tx = Arrays.copyOf(tx, newLength);
+        }
+
+        // create gap when inserting bucket in middle
+        if (index < bucketCount) {
+            final int dstPos = index + 1;
+            final int length = bucketCount - index;
+
+            System.arraycopy(bucketStart, index, bucketStart, dstPos, length);
+            System.arraycopy(rx, index, rx, dstPos, length);
+            System.arraycopy(tx, index, tx, dstPos, length);
+        }
+
+        bucketStart[index] = start;
+        rx[index] = 0;
+        tx[index] = 0;
+        bucketCount++;
+    }
+
+    /**
+     * Remove buckets older than requested cutoff.
+     */
+    public void removeBucketsBefore(long cutoff) {
+        int i;
+        for (i = 0; i < bucketCount; i++) {
+            final long curStart = bucketStart[i];
+            final long curEnd = curStart + bucketDuration;
+
+            // cutoff happens before or during this bucket; everything before
+            // this bucket should be removed.
+            if (curEnd > cutoff) break;
+        }
+
+        if (i > 0) {
+            final int length = bucketStart.length;
+            bucketStart = Arrays.copyOfRange(bucketStart, i, length);
+            rx = Arrays.copyOfRange(rx, i, length);
+            tx = Arrays.copyOfRange(tx, i, length);
+            bucketCount -= i;
+        }
+    }
+
+    public void dump(String prefix, PrintWriter pw) {
+        // TODO: consider stripping identity when dumping
+        pw.print(prefix);
+        pw.print("NetworkStatsHistory: networkType="); pw.print(networkType);
+        pw.print(" identity="); pw.print(identity);
+        pw.print(" uid="); pw.println(uid);
+        for (int i = 0; i < bucketCount; i++) {
+            pw.print(prefix);
+            pw.print("  timestamp="); pw.print(bucketStart[i]);
+            pw.print(" rx="); pw.print(rx[i]);
+            pw.print(" tx="); pw.println(tx[i]);
+        }
+    }
+
+    @Override
+    public String toString() {
+        final CharArrayWriter writer = new CharArrayWriter();
+        dump("", new PrintWriter(writer));
+        return writer.toString();
+    }
+
+    public static final Creator<NetworkStatsHistory> CREATOR = new Creator<NetworkStatsHistory>() {
+        public NetworkStatsHistory createFromParcel(Parcel in) {
+            return new NetworkStatsHistory(in);
+        }
+
+        public NetworkStatsHistory[] newArray(int size) {
+            return new NetworkStatsHistory[size];
+        }
+    };
+
+    private static long[] readLongArray(DataInputStream in) throws IOException {
+        final int size = in.readInt();
+        final long[] values = new long[size];
+        for (int i = 0; i < values.length; i++) {
+            values[i] = in.readLong();
+        }
+        return values;
+    }
+
+    private static void writeLongArray(DataOutputStream out, long[] values, int size) throws IOException {
+        if (size > values.length) {
+            throw new IllegalArgumentException("size larger than length");
+        }
+        out.writeInt(size);
+        for (int i = 0; i < size; i++) {
+            out.writeLong(values[i]);
+        }
+    }
+
+    private static long[] readLongArray(Parcel in) {
+        final int size = in.readInt();
+        final long[] values = new long[size];
+        for (int i = 0; i < values.length; i++) {
+            values[i] = in.readLong();
+        }
+        return values;
+    }
+
+    private static void writeLongArray(Parcel out, long[] values, int size) {
+        if (size > values.length) {
+            throw new IllegalArgumentException("size larger than length");
+        }
+        out.writeInt(size);
+        for (int i = 0; i < size; i++) {
+            out.writeLong(values[i]);
+        }
+    }
+
+}
diff --git a/core/java/android/net/TrafficStats.java b/core/java/android/net/TrafficStats.java
index c0ff734..8ab64fa 100644
--- a/core/java/android/net/TrafficStats.java
+++ b/core/java/android/net/TrafficStats.java
@@ -141,7 +141,8 @@
 
             // subtract starting values and return delta
             final NetworkStats profilingStop = getNetworkStatsForUid(context);
-            final NetworkStats profilingDelta = profilingStop.subtract(sActiveProfilingStart);
+            final NetworkStats profilingDelta = profilingStop.subtract(
+                    sActiveProfilingStart, false);
             sActiveProfilingStart = null;
             return profilingDelta;
         }
diff --git a/core/java/android/os/INetStatService.aidl b/core/java/android/os/INetStatService.aidl
deleted file mode 100644
index a8f3de0..0000000
--- a/core/java/android/os/INetStatService.aidl
+++ /dev/null
@@ -1,35 +0,0 @@
-/*
- * Copyright (C) 2008 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.os;
-
-/**
- * Retrieves packet and byte counts for the phone data interface,
- * and for all interfaces.
- * Used for the data activity icon and the phone status in Settings.
- *
- * {@hide}
- */
-interface INetStatService {
-    long getMobileTxPackets();
-    long getMobileRxPackets();
-    long getMobileTxBytes();
-    long getMobileRxBytes();
-    long getTotalTxPackets();
-    long getTotalRxPackets();
-    long getTotalTxBytes();
-    long getTotalRxBytes();
-}
diff --git a/core/tests/coretests/src/android/net/NetworkStatsHistoryTest.java b/core/tests/coretests/src/android/net/NetworkStatsHistoryTest.java
new file mode 100644
index 0000000..eb63c0d
--- /dev/null
+++ b/core/tests/coretests/src/android/net/NetworkStatsHistoryTest.java
@@ -0,0 +1,210 @@
+/*
+ * Copyright (C) 2011 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;
+
+import static android.net.ConnectivityManager.TYPE_MOBILE;
+import static android.net.NetworkStatsHistory.UID_ALL;
+import static android.text.format.DateUtils.DAY_IN_MILLIS;
+import static android.text.format.DateUtils.HOUR_IN_MILLIS;
+import static android.text.format.DateUtils.MINUTE_IN_MILLIS;
+import static android.text.format.DateUtils.SECOND_IN_MILLIS;
+import static android.text.format.DateUtils.WEEK_IN_MILLIS;
+import static android.text.format.DateUtils.YEAR_IN_MILLIS;
+
+import android.test.suitebuilder.annotation.SmallTest;
+import android.test.suitebuilder.annotation.Suppress;
+import android.util.Log;
+
+import junit.framework.TestCase;
+
+import java.util.Random;
+
+@SmallTest
+public class NetworkStatsHistoryTest extends TestCase {
+    private static final String TAG = "NetworkStatsHistoryTest";
+
+    private static final long TEST_START = 1194220800000L;
+
+    private NetworkStatsHistory stats;
+
+    @Override
+    protected void tearDown() throws Exception {
+        super.tearDown();
+        if (stats != null) {
+            assertConsistent(stats);
+        }
+    }
+
+    public void testRecordSingleBucket() throws Exception {
+        final long BUCKET_SIZE = HOUR_IN_MILLIS;
+        stats = buildStats(BUCKET_SIZE);
+
+        // record data into narrow window to get single bucket
+        stats.recordData(TEST_START, TEST_START + SECOND_IN_MILLIS, 1024L, 2048L);
+
+        assertEquals(1, stats.bucketCount);
+        assertBucket(stats, 0, 1024L, 2048L);
+    }
+
+    public void testRecordEqualBuckets() throws Exception {
+        final long bucketDuration = HOUR_IN_MILLIS;
+        stats = buildStats(bucketDuration);
+
+        // split equally across two buckets
+        final long recordStart = TEST_START + (bucketDuration / 2);
+        stats.recordData(recordStart, recordStart + bucketDuration, 1024L, 128L);
+
+        assertEquals(2, stats.bucketCount);
+        assertBucket(stats, 0, 512L, 64L);
+        assertBucket(stats, 1, 512L, 64L);
+    }
+
+    public void testRecordTouchingBuckets() throws Exception {
+        final long BUCKET_SIZE = 15 * MINUTE_IN_MILLIS;
+        stats = buildStats(BUCKET_SIZE);
+
+        // split almost completely into middle bucket, but with a few minutes
+        // overlap into neighboring buckets. total record is 20 minutes.
+        final long recordStart = (TEST_START + BUCKET_SIZE) - MINUTE_IN_MILLIS;
+        final long recordEnd = (TEST_START + (BUCKET_SIZE * 2)) + (MINUTE_IN_MILLIS * 4);
+        stats.recordData(recordStart, recordEnd, 1000L, 5000L);
+
+        assertEquals(3, stats.bucketCount);
+        // first bucket should have (1/20 of value)
+        assertBucket(stats, 0, 50L, 250L);
+        // second bucket should have (15/20 of value)
+        assertBucket(stats, 1, 750L, 3750L);
+        // final bucket should have (4/20 of value)
+        assertBucket(stats, 2, 200L, 1000L);
+    }
+
+    public void testRecordGapBuckets() throws Exception {
+        final long BUCKET_SIZE = HOUR_IN_MILLIS;
+        stats = buildStats(BUCKET_SIZE);
+
+        // record some data today and next week with large gap
+        final long firstStart = TEST_START;
+        final long lastStart = TEST_START + WEEK_IN_MILLIS;
+        stats.recordData(firstStart, firstStart + SECOND_IN_MILLIS, 128L, 256L);
+        stats.recordData(lastStart, lastStart + SECOND_IN_MILLIS, 64L, 512L);
+
+        // we should have two buckets, far apart from each other
+        assertEquals(2, stats.bucketCount);
+        assertBucket(stats, 0, 128L, 256L);
+        assertBucket(stats, 1, 64L, 512L);
+
+        // now record something in middle, spread across two buckets
+        final long middleStart = TEST_START + DAY_IN_MILLIS;
+        final long middleEnd = middleStart + (HOUR_IN_MILLIS * 2);
+        stats.recordData(middleStart, middleEnd, 2048L, 2048L);
+
+        // now should have four buckets, with new record in middle two buckets
+        assertEquals(4, stats.bucketCount);
+        assertBucket(stats, 0, 128L, 256L);
+        assertBucket(stats, 1, 1024L, 1024L);
+        assertBucket(stats, 2, 1024L, 1024L);
+        assertBucket(stats, 3, 64L, 512L);
+    }
+
+    public void testRecordOverlapBuckets() throws Exception {
+        final long BUCKET_SIZE = HOUR_IN_MILLIS;
+        stats = buildStats(BUCKET_SIZE);
+
+        // record some data in one bucket, and another overlapping buckets
+        stats.recordData(TEST_START, TEST_START + SECOND_IN_MILLIS, 256L, 256L);
+        final long midStart = TEST_START + (HOUR_IN_MILLIS / 2);
+        stats.recordData(midStart, midStart + HOUR_IN_MILLIS, 1024L, 1024L);
+
+        // should have two buckets, with some data mixed together
+        assertEquals(2, stats.bucketCount);
+        assertBucket(stats, 0, 768L, 768L);
+        assertBucket(stats, 1, 512L, 512L);
+    }
+
+    public void testRemove() throws Exception {
+        final long BUCKET_SIZE = HOUR_IN_MILLIS;
+        stats = buildStats(BUCKET_SIZE);
+
+        // record some data across 24 buckets
+        stats.recordData(TEST_START, TEST_START + DAY_IN_MILLIS, 24L, 24L);
+        assertEquals(24, stats.bucketCount);
+
+        // try removing far before buckets; should be no change
+        stats.removeBucketsBefore(TEST_START - YEAR_IN_MILLIS);
+        assertEquals(24, stats.bucketCount);
+
+        // try removing just moments into first bucket; should be no change
+        // since that bucket contains data beyond the cutoff
+        stats.removeBucketsBefore(TEST_START + SECOND_IN_MILLIS);
+        assertEquals(24, stats.bucketCount);
+
+        // try removing single bucket
+        stats.removeBucketsBefore(TEST_START + HOUR_IN_MILLIS);
+        assertEquals(23, stats.bucketCount);
+
+        // try removing multiple buckets
+        stats.removeBucketsBefore(TEST_START + (4 * HOUR_IN_MILLIS));
+        assertEquals(20, stats.bucketCount);
+
+        // try removing all buckets
+        stats.removeBucketsBefore(TEST_START + YEAR_IN_MILLIS);
+        assertEquals(0, stats.bucketCount);
+    }
+
+    @Suppress
+    public void testFuzzing() throws Exception {
+        try {
+            // fuzzing with random events, looking for crashes
+            final Random r = new Random();
+            for (int i = 0; i < 500; i++) {
+                stats = buildStats(r.nextLong());
+                for (int j = 0; j < 10000; j++) {
+                    if (r.nextBoolean()) {
+                        // add range
+                        final long start = r.nextLong();
+                        final long end = start + r.nextInt();
+                        stats.recordData(start, end, r.nextLong(), r.nextLong());
+                    } else {
+                        // trim something
+                        stats.removeBucketsBefore(r.nextLong());
+                    }
+                }
+                assertConsistent(stats);
+            }
+        } catch (Throwable e) {
+            Log.e(TAG, String.valueOf(stats));
+            throw new RuntimeException(e);
+        }
+    }
+
+    private static NetworkStatsHistory buildStats(long bucketSize) {
+        return new NetworkStatsHistory(TYPE_MOBILE, null, UID_ALL, bucketSize);
+    }
+
+    private static void assertConsistent(NetworkStatsHistory stats) {
+        // verify timestamps are monotonic
+        for (int i = 1; i < stats.bucketCount; i++) {
+            assertTrue(stats.bucketStart[i - 1] < stats.bucketStart[i]);
+        }
+    }
+
+    private static void assertBucket(NetworkStatsHistory stats, int index, long rx, long tx) {
+        assertEquals("unexpected rx", rx, stats.rx[index]);
+        assertEquals("unexpected tx", tx, stats.tx[index]);
+    }
+
+}
diff --git a/core/tests/coretests/src/android/net/NetworkStatsTest.java b/core/tests/coretests/src/android/net/NetworkStatsTest.java
index 45719c2..23eb9cf 100644
--- a/core/tests/coretests/src/android/net/NetworkStatsTest.java
+++ b/core/tests/coretests/src/android/net/NetworkStatsTest.java
@@ -47,8 +47,9 @@
                 .addEntry(TEST_IFACE, 100, 1024, 0)
                 .addEntry(TEST_IFACE, 101, 0, 1024).build();
 
-        final NetworkStats result = after.subtract(before);
+        final NetworkStats result = after.subtract(before, true);
 
+        // identical data should result in zero delta
         assertEquals(0, result.rx[0]);
         assertEquals(0, result.tx[0]);
         assertEquals(0, result.rx[1]);
@@ -64,7 +65,7 @@
                 .addEntry(TEST_IFACE, 100, 1025, 2)
                 .addEntry(TEST_IFACE, 101, 3, 1028).build();
 
-        final NetworkStats result = after.subtract(before);
+        final NetworkStats result = after.subtract(before, true);
 
         // expect delta between measurements
         assertEquals(1, result.rx[0]);
@@ -83,7 +84,7 @@
                 .addEntry(TEST_IFACE, 101, 0, 1024)
                 .addEntry(TEST_IFACE, 102, 1024, 1024).build();
 
-        final NetworkStats result = after.subtract(before);
+        final NetworkStats result = after.subtract(before, true);
 
         // its okay to have new rows
         assertEquals(0, result.rx[0]);
diff --git a/services/java/com/android/server/NetStatService.java b/services/java/com/android/server/NetStatService.java
deleted file mode 100644
index 7fe6743..0000000
--- a/services/java/com/android/server/NetStatService.java
+++ /dev/null
@@ -1,96 +0,0 @@
-/*
- * Copyright (C) 2008 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 com.android.server;
-
-import android.content.Context;
-import android.net.TrafficStats;
-import android.os.INetStatService;
-import android.os.SystemClock;
-
-import java.io.FileDescriptor;
-import java.io.PrintWriter;
-
-public class NetStatService extends INetStatService.Stub {
-    private final Context mContext;
-
-    public NetStatService(Context context) {
-        mContext = context;
-    }
-
-    public long getMobileTxPackets() {
-        return TrafficStats.getMobileTxPackets();
-    }
-
-    public long getMobileRxPackets() {
-        return TrafficStats.getMobileRxPackets();
-    }
-
-    public long getMobileTxBytes() {
-        return TrafficStats.getMobileTxBytes();
-    }
-
-    public long getMobileRxBytes() {
-        return TrafficStats.getMobileRxBytes();
-    }
-
-    public long getTotalTxPackets() {
-        return TrafficStats.getTotalTxPackets();
-    }
-
-    public long getTotalRxPackets() {
-        return TrafficStats.getTotalRxPackets();
-    }
-
-    public long getTotalTxBytes() {
-        return TrafficStats.getTotalTxBytes();
-    }
-
-    public long getTotalRxBytes() {
-        return TrafficStats.getTotalRxBytes();
-    }
-
-    @Override
-    protected void dump(FileDescriptor fd, PrintWriter pw, String[] args) {
-        // This data is accessible to any app -- no permission check needed.
-
-        pw.print("Elapsed: total=");
-        pw.print(SystemClock.elapsedRealtime());
-        pw.print("ms awake=");
-        pw.print(SystemClock.uptimeMillis());
-        pw.println("ms");
-
-        pw.print("Mobile: Tx=");
-        pw.print(getMobileTxBytes());
-        pw.print("B/");
-        pw.print(getMobileTxPackets());
-        pw.print("Pkts Rx=");
-        pw.print(getMobileRxBytes());
-        pw.print("B/");
-        pw.print(getMobileRxPackets());
-        pw.println("Pkts");
-
-        pw.print("Total: Tx=");
-        pw.print(getTotalTxBytes());
-        pw.print("B/");
-        pw.print(getTotalTxPackets());
-        pw.print("Pkts Rx=");
-        pw.print(getTotalRxBytes());
-        pw.print("B/");
-        pw.print(getTotalRxPackets());
-        pw.println("Pkts");
-    }
-}
diff --git a/services/java/com/android/server/SystemServer.java b/services/java/com/android/server/SystemServer.java
index 4cd601f..596cbac 100644
--- a/services/java/com/android/server/SystemServer.java
+++ b/services/java/com/android/server/SystemServer.java
@@ -49,6 +49,7 @@
 import com.android.server.accessibility.AccessibilityManagerService;
 import com.android.server.am.ActivityManagerService;
 import com.android.server.net.NetworkPolicyManagerService;
+import com.android.server.net.NetworkStatsService;
 import com.android.server.pm.PackageManagerService;
 import com.android.server.usb.UsbService;
 import com.android.server.wm.WindowManagerService;
@@ -116,7 +117,9 @@
         LightsService lights = null;
         PowerManagerService power = null;
         BatteryService battery = null;
+        AlarmManagerService alarm = null;
         NetworkManagementService networkManagement = null;
+        NetworkStatsService networkStats = null;
         NetworkPolicyManagerService networkPolicy = null;
         ConnectivityService connectivity = null;
         IPackageManager pm = null;
@@ -188,7 +191,7 @@
             power.init(context, lights, ActivityManagerService.getDefault(), battery);
 
             Slog.i(TAG, "Alarm Manager");
-            AlarmManagerService alarm = new AlarmManagerService(context);
+            alarm = new AlarmManagerService(context);
             ServiceManager.addService(Context.ALARM_SERVICE, alarm);
 
             Slog.i(TAG, "Init Watchdog");
@@ -274,22 +277,6 @@
             }
 
             try {
-                Slog.i(TAG, "NetStat Service");
-                ServiceManager.addService("netstat", new NetStatService(context));
-            } catch (Throwable e) {
-                Slog.e(TAG, "Failure starting NetStat Service", e);
-            }
-
-            try {
-                Slog.i(TAG, "NetworkPolicy Service");
-                networkPolicy = new NetworkPolicyManagerService(
-                        context, ActivityManagerService.self(), power);
-                ServiceManager.addService(Context.NETWORK_POLICY_SERVICE, networkPolicy);
-            } catch (Throwable e) {
-                Slog.e(TAG, "Failure starting Connectivity Service", e);
-            }
-
-            try {
                 Slog.i(TAG, "NetworkManagement Service");
                 networkManagement = NetworkManagementService.create(context);
                 ServiceManager.addService(Context.NETWORKMANAGEMENT_SERVICE, networkManagement);
@@ -298,6 +285,23 @@
             }
 
             try {
+                Slog.i(TAG, "NetworkStats Service");
+                networkStats = new NetworkStatsService(context, networkManagement, alarm);
+                ServiceManager.addService(Context.NETWORK_STATS_SERVICE, networkStats);
+            } catch (Throwable e) {
+                Slog.e(TAG, "Failure starting NetworkStats Service", e);
+            }
+
+            try {
+                Slog.i(TAG, "NetworkPolicy Service");
+                networkPolicy = new NetworkPolicyManagerService(
+                        context, ActivityManagerService.self(), power, networkStats);
+                ServiceManager.addService(Context.NETWORK_POLICY_SERVICE, networkPolicy);
+            } catch (Throwable e) {
+                Slog.e(TAG, "Failure starting NetworkPolicy Service", e);
+            }
+
+            try {
                 Slog.i(TAG, "Connectivity Service");
                 connectivity = new ConnectivityService(context, networkManagement, networkPolicy);
                 ServiceManager.addService(Context.CONNECTIVITY_SERVICE, connectivity);
@@ -535,6 +539,7 @@
         // These are needed to propagate to the runnable below.
         final Context contextF = context;
         final BatteryService batteryF = battery;
+        final NetworkStatsService networkStatsF = networkStats;
         final NetworkPolicyManagerService networkPolicyF = networkPolicy;
         final ConnectivityService connectivityF = connectivity;
         final DockObserver dockF = dock;
@@ -561,6 +566,7 @@
 
                 startSystemUi(contextF);
                 if (batteryF != null) batteryF.systemReady();
+                if (networkStatsF != null) networkStatsF.systemReady();
                 if (networkPolicyF != null) networkPolicyF.systemReady();
                 if (connectivityF != null) connectivityF.systemReady();
                 if (dockF != null) dockF.systemReady();
diff --git a/services/java/com/android/server/net/NetworkPolicyManagerService.java b/services/java/com/android/server/net/NetworkPolicyManagerService.java
index 1ae8284..17c7161 100644
--- a/services/java/com/android/server/net/NetworkPolicyManagerService.java
+++ b/services/java/com/android/server/net/NetworkPolicyManagerService.java
@@ -35,10 +35,10 @@
 import android.net.ConnectivityManager;
 import android.net.INetworkPolicyListener;
 import android.net.INetworkPolicyManager;
+import android.net.INetworkStatsService;
 import android.os.IPowerManager;
 import android.os.RemoteCallbackList;
 import android.os.RemoteException;
-import android.util.Log;
 import android.util.Slog;
 import android.util.SparseArray;
 import android.util.SparseBooleanArray;
@@ -59,11 +59,12 @@
     private static final String TAG = "NetworkPolicy";
     private static final boolean LOGD = true;
 
-    private Context mContext;
-    private IActivityManager mActivityManager;
-    private IPowerManager mPowerManager;
+    private final Context mContext;
+    private final IActivityManager mActivityManager;
+    private final IPowerManager mPowerManager;
+    private final INetworkStatsService mNetworkStats;
 
-    private Object mRulesLock = new Object();
+    private final Object mRulesLock = new Object();
 
     private boolean mScreenOn;
 
@@ -80,21 +81,24 @@
     private final RemoteCallbackList<INetworkPolicyListener> mListeners = new RemoteCallbackList<
             INetworkPolicyListener>();
 
-    // TODO: periodically poll network stats and write to disk
     // TODO: save/restore policy information from disk
 
     // TODO: keep whitelist of system-critical services that should never have
     // rules enforced, such as system, phone, and radio UIDs.
 
-    public NetworkPolicyManagerService(
-            Context context, IActivityManager activityManager, IPowerManager powerManager) {
+    // TODO: keep record of billing cycle details, and limit rules
+    // TODO: keep map of interfaces-to-billing-relationship
+
+    public NetworkPolicyManagerService(Context context, IActivityManager activityManager,
+            IPowerManager powerManager, INetworkStatsService networkStats) {
         mContext = checkNotNull(context, "missing context");
         mActivityManager = checkNotNull(activityManager, "missing activityManager");
         mPowerManager = checkNotNull(powerManager, "missing powerManager");
+        mNetworkStats = checkNotNull(networkStats, "missing networkStats");
     }
 
     public void systemReady() {
-        // TODO: read current policy+stats from disk and generate NMS rules
+        // TODO: read current policy from disk
 
         updateScreenOn();
 
@@ -114,18 +118,13 @@
         screenFilter.addAction(Intent.ACTION_SCREEN_OFF);
         mContext.registerReceiver(mScreenReceiver, screenFilter);
 
-        final IntentFilter shutdownFilter = new IntentFilter();
-        shutdownFilter.addAction(Intent.ACTION_SHUTDOWN);
-        mContext.registerReceiver(mShutdownReceiver, shutdownFilter);
-
     }
 
     private IProcessObserver mProcessObserver = new IProcessObserver.Stub() {
         @Override
         public void onForegroundActivitiesChanged(int pid, int uid, boolean foregroundActivities) {
             // only someone like AMS should only be calling us
-            mContext.enforceCallingOrSelfPermission(
-                    MANAGE_APP_TOKENS, "requires MANAGE_APP_TOKENS permission");
+            mContext.enforceCallingOrSelfPermission(MANAGE_APP_TOKENS, TAG);
 
             synchronized (mRulesLock) {
                 // because a uid can have multiple pids running inside, we need to
@@ -145,8 +144,7 @@
         @Override
         public void onProcessDied(int pid, int uid) {
             // only someone like AMS should only be calling us
-            mContext.enforceCallingOrSelfPermission(
-                    MANAGE_APP_TOKENS, "requires MANAGE_APP_TOKENS permission");
+            mContext.enforceCallingOrSelfPermission(MANAGE_APP_TOKENS, TAG);
 
             synchronized (mRulesLock) {
                 // clear records and recompute, when they exist
@@ -170,19 +168,10 @@
         }
     };
 
-    private BroadcastReceiver mShutdownReceiver = new BroadcastReceiver() {
-        @Override
-        public void onReceive(Context context, Intent intent) {
-            // TODO: persist any pending stats during clean shutdown
-            Log.d(TAG, "persisting stats");
-        }
-    };
-
     @Override
     public void setUidPolicy(int uid, int policy) {
         // TODO: create permission for modifying data policy
-        mContext.enforceCallingOrSelfPermission(
-                UPDATE_DEVICE_STATS, "requires UPDATE_DEVICE_STATS permission");
+        mContext.enforceCallingOrSelfPermission(UPDATE_DEVICE_STATS, TAG);
 
         final int oldPolicy;
         synchronized (mRulesLock) {
@@ -228,7 +217,7 @@
 
     @Override
     protected void dump(FileDescriptor fd, PrintWriter fout, String[] args) {
-        mContext.enforceCallingOrSelfPermission(DUMP, "requires DUMP permission");
+        mContext.enforceCallingOrSelfPermission(DUMP, TAG);
 
         synchronized (mRulesLock) {
             fout.println("Policy status for known UIDs:");
@@ -366,7 +355,7 @@
         }
         return value;
     }
-    
+
     private static void collectKeys(SparseIntArray source, SparseBooleanArray target) {
         final int size = source.size();
         for (int i = 0; i < size; i++) {
diff --git a/services/java/com/android/server/net/NetworkStatsService.java b/services/java/com/android/server/net/NetworkStatsService.java
new file mode 100644
index 0000000..d9c1f25
--- /dev/null
+++ b/services/java/com/android/server/net/NetworkStatsService.java
@@ -0,0 +1,403 @@
+/*
+ * Copyright (C) 2008 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 com.android.server.net;
+
+import static android.Manifest.permission.DUMP;
+import static android.Manifest.permission.SHUTDOWN;
+import static android.Manifest.permission.UPDATE_DEVICE_STATS;
+import static android.net.ConnectivityManager.TYPE_MOBILE;
+import static android.net.ConnectivityManager.TYPE_WIFI;
+import static android.net.NetworkStats.UID_ALL;
+
+import android.app.AlarmManager;
+import android.app.IAlarmManager;
+import android.app.PendingIntent;
+import android.content.BroadcastReceiver;
+import android.content.Context;
+import android.content.Intent;
+import android.content.IntentFilter;
+import android.net.INetworkStatsService;
+import android.net.LinkProperties;
+import android.net.NetworkStats;
+import android.net.NetworkStatsHistory;
+import android.net.wifi.WifiManager;
+import android.os.Handler;
+import android.os.HandlerThread;
+import android.os.INetworkManagementService;
+import android.os.RemoteException;
+import android.os.SystemClock;
+import android.telephony.TelephonyManager;
+import android.text.format.DateUtils;
+import android.util.NtpTrustedTime;
+import android.util.Slog;
+import android.util.TrustedTime;
+
+import com.android.internal.telephony.Phone;
+import com.android.internal.telephony.TelephonyIntents;
+import com.google.android.collect.Maps;
+
+import java.io.FileDescriptor;
+import java.io.PrintWriter;
+import java.util.HashMap;
+
+/**
+ * Collect and persist detailed network statistics, and provide this data to
+ * other system services.
+ */
+public class NetworkStatsService extends INetworkStatsService.Stub {
+    private static final String TAG = "NetworkStatsService";
+    private static final boolean LOGD = true;
+
+    private final Context mContext;
+    private final INetworkManagementService mNetworkManager;
+    private final IAlarmManager mAlarmManager;
+    private final TrustedTime mTime;
+
+    private static final String ACTION_NETWORK_STATS_POLL =
+            "com.android.server.action.NETWORK_STATS_POLL";
+
+    private PendingIntent mPollIntent;
+
+    // TODO: move tweakable params to Settings.Secure
+    // TODO: listen for kernel push events through netd instead of polling
+
+    private static final long KB_IN_BYTES = 1024;
+
+    private static final long POLL_INTERVAL = AlarmManager.INTERVAL_FIFTEEN_MINUTES;
+    private static final long SUMMARY_BUCKET_DURATION = 6 * DateUtils.HOUR_IN_MILLIS;
+    private static final long SUMMARY_MAX_HISTORY = 90 * DateUtils.DAY_IN_MILLIS;
+
+    // TODO: remove these high-frequency testing values
+//    private static final long POLL_INTERVAL = 5 * DateUtils.SECOND_IN_MILLIS;
+//    private static final long SUMMARY_BUCKET_DURATION = 10 * DateUtils.SECOND_IN_MILLIS;
+//    private static final long SUMMARY_MAX_HISTORY = 2 * DateUtils.MINUTE_IN_MILLIS;
+
+    /** Minimum delta required to persist to disk. */
+    private static final long SUMMARY_PERSIST_THRESHOLD = 64 * KB_IN_BYTES;
+
+    private static final long TIME_CACHE_MAX_AGE = DateUtils.DAY_IN_MILLIS;
+
+    private final Object mStatsLock = new Object();
+
+    /** Set of active ifaces during this boot. */
+    private HashMap<String, InterfaceInfo> mActiveIface = Maps.newHashMap();
+    /** Set of historical stats for known ifaces. */
+    private HashMap<InterfaceInfo, NetworkStatsHistory> mIfaceStats = Maps.newHashMap();
+
+    private NetworkStats mLastPollStats;
+    private NetworkStats mLastPersistStats;
+
+    private final HandlerThread mHandlerThread;
+    private final Handler mHandler;
+
+    // TODO: collect detailed uid stats, storing tag-granularity data until next
+    // dropbox, and uid summary for a specific bucket count.
+
+    // TODO: periodically compile statistics and send to dropbox.
+
+    public NetworkStatsService(
+            Context context, INetworkManagementService networkManager, IAlarmManager alarmManager) {
+        // TODO: move to using cached NtpTrustedTime
+        this(context, networkManager, alarmManager, new NtpTrustedTime());
+    }
+
+    public NetworkStatsService(Context context, INetworkManagementService networkManager,
+            IAlarmManager alarmManager, TrustedTime time) {
+        mContext = checkNotNull(context, "missing Context");
+        mNetworkManager = checkNotNull(networkManager, "missing INetworkManagementService");
+        mAlarmManager = checkNotNull(alarmManager, "missing IAlarmManager");
+        mTime = checkNotNull(time, "missing TrustedTime");
+
+        mHandlerThread = new HandlerThread(TAG);
+        mHandlerThread.start();
+        mHandler = new Handler(mHandlerThread.getLooper());
+    }
+
+    public void systemReady() {
+        // read historical stats from disk
+        readStatsLocked();
+
+        // watch other system services that claim interfaces
+        // TODO: protect incoming broadcast with permissions check.
+        // TODO: consider migrating this to ConnectivityService, but it might
+        // cause a circular dependency.
+        final IntentFilter interfaceFilter = new IntentFilter();
+        interfaceFilter.addAction(TelephonyIntents.ACTION_ANY_DATA_CONNECTION_STATE_CHANGED);
+        interfaceFilter.addAction(WifiManager.NETWORK_STATE_CHANGED_ACTION);
+        mContext.registerReceiver(mInterfaceReceiver, interfaceFilter);
+
+        // listen for periodic polling events
+        final IntentFilter pollFilter = new IntentFilter(ACTION_NETWORK_STATS_POLL);
+        mContext.registerReceiver(mPollReceiver, pollFilter, UPDATE_DEVICE_STATS, mHandler);
+
+        // persist stats during clean shutdown
+        final IntentFilter shutdownFilter = new IntentFilter(Intent.ACTION_SHUTDOWN);
+        mContext.registerReceiver(mShutdownReceiver, shutdownFilter, SHUTDOWN, null);
+
+        try {
+            registerPollAlarmLocked();
+        } catch (RemoteException e) {
+            Slog.w(TAG, "unable to register poll alarm");
+        }
+    }
+
+    /**
+     * Clear any existing {@link #ACTION_NETWORK_STATS_POLL} alarms, and
+     * reschedule based on current {@link #POLL_INTERVAL} value.
+     */
+    private void registerPollAlarmLocked() throws RemoteException {
+        if (mPollIntent != null) {
+            mAlarmManager.remove(mPollIntent);
+        }
+
+        mPollIntent = PendingIntent.getBroadcast(
+                mContext, 0, new Intent(ACTION_NETWORK_STATS_POLL), 0);
+
+        final long currentRealtime = SystemClock.elapsedRealtime();
+        mAlarmManager.setInexactRepeating(
+                AlarmManager.ELAPSED_REALTIME, currentRealtime, POLL_INTERVAL, mPollIntent);
+    }
+
+    @Override
+    public NetworkStatsHistory[] getNetworkStatsSummary(int networkType) {
+        // TODO: return history for requested types
+        return null;
+    }
+
+    @Override
+    public NetworkStatsHistory getNetworkStatsUid(int uid) {
+        // TODO: return history for requested uid
+        return null;
+    }
+
+    /**
+     * Receiver that watches for other system components that claim network
+     * interfaces. Used to associate {@link TelephonyManager#getSubscriberId()}
+     * with mobile interfaces.
+     */
+    private BroadcastReceiver mInterfaceReceiver = new BroadcastReceiver() {
+        @Override
+        public void onReceive(Context context, Intent intent) {
+            final String action = intent.getAction();
+            if (TelephonyIntents.ACTION_ANY_DATA_CONNECTION_STATE_CHANGED.equals(action)) {
+                final LinkProperties prop = intent.getParcelableExtra(
+                        Phone.DATA_LINK_PROPERTIES_KEY);
+                final String iface = prop != null ? prop.getInterfaceName() : null;
+                if (iface != null) {
+                    final TelephonyManager teleManager = (TelephonyManager) context
+                            .getSystemService(Context.TELEPHONY_SERVICE);
+                    final InterfaceInfo info = new InterfaceInfo(
+                            iface, TYPE_MOBILE, teleManager.getSubscriberId());
+                    reportActiveInterface(info);
+                }
+            } else if (WifiManager.NETWORK_STATE_CHANGED_ACTION.equals(action)) {
+                final LinkProperties prop = intent.getParcelableExtra(
+                        WifiManager.EXTRA_LINK_PROPERTIES);
+                final String iface = prop != null ? prop.getInterfaceName() : null;
+                if (iface != null) {
+                    final InterfaceInfo info = new InterfaceInfo(iface, TYPE_WIFI, null);
+                    reportActiveInterface(info);
+                }
+            }
+        }
+    };
+
+    private BroadcastReceiver mPollReceiver = new BroadcastReceiver() {
+        @Override
+        public void onReceive(Context context, Intent intent) {
+            // already running on background handler, network/io is safe, and
+            // caller verified to have UPDATE_DEVICE_STATS permission above.
+            synchronized (mStatsLock) {
+                // TODO: acquire wakelock while performing poll
+                performPollLocked();
+            }
+        }
+    };
+
+    private BroadcastReceiver mShutdownReceiver = new BroadcastReceiver() {
+        @Override
+        public void onReceive(Context context, Intent intent) {
+            // persist stats during clean shutdown
+            synchronized (mStatsLock) {
+                writeStatsLocked();
+            }
+        }
+    };
+
+    private void performPollLocked() {
+        if (LOGD) Slog.v(TAG, "performPollLocked()");
+
+        // try refreshing time source when stale
+        if (mTime.getCacheAge() > TIME_CACHE_MAX_AGE) {
+            mTime.forceRefresh();
+        }
+
+        // TODO: consider marking "untrusted" times in historical stats
+        final long currentTime = mTime.hasCache() ? mTime.currentTimeMillis()
+                : System.currentTimeMillis();
+
+        final NetworkStats current;
+        try {
+            current = mNetworkManager.getNetworkStatsSummary();
+        } catch (RemoteException e) {
+            Slog.w(TAG, "problem reading network stats");
+            return;
+        }
+
+        // update historical usage with delta since last poll
+        final NetworkStats pollDelta = computeStatsDelta(mLastPollStats, current);
+        final long timeStart = currentTime - pollDelta.elapsedRealtime;
+        for (String iface : pollDelta.getKnownIfaces()) {
+            final InterfaceInfo info = mActiveIface.get(iface);
+            if (info == null) {
+                if (LOGD) Slog.w(TAG, "unknown interface " + iface + ", ignoring stats");
+                continue;
+            }
+
+            final int index = pollDelta.findIndex(iface, UID_ALL);
+            final long rx = pollDelta.rx[index];
+            final long tx = pollDelta.tx[index];
+
+            final NetworkStatsHistory history = findOrCreateHistoryLocked(info);
+            history.recordData(timeStart, currentTime, rx, tx);
+            history.removeBucketsBefore(currentTime - SUMMARY_MAX_HISTORY);
+        }
+
+        mLastPollStats = current;
+
+        // decide if enough has changed to trigger persist
+        final NetworkStats persistDelta = computeStatsDelta(mLastPersistStats, current);
+        for (String iface : persistDelta.getKnownIfaces()) {
+            final int index = persistDelta.findIndex(iface, UID_ALL);
+            if (persistDelta.rx[index] > SUMMARY_PERSIST_THRESHOLD
+                    || persistDelta.tx[index] > SUMMARY_PERSIST_THRESHOLD) {
+                writeStatsLocked();
+                mLastPersistStats = current;
+                break;
+            }
+        }
+    }
+
+    private NetworkStatsHistory findOrCreateHistoryLocked(InterfaceInfo info) {
+        NetworkStatsHistory stats = mIfaceStats.get(info);
+        if (stats == null) {
+            stats = new NetworkStatsHistory(
+                    info.networkType, info.identity, UID_ALL, SUMMARY_BUCKET_DURATION);
+            mIfaceStats.put(info, stats);
+        }
+        return stats;
+    }
+
+    private void readStatsLocked() {
+        if (LOGD) Slog.v(TAG, "readStatsLocked()");
+        // TODO: read historical stats from disk using AtomicFile
+    }
+
+    private void writeStatsLocked() {
+        if (LOGD) Slog.v(TAG, "writeStatsLocked()");
+        // TODO: persist historical stats to disk using AtomicFile
+    }
+
+    @Override
+    protected void dump(FileDescriptor fd, PrintWriter pw, String[] args) {
+        mContext.enforceCallingOrSelfPermission(DUMP, TAG);
+
+        pw.println("Active interfaces:");
+        for (InterfaceInfo info : mActiveIface.values()) {
+            info.dump("  ", pw);
+        }
+
+        pw.println("Known historical stats:");
+        for (NetworkStatsHistory stats : mIfaceStats.values()) {
+            stats.dump("  ", pw);
+        }
+    }
+
+    /**
+     * Details for a well-known network interface, including its name, network
+     * type, and billing relationship identity (such as IMSI).
+     */
+    private static class InterfaceInfo {
+        public final String iface;
+        public final int networkType;
+        public final String identity;
+
+        public InterfaceInfo(String iface, int networkType, String identity) {
+            this.iface = iface;
+            this.networkType = networkType;
+            this.identity = identity;
+        }
+
+        @Override
+        public int hashCode() {
+            final int prime = 31;
+            int result = 1;
+            result = prime * result + ((identity == null) ? 0 : identity.hashCode());
+            result = prime * result + ((iface == null) ? 0 : iface.hashCode());
+            result = prime * result + networkType;
+            return result;
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+            if (obj instanceof InterfaceInfo) {
+                final InterfaceInfo info = (InterfaceInfo) obj;
+                return equal(iface, info.iface) && networkType == info.networkType
+                        && equal(identity, info.identity);
+            }
+            return false;
+        }
+
+        public void dump(String prefix, PrintWriter pw) {
+            pw.print(prefix);
+            pw.print("InterfaceInfo: iface="); pw.print(iface);
+            pw.print(" networkType="); pw.print(networkType);
+            pw.print(" identity="); pw.println(identity);
+        }
+    }
+
+    private void reportActiveInterface(InterfaceInfo info) {
+        synchronized (mStatsLock) {
+            // TODO: when interface redefined, port over historical stats
+            mActiveIface.put(info.iface, info);
+        }
+    }
+
+    /**
+     * Return the delta between two {@link NetworkStats} snapshots, where {@code
+     * before} can be {@code null}.
+     */
+    private static NetworkStats computeStatsDelta(NetworkStats before, NetworkStats current) {
+        if (before != null) {
+            return current.subtract(before, false);
+        } else {
+            return current;
+        }
+    }
+
+    private static boolean equal(Object a, Object b) {
+        return a == b || (a != null && a.equals(b));
+    }
+
+    private static <T> T checkNotNull(T value, String message) {
+        if (value == null) {
+            throw new NullPointerException(message);
+        }
+        return value;
+    }
+
+}
diff --git a/services/tests/servicestests/src/com/android/server/NetworkPolicyManagerServiceTest.java b/services/tests/servicestests/src/com/android/server/NetworkPolicyManagerServiceTest.java
index cf1171f..6552cdf 100644
--- a/services/tests/servicestests/src/com/android/server/NetworkPolicyManagerServiceTest.java
+++ b/services/tests/servicestests/src/com/android/server/NetworkPolicyManagerServiceTest.java
@@ -32,6 +32,7 @@
 import android.content.pm.PackageManager;
 import android.net.ConnectivityManager;
 import android.net.INetworkPolicyListener;
+import android.net.INetworkStatsService;
 import android.os.Binder;
 import android.os.IPowerManager;
 import android.test.AndroidTestCase;
@@ -57,6 +58,7 @@
 
     private IActivityManager mActivityManager;
     private IPowerManager mPowerManager;
+    private INetworkStatsService mStatsService;
     private INetworkPolicyListener mPolicyListener;
 
     private NetworkPolicyManagerService mService;
@@ -90,10 +92,11 @@
 
         mActivityManager = createMock(IActivityManager.class);
         mPowerManager = createMock(IPowerManager.class);
+        mStatsService = createMock(INetworkStatsService.class);
         mPolicyListener = createMock(INetworkPolicyListener.class);
 
         mService = new NetworkPolicyManagerService(
-                mServiceContext, mActivityManager, mPowerManager);
+                mServiceContext, mActivityManager, mPowerManager, mStatsService);
 
         // RemoteCallbackList needs a binder to use as key
         expect(mPolicyListener.asBinder()).andReturn(mStubBinder).atLeastOnce();
@@ -123,6 +126,7 @@
 
         mActivityManager = null;
         mPowerManager = null;
+        mStatsService = null;
         mPolicyListener = null;
 
         mService = null;
@@ -262,11 +266,11 @@
     }
 
     private void replay() {
-        EasyMock.replay(mActivityManager, mPowerManager, mPolicyListener);
+        EasyMock.replay(mActivityManager, mPowerManager, mStatsService, mPolicyListener);
     }
 
     private void verifyAndReset() {
-        EasyMock.verify(mActivityManager, mPowerManager, mPolicyListener);
-        EasyMock.reset(mActivityManager, mPowerManager, mPolicyListener);
+        EasyMock.verify(mActivityManager, mPowerManager, mStatsService, mPolicyListener);
+        EasyMock.reset(mActivityManager, mPowerManager, mStatsService, mPolicyListener);
     }
 }