cksystemsteaching / selfie Goto Github PK

An educational software system of a tiny self-compiling C compiler, a tiny self-executing RISC-V emulator, and a tiny self-hosting RISC-V hypervisor.

Home Page: http://selfie.cs.uni-salzburg.at

License: BSD 2-Clause "Simplified" License

C 39.03% Assembly 0.31% Makefile 1.04% Dockerfile 0.22% Python 12.06% Jupyter Notebook 46.92% OpenQASM 0.40% Shell 0.02% Nix 0.01%

teaching computer-science compiler emulator virtual-machine symbolic-execution-engine

selfie's Introduction

Selfie

Selfie is a project of the Computational Systems Group at the Department of Computer Sciences of the University of Salzburg in Austria.

The Selfie Project provides an educational platform for teaching undergraduate and graduate students the design and implementation of programming languages and runtime systems. The focus is on the construction of compilers, libraries, operating systems, and virtual machine monitors. The common theme is to identify and resolve self-reference in systems code which is seen as the key challenge when teaching systems engineering, hence the name.

Selfie is a self-contained 64-bit, 12KLOC C implementation of:

a self-compiling compiler called starc that compiles a tiny but still fast subset of C called C Star (C*) to a tiny and easy-to-teach subset of RISC-V called RISC-U,
a self-executing emulator called mipster that executes RISC-U code including itself when compiled with starc,
a self-hosting hypervisor called hypster that provides RISC-U virtual machines that can host all of selfie, that is, starc, mipster, and hypster itself, and
a tiny C* library called libcstar utilized by selfie.

Selfie is implemented in a single (!) file and kept minimal for simplicity. There is also a simple in-memory linker, a RISC-U disassembler, a garbage collector, L1 instruction and data caches, a profiler, and a debugger with replay as well as minimal operating system support in the form of RISC-V system calls built into the emulator and hypervisor. The garbage collector is conservative and even self-collecting. It may operate as library in the same address space as the mutator and/or as part of the emulator in the address space of the kernel.

Selfie generates ELF binaries that run on real RISC-V hardware as well as on QEMU and are compatible with the official RISC-V toolchain, in particular the spike emulator and the pk kernel.

Selfie is designed as 64-bit system and requires as such a 64-bit system to run (LP64 data model). However, selfie also compiles on systems that support compiling and executing 32-bit binaries (ILP32 data model). In that case, selfie becomes a 32-bit system that generates and executes 32-bit binaries out-of-the-box. This is possible because the implementation of selfie carefully avoids 32-bit overflows throughout the system.

Support

Slack: Join the conversation in the #selfie channel at cksystemsteaching.slack.com
Slides: There are classroom slides that provide a comprehensive introduction to the design and implementation of selfie.
Autograder: There is an autograder with compiler and operating systems assignments.
Paper: There is an Onward! 2017 paper featuring selfie.
Book: There is a free book in early draft form based on selfie called Elementary Computer Science: From Bits and Bytes to the Universality of Computing reaching out to everyone with an interest in learning about computer science.
Code: The selfie code is open source and available at github.com/cksystemsteaching/selfie
X: Follow us at x.com/christophkirsch
Web: The selfie homepage is at selfie.cs.uni-salzburg.at

Extras

Garbage collection: In addition to the conservative but O(n^2) garbage collector in selfie, there is an implementation of an O(n) Boehm garbage collector for small memory blocks with fall-back to the garbage collector in selfie for large memory blocks.
Fuzzing: There is a simple but self-fuzzing fuzzer called buzzr based on selfie that fuzzes RISC-U code including all of selfie and itself.
Symbolic execution: There is a self-executing symbolic execution engine called monster based on selfie that translates RISC-U code including all of selfie and itself to SMT-LIB formulae that are satisfiable if and only if there is input to the code such that the code exits with non-zero exit codes or performs division by zero within a given number of machine instructions.
Bounded model checking: There is a self-translating modeling engine called BEATOR based on selfie that translates RISC-U code including all of selfie and itself to BTOR2 formulae that are satisfiable if and only if there is input to the code such that the code exits with non-zero exit codes, performs division by zero, or accesses memory outside of allocated memory blocks.
BTOR2 visualization: There is a visualization tool called beatle that displays BTOR2 formulae generated from RISC-U binaries as directed acyclic graphs.
SAT solving: There is a bruteforce SAT solver called babysat based on selfie that computes satisfiability of SAT formulae in DIMACS CNF.
Binary translation: There is a self-translating binary translator based on selfie that translates RISC-U code including all of selfie and itself to x86 binary code.

Installing Selfie

Selfie runs natively on Linux, macOS, and Windows machines and possibly other systems that have a terminal and a C compiler installed. However, even without a C compiler installed on your machine, or if you only have access to a web browser you can run selfie. There are at least three ways to install and run selfie:

Natively on your machine (recommended): download and unzip selfie. Then, open a terminal to run selfie, see further below. For this to work, you need to have a C compiler installed on your machine. We recommend using clang or gcc (with cygwin on Windows).
In docker on your machine (advanced): download and install docker. Then, open a terminal and type docker run -it cksystemsteaching/selfie. The advantage of using docker is that you can run selfie out of the box on your machine without installing any tools such as a C compiler. All necessary and even optional tools are pre-installed in the selfie docker image. However, you need to know how to use docker.
In the cloud (easy but requires Internet connectivity): if you only have access to a web browser, just click here. Alternatively, create a github account, unless you already have one, and fork selfie into your github account. Then, create a cloud9 student account, connect it to your github account, verify your email address and set a password (important!), and finally clone your fork of selfie into a new cloud9 workspace.

At this point we assume that you have a system that supports running selfie. Below we use the make command assuming it is installed on your system which is usually the case. However, we also show the command invoked by make so that you can always invoke that command manually if your system does not have make installed.

The next step is to produce a selfie binary. To do that cd to the selfie folder in your terminal and then type make. With docker, the system will respond make: 'selfie' is up to date since there is already a selfie binary pre-installed. Without docker, make will invoke the C compiler on your machine or in the cloud9 workspace:

cc -Wall -Wextra -O3 -D'uint64_t=unsigned long' selfie.c -o selfie

and then compile selfie.c into an executable called selfie as directed by the -o option. The executable contains the C* compiler, the mipster emulator, and the hypster hypervisor. The -Wall and -Wextra options enable all compiler warnings which is useful during further development of selfie. The -O3 option instructs the compiler to generate optimized code. The -D'uint64_t=unsigned long' option is needed to bootstrap the code. It defines the data type uint64_t which would otherwise be undefined since C* does not include the necessary definitions. If your system supports compiling and executing 32-bit binaries you may also try make selfie-32 which will produce a 32-bit system that in turn generates and executes 32-bit binaries.

Running Selfie

Once you have successfully compiled selfie.c you may invoke selfie without any arguments as follows:

$ ./selfie
./selfie { -c { source } | -o binary | [ -s | -S ] assembly | -l binary } [ ( -m | -d | -r | -y ) 0-4096 ... ]

In this case, selfie responds with its usage pattern.

The order in which the options are provided matters for taking full advantage of self-referentiality.

The -c option invokes the C* compiler on the given list of source files compiling and linking them into RISC-U code that is stored internally. For example, selfie may be used to compile its own source code selfie.c as follows:

$ ./selfie -c selfie.c

The -o option writes RISC-U code produced by the most recent compiler invocation to the given binary file. For example, selfie may be instructed to compile itself and then output the generated RISC-U code into a RISC-U binary file called selfie.m:

$ ./selfie -c selfie.c -o selfie.m

The -s option writes RISC-U assembly of the RISC-U code produced by the most recent compiler invocation to the given assembly file while the -S option additionally includes approximate line numbers and the binary representation of the instructions. Similarly as before, selfie may be instructed to compile itself and then output the generated RISC-U code into a RISC-U assembly file called selfie.s:

$ ./selfie -c selfie.c -s selfie.s

The -l option loads RISC-U code from the given binary file. The -o and -s options can also be used after the -l option. However, in this case the -s option does not generate approximate source line numbers. For example, the previously generated RISC-U binary file selfie.m may be loaded as follows:

$ ./selfie -l selfie.m

The -m option invokes the mipster emulator to execute RISC-U code most recently loaded or produced by a compiler invocation. The emulator creates a machine instance with 0-4096 MB of memory. The source or binary name of the RISC-U code and any remaining ... arguments are passed to the main function of the code. For example, the following invocation executes selfie.m using mipster:

$ ./selfie -l selfie.m -m 1

This is in fact semantically equivalent to executing selfie without any arguments:

$ ./selfie

The -d option is similar to the -m option except that mipster outputs each executed instruction, its approximate source line number, if available, and the relevant machine state. Alternatively, the -r option limits the amount of output created with the -d option by having mipster merely replay code execution when runtime errors such as division by zero occur. In this case, mipster outputs only the instructions that were executed right before the error occurred.

If you are using docker you can also execute selfie.m directly on spike and pk as follows:

$ spike pk selfie.m

which is again semantically equivalent to executing selfie without any arguments.

The -y option invokes the hypster hypervisor to execute RISC-U code similar to the mipster emulator. The difference to mipster is that hypster creates RISC-U virtual machines rather than a RISC-U emulator to execute the code. See below for an example.

Self-compilation

Here is an example of how to perform self-compilation of selfie.c and then check if the RISC-U code selfie1.m generated for selfie.c by executing the ./selfie binary is equivalent to the code selfie2.m generated by executing the just generated selfie1.m binary:

$ ./selfie -c selfie.c -o selfie1.m -m 2 -c selfie.c -o selfie2.m
$ diff -s selfie1.m selfie2.m
Files selfie1.m and selfie2.m are identical

Note that at least 2MB of memory is required for this to work.

Self-execution

The following example shows how to perform self-execution of the mipster emulator. In this case we invoke mipster to invoke itself to execute selfie:

$ ./selfie -c selfie.c -o selfie.m -m 2 -l selfie.m -m 1

which is again semantically equivalent to executing selfie without any arguments but this time with selfie printing its usage pattern much slower since there is a mipster running on top of another mipster.

Self-hosting

The previous example can also be done by running hypster on mipster. This is significantly faster and requires less memory since hypster does not create a second emulator instance on top of the first emulator instance. Instead, hypster creates a virtual machine to execute selfie that runs concurrently to hypster on the first emulator instance:

$ ./selfie -c selfie.c -o selfie.m -m 1 -l selfie.m -y 1

We may even run hypster on hypster on mipster which is still reasonably fast since there is still only one emulator instance involved and hypster itself does not add much overhead:

