Viewing file:  HeaderTable.h (13.16 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
/*
* Phusion Passenger - https://www.phusionpassenger.com/
* Copyright (c) 2014-2017 Phusion Holding B.V.
*
* "Passenger", "Phusion Passenger" and "Union Station" are registered
* trademarks of Phusion Holding B.V.
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
* THE SOFTWARE.
*/
#ifndef _PASSENGER_SERVER_KIT_HEADER_TABLE_H_
#define _PASSENGER_SERVER_KIT_HEADER_TABLE_H_
#include <boost/cstdint.hpp>
#include <cstring>
#include <cassert>
#include <DataStructures/LString.h>
#include <DataStructures/HashedStaticString.h>
#include <StaticString.h>
namespace Passenger {
namespace ServerKit {
using namespace std;
extern const HashedStaticString HTTP_COOKIE;
extern const HashedStaticString HTTP_SET_COOKIE;
struct Header {
/** Downcased version of the key, for case-insensitive lookup. */
LString key;
/** Original, unmodified key. */
LString origKey;
LString val;
boost::uint32_t hash;
};
/**
* A hash table, optimized for storing HTTP headers. It assumes the following workload:
*
* * Inserts happen in bulk, soon after hash table creation or clearing.
* * Once the bulk insertion phase is over, lookups are frequent, but modifications
* are not.
* * The hash table does not contain a lot of elements. Maybe 35 or so.
*
* The hash table uses open addressing and linear probing for cache friendliness. It
* supports keys that are non-contigunous in memory, through the use of LString.
*
* It supports at most 2^16-1 keys.
*
* The hash table automatically doubles in size when it becomes 75% full.
* The hash table never shrinks in size, even after clear(), unless you explicitly call
* compact(). This allows you to reuse hash table memory over multiple requests.
*
* This implementation is based on https://github.com/preshing/CompareIntegerMaps.
* See also http://preshing.com/20130107/this-hash-table-is-faster-than-a-judy-array
*/
class HeaderTable {
public:
#define PHT_FIRST_CELL(hash) (m_cells + ((hash) & (m_arraySize - 1)))
#define PHT_CIRCULAR_NEXT(c) ((c) + 1 != m_cells + m_arraySize ? (c) + 1 : m_cells)
#define PHT_CIRCULAR_OFFSET(a, b) ((b) >= (a) ? (b) - (a) : m_arraySize + (b) - (a))
static const unsigned int MAX_KEY_LENGTH = 65535;
static const unsigned int DEFAULT_SIZE = 64;
struct Cell {
Header *header;
};
private:
Cell *m_cells;
boost::uint16_t m_arraySize;
boost::uint16_t m_population;
bool shouldRepopulateOnInsert() const {
return (m_population + 1) * 4 >= m_arraySize * 3;
}
OXT_FORCE_INLINE
bool cellIsEmpty(const Cell * const cell) const {
return cell->header == NULL;
}
static boost::uint32_t upper_power_of_two(boost::uint32_t v) {
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
return v;
}
OXT_FORCE_INLINE
static bool isCookieHeader(const Header *header) {
return header->hash == HTTP_COOKIE.hash()
&& psg_lstr_cmp(&header->key, HTTP_COOKIE);
}
OXT_FORCE_INLINE
static bool isSetCookieHeader(const Header *header) {
return header->hash == HTTP_SET_COOKIE.hash()
&& psg_lstr_cmp(&header->key, HTTP_SET_COOKIE);
}
void repopulate(unsigned int desiredSize) {
assert((desiredSize & (desiredSize - 1)) == 0); // Must be a power of 2
assert(m_population * 4 <= desiredSize * 3);
// Get start/end pointers of old array
Cell *oldCells = m_cells;
Cell *end = m_cells + m_arraySize;
// Allocate new array
m_arraySize = desiredSize;
m_cells = new Cell[m_arraySize];
memset(m_cells, 0, sizeof(Cell) * m_arraySize);
if (oldCells == NULL) {
return;
}
// Iterate through old array
for (Cell *oldCell = oldCells; oldCell != end; oldCell++) {
if (!cellIsEmpty(oldCell)) {
// Insert this element into new array
Cell *newCell = PHT_FIRST_CELL(oldCell->header->hash);
while (true) {
if (cellIsEmpty(newCell)) {
// Insert here
*newCell = *oldCell;
break;
} else {
newCell = PHT_CIRCULAR_NEXT(newCell);
}
}
}
}
// Delete old array
delete[] oldCells;
}
void copyFrom(const HeaderTable &other) {
m_arraySize = other.m_arraySize;
m_population = other.m_population;
m_cells = new Cell[other.m_arraySize];
memcpy(m_cells, other.m_cells, other.m_arraySize * sizeof(Cell));
}
public:
HeaderTable(unsigned int initialSize = DEFAULT_SIZE)
{
init(initialSize);
}
HeaderTable(const HeaderTable &other) {
copyFrom(other);
}
~HeaderTable() {
delete[] m_cells;
}
HeaderTable &operator=(const HeaderTable &other) {
delete[] m_cells;
copyFrom(other);
return *this;
}
void init(unsigned int initialSize) {
assert((initialSize & (initialSize - 1)) == 0); // Must be a power of 2
m_arraySize = initialSize;
if (initialSize == 0) {
m_cells = NULL;
} else {
m_cells = new Cell[m_arraySize];
memset(m_cells, 0, sizeof(Cell) * m_arraySize);
}
m_population = 0;
}
const Cell *lookupCell(const HashedStaticString &key) const {
assert(!key.empty());
assert(key.size() < MAX_KEY_LENGTH);
if (m_cells == NULL) {
return NULL;
}
const Cell *cell = PHT_FIRST_CELL(key.hash());
while (true) {
if (cellIsEmpty(cell)) {
// Empty cell found.
return NULL;
} else if (psg_lstr_cmp(&cell->header->key, key)) {
// Non-empty cell found.
return cell;
} else {
// Keep probing.
cell = PHT_CIRCULAR_NEXT(cell);
}
}
}
OXT_FORCE_INLINE
Cell *lookupCell(const HashedStaticString &key) {
return const_cast<Cell *>(static_cast<const HeaderTable *>(this)->lookupCell(key));
}
OXT_FORCE_INLINE
Header *lookupHeader(const HashedStaticString &key) {
Cell *cell = lookupCell(key);
if (cell != NULL) {
return cell->header;
} else {
return NULL;
}
}
const LString *lookup(const HashedStaticString &key) const {
const Cell * const cell = lookupCell(key);
if (cell != NULL) {
return &cell->header->val;
} else {
return NULL;
}
}
OXT_FORCE_INLINE
LString *lookup(const HashedStaticString &key) {
return const_cast<LString *>(static_cast<const HeaderTable *>(this)->lookup(key));
}
/**
* HeaderTable takes over ownership of `header`. But you must ensure that the pool
* that the header was allocated from is not destroyed before the HeaderTable
* is destroyed or cleared.
*/
void insert(Header **headerPtr, psg_pool_t *pool) {
Header *header = *headerPtr;
assert(header->key.size < MAX_KEY_LENGTH);
if (m_cells == NULL) {
repopulate(DEFAULT_SIZE);
}
while (true) {
Cell *cell = PHT_FIRST_CELL(header->hash);
while (true) {
if (cellIsEmpty(cell)) {
// Cell is empty. Insert here.
if (shouldRepopulateOnInsert()) {
// Time to resize
repopulate(m_arraySize * 2);
break;
}
m_population++;
cell->header = header;
*headerPtr = NULL;
return;
} else if (psg_lstr_cmp(&cell->header->key, &header->key)) {
// Cell matches, so merge value into header.
if (isCookieHeader(header)) {
psg_lstr_append(&cell->header->val, pool, ";", 1);
} else if (isSetCookieHeader(header)) {
psg_lstr_append(&cell->header->val, pool, "\n", 1);
} else {
psg_lstr_append(&cell->header->val, pool, ",", 1);
}
psg_lstr_move_and_append(&header->val, pool,
&cell->header->val);
psg_lstr_deinit(&header->key);
psg_lstr_deinit(&header->origKey);
*headerPtr = NULL;
return;
} else {
cell = PHT_CIRCULAR_NEXT(cell);
}
}
}
}
Header *insert(psg_pool_t *pool, const StaticString &name,
const StaticString &value)
{
Header *header = (Header *) psg_palloc(pool, sizeof(Header));
char *downcasedName = (char *) psg_pnalloc(pool, name.size());
convertLowerCase((const unsigned char *) name.data(),
(unsigned char *) downcasedName, name.size());
psg_lstr_init(&header->key);
psg_lstr_append(&header->key, pool, downcasedName, name.size());
psg_lstr_init(&header->origKey);
psg_lstr_append(&header->origKey, pool, name.data(), name.size());
psg_lstr_init(&header->val);
psg_lstr_append(&header->val, pool, value.data(), value.size());
header->hash = HashedStaticString(downcasedName, name.size()).hash();
insert(&header, pool);
return header;
}
void erase(Cell *cell) {
assert(cell >= m_cells && cell - m_cells < m_arraySize);
assert(!cellIsEmpty(cell));
// Remove this cell by shuffling neighboring cells so there are no gaps in anyone's probe chain
Cell *neighbor = PHT_CIRCULAR_NEXT(cell);
while (true) {
if (cellIsEmpty(neighbor)) {
// There's no neighbor to move. Go ahead and clear this cell, then return.
if (cell->header != NULL) {
// A previous iteration in this loop
// could have made cell->header NULL.
psg_lstr_deinit(&cell->header->key);
psg_lstr_deinit(&cell->header->origKey);
psg_lstr_deinit(&cell->header->val);
cell->header = NULL;
}
m_population--;
return;
}
Cell *ideal = PHT_FIRST_CELL(neighbor->header->hash);
if (PHT_CIRCULAR_OFFSET(ideal, cell) < PHT_CIRCULAR_OFFSET(ideal, neighbor)) {
// Erase current cell and move neighbor into this position,
// then make the now-empty neighbor the new cell to remove.
if (cell->header != NULL) {
// A previous iteration in this loop
// could have made cell->header NULL.
psg_lstr_deinit(&cell->header->key);
psg_lstr_deinit(&cell->header->origKey);
psg_lstr_deinit(&cell->header->val);
}
*cell = *neighbor;
cell = neighbor;
neighbor->header = NULL;
}
neighbor = PHT_CIRCULAR_NEXT(neighbor);
}
}
void erase(const HashedStaticString &key) {
Cell *cell = lookupCell(key);
if (cell != NULL) {
erase(cell);
}
}
/** Does not resize the array. */
void clear() {
if (m_cells != NULL && m_population != 0) {
memset(m_cells, 0, sizeof(Cell) * m_arraySize);
}
m_population = 0;
}
void freeMemory() {
delete[] m_cells;
m_cells = NULL;
m_arraySize = 0;
m_population = 0;
}
void compact() {
repopulate(upper_power_of_two((m_population * 4 + 3) / 3));
}
unsigned int size() const {
return m_population;
}
unsigned int arraySize() const {
return m_arraySize;
}
void debug(psg_pool_t *pool) const {
for (unsigned int i = 0; i < m_arraySize; i++) {
int size = -1;
int ideal = -1;
unsigned int hash = 0;
const char *key = "";
if (!cellIsEmpty(&m_cells[i])) {
size = m_cells[i].header->key.size;
hash = m_cells[i].header->hash;
ideal = int(PHT_FIRST_CELL(m_cells[i].header->hash) - m_cells);
if (size > 0) {
const LString *str = psg_lstr_null_terminate(
&m_cells[i].header->key, pool);
key = str->start->data;
}
}
printf("%u: key=(%s), size=%d, hash=%u, ideal index=%u\n",
i, key, size, hash, ideal);
}
}
friend class Iterator;
class Iterator {
private:
HeaderTable *m_table;
Cell *m_cur;
public:
Iterator(HeaderTable &table)
: m_table(&table)
{
if (m_table->m_cells != NULL) {
m_cur = &m_table->m_cells[0];
if (m_table->cellIsEmpty(m_cur)) {
next();
}
} else {
m_cur = NULL;
}
}
Cell *next() {
if (m_cur == NULL) {
// Already finished.
return NULL;
}
Cell *end = m_table->m_cells + m_table->m_arraySize;
while (++m_cur != end) {
if (!m_table->cellIsEmpty(m_cur)) {
return m_cur;
}
}
// Finished
return m_cur = NULL;
}
OXT_FORCE_INLINE
Cell *operator*() const {
return m_cur;
}
OXT_FORCE_INLINE
Cell *operator->() const {
return m_cur;
}
};
friend class ConstIterator;
class ConstIterator {
private:
const HeaderTable *m_table;
const Cell *m_cur;
public:
ConstIterator(const HeaderTable &table)
: m_table(&table)
{
if (m_table->m_cells != NULL) {
m_cur = &m_table->m_cells[0];
if (m_table->cellIsEmpty(m_cur)) {
next();
}
} else {
m_cur = NULL;
}
}
const Cell *next() {
if (m_cur == NULL) {
// Already finished.
return NULL;
}
const Cell *end = m_table->m_cells + m_table->m_arraySize;
while (++m_cur != end) {
if (!m_table->cellIsEmpty(m_cur)) {
return m_cur;
}
}
// Finished
m_cur = NULL;
return NULL;
}
OXT_FORCE_INLINE
const Cell *operator*() const {
return m_cur;
}
OXT_FORCE_INLINE
const Cell *operator->() const {
return m_cur;
}
};
};
} // namespace ServerKit
} // namespace Passenger
#endif /* _PASSENGER_SERVER_KIT_HEADER_TABLE_H_ */
|