Multi-threaded store SEGV fixes and debug improvements.

Fix race condition in the store. When storing an item, we
immediately put it into the hash (thus getting our existence
check). We then check and try to free enough space for it in
the budget. If we cannot free enough, we remove the item
from the hash. The race condition comes if someone else finds
it in the hash in the meantime.

To fix this, we update all 'finds' of things in the hash to
move it to the head of the LRU chain (regardless of whether it
was in the chain before or not). We only remove it from the
hash in the 'failed-to-fit-in-the-budget' case if it's not in the
chain already.

Also, we fix a bug in the "failed to fit" removal case where we
were failing to realise that the the pos pointer was not valid
any more.

In the course of tracking this bug down various debug functions
were improved. These are committed here too.

3 files changed, 81 insertions, 40 deletions

diff --git a/fitz/base_hash.c b/fitz/base_hash.c
index 037988cb..1da8cac9 100644
--- a/fitz/base_hash.c
+++ b/fitz/base_hash.c
@@ -311,11 +311,11 @@ fz_hash_remove_fast(fz_context *ctx, fz_hash_table *table, void *key, unsigned p
 {
 	fz_hash_entry *ents = table->ents;
 
-	if (memcmp(key, ents[pos].key, table->keylen) != 0)
+	if (ents[pos].val == NULL || memcmp(key, ents[pos].key, table->keylen) != 0)
 	{
-		/* The key didn't match! The table must have been rebuilt
-		 * (or the contents moved) in the meantime. Do the removal
-		 * the slow way. */
+		/* The value isn't there, or the key didn't match! The table
+		 * must have been rebuilt (or the contents moved) in the
+		 * meantime. Do the removal the slow way. */
 		fz_hash_remove(ctx, table, key);
 	}
 	else
@@ -326,6 +326,12 @@ fz_hash_remove_fast(fz_context *ctx, fz_hash_table *table, void *key, unsigned p
 void
 fz_print_hash(fz_context *ctx, FILE *out, fz_hash_table *table)
 {
+	fz_print_hash_details(ctx, out, table, NULL);
+}
+
+void
+fz_print_hash_details(fz_context *ctx, FILE *out, fz_hash_table *table, void (*details)(FILE *,void*))
+{
 	int i, k;
 
 	fprintf(out, "cache load %d / %d\n", table->load, table->size);
@@ -339,7 +345,10 @@ fz_print_hash(fz_context *ctx, FILE *out, fz_hash_table *table)
 			fprintf(out, "table % 4d: key=", i);
 			for (k = 0; k < MAX_KEY_LEN; k++)
 				fprintf(out, "%02x", ((char*)table->ents[i].key)[k]);
-			fprintf(out, " val=$%p\n", table->ents[i].val);
+			if (details)
+				details(out, table->ents[i].val);
+			else
+				fprintf(out, " val=$%p\n", table->ents[i].val);
 		}
 	}
 }
diff --git a/fitz/fitz-internal.h b/fitz/fitz-internal.h
index 7193301a..bf7d2873 100644
--- a/fitz/fitz-internal.h
+++ b/fitz/fitz-internal.h
@@ -271,6 +271,7 @@ void *fz_hash_get_val(fz_context *ctx, fz_hash_table *table, int idx);
 
 #ifndef NDEBUG
 void fz_print_hash(fz_context *ctx, FILE *out, fz_hash_table *table);
+void fz_print_hash_details(fz_context *ctx, FILE *out, fz_hash_table *table, void (*details)(FILE *, void *));
 #endif
 
 /*
@@ -587,6 +588,7 @@ int fz_store_scavenge(fz_context *ctx, unsigned int size, int *phase);
 */
 #ifndef NDEBUG
 void fz_print_store(fz_context *ctx, FILE *out);
+void fz_print_store_locked(fz_context *ctx, FILE *out);
 #endif
 
 struct fz_buffer_s
diff --git a/fitz/res_store.c b/fitz/res_store.c
index 93a7c6e3..bfe7eedb 100644
--- a/fitz/res_store.c
+++ b/fitz/res_store.c
@@ -188,6 +188,31 @@ ensure_space(fz_context *ctx, unsigned int tofree)
 	return count;
 }
 
