[dovecot-cvs] dovecot/src/lib-index Makefile.am, 1.30, 1.31 mailbox-list-index-private.h, NONE, 1.1 mailbox-list-index-sync.c, NONE, 1.1 mailbox-list-index.c, NONE, 1.1 mailbox-list-index.h, NONE, 1.1

[tss at dovecot.org]

Update of /var/lib/cvs/dovecot/src/lib-index
In directory talvi:/tmp/cvs-serv28938/lib-index

Modified Files:
	Makefile.am 
Added Files:
	mailbox-list-index-private.h mailbox-list-index-sync.c 
	mailbox-list-index.c mailbox-list-index.h 
Log Message:
Mailbox list indexing and related changes. Currently works only with
maildir and mmap_disable=no. This allows doing STATUS to synced mailboxes
without opening their index files at all.



Index: Makefile.am
===================================================================
RCS file: /var/lib/cvs/dovecot/src/lib-index/Makefile.am,v
retrieving revision 1.30
retrieving revision 1.31
diff -u -d -r1.30 -r1.31
--- Makefile.am	15 Oct 2006 12:25:39 -0000	1.30
+++ Makefile.am	25 Nov 2006 22:17:40 -0000	1.31
@@ -28,7 +28,9 @@
         mail-transaction-log.c \
         mail-transaction-log-append.c \
         mail-transaction-log-view.c \
-        mail-transaction-util.c
+        mail-transaction-util.c \
+        mailbox-list-index.c \
+        mailbox-list-index-sync.c
 
 noinst_HEADERS = \
 	mail-cache.h \
@@ -41,4 +43,6 @@
 	mail-index-view-private.h \
         mail-transaction-log.h \
 	mail-transaction-log-private.h \
-        mail-transaction-util.h
+        mail-transaction-util.h \
+        mailbox-list-index.h \
+        mailbox-list-index-private.h

--- NEW FILE: mailbox-list-index-private.h ---
#ifndef __MAILBOX_LIST_INDEX_PRIVATE_H
#define __MAILBOX_LIST_INDEX_PRIVATE_H

#include "mailbox-list-index.h"

#define MAILBOX_LIST_INDEX_MAJOR_VERSION 1
#define MAILBOX_LIST_INDEX_MINOR_VERSION 0

struct mailbox_list_index_header {
	uint8_t major_version;
	uint8_t minor_version;
	uint8_t unused[2];

	uint32_t header_size;
	uint32_t uid_validity;

	/* locking required to access the fields below: */
	uint32_t next_uid;

	uint32_t used_space;
	uint32_t deleted_space;
};

struct mailbox_list_dir_record {
	/* If non-zero, contains a pointer to updated directory list.
	   Stored using mail_index_uint32_to_offset(). */
	uint32_t next_offset;

	uint32_t count;
	/* The records are sorted by their name_hash */
	/* struct mailbox_list_record records[count]; */
};

struct mailbox_list_record {
	/* CRC32 hash of the name */
	uint32_t name_hash;
	uint32_t uid:31;
	/* Set when this record has been marked as deleted. It will be removed
	   permanently the next time a new record is added to this directory
	   or on the next index compression. */
	uint32_t deleted:1;

	/* Points to a NUL-terminated record name */
	uint32_t name_offset;
	/* the dir offset is stored using mail_index_uint32_to_offset()
	   since it may change while we're reading */
	uint32_t dir_offset;
};

struct mailbox_list_index {
	char *filepath;
	char separator;
	struct mail_index *mail_index;

	int fd;

	void *mmap_base;
	size_t mmap_size;
	const struct mailbox_list_index_header *hdr;
};

#define MAILBOX_LIST_RECORDS(dir) \
	((struct mailbox_list_record *)(dir + 1))
#define MAILBOX_LIST_RECORD_IDX(dir, rec) \
	((rec) - MAILBOX_LIST_RECORDS(dir))

int mailbox_list_index_set_syscall_error(struct mailbox_list_index *index,
					 const char *function);

int mailbox_list_index_dir_lookup_rec(struct mailbox_list_index *index,
				      const struct mailbox_list_dir_record *dir,
				      const char *name,
				      const struct mailbox_list_record **rec_r);
int mailbox_list_index_get_dir(struct mailbox_list_index *index,
			       uint32_t *offset,
			       const struct mailbox_list_dir_record **dir_r);
int mailbox_list_index_map(struct mailbox_list_index *index);

#endif

--- NEW FILE: mailbox-list-index-sync.c ---
/* Copyright (C) 2006 Timo Sirainen */

#include "lib.h"
#include "array.h"
#include "bsearch-insert-pos.h"
#include "crc32.h"
#include "file-set-size.h"
#include "mmap-util.h"
#include "mail-index-private.h"
#include "mailbox-list-index-private.h"

#include <stddef.h>

#define ROOT_INIT_COUNT 128
#define DIR_ALLOC_MORE_COUNT 4
#define MAILBOX_LIST_INDEX_GROW_PERCENTAGE 10
#define MAILBOX_LIST_INDEX_MIN_SIZE 512

struct mailbox_list_sync_record {
	uint32_t name_hash;
	uint32_t seq;
	uint32_t uid;
	const char *name;

	/* dir is used if it's non-NULL, otherwise dir_offset is used */
	struct mailbox_list_sync_dir *dir;
	uint32_t dir_offset;

	uint32_t created:1;
	uint32_t seen:1;
};

struct mailbox_list_sync_dir {
	/* The records are sorted by their name_hash */
	ARRAY_DEFINE(records, struct mailbox_list_sync_record);

	/* Offset to the original location in the index, or 0 for new dirs */
	uint32_t offset;
	unsigned int seen_records_count;
	unsigned int new_records_count;
};

struct mailbox_list_index_sync_ctx {
	struct mailbox_list_index *index;
	pool_t pool;

	enum mailbox_list_sync_flags flags;
	const char *sync_path;
	struct mail_index_sync_ctx *mail_sync_ctx;
	struct mail_index_view *view;
	struct mail_index_transaction *trans;

	struct mailbox_list_index_header hdr;
	struct mailbox_list_sync_dir *root, *sync_root;

	unsigned int failed:1;
	unsigned int partial:1;
	unsigned int seen_sync_root:1;
};

struct mailbox_list_sync_lookup_key {
	uint32_t name_hash;
	const char *name;
	bool *match;
};

static struct mailbox_list_sync_dir *
mailbox_list_alloc_sync_dir(struct mailbox_list_index_sync_ctx *ctx,
			    unsigned int initial_count)
{
	struct mailbox_list_sync_dir *sync_dir;

	sync_dir = p_new(ctx->pool, struct mailbox_list_sync_dir, 1);
	p_array_init(&sync_dir->records, ctx->pool, initial_count);
	return sync_dir;
}

static int
mailbox_list_copy_sync_dir(struct mailbox_list_index_sync_ctx *ctx,
			   uint32_t offset,
			   struct mailbox_list_sync_dir **sync_dir_r)
{
	const struct mailbox_list_dir_record *dir;
	const struct mailbox_list_record *recs;
	struct mailbox_list_sync_dir *sync_dir;
	struct mailbox_list_sync_record *sync_rec;
	const char *name;
	size_t max_len;
	unsigned int i;

	if (mailbox_list_index_get_dir(ctx->index, &offset, &dir) < 0)
		return -1;

	sync_dir = mailbox_list_alloc_sync_dir(ctx, dir->count +
					       DIR_ALLOC_MORE_COUNT);
	sync_dir->offset = offset;

	recs = MAILBOX_LIST_RECORDS(dir);
	for (i = 0; i < dir->count; i++) {
		sync_rec = array_append_space(&sync_dir->records);
		sync_rec->name_hash = recs[i].name_hash;
		sync_rec->uid = recs[i].uid;
		sync_rec->dir_offset =
			mail_index_offset_to_uint32(recs[i].dir_offset);

		max_len = ctx->index->mmap_size - recs[i].name_offset;
		name = CONST_PTR_OFFSET(ctx->index->mmap_base,
					recs[i].name_offset);

		sync_rec->name = p_strndup(ctx->pool, name, max_len);
	}

	*sync_dir_r = sync_dir;
	return 0;
}

static int mailbox_list_sync_record_cmp(const void *_key, const void *_rec)
{
	const struct mailbox_list_sync_lookup_key *key = _key;
	const struct mailbox_list_sync_record *rec = _rec;
	int ret;

	if (key->name_hash < rec->name_hash)
		return -1;
	if (key->name_hash > rec->name_hash)
		return 1;

	ret = strcmp(key->name, rec->name);
	if (ret == 0)
		*key->match = TRUE;
	return ret;
}

static struct mailbox_list_sync_record *
mailbox_list_sync_dir_lookup(struct mailbox_list_sync_dir *dir,
			     const char *name, unsigned int *idx_r)
{
	struct mailbox_list_sync_lookup_key key;
	const struct mailbox_list_sync_record *recs;
	struct mailbox_list_sync_record *rec;
	unsigned int count;
	bool match;

	/* binary search the current hierarchy level name. the values are
	   sorted primarily by their hash value and secondarily by the actual
	   name */
	match = FALSE;
	key.name = name;
	key.name_hash = crc32_str(name);
	key.match = &match;

	recs = array_get(&dir->records, &count);
	rec = bsearch_insert_pos(&key, recs, count, sizeof(*rec),
				 mailbox_list_sync_record_cmp);
	*idx_r = rec - recs;
	return match ? rec : NULL;
}

static struct mailbox_list_sync_record *
mailbox_list_alloc_add_record(struct mailbox_list_index_sync_ctx *ctx,
			      struct mailbox_list_sync_dir *dir,
			      const char *name, unsigned int idx)
{
	struct mailbox_list_sync_record *rec;

	rec = array_insert_space(&dir->records, idx);
	rec->name_hash = crc32_str(name);
	rec->name = p_strdup(ctx->pool, name);
	rec->uid = ctx->hdr.next_uid++;
	rec->created = TRUE;
	mail_index_append(ctx->trans, rec->uid, &rec->seq);

	dir->new_records_count++;
	return rec;
}

static int
mailbox_list_index_sync_get_seq(struct mailbox_list_index_sync_ctx *ctx,
				struct mailbox_list_sync_record *rec)
{
	if (rec->uid == 0) {
		return mailbox_list_index_set_corrupted(ctx->index,
							"Record with UID=0");
	}
	if (mail_index_lookup_uid_range(ctx->view, rec->uid, rec->uid,
					&rec->seq, &rec->seq) < 0)
		return -1;

	if (rec->seq == 0) {
		return mailbox_list_index_set_corrupted(ctx->index,
			"Desync: Record expunged from mail index");
	}
	return 0;
}

static int
mailbox_list_index_sync_int(struct mailbox_list_index_sync_ctx *ctx,
			    const char *name,
			    struct mailbox_list_sync_dir **dir_r,
			    uint32_t *seq_r)
{
	const char *p, *hier_name;
	struct mailbox_list_sync_dir *dir;
	struct mailbox_list_sync_record *rec = NULL;
	unsigned int idx;

	if (ctx->failed)
		return -1;

	dir = ctx->sync_root;

	t_push();
	for (;;) {
		p = strchr(name, ctx->index->separator);
		hier_name = p == NULL ? name : t_strdup_until(name, p);

		if (*hier_name == '\0') {
			if (p == NULL) {
				/* name ended with a separator */
				break;
			}
			/* two separators adjacently, skip this */
			name = p + 1;
			continue;
		}

		if (rec != NULL) {
			mail_index_update_flags(ctx->trans, rec->seq,
				MODIFY_REPLACE,
				MAILBOX_LIST_INDEX_FLAG_NONEXISTENT |
				MAILBOX_LIST_INDEX_FLAG_CHILDREN);
		}

		rec = mailbox_list_sync_dir_lookup(dir, hier_name, &idx);
		if (rec == NULL) {
			/* new record */
			rec = mailbox_list_alloc_add_record(ctx, dir,
							    hier_name, idx);
		} else if (rec->seq == 0) {
			/* this record was copied from existing index.
			   the uid is known, but the sequence isn't. */
			if (mailbox_list_index_sync_get_seq(ctx, rec) < 0) {
				ctx->failed = TRUE;
				break;
			}
		}
		*seq_r = rec->seq;

		/* remember that we've seen this record */
		if (!rec->seen) {
			rec->seen = TRUE;
			dir->seen_records_count++;
		}

		if (p == NULL) {
			/* leaf */
			break;
		}

		if (rec->dir == NULL) {
			if (rec->dir_offset != 0) {
				if (mailbox_list_copy_sync_dir(ctx,
							       rec->dir_offset,
							       &rec->dir) < 0) {
					ctx->failed = TRUE;
					break;
				}
			} else {
				rec->dir = mailbox_list_alloc_sync_dir(ctx,
						1 + DIR_ALLOC_MORE_COUNT);
			}
		}

		name = p + 1;
		dir = rec->dir;
	}
	t_pop();

	i_assert(dir != NULL);
	*dir_r = dir;
	return ctx->failed ? -1 : 0;
}

