NetBSD Problem Report #36816

From mouse@Sparkle.Rodents.Montreal.QC.CA  Tue Aug 21 17:01:05 2007
Return-Path: <mouse@Sparkle.Rodents.Montreal.QC.CA>
Received: from mail.netbsd.org (mail.netbsd.org [204.152.190.11])
	by narn.NetBSD.org (Postfix) with ESMTP id 64B4163B8FC
	for <gnats-bugs@gnats.NetBSD.org>; Tue, 21 Aug 2007 17:01:05 +0000 (UTC)
Message-Id: <200708211701.NAA17103@Sparkle.Rodents.Montreal.QC.CA>
Date: Tue, 21 Aug 2007 13:01:03 -0400 (EDT)
From: der Mouse <mouse@Rodents.Montreal.QC.CA>
Reply-To: mouse@Rodents.Montreal.QC.CA
To: gnats-bugs@NetBSD.org
Subject: [dM] sort -n mis-sorts -ve numbers
X-Send-Pr-Version: 3.95

>Number:         36816
>Category:       bin
>Synopsis:       [dM] sort -n mis-sorts -ve numbers
>Confidential:   no
>Severity:       serious
>Priority:       high
>Responsible:    bin-bug-people
>State:          closed
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Tue Aug 21 17:05:00 +0000 2007
>Closed-Date:    Sat Aug 22 11:18:25 +0000 2009
>Last-Modified:  Wed Oct 14 20:45:10 +0000 2009
>Originator:     der Mouse
>Release:        NetBSD 3.1
>Organization:
	Dis-
>Environment:
This has been seen on three systems:

System: NetBSD Omega.Rodents.Montreal.QC.CA 3.1 NetBSD 3.1 (OMEGA) #2: Sun Aug 19 19:49:12 EDT 2007 mouse@Omega.Rodents.Montreal.QC.CA:/home/mouse/kbuild/OMEGA alpha
Architecture: alpha
Machine: alpha

System: NetBSD Darkstar.Rodents.Montreal.QC.CA 3.1 NetBSD 3.1 (DARKSTAR) #1: Sun Aug 12 13:19:04 EDT 2007  mouse@Darkstar.Rodents.Montreal.QC.CA:/usr/src/sys/arch/hpcmips/compile/DARKSTAR hpcmips
Architecture: mipsel
Machine: hpcmips

System: NetBSD NetBSD-3-1.Rodents.Montreal.QC.CA 3.1 NetBSD 3.1 (GEN31) #0: Sun Aug 12 15:07:30 EDT 2007  mouse@NetBSD-3-1.Rodents.Montreal.QC.CA:/home/mouse/kbuild/GEN31 i386
Architecture: i386
Machine: i386
>Description:
	sort(1) mis-sorts negative numbers under at least some
	circumstances.  I haven't explored the envelope of the bug much.
>How-To-Repeat:
	This behaves the same on all three of the above-mentioned
	machines:

	% echo -512 -511 -510 -509 -508 -501 -500 | /usr/bin/tr \  \\n | sort -n
	-510
	-512
	-511
	-500
	-509
	-508
	-501
	% 
>Fix:
	Unknown.  Could this be related to 30504?  The test case given
	there does not misbehave for me, fwtmbw.

	3.0, 2.0, 1.6.2, 1.6.1 all misbehave as illustrated above for
	me (tested on i386 only).  1.4T does not, interestingly.

/~\ The ASCII				der Mouse
\ / Ribbon Campaign
 X  Against HTML	       mouse@rodents.montreal.qc.ca
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

>Release-Note:

>Audit-Trail:
From: Alan Barrett <apb@cequrux.com>
To: gnats-bugs@NetBSD.org
Cc: netbsd-bugs@NetBSD.org
Subject: Re: bin/36816: [dM] sort -n mis-sorts -ve numbers
Date: Tue, 21 Aug 2007 23:49:28 +0200

 On Tue, 21 Aug 2007, der Mouse wrote:
 > 	sort(1) mis-sorts negative numbers under at least some
 > 	circumstances.  I haven't explored the envelope of the bug much.

 Have you tried the patch in PR 30504?  This looks like one of the
 problems with trailing zeros that was supposed to have been fixed
 by that patch.

 --apb (Alan Barrett)

From: der Mouse <mouse@Rodents.Montreal.QC.CA>
To: Alan Barrett <apb@cequrux.com>
Cc: gnats-bugs@NetBSD.org
Subject: Re: bin/36816: [dM] sort -n mis-sorts -ve numbers
Date: Wed, 22 Aug 2007 00:10:16 -0400 (EDT)

 >> 	sort(1) mis-sorts negative numbers under at least some
 >> 	circumstances.  I haven't explored the envelope of the bug
 >> 	much.
 > Have you tried the patch in PR 30504?  This looks like one of the
 > problems with trailing zeros that was supposed to have been fixed by
 > that patch.

 No, I didn't try it; since the test case given in 30504 didn't
 (mis)behave as outlined in the PR, I guessed it wasn't very relevant.

 The patch in 30504 (the second one) does make the symptom I saw go
 away, though, so you are quite likely right that it is another
 manifestation of the same bug.  Thank you; I'll run with this patch
 unless and until either I find something it breaks (that I consider
 more important than this) or a new release comes out with an in-tree
 fix.

 /~\ The ASCII				der Mouse
 \ / Ribbon Campaign
  X  Against HTML	       mouse@rodents.montreal.qc.ca
 / \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

