plugins/pop3-migration/pop3-migration-plugin.c

	pop3-migration-plugin.c revision 71748cca1bacd74451fd228db5536828bdfeb190
e59faf65ce864fe95dc00f5d52b8323cdbd0608aTimo Sirainen/* Copyright (c) 2007-2016 Dovecot authors, see the included COPYING file */
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen#include "lib.h"
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen#include "array.h"
61b0637759146621cbb7edcbd0b03a71cfd66dfeTimo Sirainen#include "istream.h"
7a7d2aa11e46195e2d92d6c337d7e78052a5ce67Timo Sirainen#include "istream-header-filter.h"
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen#include "str.h"
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen#include "sha1.h"
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen#include "message-size.h"
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen#include "message-header-hash.h"
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen#include "message-header-parser.h"
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen#include "mail-cache.h"
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen#include "mail-namespace.h"
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen#include "mail-search-build.h"
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen#include "index-storage.h"
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen#include "index-mail.h"
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen#include "pop3-migration-plugin.h"
f7539a17ea306191b53b8f5e752e228937df9ec3Timo Sirainen
f7539a17ea306191b53b8f5e752e228937df9ec3Timo Sirainen#define POP3_MIGRATION_CONTEXT(obj) \
f7539a17ea306191b53b8f5e752e228937df9ec3Timo Sirainen    MODULE_CONTEXT(obj, pop3_migration_storage_module)
f7539a17ea306191b53b8f5e752e228937df9ec3Timo Sirainen#define POP3_MIGRATION_MAIL_CONTEXT(obj) \
f7539a17ea306191b53b8f5e752e228937df9ec3Timo Sirainen    MODULE_CONTEXT(obj, pop3_migration_mail_module)
f7539a17ea306191b53b8f5e752e228937df9ec3Timo Sirainen
f7539a17ea306191b53b8f5e752e228937df9ec3Timo Sirainenstruct msg_map_common {
f7539a17ea306191b53b8f5e752e228937df9ec3Timo Sirainen    /* sha1(header) - set only when needed */
f7539a17ea306191b53b8f5e752e228937df9ec3Timo Sirainen    unsigned char hdr_sha1[SHA1_RESULTLEN];
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen    unsigned int hdr_sha1_set:1;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen};
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainenstruct pop3_uidl_map {
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen    struct msg_map_common common;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen    uint32_t pop3_seq;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen    uint32_t imap_uid;
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen    /* UIDL */
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen    const char *pop3_uidl;
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen    /* LIST size */
e5fd6dfd0a492e4708d4dbb7971d7fc5d7b8fd85Timo Sirainen    uoff_t size;
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen};
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen
d22301419109ed4a38351715e6760011421dadecTimo Sirainenstruct imap_msg_map {
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen    struct msg_map_common common;
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen    uint32_t uid, pop3_seq;
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen    uoff_t psize;
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen    const char *pop3_uidl;
3b32bc12710240f86465a00fbb2bd1ef030e6c40Timo Sirainen};
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen
d22301419109ed4a38351715e6760011421dadecTimo Sirainenstruct pop3_migration_mail_storage {
d22301419109ed4a38351715e6760011421dadecTimo Sirainen    union mail_storage_module_context module_ctx;
d22301419109ed4a38351715e6760011421dadecTimo Sirainen
d22301419109ed4a38351715e6760011421dadecTimo Sirainen    const char *pop3_box_vname;
d22301419109ed4a38351715e6760011421dadecTimo Sirainen    ARRAY(struct pop3_uidl_map) pop3_uidl_map;
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen
e5fd6dfd0a492e4708d4dbb7971d7fc5d7b8fd85Timo Sirainen    unsigned int all_mailboxes:1;
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen    unsigned int pop3_all_hdr_sha1_set:1;
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen    unsigned int ignore_missing_uidls:1;
d22301419109ed4a38351715e6760011421dadecTimo Sirainen    unsigned int skip_size_check:1;
d22301419109ed4a38351715e6760011421dadecTimo Sirainen};
d22301419109ed4a38351715e6760011421dadecTimo Sirainen
d22301419109ed4a38351715e6760011421dadecTimo Sirainenstruct pop3_migration_mailbox {
d22301419109ed4a38351715e6760011421dadecTimo Sirainen    union mailbox_module_context module_ctx;
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen
d22301419109ed4a38351715e6760011421dadecTimo Sirainen    ARRAY(struct imap_msg_map) imap_msg_map;
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen    unsigned int first_unfound_idx;
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen    struct mail_cache_field cache_field;
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen
ca98892a6b8a30ffc1fe26fcf02c7d59e3204e7eTimo Sirainen    unsigned int cache_field_registered:1;
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen    unsigned int uidl_synced:1;
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen    unsigned int uidl_sync_failed:1;
ca98892a6b8a30ffc1fe26fcf02c7d59e3204e7eTimo Sirainen    unsigned int uidl_ordered:1;
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen};
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen/* NOTE: these headers must be sorted */
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainenstatic const char *hdr_hash_skip_headers[] = {
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen    "Content-Length",
b42697a5749b85659a24316d97f1c208d469e4e8Timo Sirainen    "Return-Path", /* Yahoo IMAP has Return-Path, Yahoo POP3 doesn't */
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen    "Status",
ca98892a6b8a30ffc1fe26fcf02c7d59e3204e7eTimo Sirainen    "X-IMAP",
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen    "X-IMAPbase",
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen    "X-Keywords",
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen    "X-Message-Flag",
ca98892a6b8a30ffc1fe26fcf02c7d59e3204e7eTimo Sirainen    "X-Status",
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen    "X-UID",
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen    "X-UIDL",
df00412606a00714a6e85383fa87fbdc7cc1fb5bTimo Sirainen    "X-Yahoo-Newman-Property"
df00412606a00714a6e85383fa87fbdc7cc1fb5bTimo Sirainen};
df00412606a00714a6e85383fa87fbdc7cc1fb5bTimo Sirainenconst char *pop3_migration_plugin_version = DOVECOT_ABI_VERSION;
df00412606a00714a6e85383fa87fbdc7cc1fb5bTimo Sirainen
df00412606a00714a6e85383fa87fbdc7cc1fb5bTimo Sirainenstatic MODULE_CONTEXT_DEFINE_INIT(pop3_migration_storage_module,
df00412606a00714a6e85383fa87fbdc7cc1fb5bTimo Sirainen                  &mail_storage_module_register);
df00412606a00714a6e85383fa87fbdc7cc1fb5bTimo Sirainenstatic MODULE_CONTEXT_DEFINE_INIT(pop3_migration_mail_module,
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen                  &mail_module_register);
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen
17ad2164c747cedbf81dae1893063e71a3df0356Timo Sirainenstatic int imap_msg_map_uid_cmp(const struct imap_msg_map *map1,
17ad2164c747cedbf81dae1893063e71a3df0356Timo Sirainen                const struct imap_msg_map *map2)
17ad2164c747cedbf81dae1893063e71a3df0356Timo Sirainen{
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen    if (map1->uid < map2->uid)
3c493c276f599d9b9cd10764876d648003046954Timo Sirainen        return -1;
3c493c276f599d9b9cd10764876d648003046954Timo Sirainen    if (map1->uid > map2->uid)
3c493c276f599d9b9cd10764876d648003046954Timo Sirainen        return 1;
17ad2164c747cedbf81dae1893063e71a3df0356Timo Sirainen    return 0;
3c493c276f599d9b9cd10764876d648003046954Timo Sirainen}
9ffdc9d18870acef2e4dde99715d8528ff4b080dTimo Sirainen
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainenstatic int pop3_uidl_map_pop3_seq_cmp(const struct pop3_uidl_map *map1,
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen                      const struct pop3_uidl_map *map2)
f81f4bc282cd1944cec187bae89c0701a416ed2aTimo Sirainen{
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen    if (map1->pop3_seq < map2->pop3_seq)
f81f4bc282cd1944cec187bae89c0701a416ed2aTimo Sirainen        return -1;
ca98892a6b8a30ffc1fe26fcf02c7d59e3204e7eTimo Sirainen    if (map1->pop3_seq > map2->pop3_seq)
f81f4bc282cd1944cec187bae89c0701a416ed2aTimo Sirainen        return 1;
ca98892a6b8a30ffc1fe26fcf02c7d59e3204e7eTimo Sirainen    return 0;
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen}
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainenstatic int pop3_uidl_map_hdr_cmp(const struct pop3_uidl_map *map1,
7bafda1813454621e03615e83d55bccfa7cc56bdTimo Sirainen                 const struct pop3_uidl_map *map2)
7bafda1813454621e03615e83d55bccfa7cc56bdTimo Sirainen{
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen    return memcmp(map1->common.hdr_sha1, map2->common.hdr_sha1,
7bafda1813454621e03615e83d55bccfa7cc56bdTimo Sirainen              sizeof(map1->common.hdr_sha1));
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen}
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen
563273bdac80393af63b9520cbf4d24cc0efd028Timo Sirainenstatic int imap_msg_map_hdr_cmp(const struct imap_msg_map *map1,
ac26a4607cb12b156f6a42f1ead2881bedd43d94Timo Sirainen                const struct imap_msg_map *map2)
dca6d617a23e3f93af3b8df59acb46478179fe55Timo Sirainen{
2615df45a8027948a474abe5e817b34b0499c171Timo Sirainen    return memcmp(map1->common.hdr_sha1, map2->common.hdr_sha1,
1108376e39a19912e8394e64e19b1bc6f6691cf6Timo Sirainen              sizeof(map1->common.hdr_sha1));
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen}
3e564425db51f3921ce4de11859777135fdedd15Timo Sirainen
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainenstruct pop3_hdr_context {
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen    bool have_eoh;
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen    bool stop;
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen};
7bafda1813454621e03615e83d55bccfa7cc56bdTimo Sirainen
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainenstatic bool header_name_is_valid(const char *name)
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen{
a2f250a332dfc1e6cd4ffd196c621eb9dbf7b8a1Timo Sirainen    unsigned int i;
306cfd77100131c08b243de10f6d40500f4c27c6Timo Sirainen
1d2b188f0eedc3cab6e27ceac5425a037f38042eTimo Sirainen    for (i = 0; name[i] != '\0'; i++) {
09c08fad8e7cc694a6c8d1711e67839acd3a2f04Timo Sirainen        if ((uint8_t)name[i] <= 0x20 || name[i] >= 0x7f)
438f12d7a776da695019114884b48188d94613efTimo Sirainen            return FALSE;
17ad2164c747cedbf81dae1893063e71a3df0356Timo Sirainen    }
9ffdc9d18870acef2e4dde99715d8528ff4b080dTimo Sirainen    return TRUE;
61b0637759146621cbb7edcbd0b03a71cfd66dfeTimo Sirainen}
2649b237dd4690575e75a30b2bf3b39ebd37b835Timo Sirainen
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainenstatic void
d3442384ca53d4b18a493db7dd0b000f470419cfTimo Sirainenpop3_header_filter_callback(struct header_filter_istream *input ATTR_UNUSED,
d3442384ca53d4b18a493db7dd0b000f470419cfTimo Sirainen                struct message_header_line *hdr,
fbd918f47f591f8084fd52b207ef29515ddd11b9Timo Sirainen                bool *matched, struct pop3_hdr_context *ctx)
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen{
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen    if (hdr == NULL)
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen        return;
5137d2d80255938a0f5fb8f3c1a21b34cf11ada3Timo Sirainen    if (hdr->eoh) {
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen        ctx->have_eoh = TRUE;
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen        if (ctx->stop) {
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen            /* matched is handled differently for eoh by
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen             istream-header-filter. a design bug I guess.. */
ecdce39e5ef4b62eefa9f5818f17d153fd5d710aTimo Sirainen            *matched = FALSE;
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen        }
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen    } else {
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen        if (strspn(hdr->name, "\r") == hdr->name_len) {
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen            /* CR+CR+LF - some servers stop the header processing
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen             here while others don't. To make sure they can be
e3aeeb634245e80d4f643f8d2eea11d6b72336d8Timo Sirainen             matched correctly we want to stop here entirely. */
e3aeeb634245e80d4f643f8d2eea11d6b72336d8Timo Sirainen            ctx->stop = TRUE;
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen        }
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen        if (ctx->stop)
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen            *matched = TRUE;
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen        else if (!header_name_is_valid(hdr->name)) {
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen            /* Yahoo IMAP drops headers with invalid names, while
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen               Yahoo POP3 preserves them. Drop them all. */
c6a57378d3c54988f525f81e19c0c5d132a0770dTimo Sirainen            *matched = TRUE;
        }
    }
}

