diff --git a/libs/cputimeinstate/Android.bp b/libs/cputimeinstate/Android.bp
index 28cb138..9080ce1 100644
--- a/libs/cputimeinstate/Android.bp
+++ b/libs/cputimeinstate/Android.bp
@@ -19,7 +19,11 @@
     name: "libtimeinstate_test",
     srcs: ["testtimeinstate.cpp"],
     shared_libs: [
+        "libbase",
+        "libbpf",
+        "libbpf_android",
         "libtimeinstate",
+        "libnetdutils",
     ],
     cflags: [
         "-Werror",
diff --git a/libs/cputimeinstate/cputimeinstate.cpp b/libs/cputimeinstate/cputimeinstate.cpp
index 41cbde1..0e68e62 100644
--- a/libs/cputimeinstate/cputimeinstate.cpp
+++ b/libs/cputimeinstate/cputimeinstate.cpp
@@ -17,6 +17,7 @@
 #define LOG_TAG "libtimeinstate"
 
 #include "cputimeinstate.h"
+#include "timeinstate.h"
 
 #include <dirent.h>
 #include <errno.h>
@@ -38,23 +39,12 @@
 #include <libbpf.h>
 #include <log/log.h>
 
-#define BPF_FS_PATH "/sys/fs/bpf/"
-
 using android::base::StringPrintf;
 using android::base::unique_fd;
 
 namespace android {
 namespace bpf {
 
-struct time_key_t {
-    uint32_t uid;
-    uint32_t freq;
-};
-
-struct val_t {
-    uint64_t ar[100];
-};
-
 static std::mutex gInitializedMutex;
 static bool gInitialized = false;
 static uint32_t gNPolicies = 0;
diff --git a/libs/cputimeinstate/testtimeinstate.cpp b/libs/cputimeinstate/testtimeinstate.cpp
index d4b8738..6347de1 100644
--- a/libs/cputimeinstate/testtimeinstate.cpp
+++ b/libs/cputimeinstate/testtimeinstate.cpp
@@ -1,14 +1,24 @@
 
+#include "timeinstate.h"
+
+#include <sys/sysinfo.h>
+
 #include <unordered_map>
 #include <vector>
 
 #include <gtest/gtest.h>
 
+#include <android-base/unique_fd.h>
+#include <bpf/BpfMap.h>
 #include <cputimeinstate.h>
+#include <libbpf.h>
 
 namespace android {
 namespace bpf {
 
+static constexpr uint64_t NSEC_PER_SEC = 1000000000;
+static constexpr uint64_t NSEC_PER_YEAR = NSEC_PER_SEC * 60 * 60 * 24 * 365;
+
 using std::vector;
 
 TEST(TimeInStateTest, SingleUid) {
@@ -33,8 +43,95 @@
     }
 }
 
+TEST(TimeInStateTest, SingleAndAllUidConsistent) {
+    auto map = getUidsCpuFreqTimes();
+    ASSERT_TRUE(map.has_value());
+    ASSERT_FALSE(map->empty());
+
+    for (const auto &kv : *map) {
+        uint32_t uid = kv.first;
+        auto times1 = kv.second;
+        auto times2 = getUidCpuFreqTimes(uid);
+        ASSERT_TRUE(times2.has_value());
+
+        ASSERT_EQ(times1.size(), times2->size());
+        for (uint32_t i = 0; i < times1.size(); ++i) {
+            ASSERT_EQ(times1[i].size(), (*times2)[i].size());
+            for (uint32_t j = 0; j < times1[i].size(); ++j) {
+                ASSERT_LE((*times2)[i][j] - times1[i][j], NSEC_PER_SEC);
+            }
+        }
+    }
+}
+
+void TestCheckDelta(uint64_t before, uint64_t after) {
+    // Times should never decrease
+    ASSERT_LE(before, after);
+    // UID can't have run for more than ~1s on each CPU
+    ASSERT_LE(after - before, NSEC_PER_SEC * 2 * get_nprocs_conf());
+}
+
+TEST(TimeInStateTest, AllUidMonotonic) {
+    auto map1 = getUidsCpuFreqTimes();
+    ASSERT_TRUE(map1.has_value());
+    sleep(1);
+    auto map2 = getUidsCpuFreqTimes();
+    ASSERT_TRUE(map2.has_value());
+
+    for (const auto &kv : *map1) {
+        uint32_t uid = kv.first;
+        auto times = kv.second;
+        ASSERT_NE(map2->find(uid), map2->end());
+        for (uint32_t policy = 0; policy < times.size(); ++policy) {
+            for (uint32_t freqIdx = 0; freqIdx < times[policy].size(); ++freqIdx) {
+                auto before = times[policy][freqIdx];
+                auto after = (*map2)[uid][policy][freqIdx];
+                ASSERT_NO_FATAL_FAILURE(TestCheckDelta(before, after));
+            }
+        }
+    }
+}
+
+TEST(TimeInStateTest, AllUidSanityCheck) {
+    auto map = getUidsCpuFreqTimes();
+    ASSERT_TRUE(map.has_value());
+
+    bool foundLargeValue = false;
+    for (const auto &kv : *map) {
+        for (const auto &timeVec : kv.second) {
+            for (const auto &time : timeVec) {
+                ASSERT_LE(time, NSEC_PER_YEAR);
+                if (time > UINT32_MAX) foundLargeValue = true;
+            }
+        }
+    }
+    // UINT32_MAX nanoseconds is less than 5 seconds, so if every part of our pipeline is using
+    // uint64_t as expected, we should have some times higher than that.
+    ASSERT_TRUE(foundLargeValue);
+}
+
 TEST(TimeInStateTest, RemoveUid) {
-    auto times = getUidCpuFreqTimes(0);
+    uint32_t uid = 0;
+    {
+        // Find an unused UID
+        auto times = getUidsCpuFreqTimes();
+        ASSERT_TRUE(times.has_value());
+        ASSERT_FALSE(times->empty());
+        for (const auto &kv : *times) uid = std::max(uid, kv.first);
+        ++uid;
+    }
+    {
+        // Add a map entry for our fake UID by copying a real map entry
+        android::base::unique_fd fd{bpf_obj_get(BPF_FS_PATH "map_time_in_state_uid_times_map")};
+        ASSERT_GE(fd, 0);
+        time_key_t k;
+        ASSERT_FALSE(getFirstMapKey(fd, &k));
+        val_t val;
+        ASSERT_FALSE(findMapEntry(fd, &k, &val));
+        k.uid = uid;
+        ASSERT_FALSE(writeToMapEntry(fd, &k, &val, BPF_NOEXIST));
+    }
+    auto times = getUidCpuFreqTimes(uid);
     ASSERT_TRUE(times.has_value());
     ASSERT_FALSE(times->empty());
 
@@ -44,15 +141,12 @@
     }
     ASSERT_GT(sum, (uint64_t)0);
 
-    ASSERT_TRUE(clearUidCpuFreqTimes(0));
+    ASSERT_TRUE(clearUidCpuFreqTimes(uid));
 
-    auto times2 = getUidCpuFreqTimes(0);
-    ASSERT_TRUE(times2.has_value());
-    ASSERT_EQ(times2->size(), times->size());
-    for (size_t i = 0; i < times->size(); ++i) {
-        ASSERT_EQ((*times2)[i].size(), (*times)[i].size());
-        for (size_t j = 0; j < (*times)[i].size(); ++j) ASSERT_LE((*times2)[i][j], (*times)[i][j]);
-    }
+    auto allTimes = getUidsCpuFreqTimes();
+    ASSERT_TRUE(allTimes.has_value());
+    ASSERT_FALSE(allTimes->empty());
+    ASSERT_EQ(allTimes->find(uid), allTimes->end());
 }
 
 } // namespace bpf
diff --git a/libs/cputimeinstate/timeinstate.h b/libs/cputimeinstate/timeinstate.h
new file mode 100644
index 0000000..cf66ae7
--- /dev/null
+++ b/libs/cputimeinstate/timeinstate.h
@@ -0,0 +1,28 @@
+/*
+ * Copyright (C) 2018 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.
+ */
+
+#include <inttypes.h>
+
+#define BPF_FS_PATH "/sys/fs/bpf/"
+
+struct time_key_t {
+    uint32_t uid;
+    uint32_t freq;
+};
+
+struct val_t {
+    uint64_t ar[100];
+};