1 /* Copyright (c) 2013-2018 Dovecot authors, see the included COPYING file */
2
3 #include "lib.h"
4 #include "array.h"
5 #include "buffer.h"
6 #include "str.h"
7 #include "md5.h"
8 #include "hex-binary.h"
9 #include "aqueue.h"
10 #include "hash.h"
11 #include "dsync-brain-private.h"
12 #include "dsync-mailbox-tree-private.h"
13
14 #define TEMP_MAX_NAME_LEN 100
15 #define TEMP_SUFFIX_MAX_LEN (sizeof("temp-")-1 + 8)
16 #define TEMP_SUFFIX_FORMAT "temp-%x"
17
18 struct dsync_mailbox_tree_bfs_iter {
19 struct dsync_mailbox_tree *tree;
20
21 ARRAY(struct dsync_mailbox_node *) queue_arr;
22 struct aqueue *queue;
23 struct dsync_mailbox_node *cur;
24 };
25
26 struct dsync_mailbox_tree_sync_ctx {
27 pool_t pool;
28 struct dsync_mailbox_tree *local_tree, *remote_tree;
29 enum dsync_mailbox_trees_sync_type sync_type;
30 enum dsync_mailbox_trees_sync_flags sync_flags;
31 unsigned int combined_mailboxes_count;
32
33 ARRAY(struct dsync_mailbox_tree_sync_change) changes;
34 unsigned int change_idx;
35 bool failed;
36 };
37
38 static struct dsync_mailbox_tree_bfs_iter *
dsync_mailbox_tree_bfs_iter_init(struct dsync_mailbox_tree * tree)39 dsync_mailbox_tree_bfs_iter_init(struct dsync_mailbox_tree *tree)
40 {
41 struct dsync_mailbox_tree_bfs_iter *iter;
42
43 iter = i_new(struct dsync_mailbox_tree_bfs_iter, 1);
44 iter->tree = tree;
45 i_array_init(&iter->queue_arr, 32);
46 iter->queue = aqueue_init(&iter->queue_arr.arr);
47 iter->cur = tree->root.first_child;
48 return iter;
49 }
50
51 static bool
dsync_mailbox_tree_bfs_iter_next(struct dsync_mailbox_tree_bfs_iter * iter,struct dsync_mailbox_node ** node_r)52 dsync_mailbox_tree_bfs_iter_next(struct dsync_mailbox_tree_bfs_iter *iter,
53 struct dsync_mailbox_node **node_r)
54 {
55 if (iter->cur == NULL) {
56 if (aqueue_count(iter->queue) == 0)
57 return FALSE;
58 iter->cur = array_idx_elem(&iter->queue_arr,
59 aqueue_idx(iter->queue, 0));
60 aqueue_delete_tail(iter->queue);
61 }
62 *node_r = iter->cur;
63
64 if (iter->cur->first_child != NULL)
65 aqueue_append(iter->queue, &iter->cur->first_child);
66 iter->cur = iter->cur->next;
67 return TRUE;
68 }
69
70 static void
dsync_mailbox_tree_bfs_iter_deinit(struct dsync_mailbox_tree_bfs_iter ** _iter)71 dsync_mailbox_tree_bfs_iter_deinit(struct dsync_mailbox_tree_bfs_iter **_iter)
72 {
73 struct dsync_mailbox_tree_bfs_iter *iter = *_iter;
74
75 *_iter = NULL;
76
77 aqueue_deinit(&iter->queue);
78 array_free(&iter->queue_arr);
79 i_free(iter);
80 }
81
82 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)83 sync_add_dir_change(struct dsync_mailbox_tree_sync_ctx *ctx,
84 const struct dsync_mailbox_node *node,
85 enum dsync_mailbox_tree_sync_type type)
86 {
87 struct dsync_mailbox_tree_sync_change *change;
88 const char *name;
89
90 i_assert(ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL);
91
92 name = dsync_mailbox_node_get_full_name(ctx->local_tree, node);
93
94 change = array_append_space(&ctx->changes);
95 change->type = type;
96 change->ns = node->ns;
97 change->full_name = p_strdup(ctx->pool, name);
98 }
99
100 static void
sync_add_create_change(struct dsync_mailbox_tree_sync_ctx * ctx,const struct dsync_mailbox_node * node,const char * name)101 sync_add_create_change(struct dsync_mailbox_tree_sync_ctx *ctx,
102 const struct dsync_mailbox_node *node, const char *name)
103 {
104 struct dsync_mailbox_tree_sync_change *change;
105
106 i_assert(ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL);
107
108 change = array_append_space(&ctx->changes);
109 change->type = DSYNC_MAILBOX_TREE_SYNC_TYPE_CREATE_BOX;
110 change->ns = node->ns;
111 change->full_name = p_strdup(ctx->pool, name);
112 memcpy(change->mailbox_guid, node->mailbox_guid,
113 sizeof(change->mailbox_guid));
114 change->uid_validity = node->uid_validity;
115 }
116
sort_siblings(ARRAY_TYPE (dsync_mailbox_node)* siblings)117 static void sort_siblings(ARRAY_TYPE(dsync_mailbox_node) *siblings)
118 {
119 struct dsync_mailbox_node *const *nodes;
120 unsigned int i, count;
121
122 array_sort(siblings, dsync_mailbox_node_name_cmp);
123
124 nodes = array_get(siblings, &count);
125 if (count == 0)
126 return;
127
128 nodes[0]->parent->first_child = nodes[0];
129 for (i = 1; i < count; i++)
130 nodes[i-1]->next = nodes[i];
131 nodes[count-1]->next = NULL;
132 }
133
134 static void
sync_set_node_deleted(struct dsync_mailbox_tree * tree,struct dsync_mailbox_node * node)135 sync_set_node_deleted(struct dsync_mailbox_tree *tree,
136 struct dsync_mailbox_node *node)
137 {
138 const uint8_t *guid_p;
139
140 /* for the rest of this sync assume that the mailbox has
141 already been deleted */
142 guid_p = node->mailbox_guid;
143 hash_table_remove(tree->guid_hash, guid_p);
144
145 node->existence = DSYNC_MAILBOX_NODE_DELETED;
146 memset(node->mailbox_guid, 0, sizeof(node->mailbox_guid));
147 node->uid_validity = 0;
148 }
149
150 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)151 sync_delete_mailbox_node(struct dsync_mailbox_tree_sync_ctx *ctx,
152 struct dsync_mailbox_tree *tree,
153 struct dsync_mailbox_node *node, const char *reason)
154 {
155 struct dsync_mailbox_tree_sync_change *change;
156 const char *name;
157
158 if ((ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_DEBUG) != 0 &&
159 tree == ctx->local_tree) {
160 i_debug("brain %c: Deleting mailbox '%s' (GUID %s): %s",
161 (ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_MASTER_BRAIN) != 0 ? 'M' : 'S',
162 dsync_mailbox_node_get_full_name(tree, node),
163 guid_128_to_string(node->mailbox_guid), reason);
164 }
165
166 if (tree == ctx->local_tree &&
167 node->existence != DSYNC_MAILBOX_NODE_DELETED) {
168 /* delete this mailbox locally */
169 i_assert(ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL);
170 change = array_append_space(&ctx->changes);
171 change->type = DSYNC_MAILBOX_TREE_SYNC_TYPE_DELETE_BOX;
172 change->ns = node->ns;
173 name = dsync_mailbox_node_get_full_name(tree, node);
174 change->full_name = p_strdup(ctx->pool, name);
175 memcpy(change->mailbox_guid, node->mailbox_guid,
176 sizeof(change->mailbox_guid));
177 }
178 sync_set_node_deleted(tree, node);
179 }
180
181 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)182 sync_delete_mailbox(struct dsync_mailbox_tree_sync_ctx *ctx,
183 struct dsync_mailbox_tree *tree,
184 struct dsync_mailbox_node *node, const char *reason)
185 {
186 struct dsync_mailbox_tree *other_tree;
187 struct dsync_mailbox_node *other_node;
188 const uint8_t *guid_p;
189
190 other_tree = tree == ctx->local_tree ?
191 ctx->remote_tree : ctx->local_tree;
192 guid_p = node->mailbox_guid;
193 other_node = hash_table_lookup(other_tree->guid_hash, guid_p);
194 if (other_node == NULL) {
195 /* doesn't exist / already deleted */
196 } else {
197 sync_delete_mailbox_node(ctx, other_tree, other_node, reason);
198 }
199 sync_delete_mailbox_node(ctx, tree, node, reason);
200 }
201
202 static void
sync_tree_sort_and_delete_mailboxes(struct dsync_mailbox_tree_sync_ctx * ctx,struct dsync_mailbox_tree * tree,bool twoway_sync)203 sync_tree_sort_and_delete_mailboxes(struct dsync_mailbox_tree_sync_ctx *ctx,
204 struct dsync_mailbox_tree *tree,
205 bool twoway_sync)
206 {
207 struct dsync_mailbox_tree_bfs_iter *iter;
208 struct dsync_mailbox_node *node, *parent = NULL;
209 ARRAY_TYPE(dsync_mailbox_node) siblings;
210
211 t_array_init(&siblings, 64);
212
213 iter = dsync_mailbox_tree_bfs_iter_init(tree);
214 while (dsync_mailbox_tree_bfs_iter_next(iter, &node)) {
215 if (node->parent != parent) {
216 sort_siblings(&siblings);
217 array_clear(&siblings);
218 parent = node->parent;
219 }
220 if (node->existence == DSYNC_MAILBOX_NODE_DELETED &&
221 !dsync_mailbox_node_is_dir(node)) {
222 if (twoway_sync) {
223 /* this mailbox was deleted. delete it from the
224 other side as well */
225 sync_delete_mailbox(ctx, tree, node,
226 "Mailbox has been deleted");
227 } else {
228 /* treat the node as if it didn't exist. it'll
229 get either recreated or deleted later. in
230 any case this function must handle all
231 existence=DELETED mailbox nodes by changing
232 them into directories (setting GUID=0) or
233 we'll assert-crash later */
234 sync_set_node_deleted(tree, node);
235 }
236 }
237 ctx->combined_mailboxes_count++;
238 array_push_back(&siblings, &node);
239 }
240 sort_siblings(&siblings);
241 dsync_mailbox_tree_bfs_iter_deinit(&iter);
242 }
243
node_names_equal(const struct dsync_mailbox_node * n1,const struct dsync_mailbox_node * n2)244 static bool node_names_equal(const struct dsync_mailbox_node *n1,
245 const struct dsync_mailbox_node *n2)
246 {
247 while (n1 != NULL && n2 != NULL) {
248 if (strcmp(n1->name, n2->name) != 0)
249 return FALSE;
250 n1 = n1->parent;
251 n2 = n2->parent;
252 }
253 return n1 == NULL && n2 == NULL;
254 }
255
256 static void
dsync_mailbox_tree_node_attach_sorted(struct dsync_mailbox_node * node,struct dsync_mailbox_node * parent)257 dsync_mailbox_tree_node_attach_sorted(struct dsync_mailbox_node *node,
258 struct dsync_mailbox_node *parent)
259 {
260 struct dsync_mailbox_node **p;
261
262 node->parent = parent;
263 for (p = &parent->first_child; *p != NULL; p = &(*p)->next) {
264 if (dsync_mailbox_node_name_cmp(p, &node) > 0)
265 break;
266 }
267 node->next = *p;
268 *p = node;
269 }
270
271 static void
dsync_mailbox_tree_node_move_sorted(struct dsync_mailbox_node * node,struct dsync_mailbox_node * parent)272 dsync_mailbox_tree_node_move_sorted(struct dsync_mailbox_node *node,
273 struct dsync_mailbox_node *parent)
274 {
275 /* detach from old parent */
276 dsync_mailbox_tree_node_detach(node);
277 /* attach to new parent */
278 dsync_mailbox_tree_node_attach_sorted(node, parent);
279 }
280
281 static struct dsync_mailbox_node *
sorted_tree_get(struct dsync_mailbox_tree * tree,const char * name)282 sorted_tree_get(struct dsync_mailbox_tree *tree, const char *name)
283 {
284 struct dsync_mailbox_node *node, *parent, *ret;
285
286 node = ret = dsync_mailbox_tree_get(tree, name);
287 while (node->parent != NULL &&
288 node->existence == DSYNC_MAILBOX_NODE_NONEXISTENT) {
289 parent = node->parent;
290 dsync_mailbox_tree_node_detach(node);
291 dsync_mailbox_tree_node_attach_sorted(node, parent);
292 node = parent;
293 }
294 return ret;
295 }
296
297 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)298 sync_node_new(struct dsync_mailbox_tree *tree,
299 struct dsync_mailbox_node **pos,
300 struct dsync_mailbox_node *parent,
301 const struct dsync_mailbox_node *src)
302 {
303 struct dsync_mailbox_node *node;
304
305 node = p_new(tree->pool, struct dsync_mailbox_node, 1);
306 node->existence = DSYNC_MAILBOX_NODE_NONEXISTENT;
307 node->name = p_strdup(tree->pool, src->name);
308 node->sync_temporary_name = src->sync_temporary_name;
309 node->ns = src->ns;
310 node->parent = parent;
311 node->next = *pos;
312 *pos = node;
313 return node;
314 }
315
316 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)317 sorted_tree_get_by_node_name(struct dsync_mailbox_tree *tree,
318 struct dsync_mailbox_tree *other_tree,
319 struct dsync_mailbox_node *other_node)
320 {
321 const char *parent_name;
322
323 if (other_node == &other_tree->root)
324 return &tree->root;
325
326 parent_name = dsync_mailbox_node_get_full_name(other_tree, other_node);
327 return sorted_tree_get(tree, parent_name);
328 }
329
node_has_child(struct dsync_mailbox_node * parent,const char * name)330 static bool node_has_child(struct dsync_mailbox_node *parent, const char *name)
331 {
332 struct dsync_mailbox_node *node;
333
334 for (node = parent->first_child; node != NULL; node = node->next) {
335 if (strcmp(node->name, name) == 0)
336 return TRUE;
337 }
338 return FALSE;
339 }
340
341 static bool
node_has_existent_children(struct dsync_mailbox_node * node,bool dirs_ok)342 node_has_existent_children(struct dsync_mailbox_node *node, bool dirs_ok)
343 {
344 for (node = node->first_child; node != NULL; node = node->next) {
345 if (node->existence == DSYNC_MAILBOX_NODE_EXISTS &&
346 (dirs_ok || !dsync_mailbox_node_is_dir(node)))
347 return TRUE;
348 if (node_has_existent_children(node, dirs_ok))
349 return TRUE;
350 }
351 return FALSE;
352 }
353
node_is_existent(struct dsync_mailbox_node * node)354 static bool node_is_existent(struct dsync_mailbox_node *node)
355 {
356 if (node->existence == DSYNC_MAILBOX_NODE_EXISTS)
357 return TRUE;
358 return node_has_existent_children(node, TRUE);
359 }
360
sync_node_is_namespace_prefix(struct dsync_mailbox_tree * tree,struct dsync_mailbox_node * node)361 static bool sync_node_is_namespace_prefix(struct dsync_mailbox_tree *tree,
362 struct dsync_mailbox_node *node)
363 {
364 const char *full_name;
365 size_t prefix_len = node->ns == NULL ? 0 : node->ns->prefix_len;
366
367 if (strcmp(node->name, "INBOX") == 0 && node->parent == &tree->root)
368 return TRUE;
369
370 if (prefix_len == 0)
371 return FALSE;
372
373 full_name = dsync_mailbox_node_get_full_name(tree, node);
374 if (node->ns->prefix[prefix_len-1] == mail_namespace_get_sep(node->ns))
375 prefix_len--;
376 return strncmp(full_name, node->ns->prefix, prefix_len) == 0 &&
377 full_name[prefix_len] == '\0';
378 }
379
380 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)381 sync_rename_node_to_temp(struct dsync_mailbox_tree_sync_ctx *ctx,
382 struct dsync_mailbox_tree *tree,
383 struct dsync_mailbox_node *node,
384 struct dsync_mailbox_node *new_parent,
385 const char **reason_r)
386 {
387 struct dsync_mailbox_tree_sync_change *change;
388 const char *old_name, *new_name, *p;
389 char name[TEMP_MAX_NAME_LEN+1];
390 buffer_t buf;
391 size_t prefix_len, max_prefix_len;
392 unsigned int counter = 1;
393
394 i_assert(!sync_node_is_namespace_prefix(tree, node));
395
396 buffer_create_from_data(&buf, name, sizeof(name));
397 max_prefix_len = TEMP_MAX_NAME_LEN - TEMP_SUFFIX_MAX_LEN - 1;
398 if (node->sync_temporary_name) {
399 /* the source name was also a temporary name. drop the
400 -<suffix> from it */
401 p = strrchr(node->name, '-');
402 i_assert(p != NULL);
403 if (max_prefix_len > (size_t)(p - node->name))
404 max_prefix_len = p - node->name;
405 }
406 str_append_max(&buf, node->name, max_prefix_len);
407 str_append_c(&buf, '-');
408 prefix_len = buf.used;
409
410 do {
411 str_truncate(&buf, prefix_len);
412 str_printfa(&buf, TEMP_SUFFIX_FORMAT, counter++);
413 /* the generated name is quite unlikely to exist,
414 but check anyway.. */
415 } while (node_has_child(node->parent, str_c(&buf)));
416
417 old_name = tree != ctx->local_tree ? NULL :
418 dsync_mailbox_node_get_full_name(tree, node);
419
420 *reason_r = t_strdup_printf("Renamed '%s' to '%s'", node->name, str_c(&buf));
421 node->name = p_strdup(tree->pool, str_c(&buf));
422 node->sync_temporary_name = TRUE;
423 node->last_renamed_or_created = 0;
424 dsync_mailbox_tree_node_move_sorted(node, new_parent);
425
426 if (tree == ctx->local_tree && node_is_existent(node)) {
427 /* we're modifying a local tree. remember this change. */
428 new_name = dsync_mailbox_node_get_full_name(tree, node);
429
430 i_assert(ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL);
431 i_assert(strcmp(old_name, "INBOX") != 0);
432 change = array_append_space(&ctx->changes);
433 change->type = DSYNC_MAILBOX_TREE_SYNC_TYPE_RENAME;
434 change->ns = node->ns;
435 change->full_name = p_strdup(ctx->pool, old_name);
436 change->rename_dest_name = p_strdup(ctx->pool, new_name);
437 }
438 }
439
node_has_parent(struct dsync_mailbox_node * node,struct dsync_mailbox_node * parent)440 static bool node_has_parent(struct dsync_mailbox_node *node,
441 struct dsync_mailbox_node *parent)
442 {
443 for (; node != NULL; node = node->parent) {
444 if (node == parent)
445 return TRUE;
446 }
447 return FALSE;
448 }
449
450 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)451 sync_rename_node(struct dsync_mailbox_tree_sync_ctx *ctx,
452 struct dsync_mailbox_tree *tree,
453 struct dsync_mailbox_node *temp_node,
454 struct dsync_mailbox_node *node,
455 const struct dsync_mailbox_node *other_node,
456 const char **reason_r)
457 {
458 struct dsync_mailbox_tree_sync_change *change;
459 struct dsync_mailbox_tree *other_tree;
460 struct dsync_mailbox_node *parent;
461 const char *name, *other_name;
462
463 i_assert(node != NULL);
464 i_assert(other_node != NULL);
465
466 /* move/rename node in the tree, so that its position/name is identical
467 to other_node (in other_tree). temp_node's name is changed to
468 temporary name (i.e. it assumes that node's name becomes temp_node's
469 original name) */
470 other_tree = tree == ctx->local_tree ?
471 ctx->remote_tree : ctx->local_tree;
472
473 parent = sorted_tree_get_by_node_name(tree, other_tree,
474 other_node->parent);
475 if (node_has_parent(parent, node)) {
476 /* don't introduce a loop. temporarily rename node
477 under root. */
478 sync_rename_node_to_temp(ctx, tree, node, &tree->root, reason_r);
479 *reason_r = t_strconcat(*reason_r, " (Don't introduce loop)", NULL);
480 return;
481 }
482 sync_rename_node_to_temp(ctx, tree, temp_node, temp_node->parent, reason_r);
483
484 /* get the old name before it's modified */
485 name = dsync_mailbox_node_get_full_name(tree, node);
486
487 /* set the new name */
488 *reason_r = t_strdup_printf("%s + Renamed '%s' to '%s'",
489 *reason_r, name, other_node->name);
490 node->name = p_strdup(tree->pool, other_node->name);
491 node->sync_temporary_name = other_node->sync_temporary_name;
492 node->last_renamed_or_created = other_node->last_renamed_or_created;
493 /* change node's parent if necessary. in any case detach+reattach it
494 sorted, because the nodes must be sorted by name, and the node's
495 name (or its parent) changed. */
496 dsync_mailbox_tree_node_move_sorted(node, parent);
497
498 if (tree == ctx->local_tree && node_is_existent(node)) {
499 /* we're modifying a local tree. remember this change. */
500 other_name = dsync_mailbox_node_get_full_name(other_tree, other_node);
501
502 i_assert(ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL);
503 i_assert(strcmp(name, "INBOX") != 0);
504 change = array_append_space(&ctx->changes);
505 change->type = DSYNC_MAILBOX_TREE_SYNC_TYPE_RENAME;
506 change->ns = node->ns;
507 change->full_name = p_strdup(ctx->pool, name);
508 change->rename_dest_name = p_strdup(ctx->pool, other_name);
509 }
510 }
511
node_mailbox_guids_cmp(struct dsync_mailbox_node * node1,struct dsync_mailbox_node * node2)512 static int node_mailbox_guids_cmp(struct dsync_mailbox_node *node1,
513 struct dsync_mailbox_node *node2)
514 {
515 int ret;
516
517 while (node1 != NULL && node2 != NULL) {
518 if (node1->existence == DSYNC_MAILBOX_NODE_EXISTS &&
519 node2->existence != DSYNC_MAILBOX_NODE_EXISTS)
520 return -1;
521 if (node2->existence == DSYNC_MAILBOX_NODE_EXISTS &&
522 node1->existence != DSYNC_MAILBOX_NODE_EXISTS)
523 return 1;
524
525 ret = memcmp(node1->mailbox_guid, node2->mailbox_guid,
526 sizeof(node1->mailbox_guid));
527 if (ret != 0)
528 return ret;
529
530 ret = node_mailbox_guids_cmp(node1->first_child,
531 node2->first_child);
532 if (ret != 0)
533 return ret;
534 node1 = node1->next;
535 node2 = node2->next;
536 }
537 if (node1 == NULL && node2 == NULL)
538 return 0;
539 return node1 != NULL ? -1 : 1;
540 }
541
node_mailbox_names_cmp(struct dsync_mailbox_node * node1,struct dsync_mailbox_node * node2)542 static int node_mailbox_names_cmp(struct dsync_mailbox_node *node1,
543 struct dsync_mailbox_node *node2)
544 {
545 int ret;
546
547 while (node1 != NULL && node2 != NULL) {
548 ret = strcmp(node1->name, node2->name);
549 if (ret != 0)
550 return ret;
551
552 ret = node_mailbox_names_cmp(node1->first_child,
553 node2->first_child);
554 if (ret != 0)
555 return ret;
556 node1 = node1->next;
557 node2 = node2->next;
558 }
559 if (node1 == NULL && node2 == NULL)
560 return 0;
561 return node1 != NULL ? -1 : 1;
562 }
563
node_mailbox_trees_cmp(struct dsync_mailbox_node * node1,struct dsync_mailbox_node * node2)564 static int node_mailbox_trees_cmp(struct dsync_mailbox_node *node1,
565 struct dsync_mailbox_node *node2)
566 {
567 int ret;
568
569 ret = node_mailbox_guids_cmp(node1, node2);
570 if (ret == 0) {
571 /* only a directory name changed and all the timestamps
572 are equal. just pick the alphabetically smaller. */
573 ret = node_mailbox_names_cmp(node1, node2);
574 }
575 i_assert(ret != 0);
576 return ret;
577 }
578
nodes_get_timestamp(struct dsync_mailbox_node * node1,struct dsync_mailbox_node * node2)579 static time_t nodes_get_timestamp(struct dsync_mailbox_node *node1,
580 struct dsync_mailbox_node *node2)
581 {
582 time_t ts = 0;
583
584 /* avoid using temporary names in case all the timestamps are 0 */
585 if (node1 != NULL && !node1->sync_temporary_name)
586 ts = node1->last_renamed_or_created + 1;
587 if (node2 != NULL && !node2->sync_temporary_name &&
588 ts <= node2->last_renamed_or_created)
589 ts = node2->last_renamed_or_created + 1;
590 return ts;
591 }
592
sync_node_is_namespace_root(struct dsync_mailbox_tree * tree,struct dsync_mailbox_node * node)593 static bool sync_node_is_namespace_root(struct dsync_mailbox_tree *tree,
594 struct dsync_mailbox_node *node)
595 {
596 if (node == NULL)
597 return FALSE;
598 if (node == &tree->root)
599 return TRUE;
600 return sync_node_is_namespace_prefix(tree, node);
601 }
602
603 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)604 sync_rename_lower_ts(struct dsync_mailbox_tree_sync_ctx *ctx,
605 struct dsync_mailbox_node *local_node1,
606 struct dsync_mailbox_node *remote_node1,
607 struct dsync_mailbox_node *local_node2,
608 struct dsync_mailbox_node *remote_node2,
609 const char **reason_r)
610 {
611 time_t local_ts, remote_ts;
612
613 /* We're scanning the tree at the position of local_node1
614 and remote_node2. They have identical names. We also know that
615 local_node1&remote_node1 and local_node2&remote_node2 are "the same"
616 either because their GUIDs or (in case of one being a directory)
617 their childrens' GUIDs match. We don't know where local_node2 or
618 remote_node1 are located in the mailbox tree, or if they exist
619 at all. Note that node1 and node2 may be the same node pointers. */
620 i_assert(strcmp(local_node1->name, remote_node2->name) == 0);
621
622 if (sync_node_is_namespace_root(ctx->remote_tree, remote_node1) ||
623 sync_node_is_namespace_root(ctx->remote_tree, remote_node2) ||
624 sync_node_is_namespace_root(ctx->local_tree, local_node1) ||
625 sync_node_is_namespace_root(ctx->local_tree, local_node2)) {
626 local_node1->sync_delayed_guid_change = TRUE;
627 remote_node2->sync_delayed_guid_change = TRUE;
628 *reason_r = "Can't rename namespace prefixes - will be merged later";
629 return FALSE;
630 }
631
632 local_ts = nodes_get_timestamp(local_node1, local_node2);
633 remote_ts = nodes_get_timestamp(remote_node1, remote_node2);
634
635 if (ctx->sync_type == DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL)
636 local_ts = remote_ts+1;
637 else if (ctx->sync_type == DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_REMOTE)
638 remote_ts = local_ts+1;
639
640 /* The algorithm must be deterministic regardless of the sync direction,
641 so in case the timestamps are equal we need to resort to looking at
642 the other data. We'll start by looking at the nodes' mailbox GUIDs,
643 but if both of them don't exist continue looking into their
644 children. */
645 if (local_ts > remote_ts ||
646 (local_ts == remote_ts &&
647 node_mailbox_trees_cmp(local_node1, remote_node2) < 0)) {
648 /* local nodes have a higher timestamp. we only want to do
649 renames where the destination parent is the current node's
650 (local_node1/remote_node2) parent. */
651
652 /* Numbers are GUIDs, letters are mailbox names:
653
654 local 1A <-name conflict-> remote 2A
655 local 2B <- potentially -> remote 1[BC]
656
657 Here we want to preserve the local 1A & 2B names: */
658 if (local_node2 == NULL) {
659 /* local : 1A
660 remote: 1B, 2A -> 2A-temp, 1A */
661 sync_rename_node(ctx, ctx->remote_tree, remote_node2,
662 remote_node1, local_node1, reason_r);
663 *reason_r = t_strconcat(*reason_r, "(local: local_node2=NULL)", NULL);
664 return TRUE;
665 } else if (remote_node1 == remote_node2) {
666 /* FIXME: this fixes an infinite loop when in
667 rename2 test, think it through why :) */
668 *reason_r = "local: remote_node1=remote_node2";
669 } else if (remote_node1 != NULL) {
670 /* a) local_node1->parent == local_node2->parent
671
672 local : 1A, 2B
673 remote: 1B, 2A -> 2A-temp, 1A(, 2B)
674 remote: 1C, 2A -> 2B, 1A
675 remote: 1C, 2A, 3B -> 2A-temp, 1A(, 3B-temp, 2B)
676
677 b) local_node1->parent != local_node2->parent
678
679 local : 1X/A, 2Y/B
680 remote: 1Y/B, 2X/A -> 2X/A-temp, 1X/A(, 2Y/B)
681 remote: 1Z/C, 2X/A -> 2X/A-temp, 1X/A
682 remote: 1Z/C, 2X/A, 3Y/B -> 2X/A-temp, 1X/A
683
684 We can handle all of these more easily by simply
685 always renaming 2 to a temporary name and handling
686 it when we reach B handling. */
687 sync_rename_node(ctx, ctx->remote_tree, remote_node2,
688 remote_node1, local_node1, reason_r);
689 *reason_r = t_strconcat(*reason_r, "(local: remote_node1=NULL)", NULL);
690 return TRUE;
691 } else if (node_has_parent(local_node1, local_node2) &&
692 ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL) {
693 /* node2 is a parent of node1, but it should be
694 vice versa */
695 sync_rename_node_to_temp(ctx, ctx->local_tree,
696 local_node1, local_node2->parent, reason_r);
697 *reason_r = t_strconcat(*reason_r, "(local: node2 parent of node1)", NULL);
698 return TRUE;
699 } else if (node_has_parent(local_node2, local_node1) &&
700 ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL) {
701 /* node1 is a parent of node2, but it should be
702 vice versa */
703 sync_rename_node_to_temp(ctx, ctx->local_tree,
704 local_node2, local_node1->parent, reason_r);
705 *reason_r = t_strconcat(*reason_r, "(local: node1 parent of node2)", NULL);
706 return TRUE;
707 } else if (local_node1->existence == DSYNC_MAILBOX_NODE_EXISTS) {
708 sync_rename_node_to_temp(ctx, ctx->remote_tree,
709 remote_node2, remote_node2->parent, reason_r);
710 *reason_r = t_strconcat(*reason_r, "(local: local_node1 exists)", NULL);
711 return TRUE;
712 } else {
713 /* local : 1A, 2B
714 remote: 2A -> (2B)
715 remote: 2A, 3B -> (3B-temp, 2B) */
716 *reason_r = "local: unchanged";
717 }
718 } else {
719 /* remote nodes have a higher timestamp */
720 if (remote_node1 == NULL) {
721 sync_rename_node(ctx, ctx->local_tree, local_node1,
722 local_node2, remote_node2, reason_r);
723 *reason_r = t_strconcat(*reason_r, "(remote: remote_node1=NULL)", NULL);
724 return TRUE;
725 } else if (local_node2 == local_node1) {
726 *reason_r = "remote: remote_node2=remote_node1";
727 } else if (local_node2 != NULL) {
728 sync_rename_node(ctx, ctx->local_tree, local_node1,
729 local_node2, remote_node2, reason_r);
730 *reason_r = t_strconcat(*reason_r, "(remote: local_node2=NULL)", NULL);
731 return TRUE;
732 } else if (node_has_parent(remote_node1, remote_node2) &&
733 ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_REMOTE) {
734 sync_rename_node_to_temp(ctx, ctx->remote_tree,
735 remote_node1, remote_node2->parent, reason_r);
736 *reason_r = t_strconcat(*reason_r, "(remote: node2 parent of node1)", NULL);
737 return TRUE;
738 } else if (node_has_parent(remote_node2, remote_node1) &&
739 ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_REMOTE) {
740 sync_rename_node_to_temp(ctx, ctx->remote_tree,
741 remote_node2, remote_node1->parent, reason_r);
742 *reason_r = t_strconcat(*reason_r, "(remote: node1 parent of node2)", NULL);
743 return TRUE;
744 } else if (remote_node2->existence == DSYNC_MAILBOX_NODE_EXISTS) {
745 sync_rename_node_to_temp(ctx, ctx->local_tree,
746 local_node1, local_node1->parent, reason_r);
747 *reason_r = t_strconcat(*reason_r, "(remote: remote_node2 exists)", NULL);
748 return TRUE;
749 } else {
750 *reason_r = "remote: unchanged";
751 }
752 }
753 return FALSE;
754 }
755
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)756 static bool sync_rename_conflict(struct dsync_mailbox_tree_sync_ctx *ctx,
757 struct dsync_mailbox_node *local_node1,
758 struct dsync_mailbox_node *remote_node2,
759 const char **reason_r)
760 {
761 struct dsync_mailbox_node *local_node2, *remote_node1;
762 const uint8_t *guid_p;
763 bool ret;
764
765 guid_p = local_node1->mailbox_guid;
766 remote_node1 = hash_table_lookup(ctx->remote_tree->guid_hash, guid_p);
767 guid_p = remote_node2->mailbox_guid;
768 local_node2 = hash_table_lookup(ctx->local_tree->guid_hash, guid_p);
769
770 if ((remote_node1 != NULL && remote_node1->existence == DSYNC_MAILBOX_NODE_EXISTS) ||
771 (local_node2 != NULL && local_node2->existence == DSYNC_MAILBOX_NODE_EXISTS)) {
772 /* conflicting name, rename the one with lower timestamp */
773 ret = sync_rename_lower_ts(ctx, local_node1, remote_node1,
774 local_node2, remote_node2, reason_r);
775 *reason_r = t_strconcat("conflicting name: ", *reason_r, NULL);
776 return ret;
777 } else if (dsync_mailbox_node_is_dir(local_node1) ||
778 dsync_mailbox_node_is_dir(remote_node2)) {
779 /* one of the nodes is a directory, and the other is a mailbox
780 that doesn't exist on the other side. there is no conflict,
781 we'll just need to create the mailbox later. */
782 *reason_r = "mailbox not selectable yet";
783 return FALSE;
784 } else {
785 /* both nodes are mailboxes that don't exist on the other side.
786 we'll merge these mailboxes together later and change their
787 GUIDs and UIDVALIDITYs to be the same */
788 local_node1->sync_delayed_guid_change = TRUE;
789 remote_node2->sync_delayed_guid_change = TRUE;
790 *reason_r = "GUIDs conflict - will be merged later";
791 return FALSE;
792 }
793 }
794
795 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)796 sync_find_branch(struct dsync_mailbox_tree *tree,
797 struct dsync_mailbox_tree *other_tree,
798 struct dsync_mailbox_node *dir_node)
799 {
800 struct dsync_mailbox_node *node, *other_node;
801 const uint8_t *guid_p;
802
803 for (node = dir_node->first_child; node != NULL; node = node->next) {
804 if (dsync_mailbox_node_is_dir(node)) {
805 other_node = sync_find_branch(tree, other_tree, node);
806 if (other_node != NULL)
807 return other_node;
808 } else {
809 guid_p = node->mailbox_guid;
810 other_node = hash_table_lookup(other_tree->guid_hash,
811 guid_p);
812 if (other_node != NULL)
813 return other_node->parent;
814 }
815 }
816 return NULL;
817 }
818
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)819 static bool sync_rename_directory(struct dsync_mailbox_tree_sync_ctx *ctx,
820 struct dsync_mailbox_node *local_node1,
821 struct dsync_mailbox_node *remote_node2,
822 const char **reason_r)
823 {
824 struct dsync_mailbox_node *remote_node1, *local_node2;
825
826 /* see if we can find matching mailbox branches based on the nodes'
827 child mailboxes (with GUIDs). we can then rename the entire branch.
828 don't try to do this for namespace prefixes though. */
829 remote_node1 = sync_find_branch(ctx->local_tree,
830 ctx->remote_tree, local_node1);
831 local_node2 = sync_find_branch(ctx->remote_tree, ctx->local_tree,
832 remote_node2);
833 if (remote_node1 == NULL || local_node2 == NULL) {
834 *reason_r = "Directory rename branch not found";
835 return FALSE;
836 }
837 if (node_names_equal(remote_node1, local_node2)) {
838 *reason_r = "Directory name paths are equal";
839 return FALSE;
840 }
841
842 return sync_rename_lower_ts(ctx, local_node1, remote_node1,
843 local_node2, remote_node2, reason_r);
844 }
845
sync_rename_mailboxes(struct dsync_mailbox_tree_sync_ctx * ctx,struct dsync_mailbox_node * local_parent,struct dsync_mailbox_node * remote_parent)846 static bool sync_rename_mailboxes(struct dsync_mailbox_tree_sync_ctx *ctx,
847 struct dsync_mailbox_node *local_parent,
848 struct dsync_mailbox_node *remote_parent)
849 {
850 struct dsync_mailbox_node **local_nodep = &local_parent->first_child;
851 struct dsync_mailbox_node **remote_nodep = &remote_parent->first_child;
852 struct dsync_mailbox_node *local_node, *remote_node;
853 const char *reason;
854 string_t *debug = NULL;
855 bool changed;
856
857 if ((ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_DEBUG) != 0)
858 debug = t_str_new(128);
859
860 /* the nodes are sorted by their names. */
861 while (*local_nodep != NULL || *remote_nodep != NULL) {
862 local_node = *local_nodep;
863 remote_node = *remote_nodep;
864
865 if (local_node == NULL ||
866 (remote_node != NULL &&
867 strcmp(local_node->name, remote_node->name) > 0)) {
868 /* add a missing local node */
869 local_node = sync_node_new(ctx->local_tree, local_nodep,
870 local_parent, remote_node);
871 }
872 if (remote_node == NULL ||
873 strcmp(remote_node->name, local_node->name) > 0) {
874 /* add a missing remote node */
875 remote_node = sync_node_new(ctx->remote_tree, remote_nodep,
876 remote_parent, local_node);
877 }
878 i_assert(strcmp(local_node->name, remote_node->name) == 0);
879 if (debug != NULL) {
880 str_truncate(debug, 0);
881 str_append(debug, "Mailbox ");
882 dsync_mailbox_node_append_full_name(debug, ctx->local_tree, local_node);
883 str_printfa(debug, ": local=%s/%ld/%d, remote=%s/%ld/%d",
884 guid_128_to_string(local_node->mailbox_guid),
885 (long)local_node->last_renamed_or_created,
886 local_node->existence,
887 guid_128_to_string(remote_node->mailbox_guid),
888 (long)remote_node->last_renamed_or_created,
889 remote_node->existence);
890 }
891
892 if (dsync_mailbox_node_is_dir(local_node) &&
893 dsync_mailbox_node_is_dir(remote_node)) {
894 /* both nodes are directories (or other side is
895 nonexistent). see if we can match them by their
896 child mailboxes */
897 changed = sync_rename_directory(ctx, local_node, remote_node, &reason);
898 } else if (dsync_mailbox_node_guids_equal(local_node,
899 remote_node)) {
900 /* mailboxes are equal, no need to rename */
901 reason = "Mailboxes are equal";
902 changed = FALSE;
903 } else {
904 /* mailbox naming conflict */
905 changed = sync_rename_conflict(ctx, local_node,
906 remote_node, &reason);
907 }
908 /* handle children, if there are any */
909 if (debug != NULL) {
910 i_debug("brain %c: %s: %s",
911 (ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_MASTER_BRAIN) != 0 ? 'M' : 'S',
912 str_c(debug), reason);
913 }
914
915 if (!changed) T_BEGIN {
916 changed = sync_rename_mailboxes(ctx, local_node,
917 remote_node);
918 } T_END;
919 if (changed)
920 return TRUE;
921
922 local_nodep = &local_node->next;
923 remote_nodep = &remote_node->next;
924 }
925 return FALSE;
926 }
927
mailbox_node_hash_first_child(struct dsync_mailbox_node * node,struct md5_context * md5)928 static bool mailbox_node_hash_first_child(struct dsync_mailbox_node *node,
929 struct md5_context *md5)
930 {
931 for (node = node->first_child; node != NULL; node = node->next) {
932 if (node->existence == DSYNC_MAILBOX_NODE_EXISTS) {
933 md5_update(md5, node->mailbox_guid,
934 sizeof(node->mailbox_guid));
935 md5_update(md5, node->name, strlen(node->name));
936 return TRUE;
937 }
938 if (node->first_child != NULL) {
939 if (mailbox_node_hash_first_child(node, md5))
940 return TRUE;
941 }
942 }
943 return FALSE;
944 }
945
946 static const char *
mailbox_node_generate_suffix(struct dsync_mailbox_node * node)947 mailbox_node_generate_suffix(struct dsync_mailbox_node *node)
948 {
949 struct md5_context md5;
950 unsigned char digest[MD5_RESULTLEN];
951
952 if (!dsync_mailbox_node_is_dir(node))
953 return guid_128_to_string(node->mailbox_guid);
954
955 md5_init(&md5);
956 if (!mailbox_node_hash_first_child(node, &md5))
957 i_unreached(); /* we would have deleted it */
958 md5_final(&md5, digest);
959 return binary_to_hex(digest, sizeof(digest));
960 }
961
suffix_inc(string_t * str)962 static void suffix_inc(string_t *str)
963 {
964 char *data;
965 size_t i;
966
967 data = str_c_modifiable(str) + str_len(str)-1;
968 for (i = str_len(str); i > 0; i--, data--) {
969 if ((*data >= '0' && *data < '9') ||
970 (*data >= 'a' && *data < 'f')) {
971 *data += 1;
972 return;
973 } else if (*data == '9') {
974 *data = 'a';
975 return;
976 } else if (*data != 'f') {
977 i_unreached();
978 }
979 }
980 i_unreached();
981 }
982
983 static void
sync_rename_temp_mailbox_node(struct dsync_mailbox_tree * tree,struct dsync_mailbox_node * node,const char ** reason_r)984 sync_rename_temp_mailbox_node(struct dsync_mailbox_tree *tree,
985 struct dsync_mailbox_node *node,
986 const char **reason_r)
987 {
988 const char *p, *new_suffix;
989 string_t *str = t_str_new(256);
990 size_t max_prefix_len;
991
992 /* The name is currently <oldname>-<temp>. Both sides need to
993 use equivalent names, so we'll replace the <temp> if possible
994 with a) mailbox GUID, b) sha1 of childrens' (GUID|name)s. In the
995 very unlikely case of such name already existing, just increase
996 the last letters until it's not found. */
997 new_suffix = mailbox_node_generate_suffix(node);
998
999 p = strrchr(node->name, '-');
1000 i_assert(p != NULL);
1001 p++;
1002 max_prefix_len = TEMP_MAX_NAME_LEN - strlen(new_suffix) - 1;
1003 if (max_prefix_len > (size_t)(p-node->name))
1004 max_prefix_len = p-node->name;
1005 str_append_max(str, node->name, max_prefix_len);
1006 str_append(str, new_suffix);
1007 while (node_has_child(node->parent, str_c(str)))
1008 suffix_inc(str);
1009
1010 *reason_r = t_strdup_printf("Renamed '%s' to '%s'",
1011 dsync_mailbox_node_get_full_name(tree, node), str_c(str));
1012 node->name = p_strdup(tree->pool, str_c(str));
1013
1014 dsync_mailbox_tree_node_move_sorted(node, node->parent);
1015 node->sync_temporary_name = FALSE;
1016 }
1017
1018 static void
sync_rename_delete_node_dirs(struct dsync_mailbox_tree_sync_ctx * ctx,struct dsync_mailbox_tree * tree,struct dsync_mailbox_node * node)1019 sync_rename_delete_node_dirs(struct dsync_mailbox_tree_sync_ctx *ctx,
1020 struct dsync_mailbox_tree *tree,
1021 struct dsync_mailbox_node *node)
1022 {
1023 struct dsync_mailbox_node *child;
1024
1025 for (child = node->first_child; child != NULL; child = child->next)
1026 sync_rename_delete_node_dirs(ctx, tree, child);
1027
1028 if (tree == ctx->local_tree &&
1029 ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL &&
1030 node->existence != DSYNC_MAILBOX_NODE_NONEXISTENT) {
1031 sync_add_dir_change(ctx, node,
1032 DSYNC_MAILBOX_TREE_SYNC_TYPE_DELETE_DIR);
1033 }
1034 node->existence = DSYNC_MAILBOX_NODE_NONEXISTENT;
1035 node->sync_temporary_name = FALSE;
1036 }
1037
1038 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)1039 sync_rename_temp_mailboxes(struct dsync_mailbox_tree_sync_ctx *ctx,
1040 struct dsync_mailbox_tree *tree,
1041 struct dsync_mailbox_node *node, bool *renames_r)
1042 {
1043 const char *reason;
1044
1045 for (; node != NULL; node = node->next) {
1046 while (sync_rename_temp_mailboxes(ctx, tree, node->first_child, renames_r)) ;
1047
1048 if (!node->sync_temporary_name) {
1049 } else if (dsync_mailbox_node_is_dir(node) &&
1050 (node->first_child == NULL ||
1051 !node_has_existent_children(node, FALSE))) {
1052 /* we can just delete this directory and
1053 any child directories it may have */
1054 if ((ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_DEBUG) != 0) {
1055 i_debug("brain %c: %s mailbox %s: Delete directory-only tree",
1056 (ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_MASTER_BRAIN) != 0 ? 'M' : 'S',
1057 tree == ctx->local_tree ? "local" : "remote",
1058 dsync_mailbox_node_get_full_name(tree, node));
1059 }
1060 sync_rename_delete_node_dirs(ctx, tree, node);
1061 } else {
1062 T_BEGIN {
1063 *renames_r = TRUE;
1064 sync_rename_temp_mailbox_node(tree, node, &reason);
1065 if ((ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_DEBUG) != 0) {
1066 i_debug("brain %c: %s mailbox %s: %s",
1067 (ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_MASTER_BRAIN) != 0 ? 'M' : 'S',
1068 tree == ctx->local_tree ? "local" : "remote",
1069 dsync_mailbox_node_get_full_name(tree, node), reason);
1070 }
1071 } T_END;
1072 return TRUE;
1073 }
1074 }
1075 return FALSE;
1076 }
1077
1078 static int
dsync_mailbox_tree_handle_renames(struct dsync_mailbox_tree_sync_ctx * ctx,bool * renames_r)1079 dsync_mailbox_tree_handle_renames(struct dsync_mailbox_tree_sync_ctx *ctx,
1080 bool *renames_r)
1081 {
1082 unsigned int max_renames, count = 0;
1083 bool changed;
1084
1085 *renames_r = FALSE;
1086
1087 max_renames = ctx->combined_mailboxes_count * 3;
1088 do {
1089 T_BEGIN {
1090 changed = sync_rename_mailboxes(ctx, &ctx->local_tree->root,
1091 &ctx->remote_tree->root);
1092 } T_END;
1093 if ((ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_DEBUG) != 0 &&
1094 changed) {
1095 i_debug("brain %c: -- Mailbox renamed, restart sync --",
1096 (ctx->sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_MASTER_BRAIN) != 0 ? 'M' : 'S');
1097 }
1098 } while (changed && ++count <= max_renames);
1099
1100 if (changed) {
1101 i_error("BUG: Mailbox renaming algorithm got into a potentially infinite loop, aborting");
1102 return -1;
1103 }
1104
1105 while (sync_rename_temp_mailboxes(ctx, ctx->local_tree, &ctx->local_tree->root, renames_r)) ;
1106 while (sync_rename_temp_mailboxes(ctx, ctx->remote_tree, &ctx->remote_tree->root, renames_r)) ;
1107 return 0;
1108 }
1109
sync_is_wrong_mailbox(struct dsync_mailbox_node * node,const struct dsync_mailbox_node * wanted_node,const char ** reason_r)1110 static bool sync_is_wrong_mailbox(struct dsync_mailbox_node *node,
1111 const struct dsync_mailbox_node *wanted_node,
1112 const char **reason_r)
1113 {
1114 if (wanted_node->existence != DSYNC_MAILBOX_NODE_EXISTS) {
1115 *reason_r = wanted_node->existence == DSYNC_MAILBOX_NODE_DELETED ?
1116 "Mailbox has been deleted" : "Mailbox doesn't exist";
1117 return TRUE;
1118 }
1119 if (node->uid_validity != wanted_node->uid_validity) {
1120 *reason_r = t_strdup_printf("UIDVALIDITY changed (%u -> %u)",
1121 wanted_node->uid_validity,
1122 node->uid_validity);
1123 return TRUE;
1124 }
1125 if (node->uid_next > wanted_node->uid_next) {
1126 /* we can't lower the UIDNEXT */
1127 *reason_r = t_strdup_printf("UIDNEXT is too high (%u > %u)",
1128 node->uid_next,
1129 wanted_node->uid_next);
1130 return TRUE;
1131 }
1132 if (memcmp(node->mailbox_guid, wanted_node->mailbox_guid,
1133 sizeof(node->mailbox_guid)) != 0) {
1134 *reason_r = "GUID changed";
1135 return TRUE;
1136 }
1137 return FALSE;
1138 }
1139
1140 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)1141 sync_delete_wrong_mailboxes_branch(struct dsync_mailbox_tree_sync_ctx *ctx,
1142 struct dsync_mailbox_tree *tree,
1143 const struct dsync_mailbox_tree *wanted_tree,
1144 struct dsync_mailbox_node *node,
1145 const struct dsync_mailbox_node *wanted_node)
1146 {
1147 const char *reason;
1148 int ret;
1149
1150 while (node != NULL && wanted_node != NULL) {
1151 if (node->first_child != NULL) {
1152 sync_delete_wrong_mailboxes_branch(ctx,
1153 tree, wanted_tree,
1154 node->first_child, wanted_node->first_child);
1155 }
1156 ret = strcmp(node->name, wanted_node->name);
1157 if (ret < 0) {
1158 /* node shouldn't exist */
1159 if (node->existence == DSYNC_MAILBOX_NODE_EXISTS &&
1160 !dsync_mailbox_node_is_dir(node)) {
1161 sync_delete_mailbox_node(ctx, tree, node,
1162 "Mailbox doesn't exist");
1163 }
1164 node = node->next;
1165 } else if (ret > 0) {
1166 /* wanted_node doesn't exist. it's created later. */
1167 wanted_node = wanted_node->next;
1168 } else T_BEGIN {
1169 if (sync_is_wrong_mailbox(node, wanted_node, &reason) &&
1170 node->existence == DSYNC_MAILBOX_NODE_EXISTS &&
1171 !dsync_mailbox_node_is_dir(node))
1172 sync_delete_mailbox_node(ctx, tree, node, reason);
1173 node = node->next;
1174 wanted_node = wanted_node->next;
1175 } T_END;
1176 }
1177 for (; node != NULL; node = node->next) {
1178 /* node and its children shouldn't exist */
1179 if (node->first_child != NULL) {
1180 sync_delete_wrong_mailboxes_branch(ctx,
1181 tree, wanted_tree,
1182 node->first_child, NULL);
1183 }
1184 if (node->existence == DSYNC_MAILBOX_NODE_EXISTS &&
1185 !dsync_mailbox_node_is_dir(node))
1186 sync_delete_mailbox_node(ctx, tree, node, "Mailbox doesn't exist");
1187 }
1188 }
1189
1190 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)1191 sync_delete_wrong_mailboxes(struct dsync_mailbox_tree_sync_ctx *ctx,
1192 struct dsync_mailbox_tree *tree,
1193 const struct dsync_mailbox_tree *wanted_tree)
1194 {
1195 sync_delete_wrong_mailboxes_branch(ctx, tree, wanted_tree,
1196 tree->root.first_child,
1197 wanted_tree->root.first_child);
1198 }
1199
sync_create_mailboxes(struct dsync_mailbox_tree_sync_ctx * ctx,struct dsync_mailbox_tree * tree)1200 static void sync_create_mailboxes(struct dsync_mailbox_tree_sync_ctx *ctx,
1201 struct dsync_mailbox_tree *tree)
1202 {
1203 struct dsync_mailbox_tree *other_tree;
1204 struct dsync_mailbox_tree_iter *iter;
1205 struct dsync_mailbox_node *node, *other_node;
1206 const char *name;
1207 const uint8_t *guid_p;
1208
1209 other_tree = tree == ctx->local_tree ?
1210 ctx->remote_tree : ctx->local_tree;
1211
1212 iter = dsync_mailbox_tree_iter_init(tree);
1213 while (dsync_mailbox_tree_iter_next(iter, &name, &node)) {
1214 /* make sure the renaming handled everything */
1215 i_assert(!node->sync_temporary_name);
1216 if (dsync_mailbox_node_is_dir(node))
1217 continue;
1218
1219 i_assert(node->existence == DSYNC_MAILBOX_NODE_EXISTS);
1220
1221 guid_p = node->mailbox_guid;
1222 other_node = hash_table_lookup(other_tree->guid_hash, guid_p);
1223 if (other_node == NULL)
1224 other_node = sorted_tree_get(other_tree, name);
1225 if (dsync_mailbox_node_is_dir(other_node)) {
1226 /* create a missing mailbox */
1227 other_node->existence = DSYNC_MAILBOX_NODE_EXISTS;
1228 other_node->ns = node->ns;
1229 other_node->uid_validity = node->uid_validity;
1230 memcpy(other_node->mailbox_guid, node->mailbox_guid,
1231 sizeof(other_node->mailbox_guid));
1232 if (other_tree == ctx->local_tree)
1233 sync_add_create_change(ctx, other_node, name);
1234 } else if (!guid_128_equals(node->mailbox_guid,
1235 other_node->mailbox_guid)) {
1236 /* mailbox with same name exists both locally and
1237 remotely, but they have different GUIDs and neither
1238 side has the other's GUID. typically this means that
1239 both sides had autocreated some mailboxes (e.g.
1240 INBOX). we'll just change the GUID for one of
1241 them. */
1242 i_assert(node->existence == DSYNC_MAILBOX_NODE_EXISTS);
1243 i_assert(node->ns == other_node->ns);
1244
1245 if (other_tree == ctx->local_tree)
1246 sync_add_create_change(ctx, node, name);
1247 } else {
1248 /* existing mailbox. mismatching UIDVALIDITY is handled
1249 later while syncing the mailbox. */
1250 i_assert(node->existence == DSYNC_MAILBOX_NODE_EXISTS);
1251 i_assert(node->ns == other_node->ns);
1252 }
1253 }
1254 dsync_mailbox_tree_iter_deinit(&iter);
1255 }
1256
1257 static void
sync_subscription(struct dsync_mailbox_tree_sync_ctx * ctx,struct dsync_mailbox_node * local_node,struct dsync_mailbox_node * remote_node)1258 sync_subscription(struct dsync_mailbox_tree_sync_ctx *ctx,
1259 struct dsync_mailbox_node *local_node,
1260 struct dsync_mailbox_node *remote_node)
1261 {
1262 bool use_local;
1263
1264 if (ctx->sync_type == DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL)
1265 use_local = TRUE;
1266 else if (ctx->sync_type == DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_REMOTE)
1267 use_local = FALSE;
1268 else if (local_node->last_subscription_change > remote_node->last_subscription_change)
1269 use_local = TRUE;
1270 else if (local_node->last_subscription_change < remote_node->last_subscription_change)
1271 use_local = FALSE;
1272 else {
1273 /* local and remote have equal timestamps. prefer to subscribe
1274 rather than unsubscribe. */
1275 use_local = local_node->subscribed;
1276 }
1277 if (use_local) {
1278 /* use local subscription state */
1279 remote_node->subscribed = local_node->subscribed;
1280 } else {
1281 /* use remote subscription state */
1282 local_node->subscribed = remote_node->subscribed;
1283 sync_add_dir_change(ctx, local_node, local_node->subscribed ?
1284 DSYNC_MAILBOX_TREE_SYNC_TYPE_SUBSCRIBE :
1285 DSYNC_MAILBOX_TREE_SYNC_TYPE_UNSUBSCRIBE);
1286 }
1287 }
1288
sync_mailbox_child_dirs(struct dsync_mailbox_tree_sync_ctx * ctx,struct dsync_mailbox_node * local_parent,struct dsync_mailbox_node * remote_parent)1289 static void sync_mailbox_child_dirs(struct dsync_mailbox_tree_sync_ctx *ctx,
1290 struct dsync_mailbox_node *local_parent,
1291 struct dsync_mailbox_node *remote_parent)
1292 {
1293 struct dsync_mailbox_node **local_nodep = &local_parent->first_child;
1294 struct dsync_mailbox_node **remote_nodep = &remote_parent->first_child;
1295 struct dsync_mailbox_node *local_node, *remote_node;
1296 int ret;
1297
1298 /* NOTE: the nodes are always sorted. renaming created all of the
1299 interesting nodes, but it may have left some extra nonexistent nodes
1300 lying around, which we will delete. */
1301 while (*local_nodep != NULL && *remote_nodep != NULL) {
1302 local_node = *local_nodep;
1303 remote_node = *remote_nodep;
1304
1305 ret = strcmp(local_node->name, remote_node->name);
1306 if (ret < 0) {
1307 i_assert(!node_is_existent(local_node));
1308 *local_nodep = local_node->next;
1309 continue;
1310 }
1311 if (ret > 0) {
1312 i_assert(!node_is_existent(remote_node));
1313 *remote_nodep = remote_node->next;
1314 continue;
1315 }
1316
1317 if (local_node->existence == DSYNC_MAILBOX_NODE_EXISTS &&
1318 remote_node->existence == DSYNC_MAILBOX_NODE_NONEXISTENT &&
1319 ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_REMOTE) {
1320 /* create to remote */
1321 remote_node->existence = DSYNC_MAILBOX_NODE_EXISTS;
1322 }
1323 if (remote_node->existence == DSYNC_MAILBOX_NODE_EXISTS &&
1324 local_node->existence == DSYNC_MAILBOX_NODE_NONEXISTENT &&
1325 ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL) {
1326 /* create to local */
1327 local_node->existence = DSYNC_MAILBOX_NODE_EXISTS;
1328 sync_add_dir_change(ctx, local_node,
1329 DSYNC_MAILBOX_TREE_SYNC_TYPE_CREATE_DIR);
1330 }
1331
1332 /* create/delete child dirs */
1333 sync_mailbox_child_dirs(ctx, local_node, remote_node);
1334
1335 if (local_node->subscribed != remote_node->subscribed)
1336 sync_subscription(ctx, local_node, remote_node);
1337
1338 if (local_node->existence == DSYNC_MAILBOX_NODE_DELETED &&
1339 !node_has_existent_children(local_node, TRUE) &&
1340 remote_node->existence == DSYNC_MAILBOX_NODE_EXISTS &&
1341 ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_REMOTE) {
1342 /* delete from remote */
1343 i_assert(!node_has_existent_children(remote_node, TRUE));
1344 remote_node->existence = DSYNC_MAILBOX_NODE_NONEXISTENT;
1345 }
1346 if (remote_node->existence == DSYNC_MAILBOX_NODE_DELETED &&
1347 !node_has_existent_children(remote_node, TRUE) &&
1348 local_node->existence == DSYNC_MAILBOX_NODE_EXISTS &&
1349 ctx->sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL) {
1350 /* delete from local */
1351 i_assert(!node_has_existent_children(local_node, TRUE));
1352 local_node->existence = DSYNC_MAILBOX_NODE_NONEXISTENT;
1353 sync_add_dir_change(ctx, local_node,
1354 DSYNC_MAILBOX_TREE_SYNC_TYPE_DELETE_DIR);
1355 }
1356
1357 local_nodep = &local_node->next;
1358 remote_nodep = &remote_node->next;
1359 }
1360 while (*local_nodep != NULL) {
1361 i_assert(!node_is_existent(*local_nodep));
1362 *local_nodep = (*local_nodep)->next;
1363 }
1364 while (*remote_nodep != NULL) {
1365 i_assert(!node_is_existent(*remote_nodep));
1366 *remote_nodep = (*remote_nodep)->next;
1367 }
1368 }
1369
sync_mailbox_dirs(struct dsync_mailbox_tree_sync_ctx * ctx)1370 static void sync_mailbox_dirs(struct dsync_mailbox_tree_sync_ctx *ctx)
1371 {
1372 sync_mailbox_child_dirs(ctx, &ctx->local_tree->root,
1373 &ctx->remote_tree->root);
1374 }
1375
1376 static void
dsync_mailbox_tree_update_child_timestamps(struct dsync_mailbox_node * node,time_t parent_timestamp)1377 dsync_mailbox_tree_update_child_timestamps(struct dsync_mailbox_node *node,
1378 time_t parent_timestamp)
1379 {
1380 time_t ts;
1381
1382 if (node->last_renamed_or_created < parent_timestamp)
1383 node->last_renamed_or_created = parent_timestamp;
1384 ts = node->last_renamed_or_created;
1385
1386 for (node = node->first_child; node != NULL; node = node->next)
1387 dsync_mailbox_tree_update_child_timestamps(node, ts);
1388 }
1389
1390 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)1391 dsync_mailbox_trees_sync_init(struct dsync_mailbox_tree *local_tree,
1392 struct dsync_mailbox_tree *remote_tree,
1393 enum dsync_mailbox_trees_sync_type sync_type,
1394 enum dsync_mailbox_trees_sync_flags sync_flags)
1395 {
1396 struct dsync_mailbox_tree_sync_ctx *ctx;
1397 unsigned int rename_counter = 0;
1398 bool renames;
1399 pool_t pool;
1400
1401 i_assert(hash_table_is_created(local_tree->guid_hash));
1402 i_assert(hash_table_is_created(remote_tree->guid_hash));
1403
1404 pool = pool_alloconly_create(MEMPOOL_GROWING"dsync mailbox trees sync",
1405 1024*64);
1406 ctx = p_new(pool, struct dsync_mailbox_tree_sync_ctx, 1);
1407 ctx->pool = pool;
1408 ctx->local_tree = local_tree;
1409 ctx->remote_tree = remote_tree;
1410 ctx->sync_type = sync_type;
1411 ctx->sync_flags = sync_flags;
1412 i_array_init(&ctx->changes, 128);
1413
1414 again:
1415 renames = FALSE;
1416 ctx->combined_mailboxes_count = 0;
1417 sync_tree_sort_and_delete_mailboxes(ctx, remote_tree,
1418 sync_type == DSYNC_MAILBOX_TREES_SYNC_TYPE_TWOWAY);
1419 sync_tree_sort_and_delete_mailboxes(ctx, local_tree,
1420 sync_type == DSYNC_MAILBOX_TREES_SYNC_TYPE_TWOWAY);
1421
1422 dsync_mailbox_tree_update_child_timestamps(&local_tree->root, 0);
1423 dsync_mailbox_tree_update_child_timestamps(&remote_tree->root, 0);
1424 if ((sync_flags & DSYNC_MAILBOX_TREES_SYNC_FLAG_NO_RENAMES) == 0) {
1425 if (dsync_mailbox_tree_handle_renames(ctx, &renames) < 0) {
1426 ctx->failed = TRUE;
1427 return ctx;
1428 }
1429 }
1430
1431 /* if we're not doing a two-way sync, delete now any mailboxes, which
1432 a) shouldn't exist, b) doesn't have a matching GUID/UIDVALIDITY,
1433 c) has a too high UIDNEXT */
1434 if (sync_type == DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL)
1435 sync_delete_wrong_mailboxes(ctx, remote_tree, local_tree);
1436 else if (sync_type == DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_REMOTE)
1437 sync_delete_wrong_mailboxes(ctx, local_tree, remote_tree);
1438
1439 if (sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_LOCAL)
1440 sync_create_mailboxes(ctx, remote_tree);
1441 if (sync_type != DSYNC_MAILBOX_TREES_SYNC_TYPE_PRESERVE_REMOTE)
1442 sync_create_mailboxes(ctx, local_tree);
1443 if (renames && rename_counter++ <= ctx->combined_mailboxes_count*3) {
1444 /* this rename algorithm is just horrible. we're retrying this
1445 because the final sync_rename_temp_mailbox_node() calls
1446 give different names to local & remote mailbox trees.
1447 something's not right here, but this looping is better than
1448 a crash in sync_mailbox_dirs() due to trees not matching. */
1449 goto again;
1450 }
1451 sync_mailbox_dirs(ctx);
1452 return ctx;
1453 }
1454
1455 const struct dsync_mailbox_tree_sync_change *
dsync_mailbox_trees_sync_next(struct dsync_mailbox_tree_sync_ctx * ctx)1456 dsync_mailbox_trees_sync_next(struct dsync_mailbox_tree_sync_ctx *ctx)
1457 {
1458 if (ctx->change_idx == array_count(&ctx->changes))
1459 return NULL;
1460 return array_idx(&ctx->changes, ctx->change_idx++);
1461 }
1462
dsync_mailbox_trees_sync_deinit(struct dsync_mailbox_tree_sync_ctx ** _ctx)1463 int dsync_mailbox_trees_sync_deinit(struct dsync_mailbox_tree_sync_ctx **_ctx)
1464 {
1465 struct dsync_mailbox_tree_sync_ctx *ctx = *_ctx;
1466 int ret = ctx->failed ? -1 : 0;
1467
1468 *_ctx = NULL;
1469
1470 array_free(&ctx->changes);
1471 pool_unref(&ctx->pool);
1472 return ret;
1473 }
1474