proxygen: proxygen::HeaderTable Class Reference

#include <HeaderTable.h>

Inheritance diagram for proxygen::HeaderTable:

Public Types
using	names_map = std::unordered_map< HPACKHeaderName, std::list< uint32_t >>

Public Member Functions
	HeaderTable (uint32_t capacityVal)

virtual	~HeaderTable ()

	HeaderTable (const HeaderTable &)=delete

HeaderTable &	operator= (const HeaderTable &)=delete

virtual bool	add (HPACKHeader header)

uint32_t	getIndex (const HPACKHeader &header) const

const HPACKHeader &	getHeader (uint32_t index) const

bool	isValid (uint32_t index) const

bool	hasName (const HPACKHeaderName &headerName)

const names_map &	names () const

uint32_t	nameIndex (const HPACKHeaderName &headerName) const

uint32_t	capacity () const

uint32_t	getMaxTableLength (uint32_t capacityVal)

virtual bool	setCapacity (uint32_t capacity)

uint32_t	size () const

uint32_t	bytes () const

size_t	length () const

bool	operator== (const HeaderTable &other) const

Static Public Member Functions
static uint32_t	toExternal (uint32_t head, uint32_t length, uint32_t internalIndex)

static uint32_t	toInternal (uint32_t head, uint32_t length, uint32_t externalIndex)

Protected Member Functions
void	init (uint32_t capacityVal)

virtual void	increaseTableLengthTo (uint32_t newLength)

virtual void	resizeTable (uint32_t newLength)

virtual void	updateResizedTable (uint32_t oldTail, uint32_t oldLength, uint32_t newLength)

virtual uint32_t	removeLast ()

void	reset ()

virtual uint32_t	evict (uint32_t needed, uint32_t desiredCapacity)

uint32_t	next (uint32_t i) const

uint32_t	tail () const

uint32_t	toExternal (uint32_t internalIndex) const

uint32_t	toInternal (uint32_t externalIndex) const

Protected Attributes
uint32_t	capacity_ {0}

uint32_t	bytes_ {0}

std::vector< HPACKHeader >	table_

uint32_t	size_ {0}

uint32_t	head_ {0}

names_map	names_

Private Member Functions
uint32_t	getIndexImpl (const HPACKHeaderName &header, const folly::fbstring &value, bool nameOnly) const

Detailed Description

Data structure for maintaining indexed headers, based on a fixed-length ring with FIFO semantics. Externally it acts as an array.

Definition at line 26 of file HeaderTable.h.

Member Typedef Documentation

using proxygen::HeaderTable::names_map = std::unordered_map<HPACKHeaderName, std::list<uint32_t>>

Definition at line 28 of file HeaderTable.h.

Constructor & Destructor Documentation

proxygen::HeaderTable::HeaderTable ( uint32_t capacityVal )

inlineexplicit

Definition at line 30 of file HeaderTable.h.

References init().

Referenced by ~HeaderTable().

                                              {
     init(capacityVal);
   }

virtual proxygen::HeaderTable::~HeaderTable ( )

inlinevirtual

Definition at line 34 of file HeaderTable.h.

References add(), getHeader(), getIndex(), hasName(), HeaderTable(), isValid(), operator=(), and uint32_t.

34 {}

proxygen::HeaderTable::HeaderTable ( const HeaderTable & )

delete

Member Function Documentation

bool proxygen::HeaderTable::add ( HPACKHeader header )

virtual

Add the header entry at the beginning of the table (index=1)

Returns: true if it was able to add the entry

Reimplemented in proxygen::QPACKHeaderTable.

Definition at line 33 of file HeaderTable.cpp.

References proxygen::HPACKHeader::bytes(), bytes_, capacity_, folly::chrono::ceil(), evict(), getMaxTableLength(), head_, increaseTableLengthTo(), length(), min, folly::gen::move, proxygen::HPACKHeader::name, names_, next(), reset(), size_, table_, and uint32_t.

