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

annotate src/lib-storage/index/index-sort-string.c @ 9266:cd29b745c8dd HEAD

configure: clock_gettime()'s -lrt adding dropped everything else from $LIBS.

author	Timo Sirainen <tss@iki.fi>
date	Mon, 27 Jul 2009 06:32:42 -0400
parents	969d23a89379
children	c50f133f0acc

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;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	30
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	31 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	32 const char **sort_strings;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	33 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	34 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	35
8480 f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	36 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	37 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	38
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	39 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	40 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	41 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	42 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	43 unsigned int seqs_nonsorted:1;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	44 };
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	45
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	46 static char expunged_msg;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	47 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	48
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	49 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	50 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	51
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	52 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	53 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	54 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	55 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	56 const char *name;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	57
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	58 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	59 case MAIL_SORT_CC:
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	60 name = "sort-c";
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	61 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	62 case MAIL_SORT_FROM:
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	63 name = "sort-f";
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_SUBJECT:
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	66 name = "sort-s";
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_TO:
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	69 name = "sort-t";
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 default:
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	72 i_unreached();
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	73 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	74
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	75 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	76 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	77 ctx->program = program;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	78 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	79 sizeof(uint32_t),
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	80 sizeof(uint32_t));
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	81 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	82 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	83 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	84
8480 f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	85 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	86 {
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	87 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	88
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	89 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	90 return -1;
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	91 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	92 return 1;
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	93 return 0;
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	94 }
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	95
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	96 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	97 {
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	98 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	99 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	100
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	101 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	102 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	103
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	104 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	105 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	106 }
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	107
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	108 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	109 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	110 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	111 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	112 uint32_t seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	113
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	114 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	115 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	116
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	117 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	118 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	119 else
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	120 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	121
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	122 for (i = j = 0;;) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	123 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	124 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	125 seq = nodes[i++].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	126 else
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	127 seq = nodes2[j++].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	128 } else if (i < count) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	129 seq = nodes[i++].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	130 } else if (j < count2) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	131 seq = nodes2[j++].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	132 } else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	133 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	134 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	135 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	136 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	137 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	138
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	139 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	140 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	141 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	142 const uint32_t *seqs;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	143 unsigned int i, count;
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 i_assert(!ctx->regetting);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	146 ctx->regetting = TRUE;
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 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	149 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	150 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	151
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	152 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	153 node.wanted = TRUE;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	154 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	155 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	156 node.seq = seqs[i];
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	157 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	158 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	159 ctx->regetting = FALSE;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	160 }
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 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	163 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	164 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	165 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	166 (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	167 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	168 const void *data;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	169 uint32_t reset_id;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	170 bool expunged;
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 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	173 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	174 if (expunged) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	175 /* 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	176 node->no_update = TRUE;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	177 /* 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	178 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	179 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	180 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	181 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	182 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	183 node->sort_id = 0;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	184 } else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	185 node->sort_id = data == NULL ? 0 : (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	186 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	187 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	188 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	189 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	190 } else {
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	191 i_assert(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	192 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	193 }
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	194 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	195
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	196 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	197 /* 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	198 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	199 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	200 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	201 reset_id = 0;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	202 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	203 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	204 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	205 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	206 } 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	207 /* 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	208 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	209 anymore. */
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	210 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	211 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	212 } else {
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	213 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	214 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	215 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	216 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	217 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	218
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	219 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	220 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	221 else
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	222 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	223 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	224 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	225 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	226
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	227 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	228 struct mail *mail)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	229 {
8480 f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	230 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	231 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	232
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	233 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	234 node.seq = mail->seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	235 node.wanted = TRUE;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	236
8480 f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	237 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	238 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	239 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	240
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	241 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	242 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	243
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	244 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	245 {
7613 63602977ca9b sort index: Messages without sort_id weren't sorted correctly on secondary Timo Sirainen <tss@iki.fi> parents: 7612 diff changeset	246 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	247 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	248 int ret;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	249
7613 63602977ca9b sort index: Messages without sort_id weren't sorted correctly on secondary Timo Sirainen <tss@iki.fi> parents: 7612 diff changeset	250 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	251 if (ret != 0)
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	252 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	253
63602977ca9b sort index: Messages without sort_id weren't sorted correctly on secondary Timo Sirainen <tss@iki.fi> parents: 7612 diff changeset	254 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	255 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	256 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	257 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	258
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	259 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	260 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	261 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	262 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	263 string_t *str;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	264 pool_t pool;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	265 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	266 unsigned int i, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	267
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	268 /* 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	269 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	270 CPU caching. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	271 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	272 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	273 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	274 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	275 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	276 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	277 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	278
8781 513ba5a698a1 SORT: Don't waste data stack memory when sorting many messages. Timo Sirainen <tss@iki.fi> parents: 8590 diff changeset	279 T_BEGIN {
513ba5a698a1 SORT: Don't waste data stack memory when sorting many messages. Timo Sirainen <tss@iki.fi> parents: 8590 diff changeset	280 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	281 sort_type, str);
513ba5a698a1 SORT: Don't waste data stack memory when sorting many messages. Timo Sirainen <tss@iki.fi> parents: 8590 diff changeset	282 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	283 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	284 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	285 } T_END;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	286 }
8781 513ba5a698a1 SORT: Don't waste data stack memory when sorting many messages. Timo Sirainen <tss@iki.fi> parents: 8590 diff changeset	287 str_free(&str);
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	288
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	289 /* 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	290 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	291 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	292 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	293 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	294
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	295 static const char *
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	296 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	297 string_t *str)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	298 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	299 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	300 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	301 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	302 const char *result = NULL;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	303 unsigned int i, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	304 uint32_t sort_id;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	305
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	306 /* 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	307 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	308 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	309 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	310 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	311 /* 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	312 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	313 non-expunged messages. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	314 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	315 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	316 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	317
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	318 /* 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	319 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	320 identical sort IDs. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	321 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	322 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	323 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	324
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	325 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	326 /* 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	327 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	328 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	329 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	330 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	331 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	332 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	333 sort_type, str) >= 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	334 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	335 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	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 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	339 if (result == NULL) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	340 /* unknown */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	341 return &expunged_msg;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	342 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	343
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	344 /* 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	345 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	346 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	347 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	348 return result;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	349 }
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 static const char *
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	352 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	353 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	354 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	355 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	356 int ret;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	357
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	358 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	359 string_t *str;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	360
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	361 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	362 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	363 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	364 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	365 ctx->sort_strings[seq] =
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	366 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	367 } else if (ret >= 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	368 ctx->sort_strings[seq] = "";
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	369 } else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	370 ctx->sort_strings[seq] =
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	371 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	372 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	373 } T_END;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	374
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	375 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	376 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	377
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	378 static void
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	379 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	380 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	381 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	382 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	383 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	384 const char str, str2;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	385 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	386 int ret;
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 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	389 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	390 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	391 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	392 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	393 if (str != &expunged_msg)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	394 ret = strcmp(key, str);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	395 else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	396 /* put expunged messages first */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	397 ret = 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	398 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	399 prev--;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	400 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	401 nodes[prev].seq);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	402 if (str2 != &expunged_msg) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	403 ret = strcmp(key, str2);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	404 if (ret <= 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	405 idx = prev;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	406 str = str2;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	407 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	408 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	409 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	410 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	411 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	412 if (ret > 0)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	413 left_idx = idx+1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	414 else if (ret < 0)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	415 right_idx = idx;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	416 else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	417 *idx_r = idx + 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	418 *prev_str_r = str;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	419 return;
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 }
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 if (left_idx > idx)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	424 idx++;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	425
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	426 *idx_r = idx;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	427 if (idx > start_idx) {
7566 8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	428 prev = idx;
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	429 do {
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	430 prev--;
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	431 str2 = index_sort_get_string(ctx, prev,
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	432 nodes[prev].seq);
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	433 } while (str2 == &expunged_msg && prev > 0 &&
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	434 nodes[prev-1].sort_id == nodes[prev].sort_id);
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	435 *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	436 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	437 }
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 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	440 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	441 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	442 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	443 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	444 int ret;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	445
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	446 /* 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	447 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	448 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	449 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	450
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	451 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	452 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	453
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	454 prev_str = NULL;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	455 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	456 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	457 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	458
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	459 if (nzstr != &expunged_msg)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	460 ret = strcmp(zstr, nzstr);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	461 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	462 /* 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	463 together */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	464 ret = -1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	465 } else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	466 /* 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	467 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	468 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	469 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	470 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	471 ret = 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	472 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	473
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	474 if (ret <= 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	475 array_append(&ctx->sorted_nodes, &znodes[zpos], 1);
7566 8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	476 prev_str = zstr;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	477 zpos++;
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 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	480 prev_str = nzstr;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	481 nzpos++;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	482
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	483 /* 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	484 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	485 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	486 scanning. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	487 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	488 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	489 &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	490 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	491 &nznodes[nzpos],
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	492 nz_next_pos - nzpos);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	493 nzpos = nz_next_pos;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	494 }
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 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	497 /* 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	498 for (; zpos < zcount; zpos++)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	499 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	500 for (; nzpos < nzcount; nzpos++)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	501 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	502
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	503 /* 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	504 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	505 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	506 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	507 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	508
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	509 static int
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	510 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	511 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	512 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	513
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	514 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	515 unsigned int i, count, rightmost_idx, skip;
8799 969d23a89379 Compiler warning fixes. Timo Sirainen <tss@iki.fi> parents: 8781 diff changeset	516 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	517 uint32_t left_sort_id, right_sort_id, diff;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	518 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	519 int ret;
7564 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 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	522 rightmost_idx = count - 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	523
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	524 /* 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	525 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	526 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	527 /* 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	528 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	529 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	530 /* 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	531 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	532 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	533 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	534 }
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	535 return 0;
7564 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
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	538 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	539 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	540 left_sort_id = 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	541 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	542 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	543 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	544 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	545 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	546 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	547
7609 c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	548 diff = right_sort_id - left_sort_id;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	549 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	550 /* 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	551 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	552 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	553 while (left_idx > 0) {
7e3590da43a9 sort indexes: One more assert-crashfix when renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 8018 diff changeset	554 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	555 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	556 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	557 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	558 left_sort_id = 1;
7e3590da43a9 sort indexes: One more assert-crashfix when renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 8018 diff changeset	559 }
7e3590da43a9 sort indexes: One more assert-crashfix when renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 8018 diff changeset	560 break;
7568 66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	561 }
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	562 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	563
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	564 while (right_idx < rightmost_idx) {
7609 c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	565 right_idx++;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	566 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	567 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	568 }
7568 66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	569 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	570 if (right_sort_id == 0) {
66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	571 i_assert(right_idx == rightmost_idx);
66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	572 right_sort_id = (uint32_t)-1;
66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	573 }
8018 2621f6f10c2e SORT: Fixed assert-crash. Timo Sirainen <tss@iki.fi> parents: 7956 diff changeset	574 i_assert(left_sort_id <= right_sort_id);
7609 c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	575
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	576 if (diff == right_sort_id - left_sort_id) {
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	577 /* 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	578 have to renumber the leftmost/rightmost node(s) */
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	579 i_assert(left_idx == 0 && right_idx == rightmost_idx);
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	580 if (left_sort_id > 1) {
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	581 left_sort_id = 1;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	582 no_left_str = TRUE;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	583 } else {
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	584 i_assert(right_sort_id != (uint32_t)-1);
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	585 right_sort_id = (uint32_t)-1;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	586 no_right_str = TRUE;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	587 }
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 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	590 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	591
7609 c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	592 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	593 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	594 nodes[left_idx].seq);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	595 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	596 /* 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	597 left_str = NULL;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	598 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	599 left_idx++;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	600 }
7609 c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	601 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	602 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	603 nodes[right_idx].seq);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	604 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	605 /* 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	606 right_str = NULL;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	607 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	608 right_idx--;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	609 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	610 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	611
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	612 /* 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	613 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	614 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	615 the same sort IDs. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	616 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	617 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	618 if (str == &expunged_msg) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	619 /* 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	620 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	621 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	622 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	623 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	624 continue;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	625 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	626
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	627 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	628 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	629 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	630 /* 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	631 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	632 }
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	633 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	634 } 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	635 /* 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	636 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	637 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	638 } else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	639 /* 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	640 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	641 messages */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	642 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	643 (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	644 if (skip == 0) {
b3fb8215a339 Sort indexes: Don't assert-crash with broken sort IDs. Timo Sirainen <tss@iki.fi> parents: 8070 diff changeset	645 /* 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	646 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	647 return -1;
b3fb8215a339 Sort indexes: Don't assert-crash with broken sort IDs. Timo Sirainen <tss@iki.fi> parents: 8070 diff changeset	648 }
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	649 left_sort_id += skip;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	650 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	651
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	652 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	653 left_str = str;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	654 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	655 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	656 }
7954 d75fdd0fb8b2 Sort index sometimes failed wrongly with "Sort IDs broken" errors. Timo Sirainen <tss@iki.fi> parents: 7859 diff changeset	657 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	658 (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	659 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	660 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	661
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	662 static int
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	663 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	664 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	665 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	666 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	667
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	668 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	669 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	670 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	671 continue;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	672
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	673 /* 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	674 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	675 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	676 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	677 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	678 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	679 if (right_idx == count)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	680 right_idx--;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	681 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	682 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	683 return -1;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	684 }
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	685 return 0;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	686 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	687
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	688 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	689 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	690 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	691 (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	692 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	693 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	694 unsigned int i, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	695
7567 9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	696 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	697 /* 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	698 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	699 return;
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	700 }
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	701
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	702 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	703
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	704 /* 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	705 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	706 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	707 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	708 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	709 continue;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	710
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	711 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	712 &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	713 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	714 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	715
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	716 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	717 {
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	718 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	719 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	720
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	721 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	722 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	723 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	724 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	725
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	726 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	727 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	728 n1->seq, n2->seq);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	729 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	730
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	731 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	732 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	733 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	734 const uint32_t *seqs;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	735 unsigned int i, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	736 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	737
7567 9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	738 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	739
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	740 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	741 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	742 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	743 next_seq++;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	744 else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	745 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	746 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	747 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	748 node.seq = seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	749 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	750 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	751 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	752 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	753 }
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	754
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	755 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	756 /* 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	757 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	758 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	759 }
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	760 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	761
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	762 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	763 {
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	764 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	765 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	766 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	767
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	768 mail_storage_set_critical(box->storage,
7955 83019368c9dc s/reseting/resetting/ Timo Sirainen <tss@iki.fi> parents: 7954 diff changeset	769 "Sort IDs %u broken in mailbox %s, resetting",
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	770 ctx->ext_id, box->name);
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	771
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	772 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	773 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	774 &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	775 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	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 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	778 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	779 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	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
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	782 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	783 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	784 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	785 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	786 unsigned int i, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	787 uint32_t seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	788
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	789 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	790
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	791 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	792 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	793 /* 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	794 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	795 sort_node_cmp);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	796
7956 439636cce455 Memory leak fixes. Timo Sirainen <tss@iki.fi> parents: 7955 diff changeset	797 if (!array_is_created(&program->seqs))
439636cce455 Memory leak fixes. Timo Sirainen <tss@iki.fi> parents: 7955 diff changeset	798 i_array_init(&program->seqs, count);
439636cce455 Memory leak fixes. Timo Sirainen <tss@iki.fi> parents: 7955 diff changeset	799 else
439636cce455 Memory leak fixes. Timo Sirainen <tss@iki.fi> parents: 7955 diff changeset	800 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	801 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	802 seq = nodes[i].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	803 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	804 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	805 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	806 } else {
8480 f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	807 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	808 /* 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	809 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	810 }
f0c9677bf489 Sorting: Don't break if search code adds sequences in random order. Timo Sirainen <tss@iki.fi> parents: 8193 diff changeset	811
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	812 /* 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	813 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	814 to know about. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	815 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	816 /* 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	817 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	818 /* 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	819 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	820 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	821 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	822 for (;;) {
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	823 /* 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	824 index_sort_zeroes(ctx);
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	825
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	826 if (ctx->reverse) {
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	827 /* 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	828 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	829 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	830 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	831 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	832 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	833 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	834 array_reverse(&ctx->nonzero_nodes);
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	835 array_reverse(&ctx->zero_nodes);
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	836 }
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	837
7614 dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	838 /* 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	839 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	840 /* 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	841 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	842 break;
dd899a1841d9 sort index: Try to catch broken sort_ids and recreate them correctly instead Timo Sirainen <tss@iki.fi> parents: 7613 diff changeset	843
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	844 /* 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	845 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	846 }
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	847 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	848
7859 f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	849 if (ctx->reverse) {
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	850 /* restore the correct sort order */
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	851 array_reverse(&ctx->sorted_nodes);
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	852 }
f431c67621ed Reversing the primary sort criterion reversed also reversed secondary Timo Sirainen <tss@iki.fi> parents: 7614 diff changeset	853
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	854 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	855 array_clear(&program->seqs);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	856 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	857 if (nodes[i].wanted) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	858 seq = nodes[i].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	859 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	860 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	861 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	862 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	863 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	864 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	865 /* 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	866 sorted_nodes. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	867 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	868
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	869 array_free(&ctx->zero_nodes);
7956 439636cce455 Memory leak fixes. Timo Sirainen <tss@iki.fi> parents: 7955 diff changeset	870 i_free(ctx);
439636cce455 Memory leak fixes. Timo Sirainen <tss@iki.fi> parents: 7955 diff changeset	871 program->context = NULL;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	872 }

Mercurial > dovecot > original-hg > dovecot-1.2

annotate src/lib-storage/index/index-sort-string.c @ 9266:cd29b745c8dd HEAD