diff --git a/fs_mgr/Android.mk b/fs_mgr/Android.mk
index 61bf1ee..0ec6c4b 100644
--- a/fs_mgr/Android.mk
+++ b/fs_mgr/Android.mk
@@ -4,8 +4,12 @@
 include $(CLEAR_VARS)
 
 LOCAL_SRC_FILES:= fs_mgr.c fs_mgr_verity.c fs_mgr_fstab.c
+LOCAL_SRC_FILES += fs_mgr_format.c
 
-LOCAL_C_INCLUDES := $(LOCAL_PATH)/include
+LOCAL_C_INCLUDES := $(LOCAL_PATH)/include \
+    system/vold \
+    system/extras/ext4_utils \
+    external/openssl/include
 
 LOCAL_MODULE:= libfs_mgr
 LOCAL_STATIC_LIBRARIES := liblogwrap libmincrypt libext4_utils_static
@@ -35,6 +39,7 @@
 LOCAL_UNSTRIPPED_PATH := $(TARGET_ROOT_OUT_UNSTRIPPED)
 
 LOCAL_STATIC_LIBRARIES := libfs_mgr liblogwrap libcutils liblog libc libmincrypt libext4_utils_static
+LOCAL_STATIC_LIBRARIES += libsparse_static libz libselinux
 
 LOCAL_CFLAGS := -Werror
 
diff --git a/fs_mgr/fs_mgr.c b/fs_mgr/fs_mgr.c
index ad02922..8533ff6 100644
--- a/fs_mgr/fs_mgr.c
+++ b/fs_mgr/fs_mgr.c
@@ -40,6 +40,9 @@
 #include "mincrypt/sha.h"
 #include "mincrypt/sha256.h"
 
+#include "ext4_utils.h"
+#include "wipe.h"
+
 #include "fs_mgr_priv.h"
 #include "fs_mgr_priv_verity.h"
 
@@ -380,6 +383,8 @@
             }
         }
         int last_idx_inspected;
+        int top_idx = i;
+
         mret = mount_with_alternatives(fstab, i, &last_idx_inspected, &attempted_idx);
         i = last_idx_inspected;
         mount_errno = errno;
@@ -409,10 +414,38 @@
             continue;
         }
 
