Add scavenging functionality.

When fz_malloc (etc) are about to fail, we try to scavenge memory
from the store and then retry. We repeatedly try to bin objects
from the store until the malloc succeeds, or until we have nothing
else to bin.

This means we no longer need the 'aging' of the store, so this is
removed.

6 files changed, 139 insertions, 26 deletions

diff --git a/apps/pdfapp.c b/apps/pdfapp.c
index c1e026fe..849b0d18 100644
--- a/apps/pdfapp.c
+++ b/apps/pdfapp.c
@@ -342,8 +342,6 @@ static void pdfapp_loadpage_pdf(pdfapp_t *app)
 	fz_free_device(mdev);
 
 	pdf_free_page(app->ctx, page);
-
-	fz_age_store(app->ctx, 3);
 }
 
 static void pdfapp_loadpage_xps(pdfapp_t *app)
diff --git a/apps/pdfdraw.c b/apps/pdfdraw.c
index f7867bf0..1e71181e 100644
--- a/apps/pdfdraw.c
+++ b/apps/pdfdraw.c
@@ -263,8 +263,6 @@ static void drawpage(pdf_xref *xref, int pagenum)
 	if (showmd5 || showtime)
 		printf("\n");
 
-	fz_age_store(ctx, 3);
-
 	fz_flush_warnings(ctx);
 }
 
diff --git a/fitz/base_memory.c b/fitz/base_memory.c
index 79ae38b0..17a701e2 100644
--- a/fitz/base_memory.c
+++ b/fitz/base_memory.c
@@ -1,9 +1,48 @@
 #include "fitz.h"
 
+static void *
+do_scavenging_malloc(fz_context *ctx, unsigned int size)
+{
+	void *p;
+	int phase = 0;
+
+	/* LOCK */
+	do {
+		p = ctx->alloc->malloc(ctx->alloc->user, size);
+		if (p != NULL)
+			return p;
+	} while (fz_store_scavenge(ctx, size, &phase));
+	/* UNLOCK */
+
+	return NULL;
+}
+
+static void *
+do_scavenging_realloc(fz_context *ctx, void *p, unsigned int size)
+{
+	void *q;
+	int phase = 0;
+
+	/* LOCK */
+	do {
+		q = ctx->alloc->realloc(ctx->alloc->user, p, size);
+		if (q != NULL)
+			return q;
+	} while (fz_store_scavenge(ctx, size, &phase));
+	/* UNLOCK */
+
+	return NULL;
+}
+
 void *
 fz_malloc(fz_context *ctx, unsigned int size)
 {
-	void *p = ctx->alloc->malloc(ctx->alloc->user, size);
+	void *p;
+
+	if (size == 0)
+		return NULL;
+
+	p = do_scavenging_malloc(ctx, size);
 	if (!p)
 		fz_throw(ctx, "malloc of %d bytes failed", size);
 	return p;
@@ -12,7 +51,7 @@ fz_malloc(fz_context *ctx, unsigned int size)
 void *
 fz_malloc_no_throw(fz_context *ctx, unsigned int size)
 {
-	return ctx->alloc->malloc(ctx->alloc->user, size);
+	return do_scavenging_malloc(ctx, size);
 }
 
 void *
@@ -26,7 +65,7 @@ fz_malloc_array(fz_context *ctx, unsigned int count, unsigned int size)
 	if (count > UINT_MAX / size)
 		fz_throw(ctx, "malloc of array (%d x %d bytes) failed (integer overflow)", count, size);
 
-	p = ctx->alloc->malloc(ctx->alloc->user, count * size);
+	p = do_scavenging_malloc(ctx, count * size);
 	if (!p)
 		fz_throw(ctx, "malloc of array (%d x %d bytes) failed", count, size);
 	return p;
@@ -44,7 +83,7 @@ fz_malloc_array_no_throw(fz_context *ctx, unsigned int count, unsigned int size)
 		return NULL;
 	}
 
-	return ctx->alloc->malloc(ctx->alloc->user, count * size);
+	return do_scavenging_malloc(ctx, count * size);
 }
 
 void *
@@ -60,7 +99,7 @@ fz_calloc(fz_context *ctx, unsigned int count, unsigned int size)
 		fz_throw(ctx, "calloc (%d x %d bytes) failed (integer overflow)", count, size);
 	}
 
