ctdb-common: Add hash_count abstraction

Signed-off-by: Amitay Isaacs <amitay@gmail.com>
Reviewed-by: Martin Schwenke <martin@meltin.net>

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(&current_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(&current_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: