Collect historical network stats.

Periodically records delta network traffic into historical buckets to
support other services, such NetworkPolicyManager and Settings UI.

Introduces NetworkStatsHistory structure which contains sparse, uniform
buckets of data usage defined by timestamps.  Service periodically
polls NetworkStats and records changes into buckets.  It only persists
to disk when substantial changes have occured.  Current parameters
create 4 buckets each day, and persist for 90 days, resulting in about
8kB of data per network.

Only records stats for "well known" network interfaces that have been
claimed by Telephony or Wi-Fi subsystems.  Historical stats are also
keyed off identity (such as IMSI) to support SIM swapping.

Change-Id: Ia27d1289556a2bf9545fbc4f3b789425a01be53a
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/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;
+    }
+
+}