Referenced by proxygen::QPACKHeaderTable::add(), proxygen::HPACKDecoder::decodeLiteralHeader(), proxygen::HPACKEncoder::encodeAsLiteral(), proxygen::HeaderTableTests::resizeAndFillTable(), proxygen::HPACKContext::seedHeaderTable(), proxygen::StaticHeaderTable::StaticHeaderTable(), proxygen::TEST_F(), and ~HeaderTable().

                                         {
   if (header.bytes() > capacity_) {
     // Per the RFC spec https://tools.ietf.org/html/rfc7541#page-11, we must
     // flush the underlying table if a request is made for a header that is
     // larger than the current table capacity
     reset();
     return false;
   }
 
   // Make the necessary room in the table if appropriate per RFC spec
   if ((bytes_ + header.bytes()) > capacity_) {
     if (evict(header.bytes(), capacity_) == 0) {
       return false;
     }
   }
 
   if (size_ == length()) {
     increaseTableLengthTo(std::min((uint32_t)ceil(size_ * 1.5),
                                    getMaxTableLength(capacity_)));
   }
   head_ = next(head_);
   // index name
   names_[header.name].push_back(head_);
   bytes_ += header.bytes();
   table_[head_] = std::move(header);
 
   ++size_;
   return true;
 }

uint32_t proxygen::HeaderTable::bytes ( ) const

inline

Returns: size in bytes, the sum of the size of all entries

Definition at line 112 of file HeaderTable.h.

References bytes_.

Referenced by proxygen::QPACKHeaderTable::add(), proxygen::QPACKContext::getBytesStored(), proxygen::HPACKContext::getBytesStored(), proxygen::operator<<(), operator==(), proxygen::HeaderTableTests::resizeAndFillTable(), proxygen::TEST_F(), and TEST_P().

                          {
     return bytes_;
   }

uint32_t proxygen::HeaderTable::capacity ( ) const

inline

Table capacity, or maximum number of bytes we can hold.

Definition at line 86 of file HeaderTable.h.

References capacity_, getMaxTableLength(), setCapacity(), and uint32_t.

Referenced by proxygen::HPACKEncoder::encode(), proxygen::QPACKEncoder::encode(), proxygen::HPACKEncoder::encodeAsLiteral(), proxygen::QPACKContext::getTableSize(), proxygen::HPACKContext::getTableSize(), proxygen::QPACKHeaderTable::isDraining(), proxygen::HPACKEncoderBase::setHeaderTableSize(), and proxygen::QPACKEncoder::shouldIndex().

                             {
     return capacity_;
   }

uint32_t proxygen::HeaderTable::evict	(	uint32_t	needed,
		uint32_t	desiredCapacity
	)

protectedvirtual

Evict entries to make space for the needed amount of bytes.

Reimplemented in proxygen::QPACKHeaderTable.

Definition at line 196 of file HeaderTable.cpp.

References bytes_, removeLast(), size_, and uint32_t.

Referenced by add(), proxygen::QPACKHeaderTable::evict(), length(), and setCapacity().

                                                                      {
   uint32_t previousSize = size_;
   while (size_ > 0 && (bytes_ + needed > desiredCapacity)) {
     removeLast();
   }
   return previousSize - size_;
 }

const HPACKHeader & proxygen::HeaderTable::getHeader ( uint32_t index ) const

Get the table entry at the given external index.

Returns: the header entry

Definition at line 93 of file HeaderTable.cpp.

References isValid(), table_, and toInternal().

Referenced by proxygen::QPACKContext::getHeader(), proxygen::HPACKContext::getHeader(), proxygen::operator<<(), proxygen::TEST_F(), and ~HeaderTable().

                                                               {
   CHECK(isValid(index));
   return table_[toInternal(index)];
 }

uint32_t proxygen::HeaderTable::getIndex ( const HPACKHeader & header ) const

Get the index of the given header, if found.

Returns: 0 in case the header is not found

Definition at line 63 of file HeaderTable.cpp.

References getIndexImpl(), proxygen::HPACKHeader::name, and proxygen::HPACKHeader::value.

Referenced by proxygen::QPACKEncoder::encodeHeaderQ(), proxygen::HPACKContext::getIndex(), proxygen::TEST_F(), and ~HeaderTable().

                                                               {
   return getIndexImpl(header.name, header.value, false);
 }

uint32_t proxygen::HeaderTable::getIndexImpl	(	const HPACKHeaderName &	header,
		const folly::fbstring &	value,
		bool	nameOnly
	)		const

private

Definition at line 67 of file HeaderTable.cpp.

References i, names_, table_, and toExternal().

