1 /* Copyright (c) 2004-2018 Dovecot authors, see the included COPYING file */
2
3 #include "lib.h"
4 #include "ioloop.h"
5 #include "array.h"
6 #include "mail-index-private.h"
7 #include "mail-transaction-log-private.h"
8
9 static void mail_index_fsck_error(struct mail_index *index,
10 const char *fmt, ...) ATTR_FORMAT(2, 3);
mail_index_fsck_error(struct mail_index * index,const char * fmt,...)11 static void mail_index_fsck_error(struct mail_index *index,
12 const char *fmt, ...)
13 {
14 va_list va;
15
16 va_start(va, fmt);
17 mail_index_set_error(index, "Fixed index file %s: %s",
18 index->filepath, t_strdup_vprintf(fmt, va));
19 va_end(va);
20 }
21
22 #define CHECK(field, oper) \
23 if (hdr->field oper map->hdr.field) { \
24 mail_index_fsck_error(index, #field" %u -> %u", \
25 map->hdr.field, hdr->field); \
26 }
27
28 static void
mail_index_fsck_log_pos(struct mail_index * index,struct mail_index_map * map,struct mail_index_header * hdr)29 mail_index_fsck_log_pos(struct mail_index *index, struct mail_index_map *map,
30 struct mail_index_header *hdr)
31 {
32 unsigned int hdr_size = index->log->head->hdr.hdr_size;
33 uint32_t file_seq;
34 uoff_t file_offset;
35
36 mail_transaction_log_get_head(index->log, &file_seq, &file_offset);
37 if (hdr->log_file_seq < file_seq) {
38 /* index's log_file_seq is too old. move it to log head. */
39 hdr->log_file_head_offset = hdr->log_file_tail_offset =
40 sizeof(struct mail_transaction_log_header);
41 } else if (hdr->log_file_seq == file_seq) {
42 /* index's log_file_seq matches the current log. make sure the
43 offsets are valid. */
44 if (hdr->log_file_head_offset > file_offset)
45 hdr->log_file_head_offset = file_offset;
46 else if (hdr->log_file_head_offset < hdr_size)
47 hdr->log_file_head_offset = hdr_size;
48
49 if (hdr->log_file_tail_offset > hdr->log_file_head_offset)
50 hdr->log_file_tail_offset = hdr->log_file_head_offset;
51 else if (hdr->log_file_tail_offset != 0 &&
52 hdr->log_file_tail_offset < hdr_size)
53 hdr->log_file_tail_offset = hdr_size;
54 } else {
55 /* index's log_file_seq is newer than exists. move it to
56 end of the current log head. */
57 hdr->log_file_head_offset = hdr->log_file_tail_offset =
58 file_offset;
59 }
60 hdr->log_file_seq = file_seq;
61
62 CHECK(log_file_seq, !=);
63 if (hdr->log_file_seq == map->hdr.log_file_seq) {
64 /* don't bother complaining about these if file changed too */
65 CHECK(log_file_head_offset, !=);
66 CHECK(log_file_tail_offset, !=);
67 }
68 }
69
70 static void
mail_index_fsck_header(struct mail_index * index,struct mail_index_map * map,struct mail_index_header * hdr)71 mail_index_fsck_header(struct mail_index *index, struct mail_index_map *map,
72 struct mail_index_header *hdr)
73 {
74 /* mail_index_map_check_header() has already checked that the index
75 isn't completely broken. */
76 if (hdr->uid_validity == 0 && hdr->next_uid != 1)
77 hdr->uid_validity = ioloop_time;
78
79 if (index->log->head != NULL)
80 mail_index_fsck_log_pos(index, map, hdr);
81 }
82
83 static bool
array_has_name(const ARRAY_TYPE (const_string)* names,const char * name)84 array_has_name(const ARRAY_TYPE(const_string) *names, const char *name)
85 {
86 const char *arr_name;
87
88 array_foreach_elem(names, arr_name) {
89 if (strcmp(arr_name, name) == 0)
90 return TRUE;
91 }
92 return FALSE;
93 }
94
95 static unsigned int
mail_index_fsck_find_keyword_count(struct mail_index_map * map,const struct mail_index_ext_header * ext_hdr)96 mail_index_fsck_find_keyword_count(struct mail_index_map *map,
97 const struct mail_index_ext_header *ext_hdr)
98 {
99 const struct mail_index_record *rec;
100 const uint8_t *kw;
101 unsigned int r, i, j, cur, max = 0, kw_pos, kw_size;
102
103 kw_pos = ext_hdr->record_offset;
104 kw_size = ext_hdr->record_size;
105
106 rec = map->rec_map->records;
107 for (r = 0; r < map->rec_map->records_count; r++) {
108 kw = CONST_PTR_OFFSET(rec, kw_pos);
109 for (i = cur = 0; i < kw_size; i++) {
110 if (kw[i] != 0) {
111 for (j = 0; j < 8; j++) {
112 if ((kw[i] & (1 << j)) != 0)
113 cur = i * 8 + j + 1;
114 }
115 }
116 }
117 if (cur > max) {
118 max = cur;
119 if (max == kw_size*8)
120 return max;
121 }
122 rec = CONST_PTR_OFFSET(rec, map->hdr.record_size);
123 }
124 return max;
125 }
126
127 static bool
keyword_name_is_valid(const char * buffer,unsigned int pos,unsigned int size)128 keyword_name_is_valid(const char *buffer, unsigned int pos, unsigned int size)
129 {
130 for (; pos < size; pos++) {
131 if (buffer[pos] == '\0')
132 return TRUE;
133 if (((unsigned char)buffer[pos] & 0x7f) < 32) {
134 /* control characters aren't valid */
135 return FALSE;
136 }
137 }
138 return FALSE;
139 }
140
141 static void
mail_index_fsck_keywords(struct mail_index * index,struct mail_index_map * map,struct mail_index_header * hdr,const struct mail_index_ext_header * ext_hdr,unsigned int ext_offset,unsigned int * offset_p)142 mail_index_fsck_keywords(struct mail_index *index, struct mail_index_map *map,
143 struct mail_index_header *hdr,
144 const struct mail_index_ext_header *ext_hdr,
145 unsigned int ext_offset, unsigned int *offset_p)
146 {
147 const struct mail_index_keyword_header *kw_hdr;
148 struct mail_index_keyword_header *new_kw_hdr;
149 const struct mail_index_keyword_header_rec *kw_rec;
150 struct mail_index_keyword_header_rec new_kw_rec;
151 const char *name, *name_buffer, **name_array;
152 unsigned int i, j, name_pos, name_size, rec_pos, hdr_offset, diff;
153 unsigned int changed_count, keywords_count, name_base_pos;
154 ARRAY_TYPE(const_string) names;
155 buffer_t *dest;
156 bool changed = FALSE;
157
158 hdr_offset = ext_offset +
159 mail_index_map_ext_hdr_offset(sizeof(MAIL_INDEX_EXT_KEYWORDS)-1);
160 kw_hdr = MAIL_INDEX_MAP_HDR_OFFSET(map, hdr_offset);
161 keywords_count = kw_hdr->keywords_count;
162
163 kw_rec = (const void *)(kw_hdr + 1);
164 name_buffer = (const char *)(kw_rec + keywords_count);
165
166 name_pos = (size_t)(name_buffer - (const char *)kw_hdr);
167 if (name_pos > ext_hdr->hdr_size) {
168 /* the header is completely broken */
169 keywords_count =
170 mail_index_fsck_find_keyword_count(map, ext_hdr);
171 mail_index_fsck_error(index, "Assuming keywords_count = %u",
172 keywords_count);
173 kw_rec = NULL;
174 name_size = 0;
175 changed = TRUE;
176 } else {
177 name_size = ext_hdr->hdr_size - name_pos;
178 }
179
180 /* create keyword name array. invalid keywords are added as
181 empty strings */
182 t_array_init(&names, keywords_count);
183 for (i = 0; i < keywords_count; i++) {
184 if (name_size == 0 ||
185 !keyword_name_is_valid(name_buffer, kw_rec[i].name_offset,
186 name_size))
187 name = "";
188 else
189 name = name_buffer + kw_rec[i].name_offset;
190
191 if (*name != '\0' && array_has_name(&names, name)) {
192 /* duplicate */
193 name = "";
194 }
195 array_push_back(&names, &name);
196 }
197
198 /* give new names to invalid keywords */
199 changed_count = 0;
200 name_array = array_front_modifiable(&names);
201 for (i = j = 0; i < keywords_count; i++) {
202 while (name_array[i][0] == '\0') {
203 name = t_strdup_printf("unknown-%d", j++);
204 if (!array_has_name(&names, name)) {
205 name_array[i] = name;
206 changed = TRUE;
207 changed_count++;
208 }
209 }
210 }
211
212 if (!changed) {
213 /* nothing was broken */
214 return;
215 }
216
217 mail_index_fsck_error(index, "Renamed %u keywords to unknown-*",
218 changed_count);
219
220 dest = buffer_create_dynamic(default_pool,
221 I_MAX(ext_hdr->hdr_size, 128));
222 new_kw_hdr = buffer_append_space_unsafe(dest, sizeof(*new_kw_hdr));
223 new_kw_hdr->keywords_count = keywords_count;
224
225 /* add keyword records so we can start appending names directly */
226 rec_pos = dest->used;
227 i_zero(&new_kw_rec);
228 (void)buffer_append_space_unsafe(dest, keywords_count * sizeof(*kw_rec));
229
230 /* write the actual records and names */
231 name_base_pos = dest->used;
232 for (i = 0; i < keywords_count; i++) {
233 new_kw_rec.name_offset = dest->used - name_base_pos;
234 buffer_write(dest, rec_pos, &new_kw_rec, sizeof(new_kw_rec));
235 rec_pos += sizeof(*kw_rec);
236
237 buffer_append(dest, name_array[i], strlen(name_array[i]) + 1);
238 }
239
240 /* keep the header size at least the same size as before */
241 if (dest->used < ext_hdr->hdr_size)
242 buffer_append_zero(dest, ext_hdr->hdr_size - dest->used);
243
244 if (dest->used > ext_hdr->hdr_size) {
245 /* need to resize the header */
246 struct mail_index_ext_header new_ext_hdr;
247
248 diff = dest->used - ext_hdr->hdr_size;
249 buffer_copy(map->hdr_copy_buf, hdr_offset + diff,
250 map->hdr_copy_buf, hdr_offset, SIZE_MAX);
251 hdr->header_size += diff;
252 *offset_p += diff;
253
254 new_ext_hdr = *ext_hdr;
255 new_ext_hdr.hdr_size += diff;
256 buffer_write(map->hdr_copy_buf, ext_offset,
257 &new_ext_hdr, sizeof(new_ext_hdr));
258 }
259
260 i_assert(hdr_offset + dest->used <= map->hdr_copy_buf->used);
261 buffer_write(map->hdr_copy_buf, hdr_offset, dest->data, dest->used);
262
263 /* keywords changed unexpectedly, so all views are broken now */
264 index->inconsistency_id++;
265
266 buffer_free(&dest);
267 }
268
269 static void
mail_index_fsck_extensions(struct mail_index * index,struct mail_index_map * map,struct mail_index_header * hdr)270 mail_index_fsck_extensions(struct mail_index *index, struct mail_index_map *map,
271 struct mail_index_header *hdr)
272 {
273 const struct mail_index_ext_header *ext_hdr;
274 ARRAY_TYPE(const_string) names;
275 const char *name, *error;
276 unsigned int offset, next_offset, i;
277
278 t_array_init(&names, 64);
279 offset = MAIL_INDEX_HEADER_SIZE_ALIGN(hdr->base_header_size);
280 for (i = 0; offset < hdr->header_size; i++) {
281 /* mail_index_map_ext_get_next() uses map->hdr, so make sure
282 it's up-to-date */
283 map->hdr = *hdr;
284
285 next_offset = offset;
286 if (mail_index_map_ext_get_next(map, &next_offset,
287 &ext_hdr, &name) < 0) {
288 /* the extension continued outside header, drop it */
289 mail_index_fsck_error(index,
290 "Dropped extension #%d (%s) "
291 "with invalid header size",
292 i, name);
293 hdr->header_size = offset;
294 buffer_set_used_size(map->hdr_copy_buf, hdr->header_size);
295 break;
296 }
297 if (mail_index_map_ext_hdr_check(hdr, ext_hdr, name,
298 &error) < 0) {
299 mail_index_fsck_error(index,
300 "Dropped broken extension #%d (%s)", i, name);
301 } else if (array_has_name(&names, name)) {
302 mail_index_fsck_error(index,
303 "Dropped duplicate extension %s", name);
304 } else {
305 /* name may change if header buffer is changed */
306 name = t_strdup(name);
307
308 if (strcmp(name, MAIL_INDEX_EXT_KEYWORDS) == 0) {
309 mail_index_fsck_keywords(index, map, hdr,
310 ext_hdr, offset,
311 &next_offset);
312 }
313 array_push_back(&names, &name);
314 offset = next_offset;
315 continue;
316 }
317
318 /* drop the field */
319 hdr->header_size -= next_offset - offset;
320 buffer_copy(map->hdr_copy_buf, offset,
321 map->hdr_copy_buf, next_offset, SIZE_MAX);
322 buffer_set_used_size(map->hdr_copy_buf, hdr->header_size);
323 }
324 }
325
326 static void
mail_index_fsck_records(struct mail_index * index,struct mail_index_map * map,struct mail_index_header * hdr)327 mail_index_fsck_records(struct mail_index *index, struct mail_index_map *map,
328 struct mail_index_header *hdr)
329 {
330 struct mail_index_record *rec, *next_rec;
331 uint32_t i, last_uid;
332 bool logged_unordered_uids = FALSE, logged_zero_uids = FALSE;
333 bool records_dropped = FALSE;
334
335 hdr->messages_count = 0;
336 hdr->seen_messages_count = 0;
337 hdr->deleted_messages_count = 0;
338
339 hdr->first_unseen_uid_lowwater = 0;
340 hdr->first_deleted_uid_lowwater = 0;
341
342 rec = map->rec_map->records; last_uid = 0;
343 for (i = 0; i < map->rec_map->records_count; ) {
344 next_rec = PTR_OFFSET(rec, hdr->record_size);
345 if (rec->uid <= last_uid) {
346 /* log an error once, and skip this record */
347 if (rec->uid == 0) {
348 if (!logged_zero_uids) {
349 mail_index_fsck_error(index,
350 "Record UIDs have zeroes");
351 logged_zero_uids = TRUE;
352 }
353 } else {
354 if (!logged_unordered_uids) {
355 mail_index_fsck_error(index,
356 "Record UIDs unordered");
357 logged_unordered_uids = TRUE;
358 }
359 }
360 /* not the fastest way when we're skipping lots of
361 records, but this should happen rarely so don't
362 bother optimizing. */
363 memmove(rec, next_rec, hdr->record_size *
364 (map->rec_map->records_count - i - 1));
365 map->rec_map->records_count--;
366 records_dropped = TRUE;
367 continue;
368 }
369
370 hdr->messages_count++;
371 if ((rec->flags & MAIL_SEEN) != 0)
372 hdr->seen_messages_count++;
373 if ((rec->flags & MAIL_DELETED) != 0)
374 hdr->deleted_messages_count++;
375
376 if ((rec->flags & MAIL_SEEN) == 0 &&
377 hdr->first_unseen_uid_lowwater == 0)
378 hdr->first_unseen_uid_lowwater = rec->uid;
379 if ((rec->flags & MAIL_DELETED) != 0 &&
380 hdr->first_deleted_uid_lowwater == 0)
381 hdr->first_deleted_uid_lowwater = rec->uid;
382
383 last_uid = rec->uid;
384 rec = next_rec;
385 i++;
386 }
387
388 if (records_dropped) {
389 /* all existing views are broken now */
390 index->inconsistency_id++;
391 }
392
393 if (hdr->next_uid <= last_uid) {
394 mail_index_fsck_error(index, "next_uid %u -> %u",
395 hdr->next_uid, last_uid+1);
396 hdr->next_uid = last_uid+1;
397 }
398
399 if (hdr->first_unseen_uid_lowwater == 0)
400 hdr->first_unseen_uid_lowwater = hdr->next_uid;
401 if (hdr->first_deleted_uid_lowwater == 0)
402 hdr->first_deleted_uid_lowwater = hdr->next_uid;
403 if (hdr->first_recent_uid > hdr->next_uid)
404 hdr->first_recent_uid = hdr->next_uid;
405 if (hdr->first_recent_uid == 0)
406 hdr->first_recent_uid = 1;
407
408 CHECK(uid_validity, !=);
409 CHECK(messages_count, !=);
410 CHECK(seen_messages_count, !=);
411 CHECK(deleted_messages_count, !=);
412
413 CHECK(first_unseen_uid_lowwater, <);
414 CHECK(first_deleted_uid_lowwater, <);
415 CHECK(first_recent_uid, !=);
416 }
417
418 static void
mail_index_fsck_map(struct mail_index * index,struct mail_index_map * map)419 mail_index_fsck_map(struct mail_index *index, struct mail_index_map *map)
420 {
421 struct mail_index_header hdr;
422
423 if (index->log->head != NULL) {
424 /* Remember the log head position. If we go back in the index's
425 head offset, ignore errors in the log up to this offset. */
426 mail_transaction_log_get_head(index->log,
427 &index->fsck_log_head_file_seq,
428 &index->fsck_log_head_file_offset);
429 }
430 hdr = map->hdr;
431
432 mail_index_fsck_header(index, map, &hdr);
433 mail_index_fsck_extensions(index, map, &hdr);
434 mail_index_fsck_records(index, map, &hdr);
435
436 hdr.flags |= MAIL_INDEX_HDR_FLAG_FSCKD;
437 map->hdr = hdr;
438 i_assert(map->hdr_copy_buf->used == map->hdr.header_size);
439 }
440
mail_index_fsck(struct mail_index * index)441 int mail_index_fsck(struct mail_index *index)
442 {
443 bool orig_locked = index->log_sync_locked;
444 struct mail_index_map *map;
445 uint32_t file_seq;
446 uoff_t file_offset;
447
448 i_warning("fscking index file %s", index->filepath);
449
450 index->fscked = TRUE;
451
452 if (index->log->head == NULL) {
453 /* we're trying to open the index files, but there wasn't
454 any .log file. */
455 if (mail_transaction_log_create(index->log, FALSE) < 0)
456 return -1;
457 }
458
459 if (!orig_locked) {
460 if (mail_transaction_log_sync_lock(index->log, "fscking",
461 &file_seq, &file_offset) < 0)
462 return -1;
463 }
464
465 map = mail_index_map_clone(index->map);
466 mail_index_unmap(&index->map);
467 index->map = map;
468
469 T_BEGIN {
470 mail_index_fsck_map(index, map);
471 } T_END;
472
473 mail_index_write(index, FALSE, "fscking");
474
475 if (!orig_locked)
476 mail_transaction_log_sync_unlock(index->log, "fscking");
477 return 0;
478 }
479
mail_index_fsck_locked(struct mail_index * index)480 void mail_index_fsck_locked(struct mail_index *index)
481 {
482 int ret;
483
484 i_assert(index->log_sync_locked);
485 ret = mail_index_fsck(index);
486 i_assert(ret == 0);
487 }
488
mail_index_reset_fscked(struct mail_index * index)489 bool mail_index_reset_fscked(struct mail_index *index)
490 {
491 bool ret = index->fscked;
492
493 index->fscked = FALSE;
494 return ret;
495 }
496