Managarm Handbook

Managarm is a pragmatic microkernel-based operating system with fully asynchronous I/O.

This documentation contains conceptual and technical details for various parts of the system and different guides.

The Official Discord server can be found here: https://discord.gg/7WB6Ur3.

What is this about? - from the managarm README.

This is the main repository of managarm, a microkernel-based operating system.

What is special about managarm? Some notable properties of managarm are: (i) managarm is based on a microkernel while common Desktop operating systems like Linux and Windows use monolithic kernels, (ii) managarm uses a completely asynchronous API for I/O and (iii) despite those internal differences, managarm provides good compatibility with Linux at the user space level.

Aren't microkernels slow? Microkernels do have some performance disadvantages over monolithic kernels. managarm tries to mitigate some of those issues by providing good abstractions (at the driver and system call levels) that allow efficient implementations of common user space functionality (like POSIX).

Is this a Linux distribution? No, managarm runs its own kernel that does not originate from Linux. While the managarm user space API supports many Linux APIs (e.g. epoll, timerfd, signalfd or tmpfs), managarm does not share any source code (or binaries) with the Linux kernel.

Getting Started

This section of the Managarm Documentation shows how to get into Managarm.

I want to try out Managarm

If you want to try out Managarm without building the system yourself.

Trying out Managarm

I want to contribute to Managarm

If you want to contribute to Managarm or develop for it.

Contributing

Trying out managarm

The Managarm project provides nightly builds of managarm if you want to try out Managarm without setting up the development environment and building the whole OS yourself.

Nightly builds

The latest nightly build can be downloaded here.

Our build server, named xbbs, the xbstrap build server, which builds all of our packages automatically can be viewed at https://builds.managarm.org.

Running the nightly builds

Before running the downloaded nightly build you have to uncompress it.

To run the nightly builds we recommend using QEMU with the following options:

$ qemu-system-x86_64 -enable-kvm -m 2048 -cpu host,migratable=off -device qemu-xhci -device usb-kbd -device usb-tablet -drive id=hdd,file=image,format=raw,if=none -device virtio-blk-pci,drive=hdd -vga vmware -debugcon stdio

Be aware that the -enable-kvm flags works only on systems that support KVM.

Supported Hardware and Software

Software

Programs supported on managarm include Weston (the Wayland reference compositor), kmscon (a system console), GNU coreutils, bash, nano and others.

A list of packages is available on our repo. A quick overview of various categories can be found at package list.

Hardware

Real Hardware

  • General: USB (UHCI, EHCI, XHCI)
  • Graphics: Generic VBE graphics, Intel G45
  • Input: USB human interface devices, PS/2 keyboard and mouse
  • Storage: USB mass storage devices, NVMe, AHCI, ATA

Virtual Hardware

Includes all of the hardware listed above

  • Graphics: virtio GPU, Bochs VBE interface, VMWare SVGA
  • Storage: virtio block
  • Networking: virtio net

Supported packages

For an always up-to-date package list please look here.

Managarm uses xbps for it's package management, users can use this to fetch packages from within managarm.

Some of the available packages include:

  • Unix tools: grep, sed, findutils, coreutils, gawk, file, man-db, tar, which, groff, less, bzip2, gzip, xz-utils, lz4, zstd
  • Development: yasm, nasm, diffutils, patch, make, m4, gcc, cmake, binutils, bc
  • Scripting: perl (only basic functionality), python (only basic functionality), lua
  • Games: ace, mednafen, tyr-quake, gtklife, nyancat
  • Networking: wget, curl, socat, rsync
  • Editors: nano, vim
  • Shells: bash
  • Graphical: weston, mesa-demos, gtk+2, xclock, xkill, xwininfo
  • Databases: sqlite, gdbm
  • Bootloaders: limine

Building Managarm

This guide shows how to build a managarm distribution from source utilising the bootstrap-managarm patches and build scripts.

Building a managarm distribution from source

Build environment

To make sure that all build environments work properly, it is recommended to setup a build environment with our lightweight containerized build runtime cbuildrt (see below for instructions). It is also possible to build with Docker (see here), or by installing the dependencies manually (see here), but these methods are no longer recommended.

Make sure that you have at least 20 - 30 GiB of free disk space.

Preparations

  1. Create a directory which will be used for storing the source and build directories. Here we use ~/managarm, but it can be any directory. 
    mkdir ~/managarm && cd ~/managarm
  2. Install the xbstrap build system via pip3: 
    pip3 install xbstrap
  3. The git, subversion and mercurial tools are required on the host (whether you build in a container or not). Install these via your package manager.
  4. Clone this repository into a src directory and create a build directory: 
    git clone https://github.com/managarm/bootstrap-managarm.git src
mkdir build

Creating a cbuildrt environment

  1. Download and install the latest cbuildrt release by running:

    xbstrap prereqs cbuildrt xbps

    Note: If you choose to build cbuildrt from source, make sure to place the resulting binary either in $PATH or in ~/.xbstrap/bin.

  2. Download and unpack the latest Managarm rootfs somewhere:

    curl https://repos.managarm.org/buildenv/managarm-buildenv.tar.gz -o managarm-rootfs.tar.gz
tar xvf managarm-rootfs.tar.gz

  3. Inside the build directory, create a file named bootstrap-site.yml with the following contents:

    pkg_management:
  format: xbps

container:
  runtime: cbuildrt
  rootfs:  /path/to/your/rootfs
  uid: 1000
  gid: 1000
  src_mount: /var/lib/managarm-buildenv/src
  build_mount: /var/lib/managarm-buildenv/build
  allow_containerless: true

    Note: you must keep the src_mount and build_mount values as shown above if you want to be able to use pre-built tools from our build server. These paths refer to locations on the container, not on your host machine. Also note that these paths cannot be changed after starting the build; doing so will likely result in a broken directory tree.

  4. In the build/bootstrap-site.yml file you just created, replace the container.rootfs key with the path to your rootfs.

Building

  1. Initialize the build directory with

    cd build
xbstrap init ../src

  2. Decide which software you want to include in the image you create. There are several meta-packages available which help you decide this:

    • base: just enough to boot into kmscon plus some functional commands to play with (such as less and grep)
    • base-devel: same as base plus some extra development tools (such as gcc and binutils)
    • weston-desktop: full managarm experience with a selection of terminal and GUI software

  3. To actually execute the build, we recommend that you install the necessary tools and packages as binaries from our build server. This can save you multiple hours of compilation, depending on your machine.

    Note: this only works if you build in a container (though this is untested with Docker). Containerless builds must do a full build from source (see below).

    xbstrap pull-pack --deps-of <meta-package> mlibc mlibc-headers # e.g xbstrap pull-pack --deps-of base mlibc mlibc-headers
