From d7399e572e334fb036c7f6b59400f5075147054c Mon Sep 17 00:00:00 2001 From: Sergey Poznyakoff Date: Tue, 1 Aug 2017 11:22:27 +0300 Subject: Initial commit --- src/.gitignore | 4 + src/Makefile.am | 56 +++++++++ src/vmod_dict.c | 352 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/vmod_dict.vcc | 37 ++++++ 4 files changed, 449 insertions(+) create mode 100644 src/.gitignore create mode 100644 src/Makefile.am create mode 100644 src/vmod_dict.c create mode 100644 src/vmod_dict.vcc (limited to 'src') diff --git a/src/.gitignore b/src/.gitignore new file mode 100644 index 0000000..1b6a341 --- /dev/null +++ b/src/.gitignore @@ -0,0 +1,4 @@ +vcc_if.c +vcc_if.h +*.rst +vmod_dict.3 diff --git a/src/Makefile.am b/src/Makefile.am new file mode 100644 index 0000000..bff41f5 --- /dev/null +++ b/src/Makefile.am @@ -0,0 +1,56 @@ +# 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 . + +AM_CPPFLAGS=\ + $(VARNISHAPI_CFLAGS)\ + -DLOCALSTATEDIR=\"$(localstatedir)\" + +vmoddir = $(VMODDIR) +vmod_LTLIBRARIES = libvmod_dict.la + +libvmod_dict_la_LDFLAGS=-module -export-dynamic -avoid-version +libvmod_dict_la_LIBADD= + +libvmod_dict_la_SOURCES = \ + vmod_dict.c + +nodist_libvmod_dict_la_SOURCES = \ + vcc_if.c vcc_if.h + +vmod_dict.lo: vcc_if.h + +CLEANFILES = vcc_if.c vcc_if.h *.rst + +vmodtoolargs = --strict +vccfile = $(top_srcdir)/src/vmod_dict.vcc + +vcc_if.c vcc_if.h: $(vccfile) + $(AM_V_GEN)$(PYTHON) $(VARNISHAPI_VMODTOOL) $(vmodtoolargs) $(vccfile) + +EXTRA_DIST = \ + vmod_dict.vcc\ + vmod_dict.man.rst\ + vmod_dict.rst + +dist_man_MANS=vmod_dict.3 + +DISTCLEANFILES=vmod_dict.3 + +vmod_dict.3: vmod_dict.man.rst + @$(abs_top_srcdir)/build-aux/missing rst2man.py \ + vmod_dict.man.rst > vmod_dict.3 + + diff --git a/src/vmod_dict.c b/src/vmod_dict.c new file mode 100644 index 0000000..03d116f --- /dev/null +++ b/src/vmod_dict.c @@ -0,0 +1,352 @@ +/* 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 "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; +}; + +static struct entry *ent_head, *ent_tail; +static size_t ent_count; + +static size_t hash_size; +static struct entry const **hash_table; +static size_t max_hash_size = 8192; + +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) { + fprintf(stderr, + "lookup.init: can't load \"%s\": %s\n", + file, strerror(errno)); + } + 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) { + fprintf(stderr, "%s:%u: malformed line\n", 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); + ent->next = NULL; + if (ent_tail) + ent_tail->next = ent; + else + ent_head = ent; + ent_tail = ent; + ent_count++; + } + assert(n != -1); + fclose(fp); +} + +VCL_VOID +vmod_load(VRT_CTX, VCL_STRING file, VCL_BOOL ci, VCL_INT coll) +{ + struct entry *ent; + size_t next_size; + + collation = ci ? ci_coll : cs_coll; + + load_entries(file); + + next_size = ent_count * 2; + if (ent_count < 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]) { + i = (i + 1) % hash_size; + assert(i != h); + n++; + } + + if (n > cn) cn = n; + hash_table[i] = ent; + } + + if (coll <= 0 || cn < coll) + break; + + next_size *= 2; + } while (next_size < max_hash_size); +} + +VCL_STRING +vmod_lookup(VRT_CTX, VCL_STRING key) +{ + if (key) { + size_t i, h; + + h = string_hash(key) % hash_size; + i = h; + while (hash_table[i]) { + if (streq(hash_table[i]->key, key)) { + char *s = WS_Copy(ctx->ws, hash_table[i]->val, + -1); + AN(s); + return s; + } + i = (i + 1) % hash_size; + if (i == h) + break; + } + } + return NULL; +} + diff --git a/src/vmod_dict.vcc b/src/vmod_dict.vcc new file mode 100644 index 0000000..76c4267 --- /dev/null +++ b/src/vmod_dict.vcc @@ -0,0 +1,37 @@ +$Module dict 3 Dictionary look-up for Varnish Cache + +DESCRIPTION +=========== + +Provides simple key/value dictionary API. The dictionary is kept in +a disk file. Each non-empty line in such a file is either a comment +or a pair of keyword - value separated by one or more whitespace characters. +Leading and trailing whitespace is discarded. Comments are introduced by a +hash sign at the beginning of the line. Empty lines and comments are ignored. + +$Function VOID load(STRING file, BOOL ci, INT ncls) + +Description + Loads key/value dictionary from **file** into memory. The **ci** + parameter controls whether key lookups should be case-insensitive. + The **ncls** parameter, if positive, gives the maximum allowable length + of collision chain in the hash table. The module will adjust the hash + load factor to ensure thes number of collisions doesn't exceed this + value. + + This function is normally called from **vcl_init**. + +$Function STRING lookup(STRING key) + +Description + Looks up the **key** in the table loaded by the **dict.load**. + Returns the value if found, or **NULL** otherwise. + +COPYRIGHT +========= + +| Copyright (C) Sergey Poznyakoff +| License GPLv3+: GNU GPL version 3 or later +| +| This is free software: you are free to change and redistribute it. +| There is NO WARRANTY, to the extent permitted by law. -- cgit v1.2.1