diff --git a/app.te b/app.te
index 0c866c5..8af6244 100644
--- a/app.te
+++ b/app.te
@@ -124,7 +124,14 @@
 # Read and write /data/data/com.android.providers.telephony files passed over Binder.
 allow appdomain radio_data_file:file { read write getattr };
 
-# Access SDcard via the fuse mount.
+# See visible storage
+allow appdomain storage_file:dir r_dir_perms;
+allow appdomain storage_file:file r_file_perms;
+allow appdomain mnt_user_file:dir r_dir_perms;
+# Follow the /storage/self/primary symlink
+allow appdomain mnt_user_file:lnk_file r_file_perms;
+
+# Read/write visible storage
 allow appdomain fuse:dir create_dir_perms;
 allow appdomain fuse:file create_file_perms;
 
diff --git a/blkid.te b/blkid.te
new file mode 100644
index 0000000..54f6bc2
--- /dev/null
+++ b/blkid.te
@@ -0,0 +1,16 @@
+# blkid called from vold
+type blkid, domain;
+type blkid_exec, exec_type, file_type;
+
+# Allowed read-only access to vold block devices to extract UUID/label
+allow blkid block_device:dir search;
+allow blkid vold_device:blk_file r_file_perms;
+
+# Allow stdin/out back to vold
+allow blkid vold:fd use;
+allow blkid vold:fifo_file { read write getattr };
+
+# Only allow entry from vold
+neverallow { domain -vold } blkid:process transition;
+neverallow domain blkid:process dyntransition;
+neverallow blkid { file_type fs_type -blkid_exec }:file entrypoint;
diff --git a/file.te b/file.te
index fa4c482..782fae7 100644
--- a/file.te
+++ b/file.te
@@ -83,6 +83,15 @@
 # /data/bootchart
 type bootchart_data_file, file_type, data_file_type;
 
+# Mount locations managed by vold
+type mnt_media_rw_file, file_type;
+type mnt_user_file, file_type;
+type storage_file, file_type;
+
+# Label for storage dirs which are just mount stubs
+type mnt_media_rw_stub_file, file_type;
+type storage_stub_file, file_type;
+
 # /data/misc subdirectories
 type adb_keys_file, file_type, data_file_type;
 type audio_data_file, file_type, data_file_type;
diff --git a/file_contexts b/file_contexts
index 406f566..92b8d32 100644
--- a/file_contexts
+++ b/file_contexts
@@ -42,7 +42,7 @@
 /dev/block(/.*)?	u:object_r:block_device:s0
 /dev/block/dm-[0-9]+	u:object_r:dm_device:s0
 /dev/block/loop[0-9]*	u:object_r:loop_device:s0
-/dev/block/vold/[0-9]+:[0-9]+	u:object_r:vold_device:s0
+/dev/block/vold/.+	u:object_r:vold_device:s0
 /dev/block/ram[0-9]*	u:object_r:ram_device:s0
 /dev/bus/usb(.*)?       u:object_r:usb_device:s0
 /dev/cam		u:object_r:camera_device:s0
@@ -127,6 +127,7 @@
 /system(/.*)?		u:object_r:system_file:s0
 /system/bin/e2fsck	--	u:object_r:fsck_exec:s0
 /system/bin/fsck\.f2fs	--	u:object_r:fsck_exec:s0
+/system/bin/fsck_msdos	--	u:object_r:fsck_exec:s0
 /system/bin/toolbox	--	u:object_r:toolbox_exec:s0
 /system/bin/toybox	--	u:object_r:toolbox_exec:s0
 /system/bin/logcat	--	u:object_r:logcat_exec:s0
@@ -171,6 +172,8 @@
 /system/bin/dex2oat     u:object_r:dex2oat_exec:s0
 # patchoat executable has (essentially) the same requirements as dex2oat.
 /system/bin/patchoat    u:object_r:dex2oat_exec:s0
+/system/bin/sgdisk      u:object_r:sgdisk_exec:s0
+/system/bin/blkid       u:object_r:blkid_exec:s0
 
 #############################
 # Vendor files
@@ -270,3 +273,9 @@
 /mnt/asec/[^/]+/[^/]+\.zip  u:object_r:asec_public_file:s0
 /mnt/asec/[^/]+/lib(/.*)?   u:object_r:asec_public_file:s0
 /data/app-asec(/.*)?        u:object_r:asec_image_file:s0
+
+#############################
+# external storage
+/mnt/media_rw(/.*)?         u:object_r:mnt_media_rw_file:s0
+/mnt/user(/.*)?             u:object_r:mnt_user_file:s0
+/storage(/.*)?              u:object_r:storage_file:s0
diff --git a/fsck.te b/fsck.te
index ab4ee31..a86884c 100644
--- a/fsck.te
+++ b/fsck.te
@@ -1,4 +1,4 @@
-# e2fsck or any other fsck program run by init.
+# Any fsck program run by init or vold
 type fsck, domain;
 type fsck_exec, exec_type, file_type;
 
