diff options
41 files changed, 1882 insertions, 77 deletions
diff --git a/.clang-format b/.clang-format new file mode 100644 index 0000000..065dcdf --- /dev/null +++ b/.clang-format @@ -0,0 +1,225 @@ +--- +Language: Cpp +# BasedOnStyle: Mozilla +AccessModifierOffset: -2 +AlignAfterOpenBracket: Align +AlignArrayOfStructures: None +AlignConsecutiveAssignments: + Enabled: false + AcrossEmptyLines: false + AcrossComments: false + AlignCompound: false + PadOperators: true +AlignConsecutiveBitFields: + Enabled: false + AcrossEmptyLines: false + AcrossComments: false + AlignCompound: false + PadOperators: false +AlignConsecutiveDeclarations: + Enabled: false + AcrossEmptyLines: false + AcrossComments: false + AlignCompound: false + PadOperators: false +AlignConsecutiveMacros: + Enabled: false + AcrossEmptyLines: false + AcrossComments: false + AlignCompound: false + PadOperators: false +AlignEscapedNewlines: Right +AlignOperands: Align +AlignTrailingComments: + Kind: Always + OverEmptyLines: 0 +AllowAllArgumentsOnNextLine: true +AllowAllParametersOfDeclarationOnNextLine: false +AllowShortBlocksOnASingleLine: Never +AllowShortCaseLabelsOnASingleLine: false +AllowShortEnumsOnASingleLine: true +AllowShortFunctionsOnASingleLine: Inline +AllowShortIfStatementsOnASingleLine: Never +AllowShortLambdasOnASingleLine: All +AllowShortLoopsOnASingleLine: false +AlwaysBreakAfterDefinitionReturnType: TopLevel +AlwaysBreakAfterReturnType: TopLevel +AlwaysBreakBeforeMultilineStrings: false +AlwaysBreakTemplateDeclarations: Yes +AttributeMacros: + - __capability +BinPackArguments: false +BinPackParameters: false +BitFieldColonSpacing: Both +BraceWrapping: + AfterCaseLabel: false + AfterClass: true + AfterControlStatement: Never + AfterEnum: true + AfterExternBlock: true + AfterFunction: true + AfterNamespace: false + AfterObjCDeclaration: false + AfterStruct: true + AfterUnion: true + BeforeCatch: false + BeforeElse: false + BeforeLambdaBody: false + BeforeWhile: false + IndentBraces: false + SplitEmptyFunction: true + SplitEmptyRecord: false + SplitEmptyNamespace: true +BreakAfterAttributes: Never +BreakAfterJavaFieldAnnotations: false +BreakArrays: true +BreakBeforeBinaryOperators: None +BreakBeforeConceptDeclarations: Always +BreakBeforeBraces: Mozilla +BreakBeforeInlineASMColon: OnlyMultiline +BreakBeforeTernaryOperators: true +BreakConstructorInitializers: BeforeComma +BreakInheritanceList: BeforeComma +BreakStringLiterals: true +ColumnLimit: 80 +CommentPragmas: '^ IWYU pragma:' +CompactNamespaces: false +ConstructorInitializerIndentWidth: 2 +ContinuationIndentWidth: 2 +Cpp11BracedListStyle: false +DerivePointerAlignment: false +DisableFormat: false +EmptyLineAfterAccessModifier: Never +EmptyLineBeforeAccessModifier: LogicalBlock +ExperimentalAutoDetectBinPacking: false +FixNamespaceComments: false +ForEachMacros: + - foreach + - Q_FOREACH + - BOOST_FOREACH +IfMacros: + - KJ_IF_MAYBE +IncludeBlocks: Preserve +IncludeCategories: + - Regex: '^"(llvm|llvm-c|clang|clang-c)/' + Priority: 2 + SortPriority: 0 + CaseSensitive: false + - Regex: '^(<|"(gtest|gmock|isl|json)/)' + Priority: 3 + SortPriority: 0 + CaseSensitive: false + - Regex: '.*' + Priority: 1 + SortPriority: 0 + CaseSensitive: false +IncludeIsMainRegex: '(Test)?$' +IncludeIsMainSourceRegex: '' +IndentAccessModifiers: false +IndentCaseBlocks: false +IndentCaseLabels: true +IndentExternBlock: AfterExternBlock +IndentGotoLabels: true +IndentPPDirectives: None +IndentRequiresClause: true +IndentWidth: 2 +IndentWrappedFunctionNames: false +InsertBraces: false +InsertNewlineAtEOF: false +InsertTrailingCommas: None +IntegerLiteralSeparator: + Binary: 0 + BinaryMinDigits: 0 + Decimal: 0 + DecimalMinDigits: 0 + Hex: 0 + HexMinDigits: 0 +JavaScriptQuotes: Leave +JavaScriptWrapImports: true +KeepEmptyLinesAtTheStartOfBlocks: true +LambdaBodyIndentation: Signature +LineEnding: DeriveLF +MacroBlockBegin: '' +MacroBlockEnd: '' +MaxEmptyLinesToKeep: 1 +NamespaceIndentation: None +ObjCBinPackProtocolList: Auto +ObjCBlockIndentWidth: 2 +ObjCBreakBeforeNestedBlockParam: true +ObjCSpaceAfterProperty: true +ObjCSpaceBeforeProtocolList: false +PackConstructorInitializers: BinPack +PenaltyBreakAssignment: 2 +PenaltyBreakBeforeFirstCallParameter: 19 +PenaltyBreakComment: 300 +PenaltyBreakFirstLessLess: 120 +PenaltyBreakOpenParenthesis: 0 +PenaltyBreakString: 1000 +PenaltyBreakTemplateDeclaration: 10 +PenaltyExcessCharacter: 1000000 +PenaltyIndentedWhitespace: 0 +PenaltyReturnTypeOnItsOwnLine: 200 +PointerAlignment: Left +PPIndentWidth: -1 +QualifierAlignment: Leave +ReferenceAlignment: Pointer +ReflowComments: true +RemoveBracesLLVM: false +RemoveSemicolon: false +RequiresClausePosition: OwnLine +RequiresExpressionIndentation: OuterScope +SeparateDefinitionBlocks: Leave +ShortNamespaceLines: 1 +SortIncludes: CaseSensitive +SortJavaStaticImport: Before +SortUsingDeclarations: LexicographicNumeric +SpaceAfterCStyleCast: false +SpaceAfterLogicalNot: false +SpaceAfterTemplateKeyword: false +SpaceAroundPointerQualifiers: Default +SpaceBeforeAssignmentOperators: true +SpaceBeforeCaseColon: false +SpaceBeforeCpp11BracedList: false +SpaceBeforeCtorInitializerColon: true +SpaceBeforeInheritanceColon: true +SpaceBeforeParens: ControlStatements +SpaceBeforeParensOptions: + AfterControlStatements: true + AfterForeachMacros: true + AfterFunctionDefinitionName: false + AfterFunctionDeclarationName: false + AfterIfMacros: true + AfterOverloadedOperator: false + AfterRequiresInClause: false + AfterRequiresInExpression: false + BeforeNonEmptyParentheses: false +SpaceBeforeRangeBasedForLoopColon: true +SpaceBeforeSquareBrackets: false +SpaceInEmptyBlock: false +SpaceInEmptyParentheses: false +SpacesBeforeTrailingComments: 1 +SpacesInAngles: Never +SpacesInConditionalStatement: false +SpacesInContainerLiterals: true +SpacesInCStyleCastParentheses: false +SpacesInLineCommentPrefix: + Minimum: 1 + Maximum: -1 +SpacesInParentheses: false +SpacesInSquareBrackets: false +Standard: Latest +StatementAttributeLikeMacros: + - Q_EMIT +StatementMacros: + - Q_UNUSED + - QT_REQUIRE_VERSION +TabWidth: 8 +UseTab: Never +WhitespaceSensitiveMacros: + - BOOST_PP_STRINGIZE + - CF_SWIFT_NAME + - NS_SWIFT_NAME + - PP_STRINGIZE + - STRINGIZE +... + @@ -25,3 +25,5 @@ barrier .DS_Store *.dSYM *.pcap +riscv/ +compile_flags.txt @@ -13,12 +13,14 @@ OBJS = \ $K/kalloc.o \ $K/string.o \ $K/main.o \ + $K/cow.o \ $K/vm.o \ $K/proc.o \ $K/swtch.o \ $K/trampoline.o \ $K/trap.o \ $K/syscall.o \ + $K/sysinfo.o \ $K/sysproc.o \ $K/bio.o \ $K/fs.o \ @@ -90,7 +92,7 @@ CFLAGS = -Wall -Werror -O -fno-omit-frame-pointer -ggdb -gdwarf-2 ifdef LAB LABUPPER = $(shell echo $(LAB) | tr a-z A-Z) -XCFLAGS += -DSOL_$(LABUPPER) -DLAB_$(LABUPPER) +XCFLAGS += -DSOL_$(LABUPPER) -DLAB_$(LABUPPER) -DLAB_PGTBL endif CFLAGS += $(XCFLAGS) @@ -188,6 +190,13 @@ UPROGS=\ $U/_grind\ $U/_wc\ $U/_zombie\ + $U/_sleep\ + $U/_pingpong\ + $U/_primes\ + $U/_find\ + $U/_xargs\ + $U/_trace\ + $U/_sysinfotest\ @@ -197,21 +206,18 @@ UPROGS += \ $U/_stats endif -ifeq ($(LAB),traps) UPROGS += \ $U/_call\ - $U/_bttest -endif + $U/_bttest\ + $U/_alarmtest ifeq ($(LAB),lazy) UPROGS += \ $U/_lazytests endif -ifeq ($(LAB),cow) UPROGS += \ $U/_cowtest -endif ifeq ($(LAB),thread) UPROGS += \ @@ -231,10 +237,8 @@ barrier: notxv6/barrier.c gcc -o barrier -g -O2 $(XCFLAGS) notxv6/barrier.c -pthread endif -ifeq ($(LAB),pgtbl) UPROGS += \ $U/_pgtbltest -endif ifeq ($(LAB),lock) UPROGS += \ @@ -255,9 +259,7 @@ UPROGS += \ endif UEXTRA= -ifeq ($(LAB),util) - UEXTRA += user/xargstest.sh -endif +UEXTRA += user/xargstest.sh fs.img: mkfs/mkfs README $(UEXTRA) $(UPROGS) @@ -266,11 +268,13 @@ fs.img: mkfs/mkfs README $(UEXTRA) $(UPROGS) -include kernel/*.d user/*.d clean: - rm -rf *.tex *.dvi *.idx *.aux *.log *.ind *.ilg *.dSYM *.zip *.pcap \ + rm -f *.tex *.dvi *.idx *.aux *.log *.ind *.ilg *.dSYM *.zip \ */*.o */*.d */*.asm */*.sym \ - $U/initcode $U/initcode.out $U/usys.S $U/_* \ - $K/kernel \ - mkfs/mkfs fs.img .gdbinit __pycache__ xv6.out* \ + $U/initcode $U/initcode.out $K/kernel fs.img \ + mkfs/mkfs .gdbinit \ + $U/usys.S \ + $(UPROGS) \ + *.zip \ ph barrier # try to generate a unique GDB port diff --git a/answers-pgtbl.txt b/answers-pgtbl.txt new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/answers-pgtbl.txt diff --git a/answers-syscall.txt b/answers-syscall.txt new file mode 100644 index 0000000..ca0ce77 --- /dev/null +++ b/answers-syscall.txt @@ -0,0 +1,9 @@ +usertrap() +7 +SYS_exec +user mode +lw a3,0(zero) +a3 +no +yes, `scause` 0xd -> interrupt = 0, exception code = 13 -> instruction page fault (riscv-priviledged p71) +'initcode', 1 diff --git a/answers-traps.txt b/answers-traps.txt new file mode 100644 index 0000000..dbb40f1 --- /dev/null +++ b/answers-traps.txt @@ -0,0 +1,6 @@ +a0~a7, a2 +0x26 (optimized during compile time), 0x14 (inline, unfolded) +0x666 +0x38 (next instruction) +He110 World +the value in register a2 diff --git a/grade-lab-cow b/grade-lab-cow new file mode 100755 index 0000000..08b6990 --- /dev/null +++ b/grade-lab-cow @@ -0,0 +1,55 @@ +#!/usr/bin/env python3 + +import re +from gradelib import * + +r = Runner(save("xv6.out")) + +@test(0, "running cowtest") +def test_cowtest(): + r.run_qemu(shell_script([ + 'cowtest' + ])) + +@test(30, "simple", parent=test_cowtest) +def test_simple(): + matches = re.findall("^simple: ok$", r.qemu.output, re.M) + assert_equal(len(matches), 2, "Number of appearances of 'simple: ok'") + +@test(30, "three", parent=test_cowtest) +def test_three(): + matches = re.findall("^three: ok$", r.qemu.output, re.M) + assert_equal(len(matches), 3, "Number of appearances of 'three: ok'") + +@test(20, "file", parent=test_cowtest) +def test_file(): + r.match('^file: ok$') + +@test(0, "usertests") +def test_usertests(): + r.run_qemu(shell_script([ + 'usertests -q' + ]), timeout=1000) + r.match('^ALL TESTS PASSED$') + +def usertest_check(testcase, nextcase, output): + if not re.search(r'\ntest {}: [\s\S]*OK\ntest {}'.format(testcase, nextcase), output): + raise AssertionError('Failed ' + testcase) + +@test(5, "usertests: copyin", parent=test_usertests) +def test_sbrkbugs(): + usertest_check("copyin", "copyout", r.qemu.output) + +@test(5, "usertests: copyout", parent=test_usertests) +def test_sbrkbugs(): + usertest_check("copyout", "copyinstr1", r.qemu.output) + +@test(19, "usertests: all tests", parent=test_usertests) +def test_usertests_all(): + r.match('^ALL TESTS PASSED$') + +@test(1, "time") +def test_time(): + check_time() + +run_tests() diff --git a/grade-lab-pgtbl b/grade-lab-pgtbl new file mode 100755 index 0000000..121bb3b --- /dev/null +++ b/grade-lab-pgtbl @@ -0,0 +1,79 @@ +#!/usr/bin/env python3 + +import re +from gradelib import * + +r = Runner(save("xv6.out")) + +PTE_PRINT = """page table 0x0000000087f6b000 + ..0: pte 0x0000000021fd9c01 pa 0x0000000087f67000 + .. ..0: pte 0x0000000021fd9801 pa 0x0000000087f66000 + .. .. ..0: pte 0x0000000021fda01b pa 0x0000000087f68000 + .. .. ..1: pte 0x0000000021fd9417 pa 0x0000000087f65000 + .. .. ..2: pte 0x0000000021fd9007 pa 0x0000000087f64000 + .. .. ..3: pte 0x0000000021fd8c17 pa 0x0000000087f63000 + ..255: pte 0x0000000021fda801 pa 0x0000000087f6a000 + .. ..511: pte 0x0000000021fda401 pa 0x0000000087f69000 + .. .. ..509: pte 0x0000000021fdcc13 pa 0x0000000087f73000 + .. .. ..510: pte 0x0000000021fdd007 pa 0x0000000087f74000 + .. .. ..511: pte 0x0000000020001c0b pa 0x0000000080007000""" + +VAL_RE = "(0x00000000[0-9a-f]+)" +INDENT_RE = r"\s*\.\.\s*" +INDENT_ESC = "\\\s*\.\.\\\s*" + +@test(0, "pgtbltest") +def test_pgtbltest(): + r.run_qemu(shell_script([ + 'pgtbltest' + ]), timeout=300) + +@test(10, "pgtbltest: ugetpid", parent=test_pgtbltest) +def test_nettest_(): + r.match('^ugetpid_test: OK$') + +@test(10, "pgtbltest: pgaccess", parent=test_pgtbltest) +def test_nettest_(): + r.match('^pgaccess_test: OK$') + +@test(10, "pte printout") +def test_pteprint(): + first = True + r.run_qemu(shell_script([ + 'echo hi' + ])) + r.match('^hi') + p = re.compile(VAL_RE) + d = re.compile(INDENT_RE) + for l in PTE_PRINT.splitlines(): + l = d.sub(INDENT_ESC, l) + l = p.sub(VAL_RE, l) + r.match(r'^{}$'.format(l)) + if first: + first = False + else: + matches = re.findall(r'^{}$'.format(l), r.qemu.output, re.MULTILINE) + assert_equal(len(matches[0]), 2) + pa = (int(matches[0][0], 16) >> 10) << 12 + assert_equal(int(matches[0][1], 16), pa) + +@test(5, "answers-pgtbl.txt") +def test_answers(): + # just a simple sanity check, will be graded manually + check_answers("answers-pgtbl.txt") + +@test(0, "usertests") +def test_usertests(): + r.run_qemu(shell_script([ + 'usertests -q' + ]), timeout=300) + +@test(10, "usertests: all tests", parent=test_usertests) +def test_usertests(): + r.match('^ALL TESTS PASSED$') + +@test(1, "time") +def test_time(): + check_time() + +run_tests() diff --git a/grade-lab-traps b/grade-lab-traps new file mode 100755 index 0000000..10613d3 --- /dev/null +++ b/grade-lab-traps @@ -0,0 +1,74 @@ +#!/usr/bin/env python3 + +import os +import re +import subprocess +from gradelib import * + +r = Runner(save("xv6.out")) + +@test(5, "answers-traps.txt") +def test_answers(): + # just a simple sanity check, will be graded manually + check_answers("answers-traps.txt") + +BACKTRACE_RE = r"^(0x000000008[0-9a-f]+)" + +def addr2line(): + for f in ['riscv64-unknown-elf-addr2line', 'riscv64-linux-gnu-addr2line', 'addr2line', ]: + try: + devnull = open(os.devnull) + subprocess.Popen([f], stdout=devnull, stderr=devnull).communicate() + return f + except OSError: + continue + raise AssertionError('Cannot find the addr2line program') + +@test(10, "backtrace test") +def test_backtracetest(): + r.run_qemu(shell_script([ + 'bttest' + ])) + a2l = addr2line() + matches = re.findall(BACKTRACE_RE, r.qemu.output, re.MULTILINE) + assert_equal(len(matches), 3) + files = ['sysproc.c', 'syscall.c', 'trap.c'] + for f, m in zip(files, matches): + result = subprocess.run([a2l, '-e', 'kernel/kernel', m], stdout=subprocess.PIPE) + if not f in result.stdout.decode("utf-8"): + raise AssertionError('Trace is incorrect; no %s' % f) + +@test(0, "running alarmtest") +def test_alarmtest(): + r.run_qemu(shell_script([ + 'alarmtest' + ])) + +@test(20, "alarmtest: test0", parent=test_alarmtest) +def test_alarmtest_test0(): + r.match('^test0 passed$') + +@test(20, "alarmtest: test1", parent=test_alarmtest) +def test_alarmtest_test1(): + r.match('^\\.?test1 passed$') + +@test(10, "alarmtest: test2", parent=test_alarmtest) +def test_alarmtest_test2(): + r.match('^\\.?test2 passed$') + +@test(10, "alarmtest: test3", parent=test_alarmtest) +def test_alarmtest_test3(): + r.match('^test3 passed$') + +@test(19, "usertests") +def test_usertests(): + r.run_qemu(shell_script([ + 'usertests -q' + ]), timeout=300) + r.match('^ALL TESTS PASSED$') + +@test(1, "time") +def test_time(): + check_time() + +run_tests() diff --git a/kernel/cow.c b/kernel/cow.c new file mode 100644 index 0000000..b3634fc --- /dev/null +++ b/kernel/cow.c @@ -0,0 +1,30 @@ +// COW pagefault handler +#include "types.h" +#include "riscv.h" +#include "defs.h" + +int +cow_handler(pagetable_t pagetable, uint64 va) +{ + // you can't really write to rediculous pointers + if(va >= MAXVA || PGROUNDDOWN(va) == 0) + return -1; + pte_t *pte = walk(pagetable, va, 0); + if(pte == 0 || (*pte & PTE_V) == 0 || (*pte & PTE_U) == 0) + return -1; + if(*pte & PTE_C){ + uint64 pa_orig = PTE2PA(*pte); + uint64 pa_new = (uint64)kalloc(); + if(pa_new == 0){ + printf("cow pagefault: kalloc failed\n"); + return -1; + } + // copy the page and add write permission + memmove((void*)pa_new, (void*)pa_orig, PGSIZE); + uint64 flags = (PTE_FLAGS(*pte) | PTE_W) & ~PTE_C; + *pte = PA2PTE(pa_new) | flags; + kfree((void*)pa_orig); + } else if ((*pte & PTE_W) == 0) + return -1; + return 0; +} diff --git a/kernel/defs.h b/kernel/defs.h index c6fef8c..02226b5 100644 --- a/kernel/defs.h +++ b/kernel/defs.h @@ -12,6 +12,7 @@ struct superblock; struct mbuf; struct sock; #endif +struct sysinfo; // bio.c void binit(void); @@ -26,6 +27,9 @@ void consoleinit(void); void consoleintr(int); void consputc(int); +// cow.c +int cow_handler(pagetable_t, uint64); + // exec.c int exec(char*, char**); @@ -64,9 +68,12 @@ void ramdiskintr(void); void ramdiskrw(struct buf*); // kalloc.c +int refcnt_inc(uint64); +int refcnt_dec(uint64); void* kalloc(void); void kfree(void *); void kinit(void); +int get_freemem(void); // log.c void initlog(int, struct superblock*); @@ -84,6 +91,7 @@ int pipewrite(struct pipe*, uint64, int); void printf(char*, ...); void panic(char*) __attribute__((noreturn)); void printfinit(void); +void backtrace(void); // proc.c int cpuid(void); @@ -110,6 +118,8 @@ void yield(void); int either_copyout(int user_dst, uint64 dst, void *src, uint64 len); int either_copyin(void *dst, int user_src, uint64 src, uint64 len); void procdump(void); +int get_nproc(void); +int pgaccess(uint64 base, int len, uint64 mask); // swtch.S void swtch(struct context*, struct context*); @@ -149,6 +159,9 @@ int fetchstr(uint64, char*, int); int fetchaddr(uint64, uint64*); void syscall(); +// sysinfo.c +int sys_info(uint64); + // trap.c extern uint ticks; void trapinit(void); @@ -181,6 +194,7 @@ uint64 walkaddr(pagetable_t, uint64); int copyout(pagetable_t, uint64, char *, uint64); int copyin(pagetable_t, char *, uint64, uint64); int copyinstr(pagetable_t, char *, uint64, uint64); +void vmprint(pagetable_t); // plic.c void plicinit(void); diff --git a/kernel/exec.c b/kernel/exec.c index e18bbb6..35b35f5 100644 --- a/kernel/exec.c +++ b/kernel/exec.c @@ -128,6 +128,10 @@ exec(char *path, char **argv) p->trapframe->sp = sp; // initial stack pointer proc_freepagetable(oldpagetable, oldsz); + if(p->pid == 1){ + vmprint(p->pagetable); + } + return argc; // this ends up in a0, the first argument to main(argc, argv) bad: diff --git a/kernel/kalloc.c b/kernel/kalloc.c index 0699e7e..581f0f6 100644 --- a/kernel/kalloc.c +++ b/kernel/kalloc.c @@ -23,10 +23,41 @@ struct { struct run *freelist; } kmem; +int phypg_refcnt[PHYSTOP/PGSIZE]; + +// Increase the refcnt +int +refcnt_inc(uint64 pa) +{ + acquire(&kmem.lock); + int *prefcnt = &phypg_refcnt[pa/PGSIZE]; + if(pa > PHYSTOP || *prefcnt < 1) + panic("increase refcnt"); + (*prefcnt)++; + release(&kmem.lock); + return *prefcnt; +} + +// Decrease the refcnt +int +refcnt_dec(uint64 pa) +{ + acquire(&kmem.lock); + int *prefcnt = &phypg_refcnt[pa/PGSIZE]; + if(pa > PHYSTOP || *prefcnt < 1) + panic("decrease refcnt"); + (*prefcnt)--; + release(&kmem.lock); + return *prefcnt; +} + void kinit() { initlock(&kmem.lock, "kmem"); + // init all refcnt to 1, which would later be freed to 0 by kfree() + for(uint64 p = PGROUNDUP((uint64)end); p + PGSIZE <= PHYSTOP; p += PGSIZE) + phypg_refcnt[p/PGSIZE] = 1; freerange(end, (void*)PHYSTOP); } @@ -51,6 +82,12 @@ kfree(void *pa) if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP) panic("kfree"); + refcnt_dec((uint64)pa); + + if(phypg_refcnt[(uint64)pa/PGSIZE] > 0) + // We still have refs to this phy page, do not actually free it + return; + // Fill with junk to catch dangling refs. memset(pa, 1, PGSIZE); @@ -72,11 +109,29 @@ kalloc(void) acquire(&kmem.lock); r = kmem.freelist; - if(r) + if(r){ + if(phypg_refcnt[(uint64)r/PGSIZE]) + panic("kalloc: invalid refcnt"); + phypg_refcnt[(uint64)r/PGSIZE] = 1; kmem.freelist = r->next; + } release(&kmem.lock); if(r) memset((char*)r, 5, PGSIZE); // fill with junk return (void*)r; } + +int +get_freemem(void) +{ + int n; + struct run *r; + + acquire(&kmem.lock); + for (n = 0, r = kmem.freelist; r; r = r->next) + n++; + release(&kmem.lock); + + return n * PGSIZE; +} diff --git a/kernel/printf.c b/kernel/printf.c index 1a50203..509c1c5 100644 --- a/kernel/printf.c +++ b/kernel/printf.c @@ -122,6 +122,8 @@ panic(char *s) printf("panic: "); printf(s); printf("\n"); + backtrace(); + panicked = 1; // freeze uart output from other CPUs for(;;) ; @@ -133,3 +135,18 @@ printfinit(void) initlock(&pr.lock, "pr"); pr.locking = 1; } + +void +backtrace(void) +{ + uint64 fp = r_fp(); + printf("backtrace:\n"); + uint64 stackpg = PGROUNDDOWN(fp); + // Whereever fp points to should always live in the stack page + while(PGROUNDDOWN(fp) == stackpg){ + // print the return addr (stored in fp-8) + printf("%p\n", *(uint64 *)(fp-8)); + // load previous (upper stack) fp + fp = *(uint64 *)(fp-16); + } +} diff --git a/kernel/proc.c b/kernel/proc.c index 58a8a0b..9a9bae9 100644 --- a/kernel/proc.c +++ b/kernel/proc.c @@ -39,6 +39,7 @@ proc_mapstacks(pagetable_t kpgtbl) if(pa == 0) panic("kalloc"); uint64 va = KSTACK((int) (p - proc)); + p->alarm_tickspassed = 0; kvmmap(kpgtbl, va, (uint64)pa, PGSIZE, PTE_R | PTE_W); } } @@ -132,6 +133,25 @@ found: return 0; } + // Allocate a usyscall page and fill pid. + if((p->usyscall = (struct usyscall *)kalloc()) == 0){ + freeproc(p); + release(&p->lock); + return 0; + } + p->usyscall->pid = p->pid; + + // reset sigalarm props + p->alarm_interval = 0; + p->alarm_handler = 0; + p->alarm_tickspassed = 0; + p->alarm_caninvoke = 1; + if((p->atpfm = (struct trapframe *)kalloc()) == 0){ + freeproc(p); + release(&p->lock); + return 0; + } + // An empty user page table. p->pagetable = proc_pagetable(p); if(p->pagetable == 0){ @@ -158,8 +178,18 @@ freeproc(struct proc *p) if(p->trapframe) kfree((void*)p->trapframe); p->trapframe = 0; + if(p->usyscall) + kfree((void*)p->usyscall); + p->usyscall = 0; if(p->pagetable) proc_freepagetable(p->pagetable, p->sz); + if(p->atpfm) + kfree((void*)p->atpfm); + p->atpfm = 0; + p->alarm_interval = 0; + p->alarm_handler = 0; + p->alarm_tickspassed = 0; + p->alarm_caninvoke = 1; p->pagetable = 0; p->sz = 0; p->pid = 0; @@ -172,7 +202,7 @@ freeproc(struct proc *p) } // Create a user page table for a given process, with no user memory, -// but with trampoline and trapframe pages. +// but with trampoline, trapframe and usyscall pages. pagetable_t proc_pagetable(struct proc *p) { @@ -202,6 +232,14 @@ proc_pagetable(struct proc *p) return 0; } + // map the usyscall page below the trapframe page, for + // ugetpid(). + if(mappages(pagetable, USYSCALL, PGSIZE, + (uint64)(p->usyscall), PTE_R | PTE_U) < 0){ + uvmunmap(pagetable, USYSCALL, 1, 0); + uvmfree(pagetable, 0); + return 0; + } return pagetable; } @@ -212,6 +250,7 @@ proc_freepagetable(pagetable_t pagetable, uint64 sz) { uvmunmap(pagetable, TRAMPOLINE, 1, 0); uvmunmap(pagetable, TRAPFRAME, 1, 0); + uvmunmap(pagetable, USYSCALL, 1, 0); uvmfree(pagetable, sz); } @@ -299,6 +338,9 @@ fork(void) // copy saved user registers. *(np->trapframe) = *(p->trapframe); + // inherit trace_mask + np->trace_mask = p->trace_mask; + // Cause fork to return 0 in the child. np->trapframe->a0 = 0; @@ -686,3 +728,43 @@ procdump(void) printf("\n"); } } + +int +get_nproc(void) +{ + int n = 0; + struct proc *p; + + for(int i = 0; i < NPROC; i++) { + p = &proc[i]; + acquire(&p->lock); + if(p->state != UNUSED) + n++; + release(&p->lock); + } + + return n; +} + +// lab pagetable: report which pages have been accessed (r/w) +// according to PTE_A and store it in a bit mask (3rd param) +int +pgaccess(uint64 base, int len, uint64 mask_addr) +{ + struct proc *p = myproc(); + pagetable_t pgtbl = p->pagetable; + pte_t *pte; + int mask = 0; + + // iterater thru pages + for(int i = 0; i < len; i++) { + pte = walk(pgtbl, base + i * PGSIZE, 0); + if(*pte & PTE_A) { + *pte &= (~PTE_A); // clear PTE_A to avoid setting it forever + mask |= (1L << i); + } + } + + // now copyout the mask to user memory + return copyout(pgtbl, mask_addr, (char *)&mask, sizeof(mask)); +} diff --git a/kernel/proc.h b/kernel/proc.h index d021857..a195b02 100644 --- a/kernel/proc.h +++ b/kernel/proc.h @@ -91,6 +91,7 @@ struct proc { int killed; // If non-zero, have been killed int xstate; // Exit status to be returned to parent's wait int pid; // Process ID + int trace_mask; // SYS_trace mask (1 << SYS_xxx) // wait_lock must be held when using this: struct proc *parent; // Parent process @@ -100,8 +101,14 @@ struct proc { uint64 sz; // Size of process memory (bytes) pagetable_t pagetable; // User page table struct trapframe *trapframe; // data page for trampoline.S + struct usyscall *usyscall; // data page for usyscall struct context context; // swtch() here to run process struct file *ofile[NOFILE]; // Open files struct inode *cwd; // Current directory char name[16]; // Process name (debugging) + int alarm_interval; // sigalarm syscall interval + uint64 alarm_handler; // sigalarm syscall handler + int alarm_tickspassed; // record how many ticks passed since last sigalarm handler call + int alarm_caninvoke; // prevent re-entrant calls to handler + struct trapframe *atpfm; // trapframe to resume after handling, must hold p->lock }; diff --git a/kernel/riscv.h b/kernel/riscv.h index 20a01db..7d6eb6e 100644 --- a/kernel/riscv.h +++ b/kernel/riscv.h @@ -327,6 +327,15 @@ sfence_vma() asm volatile("sfence.vma zero, zero"); } +// read the frame pointer of currently executing func +static inline uint64 +r_fp() +{ + uint64 x; + asm volatile("mv %0, s0" : "=r" (x) ); + return x; +} + typedef uint64 pte_t; typedef uint64 *pagetable_t; // 512 PTEs @@ -343,6 +352,8 @@ typedef uint64 *pagetable_t; // 512 PTEs #define PTE_W (1L << 2) #define PTE_X (1L << 3) #define PTE_U (1L << 4) // user can access +#define PTE_A (1L << 6) // riscv access bit +#define PTE_C (1L << 8) // RSW low bit, use it to mark whether a page is COW // shift a physical address to the right place for a PTE. #define PA2PTE(pa) ((((uint64)pa) >> 12) << 10) diff --git a/kernel/syscall.c b/kernel/syscall.c index beea0ef..172c5ea 100644 --- a/kernel/syscall.c +++ b/kernel/syscall.c @@ -101,6 +101,17 @@ extern uint64 sys_unlink(void); extern uint64 sys_link(void); extern uint64 sys_mkdir(void); extern uint64 sys_close(void); +extern uint64 sys_trace(void); +extern uint64 sys_sysinfo(void); + +#ifdef LAB_NET +extern uint64 sys_connect(void); +#endif +#ifdef LAB_PGTBL +extern uint64 sys_pgaccess(void); +#endif +extern uint64 sys_sigalarm(void); +extern uint64 sys_sigreturn(void); #ifdef LAB_NET extern uint64 sys_connect(void); @@ -139,8 +150,46 @@ static uint64 (*syscalls[])(void) = { #ifdef LAB_PGTBL [SYS_pgaccess] sys_pgaccess, #endif +[SYS_trace] sys_trace, +[SYS_sysinfo] sys_sysinfo, +[SYS_sigalarm] sys_sigalarm, +[SYS_sigreturn] sys_sigreturn, }; +// syscall name maps for SYS_trace: +static char *syscall_names[] = { +[SYS_fork] "fork", +[SYS_exit] "exit", +[SYS_wait] "wait", +[SYS_pipe] "pipe", +[SYS_read] "read", +[SYS_kill] "kill", +[SYS_exec] "exec", +[SYS_fstat] "fstat", +[SYS_chdir] "chdir", +[SYS_dup] "dup", +[SYS_getpid] "getpid", +[SYS_sbrk] "sbrk", +[SYS_sleep] "sleep", +[SYS_uptime] "uptime", +[SYS_open] "open", +[SYS_write] "write", +[SYS_mknod] "mknod", +[SYS_unlink] "unlink", +[SYS_link] "link", +[SYS_mkdir] "mkdir", +[SYS_close] "close", +#ifdef LAB_NET +[SYS_connect] "connect", +#endif +#ifdef LAB_PGTBL +[SYS_pgaccess] "pgaccess", +#endif +[SYS_trace] "trace", +[SYS_sysinfo] "sysinfo", +[SYS_sigalarm] "sigalarm", +[SYS_sigreturn] "sigreturn", +}; void @@ -154,9 +203,17 @@ syscall(void) // Use num to lookup the system call function for num, call it, // and store its return value in p->trapframe->a0 p->trapframe->a0 = syscalls[num](); + + // SYS_trace: match all the syscalls which number < mask asked + // p->trace_mask == 1 << SYS_xxx + if(p->trace_mask >> num) { + printf("%d: syscall %s -> %d\n", p->pid, syscall_names[num], p->trapframe->a0); + } + } else { printf("%d %s: unknown sys call %d\n", p->pid, p->name, num); p->trapframe->a0 = -1; } } + diff --git a/kernel/sysinfo.c b/kernel/sysinfo.c new file mode 100644 index 0000000..c66324d --- /dev/null +++ b/kernel/sysinfo.c @@ -0,0 +1,24 @@ +#include "types.h" +#include "riscv.h" +#include "param.h" +#include "spinlock.h" +#include "defs.h" +#include "sysinfo.h" +#include "proc.h" + +// Get current system info +// addr is a user virtual address, pointing to a struct sysinfo. +int +sys_info(uint64 addr) { + struct proc *p = myproc(); + struct sysinfo info; + + // Fill nums into the sysinfo struct + info.freemem = get_freemem(); + info.nproc = get_nproc(); + + if(copyout(p->pagetable, addr, (char *)&info, sizeof(info)) < 0) + return -1; + return 0; +} + diff --git a/kernel/sysinfo.h b/kernel/sysinfo.h new file mode 100644 index 0000000..fb878e6 --- /dev/null +++ b/kernel/sysinfo.h @@ -0,0 +1,4 @@ +struct sysinfo { + uint64 freemem; // amount of free memory (bytes) + uint64 nproc; // number of process +}; diff --git a/kernel/sysproc.c b/kernel/sysproc.c index 3b4d5bd..715a511 100644 --- a/kernel/sysproc.c +++ b/kernel/sysproc.c @@ -1,7 +1,7 @@ #include "types.h" #include "riscv.h" -#include "defs.h" #include "param.h" +#include "defs.h" #include "memlayout.h" #include "spinlock.h" #include "proc.h" @@ -54,9 +54,8 @@ sys_sleep(void) int n; uint ticks0; + argint(0, &n); - if(n < 0) - n = 0; acquire(&tickslock); ticks0 = ticks; while(ticks - ticks0 < n){ @@ -66,10 +65,29 @@ sys_sleep(void) } sleep(&ticks, &tickslock); } + + // backtrace(); + release(&tickslock); return 0; } + +#ifdef LAB_PGTBL +int +sys_pgaccess(void) +{ + uint64 base, mask; + int len; + + + argaddr(0, &base); + argint(1, &len); + argaddr(2, &mask); + return pgaccess(base, len, mask); +} +#endif + uint64 sys_kill(void) { @@ -91,3 +109,44 @@ sys_uptime(void) release(&tickslock); return xticks; } + +uint64 +sys_trace(void) +{ + argint(0, &myproc()->trace_mask); + + return -(myproc()->trace_mask <= 1); +} + +uint64 +sys_sysinfo(void) +{ + uint64 si; // user pointer to struct sysinfo + + argaddr(0, &si); + return sys_info(si); +} + +uint64 +sys_sigalarm(void) +{ + struct proc *p = myproc(); + uint64 handler; + + argint(0, &p->alarm_interval); + argaddr(1, &handler); + p->alarm_handler = handler; + + return 0; +} + +uint64 sys_sigreturn(void) +{ + struct proc *p = myproc(); + // retore saved trapframe to resume + memmove(p->trapframe, p->atpfm, sizeof(struct trapframe)); + p->alarm_tickspassed = 0; + p->alarm_caninvoke = 1; + // make sure return the original a0 in trapframe to pass test3 + return p->trapframe->a0; +} diff --git a/kernel/trap.c b/kernel/trap.c index 5332dda..7cc69b1 100644 --- a/kernel/trap.c +++ b/kernel/trap.c @@ -6,6 +6,12 @@ #include "proc.h" #include "defs.h" +/* + * Always remember that RISC-V disables interrupts when it starts to take a trap, + * so there's no need to call intr_off() at the beginning of trap handling. + * Reference: xv6-riscv-book 4.5 + */ + struct spinlock tickslock; uint ticks; @@ -67,11 +73,18 @@ usertrap(void) syscall(); } else if((which_dev = devintr()) != 0){ // ok + } else if(r_scause() == 13 || r_scause() == 15){ + // deal with page fault + uint64 va = r_stval(); + if(cow_handler(p->pagetable, va) < 0) + goto err; } else { printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid); printf(" sepc=%p stval=%p\n", r_sepc(), r_stval()); + err: + printf("killing the process...\n"); setkilled(p); } @@ -79,9 +92,22 @@ usertrap(void) exit(-1); - // give up the CPU if this is a timer interrupt. - if(which_dev == 2) + if(which_dev == 2){ + // timer interrupt + if(p->alarm_interval > 0 && p->alarm_caninvoke){ + // record sigalarm + p->alarm_tickspassed++; + if(p->alarm_tickspassed == p->alarm_interval){ + // store original trapframe in p->atpfm + memmove(p->atpfm, p->trapframe, sizeof(struct trapframe)); + p->alarm_tickspassed = 0; + p->alarm_caninvoke = 0; + p->trapframe->epc = p->alarm_handler; + } + } + // give up the CPU. yield(); + } usertrapret(); } diff --git a/kernel/vm.c b/kernel/vm.c index 7119242..be7d042 100644 --- a/kernel/vm.c +++ b/kernel/vm.c @@ -320,20 +320,26 @@ uvmcopy(pagetable_t old, pagetable_t new, uint64 sz) pte_t *pte; uint64 pa, i; uint flags; - char *mem; + // char *mem; for(i = 0; i < sz; i += PGSIZE){ if((pte = walk(old, i, 0)) == 0) panic("uvmcopy: pte should exist"); if((*pte & PTE_V) == 0) panic("uvmcopy: page not present"); - pa = PTE2PA(*pte); - flags = PTE_FLAGS(*pte); + // do not do the actual copy, just increase the refcnt and mark pages readonly COW + /* if((mem = kalloc()) == 0) goto err; memmove(mem, (char*)pa, PGSIZE); - if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){ - kfree(mem); + */ + *pte &= ~PTE_W; + *pte |= PTE_C; + pa = PTE2PA(*pte); + refcnt_inc(pa); + flags = PTE_FLAGS(*pte); + if(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){ + // kfree(mem); goto err; } } @@ -364,22 +370,21 @@ int copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len) { uint64 n, va0, pa0; - pte_t *pte; + // pte_t *pte; while(len > 0){ va0 = PGROUNDDOWN(dstva); - if (va0 >= MAXVA) - return -1; - if((pte = walk(pagetable, va0, 0)) == 0) { - // printf("copyout: pte should exist 0x%x %d\n", dstva, len); - return -1; - } - - // forbid copyout over read-only user text pages. - if((*pte & PTE_W) == 0) + if(cow_handler(pagetable, va0) < 0) return -1; + /* + pte = walk(pagetable, va0, 0); + if(pte == 0 || (*pte & PTE_V) == 0 || (*pte & PTE_U) == 0 || + (*pte & PTE_W) == 0) + return -1; + pa0 = PTE2PA(*pte); + */ pa0 = walkaddr(pagetable, va0); if(pa0 == 0) return -1; @@ -463,5 +468,29 @@ copyinstr(pagetable_t pagetable, char *dst, uint64 srcva, uint64 max) } } +static void +walkprint(pagetable_t pgtbl, int level) +{ + for(int i = 0; i < 512; i++){ + pte_t pte = pgtbl[i]; + if(pte & PTE_V){ + for(int j = 0; j < level; j++){ + printf(" .."); + } + printf("%d: pte %p pa %p\n", i, pte, PTE2PA(pte)); + if((pte & (PTE_R|PTE_W|PTE_X)) == 0){ + // this PTE points to a lower-level page table. + walkprint((pagetable_t)PTE2PA(pte), level+1); + } + } + } +} +// Print the contents of a page table +void +vmprint(pagetable_t pgtbl) +{ + printf("page table %p\n", pgtbl); + walkprint(pgtbl, 1); +} diff --git a/time.txt b/time.txt new file mode 100644 index 0000000..00750ed --- /dev/null +++ b/time.txt @@ -0,0 +1 @@ +3 diff --git a/user/alarmtest.c b/user/alarmtest.c new file mode 100644 index 0000000..b8d85f7 --- /dev/null +++ b/user/alarmtest.c @@ -0,0 +1,193 @@ +// +// test program for the alarm lab. +// you can modify this file for testing, +// but please make sure your kernel +// modifications pass the original +// versions of these tests. +// + +#include "kernel/param.h" +#include "kernel/types.h" +#include "kernel/stat.h" +#include "kernel/riscv.h" +#include "user/user.h" + +void test0(); +void test1(); +void test2(); +void test3(); +void periodic(); +void slow_handler(); +void dummy_handler(); + +int +main(int argc, char *argv[]) +{ + test0(); + test1(); + test2(); + test3(); + exit(0); +} + +volatile static int count; + +void +periodic() +{ + count = count + 1; + printf("alarm!\n"); + sigreturn(); +} + +// tests whether the kernel calls +// the alarm handler even a single time. +void +test0() +{ + int i; + printf("test0 start\n"); + count = 0; + sigalarm(2, periodic); + for(i = 0; i < 1000*500000; i++){ + if((i % 1000000) == 0) + write(2, ".", 1); + if(count > 0) + break; + } + sigalarm(0, 0); + if(count > 0){ + printf("test0 passed\n"); + } else { + printf("\ntest0 failed: the kernel never called the alarm handler\n"); + } +} + +void __attribute__ ((noinline)) foo(int i, int *j) { + if((i % 2500000) == 0) { + write(2, ".", 1); + } + *j += 1; +} + +// +// tests that the kernel calls the handler multiple times. +// +// tests that, when the handler returns, it returns to +// the point in the program where the timer interrupt +// occurred, with all registers holding the same values they +// held when the interrupt occurred. +// +void +test1() +{ + int i; + int j; + + printf("test1 start\n"); + count = 0; + j = 0; + sigalarm(2, periodic); + for(i = 0; i < 500000000; i++){ + if(count >= 10) + break; + foo(i, &j); + } + if(count < 10){ + printf("\ntest1 failed: too few calls to the handler\n"); + } else if(i != j){ + // the loop should have called foo() i times, and foo() should + // have incremented j once per call, so j should equal i. + // once possible source of errors is that the handler may + // return somewhere other than where the timer interrupt + // occurred; another is that that registers may not be + // restored correctly, causing i or j or the address ofj + // to get an incorrect value. + printf("\ntest1 failed: foo() executed fewer times than it was called\n"); + } else { + printf("test1 passed\n"); + } +} + +// +// tests that kernel does not allow reentrant alarm calls. +void +test2() +{ + int i; + int pid; + int status; + + printf("test2 start\n"); + if ((pid = fork()) < 0) { + printf("test2: fork failed\n"); + } + if (pid == 0) { + count = 0; + sigalarm(2, slow_handler); + for(i = 0; i < 1000*500000; i++){ + if((i % 1000000) == 0) + write(2, ".", 1); + if(count > 0) + break; + } + if (count == 0) { + printf("\ntest2 failed: alarm not called\n"); + exit(1); + } + exit(0); + } + wait(&status); + if (status == 0) { + printf("test2 passed\n"); + } +} + +void +slow_handler() +{ + count++; + printf("alarm!\n"); + if (count > 1) { + printf("test2 failed: alarm handler called more than once\n"); + exit(1); + } + for (int i = 0; i < 1000*500000; i++) { + asm volatile("nop"); // avoid compiler optimizing away loop + } + sigalarm(0, 0); + sigreturn(); +} + +// +// dummy alarm handler; after running immediately uninstall +// itself and finish signal handling +void +dummy_handler() +{ + sigalarm(0, 0); + sigreturn(); +} + +// +// tests that the return from sys_sigreturn() does not +// modify the a0 register +void +test3() +{ + uint64 a0; + + sigalarm(1, dummy_handler); + printf("test3 start\n"); + + asm volatile("lui a5, 0"); + asm volatile("addi a0, a5, 0xac" : : : "a0"); + for(int i = 0; i < 500000000; i++) + ; + asm volatile("mv %0, a0" : "=r" (a0) ); + + if(a0 != 0xac) + printf("test3 failed: register a0 changed\n"); + else + printf("test3 passed\n"); +} diff --git a/user/bttest.c b/user/bttest.c new file mode 100644 index 0000000..05405f9 --- /dev/null +++ b/user/bttest.c @@ -0,0 +1,10 @@ +#include "kernel/types.h" +#include "kernel/stat.h" +#include "user/user.h" + +int +main(int argc, char *argv[]) +{ + sleep(1); + exit(0); +} diff --git a/user/call.c b/user/call.c new file mode 100644 index 0000000..f725dcb --- /dev/null +++ b/user/call.c @@ -0,0 +1,17 @@ +#include "kernel/param.h" +#include "kernel/types.h" +#include "kernel/stat.h" +#include "user/user.h" + +int g(int x) { + return x+3; +} + +int f(int x) { + return g(x); +} + +void main(void) { + printf("%d %d\n", f(8)+1, 13); + exit(0); +} diff --git a/user/cowtest.c b/user/cowtest.c new file mode 100644 index 0000000..29b918f --- /dev/null +++ b/user/cowtest.c @@ -0,0 +1,197 @@ +// +// tests for copy-on-write fork() assignment. +// + +#include "kernel/types.h" +#include "kernel/memlayout.h" +#include "user/user.h" + +// allocate more than half of physical memory, +// then fork. this will fail in the default +// kernel, which does not support copy-on-write. +void +simpletest() +{ + uint64 phys_size = PHYSTOP - KERNBASE; + int sz = (phys_size / 3) * 2; + + printf("simple: "); + + char *p = sbrk(sz); + if(p == (char*)0xffffffffffffffffL){ + printf("sbrk(%d) failed\n", sz); + exit(-1); + } + + for(char *q = p; q < p + sz; q += 4096){ + *(int*)q = getpid(); + } + + int pid = fork(); + if(pid < 0){ + printf("fork() failed\n"); + exit(-1); + } + + if(pid == 0) + exit(0); + + wait(0); + + if(sbrk(-sz) == (char*)0xffffffffffffffffL){ + printf("sbrk(-%d) failed\n", sz); + exit(-1); + } + + printf("ok\n"); +} + +// three processes all write COW memory. +// this causes more than half of physical memory +// to be allocated, so it also checks whether +// copied pages are freed. +void +threetest() +{ + uint64 phys_size = PHYSTOP - KERNBASE; + int sz = phys_size / 4; + int pid1, pid2; + + printf("three: "); + + char *p = sbrk(sz); + if(p == (char*)0xffffffffffffffffL){ + printf("sbrk(%d) failed\n", sz); + exit(-1); + } + + pid1 = fork(); + if(pid1 < 0){ + printf("fork failed\n"); + exit(-1); + } + if(pid1 == 0){ + pid2 = fork(); + if(pid2 < 0){ + printf("fork failed"); + exit(-1); + } + if(pid2 == 0){ + for(char *q = p; q < p + (sz/5)*4; q += 4096){ + *(int*)q = getpid(); + } + for(char *q = p; q < p + (sz/5)*4; q += 4096){ + if(*(int*)q != getpid()){ + printf("wrong content\n"); + exit(-1); + } + } + exit(-1); + } + for(char *q = p; q < p + (sz/2); q += 4096){ + *(int*)q = 9999; + } + exit(0); + } + + for(char *q = p; q < p + sz; q += 4096){ + *(int*)q = getpid(); + } + + wait(0); + + sleep(1); + + for(char *q = p; q < p + sz; q += 4096){ + if(*(int*)q != getpid()){ + printf("wrong content\n"); + exit(-1); + } + } + + if(sbrk(-sz) == (char*)0xffffffffffffffffL){ + printf("sbrk(-%d) failed\n", sz); + exit(-1); + } + + printf("ok\n"); +} + +char junk1[4096]; +int fds[2]; +char junk2[4096]; +char buf[4096]; +char junk3[4096]; + +// test whether copyout() simulates COW faults. +void +filetest() +{ + printf("file: "); + + buf[0] = 99; + + for(int i = 0; i < 4; i++){ + if(pipe(fds) != 0){ + printf("pipe() failed\n"); + exit(-1); + } + int pid = fork(); + if(pid < 0){ + printf("fork failed\n"); + exit(-1); + } + if(pid == 0){ + sleep(1); + if(read(fds[0], buf, sizeof(i)) != sizeof(i)){ + printf("error: read failed\n"); + exit(1); + } + sleep(1); + int j = *(int*)buf; + if(j != i){ + printf("error: read the wrong value\n"); + exit(1); + } + exit(0); + } + if(write(fds[1], &i, sizeof(i)) != sizeof(i)){ + printf("error: write failed\n"); + exit(-1); + } + } + + int xstatus = 0; + for(int i = 0; i < 4; i++) { + wait(&xstatus); + if(xstatus != 0) { + exit(1); + } + } + + if(buf[0] != 99){ + printf("error: child overwrote parent\n"); + exit(1); + } + + printf("ok\n"); +} + +int +main(int argc, char *argv[]) +{ + simpletest(); + + // check that the first simpletest() freed the physical memory. + simpletest(); + + threetest(); + threetest(); + threetest(); + + filetest(); + + printf("ALL COW TESTS PASSED\n"); + + exit(0); +} diff --git a/user/find.c b/user/find.c new file mode 100644 index 0000000..e185e9d --- /dev/null +++ b/user/find.c @@ -0,0 +1,84 @@ +#include "kernel/types.h" + +#include "kernel/fcntl.h" +#include "kernel/fs.h" +#include "kernel/stat.h" +#include "user/user.h" + +char* +fmtname(char* path) +{ + char* p; + + // Find first character after last slash. + for (p = path + strlen(path); p >= path && *p != '/'; p--) + ; + p++; + return p; +} + +void +find(char* root_path, char* filename) +{ + static char buf[512]; + char* p; + int fd; + struct dirent de; + struct stat st; + + if ((fd = open(root_path, O_RDONLY)) < 0) { + fprintf(2, "find: cannot open %s\n", root_path); + return; + } + if (fstat(fd, &st) < 0) { + fprintf(2, "find: cannot stat %s\n", root_path); + close(fd); + return; + } + + switch (st.type) { + case T_FILE: + if (!strcmp(fmtname(root_path), filename)) { + printf("%s\n", root_path); + } + break; + case T_DIR: + if (strlen(root_path) + 1 + DIRSIZ + 1 > sizeof(buf)) { + printf("find: path too long\n"); + break; + } + + strcpy(buf, root_path); + + p = buf + strlen(buf); + *p++ = '/'; + while (read(fd, &de, sizeof(de)) == sizeof(de)) { + if (de.inum == 0) + continue; + memmove(p, de.name, DIRSIZ); + p[DIRSIZ] = '\0'; + + // printf("i'm finding %s!\n", fmtname(buf)); + + if (!strcmp(fmtname(buf), ".") || !strcmp(fmtname(buf), "..")) { + continue; + } + + find(buf, filename); + } + } + close(fd); +} + +int +main(int argc, char* argv[]) +{ + if (argc < 3) { + fprintf(2, "usage: find [root_path] filename...\n"); + exit(1); + } + + for (int i = 2; i < argc; i++) { + find(argv[1], argv[i]); + } +} diff --git a/user/pgtbltest.c b/user/pgtbltest.c new file mode 100644 index 0000000..bce158a --- /dev/null +++ b/user/pgtbltest.c @@ -0,0 +1,70 @@ +#include "kernel/param.h" +#include "kernel/fcntl.h" +#include "kernel/types.h" +#include "kernel/riscv.h" +#include "user/user.h" + +void ugetpid_test(); +void pgaccess_test(); + +int +main(int argc, char *argv[]) +{ + ugetpid_test(); + pgaccess_test(); + printf("pgtbltest: all tests succeeded\n"); + exit(0); +} + +char *testname = "???"; + +void +err(char *why) +{ + printf("pgtbltest: %s failed: %s, pid=%d\n", testname, why, getpid()); + exit(1); +} + +void +ugetpid_test() +{ + int i; + + printf("ugetpid_test starting\n"); + testname = "ugetpid_test"; + + for (i = 0; i < 64; i++) { + int ret = fork(); + if (ret != 0) { + wait(&ret); + if (ret != 0) + exit(1); + continue; + } + if (getpid() != ugetpid()) + err("missmatched PID"); + exit(0); + } + printf("ugetpid_test: OK\n"); +} + +void +pgaccess_test() +{ + char *buf; + unsigned int abits; + printf("pgaccess_test starting\n"); + testname = "pgaccess_test"; + buf = malloc(32 * PGSIZE); + if (pgaccess(buf, 32, &abits) < 0) + err("pgaccess failed"); + buf[PGSIZE * 1] += 1; + buf[PGSIZE * 2] += 1; + buf[PGSIZE * 30] += 1; + if (pgaccess(buf, 32, &abits) < 0) + err("pgaccess failed"); + if (abits != ((1 << 1) | (1 << 2) | (1 << 30))) + err("incorrect access bits set"); + free(buf); + printf("pgaccess_test: OK\n"); +} diff --git a/user/pingpong.c b/user/pingpong.c index 6ed12e7..7b03a76 100644 --- a/user/pingpong.c +++ b/user/pingpong.c @@ -1,52 +1,44 @@ #include "kernel/types.h" -#include "kernel/stat.h" #include "user/user.h" -#define N 5 -char buf[N]; +int +main(int argc, char* argv[]) +{ + int p[2]; -void -pong(int *parent_to_child, int *child_to_parent) { - if (read(parent_to_child[0], buf, N) < 0) { - printf("read failed\n"); - } - printf("%d: received %s\n", getpid(), buf); - if (write(child_to_parent[1], "pong", 4) != 4) { - printf("write failed\n"); + if (argc > 1) { + fprintf(2, "usage: pingpong\n"); + exit(1); } -} -void -ping(int *parent_to_child, int *child_to_parent) { - - if (write(parent_to_child[1], "ping", 4) != 4) { - printf("write failed\n"); - } - if (read(child_to_parent[0], buf, N) < 0) { - printf("read failed\n"); - } - printf("%d: received %s\n", getpid(), buf); -} + pipe(p); -int -main(int argc, char *argv[]) -{ - int parent_to_child[2]; - int child_to_parent[2]; + int pid = fork(); - int pid; - - if (pipe(parent_to_child) < 0 || pipe(child_to_parent) < 0) { - printf("pipe failed\n"); - } - if ((pid = fork()) < 0) { - printf("fork failed\n"); - } if (pid == 0) { - pong(parent_to_child, child_to_parent); - } else { - ping(parent_to_child, child_to_parent); + short n; + read(p[0], &n, sizeof(n)); + if (n == 42) { + fprintf(1, "%d: received ping\n", getpid()); + } + n++; + write(p[1], &n, sizeof(n)); + close(p[0]); + close(p[1]); + exit(0); + } + + short n = 42; + + write(p[1], &n, sizeof(n)); + read(p[0], &n, sizeof(n)); + if (n == 43) { + fprintf(1, "%d: received pong\n", getpid()); } - + close(p[0]); + close(p[1]); + + wait(0); + exit(0); } diff --git a/user/primes.c b/user/primes.c new file mode 100644 index 0000000..b359524 --- /dev/null +++ b/user/primes.c @@ -0,0 +1,74 @@ +#include "kernel/types.h" +#include "user/user.h" + +#define MAX 36 +#define FIRST_PRIME 2 + +int +generate_natural(); // -> out_fd +int +prime_filter(int in_fd, int prime); // -> out_fd + +int +main(int argc, char* argv[]) +{ + int prime; + + int in = generate_natural(); + while (read(in, &prime, sizeof(int))) { + // printf("prime %d: in_fd: %d\n", prime, in); // debug + printf("prime %d\n", prime); + in = prime_filter(in, prime); + } + + close(in); + + exit(0); +} + +int +generate_natural() +{ + int out_pipe[2]; + + pipe(out_pipe); + + if (!fork()) { + for (int i = FIRST_PRIME; i < MAX; i++) { + write(out_pipe[1], &i, sizeof(int)); + } + close(out_pipe[1]); + + exit(0); + } + + close(out_pipe[1]); + + return out_pipe[0]; +} + +int +prime_filter(int in_fd, int prime) +{ + int num; + int out_pipe[2]; + + pipe(out_pipe); + + if (!fork()) { + while (read(in_fd, &num, sizeof(int))) { + if (num % prime) { + write(out_pipe[1], &num, sizeof(int)); + } + } + close(in_fd); + close(out_pipe[1]); + + exit(0); + } + + close(in_fd); + close(out_pipe[1]); + + return out_pipe[0]; +} @@ -165,6 +165,9 @@ main(void) fprintf(2, "cannot cd %s\n", buf+3); continue; } + if(buf[0] == 'e' && buf[1] == 'x' && buf[2] == 'i' && buf[3] == 't'){ + exit(0); + } if(fork1() == 0) runcmd(parsecmd(buf)); wait(0); diff --git a/user/sleep.c b/user/sleep.c new file mode 100644 index 0000000..961f558 --- /dev/null +++ b/user/sleep.c @@ -0,0 +1,22 @@ +#include "kernel/types.h" +#include "user/user.h" + +int +main(int argc, char* argv[]) +{ + uint sec = 0; + + if (argc <= 1) { + fprintf(2, "usage: sleep [time (ticks)]\n"); + exit(1); + } + sec = atoi(argv[1]); + + sleep(sec); + + if (argc <= 2) { + exit(0); + } + + exit(0); +} diff --git a/user/sysinfotest.c b/user/sysinfotest.c new file mode 100644 index 0000000..8a648a6 --- /dev/null +++ b/user/sysinfotest.c @@ -0,0 +1,153 @@ +#include "kernel/types.h" +#include "kernel/riscv.h" +#include "kernel/sysinfo.h" +#include "user/user.h" + + +void +sinfo(struct sysinfo *info) { + if (sysinfo(info) < 0) { + printf("FAIL: sysinfo failed"); + exit(1); + } +} + +// +// use sbrk() to count how many free physical memory pages there are. +// +int +countfree() +{ + uint64 sz0 = (uint64)sbrk(0); + struct sysinfo info; + int n = 0; + + while(1){ + if((uint64)sbrk(PGSIZE) == 0xffffffffffffffff){ + break; + } + n += PGSIZE; + } + sinfo(&info); + if (info.freemem != 0) { + printf("FAIL: there is no free mem, but sysinfo.freemem=%d\n", + info.freemem); + exit(1); + } + sbrk(-((uint64)sbrk(0) - sz0)); + return n; +} + +void +testmem() { + struct sysinfo info; + uint64 n = countfree(); + + sinfo(&info); + + if (info.freemem!= n) { + printf("FAIL: free mem %d (bytes) instead of %d\n", info.freemem, n); + exit(1); + } + + if((uint64)sbrk(PGSIZE) == 0xffffffffffffffff){ + printf("sbrk failed"); + exit(1); + } + + sinfo(&info); + + if (info.freemem != n-PGSIZE) { + printf("FAIL: free mem %d (bytes) instead of %d\n", n-PGSIZE, info.freemem); + exit(1); + } + + if((uint64)sbrk(-PGSIZE) == 0xffffffffffffffff){ + printf("sbrk failed"); + exit(1); + } + + sinfo(&info); + + if (info.freemem != n) { + printf("FAIL: free mem %d (bytes) instead of %d\n", n, info.freemem); + exit(1); + } +} + +void +testcall() { + struct sysinfo info; + + if (sysinfo(&info) < 0) { + printf("FAIL: sysinfo failed\n"); + exit(1); + } + + if (sysinfo((struct sysinfo *) 0xeaeb0b5b00002f5e) != 0xffffffffffffffff) { + printf("FAIL: sysinfo succeeded with bad argument\n"); + exit(1); + } +} + +void testproc() { + struct sysinfo info; + uint64 nproc; + int status; + int pid; + + sinfo(&info); + nproc = info.nproc; + + pid = fork(); + if(pid < 0){ + printf("sysinfotest: fork failed\n"); + exit(1); + } + if(pid == 0){ + sinfo(&info); + if(info.nproc != nproc+1) { + printf("sysinfotest: FAIL nproc is %d instead of %d\n", info.nproc, nproc+1); + exit(1); + } + exit(0); + } + wait(&status); + sinfo(&info); + if(info.nproc != nproc) { + printf("sysinfotest: FAIL nproc is %d instead of %d\n", info.nproc, nproc); + exit(1); + } +} + +void testbad() { + int pid = fork(); + int xstatus; + + if(pid < 0){ + printf("sysinfotest: fork failed\n"); + exit(1); + } + if(pid == 0){ + sinfo(0x0); + exit(0); + } + wait(&xstatus); + if(xstatus == -1) // kernel killed child? + exit(0); + else { + printf("sysinfotest: testbad succeeded %d\n", xstatus); + exit(xstatus); + } +} + +int +main(int argc, char *argv[]) +{ + printf("sysinfotest: start\n"); + testcall(); + testmem(); + testproc(); + printf("sysinfotest: OK\n"); + exit(0); +} diff --git a/user/trace.c b/user/trace.c new file mode 100644 index 0000000..dd77760 --- /dev/null +++ b/user/trace.c @@ -0,0 +1,27 @@ +#include "kernel/param.h" +#include "kernel/types.h" +#include "kernel/stat.h" +#include "user/user.h" + +int +main(int argc, char *argv[]) +{ + int i; + char *nargv[MAXARG]; + + if(argc < 3 || (argv[1][0] < '0' || argv[1][0] > '9')){ + fprintf(2, "Usage: %s mask command\n", argv[0]); + exit(1); + } + + if (trace(atoi(argv[1])) < 0) { + fprintf(2, "%s: trace failed\n", argv[0]); + exit(1); + } + + for(i = 2; i < argc && i < MAXARG; i++){ + nargv[i-2] = argv[i]; + } + exec(nargv[0], nargv); + exit(0); +} diff --git a/user/ulib.c b/user/ulib.c index c7b66c4..871adc9 100644 --- a/user/ulib.c +++ b/user/ulib.c @@ -1,8 +1,13 @@ #include "kernel/types.h" #include "kernel/stat.h" #include "kernel/fcntl.h" +#ifdef LAB_PGTBL +#include "kernel/riscv.h" +#include "kernel/memlayout.h" +#endif #include "user/user.h" + // // wrapper so that it's OK if main() does not call exit(). // @@ -145,3 +150,12 @@ memcpy(void *dst, const void *src, uint n) { return memmove(dst, src, n); } + +#ifdef LAB_PGTBL +int +ugetpid(void) +{ + struct usyscall *u = (struct usyscall *)USYSCALL; + return u->pid; +} +#endif diff --git a/user/user.h b/user/user.h index 16cf173..34591fd 100644 --- a/user/user.h +++ b/user/user.h @@ -1,4 +1,5 @@ struct stat; +struct sysinfo; // system calls int fork(void); @@ -30,6 +31,10 @@ int pgaccess(void *base, int len, void *mask); // usyscall region int ugetpid(void); #endif +int trace(int); +int sysinfo(struct sysinfo*); +int sigalarm(int ticks, void (*handler)()); +int sigreturn(void); // ulib.c int stat(const char*, struct stat*); diff --git a/user/usys.pl b/user/usys.pl index 6453fe9..33af0ad 100755 --- a/user/usys.pl +++ b/user/usys.pl @@ -36,5 +36,9 @@ entry("getpid"); entry("sbrk"); entry("sleep"); entry("uptime"); +entry("trace"); +entry("sysinfo"); entry("connect"); entry("pgaccess"); +entry("sigalarm"); +entry("sigreturn"); diff --git a/user/xargs.c b/user/xargs.c new file mode 100644 index 0000000..b5b9bee --- /dev/null +++ b/user/xargs.c @@ -0,0 +1,60 @@ +#include "kernel/types.h" + +#include "kernel/param.h" +#include "kernel/stat.h" +#include "user/user.h" + +#define is_blank(chr) (chr == ' ' || chr == '\t') + +int +main(int argc, char* argv[]) +{ + char buf[2048], ch; + char* p = buf; + char* v[MAXARG]; + int c; + int blanks = 0; + int offset = 0; + + if (argc <= 1) { + fprintf(2, "usage: xargs <command> [argv...]\n"); + exit(1); + } + + for (c = 1; c < argc; c++) { + v[c - 1] = argv[c]; + } + --c; + + while (read(0, &ch, 1) > 0) { + if (is_blank(ch)) { + blanks++; + continue; + } + + if (blanks) { + buf[offset++] = 0; + + v[c++] = p; + p = buf + offset; + + blanks = 0; + } + + if (ch != '\n') { + buf[offset++] = ch; + } else { + v[c++] = p; + p = buf + offset; + + if (!fork()) { + exit(exec(v[0], v)); + } + wait(0); + + c = argc - 1; + } + } + + exit(0); +} diff --git a/user/xargstest.sh b/user/xargstest.sh new file mode 100644 index 0000000..4362589 --- /dev/null +++ b/user/xargstest.sh @@ -0,0 +1,6 @@ +mkdir a +echo hello > a/b +mkdir c +echo hello > c/b +echo hello > b +find . b | xargs grep hello |