static int mailbox_list_index_get_root(struct mailbox_list_index_sync_ctx *ctx)
{
	uint32_t seq;

	i_assert(ctx->index->mmap_size > 0);

	if (ctx->index->mmap_size == sizeof(*ctx->index->hdr)) {
		/* root doesn't exist in the file yet */
		ctx->root = mailbox_list_alloc_sync_dir(ctx,
							ROOT_INIT_COUNT);
	} else {
		if (mailbox_list_copy_sync_dir(ctx, sizeof(*ctx->index->hdr),
					       &ctx->root) < 0)
			return -1;
	}

	/* keep sync_root=root until we've built the sync_root path. */
	ctx->sync_root = ctx->root;

	if (*ctx->sync_path != '\0') {
		if (mailbox_list_index_sync_more(ctx, ctx->sync_path, &seq) < 0)
			return -1;
	}

	return mailbox_list_index_sync_int(ctx, ctx->sync_path,
					   &ctx->sync_root, &seq);
}

static int sync_init_mail_sync(struct mailbox_list_index_sync_ctx *ctx)
{
	struct mail_index_sync_rec sync_rec;
	const struct mail_index_header *hdr;

	if (mail_index_sync_begin(ctx->index->mail_index, &ctx->mail_sync_ctx,
				  &ctx->view, (uint32_t)-1, 0,
				  FALSE, FALSE) < 0)
		return -1;

	/* we should have only external transactions in here, for which we
	   don't need to do anything but write them to the index */
	while (mail_index_sync_next(ctx->mail_sync_ctx, &sync_rec) > 0)
		;

	hdr = mail_index_get_header(ctx->view);
	if (hdr->uid_validity != 0) {
		if (hdr->uid_validity != ctx->hdr.uid_validity) {
			return mailbox_list_index_set_corrupted(ctx->index,
				"Desync: uid_validity changed");
		}
	}

	ctx->trans = mail_index_transaction_begin(ctx->view, FALSE, TRUE);
	if (hdr->uid_validity == 0) {
		mail_index_update_header(ctx->trans,
			offsetof(struct mail_index_header, uid_validity),
			&ctx->hdr.uid_validity, sizeof(ctx->hdr.uid_validity),
			TRUE);
	}

	return mailbox_list_index_get_root(ctx);
}

int mailbox_list_index_sync_init(struct mailbox_list_index *index,
				 const char *path,
				 enum mailbox_list_sync_flags flags,
				 struct mailbox_list_index_sync_ctx **ctx_r)
{
	struct mailbox_list_index_sync_ctx *ctx;
	pool_t pool;
	size_t len;

	/* add separator to end of path if it isn't there */
	len = strlen(path);
	if (len > 0 && path[len-1] != index->separator)
		path = t_strdup_printf("%s%c", path, index->separator);

	pool = pool_alloconly_create("mailbox list index sync", 1024*32);

	ctx = p_new(pool, struct mailbox_list_index_sync_ctx, 1);
	ctx->pool = pool;
	ctx->index = index;
	ctx->sync_path = p_strdup(pool, path);
	ctx->flags = flags;
	ctx->hdr = *index->hdr;

	/* mail index syncing acts as the only locking for us */
	if (sync_init_mail_sync(ctx) < 0) {
		mailbox_list_index_sync_commit(&ctx);
		return -1;
	}

	*ctx_r = ctx;
	return 0;
}

struct mail_index_view *
mailbox_list_index_sync_get_view(struct mailbox_list_index_sync_ctx *ctx)
{
	return ctx->view;
}

struct mail_index_transaction *
mailbox_list_index_sync_get_transaction(struct mailbox_list_index_sync_ctx *ctx)
{
	return ctx->trans;
}

int mailbox_list_index_sync_more(struct mailbox_list_index_sync_ctx *ctx,
				 const char *name, uint32_t *seq_r)
{
	struct mailbox_list_sync_dir *dir;

	return mailbox_list_index_sync_int(ctx, name, &dir, seq_r);
}

static int
mailbox_list_index_sync_grow(struct mailbox_list_index_sync_ctx *ctx,
			     uint32_t size)
{
	struct mailbox_list_index *index = ctx->index;
	uoff_t new_fsize, grow_size;

	new_fsize = ctx->hdr.used_space + size;
	grow_size = new_fsize / 100 * MAILBOX_LIST_INDEX_GROW_PERCENTAGE;
	if (grow_size < MAILBOX_LIST_INDEX_MIN_SIZE)
		grow_size = MAILBOX_LIST_INDEX_MIN_SIZE;
	new_fsize += grow_size;
	new_fsize &= ~(512-1);

	i_assert(new_fsize >= ctx->hdr.used_space + size);

	if (file_set_size(index->fd, (off_t)new_fsize) < 0) {
		mailbox_list_index_set_syscall_error(index, "file_set_size()");
		return -1;
	}

	return mailbox_list_index_map(index);
}

static int
mailbox_list_index_sync_alloc_space(struct mailbox_list_index_sync_ctx *ctx,
				    uint32_t size, void **base_r,
				    uint32_t *base_offset_r)
{
	size_t pos = ctx->hdr.used_space;

	/* all allocations must be 32bit aligned */
	pos = (pos + 3) & ~3;

	if (pos + size > ctx->index->mmap_size) {
		if (mailbox_list_index_sync_grow(ctx, size + 3) < 0)
			return -1;

		i_assert(pos + size < ctx->index->mmap_size);
	}

	*base_offset_r = pos;
	*base_r = PTR_OFFSET(ctx->index->mmap_base, *base_offset_r);
	ctx->hdr.used_space = pos + size;
	return 0;
}