@@ -11,10 +11,15 @@
 # Inherit and use pty created by android_fork_execvp_ext().
 allow fsck devpts:chr_file { read write ioctl getattr };
 
-# Run e2fsck on block devices.
+# Run fsck on certain block devices
 allow fsck block_device:dir search;
 allow fsck userdata_block_device:blk_file rw_file_perms;
 allow fsck cache_block_device:blk_file rw_file_perms;
+allow fsck vold_device:blk_file rw_file_perms;
+
+# Allow stdin/out back to vold
+allow fsck vold:fd use;
+allow fsck vold:fifo_file { read write getattr };
 
 ###
 ### neverallow rules
@@ -31,7 +36,7 @@
   system_block_device
 }:blk_file no_rw_file_perms;
 
-# Only allow entry from init via the e2fsck binary.
-neverallow { domain -init } fsck:process transition;
+# Only allow entry from init or vold via fsck binaries
+neverallow { domain -init -vold } fsck:process transition;
 neverallow domain fsck:process dyntransition;
-neverallow fsck { file_type fs_type -fsck_exec}:file entrypoint;
+neverallow fsck { file_type fs_type -fsck_exec }:file entrypoint;
diff --git a/sdcardd.te b/sdcardd.te
index 5ea77a9..96216c4 100644
--- a/sdcardd.te
+++ b/sdcardd.te
@@ -1,11 +1,14 @@
 type sdcardd, domain;
 type sdcardd_exec, exec_type, file_type;
 
-init_daemon_domain(sdcardd)
+init_daemon_domain(sdcardd) # TODO: deprecated in M
 
 allow sdcardd cgroup:dir create_dir_perms;
 allow sdcardd fuse_device:chr_file rw_file_perms;
-allow sdcardd rootfs:dir mounton;
+allow sdcardd rootfs:dir mounton;  # TODO: deprecated in M
+allow sdcardd mnt_media_rw_file:dir r_dir_perms;
+allow sdcardd storage_file:dir search;
+allow sdcardd storage_stub_file:dir { search mounton };
 allow sdcardd sdcard_type:filesystem { mount unmount };
 allow sdcardd self:capability { setuid setgid dac_override sys_admin sys_resource };
 
@@ -21,3 +24,7 @@
 
 # Read /data/.layout_version
 allow sdcardd install_data_file:file r_file_perms;
+
+# Allow stdin/out back to vold
+allow sdcardd vold:fd use;
+allow sdcardd vold:fifo_file { read write getattr };
diff --git a/sgdisk.te b/sgdisk.te
new file mode 100644
index 0000000..66656b6
--- /dev/null
+++ b/sgdisk.te
@@ -0,0 +1,16 @@
+# sgdisk called from vold
+type sgdisk, domain;
+type sgdisk_exec, exec_type, file_type;
+
+# Allowed to read/write low-level partition tables
+allow sgdisk block_device:dir search;
+allow sgdisk vold_device:blk_file rw_file_perms;
+
+# Allow stdin/out back to vold
+allow sgdisk vold:fd use;
+allow sgdisk vold:fifo_file { read write getattr };
+
+# Only allow entry from vold
+neverallow { domain -vold } sgdisk:process transition;
+neverallow domain sgdisk:process dyntransition;
+neverallow sgdisk { file_type fs_type -sgdisk_exec }:file entrypoint;
diff --git a/system_server.te b/system_server.te
index 589dbef..36fbace 100644
--- a/system_server.te
+++ b/system_server.te
@@ -468,13 +468,22 @@
 # /oem access
 r_dir_file(system_server, oemfs)
 
+# Allow resolving per-user storage symlinks
+allow system_server { mnt_user_file storage_file }:dir { getattr search };
+allow system_server { mnt_user_file storage_file }:lnk_file { getattr read };
+
+# Allow statfs() on storage devices, which happens fast enough that
+# we shouldn't be killed during unsafe removal
+allow system_server sdcard_type:dir { getattr search };
+
 ###
 ### Neverallow rules
 ###
 ### system_server should NEVER do any of this
 
-# Do not allow accessing SDcard files as unsafe ejection could
-# cause the kernel to kill the system_server.
+# Do not allow opening files from external storage as unsafe ejection
+# could cause the kernel to kill the system_server.
+neverallow system_server sdcard_type:dir { open read write };
 neverallow system_server sdcard_type:file rw_file_perms;
 
 # system server should never be opening zygote spawned app data
diff --git a/vold.te b/vold.te
index 17ddd61..cde7c77 100644
--- a/vold.te
+++ b/vold.te
@@ -4,6 +4,12 @@
 
 init_daemon_domain(vold)
 
