Index: head/etc/mtree/BSD.tests.dist =================================================================== --- head/etc/mtree/BSD.tests.dist +++ head/etc/mtree/BSD.tests.dist @@ -644,6 +644,8 @@ .. soelim .. + tail + .. tar .. timeout Index: head/usr.bin/tail/Makefile =================================================================== --- head/usr.bin/tail/Makefile +++ head/usr.bin/tail/Makefile @@ -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 Index: head/usr.bin/tail/reverse.c =================================================================== --- head/usr.bin/tail/reverse.c +++ head/usr.bin/tail/reverse.c @@ -40,6 +40,7 @@ __FBSDID("$FreeBSD$"); #include +#include #include #include @@ -169,12 +170,12 @@ 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 @@ 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 @@ } /* - * 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); } Index: head/usr.bin/tail/tests/Makefile =================================================================== --- head/usr.bin/tail/tests/Makefile +++ head/usr.bin/tail/tests/Makefile @@ -0,0 +1,7 @@ +# $FreeBSD$ + +PACKAGE= tests + +ATF_TESTS_SH= tail_test + +.include Index: head/usr.bin/tail/tests/tail_test.sh =================================================================== --- head/usr.bin/tail/tests/tail_test.sh +++ head/usr.bin/tail/tests/tail_test.sh @@ -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 +}