diff options
Diffstat (limited to 'third_party/rust/h2/src/hpack/table.rs')
-rw-r--r-- | third_party/rust/h2/src/hpack/table.rs | 766 |
1 files changed, 766 insertions, 0 deletions
diff --git a/third_party/rust/h2/src/hpack/table.rs b/third_party/rust/h2/src/hpack/table.rs new file mode 100644 index 0000000000..3e45f413b8 --- /dev/null +++ b/third_party/rust/h2/src/hpack/table.rs @@ -0,0 +1,766 @@ +use super::Header; + +use fnv::FnvHasher; +use http::header; +use http::method::Method; + +use std::collections::VecDeque; +use std::hash::{Hash, Hasher}; +use std::{cmp, mem, usize}; + +/// HPACK encoder table +#[derive(Debug)] +pub struct Table { + mask: usize, + indices: Vec<Option<Pos>>, + slots: VecDeque<Slot>, + inserted: usize, + // Size is in bytes + size: usize, + max_size: usize, +} + +#[derive(Debug)] +pub enum Index { + // The header is already fully indexed + Indexed(usize, Header), + + // The name is indexed, but not the value + Name(usize, Header), + + // The full header has been inserted into the table. + Inserted(usize), + + // Only the value has been inserted (hpack table idx, slots idx) + InsertedValue(usize, usize), + + // The header is not indexed by this table + NotIndexed(Header), +} + +#[derive(Debug)] +struct Slot { + hash: HashValue, + header: Header, + next: Option<usize>, +} + +#[derive(Debug, Clone, Copy, Eq, PartialEq)] +struct Pos { + index: usize, + hash: HashValue, +} + +#[derive(Debug, Copy, Clone, Eq, PartialEq)] +struct HashValue(usize); + +const MAX_SIZE: usize = 1 << 16; +const DYN_OFFSET: usize = 62; + +macro_rules! probe_loop { + ($probe_var: ident < $len: expr, $body: expr) => { + debug_assert!($len > 0); + loop { + if $probe_var < $len { + $body + $probe_var += 1; + } else { + $probe_var = 0; + } + } + }; +} + +impl Table { + pub fn new(max_size: usize, capacity: usize) -> Table { + if capacity == 0 { + Table { + mask: 0, + indices: vec![], + slots: VecDeque::new(), + inserted: 0, + size: 0, + max_size, + } + } else { + let capacity = cmp::max(to_raw_capacity(capacity).next_power_of_two(), 8); + + Table { + mask: capacity.wrapping_sub(1), + indices: vec![None; capacity], + slots: VecDeque::with_capacity(usable_capacity(capacity)), + inserted: 0, + size: 0, + max_size, + } + } + } + + #[inline] + pub fn capacity(&self) -> usize { + usable_capacity(self.indices.len()) + } + + pub fn max_size(&self) -> usize { + self.max_size + } + + /// Gets the header stored in the table + pub fn resolve<'a>(&'a self, index: &'a Index) -> &'a Header { + use self::Index::*; + + match *index { + Indexed(_, ref h) => h, + Name(_, ref h) => h, + Inserted(idx) => &self.slots[idx].header, + InsertedValue(_, idx) => &self.slots[idx].header, + NotIndexed(ref h) => h, + } + } + + pub fn resolve_idx(&self, index: &Index) -> usize { + use self::Index::*; + + match *index { + Indexed(idx, ..) => idx, + Name(idx, ..) => idx, + Inserted(idx) => idx + DYN_OFFSET, + InsertedValue(_name_idx, slot_idx) => slot_idx + DYN_OFFSET, + NotIndexed(_) => panic!("cannot resolve index"), + } + } + + /// Index the header in the HPACK table. + pub fn index(&mut self, header: Header) -> Index { + // Check the static table + let statik = index_static(&header); + + // Don't index certain headers. This logic is borrowed from nghttp2. + if header.skip_value_index() { + // Right now, if this is true, the header name is always in the + // static table. At some point in the future, this might not be true + // and this logic will need to be updated. + debug_assert!(statik.is_some(), "skip_value_index requires a static name",); + return Index::new(statik, header); + } + + // If the header is already indexed by the static table, return that + if let Some((n, true)) = statik { + return Index::Indexed(n, header); + } + + // Don't index large headers + if header.len() * 4 > self.max_size * 3 { + return Index::new(statik, header); + } + + self.index_dynamic(header, statik) + } + + fn index_dynamic(&mut self, header: Header, statik: Option<(usize, bool)>) -> Index { + debug_assert!(self.assert_valid_state("one")); + + if header.len() + self.size < self.max_size || !header.is_sensitive() { + // Only grow internal storage if needed + self.reserve_one(); + } + + if self.indices.is_empty() { + // If `indices` is not empty, then it is impossible for all + // `indices` entries to be `Some`. So, we only need to check for the + // empty case. + return Index::new(statik, header); + } + + let hash = hash_header(&header); + + let desired_pos = desired_pos(self.mask, hash); + let mut probe = desired_pos; + let mut dist = 0; + + // Start at the ideal position, checking all slots + probe_loop!(probe < self.indices.len(), { + if let Some(pos) = self.indices[probe] { + // The slot is already occupied, but check if it has a lower + // displacement. + let their_dist = probe_distance(self.mask, pos.hash, probe); + + let slot_idx = pos.index.wrapping_add(self.inserted); + + if their_dist < dist { + // Index robinhood + return self.index_vacant(header, hash, dist, probe, statik); + } else if pos.hash == hash && self.slots[slot_idx].header.name() == header.name() { + // Matching name, check values + return self.index_occupied(header, hash, pos.index, statik.map(|(n, _)| n)); + } + } else { + return self.index_vacant(header, hash, dist, probe, statik); + } + + dist += 1; + }); + } + + fn index_occupied( + &mut self, + header: Header, + hash: HashValue, + mut index: usize, + statik: Option<usize>, + ) -> Index { + debug_assert!(self.assert_valid_state("top")); + + // There already is a match for the given header name. Check if a value + // matches. The header will also only be inserted if the table is not at + // capacity. + loop { + // Compute the real index into the VecDeque + let real_idx = index.wrapping_add(self.inserted); + + if self.slots[real_idx].header.value_eq(&header) { + // We have a full match! + return Index::Indexed(real_idx + DYN_OFFSET, header); + } + + if let Some(next) = self.slots[real_idx].next { + index = next; + continue; + } + + if header.is_sensitive() { + // Should we assert this? + // debug_assert!(statik.is_none()); + return Index::Name(real_idx + DYN_OFFSET, header); + } + + self.update_size(header.len(), Some(index)); + + // Insert the new header + self.insert(header, hash); + + // Recompute real_idx as it just changed. + let new_real_idx = index.wrapping_add(self.inserted); + + // The previous node in the linked list may have gotten evicted + // while making room for this header. + if new_real_idx < self.slots.len() { + let idx = 0usize.wrapping_sub(self.inserted); + + self.slots[new_real_idx].next = Some(idx); + } + + debug_assert!(self.assert_valid_state("bottom")); + + // Even if the previous header was evicted, we can still reference + // it when inserting the new one... + return if let Some(n) = statik { + // If name is in static table, use it instead + Index::InsertedValue(n, 0) + } else { + Index::InsertedValue(real_idx + DYN_OFFSET, 0) + }; + } + } + + fn index_vacant( + &mut self, + header: Header, + hash: HashValue, + mut dist: usize, + mut probe: usize, + statik: Option<(usize, bool)>, + ) -> Index { + if header.is_sensitive() { + return Index::new(statik, header); + } + + debug_assert!(self.assert_valid_state("top")); + debug_assert!(dist == 0 || self.indices[probe.wrapping_sub(1) & self.mask].is_some()); + + // Passing in `usize::MAX` for prev_idx since there is no previous + // header in this case. + if self.update_size(header.len(), None) { + while dist != 0 { + let back = probe.wrapping_sub(1) & self.mask; + + if let Some(pos) = self.indices[back] { + let their_dist = probe_distance(self.mask, pos.hash, back); + + if their_dist < (dist - 1) { + probe = back; + dist -= 1; + } else { + break; + } + } else { + probe = back; + dist -= 1; + } + } + } + + debug_assert!(self.assert_valid_state("after update")); + + self.insert(header, hash); + + let pos_idx = 0usize.wrapping_sub(self.inserted); + + let prev = mem::replace( + &mut self.indices[probe], + Some(Pos { + index: pos_idx, + hash, + }), + ); + + if let Some(mut prev) = prev { + // Shift forward + let mut probe = probe + 1; + + probe_loop!(probe < self.indices.len(), { + let pos = &mut self.indices[probe]; + + prev = match mem::replace(pos, Some(prev)) { + Some(p) => p, + None => break, + }; + }); + } + + debug_assert!(self.assert_valid_state("bottom")); + + if let Some((n, _)) = statik { + Index::InsertedValue(n, 0) + } else { + Index::Inserted(0) + } + } + + fn insert(&mut self, header: Header, hash: HashValue) { + self.inserted = self.inserted.wrapping_add(1); + + self.slots.push_front(Slot { + hash, + header, + next: None, + }); + } + + pub fn resize(&mut self, size: usize) { + self.max_size = size; + + if size == 0 { + self.size = 0; + + for i in &mut self.indices { + *i = None; + } + + self.slots.clear(); + self.inserted = 0; + } else { + self.converge(None); + } + } + + fn update_size(&mut self, len: usize, prev_idx: Option<usize>) -> bool { + self.size += len; + self.converge(prev_idx) + } + + fn converge(&mut self, prev_idx: Option<usize>) -> bool { + let mut ret = false; + + while self.size > self.max_size { + ret = true; + self.evict(prev_idx); + } + + ret + } + + fn evict(&mut self, prev_idx: Option<usize>) { + let pos_idx = (self.slots.len() - 1).wrapping_sub(self.inserted); + + debug_assert!(!self.slots.is_empty()); + debug_assert!(self.assert_valid_state("one")); + + // Remove the header + let slot = self.slots.pop_back().unwrap(); + let mut probe = desired_pos(self.mask, slot.hash); + + // Update the size + self.size -= slot.header.len(); + + debug_assert_eq!( + self.indices + .iter() + .filter_map(|p| *p) + .filter(|p| p.index == pos_idx) + .count(), + 1 + ); + + // Find the associated position + probe_loop!(probe < self.indices.len(), { + debug_assert!(self.indices[probe].is_some()); + + let mut pos = self.indices[probe].unwrap(); + + if pos.index == pos_idx { + if let Some(idx) = slot.next { + pos.index = idx; + self.indices[probe] = Some(pos); + } else if Some(pos.index) == prev_idx { + pos.index = 0usize.wrapping_sub(self.inserted + 1); + self.indices[probe] = Some(pos); + } else { + self.indices[probe] = None; + self.remove_phase_two(probe); + } + + break; + } + }); + + debug_assert!(self.assert_valid_state("two")); + } + + // Shifts all indices that were displaced by the header that has just been + // removed. + fn remove_phase_two(&mut self, probe: usize) { + let mut last_probe = probe; + let mut probe = probe + 1; + + probe_loop!(probe < self.indices.len(), { + if let Some(pos) = self.indices[probe] { + if probe_distance(self.mask, pos.hash, probe) > 0 { + self.indices[last_probe] = self.indices[probe].take(); + } else { + break; + } + } else { + break; + } + + last_probe = probe; + }); + + debug_assert!(self.assert_valid_state("two")); + } + + fn reserve_one(&mut self) { + let len = self.slots.len(); + + if len == self.capacity() { + if len == 0 { + let new_raw_cap = 8; + self.mask = 8 - 1; + self.indices = vec![None; new_raw_cap]; + } else { + let raw_cap = self.indices.len(); + self.grow(raw_cap << 1); + } + } + } + + #[inline] + fn grow(&mut self, new_raw_cap: usize) { + // This path can never be reached when handling the first allocation in + // the map. + + debug_assert!(self.assert_valid_state("top")); + + // find first ideally placed element -- start of cluster + let mut first_ideal = 0; + + for (i, pos) in self.indices.iter().enumerate() { + if let Some(pos) = *pos { + if 0 == probe_distance(self.mask, pos.hash, i) { + first_ideal = i; + break; + } + } + } + + // visit the entries in an order where we can simply reinsert them + // into self.indices without any bucket stealing. + let old_indices = mem::replace(&mut self.indices, vec![None; new_raw_cap]); + self.mask = new_raw_cap.wrapping_sub(1); + + for &pos in &old_indices[first_ideal..] { + self.reinsert_entry_in_order(pos); + } + + for &pos in &old_indices[..first_ideal] { + self.reinsert_entry_in_order(pos); + } + + debug_assert!(self.assert_valid_state("bottom")); + } + + fn reinsert_entry_in_order(&mut self, pos: Option<Pos>) { + if let Some(pos) = pos { + // Find first empty bucket and insert there + let mut probe = desired_pos(self.mask, pos.hash); + + probe_loop!(probe < self.indices.len(), { + if self.indices[probe].is_none() { + // empty bucket, insert here + self.indices[probe] = Some(pos); + return; + } + + debug_assert!({ + let them = self.indices[probe].unwrap(); + let their_distance = probe_distance(self.mask, them.hash, probe); + let our_distance = probe_distance(self.mask, pos.hash, probe); + + their_distance >= our_distance + }); + }); + } + } + + #[cfg(not(test))] + fn assert_valid_state(&self, _: &'static str) -> bool { + true + } + + #[cfg(test)] + fn assert_valid_state(&self, _msg: &'static str) -> bool { + /* + // Checks that the internal map structure is valid + // + // Ensure all hash codes in indices match the associated slot + for pos in &self.indices { + if let Some(pos) = *pos { + let real_idx = pos.index.wrapping_add(self.inserted); + + if real_idx.wrapping_add(1) != 0 { + assert!(real_idx < self.slots.len(), + "out of index; real={}; len={}, msg={}", + real_idx, self.slots.len(), msg); + + assert_eq!(pos.hash, self.slots[real_idx].hash, + "index hash does not match slot; msg={}", msg); + } + } + } + + // Every index is only available once + for i in 0..self.indices.len() { + if self.indices[i].is_none() { + continue; + } + + for j in i+1..self.indices.len() { + assert_ne!(self.indices[i], self.indices[j], + "duplicate indices; msg={}", msg); + } + } + + for (index, slot) in self.slots.iter().enumerate() { + let mut indexed = None; + + // First, see if the slot is indexed + for (i, pos) in self.indices.iter().enumerate() { + if let Some(pos) = *pos { + let real_idx = pos.index.wrapping_add(self.inserted); + if real_idx == index { + indexed = Some(i); + // Already know that there is no dup, so break + break; + } + } + } + + if let Some(actual) = indexed { + // Ensure that it is accessible.. + let desired = desired_pos(self.mask, slot.hash); + let mut probe = desired; + let mut dist = 0; + + probe_loop!(probe < self.indices.len(), { + assert!(self.indices[probe].is_some(), + "unexpected empty slot; probe={}; hash={:?}; msg={}", + probe, slot.hash, msg); + + let pos = self.indices[probe].unwrap(); + + let their_dist = probe_distance(self.mask, pos.hash, probe); + let real_idx = pos.index.wrapping_add(self.inserted); + + if real_idx == index { + break; + } + + assert!(dist <= their_dist, + "could not find entry; actual={}; desired={}" + + "probe={}, dist={}; their_dist={}; index={}; msg={}", + actual, desired, probe, dist, their_dist, + index.wrapping_sub(self.inserted), msg); + + dist += 1; + }); + } else { + // There is exactly one next link + let cnt = self.slots.iter().map(|s| s.next) + .filter(|n| *n == Some(index.wrapping_sub(self.inserted))) + .count(); + + assert_eq!(1, cnt, "more than one node pointing here; msg={}", msg); + } + } + */ + + // TODO: Ensure linked lists are correct: no cycles, etc... + + true + } +} + +#[cfg(test)] +impl Table { + /// Returns the number of headers in the table + pub fn len(&self) -> usize { + self.slots.len() + } + + /// Returns the table size + pub fn size(&self) -> usize { + self.size + } +} + +impl Index { + fn new(v: Option<(usize, bool)>, e: Header) -> Index { + match v { + None => Index::NotIndexed(e), + Some((n, true)) => Index::Indexed(n, e), + Some((n, false)) => Index::Name(n, e), + } + } +} + +#[inline] +fn usable_capacity(cap: usize) -> usize { + cap - cap / 4 +} + +#[inline] +fn to_raw_capacity(n: usize) -> usize { + n + n / 3 +} + +#[inline] +fn desired_pos(mask: usize, hash: HashValue) -> usize { + hash.0 & mask +} + +#[inline] +fn probe_distance(mask: usize, hash: HashValue, current: usize) -> usize { + current.wrapping_sub(desired_pos(mask, hash)) & mask +} + +fn hash_header(header: &Header) -> HashValue { + const MASK: u64 = (MAX_SIZE as u64) - 1; + + let mut h = FnvHasher::default(); + header.name().hash(&mut h); + HashValue((h.finish() & MASK) as usize) +} + +/// Checks the static table for the header. If found, returns the index and a +/// boolean representing if the value matched as well. +fn index_static(header: &Header) -> Option<(usize, bool)> { + match *header { + Header::Field { + ref name, + ref value, + } => match *name { + header::ACCEPT_CHARSET => Some((15, false)), + header::ACCEPT_ENCODING => { + if value == "gzip, deflate" { + Some((16, true)) + } else { + Some((16, false)) + } + } + header::ACCEPT_LANGUAGE => Some((17, false)), + header::ACCEPT_RANGES => Some((18, false)), + header::ACCEPT => Some((19, false)), + header::ACCESS_CONTROL_ALLOW_ORIGIN => Some((20, false)), + header::AGE => Some((21, false)), + header::ALLOW => Some((22, false)), + header::AUTHORIZATION => Some((23, false)), + header::CACHE_CONTROL => Some((24, false)), + header::CONTENT_DISPOSITION => Some((25, false)), + header::CONTENT_ENCODING => Some((26, false)), + header::CONTENT_LANGUAGE => Some((27, false)), + header::CONTENT_LENGTH => Some((28, false)), + header::CONTENT_LOCATION => Some((29, false)), + header::CONTENT_RANGE => Some((30, false)), + header::CONTENT_TYPE => Some((31, false)), + header::COOKIE => Some((32, false)), + header::DATE => Some((33, false)), + header::ETAG => Some((34, false)), + header::EXPECT => Some((35, false)), + header::EXPIRES => Some((36, false)), + header::FROM => Some((37, false)), + header::HOST => Some((38, false)), + header::IF_MATCH => Some((39, false)), + header::IF_MODIFIED_SINCE => Some((40, false)), + header::IF_NONE_MATCH => Some((41, false)), + header::IF_RANGE => Some((42, false)), + header::IF_UNMODIFIED_SINCE => Some((43, false)), + header::LAST_MODIFIED => Some((44, false)), + header::LINK => Some((45, false)), + header::LOCATION => Some((46, false)), + header::MAX_FORWARDS => Some((47, false)), + header::PROXY_AUTHENTICATE => Some((48, false)), + header::PROXY_AUTHORIZATION => Some((49, false)), + header::RANGE => Some((50, false)), + header::REFERER => Some((51, false)), + header::REFRESH => Some((52, false)), + header::RETRY_AFTER => Some((53, false)), + header::SERVER => Some((54, false)), + header::SET_COOKIE => Some((55, false)), + header::STRICT_TRANSPORT_SECURITY => Some((56, false)), + header::TRANSFER_ENCODING => Some((57, false)), + header::USER_AGENT => Some((58, false)), + header::VARY => Some((59, false)), + header::VIA => Some((60, false)), + header::WWW_AUTHENTICATE => Some((61, false)), + _ => None, + }, + Header::Authority(_) => Some((1, false)), + Header::Method(ref v) => match *v { + Method::GET => Some((2, true)), + Method::POST => Some((3, true)), + _ => Some((2, false)), + }, + Header::Scheme(ref v) => match &**v { + "http" => Some((6, true)), + "https" => Some((7, true)), + _ => Some((6, false)), + }, + Header::Path(ref v) => match &**v { + "/" => Some((4, true)), + "/index.html" => Some((5, true)), + _ => Some((4, false)), + }, + Header::Protocol(..) => None, + Header::Status(ref v) => match u16::from(*v) { + 200 => Some((8, true)), + 204 => Some((9, true)), + 206 => Some((10, true)), + 304 => Some((11, true)), + 400 => Some((12, true)), + 404 => Some((13, true)), + 500 => Some((14, true)), + _ => Some((8, false)), + }, + } +} |