-	p = ctx->alloc->malloc(ctx->alloc->user, count * size);
+	p = do_scavenging_malloc(ctx, count * size);
 	if (!p)
 	{
 		fz_throw(ctx, "calloc (%d x %d bytes) failed", count, size);
@@ -83,7 +122,7 @@ fz_calloc_no_throw(fz_context *ctx, unsigned int count, unsigned int size)
 		return NULL;
 	}
 
-	p = ctx->alloc->malloc(ctx->alloc->user, count * size);
+	p = do_scavenging_malloc(ctx, count * size);
 	if (p)
 	{
 		memset(p, 0, count*size);
@@ -105,7 +144,7 @@ fz_resize_array(fz_context *ctx, void *p, unsigned int count, unsigned int size)
 	if (count > UINT_MAX / size)
 		fz_throw(ctx, "resize array (%d x %d bytes) failed (integer overflow)", count, size);
 
-	np = ctx->alloc->realloc(ctx->alloc->user, p, count * size);
+	np = do_scavenging_realloc(ctx, p, count * size);
 	if (!np)
 		fz_throw(ctx, "resize array (%d x %d bytes) failed", count, size);
 	return np;
@@ -126,13 +165,15 @@ fz_resize_array_no_throw(fz_context *ctx, void *p, unsigned int count, unsigned
 		return NULL;
 	}
 
-	return ctx->alloc->realloc(ctx->alloc->user, p, count * size);
+	return do_scavenging_realloc(ctx, p, count * size);
 }
 
 void
 fz_free(fz_context *ctx, void *p)
 {
+	/* LOCK */
 	ctx->alloc->free(ctx->alloc->user, p);
+	/* UNLOCK */
 }
 
 char *
diff --git a/fitz/fitz.h b/fitz/fitz.h
index 81743d0a..aad4b9a2 100644
--- a/fitz/fitz.h
+++ b/fitz/fitz.h
@@ -525,7 +525,8 @@ void fz_drop_storable(fz_context *, fz_storable *);
 void fz_store_item(fz_context *ctx, fz_obj *key, void *val, unsigned int itemsize);
 void *fz_find_item(fz_context *ctx, fz_store_free_fn *freefn, fz_obj *key);
 void fz_remove_item(fz_context *ctx, fz_store_free_fn *freefn, fz_obj *key);
-void fz_age_store(fz_context *ctx, int maxage);
+void fz_empty_store(fz_context *ctx);
+int fz_store_scavenge(fz_context *ctx, unsigned int size, int *phase);
 
 /*
  * Buffered reader.
diff --git a/fitz/res_store.c b/fitz/res_store.c
index 08885c30..6c1c628d 100644
--- a/fitz/res_store.c
+++ b/fitz/res_store.c
@@ -9,7 +9,6 @@ struct fz_item_s
 	fz_item *next;
 	fz_item *prev;
 	fz_store *store;
-	int age;
 };
 
 struct refkey
@@ -83,8 +82,10 @@ fz_drop_storable(fz_context *ctx, fz_storable *s)
 }
 
 static void
-evict(fz_context *ctx, fz_store *store, fz_item *item)
+evict(fz_context *ctx, fz_item *item)
 {
+	fz_store *store = ctx->store;
+
 	store->size -= item->size;
 	/* Unlink from the linked list */
 	if (item->next)
@@ -104,8 +105,10 @@ evict(fz_context *ctx, fz_store *store, fz_item *item)
 		refkey.gen = fz_to_gen(item->key);
 		fz_hash_remove(store->hash, &refkey);
 	}
-	/* Drop the value, key and item */
-	item->val->free(ctx, item->val);
+	/* Drop a reference to the value (freeing if required) */
+	if (item->val->refs > 0 && --item->val->refs == 0)
+		item->val->free(ctx, item->val);
+	/* Always drops the key and free the item */
 	fz_drop_obj(item->key);
 	fz_free(ctx, item);
 }
@@ -143,7 +146,7 @@ ensure_space(fz_context *ctx, unsigned int tofree)
 		{
 			/* Free this item */
 			count += item->size;
-			evict(ctx, store, item);
+			evict(ctx, item);
 
 			if (count >= tofree)
 				break;
@@ -308,7 +311,7 @@ fz_remove_item(fz_context *ctx, fz_store_free_fn *free, fz_obj *key)
 }
 
 void