Referenced by getIndex(), and nameIndex().

                                                         {
   auto it = names_.find(headerName);
   if (it == names_.end()) {
     return 0;
   }
   for (auto indexIt = it->second.rbegin(); indexIt != it->second.rend();
        ++indexIt) {
     auto i = *indexIt;
     if (nameOnly || table_[i].value == value) {
       return toExternal(i);
     }
   }
   return 0;
 }

uint32_t proxygen::HeaderTable::getMaxTableLength ( uint32_t capacityVal )

Returns the maximum table length required to support HPACK headers given the specified capacity bytes

Definition at line 98 of file HeaderTable.cpp.

Referenced by add(), capacity(), init(), setCapacity(), and proxygen::TEST_F().

                                                             {
   // At a minimum an entry will take 32 bytes
   // No need to add an extra slot; i.e. a capacity of 32 to 63 bytes can hold
   // at most one entry.
   return (capacityVal >> 5);
 }

bool proxygen::HeaderTable::hasName ( const HPACKHeaderName & headerName )

Returns: true if there is at least one header with the given name

Definition at line 84 of file HeaderTable.cpp.

References names_.

Referenced by proxygen::TEST_F(), and ~HeaderTable().

                                                            {
   return names_.find(headerName) != names_.end();
 }

void proxygen::HeaderTable::increaseTableLengthTo ( uint32_t newLength )

protectedvirtual

Reimplemented in proxygen::QPACKHeaderTable.

Definition at line 159 of file HeaderTable.cpp.

References head_, length(), names_, resizeTable(), size_, tail(), uint32_t, and updateResizedTable().

Referenced by add(), proxygen::QPACKHeaderTable::increaseTableLengthTo(), length(), and setCapacity().

                                                           {
   DCHECK_GE(newLength, length());
   uint32_t oldTail = (size_ > 0) ? tail() : 0;
   auto oldLength = length();
   resizeTable(newLength);
 
   // TODO: referenence to head here is incompatible with baseIndex
   if (size_ > 0 && oldTail > head_) {
     // the list wrapped around, need to move oldTail..oldLength to the end
     // of the now-larger table_
     updateResizedTable(oldTail, oldLength, newLength);
     // Update the names indecies that pointed to the old range
     for (auto& names_it: names_) {
       for (auto& idx: names_it.second) {
         if (idx >= oldTail) {
           DCHECK_LT(idx + (length() - oldLength), length());
           idx += (length() - oldLength);
         } else {
           // remaining indecies in the list were smaller than oldTail, so
           // should be indexed from 0
           break;
         }
       }
     }
   }
 }

void proxygen::HeaderTable::init ( uint32_t capacityVal )

protected

Initialize with a given capacity.

Definition at line 20 of file HeaderTable.cpp.

References bytes_, capacity_, getMaxTableLength(), head_, i, names_, size_, table_, and uint32_t.

Referenced by HeaderTable(), length(), and proxygen::StaticHeaderTable::StaticHeaderTable().

                                            {
   bytes_ = 0;
   size_ = 0;
   head_ = 0;
   capacity_ = capacityVal;
   uint32_t initLength = getMaxTableLength(capacity_) / 2;
   table_.reserve(initLength);
   for (uint32_t i = 0; i < initLength; i++) {
     table_.emplace_back();
   }
   names_.clear();
 }

bool proxygen::HeaderTable::isValid ( uint32_t index ) const

Checks if an external index is valid.

Definition at line 204 of file HeaderTable.cpp.

References proxygen::ERROR, and size_.

Referenced by getHeader(), proxygen::HPACKDecoder::isValid(), proxygen::QPACKDecoder::isValid(), proxygen::QPACKHeaderTable::isValid(), and ~HeaderTable().

                                               {
   bool result = false;
   result = 0 < index && index <= size_;
   if (!result) {
     LOG(ERROR) << "Invalid index=" << index << " size_=" << size_;
   }
   return result;
 }

size_t proxygen::HeaderTable::length ( ) const

inline

Returns: how many slots we have in the table

Definition at line 119 of file HeaderTable.h.

References evict(), i, increaseTableLengthTo(), init(), next(), operator==(), removeLast(), reset(), resizeTable(), table_, tail(), toExternal(), toInternal(), uint32_t, and updateResizedTable().

Referenced by add(), increaseTableLengthTo(), next(), setCapacity(), tail(), proxygen::TEST_F(), toExternal(), and toInternal().

                         {
     return table_.size();
   }