+# Switch to more restrictive domains when executing common tools
+domain_auto_trans(vold, sgdisk_exec, sgdisk);
+domain_auto_trans(vold, blkid_exec, blkid);
+domain_auto_trans(vold, sdcardd_exec, sdcardd);
+domain_auto_trans(vold, fsck_exec, fsck);
+
 typeattribute vold mlstrustedsubject;
 allow vold self:process setfscreate;
 allow vold system_file:file x_file_perms;
@@ -13,10 +19,28 @@
 allow vold device:dir write;
 allow vold devpts:chr_file rw_file_perms;
 allow vold rootfs:dir mounton;
-allow vold sdcard_type:dir mounton;
-allow vold sdcard_type:filesystem { mount remount unmount };
-allow vold sdcard_type:dir create_dir_perms;
-allow vold sdcard_type:file create_file_perms;
+allow vold sdcard_type:dir mounton; # TODO: deprecated in M
+allow vold sdcard_type:filesystem { mount remount unmount }; # TODO: deprecated in M
+allow vold sdcard_type:dir create_dir_perms; # TODO: deprecated in M
+allow vold sdcard_type:file create_file_perms; # TODO: deprecated in M
+
+# Manage locations where storage is mounted
+allow vold { mnt_media_rw_file storage_file sdcard_type }:dir create_dir_perms;
+allow vold { mnt_media_rw_file storage_file sdcard_type }:file create_file_perms;
+
+# Newly created storage dirs are always treated as mount stubs to prevent us
+# from accidentally writing when the mount point isn't present.
+type_transition vold storage_file:dir storage_stub_file;
+type_transition vold mnt_media_rw_file:dir mnt_media_rw_stub_file;
+
+# Allow mounting of storage devices
+allow vold { mnt_media_rw_stub_file storage_stub_file }:dir { mounton create rmdir getattr setattr };
+allow vold sdcard_type:filesystem { mount unmount remount };
+
+# Manage per-user primary symlinks
+allow vold mnt_user_file:dir create_dir_perms;
+allow vold mnt_user_file:lnk_file create_file_perms;
+
 allow vold tmpfs:filesystem { mount unmount };
 allow vold tmpfs:dir create_dir_perms;
 allow vold tmpfs:dir mounton;
@@ -34,7 +58,7 @@
 allow vold domain:process { signal sigkill };
 allow vold self:capability { sys_ptrace kill };
 
-# For blkid
+# For blkid and sgdisk
 allow vold shell_exec:file rx_file_perms;
 
 # XXX Label sysfs files with a specific type?
@@ -78,7 +102,7 @@
 allow vold asec_image_file:file create_file_perms;
 allow vold asec_image_file:dir rw_dir_perms;
 security_access_policy(vold)
-allow vold asec_apk_file:dir { rw_dir_perms setattr relabelfrom relabelto };
+allow vold asec_apk_file:dir { create_dir_perms mounton relabelfrom relabelto };
 allow vold asec_public_file:dir { relabelto setattr };
 allow vold asec_apk_file:file { r_file_perms setattr relabelfrom relabelto };
 allow vold asec_public_file:file { relabelto setattr };
diff --git a/zygote.te b/zygote.te
index adbea06..d2f629c 100644
--- a/zygote.te
+++ b/zygote.te
@@ -48,13 +48,19 @@
 # /proc/cpuinfo with /system/lib/<ISA>/cpuinfo using a bind mount
 allow zygote proc_cpuinfo:file mounton;
 
-# Setting up /storage/emulated.
+# Allow remounting rootfs as MS_SLAVE
 allow zygote rootfs:dir mounton;
-allow zygote sdcard_type:dir { write search setattr create add_name mounton };
-dontaudit zygote self:capability fsetid;
-allow zygote tmpfs:dir { write create add_name setattr mounton search };
-allow zygote tmpfs:filesystem mount;
-allow zygote labeledfs:filesystem remount;
+allow zygote sdcard_type:dir { write search setattr create add_name mounton }; # TODO: deprecated in M
+dontaudit zygote self:capability fsetid; # TODO: deprecated in M
+allow zygote tmpfs:dir { write create add_name setattr mounton search }; # TODO: deprecated in M
+allow zygote tmpfs:filesystem mount; # TODO: deprecated in M
+allow zygote labeledfs:filesystem remount; # TODO: deprecated in M
+
+# Allowed to create user-specific storage source if started before vold
+allow zygote mnt_user_file:dir create_dir_perms;
+allow zygote mnt_user_file:lnk_file create_file_perms;
+# Allowed to mount user-specific storage into place
+allow zygote storage_file:dir { search mounton };
 
 # Handle --invoke-with command when launching Zygote with a wrapper command.
 allow zygote zygote_exec:file rx_file_perms;