Extend store to cope with references used in keys.

The store is effectively a list of items, where each item is a
(key, value) pair. The design is such that we can easily get
into the state where the only reference to a value is that held
by the store. Subsequent references can then be generated by
things being 'found' from within the store.

While the only reference to an object is that held by it being
a value in the store, the store is free to evict it to save
memory.

Images present a complication to this design; images are stored
both as values within the store (by the pdf agent, so that we
do not regenerate images each time we meet them in the file),
and as parts of the keys within the store.

For example, once an image is decoded to give a pixmap, the
pixmap is cached in the store. The key to look that pixmap up
again includes a reference to the image from which the pixmap
was generated.

This means, that for document handlers such as gproof that do
not place images in the store, we can end up with images that
are kept around purely by dint of being used as references in
store keys. There is no chance of the value (the decoded pixmap)
ever being 'found' from the store as no one other than the
key is holding a reference to the image required. Thus the
images/pixmaps are never freed until the store is emptied.

This commit offers a fix for this situation.

Standard store items are based on an fz_storable type. Here we
introduce a new fz_key_storable type derived from that. As well
as keeping track of the number of references a given item has
to it, it keeps a separate count of the number of references a
given item has to it from keys in the store.

On dropping a reference, we check to see if the number of
references has become the same as the number of references from
keys in the store. If it has, then we know that these keys can
never be 'found' again. So we filter them out of the store,
which drops the items.

5 files changed, 189 insertions, 17 deletions

diff --git a/include/mupdf/fitz/image.h b/include/mupdf/fitz/image.h
index 6482e80e..cc521904 100644
--- a/include/mupdf/fitz/image.h
+++ b/include/mupdf/fitz/image.h
@@ -68,6 +68,9 @@ void fz_drop_image_base(fz_context *ctx, fz_image *image);
 */
 fz_image *fz_keep_image(fz_context *ctx, fz_image *image);
 
+fz_image *fz_keep_image_store_key(fz_context *ctx, fz_image *image);
+void fz_drop_image_store_key(fz_context *ctx, fz_image *image);
+
 typedef void (fz_drop_image_fn)(fz_context *ctx, fz_image *image);
 typedef fz_pixmap *(fz_image_get_pixmap_fn)(fz_context *, fz_image *, fz_irect *, int, int, int *);
 typedef size_t (fz_image_get_size_fn)(fz_context *, fz_image *);
@@ -85,7 +88,7 @@ size_t fz_image_size(fz_context *ctx, fz_image *im);
 
 struct fz_image_s
 {
-	fz_storable storable;
+	fz_key_storable key_storable;
 	int w, h;
 	uint8_t n;
 	uint8_t bpc;
diff --git a/include/mupdf/fitz/store.h b/include/mupdf/fitz/store.h
index 07f6a286..2ef9810b 100644
--- a/include/mupdf/fitz/store.h
+++ b/include/mupdf/fitz/store.h
@@ -26,6 +26,7 @@
  */
 
 typedef struct fz_storable_s fz_storable;
+typedef struct fz_key_storable_s fz_key_storable;
 
 typedef void (fz_store_drop_fn)(fz_context *, fz_storable *);
 
@@ -34,14 +35,30 @@ struct fz_storable_s {
 	fz_store_drop_fn *drop;
 };
 
+struct fz_key_storable_s {
+	fz_storable storable;
+	int store_key_refs;
+};
+
 #define FZ_INIT_STORABLE(S_,RC,DROP) \
 	do { fz_storable *S = &(S_)->storable; S->refs = (RC); \
 	S->drop = (DROP); \
 	} while (0)
 
+#define FZ_INIT_KEY_STORABLE(KS_,RC,DROP) \
+	do { fz_key_storable *KS = &(KS_)->key_storable; KS->store_key_refs = 0;\
+	FZ_INIT_STORABLE(KS,RC,DROP); \
+	} while (0)
+
 void *fz_keep_storable(fz_context *, const fz_storable *);
 void fz_drop_storable(fz_context *, const fz_storable *);
 
+void *fz_keep_key_storable(fz_context *, const fz_key_storable *);
+int fz_drop_key_storable(fz_context *, const fz_key_storable *);
+
+void *fz_keep_key_storable_key(fz_context *, const fz_key_storable *);
+void fz_drop_key_storable_key(fz_context *, const fz_key_storable *);
+
 /*
 	The store can be seen as a dictionary that maps keys to fz_storable
 	values. In order to allow keys of different types to be stored, we
@@ -192,6 +209,10 @@ int fz_store_scavenge(fz_context *ctx, size_t size, int *phase);
 */
 int fz_shrink_store(fz_context *ctx, unsigned int percent);
 
+typedef int (fz_store_filter_fn)(fz_context *ctx, void *arg, void *key);
+
+void fz_filter_store(fz_context *ctx, fz_store_filter_fn *fn, void *arg, fz_store_type *type);
+
 /*
 	fz_print_store: Dump the contents of the store for debugging.
 */
diff --git a/source/fitz/image.c b/source/fitz/image.c
index e6772783..247cb088 100644
--- a/source/fitz/image.c
+++ b/source/fitz/image.c
@@ -18,18 +18,6 @@ struct fz_pixmap_image_s
 	fz_pixmap *tile;
 };
 
