From owner-svn-src-all@freebsd.org Tue Jan 10 20:43:34 2017 Return-Path: Delivered-To: svn-src-all@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 09E8FCA9126; Tue, 10 Jan 2017 20:43:34 +0000 (UTC) (envelope-from asomers@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id CF34B14D2; Tue, 10 Jan 2017 20:43:33 +0000 (UTC) (envelope-from asomers@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id v0AKhXQx073174; Tue, 10 Jan 2017 20:43:33 GMT (envelope-from asomers@FreeBSD.org) Received: (from asomers@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id v0AKhWuv073169; Tue, 10 Jan 2017 20:43:32 GMT (envelope-from asomers@FreeBSD.org) Message-Id: <201701102043.v0AKhWuv073169@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: asomers set sender to asomers@FreeBSD.org using -f From: Alan Somers Date: Tue, 10 Jan 2017 20:43:32 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r311895 - in head: etc/mtree usr.bin/tail usr.bin/tail/tests X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 10 Jan 2017 20:43:34 -0000 Author: asomers Date: Tue Jan 10 20:43:32 2017 New Revision: 311895 URL: https://svnweb.freebsd.org/changeset/base/311895 Log: Fix memory leaks during "tail -r" of an irregular file * Rewrite r_buf to use standard tail queues instead of a hand-rolled circular linked list. Free dynamic allocations when done. * Remove an optimization for the case where the file is a multiple of 128KB in size and there is a scarcity of memory. * Add ATF tests for "tail -r" and its variants. Reported by: Valgrind Reviewed by: ngie MFC after: 4 weeks Sponsored by: Spectra Logic Corp Differential Revision: https://reviews.freebsd.org/D9067 Added: head/usr.bin/tail/tests/ head/usr.bin/tail/tests/Makefile (contents, props changed) head/usr.bin/tail/tests/tail_test.sh (contents, props changed) Modified: head/etc/mtree/BSD.tests.dist head/usr.bin/tail/Makefile head/usr.bin/tail/reverse.c Modified: head/etc/mtree/BSD.tests.dist ============================================================================== --- head/etc/mtree/BSD.tests.dist Tue Jan 10 20:37:44 2017 (r311894) +++ head/etc/mtree/BSD.tests.dist Tue Jan 10 20:43:32 2017 (r311895) @@ -644,6 +644,8 @@ .. soelim .. + tail + .. tar .. timeout Modified: head/usr.bin/tail/Makefile ============================================================================== --- head/usr.bin/tail/Makefile Tue Jan 10 20:37:44 2017 (r311894) +++ head/usr.bin/tail/Makefile Tue Jan 10 20:43:32 2017 (r311895) @@ -1,7 +1,13 @@ # $FreeBSD$ # @(#)Makefile 8.1 (Berkeley) 6/6/93 +.include + PROG= tail SRCS= forward.c misc.c read.c reverse.c tail.c +.if ${MK_TESTS} != "no" +SUBDIR+= tests +.endif + .include Modified: head/usr.bin/tail/reverse.c ============================================================================== --- head/usr.bin/tail/reverse.c Tue Jan 10 20:37:44 2017 (r311894) +++ head/usr.bin/tail/reverse.c Tue Jan 10 20:43:32 2017 (r311895) @@ -40,6 +40,7 @@ static char sccsid[] = "@(#)reverse.c 8. __FBSDID("$FreeBSD$"); #include +#include #include #include @@ -169,12 +170,12 @@ r_reg(FILE *fp, const char *fn, enum STY ierr(fn); } -typedef struct bf { - struct bf *next; - struct bf *prev; - int len; - char *l; -} BF; +static const size_t bsz = 128 * 1024; +typedef struct bfelem { + TAILQ_ENTRY(bfelem) entries; + size_t len; + char l[bsz]; +} bfelem_t; /* * r_buf -- display a non-regular file in reverse order by line. @@ -189,64 +190,42 @@ typedef struct bf { static void r_buf(FILE *fp, const char *fn) { - BF *mark, *tl, *tr; - int ch, len, llen; + struct bfelem *tl, *temp, *first = NULL; + size_t len, llen; char *p; - off_t enomem; + off_t enomem = 0; + TAILQ_HEAD(bfhead, bfelem) head; - tl = NULL; -#define BSZ (128 * 1024) - for (mark = NULL, enomem = 0;;) { + TAILQ_INIT(&head); + + while (!feof(fp)) { /* * Allocate a new block and link it into place in a doubly * linked list. If out of memory, toss the LRU block and * keep going. */ - if (enomem || (tl = malloc(sizeof(BF))) == NULL || - (tl->l = malloc(BSZ)) == NULL) { - if (!mark) + while ((tl = malloc(sizeof(bfelem_t))) == NULL) { + first = TAILQ_FIRST(&head); + if (TAILQ_EMPTY(&head)) err(1, "malloc"); - if (enomem) - tl = tl->next; - else { - if (tl) - free(tl); - tl = mark; - } - enomem += tl->len; - } else if (mark) { - tl->next = mark; - tl->prev = mark->prev; - mark->prev->next = tl; - mark->prev = tl; - } else { - mark = tl; - mark->next = mark->prev = mark; + enomem += first->len; + TAILQ_REMOVE(&head, first, entries); + free(first); } + TAILQ_INSERT_TAIL(&head, tl, entries); /* Fill the block with input data. */ - for (p = tl->l, len = 0; - len < BSZ && (ch = getc(fp)) != EOF; ++len) - *p++ = ch; - - if (ferror(fp)) { - ierr(fn); - return; - } - - /* - * If no input data for this block and we tossed some data, - * recover it. - */ - if (!len && enomem) { - enomem -= tl->len; - tl = tl->prev; - break; + len = 0; + while ((!feof(fp)) && len < bsz) { + p = tl->l + len; + len += fread(p, 1, bsz - len, fp); + if (ferror(fp)) { + ierr(fn); + return; + } } tl->len = len; - if (ch == EOF) - break; } if (enomem) { @@ -255,37 +234,44 @@ r_buf(FILE *fp, const char *fn) } /* - * Step through the blocks in the reverse order read. The last char - * is special, ignore whether newline or not. + * Now print the lines in reverse order + * Outline: + * Scan backward for "\n", + * print forward to the end of the buffers + * free any buffers that start after the "\n" just found + * Loop */ - for (mark = tl;;) { - for (p = tl->l + (len = tl->len) - 1, llen = 0; len--; - --p, ++llen) - if (*p == '\n') { - if (llen) { + tl = TAILQ_LAST(&head, bfhead); + first = TAILQ_FIRST(&head); + while (tl != NULL) { + for (p = tl->l + tl->len - 1, llen = 0; p >= tl->l; + --p, ++llen) { + int start = (tl == first && p == tl->l); + + if ((*p == '\n') || start) { + struct bfelem *tr; + + if (start && len) + WR(p, llen + 1); + else if (llen) WR(p + 1, llen); - llen = 0; - } - if (tl == mark) - continue; - for (tr = tl->next; tr->len; tr = tr->next) { - WR(tr->l, tr->len); - tr->len = 0; - if (tr == mark) - break; + tr = TAILQ_NEXT(tl, entries); + llen = 0; + if (tr != NULL) { + TAILQ_FOREACH_FROM_SAFE(tr, &head, + entries, temp) { + if (tr->len) + WR(&tr->l, tr->len); + TAILQ_REMOVE(&head, tr, + entries); + free(tr); + } } } + } tl->len = llen; - if ((tl = tl->prev) == mark) - break; - } - tl = tl->next; - if (tl->len) { - WR(tl->l, tl->len); - tl->len = 0; - } - while ((tl = tl->next)->len) { - WR(tl->l, tl->len); - tl->len = 0; + tl = TAILQ_PREV(tl, bfhead, entries); } + TAILQ_REMOVE(&head, first, entries); + free(first); } Added: head/usr.bin/tail/tests/Makefile ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/usr.bin/tail/tests/Makefile Tue Jan 10 20:43:32 2017 (r311895) @@ -0,0 +1,7 @@ +# $FreeBSD$ + +PACKAGE= tests + +ATF_TESTS_SH= tail_test + +.include Added: head/usr.bin/tail/tests/tail_test.sh ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/usr.bin/tail/tests/tail_test.sh Tue Jan 10 20:43:32 2017 (r311895) @@ -0,0 +1,233 @@ +# Copyright (c) 2016 Alan Somers +# All rights reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: +# 1. Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# 2. Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in the +# documentation and/or other materials provided with the distribution. +# +# THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +# ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +# OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +# HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +# OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +# SUCH DAMAGE. +# +# $FreeBSD$ + +atf_test_case empty_r +empty_r_head() +{ + atf_set "descr" "Reverse an empty file" +} +empty_r_body() +{ + touch infile expectfile + tail -r infile > outfile + tail -r < infile > outpipe + atf_check cmp expectfile outfile + atf_check cmp expectfile outpipe +} + +atf_test_case file_r +file_r_head() +{ + atf_set "descr" "Reverse a file" +} +file_r_body() +{ + cat > infile < expectfile << HERE +This is the third line +This is the second line +This is the first line +HERE + tail -r infile > outfile + tail -r < infile > outpipe + atf_check cmp expectfile outfile + atf_check cmp expectfile outpipe +} + +atf_test_case file_rn2 +file_rn2_head() +{ + atf_set "descr" "Reverse the last two lines of a file" +} +file_rn2_body() +{ + cat > infile < expectfile << HERE +This is the third line +This is the second line +HERE + tail -rn2 infile > outfile + tail -rn2 < infile > outpipe + atf_check cmp expectfile outfile + atf_check cmp expectfile outpipe +} + +atf_test_case file_rc28 +file_rc28_head() +{ + atf_set "descr" "Reverse a file and display the last 28 characters" +} +file_rc28_body() +{ + cat > infile < expectfile << HERE +This is the third line +line +HERE + tail -rc28 infile > outfile + tail -rc28 < infile > outpipe + atf_check cmp expectfile outfile + atf_check cmp expectfile outpipe +} + +atf_test_case longfile_r +longfile_r_head() +{ + atf_set "descr" "Reverse a long file" +} +longfile_r_body() +{ + jot -w "%0511d" 1030 0 > infile + jot -w "%0511d" 1030 1029 0 -1 > expectfile + tail -r infile > outfile + tail -r < infile > outpipe + atf_check cmp expectfile outfile + atf_check cmp expectfile outpipe +} + +atf_test_case longfile_r_enomem +longfile_r_enomem_head() +{ + atf_set "descr" "Reverse a file that's too long to store in RAM" +} +longfile_r_enomem_body() +{ + # When we reverse a file that's too long for RAM, tail should drop the + # first part and just print what it can. We'll check that the last + # part is ok + { + ulimit -v 32768 || atf_skip "Can't adjust ulimit" + jot -w "%01023d" 32768 0 | tail -r > outfile ; + } + if [ "$?" -ne 1 ]; then + atf_skip "Didn't get ENOMEM. Adjust test parameters" + fi + # We don't know how much of the input we dropped. So just check that + # the first ten lines of tail's output are the same as the last ten of + # the input + jot -w "%01023d" 10 32767 0 -1 > expectfile + head -n 10 outfile > outtrunc + diff expectfile outtrunc + atf_check cmp expectfile outtrunc +} + +atf_test_case longfile_r_longlines +longfile_r_longlines_head() +{ + atf_set "descr" "Reverse a long file with extremely long lines" +} +longfile_r_longlines_body() +{ + jot -s " " -w "%07d" 18000 0 > infile + jot -s " " -w "%07d" 18000 18000 >> infile + jot -s " " -w "%07d" 18000 36000 >> infile + jot -s " " -w "%07d" 18000 36000 > expectfile + jot -s " " -w "%07d" 18000 18000 >> expectfile + jot -s " " -w "%07d" 18000 0 >> expectfile + tail -r infile > outfile + tail -r < infile > outpipe + atf_check cmp expectfile outfile + atf_check cmp expectfile outpipe +} + +atf_test_case longfile_rc135782 +longfile_rc135782_head() +{ + atf_set "descr" "Reverse a long file and print the last 135,782 bytes" +} +longfile_rc135782_body() +{ + jot -w "%063d" 9000 0 > infile + jot -w "%063d" 2121 8999 0 -1 > expectfile + echo "0000000000000000000000000000000006878" >> expectfile + tail -rc135782 infile > outfile + tail -rc135782 < infile > outpipe + atf_check cmp expectfile outfile + atf_check cmp expectfile outpipe +} + +atf_test_case longfile_rc145782_longlines +longfile_rc145782_longlines_head() +{ + atf_set "descr" "Reverse a long file with extremely long lines and print the last 145,782 bytes" +} +longfile_rc145782_longlines_body() +{ + jot -s " " -w "%07d" 18000 0 > infile + jot -s " " -w "%07d" 18000 18000 >> infile + jot -s " " -w "%07d" 18000 36000 >> infile + jot -s " " -w "%07d" 18000 36000 > expectfile + echo -n "35777 " >> expectfile + jot -s " " -w "%07d" 222 35778 >> expectfile + tail -rc145782 infile > outfile + tail -rc145782 < infile > outpipe + atf_check cmp expectfile outfile + atf_check cmp expectfile outpipe +} + +atf_test_case longfile_rn2500 +longfile_rn2500_head() +{ + atf_set "descr" "Reverse a long file and print the last 2,500 lines" +} +longfile_rn2500_body() +{ + jot -w "%063d" 9000 0 > infile + jot -w "%063d" 2500 8999 0 -1 > expectfile + tail -rn2500 infile > outfile + tail -rn2500 < infile > outpipe + atf_check cmp expectfile outfile + atf_check cmp expectfile outpipe +} + + +atf_init_test_cases() +{ + atf_add_test_case empty_r + atf_add_test_case file_r + atf_add_test_case file_rc28 + atf_add_test_case file_rn2 + # The longfile tests are designed to exercise behavior in r_buf(), + # which operates on 128KB blocks + atf_add_test_case longfile_r + atf_add_test_case longfile_r_enomem + atf_add_test_case longfile_r_longlines + atf_add_test_case longfile_rc135782 + atf_add_test_case longfile_rc145782_longlines + atf_add_test_case longfile_rn2500 +}