int pop3_migration_get_hdr_sha1(uint32_t mail_seq, struct istream *input,
                uoff_t hdr_size,
                unsigned char sha1_r[SHA1_RESULTLEN],
                bool *have_eoh_r)
{
    struct istream *input2;
    const unsigned char *data;
    size_t size;
    struct sha1_ctxt sha1_ctx;
    struct pop3_hdr_context hdr_ctx;

    memset(&hdr_ctx, 0, sizeof(hdr_ctx));
    input2 = i_stream_create_limit(input, hdr_size);
    /* hide headers that might change or be different in IMAP vs. POP3 */
    input = i_stream_create_header_filter(input2,
                HEADER_FILTER_EXCLUDE | HEADER_FILTER_NO_CR,
                hdr_hash_skip_headers,
                N_ELEMENTS(hdr_hash_skip_headers),
                pop3_header_filter_callback, &hdr_ctx);
    i_stream_unref(&input2);

    sha1_init(&sha1_ctx);
    while (i_stream_read_data(input, &data, &size, 0) > 0) {
        message_header_hash_more(&hash_method_sha1, &sha1_ctx, 2,
                     data, size);
        i_stream_skip(input, size);
    }
    if (input->stream_errno != 0) {
        i_error("pop3_migration: Failed to read header for msg %u: %s",
            mail_seq, i_stream_get_error(input));
        i_stream_unref(&input);
        return -1;
    }
    sha1_result(&sha1_ctx, sha1_r);
    i_stream_unref(&input);

    *have_eoh_r = hdr_ctx.have_eoh;
    return 0;
}

