diff --git a/cmds/installd/commands.c b/cmds/installd/commands.c
index 1bb4935..f5f6f3b 100644
--- a/cmds/installd/commands.c
+++ b/cmds/installd/commands.c
@@ -26,6 +26,7 @@
 dir_rec_t android_asec_dir;
 dir_rec_t android_app_dir;
 dir_rec_t android_app_private_dir;
+dir_rec_t android_media_dir;
 dir_rec_array_t android_system_dirs;
 
 int install(const char *pkgname, uid_t uid, gid_t gid)
@@ -273,17 +274,6 @@
     return delete_dir_contents(cachedir, 0, 0);
 }
 
-static int64_t disk_free()
-{
-    struct statfs sfs;
-    if (statfs(android_data_dir.path, &sfs) == 0) {
-        return sfs.f_bavail * sfs.f_bsize;
-    } else {
-        ALOGE("Couldn't statfs %s: %s\n", android_data_dir.path, strerror(errno));
-        return -1;
-    }
-}
-
 /* Try to ensure free_size bytes of storage are available.
  * Returns 0 on success.
  * This is rather simple-minded because doing a full LRU would
@@ -293,57 +283,66 @@
  */
 int free_cache(int64_t free_size)
 {
-    const char *name;
-    int dfd, subfd;
+    cache_t* cache;
+    int64_t avail;
     DIR *d;
     struct dirent *de;
-    int64_t avail;
-    char datadir[PKG_PATH_MAX];
+    char tmpdir[PATH_MAX];
+    char *dirpos;
 
-    avail = disk_free();
+    avail = data_disk_free();
     if (avail < 0) return -1;
 
     ALOGI("free_cache(%" PRId64 ") avail %" PRId64 "\n", free_size, avail);
     if (avail >= free_size) return 0;
 
-    if (create_persona_path(datadir, 0)) {
-        ALOGE("couldn't get directory for persona 0");
-        return -1;
+    cache = start_cache_collection();
+
+    // Collect cache files for primary user.
+    if (create_persona_path(tmpdir, 0) == 0) {
+        //ALOGI("adding cache files from %s\n", tmpdir);
+        add_cache_files(cache, tmpdir, "cache");
     }
 
-    d = opendir(datadir);
-    if (d == NULL) {
-        ALOGE("cannot open %s: %s\n", datadir, strerror(errno));
-        return -1;
-    }
-    dfd = dirfd(d);
-
-    while ((de = readdir(d))) {
-        if (de->d_type != DT_DIR) continue;
-        name = de->d_name;
-
-        /* always skip "." and ".." */
-        if (name[0] == '.') {
-            if (name[1] == 0) continue;
-            if ((name[1] == '.') && (name[2] == 0)) continue;
+    // Search for other users and add any cache files from them.
+    snprintf(tmpdir, sizeof(tmpdir), "%s%s", android_data_dir.path,
+            SECONDARY_USER_PREFIX);
+    dirpos = tmpdir + strlen(tmpdir);
+    d = opendir(tmpdir);
+    if (d != NULL) {
+        while ((de = readdir(d))) {
+            if (de->d_type == DT_DIR) {
+                const char *name = de->d_name;
+                    /* always skip "." and ".." */
+                if (name[0] == '.') {
+                    if (name[1] == 0) continue;
+                    if ((name[1] == '.') && (name[2] == 0)) continue;
+                }
+                if ((strlen(name)+(dirpos-tmpdir)) < (sizeof(tmpdir)-1)) {
+                    strcpy(dirpos, name);
+                    //ALOGI("adding cache files from %s\n", tmpdir);
+                    add_cache_files(cache, tmpdir, "cache");
+                } else {
+                    ALOGW("Path exceeds limit: %s%s", tmpdir, name);
+                }
+            }
         }
-
-        subfd = openat(dfd, name, O_RDONLY | O_DIRECTORY);
-        if (subfd < 0) continue;
-
-        delete_dir_contents_fd(subfd, "cache");
-        close(subfd);
-
-        avail = disk_free();
-        if (avail >= free_size) {
-            closedir(d);
-            return 0;
-        }
+        closedir(d);
     }
-    closedir(d);
 
-    /* Fail case - not possible to free space */
-    return -1;
+    // Collect cache files on external storage (if it is mounted as part
+    // of the internal storage).
+    strcpy(tmpdir, android_media_dir.path);
+    if (lookup_media_dir(tmpdir, "Android") == 0
+            && lookup_media_dir(tmpdir, "data") == 0) {
+        //ALOGI("adding cache files from %s\n", tmpdir);
+        add_cache_files(cache, tmpdir, "cache");
+    }
+
+    clear_cache_files(cache, free_size);
+    finish_cache_collection(cache);
+
+    return data_disk_free() >= free_size ? 0 : -1;
 }
 
 int move_dex(const char *src, const char *dst)
diff --git a/cmds/installd/installd.c b/cmds/installd/installd.c
index fa4b8a6..89c059e 100644
--- a/cmds/installd/installd.c
+++ b/cmds/installd/installd.c
@@ -297,6 +297,11 @@
         return -1;
     }
 
+    // Get the android media directory.
+    if (copy_and_append(&android_media_dir, &android_data_dir, MEDIA_SUBDIR) < 0) {
+        return -1;
+    }
+
     // Take note of the system and vendor directories.
     android_system_dirs.count = 2;
 
diff --git a/cmds/installd/installd.h b/cmds/installd/installd.h
index 1b843fd..f5853ff 100644
--- a/cmds/installd/installd.h
+++ b/cmds/installd/installd.h
@@ -60,6 +60,8 @@
 
 #define APP_SUBDIR             "app/" // sub-directory under ANDROID_DATA
 
+#define MEDIA_SUBDIR           "media/" // sub-directory under ANDROID_DATA
+
 /* other handy constants */
 
 #define PRIVATE_APP_SUBDIR     "app-private/" // sub-directory under ANDROID_DATA
@@ -91,8 +93,36 @@
 extern dir_rec_t android_app_private_dir;
 extern dir_rec_t android_data_dir;
 extern dir_rec_t android_asec_dir;
+extern dir_rec_t android_media_dir;
 extern dir_rec_array_t android_system_dirs;
 
+typedef struct cache_dir_struct {
+    struct cache_dir_struct* parent;
+    int32_t childCount;
+    int32_t hiddenCount;
+    int32_t deleted;
+    char name[];
+} cache_dir_t;
+
+typedef struct {
+    cache_dir_t* dir;
+    time_t modTime;
+    char name[];
+} cache_file_t;
+
+typedef struct {
+    size_t numDirs;
+    size_t availDirs;
+    cache_dir_t** dirs;
+    size_t numFiles;
+    size_t availFiles;
+    cache_file_t** files;
+    size_t numCollected;
+    void* memBlocks;
+    int8_t* curMemBlockAvail;
+    int8_t* curMemBlockEnd;
+} cache_t;
+
 /* util.c */
 
 int create_pkg_path_in_dir(char path[PKG_PATH_MAX],
@@ -123,6 +153,18 @@
 
 int delete_dir_contents_fd(int dfd, const char *name);
 
+int lookup_media_dir(char basepath[PATH_MAX], const char *dir);
+
+int64_t data_disk_free();
+
+cache_t* start_cache_collection();
+
+void add_cache_files(cache_t* cache, const char *basepath, const char *cachedir);
+
+void clear_cache_files(cache_t* cache, int64_t free_size);
+
+void finish_cache_collection(cache_t* cache);
+
 int validate_system_app_path(const char* path);
 
 int get_path_from_env(dir_rec_t* rec, const char* var);
diff --git a/cmds/installd/utils.c b/cmds/installd/utils.c
index 52ec9e8..79db972 100644
--- a/cmds/installd/utils.c
+++ b/cmds/installd/utils.c
@@ -16,6 +16,8 @@
 
 #include "installd.h"
 
+#define CACHE_NOISY(x) //x
+
 int create_pkg_path_in_dir(char path[PKG_PATH_MAX],
                                 const dir_rec_t* dir,
                                 const char* pkgname,
@@ -296,6 +298,489 @@
     return res;
 }
 
+int lookup_media_dir(char basepath[PATH_MAX], const char *dir)
+{
+    DIR *d;
+    struct dirent *de;
+    struct stat s;
+    char* dirpos = basepath + strlen(basepath);
+
+    if ((*(dirpos-1)) != '/') {
+        *dirpos = '/';
+        dirpos++;
+    }
+
+    CACHE_NOISY(ALOGI("Looking up %s in %s\n", dir, basepath));
+    // Verify the path won't extend beyond our buffer, to avoid
+    // repeated checking later.
+    if ((dirpos-basepath+strlen(dir)) >= (PATH_MAX-1)) {
+        ALOGW("Path exceeds limit: %s%s", basepath, dir);
+        return -1;
+    }
+
+    // First, can we find this directory with the case that is given?
+    strcpy(dirpos, dir);
+    if (stat(basepath, &s) >= 0) {
+        CACHE_NOISY(ALOGI("Found direct: %s\n", basepath));
+        return 0;
+    }
+
+    // Not found with that case...  search through all entries to find
+    // one that matches regardless of case.
+    *dirpos = 0;
+
+    d = opendir(basepath);
+    if (d == NULL) {
+        return -1;
+    }
+
+    while ((de = readdir(d))) {
+        if (strcasecmp(de->d_name, dir) == 0) {
+            strcpy(dirpos, de->d_name);
+            closedir(d);
+            CACHE_NOISY(ALOGI("Found search: %s\n", basepath));
+            return 0;
+        }
+    }
+
+    ALOGW("Couldn't find %s in %s", dir, basepath);
+    closedir(d);
+    return -1;
+}
+
+int64_t data_disk_free()
+{
+    struct statfs sfs;
+    if (statfs(android_data_dir.path, &sfs) == 0) {
+        return sfs.f_bavail * sfs.f_bsize;
+    } else {
+        ALOGE("Couldn't statfs %s: %s\n", android_data_dir.path, strerror(errno));
+        return -1;
+    }
+}
+
+cache_t* start_cache_collection()
+{
+    cache_t* cache = (cache_t*)calloc(1, sizeof(cache_t));
+    return cache;
+}
+
+#define CACHE_BLOCK_SIZE (512*1024)
+
+static void* _cache_malloc(cache_t* cache, size_t len)
+{
+    len = (len+3)&~3;
+    if (len > (CACHE_BLOCK_SIZE/2)) {
+        // It doesn't make sense to try to put this allocation into one
+        // of our blocks, because it is so big.  Instead, make a new dedicated
+        // block for it.
+        int8_t* res = (int8_t*)malloc(len+sizeof(void*));
+        if (res == NULL) {
+            return NULL;
+        }
+        CACHE_NOISY(ALOGI("Allocated large cache mem block: %p size %d", res, len));
+        // Link it into our list of blocks, not disrupting the current one.
+        if (cache->memBlocks == NULL) {
+            *(void**)res = NULL;
+            cache->memBlocks = res;
+        } else {
+            *(void**)res = *(void**)cache->memBlocks;
+            *(void**)cache->memBlocks = res;
+        }
+        return res + sizeof(void*);
+    }
+    int8_t* res = cache->curMemBlockAvail;
+    int8_t* nextPos = res + len;
+    if (cache->memBlocks == NULL || nextPos > cache->curMemBlockEnd) {
+        int8_t* newBlock = malloc(CACHE_BLOCK_SIZE);
+        if (newBlock == NULL) {
+            return NULL;
+        }
+        CACHE_NOISY(ALOGI("Allocated new cache mem block: %p", newBlock));
+        *(void**)newBlock = cache->memBlocks;
+        cache->memBlocks = newBlock;
+        res = cache->curMemBlockAvail = newBlock + sizeof(void*);
+        cache->curMemBlockEnd = newBlock + CACHE_BLOCK_SIZE;
+        nextPos = res + len;
+    }
+    CACHE_NOISY(ALOGI("cache_malloc: ret %p size %d, block=%p, nextPos=%p",
+            res, len, cache->memBlocks, nextPos));
+    cache->curMemBlockAvail = nextPos;
+    return res;
+}
+
+static void* _cache_realloc(cache_t* cache, void* cur, size_t origLen, size_t len)
+{
+    // This isn't really a realloc, but it is good enough for our purposes here.
+    void* alloc = _cache_malloc(cache, len);
+    if (alloc != NULL && cur != NULL) {
+        memcpy(alloc, cur, origLen < len ? origLen : len);
+    }
+    return alloc;
+}
+
+static void _inc_num_cache_collected(cache_t* cache)
+{
+    cache->numCollected++;
+    if ((cache->numCollected%20000) == 0) {
+        ALOGI("Collected cache so far: %d directories, %d files",
+            cache->numDirs, cache->numFiles);
+    }
+}
+
+static cache_dir_t* _add_cache_dir_t(cache_t* cache, cache_dir_t* parent, const char *name)
+{
+    size_t nameLen = strlen(name);
+    cache_dir_t* dir = (cache_dir_t*)_cache_malloc(cache, sizeof(cache_dir_t)+nameLen+1);
+    if (dir != NULL) {
+        dir->parent = parent;
+        dir->childCount = 0;
+        dir->hiddenCount = 0;
+        dir->deleted = 0;
+        strcpy(dir->name, name);
+        if (cache->numDirs >= cache->availDirs) {
+            size_t newAvail = cache->availDirs < 1000 ? 1000 : cache->availDirs*2;
+            cache_dir_t** newDirs = (cache_dir_t**)_cache_realloc(cache, cache->dirs,
+                    cache->availDirs*sizeof(cache_dir_t*), newAvail*sizeof(cache_dir_t*));
+            if (newDirs == NULL) {
+                ALOGE("Failure growing cache dirs array for %s\n", name);
+                return NULL;
+            }
+            cache->availDirs = newAvail;
+            cache->dirs = newDirs;
+        }
+        cache->dirs[cache->numDirs] = dir;
+        cache->numDirs++;
+        if (parent != NULL) {
+            parent->childCount++;
+        }
+        _inc_num_cache_collected(cache);
+    } else {
+        ALOGE("Failure allocating cache_dir_t for %s\n", name);
+    }
+    return dir;
+}
+
+static cache_file_t* _add_cache_file_t(cache_t* cache, cache_dir_t* dir, time_t modTime,
+        const char *name)
+{
+    size_t nameLen = strlen(name);
+    cache_file_t* file = (cache_file_t*)_cache_malloc(cache, sizeof(cache_file_t)+nameLen+1);
+    if (file != NULL) {
+        file->dir = dir;
+        file->modTime = modTime;
+        strcpy(file->name, name);
+        if (cache->numFiles >= cache->availFiles) {
+            size_t newAvail = cache->availFiles < 1000 ? 1000 : cache->availFiles*2;
+            cache_file_t** newFiles = (cache_file_t**)_cache_realloc(cache, cache->files,
+                    cache->availFiles*sizeof(cache_file_t*), newAvail*sizeof(cache_file_t*));
+            if (newFiles == NULL) {
+                ALOGE("Failure growing cache file array for %s\n", name);
+                return NULL;
+            }
+            cache->availFiles = newAvail;
+            cache->files = newFiles;
+        }
+        CACHE_NOISY(ALOGI("Setting file %p at position %d in array %p", file,
+                cache->numFiles, cache->files));
+        cache->files[cache->numFiles] = file;
+        cache->numFiles++;
+        dir->childCount++;
+        _inc_num_cache_collected(cache);
+    } else {
+        ALOGE("Failure allocating cache_file_t for %s\n", name);
+    }
+    return file;
+}
+
+static int _add_cache_files(cache_t *cache, cache_dir_t *parentDir, const char *dirName,
+        DIR* dir, char *pathBase, char *pathPos, size_t pathAvailLen)
+{
+    struct dirent *de;
+    cache_dir_t* cacheDir = NULL;
+    int dfd;
+
+    CACHE_NOISY(ALOGI("_add_cache_files: parent=%p dirName=%s dir=%p pathBase=%s",
+            parentDir, dirName, dir, pathBase));
+
+    dfd = dirfd(dir);
+
+    if (dfd < 0) return 0;
+
+    // Sub-directories always get added to the data structure, so if they
+    // are empty we will know about them to delete them later.
+    cacheDir = _add_cache_dir_t(cache, parentDir, dirName);
+
+    while ((de = readdir(dir))) {
+        const char *name = de->d_name;
+
+        if (de->d_type == DT_DIR) {
+            int subfd;
+            DIR *subdir;
+
+                /* always skip "." and ".." */
+            if (name[0] == '.') {
+                if (name[1] == 0) continue;
+                if ((name[1] == '.') && (name[2] == 0)) continue;
+            }
+
+            subfd = openat(dfd, name, O_RDONLY | O_DIRECTORY);
+            if (subfd < 0) {
+                ALOGE("Couldn't openat %s: %s\n", name, strerror(errno));
+                continue;
+            }
+            subdir = fdopendir(subfd);
+            if (subdir == NULL) {
+                ALOGE("Couldn't fdopendir %s: %s\n", name, strerror(errno));
+                close(subfd);
+                continue;
+            }
+            if (cacheDir == NULL) {
+                cacheDir = _add_cache_dir_t(cache, parentDir, dirName);
+            }
+            if (cacheDir != NULL) {
+                // Update pathBase for the new path...  this may change dirName
+                // if that is also pointing to the path, but we are done with it
+                // now.
+                size_t finallen = snprintf(pathPos, pathAvailLen, "/%s", name);
+                CACHE_NOISY(ALOGI("Collecting dir %s\n", pathBase));
+                if (finallen < pathAvailLen) {
+                    _add_cache_files(cache, cacheDir, name, subdir, pathBase,
+                            pathPos+finallen, pathAvailLen-finallen);
+                } else {
+                    // Whoops, the final path is too long!  We'll just delete
+                    // this directory.
+                    ALOGW("Cache dir %s truncated in path %s; deleting dir\n",
+                            name, pathBase);
+                    _delete_dir_contents(subdir, NULL);
+                    if (unlinkat(dfd, name, AT_REMOVEDIR) < 0) {
+                        ALOGE("Couldn't unlinkat %s: %s\n", name, strerror(errno));
+                    }
+                }
+            }
+            closedir(subdir);
+        } else if (de->d_type == DT_REG) {
+            // Skip files that start with '.'; they will be deleted if
+            // their entire directory is deleted.  This allows for metadata
+            // like ".nomedia" to remain in the directory until the entire
+            // directory is deleted.
+            if (cacheDir == NULL) {
+                cacheDir = _add_cache_dir_t(cache, parentDir, dirName);
+            }
+            if (name[0] == '.') {
+                cacheDir->hiddenCount++;
+                continue;
+            }
+            if (cacheDir != NULL) {
+                // Build final full path for file...  this may change dirName
+                // if that is also pointing to the path, but we are done with it
+                // now.
+                size_t finallen = snprintf(pathPos, pathAvailLen, "/%s", name);
+                CACHE_NOISY(ALOGI("Collecting file %s\n", pathBase));
+                if (finallen < pathAvailLen) {
+                    struct stat s;
+                    if (stat(pathBase, &s) >= 0) {
+                        _add_cache_file_t(cache, cacheDir, s.st_mtime, name);
+                    } else {
+                        ALOGW("Unable to stat cache file %s; deleting\n", pathBase);
+                        if (unlink(pathBase) < 0) {
+                            ALOGE("Couldn't unlink %s: %s\n", pathBase, strerror(errno));
+                        }
+                    }
+                } else {
+                    // Whoops, the final path is too long!  We'll just delete
+                    // this file.
+                    ALOGW("Cache file %s truncated in path %s; deleting\n",
+                            name, pathBase);
+                    if (unlinkat(dfd, name, 0) < 0) {
+                        *pathPos = 0;
+                        ALOGE("Couldn't unlinkat %s in %s: %s\n", name, pathBase,
+                                strerror(errno));
+                    }
+                }
+            }
+        } else {
+            cacheDir->hiddenCount++;
+        }
+    }
+    return 0;
+}
+
+void add_cache_files(cache_t* cache, const char *basepath, const char *cachedir)
+{
+    DIR *d;
+    struct dirent *de;
+    char dirname[PATH_MAX];
+
+    CACHE_NOISY(ALOGI("add_cache_files: base=%s cachedir=%s\n", basepath, cachedir));
+
+    d = opendir(basepath);
+    if (d == NULL) {
+        return;
+    }
+
+    while ((de = readdir(d))) {
+        if (de->d_type == DT_DIR) {
+            DIR* subdir;
+            const char *name = de->d_name;
+            char* pathpos;
+
+                /* always skip "." and ".." */
+            if (name[0] == '.') {
+                if (name[1] == 0) continue;
+                if ((name[1] == '.') && (name[2] == 0)) continue;
+            }
+
+            strcpy(dirname, basepath);
+            pathpos = dirname + strlen(dirname);
+            if ((*(pathpos-1)) != '/') {
+                *pathpos = '/';
+                pathpos++;
+                *pathpos = 0;
+            }
+            if (cachedir != NULL) {
+                snprintf(pathpos, sizeof(dirname)-(pathpos-dirname), "%s/%s", name, cachedir);
+            } else {
+                snprintf(pathpos, sizeof(dirname)-(pathpos-dirname), "%s", name);
+            }
+            CACHE_NOISY(ALOGI("Adding cache files from dir: %s\n", dirname));
+            subdir = opendir(dirname);
+            if (subdir != NULL) {
+                size_t dirnameLen = strlen(dirname);
+                _add_cache_files(cache, NULL, dirname, subdir, dirname, dirname+dirnameLen,
+                        PATH_MAX - dirnameLen);
+                closedir(subdir);
+            }
+        }
+    }
+
+    closedir(d);
+}
+
+static char *create_dir_path(char path[PATH_MAX], cache_dir_t* dir)
+{
+    char *pos = path;
+    if (dir->parent != NULL) {
+        pos = create_dir_path(path, dir->parent);
+    }
+    // Note that we don't need to worry about going beyond the buffer,
+    // since when we were constructing the cache entries our maximum
+    // buffer size for full paths was PATH_MAX.
+    strcpy(pos, dir->name);
+    pos += strlen(pos);
+    *pos = '/';
+    pos++;
+    *pos = 0;
+    return pos;
+}
+
+static void delete_cache_dir(char path[PATH_MAX], cache_dir_t* dir)
+{
+    if (dir->parent != NULL) {
+        create_dir_path(path, dir);
+        ALOGI("DEL DIR %s\n", path);
+        if (dir->hiddenCount <= 0) {
+            if (rmdir(path)) {
+                ALOGE("Couldn't rmdir %s: %s\n", path, strerror(errno));
+                return;
+            }
+        } else {
+            // The directory contains hidden files so we need to delete
+            // them along with the directory itself.
+            if (delete_dir_contents(path, 1, NULL)) {
+                return;
+            }
+        }
+        dir->parent->childCount--;
+        dir->deleted = 1;
+        if (dir->parent->childCount <= 0) {
+            delete_cache_dir(path, dir->parent);
+        }
+    } else if (dir->hiddenCount > 0) {
+        // This is a root directory, but it has hidden files.  Get rid of
+        // all of those files, but not the directory itself.
+        create_dir_path(path, dir);
+        ALOGI("DEL CONTENTS %s\n", path);
+        delete_dir_contents(path, 0, NULL);
+    }
+}
+
+static int cache_modtime_sort(const void *lhsP, const void *rhsP)
+{
+    const cache_file_t *lhs = *(const cache_file_t**)lhsP;
+    const cache_file_t *rhs = *(const cache_file_t**)rhsP;
+    return lhs->modTime < rhs->modTime ? -1 : (lhs->modTime > rhs->modTime ? 1 : 0);
+}
+
+void clear_cache_files(cache_t* cache, int64_t free_size)
+{
+    size_t i;
+    int skip = 0;
+    char path[PATH_MAX];
+
+    ALOGI("Collected cache files: %d directories, %d files",
+        cache->numDirs, cache->numFiles);
+
+    CACHE_NOISY(ALOGI("Sorting files..."));
+    qsort(cache->files, cache->numFiles, sizeof(cache_file_t*),
+            cache_modtime_sort);
+
+    CACHE_NOISY(ALOGI("Cleaning empty directories..."));
+    for (i=cache->numDirs; i>0; i--) {
+        cache_dir_t* dir = cache->dirs[i-1];
+        if (dir->childCount <= 0 && !dir->deleted) {
+            delete_cache_dir(path, dir);
+        }
+    }
+
+    CACHE_NOISY(ALOGI("Trimming files..."));
+    for (i=0; i<cache->numFiles; i++) {
+        skip++;
+        if (skip > 10) {
+            if (data_disk_free() > free_size) {
+                return;
+            }
+            skip = 0;
+        }
+        cache_file_t* file = cache->files[i];
+        strcpy(create_dir_path(path, file->dir), file->name);
+        ALOGI("DEL (mod %d) %s\n", (int)file->modTime, path);
+        if (unlink(path) < 0) {
+            ALOGE("Couldn't unlink %s: %s\n", path, strerror(errno));
+        }
+        file->dir->childCount--;
+        if (file->dir->childCount <= 0) {
+            delete_cache_dir(path, file->dir);
+        }
+    }
+}
+
+void finish_cache_collection(cache_t* cache)
+{
+    size_t i;
+
+    CACHE_NOISY(ALOGI("clear_cache_files: %d dirs, %d files\n", cache->numDirs, cache->numFiles));
+    CACHE_NOISY(
+        for (i=0; i<cache->numDirs; i++) {
+            cache_dir_t* dir = cache->dirs[i];
+            ALOGI("dir #%d: %p %s parent=%p\n", i, dir, dir->name, dir->parent);
+        })
+    CACHE_NOISY(
+        for (i=0; i<cache->numFiles; i++) {
+            cache_file_t* file = cache->files[i];
+            ALOGI("file #%d: %p %s time=%d dir=%p\n", i, file, file->name,
+                    (int)file->modTime, file->dir);
+        })
+    void* block = cache->memBlocks;
+    while (block != NULL) {
+        void* nextBlock = *(void**)block;
+        CACHE_NOISY(ALOGI("Freeing cache mem block: %p", block));
+        free(block);
+        block = nextBlock;
+    }
+    free(cache);
+}
+
 /**
  * Checks whether a path points to a system app (.apk file). Returns 0
  * if it is a system app or -1 if it is not.
diff --git a/cmds/pm/src/com/android/commands/pm/Pm.java b/cmds/pm/src/com/android/commands/pm/Pm.java
index 88a025e..4cb5270 100644
--- a/cmds/pm/src/com/android/commands/pm/Pm.java
+++ b/cmds/pm/src/com/android/commands/pm/Pm.java
@@ -157,6 +157,11 @@
             return;
         }
 
+        if ("trim-caches".equals(op)) {
+            runTrimCaches();
+            return;
+        }
+
         if ("create-user".equals(op)) {
             runCreateUser();
             return;
@@ -1098,7 +1103,7 @@
         return obs.result;
     }
 
-    class ClearDataObserver extends IPackageDataObserver.Stub {
+    static class ClearDataObserver extends IPackageDataObserver.Stub {
         boolean finished;
         boolean result;
 
@@ -1272,6 +1277,75 @@
         }
     }
 
+    static class ClearCacheObserver extends IPackageDataObserver.Stub {
+        boolean finished;
+        boolean result;
+
+        @Override
+        public void onRemoveCompleted(String packageName, boolean succeeded) throws RemoteException {
+            synchronized (this) {
+                finished = true;
+                result = succeeded;
+                notifyAll();
+            }
+        }
+
+    }
+
+    private void runTrimCaches() {
+        String size = nextArg();
+        if (size == null) {
+            System.err.println("Error: no size specified");
+            showUsage();
+            return;
+        }
+        int len = size.length();
+        long multiplier = 1;
+        if (len > 1) {
+            char c = size.charAt(len-1);
+            if (c == 'K' || c == 'k') {
+                multiplier = 1024L;
+            } else if (c == 'M' || c == 'm') {
+                multiplier = 1024L*1024L;
+            } else if (c == 'G' || c == 'g') {
+                multiplier = 1024L*1024L*1024L;
+            } else {
+                System.err.println("Invalid suffix: " + c);
+                showUsage();
+                return;
+            }
+            size = size.substring(0, len-1);
+        }
+        long sizeVal;
+        try {
+            sizeVal = Long.parseLong(size) * multiplier;
+        } catch (NumberFormatException e) {
+            System.err.println("Error: expected number at: " + size);
+            showUsage();
+            return;
+        }
+        ClearDataObserver obs = new ClearDataObserver();
+        try {
+            mPm.freeStorageAndNotify(sizeVal, obs);
+            synchronized (obs) {
+                while (!obs.finished) {
+                    try {
+                        obs.wait();
+                    } catch (InterruptedException e) {
+                    }
+                }
+            }
+        } catch (RemoteException e) {
+            System.err.println(e.toString());
+            System.err.println(PM_NOT_RUNNING_ERR);
+        } catch (IllegalArgumentException e) {
+            System.err.println("Bad argument: " + e.toString());
+            showUsage();
+        } catch (SecurityException e) {
+            System.err.println("Operation not allowed: " + e.toString());
+        }
+    }
+
     /**
      * Displays the package file for a package.
      * @param pckg
@@ -1373,6 +1447,7 @@
         System.err.println("       pm set-install-location [0/auto] [1/internal] [2/external]");
         System.err.println("       pm get-install-location");
         System.err.println("       pm set-permission-enforced PERMISSION [true|false]");
+        System.err.println("       pm trim-caches DESIRED_FREE_SPACE");
         System.err.println("");
         System.err.println("pm list packages: prints all packages, optionally only");
         System.err.println("  those whose package name contains the text in FILTER.  Options:");
@@ -1434,5 +1509,7 @@
         System.err.println("    0 [auto]: Let system decide the best location");
         System.err.println("    1 [internal]: Install on internal device storage");
         System.err.println("    2 [external]: Install on external media");
+        System.err.println("");
+        System.err.println("pm trim-caches: trim cache files to reach the given free space.");
     }
 }
diff --git a/services/java/com/android/server/DeviceStorageMonitorService.java b/services/java/com/android/server/DeviceStorageMonitorService.java
index 0ed5189..9231674 100644
--- a/services/java/com/android/server/DeviceStorageMonitorService.java
+++ b/services/java/com/android/server/DeviceStorageMonitorService.java
@@ -16,6 +16,9 @@
 
 package com.android.server;
 
+import java.io.FileDescriptor;
+import java.io.PrintWriter;
+
 import android.app.Notification;
 import android.app.NotificationManager;
 import android.app.PendingIntent;
@@ -24,6 +27,7 @@
 import android.content.Intent;
 import android.content.pm.IPackageDataObserver;
 import android.content.pm.IPackageManager;
+import android.content.pm.PackageManager;
 import android.os.Binder;
 import android.os.Environment;
 import android.os.FileObserver;
@@ -36,8 +40,10 @@
 import android.os.SystemClock;
 import android.os.SystemProperties;
 import android.provider.Settings;
+import android.text.format.Formatter;
 import android.util.EventLog;
 import android.util.Slog;
+import android.util.TimeUtils;
 
 /**
  * This class implements a service to monitor the amount of disk
@@ -71,6 +77,7 @@
     private static final long DEFAULT_CHECK_INTERVAL = MONITOR_INTERVAL*60*1000;
     private static final int DEFAULT_FULL_THRESHOLD_BYTES = 1024*1024; // 1MB
     private long mFreeMem;  // on /data
+    private long mFreeMemAfterLastCacheClear;  // on /data
     private long mLastReportedFreeMem;
     private long mLastReportedFreeMemTime;
     private boolean mLowMemFlag=false;
@@ -95,7 +102,19 @@
     private final CacheFileDeletedObserver mCacheFileDeletedObserver;
     private static final int _TRUE = 1;
     private static final int _FALSE = 0;
+    // This is the raw threshold that has been set at which we consider
+    // storage to be low.
     private long mMemLowThreshold;
+    // This is the threshold at which we start trying to flush caches
+    // to get below the low threshold limit.  It is less than the low
+    // threshold; we will allow storage to get a bit beyond the limit
+    // before flushing and checking if we are actually low.
+    private long mMemCacheStartTrimThreshold;
+    // This is the threshold that we try to get to when deleting cache
+    // files.  This is greater than the low threshold so that we will flush
+    // more files than absolutely needed, to reduce the frequency that
+    // flushing takes place.
+    private long mMemCacheTrimToThreshold;
     private int mMemFullThreshold;
 
     /**
@@ -190,7 +209,7 @@
         try {
             if (localLOGV) Slog.i(TAG, "Clearing cache");
             IPackageManager.Stub.asInterface(ServiceManager.getService("package")).
-                    freeStorageAndNotify(mMemLowThreshold, mClearCacheObserver);
+                    freeStorageAndNotify(mMemCacheTrimToThreshold, mClearCacheObserver);
         } catch (RemoteException e) {
             Slog.w(TAG, "Failed to get handle for PackageManger Exception: "+e);
             mClearingCache = false;
@@ -216,24 +235,42 @@
 
             //post intent to NotificationManager to display icon if necessary
             if (mFreeMem < mMemLowThreshold) {
-                if (!mLowMemFlag) {
-                    if (checkCache) {
-                        // See if clearing cache helps
-                        // Note that clearing cache is asynchronous and so we do a
-                        // memory check again once the cache has been cleared.
-                        mThreadStartTime = System.currentTimeMillis();
-                        mClearSucceeded = false;
-                        clearCache();
-                    } else {
+                if (checkCache) {
+                    // We are allowed to clear cache files at this point to
+                    // try to get down below the limit, because this is not
+                    // the initial call after a cache clear has been attempted.
+                    // In this case we will try a cache clear if our free
+                    // space has gone below the cache clear limit.
+                    if (mFreeMem < mMemCacheStartTrimThreshold) {
+                        // We only clear the cache if the free storage has changed
+                        // a significant amount since the last time.
+                        if ((mFreeMemAfterLastCacheClear-mFreeMem)
+                                >= ((mMemLowThreshold-mMemCacheStartTrimThreshold)/4)) {
+                            // See if clearing cache helps
+                            // Note that clearing cache is asynchronous and so we do a
+                            // memory check again once the cache has been cleared.
+                            mThreadStartTime = System.currentTimeMillis();
+                            mClearSucceeded = false;
+                            clearCache();
+                        }
+                    }
+                } else {
+                    // This is a call from after clearing the cache.  Note
+                    // the amount of free storage at this point.
+                    mFreeMemAfterLastCacheClear = mFreeMem;
+                    if (!mLowMemFlag) {
+                        // We tried to clear the cache, but that didn't get us
+                        // below the low storage limit.  Tell the user.
                         Slog.i(TAG, "Running low on memory. Sending notification");
                         sendNotification();
                         mLowMemFlag = true;
+                    } else {
+                        if (localLOGV) Slog.v(TAG, "Running low on memory " +
+                                "notification already sent. do nothing");
                     }
-                } else {
-                    if (localLOGV) Slog.v(TAG, "Running low on memory " +
-                            "notification already sent. do nothing");
                 }
             } else {
+                mFreeMemAfterLastCacheClear = mFreeMem;
                 if (mLowMemFlag) {
                     Slog.i(TAG, "Memory available. Cancelling notification");
                     cancelNotification();
@@ -276,7 +313,7 @@
                               Settings.Secure.SYS_STORAGE_THRESHOLD_PERCENTAGE,
                               DEFAULT_THRESHOLD_PERCENTAGE);
         if(localLOGV) Slog.v(TAG, "Threshold Percentage="+value);
-        value *= mTotalMemory;
+        value = (value*mTotalMemory)/100;
         long maxValue = Settings.Secure.getInt(
                 mContentResolver,
                 Settings.Secure.SYS_STORAGE_THRESHOLD_MAX_BYTES,
@@ -312,8 +349,8 @@
         mSystemFileStats = new StatFs(SYSTEM_PATH);
         mCacheFileStats = new StatFs(CACHE_PATH);
         //initialize total storage on device
-        mTotalMemory = ((long)mDataFileStats.getBlockCount() *
-                        mDataFileStats.getBlockSize())/100L;
+        mTotalMemory = (long)mDataFileStats.getBlockCount() *
+                        mDataFileStats.getBlockSize();
         mStorageLowIntent = new Intent(Intent.ACTION_DEVICE_STORAGE_LOW);
         mStorageLowIntent.addFlags(Intent.FLAG_RECEIVER_REGISTERED_ONLY_BEFORE_BOOT);
         mStorageOkIntent = new Intent(Intent.ACTION_DEVICE_STORAGE_OK);
@@ -325,6 +362,10 @@
         // cache storage thresholds
         mMemLowThreshold = getMemThreshold();
         mMemFullThreshold = getMemFullThreshold();
+        mMemCacheStartTrimThreshold = ((mMemLowThreshold*3)+mMemFullThreshold)/4;
+        mMemCacheTrimToThreshold = mMemLowThreshold
+                + ((mMemLowThreshold-mMemCacheStartTrimThreshold)*2);
+        mFreeMemAfterLastCacheClear = mTotalMemory;
         checkMemory(true);
 
         mCacheFileDeletedObserver = new CacheFileDeletedObserver();
@@ -435,4 +476,40 @@
             EventLogTags.writeCacheFileDeleted(path);
         }
     }
+
+    @Override
+    protected void dump(FileDescriptor fd, PrintWriter pw, String[] args) {
+        if (mContext.checkCallingOrSelfPermission(android.Manifest.permission.DUMP)
+                != PackageManager.PERMISSION_GRANTED) {
+
+            pw.println("Permission Denial: can't dump " + SERVICE + " from from pid="
+                    + Binder.getCallingPid()
+                    + ", uid=" + Binder.getCallingUid());
+            return;
+        }
+
+        pw.println("Current DeviceStorageMonitor state:");
+        pw.print("  mFreeMem="); pw.print(Formatter.formatFileSize(mContext, mFreeMem));
+                pw.print(" mTotalMemory=");
+                pw.println(Formatter.formatFileSize(mContext, mTotalMemory));
+        pw.print("  mFreeMemAfterLastCacheClear=");
+                pw.println(Formatter.formatFileSize(mContext, mFreeMemAfterLastCacheClear));
+        pw.print("  mLastReportedFreeMem=");
+                pw.print(Formatter.formatFileSize(mContext, mLastReportedFreeMem));
+                pw.print(" mLastReportedFreeMemTime=");
+                TimeUtils.formatDuration(mLastReportedFreeMemTime, SystemClock.elapsedRealtime(), pw);
+                pw.println();
+        pw.print("  mLowMemFlag="); pw.print(mLowMemFlag);
+                pw.print(" mMemFullFlag="); pw.println(mMemFullFlag);
+        pw.print("  mClearSucceeded="); pw.print(mClearSucceeded);
+                pw.print(" mClearingCache="); pw.println(mClearingCache);
+        pw.print("  mMemLowThreshold=");
+                pw.print(Formatter.formatFileSize(mContext, mMemLowThreshold));
+                pw.print(" mMemFullThreshold=");
+                pw.println(Formatter.formatFileSize(mContext, mMemFullThreshold));
+        pw.print("  mMemCacheStartTrimThreshold=");
+                pw.print(Formatter.formatFileSize(mContext, mMemCacheStartTrimThreshold));
+                pw.print(" mMemCacheTrimToThreshold=");
+                pw.println(Formatter.formatFileSize(mContext, mMemCacheTrimToThreshold));
+    }
 }