cache: switch to gradual cache clearing

Advantages over the old algorithm consist of the following.
 * There are no glitches due to full cache clearing.
   Items are arranged into linked list ordered by time of last use.
   Only the oldest items get deleted at the clearing event.
 * Each item now keeps track of number of references.
   Referenced cache values are immune to clearing.
 * Reduced amount of total cache memory for the same performance.
 * Reduced number of memory allocations per cache item.

8 files changed, 316 insertions, 198 deletions

diff --git a/libass/ass_cache.c b/libass/ass_cache.c
index d8c561e..44aaee9 100644
--- a/libass/ass_cache.c
+++ b/libass/ass_cache.c
@@ -65,8 +65,7 @@ static unsigned font_compare(void *key1, void *key2, size_t key_size)
 
 static void font_destruct(void *key, void *value)
 {
-    ass_font_free(value);
-    free(key);
+    ass_font_clear(value);
 }
 
 // bitmap cache
@@ -78,10 +77,10 @@ static void bitmap_destruct(void *key, void *value)
         ass_free_bitmap(v->bm);
     if (v->bm_o)
         ass_free_bitmap(v->bm_o);
-    if (k->type == BITMAP_CLIP)
-        free(k->u.clip.text);
-    free(key);
-    free(value);
+    switch (k->type) {
+        case BITMAP_OUTLINE: ass_cache_dec_ref(k->u.outline.outline); break;
+        case BITMAP_CLIP: free(k->u.clip.text); break;
+    }
 }
 
 static size_t bitmap_size(void *value, size_t value_size)
@@ -105,7 +104,7 @@ static unsigned bitmap_hash(void *key, size_t key_size)
     }
 }
 
-static unsigned bitmap_compare (void *a, void *b, size_t key_size)
+static unsigned bitmap_compare(void *a, void *b, size_t key_size)
 {
     BitmapHashKey *ak = a;
     BitmapHashKey *bk = b;
@@ -128,9 +127,9 @@ static void composite_destruct(void *key, void *value)
         ass_free_bitmap(v->bm_o);
     if (v->bm_s)
         ass_free_bitmap(v->bm_s);
+    for (size_t i = 0; i < k->bitmap_count; i++)
+        ass_cache_dec_ref(k->bitmaps[i].image);
     free(k->bitmaps);
-    free(key);
-    free(value);
 }
 
 static size_t composite_size(void *value, size_t value_size)
