mail-cache-lookup.c revision adef31eb09ce4092968afc81680524ffb626b21e
baf6671fd3847865da9b64dc8f8be85d81304840Daniel Lezcano/* Copyright (c) 2003-2017 Dovecot authors, see the included COPYING file */
baf6671fd3847865da9b64dc8f8be85d81304840Daniel Lezcano
892bd61e0fcc788390abfadd32b1897943290879dlezcano#include "lib.h"
5c320b769229d713e84b02ed6b7ae1309ac31dbbGuido Trotter#include "array.h"
5c320b769229d713e84b02ed6b7ae1309ac31dbbGuido Trotter#include "buffer.h"
5c320b769229d713e84b02ed6b7ae1309ac31dbbGuido Trotter#include "str.h"
892bd61e0fcc788390abfadd32b1897943290879dlezcano#include "mail-cache-private.h"
d1de19abd0067f38bc08a4a3357de701a4e5571ddlezcano
d1de19abd0067f38bc08a4a3357de701a4e5571ddlezcano
11cddd70eb8c285287b73562ba4208d74e1b9fdeSerge Hallyn#define CACHE_PREFETCH IO_BLOCK_SIZE
d1de19abd0067f38bc08a4a3357de701a4e5571ddlezcano
d1de19abd0067f38bc08a4a3357de701a4e5571ddlezcanoint mail_cache_get_record(struct mail_cache *cache, uint32_t offset,
d1de19abd0067f38bc08a4a3357de701a4e5571ddlezcano const struct mail_cache_record **rec_r)
d1de19abd0067f38bc08a4a3357de701a4e5571ddlezcano{
d1de19abd0067f38bc08a4a3357de701a4e5571ddlezcano const struct mail_cache_record *rec;
396639d4247ffd9aaf09a814305fd1d57fef7b58Daniel Lezcano const void *data;
396639d4247ffd9aaf09a814305fd1d57fef7b58Daniel Lezcano int ret;
b0a33c1eb65d2c87e886c740a0dadd8ad5f8d87ddlezcano
d1de19abd0067f38bc08a4a3357de701a4e5571ddlezcano i_assert(offset != 0);
d1de19abd0067f38bc08a4a3357de701a4e5571ddlezcano
810567bbbe283c547e4ac837545d1e592916df26Serge Hallyn if (offset % sizeof(uint32_t) != 0) {
d1de19abd0067f38bc08a4a3357de701a4e5571ddlezcano /* records are always 32-bit aligned */
d1de19abd0067f38bc08a4a3357de701a4e5571ddlezcano mail_cache_set_corrupted(cache, "invalid record offset");
b0e505c974ff7b018350f99f32199a52e18ed55bdlezcano return -1;
8a67a2b2eaf28033962a432c214bd3303c29c54cdlezcano }
e4b3fe5833cf5e8cb85389ceed8a00254c87b01fgkurz@linux.vnet.ibm.com
49ee6cdcbf79d8b6fa617479ec8ab753ccca923dChristian Seiler /* we don't know yet how large the record is, so just guess */
8a67a2b2eaf28033962a432c214bd3303c29c54cdlezcano if (mail_cache_map(cache, offset, sizeof(*rec) + CACHE_PREFETCH,
8b8b04f80adf21480c25deb1aae263049ddd6754dlezcano &data) < 0)
8b8b04f80adf21480c25deb1aae263049ddd6754dlezcano return -1;
8b8b04f80adf21480c25deb1aae263049ddd6754dlezcano
d1de19abd0067f38bc08a4a3357de701a4e5571ddlezcano if (offset + sizeof(*rec) > cache->mmap_length) {
6a85cf91247b7dd9c3faeddceca8dacb96d02cd6Stéphane Graber mail_cache_set_corrupted(cache, "record points outside file");
6a85cf91247b7dd9c3faeddceca8dacb96d02cd6Stéphane Graber return -1;
6a85cf91247b7dd9c3faeddceca8dacb96d02cd6Stéphane Graber }
6a85cf91247b7dd9c3faeddceca8dacb96d02cd6Stéphane Graber rec = data;
6a85cf91247b7dd9c3faeddceca8dacb96d02cd6Stéphane Graber
d1de19abd0067f38bc08a4a3357de701a4e5571ddlezcano if (rec->size < sizeof(*rec)) {
f080ffd7d656fbd9505a8e8eb52a05d61355c677Dwight Engen mail_cache_set_corrupted(cache, "invalid record size");
f080ffd7d656fbd9505a8e8eb52a05d61355c677Dwight Engen return -1;
f080ffd7d656fbd9505a8e8eb52a05d61355c677Dwight Engen }
f080ffd7d656fbd9505a8e8eb52a05d61355c677Dwight Engen if (rec->size > CACHE_PREFETCH) {
aa8d013ec5b09cd1cd904173d6234ef126eb2126Peter Simons /* larger than we guessed. map the rest of the record. */
7822022c4c72cee06905b540b89b653491d6f6b2Stéphane Graber if ((ret = mail_cache_map(cache, offset, rec->size, &data)) < 0)
6a85cf91247b7dd9c3faeddceca8dacb96d02cd6Stéphane Graber return -1;
8a67a2b2eaf28033962a432c214bd3303c29c54cdlezcano if (ret == 0) {
aa8d013ec5b09cd1cd904173d6234ef126eb2126Peter Simons mail_cache_set_corrupted(cache, "record points outside file");
7822022c4c72cee06905b540b89b653491d6f6b2Stéphane Graber return -1;
6a85cf91247b7dd9c3faeddceca8dacb96d02cd6Stéphane Graber }
8a67a2b2eaf28033962a432c214bd3303c29c54cdlezcano rec = data;
aa8d013ec5b09cd1cd904173d6234ef126eb2126Peter Simons }
7822022c4c72cee06905b540b89b653491d6f6b2Stéphane Graber
6a85cf91247b7dd9c3faeddceca8dacb96d02cd6Stéphane Graber *rec_r = rec;
99e4008cad9e959b683c6f48411fcf15a92be3b5Michel Normand return 0;
10fba81b9d0221b8e47aa1e0b43236413b7d28dfMichel Normand}
8b8b04f80adf21480c25deb1aae263049ddd6754dlezcano
5c320b769229d713e84b02ed6b7ae1309ac31dbbGuido Trotteruint32_t mail_cache_lookup_cur_offset(struct mail_index_view *view,
3b9246c4aae3f7602c0ad64f5b1204eb559e5b07Daniel Lezcano uint32_t seq, uint32_t *reset_id_r)
892bd61e0fcc788390abfadd32b1897943290879dlezcano{
struct mail_cache *cache = mail_index_view_get_index(view)->cache;
struct mail_index_map *map;
const void *data;
uint32_t offset;
mail_index_lookup_ext_full(view, seq, cache->ext_id, &map, &data, NULL);
if (data == NULL) {
/* no cache offsets */
return 0;
}
offset = *((const uint32_t *)data);
if (offset == 0)
return 0;
if (!mail_index_ext_get_reset_id(view, map, cache->ext_id, reset_id_r))
i_unreached();
return offset;
}
static int
mail_cache_lookup_offset(struct mail_cache *cache, struct mail_index_view *view,
uint32_t seq, uint32_t *offset_r)
{
uint32_t offset, reset_id;
int i, ret;
offset = mail_cache_lookup_cur_offset(view, seq, &reset_id);
if (offset == 0)
return 0;
/* reset_id must match file_seq or the offset is for a different cache
file. if this happens, try if reopening the cache helps. if not,
it was probably for an old cache file that's already lost by now. */
i = 0;
while (cache->hdr->file_seq != reset_id) {
if (++i == 2 || reset_id < cache->hdr->file_seq)
return 0;
if (cache->locked) {
/* we're probably compressing */
return 0;
}
if ((ret = mail_cache_reopen(cache)) <= 0) {
/* error / we already have the latest file open */
return ret;
}
}
*offset_r = offset;
return 1;
}
bool mail_cache_track_loops(struct mail_cache_loop_track *loop_track,
uoff_t offset, uoff_t size)
{
i_assert(offset != 0);
i_assert(size != 0);
/* looping happens only in rare error conditions, so it's enough if we
just catch it eventually. we do this by checking if we've seen
more record data than possible in the accessed file area. */
if (loop_track->size_sum == 0) {
/* first call */
loop_track->min_offset = offset;
loop_track->max_offset = offset + size;
} else {
if (loop_track->min_offset > offset)
loop_track->min_offset = offset;
if (loop_track->max_offset < offset + size)
loop_track->max_offset = offset + size;
}
loop_track->size_sum += size;
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);
i_zero(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;
i_zero(&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) || ctx->stop)
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;
i_zero(&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_set_used_size(view->cached_exists_buf, 0);
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;
if (data_size > 0) {
hdr_data->data = data_dup =
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 */
i_zero(&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;
}
static uint32_t
mail_cache_get_highest_seq_with_cache(struct mail_cache_view *view,
uint32_t below_seq, uint32_t *reset_id_r)
{
uint32_t seq;
/* find the newest mail that has anything in cache */
for (seq = below_seq-1; seq > 0; seq--) {
if (mail_cache_lookup_cur_offset(view->view, seq, reset_id_r) != 0)
return seq;
}
return 0;
}
const char *
mail_cache_get_missing_reason(struct mail_cache_view *view, uint32_t seq)
{
uint32_t offset, reset_id;
if (MAIL_CACHE_IS_UNUSABLE(view->cache))
return "Cache file is unusable";
offset = mail_cache_lookup_cur_offset(view->view, seq, &reset_id);
if (offset != 0) {
if (view->cache->hdr->file_seq != reset_id) {
return t_strdup_printf(
"Index reset_id=%u doesn't match cache reset_id=%u",
reset_id, view->cache->hdr->file_seq);
}
return t_strdup_printf(
"Mail has other cached fields, reset_id=%u", reset_id);
}
seq = mail_cache_get_highest_seq_with_cache(view, seq, &reset_id);
if (seq == 0) {
return t_strdup_printf("Cache file is empty, reset_id=%u",
view->cache->hdr->file_seq);
}
uint32_t uid;
mail_index_lookup_uid(view->view, seq, &uid);
if (view->cache->hdr->file_seq != reset_id) {
return t_strdup_printf(
"Mail not cached, highest cached seq=%u uid=%u: "
"Index reset_id=%u doesn't match cache reset_id=%u",
seq, uid, reset_id, view->cache->hdr->file_seq);
}
return t_strdup_printf(
"Mail not cached, highest cached seq=%u uid=%u: reset_id=%u",
seq, uid, reset_id);
}