+static void
+touch(fz_store *store, fz_item *item)
+{
+	if (item->next != item)
+	{
+		/* Already in the list - unlink it */
+		if (item->next)
+			item->next->prev = item->prev;
+		else
+			store->tail = item->prev;
+		if (item->prev)
+			item->prev->next = item->next;
+		else
+			store->head = item->next;
+	}
+	/* Now relink it at the start of the LRU chain */
+	item->next = store->head;
+	if (item->next)
+		item->next->prev = item;
+	else
+		store->tail = item;
+	store->head = item;
+	item->prev = NULL;
+}
+
 void *
 fz_store_item(fz_context *ctx, void *key, void *val_, unsigned int itemsize, fz_store_type *type)
 {
@@ -256,6 +281,8 @@ fz_store_item(fz_context *ctx, void *key, void *val_, unsigned int itemsize, fz_
 		}
 		fz_catch(ctx)
 		{
+			/* Any error here means that item never made it into the
+			 * hash - so no one else can have a reference. */
 			fz_unlock(ctx, FZ_LOCK_ALLOC);
 			fz_free(ctx, item);
 			type->drop_key(ctx, key);
@@ -265,6 +292,7 @@ fz_store_item(fz_context *ctx, void *key, void *val_, unsigned int itemsize, fz_
 		{
 			/* There was one there already! Take a new reference
 			 * to the existing one, and drop our current one. */
+			touch(store, existing);
 			if (existing->val->refs > 0)
 				existing->val->refs++;
 			fz_unlock(ctx, FZ_LOCK_ALLOC);
@@ -286,8 +314,16 @@ fz_store_item(fz_context *ctx, void *key, void *val_, unsigned int itemsize, fz_
 			if (ensure_space(ctx, size - store->max) == 0)
 			{
 				/* Failed to free any space. */
+				/* If we are using the hash table, then we've already
+				 * inserted item - remove it. */
 				if (use_hash)
 				{
+					/* If someone else has already picked up a reference
+					 * to item, then we cannot remove it. Leave it in the
+					 * store, and we'll live with being over budget. We
+					 * know this is the case, if it's in the linked list. */
+					if (item->next != item)
+						break;
 					fz_hash_remove_fast(ctx, store->hash, &hash, pos);
 				}
 				fz_unlock(ctx, FZ_LOCK_ALLOC);
@@ -302,13 +338,7 @@ fz_store_item(fz_context *ctx, void *key, void *val_, unsigned int itemsize, fz_
 	store->size += itemsize;
 
 	/* Regardless of whether it's indexed, it goes into the linked list */
-	item->next = store->head;
-	if (item->next)
-		item->next->prev = item;
-	else
-		store->tail = item;
-	store->head = item;
-	item->prev = NULL;
+	touch(store, item);
 	fz_unlock(ctx, FZ_LOCK_ALLOC);
 
 	return NULL;
@@ -351,31 +381,11 @@ fz_find_item(fz_context *ctx, fz_store_free_fn *free, void *key, fz_store_type *
 	}
 	if (item)
 	{
-		/* Momentarily things can be in the hash table (and hence can
-		 * be found) without being in the list. Don't attempt to LRU
-		 * these. We indicate such items by setting
-		 * item->next == item. */
-		if (item->next != item)
-		{
-			/* LRU: Move the block to the front */
-			/* Unlink from present position */
-			if (item->next)
-				item->next->prev = item->prev;
-			else
-				store->tail = item->prev;
-			if (item->prev)
-				item->prev->next = item->next;
-			else
-				store->head = item->next;
-			/* Insert at head */
-			item->next = store->head;
-			if (item->next)
-				item->next->prev = item;
-			else
-				store->tail = item;
-			item->prev = NULL;
-			store->head = item;
-		}
+		/* LRU the block. This also serves to ensure that any item
+		 * picked up from the hash before it has made it into the
+		 * linked list does not get whipped out again due to the
+		 * store being full. */
+		touch(store, item);
 		/* And bump the refcount before returning */
 		if (item->val->refs > 0)
 			item->val->refs++;
@@ -491,15 +501,23 @@ fz_drop_store_context(fz_context *ctx)
 }
 
 #ifndef NDEBUG
+static void
+print_item(FILE *out, void *item_)
+{
+	fz_item *item = (fz_item *)item_;
+	fprintf(out, " val=%p item=%p\n", item->val, item);
+	fflush(out);
+}
+
 void
-fz_print_store(fz_context *ctx, FILE *out)
+fz_print_store_locked(fz_context *ctx, FILE *out)
 {
 	fz_item *item, *next;
 	fz_store *store = ctx->store;
 
 	fprintf(out, "-- resource store contents --\n");
+	fflush(out);
 
-	fz_lock(ctx, FZ_LOCK_ALLOC);
 	for (item = store->head; item; item = next)
 	{
 		next = item->next;
@@ -509,10 +527,22 @@ fz_print_store(fz_context *ctx, FILE *out)
 		fz_unlock(ctx, FZ_LOCK_ALLOC);
 		item->type->debug(out, item->key);
 		fprintf(out, " = %p\n", item->val);
+		fflush(out);
 		fz_lock(ctx, FZ_LOCK_ALLOC);
 		if (next)
 			next->val->refs--;
 	}
+	fprintf(out, "-- resource store hash contents --\n");
+	fz_print_hash_details(ctx, out, store->hash, print_item);
+	fprintf(out, "-- end --\n");
+	fflush(out);
+}
+
+void
+fz_print_store(fz_context *ctx, FILE *out)
+{
+	fz_lock(ctx, FZ_LOCK_ALLOC);
+	fz_print_store_locked(ctx, out);
 	fz_unlock(ctx, FZ_LOCK_ALLOC);
 }
 #endif
@@ -561,7 +591,7 @@ int fz_store_scavenge(fz_context *ctx, unsigned int size, int *phase)
 
 #ifdef DEBUG_SCAVENGING
 	printf("Scavenging: store=%d size=%d phase=%d\n", store->size, size, *phase);
-	fz_print_store(ctx, stderr);
+	fz_print_store_locked(ctx, stderr);
 	Memento_stats();
 #endif
 	do