plugins/virtual/virtual-storage.c

	virtual-storage.c revision d5282594ec73c953ffb23096a2cddf373cc15f46
1N/A/* Copyright (c) 2008-2017 Dovecot authors, see the included COPYING file */
1N/A
1N/A#include "lib.h"
1N/A#include "array.h"
1N/A#include "ioloop.h"
2N/A#include "str.h"
2N/A#include "llist.h"
12N/A#include "mkdir-parents.h"
2N/A#include "unlink-directory.h"
2N/A#include "index-mail.h"
2N/A#include "mail-copy.h"
12N/A#include "mail-search.h"
2N/A#include "mailbox-list-private.h"
2N/A#include "virtual-plugin.h"
2N/A#include "virtual-transaction.h"
12N/A#include "virtual-storage.h"
2N/A
2N/A#include <stdio.h>
2N/A#include <unistd.h>
12N/A#include <dirent.h>
2N/A#include <sys/stat.h>
2N/A
2N/A#define VIRTUAL_DEFAULT_MAX_OPEN_MAILBOXES 64
12N/A
1N/A#define VIRTUAL_BACKEND_CONTEXT(obj) \
1N/A    MODULE_CONTEXT(obj, virtual_backend_storage_module)
2N/A
2N/Astruct virtual_backend_mailbox {
2N/A    union mailbox_module_context module_ctx;
2N/A};
2N/A
2N/Aextern struct mail_storage virtual_storage;
2N/Aextern struct mailbox virtual_mailbox;
12N/Aextern struct virtual_mailbox_vfuncs virtual_mailbox_vfuncs;
2N/A
2N/Astruct virtual_storage_module virtual_storage_module =
2N/A    MODULE_CONTEXT_INIT(&mail_storage_module_register);
2N/Astatic MODULE_CONTEXT_DEFINE_INIT(virtual_backend_storage_module,
2N/A                  &mail_storage_module_register);
2N/A
2N/Astatic bool ns_is_visible(struct mail_namespace *ns)
2N/A{
2N/A    return (ns->flags & NAMESPACE_FLAG_LIST_PREFIX) != 0 ||
2N/A        (ns->flags & NAMESPACE_FLAG_LIST_CHILDREN) != 0 ||
2N/A        (ns->flags & NAMESPACE_FLAG_HIDDEN) == 0;
2N/A}
2N/A
2N/Astatic const char *get_user_visible_mailbox_name(struct mailbox *box)
2N/A{
2N/A    if (ns_is_visible(box->list->ns))
2N/A        return box->vname;
2N/A    else {
2N/A        return t_strdup_printf("<hidden>%c%s",
2N/A                       mail_namespace_get_sep(box->list->ns),
2N/A                       box->vname);
2N/A    }
2N/A}
2N/A
2N/Avoid virtual_box_copy_error(struct mailbox *dest, struct mailbox *src)
2N/A{
2N/A    const char *name, *str;
2N/A    enum mail_error error;
2N/A
2N/A    name = get_user_visible_mailbox_name(src);
2N/A    str = mailbox_get_last_error(src, &error);
2N/A
2N/A    str = t_strdup_printf("%s (for backend mailbox %s)", str, name);
2N/A    mail_storage_set_error(dest->storage, error, str);
2N/A}
2N/A
2N/Astatic struct mail_storage *virtual_storage_alloc(void)
2N/A{
2N/A    struct virtual_storage *storage;
2N/A    pool_t pool;
1N/A
12N/A    pool = pool_alloconly_create("virtual storage", 1024);
12N/A    storage = p_new(pool, struct virtual_storage, 1);
12N/A    storage->storage = virtual_storage;
12N/A    storage->storage.pool = pool;
9N/A    p_array_init(&storage->open_stack, pool, 8);
9N/A    return &storage->storage;
9N/A}
9N/A
9N/Astatic int
9N/Avirtual_storage_create(struct mail_storage *_storage,
9N/A               struct mail_namespace *ns ATTR_UNUSED,
9N/A               const char **error_r)
9N/A{
9N/A    struct virtual_storage *storage = (struct virtual_storage *)_storage;
9N/A    const char *value;
9N/A
2N/A    value = mail_user_plugin_getenv(_storage->user, "virtual_max_open_mailboxes");
9N/A    if (value == NULL)
9N/A        storage->max_open_mailboxes = VIRTUAL_DEFAULT_MAX_OPEN_MAILBOXES;
9N/A    else if (str_to_uint(value, &storage->max_open_mailboxes) < 0) {
9N/A        *error_r = "Invalid virtual_max_open_mailboxes setting";
9N/A        return -1;
9N/A    }
9N/A    return 0;
9N/A}
9N/A
9N/Astatic void
9N/Avirtual_storage_get_list_settings(const struct mail_namespace *ns ATTR_UNUSED,
9N/A                  struct mailbox_list_settings *set)
12N/A{
12N/A    if (set->layout == NULL)
12N/A        set->layout = MAILBOX_LIST_NAME_FS;
12N/A    if (set->subscription_fname == NULL)
12N/A        set->subscription_fname = VIRTUAL_SUBSCRIPTION_FILE_NAME;
12N/A}
12N/A
12N/Astruct virtual_backend_box *
12N/Avirtual_backend_box_lookup_name(struct virtual_mailbox *mbox, const char *name)
12N/A{
12N/A    struct virtual_backend_box *const *bboxes;
12N/A    unsigned int i, count;
12N/A
12N/A    bboxes = array_get(&mbox->backend_boxes, &count);
12N/A    for (i = 0; i < count; i++) {
        if (strcmp(bboxes[i]->name, name) == 0)
            return bboxes[i];
    }
    return NULL;
}