static unsigned int get_cache_idx(struct mail *mail)
{
    struct pop3_migration_mailbox *mbox = POP3_MIGRATION_CONTEXT(mail->box);

    if (mbox->cache_field_registered)
        return mbox->cache_field.idx;

    mbox->cache_field.name = "pop3-migration.hdr";
    mbox->cache_field.type = MAIL_CACHE_FIELD_FIXED_SIZE;
    mbox->cache_field.field_size = SHA1_RESULTLEN;
    mail_cache_register_fields(mail->box->cache, &mbox->cache_field, 1);
    mbox->cache_field_registered = TRUE;
    return mbox->cache_field.idx;
}

static int
get_hdr_sha1(struct mail *mail, unsigned char sha1_r[SHA1_RESULTLEN])
{
    struct istream *input;
    struct message_size hdr_size;
    const char *errstr;
    enum mail_error error;
    bool have_eoh;

    if (mail_get_hdr_stream(mail, &hdr_size, &input) < 0) {
        errstr = mailbox_get_last_error(mail->box, &error);
        i_error("pop3_migration: Failed to get header for msg %u: %s",
            mail->seq, errstr);
        return error == MAIL_ERROR_EXPUNGED ? 0 : -1;
    }
    if (pop3_migration_get_hdr_sha1(mail->seq, input,
                    hdr_size.physical_size,
                    sha1_r, &have_eoh) < 0)
        return -1;
    if (have_eoh) {
        struct index_mail *imail = (struct index_mail *)mail;

        index_mail_cache_add_idx(imail, get_cache_idx(mail),
                     sha1_r, SHA1_RESULTLEN);
        return 1;
    }

    /* The empty "end of headers" line is missing. Either this means that
       the headers ended unexpectedly (which is ok) or that the remote
       server is buggy. Some servers have problems with

       1) header line continuations that contain only whitespace and
       2) headers that have no ":". The header gets truncated when such
       line is reached.

       At least Oracle IMS IMAP FETCH BODY[HEADER] handles 1) by not
       returning the whitespace line and 2) by returning the line but
       truncating the rest. POP3 TOP instead returns the entire header.
       This causes the IMAP and POP3 hashes not to match.

       If there's LF+CR+CR+LF in the middle of headers, Courier IMAP's
       FETCH BODY[HEADER] stops after that, but Courier POP3's TOP doesn't.

       So we'll try to avoid this by falling back to full FETCH BODY[]
       (and/or RETR) and we'll parse the header ourself from it. This
       should work around any similar bugs in all IMAP/POP3 servers. */
    if (mail_get_stream(mail, &hdr_size, NULL, &input) < 0) {
        errstr = mailbox_get_last_error(mail->box, &error);
        i_error("pop3_migration: Failed to get body for msg %u: %s",
            mail->seq, errstr);
        return error == MAIL_ERROR_EXPUNGED ? 0 : -1;
    }
    return pop3_migration_get_hdr_sha1(mail->seq, input,
                       hdr_size.physical_size,
                       sha1_r, &have_eoh);

}

