[dovecot-cvs] dovecot/doc design.txt,1.2,1.3 index.txt,1.1.1.1,1.2 multiaccess.txt,1.2,1.3
cras at procontrol.fi
cras at procontrol.fi
Tue Jan 14 03:45:23 EET 2003
Update of /home/cvs/dovecot/doc
In directory danu:/tmp/cvs-serv30945
Modified Files:
design.txt index.txt multiaccess.txt
Log Message:
updates
Index: design.txt
===================================================================
RCS file: /home/cvs/dovecot/doc/design.txt,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- design.txt 15 Oct 2002 00:47:53 -0000 1.2
+++ design.txt 14 Jan 2003 01:45:20 -0000 1.3
@@ -9,6 +9,7 @@
possible. Processes running as root are kept as simple as possible even if
it means minor performance hits.
+
imap-master
-----------
@@ -20,6 +21,7 @@
This is useful only if you wish to use imap somewhere you don't have root
access.
+
imap-login
----------
@@ -47,6 +49,7 @@
connections connecting to it, possibly hijacking them or stealing their
passwords if plaintext authentication was used.
+
imap-auth
---------
@@ -74,7 +77,7 @@
a) Receives authentication request with given protocol
- Initialize the request in protocol-specific manner
- If failed, send a failure-reply to client
- - Otherwise send a secret cookie (randomized data) to client
+ - Otherwise send a cookie to client
b) Receives continued authentication request for given cookie
- Verifies that the cookie is valid, replying if not
- Handle the data in protocol-specific manner
@@ -85,6 +88,10 @@
- Verifies that the cookie is valid, replying if not
- Reply with the data
+Cookies are associated to a specific imap-login process, so one process
+cannot steal another one's authentication request by pretending to be it.
+
+
imap
----
@@ -96,18 +103,20 @@
actual mail files aren't opened unless they're really needed. The index
files are accessed using shared memory maps and locked using fcntl().
-Using shared memory maps creates a security problem if the file isn't
-trusted. It might well be possible to create a buffer overflow in some
-function by modifying the file as while it's being used. Currently this
-should not be a problem as we require write access to the files ourself, so
-attacker shouldn't be able to get any extra privileges by exploiting the
-imap process. However, once support for shared readonly mailboxes are
-implemented, we need to switch into using private memory maps for them and
-to make sure that truncating files abruptly won't create any problems.
+Using memory maps creates a security problem if the file isn't trusted. It
+might well be possible to create a buffer overflow in some function by
+modifying the file as while it's being used. Currently this should not be a
+problem as we require write access to the files ourself, so attacker
+shouldn't be able to get any extra privileges by exploiting the imap
+process.
-Other than the shared memory mapping problem, the index files are not
-trusted to contain valid data. Everything in them validated before being
-used.
+Other than the memory mapping problem, index files are not trusted to
+contain valid data. Everything in them is validated before being used.
+
+Supporting shared mailboxes will be a small problem. We probably shouldn't
+even try to support using non-trusted index files but rather create trusted
+indexes separately for each user. If however the users don't have direct
+access to the indexes files, they could optionally be shared.
indexer
Index: index.txt
===================================================================
RCS file: /home/cvs/dovecot/doc/index.txt,v
retrieving revision 1.1.1.1
retrieving revision 1.2
diff -u -d -r1.1.1.1 -r1.2
--- index.txt 9 Aug 2002 09:16:18 -0000 1.1.1.1
+++ index.txt 14 Jan 2003 01:45:20 -0000 1.2
@@ -1,162 +1,122 @@
-imap index files
+IMAP Index Files
----------------
Designed to be NFS-safe and accessible from multiple computers, even with
different architecture. 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 type sizes.
+They're saved into index file's "compatibility" fields. No attempt is made
+to deal with incompatible index files, they're either overwritten or
+new files are created.
-Index file
-----------
-
-.imap.index: ID => data lookups
-
-header:
- unsigned char compat_data[4];
- /* 0 = flags,
- 1 = sizeof(unsigned int),
- 2 = sizeof(time_t),
- 3 = sizeof(off_t) */
-
- unsigned int version;
- unsigned int indexid;
-
- unsigned int flags;
- unsigned int cache_fields;
-
- off_t first_hole_position;
- off_t first_hole_records;
-
- unsigned int uid_validity;
- unsigned int first_uid;
- unsigned int next_uid;
-
- unsigned int messages_count;
- unsigned int last_nonrecent_uid;
- unsigned int first_unseen_seq;
+Index file names begin with ".imap.index" or ".imap.index-<hostname>". The
+first form is used by default, the second when first is found to be
+incompatible. If the second is also incompatible, it's simply overwritten.
+This should allow us to be NFS-safe in an environment with multiple
+different computer architectures.
- unsigned int reserved_for_future_usage[5];
+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.
-Version is always currently always 1, anything else will be considered
-invalid. The compat_data[] is just for making sure the index isn't tried to
-be accessed by incompatible computers. If they don't match, either another
-index is created or everything is aborted.
-All index files must begin with name ".imap.index", which is also the first
-file name tried. If it can't be used, all the files beginning with
-".imap.index" are checked. If compatible index isn't found,
-".imap.index-<hostname>" is created as the index.
+Main File
+---------
-File name of all the other files related to the index (data, hash, modify
-log) begin with the index's name and have ".data", ".hash" etc. appended to
-it. Also, all the files must have the same value in indexid field as the
-index or they'll be treated as being corrupted.
+.imap.index: Fixed size data
-first_hole_position and first_hole_size specify the first deleted block in
-this index file. This allows us to quickly do sequence => UID lookup even
-if some messages are already deleted. The deleted blocks should be
-compressed whenever there's time, to keep index lookups fast.
+This is the main index file. It's kept as small as possible so scanning
+through it is quite fast operation.
-cache_fields contains the bitmask of fields that should be indexed, it can
-be updated at any time, so some earlier messages may not have indexed
-everything that newer messages have. This field can be used to quickly
-check if it's even possible to find some field from index.
+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.
-data:
- unsigned int uid;
- unsigned int msg_flags; /* MailFlags | IndexMailFlags */
- time_t internal_date;
- time_t sent_date;
+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.
- off_t data_position;
- unsigned int data_size;
+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.
- unsigned int cached_fields;
- unsigned int headers_size;
+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.
-cached_fields is a bitmask of indexed fields in data file.
+Data File
+---------
-Index data file
----------------
+.imap.index.data: Variable length data
-.imap.index.data: variable length sized 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.
-header:
- unsigned int indexid
+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.
-data:
- unsigned int field; /* MailField */
- unsigned int full_field_size;
- char data[]; /* variable size */
- ...
+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..
-Fields are ordered by the field type, beginning with lowest. The fields are
-always \0 terminated which determines their real length, the
-full_field_size only marks how much space is entirely allocated for the
-field. This may differ from the real size if we've allocated some extra
-space for a field which may grow (eg. flags in maildir filename).
+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.
-Hash File
+Tree File
---------
-.imap.index.hash: UID => index lookups
-
-header:
- unsigned int indexid;
- unsigned int flags;
- unsigned int used_records;
-
-data:
- unsigned int uid;
- off_t position;
-
-File is treated as a hash map. The hash function is UID*2 % size, where
-size is (filesize - sizeof(header)) / sizeof(data). If the position is
-already taken, the value is placed into next available position. When
-looking up the hash, lookup can't be aborted until first free slot is
-found. Free slots are identified by having UID 0.
+.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..
-Locking
--------
-File locking is done using fcntl(), so currently there's no support for NFS
-servers that don't support it. File based locking would be possible, but I
-haven't bothered to do it at least yet.
-
-There's also directory lock which is done by creating a
-.dirlock.<hostname>.<pid> file and once linking it to .dirlock succeeds,
-the process owns the lock.
+Modify Log File
+---------------
-There's of course the problem that some process may die and leave the file
-locked. So, if the first lock try fails, the invalid locks are looked up
-and deleted. For locks in the same host, the pids are checked to be valid.
-For other hosts there's a timeout of 30 minutes. The locks shouldn't be
-hold more than a few seconds at maximum, so the 30 mins is probably a bit
-too much, but it's there only to be sure that small clock differences
-between hosts don't break things.
+.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.
-Modify log file
----------------
+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.
-.imap.index.access: mailbox access counter
+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.
-Everyone who are accessing the mailbox must mark themselves known, so when
-someone is updating the mailbox, it should append to log file the expunges
-and mail flag updates it did. Using the log file other imap processes can
-quickly notify clients about the changes.
+Message sequence handling is also a bit annoying with IMAP. Each client can
+have slightly different sequences, since clients cannot be immediately
+informed about expunged messages. 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.
-Besides using it to notify clients, it's also used to map client given
-message sequence numbers to real sequence numbers. They're different when
-client hasn't yet been notified of the latest expunges in the mailbox.
+Dovecot doesn't allocate such array, it simply looks up from the log file
+what the differences 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.
-The access counter is implemented using hard links - there's the one base
-.imap.index.access file that all processes link to
-.imap.index.access.<hostname>.<pid> files. Invalid links are checked and
-deleted the same way as directory locks above.
+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
@@ -164,7 +124,7 @@
(Maildir-specific)
-External changes are noticed when index file's timestamp is different than
+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.
@@ -178,3 +138,12 @@
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.
Index: multiaccess.txt
===================================================================
RCS file: /home/cvs/dovecot/doc/multiaccess.txt,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- multiaccess.txt 6 Sep 2002 19:27:32 -0000 1.2
+++ multiaccess.txt 14 Jan 2003 01:45:20 -0000 1.3
@@ -13,4 +13,6 @@
SEARCH ignores expunged messages.
-COPY fails if any of the given messages were expunged.
+COPY fails if any of the given messages were expunged. Messages copied
+until the failure is noticed are currently left to destination mailbox -
+this may change later.
More information about the dovecot-cvs
mailing list