dovecot/original-hg/dovecot-1.2: src/lib-storage/index/index-sort-string.c annotate

annotate src/lib-storage/index/index-sort-string.c @ 9444:a5d8d201bd39 HEAD

imap: Implemented SORT=DISPLAY extension (draft-ietf-morg-sortdisplay-02).

author	Timo Sirainen <tss@iki.fi>
date	Sun, 18 Oct 2009 18:37:03 -0400
parents	c50f133f0acc
children	00cd9aacd03c

rev	line source
8590 b9faf4db2a9f Updated copyright notices to include year 2009. Timo Sirainen <tss@iki.fi> parents: 8480 diff changeset	1 /* Copyright (c) 2006-2009 Dovecot authors, see the included COPYING file */
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	2
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	3 /* The idea is that we use 32bit integers for string sort IDs which specifiy
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	4 the sort order for primary sort condition. The whole 32bit integer space is
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	5 used and whenever adding a string, the available space is halved and the new
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	6 ID is added in the middle. For example if we add one mail the first time, it
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	7 gets ID 2^31. If we then add two mails which are sorted before the first
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	8 one, they get IDs 2^31/3 and 2^31/3*2. Once we run out of the available
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	9 space between IDs, more space is made by renumbering some IDs.
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	10 */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	11 #include "lib.h"
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	12 #include "array.h"
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	13 #include "str.h"
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	14 #include "index-storage.h"
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	15 #include "index-sort-private.h"
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	16
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	17 #include <stdlib.h>
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	18
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	19 struct mail_sort_node {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	20 uint32_t seq:29;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	21 uint32_t wanted:1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	22 uint32_t no_update:1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	23 uint32_t sort_id_changed:1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	24 uint32_t sort_id;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	25 };
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	26 ARRAY_DEFINE_TYPE(mail_sort_node, struct mail_sort_node);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	27
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	28 struct sort_string_context {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	29 struct mail_search_sort_program *program;
9293 c50f133f0acc sort: Don't assert-crash if sort indexes are broken. Timo Sirainen <tss@iki.fi> parents: 8799 diff changeset	30 const char *primary_sort_name;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	31
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	32 ARRAY_TYPE(mail_sort_node) zero_nodes, nonzero_nodes, sorted_nodes;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	33 const char **sort_strings;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	34 pool_t sort_string_pool;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	35 unsigned int first_missing_sort_id_idx;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	36
8480 f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	37 uint32_t ext_id, last_seq, highest_reset_id, prev_seq;
7569 ea913434d522 Sort index optimization: Don't write changes to sort IDs if we're doing it Timo Sirainen <tss@iki.fi> parents: 7568 diff changeset	38 uint32_t lowest_nonexpunged_zero;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	39
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	40 unsigned int regetting:1;
7567 9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	41 unsigned int have_all_wanted:1;
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	42 unsigned int no_writing:1;
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	43 unsigned int reverse:1;
8480 f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	44 unsigned int seqs_nonsorted:1;
9293 c50f133f0acc sort: Don't assert-crash if sort indexes are broken. Timo Sirainen <tss@iki.fi> parents: 8799 diff changeset	45 unsigned int broken:1;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	46 };
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	47
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	48 static char expunged_msg;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	49 static struct sort_string_context *static_zero_cmp_context;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	50
9293 c50f133f0acc sort: Don't assert-crash if sort indexes are broken. Timo Sirainen <tss@iki.fi> parents: 8799 diff changeset	51 static void index_sort_list_reset_broken(struct sort_string_context *ctx);
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	52 static void index_sort_node_add(struct sort_string_context *ctx,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	53 struct mail_sort_node *node);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	54
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	55 void index_sort_list_init_string(struct mail_search_sort_program *program)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	56 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	57 struct index_mailbox ibox = (struct index_mailbox )program->t->box;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	58 struct sort_string_context *ctx;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	59 const char *name;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	60
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	61 switch (program->sort_program[0] & MAIL_SORT_MASK) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	62 case MAIL_SORT_CC:
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	63 name = "sort-c";
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	64 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	65 case MAIL_SORT_FROM:
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	66 name = "sort-f";
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	67 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	68 case MAIL_SORT_SUBJECT:
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	69 name = "sort-s";
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	70 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	71 case MAIL_SORT_TO:
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	72 name = "sort-t";
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	73 break;
9444 a5d8d201bd39 imap: Implemented SORT=DISPLAY extension (draft-ietf-morg-sortdisplay-02). Timo Sirainen <tss@iki.fi> parents: 9293 diff changeset	74 case MAIL_SORT_DISPLAYFROM:
a5d8d201bd39 imap: Implemented SORT=DISPLAY extension (draft-ietf-morg-sortdisplay-02). Timo Sirainen <tss@iki.fi> parents: 9293 diff changeset	75 name = "sort-df";
a5d8d201bd39 imap: Implemented SORT=DISPLAY extension (draft-ietf-morg-sortdisplay-02). Timo Sirainen <tss@iki.fi> parents: 9293 diff changeset	76 break;
a5d8d201bd39 imap: Implemented SORT=DISPLAY extension (draft-ietf-morg-sortdisplay-02). Timo Sirainen <tss@iki.fi> parents: 9293 diff changeset	77 case MAIL_SORT_DISPLAYTO:
a5d8d201bd39 imap: Implemented SORT=DISPLAY extension (draft-ietf-morg-sortdisplay-02). Timo Sirainen <tss@iki.fi> parents: 9293 diff changeset	78 name = "sort-dt";
a5d8d201bd39 imap: Implemented SORT=DISPLAY extension (draft-ietf-morg-sortdisplay-02). Timo Sirainen <tss@iki.fi> parents: 9293 diff changeset	79 break;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	80 default:
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	81 i_unreached();
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	82 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	83
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	84 program->context = ctx = i_new(struct sort_string_context, 1);
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	85 ctx->reverse = (program->sort_program[0] & MAIL_SORT_FLAG_REVERSE) != 0;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	86 ctx->program = program;
9293 c50f133f0acc sort: Don't assert-crash if sort indexes are broken. Timo Sirainen <tss@iki.fi> parents: 8799 diff changeset	87 ctx->primary_sort_name = name;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	88 ctx->ext_id = mail_index_ext_register(ibox->index, name, 0,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	89 sizeof(uint32_t),
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	90 sizeof(uint32_t));
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	91 i_array_init(&ctx->zero_nodes, 128);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	92 i_array_init(&ctx->nonzero_nodes, 128);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	93 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	94
8480 f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	95 static int sort_node_seq_cmp(const void p1, const void p2)
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	96 {
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	97 const struct mail_sort_node n1 = p1, n2 = p2;
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	98
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	99 if (n1->seq < n2->seq)
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	100 return -1;
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	101 if (n1->seq > n2->seq)
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	102 return 1;
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	103 return 0;
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	104 }
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	105
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	106 static void index_sort_nodes_by_seq(struct sort_string_context *ctx)
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	107 {
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	108 struct mail_sort_node *nodes;
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	109 unsigned int count;
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	110
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	111 nodes = array_get_modifiable(&ctx->zero_nodes, &count);
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	112 qsort(nodes, count, sizeof(struct mail_sort_node), sort_node_seq_cmp);
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	113
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	114 nodes = array_get_modifiable(&ctx->nonzero_nodes, &count);
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	115 qsort(nodes, count, sizeof(struct mail_sort_node), sort_node_seq_cmp);
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	116 }
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	117
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	118 static void index_sort_generate_seqs(struct sort_string_context *ctx)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	119 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	120 struct mail_sort_node nodes, nodes2;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	121 unsigned int i, j, count, count2;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	122 uint32_t seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	123
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	124 nodes = array_get_modifiable(&ctx->nonzero_nodes, &count);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	125 nodes2 = array_get_modifiable(&ctx->zero_nodes, &count2);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	126
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	127 if (!array_is_created(&ctx->program->seqs))
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	128 i_array_init(&ctx->program->seqs, count + count2);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	129 else
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	130 array_clear(&ctx->program->seqs);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	131
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	132 for (i = j = 0;;) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	133 if (i < count && j < count2) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	134 if (nodes[i].seq < nodes2[j].seq)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	135 seq = nodes[i++].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	136 else
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	137 seq = nodes2[j++].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	138 } else if (i < count) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	139 seq = nodes[i++].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	140 } else if (j < count2) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	141 seq = nodes2[j++].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	142 } else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	143 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	144 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	145 array_append(&ctx->program->seqs, &seq, 1);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	146 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	147 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	148
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	149 static void index_sort_reget_sort_ids(struct sort_string_context *ctx)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	150 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	151 struct mail_sort_node node;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	152 const uint32_t *seqs;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	153 unsigned int i, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	154
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	155 i_assert(!ctx->regetting);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	156 ctx->regetting = TRUE;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	157
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	158 index_sort_generate_seqs(ctx);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	159 array_clear(&ctx->zero_nodes);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	160 array_clear(&ctx->nonzero_nodes);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	161
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	162 memset(&node, 0, sizeof(node));
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	163 node.wanted = TRUE;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	164 seqs = array_get(&ctx->program->seqs, &count);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	165 for (i = 0; i < count; i++) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	166 node.seq = seqs[i];
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	167 index_sort_node_add(ctx, &node);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	168 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	169 ctx->regetting = FALSE;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	170 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	171
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	172 static void index_sort_node_add(struct sort_string_context *ctx,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	173 struct mail_sort_node *node)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	174 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	175 struct index_transaction_context *t =
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	176 (struct index_transaction_context *)ctx->program->t;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	177 struct mail_index_map *map;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	178 const void *data;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	179 uint32_t reset_id;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	180 bool expunged;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	181
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	182 mail_index_lookup_ext_full(t->trans_view, node->seq,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	183 ctx->ext_id, &map, &data, &expunged);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	184 if (expunged) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	185 /* we don't want to update expunged messages' sort IDs */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	186 node->no_update = TRUE;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	187 /* we can't trust expunged messages' sort IDs. they might be
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	188 valid, but it's also possible that sort IDs were updated
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	189 and the expunged messages' sort IDs became invalid. we could
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	190 use sort ID if we could know the extension's reset_id at the
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	191 time of the expunge so we could compare it to
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	192 highest_reset_id, but this isn't currently possible. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	193 node->sort_id = 0;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	194 } else {
9293 c50f133f0acc sort: Don't assert-crash if sort indexes are broken. Timo Sirainen <tss@iki.fi> parents: 8799 diff changeset	195 node->sort_id = ctx->broken \|\| data == NULL ? 0 :
c50f133f0acc sort: Don't assert-crash if sort indexes are broken. Timo Sirainen <tss@iki.fi> parents: 8799 diff changeset	196 (const uint32_t )data;
7569 ea913434d522 Sort index optimization: Don't write changes to sort IDs if we're doing it Timo Sirainen <tss@iki.fi> parents: 7568 diff changeset	197 if (node->sort_id == 0) {
ea913434d522 Sort index optimization: Don't write changes to sort IDs if we're doing it Timo Sirainen <tss@iki.fi> parents: 7568 diff changeset	198 if (ctx->lowest_nonexpunged_zero > node->seq \|\|
ea913434d522 Sort index optimization: Don't write changes to sort IDs if we're doing it Timo Sirainen <tss@iki.fi> parents: 7568 diff changeset	199 ctx->lowest_nonexpunged_zero == 0)
ea913434d522 Sort index optimization: Don't write changes to sort IDs if we're doing it Timo Sirainen <tss@iki.fi> parents: 7568 diff changeset	200 ctx->lowest_nonexpunged_zero = node->seq;
9293 c50f133f0acc sort: Don't assert-crash if sort indexes are broken. Timo Sirainen <tss@iki.fi> parents: 8799 diff changeset	201 } else if (ctx->lowest_nonexpunged_zero != 0 &&
c50f133f0acc sort: Don't assert-crash if sort indexes are broken. Timo Sirainen <tss@iki.fi> parents: 8799 diff changeset	202 ctx->lowest_nonexpunged_zero <= node->seq) {
c50f133f0acc sort: Don't assert-crash if sort indexes are broken. Timo Sirainen <tss@iki.fi> parents: 8799 diff changeset	203 index_sort_list_reset_broken(ctx);
c50f133f0acc sort: Don't assert-crash if sort indexes are broken. Timo Sirainen <tss@iki.fi> parents: 8799 diff changeset	204 ctx->broken = TRUE;
c50f133f0acc sort: Don't assert-crash if sort indexes are broken. Timo Sirainen <tss@iki.fi> parents: 8799 diff changeset	205 node->sort_id = 0;
7569 ea913434d522 Sort index optimization: Don't write changes to sort IDs if we're doing it Timo Sirainen <tss@iki.fi> parents: 7568 diff changeset	206 }
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	207 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	208
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	209 if (node->sort_id != 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	210 /* if reset ID increases, lookup all existing messages' sort
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	211 IDs again. if it decreases, ignore the sort ID. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	212 if (!mail_index_ext_get_reset_id(t->trans_view, map,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	213 ctx->ext_id, &reset_id))
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	214 reset_id = 0;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	215 if (reset_id != ctx->highest_reset_id) {
7567 9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	216 if (reset_id < ctx->highest_reset_id) {
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	217 i_assert(expunged);
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	218 node->sort_id = 0;
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	219 } else if (ctx->have_all_wanted) {
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	220 /* a bit late to start changing the reset_id.
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	221 the node lists aren't ordered by sequence
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	222 anymore. */
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	223 node->sort_id = 0;
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	224 ctx->no_writing = TRUE;
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	225 } else {
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	226 ctx->highest_reset_id = reset_id;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	227 index_sort_reget_sort_ids(ctx);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	228 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	229 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	230 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	231
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	232 if (node->sort_id == 0)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	233 array_append(&ctx->zero_nodes, node, 1);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	234 else
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	235 array_append(&ctx->nonzero_nodes, node, 1);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	236 if (ctx->last_seq < node->seq)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	237 ctx->last_seq = node->seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	238 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	239
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	240 void index_sort_list_add_string(struct mail_search_sort_program *program,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	241 struct mail *mail)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	242 {
8480 f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	243 struct sort_string_context *ctx = program->context;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	244 struct mail_sort_node node;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	245
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	246 memset(&node, 0, sizeof(node));
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	247 node.seq = mail->seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	248 node.wanted = TRUE;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	249
8480 f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	250 if (mail->seq < ctx->prev_seq)
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	251 ctx->seqs_nonsorted = TRUE;
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	252 ctx->prev_seq = mail->seq;
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	253
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	254 index_sort_node_add(ctx, &node);
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	255 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	256
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	257 static int sort_node_zero_string_cmp(const void p1, const void p2)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	258 {
7613 63602977ca9b sort index: Messages without sort_id weren't sorted correctly on secondary Timo Sirainen <tss@iki.fi> parents: 7612 diff changeset	259 struct sort_string_context *ctx = static_zero_cmp_context;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	260 const struct mail_sort_node n1 = p1, n2 = p2;
7613 63602977ca9b sort index: Messages without sort_id weren't sorted correctly on secondary Timo Sirainen <tss@iki.fi> parents: 7612 diff changeset	261 int ret;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	262
7613 63602977ca9b sort index: Messages without sort_id weren't sorted correctly on secondary Timo Sirainen <tss@iki.fi> parents: 7612 diff changeset	263 ret = strcmp(ctx->sort_strings[n1->seq], ctx->sort_strings[n2->seq]);
63602977ca9b sort index: Messages without sort_id weren't sorted correctly on secondary Timo Sirainen <tss@iki.fi> parents: 7612 diff changeset	264 if (ret != 0)
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	265 return !ctx->reverse ? ret : -ret;
7613 63602977ca9b sort index: Messages without sort_id weren't sorted correctly on secondary Timo Sirainen <tss@iki.fi> parents: 7612 diff changeset	266
63602977ca9b sort index: Messages without sort_id weren't sorted correctly on secondary Timo Sirainen <tss@iki.fi> parents: 7612 diff changeset	267 return index_sort_node_cmp_type(ctx->program->temp_mail,
63602977ca9b sort index: Messages without sort_id weren't sorted correctly on secondary Timo Sirainen <tss@iki.fi> parents: 7612 diff changeset	268 ctx->program->sort_program + 1,
63602977ca9b sort index: Messages without sort_id weren't sorted correctly on secondary Timo Sirainen <tss@iki.fi> parents: 7612 diff changeset	269 n1->seq, n2->seq);
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	270 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	271
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	272 static void index_sort_zeroes(struct sort_string_context *ctx)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	273 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	274 struct mail *mail = ctx->program->temp_mail;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	275 enum mail_sort_type sort_type = ctx->program->sort_program[0];
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	276 string_t *str;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	277 pool_t pool;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	278 struct mail_sort_node *nodes;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	279 unsigned int i, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	280
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	281 /* first get all the messages' sort strings. although this takes more
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	282 memory, it makes error handling easier and probably also helps
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	283 CPU caching. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	284 ctx->sort_strings = i_new(const char *, ctx->last_seq + 1);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	285 ctx->sort_string_pool = pool =
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	286 pool_alloconly_create("sort strings", 1024*64);
8781 513ba5a698a1 SORT: Don't waste data stack memory when sorting many messages. Timo Sirainen <tss@iki.fi> parents: 8590 diff changeset	287 str = str_new(default_pool, 512);
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	288 nodes = array_get_modifiable(&ctx->zero_nodes, &count);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	289 for (i = 0; i < count; i++) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	290 i_assert(nodes[i].seq <= ctx->last_seq);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	291
8781 513ba5a698a1 SORT: Don't waste data stack memory when sorting many messages. Timo Sirainen <tss@iki.fi> parents: 8590 diff changeset	292 T_BEGIN {
513ba5a698a1 SORT: Don't waste data stack memory when sorting many messages. Timo Sirainen <tss@iki.fi> parents: 8590 diff changeset	293 index_sort_header_get(mail, nodes[i].seq,
513ba5a698a1 SORT: Don't waste data stack memory when sorting many messages. Timo Sirainen <tss@iki.fi> parents: 8590 diff changeset	294 sort_type, str);
513ba5a698a1 SORT: Don't waste data stack memory when sorting many messages. Timo Sirainen <tss@iki.fi> parents: 8590 diff changeset	295 ctx->sort_strings[nodes[i].seq] =
513ba5a698a1 SORT: Don't waste data stack memory when sorting many messages. Timo Sirainen <tss@iki.fi> parents: 8590 diff changeset	296 str_len(str) == 0 ? "" :
513ba5a698a1 SORT: Don't waste data stack memory when sorting many messages. Timo Sirainen <tss@iki.fi> parents: 8590 diff changeset	297 p_strdup(pool, str_c(str));
513ba5a698a1 SORT: Don't waste data stack memory when sorting many messages. Timo Sirainen <tss@iki.fi> parents: 8590 diff changeset	298 } T_END;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	299 }
8781 513ba5a698a1 SORT: Don't waste data stack memory when sorting many messages. Timo Sirainen <tss@iki.fi> parents: 8590 diff changeset	300 str_free(&str);
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	301
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	302 /* we have all strings, sort nodes based on them */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	303 static_zero_cmp_context = ctx;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	304 qsort(nodes, count, sizeof(struct mail_sort_node),
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	305 sort_node_zero_string_cmp);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	306 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	307
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	308 static const char *
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	309 index_sort_get_expunged_string(struct sort_string_context *ctx, uint32_t idx,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	310 string_t *str)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	311 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	312 struct mail *mail = ctx->program->temp_mail;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	313 enum mail_sort_type sort_type = ctx->program->sort_program[0];
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	314 const struct mail_sort_node *nodes;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	315 const char *result = NULL;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	316 unsigned int i, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	317 uint32_t sort_id;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	318
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	319 /* Look forwards and backwards to see if there are
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	320 identical sort_ids. If we do find them, try to get
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	321 their sort string and use it to update the rest. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	322 nodes = array_get(&ctx->nonzero_nodes, &count);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	323 sort_id = nodes[idx].sort_id;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	324 /* If previous sort ID is identical and its sort string is set, we can
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	325 trust it. If it's expunged, we already verified that there are no
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	326 non-expunged messages. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	327 if (idx > 0 && nodes[idx-1].sort_id == sort_id &&
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	328 ctx->sort_strings[nodes[idx].seq] != NULL)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	329 return ctx->sort_strings[nodes[idx].seq];
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	330
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	331 /* Go forwards as long as there are identical sort IDs. If we find one
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	332 that's not expunged, update string table for all messages with
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	333 identical sort IDs. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	334 for (i = idx + 1; i < count; i++) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	335 if (nodes[i].sort_id != sort_id)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	336 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	337
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	338 if (ctx->sort_strings[nodes[i].seq] != NULL) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	339 /* usually we fill all identical sort_ids and this
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	340 shouldn't happen, but we can get here if we skipped
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	341 over messages when binary searching */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	342 result = ctx->sort_strings[nodes[i].seq];
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	343 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	344 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	345 if (index_sort_header_get(mail, nodes[i].seq,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	346 sort_type, str) >= 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	347 result = str_len(str) == 0 ? "" :
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	348 p_strdup(ctx->sort_string_pool, str_c(str));
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	349 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	350 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	351 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	352 if (result == NULL) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	353 /* unknown */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	354 return &expunged_msg;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	355 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	356
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	357 /* fill all identical sort_ids with the same value */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	358 for (i = idx; i > 0 && nodes[i-1].sort_id == sort_id; i--) ;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	359 for (i = idx; i < count && nodes[i].sort_id == sort_id; i++)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	360 ctx->sort_strings[nodes[i].seq] = result;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	361 return result;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	362 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	363
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	364 static const char *
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	365 index_sort_get_string(struct sort_string_context *ctx,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	366 uint32_t idx, uint32_t seq)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	367 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	368 struct mail *mail = ctx->program->temp_mail;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	369 int ret;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	370
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	371 if (ctx->sort_strings[seq] == NULL) T_BEGIN {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	372 string_t *str;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	373
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	374 str = t_str_new(256);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	375 ret = index_sort_header_get(mail, seq,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	376 ctx->program->sort_program[0], str);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	377 if (str_len(str) > 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	378 ctx->sort_strings[seq] =
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	379 p_strdup(ctx->sort_string_pool, str_c(str));
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	380 } else if (ret >= 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	381 ctx->sort_strings[seq] = "";
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	382 } else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	383 ctx->sort_strings[seq] =
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	384 index_sort_get_expunged_string(ctx, idx, str);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	385 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	386 } T_END;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	387
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	388 return ctx->sort_strings[seq];
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	389 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	390
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	391 static void
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	392 index_sort_bsearch(struct sort_string_context ctx, const char key,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	393 unsigned int start_idx, unsigned int *idx_r,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	394 const char **prev_str_r)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	395 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	396 const struct mail_sort_node *nodes;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	397 const char str, str2;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	398 unsigned int idx, left_idx, right_idx, prev;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	399 int ret;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	400
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	401 nodes = array_get_modifiable(&ctx->nonzero_nodes, &right_idx);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	402 idx = left_idx = start_idx;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	403 while (left_idx < right_idx) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	404 idx = (left_idx + right_idx) / 2;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	405 str = index_sort_get_string(ctx, idx, nodes[idx].seq);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	406 if (str != &expunged_msg)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	407 ret = strcmp(key, str);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	408 else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	409 /* put expunged messages first */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	410 ret = 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	411 for (prev = idx; prev > 0; ) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	412 prev--;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	413 str2 = index_sort_get_string(ctx, prev,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	414 nodes[prev].seq);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	415 if (str2 != &expunged_msg) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	416 ret = strcmp(key, str2);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	417 if (ret <= 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	418 idx = prev;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	419 str = str2;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	420 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	421 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	422 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	423 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	424 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	425 if (ret > 0)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	426 left_idx = idx+1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	427 else if (ret < 0)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	428 right_idx = idx;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	429 else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	430 *idx_r = idx + 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	431 *prev_str_r = str;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	432 return;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	433 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	434 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	435
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	436 if (left_idx > idx)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	437 idx++;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	438
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	439 *idx_r = idx;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	440 if (idx > start_idx) {
7566 8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	441 prev = idx;
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	442 do {
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	443 prev--;
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	444 str2 = index_sort_get_string(ctx, prev,
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	445 nodes[prev].seq);
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	446 } while (str2 == &expunged_msg && prev > 0 &&
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	447 nodes[prev-1].sort_id == nodes[prev].sort_id);
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	448 *prev_str_r = str2;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	449 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	450 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	451
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	452 static void index_sort_merge(struct sort_string_context *ctx)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	453 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	454 struct mail_sort_node znodes, nznodes;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	455 const char zstr, nzstr, *prev_str;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	456 unsigned int zpos, nzpos, nz_next_pos, zcount, nzcount;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	457 int ret;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	458
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	459 /* both zero_nodes and nonzero_nodes are sorted. we'll now just have
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	460 to merge them together. use sorted_nodes as the result array. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	461 i_array_init(&ctx->sorted_nodes, array_count(&ctx->nonzero_nodes) +
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	462 array_count(&ctx->zero_nodes));
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	463
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	464 znodes = array_get_modifiable(&ctx->zero_nodes, &zcount);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	465 nznodes = array_get_modifiable(&ctx->nonzero_nodes, &nzcount);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	466
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	467 prev_str = NULL;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	468 for (zpos = nzpos = 0; zpos < zcount && nzpos < nzcount; ) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	469 zstr = ctx->sort_strings[znodes[zpos].seq];
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	470 nzstr = index_sort_get_string(ctx, nzpos, nznodes[nzpos].seq);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	471
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	472 if (nzstr != &expunged_msg)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	473 ret = strcmp(zstr, nzstr);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	474 else if (prev_str != NULL && strcmp(zstr, prev_str) == 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	475 /* identical to previous message, must keep them
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	476 together */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	477 ret = -1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	478 } else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	479 /* we can't be yet sure about the order, but future
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	480 nznodes may reveal that the znode must be added
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	481 later. if future nznodes don't reveal that, we have
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	482 no idea about these nodes' order. so just always
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	483 put the expunged message first. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	484 ret = 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	485 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	486
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	487 if (ret <= 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	488 array_append(&ctx->sorted_nodes, &znodes[zpos], 1);
7566 8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	489 prev_str = zstr;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	490 zpos++;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	491 } else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	492 array_append(&ctx->sorted_nodes, &nznodes[nzpos], 1);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	493 prev_str = nzstr;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	494 nzpos++;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	495
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	496 /* avoid looking up all existing messages' strings by
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	497 binary searching the next zero-node position. don't
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	498 bother if it looks like more work than linear
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	499 scanning. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	500 if (zcount - zpos < (nzcount - nzpos)/2) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	501 index_sort_bsearch(ctx, zstr, nzpos,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	502 &nz_next_pos, &prev_str);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	503 array_append(&ctx->sorted_nodes,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	504 &nznodes[nzpos],
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	505 nz_next_pos - nzpos);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	506 nzpos = nz_next_pos;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	507 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	508 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	509 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	510 /* only one of zero_nodes and nonzero_nodes can be non-empty now */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	511 for (; zpos < zcount; zpos++)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	512 array_append(&ctx->sorted_nodes, &znodes[zpos], 1);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	513 for (; nzpos < nzcount; nzpos++)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	514 array_append(&ctx->sorted_nodes, &nznodes[nzpos], 1);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	515
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	516 /* future index_sort_get_string() calls use ctx->nonzero_nodes, but we
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	517 use only ctx->sorted_nodes. make them identical. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	518 array_free(&ctx->nonzero_nodes);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	519 ctx->nonzero_nodes = ctx->sorted_nodes;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	520 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	521
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	522 static int
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	523 index_sort_add_ids_range(struct sort_string_context *ctx,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	524 unsigned int left_idx, unsigned int right_idx)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	525 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	526
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	527 struct mail_sort_node *nodes;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	528 unsigned int i, count, rightmost_idx, skip;
8799 969d23a89379 Compiler warning fixes. Timo Sirainen <tss@iki.fi> parents: 8781 diff changeset	529 const char left_str = NULL, right_str = NULL, *str = NULL;
7609 c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	530 uint32_t left_sort_id, right_sort_id, diff;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	531 bool no_left_str = FALSE, no_right_str = FALSE;
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	532 int ret;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	533
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	534 nodes = array_get_modifiable(&ctx->sorted_nodes, &count);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	535 rightmost_idx = count - 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	536
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	537 /* get the sort IDs from left and right */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	538 left_sort_id = nodes[left_idx].sort_id;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	539 right_sort_id = nodes[right_idx].sort_id;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	540 /* check if all of them should have the same sort IDs. we don't want
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	541 to hit the renumbering code in that situation. */
7612 5824e6f1d279 sort index: Removed some optimization checks that wouldn't always be true, Timo Sirainen <tss@iki.fi> parents: 7609 diff changeset	542 if (left_sort_id == right_sort_id && left_sort_id != 0) {
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	543 /* they should all have the same sort ID */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	544 for (i = left_idx + 1; i < right_idx; i++) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	545 nodes[i].sort_id = left_sort_id;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	546 nodes[i].sort_id_changed = TRUE;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	547 }
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	548 return 0;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	549 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	550
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	551 if (left_sort_id == 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	552 i_assert(left_idx == 0);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	553 left_sort_id = 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	554 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	555 if (right_sort_id == 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	556 i_assert(right_idx == rightmost_idx);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	557 right_sort_id = (uint32_t)-1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	558 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	559 i_assert(left_sort_id <= right_sort_id);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	560
7609 c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	561 diff = right_sort_id - left_sort_id;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	562 while (diff / (right_idx-left_idx + 2) == 0) {
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	563 /* we most likely don't have enough space. we have to
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	564 renumber some of the existing sort IDs. do this by
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	565 widening the area we're giving sort IDs. */
8070 7e3590da43a9 sort indexes: One more assert-crashfix when renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 8018 diff changeset	566 while (left_idx > 0) {
7e3590da43a9 sort indexes: One more assert-crashfix when renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 8018 diff changeset	567 if (nodes[--left_idx].sort_id != left_sort_id) {
7e3590da43a9 sort indexes: One more assert-crashfix when renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 8018 diff changeset	568 left_sort_id = nodes[left_idx].sort_id;
7e3590da43a9 sort indexes: One more assert-crashfix when renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 8018 diff changeset	569 if (left_sort_id == 0) {
7e3590da43a9 sort indexes: One more assert-crashfix when renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 8018 diff changeset	570 i_assert(left_idx == 0);
7e3590da43a9 sort indexes: One more assert-crashfix when renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 8018 diff changeset	571 left_sort_id = 1;
7e3590da43a9 sort indexes: One more assert-crashfix when renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 8018 diff changeset	572 }
7e3590da43a9 sort indexes: One more assert-crashfix when renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 8018 diff changeset	573 break;
7568 66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	574 }
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	575 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	576
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	577 while (right_idx < rightmost_idx) {
7609 c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	578 right_idx++;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	579 if (nodes[right_idx].sort_id > right_sort_id)
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	580 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	581 }
7568 66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	582 right_sort_id = nodes[right_idx].sort_id;
66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	583 if (right_sort_id == 0) {
66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	584 i_assert(right_idx == rightmost_idx);
66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	585 right_sort_id = (uint32_t)-1;
66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	586 }
8018 2621f6f10c2e SORT: Fixed assert-crash. Timo Sirainen <tss@iki.fi> parents: 7956 diff changeset	587 i_assert(left_sort_id <= right_sort_id);
7609 c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	588
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	589 if (diff == right_sort_id - left_sort_id) {
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	590 /* we did nothing, but there's still not enough space.
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	591 have to renumber the leftmost/rightmost node(s) */
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	592 i_assert(left_idx == 0 && right_idx == rightmost_idx);
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	593 if (left_sort_id > 1) {
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	594 left_sort_id = 1;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	595 no_left_str = TRUE;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	596 } else {
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	597 i_assert(right_sort_id != (uint32_t)-1);
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	598 right_sort_id = (uint32_t)-1;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	599 no_right_str = TRUE;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	600 }
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	601 }
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	602 diff = right_sort_id - left_sort_id;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	603 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	604
7609 c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	605 if (nodes[left_idx].sort_id != 0 && !no_left_str) {
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	606 left_str = index_sort_get_string(ctx, left_idx,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	607 nodes[left_idx].seq);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	608 if (left_str == &expunged_msg) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	609 /* not equivalent with any message */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	610 left_str = NULL;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	611 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	612 left_idx++;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	613 }
7609 c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	614 if (nodes[right_idx].sort_id != 0 && !no_right_str) {
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	615 right_str = index_sort_get_string(ctx, right_idx,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	616 nodes[right_idx].seq);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	617 if (right_str == &expunged_msg) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	618 /* not equivalent with any message */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	619 right_str = NULL;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	620 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	621 right_idx--;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	622 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	623 i_assert(left_idx <= right_idx);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	624
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	625 /* give (new) sort IDs to all nodes in left_idx..right_idx range.
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	626 divide the available space so that each message gets an equal sized
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	627 share. some messages' sort strings may be equivalent, so give them
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	628 the same sort IDs. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	629 for (i = left_idx; i <= right_idx; i++) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	630 str = index_sort_get_string(ctx, i, nodes[i].seq);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	631 if (str == &expunged_msg) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	632 /* it doesn't really matter what we give to this
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	633 message, since it's only temporary and we don't
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	634 know its correct position anyway. so let's assume
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	635 it's equivalent to previous message. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	636 nodes[i].sort_id = left_sort_id;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	637 continue;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	638 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	639
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	640 ret = left_str == NULL ? 1 : strcmp(str, left_str);
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	641 if (ret <= 0) {
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	642 if (ret < 0) {
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	643 /* broken sort_ids */
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	644 return -1;
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	645 }
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	646 nodes[i].sort_id = left_sort_id;
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	647 } else if (right_str != NULL && strcmp(str, right_str) == 0) {
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	648 /* the rest of the sort IDs should be the same */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	649 nodes[i].sort_id = right_sort_id;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	650 left_sort_id = right_sort_id;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	651 } else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	652 /* divide the available space equally. leave the same
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	653 sized space also between the first and the last
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	654 messages */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	655 skip = (right_sort_id - left_sort_id) /
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	656 (right_idx - i + 2);
8193 b3fb8215a339 Sort indexes: Don't assert-crash with broken sort IDs. Timo Sirainen <tss@iki.fi> parents: 8070 diff changeset	657 if (skip == 0) {
b3fb8215a339 Sort indexes: Don't assert-crash with broken sort IDs. Timo Sirainen <tss@iki.fi> parents: 8070 diff changeset	658 /* broken sort IDs (we previously assigned
b3fb8215a339 Sort indexes: Don't assert-crash with broken sort IDs. Timo Sirainen <tss@iki.fi> parents: 8070 diff changeset	659 left_sort_id=right_sort_id) */
b3fb8215a339 Sort indexes: Don't assert-crash with broken sort IDs. Timo Sirainen <tss@iki.fi> parents: 8070 diff changeset	660 return -1;
b3fb8215a339 Sort indexes: Don't assert-crash with broken sort IDs. Timo Sirainen <tss@iki.fi> parents: 8070 diff changeset	661 }
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	662 left_sort_id += skip;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	663 i_assert(left_sort_id < right_sort_id);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	664
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	665 nodes[i].sort_id = left_sort_id;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	666 left_str = str;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	667 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	668 nodes[i].sort_id_changed = TRUE;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	669 }
7954 d75fdd0fb8b2 Sort index sometimes failed wrongly with "Sort IDs broken" errors. Timo Sirainen <tss@iki.fi> parents: 7859 diff changeset	670 return right_str == NULL \|\| strcmp(str, right_str) < 0 \|\|
d75fdd0fb8b2 Sort index sometimes failed wrongly with "Sort IDs broken" errors. Timo Sirainen <tss@iki.fi> parents: 7859 diff changeset	671 (strcmp(str, right_str) == 0 &&
d75fdd0fb8b2 Sort index sometimes failed wrongly with "Sort IDs broken" errors. Timo Sirainen <tss@iki.fi> parents: 7859 diff changeset	672 nodes[i-1].sort_id == right_sort_id) ? 0 : -1;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	673 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	674
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	675 static int
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	676 index_sort_add_sort_ids(struct sort_string_context *ctx)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	677 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	678 const struct mail_sort_node *nodes;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	679 unsigned int i, left_idx, right_idx, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	680
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	681 nodes = array_get(&ctx->sorted_nodes, &count);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	682 for (i = 0; i < count; i++) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	683 if (nodes[i].sort_id != 0)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	684 continue;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	685
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	686 /* get the range for all sort_id=0 nodes. include the nodes
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	687 left and right of the range as well */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	688 for (right_idx = i + 1; right_idx < count; right_idx++) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	689 if (nodes[right_idx].sort_id != 0)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	690 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	691 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	692 if (right_idx == count)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	693 right_idx--;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	694 left_idx = i == 0 ? 0 : i - 1;
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	695 if (index_sort_add_ids_range(ctx, left_idx, right_idx) < 0)
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	696 return -1;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	697 }
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	698 return 0;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	699 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	700
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	701 static void index_sort_write_changed_sort_ids(struct sort_string_context *ctx)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	702 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	703 struct index_transaction_context *t =
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	704 (struct index_transaction_context *)ctx->program->t;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	705 uint32_t ext_id = ctx->ext_id;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	706 const struct mail_sort_node *nodes;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	707 unsigned int i, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	708
7567 9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	709 if (ctx->no_writing) {
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	710 /* our reset_id is already stale - don't even bother
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	711 trying to write */
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	712 return;
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	713 }
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	714
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	715 mail_index_ext_reset_inc(t->trans, ext_id, ctx->highest_reset_id, FALSE);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	716
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	717 /* add the missing sort IDs to index */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	718 nodes = array_get_modifiable(&ctx->sorted_nodes, &count);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	719 for (i = 0; i < count; i++) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	720 i_assert(nodes[i].sort_id != 0);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	721 if (!nodes[i].sort_id_changed \|\| nodes[i].no_update)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	722 continue;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	723
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	724 mail_index_update_ext(t->trans, nodes[i].seq, ext_id,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	725 &nodes[i].sort_id, NULL);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	726 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	727 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	728
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	729 static int sort_node_cmp(const void p1, const void p2)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	730 {
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	731 struct sort_string_context *ctx = static_zero_cmp_context;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	732 const struct mail_sort_node n1 = p1, n2 = p2;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	733
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	734 if (n1->sort_id < n2->sort_id)
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	735 return !ctx->reverse ? -1 : 1;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	736 if (n1->sort_id > n2->sort_id)
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	737 return !ctx->reverse ? 1 : -1;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	738
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	739 return index_sort_node_cmp_type(ctx->program->temp_mail,
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	740 ctx->program->sort_program + 1,
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	741 n1->seq, n2->seq);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	742 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	743
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	744 static void index_sort_add_missing(struct sort_string_context *ctx)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	745 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	746 struct mail_sort_node node;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	747 const uint32_t *seqs;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	748 unsigned int i, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	749 uint32_t seq, next_seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	750
7567 9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	751 ctx->have_all_wanted = TRUE;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	752
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	753 seqs = array_get(&ctx->program->seqs, &count);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	754 for (i = 0, next_seq = 1; i < count; i++) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	755 if (seqs[i] == next_seq)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	756 next_seq++;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	757 else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	758 i_assert(next_seq < seqs[i]);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	759 for (seq = next_seq; seq < seqs[i]; seq++) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	760 memset(&node, 0, sizeof(node));
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	761 node.seq = seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	762 index_sort_node_add(ctx, &node);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	763 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	764 next_seq = seqs[i] + 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	765 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	766 }
7569 ea913434d522 Sort index optimization: Don't write changes to sort IDs if we're doing it Timo Sirainen <tss@iki.fi> parents: 7568 diff changeset	767
ea913434d522 Sort index optimization: Don't write changes to sort IDs if we're doing it Timo Sirainen <tss@iki.fi> parents: 7568 diff changeset	768 if (ctx->lowest_nonexpunged_zero == 0) {
ea913434d522 Sort index optimization: Don't write changes to sort IDs if we're doing it Timo Sirainen <tss@iki.fi> parents: 7568 diff changeset	769 /* we're handling only expunged zeros. if it causes us to
ea913434d522 Sort index optimization: Don't write changes to sort IDs if we're doing it Timo Sirainen <tss@iki.fi> parents: 7568 diff changeset	770 renumber some existing sort IDs, don't save them. */
ea913434d522 Sort index optimization: Don't write changes to sort IDs if we're doing it Timo Sirainen <tss@iki.fi> parents: 7568 diff changeset	771 ctx->no_writing = TRUE;
ea913434d522 Sort index optimization: Don't write changes to sort IDs if we're doing it Timo Sirainen <tss@iki.fi> parents: 7568 diff changeset	772 }
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	773 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	774
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	775 static void index_sort_list_reset_broken(struct sort_string_context *ctx)
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	776 {
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	777 struct mailbox *box = ctx->program->t->box;
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	778 struct mail_sort_node *nodes;
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	779 unsigned int i, count;
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	780
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	781 mail_storage_set_critical(box->storage,
9293 c50f133f0acc sort: Don't assert-crash if sort indexes are broken. Timo Sirainen <tss@iki.fi> parents: 8799 diff changeset	782 "%s: Broken %s indexes, resetting",
c50f133f0acc sort: Don't assert-crash if sort indexes are broken. Timo Sirainen <tss@iki.fi> parents: 8799 diff changeset	783 box->name, ctx->primary_sort_name);
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	784
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	785 array_clear(&ctx->zero_nodes);
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	786 array_append_array(&ctx->zero_nodes,
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	787 &ctx->nonzero_nodes);
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	788 array_clear(&ctx->nonzero_nodes);
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	789
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	790 nodes = array_get_modifiable(&ctx->zero_nodes, &count);
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	791 for (i = 0; i < count; i++)
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	792 nodes[i].sort_id = 0;
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	793 }
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	794
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	795 void index_sort_list_finish_string(struct mail_search_sort_program *program)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	796 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	797 struct sort_string_context *ctx = program->context;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	798 struct mail_sort_node *nodes;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	799 unsigned int i, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	800 uint32_t seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	801
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	802 nodes = array_get_modifiable(&ctx->nonzero_nodes, &count);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	803
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	804 static_zero_cmp_context = ctx;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	805 if (array_count(&ctx->zero_nodes) == 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	806 /* fast path: we have all sort IDs */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	807 qsort(nodes, count, sizeof(struct mail_sort_node),
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	808 sort_node_cmp);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	809
7956 439636cce455 Memory leak fixes. Timo Sirainen <tss@iki.fi> parents: 7955 diff changeset	810 if (!array_is_created(&program->seqs))
439636cce455 Memory leak fixes. Timo Sirainen <tss@iki.fi> parents: 7955 diff changeset	811 i_array_init(&program->seqs, count);
439636cce455 Memory leak fixes. Timo Sirainen <tss@iki.fi> parents: 7955 diff changeset	812 else
439636cce455 Memory leak fixes. Timo Sirainen <tss@iki.fi> parents: 7955 diff changeset	813 array_clear(&program->seqs);
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	814 for (i = 0; i < count; i++) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	815 seq = nodes[i].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	816 array_append(&program->seqs, &seq, 1);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	817 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	818 array_free(&ctx->nonzero_nodes);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	819 } else {
8480 f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	820 if (ctx->seqs_nonsorted) {
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	821 /* the nodes need to be sorted by sequence initially */
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	822 index_sort_nodes_by_seq(ctx);
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	823 }
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	824
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	825 /* we have to add some sort IDs. we'll do this for all
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	826 messages, so first remember what messages we wanted
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	827 to know about. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	828 index_sort_generate_seqs(ctx);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	829 /* add messages not in seqs list */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	830 index_sort_add_missing(ctx);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	831 /* sort all messages with sort IDs */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	832 nodes = array_get_modifiable(&ctx->nonzero_nodes, &count);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	833 qsort(nodes, count, sizeof(struct mail_sort_node),
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	834 sort_node_cmp);
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	835 for (;;) {
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	836 /* sort all messages without sort IDs */
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	837 index_sort_zeroes(ctx);
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	838
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	839 if (ctx->reverse) {
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	840 /* sort lists are descending currently, but
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	841 merging and sort ID assigning works only
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	842 with ascending lists. reverse the lists
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	843 temporarily. we can't do this while earlier
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	844 because secondary sort conditions must not
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	845 be reversed in results (but while assigning
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	846 sort IDs it doesn't matter). */
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	847 array_reverse(&ctx->nonzero_nodes);
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	848 array_reverse(&ctx->zero_nodes);
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	849 }
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	850
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	851 /* merge zero and non-zero arrays into sorted_nodes */
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	852 index_sort_merge(ctx);
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	853 /* give sort IDs to messages missing them */
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	854 if (index_sort_add_sort_ids(ctx) == 0)
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	855 break;
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	856
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	857 /* broken, try again with sort IDs reset */
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	858 index_sort_list_reset_broken(ctx);
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	859 }
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	860 index_sort_write_changed_sort_ids(ctx);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	861
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	862 if (ctx->reverse) {
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	863 /* restore the correct sort order */
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	864 array_reverse(&ctx->sorted_nodes);
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	865 }
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	866
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	867 nodes = array_get_modifiable(&ctx->sorted_nodes, &count);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	868 array_clear(&program->seqs);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	869 for (i = 0; i < count; i++) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	870 if (nodes[i].wanted) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	871 seq = nodes[i].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	872 array_append(&program->seqs, &seq, 1);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	873 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	874 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	875 pool_unref(&ctx->sort_string_pool);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	876 i_free(ctx->sort_strings);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	877 array_free(&ctx->sorted_nodes);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	878 /* NOTE: we already freed nonzero_nodes and made it point to
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	879 sorted_nodes. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	880 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	881
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	882 array_free(&ctx->zero_nodes);
7956 439636cce455 Memory leak fixes. Timo Sirainen <tss@iki.fi> parents: 7955 diff changeset	883 i_free(ctx);
439636cce455 Memory leak fixes. Timo Sirainen <tss@iki.fi> parents: 7955 diff changeset	884 program->context = NULL;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	885 }

Mercurial > dovecot > original-hg > dovecot-1.2

annotate src/lib-storage/index/index-sort-string.c @ 9444:a5d8d201bd39 HEAD