/rust/registry/src/index.crates.io-6f17d22bba15001f/h2-0.4.7/src/hpack/table.rs

Source (jump to first uncovered line)
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};

/// 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)),
        },
    }
}

Coverage Report

Created: 2025-02-25 06:39

Line	Count	Source (jump to first uncovered line)
1		use super::Header;
2
3		use fnv::FnvHasher;
4		use http::header;
5		use http::method::Method;
6
7		use std::collections::VecDeque;
8		use std::hash::{Hash, Hasher};
9		use std::{cmp, mem};
10
11		/// HPACK encoder table
12		#[derive(Debug)]
13		pub struct Table {
14		mask: usize,
15		indices: Vec<Option<Pos>>,
16		slots: VecDeque<Slot>,
17		inserted: usize,
18		// Size is in bytes
19		size: usize,
20		max_size: usize,
21		}
22
23		#[derive(Debug)]
24		pub enum Index {
25		// The header is already fully indexed
26		Indexed(usize, Header),
27
28		// The name is indexed, but not the value
29		Name(usize, Header),
30
31		// The full header has been inserted into the table.
32		Inserted(usize),
33
34		// Only the value has been inserted (hpack table idx, slots idx)
35		InsertedValue(usize, usize),
36
37		// The header is not indexed by this table
38		NotIndexed(Header),
39		}
40
41		#[derive(Debug)]
42		struct Slot {
43		hash: HashValue,
44		header: Header,
45		next: Option<usize>,
46		}
47
48		#[derive(Debug, Clone, Copy, Eq, PartialEq)]
49		struct Pos {
50		index: usize,
51		hash: HashValue,
52		}
53
54		#[derive(Debug, Copy, Clone, Eq, PartialEq)]
55		struct HashValue(usize);
56
57		const MAX_SIZE: usize = 1 << 16;
58		const DYN_OFFSET: usize = 62;
59
60		macro_rules! probe_loop {
61		($probe_var: ident < $len: expr, $body: expr) => {
62		debug_assert!($len > 0);
63		loop {
64		if $probe_var < $len {
65		$body
66		$probe_var += 1;
67		} else {
68		$probe_var = 0;
69		}
70		}
71		};
72		}
73
74		impl Table {
75	0	pub fn new(max_size: usize, capacity: usize) -> Table {
76	0	if capacity == 0 {
77	0	Table {
78	0	mask: 0,
79	0	indices: vec![],
80	0	slots: VecDeque::new(),
81	0	inserted: 0,
82	0	size: 0,
83	0	max_size,
84	0	}
85		} else {
86	0	let capacity = cmp::max(to_raw_capacity(capacity).next_power_of_two(), 8);
87	0
88	0	Table {
89	0	mask: capacity.wrapping_sub(1),
90	0	indices: vec![None; capacity],
91	0	slots: VecDeque::with_capacity(usable_capacity(capacity)),
92	0	inserted: 0,
93	0	size: 0,
94	0	max_size,
95	0	}
96		}
97	0	}
98
99		#[inline]
100	0	pub fn capacity(&self) -> usize {
101	0	usable_capacity(self.indices.len())
102	0	}
103
104	0	pub fn max_size(&self) -> usize {
105	0	self.max_size
106	0	}
107
108		/// Gets the header stored in the table
109	0	pub fn resolve<'a>(&'a self, index: &'a Index) -> &'a Header {
110		use self::Index::*;
111
112	0	match *index {
113	0	Indexed(_, ref h) => h,
114	0	Name(_, ref h) => h,
115	0	Inserted(idx) => &self.slots[idx].header,
116	0	InsertedValue(_, idx) => &self.slots[idx].header,
117	0	NotIndexed(ref h) => h,
118		}
119	0	}
120
121	0	pub fn resolve_idx(&self, index: &Index) -> usize {
122		use self::Index::*;
123
124	0	match *index {
125	0	Indexed(idx, ..) => idx,
126	0	Name(idx, ..) => idx,
127	0	Inserted(idx) => idx + DYN_OFFSET,
128	0	InsertedValue(_name_idx, slot_idx) => slot_idx + DYN_OFFSET,
129	0	NotIndexed(_) => panic!("cannot resolve index"),
130		}
131	0	}
132
133		/// Index the header in the HPACK table.
134	0	pub fn index(&mut self, header: Header) -> Index {
135	0	// Check the static table
136	0	let statik = index_static(&header);
137	0
138	0	// Don't index certain headers. This logic is borrowed from nghttp2.
139	0	if header.skip_value_index() {
140		// Right now, if this is true, the header name is always in the
141		// static table. At some point in the future, this might not be true
142		// and this logic will need to be updated.
143	0	debug_assert!(statik.is_some(), "skip_value_index requires a static name",);
144	0	return Index::new(statik, header);
145	0	}
146
147		// If the header is already indexed by the static table, return that
148	0	if let Some((n, true)) = statik {
149	0	return Index::Indexed(n, header);
150	0	}
151	0
152	0	// Don't index large headers
153	0	if header.len() * 4 > self.max_size * 3 {
154	0	return Index::new(statik, header);
155	0	}
156	0
157	0	self.index_dynamic(header, statik)
158	0	}
159
160	0	fn index_dynamic(&mut self, header: Header, statik: Option<(usize, bool)>) -> Index {
161	0	debug_assert!(self.assert_valid_state("one"));
162
163	0	if header.len() + self.size < self.max_size \|\| !header.is_sensitive() {
164	0	// Only grow internal storage if needed
165	0	self.reserve_one();
166	0	}
167
168	0	if self.indices.is_empty() {
169		// If `indices` is not empty, then it is impossible for all
170		// `indices` entries to be `Some`. So, we only need to check for the
171		// empty case.
172	0	return Index::new(statik, header);
173	0	}
174	0
175	0	let hash = hash_header(&header);
176	0
177	0	let desired_pos = desired_pos(self.mask, hash);
178	0	let mut probe = desired_pos;
179	0	let mut dist = 0;
180	0
181	0	// Start at the ideal position, checking all slots
182	0	probe_loop!(probe < self.indices.len(), {
183	0	if let Some(pos) = self.indices[probe] {
184		// The slot is already occupied, but check if it has a lower
185		// displacement.
186	0	let their_dist = probe_distance(self.mask, pos.hash, probe);
187	0
188	0	let slot_idx = pos.index.wrapping_add(self.inserted);
189	0
190	0	if their_dist < dist {
191		// Index robinhood
192	0	return self.index_vacant(header, hash, dist, probe, statik);
193	0	} else if pos.hash == hash && self.slots[slot_idx].header.name() == header.name() {
194		// Matching name, check values
195	0	return self.index_occupied(header, hash, pos.index, statik.map(\|(n, _)\| n));
196	0	}
197		} else {
198	0	return self.index_vacant(header, hash, dist, probe, statik);
199		}
200
201	0	dist += 1;
202		});
203	0	}
204
205	0	fn index_occupied(
206	0	&mut self,
207	0	header: Header,
208	0	hash: HashValue,
209	0	mut index: usize,
210	0	statik: Option<usize>,
211	0	) -> Index {
212	0	debug_assert!(self.assert_valid_state("top"));
213
214		// There already is a match for the given header name. Check if a value
215		// matches. The header will also only be inserted if the table is not at
216		// capacity.
217		loop {
218		// Compute the real index into the VecDeque
219	0	let real_idx = index.wrapping_add(self.inserted);
220	0
221	0	if self.slots[real_idx].header.value_eq(&header) {
222		// We have a full match!
223	0	return Index::Indexed(real_idx + DYN_OFFSET, header);
224	0	}
225
226	0	if let Some(next) = self.slots[real_idx].next {
227	0	index = next;
228	0	continue;
229	0	}
230	0
231	0	if header.is_sensitive() {
232		// Should we assert this?
233		// debug_assert!(statik.is_none());
234	0	return Index::Name(real_idx + DYN_OFFSET, header);
235	0	}
236	0
237	0	self.update_size(header.len(), Some(index));
238	0
239	0	// Insert the new header
240	0	self.insert(header, hash);
241	0
242	0	// Recompute real_idx as it just changed.
243	0	let new_real_idx = index.wrapping_add(self.inserted);
244	0
245	0	// The previous node in the linked list may have gotten evicted
246	0	// while making room for this header.
247	0	if new_real_idx < self.slots.len() {
248	0	let idx = 0usize.wrapping_sub(self.inserted);
249	0
250	0	self.slots[new_real_idx].next = Some(idx);
251	0	}
252
253	0	debug_assert!(self.assert_valid_state("bottom"));
254
255		// Even if the previous header was evicted, we can still reference
256		// it when inserting the new one...
257	0	return if let Some(n) = statik {
258		// If name is in static table, use it instead
259	0	Index::InsertedValue(n, 0)
260		} else {
261	0	Index::InsertedValue(real_idx + DYN_OFFSET, 0)
262		};
263		}
264	0	}
265
266	0	fn index_vacant(
267	0	&mut self,
268	0	header: Header,
269	0	hash: HashValue,
270	0	mut dist: usize,
271	0	mut probe: usize,
272	0	statik: Option<(usize, bool)>,
273	0	) -> Index {
274	0	if header.is_sensitive() {
275	0	return Index::new(statik, header);
276	0	}
277	0
278	0	debug_assert!(self.assert_valid_state("top"));
279	0	debug_assert!(dist == 0 \|\| self.indices[probe.wrapping_sub(1) & self.mask].is_some());
280
281		// Passing in `usize::MAX` for prev_idx since there is no previous
282		// header in this case.
283	0	if self.update_size(header.len(), None) {
284	0	while dist != 0 {
285	0	let back = probe.wrapping_sub(1) & self.mask;
286
287	0	if let Some(pos) = self.indices[back] {
288	0	let their_dist = probe_distance(self.mask, pos.hash, back);
289	0
290	0	if their_dist < (dist - 1) {
291	0	probe = back;
292	0	dist -= 1;
293	0	} else {
294	0	break;
295		}
296	0	} else {
297	0	probe = back;
298	0	dist -= 1;
299	0	}
300		}
301	0	}
302
303	0	debug_assert!(self.assert_valid_state("after update"));
304
305	0	self.insert(header, hash);
306	0
307	0	let pos_idx = 0usize.wrapping_sub(self.inserted);
308	0
309	0	let prev = mem::replace(
310	0	&mut self.indices[probe],
311	0	Some(Pos {
312	0	index: pos_idx,
313	0	hash,
314	0	}),
315	0	);
316
317	0	if let Some(mut prev) = prev {
318		// Shift forward
319	0	let mut probe = probe + 1;
320	0
321	0	probe_loop!(probe < self.indices.len(), {
322	0	let pos = &mut self.indices[probe];
323	0
324	0	prev = match mem::replace(pos, Some(prev)) {
325	0	Some(p) => p,
326	0	None => break,
327		};
328		});
329	0	}
330
331	0	debug_assert!(self.assert_valid_state("bottom"));
332
333	0	if let Some((n, _)) = statik {
334	0	Index::InsertedValue(n, 0)
335		} else {
336	0	Index::Inserted(0)
337		}
338	0	}
339
340	0	fn insert(&mut self, header: Header, hash: HashValue) {
341	0	self.inserted = self.inserted.wrapping_add(1);
342	0
343	0	self.slots.push_front(Slot {
344	0	hash,
345	0	header,
346	0	next: None,
347	0	});
348	0	}
349
350	0	pub fn resize(&mut self, size: usize) {
351	0	self.max_size = size;
352	0
353	0	if size == 0 {
354	0	self.size = 0;
355
356	0	for i in &mut self.indices {
357	0	*i = None;
358	0	}
359
360	0	self.slots.clear();
361	0	self.inserted = 0;
362	0	} else {
363	0	self.converge(None);
364	0	}
365	0	}
366
367	0	fn update_size(&mut self, len: usize, prev_idx: Option<usize>) -> bool {
368	0	self.size += len;
369	0	self.converge(prev_idx)
370	0	}
371
372	0	fn converge(&mut self, prev_idx: Option<usize>) -> bool {
373	0	let mut ret = false;
374
375	0	while self.size > self.max_size {
376	0	ret = true;
377	0	self.evict(prev_idx);
378	0	}
379
380	0	ret
381	0	}
382
383	0	fn evict(&mut self, prev_idx: Option<usize>) {
384	0	let pos_idx = (self.slots.len() - 1).wrapping_sub(self.inserted);
385	0
386	0	debug_assert!(!self.slots.is_empty());
387	0	debug_assert!(self.assert_valid_state("one"));
388
389		// Remove the header
390	0	let slot = self.slots.pop_back().unwrap();
391	0	let mut probe = desired_pos(self.mask, slot.hash);
392	0
393	0	// Update the size
394	0	self.size -= slot.header.len();
395	0
396	0	debug_assert_eq!(
397	0	self.indices
398	0	.iter()
399	0	.filter_map(\|p\| *p)
400	0	.filter(\|p\| p.index == pos_idx)
401	0	.count(),
402		1
403		);
404
405		// Find the associated position
406	0	probe_loop!(probe < self.indices.len(), {
407	0	debug_assert!(self.indices[probe].is_some());
408
409	0	let mut pos = self.indices[probe].unwrap();
410	0
411	0	if pos.index == pos_idx {
412	0	if let Some(idx) = slot.next {
413	0	pos.index = idx;
414	0	self.indices[probe] = Some(pos);
415	0	} else if Some(pos.index) == prev_idx {
416	0	pos.index = 0usize.wrapping_sub(self.inserted + 1);
417	0	self.indices[probe] = Some(pos);
418	0	} else {
419	0	self.indices[probe] = None;
420	0	self.remove_phase_two(probe);
421	0	}
422
423	0	break;
424	0	}
425		});
426
427	0	debug_assert!(self.assert_valid_state("two"));
428	0	}
429
430		// Shifts all indices that were displaced by the header that has just been
431		// removed.
432	0	fn remove_phase_two(&mut self, probe: usize) {
433	0	let mut last_probe = probe;
434	0	let mut probe = probe + 1;
435	0
436	0	probe_loop!(probe < self.indices.len(), {
437	0	if let Some(pos) = self.indices[probe] {
438	0	if probe_distance(self.mask, pos.hash, probe) > 0 {
439	0	self.indices[last_probe] = self.indices[probe].take();
440	0	} else {
441	0	break;
442		}
443		} else {
444	0	break;
445		}
446
447	0	last_probe = probe;
448		});
449
450	0	debug_assert!(self.assert_valid_state("two"));
451	0	}
452
453	0	fn reserve_one(&mut self) {
454	0	let len = self.slots.len();
455	0
456	0	if len == self.capacity() {
457	0	if len == 0 {
458	0	let new_raw_cap = 8;
459	0	self.mask = 8 - 1;
460	0	self.indices = vec![None; new_raw_cap];
461	0	} else {
462	0	let raw_cap = self.indices.len();
463	0	self.grow(raw_cap << 1);
464	0	}
465	0	}
466	0	}
467
468		#[inline]
469	0	fn grow(&mut self, new_raw_cap: usize) {
470	0	// This path can never be reached when handling the first allocation in
471	0	// the map.
472	0
473	0	debug_assert!(self.assert_valid_state("top"));
474
475		// find first ideally placed element -- start of cluster
476	0	let mut first_ideal = 0;
477
478	0	for (i, pos) in self.indices.iter().enumerate() {
479	0	if let Some(pos) = *pos {
480	0	if 0 == probe_distance(self.mask, pos.hash, i) {
481	0	first_ideal = i;
482	0	break;
483	0	}
484	0	}
485		}
486
487		// visit the entries in an order where we can simply reinsert them
488		// into self.indices without any bucket stealing.
489	0	let old_indices = mem::replace(&mut self.indices, vec![None; new_raw_cap]);
490	0	self.mask = new_raw_cap.wrapping_sub(1);
491
492	0	for &pos in &old_indices[first_ideal..] {
493	0	self.reinsert_entry_in_order(pos);
494	0	}
495
496	0	for &pos in &old_indices[..first_ideal] {
497	0	self.reinsert_entry_in_order(pos);
498	0	}
499
500	0	debug_assert!(self.assert_valid_state("bottom"));
501	0	}
502
503	0	fn reinsert_entry_in_order(&mut self, pos: Option<Pos>) {
504	0	if let Some(pos) = pos {
505		// Find first empty bucket and insert there
506	0	let mut probe = desired_pos(self.mask, pos.hash);
507	0
508	0	probe_loop!(probe < self.indices.len(), {
509	0	if self.indices[probe].is_none() {
510		// empty bucket, insert here
511	0	self.indices[probe] = Some(pos);
512	0	return;
513	0	}
514	0
515	0	debug_assert!({
516	0	let them = self.indices[probe].unwrap();
517	0	let their_distance = probe_distance(self.mask, them.hash, probe);
518	0	let our_distance = probe_distance(self.mask, pos.hash, probe);
519	0
520	0	their_distance >= our_distance
521		});
522		});
523	0	}
524	0	}
525
526		#[cfg(not(test))]
527	0	fn assert_valid_state(&self, _: &'static str) -> bool {
528	0	true
529	0	}
530
531		#[cfg(test)]
532		fn assert_valid_state(&self, _msg: &'static str) -> bool {
533		/*
534		// Checks that the internal map structure is valid
535		//
536		// Ensure all hash codes in indices match the associated slot
537		for pos in &self.indices {
538		if let Some(pos) = *pos {
539		let real_idx = pos.index.wrapping_add(self.inserted);
540
541		if real_idx.wrapping_add(1) != 0 {
542		assert!(real_idx < self.slots.len(),
543		"out of index; real={}; len={}, msg={}",
544		real_idx, self.slots.len(), msg);
545
546		assert_eq!(pos.hash, self.slots[real_idx].hash,
547		"index hash does not match slot; msg={}", msg);
548		}
549		}
550		}
551
552		// Every index is only available once
553		for i in 0..self.indices.len() {
554		if self.indices[i].is_none() {
555		continue;
556		}
557
558		for j in i+1..self.indices.len() {
559		assert_ne!(self.indices[i], self.indices[j],
560		"duplicate indices; msg={}", msg);
561		}
562		}
563
564		for (index, slot) in self.slots.iter().enumerate() {
565		let mut indexed = None;
566
567		// First, see if the slot is indexed
568		for (i, pos) in self.indices.iter().enumerate() {
569		if let Some(pos) = *pos {
570		let real_idx = pos.index.wrapping_add(self.inserted);
571		if real_idx == index {
572		indexed = Some(i);
573		// Already know that there is no dup, so break
574		break;
575		}
576		}
577		}
578
579		if let Some(actual) = indexed {
580		// Ensure that it is accessible..
581		let desired = desired_pos(self.mask, slot.hash);
582		let mut probe = desired;
583		let mut dist = 0;
584
585		probe_loop!(probe < self.indices.len(), {
586		assert!(self.indices[probe].is_some(),
587		"unexpected empty slot; probe={}; hash={:?}; msg={}",
588		probe, slot.hash, msg);
589
590		let pos = self.indices[probe].unwrap();
591
592		let their_dist = probe_distance(self.mask, pos.hash, probe);
593		let real_idx = pos.index.wrapping_add(self.inserted);
594
595		if real_idx == index {
596		break;
597		}
598
599		assert!(dist <= their_dist,
600		"could not find entry; actual={}; desired={}" +
601		"probe={}, dist={}; their_dist={}; index={}; msg={}",
602		actual, desired, probe, dist, their_dist,
603		index.wrapping_sub(self.inserted), msg);
604
605		dist += 1;
606		});
607		} else {
608		// There is exactly one next link
609		let cnt = self.slots.iter().map(\|s\| s.next)
610		.filter(\|n\| *n == Some(index.wrapping_sub(self.inserted)))
611		.count();
612
613		assert_eq!(1, cnt, "more than one node pointing here; msg={}", msg);
614		}
615		}
616		*/
617
618		// TODO: Ensure linked lists are correct: no cycles, etc...
619
620		true
621		}
622		}
623
624		#[cfg(test)]
625		impl Table {
626		/// Returns the number of headers in the table
627		pub fn len(&self) -> usize {
628		self.slots.len()
629		}
630
631		/// Returns the table size
632		pub fn size(&self) -> usize {
633		self.size
634		}
635		}
636
637		impl Index {
638	0	fn new(v: Option<(usize, bool)>, e: Header) -> Index {
639	0	match v {
640	0	None => Index::NotIndexed(e),
641	0	Some((n, true)) => Index::Indexed(n, e),
642	0	Some((n, false)) => Index::Name(n, e),
643		}
644	0	}
645		}
646
647		#[inline]
648	0	fn usable_capacity(cap: usize) -> usize {
649	0	cap - cap / 4
650	0	}
651
652		#[inline]
653	0	fn to_raw_capacity(n: usize) -> usize {
654	0	n + n / 3
655	0	}
656
657		#[inline]
658	0	fn desired_pos(mask: usize, hash: HashValue) -> usize {
659	0	hash.0 & mask
660	0	}
661
662		#[inline]
663	0	fn probe_distance(mask: usize, hash: HashValue, current: usize) -> usize {
664	0	current.wrapping_sub(desired_pos(mask, hash)) & mask
665	0	}
666
667	0	fn hash_header(header: &Header) -> HashValue {
668		const MASK: u64 = (MAX_SIZE as u64) - 1;
669
670	0	let mut h = FnvHasher::default();
671	0	header.name().hash(&mut h);
672	0	HashValue((h.finish() & MASK) as usize)
673	0	}
674
675		/// Checks the static table for the header. If found, returns the index and a
676		/// boolean representing if the value matched as well.
677	0	fn index_static(header: &Header) -> Option<(usize, bool)> {
678	0	match *header {
679		Header::Field {
680	0	ref name,
681	0	ref value,
682	0	} => match *name {
683	0	header::ACCEPT_CHARSET => Some((15, false)),
684		header::ACCEPT_ENCODING => {
685	0	if value == "gzip, deflate" {
686	0	Some((16, true))
687		} else {
688	0	Some((16, false))
689		}
690		}
691	0	header::ACCEPT_LANGUAGE => Some((17, false)),
692	0	header::ACCEPT_RANGES => Some((18, false)),
693	0	header::ACCEPT => Some((19, false)),
694	0	header::ACCESS_CONTROL_ALLOW_ORIGIN => Some((20, false)),
695	0	header::AGE => Some((21, false)),
696	0	header::ALLOW => Some((22, false)),
697	0	header::AUTHORIZATION => Some((23, false)),
698	0	header::CACHE_CONTROL => Some((24, false)),
699	0	header::CONTENT_DISPOSITION => Some((25, false)),
700	0	header::CONTENT_ENCODING => Some((26, false)),
701	0	header::CONTENT_LANGUAGE => Some((27, false)),
702	0	header::CONTENT_LENGTH => Some((28, false)),
703	0	header::CONTENT_LOCATION => Some((29, false)),
704	0	header::CONTENT_RANGE => Some((30, false)),
705	0	header::CONTENT_TYPE => Some((31, false)),
706	0	header::COOKIE => Some((32, false)),
707	0	header::DATE => Some((33, false)),
708	0	header::ETAG => Some((34, false)),
709	0	header::EXPECT => Some((35, false)),
710	0	header::EXPIRES => Some((36, false)),
711	0	header::FROM => Some((37, false)),
712	0	header::HOST => Some((38, false)),
713	0	header::IF_MATCH => Some((39, false)),
714	0	header::IF_MODIFIED_SINCE => Some((40, false)),
715	0	header::IF_NONE_MATCH => Some((41, false)),
716	0	header::IF_RANGE => Some((42, false)),
717	0	header::IF_UNMODIFIED_SINCE => Some((43, false)),
718	0	header::LAST_MODIFIED => Some((44, false)),
719	0	header::LINK => Some((45, false)),
720	0	header::LOCATION => Some((46, false)),
721	0	header::MAX_FORWARDS => Some((47, false)),
722	0	header::PROXY_AUTHENTICATE => Some((48, false)),
723	0	header::PROXY_AUTHORIZATION => Some((49, false)),
724	0	header::RANGE => Some((50, false)),
725	0	header::REFERER => Some((51, false)),
726	0	header::REFRESH => Some((52, false)),
727	0	header::RETRY_AFTER => Some((53, false)),
728	0	header::SERVER => Some((54, false)),
729	0	header::SET_COOKIE => Some((55, false)),
730	0	header::STRICT_TRANSPORT_SECURITY => Some((56, false)),
731	0	header::TRANSFER_ENCODING => Some((57, false)),
732	0	header::USER_AGENT => Some((58, false)),
733	0	header::VARY => Some((59, false)),
734	0	header::VIA => Some((60, false)),
735	0	header::WWW_AUTHENTICATE => Some((61, false)),
736	0	_ => None,
737		},
738	0	Header::Authority(_) => Some((1, false)),
739	0	Header::Method(ref v) => match *v {
740	0	Method::GET => Some((2, true)),
741	0	Method::POST => Some((3, true)),
742	0	_ => Some((2, false)),
743		},
744	0	Header::Scheme(ref v) => match &**v {
745	0	"http" => Some((6, true)),
746	0	"https" => Some((7, true)),
747	0	_ => Some((6, false)),
748		},
749	0	Header::Path(ref v) => match &**v {
750	0	"/" => Some((4, true)),
751	0	"/index.html" => Some((5, true)),
752	0	_ => Some((4, false)),
753		},
754	0	Header::Protocol(..) => None,
755	0	Header::Status(ref v) => match u16::from(*v) {
756	0	200 => Some((8, true)),
757	0	204 => Some((9, true)),
758	0	206 => Some((10, true)),
759	0	304 => Some((11, true)),
760	0	400 => Some((12, true)),
761	0	404 => Some((13, true)),
762	0	500 => Some((14, true)),
763	0	_ => Some((8, false)),
764		},
765		}
766	0	}