struct virtual_backend_box *
virtual_backend_box_lookup(struct virtual_mailbox *mbox, uint32_t mailbox_id)
{
    struct virtual_backend_box *const *bboxes;
    unsigned int i, count;

    if (mailbox_id == 0)
        return NULL;

    bboxes = array_get(&mbox->backend_boxes, &count);
    for (i = 0; i < count; i++) {
        if (bboxes[i]->mailbox_id == mailbox_id)
            return bboxes[i];
    }
    return NULL;
}

static bool virtual_mailbox_is_in_open_stack(struct virtual_storage *storage,
                         const char *name)
{
    const char *const *names;
    unsigned int i, count;

    names = array_get(&storage->open_stack, &count);
    for (i = 0; i < count; i++) {
        if (strcmp(names[i], name) == 0)
            return TRUE;
    }
    return FALSE;
}

static int virtual_backend_box_open_failed(struct virtual_mailbox *mbox,
                       struct virtual_backend_box *bbox)
{
    enum mail_error error;
    const char *str;

    str = t_strdup_printf(
        "Virtual mailbox open failed because of mailbox %s: %s",
        get_user_visible_mailbox_name(bbox->box),
        mailbox_get_last_error(bbox->box, &error));
    mail_storage_set_error(mbox->box.storage, error, str);
    mailbox_free(&bbox->box);

    if (error == MAIL_ERROR_PERM && bbox->wildcard) {
        /* this mailbox wasn't explicitly specified. just skip it. */
        return 0;
    }
    return -1;
}

static int virtual_backend_box_alloc(struct virtual_mailbox *mbox,
                     struct virtual_backend_box *bbox,
                     enum mailbox_flags flags)
{
    struct mail_user *user = mbox->storage->storage.user;
    struct mail_namespace *ns;
    const char *mailbox;
    enum mailbox_existence existence;

    i_assert(bbox->box == NULL);

    if (!bbox->clear_recent)
        flags &= ~MAILBOX_FLAG_DROP_RECENT;

