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