static bool
get_cached_hdr_sha1(struct mail *mail, buffer_t *cache_buf,
            unsigned char sha1_r[SHA1_RESULTLEN])
{
    struct index_mail *imail = (struct index_mail *)mail;

    buffer_set_used_size(cache_buf, 0);
    if (index_mail_cache_lookup_field(imail, cache_buf,
                      get_cache_idx(mail)) > 0 &&
        cache_buf->used == SHA1_RESULTLEN) {
        memcpy(sha1_r, cache_buf->data, cache_buf->used);
        return TRUE;
    }
    return FALSE;
}

static struct mailbox *pop3_mailbox_alloc(struct mail_storage *storage)
{
    struct pop3_migration_mail_storage *mstorage =
        POP3_MIGRATION_CONTEXT(storage);
    struct mail_namespace *ns;

    ns = mail_namespace_find(storage->user->namespaces,
                 mstorage->pop3_box_vname);
    i_assert(ns != NULL);
    return mailbox_alloc(ns->list, mstorage->pop3_box_vname,
                 MAILBOX_FLAG_READONLY | MAILBOX_FLAG_POP3_SESSION);
}

static int pop3_map_read(struct mail_storage *storage, struct mailbox *pop3_box)
{
    struct pop3_migration_mail_storage *mstorage =
        POP3_MIGRATION_CONTEXT(storage);
    struct mailbox_transaction_context *t;
    struct mail_search_args *search_args;
    struct mail_search_context *ctx;
    struct mail *mail;
    struct pop3_uidl_map *map;
    const char *uidl;
    uoff_t size = (uoff_t)-1;
    int ret = 0;

    if (array_is_created(&mstorage->pop3_uidl_map)) {
        /* already read these, just reset the imap_uids */
        array_foreach_modifiable(&mstorage->pop3_uidl_map, map)
            map->imap_uid = 0;
        return 0;
    }
    i_array_init(&mstorage->pop3_uidl_map, 128);

    if (mailbox_sync(pop3_box, 0) < 0) {
        i_error("pop3_migration: Couldn't sync mailbox %s: %s",
            pop3_box->vname, mailbox_get_last_error(pop3_box, NULL));
        return -1;
    }

    t = mailbox_transaction_begin(pop3_box, 0);
    search_args = mail_search_build_init();
    mail_search_build_add_all(search_args);
    ctx = mailbox_search_init(t, search_args, NULL,
                  mstorage->skip_size_check ? 0 :
                  MAIL_FETCH_PHYSICAL_SIZE, NULL);
    mail_search_args_unref(&search_args);

    while (mailbox_search_next(ctx, &mail)) {
        /* get the size with LIST instead of RETR */
        mail->lookup_abort = MAIL_LOOKUP_ABORT_READ_MAIL;

        if (mstorage->skip_size_check)
            ;
        else if (mail_get_physical_size(mail, &size) < 0) {
            i_error("pop3_migration: Failed to get size for msg %u: %s",
                mail->seq,
                mailbox_get_last_error(pop3_box, NULL));
            ret = -1;
            break;
        }
        if (mail_get_special(mail, MAIL_FETCH_UIDL_BACKEND, &uidl) < 0) {
            i_error("pop3_migration: Failed to get UIDL for msg %u: %s",
                mail->seq,
                mailbox_get_last_error(pop3_box, NULL));
            ret = -1;
            break;
        }
        if (*uidl == '\0') {
            i_warning("pop3_migration: UIDL for msg %u is empty",
                  mail->seq);
            continue;
        }

        map = array_append_space(&mstorage->pop3_uidl_map);
        map->pop3_seq = mail->seq;
        map->pop3_uidl = p_strdup(storage->pool, uidl);
        map->size = size;
    }

    if (mailbox_search_deinit(&ctx) < 0) {
        i_error("pop3_migration: Failed to search all POP3 mails: %s",
            mailbox_get_last_error(pop3_box, NULL));
        ret = -1;
    }
    (void)mailbox_transaction_commit(&t);
    return ret;
}