static int
mailbox_list_index_sync_recreate_dir(struct mailbox_list_index_sync_ctx *ctx,
				     struct mailbox_list_sync_dir *sync_dir,
				     uint32_t offset_pos, bool partial)
{
	struct mailbox_list_dir_record *dir, *new_dir;
	struct mailbox_list_record *recs, *new_recs;
	struct mailbox_list_sync_record *sync_recs;
	unsigned int src, dest, orig, count, nondeleted_count;
	unsigned int name_space_needed, deleted_space;
	uint32_t base_offset, name_pos, size;
	void *base;

	i_assert((offset_pos % sizeof(uint32_t)) == 0);
	i_assert(offset_pos < ctx->index->mmap_size);

	/* count how much space we need and how much we wasted for deleted
	   records */
	nondeleted_count = 0; name_space_needed = 0; deleted_space = 0;
	sync_recs = array_get_modifiable(&sync_dir->records, &count);
	for (src = 0; src < count; src++) {
		if (sync_recs[src].seen || partial) {
			nondeleted_count++;
			if (sync_recs[src].created) {
				/* new record */
				name_space_needed +=
					strlen(sync_recs[src].name) + 1;
			}
		} else {
			deleted_space += sizeof(*new_recs) +
				strlen(sync_recs[src].name) + 1;
		}
	}

	/* @UNSAFE */
	name_space_needed += sizeof(*dir) +
		nondeleted_count * sizeof(*new_recs);
	if (mailbox_list_index_sync_alloc_space(ctx, name_space_needed,
						&base, &base_offset) < 0)
		return -1;
	/* NOTE: any pointers to the index file may have been invalidated
	   as a result of growing the the memory area */

	if (sync_dir->offset == 0) {
		dir = NULL;
		recs = NULL;
	} else {
		/* the offset should have been verified already to be valid */
		i_assert(sync_dir->offset == offset_pos);
		i_assert(sync_dir->offset < ctx->index->mmap_size);
		dir = PTR_OFFSET(ctx->index->mmap_base, sync_dir->offset);
		recs = MAILBOX_LIST_RECORDS(dir);
	}

	new_dir = base;
	new_dir->count = nondeleted_count;

	new_recs = MAILBOX_LIST_RECORDS(new_dir);
	name_pos = (const char *)(new_recs + nondeleted_count) -
		(const char *)base;
	for (src = dest = 0; src < count; src++) {
		if (!sync_recs[src].seen && !partial) {
			/* expunge from mail index */
			uint32_t seq;

			if (mail_index_lookup_uid_range(ctx->view,
							sync_recs[src].uid,
							sync_recs[src].uid,
							&seq, &seq) < 0)
				return -1;

			if (seq != 0)
				mail_index_expunge(ctx->trans, seq);
			// FIXME: expunge also NONEXISTENT parents
			continue;
		}

		new_recs[dest].name_hash = sync_recs[src].name_hash;
		new_recs[dest].dir_offset =
			mail_index_uint32_to_offset(sync_recs[src].dir_offset);
		if (sync_recs[src].created) {
			/* new record */
			new_recs[dest].uid = sync_recs[src].uid;
			new_recs[dest].name_offset = base_offset + name_pos;
			size = strlen(sync_recs[src].name) + 1;
			memcpy(PTR_OFFSET(base, name_pos), sync_recs[src].name,
			       size);
			name_pos += size;
		} else {
			/* existing record. need to find its name_offset */
			for (orig = 0; orig < dir->count; orig++) {
				if (recs[orig].uid == sync_recs[src].uid)
					break;
			}
			i_assert(orig < dir->count);

			new_recs[dest].uid = sync_recs[src].uid;
			new_recs[dest].name_offset = recs[orig].name_offset;
		}
		dest++;
	}
	i_assert(dest == nondeleted_count);
	i_assert(name_pos == name_space_needed);

	if (offset_pos == 0) {
		/* we're writing the root directory */
		i_assert(base_offset == sizeof(*ctx->index->hdr));
	} else {
		/* add a link to this newly created directory. */
		uint32_t *pos;

		pos = PTR_OFFSET(ctx->index->mmap_base, offset_pos);
		i_assert(mail_index_offset_to_uint32(*pos) == 0);
		*pos = mail_index_uint32_to_offset(base_offset);
	}

	sync_dir->offset = base_offset;
	return 0;
}

static int
mailbox_list_index_sync_update_dir(struct mailbox_list_index_sync_ctx *ctx,
				   struct mailbox_list_sync_dir *sync_dir)
{
	const struct mailbox_list_dir_record *dir;
	struct mailbox_list_record *recs;
	const struct mailbox_list_sync_record *sync_recs;
	unsigned int i, count;

	i_assert(sync_dir->offset != 0);

	if (mailbox_list_index_get_dir(ctx->index, &sync_dir->offset, &dir) < 0)
		return -1;

	sync_recs = array_get(&sync_dir->records, &count);
	i_assert(dir->count == count);
	i_assert(sync_dir->seen_records_count < count);

	recs = MAILBOX_LIST_RECORDS(dir);
	for (i = 0; i < dir->count; i++) {
		if (!sync_recs[i].seen)
			recs[i].deleted = TRUE;
	}
	return 0;
}

static int
mailbox_list_index_sync_write_dir(struct mailbox_list_index_sync_ctx *ctx,
				  struct mailbox_list_sync_dir *sync_dir,
				  uint32_t offset_pos, bool partial)
{
	const struct mailbox_list_dir_record *dir;
	const struct mailbox_list_record *recs;
	const struct mailbox_list_sync_record *sync_recs;
	uint32_t child_offset_pos;
	unsigned int i, j, count;

	if (!ctx->seen_sync_root && ctx->sync_root == sync_dir) {
		i_assert(partial);
		ctx->seen_sync_root = TRUE;
		partial = (ctx->flags & MAILBOX_LIST_SYNC_FLAG_PARTIAL) != 0;
	}

	if (sync_dir->offset != 0) {
		/* point to latest dir entry's next_offset */
		offset_pos = sync_dir->offset +
			offsetof(struct mailbox_list_dir_record, next_offset);
	}

	if (sync_dir->new_records_count > 0) {
		/* need to recreate the dir record */
		if (mailbox_list_index_sync_recreate_dir(ctx, sync_dir,
							 offset_pos,
							 partial) < 0)
			return -1;
		/* NOTE: index may have been remaped here */
	} else if (sync_dir->seen_records_count !=
		   array_count(&sync_dir->records) && !partial) {
		/* just mark the records deleted */
		if (mailbox_list_index_sync_update_dir(ctx, sync_dir) < 0)
			return -1;
	}

	if (!partial && (ctx->flags & MAILBOX_LIST_SYNC_FLAG_RECURSIVE) == 0) {
		/* we're doing a full sync only for the root */
		partial = TRUE;
	}

	/* update child mailboxes */
	sync_recs = array_get(&sync_dir->records, &count);
	if (count == 0)
		return 0;

	i_assert(sync_dir->offset != 0 &&
		 sync_dir->offset < ctx->index->mmap_size);
	for (i = j = 0; i < count; i++) {
		if (sync_recs[i].dir == NULL)
			continue;

		/* these may change after each sync_write_dir() call */
		dir = CONST_PTR_OFFSET(ctx->index->mmap_base, sync_dir->offset);
		recs = MAILBOX_LIST_RECORDS(dir);

		/* child_offset_pos needs to point to record's dir_offset */
		for (; j < dir->count; j++) {
			if (recs[j].uid == sync_recs[i].uid)
				break;
		}
		i_assert(j < dir->count);

		child_offset_pos = (const char *)&recs[j].dir_offset -
			(const char *)ctx->index->mmap_base;
		if (mailbox_list_index_sync_write_dir(ctx, sync_recs[i].dir,
						      child_offset_pos,
						      partial) < 0)
			return -1;
	}
	return 0;
}

