CVE-2020-25792

@@ -11,7 +11,7 @@ use core::cmp::Ordering;
 use core::fmt::{Debug, Error, Formatter};
 use core::hash::{Hash, Hasher};
 use core::iter::FromIterator;
-use core::mem::MaybeUninit;
+use core::mem::{replace, MaybeUninit};
 use core::ops::{Bound, Range, RangeBounds};
 use core::ops::{Index, IndexMut};
 
@@ -253,6 +253,7 @@ where
     #[inline]
     #[must_use]
     pub fn unit(value: A) -> Self {
+        assert!(Self::CAPACITY >= 1);
         let mut buffer = Self {
             origin: 0.into(),
             length: 1,
@@ -268,6 +269,7 @@ where
     #[inline]
     #[must_use]
     pub fn pair(value1: A, value2: A) -> Self {
+        assert!(Self::CAPACITY >= 2);
         let mut buffer = Self {
             origin: 0.into(),
             length: 2,
@@ -714,10 +716,22 @@ where
             }
         }
         let mut index = self.raw(index);
-        for value in iter {
+        // Panic safety: unless and until we fill it fully, there's a hole somewhere in the middle
+        // and the destructor would drop non-existing elements. Therefore we pretend to be empty
+        // for a while (and leak the elements instead in case something bad happens).
+        let mut inserted = 0;
+        let length = replace(&mut self.length, 0);
+        for value in iter.take(insert_size) {
             unsafe { self.force_write(index, value) };
             index += 1;
+            inserted += 1;
         }
+        // This would/could create a hole in the middle if it was less
+        assert_eq!(
+            inserted, insert_size,
+            "Iterator has fewer elements than advertised",
+        );
+        self.length = length;
     }
 
     /// Remove the value at index `index`, shifting all the following values to
@@ -787,8 +801,12 @@ impl<A: Clone, N: ChunkLength<A>> Clone for RingBuffer<A, N> {
         let mut out = Self::new();
         out.origin = self.origin;
         out.length = self.length;
-        for index in out.range() {
+        let range = self.range();
+        // Panic safety. If we panic, we don't want to drop more than we have initialized.
+        out.length = 0;
+        for index in range {
             unsafe { out.force_write(index, (&*self.ptr(index)).clone()) };
+            out.length += 1;
         }
         out
     }
@@ -1003,6 +1021,8 @@ impl<'a, A, N: ChunkLength<A>> IntoIterator for &'a mut RingBuffer<A, N> {
 
 #[cfg(test)]
 mod test {
+    use typenum::U0;
+
     use super::*;
 
     #[test]
@@ -1121,4 +1141,16 @@ mod test {
         }
         assert_eq!(0, counter.load(Ordering::Relaxed));
     }
+
+    #[test]
+    #[should_panic(expected = "assertion failed: Self::CAPACITY >= 1")]
+    fn unit_on_empty() {
+        let _ = RingBuffer::<usize, U0>::unit(1);
+    }
+
+    #[test]
+    #[should_panic(expected = "assertion failed: Self::CAPACITY >= 2")]
+    fn pair_on_empty() {
+        let _ = RingBuffer::<usize, U0>::pair(1, 2);
+    }
 }

@@ -125,9 +125,13 @@ where
     fn clone(&self) -> Self {
         let mut out = Self::new();
         out.left = self.left;
-        out.right = self.right;
+        out.right = self.left;
         for index in self.left..self.right {
             unsafe { Chunk::force_write(index, (*self.ptr(index)).clone(), &mut out) }
+            // Panic safety, move the right index to cover only the really initialized things. This
+            // way we don't try to drop uninitialized, but also don't leak if we panic in the
+            // middle.
+            out.right = index + 1;
         }
         out
     }
@@ -151,6 +155,7 @@ where
 
     /// Construct a new chunk with one item.
     pub fn unit(value: A) -> Self {
+        assert!(Self::CAPACITY >= 1);
         let mut chunk = Self {
             left: 0,
             right: 1,
@@ -164,6 +169,7 @@ where
 
     /// Construct a new chunk with two items.
     pub fn pair(left: A, right: A) -> Self {
+        assert!(Self::CAPACITY >= 2);
         let mut chunk = Self {
             left: 0,
             right: 2,
@@ -282,6 +288,49 @@ where
         }
     }
 
+    /// Write values from iterator into range starting at write_index.
+    ///
+    /// Will overwrite values at the relevant range without dropping even in case the values were
+    /// already initialized (it is expected they are empty). Does not update the left or right
+    /// index.
+    ///
+    /// # Safety
+    ///
+    /// Range checks must already have been performed.
+    ///
+    /// # Panics
+    ///
+    /// If the iterator panics, the chunk becomes conceptually empty and will leak any previous
+    /// elements (even the ones outside the range).
+    #[inline]
+    unsafe fn write_from_iter<I>(mut write_index: usize, iter: I, chunk: &mut Self)
+    where
+        I: ExactSizeIterator<Item = A>,
+    {
+        // Panic safety. We make the array conceptually empty, so we never ever drop anything that
+        // is unitialized. We do so because we expect to be called when there's a potential "hole"
+        // in the array that makes the space for the new elements to be written. We return it back
+        // to original when everything goes fine, but leak any elements on panic. This is bad, but
+        // better than dropping non-existing stuff.
+        //
+        // Should we worry about some better panic recovery than this?
+        let left = replace(&mut chunk.left, 0);
+        let right = replace(&mut chunk.right, 0);
+        let len = iter.len();
+        let expected_end = write_index + len;
+        for value in iter.take(len) {
+            Chunk::force_write(write_index, value, chunk);
+            write_index += 1;
+        }
+        // Oops, we have a hole in here now. That would be bad, give up.
+        assert_eq!(
+            expected_end, write_index,
+            "ExactSizeIterator yielded fewer values than advertised",
+        );
+        chunk.left = left;
+        chunk.right = right;
+    }
+
     /// Copy a range between chunks
     #[inline]
     unsafe fn force_copy_to(
@@ -583,32 +632,23 @@ where
         if self.right == N::USIZE || (self.left >= insert_size && left_size < right_size) {
             unsafe {
                 Chunk::force_copy(self.left, self.left - insert_size, left_size, self);
-                let mut write_index = real_index - insert_size;
-                for value in iter {
-                    Chunk::force_write(write_index, value, self);
-                    write_index += 1;
-                }
+                let write_index = real_index - insert_size;
+                Chunk::write_from_iter(write_index, iter, self);
             }
             self.left -= insert_size;
         } else if self.left == 0 || (self.right + insert_size <= Self::CAPACITY) {
             unsafe {
                 Chunk::force_copy(real_index, real_index + insert_size, right_size, self);
-                let mut write_index = real_index;
-                for value in iter {
-                    Chunk::force_write(write_index, value, self);
-                    write_index += 1;
-                }
+                let write_index = real_index;
+                Chunk::write_from_iter(write_index, iter, self);
             }
             self.right += insert_size;
         } else {
             unsafe {
                 Chunk::force_copy(self.left, 0, left_size, self);
                 Chunk::force_copy(real_index, left_size + insert_size, right_size, self);
-                let mut write_index = left_size;
-                for value in iter {
-                    Chunk::force_write(write_index, value, self);
-                    write_index += 1;
-                }
+                let write_index = left_size;
+                Chunk::write_from_iter(write_index, iter, self);
             }
             self.right -= self.left;
             self.right += insert_size;
@@ -817,6 +857,7 @@ where
     N: ChunkLength<A>,
 {
     fn from(array: &mut InlineArray<A, T>) -> Self {
+        assert!(array.len() <= Self::CAPACITY);
         let mut out = Self::new();
         out.left = 0;
         out.right = array.len();
@@ -975,6 +1016,8 @@ where
 
 #[cfg(test)]
 mod test {
+    use typenum::U0;
+
     use super::*;
 
     #[test]
@@ -1183,4 +1226,16 @@ mod test {
         }
         assert_eq!(0, counter.load(Ordering::Relaxed));
     }
+
+    #[test]
+    #[should_panic(expected = "assertion failed: Self::CAPACITY >= 1")]
+    fn unit_on_empty() {
+        Chunk::<usize, U0>::unit(1);
+    }
+
+    #[test]
+    #[should_panic(expected = "assertion failed: Self::CAPACITY >= 2")]
+    fn pair_on_empty() {
+        Chunk::<usize, U0>::pair(1, 2);
+    }
 }

@@ -11,7 +11,6 @@ use core::cmp::Ordering;
 use core::fmt::{Debug, Error, Formatter};
 use core::hash::{Hash, Hasher};
 use core::iter::FromIterator;
-use core::marker::PhantomData;
 use core::mem::{self, MaybeUninit};
 use core::ops::{Deref, DerefMut};
 use core::ptr;
@@ -25,7 +24,7 @@ pub use self::iter::{Drain, Iter};
 /// This works like a vector, but allocated on the stack (and thus marginally
 /// faster than `Vec`), with the allocated space exactly matching the size of
 /// the given type `T`. The vector consists of a `usize` tracking its current
-/// length, followed by zero or more elements of type `A`. The capacity is thus
+/// length and zero or more elements of type `A`. The capacity is thus
 /// `( size_of::<T>() - size_of::<usize>() ) / size_of::<A>()`. This could lead
 /// to situations where the capacity is zero, if `size_of::<A>()` is greater
 /// than `size_of::<T>() - size_of::<usize>()`, which is not an error and
@@ -72,9 +71,37 @@ pub use self::iter::{Drain, Iter};
 ///
 /// Both of these will have the same size, and we can swap the `Inline` case out
 /// with the `Full` case once the `InlineArray` runs out of capacity.
+#[repr(C)]
 pub struct InlineArray<A, T> {
+    // Alignment tricks
+    //
+    // We need both the usize header and data to be properly aligned in memory. We do a few tricks
+    // to handle that.
+    //
+    // * An alignment is always power of 2. Therefore, with a pair of alignments, one is always
+    //   a multiple of the other (one way or the other).
+    // * A struct is aligned to at least the max alignment of each of its fields.
+    // * A repr(C) struct follows the order of fields and pushes each as close to the previous one
+    //   as allowed by alignment.
+    //
+    // By placing two "fake" fields that have 0 size, but an alignment first, we make sure that all
+    // 3 start at the beginning of the struct and that all of them are aligned to their maximum
+    // alignment.
+    //
+    // Furthermore, because we don't know if usize or A has bigger alignment, we decide on case by
+    // case basis if the header or the elements go first. By placing the one with higher alignment
+    // requirements first, we align that one and the other one will be aligned "automatically" when
+    // placed just after it.
+    //
+    // To the best of our knowledge, this is all guaranteed by the compiler. But just to make sure,
+    // we have bunch of asserts in the constructor to check; as these are invariants enforced by
+    // the compiler, it should be trivial for it to remove the checks so they are for free (if we
+    // are correct) or will save us (if we are not).
+    //
+    // Additionally, the [A; 0] serves as a form of PhantomData.
+    _header_align: [usize; 0],
+    _data_align: [A; 0],
     data: MaybeUninit<T>,
-    phantom: PhantomData<A>,
 }
 
 const fn capacity(host_size: usize, header_size: usize, element_size: usize) -> usize {
@@ -89,32 +116,67 @@ impl<A, T> InlineArray<A, T> {
     const HOST_SIZE: usize = mem::size_of::<T>();
     const ELEMENT_SIZE: usize = mem::size_of::<A>();
     const HEADER_SIZE: usize = mem::size_of::<usize>();
+    // Do we place the header before the elements or the other way around?
+    const HEADER_FIRST: bool = mem::align_of::<usize>() >= mem::align_of::<A>();
+    // Note: one of the following is always 0
+    // How many usizes to skip before the first element?
+    const ELEMENT_SKIP: usize = Self::HEADER_FIRST as usize;
+    // How many elements to skip before the header
+    const HEADER_SKIP: usize = Self::CAPACITY * (1 - Self::ELEMENT_SKIP);
 
     /// The maximum number of elements the `InlineArray` can hold.
     pub const CAPACITY: usize = capacity(Self::HOST_SIZE, Self::HEADER_SIZE, Self::ELEMENT_SIZE);
 
     #[inline]
     #[must_use]
     unsafe fn len_const(&self) -> *const usize {
-        (&self.data) as *const _ as *const usize
+        let ptr = self
+            .data
+            .as_ptr()
+            .cast::<A>()
+            .add(Self::HEADER_SKIP)
+            .cast::<usize>();
+        debug_assert!(ptr as usize % mem::align_of::<usize>() == 0);
+        ptr
     }
 
     #[inline]
     #[must_use]
     pub(crate) unsafe fn len_mut(&mut self) -> *mut usize {
-        (&mut self.data) as *mut _ as *mut usize
+        let ptr = self
+            .data
+            .as_mut_ptr()
+            .cast::<A>()
+            .add(Self::HEADER_SKIP)
+            .cast::<usize>();
+        debug_assert!(ptr as usize % mem::align_of::<usize>() == 0);
+        ptr
     }
 
     #[inline]
     #[must_use]
     pub(crate) unsafe fn data(&self) -> *const A {
-        self.len_const().add(1) as *const _ as *const A
+        let ptr = self
+            .data
+            .as_ptr()
+            .cast::<usize>()
+            .add(Self::ELEMENT_SKIP)
+            .cast::<A>();
+        debug_assert!(ptr as usize % mem::align_of::<A>() == 0);
+        ptr
     }
 
     #[inline]
     #[must_use]
     unsafe fn data_mut(&mut self) -> *mut A {
-        self.len_mut().add(1) as *mut _ as *mut A
+        let ptr = self
+            .data
+            .as_mut_ptr()
+            .cast::<usize>()
+            .add(Self::ELEMENT_SKIP)
+            .cast::<A>();
+        debug_assert!(ptr as usize % mem::align_of::<A>() == 0);
+        ptr
     }
 
     #[inline]
@@ -164,12 +226,36 @@ impl<A, T> InlineArray<A, T> {
     #[inline]
     #[must_use]
     pub fn new() -> Self {
-        debug_assert!(Self::HOST_SIZE > Self::HEADER_SIZE);
+        assert!(Self::HOST_SIZE > Self::HEADER_SIZE);
         let mut self_ = Self {
+            _header_align: [],
+            _data_align: [],
             data: MaybeUninit::uninit(),
-            phantom: PhantomData,
         };
-        unsafe { *self_.len_mut() = 0 }
+        // Sanity check our assumptions about what is guaranteed by the compiler. If we are right,
+        // these should completely optimize out of the resulting binary.
+        assert_eq!(
+            &self_ as *const _ as usize,
+            self_.data.as_ptr() as usize,
+            "Padding at the start of struct",
+        );
+        assert_eq!(mem::size_of::<Self>(), mem::size_of::<T>());
+        assert_eq!(
+            self_.data.as_ptr() as usize % mem::align_of::<usize>(),
+            0,
+            "Unaligned header"
+        );
+        assert_eq!(
+            self_.data.as_ptr() as usize % mem::align_of::<A>(),
+            0,
+            "Unaligned elements"
+        );
+        assert!(
+            mem::align_of::<A>() % mem::align_of::<usize>() == 0
+                || mem::align_of::<usize>() % mem::align_of::<A>() == 0
+        );
+        assert!(Self::ELEMENT_SKIP == 0 || Self::HEADER_SKIP == 0);
+        unsafe { ptr::write(self_.len_mut(), 0usize) };
         self_
     }
 
@@ -270,7 +356,7 @@ impl<A, T> InlineArray<A, T> {
 
     #[inline]
     unsafe fn drop_contents(&mut self) {
-        ptr::drop_in_place::<[A]>(&mut **self)
+        ptr::drop_in_place::<[A]>(&mut **self) // uses DerefMut
     }
 
     /// Discard the contents of the array.
@@ -516,4 +602,24 @@ mod test {
         assert_eq!(65536, chunk.len());
         assert_eq!(Some(()), chunk.pop());
     }
+
+    #[test]
+    fn low_align_base() {
+        let mut chunk: InlineArray<String, [u8; 512]> = InlineArray::new();
+        chunk.push("Hello".to_owned());
+        assert_eq!(chunk[0], "Hello");
+    }
+
+    #[test]
+    fn big_align_elem() {
+        #[repr(align(256))]
+        struct BigAlign(usize);
+
+        let mut chunk: InlineArray<BigAlign, [usize; 256]> = InlineArray::new();
+        chunk.push(BigAlign(42));
+        assert_eq!(
+            chunk.get(0).unwrap() as *const _ as usize % mem::align_of::<BigAlign>(),
+            0
+        );
+    }
 }