    mailbox = bbox->name;
    ns = mail_namespace_find(user->namespaces, mailbox);
    bbox->box = mailbox_alloc(ns->list, mailbox, flags);
    MODULE_CONTEXT_SET(bbox->box, virtual_storage_module, bbox);
    mailbox_set_reason(bbox->box, mbox->box.reason == NULL ? "virtual mailbox" :
        t_strdup_printf("virtual mailbox: %s", mbox->box.reason));

    if (mailbox_exists(bbox->box, TRUE, &existence) < 0)
        return virtual_backend_box_open_failed(mbox, bbox);
    if (existence != MAILBOX_EXISTENCE_SELECT) {
        /* ignore this. it could be intentional. */
        if (mbox->storage->storage.user->mail_debug) {
            i_debug("virtual mailbox %s: "
                "Skipping non-existing mailbox %s",
                mbox->box.vname, bbox->box->vname);
        }
        mailbox_free(&bbox->box);
        return 0;
    }

    i_array_init(&bbox->uids, 64);
    i_array_init(&bbox->sync_pending_removes, 64);
    /* we use modseqs for being able to check quickly if backend mailboxes
       have changed. make sure the backend has them enabled. */
    (void)mailbox_enable(bbox->box, MAILBOX_FEATURE_CONDSTORE);
    return 1;
}

static int virtual_mailboxes_open(struct virtual_mailbox *mbox,
                  enum mailbox_flags flags)
{
    struct virtual_backend_box *const *bboxes;
    unsigned int i, count;
    int ret;

    bboxes = array_get(&mbox->backend_boxes, &count);
    for (i = 0; i < count; ) {
        ret = virtual_backend_box_alloc(mbox, bboxes[i], flags);
        if (ret <= 0) {
            if (ret < 0)
                break;
            array_delete(&mbox->backend_boxes, i, 1);
            bboxes = array_get(&mbox->backend_boxes, &count);
        } else {
            i++;
        }
    }
    if (i == count)
        return 0;
    else {
        /* failed */
        for (; i > 0; i--) {
            mailbox_free(&bboxes[i-1]->box);
            array_free(&bboxes[i-1]->uids);
        }
        return -1;
    }
}

static struct mailbox *
virtual_mailbox_alloc(struct mail_storage *_storage, struct mailbox_list *list,
              const char *vname, enum mailbox_flags flags)
{
    struct virtual_storage *storage = (struct virtual_storage *)_storage;
    struct virtual_mailbox *mbox;
    pool_t pool;

    pool = pool_alloconly_create("virtual mailbox", 2048);
    mbox = p_new(pool, struct virtual_mailbox, 1);
    mbox->box = virtual_mailbox;
    mbox->box.pool = pool;
    mbox->box.storage = _storage;
    mbox->box.list = list;
    mbox->box.mail_vfuncs = &virtual_mail_vfuncs;
    mbox->box.virtual_vfuncs = &virtual_mailbox_vfuncs;

    index_storage_mailbox_alloc(&mbox->box, vname, flags, MAIL_INDEX_PREFIX);

    mbox->storage = storage;
    mbox->virtual_ext_id = (uint32_t)-1;
    return &mbox->box;
}

void virtual_backend_box_sync_mail_unset(struct virtual_backend_box *bbox)
{
    struct mailbox_transaction_context *trans;

    if (bbox->sync_mail != NULL) {
        trans = bbox->sync_mail->transaction;
        mail_free(&bbox->sync_mail);
        (void)mailbox_transaction_commit(&trans);
    }
}

static bool virtual_backend_box_can_close(struct virtual_backend_box *bbox)
{
    if (bbox->box->notify_callback != NULL) {
        /* FIXME: IMAP IDLE running - we should support closing this
           also if mailbox_list_index=yes */
        return FALSE;
    }
    if (array_count(&bbox->sync_pending_removes) > 0) {
        /* FIXME: we could probably close this by making
           syncing support it? */
        return FALSE;
    }
    return TRUE;
}

