# HG changeset patch
# User Timo Sirainen <tss@iki.fi>
# Date 1204419000 -7200
# Node ID 6f59434cf229a2fdc9a87a384b28a78365bfb91e
# Parent  fce616c5959795d3f99017be425eec3a72a2bba3
Optimized cache record loop tracking.

diff -r fce616c59597 -r 6f59434cf229 src/lib-index/mail-cache-lookup.c
--- a/src/lib-index/mail-cache-lookup.c	Sat Mar 01 00:15:34 2008 +0200
+++ b/src/lib-index/mail-cache-lookup.c	Sun Mar 02 02:50:00 2008 +0200
@@ -105,18 +105,29 @@
 	return 1;
 }
 
-bool mail_cache_track_loops(ARRAY_TYPE(uint32_t) *array, uint32_t offset)
+bool mail_cache_track_loops(struct mail_cache_loop_track *loop_track,
+			    uoff_t offset, uoff_t size)
 {
-	const uint32_t *offsets;
-	unsigned int i, count;
+	i_assert(offset != 0);
+	i_assert(size != 0);
 
-	offsets = array_get(array, &count);
-	for (i = 0; i < count; i++) {
-		if (offsets[i] == offset)
-			return TRUE;
+	/* looping happens only in rare error conditions, so it's enough if we
+	   just catch it eventually. we do this by checking if we've seen
+	   more record data than possible in the accessed file area. */
+	if (loop_track->size_sum == 0) {
+		/* first call */
+		loop_track->min_offset = offset;
+		loop_track->max_offset = offset + size;
+	} else {
+		if (loop_track->min_offset > offset)
+			loop_track->min_offset = offset;
+		if (loop_track->max_offset < offset + size)
+			loop_track->max_offset = offset + size;
 	}
-	array_append(array, &offset, 1);
-	return FALSE;
+
+	loop_track->size_sum += size;
+	return loop_track->size_sum >
+		(loop_track->max_offset - loop_track->min_offset);
 }
 
 void mail_cache_lookup_iter_init(struct mail_cache_view *view, uint32_t seq,
@@ -143,7 +154,7 @@
 	}
 	ctx->remap_counter = view->cache->remap_counter;
 
-	array_clear(&view->looping_offsets);
+	memset(&view->loop_track, 0, sizeof(view->loop_track));
 }
 
 static int
@@ -168,17 +179,18 @@
 
 		ctx->appends_checked = TRUE;
 		ctx->remap_counter = view->cache->remap_counter;
-		array_clear(&view->looping_offsets);
+		memset(&view->loop_track, 0, sizeof(view->loop_track));
 	}
 
 	/* look up the next record */
-	if (mail_cache_track_loops(&view->looping_offsets, ctx->offset)) {
+	if (mail_cache_get_record(view->cache, ctx->offset, &ctx->rec) < 0)
+		return -1;
+	if (mail_cache_track_loops(&view->loop_track, ctx->offset,
+				   ctx->rec->size)) {
 		mail_cache_set_corrupted(view->cache,
 					 "record list is circular");
 		return -1;
 	}
-	if (mail_cache_get_record(view->cache, ctx->offset, &ctx->rec) < 0)
-		return -1;
 	ctx->remap_counter = view->cache->remap_counter;
 
 	ctx->pos = sizeof(*ctx->rec);
diff -r fce616c59597 -r 6f59434cf229 src/lib-index/mail-cache-private.h
--- a/src/lib-index/mail-cache-private.h	Sat Mar 01 00:15:34 2008 +0200
+++ b/src/lib-index/mail-cache-private.h	Sun Mar 02 02:50:00 2008 +0200
@@ -175,6 +175,12 @@
 	unsigned int field_header_write_pending:1;
 };
 
