summaryrefslogtreecommitdiffabout
authorSergey Poznyakoff <gray@gnu.org.ua>2016-01-26 13:39:51 (GMT)
committer Sergey Poznyakoff <gray@gnu.org.ua>2016-02-08 14:57:32 (GMT)
commitde9ac8a2fde1fc940909ce73888c8792d893c193 (patch) (side-by-side diff)
tree0a495878f61ad84e96ca78fd5aa7ecea79415b14
parent67731a160cc7c3e090236316af459f695593fc55 (diff)
downloadvmod-tbf-de9ac8a2fde1fc940909ce73888c8792d893c193.tar.gz
vmod-tbf-de9ac8a2fde1fc940909ce73888c8792d893c193.tar.bz2
Keep TBF data in a binary tree instead of DBM database (port 6ea9edf0).
* configure.ac: Don't check for libdb. * src/tbf.c: Rewrite using binary tree. * src/vmod_tbf.vcc (open, close, sync): Remove. (rate, check): Add PRIV_VCL argument. (debug,dump,gc,set_gc_interval): New functions. * tests/test00.vtc: Remove calls to tbf.open/close * tests/test01.vtc: Likewise. * tests/test02.vtc: Likewise. * tests/test03.vtc: Likewise. * NEWS: Document changes. * src/vmod-tbf.3: Likewise.
Diffstat (more/less context) (ignore whitespace changes)
-rw-r--r--NEWS2
-rw-r--r--src/tbf.c743
-rw-r--r--src/vmod-tbf.390
-rw-r--r--src/vmod_tbf.vcc13
-rw-r--r--tests/test00.vti6
-rw-r--r--tests/test01.vtc6
-rw-r--r--tests/test02.vti6
-rw-r--r--tests/test03.vtc6
8 files changed, 394 insertions, 478 deletions
diff --git a/NEWS b/NEWS
index b87dafa..234d374 100644
--- a/NEWS
+++ b/NEWS
@@ -1,4 +1,4 @@
-vmod-tbf -- history of user-visible changes. 2014-11-13
+vmod-tbf -- history of user-visible changes. 2016-02-08
Copyright (C) 2013-2014 Sergey Poznyakoff
See the end of file for copying conditions.
diff --git a/src/tbf.c b/src/tbf.c
index dadb9cc..bbcbaa8 100644
--- a/src/tbf.c
+++ b/src/tbf.c
@@ -15,9 +15,15 @@
along with vmod-tbf. If not, see <http://www.gnu.org/licenses/>.
*/
#include "tbf.h"
-#include <db.h>
+#include "vsha256.h"
-static int debug_level;
+#ifndef USEC_PER_SEC
+# define USEC_PER_SEC 1000000L
+#endif
+
+#define DEBUG 1
+static unsigned gc_interval = 3600;
+static int debug_level = 0;
static void
debugprt(const char *fmt, ...)
@@ -28,352 +34,233 @@ debugprt(const char *fmt, ...)
va_end(ap);
}
#define debug(n,c) do { if (debug_level>=(n)) debugprt c; } while (0)
+
+enum { CHILD_LEFT, CHILD_RIGHT };
-#ifndef USEC_PER_SEC
-# define USEC_PER_SEC 1000000L
+struct node {
+ uint8_t key[SHA256_LEN];
+#ifdef DEBUG
+ char *keystr;
#endif
-
-#define DEFDBNAME "tbf.bdb"
-#define DEFOPENPARAMS "truncate"
-#define DBFILEMODE 0640
-
-static char *dbdir;
-static char *dbname;
-static DB_ENV *dbenv;
-static DB *db;
-static uint64_t autosync_max;
-static uint64_t autosync_count;
-static int tbf_disabled;
-
-static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
-
-
-/* The keylock structure serializes accesses to each db record, ensuring
- that no other thread could modify the data between calls to get and
- put */
-
-struct keylock {
- char *key; /* Key string */
- unsigned refcnt; /* Reference count */
- pthread_mutex_t mutex;
- VTAILQ_ENTRY(keylock) list;
+ struct node *parent;
+ struct node *child[2];
+ struct node *prev, *next;
+ pthread_cond_t notbusy;
+ int busy;
+ uint64_t timestamp; /* microseconds since epoch */
+ size_t tokens; /* tokens available */
};
-/* Keylock_head keeps a list of active (i.e. used by at least one thread)
- keylocks. Keylock_avail keeps a list of available threads, to avoid
- unnecessary memory allocations/frees. */
-static VTAILQ_HEAD(, keylock) keylock_head, keylock_avail;
-
-/* Find and return a keylock corresponding to the given key. If not found,
- create it, either by getting an unused entry from keylock_avail or by
- allocating a new one. */
-static struct keylock *
-keylock_find(const char *key)
+struct tree
{
- struct keylock *kp;
-
- VTAILQ_FOREACH(kp, &keylock_head, list) {
- if (strcmp(kp->key, key) == 0) {
- kp->refcnt++;
- return kp;
- }
- }
+ /* Root node of the tree */
+ struct node *root;
+ /* All nodes are linked in a LRU fashion, head pointing to
+ the most recently used, and tail to the last recently used
+ ones. */
+ struct node *head, *tail;
+ pthread_mutex_t mutex;
+};
+
+/* Linked list management */
- if (VTAILQ_FIRST(&keylock_avail)) {
- kp = VTAILQ_FIRST(&keylock_avail);
- VTAILQ_REMOVE(&keylock_avail, kp, list);
+/* Link NODE after REF in TREE. If REF is NULL, link at head */
+static void
+lru_link_node(struct tree *tree, struct node *node, struct node *ref)
+{
+ if (!ref) {
+ node->prev = NULL;
+ node->next = tree->head;
+ if (tree->head)
+ tree->head->prev = node;
+ else
+ tree->tail = node;
+ tree->head = node;
} else {
- kp = malloc(sizeof(*kp));
- AN(kp);
- pthread_mutex_init(&kp->mutex, NULL);
+ struct node *x;
+
+ node->prev = ref;
+ if ((x = ref->next))
+ x->prev = node;
+ else
+ tree->tail = node;
+ ref->next = node;
}
- kp->key = strdup(key);
- AN(kp->key);
- kp->refcnt = 1;
- VTAILQ_INSERT_TAIL(&keylock_head, kp, list);
- return kp;
}
-/* Thread-safe version of the above. */
-static struct keylock *
-keylock_find_safe(const char *key)
+static void
+lru_unlink_node(struct tree *tree, struct node *node)
{
- struct keylock *kp;
- pthread_mutex_lock(&mutex);
- kp = keylock_find(key);
- pthread_mutex_unlock(&mutex);
- return kp;
+ struct node *x;
+
+ debug(1,("UNLINK %p %p\n", node, node->prev, node->next));
+
+ if ((x = node->prev))
+ x->next = node->next;
+ else
+ tree->head = node->next;
+ if ((x = node->next))
+ x->prev = node->prev;
+ else
+ tree->tail = node->prev;
+ node->prev = node->next = NULL;
+}
+
+static int
+keycmp(uint8_t *a, uint8_t *b)
+{
+ return memcmp(a, b, SHA256_LEN);
}
-/* Remove keylock from keylock_head and attach it to keylock_avail for
- eventual future use. */
static void
-keylock_remove_safe(struct keylock *kp)
+keycpy(uint8_t *a, uint8_t *b)
{
- pthread_mutex_lock(&mutex);
- free(kp->key);
- kp->key = NULL;
- VTAILQ_REMOVE(&keylock_head, kp, list);
- VTAILQ_INSERT_TAIL(&keylock_avail, kp, list);
- pthread_mutex_unlock(&mutex);
+ memcpy(a, b, SHA256_LEN);
}
-
+
static void
-tbf_set_db_dir(const char *dir)
+key_create(char const *input, uint8_t key[])
{
- if (dbdir)
- free(dbdir);
- dbdir = strdup(dir);
- AN(dbdir);
+ struct SHA256Context ctx;
+ SHA256_Init(&ctx);
+ SHA256_Update(&ctx, input, strlen (input));
+ SHA256_Final(key, &ctx);
}
-struct param_kw {
- char *pkw_str;
- int pkw_len;
- int pkw_tok;
-};
-
-enum {
- PKW_TRUNCATE,
- PKW_MODE,
- PKW_SYNC,
- PKW_DEBUG,
- PKW_DBNAME
-};
-
-static struct param_kw param_kw_tab[] = {
-#define S(s) #s, sizeof(#s)-1
- { S(truncate), PKW_TRUNCATE },
- { S(trunc), PKW_TRUNCATE },
- { S(mode=), PKW_MODE },
- { S(sync=), PKW_SYNC },
- { S(debug=), PKW_DEBUG },
- { S(dbname=), PKW_DBNAME },
- { NULL }
-#undef S
-};
-
static void
-tbf_open(const char *params)
+node_lock(struct tree *tree, struct node *node)
{
- int rc;
- int filemode = DBFILEMODE;
- uint64_t n;
- char *p;
- struct stat st;
- int truncate = 0;
-
- if (!dbdir) {
- dbdir = strdup(LOCALSTATEDIR "/vmod-tbf");
- AN(dbdir);
- }
- if (!dbname) {
- dbname = strdup(DEFDBNAME);
- AN(dbname);
+ if (node->busy) {
+ pthread_cond_wait(&node->notbusy, &tree->mutex);
+ node->busy = 1;
}
-
- while (*params) {
- struct param_kw *pkw;
-
- for (pkw = param_kw_tab; pkw->pkw_str; pkw++) {
- if (strncmp(params, pkw->pkw_str, pkw->pkw_len) == 0)
- break;
- }
-
- if (!pkw->pkw_str) {
- syslog(LOG_DAEMON|LOG_ERR, "invalid keyword %s", params);
- break;
- }
-
- params += pkw->pkw_len;
-
- switch (pkw->pkw_tok) {
- case PKW_TRUNCATE:
- truncate = 1;
- break;
-
- case PKW_MODE:
- errno = 0;
- n = strtoul(params, &p, 8);
- if (errno || (n & ~0777) || !(*p == 0 || *p == ';')) {
- syslog(LOG_DAEMON|LOG_ERR,
- "invalid file mode near %s", p);
- params += strlen(params);
- } else {
- filemode = n;
- params = p;
- }
- break;
-
- case PKW_SYNC:
- errno = 0;
- n = strtoul(params, &p, 10);
- if (errno || !(*p == 0 || *p == ';')) {
- syslog(LOG_DAEMON|LOG_ERR,
- "invalid count near %s", p);
- params += strlen(params);
- } else {
- autosync_max = n;
- autosync_count = 0;
- params = p;
- }
- break;
-
- case PKW_DEBUG:
- errno = 0;
- n = strtoul(params, &p, 10);
- if (errno || !(*p == 0 || *p == ';')) {
- syslog(LOG_DAEMON|LOG_ERR,
- "invalid debug level near %s", p);
- params += strlen(params);
- } else {
- debug_level = n;
- params = p;
- }
- break;
+}
- case PKW_DBNAME:
- if (dbname)
- free(dbname);
- n = strcspn(params, ";");
- dbname = malloc(n + 1);
- AN(dbname);
- memcpy(dbname, params, n);
- dbname[n] = 0;
- params += n;
- break;
- }
+static void
+node_unlock(struct node *node)
+{
+ node->busy = 0;
+ pthread_cond_broadcast(&node->notbusy);
+}
+
+enum node_lookup_result {
+ NODE_FOUND,
+ NODE_NEW
+};
- if (*params == 0)
- break;
- else if (*params == ';')
- params++;
- else {
- syslog(LOG_DAEMON|LOG_ERR,
- "expected ';' near %s", params);
- break;
- }
- }
+static int
+tree_lookup_node(struct tree *tree, uint8_t key[], struct node **ret)
+{
+ int res;
+ struct node *node, *parent = NULL;
+ struct node **nodeptr;
- debug(1, ("opening database %s/%s", dbdir, dbname));
-
- if (rc = db_env_create(&dbenv, 0)) {
- syslog(LOG_DAEMON|LOG_ERR, "cannot create db environment: %s",
- db_strerror(rc));
- return;
- }
+ pthread_mutex_lock(&tree->mutex);
- if (stat(dbdir, &st)) {
- if (errno == ENOENT) {
- if (mkdir(dbdir,
- filemode | 0100 |
- ((filemode & 0060) ? 0010 : 0) |
- ((filemode & 0006) ? 0001 : 0))) {
- syslog(LOG_DAEMON|LOG_ERR,
- "cannot create db environment directory %s: %m",
- dbdir);
- }
- } else {
- syslog(LOG_DAEMON|LOG_ERR,
- "cannot stat db environment directory %s: %m",
- dbdir);
- return;
- }
- } else if (!S_ISDIR(st.st_mode)) {
- syslog(LOG_DAEMON|LOG_ERR, "%s is not a directory",
- dbdir);
- return;
- }
-
- rc = dbenv->open(dbenv, dbdir,
- DB_THREAD | DB_CREATE | DB_INIT_MPOOL | DB_INIT_CDB,
- 0);
- if (rc) {
- syslog(LOG_DAEMON|LOG_ERR, "cannot open db environment %s: %s",
- dbdir, db_strerror(rc));
- tbf_disabled = 1;
- return;
- }
-
- rc = db_create(&db, dbenv, 0);
- if (rc) {
- syslog(LOG_DAEMON|LOG_ERR, "cannot create db struct");
- return;
+ nodeptr = &tree->root;
+ while ((node = *nodeptr) != NULL) {
+ res = keycmp(key, node->key);
+ if (res == 0)
+ break;
+ parent = node;
+ nodeptr = &node->child[res > 0];
}
- rc = db->open(db, NULL, dbname, NULL, DB_HASH,
- DB_THREAD | DB_CREATE, filemode);
- if (rc) {
- syslog(LOG_DAEMON|LOG_ERR, "cannot open database %s: %s",
- dbname, db_strerror (rc));
- db->close(db, 0);
- db = NULL;
- dbenv->close(dbenv, 0);
- dbenv = NULL;
- tbf_disabled = 1;
+ if (node) {
+ node_lock(tree, node);
+ lru_unlink_node(tree, node);
+ res = NODE_FOUND;
+ } else {
+ node = calloc(1, sizeof(*node));
+ AN(node);
+ node->parent = parent;
+ keycpy(node->key, key);
+ pthread_cond_init(&node->notbusy, NULL);
+ node->busy = 1;
+ *nodeptr = node;
+ debug(2, ("%x: allocated new node %p", pthread_self(), node));
+ res = NODE_NEW;
}
-
- if (truncate) {
- rc = db->truncate(db, NULL, NULL, 0);
- if (rc)
- syslog(LOG_DAEMON|LOG_WARNING,
- "failed to truncate database %s: %s",
- dbname, db_strerror(rc));
- }
-}
-
-static DB *
-tbf_open_safe(const char *params)
-{
- if (tbf_disabled)
- return NULL;
- pthread_mutex_lock(&mutex);
- if (!db)
- tbf_open(params ? params : DEFOPENPARAMS);
- pthread_mutex_unlock(&mutex);
- return db;
-}
-
-int
-tbf_init(struct vmod_priv *priv, const struct VCL_conf *vclconf)
-{
- VTAILQ_INIT(&keylock_head);
- VTAILQ_INIT(&keylock_avail);
+ lru_link_node(tree, node, NULL);
+ *ret = node;
+ pthread_mutex_unlock(&tree->mutex);
+// debug(0, ("head: %p, root: %p", tree->head, tree->root));
+ return res;
}
-void
-vmod_open(MOD_CTX ctx, const char *dir, const char *params)
+static void
+node_free(struct node *node)
{
- if (db) {
- syslog(LOG_DAEMON|LOG_ERR, "tbf.open called twice");
- return;
- }
- tbf_set_db_dir(dir);
- tbf_open_safe(params);
+#ifdef DEBUG
+ free(node->keystr);
+#endif
+ pthread_cond_destroy(&node->notbusy);
+ free(node);
}
-void
-vmod_close(MOD_CTX ctx)
+static void
+tree_delete_node_unlocked(struct tree *tree, struct node *node)
{
- pthread_mutex_lock(&mutex);
- if (db) {
- debug(1, ("closing database %s", dbname));
- db->close(db, 0);
- db = NULL;
- dbenv->close(dbenv, 0);
- dbenv = NULL;
- tbf_disabled = 0;
+ struct node *parent = node->parent;
+ struct node **slot;
+
+ if (!parent)
+ slot = &tree->root;
+ else if (node == parent->child[CHILD_LEFT])
+ slot = &parent->child[CHILD_LEFT];
+ else
+ slot = &parent->child[CHILD_RIGHT];
+
+ if (!node->child[CHILD_LEFT]) {
+ /* No left subtree: link the right subtree to the parent slot */
+ *slot = node->child[CHILD_RIGHT];
+ if (node->child[CHILD_RIGHT])
+ node->child[CHILD_RIGHT]->parent = parent;
+ } else if (!node->child[CHILD_RIGHT]) {
+ /* No right subtree: link the left subtree to the parent slot */
+ *slot = node->child[CHILD_LEFT];
+ if (node->child[CHILD_LEFT])
+ node->child[CHILD_LEFT]->parent = parent;
+ } else {
+ /* Node has both subtrees. Find the largest value in the
+ right subtree */
+ struct node *p;
+ for (p = node->child[CHILD_LEFT]; p->child[CHILD_RIGHT];
+ p = p->child[CHILD_RIGHT])
+ ;
+
+ p->child[CHILD_RIGHT] = node->child[CHILD_RIGHT];
+ p->child[CHILD_RIGHT]->parent = p;
+
+ *slot = node->child[CHILD_LEFT];
+ node->child[CHILD_LEFT]->parent = parent;
}
- pthread_mutex_unlock(&mutex);
+ lru_unlink_node(tree, node);
}
+/* Dispose of tree nodes that were last accessed TIMEOUT seconds ago or
+ earlier */
void
-vmod_sync(MOD_CTX ctx)
+tree_gc(struct tree *tree, time_t timeout)
{
- if (db) {
- debug(1, ("synchronizing database"));
- db->sync(db, 0);
+ struct node *p;
+ uint64_t t;
+
+ pthread_mutex_lock(&tree->mutex);
+ t = (uint64_t) (time(NULL) - timeout) * USEC_PER_SEC;
+ debug(1,("gc till %"PRIu64, t));
+ while ((p = tree->tail) && p->timestamp < t) {
+#ifdef DEBUG
+ debug(1,("deleting %s", tree->tail->keystr));
+ debug(1,("%p %p %p\n", tree->head, tree->tail, tree->tail->prev));
+#endif
+ node_lock(tree, p);
+ tree_delete_node_unlocked(tree, p);
+ node_unlock(p);
+ node_free(p);
+ debug(1,("%p %p\n", tree->head, tree->tail));
}
+ pthread_mutex_unlock(&tree->mutex);
}
/* Algorithm:
@@ -395,149 +282,167 @@ vmod_sync(MOD_CTX ctx)
arrived for BURST_SIZE*INTERVAL or more microseconds.
*/
-struct tbf_bucket {
- uint64_t timestamp; /* microseconds since epoch */
- size_t tokens; /* tokens available */
-};
-
int
-tbf_proc(MOD_CTX ctx, DB *db, const char *key, int cost,
+tbf_proc(struct tree *tree, const char *keystr, int cost,
unsigned long interval, int burst_size)
{
- DBT keydat, content;
+ uint8_t key[SHA256_LEN];
+ struct node *node = NULL;
struct timeval tv;
uint64_t now;
uint64_t elapsed;
uint64_t tokens;
- struct tbf_bucket *bkt, init_bkt;
- int rc, res;
+ int res;
- memset(&keydat, 0, sizeof keydat);
- keydat.data = (void*) key;
- keydat.size = strlen(key);
+ key_create(keystr, key);
gettimeofday(&tv, NULL);
now = (uint64_t) tv.tv_sec * USEC_PER_SEC + (uint64_t)tv.tv_usec;
- memset(&content, 0, sizeof content);
- content.flags = DB_DBT_MALLOC;
- rc = db->get(db, NULL, &keydat, &content, 0);
- switch (rc) {
- case 0:
- bkt = (struct tbf_bucket *) content.data;
+ switch (tree_lookup_node(tree, key, &node)) {
+ case NODE_FOUND:
/* calculate elapsed time and number of new tokens since
last add */;
- elapsed = now - bkt->timestamp;
+ elapsed = now - node->timestamp;
tokens = elapsed / interval; /* partial tokens ignored */
/* timestamp set to time of most recent token */
- bkt->timestamp += tokens * interval;
+ node->timestamp += tokens * interval;
/* add existing tokens to 64bit counter to prevent overflow
in range check */
- tokens += bkt->tokens;
+ tokens += node->tokens;
if (tokens >= burst_size)
- bkt->tokens = burst_size;
+ node->tokens = burst_size;
else
- bkt->tokens = (size_t)tokens;
+ node->tokens = (size_t)tokens;
- debug(2, ("found, elapsed time: %"PRIu64" us, "
+ debug(2, ("%x: found, elapsed time: %"PRIu64" us, "
"new tokens: %"PRIu64", total: %lu ",
- elapsed, tokens, (unsigned long) bkt->tokens));
+ pthread_self(),
+ elapsed, tokens, (unsigned long) node->tokens));
break;
- case DB_NOTFOUND:
+ case NODE_NEW:
/* Initialize the structure */
- init_bkt.timestamp = now;
- init_bkt.tokens = burst_size;
- bkt = &init_bkt;
- break;
-
- default:
- syslog(LOG_DAEMON|LOG_ERR, "cannot fetch data %s: %s",
- key, db_strerror(rc));
- return false;
+#ifdef DEBUG
+ node->keystr = strdup(keystr);
+#endif
+ node->timestamp = now;
+ node->tokens = burst_size;
}
- if (cost <= bkt->tokens) {
+ if (cost <= node->tokens) {
res = 1;
- bkt->tokens -= cost;
- debug(2, ("tbf_rate matched %s, tokens left %lu", key,
- (unsigned long)bkt->tokens));
+ node->tokens -= cost;
+ debug(2, ("%x: tbf_rate matched %s, tokens left %lu",
+ pthread_self(), keystr,
+ (unsigned long) node->tokens));
} else {
res = 0;
- debug(1, ("tbf_rate overlimit on %s", key));
+ debug(1, ("%x: tbf_rate overlimit on %s",
+ pthread_self(), keystr));
}
+ node_unlock(node);
+ debug(1, ("tbf_proc: return"));
+ return res;
+}
- /* Update the db */
- content.data = (void*) bkt;
- content.size = sizeof(*bkt);
+struct tree *
+tree_create(void)
+{
+ struct tree *tree = calloc(1, sizeof(*tree));
+ AN(tree);
+ pthread_mutex_init(&tree->mutex, NULL);
+ return tree;
+}
- rc = db->put(db, NULL, &keydat, &content, 0);
- if (rc) {
- syslog(LOG_DAEMON|LOG_ERR, "error updating key %s: %s",
- key, db_strerror(rc));
+void
+tree_free(void *data)
+{
+ struct tree *tree = data;
+ struct node *p;
+
+ pthread_mutex_lock(&tree->mutex);
+ while ((p = tree->tail)) {
+ node_lock(tree, p);
+ lru_unlink_node(tree, p);
+ node_unlock(p);
+ node_free(p);
}
+ pthread_mutex_unlock(&tree->mutex);
+ pthread_mutex_destroy(&tree->mutex);
+ free(tree);
+}
+
+int
+tbf_init(struct vmod_priv *priv, const struct VCL_conf *vclconf)
+{
+ priv->priv = tree_create();
+ priv->free = tree_free;
+}
- if (bkt != &init_bkt)
- free(bkt);
+struct tree *
+get_tree(struct vmod_priv *priv)
+{
+ return priv->priv;
+}
- if (autosync_max && ++autosync_count >= autosync_max) {
- debug(1, ("synchronizing database"));
- db->sync(db, 0);
- autosync_count = 0;
- }
-
- return res;
+VCL_VOID
+vmod_debug(MOD_CTX ctx, VCL_INT newval)
+{
+ debug_level = newval;
+}
+
+VCL_VOID
+vmod_set_gc_interval(MOD_CTX ctx, VCL_REAL interval)
+{
+ gc_interval = interval;
+}
+
+VCL_VOID
+vmod_gc(MOD_CTX ctx, struct vmod_priv *priv, VCL_REAL interval)
+{
+ tree_gc(get_tree(priv), interval);
}
VCL_BOOL
-vmod_rate(MOD_CTX ctx, VCL_STRING key, VCL_INT cost, VCL_REAL t,
+vmod_rate(MOD_CTX ctx, struct vmod_priv *priv,
+ VCL_STRING key, VCL_INT cost, VCL_REAL t,
VCL_INT burst_size)
{
+ struct tree *tree = get_tree(priv);
unsigned long interval = t * USEC_PER_SEC;
- int rc;
- debug(2, ("entering rate(%s,%d,%g,%d)", key, cost, t, burst_size));
+ debug(2, ("%x: entering rate(%s,%d,%g,%d)",
+ pthread_self(), key, cost, t, burst_size));
if (interval == 0 || burst_size == 0)
return false;
+ tree_gc(tree, gc_interval);
+
if (!cost) {
- /* cost free, so don't waste time on database access */
+ /* cost free, so don't waste time on tree lookup */
return true;
}
if (cost > burst_size) {
/* impossibly expensive, so don't waste time on
- database access */
+ tree lookup */
return false;
}
- db = tbf_open_safe(NULL);
- if (db) {
- struct keylock *kp;
-
- kp = keylock_find_safe(key);
- debug(2, ("found key %s, ref %u", key, kp->refcnt));
- AZ(pthread_mutex_lock(&kp->mutex));
- rc = tbf_proc(ctx, db, key, cost, interval, burst_size);
- if (--kp->refcnt == 0)
- keylock_remove_safe(kp);
- AZ(pthread_mutex_unlock(&kp->mutex));
- } else
- rc = false;
-
- return rc;
+ return tbf_proc(tree, key, cost, interval, burst_size);
}
#define ISWS(c) ((c)==' '||(c)=='\t')
VCL_BOOL
-vmod_check(MOD_CTX ctx, VCL_STRING key, VCL_STRING spec)
+vmod_check(MOD_CTX ctx, struct vmod_priv *priv,
+ VCL_STRING key, VCL_STRING spec)
{
- double t, v, n;
+ double v, n;
char *p;
#define SKIPWS(init) for (init; *spec && ISWS(*spec); spec++)
- int burst;
errno = 0;
v = strtod(spec, &p);
@@ -593,5 +498,71 @@ vmod_check(MOD_CTX ctx, VCL_STRING key, VCL_STRING spec)
syslog(LOG_DAEMON|LOG_WARNING, "garbage after rate spec: %s",
spec);
- return vmod_rate(ctx, key, 1, n/v, v/n+1);
+ return vmod_rate(ctx, priv, key, 1, n/v, v/n+1);
+}
+
+static char xdig[] = "0123456789abcdef";
+
+static void
+key_to_str(uint8_t key[], char *buf)
+{
+ size_t i;
+
+ for (i = 0; i < SHA256_LEN; i++) {
+ *buf++ = xdig[key[i] >> 4];
+ *buf++ = xdig[key[i] & 0xf];
+ }
+ *buf = 0;
+}
+
+static void
+node_to_keystr(struct node *node, char *buf)
+{
+ if (node)
+ key_to_str(node->key, buf);
+ else
+ *buf = 0;
+}
+
+VCL_VOID
+vmod_dump(MOD_CTX ctx, struct vmod_priv *priv, VCL_STRING file)
+{
+ struct tree *tree = get_tree(priv);
+ struct node *node;
+ char keybuf[3][2*SHA256_LEN+1];
+ FILE *fp;
+ int err = 0;
+
+ fp = fopen(file, "w");
+ if (!fp) {
+ syslog(LOG_DAEMON|LOG_ERR,
+ "tbf.dump: can't open file %s for output: %m", file);
+ return;
+ }
+ pthread_mutex_lock(&tree->mutex);
+ if (tree->root) {
+ node_to_keystr(tree->root, keybuf[0]);
+ fprintf(fp, "%s\n", keybuf[0]);
+ }
+ for (node = tree->head; node; node = node->next) {
+ node_to_keystr(node, keybuf[0]);
+ node_to_keystr(node->child[CHILD_LEFT], keybuf[1]);
+ node_to_keystr(node->child[CHILD_RIGHT], keybuf[2]);
+#ifdef DEBUG
+ fprintf(fp, "# %s\n", node->keystr);
+#endif
+ fprintf(fp, "%s:%s:%s:%"PRIu64":%lu\n",
+ keybuf[0], keybuf[1], keybuf[2],
+ node->timestamp, (unsigned long)node->tokens);
+ if (ferror(fp)) {
+ syslog(LOG_DAEMON|LOG_ERR,
+ "tbf.dump: error writing to %s: %m", file);
+ err = 1;
+ break;
+ }
+ }
+ pthread_mutex_unlock(&tree->mutex);
+ fclose(fp);
+ if (err)
+ unlink(file);
}
diff --git a/src/vmod-tbf.3 b/src/vmod-tbf.3
index 03d7daf..08ffb43 100644
--- a/src/vmod-tbf.3
+++ b/src/vmod-tbf.3
@@ -13,20 +13,24 @@
.\"
.\" You should have received a copy of the GNU General Public License
.\" along with vmod-tbf. If not, see <http://www.gnu.org/licenses/>.
-.TH VMOD-TBF 1 "November 13, 2014" "VMOD-TBF" "User Reference"
+.TH VMOD-TBF 1 "January 26, 2016" "VMOD-TBF" "User Reference"
.SH NAME
vmod-tbf \- token bucket filtering for Varnish
.SH SYNOPSIS
.B import tbf;
-.BI "VOID tbf.open(STRING " dbdir ", STRING " params ");"
-
-.B VOID tbf.close();
-
.BI "BOOL tbf.rate(STRING " key ", INT " COST ", DURATION " interval ", INT " burst_size ");"
.BI "BOOL tbf.check(STRING " key ", STRING " rate ");"
+.BI "VOID tbf.debug(INT " level ");"
+
+.BI "VOID tbf.dump(STRING " file ");"
+
+.BI "VOID tbf.gc(DURATION " interval ");"
+
+.BI "VOID tbf.set_gc_interval(DURATION " interval ");"
+
.BI "REAL tbf.getla(INT " sample ");"
.BI "INT tbf.systime();"
@@ -119,62 +123,26 @@ sub vcl_recv {
.EE
.SS Storage
.PP
-Buckets are kept in a Berkeley database file. The \fBtbf.open\fR function
-controls its location and permissions. The \fBdbdir\fR argument
-supplies the full pathname to the directory where the database is
-located. The \fBparams\fR argument is a semicolon separated list of
-the following parameters:
-.TP
-.BI dbname= NAME
-Sets the name of the database file. Default is \fBtbf.bdb\fR.
-.TP
-.BR truncate " or " trunc
-Truncate the database if it already exists.
-.TP
-.BI mode= OCT
-Set the file mode. \fIOCT\fR is an octal number. The default file
-mode is \fB640\fR. Note that this parameter takes effect only when
-creating the file. If the database file already exists by the time
-\fBtbf.open\fR is called, its mode will not be altered.
-.TP
-.BI sync= N
-Synchronize the database with the disk after each \fBN\fR writes.
-.TP
-.BI debug= N
-Set debugging level.
-.PP
-Normally, this function should be called only once, from the
-\fBvcl_init\fR subroutine:
-.PP
-.EX
-sub vcl_init {
- tbf.open("/var/run/varnish/tbf.db", "mode=600");
-}
-.EE
-.PP
-Note that the directory where the database file is located must be
-writable for the user \fBVarnish\fR runs as.
-.PP
-Unless the \fBtbf.open\fR function was called, both \fBtbf.rate\fR and
-\fBtbf.check\fR will attempt to use the database located in
-\fIlocalstatedir\fB/vmod-tbf\fR, where \fIlocalstatedir\fR is the
-directory for modifiable single-machine data, which is set when
-configuring the package (e.g. \fB/var/run\fR or the like).
-.PP
-If the database directory does not exist, \fBtbf.open\fR will attempt
-to create it, deducing its mode from the database file mode (see the
-\fBmode=\fR parameter above) by setting executable
-bit in each triplet that has read or write bit set (e.g. \fB640\fR
-will become \fB750\fR).
-.PP
-The \fBtbf.close\fR function flushes the data and closes the database.
-It is normally called from the \fBvcl_fini\fR subroutine:
-.PP
-.EX
-sub vcl_fini {
- tbf.close();
-}
-.EE
+Buckets are kept in a binary tree structure, indexed by the key value.
+In order to prevent stale data from accumulating in the memory,
+garbage collection is run periodically. During garbage collection,
+all buckets that have not been accessed more than predefined amount of
+time are removed from the tree and disposed of. The default interval
+is 1 hour. It can be configured using the
+.B tbf.set_gc_interval
+function.
+.PP
+Garbage collection can also be triggered explicitly, using the
+.B tbf.gc
+function with the interval as its argument.
+.PP
+The function
+.B tbf.dump
+dumps entire tree to the disk file.
+.PP
+The function
+.B tbf.debug
+sets the debug level.
.SS Other functions
.PP
Several functions are provided that do not exactly belong to the
diff --git a/src/vmod_tbf.vcc b/src/vmod_tbf.vcc
index bb03d44..43609b7 100644
--- a/src/vmod_tbf.vcc
+++ b/src/vmod_tbf.vcc
@@ -24,12 +24,13 @@ For a detailed documentation, please see vmod-tbf(3) manual page.
DESCRIPTION
===========
-$Init tbf_init
-$Function VOID open(STRING, STRING)
-$Function VOID close()
-$Function VOID sync()
-$Function BOOL rate(STRING, INT, DURATION, INT)
-$Function BOOL check(STRING, STRING)
+$Event tbf_event
+$Function VOID debug(INT)
+$Function VOID dump(PRIV_VCL, STRING)
+$Function VOID gc(PRIV_VCL, DURATION)
+$Function VOID set_gc_interval(DURATION)
+$Function BOOL rate(PRIV_VCL, STRING, INT, DURATION, INT)
+$Function BOOL check(PRIV_VCL, STRING, STRING)
$Function REAL getla(INT)
$Function INT systime()
$Function STRING strftime(STRING, INT)
diff --git a/tests/test00.vti b/tests/test00.vti
index 53b9049..6d3e24e 100644
--- a/tests/test00.vti
+++ b/tests/test00.vti
@@ -23,12 +23,6 @@ server s1 {
varnish v1 -vcl+backend {
import tbf from "${vmod_topbuild}/src/.libs/libvmod_tbf.so";
- sub vcl_init {
- tbf.open("${vmod_topbuild}/tests/tbf", "truncate");
- }
- sub vcl_fini {
- tbf.close();
- }
sub vcl_recv {
if (!tbf.rate("url:"+req.url, 1, 20 s, 5)) {
#VARNISH3# error 420 "Overlimit";
diff --git a/tests/test01.vtc b/tests/test01.vtc
index da11d2b..ba7fd10 100644
--- a/tests/test01.vtc
+++ b/tests/test01.vtc
@@ -23,12 +23,6 @@ server s1 {
varnish v1 -vcl+backend {
import tbf from "${vmod_topbuild}/src/.libs/libvmod_tbf.so";
- sub vcl_init {
- tbf.open("${vmod_topbuild}/tests/tbf", "trunc");
- }
- sub vcl_fini {
- tbf.close();
- }
sub vcl_deliver {
set resp.http.result = tbf.rate("url:"+req.url, 1, 1s, 5);
}
diff --git a/tests/test02.vti b/tests/test02.vti
index ef58fb8..54ecdee 100644
--- a/tests/test02.vti
+++ b/tests/test02.vti
@@ -23,12 +23,6 @@ server s1 {
varnish v1 -vcl+backend {
import tbf from "${vmod_topbuild}/src/.libs/libvmod_tbf.so";
- sub vcl_init {
- tbf.open("${vmod_topbuild}/tests/tbf", "truncate");
- }
- sub vcl_fini {
- tbf.close();
- }
sub vcl_recv {
if (!tbf.check("url:"+req.url, "4 req/s")) {
#VARNISH3# error 420 "Overlimit";
diff --git a/tests/test03.vtc b/tests/test03.vtc
index 6da4839..0a6cdea 100644
--- a/tests/test03.vtc
+++ b/tests/test03.vtc
@@ -23,12 +23,6 @@ server s1 {
varnish v1 -vcl+backend {
import tbf from "${vmod_topbuild}/src/.libs/libvmod_tbf.so";
- sub vcl_init {
- tbf.open("${vmod_topbuild}/tests/tbf", "trunc");
- }
- sub vcl_fini {
- tbf.close();
- }
sub vcl_deliver {
set resp.http.result = tbf.check("url:"+req.url, "4req/s");
}

Return to:

Send suggestions and report system problems to the System administrator.