--- a/configure.in	Fri Sep 28 00:03:12 2012 +0300
+++ b/configure.in	Fri Sep 28 00:11:19 2012 +0300
@@ -2463,7 +2463,7 @@
 
 LINKED_STORAGE_LIBS=
 
-mailbox_list_drivers="maildir imapdir none fs shared"
+mailbox_list_drivers="maildir imapdir fs index none shared"
 have_sdbox=no
 for storage in $mail_storages; do
   LINKED_STORAGE_LIBS="$LINKED_STORAGE_LIBS `eval echo \\$${storage}_libs`"

--- a/src/lib-storage/list/Makefile.am	Fri Sep 28 00:03:12 2012 +0300
+++ b/src/lib-storage/list/Makefile.am	Fri Sep 28 00:11:19 2012 +0300
@@ -14,6 +14,7 @@
 	mailbox-list-fs-flags.c \
 	mailbox-list-fs-iter.c \
 	mailbox-list-index.c \
+	mailbox-list-index-backend.c \
 	mailbox-list-index-iter.c \
 	mailbox-list-index-notify.c \
 	mailbox-list-index-status.c \
@@ -30,6 +31,8 @@
 	mailbox-list-delete.h \
 	mailbox-list-fs.h \
 	mailbox-list-index.h \
+	mailbox-list-index-storage.h \
+	mailbox-list-index-sync.h \
 	mailbox-list-maildir.h \
 	mailbox-list-notify-tree.h \
 	mailbox-list-subscriptions.h \

--- a/src/lib-storage/list/mailbox-list-delete.c	Fri Sep 28 00:03:12 2012 +0300
+++ b/src/lib-storage/list/mailbox-list-delete.c	Fri Sep 28 00:11:19 2012 +0300
@@ -119,17 +119,8 @@
 }
 
 int mailbox_list_delete_mailbox_file(struct mailbox_list *list,
-				     const char *name)
+				     const char *name, const char *path)
 {
-	const char *path;
-	int ret;
-
-	ret = mailbox_list_get_path(list, name, MAILBOX_LIST_PATH_TYPE_MAILBOX,
-				    &path);
-	if (ret < 0)
-		return -1;
-	i_assert(ret > 0);
-
 	/* we can simply unlink() the file */
 	if (unlink(path) == 0)
 		return 0;

--- a/src/lib-storage/list/mailbox-list-delete.h	Fri Sep 28 00:03:12 2012 +0300
+++ b/src/lib-storage/list/mailbox-list-delete.h	Fri Sep 28 00:11:19 2012 +0300
@@ -7,7 +7,7 @@
 					  const char *name,
 					  const char *trash_dir);
 int mailbox_list_delete_mailbox_file(struct mailbox_list *list,
-				     const char *name);
+				     const char *name, const char *path);
 int mailbox_list_delete_mailbox_nonrecursive(struct mailbox_list *list,
 					     const char *name, const char *path,
 					     bool rmdir_path);