xbstrap install --deps-of <meta-package>

# The following two commands fetch managarm and mlibc (plus their required tools) to enable local development:
xbstrap download-tool-archive --build-deps-of managarm-system --build-deps-of managarm-kernel --build-deps-of mlibc
xbstrap install --rebuild managarm-system managarm-kernel mlibc mlibc-headers

    If instead you want to build everything from source, simply run xbstrap install <group>, e.g xbstrap install weston-desktop. Note that this can take multiple hours, depending on your machine.

Creating Images

After managarm's packages have been built, building a HDD image of the system is straightforward.

For all methods, the image creation and updation commands shown below require the following programs to be installed on the host: rsync, losetup, sfdisk, mkfs.ext2, mkfs.vfat. Refer to image_create for more details on this.

  1. Decide what method you want to use to copy files to the image:

    1. Using libguestfs (the default method). We recommend this when root access is not possible or desirable. However, it is much slower than method 2 and requires some setup on the host (see below).
    2. Using a classic loopback and mount (requires root privileges). We recommend this when root access is acceptable because it is the fastest method and most guaranteed to work.
    3. Via Docker container (only works with the Docker build method). This is handy in case the user is in the docker group since it does not require additional root authentication. We discourage this because it uses docker run --privileged (which is not safer than giving root access) and currently has some bugs.

    Going with method 1 will require libguestfs to be installed on the host. After installing libguestfs, if you encounter errors while making the image it might be necessary to run the following:

    sudo install -d /usr/lib/guestfs
sudo update-libguestfs-appliance

  2. Add the following to build/bootstrap-site.yml, depending on what mount method you have chosen:

    define_options:
  mount-using: 'loopback' # or guestfs/docker

  3. Create the image:

    xbstrap run initialize-empty-image

  4. Copy the system onto it:

    xbstrap run make-image

  5. Launch the image using QEMU:

    xbstrap run qemu # Note that you can combine the last two operations: xbstrap run make-image qemu

Alternatively, you can call the necessary scripts manually (check their help messages for more information):

  • ../src/managarm/tools/gen-initrd.py and ../src/scripts/update-image.py for copying the files onto the image (the mount method can be selected with the --mount-using argument)
  • ../src/scripts/vm-util.py qemu for launching QEMU

Building Managarm

This guide shows how to build a managarm distribution from source utilising the bootstrap-managarm patches and build scripts.

Building a managarm distribution from source

Build environment

To make sure that all build environments work properly, it is recommended to setup a build environment with our lightweight containerized build runtime cbuildrt (see below for instructions). It is also possible to build with Docker (see here), or by installing the dependencies manually (see here), but these methods are no longer recommended.

Make sure that you have at least 20 - 30 GiB of free disk space.

Preparations

  1. Create a directory which will be used for storing the source and build directories. Here we use ~/managarm, but it can be any directory. 
    mkdir ~/managarm && cd ~/managarm
  2. Install the xbstrap build system via pip3: 
    pip3 install xbstrap
  3. The git, subversion and mercurial tools are required on the host (whether you build in a container or not). Install these via your package manager.
  4. Clone this repository into a src directory and create a build directory: 
    git clone https://github.com/managarm/bootstrap-managarm.git src
mkdir build

Creating a cbuildrt environment

  1. Download and install the latest cbuildrt release by running:

    xbstrap prereqs cbuildrt xbps

    Note: If you choose to build cbuildrt from source, make sure to place the resulting binary either in $PATH or in ~/.xbstrap/bin.

  2. Download and unpack the latest Managarm rootfs somewhere:

    curl https://repos.managarm.org/buildenv/managarm-buildenv.tar.gz -o managarm-rootfs.tar.gz
tar xvf managarm-rootfs.tar.gz

  3. Inside the build directory, create a file named bootstrap-site.yml with the following contents:

    pkg_management:
  format: xbps

container:
  runtime: cbuildrt
  rootfs:  /path/to/your/rootfs
  uid: 1000
  gid: 1000
  src_mount: /var/lib/managarm-buildenv/src
  build_mount: /var/lib/managarm-buildenv/build
  allow_containerless: true

    Note: you must keep the src_mount and build_mount values as shown above if you want to be able to use pre-built tools from our build server. These paths refer to locations on the container, not on your host machine. Also note that these paths cannot be changed after starting the build; doing so will likely result in a broken directory tree.

  4. In the build/bootstrap-site.yml file you just created, replace the container.rootfs key with the path to your rootfs.

Building

  1. Initialize the build directory with

    cd build
xbstrap init ../src

  2. Decide which software you want to include in the image you create. There are several meta-packages available which help you decide this:

    • base: just enough to boot into kmscon plus some functional commands to play with (such as less and grep)
    • base-devel: same as base plus some extra development tools (such as gcc and binutils)
    • weston-desktop: full managarm experience with a selection of terminal and GUI software

  3. To actually execute the build, we recommend that you install the necessary tools and packages as binaries from our build server. This can save you multiple hours of compilation, depending on your machine.

    Note: this only works if you build in a container (though this is untested with Docker). Containerless builds must do a full build from source (see below).

    xbstrap pull-pack --deps-of <meta-package> mlibc mlibc-headers # e.g xbstrap pull-pack --deps-of base mlibc mlibc-headers
xbstrap install --deps-of <meta-package>

# The following two commands fetch managarm and mlibc (plus their required tools) to enable local development:
xbstrap download-tool-archive --build-deps-of managarm-system --build-deps-of managarm-kernel --build-deps-of mlibc
xbstrap install --rebuild managarm-system managarm-kernel mlibc mlibc-headers

    If instead you want to build everything from source, simply run xbstrap install <group>, e.g xbstrap install weston-desktop. Note that this can take multiple hours, depending on your machine.

Creating Images

After managarm's packages have been built, building a HDD image of the system is straightforward.

For all methods, the image creation and updation commands shown below require the following programs to be installed on the host: rsync, losetup, sfdisk, mkfs.ext2, mkfs.vfat. Refer to image_create for more details on this.

  1. Decide what method you want to use to copy files to the image:

    1. Using libguestfs (the default method). We recommend this when root access is not possible or desirable. However, it is much slower than method 2 and requires some setup on the host (see below).
    2. Using a classic loopback and mount (requires root privileges). We recommend this when root access is acceptable because it is the fastest method and most guaranteed to work.
    3. Via Docker container (only works with the Docker build method). This is handy in case the user is in the docker group since it does not require additional root authentication. We discourage this because it uses docker run --privileged (which is not safer than giving root access) and currently has some bugs.

    Going with method 1 will require libguestfs to be installed on the host. After installing libguestfs, if you encounter errors while making the image it might be necessary to run the following:

    sudo install -d /usr/lib/guestfs