@@ -150,7 +149,7 @@ static unsigned composite_hash(void *key, size_t key_size)
 {
     CompositeHashKey *k = key;
     unsigned hval = filter_hash(&k->filter, key_size);
-    for (size_t i = 0; i < k->bitmap_count; ++i) {
+    for (size_t i = 0; i < k->bitmap_count; i++) {
         hval = fnv_32a_buf(&k->bitmaps[i].image, sizeof(k->bitmaps[i].image), hval);
         hval = fnv_32a_buf(&k->bitmaps[i].x, sizeof(k->bitmaps[i].x), hval);
         hval = fnv_32a_buf(&k->bitmaps[i].y, sizeof(k->bitmaps[i].y), hval);
@@ -164,7 +163,7 @@ static unsigned composite_compare(void *a, void *b, size_t key_size)
     CompositeHashKey *bk = b;
     if (ak->bitmap_count != bk->bitmap_count)
         return 0;
-    for (size_t i = 0; i < ak->bitmap_count; ++i) {
+    for (size_t i = 0; i < ak->bitmap_count; i++) {
         if (ak->bitmaps[i].image != bk->bitmaps[i].image ||
             ak->bitmaps[i].x != bk->bitmaps[i].x ||
             ak->bitmaps[i].y != bk->bitmaps[i].y)
@@ -205,24 +204,34 @@ static void outline_destruct(void *key, void *value)
     free(v->outline);
     outline_free(v->border);
     free(v->border);
-    if (k->type == OUTLINE_DRAWING)
-        free(k->u.drawing.text);
-    free(key);
-    free(value);
+    switch (k->type) {
+        case OUTLINE_GLYPH: ass_cache_dec_ref(k->u.glyph.font); break;
+        case OUTLINE_DRAWING: free(k->u.drawing.text); break;
+    }
+}
+
+
+// glyph metric cache
+static void glyph_metric_destruct(void *key, void *value)
+{
+    GlyphMetricsHashKey *k = key;
+    ass_cache_dec_ref(k->font);
 }
 
 
 
 // Cache data
 typedef struct cache_item {
-    void *key;
-    void *value;
-    struct cache_item *next;
+    struct cache *cache;
+    struct cache_item *next, **prev;
+    struct cache_item *queue_next, **queue_prev;
+    size_t size, ref_count;
 } CacheItem;
 
 struct cache {
     unsigned buckets;
     CacheItem **map;
+    CacheItem *queue_first, **queue_last;
 
     HashFunction hash_func;
     ItemSize size_func;
@@ -237,6 +246,19 @@ struct cache {
     unsigned items;
 };
 
+#define CACHE_ALIGN 8
+#define CACHE_ITEM_SIZE ((sizeof(CacheItem) + (CACHE_ALIGN - 1)) & ~(CACHE_ALIGN - 1))
+
+static inline size_t align_cache(size_t size)
+{
+    return (size + (CACHE_ALIGN - 1)) & ~(CACHE_ALIGN - 1);
+}
+
+static inline CacheItem *value_to_item(void *value)
+{
+    return (CacheItem *) ((char *) value - CACHE_ITEM_SIZE);
+}
+
 // Hash for a simple (single value or array) type
 static unsigned hash_simple(void *key, size_t key_size)
 {
@@ -252,8 +274,6 @@ static unsigned compare_simple(void *a, void *b, size_t key_size)
 // Default destructor
 static void destruct_simple(void *key, void *value)
 {
-    free(key);
-    free(value);
 }
 
 
@@ -266,6 +286,7 @@ Cache *ass_cache_create(HashFunction hash_func, HashCompare compare_func,
     if (!cache)
         return NULL;
     cache->buckets = 0xFFFF;
+    cache->queue_last = &cache->queue_first;
     cache->hash_func = hash_simple;
     cache->compare_func = compare_simple;
     cache->destruct_func = destruct_simple;
@@ -287,73 +308,157 @@ Cache *ass_cache_create(HashFunction hash_func, HashCompare compare_func,
     return cache;
 }
 
-void *ass_cache_put(Cache *cache, void *key, void *value)
+bool ass_cache_get(Cache *cache, void *key, void *value_ptr)
 {
+    char **value = (char **) value_ptr;
+    size_t key_offs = CACHE_ITEM_SIZE + align_cache(cache->value_size);
     unsigned bucket = cache->hash_func(key, cache->key_size) % cache->buckets;
-    CacheItem **bucketptr = &cache->map[bucket];
+    CacheItem *item = cache->map[bucket];
+    while (item) {
+        if (cache->compare_func(key, (char *) item + key_offs, cache->key_size)) {
+            assert(item->size);
+            if (!item->queue_prev || item->queue_next) {
+                if (item->queue_prev) {
+                    item->queue_next->queue_prev = item->queue_prev;
+                    *item->queue_prev = item->queue_next;
+                }
+                *cache->queue_last = item;
+                item->queue_prev = cache->queue_last;
+                cache->queue_last = &item->queue_next;
+                item->queue_next = NULL;
+            }
+            cache->hits++;
+            *value = (char *) item + CACHE_ITEM_SIZE;
+            return true;
+        }
+        item = item->next;
+    }
+    cache->misses++;
 
-    CacheItem *item = calloc(1, sizeof(CacheItem));
-    if (!item)
-        return NULL;
-    item->key = malloc(cache->key_size);
-    item->value = malloc(cache->value_size);
-    if (!item->key || !item->value) {
-        free(item->key);
-        free(item->value);
-        free(item);
-        return NULL;
+    item = malloc(key_offs + cache->key_size);
+    if (!item) {
+        *value = NULL;
+        return 0;
     }
-    memcpy(item->key, key, cache->key_size);
-    memcpy(item->value, value, cache->value_size);
+    item->size = 0;
+    item->cache = cache;
+    *value = (char *) item + CACHE_ITEM_SIZE;
+    memcpy((char *) item + key_offs, key, cache->key_size);
 
+    CacheItem **bucketptr = &cache->map[bucket];
+    if (*bucketptr)
+        (*bucketptr)->prev = &item->next;
+    item->prev = bucketptr;
     item->next = *bucketptr;
     *bucketptr = item;
 
+    *cache->queue_last = item;
+    item->queue_prev = cache->queue_last;
+    cache->queue_last = &item->queue_next;
+    item->queue_next = NULL;
+
+    item->ref_count = 0;
+    return false;
+}
+
+void *ass_cache_get_key(void *value)
+{
+    CacheItem *item = value_to_item(value);
+    assert(!item->size);
+    return (char *) value + align_cache(item->cache->value_size);
+}
+
+void ass_cache_commit(void *value)
+{
+    CacheItem *item = value_to_item(value);
+    assert(!item->size);
+    Cache *cache = item->cache;
+
     cache->items++;
     if (cache->size_func)
-        cache->cache_size += cache->size_func(value, cache->value_size);
+        item->size = cache->size_func(value, cache->value_size);
     else
-        cache->cache_size++;
+        item->size = 1;
+    cache->cache_size += item->size;
+}
+
+void ass_cache_cancel(void *value)
+{
+    CacheItem *item = value_to_item(value);
+    assert(!item->size);
 
-    return item->value;
+    if (item->queue_next)
+        item->queue_next->queue_prev = item->queue_prev;
+    *item->queue_prev = item->queue_next;
+
+    if (item->next)
+        item->next->prev = item->prev;
+    *item->prev = item->next;
+    free(item);
 }
 
-void *ass_cache_get(Cache *cache, void *key)
+static inline void destroy_item(Cache *cache, CacheItem *item)
 {
-    unsigned bucket = cache->hash_func(key, cache->key_size) % cache->buckets;
-    CacheItem *item = cache->map[bucket];
-    while (item) {
-        if (cache->compare_func(key, item->key, cache->key_size)) {
-            cache->hits++;
-            return item->value;
-        }
-        item = item->next;
-    }
-    cache->misses++;
-    return NULL;
+    assert(item->cache == cache);
+    char *value = (char *) item + CACHE_ITEM_SIZE;
+    cache->destruct_func(value + align_cache(cache->value_size), value);
+    free(item);
 }
 
-int ass_cache_empty(Cache *cache, size_t max_size)
+void ass_cache_inc_ref(void *value)
 {
-    int i;
+    CacheItem *item = value_to_item(value);
+    assert(item->size);
+    item->ref_count++;
+}
 
-    if (cache->cache_size < max_size)
-        return 0;
+void ass_cache_dec_ref(void *value)
+{
+    CacheItem *item = value_to_item(value);
+    assert(item->size && item->ref_count);
 
-    for (i = 0; i < cache->buckets; i++) {
-        CacheItem *item = cache->map[i];
-        while (item) {
-            CacheItem *next = item->next;
-            cache->destruct_func(item->key, item->value);
-            free(item);
-            item = next;
+    item->ref_count--;
+    if (item->ref_count || item->queue_prev)
+        return;
+
+    if (item->next)
+        item->next->prev = item->prev;
+    *item->prev = item->next;
+
+    item->cache->items--;
+    item->cache->cache_size -= item->size;
+    destroy_item(item->cache, item);
+}
+
+void ass_cache_cut(Cache *cache, size_t max_size)
+{
+    if (cache->cache_size <= max_size)
+        return;
+
+    do {
+        CacheItem *item = cache->queue_first;
+        if (!item)
+            break;
+        assert(item->size);
+
+        cache->queue_first = item->queue_next;
+        if (item->ref_count) {
+            item->queue_prev = NULL;
+            continue;
         }
-        cache->map[i] = NULL;
-    }
 
-    cache->items = cache->hits = cache->misses = cache->cache_size = 0;
+        if (item->next)
+            item->next->prev = item->prev;
+        *item->prev = item->next;
 
-    return 1;
+        cache->items--;
+        cache->cache_size -= item->size;
+        destroy_item(cache, item);
+    } while (cache->cache_size > max_size);
+    if (cache->queue_first)
+        cache->queue_first->queue_prev = &cache->queue_first;
+    else
+        cache->queue_last = &cache->queue_first;
 }
 
 void ass_cache_stats(Cache *cache, size_t *size, unsigned *hits,
@@ -369,9 +474,27 @@ void ass_cache_stats(Cache *cache, size_t *size, unsigned *hits,
         *count = cache->items;
 }
 
+void ass_cache_empty(Cache *cache)
+{
+    for (int i = 0; i < cache->buckets; i++) {
+        CacheItem *item = cache->map[i];
+        while (item) {
+            assert(item->size);
+            CacheItem *next = item->next;
+            destroy_item(cache, item);
+            item = next;
+        }
+        cache->map[i] = NULL;
+    }
+
+    cache->queue_first = NULL;
+    cache->queue_last = &cache->queue_first;
+    cache->items = cache->hits = cache->misses = cache->cache_size = 0;
+}
+
 void ass_cache_done(Cache *cache)
 {
-    ass_cache_empty(cache, 0);
+    ass_cache_empty(cache);
     free(cache->map);
     free(cache);
 }
@@ -391,7 +514,7 @@ Cache *ass_outline_cache_create(void)
 
 Cache *ass_glyph_metrics_cache_create(void)
 {
-    return ass_cache_create(glyph_metrics_hash, glyph_metrics_compare, NULL,
+    return ass_cache_create(glyph_metrics_hash, glyph_metrics_compare, glyph_metric_destruct,
             (ItemSize) NULL, sizeof(GlyphMetricsHashKey),
             sizeof(GlyphMetricsHashValue));
 }
diff --git a/libass/ass_cache.h b/libass/ass_cache.h
index af814ac..63e9e59 100644
--- a/libass/ass_cache.h
+++ b/libass/ass_cache.h
@@ -106,11 +106,16 @@ typedef struct {
 Cache *ass_cache_create(HashFunction hash_func, HashCompare compare_func,
                         CacheItemDestructor destruct_func, ItemSize size_func,
                         size_t key_size, size_t value_size);
-void *ass_cache_put(Cache *cache, void *key, void *value);
-void *ass_cache_get(Cache *cache, void *key);
-int ass_cache_empty(Cache *cache, size_t max_size);
+bool ass_cache_get(Cache *cache, void *key, void *value_ptr);
+void *ass_cache_get_key(void *value);
+void ass_cache_commit(void *value);
+void ass_cache_cancel(void *value);
+void ass_cache_inc_ref(void *value);
+void ass_cache_dec_ref(void *value);
+void ass_cache_cut(Cache *cache, size_t max_size);
 void ass_cache_stats(Cache *cache, size_t *size, unsigned *hits,
                      unsigned *misses, unsigned *count);
+void ass_cache_empty(Cache *cache);
 void ass_cache_done(Cache *cache);
 Cache *ass_font_cache_create(void);
 Cache *ass_outline_cache_create(void);
diff --git a/libass/ass_font.c b/libass/ass_font.c
index 3d1b183..a4c45bd 100644
--- a/libass/ass_font.c
+++ b/libass/ass_font.c
@@ -229,32 +229,32 @@ ASS_Font *ass_font_new(Cache *font_cache, ASS_Library *library,
                        ASS_FontDesc *desc)
 {
     int error;
-    ASS_Font *fontp;
-    ASS_Font font;
-
-    fontp = ass_cache_get(font_cache, desc);
-    if (fontp)
-        return fontp;
-
-    font.library = library;
-    font.ftlibrary = ftlibrary;
-    font.shaper_priv = NULL;
-    font.n_faces = 0;
-    font.desc.family = strdup(desc->family);
-    font.desc.bold = desc->bold;
-    font.desc.italic = desc->italic;
-    font.desc.vertical = desc->vertical;
-
-    font.scale_x = font.scale_y = 1.;
-    font.v.x = font.v.y = 0;
-    font.size = 0.;
-
-    error = add_face(fontsel, &font, 0);
+    ASS_Font *font;
+    if (ass_cache_get(font_cache, desc, &font))
+        return font;
+
+    font->library = library;
+    font->ftlibrary = ftlibrary;
+    font->shaper_priv = NULL;
+    font->n_faces = 0;
+    ASS_FontDesc *new_desc = ass_cache_get_key(font);
+    font->desc.family = new_desc->family = strdup(desc->family);
+    font->desc.bold = desc->bold;
+    font->desc.italic = desc->italic;
+    font->desc.vertical = desc->vertical;
+
+    font->scale_x = font->scale_y = 1.;
+    font->v.x = font->v.y = 0;
+    font->size = 0.;
+
+    error = add_face(fontsel, font, 0);
     if (error == -1) {
-        free(font.desc.family);
+        ass_cache_cancel(font);
+        free(font->desc.family);
         return 0;
-    } else
-        return ass_cache_put(font_cache, &font.desc, &font);
+    }
+    ass_cache_commit(font);
+    return font;
 }
 
 /**
@@ -674,9 +674,9 @@ FT_Glyph ass_font_get_glyph(ASS_Font *font, uint32_t ch, int face_index,
 }
 
 /**
- * \brief Deallocate ASS_Font
+ * \brief Deallocate ASS_Font internals
  **/
-void ass_font_free(ASS_Font *font)
+void ass_font_clear(ASS_Font *font)
 {
     int i;
     if (font->shaper_priv)
@@ -686,7 +686,6 @@ void ass_font_free(ASS_Font *font)
             FT_Done_Face(font->faces[i]);
     }
     free(font->desc.family);
-    free(font);
 }
 
 /**
diff --git a/libass/ass_font.h b/libass/ass_font.h
index 9fc4532..3035654 100644
--- a/libass/ass_font.h
+++ b/libass/ass_font.h
@@ -74,7 +74,7 @@ uint32_t ass_font_index_magic(FT_Face face, uint32_t symbol);
 FT_Glyph ass_font_get_glyph(ASS_Font *font,
                             uint32_t ch, int face_index, int index,
                             ASS_Hinting hinting, int deco);
-void ass_font_free(ASS_Font *font);
+void ass_font_clear(ASS_Font *font);
 
 void outline_translate(const ASS_Outline *outline, FT_Pos dx, FT_Pos dy);
 void outline_transform(const ASS_Outline *outline, const FT_Matrix *matrix);
diff --git a/libass/ass_render.c b/libass/ass_render.c
index 7044335..ef0531d 100644
--- a/libass/ass_render.c
+++ b/libass/ass_render.c
@@ -130,10 +130,11 @@ static void free_list_clear(ASS_Renderer *render_priv)
 
 void ass_renderer_done(ASS_Renderer *render_priv)
 {
-    ass_cache_done(render_priv->cache.font_cache);
-    ass_cache_done(render_priv->cache.bitmap_cache);
     ass_cache_done(render_priv->cache.composite_cache);
+    ass_cache_done(render_priv->cache.bitmap_cache);
     ass_cache_done(render_priv->cache.outline_cache);
+    ass_shaper_free(render_priv->shaper);
+    ass_cache_done(render_priv->cache.font_cache);
 
     ass_free_images(render_priv->images_root);
     ass_free_images(render_priv->prev_images_root);
@@ -148,7 +149,6 @@ void ass_renderer_done(ASS_Renderer *render_priv)
     }
     if (render_priv->fontselect)
         ass_fontselect_free(render_priv->fontselect);
-    ass_shaper_free(render_priv->shaper);
     if (render_priv->ftlibrary)
         FT_Done_FreeType(render_priv->ftlibrary);
     free(render_priv->eimg);
@@ -487,31 +487,34 @@ static bool free_list_add(ASS_Renderer *render_priv, void *object)
 static void blend_vector_clip(ASS_Renderer *render_priv,
                               ASS_Image *head)
 {
-    Bitmap *clip_bm = NULL;
-    ASS_Image *cur;
     ASS_Drawing *drawing = render_priv->state.clip_drawing;
-    BitmapHashKey key;
-    BitmapHashValue *val;
-
     if (!drawing)
         return;
 
     // Try to get mask from cache
+    BitmapHashKey key;
     memset(&key, 0, sizeof(key));
     key.type = BITMAP_CLIP;
     key.u.clip.text = drawing->text;
-    val = ass_cache_get(render_priv->cache.bitmap_cache, &key);
 
-    if (val) {
+    BitmapHashValue *val;
+    Bitmap *clip_bm = NULL;
+    if (ass_cache_get(render_priv->cache.bitmap_cache, &key, &val)) {
         clip_bm = val->bm;
     } else {
-        BitmapHashValue v;
-
         // Not found in cache, parse and rasterize it
         ASS_Outline *outline = ass_drawing_parse(drawing, 1);
         if (!outline) {
             ass_msg(render_priv->library, MSGL_WARN,
                     "Clip vector parsing failed. Skipping.");
+            ass_cache_cancel(val);
+            return;
+        }
+
+        BitmapHashKey *new_key = ass_cache_get_key(val);
+        new_key->u.clip.text = strdup(drawing->text);
+        if (!new_key->u.clip.text) {
+            ass_cache_cancel(val);
             return;
         }
 
@@ -528,16 +531,15 @@ static void blend_vector_clip(ASS_Renderer *render_priv,
         clip_bm = outline_to_bitmap(render_priv, outline, 0);
 
         // Add to cache
-        memset(&v, 0, sizeof(v));
-        key.u.clip.text = strdup(drawing->text);
-        v.bm = clip_bm;
-        ass_cache_put(render_priv->cache.bitmap_cache, &key, &v);
+        val->bm = clip_bm;
+        val->bm_o = NULL;
+        ass_cache_commit(val);
     }
 
     if (!clip_bm) return;
 
     // Iterate through bitmaps and blend/clip them
-    for (cur = head; cur; cur = cur->next) {
+    for (ASS_Image *cur = head; cur; cur = cur->next) {
         int left, top, right, bottom, w, h;
         int ax, ay, aw, ah, as;
         int bx, by, bw, bh, bs;
@@ -1153,29 +1155,32 @@ static void fill_composite_hash(CompositeHashKey *hk, CombinedBitmapInfo *info)
 static void
 get_outline_glyph(ASS_Renderer *priv, GlyphInfo *info)
 {
-    OutlineHashValue *val;
-    OutlineHashKey key;
-
     memset(&info->hash_key, 0, sizeof(info->hash_key));
 
+    OutlineHashKey key;
+    OutlineHashValue *val;
     fill_glyph_hash(priv, &key, info);
-    val = ass_cache_get(priv->cache.outline_cache, &key);
-
-    if (!val) {
-        OutlineHashValue v;
-        memset(&v, 0, sizeof(v));
+    if (!ass_cache_get(priv->cache.outline_cache, &key, &val)) {
+        memset(val, 0, sizeof(*val));
 
         if (info->drawing) {
             ASS_Drawing *drawing = info->drawing;
             ass_drawing_hash(drawing);
-            if(!ass_drawing_parse(drawing, 0))
+            if(!ass_drawing_parse(drawing, 0)) {
+                ass_cache_cancel(val);
+                return;
+            }
+            OutlineHashKey *new_key = ass_cache_get_key(val);
+            new_key->u.drawing.text = strdup(drawing->text);
+            if(!new_key->u.drawing.text) {
+                ass_cache_cancel(val);
                 return;
-            v.outline = outline_copy(&drawing->outline);
-            v.advance.x = drawing->advance.x;
-            v.advance.y = drawing->advance.y;
-            v.asc = drawing->asc;
-            v.desc = drawing->desc;
-            key.u.drawing.text = strdup(drawing->text);
+            }
+            val->outline = outline_copy(&drawing->outline);
+            val->advance.x = drawing->advance.x;
+            val->advance.y = drawing->advance.y;
+            val->asc = drawing->asc;
+            val->desc = drawing->desc;
         } else {
             ass_face_set_size(info->font->faces[info->face_index],
                               info->font_size);
@@ -1186,35 +1191,37 @@ get_outline_glyph(ASS_Renderer *priv, GlyphInfo *info)
                         info->symbol, info->face_index, info->glyph_index,
                         priv->settings.hinting, info->flags);
             if (glyph != NULL) {
-                v.outline = outline_convert(&((FT_OutlineGlyph)glyph)->outline);
+                val->outline = outline_convert(&((FT_OutlineGlyph) glyph)->outline);
                 if (priv->settings.shaper == ASS_SHAPING_SIMPLE) {
-                    v.advance.x = d16_to_d6(glyph->advance.x);
-                    v.advance.y = d16_to_d6(glyph->advance.y);
+                    val->advance.x = d16_to_d6(glyph->advance.x);
+                    val->advance.y = d16_to_d6(glyph->advance.y);
                 }
                 FT_Done_Glyph(glyph);
                 ass_font_get_asc_desc(info->font, info->symbol,
-                        &v.asc, &v.desc);
-                v.asc  *= info->scale_y;
-                v.desc *= info->scale_y;
+                                      &val->asc, &val->desc);
+                val->asc  *= info->scale_y;
+                val->desc *= info->scale_y;
             }
         }
 
-        if (!v.outline)
+        if (!val->outline) {
+            ass_cache_cancel(val);
             return;
+        }
 
-        outline_get_cbox(v.outline, &v.bbox_scaled);
+        outline_get_cbox(val->outline, &val->bbox_scaled);
 
         if (info->border_style == 3) {
             FT_Vector advance;
 
-            v.border = calloc(1, sizeof(ASS_Outline));
+            val->border = calloc(1, sizeof(ASS_Outline));
 
             if (priv->settings.shaper == ASS_SHAPING_SIMPLE || info->drawing)
-                advance = v.advance;
+                advance = val->advance;
             else
                 advance = info->advance;
 
-            draw_opaque_box(priv, info, v.asc, v.desc, v.border, advance,
+            draw_opaque_box(priv, info, val->asc, val->desc, val->border, advance,
                     double_to_d6(info->border_x * priv->border_scale),
                     double_to_d6(info->border_y * priv->border_scale));
 
@@ -1222,13 +1229,15 @@ get_outline_glyph(ASS_Renderer *priv, GlyphInfo *info)
                 && double_to_d6(info->scale_x) && double_to_d6(info->scale_y)) {
 
             change_border(priv, info->border_x, info->border_y);
-            v.border = outline_copy(v.outline);
-            stroke_outline(priv, v.border,
+            val->border = outline_copy(val->outline);
+            stroke_outline(priv, val->border,
                     double_to_d6(info->border_x * priv->border_scale),
                     double_to_d6(info->border_y * priv->border_scale));
         }
 
-        val = ass_cache_put(priv->cache.outline_cache, &key, &v);
+        if (!info->drawing)
+            ass_cache_inc_ref(info->font);
+        ass_cache_commit(val);
     }
 
     info->hash_key.u.outline.outline = val;
@@ -1329,22 +1338,18 @@ transform_3d(FT_Vector shift, ASS_Outline *outline, ASS_Outline *border,
 static void
 get_bitmap_glyph(ASS_Renderer *render_priv, GlyphInfo *info)
 {
-    BitmapHashValue *val;
-    OutlineBitmapHashKey *key = &info->hash_key.u.outline;
-
     if (!info->outline || info->symbol == '\n' || info->symbol == 0 || info->skip)
         return;
 
-    val = ass_cache_get(render_priv->cache.bitmap_cache, &info->hash_key);
-
-    if (!val) {
+    BitmapHashValue *val;
+    OutlineBitmapHashKey *key = &info->hash_key.u.outline;
+    if (!ass_cache_get(render_priv->cache.bitmap_cache, &info->hash_key, &val)) {
         FT_Vector shift;
-        BitmapHashValue hash_val;
         int error;
         double fax_scaled, fay_scaled;
         double scale_x = render_priv->font_scale_x;
 
-        hash_val.bm = hash_val.bm_o = NULL;
+        val->bm = val->bm_o = NULL;
 
         ASS_Outline *outline = outline_copy(info->outline);
         ASS_Outline *border  = outline_copy(info->border);
@@ -1379,12 +1384,13 @@ get_bitmap_glyph(ASS_Renderer *render_priv, GlyphInfo *info)
 
         // render glyph
         error = outline_to_bitmap2(render_priv, outline, border,
-                                   &hash_val.bm, &hash_val.bm_o);
+                                   &val->bm, &val->bm_o);
         if (error)
             info->symbol = 0;
 
-        val = ass_cache_put(render_priv->cache.bitmap_cache, &info->hash_key,
-                &hash_val);
+        assert(info->hash_key.type == BITMAP_OUTLINE);
+        ass_cache_inc_ref(info->hash_key.u.outline.outline);
+        ass_cache_commit(val);
 
         outline_free(outline);
         free(outline);
@@ -2254,8 +2260,6 @@ static void render_and_combine_glyphs(ASS_Renderer *render_priv,
         }
     }
 
-    CompositeHashKey hk;
-    CompositeHashValue *hv;
     for (int i = 0; i < nb_bitmaps; ++i) {
         CombinedBitmapInfo *info = &combined_info[i];
         for (int j = 0; j < info->bitmap_count; ++j) {
@@ -2263,10 +2267,10 @@ static void render_and_combine_glyphs(ASS_Renderer *render_priv,
             info->bitmaps[j].y -= info->y;
         }
 
+        CompositeHashKey hk;
+        CompositeHashValue *hv;
         fill_composite_hash(&hk, info);
-
-        hv = ass_cache_get(render_priv->cache.composite_cache, &hk);
-        if (hv) {
+        if (ass_cache_get(render_priv->cache.composite_cache, &hk, &hv)) {
             info->bm = hv->bm;
             info->bm_o = hv->bm_o;
             info->bm_s = hv->bm_s;
@@ -2344,19 +2348,19 @@ static void render_and_combine_glyphs(ASS_Renderer *render_priv,
             }
         }
 
-        if(info->bm || info->bm_o){
+        if (info->bm || info->bm_o) {
             ass_synth_blur(render_priv->engine, info->filter.flags & FILTER_BORDER_STYLE_3,
                            info->filter.be, info->filter.blur, info->bm, info->bm_o);
             if (info->filter.flags & FILTER_DRAW_SHADOW)
                 make_shadow_bitmap(info, render_priv);
         }
 
-        CompositeHashValue chv;
-        chv.bm = info->bm;
-        chv.bm_o = info->bm_o;
-        chv.bm_s = info->bm_s;
-
-        ass_cache_put(render_priv->cache.composite_cache, &hk, &chv);
+        hv->bm = info->bm;
+        hv->bm_o = info->bm_o;
+        hv->bm_s = info->bm_s;
+        for (int j = 0; j < info->bitmap_count; ++j)
+            ass_cache_inc_ref(info->bitmaps[j].image);
+        ass_cache_commit(hv);
     }
 
     text_info->n_bitmaps = nb_bitmaps;
@@ -2639,24 +2643,12 @@ void ass_free_images(ASS_Image *img)
  */
 static void check_cache_limits(ASS_Renderer *priv, CacheStore *cache)
 {
-    if (ass_cache_empty(cache->bitmap_cache, cache->bitmap_max_size)) {
-        ass_cache_empty(cache->composite_cache, 0);
-        ass_free_images(priv->prev_images_root);
-        priv->prev_images_root = 0;
-        priv->cache_cleared = 1;
-    }
-    if (ass_cache_empty(cache->outline_cache, cache->glyph_max)) {
-        ass_cache_empty(cache->bitmap_cache, 0);
-        ass_cache_empty(cache->composite_cache, 0);
-        ass_free_images(priv->prev_images_root);
-        priv->prev_images_root = 0;
-        priv->cache_cleared = 1;
-    }
-    if (ass_cache_empty(cache->composite_cache, cache->composite_max_size)) {
-        ass_free_images(priv->prev_images_root);
-        priv->prev_images_root = 0;
-        priv->cache_cleared = 1;
-    }
+    ass_cache_cut(cache->composite_cache, cache->composite_max_size);
+    ass_cache_cut(cache->bitmap_cache, cache->bitmap_max_size);
+    ass_cache_cut(cache->outline_cache, cache->glyph_max);
+    ass_free_images(priv->prev_images_root);
+    priv->prev_images_root = 0;
+    priv->cache_cleared = 1;
 }
 
 /**
diff --git a/libass/ass_render.h b/libass/ass_render.h
index e6b1f17..83dd1d8 100644
--- a/libass/ass_render.h
+++ b/libass/ass_render.h
@@ -42,8 +42,8 @@
 #include "ass_rasterizer.h"
 
 #define GLYPH_CACHE_MAX 10000
-#define BITMAP_CACHE_MAX_SIZE 500 * 1048576
-#define COMPOSITE_CACHE_MAX_SIZE 500 * 1048576
+#define BITMAP_CACHE_MAX_SIZE 128 * 1048576
+#define COMPOSITE_CACHE_MAX_SIZE 64 * 1048576
 
 #define PARSED_FADE (1<<0)
 #define PARSED_A    (1<<1)
diff --git a/libass/ass_render_api.c b/libass/ass_render_api.c
index 4f6b063..9c5f4d4 100644
--- a/libass/ass_render_api.c
+++ b/libass/ass_render_api.c
@@ -27,9 +27,9 @@ static void ass_reconfigure(ASS_Renderer *priv)
     ASS_Settings *settings = &priv->settings;
 
     priv->render_id++;
-    ass_cache_empty(priv->cache.outline_cache, 0);
-    ass_cache_empty(priv->cache.bitmap_cache, 0);
-    ass_cache_empty(priv->cache.composite_cache, 0);
+    ass_cache_empty(priv->cache.composite_cache);
+    ass_cache_empty(priv->cache.bitmap_cache);
+    ass_cache_empty(priv->cache.outline_cache);
     ass_free_images(priv->prev_images_root);
     priv->prev_images_root = 0;
 
diff --git a/libass/ass_shaper.c b/libass/ass_shaper.c
index fa50982..95ffda3 100644
--- a/libass/ass_shaper.c
+++ b/libass/ass_shaper.c
@@ -207,26 +207,25 @@ get_cached_metrics(struct ass_shaper_metrics_data *metrics, FT_Face face,
                    hb_codepoint_t unicode, hb_codepoint_t glyph)
 {
     GlyphMetricsHashValue *val;
-
     metrics->hash_key.glyph_index = glyph;
-    val = ass_cache_get(metrics->metrics_cache, &metrics->hash_key);
-
-    if (!val) {
+    if (!ass_cache_get(metrics->metrics_cache, &metrics->hash_key, &val)) {
         int load_flags = FT_LOAD_DEFAULT | FT_LOAD_IGNORE_GLOBAL_ADVANCE_WIDTH
             | FT_LOAD_IGNORE_TRANSFORM;
-        GlyphMetricsHashValue new_val;
 
-        if (FT_Load_Glyph(face, glyph, load_flags))
+        if (FT_Load_Glyph(face, glyph, load_flags)) {
+            ass_cache_cancel(val);
             return NULL;
+        }
 
-        memcpy(&new_val.metrics, &face->glyph->metrics, sizeof(FT_Glyph_Metrics));
+        memcpy(&val->metrics, &face->glyph->metrics, sizeof(FT_Glyph_Metrics));
 
         // if @font rendering is enabled and the glyph should be rotated,
         // make cached_h_advance pick up the right advance later
         if (metrics->vertical && unicode >= VERTICAL_LOWER_BOUND)
-            new_val.metrics.horiAdvance = new_val.metrics.vertAdvance;
+            val->metrics.horiAdvance = val->metrics.vertAdvance;
 
-        val = ass_cache_put(metrics->metrics_cache, &metrics->hash_key, &new_val);
+        ass_cache_inc_ref(metrics->hash_key.font);
+        ass_cache_commit(val);
     }
 
     return val;