From: David Laight <dsl@netbsd.org>
To: gnats-bugs@gnats.NetBSD.org
Cc: 
Subject: PR/36816 CVS commit: src/usr.bin/sort
Date: Sat, 22 Aug 2009 10:53:29 +0000

 Module Name:	src
 Committed By:	dsl
 Date:		Sat Aug 22 10:53:28 UTC 2009

 Modified Files:
 	src/usr.bin/sort: append.c fields.c files.c fsort.c init.c msort.c
 	    sort.c sort.h

 Log Message:
 Rework the way sort generates sort keys:
 - If we generate a key, it is always sortable using memcmp()
 - If we are sorting the whole record, then a weight-table must be used
   during compares.
 - Major surgery to encoding of numbers to ensure unique keys for equal
   numeric values.  Reverse numerics are handled by inverting the sign.
 - Case folding (-f) is handled when the sort keys are generated. No other
   code has to care at all.
 - Key uniqueness (-u) is done during merge for large datasets. It only
   has to be done when writing the output file for small files.
   Since the file is in key order this is simple!
 Probably fixes all of: PR/27257 PR/25551 PR/22182 PR/31095 PR/30504
 PR/36816 PR/37860 PR/39308
 Also PR/18614 should no longer die, but a little more work needs to be
 done on the merging for very large files.


 To generate a diff of this commit:
 cvs rdiff -u -r1.19 -r1.20 src/usr.bin/sort/append.c src/usr.bin/sort/init.c
 cvs rdiff -u -r1.24 -r1.25 src/usr.bin/sort/fields.c src/usr.bin/sort/sort.h
 cvs rdiff -u -r1.34 -r1.35 src/usr.bin/sort/files.c
 cvs rdiff -u -r1.38 -r1.39 src/usr.bin/sort/fsort.c
 cvs rdiff -u -r1.22 -r1.23 src/usr.bin/sort/msort.c
 cvs rdiff -u -r1.51 -r1.52 src/usr.bin/sort/sort.c

 Please note that diffs are not public domain; they are subject to the
 copyright notices on the relevant files.

State-Changed-From-To: open->closed
State-Changed-By: dsl@NetBSD.org
State-Changed-When: Sat, 22 Aug 2009 11:18:25 +0000
State-Changed-Why:
fixed - see baove


From: Stephen Borrill <sborrill@netbsd.org>
To: gnats-bugs@gnats.NetBSD.org
Cc: 
Subject: PR/36816 CVS commit: [netbsd-5] src/usr.bin/sort
Date: Wed, 14 Oct 2009 20:41:53 +0000

 Module Name:	src
 Committed By:	sborrill
 Date:		Wed Oct 14 20:41:53 UTC 2009

 Modified Files:
 	src/usr.bin/sort [netbsd-5]: Makefile append.c fields.c files.c fsort.c
 	    fsort.h init.c msort.c sort.1 sort.c sort.h tmp.c
 Added Files:
 	src/usr.bin/sort [netbsd-5]: radix_sort.c

 Log Message:
 Pull up the following revisions(s) (requested by dsl in ticket #1084):
 	usr.bin/sort/Makefile:	revision 1.6-1.8
 	usr.bin/sort/append.c:	revision 1.15-1.22
 	usr.bin/sort/fields.c:	revision 1.20-1.30
 	usr.bin/sort/files.c:	revision 1.27-1.40
 	usr.bin/sort/fsort.c:	revision 1.33-1.45
 	usr.bin/sort/fsort.h:	revision 1.14-1.17
 	usr.bin/sort/init.c:	revision 1.19-1.23
 	usr.bin/sort/msort.c:	revision 1.19-1.28
 	usr.bin/sort/radix_sort.c:	revision 1.1-1.4
 	usr.bin/sort/sort.1:	revision 1.27-1.29
 	usr.bin/sort/sort.c:	revision 1.47-1.56
 	usr.bin/sort/sort.h:	revision 1.20-1.30
 	usr.bin/sort/tmp.c:	revision 1.14-1.15

 Only use radix sort for in-memory sort, always merge temporary files.
 Use a local radixsort() function so we can pass record length.
 Avoid use of weight tables for key compares.
 Fix generation of keys for numbers, negate value for reverse sort.
 Write file in reverse-key order for 'sort -n'.
 'sort -S' now does a posix sort (sort matching keys by record data).
 Ensure merge sort doesn't have too many temporary files open.
 Fixes: PR#18614 PR#27257 PR#25551 PR#22182 PR#31095 PR#30504 PR#36816
 PR#37860 PR#39308 PR#42094


 To generate a diff of this commit:
 cvs rdiff -u -r1.5 -r1.5.40.1 src/usr.bin/sort/Makefile
 cvs rdiff -u -r1.14 -r1.14.6.1 src/usr.bin/sort/append.c
 cvs rdiff -u -r1.19 -r1.19.6.1 src/usr.bin/sort/fields.c \
     src/usr.bin/sort/sort.h
 cvs rdiff -u -r1.26 -r1.26.6.1 src/usr.bin/sort/files.c \
     src/usr.bin/sort/sort.1
 cvs rdiff -u -r1.32 -r1.32.6.1 src/usr.bin/sort/fsort.c
 cvs rdiff -u -r1.13 -r1.13.6.1 src/usr.bin/sort/fsort.h \
     src/usr.bin/sort/tmp.c
 cvs rdiff -u -r1.18 -r1.18.6.1 src/usr.bin/sort/init.c \
     src/usr.bin/sort/msort.c
 cvs rdiff -u -r0 -r1.4.2.2 src/usr.bin/sort/radix_sort.c
 cvs rdiff -u -r1.46 -r1.46.4.1 src/usr.bin/sort/sort.c

 Please note that diffs are not public domain; they are subject to the
 copyright notices on the relevant files.

>Unformatted:

Home	PR Database Search