sudo update-libguestfs-appliance

  2. Add the following to build/bootstrap-site.yml, depending on what mount method you have chosen:

    define_options:
  mount-using: 'loopback' # or guestfs/docker

  3. Create the image:

    xbstrap run initialize-empty-image

  4. Copy the system onto it:

    xbstrap run make-image

  5. Launch the image using QEMU:

    xbstrap run qemu # Note that you can combine the last two operations: xbstrap run make-image qemu

Alternatively, you can call the necessary scripts manually (check their help messages for more information):

  • ../src/managarm/tools/gen-initrd.py and ../src/scripts/update-image.py for copying the files onto the image (the mount method can be selected with the --mount-using argument)
  • ../src/scripts/vm-util.py qemu for launching QEMU

Building with Docker

This section explains how to build Managarm in a Docker environment.

Note: we recommend using cbuildrt instead of Docker as it is faster, requires less privileges and is better tested (we use cbuildrt on our continuous integration build server, so breakages are more noticeable).

  1. Complete the Preparations section.
  2. Install Docker.
  3. Build a Docker image from the provided Dockerfile: 
    docker build -t managarm-buildenv --build-arg=USER=$(id -u) src/docker
  4. Create a bootstrap-site.yml file inside the build directory containing: 
    container:
  runtime: docker
  image: managarm-buildenv
  src_mount: /var/bootstrap-managarm/src
  build_mount: /var/bootstrap-managarm/build
  allow_containerless: true
    This bootstrap-site.yml will instruct our build system to invoke the build scripts within your container image.

Now proceed to the Building section.

Building without containers

This section explains how to build Managarm with manual installation of the build dependencies.

Note: we recommend using cbuildrt as it provides a clean build environment separate from your host machine, so issues are less frequent and easier to reproduce. It also allows you to use pre-built tools from our build server rather than compiling everything from source.

Be aware that not only missing dependencies can impact the build process: some ports might incorrectly detect optional dependencies from the host operating system. Since it is infeasible to test all possible combinations of host packages, support for building outside of containers is not a priority of the project.

  1. Complete the Preparations section.
  2. Certain programs are required to build managarm; to get a list of the corresponding Debian packages we refer you to the Dockerfile.
  3. meson is required. There is a Debian package, but as of Debian Stretch, a newer version is required. Install it from pip: 
    pip3 install meson
  4. For managarm kernel documentation you may also want mdbook. You can install it from your distribution repositories, or using cargo: 
    cargo install --git https://github.com/rust-lang/mdBook.git mdbook

Now proceed to the Building paragraph.

Updating Packages

This section describes how to keep an existing Managarm build up to date after upstream repositories have merged changes.

Updating system packages

To keep up with updates of Managarm's kernel and drivers, it is usually enough to keep the packages managarm-kernel, managarm-system, mlibc and mlibc-headers up to date.

If you have local changes to these system packages, it is usually advisable to update the packages via git (see the following section). In other cases, xbstrap can be used to update these packages using the command:

xbstrap install -u --deps-of managarm-system --deps-of managarm-kernel --deps-of mlibc mlibc-headers

It is important to update mlibc-headers when mlibc modifies its public headers. If mlibc-headers is out of date, mlibc will still build fine but ports will not see any updates in C library headers.

Updating via git (or other version control tools)

xbstrap manages source repositories by using each package's upstream version control tool. In most cases, upstreams use git (although hg and svn are also supported by xbstrap). To update a package via git (or any other VCS), simply pull a new revision of the package and use xbstrap to rebuild it.

For example, pulling a new revision of the managarm repository and rebuilding the managarm-system and managarm-kernel packages can be achived via:

cd ~/managarm/src/managarm
git pull origin master
cd ~/managarm/build
xbstrap install --rebuild managarm-system managarm-kernel

Note: When updating packages through VCS, make sure to also keep their dependencies up to date. For the system packages mentioned above these dependencies include frigg, libasync, libsmarter, fafnir and lewis.

Updating ports

Updating ports via xbstrap works similarly as updating system packages. However, ports usually build from fixed versions (and not from branches). If local changes have been applied to such a fixed version (e.g., by patches), xbstrap refuses to automatically check out a different commit, as doing a git checkout (or similar) would risk loss of local commits and/or uncommitted changes. To override this behavior, pass --reset to discard local commits (or --hard-reset to discard uncommitted changes and local commits).

For example, to update bash, run

# Do a dry-run first. Make sure to verify that no local changes would be discarded.
xbstrap install -u -n bash
xbstrap install -u --reset bash

Note: It is safe to use --reset to remove patches that have been applied by xbstrap itself. However, care should be taken to not update repositories with important local modifications that you have applied yourself.

In case of git, local commits can usually be recovered after --reset by inspecting git reflog; uncommitted changes that are discarded by --hard-reset cannot easily be restored.

Contributing

This section of the Managarm documentation helps you on contributing to Managarm.

Communication

Discord

Most of our communication happens on our Discord at https://discord.gg/7WB6Ur3.

GitHub

Some of our communication takes place on GitHub at https://github.com/managarm/managarm.

IRC

We also have an IRC channel #managarm on irc.libera.chat, please keep in mind that our former channel found on freenode is no longer in use.

Contributing to The Managarm Project

First off, thanks for taking the time to contribute! ❤️

All types of contributions are encouraged and valued. See the Table of Contents for different ways to help and details about how this project handles them. Please make sure to read the relevant section before making your contribution. It will make it a lot easier for us maintainers and smooth out the experience for all involved. The community looks forward to your contributions. 🎉

Table of Contents

I Have a Question

Our primary way of communication is our Discord server, please don't hesitate to ask a question there, we are more then willing to help. We also use GitHub Issues. You can search here to see if a question has already been answered before.

How do I contribute?

When contributing to this project, you must agree that you have authored 100% of the content, that you have the necessary rights to the content and that the content you contribute may be provided under the project license.

Reporting Bugs

Submitting a Bug Report

A good bug report shouldn't leave others needing to chase you up for more information. Therefore, we ask you to investigate carefully, collect information and describe the issue in detail in your report. Please complete the following steps in advance to help us fix any potential bug as fast as possible.

