diff options
Diffstat (limited to 'third_party/rust/neqo-qpack')
18 files changed, 6296 insertions, 0 deletions
diff --git a/third_party/rust/neqo-qpack/.cargo-checksum.json b/third_party/rust/neqo-qpack/.cargo-checksum.json new file mode 100644 index 0000000000..5fa989ca5f --- /dev/null +++ b/third_party/rust/neqo-qpack/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.toml":"880cdcddc73dceafa69773ae482a1eaaced927504856130b0cc15ec91ac31e59","src/decoder.rs":"8bd336c91cca989883106a9d0bf26b117d224e0e7643960c3e97d0168d1853c4","src/decoder_instructions.rs":"2205c7635b8f0c568f6fe9a63c17028eaf8d29a9b5ac7136b6554cc7fbf35038","src/encoder.rs":"b888a819595fec47037d508b943f5ff04ed52ea376bef1f90e08edc6576e773c","src/encoder_instructions.rs":"1eb4f6eee2d9ff16f96dc5bf80dae9bc04316126f6eca933fb51dbd9218a439c","src/header_block.rs":"9ee3bc4189ae36ae0a926295f6f8b3a1169463a19ccbc65e6d588c8b317020ad","src/huffman.rs":"3a9edaf827343ec6e43cfd50fcc0d0077287947160ae630da5c3ddaaefedd010","src/huffman_decode_helper.rs":"2970c57f052878b727c2f764490c54184f5c2608e1d6aa961c3b01509e290122","src/huffman_table.rs":"06fea766a6276ac56c7ee0326faed800a742c15fda1f33bf2513e6cc6a5e6d27","src/lib.rs":"6e25612bb30f0e4361566662da1e5353131ae12f97938c6ac3b2dafbf6a8bc86","src/prefix.rs":"72c587c40aef4ed38cf13b2de91091d671611679be2a9da6f0b24abafaf50dc5","src/qlog.rs":"7618085e27bb3fb1f4d1c73ba501b9a293723293c4020b7cc4129676eb278131","src/qpack_send_buf.rs":"bc86cce786b6c8a468aed8d436ec4a8a86b3d4a917495fff7931ba4026c36c47","src/reader.rs":"be265cc8c317512f266fafdcc835d0e413caf5280a7cc945bfe6e7e849529d67","src/static_table.rs":"fda9d5c6f38f94b0bf92d3afdf8432dce6e27e189736596e16727090c77b78ec","src/stats.rs":"624dfa3b40858c304097bb0ce5b1be1bb4d7916b1abfc222f1aa705907009730","src/table.rs":"f7091bdd9ad1f8fe3b2298a7dbfd3d285c212d69569cda54f9bcf251cb758a21"},"package":null}
\ No newline at end of file diff --git a/third_party/rust/neqo-qpack/Cargo.toml b/third_party/rust/neqo-qpack/Cargo.toml new file mode 100644 index 0000000000..daa1bf8029 --- /dev/null +++ b/third_party/rust/neqo-qpack/Cargo.toml @@ -0,0 +1,23 @@ +[package] +name = "neqo-qpack" +version = "0.6.3" +authors = ["Dragana Damjanovic <dragana.damjano@gmail.com>"] +edition = "2018" +rust-version = "1.57.0" +license = "MIT/Apache-2.0" + +[dependencies] +neqo-common = { path = "./../neqo-common" } +neqo-transport = { path = "./../neqo-transport" } +neqo-crypto = { path = "./../neqo-crypto" } +log = {version = "0.4.0", default-features = false} +static_assertions = "1.1.0" +qlog = "0.4.0" +lazy_static = "1.3.0" + +[dev-dependencies] +test-fixture = { path = "../test-fixture" } + +[features] +default = ["deny-warnings"] +deny-warnings = [] diff --git a/third_party/rust/neqo-qpack/src/decoder.rs b/third_party/rust/neqo-qpack/src/decoder.rs new file mode 100644 index 0000000000..e5cbfa09d0 --- /dev/null +++ b/third_party/rust/neqo-qpack/src/decoder.rs @@ -0,0 +1,804 @@ +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use crate::decoder_instructions::DecoderInstruction; +use crate::encoder_instructions::{DecodedEncoderInstruction, EncoderInstructionReader}; +use crate::header_block::{HeaderDecoder, HeaderDecoderResult}; +use crate::qpack_send_buf::QpackData; +use crate::reader::ReceiverConnWrapper; +use crate::stats::Stats; +use crate::table::HeaderTable; +use crate::{Error, QpackSettings, Res}; +use neqo_common::{qdebug, Header}; +use neqo_transport::{Connection, StreamId}; +use std::convert::TryFrom; + +pub const QPACK_UNI_STREAM_TYPE_DECODER: u64 = 0x3; + +#[derive(Debug)] +pub struct QPackDecoder { + instruction_reader: EncoderInstructionReader, + table: HeaderTable, + acked_inserts: u64, + max_entries: u64, + send_buf: QpackData, + local_stream_id: Option<StreamId>, + max_table_size: u64, + max_blocked_streams: usize, + blocked_streams: Vec<(StreamId, u64)>, //stream_id and requested inserts count. + stats: Stats, +} + +impl QPackDecoder { + /// # Panics + /// If settings include invalid values. + #[must_use] + pub fn new(qpack_settings: &QpackSettings) -> Self { + qdebug!("Decoder: creating a new qpack decoder."); + let mut send_buf = QpackData::default(); + send_buf.encode_varint(QPACK_UNI_STREAM_TYPE_DECODER); + Self { + instruction_reader: EncoderInstructionReader::new(), + table: HeaderTable::new(false), + acked_inserts: 0, + max_entries: qpack_settings.max_table_size_decoder >> 5, + send_buf, + local_stream_id: None, + max_table_size: qpack_settings.max_table_size_decoder, + max_blocked_streams: usize::try_from(qpack_settings.max_blocked_streams).unwrap(), + blocked_streams: Vec::new(), + stats: Stats::default(), + } + } + + #[must_use] + fn capacity(&self) -> u64 { + self.table.capacity() + } + + #[must_use] + pub fn get_max_table_size(&self) -> u64 { + self.max_table_size + } + + /// # Panics + /// If the number of blocked streams is too large. + #[must_use] + pub fn get_blocked_streams(&self) -> u16 { + u16::try_from(self.max_blocked_streams).unwrap() + } + + /// returns a list of unblocked streams + /// # Errors + /// May return: `ClosedCriticalStream` if stream has been closed or `EncoderStream` + /// in case of any other transport error. + pub fn receive(&mut self, conn: &mut Connection, stream_id: StreamId) -> Res<Vec<StreamId>> { + let base_old = self.table.base(); + self.read_instructions(conn, stream_id) + .map_err(|e| map_error(&e))?; + let base_new = self.table.base(); + if base_old == base_new { + return Ok(Vec::new()); + } + + let r = self + .blocked_streams + .iter() + .filter_map(|(id, req)| if *req <= base_new { Some(*id) } else { None }) + .collect::<Vec<_>>(); + self.blocked_streams.retain(|(_, req)| *req > base_new); + Ok(r) + } + + fn read_instructions(&mut self, conn: &mut Connection, stream_id: StreamId) -> Res<()> { + let mut recv = ReceiverConnWrapper::new(conn, stream_id); + loop { + match self.instruction_reader.read_instructions(&mut recv) { + Ok(instruction) => self.execute_instruction(instruction)?, + Err(Error::NeedMoreData) => break Ok(()), + Err(e) => break Err(e), + } + } + } + + fn execute_instruction(&mut self, instruction: DecodedEncoderInstruction) -> Res<()> { + match instruction { + DecodedEncoderInstruction::Capacity { value } => self.set_capacity(value)?, + DecodedEncoderInstruction::InsertWithNameRefStatic { index, value } => { + Error::map_error( + self.table.insert_with_name_ref(true, index, &value), + Error::EncoderStream, + )?; + self.stats.dynamic_table_inserts += 1; + } + DecodedEncoderInstruction::InsertWithNameRefDynamic { index, value } => { + Error::map_error( + self.table.insert_with_name_ref(false, index, &value), + Error::EncoderStream, + )?; + self.stats.dynamic_table_inserts += 1; + } + DecodedEncoderInstruction::InsertWithNameLiteral { name, value } => { + Error::map_error( + self.table.insert(&name, &value).map(|_| ()), + Error::EncoderStream, + )?; + self.stats.dynamic_table_inserts += 1; + } + DecodedEncoderInstruction::Duplicate { index } => { + Error::map_error(self.table.duplicate(index), Error::EncoderStream)?; + self.stats.dynamic_table_inserts += 1; + } + DecodedEncoderInstruction::NoInstruction => { + unreachable!("This can be call only with an instruction."); + } + } + Ok(()) + } + + fn set_capacity(&mut self, cap: u64) -> Res<()> { + qdebug!([self], "received instruction capacity cap={}", cap); + if cap > self.max_table_size { + return Err(Error::EncoderStream); + } + self.table.set_capacity(cap) + } + + fn header_ack(&mut self, stream_id: StreamId, required_inserts: u64) { + DecoderInstruction::HeaderAck { stream_id }.marshal(&mut self.send_buf); + if required_inserts > self.acked_inserts { + self.acked_inserts = required_inserts; + } + } + + pub fn cancel_stream(&mut self, stream_id: StreamId) { + if self.table.capacity() > 0 { + self.blocked_streams.retain(|(id, _)| *id != stream_id); + DecoderInstruction::StreamCancellation { stream_id }.marshal(&mut self.send_buf); + } + } + + /// # Errors + /// May return an error in case of any transport error. TODO: define transport errors. + /// # Panics + /// Never, but rust doesn't know that. + #[allow(clippy::map_err_ignore)] + pub fn send(&mut self, conn: &mut Connection) -> Res<()> { + // Encode increment instruction if needed. + let increment = self.table.base() - self.acked_inserts; + if increment > 0 { + DecoderInstruction::InsertCountIncrement { increment }.marshal(&mut self.send_buf); + self.acked_inserts = self.table.base(); + } + if self.send_buf.len() != 0 && self.local_stream_id.is_some() { + let r = conn + .stream_send(self.local_stream_id.unwrap(), &self.send_buf[..]) + .map_err(|_| Error::DecoderStream)?; + qdebug!([self], "{} bytes sent.", r); + self.send_buf.read(r as usize); + } + Ok(()) + } + + /// # Errors + /// May return `DecompressionFailed` if header block is incorrect or incomplete. + pub fn refers_dynamic_table(&self, buf: &[u8]) -> Res<bool> { + HeaderDecoder::new(buf).refers_dynamic_table(self.max_entries, self.table.base()) + } + + /// This function returns None if the stream is blocked waiting for table insertions. + /// 'buf' must contain the complete header block. + /// # Errors + /// May return `DecompressionFailed` if header block is incorrect or incomplete. + /// # Panics + /// When there is a programming error. + pub fn decode_header_block( + &mut self, + buf: &[u8], + stream_id: StreamId, + ) -> Res<Option<Vec<Header>>> { + qdebug!([self], "decode header block."); + let mut decoder = HeaderDecoder::new(buf); + + match decoder.decode_header_block(&self.table, self.max_entries, self.table.base()) { + Ok(HeaderDecoderResult::Blocked(req_insert_cnt)) => { + if self.blocked_streams.len() > self.max_blocked_streams { + Err(Error::DecompressionFailed) + } else { + let r = self + .blocked_streams + .iter() + .filter_map(|(id, req)| if *id == stream_id { Some(*req) } else { None }) + .collect::<Vec<_>>(); + if !r.is_empty() { + debug_assert!(r.len() == 1); + debug_assert!(r[0] == req_insert_cnt); + return Ok(None); + } + self.blocked_streams.push((stream_id, req_insert_cnt)); + Ok(None) + } + } + Ok(HeaderDecoderResult::Headers(h)) => { + if decoder.get_req_insert_cnt() != 0 { + self.header_ack(stream_id, decoder.get_req_insert_cnt()); + self.stats.dynamic_table_references += 1; + } + Ok(Some(h)) + } + Err(_) => Err(Error::DecompressionFailed), + } + } + + /// # Panics + /// When a stream has already been added. + pub fn add_send_stream(&mut self, stream_id: StreamId) { + assert!( + self.local_stream_id.is_none(), + "Adding multiple local streams" + ); + self.local_stream_id = Some(stream_id); + } + + #[must_use] + pub fn local_stream_id(&self) -> Option<StreamId> { + self.local_stream_id + } + + #[must_use] + pub fn stats(&self) -> Stats { + self.stats.clone() + } +} + +impl ::std::fmt::Display for QPackDecoder { + fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result { + write!(f, "QPackDecoder {}", self.capacity()) + } +} + +fn map_error(err: &Error) -> Error { + if *err == Error::ClosedCriticalStream { + Error::ClosedCriticalStream + } else { + Error::EncoderStream + } +} + +#[cfg(test)] +mod tests { + use super::{Connection, Error, QPackDecoder, Res}; + use crate::QpackSettings; + use neqo_common::Header; + use neqo_transport::{StreamId, StreamType}; + use std::convert::TryFrom; + use std::mem; + use test_fixture::now; + + const STREAM_0: StreamId = StreamId::new(0); + + struct TestDecoder { + decoder: QPackDecoder, + send_stream_id: StreamId, + recv_stream_id: StreamId, + conn: Connection, + peer_conn: Connection, + } + + fn connect() -> TestDecoder { + let (mut conn, mut peer_conn) = test_fixture::connect(); + + // create a stream + let recv_stream_id = peer_conn.stream_create(StreamType::UniDi).unwrap(); + let send_stream_id = conn.stream_create(StreamType::UniDi).unwrap(); + + // create a decoder + let mut decoder = QPackDecoder::new(&QpackSettings { + max_table_size_encoder: 0, + max_table_size_decoder: 300, + max_blocked_streams: 100, + }); + decoder.add_send_stream(send_stream_id); + + TestDecoder { + decoder, + send_stream_id, + recv_stream_id, + conn, + peer_conn, + } + } + + fn recv_instruction(decoder: &mut TestDecoder, encoder_instruction: &[u8], res: &Res<()>) { + let _ = decoder + .peer_conn + .stream_send(decoder.recv_stream_id, encoder_instruction) + .unwrap(); + let out = decoder.peer_conn.process(None, now()); + mem::drop(decoder.conn.process(out.dgram(), now())); + assert_eq!( + decoder + .decoder + .read_instructions(&mut decoder.conn, decoder.recv_stream_id), + *res + ); + } + + fn send_instructions_and_check(decoder: &mut TestDecoder, decoder_instruction: &[u8]) { + decoder.decoder.send(&mut decoder.conn).unwrap(); + let out = decoder.conn.process(None, now()); + mem::drop(decoder.peer_conn.process(out.dgram(), now())); + let mut buf = [0_u8; 100]; + let (amount, fin) = decoder + .peer_conn + .stream_recv(decoder.send_stream_id, &mut buf) + .unwrap(); + assert!(!fin); + assert_eq!(&buf[..amount], decoder_instruction); + } + + fn decode_headers( + decoder: &mut TestDecoder, + header_block: &[u8], + headers: &[Header], + stream_id: StreamId, + ) { + let decoded_headers = decoder + .decoder + .decode_header_block(header_block, stream_id) + .unwrap(); + let h = decoded_headers.unwrap(); + assert_eq!(h, headers); + } + + fn test_instruction( + capacity: u64, + instruction: &[u8], + res: &Res<()>, + decoder_instruction: &[u8], + check_capacity: u64, + ) { + let mut decoder = connect(); + + if capacity > 0 { + assert!(decoder.decoder.set_capacity(capacity).is_ok()); + } + + // recv an instruction + recv_instruction(&mut decoder, instruction, res); + + // send decoder instruction and check that is what we expect. + send_instructions_and_check(&mut decoder, decoder_instruction); + + if check_capacity > 0 { + assert_eq!(decoder.decoder.capacity(), check_capacity); + } + } + + // test insert_with_name_ref which fails because there is not enough space in the table + #[test] + fn test_recv_insert_with_name_ref_1() { + test_instruction( + 0, + &[0xc4, 0x04, 0x31, 0x32, 0x33, 0x34], + &Err(Error::EncoderStream), + &[0x03], + 0, + ); + } + + // test insert_name_ref that succeeds + #[test] + fn test_recv_insert_with_name_ref_2() { + test_instruction( + 100, + &[0xc4, 0x04, 0x31, 0x32, 0x33, 0x34], + &Ok(()), + &[0x03, 0x01], + 0, + ); + } + + // test insert with name literal - succeeds + #[test] + fn test_recv_insert_with_name_litarel_2() { + test_instruction( + 200, + &[ + 0x4e, 0x63, 0x6f, 0x6e, 0x74, 0x65, 0x6e, 0x74, 0x2d, 0x6c, 0x65, 0x6e, 0x67, 0x74, + 0x68, 0x04, 0x31, 0x32, 0x33, 0x34, + ], + &Ok(()), + &[0x03, 0x01], + 0, + ); + } + + #[test] + fn test_recv_change_capacity() { + test_instruction(0, &[0x3f, 0xa9, 0x01], &Ok(()), &[0x03], 200); + } + + #[test] + fn test_recv_change_capacity_too_big() { + test_instruction( + 0, + &[0x3f, 0xf1, 0x02], + &Err(Error::EncoderStream), + &[0x03], + 0, + ); + } + + // this test tests header decoding, the header acks command and the insert count increment command. + #[test] + fn test_duplicate() { + let mut decoder = connect(); + + assert!(decoder.decoder.set_capacity(100).is_ok()); + + // receive an instruction + recv_instruction( + &mut decoder, + &[ + 0x4e, 0x63, 0x6f, 0x6e, 0x74, 0x65, 0x6e, 0x74, 0x2d, 0x6c, 0x65, 0x6e, 0x67, 0x74, + 0x68, 0x04, 0x31, 0x32, 0x33, 0x34, + ], + &Ok(()), + ); + + // receive the second instruction, a duplicate instruction. + recv_instruction(&mut decoder, &[0x00], &Ok(())); + + send_instructions_and_check(&mut decoder, &[0x03, 0x02]); + } + + struct TestElement { + pub headers: Vec<Header>, + pub header_block: &'static [u8], + pub encoder_inst: &'static [u8], + } + + #[test] + fn test_encode_incr_encode_header_ack_some() { + // 1. Decoder receives an instruction (header and value both as literal) + // 2. Decoder process the instruction and sends an increment instruction. + // 3. Decoder receives another two instruction (header and value both as literal) and + // a header block. + // 4. Now it sends only a header ack and an increment instruction with increment==1. + let headers = vec![ + Header::new("my-headera", "my-valuea"), + Header::new("my-headerb", "my-valueb"), + ]; + let header_block = &[0x03, 0x81, 0x10, 0x11]; + let first_encoder_inst = &[ + 0x4a, 0x6d, 0x79, 0x2d, 0x68, 0x65, 0x61, 0x64, 0x65, 0x72, 0x61, 0x09, 0x6d, 0x79, + 0x2d, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x61, + ]; + let second_encoder_inst = &[ + 0x4a, 0x6d, 0x79, 0x2d, 0x68, 0x65, 0x61, 0x64, 0x65, 0x72, 0x62, 0x09, 0x6d, 0x79, + 0x2d, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x62, 0x4a, 0x6d, 0x79, 0x2d, 0x68, 0x65, 0x61, + 0x64, 0x65, 0x72, 0x63, 0x09, 0x6d, 0x79, 0x2d, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x63, + ]; + + let mut decoder = connect(); + + assert!(decoder.decoder.set_capacity(200).is_ok()); + + recv_instruction(&mut decoder, first_encoder_inst, &Ok(())); + + send_instructions_and_check(&mut decoder, &[0x03, 0x1]); + + recv_instruction(&mut decoder, second_encoder_inst, &Ok(())); + + decode_headers(&mut decoder, header_block, &headers, STREAM_0); + + send_instructions_and_check(&mut decoder, &[0x80, 0x1]); + } + + #[test] + fn test_encode_incr_encode_header_ack_all() { + // 1. Decoder receives an instruction (header and value both as literal) + // 2. Decoder process the instruction and sends an increment instruction. + // 3. Decoder receives another instruction (header and value both as literal) and + // a header block. + // 4. Now it sends only a header ack. + let headers = vec![ + Header::new("my-headera", "my-valuea"), + Header::new("my-headerb", "my-valueb"), + ]; + let header_block = &[0x03, 0x81, 0x10, 0x11]; + let first_encoder_inst = &[ + 0x4a, 0x6d, 0x79, 0x2d, 0x68, 0x65, 0x61, 0x64, 0x65, 0x72, 0x61, 0x09, 0x6d, 0x79, + 0x2d, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x61, + ]; + let second_encoder_inst = &[ + 0x4a, 0x6d, 0x79, 0x2d, 0x68, 0x65, 0x61, 0x64, 0x65, 0x72, 0x62, 0x09, 0x6d, 0x79, + 0x2d, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x62, + ]; + + let mut decoder = connect(); + + assert!(decoder.decoder.set_capacity(200).is_ok()); + + recv_instruction(&mut decoder, first_encoder_inst, &Ok(())); + + send_instructions_and_check(&mut decoder, &[0x03, 0x1]); + + recv_instruction(&mut decoder, second_encoder_inst, &Ok(())); + + decode_headers(&mut decoder, header_block, &headers, STREAM_0); + + send_instructions_and_check(&mut decoder, &[0x80]); + } + + #[test] + fn test_header_ack_all() { + // Send two instructions to insert values into the dynamic table and then send a header + // that references them both. The result should be only a header acknowledgement. + let headers = vec![ + Header::new("my-headera", "my-valuea"), + Header::new("my-headerb", "my-valueb"), + ]; + let header_block = &[0x03, 0x81, 0x10, 0x11]; + let encoder_inst = &[ + 0x4a, 0x6d, 0x79, 0x2d, 0x68, 0x65, 0x61, 0x64, 0x65, 0x72, 0x61, 0x09, 0x6d, 0x79, + 0x2d, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x61, 0x4a, 0x6d, 0x79, 0x2d, 0x68, 0x65, 0x61, + 0x64, 0x65, 0x72, 0x62, 0x09, 0x6d, 0x79, 0x2d, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x62, + ]; + + let mut decoder = connect(); + + assert!(decoder.decoder.set_capacity(200).is_ok()); + + recv_instruction(&mut decoder, encoder_inst, &Ok(())); + + decode_headers(&mut decoder, header_block, &headers, STREAM_0); + + send_instructions_and_check(&mut decoder, &[0x03, 0x80]); + } + + #[test] + fn test_header_ack_and_incr_instruction() { + // Send two instructions to insert values into the dynamic table and then send a header + // that references only the first. The result should be a header acknowledgement and a + // increment instruction. + let headers = vec![Header::new("my-headera", "my-valuea")]; + let header_block = &[0x02, 0x80, 0x10]; + let encoder_inst = &[ + 0x4a, 0x6d, 0x79, 0x2d, 0x68, 0x65, 0x61, 0x64, 0x65, 0x72, 0x61, 0x09, 0x6d, 0x79, + 0x2d, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x61, 0x4a, 0x6d, 0x79, 0x2d, 0x68, 0x65, 0x61, + 0x64, 0x65, 0x72, 0x62, 0x09, 0x6d, 0x79, 0x2d, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x62, + ]; + + let mut decoder = connect(); + + assert!(decoder.decoder.set_capacity(200).is_ok()); + + recv_instruction(&mut decoder, encoder_inst, &Ok(())); + + decode_headers(&mut decoder, header_block, &headers, STREAM_0); + + send_instructions_and_check(&mut decoder, &[0x03, 0x80, 0x01]); + } + + #[test] + fn test_header_block_decoder() { + let test_cases: [TestElement; 6] = [ + // test a header with ref to static - encode_indexed + TestElement { + headers: vec![Header::new(":method", "GET")], + header_block: &[0x00, 0x00, 0xd1], + encoder_inst: &[], + }, + // test encode_literal_with_name_ref + TestElement { + headers: vec![Header::new(":path", "/somewhere")], + header_block: &[ + 0x00, 0x00, 0x51, 0x0a, 0x2f, 0x73, 0x6f, 0x6d, 0x65, 0x77, 0x68, 0x65, 0x72, + 0x65, + ], + encoder_inst: &[], + }, + // test adding a new header and encode_post_base_index, also test fix_header_block_prefix + TestElement { + headers: vec![Header::new("my-header", "my-value")], + header_block: &[0x02, 0x80, 0x10], + encoder_inst: &[ + 0x49, 0x6d, 0x79, 0x2d, 0x68, 0x65, 0x61, 0x64, 0x65, 0x72, 0x08, 0x6d, 0x79, + 0x2d, 0x76, 0x61, 0x6c, 0x75, 0x65, + ], + }, + // test encode_indexed with a ref to dynamic table. + TestElement { + headers: vec![Header::new("my-header", "my-value")], + header_block: &[0x02, 0x00, 0x80], + encoder_inst: &[], + }, + // test encode_literal_with_name_ref. + TestElement { + headers: vec![Header::new("my-header", "my-value2")], + header_block: &[ + 0x02, 0x00, 0x40, 0x09, 0x6d, 0x79, 0x2d, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x32, + ], + encoder_inst: &[], + }, + // test multiple headers + TestElement { + headers: vec![ + Header::new(":method", "GET"), + Header::new(":path", "/somewhere"), + Header::new(":authority", "example.com"), + Header::new(":scheme", "https"), + ], + header_block: &[ + 0x00, 0x01, 0xd1, 0x51, 0x0a, 0x2f, 0x73, 0x6f, 0x6d, 0x65, 0x77, 0x68, 0x65, + 0x72, 0x65, 0x50, 0x0b, 0x65, 0x78, 0x61, 0x6d, 0x70, 0x6c, 0x65, 0x2e, 0x63, + 0x6f, 0x6d, 0xd7, + ], + encoder_inst: &[], + }, + ]; + + let mut decoder = connect(); + + assert!(decoder.decoder.set_capacity(200).is_ok()); + + for (i, t) in test_cases.iter().enumerate() { + // receive an instruction + if !t.encoder_inst.is_empty() { + recv_instruction(&mut decoder, t.encoder_inst, &Ok(())); + } + + decode_headers( + &mut decoder, + t.header_block, + &t.headers, + StreamId::from(u64::try_from(i).unwrap()), + ); + } + + // test header acks and the insert count increment command + send_instructions_and_check(&mut decoder, &[0x03, 0x82, 0x83, 0x84]); + } + + #[test] + fn test_header_block_decoder_huffman() { + let test_cases: [TestElement; 6] = [ + // test a header with ref to static - encode_indexed + TestElement { + headers: vec![Header::new(":method", "GET")], + header_block: &[0x00, 0x00, 0xd1], + encoder_inst: &[], + }, + // test encode_literal_with_name_ref + TestElement { + headers: vec![Header::new(":path", "/somewhere")], + header_block: &[ + 0x00, 0x00, 0x51, 0x87, 0x61, 0x07, 0xa4, 0xbe, 0x27, 0x2d, 0x85, + ], + encoder_inst: &[], + }, + // test adding a new header and encode_post_base_index, also test fix_header_block_prefix + TestElement { + headers: vec![Header::new("my-header", "my-value")], + header_block: &[0x02, 0x80, 0x10], + encoder_inst: &[ + 0x67, 0xa7, 0xd2, 0xd3, 0x94, 0x72, 0x16, 0xcf, 0x86, 0xa7, 0xd2, 0xdd, 0xc7, + 0x45, 0xa5, + ], + }, + // test encode_indexed with a ref to dynamic table. + TestElement { + headers: vec![Header::new("my-header", "my-value")], + header_block: &[0x02, 0x00, 0x80], + encoder_inst: &[], + }, + // test encode_literal_with_name_ref. + TestElement { + headers: vec![Header::new("my-header", "my-value2")], + header_block: &[ + 0x02, 0x00, 0x40, 0x87, 0xa7, 0xd2, 0xdd, 0xc7, 0x45, 0xa5, 0x17, + ], + encoder_inst: &[], + }, + // test multiple headers + TestElement { + headers: vec![ + Header::new(":method", "GET"), + Header::new(":path", "/somewhere"), + Header::new(":authority", "example.com"), + Header::new(":scheme", "https"), + ], + header_block: &[ + 0x00, 0x01, 0xd1, 0x51, 0x87, 0x61, 0x07, 0xa4, 0xbe, 0x27, 0x2d, 0x85, 0x50, + 0x88, 0x2f, 0x91, 0xd3, 0x5d, 0x05, 0x5c, 0x87, 0xa7, 0xd7, + ], + encoder_inst: &[], + }, + ]; + + let mut decoder = connect(); + + assert!(decoder.decoder.set_capacity(200).is_ok()); + + for (i, t) in test_cases.iter().enumerate() { + // receive an instruction. + if !t.encoder_inst.is_empty() { + recv_instruction(&mut decoder, t.encoder_inst, &Ok(())); + } + + decode_headers( + &mut decoder, + t.header_block, + &t.headers, + StreamId::from(u64::try_from(i).unwrap()), + ); + } + + // test header acks and the insert count increment command + send_instructions_and_check(&mut decoder, &[0x03, 0x82, 0x83, 0x84]); + } + + #[test] + fn test_subtract_overflow_in_header_ack() { + const HEADER_BLOCK_1: &[u8] = &[0x03, 0x81, 0x10, 0x11]; + const ENCODER_INST: &[u8] = &[ + 0x4a, 0x6d, 0x79, 0x2d, 0x68, 0x65, 0x61, 0x64, 0x65, 0x72, 0x61, 0x09, 0x6d, 0x79, + 0x2d, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x61, 0x4a, 0x6d, 0x79, 0x2d, 0x68, 0x65, 0x61, + 0x64, 0x65, 0x72, 0x62, 0x09, 0x6d, 0x79, 0x2d, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x62, + ]; + const HEADER_BLOCK_2: &[u8] = &[0x02, 0x80, 0x10]; + // Test for issue https://github.com/mozilla/neqo/issues/475 + // Send two instructions to insert values into the dynamic table and send a header + // that references them both. This will increase number of acked inserts in the table + // to 2. Then send a header that references only one of them which shouldn't increase + // number of acked inserts. + let headers = vec![ + Header::new("my-headera", "my-valuea"), + Header::new("my-headerb", "my-valueb"), + ]; + + let mut decoder = connect(); + + assert!(decoder.decoder.set_capacity(200).is_ok()); + + recv_instruction(&mut decoder, ENCODER_INST, &Ok(())); + + decode_headers(&mut decoder, HEADER_BLOCK_1, &headers, STREAM_0); + + let headers = vec![Header::new("my-headera", "my-valuea")]; + + decode_headers(&mut decoder, HEADER_BLOCK_2, &headers, STREAM_0); + } + + #[test] + fn test_base_larger_than_entry_count() { + // Test for issue https://github.com/mozilla/neqo/issues/533 + // Send instruction that inserts 2 fields into the dynamic table and send a header that + // uses base larger than 2. + const ENCODER_INST: &[u8] = &[ + 0x4a, 0x6d, 0x79, 0x2d, 0x68, 0x65, 0x61, 0x64, 0x65, 0x72, 0x61, 0x09, 0x6d, 0x79, + 0x2d, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x61, 0x4a, 0x6d, 0x79, 0x2d, 0x68, 0x65, 0x61, + 0x64, 0x65, 0x72, 0x62, 0x09, 0x6d, 0x79, 0x2d, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x62, + ]; + + const HEADER_BLOCK: &[u8] = &[0x03, 0x03, 0x83, 0x84]; + + let headers = vec![ + Header::new("my-headerb", "my-valueb"), + Header::new("my-headera", "my-valuea"), + ]; + + let mut decoder = connect(); + + assert!(decoder.decoder.set_capacity(200).is_ok()); + + recv_instruction(&mut decoder, ENCODER_INST, &Ok(())); + + decode_headers(&mut decoder, HEADER_BLOCK, &headers, STREAM_0); + } +} diff --git a/third_party/rust/neqo-qpack/src/decoder_instructions.rs b/third_party/rust/neqo-qpack/src/decoder_instructions.rs new file mode 100644 index 0000000000..eb8a331f3a --- /dev/null +++ b/third_party/rust/neqo-qpack/src/decoder_instructions.rs @@ -0,0 +1,244 @@ +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use crate::prefix::{ + DECODER_HEADER_ACK, DECODER_INSERT_COUNT_INCREMENT, DECODER_STREAM_CANCELLATION, +}; +use crate::qpack_send_buf::QpackData; +use crate::reader::{IntReader, ReadByte}; +use crate::Res; +use neqo_common::{qdebug, qtrace}; +use neqo_transport::StreamId; +use std::mem; + +#[derive(Debug, Copy, Clone, PartialEq, Eq)] +pub enum DecoderInstruction { + InsertCountIncrement { increment: u64 }, + HeaderAck { stream_id: StreamId }, + StreamCancellation { stream_id: StreamId }, + NoInstruction, +} + +impl DecoderInstruction { + fn get_instruction(b: u8) -> Self { + if DECODER_HEADER_ACK.cmp_prefix(b) { + Self::HeaderAck { + stream_id: StreamId::from(0), + } + } else if DECODER_STREAM_CANCELLATION.cmp_prefix(b) { + Self::StreamCancellation { + stream_id: StreamId::from(0), + } + } else if DECODER_INSERT_COUNT_INCREMENT.cmp_prefix(b) { + Self::InsertCountIncrement { increment: 0 } + } else { + unreachable!(); + } + } + + pub(crate) fn marshal(&self, enc: &mut QpackData) { + match self { + Self::InsertCountIncrement { increment } => { + enc.encode_prefixed_encoded_int(DECODER_INSERT_COUNT_INCREMENT, *increment); + } + Self::HeaderAck { stream_id } => { + enc.encode_prefixed_encoded_int(DECODER_HEADER_ACK, stream_id.as_u64()); + } + Self::StreamCancellation { stream_id } => { + enc.encode_prefixed_encoded_int(DECODER_STREAM_CANCELLATION, stream_id.as_u64()); + } + Self::NoInstruction => {} + } + } +} + +#[derive(Debug)] +enum DecoderInstructionReaderState { + ReadInstruction, + ReadInt { reader: IntReader }, +} + +#[derive(Debug)] +pub struct DecoderInstructionReader { + state: DecoderInstructionReaderState, + instruction: DecoderInstruction, +} + +impl ::std::fmt::Display for DecoderInstructionReader { + fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result { + write!(f, "InstructionReader") + } +} + +impl DecoderInstructionReader { + pub fn new() -> Self { + Self { + state: DecoderInstructionReaderState::ReadInstruction, + instruction: DecoderInstruction::NoInstruction, + } + } + + /// ### Errors + /// 1) `NeedMoreData` if the reader needs more data + /// 2) `ClosedCriticalStream` + /// 3) other errors will be translated to `DecoderStream` by the caller of this function. + pub fn read_instructions<R: ReadByte>(&mut self, recv: &mut R) -> Res<DecoderInstruction> { + qdebug!([self], "read a new instraction"); + loop { + match &mut self.state { + DecoderInstructionReaderState::ReadInstruction => { + let b = recv.read_byte()?; + self.instruction = DecoderInstruction::get_instruction(b); + self.state = DecoderInstructionReaderState::ReadInt { + reader: IntReader::make( + b, + &[ + DECODER_HEADER_ACK, + DECODER_STREAM_CANCELLATION, + DECODER_INSERT_COUNT_INCREMENT, + ], + ), + }; + } + DecoderInstructionReaderState::ReadInt { reader } => { + let val = reader.read(recv)?; + qtrace!([self], "varint read {}", val); + match &mut self.instruction { + DecoderInstruction::InsertCountIncrement { increment: v } => { + *v = val; + self.state = DecoderInstructionReaderState::ReadInstruction; + break Ok(mem::replace( + &mut self.instruction, + DecoderInstruction::NoInstruction, + )); + } + DecoderInstruction::HeaderAck { stream_id: v } + | DecoderInstruction::StreamCancellation { stream_id: v } => { + *v = StreamId::from(val); + self.state = DecoderInstructionReaderState::ReadInstruction; + break Ok(mem::replace( + &mut self.instruction, + DecoderInstruction::NoInstruction, + )); + } + DecoderInstruction::NoInstruction => { + unreachable!("This instruction cannot be in this state."); + } + } + } + } + } + } +} + +#[cfg(test)] +mod test { + + use super::{DecoderInstruction, DecoderInstructionReader, QpackData}; + use crate::reader::test_receiver::TestReceiver; + use crate::Error; + use neqo_transport::StreamId; + + fn test_encoding_decoding(instruction: DecoderInstruction) { + let mut buf = QpackData::default(); + instruction.marshal(&mut buf); + let mut test_receiver: TestReceiver = TestReceiver::default(); + test_receiver.write(&buf); + let mut decoder = DecoderInstructionReader::new(); + assert_eq!( + decoder.read_instructions(&mut test_receiver).unwrap(), + instruction + ); + } + + #[test] + fn test_encoding_decoding_instructions() { + test_encoding_decoding(DecoderInstruction::InsertCountIncrement { increment: 1 }); + test_encoding_decoding(DecoderInstruction::InsertCountIncrement { increment: 10_000 }); + + test_encoding_decoding(DecoderInstruction::HeaderAck { + stream_id: StreamId::new(1), + }); + test_encoding_decoding(DecoderInstruction::HeaderAck { + stream_id: StreamId::new(10_000), + }); + + test_encoding_decoding(DecoderInstruction::StreamCancellation { + stream_id: StreamId::new(1), + }); + test_encoding_decoding(DecoderInstruction::StreamCancellation { + stream_id: StreamId::new(10_000), + }); + } + + fn test_encoding_decoding_slow_reader(instruction: DecoderInstruction) { + let mut buf = QpackData::default(); + instruction.marshal(&mut buf); + let mut test_receiver: TestReceiver = TestReceiver::default(); + let mut decoder = DecoderInstructionReader::new(); + for i in 0..buf.len() - 1 { + test_receiver.write(&buf[i..=i]); + assert_eq!( + decoder.read_instructions(&mut test_receiver), + Err(Error::NeedMoreData) + ); + } + test_receiver.write(&buf[buf.len() - 1..buf.len()]); + assert_eq!( + decoder.read_instructions(&mut test_receiver).unwrap(), + instruction + ); + } + + #[test] + fn test_encoding_decoding_instructions_slow_reader() { + test_encoding_decoding_slow_reader(DecoderInstruction::InsertCountIncrement { + increment: 10_000, + }); + test_encoding_decoding_slow_reader(DecoderInstruction::HeaderAck { + stream_id: StreamId::new(10_000), + }); + test_encoding_decoding_slow_reader(DecoderInstruction::StreamCancellation { + stream_id: StreamId::new(10_000), + }); + } + + #[test] + fn test_decoding_error() { + let mut test_receiver: TestReceiver = TestReceiver::default(); + // InsertCountIncrement with overflow + test_receiver.write(&[ + 0x3f, 0xc1, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xff, 0x02, + ]); + let mut decoder = DecoderInstructionReader::new(); + assert_eq!( + decoder.read_instructions(&mut test_receiver), + Err(Error::IntegerOverflow) + ); + + let mut test_receiver: TestReceiver = TestReceiver::default(); + // StreamCancellation with overflow + test_receiver.write(&[ + 0x7f, 0xc1, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xff, 0x02, + ]); + let mut decoder = DecoderInstructionReader::new(); + assert_eq!( + decoder.read_instructions(&mut test_receiver), + Err(Error::IntegerOverflow) + ); + + let mut test_receiver: TestReceiver = TestReceiver::default(); + // HeaderAck with overflow + test_receiver.write(&[ + 0x7f, 0xc1, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xff, 0x02, + ]); + let mut decoder = DecoderInstructionReader::new(); + assert_eq!( + decoder.read_instructions(&mut test_receiver), + Err(Error::IntegerOverflow) + ); + } +} diff --git a/third_party/rust/neqo-qpack/src/encoder.rs b/third_party/rust/neqo-qpack/src/encoder.rs new file mode 100644 index 0000000000..a5ebd01666 --- /dev/null +++ b/third_party/rust/neqo-qpack/src/encoder.rs @@ -0,0 +1,1645 @@ +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use crate::decoder_instructions::{DecoderInstruction, DecoderInstructionReader}; +use crate::encoder_instructions::EncoderInstruction; +use crate::header_block::HeaderEncoder; +use crate::qlog; +use crate::qpack_send_buf::QpackData; +use crate::reader::ReceiverConnWrapper; +use crate::stats::Stats; +use crate::table::{HeaderTable, LookupResult, ADDITIONAL_TABLE_ENTRY_SIZE}; +use crate::{Error, QpackSettings, Res}; +use neqo_common::{qdebug, qerror, qlog::NeqoQlog, qtrace, Header}; +use neqo_transport::{Connection, Error as TransportError, StreamId}; +use std::collections::{HashMap, HashSet, VecDeque}; +use std::convert::TryFrom; + +pub const QPACK_UNI_STREAM_TYPE_ENCODER: u64 = 0x2; + +#[derive(Debug, PartialEq)] +enum LocalStreamState { + NoStream, + Uninitialized(StreamId), + Initialized(StreamId), +} + +impl LocalStreamState { + pub fn stream_id(&self) -> Option<StreamId> { + match self { + Self::NoStream => None, + Self::Uninitialized(stream_id) | Self::Initialized(stream_id) => Some(*stream_id), + } + } +} + +#[derive(Debug)] +pub struct QPackEncoder { + table: HeaderTable, + max_table_size: u64, + max_entries: u64, + instruction_reader: DecoderInstructionReader, + local_stream: LocalStreamState, + max_blocked_streams: u16, + // Remember header blocks that are referring to dynamic table. + // There can be multiple header blocks in one stream, headers, trailer, push stream request, etc. + // This HashMap maps a stream ID to a list of header blocks. Each header block is a list of + // referenced dynamic table entries. + unacked_header_blocks: HashMap<StreamId, VecDeque<HashSet<u64>>>, + blocked_stream_cnt: u16, + use_huffman: bool, + next_capacity: Option<u64>, + stats: Stats, +} + +impl QPackEncoder { + #[must_use] + pub fn new(qpack_settings: &QpackSettings, use_huffman: bool) -> Self { + Self { + table: HeaderTable::new(true), + max_table_size: qpack_settings.max_table_size_encoder, + max_entries: 0, + instruction_reader: DecoderInstructionReader::new(), + local_stream: LocalStreamState::NoStream, + max_blocked_streams: 0, + unacked_header_blocks: HashMap::new(), + blocked_stream_cnt: 0, + use_huffman, + next_capacity: None, + stats: Stats::default(), + } + } + + /// This function is use for setting encoders table max capacity. The value is received as + /// a `SETTINGS_QPACK_MAX_TABLE_CAPACITY` setting parameter. + /// # Errors + /// `EncoderStream` if value is too big. + /// `ChangeCapacity` if table capacity cannot be reduced. + pub fn set_max_capacity(&mut self, cap: u64) -> Res<()> { + if cap > (1 << 30) - 1 { + return Err(Error::EncoderStream); + } + + if cap == self.table.capacity() { + return Ok(()); + } + + qdebug!( + [self], + "Set max capacity to new capacity:{} old:{} max_table_size={}.", + cap, + self.table.capacity(), + self.max_table_size, + ); + + let new_cap = std::cmp::min(self.max_table_size, cap); + // we also set our table to the max allowed. + self.change_capacity(new_cap); + Ok(()) + } + + /// This function is use for setting encoders max blocked streams. The value is received as + /// a `SETTINGS_QPACK_BLOCKED_STREAMS` setting parameter. + /// # Errors + /// `EncoderStream` if value is too big. + pub fn set_max_blocked_streams(&mut self, blocked_streams: u64) -> Res<()> { + self.max_blocked_streams = u16::try_from(blocked_streams).or(Err(Error::EncoderStream))?; + Ok(()) + } + + /// Reads decoder instructions. + /// # Errors + /// May return: `ClosedCriticalStream` if stream has been closed or `DecoderStream` + /// in case of any other transport error. + pub fn receive(&mut self, conn: &mut Connection, stream_id: StreamId) -> Res<()> { + self.read_instructions(conn, stream_id) + .map_err(|e| map_error(&e)) + } + + fn read_instructions(&mut self, conn: &mut Connection, stream_id: StreamId) -> Res<()> { + qdebug!([self], "read a new instraction"); + loop { + let mut recv = ReceiverConnWrapper::new(conn, stream_id); + match self.instruction_reader.read_instructions(&mut recv) { + Ok(instruction) => self.call_instruction(instruction, conn.qlog_mut())?, + Err(Error::NeedMoreData) => break Ok(()), + Err(e) => break Err(e), + } + } + } + + fn recalculate_blocked_streams(&mut self) { + let acked_inserts_cnt = self.table.get_acked_inserts_cnt(); + self.blocked_stream_cnt = 0; + for hb_list in self.unacked_header_blocks.values_mut() { + debug_assert!(!hb_list.is_empty()); + if hb_list.iter().flatten().any(|e| *e >= acked_inserts_cnt) { + self.blocked_stream_cnt += 1; + } + } + } + + #[allow(clippy::map_err_ignore)] + fn insert_count_instruction(&mut self, increment: u64) -> Res<()> { + self.table + .increment_acked(increment) + .map_err(|_| Error::DecoderStream)?; + self.recalculate_blocked_streams(); + Ok(()) + } + + fn header_ack(&mut self, stream_id: StreamId) { + self.stats.header_acks_recv += 1; + let mut new_acked = self.table.get_acked_inserts_cnt(); + if let Some(hb_list) = self.unacked_header_blocks.get_mut(&stream_id) { + if let Some(ref_list) = hb_list.pop_back() { + for iter in ref_list { + self.table.remove_ref(iter); + if iter >= new_acked { + new_acked = iter + 1; + } + } + } else { + debug_assert!(false, "We should have at least one header block."); + } + if hb_list.is_empty() { + self.unacked_header_blocks.remove(&stream_id); + } + } + if new_acked > self.table.get_acked_inserts_cnt() { + self.insert_count_instruction(new_acked - self.table.get_acked_inserts_cnt()) + .expect("This should neve happen"); + } + } + + fn stream_cancellation(&mut self, stream_id: StreamId) { + self.stats.stream_cancelled_recv += 1; + let mut was_blocker = false; + if let Some(mut hb_list) = self.unacked_header_blocks.remove(&stream_id) { + debug_assert!(!hb_list.is_empty()); + while let Some(ref_list) = hb_list.pop_front() { + for iter in ref_list { + self.table.remove_ref(iter); + was_blocker = was_blocker || (iter >= self.table.get_acked_inserts_cnt()); + } + } + } + if was_blocker { + debug_assert!(self.blocked_stream_cnt > 0); + self.blocked_stream_cnt -= 1; + } + } + + fn call_instruction( + &mut self, + instruction: DecoderInstruction, + qlog: &mut NeqoQlog, + ) -> Res<()> { + qdebug!([self], "call intruction {:?}", instruction); + match instruction { + DecoderInstruction::InsertCountIncrement { increment } => { + qlog::qpack_read_insert_count_increment_instruction( + qlog, + increment, + &increment.to_be_bytes(), + ); + + self.insert_count_instruction(increment) + } + DecoderInstruction::HeaderAck { stream_id } => { + self.header_ack(stream_id); + Ok(()) + } + DecoderInstruction::StreamCancellation { stream_id } => { + self.stream_cancellation(stream_id); + Ok(()) + } + DecoderInstruction::NoInstruction => Ok(()), + } + } + + /// Inserts a new entry into a table and sends the corresponding instruction to a peer. An entry is added only + /// if it is possible to send the corresponding instruction immediately, i.e. the encoder stream is not + /// blocked by the flow control (or stream internal buffer(this is very unlikely)). + /// ### Errors + /// `EncoderStreamBlocked` if the encoder stream is blocked by the flow control. + /// `DynamicTableFull` if the dynamic table does not have enough space for the entry. + /// The function can return transport errors: `InvalidStreamId`, `InvalidInput` and `FinalSizeError`. + /// # Panics + /// When the insertion fails (it should not). + pub fn send_and_insert( + &mut self, + conn: &mut Connection, + name: &[u8], + value: &[u8], + ) -> Res<u64> { + qdebug!([self], "insert {:?} {:?}.", name, value); + + let entry_size = name.len() + value.len() + ADDITIONAL_TABLE_ENTRY_SIZE; + + if !self.table.insert_possible(entry_size) { + return Err(Error::DynamicTableFull); + } + + let mut buf = QpackData::default(); + EncoderInstruction::InsertWithNameLiteral { name, value } + .marshal(&mut buf, self.use_huffman); + + let stream_id = self.local_stream.stream_id().ok_or(Error::Internal)?; + + let sent = conn + .stream_send_atomic(stream_id, &buf) + .map_err(|e| map_stream_send_atomic_error(&e))?; + if !sent { + return Err(Error::EncoderStreamBlocked); + } + + self.stats.dynamic_table_inserts += 1; + + match self.table.insert(name, value) { + Ok(inx) => Ok(inx), + Err(e) => { + debug_assert!(false); + Err(e) + } + } + } + + fn change_capacity(&mut self, value: u64) { + qdebug!([self], "change capacity: {}", value); + self.next_capacity = Some(value); + } + + fn maybe_send_change_capacity( + &mut self, + conn: &mut Connection, + stream_id: StreamId, + ) -> Res<()> { + if let Some(cap) = self.next_capacity { + // Check if it is possible to reduce the capacity, e.g. if enough space can be make free for the reduction. + if cap < self.table.capacity() && !self.table.can_evict_to(cap) { + return Err(Error::DynamicTableFull); + } + let mut buf = QpackData::default(); + EncoderInstruction::Capacity { value: cap }.marshal(&mut buf, self.use_huffman); + if !conn.stream_send_atomic(stream_id, &buf)? { + return Err(Error::EncoderStreamBlocked); + } + if self.table.set_capacity(cap).is_err() { + debug_assert!( + false, + "can_evict_to should have checked and make sure this operation is possible" + ); + return Err(Error::InternalError(1)); + } + self.max_entries = cap / 32; + self.next_capacity = None; + } + Ok(()) + } + + /// Sends any qpack encoder instructions. + /// # Errors + /// returns `EncoderStream` in case of an error. + pub fn send_encoder_updates(&mut self, conn: &mut Connection) -> Res<()> { + match self.local_stream { + LocalStreamState::NoStream => { + qerror!("Send call but there is no stream yet."); + Ok(()) + } + LocalStreamState::Uninitialized(stream_id) => { + let mut buf = QpackData::default(); + buf.encode_varint(QPACK_UNI_STREAM_TYPE_ENCODER); + if !conn.stream_send_atomic(stream_id, &buf[..])? { + return Err(Error::EncoderStreamBlocked); + } + self.local_stream = LocalStreamState::Initialized(stream_id); + self.maybe_send_change_capacity(conn, stream_id) + } + LocalStreamState::Initialized(stream_id) => { + self.maybe_send_change_capacity(conn, stream_id) + } + } + } + + fn is_stream_blocker(&self, stream_id: StreamId) -> bool { + if let Some(hb_list) = self.unacked_header_blocks.get(&stream_id) { + debug_assert!(!hb_list.is_empty()); + match hb_list.iter().flatten().max() { + Some(max_ref) => *max_ref >= self.table.get_acked_inserts_cnt(), + None => false, + } + } else { + false + } + } + + /// Encodes headers + /// # Errors + /// `ClosedCriticalStream` if the encoder stream is closed. + /// `InternalError` if an unexpected error occurred. + /// # Panics + /// If there is a programming error. + pub fn encode_header_block( + &mut self, + conn: &mut Connection, + h: &[Header], + stream_id: StreamId, + ) -> HeaderEncoder { + qdebug!([self], "encoding headers."); + + let mut encoder_blocked = false; + // Try to send capacity instructions if present. + if self.send_encoder_updates(conn).is_err() { + // This code doesn't try to deal with errors, it just tries + // to write to the encoder stream AND if it can't uses + // literal instructions. + // The errors can be: + // 1) `EncoderStreamBlocked` - this is an error that + // can occur. + // 2) `InternalError` - this is unexpected error. + // 3) `ClosedCriticalStream` - this is error that should + // close the HTTP/3 session. + // The last 2 errors are ignored here and will be picked up + // by the main loop. + encoder_blocked = true; + } + + let mut encoded_h = + HeaderEncoder::new(self.table.base(), self.use_huffman, self.max_entries); + + let stream_is_blocker = self.is_stream_blocker(stream_id); + let can_block = self.blocked_stream_cnt < self.max_blocked_streams || stream_is_blocker; + + let mut ref_entries = HashSet::new(); + + for iter in h.iter() { + let name = iter.name().as_bytes().to_vec(); + let value = iter.value().as_bytes().to_vec(); + qtrace!("encoding {:x?} {:x?}.", name, value); + + if let Some(LookupResult { + index, + static_table, + value_matches, + }) = self.table.lookup(&name, &value, can_block) + { + qtrace!( + [self], + "found a {} entry, value-match={}", + if static_table { "static" } else { "dynamic" }, + value_matches + ); + if value_matches { + if static_table { + encoded_h.encode_indexed_static(index); + } else { + encoded_h.encode_indexed_dynamic(index); + } + } else { + encoded_h.encode_literal_with_name_ref(static_table, index, &value); + } + if !static_table && ref_entries.insert(index) { + self.table.add_ref(index); + } + } else if can_block && !encoder_blocked { + // Insert using an InsertWithNameLiteral instruction. This entry name does not match any name in the + // tables therefore we cannot use any other instruction. + if let Ok(index) = self.send_and_insert(conn, &name, &value) { + encoded_h.encode_indexed_dynamic(index); + ref_entries.insert(index); + self.table.add_ref(index); + } else { + // This code doesn't try to deal with errors, it just tries + // to write to the encoder stream AND if it can't uses + // literal instructions. + // The errors can be: + // 1) `EncoderStreamBlocked` - this is an error that + // can occur. + // 2) `DynamicTableFull` - this is an error that + // can occur. + // 3) `InternalError` - this is unexpected error. + // 4) `ClosedCriticalStream` - this is error that should + // close the HTTP/3 session. + // The last 2 errors are ignored here and will be picked up + // by the main loop. + // As soon as one of the instructions cannot be written or the table is full, do not try again. + encoder_blocked = true; + encoded_h.encode_literal_with_name_literal(&name, &value); + } + } else { + encoded_h.encode_literal_with_name_literal(&name, &value); + } + } + + encoded_h.encode_header_block_prefix(); + + if !stream_is_blocker { + // The streams was not a blocker, check if the stream is a blocker now. + if let Some(max_ref) = ref_entries.iter().max() { + if *max_ref >= self.table.get_acked_inserts_cnt() { + debug_assert!(self.blocked_stream_cnt <= self.max_blocked_streams); + self.blocked_stream_cnt += 1; + } + } + } + + if !ref_entries.is_empty() { + self.unacked_header_blocks + .entry(stream_id) + .or_insert_with(VecDeque::new) + .push_front(ref_entries); + self.stats.dynamic_table_references += 1; + } + encoded_h + } + + /// Encoder stream has been created. Add the stream id. + /// # Panics + /// If a stream has already been added. + pub fn add_send_stream(&mut self, stream_id: StreamId) { + if self.local_stream == LocalStreamState::NoStream { + self.local_stream = LocalStreamState::Uninitialized(stream_id); + } else { + panic!("Adding multiple local streams"); + } + } + + #[must_use] + pub fn stats(&self) -> Stats { + self.stats.clone() + } + + #[must_use] + pub fn local_stream_id(&self) -> Option<StreamId> { + self.local_stream.stream_id() + } + + #[cfg(test)] + fn blocked_stream_cnt(&self) -> u16 { + self.blocked_stream_cnt + } +} + +impl ::std::fmt::Display for QPackEncoder { + fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result { + write!(f, "QPackEncoder") + } +} + +fn map_error(err: &Error) -> Error { + if *err == Error::ClosedCriticalStream { + Error::ClosedCriticalStream + } else { + Error::DecoderStream + } +} + +fn map_stream_send_atomic_error(err: &TransportError) -> Error { + match err { + TransportError::InvalidStreamId | TransportError::FinalSizeError => { + Error::ClosedCriticalStream + } + _ => { + debug_assert!(false, "Unexpected error"); + Error::InternalError(2) + } + } +} + +#[cfg(test)] +mod tests { + use super::{Connection, Error, Header, QPackEncoder, Res}; + use crate::QpackSettings; + use neqo_transport::{ConnectionParameters, StreamId, StreamType}; + use std::mem; + use test_fixture::{default_client, default_server, handshake, new_server, now, DEFAULT_ALPN}; + + struct TestEncoder { + encoder: QPackEncoder, + send_stream_id: StreamId, + recv_stream_id: StreamId, + conn: Connection, + peer_conn: Connection, + } + + impl TestEncoder { + pub fn change_capacity(&mut self, capacity: u64) -> Res<()> { + self.encoder.set_max_capacity(capacity).unwrap(); + // We will try to really change the table only when we send the change capacity instruction. + self.encoder.send_encoder_updates(&mut self.conn) + } + + pub fn insert(&mut self, header: &[u8], value: &[u8], inst: &[u8]) { + let res = self.encoder.send_and_insert(&mut self.conn, header, value); + assert!(res.is_ok()); + self.send_instructions(inst); + } + + pub fn encode_header_block( + &mut self, + stream_id: StreamId, + headers: &[Header], + expected_encoding: &[u8], + inst: &[u8], + ) { + let buf = self + .encoder + .encode_header_block(&mut self.conn, headers, stream_id); + assert_eq!(&buf[..], expected_encoding); + self.send_instructions(inst); + } + + pub fn send_instructions(&mut self, encoder_instruction: &[u8]) { + self.encoder.send_encoder_updates(&mut self.conn).unwrap(); + let out = self.conn.process(None, now()); + let out2 = self.peer_conn.process(out.dgram(), now()); + mem::drop(self.conn.process(out2.dgram(), now())); + let mut buf = [0_u8; 100]; + let (amount, fin) = self + .peer_conn + .stream_recv(self.send_stream_id, &mut buf) + .unwrap(); + assert!(!fin); + assert_eq!(buf[..amount], encoder_instruction[..]); + } + } + + fn connect_generic(huffman: bool, max_data: Option<u64>) -> TestEncoder { + let mut conn = default_client(); + let mut peer_conn = max_data.map_or_else(default_server, |max| { + new_server( + DEFAULT_ALPN, + ConnectionParameters::default() + .max_stream_data(StreamType::UniDi, true, max) + .max_stream_data(StreamType::BiDi, true, max) + .max_stream_data(StreamType::BiDi, false, max), + ) + }); + handshake(&mut conn, &mut peer_conn); + + // create a stream + let recv_stream_id = peer_conn.stream_create(StreamType::UniDi).unwrap(); + let send_stream_id = conn.stream_create(StreamType::UniDi).unwrap(); + + // create an encoder + let mut encoder = QPackEncoder::new( + &QpackSettings { + max_table_size_encoder: 1500, + max_table_size_decoder: 0, + max_blocked_streams: 0, + }, + huffman, + ); + encoder.add_send_stream(send_stream_id); + + TestEncoder { + encoder, + send_stream_id, + recv_stream_id, + conn, + peer_conn, + } + } + + fn connect(huffman: bool) -> TestEncoder { + connect_generic(huffman, None) + } + + fn connect_flow_control(max_data: u64) -> TestEncoder { + connect_generic(true, Some(max_data)) + } + + fn recv_instruction(encoder: &mut TestEncoder, decoder_instruction: &[u8]) { + encoder + .peer_conn + .stream_send(encoder.recv_stream_id, decoder_instruction) + .unwrap(); + let out = encoder.peer_conn.process(None, now()); + mem::drop(encoder.conn.process(out.dgram(), now())); + assert!(encoder + .encoder + .read_instructions(&mut encoder.conn, encoder.recv_stream_id) + .is_ok()); + } + + const CAP_INSTRUCTION_200: &[u8] = &[0x02, 0x3f, 0xa9, 0x01]; + const CAP_INSTRUCTION_60: &[u8] = &[0x02, 0x3f, 0x1d]; + const CAP_INSTRUCTION_1000: &[u8] = &[0x02, 0x3f, 0xc9, 0x07]; + const CAP_INSTRUCTION_1500: &[u8] = &[0x02, 0x3f, 0xbd, 0x0b]; + + const HEADER_CONTENT_LENGTH: &[u8] = &[ + 0x63, 0x6f, 0x6e, 0x74, 0x65, 0x6e, 0x74, 0x2d, 0x6c, 0x65, 0x6e, 0x67, 0x74, 0x68, + ]; + const VALUE_1: &[u8] = &[0x31, 0x32, 0x33, 0x34]; + const VALUE_2: &[u8] = &[0x31, 0x32, 0x33, 0x34, 0x35]; + + // HEADER_CONTENT_LENGTH and VALUE_1 encoded by instruction insert_with_name_literal. + const HEADER_CONTENT_LENGTH_VALUE_1_NAME_LITERAL: &[u8] = &[ + 0x4e, 0x63, 0x6f, 0x6e, 0x74, 0x65, 0x6e, 0x74, 0x2d, 0x6c, 0x65, 0x6e, 0x67, 0x74, 0x68, + 0x04, 0x31, 0x32, 0x33, 0x34, + ]; + + // HEADER_CONTENT_LENGTH and VALUE_2 encoded by instruction insert_with_name_literal. + const HEADER_CONTENT_LENGTH_VALUE_2_NAME_LITERAL: &[u8] = &[ + 0x4e, 0x63, 0x6f, 0x6e, 0x74, 0x65, 0x6e, 0x74, 0x2d, 0x6c, 0x65, 0x6e, 0x67, 0x74, 0x68, + 0x05, 0x31, 0x32, 0x33, 0x34, 0x35, + ]; + + // Indexed Header Field that refers to the first entry in the dynamic table. + const ENCODE_INDEXED_REF_DYNAMIC: &[u8] = &[0x02, 0x00, 0x80]; + + const STREAM_1: StreamId = StreamId::new(1); + const STREAM_2: StreamId = StreamId::new(2); + const HEADER_ACK_STREAM_ID_1: &[u8] = &[0x81]; + const HEADER_ACK_STREAM_ID_2: &[u8] = &[0x82]; + const STREAM_CANCELED_ID_1: &[u8] = &[0x41]; + + // test insert_with_name_literal which fails because there is not enough space in the table + #[test] + fn test_insert_with_name_literal_1() { + let mut encoder = connect(false); + + // insert "content-length: 1234 + let res = + encoder + .encoder + .send_and_insert(&mut encoder.conn, HEADER_CONTENT_LENGTH, VALUE_1); + assert_eq!(Error::DynamicTableFull, res.unwrap_err()); + encoder.send_instructions(&[0x02]); + } + + // test insert_with_name_literal - succeeds + #[test] + fn test_insert_with_name_literal_2() { + let mut encoder = connect(false); + + assert!(encoder.encoder.set_max_capacity(200).is_ok()); + // test the change capacity instruction. + encoder.send_instructions(CAP_INSTRUCTION_200); + + // insert "content-length: 1234 + let res = + encoder + .encoder + .send_and_insert(&mut encoder.conn, HEADER_CONTENT_LENGTH, VALUE_1); + assert!(res.is_ok()); + encoder.send_instructions(HEADER_CONTENT_LENGTH_VALUE_1_NAME_LITERAL); + } + + #[test] + fn test_change_capacity() { + let mut encoder = connect(false); + + assert!(encoder.encoder.set_max_capacity(200).is_ok()); + encoder.send_instructions(CAP_INSTRUCTION_200); + } + + struct TestElement { + pub headers: Vec<Header>, + pub header_block: &'static [u8], + pub encoder_inst: &'static [u8], + } + + #[test] + fn test_header_block_encoder_non() { + let test_cases: [TestElement; 6] = [ + // test a header with ref to static - encode_indexed + TestElement { + headers: vec![Header::new(":method", "GET")], + header_block: &[0x00, 0x00, 0xd1], + encoder_inst: &[], + }, + // test encode_literal_with_name_ref + TestElement { + headers: vec![Header::new(":path", "/somewhere")], + header_block: &[ + 0x00, 0x00, 0x51, 0x0a, 0x2f, 0x73, 0x6f, 0x6d, 0x65, 0x77, 0x68, 0x65, 0x72, + 0x65, + ], + encoder_inst: &[], + }, + // test adding a new header and encode_post_base_index, also test fix_header_block_prefix + TestElement { + headers: vec![Header::new("my-header", "my-value")], + header_block: &[0x02, 0x80, 0x10], + encoder_inst: &[ + 0x49, 0x6d, 0x79, 0x2d, 0x68, 0x65, 0x61, 0x64, 0x65, 0x72, 0x08, 0x6d, 0x79, + 0x2d, 0x76, 0x61, 0x6c, 0x75, 0x65, + ], + }, + // test encode_indexed with a ref to dynamic table. + TestElement { + headers: vec![Header::new("my-header", "my-value")], + header_block: ENCODE_INDEXED_REF_DYNAMIC, + encoder_inst: &[], + }, + // test encode_literal_with_name_ref. + TestElement { + headers: vec![Header::new("my-header", "my-value2")], + header_block: &[ + 0x02, 0x00, 0x40, 0x09, 0x6d, 0x79, 0x2d, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x32, + ], + encoder_inst: &[], + }, + // test multiple headers + TestElement { + headers: vec![ + Header::new(":method", "GET"), + Header::new(":path", "/somewhere"), + Header::new(":authority", "example.com"), + Header::new(":scheme", "https"), + ], + header_block: &[ + 0x00, 0x01, 0xd1, 0x51, 0x0a, 0x2f, 0x73, 0x6f, 0x6d, 0x65, 0x77, 0x68, 0x65, + 0x72, 0x65, 0x50, 0x0b, 0x65, 0x78, 0x61, 0x6d, 0x70, 0x6c, 0x65, 0x2e, 0x63, + 0x6f, 0x6d, 0xd7, + ], + encoder_inst: &[], + }, + ]; + + let mut encoder = connect(false); + + encoder.encoder.set_max_blocked_streams(100).unwrap(); + encoder.encoder.set_max_capacity(200).unwrap(); + + // test the change capacity instruction. + encoder.send_instructions(CAP_INSTRUCTION_200); + + for t in &test_cases { + let buf = encoder + .encoder + .encode_header_block(&mut encoder.conn, &t.headers, STREAM_1); + assert_eq!(&buf[..], t.header_block); + encoder.send_instructions(t.encoder_inst); + } + } + + #[test] + fn test_header_block_encoder_huffman() { + let test_cases: [TestElement; 6] = [ + // test a header with ref to static - encode_indexed + TestElement { + headers: vec![Header::new(":method", "GET")], + header_block: &[0x00, 0x00, 0xd1], + encoder_inst: &[], + }, + // test encode_literal_with_name_ref + TestElement { + headers: vec![Header::new(":path", "/somewhere")], + header_block: &[ + 0x00, 0x00, 0x51, 0x87, 0x61, 0x07, 0xa4, 0xbe, 0x27, 0x2d, 0x85, + ], + encoder_inst: &[], + }, + // test adding a new header and encode_post_base_index, also test fix_header_block_prefix + TestElement { + headers: vec![Header::new("my-header", "my-value")], + header_block: &[0x02, 0x80, 0x10], + encoder_inst: &[ + 0x67, 0xa7, 0xd2, 0xd3, 0x94, 0x72, 0x16, 0xcf, 0x86, 0xa7, 0xd2, 0xdd, 0xc7, + 0x45, 0xa5, + ], + }, + // test encode_indexed with a ref to dynamic table. + TestElement { + headers: vec![Header::new("my-header", "my-value")], + header_block: ENCODE_INDEXED_REF_DYNAMIC, + encoder_inst: &[], + }, + // test encode_literal_with_name_ref. + TestElement { + headers: vec![Header::new("my-header", "my-value2")], + header_block: &[ + 0x02, 0x00, 0x40, 0x87, 0xa7, 0xd2, 0xdd, 0xc7, 0x45, 0xa5, 0x17, + ], + encoder_inst: &[], + }, + // test multiple headers + TestElement { + headers: vec![ + Header::new(":method", "GET"), + Header::new(":path", "/somewhere"), + Header::new(":authority", "example.com"), + Header::new(":scheme", "https"), + ], + header_block: &[ + 0x00, 0x01, 0xd1, 0x51, 0x87, 0x61, 0x07, 0xa4, 0xbe, 0x27, 0x2d, 0x85, 0x50, + 0x88, 0x2f, 0x91, 0xd3, 0x5d, 0x05, 0x5c, 0x87, 0xa7, 0xd7, + ], + encoder_inst: &[], + }, + ]; + + let mut encoder = connect(true); + + encoder.encoder.set_max_blocked_streams(100).unwrap(); + encoder.encoder.set_max_capacity(200).unwrap(); + + // test the change capacity instruction. + encoder.send_instructions(CAP_INSTRUCTION_200); + + for t in &test_cases { + let buf = encoder + .encoder + .encode_header_block(&mut encoder.conn, &t.headers, STREAM_1); + assert_eq!(&buf[..], t.header_block); + encoder.send_instructions(t.encoder_inst); + } + } + + // Test inserts block on waiting for an insert count increment. + #[test] + fn test_insertion_blocked_on_insert_count_feedback() { + let mut encoder = connect(false); + + encoder.encoder.set_max_capacity(60).unwrap(); + + // test the change capacity instruction. + encoder.send_instructions(CAP_INSTRUCTION_60); + + // insert "content-length: 1234 + let res = + encoder + .encoder + .send_and_insert(&mut encoder.conn, HEADER_CONTENT_LENGTH, VALUE_1); + assert!(res.is_ok()); + encoder.send_instructions(HEADER_CONTENT_LENGTH_VALUE_1_NAME_LITERAL); + + // insert "content-length: 12345 which will fail because the ntry in the table cannot be evicted. + let res = + encoder + .encoder + .send_and_insert(&mut encoder.conn, HEADER_CONTENT_LENGTH, VALUE_2); + assert!(res.is_err()); + encoder.send_instructions(&[]); + + // receive an insert count increment. + recv_instruction(&mut encoder, &[0x01]); + + // insert "content-length: 12345 again it will succeed. + let res = + encoder + .encoder + .send_and_insert(&mut encoder.conn, HEADER_CONTENT_LENGTH, VALUE_2); + assert!(res.is_ok()); + encoder.send_instructions(HEADER_CONTENT_LENGTH_VALUE_2_NAME_LITERAL); + } + + // Test inserts block on waiting for acks + // test the table insertion is blocked: + // 0 - waiting for a header ack + // 2 - waiting for a stream cancel. + fn test_insertion_blocked_on_waiting_for_header_ack_or_stream_cancel(wait: u8) { + let mut encoder = connect(false); + + assert!(encoder.encoder.set_max_capacity(60).is_ok()); + // test the change capacity instruction. + encoder.send_instructions(CAP_INSTRUCTION_60); + + // insert "content-length: 1234 + let res = + encoder + .encoder + .send_and_insert(&mut encoder.conn, HEADER_CONTENT_LENGTH, VALUE_1); + assert!(res.is_ok()); + encoder.send_instructions(HEADER_CONTENT_LENGTH_VALUE_1_NAME_LITERAL); + + // receive an insert count increment. + recv_instruction(&mut encoder, &[0x01]); + + // send a header block + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("content-length", "1234")], + STREAM_1, + ); + assert_eq!(&buf[..], ENCODE_INDEXED_REF_DYNAMIC); + encoder.send_instructions(&[]); + + // insert "content-length: 12345 which will fail because the entry in the table cannot be evicted + let res = + encoder + .encoder + .send_and_insert(&mut encoder.conn, HEADER_CONTENT_LENGTH, VALUE_2); + assert!(res.is_err()); + encoder.send_instructions(&[]); + + if wait == 0 { + // receive a header_ack. + recv_instruction(&mut encoder, HEADER_ACK_STREAM_ID_1); + } else { + // receive a stream canceled + recv_instruction(&mut encoder, STREAM_CANCELED_ID_1); + } + + // insert "content-length: 12345 again it will succeed. + let res = + encoder + .encoder + .send_and_insert(&mut encoder.conn, HEADER_CONTENT_LENGTH, VALUE_2); + assert!(res.is_ok()); + encoder.send_instructions(HEADER_CONTENT_LENGTH_VALUE_2_NAME_LITERAL); + } + + #[test] + fn test_header_ack() { + test_insertion_blocked_on_waiting_for_header_ack_or_stream_cancel(0); + } + + #[test] + fn test_stream_canceled() { + test_insertion_blocked_on_waiting_for_header_ack_or_stream_cancel(1); + } + + fn assert_is_index_to_dynamic(buf: &[u8]) { + assert_eq!(buf[2] & 0xc0, 0x80); + } + + fn assert_is_index_to_dynamic_post(buf: &[u8]) { + assert_eq!(buf[2] & 0xf0, 0x10); + } + + fn assert_is_index_to_static_name_only(buf: &[u8]) { + assert_eq!(buf[2] & 0xf0, 0x50); + } + + fn assert_is_literal_value_literal_name(buf: &[u8]) { + assert_eq!(buf[2] & 0xf0, 0x20); + } + + #[test] + fn max_block_streams1() { + let mut encoder = connect(false); + + assert!(encoder.encoder.set_max_capacity(60).is_ok()); + + // change capacity to 60. + encoder.send_instructions(CAP_INSTRUCTION_60); + + // insert "content-length: 1234 + let res = + encoder + .encoder + .send_and_insert(&mut encoder.conn, HEADER_CONTENT_LENGTH, VALUE_1); + + assert!(res.is_ok()); + encoder.send_instructions(HEADER_CONTENT_LENGTH_VALUE_1_NAME_LITERAL); + + encoder.encoder.set_max_blocked_streams(1).unwrap(); + + // send a header block, it refers to unacked entry. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("content-length", "1234")], + STREAM_1, + ); + assert_is_index_to_dynamic(&buf); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 1); + + encoder.send_instructions(&[]); + + // The next one will not use the dynamic entry because it is exceeding the max_blocked_streams + // limit. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("content-length", "1234")], + StreamId::new(2), + ); + assert_is_index_to_static_name_only(&buf); + + encoder.send_instructions(&[]); + assert_eq!(encoder.encoder.blocked_stream_cnt(), 1); + + // another header block to already blocked stream can still use the entry. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("content-length", "1234")], + STREAM_1, + ); + assert_is_index_to_dynamic(&buf); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 1); + } + + #[test] + fn max_block_streams2() { + let mut encoder = connect(false); + + assert!(encoder.encoder.set_max_capacity(200).is_ok()); + + // change capacity to 200. + encoder.send_instructions(CAP_INSTRUCTION_200); + + // insert "content-length: 1234 + let res = + encoder + .encoder + .send_and_insert(&mut encoder.conn, HEADER_CONTENT_LENGTH, VALUE_1); + + assert!(res.is_ok()); + encoder.send_instructions(HEADER_CONTENT_LENGTH_VALUE_1_NAME_LITERAL); + + // insert "content-length: 12345 + let res = + encoder + .encoder + .send_and_insert(&mut encoder.conn, HEADER_CONTENT_LENGTH, VALUE_2); + + assert!(res.is_ok()); + encoder.send_instructions(HEADER_CONTENT_LENGTH_VALUE_2_NAME_LITERAL); + + encoder.encoder.set_max_blocked_streams(1).unwrap(); + + // send a header block, it refers to unacked entry. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("content-length", "1234")], + STREAM_1, + ); + assert_is_index_to_dynamic(&buf); + + // encode another header block for the same stream that will refer to the second entry + // in the dynamic table. + // This should work because the stream is already a blocked stream + // send a header block, it refers to unacked entry. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("content-length", "12345")], + STREAM_1, + ); + assert_is_index_to_dynamic(&buf); + } + + #[test] + fn max_block_streams3() { + let mut encoder = connect(false); + + assert!(encoder.encoder.set_max_capacity(200).is_ok()); + + // change capacity to 200. + encoder.send_instructions(CAP_INSTRUCTION_200); + + encoder.encoder.set_max_blocked_streams(1).unwrap(); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 0); + + // send a header block, that creates an new entry and refers to it. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("name1", "value1")], + STREAM_1, + ); + assert_is_index_to_dynamic_post(&buf); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 1); + + // The next one will not create a new entry because the encoder is on max_blocked_streams limit. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("name2", "value2")], + STREAM_2, + ); + assert_is_literal_value_literal_name(&buf); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 1); + + // another header block to already blocked stream can still create a new entry. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("name2", "value2")], + STREAM_1, + ); + assert_is_index_to_dynamic_post(&buf); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 1); + } + + #[test] + fn max_block_streams4() { + let mut encoder = connect(false); + + assert!(encoder.encoder.set_max_capacity(200).is_ok()); + + // change capacity to 200. + encoder.send_instructions(CAP_INSTRUCTION_200); + + encoder.encoder.set_max_blocked_streams(1).unwrap(); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 0); + + // send a header block, that creates an new entry and refers to it. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("name1", "value1")], + STREAM_1, + ); + assert_is_index_to_dynamic_post(&buf); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 1); + + // another header block to already blocked stream can still create a new entry. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("name2", "value2")], + STREAM_1, + ); + assert_is_index_to_dynamic_post(&buf); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 1); + + // receive a header_ack for the first header block. + recv_instruction(&mut encoder, HEADER_ACK_STREAM_ID_1); + + // The stream is still blocking because the second header block is not acked. + assert_eq!(encoder.encoder.blocked_stream_cnt(), 1); + } + + #[test] + fn max_block_streams5() { + let mut encoder = connect(false); + + assert!(encoder.encoder.set_max_capacity(200).is_ok()); + + // change capacity to 200. + encoder.send_instructions(CAP_INSTRUCTION_200); + + encoder.encoder.set_max_blocked_streams(1).unwrap(); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 0); + + // send a header block, that creates an new entry and refers to it. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("name1", "value1")], + STREAM_1, + ); + assert_is_index_to_dynamic_post(&buf); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 1); + + // another header block to already blocked stream can still create a new entry. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("name1", "value1")], + STREAM_1, + ); + assert_is_index_to_dynamic(&buf); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 1); + + // receive a header_ack for the first header block. + recv_instruction(&mut encoder, HEADER_ACK_STREAM_ID_1); + + // The stream is not blocking anymore because header ack also acks the instruction. + assert_eq!(encoder.encoder.blocked_stream_cnt(), 0); + } + + #[test] + fn max_block_streams6() { + let mut encoder = connect(false); + + assert!(encoder.encoder.set_max_capacity(200).is_ok()); + + // change capacity to 200. + encoder.send_instructions(CAP_INSTRUCTION_200); + + encoder.encoder.set_max_blocked_streams(2).unwrap(); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 0); + + // send a header block, that creates an new entry and refers to it. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("name1", "value1")], + STREAM_1, + ); + assert_is_index_to_dynamic_post(&buf); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 1); + + // header block for the next stream will create an new entry as well. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("name2", "value2")], + STREAM_2, + ); + assert_is_index_to_dynamic_post(&buf); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 2); + + // receive a header_ack for the second header block. This will ack the first as well + recv_instruction(&mut encoder, HEADER_ACK_STREAM_ID_2); + + // The stream is not blocking anymore because header ack also acks the instruction. + assert_eq!(encoder.encoder.blocked_stream_cnt(), 0); + } + + #[test] + fn max_block_streams7() { + let mut encoder = connect(false); + + assert!(encoder.encoder.set_max_capacity(200).is_ok()); + + // change capacity to 200. + encoder.send_instructions(CAP_INSTRUCTION_200); + + encoder.encoder.set_max_blocked_streams(2).unwrap(); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 0); + + // send a header block, that creates an new entry and refers to it. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("name1", "value1")], + STREAM_1, + ); + assert_is_index_to_dynamic_post(&buf); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 1); + + // header block for the next stream will create an new entry as well. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("name1", "value1")], + STREAM_2, + ); + assert_is_index_to_dynamic(&buf); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 2); + + // receive a stream cancel for the first stream. + // This will remove the first stream as blocking but it will not mark the instruction as acked. + // and the second steam will still be blocking. + recv_instruction(&mut encoder, STREAM_CANCELED_ID_1); + + // The stream is not blocking anymore because header ack also acks the instruction. + assert_eq!(encoder.encoder.blocked_stream_cnt(), 1); + } + + #[test] + fn max_block_stream8() { + let mut encoder = connect(false); + + assert!(encoder.encoder.set_max_capacity(200).is_ok()); + + // change capacity to 200. + encoder.send_instructions(CAP_INSTRUCTION_200); + + encoder.encoder.set_max_blocked_streams(2).unwrap(); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 0); + + // send a header block, that creates an new entry and refers to it. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("name1", "value1")], + STREAM_1, + ); + assert_is_index_to_dynamic_post(&buf); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 1); + + // header block for the next stream will refer to the same entry. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("name1", "value1")], + STREAM_2, + ); + assert_is_index_to_dynamic(&buf); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 2); + + // send another header block on stream 1. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("name2", "value2")], + STREAM_1, + ); + assert_is_index_to_dynamic_post(&buf); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 2); + + // stream 1 is block on entries 1 and 2; stream 2 is block only on 1. + // receive an Insert Count Increment for the first entry. + // After that only stream 1 will be blocking. + recv_instruction(&mut encoder, &[0x01]); + + assert_eq!(encoder.encoder.blocked_stream_cnt(), 1); + } + + #[test] + fn dynamic_table_can_evict1() { + let mut encoder = connect(false); + + assert!(encoder.encoder.set_max_capacity(60).is_ok()); + + // change capacity to 60. + encoder.send_instructions(CAP_INSTRUCTION_60); + + encoder.encoder.set_max_blocked_streams(2).unwrap(); + + // insert "content-length: 1234 + let res = + encoder + .encoder + .send_and_insert(&mut encoder.conn, HEADER_CONTENT_LENGTH, VALUE_1); + + assert!(res.is_ok()); + encoder.send_instructions(HEADER_CONTENT_LENGTH_VALUE_1_NAME_LITERAL); + + // send a header block, it refers to unacked entry. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("content-length", "1234")], + STREAM_1, + ); + assert_is_index_to_dynamic(&buf); + + // trying to evict the entry will failed. + assert!(encoder.change_capacity(10).is_err()); + + // receive an Insert Count Increment for the entry. + recv_instruction(&mut encoder, &[0x01]); + + // trying to evict the entry will failed. The stream is still referring to it. + assert!(encoder.change_capacity(10).is_err()); + + // receive a header_ack for the header block. + recv_instruction(&mut encoder, HEADER_ACK_STREAM_ID_1); + + // now entry can be evicted. + assert!(encoder.change_capacity(10).is_ok()); + } + + #[test] + fn dynamic_table_can_evict2() { + let mut encoder = connect(false); + + assert!(encoder.encoder.set_max_capacity(60).is_ok()); + + // change capacity to 60. + encoder.send_instructions(CAP_INSTRUCTION_60); + + encoder.encoder.set_max_blocked_streams(2).unwrap(); + + // insert "content-length: 1234 + let res = + encoder + .encoder + .send_and_insert(&mut encoder.conn, HEADER_CONTENT_LENGTH, VALUE_1); + + assert!(res.is_ok()); + encoder.send_instructions(HEADER_CONTENT_LENGTH_VALUE_1_NAME_LITERAL); + + // send a header block, it refers to unacked entry. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("content-length", "1234")], + STREAM_1, + ); + assert_is_index_to_dynamic(&buf); + + // trying to evict the entry will failed. + assert!(encoder.change_capacity(10).is_err()); + + // receive an Insert Count Increment for the entry. + recv_instruction(&mut encoder, &[0x01]); + + // trying to evict the entry will failed. The stream is still referring to it. + assert!(encoder.change_capacity(10).is_err()); + + // receive a stream cancelled. + recv_instruction(&mut encoder, STREAM_CANCELED_ID_1); + + // now entry can be evicted. + assert!(encoder.change_capacity(10).is_ok()); + } + + #[test] + fn dynamic_table_can_evict3() { + let mut encoder = connect(false); + + assert!(encoder.encoder.set_max_capacity(60).is_ok()); + + // change capacity to 60. + encoder.send_instructions(CAP_INSTRUCTION_60); + + encoder.encoder.set_max_blocked_streams(2).unwrap(); + + // insert "content-length: 1234 + let res = + encoder + .encoder + .send_and_insert(&mut encoder.conn, HEADER_CONTENT_LENGTH, VALUE_1); + + assert!(res.is_ok()); + encoder.send_instructions(HEADER_CONTENT_LENGTH_VALUE_1_NAME_LITERAL); + + // trying to evict the entry will failed, because the entry is not acked. + assert!(encoder.change_capacity(10).is_err()); + + // receive an Insert Count Increment for the entry. + recv_instruction(&mut encoder, &[0x01]); + + // now entry can be evicted. + assert!(encoder.change_capacity(10).is_ok()); + } + + #[test] + fn dynamic_table_can_evict4() { + let mut encoder = connect(false); + + assert!(encoder.encoder.set_max_capacity(60).is_ok()); + + // change capacity to 60. + encoder.send_instructions(CAP_INSTRUCTION_60); + + encoder.encoder.set_max_blocked_streams(2).unwrap(); + + // insert "content-length: 1234 + let res = + encoder + .encoder + .send_and_insert(&mut encoder.conn, HEADER_CONTENT_LENGTH, VALUE_1); + + assert!(res.is_ok()); + encoder.send_instructions(HEADER_CONTENT_LENGTH_VALUE_1_NAME_LITERAL); + + // send a header block, it refers to unacked entry. + let buf = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[Header::new("content-length", "1234")], + STREAM_1, + ); + assert_is_index_to_dynamic(&buf); + + // trying to evict the entry will failed. The stream is still referring to it and + // entry is not acked. + assert!(encoder.change_capacity(10).is_err()); + + // receive a header_ack for the header block. This will also ack the instruction. + recv_instruction(&mut encoder, HEADER_ACK_STREAM_ID_1); + + // now entry can be evicted. + assert!(encoder.change_capacity(10).is_ok()); + } + + #[test] + fn encoder_flow_controlled_blocked() { + const SMALL_MAX_DATA: u64 = 20; + const ONE_INSTRUCTION_1: &[u8] = &[ + 0x67, 0x41, 0xe9, 0x2a, 0x67, 0x35, 0x53, 0x7f, 0x83, 0x8, 0x99, 0x6b, + ]; + const ONE_INSTRUCTION_2: &[u8] = &[ + 0x67, 0x41, 0xe9, 0x2a, 0x67, 0x35, 0x53, 0x37, 0x83, 0x8, 0x99, 0x6b, + ]; + + let mut encoder = connect_flow_control(SMALL_MAX_DATA); + + // change capacity to 1000 and max_block streams to 20. + encoder.encoder.set_max_blocked_streams(20).unwrap(); + assert!(encoder.encoder.set_max_capacity(1000).is_ok()); + encoder.send_instructions(CAP_INSTRUCTION_1000); + + // Encode a header block with 2 headers. The first header will be added to the dynamic table. + // The second will not be added to the dynamic table, because the corresponding instruction + // cannot be written immediately due to the flow control limit. + let buf1 = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[ + Header::new("something", "1234"), + Header::new("something2", "12345678910"), + ], + STREAM_1, + ); + + // Assert that the first header is encoded as an index to the dynamic table (a post form). + assert_eq!(buf1[2], 0x10); + // Assert that the second header is encoded as a literal with a name literal + assert_eq!(buf1[3] & 0xf0, 0x20); + + // Try to encode another header block. Here both headers will be encoded as a literal with a name literal + let buf2 = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[ + Header::new("something3", "1234"), + Header::new("something4", "12345678910"), + ], + STREAM_2, + ); + assert_eq!(buf2[2] & 0xf0, 0x20); + + // Ensure that we have sent only one instruction for (String::from("something", "1234")) + encoder.send_instructions(ONE_INSTRUCTION_1); + + // exchange a flow control update. + let out = encoder.peer_conn.process(None, now()); + mem::drop(encoder.conn.process(out.dgram(), now())); + + // Try writing a new header block. Now, headers will be added to the dynamic table again, because + // instructions can be sent. + let buf3 = encoder.encoder.encode_header_block( + &mut encoder.conn, + &[ + Header::new("something5", "1234"), + Header::new("something6", "12345678910"), + ], + StreamId::new(3), + ); + // Assert that the first header is encoded as an index to the dynamic table (a post form). + assert_eq!(buf3[2], 0x10); + // Assert that the second header is encoded as a literal with a name literal + assert_eq!(buf3[3] & 0xf0, 0x20); + + // Asset that one instruction has been sent + encoder.send_instructions(ONE_INSTRUCTION_2); + } + + #[test] + fn encoder_max_capacity_limit() { + let mut encoder = connect(false); + + // change capacity to 2000. + assert!(encoder.encoder.set_max_capacity(2000).is_ok()); + encoder.send_instructions(CAP_INSTRUCTION_1500); + } + + #[test] + fn test_do_not_evict_entry_that_are_referred_only_by_the_same_header_blocked_encoding() { + let mut encoder = connect(false); + + encoder.encoder.set_max_blocked_streams(20).unwrap(); + assert!(encoder.change_capacity(50).is_ok()); + + encoder + .encoder + .send_and_insert(&mut encoder.conn, b"something5", b"1234") + .unwrap(); + + encoder + .encoder + .send_encoder_updates(&mut encoder.conn) + .unwrap(); + let out = encoder.conn.process(None, now()); + mem::drop(encoder.peer_conn.process(out.dgram(), now())); + // receive an insert count increment. + recv_instruction(&mut encoder, &[0x01]); + + // The first header will use the table entry and the second will use the literal + // encoding because the first entry is referred to and cannot be evicted. + assert_eq!( + encoder + .encoder + .encode_header_block( + &mut encoder.conn, + &[ + Header::new("something5", "1234"), + Header::new("something6", "1234"), + ], + StreamId::new(3), + ) + .to_vec(), + &[ + 0x02, 0x00, 0x80, 0x27, 0x03, 0x73, 0x6f, 0x6d, 0x65, 0x74, 0x68, 0x69, 0x6e, 0x67, + 0x36, 0x04, 0x31, 0x32, 0x33, 0x34 + ] + ); + // Also check that ther is no new instruction send by the encoder. + assert!(encoder.conn.process_output(now()).dgram().is_none()); + } + + #[test] + fn test_streams_cancel_cleans_up_unacked_header_blocks() { + let mut encoder = connect(false); + + encoder.encoder.set_max_blocked_streams(10).unwrap(); + assert!(encoder.change_capacity(60).is_ok()); + encoder.send_instructions(CAP_INSTRUCTION_60); + + // insert "content-length: 1234 + encoder.insert( + HEADER_CONTENT_LENGTH, + VALUE_1, + HEADER_CONTENT_LENGTH_VALUE_1_NAME_LITERAL, + ); + + // send a header block + encoder.encode_header_block( + StreamId::new(1), + &[Header::new("content-length", "1234")], + ENCODE_INDEXED_REF_DYNAMIC, + &[], + ); + + // receive a stream canceled instruction. + recv_instruction(&mut encoder, STREAM_CANCELED_ID_1); + + recv_instruction(&mut encoder, &[0x01]); + } +} diff --git a/third_party/rust/neqo-qpack/src/encoder_instructions.rs b/third_party/rust/neqo-qpack/src/encoder_instructions.rs new file mode 100644 index 0000000000..93be06bf7f --- /dev/null +++ b/third_party/rust/neqo-qpack/src/encoder_instructions.rs @@ -0,0 +1,499 @@ +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use crate::prefix::{ + ENCODER_CAPACITY, ENCODER_DUPLICATE, ENCODER_INSERT_WITH_NAME_LITERAL, + ENCODER_INSERT_WITH_NAME_REF_DYNAMIC, ENCODER_INSERT_WITH_NAME_REF_STATIC, NO_PREFIX, +}; +use crate::qpack_send_buf::QpackData; +use crate::reader::{IntReader, LiteralReader, ReadByte, Reader}; +use crate::Res; +use neqo_common::{qdebug, qtrace}; +use std::mem; + +// The encoder only uses InsertWithNameLiteral, therefore clippy is complaining about dead_code. +// We may decide to use othe instruction in the future. +// All instructions are used for testing, therefore they are defined. +#[allow(dead_code)] +#[derive(Debug, PartialEq, Eq)] +pub enum EncoderInstruction<'a> { + Capacity { value: u64 }, + InsertWithNameRefStatic { index: u64, value: &'a [u8] }, + InsertWithNameRefDynamic { index: u64, value: &'a [u8] }, + InsertWithNameLiteral { name: &'a [u8], value: &'a [u8] }, + Duplicate { index: u64 }, + NoInstruction, +} + +impl<'a> EncoderInstruction<'a> { + pub(crate) fn marshal(&self, enc: &mut QpackData, use_huffman: bool) { + match self { + Self::Capacity { value } => { + enc.encode_prefixed_encoded_int(ENCODER_CAPACITY, *value); + } + Self::InsertWithNameRefStatic { index, value } => { + enc.encode_prefixed_encoded_int(ENCODER_INSERT_WITH_NAME_REF_STATIC, *index); + enc.encode_literal(use_huffman, NO_PREFIX, value); + } + Self::InsertWithNameRefDynamic { index, value } => { + enc.encode_prefixed_encoded_int(ENCODER_INSERT_WITH_NAME_REF_DYNAMIC, *index); + enc.encode_literal(use_huffman, NO_PREFIX, value); + } + Self::InsertWithNameLiteral { name, value } => { + enc.encode_literal(use_huffman, ENCODER_INSERT_WITH_NAME_LITERAL, name); + enc.encode_literal(use_huffman, NO_PREFIX, value); + } + Self::Duplicate { index } => { + enc.encode_prefixed_encoded_int(ENCODER_DUPLICATE, *index); + } + Self::NoInstruction => {} + } + } +} + +#[derive(Debug)] +enum EncoderInstructionReaderState { + ReadInstruction, + ReadFirstInt { reader: IntReader }, + ReadFirstLiteral { reader: LiteralReader }, + ReadSecondLiteral { reader: LiteralReader }, + Done, +} + +#[derive(Debug, PartialEq, Eq)] +pub enum DecodedEncoderInstruction { + Capacity { value: u64 }, + InsertWithNameRefStatic { index: u64, value: Vec<u8> }, + InsertWithNameRefDynamic { index: u64, value: Vec<u8> }, + InsertWithNameLiteral { name: Vec<u8>, value: Vec<u8> }, + Duplicate { index: u64 }, + NoInstruction, +} + +impl<'a> From<&'a EncoderInstruction<'a>> for DecodedEncoderInstruction { + fn from(inst: &'a EncoderInstruction) -> Self { + match inst { + EncoderInstruction::Capacity { value } => Self::Capacity { value: *value }, + EncoderInstruction::InsertWithNameRefStatic { index, value } => { + Self::InsertWithNameRefStatic { + index: *index, + value: value.to_vec(), + } + } + EncoderInstruction::InsertWithNameRefDynamic { index, value } => { + Self::InsertWithNameRefDynamic { + index: *index, + value: value.to_vec(), + } + } + EncoderInstruction::InsertWithNameLiteral { name, value } => { + Self::InsertWithNameLiteral { + name: name.to_vec(), + value: value.to_vec(), + } + } + EncoderInstruction::Duplicate { index } => Self::Duplicate { index: *index }, + EncoderInstruction::NoInstruction => Self::NoInstruction, + } + } +} + +#[derive(Debug)] +pub struct EncoderInstructionReader { + state: EncoderInstructionReaderState, + instruction: DecodedEncoderInstruction, +} + +impl ::std::fmt::Display for EncoderInstructionReader { + fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result { + write!( + f, + "EncoderInstructionReader state={:?} instruction:{:?}", + self.state, self.instruction + ) + } +} + +impl EncoderInstructionReader { + pub fn new() -> Self { + Self { + state: EncoderInstructionReaderState::ReadInstruction, + instruction: DecodedEncoderInstruction::NoInstruction, + } + } + + fn decode_instruction_from_byte(&mut self, b: u8) { + self.instruction = if ENCODER_INSERT_WITH_NAME_REF_STATIC.cmp_prefix(b) { + DecodedEncoderInstruction::InsertWithNameRefStatic { + index: 0, + value: Vec::new(), + } + } else if ENCODER_INSERT_WITH_NAME_REF_DYNAMIC.cmp_prefix(b) { + DecodedEncoderInstruction::InsertWithNameRefDynamic { + index: 0, + value: Vec::new(), + } + } else if ENCODER_INSERT_WITH_NAME_LITERAL.cmp_prefix(b) { + DecodedEncoderInstruction::InsertWithNameLiteral { + name: Vec::new(), + value: Vec::new(), + } + } else if ENCODER_CAPACITY.cmp_prefix(b) { + DecodedEncoderInstruction::Capacity { value: 0 } + } else if ENCODER_DUPLICATE.cmp_prefix(b) { + DecodedEncoderInstruction::Duplicate { index: 0 } + } else { + unreachable!("The above patterns match everything."); + }; + qdebug!([self], "instruction decoded"); + } + + fn decode_instruction_type<T: ReadByte + Reader>(&mut self, recv: &mut T) -> Res<()> { + let b = recv.read_byte()?; + + self.decode_instruction_from_byte(b); + match self.instruction { + DecodedEncoderInstruction::Capacity { .. } + | DecodedEncoderInstruction::Duplicate { .. } => { + self.state = EncoderInstructionReaderState::ReadFirstInt { + reader: IntReader::new(b, ENCODER_CAPACITY.len()), + } + } + DecodedEncoderInstruction::InsertWithNameRefStatic { .. } + | DecodedEncoderInstruction::InsertWithNameRefDynamic { .. } => { + self.state = EncoderInstructionReaderState::ReadFirstInt { + reader: IntReader::new(b, ENCODER_INSERT_WITH_NAME_REF_STATIC.len()), + } + } + DecodedEncoderInstruction::InsertWithNameLiteral { .. } => { + self.state = EncoderInstructionReaderState::ReadFirstLiteral { + reader: LiteralReader::new_with_first_byte( + b, + ENCODER_INSERT_WITH_NAME_LITERAL.len(), + ), + } + } + DecodedEncoderInstruction::NoInstruction => { + unreachable!("We must have instruction at this point."); + } + } + Ok(()) + } + + /// ### Errors + /// 1) `NeedMoreData` if the reader needs more data + /// 2) `ClosedCriticalStream` + /// 3) other errors will be translated to `EncoderStream` by the caller of this function. + pub fn read_instructions<T: ReadByte + Reader>( + &mut self, + recv: &mut T, + ) -> Res<DecodedEncoderInstruction> { + qdebug!([self], "reading instructions"); + loop { + match &mut self.state { + EncoderInstructionReaderState::ReadInstruction => { + self.decode_instruction_type(recv)?; + } + EncoderInstructionReaderState::ReadFirstInt { reader } => { + let val = reader.read(recv)?; + + qtrace!([self], "First varint read {}", val); + match &mut self.instruction { + DecodedEncoderInstruction::Capacity { value: v, .. } + | DecodedEncoderInstruction::Duplicate { index: v } => { + *v = val; + self.state = EncoderInstructionReaderState::Done; + } + DecodedEncoderInstruction::InsertWithNameRefStatic { index, .. } + | DecodedEncoderInstruction::InsertWithNameRefDynamic { index, .. } => { + *index = val; + self.state = EncoderInstructionReaderState::ReadFirstLiteral { + reader: LiteralReader::default(), + }; + } + _ => unreachable!("This instruction cannot be in this state."), + } + } + EncoderInstructionReaderState::ReadFirstLiteral { reader } => { + let val = reader.read(recv)?; + + qtrace!([self], "first literal read {:?}", val); + match &mut self.instruction { + DecodedEncoderInstruction::InsertWithNameRefStatic { value, .. } + | DecodedEncoderInstruction::InsertWithNameRefDynamic { value, .. } => { + *value = val; + self.state = EncoderInstructionReaderState::Done; + } + DecodedEncoderInstruction::InsertWithNameLiteral { name, .. } => { + *name = val; + self.state = EncoderInstructionReaderState::ReadSecondLiteral { + reader: LiteralReader::default(), + }; + } + _ => unreachable!("This instruction cannot be in this state."), + } + } + EncoderInstructionReaderState::ReadSecondLiteral { reader } => { + let val = reader.read(recv)?; + + qtrace!([self], "second literal read {:?}", val); + match &mut self.instruction { + DecodedEncoderInstruction::InsertWithNameLiteral { value, .. } => { + *value = val; + self.state = EncoderInstructionReaderState::Done; + } + _ => unreachable!("This instruction cannot be in this state."), + } + } + EncoderInstructionReaderState::Done => {} + } + if matches!(self.state, EncoderInstructionReaderState::Done) { + self.state = EncoderInstructionReaderState::ReadInstruction; + break Ok(mem::replace( + &mut self.instruction, + DecodedEncoderInstruction::NoInstruction, + )); + } + } + } +} + +#[cfg(test)] +mod test { + + use super::{EncoderInstruction, EncoderInstructionReader, QpackData}; + use crate::reader::test_receiver::TestReceiver; + use crate::Error; + + fn test_encoding_decoding(instruction: &EncoderInstruction, use_huffman: bool) { + let mut buf = QpackData::default(); + instruction.marshal(&mut buf, use_huffman); + let mut test_receiver: TestReceiver = TestReceiver::default(); + test_receiver.write(&buf); + let mut reader = EncoderInstructionReader::new(); + assert_eq!( + reader.read_instructions(&mut test_receiver).unwrap(), + instruction.into() + ); + } + + #[test] + fn test_encoding_decoding_instructions() { + test_encoding_decoding(&EncoderInstruction::Capacity { value: 1 }, false); + test_encoding_decoding(&EncoderInstruction::Capacity { value: 10_000 }, false); + + test_encoding_decoding( + &EncoderInstruction::InsertWithNameRefStatic { + index: 1, + value: &[0x62, 0x64, 0x65], + }, + false, + ); + test_encoding_decoding( + &EncoderInstruction::InsertWithNameRefStatic { + index: 1, + value: &[0x62, 0x64, 0x65], + }, + true, + ); + test_encoding_decoding( + &EncoderInstruction::InsertWithNameRefStatic { + index: 10_000, + value: &[0x62, 0x64, 0x65], + }, + false, + ); + test_encoding_decoding( + &EncoderInstruction::InsertWithNameRefStatic { + index: 10_000, + value: &[0x62, 0x64, 0x65], + }, + true, + ); + + test_encoding_decoding( + &EncoderInstruction::InsertWithNameRefDynamic { + index: 1, + value: &[0x62, 0x64, 0x65], + }, + false, + ); + test_encoding_decoding( + &EncoderInstruction::InsertWithNameRefDynamic { + index: 1, + value: &[0x62, 0x64, 0x65], + }, + true, + ); + test_encoding_decoding( + &EncoderInstruction::InsertWithNameRefDynamic { + index: 10_000, + value: &[0x62, 0x64, 0x65], + }, + false, + ); + test_encoding_decoding( + &EncoderInstruction::InsertWithNameRefDynamic { + index: 10_000, + value: &[0x62, 0x64, 0x65], + }, + true, + ); + + test_encoding_decoding( + &EncoderInstruction::InsertWithNameLiteral { + name: &[0x62, 0x64, 0x65], + value: &[0x62, 0x64, 0x65], + }, + false, + ); + test_encoding_decoding( + &EncoderInstruction::InsertWithNameLiteral { + name: &[0x62, 0x64, 0x65], + value: &[0x62, 0x64, 0x65], + }, + true, + ); + + test_encoding_decoding(&EncoderInstruction::Duplicate { index: 1 }, false); + test_encoding_decoding(&EncoderInstruction::Duplicate { index: 10_000 }, false); + } + + fn test_encoding_decoding_slow_reader(instruction: &EncoderInstruction, use_huffman: bool) { + let mut buf = QpackData::default(); + instruction.marshal(&mut buf, use_huffman); + let mut test_receiver: TestReceiver = TestReceiver::default(); + let mut decoder = EncoderInstructionReader::new(); + for i in 0..buf.len() - 1 { + test_receiver.write(&buf[i..=i]); + assert_eq!( + decoder.read_instructions(&mut test_receiver), + Err(Error::NeedMoreData) + ); + } + test_receiver.write(&buf[buf.len() - 1..buf.len()]); + assert_eq!( + decoder.read_instructions(&mut test_receiver).unwrap(), + instruction.into() + ); + } + + #[test] + fn test_encoding_decoding_instructions_slow_reader() { + test_encoding_decoding_slow_reader(&EncoderInstruction::Capacity { value: 1 }, false); + test_encoding_decoding_slow_reader(&EncoderInstruction::Capacity { value: 10_000 }, false); + + test_encoding_decoding_slow_reader( + &EncoderInstruction::InsertWithNameRefStatic { + index: 1, + value: &[0x62, 0x64, 0x65], + }, + false, + ); + test_encoding_decoding_slow_reader( + &EncoderInstruction::InsertWithNameRefStatic { + index: 1, + value: &[0x62, 0x64, 0x65], + }, + true, + ); + test_encoding_decoding_slow_reader( + &EncoderInstruction::InsertWithNameRefStatic { + index: 10_000, + value: &[0x62, 0x64, 0x65], + }, + false, + ); + test_encoding_decoding_slow_reader( + &EncoderInstruction::InsertWithNameRefStatic { + index: 10_000, + value: &[0x62, 0x64, 0x65], + }, + true, + ); + + test_encoding_decoding_slow_reader( + &EncoderInstruction::InsertWithNameRefDynamic { + index: 1, + value: &[0x62, 0x64, 0x65], + }, + false, + ); + test_encoding_decoding_slow_reader( + &EncoderInstruction::InsertWithNameRefDynamic { + index: 1, + value: &[0x62, 0x64, 0x65], + }, + true, + ); + test_encoding_decoding_slow_reader( + &EncoderInstruction::InsertWithNameRefDynamic { + index: 10_000, + value: &[0x62, 0x64, 0x65], + }, + false, + ); + test_encoding_decoding_slow_reader( + &EncoderInstruction::InsertWithNameRefDynamic { + index: 10_000, + value: &[0x62, 0x64, 0x65], + }, + true, + ); + + test_encoding_decoding_slow_reader( + &EncoderInstruction::InsertWithNameLiteral { + name: &[0x62, 0x64, 0x65], + value: &[0x62, 0x64, 0x65], + }, + false, + ); + test_encoding_decoding_slow_reader( + &EncoderInstruction::InsertWithNameLiteral { + name: &[0x62, 0x64, 0x65], + value: &[0x62, 0x64, 0x65], + }, + true, + ); + + test_encoding_decoding_slow_reader(&EncoderInstruction::Duplicate { index: 1 }, false); + test_encoding_decoding_slow_reader(&EncoderInstruction::Duplicate { index: 10_000 }, false); + } + + #[test] + fn test_decoding_error() { + let mut test_receiver: TestReceiver = TestReceiver::default(); + // EncoderInstruction::Capacity with overflow + test_receiver.write(&[ + 0x3f, 0xc1, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xff, 0x02, + ]); + let mut decoder = EncoderInstructionReader::new(); + assert_eq!( + decoder.read_instructions(&mut test_receiver), + Err(Error::IntegerOverflow) + ); + + let mut test_receiver: TestReceiver = TestReceiver::default(); + // EncoderInstruction::InsertWithNameRefStatic with overflow of index value. + test_receiver.write(&[ + 0xff, 0xc1, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xff, 0x02, 0x00, 0x00, + ]); + let mut decoder = EncoderInstructionReader::new(); + assert_eq!( + decoder.read_instructions(&mut test_receiver), + Err(Error::IntegerOverflow) + ); + + let mut test_receiver: TestReceiver = TestReceiver::default(); + // EncoderInstruction::InsertWithNameRefStatic with a garbage value. + test_receiver.write(&[0xc1, 0x81, 0x00]); + let mut decoder = EncoderInstructionReader::new(); + assert_eq!( + decoder.read_instructions(&mut test_receiver), + Err(Error::HuffmanDecompressionFailed) + ); + } +} diff --git a/third_party/rust/neqo-qpack/src/header_block.rs b/third_party/rust/neqo-qpack/src/header_block.rs new file mode 100644 index 0000000000..38f8738df9 --- /dev/null +++ b/third_party/rust/neqo-qpack/src/header_block.rs @@ -0,0 +1,933 @@ +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use crate::prefix::{ + BASE_PREFIX_NEGATIVE, BASE_PREFIX_POSITIVE, HEADER_FIELD_INDEX_DYNAMIC, + HEADER_FIELD_INDEX_DYNAMIC_POST, HEADER_FIELD_INDEX_STATIC, HEADER_FIELD_LITERAL_NAME_LITERAL, + HEADER_FIELD_LITERAL_NAME_REF_DYNAMIC, HEADER_FIELD_LITERAL_NAME_REF_DYNAMIC_POST, + HEADER_FIELD_LITERAL_NAME_REF_STATIC, NO_PREFIX, +}; +use crate::qpack_send_buf::QpackData; +use crate::reader::{to_string, ReceiverBufferWrapper}; +use crate::table::HeaderTable; +use crate::{Error, Res}; +use neqo_common::{qtrace, Header}; +use std::mem; +use std::ops::{Deref, Div}; + +#[derive(Default, Debug, PartialEq)] +pub struct HeaderEncoder { + buf: QpackData, + base: u64, + use_huffman: bool, + max_entries: u64, + max_dynamic_index_ref: Option<u64>, +} + +impl ::std::fmt::Display for HeaderEncoder { + fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result { + write!(f, "HeaderEncoder") + } +} + +impl HeaderEncoder { + pub fn new(base: u64, use_huffman: bool, max_entries: u64) -> Self { + Self { + buf: QpackData::default(), + base, + use_huffman, + max_entries, + max_dynamic_index_ref: None, + } + } + + pub fn len(&self) -> usize { + self.buf.len() + } + + pub fn read(&mut self, r: usize) { + self.buf.read(r); + } + + pub fn encode_indexed_static(&mut self, index: u64) { + qtrace!([self], "encode static index {}.", index); + self.buf + .encode_prefixed_encoded_int(HEADER_FIELD_INDEX_STATIC, index); + } + + fn new_ref(&mut self, index: u64) { + if let Some(r) = self.max_dynamic_index_ref { + if r < index { + self.max_dynamic_index_ref = Some(index); + } + } else { + self.max_dynamic_index_ref = Some(index); + } + } + + pub fn encode_indexed_dynamic(&mut self, index: u64) { + qtrace!([self], "encode dynamic index {}.", index); + if index < self.base { + self.buf + .encode_prefixed_encoded_int(HEADER_FIELD_INDEX_DYNAMIC, self.base - index - 1); + } else { + self.buf + .encode_prefixed_encoded_int(HEADER_FIELD_INDEX_DYNAMIC_POST, index - self.base); + } + self.new_ref(index); + } + + pub fn encode_literal_with_name_ref(&mut self, is_static: bool, index: u64, value: &[u8]) { + qtrace!( + [self], + "encode literal with name ref - index={}, static={}, value={:x?}", + index, + is_static, + value + ); + if is_static { + self.buf + .encode_prefixed_encoded_int(HEADER_FIELD_LITERAL_NAME_REF_STATIC, index); + } else if index < self.base { + self.buf.encode_prefixed_encoded_int( + HEADER_FIELD_LITERAL_NAME_REF_DYNAMIC, + self.base - index - 1, + ); + self.new_ref(index); + } else { + self.buf.encode_prefixed_encoded_int( + HEADER_FIELD_LITERAL_NAME_REF_DYNAMIC_POST, + index - self.base, + ); + self.new_ref(index); + } + + self.buf.encode_literal(self.use_huffman, NO_PREFIX, value); + } + + pub fn encode_literal_with_name_literal(&mut self, name: &[u8], value: &[u8]) { + qtrace!( + [self], + "encode literal with name literal - name={:x?}, value={:x?}.", + name, + value + ); + self.buf + .encode_literal(self.use_huffman, HEADER_FIELD_LITERAL_NAME_LITERAL, name); + self.buf.encode_literal(self.use_huffman, NO_PREFIX, value); + } + + pub fn encode_header_block_prefix(&mut self) { + let tmp = mem::take(&mut self.buf); + let (enc_insert_cnt, delta, prefix) = + self.max_dynamic_index_ref + .map_or((0, self.base, BASE_PREFIX_POSITIVE), |r| { + let req_insert_cnt = r + 1; + if req_insert_cnt <= self.base { + ( + req_insert_cnt % (2 * self.max_entries) + 1, + self.base - req_insert_cnt, + BASE_PREFIX_POSITIVE, + ) + } else { + ( + req_insert_cnt % (2 * self.max_entries) + 1, + req_insert_cnt - self.base - 1, + BASE_PREFIX_NEGATIVE, + ) + } + }); + qtrace!( + [self], + "encode header block prefix max_dynamic_index_ref={:?}, base={}, enc_insert_cnt={}, delta={}, prefix={:?}.", + self.max_dynamic_index_ref, + self.base, + enc_insert_cnt, + delta, + prefix + ); + + self.buf + .encode_prefixed_encoded_int(NO_PREFIX, enc_insert_cnt); + self.buf.encode_prefixed_encoded_int(prefix, delta); + + self.buf.write_bytes(&tmp); + } +} + +impl Deref for HeaderEncoder { + type Target = [u8]; + fn deref(&self) -> &Self::Target { + &self.buf + } +} + +pub(crate) struct HeaderDecoder<'a> { + buf: ReceiverBufferWrapper<'a>, + base: u64, + req_insert_cnt: u64, +} + +impl<'a> ::std::fmt::Display for HeaderDecoder<'a> { + fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result { + write!(f, "HeaderDecoder") + } +} + +#[derive(Debug, PartialEq, Eq)] +pub enum HeaderDecoderResult { + Blocked(u64), + Headers(Vec<Header>), +} + +impl<'a> HeaderDecoder<'a> { + pub fn new(buf: &'a [u8]) -> Self { + Self { + buf: ReceiverBufferWrapper::new(buf), + base: 0, + req_insert_cnt: 0, + } + } + + pub fn refers_dynamic_table( + &mut self, + max_entries: u64, + total_num_of_inserts: u64, + ) -> Res<bool> { + Error::map_error( + self.read_base(max_entries, total_num_of_inserts), + Error::DecompressionFailed, + )?; + Ok(self.req_insert_cnt != 0) + } + + pub fn decode_header_block( + &mut self, + table: &HeaderTable, + max_entries: u64, + total_num_of_inserts: u64, + ) -> Res<HeaderDecoderResult> { + Error::map_error( + self.read_base(max_entries, total_num_of_inserts), + Error::DecompressionFailed, + )?; + + if table.base() < self.req_insert_cnt { + qtrace!( + [self], + "decoding is blocked, requested inserts count={}", + self.req_insert_cnt + ); + return Ok(HeaderDecoderResult::Blocked(self.req_insert_cnt)); + } + let mut h: Vec<Header> = Vec::new(); + + while !self.buf.done() { + let b = Error::map_error(self.buf.peek(), Error::DecompressionFailed)?; + if HEADER_FIELD_INDEX_STATIC.cmp_prefix(b) { + h.push(Error::map_error( + self.read_indexed_static(), + Error::DecompressionFailed, + )?); + } else if HEADER_FIELD_INDEX_DYNAMIC.cmp_prefix(b) { + h.push(Error::map_error( + self.read_indexed_dynamic(table), + Error::DecompressionFailed, + )?); + } else if HEADER_FIELD_INDEX_DYNAMIC_POST.cmp_prefix(b) { + h.push(Error::map_error( + self.read_indexed_dynamic_post(table), + Error::DecompressionFailed, + )?); + } else if HEADER_FIELD_LITERAL_NAME_REF_STATIC.cmp_prefix(b) { + h.push(Error::map_error( + self.read_literal_with_name_ref_static(), + Error::DecompressionFailed, + )?); + } else if HEADER_FIELD_LITERAL_NAME_REF_DYNAMIC.cmp_prefix(b) { + h.push(Error::map_error( + self.read_literal_with_name_ref_dynamic(table), + Error::DecompressionFailed, + )?); + } else if HEADER_FIELD_LITERAL_NAME_LITERAL.cmp_prefix(b) { + h.push(Error::map_error( + self.read_literal_with_name_literal(), + Error::DecompressionFailed, + )?); + } else if HEADER_FIELD_LITERAL_NAME_REF_DYNAMIC_POST.cmp_prefix(b) { + h.push(Error::map_error( + self.read_literal_with_name_ref_dynamic_post(table), + Error::DecompressionFailed, + )?); + } else { + unreachable!("All prefixes are covered"); + } + } + + qtrace!([self], "done decoding header block."); + Ok(HeaderDecoderResult::Headers(h)) + } + + pub fn get_req_insert_cnt(&self) -> u64 { + self.req_insert_cnt + } + + fn read_base(&mut self, max_entries: u64, total_num_of_inserts: u64) -> Res<()> { + let insert_cnt = self.buf.read_prefixed_int(0)?; + self.req_insert_cnt = + HeaderDecoder::calc_req_insert_cnt(insert_cnt, max_entries, total_num_of_inserts)?; + + let s = self.buf.peek()? & 0x80 != 0; + let base_delta = self.buf.read_prefixed_int(1)?; + self.base = if s { + if self.req_insert_cnt <= base_delta { + return Err(Error::DecompressionFailed); + } + self.req_insert_cnt - base_delta - 1 + } else { + self.req_insert_cnt + .checked_add(base_delta) + .ok_or(Error::DecompressionFailed)? + }; + qtrace!( + [self], + "requested inserts count is {} and base is {}", + self.req_insert_cnt, + self.base + ); + Ok(()) + } + + fn calc_req_insert_cnt(encoded: u64, max_entries: u64, total_num_of_inserts: u64) -> Res<u64> { + if encoded == 0 { + Ok(0) + } else if max_entries == 0 { + Err(Error::DecompressionFailed) + } else { + let full_range = 2 * max_entries; + if encoded > full_range { + return Err(Error::DecompressionFailed); + } + let max_value = total_num_of_inserts + max_entries; + let max_wrapped = max_value.div(full_range) * full_range; + let mut req_insert_cnt = max_wrapped + encoded - 1; + if req_insert_cnt > max_value { + if req_insert_cnt < full_range { + return Err(Error::DecompressionFailed); + } + req_insert_cnt -= full_range; + } + Ok(req_insert_cnt) + } + } + + fn read_indexed_static(&mut self) -> Res<Header> { + let index = self + .buf + .read_prefixed_int(HEADER_FIELD_INDEX_STATIC.len())?; + qtrace!([self], "decoder static indexed {}.", index); + let entry = HeaderTable::get_static(index)?; + Ok(Header::new( + to_string(entry.name())?, + to_string(entry.value())?, + )) + } + + fn read_indexed_dynamic(&mut self, table: &HeaderTable) -> Res<Header> { + let index = self + .buf + .read_prefixed_int(HEADER_FIELD_INDEX_DYNAMIC.len())?; + qtrace!([self], "decoder dynamic indexed {}.", index); + let entry = table.get_dynamic(index, self.base, false)?; + Ok(Header::new( + to_string(entry.name())?, + to_string(entry.value())?, + )) + } + + fn read_indexed_dynamic_post(&mut self, table: &HeaderTable) -> Res<Header> { + let index = self + .buf + .read_prefixed_int(HEADER_FIELD_INDEX_DYNAMIC_POST.len())?; + qtrace!([self], "decode post-based {}.", index); + let entry = table.get_dynamic(index, self.base, true)?; + Ok(Header::new( + to_string(entry.name())?, + to_string(entry.value())?, + )) + } + + fn read_literal_with_name_ref_static(&mut self) -> Res<Header> { + qtrace!( + [self], + "read literal with name reference to the static table." + ); + + let index = self + .buf + .read_prefixed_int(HEADER_FIELD_LITERAL_NAME_REF_STATIC.len())?; + + Ok(Header::new( + to_string(HeaderTable::get_static(index)?.name())?, + self.buf.read_literal_from_buffer(0)?, + )) + } + + fn read_literal_with_name_ref_dynamic(&mut self, table: &HeaderTable) -> Res<Header> { + qtrace!( + [self], + "read literal with name reference ot the dynamic table." + ); + + let index = self + .buf + .read_prefixed_int(HEADER_FIELD_LITERAL_NAME_REF_DYNAMIC.len())?; + + Ok(Header::new( + to_string(table.get_dynamic(index, self.base, false)?.name())?, + self.buf.read_literal_from_buffer(0)?, + )) + } + + fn read_literal_with_name_ref_dynamic_post(&mut self, table: &HeaderTable) -> Res<Header> { + qtrace!([self], "decoder literal with post-based index."); + + let index = self + .buf + .read_prefixed_int(HEADER_FIELD_LITERAL_NAME_REF_DYNAMIC_POST.len())?; + + Ok(Header::new( + to_string(table.get_dynamic(index, self.base, true)?.name())?, + self.buf.read_literal_from_buffer(0)?, + )) + } + + fn read_literal_with_name_literal(&mut self) -> Res<Header> { + qtrace!([self], "decode literal with name literal."); + + let name = self + .buf + .read_literal_from_buffer(HEADER_FIELD_LITERAL_NAME_LITERAL.len())?; + + Ok(Header::new(name, self.buf.read_literal_from_buffer(0)?)) + } +} + +#[cfg(test)] +mod tests { + + use super::{HeaderDecoder, HeaderDecoderResult, HeaderEncoder, HeaderTable}; + use crate::Error; + + const INDEX_STATIC_TEST: &[(u64, &[u8], &str, &str)] = &[ + (0, &[0x0, 0x0, 0xc0], ":authority", ""), + (10, &[0x0, 0x0, 0xca], "last-modified", ""), + (15, &[0x0, 0x0, 0xcf], ":method", "CONNECT"), + (65, &[0x0, 0x0, 0xff, 0x02], ":status", "206"), + ]; + + const INDEX_DYNAMIC_TEST: &[(u64, &[u8], &str, &str)] = &[ + (0, &[0x02, 0x41, 0xbf, 0x2], "header0", "0"), + (10, &[0x0c, 0x37, 0xb7], "header10", "10"), + (15, &[0x11, 0x32, 0xb2], "header15", "15"), + (65, &[0x43, 0x0, 0x80], "header65", "65"), + ]; + + const INDEX_DYNAMIC_POST_TEST: &[(u64, &[u8], &str, &str)] = &[ + (0, &[0x02, 0x80, 0x10], "header0", "0"), + (10, &[0x0c, 0x8a, 0x1a], "header10", "10"), + (15, &[0x11, 0x8f, 0x1f, 0x00], "header15", "15"), + (65, &[0x43, 0xc1, 0x1f, 0x32], "header65", "65"), + ]; + + const NAME_REF_STATIC: &[(u64, &[u8], &str, &str)] = &[ + ( + 0, + &[ + 0x00, 0x00, 0x50, 0x0a, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, 0x79, + ], + ":authority", + "custom-key", + ), + ( + 10, + &[ + 0x00, 0x00, 0x5a, 0x0a, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, 0x79, + ], + "last-modified", + "custom-key", + ), + ( + 15, + &[ + 0x00, 0x00, 0x5f, 0x00, 0x0a, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, + 0x79, + ], + ":method", + "custom-key", + ), + ( + 65, + &[ + 0x00, 0x00, 0x5f, 0x32, 0x0a, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, + 0x79, + ], + ":status", + "custom-key", + ), + ]; + + const NAME_REF_DYNAMIC: &[(u64, &[u8], &str, &str)] = &[ + ( + 0, + &[ + 0x02, 0x41, 0x4f, 0x32, 0x0a, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, + 0x79, + ], + "header0", + "custom-key", + ), + ( + 10, + &[ + 0x0c, 0x37, 0x4f, 0x28, 0x0a, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, + 0x79, + ], + "header10", + "custom-key", + ), + ( + 15, + &[ + 0x11, 0x32, 0x4f, 0x23, 0x0a, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, + 0x79, + ], + "header15", + "custom-key", + ), + ( + 65, + &[ + 0x43, 0x00, 0x40, 0x0a, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, 0x79, + ], + "header65", + "custom-key", + ), + ]; + + const NAME_REF_DYNAMIC_POST: &[(u64, &[u8], &str, &str)] = &[ + ( + 0, + &[ + 0x02, 0x80, 0x00, 0x0a, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, 0x79, + ], + "header0", + "custom-key", + ), + ( + 10, + &[ + 0x0c, 0x8a, 0x07, 0x03, 0x0a, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, + 0x79, + ], + "header10", + "custom-key", + ), + ( + 15, + &[ + 0x11, 0x8f, 0x07, 0x08, 0x0a, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, + 0x79, + ], + "header15", + "custom-key", + ), + ( + 65, + &[ + 0x43, 0xc1, 0x07, 0x3a, 0x0a, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, + 0x79, + ], + "header65", + "custom-key", + ), + ]; + + const NAME_REF_DYNAMIC_HUFFMAN: &[(u64, &[u8], &str, &str)] = &[ + ( + 0, + &[ + 0x02, 0x41, 0x4f, 0x32, 0x88, 0x25, 0xa8, 0x49, 0xe9, 0x5b, 0xa9, 0x7d, 0x7f, + ], + "header0", + "custom-key", + ), + ( + 10, + &[ + 0x0c, 0x37, 0x4f, 0x28, 0x88, 0x25, 0xa8, 0x49, 0xe9, 0x5b, 0xa9, 0x7d, 0x7f, + ], + "header10", + "custom-key", + ), + ( + 15, + &[ + 0x11, 0x32, 0x4f, 0x23, 0x88, 0x25, 0xa8, 0x49, 0xe9, 0x5b, 0xa9, 0x7d, 0x7f, + ], + "header15", + "custom-key", + ), + ( + 65, + &[ + 0x43, 0x00, 0x40, 0x88, 0x25, 0xa8, 0x49, 0xe9, 0x5b, 0xa9, 0x7d, 0x7f, + ], + "header65", + "custom-key", + ), + ]; + + const VALUE: &[u8] = &[0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, 0x79]; + + const LITERAL_LITERAL: &[u8] = &[ + 0x0, 0x42, 0x27, 0x03, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, 0x79, 0x0a, + 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, 0x79, + ]; + const LITERAL_LITERAL_HUFFMAN: &[u8] = &[ + 0x0, 0x42, 0x2f, 0x01, 0x25, 0xa8, 0x49, 0xe9, 0x5b, 0xa9, 0x7d, 0x7f, 0x88, 0x25, 0xa8, + 0x49, 0xe9, 0x5b, 0xa9, 0x7d, 0x7f, + ]; + + const LITERAL_VALUE: &str = "custom-key"; + + #[test] + fn test_encode_indexed_static() { + for (index, result, _, _) in INDEX_STATIC_TEST { + let mut encoded_h = HeaderEncoder::new(0, true, 1000); + encoded_h.encode_indexed_static(*index); + encoded_h.encode_header_block_prefix(); + assert_eq!(&&*encoded_h, result); + } + } + + #[test] + fn test_encode_indexed_dynamic() { + for (index, result, _, _) in INDEX_DYNAMIC_TEST { + let mut encoded_h = HeaderEncoder::new(66, true, 1000); + encoded_h.encode_indexed_dynamic(*index); + encoded_h.encode_header_block_prefix(); + assert_eq!(&&*encoded_h, result); + } + } + + #[test] + fn test_encode_indexed_dynamic_post() { + for (index, result, _, _) in INDEX_DYNAMIC_POST_TEST { + let mut encoded_h = HeaderEncoder::new(0, true, 1000); + encoded_h.encode_indexed_dynamic(*index); + encoded_h.encode_header_block_prefix(); + assert_eq!(&&*encoded_h, result); + } + } + + #[test] + fn test_encode_literal_with_name_ref_static() { + for (index, result, _, _) in NAME_REF_STATIC { + let mut encoded_h = HeaderEncoder::new(0, false, 1000); + encoded_h.encode_literal_with_name_ref(true, *index, VALUE); + encoded_h.encode_header_block_prefix(); + assert_eq!(&&*encoded_h, result); + } + } + + #[test] + fn test_encode_literal_with_name_ref_dynamic() { + for (index, result, _, _) in NAME_REF_DYNAMIC { + let mut encoded_h = HeaderEncoder::new(66, false, 1000); + encoded_h.encode_literal_with_name_ref(false, *index, VALUE); + encoded_h.encode_header_block_prefix(); + assert_eq!(&&*encoded_h, result); + } + } + + #[test] + fn test_encode_literal_with_name_ref_dynamic_post() { + for (index, result, _, _) in NAME_REF_DYNAMIC_POST { + let mut encoded_h = HeaderEncoder::new(0, false, 1000); + encoded_h.encode_literal_with_name_ref(false, *index, VALUE); + encoded_h.encode_header_block_prefix(); + assert_eq!(&&*encoded_h, result); + } + } + + #[test] + fn test_encode_literal_with_name_ref_dynamic_huffman() { + for (index, result, _, _) in NAME_REF_DYNAMIC_HUFFMAN { + let mut encoded_h = HeaderEncoder::new(66, true, 1000); + encoded_h.encode_literal_with_name_ref(false, *index, VALUE); + encoded_h.encode_header_block_prefix(); + assert_eq!(&&*encoded_h, result); + } + } + #[test] + fn test_encode_literal_with_literal() { + let mut encoded_h = HeaderEncoder::new(66, false, 1000); + encoded_h.encode_literal_with_name_literal(VALUE, VALUE); + encoded_h.encode_header_block_prefix(); + assert_eq!(&*encoded_h, LITERAL_LITERAL); + + let mut encoded_h = HeaderEncoder::new(66, true, 1000); + encoded_h.encode_literal_with_name_literal(VALUE, VALUE); + encoded_h.encode_header_block_prefix(); + assert_eq!(&*encoded_h, LITERAL_LITERAL_HUFFMAN); + } + + #[test] + fn decode_indexed_static() { + for (_, encoded, decoded1, decoded2) in INDEX_STATIC_TEST { + let table = HeaderTable::new(false); + let mut decoder_h = HeaderDecoder::new(encoded); + if let HeaderDecoderResult::Headers(result) = + decoder_h.decode_header_block(&table, 1000, 0).unwrap() + { + assert_eq!(result.len(), 1); + assert_eq!(result[0].name(), *decoded1); + assert_eq!(result[0].value(), *decoded2); + } else { + panic!("No headers"); + } + } + } + + fn fill_table(table: &mut HeaderTable) { + table.set_capacity(10000).unwrap(); + for i in 0..66 { + let mut v = b"header".to_vec(); + let mut num = i.to_string().as_bytes().to_vec(); + v.append(&mut num); + table.insert(&v[..], i.to_string().as_bytes()).unwrap(); + } + } + + #[test] + fn decode_indexed_dynamic() { + for (_, encoded, decoded1, decoded2) in INDEX_DYNAMIC_TEST { + let mut table = HeaderTable::new(false); + fill_table(&mut table); + let mut decoder_h = HeaderDecoder::new(encoded); + if let HeaderDecoderResult::Headers(result) = + decoder_h.decode_header_block(&table, 1000, 0).unwrap() + { + assert_eq!(result.len(), 1); + assert_eq!(result[0].name(), *decoded1); + assert_eq!(result[0].value(), *decoded2); + } else { + panic!("No headers"); + } + } + } + + #[test] + fn decode_indexed_dynamic_post() { + for (_, encoded, decoded1, decoded2) in INDEX_DYNAMIC_POST_TEST { + let mut table = HeaderTable::new(false); + fill_table(&mut table); + let mut decoder_h = HeaderDecoder::new(encoded); + if let HeaderDecoderResult::Headers(result) = + decoder_h.decode_header_block(&table, 1000, 0).unwrap() + { + assert_eq!(result.len(), 1); + assert_eq!(result[0].name(), *decoded1); + assert_eq!(result[0].value(), *decoded2); + } else { + panic!("No headers"); + } + } + } + + #[test] + fn decode_literal_with_name_ref_static() { + for (_, encoded, decoded1, decoded2) in NAME_REF_STATIC { + let table = HeaderTable::new(false); + let mut decoder_h = HeaderDecoder::new(encoded); + if let HeaderDecoderResult::Headers(result) = + decoder_h.decode_header_block(&table, 1000, 0).unwrap() + { + assert_eq!(result.len(), 1); + assert_eq!(result[0].name(), *decoded1); + assert_eq!(result[0].value(), *decoded2); + } else { + panic!("No headers"); + } + } + } + + #[test] + fn decode_literal_with_name_ref_dynamic() { + for (_, encoded, decoded1, decoded2) in NAME_REF_DYNAMIC { + let mut table = HeaderTable::new(false); + fill_table(&mut table); + let mut decoder_h = HeaderDecoder::new(encoded); + if let HeaderDecoderResult::Headers(result) = + decoder_h.decode_header_block(&table, 1000, 0).unwrap() + { + assert_eq!(result.len(), 1); + assert_eq!(result[0].name(), *decoded1); + assert_eq!(result[0].value(), *decoded2); + } else { + panic!("No headers"); + } + } + } + + #[test] + fn decode_literal_with_name_ref_dynamic_post() { + for (_, encoded, decoded1, decoded2) in NAME_REF_DYNAMIC_POST { + let mut table = HeaderTable::new(false); + fill_table(&mut table); + let mut decoder_h = HeaderDecoder::new(encoded); + if let HeaderDecoderResult::Headers(result) = + decoder_h.decode_header_block(&table, 1000, 0).unwrap() + { + assert_eq!(result.len(), 1); + assert_eq!(result[0].name(), *decoded1); + assert_eq!(result[0].value(), *decoded2); + } else { + panic!("No headers"); + } + } + } + + #[test] + fn decode_literal_with_name_ref_dynamic_huffman() { + for (_, encoded, decoded1, decoded2) in NAME_REF_DYNAMIC_HUFFMAN { + let mut table = HeaderTable::new(false); + fill_table(&mut table); + let mut decoder_h = HeaderDecoder::new(encoded); + if let HeaderDecoderResult::Headers(result) = + decoder_h.decode_header_block(&table, 1000, 0).unwrap() + { + assert_eq!(result.len(), 1); + assert_eq!(result[0].name(), *decoded1); + assert_eq!(result[0].value(), *decoded2); + } else { + panic!("No headers"); + } + } + } + + #[test] + fn decode_literal_literal() { + let mut table = HeaderTable::new(false); + fill_table(&mut table); + let mut decoder_h = HeaderDecoder::new(LITERAL_LITERAL); + if let HeaderDecoderResult::Headers(result) = + decoder_h.decode_header_block(&table, 1000, 0).unwrap() + { + assert_eq!(result.len(), 1); + assert_eq!(result[0].name(), LITERAL_VALUE); + assert_eq!(result[0].value(), LITERAL_VALUE); + } else { + panic!("No headers"); + } + + let mut decoder_h = HeaderDecoder::new(LITERAL_LITERAL_HUFFMAN); + if let HeaderDecoderResult::Headers(result) = + decoder_h.decode_header_block(&table, 1000, 0).unwrap() + { + assert_eq!(result.len(), 1); + assert_eq!(result[0].name(), LITERAL_VALUE); + assert_eq!(result[0].value(), LITERAL_VALUE); + } else { + panic!("No headers"); + } + } + + // Test that we are ignoring N-bit. + #[test] + fn decode_ignore_n_bit() { + const TEST_N_BIT: &[(&[u8], &str, &str)] = &[ + ( + &[ + 0x02, 0x41, 0x6f, 0x32, 0x0a, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, + 0x65, 0x79, + ], + "header0", + "custom-key", + ), + ( + &[ + 0x02, 0x80, 0x08, 0x0a, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, + 0x79, + ], + "header0", + "custom-key", + ), + ( + &[ + 0x0, 0x42, 0x37, 0x03, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, + 0x79, 0x0a, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, 0x79, + ], + "custom-key", + "custom-key", + ), + ( + &[ + 0x0, 0x42, 0x3f, 0x01, 0x25, 0xa8, 0x49, 0xe9, 0x5b, 0xa9, 0x7d, 0x7f, 0x88, + 0x25, 0xa8, 0x49, 0xe9, 0x5b, 0xa9, 0x7d, 0x7f, + ], + "custom-key", + "custom-key", + ), + ]; + + for (encoded, decoded1, decoded2) in TEST_N_BIT { + let mut table = HeaderTable::new(false); + fill_table(&mut table); + let mut decoder_h = HeaderDecoder::new(encoded); + if let HeaderDecoderResult::Headers(result) = + decoder_h.decode_header_block(&table, 1000, 0).unwrap() + { + assert_eq!(result.len(), 1); + assert_eq!(result[0].name(), *decoded1); + assert_eq!(result[0].value(), *decoded2); + } else { + panic!("No headers"); + } + } + } + + /// If the base calculation goes negative, that is an error. + #[test] + fn negative_base() { + let mut table = HeaderTable::new(false); + fill_table(&mut table); + let mut decoder_h = HeaderDecoder::new(&[0x0, 0x87, 0x01, 0x02, 0x03]); + assert_eq!( + Error::DecompressionFailed, + decoder_h.decode_header_block(&table, 1000, 0).unwrap_err() + ); + } + + /// If the base calculation overflows the largest value we support (`u64::MAX`), + /// then that is an error. + #[test] + fn overflow_base() { + let mut table = HeaderTable::new(false); + fill_table(&mut table); + // A small required insert count is necessary, but we can set the + // base delta to u64::MAX. + let mut decoder_h = HeaderDecoder::new(&[ + 0xff, 0x01, 0x7f, 0x80, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01, 0x02, + 0x03, + ]); + assert_eq!( + Error::DecompressionFailed, + decoder_h.decode_header_block(&table, 1000, 0).unwrap_err() + ); + } +} diff --git a/third_party/rust/neqo-qpack/src/huffman.rs b/third_party/rust/neqo-qpack/src/huffman.rs new file mode 100644 index 0000000000..31657ca826 --- /dev/null +++ b/third_party/rust/neqo-qpack/src/huffman.rs @@ -0,0 +1,256 @@ +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use crate::huffman_decode_helper::{HuffmanDecoderNode, HUFFMAN_DECODE_ROOT}; +use crate::huffman_table::HUFFMAN_TABLE; +use crate::{Error, Res}; +use std::convert::TryFrom; + +struct BitReader<'a> { + input: &'a [u8], + offset: usize, + current_bit: u8, +} + +impl<'a> BitReader<'a> { + pub fn new(input: &'a [u8]) -> Self { + BitReader { + input, + offset: 0, + current_bit: 8, + } + } + + pub fn read_bit(&mut self) -> Res<u8> { + if self.input.len() == self.offset { + return Err(Error::NeedMoreData); + } + + if self.current_bit == 0 { + self.offset += 1; + if self.offset == self.input.len() { + return Err(Error::NeedMoreData); + } + self.current_bit = 8; + } + self.current_bit -= 1; + Ok((self.input[self.offset] >> self.current_bit) & 0x01) + } + + pub fn verify_ending(&mut self, i: u8) -> Res<()> { + if (i + self.current_bit) > 7 { + return Err(Error::HuffmanDecompressionFailed); + } + + if self.input.is_empty() { + Ok(()) + } else if self.offset != self.input.len() { + Err(Error::HuffmanDecompressionFailed) + } else if self.input[self.input.len() - 1] & ((0x1 << (i + self.current_bit)) - 1) + == ((0x1 << (i + self.current_bit)) - 1) + { + self.current_bit = 0; + Ok(()) + } else { + Err(Error::HuffmanDecompressionFailed) + } + } + + pub fn has_more_data(&self) -> bool { + !self.input.is_empty() && (self.offset != self.input.len() || (self.current_bit != 0)) + } +} + +/// Decodes huffman encoded input. +/// # Errors +/// This function may return `HuffmanDecompressionFailed` if `input` is not a correct huffman-encoded array of bits. +/// # Panics +/// Never, but rust can't know that. +pub fn decode_huffman(input: &[u8]) -> Res<Vec<u8>> { + let mut reader = BitReader::new(input); + let mut output = Vec::new(); + while reader.has_more_data() { + if let Some(c) = decode_character(&mut reader)? { + if c == 256 { + return Err(Error::HuffmanDecompressionFailed); + } + output.push(u8::try_from(c).unwrap()); + } + } + + Ok(output) +} + +fn decode_character(reader: &mut BitReader) -> Res<Option<u16>> { + let mut node: &HuffmanDecoderNode = &HUFFMAN_DECODE_ROOT; + let mut i = 0; + while node.value.is_none() { + match reader.read_bit() { + Err(_) => { + reader.verify_ending(i)?; + return Ok(None); + } + Ok(b) => { + i += 1; + if let Some(next) = &node.next[usize::from(b)] { + node = next; + } else { + reader.verify_ending(i)?; + return Ok(None); + } + } + } + } + debug_assert!(node.value.is_some()); + Ok(node.value) +} + +/// # Panics +/// Never, but rust doesn't know that. +#[must_use] +pub fn encode_huffman(input: &[u8]) -> Vec<u8> { + let mut output: Vec<u8> = Vec::new(); + let mut left: u8 = 8; + let mut saved: u8 = 0; + for c in input { + let mut e = HUFFMAN_TABLE[*c as usize]; + + // Fill the previous byte + if e.len < left { + let b = u8::try_from(e.val & 0xFF).unwrap(); + saved |= b << (left - e.len); + left -= e.len; + e.len = 0; + } else { + let v: u8 = u8::try_from(e.val >> (e.len - left)).unwrap(); + saved |= v; + output.push(saved); + e.len -= left; + left = 8; + saved = 0; + } + + // Write full bytes + while e.len >= 8 { + let v: u8 = u8::try_from((e.val >> (e.len - 8)) & 0xFF).unwrap(); + output.push(v); + e.len -= 8; + } + + // Write the rest into saved. + if e.len > 0 { + saved = u8::try_from(e.val & ((1 << e.len) - 1)).unwrap() << (8 - e.len); + left = 8 - e.len; + } + } + + if left < 8 { + let v: u8 = (1 << left) - 1; + saved |= v; + output.push(saved); + } + + output +} + +#[cfg(test)] +mod tests { + use super::{decode_huffman, encode_huffman, Error}; + + struct TestElement { + pub val: &'static [u8], + pub res: &'static [u8], + } + const TEST_CASES: &[TestElement] = &[ + TestElement { + val: b"www.example.com", + res: &[ + 0xf1, 0xe3, 0xc2, 0xe5, 0xf2, 0x3a, 0x6b, 0xa0, 0xab, 0x90, 0xf4, 0xff, + ], + }, + TestElement { + val: b"no-cache", + res: &[0xa8, 0xeb, 0x10, 0x64, 0x9c, 0xbf], + }, + TestElement { + val: b"custom-key", + res: &[0x25, 0xa8, 0x49, 0xe9, 0x5b, 0xa9, 0x7d, 0x7f], + }, + TestElement { + val: b"custom-value", + res: &[0x25, 0xa8, 0x49, 0xe9, 0x5b, 0xb8, 0xe8, 0xb4, 0xbf], + }, + TestElement { + val: b"private", + res: &[0xae, 0xc3, 0x77, 0x1a, 0x4b], + }, + TestElement { + val: b"Mon, 21 Oct 2013 20:13:21 GMT", + res: &[ + 0xd0, 0x7a, 0xbe, 0x94, 0x10, 0x54, 0xd4, 0x44, 0xa8, 0x20, 0x05, 0x95, 0x04, 0x0b, + 0x81, 0x66, 0xe0, 0x82, 0xa6, 0x2d, 0x1b, 0xff, + ], + }, + TestElement { + val: b"https://www.example.com", + res: &[ + 0x9d, 0x29, 0xad, 0x17, 0x18, 0x63, 0xc7, 0x8f, 0x0b, 0x97, 0xc8, 0xe9, 0xae, 0x82, + 0xae, 0x43, 0xd3, + ], + }, + TestElement { + val: b"Mon, 21 Oct 2013 20:13:22 GMT", + res: &[ + 0xd0, 0x7a, 0xbe, 0x94, 0x10, 0x54, 0xd4, 0x44, 0xa8, 0x20, 0x05, 0x95, 0x04, 0x0b, + 0x81, 0x66, 0xe0, 0x84, 0xa6, 0x2d, 0x1b, 0xff, + ], + }, + TestElement { + val: b"gzip", + res: &[0x9b, 0xd9, 0xab], + }, + TestElement { + val: b"foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", + res: &[ + 0x94, 0xe7, 0x82, 0x1d, 0xd7, 0xf2, 0xe6, 0xc7, 0xb3, 0x35, 0xdf, 0xdf, 0xcd, 0x5b, + 0x39, 0x60, 0xd5, 0xaf, 0x27, 0x08, 0x7f, 0x36, 0x72, 0xc1, 0xab, 0x27, 0x0f, 0xb5, + 0x29, 0x1f, 0x95, 0x87, 0x31, 0x60, 0x65, 0xc0, 0x03, 0xed, 0x4e, 0xe5, 0xb1, 0x06, + 0x3d, 0x50, 0x07, + ], + }, + TestElement { + val: b"<?\\ >", + res: &[0xff, 0xf9, 0xfe, 0x7f, 0xff, 0x05, 0x3f, 0xef], + }, + ]; + + const WRONG_END: &[u8] = &[0xa8, 0xeb, 0x10, 0x64, 0x9c, 0xaf]; + + #[test] + fn test_encoder() { + for e in TEST_CASES { + let out = encode_huffman(e.val); + assert_eq!(out[..], *e.res); + } + } + + #[test] + fn test_decoder() { + for e in TEST_CASES { + let res = decode_huffman(e.res); + assert!(res.is_ok()); + assert_eq!(res.unwrap()[..], *e.val); + } + } + + #[test] + fn decoder_error_wrong_ending() { + assert_eq!( + decode_huffman(WRONG_END), + Err(Error::HuffmanDecompressionFailed) + ); + } +} diff --git a/third_party/rust/neqo-qpack/src/huffman_decode_helper.rs b/third_party/rust/neqo-qpack/src/huffman_decode_helper.rs new file mode 100644 index 0000000000..7589ebd11a --- /dev/null +++ b/third_party/rust/neqo-qpack/src/huffman_decode_helper.rs @@ -0,0 +1,55 @@ +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use crate::huffman_table::HUFFMAN_TABLE; +use lazy_static::lazy_static; +use std::convert::TryFrom; + +pub struct HuffmanDecoderNode { + pub next: [Option<Box<HuffmanDecoderNode>>; 2], + pub value: Option<u16>, +} + +lazy_static! { + pub static ref HUFFMAN_DECODE_ROOT: HuffmanDecoderNode = make_huffman_tree(0, 0); +} + +fn make_huffman_tree(prefix: u32, len: u8) -> HuffmanDecoderNode { + let mut found = false; + let mut next = [None, None]; + for (i, iter) in HUFFMAN_TABLE.iter().enumerate() { + if iter.len <= len { + continue; + } + if (iter.val >> (iter.len - len)) != prefix { + continue; + } + + found = true; + if iter.len == len + 1 { + // This is a leaf + let bit = usize::try_from(iter.val & 1).unwrap(); + next[bit] = Some(Box::new(HuffmanDecoderNode { + next: [None, None], + value: Some(u16::try_from(i).unwrap()), + })); + if next[bit ^ 1].is_some() { + return HuffmanDecoderNode { next, value: None }; + } + } + } + + if found { + if next[0].is_none() { + next[0] = Some(Box::new(make_huffman_tree(prefix << 1, len + 1))); + } + if next[1].is_none() { + next[1] = Some(Box::new(make_huffman_tree((prefix << 1) + 1, len + 1))); + } + } + + HuffmanDecoderNode { next, value: None } +} diff --git a/third_party/rust/neqo-qpack/src/huffman_table.rs b/third_party/rust/neqo-qpack/src/huffman_table.rs new file mode 100644 index 0000000000..928f6860a5 --- /dev/null +++ b/third_party/rust/neqo-qpack/src/huffman_table.rs @@ -0,0 +1,280 @@ +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +#[derive(Debug, Copy, Clone)] +pub struct HuffmanTableEntry { + pub len: u8, + pub val: u32, +} + +macro_rules! huffman_table { + [$($v:expr => $l:expr),+ $(,)?] => { + &[ + $(HuffmanTableEntry { len: $l, val: $v }),+ + ] + }; +} + +// Table contains the raw HPACK Huffman table +pub const HUFFMAN_TABLE: &[HuffmanTableEntry] = huffman_table![ + 0x1ff8 => 13, + 0x007f_ffd8 => 23, + 0x0fff_ffe2 => 28, + 0x0fff_ffe3 => 28, + 0x0fff_ffe4 => 28, + 0x0fff_ffe5 => 28, + 0x0fff_ffe6 => 28, + 0x0fff_ffe7 => 28, + 0x0fff_ffe8 => 28, + 0x00ff_ffea => 24, + 0x3fff_fffc => 30, + 0x0fff_ffe9 => 28, + 0x0fff_ffea => 28, + 0x3fff_fffd => 30, + 0x0fff_ffeb => 28, + 0x0fff_ffec => 28, + 0x0fff_ffed => 28, + 0x0fff_ffee => 28, + 0x0fff_ffef => 28, + 0x0fff_fff0 => 28, + 0x0fff_fff1 => 28, + 0x0fff_fff2 => 28, + 0x3fff_fffe => 30, + 0x0fff_fff3 => 28, + 0x0fff_fff4 => 28, + 0x0fff_fff5 => 28, + 0x0fff_fff6 => 28, + 0x0fff_fff7 => 28, + 0x0fff_fff8 => 28, + 0x0fff_fff9 => 28, + 0x0fff_fffa => 28, + 0x0fff_fffb => 28, + 0x14 => 6, // ' ' + 0x3f8 => 10, // '!' + 0x3f9 => 10, // '"' + 0xffa => 12, // '#' + 0x1ff9 => 13, // '$' + 0x15 => 6, // '%' + 0xf8 => 8, // '&' + 0x7fa => 11, // ''' + 0x3fa => 10, // '(' + 0x3fb => 10, // ')' + 0xf9 => 8, // '*' + 0x7fb => 11, // '+' + 0xfa => 8, // ',' + 0x16 => 6, // '-' + 0x17 => 6, // '.' + 0x18 => 6, // '/' + 0x0 => 5, // '0' + 0x1 => 5, // '1' + 0x2 => 5, // '2' + 0x19 => 6, // '3' + 0x1a => 6, // '4' + 0x1b => 6, // '5' + 0x1c => 6, // '6' + 0x1d => 6, // '7' + 0x1e => 6, // '8' + 0x1f => 6, // '9' + 0x5c => 7, // ':' + 0xfb => 8, // ';' + 0x7ffc => 15, // '<' + 0x20 => 6, // '=' + 0xffb => 12, // '>' + 0x3fc => 10, // '?' + 0x1ffa => 13, // '@' + 0x21 => 6, // 'A' + 0x5d => 7, // 'B' + 0x5e => 7, // 'C' + 0x5f => 7, // 'D' + 0x60 => 7, // 'E' + 0x61 => 7, // 'F' + 0x62 => 7, // 'G' + 0x63 => 7, // 'H' + 0x64 => 7, // 'I' + 0x65 => 7, // 'J' + 0x66 => 7, // 'K' + 0x67 => 7, // 'L' + 0x68 => 7, // 'M' + 0x69 => 7, // 'N' + 0x6a => 7, // 'O' + 0x6b => 7, // 'P' + 0x6c => 7, // 'Q' + 0x6d => 7, // 'R' + 0x6e => 7, // 'S' + 0x6f => 7, // 'T' + 0x70 => 7, // 'U' + 0x71 => 7, // 'V' + 0x72 => 7, // 'W' + 0xfc => 8, // 'X' + 0x73 => 7, // 'Y' + 0xfd => 8, // 'Z' + 0x1ffb => 13, // '[' + 0x0007_fff0 => 19, // '\' + 0x1ffc => 13, // ']' + 0x3ffc => 14, // '^' + 0x22 => 6, // '_' + 0x7ffd => 15, // '`' + 0x3 => 5, // 'a' + 0x23 => 6, // 'b' + 0x4 => 5, // 'c' + 0x24 => 6, // 'd' + 0x5 => 5, // 'e' + 0x25 => 6, // 'f' + 0x26 => 6, // 'g' + 0x27 => 6, // 'h' + 0x6 => 5, // 'i' + 0x74 => 7, // 'j' + 0x75 => 7, // 'k' + 0x28 => 6, // 'l' + 0x29 => 6, // 'm' + 0x2a => 6, // 'n' + 0x7 => 5, // 'o' + 0x2b => 6, // 'p' + 0x76 => 7, // 'q' + 0x2c => 6, // 'r' + 0x8 => 5, // 's' + 0x9 => 5, // 't' + 0x2d => 6, // 'u' + 0x77 => 7, // 'v' + 0x78 => 7, // 'w' + 0x79 => 7, // 'x' + 0x7a => 7, // 'y' + 0x7b => 7, // 'z' + 0x7ffe => 15, // '{' + 0x7fc => 11, // '|' + 0x3ffd => 14, // '}' + 0x1ffd => 13, // '~' + 0x0fff_fffc => 28, + 0x000f_ffe6 => 20, + 0x003f_ffd2 => 22, + 0x000f_ffe7 => 20, + 0x000f_ffe8 => 20, + 0x003f_ffd3 => 22, + 0x003f_ffd4 => 22, + 0x003f_ffd5 => 22, + 0x007f_ffd9 => 23, + 0x003f_ffd6 => 22, + 0x007f_ffda => 23, + 0x007f_ffdb => 23, + 0x007f_ffdc => 23, + 0x007f_ffdd => 23, + 0x007f_ffde => 23, + 0x00ff_ffeb => 24, + 0x007f_ffdf => 23, + 0x00ff_ffec => 24, + 0x00ff_ffed => 24, + 0x003f_ffd7 => 22, + 0x007f_ffe0 => 23, + 0x00ff_ffee => 24, + 0x007f_ffe1 => 23, + 0x007f_ffe2 => 23, + 0x007f_ffe3 => 23, + 0x007f_ffe4 => 23, + 0x001f_ffdc => 21, + 0x003f_ffd8 => 22, + 0x007f_ffe5 => 23, + 0x003f_ffd9 => 22, + 0x007f_ffe6 => 23, + 0x007f_ffe7 => 23, + 0x00ff_ffef => 24, + 0x003f_ffda => 22, + 0x001f_ffdd => 21, + 0x000f_ffe9 => 20, + 0x003f_ffdb => 22, + 0x003f_ffdc => 22, + 0x007f_ffe8 => 23, + 0x007f_ffe9 => 23, + 0x001f_ffde => 21, + 0x007f_ffea => 23, + 0x003f_ffdd => 22, + 0x003f_ffde => 22, + 0x00ff_fff0 => 24, + 0x001f_ffdf => 21, + 0x003f_ffdf => 22, + 0x007f_ffeb => 23, + 0x007f_ffec => 23, + 0x001f_ffe0 => 21, + 0x001f_ffe1 => 21, + 0x003f_ffe0 => 22, + 0x001f_ffe2 => 21, + 0x007f_ffed => 23, + 0x003f_ffe1 => 22, + 0x007f_ffee => 23, + 0x007f_ffef => 23, + 0x000f_ffea => 20, + 0x003f_ffe2 => 22, + 0x003f_ffe3 => 22, + 0x003f_ffe4 => 22, + 0x007f_fff0 => 23, + 0x003f_ffe5 => 22, + 0x003f_ffe6 => 22, + 0x007f_fff1 => 23, + 0x03ff_ffe0 => 26, + 0x03ff_ffe1 => 26, + 0x000f_ffeb => 20, + 0x0007_fff1 => 19, + 0x003f_ffe7 => 22, + 0x007f_fff2 => 23, + 0x003f_ffe8 => 22, + 0x01ff_ffec => 25, + 0x03ff_ffe2 => 26, + 0x03ff_ffe3 => 26, + 0x03ff_ffe4 => 26, + 0x07ff_ffde => 27, + 0x07ff_ffdf => 27, + 0x03ff_ffe5 => 26, + 0x00ff_fff1 => 24, + 0x01ff_ffed => 25, + 0x0007_fff2 => 19, + 0x001f_ffe3 => 21, + 0x03ff_ffe6 => 26, + 0x07ff_ffe0 => 27, + 0x07ff_ffe1 => 27, + 0x03ff_ffe7 => 26, + 0x07ff_ffe2 => 27, + 0x00ff_fff2 => 24, + 0x001f_ffe4 => 21, + 0x001f_ffe5 => 21, + 0x03ff_ffe8 => 26, + 0x03ff_ffe9 => 26, + 0x0fff_fffd => 28, + 0x07ff_ffe3 => 27, + 0x07ff_ffe4 => 27, + 0x07ff_ffe5 => 27, + 0x000f_ffec => 20, + 0x00ff_fff3 => 24, + 0x000f_ffed => 20, + 0x001f_ffe6 => 21, + 0x003f_ffe9 => 22, + 0x001f_ffe7 => 21, + 0x001f_ffe8 => 21, + 0x007f_fff3 => 23, + 0x003f_ffea => 22, + 0x003f_ffeb => 22, + 0x01ff_ffee => 25, + 0x01ff_ffef => 25, + 0x00ff_fff4 => 24, + 0x00ff_fff5 => 24, + 0x03ff_ffea => 26, + 0x007f_fff4 => 23, + 0x03ff_ffeb => 26, + 0x07ff_ffe6 => 27, + 0x03ff_ffec => 26, + 0x03ff_ffed => 26, + 0x07ff_ffe7 => 27, + 0x07ff_ffe8 => 27, + 0x07ff_ffe9 => 27, + 0x07ff_ffea => 27, + 0x07ff_ffeb => 27, + 0x0fff_fffe => 28, + 0x07ff_ffec => 27, + 0x07ff_ffed => 27, + 0x07ff_ffee => 27, + 0x07ff_ffef => 27, + 0x07ff_fff0 => 27, + 0x03ff_ffee => 26, + 0x3fff_ffff => 30, +]; diff --git a/third_party/rust/neqo-qpack/src/lib.rs b/third_party/rust/neqo-qpack/src/lib.rs new file mode 100644 index 0000000000..4dc424d836 --- /dev/null +++ b/third_party/rust/neqo-qpack/src/lib.rs @@ -0,0 +1,118 @@ +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +#![cfg_attr(feature = "deny-warnings", deny(warnings))] +#![warn(clippy::pedantic)] +// This is because of Encoder and Decoder structs. TODO: think about a better namings for crate and structs. +#![allow(clippy::module_name_repetitions)] + +pub mod decoder; +mod decoder_instructions; +pub mod encoder; +mod encoder_instructions; +mod header_block; +pub mod huffman; +mod huffman_decode_helper; +pub mod huffman_table; +mod prefix; +mod qlog; +mod qpack_send_buf; +pub mod reader; +mod static_table; +mod stats; +mod table; + +pub use decoder::QPackDecoder; +pub use encoder::QPackEncoder; +pub use stats::Stats; + +type Res<T> = Result<T, Error>; + +#[derive(Debug, PartialEq, PartialOrd, Ord, Eq, Clone, Copy)] +pub struct QpackSettings { + pub max_table_size_decoder: u64, + pub max_table_size_encoder: u64, + pub max_blocked_streams: u16, +} + +#[derive(Clone, Debug, PartialEq, Eq)] +pub enum Error { + DecompressionFailed, + EncoderStream, + DecoderStream, + ClosedCriticalStream, + InternalError(u16), + + // These are internal errors, they will be transformed into one of the above. + NeedMoreData, // Return when an input stream does not have more data that a decoder needs.(It does not mean that a stream is closed.) + HeaderLookup, + HuffmanDecompressionFailed, + ToStringFailed, + ChangeCapacity, + DynamicTableFull, + IncrementAck, + IntegerOverflow, + WrongStreamCount, + Decoding, // Decoding internal error that is not one of the above. + EncoderStreamBlocked, + Internal, + + TransportError(neqo_transport::Error), + QlogError, +} + +impl Error { + #[must_use] + pub fn code(&self) -> neqo_transport::AppError { + match self { + Self::DecompressionFailed => 0x200, + Self::EncoderStream => 0x201, + Self::DecoderStream => 0x202, + Self::ClosedCriticalStream => 0x104, + // These are all internal errors. + _ => 3, + } + } + + /// # Errors + /// Any error is mapped to the indicated type. + fn map_error<R>(r: Result<R, Self>, err: Self) -> Result<R, Self> { + r.map_err(|e| { + if matches!(e, Self::ClosedCriticalStream) { + e + } else { + err + } + }) + } +} + +impl ::std::error::Error for Error { + fn source(&self) -> Option<&(dyn ::std::error::Error + 'static)> { + match self { + Self::TransportError(e) => Some(e), + _ => None, + } + } +} + +impl ::std::fmt::Display for Error { + fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result { + write!(f, "QPACK error: {:?}", self) + } +} + +impl From<neqo_transport::Error> for Error { + fn from(err: neqo_transport::Error) -> Self { + Self::TransportError(err) + } +} + +impl From<::qlog::Error> for Error { + fn from(_err: ::qlog::Error) -> Self { + Self::QlogError + } +} diff --git a/third_party/rust/neqo-qpack/src/prefix.rs b/third_party/rust/neqo-qpack/src/prefix.rs new file mode 100644 index 0000000000..ee0826850d --- /dev/null +++ b/third_party/rust/neqo-qpack/src/prefix.rs @@ -0,0 +1,139 @@ +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +#[derive(Copy, Clone, Debug)] +pub struct Prefix { + prefix: u8, + len: u8, + mask: u8, +} + +impl Prefix { + pub fn new(prefix: u8, len: u8) -> Self { + // len should never be larger than 7. + // Most of Prefixes are instantiated as consts bellow. The only place where this construcrtor is used + // is in tests and when literals are encoded and the Huffman bit is added to one of the consts bellow. + // create_prefix guaranty that all const have len < 7 so we can safely assert that len is <=7. + assert!(len <= 7); + assert!((len == 0) || (prefix & ((1 << (8 - len)) - 1) == 0)); + Self { + prefix, + len, + mask: if len == 0 { + 0xFF + } else { + ((1 << len) - 1) << (8 - len) + }, + } + } + + pub fn len(self) -> u8 { + self.len + } + + pub fn prefix(self) -> u8 { + self.prefix + } + + pub fn cmp_prefix(self, b: u8) -> bool { + (b & self.mask) == self.prefix + } +} + +#[macro_export] +macro_rules! create_prefix { + ($n:ident) => { + pub const $n: Prefix = Prefix { + prefix: 0x0, + len: 0, + mask: 0xFF, + }; + }; + ($n:ident, $v:expr, $l:expr) => { + static_assertions::const_assert!($l < 7); + static_assertions::const_assert!($v & ((1 << (8 - $l)) - 1) == 0); + pub const $n: Prefix = Prefix { + prefix: $v, + len: $l, + mask: ((1 << $l) - 1) << (8 - $l), + }; + }; + ($n:ident, $v:expr, $l:expr, $m:expr) => { + static_assertions::const_assert!($l < 7); + static_assertions::const_assert!($v & ((1 << (8 - $l)) - 1) == 0); + static_assertions::const_assert!((((1 << $l) - 1) << (8 - $l)) >= $m); + pub const $n: Prefix = Prefix { + prefix: $v, + len: $l, + mask: $m, + }; + }; +} + +create_prefix!(NO_PREFIX); +//===================================================================== +// Decoder instructions prefix +//===================================================================== + +// | 1 | Stream ID (7+) | +create_prefix!(DECODER_HEADER_ACK, 0x80, 1); + +// | 0 | 1 | Stream ID (6+) | +create_prefix!(DECODER_STREAM_CANCELLATION, 0x40, 2); + +// | 0 | 0 | Increment (6+) | +create_prefix!(DECODER_INSERT_COUNT_INCREMENT, 0x00, 2); + +//===================================================================== +// Encoder instructions prefix +//===================================================================== + +// | 0 | 0 | 1 | Capacity (5+) | +create_prefix!(ENCODER_CAPACITY, 0x20, 3); + +// | 1 | T | Name Index (6+) | +// T == 1 static +// T == 0 dynamic +create_prefix!(ENCODER_INSERT_WITH_NAME_REF_STATIC, 0xC0, 2); +create_prefix!(ENCODER_INSERT_WITH_NAME_REF_DYNAMIC, 0x80, 2); + +// | 0 | 1 | H | Name Length (5+) | +// H is not relevant for decoding this prefix, therefore the mask is 1100 0000 = 0xC0 +create_prefix!(ENCODER_INSERT_WITH_NAME_LITERAL, 0x40, 2); + +// | 0 | 0 | 0 | Index (5+) | +create_prefix!(ENCODER_DUPLICATE, 0x00, 3); + +//===================================================================== +//Header block encoding prefixes +//===================================================================== + +create_prefix!(BASE_PREFIX_POSITIVE, 0x00, 1); +create_prefix!(BASE_PREFIX_NEGATIVE, 0x80, 1); + +// | 1 | T | index(6+) | +// T == 1 static +// T == 0 dynamic +create_prefix!(HEADER_FIELD_INDEX_STATIC, 0xC0, 2); +create_prefix!(HEADER_FIELD_INDEX_DYNAMIC, 0x80, 2); + +// | 0 | 0 | 0 | 1 | Index(4+) | +create_prefix!(HEADER_FIELD_INDEX_DYNAMIC_POST, 0x10, 4); + +// | 0 | 1 | N | T | Index(4+) | +// T == 1 static +// T == 0 dynamic +// N is ignored, therefore the mask is 1101 0000 = 0xD0 +create_prefix!(HEADER_FIELD_LITERAL_NAME_REF_STATIC, 0x50, 4, 0xD0); +create_prefix!(HEADER_FIELD_LITERAL_NAME_REF_DYNAMIC, 0x40, 4, 0xD0); + +// | 0 | 0 | 0 | 0 | N | Index(3+) | +// N is ignored, therefore the mask is 1111 0000 = 0xF0 +create_prefix!(HEADER_FIELD_LITERAL_NAME_REF_DYNAMIC_POST, 0x00, 5, 0xF0); + +// | 0 | 0 | 1 | N | H | Index(3+) | +// N is ignored and H is not relevant for decoding this prefix, therefore the mask is 1110 0000 = 0xE0 +create_prefix!(HEADER_FIELD_LITERAL_NAME_LITERAL, 0x20, 4, 0xE0); diff --git a/third_party/rust/neqo-qpack/src/qlog.rs b/third_party/rust/neqo-qpack/src/qlog.rs new file mode 100644 index 0000000000..11f9dbc0b3 --- /dev/null +++ b/third_party/rust/neqo-qpack/src/qlog.rs @@ -0,0 +1,28 @@ +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +// Functions that handle capturing QLOG traces. + +use neqo_common::hex; +use neqo_common::qlog::NeqoQlog; +use qlog::{event::Event, QPackInstruction, QpackInstructionTypeName}; + +pub fn qpack_read_insert_count_increment_instruction( + qlog: &mut NeqoQlog, + increment: u64, + data: &[u8], +) { + qlog.add_event(|| { + Some(Event::qpack_instruction_received( + QPackInstruction::InsertCountIncrementInstruction { + instruction_type: QpackInstructionTypeName::InsertCountIncrementInstruction, + increment, + }, + Some(8.to_string()), + Some(hex(data)), + )) + }); +} diff --git a/third_party/rust/neqo-qpack/src/qpack_send_buf.rs b/third_party/rust/neqo-qpack/src/qpack_send_buf.rs new file mode 100644 index 0000000000..4fbdbf12bd --- /dev/null +++ b/third_party/rust/neqo-qpack/src/qpack_send_buf.rs @@ -0,0 +1,161 @@ +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use crate::huffman::encode_huffman; +use crate::prefix::Prefix; +use neqo_common::Encoder; +use std::convert::TryFrom; +use std::ops::Deref; + +#[derive(Default, Debug, PartialEq)] +pub(crate) struct QpackData { + buf: Vec<u8>, +} + +impl QpackData { + pub fn len(&self) -> usize { + self.buf.len() + } + + fn write_byte(&mut self, b: u8) { + self.buf.push(b); + } + + pub fn encode_varint(&mut self, i: u64) { + let mut enc = Encoder::default(); + enc.encode_varint(i); + self.buf.append(&mut enc.into()); + } + + pub(crate) fn encode_prefixed_encoded_int(&mut self, prefix: Prefix, mut val: u64) -> usize { + let first_byte_max: u8 = if prefix.len() == 0 { + 0xff + } else { + (1 << (8 - prefix.len())) - 1 + }; + + if val < u64::from(first_byte_max) { + let v = u8::try_from(val).unwrap(); + self.write_byte((prefix.prefix() & !first_byte_max) | v); + return 1; + } + + self.write_byte(prefix.prefix() | first_byte_max); + val -= u64::from(first_byte_max); + + let mut written = 1; + let mut done = false; + while !done { + let mut b = u8::try_from(val & 0x7f).unwrap(); + val >>= 7; + if val > 0 { + b |= 0x80; + } else { + done = true; + } + + self.write_byte(b); + written += 1; + } + written + } + + pub fn encode_literal(&mut self, use_huffman: bool, prefix: Prefix, value: &[u8]) { + let real_prefix = Prefix::new( + if use_huffman { + prefix.prefix() | (0x80 >> prefix.len()) + } else { + prefix.prefix() + }, + prefix.len() + 1, + ); + + if use_huffman { + let encoded = encode_huffman(value); + self.encode_prefixed_encoded_int(real_prefix, u64::try_from(encoded.len()).unwrap()); + self.write_bytes(&encoded); + } else { + self.encode_prefixed_encoded_int(real_prefix, u64::try_from(value.len()).unwrap()); + self.write_bytes(value); + } + } + + pub fn write_bytes(&mut self, buf: &[u8]) { + self.buf.extend_from_slice(buf); + } + + pub fn read(&mut self, r: usize) { + assert!( + r <= self.buf.len(), + "want to set more bytes read than remain in the buffer." + ); + self.buf = self.buf.split_off(r); + } +} + +impl Deref for QpackData { + type Target = [u8]; + fn deref(&self) -> &Self::Target { + &self.buf + } +} + +#[cfg(test)] +mod tests { + use super::{Prefix, QpackData}; + + #[test] + fn test_encode_prefixed_encoded_int_1() { + let mut d = QpackData::default(); + d.encode_prefixed_encoded_int(Prefix::new(0xC0, 2), 5); + assert_eq!(d[..], [0xc5]); + } + + #[test] + fn test_encode_prefixed_encoded_int_2() { + let mut d = QpackData::default(); + d.encode_prefixed_encoded_int(Prefix::new(0xC0, 2), 65); + assert_eq!(d[..], [0xff, 0x02]); + } + + #[test] + fn test_encode_prefixed_encoded_int_3() { + let mut d = QpackData::default(); + d.encode_prefixed_encoded_int(Prefix::new(0xC0, 2), 100_000); + assert_eq!(d[..], [0xff, 0xe1, 0x8c, 0x06]); + } + + #[test] + fn max_int() { + let mut d = QpackData::default(); + d.encode_prefixed_encoded_int(Prefix::new(0x80, 1), u64::MAX); + assert_eq!( + d[..], + [0xff, 0x80, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01] + ); + } + + const VALUE: &[u8] = b"custom-key"; + + const LITERAL: &[u8] = &[ + 0xca, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, 0x79, + ]; + const LITERAL_HUFFMAN: &[u8] = &[0xe8, 0x25, 0xa8, 0x49, 0xe9, 0x5b, 0xa9, 0x7d, 0x7f]; + + #[test] + fn test_encode_literal() { + let mut d = QpackData::default(); + d.encode_literal(false, Prefix::new(0xC0, 2), VALUE); + assert_eq!(&&d[..], &LITERAL); + } + + #[test] + fn test_encode_literal_huffman() { + let mut d = QpackData::default(); + d.encode_literal(true, Prefix::new(0xC0, 2), VALUE); + assert_eq!(&&d[..], &LITERAL_HUFFMAN); + } +} diff --git a/third_party/rust/neqo-qpack/src/reader.rs b/third_party/rust/neqo-qpack/src/reader.rs new file mode 100644 index 0000000000..386a25ffc1 --- /dev/null +++ b/third_party/rust/neqo-qpack/src/reader.rs @@ -0,0 +1,586 @@ +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use crate::huffman::decode_huffman; +use crate::prefix::Prefix; +use crate::{Error, Res}; +use neqo_common::{qdebug, qerror}; +use neqo_transport::{Connection, StreamId}; +use std::convert::TryInto; +use std::mem; +use std::str; + +pub trait ReadByte { + /// # Errors + /// Return error occurred while reading a byte. + /// The exact error depends on trait implementation. + fn read_byte(&mut self) -> Res<u8>; +} + +pub trait Reader { + /// # Errors + /// Return error occurred while reading date into a buffer. + /// The exact error depends on trait implementation. + fn read(&mut self, buf: &mut [u8]) -> Res<usize>; +} + +pub(crate) struct ReceiverConnWrapper<'a> { + conn: &'a mut Connection, + stream_id: StreamId, +} + +impl<'a> ReadByte for ReceiverConnWrapper<'a> { + fn read_byte(&mut self) -> Res<u8> { + let mut b = [0]; + match self.conn.stream_recv(self.stream_id, &mut b)? { + (_, true) => Err(Error::ClosedCriticalStream), + (0, false) => Err(Error::NeedMoreData), + _ => Ok(b[0]), + } + } +} + +impl<'a> Reader for ReceiverConnWrapper<'a> { + fn read(&mut self, buf: &mut [u8]) -> Res<usize> { + match self.conn.stream_recv(self.stream_id, buf)? { + (_, true) => Err(Error::ClosedCriticalStream), + (amount, false) => Ok(amount), + } + } +} + +impl<'a> ReceiverConnWrapper<'a> { + pub fn new(conn: &'a mut Connection, stream_id: StreamId) -> Self { + Self { conn, stream_id } + } +} + +/// This is only used by header decoder therefore all errors are `DecompressionFailed`. +/// A header block is read entirely before decoding it, therefore if there is not enough +/// data in the buffer an error `DecompressionFailed` will be return. +pub(crate) struct ReceiverBufferWrapper<'a> { + buf: &'a [u8], + offset: usize, +} + +impl<'a> ReadByte for ReceiverBufferWrapper<'a> { + fn read_byte(&mut self) -> Res<u8> { + if self.offset == self.buf.len() { + Err(Error::DecompressionFailed) + } else { + let b = self.buf[self.offset]; + self.offset += 1; + Ok(b) + } + } +} + +impl<'a> ReceiverBufferWrapper<'a> { + pub fn new(buf: &'a [u8]) -> Self { + Self { buf, offset: 0 } + } + + pub fn peek(&self) -> Res<u8> { + if self.offset == self.buf.len() { + Err(Error::DecompressionFailed) + } else { + Ok(self.buf[self.offset]) + } + } + + pub fn done(&self) -> bool { + self.offset == self.buf.len() + } + + /// The function decodes varint with a prefixed, i.e. ignores `prefix_len` bits of the first + /// byte. + /// `ReceiverBufferWrapper` is only used for decoding header blocks. The header blocks are read + /// entirely before a decoding starts, therefore any incomplete varint because of reaching the + /// end of a buffer will be treated as the `DecompressionFailed` error. + pub fn read_prefixed_int(&mut self, prefix_len: u8) -> Res<u64> { + debug_assert!(prefix_len < 8); + + let first_byte = self.read_byte()?; + let mut reader = IntReader::new(first_byte, prefix_len); + reader.read(self) + } + + /// Do not use `LiteralReader` here to avoid copying data. + /// The function decoded a literal with a prefix: + /// 1) ignores `prefix_len` bits of the first byte, + /// 2) reads "huffman bit" + /// 3) decode varint that is the length of a literal + /// 4) reads the literal + /// 5) performs huffman decoding if needed. + /// + /// `ReceiverBufferWrapper` is only used for decoding header blocks. The header blocks are read + /// entirely before a decoding starts, therefore any incomplete varint or literal because of + /// reaching the end of a buffer will be treated as the `DecompressionFailed` error. + pub fn read_literal_from_buffer(&mut self, prefix_len: u8) -> Res<String> { + debug_assert!(prefix_len < 7); + + let first_byte = self.read_byte()?; + let use_huffman = (first_byte & (0x80 >> prefix_len)) != 0; + let mut int_reader = IntReader::new(first_byte, prefix_len + 1); + let length: usize = int_reader + .read(self)? + .try_into() + .or(Err(Error::DecompressionFailed))?; + if use_huffman { + Ok(to_string(&decode_huffman(self.slice(length)?)?)?) + } else { + Ok(to_string(self.slice(length)?)?) + } + } + + fn slice(&mut self, len: usize) -> Res<&[u8]> { + if self.offset + len > self.buf.len() { + Err(Error::DecompressionFailed) + } else { + let start = self.offset; + self.offset += len; + Ok(&self.buf[start..self.offset]) + } + } +} + +/// This is varint reader that can take into account a prefix. +#[derive(Debug)] +pub struct IntReader { + value: u64, + cnt: u8, + done: bool, +} + +impl IntReader { + /// `IntReader` is created by suppling the first byte anf prefix length. + /// A varint may take only one byte, In that case already the first by has set state to done. + /// # Panics + /// When `prefix_len` is 8 or larger. + #[must_use] + pub fn new(first_byte: u8, prefix_len: u8) -> Self { + debug_assert!(prefix_len < 8, "prefix cannot larger than 7."); + let mask = if prefix_len == 0 { + 0xff + } else { + (1 << (8 - prefix_len)) - 1 + }; + let value = u64::from(first_byte & mask); + + Self { + value, + cnt: 0, + done: value < u64::from(mask), + } + } + + /// # Panics + /// Never, but rust doesn't know that. + #[must_use] + pub fn make(first_byte: u8, prefixes: &[Prefix]) -> Self { + for prefix in prefixes { + if prefix.cmp_prefix(first_byte) { + return Self::new(first_byte, prefix.len()); + } + } + unreachable!(); + } + + /// This function reads bytes until the varint is decoded or until stream/buffer does not + /// have any more date. + /// # Errors + /// Possible errors are: + /// 1) `NeedMoreData` if the reader needs more data, + /// 2) `IntegerOverflow`, + /// 3) Any `ReadByte`'s error + pub fn read<R: ReadByte>(&mut self, s: &mut R) -> Res<u64> { + let mut b: u8; + while !self.done { + b = s.read_byte()?; + + if (self.cnt == 63) && (b > 1 || (b == 1 && ((self.value >> 63) == 1))) { + qerror!("Error decoding prefixed encoded int - IntegerOverflow"); + return Err(Error::IntegerOverflow); + } + self.value += u64::from(b & 0x7f) << self.cnt; + if (b & 0x80) == 0 { + self.done = true; + } + self.cnt += 7; + if self.cnt >= 64 { + self.done = true; + } + } + Ok(self.value) + } +} + +#[derive(Debug)] +enum LiteralReaderState { + ReadHuffman, + ReadLength { reader: IntReader }, + ReadLiteral { offset: usize }, + Done, +} + +impl Default for LiteralReaderState { + fn default() -> Self { + Self::ReadHuffman + } +} + +/// This is decoder of a literal with a prefix: +/// 1) ignores `prefix_len` bits of the first byte, +/// 2) reads "huffman bit" +/// 3) decode varint that is the length of a literal +/// 4) reads the literal +/// 5) performs huffman decoding if needed. +#[derive(Debug, Default)] +pub struct LiteralReader { + state: LiteralReaderState, + literal: Vec<u8>, + use_huffman: bool, +} + +impl LiteralReader { + /// Creates `LiteralReader` with the first byte. This constructor is always used + /// when a litreral has a prefix. + /// For literals without a prefix please use the default constructor. + /// # Panics + /// If `prefix_len` is 8 or more. + #[must_use] + pub fn new_with_first_byte(first_byte: u8, prefix_len: u8) -> Self { + assert!(prefix_len < 8); + Self { + state: LiteralReaderState::ReadLength { + reader: IntReader::new(first_byte, prefix_len + 1), + }, + literal: Vec::new(), + use_huffman: (first_byte & (0x80 >> prefix_len)) != 0, + } + } + + /// This function reads bytes until the literal is decoded or until stream/buffer does not + /// have any more date ready. + /// # Errors + /// Possible errors are: + /// 1) `NeedMoreData` if the reader needs more data, + /// 2) `IntegerOverflow` + /// 3) Any `ReadByte`'s error + /// It returns value if reading the literal is done or None if it needs more data. + /// # Panics + /// When this object is complete. + pub fn read<T: ReadByte + Reader>(&mut self, s: &mut T) -> Res<Vec<u8>> { + loop { + qdebug!("state = {:?}", self.state); + match &mut self.state { + LiteralReaderState::ReadHuffman => { + let b = s.read_byte()?; + + self.use_huffman = (b & 0x80) != 0; + self.state = LiteralReaderState::ReadLength { + reader: IntReader::new(b, 1), + }; + } + LiteralReaderState::ReadLength { reader } => { + let v = reader.read(s)?; + self.literal + .resize(v.try_into().or(Err(Error::Decoding))?, 0x0); + self.state = LiteralReaderState::ReadLiteral { offset: 0 }; + } + LiteralReaderState::ReadLiteral { offset } => { + let amount = s.read(&mut self.literal[*offset..])?; + *offset += amount; + if *offset == self.literal.len() { + self.state = LiteralReaderState::Done; + if self.use_huffman { + break Ok(decode_huffman(&self.literal)?); + } + break Ok(mem::take(&mut self.literal)); + } + break Err(Error::NeedMoreData); + } + LiteralReaderState::Done => { + panic!("Should not call read() in this state."); + } + } + } + } +} + +/// This is a helper function used only by `ReceiverBufferWrapper`, therefore it returns +/// `DecompressionFailed` if any error happens. +/// # Errors +/// If an parsing error occurred, the function returns `ToStringFailed`. +pub fn to_string(v: &[u8]) -> Res<String> { + match str::from_utf8(v) { + Ok(s) => Ok(s.to_string()), + Err(_) => Err(Error::ToStringFailed), + } +} + +#[cfg(test)] +pub(crate) mod test_receiver { + + use super::{Error, ReadByte, Reader, Res}; + use std::collections::VecDeque; + + #[derive(Default)] + pub struct TestReceiver { + buf: VecDeque<u8>, + } + + impl ReadByte for TestReceiver { + fn read_byte(&mut self) -> Res<u8> { + self.buf.pop_back().ok_or(Error::NeedMoreData) + } + } + + impl Reader for TestReceiver { + fn read(&mut self, buf: &mut [u8]) -> Res<usize> { + let len = if buf.len() > self.buf.len() { + self.buf.len() + } else { + buf.len() + }; + for item in buf.iter_mut().take(len) { + *item = self.buf.pop_back().ok_or(Error::NeedMoreData)?; + } + Ok(len) + } + } + + impl TestReceiver { + pub fn write(&mut self, buf: &[u8]) { + for b in buf { + self.buf.push_front(*b); + } + } + } +} + +#[cfg(test)] +mod tests { + + use super::{ + str, test_receiver, to_string, Error, IntReader, LiteralReader, ReadByte, + ReceiverBufferWrapper, Res, + }; + use test_receiver::TestReceiver; + + const TEST_CASES_NUMBERS: [(&[u8], u8, u64); 7] = [ + (&[0xEA], 3, 10), + (&[0x0A], 3, 10), + (&[0x8A], 3, 10), + (&[0xFF, 0x9A, 0x0A], 3, 1337), + (&[0x1F, 0x9A, 0x0A], 3, 1337), + (&[0x9F, 0x9A, 0x0A], 3, 1337), + (&[0x2A], 0, 42), + ]; + + #[test] + fn read_prefixed_int() { + for (buf, prefix_len, value) in &TEST_CASES_NUMBERS { + let mut reader = IntReader::new(buf[0], *prefix_len); + let mut test_receiver: TestReceiver = TestReceiver::default(); + test_receiver.write(&buf[1..]); + assert_eq!(reader.read(&mut test_receiver), Ok(*value)); + } + } + + #[test] + fn read_prefixed_int_with_more_data_in_buffer() { + for (buf, prefix_len, value) in &TEST_CASES_NUMBERS { + let mut reader = IntReader::new(buf[0], *prefix_len); + let mut test_receiver: TestReceiver = TestReceiver::default(); + test_receiver.write(&buf[1..]); + // add some more data + test_receiver.write(&[0x0, 0x0, 0x0]); + assert_eq!(reader.read(&mut test_receiver), Ok(*value)); + } + } + + #[test] + fn read_prefixed_int_slow_writer() { + let (buf, prefix_len, value) = &TEST_CASES_NUMBERS[4]; + let mut reader = IntReader::new(buf[0], *prefix_len); + let mut test_receiver: TestReceiver = TestReceiver::default(); + + // data has not been received yet, reading IntReader will return Err(Error::NeedMoreData). + assert_eq!(reader.read(&mut test_receiver), Err(Error::NeedMoreData)); + + // Write one byte. + test_receiver.write(&buf[1..2]); + // data has not been received yet, reading IntReader will return Err(Error::NeedMoreData). + assert_eq!(reader.read(&mut test_receiver), Err(Error::NeedMoreData)); + + // Write one byte. + test_receiver.write(&buf[2..]); + // Now prefixed int is complete. + assert_eq!(reader.read(&mut test_receiver), Ok(*value)); + } + + type TestSetup = (&'static [u8], u8, Res<u64>); + const TEST_CASES_BIG_NUMBERS: [TestSetup; 3] = [ + ( + &[ + 0xFF, 0x80, 0xFE, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x01, + ], + 0, + Ok(0xFFFF_FFFF_FFFF_FFFF), + ), + ( + &[ + 0xFF, 0x81, 0xFE, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x01, + ], + 0, + Err(Error::IntegerOverflow), + ), + ( + &[ + 0xFF, 0x80, 0xFE, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x02, + ], + 0, + Err(Error::IntegerOverflow), + ), + ]; + + #[test] + fn read_prefixed_int_big_number() { + for (buf, prefix_len, value) in &TEST_CASES_BIG_NUMBERS { + let mut reader = IntReader::new(buf[0], *prefix_len); + let mut test_receiver: TestReceiver = TestReceiver::default(); + test_receiver.write(&buf[1..]); + assert_eq!(reader.read(&mut test_receiver), *value); + } + } + + const TEST_CASES_LITERAL: [(&[u8], u8, &str); 9] = [ + // No Huffman + ( + &[ + 0x0a, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, 0x79, + ], + 1, + "custom-key", + ), + ( + &[ + 0x0a, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, 0x79, + ], + 3, + "custom-key", + ), + ( + &[ + 0xea, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x6b, 0x65, 0x79, + ], + 3, + "custom-key", + ), + ( + &[ + 0x0d, 0x63, 0x75, 0x73, 0x74, 0x6f, 0x6d, 0x2d, 0x68, 0x65, 0x61, 0x64, 0x65, 0x72, + ], + 1, + "custom-header", + ), + // With Huffman + (&[0x15, 0xae, 0xc3, 0x77, 0x1a, 0x4b], 3, "private"), + ( + &[ + 0x56, 0xd0, 0x7a, 0xbe, 0x94, 0x10, 0x54, 0xd4, 0x44, 0xa8, 0x20, 0x05, 0x95, 0x04, + 0x0b, 0x81, 0x66, 0xe0, 0x82, 0xa6, 0x2d, 0x1b, 0xff, + ], + 1, + "Mon, 21 Oct 2013 20:13:21 GMT", + ), + ( + &[ + 0xff, 0x0f, 0xd0, 0x7a, 0xbe, 0x94, 0x10, 0x54, 0xd4, 0x44, 0xa8, 0x20, 0x05, 0x95, + 0x04, 0x0b, 0x81, 0x66, 0xe0, 0x82, 0xa6, 0x2d, 0x1b, 0xff, + ], + 4, + "Mon, 21 Oct 2013 20:13:21 GMT", + ), + ( + &[ + 0x51, 0x9d, 0x29, 0xad, 0x17, 0x18, 0x63, 0xc7, 0x8f, 0x0b, 0x97, 0xc8, 0xe9, 0xae, + 0x82, 0xae, 0x43, 0xd3, + ], + 1, + "https://www.example.com", + ), + ( + &[ + 0x91, 0x9d, 0x29, 0xad, 0x17, 0x18, 0x63, 0xc7, 0x8f, 0x0b, 0x97, 0xc8, 0xe9, 0xae, + 0x82, 0xae, 0x43, 0xd3, + ], + 0, + "https://www.example.com", + ), + ]; + + #[test] + fn read_literal() { + for (buf, prefix_len, value) in &TEST_CASES_LITERAL { + let mut reader = LiteralReader::new_with_first_byte(buf[0], *prefix_len); + let mut test_receiver: TestReceiver = TestReceiver::default(); + test_receiver.write(&buf[1..]); + assert_eq!( + to_string(&reader.read(&mut test_receiver).unwrap()).unwrap(), + *value + ); + } + } + + #[test] + fn read_prefixed_int_receiver_buffer_wrapper() { + for (buf, prefix_len, value) in &TEST_CASES_NUMBERS { + let mut buffer = ReceiverBufferWrapper::new(buf); + let mut reader = IntReader::new(buffer.read_byte().unwrap(), *prefix_len); + assert_eq!(reader.read(&mut buffer), Ok(*value)); + } + } + + #[test] + fn read_prefixed_int_big_receiver_buffer_wrapper() { + for (buf, prefix_len, value) in &TEST_CASES_BIG_NUMBERS { + let mut buffer = ReceiverBufferWrapper::new(buf); + let mut reader = IntReader::new(buffer.read_byte().unwrap(), *prefix_len); + assert_eq!(reader.read(&mut buffer), *value); + } + } + + #[test] + fn read_literal_receiver_buffer_wrapper() { + for (buf, prefix_len, value) in &TEST_CASES_LITERAL { + let mut buffer = ReceiverBufferWrapper::new(buf); + assert_eq!( + buffer.read_literal_from_buffer(*prefix_len).unwrap(), + *value + ); + } + } + + #[test] + fn read_failure_receiver_buffer_wrapper_number() { + let (buf, prefix_len, _) = &TEST_CASES_NUMBERS[4]; + let mut buffer = ReceiverBufferWrapper::new(&buf[..1]); + let mut reader = IntReader::new(buffer.read_byte().unwrap(), *prefix_len); + assert_eq!(reader.read(&mut buffer), Err(Error::DecompressionFailed)); + } + + #[test] + fn read_failure_receiver_buffer_wrapper_literal() { + let (buf, prefix_len, _) = &TEST_CASES_LITERAL[0]; + let mut buffer = ReceiverBufferWrapper::new(&buf[..6]); + assert_eq!( + buffer.read_literal_from_buffer(*prefix_len), + Err(Error::DecompressionFailed) + ); + } +} diff --git a/third_party/rust/neqo-qpack/src/static_table.rs b/third_party/rust/neqo-qpack/src/static_table.rs new file mode 100644 index 0000000000..4407fbce59 --- /dev/null +++ b/third_party/rust/neqo-qpack/src/static_table.rs @@ -0,0 +1,134 @@ +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +#[derive(Debug)] +pub struct StaticTableEntry { + index: u64, + name: &'static [u8], + value: &'static [u8], +} + +impl StaticTableEntry { + pub fn name(&self) -> &[u8] { + self.name + } + + pub fn value(&self) -> &[u8] { + self.value + } + + pub fn index(&self) -> u64 { + self.index + } +} + +macro_rules! static_table_entries { + [$($i:expr, $n:expr, $v:expr);+ $(;)?] => { + &[ $(StaticTableEntry { index: $i, name: $n, value: $v }),+ ] + }; +} + +pub const HEADER_STATIC_TABLE: &[StaticTableEntry] = static_table_entries![ + 0, b":authority", b""; + 1, b":path", b"/"; + 2, b"age", b"0"; + 3, b"content-disposition", b""; + 4, b"content-length", b"0"; + 5, b"cookie", b""; + 6, b"date", b""; + 7, b"etag", b""; + 8, b"if-modified-since", b""; + 9, b"if-none-match", b""; + 10, b"last-modified", b""; + 11, b"link", b""; + 12, b"location", b""; + 13, b"referer", b""; + 14, b"set-cookie", b""; + 15, b":method", b"CONNECT"; + 16, b":method", b"DELETE"; + 17, b":method", b"GET"; + 18, b":method", b"HEAD"; + 19, b":method", b"OPTIONS"; + 20, b":method", b"POST"; + 21, b":method", b"PUT"; + 22, b":scheme", b"http"; + 23, b":scheme", b"https"; + 24, b":status", b"103"; + 25, b":status", b"200"; + 26, b":status", b"304"; + 27, b":status", b"404"; + 28, b":status", b"503"; + 29, b"accept", b"*/*"; + 30, b"accept", b"application/dns-message"; + 31, b"accept-encoding", b"gzip, deflate, br"; + 32, b"accept-ranges", b"bytes"; + 33, b"access-control-allow-headers", b"cache-control"; + 34, b"access-control-allow-headers", b"content-type"; + 35, b"access-control-allow-origin", b"*"; + 36, b"cache-control", b"max-age=0"; + 37, b"cache-control", b"max-age=2592000"; + 38, b"cache-control", b"max-age=604800"; + 39, b"cache-control", b"no-cache"; + 40, b"cache-control", b"no-store"; + 41, b"cache-control", b"public, max-age=31536000"; + 42, b"content-encoding", b"br"; + 43, b"content-encoding", b"gzip"; + 44, b"content-type", b"application/dns-message"; + 45, b"content-type", b"application/javascript"; + 46, b"content-type", b"application/json"; + 47, b"content-type", b"application/x-www-form-urlencoded"; + 48, b"content-type", b"image/gif"; + 49, b"content-type", b"image/jpeg"; + 50, b"content-type", b"image/png"; + 51, b"content-type", b"text/css"; + 52, b"content-type", b"text/html; charset=utf-8"; + 53, b"content-type", b"text/plain"; + 54, b"content-type", b"text/plain;charset=utf-8"; + 55, b"range", b"bytes=0-"; + 56, b"strict-transport-security", b"max-age=31536000"; + 57, b"strict-transport-security", b"max-age=31536000; includesubdomains"; + 58, b"strict-transport-security", b"max-age=31536000; includesubdomains; preload"; + 59, b"vary", b"accept-encoding"; + 60, b"vary", b"origin"; + 61, b"x-content-type-options", b"nosniff"; + 62, b"x-xss-protection", b"1; mode=block"; + 63, b":status", b"100"; + 64, b":status", b"204"; + 65, b":status", b"206"; + 66, b":status", b"302"; + 67, b":status", b"400"; + 68, b":status", b"403"; + 69, b":status", b"421"; + 70, b":status", b"425"; + 71, b":status", b"500"; + 72, b"accept-language", b""; + 73, b"access-control-allow-credentials", b"FALSE"; + 74, b"access-control-allow-credentials", b"TRUE"; + 75, b"access-control-allow-headers", b"*"; + 76, b"access-control-allow-methods", b"get"; + 77, b"access-control-allow-methods", b"get, post, options"; + 78, b"access-control-allow-methods", b"options"; + 79, b"access-control-expose-headers", b"content-length"; + 80, b"access-control-request-headers", b"content-type"; + 81, b"access-control-request-method", b"get"; + 82, b"access-control-request-method", b"post"; + 83, b"alt-svc", b"clear"; + 84, b"authorization", b""; + 85, b"content-security-policy", b"script-src 'none'; object-src 'none'; base-uri 'none'"; + 86, b"early-data", b"1"; + 87, b"expect-ct", b""; + 88, b"forwarded", b""; + 89, b"if-range", b""; + 90, b"origin", b""; + 91, b"purpose", b"prefetch"; + 92, b"server", b""; + 93, b"timing-allow-origin", b"*"; + 94, b"upgrade-insecure-requests", b"1"; + 95, b"user-agent", b""; + 96, b"x-forwarded-for", b""; + 97, b"x-frame-options", b"deny"; + 98, b"x-frame-options", b"sameorigin"; +]; diff --git a/third_party/rust/neqo-qpack/src/stats.rs b/third_party/rust/neqo-qpack/src/stats.rs new file mode 100644 index 0000000000..7cb334b0c7 --- /dev/null +++ b/third_party/rust/neqo-qpack/src/stats.rs @@ -0,0 +1,17 @@ +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +// Tracking of some useful statistics. + +#[derive(Default, Debug, Clone)] +/// `QPack` statistics +pub struct Stats { + pub dynamic_table_inserts: usize, + // This is the munber of header blockes that reference the dynamic table. + pub dynamic_table_references: usize, + pub stream_cancelled_recv: usize, + pub header_acks_recv: usize, +} diff --git a/third_party/rust/neqo-qpack/src/table.rs b/third_party/rust/neqo-qpack/src/table.rs new file mode 100644 index 0000000000..8b2d70edce --- /dev/null +++ b/third_party/rust/neqo-qpack/src/table.rs @@ -0,0 +1,373 @@ +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use crate::static_table::{StaticTableEntry, HEADER_STATIC_TABLE}; +use crate::{Error, Res}; +use neqo_common::qtrace; +use std::collections::VecDeque; +use std::convert::TryFrom; + +pub const ADDITIONAL_TABLE_ENTRY_SIZE: usize = 32; + +pub struct LookupResult { + pub index: u64, + pub static_table: bool, + pub value_matches: bool, +} + +#[derive(Debug)] +pub(crate) struct DynamicTableEntry { + base: u64, + name: Vec<u8>, + value: Vec<u8>, + /// Number of header blocks that refer this entry. + /// This is only used by the encoder. + refs: u64, +} + +impl DynamicTableEntry { + pub fn can_reduce(&self, first_not_acked: u64) -> bool { + self.refs == 0 && self.base < first_not_acked + } + + pub fn size(&self) -> usize { + self.name.len() + self.value.len() + ADDITIONAL_TABLE_ENTRY_SIZE + } + + pub fn add_ref(&mut self) { + self.refs += 1; + } + + pub fn remove_ref(&mut self) { + assert!(self.refs > 0); + self.refs -= 1; + } + + pub fn name(&self) -> &[u8] { + &self.name + } + + pub fn value(&self) -> &[u8] { + &self.value + } + + pub fn index(&self) -> u64 { + self.base + } +} + +#[derive(Debug)] +pub(crate) struct HeaderTable { + dynamic: VecDeque<DynamicTableEntry>, + /// The total capacity (in QPACK bytes) of the table. This is set by + /// configuration. + capacity: u64, + /// The amount of used capacity. + used: u64, + /// The total number of inserts thus far. + base: u64, + /// This is number of inserts that are acked. this correspond to index of the first not acked. + /// This is only used by thee encoder. + acked_inserts_cnt: u64, +} + +impl ::std::fmt::Display for HeaderTable { + fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result { + write!( + f, + "HeaderTable for (base={} acked_inserts_cnt={} capacity={})", + self.base, self.acked_inserts_cnt, self.capacity + ) + } +} + +impl HeaderTable { + pub fn new(encoder: bool) -> Self { + Self { + dynamic: VecDeque::new(), + capacity: 0, + used: 0, + base: 0, + acked_inserts_cnt: if encoder { 0 } else { u64::max_value() }, + } + } + + /// Returns number of inserts. + pub fn base(&self) -> u64 { + self.base + } + + /// Returns capacity of the dynamic table + pub fn capacity(&self) -> u64 { + self.capacity + } + + /// Change the dynamic table capacity. + /// ### Errors + /// `ChangeCapacity` if table capacity cannot be reduced. + /// The table cannot be reduce if there are entries that are referred at the moment or their inserts are unacked. + pub fn set_capacity(&mut self, cap: u64) -> Res<()> { + qtrace!([self], "set capacity to {}", cap); + if !self.evict_to(cap) { + return Err(Error::ChangeCapacity); + } + self.capacity = cap; + Ok(()) + } + + /// Get a static entry with `index`. + /// ### Errors + /// `HeaderLookup` if the index does not exist in the static table. + pub fn get_static(index: u64) -> Res<&'static StaticTableEntry> { + let inx = usize::try_from(index).or(Err(Error::HeaderLookup))?; + if inx > HEADER_STATIC_TABLE.len() { + return Err(Error::HeaderLookup); + } + Ok(&HEADER_STATIC_TABLE[inx]) + } + + fn get_dynamic_with_abs_index(&mut self, index: u64) -> Res<&mut DynamicTableEntry> { + if self.base <= index { + debug_assert!(false, "This is an internal error"); + return Err(Error::HeaderLookup); + } + let inx = self.base - index - 1; + let inx = usize::try_from(inx).or(Err(Error::HeaderLookup))?; + if inx >= self.dynamic.len() { + return Err(Error::HeaderLookup); + } + Ok(&mut self.dynamic[inx]) + } + + fn get_dynamic_with_relative_index(&self, index: u64) -> Res<&DynamicTableEntry> { + let inx = usize::try_from(index).or(Err(Error::HeaderLookup))?; + if inx >= self.dynamic.len() { + return Err(Error::HeaderLookup); + } + Ok(&self.dynamic[inx]) + } + + /// Get a entry in the dynamic table. + /// ### Errors + /// `HeaderLookup` if entry does not exist. + pub fn get_dynamic(&self, index: u64, base: u64, post: bool) -> Res<&DynamicTableEntry> { + let inx = if post { + if self.base < (base + index + 1) { + return Err(Error::HeaderLookup); + } + self.base - (base + index + 1) + } else { + if (self.base + index) < base { + return Err(Error::HeaderLookup); + } + (self.base + index) - base + }; + + self.get_dynamic_with_relative_index(inx) + } + + /// Remove a reference to a dynamic table entry. + pub fn remove_ref(&mut self, index: u64) { + qtrace!([self], "remove reference to entry {}", index); + self.get_dynamic_with_abs_index(index) + .expect("we should have the entry") + .remove_ref(); + } + + /// Add a reference to a dynamic table entry. + pub fn add_ref(&mut self, index: u64) { + qtrace!([self], "add reference to entry {}", index); + self.get_dynamic_with_abs_index(index) + .expect("we should have the entry") + .add_ref(); + } + + /// Look for a header pair. + /// The function returns `LookupResult`: `index`, `static_table` (if it is a static table entry) and `value_matches` + /// (if the header value matches as well not only header name) + pub fn lookup(&mut self, name: &[u8], value: &[u8], can_block: bool) -> Option<LookupResult> { + qtrace!( + [self], + "lookup name:{:?} value {:?} can_block={}", + name, + value, + can_block + ); + let mut name_match = None; + for iter in HEADER_STATIC_TABLE.iter() { + if iter.name() == name { + if iter.value() == value { + return Some(LookupResult { + index: iter.index(), + static_table: true, + value_matches: true, + }); + } + + if name_match.is_none() { + name_match = Some(LookupResult { + index: iter.index(), + static_table: true, + value_matches: false, + }); + } + } + } + + for iter in &mut self.dynamic { + if !can_block && iter.index() >= self.acked_inserts_cnt { + continue; + } + if iter.name == name { + if iter.value == value { + return Some(LookupResult { + index: iter.index(), + static_table: false, + value_matches: true, + }); + } + + if name_match.is_none() { + name_match = Some(LookupResult { + index: iter.index(), + static_table: false, + value_matches: false, + }); + } + } + } + name_match + } + + fn evict_to(&mut self, reduce: u64) -> bool { + self.evict_to_internal(reduce, false) + } + + pub fn can_evict_to(&mut self, reduce: u64) -> bool { + self.evict_to_internal(reduce, true) + } + + pub fn evict_to_internal(&mut self, reduce: u64, only_check: bool) -> bool { + qtrace!( + [self], + "reduce table to {}, currently used:{} only_check:{}", + reduce, + self.used, + only_check + ); + let mut used = self.used; + while (!self.dynamic.is_empty()) && used > reduce { + if let Some(e) = self.dynamic.back() { + if !e.can_reduce(self.acked_inserts_cnt) { + return false; + } + used -= u64::try_from(e.size()).unwrap(); + if !only_check { + self.used -= u64::try_from(e.size()).unwrap(); + self.dynamic.pop_back(); + } + } + } + true + } + + pub fn insert_possible(&mut self, size: usize) -> bool { + u64::try_from(size).unwrap() <= self.capacity + && self.can_evict_to(self.capacity - u64::try_from(size).unwrap()) + } + + /// Insert a new entry. + /// ### Errors + /// `DynamicTableFull` if an entry cannot be added to the table because there is not enough space and/or + /// other entry cannot be evicted. + pub fn insert(&mut self, name: &[u8], value: &[u8]) -> Res<u64> { + qtrace!([self], "insert name={:?} value={:?}", name, value); + let entry = DynamicTableEntry { + name: name.to_vec(), + value: value.to_vec(), + base: self.base, + refs: 0, + }; + if u64::try_from(entry.size()).unwrap() > self.capacity + || !self.evict_to(self.capacity - u64::try_from(entry.size()).unwrap()) + { + return Err(Error::DynamicTableFull); + } + self.base += 1; + self.used += u64::try_from(entry.size()).unwrap(); + let index = entry.index(); + self.dynamic.push_front(entry); + Ok(index) + } + + /// Insert a new entry with the name refer to by a index to static or dynamic table. + /// ### Errors + /// `DynamicTableFull` if an entry cannot be added to the table because there is not enough space and/or + /// other entry cannot be evicted. + /// `HeaderLookup` if the index dos not exits in the static/dynamic table. + pub fn insert_with_name_ref( + &mut self, + name_static_table: bool, + name_index: u64, + value: &[u8], + ) -> Res<u64> { + qtrace!( + [self], + "insert with ref to index={} in {} value={:?}", + name_index, + if name_static_table { + "static" + } else { + "dynamic" + }, + value + ); + let name = if name_static_table { + HeaderTable::get_static(name_index)?.name().to_vec() + } else { + self.get_dynamic(name_index, self.base, false)? + .name() + .to_vec() + }; + self.insert(&name, value) + } + + /// Duplicate an entry. + /// ### Errors + /// `DynamicTableFull` if an entry cannot be added to the table because there is not enough space and/or + /// other entry cannot be evicted. + /// `HeaderLookup` if the index dos not exits in the static/dynamic table. + pub fn duplicate(&mut self, index: u64) -> Res<u64> { + qtrace!([self], "duplicate entry={}", index); + // need to remember name and value because insert may delete the entry. + let name: Vec<u8>; + let value: Vec<u8>; + { + let entry = self.get_dynamic(index, self.base, false)?; + name = entry.name().to_vec(); + value = entry.value().to_vec(); + qtrace!([self], "dumplicate name={:?} value={:?}", name, value); + } + self.insert(&name, &value) + } + + /// Increment number of acknowledge entries. + /// ### Errors + /// `IncrementAck` if ack is greater than actual number of inserts. + pub fn increment_acked(&mut self, increment: u64) -> Res<()> { + qtrace!([self], "increment acked by {}", increment); + self.acked_inserts_cnt += increment; + if self.base < self.acked_inserts_cnt { + return Err(Error::IncrementAck); + } + Ok(()) + } + + /// Return number of acknowledge inserts. + pub fn get_acked_inserts_cnt(&self) -> u64 { + self.acked_inserts_cnt + } +} |