+struct mail_cache_loop_track {
+	/* we're looping if size_sum > (max_offset-min_offset) */
+	uoff_t min_offset, max_offset;
+	uoff_t size_sum;
+};
+
 struct mail_cache_view {
 	struct mail_cache *cache;
 	struct mail_index_view *view, *trans_view;
@@ -182,8 +188,7 @@
 	struct mail_cache_transaction_ctx *transaction;
 	uint32_t trans_seq1, trans_seq2;
 
-	/* temporary array, just to avoid mallocs. */
-	ARRAY_TYPE(uint32_t) looping_offsets;
+	struct mail_cache_loop_track loop_track;
 
 	/* if cached_exists_buf[field] == cached_exists_value, it's cached.
 	   this allows us to avoid constantly clearing the whole buffer.
@@ -236,9 +241,11 @@
 			  const struct mail_cache_record **rec_r);
 uint32_t mail_cache_get_first_new_seq(struct mail_index_view *view);
 
-/* Returns TRUE if offset is already in given array. Otherwise return FALSE
-   and add the offset to the array. */
-bool mail_cache_track_loops(ARRAY_TYPE(uint32_t) *array, uint32_t offset);
+/* Returns TRUE if offset..size area has been tracked before.
+   Returns FALSE if the area may or may not have been tracked before,
+   but we don't know for sure yet. */
+bool mail_cache_track_loops(struct mail_cache_loop_track *loop_track,
+			    uoff_t offset, uoff_t size);
 
 /* Iterate through a message's cached fields. */
 void mail_cache_lookup_iter_init(struct mail_cache_view *view, uint32_t seq,
diff -r fce616c59597 -r 6f59434cf229 src/lib-index/mail-cache-transaction.c
--- a/src/lib-index/mail-cache-transaction.c	Sat Mar 01 00:15:34 2008 +0200
+++ b/src/lib-index/mail-cache-transaction.c	Sun Mar 02 02:50:00 2008 +0200
@@ -1072,7 +1072,8 @@
 static int mail_cache_delete_real(struct mail_cache *cache, uint32_t offset)
 {
 	const struct mail_cache_record *rec;
-	ARRAY_TYPE(uint32_t) looping_offsets;
+	struct mail_cache_loop_track loop_track;
+	int ret = 0;
 
 	i_assert(cache->locked);
 
@@ -1081,30 +1082,26 @@
 	   the data. also it's actually useful as some index views are still
 	   able to ask cached data from messages that have already been
 	   expunged. */
-	t_array_init(&looping_offsets, 8);
-	array_append(&looping_offsets, &offset, 1);
-	while (mail_cache_get_record(cache, offset, &rec) == 0) {
-		cache->hdr_copy.deleted_space += rec->size;
-		offset = rec->prev_offset;
-
-		if (offset == 0) {
-			/* successfully got to the end of the list */
-			return 0;
-		}
-
-		if (mail_cache_track_loops(&looping_offsets, offset)) {
+	memset(&loop_track, 0, sizeof(loop_track));
+	while (offset != 0 &&
+	       (ret = mail_cache_get_record(cache, offset, &rec)) == 0) {
+		if (mail_cache_track_loops(&loop_track, offset, rec->size)) {
 			mail_cache_set_corrupted(cache,
 						 "record list is circular");
 			return -1;
 		}
+
+		cache->hdr_copy.deleted_space += rec->size;
+		offset = rec->prev_offset;
 	}
-	return -1;
+	return ret;
 }
 
 int mail_cache_delete(struct mail_cache *cache, uint32_t offset)
 {
 	int ret;
 
+	i_assert(cache->locked);
 	T_BEGIN {
 		ret = mail_cache_delete_real(cache, offset);
 	} T_END;
diff -r fce616c59597 -r 6f59434cf229 src/lib-index/mail-cache.c
--- a/src/lib-index/mail-cache.c	Sat Mar 01 00:15:34 2008 +0200
+++ b/src/lib-index/mail-cache.c	Sun Mar 02 02:50:00 2008 +0200
@@ -656,7 +656,6 @@
 	view = i_new(struct mail_cache_view, 1);
 	view->cache = cache;
 	view->view = iview;
-	i_array_init(&view->looping_offsets, 32);
 	view->cached_exists_buf =
 		buffer_create_dynamic(default_pool,
 				      cache->file_fields_count + 10);
@@ -670,7 +669,6 @@
 	if (view->cache->field_header_write_pending)
                 (void)mail_cache_header_fields_update(view->cache);
 
-	array_free(&view->looping_offsets);
 	buffer_free(&view->cached_exists_buf);
 	i_free(view);
 }