uint32_t proxygen::HeaderTable::nameIndex ( const HPACKHeaderName & headerName ) const

Get any index of a header that has the given name. From all the headers with the given name we pick the last one added to the header table, but the way we pick the header can be arbitrary.

Definition at line 88 of file HeaderTable.cpp.

References getIndexImpl(), and value.

Referenced by proxygen::QPACKEncoder::getNameIndexQ(), proxygen::HPACKContext::nameIndex(), names(), and proxygen::TEST_F().

                                                                        {
   folly::fbstring value;
   return getIndexImpl(headerName, value, true /* name only */);
 }

const names_map& proxygen::HeaderTable::names ( ) const

inline

Returns: the map holding the indexed names

Definition at line 72 of file HeaderTable.h.

References nameIndex(), names_, and uint32_t.

Referenced by proxygen::TEST_F().

                                  {
     return names_;
   }

uint32_t proxygen::HeaderTable::next ( uint32_t i ) const

protected

Move the index to the right.

Definition at line 213 of file HeaderTable.cpp.

References length().

Referenced by add(), proxygen::QPACKHeaderTable::canEvict(), and length().

                                            {
   return (i + 1) % length();
 }

HeaderTable& proxygen::HeaderTable::operator= ( const HeaderTable & )

delete

Referenced by ~HeaderTable().

bool proxygen::HeaderTable::operator== ( const HeaderTable & other ) const

Definition at line 244 of file HeaderTable.cpp.

References bytes(), and size().

Referenced by length().

                                                            {
   if (size() != other.size()) {
     return false;
   }
   if (bytes() != other.bytes()) {
     return false;
   }
   return true;
 }

uint32_t proxygen::HeaderTable::removeLast ( )

protectedvirtual

Removes one header entry from the beginning of the header table.

Returns the size of the removed header

Reimplemented in proxygen::QPACKHeaderTable.

Definition at line 105 of file HeaderTable.cpp.

References bytes_, name, names_, size_, folly::pushmi::detail::t, table_, tail(), and uint32_t.

Referenced by evict(), length(), and proxygen::QPACKHeaderTable::removeLast().

                                  {
   auto t = tail();
   // remove the first element from the names index
   auto names_it = names_.find(table_[t].name);
   DCHECK(names_it != names_.end());
   auto &ilist = names_it->second;
   DCHECK_EQ(ilist.front(), t);
   ilist.pop_front();
 
   // remove the name if there are no indices associated with it
   if (ilist.empty()) {
     names_.erase(names_it);
   }
   const auto& header = table_[t];
   uint32_t headerBytes = header.bytes();
   bytes_ -= headerBytes;
   VLOG(10) << "Removing local idx=" << t << " name=" << header.name
            << " value=" << header.value;
   --size_;
   return headerBytes;
 }

void proxygen::HeaderTable::reset ( )

protected

Empties the underlying header table

Definition at line 127 of file HeaderTable.cpp.

References bytes_, names_, and size_.

Referenced by add(), and length().

                         {
   names_.clear();
 
   bytes_ = 0;
   size_ = 0;
 
   // Capacity remains unchanged and for now we leave head_ index the same
 }

void proxygen::HeaderTable::resizeTable ( uint32_t newLength )

protectedvirtual

Reimplemented in proxygen::QPACKHeaderTable.

Definition at line 186 of file HeaderTable.cpp.

References table_.

Referenced by increaseTableLengthTo(), length(), and proxygen::QPACKHeaderTable::resizeTable().

                                                 {
   table_.resize(newLength);
 }

bool proxygen::HeaderTable::setCapacity ( uint32_t capacity )

virtual

Sets the current capacity of the header table, and evicts entries if needed. Returns false if eviction failed.

Reimplemented in proxygen::QPACKHeaderTable.

Definition at line 136 of file HeaderTable.cpp.

References bytes_, capacity_, evict(), getMaxTableLength(), increaseTableLengthTo(), length(), and uint32_t.