static int
mailbox_list_index_sync_write(struct mailbox_list_index_sync_ctx *ctx)
{
	struct mailbox_list_index_header *hdr;
	bool partial;

	if (ctx->sync_root == ctx->root) {
		ctx->seen_sync_root = TRUE;
		partial = (ctx->flags & MAILBOX_LIST_SYNC_FLAG_PARTIAL) != 0;
	} else {
		/* until we've seen the sync root, we're doing only partial
		   syncing */
		partial = TRUE;
	}

	if (mailbox_list_index_sync_write_dir(ctx, ctx->root, 0, partial) < 0)
		return -1;

	/* update header */
	hdr = ctx->index->mmap_base;
	hdr->next_uid = ctx->hdr.next_uid;
	hdr->used_space = ctx->hdr.used_space;
	hdr->deleted_space = ctx->hdr.deleted_space;

	if (msync(ctx->index->mmap_base, hdr->used_space, MS_SYNC) < 0) {
		mailbox_list_index_set_syscall_error(ctx->index, "msync()");
		return -1;
	}
	return 0;
}

int mailbox_list_index_sync_commit(struct mailbox_list_index_sync_ctx **_ctx)
{
	struct mailbox_list_index_sync_ctx *ctx = *_ctx;
	int ret = ctx->failed ? -1 : 0;

	*_ctx = NULL;

	if (!ctx->failed) {
		/* write all the changes to the index */
		ret = mailbox_list_index_sync_write(ctx);
	}

	if (ctx->mail_sync_ctx != NULL) {
		if (ret < 0)
			mail_index_transaction_rollback(&ctx->trans);
		else {
			uint32_t seq;
			uoff_t offset;

			if (mail_index_transaction_commit(&ctx->trans,
							  &seq, &offset) < 0)
				ret = -1;
		}

		if (ret < 0)
			mail_index_sync_rollback(&ctx->mail_sync_ctx);
		else {
			if (mail_index_sync_commit(&ctx->mail_sync_ctx) < 0)
				ret = -1;
		}
	}

	pool_unref(ctx->pool);
	return ret;
}

void mailbox_list_index_sync_rollback(struct mailbox_list_index_sync_ctx **ctx)
{
	(*ctx)->failed = TRUE;
	(void)mailbox_list_index_sync_commit(ctx);
}

--- NEW FILE: mailbox-list-index.c ---
/* Copyright (C) 2006 Timo Sirainen */

#include "lib.h"
#include "array.h"
#include "crc32.h"
#include "ioloop.h"
#include "str.h"
#include "file-dotlock.h"
#include "mmap-util.h"
#include "write-full.h"
#include "mail-index-private.h"
#include "mailbox-list-index-private.h"

#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/stat.h>

struct mailbox_list_iter_path {
	const struct mailbox_list_dir_record *dir;
	unsigned int pos;
	unsigned int name_path_len;
};

struct mailbox_list_iter_ctx {
	struct mailbox_list_index *index;

	unsigned int recurse_level;

	struct mailbox_list_iter_path cur;
	ARRAY_DEFINE(path, struct mailbox_list_iter_path);
	string_t *name_path;

	unsigned int failed:1;
};

const struct dotlock_settings dotlock_set = {
	MEMBER(temp_prefix) NULL,
	MEMBER(lock_suffix) NULL,

	MEMBER(timeout) 60,
	MEMBER(stale_timeout) 30,

	MEMBER(callback) NULL,
	MEMBER(context) NULL,

	MEMBER(use_excl_lock) FALSE
};

int mailbox_list_index_set_syscall_error(struct mailbox_list_index *index,
					 const char *function)
{
	i_error("%s failed with file %s: %m", index->filepath, function);
	return -1;
}

static void mailbox_list_index_unmap(struct mailbox_list_index *index)
{
	if (index->mmap_base != NULL) {
		if (munmap(index->mmap_base, index->mmap_size) < 0)
			mailbox_list_index_set_syscall_error(index, "munmap()");
		index->mmap_base = NULL;
		index->mmap_size = 0;
	}

	index->hdr = NULL;
}

static void mailbox_list_index_file_close(struct mailbox_list_index *index)
{
	mailbox_list_index_unmap(index);

	if (index->fd != -1) {
		if (close(index->fd) < 0)
			mailbox_list_index_set_syscall_error(index, "close()");
	}
}

int mailbox_list_index_set_corrupted(struct mailbox_list_index *index,
				     const char *str)
{
	(void)unlink(index->filepath);
	// FIXME: reopen or something

	i_error("Corrupted mailbox list index file %s: %s",
		index->filepath, str);
	return -1;
}

