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 <src.opts.mk>
+
PROG= tail
SRCS= forward.c misc.c read.c reverse.c tail.c
+.if ${MK_TESTS} != "no"
+SUBDIR+= tests
+.endif
+
.include <bsd.prog.mk>
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 <sys/param.h>
+#include <sys/queue.h>
#include <sys/stat.h>
#include <sys/mman.h>
@@ -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 <bsd.test.mk>
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 <<HERE
+This is the first line
+This is the second line
+This is the third line
+HERE
+ cat > 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 <<HERE
+This is the first line
+This is the second line
+This is the third line
+HERE
+ cat > 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 <<HERE
+This is the first line
+This is the second line
+This is the third line
+HERE
+ cat > 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
+}
_______________________________________________
svn-src-head@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/svn-src-head
To unsubscribe, send any mail to "svn-src-head-unsubscr...@freebsd.org"