static bool
virtual_backend_box_close_any_except(struct virtual_mailbox *mbox,
                     struct virtual_backend_box *except_bbox)
{
    struct virtual_backend_box *bbox;

    /* first try to close a mailbox without any transactions.
       we'll also skip any mailbox that has notifications enabled (ideally
       these would be handled by mailbox list index) */
    for (bbox = mbox->open_backend_boxes_head; bbox != NULL; bbox = bbox->next_open) {
        i_assert(bbox->box->opened);

        if (bbox != except_bbox &&
            bbox->box->transaction_count == 0 &&
            virtual_backend_box_can_close(bbox)) {
            i_assert(bbox->sync_mail == NULL);
            virtual_backend_box_close(mbox, bbox);
            return TRUE;
        }
    }

    /* next try to close a mailbox that has sync_mail, but no
       other transactions */
    for (bbox = mbox->open_backend_boxes_head; bbox != NULL; bbox = bbox->next_open) {
        if (bbox != except_bbox &&
            bbox->sync_mail != NULL &&
            bbox->box->transaction_count == 1 &&
            virtual_backend_box_can_close(bbox)) {
            virtual_backend_box_sync_mail_unset(bbox);
            i_assert(bbox->box->transaction_count == 0);
            virtual_backend_box_close(mbox, bbox);
            return TRUE;
        }
    }
    return FALSE;
}

static void virtual_backend_mailbox_close(struct mailbox *box)
{
    struct virtual_backend_box *bbox = VIRTUAL_CONTEXT(box);
    struct virtual_backend_mailbox *vbox = VIRTUAL_BACKEND_CONTEXT(box);

    if (bbox != NULL && bbox->open_tracked) {
        /* we could have gotten here from e.g. mailbox_autocreate()
           without going through virtual_mailbox_close() */
        virtual_backend_box_close(bbox->virtual_mbox, bbox);
    }
    vbox->module_ctx.super.close(box);
}

void virtual_backend_mailbox_allocated(struct mailbox *box)
{
    struct mailbox_vfuncs *v = box->vlast;
    struct virtual_backend_mailbox *vbox;

    vbox = p_new(box->pool, struct virtual_backend_mailbox, 1);
    vbox->module_ctx.super = *v;
    box->vlast = &vbox->module_ctx.super;
    v->close = virtual_backend_mailbox_close;
    MODULE_CONTEXT_SET(box, virtual_backend_storage_module, vbox);
}

void virtual_backend_mailbox_opened(struct mailbox *box)
{
    struct virtual_backend_box *bbox = VIRTUAL_CONTEXT(box);
    struct virtual_mailbox *mbox;

    if (bbox == NULL) {
        /* not a backend for a virtual mailbox */
        return;
    }
    i_assert(!bbox->open_tracked);
    mbox = bbox->virtual_mbox;

    /* the backend mailbox was already opened. if we didn't get here
       from virtual_backend_box_open() we may need to close a mailbox */
    while (mbox->backends_open_count >= mbox->storage->max_open_mailboxes &&
           virtual_backend_box_close_any_except(mbox, bbox))
        ;

    bbox->open_tracked = TRUE;
    mbox->backends_open_count++;
    DLLIST2_APPEND_FULL(&mbox->open_backend_boxes_head,
                &mbox->open_backend_boxes_tail, bbox,
                prev_open, next_open);
}

int virtual_backend_box_open(struct virtual_mailbox *mbox,
                 struct virtual_backend_box *bbox)
{
    i_assert(!bbox->box->opened);

    /* try to keep the number of open mailboxes below the threshold
       before opening the mailbox */
    while (mbox->backends_open_count >= mbox->storage->max_open_mailboxes &&
           virtual_backend_box_close_any_except(mbox, bbox))
        ;

    return mailbox_open(bbox->box);
}

void virtual_backend_box_close(struct virtual_mailbox *mbox,
                   struct virtual_backend_box *bbox)
{
    i_assert(bbox->box->opened);
    i_assert(bbox->open_tracked);

