diff --git a/applypatch/applypatch.cpp b/applypatch/applypatch.cpp
index 7645a40..6f6c187 100644
--- a/applypatch/applypatch.cpp
+++ b/applypatch/applypatch.cpp
@@ -436,13 +436,13 @@
 
 // Return the amount of free space (in bytes) on the filesystem
 // containing filename.  filename must exist.  Return -1 on error.
-size_t FreeSpaceForFile(const char* filename) {
-    struct statfs sf;
-    if (statfs(filename, &sf) != 0) {
-        printf("failed to statfs %s: %s\n", filename, strerror(errno));
-        return -1;
-    }
-    return sf.f_bsize * sf.f_bavail;
+size_t FreeSpaceForFile(const std::string& filename) {
+  struct statfs sf;
+  if (statfs(filename.c_str(), &sf) != 0) {
+    printf("failed to statfs %s: %s\n", filename.c_str(), strerror(errno));
+    return -1;
+  }
+  return sf.f_bsize * sf.f_bavail;
 }
 
 int CacheSizeCheck(size_t bytes) {
diff --git a/applypatch/freecache.cpp b/applypatch/freecache.cpp
index ea364d8..cfab0f6 100644
--- a/applypatch/freecache.cpp
+++ b/applypatch/freecache.cpp
@@ -14,7 +14,10 @@
  * limitations under the License.
  */
 
+#include <ctype.h>
+#include <dirent.h>
 #include <errno.h>
+#include <error.h>
 #include <libgen.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -22,20 +25,22 @@
 #include <sys/stat.h>
 #include <sys/statfs.h>
 #include <unistd.h>
-#include <dirent.h>
-#include <ctype.h>
 
+#include <algorithm>
+#include <limits>
 #include <memory>
 #include <set>
 #include <string>
 
+#include <android-base/file.h>
 #include <android-base/parseint.h>
 #include <android-base/stringprintf.h>
+#include <android-base/strings.h>
 
 #include "applypatch/applypatch.h"
 #include "otautil/cache_location.h"
 
-static int EliminateOpenFiles(std::set<std::string>* files) {
+static int EliminateOpenFiles(const std::string& dirname, std::set<std::string>* files) {
   std::unique_ptr<DIR, decltype(&closedir)> d(opendir("/proc"), closedir);
   if (!d) {
     printf("error opening /proc: %s\n", strerror(errno));
@@ -62,7 +67,7 @@
       int count = readlink(fd_path.c_str(), link, sizeof(link)-1);
       if (count >= 0) {
         link[count] = '\0';
-        if (strncmp(link, "/cache/", 7) == 0) {
+        if (android::base::StartsWith(link, dirname)) {
           if (files->erase(link) > 0) {
             printf("%s is open by %s\n", link, de->d_name);
           }
@@ -73,77 +78,138 @@
   return 0;
 }
 
-static std::set<std::string> FindExpendableFiles() {
+static std::vector<std::string> FindExpendableFiles(
+    const std::string& dirname, const std::function<bool(const std::string&)>& name_filter) {
   std::set<std::string> files;
-  // We're allowed to delete unopened regular files in any of these
-  // directories.
-  const char* dirs[2] = {"/cache", "/cache/recovery/otatest"};
 
-  for (size_t i = 0; i < sizeof(dirs)/sizeof(dirs[0]); ++i) {
-    std::unique_ptr<DIR, decltype(&closedir)> d(opendir(dirs[i]), closedir);
-    if (!d) {
-      printf("error opening %s: %s\n", dirs[i], strerror(errno));
+  std::unique_ptr<DIR, decltype(&closedir)> d(opendir(dirname.c_str()), closedir);
+  if (!d) {
+    printf("error opening %s: %s\n", dirname.c_str(), strerror(errno));
+    return {};
+  }
+
+  // Look for regular files in the directory (not in any subdirectories).
+  struct dirent* de;
+  while ((de = readdir(d.get())) != 0) {
+    std::string path = dirname + "/" + de->d_name;
+
+    // We can't delete cache_temp_source; if it's there we might have restarted during
+    // installation and could be depending on it to be there.
+    if (path == CacheLocation::location().cache_temp_source()) {
       continue;
     }
 
-    // Look for regular files in the directory (not in any subdirectories).
-    struct dirent* de;
-    while ((de = readdir(d.get())) != 0) {
-      std::string path = std::string(dirs[i]) + "/" + de->d_name;
+    // Do not delete the file if it doesn't have the expected format.
+    if (name_filter != nullptr && !name_filter(de->d_name)) {
+      continue;
+    }
 
-      // We can't delete cache_temp_source; if it's there we might have restarted during
-      // installation and could be depending on it to be there.
-      if (path == CacheLocation::location().cache_temp_source()) {
-        continue;
-      }
-
-      struct stat st;
-      if (stat(path.c_str(), &st) == 0 && S_ISREG(st.st_mode)) {
-        files.insert(path);
-      }
+    struct stat st;
+    if (stat(path.c_str(), &st) == 0 && S_ISREG(st.st_mode)) {
+      files.insert(path);
     }
   }
 
-  printf("%zu regular files in deletable directories\n", files.size());
-  if (EliminateOpenFiles(&files) < 0) {
-    return std::set<std::string>();
+  printf("%zu regular files in deletable directory\n", files.size());
+  if (EliminateOpenFiles(dirname, &files) < 0) {
+    return {};
   }
-  return files;
+
+  return std::vector<std::string>(files.begin(), files.end());
+}
+
+// Parses the index of given log file, e.g. 3 for last_log.3; returns max number if the log name
+// doesn't have the expected format so that we'll delete these ones first.
+static unsigned int GetLogIndex(const std::string& log_name) {
+  if (log_name == "last_log" || log_name == "last_kmsg") {
+    return 0;
+  }
+
+  unsigned int index;
+  if (sscanf(log_name.c_str(), "last_log.%u", &index) == 1 ||
+      sscanf(log_name.c_str(), "last_kmsg.%u", &index) == 1) {
+    return index;
+  }
+
+  return std::numeric_limits<unsigned int>::max();
 }
 
 int MakeFreeSpaceOnCache(size_t bytes_needed) {
 #ifndef __ANDROID__
   // TODO (xunchang) implement a heuristic cache size check during host simulation.
-  printf("Skip making (%zu) bytes free space on cache; program is running on host\n", bytes_needed);
+  printf("Skip making (%zu) bytes free space on /cache; program is running on host\n",
+         bytes_needed);
   return 0;
 #endif
 
-  size_t free_now = FreeSpaceForFile("/cache");
-  printf("%zu bytes free on /cache (%zu needed)\n", free_now, bytes_needed);
-
-  if (free_now >= bytes_needed) {
-    return 0;
-  }
-  std::set<std::string> files = FindExpendableFiles();
-  if (files.empty()) {
-    // nothing we can delete to free up space!
-    printf("no files can be deleted to free space on /cache\n");
-    return -1;
-  }
-
-  // We could try to be smarter about which files to delete:  the
-  // biggest ones?  the smallest ones that will free up enough space?
-  // the oldest?  the newest?
-  //
-  // Instead, we'll be dumb.
-
-  for (const auto& file : files) {
-    unlink(file.c_str());
-    free_now = FreeSpaceForFile("/cache");
-    printf("deleted %s; now %zu bytes free\n", file.c_str(), free_now);
-    if (free_now < bytes_needed) {
-        break;
+  std::vector<std::string> dirs = { "/cache", CacheLocation::location().cache_log_directory() };
+  for (const auto& dirname : dirs) {
+    if (RemoveFilesInDirectory(bytes_needed, dirname, FreeSpaceForFile)) {
+      return 0;
     }
   }
-  return (free_now >= bytes_needed) ? 0 : -1;
+
+  return -1;
+}
+
+bool RemoveFilesInDirectory(size_t bytes_needed, const std::string& dirname,
+                            const std::function<size_t(const std::string&)>& space_checker) {
+  struct stat st;
+  if (stat(dirname.c_str(), &st) != 0) {
+    error(0, errno, "Unable to free space on %s", dirname.c_str());
+    return false;
+  }
+  if (!S_ISDIR(st.st_mode)) {
+    printf("%s is not a directory\n", dirname.c_str());
+    return false;
+  }
+
+  size_t free_now = space_checker(dirname);
+  printf("%zu bytes free on %s (%zu needed)\n", free_now, dirname.c_str(), bytes_needed);
+
+  if (free_now >= bytes_needed) {
+    return true;
+  }
+
+  std::vector<std::string> files;
+  if (dirname == CacheLocation::location().cache_log_directory()) {
+    // Deletes the log files only.
+    auto log_filter = [](const std::string& file_name) {
+      return android::base::StartsWith(file_name, "last_log") ||
+             android::base::StartsWith(file_name, "last_kmsg");
+    };
+
+    files = FindExpendableFiles(dirname, log_filter);
+
+    // Older logs will come to the top of the queue.
+    auto comparator = [](const std::string& name1, const std::string& name2) -> bool {
+      unsigned int index1 = GetLogIndex(android::base::Basename(name1));
+      unsigned int index2 = GetLogIndex(android::base::Basename(name2));
+      if (index1 == index2) {
+        return name1 < name2;
+      }
+
+      return index1 > index2;
+    };
+
+    std::sort(files.begin(), files.end(), comparator);
+  } else {
+    // We're allowed to delete unopened regular files in the directory.
+    files = FindExpendableFiles(dirname, nullptr);
+  }
+
+  for (const auto& file : files) {
+    if (unlink(file.c_str()) == -1) {
+      error(0, errno, "Failed to delete %s", file.c_str());
+      continue;
+    }
+
+    free_now = space_checker(dirname);
+    printf("deleted %s; now %zu bytes free\n", file.c_str(), free_now);
+    if (free_now >= bytes_needed) {
+      return true;
+    }
+  }
+
+  return false;
 }
diff --git a/applypatch/include/applypatch/applypatch.h b/applypatch/include/applypatch/applypatch.h
index 912ead1..021a28d 100644
--- a/applypatch/include/applypatch/applypatch.h
+++ b/applypatch/include/applypatch/applypatch.h
@@ -39,7 +39,7 @@
 // applypatch.cpp
 
 int ShowLicenses();
-size_t FreeSpaceForFile(const char* filename);
+size_t FreeSpaceForFile(const std::string& filename);
 int CacheSizeCheck(size_t bytes);
 int ParseSha1(const char* str, uint8_t* digest);
 
@@ -79,5 +79,9 @@
 // freecache.cpp
 
 int MakeFreeSpaceOnCache(size_t bytes_needed);
+// Removes the files in |dirname| until we have at least |bytes_needed| bytes of free space on
+// the partition. The size of the free space is returned by calling |space_checker|.
+bool RemoveFilesInDirectory(size_t bytes_needed, const std::string& dirname,
+                            const std::function<size_t(const std::string&)>& space_checker);
 
 #endif
diff --git a/otautil/cache_location.cpp b/otautil/cache_location.cpp
index 8ddefec..6139bf1 100644
--- a/otautil/cache_location.cpp
+++ b/otautil/cache_location.cpp
@@ -19,6 +19,7 @@
 constexpr const char kDefaultCacheTempSource[] = "/cache/saved.file";
 constexpr const char kDefaultLastCommandFile[] = "/cache/recovery/last_command";
 constexpr const char kDefaultStashDirectoryBase[] = "/cache/recovery";
+constexpr const char kDefaultCacheLogDirectory[] = "/cache/recovery";
 
 CacheLocation& CacheLocation::location() {
   static CacheLocation cache_location;
@@ -28,4 +29,5 @@
 CacheLocation::CacheLocation()
     : cache_temp_source_(kDefaultCacheTempSource),
       last_command_file_(kDefaultLastCommandFile),
-      stash_directory_base_(kDefaultStashDirectoryBase) {}
+      stash_directory_base_(kDefaultStashDirectoryBase),
+      cache_log_directory_(kDefaultCacheLogDirectory) {}
diff --git a/otautil/include/otautil/cache_location.h b/otautil/include/otautil/cache_location.h
index f2f6638..005395e 100644
--- a/otautil/include/otautil/cache_location.h
+++ b/otautil/include/otautil/cache_location.h
@@ -49,6 +49,13 @@
     stash_directory_base_ = base;
   }
 
+  std::string cache_log_directory() const {
+    return cache_log_directory_;
+  }
+  void set_cache_log_directory(const std::string& log_dir) {
+    cache_log_directory_ = log_dir;
+  }
+
  private:
   CacheLocation();
   DISALLOW_COPY_AND_ASSIGN(CacheLocation);
@@ -64,6 +71,9 @@
 
   // The base directory to write stashes during update.
   std::string stash_directory_base_;
+
+  // The location of last_log & last_kmsg.
+  std::string cache_log_directory_;
 };
 
 #endif  // _OTAUTIL_OTAUTIL_CACHE_LOCATION_H_
diff --git a/tests/component/applypatch_test.cpp b/tests/component/applypatch_test.cpp
index 9160285..aa0959b 100644
--- a/tests/component/applypatch_test.cpp
+++ b/tests/component/applypatch_test.cpp
@@ -14,8 +14,10 @@
  * limitations under the License.
  */
 
+#include <dirent.h>
 #include <fcntl.h>
 #include <gtest/gtest.h>
+#include <libgen.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <sys/stat.h>
@@ -23,6 +25,7 @@
 #include <sys/types.h>
 #include <time.h>
 
+#include <algorithm>
 #include <memory>
 #include <string>
 #include <vector>
@@ -30,6 +33,7 @@
 #include <android-base/file.h>
 #include <android-base/stringprintf.h>
 #include <android-base/test_utils.h>
+#include <android-base/unique_fd.h>
 #include <bsdiff/bsdiff.h>
 #include <openssl/sha.h>
 
@@ -110,6 +114,52 @@
   TemporaryFile cache_source;
 };
 
+class FreeCacheTest : public ::testing::Test {
+ protected:
+  static constexpr size_t PARTITION_SIZE = 4096 * 10;
+
+  // Returns a sorted list of files in |dirname|.
+  static std::vector<std::string> FindFilesInDir(const std::string& dirname) {
+    std::vector<std::string> file_list;
+
+    std::unique_ptr<DIR, decltype(&closedir)> d(opendir(dirname.c_str()), closedir);
+    struct dirent* de;
+    while ((de = readdir(d.get())) != 0) {
+      std::string path = dirname + "/" + de->d_name;
+
+      struct stat st;
+      if (stat(path.c_str(), &st) == 0 && S_ISREG(st.st_mode)) {
+        file_list.emplace_back(de->d_name);
+      }
+    }
+
+    std::sort(file_list.begin(), file_list.end());
+    return file_list;
+  }
+
+  static void AddFilesToDir(const std::string& dir, const std::vector<std::string>& files) {
+    std::string zeros(4096, 0);
+    for (const auto& file : files) {
+      std::string path = dir + "/" + file;
+      ASSERT_TRUE(android::base::WriteStringToFile(zeros, path));
+    }
+  }
+
+  void SetUp() override {
+    CacheLocation::location().set_cache_log_directory(mock_log_dir.path);
+  }
+
+  // A mock method to calculate the free space. It assumes the partition has a total size of 40960
+  // bytes and all files are 4096 bytes in size.
+  size_t MockFreeSpaceChecker(const std::string& dirname) {
+    std::vector<std::string> files = FindFilesInDir(dirname);
+    return PARTITION_SIZE - 4096 * files.size();
+  }
+
+  TemporaryDir mock_cache;
+  TemporaryDir mock_log_dir;
+};
+
 TEST_F(ApplyPatchTest, CheckModeSkip) {
   std::vector<std::string> sha1s;
   ASSERT_EQ(0, applypatch_check(&old_file[0], sha1s));
@@ -414,3 +464,82 @@
 TEST_F(ApplyPatchModesTest, ShowLicenses) {
   ASSERT_EQ(0, applypatch_modes(2, (const char* []){ "applypatch", "-l" }));
 }
+
+TEST_F(FreeCacheTest, FreeCacheSmoke) {
+  std::vector<std::string> files = { "file1", "file2", "file3" };
+  AddFilesToDir(mock_cache.path, files);
+  ASSERT_EQ(files, FindFilesInDir(mock_cache.path));
+  ASSERT_EQ(4096 * 7, MockFreeSpaceChecker(mock_cache.path));
+
+  ASSERT_TRUE(RemoveFilesInDirectory(4096 * 9, mock_cache.path, [&](const std::string& dir) {
+    return this->MockFreeSpaceChecker(dir);
+  }));
+
+  ASSERT_EQ(std::vector<std::string>{ "file3" }, FindFilesInDir(mock_cache.path));
+  ASSERT_EQ(4096 * 9, MockFreeSpaceChecker(mock_cache.path));
+}
+
+TEST_F(FreeCacheTest, FreeCacheOpenFile) {
+  std::vector<std::string> files = { "file1", "file2" };
+  AddFilesToDir(mock_cache.path, files);
+  ASSERT_EQ(files, FindFilesInDir(mock_cache.path));
+  ASSERT_EQ(4096 * 8, MockFreeSpaceChecker(mock_cache.path));
+
+  std::string file1_path = mock_cache.path + "/file1"s;
+  android::base::unique_fd fd(open(file1_path.c_str(), O_RDONLY));
+
+  // file1 can't be deleted as it's opened by us.
+  ASSERT_FALSE(RemoveFilesInDirectory(4096 * 10, mock_cache.path, [&](const std::string& dir) {
+    return this->MockFreeSpaceChecker(dir);
+  }));
+
+  ASSERT_EQ(std::vector<std::string>{ "file1" }, FindFilesInDir(mock_cache.path));
+}
+
+TEST_F(FreeCacheTest, FreeCacheLogsSmoke) {
+  std::vector<std::string> log_files = { "last_log", "last_log.1", "last_kmsg.2", "last_log.5",
+                                         "last_log.10" };
+  AddFilesToDir(mock_log_dir.path, log_files);
+  ASSERT_EQ(4096 * 5, MockFreeSpaceChecker(mock_log_dir.path));
+
+  ASSERT_TRUE(RemoveFilesInDirectory(4096 * 8, mock_log_dir.path, [&](const std::string& dir) {
+    return this->MockFreeSpaceChecker(dir);
+  }));
+
+  // Logs with a higher index will be deleted first
+  std::vector<std::string> expected = { "last_log", "last_log.1" };
+  ASSERT_EQ(expected, FindFilesInDir(mock_log_dir.path));
+  ASSERT_EQ(4096 * 8, MockFreeSpaceChecker(mock_log_dir.path));
+}
+
+TEST_F(FreeCacheTest, FreeCacheLogsStringComparison) {
+  std::vector<std::string> log_files = { "last_log.1", "last_kmsg.1", "last_log.not_number",
+                                         "last_kmsgrandom" };
+  AddFilesToDir(mock_log_dir.path, log_files);
+  ASSERT_EQ(4096 * 6, MockFreeSpaceChecker(mock_log_dir.path));
+
+  ASSERT_TRUE(RemoveFilesInDirectory(4096 * 9, mock_log_dir.path, [&](const std::string& dir) {
+    return this->MockFreeSpaceChecker(dir);
+  }));
+
+  // Logs with incorrect format will be deleted first; and the last_kmsg with the same index is
+  // deleted before last_log.
+  std::vector<std::string> expected = { "last_log.1" };
+  ASSERT_EQ(expected, FindFilesInDir(mock_log_dir.path));
+  ASSERT_EQ(4096 * 9, MockFreeSpaceChecker(mock_log_dir.path));
+}
+
+TEST_F(FreeCacheTest, FreeCacheLogsOtherFiles) {
+  std::vector<std::string> log_files = { "last_install", "command", "block.map", "last_log",
+                                         "last_kmsg.1" };
+  AddFilesToDir(mock_log_dir.path, log_files);
+  ASSERT_EQ(4096 * 5, MockFreeSpaceChecker(mock_log_dir.path));
+
+  ASSERT_FALSE(RemoveFilesInDirectory(4096 * 8, mock_log_dir.path, [&](const std::string& dir) {
+    return this->MockFreeSpaceChecker(dir);
+  }));
+
+  // Non log files in /cache/recovery won't be deleted.
+  std::vector<std::string> expected = { "block.map", "command", "last_install" };
+  ASSERT_EQ(expected, FindFilesInDir(mock_log_dir.path));
+}