Repository: bytecodealliance/wasmtime
Pull request #2428 (2020-11-18 23:08:15)

wiggle: support overlapping immutable borrows
This PR renames the existing `GuestSlice` and `GuestStr` (which impl both `Deref` and `DerefMut`) to `GuestSliceMut` and `GuestStrMut`, and makes an immutable version of each called `GuestSlice` and `GuestStr`, which only impl `Deref`.

The borrow checker now distinguishes between mutable and immutable borrows, allowing overlapping immutable borrows, while still requiring mutable borrows be exclusive. Tests have been updated to exercise this, and wasi-common has been ported to borrow mutable strs and slices where necessary.

This also moves the borrow checker implementation, which was duplicated under `wiggle/wasmtime` and `wiggle/test-helpers` (and additionally over in Lucet), into its own crate `wiggle-borrow` at `wiggle/borrow`. Users can still choose whether to use it to `impl GuestMemory` or not, but putting it in a crate gets rid of some code duplication, which I care about now that the code actually changed.

<!--

Please ensure that the following steps are all taken care of before submitting
the PR.

- [ ] This has been discussed in issue #..., or if not, please tell us why
  here.
- [ ] A short description of what this does, why it is needed; if the
  description becomes long, the matter should probably be discussed in an issue
  first.
- [ ] This PR contains test cases, if meaningful.
- [ ] A reviewer from the core maintainer team has been assigned for this PR.
  If you don't know who could review this, please indicate so. The list of
  suggested reviewers on the right can help you.

Please ensure all communication adheres to the [code of
conduct](https://github.com/bytecodealliance/wasmtime/blob/master/CODE_OF_CONDUCT.md).
-->



Patch:
diff --git a/.github/actions/install-openvino/.gitignore b/.github/actions/install-openvino/.gitignore
new file mode 100644
index 000000000..ae775fc25
--- /dev/null
+++ b/.github/actions/install-openvino/.gitignore
@@ -0,0 +1,2 @@
+CHECKSUM
+GPG-PUB-KEY*
diff --git a/.github/actions/install-openvino/action.yml b/.github/actions/install-openvino/action.yml
index e4858c2d2..f80b84149 100644
--- a/.github/actions/install-openvino/action.yml
+++ b/.github/actions/install-openvino/action.yml
@@ -5,7 +5,6 @@ inputs:
   version:
     description: 'The release version of OpenVINO to install'
     required: false
-    default: '2020.4.287'
 
 runs:
   using: composite
diff --git a/.github/actions/install-openvino/install.sh b/.github/actions/install-openvino/install.sh
index 16e523385..b96ab5bd6 100755
--- a/.github/actions/install-openvino/install.sh
+++ b/.github/actions/install-openvino/install.sh
@@ -2,15 +2,23 @@
 
 set -e
 
+if [ "$#" -ne 1 ]; then
+    version="2020.4.287"
+else
+    version="$1"
+fi
+
+scriptdir="$( cd "$( dirname "${BASH_SOURCE[0]}" )" >/dev/null 2>&1 && pwd )"
+
 # Retrieve OpenVINO checksum.
-wget https://apt.repos.intel.com/openvino/2020/GPG-PUB-KEY-INTEL-OPENVINO-2020
-echo '5f5cff8a2d26ba7de91942bd0540fa4d  GPG-PUB-KEY-INTEL-OPENVINO-2020' > CHECKSUM
-md5sum --check CHECKSUM
+curl -sSL https://apt.repos.intel.com/openvino/2020/GPG-PUB-KEY-INTEL-OPENVINO-2020 > $scriptdir/GPG-PUB-KEY-INTEL-OPENVINO-2020
+echo "5f5cff8a2d26ba7de91942bd0540fa4d $scriptdir/GPG-PUB-KEY-INTEL-OPENVINO-2020" > $scriptdir/CHECKSUM
+md5sum --check $scriptdir/CHECKSUM
 
 # Add OpenVINO repository (deb).
-sudo apt-key add GPG-PUB-KEY-INTEL-OPENVINO-2020
+sudo apt-key add $scriptdir/GPG-PUB-KEY-INTEL-OPENVINO-2020
 echo "deb https://apt.repos.intel.com/openvino/2020 all main" | sudo tee /etc/apt/sources.list.d/intel-openvino-2020.list
 sudo apt update
 
 # Install OpenVINO package.
-sudo apt install -y intel-openvino-runtime-ubuntu18-$1
+sudo apt install -y intel-openvino-runtime-ubuntu18-$version
diff --git a/Cargo.lock b/Cargo.lock
index 46384b2d6..542b28795 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -2680,6 +2680,7 @@ dependencies = [
  "wasmtime",
  "wasmtime-wiggle-macro",
  "wiggle",
+ "wiggle-borrow",
  "witx",
 ]
 
@@ -2752,6 +2753,13 @@ dependencies = [
  "witx",
 ]
 
+[[package]]
+name = "wiggle-borrow"
+version = "0.21.0"
+dependencies = [
+ "wiggle",
+]
+
 [[package]]
 name = "wiggle-generate"
 version = "0.21.0"
@@ -2778,7 +2786,7 @@ dependencies = [
 
 [[package]]
 name = "wiggle-test"
-version = "0.19.0"
+version = "0.21.0"
 dependencies = [
  "env_logger 0.8.1",
  "proptest",
@@ -2786,6 +2794,7 @@ dependencies = [
  "tracing",
  "tracing-subscriber",
  "wiggle",
+ "wiggle-borrow",
 ]
 
 [[package]]
diff --git a/crates/wasi-common/src/snapshots/wasi_snapshot_preview1.rs b/crates/wasi-common/src/snapshots/wasi_snapshot_preview1.rs
index 15dc7e310..4002a58d4 100644
--- a/crates/wasi-common/src/snapshots/wasi_snapshot_preview1.rs
+++ b/crates/wasi-common/src/snapshots/wasi_snapshot_preview1.rs
@@ -8,7 +8,7 @@ use std::convert::TryInto;
 use std::io::{self, SeekFrom};
 use std::ops::Deref;
 use tracing::{debug, trace};
-use wiggle::{GuestPtr, GuestSlice};
+use wiggle::{GuestPtr, GuestSliceMut};
 
 impl<'a> WasiSnapshotPreview1 for WasiCtx {
     fn args_get<'b>(
@@ -159,11 +159,11 @@ impl<'a> WasiSnapshotPreview1 for WasiCtx {
         iovs: &types::IovecArray<'_>,
         offset: types::Filesize,
     ) -> Result<types::Size> {
-        let mut guest_slices: Vec<GuestSlice<'_, u8>> = Vec::new();
+        let mut guest_slices: Vec<GuestSliceMut<'_, u8>> = Vec::new();
         for iov_ptr in iovs.iter() {
             let iov_ptr = iov_ptr?;
             let iov: types::Iovec = iov_ptr.read()?;
-            guest_slices.push(iov.buf.as_array(iov.buf_len).as_slice()?);
+            guest_slices.push(iov.buf.as_array(iov.buf_len).as_slice_mut()?);
         }
 
         let required_rights =
@@ -266,7 +266,7 @@ impl<'a> WasiSnapshotPreview1 for WasiCtx {
         for iov_ptr in iovs.iter() {
             let iov_ptr = iov_ptr?;
             let iov: types::Iovec = iov_ptr.read()?;
-            guest_slices.push(iov.buf.as_array(iov.buf_len).as_slice()?);
+            guest_slices.push(iov.buf.as_array(iov.buf_len).as_slice_mut()?);
         }
 
         let required_rights = HandleRights::from_base(types::Rights::FD_READ);
@@ -567,7 +567,7 @@ impl<'a> WasiSnapshotPreview1 for WasiCtx {
                 false,
             )?
         };
-        let mut slice = buf.as_array(buf_len).as_slice()?;
+        let mut slice = buf.as_array(buf_len).as_slice_mut()?;
         let host_bufused = dirfd.readlink(&path, &mut *slice)?.try_into()?;
         Ok(host_bufused)
     }
@@ -800,7 +800,7 @@ impl<'a> WasiSnapshotPreview1 for WasiCtx {
     }
 
     fn random_get(&self, buf: &GuestPtr<u8>, buf_len: types::Size) -> Result<()> {
-        let mut slice = buf.as_array(buf_len).as_slice()?;
+        let mut slice = buf.as_array(buf_len).as_slice_mut()?;
         getrandom::getrandom(&mut *slice)?;
         Ok(())
     }
diff --git a/crates/wasi-nn/src/impl.rs b/crates/wasi-nn/src/impl.rs
index a8828c1fe..fb8e781dd 100644
--- a/crates/wasi-nn/src/impl.rs
+++ b/crates/wasi-nn/src/impl.rs
@@ -158,7 +158,7 @@ impl<'a> WasiEphemeralNn for WasiNnCtx {
             };
 
         // Copy the tensor data over to the `out_buffer`.
