Repository: ParkMyCar/compact_str
Pull request #167 (2022-07-25 00:48:28)

backport(v0.5): Test case discovered by AFL (#161)
* fix: Bug when trying to create a CompactString with capacity of 16711422 on 32-bit arches
* Fixed the underlying bug, which was related to the change in HEAP_MASK
* Add debug.rs binary to repro single failing fuzz cases
* Add unit test with comment to repro the exact failure
* ignore all capacity values test in miri

Backport of: https://github.com/ParkMyCar/compact_str/pull/161


Patch:
diff --git a/compact_str/src/repr/boxed/capacity.rs b/compact_str/src/repr/boxed/capacity.rs
index 1dc00605..1d4f60cd 100644
--- a/compact_str/src/repr/boxed/capacity.rs
+++ b/compact_str/src/repr/boxed/capacity.rs
@@ -2,8 +2,21 @@ use crate::repr::HEAP_MASK;
 
 // how many bytes a `usize` occupies
 const USIZE_SIZE: usize = core::mem::size_of::<usize>();
-// state that describes the capacity as being stored on the heap
-const CAPACITY_IS_ON_THE_HEAP: [u8; USIZE_SIZE] = [HEAP_MASK; USIZE_SIZE];
+
+/// Used to generate [`CAPACITY_IS_ON_THE_HEAP`]
+#[allow(non_snake_case)]
+const fn CAP_ON_HEAP_FLAG() -> [u8; USIZE_SIZE] {
+    // all bytes 255, with the last
+    let mut flag = [255; USIZE_SIZE];
+    flag[USIZE_SIZE - 1] = HEAP_MASK;
+    flag
+}
+
+/// State that describes the capacity as being stored on the heap.
+///
+/// All bytes `255`, with the last being [`HEAP_MASK`], using the same amount of bytes as `usize`
+/// Example (64-bit): `[255, 255, 255, 255, 255, 255, 255, 254]`
+const CAPACITY_IS_ON_THE_HEAP: [u8; USIZE_SIZE] = CAP_ON_HEAP_FLAG();
 
 // how many bytes we can use for capacity
 const SPACE_FOR_CAPACITY: usize = USIZE_SIZE - 1;
@@ -101,6 +114,8 @@ impl Capacity {
 
 #[cfg(test)]
 mod tests {
+    use rayon::prelude::*;
+
     use super::Capacity;
 
     #[test]
@@ -146,6 +161,27 @@ mod tests {
         let og = usize::MAX;
         assert!(Capacity::new(og).is_err());
     }
+
+    #[test]
+    #[cfg_attr(miri, ignore)]
+    fn test_all_valid_32bit_values() {
+        #[cfg(target_pointer_width = "32")]
+        assert_eq!(16_777_214, super::MAX_VALUE);
+
+        (0..=16_777_214)
+            .into_par_iter()
+            .for_each(|i| match Capacity::new(i) {
+                Ok(cap) => match cap.as_usize() {
+                    Ok(val) => assert_eq!(val, i, "value roundtriped to wrong value?"),
+                    Err(_) => panic!("value converted, but failed to roundtrip! val: {}", i),
+                },
+                Err(_) => panic!("failed to convert {}", i),
+            });
+
+        // one above the 32-bit max value
+        #[cfg(target_pointer_width = "32")]
+        assert!(Capacity::new(16_777_215).is_err());
+    }
 }
 
 crate::asserts::assert_size_eq!(Capacity, usize);


Test patch:
diff --git a/compact_str/src/tests.rs b/compact_str/src/tests.rs
index d5676bd3..5f960f66 100644
--- a/compact_str/src/tests.rs
+++ b/compact_str/src/tests.rs
@@ -713,3 +713,35 @@ fn test_to_compact_string() {
         format_compact!("0{}67890123456789{}", "12345", 999999)
     );
 }
+
+#[test]
+fn test_with_capacity_16711422() {
+    // Fuzzing with AFL on a 32-bit ARM arch found this bug!
+    //
+    // We have our own heap implemenation called BoxString, which optionally stores the capacity
+    // on the heap, which is really only relevant for 32-bit architectures. The discriminant it used
+    // to determine if capacity was on the heap, was when the last `usize` number of bytes were all
+    // equal to our internal HEAP_MASK, which at the time was `255`. At the time this worked and was
+    // correct.
+    //
+    // When we released support to make the size of CompactString == Option<CompactString>, we
+    // changed the HEAP_MASK to `254`, which unintentionally made our discriminant for determining
+    // if our capacity was on the heap, all `254`s, yet our "max inline capacity value" was still
+    // based on the discriminant being all `255`s.
+    //
+    // When creating a BoxString with capacity 16711422, we'd correctly decide we could store the
+    // capacity inline, but this would create a capacity with an underlying value of
+    // [254, 254, 254, HEAP_MASK]. Once the HEAP_MASK changed to 254, this capacity was now the same
+    // as the discriminant to determine if the capacity was on the heap, so we'd incorrectly
+    // identify the capacity as being on the heap, when it was really inline.
+
+    assert_eq!(16711422_u32.to_le_bytes(), [254, 254, 254, 0]);
+
+    let compact = CompactString::with_capacity(16711422);
+    let std_str = String::with_capacity(16711422);
+
+    assert!(compact.is_heap_allocated());
+    assert_eq!(compact.capacity(), std_str.capacity());
+    assert_eq!(compact, "");
+    assert_eq!(compact, std_str);
+}