    if (bbox->search_result != NULL)
        mailbox_search_result_free(&bbox->search_result);

    if (bbox->search_args != NULL &&
        bbox->search_args_initialized) {
        mail_search_args_deinit(bbox->search_args);
        bbox->search_args_initialized = FALSE;
    }
    i_assert(mbox->backends_open_count > 0);
    mbox->backends_open_count--;
    bbox->open_tracked = FALSE;

    DLLIST2_REMOVE_FULL(&mbox->open_backend_boxes_head,
                &mbox->open_backend_boxes_tail, bbox,
                prev_open, next_open);
    mailbox_close(bbox->box);
}

void virtual_backend_box_accessed(struct virtual_mailbox *mbox,
                  struct virtual_backend_box *bbox)
{
    DLLIST2_REMOVE_FULL(&mbox->open_backend_boxes_head,
                &mbox->open_backend_boxes_tail, bbox,
                prev_open, next_open);
    DLLIST2_APPEND_FULL(&mbox->open_backend_boxes_head,
                &mbox->open_backend_boxes_tail, bbox,
                prev_open, next_open);
}

static void virtual_mailbox_close_internal(struct virtual_mailbox *mbox)
{
    struct virtual_backend_box **bboxes;
    unsigned int i, count;

    bboxes = array_get_modifiable(&mbox->backend_boxes, &count);
    for (i = 0; i < count; i++) {
        if (bboxes[i]->box == NULL)
            continue;

        if (bboxes[i]->box->opened)
            virtual_backend_box_close(mbox, bboxes[i]);
        mailbox_free(&bboxes[i]->box);
        if (array_is_created(&bboxes[i]->sync_outside_expunges))
            array_free(&bboxes[i]->sync_outside_expunges);
        array_free(&bboxes[i]->sync_pending_removes);
        array_free(&bboxes[i]->uids);
    }
    i_assert(mbox->backends_open_count == 0);
}

static int
virtual_mailbox_exists(struct mailbox *box, bool auto_boxes ATTR_UNUSED,
               enum mailbox_existence *existence_r)
{
    return index_storage_mailbox_exists_full(box, VIRTUAL_CONFIG_FNAME,
                         existence_r);
}

static int virtual_mailbox_open(struct mailbox *box)
{
    struct virtual_mailbox *mbox = (struct virtual_mailbox *)box;
    bool broken;
    int ret = 0;

    if (virtual_mailbox_is_in_open_stack(mbox->storage, box->name)) {
        mail_storage_set_critical(box->storage,
            "Virtual mailbox loops: %s", box->name);
        return -1;
    }

    if (!array_is_created(&mbox->backend_boxes))
        ret = virtual_config_read(mbox);
    if (ret == 0) {
        array_append(&mbox->storage->open_stack, &box->name, 1);
        ret = virtual_mailboxes_open(mbox, box->flags);
        array_delete(&mbox->storage->open_stack,
                 array_count(&mbox->storage->open_stack)-1, 1);
    }
    if (ret < 0) {
        virtual_mailbox_close_internal(mbox);
        return -1;
    }
    if (index_storage_mailbox_open(box, FALSE) < 0)
        return -1;

    mbox->virtual_ext_id =
        mail_index_ext_register(mbox->box.index, "virtual", 0,
            sizeof(struct virtual_mail_index_record),
            sizeof(uint32_t));

    if (virtual_mailbox_ext_header_read(mbox, box->view, &broken) < 0) {
        virtual_mailbox_close_internal(mbox);
        index_storage_mailbox_close(box);
        return -1;
    }
    return 0;
}

static void virtual_mailbox_close(struct mailbox *box)
{
    struct virtual_mailbox *mbox = (struct virtual_mailbox *)box;

    virtual_mailbox_close_internal(mbox);
    index_storage_mailbox_close(box);
}

