Logic for atmoic/tombstone behavior; split mode.

Flesh out logic for cache directories that request new atomic and/or
tombstone clearing behaviors.  Atomic directories are considered for
deletion as a single all-or-nothing unit, and tombstone directories
truncate any removed files instead of unlinking them.

Since these behaviors can be mixed together, add local tests that
quickly verify several different permutations.

Reduce memory footprint of CacheItem objects by only storing name
and pointer to parent (instead of full path).  Fix ordering bug by
switching to std::stable_sort.

Add "V2_DEFY_QUOTA" flag so we can split clearing into two distinct
phases: clearing data for apps above their quotas, and then pushing
deeper by clearing data for apps below their quotas.

Test: adb shell /data/nativetest64/installd_cache_test/installd_cache_test
Bug: 34692014, 33811826
Change-Id: I156897de1d1d1c371b2b837128b2e286bf33d40d
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) {