# HG changeset patch # User Timo Sirainen # Date 1227400809 -7200 # Node ID b127057043296c073c29cc67562ca3231749d7fe # Parent 1ff129ed866a986ad661210cca62626aa6e4a862 Optimized searching with virtual mailboxes. Instead of going through the messages in the virtual mailbox order, go them through one mailbox at a time and in ascending message order within that mailbox. diff -r 1ff129ed866a -r b12705704329 src/plugins/virtual/Makefile.am --- a/src/plugins/virtual/Makefile.am Sun Nov 23 02:37:23 2008 +0200 +++ b/src/plugins/virtual/Makefile.am Sun Nov 23 02:40:09 2008 +0200 @@ -15,6 +15,7 @@ virtual-config.c \ virtual-mail.c \ virtual-plugin.c \ + virtual-search.c \ virtual-storage.c \ virtual-sync.c \ virtual-transaction.c diff -r 1ff129ed866a -r b12705704329 src/plugins/virtual/virtual-search.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/plugins/virtual/virtual-search.c Sun Nov 23 02:40:09 2008 +0200 @@ -0,0 +1,208 @@ +/* Copyright (c) 2008 Dovecot authors, see the included COPYING file */ + +#include "lib.h" +#include "array.h" +#include "mail-search.h" +#include "index-storage.h" +#include "virtual-storage.h" + +#include + +enum virtual_search_state { + VIRTUAL_SEARCH_STATE_FAILED = -1, + VIRTUAL_SEARCH_STATE_BUILD, + VIRTUAL_SEARCH_STATE_RETURN, + VIRTUAL_SEARCH_STATE_SORT, + VIRTUAL_SEARCH_STATE_SORT_DONE +}; + +struct virtual_search_record { + uint32_t mailbox_id; + uint32_t real_uid; + uint32_t virtual_seq; +}; + +struct virtual_search_context { + union mail_search_module_context module_ctx; + + ARRAY_TYPE(seq_range) result; + struct seq_range_iter result_iter; + ARRAY_DEFINE(records, struct virtual_search_record); + + enum virtual_search_state search_state; + unsigned int next_result_n; + unsigned int next_record_idx; +}; + +static int virtual_search_record_cmp(const void *p1, const void *p2) +{ + const struct virtual_search_record *r1 = p1, *r2 = p2; + + if (r1->mailbox_id < r2->mailbox_id) + return -1; + if (r1->mailbox_id > r2->mailbox_id) + return 1; + + if (r1->real_uid < r2->real_uid) + return -1; + if (r1->real_uid > r2->real_uid) + return 1; + return 0; +} + +static int mail_search_get_result(struct mail_search_context *ctx) +{ + const struct mail_search_arg *arg; + int ret = 1; + + for (arg = ctx->args->args; arg != NULL; arg = arg->next) { + if (arg->result < 0) + return -1; + if (arg->result == 0) + ret = 0; + } + return ret; +} + +static int virtual_search_get_records(struct mail_search_context *ctx, + struct virtual_search_context *vctx) +{ + struct virtual_mailbox *mbox = + (struct virtual_mailbox *)ctx->transaction->box; + const struct virtual_mail_index_record *vrec; + struct virtual_search_record srec, *srecs; + unsigned int count; + const void *data; + bool expunged; + int ret, result; + + memset(&srec, 0, sizeof(srec)); + while ((ret = index_storage_search_next_update_seq(ctx)) > 0) { + result = mail_search_get_result(ctx); + i_assert(result != 0); + if (result > 0) { + /* full match, no need to check this any further */ + seq_range_array_add(&vctx->result, 0, ctx->seq); + } else { + /* possible match, save and check later */ + mail_index_lookup_ext(mbox->ibox.view, ctx->seq, + mbox->virtual_ext_id, + &data, &expunged); + vrec = data; + + srec.mailbox_id = vrec->mailbox_id; + srec.real_uid = vrec->real_uid; + srec.virtual_seq = ctx->seq; + array_append(&vctx->records, &srec, 1); + } + mail_search_args_reset(ctx->args->args, FALSE); + } + srecs = array_get_modifiable(&vctx->records, &count); + qsort(srecs, count, sizeof(*srecs), virtual_search_record_cmp); + return ret; +} + +struct mail_search_context * +virtual_search_init(struct mailbox_transaction_context *t, + struct mail_search_args *args, + const enum mail_sort_type *sort_program) +{ + struct mail_search_context *ctx; + struct virtual_search_context *vctx; + + ctx = index_storage_search_init(t, args, sort_program); + + vctx = i_new(struct virtual_search_context, 1); + vctx->search_state = VIRTUAL_SEARCH_STATE_BUILD; + i_array_init(&vctx->result, 64); + i_array_init(&vctx->records, 64); + MODULE_CONTEXT_SET(ctx, virtual_storage_module, vctx); + + if (virtual_search_get_records(ctx, vctx) < 0) + vctx->search_state = VIRTUAL_SEARCH_STATE_FAILED; + + seq_range_array_iter_init(&vctx->result_iter, &vctx->result); + return ctx; +} + +int virtual_search_deinit(struct mail_search_context *ctx) +{ + struct virtual_search_context *vctx = VIRTUAL_CONTEXT(ctx); + + array_free(&vctx->result); + array_free(&vctx->records); + i_free(vctx); + return index_storage_search_deinit(ctx); +} + +int virtual_search_next_nonblock(struct mail_search_context *ctx, + struct mail *mail, bool *tryagain_r) +{ + struct virtual_search_context *vctx = VIRTUAL_CONTEXT(ctx); + uint32_t seq; + int ret; + + switch (vctx->search_state) { + case VIRTUAL_SEARCH_STATE_FAILED: + return -1; + case VIRTUAL_SEARCH_STATE_BUILD: + if (ctx->sort_program == NULL) + vctx->search_state = VIRTUAL_SEARCH_STATE_SORT; + else + vctx->search_state = VIRTUAL_SEARCH_STATE_RETURN; + return virtual_search_next_nonblock(ctx, mail, tryagain_r); + case VIRTUAL_SEARCH_STATE_RETURN: + return index_storage_search_next_nonblock(ctx, mail, tryagain_r); + case VIRTUAL_SEARCH_STATE_SORT: + /* the messages won't be returned sorted, so we'll have to + do it ourself */ + while ((ret = index_storage_search_next_nonblock(ctx, mail, + tryagain_r)) > 0) + seq_range_array_add(&vctx->result, 0, mail->seq); + if (ret < 0 || *tryagain_r) + return ret; + + vctx->next_result_n = 0; + vctx->search_state = VIRTUAL_SEARCH_STATE_SORT_DONE; + /* fall through */ + case VIRTUAL_SEARCH_STATE_SORT_DONE: + *tryagain_r = FALSE; + if (!seq_range_array_iter_nth(&vctx->result_iter, + vctx->next_result_n, &seq)) + return 0; + vctx->next_result_n++; + mail_set_seq(mail, seq); + return 1; + } + i_unreached(); +} + +static void search_args_set_full_match(struct mail_search_arg *args) +{ + for (; args != NULL; args = args->next) + args->result = 1; +} + +bool virtual_search_next_update_seq(struct mail_search_context *ctx) +{ + struct virtual_search_context *vctx = VIRTUAL_CONTEXT(ctx); + const struct virtual_search_record *recs; + unsigned int count; + + recs = array_get(&vctx->records, &count); + if (vctx->next_record_idx < count) { + ctx->seq = recs[vctx->next_record_idx++].virtual_seq - 1; + if (!index_storage_search_next_update_seq(ctx)) + i_unreached(); + return TRUE; + } + + if (ctx->sort_program != NULL && + seq_range_array_iter_nth(&vctx->result_iter, + vctx->next_result_n, &ctx->seq)) { + search_args_set_full_match(ctx->args->args); + vctx->next_result_n++; + return TRUE; + } + return FALSE; +} diff -r 1ff129ed866a -r b12705704329 src/plugins/virtual/virtual-storage.c --- a/src/plugins/virtual/virtual-storage.c Sun Nov 23 02:37:23 2008 +0200 +++ b/src/plugins/virtual/virtual-storage.c Sun Nov 23 02:40:09 2008 +0200 @@ -24,6 +24,8 @@ extern struct mail_storage virtual_storage; extern struct mailbox virtual_mailbox; +struct virtual_storage_module virtual_storage_module = + MODULE_CONTEXT_INIT(&mail_storage_module_register); static MODULE_CONTEXT_DEFINE_INIT(virtual_mailbox_list_module, &mailbox_list_module_register); @@ -584,10 +586,10 @@ index_header_lookup_init, index_header_lookup_ref, index_header_lookup_unref, - index_storage_search_init, - index_storage_search_deinit, - index_storage_search_next_nonblock, - index_storage_search_next_update_seq, + virtual_search_init, + virtual_search_deinit, + virtual_search_next_nonblock, + virtual_search_next_update_seq, NULL, NULL, NULL, diff -r 1ff129ed866a -r b12705704329 src/plugins/virtual/virtual-storage.h --- a/src/plugins/virtual/virtual-storage.h Sun Nov 23 02:37:23 2008 +0200 +++ b/src/plugins/virtual/virtual-storage.h Sun Nov 23 02:40:09 2008 +0200 @@ -10,6 +10,9 @@ #define VIRTUAL_CONFIG_FNAME "dovecot-virtual" #define VIRTUAL_INDEX_PREFIX "dovecot.index" +#define VIRTUAL_CONTEXT(obj) \ + MODULE_CONTEXT(obj, virtual_storage_module) + struct virtual_mail_index_header { /* Increased by one each time the header is modified */ uint32_t change_counter; @@ -107,6 +110,9 @@ unsigned int sync_initialized:1; }; +extern MODULE_CONTEXT_DEFINE(virtual_storage_module, + &mail_storage_module_register); + extern struct mail_storage virtual_storage; extern struct mail_vfuncs virtual_mail_vfuncs; @@ -121,6 +127,15 @@ virtual_transaction_get(struct mailbox_transaction_context *trans, struct mailbox *backend_box); +struct mail_search_context * +virtual_search_init(struct mailbox_transaction_context *t, + struct mail_search_args *args, + const enum mail_sort_type *sort_program); +int virtual_search_deinit(struct mail_search_context *ctx); +int virtual_search_next_nonblock(struct mail_search_context *ctx, + struct mail *mail, bool *tryagain_r); +bool virtual_search_next_update_seq(struct mail_search_context *ctx); + struct mail * virtual_mail_alloc(struct mailbox_transaction_context *t, enum mail_fetch_field wanted_fields,