pipeline-cache: Prune old unused pipelines when the cache gets too big

Previously when a pipeline is added to the cache it would never be
removed. If the application is generating a lot of unique pipelines
this can end up effectively leaking a large number of resources
including the GL program objects. Arguably this isn't really a problem
because if the application is generating that many unique pipelines
then it is doing something wrong anyway. It also implies that it will
be recompiling shaders very often so the cache leaking will likely be
the least of the problems.

This patch makes it keep track of which pipelines in the cache are in
use. The cache now returns a struct representing the entry instead of
directly returning the pipeline. This entry contains a usage counter
which the pipeline backends can use to mark when there is a pipeline
alive that is using the cache entry. When the hash table decides that
it's a good time to prune some entries, it will make a list of all of
the pipelines that are not in use and then remove the least recently
used half of the pipelines. That way it is less likely to remove
pipelines that the application is actually regenerating often even if
they aren't in use all of the time.

When the cache is pruned the hash table makes a note of how small the
cache could be if it removed all of the unused pipelines. The hash
table starts pruning when there are more entries than twice this
minimum expected size. The idea is that if that case it hit then the
hash table is more than half full of useless pipelines so the
application is generating lots of redundant pipelines and it is a good
time to remove them.

Reviewed-by: Robert Bragg <robert@linux.intel.com>

8 files changed, 334 insertions, 87 deletions

diff --git a/cogl/cogl-pipeline-cache.c b/cogl/cogl-pipeline-cache.c
index 3a96490c..cc4e5c80 100644
--- a/cogl/cogl-pipeline-cache.c
+++ b/cogl/cogl-pipeline-cache.c
@@ -29,6 +29,8 @@
 #include "config.h"
 #endif
 
+#include <test-fixtures/test-unit.h>
+
 #include "cogl-context-private.h"
 #include "cogl-pipeline-private.h"
 #include "cogl-pipeline-cache.h"
@@ -86,7 +88,7 @@ _cogl_pipeline_cache_free (CoglPipelineCache *cache)
   g_free (cache);
 }
 
-CoglPipeline *
+CoglPipelineCacheEntry *
 _cogl_pipeline_cache_get_fragment_template (CoglPipelineCache *cache,
                                             CoglPipeline *key_pipeline)
 {
@@ -94,7 +96,7 @@ _cogl_pipeline_cache_get_fragment_template (CoglPipelineCache *cache,
                                         key_pipeline);
 }
 
-CoglPipeline *
+CoglPipelineCacheEntry *
 _cogl_pipeline_cache_get_vertex_template (CoglPipelineCache *cache,
                                           CoglPipeline *key_pipeline)
 {
@@ -102,10 +104,107 @@ _cogl_pipeline_cache_get_vertex_template (CoglPipelineCache *cache,
                                         key_pipeline);
 }
 
-CoglPipeline *
+CoglPipelineCacheEntry *
 _cogl_pipeline_cache_get_combined_template (CoglPipelineCache *cache,
                                             CoglPipeline *key_pipeline)
 {
   return _cogl_pipeline_hash_table_get (&cache->combined_hash,
                                         key_pipeline);
 }
+
+#ifdef ENABLE_UNIT_TESTS
+
+static void
+create_pipelines (CoglPipeline **pipelines,
+                  int n_pipelines)
+{
+  int i;
+
+  for (i = 0; i < n_pipelines; i++)
+    {
+      char *source = g_strdup_printf ("  cogl_color_out = "
+                                      "vec4 (%f, 0.0, 0.0, 1.0);\n",
+                                      i / 255.0f);
+      CoglSnippet *snippet =
+        cogl_snippet_new (COGL_SNIPPET_HOOK_FRAGMENT,
+                          NULL, /* declarations */
+                          source);
+
+      g_free (source);
+
+      pipelines[i] = cogl_pipeline_new (test_ctx);
+      cogl_pipeline_add_snippet (pipelines[i], snippet);
+      cogl_object_unref (snippet);
+    }
+
+  /* Test that drawing with them works. This should create the entries
+   * in the cache */
+  for (i = 0; i < n_pipelines; i++)
+    {
+      cogl_framebuffer_draw_rectangle (test_fb,
+                                       pipelines[i],
+                                       i, 0,
+                                       i + 1, 1);
+      test_utils_check_pixel_rgb (test_fb, i, 0, i, 0, 0);
+    }
+
+}
+
+UNIT_TEST (check_pipeline_pruning,
+           TEST_REQUIREMENT_GLSL, /* requirements */
+           0 /* no failure cases */)
+{
+  CoglPipeline *pipelines[18];
+  int fb_width, fb_height;
+  CoglPipelineHashTable *fragment_hash =
+    &test_ctx->pipeline_cache->fragment_hash;
+  CoglPipelineHashTable *combined_hash =
+    &test_ctx->pipeline_cache->combined_hash;
+  int i;
+
+  fb_width = cogl_framebuffer_get_width (test_fb);
+  fb_height = cogl_framebuffer_get_height (test_fb);
+
+  cogl_framebuffer_orthographic (test_fb,
+                                 0, 0,
+                                 fb_width,
+                                 fb_height,
+                                 -1,
+                                 100);
+
+  /* Create 18 unique pipelines. This should end up being more than
+   * the initial expected minimum size so it will trigger the garbage
+   * collection. However all of the pipelines will be in use so they
+   * won't be collected */
+  create_pipelines (pipelines, 18);
+
+  /* These pipelines should all have unique entries in the cache. We
+   * should have run the garbage collection once and at that point the
+   * expected minimum size would have been 17 */
+  g_assert_cmpint (g_hash_table_size (fragment_hash->table), ==, 18);
+  g_assert_cmpint (g_hash_table_size (combined_hash->table), ==, 18);
+  g_assert_cmpint (fragment_hash->expected_min_size, ==, 17);
+  g_assert_cmpint (combined_hash->expected_min_size, ==, 17);
+
+  /* Destroy the original pipelines and create some new ones. This
+   * should run the garbage collector again but this time the
+   * pipelines won't be in use so it should free some of them */
+  for (i = 0; i < 18; i++)
+    cogl_object_unref (pipelines[i]);
+
+  create_pipelines (pipelines, 18);
+
+  /* The garbage collection should have freed half of the original 18
+   * pipelines which means there should now be 18*1.5 = 27 */
+  g_assert_cmpint (g_hash_table_size (fragment_hash->table), ==, 27);
+  g_assert_cmpint (g_hash_table_size (combined_hash->table), ==, 27);
+  /* The 35th pipeline would have caused the garbage collection. At
+   * that point there would be 35-18=17 used unique pipelines. */
+  g_assert_cmpint (fragment_hash->expected_min_size, ==, 17);
+  g_assert_cmpint (combined_hash->expected_min_size, ==, 17);
+
+  for (i = 0; i < 18; i++)
+    cogl_object_unref (pipelines[i]);
+}
+
+#endif /* ENABLE_UNIT_TESTS */
diff --git a/cogl/cogl-pipeline-cache.h b/cogl/cogl-pipeline-cache.h
index 6bc15fdd..7bb31ea2 100644
--- a/cogl/cogl-pipeline-cache.h
+++ b/cogl/cogl-pipeline-cache.h
@@ -28,6 +28,15 @@
 
 typedef struct _CoglPipelineCache CoglPipelineCache;
 
+typedef struct
+{
+  CoglPipeline *pipeline;
+
+  /* Number of usages of this template. If this drops to zero then it
+   * will be a candidate for removal from the cache */
+  int usage_count;
+} CoglPipelineCacheEntry;
+
 CoglPipelineCache *
 _cogl_pipeline_cache_new (void);
 
@@ -43,7 +52,7 @@ _cogl_pipeline_cache_free (CoglPipelineCache *cache);
  * with a similar pipeline. In that case the copy itself will be
  * returned
  */
-CoglPipeline *
+CoglPipelineCacheEntry *
 _cogl_pipeline_cache_get_fragment_template (CoglPipelineCache *cache,
                                             CoglPipeline *key_pipeline);
 
