Differences between revisions 13 and 15 (spanning 2 versions)
Revision 13 as of 2012-08-13 14:40:59
Size: 10741
Editor: bbb
Comment:
Revision 15 as of 2012-08-14 10:23:29
Size: 2148
Editor: bbb
Comment:
Deletions are marked like this. Additions are marked like this.
Line 4: Line 4:

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'''.
Line 13: Line 11:
Line 18: Line 15:
Commit early, commit often. Make many small commits a you go along. You can clean them up later using git rebase. Test incrementally to catch errors early. Compile test after each edit. Test-boot as often as possible. The earlier you catch an error, the easier it is to debug.

Commit early, commit often. Make many small commits a you go along. You can clean them up later using `git rebase`.
Line 22: Line 21:
Follow the kernel coding standard defined in Documentation/CodingStyle, even when writing “throw away” code. Follow the kernel coding standard defined in [[http://lxr.linux.no/linux/Documentation/CodingStyle|Documentation/CodingStyle]], even when writing “throw away” code.
Line 25: Line 24:
== Step 0: Checkout and Compile the Kernel == == Steps ==
Line 27: Line 26:
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
}}}
The tutorial is structured in a series of steps, which are intended to be completed sequentially. When working through these, you should reproduce the instructions on your own local machine. If something seems unclear, please feel free to ask on the [[Mailinglist|mailinglist]] for clarification.
Line 37: Line 28:
Next, obtain a working kernel configuration. For this tutorial, we are going to use the default KVM configuration. In the first seven steps, the tutorial re-creates a ''partitioned EDF'' (P-EDF) scheduler. In contrast to the PSN-EDF plugin shipping with LITMUS^RT^, the demo implementation does not support locking and non-preemptive sections to keep it simple.
Line 39: Line 30:
{{{
$ 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`):
{{{#!highlight c
#include <litmus/sched_plugin.h>
#include <litmus/preempt.h>

static struct task_struct* demo_schedule(struct task_struct * prev)
{
 /* This mandatory. It triggers a transition in the LITMUS^RT remote
  * preemption state machine. Call this AFTER the plugin has made a local
  * scheduling decision.
  */
 sched_state_task_picked();

 /* We don't schedule anything for now. NULL means "schedule background work". */
 return NULL;
}

static long demo_admit_task(struct task_struct *tsk)
{
 /* Reject every task. */
 return -EINVAL;
}

static struct sched_plugin demo_plugin = {
 .plugin_name = "DEMO",
 .schedule = demo_schedule,
 .admit_task = demo_admit_task,
};

static int __init init_demo(void)
{
 return register_sched_plugin(&demo_plugin);
}

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: Observe the Debugging TRACE() Log =

Next, we are going to export some debugging message with the `TRACE()` macro. Specifically, we use `TRACE_TASK()` to record
tasks as they are being rejected by the plugin.

To do so, include `include/litmus/debug_trace.h` and change `demo_admit_task()` to look like this:
{{{
static long demo_admit_task(struct task_struct *tsk)
{
 TRACE_TASK(tsk, "rejected by demo plugin.\n");

 /* Reject every task. */
 return -EINVAL;
}
}}}

It is now possible to see the message when a task is rejected in `/dev/litmus/log`:
{{{
[root@litmus-rt ~]# setsched DEMO
[root@litmus-rt ~]# cat /dev/litmus/log > debug.txt &
[1] 1462
[root@litmus-rt ~]# liblitmus/rtspin 10 100 10
could not become RT task: Invalid argument
[root@litmus-rt ~]# cat debug.txt
1 P3 [vprintk@kernel/printk.c:883]: Setting up rt task parameters for process 1464.
2 P1 [alloc_ctrl_page@litmus/ctrldev.c:25]: (rtspin/1464:0) alloc_ctrl_page ctrl_page = ffff88007881d000
3 P1 [map_ctrl_page@litmus/ctrldev.c:39]: (rtspin/1464:0) litmus/ctrl: mapping ffff88007881d000 (pfn:7881d) to 0x7fc686ed5000 (prot:8000000000000027)
4 P1 [litmus_ctrl_mmap@litmus/ctrldev.c:114]: (rtspin/1464:0) litmus_ctrl_mmap flags=0x2166073 prot=0x8000000000000027
5 P1 [demo_admit_task@litmus/sched_demo.c:21]: (rtspin/1464:0) rejected by demo plugin.
6 P1 [litmus_ctrl_vm_close@litmus/ctrldev.c:53]: (rtspin/1464:0) litmus_ctrl_vm_close flags=0x2164073 prot=0x27
7 P1 [litmus_ctrl_vm_close@litmus/ctrldev.c:58]: (rtspin/1464:0) litmus/ctrl: 00007fc686ed5000:00007fc686ed6000 vma:ffff8800793e01e0 vma->vm_private_data: (null) closed.
8 P1 [exit_litmus@litmus/litmus.c:497]: (rtspin/1464:0) freeing ctrl_page ffff88007881d000
}}}

Tracing is explained in more detail in [[Tracing|the tracing tutorial]].

== Step 4: Define the Per-Processor State ==
In this step, we define the scheduler state on each processor.

Add the following headers to `sched_demo.c`:
{{{
#include <litmus/litmus.h>
#include <litmus/rt_domain.h>
#include <litmus/edf_common.h>
}}}

{{{
struct demo_cpu_state {
 rt_domain_t local_queues;
 int cpu;

 struct task_struct* scheduled;
};

DEFINE_PER_CPU(struct demo_cpu_state, demo_cpu_state);

#define cpu_state_for(cpu_id) (&per_cpu(demo_cpu_state, cpu_id))

}}}

{{{
static long demo_activate_plugin(void)
{
 int cpu;
 struct demo_cpu_state *state;

 for_each_online_cpu(cpu) {
  TRACE("Initializing CPU%d...\n", cpu);

  state = cpu_state_for(cpu);

  state->cpu = cpu;
  state->scheduled = NULL;
  edf_domain_init(&state->local_queues, NULL, NULL);
 }

 return 0;
}
}}}

{{{
static struct sched_plugin demo_plugin = {
 .plugin_name = "DEMO",
 .schedule = demo_schedule,
 .admit_task = demo_admit_task,
 .activate_plugin = demo_activate_plugin,
};
}}}

{{{
[root@litmus-rt ~]# cat /dev/litmus/log > debug.txt &
[1] 1459
[root@litmus-rt ~]# setsched DEMO
[root@litmus-rt ~]# cat debug.txt
1 P2 [demo_activate_plugin@litmus/sched_demo.c:48]: Initializing CPU0...
2 P2 [demo_activate_plugin@litmus/sched_demo.c:48]: Initializing CPU1...
3 P2 [demo_activate_plugin@litmus/sched_demo.c:48]: Initializing CPU2...
4 P2 [demo_activate_plugin@litmus/sched_demo.c:48]: Initializing CPU3...
5 P2 [vprintk@kernel/printk.c:883]: <6>Switching to LITMUS^RT plugin DEMO.
}}}

== Step 5: Augment the Per-Task State ==
Our scheduler needs to keep track of...



= Planned stuff =

== 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...''
 * [[/Step0|Step 0: checkout and compile the kernel]]
 * [[/Step1|Step 1: add a source file to the build system]]
 * [[/Step2|Step 2: register a dummy plugin]]
 * [[/Step3|Step 3: log debug message with TRACE()]]
 * [[/Step4|Step 4: define P-EDF per-processor state]]
 * [[/Step5|Step 5: add P-EDF scheduling function]]
 * [[/Step6|Step 6: add support for task state changes]]
 * [[/Step7|Step 7: implement preemptive P-EDF]]
 * [[/Step8|Step 8: admit real-time tasks]]

How to Create a Custom Scheduler Plugin in LITMUS^RT

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

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.

Test incrementally to catch errors early. Compile test after each edit. Test-boot as often as possible. The earlier you catch an error, the easier it is to debug.

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.

Steps

The tutorial is structured in a series of steps, which are intended to be completed sequentially. When working through these, you should reproduce the instructions on your own local machine. If something seems unclear, please feel free to ask on the mailinglist for clarification.

In the first seven steps, the tutorial re-creates a partitioned EDF (P-EDF) scheduler. In contrast to the PSN-EDF plugin shipping with LITMUSRT, the demo implementation does not support locking and non-preemptive sections to keep it simple.

CreateAPluginTutorial (last edited 2014-06-12 15:51:56 by bbb)