static int
mailbox_list_index_check_header(struct mailbox_list_index *index,
				const struct mailbox_list_index_header *hdr)
{
	if (hdr->major_version != MAILBOX_LIST_INDEX_MAJOR_VERSION)
		return -1;

	if (hdr->header_size < sizeof(*hdr)) {
		return mailbox_list_index_set_corrupted(index,
			"header_size is too small");
	}
	if (hdr->header_size > index->mmap_size) {
		return mailbox_list_index_set_corrupted(index,
			"header_size is too large");
	}

	if (hdr->uid_validity == 0) {
		return mailbox_list_index_set_corrupted(index,
							"uid_validity is 0");
	}
	if (hdr->next_uid == 0)
		return mailbox_list_index_set_corrupted(index, "next_uid is 0");

	if (hdr->uid_validity != index->mail_index->hdr->uid_validity &&
	    index->mail_index->hdr->uid_validity != 0) {
		mail_index_set_error(index->mail_index,
			"uid_validity changed in file %s", index->filepath);
		mail_index_mark_corrupted(index->mail_index);
	}

	return 0;
}

int mailbox_list_index_map(struct mailbox_list_index *index)
{
	const struct mailbox_list_index_header *hdr;

	mailbox_list_index_unmap(index);

	// FIXME: handle non-mmaps
	index->mmap_base = mmap_rw_file(index->fd, &index->mmap_size);
	if (index->mmap_base == MAP_FAILED) {
		index->mmap_base = NULL;
		return mailbox_list_index_set_syscall_error(index, "mmap()");
	}

	if (index->mmap_size < sizeof(*hdr)) {
		mailbox_list_index_set_corrupted(index, "File too small");
		return 0;
	}

	hdr = index->mmap_base;
	if (mailbox_list_index_check_header(index, hdr) < 0)
		return 0;

	index->hdr = hdr;
	return 1;
}

static void
mailbox_list_index_init_header(struct mailbox_list_index_header *hdr)
{
	memset(hdr, 0, sizeof(*hdr));
	hdr->major_version = MAILBOX_LIST_INDEX_MAJOR_VERSION;
	hdr->minor_version = MAILBOX_LIST_INDEX_MINOR_VERSION;

	hdr->header_size = sizeof(*hdr);
	hdr->used_space = hdr->header_size;

	hdr->uid_validity = ioloop_time;
	hdr->next_uid = 1;
}

static int mailbox_list_index_is_recreated(struct mailbox_list_index *index)
{
	struct stat st1, st2;

	if (stat(index->filepath, &st1) < 0) {
		mailbox_list_index_set_syscall_error(index, "stat()");
		return -1;
	}
	if (fstat(index->fd, &st2) < 0) {
		mailbox_list_index_set_syscall_error(index, "fstat()");
		return -1;
	}

	return st1.st_ino != st2.st_ino ||
		!CMP_DEV_T(st1.st_dev, st2.st_dev);
}

static int
mailbox_list_index_file_create(struct mailbox_list_index *index)
{
	struct mailbox_list_index_header hdr;
	struct dotlock *dotlock;
	int fd, ret;

	fd = file_dotlock_open(&dotlock_set, index->filepath, 0, &dotlock);
	if (fd == -1) {
		mailbox_list_index_set_syscall_error(index,
						     "file_dotlock_open()");
		return -1;
	}

	if (index->fd != -1) {
		/* if the file has been recreated by someone else,
		   retry opening it */
		ret = mailbox_list_index_is_recreated(index);
		if (ret != 0) {
			(void)file_dotlock_delete(&dotlock);
			return ret < 0 ? -1 : 0;
		}
	}

	mailbox_list_index_init_header(&hdr);
	if (write_full(fd, &hdr, sizeof(hdr)) < 0) {
		mailbox_list_index_set_syscall_error(index, "write_full()");
		(void)file_dotlock_delete(&dotlock);
		return -1;
	}

	if (file_dotlock_replace(&dotlock,
				 DOTLOCK_REPLACE_FLAG_DONT_CLOSE_FD) < 0) {
		mailbox_list_index_set_syscall_error(index,
						     "file_dotlock_replace()");
		(void)close(fd);
		return -1;
	}

	if (index->fd != -1)
		mailbox_list_index_file_close(index);
	index->fd = fd;

	ret = mailbox_list_index_map(index);
	if (ret == 0) {
		i_error("Self-created mailbox list index file %s was corrupted",
			index->filepath);
		return -1;
	}
	return ret;
}

static int
mailbox_list_index_file_try_open_or_create(struct mailbox_list_index *index)
{
	int ret;

	i_assert(index->fd == -1);

	index->fd = open(index->filepath, O_RDWR);
	if (index->fd == -1) {
		if (errno != ENOENT) {
			mailbox_list_index_set_syscall_error(index, "open()");
			return -1;
		}
	} else {
		ret = mailbox_list_index_map(index);
		if (ret != 0) {
			if (ret < 0)
				mailbox_list_index_file_close(index);
			return ret;
		}
	}

	ret = mailbox_list_index_file_create(index);
	if (ret <= 0)
		mailbox_list_index_file_close(index);
	return ret;
}

int mailbox_list_index_open_or_create(struct mailbox_list_index *index)
{
	int ret;

	while ((ret = mailbox_list_index_file_try_open_or_create(index)) == 0) {
		/* file was recreated by someone else, try reopening */
	}
	return ret < 0 ? -1 : 0;
}

struct mailbox_list_index *
mailbox_list_index_alloc(const char *path, char separator,
			 struct mail_index *mail_index)
{
	struct mailbox_list_index *index;

	index = i_new(struct mailbox_list_index, 1);
	index->filepath = i_strdup(path);
	index->separator = separator;
	index->mail_index = mail_index;
	index->fd = -1;
	return index;
}

void mailbox_list_index_free(struct mailbox_list_index **_index)
{
	struct mailbox_list_index *index = *_index;

	*_index = NULL;

	i_free(index->filepath);
	i_free(index);
}

struct mailbox_list_index_lookup_key {
	uint32_t name_hash;

	struct mailbox_list_index *index;
	const char *name;

	bool *failed;
};

static int
mailbox_list_get_name(struct mailbox_list_index *index, pool_t pool,
		      const struct mailbox_list_record *rec,
		      const char **name_r)
{
	size_t max_len;
	const char *name;

	if (rec->name_offset >= index->mmap_size) {
		mailbox_list_index_set_corrupted(index,
			"record name_offset points outside file");
		return -1;
	}
	max_len = index->mmap_size - rec->name_offset;
	name = CONST_PTR_OFFSET(index->mmap_base, rec->name_offset);
	/* get name length. don't bother checking if it's not NUL-terminated,
	   because practically it always is even if the file is corrupted.
	   just make sure we don't crash if it happens. */
	*name_r = p_strndup(pool, name, max_len);
	return 0;
}

