xv6/Blitz  --  Harry Porter, 5 November 2023
============================================

This OS kernel is a direct transcription of the xv6/Risc-V code from "C" into "KPL". The original C code was copied from from:

   https://github.com/mit-pdos/xv6-riscv    (as downloaded on 4 August 2023)



OTHER DOCUMENTATION
===================

For information about xv6 see:

  "xv6: a simple, Unix-like teaching operating system",
     by Russ Cox, Frans Kaashoek, Robert Morris
     https://pdos.csail.mit.edu/6.828/2023/xv6/book-riscv-rev3.pdf

  "The xv6 Kernel", YouTube Playlist, by Harry Porter
     https://www.youtube.com/playlist?list=PLbtzT1TYeoMhTPzyTZboW_j7TPAnjv9XB

  "Shell Code Explained", YouTube Playlist, by Harry Porter
     https://www.youtube.com/playlist?list=PLbtzT1TYeoMhF4hcpEiCsOeN13zqrzBJq



TO EXECUTE THE KERNEL
=====================

To compile everything:
  cd .../KPL-Code/xv6
  make

With only one core running:
  blitz xv6.exe -disk disk.img -g -raw

With all cores running:
  blitz xv6.exe -disk disk.img -g -raw -startall

Arguments to the Blitz emulator:
     -g
         Go; Start execution immediately.
     -raw
         For all input, do not echo. The xv6 kernel will echo input from the UART.
     -startall
         Start all cores; default is just core 0.
     -disk <filename>
         Name the host file that will be used for all disk I/O.

To exit the kernel, type Control-C.
Then, in the emulator, type "q".
(Or just hit Control-C three times.)



KERNEL PARAMETERS
=================

There are a number of parameters defined as constants in the xv6 kernel:
    NPROC        maximum number of processes
    NCPU         maximum number of CPUs
    NOFILE       open files per process
    NFILE        open files per system
    NINODE       maximum number of active i-nodes
    NDEV         maximum major device number
    ROOTDEV      device number of file system root disk
    MAXARG       max exec arguments
    MAXOPBLOCKS  max # of blocks any FS op writes
    LOGSIZE      max data blocks in on-disk log
    NBUF         size of disk block cache
    FSSIZE       size of file system in blocks
    MAXPATH      maximum file path name

    BSIZE        block size
    FSSIZE       size of file system in blocks
    NINODES      max # of files (i-nodes) on the disk

    MAXOPBLOCKS  max # of blocks any FS op writes
    LOGSIZE      max data blocks in on-disk log
    NBUF         size of disk buffer cache

    FSMAGIC      Magic number in superblock

    DIRSIZ       Max size of filenames
    NDIRECT      Number of direct pointers in an i-node

The Blitz implementation uses the same values as the Risc-V implementation, with a couple of minor differences:
    FSMAGIC      Enlarged to 64 bits
    FSSIZE       Increased to 6000 blocks



FILE ORGANIZATION
=================

The xv6 code lives in the "xv6" directory, which is just one thing in the "KPL-Code" directory.

Here are the key files:

  KPL-Code/
    xv6/
      README-RISCV                          -- For xv6/Risc-V
      README-BLITZ                          -- This very file
      RISCV-LICENSE                         -- For xv6/Risc-V
      makefile
      xv6.c                                 -- The kernel code
      syscall.h
      fs.h
      entry.s
      initcode.s
      makeUsys.c                            -- Program to automatically create usys.s
      mkfs.c                                -- Program to build the initial filesystem
      disk.img                              -- Contains the xv6 file system
      UserCode/
        UserSystem.c                        -- Package used by all user-level programs
        UserRuntime.s                       -- Assembly code needed by all user-level programs
        usys.s
        init.c
        sh.c
        echo.c
        cat.c
          ...other user programs...

In the Risc-V version, the kernel code is spread over a large number of files, such as:
   main.c   kalloc.c   sysproc.c   ...
In the Blitz version, all the code is combined into one large file "xv6.c", with data and type definitions in "xv6.h". The benefit of this organization is that text searching is quick and easy. Compile-time is not an issue.

In addition, the following assembly code is part of xv6/Blitz:
   entry.s         -- Contains "_entry", "kernelvec", "uservec", "userret" and "swtch"
   initcode.s      -- The first user-level code executed, which execs the "init" process.
I combined all the xv6 assembly code into a single file ("entry.s"), because there was so little code and it seemed cleaner. The same code in the Risc-V implementation is spread over these files: 
   entry.S    trampoline.S    kernelvec.S    swtch.S

