Repository: rustls/rustls (language: rust)

Issue:
Poor asymptotic performance when reading plaintext incrementally
If we receive a large appdata message (16KB) and the application reads it one byte at a time, we spend a silly amount of time in memmove. That is because:

- `ChunkVecBuffer::read` for one byte has complexity of O(N)
- the application must call it once for each byte

So we end up with accidentally quadratic overall performance.

This also affects our benchmarking: currently each 16KB message is received in two 8KB reads, with 8KB of wasted memmove.


Discussion / hints:

Fix patch:
diff --git a/rustls/examples/internal/bench_impl.rs b/rustls/examples/internal/bench_impl.rs
index a2bf5981e20..347a0edea61 100644
--- a/rustls/examples/internal/bench_impl.rs
+++ b/rustls/examples/internal/bench_impl.rs
@@ -1051,10 +1051,10 @@ where
     LS: SideData,
     RS: SideData,
 {
-    let mut tls_buf = [0u8; 262144];
+    let mut tls_buf = vec![0u8; 262_144];
     let mut read_time = 0f64;
     let mut data_left = expect_data;
-    let mut data_buf = [0u8; 8192];
+    let mut data_buf = vec![0u8; 16_384];
 
     loop {
         let mut sz = 0;
diff --git a/rustls/src/compress.rs b/rustls/src/compress.rs
index 5ac01477938..e6a2f028d96 100644
--- a/rustls/src/compress.rs
+++ b/rustls/src/compress.rs
@@ -445,7 +445,7 @@ impl CompressionCacheEntry {
 }
 
 #[cfg(all(test, any(feature = "brotli", feature = "zlib")))]
-pub mod tests {
+mod tests {
     use std::{println, vec};
 
     use super::*;
diff --git a/rustls/src/crypto/aws_lc_rs/ticketer.rs b/rustls/src/crypto/aws_lc_rs/ticketer.rs
index 5621b1cde4a..d6ef0876d1f 100644
--- a/rustls/src/crypto/aws_lc_rs/ticketer.rs
+++ b/rustls/src/crypto/aws_lc_rs/ticketer.rs
@@ -14,6 +14,7 @@ use aws_lc_rs::{hmac, iv};
 use super::ring_like::rand::{SecureRandom, SystemRandom};
 use super::unspecified_err;
 use crate::error::Error;
+#[cfg(debug_assertions)]
 use crate::log::debug;
 use crate::polyfill::try_split_at;
 use crate::rand::GetRandomFailed;
diff --git a/rustls/src/crypto/ring/ticketer.rs b/rustls/src/crypto/ring/ticketer.rs
index 5a74cb9ce31..3423f1ed654 100644
--- a/rustls/src/crypto/ring/ticketer.rs
+++ b/rustls/src/crypto/ring/ticketer.rs
@@ -10,6 +10,7 @@ use subtle::ConstantTimeEq;
 use super::ring_like::aead;
 use super::ring_like::rand::{SecureRandom, SystemRandom};
 use crate::error::Error;
+#[cfg(debug_assertions)]
 use crate::log::debug;
 use crate::polyfill::try_split_at;
 use crate::rand::GetRandomFailed;
diff --git a/rustls/src/vecbuf.rs b/rustls/src/vecbuf.rs
index b2377797d63..813b99f4dce 100644
--- a/rustls/src/vecbuf.rs
+++ b/rustls/src/vecbuf.rs
@@ -1,6 +1,6 @@
 use alloc::collections::VecDeque;
 use alloc::vec::Vec;
-use core::cmp;
+use core::{cmp, mem};
 #[cfg(feature = "std")]
 use std::io;
 #[cfg(feature = "std")]
@@ -9,18 +9,27 @@ use std::io::Read;
 #[cfg(feature = "std")]
 use crate::msgs::message::OutboundChunks;
 
-/// This is a byte buffer that is built from a vector
-/// of byte vectors.  This avoids extra copies when
-/// appending a new byte vector, at the expense of
-/// more complexity when reading out.
+/// This is a byte buffer that is built from a deque of byte vectors.
+///
+/// This avoids extra copies when appending a new byte vector,
+/// at the expense of more complexity when reading out.
 pub(crate) struct ChunkVecBuffer {
+    /// How many bytes have been consumed in the first chunk.
+    ///
+    /// Invariant: zero if `chunks.is_empty()`
+    /// Invariant: 0 <= `prefix_used` < `chunks[0].len()`
+    prefix_used: usize,
+
     chunks: VecDeque<Vec<u8>>,
+
+    /// The total upper limit (in bytes) of this object.
     limit: Option<usize>,
 }
 
 impl ChunkVecBuffer {
     pub(crate) fn new(limit: Option<usize>) -> Self {
         Self {
+            prefix_used: 0,
             chunks: VecDeque::new(),
             limit,
         }
@@ -44,11 +53,10 @@ impl ChunkVecBuffer {
 
     /// How many bytes we're storing
     pub(crate) fn len(&self) -> usize {
-        let mut len = 0;
-        for ch in &self.chunks {
-            len += ch.len();
-        }
-        len
+        self.chunks
+            .iter()
+            .fold(0usize, |acc, chunk| acc + chunk.len())
+            - self.prefix_used
     }
 
     /// For a proposed append of `len` bytes, how many
@@ -74,17 +82,26 @@ impl ChunkVecBuffer {
         len
     }
 
-    /// Take one of the chunks from this object.  This
-    /// function panics if the object `is_empty`.
+    /// Take one of the chunks from this object.
+    ///
+    /// This function returns `None` if the object `is_empty`.
     pub(crate) fn pop(&mut self) -> Option<Vec<u8>> {
-        self.chunks.pop_front()
+        let mut first = self.chunks.pop_front();
+
+        if let Some(first) = &mut first {
+            // slice off `prefix_used` if needed (uncommon)
+            let prefix = mem::take(&mut self.prefix_used);
+            first.drain(0..prefix);
+        }
+
+        first
     }
 
     #[cfg(read_buf)]
     /// Read data out of this object, writing it into `cursor`.
     pub(crate) fn read_buf(&mut self, mut cursor: core::io::BorrowedCursor<'_>) -> io::Result<()> {
         while !self.is_empty() && cursor.capacity() > 0 {
-            let chunk = self.chunks[0].as_slice();
+            let chunk = &self.chunks[0][self.prefix_used..];
             let used = cmp::min(chunk.len(), cursor.capacity());
             cursor.append(&chunk[..used]);
             self.consume(used);
@@ -116,9 +133,7 @@ impl ChunkVecBuffer {
         let mut offs = 0;
 
         while offs < buf.len() && !self.is_empty() {
-            let used = self.chunks[0]
-                .as_slice()
-                .read(&mut buf[offs..])?;
+            let used = (&self.chunks[0][self.prefix_used..]).read(&mut buf[offs..])?;
 
             self.consume(used);
             offs += used;
@@ -127,14 +142,18 @@ impl ChunkVecBuffer {
         Ok(offs)
     }
 
-    fn consume(&mut self, mut used: usize) {
-        while let Some(mut buf) = self.chunks.pop_front() {
-            if used < buf.len() {
-                buf.drain(..used);
-                self.chunks.push_front(buf);
+    fn consume(&mut self, used: usize) {
+        // first, mark the rightmost extent of the used buffer
+        self.prefix_used += used;
+
+        // then reduce `prefix_used` by discarding wholly-covered
+        // buffers
+        while let Some(buf) = self.chunks.front() {
+            if self.prefix_used < buf.len() {
                 break;
             } else {
-                used -= buf.len();
+                self.prefix_used -= buf.len();
+                self.chunks.pop_front();
             }
         }
     }
@@ -145,9 +164,11 @@ impl ChunkVecBuffer {
             return Ok(0);
         }
 
+        let mut prefix = self.prefix_used;
         let mut bufs = [io::IoSlice::new(&[]); 64];
         for (iov, chunk) in bufs.iter_mut().zip(self.chunks.iter()) {
-            *iov = io::IoSlice::new(chunk);
+            *iov = io::IoSlice::new(&chunk[prefix..]);
+            prefix = 0;
         }
         let len = cmp::min(bufs.len(), self.chunks.len());
         let used = wr.write_vectored(&bufs[..len])?;
@@ -158,6 +179,9 @@ impl ChunkVecBuffer {
 
 #[cfg(all(test, feature = "std"))]
 mod tests {
+    use alloc::vec;
+    use alloc::vec::Vec;
+
     use super::ChunkVecBuffer;
 
     #[test]
@@ -173,6 +197,48 @@ mod tests {
         assert_eq!(buf.to_vec(), b"helloworldhe".to_vec());
     }
 
+    #[test]
+    fn read_byte_by_byte() {
+        let mut cvb = ChunkVecBuffer::new(None);
+        cvb.append(b"test fixture data".to_vec());
+        assert!(!cvb.is_empty());
+        for expect in b"test fixture data" {
+            let mut byte = [0];
+            assert_eq!(cvb.read(&mut byte).unwrap(), 1);
+            assert_eq!(byte[0], *expect);
+        }
+
+        assert_eq!(cvb.read(&mut [0]).unwrap(), 0);
+    }
+
+    #[test]
+    fn every_possible_chunk_interleaving() {
+        let input = (0..=0xffu8)
+            .cycle()
+            .take(4096)
+            .collect::<Vec<u8>>();
+
+        for input_chunk_len in 1..64usize {
+            for output_chunk_len in 1..65usize {
+                std::println!("check input={input_chunk_len} output={output_chunk_len}");
+                let mut cvb = ChunkVecBuffer::new(None);
+                for chunk in input.chunks(input_chunk_len) {
+                    cvb.append(chunk.to_vec());
+                }
+
+                assert_eq!(cvb.len(), input.len());
+                let mut buf = vec![0u8; output_chunk_len];
+
+                for expect in input.chunks(output_chunk_len) {
+                    assert_eq!(expect.len(), cvb.read(&mut buf).unwrap());
+                    assert_eq!(expect, &buf[..expect.len()]);
+                }
+
+                assert_eq!(cvb.read(&mut [0]).unwrap(), 0);
+            }
+        }
+    }
+
     #[cfg(read_buf)]
     #[test]
     fn read_buf() {
@@ -208,3 +274,51 @@ mod tests {
         }
     }
 }
+
+#[cfg(bench)]
+mod benchmarks {
+    use alloc::vec;
+
+    use super::ChunkVecBuffer;
+
+    #[bench]
+    fn read_one_byte_from_large_message(b: &mut test::Bencher) {
+        b.iter(|| {
+            let mut cvb = ChunkVecBuffer::new(None);
+            cvb.append(vec![0u8; 16_384]);
+            assert_eq!(1, cvb.read(&mut [0u8]).unwrap());
+        });
+    }
+
+    #[bench]
+    fn read_all_individual_from_large_message(b: &mut test::Bencher) {
+        b.iter(|| {
+            let mut cvb = ChunkVecBuffer::new(None);
+            cvb.append(vec![0u8; 16_384]);
+            loop {
+                if let Ok(0) = cvb.read(&mut [0u8]) {
+                    break;
+                }
+            }
+        });
+    }
+
+    #[bench]
+    fn read_half_bytes_from_large_message(b: &mut test::Bencher) {
+        b.iter(|| {
+            let mut cvb = ChunkVecBuffer::new(None);
+            cvb.append(vec![0u8; 16_384]);
+            assert_eq!(8192, cvb.read(&mut [0u8; 8192]).unwrap());
+            assert_eq!(8192, cvb.read(&mut [0u8; 8192]).unwrap());
+        });
+    }
+
+    #[bench]
+    fn read_entire_large_message(b: &mut test::Bencher) {
+        b.iter(|| {
+            let mut cvb = ChunkVecBuffer::new(None);
+            cvb.append(vec![0u8; 16_384]);
+            assert_eq!(16_384, cvb.read(&mut [0u8; 16_384]).unwrap());
+        });
+    }
+}


Test patch: