Lab 08

NCTU OSDI Lab 8: File System Meets Hardware

Documentation: Lab 8

Lab 8 Demo Release

Required

• Required 1
  • Get the FAT32 partition.
  • Parse the FAT32’s metadata and set up the mount.
• Requried 2
  • Look up and open a file in FAT32.
  • Read/Write a file in FAT32.

Elective

• Elective 1
  • Create a file in FAT32.
• Elective 2
  • Implement a FAT32 with LFN support. You should create/lookup a file with special characters(e.g. Chinese) in its name.
• Elective 3
  • Implement a mechanism that each device can register itself to a VFS.
  • Implement a VFS interface and a tmpfs method for int mknod(const char* pathname, int dev_id)
  • Create a sdcard device file. A user can read or write an SD card by reading or writing its device file.
  • Create a UART device file as the console, A user can get/print characters from/to console by reading or writing its device file.
• Elective 4
  • Implement a component name cache mechanism for faster pathname lookup.
  • Implement a page cache mechanism for faster file read and write.
  • Implement a VFS interface and a FAT32 method for int sync()

Questions

• Explain how an OS supports automatically mounting file systems after plug in a USB flash drive into a computer.
• How to implement a component cache mechanism if a file has multiple names (because of hard links)
• Does tmpfs need sync method?

Lab 07

NCTU OSDI Lab 7: Virtual File System

Documentation: Lab 7

Lab 7 Demo Release

Required

• Required 1
  • Set up tmpfs as the root file system.
• Requried 2
  • implement struct file* vfs_open(const char *pathname, int flags)
  • implement int vfs_close(struct file* file)
• Required 3
  • Implement int vfs_write(struct file* file, const void* buf, size_t len)
  • Implement int vfs_read(struct file* file, void* buf, size_t len)

Elective

• Elective 1
  • Implement an API for users to get the directory entries information from a directory.
• Elective 2
  • Implement file descriptor table for tasks.
  • Implement VFS system calls.
• Elective 3
  • Implement a VFS interface and a tmpfs method for int mkdir(const char* pathname).
  • Implement int chdir(const char* pathname)
  • Implement VFS interfaces and tmpfs methods for int mount(const char* device, const char* mountpoint, const char* filesystem) and int umount(const char* mountpoint).
    Implement pathname lookup.
• Elective 4
  • The procfs creates switch and hello file in its root directory. Users can access them by open, read, and write.
  • The procfs lazily updates the task-related directory and file. Users can read task’s status by reading <task id>/status
• Elective 5
  • Implement initramfs to populate the root file system.

Questions

• Is it possible that a file exists in a file system, but there is no vnode object of it?
• Is EOF pass to the reader by a special character in the reader’s buffer?
• Should each task owns its current working directory and the root directory?

Lab 06

NCTU OSDI Lab 6: Allocator

Documentation: Lab 6

Lab 6 Demo Release

Required

• Required 1
  • Implement the buddy system for contiguous pages allocation.
• Requried 2
  • Implement the API for register a fixed-size allocator.
  • Implement the API for allocate and free for fixed-size object.
• Required 3
  • Implement a varied-sized allocator.

Elective

• Elective 1
  • Implement the startup allocator.
• Elective 2
  • Replace the static memory allocator with the dynamic memory allocator in your kernel.

Questions

• Is buddy allocator perfectly eliminate external fragmentation? If yes, prove it? If no, give an external fragmentation example.
• If the registered object size is 2049 byte, one page frame can only fit in one object. Hence the internal fragmentation is around 50%. How to decrease the percentage of the internal fragmentation in this case?
• What’s the benefit to prevent static allocation?

Lab 05

NCTU OSDI Lab 5: Virtual memory

Documentation: Lab 5

Lab 5 Demo Release

Required

• Required 1
  • Set up TCR_EL1.
  • Set up MAIR_EL1.
  • Set up identity mapping.
  • Modify linker script and map the upper address space.
  • Linear map kernel with finer granularity and map RAM as normal memory.
• Requried 2
  • Implement page bookkeeping.
  • Implement the translation function between kernel virtual address, physical address, PFN and the reference to struct page.
  • Implement page_alloc and page_free.