static void
pop3_map_read_cached_hdr_hashes(struct mailbox_transaction_context *t,
                struct mail_search_args *search_args,
                struct array *msg_map)
{
    struct mail_search_context *ctx;
    struct mail *mail;
    struct msg_map_common *map;
    buffer_t *cache_buf;

    ctx = mailbox_search_init(t, search_args, NULL, 0, NULL);
    cache_buf = buffer_create_dynamic(pool_datastack_create(), SHA1_RESULTLEN);

    while (mailbox_search_next(ctx, &mail)) {
        map = array_idx_modifiable_i(msg_map, mail->seq-1);

        if (get_cached_hdr_sha1(mail, cache_buf, map->hdr_sha1))
            map->hdr_sha1_set = TRUE;
    }

    if (mailbox_search_deinit(&ctx) < 0) {
        i_warning("pop3_migration: Failed to search all cached POP3 header hashes: %s - ignoring",
              mailbox_get_last_error(t->box, NULL));
    }
}

static void map_remove_found_seqs(struct mail_search_arg *search_arg,
                  struct array *msg_map, uint32_t seq1)
{
    const struct msg_map_common *map;
    uint32_t seq, count = array_count_i(msg_map);

    i_assert(search_arg->type == SEARCH_SEQSET);

    for (seq = seq1; seq <= count; seq++) {
        map = array_idx_i(msg_map, seq-1);
        if (map->hdr_sha1_set)
            seq_range_array_remove(&search_arg->value.seqset, seq);
    }
}

static int
map_read_hdr_hashes(struct mailbox *box, struct array *msg_map, uint32_t seq1)
{
        struct mailbox_transaction_context *t;
    struct mail_search_args *search_args;
    struct mail_search_context *ctx;
    struct mail *mail;
    struct msg_map_common *map;
    int ret = 0;

    t = mailbox_transaction_begin(box, 0);
    /* get all the cached hashes */
    search_args = mail_search_build_init();
    mail_search_build_add_seqset(search_args, seq1, array_count_i(msg_map));
    pop3_map_read_cached_hdr_hashes(t, search_args, msg_map);
    /* read all the non-cached hashes. doing this in two passes allows
       us to set wanted_fields=MAIL_FETCH_STREAM_HEADER, which allows
       prefetching to work without downloading all the headers even
       for mails that already are cached. */
    map_remove_found_seqs(search_args->args, msg_map, seq1);
    ctx = mailbox_search_init(t, search_args, NULL,
                  MAIL_FETCH_STREAM_HEADER, NULL);
    mail_search_args_unref(&search_args);

    while (mailbox_search_next(ctx, &mail)) {
        map = array_idx_modifiable_i(msg_map, mail->seq-1);

        if ((ret = get_hdr_sha1(mail, map->hdr_sha1)) < 0) {
            ret = -1;
            break;
        }
        if (ret > 0)
            map->hdr_sha1_set = TRUE;
    }

    if (mailbox_search_deinit(&ctx) < 0) {
        i_error("pop3_migration: Failed to search all mail headers: %s",
            mailbox_get_last_error(box, NULL));
        ret = -1;
    }
    (void)mailbox_transaction_commit(&t);
    return ret < 0 ? -1 : 0;
}

static int
pop3_map_read_hdr_hashes(struct mail_storage *storage, struct mailbox *pop3_box,
             unsigned first_seq)
{
    struct pop3_migration_mail_storage *mstorage =
        POP3_MIGRATION_CONTEXT(storage);

    if (mstorage->pop3_all_hdr_sha1_set)
        return 0;
    if (mstorage->all_mailboxes) {
        /* we may be matching against multiple mailboxes.
           read all the hashes only once. */
        first_seq = 1;
    }

    if (map_read_hdr_hashes(pop3_box, &mstorage->pop3_uidl_map.arr,
                first_seq) < 0)
        return -1;

    if (first_seq == 1)
        mstorage->pop3_all_hdr_sha1_set = TRUE;
    return 0;
}

