summaryrefslogtreecommitdiffabout
authorSergey Poznyakoff <gray@gnu.org.ua>2016-01-29 16:03:31 (GMT)
committer Sergey Poznyakoff <gray@gnu.org.ua>2016-01-29 16:03:31 (GMT)
commitf490124e04a9dda412d1979ca9e3e7a51f7ab8d3 (patch) (side-by-side diff)
tree8fed90caf8305d733438ddf2c2871c28a814571c
parent6ea9edf098af19ebb8b081be35c510ed57e99f47 (diff)
downloadvmod-tbf-f490124e04a9dda412d1979ca9e3e7a51f7ab8d3.tar.gz
vmod-tbf-f490124e04a9dda412d1979ca9e3e7a51f7ab8d3.tar.bz2
Change dump format; optionally dump the tree at exit; provide statistics
* src/tbf.c: Store tree in the global variable. Optionally save it to a disk file at exit. Provide statistics, dumping and loading functions. * src/tbf.h: Move data type declarations here. * src/vmod_tbf.vcc (load, dump_at_exit) (log_tree, log_stats): New functions. (dump, gc, rate, check): Remove PRIV_VCL parameter. * tests/Makefile.am (test05.vtc): New test case. * tests/test05.vtc: New file.
Diffstat (more/less context) (ignore whitespace changes)
-rw-r--r--src/Makefile.am2
-rw-r--r--src/tbf.c774
-rw-r--r--src/tbf.h54
-rw-r--r--src/vmod_tbf.vcc15
-rw-r--r--tests/Makefile.am1
-rw-r--r--tests/test05.vtc117
6 files changed, 809 insertions, 154 deletions
diff --git a/src/Makefile.am b/src/Makefile.am
index fa6050d..0ccb3bf 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -50,5 +50,3 @@ vcc_if.c vcc_if.h: $(vmodtool) $(vccfile)
EXTRA_DIST = \
vmod_tbf.vcc
-
-
diff --git a/src/tbf.c b/src/tbf.c
index 1ad754e..8fe3870 100644
--- a/src/tbf.c
+++ b/src/tbf.c
@@ -1,5 +1,5 @@
/* This file is part of vmod-tbf
- Copyright (C) 2013-2014 Sergey Poznyakoff
+ Copyright (C) 2013-2016 Sergey Poznyakoff
Vmod-tbf is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
@@ -15,13 +15,7 @@
along with vmod-tbf. If not, see <http://www.gnu.org/licenses/>.
*/
#include "tbf.h"
-#include "vsha256.h"
-#ifndef USEC_PER_SEC
-# define USEC_PER_SEC 1000000L
-#endif
-
-#define DEBUG 1
static unsigned gc_interval = 3600;
static int debug_level = 0;
@@ -35,33 +29,6 @@ debugprt(const char *fmt, ...)
}
#define debug(n,c) do { if (debug_level>=(n)) debugprt c; } while (0)
-enum { CHILD_LEFT, CHILD_RIGHT };
-
-struct node {
- uint8_t key[SHA256_LEN];
-#ifdef DEBUG
- char *keystr;
-#endif
- 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 */
-};
-
-struct tree
-{
- /* 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 */
/* Link NODE after REF in TREE. If REF is NULL, link at head */
@@ -78,8 +45,9 @@ lru_link_node(struct tree *tree, struct node *node, struct node *ref)
tree->head = node;
} else {
struct node *x;
-
+ //debug(0, ("LINK %p %p %p", node, ref, ref->next));
node->prev = ref;
+ node->next = ref->next;
if ((x = ref->next))
x->prev = node;
else
@@ -93,8 +61,6 @@ lru_unlink_node(struct tree *tree, struct node *node)
{
struct node *x;
- debug(1,("UNLINK %p %p\n", node, node->prev, node->next));
-
if ((x = node->prev))
x->next = node->next;
else
@@ -127,6 +93,22 @@ key_create(char const *input, uint8_t key[])
SHA256_Final(key, &ctx);
}
+static struct node *
+node_alloc(uint8_t key[], struct node *parent)
+{
+ static struct node *node;
+
+ node = calloc(1, sizeof(*node));
+ AN(node);
+ node->parent = parent;
+ keycpy(node->key, key);
+ pthread_cond_init(&node->notbusy, NULL);
+ node->busy = 1;
+ node->status = NST_INCOMPLETE;
+// debug(2, ("%x: allocated new node %p", pthread_self(), node));
+ return node;
+}
+
static void
node_lock(struct tree *tree, struct node *node)
{
@@ -139,15 +121,12 @@ node_lock(struct tree *tree, struct node *node)
static void
node_unlock(struct node *node)
{
- node->busy = 0;
- pthread_cond_broadcast(&node->notbusy);
+ if (node->busy) {
+ node->busy = 0;
+ pthread_cond_broadcast(&node->notbusy);
+ }
}
-enum node_lookup_result {
- NODE_FOUND,
- NODE_NEW
-};
-
static int
tree_lookup_node(struct tree *tree, uint8_t key[], struct node **ret)
{
@@ -171,20 +150,14 @@ tree_lookup_node(struct tree *tree, uint8_t key[], struct node **ret)
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;
+ node = node_alloc(key, parent);
*nodeptr = node;
- debug(2, ("%x: allocated new node %p", pthread_self(), node));
res = NODE_NEW;
}
lru_link_node(tree, node, NULL);
*ret = node;
pthread_mutex_unlock(&tree->mutex);
-// debug(0, ("head: %p, root: %p", tree->head, tree->root));
+// debug(2, ("head: %p, root: %p", tree->head, tree->root));
return res;
}
@@ -245,21 +218,22 @@ tree_gc(struct tree *tree, time_t timeout)
{
struct node *p;
uint64_t t;
-
+ size_t count = 0;
+
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));
+ ++count;
}
+ debug(1,("gc removed %lu nodes", count));
pthread_mutex_unlock(&tree->mutex);
}
@@ -282,7 +256,7 @@ tree_gc(struct tree *tree, time_t timeout)
arrived for BURST_SIZE*INTERVAL or more microseconds.
*/
-int
+static int
tbf_proc(struct tree *tree, const char *keystr, int cost,
unsigned long interval, int burst_size)
{
@@ -316,14 +290,14 @@ tbf_proc(struct tree *tree, const char *keystr, int cost,
else
node->tokens = (size_t)tokens;
- debug(2, ("%x: found, elapsed time: %"PRIu64" us, "
- "new tokens: %"PRIu64", total: %lu ",
- pthread_self(),
+ debug(2, ("found, elapsed time: %"PRIu64" us, "
+ "new tokens: %"PRIu64", total: %lu",
elapsed, tokens, (unsigned long) node->tokens));
break;
case NODE_NEW:
/* Initialize the structure */
+ node->status = NST_INIT;
#ifdef DEBUG
node->keystr = strdup(keystr);
#endif
@@ -334,53 +308,550 @@ tbf_proc(struct tree *tree, const char *keystr, int cost,
if (cost <= node->tokens) {
res = 1;
node->tokens -= cost;
- debug(2, ("%x: tbf_rate matched %s, tokens left %lu",
- pthread_self(), keystr,
+ debug(2, ("tbf_rate matched %s, tokens left %lu",
+ keystr,
(unsigned long) node->tokens));
} else {
res = 0;
- debug(1, ("%x: tbf_rate overlimit on %s",
- pthread_self(), keystr));
+ debug(1, ("tbf_rate overlimit on %s", keystr));
}
node_unlock(node);
debug(1, ("tbf_proc: return"));
return res;
}
-struct tree *
+static void tree_ref(struct tree *tree);
+
+static struct tree *
tree_create(void)
{
struct tree *tree = calloc(1, sizeof(*tree));
AN(tree);
pthread_mutex_init(&tree->mutex, NULL);
+ tree_ref(tree);
return tree;
}
-void
-tree_free(void *data)
+static void
+tree_ref(struct tree *tree)
{
- struct tree *tree = data;
+ pthread_mutex_lock(&tree->mutex);
+ tree->refcnt++;
+ pthread_mutex_unlock(&tree->mutex);
+}
+
+static void
+tree_destroy(struct tree **tree_ptr)
+{
+ struct tree *tree = *tree_ptr;
struct node *p;
pthread_mutex_lock(&tree->mutex);
+ *tree_ptr = NULL;
+
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);
}
+
+static void
+tree_unref(struct tree **ptree)
+{
+ struct tree *tree = *ptree;
+
+ pthread_mutex_lock(&tree->mutex);
+ AN(tree->refcnt);
+ if (--tree->refcnt == 0)
+ *ptree = NULL;
+ pthread_mutex_unlock(&tree->mutex);
+ if (tree->refcnt == 0)
+ tree_destroy(&tree);
+}
+
+static struct node *
+node_postorder_first(struct node *node)
+{
+ uint32_t n = node->ord;
+
+ while (1) {
+ if (node->child[CHILD_LEFT])
+ node = node->child[CHILD_LEFT];
+ else if (node->child[CHILD_RIGHT])
+ node = node->child[CHILD_RIGHT];
+ else
+ break;
+ node->ord = ++n;
+ }
+ return node;
+}
+
+static struct node *
+node_postorder_next(struct node *node)
+{
+ AN(node->parent);
+ if (node == node->parent->child[CHILD_RIGHT])
+ return node->parent;
+ if (node == node->parent->child[CHILD_LEFT]) {
+ if (node->parent->child[CHILD_RIGHT]) {
+ node->parent->child[CHILD_RIGHT]->ord = node->parent->ord + 1;
+ return node_postorder_first(node->parent->child[CHILD_RIGHT]);
+ } else
+ return node->parent;
+ }
+ /* should not happen */
+ abort();
+}
+
+static void
+tree_traverse_postorder(struct tree *tree,
+ void (*visit)(struct node *, void *data),
+ void *data)
+{
+ struct node *node;
+ pthread_mutex_lock(&tree->mutex);
+ tree->root->ord = 1;
+ node = node_postorder_first(tree->root);
+ visit(node, data);
+ while (node != tree->root) {
+ node = node_postorder_next(node);
+ visit(node, data);
+ }
+ pthread_mutex_unlock(&tree->mutex);
+}
+#if 0
+static void
+node_traverse_postorder(struct node *node,
+ void (*visit)(struct node *, void *data),
+ void *data)
+{
+ if (!node) return;
+ node_traverse_postorder(node->child[CHILD_LEFT], visit, data);
+ node_traverse_postorder(node->child[CHILD_RIGHT], visit, data);
+ visit(node, data);
+}
+
+static void
+tree_traverse_postorder(struct tree *tree,
+ void (*visit)(struct node *, void *data),
+ void *data)
+{
+ node_traverse_postorder(tree->root, visit, data);
+}
+#endif
+
+struct tree_stats
+{
+ uint32_t len_sum;
+ uint32_t num_nodes;
+ uint32_t num_leaves;
+ uint32_t shortest_path;
+ uint32_t longest_path;
+ double avg_path;
+};
+
+static void
+node_compute_stats(struct node *node, void *data)
+{
+ struct tree_stats *st = data;
+ st->num_nodes++;
+ if (!node->child[CHILD_LEFT] && !node->child[CHILD_RIGHT]) {
+ st->num_leaves++;
+ st->len_sum += node->ord;
+ if (node->ord > st->longest_path)
+ st->longest_path = node->ord;
+ if (node->ord < st->shortest_path)
+ st->shortest_path = node->ord;
+ }
+}
+
+void
+tree_compute_stats(struct tree *tree, struct tree_stats *st)
+{
+ memset(st, 0, sizeof(*st));
+ st->shortest_path = tree->root != NULL ? (uint32_t)-1 : 0;
+ tree_traverse_postorder(tree, node_compute_stats, st);
+ if (st->num_leaves)
+ st->avg_path = (double) st->len_sum / st->num_leaves;
+}
+
+
+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;
+}
+
+static void
+node_dump_ord(struct node *node, FILE *fp)
+{
+ uint32_t *p;
+
+ if (node)
+ p = &node->ord;
+ else {
+ uint32_t t = 0;
+ p = &t;
+ }
+ fwrite(p, sizeof(*p), 1, fp);
+}
+
+#define ELSIZE(m) sizeof(((struct node*)0)->m)
+#define RECSIZE (3*ELSIZE(key) + ELSIZE(timestamp) + ELSIZE(tokens))
+
+static void
+node_dump(struct node *node, FILE *fp)
+{
+ uint32_t len = 1;
+ uint32_t flags = 0;
+
+#ifdef DEBUG
+ len += (strlen(node->keystr) + RECSIZE) / RECSIZE;
+#endif
+ fwrite(&len, sizeof(len), 1, fp);
+ if (node->child[CHILD_LEFT])
+ flags |= FL_CHILD_LEFT;
+ if (node->child[CHILD_RIGHT])
+ flags |= FL_CHILD_RIGHT;
+ fwrite(&flags, sizeof(flags), 1, fp);
+
+ fwrite(&node->key, sizeof(node->key), 1, fp);
+ node_dump_ord(node->child[CHILD_LEFT], fp);
+ node_dump_ord(node->child[CHILD_RIGHT], fp);
+ fwrite(&node->timestamp, sizeof(node->timestamp), 1, fp);
+ fwrite(&node->tokens, sizeof(node->tokens), 1, fp);
+#ifdef DEBUG
+ fwrite(node->keystr, strlen(node->keystr), 1, fp);
+ len = RECSIZE - (strlen(node->keystr) + RECSIZE) % RECSIZE;
+ if (len) {
+ char c = 0;
+ fseek(fp, len-1, SEEK_CUR);
+ fputc(c, fp);
+ }
+#endif
+}
+
+static void
+tree_dump_unlocked(struct tree *tree, char const *file)
+{
+ struct node *node;
+ char keybuf[3][2*SHA256_LEN+1];
+ FILE *fp;
+ int err = 0;
+ struct dump_header header;
+
+ fp = fopen(file, "w");
+ if (!fp) {
+ syslog(LOG_DAEMON|LOG_ERR,
+ "tbf.dump: can't open file %s for output: %m", file);
+ return;
+ }
+
+ header.version = DUMP_VERSION;
+#ifdef DEBUG
+ header.debug = 1;
+#else
+ header.debug = 0;
+#endif
+ header.size = RECSIZE;
+ header.count = 0;
+
+ /* Count nodes */
+ for (node = tree->head; node; node = node->next)
+ node->ord = header.count++;
+ if (tree->root)
+ header.root = tree->root->ord;
+ fwrite(&header, sizeof(header), 1, fp);
+ for (node = tree->head; node; node = node->next) {
+ node_dump(node, fp);
+ if (ferror(fp)) {
+ syslog(LOG_DAEMON|LOG_ERR,
+ "tbf.dump: error writing to %s: %m", file);
+ err = 1;
+ break;
+ }
+ }
+ fclose(fp);
+ if (err)
+ unlink(file);
+}
+
+static void
+tree_dump(struct tree *tree, char const *file)
+{
+ if (tree) {
+ pthread_mutex_lock(&tree->mutex);
+ tree_dump_unlocked(tree, file);
+ pthread_mutex_unlock(&tree->mutex);
+ }
+}
+
+static int
+readrec(FILE *fp, void *buf, size_t size)
+{
+ switch (fread(buf, size, 1, fp)) {
+ case 1:
+ break;
+ case -1:
+ syslog(LOG_DAEMON|LOG_ERR, "tbf.%s: read error: %s",
+ __FUNCTION__, strerror(errno));
+ return -1;
+ default:
+ syslog(LOG_DAEMON|LOG_ERR, "tbf.%s: unexpected EOF",
+ __FUNCTION__);
+ return -1;
+ }
+ return 0;
+}
+
+#define READREC(f,r) readrec(f, &(r), sizeof(r))
+
+struct node *
+new_node(struct node **nodes, struct dump_header *hdr,
+ uint32_t ord, struct node *parent)
+{
+ struct node *child;
+
+ if (ord >= hdr->count)
+ return NULL;
+
+ if (nodes[ord]) {
+ child = nodes[ord];
+ child->parent = parent;
+ } else {
+ static uint8_t null_key[SHA256_LEN];
+
+ child = node_alloc(null_key, parent);
+ nodes[ord] = child;
+ }
+ return child;
+}
+
+int
+tree_load_nodes(struct tree *tree, struct dump_header *hdr,
+ struct node **nodes, FILE *fp)
+{
+ size_t i;
+ uint32_t root_idx;
+ uint32_t ord[2];
+ size_t incomplete = 0;
+
+ for (i = 0; i < hdr->count; i++) {
+ struct node node, *np;
+ uint32_t len;
+ uint32_t flags;
+
+ debug(0,("Load record %lu/%lu %lu", i, hdr->count, incomplete));
+
+ if (READREC(fp, len))
+ return -1;
+ if (READREC(fp, flags))
+ return -1;
+ if (READREC(fp, node.key))
+ return -1;
+ if (READREC(fp, ord[CHILD_LEFT]))
+ return -1;
+ if (READREC(fp, ord[CHILD_RIGHT]))
+ return -1;
+ if (READREC(fp, node.timestamp))
+ return -1;
+ if (READREC(fp, node.tokens))
+ return -1;
+
+ if (--len) {
+#ifdef DEBUG
+ char *p, *recbuf = malloc(len * hdr->size);
+ AN(recbuf);
+ p = recbuf;
+ while (len--) {
+ if (readrec(fp, p, hdr->size)) {
+ free(recbuf);
+ return -1;
+ }
+ p += hdr->size;
+ }
+ node.keystr = recbuf;
+#else
+ fseek(fp, len * hdr->size, SEEK_SET);
+#endif
+ }
+
+ if (nodes[i]) {
+ np = nodes[i];
+ if (np->status == NST_INIT) {
+ syslog(LOG_DAEMON|LOG_ERR,
+ "tbf.%s: duplicate node",
+ __FUNCTION__);
+#if DEBUG
+ free(node.keystr);
+#endif
+ return -1;
+ } else {
+ --incomplete;
+ keycpy(np->key, node.key);
+ }
+ } else {
+ np = node_alloc(node.key, NULL);
+ np->status = NST_INIT;
+ node_unlock(np);
+ nodes[i] = np;
+ }
+ np->timestamp = node.timestamp;
+ np->tokens = node.tokens;
+#if DEBUG
+ np->keystr = node.keystr;
+ debug(0, ("loaded %p: %s %1x (%lu,%lu): time: %"PRIu64" us, tokens: %lu",
+ np,
+ np->keystr,
+ flags,
+ ord[CHILD_LEFT],
+ ord[CHILD_RIGHT],
+ np->timestamp, np->tokens));
+#endif
+ if (flags & FL_CHILD_LEFT) {
+ np->child[CHILD_LEFT] =
+ new_node(nodes, hdr, ord[CHILD_LEFT], np);
+ if (!np->child[CHILD_LEFT]) {
+ syslog(LOG_DAEMON|LOG_ERR,
+ "tbf.%s: invalid left pointer",
+ __FUNCTION__);
+ return -1;
+ }
+ if (np->child[CHILD_LEFT]->status == NST_INCOMPLETE) {
+ ++incomplete;
+ }
+ }
+
+ if (flags & FL_CHILD_RIGHT) {
+ np->child[CHILD_RIGHT] =
+ new_node(nodes, hdr, ord[CHILD_RIGHT], np);
+ if (!np->child[CHILD_RIGHT]) {
+ syslog(LOG_DAEMON|LOG_ERR,
+ "tbf.%s: invalid left pointer",
+ __FUNCTION__);
+ return -1;
+ }
+ if (np->child[CHILD_RIGHT]->status == NST_INCOMPLETE) {
+ ++incomplete;
+ }
+ }
+ lru_link_node(tree, np, tree->tail);
+ }
+
+ if (incomplete) {
+ syslog(LOG_DAEMON|LOG_ERR, "tbf.%s: %lu incomplete nodes left",
+ __FUNCTION__, incomplete);
+ return 1;
+ }
+ tree->root = nodes[hdr->root];
+// debug(0,("Loaded nodes"));
+ return 0;
+}
+
+struct tree *
+tree_load(char const *filename)
+{
+ FILE *fp;
+ struct tree *tree;
+ int rc;
+ struct dump_header header;
+
+ fp = fopen(filename, "r");
+ if (!fp) {
+ syslog(LOG_DAEMON|LOG_ERR, "can't open file %s: %s",
+ filename, strerror(errno));
+ return NULL;
+ }
+
+ if (READREC(fp, header))
+ rc = -1;
+ else {
+ struct node **nodes;
+
+ debug(0,("elements: %"PRIu32", size: %"PRIu32", root: %"PRIu32,
+ header.count, header.size, header.root));
+ tree = tree_create();
+ nodes = calloc(header.count, sizeof(*nodes));
+ rc = tree_load_nodes(tree, &header, nodes, fp);
+ fclose(fp);
+ if (rc) {
+ size_t i;
+ for (i = 0; i < header.count; i++) {
+ if (nodes[i])
+ node_free(nodes[i]);
+ }
+ tree->root = tree->head = tree->tail = NULL;
+ tree_destroy(&tree);
+ }
+ free(nodes);
+ }
+ return tree;
+}
+
+
+pthread_mutex_t access_mutex = PTHREAD_MUTEX_INITIALIZER;
+static struct tree *tbf_tree;
+static char *tbf_dump_file_name;
+
+static struct tree *
+tbf_get_tree(void)
+{
+ struct tree *t;
+ pthread_mutex_lock(&access_mutex);
+ tree_ref(tbf_tree);
+ t = tbf_tree;
+ pthread_mutex_unlock(&access_mutex);
+ return t;
+}
+
+static void
+tbf_release_tree(struct tree **t)
+{
+ tree_unref(t);
+}
+
+
+static void
+tbf_exit()
+{
+ if (tbf_dump_file_name) {
+ struct tree *t = tbf_get_tree();
+ tree_dump(t, tbf_dump_file_name);
+ tbf_release_tree(&t);
+ }
+}
+
int
tbf_event(VRT_CTX, struct vmod_priv *priv, enum vcl_event_e e)
{
switch (e) {
case VCL_EVENT_LOAD:
- priv->priv = tree_create();
- priv->free = tree_free;
+ tbf_tree = tree_create();
+ atexit(tbf_exit);
break;
case VCL_EVENT_DISCARD:
@@ -393,12 +864,6 @@ tbf_event(VRT_CTX, struct vmod_priv *priv, enum vcl_event_e e)
return 0;
}
-struct tree *
-get_tree(struct vmod_priv *priv)
-{
- return priv->priv;
-}
-
VCL_VOID
vmod_debug(VRT_CTX, VCL_INT newval)
{
@@ -412,45 +877,44 @@ vmod_set_gc_interval(VRT_CTX, VCL_REAL interval)
}
VCL_VOID
-vmod_gc(VRT_CTX, struct vmod_priv *priv, VCL_REAL interval)
+vmod_gc(VRT_CTX, VCL_REAL interval)
{
- tree_gc(get_tree(priv), interval);
+ tree_gc(tbf_tree, interval);
}
VCL_BOOL
-vmod_rate(VRT_CTX, struct vmod_priv *priv,
+vmod_rate(VRT_CTX,
VCL_STRING key, VCL_INT cost, VCL_REAL t,
VCL_INT burst_size)
{
- struct tree *tree = get_tree(priv);
+ VCL_BOOL res;
+ struct tree *tree = tbf_get_tree();
unsigned long interval = t * USEC_PER_SEC;
- debug(2, ("%x: entering rate(%s,%d,%g,%d)",
- pthread_self(), key, cost, t, burst_size));
+ debug(2, ("entering rate(%s,%d,%g,%d)",
+ key, cost, t, burst_size));
- if (interval == 0 || burst_size == 0)
- return false;
-
tree_gc(tree, gc_interval);
- if (!cost) {
+ if (interval == 0 || burst_size == 0)
+ res = false;
+ else if (!cost)
/* cost free, so don't waste time on tree lookup */
- return true;
- }
- if (cost > burst_size) {
+ res = true;
+ else if (cost > burst_size)
/* impossibly expensive, so don't waste time on
tree lookup */
- return false;
- }
-
- return tbf_proc(tree, key, cost, interval, burst_size);
+ res = false;
+ else
+ res = tbf_proc(tree, key, cost, interval, burst_size);
+ tbf_release_tree(&tree);
+ return res;
}
#define ISWS(c) ((c)==' '||(c)=='\t')
VCL_BOOL
-vmod_check(VRT_CTX, struct vmod_priv *priv,
- VCL_STRING key, VCL_STRING spec)
+vmod_check(VRT_CTX, VCL_STRING key, VCL_STRING spec)
{
double v, n;
char *p;
@@ -510,71 +974,87 @@ vmod_check(VRT_CTX, struct vmod_priv *priv,
syslog(LOG_DAEMON|LOG_WARNING, "garbage after rate spec: %s",
spec);
- return vmod_rate(ctx, priv, key, 1, n/v, v/n+1);
+ return vmod_rate(ctx, key, 1, n/v, v/n+1);
}
-static char xdig[] = "0123456789abcdef";
-
-static void
-key_to_str(uint8_t key[], char *buf)
+VCL_VOID
+vmod_dump(VRT_CTX, VCL_STRING file)
{
- size_t i;
+ struct tree *t = tbf_get_tree();
+ tree_dump(t, file);
+ tbf_release_tree(&t);
+}
- for (i = 0; i < SHA256_LEN; i++) {
- *buf++ = xdig[key[i] >> 4];
- *buf++ = xdig[key[i] & 0xf];
+VCL_VOID
+vmod_dump_at_exit(VRT_CTX, VCL_STRING file)
+{
+ pthread_mutex_lock(&access_mutex);
+ free(tbf_dump_file_name);
+ tbf_dump_file_name = strdup(file);
+ AN(tbf_dump_file_name);
+ pthread_mutex_unlock(&access_mutex);
+}
+
+VCL_VOID
+vmod_load(VRT_CTX, VCL_STRING file)
+{
+ struct tree *new_tree = tree_load(file);
+ if (new_tree) {
+ pthread_mutex_lock(&access_mutex);
+ tree_unref(&tbf_tree);
+ tbf_tree = new_tree;
+ pthread_mutex_unlock(&access_mutex);
}
- *buf = 0;
}
+struct traverse_closure
+{
+ int prio;
+ uint32_t num;
+};
+
static void
-node_to_keystr(struct node *node, char *buf)
+log_node(struct node *node, void *data)
{
- if (node)
- key_to_str(node->key, buf);
- else
- *buf = 0;
+ struct traverse_closure *tc = data;
+ char kbuf[2*SHA256_LEN+1];
+ key_to_str(node->key, kbuf);
+#ifdef DEBUG
+ syslog(tc->prio, "%d: %p(%p,%p): %lu %s: %s", tc->num, node,
+ node->child[CHILD_LEFT], node->child[CHILD_RIGHT], node->ord,
+ kbuf,
+ node->keystr);
+#else
+ syslog(tc->prio, "%d: %p(%p,%p): %lu %s", tc->num, node,
+ node->child[CHILD_LEFT], node->child[CHILD_RIGHT], node->ord,
+ kbuf);
+#endif
}
+
VCL_VOID
-vmod_dump(VRT_CTX, struct vmod_priv *priv, VCL_STRING file)
+vmod_log_tree(VRT_CTX, VCL_INT prio)
{
- 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);
+ struct traverse_closure tc;
+ struct tree *tree = tbf_get_tree();
+ if (!tree)
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);
+ tc.num = 0;
+ tc.prio = prio;
+ tree_traverse_postorder(tree, log_node, &tc);
+ tbf_release_tree(&tree);
+}
+
+VCL_VOID
+vmod_log_stats(VRT_CTX, VCL_INT prio)
+{
+ struct tree_stats st;
+ struct tree *tree = tbf_get_tree();
+ tree_compute_stats(tree, &st);
+ tbf_release_tree(&tree);
+ syslog(prio, "Number of nodes: %lu", st.num_nodes);
+ syslog(prio, "Number of leaves: %lu", st.num_leaves);
+ syslog(prio, "Shortest path: %lu", st.shortest_path);
+ syslog(prio, "Longest path: %lu", st.longest_path);
+ syslog(prio, "Avg path: %f", st.avg_path);
}
diff --git a/src/tbf.h b/src/tbf.h
index ea0aa6e..d4dd292 100644
--- a/src/tbf.h
+++ b/src/tbf.h
@@ -26,8 +26,62 @@
#include <vcl.h>
#include <vrt.h>
#include "vcc_if.h"
+#include "vsha256.h"
#include "pthread.h"
#include "bin/varnishd/cache/cache.h"
#define MOD_CTX const struct vrt_ctx *
#define WSPTR(s) ((s)->ws)
+
+#ifndef USEC_PER_SEC
+# define USEC_PER_SEC 1000000L
+#endif
+
+#define DEBUG 1
+
+struct dump_header {
+ uint32_t version;
+ uint32_t debug;
+ uint32_t size;
+ uint32_t count;
+ uint32_t root;
+};
+#define DUMP_VERSION 0
+
+enum { CHILD_LEFT, CHILD_RIGHT };
+
+#define FL_CHILD_LEFT 0x1
+#define FL_CHILD_RIGHT 0x2
+
+enum { NST_INCOMPLETE, NST_INIT };
+
+struct node {
+ uint8_t key[SHA256_LEN];
+#ifdef DEBUG
+ char *keystr;
+#endif
+ struct node *parent;
+ struct node *child[2];
+ struct node *prev, *next;
+ pthread_cond_t notbusy;
+ int busy:1;
+ int status;
+ uint32_t ord;
+ uint64_t timestamp; /* microseconds since epoch */
+ size_t tokens; /* tokens available */
+};
+
+struct tree
+{
+ /* 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;
+ size_t refcnt;
+};
+
+enum node_lookup_result { NODE_FOUND, NODE_NEW };
+
diff --git a/src/vmod_tbf.vcc b/src/vmod_tbf.vcc
index 43609b7..0ec6b8a 100644
--- a/src/vmod_tbf.vcc
+++ b/src/vmod_tbf.vcc
@@ -1,5 +1,5 @@
# This file is part of vmod-tbf
-# Copyright (C) 2013-2014 Sergey Poznyakoff
+# Copyright (C) 2013-2016 Sergey Poznyakoff
#
# Vmod-tbf is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
@@ -26,12 +26,17 @@ DESCRIPTION
$Event tbf_event
$Function VOID debug(INT)
-$Function VOID dump(PRIV_VCL, STRING)
-$Function VOID gc(PRIV_VCL, DURATION)
+$Function VOID dump(STRING)
+$Function VOID load(STRING)
+$Function VOID gc(DURATION)
$Function VOID set_gc_interval(DURATION)
-$Function BOOL rate(PRIV_VCL, STRING, INT, DURATION, INT)
-$Function BOOL check(PRIV_VCL, STRING, STRING)
+$Function VOID dump_at_exit(STRING)
+$Function BOOL rate(STRING, INT, DURATION, INT)
+$Function BOOL check(STRING, STRING)
$Function REAL getla(INT)
$Function INT systime()
$Function STRING strftime(STRING, INT)
$Function VOID sleep(DURATION)
+
+$Function VOID log_tree(INT)
+$Function VOID log_stats(INT) \ No newline at end of file
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 9b4a5fe..413d176 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -19,6 +19,7 @@ VMOD_TESTS = \
test01.vtc\
test02.vtc\
test03.vtc\
+ test05.vtc\
time00.vtc
EXTRA_DIST=$(VMOD_TESTS)
diff --git a/tests/test05.vtc b/tests/test05.vtc
new file mode 100644
index 0000000..485318e
--- a/dev/null
+++ b/tests/test05.vtc
@@ -0,0 +1,117 @@
+# This file is part of vmod-tbf
+# Copyright (C) 2013-2016 Sergey Poznyakoff
+#
+# Vmod-tbf 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-tbf 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-tbf. If not, see <http://www.gnu.org/licenses/>.
+
+varnishtest "Test dump/load facilities"
+
+server s1 {
+ rxreq
+ txresp
+
+ rxreq
+ txresp
+
+ rxreq
+ txresp
+
+ rxreq
+ txresp
+
+ rxreq
+ txresp
+
+ rxreq
+ txresp
+
+ rxreq
+ txresp
+
+ rxreq
+ txresp
+
+ rxreq
+ txresp
+} -start
+
+varnish v1 -vcl+backend {
+ import std;
+ import tbf from "${vmod_topbuild}/src/.libs/libvmod_tbf.so";
+ # sub vcl_init {
+ # tbf.debug(20);
+ # }
+ sub vcl_recv {
+ if (req.url == "/dump") {
+ tbf.dump("/tmp/test05.dump");
+ } else if (req.url == "/load") {
+ tbf.load("/tmp/test05.dump");
+ } else if (!tbf.rate("url:"+req.url, 1, 5 s, 2)) {
+ return (synth(420, "Overlimit"));
+ }
+ return (hash);
+ }
+} -start
+
+client c1 {
+ txreq -url "/seks"
+ rxresp
+ expect resp.status == 200
+ txreq -url "/fire"
+ rxresp
+ expect resp.status == 200
+ txreq -url "/tre"
+ rxresp
+ expect resp.status == 200
+ txreq -url "/fem"
+ rxresp
+ expect resp.status == 200
+ txreq -url "/en"
+ rxresp
+ expect resp.status == 200
+ txreq -url "/to"
+ rxresp
+ expect resp.status == 200
+ txreq -url "/sju"
+ rxresp
+ expect resp.status == 200
+
+ # [1] Save the tree
+ txreq -url "/dump"
+ rxresp
+ expect resp.status == 200
+
+ txreq -url "/sju"
+ rxresp
+ expect resp.status == 200
+ txreq -url "/sju"
+ rxresp
+ expect resp.status == 420
+
+ # Restore the tree to its state at [1]
+ txreq -url "/load"
+ rxresp
+ expect resp.status == 200
+
+ # It should now allow to access /sju
+ txreq -url "/sju"
+ rxresp
+ expect resp.status == 200
+
+# delay
+
+}
+
+client c1 -run
+
+

Return to:

Send suggestions and report system problems to the System administrator.