diff options
| -rw-r--r-- | ctdb/common/hash_count.c | 219 | ||||
| -rw-r--r-- | ctdb/common/hash_count.h | 94 | ||||
| -rwxr-xr-x | ctdb/tests/cunit/hash_count_test_001.sh | 7 | ||||
| -rw-r--r-- | ctdb/tests/src/hash_count_test.c | 132 | ||||
| -rw-r--r-- | ctdb/wscript | 4 |
5 files changed, 455 insertions, 1 deletions
diff --git a/ctdb/common/hash_count.c b/ctdb/common/hash_count.c new file mode 100644 index 00000000000..f84501663c1 --- /dev/null +++ b/ctdb/common/hash_count.c @@ -0,0 +1,219 @@ +/* + Using hash table for counting events + + Copyright (C) Amitay Isaacs 2017 + + This program 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 of the License, or + (at your option) any later version. + + This program 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 this program; if not, see <http://www.gnu.org/licenses/>. +*/ + +#include "replace.h" +#include "system/filesys.h" +#include "system/time.h" + +#include <tdb.h> + +#include "lib/util/time.h" + +#include "common/db_hash.h" +#include "common/hash_count.h" + +struct hash_count_value { + struct timeval update_time; + uint64_t counter; +}; + +struct hash_count_context { + struct db_hash_context *dh; + struct timeval update_interval; + hash_count_update_handler_fn handler; + void *private_data; +}; + +/* + * Initialise hash count map + */ +int hash_count_init(TALLOC_CTX *mem_ctx, struct timeval update_interval, + hash_count_update_handler_fn handler, void *private_data, + struct hash_count_context **result) +{ + struct hash_count_context *hcount; + int ret; + + if (handler == NULL) { + return EINVAL; + } + + hcount = talloc_zero(mem_ctx, struct hash_count_context); + if (hcount == NULL) { + return ENOMEM; + } + + ret = db_hash_init(hcount, "hash_count_db", 8192, DB_HASH_COMPLEX, + &hcount->dh); + if (ret != 0) { + talloc_free(hcount); + return ret; + } + + hcount->update_interval = update_interval; + hcount->handler = handler; + hcount->private_data = private_data; + + *result = hcount; + return 0; +} + +static int hash_count_fetch_parser(uint8_t *keybuf, size_t keylen, + uint8_t *databuf, size_t datalen, + void *private_data) +{ + struct hash_count_value *value = + (struct hash_count_value *)private_data; + + if (datalen != sizeof(struct hash_count_value)) { + return EIO; + } + + *value = *(struct hash_count_value *)databuf; + return 0; +} + +static int hash_count_fetch(struct hash_count_context *hcount, TDB_DATA key, + struct hash_count_value *value) +{ + return db_hash_fetch(hcount->dh, key.dptr, key.dsize, + hash_count_fetch_parser, value); +} + +static int hash_count_insert(struct hash_count_context *hcount, TDB_DATA key, + struct hash_count_value *value) +{ + return db_hash_insert(hcount->dh, key.dptr, key.dsize, + (uint8_t *)value, + sizeof(struct hash_count_value)); +} + +static int hash_count_update(struct hash_count_context *hcount, TDB_DATA key, + struct hash_count_value *value) +{ + return db_hash_add(hcount->dh, key.dptr, key.dsize, + (uint8_t *)value, sizeof(struct hash_count_value)); +} + +int hash_count_increment(struct hash_count_context *hcount, TDB_DATA key) +{ + struct hash_count_value value; + struct timeval current_time = timeval_current(); + int ret; + + if (hcount == NULL) { + return EINVAL; + } + + ret = hash_count_fetch(hcount, key, &value); + if (ret == 0) { + struct timeval tmp_t; + + tmp_t = timeval_sum(&value.update_time, + &hcount->update_interval); + if (timeval_compare(¤t_time, &tmp_t) < 0) { + value.counter += 1; + } else { + value.update_time = current_time; + value.counter = 1; + } + + hcount->handler(key, value.counter, hcount->private_data); + ret = hash_count_update(hcount, key, &value); + + } else if (ret == ENOENT) { + value.update_time = current_time; + value.counter = 1; + + hcount->handler(key, value.counter, hcount->private_data); + ret = hash_count_insert(hcount, key, &value); + } + + return ret; +} + +static struct timeval timeval_subtract(const struct timeval *tv1, + const struct timeval *tv2) +{ + struct timeval tv = *tv1; + const unsigned int million = 1000000; + + if (tv.tv_sec > 1) { + tv.tv_sec -= 1; + tv.tv_usec += million; + } else { + return tv; + } + + tv.tv_sec -= tv2->tv_sec; + tv.tv_usec -= tv2->tv_usec; + + tv.tv_sec += tv.tv_usec / million; + tv.tv_usec = tv.tv_usec % million; + + return tv; +} + +struct hash_count_expire_state { + struct db_hash_context *dh; + struct timeval last_time; + int count; +}; + +static int hash_count_expire_parser(uint8_t *keybuf, size_t keylen, + uint8_t *databuf, size_t datalen, + void *private_data) +{ + struct hash_count_expire_state *state = + (struct hash_count_expire_state *)private_data; + struct hash_count_value *value; + int ret = 0; + + if (datalen != sizeof(struct hash_count_value)) { + return EIO; + } + + value = (struct hash_count_value *)databuf; + if (timeval_compare(&value->update_time, &state->last_time) < 0) { + ret = db_hash_delete(state->dh, keybuf, keylen); + if (ret == 0) { + state->count += 1; + } + } + + return ret; +} + +void hash_count_expire(struct hash_count_context *hcount, int *delete_count) +{ + struct timeval current_time = timeval_current(); + struct hash_count_expire_state state; + + state.dh = hcount->dh; + state.last_time = timeval_subtract(¤t_time, + &hcount->update_interval); + state.count = 0; + + (void) db_hash_traverse_update(hcount->dh, hash_count_expire_parser, + &state, NULL); + + if (delete_count != NULL) { + *delete_count = state.count; + } +} diff --git a/ctdb/common/hash_count.h b/ctdb/common/hash_count.h new file mode 100644 index 00000000000..f14c82cbd7a --- /dev/null +++ b/ctdb/common/hash_count.h @@ -0,0 +1,94 @@ +/* + Using hash table for counting events + + Copyright (C) Amitay Isaacs 2017 + + This program 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 of the License, or + (at your option) any later version. + + This program 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 this program; if not, see <http://www.gnu.org/licenses/>. +*/ + +#ifndef __CTDB_HASH_COUNT_H__ +#define __CTDB_HASH_COUNT_H__ + +/** + * @file hash_count.h + * + * @brief Count key-based events for specified interval + * + * This can be used to measure the rate of events based on any interval. + * For example, number of occurrences per second. + */ + +/** + * @brief Handler callback function called when counter is incremented + * + * This function is called every time a counter is incremented for a key. + * The counter argument is the number of times the increment function is + * called during a count interval. + * + * This function should not modify key and data arguments. + */ +typedef void (*hash_count_update_handler_fn)(TDB_DATA key, uint64_t counter, + void *private_data); + +/** + * @brief Abstract structure representing hash based counting + */ +struct hash_count_context; + +/** + * @brief Initialize hash counting + * + * This return a new hash count context which is a talloc context. Freeing + * this context will free all the memory associated with hash count. + * + * @param[in] mem_ctx Talloc memory context + * @param[in] count_interval The time interval for counting events + * @param[in] handler Function called when counter is incremented + * @param[in] private_data Private data to handler function + * @param[out] result The new hash_count structure + * @return 0 on success, errno on failure + */ +int hash_count_init(TALLOC_CTX *mem_ctx, struct timeval count_interval, + hash_count_update_handler_fn handler, void *private_data, + struct hash_count_context **result); + +/** + * @brief Increment a counter for a key + * + * First time this is called for a key, corresponding counter is set to 1 + * and the start time is noted. For all subsequent calls made during the + * count_interval (used in initializing the context) will increment + * corresponding counter for the key. After the count_interval has elapsed, + * the counter will be reset to 1. + * + * @param[in] hcount The hash count context + * @param[in] key The key for which counter is updated + * @return 0 on success, errno on failure + * + * This will result in a callback function being called. + */ +int hash_count_increment(struct hash_count_context *hcount, TDB_DATA key); + +/** + * @brief Remove keys for which count interval has elapsed + * + * This function is used to clean the database of keys for which there are + * no recent events. + * + * @param[in] hcount The hash count context + * @param[out] delete_count The number of keys deleted + */ +void hash_count_expire(struct hash_count_context *hcount, int *delete_count); + +#endif /* __CTDB_HASH_COUNT_H__ */ diff --git a/ctdb/tests/cunit/hash_count_test_001.sh b/ctdb/tests/cunit/hash_count_test_001.sh new file mode 100755 index 00000000000..39587060b01 --- /dev/null +++ b/ctdb/tests/cunit/hash_count_test_001.sh @@ -0,0 +1,7 @@ +#!/bin/sh + +. "${TEST_SCRIPTS_DIR}/unit.sh" + +ok_null + +unit_test hash_count_test diff --git a/ctdb/tests/src/hash_count_test.c b/ctdb/tests/src/hash_count_test.c new file mode 100644 index 00000000000..6ddde084cff --- /dev/null +++ b/ctdb/tests/src/hash_count_test.c @@ -0,0 +1,132 @@ +/* + hash_count tests + + Copyright (C) Amitay Isaacs 2017 + + This program 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 of the License, or + (at your option) any later version. + + This program 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 this program; if not, see <http://www.gnu.org/licenses/>. +*/ + +#include "replace.h" + +#include <assert.h> + +#include "common/db_hash.c" +#include "common/hash_count.c" + +#define KEY "this_is_a_test_key" + +static void test1_handler(TDB_DATA key, uint64_t counter, void *private_data) +{ + int *count = (int *)private_data; + + assert(key.dsize == strlen(KEY)); + assert(strcmp((char *)key.dptr, KEY) == 0); + assert(counter > 0); + + (*count) += 1; +} + +static void do_test1(void) +{ + struct hash_count_context *hc = NULL; + TALLOC_CTX *mem_ctx = talloc_new(NULL); + struct timeval interval = {1, 0}; + TDB_DATA key; + int count = 0; + int ret, i; + + key.dptr = (uint8_t *)discard_const(KEY); + key.dsize = strlen(KEY); + + ret = hash_count_increment(hc, key); + assert(ret == EINVAL); + + ret = hash_count_init(mem_ctx, interval, NULL, NULL, &hc); + assert(ret == EINVAL); + + ret = hash_count_init(mem_ctx, interval, test1_handler, &count, &hc); + assert(ret == 0); + assert(hc != NULL); + + for (i=0; i<10; i++) { + ret = hash_count_increment(hc, key); + assert(ret == 0); + assert(count == i+1); + } + + talloc_free(hc); + ret = talloc_get_size(mem_ctx); + assert(ret == 0); + + talloc_free(mem_ctx); +} + +static void test2_handler(TDB_DATA key, uint64_t counter, void *private_data) +{ + uint64_t *count = (uint64_t *)private_data; + + *count = counter; +} + +static void do_test2(void) +{ + struct hash_count_context *hc; + TALLOC_CTX *mem_ctx = talloc_new(NULL); + struct timeval interval = {1, 0}; + TDB_DATA key; + uint64_t count = 0; + int ret; + + key.dptr = (uint8_t *)discard_const(KEY); + key.dsize = strlen(KEY); + + ret = hash_count_init(mem_ctx, interval, test2_handler, &count, &hc); + assert(ret == 0); + + ret = hash_count_increment(hc, key); + assert(ret == 0); + assert(count == 1); + + hash_count_expire(hc, &ret); + assert(ret == 0); + + ret = hash_count_increment(hc, key); + assert(ret == 0); + assert(count == 2); + + sleep(2); + + ret = hash_count_increment(hc, key); + assert(ret == 0); + assert(count == 1); + + sleep(2); + + hash_count_expire(hc, &ret); + assert(ret == 1); + + talloc_free(hc); + ret = talloc_get_size(mem_ctx); + assert(ret == 0); + + talloc_free(mem_ctx); +} + +int main(void) +{ + do_test1(); + do_test2(); + + return 0; +} diff --git a/ctdb/wscript b/ctdb/wscript index 9e99fa2dd0e..fe0a8a23dba 100644 --- a/ctdb/wscript +++ b/ctdb/wscript @@ -390,7 +390,8 @@ def build(bld): '''db_hash.c srvid.c reqid.c pkt_read.c pkt_write.c comm.c logging.c rb_tree.c tunable.c - pidfile.c run_proc.c'''), + pidfile.c run_proc.c + hash_count.c'''), deps='''samba-util sys_rw tevent-util replace talloc tevent tdb''') @@ -738,6 +739,7 @@ def build(bld): 'run_proc_test', 'sock_daemon_test', 'sock_io_test', + 'hash_count_test' ] for target in ctdb_unit_tests: |