We're hiring!
*

Implementing a performance boosting algorithm in Coccinelle

Jaskaran Singh avatar

Jaskaran Singh
January 21, 2021

Share this post:

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.

What is Coccinelle?

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.

How it works

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.

Implementing the algorithm

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:

  • While parsing a C file, Parse its included header files recursively. Parse each header file only once.
  • While parsing a header file, figure out types of relevant C constructs (struct fields, typedefs) and store the names of each in a cache. Map a name to the file its declared in and the type associated to the name.
  • While parsing a header file, create a dependency graph to figure out what header file is reachable from which C file.
  • When parsing a C file, and encountering a variable with an unknown type:
    • Lookup the name cache for the variable.
    • Determine reachability of the header file that variable is declared in using the dependency graph.
    • Grab the type of the reachable file's variable.

Result

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!

Comments (0)


Add a Comment






Allowed tags: <b><i><br>Add a new comment:


Search the newsroom

Latest Blog Posts

Automatic regression handling and reporting for the Linux Kernel

14/03/2024

In continuation with our series about Kernel Integration we'll go into more detail about how regression detection, processing, and tracking…

Almost a fully open-source boot chain for Rockchip's RK3588!

21/02/2024

Now included in our Debian images & available via our GitLab, you can build a complete, working BL31 (Boot Loader stage 3.1), and replace…

What's the latest with WirePlumber?

19/02/2024

Back in 2022, after a series of issues were found in its design, I made the call to rework some of WirePlumber's fundamentals in order to…

DRM-CI: A GitLab-CI pipeline for Linux kernel testing

08/02/2024

Continuing our Kernel Integration series, we're excited to introduce DRM-CI, a groundbreaking solution that enables developers to test their…

Persian Rug, Part 4 - The limitations of proxies

23/01/2024

This is the fourth and final part in a series on persian-rug, a Rust crate for interconnected objects. We've touched on the two big limitations:…

How to share code between Vulkan and Gallium

16/01/2024

One of the key high-level challenges of building Mesa drivers these days is figuring out how to best share code between a Vulkan driver…

Open Since 2005 logo

We use cookies on this website to ensure that you get the best experience. By continuing to use this website you are consenting to the use of these cookies. To find out more please follow this link.

Collabora Ltd © 2005-2024. All rights reserved. Privacy Notice. Sitemap.