nasty bug in bsearch() in b17.1 under Windows'95????

nasty bug in bsearch() in b17.1 under Windows'95????

[Mumit Khan]

I believe there is a nasty bug in bsearch that gets tickled whenever the
item to be searched for is "greater" than the last item in the list
supplied. Take the following trivial code:

=== bsearch-bug.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

char *mynames[] = {"bb", "cc", "za"};

#define ARRAY_SIZE(x) sizeof(x)/sizeof((x)[0])

static int compare_name(const void *name, const void *item_name) {
    const char *x_name = (char*) name;
    const char *y_name = *((char**) item_name);
    /* in gdb, do a display on both x_name and y_name */
    return strcmp(x_name, y_name);
}

int main(int argc, char* argv[]) {
    char *what = (argc == 2) ? argv[1] : "zb";
    char *item = bsearch(what, &mynames[0], ARRAY_SIZE (mynames),
        sizeof (mynames[0]), (void*) compare_name);
    printf ("Item %s %s\n", what, (item) ? "FOUND" : "NOT FOUND");
    return 0;
}

=== bsearch-bug.c

% gcc -g -o bsearch-bug.exe bsearch.c
% ./bsearch aa
Item aa NOT FOUND
% ./bsearch bb
Item bb FOUND
% ./bsearch za
Item za FOUND
% ./bsearch zb
Item zb NOT FOUND		<<- this is expected, but it's buggy!

The last case is where the bug is. The comparison function is passed a
pointer that is *one past* the last item. To see it, simply use the
display feature in gdb and watch for the addresses being passed to
compare_name when trying to find "zb".

Could someone please verify this on their system? Mine is rather hacked
up and I would like a second opinion before calling it a bug.
Unfortunately I'm on the road with no ready access to the source tree,
but hopefully will post a fix when I get back in a day or two (unless
of course the bug is due to my own changes :-).

fyi, this breaks g77 quite horribly when compiling anything with
a subroutine or function name of "zsw" or greater.

Cheers
Mumit -- khan@xraylith.wisc.edu
http://www.xraylith.wisc.edu/~khan/
-
For help on using this list, send a message to
"gnu-win32-request@cygnus.com" with one line of text: "help".

Re: nasty bug in bsearch() in b17.1 under Windows'95????

[Jim Balter]

Mumit Khan wrote:
> 
> I believe there is a nasty bug in bsearch that gets tickled whenever the
> item to be searched for is "greater" than the last item in the list
> supplied. Take the following trivial code:

The bsearch.c in newlib contains a quite explicit and quite erroneous
comparison to the item one past the last range whenever the key isn't
found.  Normally this is merely pointless extra work, but if the key is
greater than the last element, then it is an out of bounds reference,
just as you have discovered.  The "easiest" fix is to simply remove the
lines

  if (compar (key, base) == 0)
    return (_PTR) base;


from before the final return NULL.  A better fix is to replace bsearch.c
with the simpler, more efficient, and more comprehendable one from
glibc (in fact, all of newlib should be replaced with glibc, but that's
another story):


/* Copyright (C) 1991, 1992 Free Software Foundation, Inc.
This file is part of the GNU C Library.

The GNU C Library is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.

The GNU C Library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Library General Public License for more details.

You should have received a copy of the GNU Library General Public
License along with the GNU C Library; see the file COPYING.LIB.  If
not, write to the Free Software Foundation, Inc., 675 Mass Ave,
Cambridge, MA 02139, USA.  */

/*
I've added underscores in front of the macros so it can compile under
gnu-win32 without the GNU ansidecl.h.

#include <ansidecl.h>
*/
#include <stdlib.h>


/* Perform a binary search for KEY in BASE which has NMEMB elements
   of SIZE bytes each.  The comparisons are done by (*COMPAR)().  */
_PTR
_DEFUN(bsearch, (key, base, nmemb, size, compar),
      register _CONST _PTR key _AND register _CONST _PTR base _AND
      size_t nmemb _AND register size_t size _AND
      register int _EXFUN((*compar), (_CONST _PTR, _CONST _PTR)))
{
  register size_t l, u, idx;
  register _CONST _PTR p;
  register int comparison;

  l = 0;
  u = nmemb;
  while (l < u)
    {
      idx = (l + u) / 2;
      p = (_PTR) (((_CONST char *) base) + (idx * size));
      comparison = (*compar)(key, p);
      if (comparison < 0)
	u = idx;
      else if (comparison > 0)
	l = idx + 1;
      else
	return (_PTR) p;
    }

  return NULL;
}

