src/lib-index/mail-cache-lookup.c

	mail-cache-lookup.c revision 45324f1eafa565dbc65e4dd335de9507dead55e6
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn/* Copyright (c) 2003-2014 Dovecot authors, see the included COPYING file */
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn#include "lib.h"
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn#include "array.h"
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn#include "buffer.h"
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn#include "str.h"
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn#include "mail-cache-private.h"
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn#include <stdlib.h>
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn#define CACHE_PREFETCH IO_BLOCK_SIZE
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallynint mail_cache_get_record(struct mail_cache *cache, uint32_t offset,
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn              const struct mail_cache_record **rec_r)
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn{
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    const struct mail_cache_record *rec;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    const void *data;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    int ret;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    i_assert(offset != 0);
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    if (offset % sizeof(uint32_t) != 0) {
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        /* records are always 32-bit aligned */
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        mail_cache_set_corrupted(cache, "invalid record offset");
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        return -1;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    }
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    /* we don't know yet how large the record is, so just guess */
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    if (mail_cache_map(cache, offset, sizeof(*rec) + CACHE_PREFETCH,
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn               &data) < 0)
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        return -1;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    if (offset + sizeof(*rec) > cache->mmap_length) {
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        mail_cache_set_corrupted(cache, "record points outside file");
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        return -1;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    }
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    rec = data;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    if (rec->size < sizeof(*rec)) {
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        mail_cache_set_corrupted(cache, "invalid record size");
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        return -1;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    }
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    if (rec->size > CACHE_PREFETCH) {
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        /* larger than we guessed. map the rest of the record. */
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        if ((ret = mail_cache_map(cache, offset, rec->size, &data)) < 0)
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn            return -1;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        if (ret == 0) {
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn            mail_cache_set_corrupted(cache, "record points outside file");
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn            return -1;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        }
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        rec = data;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    }
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    *rec_r = rec;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    return 0;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn}
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallynuint32_t mail_cache_lookup_cur_offset(struct mail_index_view *view,
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn                      uint32_t seq, uint32_t *reset_id_r)
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn{
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    struct mail_cache *cache = mail_index_view_get_index(view)->cache;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    struct mail_index_map *map;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    const void *data;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    uint32_t offset;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    mail_index_lookup_ext_full(view, seq, cache->ext_id, &map, &data, NULL);
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    if (data == NULL) {
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        /* no cache offsets */
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        return 0;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    }
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    offset = *((const uint32_t *)data);
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    if (offset == 0)
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        return 0;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    if (!mail_index_ext_get_reset_id(view, map, cache->ext_id, reset_id_r))
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        i_unreached();
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    return offset;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn}
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallynstatic int
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallynmail_cache_lookup_offset(struct mail_cache *cache, struct mail_index_view *view,
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn             uint32_t seq, uint32_t *offset_r)
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn{
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    uint32_t offset, reset_id;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    int i, ret;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    offset = mail_cache_lookup_cur_offset(view, seq, &reset_id);
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    if (offset == 0)
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        return 0;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    /* reset_id must match file_seq or the offset is for a different cache
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn       file. if this happens, try if reopening the cache helps. if not,
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn       it was probably for an old cache file that's already lost by now. */
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    i = 0;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    while (cache->hdr->file_seq != reset_id) {
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        if (++i == 2 || reset_id < cache->hdr->file_seq)
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn            return 0;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        if (cache->locked) {
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn            /* we're probably compressing */
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn            return 0;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        }
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        if ((ret = mail_cache_reopen(cache)) <= 0) {
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn            /* error / we already have the latest file open */
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn            return ret;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        }
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    }
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    *offset_r = offset;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    return 1;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn}
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallynbool mail_cache_track_loops(struct mail_cache_loop_track *loop_track,
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn                uoff_t offset, uoff_t size)
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn{
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    i_assert(offset != 0);
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    i_assert(size != 0);
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    /* looping happens only in rare error conditions, so it's enough if we
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn       just catch it eventually. we do this by checking if we've seen
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn       more record data than possible in the accessed file area. */
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    if (loop_track->size_sum == 0) {
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        /* first call */
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        loop_track->min_offset = offset;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        loop_track->max_offset = offset + size;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    } else {
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        if (loop_track->min_offset > offset)
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn            loop_track->min_offset = offset;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn        if (loop_track->max_offset < offset + size)
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn            loop_track->max_offset = offset + size;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    }
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    loop_track->size_sum += size;
198b363fff1de9afcee2f26b9aa847316f589afeSerge Hallyn    return loop_track->size_sum >
        (loop_track->max_offset - loop_track->min_offset);
}

