dovecot-2.2: dsync: Rewritten syncing for mailbox renames.
dovecot at dovecot.org
dovecot at dovecot.org
Thu Sep 6 01:25:38 EEST 2012
details: http://hg.dovecot.org/dovecot-2.2/rev/0af20585964d
changeset: 15035:0af20585964d
user: Timo Sirainen <tss at iki.fi>
date: Thu Sep 06 01:25:23 2012 +0300
description:
dsync: Rewritten syncing for mailbox renames.
A few things didn't go as I originally intended in the algorithm, but it
appears to give consistent results now. :) But the algorithm should probably
be looked at more closely at some point.
diffstat:
src/doveadm/dsync/Makefile.am | 19 +
src/doveadm/dsync/dsync-brain-mailbox-tree.c | 13 +-
src/doveadm/dsync/dsync-mailbox-tree-fill.c | 30 +-
src/doveadm/dsync/dsync-mailbox-tree-private.h | 16 +-
src/doveadm/dsync/dsync-mailbox-tree-sync.c | 841 +++++++++++++++++-----
src/doveadm/dsync/dsync-mailbox-tree.c | 151 +++-
src/doveadm/dsync/dsync-mailbox-tree.h | 23 +-
src/doveadm/dsync/dsync-slave-io.c | 51 +-
src/doveadm/dsync/test-dsync-mailbox-tree-sync.c | 639 +++++++++++++++++
9 files changed, 1539 insertions(+), 244 deletions(-)
diffs (truncated from 2199 to 300 lines):
diff -r 7efef678bca8 -r 0af20585964d src/doveadm/dsync/Makefile.am
--- a/src/doveadm/dsync/Makefile.am Thu Sep 06 01:13:03 2012 +0300
+++ b/src/doveadm/dsync/Makefile.am Thu Sep 06 01:25:23 2012 +0300
@@ -49,3 +49,22 @@
dsync-slave.h \
dsync-slave-private.h \
dsync-transaction-log-scan.h
+
+test_programs = \
+ test-dsync-mailbox-tree-sync
+
+noinst_PROGRAMS = $(test_programs)
+
+test_libs = \
+ ../../lib-test/libtest.la \
+ ../../lib/liblib.la
+
+test_dsync_mailbox_tree_sync_SOURCES = test-dsync-mailbox-tree-sync.c
+test_dsync_mailbox_tree_sync_LDADD = dsync-mailbox-tree-sync.lo dsync-mailbox-tree.lo $(test_libs)
+test_dsync_mailbox_tree_sync_DEPENDENCIES = dsync-mailbox-tree-sync.lo dsync-mailbox-tree.lo $(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 7efef678bca8 -r 0af20585964d src/doveadm/dsync/dsync-brain-mailbox-tree.c
--- a/src/doveadm/dsync/dsync-brain-mailbox-tree.c Thu Sep 06 01:13:03 2012 +0300
+++ b/src/doveadm/dsync/dsync-brain-mailbox-tree.c Thu Sep 06 01:25:23 2012 +0300
@@ -64,10 +64,12 @@
dsync_brain_check_namespaces(brain);
brain->local_mailbox_tree =
- dsync_mailbox_tree_init(brain->hierarchy_sep);
+ dsync_mailbox_tree_init(brain->hierarchy_sep,
+ doveadm_settings->dsync_alt_char[0]);
/* we'll convert remote mailbox names to use our own separator */
brain->remote_mailbox_tree =
- dsync_mailbox_tree_init(brain->hierarchy_sep);
+ dsync_mailbox_tree_init(brain->hierarchy_sep,
+ doveadm_settings->dsync_alt_char[0]);
/* fill the local mailbox tree */
if (brain->sync_ns != NULL) {
@@ -329,6 +331,13 @@
if (node == NULL)
return;
+ if (!other_del->delete_mailbox &&
+ other_del->timestamp <= node->last_renamed_or_created) {
+ /* we don't want to delete this directory, we already have a
+ newer timestamp for it */
+ return;
+ }
+
/* make a node for it in the other mailbox tree */
name = dsync_mailbox_node_get_full_name(tree, node);
other_node = dsync_mailbox_tree_get(other_tree, name);
diff -r 7efef678bca8 -r 0af20585964d src/doveadm/dsync/dsync-mailbox-tree-fill.c
--- a/src/doveadm/dsync/dsync-mailbox-tree-fill.c Thu Sep 06 01:13:03 2012 +0300
+++ b/src/doveadm/dsync/dsync-mailbox-tree-fill.c Thu Sep 06 01:25:23 2012 +0300
@@ -111,6 +111,7 @@
node = rec->type == MAILBOX_LOG_RECORD_DELETE_MAILBOX ? NULL :
dsync_mailbox_tree_find_sha(tree, ns, rec->mailbox_guid);
+ timestamp = mailbox_log_record_get_timestamp(rec);
switch (rec->type) {
case MAILBOX_LOG_RECORD_DELETE_MAILBOX:
guid_p = rec->mailbox_guid;
@@ -121,26 +122,39 @@
}
del = array_append_space(&tree->deletes);
del->delete_mailbox = TRUE;
+ del->timestamp = timestamp;
memcpy(del->guid, rec->mailbox_guid, sizeof(del->guid));
break;
case MAILBOX_LOG_RECORD_DELETE_DIR:
if (node != NULL) {
- /* mailbox exists again, skip it */
+ /* directory exists again, skip it */
break;
}
+ /* we don't know what directory name was deleted,
+ just its hash. if the name still exists on the other
+ dsync side, it can match this deletion to the
+ name. */
del = array_append_space(&tree->deletes);
+ del->timestamp = timestamp;
memcpy(del->guid, rec->mailbox_guid, sizeof(del->guid));
break;
+ case MAILBOX_LOG_RECORD_CREATE_DIR:
+ if (node == NULL) {
+ /* directory has been deleted again, skip it */
+ break;
+ }
+ /* notify the remote that we want to keep this
+ directory created (unless remote has a newer delete
+ timestamp) */
+ node->last_renamed_or_created = timestamp;
+ break;
case MAILBOX_LOG_RECORD_RENAME:
+ if (node != NULL)
+ node->last_renamed_or_created = timestamp;
+ break;
case MAILBOX_LOG_RECORD_SUBSCRIBE:
case MAILBOX_LOG_RECORD_UNSUBSCRIBE:
- if (node == NULL)
- break;
-
- timestamp = mailbox_log_record_get_timestamp(rec);
- if (rec->type == MAILBOX_LOG_RECORD_RENAME)
- node->last_renamed = timestamp;
- else
+ if (node != NULL)
node->last_subscription_change = timestamp;
break;
}
diff -r 7efef678bca8 -r 0af20585964d src/doveadm/dsync/dsync-mailbox-tree-private.h
--- a/src/doveadm/dsync/dsync-mailbox-tree-private.h Thu Sep 06 01:13:03 2012 +0300
+++ b/src/doveadm/dsync/dsync-mailbox-tree-private.h Thu Sep 06 01:25:23 2012 +0300
@@ -5,7 +5,9 @@
struct dsync_mailbox_tree {
pool_t pool;
- char sep, sep_str[2], remote_sep;
+ char sep, sep_str[2], remote_sep, alt_char;
+ /* root node isn't part of the real mailbox tree. its name is "" and
+ it has no siblings */
struct dsync_mailbox_node root;
unsigned int iter_count;
@@ -20,4 +22,16 @@
void dsync_mailbox_tree_build_name128_hash(struct dsync_mailbox_tree *tree);
+int dsync_mailbox_node_name_cmp(struct dsync_mailbox_node *const *n1,
+ struct dsync_mailbox_node *const *n2);
+
+void dsync_mailbox_tree_node_attach(struct dsync_mailbox_node *node,
+ struct dsync_mailbox_node *parent);
+void dsync_mailbox_tree_node_detach(struct dsync_mailbox_node *node);
+
+struct dsync_mailbox_tree *
+dsync_mailbox_tree_dup(const struct dsync_mailbox_tree *src);
+bool dsync_mailbox_trees_equal(struct dsync_mailbox_tree *tree1,
+ struct dsync_mailbox_tree *tree2);
+
#endif
diff -r 7efef678bca8 -r 0af20585964d src/doveadm/dsync/dsync-mailbox-tree-sync.c
--- a/src/doveadm/dsync/dsync-mailbox-tree-sync.c Thu Sep 06 01:13:03 2012 +0300
+++ b/src/doveadm/dsync/dsync-mailbox-tree-sync.c Thu Sep 06 01:25:23 2012 +0300
@@ -2,10 +2,18 @@
#include "lib.h"
#include "array.h"
+#include "buffer.h"
+#include "str.h"
+#include "md5.h"
+#include "hex-binary.h"
#include "aqueue.h"
#include "hash.h"
#include "dsync-mailbox-tree-private.h"
+#define TEMP_MAX_NAME_LEN 100
+#define TEMP_SUFFIX_MAX_LEN (sizeof("temp-")-1 + 8)
+#define TEMP_SUFFIX_FORMAT "temp-%x"
+
struct dsync_mailbox_tree_bfs_iter {
struct dsync_mailbox_tree *tree;
@@ -56,12 +64,6 @@
return TRUE;
}
-static bool
-dsync_mailbox_tree_bfs_iter_is_eob(struct dsync_mailbox_tree_bfs_iter *iter)
-{
- return iter->cur == NULL;
-}
-
static void
dsync_mailbox_tree_bfs_iter_deinit(struct dsync_mailbox_tree_bfs_iter **_iter)
{
@@ -74,10 +76,35 @@
i_free(iter);
}
-static int dsync_mailbox_node_sync_cmp(struct dsync_mailbox_node *const *n1,
- struct dsync_mailbox_node *const *n2)
+static void
+sync_add_dir_change(struct dsync_mailbox_tree_sync_ctx *ctx,
+ const struct dsync_mailbox_node *node,
+ enum dsync_mailbox_tree_sync_type type)
{
- return strcmp((*n1)->name, (*n2)->name);
+ struct dsync_mailbox_tree_sync_change *change;
+ const char *name;
+
+ name = dsync_mailbox_node_get_full_name(ctx->local_tree, node);
+
+ change = array_append_space(&ctx->changes);
+ change->type = type;
+ change->ns = node->ns;
+ change->full_name = p_strdup(ctx->pool, name);
+}
+
+static void
+sync_add_create_change(struct dsync_mailbox_tree_sync_ctx *ctx,
+ const struct dsync_mailbox_node *node, const char *name)
+{
+ struct dsync_mailbox_tree_sync_change *change;
+
+ change = array_append_space(&ctx->changes);
+ change->type = DSYNC_MAILBOX_TREE_SYNC_TYPE_CREATE_BOX;
+ change->ns = node->ns;
+ change->full_name = p_strdup(ctx->pool, name);
+ memcpy(change->mailbox_guid, node->mailbox_guid,
+ sizeof(change->mailbox_guid));
+ change->uid_validity = node->uid_validity;
}
static void sort_siblings(ARRAY_TYPE(dsync_mailbox_node) *siblings)
@@ -85,7 +112,7 @@
struct dsync_mailbox_node *const *nodes;
unsigned int i, count;
- array_sort(siblings, dsync_mailbox_node_sync_cmp);
+ array_sort(siblings, dsync_mailbox_node_name_cmp);
nodes = array_get(siblings, &count);
if (count == 0)
@@ -128,11 +155,13 @@
/* for the rest of this sync assume that the mailbox has
already been deleted */
if (other_node != NULL) {
+ hash_table_remove(other_tree->guid_hash, guid_p);
other_node->existence = DSYNC_MAILBOX_NODE_DELETED;
memset(other_node->mailbox_guid, 0,
sizeof(other_node->mailbox_guid));
}
memset(node->mailbox_guid, 0, sizeof(node->mailbox_guid));
+ node->uid_validity = 0;
}
static void
@@ -153,7 +182,7 @@
parent = node->parent;
}
if (node->existence == DSYNC_MAILBOX_NODE_DELETED &&
- !guid_128_is_empty(node->mailbox_guid))
+ !dsync_mailbox_node_is_dir(node))
sync_delete_mailbox(ctx, tree, node);
array_append(&siblings, &node, 1);
}
@@ -161,44 +190,6 @@
dsync_mailbox_tree_bfs_iter_deinit(&iter);
}
-static struct dsync_mailbox_node *
-sync_find_node(struct dsync_mailbox_tree *tree,
- struct dsync_mailbox_node *other_node)
-{
- struct dsync_mailbox_node *n1, *n2;
- const uint8_t *guid_p;
-
- if (!guid_128_is_empty(other_node->mailbox_guid)) {
- guid_p = other_node->mailbox_guid;
- return hash_table_lookup(tree->guid_hash, guid_p);
- }
- /* if we can find a node that has all of the same mailboxes as children,
- return it. */
- for (n1 = other_node->first_child; n1 != NULL; n1 = n1->next) {
- if (!guid_128_is_empty(n1->mailbox_guid))
- break;
- }
- if (n1 == NULL)
- return NULL;
- guid_p = n1->mailbox_guid;
- n2 = hash_table_lookup(tree->guid_hash, guid_p);
- if (n2 == NULL)
- return NULL;
-
- /* note that all of the nodes are sorted at this point. */
- n1 = n1->parent->first_child;
- n2 = n2->parent->first_child;
- for (; n1 != NULL && n2 != NULL; n1 = n1->next, n2 = n2->next) {
- if (strcmp(n1->name, n2->name) != 0 ||
- memcmp(n1->mailbox_guid, n2->mailbox_guid,
- sizeof(n1->mailbox_guid)) != 0)
- break;
- }
- if (n1 != NULL || n2 != NULL)
- return NULL;
- return n2;
-}
-
static bool node_names_equal(const struct dsync_mailbox_node *n1,
const struct dsync_mailbox_node *n2)
{
@@ -212,18 +203,6 @@
More information about the dovecot-cvs
mailing list