Jaskaran Singh
January 21, 2021
Reading time:
Last year, from June to September, I worked on the kernel development tool Coccinelle under Collabora. I implemented a performance boosting algorithm for one of Coccinelle's use cases. Here's a look at this work.
Coccinelle is a tool used to refactor C source code. It's used for development in the Linux Kernel. You write an abstract patch (called a Semantic patch in Coccinelle terms), basically to remove a few lines of code and add some, to make a tree-wide change.
Coccinelle uses the semantic patch language for this purpose. Following is a basic example of a semantic patch:
@@ expression E; constant c; type T; @@ -kzalloc(c * sizeof(T), E) +kcalloc(c, sizeof(T), E)
When applied to the tree, the above semantic patch replaces every instance of kzalloc with kcalloc.
For more information, check out this page.
On the inside, Coccinelle has a semantic patch parser and a C parser. When fed a semantic patch and a C file, Coccinelle parses the semantic patch to create an AST, and parses the C file to create an AST as well.
Following this, it compares the semantic patch AST with the C AST. If matches are found, the changes detailed in the semantic patch are made to the C file.
During my work on Coccinelle, I implemented a performance boosting algorithm to speed up recursive parsing of header files in the Linux Kernel.
Coccinelle has an option to parse included header files recursively to figure out types of certain C constructs such as struct fields and typedefs. This is necessary in some cases, as Coccinelle can only look at one C file at a time.
Initially, this recursive parsing would take close to 7 hours for the entire Linux Kernel. Since the target userbase of Coccinelle is kernel developers, 7 hours wasn't a very good benchmark.
Implementation of the performance boosting algorithm resulted in that time coming down to 45 minutes. For the curious, following is the algorithm:
The algorithm isn't perfect, as it still takes 45 minutes to get everything done. There's a lot more that could be done, like leveraging multiprocessing (a whole other can of worms), or conditionally parsing the files based on the semantic patch's matches. However, it works relatively fine on a moderately fast PC.
Thank you Collabora for financially supporting this project!
08/06/2023
Contrary to traditional software development, data is more important than code in machine learning. Building a high-performing model requires…
31/05/2023
A while back I presented USB 2.0 host support that was added to U-boot for the Radxa Rock-5B RK3588 Rockchip board. This time, USB 3.0 was…
18/05/2023
Work continues on the Radxa ROCK5B RK388, as PCIe and RTL8125B networking support in U-boot have now been added. Publishing code as Open…
03/05/2023
NVK, an open-source Vulkan driver for NVIDIA hardware that is part of Mesa, now supports the Vulkan extension VK_KHR_multiview.
27/04/2023
The beauty of Open Source is that we can reuse code written by many other people, keep their authorship, and credit them for their work,…
18/04/2023
Want to develop your Meson project in a modern IDE? Make sure to install Meson VSCode extension which is now fully functional with the recent…
Comments (0)
Add a Comment