I was meaning to write about switches vs. function pointers this week but got sidetracked by a friend challenging me to run an Arqua analysis on the Linux kernel. After cloning the kernel git and building an “unconfigured” kernel for arm with the appropriate Makefile patches I was struck by a storm of bugs in Arqua. After days of fixing my own unpleasantly unstructured code and adding new visualisation elements to Arqua, I managed to produce the following image of the recently tagged v3.5-rc4:

high resolution

Moving in even further we get this:

high resolution

Now, I am extremely naive when it comes to the Linux kernel, so this is strictly an objective analysis of the structure only. The result also assumes that the directory structure is a reflection of the architecture. This is of course not necessarily true, but the way Arqua operates (and in my personal opinion a sound way to structure source code).

The report shows us the following top five list of smells:

• linux: Complexity Smells:102808
• linux: Tangle Smells:81177
• linux/fs: Complexity Smells:65901
• linux/kernel: Complexity Smells:49215
• linux/mm: Complexity Smells:35691

The total number of smells is 568167 and the quality only 3%. So why the low score? The further up in the structure you get the bigger the smells get. Looking at the kernel, the top structure has lots of edges and could perhaps be broken down even further (again, I am not knowledgeable with how the Linux kernel works, and could not do any qualified guesses on how). The top structure also has a lot of tangles that really should be resolved.

Changes to Arqua

A few changes to the Arqua options was needed in order to be able to create visualisations of the Linux kernel. The following options were changed/added:

• -packages tells Arqua to draw packages
• -files tells Arqua to draw files
• -functions tells Arqua to draw functions
• -levels replaces the old -start and -stop options and tells Arqua how many levels of package abstraction to draw

At least one of -packages, -files or -functions needs to be set when running Arqua.

Generating Your Own Linux Kernel Analysis

Generating this analysis for your own version and configuration is quite easy. First add the -fdump-rtl-expand command to KBUILD_CFLAGS to get the build to generate the needed RTL files:

KBUILD_CFLAGS += -fdump-rtl-expand

Secondly, to get a better result, make sure you do not optimize the code for speed. It seems like the RTL files are post-optimization files. This will give us strange dependencies caused by inlining functions. I couldn’t remove the optimizations completely without getting compilation errors, but there is an option to do size optimization instead so this is what I did. Either make sure that your configuration sets CONFIG_CC_OPTIMIZE_FOR_SIZE or just do it the lazy way as I did and change the Makefile while you are at it:

KBUILD_CFLAGS += -Os

This is everything you need. Build your kernel and make sure that you get RTL files in the source structure (with the .expand extension).

After the kernel is built it is time to run Arqua. I have made an other Makefile for this that should be put in the directory above the kernel:

OUTDIR := out
SRCDIR := linux

EXPANDS := $(shell find $(SRCDIR) -type f -name '*.expand')

$(OUTDIR)/system.pdf: $(OUTDIR)/system.dot
    @ mkdir -p $(dir $@)
    dot -Tpdf -o $@ $<

$(OUTDIR)/system.dot : $(EXPANDS)
    @ mkdir -p $(dir $@)
    arqua -levels 2 -packages -root $(SRCDIR) $(EXPANDS) > $@

clean:
    @ rm -rf $(OUTDIR)

This Makefile scans the kernel directory (in my case linux), finds all the RTL files, and sends these to Arqua. A dot file is generated in the out directory and then the Graphviz tool dot is used to create a pdf. You can change this to an other image format if you like. The pdf generator is good for large images since it is vector based and thus possible to zoom.

The example Makefile uses the -levels 2 -packages option. To get more details change to -levels 3 -packages. Any more details and dot has problems generating an image. You can choose to generate a specific folder with full details by changing the SRCDIR variable in the Makefile. When doing so it is also possible to add the -files option to show add files to the image. The following image uses the option levels 4 -packages -files -root linux/kernel:

high resolution

Summary

After a lot of bugfixes in Arqua it is now possible to analyse rather complex systems as the Linux kernel. The kernel itself seems to have a quite tangled and complex structure. I am not sure if it is relevant to improve this structure according to the complexity model described in previous posts. Perhaps the analysis model itself needs some improvement and perhaps the thresholds needs to be adjusted, or perhaps the Linux kernel really do need some restructuring. Any input on these topics is highly welcome.