Subject: bug#9780: sort -u throws out non-duplicates

From: Jim Meyering <[email-masked]>
Date: Fri, 17 Aug 2012 22:31:21 +0200

Paul Eggert wrote:
> On 08/17/2012 12:53 PM, Jim Meyering wrote:
>> safe_text is initially NULL and we enter that block
>> only when we're about to fread into a buffer that overlaps
>> the current saved_line.text buffer.
>
> Sorry, I wasn't clear enough.  I was worried about the
> case when saved_line.text does not overlap the buffer
> we're about to read into, because the buffer we're about
> to read into has been realloc'ed.  The idea is that we
> saved a line, then realloc'ed the buffer, and now we're
> doing the overlap test.  There won't be an overlap (assuming
> realloc gave us fresh space), but the saved line points
> into freed memory.

Ohhh.  Good catch.
That is a related, but independent bug.
It also afflicts the code from before today's change.

Here's the part of fillbuf that can realloc "buf->buf",
leaving saved_line.text pointing into freed memory:

          {
            /* The current input line is too long to fit in the buffer.
               Increase the buffer size and try again, keeping it properly
               aligned.  */
            size_t line_alloc = buf->alloc / sizeof (struct line);
            buf->buf = x2nrealloc (buf->buf, &line_alloc, sizeof (struct line));
            buf->alloc = line_alloc * sizeof (struct line);
          }
        }
    }

One way to work around that is to update saved_line.text,
if needed, right after that x2nrealloc call.

Understanding that scenario, it was easy to construct a case
that triggers a free memory read:

    $ perl -le 'print "a\n"."0"x900'|valgrind ./sort --p=1 -S32b -u>/dev/null
    ==5263== Memcheck, a memory error detector
    ==5263== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
    ==5263== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
    ==5263== Command: ./sort --p=1 -S32b -u
    ==5263==
    ==5263== Invalid read of size 1
    ==5263==    at 0x4A0AD1C: bcmp (mc_replace_strmem.c:889)
    ==5263==    by 0x408118: compare (sort.c:2736)
    ==5263==    by 0x408425: write_unique (sort.c:3391)
    ==5263==    by 0x40467A: main (sort.c:3959)
    ==5263==  Address 0x4c34270 is 0 bytes inside a block of size 576 free'd
    ==5263==    at 0x4A0892E: realloc (vg_replace_malloc.c:632)
    ==5263==    by 0x410130: xrealloc (xmalloc.c:63)
    ==5263==    by 0x406C04: fillbuf (sort.c:1857)
    ==5263==    by 0x40462C: main (sort.c:3916)
    ==5263==
    ==5263==
    ==5263== HEAP SUMMARY:
    ==5263==     in use at exit: 128 bytes in 1 blocks
    ==5263==   total heap usage: 23 allocs, 22 frees, 530,779 bytes allocated
    ==5263==
    ==5263== LEAK SUMMARY:
    ==5263==    definitely lost: 0 bytes in 0 blocks
    ==5263==    indirectly lost: 0 bytes in 0 blocks
    ==5263==      possibly lost: 0 bytes in 0 blocks
    ==5263==    still reachable: 128 bytes in 1 blocks
    ==5263==         suppressed: 0 bytes in 0 blocks
    ==5263== Rerun with --leak-check=full to see details of leaked memory
    ==5263==
    ==5263== For counts of detected and suppressed errors, rerun with: -v
    ==5263== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 2 from 2)

So we definitely have a *second* bug here.
Thanks!