static int imap_map_read(struct mailbox *box)
{
    struct pop3_migration_mailbox *mbox = POP3_MIGRATION_CONTEXT(box);
    struct pop3_migration_mail_storage *mstorage =
        POP3_MIGRATION_CONTEXT(box->storage);
    struct mailbox_status status;
        struct mailbox_transaction_context *t;
    struct mail_search_args *search_args;
    struct mail_search_context *ctx;
    struct mail *mail;
    struct imap_msg_map *map;
    uoff_t psize = (uoff_t)-1;
    int ret = 0;

    mailbox_get_open_status(box, STATUS_MESSAGES, &status);

    i_assert(!array_is_created(&mbox->imap_msg_map));
    p_array_init(&mbox->imap_msg_map, box->pool, status.messages);

    t = mailbox_transaction_begin(box, 0);
    search_args = mail_search_build_init();
    mail_search_build_add_all(search_args);
    ctx = mailbox_search_init(t, search_args, NULL,
                  mstorage->skip_size_check ? 0 :
                  MAIL_FETCH_PHYSICAL_SIZE, NULL);
    mail_search_args_unref(&search_args);

    while (mailbox_search_next(ctx, &mail)) {
        if (mstorage->skip_size_check)
            ;
        else if (mail_get_physical_size(mail, &psize) < 0) {
            i_error("pop3_migration: Failed to get psize for imap uid %u: %s",
                mail->uid,
                mailbox_get_last_error(box, NULL));
            ret = -1;
            break;
        }

        map = array_append_space(&mbox->imap_msg_map);
        map->uid = mail->uid;
        map->psize = psize;
    }

    if (mailbox_search_deinit(&ctx) < 0) {
        i_error("pop3_migration: Failed to search all IMAP mails: %s",
            mailbox_get_last_error(box, NULL));
        ret = -1;
    }
    (void)mailbox_transaction_commit(&t);
    return ret;
}

static int imap_map_read_hdr_hashes(struct mailbox *box)
{
    struct pop3_migration_mailbox *mbox = POP3_MIGRATION_CONTEXT(box);

    return map_read_hdr_hashes(box, &mbox->imap_msg_map.arr,
                   mbox->first_unfound_idx+1);
}

static bool pop3_uidl_assign_by_size(struct mailbox *box)
{
    struct pop3_migration_mailbox *mbox = POP3_MIGRATION_CONTEXT(box);
    struct pop3_migration_mail_storage *mstorage =
        POP3_MIGRATION_CONTEXT(box->storage);
    struct pop3_uidl_map *pop3_map;
    struct imap_msg_map *imap_map;
    unsigned int i, pop3_count, imap_count, count;

    if (mstorage->skip_size_check)
        return FALSE;

    pop3_map = array_get_modifiable(&mstorage->pop3_uidl_map, &pop3_count);
    imap_map = array_get_modifiable(&mbox->imap_msg_map, &imap_count);
    count = I_MIN(pop3_count, imap_count);

    /* see if we can match the messages using sizes */
    for (i = 0; i < count; i++) {
        if (pop3_map[i].size != imap_map[i].psize)
            break;
        if (i+1 < count && pop3_map[i].size == pop3_map[i+1].size) {
            /* two messages with same size, don't trust them */
            break;
        }

        pop3_map[i].imap_uid = imap_map[i].uid;
        imap_map[i].pop3_uidl = pop3_map[i].pop3_uidl;
        imap_map[i].pop3_seq = pop3_map[i].pop3_seq;
    }
    mbox->first_unfound_idx = i;
    if (box->storage->user->mail_debug)
        i_debug("pop3_migration: %u/%u mails matched by size", i, count);
    return i == count;
}

static int
pop3_uidl_assign_by_hdr_hash(struct mailbox *box, struct mailbox *pop3_box)
{
    struct pop3_migration_mail_storage *mstorage =
        POP3_MIGRATION_CONTEXT(box->storage);
    struct pop3_migration_mailbox *mbox = POP3_MIGRATION_CONTEXT(box);
    struct pop3_uidl_map *pop3_map;
    struct imap_msg_map *imap_map;
    unsigned int pop3_idx, imap_idx, pop3_count, imap_count;
    unsigned int first_seq, missing_uids_count;
    uint32_t first_missing_idx = (uint32_t)-1;
    int ret;

    first_seq = mbox->first_unfound_idx+1;
    if (pop3_map_read_hdr_hashes(box->storage, pop3_box, first_seq) < 0 ||
        imap_map_read_hdr_hashes(box) < 0)
        return -1;

    array_sort(&mstorage->pop3_uidl_map, pop3_uidl_map_hdr_cmp);
    array_sort(&mbox->imap_msg_map, imap_msg_map_hdr_cmp);

    pop3_map = array_get_modifiable(&mstorage->pop3_uidl_map, &pop3_count);
    imap_map = array_get_modifiable(&mbox->imap_msg_map, &imap_count);

    pop3_idx = imap_idx = 0;
    while (pop3_idx < pop3_count && imap_idx < imap_count) {
        if (!pop3_map[pop3_idx].common.hdr_sha1_set ||
            pop3_map[pop3_idx].imap_uid != 0) {
            pop3_idx++;
            continue;
        }
        if (!imap_map[imap_idx].common.hdr_sha1_set ||
            imap_map[imap_idx].pop3_uidl != NULL) {
            imap_idx++;
            continue;
        }
        ret = memcmp(pop3_map[pop3_idx].common.hdr_sha1,
                 imap_map[imap_idx].common.hdr_sha1,
                 sizeof(pop3_map[pop3_idx].common.hdr_sha1));
        if (ret < 0)
            pop3_idx++;
        else if (ret > 0)
            imap_idx++;
        else {
            pop3_map[pop3_idx].imap_uid = imap_map[imap_idx].uid;
            imap_map[imap_idx].pop3_uidl =
                pop3_map[pop3_idx].pop3_uidl;
            imap_map[imap_idx].pop3_seq =
                pop3_map[pop3_idx].pop3_seq;
        }
    }
    missing_uids_count = 0;
    for (pop3_idx = 0; pop3_idx < pop3_count; pop3_idx++) {
        if (pop3_map[pop3_idx].imap_uid != 0) {
            /* matched */
        } else if (!pop3_map[pop3_idx].common.hdr_sha1_set) {
            /* we treated this mail as expunged - ignore */
        } else {
            if (first_missing_idx == (uint32_t)-1)
                first_missing_idx = pop3_idx;
            missing_uids_count++;
        }
    }
    if (missing_uids_count > 0 && !mstorage->all_mailboxes) {
        string_t *str = t_str_new(128);

        str_printfa(str, "pop3_migration: %u POP3 messages have no "
                "matching IMAP messages (first POP3 msg %u UIDL %s)",
                missing_uids_count,
                pop3_map[first_missing_idx].pop3_seq,
                pop3_map[first_missing_idx].pop3_uidl);
        if (imap_count + missing_uids_count == pop3_count) {
            str_append(str, " - all IMAP messages were found "
                "(POP3 contains more than IMAP INBOX - you may want to set pop3_migration_all_mailboxes=yes)");
        }
        if (!mstorage->ignore_missing_uidls) {
            i_error("%s - set pop3_migration_ignore_missing_uidls=yes to continue anyway",
                str_c(str));
            return -1;
        }
        i_warning("%s", str_c(str));
    } else if (box->storage->user->mail_debug) {
        i_debug("pop3_migration: %u mails matched by headers", pop3_count);
    }
    array_sort(&mstorage->pop3_uidl_map, pop3_uidl_map_pop3_seq_cmp);
    array_sort(&mbox->imap_msg_map, imap_msg_map_uid_cmp);
    return 0;
}