--
<J Q B>
-
For help on using this list, send a message to
"gnu-win32-request@cygnus.com" with one line of text: "help".

newlib vs glibc

[Fergus Henderson]

Jim Balter wrote:
> 
> [...bug in bsearch()...]  A better fix is to replace bsearch.c
> with the simpler, more efficient, and more comprehendable one from
> glibc (in fact, all of newlib should be replaced with glibc, but that's
> another story):

So why do we have two C libraries?

-- 
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: < http://www.cs.mu.oz.au/~fjh >   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.
-
For help on using this list, send a message to
"gnu-win32-request@cygnus.com" with one line of text: "help".

Re: nasty bug in bsearch() in b17.1 under Windows'95????

[Mumit Khan]

Jim Balter <jqb@netcom.com> writes:
> 
> The bsearch.c in newlib contains a quite explicit and quite erroneous
> comparison to the item one past the last range whenever the key isn't
> found.  Normally this is merely pointless extra work, but if the key is
> greater than the last element, then it is an out of bounds reference,
> just as you have discovered.  The "easiest" fix is to simply remove the
> lines
> 
>   if (compar (key, base) == 0)
>     return (_PTR) base;
> 

Exactly. Just looked at the source, and it's quite obvious. As you
mention, it also does an extra comparison for no reason whatsoever
in the other cases.

Here's the trivial patch, which took non-trivial number of hours
to find ;-) debugging f771 on a '95 box is no fun. 

*** bsearch.c.~1	Tue Mar 25 22:47:42 1997
--- bsearch.c	Tue Mar 25 22:47:46 1997
*************** _DEFUN (bsearch, (key, base, nmemb, size
*** 94,100 ****
      }
  
-   if (compar (key, base) == 0)
-     return (_PTR) base;
- 
    return NULL;
  }
--- 94,97 ----

Regards,
Mumit -- khan@xraylith.wisc.edu
http://www.xraylith.wisc.edu/~khan/
-
For help on using this list, send a message to
"gnu-win32-request@cygnus.com" with one line of text: "help".

Re: newlib vs glibc

[Jim Balter]

Fergus Henderson wrote:
> 
> Jim Balter wrote:
> >
> > [...bug in bsearch()...]  A better fix is to replace bsearch.c
> > with the simpler, more efficient, and more comprehendable one from
> > glibc (in fact, all of newlib should be replaced with glibc, but that's
> > another story):
> 
> So why do we have two C libraries?

I'm not sure what you mean by "we".  Cygnus (Steve Chamberlain?)
decided for some reason, when creating gnu-win32, to put together their
own "newlib" from Berkeley code and various other sources, rather than
use glibc.  Perhaps glibc wasn't in good shape at the time or newlib was
already used internally at Cygnus or ...; the answers to such questions
often involve complex and ad hoc history.  There are various couplings
between cygwin.dll and newlib such that one cannot casually rip out
newlib and replace it with something else.  Certainly not when that
something else is glibc, which has its own framework for coupling with
the lower level system.  Nonetheless, converting to glibc might well be
worth it in the long run.  I have my own plans for a POSIX dll that I am
pursuing, and one of my requirements is that it be integrated into
glibc.  Some of that effort might also work toward making it easier to
integrate cygwin.dll with glibc, but that's not my main goal.  I just
threw out a couple of provocative comments about glibc to see if anyone
would take the bait; glibc is of significantly higher quality than
newlib, partly because it has a wider user base, partly because it is
higher on the evolutionary tree, and partly (largely) for the kind of
talent (e.g., Roland McGrath, Ulrich Drepper) involved in it (the sort
that GNU projects tend to draw).

--
<J Q B>
-
For help on using this list, send a message to
"gnu-win32-request@cygnus.com" with one line of text: "help".

Re: nasty bug in bsearch()

[Geoffrey Noer]

Mumit Khan wrote a very long time ago:
> 
> I believe there is a nasty bug in bsearch that gets tickled whenever the
> item to be searched for is "greater" than the last item in the list
> supplied. Take the following trivial code:
[...]

This will be fixed in the next release.  I just rewrote
newlib/libc/stdlib/bsearch.c using a better algorithm.

-- 
Geoffrey Noer
noer@cygnus.com
-
For help on using this list (especially unsubscribing), send a message to
"gnu-win32-request@cygnus.com" with one line of text: "help".