Mercurial > dovecot > core-2.2
changeset 12641:ad002fdc6a6c
lib-storage: Initial commit for rewritten mailbox list indexes code.
They're only enabled with mailbox_list_index=yes setting (default is no).
They can also get out of sync pretty easily currently.
author | Timo Sirainen <tss@iki.fi> |
---|---|
date | Tue, 08 Feb 2011 01:35:45 +0200 |
parents | 19ffd1889f40 |
children | 46dc31d8769f |
files | src/lib-storage/list/Makefile.am src/lib-storage/list/index-mailbox-list-status.c src/lib-storage/list/index-mailbox-list-sync.c src/lib-storage/list/index-mailbox-list.c src/lib-storage/list/index-mailbox-list.h src/lib-storage/mail-storage-settings.c src/lib-storage/mail-storage-settings.h src/lib-storage/mail-storage.c |
diffstat | 8 files changed, 890 insertions(+), 789 deletions(-) [+] |
line wrap: on
line diff
--- a/src/lib-storage/list/Makefile.am Tue Feb 08 00:08:38 2011 +0200 +++ b/src/lib-storage/list/Makefile.am Tue Feb 08 01:35:45 2011 +0200 @@ -10,7 +10,7 @@ libstorage_list_la_SOURCES = \ index-mailbox-list.c \ - index-mailbox-list-sync.c \ + index-mailbox-list-status.c \ mailbox-list-delete.c \ mailbox-list-fs.c \ mailbox-list-fs-flags.c \
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lib-storage/list/index-mailbox-list-status.c Tue Feb 08 01:35:45 2011 +0200 @@ -0,0 +1,294 @@ +/* Copyright (c) 2006-2011 Dovecot authors, see the included COPYING file */ + +#include "lib.h" +#include "array.h" +#include "mail-storage-private.h" +#include "index-mailbox-list.h" + +#define INDEX_LIST_STORAGE_CONTEXT(obj) \ + MODULE_CONTEXT(obj, index_list_storage_module) + +#define CACHED_STATUS_ITEMS \ + (STATUS_MESSAGES | STATUS_UNSEEN | STATUS_RECENT | \ + STATUS_UIDNEXT | STATUS_UIDVALIDITY | STATUS_HIGHESTMODSEQ) + +struct index_list_mailbox { + union mailbox_module_context module_ctx; +}; + +static MODULE_CONTEXT_DEFINE_INIT(index_list_storage_module, + &mail_storage_module_register); + +static int +index_list_mailbox_open_view(struct mailbox *box, + struct mail_index_view **view_r, uint32_t *seq_r) +{ + struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(box->list); + struct index_mailbox_node *node; + struct mail_index_view *view; + uint32_t seq; + + if (index_mailbox_list_refresh(box->list) < 0) + return -1; + + node = index_mailbox_list_lookup(box->list, box->vname); + if (node == NULL) { + /* mailbox not found */ + return 0; + } + + view = mail_index_view_open(ilist->index); + if (!mail_index_lookup_seq(view, node->uid, &seq)) { + /* our in-memory tree is out of sync */ + ilist->force_refresh = TRUE; + mail_index_view_close(&view); + return 0; + } + + *view_r = view; + *seq_r = seq; + return 1; +} + +static bool +index_list_get_view_status(struct mailbox *box, struct mail_index_view *view, + uint32_t seq, enum mailbox_status_items items, + struct mailbox_status *status_r, + uint8_t *mailbox_guid) +{ + struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(box->list); + const void *data; + bool expunged; + bool ret = TRUE; + + if ((items & STATUS_UIDVALIDITY) != 0 || mailbox_guid != NULL) { + const struct mailbox_list_index_record *rec; + + mail_index_lookup_ext(view, seq, ilist->ext_id, + &data, &expunged); + rec = data; + if (rec == NULL || rec->uid_validity == 0) + ret = FALSE; + else { + status_r->uidvalidity = rec->uid_validity; + memcpy(mailbox_guid, rec->guid, MAIL_GUID_128_SIZE); + } + } + + if ((items & (STATUS_MESSAGES | STATUS_UNSEEN | + STATUS_RECENT | STATUS_UIDNEXT)) != 0) { + const struct mailbox_list_index_msgs_record *rec; + + mail_index_lookup_ext(view, seq, ilist->msgs_ext_id, + &data, &expunged); + rec = data; + if (rec == NULL || rec->uidnext == 0) + ret = FALSE; + else { + status_r->messages = rec->messages; + status_r->unseen = rec->unseen; + status_r->recent = rec->recent; + status_r->uidnext = rec->uidnext; + } + } + if ((items & STATUS_HIGHESTMODSEQ) != 0) { + const uint64_t *rec; + + mail_index_lookup_ext(view, seq, ilist->hmodseq_ext_id, + &data, &expunged); + rec = data; + if (rec == NULL || *rec == 0) + ret = FALSE; + else + status_r->highest_modseq = *rec; + } + return ret; +} + +static int +index_list_get_cached_status(struct mailbox *box, + enum mailbox_status_items items, + struct mailbox_status *status_r) +{ + struct mail_index_view *view; + uint32_t seq; + int ret; + + memset(status_r, 0, sizeof(*status_r)); + + ret = index_list_mailbox_open_view(box, &view, &seq); + if (ret <= 0) + return ret; + + ret = index_list_get_view_status(box, view, seq, items, status_r, NULL); + mail_index_view_close(&view); + return ret; +} + +static int +index_list_get_status(struct mailbox *box, enum mailbox_status_items items, + struct mailbox_status *status_r) +{ + struct index_list_mailbox *ibox = INDEX_LIST_STORAGE_CONTEXT(box); + + if ((items & ~CACHED_STATUS_ITEMS) == 0 && !box->opened) { + if (index_list_get_cached_status(box, items, status_r) > 0) + return 0; + /* nonsynced / error, fallback to doing it the slow way */ + } + return ibox->module_ctx.super.get_status(box, items, status_r); +} + +static int +index_list_update(struct mailbox *box, struct mail_index_view *view, + uint32_t seq, const struct mailbox_status *status) +{ + struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(box->list); + struct mail_index_transaction *trans; + struct mail_index_transaction_commit_result result; + struct mailbox_metadata metadata; + struct mailbox_status old_status; + uint8_t mailbox_guid[MAIL_GUID_128_SIZE]; + bool rec_changed, msgs_changed, hmodseq_changed; + + if (mailbox_get_metadata(box, MAILBOX_METADATA_GUID, &metadata) < 0) + memset(&metadata, 0, sizeof(metadata)); + + memset(&old_status, 0, sizeof(old_status)); + (void)index_list_get_view_status(box, view, seq, CACHED_STATUS_ITEMS, + &old_status, mailbox_guid); + + rec_changed = old_status.uidvalidity != status->uidvalidity || + memcmp(metadata.guid, mailbox_guid, sizeof(metadata.guid)) == 0; + msgs_changed = old_status.messages != status->messages || + old_status.unseen != status->unseen || + old_status.recent != status->recent || + old_status.uidnext != status->uidnext; + /* update highest-modseq only if they're ever been used */ + if (old_status.highest_modseq == status->highest_modseq) { + hmodseq_changed = FALSE; + } else if ((box->enabled_features & MAILBOX_FEATURE_CONDSTORE) != 0 || + old_status.highest_modseq != 0) { + hmodseq_changed = TRUE; + } else { + const void *data; + bool expunged; + + mail_index_lookup_ext(view, seq, ilist->hmodseq_ext_id, + &data, &expunged); + hmodseq_changed = data != NULL; + } + + hmodseq_changed = old_status.highest_modseq != status->highest_modseq && + (old_status.highest_modseq != 0 || + (box->enabled_features & MAILBOX_FEATURE_CONDSTORE) != 0); + + if (!rec_changed && !msgs_changed && !hmodseq_changed) + return 0; + + trans = mail_index_transaction_begin(view, + MAIL_INDEX_TRANSACTION_FLAG_EXTERNAL); + + if (rec_changed) { + struct mailbox_list_index_record rec; + const void *old_data; + bool expunged; + + mail_index_lookup_ext(view, seq, ilist->ext_id, + &old_data, &expunged); + i_assert(old_data != NULL); + memcpy(&rec, old_data, sizeof(rec)); + + rec.uid_validity = status->uidvalidity; + memcpy(rec.guid, mailbox_guid, sizeof(rec.guid)); + mail_index_update_ext(trans, seq, ilist->ext_id, &rec, NULL); + } + + if (msgs_changed) { + struct mailbox_list_index_msgs_record msgs; + + memset(&msgs, 0, sizeof(msgs)); + msgs.messages = status->messages; + msgs.unseen = status->unseen; + msgs.recent = status->recent; + msgs.uidnext = status->uidnext; + + mail_index_update_ext(trans, seq, ilist->msgs_ext_id, + &msgs, NULL); + } + if (hmodseq_changed) { + mail_index_update_ext(trans, seq, ilist->hmodseq_ext_id, + &status->highest_modseq, NULL); + } + + return mail_index_transaction_commit_full(&trans, &result); +} + +static int index_list_sync_deinit(struct mailbox_sync_context *ctx, + struct mailbox_sync_status *status_r) +{ + struct mailbox *box = ctx->box; + struct index_list_mailbox *ibox = INDEX_LIST_STORAGE_CONTEXT(box); + struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(box->list); + struct index_mailbox_node *node; + struct mail_index_view *view; + struct mailbox_status status; + uint32_t seq; + + if (ibox->module_ctx.super.sync_deinit(ctx, status_r) < 0) + return -1; + ctx = NULL; + + /* update mailbox list index */ + node = index_mailbox_list_lookup(box->list, box->vname); + if (node == NULL) + ilist->force_refresh = TRUE; + else { + view = mail_index_view_open(ilist->index); + if (mail_index_lookup_seq(view, node->uid, &seq)) { + mailbox_get_open_status(box, CACHED_STATUS_ITEMS, + &status); + (void)index_list_update(box, view, seq, &status); + } + mail_index_view_close(&view); + } + return 0; +} + +static void index_list_mail_mailbox_allocated(struct mailbox *box) +{ + struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(box->list); + struct index_list_mailbox *ibox; + + if (ilist == NULL) + return; + + ibox = p_new(box->pool, struct index_list_mailbox, 1); + ibox->module_ctx.super = box->v; + box->v.get_status = index_list_get_status; + box->v.sync_deinit = index_list_sync_deinit; + + MODULE_CONTEXT_SET(box, index_list_storage_module, ibox); +} + +void index_mailbox_list_status_init_list(struct mailbox_list *list) +{ + struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(list); + + ilist->msgs_ext_id = mail_index_ext_register(ilist->index, "msgs", 0, + sizeof(struct mailbox_list_index_msgs_record), + sizeof(uint32_t)); + + ilist->hmodseq_ext_id = + mail_index_ext_register(ilist->index, "msgs", 0, + sizeof(uint64_t), sizeof(uint64_t)); +} + +static struct mail_storage_hooks index_mailbox_list_status_hooks = { + .mailbox_allocated = index_list_mail_mailbox_allocated +}; + +void index_mailbox_list_status_init(void) +{ + mail_storage_hooks_add_internal(&index_mailbox_list_status_hooks); +}
--- a/src/lib-storage/list/index-mailbox-list-sync.c Tue Feb 08 00:08:38 2011 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,391 +0,0 @@ -/* Copyright (c) 2006-2010 Dovecot authors, see the included COPYING file */ - -#include "lib.h" -#include "ioloop.h" -#include "array.h" -#include "index-storage.h" -#include "mailbox-list-index.h" -#include "index-mailbox-list.h" -#include "maildir/maildir-sync.h" - -#include <sys/stat.h> - -#define INDEX_LIST_STORAGE_CONTEXT(obj) \ - MODULE_CONTEXT(obj, index_list_storage_module) - -#define CACHED_STATUS_ITEMS \ - (STATUS_MESSAGES | STATUS_UNSEEN | STATUS_RECENT | \ - STATUS_UIDNEXT | STATUS_UIDVALIDITY) - -struct index_list_mailbox { - union mailbox_module_context module_ctx; - - uint32_t log_seq; - uoff_t log_offset; -}; - -struct index_list_map { - const char *name; - unsigned int eid_offset; - unsigned int status_offset; -}; -#undef DEF -#define DEF(a, b, c) \ - { a, offsetof(struct index_mailbox_list, b), \ - offsetof(struct mailbox_status, c) } -static struct index_list_map index_list_map[] = { - DEF("msgs", eid_messages, messages), - DEF("unseen", eid_unseen, unseen), - DEF("recent", eid_recent, recent), - DEF("uid_validity", eid_uid_validity, uidvalidity), - DEF("uidnext", eid_uidnext, uidnext), - { NULL, 0, 0 } -}; - -static MODULE_CONTEXT_DEFINE_INIT(index_list_storage_module, - &mail_storage_module_register); - -static void index_list_box_close(struct mailbox *box) -{ - struct index_list_mailbox *ibox = INDEX_LIST_STORAGE_CONTEXT(box); - - ibox->module_ctx.super.close(box); -} - -static int index_list_update_mail_index(struct index_mailbox_list *ilist, - struct mailbox *box) -{ - struct index_list_mailbox *ibox = INDEX_LIST_STORAGE_CONTEXT(box); - struct mail_index_sync_ctx *mail_sync_ctx; - struct mail_index_view *view; - struct mail_index_transaction *trans; - struct mail_index_sync_rec sync_rec; - int ret; - - if (ibox->log_seq == 0) - return 0; - - ret = mail_index_sync_begin_to(ilist->mail_index, - &mail_sync_ctx, &view, &trans, - ibox->log_seq, ibox->log_offset, 0); - if (ret <= 0) - return ret; - - /* we should have only external transactions in here, for which we - don't need to do anything but write them to the index */ - while (mail_index_sync_next(mail_sync_ctx, &sync_rec)) - ; - - return mail_index_sync_commit(&mail_sync_ctx); -} - -static int -index_list_mailbox_open_unchanged_view(struct mailbox *box, - struct mail_index_view **view_r, - uint32_t *seq_r) -{ - struct index_mailbox_list *ilist; - struct mail_index_view *view; - uint32_t uid, seq; - int ret; - - ilist = INDEX_LIST_CONTEXT(box->list); - - if (ilist == NULL) { - /* indexing disabled */ - return 0; - } - - ret = mailbox_list_index_lookup(ilist->list_sync_view, box->name, &uid); - if (ret <= 0) - return ret; - - /* make sure we're synced */ - if (index_list_update_mail_index(ilist, box) < 0) - return -1; - - /* found from list index. lookup the mail index record for it */ - view = mail_index_view_open(ilist->mail_index); - if (!mail_index_lookup_seq(view, uid, &seq)) { - mail_index_view_close(&view); - return 0; - } - - T_BEGIN { - ret = box->v.list_index_has_changed(box, view, seq); - } T_END; - if (ret != 0) { - /* error / mailbox has changed. we'll need to sync it. */ - mail_index_view_close(&view); - return ret < 0 ? -1 : 0; - } - - *view_r = view; - *seq_r = seq; - return 1; -} - -static int -index_list_get_cached_status(struct mailbox *box, struct mailbox_status *status) -{ - struct index_mailbox_list *ilist; - struct mail_index_view *view; - const void *data; - uint32_t seq, *ext_id_p, *counter_p; - unsigned int i; - bool expunged; - int ret; - - memset(status, 0, sizeof(*status)); - - ret = index_list_mailbox_open_unchanged_view(box, &view, &seq); - if (ret <= 0) - return ret; - - ilist = INDEX_LIST_CONTEXT(box->list); - for (i = 0; index_list_map[i].name != NULL; i++) { - ext_id_p = PTR_OFFSET(ilist, index_list_map[i].eid_offset); - mail_index_lookup_ext(view, seq, *ext_id_p, &data, &expunged); - if (expunged || data == NULL) { - ret = 0; - break; - } - - counter_p = PTR_OFFSET(status, index_list_map[i].status_offset); - *counter_p = *(const uint32_t *)data; - } - - mail_index_view_close(&view); - return ret; -} - -static int -index_list_get_status(struct mailbox *box, enum mailbox_status_items items, - struct mailbox_status *status) -{ - struct index_list_mailbox *ibox = INDEX_LIST_STORAGE_CONTEXT(box); - - if ((items & ~CACHED_STATUS_ITEMS) == 0) { - if (index_list_get_cached_status(box, status) > 0) - return 0; - /* nonsynced / error, fallback to doing it the slow way */ - } - - return ibox->module_ctx.super.get_status(box, items, status); -} - -static int index_list_lookup_or_create(struct index_mailbox_list *ilist, - struct mailbox *box, uint32_t *uid_r) -{ - struct mailbox_list_index_sync_ctx *sync_ctx; - int ret; - - ret = mailbox_list_index_lookup(ilist->list_sync_view, - box->name, uid_r); - if (ret > 0) { - /* we'll need the mailbox synced since we're updating its - contents based on what it already contains */ - if (index_list_update_mail_index(ilist, box) < 0) - return -1; - return 1; - } else if (ret < 0) - return -1; - - /* create the mailbox by doing a partial sync with the mailbox name - as the sync root path */ - if (mailbox_list_index_sync_init(ilist->list_index, box->name, - MAILBOX_LIST_SYNC_FLAG_PARTIAL, - &sync_ctx) < 0) - return -1; - if (mailbox_list_index_sync_commit(&sync_ctx) < 0) - return -1; - - ret = mailbox_list_index_lookup(ilist->list_sync_view, - box->name, uid_r); - if (ret != 0) - return ret < 0 ? -1 : 0; - - mail_storage_set_critical(box->storage, - "mailbox index: Created mailbox %s not found", box->name); - return -1; -} - -static int -index_list_update(struct index_mailbox_list *ilist, struct mailbox *box, - struct mail_index_view *view, uint32_t seq, - const struct mailbox_status *status) -{ - struct index_list_mailbox *ibox = INDEX_LIST_STORAGE_CONTEXT(box); - struct mail_index_transaction *trans; - struct mail_index_transaction_commit_result result; - const void *data; - const uint32_t *counter_p; - uint32_t *ext_id_p; - unsigned int i; - bool expunged; - int ret = 0; - - trans = mail_index_transaction_begin(view, - MAIL_INDEX_TRANSACTION_FLAG_EXTERNAL); - - /* update counters */ - for (i = 0; index_list_map[i].name != NULL; i++) { - ext_id_p = PTR_OFFSET(ilist, index_list_map[i].eid_offset); - mail_index_lookup_ext(view, seq, *ext_id_p, &data, &expunged); - if (expunged) { - ret = -1; - break; - } - - counter_p = CONST_PTR_OFFSET(status, - index_list_map[i].status_offset); - if (data == NULL || - *(const uint32_t *)data != *counter_p) { - mail_index_update_ext(trans, seq, *ext_id_p, - counter_p, NULL); - } - } - - if (box->v.list_index_update_sync(box, trans, seq) < 0) - ret = -1; - if (ret < 0) { - mail_index_transaction_rollback(&trans); - return -1; - } - - if (mail_index_transaction_commit_full(&trans, &result) < 0) - return -1; - - ibox->log_seq = result.log_file_seq; - ibox->log_offset = result.log_file_offset; - return 0; -} - -static struct mailbox_sync_context * -index_list_sync_init(struct mailbox *box, enum mailbox_sync_flags flags) -{ - struct index_list_mailbox *ibox = INDEX_LIST_STORAGE_CONTEXT(box); - struct mailbox_sync_context *ctx; - - /* clear any cached log seq/offset */ - ibox->log_seq = (uint32_t)-1; - ibox->log_offset = 0; - - if (!box->opened) { - /* check using the mailbox list index if the mailbox has - changed. if not, we don't need to open the mailbox yet. */ - struct mail_index_view *view; - uint32_t seq; - int ret; - - ret = index_list_mailbox_open_unchanged_view(box, &view, &seq); - if (ret > 0) { - ctx = i_new(struct mailbox_sync_context, 1); - ctx->box = box; - mail_index_view_close(&view); - - /* no changes, so don't bother checking again before - next sync */ - ibox->log_seq = 0; - return ctx; - } - } - - return ibox->module_ctx.super.sync_init(box, flags); -} - -static bool index_list_sync_next(struct mailbox_sync_context *ctx, - struct mailbox_sync_rec *sync_rec_r) -{ - struct index_list_mailbox *ibox = INDEX_LIST_STORAGE_CONTEXT(ctx->box); - - if (!ctx->box->opened) - return FALSE; - - return ibox->module_ctx.super.sync_next(ctx, sync_rec_r); -} - -static int index_list_sync_deinit(struct mailbox_sync_context *ctx, - struct mailbox_sync_status *status_r) -{ - struct mailbox *box = ctx->box; - struct index_list_mailbox *ibox = INDEX_LIST_STORAGE_CONTEXT(box); - struct index_mailbox_list *ilist; - struct mail_index_view *view; - struct mailbox_status status; - uint32_t uid, seq; - - if (!box->opened) { - /* nothing synced. just return the status. */ - i_free(ctx); - return 0; - } - - ilist = INDEX_LIST_CONTEXT(box->list); - - if (ilist == NULL) { - /* indexing disabled */ - return ibox->module_ctx.super.sync_deinit(ctx, status_r); - } - - if (ibox->module_ctx.super.sync_deinit(ctx, status_r) < 0) - return -1; - ctx = NULL; - - /* sync mailbox list index */ - if (index_list_lookup_or_create(ilist, box, &uid) < 0) { - /* just ignore the error */ - return 0; - } - - view = mail_index_view_open(ilist->mail_index); - if (mail_index_lookup_seq(view, uid, &seq)) { - mailbox_get_open_status(box, CACHED_STATUS_ITEMS, &status); - (void)index_list_update(ilist, box, view, seq, &status); - } - mail_index_view_close(&view); - return 0; -} - -static void index_list_mail_mailbox_allocated(struct mailbox *box) -{ - struct index_mailbox_list *ilist = - INDEX_LIST_CONTEXT(box->list); - struct index_list_mailbox *ibox; - - if (ilist == NULL) - return; - - ibox = p_new(box->pool, struct index_list_mailbox, 1); - ibox->module_ctx.super = box->v; - box->v.close = index_list_box_close; - box->v.get_status = index_list_get_status; - box->v.sync_init = index_list_sync_init; - box->v.sync_next = index_list_sync_next; - box->v.sync_deinit = index_list_sync_deinit; - - MODULE_CONTEXT_SET(box, index_list_storage_module, ibox); -} - -void index_mailbox_list_sync_init_list(struct mailbox_list *list) -{ - struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(list); - unsigned int i; - uint32_t *ext_id_p; - - for (i = 0; index_list_map[i].name != NULL; i++) { - ext_id_p = PTR_OFFSET(ilist, index_list_map[i].eid_offset); - *ext_id_p = mail_index_ext_register(ilist->mail_index, - index_list_map[i].name, 0, - sizeof(uint32_t), sizeof(uint32_t)); - } -} - -static struct mail_storage_hooks index_mailbox_list_sync_hooks = { - .mailbox_allocated = index_list_mail_mailbox_allocated -}; - -void index_mailbox_list_sync_init(void) -{ - mail_storage_hooks_add_internal(&index_mailbox_list_sync_hooks); -}
--- a/src/lib-storage/list/index-mailbox-list.c Tue Feb 08 00:08:38 2011 +0200 +++ b/src/lib-storage/list/index-mailbox-list.c Tue Feb 08 01:35:45 2011 +0200 @@ -1,270 +1,438 @@ -/* Copyright (c) 2006-2010 Dovecot authors, see the included COPYING file */ +/* Copyright (c) 2006-2011 Dovecot authors, see the included COPYING file */ #include "lib.h" #include "ioloop.h" -#include "array.h" -#include "file-lock.h" +#include "str.h" +#include "hash.h" #include "imap-match.h" #include "mail-index.h" -#include "mail-storage.h" #include "mail-storage-hooks.h" -#include "mailbox-tree.h" #include "mailbox-list-subscriptions.h" -#include "mailbox-list-index.h" #include "index-mailbox-list.h" -#include <stdlib.h> -#include <time.h> -#include <sys/stat.h> +struct index_mailbox_list_sync_context { + struct index_mailbox_list *ilist; + char sep[2]; + uint32_t next_uid; -/* min 2 seconds */ -#define MAILBOX_LIST_SYNC_SECS 2 + struct mail_index_sync_ctx *sync_ctx; + struct mail_index_view *view; + struct mail_index_transaction *trans; +}; struct index_mailbox_list_module index_mailbox_list_module = MODULE_CONTEXT_INIT(&mailbox_list_module_register); -static enum mailbox_info_flags -index_mailbox_list_index_flags_translate(enum mailbox_list_index_flags flags) +static int index_mailbox_list_read(struct index_mailbox_list *ilist, + bool force); + +static void index_mailbox_list_reset(struct index_mailbox_list *ilist) +{ + hash_table_clear(ilist->mailbox_names, FALSE); + hash_table_clear(ilist->mailbox_hash, FALSE); + p_clear(ilist->mailbox_pool); + ilist->mailbox_tree = NULL; + ilist->highest_name_id = 0; + ilist->sync_log_file_seq = 0; + ilist->sync_log_file_offset = 0; +} + +static struct index_mailbox_node * +index_mailbox_node_find_sibling(struct index_mailbox_node *node, + const char *name) { - enum mailbox_info_flags info_flags = 0; + while (node != NULL) { + if (strcmp(node->name, name) == 0) + return node; + node = node->next; + } + return NULL; +} + +static void +index_mailbox_node_add_to_index(struct index_mailbox_list_sync_context *ctx, + struct index_mailbox_node *node, + uint32_t *name_id_r, uint32_t *seq_r) +{ + struct mailbox_list_index_record irec; + uint32_t seq; + + memset(&irec, 0, sizeof(irec)); + irec.name_id = node->name_id; + if (node->parent != NULL) + irec.parent_uid = node->parent->uid; + + mail_index_append(ctx->trans, node->uid, &seq); + mail_index_update_flags(ctx->trans, seq, MODIFY_REPLACE, + (enum mail_flags)MAILBOX_LIST_INDEX_FLAG_NONEXISTENT); + mail_index_update_ext(ctx->trans, seq, ctx->ilist->ext_id, &irec, NULL); + + *name_id_r = irec.name_id; + *seq_r = seq; +} - if ((flags & MAILBOX_LIST_INDEX_FLAG_CHILDREN) != 0) - info_flags |= MAILBOX_CHILDREN; - if ((flags & MAILBOX_LIST_INDEX_FLAG_NOCHILDREN) != 0) - info_flags |= MAILBOX_NOCHILDREN; +static struct index_mailbox_node * +index_mailbox_node_add(struct index_mailbox_list_sync_context *ctx, + struct index_mailbox_node *parent, const char *name, + uint32_t *seq_r) +{ + struct index_mailbox_node *node; + uint32_t name_id; + char *dup_name; + + node = p_new(ctx->ilist->mailbox_pool, struct index_mailbox_node, 1); + node->flags = MAILBOX_LIST_INDEX_FLAG_NONEXISTENT; + node->name = dup_name = p_strdup(ctx->ilist->mailbox_pool, name); + node->name_id = ++ctx->ilist->highest_name_id; + node->uid = ctx->next_uid++; + + if (parent != NULL) { + node->parent = parent; + node->next = parent->children; + parent->children = node; + } else { + node->next = ctx->ilist->mailbox_tree; + ctx->ilist->mailbox_tree = node; + } - if ((flags & MAILBOX_LIST_INDEX_FLAG_NONEXISTENT) != 0) - info_flags |= MAILBOX_NONEXISTENT; - if ((flags & MAILBOX_LIST_INDEX_FLAG_NOSELECT) != 0) - info_flags |= MAILBOX_NOSELECT; - return info_flags; + index_mailbox_node_add_to_index(ctx, node, &name_id, seq_r); + hash_table_insert(ctx->ilist->mailbox_hash, + POINTER_CAST(node->uid), node); + hash_table_insert(ctx->ilist->mailbox_names, + POINTER_CAST(name_id), dup_name); + return node; +} + +struct index_mailbox_node * +index_mailbox_list_lookup(struct mailbox_list *list, const char *vname) +{ + struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(list); + struct index_mailbox_node *node; + + T_BEGIN { + const char *const *path; + unsigned int i; + char sep[2]; + + sep[0] = mail_namespace_get_sep(list->ns); sep[1] = '\0'; + path = t_strsplit(vname, sep); + node = ilist->mailbox_tree; + for (i = 0;; i++) { + node = index_mailbox_node_find_sibling(node, path[i]); + if (node == NULL || path[i+1] == NULL) + break; + node = node->children; + } + } T_END; + + return node; } -static enum mailbox_list_index_flags -index_mailbox_list_info_flags_translate(enum mailbox_info_flags info_flags) +static uint32_t +index_mailbox_list_sync_name(struct index_mailbox_list_sync_context *ctx, + const char *name, + enum mailbox_list_index_flags flags) { - enum mailbox_list_index_flags flags = 0; + const char *const *path; + struct index_mailbox_node *node, *parent; + unsigned int i; + uint32_t seq = 0; + + path = t_strsplit(name, ctx->sep); + node = ctx->ilist->mailbox_tree; parent = NULL; + for (i = 0; path[i] != NULL; i++) { + node = index_mailbox_node_find_sibling(node, path[i]); + if (node == NULL) + break; + parent = node; + node = node->children; + } - if ((info_flags & MAILBOX_CHILDREN) != 0) - flags |= MAILBOX_LIST_INDEX_FLAG_CHILDREN; - else if ((info_flags & MAILBOX_NOCHILDREN) != 0) - flags |= MAILBOX_LIST_INDEX_FLAG_NOCHILDREN; + node = parent; + if (path[i] == NULL) { + if (!mail_index_lookup_seq(ctx->view, node->uid, &seq)) + i_panic("mailbox list index: lost uid=%u", node->uid); + } else { + for (; path[i] != NULL; i++) + node = index_mailbox_node_add(ctx, node, path[i], &seq); + } + + node->flags = flags; + return seq; +} - if ((info_flags & MAILBOX_NONEXISTENT) != 0) - flags |= MAILBOX_LIST_INDEX_FLAG_NONEXISTENT; - if ((info_flags & MAILBOX_NOSELECT) != 0) - flags |= MAILBOX_LIST_INDEX_FLAG_NOSELECT; - return flags; +static void get_existing_name_ids(ARRAY_TYPE(uint32_t) *ids, + const struct index_mailbox_node *node) +{ + for (; node != NULL; node = node->next) { + if (node->children != NULL) + get_existing_name_ids(ids, node->children); + array_append(ids, &node->name_id, 1); + } +} + +static int uint32_cmp(const uint32_t *p1, const uint32_t *p2) +{ + return *p1 < *p2 ? -1 : + (*p1 > *p2 ? 1 : 0); } -static int -index_mailbox_list_is_synced(struct index_mailbox_list_iterate_context *ctx) +static void +index_mailbox_list_sync_names(struct index_mailbox_list_sync_context *ctx) { - const struct mail_index_header *hdr; - struct stat st; - const char *path = ctx->ctx.list->set.root_dir; + struct index_mailbox_list *ilist = ctx->ilist; + ARRAY_TYPE(uint32_t) existing_name_ids; + buffer_t *buf; + const void *ext_data; + size_t ext_size; + const char *name; + const uint32_t *id_p; + uint32_t prev_id = 0; + + t_array_init(&existing_name_ids, 64); + get_existing_name_ids(&existing_name_ids, ilist->mailbox_tree); + array_sort(&existing_name_ids, uint32_cmp); + + buf = buffer_create_dynamic(pool_datastack_create(), 1024); + array_foreach(&existing_name_ids, id_p) { + if (*id_p != prev_id) { + buffer_append(buf, id_p, sizeof(*id_p)); + name = hash_table_lookup(ilist->mailbox_names, + POINTER_CAST(*id_p)); + buffer_append(buf, name, strlen(name) + 1); + prev_id = *id_p; + } + } + buffer_append_zero(buf, sizeof(*id_p)); - if (ctx->view == NULL) { - /* uid_validity changed */ - return 0; + mail_index_get_header_ext(ctx->view, ilist->ext_id, + &ext_data, &ext_size); + if (nearest_power(ext_size) != nearest_power(buf->used)) { + mail_index_ext_resize(ctx->trans, ilist->ext_id, + nearest_power(buf->used), + sizeof(struct mailbox_list_index_record), + sizeof(uint32_t)); } + mail_index_update_header_ext(ctx->trans, ilist->ext_id, + 0, buf->data, buf->used); +} - /* FIXME: single sync_stamp works only with maildir++ */ - if (stat(path, &st) < 0) { - mailbox_list_set_critical(ctx->ctx.list, - "stat(%s) failed: %m", path); +static int index_mailbox_list_sync(struct mailbox_list *list) +{ + struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(list); + struct index_mailbox_list_sync_context sync_ctx; + struct mailbox_list_iterate_context *iter; + const struct mail_index_header *hdr; + const struct mailbox_info *info; + const char *patterns[2]; + enum mailbox_list_index_flags flags; + uint32_t seq, orig_highest_name_id; + int ret = 0; + + index_mailbox_list_reset(ilist); + + memset(&sync_ctx, 0, sizeof(sync_ctx)); + sync_ctx.ilist = ilist; + sync_ctx.sep[0] = mail_namespace_get_sep(list->ns); + if (mail_index_sync_begin(ilist->index, &sync_ctx.sync_ctx, + &sync_ctx.view, &sync_ctx.trans, + MAIL_INDEX_SYNC_FLAG_AVOID_FLAG_UPDATES) < 0) + return -1; + + if (index_mailbox_list_read(ilist, TRUE) < 0) { + mail_index_sync_rollback(&sync_ctx.sync_ctx); return -1; } - /* - if mtime is older than 2 secs, we set the first bit on - if mtime is 0-2 secs old, we set the first bit off. - - this way we'll always do a resync later when syncing a recently - changed directory. if the directory changes while we're syncing it - we'll resync it again later. + orig_highest_name_id = ilist->highest_name_id; - this would work with 1 second difference if we didn't store the - dirtyness flag in the stamp's first bit. - */ - if (st.st_mtime < ioloop_time - MAILBOX_LIST_SYNC_SECS) - st.st_mtime |= 1; - else - st.st_mtime &= ~1; - - ctx->sync_stamp = st.st_mtime; - - hdr = mail_index_get_header(ctx->mail_view); - return hdr->sync_stamp == ctx->sync_stamp; -} + hdr = mail_index_get_header(sync_ctx.view); + sync_ctx.next_uid = hdr->next_uid; -static void pattern_parse(struct mailbox_list *list, const char *pattern, - const char **prefix_r, int *recurse_level_r) -{ - char sep = mailbox_list_get_hierarchy_sep(list); - const char *prefix_start, *prefix_end; - bool seen_wildcards = FALSE; - int recurse_level = 0; + if (hdr->uid_validity == 0) { + uint32_t uid_validity = ioloop_time; - prefix_start = prefix_end = pattern; - for (; *pattern != '\0'; pattern++) { - if (*pattern == '%') - seen_wildcards = TRUE; - else if (*pattern == '*') { - recurse_level = -1; - break; - } - - if (*pattern == sep) { - if (!seen_wildcards) - prefix_end = pattern; - recurse_level++; - } + mail_index_update_header(sync_ctx.trans, + offsetof(struct mail_index_header, uid_validity), + &uid_validity, sizeof(uid_validity), TRUE); } - *prefix_r = prefix_start == prefix_end ? "" : - t_strdup_until(prefix_start, prefix_end); - *recurse_level_r = recurse_level; -} - -static int -index_mailbox_list_sync(struct index_mailbox_list_iterate_context *ctx) -{ - struct mailbox_list *list = ctx->ctx.list; - struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(list); - struct mailbox_list_iterate_context *iter; - struct mailbox_list_index_sync_ctx *sync_ctx; - const struct mailbox_info *info; - enum mailbox_list_sync_flags sync_flags; - enum mailbox_list_index_flags flags; - const char *patterns[2]; - uint32_t seq; - int ret = 0; + patterns[0] = "*"; patterns[1] = NULL; + iter = ilist->module_ctx.super.iter_init(list, patterns, 0); + while ((info = ilist->module_ctx.super.iter_next(iter)) != NULL) { + flags = 0; + if ((info->flags & MAILBOX_NONEXISTENT) != 0) + flags |= MAILBOX_LIST_INDEX_FLAG_NONEXISTENT; + if ((info->flags & MAILBOX_NOSELECT) != 0) + flags |= MAILBOX_LIST_INDEX_FLAG_NOSELECT; + if ((info->flags & MAILBOX_NOINFERIORS) != 0) + flags |= MAILBOX_LIST_INDEX_FLAG_NOINFERIORS; - /* FIXME: this works nicely with maildir++, but not others */ - sync_flags = MAILBOX_LIST_SYNC_FLAG_RECURSIVE; - patterns[0] = "*"; patterns[1] = NULL; - - if (mailbox_list_index_sync_init(ilist->list_index, "", - sync_flags, &sync_ctx) < 0) - return -1; - - ctx->trans = mailbox_list_index_sync_get_transaction(sync_ctx); + T_BEGIN { + seq = index_mailbox_list_sync_name(&sync_ctx, + info->name, (enum mail_flags)flags); + } T_END; - iter = ilist->module_ctx.super. - iter_init(list, patterns, MAILBOX_LIST_ITER_RETURN_CHILDREN); - while ((info = ilist->module_ctx.super.iter_next(iter)) != NULL) { - if (mailbox_list_index_sync_more(sync_ctx, info->name, - &seq) < 0) { - ret = -1; - break; - } - - flags = index_mailbox_list_info_flags_translate(info->flags); - mail_index_update_flags(ctx->trans, seq, MODIFY_REPLACE, - (enum mail_flags)flags); + mail_index_update_flags(sync_ctx.trans, seq, + MODIFY_REPLACE, flags); } if (ilist->module_ctx.super.iter_deinit(iter) < 0) ret = -1; if (ret < 0) { - mailbox_list_index_sync_rollback(&sync_ctx); + mail_index_sync_rollback(&sync_ctx.sync_ctx); return -1; } - /* FIXME: single sync_stamp works only with maildir++ */ - mail_index_update_header(ctx->trans, - offsetof(struct mail_index_header, sync_stamp), - &ctx->sync_stamp, sizeof(ctx->sync_stamp), TRUE); - return mailbox_list_index_sync_commit(&sync_ctx); + if (orig_highest_name_id != ilist->highest_name_id) { + /* new names added */ + T_BEGIN { + index_mailbox_list_sync_names(&sync_ctx); + } T_END; + } + ilist->force_refresh = FALSE; + return mail_index_sync_commit(&sync_ctx.sync_ctx); +} + +static int index_mailbox_list_parse_header(struct index_mailbox_list *ilist, + struct mail_index_view *view) +{ + const void *data, *p; + size_t i, len, size; + uint32_t id, prev_id = 0; + char *name; + + mail_index_get_header_ext(view, ilist->ext_id, &data, &size); + for (i = 0; i < size; ) { + /* get id */ + if (i + sizeof(id) > size) + return -1; + memcpy(&id, CONST_PTR_OFFSET(data, i), sizeof(id)); + i += sizeof(id); + + if (id <= prev_id) { + /* allow extra space in the end as long as last id=0 */ + return id == 0 ? 0 : -1; + } + + /* get name */ + p = memchr(CONST_PTR_OFFSET(data, i), '\0', size-i); + if (p == NULL) + return -1; + len = (const char *)p - + (const char *)(CONST_PTR_OFFSET(data, i)); + + name = p_strndup(ilist->mailbox_pool, + CONST_PTR_OFFSET(data, i), len); + i += len + 1; + + /* add id => name to hash table */ + hash_table_insert(ilist->mailbox_names, POINTER_CAST(id), name); + ilist->highest_name_id = id; + } + i_assert(i == size); + return 0; } -static bool -index_mailbox_list_iter_init_try(struct index_mailbox_list_iterate_context *ctx, - const char *const *patterns) +static int index_mailbox_list_parse_records(struct index_mailbox_list *ilist, + struct mail_index_view *view) { - struct mailbox_list *list = ctx->ctx.list; - enum mailbox_list_iter_flags flags = ctx->ctx.flags; - struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(list); - const char *prefix, *cur_prefix, *const *tmp; - enum mailbox_list_iter_flags subs_flags; - int cur_recurse_level; - char sep; + struct index_mailbox_node *node; + const struct mail_index_record *rec; + const struct mailbox_list_index_record *irec; + const void *data; + bool expunged; + uint32_t seq, count; + + count = mail_index_view_get_messages_count(view); + for (seq = 1; seq <= count; seq++) { + node = p_new(ilist->mailbox_pool, struct index_mailbox_node, 1); + rec = mail_index_lookup(view, seq); + node->uid = rec->uid; + node->flags = rec->flags; + + mail_index_lookup_ext(view, seq, ilist->ext_id, + &data, &expunged); + if (data == NULL) + return -1; + irec = data; + + node->name_id = irec->name_id; + node->name = hash_table_lookup(ilist->mailbox_names, + POINTER_CAST(irec->name_id)); + if (node->name == NULL) + return -1; - subs_flags = MAILBOX_LIST_ITER_SELECT_SUBSCRIBED | - MAILBOX_LIST_ITER_RETURN_NO_FLAGS; - if ((flags & MAILBOX_LIST_ITER_RAW_LIST) != 0 || - (flags & (subs_flags | - MAILBOX_LIST_ITER_RETURN_CHILDREN)) == subs_flags) { - /* Ignore indexes completely */ - return FALSE; + if (irec->parent_uid != 0) { + node->parent = hash_table_lookup(ilist->mailbox_hash, + POINTER_CAST(irec->parent_uid)); + if (node->parent == NULL) + return -1; + node->next = node->parent->children; + node->parent->children = node; + } else { + node->next = ilist->mailbox_tree; + ilist->mailbox_tree = node; + } + hash_table_insert(ilist->mailbox_hash, + POINTER_CAST(node->uid), node); } + return 0; +} - sep = mailbox_list_get_hierarchy_sep(list); - ctx->glob = imap_match_init_multiple(default_pool, patterns, TRUE, sep); - if ((flags & (MAILBOX_LIST_ITER_SELECT_SUBSCRIBED | - MAILBOX_LIST_ITER_RETURN_SUBSCRIBED)) != 0) { - /* we'll need to know the subscriptions */ - ctx->subs_tree = mailbox_tree_init(sep); - /*if (mailbox_list_subscriptions_fill(&ctx->ctx, ctx->subs_tree, - ctx->glob, FALSE) < 0)*/ { - /* let the backend handle this failure */ - return FALSE; - } +static int index_mailbox_list_read(struct index_mailbox_list *ilist, bool force) +{ + struct mail_index_view *view; + const struct mail_index_header *hdr; + int ret; + + view = mail_index_view_open(ilist->index); + hdr = mail_index_get_header(view); + if (!force && + hdr->log_file_seq == ilist->sync_log_file_seq && + hdr->log_file_head_offset == ilist->sync_log_file_offset) { + /* nothing changed */ + mail_index_view_close(&view); + return 0; } - /* Refresh index before opening our view */ - if (mail_index_refresh(ilist->mail_index) < 0) - return FALSE; - - ctx->mail_view = mail_index_view_open(ilist->mail_index); - if (mailbox_list_index_view_init(ilist->list_index, - ctx->mail_view, &ctx->view) < 0) - ctx->view = NULL; + index_mailbox_list_reset(ilist); + ilist->sync_log_file_seq = hdr->log_file_seq; + ilist->sync_log_file_offset = hdr->log_file_head_offset; - /* FIXME: we could just do multiple lookups for different patterns */ - prefix = NULL; - for (tmp = patterns; *tmp != NULL; tmp++) { - pattern_parse(list, *tmp, &cur_prefix, &cur_recurse_level); - if (prefix != NULL && strcmp(prefix, cur_prefix) != 0) - prefix = ""; - if (cur_recurse_level > ctx->recurse_level || - cur_recurse_level == -1) - ctx->recurse_level = cur_recurse_level; + ret = index_mailbox_list_parse_header(ilist, view); + if (ret == 0) + ret = index_mailbox_list_parse_records(ilist, view); + mail_index_view_close(&view); + if (ret < 0) { + i_error("Corrupted mailbox list index %s", ilist->path); + mail_index_mark_corrupted(ilist->index); + return -1; } - if (prefix == NULL) - prefix = ""; + return 0; +} - if (index_mailbox_list_is_synced(ctx) <= 0) { - if (index_mailbox_list_sync(ctx) < 0) - return FALSE; +int index_mailbox_list_refresh(struct mailbox_list *list) +{ + struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(list); - /* updated, we'll have to reopen views */ - mail_index_view_close(&ctx->mail_view); - if (ctx->view != NULL) - mailbox_list_index_view_deinit(&ctx->view); - - ctx->mail_view = mail_index_view_open(ilist->mail_index); - if (mailbox_list_index_view_init(ilist->list_index, - ctx->mail_view, - &ctx->view) < 0) - return FALSE; + if (ilist->iter_refcount > 0) { + /* someone's already iterating. don't break them. */ + return 0; } - if ((flags & MAILBOX_LIST_ITER_SELECT_SUBSCRIBED) != 0) { - ctx->subs_iter = - mailbox_tree_iterate_init(ctx->subs_tree, - NULL, MAILBOX_MATCHED); + if (ilist->mailbox_tree == NULL || ilist->force_refresh) { + /* the first mailbox list in this session, + refresh list of mailboxes */ + if (index_mailbox_list_sync(list) < 0) + return -1; } else { - /* list from index */ - ctx->info_pool = - pool_alloconly_create("mailbox name pool", 256); - ctx->iter_ctx = - mailbox_list_index_iterate_init(ctx->view, prefix, - ctx->recurse_level); - ctx->prefix = *prefix == '\0' ? i_strdup(ctx->ns_prefix) : - i_strdup_printf("%s%s%c", ctx->ns_prefix, prefix, sep); + if (mail_index_refresh(ilist->index) < 0) + return -1; + + if (index_mailbox_list_read(ilist, FALSE) < 0) + return -1; } - return TRUE; + return 0; } static struct mailbox_list_iterate_context * @@ -274,96 +442,102 @@ { struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(list); struct index_mailbox_list_iterate_context *ctx; + char ns_sep = mail_namespace_get_sep(list->ns); ctx = i_new(struct index_mailbox_list_iterate_context, 1); ctx->ctx.list = list; ctx->ctx.flags = flags; - ctx->ns_prefix = list->ns->prefix; - ctx->ns_prefix_len = strlen(ctx->ns_prefix); + ctx->ctx.glob = imap_match_init_multiple(default_pool, patterns, + TRUE, ns_sep); + array_create(&ctx->ctx.module_contexts, default_pool, sizeof(void *), 5); + ctx->sep = ns_sep; - if (!index_mailbox_list_iter_init_try(ctx, patterns)) { + if (index_mailbox_list_refresh(ctx->ctx.list) < 0) { /* no indexing */ + ilist->force_refresh = TRUE; ctx->backend_ctx = ilist->module_ctx.super. iter_init(list, patterns, flags); + } else { + /* listing mailboxes from index */ + ctx->info.ns = list->ns; + ctx->path = str_new(default_pool, 128); + ctx->next_node = ilist->mailbox_tree; + ilist->iter_refcount++; } return &ctx->ctx; } -static int -list_index_get_info_flags(struct index_mailbox_list_iterate_context *ctx, - uint32_t uid, enum mailbox_info_flags *flags_r) +static void +index_mailbox_list_update_info(struct index_mailbox_list_iterate_context *ctx) { - struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(ctx->ctx.list); - const struct mail_index_record *rec; - uint32_t seq; + struct index_mailbox_node *node = ctx->next_node; + + str_truncate(ctx->path, ctx->parent_len); + if (str_len(ctx->path) > 0) + str_append_c(ctx->path, ctx->sep); + str_append(ctx->path, node->name); - if (!mail_index_lookup_seq(ctx->mail_view, uid, &seq)) { - i_error("Mailbox list index desynced: " - "Record uid=%u expunged from mail index", uid); - mail_index_mark_corrupted(ilist->mail_index); - return -1; + ctx->info.name = str_c(ctx->path); + ctx->info.flags = 0; + if ((node->flags & MAILBOX_LIST_INDEX_FLAG_NONEXISTENT) != 0) + ctx->info.flags |= MAILBOX_NONEXISTENT; + else if ((node->flags & MAILBOX_LIST_INDEX_FLAG_NOSELECT) != 0) + ctx->info.flags |= MAILBOX_NOSELECT; + if ((node->flags & MAILBOX_LIST_INDEX_FLAG_NOINFERIORS) != 0) + ctx->info.flags |= MAILBOX_NOINFERIORS; + ctx->info.flags |= node->children != NULL ? + MAILBOX_CHILDREN : MAILBOX_NOCHILDREN; + + if ((ctx->ctx.flags & (MAILBOX_LIST_ITER_SELECT_SUBSCRIBED | + MAILBOX_LIST_ITER_RETURN_SUBSCRIBED)) != 0) { + mailbox_list_set_subscription_flags(ctx->ctx.list, + ctx->info.name, + &ctx->info.flags); } - rec = mail_index_lookup(ctx->mail_view, seq); - *flags_r = index_mailbox_list_index_flags_translate(rec->flags); - return 0; + /* FIXME: set marked, unmarked flags based on recent counter */ } -static int list_index_iter_next(struct index_mailbox_list_iterate_context *ctx, - const struct mailbox_info **info_r) +static void +index_mailbox_list_update_next(struct index_mailbox_list_iterate_context *ctx, + bool follow_children) { - struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(ctx->ctx.list); - struct mailbox_list_index_info iinfo; - struct mailbox_node *subs_node; - int ret; - - /* find the next matching mailbox */ - for (;;) { - p_clear(ctx->info_pool); - ret = mailbox_list_index_iterate_next(ctx->iter_ctx, &iinfo); - if (ret <= 0) { - *info_r = NULL; - return ret; - } - - ctx->info.name = *ctx->prefix == '\0' ? iinfo.name : - p_strconcat(ctx->info_pool, ctx->prefix, - iinfo.name, NULL); - if (imap_match(ctx->glob, ctx->info.name) != IMAP_MATCH_YES) - continue; + struct index_mailbox_node *node = ctx->next_node; - if (list_index_get_info_flags(ctx, iinfo.uid, - &ctx->info.flags) < 0) - return -1; - - if ((ctx->info.flags & MAILBOX_NOCHILDREN) != 0 && - iinfo.has_children) { - i_error("Mailbox list index desynced: " - "Children flags for uid=%u wrong in mail index", - iinfo.uid); - mail_index_mark_corrupted(ilist->mail_index); - return -1; - } - - /* skip nonexistent mailboxes when finding with "*" */ - if ((ctx->info.flags & MAILBOX_NONEXISTENT) != 0 && - ctx->recurse_level < 0) - continue; - - if (ctx->subs_tree != NULL) { - /* get subscription states */ - subs_node = mailbox_tree_lookup(ctx->subs_tree, - ctx->info.name); - if (subs_node != NULL) { - ctx->info.flags |= subs_node->flags & - (MAILBOX_SUBSCRIBED | - MAILBOX_CHILD_SUBSCRIBED); + if (node->children != NULL && follow_children) { + ctx->parent_len = str_len(ctx->path); + ctx->next_node = node->children; + } else { + while (node->next == NULL) { + node = node->parent; + if (node != NULL) { + ctx->parent_len -= strlen(node->name); + if (node->parent != NULL) + ctx->parent_len--; + } + if (node == NULL) { + /* last one */ + ctx->next_node = NULL; + return; } } + ctx->next_node = node->next; + } +} - *info_r = &ctx->info; - return 0; - } +static bool +iter_subscriptions_ok(struct index_mailbox_list_iterate_context *ctx) +{ + if ((ctx->ctx.flags & MAILBOX_LIST_ITER_SELECT_SUBSCRIBED) == 0) + return TRUE; + + if ((ctx->info.flags & MAILBOX_SUBSCRIBED) != 0) + return TRUE; + + if ((ctx->ctx.flags & MAILBOX_LIST_ITER_SELECT_RECURSIVEMATCH) != 0 && + (ctx->info.flags & MAILBOX_CHILD_SUBSCRIBED) != 0) + return TRUE; + return FALSE; } static const struct mailbox_info * @@ -372,42 +546,33 @@ struct index_mailbox_list_iterate_context *ctx = (struct index_mailbox_list_iterate_context *)_ctx; struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(_ctx->list); - const struct mailbox_info *info; - struct mailbox_node *subs_node; - const char *index_name; - uint32_t uid; + bool follow_children; + enum imap_match_result match; - if (ctx->iter_ctx != NULL) { - /* listing mailboxes from index */ - if (list_index_iter_next(ctx, &info) < 0) { - ctx->failed = TRUE; - return NULL; - } - return info; - } else if (ctx->backend_ctx != NULL) { + if (ctx->backend_ctx != NULL) { /* index isn't being used */ return ilist->module_ctx.super.iter_next(ctx->backend_ctx); } - /* listing subscriptions, but we also want flags */ - subs_node = mailbox_tree_iterate_next(ctx->subs_iter, &ctx->info.name); - if (subs_node == NULL) - return NULL; - - index_name = ctx->info.name; - if (ctx->ns_prefix_len > 0 && - strncmp(ctx->info.name, ctx->ns_prefix, ctx->ns_prefix_len) == 0) - index_name += ctx->ns_prefix_len; + /* listing mailboxes from index */ + while (ctx->next_node != NULL) { + index_mailbox_list_update_info(ctx); + match = imap_match(_ctx->glob, ctx->info.name); - if (mailbox_list_index_lookup(ctx->view, index_name, &uid) < 0 || - list_index_get_info_flags(ctx, uid, &ctx->info.flags) < 0) { - ctx->failed = TRUE; - return NULL; + follow_children = (match & (IMAP_MATCH_YES | + IMAP_MATCH_CHILDREN)) != 0; + if (match == IMAP_MATCH_YES && iter_subscriptions_ok(ctx)) { + index_mailbox_list_update_next(ctx, TRUE); + return &ctx->info; + } else if ((_ctx->flags & MAILBOX_LIST_ITER_SELECT_SUBSCRIBED) != 0 && + (ctx->info.flags & MAILBOX_CHILD_SUBSCRIBED) == 0) { + /* listing only subscriptions, but there are no + subscribed children. */ + follow_children = FALSE; + } + index_mailbox_list_update_next(ctx, follow_children); } - - ctx->info.flags |= subs_node->flags & - (MAILBOX_SUBSCRIBED | MAILBOX_CHILD_SUBSCRIBED); - return &ctx->info; + return NULL; } static int @@ -418,24 +583,16 @@ struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(_ctx->list); int ret = ctx->failed ? -1 : 0; - if (ctx->subs_iter != NULL) - mailbox_tree_iterate_deinit(&ctx->subs_iter); - if (ctx->iter_ctx != NULL) - mailbox_list_index_iterate_deinit(&ctx->iter_ctx); - if (ctx->info_pool != NULL) - pool_unref(&ctx->info_pool); - - if (ctx->mail_view != NULL) - mail_index_view_close(&ctx->mail_view); - if (ctx->view != NULL) - mailbox_list_index_view_deinit(&ctx->view); - if (ctx->backend_ctx != NULL) ret = ilist->module_ctx.super.iter_deinit(ctx->backend_ctx); + else { + i_assert(ilist->iter_refcount > 0); + ilist->iter_refcount--; + str_free(&ctx->path); + } - if (ctx->glob != NULL) - imap_match_deinit(&ctx->glob); - i_free(ctx->prefix); + imap_match_deinit(&ctx->ctx.glob); + array_free(&ctx->ctx.module_contexts); i_free(ctx); return ret; } @@ -444,69 +601,49 @@ { struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(list); - mailbox_list_index_free(&ilist->list_index); - mailbox_list_index_view_deinit(&ilist->list_sync_view); - mail_index_free(&ilist->mail_index); - + hash_table_destroy(&ilist->mailbox_hash); + hash_table_destroy(&ilist->mailbox_names); + pool_unref(&ilist->mailbox_pool); + mail_index_close(ilist->index); + mail_index_free(&ilist->index); ilist->module_ctx.super.deinit(list); } -static int index_mailbox_list_open_indexes(struct mailbox_list *list, - const char *dir) +static int index_mailbox_list_index_open(struct mailbox_list *list) { struct index_mailbox_list *ilist = INDEX_LIST_CONTEXT(list); - const char *path; - enum mail_index_open_flags index_flags = 0; - char sep; - int ret; + const struct mail_storage_settings *set = list->mail_set; + enum mail_index_open_flags index_flags; + unsigned int lock_timeout; - index_flags = mail_storage_settings_to_index_flags(list->mail_set); + index_flags = mail_storage_settings_to_index_flags(set); + lock_timeout = set->mail_max_lock_timeout == 0 ? -1U : + set->mail_max_lock_timeout; - mail_index_set_lock_method(ilist->mail_index, - list->mail_set->parsed_lock_method, -1U); - if (mail_index_open_or_create(ilist->mail_index, index_flags) < 0) { - if (mail_index_move_to_memory(ilist->mail_index) < 0) { + mail_index_set_lock_method(ilist->index, set->parsed_lock_method, + lock_timeout); + if (mail_index_open_or_create(ilist->index, index_flags) < 0) { + if (mail_index_move_to_memory(ilist->index) < 0) { /* try opening once more. it should be created directly into memory now. */ - ret = mail_index_open_or_create(ilist->mail_index, - index_flags); - if (ret < 0) { - /* everything failed. there's a bug in the - code, but just work around it by disabling - the index completely */ - return -1; - } + if (mail_index_open_or_create(ilist->index, + index_flags) < 0) + i_panic("in-memory index creation failed"); } } - - path = t_strconcat(dir, "/"MAILBOX_LIST_INDEX_NAME, NULL); - sep = mailbox_list_get_hierarchy_sep(list); - ilist->list_index = mailbox_list_index_alloc(path, sep, - ilist->mail_index); - if (mailbox_list_index_open_or_create(ilist->list_index) < 0) { - /* skip indexing */ - mailbox_list_index_free(&ilist->list_index); - return -1; - } - if (mailbox_list_index_view_init(ilist->list_index, NULL, - &ilist->list_sync_view) < 0) { - mailbox_list_index_free(&ilist->list_index); - return -1; - } return 0; } static void index_mailbox_list_created(struct mailbox_list *list) { - struct index_mailbox_list *ilist = NULL; + struct index_mailbox_list *ilist; const char *dir; - /* FIXME: always disabled for now */ dir = mailbox_list_get_path(list, NULL, MAILBOX_LIST_PATH_TYPE_INDEX); - if (*dir == '\0' || list->mail_set->mailbox_list_index_disable || - strcmp(list->name, "maildir++") != 0 || 1) { + if (*dir == '\0' || list->mail_set->mailbox_list_index) { /* reserve the module context anyway, so syncing code knows that the index is disabled */ + ilist = NULL; MODULE_CONTEXT_SET(list, index_mailbox_list_module, ilist); return; } @@ -520,18 +657,28 @@ list->v.iter_next = index_mailbox_list_iter_next; MODULE_CONTEXT_SET(list, index_mailbox_list_module, ilist); - ilist->mail_index = mail_index_alloc(dir, MAIL_INDEX_PREFIX); + ilist->path = p_strdup_printf(list->pool, + "%s/"MAILBOX_LIST_INDEX_PREFIX, dir); + ilist->index = mail_index_alloc(dir, MAILBOX_LIST_INDEX_PREFIX); + + ilist->ext_id = mail_index_ext_register(ilist->index, "list", 0, + sizeof(struct mailbox_list_index_record), + sizeof(uint32_t)); - /* sync_init allocates the extensions. do it here before opening the - index files, so that our initial memory pool size guesses are a - bit more optimal */ - index_mailbox_list_sync_init_list(list); + ilist->mailbox_pool = pool_alloconly_create("mailbox list index", 4096); + ilist->mailbox_names = + hash_table_create(default_pool, ilist->mailbox_pool, + 0, NULL, NULL); + ilist->mailbox_hash = + hash_table_create(default_pool, ilist->mailbox_pool, + 0, NULL, NULL); - if (index_mailbox_list_open_indexes(list, dir) < 0) { + if (index_mailbox_list_index_open(list) < 0) { list->v = ilist->module_ctx.super; - mail_index_free(&ilist->mail_index); + mail_index_free(&ilist->index); MODULE_CONTEXT_UNSET(list, index_mailbox_list_module); } + index_mailbox_list_status_init_list(list); } static struct mail_storage_hooks index_mailbox_list_hooks = { @@ -543,5 +690,5 @@ void index_mailbox_list_init(void) { mail_storage_hooks_add_internal(&index_mailbox_list_hooks); - index_mailbox_list_sync_init(); + index_mailbox_list_status_init(); }
--- a/src/lib-storage/list/index-mailbox-list.h Tue Feb 08 00:08:38 2011 +0200 +++ b/src/lib-storage/list/index-mailbox-list.h Tue Feb 08 01:35:45 2011 +0200 @@ -4,46 +4,86 @@ #include "module-context.h" #include "mailbox-list-private.h" -#define MAIL_INDEX_PREFIX "dovecot.list.index" -#define MAILBOX_LIST_INDEX_NAME MAIL_INDEX_PREFIX".uidmap" +#define MAILBOX_LIST_INDEX_PREFIX "dovecot.list.index" #define INDEX_LIST_CONTEXT(obj) \ MODULE_CONTEXT(obj, index_mailbox_list_module) +/* stored in mail_index_record.flags: */ +enum mailbox_list_index_flags { + MAILBOX_LIST_INDEX_FLAG_NONEXISTENT = MAIL_DELETED, + MAILBOX_LIST_INDEX_FLAG_NOSELECT = MAIL_DRAFT, + MAILBOX_LIST_INDEX_FLAG_NOINFERIORS = MAIL_ANSWERED, + + /* set during syncing for mailboxes that still exist */ + MAILBOX_LIST_INDEX_FLAG_MARKED +}; + +struct mailbox_list_index_record { + /* points to given id in header */ + uint32_t name_id; + /* parent mailbox's UID, 0 = root */ + uint32_t parent_uid; + + /* the following fields are temporarily zero while unknown, + also permanently zero for \NoSelect and \Nonexistent mailboxes: */ + + uint8_t guid[MAIL_GUID_128_SIZE]; + uint32_t uid_validity; +}; + +struct mailbox_list_index_msgs_record { + uint32_t messages; + uint32_t unseen; + uint32_t recent; + uint32_t uidnext; +}; + +struct index_mailbox_node { + struct index_mailbox_node *parent; + struct index_mailbox_node *next; + struct index_mailbox_node *children; + + uint32_t name_id, uid; + enum mailbox_list_index_flags flags; + const char *name; +}; + struct index_mailbox_list { union mailbox_list_module_context module_ctx; - struct mail_index *mail_index; - struct mailbox_list_index *list_index; - struct mailbox_list_index_view *list_sync_view; + const char *path; + struct mail_index *index; + uint32_t ext_id, msgs_ext_id, hmodseq_ext_id; + + /* Number of iterations going on. Don't refresh mailbox list while + any iterations are going on. */ + int iter_refcount; - uint32_t eid_messages, eid_unseen, eid_recent; - uint32_t eid_uid_validity, eid_uidnext; + pool_t mailbox_pool; + /* uint32_t id => const char *name */ + struct hash_table *mailbox_names; + uint32_t highest_name_id; + + uint32_t sync_log_file_seq; + uoff_t sync_log_file_offset; + + /* uint32_t uid => struct index_mailbox_node* */ + struct hash_table *mailbox_hash; + struct index_mailbox_node *mailbox_tree; + + unsigned int force_refresh:1; }; struct index_mailbox_list_iterate_context { struct mailbox_list_iterate_context ctx; - - struct mailbox_list_iter_ctx *iter_ctx; struct mailbox_list_iterate_context *backend_ctx; - struct mailbox_tree_context *subs_tree; - struct mailbox_tree_iterate_context *subs_iter; - - struct mailbox_list_index_view *view; - struct mail_index_view *mail_view; - struct mail_index_transaction *trans; - - char *prefix; - int recurse_level; - struct imap_match_glob *glob; - - const char *ns_prefix; - unsigned int ns_prefix_len; - - pool_t info_pool; struct mailbox_info info; - uint32_t sync_stamp; + unsigned int parent_len; + string_t *path; + struct index_mailbox_node *next_node; + char sep; unsigned int failed:1; }; @@ -51,7 +91,12 @@ extern MODULE_CONTEXT_DEFINE(index_mailbox_list_module, &mailbox_list_module_register); -void index_mailbox_list_sync_init(void); -void index_mailbox_list_sync_init_list(struct mailbox_list *list); +struct index_mailbox_node * +index_mailbox_list_lookup(struct mailbox_list *list, const char *vname); + +int index_mailbox_list_refresh(struct mailbox_list *list); + +void index_mailbox_list_status_init(void); +void index_mailbox_list_status_init_list(struct mailbox_list *list); #endif
--- a/src/lib-storage/mail-storage-settings.c Tue Feb 08 00:08:38 2011 +0200 +++ b/src/lib-storage/mail-storage-settings.c Tue Feb 08 01:35:45 2011 +0200 @@ -40,7 +40,7 @@ DEF(SET_BOOL, dotlock_use_excl), DEF(SET_BOOL, mail_nfs_storage), DEF(SET_BOOL, mail_nfs_index), - DEF(SET_BOOL, mailbox_list_index_disable), + DEF(SET_BOOL, mailbox_list_index), DEF(SET_BOOL, mail_debug), DEF(SET_BOOL, mail_full_filesystem_access), DEF(SET_BOOL, maildir_stat_dirs), @@ -68,7 +68,7 @@ .dotlock_use_excl = FALSE, .mail_nfs_storage = FALSE, .mail_nfs_index = FALSE, - .mailbox_list_index_disable = FALSE, + .mailbox_list_index = FALSE, .mail_debug = FALSE, .mail_full_filesystem_access = FALSE, .maildir_stat_dirs = FALSE,
--- a/src/lib-storage/mail-storage-settings.h Tue Feb 08 00:08:38 2011 +0200 +++ b/src/lib-storage/mail-storage-settings.h Tue Feb 08 01:35:45 2011 +0200 @@ -27,7 +27,7 @@ bool dotlock_use_excl; bool mail_nfs_storage; bool mail_nfs_index; - bool mailbox_list_index_disable; + bool mailbox_list_index; bool mail_debug; bool mail_full_filesystem_access; bool maildir_stat_dirs;
--- a/src/lib-storage/mail-storage.c Tue Feb 08 00:08:38 2011 +0200 +++ b/src/lib-storage/mail-storage.c Tue Feb 08 01:35:45 2011 +0200 @@ -574,6 +574,12 @@ i_assert(uni_utf8_str_is_valid(vname)); + if (strcasecmp(vname, "INBOX") == 0 && + (list->ns->flags & NAMESPACE_FLAG_INBOX_USER) != 0) { + /* make sure INBOX shows up in uppercase everywhere */ + vname = "INBOX"; + } + if (mailbox_list_get_storage(&new_list, vname, &storage) < 0) { /* just use the first storage. FIXME: does this break? */ storage = list->ns->storage;