static int pop3_migration_uidl_sync(struct mailbox *box)
{
    struct pop3_migration_mailbox *mbox = POP3_MIGRATION_CONTEXT(box);
    struct pop3_migration_mail_storage *mstorage =
        POP3_MIGRATION_CONTEXT(box->storage);
    struct mailbox *pop3_box;
    const struct pop3_uidl_map *pop3_map;
    unsigned int i, count;
    uint32_t prev_uid;

    pop3_box = pop3_mailbox_alloc(box->storage);
    /* the POP3 server isn't connected to yet. handle all IMAP traffic
       first before connecting, so POP3 server won't disconnect us due to
       idling. */
    if (imap_map_read(box) < 0 ||
        pop3_map_read(box->storage, pop3_box) < 0) {
        mailbox_free(&pop3_box);
        return -1;
    }

    if (!pop3_uidl_assign_by_size(box)) {
        /* everything wasn't assigned, figure out the rest with
           header hashes */
        if (pop3_uidl_assign_by_hdr_hash(box, pop3_box) < 0) {
            mailbox_free(&pop3_box);
            return -1;
        }
    }

    /* see if the POP3 UIDL order is the same as IMAP UID order */
    mbox->uidl_ordered = TRUE;
    pop3_map = array_get(&mstorage->pop3_uidl_map, &count);
    prev_uid = 0;
    for (i = 0; i < count; i++) {
        if (pop3_map[i].imap_uid == 0)
            continue;

        if (prev_uid > pop3_map[i].imap_uid) {
            mbox->uidl_ordered = FALSE;
            break;
        }
        prev_uid = pop3_map[i].imap_uid;
    }

    mbox->uidl_synced = TRUE;
    mailbox_free(&pop3_box);
    return 0;
}

static int pop3_migration_uidl_sync_if_needed(struct mailbox *box)
{
    struct pop3_migration_mailbox *mbox = POP3_MIGRATION_CONTEXT(box);

    if (mbox->uidl_synced)
        return 0;

    if (mbox->uidl_sync_failed ||
        pop3_migration_uidl_sync(box) < 0) {
        mbox->uidl_sync_failed = TRUE;
        mail_storage_set_error(box->storage, MAIL_ERROR_TEMP,
                       "POP3 UIDLs couldn't be synced");
        return -1;
    }
    return 0;
}

static int
pop3_migration_get_special(struct mail *_mail, enum mail_fetch_field field,
               const char **value_r)
{
    struct mail_private *mail = (struct mail_private *)_mail;
    union mail_module_context *mmail = POP3_MIGRATION_MAIL_CONTEXT(mail);
    struct pop3_migration_mailbox *mbox = POP3_MIGRATION_CONTEXT(_mail->box);
    struct imap_msg_map map_key, *map;

    if (field == MAIL_FETCH_UIDL_BACKEND ||
        field == MAIL_FETCH_POP3_ORDER) {
        if (pop3_migration_uidl_sync_if_needed(_mail->box) < 0)
            return -1;

        memset(&map_key, 0, sizeof(map_key));
        map_key.uid = _mail->uid;
        map = array_bsearch(&mbox->imap_msg_map, &map_key,
                    imap_msg_map_uid_cmp);
        if (map != NULL && map->pop3_uidl != NULL) {
            if (field == MAIL_FETCH_UIDL_BACKEND)
                *value_r = map->pop3_uidl;
            else
                *value_r = t_strdup_printf("%u", map->pop3_seq);
            return 0;
        }
        /* not found from POP3 server, fallback to default */
    }
    return mmail->super.get_special(_mail, field, value_r);
}

