diff --git a/cmds/installd/tests/Android.bp b/cmds/installd/tests/Android.bp
index a32df22..b5b080d 100644
--- a/cmds/installd/tests/Android.bp
+++ b/cmds/installd/tests/Android.bp
@@ -14,3 +14,22 @@
         "libdiskusage",
     ],
 }
+
+cc_test {
+    name: "installd_cache_test",
+    clang: true,
+    srcs: ["installd_cache_test.cpp"],
+    shared_libs: [
+        "libbase",
+        "libbinder",
+        "libcutils",
+        "liblog",
+        "liblogwrap",
+        "libselinux",
+        "libutils",
+    ],
+    static_libs: [
+        "libinstalld",
+        "libdiskusage",
+    ],
+}
diff --git a/cmds/installd/tests/installd_cache_test.cpp b/cmds/installd/tests/installd_cache_test.cpp
new file mode 100644
index 0000000..50a47d2
--- /dev/null
+++ b/cmds/installd/tests/installd_cache_test.cpp
@@ -0,0 +1,323 @@
+/*
+ * Copyright (C) 2017 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 <stdlib.h>
+#include <string.h>
+#include <sys/statvfs.h>
+#include <sys/xattr.h>
+
+#include <android-base/logging.h>
+#include <android-base/stringprintf.h>
+#include <cutils/properties.h>
+#include <gtest/gtest.h>
+
+#include "InstalldNativeService.h"
+#include "globals.h"
+#include "utils.h"
+
+using android::base::StringPrintf;
+
+namespace android {
+namespace installd {
+
+constexpr const char* kTestUuid = "TEST";
+
+constexpr int64_t kKbInBytes = 1024;
+constexpr int64_t kMbInBytes = 1024 * kKbInBytes;
+constexpr int64_t kGbInBytes = 1024 * kMbInBytes;
+constexpr int64_t kTbInBytes = 1024 * kGbInBytes;
+
+static constexpr int FLAG_FREE_CACHE_V2 = 1 << 13;
+static constexpr int FLAG_FREE_CACHE_V2_DEFY_QUOTA = 1 << 14;
+
+int get_property(const char *key, char *value, const char *default_value) {
+    return property_get(key, value, default_value);
+}
+
+bool calculate_oat_file_path(char path[PKG_PATH_MAX] ATTRIBUTE_UNUSED,
+        const char *oat_dir ATTRIBUTE_UNUSED,
+        const char *apk_path ATTRIBUTE_UNUSED,
+        const char *instruction_set ATTRIBUTE_UNUSED) {
+    return false;
+}
+
+bool calculate_odex_file_path(char path[PKG_PATH_MAX] ATTRIBUTE_UNUSED,
+        const char *apk_path ATTRIBUTE_UNUSED,
+        const char *instruction_set ATTRIBUTE_UNUSED) {
+    return false;
+}
+
+bool create_cache_path(char path[PKG_PATH_MAX] ATTRIBUTE_UNUSED,
+        const char *src ATTRIBUTE_UNUSED,
+        const char *instruction_set ATTRIBUTE_UNUSED) {
+    return false;
+}
+
+static void mkdir(const char* path) {
+    const char* fullPath = StringPrintf("/data/local/tmp/user/0/%s", path).c_str();
+    ::mkdir(fullPath, 0755);
+}
+
+static void touch(const char* path, int len, int time) {
+    const char* fullPath = StringPrintf("/data/local/tmp/user/0/%s", path).c_str();
+    int fd = ::open(fullPath, O_RDWR | O_CREAT, 0644);
+    ::fallocate(fd, 0, 0, len);
+    ::close(fd);
+    struct utimbuf times;
+    times.actime = times.modtime = std::time(0) + time;
+    ::utime(fullPath, &times);
+}
+
+static int exists(const char* path) {
+    const char* fullPath = StringPrintf("/data/local/tmp/user/0/%s", path).c_str();
+    return ::access(fullPath, F_OK);
+}
+
+static int64_t size(const char* path) {
+    const char* fullPath = StringPrintf("/data/local/tmp/user/0/%s", path).c_str();
+    struct stat buf;
+    if (!stat(fullPath, &buf)) {
+        return buf.st_size;
+    } else {
+        return -1;
+    }
+}
+
+static int64_t free() {
+    struct statvfs buf;
+    if (!statvfs("/data/local/tmp", &buf)) {
+        return buf.f_bavail * buf.f_bsize;
+    } else {
+        return -1;
+    }
+}
+
+static void setxattr(const char* path, const char* key) {
+    const char* fullPath = StringPrintf("/data/local/tmp/user/0/%s", path).c_str();
+    ::setxattr(fullPath, key, "", 0, 0);
+}
+
+class CacheTest : public testing::Test {
+protected:
+    InstalldNativeService* service;
+    std::unique_ptr<std::string> testUuid;
+
+    virtual void SetUp() {
+        setenv("ANDROID_LOG_TAGS", "*:v", 1);
+        android::base::InitLogging(nullptr);
+
+        service = new InstalldNativeService();
+        testUuid = std::make_unique<std::string>();
+        *testUuid = std::string(kTestUuid);
+        system("mkdir -p /data/local/tmp/user/0");
+    }
+
+    virtual void TearDown() {
+        delete service;
+        system("rm -rf /data/local/tmp/user");
+    }
+};
+
+TEST_F(CacheTest, FreeCache_All) {
+    mkdir("com.example");
+    touch("com.example/normal", 1 * kMbInBytes, 60);
+    mkdir("com.example/cache");
+    mkdir("com.example/cache/foo");
+    touch("com.example/cache/foo/one", 1 * kMbInBytes, 60);
+    touch("com.example/cache/foo/two", 2 * kMbInBytes, 120);
+
+    EXPECT_EQ(0, exists("com.example/normal"));
+    EXPECT_EQ(0, exists("com.example/cache/foo/one"));
+    EXPECT_EQ(0, exists("com.example/cache/foo/two"));
+
+    service->freeCache(testUuid, kTbInBytes,
+            FLAG_FREE_CACHE_V2 | FLAG_FREE_CACHE_V2_DEFY_QUOTA);
+
+    EXPECT_EQ(0, exists("com.example/normal"));
+    EXPECT_EQ(-1, exists("com.example/cache/foo/one"));
+    EXPECT_EQ(-1, exists("com.example/cache/foo/two"));
+}
+
+TEST_F(CacheTest, FreeCache_Age) {
+    mkdir("com.example");
+    mkdir("com.example/cache");
+    mkdir("com.example/cache/foo");
+    touch("com.example/cache/foo/one", kMbInBytes, 60);
+    touch("com.example/cache/foo/two", kMbInBytes, 120);
+
+    service->freeCache(testUuid, free() + kKbInBytes,
+            FLAG_FREE_CACHE_V2 | FLAG_FREE_CACHE_V2_DEFY_QUOTA);
+
+    EXPECT_EQ(-1, exists("com.example/cache/foo/one"));
+    EXPECT_EQ(0, exists("com.example/cache/foo/two"));
+
+    service->freeCache(testUuid, free() + kKbInBytes,
+            FLAG_FREE_CACHE_V2 | FLAG_FREE_CACHE_V2_DEFY_QUOTA);
+
+    EXPECT_EQ(-1, exists("com.example/cache/foo/one"));
+    EXPECT_EQ(-1, exists("com.example/cache/foo/two"));
+}
+
+TEST_F(CacheTest, FreeCache_Tombstone) {
+    mkdir("com.example");
+    mkdir("com.example/cache");
+    mkdir("com.example/cache/foo");
+    touch("com.example/cache/foo/foo1", 1 * kMbInBytes, 60);
+    touch("com.example/cache/foo/foo2", 1 * kMbInBytes, 60);
+    mkdir("com.example/cache/bar");
+    touch("com.example/cache/bar/bar1", 2 * kMbInBytes, 120);
+    touch("com.example/cache/bar/bar2", 2 * kMbInBytes, 120);
+
+    setxattr("com.example/cache/bar", "user.cache_tombstone");
+
+    EXPECT_EQ(0, exists("com.example/cache/foo/foo1"));
+    EXPECT_EQ(0, exists("com.example/cache/foo/foo2"));
+    EXPECT_EQ(0, exists("com.example/cache/bar/bar1"));
+    EXPECT_EQ(0, exists("com.example/cache/bar/bar2"));
+    EXPECT_EQ(2 * kMbInBytes, size("com.example/cache/bar/bar1"));
+    EXPECT_EQ(2 * kMbInBytes, size("com.example/cache/bar/bar2"));
+
+    service->freeCache(testUuid, kTbInBytes,
+            FLAG_FREE_CACHE_V2 | FLAG_FREE_CACHE_V2_DEFY_QUOTA);
+
+    EXPECT_EQ(-1, exists("com.example/cache/foo/foo1"));
+    EXPECT_EQ(-1, exists("com.example/cache/foo/foo2"));
+    EXPECT_EQ(0, exists("com.example/cache/bar/bar1"));
+    EXPECT_EQ(0, exists("com.example/cache/bar/bar2"));
+    EXPECT_EQ(0, size("com.example/cache/bar/bar1"));
+    EXPECT_EQ(0, size("com.example/cache/bar/bar2"));
+}
+
+TEST_F(CacheTest, FreeCache_Atomic) {
+    mkdir("com.example");
+    mkdir("com.example/cache");
+    mkdir("com.example/cache/foo");
+    touch("com.example/cache/foo/foo1", 1 * kMbInBytes, 60);
+    touch("com.example/cache/foo/foo2", 1 * kMbInBytes, 120);
+
+    setxattr("com.example/cache/foo", "user.cache_atomic");
+
+    service->freeCache(testUuid, free() + kKbInBytes,
+            FLAG_FREE_CACHE_V2 | FLAG_FREE_CACHE_V2_DEFY_QUOTA);
+
+    EXPECT_EQ(-1, exists("com.example/cache/foo/foo1"));
+    EXPECT_EQ(-1, exists("com.example/cache/foo/foo2"));
+}
+
+TEST_F(CacheTest, FreeCache_AtomicTombstone) {
+    LOG(INFO) << "FreeCache_AtomicTombstone";
+
+    mkdir("com.example");
+    mkdir("com.example/cache");
+
+    // this dir must look really old for some reason?
+    mkdir("com.example/cache/atomic");
+    touch("com.example/cache/atomic/file1", kMbInBytes, 120);
+    touch("com.example/cache/atomic/file2", kMbInBytes, 120);
+    mkdir("com.example/cache/atomic/dir");
+    touch("com.example/cache/atomic/dir/file1", kMbInBytes, 120);
+    touch("com.example/cache/atomic/dir/file2", kMbInBytes, 120);
+    mkdir("com.example/cache/atomic/tomb");
+    touch("com.example/cache/atomic/tomb/file1", kMbInBytes, 120);
+    touch("com.example/cache/atomic/tomb/file2", kMbInBytes, 120);
+    mkdir("com.example/cache/atomic/tomb/dir");
+    touch("com.example/cache/atomic/tomb/dir/file1", kMbInBytes, 120);
+    touch("com.example/cache/atomic/tomb/dir/file2", kMbInBytes, 120);
+
+    mkdir("com.example/cache/tomb");
+    touch("com.example/cache/tomb/file1", kMbInBytes, 240);
+    touch("com.example/cache/tomb/file2", kMbInBytes, 240);
+    mkdir("com.example/cache/tomb/dir");
+    touch("com.example/cache/tomb/dir/file1", kMbInBytes, 240);
+    touch("com.example/cache/tomb/dir/file2", kMbInBytes, 240);
+    mkdir("com.example/cache/tomb/atomic");
+    touch("com.example/cache/tomb/atomic/file1", kMbInBytes, 60);
+    touch("com.example/cache/tomb/atomic/file2", kMbInBytes, 60);
+    mkdir("com.example/cache/tomb/atomic/dir");
+    touch("com.example/cache/tomb/atomic/dir/file1", kMbInBytes, 60);
+    touch("com.example/cache/tomb/atomic/dir/file2", kMbInBytes, 60);
+
+    setxattr("com.example/cache/atomic", "user.cache_atomic");
+    setxattr("com.example/cache/atomic/tomb", "user.cache_tombstone");
+    setxattr("com.example/cache/tomb", "user.cache_tombstone");
+    setxattr("com.example/cache/tomb/atomic", "user.cache_atomic");
+
+    service->freeCache(testUuid, free() + kKbInBytes,
+            FLAG_FREE_CACHE_V2 | FLAG_FREE_CACHE_V2_DEFY_QUOTA);
+
+    EXPECT_EQ(kMbInBytes, size("com.example/cache/atomic/file1"));
+    EXPECT_EQ(kMbInBytes, size("com.example/cache/atomic/file2"));
+    EXPECT_EQ(kMbInBytes, size("com.example/cache/atomic/dir/file1"));
+    EXPECT_EQ(kMbInBytes, size("com.example/cache/atomic/dir/file2"));
+    EXPECT_EQ(kMbInBytes, size("com.example/cache/atomic/tomb/file1"));
+    EXPECT_EQ(kMbInBytes, size("com.example/cache/atomic/tomb/file2"));
+    EXPECT_EQ(kMbInBytes, size("com.example/cache/atomic/tomb/dir/file1"));
+    EXPECT_EQ(kMbInBytes, size("com.example/cache/atomic/tomb/dir/file2"));
+
+    EXPECT_EQ(kMbInBytes, size("com.example/cache/tomb/file1"));
+    EXPECT_EQ(kMbInBytes, size("com.example/cache/tomb/file2"));
+    EXPECT_EQ(kMbInBytes, size("com.example/cache/tomb/dir/file1"));
+    EXPECT_EQ(kMbInBytes, size("com.example/cache/tomb/dir/file2"));
+    EXPECT_EQ(0, size("com.example/cache/tomb/atomic/file1"));
+    EXPECT_EQ(0, size("com.example/cache/tomb/atomic/file2"));
+    EXPECT_EQ(0, size("com.example/cache/tomb/atomic/dir/file1"));
+    EXPECT_EQ(0, size("com.example/cache/tomb/atomic/dir/file2"));
+
+    service->freeCache(testUuid, free() + kKbInBytes,
+            FLAG_FREE_CACHE_V2 | FLAG_FREE_CACHE_V2_DEFY_QUOTA);
+
+    EXPECT_EQ(-1, size("com.example/cache/atomic/file1"));
+    EXPECT_EQ(-1, size("com.example/cache/atomic/file2"));
+    EXPECT_EQ(-1, size("com.example/cache/atomic/dir/file1"));
+    EXPECT_EQ(-1, size("com.example/cache/atomic/dir/file2"));
+    EXPECT_EQ(0, size("com.example/cache/atomic/tomb/file1"));
+    EXPECT_EQ(0, size("com.example/cache/atomic/tomb/file2"));
+    EXPECT_EQ(0, size("com.example/cache/atomic/tomb/dir/file1"));
+    EXPECT_EQ(0, size("com.example/cache/atomic/tomb/dir/file2"));
+
+    EXPECT_EQ(kMbInBytes, size("com.example/cache/tomb/file1"));
+    EXPECT_EQ(kMbInBytes, size("com.example/cache/tomb/file2"));
+    EXPECT_EQ(kMbInBytes, size("com.example/cache/tomb/dir/file1"));
+    EXPECT_EQ(kMbInBytes, size("com.example/cache/tomb/dir/file2"));
+    EXPECT_EQ(0, size("com.example/cache/tomb/atomic/file1"));
+    EXPECT_EQ(0, size("com.example/cache/tomb/atomic/file2"));
+    EXPECT_EQ(0, size("com.example/cache/tomb/atomic/dir/file1"));
+    EXPECT_EQ(0, size("com.example/cache/tomb/atomic/dir/file2"));
+
+    service->freeCache(testUuid, kTbInBytes,
+            FLAG_FREE_CACHE_V2 | FLAG_FREE_CACHE_V2_DEFY_QUOTA);
+
+    EXPECT_EQ(-1, size("com.example/cache/atomic/file1"));
+    EXPECT_EQ(-1, size("com.example/cache/atomic/file2"));
+    EXPECT_EQ(-1, size("com.example/cache/atomic/dir/file1"));
+    EXPECT_EQ(-1, size("com.example/cache/atomic/dir/file2"));
+    EXPECT_EQ(0, size("com.example/cache/atomic/tomb/file1"));
+    EXPECT_EQ(0, size("com.example/cache/atomic/tomb/file2"));
+    EXPECT_EQ(0, size("com.example/cache/atomic/tomb/dir/file1"));
+    EXPECT_EQ(0, size("com.example/cache/atomic/tomb/dir/file2"));
+
+    EXPECT_EQ(0, size("com.example/cache/tomb/file1"));
+    EXPECT_EQ(0, size("com.example/cache/tomb/file2"));
+    EXPECT_EQ(0, size("com.example/cache/tomb/dir/file1"));
+    EXPECT_EQ(0, size("com.example/cache/tomb/dir/file2"));
+    EXPECT_EQ(0, size("com.example/cache/tomb/atomic/file1"));
+    EXPECT_EQ(0, size("com.example/cache/tomb/atomic/file2"));
+    EXPECT_EQ(0, size("com.example/cache/tomb/atomic/dir/file1"));
+    EXPECT_EQ(0, size("com.example/cache/tomb/atomic/dir/file2"));
+}
+
+}  // namespace installd
+}  // namespace android
diff --git a/cmds/installd/tests/installd_utils_test.cpp b/cmds/installd/tests/installd_utils_test.cpp
index 947cc0d..4b68574 100644
--- a/cmds/installd/tests/installd_utils_test.cpp
+++ b/cmds/installd/tests/installd_utils_test.cpp
@@ -29,6 +29,7 @@
 #define TEST_DATA_DIR "/data/"
 #define TEST_APP_DIR "/data/app/"
 #define TEST_APP_PRIVATE_DIR "/data/app-private/"
+#define TEST_APP_EPHEMERAL_DIR "/data/app-ephemeral/"
 #define TEST_ASEC_DIR "/mnt/asec/"
 #define TEST_EXPAND_DIR "/mnt/expand/"
 
@@ -57,6 +58,9 @@
         android_app_private_dir.path = (char*) TEST_APP_PRIVATE_DIR;
         android_app_private_dir.len = strlen(TEST_APP_PRIVATE_DIR);
 
+        android_app_ephemeral_dir.path = (char*) TEST_APP_EPHEMERAL_DIR;
+        android_app_ephemeral_dir.len = strlen(TEST_APP_EPHEMERAL_DIR);
+
         android_data_dir.path = (char*) TEST_DATA_DIR;
         android_data_dir.len = strlen(TEST_DATA_DIR);
 
@@ -85,19 +89,19 @@
     // Bad prefixes directories
     const char *badprefix1 = "/etc/passwd";
     EXPECT_EQ(-1, validate_apk_path(badprefix1))
-            << badprefix1 << " should be allowed as a valid path";
+            << badprefix1 << " should not be allowed as a valid path";
 
     const char *badprefix2 = "../.." TEST_APP_DIR "../../../blah";
     EXPECT_EQ(-1, validate_apk_path(badprefix2))
-            << badprefix2 << " should be allowed as a valid path";
+            << badprefix2 << " should not be allowed as a valid path";
 
     const char *badprefix3 = "init.rc";
     EXPECT_EQ(-1, validate_apk_path(badprefix3))
-            << badprefix3 << " should be allowed as a valid path";
+            << badprefix3 << " should not be allowed as a valid path";
 
     const char *badprefix4 = "/init.rc";
     EXPECT_EQ(-1, validate_apk_path(badprefix4))
-            << badprefix4 << " should be allowed as a valid path";
+            << badprefix4 << " should not be allowed as a valid path";
 }
 
 TEST_F(UtilsTest, IsValidApkPath_Internal) {