Referenced by capacity(), proxygen::HPACKDecoderBase::handleTableSizeUpdate(), proxygen::HeaderTableTests::resizeTable(), proxygen::QPACKHeaderTable::setCapacity(), proxygen::HPACKEncoderBase::setHeaderTableSize(), and proxygen::TEST_F().

                                                   {
   if (newCapacity == capacity_) {
     return true;
   } else if (newCapacity < capacity_) {
     // NOTE: currently no actual resizing is performed...
     evict(0, newCapacity);
     if (bytes_ > newCapacity) {
       // eviction failed!
       return false;
     }
   } else {
     // NOTE: due to the above lack of resizing, we must determine whether a
     // resize is actually appropriate (to handle cases where the underlying
     // vector is still >= to the size related to the new capacity requested)
     uint32_t newLength = getMaxTableLength(newCapacity) / 2;
     if (newLength > length()) {
       increaseTableLengthTo(newLength);
     }
   }
   capacity_ = newCapacity;
   return true;
 }

uint32_t proxygen::HeaderTable::size ( ) const

inline

Returns: number of valid entries

Definition at line 105 of file HeaderTable.h.

References size_.

Referenced by proxygen::QPACKHeaderTable::canEvict(), proxygen::HPACKContext::dynamicToGlobalIndex(), proxygen::QPACKContext::getHeadersStored(), proxygen::HPACKContext::getHeadersStored(), proxygen::HPACKContext::globalToDynamicIndex(), proxygen::HPACKContext::isStatic(), proxygen::operator<<(), operator==(), proxygen::QPACKHeaderTable::removeLast(), proxygen::HeaderTableTests::resizeAndFillTable(), proxygen::HeaderTableTests::resizeTable(), proxygen::StaticHeaderTable::StaticHeaderTable(), TEST_F(), proxygen::TEST_F(), and TEST_P().

                         {
     return size_;
   }

uint32_t proxygen::HeaderTable::tail ( ) const

protected

Get the index of the tail element of the table.

Definition at line 217 of file HeaderTable.cpp.

References head_, length(), and size_.

Referenced by proxygen::QPACKHeaderTable::canEvict(), increaseTableLengthTo(), proxygen::QPACKHeaderTable::increaseTableLengthTo(), length(), removeLast(), and proxygen::QPACKHeaderTable::removeLast().

                                  {
   // tail is private, and only called in the encoder, where head_ is always
   // valid
   DCHECK_GT(size_, 0) << "tail() undefined";
   return (head_ + length() - size_ + 1) % length();
 }

uint32_t proxygen::HeaderTable::toExternal	(	uint32_t	head,
		uint32_t	length,
		uint32_t	internalIndex
	)

static

Static versions of the methods that translate indices.

Definition at line 228 of file HeaderTable.cpp.

Referenced by proxygen::QPACKHeaderTable::getIndexImpl(), getIndexImpl(), proxygen::QPACKHeaderTable::internalToAbsolute(), length(), and toExternal().

                                                          {
   return ((head + length - internalIndex) % length) + 1;
 }

uint32_t proxygen::HeaderTable::toExternal ( uint32_t internalIndex ) const

protected

Translate internal index to external one, including a static version.

Definition at line 224 of file HeaderTable.cpp.

References head_, length(), and toExternal().

                                                              {
   return toExternal(head_, length(), internalIndex);
 }

uint32_t proxygen::HeaderTable::toInternal	(	uint32_t	head,
		uint32_t	length,
		uint32_t	externalIndex
	)

static

Definition at line 237 of file HeaderTable.cpp.

References length().

Referenced by getHeader(), length(), toInternal(), and proxygen::QPACKHeaderTable::toInternal().

                                                          {
   // remove the offset
   --externalIndex;
   return (head + length - externalIndex) % length;
 }

uint32_t proxygen::HeaderTable::toInternal ( uint32_t externalIndex ) const

protected

Translate external index to internal one.

Definition at line 233 of file HeaderTable.cpp.

References head_, length(), and toInternal().

                                                              {
   return toInternal(head_, length(), externalIndex);
 }

void proxygen::HeaderTable::updateResizedTable	(	uint32_t	oldTail,
		uint32_t	oldLength,
		uint32_t	newLength
	)

protectedvirtual

Reimplemented in proxygen::QPACKHeaderTable.

Definition at line 190 of file HeaderTable.cpp.

References table_.

Referenced by increaseTableLengthTo(), length(), and proxygen::QPACKHeaderTable::updateResizedTable().

                                                          {
   std::move_backward(table_.begin() + oldTail, table_.begin() + oldLength,
                      table_.begin() + newLength);
 }