LIBRENEITOR

Eudyptula Challenge Version 2: Problems and Solutions

Thu, Jul 4, 2019

Bootcamp-like set of challenges to become a Kernel Developer

I’m sure if you go directly to the original Eudyptula Challeng Website you will find that you can’t enroll in to it. But fear not! You can do all the exercises alone.

The Eudyptula consist in some sort of group where the leader gives you an exercise to you to resolve. Once you resolve it the leader or mentor checks it. If it’s ok you can continue to the next exercise. If that is true, the only thing you really need is the repo with all the exercises and solutions. Right? Well… Here it is the repo.

You need to complete a total of 20 tasks to finish the Eudyptula challenge. Everything of what follows next is the adaptation of the original mailing list problems to a more web-like format. So, keep that in mind because I’m not the original creator of these exercises. If I’m not wrong, the creator is Vitaly Osipov.

Task 1: Hello World!

Write a Linux kernel module, and stand-alone Makefile, that when loaded prints to the kernel debug log level, “Hello World!” Be sure to make the module be able to be unloaded as well.

The Makefile should build the kernel module against the source for the currently running kernel, or, use an environment variable to specify what kernel tree to build it against.

SOLUTION

Task 2: Build a Custom Kernel

  1. Download Linus’s latest git tree from git.kernel.org
  2. Build it, install it, and boot it. You can use whatever kernel configuration options you wish to use, but you must enable CONFIG_LOCALVERSION_AUTO=y.
  3. Bonus points for you if you do it on a “real” machine, and not a virtual machine.

Hint, you should look into the make localmodconfig option, and base your kernel configuration on a working distro kernel configuration. Don’t sit there and answer all 1625 different kernel configuration options by hand.

After doing this, don’t throw away that kernel and git tree and configuration file. You’ll be using it for later tasks, a working kernel configuration file is a precious thing, all kernel developers have one they have grown and tended to over the years. This is the start of a long journey with yours, don’t discard it.

SOLUTION

Task 3: Modify your Kernel

Now that you have your custom kernel up and running, it’s time to modify it:

  1. Take the kernel git tree from Task 02 and modify the Makefile to and modify the EXTRAVERSION field. Do this in a way that the running kernel (after modifying the Makefile, rebuilding, and rebooting) has the characters -eudyptula in the version string.
  2. Create a patch that shows the Makefile modified. Do this in a manner that would be acceptable for merging in the kernel source tree. Read the file Documentation/SubmittingPatches and follow the steps there.

SOLUTION

Task 4: Style it

Part of the job of being a kernel developer is recognizing the proper Linux kernel coding style. The full description of this coding stylecan be found in the kernel itself, in the Documentation/CodingStyle file. I’d recommend going and reading that right now, it’s pretty simple stuff, and something that you are going to need to know and understand. There is also a tool in the kernel source tree in the scripts/ directory called checkpatch.pl that can be used to test for adhering to the coding style rules, as kernel programmers are lazy and prefer to let scripts do their work for them…

And why a coding standard at all? Once your brain learns the patterns, the information contained really starts to sink in better. So it’s important that everyone follow the same standard so that the patterns become consistent. In other words, you want to make it really easy for other people to find the bugs in your code, and not be confused and distracted by the fact that you happen to prefer 5 spaces instead of tabs for indentation.

Anyway, the tasks for this round all deal with the Linux kernel coding style. This two kernel modules, module1 and module2, do not follow the proper Linux kernel coding style rules. Please fix both of them up, in such a way that does follow the rules.

SOLUTION

Task 5: USB

Take the kernel module you wrote for task 01, and modify it so that when a USB keyboard is plugged in, the module will be automatically loaded by the correct userspace hotplug tools which are implemented by depmod / kmod / udev / mdev / systemd, depending on what distro you are using.

As a hint, go read chapter 14 of the book, “Linux Device Drivers, 3rd edition.” Don’t worry, it’s free, and online, no need to go buy anything.

