[PATCH] search: call user compare with "correct" order params

[PATCH] search: call user compare with "correct" order params

[Karl Palsson]

From: Karl Palsson <karlp@remake.is>

IEEE Std 1003.1, 2013 Edition only defines the two params to the
user callback as, "The compar argument points to a comparison function
which the application shall supply (for example, strcmp()). It is called
with two arguments that point to the elements being compared."

Both uclibc and glibc provide the arguments as, "
The comparison function referenced by compar is expected to have two
arguments which point to the key object and to an array member, in that order
"

Musl currently provides the arguments as array member, then key object.
While this is strictly compliant with the standard, it's equally
compliant to have the parameters in the other order.  If you are using
lfind to search a list of complex structures where the key is not the
same type as each entry, having these parameters arrive in unexpectd
order can/will result in segfaults.

=> Swap the order of the arguments to the user function, maintaining
equal compatibility with the standard, and gaining compatibility with
uclibc and glibc.

Signed-off-by: Karl Palsson <karlp@etactica.com>
---
 src/search/lsearch.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

Please CC me on replies, I'm not (currently) a subscriber

diff --git a/src/search/lsearch.c b/src/search/lsearch.c
index 63f3192..5eb5cc2 100644
--- a/src/search/lsearch.c
+++ b/src/search/lsearch.c
@@ -9,7 +9,7 @@ void *lsearch(const void *key, void *base, size_t *nelp, size_t width,
 	size_t i;
 
 	for (i = 0; i < n; i++)
-		if (compar(p[i], key) == 0)
+		if (compar(key, p[i]) == 0)
 			return p[i];
 	*nelp = n+1;
 	return memcpy(p[n], key, width);
@@ -23,7 +23,7 @@ void *lfind(const void *key, const void *base, size_t *nelp,
 	size_t i;
 
 	for (i = 0; i < n; i++)
-		if (compar(p[i], key) == 0)
+		if (compar(key, p[i]) == 0)
 			return p[i];
 	return 0;
 }
-- 
2.4.3

Re: [PATCH] search: call user compare with "correct" order params

[Rich Felker]

On Wed, Feb 24, 2016 at 12:12:29PM +0000, Karl Palsson wrote:
> From: Karl Palsson <karlp@remake.is>
> 
> IEEE Std 1003.1, 2013 Edition only defines the two params to the
> user callback as, "The compar argument points to a comparison function
> which the application shall supply (for example, strcmp()). It is called
> with two arguments that point to the elements being compared."
> 
> Both uclibc and glibc provide the arguments as, "
> The comparison function referenced by compar is expected to have two
> arguments which point to the key object and to an array member, in that order
> "
> 
> Musl currently provides the arguments as array member, then key object.
> While this is strictly compliant with the standard, it's equally
> compliant to have the parameters in the other order.  If you are using
> lfind to search a list of complex structures where the key is not the
> same type as each entry, having these parameters arrive in unexpectd
> order can/will result in segfaults.
> 
> => Swap the order of the arguments to the user function, maintaining
> equal compatibility with the standard, and gaining compatibility with
> uclibc and glibc.

I've read some of the scrollback from the discussion of this on IRC,
and I think:

1. Regardless of whether the patch is accepted or not, applications
   using this interface in non-portable ways should be fixed.

2. As you said, lfind/lsearch are useless functions. Aside from the
   order of the arguments being unspecified (which doesn't hurt code
   using them in the intended way), they're just going to be a lot
   slower than inlining the comparison in your own for loop.

Is there existing software that's affected by this issue for which
it's hard to get a fix upstream?

Rich

Re: [PATCH] search: call user compare with "correct" order params

[Karl Pálsson]

On Wed, 2016-02-24 at 12:41 -0500, Rich Felker wrote:

> I've read some of the scrollback from the discussion of this on IRC,
> and I think:
> 
> 1. Regardless of whether the patch is accepted or not, applications
>    using this interface in non-portable ways should be fixed.
> 
> 2. As you said, lfind/lsearch are useless functions. Aside from the
>    order of the arguments being unspecified (which doesn't hurt code
>    using them in the intended way), they're just going to be a lot
>    slower than inlining the comparison in your own for loop.
> 
> Is there existing software that's affected by this issue for which
> it's hard to get a fix upstream?

Given that musl has two choices:

a) compliant with POSIX
b) compliant with POSIX, uclibc, glibc, bsdlibc

I find it rather disappointing that the first response is "your
application is wrong" rather than, "yeah, option (b) does sound better"

Given how vague the actual posix docs are on these functions, yes, it's
a bad idea to ever use them.  However, given how vague the actual posix
docs are, I think it's hard to say whether the way I was using lfind
was actually not allowed.  (lsearch, sure, it has to insert)
Regardless, I have "fixed" my application.  Maybe you could "fix" musl
to be as equally compliant as ever before, and completely cut off
anyone else ever having to even have this discussion again?

Sincerely,
Karl Palsson

Re: [PATCH] search: call user compare with "correct" order params

[dalias]

On Tue, Mar 08, 2016 at 11:43:03AM +0000, Karl Pálsson wrote:
> On Wed, 2016-02-24 at 12:41 -0500, Rich Felker wrote:
> 
> > I've read some of the scrollback from the discussion of this on IRC,
> > and I think:
> > 
> > 1. Regardless of whether the patch is accepted or not, applications
> >    using this interface in non-portable ways should be fixed.
> > 
> > 2. As you said, lfind/lsearch are useless functions. Aside from the
> >    order of the arguments being unspecified (which doesn't hurt code
> >    using them in the intended way), they're just going to be a lot
> >    slower than inlining the comparison in your own for loop.
> > 
> > Is there existing software that's affected by this issue for which
> > it's hard to get a fix upstream?
> 
> Given that musl has two choices:
> 
> a) compliant with POSIX
> b) compliant with POSIX, uclibc, glibc, bsdlibc
> 
> I find it rather disappointing that the first response is "your
> application is wrong" rather than, "yeah, option (b) does sound better"
> 
> Given how vague the actual posix docs are on these functions, yes, it's
> a bad idea to ever use them.  However, given how vague the actual posix
> docs are, I think it's hard to say whether the way I was using lfind
> was actually not allowed.  (lsearch, sure, it has to insert)
> Regardless, I have "fixed" my application.  Maybe you could "fix" musl
> to be as equally compliant as ever before, and completely cut off
> anyone else ever having to even have this discussion again?

I'm not rejecting it; I'm just backlogged with lots of things and was
waiting for feedback from the community on this. Adding new contracts
beyond the specified contract for an interface is a big deal and
sometimes has unforseen consequences. This is probably not such a
case, but we've been bitten by it before -- adding a nonstandard
behavior only to find out later that properly supporting it imposes
costly constraints elsewhere. It wasn't my intent with the previous
reply to be hostile, just to express that the portable solution is
already better for multiple reasons (especially, performance and
simplicity in the caller).

Rich