IMAP Index Files
----------------

Should support pretty much any mail format, at least maildir and mbox can
be implemented with it.

The data in the files are stored using native byte order and native type
sizes. That information is saved into index file's "compatibility" fields.
No attempt is made to deal with incompatible index files, they're just
overwritten.

Indexes are bound to each others by "indexid" field in headers. If they
don't match, the file is assumed to be corrupted and will be rebuilt.


Main File
---------

.imap.index: Fixed size data

This is the main index file. It's kept as small as possible so scanning
through it is quite fast operation.

Index is usually accessed by getting pointer to first record in wanted
range, after that it's just accessed by jumping forward. There may be
deleted records (UID field 0) which are skipped.

first_hole_position and first_hole_size fields in header specify the first
deleted block in the index file. If we wish to access a message with a
sequence number before the deleted block, we can do it with a simple array
lookup.

The deleted blocks are compressed when INDEX_COMPRESS_PERCENTAGE of the
file consists of deleted space, 50% by default. Also the indexer process
should try to compress the files when there's extra time, to keep the
sequence lookups faster.

cache_fields field in header contains the bitmask of fields that should be
saved into index when indexing new messages. It may change at any time, and
the old messages won't (immediately) be updated to reflect the change.


Data File
---------

.imap.index.data: Variable length data

Contains the non-critical fields for messages. Each message has a fixed
size "data header" and zero or more variable width fields. It's possible to
add, remove and modify fields, but if doing so would exceed the allocated
space, the whole data block is copied to the end of file.

Only the total amount of deleted space is remembered, ie. empty blocks in
the middle of file aren't reused. The deleted blocks are compressed when
COMPRESS_PERCENTAGE of the file consists of deleted space, 20% by default.

This file is actually a very dummy database, and will likely later be
replaced with something smarter (Berkeley DB?). Currently it should be good
enough since there's not much need to insert or update fields, but ANNOTATE
extensions will something better. Although ANNOTATE would require permanent
storage, which index really isn't..

One nice TODO idea would be simple compression. Mailboxes contain a lot of
identical mail addresses and subjects, we could simply save one instance of
them.


Tree File
---------

.imap.index.tree: UID and sequence lookups

This is a red-black binary in tree file, used to find message record
positions in main index file. TODO: I should rather have used B+tree or
similiar..


Modify Log File
---------------

.imap.index.log: External change log

Communication between two IMAP servers accessing the same mailbox is
usually non-existent. If a change occurs, they both have to go through the
mailbox to see what changed and notify client about it.

Dovecot uses modify log file to log changes made to index files; currently
message flag changes and expunges. This way only one of the Dovecot
processes has to scan the mailbox, other processes simply check from the
log file what changes occured.

All external changes that Dovecot notices (eg. another MUA expunging mails)
are also saved into log file. They can quickly be found from there when
client is ready to be notified of them.

Message sequence handling is also a bit annoying with IMAP. Since clients
cannot be immediately informed about expunged messages, each client can
have slightly different sequences. The easiest way to deal with this is to
simply allocate an seq_array[] for each client which contains pointers to
messages or message UIDs. This is probably how all other IMAP servers
implement it.

Dovecot doesn't allocate such array, it simply looks up from the log file
what the differences there are between index sequences and client
sequences. It's almost always none. This was a bit tricky to implement, but
it seems to be working fine now.

If there's only one Dovecot accessing the mailbox, there's no need to write
to log file. To find out if this is the case, we use fcntl() locking
tricks. Each Dovecot process locks the modify log in shared mode, checking
if we're the only one is then as simple as trying to lock it exclusively.
It's safe because only the main index file is used for real locking.


External changes
----------------

(Maildir-specific)

External changes are checked when index file's timestamp is different than
the maildir's timestamp. When modifying the index file, it's timestamp
should be set to maildir directory's timestamp when it was last in a known
synced state.

There's still the possibility that new mail comes just after we've synced
the dir (or in the middle of it), but that's a bit difficult to fix without
scanning the directory through all the time which gets slow.

Luckily however this shouldn't be much of a problem, as new mail comes to
new/ directory where it's always noticed. It's only the cur/ directory that
may not always be exactly synced if someone else has been messing up with
it. And if someone else has done that, she most likely has also seen the
mail using that other mail client.


Locking
-------

File locking is done using fcntl(), so currently there's no support for NFS
servers that don't support it. There probably isn't even need to, indexes
could just be saved into local disk even if mailboxes are accessed through
NFS.