void mail_cache_lookup_iter_init(struct mail_cache_view *view, uint32_t seq,
                 struct mail_cache_lookup_iterate_ctx *ctx_r)
{
    struct mail_cache_lookup_iterate_ctx *ctx = ctx_r;
    int ret;

    if (!view->cache->opened)
        (void)mail_cache_open_and_verify(view->cache);

    memset(ctx, 0, sizeof(*ctx));
    ctx->view = view;
    ctx->seq = seq;

    if (!MAIL_CACHE_IS_UNUSABLE(view->cache)) {
        /* look up the first offset */
        ret = mail_cache_lookup_offset(view->cache, view->view, seq,
                           &ctx->offset);
        if (ret <= 0) {
            ctx->stop = TRUE;
            ctx->failed = ret < 0;
        }
    }
    ctx->remap_counter = view->cache->remap_counter;

    memset(&view->loop_track, 0, sizeof(view->loop_track));
}

static bool
mail_cache_lookup_iter_transaction(struct mail_cache_lookup_iterate_ctx *ctx)
{
    ctx->rec = mail_cache_transaction_lookup_rec(ctx->view->transaction,
                             ctx->seq,
                             &ctx->trans_next_idx);
    if (ctx->rec == NULL)
        return FALSE;

    ctx->remap_counter = ctx->view->cache->remap_counter;
    ctx->pos = sizeof(*ctx->rec);
    ctx->rec_size = ctx->rec->size;
    return TRUE;
}

static int
mail_cache_lookup_iter_next_record(struct mail_cache_lookup_iterate_ctx *ctx)
{
    struct mail_cache_view *view = ctx->view;

    if (ctx->failed)
        return -1;

    if (ctx->rec != NULL)
        ctx->offset = ctx->rec->prev_offset;
    if (ctx->offset == 0) {
        /* end of this record list. check newly appended data. */
        if (view->trans_seq1 > ctx->seq ||
            view->trans_seq2 < ctx->seq)
            return 0;
        /* check data still in memory. this works for recent mails
           even with INDEX=MEMORY */
        if (!ctx->memory_appends_checked) {
            if (mail_cache_lookup_iter_transaction(ctx))
                return 1;
            ctx->memory_appends_checked = TRUE;
        }
        if (MAIL_CACHE_IS_UNUSABLE(view->cache))
            return 0;

        /* check data already written to cache file */
        if (ctx->disk_appends_checked ||
            mail_cache_lookup_offset(view->cache, view->trans_view,
                         ctx->seq, &ctx->offset) <= 0)
            return 0;

        ctx->disk_appends_checked = TRUE;
        ctx->remap_counter = view->cache->remap_counter;
        memset(&view->loop_track, 0, sizeof(view->loop_track));
    }

    if (ctx->stop)
        return 0;

    /* look up the next record */
    if (mail_cache_get_record(view->cache, ctx->offset, &ctx->rec) < 0)
        return -1;
    if (mail_cache_track_loops(&view->loop_track, ctx->offset,
                   ctx->rec->size)) {
        mail_cache_set_corrupted(view->cache,
                     "record list is circular");
        return -1;
    }
    ctx->remap_counter = view->cache->remap_counter;

    ctx->pos = sizeof(*ctx->rec);
    ctx->rec_size = ctx->rec->size;
    return 1;
}

int mail_cache_lookup_iter_next(struct mail_cache_lookup_iterate_ctx *ctx,
                struct mail_cache_iterate_field *field_r)
{
    struct mail_cache *cache = ctx->view->cache;
    unsigned int field_idx;
    unsigned int data_size;
    uint32_t file_field;
    int ret;