$ ./selfie -c selfie.c -o selfie.m -m 2 -l selfie.m -y 1 -l selfie.m -y 1

Workflow

To compile any C* source code and execute it right away in a single invocation of selfie without generating a RISC-U binary use:

$ ./selfie -c any-cstar-file.c -m 1 "arguments for any-cstar-file.c"

Equivalently, you may also use a selfie-compiled version of selfie and have the mipster emulator execute selfie to compile any C* source code and then execute it right away with hypster on the same emulator instance:

$ ./selfie -c selfie.c -m 1 -c any-cstar-file.c -y 1 "arguments for any-cstar-file.c"

You may also generate RISC-U binaries both ways which will then be identical:

$ ./selfie -c any-cstar-file.c -o any-cstar-file1.m
$ ./selfie -c selfie.c -m 1 -c any-cstar-file.c -o any-cstar-file2.m
$ diff -s any-cstar-file1.m any-cstar-file2.m
Files any-cstar-file1.m and any-cstar-file2.m are identical

This can also be done in a single invocation of selfie:

$ ./selfie -c any-cstar-file.c -o any-cstar-file1.m -c selfie.c -m 1 -c any-cstar-file.c -o any-cstar-file2.m
$ diff -s any-cstar-file1.m any-cstar-file2.m
Files any-cstar-file1.m and any-cstar-file2.m are identical

The generated RISC-U binaries can then be loaded and executed as follows:

$ ./selfie -l any-cstar-file1.m -m 1 "arguments for any-cstar-file1.m"

Linking

To compile and link any C* source code from multiple source files use:

$ ./selfie -c any-cstar-file1.c any-cstar-file2.c ... -m 1

For example, to make the source code of selfie.c available as library code in any C* source code use:

$ ./selfie -c any-cstar-file.c selfie.c -m 1

Note that multiple definitions of symbols are ignored by the compiler with a warning.

Debugging

Selfie's console messages always begin with the name of the source or binary file currently running. The mipster emulator also shows the amount of memory allocated for its machine instance and how execution terminated (exit code).

As discussed before, RISC-U assembly for selfie and any other C* file is generated as follows:

$ ./selfie -c selfie.c -s selfie.s

If the assembly code is generated from a binary generated by the compiler (and not loaded from a file) approximate source line numbers are included in the assembly file.

Verbose debugging information is printed with the -d option, for example:

$ ./selfie -c selfie.c -d 1

Similarly, if the executed binary is generated by the compiler (and not loaded from a file) approximate source line numbers are included in the debug information.

selfie's People

Contributors

Stargazers

Watchers

Forkers

maigner aghosn weaselp raylouis batliay four sarming se16 andrew-m-h uchuugaka christianmoesl cpehle rokob graydon shtakai k56flex maffblaster tuyendothanh nukem epylar simap wolframalpha shkesar yetanothertimes naughtycode venthota vdt chlin501 muharremokutan andreeib dforgeas ravimandal47 cloudhan danielcorral longjohncoder techlord-rce shekkbuilder xee5ch ajinkyakulkarni chyyuu masudmo wah0airo stefanse jackbro martinnobis nivendha ngvrnd hugoplatzer cznic mewbak lparth strici topecongiro friendlypsycho mrigger yws swapnilgaikwad immortalin mattkelly scooley mateusgpe jthelin schoergk cloudxtreme fatswallow gokulvasan cponcelets occultism timung fares-z leodennis aboelnor007 wallheac davidouskayamamu the-c0d3r pcheropo joanbm ichalkias rriedig mwidmoser daveti praveenmunagapati assklou abdel01 hind77 4mekki4 jaouharabouamama safaeelamrani imaneelabid meryemjanatiidrissi karimboubouh bouayad42 a-karimkati ilyasbentachfine okensilin oussamaabb amboussetta amedboussetta mrbelmahi salimum6p

selfie's Issues

palloc address error

Hello,

I get a palloc address error when attempting to execute selfie.m by mipster. See transcript below:

~/selfie
$ gcc selfie.c -o selfie

~/selfie
$ ./selfie -c selfie.c -o selfie.m
./selfie: this is selfie's cstarc compiling selfie.c
./selfie: writing code into output file selfie.m

~/selfie
$ ./selfie -l selfie.m -m 1
./selfie: loading code from input file selfie.m
./selfie: this is selfie's mipster executing selfie.m with 1MB of memory
./selfie: palloc address error

Please advise.

Thank you,
yliam

Grade calculation is wrong with Python V2

The console log below shows a faulty grade for 6 out of 8 tests passed.