-        let mut out_slice = out_buffer.as_array(out_buffer_max_size).as_slice()?;
+        let mut out_slice = out_buffer.as_array(out_buffer_max_size).as_slice_mut()?;
         (&mut out_slice[..blob_size as usize]).copy_from_slice(blob.buffer()?);
 
         Ok(blob_size)
diff --git a/crates/wiggle/borrow/Cargo.toml b/crates/wiggle/borrow/Cargo.toml
new file mode 100644
index 000000000..4c029c900
--- /dev/null
+++ b/crates/wiggle/borrow/Cargo.toml
@@ -0,0 +1,17 @@
+[package]
+name = "wiggle-borrow"
+version = "0.21.0"
+authors = ["Pat Hickey <phickey@fastly.com>", "Jakub Konka <kubkonk@jakubkonka.com>", "Alex Crichton <alex@alexcrichton.com>"]
+edition = "2018"
+license = "Apache-2.0 WITH LLVM-exception"
+description = "A run-time borrow checker for use with Wiggle"
+categories = ["wasm"]
+keywords = ["webassembly", "wasm"]
+repository = "https://github.com/bytecodealliance/wasmtime"
+include = ["src/**/*", "LICENSE"]
+
+[dependencies]
+wiggle = { path = "..", version = "0.21.0" }
+
+[badges]
+maintenance = { status = "actively-developed" }
diff --git a/crates/wiggle/borrow/src/lib.rs b/crates/wiggle/borrow/src/lib.rs
new file mode 100644
index 000000000..35266b607
--- /dev/null
+++ b/crates/wiggle/borrow/src/lib.rs
@@ -0,0 +1,249 @@
+use std::cell::RefCell;
+use std::collections::HashMap;
+use wiggle::{BorrowHandle, GuestError, Region};
+
+pub struct BorrowChecker {
+    /// Unfortunately, since the terminology of std::cell and the problem domain of borrow checking
+    /// overlap, the method calls on this member will be confusing.
+    bc: RefCell<InnerBorrowChecker>,
+}
+
+impl BorrowChecker {
+    /// A `BorrowChecker` manages run-time validation of borrows from a
+    /// `GuestMemory`. It keeps track of regions of guest memory which are
+    /// possible to alias with Rust references (via the `GuestSlice` and
+    /// `GuestStr` structs, which implement `std::ops::Deref` and
+    /// `std::ops::DerefMut`. It also enforces that `GuestPtr::read`
+    /// does not access memory with an outstanding mutable borrow, and
+    /// `GuestPtr::write` does not access memory with an outstanding
+    /// shared or mutable borrow.
+    pub fn new() -> Self {
+        BorrowChecker {
+            bc: RefCell::new(InnerBorrowChecker::new()),
+        }
+    }
+    /// Indicates whether any outstanding shared or mutable borrows are known
+    /// to the `BorrowChecker`. This function must be `false` in order for it
+    /// to be safe to recursively call into a WebAssembly module, or to
+    /// manipulate the WebAssembly memory by any other means.
+    pub fn has_outstanding_borrows(&self) -> bool {
+        self.bc.borrow().has_outstanding_borrows()
+    }
+    pub fn shared_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
+        self.bc.borrow_mut().shared_borrow(r)
+    }
+    pub fn mut_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
+        self.bc.borrow_mut().mut_borrow(r)
+    }
+    pub fn shared_unborrow(&self, h: BorrowHandle) {
+        self.bc.borrow_mut().shared_unborrow(h)
+    }
+    pub fn mut_unborrow(&self, h: BorrowHandle) {
+        self.bc.borrow_mut().mut_unborrow(h)
+    }
+    pub fn is_shared_borrowed(&self, r: Region) -> bool {
+        self.bc.borrow().is_shared_borrowed(r)
+    }
+    pub fn is_mut_borrowed(&self, r: Region) -> bool {
+        self.bc.borrow().is_mut_borrowed(r)
+    }
+}
+
+#[derive(Debug)]
+/// This is a pretty naive way to account for borrows. This datastructure
+/// could be made a lot more efficient with some effort.
+struct InnerBorrowChecker {
+    /// Maps from handle to region borrowed. A HashMap is probably not ideal
+    /// for this but it works. It would be more efficient if we could
+    /// check `is_borrowed` without an O(n) iteration, by organizing borrows
+    /// by an ordering of Region.
+    shared_borrows: HashMap<BorrowHandle, Region>,
+    mut_borrows: HashMap<BorrowHandle, Region>,
+    /// Handle to give out for the next borrow. This is the bare minimum of
+    /// bookkeeping of free handles, and in a pathological case we could run
+    /// out, hence [`GuestError::BorrowCheckerOutOfHandles`]
+    next_handle: BorrowHandle,
+}
+
+impl InnerBorrowChecker {
+    fn new() -> Self {
+        InnerBorrowChecker {
+            shared_borrows: HashMap::new(),
+            mut_borrows: HashMap::new(),
+            next_handle: BorrowHandle(0),
+        }
+    }
+
+    fn has_outstanding_borrows(&self) -> bool {
+        !(self.shared_borrows.is_empty() && self.mut_borrows.is_empty())
+    }
+
+    fn is_shared_borrowed(&self, r: Region) -> bool {
+        self.shared_borrows.values().any(|b| b.overlaps(r))
+    }
+    fn is_mut_borrowed(&self, r: Region) -> bool {
+        self.mut_borrows.values().any(|b| b.overlaps(r))
+    }
+
+    fn new_handle(&mut self) -> Result<BorrowHandle, GuestError> {
+        // Reset handles to 0 if all handles have been returned.
+        if self.shared_borrows.is_empty() && self.mut_borrows.is_empty() {
+            self.next_handle = BorrowHandle(0);
+        }
+        let h = self.next_handle;
+        // Get the next handle. Since we don't recycle handles until all of
+        // them have been returned, there is a pathological case where a user
+        // may make a Very Large (usize::MAX) number of valid borrows and
+        // unborrows while always keeping at least one borrow outstanding, and
+        // we will run out of borrow handles.
+        self.next_handle = BorrowHandle(
+            h.0.checked_add(1)
+                .ok_or_else(|| GuestError::BorrowCheckerOutOfHandles)?,
+        );
+        Ok(h)
+    }
+
+    fn shared_borrow(&mut self, r: Region) -> Result<BorrowHandle, GuestError> {
+        if self.is_mut_borrowed(r) {
+            return Err(GuestError::PtrBorrowed(r));
+        }
+        let h = self.new_handle()?;
+        self.shared_borrows.insert(h, r);
+        Ok(h)
+    }
+
+    fn mut_borrow(&mut self, r: Region) -> Result<BorrowHandle, GuestError> {
+        if self.is_shared_borrowed(r) || self.is_mut_borrowed(r) {
+            return Err(GuestError::PtrBorrowed(r));
+        }
+        let h = self.new_handle()?;
+        self.mut_borrows.insert(h, r);
+        Ok(h)
+    }
+
+    fn shared_unborrow(&mut self, h: BorrowHandle) {
+        let removed = self.shared_borrows.remove(&h);
+        debug_assert!(removed.is_some(), "double-freed shared borrow");
+    }
+
+    fn mut_unborrow(&mut self, h: BorrowHandle) {
+        let removed = self.mut_borrows.remove(&h);
+        debug_assert!(removed.is_some(), "double-freed mut borrow");
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+    #[test]
+    fn nonoverlapping() {
+        let mut bs = InnerBorrowChecker::new();
+        let r1 = Region::new(0, 10);
+        let r2 = Region::new(10, 10);
+        assert!(!r1.overlaps(r2));
+        bs.mut_borrow(r1).expect("can borrow r1");
+        bs.mut_borrow(r2).expect("can borrow r2");
+
+        let mut bs = InnerBorrowChecker::new();
+        let r1 = Region::new(10, 10);
+        let r2 = Region::new(0, 10);
+        assert!(!r1.overlaps(r2));
+        bs.mut_borrow(r1).expect("can borrow r1");
+        bs.mut_borrow(r2).expect("can borrow r2");
+    }
+
+    #[test]
+    fn overlapping() {
+        let mut bs = InnerBorrowChecker::new();
+        let r1 = Region::new(0, 10);
+        let r2 = Region::new(9, 10);
+        assert!(r1.overlaps(r2));
+        bs.shared_borrow(r1).expect("can borrow r1");
+        assert!(bs.mut_borrow(r2).is_err(), "cant mut borrow r2");
+        bs.shared_borrow(r2).expect("can shared borrow r2");
+
+        let mut bs = InnerBorrowChecker::new();
+        let r1 = Region::new(0, 10);
+        let r2 = Region::new(2, 5);
+        assert!(r1.overlaps(r2));
+        bs.shared_borrow(r1).expect("can borrow r1");
+        assert!(bs.mut_borrow(r2).is_err(), "cant borrow r2");
+        bs.shared_borrow(r2).expect("can shared borrow r2");
+
+        let mut bs = InnerBorrowChecker::new();
+        let r1 = Region::new(9, 10);
+        let r2 = Region::new(0, 10);
+        assert!(r1.overlaps(r2));
+        bs.shared_borrow(r1).expect("can borrow r1");
+        assert!(bs.mut_borrow(r2).is_err(), "cant borrow r2");
+        bs.shared_borrow(r2).expect("can shared borrow r2");
+
+        let mut bs = InnerBorrowChecker::new();
+        let r1 = Region::new(2, 5);
+        let r2 = Region::new(0, 10);
+        assert!(r1.overlaps(r2));
+        bs.shared_borrow(r1).expect("can borrow r1");
+        assert!(bs.mut_borrow(r2).is_err(), "cant borrow r2");
+        bs.shared_borrow(r2).expect("can shared borrow r2");
+
+        let mut bs = InnerBorrowChecker::new();
+        let r1 = Region::new(2, 5);
+        let r2 = Region::new(10, 5);
+        let r3 = Region::new(15, 5);
+        let r4 = Region::new(0, 10);
+        assert!(r1.overlaps(r4));
+        bs.shared_borrow(r1).expect("can borrow r1");
+        bs.shared_borrow(r2).expect("can borrow r2");
+        bs.shared_borrow(r3).expect("can borrow r3");
+        assert!(bs.mut_borrow(r4).is_err(), "cant mut borrow r4");
+        bs.shared_borrow(r4).expect("can shared borrow r4");
+    }
+
+    #[test]
+    fn unborrowing() {
+        let mut bs = InnerBorrowChecker::new();
+        let r1 = Region::new(0, 10);
+        let r2 = Region::new(10, 10);
+        assert!(!r1.overlaps(r2));
+        assert_eq!(bs.has_outstanding_borrows(), false, "start with no borrows");
+        let h1 = bs.mut_borrow(r1).expect("can borrow r1");
+        assert_eq!(bs.has_outstanding_borrows(), true, "h1 is outstanding");
+        let h2 = bs.mut_borrow(r2).expect("can borrow r2");
+
+        assert!(bs.mut_borrow(r2).is_err(), "can't borrow r2 twice");
+        bs.mut_unborrow(h2);
+        assert_eq!(
+            bs.has_outstanding_borrows(),
+            true,
+            "h1 is still outstanding"
+        );
+        bs.mut_unborrow(h1);
+        assert_eq!(bs.has_outstanding_borrows(), false, "no remaining borrows");
+
+        let _h3 = bs
+            .mut_borrow(r2)
+            .expect("can borrow r2 again now that its been unborrowed");
+
+        // Lets try again with shared:
+
+        let mut bs = InnerBorrowChecker::new();
+        let r1 = Region::new(0, 10);
+        let r2 = Region::new(10, 10);
+        assert!(!r1.overlaps(r2));
+        assert_eq!(bs.has_outstanding_borrows(), false, "start with no borrows");
+        let h1 = bs.shared_borrow(r1).expect("can borrow r1");
+        assert_eq!(bs.has_outstanding_borrows(), true, "h1 is outstanding");
+        let h2 = bs.shared_borrow(r2).expect("can borrow r2");
+        let h3 = bs.shared_borrow(r2).expect("can shared borrow r2 twice");
+
+        bs.shared_unborrow(h2);
+        assert_eq!(
+            bs.has_outstanding_borrows(),
+            true,
+            "h1, h3 still outstanding"
+        );
+        bs.shared_unborrow(h1);
+        bs.shared_unborrow(h3);
+        assert_eq!(bs.has_outstanding_borrows(), false, "no remaining borrows");
+    }
+}
diff --git a/crates/wiggle/src/guest_type.rs b/crates/wiggle/src/guest_type.rs
index 422c3f239..0fae52491 100644
--- a/crates/wiggle/src/guest_type.rs
+++ b/crates/wiggle/src/guest_type.rs
@@ -85,7 +85,7 @@ macro_rules! primitives {
                     start: offset,
                     len: size,
                 };
-                if ptr.mem().is_borrowed(region) {
+                if ptr.mem().is_mut_borrowed(region) {
                     return Err(GuestError::PtrBorrowed(region));
                 }
                 Ok(unsafe { <$i>::from_le_bytes(*host_ptr.cast::<[u8; mem::size_of::<Self>()]>()) })
@@ -104,7 +104,7 @@ macro_rules! primitives {
                     start: offset,
                     len: size,
                 };
-                if ptr.mem().is_borrowed(region) {
+                if ptr.mem().is_shared_borrowed(region) || ptr.mem().is_mut_borrowed(region) {
                     return Err(GuestError::PtrBorrowed(region));
                 }
                 unsafe {
diff --git a/crates/wiggle/src/lib.rs b/crates/wiggle/src/lib.rs
index fe2b17249..063ab5bd4 100644
--- a/crates/wiggle/src/lib.rs
+++ b/crates/wiggle/src/lib.rs
@@ -153,27 +153,36 @@ pub unsafe trait GuestMemory {
     /// safe to recursively call into a WebAssembly module, or to manipulate
     /// the WebAssembly memory by any other means.
     fn has_outstanding_borrows(&self) -> bool;
-    /// Check if a region of linear memory is borrowed. This is called during
-    /// any `GuestPtr::read` or `GuestPtr::write` operation to ensure that
-    /// wiggle is not reading or writing a region of memory which Rust believes
-    /// it has exclusive access to.
-    fn is_borrowed(&self, r: Region) -> bool;
-    /// Borrow a region of linear memory. This is used when constructing a
-    /// `GuestSlice` or `GuestStr`. Those types will give Rust `&mut` access
+    /// Check if a region of linear memory is exclusively borrowed. This is called during any
+    /// `GuestPtr::read` or `GuestPtr::write` operation to ensure that wiggle is not reading or
+    /// writing a region of memory which Rust believes it has exclusive access to.
+    fn is_mut_borrowed(&self, r: Region) -> bool;
+    /// Check if a region of linear memory has any shared borrows.
+    fn is_shared_borrowed(&self, r: Region) -> bool;
+    /// Exclusively borrow a region of linear memory. This is used when constructing a
+    /// `GuestSliceMut` or `GuestStrMut`. Those types will give Rust `&mut` access
     /// to the region of linear memory, therefore, the `GuestMemory` impl must
     /// guarantee that at most one `BorrowHandle` is issued to a given region,
     /// `GuestMemory::has_outstanding_borrows` is true for the duration of the
-    /// borrow, and that `GuestMemory::is_borrowed` of any overlapping region
+    /// borrow, and that `GuestMemory::is_mut_borrowed` of any overlapping region
     /// is false for the duration of the borrow.
-    fn borrow(&self, r: Region) -> Result<BorrowHandle, GuestError>;
-    /// Unborrow a previously borrowed region. As long as `GuestSlice` and
-    /// `GuestStr` are implemented correctly, a `BorrowHandle` should only be
+    fn mut_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError>;
+    /// Shared borrow a region of linear memory. This is used when constructing a
+    /// `GuestSlice` or `GuestStr`. Those types will give Rust `&` (shared reference) access
+    /// to the region of linear memory.
+    fn shared_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError>;
+    /// Unborrow a previously borrowed mutable region. As long as `GuestSliceMut` and
+    /// `GuestStrMut` are implemented correctly, a mut `BorrowHandle` should only be
     /// unborrowed once.
-    fn unborrow(&self, h: BorrowHandle);
+    fn mut_unborrow(&self, h: BorrowHandle);
+    /// Unborrow a previously borrowed shared region. As long as `GuestSlice` and
+    /// `GuestStr` are implemented correctly, a shared `BorrowHandle` should only be
+    /// unborrowed once.
+    fn shared_unborrow(&self, h: BorrowHandle);
 }
 
-/// A handle to a borrow on linear memory. It is produced by `borrow` and
-/// consumed by `unborrow`. Only the `GuestMemory` impl should ever construct
+/// A handle to a borrow on linear memory. It is produced by `{mut, shared}_borrow` and
+/// consumed by `{mut, shared}_unborrow`. Only the `GuestMemory` impl should ever construct
 /// a `BorrowHandle` or inspect its contents.
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
 pub struct BorrowHandle(pub usize);
@@ -186,14 +195,23 @@ unsafe impl<'a, T: ?Sized + GuestMemory> GuestMemory for &'a T {
     fn has_outstanding_borrows(&self) -> bool {
         T::has_outstanding_borrows(self)
     }
-    fn is_borrowed(&self, r: Region) -> bool {
-        T::is_borrowed(self, r)
+    fn is_mut_borrowed(&self, r: Region) -> bool {
+        T::is_mut_borrowed(self, r)
+    }
+    fn is_shared_borrowed(&self, r: Region) -> bool {
+        T::is_shared_borrowed(self, r)
+    }
+    fn mut_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
+        T::mut_borrow(self, r)
+    }
+    fn shared_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
+        T::shared_borrow(self, r)
     }
-    fn borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
-        T::borrow(self, r)
+    fn mut_unborrow(&self, h: BorrowHandle) {
+        T::mut_unborrow(self, h)
     }
-    fn unborrow(&self, h: BorrowHandle) {
-        T::unborrow(self, h)
+    fn shared_unborrow(&self, h: BorrowHandle) {
+        T::shared_unborrow(self, h)
     }
 }
 
@@ -204,14 +222,23 @@ unsafe impl<'a, T: ?Sized + GuestMemory> GuestMemory for &'a mut T {
     fn has_outstanding_borrows(&self) -> bool {
         T::has_outstanding_borrows(self)
     }
-    fn is_borrowed(&self, r: Region) -> bool {
-        T::is_borrowed(self, r)
+    fn is_mut_borrowed(&self, r: Region) -> bool {
+        T::is_mut_borrowed(self, r)
     }
-    fn borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
-        T::borrow(self, r)
+    fn is_shared_borrowed(&self, r: Region) -> bool {
+        T::is_shared_borrowed(self, r)
     }
-    fn unborrow(&self, h: BorrowHandle) {
-        T::unborrow(self, h)
+    fn mut_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
+        T::mut_borrow(self, r)
+    }
+    fn shared_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
+        T::shared_borrow(self, r)
+    }
+    fn mut_unborrow(&self, h: BorrowHandle) {
+        T::mut_unborrow(self, h)
+    }
+    fn shared_unborrow(&self, h: BorrowHandle) {
+        T::shared_unborrow(self, h)
     }
 }
 
@@ -222,14 +249,23 @@ unsafe impl<T: ?Sized + GuestMemory> GuestMemory for Box<T> {
     fn has_outstanding_borrows(&self) -> bool {
         T::has_outstanding_borrows(self)
     }
-    fn is_borrowed(&self, r: Region) -> bool {
-        T::is_borrowed(self, r)
+    fn is_mut_borrowed(&self, r: Region) -> bool {
+        T::is_mut_borrowed(self, r)
+    }
+    fn is_shared_borrowed(&self, r: Region) -> bool {
+        T::is_shared_borrowed(self, r)
     }
-    fn borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
-        T::borrow(self, r)
+    fn mut_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
+        T::mut_borrow(self, r)
     }
-    fn unborrow(&self, h: BorrowHandle) {
-        T::unborrow(self, h)
+    fn shared_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
+        T::shared_borrow(self, r)
+    }
+    fn mut_unborrow(&self, h: BorrowHandle) {
+        T::mut_unborrow(self, h)
+    }
+    fn shared_unborrow(&self, h: BorrowHandle) {
+        T::shared_unborrow(self, h)
     }
 }
 
@@ -240,14 +276,23 @@ unsafe impl<T: ?Sized + GuestMemory> GuestMemory for Rc<T> {
     fn has_outstanding_borrows(&self) -> bool {
         T::has_outstanding_borrows(self)
     }
-    fn is_borrowed(&self, r: Region) -> bool {
-        T::is_borrowed(self, r)
+    fn is_mut_borrowed(&self, r: Region) -> bool {
+        T::is_mut_borrowed(self, r)
+    }
+    fn is_shared_borrowed(&self, r: Region) -> bool {
+        T::is_shared_borrowed(self, r)
+    }
+    fn mut_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
+        T::mut_borrow(self, r)
     }
-    fn borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
-        T::borrow(self, r)
+    fn shared_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
+        T::shared_borrow(self, r)
     }
-    fn unborrow(&self, h: BorrowHandle) {
-        T::unborrow(self, h)
+    fn mut_unborrow(&self, h: BorrowHandle) {
+        T::mut_unborrow(self, h)
+    }
+    fn shared_unborrow(&self, h: BorrowHandle) {
+        T::shared_unborrow(self, h)
     }
 }
 
@@ -258,14 +303,23 @@ unsafe impl<T: ?Sized + GuestMemory> GuestMemory for Arc<T> {
     fn has_outstanding_borrows(&self) -> bool {
         T::has_outstanding_borrows(self)
     }
-    fn is_borrowed(&self, r: Region) -> bool {
-        T::is_borrowed(self, r)
+    fn is_mut_borrowed(&self, r: Region) -> bool {
+        T::is_mut_borrowed(self, r)
+    }
+    fn is_shared_borrowed(&self, r: Region) -> bool {
+        T::is_shared_borrowed(self, r)
+    }
+    fn mut_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
+        T::mut_borrow(self, r)
+    }
+    fn shared_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
+        T::shared_borrow(self, r)
     }
-    fn borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
-        T::borrow(self, r)
+    fn mut_unborrow(&self, h: BorrowHandle) {
+        T::mut_unborrow(self, h)
     }
-    fn unborrow(&self, h: BorrowHandle) {
-        T::unborrow(self, h)
+    fn shared_unborrow(&self, h: BorrowHandle) {
+        T::shared_unborrow(self, h)
     }
 }
 
@@ -285,12 +339,14 @@ unsafe impl<T: ?Sized + GuestMemory> GuestMemory for Arc<T> {
 /// Note that the type parameter does not need to implement the `Sized` trait,
 /// so you can implement types such as this:
 ///
-/// * `GuestPtr<'_, str>` - a pointer to a guest string. Has the method
-///   [`GuestPtr::as_str`], which gives a dynamically borrow-checked
-///   `GuestStr<'_>`, which `DerefMut`s to a `&mut str`.
-/// * `GuestPtr<'_, [T]>` - a pointer to a guest array. Has the method
-///   [`GuestPtr::as_slice`], which gives a dynamically borrow-checked
-///   `GuestSlice<'_, T>`, which `DerefMut`s to a `&mut [T]`.
+/// * `GuestPtr<'_, str>` - a pointer to a guest string. Has the methods
+///   [`GuestPtr::as_str_mut`], which gives a dynamically borrow-checked
+///   `GuestStrMut<'_>`, which `DerefMut`s to a `&mut str`, and
+///   [`GuestPtr::as_str`], which is the sharedable version of same.
+/// * `GuestPtr<'_, [T]>` - a pointer to a guest array. Has methods
+///   [`GuestPtr::as_slice_mut`], which gives a dynamically borrow-checked
+///   `GuestSliceMut<'_, T>`, which `DerefMut`s to a `&mut [T]` and
+///   [`GuestPtr::as_slice`], which is the sharedable version of same.
 ///
 /// Unsized types such as this may have extra methods and won't have methods
 /// like [`GuestPtr::read`] or [`GuestPtr::write`].
@@ -470,14 +526,58 @@ impl<'a, T> GuestPtr<'a, [T]> {
 
     /// Attempts to create a [`GuestSlice<'_, T>`] from this pointer, performing
     /// bounds checks and type validation. The `GuestSlice` is a smart pointer
+    /// that can be used as a `&[T]` via the `Deref` trait.
+    /// The region of memory backing the slice will be marked as sharedably
+    /// borrowed by the [`GuestMemory`] until the `GuestSlice` is dropped.
+    /// Multiple sharedable borrows of the same memory are permitted, but only
+    /// one mutable borrow.
+    ///
+    /// This function will return a `GuestSlice` into host memory if all checks
+    /// succeed (valid utf-8, valid pointers, memory is not borrowed, etc). If
+    /// any checks fail then `GuestError` will be returned.
+    pub fn as_slice(&self) -> Result<GuestSlice<'a, T>, GuestError>
+    where
+        T: GuestTypeTransparent<'a>,
+    {
+        let len = match self.pointer.1.checked_mul(T::guest_size()) {
+            Some(l) => l,
+            None => return Err(GuestError::PtrOverflow),
+        };
+        let ptr =
+            self.mem
+                .validate_size_align(self.pointer.0, T::guest_align(), len)? as *mut T;
+
+        let borrow = self.mem.shared_borrow(Region {
+            start: self.pointer.0,
+            len,
+        })?;
+
+        // Validate all elements in slice.
+        // SAFETY: ptr has been validated by self.mem.validate_size_align
+        for offs in 0..self.pointer.1 {
+            T::validate(unsafe { ptr.add(offs as usize) })?;
+        }
+
+        // SAFETY: iff there are no overlapping mut borrows it is valid to construct a &[T]
+        let ptr = unsafe { slice::from_raw_parts(ptr, self.pointer.1 as usize) };
+
+        Ok(GuestSlice {
+            ptr,
+            mem: self.mem,
+            borrow,
+        })
+    }
+
+    /// Attempts to create a [`GuestSliceMut<'_, T>`] from this pointer, performing
+    /// bounds checks and type validation. The `GuestSliceMut` is a smart pointer
     /// that can be used as a `&[T]` or a `&mut [T]` via the `Deref` and `DerefMut`
     /// traits. The region of memory backing the slice will be marked as borrowed
     /// by the [`GuestMemory`] until the `GuestSlice` is dropped.
     ///
-    /// This function will return a `GuestSlice` into host memory if all checks
+    /// This function will return a `GuestSliceMut` into host memory if all checks
     /// succeed (valid utf-8, valid pointers, memory is not borrowed, etc). If
     /// any checks fail then `GuestError` will be returned.
-    pub fn as_slice(&self) -> Result<GuestSlice<'a, T>, GuestError>
+    pub fn as_slice_mut(&self) -> Result<GuestSliceMut<'a, T>, GuestError>
     where
         T: GuestTypeTransparent<'a>,
     {
@@ -489,7 +589,7 @@ impl<'a, T> GuestPtr<'a, [T]> {
             self.mem
                 .validate_size_align(self.pointer.0, T::guest_align(), len)? as *mut T;
 
-        let borrow = self.mem.borrow(Region {
+        let borrow = self.mem.mut_borrow(Region {
             start: self.pointer.0,
             len,
         })?;
@@ -503,7 +603,7 @@ impl<'a, T> GuestPtr<'a, [T]> {
         // SAFETY: iff there are no overlapping borrows it is valid to construct a &mut [T]
         let ptr = unsafe { slice::from_raw_parts_mut(ptr, self.pointer.1 as usize) };
 
-        Ok(GuestSlice {
+        Ok(GuestSliceMut {
             ptr,
             mem: self.mem,
             borrow,
@@ -527,7 +627,7 @@ impl<'a, T> GuestPtr<'a, [T]> {
         T: GuestTypeTransparent<'a> + Copy,
     {
         // bounds check ...
-        let mut self_slice = self.as_slice()?;
+        let mut self_slice = self.as_slice_mut()?;
         // ... length check ...
         if self_slice.len() != slice.len() {
             return Err(GuestError::SliceLengthsDiffer);
@@ -605,9 +705,9 @@ impl<'a> GuestPtr<'a, str> {
 
     /// Attempts to create a [`GuestStr<'_>`] from this pointer, performing
     /// bounds checks and utf-8 checks. The resulting `GuestStr` can be used
-    /// as a `&str` or `&mut str` via the `Deref` and `DerefMut` traits. The
-    /// region of memory backing the `str` will be marked as borrowed by the
-    /// [`GuestMemory`] until the `GuestStr` is dropped.
+    /// as a `&str` via the `Deref` trait. The region of memory backing the
+    /// `str` will be marked as sharedably borrowed by the [`GuestMemory`]
+    /// until the `GuestStr` is dropped.
     ///
     /// This function will return `GuestStr` into host memory if all checks
     /// succeed (valid utf-8, valid pointers, etc). If any checks fail then
@@ -617,7 +717,40 @@ impl<'a> GuestPtr<'a, str> {
             .mem
             .validate_size_align(self.pointer.0, 1, self.pointer.1)?;
 
-        let borrow = self.mem.borrow(Region {
+        let borrow = self.mem.shared_borrow(Region {
+            start: self.pointer.0,
+            len: self.pointer.1,
+        })?;
+
+        // SAFETY: iff there are no overlapping borrows it is ok to construct
+        // a &mut str.
+        let ptr = unsafe { slice::from_raw_parts(ptr, self.pointer.1 as usize) };
+        // Validate that contents are utf-8:
+        match str::from_utf8(ptr) {
+            Ok(ptr) => Ok(GuestStr {
+                ptr,
+                mem: self.mem,
+                borrow,
+            }),
+            Err(e) => Err(GuestError::InvalidUtf8(e)),
+        }
+    }
+
+    /// Attempts to create a [`GuestStrMut<'_>`] from this pointer, performing
+    /// bounds checks and utf-8 checks. The resulting `GuestStrMut` can be used
+    /// as a `&str` or `&mut str` via the `Deref` and `DerefMut` traits. The
+    /// region of memory backing the `str` will be marked as borrowed by the
+    /// [`GuestMemory`] until the `GuestStrMut` is dropped.
+    ///
+    /// This function will return `GuestStrMut` into host memory if all checks
+    /// succeed (valid utf-8, valid pointers, etc). If any checks fail then
+    /// `GuestError` will be returned.
+    pub fn as_str_mut(&self) -> Result<GuestStrMut<'a>, GuestError> {
+        let ptr = self
+            .mem
+            .validate_size_align(self.pointer.0, 1, self.pointer.1)?;
+
+        let borrow = self.mem.mut_borrow(Region {
             start: self.pointer.0,
             len: self.pointer.1,
         })?;
@@ -627,7 +760,7 @@ impl<'a> GuestPtr<'a, str> {
         let ptr = unsafe { slice::from_raw_parts_mut(ptr, self.pointer.1 as usize) };
         // Validate that contents are utf-8:
         match str::from_utf8_mut(ptr) {
-            Ok(ptr) => Ok(GuestStr {
+            Ok(ptr) => Ok(GuestStrMut {
                 ptr,
                 mem: self.mem,
                 borrow,
@@ -659,59 +792,101 @@ impl<T: ?Sized + Pointee> fmt::Debug for GuestPtr<'_, T> {
     }
 }
 
+/// A smart pointer to an sharedable slice in guest memory.
+/// Usable as a `&'a [T]` via [`std::ops::Deref`].
+pub struct GuestSlice<'a, T> {
+    ptr: &'a [T],
+    mem: &'a dyn GuestMemory,
+    borrow: BorrowHandle,
+}
+
+impl<'a, T> std::ops::Deref for GuestSlice<'a, T> {
+    type Target = [T];
+    fn deref(&self) -> &Self::Target {
+        self.ptr
+    }
+}
+
+impl<'a, T> Drop for GuestSlice<'a, T> {
+    fn drop(&mut self) {
+        self.mem.shared_unborrow(self.borrow)
+    }
+}
+
 /// A smart pointer to a mutable slice in guest memory.
 /// Usable as a `&'a [T]` via [`std::ops::Deref`] and as a `&'a mut [T]` via
 /// [`std::ops::DerefMut`].
-pub struct GuestSlice<'a, T> {
+pub struct GuestSliceMut<'a, T> {
     ptr: &'a mut [T],
     mem: &'a dyn GuestMemory,
     borrow: BorrowHandle,
 }
 
-impl<'a, T> std::ops::Deref for GuestSlice<'a, T> {
+impl<'a, T> std::ops::Deref for GuestSliceMut<'a, T> {
     type Target = [T];
     fn deref(&self) -> &Self::Target {
         self.ptr
     }
 }
 
-impl<'a, T> std::ops::DerefMut for GuestSlice<'a, T> {
+impl<'a, T> std::ops::DerefMut for GuestSliceMut<'a, T> {
     fn deref_mut(&mut self) -> &mut Self::Target {
         self.ptr
     }
 }
 
-impl<'a, T> Drop for GuestSlice<'a, T> {
+impl<'a, T> Drop for GuestSliceMut<'a, T> {
+    fn drop(&mut self) {
+        self.mem.mut_unborrow(self.borrow)
+    }
+}
+
+/// A smart pointer to an sharedable `str` in guest memory.
+/// Usable as a `&'a str` via [`std::ops::Deref`].
+pub struct GuestStr<'a> {
+    ptr: &'a str,
+    mem: &'a dyn GuestMemory,
+    borrow: BorrowHandle,
+}
+
+impl<'a> std::ops::Deref for GuestStr<'a> {
+    type Target = str;
+    fn deref(&self) -> &Self::Target {
+        self.ptr
+    }
+}
+
+impl<'a> Drop for GuestStr<'a> {
     fn drop(&mut self) {
-        self.mem.unborrow(self.borrow)
+        self.mem.shared_unborrow(self.borrow)
     }
 }
 
 /// A smart pointer to a mutable `str` in guest memory.
 /// Usable as a `&'a str` via [`std::ops::Deref`] and as a `&'a mut str` via
 /// [`std::ops::DerefMut`].
-pub struct GuestStr<'a> {
+pub struct GuestStrMut<'a> {
     ptr: &'a mut str,
     mem: &'a dyn GuestMemory,
     borrow: BorrowHandle,
 }
 
-impl<'a> std::ops::Deref for GuestStr<'a> {
+impl<'a> std::ops::Deref for GuestStrMut<'a> {
     type Target = str;
     fn deref(&self) -> &Self::Target {
         self.ptr
     }
 }
 
-impl<'a> std::ops::DerefMut for GuestStr<'a> {
+impl<'a> std::ops::DerefMut for GuestStrMut<'a> {
     fn deref_mut(&mut self) -> &mut Self::Target {
         self.ptr
     }
 }
 
-impl<'a> Drop for GuestStr<'a> {
+impl<'a> Drop for GuestStrMut<'a> {
     fn drop(&mut self) {
-        self.mem.unborrow(self.borrow)
+        self.mem.mut_unborrow(self.borrow)
     }
 }
 
diff --git a/crates/wiggle/wasmtime/Cargo.toml b/crates/wiggle/wasmtime/Cargo.toml
index 89a85970c..87da0c32f 100644
--- a/crates/wiggle/wasmtime/Cargo.toml
+++ b/crates/wiggle/wasmtime/Cargo.toml
@@ -15,6 +15,7 @@ wasmtime = { path = "../../wasmtime", version = "0.21.0", default-features = fal
 wasmtime-wiggle-macro = { path = "./macro", version = "0.21.0" }
 witx = { path = "../../wasi-common/WASI/tools/witx", version = "0.8.7", optional = true }
 wiggle = { path = "..", version = "0.21.0" }
+wiggle-borrow = { path = "../borrow", version = "0.21.0" }
 
 [badges]
 maintenance = { status = "actively-developed" }
diff --git a/crates/wiggle/wasmtime/src/borrow.rs b/crates/wiggle/wasmtime/src/borrow.rs
deleted file mode 100644
index 5ed16e271..000000000
--- a/crates/wiggle/wasmtime/src/borrow.rs
+++ /dev/null
@@ -1,188 +0,0 @@
-use std::cell::RefCell;
-use std::collections::HashMap;
-use wiggle::{BorrowHandle, GuestError, Region};
-
-pub struct BorrowChecker {
-    bc: RefCell<InnerBorrowChecker>,
-}
-
-impl BorrowChecker {
-    /// A `BorrowChecker` manages run-time validation of borrows from a `GuestMemory`. It keeps
-    /// track of regions of guest memory which are possible to alias with Rust references (via the
-    /// `GuestSlice` and `GuestStr` structs, which implement `std::ops::Deref` and
-    /// `std::ops::DerefMut`. It also enforces that `GuestPtr::read` and `GuestPtr::write` do not
-    /// access memory with an outstanding borrow.
-    pub fn new() -> Self {
-        BorrowChecker {
-            bc: RefCell::new(InnerBorrowChecker::new()),
-        }
-    }
-    /// Indicates whether any outstanding borrows are known to the `BorrowChecker`. This function
-    /// must be `false` in order for it to be safe to recursively call into a WebAssembly module,
-    /// or to manipulate the WebAssembly memory by any other means.
-    pub fn has_outstanding_borrows(&self) -> bool {
-        self.bc.borrow().has_outstanding_borrows()
-    }
-
-    pub(crate) fn borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
-        self.bc.borrow_mut().borrow(r)
-    }
-    pub(crate) fn unborrow(&self, h: BorrowHandle) {
-        self.bc.borrow_mut().unborrow(h)
-    }
-    pub(crate) fn is_borrowed(&self, r: Region) -> bool {
-        self.bc.borrow().is_borrowed(r)
-    }
-}
-
-#[derive(Debug)]
-/// This is a pretty naive way to account for borrows. This datastructure
-/// could be made a lot more efficient with some effort.
-struct InnerBorrowChecker {
-    /// Map from handle to region borrowed. A HashMap is probably not ideal
-    /// for this but it works. It would be more efficient if we could
-    /// check `is_borrowed` without an O(n) iteration, by organizing borrows
-    /// by an ordering of Region.
-    borrows: HashMap<BorrowHandle, Region>,
-    /// Handle to give out for the next borrow. This is the bare minimum of
-    /// bookkeeping of free handles, and in a pathological case we could run
-    /// out, hence [`GuestError::BorrowCheckerOutOfHandles`]
-    next_handle: BorrowHandle,
-}
-
-impl InnerBorrowChecker {
-    fn new() -> Self {
-        InnerBorrowChecker {
-            borrows: HashMap::new(),
-            next_handle: BorrowHandle(0),
-        }
-    }
-
-    fn has_outstanding_borrows(&self) -> bool {
-        !self.borrows.is_empty()
-    }
-
-    fn is_borrowed(&self, r: Region) -> bool {
-        !self.borrows.values().all(|b| !b.overlaps(r))
-    }
-
-    fn new_handle(&mut self) -> Result<BorrowHandle, GuestError> {
-        // Reset handles to 0 if all handles have been returned.
-        if self.borrows.is_empty() {
-            self.next_handle = BorrowHandle(0);
-        }
-        let h = self.next_handle;
-        // Get the next handle. Since we don't recycle handles until all of
-        // them have been returned, there is a pathological case where a user
-        // may make a Very Large (usize::MAX) number of valid borrows and
-        // unborrows while always keeping at least one borrow outstanding, and
-        // we will run out of borrow handles.
-        self.next_handle = BorrowHandle(
-            h.0.checked_add(1)
-                .ok_or_else(|| GuestError::BorrowCheckerOutOfHandles)?,
-        );
-        Ok(h)
-    }
-
-    fn borrow(&mut self, r: Region) -> Result<BorrowHandle, GuestError> {
-        if self.is_borrowed(r) {
-            return Err(GuestError::PtrBorrowed(r));
-        }
-        let h = self.new_handle()?;
-        self.borrows.insert(h, r);
-        Ok(h)
-    }
-
-    fn unborrow(&mut self, h: BorrowHandle) {
-        let _ = self.borrows.remove(&h);
-    }
-}
-
-#[cfg(test)]
-mod test {
-    use super::*;
-    #[test]
-    fn nonoverlapping() {
-        let mut bs = InnerBorrowChecker::new();
-        let r1 = Region::new(0, 10);
-        let r2 = Region::new(10, 10);
-        assert!(!r1.overlaps(r2));
-        bs.borrow(r1).expect("can borrow r1");
-        bs.borrow(r2).expect("can borrow r2");
-
-        let mut bs = InnerBorrowChecker::new();
-        let r1 = Region::new(10, 10);
-        let r2 = Region::new(0, 10);
-        assert!(!r1.overlaps(r2));
-        bs.borrow(r1).expect("can borrow r1");
-        bs.borrow(r2).expect("can borrow r2");
-    }
-
-    #[test]
-    fn overlapping() {
-        let mut bs = InnerBorrowChecker::new();
-        let r1 = Region::new(0, 10);
-        let r2 = Region::new(9, 10);
-        assert!(r1.overlaps(r2));
-        bs.borrow(r1).expect("can borrow r1");
-        assert!(bs.borrow(r2).is_err(), "cant borrow r2");
-
-        let mut bs = InnerBorrowChecker::new();
-        let r1 = Region::new(0, 10);
-        let r2 = Region::new(2, 5);
-        assert!(r1.overlaps(r2));
-        bs.borrow(r1).expect("can borrow r1");
-        assert!(bs.borrow(r2).is_err(), "cant borrow r2");
-
-        let mut bs = InnerBorrowChecker::new();
-        let r1 = Region::new(9, 10);
-        let r2 = Region::new(0, 10);
-        assert!(r1.overlaps(r2));
-        bs.borrow(r1).expect("can borrow r1");
-        assert!(bs.borrow(r2).is_err(), "cant borrow r2");
-
-        let mut bs = InnerBorrowChecker::new();
-        let r1 = Region::new(2, 5);
-        let r2 = Region::new(0, 10);
-        assert!(r1.overlaps(r2));
-        bs.borrow(r1).expect("can borrow r1");
-        assert!(bs.borrow(r2).is_err(), "cant borrow r2");
-
-        let mut bs = InnerBorrowChecker::new();
-        let r1 = Region::new(2, 5);
-        let r2 = Region::new(10, 5);
-        let r3 = Region::new(15, 5);
-        let r4 = Region::new(0, 10);
-        assert!(r1.overlaps(r4));
-        bs.borrow(r1).expect("can borrow r1");
-        bs.borrow(r2).expect("can borrow r2");
-        bs.borrow(r3).expect("can borrow r3");
-        assert!(bs.borrow(r4).is_err(), "cant borrow r4");
-    }
-
-    #[test]
-    fn unborrowing() {
-        let mut bs = InnerBorrowChecker::new();
-        let r1 = Region::new(0, 10);
-        let r2 = Region::new(10, 10);
-        assert!(!r1.overlaps(r2));
-        assert_eq!(bs.has_outstanding_borrows(), false, "start with no borrows");
-        let h1 = bs.borrow(r1).expect("can borrow r1");
-        assert_eq!(bs.has_outstanding_borrows(), true, "h1 is outstanding");
-        let h2 = bs.borrow(r2).expect("can borrow r2");
-
-        assert!(bs.borrow(r2).is_err(), "can't borrow r2 twice");
-        bs.unborrow(h2);
-        assert_eq!(
-            bs.has_outstanding_borrows(),
-            true,
-            "h1 is still outstanding"
-        );
-        bs.unborrow(h1);
-        assert_eq!(bs.has_outstanding_borrows(), false, "no remaining borrows");
-
-        let _h3 = bs
-            .borrow(r2)
-            .expect("can borrow r2 again now that its been unborrowed");
-    }
-}
diff --git a/crates/wiggle/wasmtime/src/lib.rs b/crates/wiggle/wasmtime/src/lib.rs
index e38ab3ac3..dc43683c1 100644
--- a/crates/wiggle/wasmtime/src/lib.rs
+++ b/crates/wiggle/wasmtime/src/lib.rs
@@ -1,9 +1,7 @@
 pub use wasmtime_wiggle_macro::*;
 pub use wiggle::*;
 
-mod borrow;
-
-use borrow::BorrowChecker;
+use wiggle_borrow::BorrowChecker;
 
 /// Lightweight `wasmtime::Memory` wrapper so we can implement the
 /// `wiggle::GuestMemory` trait on it.
@@ -37,13 +35,22 @@ unsafe impl GuestMemory for WasmtimeGuestMemory {
     fn has_outstanding_borrows(&self) -> bool {
         self.bc.has_outstanding_borrows()
     }
-    fn is_borrowed(&self, r: Region) -> bool {
-        self.bc.is_borrowed(r)
+    fn is_shared_borrowed(&self, r: Region) -> bool {
+        self.bc.is_shared_borrowed(r)
+    }
+    fn is_mut_borrowed(&self, r: Region) -> bool {
+        self.bc.is_mut_borrowed(r)
+    }
+    fn shared_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
+        self.bc.shared_borrow(r)
+    }
+    fn mut_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
+        self.bc.mut_borrow(r)
     }
-    fn borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
-        self.bc.borrow(r)
+    fn shared_unborrow(&self, h: BorrowHandle) {
+        self.bc.shared_unborrow(h)
     }
-    fn unborrow(&self, h: BorrowHandle) {
-        self.bc.unborrow(h)
+    fn mut_unborrow(&self, h: BorrowHandle) {
+        self.bc.mut_unborrow(h)
     }
 }
diff --git a/scripts/publish.rs b/scripts/publish.rs
index 5713b9f05..5931fa7d1 100644
--- a/scripts/publish.rs
+++ b/scripts/publish.rs
@@ -45,6 +45,7 @@ const CRATES_TO_PUBLISH: &[&str] = &[
     "wiggle-generate",
     "wiggle-macro",
     "wiggle",
+    "wiggle-borrow",
     "wasmtime-wiggle-macro",
     // wasi-common bits
     "winx",


Test patch:
diff --git a/crates/wiggle/test-helpers/Cargo.toml b/crates/wiggle/test-helpers/Cargo.toml
index ea49cf6af..6c6c02ed4 100644
--- a/crates/wiggle/test-helpers/Cargo.toml
+++ b/crates/wiggle/test-helpers/Cargo.toml
@@ -1,6 +1,6 @@
 [package]
 name = "wiggle-test"
-version = "0.19.0"
+version = "0.21.0"
 authors = ["Pat Hickey <phickey@fastly.com>", "Jakub Konka <kubkon@jakubkonka.com>", "Alex Crichton <alex@alexcrichton.com>"]
 license = "Apache-2.0 WITH LLVM-exception"
 edition = "2018"
@@ -14,6 +14,7 @@ publish = false
 [dependencies]
 proptest = "0.10"
 wiggle = { path = "..", features = ["tracing_log"] }
+wiggle-borrow = { path = "../borrow" }
 
 [dev-dependencies]
 thiserror = "1.0"
diff --git a/crates/wiggle/test-helpers/src/borrow.rs b/crates/wiggle/test-helpers/src/borrow.rs
deleted file mode 100644
index 5ed16e271..000000000
--- a/crates/wiggle/test-helpers/src/borrow.rs
+++ /dev/null
@@ -1,188 +0,0 @@
-use std::cell::RefCell;
-use std::collections::HashMap;
-use wiggle::{BorrowHandle, GuestError, Region};
-
-pub struct BorrowChecker {
-    bc: RefCell<InnerBorrowChecker>,
-}
-
-impl BorrowChecker {
-    /// A `BorrowChecker` manages run-time validation of borrows from a `GuestMemory`. It keeps
-    /// track of regions of guest memory which are possible to alias with Rust references (via the
-    /// `GuestSlice` and `GuestStr` structs, which implement `std::ops::Deref` and
-    /// `std::ops::DerefMut`. It also enforces that `GuestPtr::read` and `GuestPtr::write` do not
-    /// access memory with an outstanding borrow.
-    pub fn new() -> Self {
-        BorrowChecker {
-            bc: RefCell::new(InnerBorrowChecker::new()),
-        }
-    }
-    /// Indicates whether any outstanding borrows are known to the `BorrowChecker`. This function
-    /// must be `false` in order for it to be safe to recursively call into a WebAssembly module,
-    /// or to manipulate the WebAssembly memory by any other means.
-    pub fn has_outstanding_borrows(&self) -> bool {
-        self.bc.borrow().has_outstanding_borrows()
-    }
-
-    pub(crate) fn borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
-        self.bc.borrow_mut().borrow(r)
-    }
-    pub(crate) fn unborrow(&self, h: BorrowHandle) {
-        self.bc.borrow_mut().unborrow(h)
-    }
-    pub(crate) fn is_borrowed(&self, r: Region) -> bool {
-        self.bc.borrow().is_borrowed(r)
-    }
-}
-
-#[derive(Debug)]
-/// This is a pretty naive way to account for borrows. This datastructure
-/// could be made a lot more efficient with some effort.
-struct InnerBorrowChecker {
-    /// Map from handle to region borrowed. A HashMap is probably not ideal
-    /// for this but it works. It would be more efficient if we could
-    /// check `is_borrowed` without an O(n) iteration, by organizing borrows
-    /// by an ordering of Region.
-    borrows: HashMap<BorrowHandle, Region>,
-    /// Handle to give out for the next borrow. This is the bare minimum of
-    /// bookkeeping of free handles, and in a pathological case we could run
-    /// out, hence [`GuestError::BorrowCheckerOutOfHandles`]
-    next_handle: BorrowHandle,
-}
-
-impl InnerBorrowChecker {
-    fn new() -> Self {
-        InnerBorrowChecker {
-            borrows: HashMap::new(),
-            next_handle: BorrowHandle(0),
-        }
-    }
-
-    fn has_outstanding_borrows(&self) -> bool {
-        !self.borrows.is_empty()
-    }
-
-    fn is_borrowed(&self, r: Region) -> bool {
-        !self.borrows.values().all(|b| !b.overlaps(r))
-    }
-
-    fn new_handle(&mut self) -> Result<BorrowHandle, GuestError> {
-        // Reset handles to 0 if all handles have been returned.
-        if self.borrows.is_empty() {
-            self.next_handle = BorrowHandle(0);
-        }
-        let h = self.next_handle;
-        // Get the next handle. Since we don't recycle handles until all of
-        // them have been returned, there is a pathological case where a user
-        // may make a Very Large (usize::MAX) number of valid borrows and
-        // unborrows while always keeping at least one borrow outstanding, and
-        // we will run out of borrow handles.
-        self.next_handle = BorrowHandle(
-            h.0.checked_add(1)
-                .ok_or_else(|| GuestError::BorrowCheckerOutOfHandles)?,
-        );
-        Ok(h)
-    }
-
-    fn borrow(&mut self, r: Region) -> Result<BorrowHandle, GuestError> {
-        if self.is_borrowed(r) {
-            return Err(GuestError::PtrBorrowed(r));
-        }
-        let h = self.new_handle()?;
-        self.borrows.insert(h, r);
-        Ok(h)
-    }
-
-    fn unborrow(&mut self, h: BorrowHandle) {
-        let _ = self.borrows.remove(&h);
-    }
-}
-
-#[cfg(test)]
-mod test {
-    use super::*;
-    #[test]
-    fn nonoverlapping() {
-        let mut bs = InnerBorrowChecker::new();
-        let r1 = Region::new(0, 10);
-        let r2 = Region::new(10, 10);
-        assert!(!r1.overlaps(r2));
-        bs.borrow(r1).expect("can borrow r1");
-        bs.borrow(r2).expect("can borrow r2");
-
-        let mut bs = InnerBorrowChecker::new();
-        let r1 = Region::new(10, 10);
-        let r2 = Region::new(0, 10);
-        assert!(!r1.overlaps(r2));
-        bs.borrow(r1).expect("can borrow r1");
-        bs.borrow(r2).expect("can borrow r2");
-    }
-
-    #[test]
-    fn overlapping() {
-        let mut bs = InnerBorrowChecker::new();
-        let r1 = Region::new(0, 10);
-        let r2 = Region::new(9, 10);
-        assert!(r1.overlaps(r2));
-        bs.borrow(r1).expect("can borrow r1");
-        assert!(bs.borrow(r2).is_err(), "cant borrow r2");
-
-        let mut bs = InnerBorrowChecker::new();
-        let r1 = Region::new(0, 10);
-        let r2 = Region::new(2, 5);
-        assert!(r1.overlaps(r2));
-        bs.borrow(r1).expect("can borrow r1");
-        assert!(bs.borrow(r2).is_err(), "cant borrow r2");
-
-        let mut bs = InnerBorrowChecker::new();
-        let r1 = Region::new(9, 10);
-        let r2 = Region::new(0, 10);
-        assert!(r1.overlaps(r2));
-        bs.borrow(r1).expect("can borrow r1");
-        assert!(bs.borrow(r2).is_err(), "cant borrow r2");
-
-        let mut bs = InnerBorrowChecker::new();
-        let r1 = Region::new(2, 5);
-        let r2 = Region::new(0, 10);
-        assert!(r1.overlaps(r2));
-        bs.borrow(r1).expect("can borrow r1");
-        assert!(bs.borrow(r2).is_err(), "cant borrow r2");
-
-        let mut bs = InnerBorrowChecker::new();
-        let r1 = Region::new(2, 5);
-        let r2 = Region::new(10, 5);
-        let r3 = Region::new(15, 5);
-        let r4 = Region::new(0, 10);
-        assert!(r1.overlaps(r4));
-        bs.borrow(r1).expect("can borrow r1");
-        bs.borrow(r2).expect("can borrow r2");
-        bs.borrow(r3).expect("can borrow r3");
-        assert!(bs.borrow(r4).is_err(), "cant borrow r4");
-    }
-
-    #[test]
-    fn unborrowing() {
-        let mut bs = InnerBorrowChecker::new();
-        let r1 = Region::new(0, 10);
-        let r2 = Region::new(10, 10);
-        assert!(!r1.overlaps(r2));
-        assert_eq!(bs.has_outstanding_borrows(), false, "start with no borrows");
-        let h1 = bs.borrow(r1).expect("can borrow r1");
-        assert_eq!(bs.has_outstanding_borrows(), true, "h1 is outstanding");
-        let h2 = bs.borrow(r2).expect("can borrow r2");
-
-        assert!(bs.borrow(r2).is_err(), "can't borrow r2 twice");
-        bs.unborrow(h2);
-        assert_eq!(
-            bs.has_outstanding_borrows(),
-            true,
-            "h1 is still outstanding"
-        );
-        bs.unborrow(h1);
-        assert_eq!(bs.has_outstanding_borrows(), false, "no remaining borrows");
-
-        let _h3 = bs
-            .borrow(r2)
-            .expect("can borrow r2 again now that its been unborrowed");
-    }
-}
diff --git a/crates/wiggle/test-helpers/src/lib.rs b/crates/wiggle/test-helpers/src/lib.rs
index 6164e4f92..99571367a 100644
--- a/crates/wiggle/test-helpers/src/lib.rs
+++ b/crates/wiggle/test-helpers/src/lib.rs
@@ -3,8 +3,7 @@ use std::cell::UnsafeCell;
 use std::marker;
 use wiggle::{BorrowHandle, GuestMemory, Region};
 
-mod borrow;
-use borrow::BorrowChecker;
+use wiggle_borrow::BorrowChecker;
 
 #[derive(Debug, Clone)]
 pub struct MemAreas(Vec<MemArea>);
@@ -126,14 +125,23 @@ unsafe impl GuestMemory for HostMemory {
     fn has_outstanding_borrows(&self) -> bool {
         self.bc.has_outstanding_borrows()
     }
-    fn is_borrowed(&self, r: Region) -> bool {
-        self.bc.is_borrowed(r)
+    fn is_shared_borrowed(&self, r: Region) -> bool {
+        self.bc.is_shared_borrowed(r)
     }
-    fn borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
-        self.bc.borrow(r)
+    fn is_mut_borrowed(&self, r: Region) -> bool {
+        self.bc.is_mut_borrowed(r)
     }
-    fn unborrow(&self, h: BorrowHandle) {
-        self.bc.unborrow(h)
+    fn mut_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
+        self.bc.mut_borrow(r)
+    }
+    fn shared_borrow(&self, r: Region) -> Result<BorrowHandle, GuestError> {
+        self.bc.shared_borrow(r)
+    }
+    fn shared_unborrow(&self, h: BorrowHandle) {
+        self.bc.shared_unborrow(h)
+    }
+    fn mut_unborrow(&self, h: BorrowHandle) {
+        self.bc.mut_unborrow(h)
     }
 }
 
diff --git a/crates/wiggle/tests/strings.rs b/crates/wiggle/tests/strings.rs
index cff55d92d..ed176f6f6 100644
--- a/crates/wiggle/tests/strings.rs
+++ b/crates/wiggle/tests/strings.rs
@@ -34,9 +34,12 @@ impl<'a> strings::Strings for WasiCtx<'a> {
     }
 }
 
-fn test_string_strategy() -> impl Strategy<Value = String> {
+fn unicode_string_strategy() -> impl Strategy<Value = String> {
     "\\p{Greek}{1,256}"
 }
+fn ascii_string_strategy() -> impl Strategy<Value = String> {
+    "[a-zA-Z0..9]{1,256}"
+}
 
 #[derive(Debug)]
 struct HelloStringExercise {
@@ -47,7 +50,7 @@ struct HelloStringExercise {
 
 impl HelloStringExercise {
     pub fn strat() -> BoxedStrategy<Self> {
-        (test_string_strategy(),)
+        (unicode_string_strategy(),)
             .prop_flat_map(|(test_word,)| {
                 (
                     Just(test_word.clone()),
@@ -115,9 +118,9 @@ struct MultiStringExercise {
 impl MultiStringExercise {
     pub fn strat() -> BoxedStrategy<Self> {
         (
-            test_string_strategy(),
-            test_string_strategy(),
-            test_string_strategy(),
+            unicode_string_strategy(),
+            unicode_string_strategy(),
+            unicode_string_strategy(),
             HostMemory::mem_area_strat(4),
         )
             .prop_flat_map(|(a, b, c, return_ptr_loc)| {
@@ -221,3 +224,85 @@ proptest! {
         e.test()
     }
 }
+
+#[derive(Debug)]
+struct OverlappingStringExercise {
+    a: String,
+    sa_ptr_loc: MemArea,
+    offset_b: u32,
+    offset_c: u32,
+    return_ptr_loc: MemArea,
+}
+
+impl OverlappingStringExercise {
+    pub fn strat() -> BoxedStrategy<Self> {
+        // using ascii so we can window into it without worrying about codepoints
+        (ascii_string_strategy(), HostMemory::mem_area_strat(4))
+            .prop_flat_map(|(a, return_ptr_loc)| {
+                (
+                    Just(a.clone()),
+                    HostMemory::mem_area_strat(a.len() as u32),
+                    0..(a.len() as u32),
+                    0..(a.len() as u32),
+                    Just(return_ptr_loc),
+                )
+            })
+            .prop_map(|(a, sa_ptr_loc, offset_b, offset_c, return_ptr_loc)| Self {
+                a,
+                sa_ptr_loc,
+                offset_b,
+                offset_c,
+                return_ptr_loc,
+            })
+            .prop_filter("non-overlapping pointers", |e| {
+                MemArea::non_overlapping_set(&[e.sa_ptr_loc, e.return_ptr_loc])
+            })
+            .boxed()
+    }
+
+    pub fn test(&self) {
+        let ctx = WasiCtx::new();
+        let host_memory = HostMemory::new();
+
+        let write_string = |val: &str, loc: MemArea| {
+            let ptr = host_memory.ptr::<str>((loc.ptr, val.len() as u32));
+            for (slot, byte) in ptr.as_bytes().iter().zip(val.bytes()) {
+                slot.expect("should be valid pointer")
+                    .write(byte)
+                    .expect("failed to write");
+            }
+        };
+
+        write_string(&self.a, self.sa_ptr_loc);
+
+        let a_len = self.a.as_bytes().len() as i32;
+        let res = strings::multi_string(
+            &ctx,
+            &host_memory,
+            self.sa_ptr_loc.ptr as i32,
+            a_len,
+            (self.sa_ptr_loc.ptr + self.offset_b) as i32,
+            a_len - self.offset_b as i32,
+            (self.sa_ptr_loc.ptr + self.offset_c) as i32,
+            a_len - self.offset_c as i32,
+            self.return_ptr_loc.ptr as i32,
+        );
+        assert_eq!(res, types::Errno::Ok.into(), "multi string errno");
+
+        let given = host_memory
+            .ptr::<u32>(self.return_ptr_loc.ptr)
+            .read()
+            .expect("deref ptr to return value");
+        assert_eq!(
+            ((3 * a_len) - (self.offset_b as i32 + self.offset_c as i32)) as u32,
+            given
+        );
+    }
+}
+
+proptest! {
+    #[test]
+    fn overlapping_string(e in OverlappingStringExercise::strat()) {
+        e.test()
+    }
+}