Task 6: Character Device

  1. Take the kernel module you wrote for task 01, and modify it to be a misc char device driver. The misc interface is a very simple way to be able to create a character device, without having to worry about all of the sysfs and character device registration mess. And what a mess it is, so stick to the simple interfaces wherever possible.
  2. The misc device should be created with a dynamic minor number, no need running off and trying to reserve a real minor number for your test module, that would be crazy.
  3. The misc device should implement the read and write functions.
  4. The misc device node should show up in /dev/eudyptula.
  5. When the character device node is read from, your assigned id is returned to the caller.
  6. When the character device node is written to, the data sent to the kernel needs to be checked. If it matches your assigned id, then return a correct write return value. If the value does not match your assigned id, return the “invalid value” error value.
  7. The misc device should be registered when your module is loaded, and unregistered when it is unloaded.

Task 7: Rebuild it

Turns out that’s what most developers end up doing, tons and tons of rebuilds, not writing new code. Sad, but it is a good skill to know.

The tasks is: Download the linux-next kernel for today. Or tomorrow, just use the latest one. It changes every day so there is no specific one you need to pick. Build it. Boot it.

You should read the excellent documentation about how the Linux kernel is developed in Documentation/development-process/ in the kernel source itself. It’s a great read, and should tell you all you never wanted to know about what Linux kernel developers do and how they do it.

Task 8: debugfs

debugfs should be mounted by your distro in /sys/kernel/debug/, if it isn’t, then you can mount it with the line:

mount -t debugfs none /sys/kernel/debug/

Make sure it is enabled in your kernel, with the CONFIG_DEBUG_FS option, you will need it for this task.

The task, in specifics is:

  1. Take the kernel module you wrote for task 01, and modify it to be create a debugfs subdirectory called eudyptula. In that directory, create 3 virtual files called id, jiffies, and foo.
  2. The file id operates just like it did for example 06, use the same logic there, the file must be readable and writable by any user.
  3. The file jiffies is to be read only by any user, and when read, should return the current value of the jiffies kernel timer.
  4. The file foo needs to be writable only by root, but readable by anyone. When writing to it, the value must be stored, up to one page of data. When read, which can be done by any user, the value must be returned that is stored it it. Properly handle the fact that someone could be reading from the file while someone else is writing to it.
  5. When the module is unloaded, all of the debugfs files are cleaned up, and any memory allocated is freed.

Task 9: sysfs

Along with debugfs, sysfs is a common place to put information that needs to move from the user to the kernel. So let us focus on sysfs for this task.

The task this time: Take the code you wrote in task 08, and move it to sysfs. Put the eudyptula directory under the /sys/kernel/ location in sysfs.

I’d recommend reading Documentation/kobject.txt as a primer on how to use kobjects and sysfs.

Task 10: Your first patch

Go back to the linux-next tree you used for task 07. Update it, and then do the following:

  1. Create a patch that fixes one coding style problem in any of the files in drivers/staging/.
  2. Make sure the patch is correct by running it through scripts/checkpatch.pl.
  3. Submit the code to the maintainer of the driver/subsystem, finding the proper name and mailing lists to send it to by running the tool, scripts/get_maintainer.pl on your patch.

Hopefully this patch will be accepted into the kernel tree, and all of a sudden, you are an “official” kernel developer!

Task 11: Modify a driver

Remember that mess of kobject and sysfs code back in task 9? Let’s move one level up the tree and start to mess with devices and not raw kobjects. For this task:

  1. Write a patch against any driver that you are currently using on your machine. So first you have to figure out which drivers you are using, and where the source code in the kernel tree is for that driver.
  2. In that driver, add a sysfs file to show up in the /sys/devices/ tree for the device that is called id. As you might expect, this file follows the same rules as task 9 as for what you can read and write to it.
  3. The file is to show up only for devices that are controlled by a single driver, not for all devices of a single type (like all USB devices. But all USB maibox LEDs would be acceptable, if you happen to have the device that that driver controls.)