--- a/src/lib-storage/list/mailbox-list-fs.c	Fri Sep 28 00:03:12 2012 +0300
+++ b/src/lib-storage/list/mailbox-list-fs.c	Fri Sep 28 00:11:19 2012 +0300
@@ -225,10 +225,17 @@
 
 static int fs_list_delete_mailbox(struct mailbox_list *list, const char *name)
 {
+	const char *path;
 	int ret;
 
 	if ((list->flags & MAILBOX_LIST_FLAG_MAILBOX_FILES) != 0) {
-		ret = mailbox_list_delete_mailbox_file(list, name);
+		ret = mailbox_list_get_path(list, name,
+					    MAILBOX_LIST_PATH_TYPE_MAILBOX,
+					    &path);
+		if (ret < 0)
+			return -1;
+		i_assert(ret > 0);
+		ret = mailbox_list_delete_mailbox_file(list, name, path);
 	} else {
 		ret = fs_list_delete_maildir(list, name);
 	}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib-storage/list/mailbox-list-index-backend.c	Fri Sep 28 00:11:19 2012 +0300
@@ -0,0 +1,586 @@
+/* Copyright (c) 2012 Dovecot authors, see the included COPYING file */
+
+#include "lib.h"
+#include "hostpid.h"
+#include "mail-index.h"
+#include "subscription-file.h"
+#include "mailbox-list-delete.h"
+#include "mailbox-list-subscriptions.h"
+#include "mailbox-list-index-storage.h"
+#include "mailbox-list-index-sync.h"
+
+#define GLOBAL_TEMP_PREFIX ".temp."
+
+struct index_mailbox_list {
+	struct mailbox_list list;
+	const char *temp_prefix;
+};
+
+extern struct mailbox_list index_mailbox_list;
+
+static struct mailbox_list *index_list_alloc(void)
+{
+	struct index_mailbox_list *list;
+	pool_t pool;
+
+	pool = pool_alloconly_create("index list", 2048);
+
+	list = p_new(pool, struct index_mailbox_list, 1);
+	list->list = index_mailbox_list;
+	list->list.pool = pool;
+
+	list->temp_prefix = p_strconcat(pool, GLOBAL_TEMP_PREFIX,
+					my_hostname, ".", my_pid, ".", NULL);
+	return &list->list;
+}
+
+static void index_list_deinit(struct mailbox_list *_list)
+{
+	struct index_mailbox_list *list = (struct index_mailbox_list *)_list;
+
+	pool_unref(&list->list.pool);
+}
+
+static char index_list_get_hierarchy_sep(struct mailbox_list *list ATTR_UNUSED)
+{
+	return MAILBOX_LIST_INDEX_HIERARHCY_SEP;
+}
+
+static int
+index_list_get_node(struct index_mailbox_list *list, const char *name,
+		    struct mailbox_list_index_node **node_r)
+{
+	struct mailbox_list_index_node *node;
+
+	if (mailbox_list_index_refresh(&list->list) < 0)
+		return -1;
+
+	node = mailbox_list_index_lookup(&list->list, name);
+	if (node == NULL)
+		return 0;
+	*node_r = node;
+	return 1;
+}
+
+static int
+index_list_get_path(struct mailbox_list *_list, const char *name,
+		    enum mailbox_list_path_type type, const char **path_r)
+{
+	struct index_mailbox_list *list = (struct index_mailbox_list *)_list;
+	struct mailbox_list_index *ilist = INDEX_LIST_CONTEXT(_list);
+	struct mail_index_view *view;
+	struct mailbox_list_index_node *node;
+	struct mailbox_status status;
+	guid_128_t mailbox_guid;
+	const char *root_dir;
+	uint32_t seq;
+	int ret;
+
+	if (name == NULL) {
+		/* return root directories */
+		return mailbox_list_set_get_root_path(&_list->set, type,
+						      path_r) ? 1 : 0;
+	}
+	/* consistently use mailbox_dir_name as part of all mailbox
+	   directories (index/control/etc) */
+	switch (type) {
+	case MAILBOX_LIST_PATH_TYPE_MAILBOX:
+		type = MAILBOX_LIST_PATH_TYPE_DIR;
+		break;
+	case MAILBOX_LIST_PATH_TYPE_ALT_MAILBOX:
+		type = MAILBOX_LIST_PATH_TYPE_ALT_DIR;
+		break;
+	default:
+		break;
+	}
+	if (!mailbox_list_set_get_root_path(&_list->set, type, &root_dir))
+		return 0;
+
+	if ((ret = index_list_get_node(list, name, &node)) <= 0) {
+		if (ret == 0) {
+			mailbox_list_set_error(_list, MAIL_ERROR_NOTFOUND,
+				T_MAIL_ERR_MAILBOX_NOT_FOUND(name));
+		}
+		return -1;
+	}
+	view = mail_index_view_open(ilist->index);
+	if (!mail_index_lookup_seq(view, node->uid, &seq))
+		i_panic("mailbox list index: lost uid=%u", node->uid);
+	if (!mailbox_list_index_status(_list, view, seq, 0,
+				       &status, mailbox_guid)) {
+		mailbox_list_set_error(_list, MAIL_ERROR_NOTFOUND,
+				       T_MAIL_ERR_MAILBOX_NOT_FOUND(name));
+		ret = -1;
+	} else if (_list->set.mailbox_dir_name == '\0') {
+		*path_r = t_strconcat(root_dir, "/",
+				      guid_128_to_string(mailbox_guid), NULL);
+		ret = 1;
+	} else {
+		*path_r = t_strdup_printf("%s/%s%s", root_dir,
+					  _list->set.mailbox_dir_name,
+					  guid_128_to_string(mailbox_guid));
+		ret = 1;
+	}
+	mail_index_view_close(&view);
+	return ret;
+}
+
+static const char *
+index_list_get_temp_prefix(struct mailbox_list *_list, bool global)
+{
+	struct index_mailbox_list *list = (struct index_mailbox_list *)_list;
+
+	return global ? GLOBAL_TEMP_PREFIX : list->temp_prefix;
+}
+
+static int index_list_set_subscribed(struct mailbox_list *_list,
+				     const char *name, bool set)
+{
+	struct index_mailbox_list *list = (struct index_mailbox_list *)_list;
+	const char *path;
+
+	path = t_strconcat(_list->set.control_dir != NULL ?
+			   _list->set.control_dir : _list->set.root_dir,
+			   "/", _list->set.subscription_fname, NULL);
+	return subsfile_set_subscribed(_list, path, list->temp_prefix,
+				       name, set);
+}
+
+static int
+index_list_node_exists(struct index_mailbox_list *list, const char *name,
+		       enum mailbox_existence *existence_r)
+{
+	struct mailbox_list_index_node *node;
+	int ret;
+
+	*existence_r = MAILBOX_EXISTENCE_NONE;
+
+	if ((ret = index_list_get_node(list, name, &node)) < 0)
+		return -1;
+	if (ret == 0)
+		return 0;
+
+	if ((node->flags & (MAILBOX_LIST_INDEX_FLAG_NONEXISTENT |
+			    MAILBOX_LIST_INDEX_FLAG_NOSELECT)) == 0) {
+		/* selectable */
+		*existence_r = MAILBOX_EXISTENCE_SELECT;
+	} else {
+		/* non-selectable */
+		*existence_r = MAILBOX_EXISTENCE_NOSELECT;
+	}
+	return 0;
+}
+
+static int
+index_list_mailbox_create_dir(struct index_mailbox_list *list, const char *name)
+{
+	struct mailbox_list_index_sync_context *sync_ctx;
+	struct mailbox_list_index_node *node;
+	uint32_t seq;
+	bool created;
+	int ret;
+
+	if (mailbox_list_index_sync_begin(&list->list, &sync_ctx) < 0)
+		return -1;
+
+	seq = mailbox_list_index_sync_name(sync_ctx, name, &node, &created);
+	if (created || (node->flags & MAILBOX_LIST_INDEX_FLAG_NONEXISTENT) != 0) {
+		/* didn't already exist */
+		node->flags = MAILBOX_LIST_INDEX_FLAG_NOSELECT;
+		mail_index_update_flags(sync_ctx->trans, seq, MODIFY_REPLACE,
+					(enum mail_flags)node->flags);
+		ret = 1;
+	} else {
+		/* already existed */
+		ret = 0;
+	}
+	if (mailbox_list_index_sync_end(&sync_ctx, TRUE) < 0)
+		ret = -1;
+	return ret;
+}
+
+static int
+index_list_mailbox_create_selectable(struct index_mailbox_list *list,
+				     const char *name, guid_128_t mailbox_guid)
+{
+	struct mailbox_list_index_sync_context *sync_ctx;
+	struct mailbox_list_index_record rec;
+	struct mailbox_list_index_node *node;
+	const void *data;
+	bool expunged, created;
+	uint32_t seq;
+
+	if (mailbox_list_index_sync_begin(&list->list, &sync_ctx) < 0)
+		return -1;
+
+	seq = mailbox_list_index_sync_name(sync_ctx, name, &node, &created);
+	if (!created &&
+	    (node->flags & (MAILBOX_LIST_INDEX_FLAG_NONEXISTENT |
+			    MAILBOX_LIST_INDEX_FLAG_NOSELECT)) == 0) {
+		/* already selectable */
+		(void)mailbox_list_index_sync_end(&sync_ctx, FALSE);
+		return 0;
+	}
+
+	mail_index_lookup_ext(sync_ctx->view, seq, sync_ctx->ilist->ext_id,
+			      &data, &expunged);
+	i_assert(data != NULL && !expunged);
+	memcpy(&rec, data, sizeof(rec));
+	i_assert(guid_128_is_empty(rec.guid));
+
+	/* make it selectable */
+	node->flags = 0;
+	mail_index_update_flags(sync_ctx->trans, seq, MODIFY_REPLACE, 0);
+
+	memcpy(rec.guid, mailbox_guid, sizeof(rec.guid));
+	mail_index_update_ext(sync_ctx->trans, seq, sync_ctx->ilist->ext_id,
+			      &rec, NULL);
+
+	if (mailbox_list_index_sync_end(&sync_ctx, TRUE) < 0)
+		return -1;
+	return 1;
+}
+
+static int
+index_list_mailbox_create(struct mailbox *box,
+			  const struct mailbox_update *update, bool directory)
+{
+	struct index_list_mailbox *ibox = INDEX_LIST_STORAGE_CONTEXT(box);
+	struct index_mailbox_list *list =
+		(struct index_mailbox_list *)box->list;
+	struct mailbox_update new_update;
+	enum mailbox_existence existence;
+	int ret;
+
+	/* first do a quick check that it doesn't exist */
+	if ((ret = index_list_node_exists(list, box->name, &existence)) < 0) {
+		mail_storage_copy_list_error(box->storage, box->list);
+		return -1;
+	}
+	if (existence == MAILBOX_EXISTENCE_NONE && directory) {
+		/* now add the directory to index locked */
+		if ((ret = index_list_mailbox_create_dir(list, box->name)) < 0) {
+			mail_storage_copy_list_error(box->storage, box->list);
+			return -1;
+		}
+	} else if (existence != MAILBOX_EXISTENCE_SELECT && !directory) {
+		/* if no GUID is requested, generate it ourself. set
+		   UIDVALIDITY to index sometimes later. */
+		if (update == NULL)
+			memset(&new_update, 0, sizeof(new_update));
+		else
+			new_update = *update;
+		if (guid_128_is_empty(new_update.mailbox_guid))
+			guid_128_generate(new_update.mailbox_guid);
+		ret = index_list_mailbox_create_selectable(list, box->name,
+							   new_update.mailbox_guid);
+		if (ret < 0) {
+			mail_storage_copy_list_error(box->storage, box->list);
+			return -1;
+		}
+		/* the storage backend needs to use the same GUID */
+		update = &new_update;
+	} else {
+		ret = 0;
+	}
+
+	if (ret == 0) {
+		mail_storage_set_error(box->storage, MAIL_ERROR_EXISTS,
+				       "Mailbox already exists");
+		return -1;
+	}
+	return directory ? 0 :
+		ibox->module_ctx.super.create_box(box, update, directory);
+}
+
+static void
+index_list_try_delete(struct index_mailbox_list *list, const char *name,
+		      enum mailbox_list_path_type type)
+{
+	struct mailbox_list *_list = &list->list;
+	const char *mailbox_path, *path;
+
+	if (mailbox_list_get_path(_list, name, MAILBOX_LIST_PATH_TYPE_MAILBOX,
+				  &mailbox_path) <= 0 ||
+	    mailbox_list_get_path(_list, name, type, &path) <= 0 ||
+	    strcmp(path, mailbox_path) == 0)
+		return;
+
+	if (*_list->set.maildir_name == '\0' &&
+	    (_list->flags & MAILBOX_LIST_FLAG_MAILBOX_FILES) == 0) {
+		/* this directory may contain also child mailboxes' data.
+		   we don't want to delete that. */
+		bool rmdir_path = *_list->set.maildir_name != '\0';
+		if (mailbox_list_delete_mailbox_nonrecursive(_list, name, path,
+							     rmdir_path) < 0)
+			return;
+	} else {
+		if (mailbox_list_delete_trash(path) < 0 &&
+		    errno != ENOENT && errno != ENOTEMPTY) {
+			mailbox_list_set_critical(_list,
+				"unlink_directory(%s) failed: %m", path);
+		}
+	}
+
+	/* avoid leaving empty directories lying around */
+	mailbox_list_delete_until_root(_list, path, type);
+}
+
+static void
+index_list_delete_finish(struct index_mailbox_list *list, const char *name)
+{
+	index_list_try_delete(list, name, MAILBOX_LIST_PATH_TYPE_INDEX);
+	index_list_try_delete(list, name, MAILBOX_LIST_PATH_TYPE_CONTROL);
+	index_list_try_delete(list, name, MAILBOX_LIST_PATH_TYPE_ALT_MAILBOX);
+}
+
+static int
+index_list_delete_entry(struct index_mailbox_list *list, const char *name,
+			bool delete_selectable)
+{
+	struct mailbox_list_index_sync_context *sync_ctx;
+	struct mailbox_list_index_record rec;
+	struct mailbox_list_index_node *node;
+	const void *data;
+	bool expunged;
+	uint32_t seq;
+	int ret;
+
+	if (mailbox_list_index_sync_begin(&list->list, &sync_ctx) < 0)
+		return -1;
+
+	if ((ret = index_list_get_node(list, name, &node)) < 0) {
+		(void)mailbox_list_index_sync_end(&sync_ctx, FALSE);
+		return -1;
+	}
+	if (ret == 0) {
+		(void)mailbox_list_index_sync_end(&sync_ctx, FALSE);
+		mailbox_list_set_error(&list->list, MAIL_ERROR_NOTFOUND,
+				       T_MAIL_ERR_MAILBOX_NOT_FOUND(name));
+		return -1;
+	}
+	if (!mail_index_lookup_seq(sync_ctx->view, node->uid, &seq))
+		i_panic("mailbox list index: lost uid=%u", node->uid);
+	if (delete_selectable) {
+		/* make it at least non-selectable */
+		node->flags = MAILBOX_LIST_INDEX_FLAG_NOSELECT;
+		mail_index_update_flags(sync_ctx->trans, seq, MODIFY_REPLACE,
+					(enum mail_flags)node->flags);
+
+		mail_index_lookup_ext(sync_ctx->view, seq,
+				      sync_ctx->ilist->ext_id,
+				      &data, &expunged);
+		i_assert(data != NULL && !expunged);
+		memcpy(&rec, data, sizeof(rec));
+		rec.uid_validity = 0;
+		memset(&rec.guid, 0, sizeof(rec.guid));
+		mail_index_update_ext(sync_ctx->trans, seq,
+				      sync_ctx->ilist->ext_id, &rec, NULL);
+	}
+	if (node->children != NULL) {
+		/* can't delete this directory before its children,
+		   but we may have made it non-selectable already */
+		if (mailbox_list_index_sync_end(&sync_ctx, TRUE) < 0)
+			return -1;
+		return 0;
+	}
+
+	/* we can remove the entire node */
+	mail_index_expunge(sync_ctx->trans, seq);
+	mailbox_list_index_node_unlink(sync_ctx->ilist, node);
+
+	if (mailbox_list_index_sync_end(&sync_ctx, TRUE) < 0)
+		return -1;
+	return 1;
+}
+
+static int
+index_list_delete_mailbox(struct mailbox_list *_list, const char *name)
+{
+	struct index_mailbox_list *list = (struct index_mailbox_list *)_list;
+	const char *path;
+	int ret;
+
+	/* first delete the mailbox files */
+	ret = mailbox_list_get_path(_list, name, MAILBOX_LIST_PATH_TYPE_MAILBOX,
+				    &path);
+	if (ret <= 0)
+		return ret;
+
+	if ((_list->flags & MAILBOX_LIST_FLAG_MAILBOX_FILES) != 0) {
+		ret = mailbox_list_delete_mailbox_file(_list, name, path);
+	} else {
+		ret = mailbox_list_delete_mailbox_nonrecursive(_list, name,
+							       path, TRUE);
+	}
+
+	if (ret == 0 || (_list->props & MAILBOX_LIST_PROP_AUTOCREATE_DIRS) != 0)
+		index_list_delete_finish(list, name);
+	if (ret == 0) {
+		if (index_list_delete_entry(list, name, TRUE) < 0)
+			return -1;
+	}
+	return ret;
+}
+
+static int
+index_list_delete_dir(struct mailbox_list *_list, const char *name)
+{
+	struct index_mailbox_list *list = (struct index_mailbox_list *)_list;
+	int ret;
+
+	if ((ret = index_list_delete_entry(list, name, FALSE)) < 0)
+		return -1;
+	if (ret == 0) {
+		mailbox_list_set_error(_list, MAIL_ERROR_EXISTS,
+			"Mailbox has children, delete them first");
+		return -1;
+	}
+	return 0;
+}
+
+static int
+index_list_delete_symlink(struct mailbox_list *_list,
+			  const char *name ATTR_UNUSED)
+{
+	mailbox_list_set_error(_list, MAIL_ERROR_NOTPOSSIBLE,
+			       "Symlinks not supported");
+	return -1;
+}
+
+static int
+index_list_rename_mailbox(struct mailbox_list *_oldlist, const char *oldname,
+			  struct mailbox_list *_newlist, const char *newname)
+{
+	struct index_mailbox_list *list = (struct index_mailbox_list *)_oldlist;
+	struct mailbox_list_index_sync_context *sync_ctx;
+	struct mailbox_list_index_record oldrec, newrec;
+	struct mailbox_list_index_node *oldnode, *newnode, *child;
+	const void *data;
+	bool created, expunged;
+	uint32_t oldseq, newseq;
+	int ret;
+
+	if (_oldlist != _newlist) {
+		mailbox_list_set_error(_oldlist, MAIL_ERROR_NOTPOSSIBLE,
+			"Renaming not supported across namespaces.");
+		return -1;
+	}
+
+	if (mailbox_list_index_sync_begin(&list->list, &sync_ctx) < 0)
+		return -1;
+
+	if ((ret = index_list_get_node(list, oldname, &oldnode)) < 0) {
+		(void)mailbox_list_index_sync_end(&sync_ctx, FALSE);
+		return -1;
+	}
+	if (!mail_index_lookup_seq(sync_ctx->view, oldnode->uid, &oldseq))
+		i_panic("mailbox list index: lost uid=%u", oldnode->uid);
+
+	newseq = mailbox_list_index_sync_name(sync_ctx, newname,
+					      &newnode, &created);
+	if (!created) {
+		(void)mailbox_list_index_sync_end(&sync_ctx, FALSE);
+		mailbox_list_set_error(&list->list, MAIL_ERROR_EXISTS,
+				       "Target mailbox already exists");
+		return -1;
+	}
+	i_assert(oldnode != newnode);
+
+	/* copy all the data from old node to new node */
+	newnode->uid = oldnode->uid;
+	newnode->flags = oldnode->flags;
+	newnode->children = oldnode->children; oldnode->children = NULL;
+	for (child = newnode->children; child != NULL; child = child->next)
+		child->parent = newnode;
+
+	/* remove the old node from existence */
+	mailbox_list_index_node_unlink(sync_ctx->ilist, oldnode);
+
+	/* update the old index record to contain the new name_id/parent_uid,
+	   then expunge the added index record */
+	mail_index_lookup_ext(sync_ctx->view, oldseq, sync_ctx->ilist->ext_id,
+			      &data, &expunged);
+	i_assert(data != NULL && !expunged);
+	memcpy(&oldrec, data, sizeof(oldrec));
+
+	mail_index_lookup_ext(sync_ctx->view, newseq, sync_ctx->ilist->ext_id,
+			      &data, &expunged);
+	i_assert(data != NULL && !expunged);
+	memcpy(&newrec, data, sizeof(newrec));
+
+	oldrec.name_id = newrec.name_id;
+	oldrec.parent_uid = newrec.parent_uid;
+
+	mail_index_update_ext(sync_ctx->trans, oldseq,
+			      sync_ctx->ilist->ext_id, &oldrec, NULL);
+	mail_index_expunge(sync_ctx->trans, newseq);
+
+	return mailbox_list_index_sync_end(&sync_ctx, TRUE);
+}
+
+static struct mailbox_list_iterate_context *
+index_list_iter_init(struct mailbox_list *list,
+		     const char *const *patterns ATTR_UNUSED,
+		     enum mailbox_list_iter_flags flags)
+{
+	struct mailbox_list_iterate_context *ctx;
+	pool_t pool;
+
+	pool = pool_alloconly_create("mailbox list index iter", 1024);
+	ctx = p_new(pool, struct mailbox_list_iterate_context, 1);
+	ctx->pool = pool;
+	ctx->list = list;
+	ctx->flags = flags;
+	array_create(&ctx->module_contexts, pool, sizeof(void *), 5);
+	return ctx;
+}
+
+static const struct mailbox_info *
+index_list_iter_next(struct mailbox_list_iterate_context *ctx ATTR_UNUSED)
+{
+	return NULL;
+}
+
+static int index_list_iter_deinit(struct mailbox_list_iterate_context *ctx)
+{
+	pool_unref(&ctx->pool);
+	return 0;
+}
+
+struct mailbox_list index_mailbox_list = {
+	.name = MAILBOX_LIST_NAME_INDEX,
+	.props = 0,
+	.mailbox_name_max_length = MAILBOX_LIST_NAME_MAX_LENGTH,
+
+	{
+		index_list_alloc,
+		index_list_deinit,
+		NULL,
+		index_list_get_hierarchy_sep,
+		mailbox_list_default_get_vname,
+		mailbox_list_default_get_storage_name,
+		index_list_get_path,
+		index_list_get_temp_prefix,
+		NULL,
+		index_list_iter_init,
+		index_list_iter_next,
+		index_list_iter_deinit,
+		NULL,
+		NULL,
+		mailbox_list_subscriptions_refresh,
+		index_list_set_subscribed,
+		index_list_delete_mailbox,
+		index_list_delete_dir,
+		index_list_delete_symlink,
+		index_list_rename_mailbox,
+		NULL, NULL, NULL, NULL
+	}
+};
+
+void mailbox_list_index_backend_init_mailbox(struct mailbox *box)
+{
+	if (strcmp(box->list->name, MAILBOX_LIST_NAME_INDEX) != 0)
+		return;
+	box->v.create_box = index_list_mailbox_create;
+}

--- a/src/lib-storage/list/mailbox-list-index-iter.c	Fri Sep 28 00:03:12 2012 +0300
+++ b/src/lib-storage/list/mailbox-list-index-iter.c	Fri Sep 28 00:11:19 2012 +0300
@@ -7,6 +7,29 @@
 #include "mailbox-list-subscriptions.h"
 #include "mailbox-list-index.h"
 
+static bool iter_use_index(struct mailbox_list_index_iterate_context *ctx)
+{
+	struct mailbox_list_index *ilist = INDEX_LIST_CONTEXT(ctx->ctx.list);
+
+	if ((ctx->ctx.flags & MAILBOX_LIST_ITER_SELECT_SUBSCRIBED) != 0) {
+		/* for now we don't use indexes when listing subscriptions,
+		   because it needs to list also the nonexistent subscribed
+		   mailboxes, which don't exist in the index. */
+		return FALSE;
+	}
+	if ((ctx->ctx.flags & MAILBOX_LIST_ITER_RAW_LIST) != 0 &&
+	    ilist->has_backing_store) {
+		/* no indexing wanted with raw lists */
+		return FALSE;
+	}
+	if (mailbox_list_index_refresh(ctx->ctx.list) < 0 &&
+	    ilist->has_backing_store) {
+		/* refresh failed */
+		return FALSE;
+	}
+	return TRUE;
+}
+
 struct mailbox_list_iterate_context *
 mailbox_list_index_iter_init(struct mailbox_list *list,
 			     const char *const *patterns,
@@ -27,12 +50,7 @@
 	ctx->sep = ns_sep;
 	ctx->info_pool = pool_alloconly_create("mailbox list index iter info", 128);
 
-	/* for now we don't use indexes when listing subscriptions, because
-	   it needs to list also the nonexistent subscribed mailboxes, which
-	   don't exist in the index. */
-	if ((flags & MAILBOX_LIST_ITER_RAW_LIST) != 0 ||
-	    (flags & MAILBOX_LIST_ITER_SELECT_SUBSCRIBED) != 0 ||
-	    mailbox_list_index_refresh(ctx->ctx.list) < 0) {
+	if (!iter_use_index(ctx)) {
 		/* no indexing */
 		ctx->backend_ctx = ilist->module_ctx.super.
 			iter_init(list, patterns, flags);

--- a/src/lib-storage/list/mailbox-list-index-notify.c	Fri Sep 28 00:03:12 2012 +0300
+++ b/src/lib-storage/list/mailbox-list-index-notify.c	Fri Sep 28 00:11:19 2012 +0300
@@ -149,7 +149,8 @@
 	if (index_node == NULL) {
 		/* re-parse the index list using the given view. we could be
 		   jumping here between old and new view. */
-		(void)mailbox_list_index_parse(ilist, view, FALSE);
+		(void)mailbox_list_index_parse(inotify->notify.list,
+					       view, FALSE);
 		index_node = mailbox_list_index_lookup_uid(ilist, uid);
 		if (index_node == NULL)
 			return NULL;
@@ -355,8 +356,6 @@
 static void
 mailbox_list_index_notify_find_renames(struct mailbox_list_notify_index *inotify)
 {
-	struct mailbox_list_index *ilist =
-		INDEX_LIST_CONTEXT(inotify->notify.list);
 	ARRAY(struct mailbox_list_inotify_entry) entries;
 	struct mailbox_status status;
 	struct mailbox_list_notify_rename *rename;
@@ -381,7 +380,8 @@
 		}
 	}
 
-	(void)mailbox_list_index_parse(ilist, inotify->view, TRUE);
+	(void)mailbox_list_index_parse(inotify->notify.list,
+				       inotify->view, TRUE);
 	while (seq_range_array_iter_nth(&inotify->new_uids_iter,
 					inotify->new_uids_n++, &uid)) {
 		if (notify_lookup_guid(inotify, inotify->view, uid,

--- a/src/lib-storage/list/mailbox-list-index-status.c	Fri Sep 28 00:03:12 2012 +0300
+++ b/src/lib-storage/list/mailbox-list-index-status.c	Fri Sep 28 00:11:19 2012 +0300
@@ -3,22 +3,15 @@
 #include "lib.h"
 #include "array.h"
 #include "mail-index-modseq.h"
-#include "mail-storage-private.h"
+#include "mailbox-list-index-storage.h"
 #include "mailbox-list-index.h"
 
-#define INDEX_LIST_STORAGE_CONTEXT(obj) \
-	MODULE_CONTEXT(obj, index_list_storage_module)
-
 #define CACHED_STATUS_ITEMS \
 	(STATUS_MESSAGES | STATUS_UNSEEN | STATUS_RECENT | \
 	 STATUS_UIDNEXT | STATUS_UIDVALIDITY | STATUS_HIGHESTMODSEQ)
 
-struct index_list_mailbox {
-	union mailbox_module_context module_ctx;
-};
-
-static MODULE_CONTEXT_DEFINE_INIT(index_list_storage_module,
-				  &mail_storage_module_register);
+struct index_list_storage_module index_list_storage_module =
+	MODULE_CONTEXT_INIT(&mail_storage_module_register);
 
 static int
 index_list_open_view(struct mailbox *box, struct mail_index_view **view_r,
@@ -410,22 +403,12 @@
 		*flags |= MAILBOX_UNMARKED;
 }
 
-static void index_list_mail_mailbox_allocated(struct mailbox *box)
+void mailbox_list_index_status_init_mailbox(struct mailbox *box)
 {
-	struct mailbox_list_index *ilist = INDEX_LIST_CONTEXT(box->list);
-	struct index_list_mailbox *ibox;
-
-	if (ilist == NULL)
-		return;
-
-	ibox = p_new(box->pool, struct index_list_mailbox, 1);
-	ibox->module_ctx.super = box->v;
 	box->v.get_status = index_list_get_status;
 	box->v.get_metadata = index_list_get_metadata;
 	box->v.sync_deinit = index_list_sync_deinit;
 	box->v.transaction_commit = index_list_transaction_commit;
-
-	MODULE_CONTEXT_SET(box, index_list_storage_module, ibox);
 }
 
 void mailbox_list_index_status_init_list(struct mailbox_list *list)
@@ -440,12 +423,3 @@
 		mail_index_ext_register(ilist->index, "hmodseq", 0,
 					sizeof(uint64_t), sizeof(uint64_t));
 }
-
-static struct mail_storage_hooks mailbox_list_index_status_hooks = {
-	.mailbox_allocated = index_list_mail_mailbox_allocated
-};
-
-void mailbox_list_index_status_init(void)
-{
-	mail_storage_hooks_add_internal(&mailbox_list_index_status_hooks);
-}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib-storage/list/mailbox-list-index-storage.h	Fri Sep 28 00:11:19 2012 +0300
@@ -0,0 +1,16 @@
+#ifndef MAILBOX_LIST_INDEX_STORAGE_H
+#define MAILBOX_LIST_INDEX_STORAGE_H
+
+#include "mail-storage-private.h"
+
+#define INDEX_LIST_STORAGE_CONTEXT(obj) \
+	MODULE_CONTEXT(obj, index_list_storage_module)
+
+struct index_list_mailbox {
+	union mailbox_module_context module_ctx;
+};
+
+extern MODULE_CONTEXT_DEFINE(index_list_storage_module,
+			     &mail_storage_module_register);
+
+#endif

--- a/src/lib-storage/list/mailbox-list-index-sync.c	Fri Sep 28 00:03:12 2012 +0300
+++ b/src/lib-storage/list/mailbox-list-index-sync.c	Fri Sep 28 00:11:19 2012 +0300
@@ -6,18 +6,7 @@
 #include "str.h"
 #include "mail-index.h"
 #include "mail-storage.h"
-#include "mailbox-list-index.h"
-
-struct mailbox_list_index_sync_context {
-	struct mailbox_list *list;
-	struct mailbox_list_index *ilist;
-	char sep[2];
-	uint32_t next_uid;
-
-	struct mail_index_sync_ctx *sync_ctx;
-	struct mail_index_view *view;
-	struct mail_index_transaction *trans;
-};
+#include "mailbox-list-index-sync.h"
 
 static void
 node_lookup_guid(struct mailbox_list_index_sync_context *ctx,
@@ -52,7 +41,7 @@
 
 	/* get mailbox GUID if possible. we need to do this early in here to
 	   make mailbox rename detection work in NOTIFY */
-	T_BEGIN {
+	if (ctx->syncing_list) T_BEGIN {
 		node_lookup_guid(ctx, node, irec.guid);
 	} T_END;
 
@@ -99,10 +88,10 @@
 	return node;
 }
 
-static uint32_t
-mailbox_list_index_sync_name(struct mailbox_list_index_sync_context *ctx,
-			     const char *name,
-			     enum mailbox_list_index_flags flags)
+uint32_t mailbox_list_index_sync_name(struct mailbox_list_index_sync_context *ctx,
+				      const char *name,
+				      struct mailbox_list_index_node **node_r,
+				      bool *created_r)
 {
 	const char *const *path, *empty_path[] = { "", NULL };
 	struct mailbox_list_index_node *node, *parent;
@@ -129,15 +118,17 @@
 		i_assert(node != NULL);
 		if (!mail_index_lookup_seq(ctx->view, node->uid, &seq))
 			i_panic("mailbox list index: lost uid=%u", node->uid);
+		*created_r = FALSE;
 	} else {
 		/* create missing parts of the path */
 		for (; path[i] != NULL; i++) {
 			node = mailbox_list_index_node_add(ctx, node, path[i],
 							   &seq);
 		}
+		*created_r = TRUE;
 	}
 
-	node->flags = flags | MAILBOX_LIST_INDEX_FLAG_SYNC_EXISTS;
+	*node_r = node;
 	return seq;
 }
 
@@ -146,11 +137,9 @@
 		      const struct mailbox_list_index_node *node)
 {
 	for (; node != NULL; node = node->next) {
-		if ((node->flags & MAILBOX_LIST_INDEX_FLAG_SYNC_EXISTS) != 0) {
-			if (node->children != NULL)
-				get_existing_name_ids(ids, node->children);
-			array_append(ids, &node->name_id, 1);
-		}
+		if (node->children != NULL)
+			get_existing_name_ids(ids, node->children);
+		array_append(ids, &node->name_id, 1);
 	}
 }
 
@@ -218,20 +207,6 @@
 }
 
 static void
-mailbox_list_index_node_unlink(struct mailbox_list_index *ilist,
-			       struct mailbox_list_index_node *node)
-{
-	struct mailbox_list_index_node **prev;
-
-	prev = node->parent == NULL ?
-		&ilist->mailbox_tree : &node->parent->children;
-
-	while (*prev != node)
-		prev = &(*prev)->next;
-	*prev = node->next;
-}
-
-static void
 sync_expunge_nonexistent(struct mailbox_list_index_sync_context *sync_ctx,
 			 struct mailbox_list_index_node *node)
 {
@@ -251,61 +226,78 @@
 	}
 }
 
-int mailbox_list_index_sync(struct mailbox_list *list)
+int mailbox_list_index_sync_begin(struct mailbox_list *list,
+				  struct mailbox_list_index_sync_context **sync_ctx_r)
 {
 	struct mailbox_list_index *ilist = INDEX_LIST_CONTEXT(list);
-	struct mailbox_list_index_sync_context sync_ctx;
-	struct mailbox_list_iterate_context *iter;
+	struct mailbox_list_index_sync_context *sync_ctx;
+	struct mail_index_sync_ctx *index_sync_ctx;
 	struct mail_index_view *view;
+	struct mail_index_transaction *trans;
 	const struct mail_index_header *hdr;
-	const struct mailbox_info *info;
-	const char *patterns[2];
-	enum mailbox_list_index_flags flags;
-	uint32_t seq, orig_highest_name_id;
 
-	mailbox_list_index_reset(ilist);
-
-	memset(&sync_ctx, 0, sizeof(sync_ctx));
-	sync_ctx.list = list;
-	sync_ctx.ilist = ilist;
-	sync_ctx.sep[0] = mailbox_list_get_hierarchy_sep(list);
-	if (mail_index_sync_begin(ilist->index, &sync_ctx.sync_ctx,
-				  &view, &sync_ctx.trans,
+	if (mail_index_sync_begin(ilist->index, &index_sync_ctx, &view, &trans,
 				  MAIL_INDEX_SYNC_FLAG_AVOID_FLAG_UPDATES) < 0) {
 		mailbox_list_index_set_index_error(list);
 		return -1;
 	}
+	mailbox_list_index_reset(ilist);
 
 	/* re-parse mailbox list now that it's refreshed and locked */
-	if (mailbox_list_index_parse(ilist, view, TRUE) < 0) {
-		mail_index_sync_rollback(&sync_ctx.sync_ctx);
+	if (mailbox_list_index_parse(list, view, TRUE) < 0) {
+		mail_index_sync_rollback(&index_sync_ctx);
 		return -1;
 	}
-	orig_highest_name_id = ilist->highest_name_id;
+
+	sync_ctx = i_new(struct mailbox_list_index_sync_context, 1);
+	sync_ctx->list = list;
+	sync_ctx->ilist = ilist;
+	sync_ctx->sep[0] = mailbox_list_get_hierarchy_sep(list);
+	sync_ctx->orig_highest_name_id = ilist->highest_name_id;
+	sync_ctx->index_sync_ctx = index_sync_ctx;
+	sync_ctx->trans = trans;
 
 	hdr = mail_index_get_header(view);
-	sync_ctx.next_uid = hdr->next_uid;
+	sync_ctx->next_uid = hdr->next_uid;
 
 	if (hdr->uid_validity == 0) {
 		/* first time indexing, set uidvalidity */
 		uint32_t uid_validity = ioloop_time;
 
-		mail_index_update_header(sync_ctx.trans,
+		mail_index_update_header(trans,
 			offsetof(struct mail_index_header, uid_validity),
 			&uid_validity, sizeof(uid_validity), TRUE);
 	}
-	sync_ctx.view = mail_index_transaction_open_updated_view(sync_ctx.trans);
+	sync_ctx->view = mail_index_transaction_open_updated_view(trans);
+	ilist->syncing = TRUE;
+
+	*sync_ctx_r = sync_ctx;
+	return 0;
+}
+
+static int
+mailbox_list_index_sync_list(struct mailbox_list_index_sync_context *sync_ctx)
+{
+	struct mailbox_list_iterate_context *iter;
+	const struct mailbox_info *info;
+	enum mailbox_list_index_flags flags;
+	const char *patterns[2];
+	struct mailbox_list_index_node *node;
+	uint32_t seq;
+	bool created;
 
 	/* clear EXISTS-flags, so after sync we know what can be expunged */
-	mailbox_list_index_node_clear_exists(ilist->mailbox_tree);
+	mailbox_list_index_node_clear_exists(sync_ctx->ilist->mailbox_tree);
 
 	/* don't include autocreated mailboxes in index until they're
 	   actually created. */
-	ilist->syncing = TRUE;
 	patterns[0] = "*"; patterns[1] = NULL;
-	iter = ilist->module_ctx.super.
-		iter_init(list, patterns, MAILBOX_LIST_ITER_NO_AUTO_BOXES);
-	while ((info = ilist->module_ctx.super.iter_next(iter)) != NULL) {
+	iter = sync_ctx->ilist->module_ctx.super.
+		iter_init(sync_ctx->list, patterns,
+			  MAILBOX_LIST_ITER_NO_AUTO_BOXES);
+
+	sync_ctx->syncing_list = TRUE;
+	while ((info = sync_ctx->ilist->module_ctx.super.iter_next(iter)) != NULL) {
 		flags = 0;
 		if ((info->flags & MAILBOX_NONEXISTENT) != 0)
 			flags |= MAILBOX_LIST_INDEX_FLAG_NONEXISTENT;
@@ -318,42 +310,77 @@
 			const char *name =
 				mailbox_list_get_storage_name(info->ns->list,
 							      info->vname);
-			seq = mailbox_list_index_sync_name(&sync_ctx,
-							   name, flags);
+			seq = mailbox_list_index_sync_name(sync_ctx, name,
+							   &node, &created);
 		} T_END;
 
-		mail_index_update_flags(sync_ctx.trans, seq,
+		node->flags = flags | MAILBOX_LIST_INDEX_FLAG_SYNC_EXISTS;
+		mail_index_update_flags(sync_ctx->trans, seq,
 					MODIFY_REPLACE, (enum mail_flags)flags);
 	}
-	if (ilist->module_ctx.super.iter_deinit(iter) < 0) {
-		mail_index_sync_rollback(&sync_ctx.sync_ctx);
-		mail_index_view_close(&sync_ctx.view);
-		ilist->syncing = FALSE;
+	sync_ctx->syncing_list = FALSE;
+
+	if (sync_ctx->ilist->module_ctx.super.iter_deinit(iter) < 0)
 		return -1;
-	}
 
-	sync_expunge_nonexistent(&sync_ctx, ilist->mailbox_tree);
+	/* successfully listed everything, expunge any unseen mailboxes */
+	sync_expunge_nonexistent(sync_ctx, sync_ctx->ilist->mailbox_tree);
+	return 0;
+}
 
-	if (orig_highest_name_id != ilist->highest_name_id) {
+static void
+mailbox_list_index_sync_update_hdr(struct mailbox_list_index_sync_context *sync_ctx)
+{
+	if (sync_ctx->orig_highest_name_id != sync_ctx->ilist->highest_name_id) {
 		/* new names added. this implicitly resets refresh flag */
 		T_BEGIN {
-			mailbox_list_index_sync_names(&sync_ctx);
+			mailbox_list_index_sync_names(sync_ctx);
 		} T_END;
-	} else if (mailbox_list_index_need_refresh(ilist, sync_ctx.view)) {
+	} else if (mailbox_list_index_need_refresh(sync_ctx->ilist,
+						   sync_ctx->view)) {
 		/* we're synced, reset refresh flag */
 		struct mailbox_list_index_header new_hdr;
 
 		new_hdr.refresh_flag = 0;
-		mail_index_update_header_ext(sync_ctx.trans, ilist->ext_id,
+		mail_index_update_header_ext(sync_ctx->trans, sync_ctx->ilist->ext_id,
 			offsetof(struct mailbox_list_index_header, refresh_flag),
 			&new_hdr.refresh_flag, sizeof(new_hdr.refresh_flag));
 	}
-	ilist->syncing = FALSE;
-	mail_index_view_close(&sync_ctx.view);
+}
+
+int mailbox_list_index_sync_end(struct mailbox_list_index_sync_context **_sync_ctx,
+				bool success)
+{
+	struct mailbox_list_index_sync_context *sync_ctx = *_sync_ctx;
+	int ret;
+
+	*_sync_ctx = NULL;
+
+	if (success)
+		mailbox_list_index_sync_update_hdr(sync_ctx);
+	mail_index_view_close(&sync_ctx->view);
 
-	if (mail_index_sync_commit(&sync_ctx.sync_ctx) < 0) {
-		mailbox_list_index_set_index_error(list);
+	if (success) {
+		if ((ret = mail_index_sync_commit(&sync_ctx->index_sync_ctx)) < 0)
+			mailbox_list_index_set_index_error(sync_ctx->list);
+	} else {
+		mail_index_sync_rollback(&sync_ctx->index_sync_ctx);
+		ret = -1;
+	}
+	sync_ctx->ilist->syncing = FALSE;
+	i_free(sync_ctx);
+	return ret;
+}
+
+int mailbox_list_index_sync(struct mailbox_list *list)
+{
+	struct mailbox_list_index_sync_context *sync_ctx;
+	int ret = 0;
+
+	if (mailbox_list_index_sync_begin(list, &sync_ctx) < 0)
 		return -1;
-	}
-	return 0;
+
+	if (sync_ctx->ilist->has_backing_store)
+		ret = mailbox_list_index_sync_list(sync_ctx);
+	return mailbox_list_index_sync_end(&sync_ctx, ret == 0);
 }

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib-storage/list/mailbox-list-index-sync.h	Fri Sep 28 00:11:19 2012 +0300
@@ -0,0 +1,32 @@
+#ifndef MAILBOX_LIST_INDEX_SYNC_H
+#define MAILBOX_LIST_INDEX_SYNC_H
+
+#include "mailbox-list-index.h"
+
+struct mailbox_list_index_sync_context {
+	struct mailbox_list *list;
+	struct mailbox_list_index *ilist;
+	char sep[2];
+	uint32_t next_uid;
+	uint32_t orig_highest_name_id;
+
+	struct mail_index_sync_ctx *index_sync_ctx;
+	struct mail_index_view *view;
+	struct mail_index_transaction *trans;
+
+	unsigned int syncing_list:1;
+};
+
+int mailbox_list_index_sync_begin(struct mailbox_list *list,
+				  struct mailbox_list_index_sync_context **sync_ctx_r);
+int mailbox_list_index_sync_end(struct mailbox_list_index_sync_context **_sync_ctx,
+				bool success);
+int mailbox_list_index_sync(struct mailbox_list *list);
+
+/* Add name to index, return seq in index. */
+uint32_t mailbox_list_index_sync_name(struct mailbox_list_index_sync_context *ctx,
+				      const char *name,
+				      struct mailbox_list_index_node **node_r,
+				      bool *created_r);
+
+#endif

--- a/src/lib-storage/list/mailbox-list-index.c	Fri Sep 28 00:03:12 2012 +0300
+++ b/src/lib-storage/list/mailbox-list-index.c	Fri Sep 28 00:11:19 2012 +0300
@@ -7,7 +7,8 @@
 #include "mail-index-view-private.h"
 #include "mail-storage-hooks.h"
 #include "mail-storage-private.h"
-#include "mailbox-list-index.h"
+#include "mailbox-list-index-storage.h"
+#include "mailbox-list-index-sync.h"
 
 #define MAILBOX_LIST_INDEX_REFRESH_DELAY_MSECS 1000
 
@@ -125,6 +126,19 @@
 	str_append(str, node->name);
 }
 
+void mailbox_list_index_node_unlink(struct mailbox_list_index *ilist,
+				    struct mailbox_list_index_node *node)
+{
+	struct mailbox_list_index_node **prev;
+
+	prev = node->parent == NULL ?
+		&ilist->mailbox_tree : &node->parent->children;
+
+	while (*prev != node)
+		prev = &(*prev)->next;
+	*prev = node->next;
+}
+
 static int mailbox_list_index_parse_header(struct mailbox_list_index *ilist,
 					   struct mail_index_view *view)
 {
@@ -168,15 +182,36 @@
 	return 0;
 }
 
+static void
+mailbox_list_index_generate_name(struct mailbox_list_index *ilist,
+				 struct mailbox_list_index_node *node)
+{
+	guid_128_t guid;
+	char *name;
+
+	guid_128_generate(guid);
+	name = p_strdup_printf(ilist->mailbox_pool, "unknown-%s",
+			       guid_128_to_string(guid));
+	node->name = name;
+
+	hash_table_insert(ilist->mailbox_names,
+			  POINTER_CAST(node->name_id), name);
+	if (ilist->highest_name_id < node->name_id)
+		ilist->highest_name_id = node->name_id;
+}
+
 static int mailbox_list_index_parse_records(struct mailbox_list_index *ilist,
-					    struct mail_index_view *view)
+					    struct mail_index_view *view,
+					    const char **error_r)
 {
 	struct mailbox_list_index_node *node;
 	const struct mail_index_record *rec;
 	const struct mailbox_list_index_record *irec;
 	const void *data;
 	bool expunged;
-	uint32_t seq, count;
+	uint32_t seq, uid, count;
+
+	*error_r = NULL;
 
 	count = mail_index_view_get_messages_count(view);
 	for (seq = 1; seq <= count; seq++) {
@@ -188,38 +223,64 @@
 
 		mail_index_lookup_ext(view, seq, ilist->ext_id,
 				      &data, &expunged);
-		if (data == NULL)
+		if (data == NULL) {
+			*error_r = "Missing list extension data";
 			return -1;
+		}
 		irec = data;
 
 		node->name_id = irec->name_id;
 		node->name = hash_table_lookup(ilist->mailbox_names,
 					       POINTER_CAST(irec->name_id));
-		if (node->name == NULL)
-			return -1;
-
-		if (irec->parent_uid != 0) {
-			node->parent = mailbox_list_index_lookup_uid(ilist,
-							irec->parent_uid);
-			if (node->parent == NULL)
+		if (node->name == NULL) {
+			*error_r = "name_id not in index header";
+			if (ilist->has_backing_store)
 				return -1;
-			node->next = node->parent->children;
-			node->parent->children = node;
-		} else {
-			node->next = ilist->mailbox_tree;
-			ilist->mailbox_tree = node;
+			/* generate a new name and use it */
+			mailbox_list_index_generate_name(ilist, node);
 		}
 		hash_table_insert(ilist->mailbox_hash,
 				  POINTER_CAST(node->uid), node);
 	}
-	return 0;
+
+	/* do a second scan to create the actual mailbox tree hierarchy.
+	   this is needed because the parent_uid may be smaller or higher than
+	   the current node's uid */
+	for (seq = 1; seq <= count; seq++) {
+		mail_index_lookup_uid(view, seq, &uid);
+		mail_index_lookup_ext(view, seq, ilist->ext_id,
+				      &data, &expunged);
+		irec = data;
+
+		node = mailbox_list_index_lookup_uid(ilist, uid);
+		i_assert(node != NULL);
+
+		if (irec->parent_uid != 0) {
+			/* node should have a parent */
+			node->parent = mailbox_list_index_lookup_uid(ilist,
+							irec->parent_uid);
+			if (node->parent != NULL) {
+				node->next = node->parent->children;
+				node->parent->children = node;
+				continue;
+			}
+			*error_r = "parent_uid points to nonexistent record";
+			if (ilist->has_backing_store)
+				return -1;
+			/* just place it under the root */
+		}
+		node->next = ilist->mailbox_tree;
+		ilist->mailbox_tree = node;
+	}
+	return *error_r == NULL ? 0 : -1;
 }
 
-int mailbox_list_index_parse(struct mailbox_list_index *ilist,
+int mailbox_list_index_parse(struct mailbox_list *list,
 			     struct mail_index_view *view, bool force)
 {
+	struct mailbox_list_index *ilist = INDEX_LIST_CONTEXT(list);
 	const struct mail_index_header *hdr;
-	int ret;
+	const char *error;
 
 	i_assert(ilist->iter_refcount == 0);
 
@@ -235,13 +296,24 @@
 	ilist->sync_log_file_seq = hdr->log_file_seq;
 	ilist->sync_log_file_offset = hdr->log_file_head_offset;
 
-	ret = mailbox_list_index_parse_header(ilist, view);
-	if (ret == 0)
-		ret = mailbox_list_index_parse_records(ilist, view);
-	if (ret < 0) {
-		i_error("Corrupted mailbox list index %s", ilist->path);
-		mail_index_mark_corrupted(ilist->index);
-		return -1;
+	if (mailbox_list_index_parse_header(ilist, view) < 0) {
+		mailbox_list_set_critical(list,
+			"Corrupted mailbox list index header %s", ilist->path);
+		if (ilist->has_backing_store) {
+			mail_index_mark_corrupted(ilist->index);
+			return -1;
+		}
+	}
+	if (mailbox_list_index_parse_records(ilist, view, &error) < 0) {
+		mailbox_list_set_critical(list,
+			"Corrupted mailbox list index %s: %s",
+			ilist->path, error);
+		if (ilist->has_backing_store) {
+			mail_index_mark_corrupted(ilist->index);
+			return -1;
+		}
+		/* FIXME: find any missing mailboxes, add them and write the
+		   index back. */
 	}
 	return 0;
 }
@@ -253,6 +325,9 @@
 	const void *data;
 	size_t size;
 
+	if (!ilist->has_backing_store)
+		return FALSE;
+
 	mail_index_get_header_ext(view, ilist->ext_id, &data, &size);
 	hdr = data;
 	return hdr != NULL && hdr->refresh_flag != 0;
@@ -281,7 +356,7 @@
 		/* refresh list of mailboxes */
 		ret = mailbox_list_index_sync(list);
 	} else {
-		ret = mailbox_list_index_parse(ilist, view, FALSE);
+		ret = mailbox_list_index_parse(list, view, FALSE);
 	}
 	mail_index_view_close(&view);
 	return ret;
@@ -302,6 +377,9 @@
 	struct mail_index_view *view;
 	struct mail_index_transaction *trans;
 
+	if (!ilist->has_backing_store)
+		return;
+
 	mailbox_list_index_index_open(list);
 
 	view = mail_index_view_open(ilist->index);
@@ -414,10 +492,15 @@
 {
 	struct mailbox_list_index *ilist;
 	const char *dir;
+	bool has_backing_store;
+
+	/* layout=index doesn't have any backing store */
+	has_backing_store = strcmp(list->name, MAILBOX_LIST_NAME_INDEX) != 0;
 
 	if (!list->mail_set->mailbox_list_index) {
 		/* reserve the module context anyway, so syncing code knows
 		   that the index is disabled */
+		i_assert(has_backing_store);
 		ilist = NULL;
 		MODULE_CONTEXT_SET(list, mailbox_list_index_module, ilist);
 		return;
@@ -432,9 +515,11 @@
 		   each of which may have different ACLs */
 		dir = NULL;
 	}
+	i_assert(has_backing_store || dir != NULL);
 
 	ilist = p_new(list->pool, struct mailbox_list_index, 1);
 	ilist->module_ctx.super = list->v;
+	ilist->has_backing_store = has_backing_store;
 
 	list->v.deinit = mailbox_list_index_deinit;
 	list->v.iter_init = mailbox_list_index_iter_init;
@@ -472,8 +557,25 @@
 	mailbox_list_index_status_init_list(list);
 }
 
+static void mailbox_list_index_mailbox_allocated(struct mailbox *box)
+{
+	struct mailbox_list_index *ilist = INDEX_LIST_CONTEXT(box->list);
+	struct index_list_mailbox *ibox;
+
+	if (ilist == NULL)
+		return;
+
+	ibox = p_new(box->pool, struct index_list_mailbox, 1);
+	ibox->module_ctx.super = box->v;
+	MODULE_CONTEXT_SET(box, index_list_storage_module, ibox);
+
+	mailbox_list_index_status_init_mailbox(box);
+	mailbox_list_index_backend_init_mailbox(box);
+}
+
 static struct mail_storage_hooks mailbox_list_index_hooks = {
-	.mailbox_list_created = mailbox_list_index_created
+	.mailbox_list_created = mailbox_list_index_created,
+	.mailbox_allocated = mailbox_list_index_mailbox_allocated
 };
 
 void mailbox_list_index_init(void); /* called in mailbox-list-register.c */
@@ -481,5 +583,4 @@
 void mailbox_list_index_init(void)
 {
 	mail_storage_hooks_add_internal(&mailbox_list_index_hooks);
-	mailbox_list_index_status_init();
 }

--- a/src/lib-storage/list/mailbox-list-index.h	Fri Sep 28 00:03:12 2012 +0300
+++ b/src/lib-storage/list/mailbox-list-index.h	Fri Sep 28 00:11:19 2012 +0300
@@ -24,16 +24,17 @@
 
 #include "module-context.h"
 #include "mail-types.h"
+#include "mail-storage.h"
 #include "mailbox-list-private.h"
 
+#define MAILBOX_LIST_NAME_INDEX "index"
+#define MAILBOX_LIST_INDEX_HIERARHCY_SEP '~'
 #define MAILBOX_LIST_INDEX_PREFIX "dovecot.list.index"
 
 #define INDEX_LIST_CONTEXT(obj) \
 	MODULE_CONTEXT(obj, mailbox_list_index_module)
 
 struct mail_index_view;
-struct mailbox;
-struct mailbox_status;
 
 /* stored in mail_index_record.flags: */
 enum mailbox_list_index_flags {
@@ -107,6 +108,7 @@
 
 	unsigned int opened:1;
 	unsigned int syncing:1;
+	unsigned int has_backing_store:1;
 };
 
 struct mailbox_list_index_iterate_context {
@@ -134,6 +136,8 @@
 mailbox_list_index_lookup_uid(struct mailbox_list_index *ilist, uint32_t uid);
 void mailbox_list_index_node_get_path(const struct mailbox_list_index_node *node,
 				      char sep, string_t *str);
+void mailbox_list_index_node_unlink(struct mailbox_list_index *ilist,
+				    struct mailbox_list_index_node *node);
 
 bool mailbox_list_index_need_refresh(struct mailbox_list_index *ilist,
 				     struct mail_index_view *view);
@@ -144,9 +148,8 @@
 mailbox_list_index_node_find_sibling(struct mailbox_list_index_node *node,
 				     const char *name);
 void mailbox_list_index_reset(struct mailbox_list_index *ilist);
-int mailbox_list_index_parse(struct mailbox_list_index *ilist,
+int mailbox_list_index_parse(struct mailbox_list *list,
 			     struct mail_index_view *view, bool force);
-int mailbox_list_index_sync(struct mailbox_list *list);
 
 struct mailbox_list_iterate_context *
 mailbox_list_index_iter_init(struct mailbox_list *list,
@@ -174,7 +177,8 @@
 				    void (*callback)(void *context),
 				    void *context);
 
-void mailbox_list_index_status_init(void);
+void mailbox_list_index_status_init_mailbox(struct mailbox *box);
+void mailbox_list_index_backend_init_mailbox(struct mailbox *box);
 void mailbox_list_index_status_init_list(struct mailbox_list *list);
 
 #endif

--- a/src/lib-storage/list/mailbox-list-maildir.c	Fri Sep 28 00:03:12 2012 +0300
+++ b/src/lib-storage/list/mailbox-list-maildir.c	Fri Sep 28 00:11:19 2012 +0300
@@ -228,10 +228,17 @@
 static int
 maildir_list_delete_mailbox(struct mailbox_list *list, const char *name)
 {
+	const char *path;
 	int ret;
 
 	if ((list->flags & MAILBOX_LIST_FLAG_MAILBOX_FILES) != 0) {
-		ret = mailbox_list_delete_mailbox_file(list, name);
+		ret = mailbox_list_get_path(list, name,
+					    MAILBOX_LIST_PATH_TYPE_MAILBOX,
+					    &path);
+		if (ret < 0)
+			return -1;
+		i_assert(ret > 0);
+		ret = mailbox_list_delete_mailbox_file(list, name, path);
 	} else {
 		ret = maildir_list_delete_maildir(list, name);
 	}