static void virtual_mailbox_free(struct mailbox *box)
{
    struct virtual_mailbox *mbox = (struct virtual_mailbox *)box;

    virtual_config_free(mbox);
    index_storage_mailbox_free(box);
}

static int
virtual_mailbox_create(struct mailbox *box,
               const struct mailbox_update *update ATTR_UNUSED,
               bool directory ATTR_UNUSED)
{
    mail_storage_set_error(box->storage, MAIL_ERROR_NOTPOSSIBLE,
                   "Can't create virtual mailboxes");
    return -1;
}

static int
virtual_mailbox_update(struct mailbox *box,
               const struct mailbox_update *update ATTR_UNUSED)
{
    mail_storage_set_error(box->storage, MAIL_ERROR_NOTPOSSIBLE,
                   "Can't update virtual mailboxes");
    return -1;
}

static int virtual_storage_set_have_guid_flags(struct virtual_mailbox *mbox)
{
    struct virtual_backend_box *const *bboxes;
    unsigned int i, count;
    struct mailbox_status status;

    if (!mbox->box.opened) {
        if (mailbox_open(&mbox->box) < 0)
            return -1;
    }

    mbox->have_guids = TRUE;
    mbox->have_save_guids = TRUE;

    bboxes = array_get(&mbox->backend_boxes, &count);
    for (i = 0; i < count; i++) {
        if (mailbox_get_status(bboxes[i]->box, 0, &status) < 0) {
            const char *errstr;
            enum mail_error error;

            errstr = mailbox_get_last_error(bboxes[i]->box, &error);
            if (error == MAIL_ERROR_NOTFOUND) {
                /* backend mailbox was just lost - skip it */
                continue;
            }
            /* Not expected to happen, but we can't return failure
               since this could be called from
               mailbox_get_open_status() and it would panic.
               So just log the error and skip the mailbox. */
            mail_storage_set_critical(mbox->box.storage,
                "Virtual mailbox %s: Failed to get have_guid existence for backend mailbox %s: %s",
                mailbox_get_vname(&mbox->box),
                mailbox_get_vname(bboxes[i]->box), errstr);
            continue;
        }
        if (!status.have_guids)
            mbox->have_guids = FALSE;
        if (!status.have_save_guids)
            mbox->have_save_guids = FALSE;
    }
    return 0;
}

static int
virtual_storage_get_status(struct mailbox *box,
               enum mailbox_status_items items,
               struct mailbox_status *status_r)
{
    struct virtual_mailbox *mbox = (struct virtual_mailbox *)box;

    if ((items & STATUS_LAST_CACHED_SEQ) != 0)
        items |= STATUS_MESSAGES;

    if (index_storage_get_status(box, items, status_r) < 0)
        return -1;

    if ((items & STATUS_LAST_CACHED_SEQ) != 0) {
        /* Virtual mailboxes have no cached data of their own, so the
           current value is always 0. The most important use for this
           functionality is for "doveadm index" to do FTS indexing and
           it doesn't really matter there if we set this value
           correctly or not. So for now just assume that everything is
           indexed. */
        status_r->last_cached_seq = status_r->messages;
    }
    if (!mbox->have_guid_flags_set) {
        if (virtual_storage_set_have_guid_flags(mbox) < 0)
            return -1;
        mbox->have_guid_flags_set = TRUE;
    }

    if (mbox->have_guids)
        status_r->have_guids = TRUE;
    if (mbox->have_save_guids)
        status_r->have_save_guids = TRUE;
    return 0;
}

static int
virtual_mailbox_get_metadata(struct mailbox *box,
                 enum mailbox_metadata_items items,
                 struct mailbox_metadata *metadata_r)
{
    if (index_mailbox_get_metadata(box, items, metadata_r) < 0)
        return -1;
    if ((items & MAILBOX_METADATA_GUID) != 0) {
        mail_storage_set_error(box->storage, MAIL_ERROR_NOTPOSSIBLE,
                       "Virtual mailboxes have no GUIDs");
        return -1;
    }
    return 0;
}

