summaryrefslogtreecommitdiffstats
path: root/src/doveadm/dsync/dsync-mailbox-tree-sync.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/doveadm/dsync/dsync-mailbox-tree-sync.c')
-rw-r--r--src/doveadm/dsync/dsync-mailbox-tree-sync.c1473
1 files changed, 1473 insertions, 0 deletions
diff --git a/src/doveadm/dsync/dsync-mailbox-tree-sync.c b/src/doveadm/dsync/dsync-mailbox-tree-sync.c
new file mode 100644
index 0000000..e4a50ae
--- /dev/null
+++ b/src/doveadm/dsync/dsync-mailbox-tree-sync.c
@@ -0,0 +1,1473 @@
+/* Copyright (c) 2013-2018 Dovecot authors, see the included COPYING file */
+
+#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-brain-private.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;
+
+ ARRAY(struct dsync_mailbox_node *) queue_arr;
+ struct aqueue *queue;
+ struct dsync_mailbox_node *cur;
+};
+
+struct dsync_mailbox_tree_sync_ctx {
+ pool_t pool;
+ struct dsync_mailbox_tree *local_tree, *remote_tree;
+ enum dsync_mailbox_trees_sync_type sync_type;
+ enum dsync_mailbox_trees_sync_flags sync_flags;
+ unsigned int combined_mailboxes_count;
+
+ ARRAY(struct dsync_mailbox_tree_sync_change) changes;
+ unsigned int change_idx;
+ bool failed;
+};
+
+static struct dsync_mailbox_tree_bfs_iter *
+dsync_mailbox_tree_bfs_iter_init(struct dsync_mailbox_tree *tree)
+{
+ struct dsync_mailbox_tree_bfs_iter *iter;
+
+ iter = i_new(struct dsync_mailbox_tree_bfs_iter, 1);
+ iter->tree = tree;
+ i_array_init(&iter->queue_arr, 32);
+ iter->queue = aqueue_init(&iter->queue_arr.arr);
+ iter->cur = tree->root.first_child;
+ return iter;
+}
+
+static bool
+dsync_mailbox_tree_bfs_iter_next(struct dsync_mailbox_tree_bfs_iter *iter,
+ struct dsync_mailbox_node **node_r)
+{
+ if (iter->cur == NULL) {
+ if (aqueue_count(iter->queue) == 0)
+ return FALSE;
+ iter->cur = array_idx_elem(&iter->queue_arr,
+ aqueue_idx(iter->queue, 0));
+ aqueue_delete_tail(iter->queue);
+ }
+ *node_r = iter->cur;
+
+ if (iter->cur->first_child != NULL)
+ aqueue_append(iter->queue, &iter->cur->first_child);
+ iter->cur = iter->cur->next;
+ return TRUE;
+}
+
+static void
+dsync_mailbox_tree_bfs_iter_deinit(struct dsync_mailbox_tree_bfs_iter **_iter)
+{
+ struct dsync_mailbox_tree_bfs_iter *iter = *_iter;
+
+ *_iter = NULL;
+
+ aqueue_deinit(&iter->queue);
+ array_free(&iter->queue_arr);
+ i_free(iter);
+}
+
+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)
+{
+ struct dsync_mailbox_tree_sync_change *change;
+ const char *name;
+
+ i_assert(ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL);
+
+ 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;
+
+ i_assert(ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL);
+
+ 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)
+{
+ struct dsync_mailbox_node *const *nodes;
+ unsigned int i, count;
+
+ array_sort(siblings, dsync_mailbox_node_name_cmp);
+
+ nodes = array_get(siblings, &count);
+ if (count == 0)
+ return;
+
+ nodes[0]->parent->first_child = nodes[0];
+ for (i = 1; i < count; i++)
+ nodes[i-1]->next = nodes[i];
+ nodes[count-1]->next = NULL;
+}
+
+static void
+sync_set_node_deleted(struct dsync_mailbox_tree *tree,
+ struct dsync_mailbox_node *node)
+{
+ const uint8_t *guid_p;
+
+ /* for the rest of this sync assume that the mailbox has
+ already been deleted */
+ guid_p = node->mailbox_guid;
+ hash_table_remove(tree->guid_hash, guid_p);
+
+ node->existence = DSYNC_MAILBOX_NODE_DELETED;
+ memset(node->mailbox_guid, 0, sizeof(node->mailbox_guid));
+ node->uid_validity = 0;
+}
+
+static void
+sync_delete_mailbox_node(struct dsync_mailbox_tree_sync_ctx *ctx,
+ struct dsync_mailbox_tree *tree,
+ struct dsync_mailbox_node *node, const char *reason)
+{
+ struct dsync_mailbox_tree_sync_change *change;
+ const char *name;
+
+ if ((ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_DEBUG) != 0 &&
+ tree == ctx->local_tree) {
+ i_debug("brain %c: Deleting mailbox '%s' (GUID %s): %s",
+ (ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_MASTER_BRAIN) != 0 ? 'M' : 'S',
+ dsync_mailbox_node_get_full_name(tree, node),
+ guid_128_to_string(node->mailbox_guid), reason);
+ }
+
+ if (tree == ctx->local_tree &&
+ node->existence != DSYNC_MAILBOX_NODE_DELETED) {
+ /* delete this mailbox locally */
+ i_assert(ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL);
+ change = array_append_space(&ctx->changes);
+ change->type = DSYNC_MAILBOX_TREE_SYNC_TYPE_DELETE_BOX;
+ change->ns = node->ns;
+ name = dsync_mailbox_node_get_full_name(tree, node);
+ change->full_name = p_strdup(ctx->pool, name);
+ memcpy(change->mailbox_guid, node->mailbox_guid,
+ sizeof(change->mailbox_guid));
+ }
+ sync_set_node_deleted(tree, node);
+}
+
+static void
+sync_delete_mailbox(struct dsync_mailbox_tree_sync_ctx *ctx,
+ struct dsync_mailbox_tree *tree,
+ struct dsync_mailbox_node *node, const char *reason)
+{
+ struct dsync_mailbox_tree *other_tree;
+ struct dsync_mailbox_node *other_node;
+ const uint8_t *guid_p;
+
+ other_tree = tree == ctx->local_tree ?
+ ctx->remote_tree : ctx->local_tree;
+ guid_p = node->mailbox_guid;
+ other_node = hash_table_lookup(other_tree->guid_hash, guid_p);
+ if (other_node == NULL) {
+ /* doesn't exist / already deleted */
+ } else {
+ sync_delete_mailbox_node(ctx, other_tree, other_node, reason);
+ }
+ sync_delete_mailbox_node(ctx, tree, node, reason);
+}
+
+static void
+sync_tree_sort_and_delete_mailboxes(struct dsync_mailbox_tree_sync_ctx *ctx,
+ struct dsync_mailbox_tree *tree,
+ bool twoway_sync)
+{
+ struct dsync_mailbox_tree_bfs_iter *iter;
+ struct dsync_mailbox_node *node, *parent = NULL;
+ ARRAY_TYPE(dsync_mailbox_node) siblings;
+
+ t_array_init(&siblings, 64);
+
+ iter = dsync_mailbox_tree_bfs_iter_init(tree);
+ while (dsync_mailbox_tree_bfs_iter_next(iter, &node)) {
+ if (node->parent != parent) {
+ sort_siblings(&siblings);
+ array_clear(&siblings);
+ parent = node->parent;
+ }
+ if (node->existence == DSYNC_MAILBOX_NODE_DELETED &&
+ !dsync_mailbox_node_is_dir(node)) {
+ if (twoway_sync) {
+ /* this mailbox was deleted. delete it from the
+ other side as well */
+ sync_delete_mailbox(ctx, tree, node,
+ "Mailbox has been deleted");
+ } else {
+ /* treat the node as if it didn't exist. it'll
+ get either recreated or deleted later. in
+ any case this function must handle all
+ existence=DELETED mailbox nodes by changing
+ them into directories (setting GUID=0) or
+ we'll assert-crash later */
+ sync_set_node_deleted(tree, node);
+ }
+ }
+ ctx->combined_mailboxes_count++;
+ array_push_back(&siblings, &node);
+ }
+ sort_siblings(&siblings);
+ dsync_mailbox_tree_bfs_iter_deinit(&iter);
+}
+
+static bool node_names_equal(const struct dsync_mailbox_node *n1,
+ const struct dsync_mailbox_node *n2)
+{
+ while (n1 != NULL && n2 != NULL) {
+ if (strcmp(n1->name, n2->name) != 0)
+ return FALSE;
+ n1 = n1->parent;
+ n2 = n2->parent;
+ }
+ return n1 == NULL && n2 == NULL;
+}
+
+static void
+dsync_mailbox_tree_node_attach_sorted(struct dsync_mailbox_node *node,
+ struct dsync_mailbox_node *parent)
+{
+ struct dsync_mailbox_node **p;
+
+ node->parent = parent;
+ for (p = &parent->first_child; *p != NULL; p = &(*p)->next) {
+ if (dsync_mailbox_node_name_cmp(p, &node) > 0)
+ break;
+ }
+ node->next = *p;
+ *p = node;
+}
+
+static void
+dsync_mailbox_tree_node_move_sorted(struct dsync_mailbox_node *node,
+ struct dsync_mailbox_node *parent)
+{
+ /* detach from old parent */
+ dsync_mailbox_tree_node_detach(node);
+ /* attach to new parent */
+ dsync_mailbox_tree_node_attach_sorted(node, parent);
+}
+
+static struct dsync_mailbox_node *
+sorted_tree_get(struct dsync_mailbox_tree *tree, const char *name)
+{
+ struct dsync_mailbox_node *node, *parent, *ret;
+
+ node = ret = dsync_mailbox_tree_get(tree, name);
+ while (node->parent != NULL &&
+ node->existence == DSYNC_MAILBOX_NODE_NONEXISTENT) {
+ parent = node->parent;
+ dsync_mailbox_tree_node_detach(node);
+ dsync_mailbox_tree_node_attach_sorted(node, parent);
+ node = parent;
+ }
+ return ret;
+}
+
+static struct dsync_mailbox_node *
+sync_node_new(struct dsync_mailbox_tree *tree,
+ struct dsync_mailbox_node **pos,
+ struct dsync_mailbox_node *parent,
+ const struct dsync_mailbox_node *src)
+{
+ struct dsync_mailbox_node *node;
+
+ node = p_new(tree->pool, struct dsync_mailbox_node, 1);
+ node->existence = DSYNC_MAILBOX_NODE_NONEXISTENT;
+ node->name = p_strdup(tree->pool, src->name);
+ node->sync_temporary_name = src->sync_temporary_name;
+ node->ns = src->ns;
+ node->parent = parent;
+ node->next = *pos;
+ *pos = node;
+ return node;
+}
+
+static struct dsync_mailbox_node *
+sorted_tree_get_by_node_name(struct dsync_mailbox_tree *tree,
+ struct dsync_mailbox_tree *other_tree,
+ struct dsync_mailbox_node *other_node)
+{
+ const char *parent_name;
+
+ if (other_node == &other_tree->root)
+ return &tree->root;
+
+ parent_name = dsync_mailbox_node_get_full_name(other_tree, other_node);
+ return sorted_tree_get(tree, parent_name);
+}
+
+static bool node_has_child(struct dsync_mailbox_node *parent, const char *name)
+{
+ struct dsync_mailbox_node *node;
+
+ for (node = parent->first_child; node != NULL; node = node->next) {
+ if (strcmp(node->name, name) == 0)
+ return TRUE;
+ }
+ return FALSE;
+}
+
+static bool
+node_has_existent_children(struct dsync_mailbox_node *node, bool dirs_ok)
+{
+ for (node = node->first_child; node != NULL; node = node->next) {
+ if (node->existence == DSYNC_MAILBOX_NODE_EXISTS &&
+ (dirs_ok || !dsync_mailbox_node_is_dir(node)))
+ return TRUE;
+ if (node_has_existent_children(node, dirs_ok))
+ return TRUE;
+ }
+ return FALSE;
+}
+
+static bool node_is_existent(struct dsync_mailbox_node *node)
+{
+ if (node->existence == DSYNC_MAILBOX_NODE_EXISTS)
+ return TRUE;
+ return node_has_existent_children(node, TRUE);
+}
+
+static bool sync_node_is_namespace_prefix(struct dsync_mailbox_tree *tree,
+ struct dsync_mailbox_node *node)
+{
+ const char *full_name;
+ size_t prefix_len = node->ns == NULL ? 0 : node->ns->prefix_len;
+
+ if (strcmp(node->name, "INBOX") == 0 && node->parent == &tree->root)
+ return TRUE;
+
+ if (prefix_len == 0)
+ return FALSE;
+
+ full_name = dsync_mailbox_node_get_full_name(tree, node);
+ if (node->ns->prefix[prefix_len-1] == mail_namespace_get_sep(node->ns))
+ prefix_len--;
+ return strncmp(full_name, node->ns->prefix, prefix_len) == 0 &&
+ full_name[prefix_len] == '\0';
+}
+
+static void
+sync_rename_node_to_temp(struct dsync_mailbox_tree_sync_ctx *ctx,
+ struct dsync_mailbox_tree *tree,
+ struct dsync_mailbox_node *node,
+ struct dsync_mailbox_node *new_parent,
+ const char **reason_r)
+{
+ struct dsync_mailbox_tree_sync_change *change;
+ const char *old_name, *new_name, *p;
+ char name[TEMP_MAX_NAME_LEN+1];
+ buffer_t buf;
+ size_t prefix_len, max_prefix_len;
+ unsigned int counter = 1;
+
+ i_assert(!sync_node_is_namespace_prefix(tree, node));
+
+ buffer_create_from_data(&buf, name, sizeof(name));
+ max_prefix_len = TEMP_MAX_NAME_LEN - TEMP_SUFFIX_MAX_LEN - 1;
+ if (node->sync_temporary_name) {
+ /* the source name was also a temporary name. drop the
+ -<suffix> from it */
+ p = strrchr(node->name, '-');
+ i_assert(p != NULL);
+ if (max_prefix_len > (size_t)(p - node->name))
+ max_prefix_len = p - node->name;
+ }
+ str_append_max(&buf, node->name, max_prefix_len);
+ str_append_c(&buf, '-');
+ prefix_len = buf.used;
+
+ do {
+ str_truncate(&buf, prefix_len);
+ str_printfa(&buf, TEMP_SUFFIX_FORMAT, counter++);
+ /* the generated name is quite unlikely to exist,
+ but check anyway.. */
+ } while (node_has_child(node->parent, str_c(&buf)));
+
+ old_name = tree != ctx->local_tree ? NULL :
+ dsync_mailbox_node_get_full_name(tree, node);
+
+ *reason_r = t_strdup_printf("Renamed '%s' to '%s'", node->name, str_c(&buf));
+ node->name = p_strdup(tree->pool, str_c(&buf));
+ node->sync_temporary_name = TRUE;
+ node->last_renamed_or_created = 0;
+ dsync_mailbox_tree_node_move_sorted(node, new_parent);
+
+ if (tree == ctx->local_tree && node_is_existent(node)) {
+ /* we're modifying a local tree. remember this change. */
+ new_name = dsync_mailbox_node_get_full_name(tree, node);
+
+ i_assert(ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL);
+ i_assert(strcmp(old_name, "INBOX") != 0);
+ change = array_append_space(&ctx->changes);
+ change->type = DSYNC_MAILBOX_TREE_SYNC_TYPE_RENAME;
+ change->ns = node->ns;
+ change->full_name = p_strdup(ctx->pool, old_name);
+ change->rename_dest_name = p_strdup(ctx->pool, new_name);
+ }
+}
+
+static bool node_has_parent(struct dsync_mailbox_node *node,
+ struct dsync_mailbox_node *parent)
+{
+ for (; node != NULL; node = node->parent) {
+ if (node == parent)
+ return TRUE;
+ }
+ return FALSE;
+}
+
+static void
+sync_rename_node(struct dsync_mailbox_tree_sync_ctx *ctx,
+ struct dsync_mailbox_tree *tree,
+ struct dsync_mailbox_node *temp_node,
+ struct dsync_mailbox_node *node,
+ const struct dsync_mailbox_node *other_node,
+ const char **reason_r)
+{
+ struct dsync_mailbox_tree_sync_change *change;
+ struct dsync_mailbox_tree *other_tree;
+ struct dsync_mailbox_node *parent;
+ const char *name, *other_name;
+
+ i_assert(node != NULL);
+ i_assert(other_node != NULL);
+
+ /* move/rename node in the tree, so that its position/name is identical
+ to other_node (in other_tree). temp_node's name is changed to
+ temporary name (i.e. it assumes that node's name becomes temp_node's
+ original name) */
+ other_tree = tree == ctx->local_tree ?
+ ctx->remote_tree : ctx->local_tree;
+
+ parent = sorted_tree_get_by_node_name(tree, other_tree,
+ other_node->parent);
+ if (node_has_parent(parent, node)) {
+ /* don't introduce a loop. temporarily rename node
+ under root. */
+ sync_rename_node_to_temp(ctx, tree, node, &tree->root, reason_r);
+ *reason_r = t_strconcat(*reason_r, " (Don't introduce loop)", NULL);
+ return;
+ }
+ sync_rename_node_to_temp(ctx, tree, temp_node, temp_node->parent, reason_r);
+
+ /* get the old name before it's modified */
+ name = dsync_mailbox_node_get_full_name(tree, node);
+
+ /* set the new name */
+ *reason_r = t_strdup_printf("%s + Renamed '%s' to '%s'",
+ *reason_r, name, other_node->name);
+ node->name = p_strdup(tree->pool, other_node->name);
+ node->sync_temporary_name = other_node->sync_temporary_name;
+ node->last_renamed_or_created = other_node->last_renamed_or_created;
+ /* change node's parent if necessary. in any case detach+reattach it
+ sorted, because the nodes must be sorted by name, and the node's
+ name (or its parent) changed. */
+ dsync_mailbox_tree_node_move_sorted(node, parent);
+
+ if (tree == ctx->local_tree && node_is_existent(node)) {
+ /* we're modifying a local tree. remember this change. */
+ other_name = dsync_mailbox_node_get_full_name(other_tree, other_node);
+
+ i_assert(ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL);
+ i_assert(strcmp(name, "INBOX") != 0);
+ change = array_append_space(&ctx->changes);
+ change->type = DSYNC_MAILBOX_TREE_SYNC_TYPE_RENAME;
+ change->ns = node->ns;
+ change->full_name = p_strdup(ctx->pool, name);
+ change->rename_dest_name = p_strdup(ctx->pool, other_name);
+ }
+}
+
+static int node_mailbox_guids_cmp(struct dsync_mailbox_node *node1,
+ struct dsync_mailbox_node *node2)
+{
+ int ret;
+
+ while (node1 != NULL && node2 != NULL) {
+ if (node1->existence == DSYNC_MAILBOX_NODE_EXISTS &&
+ node2->existence != DSYNC_MAILBOX_NODE_EXISTS)
+ return -1;
+ if (node2->existence == DSYNC_MAILBOX_NODE_EXISTS &&
+ node1->existence != DSYNC_MAILBOX_NODE_EXISTS)
+ return 1;
+
+ ret = memcmp(node1->mailbox_guid, node2->mailbox_guid,
+ sizeof(node1->mailbox_guid));
+ if (ret != 0)
+ return ret;
+
+ ret = node_mailbox_guids_cmp(node1->first_child,
+ node2->first_child);
+ if (ret != 0)
+ return ret;
+ node1 = node1->next;
+ node2 = node2->next;
+ }
+ if (node1 == NULL && node2 == NULL)
+ return 0;
+ return node1 != NULL ? -1 : 1;
+}
+
+static int node_mailbox_names_cmp(struct dsync_mailbox_node *node1,
+ struct dsync_mailbox_node *node2)
+{
+ int ret;
+
+ while (node1 != NULL && node2 != NULL) {
+ ret = strcmp(node1->name, node2->name);
+ if (ret != 0)
+ return ret;
+
+ ret = node_mailbox_names_cmp(node1->first_child,
+ node2->first_child);
+ if (ret != 0)
+ return ret;
+ node1 = node1->next;
+ node2 = node2->next;
+ }
+ if (node1 == NULL && node2 == NULL)
+ return 0;
+ return node1 != NULL ? -1 : 1;
+}
+
+static int node_mailbox_trees_cmp(struct dsync_mailbox_node *node1,
+ struct dsync_mailbox_node *node2)
+{
+ int ret;
+
+ ret = node_mailbox_guids_cmp(node1, node2);
+ if (ret == 0) {
+ /* only a directory name changed and all the timestamps
+ are equal. just pick the alphabetically smaller. */
+ ret = node_mailbox_names_cmp(node1, node2);
+ }
+ i_assert(ret != 0);
+ return ret;
+}
+
+static time_t nodes_get_timestamp(struct dsync_mailbox_node *node1,
+ struct dsync_mailbox_node *node2)
+{
+ time_t ts = 0;
+
+ /* avoid using temporary names in case all the timestamps are 0 */
+ if (node1 != NULL && !node1->sync_temporary_name)
+ ts = node1->last_renamed_or_created + 1;
+ if (node2 != NULL && !node2->sync_temporary_name &&
+ ts <= node2->last_renamed_or_created)
+ ts = node2->last_renamed_or_created + 1;
+ return ts;
+}
+
+static bool sync_node_is_namespace_root(struct dsync_mailbox_tree *tree,
+ struct dsync_mailbox_node *node)
+{
+ if (node == NULL)
+ return FALSE;
+ if (node == &tree->root)
+ return TRUE;
+ return sync_node_is_namespace_prefix(tree, node);
+}
+
+static bool ATTR_NULL(3, 4)
+sync_rename_lower_ts(struct dsync_mailbox_tree_sync_ctx *ctx,
+ struct dsync_mailbox_node *local_node1,
+ struct dsync_mailbox_node *remote_node1,
+ struct dsync_mailbox_node *local_node2,
+ struct dsync_mailbox_node *remote_node2,
+ const char **reason_r)
+{
+ time_t local_ts, remote_ts;
+
+ /* We're scanning the tree at the position of local_node1
+ and remote_node2. They have identical names. We also know that
+ local_node1&remote_node1 and local_node2&remote_node2 are "the same"
+ either because their GUIDs or (in case of one being a directory)
+ their childrens' GUIDs match. We don't know where local_node2 or
+ remote_node1 are located in the mailbox tree, or if they exist
+ at all. Note that node1 and node2 may be the same node pointers. */
+ i_assert(strcmp(local_node1->name, remote_node2->name) == 0);
+
+ if (sync_node_is_namespace_root(ctx->remote_tree, remote_node1) ||
+ sync_node_is_namespace_root(ctx->remote_tree, remote_node2) ||
+ sync_node_is_namespace_root(ctx->local_tree, local_node1) ||
+ sync_node_is_namespace_root(ctx->local_tree, local_node2)) {
+ local_node1->sync_delayed_guid_change = TRUE;
+ remote_node2->sync_delayed_guid_change = TRUE;
+ *reason_r = "Can't rename namespace prefixes - will be merged later";
+ return FALSE;
+ }
+
+ local_ts = nodes_get_timestamp(local_node1, local_node2);
+ remote_ts = nodes_get_timestamp(remote_node1, remote_node2);
+
+ if (ctx->sync_type == DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL)
+ local_ts = remote_ts+1;
+ else if (ctx->sync_type == DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_REMOTE)
+ remote_ts = local_ts+1;
+
+ /* The algorithm must be deterministic regardless of the sync direction,
+ so in case the timestamps are equal we need to resort to looking at
+ the other data. We'll start by looking at the nodes' mailbox GUIDs,
+ but if both of them don't exist continue looking into their
+ children. */
+ if (local_ts > remote_ts ||
+ (local_ts == remote_ts &&
+ node_mailbox_trees_cmp(local_node1, remote_node2) < 0)) {
+ /* local nodes have a higher timestamp. we only want to do
+ renames where the destination parent is the current node's
+ (local_node1/remote_node2) parent. */
+
+ /* Numbers are GUIDs, letters are mailbox names:
+
+ local 1A <-name conflict-> remote 2A
+ local 2B <- potentially -> remote 1[BC]
+
+ Here we want to preserve the local 1A & 2B names: */
+ if (local_node2 == NULL) {
+ /* local : 1A
+ remote: 1B, 2A -> 2A-temp, 1A */
+ sync_rename_node(ctx, ctx->remote_tree, remote_node2,
+ remote_node1, local_node1, reason_r);
+ *reason_r = t_strconcat(*reason_r, "(local: local_node2=NULL)", NULL);
+ return TRUE;
+ } else if (remote_node1 == remote_node2) {
+ /* FIXME: this fixes an infinite loop when in
+ rename2 test, think it through why :) */
+ *reason_r = "local: remote_node1=remote_node2";
+ } else if (remote_node1 != NULL) {
+ /* a) local_node1->parent == local_node2->parent
+
+ local : 1A, 2B
+ remote: 1B, 2A -> 2A-temp, 1A(, 2B)
+ remote: 1C, 2A -> 2B, 1A
+ remote: 1C, 2A, 3B -> 2A-temp, 1A(, 3B-temp, 2B)
+
+ b) local_node1->parent != local_node2->parent
+
+ local : 1X/A, 2Y/B
+ remote: 1Y/B, 2X/A -> 2X/A-temp, 1X/A(, 2Y/B)
+ remote: 1Z/C, 2X/A -> 2X/A-temp, 1X/A
+ remote: 1Z/C, 2X/A, 3Y/B -> 2X/A-temp, 1X/A
+
+ We can handle all of these more easily by simply
+ always renaming 2 to a temporary name and handling
+ it when we reach B handling. */
+ sync_rename_node(ctx, ctx->remote_tree, remote_node2,
+ remote_node1, local_node1, reason_r);
+ *reason_r = t_strconcat(*reason_r, "(local: remote_node1=NULL)", NULL);
+ return TRUE;
+ } else if (node_has_parent(local_node1, local_node2) &&
+ ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL) {
+ /* node2 is a parent of node1, but it should be
+ vice versa */
+ sync_rename_node_to_temp(ctx, ctx->local_tree,
+ local_node1, local_node2->parent, reason_r);
+ *reason_r = t_strconcat(*reason_r, "(local: node2 parent of node1)", NULL);
+ return TRUE;
+ } else if (node_has_parent(local_node2, local_node1) &&
+ ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL) {
+ /* node1 is a parent of node2, but it should be
+ vice versa */
+ sync_rename_node_to_temp(ctx, ctx->local_tree,
+ local_node2, local_node1->parent, reason_r);
+ *reason_r = t_strconcat(*reason_r, "(local: node1 parent of node2)", NULL);
+ return TRUE;
+ } else if (local_node1->existence == DSYNC_MAILBOX_NODE_EXISTS) {
+ sync_rename_node_to_temp(ctx, ctx->remote_tree,
+ remote_node2, remote_node2->parent, reason_r);
+ *reason_r = t_strconcat(*reason_r, "(local: local_node1 exists)", NULL);
+ return TRUE;
+ } else {
+ /* local : 1A, 2B
+ remote: 2A -> (2B)
+ remote: 2A, 3B -> (3B-temp, 2B) */
+ *reason_r = "local: unchanged";
+ }
+ } else {
+ /* remote nodes have a higher timestamp */
+ if (remote_node1 == NULL) {
+ sync_rename_node(ctx, ctx->local_tree, local_node1,
+ local_node2, remote_node2, reason_r);
+ *reason_r = t_strconcat(*reason_r, "(remote: remote_node1=NULL)", NULL);
+ return TRUE;
+ } else if (local_node2 == local_node1) {
+ *reason_r = "remote: remote_node2=remote_node1";
+ } else if (local_node2 != NULL) {
+ sync_rename_node(ctx, ctx->local_tree, local_node1,
+ local_node2, remote_node2, reason_r);
+ *reason_r = t_strconcat(*reason_r, "(remote: local_node2=NULL)", NULL);
+ return TRUE;
+ } else if (node_has_parent(remote_node1, remote_node2) &&
+ ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_REMOTE) {
+ sync_rename_node_to_temp(ctx, ctx->remote_tree,
+ remote_node1, remote_node2->parent, reason_r);
+ *reason_r = t_strconcat(*reason_r, "(remote: node2 parent of node1)", NULL);
+ return TRUE;
+ } else if (node_has_parent(remote_node2, remote_node1) &&
+ ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_REMOTE) {
+ sync_rename_node_to_temp(ctx, ctx->remote_tree,
+ remote_node2, remote_node1->parent, reason_r);
+ *reason_r = t_strconcat(*reason_r, "(remote: node1 parent of node2)", NULL);
+ return TRUE;
+ } else if (remote_node2->existence == DSYNC_MAILBOX_NODE_EXISTS) {
+ sync_rename_node_to_temp(ctx, ctx->local_tree,
+ local_node1, local_node1->parent, reason_r);
+ *reason_r = t_strconcat(*reason_r, "(remote: remote_node2 exists)", NULL);
+ return TRUE;
+ } else {
+ *reason_r = "remote: unchanged";
+ }
+ }
+ return FALSE;
+}
+
+static bool sync_rename_conflict(struct dsync_mailbox_tree_sync_ctx *ctx,
+ struct dsync_mailbox_node *local_node1,
+ struct dsync_mailbox_node *remote_node2,
+ const char **reason_r)
+{
+ struct dsync_mailbox_node *local_node2, *remote_node1;
+ const uint8_t *guid_p;
+ bool ret;
+
+ guid_p = local_node1->mailbox_guid;
+ remote_node1 = hash_table_lookup(ctx->remote_tree->guid_hash, guid_p);
+ guid_p = remote_node2->mailbox_guid;
+ local_node2 = hash_table_lookup(ctx->local_tree->guid_hash, guid_p);
+
+ if ((remote_node1 != NULL && remote_node1->existence == DSYNC_MAILBOX_NODE_EXISTS) ||
+ (local_node2 != NULL && local_node2->existence == DSYNC_MAILBOX_NODE_EXISTS)) {
+ /* conflicting name, rename the one with lower timestamp */
+ ret = sync_rename_lower_ts(ctx, local_node1, remote_node1,
+ local_node2, remote_node2, reason_r);
+ *reason_r = t_strconcat("conflicting name: ", *reason_r, NULL);
+ return ret;
+ } else if (dsync_mailbox_node_is_dir(local_node1) ||
+ dsync_mailbox_node_is_dir(remote_node2)) {
+ /* one of the nodes is a directory, and the other is a mailbox
+ that doesn't exist on the other side. there is no conflict,
+ we'll just need to create the mailbox later. */
+ *reason_r = "mailbox not selectable yet";
+ return FALSE;
+ } else {
+ /* both nodes are mailboxes that don't exist on the other side.
+ we'll merge these mailboxes together later and change their
+ GUIDs and UIDVALIDITYs to be the same */
+ local_node1->sync_delayed_guid_change = TRUE;
+ remote_node2->sync_delayed_guid_change = TRUE;
+ *reason_r = "GUIDs conflict - will be merged later";
+ return FALSE;
+ }
+}
+
+static struct dsync_mailbox_node *
+sync_find_branch(struct dsync_mailbox_tree *tree,
+ struct dsync_mailbox_tree *other_tree,
+ struct dsync_mailbox_node *dir_node)
+{
+ struct dsync_mailbox_node *node, *other_node;
+ const uint8_t *guid_p;
+
+ for (node = dir_node->first_child; node != NULL; node = node->next) {
+ if (dsync_mailbox_node_is_dir(node)) {
+ other_node = sync_find_branch(tree, other_tree, node);
+ if (other_node != NULL)
+ return other_node;
+ } else {
+ guid_p = node->mailbox_guid;
+ other_node = hash_table_lookup(other_tree->guid_hash,
+ guid_p);
+ if (other_node != NULL)
+ return other_node->parent;
+ }
+ }
+ return NULL;
+}
+
+static bool sync_rename_directory(struct dsync_mailbox_tree_sync_ctx *ctx,
+ struct dsync_mailbox_node *local_node1,
+ struct dsync_mailbox_node *remote_node2,
+ const char **reason_r)
+{
+ struct dsync_mailbox_node *remote_node1, *local_node2;
+
+ /* see if we can find matching mailbox branches based on the nodes'
+ child mailboxes (with GUIDs). we can then rename the entire branch.
+ don't try to do this for namespace prefixes though. */
+ remote_node1 = sync_find_branch(ctx->local_tree,
+ ctx->remote_tree, local_node1);
+ local_node2 = sync_find_branch(ctx->remote_tree, ctx->local_tree,
+ remote_node2);
+ if (remote_node1 == NULL || local_node2 == NULL) {
+ *reason_r = "Directory rename branch not found";
+ return FALSE;
+ }
+ if (node_names_equal(remote_node1, local_node2)) {
+ *reason_r = "Directory name paths are equal";
+ return FALSE;
+ }
+
+ return sync_rename_lower_ts(ctx, local_node1, remote_node1,
+ local_node2, remote_node2, reason_r);
+}
+
+static bool sync_rename_mailboxes(struct dsync_mailbox_tree_sync_ctx *ctx,
+ struct dsync_mailbox_node *local_parent,
+ struct dsync_mailbox_node *remote_parent)
+{
+ struct dsync_mailbox_node **local_nodep = &local_parent->first_child;
+ struct dsync_mailbox_node **remote_nodep = &remote_parent->first_child;
+ struct dsync_mailbox_node *local_node, *remote_node;
+ const char *reason;
+ string_t *debug = NULL;
+ bool changed;
+
+ if ((ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_DEBUG) != 0)
+ debug = t_str_new(128);
+
+ /* the nodes are sorted by their names. */
+ while (*local_nodep != NULL || *remote_nodep != NULL) {
+ local_node = *local_nodep;
+ remote_node = *remote_nodep;
+
+ if (local_node == NULL ||
+ (remote_node != NULL &&
+ strcmp(local_node->name, remote_node->name) > 0)) {
+ /* add a missing local node */
+ local_node = sync_node_new(ctx->local_tree, local_nodep,
+ local_parent, remote_node);
+ }
+ if (remote_node == NULL ||
+ strcmp(remote_node->name, local_node->name) > 0) {
+ /* add a missing remote node */
+ remote_node = sync_node_new(ctx->remote_tree, remote_nodep,
+ remote_parent, local_node);
+ }
+ i_assert(strcmp(local_node->name, remote_node->name) == 0);
+ if (debug != NULL) {
+ str_truncate(debug, 0);
+ str_append(debug, "Mailbox ");
+ dsync_mailbox_node_append_full_name(debug, ctx->local_tree, local_node);
+ str_printfa(debug, ": local=%s/%ld/%d, remote=%s/%ld/%d",
+ guid_128_to_string(local_node->mailbox_guid),
+ (long)local_node->last_renamed_or_created,
+ local_node->existence,
+ guid_128_to_string(remote_node->mailbox_guid),
+ (long)remote_node->last_renamed_or_created,
+ remote_node->existence);
+ }
+
+ if (dsync_mailbox_node_is_dir(local_node) &&
+ dsync_mailbox_node_is_dir(remote_node)) {
+ /* both nodes are directories (or other side is
+ nonexistent). see if we can match them by their
+ child mailboxes */
+ changed = sync_rename_directory(ctx, local_node, remote_node, &reason);
+ } else if (dsync_mailbox_node_guids_equal(local_node,
+ remote_node)) {
+ /* mailboxes are equal, no need to rename */
+ reason = "Mailboxes are equal";
+ changed = FALSE;
+ } else {
+ /* mailbox naming conflict */
+ changed = sync_rename_conflict(ctx, local_node,
+ remote_node, &reason);
+ }
+ /* handle children, if there are any */
+ if (debug != NULL) {
+ i_debug("brain %c: %s: %s",
+ (ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_MASTER_BRAIN) != 0 ? 'M' : 'S',
+ str_c(debug), reason);
+ }
+
+ if (!changed) T_BEGIN {
+ changed = sync_rename_mailboxes(ctx, local_node,
+ remote_node);
+ } T_END;
+ if (changed)
+ return TRUE;
+
+ local_nodep = &local_node->next;
+ remote_nodep = &remote_node->next;
+ }
+ return FALSE;
+}
+
+static bool mailbox_node_hash_first_child(struct dsync_mailbox_node *node,
+ struct md5_context *md5)
+{
+ for (node = node->first_child; node != NULL; node = node->next) {
+ if (node->existence == DSYNC_MAILBOX_NODE_EXISTS) {
+ md5_update(md5, node->mailbox_guid,
+ sizeof(node->mailbox_guid));
+ md5_update(md5, node->name, strlen(node->name));
+ return TRUE;
+ }
+ if (node->first_child != NULL) {
+ if (mailbox_node_hash_first_child(node, md5))
+ return TRUE;
+ }
+ }
+ return FALSE;
+}
+
+static const char *
+mailbox_node_generate_suffix(struct dsync_mailbox_node *node)
+{
+ struct md5_context md5;
+ unsigned char digest[MD5_RESULTLEN];
+
+ if (!dsync_mailbox_node_is_dir(node))
+ return guid_128_to_string(node->mailbox_guid);
+
+ md5_init(&md5);
+ if (!mailbox_node_hash_first_child(node, &md5))
+ i_unreached(); /* we would have deleted it */
+ md5_final(&md5, digest);
+ return binary_to_hex(digest, sizeof(digest));
+}
+
+static void suffix_inc(string_t *str)
+{
+ char *data;
+ size_t i;
+
+ data = str_c_modifiable(str) + str_len(str)-1;
+ for (i = str_len(str); i > 0; i--, data--) {
+ if ((*data >= '0' && *data < '9') ||
+ (*data >= 'a' && *data < 'f')) {
+ *data += 1;
+ return;
+ } else if (*data == '9') {
+ *data = 'a';
+ return;
+ } else if (*data != 'f') {
+ i_unreached();
+ }
+ }
+ i_unreached();
+}
+
+static void
+sync_rename_temp_mailbox_node(struct dsync_mailbox_tree *tree,
+ struct dsync_mailbox_node *node,
+ const char **reason_r)
+{
+ const char *p, *new_suffix;
+ string_t *str = t_str_new(256);
+ size_t max_prefix_len;
+
+ /* The name is currently <oldname>-<temp>. Both sides need to
+ use equivalent names, so we'll replace the <temp> if possible
+ with a) mailbox GUID, b) sha1 of childrens' (GUID|name)s. In the
+ very unlikely case of such name already existing, just increase
+ the last letters until it's not found. */
+ new_suffix = mailbox_node_generate_suffix(node);
+
+ p = strrchr(node->name, '-');
+ i_assert(p != NULL);
+ p++;
+ max_prefix_len = TEMP_MAX_NAME_LEN - strlen(new_suffix) - 1;
+ if (max_prefix_len > (size_t)(p-node->name))
+ max_prefix_len = p-node->name;
+ str_append_max(str, node->name, max_prefix_len);
+ str_append(str, new_suffix);
+ while (node_has_child(node->parent, str_c(str)))
+ suffix_inc(str);
+
+ *reason_r = t_strdup_printf("Renamed '%s' to '%s'",
+ dsync_mailbox_node_get_full_name(tree, node), str_c(str));
+ node->name = p_strdup(tree->pool, str_c(str));
+
+ dsync_mailbox_tree_node_move_sorted(node, node->parent);
+ node->sync_temporary_name = FALSE;
+}
+
+static void
+sync_rename_delete_node_dirs(struct dsync_mailbox_tree_sync_ctx *ctx,
+ struct dsync_mailbox_tree *tree,
+ struct dsync_mailbox_node *node)
+{
+ struct dsync_mailbox_node *child;
+
+ for (child = node->first_child; child != NULL; child = child->next)
+ sync_rename_delete_node_dirs(ctx, tree, child);
+
+ if (tree == ctx->local_tree &&
+ ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL &&
+ node->existence != DSYNC_MAILBOX_NODE_NONEXISTENT) {
+ sync_add_dir_change(ctx, node,
+ DSYNC_MAILBOX_TREE_SYNC_TYPE_DELETE_DIR);
+ }
+ node->existence = DSYNC_MAILBOX_NODE_NONEXISTENT;
+ node->sync_temporary_name = FALSE;
+}
+
+static bool
+sync_rename_temp_mailboxes(struct dsync_mailbox_tree_sync_ctx *ctx,
+ struct dsync_mailbox_tree *tree,
+ struct dsync_mailbox_node *node, bool *renames_r)
+{
+ const char *reason;
+
+ for (; node != NULL; node = node->next) {
+ while (sync_rename_temp_mailboxes(ctx, tree, node->first_child, renames_r)) ;
+
+ if (!node->sync_temporary_name) {
+ } else if (dsync_mailbox_node_is_dir(node) &&
+ (node->first_child == NULL ||
+ !node_has_existent_children(node, FALSE))) {
+ /* we can just delete this directory and
+ any child directories it may have */
+ if ((ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_DEBUG) != 0) {
+ i_debug("brain %c: %s mailbox %s: Delete directory-only tree",
+ (ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_MASTER_BRAIN) != 0 ? 'M' : 'S',
+ tree == ctx->local_tree ? "local" : "remote",
+ dsync_mailbox_node_get_full_name(tree, node));
+ }
+ sync_rename_delete_node_dirs(ctx, tree, node);
+ } else {
+ T_BEGIN {
+ *renames_r = TRUE;
+ sync_rename_temp_mailbox_node(tree, node, &reason);
+ if ((ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_DEBUG) != 0) {
+ i_debug("brain %c: %s mailbox %s: %s",
+ (ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_MASTER_BRAIN) != 0 ? 'M' : 'S',
+ tree == ctx->local_tree ? "local" : "remote",
+ dsync_mailbox_node_get_full_name(tree, node), reason);
+ }
+ } T_END;
+ return TRUE;
+ }
+ }
+ return FALSE;
+}
+
+static int
+dsync_mailbox_tree_handle_renames(struct dsync_mailbox_tree_sync_ctx *ctx,
+ bool *renames_r)
+{
+ unsigned int max_renames, count = 0;
+ bool changed;
+
+ *renames_r = FALSE;
+
+ max_renames = ctx->combined_mailboxes_count * 3;
+ do {
+ T_BEGIN {
+ changed = sync_rename_mailboxes(ctx, &ctx->local_tree->root,
+ &ctx->remote_tree->root);
+ } T_END;
+ if ((ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_DEBUG) != 0 &&
+ changed) {
+ i_debug("brain %c: -- Mailbox renamed, restart sync --",
+ (ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_MASTER_BRAIN) != 0 ? 'M' : 'S');
+ }
+ } while (changed && ++count <= max_renames);
+
+ if (changed) {
+ i_error("BUG: Mailbox renaming algorithm got into a potentially infinite loop, aborting");
+ return -1;
+ }
+
+ while (sync_rename_temp_mailboxes(ctx, ctx->local_tree, &ctx->local_tree->root, renames_r)) ;
+ while (sync_rename_temp_mailboxes(ctx, ctx->remote_tree, &ctx->remote_tree->root, renames_r)) ;
+ return 0;
+}
+
+static bool sync_is_wrong_mailbox(struct dsync_mailbox_node *node,
+ const struct dsync_mailbox_node *wanted_node,
+ const char **reason_r)
+{
+ if (wanted_node->existence != DSYNC_MAILBOX_NODE_EXISTS) {
+ *reason_r = wanted_node->existence == DSYNC_MAILBOX_NODE_DELETED ?
+ "Mailbox has been deleted" : "Mailbox doesn't exist";
+ return TRUE;
+ }
+ if (node->uid_validity != wanted_node->uid_validity) {
+ *reason_r = t_strdup_printf("UIDVALIDITY changed (%u -> %u)",
+ wanted_node->uid_validity,
+ node->uid_validity);
+ return TRUE;
+ }
+ if (node->uid_next > wanted_node->uid_next) {
+ /* we can't lower the UIDNEXT */
+ *reason_r = t_strdup_printf("UIDNEXT is too high (%u > %u)",
+ node->uid_next,
+ wanted_node->uid_next);
+ return TRUE;
+ }
+ if (memcmp(node->mailbox_guid, wanted_node->mailbox_guid,
+ sizeof(node->mailbox_guid)) != 0) {
+ *reason_r = "GUID changed";
+ return TRUE;
+ }
+ return FALSE;
+}
+
+static void
+sync_delete_wrong_mailboxes_branch(struct dsync_mailbox_tree_sync_ctx *ctx,
+ struct dsync_mailbox_tree *tree,
+ const struct dsync_mailbox_tree *wanted_tree,
+ struct dsync_mailbox_node *node,
+ const struct dsync_mailbox_node *wanted_node)
+{
+ const char *reason;
+ int ret;
+
+ while (node != NULL && wanted_node != NULL) {
+ if (node->first_child != NULL) {
+ sync_delete_wrong_mailboxes_branch(ctx,
+ tree, wanted_tree,
+ node->first_child, wanted_node->first_child);
+ }
+ ret = strcmp(node->name, wanted_node->name);
+ if (ret < 0) {
+ /* node shouldn't exist */
+ if (node->existence == DSYNC_MAILBOX_NODE_EXISTS &&
+ !dsync_mailbox_node_is_dir(node)) {
+ sync_delete_mailbox_node(ctx, tree, node,
+ "Mailbox doesn't exist");
+ }
+ node = node->next;
+ } else if (ret > 0) {
+ /* wanted_node doesn't exist. it's created later. */
+ wanted_node = wanted_node->next;
+ } else T_BEGIN {
+ if (sync_is_wrong_mailbox(node, wanted_node, &reason) &&
+ node->existence == DSYNC_MAILBOX_NODE_EXISTS &&
+ !dsync_mailbox_node_is_dir(node))
+ sync_delete_mailbox_node(ctx, tree, node, reason);
+ node = node->next;
+ wanted_node = wanted_node->next;
+ } T_END;
+ }
+ for (; node != NULL; node = node->next) {
+ /* node and its children shouldn't exist */
+ if (node->first_child != NULL) {
+ sync_delete_wrong_mailboxes_branch(ctx,
+ tree, wanted_tree,
+ node->first_child, NULL);
+ }
+ if (node->existence == DSYNC_MAILBOX_NODE_EXISTS &&
+ !dsync_mailbox_node_is_dir(node))
+ sync_delete_mailbox_node(ctx, tree, node, "Mailbox doesn't exist");
+ }
+}
+
+static void
+sync_delete_wrong_mailboxes(struct dsync_mailbox_tree_sync_ctx *ctx,
+ struct dsync_mailbox_tree *tree,
+ const struct dsync_mailbox_tree *wanted_tree)
+{
+ sync_delete_wrong_mailboxes_branch(ctx, tree, wanted_tree,
+ tree->root.first_child,
+ wanted_tree->root.first_child);
+}
+
+static void sync_create_mailboxes(struct dsync_mailbox_tree_sync_ctx *ctx,
+ struct dsync_mailbox_tree *tree)
+{
+ struct dsync_mailbox_tree *other_tree;
+ struct dsync_mailbox_tree_iter *iter;
+ struct dsync_mailbox_node *node, *other_node;
+ const char *name;
+ const uint8_t *guid_p;
+
+ other_tree = tree == ctx->local_tree ?
+ ctx->remote_tree : ctx->local_tree;
+
+ iter = dsync_mailbox_tree_iter_init(tree);
+ while (dsync_mailbox_tree_iter_next(iter, &name, &node)) {
+ /* make sure the renaming handled everything */
+ i_assert(!node->sync_temporary_name);
+ if (dsync_mailbox_node_is_dir(node))
+ continue;
+
+ i_assert(node->existence == DSYNC_MAILBOX_NODE_EXISTS);
+
+ guid_p = node->mailbox_guid;
+ other_node = hash_table_lookup(other_tree->guid_hash, guid_p);
+ if (other_node == NULL)
+ other_node = sorted_tree_get(other_tree, name);
+ if (dsync_mailbox_node_is_dir(other_node)) {
+ /* create a missing mailbox */
+ other_node->existence = DSYNC_MAILBOX_NODE_EXISTS;
+ other_node->ns = node->ns;
+ other_node->uid_validity = node->uid_validity;
+ memcpy(other_node->mailbox_guid, node->mailbox_guid,
+ sizeof(other_node->mailbox_guid));
+ if (other_tree == ctx->local_tree)
+ sync_add_create_change(ctx, other_node, name);
+ } else if (!guid_128_equals(node->mailbox_guid,
+ other_node->mailbox_guid)) {
+ /* mailbox with same name exists both locally and
+ remotely, but they have different GUIDs and neither
+ side has the other's GUID. typically this means that
+ both sides had autocreated some mailboxes (e.g.
+ INBOX). we'll just change the GUID for one of
+ them. */
+ i_assert(node->existence == DSYNC_MAILBOX_NODE_EXISTS);
+ i_assert(node->ns == other_node->ns);
+
+ if (other_tree == ctx->local_tree)
+ sync_add_create_change(ctx, node, name);
+ } else {
+ /* existing mailbox. mismatching UIDVALIDITY is handled
+ later while syncing the mailbox. */
+ i_assert(node->existence == DSYNC_MAILBOX_NODE_EXISTS);
+ i_assert(node->ns == other_node->ns);
+ }
+ }
+ dsync_mailbox_tree_iter_deinit(&iter);
+}
+
+static void
+sync_subscription(struct dsync_mailbox_tree_sync_ctx *ctx,
+ struct dsync_mailbox_node *local_node,
+ struct dsync_mailbox_node *remote_node)
+{
+ bool use_local;
+
+ if (ctx->sync_type == DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL)
+ use_local = TRUE;
+ else if (ctx->sync_type == DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_REMOTE)
+ use_local = FALSE;
+ else if (local_node->last_subscription_change > remote_node->last_subscription_change)
+ use_local = TRUE;
+ else if (local_node->last_subscription_change < remote_node->last_subscription_change)
+ use_local = FALSE;
+ else {
+ /* local and remote have equal timestamps. prefer to subscribe
+ rather than unsubscribe. */
+ use_local = local_node->subscribed;
+ }
+ if (use_local) {
+ /* use local subscription state */
+ remote_node->subscribed = local_node->subscribed;
+ } else {
+ /* use remote subscription state */
+ local_node->subscribed = remote_node->subscribed;
+ sync_add_dir_change(ctx, local_node, local_node->subscribed ?
+ DSYNC_MAILBOX_TREE_SYNC_TYPE_SUBSCRIBE :
+ DSYNC_MAILBOX_TREE_SYNC_TYPE_UNSUBSCRIBE);
+ }
+}
+
+static void sync_mailbox_child_dirs(struct dsync_mailbox_tree_sync_ctx *ctx,
+ struct dsync_mailbox_node *local_parent,
+ struct dsync_mailbox_node *remote_parent)
+{
+ struct dsync_mailbox_node **local_nodep = &local_parent->first_child;
+ struct dsync_mailbox_node **remote_nodep = &remote_parent->first_child;
+ struct dsync_mailbox_node *local_node, *remote_node;
+ int ret;
+
+ /* NOTE: the nodes are always sorted. renaming created all of the
+ interesting nodes, but it may have left some extra nonexistent nodes
+ lying around, which we will delete. */
+ while (*local_nodep != NULL && *remote_nodep != NULL) {
+ local_node = *local_nodep;
+ remote_node = *remote_nodep;
+
+ ret = strcmp(local_node->name, remote_node->name);
+ if (ret < 0) {
+ i_assert(!node_is_existent(local_node));
+ *local_nodep = local_node->next;
+ continue;
+ }
+ if (ret > 0) {
+ i_assert(!node_is_existent(remote_node));
+ *remote_nodep = remote_node->next;
+ continue;
+ }
+
+ if (local_node->existence == DSYNC_MAILBOX_NODE_EXISTS &&
+ remote_node->existence == DSYNC_MAILBOX_NODE_NONEXISTENT &&
+ ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_REMOTE) {
+ /* create to remote */
+ remote_node->existence = DSYNC_MAILBOX_NODE_EXISTS;
+ }
+ if (remote_node->existence == DSYNC_MAILBOX_NODE_EXISTS &&
+ local_node->existence == DSYNC_MAILBOX_NODE_NONEXISTENT &&
+ ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL) {
+ /* create to local */
+ local_node->existence = DSYNC_MAILBOX_NODE_EXISTS;
+ sync_add_dir_change(ctx, local_node,
+ DSYNC_MAILBOX_TREE_SYNC_TYPE_CREATE_DIR);
+ }
+
+ /* create/delete child dirs */
+ sync_mailbox_child_dirs(ctx, local_node, remote_node);
+
+ if (local_node->subscribed != remote_node->subscribed)
+ sync_subscription(ctx, local_node, remote_node);
+
+ if (local_node->existence == DSYNC_MAILBOX_NODE_DELETED &&
+ !node_has_existent_children(local_node, TRUE) &&
+ remote_node->existence == DSYNC_MAILBOX_NODE_EXISTS &&
+ ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_REMOTE) {
+ /* delete from remote */
+ i_assert(!node_has_existent_children(remote_node, TRUE));
+ remote_node->existence = DSYNC_MAILBOX_NODE_NONEXISTENT;
+ }
+ if (remote_node->existence == DSYNC_MAILBOX_NODE_DELETED &&
+ !node_has_existent_children(remote_node, TRUE) &&
+ local_node->existence == DSYNC_MAILBOX_NODE_EXISTS &&
+ ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL) {
+ /* delete from local */
+ i_assert(!node_has_existent_children(local_node, TRUE));
+ local_node->existence = DSYNC_MAILBOX_NODE_NONEXISTENT;
+ sync_add_dir_change(ctx, local_node,
+ DSYNC_MAILBOX_TREE_SYNC_TYPE_DELETE_DIR);
+ }
+
+ local_nodep = &local_node->next;
+ remote_nodep = &remote_node->next;
+ }
+ while (*local_nodep != NULL) {
+ i_assert(!node_is_existent(*local_nodep));
+ *local_nodep = (*local_nodep)->next;
+ }
+ while (*remote_nodep != NULL) {
+ i_assert(!node_is_existent(*remote_nodep));
+ *remote_nodep = (*remote_nodep)->next;
+ }
+}
+
+static void sync_mailbox_dirs(struct dsync_mailbox_tree_sync_ctx *ctx)
+{
+ sync_mailbox_child_dirs(ctx, &ctx->local_tree->root,
+ &ctx->remote_tree->root);
+}
+
+static void
+dsync_mailbox_tree_update_child_timestamps(struct dsync_mailbox_node *node,
+ time_t parent_timestamp)
+{
+ time_t ts;
+
+ if (node->last_renamed_or_created < parent_timestamp)
+ node->last_renamed_or_created = parent_timestamp;
+ ts = node->last_renamed_or_created;
+
+ for (node = node->first_child; node != NULL; node = node->next)
+ dsync_mailbox_tree_update_child_timestamps(node, ts);
+}
+
+struct dsync_mailbox_tree_sync_ctx *
+dsync_mailbox_trees_sync_init(struct dsync_mailbox_tree *local_tree,
+ struct dsync_mailbox_tree *remote_tree,
+ enum dsync_mailbox_trees_sync_type sync_type,
+ enum dsync_mailbox_trees_sync_flags sync_flags)
+{
+ struct dsync_mailbox_tree_sync_ctx *ctx;
+ unsigned int rename_counter = 0;
+ bool renames;
+ pool_t pool;
+
+ i_assert(hash_table_is_created(local_tree->guid_hash));
+ i_assert(hash_table_is_created(remote_tree->guid_hash));
+
+ pool = pool_alloconly_create(MEMPOOL_GROWING"dsync mailbox trees sync",
+ 1024*64);
+ ctx = p_new(pool, struct dsync_mailbox_tree_sync_ctx, 1);
+ ctx->pool = pool;
+ ctx->local_tree = local_tree;
+ ctx->remote_tree = remote_tree;
+ ctx->sync_type = sync_type;
+ ctx->sync_flags = sync_flags;
+ i_array_init(&ctx->changes, 128);
+
+again:
+ renames = FALSE;
+ ctx->combined_mailboxes_count = 0;
+ sync_tree_sort_and_delete_mailboxes(ctx, remote_tree,
+ sync_type == DSYNC_MAILBOX_TREES_SYNC_TYPE_TWOWAY);
+ sync_tree_sort_and_delete_mailboxes(ctx, local_tree,
+ sync_type == DSYNC_MAILBOX_TREES_SYNC_TYPE_TWOWAY);
+
+ dsync_mailbox_tree_update_child_timestamps(&local_tree->root, 0);
+ dsync_mailbox_tree_update_child_timestamps(&remote_tree->root, 0);
+ if ((sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_NO_RENAMES) == 0) {
+ if (dsync_mailbox_tree_handle_renames(ctx, &renames) < 0) {
+ ctx->failed = TRUE;
+ return ctx;
+ }
+ }
+
+ /* if we're not doing a two-way sync, delete now any mailboxes, which
+ a) shouldn't exist, b) doesn't have a matching GUID/UIDVALIDITY,
+ c) has a too high UIDNEXT */
+ if (sync_type == DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL)
+ sync_delete_wrong_mailboxes(ctx, remote_tree, local_tree);
+ else if (sync_type == DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_REMOTE)
+ sync_delete_wrong_mailboxes(ctx, local_tree, remote_tree);
+
+ if (sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL)
+ sync_create_mailboxes(ctx, remote_tree);
+ if (sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_REMOTE)
+ sync_create_mailboxes(ctx, local_tree);
+ if (renames && rename_counter++ <= ctx->combined_mailboxes_count*3) {
+ /* this rename algorithm is just horrible. we're retrying this
+ because the final sync_rename_temp_mailbox_node() calls
+ give different names to local & remote mailbox trees.
+ something's not right here, but this looping is better than
+ a crash in sync_mailbox_dirs() due to trees not matching. */
+ goto again;
+ }
+ sync_mailbox_dirs(ctx);
+ return ctx;
+}
+
+const struct dsync_mailbox_tree_sync_change *
+dsync_mailbox_trees_sync_next(struct dsync_mailbox_tree_sync_ctx *ctx)
+{
+ if (ctx->change_idx == array_count(&ctx->changes))
+ return NULL;
+ return array_idx(&ctx->changes, ctx->change_idx++);
+}
+
+int dsync_mailbox_trees_sync_deinit(struct dsync_mailbox_tree_sync_ctx **_ctx)
+{
+ struct dsync_mailbox_tree_sync_ctx *ctx = *_ctx;
+ int ret = ctx->failed ? -1 : 0;
+
+ *_ctx = NULL;
+
+ array_free(&ctx->changes);
+ pool_unref(&ctx->pool);
+ return ret;
+}