From ef009c2202de0721f6a56d3b879de66246cf27fd Mon Sep 17 00:00:00 2001 From: Sergey Poznyakoff Date: Fri, 29 Jan 2016 18:03:31 +0200 Subject: Change dump format; optionally dump the tree at exit; provide statistics (port f490124e0). * 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. --- src/Makefile.am | 2 - src/tbf.c | 761 +++++++++++++++++++++++++++++++++++++++++++----------- src/tbf.h | 54 ++++ src/vmod_tbf.vcc | 16 +- tests/Makefile.am | 1 + tests/test05.vtc | 117 +++++++++ 6 files changed, 799 insertions(+), 152 deletions(-) create mode 100644 tests/test05.vtc diff --git a/src/Makefile.am b/src/Makefile.am index 214af8f..0fe7ee8 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -61,5 +61,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 bbcbaa8..4e00bd8 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 . */ #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,57 +308,541 @@ 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) +{ + pthread_mutex_lock(&tree->mutex); + tree->refcnt++; + pthread_mutex_unlock(&tree->mutex); +} + +static void +tree_destroy(struct tree **tree_ptr) { - struct tree *tree = data; + 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 -tbf_init(struct vmod_priv *priv, const struct VCL_conf *vclconf) +tree_load_nodes(struct tree *tree, struct dump_header *hdr, + struct node **nodes, FILE *fp) { - priv->priv = tree_create(); - priv->free = tree_free; + 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 * -get_tree(struct vmod_priv *priv) +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() { - return priv->priv; + if (tbf_dump_file_name) { + struct tree *t = tbf_get_tree(); + tree_dump(t, tbf_dump_file_name); + tbf_release_tree(&t); + } } VCL_VOID @@ -400,45 +858,44 @@ vmod_set_gc_interval(MOD_CTX ctx, VCL_REAL interval) } VCL_VOID -vmod_gc(MOD_CTX ctx, struct vmod_priv *priv, VCL_REAL interval) +vmod_gc(MOD_CTX ctx, VCL_REAL interval) { - tree_gc(get_tree(priv), interval); + tree_gc(tbf_tree, interval); } VCL_BOOL -vmod_rate(MOD_CTX ctx, struct vmod_priv *priv, +vmod_rate(MOD_CTX 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(MOD_CTX ctx, struct vmod_priv *priv, - VCL_STRING key, VCL_STRING spec) +vmod_check(MOD_CTX ctx, VCL_STRING key, VCL_STRING spec) { double v, n; char *p; @@ -498,71 +955,87 @@ vmod_check(MOD_CTX 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(MOD_CTX 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(MOD_CTX 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(MOD_CTX 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(MOD_CTX ctx, struct vmod_priv *priv, VCL_STRING file) +vmod_log_tree(MOD_CTX 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(MOD_CTX 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 69e1262..9a9765c 100644 --- a/src/tbf.h +++ b/src/tbf.h @@ -24,6 +24,7 @@ #include #include "vrt.h" #include "vcc_if.h" +#include "vsha256.h" #include "pthread.h" #if VARNISHVERSION == 3 # include "bin/varnishd/cache.h" @@ -39,3 +40,56 @@ # define MOD_CTX const struct vrt_ctx * # define WSPTR(s) ((s)->ws) #endif + +#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..22493e1 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 @@ -24,14 +24,18 @@ For a detailed documentation, please see vmod-tbf(3) manual page. 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 c252b02..cb255cc 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -30,6 +30,7 @@ VMOD_TESTS = \ test01.vtc\ test02.vti\ test03.vtc\ + test05.vtc\ time00.vtc .vti.vtc: diff --git a/tests/test05.vtc b/tests/test05.vtc new file mode 100644 index 0000000..485318e --- /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 . + +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 + + -- cgit v1.2.1