diff --git a/fuse_sideload/fuse_sideload.cpp b/fuse_sideload/fuse_sideload.cpp
index 3d94803..a4f08a2 100644
--- a/fuse_sideload/fuse_sideload.cpp
+++ b/fuse_sideload/fuse_sideload.cpp
@@ -73,6 +73,8 @@
 
 using SHA256Digest = std::array<uint8_t, SHA256_DIGEST_LENGTH>;
 
+#define INSTALL_REQUIRED_MEMORY (100 * 1024 * 1024)
+
 struct fuse_data {
   android::base::unique_fd ffd;  // file descriptor for the fuse socket
 
@@ -86,15 +88,84 @@
   uid_t uid;
   gid_t gid;
 
-  uint32_t curr_block;  // cache the block most recently read from the host
+  uint32_t curr_block;  // cache the block most recently used
   uint8_t* block_data;
 
   uint8_t* extra_block;  // another block of storage for reads that span two blocks
 
   std::vector<SHA256Digest>
       hashes;  // SHA-256 hash of each block (all zeros if block hasn't been read yet)
+
+  // Block cache
+  uint32_t block_cache_max_size;  // Max allowed block cache size
+  uint32_t block_cache_size;      // Current block cache size
+  uint8_t** block_cache;          // Block cache data
 };
 
+static uint64_t free_memory() {
+  uint64_t mem = 0;
+  FILE* fp = fopen("/proc/meminfo", "r");
+  if (fp) {
+    char buf[256];
+    char* linebuf = buf;
+    size_t buflen = sizeof(buf);
+    while (getline(&linebuf, &buflen, fp) > 0) {
+      char* key = buf;
+      char* val = strchr(buf, ':');
+      *val = '\0';
+      ++val;
+      if (strcmp(key, "MemFree") == 0) {
+        mem += strtoul(val, nullptr, 0) * 1024;
+      }
+      if (strcmp(key, "Buffers") == 0) {
+        mem += strtoul(val, nullptr, 0) * 1024;
+      }
+      if (strcmp(key, "Cached") == 0) {
+        mem += strtoul(val, nullptr, 0) * 1024;
+      }
+    }
+    fclose(fp);
+  }
+  return mem;
+}
+
+static int block_cache_fetch(struct fuse_data* fd, uint32_t block) {
+  if (fd->block_cache == nullptr) {
+    return -1;
+  }
+  if (fd->block_cache[block] == nullptr) {
+    return -1;
+  }
+  memcpy(fd->block_data, fd->block_cache[block], fd->block_size);
+  return 0;
+}
+
+static void block_cache_enter(struct fuse_data* fd, uint32_t block) {
+  if (!fd->block_cache) return;
+  if (fd->block_cache_size == fd->block_cache_max_size) {
+    // Evict a block from the cache.  Since the file is typically read
+    // sequentially, start looking from the block behind the current
+    // block and proceed backward.
+    int n;
+    for (n = fd->curr_block - 1; n != (int)fd->curr_block; --n) {
+      if (n < 0) {
+        n = fd->file_blocks - 1;
+      }
+      if (fd->block_cache[n]) {
+        free(fd->block_cache[n]);
+        fd->block_cache[n] = nullptr;
+        fd->block_cache_size--;
+        break;
+      }
+    }
+  }
+
+  fd->block_cache[block] = (uint8_t*)malloc(fd->block_size);
+  memcpy(fd->block_cache[block], fd->block_data, fd->block_size);
+
+  fd->block_cache_size++;
+}
+
 static void fuse_reply(const fuse_data* fd, uint64_t unique, const void* data, size_t len) {
   fuse_out_header hdr;
   hdr.len = len + sizeof(hdr);
@@ -236,6 +307,11 @@
     return 0;
   }
 
+  if (block_cache_fetch(fd, block) == 0) {
+    fd->curr_block = block;
+    return 0;
+  }
+
   uint32_t fetch_size = fd->block_size;
   if (block * fd->block_size + fetch_size > fd->file_size) {
     // If we're reading the last (partial) block of the file, expect a shorter response from the
@@ -273,6 +349,7 @@
   }
 
   fd->hashes[block] = hash;
+  block_cache_enter(fd, block);
   return 0;
 }
 
@@ -365,6 +442,9 @@
   fd.block_size = block_size;
   fd.file_blocks = (file_size == 0) ? 0 : (((file_size - 1) / block_size) + 1);
 
+  uint64_t mem = free_memory();
+  uint64_t avail = mem - (INSTALL_REQUIRED_MEMORY + fd.file_blocks * sizeof(uint8_t*));
+
   int result;
   if (fd.file_blocks > (1 << 18)) {
     fprintf(stderr, "file has too many blocks (%u)\n", fd.file_blocks);
@@ -391,6 +471,22 @@
     goto done;
   }
 
+  fd.block_cache_max_size = 0;
+  fd.block_cache_size = 0;
+  fd.block_cache = nullptr;
+  if (mem > avail) {
+    uint32_t max_size = avail / fd.block_size;
+    if (max_size > fd.file_blocks) {
+      max_size = fd.file_blocks;
+    }
+    // The cache must be at least 1% of the file size or two blocks,
+    // whichever is larger.
+    if (max_size >= fd.file_blocks / 100 && max_size >= 2) {
+      fd.block_cache_max_size = max_size;
+      fd.block_cache = (uint8_t**)calloc(fd.file_blocks, sizeof(uint8_t*));
+    }
+  }
+
   fd.ffd.reset(open("/dev/fuse", O_RDWR));
   if (fd.ffd == -1) {
     perror("open /dev/fuse");
@@ -488,6 +584,14 @@
     fprintf(stderr, "fuse_sideload umount failed: %s\n", strerror(errno));
   }
 
+  if (fd.block_cache) {
+    uint32_t n;
+    for (n = 0; n < fd.file_blocks; ++n) {
+      free(fd.block_cache[n]);
+    }
+    free(fd.block_cache);
+  }
+
   free(fd.block_data);
   free(fd.extra_block);