Task 12: Linked lists

The kernel has a unique way of creating and handling linked lists, that is quite different than the “textbook” way of doing so. But, it turns out to be faster, and simpler, than a “textbook” would describe, so that’s a good thing.

For this task, write a kernel module, based on your cleaned up one from task 04, that does the following:

  1. You have a structure that has 3 fields:

    char  name[20];
    int   id;
    bool  busy;
    name this structure identity.
  2. Your module has a static variable that points to a list of these identity structures.

  3. Write a function that looks like:

    int identity_create(char *name, int id)
    that creates the structure identity, copies in the name and id fields and sets busy to false. Proper error checking for out of memory issues is required. Return 0 if everything went ok; an error value if something went wrong.
  4. Write a function that looks like:

    struct identity *identity_find(int id);
    that takes a given id, iterates over the list of all ids, and returns the proper struct identity associated with it. If the identity is not found, return NULL.
  5. Write a function that looks like:

    void identity_destroy(int id);
    that given an id, finds the proper struct identity and removes it from the system.

Your module_init() function will look much like the following:

struct identity *temp;

identity_create("Alice", 1);
identity_create("Bob", 2);
identity_create("Dave", 3);
identity_create("Gena", 10);

temp = identity_find(3);
pr_debug("id 3 = %s\n", temp->name);

temp = identity_find(42);
if (temp == NULL)
    pr_debug("id 42 not found\n");

identity_destroy(2);
identity_destroy(1);
identity_destroy(10);
identity_destroy(42);
identity_destroy(3);

Properly check the return values of the above functions.

Task 13: Custom allocators

Now that we are allocating a structure that we want to use a lot of, we might want to start caring about the speed of the allocation, and not have to worry about the creation of those objects from the “general” memory pools of the kernel.

This task is to take the code written in task 12, and cause all memory allocated from the ‘struct identity’ to come from a private slab cache just for the fun of it.

Instead of using kmalloc() and kfree() in the module, use kmem_cache_alloc() and kmem_cache_free() instead. Of course this means you will have to initialize your memory cache properly when the module starts up. Don’t forget to do that. You are free to name your memory cache whatever you wish, but it should show up in the /proc/slabinfo file.

Task 14: Tasks

  1. Add a new field to the core kernel task structure called id.
  2. When the task is created, set the id to your id.
  3. Add a new proc file for every task called, id, located in the /proc/${PID}/ directory for that task.
  4. When the proc file is read from, have it print out the value of your id, and then increment it by one, allowing different tasks to have different values for the id file over time as they are read from.

Task 15: new syscall

This task is one of the most common undergraduate tasks there is: create a new syscall! It’s good to know the basics of how to do this, and, how to call it from userspace:

  1. Add a new syscall to the kernel called sys_eudyptula, so this is all going to be changes to the kernel tree itself, no stand-alone module needed for this task (unless you want to do it that way without hacking around the syscall table, if so, bonus points for you…)
  2. The syscall number needs to be the next syscall number for the architecture you test it on.
  3. The syscall should take two parameters: int high_id, int low_id.
  4. The syscall will take the two values, mush them together into one 64bit value (low_id being the lower 32bits of the id, high_id being the upper 32bits of the id).
  5. If the id value matches the id 7c1caf2f50d1, then the syscall returns success. Otherwise it returns a return code signifying an invalid value was passed to it.
  6. Write a userspace C program that calls the syscall and properly exercises it (valid and invalid calls need to be made).

Task 16: sparse

Go install the tool sparse. It was started by Linus as a static-analysis tool that acts much like a compiler. The kernel build system is set up to have it run if you ask it to, and it will report a bunch of issues in C code that are really specific to the kernel.

When you build the kernel, pass the C=1 option to the build, to have sparse run on the .c file before gcc is run. Depending on the file, nothing might be printed out, or something might.

