diff --git a/cmds/installd/CacheItem.cpp b/cmds/installd/CacheItem.cpp
index d1bdded..6caf149 100644
--- a/cmds/installd/CacheItem.cpp
+++ b/cmds/installd/CacheItem.cpp
@@ -16,8 +16,9 @@
 
 #include "CacheItem.h"
 
-#include <stdint.h>
 #include <inttypes.h>
+#include <stdint.h>
+#include <sys/xattr.h>
 
 #include <android-base/logging.h>
 #include <android-base/stringprintf.h>
@@ -29,12 +30,23 @@
 namespace android {
 namespace installd {
 
-CacheItem::CacheItem(const std::shared_ptr<CacheItem>& parent, FTSENT* p) : mParent(parent) {
+CacheItem::CacheItem(FTSENT* p) {
     level = p->fts_level;
     directory = S_ISDIR(p->fts_statp->st_mode);
     size = p->fts_statp->st_blocks * 512;
     modified = p->fts_statp->st_mtime;
-    mName = p->fts_path;
+
+    mParent = static_cast<CacheItem*>(p->fts_parent->fts_pointer);
+    if (mParent) {
+        atomic = mParent->atomic;
+        tombstone = mParent->tombstone;
+        mName = p->fts_name;
+        mName.insert(0, "/");
+    } else {
+        atomic = false;
+        tombstone = false;
+        mName = p->fts_path;
+    }
 }
 
 CacheItem::~CacheItem() {
@@ -46,7 +58,7 @@
 
 std::string CacheItem::buildPath() {
     std::string res = mName;
-    std::shared_ptr<CacheItem> parent = mParent;
+    CacheItem* parent = mParent;
     while (parent) {
         res.insert(0, parent->mName);
         parent = parent->mParent;
@@ -57,13 +69,47 @@
 int CacheItem::purge() {
     auto path = buildPath();
     if (directory) {
-        return delete_dir_contents_and_dir(path, true);
-    } else {
-        int res = unlink(path.c_str());
-        if (res != 0) {
-            PLOG(WARNING) << "Failed to unlink " << path;
+        FTS *fts;
+        FTSENT *p;
+        char *argv[] = { (char*) path.c_str(), nullptr };
+        if (!(fts = fts_open(argv, FTS_PHYSICAL | FTS_XDEV, NULL))) {
+            PLOG(WARNING) << "Failed to fts_open " << path;
+            return -1;
         }
-        return res;
+        while ((p = fts_read(fts)) != nullptr) {
+            switch (p->fts_info) {
+            case FTS_D:
+                if (p->fts_level == 0) {
+                    p->fts_number = tombstone;
+                } else {
+                    p->fts_number = p->fts_parent->fts_number
+                            | (getxattr(p->fts_path, kXattrCacheTombstone, nullptr, 0) >= 0);
+                }
+                break;
+            case FTS_F:
+                if (p->fts_parent->fts_number) {
+                    truncate(p->fts_path, 0);
+                } else {
+                    unlink(p->fts_path);
+                }
+                break;
+            case FTS_DEFAULT:
+            case FTS_SL:
+            case FTS_SLNONE:
+                unlink(p->fts_path);
+                break;
+            case FTS_DP:
+                rmdir(p->fts_path);
+                break;
+            }
+        }
+        return 0;
+    } else {
+        if (tombstone) {
+            return truncate(path.c_str(), 0);
+        } else {
+            return unlink(path.c_str());
+        }
     }
 }
 
diff --git a/cmds/installd/CacheItem.h b/cmds/installd/CacheItem.h
index bec8bc8..afbb15d 100644
--- a/cmds/installd/CacheItem.h
+++ b/cmds/installd/CacheItem.h
@@ -36,7 +36,7 @@
  */
 class CacheItem {
 public:
-    CacheItem(const std::shared_ptr<CacheItem>& parent, FTSENT* p);
+    CacheItem(FTSENT* p);
     ~CacheItem();
 
     std::string toString();
@@ -46,11 +46,13 @@
 
     short level;
     bool directory;
+    bool atomic;
+    bool tombstone;
     int64_t size;
     time_t modified;
 
 private:
-    std::shared_ptr<CacheItem> mParent;
+    CacheItem* mParent;
     std::string mName;
 
     DISALLOW_COPY_AND_ASSIGN(CacheItem);
diff --git a/cmds/installd/CacheTracker.cpp b/cmds/installd/CacheTracker.cpp
index 23c4330..9377836 100644
--- a/cmds/installd/CacheTracker.cpp
+++ b/cmds/installd/CacheTracker.cpp
@@ -20,6 +20,7 @@
 
 #include <fts.h>
 #include <sys/quota.h>
+#include <sys/xattr.h>
 #include <utils/Trace.h>
 
 #include <android-base/logging.h>
@@ -86,30 +87,59 @@
         PLOG(WARNING) << "Failed to fts_open " << path;
         return;
     }
-    // TODO: add support for "user.atomic" and "user.tombstone" xattrs
-    while ((p = fts_read(fts)) != NULL) {
+    while ((p = fts_read(fts)) != nullptr) {
+        if (p->fts_level == 0) continue;
+
+        // Create tracking nodes for everything we encounter
         switch (p->fts_info) {
         case FTS_D:
-            // Track the newest mtime of anything inside so we consider
-            // deleting the directory last
-            p->fts_number = p->fts_statp->st_mtime;
-            break;
-        case FTS_DP:
-            p->fts_statp->st_mtime = p->fts_number;
-
-            // Ignore the actual top-level cache directories
-            if (p->fts_level == 0) break;
         case FTS_DEFAULT:
         case FTS_F:
         case FTS_SL:
-        case FTS_SLNONE:
-            // TODO: optimize path memory footprint
-            items.push_back(std::shared_ptr<CacheItem>(new CacheItem(nullptr, p)));
+        case FTS_SLNONE: {
+            auto item = std::shared_ptr<CacheItem>(new CacheItem(p));
+            p->fts_pointer = static_cast<void*>(item.get());
+            items.push_back(item);
+        }
+        }
 
-            // Track the newest modified item under this tree
-            p->fts_parent->fts_number =
-                    std::max(p->fts_parent->fts_number, p->fts_statp->st_mtime);
-            break;
+        switch (p->fts_info) {
+        case FTS_D: {
+            auto item = static_cast<CacheItem*>(p->fts_pointer);
+            item->atomic |= (getxattr(p->fts_path, kXattrCacheAtomic, nullptr, 0) >= 0);
+            item->tombstone |= (getxattr(p->fts_path, kXattrCacheTombstone, nullptr, 0) >= 0);
+
+            // When atomic, immediately collect all files under tree
+            if (item->atomic) {
+                while ((p = fts_read(fts)) != nullptr) {
+                    if (p->fts_info == FTS_DP && p->fts_level == item->level) break;
+                    switch (p->fts_info) {
+                    case FTS_D:
+                    case FTS_DEFAULT:
+                    case FTS_F:
+                    case FTS_SL:
+                    case FTS_SLNONE:
+                        item->size += p->fts_statp->st_blocks * 512;
+                        item->modified = std::max(item->modified, p->fts_statp->st_mtime);
+                    }
+                }
+            }
+        }
+        }
+
+        // Bubble up modified time to parent
+        switch (p->fts_info) {
+        case FTS_DP:
+        case FTS_DEFAULT:
+        case FTS_F:
+        case FTS_SL:
+        case FTS_SLNONE: {
+            auto item = static_cast<CacheItem*>(p->fts_pointer);
+            auto parent = static_cast<CacheItem*>(p->fts_parent->fts_pointer);
+            if (parent) {
+                parent->modified = std::max(parent->modified, item->modified);
+            }
+        }
         }
     }
     fts_close(fts);
@@ -137,7 +167,7 @@
         }
         return left->directory;
     };
-    std::sort(items.begin(), items.end(), cmp);
+    std::stable_sort(items.begin(), items.end(), cmp);
     ATRACE_END();
 }
 
diff --git a/cmds/installd/InstalldNativeService.cpp b/cmds/installd/InstalldNativeService.cpp
index aa10666..a84b051 100644
--- a/cmds/installd/InstalldNativeService.cpp
+++ b/cmds/installd/InstalldNativeService.cpp
@@ -86,7 +86,8 @@
 static constexpr int FLAG_CLEAR_CODE_CACHE_ONLY = 1 << 9;
 static constexpr int FLAG_USE_QUOTA = 1 << 12;
 static constexpr int FLAG_FREE_CACHE_V2 = 1 << 13;
-static constexpr int FLAG_FREE_CACHE_NOOP = 1 << 14;
+static constexpr int FLAG_FREE_CACHE_V2_DEFY_QUOTA = 1 << 14;
+static constexpr int FLAG_FREE_CACHE_NOOP = 1 << 15;
 
 namespace {
 
@@ -833,6 +834,14 @@
         ATRACE_BEGIN("bounce");
         std::shared_ptr<CacheTracker> active;
         while (active || !queue.empty()) {
+            // Only look at apps under quota when explicitly requested
+            if (active && (active->getCacheRatio() < 10000)
+                    && !(flags & FLAG_FREE_CACHE_V2_DEFY_QUOTA)) {
+                LOG(DEBUG) << "Active ratio " << active->getCacheRatio()
+                        << " isn't over quota, and defy not requested";
+                break;
+            }
+
             // Find the best tracker to work with; this might involve swapping
             // if the active tracker is no longer the most over quota
             bool nextBetter = active && !queue.empty()
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) {
diff --git a/cmds/installd/utils.cpp b/cmds/installd/utils.cpp
index 37215ea..6d50f55 100644
--- a/cmds/installd/utils.cpp
+++ b/cmds/installd/utils.cpp
@@ -33,6 +33,7 @@
 #include <android-base/logging.h>
 #include <android-base/stringprintf.h>
 #include <cutils/fs.h>
+#include <cutils/properties.h>
 #include <log/log.h>
 #include <private/android_filesystem_config.h>
 
@@ -155,6 +156,9 @@
 std::string create_data_path(const char* volume_uuid) {
     if (volume_uuid == nullptr) {
         return "/data";
+    } else if (!strcmp(volume_uuid, "TEST")) {
+        CHECK(property_get_bool("ro.debuggable", false));
+        return "/data/local/tmp";
     } else {
         CHECK(is_valid_filename(volume_uuid));
         return StringPrintf("/mnt/expand/%s", volume_uuid);
diff --git a/cmds/installd/utils.h b/cmds/installd/utils.h
index 5226d1c..aa83dc2 100644
--- a/cmds/installd/utils.h
+++ b/cmds/installd/utils.h
@@ -66,6 +66,8 @@
 
 constexpr const char* kXattrInodeCache = "user.inode_cache";
 constexpr const char* kXattrInodeCodeCache = "user.inode_code_cache";
+constexpr const char* kXattrCacheAtomic = "user.cache_atomic";
+constexpr const char* kXattrCacheTombstone = "user.cache_tombstone";
 
 int create_pkg_path(char path[PKG_PATH_MAX],
                     const char *pkgname,