-        /* mount(2) returned an error, check if it's encryptable and deal with it */
+        /* mount(2) returned an error, handle the encryptable/formattable case */
+        bool wiped = partition_wiped(fstab->recs[top_idx].blk_device);
+        if (mret && mount_errno != EBUSY && mount_errno != EACCES &&
+            fs_mgr_is_formattable(&fstab->recs[top_idx]) && wiped) {
+            /* top_idx and attempted_idx point at the same partition, but sometimes
+             * at two different lines in the fstab.  Use the top one for formatting
+             * as that is the preferred one.
+             */
+            ERROR("%s(): %s is wiped and %s %s is formattable. Format it.\n", __func__,
+                  fstab->recs[top_idx].blk_device, fstab->recs[top_idx].mount_point,
+                  fstab->recs[top_idx].fs_type);
+            if (fs_mgr_is_encryptable(&fstab->recs[top_idx]) &&
+                strcmp(fstab->recs[top_idx].key_loc, KEY_IN_FOOTER)) {
+                int fd = open(fstab->recs[top_idx].key_loc, O_WRONLY, 0644);
+                if (fd >= 0) {
+                    INFO("%s(): also wipe %s\n", __func__, fstab->recs[top_idx].key_loc);
+                    wipe_block_device(fd, get_file_size(fd));
+                    close(fd);
+                } else {
+                    ERROR("%s(): %s wouldn't open (%s)\n", __func__,
+                          fstab->recs[top_idx].key_loc, strerror(errno));
+                }
+            }
+            if (fs_mgr_do_format(&fstab->recs[top_idx]) == 0) {
+                /* Let's replay the mount actions. */
+                i = top_idx - 1;
+                continue;
+            }
+        }
         if (mret && mount_errno != EBUSY && mount_errno != EACCES &&
             fs_mgr_is_encryptable(&fstab->recs[attempted_idx])) {
-            if(partition_wiped(fstab->recs[attempted_idx].blk_device)) {
+            if (wiped) {
                 ERROR("%s(): %s is wiped and %s %s is encryptable. Suggest recovery...\n", __func__,
                       fstab->recs[attempted_idx].blk_device, fstab->recs[attempted_idx].mount_point,
                       fstab->recs[attempted_idx].fs_type);
diff --git a/fs_mgr/fs_mgr_format.c b/fs_mgr/fs_mgr_format.c
new file mode 100644
index 0000000..b5b92b5
--- /dev/null
+++ b/fs_mgr/fs_mgr_format.c
@@ -0,0 +1,119 @@
+/*
+ * Copyright (C) 2015 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 <stdio.h>
+#include <unistd.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <sys/wait.h>
+#include <errno.h>
+#include <cutils/partition_utils.h>
+#include <sys/mount.h>
+#include "ext4_utils.h"
+#include "ext4.h"
+#include "make_ext4fs.h"
+#include "fs_mgr_priv.h"
+
+extern struct fs_info info;     /* magic global from ext4_utils */
+extern void reset_ext4fs_info();
+
+static int format_ext4(char *fs_blkdev, char *fs_mnt_point)
+{
+    unsigned int nr_sec;
+    int fd, rc = 0;
+
+    if ((fd = open(fs_blkdev, O_WRONLY, 0644)) < 0) {
+        ERROR("Cannot open block device.  %s\n", strerror(errno));
+        return -1;
+    }
+
+    if ((ioctl(fd, BLKGETSIZE, &nr_sec)) == -1) {
+        ERROR("Cannot get block device size.  %s\n", strerror(errno));
+        close(fd);
+        return -1;
+    }
+
+    /* Format the partition using the calculated length */
+    reset_ext4fs_info();
+    info.len = ((off64_t)nr_sec * 512);
+
+    /* Use make_ext4fs_internal to avoid wiping an already-wiped partition. */
+    rc = make_ext4fs_internal(fd, NULL, fs_mnt_point, 0, 0, 0, 0, 0, 0, 0, 0, NULL);
+    if (rc) {
+        ERROR("make_ext4fs returned %d.\n", rc);
+    }
+    close(fd);
+
+    return rc;
+}
+
+static int format_f2fs(char *fs_blkdev)
+{
+    char * args[3];
+    int pid;
+    int rc = 0;
+
+    args[0] = (char *)"/sbin/mkfs.f2fs";
+    args[1] = fs_blkdev;
+    args[2] = (char *)0;
+
+    pid = fork();
+    if (pid < 0) {
+       return pid;
+    }
+    if (!pid) {
+        /* This doesn't return */
+        execv("/sbin/mkfs.f2fs", args);
+        exit(1);
+    }
+    for(;;) {
+        pid_t p = waitpid(pid, &rc, 0);
+        if (p != pid) {
+            ERROR("Error waiting for child process - %d\n", p);
+            rc = -1;
+            break;
+        }
+        if (WIFEXITED(rc)) {
+            rc = WEXITSTATUS(rc);
+            INFO("%s done, status %d\n", args[0], rc);
+            if (rc) {
+                rc = -1;
+            }
+            break;
+        }
+        ERROR("Still waiting for %s...\n", args[0]);
+    }
+
+    return rc;
+}
+
+int fs_mgr_do_format(struct fstab_rec *fstab)
+{
+    int rc = -EINVAL;
+
+    ERROR("%s: Format %s as '%s'.\n", __func__, fstab->blk_device, fstab->fs_type);
+
+    if (!strncmp(fstab->fs_type, "f2fs", 4)) {
+        rc = format_f2fs(fstab->blk_device);
+    } else if (!strncmp(fstab->fs_type, "ext4", 4)) {
+        rc = format_ext4(fstab->blk_device, fstab->mount_point);
+    } else {
+        ERROR("File system type '%s' is not supported\n", fstab->fs_type);
+    }
+
+    return rc;
+}
diff --git a/fs_mgr/fs_mgr_fstab.c b/fs_mgr/fs_mgr_fstab.c
index ab8f128..edd9591 100644
--- a/fs_mgr/fs_mgr_fstab.c
+++ b/fs_mgr/fs_mgr_fstab.c
@@ -68,6 +68,7 @@
     { "zramsize=",   MF_ZRAMSIZE },
     { "verify",      MF_VERIFY },
     { "noemulatedsd", MF_NOEMULATEDSD },
+    { "formattable", MF_FORMATTABLE },
     { "defaults",    0 },
     { 0,             0 },
 };
@@ -432,3 +433,8 @@
 {
     return fstab->fs_mgr_flags & MF_NOEMULATEDSD;
 }
+
+int fs_mgr_is_formattable(struct fstab_rec *fstab)
+{
+    return fstab->fs_mgr_flags & (MF_FORMATTABLE);
+}
diff --git a/fs_mgr/fs_mgr_priv.h b/fs_mgr/fs_mgr_priv.h
index 34938fa..fd58306 100644
--- a/fs_mgr/fs_mgr_priv.h
+++ b/fs_mgr/fs_mgr_priv.h
@@ -75,6 +75,7 @@
 #define MF_FORCECRYPT   0x400
 #define MF_NOEMULATEDSD 0x800 /* no emulated sdcard daemon, sd card is the only
                                  external storage */
+#define MF_FORMATTABLE  0x1000
 
 #define DM_BUF_SIZE 4096
 
diff --git a/fs_mgr/include/fs_mgr.h b/fs_mgr/include/fs_mgr.h
index 5e2ff41..5a6ad2d 100644
--- a/fs_mgr/include/fs_mgr.h
+++ b/fs_mgr/include/fs_mgr.h
@@ -84,7 +84,11 @@
 int fs_mgr_is_verified(struct fstab_rec *fstab);
 int fs_mgr_is_encryptable(struct fstab_rec *fstab);
 int fs_mgr_is_noemulatedsd(struct fstab_rec *fstab);
+int fs_mgr_is_formattable(struct fstab_rec *fstab);
 int fs_mgr_swapon_all(struct fstab *fstab);
+
+int fs_mgr_do_format(struct fstab_rec *fstab);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/init/Android.mk b/init/Android.mk
index 489dc93..228e645 100644
--- a/init/Android.mk
+++ b/init/Android.mk
@@ -45,7 +45,9 @@
 	libc \
 	libselinux \
 	libmincrypt \
-	libext4_utils_static
+	libext4_utils_static \
+	libsparse_static \
+	libz
 
 LOCAL_ADDITIONAL_DEPENDENCIES += $(LOCAL_PATH)/Android.mk
 
diff --git a/init/devices.c b/init/devices.c
index 1012fee..73fe223 100644
--- a/init/devices.c
+++ b/init/devices.c
@@ -564,7 +564,7 @@
         make_device(devpath, path, block, major, minor, (const char **)links);
         if (links) {
             for (i = 0; links[i]; i++)
-                make_link(devpath, links[i]);
+                make_link_init(devpath, links[i]);
         }
     }
 
diff --git a/init/util.c b/init/util.c
index e1a3ee3..12cb11d 100644
--- a/init/util.c
+++ b/init/util.c
@@ -335,7 +335,7 @@
     }
 }
 
-void make_link(const char *oldpath, const char *newpath)
+void make_link_init(const char *oldpath, const char *newpath)
 {
     int ret;
     char buf[256];
diff --git a/init/util.h b/init/util.h
index 04b8129..a7e7c8b 100644
--- a/init/util.h
+++ b/init/util.h
@@ -33,7 +33,7 @@
 
 int mkdir_recursive(const char *pathname, mode_t mode);
 void sanitize(char *p);
-void make_link(const char *oldpath, const char *newpath);
+void make_link_init(const char *oldpath, const char *newpath);
 void remove_link(const char *oldpath, const char *newpath);
 int wait_for_file(const char *filename, int timeout);
 void open_devnull_stdio(void);