static void pop3_migration_mail_allocated(struct mail *_mail)
{
    struct pop3_migration_mail_storage *mstorage =
        POP3_MIGRATION_CONTEXT(_mail->box->storage);
    struct mail_private *mail = (struct mail_private *)_mail;
    struct mail_vfuncs *v = mail->vlast;
    union mail_module_context *mmail;
    struct mail_namespace *ns;

    if (mstorage == NULL ||
        (!mstorage->all_mailboxes && !_mail->box->inbox_user)) {
        /* assigns UIDLs only for INBOX */
        return;
    }

    ns = mail_namespace_find(_mail->box->storage->user->namespaces,
                 mstorage->pop3_box_vname);
    if (ns == mailbox_get_namespace(_mail->box)) {
        /* we're accessing the pop3-migration namespace itself */
        return;
    }

    mmail = p_new(mail->pool, union mail_module_context, 1);
    mmail->super = *v;
    mail->vlast = &mmail->super;

    v->get_special = pop3_migration_get_special;
    MODULE_CONTEXT_SET_SELF(mail, pop3_migration_mail_module, mmail);
}

static struct mail_search_context *
pop3_migration_mailbox_search_init(struct mailbox_transaction_context *t,
                   struct mail_search_args *args,
                   const enum mail_sort_type *sort_program,
                   enum mail_fetch_field wanted_fields,
                   struct mailbox_header_lookup_ctx *wanted_headers)
{
    struct pop3_migration_mailbox *mbox = POP3_MIGRATION_CONTEXT(t->box);
    struct pop3_migration_mail_storage *mstorage =
        POP3_MIGRATION_CONTEXT(t->box->storage);

    if ((wanted_fields & (MAIL_FETCH_UIDL_BACKEND |
                  MAIL_FETCH_POP3_ORDER)) != 0 &&
        (mstorage->all_mailboxes || t->box->inbox_user)) {
        /* Start POP3 UIDL syncing before the search, so we'll do it
           before we start sending any FETCH BODY[]s to IMAP. It
           shouldn't matter much, except this works around a bug in
           Yahoo IMAP where it sometimes breaks its state when doing
           a FETCH BODY[] followed by FETCH BODY[HEADER].. */
        (void)pop3_migration_uidl_sync_if_needed(t->box);
    }

    return mbox->module_ctx.super.search_init(t, args, sort_program,
                          wanted_fields, wanted_headers);
}

static void pop3_migration_mailbox_allocated(struct mailbox *box)
{
    struct mailbox_vfuncs *v = box->vlast;
    struct pop3_migration_mailbox *mbox;

    mbox = p_new(box->pool, struct pop3_migration_mailbox, 1);
    mbox->module_ctx.super = *v;
    box->vlast = &mbox->module_ctx.super;

    v->search_init = pop3_migration_mailbox_search_init;

    MODULE_CONTEXT_SET(box, pop3_migration_storage_module, mbox);
}

static void pop3_migration_mail_storage_destroy(struct mail_storage *storage)
{
    struct pop3_migration_mail_storage *mstorage =
        POP3_MIGRATION_CONTEXT(storage);

    if (array_is_created(&mstorage->pop3_uidl_map))
        array_free(&mstorage->pop3_uidl_map);

    mstorage->module_ctx.super.destroy(storage);
}

static void pop3_migration_mail_storage_created(struct mail_storage *storage)
{
    struct pop3_migration_mail_storage *mstorage;
    struct mail_storage_vfuncs *v = storage->vlast;
    const char *pop3_box_vname;

    pop3_box_vname = mail_user_plugin_getenv(storage->user,
                         "pop3_migration_mailbox");
    if (pop3_box_vname == NULL) {
        if (storage->user->mail_debug)
            i_debug("pop3_migration: No pop3_migration_mailbox setting - disabled");
        return;
    }

    mstorage = p_new(storage->pool, struct pop3_migration_mail_storage, 1);
    mstorage->module_ctx.super = *v;
    storage->vlast = &mstorage->module_ctx.super;
    v->destroy = pop3_migration_mail_storage_destroy;

    mstorage->pop3_box_vname = p_strdup(storage->pool, pop3_box_vname);
    mstorage->all_mailboxes =
        mail_user_plugin_getenv_bool(storage->user,
                    "pop3_migration_all_mailboxes");
    mstorage->ignore_missing_uidls =
        mail_user_plugin_getenv_bool(storage->user,
            "pop3_migration_ignore_missing_uidls");
    mstorage->skip_size_check =
        mail_user_plugin_getenv_bool(storage->user,
            "pop3_migration_skip_size_check");

    MODULE_CONTEXT_SET(storage, pop3_migration_storage_module, mstorage);
}

static struct mail_storage_hooks pop3_migration_mail_storage_hooks = {
    .mail_allocated = pop3_migration_mail_allocated,
    .mailbox_allocated = pop3_migration_mailbox_allocated,
    .mail_storage_created = pop3_migration_mail_storage_created
};

void pop3_migration_plugin_init(struct module *module)
{
    mail_storage_hooks_add(module, &pop3_migration_mail_storage_hooks);
}

void pop3_migration_plugin_deinit(void)
{
    mail_storage_hooks_remove(&pop3_migration_mail_storage_hooks);
}