• Required 3
  • Implement user space paging.
  • Implement a minimum user library.
  • Implement shell as an user program and use objcopy to turn the ELF file into a raw binary.
  • Embed your shell binary to kernel image.
  • Allocate one page frame for user stack and map user task’s stack to the common address.
  • Set TTBR0_EL1 to switch between different address space when context switch.
• Required 4
  • Implement page frame reclaim.
  • Implement simple page fault handler.

Elective

• Elective 1
  • Implement mmap for creating a new region.
  • Implement Region page mapping.
• Elective 2
  • Parse the ELF header.
  • Implement ELF mapping.
• Elective 3
  • Implement demand paging.
• Elective 4
  • Implement copy-on-write.

Questions

• Without indirect branch, the code might still work fine, why it’s the case and why it’s mandatory to use indirect branch.
• For mapping 1GB memory region, how many page frames are used by page tables(PGD, PUD, PMD, and PTE) in four level translation?
• If a page frame is allocated and to be mapped at user space. Is it necessary to initialize it into 0?

Lab 03

NCTU OSDI Lab 3: Exception and Interrupt

Documentation: Lab 3

Implement ISR for PL011 UART

Required

• Required 1
  • Set up the exception vector table.
  • Implement the exception handler for Synchronous Exceptions from the currentEL while using SP_ELx (offset 0x200-0x280 in the vector table).
  • Add an exc command to the shell. It issues svc #1 and then your exception handler should print the return address, EC field, and ISS field.
• Remove the infinite loop in exception_handler function and add eret at the end of ISRs. Observe the difference between saving and not saving general registers.
• Required 3
  • Implement IRQ handler for IRQ Exception from the current EL while using SP_ELx. (offset 0x280-0x300 in the vector table)
  • Implement the arm core timer handler. Add irq command to the shell to enable timer.
• Required 4
  • Return from EL2 to EL1 and set the corresponding handlers.
  • Return from EL1 to EL0 and run shell in EL0.
  • Reimplement irq command by system call.

Elective

• Pick another timer and implement its handler.
• Implement ISR for either mini UART or PL011 UART.
• Use a long delay to simulate bottom half of ISR. Compare the difference between enabling and not enabling interrupt after top half of ISR.

Questions

• Change svc instruction to brk (breakpoint) instruction. See the difference in ELR_EL2(return address). Explain why there is a difference.
• Do you need to save floating point SIMD registers in ISRs? Why or why not.
• What will happen if you don’t clear peripherals’ interrupt signal?

Lab 04

NCTU OSDI Lab 4: Multitasking

Documentation: Lab 4

Lab 4 Demo Release

Required

• Required 1
  • Design your own task struct with at least one field called task id. Task ids should be unique.
  • Implement privilege_task_create.
  • Implement context_switch.
  • In the end of privilege_task_create, put the task into the runqueue.
  • Replace context_switch withschedule in the privilege tasks, you should be able to create more than 2 tasks and switch between them.
• Requried 2
  • Reimplement the core timer handler, it updates the current task’s reschedule flag.
  • Create more than 2 privilege tasks. Each of them keeps checking the reschedule flag. If the flag is set, it prints some message, clears reschedule flag and issue schedule .
• Required 3
  • Implement do_exec.
  • Implement user tasks preemption.
• Required 4
  • Implement uart_read and uart_write.
  • Implement exec.
  • Implement fork.
  • Implement exit and zombie reaper by one of the above methods.

Elective

In the elective part, you should enable interrupt except some critical regions in EL1. Otherwise, you won’t get any score.

• Implement kill and signal handler for SIGKILL.
• Implement a priority based scheduler.
• Implement a wait queue for uart reading.interrupt after top half of ISR.
• Implement mutex_lock, mutex_unlock. If task fail to acquire the lock, it would go to sleep and context switch to other tasks.
• Let kernel could be preempted without explicit calling schedule.

Questions

• Consider the following POSIX signal example code. Can you elaborate how to design the kernel to support it?

  #include <stdio.h>
  #include <signal.h>
  #include <unistd.h>
  
  void handler(int sig) {
    printf("Hello\n");
  }
  
  int main()
  {
    signal(SIGINT, handler);
    char buf[256];
    int n = read(0, buf, 256);
    buf[n] = '\0';
    printf("Bye %s\n", buf);
  }
  

