diff options
| -rw-r--r-- | Boot-explained.txt | 21 | ||||
| -rw-r--r-- | Building-and-running-explained.txt | 64 | ||||
| -rw-r--r-- | Exception-vector-explained.txt | 38 | ||||
| -rw-r--r-- | IRQ-explained.txt | 11 | ||||
| -rw-r--r-- | Makefile | 4 | ||||
| -rw-r--r-- | Makefile-explained.txt | 34 | ||||
| -rw-r--r-- | PSRs-explained.txt | 10 | ||||
| -rw-r--r-- | Project-structure-explained.txt | 100 | ||||
| -rw-r--r-- | Ramfs-explained.txt | 19 | ||||
| -rw-r--r-- | Scheduler-explained.txt | 33 | ||||
| -rw-r--r-- | TODOs | 16 | ||||
| -rw-r--r-- | build/Makefile | 28 | ||||
| -rw-r--r-- | processor-modes-explained.txt | 33 | ||||
| -rw-r--r-- | src/arm/PL1/kernel/interrupt_vector.S | 5 | ||||
| -rw-r--r-- | src/arm/PL1/kernel/interrupts.c | 12 | ||||
| -rw-r--r-- | src/arm/PL1/kernel/kernel.ld | 2 | ||||
| -rw-r--r-- | src/arm/PL1/kernel/kernel_stage2.ld | 2 | ||||
| -rw-r--r-- | src/arm/PL1/kernel/ramfs.c | 27 | ||||
| -rw-r--r-- | src/arm/PL1/kernel/scheduler.c | 4 | ||||
| -rw-r--r-- | src/arm/PL1/loader/loader.ld | 2 | ||||
| -rw-r--r-- | src/arm/common/strings.c | 36 | ||||
| -rw-r--r-- | src/arm/common/strings.h | 6 |
22 files changed, 441 insertions, 66 deletions
diff --git a/Boot-explained.txt b/Boot-explained.txt new file mode 100644 index 0000000..1132f16 --- /dev/null +++ b/Boot-explained.txt @@ -0,0 +1,21 @@ +When RaspberryPi boots, it searches the first partition on SD card (which should be formatted FAT) for it's firmware and configuration files, loads them and executes them. The firmware then searches for the kernel image file. The name of the looked for file can be kernel.img, kernel7.img, kernel8.img (for 64-bit mode) or something else, depending on configuration and firmware used (rpi-open-firmware looks for zImage). The image is then copied to some address (which should be 0x8000 for 32-bit kernel, but is 0x2000000 in rpi-open-firmware and 0x10000 in qemu (version 2.9.1)) and jumped to on all cores. 3 arguments are passed to the kernel: first (passed in r0) is 0; second (passed in r1) is machine type; third (passed in r2) is the address of FDT or ATAGS structure describing the system or 0. +Pis, that support aarch64, can also boot directly into 64-bit mode, in which case the image gets loaded at 0x80000. We're not using 64-bit mode in this project. +Qemu can be used to emulate RaspberryPi, in which case kernel image and memory size are provided to the emulator on the command line. Qemu can also load kernel in the form of an elf file, in which case it's load address is determined based on information in the elf. + +Our kernel has been executed on qemu emulating RaspberryPi 2 as well as on real RaspberryPi 3 running rpi-open firmware (although not every functionality works everywhere). To quicken running new images of the kernel on the board, a simple bootloader has been written by us, which can be run from the SD card instead of the actual kernel. It reads the kernel image from uart, and executes it. The bootloader can also be used within qemu (although there are problems with passing keyboard input to the kernel once it's running). + +Both bootloader and kernel are split into 2 stages. +In case of the loader it is due to the fact, that the the actual kernel read by it from UART is supposed to be written at 0x8000. If the loader also ran from 0x8000 or a cloase address, it could possibly overwrite it's own code while writing kernel to memory. To avoid this, the first stage of the loader first copies it's second stage embedded in it to address 0x4000. Then it jumps to that second stage, which reads kernel image from uart, writes it at 0x8000 and jumps to it. Arguments (r0, r1, r2) are preserved and passed to the kernel. Second stage of the bootloader is intended to be kept small enough to fit between 0x4000 and 0x8000. Atags structure, if present, is guaranteed to end below 0x4000, so it should not get overwritten by loader's stage2. +The loader protocol is simple: first, size of the kernel is sent through UART (4 bytes, little endian). Then, the actual kernel image. Our program pipe_image is used to prepend kernel image with it's size. + +In case of kernel, it is desired to have image run from 0x0, because that's where the interrupt vector table is under default settings. This is also achieved by splitting into 2 stages. Stage 1 is loaded at some higher address. It has second stage image embedded in it. It copies it to 0x0 and jumps to it. What gets more complicated, than in the loader, is the handling of ATAGS structure. Before copying stage 2 to 0x0, stage 1 first checks if atags is present and if so, it is copied to some location high enough, that it won't be overwritten by stage 2 image. Whenever the memory layout is modified, it should be checked, if there is a danger of ATAGS being overwritten by some kernel operations before it is used. In current setup, new location chosen for ATAGS is always below the memory later used as the stack and it might overlap memory later used for translation table, which is not a problem, since kernel only uses ATAGS before filling that table. +When stage 1 of the kernel jumps to second stage, it passes modified arguments: first argument (r0) remains 0 if ATAGS was found and is set to 3 to indicate, that ATAGS was not found. Second argument (r2) remains unchanged. Third argument (r2) is the current address of ATAGS (or remains unchanged if no ATAGS was found). +If support for FDT is added in the future, it must also be done carefully, so that FDT doesn't get overwritten. +At the start of the stage 2 of the kernel, there is the interrupt vector table. It's first entry is the reset vector, which is not normally unused. In our case, when stage 1 jumps to 0x0, to first instruction of stage 2, it jumps to that vector, which then calls the setup routine. + +In both loader and the kernel, at the beginning of stage1 it is ensured, that only one ARM core is executing. + +It's worth noting, that in first stages the loop that copies the embedded second stage is intentionally situated after the blob in the image. This way, this loop will not overwrite itself with the data it is copying, since the stage 2 is always copied to some lower address (to 0x0 in case of kernel and to 0x4000 in case of loader - we assume stage 1 won't be loaded below 0x4000). + +Qemu, stock RaspberryPi firmware and rpi-open-firmware all load image at different addresses. Although stock firmware is not used in this project, our loader loads kernel at 0x8000, where the stock firmware would. Because of that, it is desired, that image is able to run, regardless of where it was loaded at. This was realized by writing first stages of loader and kernel in careful, position-independent assembly. The starting address in corresponding linker scripts is irrelevant. The stage 2 blobs are embedded using .incbin assembly directive. Second stages are written normally in C and compiled as position-dependent for their respective addresses. + diff --git a/Building-and-running-explained.txt b/Building-and-running-explained.txt new file mode 100644 index 0000000..b405d1c --- /dev/null +++ b/Building-and-running-explained.txt @@ -0,0 +1,64 @@ +Dependencies: +1. Native GCC (+ binutils) +2. ARM cross-compiler GCC (+ binutils) (arm-none-eabi works - other ones might or might not) +3. GNU Make +4. rpi-open-firmware (for running on the Pi) +5. GNU screen (for communicating with the kernel when running on the Pi) +6. socat (for communicating with the bootloader when running on the Pi) +7. Qemu ARM (for emulating the Pi). + +For building rpi-open-firmware You will need more tools (not listed here). + +The project has been tested only in Qemu emulating Pi 2 and on real Pi 3. Running on Pis other than Pi 2 and Pi 3 is sure to require changing the definition in global.h (because peripheral base addresses differ between Pi versions) and might also require other modifications, not known at this time. + +Building the project +Assuming make, gcc, arm-none-eabi-gcc and it's binutils are in the PATH, the kernel can be built with: + $ make kernel.img +or: + $ make +The bootloader can be built with: + $ make loader.img + +Both loader and kernel can then be found in build/ + +Running in Qemu +To run the kernel (passed as elf file) in qemu, run: + $ make qemu-elf +If You want to pass a binary image to qemu, run: + $ make qemu-bin +If you want to pass loader image to qemu and pipe kernel to it through emulated uart, run: + $ make qemu-loader +Note, that with qemu-loader the kernel will run, but will be unable to receive any keyboard input. + +The timer used by this project is the ARM timer ("based on an ARM AP804", with registers mapped at 0x7E00B000 in the GPU address space). It's absent in emulated environment, so no timer interrupts can we witnessed in qemu. + +Running on real hardware. +First, build and test rpi-open-firmware. Now, copy either kernel.img or loader.img to the SD card (next to bootcode.bin) and rename it to zImage. Also copy .dtb file corresponding to your Pi (actually, any .dtb will do, because it is not used right now) from stock firmware files to the SD card and name it rpi.dtb. Finally, create a cmdline.txt on the SD card (content doesn't matter). +Now, connect RaspberryPi via UART to Your machine. GPIO on the Pi works with 3.3V, so You should make sure, that UART device on the other end is also working wih 3.3V. This is the pinout of the RaspberyPi 3 model B that has been used for testing so far: + +Top left of the board is here +| +v + ++--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ +| 2| 4| 6| 8|10|12|14|16|18|20|22|24|26|28|30|32|34|36|38|40| ++--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ +| 1| 3| 5| 7| 9|11|13|15|17|19|21|23|25|27|29|31|33|35|37|39| ++--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ + +Under rpi-open-firmware (stock firmware might map UARTs differently): +pin 6 is Ground, +pin 8 is TX, +pin 10 is RX. + +Once UART is connected, You can power on the board. + +Assuming a USB to UART adapter is used and it is seen by Your system as /dev/ttyUSB0: +If You copied the kernel to the SD card, You can start communicating with it by running: + $ screen /dev/ttyUSB0 115200,cs8,-parenb,-cstopb,-hupcl +If You copied the loader, You can send it the kernel image and start communicating with the system by running: + $ make run-on-rpi + +To run again, replug USB to UART adapter and Pi's power supply (order matters!) and re-enter the command. + +Running under stock firmware has not been performed. In particular, the default configuration on RaspberryPi 3 seems to map other UART than used by the kernel (so-called miniUART) to pins 6, 8 and 10. This is supposed to be configurable through the use of overlays. diff --git a/Exception-vector-explained.txt b/Exception-vector-explained.txt new file mode 100644 index 0000000..eb382a2 --- /dev/null +++ b/Exception-vector-explained.txt @@ -0,0 +1,38 @@ +Whenever some illegal operation (attempt to execute undefined instruction, attempt to access memory with insufficient permission, etc.) happens or some peripheral device "messages" the ARM core, that something important happened, an exception occurs. Exception is something, that pauses normal execution and passes control to the (specific part of) operating system. +Upon an exception, several things happen: +1. Processor mode <link to processor-modes-explained.txt> changes. +2. CPSR gets saved into new mode's SPSR <link to PSRs-explained>. +3. pc (incremented by some value) is saved into new mode's lr. +4. Execution jumps to an entry in the exception vectors table specific to the exception. + +Each exception type is taken to it's specific mode. Types and their modes are: +1. Reset and supervisor mode. +2. Undefined instruction and undefined mode. +3. Supervisor call and supervisor mode. +4. Prefetch abort and abort mode. +5. Data abort and abort mode. +6. Hypervisor trap and hypervisor mode (not used normally, only with extensions). +7. IRQ and IRQ mode. +8. FIQ and FIQ mode. + +The new value of the pc (the address, to which the exception "jumps") is the address of nth instruction from exceptiom base address, which, undes simplest settings, is 0x0 (bottom of virtual address space <link to MMU-explained.txt>). N depends on the exception type. It is: +· 1 for reset +· 2 for undefined instruction +· 3 for supervisor call +· 4 for prefetch abort +· 5 for data abort +· 6 for hypervisor trap (not used here) +· 7 for IRQ +· 8 for FIQ + +Those 8 instructions constitute the exception vectors table. As the instruction follow one another, each of them should be a branch to some exception-handling routine. In fact, on other architectures often the exception vector table holds raw addresses of where to jump instead of actual instructions, as here. + +Bottom of virtual address space can be changed to some other value by manipulating the contents of SCTLR and VBAR coprocessor registers. + +On exception entry, the registers r0-r12 contain values used by the code that was executing before. In order for the exception handler to perform some action and return to that code, those registered can be preserved in memory. Some compilers can automatically generate appropriate prologue and epilogue for handler-functions, that will preserve the right registers (see <link to some gcc doc about it>; we're not using this feature in our project). + +Having old CPSR in SPSR and old pc in lr is helpful, when after handling the exception, the handler needs to return to the code that was executing before. There are 2 special instructions, subs and ldm ^ (load multiple with a dash ^), that, when used to change the pc (and therefore perform a jump) cause the SPSR to be copied into CPSR. As bits of CPSR determine the current execution mode, this causes the mode to be change to that from before the exception. In short, subs and ldm ^ are the instructions to use to return from exceptions. + +As noted eariler, upon exception entry an incremented value of pc is stored in lr. By how much it is incremented, depends on exception type and execution state. For example, entering undefined instruction exception for thumb state places in undef's lr the problematic instruction's address + 2, while taking this exception from ARM state places in undef's lr that instruction's address + 4 (see full table in paragraph B1.8.3 of armv7-ar_arm <link here>). + +It's worth noting, that while our implementation of exception handlers (<path to assembly source>) also sets the stack pointer (sp) upon each exception entry, a kernel could be written, where this wouldn't be done, as each mode enterable by exception has it's own sp. diff --git a/IRQ-explained.txt b/IRQ-explained.txt new file mode 100644 index 0000000..871d8a0 --- /dev/null +++ b/IRQ-explained.txt @@ -0,0 +1,11 @@ +2 of possible exceptions in ARM are IRQ (Interrupt Request) and FIQ (Fast Interrupt Request). The can be caused by external source, such as peripheral devices and they can be used to inform the kernel about some action, that happened. + +Interrupts offer an economic way of interacting with peripheral devices. For example, code can probe UART memory-mapped registers in a loop to see whether transmitting/receiving of a character finished. However, this causes the processor needlessly execute the loop and makes it impossible or difficult to perform another tasks at the same time. Interrupt can be used instead of probing to "notify" the kernel, that something it was waiting for just happened. While waiting for interrupt, the system can be put to halt (i.e. wfi instruction), which helps save power, or it can perform other actions without wasting processor cycles in a loop. + +An interrupt, that is normally IRQ, can be made into FIQ by ARM system dependent means. FIQ is meant to be able to be handled faster, by not having to back up registers r8-r12, that FIQ mode has it's own copies of. This project only uses IRQ. + +Some peripheral devices can be configured (through their memory-mapped registers) to generate an interrupt under certain conditions (i.e. UART can generate interrupt when received characters queue fills). The interrupt can then be either masked or unmasked (sometimes in more than one peripheral register). If interrupts are enabled in CPSR and a peripheral device tries to generate one, that is not masked, IRQ (or FIQ) exception occurs (which causes interrupts to be temporarily masked in CPSR). The code can usually check, whether an interrupt of given kind from given device is **pending**, by looking at the appropriate bit of the appropriate peripheral register (mmio). As long as an interrupt is pending, re-enabling interrupts (for example via return from IRQ handler) shall cause the exception to occur again. Removing the source of the interrupt (i.e. removing characters from UART fifo, that filled) doesn't usually cause the interrupt to stop pending, in which case a pending-bit has to be cleared, usually by writing to the appropriate peripheral register (mmio). + +IRQs and FIQs can be configured as vectored - the processor then, upon interrupt, jumps to different location depending on which interrupt occured, instead of jumping to the standard IRQ/FIQ vector <link to exception-vector-explained>. This can be used to speed up interrupt handling. Our simple project does not, however, use this feature. + +Currently, IRQs from 2 sources are used: ARM timer IRQ <link to bcm2835 arm peripherals, so that it is clear, which timer we're talking about> and UART IRQs. The kernel makes sure, that timer IRQ only occurs when processor is in user mode. IRQ handler does not return in this case - it calls scheduler. The kernel makes sure, that UART IRQ only occurs, when a process is blocked and is waiting for UART IO operation. The interrupt handler, when called, checks what type of UART action happened and tries (through calling of appropriate function from scheduler.c) to handle that action and, possibly, to unblock the waiting process. UART IRQ might occur when another process is executing (not possible now, with only one process, but shall be possible when more processes are added to the project), in which case it the handler returns, or when kernel is explicitly waiting for interrupts (because all processes are blocked), in which case it calls schedule() instead of returning. @@ -7,6 +7,10 @@ all : +kernel.img : + +loader.img : + qemu-elf : qemu-bin : diff --git a/Makefile-explained.txt b/Makefile-explained.txt index c199059..0008095 100644 --- a/Makefile-explained.txt +++ b/Makefile-explained.txt @@ -1,3 +1,5 @@ +To maintain order, all files created with the use of make, that is binaries, object files, natively executed helper programs, etc. get placed in build/. + Our project contains 2 Makefiles: one in it's root directory and one in build/. The reason is that it is possible to use Makefile to simply, elegantly and efficiently produce files in the same directory where it is, but to produce files in directory other than Makefile's own, it requires this directory to be specified in many rules across the Makefile and in general it complicates things. Also, a problem arises when trying to link objects not from within the current directory. If an object is referenced by name in linker script (which is a frequent practice in our scripts) and is passed to gcc with a path, then it'd need to also appear with that path in the linker script. Because of that a Makefile in build/ is present, that produces files into it's own directory and the Makefile in project's root is used as a proxy to that first one - it calls make recursively in build/ with the same target it was called with. @@ -10,4 +12,34 @@ All variables discussed below are defined using := assignment, which causes them Objects that should be linked together to create each of the .elf files are listed in their respective variables. I.e. objects to be used for creating kernel_stage2.elf are all listed in KERNEL_STAGE2_OBJECTS. When adding a new source file to the kernel, it is enough to add it's respective .o file to that list to make it compile and link properly. No other Makefile modifications are needed. In a simillar fashion, RAMFS_FILES variable specifies files, that should be put in the ramfs image, that will be embedded in the kernel. Adding another file only requires listing it there. However, if the file is to be found somewhere else that build/, it might be useful to use the vpath directive to tell make where to look for it. -Variables dirs and dirs_colon are defined to +Variables dirs and dirs_colon are defined to store list of all directories within src/, separated with spaces and colons, respectively. dirs_colons are used for vpath directive. dirs are used in ARM_FLAGS to pass all the directories as include search paths to gcc. empty and space are helper variables - defining dirs_colon could be achieved without them (but it's clearer this way). + +The vpath directive tells make to look for assembler sources, C sources and linker scripts in all direct and indirect subdirectories of src/ (including itself). All other files shall be found/created in build/. + +The default target is the binary image of the kernel. + +The generic rule for compiling C sources uses cross-compiler or native compiler with appropriate flags depending on whether the source file is located somewhere under arm/ directory (which lies in src/) or enywhere else. + +The generic rules for making a stripped binary image out of elf file, for assembling an assembly file, for making an arbitrary file a linkable object and for linking objects are ARM-only. + +In C world it is possible to embed a file in an executable by using objcopy to create an object file from it and then linking that object file into the executable. In this project, at the current time, this is used only for embedding ramfs in the kernel (incbin is used for embedding kernel and loader second stages in their first stages), but a generic rule for making a binary image into object file is present in case it is needed somewhere else again. + +To link elf files, the generic rule is combined with a rule that specifies the elf's objects. Objects are listed in variables whenever more than one of them is needed. + +At this point in the Makefile, the dependence of objects created from assebmly on files referenced in the assembly source via incbin is marked. + +Simple ram filesystem is created from files it should contain with the use of our own simple tool - makefs. + +Another 2 rules specifie how native programs (for the machine we're working on) are to be linked. + +Rule qemu-elf runs the kernel in qemu emulating RaspberryPi 2 with 256MiB of memory by passing the elf file of the kernel to the emulator. + +Rule qemu-bin does the same, but passes the binary image of the kernel to qemu. + +Rule qemu-loader does the same, but first passes the binary image of the bootloader to qemu and the actual kernel is piped to qemu's standard input, received by bootloader as uart data and run. This method currently makes it impossible to pass any keyboard input tu the kernel once it's running + +Rule run-on-rpi pipes the kernel through uart, assuming it is available under /dev/ttyUSB0, and then opens a screen session on that interface. This allows for executing the kernel on the Pi connected through UART, provided that our bootloader is running on the board. + +Rule clean removes all the files generated in build/. + +Ruled that don't generate files are marked as PHONY. diff --git a/PSRs-explained.txt b/PSRs-explained.txt new file mode 100644 index 0000000..6d67423 --- /dev/null +++ b/PSRs-explained.txt @@ -0,0 +1,10 @@ +CPSR (Current Program Status Register) is a register, bits of which contain and/or determine various aspects of execution, i.e. condition flags, execution state (arm, thumb or jazelle), endianness state, execution mode <link to doc explaining modes> and interrupt mask. This register is readable and writeable with the use of mrs and msr instructions from any PL1 mode, thus it is possible to change things like mode or interrupt mask by writing to this register. +Additionally, there are other registers with the same or simillar bit fields as CPSR. Those PSRs (Program Status Registers) are: +· APSR (Application Program Status Register) +· SPSRs (Saved Program Status Registers) + +APSR is can be considered the same as CPSR or a view of CPSR, with some limitations - some bit fields from CPSR are missing (reserved) in APSR. APSR can be accessed from PL0, while CPSR should only be accessed from PL1. This was an application program executing in user mode can learn some of the settings in CPSR without accessing CPSR directly. + +SPSR is used for exception handling. Each exception-taking mode has it's own SPSR (they can be called SPSR_sup, SPSR_irq, etc.). On exception entry, old contents of CPSR are backed up in entered mode's SPSR. Instructions used for exception return (subs and ldm ^), when writing to the pc, have the important additional effect of copying the SPSR to CPSR. This way, on return from an exception, processor returns to the state from before the exception (this includes endianness settings, execution state, etc.). + +In our project, the structure of PSRs is defined in terms of C bitfield structs in src/arm/PL1/kernel/psr.h. diff --git a/Project-structure-explained.txt b/Project-structure-explained.txt new file mode 100644 index 0000000..131e36b --- /dev/null +++ b/Project-structure-explained.txt @@ -0,0 +1,100 @@ +Directory structure of the project: + +doc/ +build/ + Makefile +Makefile +src/ + lib/ + rs232/ + rs232.c + rs232.h + host/ + pipe_image.c + makefs.c + arm/ + common/ + svc_interface.h + strings.c + io.h + io.c + strings.h + PL0/ + PL0_utils.h + svc.S + PL0_utils.c + PL0_test.c + PL0_test.ld + PL1/ + loader/ + loader_stage2.ld + loader_stage2.c + loader_stage1.S + loader.ld + kernel/ + demo_functionality.c + paging.h + setup.c + interrupts.h + interrupt_vector.S + kernel.ld + scheduler.h + atags.c + translation_table_descriptors.h + bcmclock.h + ramfs.c + kernel_stage1.S + paging.c + ramfs.h + interrupts.c + armclock.h + atags.h + kernel_stage2.ld + cp_regs.h + psr.h + scheduler.c + memory.h + demo_functionality.h + PL1_common/ + global.h + uart.h + uart.c + + +Meaning of significant directories and files: + +doc/ +Contains documentation of the project. + +build/ +Contains main Makefile of the project. All objects created during the build process are placed there. + +Makefile +Proxies all calls to Makefile in build/. + +src/ +Contains all sources of the project. + +src/host/ +Contains sources of helper programs to be compiled using native GCC and run on the machine where development takes place. + +src/arm/ +Contains sources to be compiled using ARM cross-compiler GCC and run on the RaspberryPi. + +src/arm/common +Contains sources used in both: privileged mode and unprivileged mode. + +src/arm/PL0 +Contains sources used exclusively in unprivileged, user-mode (PL0) program, as well as the program's linker script. + +src/arm/PL1 +Contains sources used exclusively in privileged (PL1) mode. + +src/arm/PL1/loader +Contains sources used exclusively in the bootloader, as well as linker scripts for stages 1 and 2 of this bootloader. + +src/arm/PL1/kernel +Contains sources used exclusively in the kernel, as well as linker scripts for stages 1 and 2 of this kernel. + +src/arm/PL1/PL1_common +Contains sources used in both: kernel and bootloader. diff --git a/Ramfs-explained.txt b/Ramfs-explained.txt new file mode 100644 index 0000000..da70cb5 --- /dev/null +++ b/Ramfs-explained.txt @@ -0,0 +1,19 @@ +A simple ram file system has been introduced to avoid having to embed too many files in the kernel in the future. + +The ram filesystem is created on the development machine and then embedded into the kernel. Kernel can then parse the ramfs and access files, that have been put in it. + +Ramfs contains a mapping from file's name to it's size and contents. Directories, file permissions, etc. as well as writing to filesystem are not supported. + +Currently this is used to access the code of PL0 test program by the kernel, which it then copies to the appropriate memory location. In case more user mode programs are later written, they can all be added to ramfs to enable the kernel to access them easily. + +Specification +When ramfs is accessed in memory, it MUST be aligned to a multiple of 4. +The filesystem itself consists of blocks of data, each containing one file. Blocks of data in the ramfs come one after another, with the requirement, that each block starts at a 4-aligned offset/address. If a block doesn't end at a 4-aligned address, there shall be up to 3 null-bytes of padding after it, so that the next block is properly aligned. +Each block start with a C (null-terminated) string with the name of the file it contains. At the first 4-aligned offset after the string, file size is stored on 4 bytes in little endian. Null-bytes are used for padding between file name and file size if necessary. Immediately after the file size reside file contents, that take exactly the amount of bytes specified in file size. + +As obvious from the specification, files bigger than 4GB are not supported, which is not a problem in the case of this project. + +Implementations +Creation of ramfs is done by the makefs program (src/host/makefs.c). The program accepts file names as command line arguments, creates a ramfs containing all those files and writes it to stdout. As makefs is a very simple tool (just as our ramfs is a simple format), it puts files in ramfs under the names it got on the command line. No stripping or normalizing of path is performed. In case of errors (i.e. io errors) makefs prints information to stderr and exits. +Parsing/Reading of ramfs is done by a kernel driver (src/arm/PL1/kernel/ramfs.c). The driver allows for finding a file in ramfs by name. File size and pointers to file name string and file contents are returned through a structure from function find_file. +As ramfs is embedded in kernel image, it is easily accessible to kernel code. The alignment of ramfs to a multiple of 4 is assured in kernel's linker script (src/arm/PL1/kernel/kernel_stage2.ld). diff --git a/Scheduler-explained.txt b/Scheduler-explained.txt new file mode 100644 index 0000000..efaf2c0 --- /dev/null +++ b/Scheduler-explained.txt @@ -0,0 +1,33 @@ +An operating system has to manage user processes. Our system only has one process right now, but usual actions, such as context saving or context restoring, are implemented anyways. The following few paragraphs contain information on how process management looks like in operating systems in general. + +Process might return control to the system by executing the svc (eariler called swi) instruction. System would then perform some action on behalf of the process and either return from the supervisor call exception or attempt to schedule another process to run, in which case context of the old process would need to be saved for later and context of the new process would need to be restored. + +Process has data in memory (such as it's stack, code) as well as data in registers (r0-r15, CPSR). Together they constitute process' context. From process' perspective, context should not unexpectedly change, so when control is taken away from user mode code (via an exception) and later (possibly after execution of some other processes) given back, it should be transparent to the process (except when kernel does something for the process in terms of supervisor call). In particular, the contents of core registers should be the same as before. For this to be achievable, the operating system has to back up process' registers somewhere in memory and later restore them from that memory. + +Operating system kernel maitains a queue of processes waiting for execution. When a process blocks (for example by waiting for IO), it is removed from the queue. If a process unblocks (for example because IO completed) it is added back to the queue. In general, some systems might complicate it, for example by having more queues, but discussing those variations is out of scope of this documentation. When processor is free, one of the processes from the queue (determined by some scheduling algorithm <link to wikipedia??> implemented in the kernel) gets chosen and run on the processor. + +As one process could never use a supervisor call, it could occupy the processor forever. To remedy this, timer interrupts can be used by the kernel to interrupt the execution of a process after some time. The process would then have it's context saved and go to the end of the queue. Another process would be scheduled to run. + +Other exceptions might occur when process is running. Depending on kernel design, handler of an exception (such as IRQ) might return to the process or cause another one to be scheduled. + +If at some time all processes are blocked waiting, the kernel can wait for some interrupt to happen, which could possibly unblock some process (i.e. because IO completed). + +While not mentioned earlier, switching between processes' contexts involves not only saving and restoring of registers, but also changing the translation table entries to properly map memory regions used by current process. + +In our project, process management is implemented in src/arm/PL1/kernel/scheduler.c. + +A "queue" contains data of the only process (variables PL0_regs[], PL0_sp, PL0_lr and PL0_PSR). + +Function setup_scheduler_structures is supposed to be called before scheduler is used in any way. +Function schedule_new() creates and runs a new process. +Function schedule_wait_for_output() causes the current process to have it's context saved and get blocked waiting for UART to send data. It is called from supervisor call handler. Function schedule_wait_for_input() is simillar, but process waits for UART to receive data. +Function schedule() attempts to select a process (currently the only one) and run it. If process cannot be run, schedule() waits for interrupt, that could unblock the process. The interrupt handler would not return in this case, but rather call schedule() again. +Function scheduler_try_output() is supposed to be called by IRQ handler when UART is ready to transmit more data. It can cause a process to get unblocked. scheduler_try_input() is simillar, but relates to receiving data. + +The following are assured in our design: +1. When processor is in user mode, interrupts are enabled. +2. When processor is in system mode, interrupts are disabled, except when explicitly waiting for the interrupt when process is blocked. +3. When a process is waiting for input/output, the corresponding IRQ is unmasked. Otherwise, that IRQ is masked. +4. If an interrupt from UART occurs during execution of user mode code (not possible here, as we only have one process, but shall become possible when proper processes are implemented), the handler shall return. If that interrupt occurs during execution of PL1 code, it means it occured in scheduler, that was implicitly waiting for it and the handler calls scheduler() again instead of returning. +5. Interrupt from timer is unmasked and set to come whenever a process gets scheduled to run. Timer interrupt is disabled when in PL1 (when scheduler is waiting for interrupt, only UART one can come). +6. A supervisor call requesting an UART operation, that can not be completed immediately, causes the process to block. @@ -10,10 +10,10 @@ high priority TODOs are higher; low priority ones and completed ones are lower; · VERY NAUGHTY PROBLEM · Many sources mention /COMMON/ as the section, that contains some specific kind of uninitialized (0-initialized) data. Obviously, it has to be included in the linker script. Unfortunately, gcc names it differently, mainly - /COM/. This caused our linker script to not include it in the image. Instead, it was placed somewhere after the last section specified in the linker script. This happened to be after our NOLOAD stack section, where first free MMU section is (which happens to always get allocated to the first process, which gets it's code copied there). Do You imagine sitting for hours in front of radare2, searching for a bug in scheduler.c or PL0_test.c, that causes the userspace code to fail with either some kind of weird abort or undefined instruction, always on the second PL0 instruction!? · VERY NAUGHTY PROBLEM · I wanted to make our bootloader and kernel able to run no matter what address they are loaded at (see comment in kernel's stage1 linker script). To achieve that, I added -fPIC to compilation options of all arm code. With this, I decided I can, instead of embedding code in other code using objcopy, just put that code in separate linker script section with section_start and section_end symbols defined, so that I can copy it to some other address in runtime. I did it and it worker with interrupt vector and libkernel (see point below). But once I changed EVERYTHING to use linker symbols/sections instead of objcopy embedding it turned out it doesn't really work... and I had to make it back the old way :( The thing is -fPIC requires code to be loaded by some os or bootloader, that will fill the global offset table with symbols. I knew it's possible to generate bare-metal position-independent code, that shall work without got, but it turned out this is not implemented in gcc (it is in arm compiler, but only in 32-bits and who would like to use arm compiler anyway). I ended up writing stage1 of both bootloader and the kernel in careful position-independent assembly, thus achieving my goal (jut with a bit more of effort). · Linker behaves weird when section names don't start with .text, .data, etc. - · Not strictly a problem, but a funny mistake of mine, that is worth mentioning... At first I didn't know about special features of SUBS pc, lr and ldm rn {pc} ^ instructions. So I would switch to user mode by first branching to code in PL0-accessible section and having it execute isb instruction. This worked, but was not good, because code executed by the kernel was in memory section writable by userspace code. So i separated that into "libkernel", that would be in a PL0-executable but non-writable section and would perform the switch... Well, it did work. Still, I was happy when I learned how to achieve the same with subs/ldm and could remove libkrnel, making the project a bit simpler. + · Not strictly a problem, but a funny mistake of mine, that is worth mentioning... At first I didn't know about special features of SUBS pc, lr and ldm rn {pc} ^ instructions. So I would switch to user mode by first branching to code in PL0-accessible section and having it execute isb instruction. This worked, but was not good, because code executed by the kernel was in memory section writable by userspace code. So i separated that into "libkernel", that would be in a PL0-executable but non-writable section and would perform the switch... Well, it did work. Still, I was happy when I learned how to achieve the same with subs/ldm and could remove libkernel, making the project a bit simpler. · system mode has separate stack pointer from supervisor mode, so when going from supervisor to system we need to set it... We didn't know that and we were getting weeeird bugs (where changing something little in one place would make the bug occur or not occur somewhere completely else); also, it's not allowed (undefined behaviour) to switch from system mode directly to user mode... (at least this didn't cause such weird things to happen...) · both bcm arm peripherals manual and the manual to uart itself say, that writing 0s to PL011_UART_IMSC unmasks interrupts; its the opposite: writing 1s enables specific interrupts and writing 0s disables them. wiki.osdev code also got it the way it's written in those docs, but this didn't cause problems, since uart irq was not enabled in ARM_ENABLE_IRQS_2 (using #define names from our code), so, as intended, no irq was occuring - · STILL UNFIXED · The very simple pipe_image program somehow manages to break stdin, so that even other programs run in that same (bash) shell can't read from it... (in zsh other interactively run commands work ok, but command following pipe_image inside a shell function still have that problem) + · STILL UNFIXED · The very simple pipe_image program somehow manages to break stdin, so that even other programs run in that same (bash) shell can't read from it... (in zsh other interactively run commands work ok, but commands following pipe_image inside a shell function still have that problem) - Our sources of information · wiki.osdev (good for starting off, we could also (in a polite way) mention the things, that were broken there) > getting uart irq masking wrong (not really their fault, see above) @@ -28,12 +28,20 @@ high priority TODOs are higher; low priority ones and completed ones are lower; · online ARM Compiler toolchain Assembler Reference · Christina Brook's rpi-open-firmware · http://infocenter.arm.com/help/topic/com.arm.doc.ddi0183g/DDI0183G_uart_pl011_r1p5_trm.pdf + · GNU make documentation + · description of linker scripts: https://access.redhat.com/documentation/en-US/Red_Hat_Enterprise_Linux/4/html/Using_ld_the_GNU_Linker/sections.html#OUTPUT-SECTION-DESCRIPTION - Once we get rid of other ppl's code (there was more, now only a little bit in uart.c remains) boast, that we wrote everything bu ourselves - maybe some special thanks (i.e. to gcc devs? idk) !!! IMPORTANT !!! * Add license (Unlicense?) +!!! IMPORTANT !!! +* Call them exceptions, not interrupts. + +! A bit important ! +* Also implement the generic timer and use it, as it's probably going to run on both qemu and RPi. + * inform linux errata guys about incorrecty-described uart irq masking in bcm arm perif manual * maybe add some comments in code (would do with some feedback from someone who didn't write this, as to what is unclear) @@ -58,6 +66,10 @@ high priority TODOs are higher; low priority ones and completed ones are lower; * In the Makefile: is =? the right assignment for, say, CFLAGS? +* Reintroduce checking if size of loader_stage2.img is small enough in Makfile (removed by accident). + +* Check if setting user mode's sp and lr can be achieved by msr instead of switching to system mode. If so, use this method. + * partially DONE - one can always add more, but we have the most important stuff * Implement some basic utilities for us to use (memcpy, printf, etc...) * partailly DONE - svc works; once we implement processes we could also kill them on aborts * develop userspace process supervision (handling of interrupt caused by svc instruction, proper handling of other data abort, undefined instruction, etc.) diff --git a/build/Makefile b/build/Makefile index b5257fe..53f8c98 100644 --- a/build/Makefile +++ b/build/Makefile @@ -15,6 +15,7 @@ ARM_OBJCOPY ?= $(ARM_BASE)-objcopy ARM_ELFFLAGS ?= -nostdlib -lgcc + KERNEL_STAGE2_OBJECTS := setup.o interrupt_vector.o interrupts.o \ uart.o demo_functionality.o paging.o ramfs_embeddable.o \ ramfs.o strings.o io.o atags.o scheduler.o @@ -25,6 +26,7 @@ LOADER_STAGE2_OBJECTS := uart.o strings.o io.o loader_stage2.o RAMFS_FILES := PL0_test.img + empty:= space:= $(empty) $(empty) @@ -34,8 +36,10 @@ vpath %.S $(dirs_colon) vpath %.c $(dirs_colon) vpath %.ld $(dirs_colon) + all : kernel.img + %.o : %.c $(if $(findstring /arm/,$<),\ $(ARM_CC) $(ARM_CFLAGS),$(HOST_CC) $(HOST_CFLAGS)) -c $< -o $@ @@ -52,6 +56,7 @@ all : kernel.img %.elf : %.ld $(ARM_CC) -T $< -o $@ $(ARM_ELFFLAGS) $(filter %.o,$^) + PL0_test.elf : $(PL_0_TEST_OBJECTS) kernel.elf : kernel_stage1.o @@ -62,10 +67,23 @@ loader_stage2.elf : $(LOADER_STAGE2_OBJECTS) loader.elf : loader_stage1.o + kernel_stage1.o : kernel_stage2.img loader_stage1.o : loader_stage2.img + +ramfs.img : makefs $(RAMFS_FILES) + ./makefs $(RAMFS_FILES) > $@ + + +pipe_image : pipe_image.o rs232.o + $(HOST_CC) $^ -o $@ + +makefs : makefs.o + $(HOST_CC) $^ -o $@ + + qemu-elf : kernel.elf qemu-system-arm -m 256 -M raspi2 -serial stdio -kernel $^ @@ -81,16 +99,8 @@ run-on-rpi : kernel.img pipe_image sudo socat FILE:/dev/ttyUSB0,b115200,raw - sudo screen /dev/ttyUSB0 115200,cs8,-parenb,-cstopb,-hupcl -pipe_image : pipe_image.o rs232.o - $(HOST_CC) $^ -o $@ - -makefs : makefs.o - $(HOST_CC) $^ -o $@ - -ramfs.img : makefs $(RAMFS_FILES) - ./makefs $(RAMFS_FILES) > $@ clean : -rm -f *.img *.elf *.o pipe_image makefs -.PHONY: all qemu-elf qemu-bin clean +.PHONY: all qemu-elf qemu-bin qemu-loader run-on-rpi clean diff --git a/processor-modes-explained.txt b/processor-modes-explained.txt new file mode 100644 index 0000000..d6f04c3 --- /dev/null +++ b/processor-modes-explained.txt @@ -0,0 +1,33 @@ +ARMv7-A core can be executing in one of several modes (not to be confused with instruction set states or endianness execution state). Those are: +1. User +2. FIQ +3. IRQ +4. Supervisor +5. Abort +6. Undefined +7. System + +In fact, there are more if the processor implements some extensions, but this is irrelevant here. + +Current processor mode is encoded in the lowest five bits of the CPSR <link to PSR-explained.txt> register. + +Processor can operate in one of 2 privilege levels (although, again, extensions exist, that add more levels): + · PL0 - privilege level 0 + · PL1 - privilege level 1 + +Processor modes have their assigned privilege levels. User mode has privilege level 0 and all other modes have privilege level 1. Code executing in one of privileged modes is allowed to do more things, than user mode code, i.e. writing and reading some of the coprocessor registers, executing some privileged instructions (i.e. mrs and msr, when used to reference CPSR, as well as other modes' registers), accessing privileged memory and changing the mode (without causing an interrupt). Attempts to perform those actions in user mode result either in undefined (within some limits) behaviour or an exception (depending on what action is considered). + +User mode is the one, in which application programs usually run. Other modes are usually used by the operating system's kernel. Lack of privileges in user mode allows PL1 code to control execution of PL0 code. + +While code executing in PL1 can freely (except switching from system to user mode, which produces undefined behaviour) change mode by either writing the CPRS or executing cps instruction, user mode can only be exitted by means of an interrupt. + +Some ARM core registers (i.e. r0 - r7) are shared between modes, while some are not. In this case, separate modes have their private copies of those registers. For example, lr and sp in supervisor mode are different from lr and sp in user mode. For full information about shared and not shared (banked) registers, see paragraph B9.2.1 in amrv7ar_arm <put a link here>. The most important things are that user mode and system mode share all registers with each other and they don't have their own SPSR (which is used for returning from exceptions <link to interrupt-vector-explained.txt> and exceptions are never taken to those 2 modes) and that all other modes have their own SPSR, sp and lr. +The reason for having multiple copies of the same register in different modes is that it simplifies writing interrupt handlers. I.e. supervisor mode code can safely use sp and lr without destroying the contents of user mode's sp and lr. + +The big number of PL1 modes is supposed to aid in handling of interrupts. Each kind of interrupt is taken to it's specific mode, as detailed in <Interrupt-vector-explained.txt zlinkować>. + +Supervisor mode, in addition to being the mode supervisor calls are taken to, is the mode the processor is in when the kernel boots. + +System mode, which uses the same registers as user mode, is said to have been added to ARM architecture to ease accessing the unprivileged registers. For example, setting user mode's sp from supervisor mode can be done by switching to system mode, setting the sp and switching back to supervisor mode. Other modes' registers can alternatively be accessed with the use of mrs and msr assembly instructions (but not from user mode). + +Despite the name, system mode doesn't have to be the mode used most often by operating system's kernel. In fact, prohibition of direct switching from system mode to user mode would make extensive use of system mode inpractical <is it inpractical or impractical?>. This project, for example, uses supervisor mode for most of the privileged tasks. diff --git a/src/arm/PL1/kernel/interrupt_vector.S b/src/arm/PL1/kernel/interrupt_vector.S index 1ec80f7..3afc193 100644 --- a/src/arm/PL1/kernel/interrupt_vector.S +++ b/src/arm/PL1/kernel/interrupt_vector.S @@ -8,9 +8,12 @@ _interrupt_vectors: b irq_handler_caller b fiq_handler_caller +// from what I've heard, reset is never used on the Pi; +// in our case it should run once - when stage1 of the kernel +// jumps to stage2 reset_handler_caller: ldr sp, =_supervisor_stack_top - ldr r5, =reset_handler + ldr r5, =setup bx r5 undef_handler_caller: diff --git a/src/arm/PL1/kernel/interrupts.c b/src/arm/PL1/kernel/interrupts.c index 5695e6f..6f61615 100644 --- a/src/arm/PL1/kernel/interrupts.c +++ b/src/arm/PL1/kernel/interrupts.c @@ -4,17 +4,6 @@ #include "armclock.h" #include "scheduler.h" -// defined in setup.c -void __attribute__((noreturn)) setup(void); - -// from what I've heard, reset is never used on the Pi; -// in our case it should run once - when stage1 of the kernel -// jumps to stage2 -void reset_handler(void) -{ - setup(); -} - void undefined_instruction_vector(void) { error("Undefined instruction occured"); @@ -85,6 +74,7 @@ void irq_handler(uint32_t regs[14]) if (read_SPSR().fields.PSR_MODE_4_0 != MODE_USER) { + // TODO set supervisor mode's stack pointer write_SPSR(PL1_PSR); asm volatile("mov lr, %0\n\r" "subs pc, lr, #0" :: diff --git a/src/arm/PL1/kernel/kernel.ld b/src/arm/PL1/kernel/kernel.ld index 3130634..5ccce06 100644 --- a/src/arm/PL1/kernel/kernel.ld +++ b/src/arm/PL1/kernel/kernel.ld @@ -16,7 +16,7 @@ ENTRY(_boot) /* defined in boot.S; qemu needs it to run elf file */ SECTIONS { - . = 0x8000; + . = 0x8000; /* irrelevant */ __start = .; .kernel_stage1 : diff --git a/src/arm/PL1/kernel/kernel_stage2.ld b/src/arm/PL1/kernel/kernel_stage2.ld index 9411ca2..2858355 100644 --- a/src/arm/PL1/kernel/kernel_stage2.ld +++ b/src/arm/PL1/kernel/kernel_stage2.ld @@ -1,4 +1,4 @@ -/* This sesond stage of the kernel is run from address 0x0 */ +/* This second stage of the kernel is run from address 0x0 */ TRANSLATION_TABLE_SIZE = 4096 * 4; SECTIONS_LIST_SIZE = 4096 * 8; diff --git a/src/arm/PL1/kernel/ramfs.c b/src/arm/PL1/kernel/ramfs.c index cc66b4c..ed3ff73 100644 --- a/src/arm/PL1/kernel/ramfs.c +++ b/src/arm/PL1/kernel/ramfs.c @@ -3,32 +3,7 @@ #include <stdint.h> #include "ramfs.h" - -static int strcmp(char const *str1, char const *str2) -{ - while (1) - { - int c1 = (unsigned char) *str1, c2 = (unsigned char) *str2; - - if (!c1 && !c2) - return 0; - - if (c1 != c2) - return c1 - c2; - - str1++; str2++; - } -} - -static uint32_t strlen(char const *str1) -{ - uint32_t len = 0; - - while (str1[len]) - len++; - - return len; -} +#include "strings.h" static inline char *align4(char *addr) { diff --git a/src/arm/PL1/kernel/scheduler.c b/src/arm/PL1/kernel/scheduler.c index 141ba1d..1db8078 100644 --- a/src/arm/PL1/kernel/scheduler.c +++ b/src/arm/PL1/kernel/scheduler.c @@ -24,7 +24,7 @@ _Bool waiting_for_input = 0; _Bool waiting_for_output = 0; char waiting_output; -// 0 is kernel code in system mode is being run +// 0 if kernel code in system mode is being run // 1 if our process is being run // later when we have many processes and this will hold process id uint32_t current_process; @@ -126,7 +126,7 @@ void __attribute__((noreturn)) schedule(void) write_CPSR(new_CPSR); - asm volatile("wfi"); + asm volatile("wfi" ::: "memory"); __builtin_unreachable(); } diff --git a/src/arm/PL1/loader/loader.ld b/src/arm/PL1/loader/loader.ld index 711fcbf..7ab846a 100644 --- a/src/arm/PL1/loader/loader.ld +++ b/src/arm/PL1/loader/loader.ld @@ -2,7 +2,7 @@ ENTRY(_boot) SECTIONS { - /* see linker.ld for details */ + /* irrelevant, see linker.ld for details */ . = 0x2000000; __start = .; diff --git a/src/arm/common/strings.c b/src/arm/common/strings.c index 368d7dc..0c7a73b 100644 --- a/src/arm/common/strings.c +++ b/src/arm/common/strings.c @@ -69,15 +69,6 @@ void uint32_to_hexstringt(uint32_t number, char buf[9]) trim_0s(buf); } -size_t strlen(char string[]) -{ - size_t len; - - for (len = 0; string[len]; len++); - - return len; -} - void memcpy(void *dst, void *src, size_t nbytes) { size_t iter; @@ -117,3 +108,30 @@ char *strcat(char *dst, const char *src) return dst; } + +int strcmp(char const *str1, char const *str2) +{ + while (1) + { + int c1 = (unsigned char) *str1, c2 = (unsigned char) *str2; + + if (!c1 && !c2) + return 0; + + if (c1 != c2) + return c1 - c2; + + str1++; str2++; + } +} + +size_t strlen(char const *str1) +{ + size_t len = 0; + + while (str1[len]) + len++; + + return len; +} + diff --git a/src/arm/common/strings.h b/src/arm/common/strings.h index aff0533..67c1ab7 100644 --- a/src/arm/common/strings.h +++ b/src/arm/common/strings.h @@ -22,12 +22,14 @@ void uint32_to_decstringt(uint32_t number, char buf[11]); void uint32_to_hexstringt(uint32_t number, char buf[9]); -size_t strlen(char string[]); - void memcpy(void *dst, void *src, size_t nbytes); void *memset(void *s, int c, size_t n); char *strcat(char *dst, const char *src); +int strcmp(char const *str1, char const *str2); + +size_t strlen(char const *str1); + #endif // STRINGS_H |