-fz_age_store(fz_context *ctx, int maxage)
+fz_empty_store(fz_context *ctx)
 {
 	fz_item *item, *next;
 	fz_store *store = ctx->store;
@@ -321,11 +324,7 @@ fz_age_store(fz_context *ctx, int maxage)
 	for (item = store->head; item; item = next)
 	{
 		next = item->next;
-		/* If we've only got 1 reference, then we must be the only
-		 * holders. Age the item. If it's older than the maximum,
-		 * bin it. */
-		if (item->val->refs == 1 && ++item->age > maxage)
-			evict(ctx, store, item);
+		evict(ctx, item);
 	}
 	/* UNLOCK */
 }
@@ -335,7 +334,7 @@ fz_free_store_context(fz_context *ctx)
 {
 	if (ctx == NULL || ctx->store == NULL)
 		return;
-	fz_age_store(ctx, 0);
+	fz_empty_store(ctx);
 	fz_free_hash(ctx->store->hash);
 	fz_free(ctx, ctx->store);
 	ctx->store = NULL;
@@ -352,7 +351,7 @@ fz_debug_store(fz_context *ctx)
 	/* LOCK */
 	for (item = store->head; item; item = item->next)
 	{
-		printf("store[*][claim=%d] ", item->val->refs);
+		printf("store[*][refs=%d][size=%d] ", item->val->refs, item->size);
 		if (fz_is_indirect(item->key))
 		{
 			printf("(%d %d R) ", fz_to_num(item->key), fz_to_gen(item->key));
@@ -362,3 +361,74 @@ fz_debug_store(fz_context *ctx)
 	}
 	/* UNLOCK */
 }
+
+static int
+scavenge(fz_context *ctx, unsigned int tofree)
+{
+	fz_store *store = ctx->store;
+	unsigned int count = 0;
+	fz_item *item, *prev;
+
+	/* Free the items */
+	for (item = store->tail; item; item = prev)
+	{
+		prev = item->prev;
+		if (item->val->refs == 1)
+		{
+			/* Free this item */
+			count += item->size;
+			evict(ctx, item);
+
+			if (count >= tofree)
+				break;
+		}
+	}
+	/* Success is managing to evict any blocks */
+	return count != 0;
+}
+
+int fz_store_scavenge(fz_context *ctx, unsigned int size, int *phase)
+{
+	fz_store *store;
+	unsigned int max;
+
+	if (ctx == NULL)
+		return 0;
+	store = ctx->store;
+	if (store == NULL)
+		return 0;
+
+#ifdef DEBUG_SCAVENGING
+	printf("Scavenging: store=%d size=%d phase=%d\n", store->size, size, *phase);
+	fz_debug_store(ctx);
+	Memento_stats();
+#endif
+	do
+	{
+		/* Calculate 'max' as the maximum size of the store for this phase */
+		if (store->max != FZ_STORE_UNLIMITED)
+			max = store->max / 16 * (16 - *phase);
+		else
+			max = store->size / (16 - *phase) * (15 - *phase);
+		*phase++;
+
+		if (size + store->size > max)
+			if (scavenge(ctx, size + store->size - max))
+			{
+#ifdef DEBUG_SCAVENGING
+				printf("scavenged: store=%d\n", store->size);
+				fz_debug_store(ctx);
+				Memento_stats();
+#endif
+				return 1;
+			}
+	}
+	while (max > 0);
+
+#ifdef DEBUG_SCAVENGING
+	printf("scavenging failed\n");
+	fz_debug_store(ctx);
+	Memento_listBlocks();
+#endif
+	return 0;
+}
diff --git a/scripts/cmapdump.c b/scripts/cmapdump.c
index c8ae8134..dc5d93e6 100644
--- a/scripts/cmapdump.c
+++ b/scripts/cmapdump.c
@@ -192,3 +192,8 @@ void fz_new_store_context(fz_context *ctx, unsigned int max)
 void fz_free_store_context(fz_context *ctx)
 {
 }
+
+int fz_store_scavenge(fz_context *ctx, unsigned int size, int *phase)
+{
+	return 0;
+}