1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
|
Main index
==========
The main index can be used to quickly look up messages' UIDs, flags, keywords
and extension-specific data, such as cache file or mbox file offsets.
Reading, writing and locking
----------------------------
Reading 'dovecot.index' file requires locking, unfortunately. Shared read
locking is done using the standard index locking method specified in
'lock_method' setting ('lock_method' parameter for 'mail_index_open()').
Writing to index files requires transaction log to be exclusively locked first.
This way the index locking only has to worry about existing read locks. The
locking works by first trying to lock the index with the standard locking
method, but if it couldn't acquire the lock in two seconds, it'll fallback to
copying the index file to a temporary file, and when unlocking it'll 'rename()'
the temporary file over the 'dovecot.index' file. Note that this is safe only
because of the exclusive transaction log lock. This way the writers are never
blocked by readers who are allowed to keep the shared lock as long as they
want.
The copy-locking is used always when doing anything that could corrupt the
index file if it crashed in the middle of an operation. For example if the
header or record size changes, or if messages are expunged. New messages can be
appended however, because the message count in the header is updated last.
Expunging the last messages would probably be safe also (because only the
header needs updating), but it's not done currently.
The index file should never be directly modified. Everything should go through
the transaction log, and the only time the index needs to be write-locked is
when transactions are written to it.
Currently the index file is updated whenever the backend mailbox is
synchronized. This isn't necessary, because an old index file can be updated
using the transaction log. In future there could be some smarter decisions
about when writing to the index isn't worth the extra disk writes.
Header
------
---%<-------------------------------------------------------------------------
struct mail_index_header {
uint8_t major_version;
uint8_t minor_version;
uint16_t base_header_size;
uint32_t header_size;
uint32_t record_size;
uint8_t compat_flags;
uint8_t unused[3];
uint32_t indexid;
uint32_t flags;
uint32_t uid_validity;
uint32_t next_uid;
uint32_t messages_count;
uint32_t unused_old_recent_messages_count;
uint32_t seen_messages_count;
uint32_t deleted_messages_count;
uint32_t first_recent_uid;
uint32_t first_unseen_uid_lowwater;
uint32_t first_deleted_uid_lowwater;
uint32_t log_file_seq;
uint32_t log_file_tail_offset;
uint32_t log_file_head_offset;
uint64_t unused_old_sync_size;
uint32_t unused_old_sync_stamp;
uint32_t day_stamp;
uint32_t day_first_uid[8];
}
---%<-------------------------------------------------------------------------
Fields that won't change without recreating the index:
major_version:
If this doesn't match 'MAIL_INDEX_MAJOR_VERSION', don't try to read the
index. Dovecot recreates the index file then.
minor_version:
If this doesn't match 'MAIL_INDEX_MINOR_VERSION' there are some backwards
compatible changes in the index file (typically header fields). Try to
preserve the headers and the minor version when updating the index file.
base_header_size:
Extension headers begin after the base headers. This is normally the same as
'sizeof(struct mail_index_header)'.
header_size:
Records begin after base and extension headers.
record_size:
Size of each record and its extensions. Initially the same as 'sizeof(struct
mail_index_record)'.
compat_flags:
Currently there is just one compatibility flag:
'MAIL_INDEX_COMPAT_LITTLE_ENDIAN'. Dovecot doesn't try to bother to read
different endianess files, they're simply recreated.
indexid:
Unique index file ID. This is used to make sure that the main index,
transaction log and cache file are all part of the same index.
Header flags:
MAIL_INDEX_HDR_FLAG_CORRUPTED:
Set whenever the index file is found to be corrupted. If the reader notices
this flag, it shouldn't try to continue using the index.
MAIL_INDEX_HDR_FLAG_HAVE_DIRTY:
This index has records with 'MAIL_INDEX_MAIL_FLAG_DIRTY' flag set.
MAIL_INDEX_HDR_FLAG_FSCK:
Call 'mail_index_fsck()' as soon as possible. This flag isn't actually set
anywhere currently.
Message UIDs and counters:
uid_validity:
IMAP UIDVALIDITY field. Initially can be 0, but after it's set we don't
currently try to even handle the case of UIDVALIDITY changing. It's done by
marking the index file corrupted and recreating it. That's a bit ugly, but
typically the UIDVALIDITY never changes.
next_uid:
UID given to the next appended message. Only increases.
messages_count:
Number of records in the index file.
recent_messages_count:
Number of records with 'MAIL_RECENT' flag set.
seen_messages_count:
Number of records with 'MAIL_SEEN' flag set.
deleted_messages_count:
Number of records with 'MAIL_DELETED' flag set.
first_recent_uid_lowwater:
There are no UIDs lower than this with 'MAIL_RECENT' flag set.
first_unseen_uid_lowwater:
There are no UIDs lower than this *without* 'MAIL_SEEN' flag set.
first_deleted_uid_lowwater:
There are no UIDs lower than this with 'MAIL_DELETE' flag set.
The lowwater fields are used to optimize searching messages with/without a
specific flag.
Fields related to syncing:
log_file_seq:
Log file the log_*_offset fields point to.
log_file_int_offset, log_file_ext_offset:
All the internal/external transactions before this offset in the log file are
synced to the index. External transactions are synced more often than
internal, so 'log_file_int_offset' <= 'log_file_ext_offset'.
sync_size, sync_stamp:
Used by the mailbox backends to store their synchronization information. Some
day these should be removed and replaced with extension headers.
Then there are day fields:
day_stamp:
UNIX timestamp to the beginning of the day when new records were last added
to the index file.
day_first_uid[8]:
These fields are updated when 'day_stamp' < today. The [0..6] are first moved
to [1..7], then [0] is set to the first appended UID. So they contain the
first UID of the day for last 8 days when messages were appended.
The 'day_first_uid[]' fields are used by cache file compression to decide when
to drop 'MAIL_CACHE_DECISION_TEMP' data.
Extension headers
-----------------
After the base header comes a list of extensions and their headers. The first
extension begins from 'mail_index_header.base_header_size' offset. The second
begins after the first one's 'data[]' and so on. The extensions always begin
64bit aligned however, so you may need to skip a few bytes always. Read the
extensions as long as the offset is smaller than
'mail_index_header.header_size'.
---%<-------------------------------------------------------------------------
struct mail_index_ext_header {
uint32_t hdr_size; /* size of data[] */
uint32_t reset_id;
uint16_t record_offset;
uint16_t record_size;
uint16_t record_align;
uint16_t name_size;
/* unsigned char name[name_size] */
/* unsigned char data[hdr_size] (starting 64bit aligned) */
};
---%<-------------------------------------------------------------------------
'reset_id', record offset, size and alignment is explained in
<Design.Indexes.TransactionLog.txt>'s 'struct mail_transaction_ext_intro'.
Records
-------
There are 'hdr.messages_count' records in the file. Each record contains at
least two fields: Record UID and flags. The UID is always increasing for the
records, so it's possible to find a record by its UID with binary search. The
record size is specified by 'mail_index_header.record_size'.
The flags are a combination of 'enum mail_flags' and 'enum
mail_index_mail_flags'. There exists only one index flag currently:
'MAIL_INDEX_MAIL_FLAG_DIRTY'. If a record has this flag set, it means that the
mailbox syncing code should ignore the flag in the mailbox and use the flag in
the index file instead. This is used for example with mbox and
'mbox_lazy_writes=yes'. It also allows having modifiable flags for read-only
mailboxes.
The rest data is stored in record extensions.
Keywords
--------
The keywords are stored in record extensions, but for better performance and
lower disk space usage in transaction logs, they are quite tightly integrated
to the index file code.
The list of keywords is stored in "keywords" extension header:
---%<-------------------------------------------------------------------------
struct mail_index_keyword_header {
uint32_t keywords_count;
/* struct mail_index_keyword_header_rec[] */
/* char name[][] */
};
struct mail_index_keyword_header_rec {
uint32_t unused; /* for backwards compatibility */
uint32_t name_offset; /* relative to beginning of name[] */
};
---%<-------------------------------------------------------------------------
The unused field originally contained 'count' field, but while writing this
documentation I noticed it's not actually used anywhere. Apparently it was
added there accidentally. It'll be removed in later versions.
So there exists 'keywords_count' keywords, each listed in a NUL-terminated
string beginning from 'name_offset'.
Since crashing in the middle of updating the keywords list pretty much breaks
the keywords, adding new keywords causes the index file to be always copied to
a temporary file and be replaced.
The keywords in the records are stored in a "keywords" extension bitfield. So
the nth bit in the bitfield points to the nth keyword listed in the header.
It's not currently possible to safely remove existing keywords.
Extensions
----------
The extensions only specify their wanted size and alignment, the index file
syncing code is free to assign any offset inside the record to them. The
extensions may be reordered at any time.
Dovecot's current extension ordering code works pretty well, but it's not
perfect. If the extension size isn't the same as its alignment, it may create
larger records than necessary. This will be fixed later.
The records size is always divisible by the maximum alignment requirement. This
isn't strictly necessary either, so it could be fixed later as well.
(This file was created from the wiki on 2019-06-19 12:42)
|
