summaryrefslogtreecommitdiffstats
path: root/src/lib-index/mail-index-strmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib-index/mail-index-strmap.c')
-rw-r--r--src/lib-index/mail-index-strmap.c1259
1 files changed, 1259 insertions, 0 deletions
diff --git a/src/lib-index/mail-index-strmap.c b/src/lib-index/mail-index-strmap.c
new file mode 100644
index 0000000..1287c73
--- /dev/null
+++ b/src/lib-index/mail-index-strmap.c
@@ -0,0 +1,1259 @@
+/* Copyright (c) 2008-2018 Dovecot authors, see the included COPYING file */
+
+#include "lib.h"
+#include "array.h"
+#include "bsearch-insert-pos.h"
+#include "istream.h"
+#include "ostream.h"
+#include "file-lock.h"
+#include "file-dotlock.h"
+#include "crc32.h"
+#include "safe-mkstemp.h"
+#include "str.h"
+#include "mail-index-private.h"
+#include "mail-index-strmap.h"
+
+#include <stdio.h>
+
+struct mail_index_strmap {
+ struct mail_index *index;
+ char *path;
+ int fd;
+ struct istream *input;
+
+ struct file_lock *file_lock;
+ struct dotlock *dotlock;
+ struct dotlock_settings dotlock_settings;
+};
+
+struct mail_index_strmap_view {
+ struct mail_index_strmap *strmap;
+ struct mail_index_view *view;
+
+ ARRAY_TYPE(mail_index_strmap_rec) recs;
+ ARRAY(uint32_t) recs_crc32;
+ struct hash2_table *hash;
+
+ mail_index_strmap_key_cmp_t *key_compare;
+ mail_index_strmap_rec_cmp_t *rec_compare;
+ mail_index_strmap_remap_t *remap_cb;
+ void *cb_context;
+
+ uoff_t last_read_block_offset;
+ uint32_t last_read_uid;
+ uint32_t last_added_uid;
+ uint32_t total_ref_count;
+
+ uint32_t last_ref_index;
+ uint32_t next_str_idx;
+ uint32_t lost_expunged_uid;
+
+ bool desynced:1;
+};
+
+struct mail_index_strmap_read_context {
+ struct mail_index_strmap_view *view;
+
+ struct istream *input;
+ uoff_t end_offset;
+ uint32_t highest_str_idx;
+ uint32_t uid_lookup_seq;
+ uint32_t lost_expunged_uid;
+
+ const unsigned char *data, *end, *str_idx_base;
+ struct mail_index_strmap_rec rec;
+ uint32_t next_ref_index;
+ unsigned int rec_size;
+
+ bool too_large_uids:1;
+};
+
+struct mail_index_strmap_view_sync {
+ struct mail_index_strmap_view *view;
+};
+
+struct mail_index_strmap_hash_key {
+ const char *str;
+ uint32_t crc32;
+};
+
+/* number of bytes required to store one string idx */
+#define STRMAP_FILE_STRIDX_SIZE (sizeof(uint32_t)*2)
+
+/* renumber the string indexes when highest string idx becomes larger than
+ <number of indexes>*STRMAP_FILE_MAX_STRIDX_MULTIPLIER */
+#define STRMAP_FILE_MAX_STRIDX_MULTIPLIER 2
+
+#define STRIDX_MUST_RENUMBER(highest_idx, n_unique_indexes) \
+ (highest_idx > n_unique_indexes * STRMAP_FILE_MAX_STRIDX_MULTIPLIER)
+
+#define MAIL_INDEX_STRMAP_TIMEOUT_SECS 10
+
+static const struct dotlock_settings default_dotlock_settings = {
+ .timeout = MAIL_INDEX_STRMAP_TIMEOUT_SECS,
+ .stale_timeout = 30
+};
+
+struct mail_index_strmap *
+mail_index_strmap_init(struct mail_index *index, const char *suffix)
+{
+ struct mail_index_strmap *strmap;
+
+ i_assert(index->open_count > 0);
+
+ strmap = i_new(struct mail_index_strmap, 1);
+ strmap->index = index;
+ strmap->path = i_strconcat(index->filepath, suffix, NULL);
+ strmap->fd = -1;
+
+ strmap->dotlock_settings = default_dotlock_settings;
+ strmap->dotlock_settings.use_excl_lock =
+ (index->flags & MAIL_INDEX_OPEN_FLAG_DOTLOCK_USE_EXCL) != 0;
+ strmap->dotlock_settings.nfs_flush =
+ (index->flags & MAIL_INDEX_OPEN_FLAG_NFS_FLUSH) != 0;
+ return strmap;
+}
+
+static bool
+mail_index_strmap_read_rec_next(struct mail_index_strmap_read_context *ctx,
+ uint32_t *crc32_r);
+
+static void
+mail_index_strmap_set_syscall_error(struct mail_index_strmap *strmap,
+ const char *function)
+{
+ i_assert(function != NULL);
+
+ if (ENOSPACE(errno)) {
+ strmap->index->last_error.nodiskspace = TRUE;
+ if ((strmap->index->flags &
+ MAIL_INDEX_OPEN_FLAG_NEVER_IN_MEMORY) == 0)
+ return;
+ }
+
+ mail_index_set_error(strmap->index,
+ "%s failed with strmap index file %s: %m",
+ function, strmap->path);
+}
+
+static void mail_index_strmap_close(struct mail_index_strmap *strmap)
+{
+ if (strmap->file_lock != NULL)
+ file_lock_free(&strmap->file_lock);
+ else if (strmap->dotlock != NULL)
+ file_dotlock_delete(&strmap->dotlock);
+
+ if (strmap->fd != -1) {
+ if (close(strmap->fd) < 0)
+ mail_index_strmap_set_syscall_error(strmap, "close()");
+ strmap->fd = -1;
+ }
+ i_stream_unref(&strmap->input);
+}
+
+void mail_index_strmap_deinit(struct mail_index_strmap **_strmap)
+{
+ struct mail_index_strmap *strmap = *_strmap;
+
+ *_strmap = NULL;
+ mail_index_strmap_close(strmap);
+ i_free(strmap->path);
+ i_free(strmap);
+}
+
+static unsigned int mail_index_strmap_hash_key(const void *_key)
+{
+ const struct mail_index_strmap_hash_key *key = _key;
+
+ return key->crc32;
+}
+
+static bool
+mail_index_strmap_hash_cmp(const void *_key, const void *_value, void *context)
+{
+ const struct mail_index_strmap_hash_key *key = _key;
+ const struct mail_index_strmap_rec *rec = _value;
+ struct mail_index_strmap_view *view = context;
+
+ return view->key_compare(key->str, rec, view->cb_context);
+}
+
+struct mail_index_strmap_view *
+mail_index_strmap_view_open(struct mail_index_strmap *strmap,
+ struct mail_index_view *idx_view,
+ mail_index_strmap_key_cmp_t *key_compare_cb,
+ mail_index_strmap_rec_cmp_t *rec_compare_cb,
+ mail_index_strmap_remap_t *remap_cb,
+ void *context,
+ const ARRAY_TYPE(mail_index_strmap_rec) **recs_r,
+ const struct hash2_table **hash_r)
+{
+ struct mail_index_strmap_view *view;
+
+ view = i_new(struct mail_index_strmap_view, 1);
+ view->strmap = strmap;
+ view->view = idx_view;
+ view->key_compare = key_compare_cb;
+ view->rec_compare = rec_compare_cb;
+ view->remap_cb = remap_cb;
+ view->cb_context = context;
+ view->next_str_idx = 1;
+
+ i_array_init(&view->recs, 64);
+ i_array_init(&view->recs_crc32, 64);
+ view->hash = hash2_create(0, sizeof(struct mail_index_strmap_rec),
+ mail_index_strmap_hash_key,
+ mail_index_strmap_hash_cmp, view);
+ *recs_r = &view->recs;
+ *hash_r = view->hash;
+ return view;
+}
+
+void mail_index_strmap_view_close(struct mail_index_strmap_view **_view)
+{
+ struct mail_index_strmap_view *view = *_view;
+
+ *_view = NULL;
+ array_free(&view->recs);
+ array_free(&view->recs_crc32);
+ hash2_destroy(&view->hash);
+ i_free(view);
+}
+
+uint32_t mail_index_strmap_view_get_highest_idx(struct mail_index_strmap_view *view)
+{
+ return view->next_str_idx-1;
+}
+
+static void mail_index_strmap_view_reset(struct mail_index_strmap_view *view)
+{
+ view->remap_cb(NULL, 0, 0, view->cb_context);
+ array_clear(&view->recs);
+ array_clear(&view->recs_crc32);
+ hash2_clear(view->hash);
+
+ view->last_added_uid = 0;
+ view->lost_expunged_uid = 0;
+ view->desynced = FALSE;
+}
+
+void mail_index_strmap_view_set_corrupted(struct mail_index_strmap_view *view)
+{
+ mail_index_set_error(view->strmap->index,
+ "Corrupted strmap index file: %s",
+ view->strmap->path);
+ i_unlink(view->strmap->path);
+ mail_index_strmap_close(view->strmap);
+ mail_index_strmap_view_reset(view);
+}
+
+static int mail_index_strmap_open(struct mail_index_strmap_view *view)
+{
+ struct mail_index_strmap *strmap = view->strmap;
+ const struct mail_index_header *idx_hdr;
+ struct mail_index_strmap_header hdr;
+ const unsigned char *data;
+ size_t size;
+ int ret;
+
+ i_assert(strmap->fd == -1);
+
+ strmap->fd = open(strmap->path, O_RDWR);
+ if (strmap->fd == -1) {
+ if (errno == ENOENT)
+ return 0;
+ mail_index_strmap_set_syscall_error(strmap, "open()");
+ return -1;
+ }
+ strmap->input = i_stream_create_fd(strmap->fd, SIZE_MAX);
+ ret = i_stream_read_bytes(strmap->input, &data, &size, sizeof(hdr));
+ if (ret <= 0) {
+ if (ret < 0) {
+ mail_index_strmap_set_syscall_error(strmap, "read()");
+ mail_index_strmap_close(strmap);
+ } else {
+ i_assert(ret == 0);
+ mail_index_strmap_view_set_corrupted(view);
+ }
+ return ret;
+ }
+ memcpy(&hdr, data, sizeof(hdr));
+
+ idx_hdr = mail_index_get_header(view->view);
+ if (hdr.version != MAIL_INDEX_STRMAP_VERSION ||
+ hdr.uid_validity != idx_hdr->uid_validity) {
+ /* need to rebuild. if we already had something in the strmap,
+ we can keep it. */
+ i_unlink(strmap->path);
+ mail_index_strmap_close(strmap);
+ return 0;
+ }
+
+ /* we'll read the entire file from the beginning */
+ view->last_added_uid = 0;
+ view->last_read_uid = 0;
+ view->total_ref_count = 0;
+ view->last_read_block_offset = sizeof(struct mail_index_strmap_header);
+ view->next_str_idx = 1;
+
+ mail_index_strmap_view_reset(view);
+ return 0;
+}
+
+static bool mail_index_strmap_need_reopen(struct mail_index_strmap *strmap)
+{
+ struct stat st1, st2;
+
+ /* FIXME: nfs flush */
+ if (fstat(strmap->fd, &st1) < 0) {
+ if (!ESTALE_FSTAT(errno))
+ mail_index_strmap_set_syscall_error(strmap, "fstat()");
+ return TRUE;
+ }
+ if (stat(strmap->path, &st2) < 0) {
+ mail_index_strmap_set_syscall_error(strmap, "stat()");
+ return TRUE;
+ }
+ return st1.st_ino != st2.st_ino || !CMP_DEV_T(st1.st_dev, st2.st_dev);
+}
+
+static int mail_index_strmap_refresh(struct mail_index_strmap_view *view)
+{
+ uint32_t seq;
+
+ if (MAIL_INDEX_IS_IN_MEMORY(view->strmap->index))
+ return -1;
+
+ if (view->strmap->fd != -1) {
+ if (!mail_index_strmap_need_reopen(view->strmap)) {
+ if (view->lost_expunged_uid != 0) {
+ /* last read failed because view had a message
+ that didn't exist in the strmap (because it
+ was expunged by another session). if the
+ message still isn't expunged in this view,
+ just continue using the current strmap. */
+ if (mail_index_lookup_seq(view->view,
+ view->lost_expunged_uid, &seq))
+ return -1;
+ } else if (view->desynced) {
+ /* our view isn't synced with the disk, we
+ can't read strmap without first resetting
+ the view */
+ } else {
+ i_stream_sync(view->strmap->input);
+ return 0;
+ }
+ }
+ mail_index_strmap_close(view->strmap);
+ }
+
+ return mail_index_strmap_open(view);
+}
+
+static int
+mail_index_strmap_read_packed(struct mail_index_strmap_read_context *ctx,
+ uint32_t *num_r)
+{
+ const unsigned char *data;
+ const uint8_t *bytes, *p, *end;
+ size_t size;
+ int ret;
+
+ ret = i_stream_read_bytes(ctx->input, &data, &size, sizeof(*num_r));
+ if (ret <= 0)
+ return ret;
+
+ if (ctx->input->v_offset + size > ctx->end_offset)
+ size = ctx->end_offset - ctx->input->v_offset;
+ bytes = p = (const uint8_t *)data;
+ end = bytes + size;
+
+ if (mail_index_unpack_num(&p, end, num_r) < 0)
+ return -1;
+ i_stream_skip(ctx->input, p - bytes);
+ return 1;
+}
+
+static int
+mail_index_strmap_uid_exists(struct mail_index_strmap_read_context *ctx,
+ uint32_t uid)
+{
+ const struct mail_index_record *rec;
+
+ i_assert(ctx->uid_lookup_seq > 0);
+
+ if (ctx->uid_lookup_seq > ctx->view->view->map->hdr.messages_count) {
+ if (uid >= ctx->view->view->map->hdr.next_uid) {
+ /* thread index has larger UIDs than what we've seen
+ in our view. we'll have to read them again later
+ when we know about them */
+ ctx->too_large_uids = TRUE;
+ }
+ return 0;
+ }
+
+ rec = MAIL_INDEX_REC_AT_SEQ(ctx->view->view->map, ctx->uid_lookup_seq);
+ if (rec->uid == uid) {
+ ctx->uid_lookup_seq++;
+ return 1;
+ } else if (rec->uid > uid) {
+ return 0;
+ } else {
+ /* record that exists in index is missing from strmap.
+ see if it's because the strmap is corrupted or because
+ our current view is a bit stale and the message has already
+ been expunged. */
+ mail_index_refresh(ctx->view->view->index);
+ if (mail_index_is_expunged(ctx->view->view,
+ ctx->uid_lookup_seq))
+ ctx->lost_expunged_uid = rec->uid;
+ return -1;
+ }
+}
+
+static int
+mail_index_strmap_read_rec_first(struct mail_index_strmap_read_context *ctx,
+ uint32_t *crc32_r)
+{
+ size_t size;
+ uint32_t n, i, count, str_idx;
+ int ret;
+
+ /* <uid> <n> <crc32>*count <str_idx>*count
+ where
+ n = 0 -> count=1 (only Message-ID:)
+ n = 1 -> count=2 (Message-ID: + In-Reply-To:)
+ n = 2+ -> count=n (Message-ID: + References:)
+ */
+ if (mail_index_strmap_read_packed(ctx, &n) <= 0)
+ return -1;
+ count = n < 2 ? n + 1 : n;
+ ctx->view->total_ref_count += count;
+
+ ctx->rec_size = count * (sizeof(ctx->rec.str_idx) + sizeof(*crc32_r));
+ ret = mail_index_strmap_uid_exists(ctx, ctx->rec.uid);
+ if (ret < 0)
+ return -1;
+ if (i_stream_read_bytes(ctx->view->strmap->input, &ctx->data, &size, ctx->rec_size) <= 0)
+ return -1;
+ ctx->str_idx_base = ctx->data + count * sizeof(uint32_t);
+
+ if (ret == 0) {
+ /* this message has already been expunged, ignore it.
+ update highest string indexes anyway. */
+ for (i = 0; i < count; i++) {
+ memcpy(&str_idx, ctx->str_idx_base, sizeof(str_idx));
+ if (ctx->highest_str_idx < str_idx)
+ ctx->highest_str_idx = str_idx;
+ ctx->str_idx_base += sizeof(str_idx);
+ }
+ i_stream_skip(ctx->view->strmap->input, ctx->rec_size);
+ return 0;
+ }
+
+ /* everything exists. save it. FIXME: these ref_index values
+ are thread index specific, perhaps something more generic
+ should be used some day */
+ ctx->end = ctx->data + count * sizeof(*crc32_r);
+
+ ctx->next_ref_index = 0;
+ if (!mail_index_strmap_read_rec_next(ctx, crc32_r))
+ i_unreached();
+ ctx->next_ref_index = n == 1 ? 1 : 2;
+ return 1;
+}
+
+static bool
+mail_index_strmap_read_rec_next(struct mail_index_strmap_read_context *ctx,
+ uint32_t *crc32_r)
+{
+ if (ctx->data == ctx->end) {
+ i_stream_skip(ctx->view->strmap->input, ctx->rec_size);
+ return FALSE;
+ }
+
+ /* FIXME: str_idx could be stored as packed relative values
+ (first relative to highest_idx, the rest relative to the
+ previous str_idx) */
+
+ /* read the record contents */
+ memcpy(&ctx->rec.str_idx, ctx->str_idx_base, sizeof(ctx->rec.str_idx));
+ memcpy(crc32_r, ctx->data, sizeof(*crc32_r));
+
+ ctx->rec.ref_index = ctx->next_ref_index++;
+
+ if (ctx->highest_str_idx < ctx->rec.str_idx)
+ ctx->highest_str_idx = ctx->rec.str_idx;
+
+ /* get to the next record */
+ ctx->data += sizeof(*crc32_r);
+ ctx->str_idx_base += sizeof(ctx->rec.str_idx);
+ return TRUE;
+}
+
+static int
+strmap_read_block_init(struct mail_index_strmap_view *view,
+ struct mail_index_strmap_read_context *ctx)
+{
+ struct mail_index_strmap *strmap = view->strmap;
+ const unsigned char *data;
+ size_t size;
+ uint32_t block_size, seq1, seq2;
+ int ret;
+
+ if (view->last_read_uid + 1 >= view->view->map->hdr.next_uid) {
+ /* come back later when we know about the new UIDs */
+ return 0;
+ }
+
+ i_zero(ctx);
+ ret = i_stream_read_bytes(strmap->input, &data, &size,
+ sizeof(block_size));
+ if (ret <= 0) {
+ if (strmap->input->stream_errno == 0) {
+ /* no new data */
+ return 0;
+ }
+ mail_index_strmap_set_syscall_error(strmap, "read()");
+ return -1;
+ }
+ memcpy(&block_size, data, sizeof(block_size));
+ block_size = mail_index_offset_to_uint32(block_size) >> 2;
+ if (block_size == 0) {
+ /* the rest of the file is either not written, or the previous
+ write didn't finish */
+ return 0;
+ }
+ i_stream_skip(strmap->input, sizeof(block_size));
+
+ ctx->view = view;
+ ctx->input = strmap->input;
+ ctx->end_offset = strmap->input->v_offset + block_size;
+ if (ctx->end_offset < strmap->input->v_offset) {
+ /* block size too large */
+ mail_index_strmap_view_set_corrupted(view);
+ return -1;
+ }
+ ctx->rec.uid = view->last_read_uid + 1;
+
+ /* FIXME: when reading multiple blocks we shouldn't have to calculate
+ this every time */
+ if (!mail_index_lookup_seq_range(view->view, ctx->rec.uid, (uint32_t)-1,
+ &seq1, &seq2))
+ seq1 = mail_index_view_get_messages_count(view->view) + 1;
+ ctx->uid_lookup_seq = seq1;
+ return 1;
+}
+
+static int
+strmap_read_block_next(struct mail_index_strmap_read_context *ctx,
+ uint32_t *crc32_r)
+{
+ uint32_t uid_diff;
+ int ret;
+
+ if (mail_index_strmap_read_rec_next(ctx, crc32_r))
+ return 1;
+
+ /* get next UID */
+ do {
+ if (ctx->input->v_offset == ctx->end_offset) {
+ /* this block is done */
+ return 0;
+ }
+ if (mail_index_strmap_read_packed(ctx, &uid_diff) <= 0)
+ return -1;
+
+ ctx->rec.uid += uid_diff;
+ ret = mail_index_strmap_read_rec_first(ctx, crc32_r);
+ } while (ret == 0);
+ return ret;
+}
+
+static int
+strmap_read_block_deinit(struct mail_index_strmap_read_context *ctx, int ret,
+ bool update_block_offset)
+{
+ struct mail_index_strmap_view *view = ctx->view;
+ struct mail_index_strmap *strmap = view->strmap;
+
+ if (ctx->highest_str_idx > view->total_ref_count) {
+ /* if all string indexes are unique, highest_str_index equals
+ total_ref_count. otherwise it's always lower. */
+ mail_index_set_error(strmap->index,
+ "Corrupted strmap index file %s: "
+ "String indexes too high "
+ "(highest=%u max=%u)",
+ strmap->path, ctx->highest_str_idx,
+ view->total_ref_count);
+ mail_index_strmap_view_set_corrupted(view);
+ return -1;
+ }
+ if (ctx->lost_expunged_uid != 0) {
+ /* our view contained a message that had since been expunged. */
+ i_assert(ret < 0);
+ view->lost_expunged_uid = ctx->lost_expunged_uid;
+ } else if (ret < 0) {
+ if (strmap->input->stream_errno != 0)
+ mail_index_strmap_set_syscall_error(strmap, "read()");
+ else
+ mail_index_strmap_view_set_corrupted(view);
+ return -1;
+ } else if (update_block_offset && !ctx->too_large_uids) {
+ view->last_read_block_offset = strmap->input->v_offset;
+ view->last_read_uid = ctx->rec.uid;
+ }
+ if (view->next_str_idx <= ctx->highest_str_idx)
+ view->next_str_idx = ctx->highest_str_idx + 1;
+ return ret;
+}
+
+static bool
+strmap_view_sync_handle_conflict(struct mail_index_strmap_read_context *ctx,
+ const struct mail_index_strmap_rec *hash_rec,
+ struct hash2_iter *iter)
+{
+ uint32_t seq;
+
+ /* hopefully it's a message that has since been expunged */
+ if (!mail_index_lookup_seq(ctx->view->view, hash_rec->uid, &seq)) {
+ /* message is no longer in our view. remove it completely. */
+ hash2_remove_iter(ctx->view->hash, iter);
+ return TRUE;
+ }
+ if (mail_index_is_expunged(ctx->view->view, seq)) {
+ /* it's quite likely a conflict. we may not be able to verify
+ it, so just assume it is. nothing breaks even if we guess
+ wrong, the performance just suffers a bit. */
+ return FALSE;
+ }
+
+ /* 0 means "doesn't match", which is the only acceptable case */
+ return ctx->view->rec_compare(&ctx->rec, hash_rec,
+ ctx->view->cb_context) == 0;
+}
+
+static int
+strmap_view_sync_block_check_conflicts(struct mail_index_strmap_read_context *ctx,
+ uint32_t crc32)
+{
+ struct mail_index_strmap_rec *hash_rec;
+ struct hash2_iter iter;
+
+ if (crc32 == 0) {
+ /* unique string - there are no conflicts */
+ return 0;
+ }
+
+ /* check for conflicting string indexes. they may happen if
+
+ 1) msgid exists only for a message X that has been expunged
+ 2) another process doesn't see X, but sees msgid for another
+ message and writes it using a new string index
+ 3) if we still see X, we now see the same msgid with two
+ string indexes.
+
+ if we detect such a conflict, we can't continue using the
+ strmap index until X has been expunged. */
+ i_zero(&iter);
+ while ((hash_rec = hash2_iterate(ctx->view->hash,
+ crc32, &iter)) != NULL &&
+ hash_rec->str_idx != ctx->rec.str_idx) {
+ /* CRC32 matches, but string index doesn't */
+ if (!strmap_view_sync_handle_conflict(ctx, hash_rec, &iter)) {
+ ctx->lost_expunged_uid = hash_rec->uid;
+ return -1;
+ }
+ }
+ return 0;
+}
+
+static int
+mail_index_strmap_view_sync_block(struct mail_index_strmap_read_context *ctx)
+{
+ struct mail_index_strmap_rec *hash_rec;
+ uint32_t crc32, prev_uid = 0;
+ int ret;
+
+ while ((ret = strmap_read_block_next(ctx, &crc32)) > 0) {
+ if (ctx->rec.uid <= ctx->view->last_added_uid) {
+ if (ctx->rec.uid < ctx->view->last_added_uid ||
+ prev_uid != ctx->rec.uid) {
+ /* we've already added this */
+ continue;
+ }
+ }
+ prev_uid = ctx->rec.uid;
+
+ if (strmap_view_sync_block_check_conflicts(ctx, crc32) < 0) {
+ ret = -1;
+ break;
+ }
+ ctx->view->last_added_uid = ctx->rec.uid;
+
+ /* add the record to records array */
+ array_push_back(&ctx->view->recs, &ctx->rec);
+ array_push_back(&ctx->view->recs_crc32, &crc32);
+
+ /* add a separate copy of the record to hash */
+ hash_rec = hash2_insert_hash(ctx->view->hash, crc32);
+ memcpy(hash_rec, &ctx->rec, sizeof(*hash_rec));
+ }
+ return strmap_read_block_deinit(ctx, ret, TRUE);
+}
+
+struct mail_index_strmap_view_sync *
+mail_index_strmap_view_sync_init(struct mail_index_strmap_view *view,
+ uint32_t *last_uid_r)
+{
+ struct mail_index_strmap_view_sync *sync;
+ struct mail_index_strmap_read_context ctx;
+ int ret;
+
+ sync = i_new(struct mail_index_strmap_view_sync, 1);
+ sync->view = view;
+
+ if (mail_index_strmap_refresh(view) < 0) {
+ /* reading the strmap failed - just ignore and do
+ this in-memory based on whatever we knew last */
+ } else if (view->strmap->input != NULL) {
+ i_stream_seek(view->strmap->input,
+ view->last_read_block_offset);
+ while ((ret = strmap_read_block_init(view, &ctx)) > 0) {
+ if (mail_index_strmap_view_sync_block(&ctx) < 0) {
+ ret = -1;
+ break;
+ }
+ if (ctx.too_large_uids)
+ break;
+ }
+
+ if (ret < 0) {
+ /* something failed - we can still use the strmap as far
+ as we managed to read it, but our view is now out
+ of sync */
+ view->desynced = TRUE;
+ } else {
+ i_assert(view->lost_expunged_uid == 0);
+ }
+ }
+ *last_uid_r = view->last_added_uid;
+ return sync;
+}
+
+static inline uint32_t crc32_str_nonzero(const char *str)
+{
+ /* we'll flip the bits because of a bug in our old crc32 code.
+ this keeps the index format backwards compatible with the new fixed
+ crc32 code. */
+ uint32_t value = crc32_str(str) ^ 0xffffffffU;
+ return value == 0 ? 1 : value;
+}
+
+void mail_index_strmap_view_sync_add(struct mail_index_strmap_view_sync *sync,
+ uint32_t uid, uint32_t ref_index,
+ const char *key)
+{
+ struct mail_index_strmap_view *view = sync->view;
+ struct mail_index_strmap_rec *rec, *old_rec;
+ struct mail_index_strmap_hash_key hash_key;
+ uint32_t str_idx;
+
+ i_assert(uid > view->last_added_uid ||
+ (uid == view->last_added_uid &&
+ ref_index > view->last_ref_index));
+
+ hash_key.str = key;
+ hash_key.crc32 = crc32_str_nonzero(key);
+
+ old_rec = hash2_lookup(view->hash, &hash_key);
+ if (old_rec != NULL) {
+ /* The string already exists, use the same unique idx */
+ str_idx = old_rec->str_idx;
+ } else {
+ /* Newly seen string, assign a new unique idx to it */
+ str_idx = view->next_str_idx++;
+ }
+ i_assert(str_idx != 0);
+
+ rec = hash2_insert(view->hash, &hash_key);
+ rec->uid = uid;
+ rec->ref_index = ref_index;
+ rec->str_idx = str_idx;
+ array_push_back(&view->recs, rec);
+ array_push_back(&view->recs_crc32, &hash_key.crc32);
+
+ view->last_added_uid = uid;
+ view->last_ref_index = ref_index;
+}
+
+void mail_index_strmap_view_sync_add_unique(struct mail_index_strmap_view_sync *sync,
+ uint32_t uid, uint32_t ref_index)
+{
+ struct mail_index_strmap_view *view = sync->view;
+ struct mail_index_strmap_rec rec;
+
+ i_assert(uid > view->last_added_uid ||
+ (uid == view->last_added_uid &&
+ ref_index > view->last_ref_index));
+
+ i_zero(&rec);
+ rec.uid = uid;
+ rec.ref_index = ref_index;
+ rec.str_idx = view->next_str_idx++;
+ array_push_back(&view->recs, &rec);
+ array_append_zero(&view->recs_crc32);
+
+ view->last_added_uid = uid;
+ view->last_ref_index = ref_index;
+}
+
+static void
+mail_index_strmap_zero_terminate(struct mail_index_strmap_view *view)
+{
+ /* zero-terminate the records array */
+ array_append_zero(&view->recs);
+ array_pop_back(&view->recs);
+}
+
+static void mail_index_strmap_view_renumber(struct mail_index_strmap_view *view)
+{
+ struct mail_index_strmap_read_context ctx;
+ struct mail_index_strmap_rec *recs, *hash_rec;
+ uint32_t prev_uid, str_idx, *recs_crc32, *renumber_map;
+ unsigned int i, dest, count, count2;
+ int ret;
+
+ i_zero(&ctx);
+ ctx.view = view;
+ ctx.uid_lookup_seq = 1;
+
+ /* create a map of old -> new index and remove records of
+ expunged messages */
+ renumber_map = i_new(uint32_t, view->next_str_idx);
+ str_idx = 0; prev_uid = 0;
+ recs = array_get_modifiable(&view->recs, &count);
+ recs_crc32 = array_get_modifiable(&view->recs_crc32, &count2);
+ i_assert(count == count2);
+
+ for (i = dest = 0; i < count; ) {
+ if (prev_uid != recs[i].uid) {
+ /* see if this record should be removed */
+ prev_uid = recs[i].uid;
+ ret = mail_index_strmap_uid_exists(&ctx, prev_uid);
+ i_assert(ret >= 0);
+ if (ret == 0) {
+ /* message expunged */
+ do {
+ i++;
+ } while (i < count && recs[i].uid == prev_uid);
+ continue;
+ }
+ }
+
+ i_assert(recs[i].str_idx < view->next_str_idx);
+ if (renumber_map[recs[i].str_idx] == 0)
+ renumber_map[recs[i].str_idx] = ++str_idx;
+ if (i != dest) {
+ recs[dest] = recs[i];
+ recs_crc32[dest] = recs_crc32[i];
+ }
+ i++; dest++;
+ }
+ i_assert(renumber_map[0] == 0);
+ array_delete(&view->recs, dest, i-dest);
+ array_delete(&view->recs_crc32, dest, i-dest);
+ mail_index_strmap_zero_terminate(view);
+
+ /* notify caller of the renumbering */
+ i_assert(str_idx <= view->next_str_idx);
+ view->remap_cb(renumber_map, view->next_str_idx, str_idx + 1,
+ view->cb_context);
+
+ /* renumber the indexes in-place and recreate the hash */
+ recs = array_get_modifiable(&view->recs, &count);
+ hash2_clear(view->hash);
+ for (i = 0; i < count; i++) {
+ recs[i].str_idx = renumber_map[recs[i].str_idx];
+ hash_rec = hash2_insert_hash(view->hash, recs_crc32[i]);
+ memcpy(hash_rec, &recs[i], sizeof(*hash_rec));
+ }
+
+ /* update the new next_str_idx only after remapping */
+ view->next_str_idx = str_idx + 1;
+ i_free(renumber_map);
+}
+
+static void mail_index_strmap_write_block(struct mail_index_strmap_view *view,
+ struct ostream *output,
+ unsigned int i, uint32_t base_uid)
+{
+ const struct mail_index_strmap_rec *recs;
+ const uint32_t *crc32;
+ unsigned int j, n, count, count2, uid_rec_count;
+ uint32_t block_size;
+ uint8_t *p, packed[MAIL_INDEX_PACK_MAX_SIZE*2];
+ uoff_t block_offset, end_offset;
+
+ /* skip over the block size for now, we don't know it yet */
+ block_offset = output->offset;
+ block_size = 0;
+ o_stream_nsend(output, &block_size, sizeof(block_size));
+
+ /* write records */
+ recs = array_get(&view->recs, &count);
+ crc32 = array_get(&view->recs_crc32, &count2);
+ i_assert(count == count2);
+ while (i < count) {
+ /* @UNSAFE: <uid diff> */
+ p = packed;
+ mail_index_pack_num(&p, recs[i].uid - base_uid);
+ base_uid = recs[i].uid;
+
+ /* find how many records belong to this UID */
+ uid_rec_count = 1;
+ for (j = i + 1; j < count; j++) {
+ if (recs[j].uid != base_uid)
+ break;
+ uid_rec_count++;
+ }
+ view->total_ref_count += uid_rec_count;
+
+ /* <n> <crc32>*count <str_idx>*count -
+ FIXME: thread index specific code */
+ i_assert(recs[i].ref_index == 0);
+ if (uid_rec_count == 1) {
+ /* Only Message-ID: header */
+ n = 0;
+ } else if (recs[i+1].ref_index == 1) {
+ /* In-Reply-To: header */
+ n = 1;
+ i_assert(uid_rec_count == 2);
+ } else {
+ /* References: header */
+ n = uid_rec_count;
+ i_assert(recs[i+1].ref_index == 2);
+ }
+
+ mail_index_pack_num(&p, n);
+ o_stream_nsend(output, packed, p-packed);
+ for (j = 0; j < uid_rec_count; j++)
+ o_stream_nsend(output, &crc32[i+j], sizeof(crc32[i+j]));
+ for (j = 0; j < uid_rec_count; j++) {
+ i_assert(j < 2 || recs[i+j].ref_index == j+1);
+ o_stream_nsend(output, &recs[i+j].str_idx,
+ sizeof(recs[i+j].str_idx));
+ }
+ i += uid_rec_count;
+ }
+
+ /* we know the block size now - write it */
+ block_size = output->offset - (block_offset + sizeof(block_size));
+ block_size = mail_index_uint32_to_offset(block_size << 2);
+ i_assert(block_size != 0);
+
+ end_offset = output->offset;
+ (void)o_stream_seek(output, block_offset);
+ o_stream_nsend(output, &block_size, sizeof(block_size));
+ (void)o_stream_seek(output, end_offset);
+
+ if (output->stream_errno != 0)
+ return;
+
+ i_assert(view->last_added_uid == recs[count-1].uid);
+ view->last_read_uid = recs[count-1].uid;
+ view->last_read_block_offset = output->offset;
+}
+
+static void
+mail_index_strmap_recreate_write(struct mail_index_strmap_view *view,
+ struct ostream *output)
+{
+ const struct mail_index_header *idx_hdr;
+ struct mail_index_strmap_header hdr;
+
+ idx_hdr = mail_index_get_header(view->view);
+
+ /* write header */
+ i_zero(&hdr);
+ hdr.version = MAIL_INDEX_STRMAP_VERSION;
+ hdr.uid_validity = idx_hdr->uid_validity;
+ o_stream_nsend(output, &hdr, sizeof(hdr));
+
+ view->total_ref_count = 0;
+ mail_index_strmap_write_block(view, output, 0, 1);
+}
+
+static int mail_index_strmap_recreate(struct mail_index_strmap_view *view)
+{
+ struct mail_index_strmap *strmap = view->strmap;
+ string_t *str;
+ struct ostream *output;
+ const char *temp_path;
+ int fd, ret = 0;
+
+ if (array_count(&view->recs) == 0) {
+ /* everything expunged - just unlink the existing index */
+ if (unlink(strmap->path) < 0 && errno != ENOENT)
+ mail_index_strmap_set_syscall_error(strmap, "unlink()");
+ return 0;
+ }
+
+ str = t_str_new(256);
+ str_append(str, strmap->path);
+ fd = safe_mkstemp_hostpid_group(str, view->view->index->set.mode,
+ view->view->index->set.gid,
+ view->view->index->set.gid_origin);
+ temp_path = str_c(str);
+
+ if (fd == -1) {
+ mail_index_set_error(strmap->index,
+ "safe_mkstemp_hostpid(%s) failed: %m",
+ temp_path);
+ return -1;
+ }
+ output = o_stream_create_fd(fd, 0);
+ o_stream_cork(output);
+ mail_index_strmap_recreate_write(view, output);
+ if (o_stream_finish(output) < 0) {
+ mail_index_set_error(strmap->index, "write(%s) failed: %s",
+ temp_path, o_stream_get_error(output));
+ ret = -1;
+ }
+ o_stream_destroy(&output);
+ if (close(fd) < 0) {
+ mail_index_set_error(strmap->index,
+ "close(%s) failed: %m", temp_path);
+ ret = -1;
+ } else if (ret == 0 && rename(temp_path, strmap->path) < 0) {
+ mail_index_set_error(strmap->index,
+ "rename(%s, %s) failed: %m",
+ temp_path, strmap->path);
+ ret = -1;
+ }
+ if (ret < 0)
+ i_unlink(temp_path);
+ return ret;
+}
+
+static int mail_index_strmap_lock(struct mail_index_strmap *strmap)
+{
+ unsigned int timeout_secs;
+ const char *error;
+ int ret;
+
+ i_assert(strmap->fd != -1);
+
+ if (strmap->index->set.lock_method != FILE_LOCK_METHOD_DOTLOCK) {
+ i_assert(strmap->file_lock == NULL);
+
+ struct file_lock_settings lock_set = {
+ .lock_method = strmap->index->set.lock_method,
+ };
+ timeout_secs = I_MIN(MAIL_INDEX_STRMAP_TIMEOUT_SECS,
+ strmap->index->set.max_lock_timeout_secs);
+ ret = file_wait_lock(strmap->fd, strmap->path, F_WRLCK,
+ &lock_set, timeout_secs,
+ &strmap->file_lock, &error);
+ if (ret <= 0) {
+ mail_index_set_error(strmap->index,
+ "file_wait_lock() failed with strmap index file %s: %s",
+ strmap->path, error);
+ }
+ } else {
+ i_assert(strmap->dotlock == NULL);
+
+ ret = file_dotlock_create(&strmap->dotlock_settings,
+ strmap->path, 0, &strmap->dotlock);
+ if (ret <= 0) {
+ mail_index_strmap_set_syscall_error(strmap,
+ "file_dotlock_create()");
+ }
+ }
+ return ret;
+}
+
+static void mail_index_strmap_unlock(struct mail_index_strmap *strmap)
+{
+ if (strmap->file_lock != NULL)
+ file_unlock(&strmap->file_lock);
+ else if (strmap->dotlock != NULL)
+ file_dotlock_delete(&strmap->dotlock);
+}
+
+static int
+strmap_rec_cmp(const uint32_t *uid, const struct mail_index_strmap_rec *rec)
+{
+ return *uid < rec->uid ? -1 :
+ (*uid > rec->uid ? 1 : 0);
+}
+
+static int
+mail_index_strmap_write_append(struct mail_index_strmap_view *view)
+{
+ struct mail_index_strmap_read_context ctx;
+ const struct mail_index_strmap_rec *old_recs;
+ unsigned int i, old_count;
+ struct ostream *output;
+ uint32_t crc32, next_uid;
+ bool full_block;
+ int ret;
+
+ /* Check first if another process had written new records to the file.
+ If there are any, hopefully they're the same as what we would be
+ writing. There are two problematic cases when messages have been
+ expunged recently:
+
+ 1) The file contains UIDs that we don't have. This means the string
+ indexes won't be compatible anymore, so we'll have to renumber ours
+ to match the ones in the strmap file.
+
+ Currently we don't bother handling 1) case. If indexes don't match
+ what we have, we just don't write anything.
+
+ 2) We have UIDs that don't exist in the file. We can't simply skip
+ those records, because other records may have pointers to them using
+ different string indexes than we have. Even if we renumbered those,
+ future appends by other processes might cause the same problem (they
+ see the string for the first time and assign it a new index, but we
+ already have internally given it another index). So the only
+ sensible choice is to write nothing and hope that the message goes
+ away soon. */
+ next_uid = view->last_read_uid + 1;
+ (void)array_bsearch_insert_pos(&view->recs, &next_uid,
+ strmap_rec_cmp, &i);
+
+ old_recs = array_get(&view->recs, &old_count);
+ if (i < old_count) {
+ while (i > 0 && old_recs[i-1].uid == old_recs[i].uid)
+ i--;
+ }
+
+ i_stream_sync(view->strmap->input);
+ i_stream_seek(view->strmap->input, view->last_read_block_offset);
+ full_block = TRUE; ret = 0;
+ while (i < old_count &&
+ (ret = strmap_read_block_init(view, &ctx)) > 0) {
+ while ((ret = strmap_read_block_next(&ctx, &crc32)) > 0) {
+ if (ctx.rec.uid != old_recs[i].uid ||
+ ctx.rec.str_idx != old_recs[i].str_idx) {
+ /* mismatch */
+ if (ctx.rec.uid > old_recs[i].uid) {
+ /* 1) case */
+ ctx.lost_expunged_uid = ctx.rec.uid;
+ } else if (ctx.rec.uid < old_recs[i].uid) {
+ /* 2) case */
+ ctx.lost_expunged_uid = old_recs[i].uid;
+ } else {
+ /* string index mismatch,
+ shouldn't happen */
+ }
+ ret = -1;
+ break;
+ }
+ if (++i == old_count) {
+ full_block = FALSE;
+ break;
+ }
+ }
+ if (strmap_read_block_deinit(&ctx, ret, full_block) < 0) {
+ ret = -1;
+ break;
+ }
+ }
+ if (ret < 0)
+ return -1;
+ if (i == old_count) {
+ /* nothing new to write */
+ return 0;
+ }
+ i_assert(full_block);
+ i_assert(old_recs[i].uid > view->last_read_uid);
+
+ /* write the new records */
+ output = o_stream_create_fd(view->strmap->fd, 0);
+ (void)o_stream_seek(output, view->last_read_block_offset);
+ o_stream_cork(output);
+ mail_index_strmap_write_block(view, output, i,
+ view->last_read_uid + 1);
+ if (o_stream_finish(output) < 0) {
+ mail_index_strmap_set_syscall_error(view->strmap, "write()");
+ ret = -1;
+ }
+ o_stream_destroy(&output);
+ return ret;
+}
+
+static int mail_index_strmap_write(struct mail_index_strmap_view *view)
+{
+ int ret;
+
+ /* FIXME: this renumbering doesn't work well when running for a long
+ time since records aren't removed from hash often enough */
+ if (STRIDX_MUST_RENUMBER(view->next_str_idx - 1,
+ hash2_count(view->hash))) {
+ mail_index_strmap_view_renumber(view);
+ if (!MAIL_INDEX_IS_IN_MEMORY(view->strmap->index)) {
+ if (mail_index_strmap_recreate(view) < 0) {
+ view->desynced = TRUE;
+ return -1;
+ }
+ }
+ return 0;
+ }
+
+ if (MAIL_INDEX_IS_IN_MEMORY(view->strmap->index) || view->desynced)
+ return 0;
+
+ if (view->strmap->fd == -1) {
+ /* initial file creation */
+ if (mail_index_strmap_recreate(view) < 0) {
+ view->desynced = TRUE;
+ return -1;
+ }
+ return 0;
+ }
+
+ /* append the new records to the strmap file */
+ if (mail_index_strmap_lock(view->strmap) <= 0) {
+ /* timeout / error */
+ ret = -1;
+ } else if (mail_index_strmap_need_reopen(view->strmap)) {
+ /* the file was already recreated - leave the syncing as it is
+ for now and let the next sync re-read the file. */
+ ret = 0;
+ } else {
+ ret = mail_index_strmap_write_append(view);
+ }
+ mail_index_strmap_unlock(view->strmap);
+ if (ret < 0)
+ view->desynced = TRUE;
+ return ret;
+}
+
+void mail_index_strmap_view_sync_commit(struct mail_index_strmap_view_sync **_sync)
+{
+ struct mail_index_strmap_view_sync *sync = *_sync;
+ struct mail_index_strmap_view *view = sync->view;
+
+ *_sync = NULL;
+ i_free(sync);
+
+ (void)mail_index_strmap_write(view);
+ mail_index_strmap_zero_terminate(view);
+
+ /* zero-terminate the records array */
+ array_append_zero(&view->recs);
+ array_pop_back(&view->recs);
+}
+
+void mail_index_strmap_view_sync_rollback(struct mail_index_strmap_view_sync **_sync)
+{
+ struct mail_index_strmap_view_sync *sync = *_sync;
+
+ *_sync = NULL;
+
+ mail_index_strmap_view_reset(sync->view);
+ mail_index_strmap_zero_terminate(sync->view);
+ i_free(sync);
+}