We use GitHub issues to track bugs and errors. If you run into an issue with the project:

  • Open an Issue. (Since we can't be sure at this point whether it is a bug or not, we ask you not to talk about a bug yet and not to label the issue.)
  • Explain the behavior you would expect and the actual behavior.
  • Please provide as much context as possible and describe the reproduction steps that someone else can follow to recreate the issue on their own. This usually includes your code. For good bug reports you should isolate the problem and create a reduced test case.
  • Collect information about the bug:
    • Your input and the output
    • Can the bug be reproduced with the latest nightly image and/or with current packages from our package repositories?

Your First Code Contribution

This section of the Guide is Work-In-Progress. Please come back later for more information.

For instructions on how to setup the build environment, how to build and how to run Managarm we refer you to the bootstrap-managarm repository here.

Improving The Documentation

This section of the Guide is Work-In-Progress. Please come back later for more information.

Styleguides

Coding Style

For the general coding style used in The Managarm Project we refer you to the coding style.

Commit Messages

For the general commit message style used in The Managarm Project we refer you to the commit message style.

Attribution

This guide is based on the contributing-gen. Make your own!

Contributing

This section of the Managarm documentation helps you on contributing to Managarm.

Communication

Discord

Most of our communication happens on our Discord at https://discord.gg/7WB6Ur3.

GitHub

Some of our communication takes place on GitHub at https://github.com/managarm/managarm.

IRC

We also have an IRC channel #managarm on irc.libera.chat, please keep in mind that our former channel found on freenode is no longer in use.

Contributing to The Managarm Project

First off, thanks for taking the time to contribute! ❤️

All types of contributions are encouraged and valued. See the Table of Contents for different ways to help and details about how this project handles them. Please make sure to read the relevant section before making your contribution. It will make it a lot easier for us maintainers and smooth out the experience for all involved. The community looks forward to your contributions. 🎉

Table of Contents

I Have a Question

Our primary way of communication is our Discord server, please don't hesitate to ask a question there, we are more then willing to help. We also use GitHub Issues. You can search here to see if a question has already been answered before.

How do I contribute?

When contributing to this project, you must agree that you have authored 100% of the content, that you have the necessary rights to the content and that the content you contribute may be provided under the project license.

Reporting Bugs

Submitting a Bug Report

A good bug report shouldn't leave others needing to chase you up for more information. Therefore, we ask you to investigate carefully, collect information and describe the issue in detail in your report. Please complete the following steps in advance to help us fix any potential bug as fast as possible.

We use GitHub issues to track bugs and errors. If you run into an issue with the project:

  • Open an Issue. (Since we can't be sure at this point whether it is a bug or not, we ask you not to talk about a bug yet and not to label the issue.)
  • Explain the behavior you would expect and the actual behavior.
  • Please provide as much context as possible and describe the reproduction steps that someone else can follow to recreate the issue on their own. This usually includes your code. For good bug reports you should isolate the problem and create a reduced test case.
  • Collect information about the bug:
    • Your input and the output
    • Can the bug be reproduced with the latest nightly image and/or with current packages from our package repositories?

Your First Code Contribution

This section of the Guide is Work-In-Progress. Please come back later for more information.

For instructions on how to setup the build environment, how to build and how to run Managarm we refer you to the bootstrap-managarm repository here.

Improving The Documentation

This section of the Guide is Work-In-Progress. Please come back later for more information.

Styleguides

Coding Style

For the general coding style used in The Managarm Project we refer you to the coding style.

Commit Messages

For the general commit message style used in The Managarm Project we refer you to the commit message style.

Attribution

This guide is based on the contributing-gen. Make your own!

xbstrap-Workflow

After modifying the source code, xbstrap is usually used to recompile Managarm's packages and to run the resulting image in a virtual machine (such as qemu). This section gives a quick overview of useful xbstrap subcommands that are utilized to develop Managarm.

Rebuilding packages

Changes to Managarm almost always involve the packages managarm-kernel, managarm-system (which contains drivers and servers), mlibc (our C library), or mlibc-headers (which must be rebuilt after changing public mlibc headers). xbstrap can be used to rebuild these packages using

xbstrap install --rebuild managarm-system

(and similarly for packages other than managarm-system). After rebuilding a package, the make-image step needs to be invoked again to update the disk image (see the section on building Managarm of this handbook):

xbstrap run make-image
# Or `xbstrap run make-image qemu` to also run the image in qemu.

Sometimes, it can become necessary to re-run the configure scripts of ports (or Meson/CMake). This is usually the case if build scripts and/or configuration files have changed in ways that the build system does not anticipate. Invoking the configure step again is done via:

xbstrap install --reconfigure managarm-system

LSP setup

With cbuildrt>=0.1.2 and xbstrap>=0.26.0, it is now possible to run clangd server inside the build context. This provides autocompletion, hover information, basic refactoring and other features to your text editor of choice.

As the server runs inside a container or within a modified environment, which is a nonstandard configuration, some editor configuration will be required.

Common setup

Using the scripts/managarm-lsp-launcher.sh script in the bootstrap-managarm repository, we can conveniently launch an LSP server in our build environment.

This script discovers what package context you're currently in and runs clangd appropriately. It relies on the compile_commands.json link to figure out what package you're currently in. To create this link, run:

xbstrap -C /path/to/build-dir lsp <package> -- ln -s @THIS_BUILD_DIR@/compile_commands.json

For instance, if <package> is managarm-system, it will place a link in <source dir>/managarm/compile_commands.json, as this is where the xbstrap managarm source is located.

Note on "multi build" sources

Some code, such as the managarm kernel and servers, is built under two distinct configurations from the same source. For these, the above procedure will not be sufficient (which one of the two compile databases do you pick?). As a workaround, we can instruct clangd to conditionally pick a compile database.

In the managarm source directory, drop in a snippet like this one into a file called .clangd at the root:

---
CompileFlags:
  CompilationDatabase: /var/lib/managarm-buildenv/build/pkg-builds/managarm-system
---
If:
  PathMatch: kernel/.*
CompileFlags:
  CompilationDatabase: /var/lib/managarm-buildenv/build/pkg-builds/managarm-kernel

# vim: set ft=yaml :

Your paths might vary, and the LSP launcher relies on a compile database link existing (even if broken), so the above step with ln -s is still necessary.

Editor specific setup

vim (vim-lsp)

To configure vim-lsp, we recommend using a conditional on your working directory based in your Vim startup file:

if executable('xbstrap') && getcwd() =~ '/path/to/bootstrap-managarm/.*'
    au User lsp_setup call lsp#register_server({
        \ 'name': 'xbstrap-lsp-managarm',
        \ 'cmd': {server_info->['/path/to/managarm-lsp-launcher.sh', '/path/to/managarm/build/']},
        \ 'whitelist': ['c', 'cpp', 'objc', 'objcpp'],
        \ })
