/* This file is part of vmod_dict.
Copyright (C) 2017 Sergey Poznyakoff
Vmod_dict is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.
Vmod_dict is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with vmod_dict. If not, see .
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include "vcl.h"
#include "vrt.h"
#include "vas.h"
#include "cache/cache.h"
#include "vcc_if.h"
struct entry
{
char *key;
char *val;
size_t hash;
struct entry *next, *prev;
};
static struct entry *ent_head, *ent_tail;
static size_t ent_count;
static void
entry_append(struct entry *ent)
{
ent->next = NULL;
ent->prev = ent_tail;
if (ent_tail)
ent_tail->next = ent;
else
ent_head = ent;
ent_tail = ent;
ent_count++;
}
static void
entry_remove(struct entry *ent)
{
struct entry *p;
if ((p = ent->prev) != NULL)
p->next = ent->next;
else
ent_head = ent->next;
if ((p = ent->next) != NULL)
p->prev = ent->prev;
else
ent_tail = ent->prev;
ent_count--;
free(ent);
}
static size_t hash_size;
static struct entry **hash_table;
static size_t max_hash_size = 8192;
static ssize_t max_coll = -1; /* Max. number of collisions allowed */
typedef struct {
size_t readers;
size_t writer;
pthread_mutex_t mutex;
pthread_cond_t lock_free;
} locker_t;
static locker_t rwlock;
static void
locker_init(locker_t *rdwr)
{
rdwr->readers = 0;
rdwr->writer = 0;
pthread_mutex_init(&rdwr->mutex, NULL);
pthread_cond_init(&rdwr->lock_free, NULL);
}
static void
locker_rlock(locker_t *rdwr)
{
pthread_mutex_lock(&rdwr->mutex);
while (rdwr->writer)
pthread_cond_wait(&rdwr->lock_free, &rdwr->mutex);
rdwr->readers++;
pthread_mutex_unlock(&rdwr->mutex);
}
static void
locker_wlock(locker_t *rdwr)
{
pthread_mutex_lock(&rdwr->mutex);
while (rdwr->writer || rdwr->readers)
pthread_cond_wait(&rdwr->lock_free, &rdwr->mutex);
rdwr->writer++;
pthread_mutex_unlock(&rdwr->mutex);
}
static int
locker_runlock(locker_t *rdwr)
{
pthread_mutex_lock(&rdwr->mutex);
if (rdwr->readers == 0) {
pthread_mutex_unlock(&rdwr->mutex);
return -1;
} else {
rdwr->readers--;
if (rdwr->readers == 0)
pthread_cond_signal(&rdwr->lock_free);
pthread_mutex_unlock(&rdwr->mutex);
return 0;
}
}
static int
locker_wunlock(locker_t *rdwr)
{
pthread_mutex_lock(&rdwr->mutex);
if (rdwr->writer == 0) {
pthread_mutex_unlock(&rdwr->mutex);
return -1;
} else {
rdwr->writer = 0;
pthread_cond_signal(&rdwr->lock_free);
pthread_mutex_unlock(&rdwr->mutex);
return 0;
}
}
static int cs_coll[] = {
0, 1, 2, 3, 4, 5, 6, 7,
8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23,
24, 25, 26, 27, 28, 29, 30, 31,
32, 33, 34, 35, 36, 37, 38, 39,
40, 41, 42, 43, 44, 45, 46, 47,
48, 49, 50, 51, 52, 53, 54, 55,
56, 57, 58, 59, 60, 61, 62, 63,
64, 65, 66, 67, 68, 69, 70, 71,
72, 73, 74, 75, 76, 77, 78, 79,
80, 81, 82, 83, 84, 85, 86, 87,
88, 89, 90, 91, 92, 93, 94, 95,
96, 97, 98, 99, 100, 101, 102, 103,
104, 105, 106, 107, 108, 109, 110, 111,
112, 113, 114, 115, 116, 117, 118, 119,
120, 121, 122, 123, 124, 125, 126, 127,
128, 129, 130, 131, 132, 133, 134, 135,
136, 137, 138, 139, 140, 141, 142, 143,
144, 145, 146, 147, 148, 149, 150, 151,
152, 153, 154, 155, 156, 157, 158, 159,
160, 161, 162, 163, 164, 165, 166, 167,
168, 169, 170, 171, 172, 173, 174, 175,
176, 177, 178, 179, 180, 181, 182, 183,
184, 185, 186, 187, 188, 189, 190, 191,
192, 193, 194, 195, 196, 197, 198, 199,
200, 201, 202, 203, 204, 205, 206, 207,
208, 209, 210, 211, 212, 213, 214, 215,
216, 217, 218, 219, 220, 221, 222, 223,
224, 225, 226, 227, 228, 229, 230, 231,
232, 233, 234, 235, 236, 237, 238, 239,
240, 241, 242, 243, 244, 245, 246, 247,
248, 249, 250, 251, 252, 253, 254, 255
};
static int ci_coll[] = {
0, 1, 2, 3, 4, 5, 6, 7,
8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23,
24, 25, 26, 27, 28, 29, 30, 31,
32, 33, 34, 35, 36, 37, 38, 39,
40, 41, 42, 43, 44, 45, 46, 47,
48, 49, 50, 51, 52, 53, 54, 55,
56, 57, 58, 59, 60, 61, 62, 63,
64, 97, 98, 99, 100, 101, 102, 103,
104, 105, 106, 107, 108, 109, 110, 111,
112, 113, 114, 115, 116, 117, 118, 119,
120, 121, 122, 91, 92, 93, 94, 95,
96, 97, 98, 99, 100, 101, 102, 103,
104, 105, 106, 107, 108, 109, 110, 111,
112, 113, 114, 115, 116, 117, 118, 119,
120, 121, 122, 123, 124, 125, 126, 127,
128, 129, 130, 131, 132, 133, 134, 135,
136, 137, 138, 139, 140, 141, 142, 143,
144, 145, 146, 147, 148, 149, 150, 151,
152, 153, 154, 155, 156, 157, 158, 159,
160, 161, 162, 163, 164, 165, 166, 167,
168, 169, 170, 171, 172, 173, 174, 175,
176, 177, 178, 179, 180, 181, 182, 183,
184, 185, 186, 187, 188, 189, 190, 191,
192, 193, 194, 195, 196, 197, 198, 199,
200, 201, 202, 203, 204, 205, 206, 207,
208, 209, 210, 211, 212, 213, 214, 215,
216, 217, 218, 219, 220, 221, 222, 223,
224, 225, 226, 227, 228, 229, 230, 231,
232, 233, 234, 235, 236, 237, 238, 239,
240, 241, 242, 243, 244, 245, 246, 247,
248, 249, 250, 251, 252, 253, 254, 255
};
static int *collation = cs_coll;
static inline int
collate(char i)
{
return collation[(unsigned char)i];
}
#define SIZE_T_MAX ((size_t)-1)
static inline size_t
rotl(size_t x, int n)
{
return ((x << n) | (x >> ((CHAR_BIT * sizeof x) - n))) & SIZE_T_MAX;
}
static size_t
string_hash(const char *str)
{
size_t value = 0;
unsigned char ch;
while ((ch = *str++))
value = collate(ch) + rotl(value, 7);
return value;
}
static inline int
chareq(int a, int b)
{
return collate(a) == collate(b);
}
static int
streq(const char *a, const char *b)
{
while (*a) {
if (!(*b && chareq(*a, *b)))
return 0;
a++;
b++;
}
return *b ? 0 : 1;
}
static ssize_t
my_getline(FILE *fp, char **pstr, size_t *psize)
{
char *str;
size_t size;
size_t n;
int c;
if (!pstr || !psize) {
errno = EINVAL;
return -1;
}
str = *pstr;
size = *psize;
if (!str || size == 0) {
/* Initial allocation */
size = 16;
str = malloc(size);
if (!str)
return -1;
*pstr = str;
*psize = size;
}
n = 0;
while ((c = getc(fp)) != EOF) {
if (n == size) {
char *p;
size_t sz;
if (size >= (size_t) -1 / 3 * 2) {
errno = ENOMEM;
return -1;
}
sz = size + (size + 1) / 2;
p = realloc(str, sz);
if (!p)
return -1;
*pstr = str = p;
*psize = size = sz;
}
str[n++] = c;
if (c == '\n')
break;
}
if (n == size) {
char *p = realloc(str, size + 1);
if (!p)
return -1;
*pstr = str = p;
*psize = ++size;
}
str[n] = 0;
return n;
}
static inline int
isws(int c)
{
return c == ' ' || c == '\t' || c == '\r' || c == '\n';
}
static void
load_entries(char const *file)
{
FILE *fp;
ssize_t n;
char *buf = NULL;
size_t size = 0;
unsigned line;
char *p, *val;
size_t l;
struct entry *ent;
fp = fopen(file, "r");
if (!fp) {
syslog(LOG_DAEMON|LOG_ERR,
"dict.init: can't load \"%s\": %s",
file, strerror(errno));
abort();
}
line = 0;
while ((n = my_getline(fp, &buf, &size)) > 0) {
line++;
while (n > 0 && isws(buf[n-1]))
n--;
buf[n] = 0;
for (p = buf; isws(*p); p++, n--)
;
if (n == 0 || *p == '#')
continue;
l = strcspn(p, " \t");
p[l] = 0;
if (l == n) {
syslog(LOG_DAEMON|LOG_ERR,
"%s:%u: malformed line", file, line);
continue;
}
val = p + l + 1;
while (*val == ' ' || *val == '\t')
val++;
ent = malloc(sizeof *ent + l + strlen(val) + 2);
AN(ent);
ent->key = (char*)(ent + 1);
ent->val = ent->key + l + 1;
strcpy(ent->key, p);
strcpy(ent->val, val);
ent->hash = string_hash(ent->key);
entry_append(ent);
}
free(buf);
assert(n != -1);
fclose(fp);
}
static void
rehash(void)
{
struct entry *ent;
for (ent = ent_head; ent; ent = ent->next)
ent->hash = string_hash(ent->key);
}
static void
fill_table(void)
{
struct entry *ent;
size_t next_size;
next_size = ent_count * 2 + 1;
if (next_size > max_hash_size)
max_hash_size = next_size;
do {
size_t cn = 0;
size_t hs;
hash_size = next_size;
hs = sizeof(hash_table[0]) * hash_size;
hash_table = realloc(hash_table, hs);
AN(hash_table);
memset(hash_table, 0, hs);
for (ent = ent_head; ent; ent = ent->next) {
size_t h = ent->hash % hash_size;
size_t i = h;
size_t n = 0;
while (hash_table[i]) {
if (streq(hash_table[i]->key, ent->key)) {
entry_remove(hash_table[i]);
break;
}
i = (i + 1) % hash_size;
assert(i != h);
n++;
}
if (n > cn) cn = n;
hash_table[i] = ent;
}
if (max_coll <= 0 || cn < max_coll)
break;
next_size = next_size * 2 + 1;
} while (next_size < max_hash_size);
}
int
dict_event(VRT_CTX, struct vmod_priv *priv, enum vcl_event_e e)
{
switch (e) {
case VCL_EVENT_LOAD:
locker_init(&rwlock);
break;
case VCL_EVENT_DISCARD:
locker_wlock(&rwlock);
while (ent_head)
entry_remove(ent_head);
free(hash_table);
hash_table = NULL;
hash_size = 0;
locker_wunlock(&rwlock);
break;
case VCL_EVENT_WARM:
case VCL_EVENT_COLD:
break;
}
return 0;
}
VCL_VOID
vmod_ci(VRT_CTX, VCL_BOOL ci)
{
int *cp;
locker_wlock(&rwlock);
cp = ci ? ci_coll : cs_coll;
if (cp != collation) {
collation = cp;
rehash();
fill_table();
}
locker_wunlock(&rwlock);
}
VCL_VOID
vmod_collisions(VRT_CTX, VCL_INT coll)
{
max_coll = coll;
}
VCL_VOID
vmod_load(VRT_CTX, VCL_STRING file)
{
locker_wlock(&rwlock);
load_entries(file);
fill_table();
locker_wunlock(&rwlock);
}
VCL_VOID
vmod_clear(VRT_CTX)
{
size_t i;
locker_wlock(&rwlock);
for (i = 0; i < hash_size; i++)
hash_table[i] = NULL;
while (ent_head)
entry_remove(ent_head);
locker_wunlock(&rwlock);
}
static char const *
lookup_unlocked(char const *key)
{
size_t i, h;
char const *s = NULL;
if (hash_size == 0)
return NULL;
h = string_hash(key) % hash_size;
i = h;
while (hash_table[i]) {
if (streq(hash_table[i]->key, key)) {
s = hash_table[i]->val;
break;
}
i = (i + 1) % hash_size;
if (i == h)
break;
}
return s;
}
VCL_STRING
vmod_lookup(VRT_CTX, VCL_STRING key)
{
char *s = NULL;
if (key) {
locker_rlock(&rwlock);
char const *p = lookup_unlocked(key);
if (p) {
s = WS_Copy(ctx->ws, p, -1);
AN(s);
}
locker_runlock(&rwlock);
}
return s;
}