cm: grader (grader *)$ python grader/self.py bitwise-shift-2
executing test 'base'
[PASSED] cc compiles selfie.c
[PASSED] self-compilation does not lead to warnings or syntax errors
executing test 'bitwise-shift-2'
==== STAGE 1 ====
[PASSED] bitwise-right-shift operator with literals does compile
[PASSED] bitwise-right-shift operator with variables does compile
[PASSED] biwise-right-shift operator with invalid syntax does not compile
[PASSED] bitwise-left-shift operator with literals does compile
[PASSED] bitwise-left-shift operator with variables does compile
[PASSED] biwise-left-shift operator with invalid syntax does not compile
==== STAGE 2 ====
[PASSED] bitwise-right-shift operator has right RISC-V encoding
[FAILED] bitwise-right-shift operator calculates the right result for literals when executed with MIPSTER
./selfie -c grader/bitwise-right-shift-literals.c -m 128
 > Execution terminated with wrong exit code 13 instead of 2 <
 >> ./selfie: Max Göttl's selfie compiling grader/../grader/bitwise-right-shift-literals.c with starc
 >> ./selfie: 65 characters read in 3 lines and 0 comments
 >> ./selfie: with 53(81.53%) characters in 17 actual symbols
 >> ./selfie: 0 global variables, 1 procedures, 0 string literals
 >> ./selfie: 1 calls, 0 assignments, 0 while, 0 if, 1 return
 >> ./selfie: symbol table search time was 3 iterations on average and 18 in total
 >> ./selfie: 384 bytes generated with 94 instructions and 8 bytes of data
 >> ./selfie: init:    lui: 1(1.06%), addi: 45(47.87%)
 >> ./selfie: memory:  ld: 16(17.02%), sd: 6(6.38%)
 >> ./selfie: compute: add: 1(1.06%), sub: 2(2.12%), mul: 0(0.00%), divu: 0(0.00%), remu: 2(2.12%)
 >> ./selfie: control: sltu: 0(0.00%), beq: 4(4.25%), jal: 2(2.12%), jalr: 6(6.38%), ecall: 8(8.51%)
 >> ./selfie: selfie executing grader/../grader/bitwise-right-shift-literals.c with 128MB physical memory on mipster
 >> ./selfie: context grader/../grader/bitwise-right-shift-literals.c throws uncaught unknown instruction
 >> ./selfie: selfie terminating grader/../grader/bitwise-right-shift-literals.c with exit code 13
 >> ./selfie: summary: 25 executed instructions and 0.00MB(0.00%) mapped memory
 >> ./selfie: init:    lui: 1(4.00%), addi: 15(60.00%)
 >> ./selfie: memory:  ld: 0(0.00%), sd: 4(16.00%)
 >> ./selfie: compute: add: 0(0.00%), sub: 1(4.00%), mul: 0(0.00%), divu: 0(0.00%), remu: 1(4.00%)
 >> ./selfie: control: sltu: 0(0.00%), beq: 0(0.00%), jal: 1(4.00%), jalr: 0(0.00%), ecall: 2(8.00%)
 >> ./selfie: profile: total,max(ratio%)@addr(line#),2max,3max
 >> ./selfie: calls:   1,1(100.00%)@0x138(~2),0(0.00%),0(0.00%)
 >> ./selfie: loops:   0,0(0.00%),0(0.00%),0(0.00%)
 >> ./selfie: loads:   0,0(0.00%),0(0.00%),0(0.00%)
 >> ./selfie: stores:  4,1(25.00%)@0x30(~1),1(25.00%)@0x40(~1),1(25.00%)@0x13C(~2)
[PASSED] bitwise-right-shift operator has right RISC-V encoding
[FAILED] bitwise-right-shift operator calculates the right result for variables when executed with MIPSTER
./selfie -c grader/bitwise-right-shift-variables.c -m 128
 > Execution terminated with wrong exit code 13 instead of 2 <
 >> ./selfie: Max Göttl's selfie compiling grader/../grader/bitwise-right-shift-variables.c with starc
 >> ./selfie: 113 characters read in 9 lines and 0 comments
 >> ./selfie: with 81(71.68%) characters in 31 actual symbols
 >> ./selfie: 0 global variables, 1 procedures, 0 string literals
 >> ./selfie: 1 calls, 2 assignments, 0 while, 0 if, 1 return
 >> ./selfie: symbol table search time was 2 iterations on average and 24 in total
 >> ./selfie: 408 bytes generated with 100 instructions and 8 bytes of data
 >> ./selfie: init:    lui: 1(1.00%), addi: 47(47.00%)
 >> ./selfie: memory:  ld: 18(18.00%), sd: 8(8.00%)
 >> ./selfie: compute: add: 1(1.00%), sub: 2(2.00%), mul: 0(0.00%), divu: 0(0.00%), remu: 2(2.00%)
 >> ./selfie: control: sltu: 0(0.00%), beq: 4(4.00%), jal: 2(2.00%), jalr: 6(6.00%), ecall: 8(8.00%)
 >> ./selfie: selfie executing grader/../grader/bitwise-right-shift-variables.c with 128MB physical memory on mipster
 >> ./selfie: context grader/../grader/bitwise-right-shift-variables.c throws uncaught unknown instruction
 >> ./selfie: selfie terminating grader/../grader/bitwise-right-shift-variables.c with exit code 13
 >> ./selfie: summary: 30 executed instructions and 0.00MB(0.00%) mapped memory
 >> ./selfie: init:    lui: 1(3.33%), addi: 16(53.33%)
 >> ./selfie: memory:  ld: 2(6.66%), sd: 6(20.00%)
 >> ./selfie: compute: add: 0(0.00%), sub: 1(3.33%), mul: 0(0.00%), divu: 0(0.00%), remu: 1(3.33%)
 >> ./selfie: control: sltu: 0(0.00%), beq: 0(0.00%), jal: 1(3.33%), jalr: 0(0.00%), ecall: 2(6.66%)
 >> ./selfie: profile: total,max(ratio%)@addr(line#),2max,3max
 >> ./selfie: calls:   1,1(100.00%)@0x138(~5),0(0.00%),0(0.00%)
 >> ./selfie: loops:   0,0(0.00%),0(0.00%),0(0.00%)
 >> ./selfie: loads:   2,1(50.00%)@0x160(~8),1(50.00%)@0x164(~8),0(0.00%)
 >> ./selfie: stores:  6,1(16.66%)@0x30(~1),1(16.66%)@0x40(~1),1(16.66%)@0x13C(~5)
[PASSED] bitwise-left-shift operator has right RISC-V encoding
[PASSED] bitwise-left-shift operator calculates the right result for literals when executed with MIPSTER
[PASSED] bitwise-left-shift operator has right RISC-V encoding
[PASSED] bitwise-left-shift operator calculates the right result for variables when executed with MIPSTER
tests of stage 1 passed: 100.0%
tests of stage 2 passed: 0.0%
your grade is: 5

Quiet mode in bulk grader

@ChristianMoesl Could you please look at grade-from-links.py and add quiet mode here as well? This may be easier though than in the grader since only git and make need to be quiet. In the end, I need the script to output lines of the form: user/repo: 1-5

encoding glitch

In selfie/manuscript/semantics.md.
The symbol -- appears like â€”. However, it is not a markdown error.

Disassembler
: A computer program that translates machine language into assembly language -- the inverse operation to that of an assembler.

Building and running docker image in GitHub Workflow for selfie

See .travis.yml for how this is done on travis.

No timeout for selfie execution

The grader script executes selfie in a separate process and waits until it exits, to check the result. If the executed version of selfie is executing forever, the grader script also never stops.

A timeout for this execution should be added, to fix this issue.

Grader can give two different grades for the same test files

The grading script can give two different grades for the same set of test files (selfie.c). Could be, that some temporary files are not cleaned up correctly, like they should be.

Grader crashes when selfie is a directory

The grader crashes, when grading a repository with a folder selfie located at the root of the repository.

User/Selfie: Traceback (most recent call last):
  File "grader/self.py", line 998, in <module>
    main(sys.argv)
  File "grader/self.py", line 992, in main
    do_bulk_grading(tests)
  File "grader/self.py", line 949, in do_bulk_grading
    check_assignments(tests)
  File "grader/self.py", line 964, in check_assignments
    test_base(mandatory=True)
  File "grader/self.py", line 699, in test_base
    test_compile_warnings('selfie.c', 'self-compilation does not lead to warnings or syntax errors', mandatory=mandatory)
  File "grader/self.py", line 465, in test_compile_warnings
    test_execution('./selfie -c {}'.format(file), msg, success_criteria=has_no_compile_warnings, mandatory=mandatory)
  File "grader/self.py", line 353, in test_execution
    returncode, output, _ = execute(command)
  File "grader/self.py", line 197, in execute
    process = Popen(command.split(' '), stdout=PIPE, stderr=PIPE)
  File "/usr/local/Cellar/python/3.7.3/Frameworks/Python.framework/Versions/3.7/lib/python3.7/subprocess.py", line 775, in __init__
    restore_signals, start_new_session)
  File "/usr/local/Cellar/python/3.7.3/Frameworks/Python.framework/Versions/3.7/lib/python3.7/subprocess.py", line 1522, in _execute_child
    raise child_exception_type(errno_num, err_msg, err_filename)
PermissionError: [Errno 13] Permission denied: './selfie'

make spike fails on docker

spike pk selfie.m -c selfie.c -o selfie5.m -s selfie5.s -m 1
Failed to run dtc: No such file or directory
Child dtb process failed
make: *** [Makefile:93: spike] Error 1

Split array assignment

The current array assignment should be splitted into 2 assignments:

array-1:

1 dimensional arrays and selectors
global and local declarations
call by reference
array symbol without selector gives the start address of the array

array-2

n-dimensional arrays and selectors

x86 binary translator does not build on docker

@alexkollert The translator seems to be unable to generate actual files, see:

https://travis-ci.org/cksystemsteaching/selfie/jobs/516088760

Can you please fix that?

Option -q

Option -q of the grader seems to be redundant. Full output seems to be unavailable.

Ctrl-C

Pressing Ctrl-C just once should terminate grader.

Grader tests for values equal to Selfie error codes

The grading script compiles and then executes sample code and tests for the exit code value. This leads to a problem, when the value, which the grader expects, is equal to one of the Selfie errors codes (1-13). In this case, someone can not decide, if selfie aborted with an error or the mipster execution exited with this return value.

Execution timeout to strict

The execution timeout for Mipster in the grading script is to low (10s), such that it can easily trigger.

Better names for assignments

@ChristianMoesl I recall that we talked about renaming some of the assignments. Could you please do that before classes start next week? Thanks!

Segmentation fault in function storePhysicalMemory

Greetings Again Sir,

I realize your development platform and therefore main operating focus for Selfie is Linux. As you will recall from our previous correspondence in February, I have successfully run Selfie in Cygwin. However, I have also compiled selfie natively on Windows with MinGW. I only had to change the following six lines by looking up and changing open() oflag values to reflect those found in the MinGW fcntl.h file and file access permission (sflag) values to reflect those found in the MinGW sys/stat.h file. Original and changed versions of each line are shown below:

165
// 577 = 0x0241 = O_CREAT (0x0040) | O_WRONLY (0x0001) | O_TRUNC (0x0200)
// 769 = 0x0301 = _O_CREAT (0x0100) | _O_WRONLY (0x0001) | _O_TRUNC (0x0200)

166
int O_CREAT_WRONLY_TRUNC = 577; // flags for opening write-only files
int win_O_CREAT_WRONLY_TRUNC = 769; // flags for opening write-only files

168
// 420 = 00644 = S_IRUSR (00400) | S_IWUSR (00200) | S_IRGRP (00040) | S_IROTH (00004)
// 384 = 0x0180 = _S_IREAD (0x0100) | _S_IWRITE (0x0080)

169
int S_IRUSR_IWUSR_IRGRP_IROTH = 420; // flags for rw-r--r-- file permissions
int win_S_IREAD_IWRITE = 384; // flags for rw file permissions

3976
fd = open(binaryName, O_CREAT_WRONLY_TRUNC, S_IRUSR_IWUSR_IRGRP_IROTH);
fd = open(binaryName, win_O_CREAT_WRONLY_TRUNC, win_S_IREAD_IWRITE);

6015
assemblyFD = open(assemblyName, O_CREAT_WRONLY_TRUNC, S_IRUSR_IWUSR_IRGRP_IROTH);
assemblyFD = open(assemblyName, win_O_CREAT_WRONLY_TRUNC, win_S_IREAD_IWRITE);

My issue is that I get a signal SIGSEV, Segmentation Fault when line 4878 is executed inside the storePhysicalMemory function on native Windows compiled with MinGW. Do you have any idea as to what might be causing this? Maybe something to do with the paddr pointer?

Thanks,
yliam

Windows Build

GitHub Workflow on windows-latest does not build. Anyone interested in fixing this?

Overflows in profiler

The profiler overflows for the following (long-running) invocation:

> $ ./selfie -c selfie.c -m 4 -c selfie.c -m 2 -c selfie.c                                                                                                                                                                 [±master ✓]
./selfie: this is selfie compiling selfie.c with starc
./selfie: 191548 characters read in 7576 lines and 1032 comments
./selfie: with 105824(55.24%) characters in 31199 actual symbols
./selfie: 270 global variables, 311 procedures, 455 string literals
./selfie: 2094 calls, 809 assignments, 71 while, 627 if, 287 return
./selfie: 129704 bytes generated with 30755 instructions and 6684 bytes of data
./selfie: this is selfie executing selfie.c with 4MB of physical memory on mipster
selfie.c: this is selfie compiling selfie.c with starc
selfie.c: 191548 characters read in 7576 lines and 1032 comments
selfie.c: with 105824(55.24%) characters in 31199 actual symbols
selfie.c: 270 global variables, 311 procedures, 455 string literals
selfie.c: 2094 calls, 809 assignments, 71 while, 627 if, 287 return
selfie.c: 129704 bytes generated with 30755 instructions and 6684 bytes of data
selfie.c: this is selfie executing selfie.c with 2MB of physical memory on mipster
selfie.c: this is selfie compiling selfie.c with starc
selfie.c: 191548 characters read in 7576 lines and 1032 comments
selfie.c: with 105824(55.24%) characters in 31199 actual symbols
selfie.c: 270 global variables, 311 procedures, 455 string literals
selfie.c: 2094 calls, 809 assignments, 71 while, 627 if, 287 return
selfie.c: 129704 bytes generated with 30755 instructions and 6684 bytes of data
selfie.c: selfie.c exiting with exit code 0 and 1.37MB of mallocated memory
selfie.c: this is selfie terminating selfie.c with exit code 0 and 1.25MB of mapped memory
selfie.c: profile: total,max(ratio%)@addr(line#),2max(ratio%)@addr(line#),3max(ratio%)@addr(line#)
selfie.c: calls: 81494266,36060198(44.44%)@0x321C(~1438),18003399(22.12%)@0x35DC(~1481),9274087(11.38%)@0x327C(~1444)
selfie.c: loops: 3086455,2577721(84.03%)@0x7724(~2465),315373(10.22%)@0x3D10(~1565),85724(2.77%)@0x5EF8(~2063)
selfie.c: loads: 636395737,36060198(5.66%)@0x3230(~1438),18003399(2.82%)@0x35F0(~1481),18003313(2.82%)@0x3674(~1486)
selfie.c: stores: 356401479,36060198(10.12%)@0x3220(~1438),18003399(5.05%)@0x35E0(~1481),18003313(5.05%)@0x367C(~1486)
./selfie: selfie.c exiting with exit code 0 and 4.43MB of mallocated memory
./selfie: this is selfie terminating selfie.c with exit code 0 and 3.50MB of mapped memory
./selfie: profile: total,max(ratio%)@addr(line#),2max(ratio%)@addr(line#),3max(ratio%)@addr(line#)
./selfie: calls: 363159223,1213337728(344.82%)@0x140B8(~5375),1213337407(344.82%)@0x13EE8(~5354),1156375854(322.58%)@0x15F8C(~5834)
./selfie: stores: 2011320912,1213337728(60.60%)@0x140BC(~5375),1213337407(60.60%)@0x13EEC(~5354),1156375854(57.80%)@0x15F90(~5834)

Notice the missing loops and loads lines at the very end as well as the meaningless percentage numbers in the calls line.

Support for RISCV-32

Hi,

Actually I hacked a fast working version for RISCV-32G, see:

https://github.com/andreasbaumann/selfie/tree/risc32

Basically I replaced uint64_t with uint32_t, adapted some opcodes (like LW, SW instead of LD and SD).

Building is done with:

gcc -O0 -m32 -g -Duint32_t='unsigned int' selfie.c -o selfie

It seems to work on Qemu:

./selfie -c selfie.c -o selfie.m
qemu-riscv32 selfie.m

Also this works:

./selfie -c selfie.c -s selfie.s
riscv64-linux-gnu-as -march=rv32g selfie.s

I was not able to test with spike yet, as I have first to build bbl/pk for RISCV-32
on Archlinux32.

I manually checked the assembly code of the examples in manuscript and they
seem ok.

Next step for me is to see, how easy it is to join the 32-bit and 64-bit version
and maybe make it built for either platform with some switches.

Grader does not respect whitespaces in paths

The grading script splits commands, which have to be executed, by whitespaces. This leads to wrong commands, when a file path includes a whitespace.

Verify disassembler file

For every assignment, where the students have to implement a new RISC-V instruction into the compiler/emulator, there should be a test to verify, that the disassembler prints this instruction in the right format.

Autograder in the Cloud

Anyone interested in enhancing the autograder to work with GitHub Workflows? Ideally, even submitting assignments should work through that mechanism.

Compiling under Windows?

In README.md one can read:

Selfie runs on Mac, Linux, Windows and possibly other systems that have a terminal and a C compiler installed.

On the other hand only instructions for compiling (and running) Selfie under UNIX-like operating systems are given. So what is the designated way to compile Selfie under Windows using Visual C++ using either cmd.exe (e.g. via "x86 Native Tools Command Prompt"; though Microsoft considers this terminal as deprecated) or PowerShell?

Use argparse library for argument parsing

The standard python library argparse should be used to parse command line arguments.

Add precedence test in 'bitwise-shift-2'

The grader should verify, that new implemented operators follow the precedence order of C

out-of-bounds read

=========== Start of #0 stensal runtime message ===========

Runtime error: [reading from the outside of a memory space]
Continuing execution can cause undefined behavior, abort!

-
- Reading 8 bytes from 0xbffff16c will read undefined values.
- 
- The memory-space-to-be-read (start:0xbffff164, size:12 bytes) is allocated at
-     unknown_location (report this ::218)
- 
-  0xbffff164               0xbffff16f
-  +------------------------------+
-  | the memory-space-to-be-read  |......
-  +------------------------------+
-                          ^~~~~~~~~~
-      the read starts at 0xbffff16c that is 4 bytes before the memory-space end.
- 
- Stack trace (most recent call first) of the read.
- [0]  file:selfie/selfie.c::12708, 5
- [1]  file:selfie/selfie.c::12716, 14
- [2]  file:selfie/selfie.c::12747, 16
- [3]  file:selfie/selfie.c::12799, 10
- [4]  [libc-start-main]
-

============ End of #0 stensal runtime message ============

Hypster crashes with many local variables

The following code crashes when executed with Hypster with a error message "selfie.c: palloc out of physical memory".

./selfie -c selfie.c -m 128 -c code.c -y 64

code.c:

int main(int argc, char** argv) {
  uint64_t a0;
  uint64_t a1;
  // .
  // .
  // .
  uint64_t a1099;
  uint64_t a1100;

  a1100 = 1;

  return a1100;
}

Bug in load_integer()!?

I'm afraid that maybe load_integer() does not work in the way it should for integers a bit less than 2^31.
For example that code

uint64_t main(){
	uint64_t a;
	uint64_t b;
	uint64_t c;

	initLibrary();

	a = 2147483647; //2^31-1

	print((uint64_t*) "as decimal: ");
	printInteger(a);
	print((uint64_t*) "  as binary: ");
	printBinary(a, 64);
	println();

	return a;
}

prints this result

as decimal: -2147483649  as binary: 1111111111111111111111111111111101111111111111111111111111111111

Especially the binary output make me think, that the problem is not in printInteger(), but in load_integer().

Binary length overflow in emitGlobalsStrings()

Description of problem

Some larger C* programs cause selfie to segfault when compiling them. The issue was discovered when I tried to test all four shift instructions in emitLeftShiftBy(), after which ./selfie -c selfie.c segfaulted sometimes.

Example

A testcase generator and testcase C* file causing a segfault when compiled by selfie (5000 strings) can be found here: Gist

Cause

When appending instructions to binary via emitInstruction(), selfie tests whether the maxBinaryLength has already been reached. When (after having finished compilation) appending globals/strings to the binary the copyStringToBinary() / storeBinary() procedures do not check whether the maxBinaryLength has been reached, which can cause overflows. The binary size without the strings can be well within maxBinaryLength while after including strings it would be exceeded.

Possible fix

All procedures that extend the binary work with the storeBinary() procedure. Move the overflow check from emitInstruction() to storeBinary(), asserting baddr < maxBinaryLength there.

Pull request: #23

Pagesize not configurable

I tried to change to PAGESIZE to 1024 and tested selfie. But if i execute this:

./selfie -c selfie.c -o selfie3.m -s selfie3.s -y 3 -l selfie3.m -y 2 -l selfie3.m -y 2 -c selfie.c -o selfie4.m -s selfie4.s

it fails in restoreContext() (line 6598) with an segmentation fault. As far as i understood it, virtual memory isn't correctly mapped at this time.

Clone repositories with ssh authentication

The bulk grader should authenticate via ssh and a public/private key when cloning the student repositories

Fix main signature in hello-world.c

Use int and chartypes in main() function signature

Split fork-wait into two assignments

Split the fork-wait assignment into two: fork-wait and fork-wait-exit. The latter should be like the existing fork-wait. The new fork-wait should be just like before except for the status parameter for wait since doing that requires knowledge of virtual memory.

smalloc: possible array out-of-bound access when out of memory in init_library

When running a code analysis with Frama-C on selfie, I got the following alarms:

file        function                kind           alarm
----------------------------------------------------------------------------------------
selfie.c    two_to_the_power_of     mem_access      \valid_read(power_of_two_table + p)
selfie.c    two_to_the_power_of     initialization  \initialized(power_of_two_table + p)

stack: two_to_the_power_of <- get_bits <- load_character <- 
  print_format1 <- printf1 <- smalloc <- init_library <- main

What they mean is that, in case the call to smalloc fails (due to lack of memory) while initializing the library, because we didn't have time to properly allocate and initialize the global pointer power_of_two_table, the error message from smalloc itself may trigger a null pointer dereferencing.

In practice, this is extremely unlikely to happen; but in case there is some pedagogical interest in such corner cases, I'm reporting it here. One way to avoid it might be to test that power_of_two_table is not null before trying to print anything, for instance.

Please feel free to close this issue if you find it nitpicky.

Basic Tests

Add a set of basic tests, which should run on every invocation and have to succeed, to get a grade < 5.

This tests should basically check:

if selfie is compilable with gcc (check for exit-status == 0)
if selfie compiles itself without warnings

Integrate Unit tests in Travis CI build

The unit tests for the grader should be executed after every build, to ensure, that a code change does not break the grader.

Optional Assignment Parameter

The assignment parameter of the grader should be optional. If not provided the grader should just clone/update repos.

Second and third argument of `-se` option should be optional

@ChrisEdel The -se option requires at least two arguments. This is inconsistent with the usage pattern printed by selfie and the readme explaining the option. I suggest to make the second argument optional similar to the third argument (--merge-enabled) and still ignore the second and third argument in the usage pattern and readme. Can you please fix that through a PR?

Add a new test for Bitwise AND/OR/NOT

Bitwise AND/OR operators should be added to the C* language and emulator support for the corresponding RISC-V instruction should be provided.

This test should verify:

the parser correctly decides, if a is in C* or not.
the precedence of the operator is implemented like in C
the generated instructions have the correct RISC-V encoding
the semantics of the instruction is correctly implemented in the emulator

Division with integer literals gives wrong result

The following c snippet gives different results on selfie compared to gcc/clang
uint64_t a; a = (-1) / 2;

With selfie we get for a: 9223372036854775807
With gcc we get for a: 0

This is due to the lack of integer division in Selfie.

disassembling issue

@ChristianMoesl By execution of these two consecutive command lines
./selfie -c selfie.c -o selfie.m
./selfie -l selfie.m -s selfie.s
selfie.s will contain "./selfie: unknown instruction with 101101 opcode detected" at the last line.

The reason should be because of this line codeLength = *(ELF_header + 12); in selfie_load() which stores the size of the binary (including data segment) into codeLength. So, the wrong value of codeLength will be used in selfie_disassembler() function.

Merge grader and the tools scripts

The grader script (self.py) and the tools scripts grader/tools/*.py should be merged together.

Improve grader help message

With -h or no options at all, the grader should also output what it is and refer to the selfie project.

Create Readme file

A Readme file (in grader/) should be written to document the self-grader.

Positive grades without passing essential tests

Some assignments can be easily passed (grade <= 4) without actually passing some essential tests. To overcome this issue, some tests should be marked as mandatory, which means, that the assignment can not be passed, without passing all mandatory tests.

Create Unit tests

Unit tests should be created, to ensure proper code quality of the grader.
Created for assignments:

General Assignments:

self-compile
print-name

Compiler Assignments:

OS Assignments:

Fix code style differences python scripts

Quiet mode

Implement a "quiet mode" of the grader, where only the actual grade gets printed on the console. This mode should be activated with a command line option.

atoi() unreliable overflow handling

Description of problem

the atoi() function does not always fail when an integer literal representing a number larger than 2^31 is processed.

Example

int main() { int a; a = 9999999999; return 0; }

compiles successfully while

int main() { int a; a = 2222222222; return 0; }

doesn't.

Cause

Multiplying , for example, 999999999 with 10 , as done at the end of the conversion for "9999999999" obviously causes an overflow. The resulting int value is however positive so the check n < 0 does not trigger.

Possible fix

Check for overflows in a different way: Store a value x = INT_MAX / 10 = 214748364 and a maximum digit y = 8. Before introducing a new digit c to the number n, fail if

n > x or (n == x and c > y), this is true if and only if n * 10 + c mathematically is larger than INT_MAX + 1, so the input string represents a number larger than abs(INT_MIN).
n == INT_MIN, since there are digits remaining, the input string represents too large a number.

See this commit for code (no pull request possible because of private repo).

cksystemsteaching / selfie Goto Github PK

selfie's Introduction

Selfie

Support

Extras

Installing Selfie

Running Selfie

Self-compilation

Self-execution

Self-hosting

Workflow

Linking

Debugging

selfie's People

Contributors

Stargazers

Watchers

Forkers

selfie's Issues

Description of problem

Example

Cause

Possible fix

Description of problem

Example

Cause

Possible fix

Recommend Projects

Recommend Topics

Recommend Org