diff options
-rw-r--r-- | NEWS | 2 | ||||
-rw-r--r-- | src/tbf.c | 743 | ||||
-rw-r--r-- | src/vmod-tbf.3 | 90 | ||||
-rw-r--r-- | src/vmod_tbf.vcc | 13 | ||||
-rw-r--r-- | tests/test00.vti | 6 | ||||
-rw-r--r-- | tests/test01.vtc | 6 | ||||
-rw-r--r-- | tests/test02.vti | 6 | ||||
-rw-r--r-- | tests/test03.vtc | 6 |
8 files changed, 394 insertions, 478 deletions
@@ -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. @@ -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"); } |