diff options
| author | github-classroom[bot] <66690702+github-classroom[bot]@users.noreply.github.com> | 2021-12-03 13:36:17 +0000 |
|---|---|---|
| committer | github-classroom[bot] <66690702+github-classroom[bot]@users.noreply.github.com> | 2021-12-03 13:36:17 +0000 |
| commit | 88971f5b89b7029c90ac8a47d5c4aa3cac0f6376 (patch) | |
| tree | 3522d024e3ab95e45208ee32ca8c110707fcf79c | |
Initial commit
86 files changed, 5103 insertions, 0 deletions
diff --git a/.clang-format b/.clang-format new file mode 100644 index 0000000..e366c93 --- /dev/null +++ b/.clang-format @@ -0,0 +1,93 @@ +--- +Language: Cpp +# BasedOnStyle: LLVM +AccessModifierOffset: -2 +AlignAfterOpenBracket: Align +AlignConsecutiveAssignments: false +AlignConsecutiveDeclarations: false +AlignEscapedNewlinesLeft: false +AlignOperands: true +AlignTrailingComments: true +AllowAllParametersOfDeclarationOnNextLine: true +AllowShortBlocksOnASingleLine: false +AllowShortCaseLabelsOnASingleLine: false +AllowShortFunctionsOnASingleLine: None +AllowShortIfStatementsOnASingleLine: false +AllowShortLoopsOnASingleLine: false +AlwaysBreakAfterDefinitionReturnType: None +AlwaysBreakAfterReturnType: None +AlwaysBreakBeforeMultilineStrings: false +AlwaysBreakTemplateDeclarations: false +BinPackArguments: true +BinPackParameters: true +BraceWrapping: + AfterClass: false + AfterControlStatement: false + AfterEnum: false + AfterFunction: false + AfterNamespace: false + AfterObjCDeclaration: false + AfterStruct: false + AfterUnion: false + BeforeCatch: false + BeforeElse: false + IndentBraces: false +BreakBeforeBinaryOperators: None +BreakBeforeBraces: Attach +BreakBeforeTernaryOperators: true +BreakConstructorInitializersBeforeComma: false +ColumnLimit: 80 +CommentPragmas: '^ IWYU pragma:' +ConstructorInitializerAllOnOneLineOrOnePerLine: false +ConstructorInitializerIndentWidth: 2 +ContinuationIndentWidth: 2 +Cpp11BracedListStyle: true +DerivePointerAlignment: false +DisableFormat: false +ExperimentalAutoDetectBinPacking: false +ForEachMacros: [ TAILQ_FOREACH, SPLAY_FOREACH, RB_FOREACH, WITH_MTX_LOCK, + WITH_SPIN_LOCK, WITH_RW_LOCK, SET_FOREACH, LIST_FOREACH, + TAILQ_FOREACH_REVERSE, TAILQ_FOREACH_SAFE, + LIST_FOREACH_SAFE, WITH_VM_MAP_LOCK ] +IncludeCategories: + - Regex: '^"(llvm|llvm-c|clang|clang-c)/' + Priority: 2 + - Regex: '^(<|"(gtest|isl|json)/)' + Priority: 3 + - Regex: '.*' + Priority: 1 +IndentCaseLabels: true +IndentWidth: 2 +IndentWrappedFunctionNames: false +KeepEmptyLinesAtTheStartOfBlocks: true +MacroBlockBegin: '' +MacroBlockEnd: '' +MaxEmptyLinesToKeep: 1 +NamespaceIndentation: None +ObjCBlockIndentWidth: 2 +ObjCSpaceAfterProperty: false +ObjCSpaceBeforeProtocolList: true +PenaltyBreakBeforeFirstCallParameter: 19 +PenaltyBreakComment: 300 +PenaltyBreakFirstLessLess: 120 +PenaltyBreakString: 1000 +PenaltyExcessCharacter: 1000000 +PenaltyReturnTypeOnItsOwnLine: 60 +PointerAlignment: Right +ReflowComments: true +SortIncludes: false +SpaceAfterCStyleCast: false +SpaceBeforeAssignmentOperators: true +SpaceBeforeParens: ControlStatements +SpaceInEmptyParentheses: false +SpacesBeforeTrailingComments: 1 +SpacesInAngles: false +SpacesInContainerLiterals: true +SpacesInCStyleCastParentheses: false +SpacesInParentheses: false +SpacesInSquareBrackets: false +Standard: Cpp11 +TabWidth: 8 +UseTab: Never +... + diff --git a/.github/classroom/autograding.json b/.github/classroom/autograding.json new file mode 100644 index 0000000..8d445f5 --- /dev/null +++ b/.github/classroom/autograding.json @@ -0,0 +1,22 @@ +{ + "tests": [ + { + "name": "Build", + "run": "make", + "input": "", + "output": "", + "comparison": "included", + "timeout": 10, + "points": 1 + }, + { + "name": "Run tests", + "run": "timeout -v 5m make test", + "input": "", + "output": "", + "comparison": "included", + "timeout": 5, + "points": 1 + } + ] +} diff --git a/.github/workflows/classroom.yml b/.github/workflows/classroom.yml new file mode 100644 index 0000000..a80f9e5 --- /dev/null +++ b/.github/workflows/classroom.yml @@ -0,0 +1,23 @@ +name: GitHub Classroom Workflow + +on: [push] + +jobs: + build: + name: Autograding + runs-on: ubuntu-latest + container: cahirwpz/ii-so:latest + steps: + - uses: actions/checkout@v2 + - name: Check code formatting + run: ./run-clang-format.sh + - name: Check for unauthorized modifications + run: ./check-files.py + - uses: education/autograding@v1 + - name: 'Archive test results' + if: always() + uses: actions/upload-artifact@v2 + with: + name: test-results + path: sh-tests.*.log + retention-days: 1 diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..0ed9b1d --- /dev/null +++ b/.gitignore @@ -0,0 +1,20 @@ +# Compiled languages +*.o +*.so +*.a +.*.d +shell + +# Python +*.pyc + +# Vim +*.swp +*~ + +# Other files +*.log + +# Archives +*.tar.gz +*.tgz diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..0396a88 --- /dev/null +++ b/Makefile @@ -0,0 +1,17 @@ +PROGS = shell trace.so +EXTRA-CLEAN = sh-tests.*.log + +include Makefile.include + +CC += -fsanitize=address +CPPFLAGS += -DSTUDENT +LDLIBS += -lreadline + +shell: shell.o command.o lexer.o jobs.o + +test: + for i in `seq 1 10`; do python3 sh-tests.py -v || exit 1; done + +trace.so: trace.c + +# vim: ts=8 sw=8 noet diff --git a/Makefile.include b/Makefile.include new file mode 100644 index 0000000..d0be804 --- /dev/null +++ b/Makefile.include @@ -0,0 +1,111 @@ +CC = gcc -g +CFLAGS = -Og -Wall -Werror -Wstrict-prototypes +AS = as -g +ASFLAGS = +CPPFLAGS = -Iinclude +LDLIBS = -Llibcsapp -lcsapp + +# Recognize operating system +ifeq ($(shell uname -s), Darwin) +CPPFLAGS += -DMACOS +endif + +ifeq ($(shell uname -s), Linux) +CPPFLAGS += -DLINUX +endif + +ifeq ($(shell uname -s), FreeBSD) +CPPFLAGS += -DFREEBSD +endif + +# Pass "VERBOSE=1" at command line to display command being invoked by GNU Make +ifneq ($(VERBOSE), 1) +.SILENT: +endif + +LIBSRC_C = $(wildcard libcsapp/*.c) +LIBSRC_S = $(wildcard libcsapp/*.s) +LIBSRC_H = $(wildcard include/*.h) +LIBSRCS = $(LIBSRC_C) $(LIBSRC_S) $(LIBSRC_H) +LIBOBJS = $(LIBSRC_C:%.c=%.o) +ifneq ($(shell uname -s), Darwin) +LIBOBJS += $(LIBSRC_S:%.s=%.o) +endif +LIB = libcsapp/libcsapp.a + +SRC_C = $(wildcard *.c) +SRC_S = $(wildcard *.s) +SRC_H = $(wildcard *.h) +SRCS = $(SRC_C) $(SRC_S) +OBJS = $(SRC_C:%.c=%.o) + +SOURCES = $(SRCS) $(LIBSRCS) +OBJECTS = $(OBJS) $(LIBOBJS) +DEPFILES = $(foreach f,$(SRC_C) $(LIBSRC_C),\ + $(dir $(f))$(patsubst %.c,.%.d,$(notdir $(f)))) + +ARCHIVE = so$(shell date +'%y')_$(shell basename $(PWD)) +FILES = Makefile Makefile.include $(EXTRA-FILES) + +all: $(DEPFILES) $(LIB) $(PROGS) + +$(LIB): $(LIBOBJS) + +# Generate dependencies automatically +ifeq ($(words $(findstring $(MAKECMDGOALS), archive clean)), 0) + -include $(DEPFILES) +endif + +# Disable all built-in recipes and define our own +.SUFFIXES: + +.%.d: %.c + $(CC) $(CPPFLAGS) -MM -MG -o $@ $< + +%.o: %.c .%.d + @echo "[CC] $@ <- $<" + $(CC) $(CPPFLAGS) $(CFLAGS) -c -o $@ $< + +%.o: %.s + @echo "[AS] $@ <- $<" + $(AS) $(ASFLAGS) -c -o $@ $< + +%.a: + @echo "[AR] $@ <- $^" + $(AR) rc $@ $^ + +%: %.o $(LIB) + @echo "[LD] $@ <- $^" + $(CC) $(LDFLAGS) -o $@ $^ $(LDLIBS) + +%.so: %.c + @echo "[CC] $@ <- $<" + $(CC) -shared -fpic $(CFLAGS) -o $@ $< -ldl + +tags: + @echo "[CTAGS] Rebuilding tags database..." + ctags $(LIBSRC_C) $(SRC_C) $(SRC_H) + +clean: + rm -vf $(PROGS) $(OBJECTS) $(DEPFILES) $(LIB) + rm -vf $(shell find -L . -iname '*~') + rm -vf $(ARCHIVE).tar.gz + rm -vrf $(EXTRA-CLEAN) tags *.dSYM + +format: + clang-format --style=file -i $(LIBSRC_C) $(LIBSRC_H) $(SRC_C) $(SRC_H) + +archive: clean + mkdir -p $(ARCHIVE) $(ARCHIVE)/libcsapp $(ARCHIVE)/include + cp -L $(SRCS) $(SRC_H) $(FILES) $(ARCHIVE)/ + cp -L $(LIBSRCS) $(ARCHIVE)/libcsapp/ + cp -L $(LIBSRC_H) $(ARCHIVE)/include/ + for f in $(SRCS:%=$(ARCHIVE)/%); do \ + sed --in-place='' -e '/^#if.*STUDENT/,/^#endif.*STUDENT/d' $$f; \ + done + tar cvzhf $(ARCHIVE).tar.gz $(ARCHIVE) + rm -rf $(ARCHIVE) + +.PHONY: all clean format archive + +# vim: ts=8 sw=8 noet diff --git a/check-files.py b/check-files.py new file mode 100755 index 0000000..1994d0f --- /dev/null +++ b/check-files.py @@ -0,0 +1,36 @@ +#!/usr/bin/env python3 + +import hashlib +import io + +STUDENT_CODE = ['shell.c', 'command.c', 'jobs.c'] + +def remove_solution(path): + drop = False + lines = [] + + for line in open(path).readlines(): + if line.startswith('#endif /* !STUDENT */'): + drop = False + if not drop: + lines.append(line) + if line.startswith('#ifdef STUDENT'): + drop = True + + return ''.join(lines).encode('utf-8') + + +if __name__ == '__main__': + for line in open('files.md5').readlines(): + md5_orig, path = line.split() + if path in STUDENT_CODE: + contents = remove_solution(path) + else: + contents = open(path, 'rb').read() + md5_new = hashlib.md5(contents).hexdigest() + if md5_orig != md5_new: + raise SystemExit( + f'Unauthorized modification of {path} file!\n' + f'MD5 sum: {md5_new} vs {md5_orig} (original)') + + print('No unauthorized changes to source files.') diff --git a/command.c b/command.c new file mode 100644 index 0000000..f26326e --- /dev/null +++ b/command.c @@ -0,0 +1,123 @@ +#include "shell.h" + +typedef int (*func_t)(char **argv); + +typedef struct { + const char *name; + func_t func; +} command_t; + +static int do_quit(char **argv) { + shutdownjobs(); + exit(EXIT_SUCCESS); +} + +/* + * Change current working directory. + * 'cd' - change to $HOME + * 'cd path' - change to provided path + */ +static int do_chdir(char **argv) { + char *path = argv[0]; + if (path == NULL) + path = getenv("HOME"); + int rc = chdir(path); + if (rc < 0) { + msg("cd: %s: %s\n", strerror(errno), path); + return 1; + } + return 0; +} + +/* + * Displays all stopped or running jobs. + */ +static int do_jobs(char **argv) { + watchjobs(ALL); + return 0; +} + +/* + * Move running or stopped background job to foreground. + * 'fg' choose highest numbered job + * 'fg n' choose job number n + */ +static int do_fg(char **argv) { + int j = argv[0] ? atoi(argv[0]) : -1; + + sigset_t mask; + Sigprocmask(SIG_BLOCK, &sigchld_mask, &mask); + if (!resumejob(j, FG, &mask)) + msg("fg: job not found: %s\n", argv[0]); + Sigprocmask(SIG_SETMASK, &mask, NULL); + return 0; +} + +/* + * Make stopped background job running. + * 'bg' choose highest numbered job + * 'bg n' choose job number n + */ +static int do_bg(char **argv) { + int j = argv[0] ? atoi(argv[0]) : -1; + + sigset_t mask; + Sigprocmask(SIG_BLOCK, &sigchld_mask, &mask); + if (!resumejob(j, BG, &mask)) + msg("bg: job not found: %s\n", argv[0]); + Sigprocmask(SIG_SETMASK, &mask, NULL); + return 0; +} + +/* + * Make stopped background job running. + * 'bg' choose highest numbered job + * 'bg n' choose job number n + */ +static int do_kill(char **argv) { + if (!argv[0]) + return -1; + if (*argv[0] != '%') + return -1; + + int j = atoi(argv[0] + 1); + + sigset_t mask; + Sigprocmask(SIG_BLOCK, &sigchld_mask, &mask); + if (!killjob(j)) + msg("kill: job not found: %s\n", argv[0]); + Sigprocmask(SIG_SETMASK, &mask, NULL); + + return 0; +} + +static command_t builtins[] = { + {"quit", do_quit}, {"cd", do_chdir}, {"jobs", do_jobs}, {"fg", do_fg}, + {"bg", do_bg}, {"kill", do_kill}, {NULL, NULL}, +}; + +int builtin_command(char **argv) { + for (command_t *cmd = builtins; cmd->name; cmd++) { + if (strcmp(argv[0], cmd->name)) + continue; + return cmd->func(&argv[1]); + } + + errno = ENOENT; + return -1; +} + +noreturn void external_command(char **argv) { + const char *path = getenv("PATH"); + + if (!index(argv[0], '/') && path) { + /* TODO: For all paths in PATH construct an absolute path and execve it. */ +#ifdef STUDENT +#endif /* !STUDENT */ + } else { + (void)execve(argv[0], argv, environ); + } + + msg("%s: %s\n", argv[0], strerror(errno)); + exit(EXIT_FAILURE); +} diff --git a/files.md5 b/files.md5 new file mode 100644 index 0000000..777109a --- /dev/null +++ b/files.md5 @@ -0,0 +1,82 @@ +2c63cba1b68e7fcb70c571533bc14d8c .github/classroom/autograding.json +b91dd9abba52fd90c0731aeb95290cdb .github/workflows/classroom.yml +8b18c4a6b06fc53caaec115bb554ecf0 include/bitstring.h +1d7d70b239717947dedcc42146517c0f include/csapp.h +032b0af815be72336b1545608c42ae20 include/queue.h +240d3ee4b5b69628a34fb24afe6adcc7 include/rio.h +f130fc97a7b8b184fdb7a7b9edc135ad include/terminal.h +106cd1cd138cf69164aecf162e34181f include/tree.h +d3cb72a88135352ec45a22bf19a457fa libcsapp/Accept.c +872c84ec6ca3e3ff2e897b46b7092428 libcsapp/app_error.c +a9128093162eac3f45a6cc599b30ac9d libcsapp/Bind.c +4270f2c382fbc1a0d6fe5f3b55a58209 libcsapp/Close.c +7c1fc769fa94df0e474e7314dc757ab9 libcsapp/Connect.c +3a727dc1f650d82febc5dfc03e7eb9d8 libcsapp/Dup2.c +39ff215c4eb93e9e92d663cabde59012 libcsapp/Dup.c +709ddbe5e701b6a508943d9553200e28 libcsapp/Fork.c +373f66f37f505ae57a2056c29edb47cf libcsapp/Fstatat.c +adc72b1b8dab5e7d3811210c0d1a8808 libcsapp/Fstat.c +357b34f1c33842ad46ea9f0fc0f3232a libcsapp/Ftruncate.c +25d5e2010db70fbd4690d020763d7714 libcsapp/gai_error.c +eb63679a884faa2d819ce51006b098ab libcsapp/Getaddrinfo.c +1d68e09e3506686fc40056501c3a7a78 libcsapp/Getcwd.c +5fe4907b467f0967d7184a9b2872a815 libcsapp/Getdents.c +0fbff37f9250c4a918b4717d4d42e89d libcsapp/Getnameinfo.c +313074a959bc3769795345b30937ab87 libcsapp/jenkins_hash.c +b58e14759d6ee0b2a8f2f48b9aa09e45 libcsapp/Kill.c +21b0a27225c3e85b59f035e2b2952edc libcsapp/Listen.c +5f2c95b094a0f2de49bff2c5a8877cab libcsapp/Lseek.c +26eeb6d6d20f993dd1de6bbf16ae998b libcsapp/Madvise.c +4dc37c23eda7ce1893c15dc530845276 libcsapp/memory.c +f2c5988977fe582920a967e1dd609fa1 libcsapp/Mmap.c +f795a9cfca99793a7e86acdde8335a0d libcsapp/Mprotect.c +3bcdb89ab44eb1afd367b3bc62b76c78 libcsapp/Munmap.c +8b14a6657f0acf0830c1ca85a5b4bb35 libcsapp/Open.c +bfd55e6755d47ac61ecb73f8eb17445d libcsapp/open_clientfd.c +27a25f8ee3b75ef07747629f7d3be3ba libcsapp/open_listenfd.c +8ab154f7cb7a6daff448be6a11cf7174 libcsapp/Pipe.c +7b6f8fc09bc56630cefba13aa748f31e libcsapp/Poll.c +230bee94bdcbc150f35c07dd70133d5b libcsapp/posix_cond.c +b56a31cdee027d53cc75bafcf429f2ff libcsapp/posix_error.c +a9783f0faa3ffac39207ae103e022f6a libcsapp/posix_mutex.c +3e5cbcf92ecd25999fa512b27c441c95 libcsapp/posix_rwlock.c +2cd117d8ed34b6fc75815471c8f51cdf libcsapp/posix_sem.c +54ae52da584e2d4ad05e87f420b27944 libcsapp/posix_thread.c +3e817b3baba27fbdf9a1238f0a04aa6b libcsapp/Prctl.c +5be9dcdd51f49ba4341503539b04f2dd libcsapp/Read.c +5a2997cec42ebabbbaa3e1ec58cf055b libcsapp/Readlinkat.c +7bcc07e466712dbd84555c5c649debd6 libcsapp/Readlink.c +e23d5214cde3063f7d21d9fd08cee4b9 libcsapp/Rename.c +4940fede87c9610d50a08d1128572bdd libcsapp/rio.c +74e2ef35d26cb44c6cdb953219cf1286 libcsapp/safe_printf.c +d9493ed00e9f9d19148c022abcc94f66 libcsapp/Select.c +2b2522cf698114b33bbe21e951fb7174 libcsapp/Setjmp.s +6d72de71b358d7753932cb381c8a2aa5 libcsapp/Setpgid.c +7249899661174fc747dc85f96a465a0f libcsapp/Setsockopt.c +7dd41de4b7642225f0de9d58dc126d4a libcsapp/Sigaction.c +01bd75a44bc64646b4050673ef67275a libcsapp/Signal.c +d53a3d8f6c86ae2343682d31746cf5f9 libcsapp/Sigprocmask.c +d6bc319b604c4b835c1d297d55997f06 libcsapp/Sigsuspend.c +5e5e4e6872fdeb3659696b9bff76f2f0 libcsapp/Socket.c +b331c9f8e9f9b34acd72e630856f8cfe libcsapp/Socketpair.c +5bf95dab4d01717a74589cf787cf5725 libcsapp/stdio.c +e1bdf0a17f9cad66766cce1ad7ab184b libcsapp/Tcgetattr.c +b608b7e1c91edc9979e1ba2b05e780b2 libcsapp/Tcgetpgrp.c +3e6f5f6b1f256ec7c5adb02719446b01 libcsapp/Tcsetattr.c +768e5f3d28de401e53f562f748418994 libcsapp/Tcsetpgrp.c +f2c4f280227b60895577b130536fcfa7 libcsapp/terminal.c +de04149c528b3fe3bd4f7dae5f230dd4 libcsapp/unix_error.c +83cc216630162b598fe43a49f80137fb libcsapp/Unlink.c +d73e0e55f2a67cf5b0d06c0bdc46a53b libcsapp/Waitpid.c +862dc92753b807b5fab203942c271a57 libcsapp/Write.c +890a936e8c42ec09891685b5bc14a9ed libcsapp/Writev.c +67f915b143d03c1c3b8c09dbaf46eda1 command.c +0a9f12f3746a1b06b9bb0f8c25a0379c jobs.c +14544aaf7c3ef7bfc18f4517a4af60e6 lexer.c +2ccf39657567f761b5955c528e97bb0e Makefile +0e64f86947504e65f060189b8653139d Makefile.include +bcfc4f95ca76a6f421b9457984146a84 run-clang-format.sh +789ffe4853ad2d99c6330e3c3fd0e683 shell.c +4b8571a1123fe082f04ef805ddb8bff2 shell.h +cfb87487a440cb24f991511e5ca9190e sh-tests.py +43eca75c03f44eebaadcf8e916ef5928 trace.c diff --git a/include/bitstring.h b/include/bitstring.h new file mode 100644 index 0000000..66503f0 --- /dev/null +++ b/include/bitstring.h @@ -0,0 +1,138 @@ +/* $NetBSD: bitstring.h,v 1.14 2016/03/17 02:25:32 christos Exp $ */ + +/* + * Copyright (c) 1989, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Paul Vixie. + * + * 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. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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. + * + * @(#)bitstring.h 8.1 (Berkeley) 7/19/93 + */ + +#ifndef _BITSTRING_H_ +#define _BITSTRING_H_ + +/* modified for SV/AT and bitstring bugfix by M.R.Murphy, 11oct91 + * bitstr_size changed gratuitously, but shorter + * bit_alloc spelling error fixed + * the following were efficient, but didn't work, they've been made to + * work, but are no longer as efficient :-) + * bit_nclear, bit_nset, bit_ffc, bit_ffs + */ +/* + * The comment above may or may not bear any resemblance to reality. + * This code has been maintained in a confusing way, with little + * information available on the provenance of much of it. "At least it + * works." + * /s/ Perry E. Metzger, 2 Feb 98 + */ +typedef unsigned char bitstr_t; + +/* internal macros */ +/* byte of the bitstring bit is in */ +#define _bit_byte(bit) (uint32_t)((bit) >> 3) + +/* mask for the bit within its byte */ +#define _bit_mask(bit) (uint32_t)((1 << (uint32_t)((bit)&0x7))) + +/* external macros */ +/* bytes in a bitstring of nbits bits */ +#define bitstr_size(nbits) (size_t)((uint32_t)((nbits) + 7) >> 3) + +/* allocate a bitstring */ +#define bit_alloc(nbits) calloc(bitstr_size(nbits), sizeof(bitstr_t)) + +/* allocate a bitstring on the stack */ +#define bit_decl(name, nbits) ((name)[bitstr_size(nbits)]) + +/* is bit N of bitstring name set? */ +#define bit_test(name, bit) \ + /*LINTED bitwise on signed*/ ((name)[_bit_byte(bit)] & _bit_mask(bit)) + +/* set bit N of bitstring name */ +#define bit_set(name, bit) \ + /*LINTED bitwise on signed*/ \ + ((name)[_bit_byte(bit)] = \ + (unsigned char)(_bit_mask(bit) | (name)[_bit_byte(bit)])) + +/* clear bit N of bitstring name */ +#define bit_clear(name, bit) \ + /*LINTED bitwise on signed*/ \ + ((name)[_bit_byte(bit)] &= (unsigned char)~_bit_mask(bit)) + +/* clear bits start ... stop in bitstring */ +#define bit_nclear(name, start, stop) \ + do { \ + bitstr_t *_name = name; \ + size_t _start = start, _stop = stop; \ + while (_start <= _stop) { \ + bit_clear(_name, _start); \ + _start++; \ + } \ + } while (/*CONSTCOND*/ 0) + +/* set bits start ... stop in bitstring */ +#define bit_nset(name, start, stop) \ + do { \ + bitstr_t *_name = name; \ + size_t _start = start, _stop = stop; \ + while (_start <= _stop) { \ + bit_set(_name, _start); \ + _start++; \ + } \ + } while (/*CONSTCOND*/ 0) + +/* find first bit clear in name */ +#define bit_ffc(name, nbits, value) \ + do { \ + const bitstr_t *_name = name; \ + size_t _bit, _nbits = nbits; \ + int _value = -1; \ + for (_bit = 0; _bit < _nbits; ++_bit) \ + if (!bit_test(_name, _bit)) { \ + _value = _bit; \ + break; \ + } \ + *(value) = _value; \ + } while (/*CONSTCOND*/ 0) + +/* find first bit set in name */ +#define bit_ffs(name, nbits, value) \ + do { \ + const bitstr_t *_name = name; \ + size_t _bit, _nbits = nbits; \ + int _value = -1; \ + for (_bit = 0; _bit < _nbits; ++_bit) \ + if (bit_test(_name, _bit)) { \ + _value = _bit; \ + break; \ + } \ + *(value) = _value; \ + } while (/*CONSTCOND*/ 0) + +#endif /* !_BITSTRING_H_ */ diff --git a/include/csapp.h b/include/csapp.h new file mode 100644 index 0000000..0bdb80e --- /dev/null +++ b/include/csapp.h @@ -0,0 +1,241 @@ +#ifndef __CSAPP_H__ +#define __CSAPP_H__ + +#include <sys/types.h> +#include <sys/mman.h> +#ifdef LINUX +#include <sys/sysmacros.h> +#include <sys/prctl.h> +#endif +#include <sys/select.h> +#include <sys/socket.h> +#include <sys/stat.h> +#include <sys/time.h> +#include <sys/uio.h> +#include <sys/user.h> +#include <sys/wait.h> +#include <arpa/inet.h> +#include <assert.h> +#include <ctype.h> +#include <errno.h> +#include <fcntl.h> +#include <grp.h> +#include <limits.h> +#include <netdb.h> +#include <netinet/in.h> +#include <poll.h> +#include <pthread.h> +#include <pwd.h> +#include <semaphore.h> +#include <setjmp.h> +#include <signal.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <stdbool.h> +#include <stdnoreturn.h> +#include <string.h> +#include <termios.h> +#include <time.h> +#include <unistd.h> + +#define _CONCAT(x, y) x##y +#define CONCAT(x, y) _CONCAT(x, y) + +#define min(a, b) \ + ({ \ + typeof(a) _a = (a); \ + typeof(b) _b = (b); \ + _a < _b ? _a : _b; \ + }) + +#define max(a, b) \ + ({ \ + typeof(a) _a = (a); \ + typeof(b) _b = (b); \ + _a > _b ? _a : _b; \ + }) + +#ifndef powerof2 +#define powerof2(x) (((x) & ((x)-1)) == 0) +#endif + +#ifndef __unused +#define __unused __attribute__((unused)) +#endif + +extern char **environ; + +/* According to termios(3) the maximum line length is 4096 chars + * (including the terminating newline character) */ +#define MAXLINE 4096 + +/* Our own error-handling functions */ +noreturn void unix_error(const char *fmt, ...) + __attribute__((format(printf, 1, 2))); +noreturn void posix_error(int code, const char *fmt, ...) + __attribute__((format(printf, 2, 3))); +noreturn void app_error(const char *fmt, ...) + __attribute__((format(printf, 1, 2))); +noreturn void gai_error(int code, const char *fmt, ...) + __attribute__((format(printf, 2, 3))); + +/* Signal safe I/O functions */ +void safe_printf(const char *fmt, ...) __attribute__((format(printf, 1, 2))); +void safe_error(const char *fmt, ...) __attribute__((format(printf, 1, 2))); + +/* Decent hashing function. */ +#define HASHINIT 5381 + +uint32_t jenkins_hash(const void *key, size_t length, uint32_t initval); + +/* Memory allocation wrappers */ +void *Malloc(size_t size); +void *Realloc(void *ptr, size_t size); +void *Calloc(size_t nmemb, size_t size); + +/* Process control wrappers */ +pid_t Fork(void); +pid_t Waitpid(pid_t pid, int *iptr, int options); +#define Wait(iptr) Waitpid(-1, iptr, 0) +void Prctl(int option, long arg); + +/* Process environment */ +char *Getcwd(char *buf, size_t buflen); + +/* Signal control wrappers */ +void (*Signal(int sig, void (*func)(int)))(int); +void Kill(pid_t pid, int sig); +void Sigprocmask(int how, const sigset_t *set, sigset_t *oldset); +void Sigaction(int signum, const struct sigaction *act, + struct sigaction *oldact); +void Sigsuspend(const sigset_t *mask); + +/* Process group control wrappers */ +void Setpgid(pid_t pid, pid_t pgid); + +/* Stdio wrappers */ +char *Fgets(char *ptr, int n, FILE *stream); +void Fputs(const char *ptr, FILE *stream); + +/* Unix I/O wrappers */ +int Open(const char *pathname, int flags, mode_t mode); +size_t Read(int fd, void *buf, size_t count); +size_t Write(int fd, const void *buf, size_t count); +size_t Writev(int fd, const struct iovec *iov, int iovcnt); +off_t Lseek(int fildes, off_t offset, int whence); +void Close(int fd); +void Ftruncate(int fd, off_t length); +int Dup(int fd); +int Dup2(int oldfd, int newfd); +void Pipe(int fds[2]); +void Socketpair(int domain, int type, int protocol, int sv[2]); +int Select(int n, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, + struct timeval *timeout); +int Poll(struct pollfd *fds, nfds_t nfds, int timeout); + +/* Directory access (Linux specific) */ +struct linux_dirent { + unsigned long d_ino; /* Inode number */ + unsigned long d_off; /* Offset to next linux_dirent */ + unsigned short d_reclen; /* Length of this linux_dirent */ + char d_name[]; /* Filename (null-terminated) */ +}; + +int Getdents(int fd, struct linux_dirent *dirp, unsigned count); + +/* Directory operations */ +void Rename(const char *oldpath, const char *newpath); +void Unlink(const char *pathname); + +/* File metadata access wrapper */ +void Fstat(int fd, struct stat *statbuf); +void Fstatat(int dirfd, const char *pathname, struct stat *statbuf, int flags); +size_t Readlink(const char *pathname, char *buf, size_t bufsiz); +size_t Readlinkat(int dirfd, const char *pathname, char *buf, size_t bufsiz); + +/* Memory mapped files & anonymous memory */ +void *Mmap(void *addr, size_t length, int prot, int flags, int fd, + off_t offset); +void Mprotect(void *addr, size_t len, int prot); +void Munmap(void *addr, size_t len); +void Madvise(void *addr, size_t length, int advice); + +/* Terminal control */ +void Tcsetpgrp(int fd, pid_t pgrp); +pid_t Tcgetpgrp(int fd); +void Tcsetattr(int fd, int action, const struct termios *termios_p); +void Tcgetattr(int fd, struct termios *termios_p); + +/* Setjmp & longjmp implementation without sigprocmask */ +typedef struct { + long rbx; + long rbp; + long r12; + long r13; + long r14; + long r15; + void *rsp; + void *rip; +} Jmpbuf[1]; + +int Setjmp(Jmpbuf env); +noreturn void Longjmp(Jmpbuf env, int val); + +/* Socket interface wrappers. */ +typedef struct sockaddr SA; +int Socket(int domain, int type, int protocol); +void Setsockopt(int s, int level, int optname, const void *optval, int optlen); +void Bind(int sockfd, struct sockaddr *my_addr, int addrlen); +void Listen(int s, int backlog); +int Accept(int s, struct sockaddr *addr, socklen_t *addrlen); +void Connect(int sockfd, struct sockaddr *serv_addr, int addrlen); + +/* Protocol-independent wrappers. */ +void Getaddrinfo(const char *node, const char *service, + const struct addrinfo *hints, struct addrinfo **res); +void Getnameinfo(const struct sockaddr *sa, socklen_t salen, char *host, + size_t hostlen, char *serv, size_t servlen, int flags); +int open_clientfd(char *hostname, char *port); +int Open_clientfd(char *hostname, char *port); +int open_listenfd(char *port, int backlog); +int Open_listenfd(char *port, int backlog); + +/* POSIX thread control wrappers. */ + +void Pthread_create(pthread_t *tidp, pthread_attr_t *attrp, + void *(*routine)(void *), void *argp); +void Pthread_cancel(pthread_t tid); +void Pthread_join(pthread_t tid, void **thread_return); +void Pthread_detach(pthread_t tid); + +/* POSIX semaphore wrappers. */ +void Sem_init(sem_t *sem, int pshared, unsigned value); +void Sem_destroy(sem_t *sem); +void Sem_wait(sem_t *sem); +void Sem_getvalue(sem_t *sem, int *sval); +void Sem_post(sem_t *sem); + +/* POSIX mutex wrappers. */ +void Pthread_mutex_init(pthread_mutex_t *mutex, + const pthread_mutexattr_t *mutexattr); +void Pthread_mutex_destroy(pthread_mutex_t *mutex); +void Pthread_mutex_lock(pthread_mutex_t *mutex); +void Pthread_mutex_unlock(pthread_mutex_t *mutex); + +/* POSIX conditional variable wrappers. */ +void Pthread_cond_init(pthread_cond_t *cond, pthread_condattr_t *cond_attr); +void Pthread_cond_destroy(pthread_cond_t *cond); +void Pthread_cond_signal(pthread_cond_t *cond); +void Pthread_cond_broadcast(pthread_cond_t *cond); +void Pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex); + +/* POSIX reader-writer lock wrappers. */ +void Pthread_rwlock_init(pthread_rwlock_t *rwlock, + const pthread_rwlockattr_t *rwlockattr); +void Pthread_rwlock_destroy(pthread_rwlock_t *rwlock); +void Pthread_rwlock_rdlock(pthread_rwlock_t *rwlock); +void Pthread_rwlock_wrlock(pthread_rwlock_t *rwlock); +void Pthread_rwlock_unlock(pthread_rwlock_t *rwlock); + +#endif /* __CSAPP_H__ */ diff --git a/include/queue.h b/include/queue.h new file mode 100644 index 0000000..de4ddc9 --- /dev/null +++ b/include/queue.h @@ -0,0 +1,587 @@ +/* $NetBSD: queue.h,v 1.74 2019/03/23 12:01:18 maxv Exp $ */ + +/* + * Copyright (c) 1991, 1993 + * The Regents of the University of California. 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. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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. + * + * @(#)queue.h 8.5 (Berkeley) 8/20/94 + */ + +#ifndef _QUEUE_H_ +#define _QUEUE_H_ + +/* + * This file defines five types of data structures: singly-linked lists, + * lists, simple queues, tail queues, and circular queues. + * + * A singly-linked list is headed by a single forward pointer. The + * elements are singly linked for minimum space and pointer manipulation + * overhead at the expense of O(n) removal for arbitrary elements. New + * elements can be added to the list after an existing element or at the + * head of the list. Elements being removed from the head of the list + * should use the explicit macro for this purpose for optimum + * efficiency. A singly-linked list may only be traversed in the forward + * direction. Singly-linked lists are ideal for applications with large + * datasets and few or no removals or for implementing a LIFO queue. + * + * A list is headed by a single forward pointer (or an array of forward + * pointers for a hash table header). The elements are doubly linked + * so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before + * or after an existing element or at the head of the list. A list + * may only be traversed in the forward direction. + * + * A simple queue is headed by a pair of pointers, one the head of the + * list and the other to the tail of the list. The elements are singly + * linked to save space, so elements can only be removed from the + * head of the list. New elements can be added to the list after + * an existing element, at the head of the list, or at the end of the + * list. A simple queue may only be traversed in the forward direction. + * + * A tail queue is headed by a pair of pointers, one to the head of the + * list and the other to the tail of the list. The elements are doubly + * linked so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before or + * after an existing element, at the head of the list, or at the end of + * the list. A tail queue may be traversed in either direction. + * + * A circle queue is headed by a pair of pointers, one to the head of the + * list and the other to the tail of the list. The elements are doubly + * linked so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before or after + * an existing element, at the head of the list, or at the end of the list. + * A circle queue may be traversed in either direction, but has a more + * complex end of list detection. + * + * For details on the use of these macros, see the queue(3) manual page. + */ + +/* + * Include the definition of NULL only on NetBSD because sys/null.h + * is not available elsewhere. This conditional makes the header + * portable and it can simply be dropped verbatim into any system. + * The caveat is that on other systems some other header + * must provide NULL before the macros can be used. + */ + +/* + * Singly-linked List definitions. + */ +#define SLIST_HEAD(name, type) \ + struct name { \ + struct type *slh_first; /* first element */ \ + } + +#define SLIST_HEAD_INITIALIZER(head) \ + { NULL } + +#define SLIST_ENTRY(type) \ + struct { \ + struct type *sle_next; /* next element */ \ + } + +/* + * Singly-linked List access methods. + */ +#define SLIST_FIRST(head) ((head)->slh_first) +#define SLIST_END(head) NULL +#define SLIST_EMPTY(head) ((head)->slh_first == NULL) +#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) + +#define SLIST_FOREACH(var, head, field) \ + for ((var) = (head)->slh_first; (var) != SLIST_END(head); \ + (var) = (var)->field.sle_next) + +#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = SLIST_FIRST((head)); \ + (var) != SLIST_END(head) && ((tvar) = SLIST_NEXT((var), field), 1); \ + (var) = (tvar)) + +/* + * Singly-linked List functions. + */ +#define SLIST_INIT(head) \ + do { \ + (head)->slh_first = SLIST_END(head); \ + } while (/*CONSTCOND*/ 0) + +#define SLIST_INSERT_AFTER(slistelm, elm, field) \ + do { \ + (elm)->field.sle_next = (slistelm)->field.sle_next; \ + (slistelm)->field.sle_next = (elm); \ + } while (/*CONSTCOND*/ 0) + +#define SLIST_INSERT_HEAD(head, elm, field) \ + do { \ + (elm)->field.sle_next = (head)->slh_first; \ + (head)->slh_first = (elm); \ + } while (/*CONSTCOND*/ 0) + +#define SLIST_REMOVE_AFTER(slistelm, field) \ + do { \ + (slistelm)->field.sle_next = \ + SLIST_NEXT(SLIST_NEXT((slistelm), field), field); \ + } while (/*CONSTCOND*/ 0) + +#define SLIST_REMOVE_HEAD(head, field) \ + do { \ + (head)->slh_first = (head)->slh_first->field.sle_next; \ + } while (/*CONSTCOND*/ 0) + +#define SLIST_REMOVE(head, elm, type, field) \ + do { \ + if ((head)->slh_first == (elm)) { \ + SLIST_REMOVE_HEAD((head), field); \ + } else { \ + struct type *curelm = (head)->slh_first; \ + while (curelm->field.sle_next != (elm)) \ + curelm = curelm->field.sle_next; \ + curelm->field.sle_next = curelm->field.sle_next->field.sle_next; \ + } \ + } while (/*CONSTCOND*/ 0) + +/* + * List definitions. + */ +#define LIST_HEAD(name, type) \ + struct name { \ + struct type *lh_first; /* first element */ \ + } + +#define LIST_HEAD_INITIALIZER(head) \ + { NULL } + +#define LIST_ENTRY(type) \ + struct { \ + struct type *le_next; /* next element */ \ + struct type **le_prev; /* address of previous next element */ \ + } + +/* + * List access methods. + */ +#define LIST_FIRST(head) ((head)->lh_first) +#define LIST_END(head) NULL +#define LIST_EMPTY(head) ((head)->lh_first == LIST_END(head)) +#define LIST_NEXT(elm, field) ((elm)->field.le_next) + +#define LIST_FOREACH(var, head, field) \ + for ((var) = ((head)->lh_first); (var) != LIST_END(head); \ + (var) = ((var)->field.le_next)) + +#define LIST_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = LIST_FIRST((head)); \ + (var) != LIST_END(head) && ((tvar) = LIST_NEXT((var), field), 1); \ + (var) = (tvar)) + +#define LIST_MOVE(head1, head2, field) \ + do { \ + LIST_INIT((head2)); \ + if (!LIST_EMPTY((head1))) { \ + (head2)->lh_first = (head1)->lh_first; \ + (head2)->lh_first->field.le_prev = &(head2)->lh_first; \ + LIST_INIT((head1)); \ + } \ + } while (/*CONSTCOND*/ 0) + +/* + * List functions. + */ +#define LIST_INIT(head) \ + do { \ + (head)->lh_first = LIST_END(head); \ + } while (/*CONSTCOND*/ 0) + +#define LIST_INSERT_AFTER(listelm, elm, field) \ + do { \ + if (((elm)->field.le_next = (listelm)->field.le_next) != LIST_END(head)) \ + (listelm)->field.le_next->field.le_prev = &(elm)->field.le_next; \ + (listelm)->field.le_next = (elm); \ + (elm)->field.le_prev = &(listelm)->field.le_next; \ + } while (/*CONSTCOND*/ 0) + +#define LIST_INSERT_BEFORE(listelm, elm, field) \ + do { \ + (elm)->field.le_prev = (listelm)->field.le_prev; \ + (elm)->field.le_next = (listelm); \ + *(listelm)->field.le_prev = (elm); \ + (listelm)->field.le_prev = &(elm)->field.le_next; \ + } while (/*CONSTCOND*/ 0) + +#define LIST_INSERT_HEAD(head, elm, field) \ + do { \ + if (((elm)->field.le_next = (head)->lh_first) != LIST_END(head)) \ + (head)->lh_first->field.le_prev = &(elm)->field.le_next; \ + (head)->lh_first = (elm); \ + (elm)->field.le_prev = &(head)->lh_first; \ + } while (/*CONSTCOND*/ 0) + +#define LIST_REMOVE(elm, field) \ + do { \ + if ((elm)->field.le_next != NULL) \ + (elm)->field.le_next->field.le_prev = (elm)->field.le_prev; \ + *(elm)->field.le_prev = (elm)->field.le_next; \ + } while (/*CONSTCOND*/ 0) + +#define LIST_REPLACE(elm, elm2, field) \ + do { \ + if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \ + (elm2)->field.le_next->field.le_prev = &(elm2)->field.le_next; \ + (elm2)->field.le_prev = (elm)->field.le_prev; \ + *(elm2)->field.le_prev = (elm2); \ + } while (/*CONSTCOND*/ 0) + +/* + * Simple queue definitions. + */ +#define SIMPLEQ_HEAD(name, type) \ + struct name { \ + struct type *sqh_first; /* first element */ \ + struct type **sqh_last; /* addr of last next element */ \ + } + +#define SIMPLEQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).sqh_first } + +#define SIMPLEQ_ENTRY(type) \ + struct { \ + struct type *sqe_next; /* next element */ \ + } + +/* + * Simple queue access methods. + */ +#define SIMPLEQ_FIRST(head) ((head)->sqh_first) +#define SIMPLEQ_END(head) NULL +#define SIMPLEQ_EMPTY(head) ((head)->sqh_first == SIMPLEQ_END(head)) +#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) + +#define SIMPLEQ_FOREACH(var, head, field) \ + for ((var) = ((head)->sqh_first); (var) != SIMPLEQ_END(head); \ + (var) = ((var)->field.sqe_next)) + +#define SIMPLEQ_FOREACH_SAFE(var, head, field, next) \ + for ((var) = ((head)->sqh_first); \ + (var) != SIMPLEQ_END(head) && ((next = ((var)->field.sqe_next)), 1); \ + (var) = (next)) + +/* + * Simple queue functions. + */ +#define SIMPLEQ_INIT(head) \ + do { \ + (head)->sqh_first = NULL; \ + (head)->sqh_last = &(head)->sqh_first; \ + } while (/*CONSTCOND*/ 0) + +#define SIMPLEQ_INSERT_HEAD(head, elm, field) \ + do { \ + if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ + (head)->sqh_last = &(elm)->field.sqe_next; \ + (head)->sqh_first = (elm); \ + } while (/*CONSTCOND*/ 0) + +#define SIMPLEQ_INSERT_TAIL(head, elm, field) \ + do { \ + (elm)->field.sqe_next = NULL; \ + *(head)->sqh_last = (elm); \ + (head)->sqh_last = &(elm)->field.sqe_next; \ + } while (/*CONSTCOND*/ 0) + +#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) \ + do { \ + if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL) \ + (head)->sqh_last = &(elm)->field.sqe_next; \ + (listelm)->field.sqe_next = (elm); \ + } while (/*CONSTCOND*/ 0) + +#define SIMPLEQ_REMOVE_HEAD(head, field) \ + do { \ + if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \ + (head)->sqh_last = &(head)->sqh_first; \ + } while (/*CONSTCOND*/ 0) + +#define SIMPLEQ_REMOVE_AFTER(head, elm, field) \ + do { \ + if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) == \ + NULL) \ + (head)->sqh_last = &(elm)->field.sqe_next; \ + } while (/*CONSTCOND*/ 0) + +#define SIMPLEQ_REMOVE(head, elm, type, field) \ + do { \ + if ((head)->sqh_first == (elm)) { \ + SIMPLEQ_REMOVE_HEAD((head), field); \ + } else { \ + struct type *curelm = (head)->sqh_first; \ + while (curelm->field.sqe_next != (elm)) \ + curelm = curelm->field.sqe_next; \ + if ((curelm->field.sqe_next = curelm->field.sqe_next->field.sqe_next) == \ + NULL) \ + (head)->sqh_last = &(curelm)->field.sqe_next; \ + } \ + } while (/*CONSTCOND*/ 0) + +#define SIMPLEQ_CONCAT(head1, head2) \ + do { \ + if (!SIMPLEQ_EMPTY((head2))) { \ + *(head1)->sqh_last = (head2)->sqh_first; \ + (head1)->sqh_last = (head2)->sqh_last; \ + SIMPLEQ_INIT((head2)); \ + } \ + } while (/*CONSTCOND*/ 0) + +#define SIMPLEQ_LAST(head, type, field) \ + (SIMPLEQ_EMPTY((head)) \ + ? NULL \ + : ((struct type *)(void *)((char *)((head)->sqh_last) - \ + offsetof(struct type, field)))) + +/* + * Tail queue definitions. + */ +#define _TAILQ_HEAD(name, type, qual) \ + struct name { \ + qual type *tqh_first; /* first element */ \ + qual type *qual *tqh_last; /* addr of last next element */ \ + } +#define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type, ) + +#define TAILQ_HEAD_INITIALIZER(head) \ + { TAILQ_END(head), &(head).tqh_first } + +#define _TAILQ_ENTRY(type, qual) \ + struct { \ + qual type *tqe_next; /* next element */ \ + qual type *qual *tqe_prev; /* address of previous next element */ \ + } +#define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type, ) + +/* + * Tail queue access methods. + */ +#define TAILQ_FIRST(head) ((head)->tqh_first) +#define TAILQ_END(head) (NULL) +#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) +#define TAILQ_LAST(head, headname) \ + (*(((struct headname *)(void *)((head)->tqh_last))->tqh_last)) +#define TAILQ_PREV(elm, headname, field) \ + (*(((struct headname *)(void *)((elm)->field.tqe_prev))->tqh_last)) +#define TAILQ_EMPTY(head) (TAILQ_FIRST(head) == TAILQ_END(head)) + +#define TAILQ_FOREACH(var, head, field) \ + for ((var) = ((head)->tqh_first); (var) != TAILQ_END(head); \ + (var) = ((var)->field.tqe_next)) + +#define TAILQ_FOREACH_SAFE(var, head, field, next) \ + for ((var) = ((head)->tqh_first); \ + (var) != TAILQ_END(head) && ((next) = TAILQ_NEXT(var, field), 1); \ + (var) = (next)) + +#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ + for ((var) = TAILQ_LAST((head), headname); (var) != TAILQ_END(head); \ + (var) = TAILQ_PREV((var), headname, field)) + +#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, prev) \ + for ((var) = TAILQ_LAST((head), headname); \ + (var) != TAILQ_END(head) && \ + ((prev) = TAILQ_PREV((var), headname, field), 1); \ + (var) = (prev)) + +/* + * Tail queue functions. + */ +#define TAILQ_INIT(head) \ + do { \ + (head)->tqh_first = TAILQ_END(head); \ + (head)->tqh_last = &(head)->tqh_first; \ + } while (/*CONSTCOND*/ 0) + +#define TAILQ_INSERT_HEAD(head, elm, field) \ + do { \ + if (((elm)->field.tqe_next = (head)->tqh_first) != TAILQ_END(head)) \ + (head)->tqh_first->field.tqe_prev = &(elm)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm)->field.tqe_next; \ + (head)->tqh_first = (elm); \ + (elm)->field.tqe_prev = &(head)->tqh_first; \ + } while (/*CONSTCOND*/ 0) + +#define TAILQ_INSERT_TAIL(head, elm, field) \ + do { \ + (elm)->field.tqe_next = TAILQ_END(head); \ + (elm)->field.tqe_prev = (head)->tqh_last; \ + *(head)->tqh_last = (elm); \ + (head)->tqh_last = &(elm)->field.tqe_next; \ + } while (/*CONSTCOND*/ 0) + +#define TAILQ_INSERT_AFTER(head, listelm, elm, field) \ + do { \ + if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != \ + TAILQ_END(head)) \ + (elm)->field.tqe_next->field.tqe_prev = &(elm)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm)->field.tqe_next; \ + (listelm)->field.tqe_next = (elm); \ + (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ + } while (/*CONSTCOND*/ 0) + +#define TAILQ_INSERT_BEFORE(listelm, elm, field) \ + do { \ + (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ + (elm)->field.tqe_next = (listelm); \ + *(listelm)->field.tqe_prev = (elm); \ + (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ + } while (/*CONSTCOND*/ 0) + +#define TAILQ_REMOVE(head, elm, field) \ + do { \ + if (((elm)->field.tqe_next) != TAILQ_END(head)) \ + (elm)->field.tqe_next->field.tqe_prev = (elm)->field.tqe_prev; \ + else \ + (head)->tqh_last = (elm)->field.tqe_prev; \ + *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ + } while (/*CONSTCOND*/ 0) + +#define TAILQ_REPLACE(head, elm, elm2, field) \ + do { \ + if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != TAILQ_END(head)) \ + (elm2)->field.tqe_next->field.tqe_prev = &(elm2)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm2)->field.tqe_next; \ + (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \ + *(elm2)->field.tqe_prev = (elm2); \ + } while (/*CONSTCOND*/ 0) + +#define TAILQ_CONCAT(head1, head2, field) \ + do { \ + if (!TAILQ_EMPTY(head2)) { \ + *(head1)->tqh_last = (head2)->tqh_first; \ + (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ + (head1)->tqh_last = (head2)->tqh_last; \ + TAILQ_INIT((head2)); \ + } \ + } while (/*CONSTCOND*/ 0) + +/* + * Singly-linked Tail queue declarations. + */ +#define STAILQ_HEAD(name, type) \ + struct name { \ + struct type *stqh_first; /* first element */ \ + struct type **stqh_last; /* addr of last next element */ \ + } + +#define STAILQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).stqh_first } + +#define STAILQ_ENTRY(type) \ + struct { \ + struct type *stqe_next; /* next element */ \ + } + +/* + * Singly-linked Tail queue access methods. + */ +#define STAILQ_FIRST(head) ((head)->stqh_first) +#define STAILQ_END(head) NULL +#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) +#define STAILQ_EMPTY(head) (STAILQ_FIRST(head) == STAILQ_END(head)) + +/* + * Singly-linked Tail queue functions. + */ +#define STAILQ_INIT(head) \ + do { \ + (head)->stqh_first = NULL; \ + (head)->stqh_last = &(head)->stqh_first; \ + } while (/*CONSTCOND*/ 0) + +#define STAILQ_INSERT_HEAD(head, elm, field) \ + do { \ + if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \ + (head)->stqh_last = &(elm)->field.stqe_next; \ + (head)->stqh_first = (elm); \ + } while (/*CONSTCOND*/ 0) + +#define STAILQ_INSERT_TAIL(head, elm, field) \ + do { \ + (elm)->field.stqe_next = NULL; \ + *(head)->stqh_last = (elm); \ + (head)->stqh_last = &(elm)->field.stqe_next; \ + } while (/*CONSTCOND*/ 0) + +#define STAILQ_INSERT_AFTER(head, listelm, elm, field) \ + do { \ + if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL) \ + (head)->stqh_last = &(elm)->field.stqe_next; \ + (listelm)->field.stqe_next = (elm); \ + } while (/*CONSTCOND*/ 0) + +#define STAILQ_REMOVE_HEAD(head, field) \ + do { \ + if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \ + (head)->stqh_last = &(head)->stqh_first; \ + } while (/*CONSTCOND*/ 0) + +#define STAILQ_REMOVE(head, elm, type, field) \ + do { \ + if ((head)->stqh_first == (elm)) { \ + STAILQ_REMOVE_HEAD((head), field); \ + } else { \ + struct type *curelm = (head)->stqh_first; \ + while (curelm->field.stqe_next != (elm)) \ + curelm = curelm->field.stqe_next; \ + if ((curelm->field.stqe_next = \ + curelm->field.stqe_next->field.stqe_next) == NULL) \ + (head)->stqh_last = &(curelm)->field.stqe_next; \ + } \ + } while (/*CONSTCOND*/ 0) + +#define STAILQ_FOREACH(var, head, field) \ + for ((var) = ((head)->stqh_first); (var); (var) = ((var)->field.stqe_next)) + +#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = STAILQ_FIRST((head)); \ + (var) && ((tvar) = STAILQ_NEXT((var), field), 1); (var) = (tvar)) + +#define STAILQ_CONCAT(head1, head2) \ + do { \ + if (!STAILQ_EMPTY((head2))) { \ + *(head1)->stqh_last = (head2)->stqh_first; \ + (head1)->stqh_last = (head2)->stqh_last; \ + STAILQ_INIT((head2)); \ + } \ + } while (/*CONSTCOND*/ 0) + +#define STAILQ_LAST(head, type, field) \ + (STAILQ_EMPTY((head)) \ + ? NULL \ + : ((struct type *)(void *)((char *)((head)->stqh_last) - \ + offsetof(struct type, field)))) + +#endif /* !_QUEUE_H_ */ diff --git a/include/rio.h b/include/rio.h new file mode 100644 index 0000000..bd62723 --- /dev/null +++ b/include/rio.h @@ -0,0 +1,27 @@ +#ifndef _RIO_H_ +#define _RIO_H_ + +/* Persistent state for the robust I/O (Rio) package */ +#define RIO_BUFSIZE 8192 + +typedef struct { + int rio_fd; /* Descriptor for this internal buf */ + int rio_cnt; /* Unread bytes in internal buf */ + char *rio_bufptr; /* Next unread byte in internal buf */ + char rio_buf[RIO_BUFSIZE]; /* Internal buffer */ +} rio_t; + +/* Rio (Robust I/O) package */ +ssize_t rio_readn(int fd, void *usrbuf, size_t n); +ssize_t rio_writen(int fd, const void *usrbuf, size_t n); +void rio_readinitb(rio_t *rp, int fd); +ssize_t rio_readnb(rio_t *rp, void *usrbuf, size_t n); +ssize_t rio_readlineb(rio_t *rp, void *usrbuf, size_t maxlen); + +/* Wrappers that exit on failure */ +ssize_t Rio_readn(int fd, void *ptr, size_t nbytes); +void Rio_writen(int fd, const void *usrbuf, size_t n); +ssize_t Rio_readnb(rio_t *rp, void *usrbuf, size_t n); +ssize_t Rio_readlineb(rio_t *rp, void *usrbuf, size_t maxlen); + +#endif /* !_RIO_H_ */ diff --git a/include/terminal.h b/include/terminal.h new file mode 100644 index 0000000..832358e --- /dev/null +++ b/include/terminal.h @@ -0,0 +1,27 @@ +#ifndef _TERMINAL_H_ +#define _TERMINAL_H_ + +int tty_open(void); +void tty_curpos(int fd, int *x, int *y); + +/* https://en.wikipedia.org/wiki/ANSI_escape_code#Terminal_output_sequences */ + +#define ESC "\033" +#define CSI ESC "[" + +#define CUU(n) CSI #n "A" /* Cursor Up */ +#define CUD(n) CSI #n "B" /* Cursor Down */ +#define CUF(n) CSI #n "C" /* Cursor Forward */ +#define CUB(n) CSI #n "D" /* Cursor Back */ +#define CNL(n) CSI #n "E" /* Cursor Next Line */ +#define CPL(n) CSI #n "F" /* Cursor Previous Line */ +#define CHA(n) CSI #n "G" /* Cursor Horizontal Absolute */ +#define CUP(n, m) CSI #n ";" #m "H" /* Cursor Position */ +#define ED(n) CSI #n "J" /* Erase in Display */ +#define EL(n) CSI #n "K" /* Erase in Line */ +#define SU(n) CSI #n "S" /* Scroll Up Scroll */ +#define SD(n) CSI #n "T" /* Scroll Down Scroll */ +#define CPR() CSI "6n" /* Cursor Position Report */ +#define SGR(x) CSI x "m" + +#endif /* !_ANSICODES_H_ */ diff --git a/include/tree.h b/include/tree.h new file mode 100644 index 0000000..4a3413f --- /dev/null +++ b/include/tree.h @@ -0,0 +1,735 @@ +/* $NetBSD: tree.h,v 1.20 2013/09/14 13:20:45 joerg Exp $ */ +/* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */ +/* + * Copyright 2002 Niels Provos <provos@citi.umich.edu> + * 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 ``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 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. + */ + +#ifndef _TREE_H_ +#define _TREE_H_ + +/* + * This file defines data structures for different types of trees: + * splay trees and red-black trees. + * + * A splay tree is a self-organizing data structure. Every operation + * on the tree causes a splay to happen. The splay moves the requested + * node to the root of the tree and partly rebalances it. + * + * This has the benefit that request locality causes faster lookups as + * the requested nodes move to the top of the tree. On the other hand, + * every lookup causes memory writes. + * + * The Balance Theorem bounds the total access time for m operations + * and n inserts on an initially empty tree as O((m + n)lg n). The + * amortized cost for a sequence of m accesses to a splay tree is O(lg n); + * + * A red-black tree is a binary search tree with the node color as an + * extra attribute. It fulfills a set of conditions: + * - every search path from the root to a leaf consists of the + * same number of black nodes, + * - each red node (except for the root) has a black parent, + * - each leaf node is black. + * + * Every operation on a red-black tree is bounded as O(lg n). + * The maximum height of a red-black tree is 2lg (n+1). + */ + +#define SPLAY_HEAD(name, type) \ + struct name { \ + struct type *sph_root; /* root of the tree */ \ + } + +#define SPLAY_INITIALIZER(root) \ + { NULL } + +#define SPLAY_INIT(root) \ + do { \ + (root)->sph_root = NULL; \ + } while (/*CONSTCOND*/ 0) + +#define SPLAY_ENTRY(type) \ + struct { \ + struct type *spe_left; /* left element */ \ + struct type *spe_right; /* right element */ \ + } + +#define SPLAY_LEFT(elm, field) (elm)->field.spe_left +#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right +#define SPLAY_ROOT(head) (head)->sph_root +#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) + +/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ +#define SPLAY_ROTATE_RIGHT(head, tmp, field) \ + do { \ + SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ + SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ + (head)->sph_root = tmp; \ + } while (/*CONSTCOND*/ 0) + +#define SPLAY_ROTATE_LEFT(head, tmp, field) \ + do { \ + SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ + SPLAY_LEFT(tmp, field) = (head)->sph_root; \ + (head)->sph_root = tmp; \ + } while (/*CONSTCOND*/ 0) + +#define SPLAY_LINKLEFT(head, tmp, field) \ + do { \ + SPLAY_LEFT(tmp, field) = (head)->sph_root; \ + tmp = (head)->sph_root; \ + (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ + } while (/*CONSTCOND*/ 0) + +#define SPLAY_LINKRIGHT(head, tmp, field) \ + do { \ + SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ + tmp = (head)->sph_root; \ + (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ + } while (/*CONSTCOND*/ 0) + +#define SPLAY_ASSEMBLE(head, node, left, right, field) \ + do { \ + SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ + SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field); \ + SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ + SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ + } while (/*CONSTCOND*/ 0) + +/* Generates prototypes and inline functions */ + +#define SPLAY_PROTOTYPE(name, type, field, cmp) \ + void name##_SPLAY(struct name *, struct type *); \ + void name##_SPLAY_MINMAX(struct name *, int); \ + struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ + struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ + \ + /* Finds the node with the same key as elm */ \ + static __inline struct type *name##_SPLAY_FIND(struct name *head, \ + struct type *elm) { \ + if (SPLAY_EMPTY(head)) \ + return (NULL); \ + name##_SPLAY(head, elm); \ + if ((cmp)(elm, (head)->sph_root) == 0) \ + return (head->sph_root); \ + return (NULL); \ + } \ + \ + static __inline __unused struct type *name##_SPLAY_NEXT(struct name *head, \ + struct type *elm) { \ + name##_SPLAY(head, elm); \ + if (SPLAY_RIGHT(elm, field) != NULL) { \ + elm = SPLAY_RIGHT(elm, field); \ + while (SPLAY_LEFT(elm, field) != NULL) { \ + elm = SPLAY_LEFT(elm, field); \ + } \ + } else \ + elm = NULL; \ + return (elm); \ + } \ + \ + static __unused __inline struct type *name##_SPLAY_MIN_MAX( \ + struct name *head, int val) { \ + name##_SPLAY_MINMAX(head, val); \ + return (SPLAY_ROOT(head)); \ + } + +/* Main splay operation. + * Moves node close to the key of elm to top + */ +#define SPLAY_GENERATE(name, type, field, cmp) \ + struct type *name##_SPLAY_INSERT(struct name *head, struct type *elm) { \ + if (SPLAY_EMPTY(head)) { \ + SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ + } else { \ + int __comp; \ + name##_SPLAY(head, elm); \ + __comp = (cmp)(elm, (head)->sph_root); \ + if (__comp < 0) { \ + SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field); \ + SPLAY_RIGHT(elm, field) = (head)->sph_root; \ + SPLAY_LEFT((head)->sph_root, field) = NULL; \ + } else if (__comp > 0) { \ + SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field); \ + SPLAY_LEFT(elm, field) = (head)->sph_root; \ + SPLAY_RIGHT((head)->sph_root, field) = NULL; \ + } else \ + return ((head)->sph_root); \ + } \ + (head)->sph_root = (elm); \ + return (NULL); \ + } \ + \ + struct type *name##_SPLAY_REMOVE(struct name *head, struct type *elm) { \ + struct type *__tmp; \ + if (SPLAY_EMPTY(head)) \ + return (NULL); \ + name##_SPLAY(head, elm); \ + if ((cmp)(elm, (head)->sph_root) == 0) { \ + if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ + (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ + } else { \ + __tmp = SPLAY_RIGHT((head)->sph_root, field); \ + (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ + name##_SPLAY(head, elm); \ + SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ + } \ + return (elm); \ + } \ + return (NULL); \ + } \ + \ + void name##_SPLAY(struct name *head, struct type *elm) { \ + struct type __node, *__left, *__right, *__tmp; \ + int __comp; \ + \ + SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ + __left = __right = &__node; \ + \ + while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ + if (__comp < 0) { \ + __tmp = SPLAY_LEFT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if ((cmp)(elm, __tmp) < 0) { \ + SPLAY_ROTATE_RIGHT(head, __tmp, field); \ + if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ + break; \ + } \ + SPLAY_LINKLEFT(head, __right, field); \ + } else if (__comp > 0) { \ + __tmp = SPLAY_RIGHT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if ((cmp)(elm, __tmp) > 0) { \ + SPLAY_ROTATE_LEFT(head, __tmp, field); \ + if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ + break; \ + } \ + SPLAY_LINKRIGHT(head, __left, field); \ + } \ + } \ + SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ + } \ + \ + /* Splay with either the minimum or the maximum element \ + * Used to find minimum or maximum element in tree. \ + */ \ + void name##_SPLAY_MINMAX(struct name *head, int __comp) { \ + struct type __node, *__left, *__right, *__tmp; \ + \ + SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ + __left = __right = &__node; \ + \ + while (1) { \ + if (__comp < 0) { \ + __tmp = SPLAY_LEFT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if (__comp < 0) { \ + SPLAY_ROTATE_RIGHT(head, __tmp, field); \ + if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ + break; \ + } \ + SPLAY_LINKLEFT(head, __right, field); \ + } else if (__comp > 0) { \ + __tmp = SPLAY_RIGHT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if (__comp > 0) { \ + SPLAY_ROTATE_LEFT(head, __tmp, field); \ + if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ + break; \ + } \ + SPLAY_LINKRIGHT(head, __left, field); \ + } \ + } \ + SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ + } + +#define SPLAY_NEGINF -1 +#define SPLAY_INF 1 + +#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) +#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) +#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) +#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) +#define SPLAY_MIN(name, x) \ + (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) +#define SPLAY_MAX(name, x) \ + (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) + +#define SPLAY_FOREACH(x, name, head) \ + for ((x) = SPLAY_MIN(name, head); (x) != NULL; \ + (x) = SPLAY_NEXT(name, head, x)) + +/* Macros that define a red-black tree */ +#define RB_HEAD(name, type) \ + struct name { \ + struct type *rbh_root; /* root of the tree */ \ + } + +#define RB_INITIALIZER(root) \ + { NULL } + +#define RB_INIT(root) \ + do { \ + (root)->rbh_root = NULL; \ + } while (/*CONSTCOND*/ 0) + +#define RB_BLACK 0 +#define RB_RED 1 +#define RB_ENTRY(type) \ + struct { \ + struct type *rbe_left; /* left element */ \ + struct type *rbe_right; /* right element */ \ + struct type *rbe_parent; /* parent element */ \ + int rbe_color; /* node color */ \ + } + +#define RB_LEFT(elm, field) (elm)->field.rbe_left +#define RB_RIGHT(elm, field) (elm)->field.rbe_right +#define RB_PARENT(elm, field) (elm)->field.rbe_parent +#define RB_COLOR(elm, field) (elm)->field.rbe_color +#define RB_ROOT(head) (head)->rbh_root +#define RB_EMPTY(head) (RB_ROOT(head) == NULL) + +#define RB_SET(elm, parent, field) \ + do { \ + RB_PARENT(elm, field) = parent; \ + RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ + RB_COLOR(elm, field) = RB_RED; \ + } while (/*CONSTCOND*/ 0) + +#define RB_SET_BLACKRED(black, red, field) \ + do { \ + RB_COLOR(black, field) = RB_BLACK; \ + RB_COLOR(red, field) = RB_RED; \ + } while (/*CONSTCOND*/ 0) + +#ifndef RB_AUGMENT +#define RB_AUGMENT(x) \ + do { \ + } while (/*CONSTCOND*/ 0) +#endif + +#define RB_ROTATE_LEFT(head, elm, tmp, field) \ + do { \ + (tmp) = RB_RIGHT(elm, field); \ + if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ + RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ + } \ + RB_AUGMENT(elm); \ + if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ + if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ + RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ + else \ + RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ + } else \ + (head)->rbh_root = (tmp); \ + RB_LEFT(tmp, field) = (elm); \ + RB_PARENT(elm, field) = (tmp); \ + RB_AUGMENT(tmp); \ + if ((RB_PARENT(tmp, field))) \ + RB_AUGMENT(RB_PARENT(tmp, field)); \ + } while (/*CONSTCOND*/ 0) + +#define RB_ROTATE_RIGHT(head, elm, tmp, field) \ + do { \ + (tmp) = RB_LEFT(elm, field); \ + if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ + RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ + } \ + RB_AUGMENT(elm); \ + if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ + if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ + RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ + else \ + RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ + } else \ + (head)->rbh_root = (tmp); \ + RB_RIGHT(tmp, field) = (elm); \ + RB_PARENT(elm, field) = (tmp); \ + RB_AUGMENT(tmp); \ + if ((RB_PARENT(tmp, field))) \ + RB_AUGMENT(RB_PARENT(tmp, field)); \ + } while (/*CONSTCOND*/ 0) + +/* Generates prototypes and inline functions */ +#define RB_PROTOTYPE(name, type, field, cmp) \ + RB_PROTOTYPE_INTERNAL(name, type, field, cmp, ) +#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ + RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) +#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ + attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ + attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, \ + struct type *); \ + attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ + attr struct type *name##_RB_INSERT(struct name *, struct type *); \ + attr struct type *name##_RB_FIND(struct name *, struct type *); \ + attr struct type *name##_RB_NFIND(struct name *, struct type *); \ + attr struct type *name##_RB_NEXT(struct type *); \ + attr struct type *name##_RB_PREV(struct type *); \ + attr struct type *name##_RB_MINMAX(struct name *, int); + +/* Main rb operation. + * Moves node close to the key of elm to top + */ +#define RB_GENERATE(name, type, field, cmp) \ + RB_GENERATE_INTERNAL(name, type, field, cmp, ) +#define RB_GENERATE_STATIC(name, type, field, cmp) \ + RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) +#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ + attr void name##_RB_INSERT_COLOR(struct name *head, struct type *elm) { \ + struct type *parent, *gparent, *tmp; \ + while ((parent = RB_PARENT(elm, field)) != NULL && \ + RB_COLOR(parent, field) == RB_RED) { \ + gparent = RB_PARENT(parent, field); \ + if (parent == RB_LEFT(gparent, field)) { \ + tmp = RB_RIGHT(gparent, field); \ + if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ + RB_COLOR(tmp, field) = RB_BLACK; \ + RB_SET_BLACKRED(parent, gparent, field); \ + elm = gparent; \ + continue; \ + } \ + if (RB_RIGHT(parent, field) == elm) { \ + RB_ROTATE_LEFT(head, parent, tmp, field); \ + tmp = parent; \ + parent = elm; \ + elm = tmp; \ + } \ + RB_SET_BLACKRED(parent, gparent, field); \ + RB_ROTATE_RIGHT(head, gparent, tmp, field); \ + } else { \ + tmp = RB_LEFT(gparent, field); \ + if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ + RB_COLOR(tmp, field) = RB_BLACK; \ + RB_SET_BLACKRED(parent, gparent, field); \ + elm = gparent; \ + continue; \ + } \ + if (RB_LEFT(parent, field) == elm) { \ + RB_ROTATE_RIGHT(head, parent, tmp, field); \ + tmp = parent; \ + parent = elm; \ + elm = tmp; \ + } \ + RB_SET_BLACKRED(parent, gparent, field); \ + RB_ROTATE_LEFT(head, gparent, tmp, field); \ + } \ + } \ + RB_COLOR(head->rbh_root, field) = RB_BLACK; \ + } \ + \ + attr void name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, \ + struct type *elm) { \ + struct type *tmp; \ + while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ + elm != RB_ROOT(head)) { \ + if (RB_LEFT(parent, field) == elm) { \ + tmp = RB_RIGHT(parent, field); \ + if (RB_COLOR(tmp, field) == RB_RED) { \ + RB_SET_BLACKRED(tmp, parent, field); \ + RB_ROTATE_LEFT(head, parent, tmp, field); \ + tmp = RB_RIGHT(parent, field); \ + } \ + if ((RB_LEFT(tmp, field) == NULL || \ + RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ + (RB_RIGHT(tmp, field) == NULL || \ + RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ + RB_COLOR(tmp, field) = RB_RED; \ + elm = parent; \ + parent = RB_PARENT(elm, field); \ + } else { \ + if (RB_RIGHT(tmp, field) == NULL || \ + RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) { \ + struct type *oleft; \ + if ((oleft = RB_LEFT(tmp, field)) != NULL) \ + RB_COLOR(oleft, field) = RB_BLACK; \ + RB_COLOR(tmp, field) = RB_RED; \ + RB_ROTATE_RIGHT(head, tmp, oleft, field); \ + tmp = RB_RIGHT(parent, field); \ + } \ + RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ + RB_COLOR(parent, field) = RB_BLACK; \ + if (RB_RIGHT(tmp, field)) \ + RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ + RB_ROTATE_LEFT(head, parent, tmp, field); \ + elm = RB_ROOT(head); \ + break; \ + } \ + } else { \ + tmp = RB_LEFT(parent, field); \ + if (RB_COLOR(tmp, field) == RB_RED) { \ + RB_SET_BLACKRED(tmp, parent, field); \ + RB_ROTATE_RIGHT(head, parent, tmp, field); \ + tmp = RB_LEFT(parent, field); \ + } \ + if ((RB_LEFT(tmp, field) == NULL || \ + RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ + (RB_RIGHT(tmp, field) == NULL || \ + RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ + RB_COLOR(tmp, field) = RB_RED; \ + elm = parent; \ + parent = RB_PARENT(elm, field); \ + } else { \ + if (RB_LEFT(tmp, field) == NULL || \ + RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) { \ + struct type *oright; \ + if ((oright = RB_RIGHT(tmp, field)) != NULL) \ + RB_COLOR(oright, field) = RB_BLACK; \ + RB_COLOR(tmp, field) = RB_RED; \ + RB_ROTATE_LEFT(head, tmp, oright, field); \ + tmp = RB_LEFT(parent, field); \ + } \ + RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ + RB_COLOR(parent, field) = RB_BLACK; \ + if (RB_LEFT(tmp, field)) \ + RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ + RB_ROTATE_RIGHT(head, parent, tmp, field); \ + elm = RB_ROOT(head); \ + break; \ + } \ + } \ + } \ + if (elm) \ + RB_COLOR(elm, field) = RB_BLACK; \ + } \ + \ + attr struct type *name##_RB_REMOVE(struct name *head, struct type *elm) { \ + struct type *child, *parent, *old = elm; \ + int color; \ + if (RB_LEFT(elm, field) == NULL) \ + child = RB_RIGHT(elm, field); \ + else if (RB_RIGHT(elm, field) == NULL) \ + child = RB_LEFT(elm, field); \ + else { \ + struct type *left; \ + elm = RB_RIGHT(elm, field); \ + while ((left = RB_LEFT(elm, field)) != NULL) \ + elm = left; \ + child = RB_RIGHT(elm, field); \ + parent = RB_PARENT(elm, field); \ + color = RB_COLOR(elm, field); \ + if (child) \ + RB_PARENT(child, field) = parent; \ + if (parent) { \ + if (RB_LEFT(parent, field) == elm) \ + RB_LEFT(parent, field) = child; \ + else \ + RB_RIGHT(parent, field) = child; \ + RB_AUGMENT(parent); \ + } else \ + RB_ROOT(head) = child; \ + if (RB_PARENT(elm, field) == old) \ + parent = elm; \ + (elm)->field = (old)->field; \ + if (RB_PARENT(old, field)) { \ + if (RB_LEFT(RB_PARENT(old, field), field) == old) \ + RB_LEFT(RB_PARENT(old, field), field) = elm; \ + else \ + RB_RIGHT(RB_PARENT(old, field), field) = elm; \ + RB_AUGMENT(RB_PARENT(old, field)); \ + } else \ + RB_ROOT(head) = elm; \ + RB_PARENT(RB_LEFT(old, field), field) = elm; \ + if (RB_RIGHT(old, field)) \ + RB_PARENT(RB_RIGHT(old, field), field) = elm; \ + if (parent) { \ + left = parent; \ + do { \ + RB_AUGMENT(left); \ + } while ((left = RB_PARENT(left, field)) != NULL); \ + } \ + goto color; \ + } \ + parent = RB_PARENT(elm, field); \ + color = RB_COLOR(elm, field); \ + if (child) \ + RB_PARENT(child, field) = parent; \ + if (parent) { \ + if (RB_LEFT(parent, field) == elm) \ + RB_LEFT(parent, field) = child; \ + else \ + RB_RIGHT(parent, field) = child; \ + RB_AUGMENT(parent); \ + } else \ + RB_ROOT(head) = child; \ + color: \ + if (color == RB_BLACK) \ + name##_RB_REMOVE_COLOR(head, parent, child); \ + return (old); \ + } \ + \ + /* Inserts a node into the RB tree */ \ + attr struct type *name##_RB_INSERT(struct name *head, struct type *elm) { \ + struct type *tmp; \ + struct type *parent = NULL; \ + int comp = 0; \ + tmp = RB_ROOT(head); \ + while (tmp) { \ + parent = tmp; \ + comp = (cmp)(elm, parent); \ + if (comp < 0) \ + tmp = RB_LEFT(tmp, field); \ + else if (comp > 0) \ + tmp = RB_RIGHT(tmp, field); \ + else \ + return (tmp); \ + } \ + RB_SET(elm, parent, field); \ + if (parent != NULL) { \ + if (comp < 0) \ + RB_LEFT(parent, field) = elm; \ + else \ + RB_RIGHT(parent, field) = elm; \ + RB_AUGMENT(parent); \ + } else \ + RB_ROOT(head) = elm; \ + name##_RB_INSERT_COLOR(head, elm); \ + return (NULL); \ + } \ + \ + /* Finds the node with the same key as elm */ \ + attr struct type *name##_RB_FIND(struct name *head, struct type *elm) { \ + struct type *tmp = RB_ROOT(head); \ + int comp; \ + while (tmp) { \ + comp = cmp(elm, tmp); \ + if (comp < 0) \ + tmp = RB_LEFT(tmp, field); \ + else if (comp > 0) \ + tmp = RB_RIGHT(tmp, field); \ + else \ + return (tmp); \ + } \ + return (NULL); \ + } \ + \ + /* Finds the first node greater than or equal to the search key */ \ + attr struct type *name##_RB_NFIND(struct name *head, struct type *elm) { \ + struct type *tmp = RB_ROOT(head); \ + struct type *res = NULL; \ + int comp; \ + while (tmp) { \ + comp = cmp(elm, tmp); \ + if (comp < 0) { \ + res = tmp; \ + tmp = RB_LEFT(tmp, field); \ + } else if (comp > 0) \ + tmp = RB_RIGHT(tmp, field); \ + else \ + return (tmp); \ + } \ + return (res); \ + } \ + \ + /* ARGSUSED */ \ + attr struct type *name##_RB_NEXT(struct type *elm) { \ + if (RB_RIGHT(elm, field)) { \ + elm = RB_RIGHT(elm, field); \ + while (RB_LEFT(elm, field)) \ + elm = RB_LEFT(elm, field); \ + } else { \ + if (RB_PARENT(elm, field) && \ + (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ + elm = RB_PARENT(elm, field); \ + else { \ + while (RB_PARENT(elm, field) && \ + (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ + elm = RB_PARENT(elm, field); \ + elm = RB_PARENT(elm, field); \ + } \ + } \ + return (elm); \ + } \ + \ + /* ARGSUSED */ \ + attr struct type *name##_RB_PREV(struct type *elm) { \ + if (RB_LEFT(elm, field)) { \ + elm = RB_LEFT(elm, field); \ + while (RB_RIGHT(elm, field)) \ + elm = RB_RIGHT(elm, field); \ + } else { \ + if (RB_PARENT(elm, field) && \ + (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ + elm = RB_PARENT(elm, field); \ + else { \ + while (RB_PARENT(elm, field) && \ + (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ + elm = RB_PARENT(elm, field); \ + elm = RB_PARENT(elm, field); \ + } \ + } \ + return (elm); \ + } \ + \ + attr struct type *name##_RB_MINMAX(struct name *head, int val) { \ + struct type *tmp = RB_ROOT(head); \ + struct type *parent = NULL; \ + while (tmp) { \ + parent = tmp; \ + if (val < 0) \ + tmp = RB_LEFT(tmp, field); \ + else \ + tmp = RB_RIGHT(tmp, field); \ + } \ + return (parent); \ + } + +#define RB_NEGINF -1 +#define RB_INF 1 + +#define RB_INSERT(name, x, y) CONCAT(name, _RB_INSERT(x, y)) +#define RB_REMOVE(name, x, y) CONCAT(name, _RB_REMOVE(x, y)) +#define RB_FIND(name, x, y) CONCAT(name, _RB_FIND(x, y)) +#define RB_NFIND(name, x, y) CONCAT(name, _RB_NFIND(x, y)) +#define RB_NEXT(name, x, y) CONCAT(name, _RB_NEXT(y)) +#define RB_PREV(name, x, y) CONCAT(name, _RB_PREV(y)) +#define RB_MIN(name, x) CONCAT(name, _RB_MINMAX(x, RB_NEGINF)) +#define RB_MAX(name, x) CONCAT(name, _RB_MINMAX(x, RB_INF)) + +#define RB_FOREACH(x, name, head) \ + for ((x) = RB_MIN(name, head); (x) != NULL; (x) = name##_RB_NEXT(x)) + +#define RB_FOREACH_FROM(x, name, y) \ + for ((x) = (y); ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ + (x) = (y)) + +#define RB_FOREACH_SAFE(x, name, head, y) \ + for ((x) = RB_MIN(name, head); \ + ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); (x) = (y)) + +#define RB_FOREACH_REVERSE(x, name, head) \ + for ((x) = RB_MAX(name, head); (x) != NULL; (x) = name##_RB_PREV(x)) + +#define RB_FOREACH_REVERSE_FROM(x, name, y) \ + for ((x) = (y); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ + (x) = (y)) + +#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ + for ((x) = RB_MAX(name, head); \ + ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); (x) = (y)) + +#endif /* !_TREE_H_ */ @@ -0,0 +1,239 @@ +#include "shell.h" + +typedef struct proc { + pid_t pid; /* process identifier */ + int state; /* RUNNING or STOPPED or FINISHED */ + int exitcode; /* -1 if exit status not yet received */ +} proc_t; + +typedef struct job { + pid_t pgid; /* 0 if slot is free */ + proc_t *proc; /* array of processes running in as a job */ + struct termios tmodes; /* saved terminal modes */ + int nproc; /* number of processes */ + int state; /* changes when live processes have same state */ + char *command; /* textual representation of command line */ +} job_t; + +static job_t *jobs = NULL; /* array of all jobs */ +static int njobmax = 1; /* number of slots in jobs array */ +static int tty_fd = -1; /* controlling terminal file descriptor */ +static struct termios shell_tmodes; /* saved shell terminal modes */ + +static void sigchld_handler(int sig) { + int old_errno = errno; + pid_t pid; + int status; + /* TODO: Change state (FINISHED, RUNNING, STOPPED) of processes and jobs. + * Bury all children that finished saving their status in jobs. */ +#ifdef STUDENT + (void)status; + (void)pid; +#endif /* !STUDENT */ + errno = old_errno; +} + +/* When pipeline is done, its exitcode is fetched from the last process. */ +static int exitcode(job_t *job) { + return job->proc[job->nproc - 1].exitcode; +} + +static int allocjob(void) { + /* Find empty slot for background job. */ + for (int j = BG; j < njobmax; j++) + if (jobs[j].pgid == 0) + return j; + + /* If none found, allocate new one. */ + jobs = realloc(jobs, sizeof(job_t) * (njobmax + 1)); + memset(&jobs[njobmax], 0, sizeof(job_t)); + return njobmax++; +} + +static int allocproc(int j) { + job_t *job = &jobs[j]; + job->proc = realloc(job->proc, sizeof(proc_t) * (job->nproc + 1)); + return job->nproc++; +} + +int addjob(pid_t pgid, int bg) { + int j = bg ? allocjob() : FG; + job_t *job = &jobs[j]; + /* Initial state of a job. */ + job->pgid = pgid; + job->state = RUNNING; + job->command = NULL; + job->proc = NULL; + job->nproc = 0; + job->tmodes = shell_tmodes; + return j; +} + +static void deljob(job_t *job) { + assert(job->state == FINISHED); + free(job->command); + free(job->proc); + job->pgid = 0; + job->command = NULL; + job->proc = NULL; + job->nproc = 0; +} + +static void movejob(int from, int to) { + assert(jobs[to].pgid == 0); + memcpy(&jobs[to], &jobs[from], sizeof(job_t)); + memset(&jobs[from], 0, sizeof(job_t)); +} + +static void mkcommand(char **cmdp, char **argv) { + if (*cmdp) + strapp(cmdp, " | "); + + for (strapp(cmdp, *argv++); *argv; argv++) { + strapp(cmdp, " "); + strapp(cmdp, *argv); + } +} + +void addproc(int j, pid_t pid, char **argv) { + assert(j < njobmax); + job_t *job = &jobs[j]; + + int p = allocproc(j); + proc_t *proc = &job->proc[p]; + /* Initial state of a process. */ + proc->pid = pid; + proc->state = RUNNING; + proc->exitcode = -1; + mkcommand(&job->command, argv); +} + +/* Returns job's state. + * If it's finished, delete it and return exitcode through statusp. */ +static int jobstate(int j, int *statusp) { + assert(j < njobmax); + job_t *job = &jobs[j]; + int state = job->state; + + /* TODO: Handle case where job has finished. */ +#ifdef STUDENT + (void)exitcode; +#endif /* !STUDENT */ + + return state; +} + +char *jobcmd(int j) { + assert(j < njobmax); + job_t *job = &jobs[j]; + return job->command; +} + +/* Continues a job that has been stopped. If move to foreground was requested, + * then move the job to foreground and start monitoring it. */ +bool resumejob(int j, int bg, sigset_t *mask) { + if (j < 0) { + for (j = njobmax - 1; j > 0 && jobs[j].state == FINISHED; j--) + continue; + } + + if (j >= njobmax || jobs[j].state == FINISHED) + return false; + + /* TODO: Continue stopped job. Possibly move job to foreground slot. */ +#ifdef STUDENT + (void)movejob; +#endif /* !STUDENT */ + + return true; +} + +/* Kill the job by sending it a SIGTERM. */ +bool killjob(int j) { + if (j >= njobmax || jobs[j].state == FINISHED) + return false; + debug("[%d] killing '%s'\n", j, jobs[j].command); + + /* TODO: I love the smell of napalm in the morning. */ +#ifdef STUDENT +#endif /* !STUDENT */ + + return true; +} + +/* Report state of requested background jobs. Clean up finished jobs. */ +void watchjobs(int which) { + for (int j = BG; j < njobmax; j++) { + if (jobs[j].pgid == 0) + continue; + + /* TODO: Report job number, state, command and exit code or signal. */ +#ifdef STUDENT + (void)deljob; +#endif /* !STUDENT */ + } +} + +/* Monitor job execution. If it gets stopped move it to background. + * When a job has finished or has been stopped move shell to foreground. */ +int monitorjob(sigset_t *mask) { + int exitcode = 0, state; + + /* TODO: Following code requires use of Tcsetpgrp of tty_fd. */ +#ifdef STUDENT + (void)jobstate; + (void)exitcode; + (void)state; +#endif /* !STUDENT */ + + return exitcode; +} + +/* Called just at the beginning of shell's life. */ +void initjobs(void) { + struct sigaction act = { + .sa_flags = SA_RESTART, + .sa_handler = sigchld_handler, + }; + + /* Block SIGINT for the duration of `sigchld_handler` + * in case `sigint_handler` does something crazy like `longjmp`. */ + sigemptyset(&act.sa_mask); + sigaddset(&act.sa_mask, SIGINT); + Sigaction(SIGCHLD, &act, NULL); + + jobs = calloc(sizeof(job_t), 1); + + /* Assume we're running in interactive mode, so move us to foreground. + * Duplicate terminal fd, but do not leak it to subprocesses that execve. */ + assert(isatty(STDIN_FILENO)); + tty_fd = Dup(STDIN_FILENO); + fcntl(tty_fd, F_SETFD, FD_CLOEXEC); + + /* Take control of the terminal. */ + Tcsetpgrp(tty_fd, getpgrp()); + + /* Save default terminal attributes for the shell. */ + Tcgetattr(tty_fd, &shell_tmodes); +} + +/* Called just before the shell finishes. */ +void shutdownjobs(void) { + sigset_t mask; + Sigprocmask(SIG_BLOCK, &sigchld_mask, &mask); + + /* TODO: Kill remaining jobs and wait for them to finish. */ +#ifdef STUDENT +#endif /* !STUDENT */ + + watchjobs(FINISHED); + + Sigprocmask(SIG_SETMASK, &mask, NULL); + + Close(tty_fd); +} + +/* Sets foreground process group to `pgid`. */ +void setfgpgrp(pid_t pgid) { + Tcsetpgrp(tty_fd, pgid); +} @@ -0,0 +1,76 @@ +#include "shell.h" + +void strapp(char **dstp, const char *src) { + assert(dstp != NULL); + + if (*dstp == NULL) { + *dstp = strdup(src); + } else { + size_t s = strlen(*dstp) + strlen(src) + 1; + *dstp = realloc(*dstp, s); + strcat(*dstp, src); + } +} + +token_t *tokenize(char *s, int *tokc_p) { + int capacity = 10; + int ntoks = 0; + + token_t *tokvec = malloc(sizeof(token_t) * (capacity + 1)); + + while (*s != 0) { + /* Consume whitespace characters. */ + if (isspace(*s)) { + *s++ = 0; + continue; + } + + /* Make sure there's enough space to add new token. */ + if (ntoks == capacity) { + capacity *= 2; + tokvec = realloc(tokvec, sizeof(token_t) * (capacity + 1)); + } + + size_t l = strcspn(s, " |&<>;!"); + if (l > 0) { + tokvec[ntoks++] = s; + s += l; + continue; + } + + token_t tok; + + if (s[0] == '|') { + if (s[1] == '|') { + *s++ = 0; + tok = T_OR; + } else { + tok = T_PIPE; + } + } else if (s[0] == '&') { + if (s[1] == '&') { + *s++ = 0; + tok = T_AND; + } else { + tok = T_BGJOB; + } + } else if (s[0] == '<') { + tok = T_INPUT; + } else if (s[0] == '>') { + tok = T_OUTPUT; + } else if (s[0] == ';') { + tok = T_COLON; + } else if (s[0] == '!') { + tok = T_BANG; + } else { + continue; + } + + *s++ = 0; + tokvec[ntoks++] = tok; + } + + tokvec[ntoks] = NULL; + *tokc_p = ntoks; + return tokvec; +} diff --git a/libcsapp/Accept.c b/libcsapp/Accept.c new file mode 100644 index 0000000..b200b6a --- /dev/null +++ b/libcsapp/Accept.c @@ -0,0 +1,8 @@ +#include "csapp.h" + +int Accept(int s, struct sockaddr *addr, socklen_t *addrlen) { + int rc = accept(s, addr, addrlen); + if (rc < 0) + unix_error("Accept error"); + return rc; +} diff --git a/libcsapp/Bind.c b/libcsapp/Bind.c new file mode 100644 index 0000000..dcc4603 --- /dev/null +++ b/libcsapp/Bind.c @@ -0,0 +1,7 @@ +#include "csapp.h" + +void Bind(int sockfd, struct sockaddr *my_addr, int addrlen) { + int rc = bind(sockfd, my_addr, addrlen); + if (rc < 0) + unix_error("Bind error"); +} diff --git a/libcsapp/Close.c b/libcsapp/Close.c new file mode 100644 index 0000000..eb71723 --- /dev/null +++ b/libcsapp/Close.c @@ -0,0 +1,7 @@ +#include "csapp.h" + +void Close(int fd) { + int rc = close(fd); + if (rc < 0) + unix_error("Close error"); +} diff --git a/libcsapp/Connect.c b/libcsapp/Connect.c new file mode 100644 index 0000000..c701d41 --- /dev/null +++ b/libcsapp/Connect.c @@ -0,0 +1,7 @@ +#include "csapp.h" + +void Connect(int sockfd, struct sockaddr *serv_addr, int addrlen) { + int rc = connect(sockfd, serv_addr, addrlen); + if (rc < 0) + unix_error("Connect error"); +} diff --git a/libcsapp/Dup.c b/libcsapp/Dup.c new file mode 100644 index 0000000..81bd8b6 --- /dev/null +++ b/libcsapp/Dup.c @@ -0,0 +1,8 @@ +#include "csapp.h" + +int Dup(int fd) { + int rc = dup(fd); + if (rc < 0) + unix_error("Dup error"); + return rc; +} diff --git a/libcsapp/Dup2.c b/libcsapp/Dup2.c new file mode 100644 index 0000000..a0018fa --- /dev/null +++ b/libcsapp/Dup2.c @@ -0,0 +1,8 @@ +#include "csapp.h" + +int Dup2(int oldfd, int newfd) { + int rc = dup2(oldfd, newfd); + if (rc < 0) + unix_error("Dup2 error"); + return rc; +} diff --git a/libcsapp/Fork.c b/libcsapp/Fork.c new file mode 100644 index 0000000..e8f7f06 --- /dev/null +++ b/libcsapp/Fork.c @@ -0,0 +1,17 @@ +#include "csapp.h" + +static unsigned int seed = 0xdeadc0de; + +pid_t Fork(void) { + pid_t pid; + if ((pid = fork()) < 0) + unix_error("Fork error"); + /* + * Scheduler is not good enough at radomizing time of return from fork(). + * Let's help it by adding some extra random delay in one of parent or child. + */ + seed += getpid(); + if (seed & 1) + usleep(rand_r(&seed) % 10000); + return pid; +} diff --git a/libcsapp/Fstat.c b/libcsapp/Fstat.c new file mode 100644 index 0000000..9c31b2b --- /dev/null +++ b/libcsapp/Fstat.c @@ -0,0 +1,6 @@ +#include "csapp.h" + +void Fstat(int fd, struct stat *statbuf) { + if (fstat(fd, statbuf) < 0) + unix_error("Fstat error"); +} diff --git a/libcsapp/Fstatat.c b/libcsapp/Fstatat.c new file mode 100644 index 0000000..e2cf45f --- /dev/null +++ b/libcsapp/Fstatat.c @@ -0,0 +1,6 @@ +#include "csapp.h" + +void Fstatat(int dirfd, const char *pathname, struct stat *statbuf, int flags) { + if (fstatat(dirfd, pathname, statbuf, flags) < 0) + unix_error("Fstatat error"); +} diff --git a/libcsapp/Ftruncate.c b/libcsapp/Ftruncate.c new file mode 100644 index 0000000..8ad52f1 --- /dev/null +++ b/libcsapp/Ftruncate.c @@ -0,0 +1,6 @@ +#include "csapp.h" + +void Ftruncate(int fd, off_t length) { + if (ftruncate(fd, length) < 0) + unix_error("Ftruncate error"); +} diff --git a/libcsapp/Getaddrinfo.c b/libcsapp/Getaddrinfo.c new file mode 100644 index 0000000..94671df --- /dev/null +++ b/libcsapp/Getaddrinfo.c @@ -0,0 +1,9 @@ +#include "csapp.h" + +void Getaddrinfo(const char *node, const char *service, + const struct addrinfo *hints, struct addrinfo **res) { + int rc = getaddrinfo(node, service, hints, res); + + if (rc != 0) + gai_error(rc, "Getaddrinfo error"); +} diff --git a/libcsapp/Getcwd.c b/libcsapp/Getcwd.c new file mode 100644 index 0000000..c8a680a --- /dev/null +++ b/libcsapp/Getcwd.c @@ -0,0 +1,8 @@ +#include "csapp.h" + +char *Getcwd(char *buf, size_t buflen) { + char *res = getcwd(buf, buflen); + if (res == NULL) + unix_error("Getcwd failed"); + return res; +} diff --git a/libcsapp/Getdents.c b/libcsapp/Getdents.c new file mode 100644 index 0000000..67f72b0 --- /dev/null +++ b/libcsapp/Getdents.c @@ -0,0 +1,12 @@ +#include "csapp.h" + +#ifdef LINUX +#include <asm/unistd.h> + +int Getdents(int fd, struct linux_dirent *dirp, unsigned count) { + int rc = syscall(__NR_getdents, fd, dirp, count); + if (rc < 0) + unix_error("Getdents error"); + return rc; +} +#endif diff --git a/libcsapp/Getnameinfo.c b/libcsapp/Getnameinfo.c new file mode 100644 index 0000000..3b77ce1 --- /dev/null +++ b/libcsapp/Getnameinfo.c @@ -0,0 +1,9 @@ +#include "csapp.h" + +void Getnameinfo(const struct sockaddr *sa, socklen_t salen, char *host, + size_t hostlen, char *serv, size_t servlen, int flags) { + int rc = getnameinfo(sa, salen, host, hostlen, serv, servlen, flags); + + if (rc != 0) + gai_error(rc, "Getnameinfo error"); +} diff --git a/libcsapp/Kill.c b/libcsapp/Kill.c new file mode 100644 index 0000000..ae347bd --- /dev/null +++ b/libcsapp/Kill.c @@ -0,0 +1,6 @@ +#include "csapp.h" + +void Kill(pid_t pid, int sig) { + if (kill(pid, sig) < 0) + unix_error("Kill error"); +} diff --git a/libcsapp/Listen.c b/libcsapp/Listen.c new file mode 100644 index 0000000..28d1371 --- /dev/null +++ b/libcsapp/Listen.c @@ -0,0 +1,7 @@ +#include "csapp.h" + +void Listen(int s, int backlog) { + int rc = listen(s, backlog); + if (rc < 0) + unix_error("Listen error"); +} diff --git a/libcsapp/Lseek.c b/libcsapp/Lseek.c new file mode 100644 index 0000000..a56321a --- /dev/null +++ b/libcsapp/Lseek.c @@ -0,0 +1,8 @@ +#include "csapp.h" + +off_t Lseek(int fildes, off_t offset, int whence) { + off_t rc = lseek(fildes, offset, whence); + if (rc < 0) + unix_error("Lseek error"); + return rc; +} diff --git a/libcsapp/Madvise.c b/libcsapp/Madvise.c new file mode 100644 index 0000000..0e420d1 --- /dev/null +++ b/libcsapp/Madvise.c @@ -0,0 +1,6 @@ +#include "csapp.h" + +void Madvise(void *addr, size_t length, int advice) { + if (madvise(addr, length, advice) < 0) + unix_error("Madvise error"); +} diff --git a/libcsapp/Mmap.c b/libcsapp/Mmap.c new file mode 100644 index 0000000..310f26c --- /dev/null +++ b/libcsapp/Mmap.c @@ -0,0 +1,9 @@ +#include "csapp.h" + +void *Mmap(void *addr, size_t length, int prot, int flags, int fd, + off_t offset) { + void *ptr = mmap(addr, length, prot, flags, fd, offset); + if (ptr == MAP_FAILED) + unix_error("Mmap error"); + return ptr; +} diff --git a/libcsapp/Mprotect.c b/libcsapp/Mprotect.c new file mode 100644 index 0000000..3991567 --- /dev/null +++ b/libcsapp/Mprotect.c @@ -0,0 +1,6 @@ +#include "csapp.h" + +void Mprotect(void *addr, size_t length, int prot) { + if (mprotect(addr, length, prot) < 0) + unix_error("Mprotect error"); +} diff --git a/libcsapp/Munmap.c b/libcsapp/Munmap.c new file mode 100644 index 0000000..f1669f9 --- /dev/null +++ b/libcsapp/Munmap.c @@ -0,0 +1,6 @@ +#include "csapp.h" + +void Munmap(void *addr, size_t len) { + if (munmap(addr, len) < 0) + unix_error("Munmap error"); +} diff --git a/libcsapp/Open.c b/libcsapp/Open.c new file mode 100644 index 0000000..568e2aa --- /dev/null +++ b/libcsapp/Open.c @@ -0,0 +1,8 @@ +#include "csapp.h" + +int Open(const char *pathname, int flags, mode_t mode) { + int rc = open(pathname, flags, mode); + if (rc < 0) + unix_error("Open error"); + return rc; +} diff --git a/libcsapp/Pipe.c b/libcsapp/Pipe.c new file mode 100644 index 0000000..757fb1f --- /dev/null +++ b/libcsapp/Pipe.c @@ -0,0 +1,6 @@ +#include "csapp.h" + +void Pipe(int fds[2]) { + if (pipe(fds) < 0) + unix_error("Pipe error"); +} diff --git a/libcsapp/Poll.c b/libcsapp/Poll.c new file mode 100644 index 0000000..de431e9 --- /dev/null +++ b/libcsapp/Poll.c @@ -0,0 +1,10 @@ +#include "csapp.h" + +int Poll(struct pollfd *fds, nfds_t nfds, int timeout) { + int rc = poll(fds, nfds, timeout); + if (rc == -1 && errno == EINTR) + rc = 0; + if (rc < 0) + unix_error("Poll error"); + return rc; +} diff --git a/libcsapp/Prctl.c b/libcsapp/Prctl.c new file mode 100644 index 0000000..560bd8a --- /dev/null +++ b/libcsapp/Prctl.c @@ -0,0 +1,8 @@ +#include "csapp.h" + +#ifdef LINUX +void Prctl(int option, long arg) { + if (prctl(option, arg) < 0) + unix_error("Prctl error"); +} +#endif diff --git a/libcsapp/Read.c b/libcsapp/Read.c new file mode 100644 index 0000000..06f22b9 --- /dev/null +++ b/libcsapp/Read.c @@ -0,0 +1,8 @@ +#include "csapp.h" + +size_t Read(int fd, void *buf, size_t count) { + ssize_t rc = read(fd, buf, count); + if (rc < 0) + unix_error("Read error"); + return rc; +} diff --git a/libcsapp/Readlink.c b/libcsapp/Readlink.c new file mode 100644 index 0000000..c5cf63a --- /dev/null +++ b/libcsapp/Readlink.c @@ -0,0 +1,8 @@ +#include "csapp.h" + +size_t Readlink(const char *pathname, char *buf, size_t bufsiz) { + int rc = readlink(pathname, buf, bufsiz); + if (rc < 0) + unix_error("Readlink error"); + return rc; +} diff --git a/libcsapp/Readlinkat.c b/libcsapp/Readlinkat.c new file mode 100644 index 0000000..c80bf50 --- /dev/null +++ b/libcsapp/Readlinkat.c @@ -0,0 +1,8 @@ +#include "csapp.h" + +size_t Readlinkat(int dirfd, const char *pathname, char *buf, size_t bufsiz) { + ssize_t rc = readlinkat(dirfd, pathname, buf, bufsiz); + if (rc < 0) + unix_error("Readlinkat error"); + return rc; +} diff --git a/libcsapp/Rename.c b/libcsapp/Rename.c new file mode 100644 index 0000000..a41e915 --- /dev/null +++ b/libcsapp/Rename.c @@ -0,0 +1,6 @@ +#include "csapp.h" + +void Rename(const char *oldpath, const char *newpath) { + if (rename(oldpath, newpath) < 0) + unix_error("Rename error"); +} diff --git a/libcsapp/Select.c b/libcsapp/Select.c new file mode 100644 index 0000000..92a1003 --- /dev/null +++ b/libcsapp/Select.c @@ -0,0 +1,9 @@ +#include "csapp.h" + +int Select(int n, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, + struct timeval *timeout) { + int rc = select(n, readfds, writefds, exceptfds, timeout); + if (rc < 0) + unix_error("Select error"); + return rc; +} diff --git a/libcsapp/Setjmp.s b/libcsapp/Setjmp.s new file mode 100644 index 0000000..c50a649 --- /dev/null +++ b/libcsapp/Setjmp.s @@ -0,0 +1,45 @@ +_JB_RBX = 0 +_JB_RBP = 1 +_JB_R12 = 2 +_JB_R13 = 3 +_JB_R14 = 4 +_JB_R15 = 5 +_JB_RSP = 6 +_JB_RIP = 7 + + .text + + .globl Setjmp + .type Setjmp,@function +Setjmp: + movq (%rsp),%r11 + movq %rbx,(_JB_RBX * 8)(%rdi) + movq %rbp,(_JB_RBP * 8)(%rdi) + movq %r12,(_JB_R12 * 8)(%rdi) + movq %r13,(_JB_R13 * 8)(%rdi) + movq %r14,(_JB_R14 * 8)(%rdi) + movq %r15,(_JB_R15 * 8)(%rdi) + movq %rsp,(_JB_RSP * 8)(%rdi) + movq %r11,(_JB_RIP * 8)(%rdi) + xorl %eax,%eax + ret + .size Setjmp, . - Setjmp + + .globl Longjmp + .type Longjmp,@function +Longjmp: + movq (_JB_RBX * 8)(%rdi),%rbx + movq (_JB_RBP * 8)(%rdi),%rbp + movq (_JB_R12 * 8)(%rdi),%r12 + movq (_JB_R13 * 8)(%rdi),%r13 + movq (_JB_R14 * 8)(%rdi),%r14 + movq (_JB_R15 * 8)(%rdi),%r15 + movq (_JB_RSP * 8)(%rdi),%rsp + movq (_JB_RIP * 8)(%rdi),%r11 + movl %esi,%eax + testl %eax,%eax + jnz 1f + incl %eax +1: movq %r11,(%rsp) + ret + .size Longjmp, . - Longjmp diff --git a/libcsapp/Setpgid.c b/libcsapp/Setpgid.c new file mode 100644 index 0000000..e128965 --- /dev/null +++ b/libcsapp/Setpgid.c @@ -0,0 +1,6 @@ +#include "csapp.h" + +void Setpgid(pid_t pid, pid_t pgid) { + if (setpgid(pid, pgid) < 0) + unix_error("Setpgid error"); +} diff --git a/libcsapp/Setsockopt.c b/libcsapp/Setsockopt.c new file mode 100644 index 0000000..3d395bf --- /dev/null +++ b/libcsapp/Setsockopt.c @@ -0,0 +1,7 @@ +#include "csapp.h" + +void Setsockopt(int s, int level, int optname, const void *optval, int optlen) { + int rc = setsockopt(s, level, optname, optval, optlen); + if (rc < 0) + unix_error("Setsockopt error"); +} diff --git a/libcsapp/Sigaction.c b/libcsapp/Sigaction.c new file mode 100644 index 0000000..46616f5 --- /dev/null +++ b/libcsapp/Sigaction.c @@ -0,0 +1,7 @@ +#include <csapp.h> + +void Sigaction(int signum, const struct sigaction *act, + struct sigaction *oldact) { + if (sigaction(signum, act, oldact) < 0) + unix_error("Sigaction error"); +} diff --git a/libcsapp/Signal.c b/libcsapp/Signal.c new file mode 100644 index 0000000..052f1af --- /dev/null +++ b/libcsapp/Signal.c @@ -0,0 +1,8 @@ +#include "csapp.h" + +void (*Signal(int signum, void (*handler)(int)))(int) { + void (*res)(int) = signal(signum, handler); + if (res == SIG_ERR) + unix_error("Signal error"); + return res; +} diff --git a/libcsapp/Sigprocmask.c b/libcsapp/Sigprocmask.c new file mode 100644 index 0000000..7c5c3b1 --- /dev/null +++ b/libcsapp/Sigprocmask.c @@ -0,0 +1,6 @@ +#include "csapp.h" + +void Sigprocmask(int how, const sigset_t *set, sigset_t *oldset) { + if (sigprocmask(how, set, oldset) < 0) + unix_error("Sigprocmask error"); +} diff --git a/libcsapp/Sigsuspend.c b/libcsapp/Sigsuspend.c new file mode 100644 index 0000000..372e108 --- /dev/null +++ b/libcsapp/Sigsuspend.c @@ -0,0 +1,7 @@ +#include "csapp.h" + +void Sigsuspend(const sigset_t *mask) { + if (sigsuspend(mask) == -1 && errno == EINTR) + return; + unix_error("Sigsuspend error"); +} diff --git a/libcsapp/Socket.c b/libcsapp/Socket.c new file mode 100644 index 0000000..e0fbfb3 --- /dev/null +++ b/libcsapp/Socket.c @@ -0,0 +1,8 @@ +#include "csapp.h" + +int Socket(int domain, int type, int protocol) { + int rc = socket(domain, type, protocol); + if (rc < 0) + unix_error("Socket error"); + return rc; +} diff --git a/libcsapp/Socketpair.c b/libcsapp/Socketpair.c new file mode 100644 index 0000000..d7231d5 --- /dev/null +++ b/libcsapp/Socketpair.c @@ -0,0 +1,6 @@ +#include "csapp.h" + +void Socketpair(int domain, int type, int protocol, int sv[2]) { + if (socketpair(domain, type, protocol, sv) < 0) + unix_error("Socketpair error"); +} diff --git a/libcsapp/Tcgetattr.c b/libcsapp/Tcgetattr.c new file mode 100644 index 0000000..37a172c --- /dev/null +++ b/libcsapp/Tcgetattr.c @@ -0,0 +1,6 @@ +#include "csapp.h" + +void Tcgetattr(int fd, struct termios *termios_p) { + if (tcgetattr(fd, termios_p) < 0) + unix_error("Tcgetattr error"); +} diff --git a/libcsapp/Tcgetpgrp.c b/libcsapp/Tcgetpgrp.c new file mode 100644 index 0000000..47317b3 --- /dev/null +++ b/libcsapp/Tcgetpgrp.c @@ -0,0 +1,8 @@ +#include "csapp.h" + +pid_t Tcgetpgrp(int fd) { + int rc = tcgetpgrp(fd); + if (rc < 0) + unix_error("Tcgetpgrp error"); + return rc; +} diff --git a/libcsapp/Tcsetattr.c b/libcsapp/Tcsetattr.c new file mode 100644 index 0000000..1b9692d --- /dev/null +++ b/libcsapp/Tcsetattr.c @@ -0,0 +1,6 @@ +#include "csapp.h" + +void Tcsetattr(int fd, int action, const struct termios *termios_p) { + if (tcsetattr(fd, action, termios_p) < 0) + unix_error("Tcsetattr error"); +} diff --git a/libcsapp/Tcsetpgrp.c b/libcsapp/Tcsetpgrp.c new file mode 100644 index 0000000..8f7ef57 --- /dev/null +++ b/libcsapp/Tcsetpgrp.c @@ -0,0 +1,7 @@ +#include "csapp.h" + +void Tcsetpgrp(int fd, pid_t pgrp) { + int rc = tcsetpgrp(fd, pgrp); + if (rc < 0) + unix_error("Tcsetpgrp error"); +} diff --git a/libcsapp/Unlink.c b/libcsapp/Unlink.c new file mode 100644 index 0000000..35d6735 --- /dev/null +++ b/libcsapp/Unlink.c @@ -0,0 +1,6 @@ +#include "csapp.h" + +void Unlink(const char *pathname) { + if (unlink(pathname) < 0) + unix_error("Unlink error"); +} diff --git a/libcsapp/Waitpid.c b/libcsapp/Waitpid.c new file mode 100644 index 0000000..4ec5678 --- /dev/null +++ b/libcsapp/Waitpid.c @@ -0,0 +1,8 @@ +#include "csapp.h" + +pid_t Waitpid(pid_t pid, int *iptr, int options) { + pid_t retpid; + if ((retpid = waitpid(pid, iptr, options)) < 0) + unix_error("Waitpid error"); + return retpid; +} diff --git a/libcsapp/Write.c b/libcsapp/Write.c new file mode 100644 index 0000000..e778eaf --- /dev/null +++ b/libcsapp/Write.c @@ -0,0 +1,8 @@ +#include "csapp.h" + +size_t Write(int fd, const void *buf, size_t count) { + ssize_t rc = write(fd, buf, count); + if (rc < 0) + unix_error("Write error"); + return rc; +} diff --git a/libcsapp/Writev.c b/libcsapp/Writev.c new file mode 100644 index 0000000..8f25041 --- /dev/null +++ b/libcsapp/Writev.c @@ -0,0 +1,8 @@ +#include "csapp.h" + +size_t Writev(int fd, const struct iovec *iov, int iovcnt) { + ssize_t rc = writev(fd, iov, iovcnt); + if (rc < 0) + unix_error("Writev error"); + return rc; +} diff --git a/libcsapp/app_error.c b/libcsapp/app_error.c new file mode 100644 index 0000000..6a6358e --- /dev/null +++ b/libcsapp/app_error.c @@ -0,0 +1,11 @@ +#include <stdarg.h> +#include "csapp.h" + +noreturn void app_error(const char *fmt, ...) { + va_list ap; + va_start(ap, fmt); + vfprintf(stderr, fmt, ap); + fputc('\n', stderr); + va_end(ap); + exit(EXIT_FAILURE); +} diff --git a/libcsapp/gai_error.c b/libcsapp/gai_error.c new file mode 100644 index 0000000..6a6ab27 --- /dev/null +++ b/libcsapp/gai_error.c @@ -0,0 +1,11 @@ +#include <stdarg.h> +#include "csapp.h" + +noreturn void gai_error(int code, const char *fmt, ...) { + va_list ap; + va_start(ap, fmt); + vfprintf(stderr, fmt, ap); + fprintf(stderr, ": %s\n", gai_strerror(code)); + va_end(ap); + exit(EXIT_FAILURE); +} diff --git a/libcsapp/jenkins_hash.c b/libcsapp/jenkins_hash.c new file mode 100644 index 0000000..8eae9b2 --- /dev/null +++ b/libcsapp/jenkins_hash.c @@ -0,0 +1,587 @@ +#include "csapp.h" + +/* +------------------------------------------------------------------------------- +lookup3.c, by Bob Jenkins, May 2006, Public Domain. + +These are functions for producing 32-bit hashes for hash table lookup. +hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() +are externally useful functions. Routines to test the hash are included +if SELF_TEST is defined. You can use this free for any purpose. It's in +the public domain. It has no warranty. + +You probably want to use hashlittle(). hashlittle() and hashbig() +hash byte arrays. hashlittle() is faster than hashbig() on +little-endian machines. Intel and AMD are little-endian machines. +On second thought, you probably want hashlittle2(), which is identical to +hashlittle() except it returns two 32-bit hashes for the price of one. +You could implement hashbig2() if you wanted but I haven't bothered here. + +If you want to find a hash of, say, exactly 7 integers, do + a = i1; b = i2; c = i3; + mix(a,b,c); + a += i4; b += i5; c += i6; + mix(a,b,c); + a += i7; + final(a,b,c); +then use c as the hash value. If you have a variable length array of +4-byte integers to hash, use hashword(). If you have a byte array (like +a character string), use hashlittle(). If you have several byte arrays, or +a mix of things, see the comments above hashlittle(). + +Why is this so big? I read 12 bytes at a time into 3 4-byte integers, +then mix those integers. This is fast (you can do a lot more thorough +mixing with 12*3 instructions on 3 integers than you can with 3 instructions +on 1 byte), but shoehorning those bytes into integers efficiently is messy. +------------------------------------------------------------------------------- +*/ + +#define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k)))) + +/* +------------------------------------------------------------------------------- +mix -- mix 3 32-bit values reversibly. + +This is reversible, so any information in (a,b,c) before mix() is +still in (a,b,c) after mix(). + +If four pairs of (a,b,c) inputs are run through mix(), or through +mix() in reverse, there are at least 32 bits of the output that +are sometimes the same for one pair and different for another pair. +This was tested for: +* pairs that differed by one bit, by two bits, in any combination + of top bits of (a,b,c), or in any combination of bottom bits of + (a,b,c). +* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed + the output delta to a Gray code (a^(a>>1)) so a string of 1's (as + is commonly produced by subtraction) look like a single 1-bit + difference. +* the base values were pseudorandom, all zero but one bit set, or + all zero plus a counter that starts at zero. + +Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that +satisfy this are + 4 6 8 16 19 4 + 9 15 3 18 27 15 + 14 9 3 7 17 3 +Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing +for "differ" defined as + with a one-bit base and a two-bit delta. I +used http://burtleburtle.net/bob/hash/avalanche.html to choose +the operations, constants, and arrangements of the variables. + +This does not achieve avalanche. There are input bits of (a,b,c) +that fail to affect some output bits of (a,b,c), especially of a. The +most thoroughly mixed value is c, but it doesn't really even achieve +avalanche in c. + +This allows some parallelism. Read-after-writes are good at doubling +the number of bits affected, so the goal of mixing pulls in the opposite +direction as the goal of parallelism. I did what I could. Rotates +seem to cost as much as shifts on every machine I could lay my hands +on, and rotates are much kinder to the top and bottom bits, so I used +rotates. +------------------------------------------------------------------------------- +*/ +#define mix(a, b, c) \ + { \ + a -= c; \ + a ^= rot(c, 4); \ + c += b; \ + b -= a; \ + b ^= rot(a, 6); \ + a += c; \ + c -= b; \ + c ^= rot(b, 8); \ + b += a; \ + a -= c; \ + a ^= rot(c, 16); \ + c += b; \ + b -= a; \ + b ^= rot(a, 19); \ + a += c; \ + c -= b; \ + c ^= rot(b, 4); \ + b += a; \ + } + +/* +------------------------------------------------------------------------------- +final -- final mixing of 3 32-bit values (a,b,c) into c + +Pairs of (a,b,c) values differing in only a few bits will usually +produce values of c that look totally different. This was tested for +* pairs that differed by one bit, by two bits, in any combination + of top bits of (a,b,c), or in any combination of bottom bits of + (a,b,c). +* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed + the output delta to a Gray code (a^(a>>1)) so a string of 1's (as + is commonly produced by subtraction) look like a single 1-bit + difference. +* the base values were pseudorandom, all zero but one bit set, or + all zero plus a counter that starts at zero. + +These constants passed: + 14 11 25 16 4 14 24 + 12 14 25 16 4 14 24 +and these came close: + 4 8 15 26 3 22 24 + 10 8 15 26 3 22 24 + 11 8 15 26 3 22 24 +------------------------------------------------------------------------------- +*/ +#define final(a, b, c) \ + { \ + c ^= b; \ + c -= rot(b, 14); \ + a ^= c; \ + a -= rot(c, 11); \ + b ^= a; \ + b -= rot(a, 25); \ + c ^= b; \ + c -= rot(b, 16); \ + a ^= c; \ + a -= rot(c, 4); \ + b ^= a; \ + b -= rot(a, 14); \ + c ^= b; \ + c -= rot(b, 24); \ + } + +/* +-------------------------------------------------------------------- + This works on all machines. To be useful, it requires + -- that the key be an array of uint32_t's, and + -- that the length be the number of uint32_t's in the key + + The function hashword() is identical to hashlittle() on little-endian + machines, and identical to hashbig() on big-endian machines, + except that the length has to be measured in uint32_ts rather than in + bytes. hashlittle() is more complicated than hashword() only because + hashlittle() has to dance around fitting the key bytes into registers. +-------------------------------------------------------------------- +*/ +uint32_t +jenkins_hash32(const uint32_t *k, /* the key, an array of uint32_t values */ + size_t length, /* the length of the key, in uint32_ts */ + uint32_t initval) /* the previous hash, or an arbitrary value */ +{ + uint32_t a, b, c; + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + (((uint32_t)length) << 2) + initval; + + /*------------------------------------------------- handle most of the key */ + while (length > 3) { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a, b, c); + length -= 3; + k += 3; + } + + /*------------------------------------------- handle the last 3 uint32_t's */ + switch (length) /* all the case statements fall through */ + { + case 3: + c += k[2]; + case 2: + b += k[1]; + case 1: + a += k[0]; + final(a, b, c); + case 0: /* case 0: nothing left to add */ + break; + } + /*------------------------------------------------------ report the result */ + return c; +} + +#if BYTE_ORDER == LITTLE_ENDIAN +/* +------------------------------------------------------------------------------- +hashlittle() -- hash a variable-length key into a 32-bit value + k : the key (the unaligned variable-length array of bytes) + length : the length of the key, counting by bytes + initval : can be any 4-byte value +Returns a 32-bit value. Every bit of the key affects every bit of +the return value. Two keys differing by one or two bits will have +totally different hash values. + +The best hash table sizes are powers of 2. There is no need to do +mod a prime (mod is sooo slow!). If you need less than 32 bits, +use a bitmask. For example, if you need only 10 bits, do + h = (h & hashmask(10)); +In which case, the hash table should have hashsize(10) elements. + +If you are hashing n strings (uint8_t **)k, do it like this: + for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h); + +By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this +code any way you wish, private, educational, or commercial. It's free. + +Use for hash table lookup, or anything where one collision in 2^^32 is +acceptable. Do NOT use for cryptographic purposes. +------------------------------------------------------------------------------- +*/ + +uint32_t jenkins_hash(const void *key, size_t length, uint32_t initval) { + uint32_t a, b, c; /* internal state */ + union { + const void *ptr; + size_t i; + } u; /* needed for Mac Powerbook G4 */ + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; + + u.ptr = key; + if ((u.i & 0x3) == 0) { + const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ + + /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ + while (length > 12) { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a, b, c); + length -= 12; + k += 3; + } + + /*----------------------------- handle the last (probably partial) block */ + /* + * "k[2]&0xffffff" actually reads beyond the end of the string, but + * then masks off the part it's not allowed to read. Because the + * string is aligned, the masked-off tail is in the same word as the + * rest of the string. Every machine with memory protection I've seen + * does it on word boundaries, so is OK with this. But VALGRIND will + * still catch it and complain. The masking trick does make the hash + * noticably faster for short strings (like English words). + */ + + switch (length) { + case 12: + c += k[2]; + b += k[1]; + a += k[0]; + break; + case 11: + c += k[2] & 0xffffff; + b += k[1]; + a += k[0]; + break; + case 10: + c += k[2] & 0xffff; + b += k[1]; + a += k[0]; + break; + case 9: + c += k[2] & 0xff; + b += k[1]; + a += k[0]; + break; + case 8: + b += k[1]; + a += k[0]; + break; + case 7: + b += k[1] & 0xffffff; + a += k[0]; + break; + case 6: + b += k[1] & 0xffff; + a += k[0]; + break; + case 5: + b += k[1] & 0xff; + a += k[0]; + break; + case 4: + a += k[0]; + break; + case 3: + a += k[0] & 0xffffff; + break; + case 2: + a += k[0] & 0xffff; + break; + case 1: + a += k[0] & 0xff; + break; + case 0: + return c; /* zero length strings require no mixing */ + } + + } else if ((u.i & 0x1) == 0) { + const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ + const uint8_t *k8; + + /*--------------- all but last block: aligned reads and different mixing */ + while (length > 12) { + a += k[0] + (((uint32_t)k[1]) << 16); + b += k[2] + (((uint32_t)k[3]) << 16); + c += k[4] + (((uint32_t)k[5]) << 16); + mix(a, b, c); + length -= 12; + k += 6; + } + + /*----------------------------- handle the last (probably partial) block */ + k8 = (const uint8_t *)k; + switch (length) { + case 12: + c += k[4] + (((uint32_t)k[5]) << 16); + b += k[2] + (((uint32_t)k[3]) << 16); + a += k[0] + (((uint32_t)k[1]) << 16); + break; + case 11: + c += ((uint32_t)k8[10]) << 16; /* fall through */ + case 10: + c += k[4]; + b += k[2] + (((uint32_t)k[3]) << 16); + a += k[0] + (((uint32_t)k[1]) << 16); + break; + case 9: + c += k8[8]; /* fall through */ + case 8: + b += k[2] + (((uint32_t)k[3]) << 16); + a += k[0] + (((uint32_t)k[1]) << 16); + break; + case 7: + b += ((uint32_t)k8[6]) << 16; /* fall through */ + case 6: + b += k[2]; + a += k[0] + (((uint32_t)k[1]) << 16); + break; + case 5: + b += k8[4]; /* fall through */ + case 4: + a += k[0] + (((uint32_t)k[1]) << 16); + break; + case 3: + a += ((uint32_t)k8[2]) << 16; /* fall through */ + case 2: + a += k[0]; + break; + case 1: + a += k8[0]; + break; + case 0: + return c; /* zero length requires no mixing */ + } + + } else { /* need to read the key one byte at a time */ + const uint8_t *k = (const uint8_t *)key; + + /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ + while (length > 12) { + a += k[0]; + a += ((uint32_t)k[1]) << 8; + a += ((uint32_t)k[2]) << 16; + a += ((uint32_t)k[3]) << 24; + b += k[4]; + b += ((uint32_t)k[5]) << 8; + b += ((uint32_t)k[6]) << 16; + b += ((uint32_t)k[7]) << 24; + c += k[8]; + c += ((uint32_t)k[9]) << 8; + c += ((uint32_t)k[10]) << 16; + c += ((uint32_t)k[11]) << 24; + mix(a, b, c); + length -= 12; + k += 12; + } + + /*-------------------------------- last block: affect all 32 bits of (c) */ + switch (length) /* all the case statements fall through */ + { + case 12: + c += ((uint32_t)k[11]) << 24; + case 11: + c += ((uint32_t)k[10]) << 16; + case 10: + c += ((uint32_t)k[9]) << 8; + case 9: + c += k[8]; + case 8: + b += ((uint32_t)k[7]) << 24; + case 7: + b += ((uint32_t)k[6]) << 16; + case 6: + b += ((uint32_t)k[5]) << 8; + case 5: + b += k[4]; + case 4: + a += ((uint32_t)k[3]) << 24; + case 3: + a += ((uint32_t)k[2]) << 16; + case 2: + a += ((uint32_t)k[1]) << 8; + case 1: + a += k[0]; + break; + case 0: + return c; + } + } + + final(a, b, c); + return c; +} + +#else /* !(BYTE_ORDER == LITTLE_ENDIAN) */ + +/* + * hashbig(): + * This is the same as hashword() on big-endian machines. It is different + * from hashlittle() on all machines. hashbig() takes advantage of + * big-endian byte ordering. + */ +uint32_t jenkins_hash(const void *key, size_t length, uint32_t initval) { + uint32_t a, b, c; + union { + const void *ptr; + size_t i; + } u; /* to cast key to (size_t) happily */ + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; + + u.ptr = key; + if ((u.i & 0x3) == 0) { + const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ + + /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ + while (length > 12) { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a, b, c); + length -= 12; + k += 3; + } + + /*----------------------------- handle the last (probably partial) block */ + /* + * "k[2]<<8" actually reads beyond the end of the string, but + * then shifts out the part it's not allowed to read. Because the + * string is aligned, the illegal read is in the same word as the + * rest of the string. Every machine with memory protection I've seen + * does it on word boundaries, so is OK with this. But VALGRIND will + * still catch it and complain. The masking trick does make the hash + * noticably faster for short strings (like English words). + */ + + switch (length) { + case 12: + c += k[2]; + b += k[1]; + a += k[0]; + break; + case 11: + c += k[2] & 0xffffff00; + b += k[1]; + a += k[0]; + break; + case 10: + c += k[2] & 0xffff0000; + b += k[1]; + a += k[0]; + break; + case 9: + c += k[2] & 0xff000000; + b += k[1]; + a += k[0]; + break; + case 8: + b += k[1]; + a += k[0]; + break; + case 7: + b += k[1] & 0xffffff00; + a += k[0]; + break; + case 6: + b += k[1] & 0xffff0000; + a += k[0]; + break; + case 5: + b += k[1] & 0xff000000; + a += k[0]; + break; + case 4: + a += k[0]; + break; + case 3: + a += k[0] & 0xffffff00; + break; + case 2: + a += k[0] & 0xffff0000; + break; + case 1: + a += k[0] & 0xff000000; + break; + case 0: + return c; /* zero length strings require no mixing */ + } + + } else { /* need to read the key one byte at a time */ + const uint8_t *k = (const uint8_t *)key; + + /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ + while (length > 12) { + a += ((uint32_t)k[0]) << 24; + a += ((uint32_t)k[1]) << 16; + a += ((uint32_t)k[2]) << 8; + a += ((uint32_t)k[3]); + b += ((uint32_t)k[4]) << 24; + b += ((uint32_t)k[5]) << 16; + b += ((uint32_t)k[6]) << 8; + b += ((uint32_t)k[7]); + c += ((uint32_t)k[8]) << 24; + c += ((uint32_t)k[9]) << 16; + c += ((uint32_t)k[10]) << 8; + c += ((uint32_t)k[11]); + mix(a, b, c); + length -= 12; + k += 12; + } + + /*-------------------------------- last block: affect all 32 bits of (c) */ + switch (length) /* all the case statements fall through */ + { + case 12: + c += k[11]; + case 11: + c += ((uint32_t)k[10]) << 8; + case 10: + c += ((uint32_t)k[9]) << 16; + case 9: + c += ((uint32_t)k[8]) << 24; + case 8: + b += k[7]; + case 7: + b += ((uint32_t)k[6]) << 8; + case 6: + b += ((uint32_t)k[5]) << 16; + case 5: + b += ((uint32_t)k[4]) << 24; + case 4: + a += k[3]; + case 3: + a += ((uint32_t)k[2]) << 8; + case 2: + a += ((uint32_t)k[1]) << 16; + case 1: + a += ((uint32_t)k[0]) << 24; + break; + case 0: + return c; + } + } + + final(a, b, c); + return c; +} +#endif diff --git a/libcsapp/memory.c b/libcsapp/memory.c new file mode 100644 index 0000000..8852b66 --- /dev/null +++ b/libcsapp/memory.c @@ -0,0 +1,22 @@ +#include "csapp.h" + +void *Malloc(size_t size) { + void *p = malloc(size); + if (!p) + unix_error("Malloc error"); + return p; +} + +void *Realloc(void *ptr, size_t size) { + void *p = realloc(ptr, size); + if (!p) + unix_error("Realloc error"); + return p; +} + +void *Calloc(size_t nmemb, size_t size) { + void *p = calloc(nmemb, size); + if (!p) + unix_error("Calloc error"); + return p; +} diff --git a/libcsapp/open_clientfd.c b/libcsapp/open_clientfd.c new file mode 100644 index 0000000..615af47 --- /dev/null +++ b/libcsapp/open_clientfd.c @@ -0,0 +1,57 @@ +#include "csapp.h" + +/* + * open_clientfd - Open connection to server at <hostname, port> and + * return a socket descriptor ready for reading and writing. This + * function is reentrant and protocol-independent. + * + * On error, returns: + * -2 for getaddrinfo error + * -1 with errno set for other errors. + */ + +int open_clientfd(char *hostname, char *port) { + int clientfd, rc; + struct addrinfo hints, *listp, *p; + + /* Get a list of potential server addresses */ + memset(&hints, 0, sizeof(struct addrinfo)); + hints.ai_socktype = SOCK_STREAM; /* Open a connection */ + hints.ai_flags = AI_NUMERICSERV; /* ... using a numeric port arg. */ + hints.ai_flags |= AI_ADDRCONFIG; /* Recommended for connections */ + if ((rc = getaddrinfo(hostname, port, &hints, &listp)) != 0) { + fprintf(stderr, "getaddrinfo failed (%s:%s): %s\n", hostname, port, + gai_strerror(rc)); + return -2; + } + + /* Walk the list for one that we can successfully connect to */ + for (p = listp; p; p = p->ai_next) { + /* Create a socket descriptor */ + if ((clientfd = socket(p->ai_family, p->ai_socktype, p->ai_protocol)) < 0) + continue; /* Socket failed, try the next */ + + /* Connect to the server */ + if (connect(clientfd, p->ai_addr, p->ai_addrlen) != -1) + break; /* Success */ + if (close(clientfd) < + 0) { /* Connect failed, try another */ // line:netp:openclientfd:closefd + fprintf(stderr, "open_clientfd: close failed: %s\n", strerror(errno)); + return -1; + } + } + + /* Clean up */ + freeaddrinfo(listp); + if (!p) /* All connects failed */ + return -1; + /* The last connect succeeded */ + return clientfd; +} + +int Open_clientfd(char *hostname, char *port) { + int rc = open_clientfd(hostname, port); + if (rc < 0) + unix_error("Open_clientfd error"); + return rc; +} diff --git a/libcsapp/open_listenfd.c b/libcsapp/open_listenfd.c new file mode 100644 index 0000000..4f381bf --- /dev/null +++ b/libcsapp/open_listenfd.c @@ -0,0 +1,65 @@ +#include "csapp.h" + +/* + * open_listenfd - Open and return a listening socket on port. This + * function is reentrant and protocol-independent. + * + * On error, returns: + * -2 for getaddrinfo error + * -1 with errno set for other errors. + */ + +int open_listenfd(char *port, int backlog) { + struct addrinfo hints, *listp, *p; + int listenfd, rc, optval = 1; + + /* Get a list of potential server addresses */ + memset(&hints, 0, sizeof(struct addrinfo)); + hints.ai_socktype = SOCK_STREAM; /* Accept connections */ + hints.ai_flags = AI_PASSIVE | AI_ADDRCONFIG; /* ... on any IP address */ + hints.ai_flags |= AI_NUMERICSERV; /* ... using port number */ + if ((rc = getaddrinfo(NULL, port, &hints, &listp)) != 0) { + fprintf(stderr, "getaddrinfo failed (port %s): %s\n", port, + gai_strerror(rc)); + return -2; + } + + /* Walk the list for one that we can bind to */ + for (p = listp; p; p = p->ai_next) { + /* Create a socket descriptor */ + if ((listenfd = socket(p->ai_family, p->ai_socktype, p->ai_protocol)) < 0) + continue; /* Socket failed, try the next */ + + /* Eliminates "Address already in use" error from bind */ + setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, // line:netp:csapp:setsockopt + (const void *)&optval, sizeof(int)); + + /* Bind the descriptor to the address */ + if (bind(listenfd, p->ai_addr, p->ai_addrlen) == 0) + break; /* Success */ + if (close(listenfd) < 0) { /* Bind failed, try the next */ + fprintf(stderr, "open_listenfd close failed: %s\n", strerror(errno)); + return -1; + } + } + + /* Clean up */ + freeaddrinfo(listp); + if (!p) /* No address worked */ + return -1; + + /* Make it a listening socket ready to accept connection requests */ + if (listen(listenfd, backlog) < 0) { + close(listenfd); + return -1; + } + return listenfd; +} + +int Open_listenfd(char *port, int backlog) { + int rc = open_listenfd(port, backlog); + + if (rc < 0) + unix_error("Open_listenfd error"); + return rc; +} diff --git a/libcsapp/posix_cond.c b/libcsapp/posix_cond.c new file mode 100644 index 0000000..f697272 --- /dev/null +++ b/libcsapp/posix_cond.c @@ -0,0 +1,26 @@ +#include "csapp.h" + +void Pthread_cond_init(pthread_cond_t *cond, pthread_condattr_t *cond_attr) { + if (pthread_cond_init(cond, cond_attr)) + unix_error("Pthread_cond_init"); +} + +void Pthread_cond_destroy(pthread_cond_t *cond) { + if (pthread_cond_destroy(cond)) + unix_error("Pthread_cond_destroy"); +} + +void Pthread_cond_signal(pthread_cond_t *cond) { + if (pthread_cond_signal(cond)) + unix_error("Pthread_cond_signal"); +} + +void Pthread_cond_broadcast(pthread_cond_t *cond) { + if (pthread_cond_broadcast(cond)) + unix_error("Pthread_cond_broadcast"); +} + +void Pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex) { + if (pthread_cond_wait(cond, mutex)) + unix_error("Pthread_cond_wait"); +} diff --git a/libcsapp/posix_error.c b/libcsapp/posix_error.c new file mode 100644 index 0000000..e5ad88e --- /dev/null +++ b/libcsapp/posix_error.c @@ -0,0 +1,11 @@ +#include <stdarg.h> +#include "csapp.h" + +void posix_error(int code, const char *fmt, ...) { + va_list ap; + va_start(ap, fmt); + vfprintf(stderr, fmt, ap); + fprintf(stderr, ": %s\n", strerror(code)); + va_end(ap); + exit(EXIT_FAILURE); +} diff --git a/libcsapp/posix_mutex.c b/libcsapp/posix_mutex.c new file mode 100644 index 0000000..9c34e9a --- /dev/null +++ b/libcsapp/posix_mutex.c @@ -0,0 +1,22 @@ +#include "csapp.h" + +void Pthread_mutex_init(pthread_mutex_t *mutex, + const pthread_mutexattr_t *mutexattr) { + if (pthread_mutex_init(mutex, mutexattr)) + unix_error("Pthread_mutex_init"); +} + +void Pthread_mutex_destroy(pthread_mutex_t *mutex) { + if (pthread_mutex_destroy(mutex)) + unix_error("Pthread_mutex_destroy"); +} + +void Pthread_mutex_lock(pthread_mutex_t *mutex) { + if (pthread_mutex_lock(mutex)) + unix_error("Pthread_mutex_lock"); +} + +void Pthread_mutex_unlock(pthread_mutex_t *mutex) { + if (pthread_mutex_unlock(mutex)) + unix_error("Pthread_mutex_unlock"); +} diff --git a/libcsapp/posix_rwlock.c b/libcsapp/posix_rwlock.c new file mode 100644 index 0000000..47ab603 --- /dev/null +++ b/libcsapp/posix_rwlock.c @@ -0,0 +1,27 @@ +#include "csapp.h" + +void Pthread_rwlock_init(pthread_rwlock_t *rwlock, + const pthread_rwlockattr_t *rwlockattr) { + if (pthread_rwlock_init(rwlock, rwlockattr)) + unix_error("Pthread_rwlock_init"); +} + +void Pthread_rwlock_destroy(pthread_rwlock_t *rwlock) { + if (pthread_rwlock_destroy(rwlock)) + unix_error("Pthread_rwlock_destroy"); +} + +void Pthread_rwlock_rdlock(pthread_rwlock_t *rwlock) { + if (pthread_rwlock_rdlock(rwlock)) + unix_error("Pthread_rwlock_rdlock"); +} + +void Pthread_rwlock_wrlock(pthread_rwlock_t *rwlock) { + if (pthread_rwlock_wrlock(rwlock)) + unix_error("Pthread_rwlock_wrlock"); +} + +void Pthread_rwlock_unlock(pthread_rwlock_t *rwlock) { + if (pthread_rwlock_unlock(rwlock)) + unix_error("Pthread_rwlock_unlock"); +} diff --git a/libcsapp/posix_sem.c b/libcsapp/posix_sem.c new file mode 100644 index 0000000..8653397 --- /dev/null +++ b/libcsapp/posix_sem.c @@ -0,0 +1,26 @@ +#include "csapp.h" + +void Sem_init(sem_t *sem, int pshared, unsigned value) { + if (sem_init(sem, pshared, value)) + unix_error("sem_init"); +} + +void Sem_destroy(sem_t *sem) { + if (sem_destroy(sem)) + unix_error("sem_destroy"); +} + +void Sem_wait(sem_t *sem) { + if (sem_wait(sem)) + unix_error("sem_wait"); +} + +void Sem_getvalue(sem_t *sem, int *sval) { + if (sem_getvalue(sem, sval)) + unix_error("sem_getvalue"); +} + +void Sem_post(sem_t *sem) { + if (sem_post(sem)) + unix_error("sem_post"); +} diff --git a/libcsapp/posix_thread.c b/libcsapp/posix_thread.c new file mode 100644 index 0000000..15164bd --- /dev/null +++ b/libcsapp/posix_thread.c @@ -0,0 +1,30 @@ +/************************************************ + * Wrappers for Pthreads thread control functions + ************************************************/ + +#include "csapp.h" + +void Pthread_create(pthread_t *tidp, pthread_attr_t *attrp, + void *(*routine)(void *), void *argp) { + int rc = pthread_create(tidp, attrp, routine, argp); + if (rc) + posix_error(rc, "Pthread_create error"); +} + +void Pthread_cancel(pthread_t tid) { + int rc = pthread_cancel(tid); + if (rc) + posix_error(rc, "Pthread_cancel error"); +} + +void Pthread_join(pthread_t tid, void **thread_return) { + int rc = pthread_join(tid, thread_return); + if (rc) + posix_error(rc, "Pthread_join error"); +} + +void Pthread_detach(pthread_t tid) { + int rc = pthread_detach(tid); + if (rc) + posix_error(rc, "Pthread_detach error"); +} diff --git a/libcsapp/rio.c b/libcsapp/rio.c new file mode 100644 index 0000000..6624adb --- /dev/null +++ b/libcsapp/rio.c @@ -0,0 +1,147 @@ +#include "csapp.h" +#include "rio.h" + +/* rio_readn - Robustly read n bytes (unbuffered) */ +ssize_t rio_readn(int fd, void *usrbuf, size_t n) { + size_t nleft = n; + ssize_t nread; + char *bufp = usrbuf; + + while (nleft > 0) { + if ((nread = read(fd, bufp, nleft)) < 0) { + if (errno == EINTR) /* Interrupted by sig handler return */ + nread = 0; /* and call read() again */ + else + return -1; /* errno set by read() */ + } else if (nread == 0) + break; /* EOF */ + nleft -= nread; + bufp += nread; + } + return n - nleft; /* Return >= 0 */ +} + +ssize_t Rio_readn(int fd, void *ptr, size_t nbytes) { + ssize_t n = rio_readn(fd, ptr, nbytes); + if (n < 0) + unix_error("Rio_readn error"); + return n; +} + +/* rio_writen - Robustly write n bytes (unbuffered) */ +ssize_t rio_writen(int fd, const void *usrbuf, size_t n) { + size_t nleft = n; + ssize_t nwritten; + const char *bufp = usrbuf; + + while (nleft > 0) { + if ((nwritten = write(fd, bufp, nleft)) <= 0) { + if (errno == EINTR) /* Interrupted by sig handler return */ + nwritten = 0; /* and call write() again */ + else + return -1; /* errno set by write() */ + } + nleft -= nwritten; + bufp += nwritten; + } + return n; +} + +void Rio_writen(int fd, const void *usrbuf, size_t n) { + if (rio_writen(fd, usrbuf, n) != n) + unix_error("Rio_writen error"); +} + +/* + * rio_read - This is a wrapper for the Unix read() function that + * transfers min(n, rio_cnt) bytes from an internal buffer to a user + * buffer, where n is the number of bytes requested by the user and + * rio_cnt is the number of unread bytes in the internal buffer. On + * entry, rio_read() refills the internal buffer via a call to + * read() if the internal buffer is empty. + */ +static ssize_t rio_read(rio_t *rp, char *usrbuf, size_t n) { + int cnt; + + while (rp->rio_cnt <= 0) { /* Refill if buf is empty */ + rp->rio_cnt = read(rp->rio_fd, rp->rio_buf, sizeof(rp->rio_buf)); + if (rp->rio_cnt < 0) { + if (errno != EINTR) /* Interrupted by sig handler return */ + return -1; + } else if (rp->rio_cnt == 0) /* EOF */ + return 0; + else + rp->rio_bufptr = rp->rio_buf; /* Reset buffer ptr */ + } + + /* Copy min(n, rp->rio_cnt) bytes from internal buf to user buf */ + cnt = n; + if (rp->rio_cnt < n) + cnt = rp->rio_cnt; + memcpy(usrbuf, rp->rio_bufptr, cnt); + rp->rio_bufptr += cnt; + rp->rio_cnt -= cnt; + return cnt; +} + +ssize_t Rio_readnb(rio_t *rp, void *usrbuf, size_t n) { + ssize_t rc = rio_readnb(rp, usrbuf, n); + if (rc < 0) + unix_error("Rio_readnb error"); + return rc; +} + +/* rio_readinitb - Associate a descriptor with a read buffer and reset buffer */ +void rio_readinitb(rio_t *rp, int fd) { + rp->rio_fd = fd; + rp->rio_cnt = 0; + rp->rio_bufptr = rp->rio_buf; +} + +/* rio_readnb - Robustly read n bytes (buffered) */ +ssize_t rio_readnb(rio_t *rp, void *usrbuf, size_t n) { + size_t nleft = n; + ssize_t nread; + char *bufp = usrbuf; + + while (nleft > 0) { + if ((nread = rio_read(rp, bufp, nleft)) < 0) + return -1; /* errno set by read() */ + else if (nread == 0) + break; /* EOF */ + nleft -= nread; + bufp += nread; + } + return (n - nleft); /* return >= 0 */ +} + +/* rio_readlineb - Robustly read a text line (buffered) */ +ssize_t rio_readlineb(rio_t *rp, void *usrbuf, size_t maxlen) { + int n, rc; + char c, *bufp = usrbuf; + + for (n = 1; n < maxlen; n++) { + if ((rc = rio_read(rp, &c, 1)) == 1) { + *bufp++ = c; + if (c == '\n') { + n++; + break; + } + } else if (rc == 0) { + if (n == 1) + return 0; /* EOF, no data read */ + else + break; /* EOF, some data was read */ + } else + return -1; /* Error */ + } + *bufp = 0; + return n - 1; +} + +ssize_t Rio_readlineb(rio_t *rp, void *usrbuf, size_t maxlen) { + ssize_t rc = rio_readlineb(rp, usrbuf, maxlen); + if (rc < 0) + unix_error("Rio_readlineb error"); + return rc; +} diff --git a/libcsapp/safe_printf.c b/libcsapp/safe_printf.c new file mode 100644 index 0000000..ac7af65 --- /dev/null +++ b/libcsapp/safe_printf.c @@ -0,0 +1,135 @@ +#include <stdarg.h> +#include "csapp.h" + +/* This is actually used with radix [2..36] */ +static char const digits[] = "0123456789abcdefghijklmnopqrstuvwxyz"; + +#define MAXNBUF (sizeof(intmax_t) * 8 + 1) +#define LINELEN 512 + +static char *print_num(char *nbuf, uintmax_t num, int base, int *len_p) { + char *p = nbuf; + + *p = '\0'; + do { + *++p = digits[num % base]; + } while (num /= base); + + *len_p = p - nbuf; + return p; +} + +static int safe_vprintf(int fd, const char *fmt, va_list ap) { + char line[LINELEN]; + char nbuf[MAXNBUF]; + int linelen = 0; + int stop = 0; + +#define PCHAR(c) \ + { \ + int _c = (c); \ + if (linelen < MAXLINE) \ + line[linelen++] = _c; \ + } + + if (fmt == NULL) + fmt = "(null)\n"; + + for (;;) { + int neg = 0, lflag = 0; + int ch, n, base, sign; + uintmax_t num; + + while ((ch = *fmt++) != '%' || stop) { + if (ch == '\0') + goto print; + PCHAR(ch); + } + + const char *percent = fmt - 1; + char *p; + + again: + switch ((ch = *fmt++)) { + case '%': + PCHAR(ch); + break; + + case 'l': + lflag = 1; + goto again; + + case 'c': + PCHAR(va_arg(ap, int)); + break; + + case 's': + p = va_arg(ap, char *); + if (p == NULL) + p = "(null)"; + n = strlen(p); + while (n--) + PCHAR(*p++); + break; + + case 'd': + base = 10; + sign = 1; + if (lflag) + num = va_arg(ap, long); + else + num = va_arg(ap, int); + goto number; + + case 'x': + base = 16; + sign = 0; + if (lflag) + num = va_arg(ap, unsigned long); + else + num = va_arg(ap, unsigned int); + goto number; + + number: + if (sign && (intmax_t)num < 0) { + neg = 1; + num = -(intmax_t)num; + } + if (neg) + PCHAR('-'); + if (base == 16) { + PCHAR('0'); + PCHAR('x'); + } + p = print_num(nbuf, num, base, &n); + while (n--) + PCHAR(*p--); + break; + + default: + while (percent < fmt) + PCHAR(*percent++); + stop = 1; + break; + } + } +#undef PCHAR + +print: + return write(fd, line, linelen); +} + +void safe_printf(const char *fmt, ...) { + va_list ap; + va_start(ap, fmt); + safe_vprintf(STDERR_FILENO, fmt, ap); + va_end(ap); +} + +void safe_error(const char *fmt, ...) { + va_list ap; + va_start(ap, fmt); + safe_vprintf(STDERR_FILENO, fmt, ap); + va_end(ap); + exit(EXIT_FAILURE); +} diff --git a/libcsapp/stdio.c b/libcsapp/stdio.c new file mode 100644 index 0000000..a34333f --- /dev/null +++ b/libcsapp/stdio.c @@ -0,0 +1,15 @@ +#include "csapp.h" + +char *Fgets(char *ptr, int n, FILE *stream) { + char *rptr; + + if (((rptr = fgets(ptr, n, stream)) == NULL) && ferror(stream)) + app_error("Fgets error"); + + return rptr; +} + +void Fputs(const char *ptr, FILE *stream) { + if (fputs(ptr, stream) == EOF) + unix_error("Fputs error"); +} diff --git a/libcsapp/terminal.c b/libcsapp/terminal.c new file mode 100644 index 0000000..85e7da3 --- /dev/null +++ b/libcsapp/terminal.c @@ -0,0 +1,47 @@ +#include <termios.h> +#include <sys/ioctl.h> + +#include "csapp.h" +#include "terminal.h" + +int tty_open(void) { + const char *dev = ttyname(STDIN_FILENO); + if (!dev) { + errno = ENOTTY; + unix_error("tty_open error"); + } + return Open(dev, O_RDWR | O_NOCTTY, 0); +} + +void tty_curpos(int fd, int *x, int *y) { + struct termios ts, ots; + + tcgetattr(fd, &ts); + memcpy(&ots, &ts, sizeof(struct termios)); + ts.c_lflag &= ~(ECHO | ICANON | CREAD); + tcsetattr(fd, TCSADRAIN, &ts); + + /* How many characters in the input queue. */ + int m = 0; + /* TODO: Need to figure out some other way to do it on MacOS / FreeBSD. */ +#ifdef LINUX + ioctl(fd, TIOCINQ, &m); +#endif + + /* Read them all. */ + char discarded[m]; + m = Read(fd, discarded, m); + + Write(fd, CPR(), sizeof(CPR())); + char buf[20]; + int n = Read(fd, buf, 19); + buf[n] = '\0'; + + ts.c_lflag |= ICANON; + tcsetattr(fd, TCSADRAIN, &ts); + for (int i = 0; i < m; i++) + ioctl(fd, TIOCSTI, discarded + i); + + tcsetattr(fd, TCSADRAIN, &ots); + sscanf(buf, "\033[%d;%dR", x, y); +} diff --git a/libcsapp/unix_error.c b/libcsapp/unix_error.c new file mode 100644 index 0000000..4925343 --- /dev/null +++ b/libcsapp/unix_error.c @@ -0,0 +1,11 @@ +#include <stdarg.h> +#include "csapp.h" + +void unix_error(const char *fmt, ...) { + va_list ap; + va_start(ap, fmt); + vfprintf(stderr, fmt, ap); + fprintf(stderr, ": %s\n", strerror(errno)); + va_end(ap); + exit(EXIT_FAILURE); +} diff --git a/run-clang-format.sh b/run-clang-format.sh new file mode 100755 index 0000000..4411dba --- /dev/null +++ b/run-clang-format.sh @@ -0,0 +1,20 @@ +#!/bin/sh + +PAGER=cat + +# Use make format to cleanup the copied tree +if ! make format > /dev/null; then + echo "Check if clang-format is installed!" + exit 1 +fi + +# See if there are any changes compared to checked out sources. +if ! git diff --check --exit-code >/dev/null; then + echo "Formatting incorrect for C files!" + echo "Please run 'make format' before committing your changes," + echo "or manually apply the changes listed above." + git diff + exit 1 +fi + +echo "Formatting correct for C files." diff --git a/sh-tests.py b/sh-tests.py new file mode 100755 index 0000000..7b8005b --- /dev/null +++ b/sh-tests.py @@ -0,0 +1,409 @@ +#!/usr/bin/env python3 + +# You MUST NOT modify this file without author's consent. +# Doing so is considered cheating! + +import os +import pexpect +import unittest +import subprocess +import random +import time +import sys +from tempfile import NamedTemporaryFile + + +LOGFILE = 'sh-tests.{}.log'.format(os.getpid()) +LD_PRELOAD = './trace.so' +BADFNS = ['sleep', 'poll', 'select', 'alarm'] + + +class ShellTesterSimple(): + def setUp(self): + test_id = '.'.join(self.id().split('.')[-2:]) + self.child = pexpect.spawn('./shell') + self.child.logfile = open(LOGFILE, 'ab') + self.child.logfile.write(f'>>> Test: "{test_id}"\n'.encode('utf-8')) + self.child.setecho(False) + # self.child.interact() + self.expect('#') + + def tearDown(self): + self.sendline('exit\n') + self.child.logfile.close() + + def lines_before(self): + before = self.child.before.decode('utf-8').split('\r\n') + return [line.strip() for line in before if len(line)] + + def send(self, s): + self.child.send(s) + + def sendline(self, s): + self.child.sendline(s) + + def sendintr(self): + self.child.sendintr() + + def sendcontrol(self, ch): + self.child.sendcontrol(ch) + + def expect(self, s, **kw): + try: + self.child.expect(s, **kw) + except pexpect.exceptions.TIMEOUT: + self.log(f'TEST: expected "{s}"') + raise + + def expect_exact(self, s, **kw): + try: + self.child.expect_exact(s, **kw) + except pexpect.exceptions.TIMEOUT: + self.log(f'TEST: expected "{s}"') + raise + + @property + def pid(self): + return self.child.pid + + def wait(self): + self.child.wait() + + def execute(self, cmd): + """ Captures an output from the command. """ + # There's bug (?) in pexpect that's somewhat difficult to reproduce. + # After the command is issued we read from standard output till + # prompt character. Unexpectedly sometimes the command string + # is getting captured as the first line of output from the command. + self.sendline(cmd) + self.expect('#') + before = self.lines_before() + # XXX: Workaround for issue described above. + if before and cmd in before[0]: + before.pop(0) + return before + + def log(self, msg): + self.child.logfile.write(f'{msg}\n'.encode('utf-8')) + + +class ShellTester(ShellTesterSimple): + def setUp(self): + os.environ['LD_PRELOAD'] = LD_PRELOAD + super().setUp() + + def tearDown(self): + del os.environ['LD_PRELOAD'] + super().tearDown() + + def expect_syscall(self, name, caller=None): + self.expect('\[(\d+):(\d+)\] %s\(([^)]*)\)([^\r]*)\r\n' % name) + + pid, pgrp, args, retval = self.child.match.groups() + pid = int(pid) + pgrp = int(pgrp) + args = args.decode('utf-8') + retval = retval.decode('utf-8') + result = {'pid': pid, 'pgrp': pgrp, 'args': []} + + if args not in ['...', '']: + for arg in args.split(', '): + try: + result['args'].append(int(arg)) + except ValueError: + result['args'].append(arg) + + if caller is not None: + self.assertEqual(caller, pid) + if not retval: + return result + if retval.startswith(' = '): + result['retval'] = int(retval[3:]) + return result + if retval.startswith(' -> '): + items = retval[5:-1].strip() + if not items: + return result + for item in items.split(', '): + k, v = item.split('=', 1) + try: + result[k] = int(v) + except ValueError: + result[k] = v + return result + raise RuntimeError + + def expect_fork(self, parent=None): + return self.expect_syscall('fork', caller=parent) + + def expect_execve(self, child=None): + return self.expect_syscall('execve', caller=child) + + def expect_kill(self, pid=None, signum=None): + while True: + res = self.expect_syscall('kill', caller=self.pid) + if res['args'][0] == pid and res['args'][1] == signum: + break + + def expect_waitpid(self, pid=None, status=None): + while True: + res = self.expect_syscall('waitpid') + if res['pid'] == pid and res.get('status', None) == status: + break + self.assertEqual(status, res.get('status', -1)) + + def expect_spawn(self): + result = self.expect_fork(parent=self.pid) + self.expect_execve(child=result['retval']) + return result + + +class TestShellSimple(ShellTesterSimple, unittest.TestCase): + def test_redir_1(self): + nlines = 587 + inf_name = 'include/queue.h' + + # 'wc -l include/queue.h > out' + with NamedTemporaryFile(mode='r') as outf: + self.execute('wc -l ' + inf_name + ' >' + outf.name) + self.assertEqual(int(outf.read().split()[0]), nlines) + + # 'wc -l < include/queue.h' + lines = self.execute('wc -l < ' + inf_name) + self.assertEqual(lines[0], str(nlines)) + + # 'wc -l < include/queue.h > out' + with NamedTemporaryFile(mode='r') as outf: + self.execute('wc -l < ' + inf_name + ' >' + outf.name) + self.assertEqual(int(outf.read().split()[0]), nlines) + + def test_redir_2(self): + with NamedTemporaryFile(mode='w') as inf: + with NamedTemporaryFile(mode='r') as outf: + n = random.randrange(100, 200) + + for i in range(n): + inf.write('a\n') + inf.flush() + + # 'wc -l < random-text > out' + self.execute('wc -l ' + inf.name + ' >' + outf.name) + self.assertEqual(outf.read().split()[0], str(n)) + + def test_pipeline_1(self): + lines = self.execute('grep LIST include/queue.h | wc -l') + self.assertEqual(lines[0], '46') + + def test_pipeline_2(self): + lines = self.execute( + 'cat include/queue.h | cat | grep LIST | cat | wc -l') + self.assertEqual(lines[0], '46') + + def test_pipeline_3(self): + with NamedTemporaryFile(mode='r') as outf: + self.execute( + 'cat < include/queue.h | grep LIST | wc -l > ' + outf.name) + self.assertEqual(int(outf.read().split()[0]), 46) + + def test_fd_leaks(self): + # 'ls -l /proc/self/fd' + lines = self.execute('ls -l /proc/self/fd') + self.assertEqual(len(lines), 5) + for i in range(3): + self.assertIn('%d -> /dev/pts/' % i, lines[i + 1]) + self.assertIn('3 -> /proc/', lines[4]) + + # 'ls -l /proc/self/fd | cat' + lines = self.execute('ls -l /proc/self/fd | cat') + self.assertEqual(len(lines), 5) + self.assertIn('pipe:', lines[2]) + + # 'true | ls -l /proc/self/fd' + lines = self.execute('true | ls -l /proc/self/fd') + self.assertEqual(len(lines), 5) + self.assertIn('pipe:', lines[1]) + + # 'true | ls -l /proc/self/fd | cat' + lines = self.execute('true | ls -l /proc/self/fd | cat') + self.assertEqual(len(lines), 5) + self.assertIn('pipe:', lines[1]) + self.assertIn('pipe:', lines[2]) + + # check shell 'ls -l /proc/$pid/fd' + lines = self.execute('ls -l /proc/%d/fd' % self.pid) + self.assertEqual(len(lines), 5) + for i in range(4): + self.assertIn('%d -> /dev/pts/' % i, lines[i + 1]) + + def test_exitcode_1(self): + # 'true &' + self.sendline('true &') + self.expect_exact("running 'true'") + self.sendline('jobs') + self.expect_exact("exited 'true', status=0") + + # 'false &' + self.sendline('false &') + self.expect_exact("running 'false'") + self.sendline('jobs') + self.expect_exact("exited 'false', status=1") + + if False: + # 'exit 42 &' + self.sendline('exit 42 &') + self.expect_exact("running 'exit 42'") + self.sendline('jobs') + self.expect_exact("exited 'exit 42', status=42") + + def test_kill_suspended(self): + self.sendline('cat &') + self.expect_exact("running 'cat'") + self.sendline('jobs') + self.expect_exact("suspended 'cat'") + self.sendline('pkill -9 cat') + self.expect_exact("killed 'cat' by signal 9") + + def test_resume_suspended(self): + prog = 'cat' + self.sendline(f'{prog} &') + self.expect_exact(f"running '{prog}'") + self.expect('#') + self.sendline('jobs') + self.expect_exact(f"suspended '{prog}'") + self.sendline('fg') + self.expect_exact(f"continue '{prog}'") + self.sendintr() + self.sendline('jobs') + self.expect('#', searchwindowsize=2) + + def test_kill_jobs(self): + self.sendline('sleep 1000 &') + self.expect_exact("[1] running 'sleep 1000'") + self.sendline('sleep 2000 &') + self.expect_exact("[2] running 'sleep 2000'") + self.sendline('jobs') + self.expect_exact("[1] running 'sleep 1000'") + self.expect_exact("[2] running 'sleep 2000'") + self.sendline('kill %2') + self.sendline('jobs') + self.expect_exact("[1] running 'sleep 1000'") + self.expect_exact("[2] killed 'sleep 2000' by signal 15") + self.sendline('kill %1') + self.sendline('jobs') + self.expect_exact("[1] killed 'sleep 1000' by signal 15") + + def test_kill_at_quit(self): + self.sendline('sleep 1000 &') + self.expect_exact("[1] running 'sleep 1000'") + self.sendline('sleep 2000 &') + self.expect_exact("[2] running 'sleep 2000'") + self.sendline('jobs') + self.expect_exact("[1] running 'sleep 1000'") + self.expect_exact("[2] running 'sleep 2000'") + self.sendcontrol('d') + self.expect_exact("[1] killed 'sleep 1000' by signal 15") + self.expect_exact("[2] killed 'sleep 2000' by signal 15") + + +class TestShellWithSyscalls(ShellTester, unittest.TestCase): + def stty(self): + with NamedTemporaryFile(mode='r') as sttyf: + self.execute('stty -a') + return sttyf.read() + + def test_quit(self): + self.sendline('quit') + self.wait() + + def test_sigint(self): + self.sendline('cat') + child = self.expect_spawn()['retval'] + self.sendintr() + self.expect_waitpid(pid=child, status='SIGINT') + self.expect('#') + + def test_sigtstp(self): + self.sendline('cat') + child = self.expect_spawn()['retval'] + self.sendcontrol('z') + self.expect_waitpid(pid=child, status='SIGTSTP') + self.sendline('fg 1') + self.expect_waitpid(pid=child, status='SIGCONT') + self.sendcontrol('d') + self.expect('#') + + def test_terminate_tstped(self): + self.sendline('cat') + child = self.expect_spawn()['retval'] + self.sendcontrol('z') + self.expect_waitpid(pid=child, status='SIGTSTP') + self.sendline('kill %1') + self.expect_kill(pid=-child, signum='SIGCONT') + self.expect_waitpid(pid=child, status='SIGTERM') + self.sendline('jobs') + self.expect_exact("[1] killed 'cat' by signal 15") + + def test_terminate_ttined(self): + self.sendline('cat &') + child = self.expect_spawn()['retval'] + self.expect_waitpid(pid=child, status='SIGTTIN') + self.sendline('kill %1') + self.expect_kill(pid=-child, signum='SIGCONT') + self.expect_waitpid(pid=child, status='SIGTERM') + self.sendline('jobs') + self.expect_exact("[1] killed 'cat' by signal 15") + + def test_termattr_1(self): + stty_before = self.stty() + self.sendline('more shell.c') + child = self.expect_spawn()['retval'] + self.send('q') + self.expect_waitpid(pid=child, status=0) + self.expect('#') + stty_after = self.stty() + self.assertEqual(stty_before, stty_after) + + def test_termattr_2(self): + prog = 'more shell.c' + stty_before = self.stty() + self.sendline(prog) + child = self.expect_spawn()['retval'] + self.expect('--More--') + self.sendcontrol('z') + self.expect_waitpid(pid=child, status='SIGSTOP') + self.sendline('kill %1') + self.expect_waitpid(pid=child, status='SIGTERM') + self.sendline('jobs') + self.expect_exact(f"[1] killed '{prog}' by signal 15") + stty_after = self.stty() + self.assertEqual(stty_before, stty_after) + + +if __name__ == '__main__': + os.environ['PATH'] = '/usr/bin:/bin' + os.environ['LC_ALL'] = 'C' + + ldd = subprocess.run(['ldd', 'shell'], stdout=subprocess.PIPE) + for line in ldd.stdout.decode('utf-8').splitlines(): + if 'libasan' in line: + LD_PRELOAD = line.split()[2] + ':' + LD_PRELOAD + + # Fail loudly if a call to function that can provide sleep functionality + # is used. We don't want it to be used for synchronization purposes. + nm = subprocess.run(['nm', '-u', 'shell.o', 'jobs.o', 'command.o'], + stdout=subprocess.PIPE) + for line in nm.stdout.decode('utf-8').splitlines(): + fields = [fs.strip() for fs in line.split()] + if len(fields) != 2: + continue + if fields[0] == 'U' and any(fn in fields[1] for fn in BADFNS): + raise SystemExit(f'Solution rejected: a call to "{fields[1]}" ' + f'is not permitted!') + + with open(LOGFILE, 'wb') as f: + f.truncate() + + try: + unittest.main() + finally: + print(f'\nTest results were saved to "{LOGFILE}".') @@ -0,0 +1,220 @@ +#ifdef READLINE +#include <readline/readline.h> +#include <readline/history.h> +#endif + +#define DEBUG 0 +#include "shell.h" + +sigset_t sigchld_mask; + +static void sigint_handler(int sig) { + /* No-op handler, we just need break read() call with EINTR. */ + (void)sig; +} + +/* Rewrite closed file descriptors to -1, + * to make sure we don't attempt do close them twice. */ +static void MaybeClose(int *fdp) { + if (*fdp < 0) + return; + Close(*fdp); + *fdp = -1; +} + +/* Consume all tokens related to redirection operators. + * Put opened file descriptors into inputp & output respectively. */ +static int do_redir(token_t *token, int ntokens, int *inputp, int *outputp) { + token_t mode = NULL; /* T_INPUT, T_OUTPUT or NULL */ + int n = 0; /* number of tokens after redirections are removed */ + + for (int i = 0; i < ntokens; i++) { + /* TODO: Handle tokens and open files as requested. */ +#ifdef STUDENT + (void)mode; + (void)MaybeClose; +#endif /* !STUDENT */ + } + + token[n] = NULL; + return n; +} + +/* Execute internal command within shell's process or execute external command + * in a subprocess. External command can be run in the background. */ +static int do_job(token_t *token, int ntokens, bool bg) { + int input = -1, output = -1; + int exitcode = 0; + + ntokens = do_redir(token, ntokens, &input, &output); + + if (!bg) { + if ((exitcode = builtin_command(token)) >= 0) + return exitcode; + } + + sigset_t mask; + Sigprocmask(SIG_BLOCK, &sigchld_mask, &mask); + + /* TODO: Start a subprocess, create a job and monitor it. */ +#ifdef STUDENT +#endif /* !STUDENT */ + + Sigprocmask(SIG_SETMASK, &mask, NULL); + return exitcode; +} + +/* Start internal or external command in a subprocess that belongs to pipeline. + * All subprocesses in pipeline must belong to the same process group. */ +static pid_t do_stage(pid_t pgid, sigset_t *mask, int input, int output, + token_t *token, int ntokens, bool bg) { + ntokens = do_redir(token, ntokens, &input, &output); + + if (ntokens == 0) + app_error("ERROR: Command line is not well formed!"); + + /* TODO: Start a subprocess and make sure it's moved to a process group. */ + pid_t pid = Fork(); +#ifdef STUDENT +#endif /* !STUDENT */ + + return pid; +} + +static void mkpipe(int *readp, int *writep) { + int fds[2]; + Pipe(fds); + fcntl(fds[0], F_SETFD, FD_CLOEXEC); + fcntl(fds[1], F_SETFD, FD_CLOEXEC); + *readp = fds[0]; + *writep = fds[1]; +} + +/* Pipeline execution creates a multiprocess job. Both internal and external + * commands are executed in subprocesses. */ +static int do_pipeline(token_t *token, int ntokens, bool bg) { + pid_t pid, pgid = 0; + int job = -1; + int exitcode = 0; + + int input = -1, output = -1, next_input = -1; + + mkpipe(&next_input, &output); + + sigset_t mask; + Sigprocmask(SIG_BLOCK, &sigchld_mask, &mask); + + /* TODO: Start pipeline subprocesses, create a job and monitor it. + * Remember to close unused pipe ends! */ +#ifdef STUDENT + (void)input; + (void)job; + (void)pid; + (void)pgid; + (void)do_stage; +#endif /* !STUDENT */ + + Sigprocmask(SIG_SETMASK, &mask, NULL); + return exitcode; +} + +static bool is_pipeline(token_t *token, int ntokens) { + for (int i = 0; i < ntokens; i++) + if (token[i] == T_PIPE) + return true; + return false; +} + +static void eval(char *cmdline) { + bool bg = false; + int ntokens; + token_t *token = tokenize(cmdline, &ntokens); + + if (ntokens > 0 && token[ntokens - 1] == T_BGJOB) { + token[--ntokens] = NULL; + bg = true; + } + + if (ntokens > 0) { + if (is_pipeline(token, ntokens)) { + do_pipeline(token, ntokens, bg); + } else { + do_job(token, ntokens, bg); + } + } + + free(token); +} + +#ifndef READLINE +static char *readline(const char *prompt) { + static char line[MAXLINE]; /* `readline` is clearly not reentrant! */ + + write(STDOUT_FILENO, prompt, strlen(prompt)); + + line[0] = '\0'; + + ssize_t nread = read(STDIN_FILENO, line, MAXLINE); + if (nread < 0) { + if (errno != EINTR) + unix_error("Read error"); + msg("\n"); + } else if (nread == 0) { + return NULL; /* EOF */ + } else { + if (line[nread - 1] == '\n') + line[nread - 1] = '\0'; + } + + return strdup(line); +} +#endif + +int main(int argc, char *argv[]) { + /* `stdin` should be attached to terminal running in canonical mode */ + if (!isatty(STDIN_FILENO)) + app_error("ERROR: Shell can run only in interactive mode!"); + +#ifdef READLINE + rl_initialize(); +#endif + + sigemptyset(&sigchld_mask); + sigaddset(&sigchld_mask, SIGCHLD); + + if (getsid(0) != getpgid(0)) + Setpgid(0, 0); + + initjobs(); + + struct sigaction act = { + .sa_handler = sigint_handler, + .sa_flags = 0, /* without SA_RESTART read() will return EINTR */ + }; + Sigaction(SIGINT, &act, NULL); + + Signal(SIGTSTP, SIG_IGN); + Signal(SIGTTIN, SIG_IGN); + Signal(SIGTTOU, SIG_IGN); + + while (true) { + char *line = readline("# "); + + if (line == NULL) + break; + + if (strlen(line)) { +#ifdef READLINE + add_history(line); +#endif + eval(line); + } + free(line); + watchjobs(FINISHED); + } + + msg("\n"); + shutdownjobs(); + + return 0; +} @@ -0,0 +1,65 @@ +#ifndef _SHELL_H_ +#define _SHELL_H_ + +#include "csapp.h" + +#define msg(...) dprintf(STDERR_FILENO, __VA_ARGS__) + +#if DEBUG > 0 +#define debug(...) dprintf(STDERR_FILENO, __VA_ARGS__) +#else +#define debug(...) +#endif + +typedef char *token_t; + +#define T_NULL ((token_t)0) +#define T_AND ((token_t)1) +#define T_OR ((token_t)2) +#define T_PIPE ((token_t)3) +#define T_BGJOB ((token_t)4) +#define T_COLON ((token_t)5) +#define T_OUTPUT ((token_t)6) +#define T_INPUT ((token_t)7) +#define T_APPEND ((token_t)8) +#define T_BANG ((token_t)9) +#define separator_p(t) ((t) <= T_COLON) +#define string_p(t) ((t) > T_BANG) + +void strapp(char **dstp, const char *src); +token_t *tokenize(char *s, int *tokc_p); + +/* Do not change those values or code will break! */ +enum { + FG = 0, /* foreground job */ + BG = 1, /* background job */ +}; + +/* Do not change those values or code will break! */ +enum { + ALL = -1, /* all jobs */ + FINISHED = 0, /* only jobs that have finished */ + RUNNING = 1, /* only jobs that are still running */ + STOPPED = 2, /* jobs that have been suspended by SIGTSTP / SIGSTOP */ +}; + +void initjobs(void); +void shutdownjobs(void); + +int addjob(pid_t pgid, int bg); +void addproc(int job, pid_t pid, char **argv); +bool killjob(int job); +void watchjobs(int state); +char *jobcmd(int job); +bool resumejob(int job, int bg, sigset_t *mask); +int monitorjob(sigset_t *mask); + +void setfgpgrp(pid_t pgid); + +int builtin_command(char **argv); +noreturn void external_command(char **argv); + +/* Used by Sigprocmask to enter critical section protecting against SIGCHLD. */ +extern sigset_t sigchld_mask; + +#endif /* !_SHELL_H_ */ @@ -0,0 +1,148 @@ +/* You MUST NOT modify this file without author's consent. + * Doing so is considered cheating! */ + +#define _GNU_SOURCE +#include <assert.h> +#include <stdarg.h> +#include <stdio.h> +#include <stdlib.h> +#include <signal.h> +#include <unistd.h> +#include <termios.h> +#include <dlfcn.h> + +static int (*execve_p)(const char *path, char *const argv[], + char *const envp[]) = NULL; +static int (*fork_p)(void) = NULL; +static pid_t (*waitpid_p)(pid_t pid, int *status, int options) = NULL; +static int (*dup2_p)(int oldfd, int newfd) = NULL; +static int (*open_p)(const char *pathname, int flags, mode_t mode) = NULL; +static int (*close_p)(int fd) = NULL; +static int (*setpgid_p)(pid_t pid, pid_t pgid) = NULL; +static int (*tcsetpgrp_p)(int fd, pid_t pgrp); +static int (*tcsetattr_p)(int fd, int action, const struct termios *t); +static int (*kill_p)(pid_t pid, int sig); + +static void xdlsym(const char *symbol, void **fn_p) { + if (*fn_p == NULL) { + *fn_p = dlsym(RTLD_NEXT, symbol); + char *error = dlerror(); + if (error) { + fputs(error, stderr); + exit(EXIT_FAILURE); + } + } +} + +#define LINESZ 256 + +static __attribute__((format(printf, 1, 2))) void report(const char *fmt, ...) { + char line[LINESZ]; + int n = 0; + va_list args; + va_start(args, fmt); + n += snprintf(line + n, LINESZ - n, "[%d:%d] ", getpid(), getpgrp()); + n += vsnprintf(line + n, LINESZ - n, fmt, args); + assert(n < LINESZ); /* Need one character to terminate string! */ + line[n++] = '\n'; + va_end(args); + int m = write(STDERR_FILENO, line, n); + assert(m == n); /* Fail if write was not atomic! */ +} + +int execve(const char *path, char *const argv[], char *const envp[]) { + xdlsym("execve", (void **)&execve_p); + report("execve(\"%s\", %p, %p)", path, argv, envp); + return execve_p(path, argv, envp); +} + +int fork(void) { + xdlsym("fork", (void **)&fork_p); + pid_t child = fork_p(); + if (child) + report("fork() = %d", child); + return child; +} + +#define _SN(x) [x] = #x + +static const char *signame[NSIG] = { + _SN(SIGHUP), _SN(SIGINT), _SN(SIGQUIT), _SN(SIGILL), _SN(SIGTRAP), + _SN(SIGABRT), _SN(SIGFPE), _SN(SIGKILL), _SN(SIGBUS), _SN(SIGSYS), + _SN(SIGSEGV), _SN(SIGPIPE), _SN(SIGALRM), _SN(SIGTERM), _SN(SIGURG), + _SN(SIGSTOP), _SN(SIGTSTP), _SN(SIGCONT), _SN(SIGCHLD), _SN(SIGTTIN), + _SN(SIGTTOU), _SN(SIGPOLL), _SN(SIGXCPU), _SN(SIGXFSZ), _SN(SIGVTALRM), + _SN(SIGPROF), _SN(SIGUSR1), _SN(SIGUSR2), _SN(SIGWINCH)}; + +#undef _SN + +pid_t waitpid(pid_t pid, int *statusp, int options) { + int status; + xdlsym("waitpid", (void **)&waitpid_p); + pid = waitpid_p(pid, &status, options); + if (pid <= 0) { + report("waitpid(...) -> {}"); + } else if (WIFCONTINUED(status)) { + report("waitpid(...) -> {pid=%d, status=SIGCONT}", pid); + } else if (WIFSTOPPED(status)) { + report("waitpid(...) -> {pid=%d, status=%s}", pid, + signame[WSTOPSIG(status)]); + } else if (WIFSIGNALED(status)) { + report("waitpid(...) -> {pid=%d, status=%s}", pid, + signame[WTERMSIG(status)]); + } else if (WIFEXITED(status)) { + report("waitpid(...) -> {pid=%d, status=%d}", pid, WEXITSTATUS(status)); + } + if (statusp) + *statusp = status; + return pid; +} + +int open(const char *pathname, int flags, mode_t mode) { + xdlsym("open", (void **)&open_p); + int res = open_p(pathname, flags, mode); + report("open(\"%s\", %d, %d) = %d", pathname, flags, mode, res); + return res; +} + +int close(int fd) { + xdlsym("close", (void **)&close_p); + int res = close_p(fd); + report("close(%d) = %d", fd, res); + return res; +} + +int dup2(int oldfd, int newfd) { + xdlsym("dup2", (void **)&dup2_p); + int res = dup2_p(oldfd, newfd); + report("dup2(%d, %d) = %d", oldfd, newfd, res); + return res; +} + +int setpgid(pid_t pid, pid_t pgid) { + xdlsym("setpgid", (void **)&setpgid_p); + int res = setpgid_p(pid, pgid); + report("setpgid(%d, %d) = %d", pid, pgid, res); + return res; +} + +int kill(pid_t pid, int sig) { + xdlsym("kill", (void **)&kill_p); + int res = kill_p(pid, sig); + report("kill(%d, %s) = %d", pid, signame[sig], res); + return res; +} + +int tcsetpgrp(int fd, pid_t pgrp) { + xdlsym("tcsetpgrp", (void **)&tcsetpgrp_p); + int res = tcsetpgrp_p(fd, pgrp); + report("tcsetpgrp(%d, %d) = %d", fd, pgrp, res); + return res; +} + +int tcsetattr(int fd, int action, const struct termios *t) { + xdlsym("tcsetattr", (void **)&tcsetattr_p); + int res = tcsetattr_p(fd, action, t); + report("tcsetattr(%d, %d, %p) = %d", fd, action, t, res); + return res; +} |