    i_assert(ctx->remap_counter == cache->remap_counter);

    if (ctx->pos + sizeof(uint32_t) > ctx->rec_size) {
        if (ctx->pos != ctx->rec_size) {
            mail_cache_set_corrupted(cache,
                "record has invalid size");
            return -1;
        }

        if ((ret = mail_cache_lookup_iter_next_record(ctx)) <= 0)
            return ret;
    }

    /* return the next field */
    file_field = *((const uint32_t *)CONST_PTR_OFFSET(ctx->rec, ctx->pos));
    ctx->pos += sizeof(uint32_t);

    if (file_field >= cache->file_fields_count) {
        /* new field, have to re-read fields header to figure
           out its size. don't do this if we're compressing. */
        if (!cache->locked) {
            if (mail_cache_header_fields_read(cache) < 0)
                return -1;
        }
        if (file_field >= cache->file_fields_count) {
            mail_cache_set_corrupted(cache,
                "field index too large (%u >= %u)",
                file_field, cache->file_fields_count);
            return -1;
        }

        /* field reading might have re-mmaped the file and
           caused rec pointer to break. need to get it again. */
        if (mail_cache_get_record(cache, ctx->offset, &ctx->rec) < 0)
            return -1;
        ctx->remap_counter = cache->remap_counter;
    }

    field_idx = cache->file_field_map[file_field];
    data_size = cache->fields[field_idx].field.field_size;
    if (data_size == UINT_MAX &&
        ctx->pos + sizeof(uint32_t) <= ctx->rec->size) {
        /* variable size field. get its size from the file. */
        data_size = *((const uint32_t *)
                  CONST_PTR_OFFSET(ctx->rec, ctx->pos));
        ctx->pos += sizeof(uint32_t);
    }

    if (ctx->rec->size - ctx->pos < data_size) {
        mail_cache_set_corrupted(cache,
            "record continues outside its allocated size");
        return -1;
    }

    field_r->field_idx = field_idx;
    field_r->data = CONST_PTR_OFFSET(ctx->rec, ctx->pos);
    field_r->size = data_size;
    field_r->offset = ctx->offset + ctx->pos;

    /* each record begins from 32bit aligned position */
    ctx->pos += (data_size + sizeof(uint32_t)-1) & ~(sizeof(uint32_t)-1);
    return 1;
}

static int mail_cache_seq(struct mail_cache_view *view, uint32_t seq)
{
    struct mail_cache_lookup_iterate_ctx iter;
    struct mail_cache_iterate_field field;
    int ret;

    if (++view->cached_exists_value == 0) {
        /* wrapped, we'll have to clear the buffer */
        buffer_reset(view->cached_exists_buf);
        view->cached_exists_value++;
    }
    view->cached_exists_seq = seq;

    mail_cache_lookup_iter_init(view, seq, &iter);
    while ((ret = mail_cache_lookup_iter_next(&iter, &field)) > 0) {
        buffer_write(view->cached_exists_buf, field.field_idx,
                 &view->cached_exists_value, 1);
    }
    return ret;
}

static bool
mail_cache_file_has_field(struct mail_cache *cache, unsigned int field)
{
    i_assert(field < cache->fields_count);
    return cache->field_file_map[field] != (uint32_t)-1;
}

int mail_cache_field_exists(struct mail_cache_view *view, uint32_t seq,
                unsigned int field)
{
    const uint8_t *data;

    i_assert(seq > 0);

    if (!view->cache->opened)
        (void)mail_cache_open_and_verify(view->cache);

    if (!mail_cache_file_has_field(view->cache, field))
        return 0;

    /* FIXME: we should discard the cache if view has been synced */
    if (view->cached_exists_seq != seq) {
        if (mail_cache_seq(view, seq) < 0)
            return -1;
    }

    data = view->cached_exists_buf->data;
    return (field < view->cached_exists_buf->used &&
        data[field] == view->cached_exists_value) ? 1 : 0;
}