In Blitz/KPL, each program consists of one or more "packages". For each package, there is a ".h" and ".c" file. For xv6, we have:
   xv6.h                  xv6.c            -- Contains the kernel code
   syscall.h              syscall.c        -- syscall.h contains definitions; syscall.c is empty
   fs.h                   fs.c             -- fs.h contains definitions; fs.c is empty

The xv6 kernel runs under the Blitz-64 emulator as a "stand-alone program". What this means is that it uses packages that are required to support the KPL language and that are needed for running as a stand-alone program, as kernels must do. The relevant package is:
   BasicSystem.h          BasicSystem.c

The BasicSystem package in turn uses:
   KPLSupport.h           KPLSupport.c      -- Basic functionality of KPL, including many useful functions
   HostInterface.h        HostInterface.c   -- Functions to access the host file system (not used in xv6)
   KPLRuntime.s                             -- Hand-coded assembly concerned with KPL language support
   GlobalTrapHandler.s                      -- Hand-coded assembly for non-xv6 trap handling
   BasicRuntime.s                           -- Hand-coded assembly concerned with stand-alone execution

All user-level programs are kept in the "UserCode" sub-directory. A single package is used by all user-level programs:
   UserSystem.h           UserSystem.c      -- Includes syscalls and support functions not defined in KPLSupport
In addition, user-level programs must be linked with:
   UserRuntime.s          -- Hand-coded assembly defining _entry, which initializes and invokes "main"
   usys.s                 -- Auto-generated assembly code with a single "stub" routine for each syscall 

There are two additional stand-alone KPL programs:
   makeUsys.h             makeUsys.c        -- Automatically creates the usys.s file
   mkfs.h                 mkfs.c            -- Builds the "disk.img" file, which contains the xv6 file system
The "makefile" will run these programs whenever necessary.

Both "makeUsys" and "mkfs" run as stand-alone KPL programs. As such, they use the following packages:
   BasicSystem.h          BasicSystem.c
   PrintPackage.h         PrintPackage.c    -- Support for KPL's printf statements

For each user-level programs, there is a single package. For example:
   sh.h                   sh.c
   echo.h                 echo.c
   cat.h                  cat.c
      ...etc...

Each user-level programs uses "UserSystem" and is linked with:
   UserSystem.o
   UserRuntime.o
   usys.o



MAKEFILES
=========

The "xv6/makefile" does the following:

     --Update any tools (such as the KPL compiler) that have been changed
     --Assemble "initcode.s"
     --Assemble "entry.s"
     --Compile package "fs"
     --Compile package "syscall"
     --Compile, assemble, and link the kernel, producing "xv6.exe"
     --Assemble "UserRuntime.s"
     --Compile package "UserSystem"
     --Compile package "makeUsys"
     --Execute makeUsys to create "usys.s"; assemble "usys.s"
     --Compile, assemble, and link each user-level program
     --Compile package "mkfs"
     --Run mkfs to build the "disk.img"

