Biscuit Code Reading

Go Conference 2018 Autumn

Learning System Programming with Golang (21)��Hashtag: #gocon_a

​

Yoshiki Shibukawa

Future Corporation

@shibu_jp

Today’s Content

Who are You?

01

What is Biscuit?

Code Structure

Boot Sequence of Std Go Application

Boot Sequence of Biscuit

Pickup Some Code

02

03

04

05

06

Who Are You?

SECTION ONE

Who Are You?

Yoshiki Shibukawa

Job:

Honda R&D: - Dec.2010

DeNA: - Aug.2017

Future Corporation: Sep.2017-

Family:

Wife and three girls

Books:

つまみぐい勉強法, Real World HTTP, Mithil, � Goならわかるシステムプログラミング

Translation:

Expert Python Programming

Software development with SCRUM

Pomodoro Technique Illustrated

The Art of Community etc

Favorite Languages:

((Type)|(Java))Script / Go / Python

Other hobbies:

Inline skating

Account:

github.com/shibukawa

twitter.com/shibu_jp

フューチャーをざっくり言うと

• 二人のエンジニアが創ったITコンサル会社
• コンサルからSIまで全部やる
• 中立（ニュートラル）のポジション
• 「ないものはつくる」の精神

2016年4月1日に持株会社体制に移行

Most favorite OSS in Future is...

• Vuls is a vulnerability detection tool
• It gets many github stars and have been featured on Japanese technology magazines

https://github.com/future-architect/vuls

6

Cheetah Grid

• Very fast table drawing component (It uses same canvas drawing technique with Google Spreadsheet)
• It draws 100 million rows in 100 milliseconds
• It provides Vue.js component
• I am working on React component now.

​

https://github.com/future-architect/cheetah-grid

7

We Are Hiring!

• FutureはJavaが多い（新卒の研修がJavaなので）けど、Go案件も増えてきています！
• FutureVuls (SaaS版のVulsサービス) はGo/React/TypeScriptなどを使って実装されています
• Goを仕事で使ってみたいけど、まだGoの業務経験がない、他の言語はわかるという人もポテンシャル採用あるよ！ってFutureVulsのリーダーの林さんが言っていたので、興味がある方はお声がけください

Important Information

