- Release Date: 2/12/2025
- Due: 2/20/2025 11:59pm
Introduction
This exercise aims to familiarize you with essential data structures in the Linux kernel, including lists, hashtable, red-black tree, radix tree, and xarray. To facilitate testing, you will rely on a file in the /proc filesystem that prints the contents of these data structures.
Turn in ${YourPID}-lkp25-ex1.tar.gz including source code and Makefile on Canvas.
Recommended Background Reading
- Linux /proc file system
- Bash Scripting Tutorial for Beginners
- Bash Scripting Tutorial
- Bash Guide for Beginners
- Explain Shell
Description
Skeleton code: here
You should enhance the provided kernel module (skeleton code) to store integer numbers passed as kernel module parameters to these four data structures. Be sure that your code properly allocates memory as well as properly frees memory where the inserted data was put upon module unloading.
The kernel module accepts the parameter int_str="1,2,3,4,5" and uses /proc/lkp25-ex1 as an output interface. Refer to test-ex1.sh, the expected output should match the example below. The /proc file interface is already implemented in the skeleton code; your task is to understand and use it correctly.
$ cat /proc/lkp25-ex1
Linked list: 1, 2, 3, 4, 5
Hash table: 3, 4, 1, 2, 5
Red-back tree: 1, 2, 3, 4, 5
Radix tree: 1, 2, 3, 4, 5
XArray: 1, 2, 3, 4, 5
$ dmesg
[...] Linked list: 1, 2, 3, 4, 5
[...] Hash table: 3, 4, 1, 2, 5
[...] Red-back tree: 1, 2, 3, 4, 5
[...] Radix tree: 1, 2, 3, 4, 5
[...] XArray: 1, 2, 3, 4, 5
You can also use ./test-ex1.sh for end to end testing.
$ ./test-ex1.sh
Points Distribution
- 10 pts: linked list working
- 10 pts: hash table working
- 10 pts: red-black tree working
- 10 pts: radix tree working
- 10 pts: Xarray working
Please make sure you code compiles and runs correctly after removing ccflags-y += -Wno-unused-variable -Wno-unused-function in the Makefile.