Roughly speaking, here are the commands: [For clarity below, we use ".../KPL-Code/" rather than "../"]

  --Assemble "initcode.s"
     asm initcode.s -o initcode.o -l >initcode.listing
     link initcode.o -o initcode.exe
     hexify initcode.exe -silent -hex2 -nowarn > initcode.hex
     head -n 25 initcode.hex
        The machine code for "initcode" must be copied directly into the kernel (xv6.c).

  --Assemble "entry.s"
     asm entry.s -o entry.o -l > entry.listing
        The file "entry.s" contains "_entry", "kernelvec", "uservec", "userret" and "swtch".

  --Compile package "fs"
     kpl fs -o fs.s -d .../KPL-Code/
     asm fs.s -o fs.o
        This package only contains definitions related to the filesystem.

  --Compile package "syscall"
     kpl syscall -o syscall.s -d .../KPL-Code/
     asm syscall.s -o syscall.o
        This package only contains definitions related to syscalls.

  --Compile, assemble, and link the kernel, producing "xv6.exe"
     kpl xv6 -o xv6.s -unsafe -d .../KPL-Code/
     asm xv6.s -o xv6.o
     link    xv6.o entry.o fs.o syscall.o                                        \
               .../KPL-Code/KPLRuntime.o           \
               .../KPL-Code/BasicRuntime.o         \
               .../KPL-Code/KPLSupport.o           \
               .../KPL-Code/BasicSystem.o          \
               .../KPL-Code/HostInterface.o        \
               .../KPL-Code/GlobalTrapHandler.o    \
                  -o xv6.exe -k -w2

  --Assemble "UserRuntime.s"
     asm UserRuntime.s -o UserRuntime.o -l >UserRuntime.listing

  --Compile package "UserSystem"
     kpl UserSystem -d .../KPL-Code/ -o UserSystem.s -unsafe
     asm UserSystem.s -o UserSystem.o

  --Compile package "makeUsys"
     kpl   makeUsys -o makeUsys.s -unsafe -d .../KPL-Code/
     asm   makeUsys.s -o makeUsys.o
     link  makeUsys.o                               \
               .../KPL-Code/xv6/syscall.o           \
               .../KPL-Code/KPLSupport.o            \
               .../KPL-Code/BasicSystem.o           \
               .../KPL-Code/HostInterface.o         \
               .../KPL-Code/PrintPackage.o          \
               .../KPL-Code/KPLRuntime.o            \
               .../KPL-Code/BasicRuntime.o          \
               .../KPL-Code/BasicEntry.o            \
               .../KPL-Code/GlobalTrapHandler.o     \
                  -o makeUsys.exe -k -w2

  --Execute makeUsys to create "usys.s" and then assemble "usys.s"
     blitz makeUsys.exe -g -nowarn > usys.s
     asm   usys.s -o usys.o

  --Compile, assemble, and link each user-level program
     For example:
          kpl  echo -o echo.s -unsafe -d .../KPL-Code/
          asm  echo.s -o echo.o
          link echo.o                                \
               .../KPL-Code/KPLSupport.o             \
               .../KPL-Code/KPLRuntime.o             \
               .../KPL-Code/xv6/syscall.o            \
               UserSystem.o
               UserRuntime.o
               usys.o
                  -o echo.exe -w2

  --Compile package "mkfs"
     kpl mkfs -o mkfs.s -unsafe -d .../KPL-Code/
     asm mkfs.s -o mkfs.o
     link    mkfs.o                                \
               .../KPL-Code/xv6/fs.o               \
               .../KPL-Code/KPLSupport.o           \
               .../KPL-Code/BasicSystem.o          \
               .../KPL-Code/HostInterface.o        \
               .../KPL-Code/PrintPackage.o         \
               .../KPL-Code/KPLRuntime.o           \
               .../KPL-Code/BasicRuntime.o         \
               .../KPL-Code/BasicEntry.o           \
               .../KPL-Code/GlobalTrapHandler.o    \
                  -o mkfs.exe -k -w2

  --Run mkfs to build the "disk.img"
     blitz mkfs.exe -g -nowarn -args                                                            \
              ".../KPL-Code/xv6/disk.img                                                        \
               README      README-BLITZ                                                         \
               init.exe    echo.exe       sh.exe         ls.exe         cat.exe    rm.exe       \
               wc.exe      mkdir.exe      grep.exe       ln.exe         kill.exe                \
               grind.exe   forktest.exe   stressfs.exe   usertests.exe  zombie.exe"



DIFFERENCES BETWEEN THE Risc-V AND Blitz-64 IMPLEMENTATIONS
===========================================================

The directory organization is slightly different. In the xv6/Risc-V implementation, the directory hierarchy is:
    xv6
      kernel
      user
      mkfs
In the xv6/Blitz implementation, we have one directory and only one sub-directory.
    xv6
      UserCode
The code that was in "kernel" and "mkfs" is now in "xv6". With the Mac Finder, it was simpler to collapse things a bit.

Most of the changes to the code were syntactic and superficial, reflecting cosmetic differences between the C and KPL languages.

Here are some additional differences:

A major difference concerns how strings are handled. In C, string are null-terminated. In KPL, a "String" is an array of bytes which contains a header with size information. The operations on strings are similar but have different names. For example, "strlen" in C becomes "arraySize" in KPL.

In KPL, arrays must be initialized, so a number of calls to "arrayInitialize" have been added.

Pointer arithmetic is a bit different. In C, "p+1" will advance the pointer by the size of whatever is pointed to. In KPL, this becomes, e.g., "p + sizeOf(xxx)".

In C, arrays are often null-terminated. For example, the "argv" array is null-terminated. In KPL, the additional slot of null is not needed and is removed. Instead, KPL code relies on the array size.

In the C code, a variety of unsigned integers types are used (e.g., uchar, uint, uint64). In KPL, signed types are used. In fact, the "int" type (signed, 64-bits) is used for almost all of these.

There are several identifiers that conflict with other uses in KPL, such as printf, end, exit, type. These are changed to printf_, end_, exit_, type_.

