How to Create a Custom Scheduler Plugin in LITMUS^RT

A brief guide to creating a new scheduling plugin in LITMUS^RT (based on version 2012.2.)

As an example, we are going to implement a simple semi-partitioned EDF scheduler that migrates jobs among CPUs in a round-robin fashion every 500us of execution. While this is not an overly practical scheduler, it's a good example because it allows to demonstrate how to implement migrations, per-processor state, and custom scheduling timers.

Prerequisites

• A testing environment (i.e., KVM/Qemu or Bochs). This tutorial assumes KVM.
• Strong C programming skills.
• Ideally, some exposure to OS kernel development.

General Guidelines

Work in a checked-out git repository. Do not use the tarball from the web page. This will make keeping track of your edits and incorporating upstream changes much easier.

Commit early, commit often. Make many small commits a you go along. You can clean them up later using git rebase.

Do not commit to the master branch. This will make incorporating upstream changes much easier.

Follow the kernel coding standard defined in Documentation/CodingStyle, even when writing “throw away” code.

Step 0: Checkout and Compile the Kernel

First, obtain a copy of the LITMUS^RT kernel.

$ git clone http://www.litmus-rt.org/src/litmus-rt.git
Cloning into litmus-rt...                                                                                                                                                                                       
$ cd litmus-rt/                                                                                                                                                               
$ ls
COPYING  Documentation  Kconfig      Makefile  REPORTING-BUGS  block   drivers   fs       init  kernel  litmus  net      scripts   sound  usr
CREDITS  Kbuild         MAINTAINERS  README    arch            crypto  firmware  include  ipc   lib     mm      samples  security  tools  virt

Next, obtain a working kernel configuration. For this tutorial, we are going to use the default KVM configuration.

$ wget http://www.litmus-rt.org/releases/2012.2/x86_64-config                                                                                                       
[...]
2012-08-13 14:22:25 (13.7 MB/s) - "x86_64-config" saved [52837/52837]
$ cp x86_64-config .config

Compile the kernel. On x86, the kernel build target is bzImage. Note that we do not compile modules for the default KVM configuration because all necessary drivers are statically compiled into the kernel image.

$ make -j16 bzImage
[...]
  CC      arch/x86/boot/compressed/cmdline.o
  CC      arch/x86/boot/compressed/early_serial_console.o
  OBJCOPY arch/x86/boot/compressed/vmlinux.bin
  HOSTCC  arch/x86/boot/compressed/mkpiggy
  GZIP    arch/x86/boot/compressed/vmlinux.bin.gz
  MKPIGGY arch/x86/boot/compressed/piggy.S
  AS      arch/x86/boot/compressed/piggy.o
  LD      arch/x86/boot/compressed/vmlinux
  ZOFFSET arch/x86/boot/zoffset.h
  OBJCOPY arch/x86/boot/vmlinux.bin
  AS      arch/x86/boot/header.o
  LD      arch/x86/boot/setup.elf
  OBJCOPY arch/x86/boot/setup.bin
  BUILD   arch/x86/boot/bzImage
Root device is (8, 1)
Setup is 14908 bytes (padded to 15360 bytes).
System is 3334 kB
CRC 3e3102d9
Kernel: arch/x86/boot/bzImage is ready  (#1)

Next, obtain a copy of liblitmus, the corresponding userspace library

$ git clone http://www.litmus-rt.org/src/liblitmus.git
Cloning into liblitmus...
$ cd liblitmus/
$ ls
INSTALL  Makefile  README  arch  bin  inc  include  setsched  showsched  src  tests

Finally, compile liblitmus. Note that this must occur after checking out the kernel since the liblitmus build system pulls some headers out of the kernel repository.

$ make
cp ../litmus-rt/include/litmus/rt_param.h include/litmus/rt_param.h
[...]
gcc -o runtests -m64  core_api.o fdso.o locks.o pcp.o runner.o   -L. -llitmus 

We are now ready to start hacking LITMUS^RT.

Step 1: Dummy File

Create a new file and add it to the build system.

1. Create the file litmus/sched_demo.c (all file names are relative to the kernel repository).

2. Edit the file litmus/Makefile to add sched_demo.o to the list named obj-y.

3. Compile the kernel to see if everything works.

After you've verified there are no errors, create a git commit.

Step 2: Dummy Plugin

Edit the file litmus/sched_demo.c to declare a dummy plugin (that implements no particular policy and that rejects all tasks).

The required code looks like this (litmus/sched_demo.c):

   1 #include <litmus/sched_plugin.h>
   2 
   3 
   4 static struct task_struct* demo_schedule(struct task_struct * prev)
   5 {
   6         /* We don't schedule anything for now. NULL means "schedule background work". */
   7         return NULL;
   8 }
   9 
  10 static long demo_admit_task(struct task_struct *tsk)
  11 {
  12         /* Reject every task. */
  13         return -EINVAL;
  14 }
  15 
  16 static struct sched_plugin demo_plugin = {
  17         .plugin_name            = "DEMO",
  18         .schedule               = demo_schedule,
  19         .admit_task             = demo_admit_task,
  20 };
  21 
  22 static int __init init_demo(void)
  23 {
  24         return register_sched_plugin(&demo_plugin);
  25 }
  26 
  27 module_init(init_demo);

With these changes, it should be possible to boot the kernel and select the DEMO plugin with setsched.

To test if it rejects tasks as expected, run rtspin (inside the VM):

[root@litmus-rt ~]# setsched DEMO
[root@litmus-rt ~]# showsched 
DEMO
[root@litmus-rt ~]# liblitmus/rtspin 10 100 10
could not become RT task: Invalid argument

The plugin did indeed reject the task, as expected.

Step 3: Define the Per-Processor State

In this step, we define the scheduler state on each processor.

Step 4: Augment the Per-Task State

Our scheduler needs to keep track of...

Step 5: Initialize the Scheduler Plugin

To be written...

Step 6: Initialize new Tasks

To be written...

Step 7: Enable Admission of Tasks

To be written...

Step 8: Boot the Kernel in KVM

To be written...

kvm -gdb tcp::3008 -smp 4 -hda /RTS/litmus-rt/work/kvm-images/bbb-litmus-rt.img -m 2000 -net nic,model=e1000 -net user -k en-us -kernel /home/bbb/ldev/litmus-rt/arch/x86/boot/bzImage -append console=ttyS0 ro root=/dev/hda1 no_timer_check  no_timer_check -nographic -redir tcp:2104::22

Step 9: Observe the Debugging TRACE() Log

To be written...

Step 10: Trace Task Execution

To be written...

Step 11: Visualize the Trace

To be written...

Step 12: Record Scheduling Overheads

To be written...

Step 13: Analyze Scheduling Overheads

To be written...