bool mail_cache_field_exists_any(struct mail_cache_view *view, uint32_t seq)
{
    uint32_t reset_id;

    return mail_cache_lookup_cur_offset(view->view, seq, &reset_id) != 0;
}

enum mail_cache_decision_type
mail_cache_field_get_decision(struct mail_cache *cache, unsigned int field_idx)
{
    i_assert(field_idx < cache->fields_count);

    return cache->fields[field_idx].field.decision;
}

static int
mail_cache_lookup_bitmask(struct mail_cache_lookup_iterate_ctx *iter,
              unsigned int field_idx, unsigned int field_size,
              buffer_t *dest_buf)
{
    struct mail_cache_iterate_field field;
    const unsigned char *src;
    unsigned char *dest;
    unsigned int i;
    bool found = FALSE;
    int ret;

    /* make sure all bits are cleared first */
    buffer_write_zero(dest_buf, 0, field_size);

    while ((ret = mail_cache_lookup_iter_next(iter, &field)) > 0) {
        if (field.field_idx != field_idx)
            continue;

        /* merge all bits */
        src = field.data;
        dest = buffer_get_space_unsafe(dest_buf, 0, field.size);
        for (i = 0; i < field.size; i++)
            dest[i] |= src[i];
        found = TRUE;
    }
    return ret < 0 ? -1 : (found ? 1 : 0);
}

int mail_cache_lookup_field(struct mail_cache_view *view, buffer_t *dest_buf,
                uint32_t seq, unsigned int field_idx)
{
    const struct mail_cache_field *field_def;
    struct mail_cache_lookup_iterate_ctx iter;
    struct mail_cache_iterate_field field;
    int ret;

    ret = mail_cache_field_exists(view, seq, field_idx);
    mail_cache_decision_state_update(view, seq, field_idx);
    if (ret <= 0)
        return ret;

    /* the field should exist */
    mail_cache_lookup_iter_init(view, seq, &iter);
    field_def = &view->cache->fields[field_idx].field;
    if (field_def->type == MAIL_CACHE_FIELD_BITMASK) {
        return mail_cache_lookup_bitmask(&iter, field_idx,
                         field_def->field_size,
                         dest_buf);
    }

    /* return the first one that's found. if there are multiple
       they're all identical. */
    while ((ret = mail_cache_lookup_iter_next(&iter, &field)) > 0) {
        if (field.field_idx == field_idx) {
            buffer_append(dest_buf, field.data, field.size);
            break;
        }
    }
    return ret;
}

struct header_lookup_data {
    uint32_t data_size;
    const unsigned char *data;
};

struct header_lookup_line {
    uint32_t line_num;
    struct header_lookup_data *data;
};

struct header_lookup_context {
    struct mail_cache_view *view;
    pool_t pool;
    ARRAY(struct header_lookup_line) lines;
};

enum {
    HDR_FIELD_STATE_DONTWANT = 0,
    HDR_FIELD_STATE_WANT,
    HDR_FIELD_STATE_SEEN
};

static void header_lines_save(struct header_lookup_context *ctx,
                  const struct mail_cache_iterate_field *field)
{
    const uint32_t *lines = field->data;
    uint32_t data_size = field->size;
    struct header_lookup_line hdr_line;
        struct header_lookup_data *hdr_data;
    void *data_dup;
    unsigned int i, lines_count, pos;

    /* data = { line_nums[], 0, "headers" } */
    for (i = 0; data_size >= sizeof(uint32_t); i++) {
        data_size -= sizeof(uint32_t);
        if (lines[i] == 0)
            break;
    }
    lines_count = i;
    pos = (lines_count+1) * sizeof(uint32_t);

    hdr_data = p_new(ctx->pool, struct header_lookup_data, 1);
    hdr_data->data_size = data_size;
    hdr_data->data = data_dup = data_size == 0 ? NULL :
        p_malloc(ctx->pool, data_size);
    memcpy(data_dup, CONST_PTR_OFFSET(field->data, pos), data_size);

    for (i = 0; i < lines_count; i++) {
        hdr_line.line_num = lines[i];
        hdr_line.data = hdr_data;
        array_append(&ctx->lines, &hdr_line, 1);
    }
}

