Kernel Implementation: Standard Library

Now that our kernel can load and run programs, we’re going to start thinking about the standard library functions required to support more interesting programs like a shell.

Functions and system calls

We’ll spend time in class discussing the functions we need to implement in the standard library and the system calls required to support them. Our discussion will include a pared-down list of functions and system calls you should start implementing. You may decide to implement these as-needed, but if you are caught up on other implementation tasks you should start writing these functions before our next class.

Here are the functions we need to run our shell, organized by general category.

Input/Output

Implement these using the read and write system calls your kernel already supports.

read (a wrapper around the syscall invocation)
write (a wrapper around the syscall invocation)
printf
getline
perror (just a placeholder for now—we’ll discuss error handling soon)

String Utilities

All of these utilities can be implemented entirely in the library with no special system calls. You can prioritize the functions you actually use in your shell lab.

strtok/strtok_r
strsep
strlen
strcpy
atoi
strpbrk
strcmp

Memory Utilities

Implement these utility functions entirely in userspace, or using a new mmap system call that maps a virtual page somewhere in the process’ address space.

mmap (this one requires a new system call)
malloc (Keep it simple! See example below)
memcpy
memset

A simple `malloc` implementation

We can get things up and running with a very simple malloc design that doesn’t support freeing.

              // Round a value x up to the next multiple of y
#define ROUND_UP(x, y) ((x) % (y) == 0 ? (x) : (x) + ((y) - (x) % (y)))

void* bump = NULL;
size_t space_remaining = 0;

void* malloc(size_t sz) {
  // Round sz up to a multiple of 16
  sz = ROUND_UP(sz, 16);

  // Do we have enough space to satisfy this allocation?
  if (space_remaining < sz) {
    // No. Get some more space using `mmap`
    size_t rounded_up = ROUND_UP(sz, PAGE_SIZE);
    void* newmem = mmap(NULL, rounded_up, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);

    // Check for errors
    if (newmem == NULL) {
      return NULL;
    }

    bump = newmem;
    space_remaining = rounded_up;
  }

  // Grab bytes from the beginning of our bump pointer region
  void* result = bump;
  bump += sz;
  space_remaining -= sz;

  return result;
}

void free(void* p) {
  // Do nothing
}

            

Scary Process Functions

We’ll get to these later. They require some notion of a process and a bit more manipulation of address spaces that we’ll start on next week.

fork
exec (some variant, likely not execvp)
wait
exit

Build system changes

Building a standard library will require some further updates to your build system. We’ll run through these in class, but they’re posted here for reference:

Top-level `Makefile`

We are going to add code to our top-level Makefile to build a standard library in addition to the init and kernel targets. That Makefile should look like this:

              .PHONY: all
all: boot.iso

.PHONY: run
run: boot.iso
	./run.sh

.PHONY: clean
clean:
	rm -f iso_root boot.iso
	$(MAKE) -C stdlib clean
	$(MAKE) -C kernel clean
	$(MAKE) -C init clean

.PHONY: stdlib
stdlib:
	$(MAKE) -C stdlib

.PHONY: kernel
kernel: stdlib
	$(MAKE) -C kernel

.PHONY: init
init: stdlib
	$(MAKE) -C init

limine:
	git clone https://github.com/limine-bootloader/limine.git --branch=v2.0-branch-binary --depth=1
	$(MAKE) -C limine

boot.iso: limine kernel init limine.cfg
	rm -rf iso_root
	mkdir -p iso_root
	cp kernel/kernel.elf init/init limine.cfg limine/limine.sys limine/limine-cd.bin limine/limine-eltorito-efi.bin iso_root/
	xorriso -as mkisofs -b limine-cd.bin -no-emul-boot -boot-load-size 4 -boot-info-table --efi-boot limine-eltorito-efi.bin -efi-boot-part --efi-boot-image --protective-msdos-label iso_root -o boot.iso
	limine/limine-install boot.iso
	rm -rf iso_root


            

New `Makefile` in the `stdlib` directory