-fz_image *
-fz_keep_image(fz_context *ctx, fz_image *image)
-{
-	return fz_keep_storable(ctx, &image->storable);
-}
-
-void
-fz_drop_image(fz_context *ctx, fz_image *image)
-{
-	fz_drop_storable(ctx, &image->storable);
-}
-
 typedef struct fz_image_key_s fz_image_key;
 
 struct fz_image_key_s {
@@ -39,6 +27,24 @@ struct fz_image_key_s {
 	fz_irect rect;
 };
 
+fz_image *
+fz_keep_image(fz_context *ctx, fz_image *image)
+{
+	return fz_keep_key_storable(ctx, &image->key_storable);
+}
+
+fz_image *
+fz_keep_image_store_key(fz_context *ctx, fz_image *image)
+{
+	return fz_keep_key_storable_key(ctx, &image->key_storable);
+}
+
+void
+fz_drop_image_store_key(fz_context *ctx, fz_image *image)
+{
+	fz_drop_key_storable_key(ctx, &image->key_storable);
+}
+
 static int
 fz_make_hash_image_key(fz_context *ctx, fz_store_hash *hash, void *key_)
 {
@@ -62,7 +68,7 @@ fz_drop_image_key(fz_context *ctx, void *key_)
 	fz_image_key *key = (fz_image_key *)key_;
 	if (fz_drop_imp(ctx, key, &key->refs))
 	{
-		fz_drop_image(ctx, key->image);
+		fz_drop_image_store_key(ctx, key->image);
 		fz_free(ctx, key);
 	}
 }
@@ -91,6 +97,26 @@ static fz_store_type fz_image_store_type =
 	fz_print_image
 };
 
