* nasty bug in bsearch() in b17.1 under Windows'95???? @ 1997-03-24 22:51 Mumit Khan 1997-03-25 6:06 ` Jim Balter 1997-07-21 17:47 ` nasty bug in bsearch() Geoffrey Noer 0 siblings, 2 replies; 6+ messages in thread From: Mumit Khan @ 1997-03-24 22:51 UTC (permalink / raw) To: gnu-win32; +Cc: noer 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". ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: nasty bug in bsearch() in b17.1 under Windows'95???? 1997-03-24 22:51 nasty bug in bsearch() in b17.1 under Windows'95???? Mumit Khan @ 1997-03-25 6:06 ` Jim Balter 1997-03-26 1:11 ` newlib vs glibc Fergus Henderson 1997-03-26 10:43 ` nasty bug in bsearch() in b17.1 under Windows'95???? Mumit Khan 1997-07-21 17:47 ` nasty bug in bsearch() Geoffrey Noer 1 sibling, 2 replies; 6+ messages in thread From: Jim Balter @ 1997-03-25 6:06 UTC (permalink / raw) To: Mumit Khan; +Cc: gnu-win32, noer 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". ^ permalink raw reply [flat|nested] 6+ messages in thread
* newlib vs glibc 1997-03-25 6:06 ` Jim Balter @ 1997-03-26 1:11 ` Fergus Henderson 1997-03-27 20:59 ` Jim Balter 1997-03-26 10:43 ` nasty bug in bsearch() in b17.1 under Windows'95???? Mumit Khan 1 sibling, 1 reply; 6+ messages in thread From: Fergus Henderson @ 1997-03-26 1:11 UTC (permalink / raw) To: gnu-win32 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". ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: newlib vs glibc 1997-03-26 1:11 ` newlib vs glibc Fergus Henderson @ 1997-03-27 20:59 ` Jim Balter 0 siblings, 0 replies; 6+ messages in thread From: Jim Balter @ 1997-03-27 20:59 UTC (permalink / raw) To: Fergus Henderson; +Cc: gnu-win32 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". ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: nasty bug in bsearch() in b17.1 under Windows'95???? 1997-03-25 6:06 ` Jim Balter 1997-03-26 1:11 ` newlib vs glibc Fergus Henderson @ 1997-03-26 10:43 ` Mumit Khan 1 sibling, 0 replies; 6+ messages in thread From: Mumit Khan @ 1997-03-26 10:43 UTC (permalink / raw) To: Jim Balter; +Cc: gnu-win32 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". ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: nasty bug in bsearch() 1997-03-24 22:51 nasty bug in bsearch() in b17.1 under Windows'95???? Mumit Khan 1997-03-25 6:06 ` Jim Balter @ 1997-07-21 17:47 ` Geoffrey Noer 1 sibling, 0 replies; 6+ messages in thread From: Geoffrey Noer @ 1997-07-21 17:47 UTC (permalink / raw) To: Mumit Khan; +Cc: gnu-win32, 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". ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~1997-07-21 17:47 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 1997-03-24 22:51 nasty bug in bsearch() in b17.1 under Windows'95???? Mumit Khan 1997-03-25 6:06 ` Jim Balter 1997-03-26 1:11 ` newlib vs glibc Fergus Henderson 1997-03-27 20:59 ` Jim Balter 1997-03-26 10:43 ` nasty bug in bsearch() in b17.1 under Windows'95???? Mumit Khan 1997-07-21 17:47 ` nasty bug in bsearch() Geoffrey Noer
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).