• Goならわかるシステムプログラミング�（I can understand system programming with Go)
• It describes modern computer features with pragmatic golang examples
• System call, virtual memory, file system, socket, process, signal, thread, container and so on
• But Japanese only now
• I hope requests to translation!!
• Google translation of original�web articles→� (https://bit.ly/2Rb8Zhp)

Gopher icon is designed by Renée French | CC-BY 3.0

This Session Level: Easy

Even If...

• You are familiar with OS
• You are familiar with Assembly, C-lang, Golang
• You are familiar with Golang’s runtime
• Or you read �“Goならわかるシステムプログラミング”

{

What is Biscuit?

SECTION TWO

Who Made it?

• MIT Parallel & Distributed Operating Systems Group made Biscuit for research since 2014
• Extracting parallelism in OS kernels using type-safe languages�Cody Cutler, M. Frans Kaashoek, Robert Morris, Nickolai Zeldovich, 2015
• The benefits and costs of writing a�POSIX kernel in a high-level language�Cody Cutler, M. Frans Kaashoek, and Robert T. Morris, MIT CSAIL, 2018

�

Biscuit is a monolithic, POSIX-subset operating system kernel in Go for x86-64 CPUs.

from README of Biscuit

Features

from README of Biscuit

• Multicore
• Kernel-supported threads
• Journaled FS with concurrent, deferred, and group commit
• Virtual memory for copy-on-write and lazily mapped anonymous/file pages
• TCP/IP stack
• AHCI SATA disk driver
• Intel 10Gb NIC driver
• Paper says it supports Nginx and Redis

Build and Run Biscuit

• Clone Biscuit’s repository
• Build Biscuit special Go compiler� $ cd src; ./make.bash
• Build Biscuit kernel and user land, images� $ cd biscuit; make
• Run� $ make gqemu

Code Structure

SECTION THREE

Code Structure

• .github Copied from Go
• api Copied from Go
• biscuit
• fsdir Boot disc image template
• maxlive Static analysis tool to decide heap size to reserve for system calls
• scripts Helper scripts (not important to read kernel)
• src Describe later
• user Userland programs
• c C programs includes coreutils tiny libc “litc” and tiny shell “lsh”
• cpp C++ programs includes tiny C++11 standard library
• lib Copied from Go
• time Copied from Go
• misc Copied from Go
• src Copied from Go basically
• test Copied from Go�

Code Structure: biscuit/src

• biscuit
• src
• accnt Time counter for process scheduler
• ahci Serial ATA device driver
• apic Interrupt controller driver
• bnet IP, ARP, ICMP, TCP
• bounds Heap usage database per system calls
• bpath Path name utility
• caller Utility for system call monkey test?
• circbuf Circular buffer
• defs Constants
• fd File descriptor
• fdops Virtual file system / Poll operators
• fs File system
• hashtable Hash table
• inet IP, ARP, ICMP, TCP packet data structure
• ixgbe Intel 10GB ethernet driver

​

Code Structure: biscuit/src

• biscuit
• src
• kernel Kernel main code and bootloader
• limits System limits
• mem Physical memory manager
• msi Message signaled interrupt
• oomsg Order to assassinate to OOM Killer
• pci PCI bus
• res Memory resource manager
• proc Procfs
• stat Concrete implementation of os.FileInfo
• stats Performance counter of CPU
• tinfo Thread info
• ustr String utility for path name
• util Utility function
• vm Virtual memory

​

Where is good entry point to read?

• biscuit/src/kernel/boot.S
• Entry point of bootloader
• biscuit/src/kernel/bootmain.c
• Main part of bootloader
• src/runtime/asm_amd64.s
• Entry point and low level code of Biscuit Kernel
• src/runtime/os_linux.go
• Hacked Go runtime in Go
• biscuit/src/kernel/main.go
• Main part of Biscuit Kernel in Go

Why Biscuit team bundles whole Golang code?

• Golang’s runtime and compiler are tightly coupled
• GOROOT specifies compiler/linker/runtime at the same time
• Biscuit kernel is completely written in Golang, but it needs to hack runtime
• Shim layer replaces system call

From The benefits and costs of writing a POSIX kernel in a high-level language

Boot Sequence of Standard Go Application

SECTION FOUR

Executable File Format

• Executable file doesn’t include only machine code
• Machine code is wrapped by Executable File Format like ELF (linux etc), Mach-O (macOS), PE (Windows)
• Biscuit uses ELF
• ELF header includes CPU type and entry point.
• Entry point points _rt0_(ARCH)_(OS) subroutine in src/runtime/rt0_(OS)_(ARCH).s

Surueña [GFDL or CC BY-SA 3.0], from Wikimedia Commons

Before main() (1)

• _rt0_(ARCH)_(OS) calls _rt0_(ARCH) subroutine in runtime/asm_(ARCH).s
• Initialize first goroutine
• Parse command line arguments passed by OS
• Get available CPU core counts
• _rt0_(ARCH) calls schedinit() function in runtime/proc.go
• Initialize stack
• Initialize memory manager
• Initialize hash algorithm that is used from map
• Initialize signal handler
• Initialize os.Args, os.Environ()
• Initialize garbage collector

​

Before main() (2)

• schedinit() calls main() function in runtime/proc.go with new goroutine
• Bind OS main thread by using runtime.lockOSThread()
• Calls init() functions of runtime()
• Calls main.init() function
• Unbind OS main thread by using runtime.unlockOSThread()
• Calls main.main() function

Boot Sequence of Biscuit

SECTION FIVE

Biscuit Boot Sequence for amd64 system

Boot Sequence of Biscuit

• There are many steps to boot OS
• BIOS loads bootloader from first sector of boot drive
• Bootloader loads Kernel program and switch to Long Mode (64 bit)
• Biscuit Kernel initialize OS features like process management, virtual memory, file system etc
• “init” provides user mode initialization
• “lsh” provides user interaction

BIOS

Bootloader

Biscuit Kernel

/bin/init

/bin/lsh

Runtime Bootstrap

Main code

Bootloader : Summary

Boot Sequence of Biscuit

​

• Bootloader has several tasks
• Biscuit assumes the computer uses BIOS, not UEFI.
• BIOS is a collection of useful functions to access hardware (keyboard, mouse, storage, etc)
• BIOS works on 16 bit Real Mode
• It can use only 1MB memory
• UEFI is more modern architecture
• More secure
• UEFI sometimes harasses Linux users
• BIOS read bootloader from boot sector on disk and run it

Get Memory Layout �(BIOS e820)

Switch to Protect Mode (32 bit)

Read kernel image �from storage

Switch to Long Mode (64 bit)

Start running Biscuit kernel

Read remained part of Boot Loader

Boot Loader : Get Memory Layout

• int 15h (ax=0x820) returns memory layout
• Boot Loader put this information in physical static memory address and Kernel reads it via the address.
• You can see the information from Linux’s dmesg

e820:� movw $start, %sp� xorl %ebx, %ebx� pushl %ebx� movw $e820m, %di�e820.1:� movl $0xe820, %eax� movl $20, %ecx� movl $0x534d4150, %edx� int $0x15

Boot Loader : Read remained part of Boot Loader

• BIOS reads only first 512 bytes of boot loader
• It is too small for current boot loaders
• GRUB supports many file systems (ext4, fat32, ntfs, ZFS, Brtfs…)
• Many boot loaders splits the program in several steps to realize rich features → https://en.wikipedia.org/wiki/GNU_GRUB
• Biscuit’s boot loader is simple but it has two steps
• First part is written in GNU assembly, but remained part is written in C
• Read program via int 13h (ax=42h) BIOS function

movw $0x7c00 + SECTSIZE, %ax�movw %ax, dap_dest_off�movw $0, dap_dest_seg�movw $1, dap_sectoff_lo��// 13h 42h�// Extended Read Sectors From // Drive�movb $0x42, %ah�movb diskid, %dl�movw $dap, %si�int $0x13

Boot Loader: Switch to Protect Mode (32 bit)

• Real Mode only uses 1MB memory, but Biscuit kernel is bigger than 4MB
• So switch to Protect Mode to read kernel.
• Protect mode needs Global Descriptor Table (memory� segments information)
• Set gdtdesc via LGDT�instruction and set mode flag�to CR0 control register then�CPU starts in Protect Mode.�

gdt:� SEG_NULL # 0 - null seg� SEG(STA_X|STA_R, 0x0, 0xffffffff) # 1 - code seg� SEG(STA_W, 0x0, 0xffffffff) # 2 - data seg� SEG64(STA_X|STA_R, 0x0, 0xffffffff) # 3 - 64bit code seg� RSEG(STA_X|STA_R, 0, 0xffff) # 4 - real mode code� RSEG(STA_W, 0, 0xffff) # 5 - real mode data��gdtdesc:� .word (gdtdesc - gdt - 1) # sizeof(gdt) - 1� .long gdt # gdt address

Boot Loader : Read kernel image from storage

• After this part is written in C (bootmain.c).
• Read kernel image from storage
• Use BIOS function 13h (ax=42h) to read image
• But BIOS works only on Real Mode (16 bit)
• Boot loader repeatedly switch back to Real Mode and calls BIOS then return to Protect Mode to store image.
• Biscuit’s bootloader is simple
• It assumes kernel is in the specific sector in storage.
• It assumes kernel is in ELF format. File size and location are read from the ELF header.

Bootloader : Switch to Long Mode (64 bit)

• Now bootloader switch to Long Mode.
• Several registers should be set to enter Long Mode.

// enter long mode�enable_pae();�enable_global();�lcr3(pgdir);�uint64_t efer = rdmsr(IA32_EFER);�wrmsr(IA32_EFER, efer | IA32_EFER_LME);�enable_paging_wp();

Bootloader: Launch Biscuit’s Kernel

• Finally Bootloader launches kernel!
• Kernel starts working in 64 bit mode
• Memory segments are initialized and memory address will be passed via table in static memory address.
• But only Bootstrap Processor (BSP: first CPU core) works even if you PC is RYZEN.
• Other CPU cores (AP = Application Processor) sleep at this point.

// Long Jump into Kernel’s entry point!

#define CODE64 3�ljmp(CODE64, entry, (uint32_t)pgdir, firstfree, NEWSTACK);

Kernel: Entrypoint

• Application’s entrypoint is specified at executable file format header.
• Biscuit is still ELF format executable
• Biscuit binary is modified by “chentry” command (biscuit/src/kernel/chentry.c) to make entrypoint _rt0_hack
• _rt0_hack is similar to _rt0_amd64_linux, but it does more task:
• Set runtime.hackmode flag to 1
• argc/argv related code is removed
• Stores page map, pgfirst pointer that�was passed from the bootloader
• ​

Kernel: hackmode flag

• Some system call functions check hackmode flag
• Biscuit’s implementation is used only on Biscuit kernel
• Even if you use Go compiler of Biscuit, regular system call is used if hackmode flag is not set

TEXT runtime·sysMmap(SB),NOSPLIT,$0� // Jump to mmap_skip if runtime.hackmode is 0� MOVQ runtime·hackmode(SB), DI� TESTQ DI, DI� JZ mmap_skip� JMP ·hack_mmap(SB)�mmap_skip:� :� MOVL $SYS_mmap, AX� SYSCALL� CMPQ AX, $0xfffffffffffff001� JLS ok� :� RET�ok:� MOVQ AX, p+32(FP)� MOVQ $0, err+40(FP)� RET

Kernel: Before main()

• Calls some extra initialization functions
• runtime.sc_setup()
• Serial Port. It is used from putch and some debug output.
• runtime.fpuinit0()
• Enable FPU and SSE
• runtime.seg_setup()
• Set GDT (Global Descriptor Table)
• runtime.int_setup()
• Set interrupt table from hardware
• runtime.proc_setup()
• Set system call table

Kernel: After main() 1/3

• apic.Bsp_init()
• Init BSP’s interrupt controller
• mem.Phys_init()
• Dump system information (like available memory)
• cpucheck()
• Dump SSE feature list of CPU
• mem.Dmap_init()
• perfsetup()
• Init performance counter (like cache miss)
• runtime.Install_traphandler(trapstub)
• attach_devs()
• Setup hardware drivers and get CPU cores
• kbd_init()

Kernel: After main() 2/3

• cpus_start(ncpu, aplim)
• Start other CPU (AP: Application Processor) cores!
• All CPU start from Real Mode (16 bit)
• Startup 16bit code is in biscuit/src/kernel/mpentry.S and bundled by tool like go-bindata (but original)
• Init Global Descriptor Table, Interrupt Descriptor Table as BSP.
• Memory address 0xfee00000 is mapped as special register. Writing this address to interrupt (throw task) to other CPU cores.
• Throw initipi (inter process interrupt) to all APs then, throw startipi to all APs

Kernel: After main() 3/3

• tinfo.SetCurrent(&tinfo.Tnote_t{})
• tinfo == thread information
• res.Resbegin(manymeg)
• rf, fs := fs.StartFS(ahci.Blockmem, ahci.Ahci, console, diskfs)
• Initialize file system
• proc.Oom_init(thefs.Fs_evict)
• exec(ustr.Ustr("bin/init"), nil)
• Start init process
• res.Resend()
• tinfo.ClearCurrent()
• sleep forever

Pickup Some Code

SECTION SIX

Hardware Access: Summary

Pickup Some Code

• There are three methods to access hardware
• Port mapped I/O
• Memory mapped I/O
• Hardware interrupt

Hardware Access: Port mapped I/O

• CPU has many ports and hardware devices are connected to the port
• Biscuit provides seven functions to do it
• On linux, applications need to call ioperm() or iopl() system call to get permission to access I/O port

func Inb(uint16) uint�func Inl(int) int�func Insl(uint16, unsafe.Pointer, uint)�func Outb(uint16, uint8)�func Outl(int, int)�func Outsl(int, unsafe.Pointer, int)�func Outw(int, int)

Hardware Access: Memory mapped I/O

• Some special memory address is mapped to hardware devices
• Memory mapped to hardware register to control devices
• Register main memory buffer to read/write big amount of data
• e.g. VRAM mapping
• DMA is similar�but different.

CPU just receive�interrupt when�transporting task�is finished

• In Biscuit, use atomic to �access memory certainly to�avoid Out of Order effect

lapaddr := 0xfee00000�lap := (*[mem.PGSIZE / 4]uint32)� (unsafe.Pointer(uintptr(lapaddr)))�icrh := 0x310 / 4�icrl := 0x300 / 4�icrw := func(hi uint32, low uint32) {� // use sync to guarantee order� atomic.StoreUint32(&lap[icrh], hi)� atomic.StoreUint32(&lap[icrl], low)� ipisent := uint32(1 << 12)� for atomic.LoadUint32(&lap[icrl])&ipisent != 0 {� }�}

Hardware Access: Interrupt

• Polling is bad idea to detect other devices
• It wastes CPU cycles
• It is similar to signal of userland applications
• Register callback function
• Go’s signal is abstracted by CSP (Communication Sequential Processes), but there is callback mechanism in POSIX.
• There are three types of interrupt
• CPU exception (like divided by zero)
• IRQ (Pin based interrupt)
• MSI (Message Signaled Interrupts)
• Biscuit creates 128 elements array and registers to CPU (LIDTQ instruction) at int_setup() before main()

System Call: as an entry point

• System call is very good entrypoint to search kernel features
• Syscall method in biscuit/src/kernel/syscall.go has big switch statement
• This is a core of kernel API

func (s *syscall_t) Syscall(...) int {� sysno := int(tf[defs.TF_RAX])� :� a1 := int(tf[defs.TF_RDI])� a2 := int(tf[defs.TF_RSI])� a3 := int(tf[defs.TF_RDX])� a4 := int(tf[defs.TF_RCX])� a5 := int(tf[defs.TF_R8])� var ret int� switch sysno {� case defs.SYS_READ:� ret = sys_read(p, a1, a2, a3)� case defs.SYS_WRITE:� ret = sys_write(p, a1, a2, a3)� :� }�}

System Call: MaxLive

• Most interesting point of Biscuit’s system call is the following lines
• Biscuit has pre calculated required memory resource information per system call at biscuit/src/bounds package
• res.Resadd(lim) wait until required memory would be available
• Inside system call, resource management becomes very simple, because required resource is available
• MaxLive in biscuit/maxlive is static code checker
• This tool is described in Biscuit’s paper
• This tool maybe export required memory resource information

lim := _sysbounds[sysno]�if !res.Resadd(lim) {� return int(-defs.ENOHEAP)�}

Conclusion

Conclusion

• Go is a very good teaching material to learn computer systems
• From top to bottom, Golang’s runtime is written in Golang runtime
• There is very good text to learn computer systems in Go�(of course, Goならわかるシステムプログラミング)

​

Conclusion

• Go is a very good teaching material to learn computer systems
• From top to bottom, Golang’s runtime is written in Golang runtime
• There is very good text to learn computer systems in Go�(of course, Goならわかるシステムプログラミング)

​

In addition to that, we can read the OS implementation in Go

(It is under real MIT’s real MIT license)