Last Comment Bug 917955 - crash in PL_strncasecmp | nsCaseInsensitiveCStringComparator::operator()(char const*, char const*, unsigned int, unsigned int) during newsgroup subscribe
: crash in PL_strncasecmp | nsCaseInsensitiveCStringComparator::operator()(char...
Status: RESOLVED FIXED
: crash, regression, topcrash
Product: MailNews Core
Classification: Components
Component: Networking: NNTP (show other bugs)
: 24
: All All
: -- critical with 2 votes (vote)
: Thunderbird 27.0
Assigned To: Alfred Peters
:
:
Mentors:
: 918346 (view as bug list)
Depends on:
Blocks: 872497
  Show dependency treegraph
 
Reported: 2013-09-18 10:58 PDT by Wayne Mery (:wsmwk, NI for questions)
Modified: 2013-10-09 13:38 PDT (History)
14 users (show)
See Also:
Crash Signature:
QA Whiteboard:
Iteration: ---
Points: ---
fixed
fixed
+
fixed


Attachments
News subscribe dialog TB 17.0.8 with filter (28.19 KB, image/png)
2013-09-22 05:33 PDT, Alfred Peters
no flags Details
News subscribe dialog TB 24.0 with filter (28.27 KB, image/png)
2013-09-22 05:44 PDT, Alfred Peters
no flags Details
Correction of the comparison function LessThen () in class nsCStringLowerCaseComparator (1.15 KB, patch)
2013-09-28 12:11 PDT, Alfred Peters
Pidgeot18: review+
Details | Diff | Splinter Review
Correction of the comparison function LessThen() in class nsCStringLowerCaseComparator (1.15 KB, patch)
2013-09-30 10:22 PDT, Alfred Peters
infofrommozilla: review+
standard8: approval‑comm‑aurora+
standard8: approval‑comm‑beta+
standard8: approval‑comm‑esr24+
Details | Diff | Splinter Review

Description Wayne Mery (:wsmwk, NI for questions) 2013-09-18 10:58:47 PDT
This bug was filed from the Socorro interface and is 
report bp-e5104f83-9047-4a65-b1ca-2f9912130908. 
Appears to be regression in TB24.
#1 crash so far

=============================================================
"I tried to subscribe to another newsgroup and typed "comp" as the start of the name. Then I noticed that was incorrect, and used backspace to erase all those characters. It got down to "c" remaining, then crashed."  Robert

0	plc4.dll	PL_strncasecmp	nsprpub/lib/libc/src/strcase.c
1	xul.dll	nsCaseInsensitiveCStringComparator::operator()(char const *,char const *,unsigned int,unsigned int)	xpcom/string/src/nsStringComparator.cpp
2	xul.dll	Compare(nsACString_internal const &,nsACString_internal const &,nsCStringComparator const &)	xpcom/string/src/nsTStringComparator.cpp
3	xul.dll	nsCStringLowerCaseComparator::LessThan(nsCString const &,nsCString const &)	mailnews/news/src/nsNntpIncomingServer.cpp
4	xul.dll	nsTArray_Impl<nsCString,nsTArrayInfallibleAllocator>::Compare<nsCStringLowerCaseComparator>(void const *,void const *,void *)	objdir-tb/mozilla/dist/include/nsTArray.h
5	xul.dll	med3	objdir-tb/mozilla/xpcom/build/nsQuickSort.cpp
6	xul.dll	NS_QuickSort	objdir-tb/mozilla/xpcom/build/nsQuickSort.cpp
7	xul.dll	NS_QuickSort	objdir-tb/mozilla/xpcom/build/nsQuickSort.cpp
8	xul.dll	NS_QuickSort	objdir-tb/mozilla/xpcom/build/nsQuickSort.cpp
9	xul.dll	NS_QuickSort	objdir-tb/mozilla/xpcom/build/nsQuickSort.cpp
10	xul.dll	NS_QuickSort	objdir-tb/mozilla/xpcom/build/nsQuickSort.cpp 

bp-d3ea40bb-d71b-4805-a174-ae3212130918 another user, if we need someone to reproduce
Comment 1 Wayne Mery (:wsmwk, NI for questions) 2013-09-18 11:01:00 PDT
#6 crash for Tb25 aurora
Comment 2 Makoto Kato [:m_kato] 2013-09-18 18:50:56 PDT
stack size of windows is 1MB, but Linux is 8MB....
Comment 3 stefan.blumenrath 2013-09-19 06:24:24 PDT
Crashes also on Seamonkey 2.21

See crash report: 

ID: f1922010-b159-4398-bed1-9a1ed2130919
Signature: PL_strncasecmp | nsCaseInsensitiveCStringComparator::operator()(char const*, char const*, unsigned int, unsigned int)
Comment 4 Wayne Mery (:wsmwk, NI for questions) 2013-09-19 09:14:23 PDT
*** Bug 918346 has been marked as a duplicate of this bug. ***
Comment 5 Alfred Peters 2013-09-22 05:33:20 PDT
Created attachment 808284 [details]
News subscribe dialog TB 17.0.8 with filter

Already in version 17.0.8 was ns_quicksort incorrect. The first element is out of place.
Comment 6 Alfred Peters 2013-09-22 05:44:09 PDT
Created attachment 808285 [details]
News subscribe dialog TB 24.0 with filter

In version TB 24.0 ns_quicksort is totally broken. The elements are completely messed up. The recursion depth is thus obviously much too high.

With many results (~16000) that causes the stack overflow.
Comment 7 Philip Chee 2013-09-22 07:50:37 PDT
I suspect Bug 872497 ( O(n^2) performance in NS_QuickSort)
http://hg.mozilla.org/mozilla-central/rev/aad29aa89237
Comment 8 Alfred Peters 2013-09-22 09:53:13 PDT
(In reply to Philip Chee from comment #7)
> I suspect Bug 872497 ( O(n^2) performance in NS_QuickSort)
> http://hg.mozilla.org/mozilla-central/rev/aad29aa89237

Yes, I can confirm that. Without that patch the result looks like the TB17.0.8 result. :-)
And no crash!
Comment 9 WADA 2013-09-23 05:28:23 PDT
(In reply to Alfred Peters from comment #5)
> The first element is out of place.
(In reply to Alfred Peters from comment #6)
> The elements are completely messed up.

QuickSort is non-stable sort. Patch of Bug 872497 simply removed "do nothing if data is already sorted in ascending order" part only, in order to resolve severe performance problem of NSQuickSort() when (a) first half of data is sorted in descending order and (b) second half of data is also sorted in descending order, and when (a) < (b). Because of "(a) < (b)", swap won't occur, then insertion sort was executed for entire data which is never sorted in ascending order(each half of data is already sorted in descending order).

If reason of crash is non-stable sort, it's simply bug of caller of NS_QuickSort(), isn't it?
Or sort result is incorrect after patch of Bug 872497?
If so, it's problem since initial of NS_QuickSort()?
Or incorrect sort result due to stack over flow after patch of Bug 872497?

(In reply to Alfred Peters from comment #6)
> The recursion depth is thus obviously much too high.

After patch of Bug 872497, NS_QuickSort() merely applies same sort algorythm for random data to "already sorted data in ascending order" and to "already sorted data in descending order".
If big random data, NS_QuickSort() can always produce such deep recursion depth. 

Why Tb still doesn't use std::stable_sort() or std::sort() of C++?
Does problem occur with std::stable_sort() or std::sort() of C++?
Comment 10 WADA 2013-09-23 17:41:48 PDT
(In reply to Alfred Peters from comment #5)
> Created attachment 808284 [details]
> News subscribe dialog TB 17.0.8 with filter
> Already in version 17.0.8 was ns_quicksort incorrect. The first element is out of place.

How many news groups is sorted? Only 27 newsgroups which are seen in the screen shot?
Is newsgroup name already sorted in ascending order when newsgroup names is passed from news server?

Incorrect position is not first element only. alabama.test, which should be first element if ascending order, is also placed at wrong position. If sort key is newsgroup name, this is never due to non-stable sort.
Phenomenon is perhaps next.
  de.mein.test3 is chosen as pivot, then alabama.test at position 0 and de.mein.test3
  at mid are swapped.
  After it, NS_QuickSort() does do sorting of first half(smaller than pivot),
  de.mein.test3, alaba..., ..., de.mein..., alabama.test,
  then NS_QuickSort() does do sorting of second half(larger than pivot),
  de.mein.test3 to netgame.test.
  Because of bug in logic of NS_QuickSort() since initial of NS_QuickSort(),
  sort result is incorrect.
  (when N == 2**n +/- 1, forget to move/swap data at pivot?)
  (when N == 2**n +/- 1, infinite recursive call after patch of Bug 872497?)

Is there any reason to continue using NS_QuickSort() which can surely produce wrong sort result?
If no crash by backout of Bug 872497, wrong sort result is preferable for Tb or acceptable for Tb?
Comment 11 WADA 2013-09-24 00:51:27 PDT
(In reply to Alfred Peters from comment #5)
> Already in version 17.0.8 was ns_quicksort incorrect. The first element is out of place.

Another question.

Sorting of newsgroup name is based on hiearchy of newsgroup name, and order/structure is correctly shown as expected if "filter"(Show items that contain) is not requested.

Is newsgroup names sorted by newsgroup name using NS_QuickSort() after picking up filtered newsgroups when "filter"(Show items that contain) is requested at subscribe of news account?
If yes, is comparison function correctly passed to NS_QuickSort()?

If no, it's "sort entire newsgroups in ascending order" then "pickup filtered newsgroup"?
  If so, how many newsgroups are defined at the news server?

(In reply to Alfred Peters from comment #6)
> With many results (~16000) that causes the stack overflow.

If many newsgroups is sorted, and if data is already fully sorted in ascending order, difference of "recursive call depth" between "before patch" and "afer patch" can be explained.
  Before patch : Insertion sort is applied to long element part at early stage of
                 NS_QuickSort() process, then recursive call depth is 1 at most.
  After  parch : Insertion sort is not applied unles elments length is less than 7.
                 This is same algorithm/logic as one for "fully random data",
                 and is always applied to "fully pre-sorted data in ascending order or
                 descending order" too after the patch.
                 So, "split to two parts then do recursive call for a half part"
                 is repeated until element part length reaches "less than 7".

If crash is due to stack overflow by "too deep recursive call", such stack overflow should always occur also in sorting of fully random data of same element number by NS_QuickSort().
Does problem like "infinte recursive call" occur in NS_Quicksort()?
Comment 12 WADA 2013-09-24 01:05:35 PDT
Crash occurs in StringComparator.
Crash caused by fully broken sort result, instead of stack overflow?
Comment 13 Mark Banner (:standard8, limited time in Dec) 2013-09-26 13:53:23 PDT
(In reply to WADA from comment #12)
> Crash occurs in StringComparator.
> Crash caused by fully broken sort result, instead of stack overflow?

No, the stacks on crash-stacks say EXCEPTION_STACK_OVERFLOW
Comment 14 Alfred Peters 2013-09-28 12:11:18 PDT
Created attachment 811557 [details] [diff] [review]
Correction of the comparison function LessThen () in class nsCStringLowerCaseComparator

The incorrect comparison function causes the worst case of the quicksort algorithm, which caused the stack overflow.
Comment 15 Joshua Cranmer [:jcranmer] 2013-09-30 06:36:45 PDT
Comment on attachment 811557 [details] [diff] [review]
Correction of the comparison function LessThen () in class nsCStringLowerCaseComparator

Review of attachment 811557 [details] [diff] [review]:
-----------------------------------------------------------------

::: mailnews/news/src/nsNntpIncomingServer.cpp
@@ +73,5 @@
>    }
>  
>    bool LessThan(const nsCString &a, const nsCString &b) const
>    {
> +    return (Compare(a, b, nsCaseInsensitiveCStringComparator()) < 0);

nit: Extraneous parentheses.
Comment 16 Alfred Peters 2013-09-30 10:22:43 PDT
Created attachment 812134 [details] [diff] [review]
Correction of the comparison function LessThen() in class nsCStringLowerCaseComparator

> > +    return (Compare(a, b, nsCaseInsensitiveCStringComparator()) < 0);
> 
> nit: Extraneous parentheses.

OK, corrected.
Comment 17 Alfred Peters 2013-09-30 10:45:18 PDT
(In reply to Alfred Peters from comment #16)
> Created attachment 812134 [details] [diff] [review]

> > nit: Extraneous parentheses.

> OK, corrected.

I'm not the real reviewer. Could this be a problem?

If not, could someone set the checkin-needed keyword. I do not have sufficient rights to do so.
Comment 18 Magnus Melin 2013-09-30 10:51:01 PDT
That's ok. Especially when carrying a review forward like that for nits fixed, it's good to add the reviewer also in the hg commit message. Like r=jcranmer.
Comment 19 Ryan VanderMeulen [:RyanVM] 2013-10-01 07:03:53 PDT
https://hg.mozilla.org/comm-central/rev/b84ca03296e3
Comment 20 David E. Ross 2013-10-05 08:27:14 PDT
When is Thunderbird 27.0 scheduled for release to end users?  This is a critical bug.
Comment 21 :aceman 2013-10-05 08:43:28 PDT
TB27 will never be released to end users. But this should go into TB24.0.1 that will go soon.
Comment 22 Mark Banner (:standard8, limited time in Dec) 2013-10-09 13:22:28 PDT
Comment on attachment 812134 [details] [diff] [review]
Correction of the comparison function LessThen() in class nsCStringLowerCaseComparator

[Triage Comment]
We want to take this onto esr for 24.0.1 to get it fixed there.

Note You need to log in before you can comment on or make changes to this bug.