home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / sys / next / programm / 5872 < prev    next >
Encoding:
Text File  |  1992-08-30  |  5.3 KB  |  179 lines
  1. Newsgroups: comp.sys.next.programmer
  2. Path: sparky!uunet!elroy.jpl.nasa.gov!usc!rpi!usenet
  3. From: gad@eclipse.its.rpi.edu (Garance A. Drosehn)
  4. Subject: Re: bug/fix for sort !!!
  5. Message-ID: <1wtysja@rpi.edu>
  6. Nntp-Posting-Host: eclipse.its.rpi.edu
  7. References: <1992Aug27.202530.28111@u.washington.edu>
  8. Date: Mon, 31 Aug 1992 04:33:30 GMT
  9. Lines: 168
  10.  
  11. I'm basically reposting this just in case no one sees comp.sys.next these  
  12. days (as well they should not, seeing it hasn't officially existed for a  
  13. year or so now...  :-).
  14.  
  15. The author claims this bug is in NeXTSTEP 2.1.  Does anyone know if it's in  
  16. NeXTSTEP 3.0?
  17. ---
  18. Garance Alistair Drosehn     =     gad@eclipse.its.rpi.edu
  19. ITS Systems Programmer            (handles NeXT-type mail)
  20. Rensselaer Polytechnic Institute;           Troy NY    USA
  21.  
  22.  - - - - - - - - [start quoted article]
  23.  
  24. In article <1992Aug27.202530.28111@u.washington.edu>
  25.     in newsgroup comp.sys.next
  26.     corey@milton.u.washington.edu (Corey Satten) writes:
  27. > As hard as it is to believe, after all these years of use, I found a bug
  28. > in /usr/bin/sort when used with the -u flag.  The bug only shows up for
  29. > relatively large inputs and causes a few of the last lines of output to
  30. > be omitted.  Below is a script you can feed both to /bin/sh to test your
  31. > sort and to "patch" to (hopefully - but as always, no guarantees) fix
  32. > your sort.c.  The context diff is for BSD 4.3 sort.c, however the exact
  33. > same code exists (at different line numbers) in Ultrix 4.1 sort.c so
  34. > you can still apply the patch verbatim.
  35. > 
  36. > --------
  37. > Corey Satten, corey@cac.washington.edu
  38. > Networks and Distributed Computing
  39. > University of Washington
  40.  
  41.   [patch from the article, but not quoted with the ">"s - garance]
  42. #!/bin/sh
  43. #
  44. # Test for sort -u bug.  The bug causes a small number of lines to be
  45. # omitted from the sort -u output for relatively large sort inputs.
  46. #
  47. # It is caused by the merge code not handling EOF properly in the  
  48. next-to-last
  49. # temp-file generated by sort.  In order to trigger the bug, enough input
  50. # must be presented that sort merges a larger number of tempfiles into a
  51. # smaller number and then merges the smaller number.  Alternatively,
  52. # the uninitialized memory which is compared against the last value
  53. # could accidently contain that value.
  54. #
  55. # This bug is known to be present in:
  56. #    BSD 4.3 Tahoe
  57. #    Sequent Dynix V3.1.4
  58. #    NeXT version 2.1
  59. #    Ultrix version 4.1, 4.2a
  60. #    AT&T 7300/3b1 version 3.51
  61. #
  62. # It appears not to be present in SunOS 4.x, OSF/1 however this may only
  63. # be because the size of the input required to trigger the bug has been
  64. # raised (the size of the tempfiles and memory arrays has been raised).
  65. #
  66. # A context diff of what I hope is a fix to the 4.3BSD version is
  67. # appended at the end of this script.  Use at your own risk.
  68. #
  69. # Corey Satten, corey@cac.washington.edu, July 31, 1992
  70.  
  71. TMP=/tmp/data$$
  72. trap "rm -f $TMP.c $TMP; exit 0" 0 1 2 13 15
  73.  
  74. COUNT=${1-45}        # value supplied as $1, else default to 45
  75.  
  76. lines=`echo "$COUNT^3 * 1.015625 / 10 * 10" | bc`
  77. echo testing sort with input of roughly $lines lines 1>&2
  78.  
  79. cat <<EOF >$TMP.c
  80. #include <stdio.h>
  81. #define r(x) ("qwertyuiopasdfghjklzxcvbnm"[pos(x)%26])
  82. #define pos(x) ((x)>0?(x):5-(x))
  83.  
  84. main() {
  85.     int lines = 0;
  86.     int i,j,k;
  87.     for (i=0; i<$COUNT; ++i) {
  88.     for (j=0; j<$COUNT; ++j) {
  89.         for (k=0; k<$COUNT; ++k) {
  90.         if ( (++lines & 63) == 0) printf("zzzzzzzzzzz - OK\n");
  91.         printf("%c%c%c%c%c%c\n",
  92.             r(k), r(j+k), r(j-k), r(i+k), r(i-k), r(i+j+k));
  93.             }
  94.         }
  95.         }
  96.     }
  97. EOF
  98. cc $TMP.c -o $TMP || {
  99.     rm -f $TMP.o
  100.     echo
  101.     echo " Sorry, your C compiler didn't compile my program." 1>&2
  102.     exit 1
  103.     }
  104.  
  105. if $TMP | sort -u | grep -s '^zzzzzzzzzzz' ; then
  106.     echo
  107.     echo " sort -u worked for this input (COUNT=$COUNT) but to be safe, you"
  108.     echo ' might wish to try again with a larger value of COUNT.  You may'
  109.     echo ' supply a value for COUNT as an argument to this script.'
  110.     echo ' The number of lines is roughly COUNT to the 3rd power.'
  111.     exit 0
  112. else
  113.     echo
  114.     echo ' sort -u failed on this system.  The line beginning with  
  115. zzzzzzzzzz'
  116.     echo ' was omitted from the sort -u output.  You might wish to compare'
  117.     echo ' sort -u output with output from sort|uniq to see if there are  
  118. any'
  119.     echo ' other differences.'
  120.     exit 1
  121. fi
  122.  
  123. # I believe this change applied to the 4.3BSD code fixes the problem.
  124. # Use at your own risk.  -Corey
  125. #
  126. *** sort.c    Fri Jul 31 08:35:33 1992
  127. --- new_sort.c    Fri Jul 31 14:33:20 1992
  128. ***************
  129. *** 387,392 ****
  130. --- 387,393 ----
  131.       int    j;
  132.       int    k, l;
  133.       int    muflg;
  134. +     int    last_muflg;
  135.   
  136.       p = (struct merg *)lspace;
  137.       j = 0;
  138. ***************
  139. *** 432,438 ****
  140.                   term();
  141.               }
  142.           }
  143. !         if(muflg){
  144.               cp = ibuf[i-1]->l;
  145.               dp = p->l;
  146.               do {
  147. --- 433,439 ----
  148.                   term();
  149.               }
  150.           }
  151. !         if(last_muflg = muflg){    /* yes assignment. Corey */
  152.               cp = ibuf[i-1]->l;
  153.               dp = p->l;
  154.               do {
  155. ***************
  156. *** 452,458 ****
  157.                   *ip = *(ip-1);
  158.                   *(ip-1) = jp;
  159.               }
  160. !             if(!muflg)
  161.                   break;
  162.               j = (*compare)(ibuf[i-1]->l,p->l);
  163.               if(cflg) {
  164. --- 453,466 ----
  165.                   *ip = *(ip-1);
  166.                   *(ip-1) = jp;
  167.               }
  168. !         /*
  169. !          * Instead of testing muflg, I introduce last_muflg
  170. !          * because when i-- reaches 1 and the value of muflg
  171. !          * changes, the code suddenly compares against p->l
  172. !          * which hasn't had a recent value copied into it.
  173. !          * Corey.
  174. !          */
  175. !             if(!last_muflg)
  176.                   break;
  177.               j = (*compare)(ibuf[i-1]->l,p->l);
  178.               if(cflg) {
  179.