dovecot-2.2: director: Optimized adding users to linked list dur...
dovecot at dovecot.org
dovecot at dovecot.org
Sun May 20 03:26:32 EEST 2012
details: http://hg.dovecot.org/dovecot-2.2/rev/0b4295b48941
changeset: 14468:0b4295b48941
user: Timo Sirainen <tss at iki.fi>
date: Thu Apr 19 21:51:48 2012 +0300
description:
director: Optimized adding users to linked list during handshake.
diffstat:
src/director/Makefile.am | 20 ++++++-
src/director/director-connection.c | 4 +-
src/director/director-request.c | 2 +-
src/director/director.c | 2 +-
src/director/test-user-directory.c | 104 +++++++++++++++++++++++++++++++++++++
src/director/user-directory.c | 83 ++++++++++++++++++++++++----
src/director/user-directory.h | 3 +-
7 files changed, 199 insertions(+), 19 deletions(-)
diffs (truncated from 327 to 300 lines):
diff -r 110673e82868 -r 0b4295b48941 src/director/Makefile.am
--- a/src/director/Makefile.am Thu Apr 19 20:29:25 2012 +0300
+++ b/src/director/Makefile.am Thu Apr 19 21:51:48 2012 +0300
@@ -4,6 +4,7 @@
AM_CPPFLAGS = \
-I$(top_srcdir)/src/lib \
+ -I$(top_srcdir)/src/lib-test \
-I$(top_srcdir)/src/lib-auth \
-I$(top_srcdir)/src/lib-imap \
-I$(top_srcdir)/src/lib-settings \
@@ -40,10 +41,27 @@
notify-connection.h \
user-directory.h
-noinst_PROGRAMS = director-test
+noinst_PROGRAMS = director-test $(test_programs)
director_test_LDADD = $(LIBDOVECOT)
director_test_DEPENDENCIES = $(LIBDOVECOT_DEPS)
director_test_SOURCES = \
director-test.c
+
+test_programs = \
+ test-user-directory
+
+test_libs = \
+ ../lib-test/libtest.la \
+ ../lib/liblib.la
+
+test_user_directory_SOURCES = test-user-directory.c
+test_user_directory_LDADD = user-directory.o $(test_libs)
+test_user_directory_DEPENDENCIES = user-directory.o $(test_libs)
+
+check: check-am check-test
+check-test: all-am
+ for bin in $(test_programs); do \
+ if ! $(RUN_TEST) ./$$bin; then exit 1; fi; \
+ done
diff -r 110673e82868 -r 0b4295b48941 src/director/director-connection.c
--- a/src/director/director-connection.c Thu Apr 19 20:29:25 2012 +0300
+++ b/src/director/director-connection.c Thu Apr 19 21:51:48 2012 +0300
@@ -540,7 +540,7 @@
}
if (director_user_refresh(conn, username_hash,
- host, ioloop_time, FALSE, &user)) {
+ host, (time_t)-1, FALSE, &user)) {
i_assert(!user->weak);
director_update_user(conn->dir, conn->host, user);
}
@@ -674,7 +674,7 @@
}
if (director_user_refresh(conn, username_hash,
- host, ioloop_time, weak, &user)) {
+ host, (time_t)-1, weak, &user)) {
if (!user->weak)
director_update_user(conn->dir, src_host, user);
else {
diff -r 110673e82868 -r 0b4295b48941 src/director/director-request.c
--- a/src/director/director-request.c Thu Apr 19 20:29:25 2012 +0300
+++ b/src/director/director-request.c Thu Apr 19 21:51:48 2012 +0300
@@ -225,7 +225,7 @@
return FALSE;
}
user = user_directory_add(dir->users, request->username_hash,
- host, ioloop_time);
+ host, (time_t)-1);
}
i_assert(!user->weak);
diff -r 110673e82868 -r 0b4295b48941 src/director/director.c
--- a/src/director/director.c Thu Apr 19 20:29:25 2012 +0300
+++ b/src/director/director.c Thu Apr 19 21:51:48 2012 +0300
@@ -582,7 +582,7 @@
user = user_directory_lookup(dir->users, username_hash);
if (user == NULL) {
user = user_directory_add(dir->users, username_hash,
- host, ioloop_time);
+ host, (time_t)-1);
} else {
if (user->host == host) {
/* user is already in this host */
diff -r 110673e82868 -r 0b4295b48941 src/director/test-user-directory.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/director/test-user-directory.c Thu Apr 19 21:51:48 2012 +0300
@@ -0,0 +1,104 @@
+/* Copyright (c) 2012 Dovecot authors, see the included COPYING file */
+
+#include "lib.h"
+#include "ioloop.h"
+#include "mail-user-hash.h"
+#include "mail-host.h"
+#include "user-directory.h"
+#include "test-common.h"
+
+#include <stdlib.h>
+
+#define USER_DIR_TIMEOUT 1000000
+
+unsigned int mail_user_hash(const char *username ATTR_UNUSED,
+ const char *format ATTR_UNUSED) { return 0; }
+
+static void
+verify_user_directory(struct user_directory *dir, unsigned int user_count)
+{
+ struct user_directory_iter *iter;
+ struct user *user, *prev = NULL;
+ unsigned int prev_stamp = 0, iter_count = 0;
+
+ iter = user_directory_iter_init(dir);
+ while ((user = user_directory_iter_next(iter)) != NULL) {
+ test_assert(prev_stamp <= user->timestamp);
+ test_assert(user->prev == prev);
+ test_assert(prev == NULL || user->prev->next == user);
+
+ iter_count++;
+ prev = user;
+ }
+ test_assert(prev == NULL || prev->next == NULL);
+ user_directory_iter_deinit(&iter);
+ test_assert(iter_count == user_count);
+}
+
+static void test_user_directory_ascending(void)
+{
+ const unsigned int count = 100000;
+ struct user_directory *dir;
+ struct mail_host *host = t_new(struct mail_host, 1);
+ unsigned int i;
+
+ test_begin("user directory ascending");
+ dir = user_directory_init(USER_DIR_TIMEOUT, "%u");
+ user_directory_add(dir, 1, host, ioloop_time + count+1);
+
+ for (i = 0; i < count; i++)
+ user_directory_add(dir, i+2, host, ioloop_time + i);
+ verify_user_directory(dir, count+1);
+ user_directory_deinit(&dir);
+ test_end();
+}
+
+static void test_user_directory_descending(void)
+{
+ const unsigned int count = 1000;
+ struct user_directory *dir;
+ struct mail_host *host = t_new(struct mail_host, 1);
+ unsigned int i;
+
+ test_begin("user directory descending");
+ dir = user_directory_init(USER_DIR_TIMEOUT, "%u");
+
+ for (i = 0; i < count; i++)
+ user_directory_add(dir, i+1, host, ioloop_time - i);
+ verify_user_directory(dir, count);
+ user_directory_deinit(&dir);
+ test_end();
+}
+
+static void test_user_directory_random(void)
+{
+ struct user_directory *dir;
+ struct mail_host *host = t_new(struct mail_host, 1);
+ time_t timestamp;
+ unsigned int i, count = 10000 + rand()%10000;
+
+ test_begin("user directory random");
+ dir = user_directory_init(USER_DIR_TIMEOUT, "%u");
+ for (i = 0; i < count; i++) {
+ if (rand() % 10 == 0)
+ timestamp = (time_t)-1;
+ else
+ timestamp = ioloop_time-rand()%100;
+ user_directory_add(dir, i+1, host, timestamp);
+ }
+ verify_user_directory(dir, count);
+ user_directory_deinit(&dir);
+ test_end();
+}
+
+int main(void)
+{
+ static void (*test_functions[])(void) = {
+ test_user_directory_ascending,
+ test_user_directory_descending,
+ test_user_directory_random,
+ NULL
+ };
+ ioloop_time = 1234567890;
+ return test_run(test_functions);
+}
diff -r 110673e82868 -r 0b4295b48941 src/director/user-directory.c
--- a/src/director/user-directory.c Thu Apr 19 20:29:25 2012 +0300
+++ b/src/director/user-directory.c Thu Apr 19 21:51:48 2012 +0300
@@ -24,6 +24,7 @@
struct hash_table *hash;
/* sorted by time */
struct user *head, *tail;
+ struct user *prev_insert_pos;
ARRAY_DEFINE(iters, struct user_directory_iter *);
@@ -42,6 +43,9 @@
if ((*iterp)->pos == user)
(*iterp)->pos = user->next;
}
+
+ if (dir->prev_insert_pos == user)
+ dir->prev_insert_pos = user->next;
}
static void user_free(struct user_directory *dir, struct user *user)
@@ -79,11 +83,61 @@
return hash_table_lookup(dir->hash, POINTER_CAST(username_hash));
}
+static void
+user_directory_insert_backwards(struct user_directory *dir,
+ struct user *pos, struct user *user)
+{
+ for (; pos != NULL; pos = pos->prev) {
+ if ((time_t)pos->timestamp <= user->timestamp)
+ break;
+ }
+ if (pos == NULL)
+ DLLIST2_PREPEND(&dir->head, &dir->tail, user);
+ else {
+ user->prev = pos;
+ user->next = pos->next;
+ user->prev->next = user;
+ if (user->next != NULL)
+ user->next->prev = user;
+ else
+ dir->tail = user;
+ }
+}
+
+static void
+user_directory_insert_forwards(struct user_directory *dir,
+ struct user *pos, struct user *user)
+{
+ for (; pos != NULL; pos = pos->next) {
+ if ((time_t)pos->timestamp >= user->timestamp)
+ break;
+ }
+ if (pos == NULL)
+ DLLIST2_APPEND(&dir->head, &dir->tail, user);
+ else {
+ user->prev = pos->prev;
+ user->next = pos;
+ if (user->prev != NULL)
+ user->prev->next = user;
+ else
+ dir->head = user;
+ user->next->prev = user;
+ }
+}
+
struct user *
user_directory_add(struct user_directory *dir, unsigned int username_hash,
struct mail_host *host, time_t timestamp)
{
- struct user *user, *pos;
+ struct user *user;
+
+ if (timestamp == (time_t)-1) {
+ /* make sure we add it at the end */
+ timestamp = ioloop_time;
+ if (dir->tail != NULL &&
+ timestamp < (time_t)dir->tail->timestamp)
+ timestamp = (time_t)dir->tail->timestamp;
+ }
user = i_new(struct user, 1);
user->username_hash = username_hash;
@@ -94,21 +148,24 @@
if (dir->tail == NULL || (time_t)dir->tail->timestamp <= timestamp)
DLLIST2_APPEND(&dir->head, &dir->tail, user);
else {
- /* need to insert to correct position */
- for (pos = dir->tail; pos != NULL; pos = pos->prev) {
- if ((time_t)pos->timestamp <= timestamp)
- break;
- }
- if (pos == NULL)
- DLLIST2_PREPEND(&dir->head, &dir->tail, user);
- else {
- user->prev = pos;
- user->next = pos->next;
- user->prev->next = user;
- user->next->prev = user;
+ /* need to insert to correct position. we should get here
+ only when handshaking. the handshaking USER requests should
+ come sorted by timestamp. so keep track of the previous
+ insert position, the next USER should be inserted after
+ it. */
+ if (dir->prev_insert_pos == NULL) {
+ /* find the position starting from tail */
More information about the dovecot-cvs
mailing list