[scaled-font] Lean and mean global glyph cache.

Jeff Muizelaar pointed out that the severe overallocation implicit in the
current version of the glyph cache is obnoxious and prevents him from
accepting the trunk into Mozilla. Jeff captured a trace of scaled font
and glyph usage during a tp run and presented his analysis in
http://lists.cairographics.org/archives/cairo/2009-March/016706.html

Using that data, the design was changed to allocate pages of glyphs from a
capped global pool but with per-font hash tables. This should allow the
glyph cache to have tight memory bounds with fair allocation according to
usage. Note that both the old design and the 1.8 glyph cache had
essentially unbounded memory constraints, since each scaled font could
cache up to 256 glyphs (1.8) or had a reserved page (old), with no limit
on the number of active fonts. Currently the eviction policy is a simple
random strategy, this gives a 'fair' allotment of the cache, but a LRU
variant might perform better.

On a sample run of firefox-3.0.7 perusing BBC news in 32 languages:
1.8:  cache allocation 8190x, ~1.2 MiB; elapsed 88.2s
old:  cache allocation 771x, ~13.8 MiB; elapsed 81.7s
lean: cache allocation 433x,  ~1.8 MiB; elapsed 82.4s

9 files changed, 232 insertions, 289 deletions

diff --git a/src/cairo-cache-private.h b/src/cairo-cache-private.h
index 8ad0c774a..25858e544 100644
--- a/src/cairo-cache-private.h
+++ b/src/cairo-cache-private.h
@@ -97,6 +97,7 @@ typedef void
 
 cairo_private cairo_cache_t *
 _cairo_cache_create (cairo_cache_keys_equal_func_t keys_equal,
+		     cairo_cache_predicate_func_t  predicate,
 		     cairo_destroy_func_t	   entry_destroy,
 		     unsigned long		   max_size);
 
@@ -113,10 +114,6 @@ cairo_private void *
 _cairo_cache_lookup (cairo_cache_t	  *cache,
 		     cairo_cache_entry_t  *key);
 
-cairo_private void *
-_cairo_cache_steal (cairo_cache_t	  *cache,
-		     cairo_cache_entry_t  *key);
-
 cairo_private cairo_status_t
 _cairo_cache_insert (cairo_cache_t	 *cache,
 		     cairo_cache_entry_t *entry);
diff --git a/src/cairo-cache.c b/src/cairo-cache.c
index cab6e1e9f..7542242dc 100644
--- a/src/cairo-cache.c
+++ b/src/cairo-cache.c
@@ -42,9 +42,16 @@ static void
 _cairo_cache_shrink_to_accommodate (cairo_cache_t *cache,
 				    unsigned long  additional);
 