static int mailbox_list_record_cmp(const void *_key, const void *_rec)
{
	const struct mailbox_list_index_lookup_key *key = _key;
	const struct mailbox_list_record *rec = _rec;
	const char *name;
	int ret;

	if (key->name_hash < rec->name_hash)
		return -1;
	if (key->name_hash > rec->name_hash)
		return 1;

	t_push();
	if (mailbox_list_get_name(key->index, unsafe_data_stack_pool,
				  rec, &name) < 0) {
		*key->failed = TRUE;
		ret = -1;
	} else {
		ret = strcmp(key->name, name);
	}
	t_pop();
	return ret;
}

int mailbox_list_index_get_dir(struct mailbox_list_index *index,
			       uint32_t *offset,
			       const struct mailbox_list_dir_record **dir_r)
{
	const struct mailbox_list_dir_record *dir;
	uint32_t next_offset, cur_offset = *offset;

	i_assert(index->mmap_size > 0);

	do {
		if (cur_offset >= index->mmap_size - sizeof(*dir)) {
			return mailbox_list_index_set_corrupted(index,
				"dir_offset points outside file");
		}
		if ((cur_offset % 4) != 0) {
			return mailbox_list_index_set_corrupted(index,
				"dir_offset not 32bit aligned");
		}

		dir = CONST_PTR_OFFSET(index->mmap_base, cur_offset);
		next_offset = mail_index_offset_to_uint32(dir->next_offset);
		if (next_offset != 0 && next_offset <= cur_offset) {
			return mailbox_list_index_set_corrupted(index,
				"next_offset points backwards");
		}
		cur_offset = next_offset;
	} while (cur_offset != 0);

	cur_offset = (const char *)dir - (const char *)index->mmap_base;
	if (dir->count > INT_MAX/sizeof(struct mailbox_list_record) ||
	    dir->count * sizeof(struct mailbox_list_record) >
	    index->mmap_size - cur_offset) {
		mailbox_list_index_set_corrupted(index, "dir count too large");
		return -1;
	}

	*offset = cur_offset;
	*dir_r = dir;
	return 0;
}

int mailbox_list_index_dir_lookup_rec(struct mailbox_list_index *index,
				      const struct mailbox_list_dir_record *dir,
				      const char *name,
				      const struct mailbox_list_record **rec_r)
{
	const struct mailbox_list_record *rec;
	struct mailbox_list_index_lookup_key key;
	bool failed = FALSE;

	/* binary search the current hierarchy level name. the values are
	   sorted primarily by their hash value and secondarily by the actual
	   name */
	memset(&key, 0, sizeof(key));
	key.index = index;
	key.name = name;
	key.name_hash = crc32_str(name);
	key.failed = &failed;

	rec = bsearch(&key, MAILBOX_LIST_RECORDS(dir), dir->count, sizeof(*rec),
		      mailbox_list_record_cmp);
	if (failed)
		return -1;
	if (rec == NULL)
		return 0;

	*rec_r = rec;
	return 1;
}

static int
mailbox_list_index_lookup_rec(struct mailbox_list_index *index,
			      uint32_t dir_offset, const char *name,
			      const struct mailbox_list_record **rec_r)
{
	const struct mailbox_list_dir_record *dir;
	const char *p, *hier_name;
	int ret;

	if (dir_offset == index->mmap_size &&
	    dir_offset == sizeof(*index->hdr)) {
		/* root doesn't exist in the file yet */
		return 0;
	}

	if (mailbox_list_index_get_dir(index, &dir_offset, &dir) < 0)
		return -1;

	p = strchr(name, index->separator);
	hier_name = p == NULL ? name : t_strdup_until(name, p);

	ret = mailbox_list_index_dir_lookup_rec(index, dir, hier_name, rec_r);
	if (ret <= 0)
		return ret;

	if (p == NULL) {
		/* found it */
		return 1;
	}

	/* recurse to children */
	dir_offset = mail_index_offset_to_uint32((*rec_r)->dir_offset);
	if (dir_offset == 0)
		return 0;

	return mailbox_list_index_lookup_rec(index, dir_offset, p + 1, rec_r);
}

static int mailbox_list_index_refresh(struct mailbox_list_index *index)
{
	int ret;

	if ((ret = mailbox_list_index_is_recreated(index)) <= 0)
		return ret;

	mailbox_list_index_file_close(index);
	return mailbox_list_index_open_or_create(index);
}

int mailbox_list_index_lookup(struct mailbox_list_index *index,
			      const char *name, uint32_t *uid_r)
{
	const struct mailbox_list_record *rec;
	uint32_t offset = sizeof(*index->hdr);
	int ret;

	ret = mailbox_list_index_lookup_rec(index, offset, name, &rec);
	if (ret == 0) {
		/* not found, see if it's found after a refresh */
		if ((ret = mailbox_list_index_refresh(index)) <= 0)
			return ret;

		ret = mailbox_list_index_lookup_rec(index, offset, name, &rec);
	}

	*uid_r = ret <= 0 ? 0 : rec->uid;
	return ret;
}

struct mailbox_list_iter_ctx *
mailbox_list_index_iterate_init(struct mailbox_list_index *index,
				const char *path, int recurse_level)
{
	struct mailbox_list_iter_ctx *ctx;
	const struct mailbox_list_record *rec;
	uint32_t offset = sizeof(*index->hdr);
	int ret;

	ctx = i_new(struct mailbox_list_iter_ctx, 1);
	ctx->index = index;
	ctx->recurse_level = recurse_level < 0 ? (unsigned int)-1 :
		(unsigned int)recurse_level;
	ctx->name_path = str_new(default_pool, 512);

	if (*path != '\0') {
		ret = mailbox_list_index_lookup_rec(index, offset, path, &rec);
		if (ret < 0)
			ctx->failed = TRUE;
		else {
			offset = ret == 0 ? 0 :
				mail_index_offset_to_uint32(rec->dir_offset);
		}
	}
	if (!ctx->failed && offset != 0) {
		if (mailbox_list_index_get_dir(index, &offset,
					       &ctx->cur.dir) < 0)
			ctx->failed = TRUE;
	}
	i_array_init(&ctx->path, I_MIN(ctx->recurse_level, 16));
	return ctx;
}