endif

GNU Emacs (eglot)

In GNU Emacs, you can use directory local variables to adjust Eglot in your clone of Managarm alone, by placing a file like the following into it:

;;; Directory Local Variables            -*- no-byte-compile: t -*-
;;; For more information see (info "(emacs) Directory Variables")

((nil . ((eglot-server-programs
          . (((c-mode c++-mode) . ("/.../managarm-lsp-launcher.sh" "/.../build"))
)))))

Which translates, roughly, to: for each file in this project, associate c-mode and c++-mode with managarm-lsp-launcher.sh. This is done like so in order to have consistent Eglot variables across the entire project.

VSCodium (LLVM clangd)

The LLVM clangd plugin allows you to change the path to clangd. We can use this to launch our wrapper:

{
    "clangd.path": "/path/to/managarm-lsp-launcher.sh",
    "clangd.arguments": ["/path/to/managarm/build/"],
    "clangd.onConfigChanged": "restart"
}

Troubleshooting

In case of trouble, please invoke the script directly like so:

/path/to/managarm-lsp-launcher.sh path/to/build; echo "$?"
  • If the script exits with no output and exit code 1, your build directory is incorrect.
  • If the script exits with no output and exit code 2, there is no compile_commands.json.
  • If you see the clangd banner, but you are seeing issues in the editor, enable the LSP logs in your editor (for instance, g:lsp_log_verbose and g:lsp_log_file with vim-lsp), and check the logs.
  • Export CLANGD_FLAGS="--log=verbose" before running your text editor to increase log verbosity and try again.
  • LLVM 13 changed the meaning of .clangd. It used to be a directory containing the indexer cache, but it was moved to $XDG_CACHE_HOME/clangd. If .clangd is a directory, remove it.
  • If there is no obvious solution, reach out for help.

Commit messages

This section of the Managarm documentation describes the commit message conventions that we use.

General

For commit messages we usually write something like this:

<module>: <A sentence describing what was changed>

If the intent or implementation are not immediately obvious, the commit should include an explanations of what is done. Of course, we expect to see this in any pull request too.

Modules

We use modules to describe where in the system the change is made. For the Managarm repo, we use the following modules:

  • thor, optionally followed by a subsystem or arch, like thor/pci or thor/x86. This is used for changes to the main kernel of Managarm, thor.
  • eir, optionally followed by a architecture, like eir/x86. This is used for changes to Managarm's prekernel, eir.
  • posix, used for everyting in the posix emulation layer.
  • docs, used when updating the documentation, like the one you are reading now!
  • core/<submodule>, submodule can be either drm or virtio at the time of writing. This is used for everything related to the core of the DRM interface or virtio handling.
  • drivers/<drivername>, where the driver name is the driver being worked on, like drivers/libblockfs for example. This is used for everything driver related.
  • hel, used for everything related to the hel and helix syscall api.
  • mbus, used for everything related to mbus.
  • protocols/<protocol>, where protocol is the protocol that is being changed. This is used for every protocol change made.
  • netserver, used for every change to the network server.
  • tests, used when working on the testsuites.
  • tools/<toolname>, used when working on the tools that the Managarm repo has, currently analyze-profile, gen-initrd, bakesvr and ostrace.
  • utils/<utilname>, used when updating various utilities that reside in this repo, currently lsmbus and runsvr.
  • build, used when editing the meson.build file.
  • meta, used for meta changes, for example a readme update.
  • .github, used when modifying files found in the .github directory.

Commit messages in the bootstrap repo

For bootstrap-managarm, the commit message usually follows the same convention as the main repo, but there are different modules there. As we're using the Gentoo style of package separation with the file names (sys-apps.yml for example), we use that as a module designator too in some cases. For your use, we've listed the used modules down below:

  • <port name>, when making changes to a port, we use the name of the port as a module specifier.
  • host-<tool name>, when making changes to host tools used during the build.
  • <gentoo package category>, where the category is something like sys-apps (see here for more examples). This is only used when moving ports around.
  • docker, used when updating the Dockerfile.
  • meta, used for meta changes, for example a readme update.
  • ci, when making changes to the ci scripts that reside in this repo.
  • .github, used when modifying files found in the .github directory.

There are two exceptions on the commit messages used in this repo, namely when adding a new port and when updating a port. When adding a new port the following message is used:

<package name>: Add port

And when updating a port the following message is used:

<port name>: Update from <old version> to <new version> <optionally, if it fixes severe security vulnerabilities, list them here, for example by listing their CVE number> <optionally, if there have been other changes to the build recipe, like new configure flags, list them here>

Coding standard for The Managarm Project

The Managarm Project follows the following coding standard.

Managarm-specific Guidelines

This section lists the most important coding style guidelines that Managarm follows. Specifically, we list the guidelines for which Managarm is likely to diverge from other projects. Please read them carefully before preparing a pull request.

  • Data types are CamelCase.
  • Variable names are camelCase.
  • Private members use a trailing underscore, like privateMember_.
  • Indentation uses tabs.
  • Braces are placed similarly to existing code.
  • Single line bodies of if, while, for all go to a seperate line, like
if(expression)
	one-line statement;
  • All headers have include guards. We use #pragma once for all headers with the exception of public headers in mlibc, which uses the classical include guards.
  • Preferred line limit is 100 characters.

Additional Guidelines

The coding style guidelines in this section are mostly well-established; we list them for completeness and to assist new contributors.

Entity Naming

  • Constants shall begin with an upper case letter, shall be upper case and words shall be separated by an underscore, like so THIS_IS_A_CONSTANT.
  • Macros shall begin with an upper case letter, shall be upper case and words shall be separated by an underscore, like so THIS_IS_A_MACRO.

Names

  • Use sensible, descriptive names.
  • Only use English names.
  • Variables with a large scope shall have long names, variables with a small scope can have short names.
  • Use namespaces for identifiers declared in different modules.
  • Use name prefixes for identifiers declared in different modules.

Indentation and Spacing

  • Each statement shall be placed on a line on its own.
  • Pointers and references shall be declared like T *x and T &x.
  • The const keyword shall be used like const int.
  • In a switch statement, cases shall be indented relative to the switch statement.

Example:

switch(condition) {
	case 1:
		code;
		break;
	case 2:
		code;
		break;
	default:
		break;
}
  • Classes and their access modifiers shall be indented on the same level.
  • A struct is preferred over class X { public.
  • All binary arithmetic, bitwise and assignment operators and the ternary conditional operator (?:) shall be surrounded by spaces; the comma operator shall be followed by a space but not preceded; all other operators shall not be used with spaces.
  • Braces shall follow "K&R Bracing Style variant One True Bracing". The K&R Bracing Style was first introduced in The C Programming Language by Brian Kernighan and Dennis Ritchie.

The opening brace is placed at the end of the enclosing statement and the closing brace is on a line on its own lined up with the enclosing statement. Statements and declaration between the braces are indented relative to the enclosing statement.

Example:

int main(int argc, char *argv[]) {
	printf("Hello!\n");
	for(int i = 0; i < 10; i++ ) {
		printf("The value of i: %d\n", i);
		if(i == 3) {
			printf("Hey, i is 3!\n");
		}
	}
}

Comments

  • Comments shall be written in english
  • If the purpose of a class or function cannot easily be recognized from its name, the class or function shall be preceded by a comment describing its purpose.
  • Multiline comments shall use the C-style. Be consistent and use the /* ... */ style for multiline comments.
  • Single line comments shall use the C++-style. Be consistent and use the // ... style for single line comments.
  • Use JavaDoc style comments for Doxygen. The comment styles /// and /** ... */ are used by JavaDoc, Doxygen and some other code documenting tools.
  • All comments shall be placed above the line the comment describes, indented identically.

Files

  • File name shall be treated as case sensitive.
  • File names shall be lower case, shall not contain spaces and shall use dashes (-) and not underscores as a word seperator.
  • C source files shall have extension ".c".
  • C header files shall have extension ".h".
  • C++ source files shall have extension ".cpp".
  • C++ header files shall have extension ".hpp".
  • Header files must have include guards. The include guard protects against the header file being included multiple times. We use #pragma once for all headers. Exception: public headers in mlibc have include guards.
  • The name of the macro used in the include guard shall have the same name as the file (excluding the extension) followed by the suffix "_H".
  • All headers shall be included with <> Exception: In programs or libraries that consist of only a single source directory, private headers shall be included with ""
  • Put #include directives at the top of files. Having all #include directives in one place makes it easy to find them.

Declarations

  • Declare class data private. Classes shall encapsulate their data and only provide access to this data by member functions to ensure that data in class objects are consistent.

The exception to the rule is C type struct that only contains data members.

Statements

  • Use gotos only in special circumstances. One possible use of gotos are try-again loops where while or for loops would obscure the structure of the code.

Example:

tryAgain:
    [...]
    if(!foo.compare_exchange(/* ... */))
        goto tryAgain;
  • All switch statements shall have a default label. Even if there is no action for the default label, it shall be included to show that the programmer has considered values not covered by case labels. If the case labels cover all possibilities, it is useful to put an assertion there to document the fact that it is impossible to get here. An assertion also protects from a future situation where a new possibility is introduced by mistake.

Semantics

  • Use plenty of assertions. Assertions are useful to verify pre-conditions, post-conditions and any other conditions that should never happen. Pre-conditions are useful to verify that functions are called with valid arguments. They are also useful as documentation of what argument value ranges a function is designed to work with. However, we do not use assertions for user controlled input.

Assertions are macros that print error messages when the condition is not met. The macros are disabled in release mode and do not cost anything in performance or used memory in the end product.

Example: This square root function is only designed to work with positive numbers. 

#include <assert.h>

double sqrt(double x) {
    // precondition: x is positive
    assert(x > 0);
    double result;
    ...
    // postcondition: result^2 ~= x
    assert(abs(result * result - x) / x < 1E-8) ;
}

Attribution

This guide is based on the Coding Standard Generator. Make your own!

The Design of Managarm

This section of the Guide is Work-In-Progress. Please come back later for more information.

The Design of Managarm

This section of the Guide is Work-In-Progress. Please come back later for more information.

The Design of Managarm

This section of the Guide is Work-In-Progress. Please come back later for more information.

Hel and Helix

This part of the Handbook if Work-In-Progress.

Hel and Helix is the syscall API for Managarm. Hel is the C API and Helix is C++ wrapper for some parts of Hel.

Doxygen Generated API Reference

The generated Documentation for managarm/hel can be found at https://docs.managarm.org/hel-api

thor and eir

This part of the handbook is Work-In-Progress.

thor and eir are the kernel of managarm.

eir is the platform-dependant part of managarm's kernel which hands over control to thor after setup.

thor then proceeds to initialize the memory subsystem, scans and initializes PCI devices, starts the ACPI subsystem and starts the base servers and supporting infrastructure needed to run Managarm's userland. This means that the following programs are started (in order).

  • mbus, which is used to allow servers to find each other.
  • kerncfg, which exposes kernel configuration to servers.
  • srvctl, controls the starting and stopping of servers.
  • kernletcc, can compile and upload small programs (written in lewis) that run in kernel space.
  • clocktracker, provides timekeeping services to servers.
  • posix-subsystem, which runs posix-init, which is Managarm's init, and provides the environment that is expected by POSIX programs.

After starting the initial userspace, thor enters normal operations and handles system calls. The code for thor and eir can found at https://github.com/managarm/managarm/tree/master/kernel.

frigg

This part of the handbook is Work-In-Progress.

frigg is a lightweight utility library for system programming written in C++. frigg has implementations for many frequently used constructs in C++, like vectors, arrays and lists. It also implements memory allocators, utilities for error handling (frg::expected), and logging utilities. In contrast to the C++ standard library, it is entirely freestanding and does not depend on functionality provided by the host. Hence, frigg is used extensively in the Managarm kernel and in mlibc.

The code for frigg can found at https://github.com/managarm/frigg.

libasync

This part of the handbook is Work-In-Progress.

libasync is a support library for supporting C++20 coroutines and C++ senders/receivers. It also provides many asynchronous primitives (e.g., asynchronous events, queues and mutexes). Managarm, being an asynchronous operating system, makes extensive use of the functionality provided by libasync.

The code for libasync can be found at https://github.com/managarm/libasync.

mbus

This part of the Handbook is Work-In-Progress.

mbus is the managarm message bus system. mbus is used by servers to publish objects, which other servers can discover. If a server finds an object of interest, it can then use mbus to connect to that server. Further communication happens over the more common hel streams documented in the hel folder of this handbook.

The code for mbus can be found at https://github.com/managarm/managarm/tree/master/mbus.

bragi

This part of the Handbook if Work-In-Progress.

bragi is the future interface definition language for use in Managarm.

The code for bragi can be found at https://github.com/managarm/bragi.

Requirements

bragi requires python3 and lark-parser.

Sample code

enum enum1 {
	foo = 1,
	bar,
	baz
}

message msg1 1 {
head(256):
	byte[64] bab;
	byte[64] bib;

tail:
	optional tag(13) byte[3] bub = [1,2,3];
	optional byte[] beb = [7];
	string bob = "test";
}

message msg2 2 {
head(128):
	optional byte[64] bab;
	int32 bib = 2345;

tail:
	byte[4] bub = [1,2,3];
	byte beb = 7;
	byte bhb = 7;
	string bob = "test";
}

message msg3 3 {head(13): byte foo = 3;}

message msg4 4 {
head(64):
	uint64 foo;
	byte[16] arr;
tail:
	int32 baz;
	uint32[] bif;
}

Compile the sample code

To compile the sample.idl sample code run:

python setup.py install
bragi

posix subsystem

This part of the Handbook is Work-In-Progress.

The posix subsystem is the core of Managarm's userspace. It is started by thor and handles all posix requests made by userspace programs, like file I/O, memory allocation and sockets. It also implements various Linux API's like epollfd, signalfd, timerfd and inotify. For file I/O on block devices, it communicates with libblockfs, which is responsible for the actual file I/O on ext2 file systems.

On startup, the subsystem runs posix-init, which is a two stage init responsible for bringing up the userland. Thus, posix-init does the following operations:

  • Starting of several servers for storage, this includes the USB host controller drivers (ehci, uhci and xhci) and the block devices (virtio-block and ata).
  • Mounting of the root (/) file system and the various pseudo file systems (procfs, sysfs, devtmpfs, tmpfs and devpts) and entering it via chroot.
  • Executing stage 2, which brings up the rest of the userspace

In stage 2, the following operations take place

  • Starting of udevd, which is responsible for populating /dev and starting of other servers via udev rules.
  • Starting of drivers that are not yet integrated in udev rules.
  • Ensuring that the Direct Rendering Manager (drm), keyboard and mouse are available.
  • Parsing the kernel command line for hints on what userspace program to run.
  • Populating the environment with essential variables.
  • Either launching weston with XWayland support, sway or kmscon, as requested.

Afterwards, init goes to sleep and the userspace is operational.

The code for the posix subsystem can be found at https://github.com/managarm/managarm/tree/master/posix/subsystem, while the code for posix-init can be found at https://github.com/managarm/managarm/tree/master/posix/init.

Managarm drivers

This section of the Guide is Work-In-Progress. Please come back later for more information.

libblockfs

This part of the Handbook is Work-In-Progress.

libblockfs is a support library in Managarm responsible for handling file I/O on block devices like hard drives and USB. It is a general interface to the underlying file systems that are available in Managarm. Userspace programs do not call libblockfs directly, but request functionality through the posix subsystem.

The code for libblockfs can be found at https://github.com/managarm/managarm/tree/master/drivers/libblockfs.

Implementation Notes

This chapter contains notes on various implementation details of the Managarm operating system.

Drivers

This section describes the overall design of drivers in Managarm and gives guidelines and recommendations for authors of new drivers.

IRQ Handling

IRQ handling is one of the most tricky parts in a driver. Handling IRQs incorrectly can not only render the driver unusable but also impact the functionality of other drivers that share the same hardware IRQ line.

General IRQ handling strategy

Handling an IRQ in your driver generally involves the following steps:

  1. Wait for an IRQ (using helix_ng::awaitEvent()).

  2. Determine if the IRQ was triggered by your device (and not by some other device that shares the same IRQ line). This usually requires reading some interrupt status register ("ISR").

    IRQs that are indeed caused by your device will need to be ACKed at a later step, IRQs that were caused by other devices that share the same IRQ line need to be NACKed.

  3. Instruct the hardware to clear the IRQ.

    For level-triggered IRQs, this will de-assert the IRQ (i.e., cause it not be be fired immediately again). For edge-triggered IRQs, this step usually re-enables the hardware device to issue an edge once a new (device-specific) event occurs.

  4. ACK or NACK the IRQ (using helAcknowledgeIrq() with appropriate flags).

  5. Depending on the device: do further processing. For example, some hardware devices will require you to inspect ring buffers to collect the requests that were finished by the device.

The order of these steps is significant: determining if the IRQ was caused by your device only makes sense after an IRQ occurred, and you cannot ACK/NACK without knowing whether the IRQ was caused by your device. Furthermore, not following the above order can lead to subtle bugs; hence, drivers should always stick to this order (see below for additional justification in the case of level-triggered IRQs).

Kernel behavior

The following rules form the basis of the guidelines for drivers below.

The kernel handles IRQs in a strictly sequenced way: when an IRQ line is raised, the kernel marks the IRQ as "in-service" and invokes all IRQ handlers (i.e., IRQ descriptors used by drivers, as well as in-kernel IRQ handlers). While the IRQ is in-service, IRQ handlers (of the same IRQ line) will not be invoked again. The kernel resets the in-service status only after all IRQ handlers (i.e., all drivers) have either ACKed or NACKed the IRQ.

If all drivers NACK an IRQ, the kernel will stall the IRQ line. More precisely, it will mask the line, preventing further IRQs from being raised. This mechanism protects against "IRQ storms", i.e., recurring IRQs that block overall system progress since the system does not know how to handle them. Drivers need to take care to not accidentially cause a stall.

Guidelines for drivers and potential pitfalls

To avoid stalls, drivers should take the following constraints into consideration:

  • A driver must avoid to clear IRQs that the kernel did not deliver to the driver yet. Clearing an IRQ that was not delivered yet causes the IRQ to not be recognized by any device; that is, it causes the IRQ to become "spurious".

    If spurious IRQs cannot be avoided (e.g., because a device might assert and then clear its IRQs during a hardware reset), drivers must call kHelAcknowledge() with the kHelAckKick flag. Failing to "kick" the spurious IRQ usually lead to all drivers NACKing the IRQ (and hence stall the IRQ line).

  • "Wrong ACK": ACKing an IRQ that was not actually caused by the device in question is not harmful as long as it happens only rarely: if another driver that shares the IRQ line also ACKs, the wrong ACK does not impact system-wide IRQ behavior. Otherwise, if all other drivers NACK, the ACK causes the IRQ temporarily to not be stalled.

  • "Wrong NACK": the reverse, namely NACKing an IRQ that actually came from the driver's corresponding device is problematic since it can cause stalls (if all other drivers NACK).

  • After obtaining a handle to an IRQ descriptor, a driver must handle IRQs in a timely manner. Keeping IRQs in-service for extended periods of time can delay other drivers that share the same IRQ line.

  • Handling an IRQ by a kernlet requires special attention during initialization: if an IRQ is currently in-service, attaching a kernlet does not immediately run the kernlet. Thus, if a driver wants to handle IRQs exclusively through the use of kernlets, the IRQ must potentially be ACKed after installing the kernlet. This can be achieved by using helAcknowledgeIrq() with the kHelAckKick | kHelAckClear flags (which is not harmful since it is equivalent to a wrong ACK).

Considerations for level-triggered IRQs:

  • Level-triggered IRQs must always clear an IRQ before ACKing it (see above). ACKing a level-triggered IRQ before clearing will cause the IRQ to be re-raised immediately. Clearing the IRQ after the re-raise may cause the IRQ to be become spurious (and thus stall the IRQ line).

Considerations for edge-triggered IRQs:

  • The kernel will buffer (a single) IRQ if an edge happens while an edge-triggered IRQ is still in-service. This ensures that IRQs that occur after clearing the ISR but before ACKing are handled correctly.

  • Spurious IRQs are problematic for edge-triggered IRQs: similarly to level-triggered IRQs, drivers will NACK spurious IRQs and thus to stall the IRQ line. This is not an issue for devices that do not re-issue edges until the ISR register is cleared yet. However, various legacy devices (such as the x86's keyboard controller) have no ISR register. If these devices are not on shared IRQ lines, they can simply always ACK all IRQs to avoid stalls.

Implementation Notes: Thor

This section discusses various implementation details of Managarm's kernel.

Initialization

Thor's initialization consists of multiple stages:

  1. Early initialization (in thorInitialize()). This stage performs rudimentary initialization of the system to enable the use of basic kernel infrastructure. Since it runs before global constructors, code in this stage cannot use global variables unless they are constinit or defined as static singletons inside functions.

    The early initialization stage is split into the following steps:

    1. Initialization of basic features the CPU architecture (in initializeArchitecture()). Among other (architecture-dependent) things, this step initializes access to CPU-local data (via getCpuData()).

    2. Initialization of debug sinks and loggers. This is done early such that other initialization code can use Thor's usual logging infrastructure (including infoLogger() and panicLogger()).

    3. Initialization of the memory management subsystem.

  2. Running global constructors. This stage runs global C++ constructors. Among other things, global constructors are used to build the initgraph data structure that is used in the next stage.

  3. Running the so-called initgraph (in thorMain()). The initgraph is a data structure that consists of tasks and dependencies between tasks. Tasks can define both dependencies and reverse dependencies; this way, the initgraph can easily be used to express dependencies between generic and subsystem-specific tasks.

    Thor does not run the entire initgraph at once; instead, the initgraph is split into multiple milestones:

    1. Reaching the tasking-available milestone. Early tasks of the initgraph run directly in thorMain, before multi-tasking or IRQ support is available.

    2. Running the remaining initgraph on a kernel fiber. Once the tasking-available milestone is reached, Thor enters multi-tasking mode and runs the remanining tasks of the initgraph in a fiber (= kernel thread).

      Since IRQ support is not available before tasking-available is reached, all tasks that depend on IRQs must depend (directly or indirectly) on tasking-available.

Scheduling

Theory

We first develop the theoretical model that Managarm's scheduling heuristic is based on. Even though our goal is to work with discrete time slices, it will be beneficial to imagine that time slices can arbitrarily be split up into smaller sub-slices.

Let:

  • \(s_i\) be the length of the \(i\)-th time slice,
  • \(n_i\) be the number of threads that are schedulable in time slice \(i\) (i.e., threads that are either running or runnable, but not blocking),
  • \(\alpha_i(t)\) be 1 if thread \(t\) is schedulable in time slice \(i\), and 0 otherwise,
  • and let \(r_\ell(t)\) be the actual running time of thread \(t\) up to (and including) time slice \(\ell\).

Deciding which thread to run. From a fairness perspective, it would be ideal to run all \(n_i\) threads for time \(\frac{s_i}{n_i}\) in time slice \(i\) (i.e., it would be ideal to split up the time slice into \(n_i\) sub-slices). In reality, we can only run a single thread per time slice; however, we can still try to balance the running time of each thread such that it approaches the ideal scenario. For this purpse, Managarm defines the unfairness of thread \(t\) as:

\[ u_\ell(t) = \left( \sum_{i=0}^\ell \alpha_i(t) \frac{s_i}{n_i} \right) - r_\ell(t) \]

In our idealized scenario, we have \(u(t) = 0\) at all times: if we split the \(i\)-th time slice into \(n_i\) sub-slices of length \(\frac{s_i}{n_i}\) and let each thread run in exactly one of the sub-slices, then \(r_\ell(t)\) would exactly equal the sum of all \(\frac{s_i}{n_i}\). Thus, if \(u(t) < 0\) (respectively \(u(t) > 0\)), thread \(t\) has been active for longer (respectively shorter) than it would have been in the ideal scenario. Since \(u(t)\) decreases if thread \(t\) runs (and increases if a thread other than \(t\) runs), we always schedule the thread with the highest value of \(u(t)\).

Picking the length of a time slice. Our scheduling heuristic also has to pick the length of time slice \(s_\ell\). For this purpose, consider the thread \(t_0\) that runs in that time slice. We want to run \(t_0\) until \(u(t_1) \geq u(t_0)\), where \(t_1\) is the next best thread. While thread \(t_0\) runs, \(u(t_0)\) evolves as:

\[ u_\ell(t_0) = u_{\ell-1}(t_0) + \frac{s_\ell}{n_\ell} - s_\ell \]

on the other hand, \(u(t_1)\) is given by:

\[ u_\ell(t_1) = u_{\ell-1}(t_1) + \frac{s_\ell}{n_\ell} \]

Hence, \( u(t_1) - u(t_0) \geq 0 \Leftrightarrow s_\ell \geq u_{\ell - 1}(t_0) - u_{\ell - 1}(t_1) \) yields the length of our time slice. In practice, we want to avoid time slices that are too short and pick \( s_\ell \geq u_{\ell - 1}(t_0) - u_{\ell - 1}(t_1) + s_\textrm{gr} \), where \( s_\textrm{gr} \) is some granularity constant (e.g., 10 ms).