Bug 692246 - font cache infinite loop
Summary: font cache infinite loop
Status: RESOLVED FIXED
Alias: None
Product: Ghostscript
Classification: Unclassified
Component: Graphics Library (show other bugs)
Version: master
Hardware: PC All
: P4 normal
Assignee: Henry Stiles
URL:
Keywords: bountiable
Depends on:
Blocks:
 
Reported: 2011-05-31 15:26 UTC by Henry Stiles
Modified: 2011-07-07 00:18 UTC (History)
1 user (show)

See Also:
Customer:
Word Size: ---


Attachments
font test (6.15 MB, application/octet-stream)
2011-05-31 15:26 UTC, Henry Stiles
Details
Patch for Bug692246 (2.17 KB, patch)
2011-06-04 12:41 UTC, Shailesh Mistry
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Henry Stiles 2011-05-31 15:26:35 UTC
Created attachment 7552 [details]
font test

e18b1569b49a7f4acc9c2902d39b9eb7254c429f causes a regression in F041 (attached).  The font cache fills up and then gets into an infinite loop searching for a character.
Comment 1 Henry Stiles 2011-05-31 17:24:12 UTC
In gdb:

r -sDEVICE=ppmraw -o /dev/null -dNOPAUSE ~/tests_private/customer_tests/F041.bin.xl

wait a minute or so:

Ctrl-C

(gdb) p chi
$32 = 2505458144
(gdb)
Comment 2 Shailesh Mistry 2011-06-01 23:02:03 UTC
The problem is down to gx_lookup_cached_char, the lookup table is 8192 in size and is completely full. Just by setting cmax_LARGE to 6000 will solve this problem.

However, there is another problem here in that if the table is ever full again it will just go round endlessly in the while loop. I thought having an escape clause might help forcing it to jump out and return a zero value but this leads to other complications which may need further investigation!
Comment 3 Henry Stiles 2011-06-02 14:32:34 UTC
(In reply to comment #2)
> The problem is down to gx_lookup_cached_char, the lookup table is 8192 in size
> and is completely full. Just by setting cmax_LARGE to 6000 will solve this
> problem.
> 
> However, there is another problem here in that if the table is ever full again
> it will just go round endlessly in the while loop. I thought having an escape
> clause might help forcing it to jump out and return a zero value but this leads
> to other complications which may need further investigation!

From the original author:

Usually the way I ensured that a direct-probe hash table didn't fill up was
to limit the number of entries to some value less than the size of the
table, so you'd have to look at the code that adds entries to and removes
entries from the table.  Typically that code keeps count of the number of
occupied entries, and deletes entries if adding a new entry would cause the
table to get "too full."

Simply using a count might still result in some lookups taking a long time
if the statistics broke just wrong, which is why I seem to remember liking
to limit the capacity to 3/4 of the size.
Comment 4 Shailesh Mistry 2011-06-04 12:41:28 UTC
Created attachment 7563 [details]
Patch for Bug692246

This patch counts the number of entries in the cache and when it is 3/4 full it removes 1% to make room for further chars. More than one char is removed so that the code does not sit on the cache limit and continually add and remove entries as more chars get cached.
Comment 5 Henry Stiles 2011-06-05 18:08:10 UTC
(In reply to comment #4)
> Created an attachment (id=7563) [details]
> Patch for Bug692246
> 
> This patch counts the number of entries in the cache and when it is 3/4 full it
> removes 1% to make room for further chars. More than one char is removed so
> that the code does not sit on the cache limit and continually add and remove
> entries as more chars get cached.


I don't think Peter would leave out code to guarantee the font cache wouldn't fill up.  Simply patching up the problem with a new implementation is rarely of interest to us.  We want to get at the underlying issue, which likely begins with looking at the commit that changed the font cache table sizes and created the regression.
Comment 6 Shailesh Mistry 2011-06-11 19:24:53 UTC
The root cause of this bug is 2 fold

1) The capacity of the hash table is independent of the cache freeing mechanism.
2) A number of "while" conditionals exist that can loop indefinitely

The value of cmax (# of chached chars) is used in gx_char_cache_alloc to calculate the size of hash table to make. However the cache freeing mechanism is based on bmax. This bug results because bmax still has enough space to make a new entry for the hash table but the table is full so the while conditional in gx_lookup_cached_char cannot find the requested char and also cannot find an empty slot to store the new char in.


This can be resolved by :-

1) remove cmax and calculate the hash table size using a function of bmax

2) update gx_lookup_cached_char so that the while loop will break out if the table is full and return 0 to indicate the requested char was not found

3) update alloc_char_in_chunk so that the while loop will free the current entry pointed to if the table is full and/or purge a set percentage to make room

4) update gx_add_cached_char so that the while loop will break out if the table is full and also purge a set percentage to make some room
Comment 7 Henry Stiles 2011-06-15 03:38:54 UTC
Sorry Shailesh, I keep trying to get back to this problem and get interrupted.  This problem began (comment #1) with a regression - the change increased the maximum character size and the amount of memory that could be used by cached chars.  So your analysis might suggest the code worked before because bmax (max font cache memory) was exceeded before the table filled up but I'm not convinced of that just reading the code.  I'd like to understand exactly how the commit broke the code before making more code changes.
Comment 8 Henry Stiles 2011-07-07 00:18:09 UTC
Fixed in http://git.ghostscript.com/?p=ghostpdl.git;a=commit;h=f91aa55a