KPL has collection of printing functions called the "Basic I/O" system. (These functions include print, printChar, printInt, printIntVar, printHexVar, ...) Although the Basic I/O functions were tremendously helpful in debugging, they are not used actively within the kernel. All printing by the kernel is with the kernel's "printf_" functions. Any basic I/O functions that remain in the code are commented out, but could be used if desired.

KPL typechecks all arguments and, in KPL, the open-ended argument lists used by "printf" cannot be handled. xv6 re-implements "printf" and this became a problem. (KPL "printf" matches the standard C printf with variable argument list. It is implemented as a special case within the compiler, but with xv6, I didn't want to include KPL's "PrintPackage" or modify any existing code.) So, to deal with the kernel's own local definition of "printf", the work-around was to create a collection of "printf_" functions. So, for example, if there are two integer args, we would use "printf_ii", as in
     "printf_ii ("%d %x\n", i, j)".

The Trampoline and Trapframe pages are completely eliminated. They, and the complexity they bring, is simply not necessary in the Blitz architecture.

In the Risc-V version, a sentinel (or "guard") page just beyond the stack is used to detect stack overflow errors. In Blitz, stack overflow is always checked by the hardware, using the "StackLimit" in the status register. Therefore, these guard pages have been eliminated.

In the C version, an exception in the user-level program will cause a terse message and the killing of the process. In the Blitz version, an error will invoke the "debugger" function (which does not exist in the Risc-V version). The debugger code will print out detailed information about the cause of the error, the activation stack, and the local variables in the currently active functions. This was a godsend. The user-level debugger code has been included into the xv6 kernel. It is rather lengthy, but very useful.

The Blitz version includes a heap, which is not used by xv6. However, whenever a user-level program has an error, the debugger code will load all the debugging info from the .exe file and build a rather complex data structure. This will allow the debugger the print the location of the error and the call stack. The heap is only used by the debugger for building this data structure. This heap is completely separate from the pool of pages managed by kalloc.

In Blitz, all executable files have names ending with the ".exe" extension. The shell automatically adds this to any command.

In the Risc-V version, the kernel has a page table of its own. In the Blitz-64 architecture, this is unnecessary and is eliminated. The functions kvminit() and kvminithart() have been eliminated since the kernel doesn't need a page table in Blitz.

The page size in xv6/Risc-V is 4096 bytes. In xv6/Blitz, the page size is 16K bytes. On the disk, things are the same for both implementations: Sectors are 512 byte and Blocks are 1024 bytes.

In Risc-V, there is a distinction between "Machine Mode" and "Supervisor Mode". This doesn't exist in Blitz-64, so all the machine-mode and software interrupt stuff is eliminated.

Startup is a little simpler in the Blitz version. The "start" routine has been eliminated.

Blitz has a Platform Level Interrupt Controller (PLIC), which channels interrupts from the UART and DISK devices to cores. Blitz does not use any per-core interrupt controller. The function plicinithart() has been eliminated since all PLIC initialization is done in plicinit().

In the C/Risc-V version, struct names usually start with lowercase letter. Following the KPL style conventions in which type names are capitalized, these names now begin with a capital letter. For example, "struct spinlock" becomes "Spinlock".

In the C/Risc-V version, boolean values are given type "int" and assigned 0 and 1. In the Blitz version, the "bool" type is used, along with "true" and "false".

In the C/Risc-V version, null is often written as 0. In the Blitz version, the "null" keyword must be used.

In the C/Risc-V version, the "tp" register contains the core number. In the Blitz version, the cpuid() function accesses the "csr_core" register directly.

In the C/Risc-V version, the symbol "end" was set by the linker to the byte beyond the kernel's code. With Blitz, we are getting "Boot_First_Unused_Addr" from the ROM-based BootLoader.

