Advanced Kernel Programming

This is the home page for the "Advanced Kernel Programming" course. Here, you can find information about the lessons and all the material used during the course

Lessons:

• First lesson: 2020/04/23, 10:20 -> 12:20
  • Introduction to the course
  • The Linux scheduler
• Second lesson: 2020/04/30, 14:30 -> 16:30
• Third lesson: 2020/05/07, 14:30 -> 16:30
  • Something more about the Linux scheduler internals
  • Patch transforming SCHED_DEADLINE into a partitioned scheduler
• Fourth lesson: 2020/05/14, 10:20 -> 12:20
  • Followup to the Patch transforming SCHED_DEADLINE into a partitioned scheduler: remove the migration related code. Note that this second patch does not apply cleanly to the kernel tree used for the lessons... Exercise: forward-port the patch to the kernel we are using.
  • A different approach to SCHED_DEADLINE migrations, based on "adaptive partitioning". Could be interesting to implement as a project.
  • Introduction to memory management in the Linux kernel
• Fifth lesson: 2020/05/18, 16:30 -> 19:00
  • Again on Linux memory management (slab allocators)
  • The research papers on which the original SLAB allocator is based are: "The Slab Allocator: An Object-Caching Kernel Memory Allocator", by Jeff Bonwick, and "Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources", by Jeff Bonwick and Jonathan Adams.
• Sixth lesson: 2020/05/21, 10:30 -> 12:30
  • Again on virtual memory
• Seventh lesson: 2020/05/25, 16:30 -> 19:00
  • Again on brk(), mlockall() and page faults
  • mmap() and its friends: example of anonymous mapping
  • Example of device supporting mmap(), with test program. IMPORTANT NOTE: in order to automatically invoke mdev to create the device file, the kernel must be compiled with the CONFIG_UEVENT_HELPER option enabled!!!
  • Similar example sharing the memory buffer, with two test program: send and recv
• Eighth lesson: 2020/05/28, 10:20 -> 12:20
  • Introduction to the Linux networking stack

Ideas about Possible Projects for the Exam

Some projects are simpler than others; if you decide to work on a project, please contact me first; if you have ideas about different projects, contact me to discuss them.

• Modify the SCHED_DEADLINE migration mechanism to implement Adaptive Partitioning (note: an updated version of the paper contains better implementation details; ask me for it if you plan to work on this project) Project already taken
• When forced threadirqs are used, try to move all the network processing to the network interrupd handler thread, removing the network softirqs
• Related to the previous project: look at the threaded NAPI patchset, and design an integration with threaded irq handlers / forced threadirqs
• Compare the performance of SLAB, SLUB and SLOB through a set of experiments (note: to really measure the slab allocator performance, and not some random noise, you need to carefully design the experiments!)
• Experimentally verify how many times the buddy allocator is used to invoke one single physical memory page, and how many times it is used of higher-order allocations (use an appropriate workload, otherwise you will not be able to measure anything) Also check which kernel subsystems need higher-order allocations (you can use ftrace to find out this information)
• Implement some kind of IPC mechanism based on shared memory, using a kernel module (you can extend and improve the shared mmap() example seen during the course). Then, compare the performance of this IPC mechanism with the ones of an equivalent IPC based on the read() and write() system calls
• Analyze the behaviour of a Linux kernel under a high network load (using netperf, or similar tools) and check which fraction of the CPU time is spent in the network softirqs (NET_RX_SOFTIRQ and NET_TX_SOFTIRQ) and which fraction of CPU time is consumed by the application sending and receiving data. Is it possible to move processing time from NET_RX_SOFTIRQ to the application using some form of early demultiplexing?
• Under high network load, try to isolate one or more core from network processing by modifying the CONFIG_RPS code

Interesting Kernel CallChains:

• Some callchains related to the scheduler
• How page faults are handled
• Some more details about mm_populate()

Downloads:

• The linux kernel source
• A minimal fs to boot it
• A program to transform processes in SCHED_DEADLINE
• Kernel patch to print an error in the kernel log when setting SCHED_DEADLINE for a task with affinity mask not compatible with gEDF

Interesting Papers:

• Bonwick, Jeff. "The slab allocator: An object-caching kernel memory allocator." USENIX summer. Vol. 16. 1994.
• Bonwick, Jeff, and Jonathan Adams. "Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources." USENIX Annual Technical Conference, General Track. 2001.
• Mogul, Jeffrey C., and K. K. Ramakrishnan. "Eliminating receive livelock in an interrupt-driven kernel." ACM Transactions on Computer Systems 15.3 (1997): 217-252.