Mon 25 Jun 2012 09:06:36 AM UTC, comment #26:
Obviously, this report has been forgotten to close.
|
Sat 28 May 2011 09:03:42 AM UTC, comment #25:
After I've committed the patch on Jan-9th, the status is kept
as ready for test. If there is no regression report by May-31st,
I will close this bug. When anything wrong is found, please reopen
this bug.
|
Sun 09 Jan 2011 02:16:34 PM UTC, comment #24:
Just I've committed the patch to prevent this issue,
based on file #22345. If you have any trouble,
I will revert it and use another patch file #22344.
|
Sun 09 Jan 2011 09:29:32 AM UTC, comment #23:
Indeed. Although the overhaul for cache code for non-inlined
configuration is needed (many `#if 0' are used to disable original
non-inlined code, I guess), this issue exists in both of inlined &
non-inlined configuration. I will do that...
|
Fri 07 Jan 2011 10:42:11 PM UTC, comment #22:
file #22344 fixes the problem. It is same as the fix I proposed. I have already tested it.
One more input; its late to tell but I also just realised:
The bug also needs to be fixed for the non-inlined version i.e. for the case 'FTC_INLINE' is not defined. The function FTC_Cache_Lookup needs to be modified.
|
Wed 05 Jan 2011 10:36:39 AM UTC, comment #21:
Toshiya-san, great job!
Both patches b and c look fine. Please apply what you prefer.
Similarly, your ftdebug and ftbench patches are good also.
|
Tue 04 Jan 2011 05:14:10 PM UTC, comment #20:
The result log files:
- ftbench_norescan.log: trace message when rescanning is off
- ftbench_norescan.valgrind.log: valgrind log when rescanning is off
- ftbench_rescan.log: trace message when rescanning is on
- ftbench_rescan.valgrind.log: trace message when rescanning is on
The executed command is:
env FT2_ALLOC_CUR_MAX_SITE=ftcsbits.c:57:120000 FT2_DEBUG="dbgmem:7 cache:7" FT2_DEBUG_MEMORY=9999 valgrind --log-file=/media/usbdisk/tmp/ftbench_rescan.valgrind.log ../freetype2-demos/bin/.libs/ftbench -C -b a -s 14 -j -d 100 /usr/share/fonts/X11/misc/k14.pcf.gz > /media/usbdisk/tmp/ftbench_norescan.log
The change of _bucket and _pnode can be found in ftbench_rescan.log,
like this (error 0x40 means OOM):
---------------------------------------------------------------
FTC_CACHE_LOOKUP_CMP() lookup object for hash=0x000000fe in cache mask=0x0000003f p=0x0000001f list length=132
ftc_snode_compare() work for gindex=231
ftc_snode_load() got error from family_load_glyph() err=0x00
ft_mem_table_set() invoked by ftcsbits.c:57, limit:(119952 =< -1 && 119952 =< 120000 && 0 =< 0)
ftc_snode_load() load glyph for gid=231, err=0x00
ftc_snode_compare() returns TRUE
FTC_CACHE_LOOKUP_CMP() lookup object for hash=0x00000104 in cache mask=0x0000003f p=0x0000001f list length=88
ftc_snode_compare() work for gindex=331
ftc_snode_load() got error from family_load_glyph() err=0x00
ft_mem_table_set() invoked by ftcsbits.c:57, limit:(120008 =< -1 && 120008 =< 120000 && 0 =< 0)
ft_mem_table_set() returns NULL to ftcsbits.c:57 (-> (nil):0), total allocation exceeds site-current-limit (120008 > 120000)
ftc_snode_load() load glyph for gid=331, err=0x40
FTC_Manager_FlushN() tries to free 4 nodes from list length=3
...
FTC_Manager_FlushN() tries to free 2398 nodes from list length=3
FTC_Manager_FlushN() freed 2397 nodes, list length=1
ftc_snode_load() got error from family_load_glyph() err=0x00
ft_mem_table_set() invoked by ftcsbits.c:57, limit:(120008 =< -1 && 672 =< 120000 && 0 =< 0)
ftc_snode_load() load glyph for gid=331, err=0x00
ftc_snode_compare() returns TRUE
FTC_CACHE_LOOKUP_CMP() changed the node list, list length=44
(_bucket, _pnode):(0x4906388,0x49087d0) -> (0x497cde0,0x497cde0)
----------------------------------------------------------------
If rescanning is disabled, ftbench aborts after freeing 2397 nodes, like:
----------------------------------------------------------------
FTC_Manager_FlushN() tries to free 2398 nodes from list length=3
FTC_Manager_FlushN() freed 2397 nodes, list length=1
ftc_snode_load() got error from family_load_glyph() err=0x00
ft_mem_table_set() invoked by ftcsbits.c:57, limit:(120008 =< -1 && 672 =< 120000 && 0 =< 0)
ftc_snode_load() load glyph for gid=331, err=0x00
ftc_snode_compare() returns TRUE
FTC_CACHE_LOOKUP_CMP() lookup object for hash=0x0000010a in cache mask=0x00000007 p=0x00000000 list length=0
ftc_snode_load() got error from family_load_glyph() err=0x00
ft_mem_table_set() invoked by ftcsbits.c:57, limit:(120064 =< -1 && 728 =< 120000 && 0 =< 0)
ftc_snode_load() load glyph for gid=431, err=0x00
FTC_CACHE_LOOKUP_CMP() lookup object for hash=0x00000111 in cache mask=0x00000007 p=0x00000000 list length=0
ftc_snode_load() got error from family_load_glyph() err=0x00
ft_mem_table_set() invoked by ftcsbits.c:57, limit:(120120 =< -1 && 784 =< 120000 && 0 =< 0)
ftc_snode_load() load glyph for gid=531, err=0x00
FTC_CACHE_LOOKUP_CMP() lookup object for hash=0x00000117 in cache mask=0x00000007 p=0x00000000 list length=0
ftc_snode_load() got error from family_load_glyph() err=0x00
ft_mem_table_set() invoked by ftcsbits.c:57, limit:(120176 =< -1 && 840 =< 120000 && 0 =< 0)
ftc_snode_load() load glyph for gid=631, err=0x00
FTC_CACHE_LOOKUP_CMP() lookup object for hash=0x0000011d in cache mask=0x00000007 p=0x00000000 list length=0
ftc_snode_load() got error from family_load_glyph() err=0x00
ft_mem_table_set() invoked by ftcsbits.c:57, limit:(120232 =< -1 && 896 =< 120000 && 0 =< 0)
ftc_snode_load() load glyph for gid=731, err=0x00
FTC_CACHE_LOOKUP_CMP() lookup object for hash=0x00000123 in cache mask=0x00000007 p=0x00000000 list length=0
ftc_snode_load() got error from family_load_glyph() err=0x00
ft_mem_table_set() invoked by ftcsbits.c:57, limit:(120288 =< -1 && 952 =< 120000 && 0 =< 0)
ftc_snode_load() load glyph for gid=831, err=0x00
FTC_CACHE_LOOKUP_CMP() lookup object for hash=0x0000012a in cache mask=0x00000007 p=0x00000000 list length=44
ftc_snode_load() got error from family_load_glyph() err=0x00
ft_mem_table_set() invoked by ftcsbits.c:57, limit:(120344 =< -1 && 1008 =< 120000 && 0 =< 0)
ftc_snode_load() load glyph for gid=931, err=0x00
FTC_CACHE_LOOKUP_CMP() lookup object for hash=0x00000130 in cache mask=0x00000007 p=0x00000000 list length=0
ftc_snode_load() got error from family_load_glyph() err=0x00
ft_mem_table_set() invoked by ftcsbits.c:57, limit:(120400 =< -1 && 1064 =< 120000 && 0 =< 0)
ftc_snode_load() load glyph for gid=1031, err=0x00
FTC_CACHE_LOOKUP_CMP() lookup object for hash=0x00000136 in cache mask=0x00000007 p=0x00000000 list length=0
ftc_snode_load() got error from family_load_glyph() err=0x00
ft_mem_table_set() invoked by ftcsbits.c:57, limit:(120456 =< -1 && 1120 =< 120000 && 0 =< 0)
ftc_snode_load() load glyph for gid=1131, err=0x00
FTC_CACHE_LOOKUP_CMP() lookup object for hash=0x0000013c in cache mask=0x00000007 p=0x00000000 522.654 us/op
[Segmentation fault]
----------------------------------------------------------------
valgrind log provides more info about this SEGV, like this:
----------------------------------------------------------------
==2579== Invalid read of size 4
==2579== at 0x40DBA6C: ftc_get_list_length (ftccache.c:470)
==2579== by 0x40DE348: FTC_SBitCache_Lookup (ftcbasic.c:715)
==2579== by 0x80498C7: test_sbit_cache (ftbench.c:484)
==2579== by 0x80490BA: benchmark (ftbench.c:180)
==2579== by 0x804A212: main (ftbench.c:837)
==2579== Address 0xf3f3f3fb is not stack'd, malloc'd or (recently) free'd
==2579==
==2579==
==2579== Process terminating with default action of signal 11 (SIGSEGV)
==2579== Access not within mapped region at address 0xF3F3F3FB
==2579== at 0x40DBA6C: ftc_get_list_length (ftccache.c:470)
==2579== by 0x40DE348: FTC_SBitCache_Lookup (ftcbasic.c:715)
==2579== by 0x80498C7: test_sbit_cache (ftbench.c:484)
==2579== by 0x80490BA: benchmark (ftbench.c:180)
==2579== by 0x804A212: main (ftbench.c:837)
==2579== If you believe this happened as a result of a stack
==2579== overflow in your program's main thread (unlikely but
==2579== possible), you can try to increase the size of the
==2579== main thread stack using the --main-stacksize= flag.
==2579== The main thread stack size used in this run was 8388608.
----------------------------------------------------------------
0xF3F3... is apparently the scrambling value that FT2 memory debugger
fills the freed buffer. Thus, without rescanning of changed list, we will
have such errors.
(file #22349)
|
Tue 04 Jan 2011 04:51:07 PM UTC, comment #19:
A patch to modify the glyph index scanning of ftbench.
Current ftbench takes 1 option to control, the first glyph
index to start the scan. This patch introduce additional
3 options:
- "-l" to specify the next of the last glyph index to finish the scan.
- "-d" to specify the delta of glyph index scanning ("-d 2" makes 0, 2, 4, 6, ...)
- "-j" to specify rectangle scan (0, delta, 2delta, ..., 1, delta+1, 2delta+1, ...)
A node in sbit cache can include multiple bitmaps with
similar glyph index, so linear scanning is difficult to make
the node reordering caused. By using "-d" option and
specify large delta (like 100), many unfilled nodes are
allocated for first and filled in later.
I'm questionable if this patch is useful for FT2 users.
For fine-tuning of glyph index scanning, loading a serie
of glyph index from external files (or stdin) would be better,
because 4 options are too many for glyph index only purpose.
(file #22348)
|
Tue 04 Jan 2011 04:31:19 PM UTC, comment #18:
A patch to introduce per-site upper limit for memory allocator.
Current FT2 has a upper limit for memory allocator whole system,
FT2_ALLOC_TOTAL_MAX and FT2_ALLOC_COUNT_MAX (most
designed malloc failure can be scheduled by them, failmalloc
is not essential, now I think).
However, to reproduce this filed bug, we want to make malloc()
failed in more specific part, like, malloc() in ftc_sbit_copy_bitmap()
when total allocated buffer in the function exceeds a limit.
This patch accepts such specification by setting
FT2_ALLOC_CUR_MAX_SITE, like, "ftcsbits.c:57:100000".
Also for easy check of the effect of the changed linked list rescanning,
the rescanning is enabled when FT2_CACHE_RESCAN_LIST is set.
More unfinished hooks are included in the patch, so this is huge.
When I split them to more cleaner fragments, I will propose them
in ft-devel mailing list or savannah patch site.
(file #22347)
|
Tue 04 Jan 2011 02:48:47 PM UTC, comment #17:
Finally I could reproduce the issue as a SEGV caused by
the access to freed memory, and the SEGV does not occur
in the patched version. Soon I will apply the patch to GIT.
Werner, could you comment about mps20101228c.diff?
If it is overkill, I will apply shorter one mps20101228b.diff.
Due to huge patch making many tracing message, the
reproduction info will be posted in later.
|
Tue 04 Jan 2011 04:28:19 AM UTC, comment #16:
The differences from mps20101228b.diff & mps20101228c.diff are following:
- the code to locate the `top' of the linked list of cache node are replaced
by new cpp macro `FTC_NODE__TOP_FOR_HASH()', because similar codes
are used in several parts.
- the comparison functions checking if the found cache node is requested one
takes new argument `FT_Bool* list_changed', to indicate if the cache node list
is changed and rescanning is needed, because most comparison functions
don't change the cache node list.
- `FTC_CACHE_LOOKUP_CMP()' rescans the cache node list when list_changed
returned by the comparison function is true.
|
Tue 04 Jan 2011 04:21:08 AM UTC, comment #15:
Excuse me, previous report about the reproduction of this issue
was my mistake. The endless loop was found out of FreeType2
(I was using ftview and the endless loop was found in X11 library).
Now I'm extending FT2 builtin memory debugger to make the scenario
occurs forcibly.
Before finishing them, here I attach 2 patches for the people
who are interested in.
mps20101228b.diff: a minimum patch changing FTC_CACHE_LOOKUP_CMP() only
mps20101228c.diff: bigger patch cleaning more.
mps20101228b.diff can be applied to freetype-2.3.5 too.
Harsha, could you check if the patch can fix the problem on
your platform?
(file #22344, file #22345)
|
Thu 30 Dec 2010 01:49:24 AM UTC, comment #14:
Werner, thank you for comment.
Fortunately, by Okuji's failmalloc (http://www.nongnu.org/failmalloc/),
it seems that I could reproduce the endless loop case. I'm not sure if
it is the error that Harsha predicted. Please let me spend more time
for this issue.
|
Wed 29 Dec 2010 08:15:52 PM UTC, comment #13:
If possible, please add your detailed explanation of the cache macro stuff to the source code so that others don't have to invest so much time as you currently do.
|
Wed 29 Dec 2010 05:03:20 PM UTC, comment #12:
Thank you for the explanation on the syntax error in the patch,
I appreciate your translation of your office work for public.
I will try to reproduce the case that ftc_sbit_copy_bitmap() returns
OOM error and check whether the proposed patch can fix the crash.
I already revised the patch and checked that it does not break
current FT2, but yet I cannot check it can fix the error you described.
|
Wed 29 Dec 2010 12:12:51 PM UTC, comment #11:
Few inputs on what you would see when you reproduce the defect:
We would be hung in the for loop forever. The reason being that the the linked list would have become circular.
what would have happened is: the previous node(i.e. node whose link is pointed by _pnode) is deleted, so the operation of putting node on top just makes the list circular. Now when look up is done again for the same bucket and the hash do not match,(i.e. node not present and we have to create new node) the for loop never ends.
|
Wed 29 Dec 2010 09:50:29 AM UTC, comment #10:
Yes, my understanding is in line with yours. And the understanding for the patch is also in line.
Sorry, I don't have any test code and also for syntax errors. The problem should be reproducible if memory available is lesser, or say there is only enough memory for say 20 nodes and if you try loading more you may see this problem. But not easy to reproduce in the actual system, we have to try to reach this out of memory condition again and again.
I am an embedded software developer. I have very little knowledge of windows and linux. So the fixes I have done at office have to be redone at home and here I don't have environment to test. That's the reason for syntax error. Sorry again.
|
Tue 28 Dec 2010 06:23:55 AM UTC, comment #9:
I draw a picture how FTC_CACHE_LOOKUP_CMP() reorders
the found node to the end of the linked list and why _bucket
and _pnode are important:
https://www.codeblog.org/blog/mpsuzuki/images/20101227_0.png
|
Tue 28 Dec 2010 06:01:26 AM UTC, comment #8:
Harsha, I'm afraid you have not tested attached file, because it has
syntax error at the head of the patch, "FTC_Node _bucket, _pnode,
_node,_node_cmp" (it requires a semicolon), but I think your pointing
out is reasonable. Following is the summary of my understanding.
If I'm misunderstanding, please correct.
I will revise your code based on my understanding (I think more indepth
revise about the linked list changing in the comparison function, I will
do that, but your proposal is useful for quick fix). Do you have any
small testing code to reproduce a crash by this problem?
--
1) FTC_CACHE_LOOKUP_CMP() searches the linked list of the nodes
for the cached objects sharing same masked hash value (idx), and
compares the node with given `query'.
2) The comparison of the node in the linked list and the given `query'
is done by given function `_nodecomp'. It is expected that `_nodecomp'
does not change the hash table structure (_cache->{p, mask}) and
the linked list for safety, because:
A) changing the hash table structure (_cache->{p, mask}) can make
the masked hash value invalid (idx).
B) changing the linked list can disturb the searching loop that follows
the linked list from the ending node to the beginning node.
3) Most `_nodecomp' functions; ftc_face_node_compare(),
ftc_cmap_node_compare(), ftc_size_node_compare() and
ftc_gnode_compare() simply return the comparison result and
does not modify the linked list. But the ftc_snode_compare() is
exceptional (public function FTC_SBitCache_Lookup() invokes
FTC_CACHE_LOOKUP() with FTC_SNode_Compare() which
is a thin wrapper of ftc_snode_compare()).
3-1) A sbit node can include multiple bitmap images for multiple
glyph index, but ftc_snode_load() loads 1 bitmap image per 1
invocation. Thus, it is possible that we find an appropriate
node that the requested bitmap image should be stored but
it is not loaded at present. In such case, ftc_snode_compare()
tries to load the requested glyph image to the node.
3-2) To prevent the cache inflation, ftc_snode_compare() tries
to catch Out-Of-Memory error from ftc_snode_load() and
retry bitmap-loading after FTC_Manager_FlushN() (it is invoked
invoked by FTC_CACHE_TRYLOOP() - FTC_CACHE_TRYLOOP_END()).
FTC_Manager_FlushN() selects the node to be flushed by
Most-Recently-Used list.
The candidate node (to be modified to include a bitmap image) is
locked by the reference counter (it is increased before ftc_snode_load())
and protected from FTC_Manager_FlushN(). In addition, when
FTC_Manager_FlushN() flushes a node in the linked list, the
nodes in neighborhood are reconnected to prevent the disconnection
of the linked list.
4) Although FTC_Manager_FlushN() keep the linked list connected,
FTC_CACHE_LOOKUP() holds the pointer to the top node
(*_bucket) and the pointer to the `link' member in the previous
node (_pnode) taken from the linked list before FTC_Manager_FlushN().
They are not synchronized with the linked list manipulation by
FTC_Manager_FlushN().
5) After finding a node including requested data (or modifying a node
to include requested data), FTC_CACHE_LOOKUP() reorders the
linked list to put the found node to the top node of the linked list,
like this:
if ( _node != *_bucket ) \
{ \
*_pnode = _node->link; \
_node->link = *_bucket; \
*_bucket = _node; \
} \
In this process, *_bucket and _pnode are used, so they should be
updated to manipulate correct nodes.
6) To update `_bucket' for new linked list, you do as:
+ _idx = _hash & _cache->mask; \
+ if ( _idx < _cache->p ) \
+ _idx = _hash & ( _cache->mask*2 + 1 ); \
+ _bucket = _pnode = _cache->buckets + _idx; \
Then, to update `_pnode' for new linked list, new linked list is scanned
until "the found node", as:
+ while(*_pnode != node) \
+ \
+ _node_cmp = *_pnode; \
+ if(NULL != _node_cmp) \
+ { \
+ _pnode = &_node_cmp->link; \
+ } \
+ else \
+ { \
+ FT_ERROR(("oops!!! node missing")); \
+ goto _NewNode; \
+ } \
+ } \
After the update of `_bucket' and `_pnode', the reordering of
the nodes in existing code is executed.
|
Sat 25 Dec 2010 08:56:58 PM UTC, comment #7:
Thanks. Indeed, it seems that the code needs some clean-up. I'm assigning your report to Toshiya-san who has recently worked on the cache code. However, it will take some days until he has time to work on it.
|
Sat 25 Dec 2010 06:59:58 PM UTC, comment #6:
It is correct that the lines appear twice. It is not a copy paste error.
The reasoning is :
Consider the call "_nodcomp( _node, query, _cache )" inside the for loop. Take the case when this call refers to FTC_SNode_Compare:
Deep inside FTC_SNode_Compare there is call for
FTC_CACHE_TRYLOOP which tries to free up nodes, which inturn leads to call of function ftc_cache_resize() deep inside the cache,which modifies p, mask and slack parameters of the cache. So it is necessary to calculate _idx (bucket where node is located) again. Hence the lines are required.
Things become clear if we start analysing the code from FTC_SBitCache_Lookup in ftcbasic.c.
|
Sat 25 Dec 2010 04:26:47 PM UTC, comment #5:
I've now looked into your changes, and I see a problem:
These lines
_idx = _hash & _cache->mask;
if ( _idx < _cache->p )
_idx = _hash & ( _cache->mask*2 + 1 );
_bucket = _pnode = _cache->buckets + _idx;
appear twice, apparently without reason. I thus wonder whether the `while' loop shall replace the `for' loop since it looks like a copy&paste error... Please comment.
My knowledge of the FreeType cache code is very limited, thus I can't fix this by myself easily.
|
Sat 25 Dec 2010 03:11:42 PM UTC, comment #4:
Oops, please forget my last remark, it is nonsense.
|
Sat 25 Dec 2010 02:26:45 PM UTC, comment #3:
Thanks for the information. Just to be sure: Here in this bug report you are referring to patch #7422, right? Right now there is no link between the patch and the bug report.
|
Sat 25 Dec 2010 01:56:52 PM UTC, comment #2:
It is not possible for me to upgrade to 2.4.4 now and test it. I took a look at files from 2.4.4 version. My understanding is that there is no change to sbit cache with respect to its functionality from 2.3.5. So this should persist in 2.4.4 also. One should be able to observe this issue when memory becomes very low and, more and more nodes need to be flushed to load a new node using snode compare function.
Also a code review should reveal this defect clearly.
|
Wed 22 Dec 2010 07:05:31 AM UTC, comment #1:
Thanks for the report. However, looking at your changed ftccache.h, you are using a FreeType version which is older than three years. Please try the latest release, 2.4.4, and check whether your problem is still present. If yes, please provide a diff (or a complete new file) relative to the recent version.
|
Sat 18 Dec 2010 08:52:25 PM UTC, original submission:
There is a problem with FTC_CACHE_LOOKUP_CMP in ftccache.h. Node compare function of sbit cache does the flushing of nodes in case of out of memory error. So it can destroy the node previous to the node in question. In such a case the operation of putting the node on top in FTC_CACHE_LOOKUP_CMP makes the list circular and hence an infinite loop in the next call of FTC_SBitCache_Lookup function. Also here memory leak can happen. Please find the file with defect fix attached. Not a good solution though from design perspective. But it works for sure.
Also one suggestion from my end is: in sbit node compare function rather than incrementing the ref_count and then decrementing, a backup can be taken and the count made greater than 0 and after flushing it can be restored back to previous value. Since ref_count is a signed value. In case it goes below 0, then the suggested methodology prevents the node in question from deletion.
Also as my understanding of object oreintation and bit of freetype code, I think that sbit,cmap, image or any other cache added inherit the cache module(ftccache.c). So they should never try to do operations does by cache by themselves. This is not followed for sbit cache node compare function implementation. This function tries to free nodes by itself. I consider this is the root cause for the above defect.
|