static int header_lookup_line_cmp(const struct header_lookup_line *l1,
                  const struct header_lookup_line *l2)
{
    return (int)l1->line_num - (int)l2->line_num;
}

static int
mail_cache_lookup_headers_real(struct mail_cache_view *view, string_t *dest,
                   uint32_t seq, unsigned int field_idxs[],
                   unsigned int fields_count, pool_t *pool_r)
{
    struct mail_cache *cache = view->cache;
    struct mail_cache_lookup_iterate_ctx iter;
    struct mail_cache_iterate_field field;
    struct header_lookup_context ctx;
    struct header_lookup_line *lines;
    const unsigned char *p, *start, *end;
    uint8_t *field_state;
    unsigned int i, count, max_field = 0;
    size_t hdr_size;
    uint8_t want = HDR_FIELD_STATE_WANT;
    buffer_t *buf;
    int ret;

    *pool_r = NULL;

    if (fields_count == 0)
        return 1;

    if (!view->cache->opened)
        (void)mail_cache_open_and_verify(view->cache);

    /* update the decision state regardless of whether the fields
       actually exist or not. */
    for (i = 0; i < fields_count; i++)
        mail_cache_decision_state_update(view, seq, field_idxs[i]);

    /* mark all the fields we want to find. */
    buf = buffer_create_dynamic(pool_datastack_create(), 32);
    for (i = 0; i < fields_count; i++) {
        if (!mail_cache_file_has_field(cache, field_idxs[i]))
            return 0;

        if (field_idxs[i] > max_field)
            max_field = field_idxs[i];

        buffer_write(buf, field_idxs[i], &want, 1);
    }
    field_state = buffer_get_modifiable_data(buf, NULL);

    /* lookup the fields */
    memset(&ctx, 0, sizeof(ctx));
    ctx.view = view;
    ctx.pool = *pool_r = pool_alloconly_create(MEMPOOL_GROWING"mail cache headers", 1024);
    t_array_init(&ctx.lines, 32);

    mail_cache_lookup_iter_init(view, seq, &iter);
    while ((ret = mail_cache_lookup_iter_next(&iter, &field)) > 0) {
        if (field.field_idx > max_field ||
            field_state[field.field_idx] != HDR_FIELD_STATE_WANT) {
            /* a) don't want it, b) duplicate */
        } else {
            field_state[field.field_idx] = HDR_FIELD_STATE_SEEN;
            header_lines_save(&ctx, &field);
        }

    }
    if (ret < 0)
        return -1;

    /* check that all fields were found */
    for (i = 0; i <= max_field; i++) {
        if (field_state[i] == HDR_FIELD_STATE_WANT)
            return 0;
    }

    /* we need to return headers in the order they existed originally.
       we can do this by sorting the messages by their line numbers. */
    array_sort(&ctx.lines, header_lookup_line_cmp);
    lines = array_get_modifiable(&ctx.lines, &count);

    /* then start filling dest buffer from the headers */
    for (i = 0; i < count; i++) {
        start = lines[i].data->data;
        end = start + lines[i].data->data_size;

        /* find the end of the (multiline) header */
        for (p = start; p != end; p++) {
            if (*p == '\n' &&
                (p+1 == end || (p[1] != ' ' && p[1] != '\t'))) {
                p++;
                break;
            }
        }
        hdr_size = (size_t)(p - start);
        buffer_append(dest, start, hdr_size);

        /* if there are more lines for this header, the following lines
           continue after this one. so skip this line. */
        lines[i].data->data += hdr_size;
        lines[i].data->data_size -= hdr_size;
    }
    return 1;
}

int mail_cache_lookup_headers(struct mail_cache_view *view, string_t *dest,
                  uint32_t seq, unsigned int field_idxs[],
                  unsigned int fields_count)
{
    pool_t pool;
    int ret;

    T_BEGIN {
        ret = mail_cache_lookup_headers_real(view, dest, seq,
                             field_idxs, fields_count,
                             &pool);
        if (pool != NULL)
            pool_unref(&pool);
    } T_END;
    return ret;
}