Create a stdlib directory and create a new Makefile there. This Makefile will build a static library that holds the code for our standard library functions. Here is the complete Makefile, based largely on the existing Makefiles we’ve seen for kernel and init.

              CC := clang -target x86_64-elf
AR := x86_64-elf-ar

CFLAGS := --std=c17 -Wall -O2 -I. -isystem ../stdlib -ffreestanding -nostdlib -fno-stack-protector -fno-pic -mno-80387 -mno-mmx -mno-3dnow -mno-sse -mno-sse2 -mno-red-zone -mcmodel=medium -MMD -MP

OUT := obj

SRC := $(wildcard *.c)
ASM := $(wildcard *.s)
C_OBJ := $(patsubst %.c, $(OUT)/%.o, $(SRC))
S_OBJ := $(patsubst %.s, $(OUT)/%.o, $(ASM))
DEP := $(patsubst %.c, $(OUT)/%.d, $(SRC))

.PHONY: all
all: libc.a

.PHONY: clean
clean:
	rm -rf libc.a $(OUT)

libc.a: $(C_OBJ) $(S_OBJ)
	$(AR) -rc $@ $^

$(C_OBJ): $(OUT)/%.o: %.c
	@mkdir -p `dirname $@`
	$(CC) $(CFLAGS) -c $< -o $@

$(S_OBJ): $(OUT)/%.o: %.s
	@mkdir -p `dirname $@`
	$(CC) -c $< -o $@

-include $(DEP)

            

This Makefile is very similar to what we’ve seen before. It compiles all source files to .o files, but instead of combining them into an executable with ld, it uses the ar utility to create a static library that programs can link against.

Updating `init` to use the standard library

Next, we need to update the Makefile for init so it uses the standard library. We’ll update the CFLAGS variable so it looks for system includes in our stdlib directory, and then add to the LDFLAGS variable to tell it to link in the C standard library we’ve created:

              CFLAGS := --std=c17 -Wall -O2 -I. -isystem ../stdlib -ffreestanding -nostdlib -fno-stack-protector -fno-pic -mno-80387 -mno-mmx -mno-3dnow -mno-sse -mno-sse2 -mno-red-zone -mcmodel=medium -MMD -MP

LDFLAGS := -nostdlib -static -L../stdlib -lc

We need to make two additional changes to the init target further down in the Makefile. Here is the full updated target you should have in your Makefile:

              init: $(C_OBJ) $(S_OBJ) linker.ld ../stdlib/libc.a
	$(LD) -T linker.ld -o $@ $(C_OBJ) $(S_OBJ) $(LDFLAGS)

The first change adds ../stdlib/libc.a as a dependency for init; this tells make to re-link init if the standard library is updated. The second change moves the LDFLAGS variable to the end of the linker command, which corrects a mistake from my original Makefile.

Updating `kernel` to use the standard library

We can save ourselves some work by using the standard library in the kernel as well. It’s important that we use kernel-specific versions of functions that might issue system calls (e.g. we use kprintf instead of printf to print from the kernel) but common utilties like memset or strlen are safe to use in both kernel and user space. You’ll need to make the same updates to the kernel Makefile we made for init:

              CFLAGS := --std=c17 -Wall -O2 -I. -isystem ../stdlib -ffreestanding -nostdlib -fno-stack-protector -fno-pic -mno-80387 -mno-mmx -mno-3dnow -mno-sse -mno-sse2 -mno-red-zone -mcmodel=kernel -MMD -MP

LDFLAGS := -nostdlib -static -L../stdlib -lc

...

kernel.elf: $(C_OBJ) $(S_OBJ) linker.ld ../stdlib/libc.a
	$(LD) -T linker.ld -o $@ $(C_OBJ) $(S_OBJ) $(LDFLAGS)

Make sure you can build and run your kernel after making these changes. You can now add standard library functions in the stdlib directory; any .h files you place here can be included with angle brackets (e.g. #include <string.h>), and the implementations you write in .c or .s files are available in both the kernel and the init program.