+static int
+drop_matching_images(fz_context *ctx, void *image_, void *key_)
+{
+	fz_image_key *key = (fz_image_key *)key_;
+	fz_image *image = (fz_image *)image_;
+
+	return key->image == image;
+}
+
+void
+fz_drop_image(fz_context *ctx, fz_image *image)
+{
+	if (fz_drop_key_storable(ctx, &image->key_storable))
+	{
+		/* All the image refs left are references from keys in the store. */
+		/* We can never hope to match these keys again, so drop the objects. */
+		fz_filter_store(ctx, drop_matching_images, image, &fz_image_store_type);
+	}
+}
+
 static void
 fz_mask_color_key(fz_pixmap *pix, int n, const int *colorkey)
 {
@@ -671,7 +697,7 @@ fz_get_pixmap_from_image(fz_context *ctx, fz_image *image, const fz_irect *subar
 
 		keyp = fz_malloc_struct(ctx, fz_image_key);
 		keyp->refs = 1;
-		keyp->image = fz_keep_image(ctx, image);
+		keyp->image = fz_keep_image_store_key(ctx, image);
 		keyp->l2factor = l2factor;
 		keyp->rect = key.rect;
 		existing_tile = fz_store_item(ctx, keyp, tile, fz_pixmap_size(ctx, tile), &fz_image_store_type);
@@ -754,7 +780,7 @@ fz_new_image(fz_context *ctx, int w, int h, int bpc, fz_colorspace *colorspace,
 	assert(size >= sizeof(fz_image));
 
 	image = Memento_label(fz_calloc(ctx, 1, size), "fz_image");
-	FZ_INIT_STORABLE(image, 1, fz_drop_image_imp);
+	FZ_INIT_KEY_STORABLE(image, 1, fz_drop_image_imp);
 	image->drop_image = drop;
 	image->get_pixmap = get;
 	image->get_size = get_size;
diff --git a/source/fitz/store.c b/source/fitz/store.c
index cad027bc..8d0a7bc4 100644
--- a/source/fitz/store.c
+++ b/source/fitz/store.c
@@ -81,6 +81,95 @@ fz_drop_storable(fz_context *ctx, const fz_storable *sc)
 		s->drop(ctx, s);
 }
 
+void *fz_keep_key_storable(fz_context *ctx, const fz_key_storable *sc)
+{
+	return fz_keep_storable(ctx, &sc->storable);
+}
+
+int fz_drop_key_storable(fz_context *ctx, const fz_key_storable *sc)
+{
+	/* Explicitly drop const to allow us to use const
+	 * sanely throughout the code. */
+	fz_key_storable *s = (fz_key_storable *)sc;
+	int drop;
+	int only_refs_are_store_key_refs = 0;
+
+	if (s == NULL)
+		return 0;
+
+	if (s->storable.refs > 0)
+		(void)Memento_dropRef(s);
+	fz_lock(ctx, FZ_LOCK_ALLOC);
+	if (s->storable.refs > 0)
+	{
+		drop = --s->storable.refs == 0;
+		if (!drop && s->storable.refs == s->store_key_refs)
+			only_refs_are_store_key_refs = 1;
+	}
+	else
+		drop = 0;
+	fz_unlock(ctx, FZ_LOCK_ALLOC);
+	/*
+		If we are dropping the last reference to an object, then
+		it cannot possibly be in the store (as the store always
+		keeps a ref to everything in it, and doesn't drop via
+		this method. So we can simply drop the storable object
+		itself without any operations on the fz_store.
+	 */
+	if (drop)
+		s->storable.drop(ctx, &s->storable);
+	return only_refs_are_store_key_refs;
+}
+
+void *fz_keep_key_storable_key(fz_context *ctx, const fz_key_storable *sc)
+{
+	/* Explicitly drop const to allow us to use const
+	 * sanely throughout the code. */
+	fz_key_storable *s = (fz_key_storable *)sc;
+
+	if (s == NULL)
+		return NULL;
+
+	if (s->storable.refs > 0)
+		(void)Memento_takeRef(s);
+	fz_lock(ctx, FZ_LOCK_ALLOC);
+	if (s->storable.refs > 0)
+	{
+		++s->storable.refs;
+		++s->store_key_refs;
+	}
+	fz_unlock(ctx, FZ_LOCK_ALLOC);
+	return s;
+}
+
+void fz_drop_key_storable_key(fz_context *ctx, const fz_key_storable *sc)
+{
+	/* Explicitly drop const to allow us to use const
+	 * sanely throughout the code. */
+	fz_key_storable *s = (fz_key_storable *)sc;
+	int drop;
+
+	if (s == NULL)
+		return;
+
+	if (s->storable.refs > 0)
+		(void)Memento_dropRef(s);
+	fz_lock(ctx, FZ_LOCK_ALLOC);
+	assert(s->store_key_refs > 0 && s->storable.refs >= s->store_key_refs);
+	drop = --s->storable.refs == 0;
+	--s->store_key_refs;
+	fz_unlock(ctx, FZ_LOCK_ALLOC);
+	/*
+		If we are dropping the last reference to an object, then
+		it cannot possibly be in the store (as the store always
+		keeps a ref to everything in it, and doesn't drop via
+		this method. So we can simply drop the storable object
+		itself without any operations on the fz_store.
+	 */
+	if (drop)
+		s->storable.drop(ctx, &s->storable);
+}
+
 static void
 evict(fz_context *ctx, fz_item *item)
 {
@@ -636,3 +725,36 @@ fz_shrink_store(fz_context *ctx, unsigned int percent)
 
 	return success;
 }
+
+void fz_filter_store(fz_context *ctx, fz_store_filter_fn *fn, void *arg, fz_store_type *type)
+{
+	fz_store *store;
+	fz_item *item, *prev;
+
+	if (ctx == NULL)
+		return;
+	store = ctx->store;
+	if (store == NULL)
+		return;
+
+	fz_lock(ctx, FZ_LOCK_ALLOC);
+
+	/* Free the items */
+	for (item = store->tail; item; item = prev)
+	{
+		prev = item->prev;
+		if (item->type != type)
+			continue;
+
+		if (fn(ctx, arg, item->key))
+		{
+			/* Free this item */
+			evict(ctx, item); /* Drops then retakes lock */
+
+			/* Have to restart search again, as prev may no longer
+			 * be valid due to release of lock in evict. */
+			prev = store->tail;
+		}
+	}
+	fz_unlock(ctx, FZ_LOCK_ALLOC);
+}
diff --git a/source/gprf/gprf-doc.c b/source/gprf/gprf-doc.c
index 5ca14aea..56570db0 100644
--- a/source/gprf/gprf-doc.c
+++ b/source/gprf/gprf-doc.c
@@ -467,7 +467,7 @@ fz_new_gprf_image(fz_context *ctx, gprf_page *page, int imagenum, fz_off_t offse
 			h = GPRF_TILESIZE;
 	}
 
-	FZ_INIT_STORABLE(&image->super, 1, fz_drop_image_gprf_imp);
+	FZ_INIT_KEY_STORABLE(&image->super, 1, fz_drop_image_gprf_imp);
 	image->super.w = w;
 	image->super.h = h;
 	image->super.n = 4; /* Always RGB + Alpha */