as pointed out by @craigbarnes [0], using the latest fix for
the tombstone issue, it's possible to provoke a situation
that causes an endless loop when all free slots in the table
are filled up with tombstones and htab_find() is called.
therefore we need to account for those as well when deciding
if there's a need to call resize() so there's never more than
75% of the table used by either dead or live items.
the resize() serves as a rehash which gets rid of all deleted
entries, and it might cause the table size to shrink if
htab_insert() is called after a lot of items have been removed.
[0]: https://github.com/rofl0r/htab/issues/1#issuecomment-800094442
testcase:
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hsearch.h"
#define HTAB_OOM_TEST
#include "hsearch.c"
static char *xstrdup(const char *str)
{
char *dup = strdup(str);
assert(dup);
return dup;
}
void utoa(unsigned number, char* buffer) {
int lentest, len = 0, i, start = 0;
lentest = number;
do {
len++;
lentest /= 10;
} while(lentest);
buffer[start+len] = 0;
do {
i = number % 10;
buffer[start+len - 1] = '0' + i;
number -= i;
len -= 1;
number /= 10;
} while (number);
}
#define TESTSIZE 8
#define KEEP 1
static char* notorious[TESTSIZE];
static void prep() {
srand(0);
char buf[16];
size_t filled = 0;
while(filled < TESTSIZE) {
utoa(rand(), buf);
size_t idx = keyhash(buf) & (TESTSIZE-1);
if(!notorious[idx]) {
notorious[idx] = xstrdup(buf);
++filled;
}
}
}
int main(void)
{
struct htab *h = htab_create(TESTSIZE);
size_t i;
assert(h);
prep();
for(i=0; i<TESTSIZE; ++i) {
char *key = notorious[i];
printf("[%zu] = \"%s\"\n", i, key);
int r = htab_insert(h, key, HTV_N(42));
if(!r == 1) {
printf("element %zu couldn't be inserted\n", i);
break;
}
assert(r == 1);
// Ensure newly inserted entry can be found
assert(htab_find(h, key));
if(i >= KEEP) htab_delete(h, key);
}
htab_find(h, "looooop");
return 0;
}
we can't just set an item's key to zero and be done with a deletion,
because this will break the item search chain.
a deleted item requires a special marker, also known as tombstone.
when searching for an item, all slots with a tombstone need to treated
as if they were in use, but when inserting an item such a slot needs
to be filled with the new item.
a common procedure is to rehash the table when the number of deleted
items crosses a certain threshold, though for simplicity we leave this
task to the resize() function which does the same thing anyway when
the hashtable grows.
this allows to fix the issue quite elegantly and with almost no
additional overhead, so we don't penalize applications that do very
few deletions.
due to the usage of a hashmap to store headers, when relaying them
to the other side the order was not prevented.
even though correct from a standards point-of-view, this caused
issues with various programs, and it allows to fingerprint the use
of tinyproxy.
to implement this, i imported the MIT-licensed hsearch.[ch] from
https://github.com/rofl0r/htab which was originally taken from
musl libc. it's a simple and efficient hashtable implementation
with far better performance characteristic than the one previously
used by tinyproxy. additionally it has an API much more well-suited
for this purpose.
orderedmap.[ch] was implemented from scratch to address this issue.
behind the scenes it uses an sblist to store string values, and a htab
to store keys and the indices into the sblist.
this allows us to iterate linearly over the sblist and then find the
corresponding key in the hash table, so the headers can be reproduced
in the order they were received.
closes#73
rofl0r