static void
virtual_notify_callback(struct mailbox *bbox ATTR_UNUSED, struct mailbox *box)
{
    box->notify_callback(box, box->notify_context);
}

static void virtual_notify_changes(struct mailbox *box)
{
    struct virtual_mailbox *mbox = (struct virtual_mailbox *)box;
    struct virtual_backend_box *const *bboxp;

    if (box->notify_callback == NULL) {
        array_foreach(&mbox->backend_boxes, bboxp)
            mailbox_notify_changes_stop((*bboxp)->box);
        return;
    }

    /* FIXME: if mailbox_list_index=yes, use mailbox-list-notify.h API
       to wait for changes and avoid opening all mailboxes here. */

    array_foreach(&mbox->backend_boxes, bboxp) {
        if (!(*bboxp)->box->opened &&
            virtual_backend_box_open(mbox, *bboxp) < 0) {
            /* we can't report error in here, so do it later */
            (*bboxp)->open_failed = TRUE;
            continue;
        }
        mailbox_notify_changes((*bboxp)->box,
                       virtual_notify_callback, box);
    }
}

static void
virtual_get_virtual_uids(struct mailbox *box,
             struct mailbox *backend_mailbox,
             const ARRAY_TYPE(seq_range) *backend_uids,
             ARRAY_TYPE(seq_range) *virtual_uids_r)
{
    struct virtual_mailbox *mbox = (struct virtual_mailbox *)box;
    struct virtual_backend_box *bbox;
    const struct virtual_backend_uidmap *uids;
    struct seq_range_iter iter;
    unsigned int n, i, count;
    uint32_t uid;

    if (mbox->lookup_prev_bbox != NULL &&
        strcmp(mbox->lookup_prev_bbox->box->vname, backend_mailbox->vname) == 0)
        bbox = mbox->lookup_prev_bbox;
    else {
        bbox = virtual_backend_box_lookup_name(mbox, backend_mailbox->vname);
        mbox->lookup_prev_bbox = bbox;
    }
    if (bbox == NULL)
        return;

    uids = array_get(&bbox->uids, &count); i = 0;
    seq_range_array_iter_init(&iter, backend_uids); n = 0;
    while (seq_range_array_iter_nth(&iter, n++, &uid)) {
        while (i < count && uids[i].real_uid < uid) i++;
        if (i < count && uids[i].real_uid == uid) {
            i_assert(uids[i].virtual_uid > 0);
            seq_range_array_add(virtual_uids_r,
                        uids[i].virtual_uid);
            i++;
        }
    }
}

static void
virtual_get_virtual_uid_map(struct mailbox *box,
                struct mailbox *backend_mailbox,
                const ARRAY_TYPE(seq_range) *backend_uids,
                ARRAY_TYPE(uint32_t) *virtual_uids_r)
{
    struct virtual_mailbox *mbox = (struct virtual_mailbox *)box;
    struct virtual_backend_box *bbox;
    const struct virtual_backend_uidmap *uids;
    struct seq_range_iter iter;
    unsigned int n, i, count;
    uint32_t uid;

    if (mbox->lookup_prev_bbox != NULL &&
        strcmp(mbox->lookup_prev_bbox->box->vname, backend_mailbox->vname) == 0)
        bbox = mbox->lookup_prev_bbox;
    else {
        bbox = virtual_backend_box_lookup_name(mbox, backend_mailbox->vname);
        mbox->lookup_prev_bbox = bbox;
    }
    if (bbox == NULL)
        return;

    uids = array_get(&bbox->uids, &count); i = 0;
    seq_range_array_iter_init(&iter, backend_uids); n = 0;
    while (seq_range_array_iter_nth(&iter, n++, &uid)) {
        while (i < count && uids[i].real_uid < uid) i++;
        if (i == count || uids[i].real_uid > uid) {
            uint32_t zero = 0;

            array_append(virtual_uids_r, &zero, 1);
        } else {
            i_assert(uids[i].virtual_uid > 0);
            array_append(virtual_uids_r, &uids[i].virtual_uid, 1);
            i++;
        }
    }
}