• Can you prevent all possible context switch by disabling interrupt?
• Do you think microkernel need to be preemptive kernel or not? Why or why not?

Lab 03

NCTU OSDI Lab 3: Exception and Interrupt

Documentation: Lab 3

Lab 3 Demo Release

Required

• Required 1
  • Set up the exception vector table.
  • Implement the exception handler for Synchronous Exceptions from the currentEL while using SP_ELx (offset 0x200-0x280 in the vector table).
  • Add an exc command to the shell. It issues svc #1 and then your exception handler should print the return address, EC field, and ISS field.
• Remove the infinite loop in exception_handler function and add eret at the end of ISRs. Observe the difference between saving and not saving general registers.
• Required 3
  • Implement IRQ handler for IRQ Exception from the current EL while using SP_ELx. (offset 0x280-0x300 in the vector table)
  • Implement the arm core timer handler. Add irq command to the shell to enable timer.
• Required 4
  • Return from EL2 to EL1 and set the corresponding handlers.
  • Return from EL1 to EL0 and run shell in EL0.
  • Reimplement irq command by system call.

Elective

• Pick another timer and implement its handler.
• Implement ISR for either mini UART or PL011 UART.
• Use a long delay to simulate bottom half of ISR. Compare the difference between enabling and not enabling interrupt after top half of ISR.

Questions

• Change svc instruction to brk (breakpoint) instruction. See the difference in ELR_EL2(return address). Explain why there is a difference.
• Do you need to save floating point SIMD registers in ISRs? Why or why not.
• What will happen if you don’t clear peripherals’ interrupt signal?

Lab 02

NCTU OSDI Lab 2: Bootloader

Description: Lab 2

Lab 2 Demo Release

Required

• Get the hardware’s information by mailbox and print them, you should at least print board revision and VC Core base address.
• Implement bootloader can load kernel image by UART.

Elective

• Get or set UART clock by mailbox and replace mini UART by PL011 UART.
• Set framebuffer by mailbox to show a splash image, show the result by qemu.
• User can specify the kernel image’s loading address.

Questions

• In x86 machine, how the above 4 steps are implemented? Roughly describe it.
  1. GPU executes the first stage bootloader from ROM on the SoC.
  2. The first stage bootloader recognizes the FAT16/32 file system and loads the second stage bootloader bootcode.bin from SD card to L2 cache.
  3. bootcode.bin initializes SDRAM and loads start.elf
  4. start.elf initializes GPU’s firmware and reads config.txt, cmdline.txt and kernel8.img to start OS.
• Calculate how long will it take for loading a 10MB kernel image by UART if baud rate is 115200.

Lab 01

NCTU OSDI Lab 1: Hello World

Documentation: Lab 1

Lab 1 Demo Release

Required

• Implement the 3 basic steps.
  • Let only one core proceed, and let others enter a busy loop.
  • Initialize the BSS segment.
  • Set the stack pointer to an appropriate position.
• Following UART to set up mini UART.
• Implement a simple shell, it should support the following commands.

  command	Description
  help	print all available commands
  hello	print Hello World!

Elective

• Write a program or script on your host computer which can read a text file and write the content to rpi3.
• Add <timestamp> command, it print current timestamp.
• Add <reboot> command.

Questions

• Is it reasonable to accelerate booting speed by parallel programming during the initialization stage?
• Point out the difference between bare-metal programming and programming on top of operating system.

Lab 00

NCTU OSDI Lab 0: Environment Setup

Documentation: Lab 0

Lab 0 Demo Release

Required

• Install the cross compiler on your host computer.
• Explain each line of the above linker script.

  SECTIONS
  {
      . = 0x80000;
      .text : { *(.text) }
  }
  

• Install qemu-system-aarch64 as an emulator for rpi3.
• Build your first kernel image and check it by QEMU.
• Set up SD card.

Questions

• What’s the RAM size of Raspberry Pi 3B+?
• What’s the cache size and level of Raspberry Pi 3B+?