+static cairo_bool_t
+_cairo_cache_entry_is_non_zero (const void *entry)
+{
+    return ((const cairo_cache_entry_t *) entry)->size;
+}
+
 static cairo_status_t
 _cairo_cache_init (cairo_cache_t		*cache,
 		   cairo_cache_keys_equal_func_t keys_equal,
+		   cairo_cache_predicate_func_t  predicate,
 		   cairo_destroy_func_t		 entry_destroy,
 		   unsigned long		 max_size)
 {
@@ -52,6 +59,9 @@ _cairo_cache_init (cairo_cache_t		*cache,
     if (unlikely (cache->hash_table == NULL))
 	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 
+    if (predicate == NULL)
+	predicate = _cairo_cache_entry_is_non_zero;
+    cache->predicate = predicate;
     cache->entry_destroy = entry_destroy;
 
     cache->max_size = max_size;
@@ -114,6 +124,7 @@ _cairo_cache_fini (cairo_cache_t *cache)
  **/
 cairo_cache_t *
 _cairo_cache_create (cairo_cache_keys_equal_func_t keys_equal,
+		     cairo_cache_predicate_func_t  predicate,
 		     cairo_destroy_func_t	   entry_destroy,
 		     unsigned long		   max_size)
 {
@@ -126,7 +137,11 @@ _cairo_cache_create (cairo_cache_keys_equal_func_t keys_equal,
 	return NULL;
     }
 
-    status = _cairo_cache_init (cache, keys_equal, entry_destroy, max_size);
+    status = _cairo_cache_init (cache,
+				keys_equal,
+				predicate,
+				entry_destroy,
+				max_size);
     if (unlikely (status)) {
 	free (cache);
 	return NULL;
@@ -221,26 +236,6 @@ _cairo_cache_lookup (cairo_cache_t	  *cache,
 				     (cairo_hash_entry_t *) key);
 }
 
-void *
-_cairo_cache_steal (cairo_cache_t	  *cache,
-		    cairo_cache_entry_t  *key)
-{
-    cairo_cache_entry_t *entry;
-
-    entry = _cairo_hash_table_steal (cache->hash_table,
-				     (cairo_hash_entry_t *) key);
-    if (entry != NULL)
-	cache->size -= entry->size;
-
-    return entry;
-}
-
-static cairo_bool_t
-_cairo_cache_entry_is_non_zero (void *entry)
-{
-    return ((cairo_cache_entry_t *)entry)->size;
-}
-
 /**
  * _cairo_cache_remove_random:
  * @cache: a cache
@@ -256,7 +251,7 @@ _cairo_cache_remove_random (cairo_cache_t *cache)
     cairo_cache_entry_t *entry;
 
     entry = _cairo_hash_table_random_entry (cache->hash_table,
-					    _cairo_cache_entry_is_non_zero);
+					    cache->predicate);
     if (unlikely (entry == NULL))
 	return FALSE;
 
diff --git a/src/cairo-ft-font.c b/src/cairo-ft-font.c
index 493a1e27d..ec6041a2a 100644
--- a/src/cairo-ft-font.c
+++ b/src/cairo-ft-font.c
@@ -532,9 +532,9 @@ _cairo_ft_unscaled_font_destroy (void *abstract_font)
 }
 
 static cairo_bool_t
-_has_unlocked_face (void *entry)
+_has_unlocked_face (const void *entry)
 {
-    cairo_ft_unscaled_font_t *unscaled = entry;
+    const cairo_ft_unscaled_font_t *unscaled = entry;
 
     return (!unscaled->from_face && unscaled->lock_count == 0 && unscaled->face);
 }
diff --git a/src/cairo-hash-private.h b/src/cairo-hash-private.h
index 8ab085822..32078bd21 100644
--- a/src/cairo-hash-private.h
+++ b/src/cairo-hash-private.h
@@ -51,7 +51,7 @@ typedef cairo_bool_t
 (*cairo_hash_keys_equal_func_t) (const void *key_a, const void *key_b);
 
 typedef cairo_bool_t
-(*cairo_hash_predicate_func_t) (void *entry);
+(*cairo_hash_predicate_func_t) (const void *entry);
 
 typedef void
 (*cairo_hash_callback_func_t) (void *entry,
@@ -68,10 +68,6 @@ _cairo_hash_table_lookup (cairo_hash_table_t  *hash_table,
 			  cairo_hash_entry_t  *key);
 
 cairo_private void *
-_cairo_hash_table_steal (cairo_hash_table_t *hash_table,
-			 cairo_hash_entry_t *key);
-
-cairo_private void *
 _cairo_hash_table_random_entry (cairo_hash_table_t	   *hash_table,
 				cairo_hash_predicate_func_t predicate);
 
diff --git a/src/cairo-hash.c b/src/cairo-hash.c
index c0c9f7d86..51303f5a7 100644
--- a/src/cairo-hash.c
+++ b/src/cairo-hash.c
@@ -346,61 +346,6 @@ _cairo_hash_table_lookup (cairo_hash_table_t *hash_table,
 }
 
 /**
- * _cairo_hash_table_steal:
- * @hash_table: a hash table
- * @key: the key of interest
- *
- * Performs a lookup in @hash_table looking for an entry which has a
- * key that matches @key, (as determined by the keys_equal() function
- * passed to _cairo_hash_table_create) and removes that entry from the
- * hash table.
- *
- * Return value: the matching entry, of %NULL if no match was found.
- **/
-void *
-_cairo_hash_table_steal (cairo_hash_table_t *hash_table,
-			 cairo_hash_entry_t *key)
-{
-    cairo_hash_entry_t *entry;
-    unsigned long table_size, i, idx, step;
-
-    table_size = hash_table->arrangement->size;
-    idx = key->hash % table_size;
-
-    entry = hash_table->entries[idx];
-    if (ENTRY_IS_LIVE (entry)) {
-	if (hash_table->keys_equal (key, entry)) {
-	    hash_table->entries[idx] = DEAD_ENTRY;
-	    hash_table->live_entries--;
-	    return entry;
-	}
-    } else if (ENTRY_IS_FREE (entry))
-	return NULL;
-
-    i = 1;
-    step = key->hash % hash_table->arrangement->rehash;
-    if (step == 0)
-	step = 1;
-    do {
-	idx += step;
-	if (idx >= table_size)
-	    idx -= table_size;
-
-	entry = hash_table->entries[idx];
-	if (ENTRY_IS_LIVE (entry)) {
-	    if (hash_table->keys_equal (key, entry)) {
-		hash_table->entries[idx] = DEAD_ENTRY;
-		hash_table->live_entries--;
-		return entry;
-	    }
-	} else if (ENTRY_IS_FREE (entry))
-	    return NULL;
-    } while (++i < table_size);
-
-    return NULL;
-}
-
-/**
  * _cairo_hash_table_random_entry:
  * @hash_table: a hash table
  * @predicate: a predicate function.
diff --git a/src/cairo-scaled-font-private.h b/src/cairo-scaled-font-private.h
index 89820c8f3..f6c97488c 100644
--- a/src/cairo-scaled-font-private.h
+++ b/src/cairo-scaled-font-private.h
@@ -106,8 +106,10 @@ struct _cairo_scaled_font {
     /* The mutex protects modification to all subsequent fields. */
     cairo_mutex_t mutex;
 
-    int cache_frozen;
-    cairo_scaled_glyph_page_t *mru_page;
+    cairo_hash_table_t *glyphs;
+    cairo_scaled_glyph_page_t *glyph_pages;
+    cairo_bool_t cache_frozen;
+    cairo_bool_t global_cache_frozen;
 
     /*
      * One surface backend may store data in each glyph.
diff --git a/src/cairo-scaled-font.c b/src/cairo-scaled-font.c
index 58733a798..e14aa2e98 100644
--- a/src/cairo-scaled-font.c
+++ b/src/cairo-scaled-font.c
@@ -49,21 +49,30 @@
 #define ISFINITE(x) ((x) * (x) >= 0.) /* check for NaNs */
 #endif
 
-#define CAIRO_SCALED_GLYPH_PAGE_SHIFT 7
-#define CAIRO_SCALED_GLYPH_PAGE_SIZE (1 << CAIRO_SCALED_GLYPH_PAGE_SHIFT)
-#define CAIRO_SCALED_GLYPH_PAGE_INDEX(I) \
-    ((I) & (CAIRO_SCALED_GLYPH_PAGE_SIZE - 1))
-#define CAIRO_SCALED_GLYPH_PAGE_BASE_INDEX(I) ((I) & -CAIRO_SCALED_GLYPH_PAGE_SIZE)
-#define CAIRO_SCALED_GLYPH_PAGE_HAS_INDEX(P, I) \
-    ((I) - (P)->base_index < CAIRO_SCALED_GLYPH_PAGE_SIZE)
-typedef struct _cairo_scaled_glyph_page_key {
-    cairo_cache_entry_t cache_entry;
-    cairo_scaled_font_t *scaled_font;
-} cairo_scaled_glyph_page_key_t;
+/* Global Glyph Cache
+ *
+ * We maintain a global pool of glyphs split between all open fonts. This
+ * allows a heavily used individual font to cache more glyphs than we could
+ * manage if we used per-font glyph caches, but at the same time maintains
+ * fairness across all fonts and provides a cap on the maximum number of
+ * global glyphs.
+ *
+ * The glyphs are allocated in pages, which are cached in the global pool.
+ * Using pages means we can reduce the frequency at which we have to probe the
+ * global cache and ameliorates the memory allocation pressure.
+ */
+
+/* XXX: This number is arbitrary---we've never done any measurement of this. */
+#define MAX_GLYPH_PAGES_CACHED 512
+static cairo_cache_t *cairo_scaled_glyph_page_cache;
 
+#define CAIRO_SCALED_GLYPH_PAGE_SIZE 32
 struct _cairo_scaled_glyph_page {
-    cairo_scaled_glyph_page_key_t key;
-    unsigned long base_index;
+    cairo_cache_entry_t cache_entry;
+
+    struct _cairo_scaled_glyph_page *prev, *next;
+
+    unsigned int num_glyphs;
     cairo_scaled_glyph_t glyphs[CAIRO_SCALED_GLYPH_PAGE_SIZE];
 };
 
@@ -176,13 +185,9 @@ static void
 _cairo_scaled_font_fini_internal (cairo_scaled_font_t *scaled_font);
 
 static void
-_cairo_scaled_glyph_page_cache_remove_scaled_font (cairo_scaled_font_t
-						   *scaled_font);
-
-static void
-_cairo_scaled_glyph_fini (cairo_scaled_glyph_t *scaled_glyph)
+_cairo_scaled_glyph_fini (cairo_scaled_font_t *scaled_font,
+			  cairo_scaled_glyph_t *scaled_glyph)
 {
-    cairo_scaled_font_t	*scaled_font = scaled_glyph->scaled_font;
     const cairo_surface_backend_t *surface_backend = scaled_font->surface_backend;
 
     if (surface_backend != NULL && surface_backend->scaled_glyph_fini != NULL)
@@ -196,8 +201,6 @@ _cairo_scaled_glyph_fini (cairo_scaled_glyph_t *scaled_glyph)
 
     if (scaled_glyph->meta_surface != NULL)
 	cairo_surface_destroy (scaled_glyph->meta_surface);
-
-    scaled_glyph->scaled_font = NULL;
 }
 
 #define ZOMBIE 0
@@ -222,8 +225,10 @@ static const cairo_scaled_font_t _cairo_scaled_font_nil = {
     { 0., 0., 0., 0., 0. },	/* extents */
     { 0., 0., 0., 0., 0. },	/* fs_extents */
     CAIRO_MUTEX_NIL_INITIALIZER,/* mutex */
+    NULL,			/* glyphs */
+    NULL,			/* pages */
     FALSE,			/* cache_frozen */
-    NULL,			/* mru_page */
+    FALSE,			/* global_cache_frozen */
     NULL,			/* surface_backend */
     NULL,			/* surface_private */
     NULL			/* backend */
@@ -419,112 +424,29 @@ _cairo_scaled_font_map_destroy (void)
  CLEANUP_MUTEX_LOCK:
     CAIRO_MUTEX_UNLOCK (_cairo_scaled_font_map_mutex);
 }
-
-/* Global Glyph Cache
- *
- * We maintain a global pool of glyphs split between all open fonts. This
- * allows a heavily used individual font to cache more glyphs than we could
- * manage if we used per-font glyph caches, but at the same time maintains
- * fairness across all fonts and provides a cap on the maximum number of
- * global glyphs.
- *
- * The glyphs are allocated in pages, which are cached in the global pool.
- * Using pages means we can exploit spatial locality within the font (nearby
- * indices are typically used in clusters) to reduce frequency of small
- * allocations and allow the scaled font to reserve a single MRU page of
- * glyphs.
- */
-
-/* XXX: This number is arbitrary---we've never done any measurement of this. */
-#define MAX_GLYPH_PAGES_CACHED 512
-
-static cairo_cache_t *cairo_scaled_glyph_page_cache;
-
-static cairo_bool_t
-_cairo_scaled_glyph_pages_equal (const void *key_a, const void *key_b)
-{
-    const cairo_scaled_glyph_page_key_t *a = key_a;
-    const cairo_scaled_glyph_page_key_t *b = key_b;
-
-    return
-	a->cache_entry.hash == b->cache_entry.hash &&
-	a->scaled_font == b->scaled_font;
-}
-
 static void
 _cairo_scaled_glyph_page_destroy (void *closure)
 {
     cairo_scaled_glyph_page_t *page = closure;
-    int n;
-
-    for (n = 0; n < CAIRO_SCALED_GLYPH_PAGE_SIZE; n++) {
-	if (page->glyphs[n].scaled_font != NULL)
-	    _cairo_scaled_glyph_fini (&page->glyphs[n]);
-    }
-
-    free (page);
-}
-
-static cairo_scaled_glyph_page_t *
-_cairo_scaled_glyph_page_cache_lookup (cairo_scaled_font_t *scaled_font,
-				       unsigned long index)
-{
-    cairo_scaled_glyph_page_key_t key;
-    cairo_scaled_glyph_page_t *page;
-
-    key.cache_entry.hash =
-	(index >> CAIRO_SCALED_GLYPH_PAGE_SHIFT) ^
-	(unsigned long) scaled_font;
-    key.scaled_font = scaled_font;
+    cairo_scaled_font_t *scaled_font;
+    unsigned int n;
 
-    if (scaled_font->cache_frozen) {
-	CAIRO_MUTEX_LOCK (_cairo_scaled_glyph_page_cache_mutex);
-	page = _cairo_cache_steal (cairo_scaled_glyph_page_cache,
-				   &key.cache_entry);
-	CAIRO_MUTEX_UNLOCK (_cairo_scaled_glyph_page_cache_mutex);
-    } else
-	page = NULL;
-
-    if (page == NULL) {
-	/* On miss, create glyph page and insert into cache */
-	page = malloc (sizeof (cairo_scaled_glyph_page_t));
-	if (unlikely (page == NULL))
-	    return NULL;
-
-	page->key.cache_entry.hash = key.cache_entry.hash;
-	/* We currently don't differentiate on glyph size at all */
-	page->key.cache_entry.size = 1;
-	page->key.scaled_font = scaled_font;
-	page->base_index = CAIRO_SCALED_GLYPH_PAGE_BASE_INDEX (index);
-
-	memset (page->glyphs, 0, sizeof (page->glyphs));
+    scaled_font = (cairo_scaled_font_t *) page->cache_entry.hash;
+    for (n = 0; n < page->num_glyphs; n++) {
+	_cairo_hash_table_remove (scaled_font->glyphs,
+				  &page->glyphs[n].hash_entry);
+	_cairo_scaled_glyph_fini (scaled_font, &page->glyphs[n]);
     }
 
-    return page;
-}
-
-static void
-_cairo_scaled_glyph_page_cache_remove_scaled_font_cb (void *entry,
-						      void *closure)
-{
-    cairo_scaled_glyph_page_key_t *key = entry;
-
-    if (key->scaled_font == closure)
-	_cairo_cache_remove (cairo_scaled_glyph_page_cache, entry);
-}
-
-static void
-_cairo_scaled_glyph_page_cache_remove_scaled_font (cairo_scaled_font_t *scaled_font)
-{
-    CAIRO_MUTEX_LOCK (_cairo_scaled_glyph_page_cache_mutex);
+    if (page->prev != NULL)
+	page->prev->next = page->next;
+    else
+	scaled_font->glyph_pages = page->next;
 
-    if (cairo_scaled_glyph_page_cache != NULL) {
-	_cairo_cache_foreach (cairo_scaled_glyph_page_cache,
-			      _cairo_scaled_glyph_page_cache_remove_scaled_font_cb,
-			      scaled_font);
-    }
+    if (page->next != NULL)
+	page->next->prev = page->prev;
 
-    CAIRO_MUTEX_UNLOCK (_cairo_scaled_glyph_page_cache_mutex);
+    free (page);
 }
 
 /* If a scaled font wants to unlock the font map while still being
@@ -702,7 +624,8 @@ _cairo_scaled_font_init_key (cairo_scaled_font_t        *scaled_font,
 }
 
 static cairo_bool_t
-_cairo_scaled_font_keys_equal (const void *abstract_key_a, const void *abstract_key_b)
+_cairo_scaled_font_keys_equal (const void *abstract_key_a,
+			       const void *abstract_key_b)
 {
     const cairo_scaled_font_t *key_a = abstract_key_a;
     const cairo_scaled_font_t *key_b = abstract_key_b;
@@ -720,6 +643,15 @@ _cairo_scaled_font_keys_equal (const void *abstract_key_a, const void *abstract_
 	    cairo_font_options_equal (&key_a->options, &key_b->options);
 }
 
+static cairo_bool_t
+_cairo_scaled_glyphs_equal (const void *abstract_a, const void *abstract_b)
+{
+    const cairo_scaled_glyph_t *a = abstract_a;
+    const cairo_scaled_glyph_t *b = abstract_b;
+
+    return a->hash_entry.hash == b->hash_entry.hash;
+}
+
 /*
  * Basic #cairo_scaled_font_t object management
  */
@@ -769,8 +701,15 @@ _cairo_scaled_font_init (cairo_scaled_font_t               *scaled_font,
 	    return status;
     }
 
-    scaled_font->finished = FALSE;
+    scaled_font->glyphs = _cairo_hash_table_create (_cairo_scaled_glyphs_equal);
+    if (unlikely (scaled_font->glyphs == NULL))
+	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+    scaled_font->glyph_pages = NULL;
     scaled_font->cache_frozen = FALSE;
+    scaled_font->global_cache_frozen = FALSE;
+
+    scaled_font->finished = FALSE;
 
     CAIRO_REFERENCE_COUNT_INIT (&scaled_font->ref_count, 1);
 
@@ -781,8 +720,6 @@ _cairo_scaled_font_init (cairo_scaled_font_t               *scaled_font,
 
     CAIRO_MUTEX_INIT (scaled_font->mutex);
 
-    scaled_font->mru_page = NULL;
-
     scaled_font->surface_backend = NULL;
     scaled_font->surface_private = NULL;
 
@@ -798,17 +735,20 @@ _cairo_scaled_font_freeze_cache (cairo_scaled_font_t *scaled_font)
     assert (scaled_font->status == CAIRO_STATUS_SUCCESS);
 
     CAIRO_MUTEX_LOCK (scaled_font->mutex);
+    scaled_font->cache_frozen = TRUE;
 }
 
 void
 _cairo_scaled_font_thaw_cache (cairo_scaled_font_t *scaled_font)
 {
-    if (scaled_font->cache_frozen) {
+    scaled_font->cache_frozen = FALSE;
+
+    if (scaled_font->global_cache_frozen) {
 	CAIRO_MUTEX_LOCK (_cairo_scaled_glyph_page_cache_mutex);
 	_cairo_cache_thaw (cairo_scaled_glyph_page_cache);
 	CAIRO_MUTEX_UNLOCK (_cairo_scaled_glyph_page_cache_mutex);
 
-	scaled_font->cache_frozen = FALSE;
+	scaled_font->global_cache_frozen = FALSE;
     }
 
     CAIRO_MUTEX_UNLOCK (scaled_font->mutex);
@@ -817,14 +757,14 @@ _cairo_scaled_font_thaw_cache (cairo_scaled_font_t *scaled_font)
 void
 _cairo_scaled_font_reset_cache (cairo_scaled_font_t *scaled_font)
 {
-    assert (CAIRO_MUTEX_IS_LOCKED (scaled_font->mutex));
+    assert (! scaled_font->cache_frozen);
 
-    if (scaled_font->mru_page != NULL) {
-	_cairo_scaled_glyph_page_destroy (scaled_font->mru_page);
-	scaled_font->mru_page = NULL;
+    CAIRO_MUTEX_LOCK (_cairo_scaled_glyph_page_cache_mutex);
+    while (scaled_font->glyph_pages != NULL) {
+	_cairo_cache_remove (cairo_scaled_glyph_page_cache,
+			     &scaled_font->glyph_pages->cache_entry);
     }
-
-    _cairo_scaled_glyph_page_cache_remove_scaled_font (scaled_font);
+    CAIRO_MUTEX_UNLOCK (_cairo_scaled_glyph_page_cache_mutex);
 }
 
 cairo_status_t
@@ -861,12 +801,8 @@ _cairo_scaled_font_fini_internal (cairo_scaled_font_t *scaled_font)
 {
     scaled_font->finished = TRUE;
 
-    if (scaled_font->mru_page != NULL) {
-	_cairo_scaled_glyph_page_destroy (scaled_font->mru_page);
-	scaled_font->mru_page = NULL;
-    }
-
-    _cairo_scaled_glyph_page_cache_remove_scaled_font (scaled_font);
+    _cairo_scaled_font_reset_cache (scaled_font);
+    _cairo_hash_table_destroy (scaled_font->glyphs);
 
     cairo_font_face_destroy (scaled_font->font_face);
     cairo_font_face_destroy (scaled_font->original_font_face);
@@ -2496,6 +2432,92 @@ _cairo_scaled_glyph_set_meta_surface (cairo_scaled_glyph_t *scaled_glyph,
     scaled_glyph->meta_surface = meta_surface;
 }
 
+static cairo_bool_t
+_cairo_scaled_glyph_page_can_remove (const void *closure)
+{
+    const cairo_scaled_glyph_page_t *page = closure;
+    const cairo_scaled_font_t *scaled_font;
+
+    scaled_font = (cairo_scaled_font_t *) page->cache_entry.hash;
+    return scaled_font->cache_frozen == 0;
+}
+
+static cairo_status_t
+_cairo_scaled_font_allocate_glyph (cairo_scaled_font_t *scaled_font,
+				   cairo_scaled_glyph_t **scaled_glyph)
+{
+    cairo_scaled_glyph_page_t *page;
+    cairo_status_t status;
+
+    /* only the first page in the list may contain available slots */
+    page = scaled_font->glyph_pages;
+    if (page != NULL && page->num_glyphs < CAIRO_SCALED_GLYPH_PAGE_SIZE) {
+	*scaled_glyph = &page->glyphs[page->num_glyphs++];
+	return CAIRO_STATUS_SUCCESS;
+    }
+
+    page = malloc (sizeof (cairo_scaled_glyph_page_t));
+    if (unlikely (page == NULL))
+	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+    page->cache_entry.hash = (unsigned long) scaled_font;
+    page->cache_entry.size = 1; /* XXX occupancy weighting? */
+    page->num_glyphs = 0;
+
+    CAIRO_MUTEX_LOCK (_cairo_scaled_glyph_page_cache_mutex);
+    if (scaled_font->global_cache_frozen == FALSE) {
+	if (unlikely (cairo_scaled_glyph_page_cache == NULL)) {
+	    cairo_scaled_glyph_page_cache =
+		_cairo_cache_create (NULL,
+				     _cairo_scaled_glyph_page_can_remove,
+				     _cairo_scaled_glyph_page_destroy,
+				     MAX_GLYPH_PAGES_CACHED);
+	    if (unlikely (cairo_scaled_glyph_page_cache == NULL)) {
+		CAIRO_MUTEX_UNLOCK (_cairo_scaled_glyph_page_cache_mutex);
+		free (page);
+		return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+	    }
+	}
+
+	_cairo_cache_freeze (cairo_scaled_glyph_page_cache);
+	scaled_font->global_cache_frozen = TRUE;
+    }
+
+    status = _cairo_cache_insert (cairo_scaled_glyph_page_cache,
+				  &page->cache_entry);
+    CAIRO_MUTEX_UNLOCK (_cairo_scaled_glyph_page_cache_mutex);
+    if (unlikely (status)) {
+	free (page);
+	return status;
+    }
+
+    page->next = scaled_font->glyph_pages;
+    page->prev = NULL;
+    if (scaled_font->glyph_pages != NULL)
+	scaled_font->glyph_pages->prev = page;
+    scaled_font->glyph_pages = page;
+
+    *scaled_glyph = &page->glyphs[page->num_glyphs++];
+    return CAIRO_STATUS_SUCCESS;
+}
+
+static void
+_cairo_scaled_font_free_last_glyph (cairo_scaled_font_t *scaled_font,
+			           cairo_scaled_glyph_t *scaled_glyph)
+{
+    cairo_scaled_glyph_page_t *page;
+
+    page = scaled_font->glyph_pages;
+    assert (page != NULL && scaled_glyph == &page->glyphs[page->num_glyphs-1]);
+
+    _cairo_scaled_glyph_fini (scaled_font, scaled_glyph);
+
+    if (--page->num_glyphs == 0) {
+	_cairo_cache_remove (cairo_scaled_glyph_page_cache, &page->cache_entry);
+	assert (scaled_font->glyph_pages != page);
+    }
+}
+
 /**
  * _cairo_scaled_glyph_lookup:
  * @scaled_font: a #cairo_scaled_font_t
@@ -2529,66 +2551,40 @@ _cairo_scaled_glyph_lookup (cairo_scaled_font_t *scaled_font,
 			    cairo_scaled_glyph_info_t info,
 			    cairo_scaled_glyph_t **scaled_glyph_ret)
 {
-    cairo_status_t		status = CAIRO_STATUS_SUCCESS;
-    cairo_scaled_glyph_page_t	*page;
+    cairo_status_t		 status = CAIRO_STATUS_SUCCESS;
     cairo_scaled_glyph_t	*scaled_glyph;
-    cairo_scaled_glyph_info_t	need_info;
+    cairo_scaled_glyph_info_t	 need_info;
 
     if (unlikely (scaled_font->status))
 	return scaled_font->status;
 
-    page = scaled_font->mru_page;
-    if (page != NULL && ! CAIRO_SCALED_GLYPH_PAGE_HAS_INDEX (page, index)) {
-	CAIRO_MUTEX_LOCK (_cairo_scaled_glyph_page_cache_mutex);
-	if (! scaled_font->cache_frozen) {
-	    if (cairo_scaled_glyph_page_cache == NULL) {
-		cairo_scaled_glyph_page_cache =
-		    _cairo_cache_create (_cairo_scaled_glyph_pages_equal,
-					 _cairo_scaled_glyph_page_destroy,
-					 MAX_GLYPH_PAGES_CACHED);
-		if (unlikely (cairo_scaled_glyph_page_cache == NULL)) {
-		    status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
-		    goto BAIL;
-		}
-	    }
-
-	    _cairo_cache_freeze (cairo_scaled_glyph_page_cache);
-	    scaled_font->cache_frozen = TRUE;
-	}
-	status = _cairo_cache_insert (cairo_scaled_glyph_page_cache,
-				      &page->key.cache_entry);
-      BAIL:
-	CAIRO_MUTEX_UNLOCK (_cairo_scaled_glyph_page_cache_mutex);
-	if (unlikely (status))
-	    return _cairo_scaled_font_set_error (scaled_font, status);
-
-	page = scaled_font->mru_page = NULL;
-    }
-
-    if (page == NULL) {
-	page = _cairo_scaled_glyph_page_cache_lookup (scaled_font, index);
-	if (unlikely (page == NULL)) {
-	    return _cairo_scaled_font_set_error (scaled_font,
-						 _cairo_error (CAIRO_STATUS_NO_MEMORY));
-	}
-    }
-
-    scaled_font->mru_page = page;
-
     /*
      * Check cache for glyph
      */
-    info |= CAIRO_SCALED_GLYPH_INFO_METRICS;
-    scaled_glyph = &page->glyphs[CAIRO_SCALED_GLYPH_PAGE_INDEX (index)];
-    if (scaled_glyph->scaled_font == NULL) {
-	scaled_glyph->index = index;
-	scaled_glyph->scaled_font = scaled_font;
+    scaled_glyph = _cairo_hash_table_lookup (scaled_font->glyphs,
+					     (cairo_hash_entry_t *) &index);
+    if (scaled_glyph == NULL) {
+	status = _cairo_scaled_font_allocate_glyph (scaled_font, &scaled_glyph);
+	if (unlikely (status))
+	    goto CLEANUP;
+
+	memset (scaled_glyph, 0, sizeof (cairo_scaled_glyph_t));
+	_cairo_scaled_glyph_set_index (scaled_glyph, index);
 
 	/* ask backend to initialize metrics and shape fields */
-	status = (*scaled_font->backend->
-		  scaled_glyph_init) (scaled_font, scaled_glyph, info);
+	status =
+	    scaled_font->backend->scaled_glyph_init (scaled_font,
+						     scaled_glyph,
+						     info | CAIRO_SCALED_GLYPH_INFO_METRICS);
+	if (unlikely (status)) {
+	    _cairo_scaled_font_free_last_glyph (scaled_font, scaled_glyph);
+	    goto CLEANUP;
+	}
+
+	status = _cairo_hash_table_insert (scaled_font->glyphs,
+					   &scaled_glyph->hash_entry);
 	if (unlikely (status)) {
-	    _cairo_scaled_glyph_fini (scaled_glyph);
+	    _cairo_scaled_font_free_last_glyph (scaled_font, scaled_glyph);
 	    goto CLEANUP;
 	}
     }
@@ -2600,19 +2596,26 @@ _cairo_scaled_glyph_lookup (cairo_scaled_font_t *scaled_font,
     need_info = 0;
     if ((info & CAIRO_SCALED_GLYPH_INFO_SURFACE) != 0 &&
 	scaled_glyph->surface == NULL)
+    {
 	need_info |= CAIRO_SCALED_GLYPH_INFO_SURFACE;
+    }
 
-    if (((info & CAIRO_SCALED_GLYPH_INFO_PATH) != 0 &&
-	 scaled_glyph->path == NULL))
+    if ((info & CAIRO_SCALED_GLYPH_INFO_PATH) != 0 &&
+	scaled_glyph->path == NULL)
+    {
 	need_info |= CAIRO_SCALED_GLYPH_INFO_PATH;
+    }
 
-    if (((info & CAIRO_SCALED_GLYPH_INFO_META_SURFACE) != 0 &&
-	 scaled_glyph->meta_surface == NULL))
+    if ((info & CAIRO_SCALED_GLYPH_INFO_META_SURFACE) != 0 &&
+	scaled_glyph->meta_surface == NULL)
+    {
 	need_info |= CAIRO_SCALED_GLYPH_INFO_META_SURFACE;
+    }
 
     if (need_info) {
-	status = (*scaled_font->backend->
-		  scaled_glyph_init) (scaled_font, scaled_glyph, need_info);
+	status = scaled_font->backend->scaled_glyph_init (scaled_font,
+							  scaled_glyph,
+							  need_info);
 	if (unlikely (status))
 	    goto CLEANUP;
 
@@ -2622,19 +2625,22 @@ _cairo_scaled_glyph_lookup (cairo_scaled_font_t *scaled_font,
 	 * glyph info. */
 
 	if ((info & CAIRO_SCALED_GLYPH_INFO_SURFACE) != 0 &&
-	    scaled_glyph->surface == NULL) {
+	    scaled_glyph->surface == NULL)
+	{
 	    status = CAIRO_INT_STATUS_UNSUPPORTED;
 	    goto CLEANUP;
 	}
 
 	if ((info & CAIRO_SCALED_GLYPH_INFO_PATH) != 0 &&
-	    scaled_glyph->path == NULL) {
+	    scaled_glyph->path == NULL)
+	{
 	    status = CAIRO_INT_STATUS_UNSUPPORTED;
 	    goto CLEANUP;
 	}
 
 	if ((info & CAIRO_SCALED_GLYPH_INFO_META_SURFACE) != 0 &&
-	    scaled_glyph->meta_surface == NULL) {
+	    scaled_glyph->meta_surface == NULL)
+	{
 	    status = CAIRO_INT_STATUS_UNSUPPORTED;
 	    goto CLEANUP;
 	}
diff --git a/src/cairo-types-private.h b/src/cairo-types-private.h
index 149d894e3..0a3ec2e4f 100644
--- a/src/cairo-types-private.h
+++ b/src/cairo-types-private.h
@@ -123,9 +123,12 @@ struct _cairo_font_options {
     cairo_hint_metrics_t hint_metrics;
 };
 
+typedef cairo_bool_t (*cairo_cache_predicate_func_t) (const void *entry);
+
 struct _cairo_cache {
     cairo_hash_table_t *hash_table;
 
+    cairo_cache_predicate_func_t predicate;
     cairo_destroy_func_t entry_destroy;
 
     unsigned long max_size;
diff --git a/src/cairoint.h b/src/cairoint.h
index b550f867b..b93c4a44e 100644
--- a/src/cairoint.h
+++ b/src/cairoint.h
@@ -362,8 +362,7 @@ typedef struct _cairo_unscaled_font {
 } cairo_unscaled_font_t;
 
 typedef struct _cairo_scaled_glyph {
-    unsigned long index;
-    cairo_scaled_font_t	    *scaled_font;	/* font the glyph lives in */
+    cairo_hash_entry_t hash_entry;
 
     cairo_text_extents_t    metrics;		/* user-space metrics */
     cairo_text_extents_t    fs_metrics;		/* font-space metrics */
@@ -378,8 +377,8 @@ typedef struct _cairo_scaled_glyph {
     void		    *surface_private;	/* for the surface backend */
 } cairo_scaled_glyph_t;
 
-#define _cairo_scaled_glyph_index(g) ((g)->index)
-#define _cairo_scaled_glyph_set_index(g, i)  ((g)->index = (i))
+#define _cairo_scaled_glyph_index(g) ((g)->hash_entry.hash)
+#define _cairo_scaled_glyph_set_index(g, i)  ((g)->hash_entry.hash = (i))
 
 #include "cairo-scaled-font-private.h"