static void
virtual_get_virtual_backend_boxes(struct mailbox *box,
                  ARRAY_TYPE(mailboxes) *mailboxes,
                  bool only_with_msgs)
{
    struct virtual_mailbox *mbox = (struct virtual_mailbox *)box;
    struct virtual_backend_box *const *bboxes;
    unsigned int i, count;

    bboxes = array_get(&mbox->backend_boxes, &count);
    for (i = 0; i < count; i++) {
        if (!only_with_msgs || array_count(&bboxes[i]->uids) > 0)
            array_append(mailboxes, &bboxes[i]->box, 1);
    }
}

static bool virtual_is_inconsistent(struct mailbox *box)
{
    struct virtual_mailbox *mbox = (struct virtual_mailbox *)box;

    if (mbox->inconsistent)
        return TRUE;

    return index_storage_is_inconsistent(box);
}

static int
virtual_list_index_has_changed(struct mailbox *box ATTR_UNUSED,
                   struct mail_index_view *list_view ATTR_UNUSED,
                   uint32_t seq ATTR_UNUSED, bool quick ATTR_UNUSED)
{
    /* we don't have any quick and easy optimizations for tracking
       virtual folders. ideally we'd completely disable mailbox list
       indexes for them, but this is the easiest way to do it for now. */
    return 1;
}

static void
virtual_list_index_update_sync(struct mailbox *box ATTR_UNUSED,
                   struct mail_index_transaction *trans ATTR_UNUSED,
                   uint32_t seq ATTR_UNUSED)
{
}

struct mail_storage virtual_storage = {
    .name = VIRTUAL_STORAGE_NAME,
    .class_flags = MAIL_STORAGE_CLASS_FLAG_NOQUOTA,

    .v = {
        NULL,
        virtual_storage_alloc,
        virtual_storage_create,
        index_storage_destroy,
        NULL,
        virtual_storage_get_list_settings,
        NULL,
        virtual_mailbox_alloc,
        NULL,
        NULL,
    }
};

struct mailbox virtual_mailbox = {
    .v = {
        index_storage_is_readonly,
        index_storage_mailbox_enable,
        virtual_mailbox_exists,
        virtual_mailbox_open,
        virtual_mailbox_close,
        virtual_mailbox_free,
        virtual_mailbox_create,
        virtual_mailbox_update,
        index_storage_mailbox_delete,
        index_storage_mailbox_rename,
        virtual_storage_get_status,
        virtual_mailbox_get_metadata,
        index_storage_set_subscribed,
        index_storage_attribute_set,
        index_storage_attribute_get,
        index_storage_attribute_iter_init,
        index_storage_attribute_iter_next,
        index_storage_attribute_iter_deinit,
        virtual_list_index_has_changed,
        virtual_list_index_update_sync,
        virtual_storage_sync_init,
        index_mailbox_sync_next,
        index_mailbox_sync_deinit,
        NULL,
        virtual_notify_changes,
        virtual_transaction_begin,
        virtual_transaction_commit,
        virtual_transaction_rollback,
        NULL,
        virtual_mail_alloc,
        virtual_search_init,
        virtual_search_deinit,
        virtual_search_next_nonblock,
        virtual_search_next_update_seq,
        virtual_save_alloc,
        virtual_save_begin,
        virtual_save_continue,
        virtual_save_finish,
        virtual_save_cancel,
        mail_storage_copy,
        NULL,
        NULL,
        NULL,
        virtual_is_inconsistent
    }
};

struct virtual_mailbox_vfuncs virtual_mailbox_vfuncs = {
    virtual_get_virtual_uids,
    virtual_get_virtual_uid_map,
    virtual_get_virtual_backend_boxes
};