@@ -56,7 +65,7 @@ _cogl_pipeline_cache_get_fragment_template (CoglPipelineCache *cache,
  * with a similar pipeline. In that case the copy itself will be
  * returned
  */
-CoglPipeline *
+CoglPipelineCacheEntry *
 _cogl_pipeline_cache_get_vertex_template (CoglPipelineCache *cache,
                                           CoglPipeline *key_pipeline);
 
@@ -70,7 +79,7 @@ _cogl_pipeline_cache_get_vertex_template (CoglPipelineCache *cache,
  * with a similar pipeline. In that case the copy itself will be
  * returned
  */
-CoglPipeline *
+CoglPipelineCacheEntry *
 _cogl_pipeline_cache_get_combined_template (CoglPipelineCache *cache,
                                             CoglPipeline *key_pipeline);
 
diff --git a/cogl/cogl-pipeline-hash-table.c b/cogl/cogl-pipeline-hash-table.c
index 8921efc5..84c5672c 100644
--- a/cogl/cogl-pipeline-hash-table.c
+++ b/cogl/cogl-pipeline-hash-table.c
@@ -32,11 +32,11 @@
 #include "cogl-context-private.h"
 #include "cogl-pipeline-private.h"
 #include "cogl-pipeline-hash-table.h"
+#include "cogl-pipeline-cache.h"
 
 typedef struct
 {
-  /* The template pipeline */
-  CoglPipeline *pipeline;
+  CoglPipelineCacheEntry parent;
 
   /* Calculating the hash is a little bit expensive for pipelines so
    * we don't want to do it repeatedly for entries that are already in
@@ -49,6 +49,10 @@ typedef struct
    * store the pointer in every hash table entry. We will use this
    * entry as both the key and the value */
   CoglPipelineHashTable *hash;
+
+  /* The number of unique pipelines that had been created when this
+   * pipeline was last accessed */
+  int age;
 } CoglPipelineHashTableEntry;
 
 static void
@@ -56,7 +60,7 @@ value_destroy_cb (void *value)
 {
   CoglPipelineHashTableEntry *entry = value;
 
-  cogl_object_unref (entry->pipeline);
+  cogl_object_unref (entry->parent.pipeline);
 
   g_slice_free (CoglPipelineHashTableEntry, entry);
 }
@@ -77,8 +81,8 @@ entry_equal (const void *a,
   const CoglPipelineHashTableEntry *entry_b = b;
   const CoglPipelineHashTable *hash = entry_a->hash;
 
-  return _cogl_pipeline_equal (entry_a->pipeline,
-                               entry_b->pipeline,
+  return _cogl_pipeline_equal (entry_a->parent.pipeline,
+                               entry_b->parent.pipeline,
                                hash->main_state,
                                hash->layer_state,
                                0);
@@ -94,6 +98,8 @@ _cogl_pipeline_hash_table_init (CoglPipelineHashTable *hash,
   hash->debug_string = debug_string;
   hash->main_state = main_state;
   hash->layer_state = layer_state;
+  /* We'll only start pruning once we get to 16 unique pipelines */
+  hash->expected_min_size = 8;
   hash->table = g_hash_table_new_full (entry_hash,
                                        entry_equal,
                                        NULL, /* key destroy */
@@ -106,7 +112,64 @@ _cogl_pipeline_hash_table_destroy (CoglPipelineHashTable *hash)
   g_hash_table_destroy (hash->table);
 }
 
-CoglPipeline *
+static void
+collect_prunable_entries_cb (void *key,
+                             void *value,
+                             void *user_data)
+{
+  GQueue *entries = user_data;
+  CoglPipelineCacheEntry *entry = value;
+
+  if (entry->usage_count == 0)
+    g_queue_push_tail (entries, entry);
+}
+
+static int
+compare_pipeline_age_cb (const void *a,
+                         const void *b)
+{
+  const CoglPipelineHashTableEntry *ae = a;
+  const CoglPipelineHashTableEntry *be = b;
+
+  return be->age - ae->age;
+}
+
+static void
+prune_old_pipelines (CoglPipelineHashTable *hash)
+{
+  GQueue entries;
+  GList *l;
+  int i;
+
+  /* Collect all of the prunable entries into a GQueue */
+  g_queue_init (&entries);
+  g_hash_table_foreach (hash->table,
+                        collect_prunable_entries_cb,
+                        &entries);
+
+  /* Sort the entries by increasing order of age */
+  entries.head = g_list_sort (entries.head, compare_pipeline_age_cb);
+
+  /* The +1 is to include the pipeline that we're about to add */
+  hash->expected_min_size = (g_hash_table_size (hash->table) -
+                             entries.length +
+                             1);
+
+  /* Remove oldest half of the prunable pipelines. We still want to
+   * keep some of the prunable entries that are recently used because
+   * it's not unlikely that the application will recreate the same
+   * pipeline */
+  for (l = entries.head, i = 0; i < entries.length / 2; l = l->next, i++)
+    {
+      CoglPipelineCacheEntry *entry = l->data;
+
+      g_hash_table_remove (hash->table, entry);
+    }
+
+  g_list_free (entries.head);
+}
+
+CoglPipelineCacheEntry *
 _cogl_pipeline_hash_table_get (CoglPipelineHashTable *hash,
                                CoglPipeline *key_pipeline)
 {
@@ -114,7 +177,7 @@ _cogl_pipeline_hash_table_get (CoglPipelineHashTable *hash,
   CoglPipelineHashTableEntry *entry;
   unsigned int copy_state;
 
-  dummy_entry.pipeline = key_pipeline;
+  dummy_entry.parent.pipeline = key_pipeline;
   dummy_entry.hash = hash;
   dummy_entry.hash_value = _cogl_pipeline_hash (key_pipeline,
                                                 hash->main_state,
@@ -123,16 +186,27 @@ _cogl_pipeline_hash_table_get (CoglPipelineHashTable *hash,
   entry = g_hash_table_lookup (hash->table, &dummy_entry);
 
   if (entry)
-    return entry->pipeline;
+    {
+      entry->age = hash->n_unique_pipelines;
+      return &entry->parent;
+    }
 
   if (hash->n_unique_pipelines == 50)
     g_warning ("Over 50 separate %s have been generated which is very "
                "unusual, so something is probably wrong!\n",
                hash->debug_string);
 
+  /* If we are going to have more than twice the expected minimum
+   * number of pipelines in the hash then we'll try pruning and update
+   * the minimum */
+  if (g_hash_table_size (hash->table) >= hash->expected_min_size * 2)
+    prune_old_pipelines (hash);
+
   entry = g_slice_new (CoglPipelineHashTableEntry);
+  entry->parent.usage_count = 0;
   entry->hash = hash;
   entry->hash_value = dummy_entry.hash_value;
+  entry->age = hash->n_unique_pipelines;
 
   copy_state = hash->main_state;
   if (hash->layer_state)
@@ -141,13 +215,13 @@ _cogl_pipeline_hash_table_get (CoglPipelineHashTable *hash,
   /* Create a new pipeline that is a child of the root pipeline
    * instead of a normal copy so that the template pipeline won't hold
    * a reference to the original pipeline */
-  entry->pipeline = _cogl_pipeline_deep_copy (key_pipeline,
-                                              copy_state,
-                                              hash->layer_state);
+  entry->parent.pipeline = _cogl_pipeline_deep_copy (key_pipeline,
+                                                     copy_state,
+                                                     hash->layer_state);
 
   g_hash_table_insert (hash->table, entry, entry);
 
   hash->n_unique_pipelines++;
 
-  return entry->pipeline;
+  return &entry->parent;
 }
diff --git a/cogl/cogl-pipeline-hash-table.h b/cogl/cogl-pipeline-hash-table.h
index 1b0a0d93..0f3d37c1 100644
--- a/cogl/cogl-pipeline-hash-table.h
+++ b/cogl/cogl-pipeline-hash-table.h
@@ -24,7 +24,7 @@
 #ifndef __COGL_PIPELINE_HASH_H__
 #define __COGL_PIPELINE_HASH_H__
 
-#include "cogl-pipeline.h"
+#include "cogl-pipeline-cache.h"
 
 typedef struct
 {
@@ -34,6 +34,11 @@ typedef struct
    * generated */
   int n_unique_pipelines;
 
+  /* This is the expected minimum size we could prune the hash table
+   * to if we were to remove all pipelines that are not in use. This
+   * is only updated after we prune the table */
+  int expected_min_size;
+
   /* String that will be used to describe the usage of this hash table
    * in the debug warning when too many pipelines are generated. This
    * must be a static string because it won't be copied or freed */
@@ -62,7 +67,7 @@ _cogl_pipeline_hash_table_destroy (CoglPipelineHashTable *hash);
  * it will be used next time the function is called with a similar
  * pipeline. In that case the copy itself will be returned
  */
-CoglPipeline *
+CoglPipelineCacheEntry *
 _cogl_pipeline_hash_table_get (CoglPipelineHashTable *hash,
                                CoglPipeline *key_pipeline);
 
diff --git a/cogl/driver/gl/cogl-pipeline-fragend-glsl.c b/cogl/driver/gl/cogl-pipeline-fragend-glsl.c
index 687a8268..9d088ebe 100644
--- a/cogl/driver/gl/cogl-pipeline-fragend-glsl.c
+++ b/cogl/driver/gl/cogl-pipeline-fragend-glsl.c
@@ -93,6 +93,8 @@ typedef struct
      layer we'll remove it from the list so we don't generate it
      again */
   CoglList layers;
+
+  CoglPipelineCacheEntry *cache_entry;
 } CoglPipelineShaderState;
 
 static CoglUserDataKey shader_state_key;
@@ -102,13 +104,15 @@ ensure_layer_generated (CoglPipeline *pipeline,
                         int layer_num);
 
 static CoglPipelineShaderState *
-shader_state_new (int n_layers)
+shader_state_new (int n_layers,
+                  CoglPipelineCacheEntry *cache_entry)
 {
   CoglPipelineShaderState *shader_state;
 
   shader_state = g_slice_new0 (CoglPipelineShaderState);
   shader_state->ref_count = 1;
   shader_state->unit_state = g_new0 (UnitState, n_layers);
+  shader_state->cache_entry = cache_entry;
 
   return shader_state;
 }
@@ -120,12 +124,17 @@ get_shader_state (CoglPipeline *pipeline)
 }
 
 static void
-destroy_shader_state (void *user_data)
+destroy_shader_state (void *user_data,
+                      void *instance)
 {
   CoglPipelineShaderState *shader_state = user_data;
 
   _COGL_GET_CONTEXT (ctx, NO_RETVAL);
 
+  if (shader_state->cache_entry &&
+      shader_state->cache_entry->pipeline != instance)
+    shader_state->cache_entry->usage_count--;
+
   if (--shader_state->ref_count == 0)
     {
       if (shader_state->gl_shader)
@@ -140,10 +149,21 @@ destroy_shader_state (void *user_data)
 static void
 set_shader_state (CoglPipeline *pipeline, CoglPipelineShaderState *shader_state)
 {
-  cogl_object_set_user_data (COGL_OBJECT (pipeline),
-                             &shader_state_key,
-                             shader_state,
-                             destroy_shader_state);
+  if (shader_state)
+    {
+      shader_state->ref_count++;
+
+      /* If we're not setting the state on the template pipeline then
+       * mark it as a usage of the pipeline cache entry */
+      if (shader_state->cache_entry &&
+          shader_state->cache_entry->pipeline != pipeline)
+        shader_state->cache_entry->usage_count++;
+    }
+
+  _cogl_object_set_user_data (COGL_OBJECT (pipeline),
+                              &shader_state_key,
+                              shader_state,
+                              destroy_shader_state);
 }
 
 static void
@@ -260,7 +280,7 @@ _cogl_pipeline_fragend_glsl_start (CoglPipeline *pipeline,
 {
   CoglPipelineShaderState *shader_state;
   CoglPipeline *authority;
-  CoglPipeline *template_pipeline = NULL;
+  CoglPipelineCacheEntry *cache_entry = NULL;
   int i;
 
   _COGL_GET_CONTEXT (ctx, NO_RETVAL);
@@ -296,35 +316,31 @@ _cogl_pipeline_fragend_glsl_start (CoglPipeline *pipeline,
           if (G_LIKELY (!(COGL_DEBUG_ENABLED
                           (COGL_DEBUG_DISABLE_PROGRAM_CACHES))))
             {
-              template_pipeline =
+              cache_entry =
                 _cogl_pipeline_cache_get_fragment_template (ctx->pipeline_cache,
                                                             authority);
 
-              shader_state = get_shader_state (template_pipeline);
+              shader_state = get_shader_state (cache_entry->pipeline);
             }
 
           if (shader_state)
             shader_state->ref_count++;
           else
-            shader_state = shader_state_new (n_layers);
+            shader_state = shader_state_new (n_layers, cache_entry);
 
           set_shader_state (authority, shader_state);
 
-          if (template_pipeline)
-            {
-              shader_state->ref_count++;
-              set_shader_state (template_pipeline, shader_state);
-            }
+          shader_state->ref_count--;
+
+          if (cache_entry)
+            set_shader_state (cache_entry->pipeline, shader_state);
         }
 
       /* If the pipeline isn't actually its own glsl-authority
        * then take a reference to the program state associated
        * with the glsl-authority... */
       if (authority != pipeline)
-        {
-          shader_state->ref_count++;
-          set_shader_state (pipeline, shader_state);
-        }
+        set_shader_state (pipeline, shader_state);
     }
 
   if (shader_state->gl_shader)
diff --git a/cogl/driver/gl/cogl-pipeline-progend-glsl.c b/cogl/driver/gl/cogl-pipeline-progend-glsl.c
index c4ca3859..9f050be8 100644
--- a/cogl/driver/gl/cogl-pipeline-progend-glsl.c
+++ b/cogl/driver/gl/cogl-pipeline-progend-glsl.c
@@ -131,6 +131,8 @@ typedef struct
   int flushed_flip_state;
 
   UnitState *unit_state;
+
+  CoglPipelineCacheEntry *cache_entry;
 } CoglPipelineProgramState;
 
 static CoglUserDataKey program_state_key;
@@ -220,7 +222,8 @@ clear_flushed_matrix_stacks (CoglPipelineProgramState *program_state)
 }
 
 static CoglPipelineProgramState *
-program_state_new (int n_layers)
+program_state_new (int n_layers,
+                   CoglPipelineCacheEntry *cache_entry)
 {
   CoglPipelineProgramState *program_state;
 
@@ -230,6 +233,7 @@ program_state_new (int n_layers)
   program_state->unit_state = g_new (UnitState, n_layers);
   program_state->uniform_locations = NULL;
   program_state->attribute_locations = NULL;
+  program_state->cache_entry = cache_entry;
   _cogl_matrix_entry_cache_init (&program_state->modelview_cache);
   _cogl_matrix_entry_cache_init (&program_state->projection_cache);
 
@@ -251,6 +255,10 @@ destroy_program_state (void *user_data,
   if (program_state->last_used_for_pipeline == instance)
     program_state->last_used_for_pipeline = NULL;
 
+  if (program_state->cache_entry &&
+      program_state->cache_entry->pipeline != instance)
+    program_state->cache_entry->usage_count--;
+
   if (--program_state->ref_count == 0)
     {
       clear_attribute_cache (program_state);
@@ -274,6 +282,17 @@ static void
 set_program_state (CoglPipeline *pipeline,
                   CoglPipelineProgramState *program_state)
 {
+  if (program_state)
+    {
+      program_state->ref_count++;
+
+      /* If we're not setting the state on the template pipeline then
+       * mark it as a usage of the pipeline cache entry */
+      if (program_state->cache_entry &&
+          program_state->cache_entry->pipeline != pipeline)
+        program_state->cache_entry->usage_count++;
+    }
+
   _cogl_object_set_user_data (COGL_OBJECT (pipeline),
                               &program_state_key,
                               program_state,
@@ -602,7 +621,7 @@ _cogl_pipeline_progend_glsl_end (CoglPipeline *pipeline,
   GLuint gl_program;
   CoglBool program_changed = FALSE;
   UpdateUniformsState state;
-  CoglPipeline *template_pipeline = NULL;
+  CoglPipelineCacheEntry *cache_entry = NULL;
 
   _COGL_GET_CONTEXT (ctx, NO_RETVAL);
 
@@ -632,33 +651,30 @@ _cogl_pipeline_progend_glsl_end (CoglPipeline *pipeline,
           if (G_LIKELY (!(COGL_DEBUG_ENABLED
                           (COGL_DEBUG_DISABLE_PROGRAM_CACHES))))
             {
-              template_pipeline =
+              cache_entry =
                 _cogl_pipeline_cache_get_combined_template (ctx->pipeline_cache,
                                                             authority);
 
-              program_state = get_program_state (template_pipeline);
+              program_state = get_program_state (cache_entry->pipeline);
             }
 
           if (program_state)
             program_state->ref_count++;
           else
             program_state
-              = program_state_new (cogl_pipeline_get_n_layers (authority));
+              = program_state_new (cogl_pipeline_get_n_layers (authority),
+                                   cache_entry);
 
           set_program_state (authority, program_state);
 
-          if (template_pipeline)
-            {
-              program_state->ref_count++;
-              set_program_state (template_pipeline, program_state);
-            }
+          program_state->ref_count--;
+
+          if (cache_entry)
+            set_program_state (cache_entry->pipeline, program_state);
         }
 
       if (authority != pipeline)
-        {
-          program_state->ref_count++;
-          set_program_state (pipeline, program_state);
-        }
+        set_program_state (pipeline, program_state);
     }
 
   if (program_state->program == 0)
diff --git a/cogl/driver/gl/cogl-pipeline-vertend-glsl.c b/cogl/driver/gl/cogl-pipeline-vertend-glsl.c
index 4f5587dd..e2a7d001 100644
--- a/cogl/driver/gl/cogl-pipeline-vertend-glsl.c
+++ b/cogl/driver/gl/cogl-pipeline-vertend-glsl.c
@@ -55,17 +55,19 @@ typedef struct
   GLuint gl_shader;
   GString *header, *source;
 
+  CoglPipelineCacheEntry *cache_entry;
 } CoglPipelineShaderState;
 
 static CoglUserDataKey shader_state_key;
 
 static CoglPipelineShaderState *
-shader_state_new (void)
+shader_state_new (CoglPipelineCacheEntry *cache_entry)
 {
   CoglPipelineShaderState *shader_state;
 
   shader_state = g_slice_new0 (CoglPipelineShaderState);
   shader_state->ref_count = 1;
+  shader_state->cache_entry = cache_entry;
 
   return shader_state;
 }
@@ -77,12 +79,17 @@ get_shader_state (CoglPipeline *pipeline)
 }
 
 static void
-destroy_shader_state (void *user_data)
+destroy_shader_state (void *user_data,
+                      void *instance)
 {
   CoglPipelineShaderState *shader_state = user_data;
 
   _COGL_GET_CONTEXT (ctx, NO_RETVAL);
 
+  if (shader_state->cache_entry &&
+      shader_state->cache_entry->pipeline != instance)
+    shader_state->cache_entry->usage_count--;
+
   if (--shader_state->ref_count == 0)
     {
       if (shader_state->gl_shader)
@@ -96,10 +103,21 @@ static void
 set_shader_state (CoglPipeline *pipeline,
                   CoglPipelineShaderState *shader_state)
 {
-  cogl_object_set_user_data (COGL_OBJECT (pipeline),
-                             &shader_state_key,
-                             shader_state,
-                             destroy_shader_state);
+  if (shader_state)
+    {
+      shader_state->ref_count++;
+
+      /* If we're not setting the state on the template pipeline then
+       * mark it as a usage of the pipeline cache entry */
+      if (shader_state->cache_entry &&
+          shader_state->cache_entry->pipeline != pipeline)
+        shader_state->cache_entry->usage_count++;
+    }
+
+  _cogl_object_set_user_data (COGL_OBJECT (pipeline),
+                              &shader_state_key,
+                              shader_state,
+                              destroy_shader_state);
 }
 
 static void
@@ -200,7 +218,7 @@ _cogl_pipeline_vertend_glsl_start (CoglPipeline *pipeline,
                                    unsigned long pipelines_difference)
 {
   CoglPipelineShaderState *shader_state;
-  CoglPipeline *template_pipeline = NULL;
+  CoglPipelineCacheEntry *cache_entry = NULL;
 
   _COGL_GET_CONTEXT (ctx, NO_RETVAL);
 
@@ -229,32 +247,28 @@ _cogl_pipeline_vertend_glsl_start (CoglPipeline *pipeline,
           if (G_LIKELY (!(COGL_DEBUG_ENABLED
                           (COGL_DEBUG_DISABLE_PROGRAM_CACHES))))
             {
-              template_pipeline =
+              cache_entry =
                 _cogl_pipeline_cache_get_vertex_template (ctx->pipeline_cache,
                                                           authority);
 
-              shader_state = get_shader_state (template_pipeline);
+              shader_state = get_shader_state (cache_entry->pipeline);
             }
 
           if (shader_state)
             shader_state->ref_count++;
           else
-            shader_state = shader_state_new ();
+            shader_state = shader_state_new (cache_entry);
 
           set_shader_state (authority, shader_state);
 
-          if (template_pipeline)
-            {
-              shader_state->ref_count++;
-              set_shader_state (template_pipeline, shader_state);
-            }
+          shader_state->ref_count--;
+
+          if (cache_entry)
+            set_shader_state (cache_entry->pipeline, shader_state);
         }
 
       if (authority != pipeline)
-        {
-          shader_state->ref_count++;
-          set_shader_state (pipeline, shader_state);
-        }
+        set_shader_state (pipeline, shader_state);
     }
 
   if (shader_state->gl_shader)
diff --git a/cogl/driver/gl/gl/cogl-pipeline-fragend-arbfp.c b/cogl/driver/gl/gl/cogl-pipeline-fragend-arbfp.c
index 1325fd9f..20a11a09 100644
--- a/cogl/driver/gl/gl/cogl-pipeline-fragend-arbfp.c
+++ b/cogl/driver/gl/gl/cogl-pipeline-fragend-arbfp.c
@@ -80,18 +80,22 @@ typedef struct
   /* We need to track the last pipeline that an ARBfp program was used
    * with so know if we need to update any program.local parameters. */
   CoglPipeline *last_used_for_pipeline;
+
+  CoglPipelineCacheEntry *cache_entry;
 } CoglPipelineShaderState;
 
 static CoglUserDataKey shader_state_key;
 
 static CoglPipelineShaderState *
-shader_state_new (int n_layers)
+shader_state_new (int n_layers,
+                  CoglPipelineCacheEntry *cache_entry)
 {
   CoglPipelineShaderState *shader_state;
 
   shader_state = g_slice_new0 (CoglPipelineShaderState);
   shader_state->ref_count = 1;
   shader_state->unit_state = g_new0 (UnitState, n_layers);
+  shader_state->cache_entry = cache_entry;
 
   return shader_state;
 }
@@ -117,6 +121,10 @@ destroy_shader_state (void *user_data,
   if (shader_state->last_used_for_pipeline == instance)
     shader_state->last_used_for_pipeline = NULL;
 
+  if (shader_state->cache_entry &&
+      shader_state->cache_entry->pipeline != instance)
+    shader_state->cache_entry->usage_count--;
+
   if (--shader_state->ref_count == 0)
     {
       if (shader_state->gl_program)
@@ -134,6 +142,17 @@ destroy_shader_state (void *user_data,
 static void
 set_shader_state (CoglPipeline *pipeline, CoglPipelineShaderState *shader_state)
 {
+  if (shader_state)
+    {
+      shader_state->ref_count++;
+
+      /* If we're not setting the state on the template pipeline then
+       * mark it as a usage of the pipeline cache entry */
+      if (shader_state->cache_entry &&
+          shader_state->cache_entry->pipeline != pipeline)
+        shader_state->cache_entry->usage_count++;
+    }
+
   _cogl_object_set_user_data (COGL_OBJECT (pipeline),
                               &shader_state_key,
                               shader_state,
@@ -156,7 +175,7 @@ _cogl_pipeline_fragend_arbfp_start (CoglPipeline *pipeline,
 {
   CoglPipelineShaderState *shader_state;
   CoglPipeline *authority;
-  CoglPipeline *template_pipeline = NULL;
+  CoglPipelineCacheEntry *cache_entry = NULL;
 
   _COGL_GET_CONTEXT (ctx, NO_RETVAL);
 
@@ -187,7 +206,6 @@ _cogl_pipeline_fragend_arbfp_start (CoglPipeline *pipeline,
       /* If we are going to share our program state with an arbfp-authority
        * then add a reference to the program state associated with that
        * arbfp-authority... */
-      shader_state->ref_count++;
       set_shader_state (pipeline, shader_state);
       return;
     }
@@ -197,11 +215,11 @@ _cogl_pipeline_fragend_arbfp_start (CoglPipeline *pipeline,
    * program in the pipeline_cache. */
   if (G_LIKELY (!(COGL_DEBUG_ENABLED (COGL_DEBUG_DISABLE_PROGRAM_CACHES))))
     {
-      template_pipeline =
+      cache_entry =
         _cogl_pipeline_cache_get_fragment_template (ctx->pipeline_cache,
                                                     authority);
 
-      shader_state = get_shader_state (template_pipeline);
+      shader_state = get_shader_state (cache_entry->pipeline);
 
       if (shader_state)
         shader_state->ref_count++;
@@ -211,7 +229,7 @@ _cogl_pipeline_fragend_arbfp_start (CoglPipeline *pipeline,
      a new one */
   if (shader_state == NULL)
     {
-      shader_state = shader_state_new (n_layers);
+      shader_state = shader_state_new (n_layers, cache_entry);
 
       /* We reuse a single grow-only GString for code-gen */
       g_string_set_size (ctx->codegen_source_buffer, 0);
@@ -228,22 +246,18 @@ _cogl_pipeline_fragend_arbfp_start (CoglPipeline *pipeline,
 
   set_shader_state (pipeline, shader_state);
 
+  shader_state->ref_count--;
+
   /* Since we have already resolved the arbfp-authority at this point
    * we might as well also associate any program we find from the cache
    * with the authority too... */
   if (authority != pipeline)
-    {
-      shader_state->ref_count++;
-      set_shader_state (authority, shader_state);
-    }
+    set_shader_state (authority, shader_state);
 
   /* If we found a template then we'll attach it to that too so that
      next time a similar pipeline is used it can use the same state */
-  if (template_pipeline)
-    {
-      shader_state->ref_count++;
-      set_shader_state (template_pipeline, shader_state);
-    }
+  if (cache_entry)
+    set_shader_state (cache_entry->pipeline, shader_state);
 }
 
 static const char *