Each process has its own kernel stack. In the C/Risc-V version, a kernel stack had both a location in physical memory (returned by kalloc) and a virtual address (mapped into a page high in the kernel's virtual space by KSTACK). In the Blitz version, things are simpler: there is only one address.

The "mkfs" has be changed substantially internally, but it still does the same thing.
   
In order to fit the Blitz/KPL style, there are a few minor differences with the disk layout used in xv6/Risc-V:
   All fields in the superblock are now doubleword ints.
      The MAGIC NUMBER is also altered to 8 bytes.
   The "addrs" array in the Dinode struct is now a Blitz array, not a C array.
      This causes Dinode structs to increase from 64 bytes to 80 bytes.
      There is no longer an integral number of Dinodes in each block.
   The "name" array in the Dirent struct is now a Blitz array, not a C array.
      This causes Dirent to increase from 16 bytes to 32 bytes.
   Otherwise, all fields retain the same sizes.

Blitz.exe files tend to be larger than C executables. As a result, the previous max file size was too small. The inode contains an array (addr) of pointers to blocks and the last one points to an indirect block. The block numbers were previously stored as 32 bit values; In the Blitz version, these are modified to 16 bit values. Previously, we could accommodate disk sizes up to 4G * 1024 bytes = 4TB. Now we can only handle disk sizes up to about 32K * 1,024 byte = 32 Mbytes. But since disk.img is typically 6000 blocks * 1024 = 6,144,000 bytes, we have room to grow. Of course, a better approach would be to introduce double and triple indirect blocks, but I want to stay as close as possible to the Risc-V xv6.

In the C, we can have things like the following, in which an assignment occurs within an expression:
    if (sz1 = uvmalloc (pagetable, sz, ph->vaddr + ph->memsz, flags2perm (ph->flags))) == 0 {
      ...
    }
This is not allowed in KPL, so this would have to be re-written as:
    sz1 = uvmalloc (pagetable, sz, ph.vaddr + ph.memsz, flags2perm (ph.flags))
    if sz1 == 0
      ...
    endIf

Arguments from user-level code to syscalls use KPL Strings and arrays.



EMULATION PARAMETERS
====================

The Blitz-64 emulator reads a file ("EmulationParms") which contains parameters that control the emulation. This kernel can be run with the following emulation parameters:

    PRIVATE_MEMORY_SIZE             0
    SHARED_MEMORY_SIZE              0x40_0000
    Number of cores                 8
    PLIC_DEVICE_START_ADDR          0x4_0020_0000
    UART0_DEVICE_START_ADDR         0x4_0020_4000
    UART0_INTERRUPT_CHECK_DELAY     500
    IN_RAW_IGNORE_CONTROL_C         0
    TRANSLATE_INPUT_CR_TO_NL        0
    TRANSLATE_OUTPUT_NL_TO_CRNL     1
    DISK0_DEVICE_START_ADDR         0x4_0020_8000
    DISK0_SECTOR_SIZE               512
    DISK0_NUMBER_OF_SECTORS         12000
    DISK0_OPERATION_DELAY           10000
    DEBUG_INVOKES_EMULATOR_K_MODE   1
    DEBUG_INVOKES_EMULATOR_U_MODE   1
    INFINITE_LOOP_CAUSES_HALT       0
    
More shared memory can be used, if needed, but this number (4 Mbytes) is adequate. Private memory must not exist or the kernel will get very confused.

The number of cores must match the NCPU constant. You can either start and run all cores, or start and use only one core, as you wish. Starting all cores will usually slow the emulation by a factor of 8, since most cores are often just idling, looking for a process to run. Nevertheless, the emulator still has to execute those instructions and the emulator is itself only a single-threaded program.

The memory mapped I/O addresses for the PLIC, Disk, and UART devices must match the addresses in xv6.h.

Control-C will stop the emulator and allow debugging of the kernel. If, after pressing control-C, you resume execution with the "go" or "g" command, the xv6 program will see the control-C (i.e., the kernel will retrieve 0x04).

The disk is configured to be 6000 blocks = 12000 sectors, with sector size of 512 and 2 sectors per block. This must match the "BSIZE" and "FSSIZE" constants in fs.h.

The DEBUG statement is very useful when debugging (either kernel or user-level programs), but is not used otherwise. To facilitate debugging of both kernel and user programs, we want to allow the DEBUG instruction to pop up into the emulator's debugger.

Normally, the emulator will detect tight, infinite loops and halt execution. However, xv6 uses these loops intentionally  (e.g., to freeze one core when another core has an error). In order to allow the faulting core to get its message printed, the detection of tight, infinite loops must be disabled.



TESTING
=======

All user-level programs have been tested and execute as expected.

The "usertests" program does extensive testing. I have modified it in a few places and added code to cover cases that the original file did not exercise. The programs "usertests", "grind", "forktest", "stressfs", and "zombie" all work as expected.

In short, the kernel seems to work correctly, without errors or race conditions, although this is a kernel and one can never be sure! Really, a formal proof-of-correctness is needed, but that is well beyond the scope of this project.



TicTacToe
=========

I have included a simple KPL demo program that illustrates several features of KPL, including the "Basic I/O System". It queries the user for moves and uses a search to respond. I/O redirection works properly with the Basic I/O System, but since the TicTacToe program is meant to be interactive, redirection would not normally be wanted.