[cairo] glyph caching bug

[Keith Packard]

Around 7 o'clock on Dec 29, TOKUNAGA Hiroyuki wrote:

> I implemented lock per entry tentatively, but encountered another
> problem. If all live entries are locked, _random_live_entry goes into an
> infinite loop. I think locking individual cache elements is hard to
> implement.

It seems like this can be avoided by allowing the _random_live_entry 
function to fail and have the cache reduction loop terminate at that 
point.  We'll want to recode the _random_live_entry function to walk through
the entire cache instead of the current random probe technique though.
We could also keep track of the number of locked entries and stop purging 
the cache when that number reached the number of live entries.

What I'm trying to avoid is forcing the whole cache to be locked 
during all rendering operations; this will cause a large spike in memory 
usage, instead of limiting memory usage to the maximum of the cache size 
and the memory necessary to perform any single operation.

> I think it is difficult to regenerate a cache entry as needed. To know
> 'which entries are needed now' would be equivalent to lock individual
> cache elements. I want to propose another model, create entry
> explicitly.

Right -- because of multiple threads sharing the same cache, you have to 
lock when you want to use any entries.  Except for this, you could assert 
that the last cache value fetched was always valid and make sure the code 
consistently used only a single cache value at a time.

> If entry was created explicitly, there's no need to call
> create_entry/destroy_entry function in lookup function. We'll be able to
> write code like this.
> 
>   for(i=0; i<length;i++) {
>      if(lookup(keys[i], &entries[i]) == NOT_FOUND)
>         entries[i] = create_entry(keys[i])
>   }

This doesn't appear to handle the case of multiple threads looking up the 
same element in the cache simultaneously -- they'll both miss, and then 
they'll both create the element and register it.  I think we have to 
atomically look elements up in the cache, creating them if missing.

-keith


-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 228 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/cairo/attachments/20041228/6df127b2/attachment.pgp