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

annotate src/lib-storage/index/index-sort-string.c @ 7609:c008dde3c973 HEAD

sort index: Fixed infinite looping.

author	Timo Sirainen <tss@iki.fi>
date	Wed, 04 Jun 2008 20:23:05 +0300
parents	ea913434d522
children	5824e6f1d279

rev	line source
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	1 /* Copyright (c) 2006-2008 Dovecot authors, see the included COPYING file */
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
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	36 uint32_t ext_id, last_seq, highest_reset_id;
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;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	42 };
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	43
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	44 static char expunged_msg;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	45 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	46 static struct mail_search_sort_program *static_sort_node_cmp_context;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	47
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	48 static 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	49 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	50
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	51 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	52 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	53 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	54 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	55 const char *name;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	56
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	57 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	58 case MAIL_SORT_CC:
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	59 name = "sort-c";
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	60 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	61 case MAIL_SORT_FROM:
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	62 name = "sort-f";
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	63 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	64 case MAIL_SORT_SUBJECT:
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	65 name = "sort-s";
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	66 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	67 case MAIL_SORT_TO:
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	68 name = "sort-t";
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	69 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	70 default:
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	71 i_unreached();
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	72 }
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 program->context = ctx = i_new(struct sort_string_context, 1);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	75 ctx->program = program;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	76 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	77 sizeof(uint32_t),
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	78 sizeof(uint32_t));
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	79 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	80 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	81 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	82
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	83 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	84 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	85 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	86 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	87 uint32_t seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	88
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	89 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	90 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	91
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	92 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	93 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	94 else
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	95 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	96
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	97 for (i = j = 0;;) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	98 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	99 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	100 seq = nodes[i++].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	101 else
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	102 seq = nodes2[j++].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	103 } else if (i < count) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	104 seq = nodes[i++].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	105 } else if (j < count2) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	106 seq = nodes2[j++].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	107 } else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	108 break;
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 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	111 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	112 }
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 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	115 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	116 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	117 const uint32_t *seqs;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	118 unsigned int i, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	119
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	120 i_assert(!ctx->regetting);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	121 ctx->regetting = TRUE;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	122
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	123 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	124 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	125 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	126
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	127 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	128 node.wanted = TRUE;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	129 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	130 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	131 node.seq = seqs[i];
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	132 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	133 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	134 ctx->regetting = FALSE;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	135 }
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 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	138 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	139 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	140 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	141 (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	142 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	143 const void *data;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	144 uint32_t reset_id;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	145 bool expunged;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	146
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	147 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	148 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	149 if (expunged) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	150 /* 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	151 node->no_update = TRUE;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	152 /* 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	153 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	154 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	155 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	156 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	157 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	158 node->sort_id = 0;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	159 } else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	160 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	161 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	162 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	163 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	164 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	165 } 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	166 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	167 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	168 }
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	169 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	170
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	171 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	172 /* 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	173 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	174 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	175 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	176 reset_id = 0;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	177 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	178 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	179 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	180 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	181 } 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	182 /* 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	183 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	184 anymore. */
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	185 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	186 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	187 } else {
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	188 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	189 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	190 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	191 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	192 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	193
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	194 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	195 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	196 else
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	197 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	198 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	199 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	200 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	201
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	202 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	203 struct mail *mail)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	204 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	205 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	206
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	207 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	208 node.seq = mail->seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	209 node.wanted = TRUE;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	210
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	211 index_sort_node_add(program->context, &node);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	212 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	213
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	214 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	215 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	216 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	217
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	218 return strcmp(static_zero_cmp_context->sort_strings[n1->seq],
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	219 static_zero_cmp_context->sort_strings[n2->seq]);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	220 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	221
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	222 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	223 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	224 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	225 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	226 string_t *str;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	227 pool_t pool;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	228 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	229 unsigned int i, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	230
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	231 /* 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	232 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	233 CPU caching. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	234 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	235 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	236 pool_alloconly_create("sort strings", 1024*64);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	237 str = t_str_new(512);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	238 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	239 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	240 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	241
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	242 index_sort_header_get(mail, nodes[i].seq, sort_type, str);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	243 ctx->sort_strings[nodes[i].seq] = str_len(str) == 0 ? "" :
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	244 p_strdup(pool, str_c(str));
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	245 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	246
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	247 /* 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	248 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	249 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	250 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	251 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	252
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	253 static const char *
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	254 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	255 string_t *str)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	256 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	257 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	258 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	259 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	260 const char *result = NULL;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	261 unsigned int i, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	262 uint32_t sort_id;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	263
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	264 /* 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	265 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	266 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	267 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	268 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	269 /* 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	270 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	271 non-expunged messages. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	272 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	273 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	274 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	275
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	276 /* 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	277 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	278 identical sort IDs. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	279 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	280 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	281 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	282
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	283 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	284 /* 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	285 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	286 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	287 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	288 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	289 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	290 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	291 sort_type, str) >= 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	292 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	293 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	294 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	295 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	296 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	297 if (result == NULL) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	298 /* unknown */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	299 return &expunged_msg;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	300 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	301
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	302 /* 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	303 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	304 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	305 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	306 return result;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	307 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	308
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	309 static const char *
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	310 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	311 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	312 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	313 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	314 int ret;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	315
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	316 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	317 string_t *str;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	318
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	319 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	320 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	321 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	322 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	323 ctx->sort_strings[seq] =
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	324 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	325 } else if (ret >= 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	326 ctx->sort_strings[seq] = "";
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	327 } else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	328 ctx->sort_strings[seq] =
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	329 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	330 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	331 } T_END;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	332
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	333 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	334 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	335
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	336 static void
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	337 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	338 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	339 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	340 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	341 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	342 const char str, str2;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	343 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	344 int ret;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	345
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	346 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	347 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	348 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	349 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	350 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	351 if (str != &expunged_msg)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	352 ret = strcmp(key, str);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	353 else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	354 /* put expunged messages first */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	355 ret = 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	356 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	357 prev--;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	358 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	359 nodes[prev].seq);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	360 if (str2 != &expunged_msg) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	361 ret = strcmp(key, str2);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	362 if (ret <= 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	363 idx = prev;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	364 str = str2;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	365 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	366 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	367 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	368 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	369 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	370 if (ret > 0)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	371 left_idx = idx+1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	372 else if (ret < 0)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	373 right_idx = idx;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	374 else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	375 *idx_r = idx + 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	376 *prev_str_r = str;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	377 return;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	378 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	379 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	380
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	381 if (left_idx > idx)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	382 idx++;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	383
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	384 *idx_r = idx;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	385 if (idx > start_idx) {
7566 8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	386 prev = idx;
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	387 do {
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	388 prev--;
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	389 str2 = index_sort_get_string(ctx, prev,
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	390 nodes[prev].seq);
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	391 } while (str2 == &expunged_msg && prev > 0 &&
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	392 nodes[prev-1].sort_id == nodes[prev].sort_id);
8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	393 *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	394 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	395 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	396
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	397 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	398 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	399 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	400 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	401 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	402 int ret;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	403
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	404 /* 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	405 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	406 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	407 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	408
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	409 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	410 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	411
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	412 prev_str = NULL;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	413 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	414 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	415 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	416
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	417 if (nzstr != &expunged_msg)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	418 ret = strcmp(zstr, nzstr);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	419 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	420 /* 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	421 together */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	422 ret = -1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	423 } else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	424 /* 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	425 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	426 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	427 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	428 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	429 ret = 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	430 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	431
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	432 if (ret <= 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	433 array_append(&ctx->sorted_nodes, &znodes[zpos], 1);
7566 8ae86f73f80d Fixes to sort indexing. Timo Sirainen <tss@iki.fi> parents: 7564 diff changeset	434 prev_str = zstr;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	435 zpos++;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	436 } else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	437 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	438 prev_str = nzstr;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	439 nzpos++;
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 /* 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	442 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	443 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	444 scanning. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	445 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	446 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	447 &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	448 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	449 &nznodes[nzpos],
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	450 nz_next_pos - nzpos);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	451 nzpos = nz_next_pos;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	452 }
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 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	455 /* 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	456 for (; zpos < zcount; zpos++)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	457 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	458 for (; nzpos < nzcount; nzpos++)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	459 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	460
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	461 /* 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	462 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	463 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	464 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	465 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	466
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	467 static void
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	468 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	469 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	470 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	471
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	472 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	473 unsigned int i, count, rightmost_idx, skip;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	474 const char left_str = NULL, right_str = NULL, *str;
7609 c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	475 uint32_t left_sort_id, right_sort_id, diff;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	476 bool no_left_str = FALSE, no_right_str = FALSE;
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	477
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	478 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	479 rightmost_idx = count - 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	480
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	481 /* 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	482 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	483 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	484 /* 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	485 to hit the renumbering code in that situation. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	486 if ((left_sort_id == right_sort_id && left_sort_id != 0) \|\|
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	487 left_sort_id == (uint32_t)-1 \|\| right_sort_id == 1) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	488 /* 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	489 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	490 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	491 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	492 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	493 return;
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 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	497 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	498 left_sort_id = 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	499 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	500 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	501 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	502 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	503 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	504 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	505
7609 c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	506 diff = right_sort_id - left_sort_id;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	507 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	508 /* 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	509 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	510 widening the area we're giving sort IDs. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	511 if (left_idx > 0) {
7568 66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	512 left_sort_id = nodes[--left_idx].sort_id;
66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	513 if (left_sort_id == 0) {
66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	514 i_assert(left_idx == 0);
66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	515 left_sort_id = 1;
66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	516 }
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	517 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	518
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	519 while (right_idx < rightmost_idx) {
7609 c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	520 right_idx++;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	521 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	522 break;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	523 }
7568 66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	524 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	525 if (right_sort_id == 0) {
66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	526 i_assert(right_idx == rightmost_idx);
66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	527 right_sort_id = (uint32_t)-1;
66e6b61680a5 Sort index: Fix to renumbering sort IDs. Timo Sirainen <tss@iki.fi> parents: 7567 diff changeset	528 }
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	529 i_assert(left_sort_id < right_sort_id);
7609 c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	530
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	531 if (diff == right_sort_id - left_sort_id) {
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	532 /* 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	533 have to renumber the leftmost/rightmost node(s) */
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	534 i_assert(left_idx == 0 && right_idx == rightmost_idx);
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	535 if (left_sort_id > 1) {
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	536 left_sort_id = 1;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	537 no_left_str = TRUE;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	538 } else {
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	539 i_assert(right_sort_id != (uint32_t)-1);
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	540 right_sort_id = (uint32_t)-1;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	541 no_right_str = TRUE;
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	542 }
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	543 }
c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	544 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	545 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	546
7609 c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	547 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	548 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	549 nodes[left_idx].seq);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	550 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	551 /* 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	552 left_str = NULL;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	553 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	554 left_idx++;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	555 }
7609 c008dde3c973 sort index: Fixed infinite looping. Timo Sirainen <tss@iki.fi> parents: 7569 diff changeset	556 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	557 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	558 nodes[right_idx].seq);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	559 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	560 /* 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	561 right_str = NULL;
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 right_idx--;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	564 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	565 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	566
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	567 /* 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	568 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	569 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	570 the same sort IDs. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	571 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	572 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	573 if (str == &expunged_msg) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	574 /* 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	575 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	576 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	577 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	578 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	579 continue;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	580 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	581
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	582 if (left_str != NULL && strcmp(str, left_str) == 0)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	583 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	584 else if (right_str != NULL && strcmp(str, right_str) == 0) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	585 /* 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	586 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	587 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	588 } else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	589 /* 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	590 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	591 messages */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	592 if (left_str != NULL)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	593 i_assert(strcmp(left_str, str) < 0);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	594 if (right_str != NULL)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	595 i_assert(strcmp(right_str, str) > 0);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	596 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	597 (right_idx - i + 2);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	598 i_assert(skip > 0);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	599 left_sort_id += skip;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	600 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	601
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	602 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	603 left_str = str;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	604 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	605 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	606 }
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
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	609 static void
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	610 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	611 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	612 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	613 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	614
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	615 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	616 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	617 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	618 continue;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	619
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	620 /* 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	621 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	622 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	623 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	624 break;
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 if (right_idx == count)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	627 right_idx--;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	628 left_idx = i == 0 ? 0 : i - 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	629 index_sort_add_ids_range(ctx, left_idx, right_idx);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	630 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	631 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	632
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	633 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	634 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	635 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	636 (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	637 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	638 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	639 unsigned int i, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	640
7567 9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	641 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	642 /* 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	643 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	644 return;
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	645 }
9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	646
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	647 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	648
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	649 /* 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	650 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	651 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	652 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	653 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	654 continue;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	655
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	656 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	657 &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	658 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	659 }
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 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	662 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	663 struct mail_search_sort_program *program = static_sort_node_cmp_context;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	664 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	665
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	666 if (n1->sort_id < n2->sort_id)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	667 return -1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	668 if (n1->sort_id > n2->sort_id)
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	669 return 1;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	670
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	671 return index_sort_node_cmp_type(program->temp_mail,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	672 program->sort_program + 1,
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	673 n1->seq, n2->seq);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	674 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	675
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	676 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	677 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	678 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	679 const uint32_t *seqs;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	680 unsigned int i, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	681 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	682
7567 9c0d2413735d Sort index: Handle reset_id growing while adding non-wanted messages to sort Timo Sirainen <tss@iki.fi> parents: 7566 diff changeset	683 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	684
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	685 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	686 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	687 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	688 next_seq++;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	689 else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	690 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	691 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	692 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	693 node.seq = seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	694 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	695 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	696 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	697 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	698 }
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	699
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	700 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	701 /* 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	702 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	703 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	704 }
7564 4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	705 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	706
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	707 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	708 {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	709 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	710 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	711 unsigned int i, count;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	712 uint32_t seq;
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 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	715
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	716 static_sort_node_cmp_context = program;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	717 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	718 /* 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	719 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	720 sort_node_cmp);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	721
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	722 i_array_init(&program->seqs, count);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	723 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	724 seq = nodes[i].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	725 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	726 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	727 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	728 } else {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	729 /* 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	730 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	731 to know about. */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	732 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	733 /* 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	734 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	735 /* 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	736 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	737 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	738 sort_node_cmp);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	739 /* sort all messages without sort IDs */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	740 index_sort_zeroes(ctx);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	741 /* merge zero and non-zero arrays into sorted_nodes */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	742 index_sort_merge(ctx);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	743 /* give sort IDs to messages missing them */
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	744 index_sort_add_sort_ids(ctx);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	745 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	746
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	747 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	748 array_clear(&program->seqs);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	749 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	750 if (nodes[i].wanted) {
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	751 seq = nodes[i].seq;
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	752 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	753 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	754 }
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	755 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	756 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	757 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	758 /* 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	759 sorted_nodes. */
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
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	762 array_free(&ctx->zero_nodes);
4a9ce9df52c5 Message sort index handling rewrite to fix several race conditions when Timo Sirainen <tss@iki.fi> parents: diff changeset	763 }

Mercurial > dovecot > original-hg > dovecot-1.2

annotate src/lib-storage/index/index-sort-string.c @ 7609:c008dde3c973 HEAD