738533 - Review NS_QuickSort() documentation and uses: Solaris, qsort, ...

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[Serge Gautherie (:sgautherie)]

http://mxr.mozilla.org/mozilla/source/xpcom/glue/nsQuickSort.h
{
39 /* We need this because Solaris' version of qsort is broken and
40  * causes array bounds reads.
41  */
}

http://mxr.mozilla.org/mozilla-central/source/xpcom/glue/nsQuickSort.cpp
{
32 /* We need this because Solaris' version of qsort is broken and
33  * causes array bounds reads.
34  */
}

***

(In reply to Wan-Teh Chang from bug 72196 comment #3)
> Mozilla should consider removing NS_QuickSort and just use
> qsort in the standard C library.  The comments in the source
> file:
>     /* We need this because Solaris' version of qsort is broken and
>      * causes array bounds reads.
>      */
> turned out to be wrong -- we were calling qsort with an
> incorrect comparison function which only broke the Solaris
> implementation of qsort.

(In reply to Jonas Sicking (:sicking) from bug 72196 comment #5)
> qsort doesn't provide a transparent |void* data| parameter that gets passed
> on
> to the compare-function. At least transformiix uses this, possibly others
> too.

Iiuc,
1) The Solaris comment(s) should be removed there too.
   And possibly replaced by the actual use case(s).
2) Replace morkQuickSort() with NS_QuickSort(), or document why that can't be.
3) Should review all (qsort() and) QuickSort() calls, wrt which function they should use.

http://mxr.mozilla.org/comm-central/search?string=qsort&case=on
"Found 103 matching lines in 55 files"
http://mxr.mozilla.org/comm-central/search?string=QuickSort&case=on
"Found 92 matching lines in 39 files"

Comment 1

[Alexander Enaldiev]

Attachment: Fix patch

Shame, but I'm not sure, that all target files contains in #include directives for <cstdlib> lib, which contains qsort(...)

Comment 2

[Alexander Enaldiev]

Need patch review. (especially `coz this is my first resolved bug!)

Comment 3

[Serge Gautherie (:sgautherie)]

Comment on attachment 612985 [details] [diff] [review]
Fix patch

(In reply to Serge Gautherie (:sgautherie) from comment #0)
> 3) Should review all (qsort() and) QuickSort() calls, wrt which function
> they should use.

Iiuc, what this patch does is to replace NS_QuickSort(..., <null>) calls with qsort() calls.

***

(In reply to Paladine from comment #1)
> Shame, but I'm not sure, that all target files contains in #include
> directives for <cstdlib> lib, which contains qsort(...)

I'm not sure what you meant.
Does this patch compile?

Comment 4

[Alexander Enaldiev]

Attachment: replacement for NS_QuickSort

renewed.
>1) The Solaris comment(s) should be removed there too.
>   And possibly replaced by the actual use case(s).
>2) Replace morkQuickSort() with NS_QuickSort(), or document why that can't be.

Didn't saw anything of it.

>3) Should review all (qsort() and) QuickSort() calls, wrt which function they >should use.
When I saw causeless usage of NS_QuickSort, i removed it. 

Is I understanding the task (for this bug) right? Just saw the tag [good first bug] :)

Comment 5

[Alexander Enaldiev]

Btw for me main question is: NS_QuickSort() was developed to provide qsort() on solaris? I have different interface (additional void* context parameter). I don't think, it can be replaced that way to easily.

Comment 6

[Benjamin Smedberg]

Comment on attachment 613123 [details] [diff] [review]
replacement for NS_QuickSort

Thank you.

Comment 7

[:Ms2ger (he/him; ⌚ UTC+1/+2)]

Comment on attachment 613123 [details] [diff] [review]
replacement for NS_QuickSort

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

::: layout/style/nsCSSProps.cpp
@@ +220,5 @@
>  
>    // Sort with lowest count at the start and highest at the end, and
>    // within counts sort in reverse property index order.
> +  qsort(&subpropCounts, ArrayLength(subpropCounts),
> +		sizeof(subpropCounts[0]), SortPropertyAndCount);

Please align the second line such that the 's' in sizeof is below the '&'.

Comment 8

[Alexander Enaldiev]

Attachment: qsort() instead of NS_QuickSort() in common cases

done.
btw I red "Mozilla Code styling" and didn't saw this moment with parameters alignment :) Is it so obvious? ;)

Comment 9

[Mark Finkle (:mfinkle) (use needinfo?)]

Comment on attachment 613800 [details] [diff] [review]
qsort() instead of NS_QuickSort() in common cases

we think this could wait for 15

Comment 10

[Ryan VanderMeulen [:RyanVM]]

FYI, toolkit/components/url-classifier/Entries.h doesn't exist since bug 673470 was backed out. I added a note to that bug about it and will land this patch without that change when the tree re-opens.

Comment 11

[Ryan VanderMeulen [:RyanVM]]

Actually, this doesn't build on Try.

../../../../toolkit/components/filepicker/nsFileView.cpp: In member function 'void nsFileView::SortArray(nsISupportsArray*)':
../../../../toolkit/components/filepicker/nsFileView.cpp:1000: error: invalid conversion from 'int (*)(const void*, const void*)' to 'int (*)(const void*, const void*, void*)'
../../../../toolkit/components/filepicker/nsFileView.cpp:1003: error: invalid conversion from 'int (*)(const void*, const void*)' to 'int (*)(const void*, const void*, void*)'
../../../../toolkit/components/filepicker/nsFileView.cpp:1006: error: invalid conversion from 'int (*)(const void*, const void*)' to 'int (*)(const void*, const void*, void*)'
../../../../toolkit/components/filepicker/nsFileView.cpp:1022: error: invalid conversion from 'int (*)(const void*, const void*, void*)' to 'int (*)(const void*, const void*)'

Comment 12

[Ryan VanderMeulen [:RyanVM]]

Should have noted that this was a b2g build that failed, which is gcc 4.4.3 I believe.

Comment 13

[Gian-Carlo Pascutto [:gcp]]

>FYI, toolkit/components/url-classifier/Entries.h doesn't exist since bug 673470 
>was backed out. I added a note to that bug about it and will land this patch 
>without that change when the tree re-opens.

This bug doesn't seem to have made it to a landing, but I put a fix in bug 673470 for using qsort:
https://hg.mozilla.org/integration/mozilla-inbound/rev/ba9ae0fe8297

Comment 14

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/ba9ae0fe8297

Comment 15

[:aceman]

I also do not understand this bug. The description was to replace qsort with NS_QuickSort. Why is the patch the other way round? What is the proper thing to do here?