The task this time is: 1. Run sparse on the drivers/staging/ directory. 2. Find one warning that looks interesting. 3. Write a patch that resolves the issue. 4. Make sure the patch is correct by running it through scripts/checkpatch.pl. 5. Submit the code to the maintainer of the driver/subsystem, finding the proper name and mailing lists to send it to by running the tool, scripts/get_maintainer.pl on your patch.

That’s it, much like task 10 was, but this time you are fixing logical issues, not just pesky coding style issues. You are a real developer now, fixing real bugs!

Task 17: Kernel Thread

Go dig up your code from task 06, the misc char device driver, and make the following changes:

  1. Delete the read function. You don’t need that anymore, so make it a write-only misc device and be sure to set the mode of the device to be write-only, by anyone. If you do this right, udev will set up the node automatically with the correct permissions.
  2. Create a wait queue, name it wee_wait.
  3. In your module init function, create a kernel thread, named of course eudyptula.
  4. The thread’s main function should not do anything at this point in time, except make sure to shutdown if asked to, and wait on the wee_wait waitqueue.
  5. In your module exit function, shut down the kernel thread you started up.

Task 18: Delayed work

Base all of this work on your task 17 codebase. Go back and dig up task 12’s source code, the one with the list handling. Copy the structure into this module, and the identity_create(), identity_find(), and identity_destroy() functions into this module as well.

Write a new function, identity_get(), that looks like:

struct identity identity_get(void);

and returns the next identity structure that is on the list, and removes it from the list. If nothing is on the list, return NULL.

Then, hook up the misc char device “write” function to do the following: 1. If a write is larger than 19 characters, truncate it at 19. 2. Take the write data and pass it to identity_create() as the string, and use an incrementing counter as the “id” value. 3. Wake up the wee_wait queue.

In the kernel thread function:

  1. If the wee_wait queue wakes us up, get the next identity in the system with a call to identity_get().
  2. Sleep for 5 seconds in an interruptable state, don’t go increasing the system load in a bad way.
  3. Write out the identity name, and id to the debug kernel log and then free the memory.

When the module exits, clean up the whole list by using the functions given, no fair mucking around with the list variables directly.

Yes, it’s a bit clunky, but it shows the basics of taking work from userspace, and then quickly returning to the user, and then going off and doing something else with the data and cleaning everything up. It’s a common pattern for a kernel, as it’s really all that a kernel ends up doing most of the time.

Load and unload the module and test that it works properly by writing and looking at the debug log, and that everything cleans up properly when the module is unloaded.

Removing the module while there is pending work is always a good stress test.

Task 19: Networking filters

For this task, write a netfilter kernel module that does the following:

  1. Monitors all IPv4 network traffic that is coming into the machine.
  2. Pints the id to the kernel debug log if the network traffic stream contains your id.
  3. Properly unregisters you from the netfilter core when the module unloads.

Test this by sending yourself an email with your id in the subject.

Task 20: File System - End Game

So, here’s the final task.

There might be other tasks that get created and added out later on, but the original challenge had 20 tasks, so after finishing this one, you can consider yourself done!

Let’s try something a bit harder. Something that might cause some data loss on a filesystem, always a fun thing to play with, if for no other reason than to not be afraid of things like that in the future.

This task requires you to work on the fat filesystem code: 1. Add an ioctl to modify the volume label of a mounted fat filesystem. Be sure to handle both 16 and 32 bit fat filesystems. 2. Create a userspace .c program to test this new ioctl.

Make sure you don’t run into 32/64bit kernel issues with the ioctl, if you do things correctly, you shouldn’t have any problems.

I recommend doing this work on either a loop-back fat filesystem on your “normal” filesystem, or on a USB stick. Either will work just as well, and make things easier to debug and test.

Watch out for locking issues, as well as dirty filesystem state problems.

Best of luck!