summaryrefslogtreecommitdiffstats
path: root/third_party/rust/h2/src/hpack/table.rs
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/rust/h2/src/hpack/table.rs')
-rw-r--r--third_party/rust/h2/src/hpack/table.rs766
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..0124f216d5
--- /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 as usize];
+
+ 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_none());
+
+ 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) as usize
+}
+
+#[inline]
+fn probe_distance(mask: usize, hash: HashValue, current: usize) -> usize {
+ current.wrapping_sub(desired_pos(mask, hash)) & mask as usize
+}
+
+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)),
+ },
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-23 13:29:20 +0000