int mailbox_list_index_iterate_next(struct mailbox_list_iter_ctx *ctx,
				    struct mailbox_list_index_info *info_r)
{
	const struct mailbox_list_iter_path *cur;
	const struct mailbox_list_record *recs;
	const char *name;
	uint32_t dir_offset;
	unsigned int count;

	if (ctx->failed)
		return -1;

	if (ctx->cur.dir == NULL) {
		/* no mailboxes */
		i_assert(array_count(&ctx->path) == 0);
		return 0;
	}

	while (ctx->cur.pos == ctx->cur.dir->count) {
		count = array_count(&ctx->path);
		if (count == 0) {
			/* we're done */
			return 0;
		}

		/* go back to parent path */
		cur = array_idx(&ctx->path, count-1);
		ctx->cur = *cur;
		array_delete(&ctx->path, count-1, 1);

		ctx->cur.pos++;
	}

	recs = MAILBOX_LIST_RECORDS(ctx->cur.dir);
	recs += ctx->cur.pos;

	if (recs->deleted) {
		ctx->cur.pos++;
		return mailbox_list_index_iterate_next(ctx, info_r);
	}

	t_push();
	if (mailbox_list_get_name(ctx->index, unsafe_data_stack_pool,
				  recs, &name) < 0) {
		ctx->failed = TRUE;
		t_pop();
		return -1;
	}
	str_truncate(ctx->name_path, ctx->cur.name_path_len);
	if (ctx->cur.name_path_len > 0)
		str_append_c(ctx->name_path, ctx->index->separator);
	str_append(ctx->name_path, name);
	t_pop();

	dir_offset = mail_index_offset_to_uint32(recs->dir_offset);
	if (dir_offset != 0 && array_count(&ctx->path) < ctx->recurse_level) {
		/* recurse into children */
		array_append(&ctx->path, &ctx->cur, 1);

		ctx->cur.name_path_len = str_len(ctx->name_path);
		ctx->cur.pos = 0;
		if (mailbox_list_index_get_dir(ctx->index, &dir_offset,
					       &ctx->cur.dir) < 0) {
			ctx->failed = TRUE;
			return -1;
		}
	} else {
		ctx->cur.pos++;
	}

	info_r->name = str_c(ctx->name_path);
	info_r->uid = recs->uid;
	info_r->has_children = dir_offset != 0;
	return 1;
}

void mailbox_list_index_iterate_deinit(struct mailbox_list_iter_ctx **_ctx)
{
	struct mailbox_list_iter_ctx *ctx = *_ctx;

	*_ctx = NULL;
	array_free(&ctx->path);
	str_free(&ctx->name_path);
	i_free(ctx);
}

--- NEW FILE: mailbox-list-index.h ---
#ifndef __MAILBOX_LIST_INDEX_H
#define __MAILBOX_LIST_INDEX_H

struct mailbox_list_index_sync_ctx;

/* Mailbox list index contains UID <-> mailbox name mapping. It also takes in
   a mail_index index which contains UID -> metadata information for the
   mailboxes. The mmap, in-memory and lock settings are taken from the
   mail_index. */

enum mailbox_list_index_flags {
	/* Mailbox has children. They may not be indexed however, so
	   mailbox_list_index_info.has_children=FALSE is possible. */
	MAILBOX_LIST_INDEX_FLAG_CHILDREN	= 0x01,
	/* Mailbox has no children. mailbox_list_index_info.has_children
	   should be FALSE. */
	MAILBOX_LIST_INDEX_FLAG_NOCHILDREN	= 0x02,
	/* The mailbox isn't selectable (eg. a directory) */
	MAILBOX_LIST_INDEX_FLAG_NOSELECT	= 0x04,
	/* The mailbox doesn't exist at all. This is only a placeholder for
	   a child mailbox. When the children are deleted, this mailbox will
	   be automatically deleted as well. */
	MAILBOX_LIST_INDEX_FLAG_NONEXISTENT	= 0x08
};


enum mailbox_list_sync_flags {
	/* All the child mailboxes are also being synced */
	MAILBOX_LIST_SYNC_FLAG_RECURSIVE	= 0x01,
	/* New mailboxes may be added, but none are removed */
	MAILBOX_LIST_SYNC_FLAG_PARTIAL		= 0x02
};

struct mailbox_list_index_info {
	const char *name;
	uint32_t uid;
	bool has_children;
};

struct mailbox_list_index *
mailbox_list_index_alloc(const char *path, char separator,
			 struct mail_index *mail_index);
void mailbox_list_index_free(struct mailbox_list_index **index);

/* Open or create mailbox list index. */
int mailbox_list_index_open_or_create(struct mailbox_list_index *index);

/* Synchronize the index with the backend. */
int mailbox_list_index_sync_init(struct mailbox_list_index *index,
				 const char *path,
				 enum mailbox_list_sync_flags flags,
				 struct mailbox_list_index_sync_ctx **ctx_r);
struct mail_index_view *
mailbox_list_index_sync_get_view(struct mailbox_list_index_sync_ctx *ctx);
struct mail_index_transaction *
mailbox_list_index_sync_get_transaction(struct mailbox_list_index_sync_ctx*ctx);
int mailbox_list_index_sync_more(struct mailbox_list_index_sync_ctx *ctx,
				 const char *name, uint32_t *seq_r);
int mailbox_list_index_sync_commit(struct mailbox_list_index_sync_ctx **ctx);
void mailbox_list_index_sync_rollback(struct mailbox_list_index_sync_ctx **ctx);

/* Get mailbox UID for a given name. Returns 1 if found, 0 if not,
   -1 if error */
int mailbox_list_index_lookup(struct mailbox_list_index *index,
			      const char *name, uint32_t *uid_r);

/* Iterate through all the mailboxes. If recurse_level is -1, all the child
   mailboxes are returned, otherwise it's the number of levels to return
   (0 = only the mailboxes directly under the path). Returned mailbox names
   are allocated from name_pool. */
struct mailbox_list_iter_ctx *
mailbox_list_index_iterate_init(struct mailbox_list_index *index,
				const char *path, int recurse_level);
/* Returns 1 if mailbox was returned, 0 at the end of iteration, -1 if error */
int mailbox_list_index_iterate_next(struct mailbox_list_iter_ctx *ctx,
				    struct mailbox_list_index_info *info_r);
void mailbox_list_index_iterate_deinit(struct mailbox_list_iter_ctx **ctx);

int mailbox_list_index_set_corrupted(struct mailbox_list_index *index,
				     const char *str);

#endif